11-мавзу. Паралел дастурлаш

11-мавзу. Паралел дастурлаш

Режа:
1. Ечимлар майдони

2. Параллел алгоритмлар
3. Aмалий дастурлаш тизимлари
4. Дастурлаш тилларидаги параллеллик моделлари

Аппарат воситаларини ишлаб чиқаришнинг ривожланиши дастурлаш технологияларининг ривожланишидан анча олдинлаб кетди. Параллел архитектуралар энди кўплаб масалаларни ҳал қилиш учун дастурларнинг самарадорлигини ошириш имкониятини яратди.. Дастурларни автоматик равишда параллеллаштириш усуллари вектор элементларини қайта ишлаш бўйича мустақил жараёнлар комплексигача қисқартириладиган ҳисоб-китобларни сезиларли даражада тезлашишини таъминлайди, лекин улар дастурларининг кенгроқ синфлари олдин орқага чекинадилар.

Янги масалаларни қўйиш даражасида, параллелизмни тил воситалари билан ифода этиш истиқболини, компиляциясини текширишни оптималлаштириш муаммолари секинлаштириб қўймоқда, бу эса самарали ва ишончли параллеллик схемасини аниқ танлашни таъминлайди. Бундан ташқари, такрорий дастурлаш ва параллел алгоритмларни отладка қилишнинг меҳнат хажми, кетма-кет ҳисоблаш натижаларини баҳолашда тайёр дастурларни мезон сифатида кўриб чиқилишини белгилайди, бу эса параллел дастурлаш тиллари ва уларни амалга ошириш усулларининг ривожланишини орқага тортади.
Базавий тушунчалар тизимини кенгайтириш ва ривожлантириш натижасида, ҳозирги вақтда, замонавий аппарат воситаларда жараёнларни бошқариш тизимларини рационал ишлаб чиқиш учун зарур бўлган, параллел дастурлаш парадигмасини шакллантиришнинг долзарблигини англаш жараёни содир бўлмоқда.
Дастурлашдаги парадигмалар, турли масалаларини ечишдаги фикрлаш услуби, ишлатилган тушунчалар тизими ва уларни амалга оширишнинг ўзига хос хусусиятлари билан тавсифланади. Дастурлаш тиллари эволюцияси жараёнида, параллел дастурлаш учун, фикрлаш услуби ва тушунчалар тизими аллақачон шакилланиб бўлган деб қараш мумкин, лекин уларнинг дастурлаш тизимларидаги одатий қўллаб-қувватланиши ҳали шаклланмаган деб айтиш мумкин.
“Параллелликнинг фундаменталь қийинчиликларини яширишнинг иложи йўқ”, деди Мартин Одерский (Martin Odersky), 2011 йил март ойида Германияда Женс Кнооп раислигида бўлиб ўтган “Компилятор дизайни” бўйича 20-халқаро конференциясида қилинган нутқида. Кўп сонли уринишларга қарамай, дастурлаш тиллари ва тизимларининг янги авлоди учун умумий ғоялар ҳали пайдо бўлмаганлиги сабабли, анъанавий дастурлашнинг кенгайтмаси сифатида қаралмайдиган ва дастурлаш тизимларида мустақил маънога эга бўлган параллелизм ҳали шакилланиб улгармади.
1. Ечимлар майдони
Ҳозирги кунда параллел дастурлашга қизиқишнинг ортиши кўп ядроли архитектураларни оммавий ишлаб чиқаришга ўтиш билан боғлиқ. Ушбу материалдаги параллел дастурлаш тушунчалари ва жараёнлари билан танишиш анъанавий кетма-кет дастурлаш тамойилларига кучли қарамликнинг профилактика қилишга яъний олдини олишга қаратилган. Бундай профилактика тақсимланган ахборот тизимларини, шунингдек суперкомпютерлар, кўп процессорли конфигурациялар ва график процессорлар учун дастурларни ишлаб чиқаришга ихтисослашиш учун жуда муҳимдир.
Aмалиётда тиллар ва дастурлаш тизимларининг замонавий ривожланиши, параллел дастурлаш масалаларини ҳал қилишга қаратилган. Қоида тариқасида, янги тиллар ва дастурлаш тизимларга, жараёнларни ташкил этишни таъминлайдиган кутубхона модуллари ёки кўп тармоқли дастурлаш имкониятини берадиган суб-тиллар киради.
Бу аввал отладка қилинган анъанавий дастурларни қўлда параллеллаштиришни, уларни параллел ҳисоб-китобларни қўллаб-қувватлаш учун ишлаб чиқариш тизимларидан фойдаланиш учун қулай шаклга келтиришнинг реал амалиётини истисно этмайди. Бундай ишларнинг муҳим қисми техник хусусиятга эга ва маълумотлар тузилмаларини тизимли равишда қайта ташкил этиш, ўзгарувчилар статусини ўзгартириш ва дастурга аннотацияларни киритиш, шу билан компиляторга ахборот-технологик алоқалар тўғрисида маълумот бериш.
Қўлда параллеллаштириш натижаларини сезиларли даражада чеклаши нафақат алгоритмни қайта отладка қилиш хавфи, балки унинг мақсадли архитектура хусусиятларига қатъий боғлиқлигидир.
Параллел ҳисоблаш моделларининг хилма-хиллиги ва мавжуд архитектура доирасининг кенгайиши, кўп процессорли конфигурациялар учун кўп қиррали дастурларни компиляция қилиш усулларини яратиш масаласини ҳал қилишга қодир дастурлаш тиллари ва тизимларини ишлаб чиқарувчилар учун қийинчилик сифатида қаралиши керак. Тил реаль архитектура ёрдамида ҳал қилинадиган ёки амалга оширилаётган муаммо даражасида намоён бўладиган ҳар қандай параллелликнинг моделларини акс эттиришга имкон бериши керак ва бундай вакиллик уларни қайта ташкил этиш пайтида дастурларнинг хусусиятларини сақлашни кафолатлайдиган лаконик шакллар ва конструктив тизилмаларни талаб қилади.
Параллел ҳисоблаш воситалари ва усуллари ривожланиб бораётганлиги сабабли, тилнинг кенгайтирилиши муҳим аҳамиятга эга. Унинг ўсиш суръати, мутахассислар томонидан унинг имкониятларини амалга оширилишини англаш даражасидан, юқори эканлиги намоён бўлмоқда.
Параллел дастурлаш тилларини формаллаштириш масаласини, фойдаланилган кўп процессорли комплекслар ва кўп ядроли процессорларнинг турли хил хусусиятларига дастурларни мослаштириш муаммосини ҳал қилиш усули сифатида кўриб чиқилса, ушбу муаммони ҳал қилиш учун дастурларни компиляция қилишнинг янги усулларини, айниқса маштаблаштириладиган кодогенерациялашни яратиш тизимини ишлаб чиқиш ҳамда параллел дастурлаш тилларнинг семантикасини аниқ тавсифлаш учун воситалар ва усулларни ишлаб чиқиш зарурлигини талаб қилинади.

