Жылу конвекцияның кері есебінің шешімінің алгоритмін параллельдеу

 

 

 

 

                       Тегістер                  Циклдық тор          Майысқан тор

14-сурет. Желi типтi топология.

Циклдық желi. Егер тордың жоғарғы торабы тордың төменгi торабымен бiрiктiретiн байланыс болса, онда желiлердiң “циклдық“ байланысы болады.

Циклдық байланыс бар желi топологиясы сәйкес әдебиеттерде торус деп те аталады.

Майысқан тор. Егер циклдық байланыстар бiр немесе бiрнеше жолдармен (бағандарымен, немесе бағандары және жолдарымен қисайса онда желiнiң майысқан торы болады.

Ескерту: майысқан торустың солтүстiк-батыс бұрышынан басталған және шығысқа қарай бағытталған жол, қайтадан солтүстiк-батыс бұрышқа келгенше әр торапқа бiр рет барып шығады.

Көпбаспалдақты желiлер. Мұндай топология бойынша құрылған жүйелер желiсiнiң бiр жақ шетiнде процессорлары және iшкi тораптарында бiрнеше ауыстырғыш элементтерi болуы мүмкiн. Көпбаспалдақты желiлiердiң мысалы – айқастырылған ажыратқыш (15-сурет).

 

 

P2

 

 P2

P0

  P1

P3

M0                   M1                     M2                 M3

 

 

 

 

15-сурет.  Айқастырылған ажыратқыш.

 

Мұндағы Pi – i-шi процессор, Mi – жадының i-шi блогы, қара дөңгелектер жабық ауыстырғыштарды көрсетедi.

Егер процессор  бiр уақытта бiр iске қосуды әрекет жасаса, онда әрбiр бағанның осы уақытта бiр ғана iске қосуы болады. Егер процессор жадының әр түрлi блоктарымен бiрiгуге әрекеттенсе, олардың бiреуi де бұғатталмайды.

“Тоғысулар“-дың  диаметрi қысқа болады. – ақпарат  бiр жақ шетiнен екiншiсiне өткенде бiр ғана ауысу элементiнен өту керек, бiрақ нашар масштабталған.

Баньян желiсi. Баньян желiсi – ауыстырғыштары бар көпбаспалдақты желi, оның кiрiстер мен шығыстар саны бiрдей, iшкi тораптары mxm айырғыш болады. Баньян желiсiнiң мысалы – көбелек желiсi немесе омега желiсi, олардың екеуi де 2x2 айырғыштарынан құрылған. Тоғысулар мен көбелек айырғыштар көппроцессорлы желiлердегi жадыға жалпықатынауды iске асыру үшiн қолданылады (16-сурет).

16-сурет. Көбелек желiсi

Барлық iшiкi тораптар – деретердi тура төбесi арқылы немесе қарама-қарсы жағына (табанына) беру үшiн конфигурацияланатын айырғыштар.

Ауыстырғыштары бар желiлер кiрiсiнен  шығысына дейiн жол салу үшiн тағайындау адресiнiң екiлiк өрнектелуiн қолданады.

Желiнiң i баспалдағында өзiн қалай конфигурациялау керектiгiн шешу үшiн айырғыш i битiн қолданады:

Егер бит 0, сұраныс жоғарғы шығыс  бойынша өтуi керек, ал бит 1-ге тең  болсағ сұраныс табаны бойынша шығуы  керек.

Сонымен, қарастырылған топология  бойынша қорытынды жасаймыз.

ґзара байланыс желiсiнiң үш маңызды атрибуты бар – синхрондау стратегиясы, басқару стратегиясы және ауыстырғыш стратегиясы.

Басқару үшiн екi альтернатива ретiнде:

• Бiр орталық контроллер;

• Немесе бағыттау стратегиясы әрбiр торапта iске  асырылатын  

үлестiрiлген басқару жүйесi болады.

Гиперкубтағы және көбелек типтi айырғыштар тораптарының идентификаторын негiзделген хабарды маршруттау үлестiрiлген басқару мысалы болады, себебi әрбiр торап өзi үшiн кiрiс хабарлдарды қалай бағыттауды шешедi.

Синхрондаудың синхронды және асинхронды стратегиялары  – есептеу жүйелерiнiң фундаментальды сипаттамасы.

Синхронда және асинхронды басқару 

Басқарудың синхронды әдiсi кең  ауөымды сағатпен сипатталған, олар сағат сигналын жүйе жалпы “қатаң“ режимде жұмыс iстейтiндей жүйенiң барлық құрылғыларына жiбередi.

Асинхронды  әдiстер жеке кең акуқымды сағаттарды қолданбайды, синхрондау үшiн көптеген жеке сағаттарды қолдана отырып басқару функциясын бүкiл жүйеге үлестiредi. Жүйенiң әртүрлi бөлiктерiн басқару және үйлестiлiк кейбiр байланыс формасыарқылы немесе “қол алысу“ арқылы жүзеге асырылады.

Басқару үшiн жеке кең ауқымды сағаттардың артықшылығы – аппараттық құрылғыларды да, программалық жасаудағы қарапайымдылық. үлестiрiлген басқарудың артықшылығы – кеңейтiлуi және икемдiлiгiнде.

3.3 Параллель  программалаудың тиімділігін бағалау

Параллель программалауда, жақсы дизайн қолданбалы есепке байланысты белгiлi бiр функцияны  оптимизациялауы керек:

• Орындалу уақытын;

• Жадының  керектi бөлiгi мен конфигурациясы;

• Орындау  шығыны;

• Қызмет көрсету бағасы және т.б.;

Осындай дизайн оптимизациясы қарапайымдылық, жұмыстылық, мобильдiк және басқа  факторлардың арасындағы “келiсiмдi“ тартады.

Берiлген әртүрлi метриканың салыстырмалы маңыздылығы қолданбалы есептiң табиғатына сәйкес өзгередi. Келесi мысалдарды қарастырамыз.

Мысал 1. Ауа райын болжайтын жүйе

Берiлген жүйенi құруда максимальды орындалу уақытын, аппараттық шығындар және орындау шығындарын, одан басқа берiлген аралықтарда модель дәлдiгiнiң максимальды болуын талап етуi керек. Қосымша сенiмдiлiктiң маңызы аса зор, өйткенi жүйе компьютердiң болашақ буындарына масштабталуы мүмкiн.

Мысал 2. Деректер қорындағы жазуды iздедiң параллель программасы.

Берiлген жағдайдағы минимальды шарт – тек iздестiру бартiзбектi программаларға қарағанда тезiрек орындалуы. Бiрақ тоқтататын фактор есептi орындауға процессор қанша уақыт жiберетiндiгiнде. Мұндағы, универсалдық (масштабтылық) аса қиын шарт емес, бiрақ код деректер қоры жүйесiндегi және компьютерлiк технологиядағы өзгерiстерге оңай бейiмделуi керек.

Мысал 3. Кескiндердi өңдеу.

Кескiндi өңдейтiн конвейер, бiрнеше параллель кезеңдерден тұрады, олардың әрбiреуi кескiндерағынына әртүрлi түрлендiрулердi орындайды. Мұнда, секундыны өңделетiн кескiндер санының маңызы зор (өнiмдiлiк) немесе

конвейерден бiр кескiннiң өтуiне кететiн уақыт (күту уақыты). өнiмдiлiктiң бейне қосымшаларды сығуда да маңызы зор.

Талдап  тексеру дәрежесi ұғымын қарастырайық.

Параллелизм көмегiмен максимальды жылдамдыққа жету ‰шiн берiлген есептi бiруақытта орындауға болатын iшкi есептер мен процесстерге бөлу қажет. Процесстiң өлшемi оның талдап тексеру дәрежесiмен сипатталуы мүмкiн.

Талдап  тексеру дәрежесi (granularity) – синхрондау н‰ктесi немесе байланыс аралығындағы есептеулер өлшемi. Параллелизм сапасы:

• әдемi бөлiну (fine grain);

• орташа бөлiну;

• тұрпайы  бөлiну бар ма соған байланысты.

Осыған  сәйкес, синхрондау нүктелерiнiң аралығындағы командалар саны бiрлiктер ретi, ондықтар және жүздiктерге сәйкес. Келесi ұғым – жылдамдату коэффиценті. Көппроцессорлы жүйелер мен бiрпроцессорлы ж‰йенiң арасындағы салыстырмалы жұмыс өлшемi – бұл S(n) жылдамдатуы, ол былай аықталады:

 

 

 

 

Теориялық анализде жылдамдату коэффициентi есептеулер қадамы терминiнде

келтiрiледi:

Суперсызықтық жылдамдату үшiн көппроцессорлы жүйелерде қосымша жады қажет. Мысалы, бiрпроцессорлы жүйелердегi сияқты көппроцессорлы жүйелерде жедел жады әрбiр процессормен байланысқан деп санайық. Көппроцессорлы жүйелердегi толық жедел жады бiр процессорлы жүйелерге қарағанда үлкен және кез-келген уақытта көп қолданбалы деректердi сақтайды. Бұл салыстырмалы баяу трафике, дискiдегi жадыға алып келедi.

Қосымша шығындар (overhead).

Параллель версияларда  “аса шығын“ пайда болатын бiрнеше фактор туу мүмкiн, және жылдамдатуды шектейдi:

•  барлық процессор бiрден пайдалы жұмысты орындай алмайтын

    период,онда тұрыпқалуы мүмкiн. (Периодқа тек бiр ғана процессор

    есептеудiң ажырамайтын тiзбектi бөлiгiнде активтi);

• тiзбектi версиясында пайда болмайтын параллель версиясындағы қосымша есептеулер, мысалы, тұрақтыларды қайтадан локальды есептеу үшiн
• хабар жiберу үшiн байланыс уақыты.

 

Амдал заңы

Егер  бiз тiзбектi орындалу уақыты 1-ге тең дңп және басқа уақыттарда тiзбектi уақыттың процентiмен өрнектелген жылдамдатуды анықтайтын формуланы нормализацияласақ, бiз

параллель процессорлар үшiн Амдал заңының келесi формулировкасын аламыз (Amdahl, 1967); Теңдеудің бұл түрi есеп теулердегi тiзбектi бөлiке қосылған үлестi айқындайды. Мұндағы

S_p – жылдамдату

 a – параллель орындауға болатын программа бөлiгi

(1-a) – тiзбектi болған программа бөлiгi

Бөлiмi –  программаны параллель орындауға қажеттi уақыт, яғни тiзбектi бөлiке жұмсалған уақыт пен параллель бөлiке жұмсалған уақыттың қосындысы, мұндағы параллелеь бөлiктiң жылдамдату коэффициенттерiнiң функциясы. Егер программаның параллельбөлiгi болып өткен жылдамдатуды шығарады, яғни р коэффициентi (орындалу р процессорда жүредi). Теңдеу түрi:

Тиiмдiлiгi

Бағасы (cost).

Процессорлық  уақыт немесе есептеу уақыты төмендегiдей  анықталуы мүмкiн:

Бағасы = (Орындалу уақыты)x(Іолданылған процессордың жалпы саны).

Тiзбектi есептеудiң  бағасы t_s орындалу уақыты. Параллель есептеу бағасы t_pxn тең. Параллель есептеу уақыты t_sS(n) деп берiлген. Бұл жағдайда параллель есептеулердiң бағасы:

Оптимальды  параллель алгоритмнiң бағасы –  көппроцессорлы жүйеде есептердi шешу бағасының бiрпроцессорлы жүйедегi бағасына пропорционадл.

Масштабтылық.

Бұл терминнiң  бiрнеше анықтамасы бар:

• архитектуралық масштабтылық немесе аппараттық жасау  масштабтылығы;

• алгоритмдiк  масштабтылық.

Архитектуралық масштабтылық немесе аппараттық жасау масштабтылығы аппараттық жасау құрылымы жүйенiң өлшемiнiң ұлғаюына мүмкiндiк беретiнiн көрсетедi.

Алгоритмдiк масштабтылық есептеу құрамының аз және өскен кезiнде де және де деректерге амалдарды өсiргенде де алгоритм тиiмдi болатындығын көрсетедi.

 

 

 

 

4. ЕСЕПТЕУ ЭКСПЕРИМЕНТІ

Есептеу математикасында  есепті шешу уақыты таңдалған шешу әдісі мен алгоритмнің күрделілігіне  тәуелді. Параллель есептеулердегі жеделдетуге баға беруді анықтау  үшін алғашқы кезекте таңдалған  есептеу алгоритміне баға берген жөн, басқаша айтқанда, алгоритмді параллельдеп бөлудің тиімділігін анықтау  және екінші кезекте берілген есептің  шешімін табу үшін таңдалған әдісті бағалау, яғни осы есепті шешуге арналған параллель тәсілдің тиімділігіне баға беру. Осы жұмыста құрылған параллельді  бағдарламаның тиімділігі тексеріліп, баға берілді. Жақсы нәтиже алынып, параллельді бағдарламаның шындығында анағұрлым тиімді екені анықталды. Енді параллельді бағдарламаның  тиімділік көрсеткіштері жайлы  айтамыз. Мынадай белгілер енгізейік: -  бір процеспен есепті орындау уақыты, - тап сол есепті процестермен шешу. Есепті шешу уақыты есептің күрделілігіне, есептің кірме деректерінің санына тәуелді. уақытының уақытына қатынасы болып белгіленетін - шамасы параллель алгоритмнің жеделдетілуі болып табылады, яғни параллельді бағдарламаның есептеу жылдамдығы:

 

.

Іс жүзінде  қолданылатын процестер санына параллель  алгоритмдердің  жеделдетілуіне қатынасы болып белгіленетін шамасы болып табылатын параллель алгоритмнің тиімділігі:

 

.

 

Мынадай белгілер енгізейік: алгоритмнің тізбекті аймағындағы скалярлық амалдар саны, алгоритмнің параллель аймағындағы амалдар саны, алгоритмдегі амалдардың жалпы саны, бір амалды орындалудың орташа уақыты, процестер саны, скалярлық амалдардың салыстырмалы салмағы. Сонда танымал Амдал саны заңы шығады:

.

       Амдал заңына параллель есептеулерге  арналған маңызды ережелер кіреді:

Жеделдету процестердің санына және есептің әлеуетті параллелизміне ( шамасы) тәуелді.

Шекті жеделдету  есептің қасиеттерімен анықталады.

Мысалы, скалярлық  амалдарының салыстырмалы шамасы (іс жүзіндегі шама) болсын делік, сонда қолданылатын процестердің кез келген санында жеделдету . Мұнан келіп, есептің әлеуетті параллелизмді анықталады.

Мінсіз параллелизм  кезінде, басқаша айтқанда, болғанда, жеделдету және тиімділігі .

 

Сурет 7 – Торап саны 1 болған кездегі параллельді бағдарламаның ядролар санына байланысты есептеу жылдамдығының сұлбасы

                  

Сурет 8 –   Торап саны 2 болған кездегі параллельді  бағдарламаның ядролар санына байланысты есептеу жылдамдығының сұлбасы 

 

                 

Сурет 9 –   Торап саны 4 болған кездегі параллельді бағдарламаның ядролар санына байланысты есептеу жылдамдығының сұлбасы

 

 

 

 

                    

 

 

 

 

 

 

 

 

Сурет 10 – MPI технологиялары арқылы алынған параллельді  бағдарламаның  тораптар санына байланысты есептеу жылдамдығының өзгеруі

                             (---- MPI speedup,— ideal speedup )

                                    

 

 

 

 

 

 

 

 

    

 

Сурет 11 – MPI/OpenMP және MPI технологиялары арқылы жазылған параллельді бағдарламаның тораптар санына байланысты есептеу жылдамдығының  өзгеруі

 

 

 

 

 

 

 

 

 

 

 

 

 

Сурет 12 –  Гибридті MPI/OpenMP параллельді бағдарламаның  ядролар санына байланысты есептеу  тиімділігінің өзгеруі