Параллельді есептеуіште жалпы жадтар жүйесін ұйымдастыру

Жұмыс түрі: Дипломдық жұмыс
Тегін: Антиплагиат
Көлемі: 52 бет
Таңдаулыға:

МАЗМҰНЫ

КІРІСПЕ
... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ..
... ... ... ... ... ... ... ... ... .6
1 ПАРАЛЛЕЛЬДІ ЕСЕПТЕУ, ПАРАЛЛЕЛЬДІ КОМПЬЮТЕР ЖӘНЕ АППАРАТТЫҚ
ҚАМТАМАСЫЗДАНДЫРУ ... ... ... ... .. ... ... ... ... ... ... ... ... ... 7

1.1 Параллелизм, параллелизм деректері, есебі және параллелизмді қолдану 7
1.2 Параллельді компьютерлердің классификациясы
... ... ... ... ... ... ... ... ... ...11
1.3 Параллельді компьютерлердің типтері және таксономия жасау тәсілдері
... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ..
... ... ... ... ... ... ... ... ... ... ... ... ... ..20

2 ПАРАЛЛЕЛЬДІ БАҒДАРЛАМАЛАУ
ОРТАСЫ ... ... ... ... ... ... ... . ... ... ... ...27

2.1 Параллельді бағдарламалаудың технологиясы
... ... ... ... ... ... ... ... ... ... ... 27
2.2 OpenMP параллельді бағдарламалау технологиясы және С++ алгоритмдік
тілде қолдану
... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ..
... ... ... ... ... ... .33
2.3 Параллельді бағдарламалаудың бағалану тиімділігі
... ... ... ... ... ... ... ..58

3 OPENMP ПАРАЛЛЕЛИЗМ ҰЙЫМДАСТЫРУДА ҚОЛДАНУ ... ... ... ... 61

3.1 Тізбектелген әдіспен Дирихле есебін шығару
... ... ... ... ... ... ... ... ... ... . .61
3.2 Параллельді есептеуіште жалпы жадтар жүйесін ұйымдастыру ... ... ... 63
3.3 Параллельді есептеуіште таратылған жадтар жүйесін ұйымдастыру ... . 79

ҚОРЫТЫНДЫ
... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ..
... ... ... ... ... ..88

ҚОЛДАНЫЛҒАН ӘДЕБИЕТТЕР
ТІЗІМІ ... ... ... ... ... ... ... . ... ... ... ... ... ... .. 89

КІРІСПЕ

Жұмыстың жалпы сипаттамасы. Бұл жұмыс параллельді есептеу жүйелерін
зерттеуге, дамуын талдауға бағытталған, параллельді бағдарламалау
саласында есептерді шешуге арналған тікелей есептеуішті қолдану мүмкіндігін
алатын параллельді есептеу жүйелері үшін параллеизм, параллелизм
деректерін, параллельді бағдарламалаудың негізгі технологиясы үшін кейбір
математикалық есептердің күрделігінің сипаттамаларын қарастыруға арналған.