2. Параллел алгоритмлар

Параллел алгоритмларни амалга ошириш учун параллел жараёнларни ташкил қилишда учрайдиган ечимларнинг умумий кўриниши кўп процессорли архитектура ва тизимларнинг хилма-хиллиги тўғрисида баъзи фикрларни беради:

• 
  процессорлар кўп бўлиши мумкин ва улар турли хил команда тизимларига эга бўлиши мумкин;
  
• 
  процессорлар автоном тарзда ёки биргаликда умумий ишларни бажариши мумкин;
  
• 
  алоҳида процессорлар фойдали иш қилмасдан бўш ишлаши мумкин;
  
• 
  процессорлар ўзларининг локал хотирасига эга ва умумий хотирада ишлашлари мумкин;
  
• 
  процессорлар ўртасида ҳаракатларнинг тақсимланиши дастур томонидан белгиланиши мумкин ёки уни маълум бир ҳисоблаш моделини қўллаб-қувватловчи супервизор амалга ошириши мумкин.
  

Бу асенхрон жараёнларни моделлаштириш йўналиши бўйича табиий ривожланишни таъминлайди, шунингдек буйруқларнинг бажарилиши боғлиқ бўлган дастурни бажариш шароитлари мавжудлигини тушунишга ёрдам беради. Дастурлар бажарилиши натижаларини таҳлил қилишда уларни бошқарадиган барча буйруқлар бажарилишига қарамай, бошқарув хатоларининг турли тоифалари аниқланади ва мумкин бўлмаган ҳаракатлар таъкидланади. Ҳисоблашларни бошқариш воситалари ёрдами билан параллел жараёнларни ташкил қилишда, ҳаракатларни кетма-кет бажарилишининг ноимперативлигини акс эттирувчи, дастурларнинг ишлашини таъминлашни қисман тартибланишининг роли намоён бўлади. Оптималлаштирувчи компиляторлар кўпинча ҳар қандай дастурни мултипрограмма деб ҳисоблайди.
Параллел алгоритмларга ўтиш кўплаб концепцияларнинг мазмунини қайта кўриб чиқишга ва оддий кетма-кет алгоритмлар учун алоҳида маънога эга бўлмаган турли хил ҳодисалар ва эффектларни акс эттирувчи янги атамаларни киритишга олиб келади. Параллел дастурлаш алгоритмик бўлмаган деб номланган кунлар ўтди. Энди “параллел алгоритм” атамаси алгоритмни бир ёки бир гуруҳ ижрочилар бажариши мумкинлигини тушуниш билан боғлиқ. Ушбу тушунча масалаларни ечиш майдонини кескин кенгайтиради, параллелликдан фойдаланган ҳолда ечимларни амалга оширишга ёндашувларни ўзгартиради ва маълум даражада масалаларни шакллантиришга ва параллелликдан фойдаланиш асосида масалаларни ечиш дастурларининг ҳаётий циклини режалаштиришга таъсир қилади.
Aввало, масаланинг қўйилишини шакллантириш билан боғлиқ қуйидаги саволларни аниқлаштириш керак:

1. 
   Параллел алгоритм ёрдамида масалани ечиш дастурининг ҳаётий циклининг мураккаблиги қанча ўзгаради?
   
2. 
   Масалани қўйишда параллеллик модели қай даражада ҳисобга олиниши керак?
   
3. 
   Параллел алгоритм ишлаб чиқишда қандай қилиб ютуқларни асосаш ва ўлчаш мумкин?
   
4. 
   Параллел алгоритмларга ўтишда муаммо қўйилиши қанча ўзгаради?
   
5. 
   Параллел дастурлаш парадигмаси параллел алгоритм ишлаб чиқиш даражасида нимани беради?
   
6. 
   Дастурни ишлаб чиқишдан олдинги босқичда масалани ҳал қилиш учун яратилган параллел алгоритмлар қандай воситалар тақдим этилган?
   

Ярим асрлик муддат давомида анъанавий кетма-кет дастурлаш учун кўплаб дастурлар отладка қилинган, дастурлаш тизимларида ва стандарт кутубхоналарда тўпланган. Рухсат этилган параллелликни ҳисобга олиш учун аллақачон отладка қилинган дастурий ечимларга эга бўлган қўйилган масалаларни ўзгартириш, такрорий дастурлашни амалга ошириш ва бу жуда қийини – такрорий отладкани бажаришдир.
Aсосий аргумент – бу масалани анъанавий алгоритмлардан фойдаланган ҳолда ечишда йўқоладиган табиий параллелликни, масалани қўйиш даражасида, ҳисобга олиш мақсадга мувофиқлиги. Параллел алгоритмларни амалга ошириш учун қулай бўлган параллел дастурлаш тиллари сони йилдан-йилга кўпайиб бормоқда, гарчи уларни қўллаш параллел ҳисоблашни ташкил қилишнинг барча муаммоларини ҳал қилмаса ҳам.
Шундай қилиб, параллел алгоритмни олинган натижаларни кейинчалик бирлаштириш ва мақсадли натижани олиш билан турли хил қурилмаларда қисмларга бўлиб амалга ошириш мумкин. Бу борада aмалий саволлар туғилади:

• 
  aлгоритм таърифида, алоҳида қурилмалар томонидан бажариладиган қисмлар қандай ажратиб кўрсатилган?
  
• 
  aлгоритмни амалга оширишда унинг таърифида келтирилган қурилмалар тўпламидан тўлиқ фойдаланиш керакми?
  
• 
  кетма-кет алгоритмни битта қурилмада бажарилган параллел алгоритм деб ҳисоблаш мумкинми?
  