Жұмыстың өзектілігі. Бұл қазіргі заманауи параллельді компьюютерлердің
түрлерін және параллельді бағдарламалау тілдерін зерттеу және қарастыру,
сонымен қатар жалпыға бірдей тәжірибелік қолдану үшін программалар кешенін
қалыптау. Оны жүзеге асыру төмендегілерден тұрады:
- қазіргі параллельді есептеуіш жүйелерді, параллельді бағдарламалау
тілдерін, параллельді бағдарлмаларды, параллельді есептеуіш жүйелердің
қазіргі даму күйін анықтаудан, сонымен бірге параллель есептеуіш
жүйелерді анықтау;
- әмбебап және арнайы ЭЕМ классификаицяларының құрылымын зерттеу;
- адамның ЭЕМ- мен әрекетенің бағдарламалық С++ тілінде OpenMP -нің
мүмкіндіктерін параллельді есептеуде, эксперименталды зерттеу және
зерттеу нәтижелерін тәжірибеге енгізу.
Зерттеудің нысаны: OpenMP-ні параллелизм ұйымдастыруда қолдану
тәсілдерін зерттеу.
Зерттеудің пәні: Параллельді есептеуіш пәніне негізделіп, параллельді
қолданудың әдіс тәсілдерін қарастыру.
Зерттеу әдістері. Диплом жұмыста параллелизмнің қолдану аймағымен оның
негізгі ерекшеліктерін қарастыру.
Ғылыми жаңалығы. OpenMP параллелизм ұйымдастыруда қолданудың жаңа
жақтырын қарастыра отырып, параллелизм ұйымдастыруда дифференциалдық
теңдеулерді шешу, оның нәтижесін алу.
Тәжірибелілік құндылығы. Параллельді есептеуіш жүйелер – ол физикалық
компьютерлер, және де көптеген есептеуіш түйіндерде әртүрлі әдістермен
мәліметтерді параллельді өңдеуді жүзеге асыратын бағдарламалық жүйелер.
Есептерді қайта параллельдеу көптеген есептердің бір уақытта шешілуі мүмкін
кіші есептердің жиынтығына негізделеді.
Зерттеу жұмысының жариялылығы. Диплом жұмыс жұмысының нәтижелері ІІІ
халықаралық ғылыми-тәжірибелік Жас ғалым-2009 (ғылыми оқулар)
конференциясының материалдарында, М.Х.Дулати атындағы ТарМУ магистрант,
аспирант, докторанттардың 4 республикалық ғылыми-тәжірибелік
конференциясының материалдарында жарияланды.
Диплом жұмыс құрылымы мен көлемі. Диплом жұмыс кіріспеден, 3 тараудан,
қорытынды, қолданылған әдебиеттер тізімінен, 2 қосымшадан, 29 суреттен және
6 кестеден тұрады.
1 ПАРАЛЛЕЛЬДІ ЕСЕПТЕУ, ПАРАЛЛЕЛЬДІ КОМПЬЮТЕР
ЖӘНЕ АППАРАТТЫҚ ҚАМТАМАСЫЗДАНДЫРУ

1. Параллелизм, параллелизм деректері, параллелизм есебі және
параллелизмді қолдану