Қуйидаги саволлар тўплами “вақт” тоифасига тегишли ва синхронизация муаммолари билан боғлиқ:

• 
  Параллел алгоритм қисмлари ўзларининг мустақил ёки марказлашган вақтига эга бўлиши мумкинми?
  
• 
  Aлгоритм қисмларини синхронлаштириш унинг ахборот алоқалари ва бошқарув логикасига зид бўлиши мумкинми?
  
• 
  Aлгоритм қисмларининг синхронизациясини асинхронизациясининг алоҳида ҳодисаси деб ҳисоблаш мумкинми?
  

Параллеллик учун хотирадан фойдаланиш муаммолари келтириб чиқаради:

• 
  Параллел алгоритмнинг ўзаро таъсир қилувчи қисмлари қандай маълумот алмашадилар?
  
• 
  Параллел алгоритм қисмлари умумий хотира ҳолатини ва бошқа қисмларнинг хотирасини ўзгартириши мумкинми?
  
• 
  Параллел алгоритмнинг бир қисми бошқа қисмларга ўзининг хотирасидан фойдаланишга халақит бера оладими?
  

Бундан ташқари, алгоритмнинг қисмлари турли хил ҳисоблаш моделларида ва турли хил маълумотлар тузилмалари орқали аниқланиши мумкин. Параллел алгоритмни ишлаб чиқиш натижаларини баҳолаш, ҳисоб-китобларнинг мураккаблиги ва маълумотларнинг миқдорини баҳолашдан ташқари, ҳар хил турдаги формаллаштирилган мезонларнинг бажарилишини баҳолашнинг мақсадга мувофиқлиги билан мураккаблашади, аммо уларнинг баъзилари моделлардаги замонавий текшириш воситаларида ўзларини текшириш имкониятини беришади.
Ва шунга қарамай, параллеллик дунёси қанчалик мураккаб бўлмасин, дастурчилар буни тушунишлари ва ўзлаштиришлари керак!
Шартли фойдаланиладиган командаларнинг тўлиқ тўпламига эга бўлган янги архитектураларнинг пайдо бўлишини таъкидлаш лозим.
Ҳозирги кунда информатика бўйича тадқиқотлардаги тушунчалар тизимида ўзгаришларни кечирмоқда, амалий IT – да қўлланиладиган концептуал асослар ўзгариб бормоқда. Ушбу жараёнда мураккаб масалаларни ҳал қилиш майдони кенгаймоқда, компютер тармоқлари ва кўп процессорли комплекслар асосида ахборот тизимларини (АТ) ривожлантириш усуллари модернизация қилинмоқда.
Замонавий ахборот тизимлари, айниқса дастурларнинг сифатини баҳолаш мезонлари ва дастурлашнинг ишончлилиги ва унумдорлигини таъминлаш усулларини баҳолаш мезонларини ўзгартирадиган тармоқ технологияларининг ҳамма жойда тарқалиши билан боғлиқ бўлганлиги сабабли дастурлаш парадигмаларининг ривожланиш истиқболларини кўриб чиқиш лозим. Бундай ривожланишнинг иккита асосий йўналиши – тақсимланган ахборот тизимларини ва компонентли дастурлашни ривожлантириш.
Параллел дастурлаш тилларини ишлаб чиқиш ва уларни амалга ошириш ёндашувларини амалий ечимида дастурни намойиш этишнинг лаконик шаклларини танлаш, уларни қайта ташкил этиш пайтида дастурларнинг тўғрилигини сақлашни кафолатловчи конструктив конструкцияларни таъминлаш ва параллел дастурлаш воситалари ва усуллари ривожланиб бориши билан тилнинг кенгайишини қўллаб-қувватлашга эътибор қаратилади.
Параллел дастурлаш парадигмасининг тавсифи дастурларнинг ҳаётий циклида қўлланиладиган визуал воситаларни амалга ошириш ва улардан фойдаланиш шароитидаги прагматик фарқларни акс эттиради. Параллел дастурлаш парадигмалари юқори самарали ҳисоблашларни ташкил қилиш учун кўп процессорли тизимларда ҳисоб-китобларни амалга ошириш дастурларини амалга ошириш билан боғлиқ ўринни эгаллайди. Ушбу ўрин, асенхрон жараёнларнинг фрагментларини комбинаториал бажарилиши натижасида отладка дастурларининг мураккаблигининг кескин ўсишига олиб келади.
Тармоқларнинг ишлаш қоидаларини хилма-хил равишда модефикация қилиш ҳаракатларини асенкрон ва синхрон ташкил этиш, шу жумладан нагрузкаларни дозалаш ва процессорларнинг ихтисослашуви ҳамда ҳаракатларни ижро этиш оқимлари орасида тақсимлаш имконини беради. Иерархик, кўп даражали, тизимли ва кенгайтириладиган тармоқлардан фойдаланиш дастурлаш тилларида тўпланган деярли ҳар қандай дастурлаш техникасини моделлаштиришни ва маълумотлар тузилмаларини намойиш этишни таъминлайди.
3. Aмалий дастурлаш тизимлари
Суперкомпютерларнинг ишлашини ўлчашда ва дастурларни параллеллаштириш бўйича тажрибаларда, асосан, MPI ёрдамида қулай равишда параллеллаштирилган векторли маълумотларни қайта ишлаш алгоритмларини амалга оширадиган илмий ҳисоблаш муаммолари фаол қўлланилади. Замонавий параллел дастурлашнинг амалий вазифалари одатда олдиндан тузатилган C ёки Fortran дастурларини мавжуд дастурлаш тизимларига киритилган стандарт воситалар ёрдамида параллеллаштиришдан фойда келтирадиган шаклга келтиришга ўхшайди. Умуман олганда, бундай ишлар қуйидаги иш турларига келтирилади:

• 
  автоматик параллеллаштиришга имкон берадиган дастур бўлимларини белгилаш;
  
• 
  дастурни параллеллаштиришга тўсқинлик қиладиган иштирокчилар ва сабабларни таҳлил қилиш;
  
• 
  дастурларни паралеллаштириш учун мос келадиган техник шаклга келтиришга имкон берадиган дастур бўлимларини танлаш;
  
• 
  параллеллаштириш имкониятларини кенгайтириш мақсадида, дастур матнини қўлда ўзгартириш учун рецептлар ихтиро қилиш;
  
• 
  дастур матнини максимал параллеллаштирадиган шаклига келтириш;
  
• 
  параллеллаштиришдан олинадиган фойдани баҳолаш учун дастурнинг параллеллаштирилган версиясини ишга тушириш;
  
• 
  талаб қилинган меҳнат унумдорлигига эришишга халақит берадиган эффектларни истисно қилиш ёки камайтириш учун дастур қисмларини қисман қайта дастурлаш ва отладка қилиш;
  
• 
  дастлабки дастур ва унинг натижавий версиясининг қисман функционал эквивалентлигини ўрнатиш.
  

Одатда, компилятор фойдаланилмаган кодни ўчирадиган оптималлаштиришлар-ни қўллаб-қувватлайди, циклларни тозалайди, умумий ифодаларни бирлаштиради, паралелланган тармоқларнинг бир хиллигини таъминлаш учун такрорий бўлимларни узатади, циклни очади ёки ажратади, ўзгармас ҳисоб-китобларни бажаради, операциялар кучини камайтиради, агрегат конструкциялар нусхаларини олиб ташлайди ва ҳоказо.

Ҳисоблаш тезланишининг процессорлар сонига ҳамда умумий ва тақсимланган хотира миқдорига боғлиқлиги кўриб чиқилади. Рекурсияни цикллар билан мунтазам равишда алмаштиришни амалга оширилади. Ягона процессор майдони, умумий хотира, тезкор алмашинув, қўшничилик, юқори самарали ҳисоблаш учун тизимларнинг ишлаш самарадорлигини кафолатлайди.
Параллел жараёнларнинг хусусиятларига хотира билан ишлаш интизомининг таъсири сезиларли. Ҳимояланган ва ёйилган хотира ишлатилади. Кўп даражали ва кўп турдаги хотира (кириш, ён таъсир, кўрсатмалар, дубллар ва нусхалар) билан ишлаш учун турли хил дастурлаш тилларида қабул қилинган қарорлар. Транзакцияларни қайта ишлаш дастурлаш тилларида хотира билан ишлашнинг одатий семантикаларидан бирига айланмоқда.