Параллельді есептеуіш жүйелер – ол физикалық компьютерлер, және де
көптеген есептеуіш түйіндерде әртүрлі әдістермен мәліметтерді параллельді
өңдеуді жүзеге асыратын бағдарламалық жүйелер. Есептерді қайта параллельдеу
ойы көптеген есептердің бір уақытта шешілуі мүмкін кіші есептердің
жиынтығына негізделеді. Әдетте параллельді есептеулер әрекеттердің
координациясын талап етеді. Параллельді есептеулер бірнеше формаларда бар:
биттер деңгейіндегі параллелизм, нұсқаулықтар негізіндегі параллелизм,
мәліметтердің параллелизмі, есептердің параллелизмі. Параллельді есептеулер
көп жылдар бойы жоғары өнімді есептерде қолданылды, бірақ соңғы кездерде
оларға процессорлардың тактілік жиілігінің көбеюіне физикалық шектеулердің
бар болуынан сұраныс көбейді. Параллельді есептеулер компьютерлер сәулеті
негізінде көпядролы процессорлар формасында доминирлеуші парадигма болды.
Бірнеше әрекеттің бір мезгілде орындалуы үшін жүргізілетін мәліметтерді
параллель өңдеудің екі түрі бар: конвейерлік және параллелизмдік.
Параллельді өңдеу. Егер бір құрылым бір уақыт бірлігінде бір операция
орындаса, онда мың операцияны мың бірлікте орындайды. Егер осындай бір
мезгілде жұмыс жүргізетін бір-біріне тәуелсіз бес құрылым болса, онда
жүйе мың операцияны мың уақыт бірлігінде емес, екі жүз уақыт бірлігінде
орындайды. Осыған ұқсас Ν құрылымды жүйе осындай жұмысты шамамен 1000 Ν
уақыт бірлігінде орындайды,
Конвейерлік өңдеу. Құбылмалы үтір формасында берілген екі заттық
сандарды қосу үшін не қажет? Көптеген операциялар жиынтығы қажет. Алғашқы
компьютерлердің процессорлары мұндай майда операцияларды соңына жеткенше
бірінен соң бірін орындайды, содан соң ғана келесі қосылғыштарды орындауға
көшетін.
Конвейерлік өңдеудің мәні жалпы операцияларды орындаудың жекелеген
кезеңдерін бөлу, әрбір кезең өзіне жүктелген жұмысты орындап болып,
нәтижесін келесі кезеңге береді де, өзі жаңа мәліметтерді қабылдайды.
Мұндай операцияларды біріктіру арқылы өңдеу жылдамдығын арттырамыз.
Мысалы, операцияда бес шағын операцияларды бөлсек, олардың әрқайсысын
орындауға уақыт бірлігі кетеді. Егер бөлінбейтін тізбекті құрылым болса,
онда 100 жұп аргументтерді ол 500 бірлікте орындайды. Егер әрбір шағын
операцияны конвейерлік құрылымның жеке кезеңдеріне бөлсек, онда уақыттың
бесінші бірлігінде алғашқы 5 жұп аргумент болады, әрбір келесі
аргумент–алдыңғыдан бір бірліктен соң келіп тұрады, яғни тізбекті
құрылыммен салыстырғанда жылдамдық бес есе жоғары болады.
Жалпы жағдайда да осыған ұқсас болады. Егер конвейерлік құрылымда
басқышы l болса, онда әрбір басқыш бәр уақыт бірлігінде жұмысқа қосылады,
онда өңдеу уақыты n тәуелсіз операцияларын өңдеу уақыты ,
құрады. Егер құрылымды тізбекті режимде пайдаланса, өңдеу уақыты
құрайды. Нәтижесінде конвейерлік өңдеуді пайдалану есебінен
жылдамдық 1 есе жоғары болады.
Конвейерлік өңдеуді қарапайым параллель өңдеумен ауыстыруға болар
еді. Алайда алынатын жүйе құны мен күрделіліг конвейрелік нұсқасының құны
мен күрделігімен салыстыруға келмейді, ал өнімділігі бірдей деңгейде.
Параллелизм бағдарламаны жазу үшін онда бір мезгілде есептелетін
операциялар тобын анықтау қажет және қандай процессормен, қандай
құрылыммен, конвейердің қандай басқасында орындалғанына байланыссыз
екендігін анықтау керек.
Бұл мүмкіндік бағдарламада нақты ақпараттық тәуелділік бар не
жоқтығымен анықталады. Бағдарламаның екі операциясы бір операцияны орындау
үшін аргумент ретінде екіншісі қолданылса, ақпараттық тәуелділік деп
аталады. Егер операция В А операциясына ақпараттық тәуелділік болса, онда
В операциясы А операциясы орындалған соң ғана орындалады. Бір жағынан,
егер А және В операциялары ақпараттық тәуелді болса, онда алгоритм олардың
орындалу тәртібіне ешқандай шектеу қоя алмайды. Сонымен, бағдарламаны
параллель жүргізу одан тәуелсіз операциялардың санын жеткілікті түрде
табуға әкеледі, оларды есептеу құрылымдары арасында тарату, синхрондылықты
қамтамасыз ету болып табылады.
Ақпараттық тәуелсіздік ұғымын ендіру қарапайым түрде болады, ал
ақпараттық тәуелсіздіктің барлық жиынтығыны зерттеу нақты бағдарламада
күрделі міндет болып табылады. Бірнеше мыңдаған операторлардан тұратын
бағдарламаныны елестету жеткілікті және әрбір циклі көптеген
операциялардан тұрады десек, туындайтын мәселелер күрделене түседі.
Міндеттер мен талдауды оңайлату үшін ақпараттық тәуелсіздік графасы
ұғымын енгізу қажет.
Мұндай графалардағы ең биік тұғыр бағдарламаның кейбір операциялары
танылады, егер екі операция арасында ақпараттық тәуелділік болса, бұл
операцияларға сәйкес келетін биіктер доғамен байланыстырылады, оның
бастапқысы ретінде ақпарат–жеткізуші биіктік, соңы ретінде–ақпарат–тұтынушы
биіктік танылады. Графты зерттеуді оңайлату үшін доға саны аз тұғырлық
граф айқындалады, егер графтың екі биіктігі жолмен байланысса оны
тәуелділіктің ең аз графы деп атайды. Ең аз граф тәуелсіздігінің көмегімен
шешілуі тиіс барлық тапсырмалар шешімін табады. Егер биіктіктерге
бағдарлама операторларының жеке қосылулары сәйкес келсе, мұндай граф
бағдарламаны орындаудың ақпараттық тарихы деп аталады. Ақпараттық тарих
талдау жасалатын бағдарламаның ақпараттық тәуелділігі құрылымы туралы
толық мәлімет береді, сондықтан бағдарламаға талдау жасауда параллельдеу
мақсатымен ақпараттық тарих қолданылады. Алайда талдау жасаудың
күрделілігі мынада, қарапайым жағдайда алынатын графты қолмен құруға және
талдауға болатын болса, ал үлкен нақты бағдарламаларда бағдарламалық
құралдар қажет.
Бағдарламаны орындаудың негізгі құрауыштары орталық процессор, кэш және
жады болып табылады. Біртекті процессордың архитектурасын жақсартудың түрлі
әдістері бар:
1. Жинақтаушының төрт модулін қолдану, орталық процессордың ішкі
бөлімінің біреуінің орнына қосушы;
2. Өткізу жолағын үлкейту үшін екі немесе одан да көп жады блоктарын
орталық процессорге қосу;
3. Бір мезгілде орындалатын командалар санын көбейту үшін екі немесе
бірнеше процессорларды қосу;
4. Барлық компьютерлердің жұмысы бірге бір бағдарламаны шешуге
бағытталуы үшін толық компьютерді қосу.
Параллелизм түрлі деңгейлерге жіктелуі мүмкін:
- тапсырма деңгейінің параллелизмі;
- бағдарлама деңгейінің параллелизмі;
- команда деңгейінің параллелизмі;
- арифметикалық – теңестіру параллелизмі.
Тапсырма деңгейінің параллелизмі – параллелизмдіктің ең жоғарғы
деңгейі. Мысалы, зертханалық немесе компьютерлік орталықта берілген уақыт
кезеңінің тапсырмаларын орындайды. Бұл үлкен компьютерлік жүйелерді сатып
алумен қол жеткізетін нәрсе, сондықтан көптеген тапсырмаларды орындау үшін
қолданушының кез келген тапсырмасы басқаларға қарағанда жылдамырақ
орындалады.
Тапсырма деңгейінің параллелизмділігі бір компьютер деңгейінде де
қолданылады.Орталық процессордың және енгізу-шығару жүйесі арқылы
параллельді жұмыс атқарады.
Параллелизмдіктің берілген түрінің үлгісі – бірнеше тапсырмалар тұрақты
жадында бір уақытта сақталады, тек біреуі кез келген уақытта орындалады.
Егер бұл тапсырма енгізу-шығару типіндегі қызметті керек етсе, онда
операция басталып, тапсырма тоқтатылып, ал басқа тапсырма орындалу
жағдайына орналастырылады. Келесіде енгізу-шығару операциясы аяқталып,
берілген деректерге қол жеткізген соң басқару бастапқы тапсырмаға кері
барып, орындау жалғасады.
Бағдарлама деңгейінің параллелизмі – бағдарлама деңгейінің
параллелизмділігі бір бағдарламаның құрамы бөліктерге бөлінген кезде жүзеге
асады. Мысалы, С=АхВ матрицасының қорытындысы матрицаларды квадраттарға
бөлу жолы арқылы есептелуі мүмкін:
С11 С11 = А11
k t
k t k t S
100 5257 1,39 5257 0,73 1,90
200 23067 23,84 23067 11,00 2,17
300 26961 226,23 26961 29,00 7,80
400 34377 562,94 34377 66,25 8,50
500 56941 1330,39 56941 191,95 6,93
600 114342 3815,36 114342 2247,95 1,70
700 64433 2927,88 64433 1699,19 1,72
800 87099 5467,64 87099 2715,73 1,99
900 286188 22759,38 286188 11776,09 1,93
1000 152657 14258,38 152657 7397,60 1,93
2000 337809 134140,64 337809 70312,45 1,91
3000 655210 247726,69 655210 129728,13 1,91

(k – итерация саны, t – секундтағы уақыт, S – жылдамдығы)

Параллельді ағындардың өзара тәуелділіктерін жоюына арналған
сызбалардың алмасуының жұптарын және тақтар жолдарын (redblack row
alternation scheme) өңдеу, егер итерация торлар әдісімен екі тізбектелген
кезеңге бөлініп орындалады, бірінші жұп жолдарының нөмері өңделеді, одан
кейін екінші кезеңде тақ жолдары нөмері өңделеді (Сурет 3). Берілген
сызбасы бірдзей уақытта айнымалылар және жолдарда жекеленіп және бағаналар
(шахмат түрінде бөлінген) аймағындағы есептеулерде де қорытындылайды.

Сурет 3.6. Алмасудағы жұп және тақ жолдарының өңделу сызбасы

Сызбаны қарасытыра отырып алмасудағы жолдарда Якоби әдісімен
салыстыруды қажет етпейді, кез келген қосымша жадтар және бірдей мағыналы
шешімдерді бағдарламаны қайта жіберуді қамтамасыз етеді. Бірақ қарап
отырсақ, қарастырылған екі деректерде де нәтиже алуға болатын көрдік, бірақ
Дирихле есебінің шешімімен және тізбектелген алгоритмдер көмегіменде сәйкес
келмейді. Бұдан басқа, есептеуіш сызбалар кішігірім аймаққа ие және
жылдамдығы өте нашар, Гаусс-Зейдель әдісінің нұсқауынан шыққан гөрі.
Параллельді есептеуіштің толқын сызбасы
Енді параллельді алгоритмдердің құрылуын қарастырамыз, яғни тек қана
есептелінетін әрекеті бар ғана орындалады және тізбектелген әдіспен және
нәтижесін есептелінетін есептердің негізгі шешімінің алынумен қамтамасыз
етеді.
Жоғарыда атап кеткендей, тізбектелген алгоритм әрбір k кезеңімен
белгісіне жақындайды, соңғы k және белгілеріне жеткенше
есептелінеді және соңғының алдындағы (k-1)-ге және белгілеріне
жақындай түседі. Нәтижесінде, тізбектелген есептеулердің нәтижелеріне
сәйкес келу талабы және параллельді есептеуіштердің сызбасы бастапқы әрбір
итерация әдісімен тек бір ғана қайта есептелуі мүмкін. Одан әрі
қарай, есептелініп болған соң есептеуіш және екі торлар
түйіндерінде орындалуы мүмкін (бұл түйінде тізбектелген сызбалар шарты
орындалады), осыдан кейін және түйіндерінің есептелуі - ,
және түйіндері қайтадан есептелінеді. Жалпы айтқанда,
итерацияның тор әдісімен орындалуы тізбектелген қадамдарды бөлуге болады,
әрбір есептелінгендер дайындалған түйіндері қосымша торлар нөмірінің
диагоналімен болады, бұл кезеңдегі нөмірлерді анықтаған.
Нәтижеде есептеуіш сызбаның толқынына ие боламыз немесе есептеуіш
майданы деп аталады, алынған алгоритмдер негізі – толқын әдісінің
деректерімен өңделеді (wavefront or hyperplane methods).
Атап кететін болсақ, біздің жағдайда толқындар мөлшері динамикалық
есептеулер қадамы өзгереді – толқын өзінің өзінің ұзындығына жеткенше
өседі, ал оң жақ торлар түйіндеріне жақындай түседі.

Кесте 4. Гаусс – Зейдель (p=4) алгоритмнің толқын сызбасындағы
параллельді нұсқау сараптамасының нәтижесі

Торлар Тізбектелген Параллельді Параллельді
мөлшері Гаусс – Зейдельалгоритм 3.5 алгоритм 3.6
әдісі (алгоритм
3.1)
k t k
k t k

k t k t S k t S ... жалғасы

Сіз бұл жұмысты біздің қосымшамыз арқылы толығымен тегін көре аласыз.