Файл қосу
Параллелді есептеуіш жүйелерді құру
|Қазақстан Республикасы білім және ғылым министрлігі |
|Семей қаласының Шәкәрім атындағы мемлекеттік университеті |
|3 деңгейдегі СМК құжаты | |ПОӘК 042.39.1.146/01-2013 |
| |ПОӘК | |
|ПОӘК |01.09.2010 ж | |
|Оқытушыға арналған |№1 басылым | |
|«Паралельді есептеу» пәні |02.09.2013 ж | |
|бойынша оқу жұмыс бағдарламасы |№2 басылым | |
| | | |
| | | |
| | | |
«Паралелдьді есептеу»
пәнін оқыту-әдістемелік кешен
5В060200 - «Информатика» мамандығына арналған
Оқытушыға арналған оқу жұмыс бағдарламасы
Семей,
2013
МАЗМҰНЫ
| |Глоссарий |
| |Дәрістер |
| |Зертханалық жұмыстар |
| |Студенттердің өздік жұмыстарының жоспары |
Кіріспе
Паралелді есептеуіш жүйелерді қолдану (ПЭЖ) есептеу техникасының
дамуының стратегиялық бағыты болып табылады. Бұл жағдай қарапайым
кезектеспелі ЭЕМ-дердің мүмкіндігінше максималды жылдамдығының принципиалды
шектеуімен ғана шақырылмайды, және де әрқашанда есептеуіш тапсырмаларды
шешу үшін есептеуіш технкасының бар мүмкіндіктері көп жағдайда жеткіліксіз
болуымен де шақырылады. Сөйтіп, қазіргі заманғы ғылым мен техника
мүмкіндіктерінің [54] "үлкен шақыру" мәселелері: климотты моделдеу, гендік
инженерия, интехралдық схемаларды жобалау, қоршаған ортаның ластануының
анализі, емдік дәрумендерді жасау және тағы сол сияқтылар - өздерінің
анализі үшін әр секундта қалқымалы үтірі бар (1 TFlops) 1000 миллиард
операцияларды орындайтын ЭЕМ талап етеді.
Жоғарғы дәрежелелі өнімділікті есептеуіш жүйелерді құру мәселесі
қазіргі заманғы ғылым мен техникалық есептердің ең күрделісі болып
табылады. Осы мәселені шешу көптеген талантты ғалымдар мен
конструкторлардың білімдері мен күштерін жан – жақты концентрациялағанда
ғана мүмкін, оның үстіне ғылым мен техниканың соңғы жетістіктерін қолдануды
және маңызды финанстік инвестицияларды талап етеді. Сонымен қатар осы
саладағы соңғы кездегі жетістіктер таңқаларлықтай. "Компьютерлік
белсенділікті стратегиялық шектеу" Accelerated Strategic Computing
Initiative – ASCI) [25] бағдарламасы АҚШ-та 1995ж қабылданған, осының
негізінде суперЭЕМ- дердің өнімділігін 18 айда 3 есе арттыру және өнімділік
дәрежесін секунтына 100 триллион операцияларды орындауға арттыру мәселелері
болды. Қазіргі уақытта жылдам әрекет ететін суперЭЕМ-дердің бірі NEC жапон
фирмасының бір векторлық процесстің жылдамдығы секундтына 8 миллиард (8
GFlops) операциялар орындайтын SX-6 компьютері болып табылады. Көп
процессорлы жүйелер үшін қол жеткізілген жылдам әрекет ету көрсеткіштері
әлде қайда жылдам: мысалға, Intel (США, 1997) фирмасының ASCI Red
жүйесінің жылдамдығы секундтына 1,8 триллион (1,8 TFlops) операциялар. Осы
курстың лекйияларын жазу кезіндегі жылдам әрекет етуші есептеуіш жүйелердің
Top 500 тізімінде BlueGene/L есептеуіш комплексі алғашқы қатарда.
Есептеулерді паралелдендіруді ұйымдастыру бір сәтте мәліметтерді өңдеу
операциялары орындалған кезде функционалды құрылғылардың көптігінен жүзеге
асады. Бұл жағдайда есептеуіш тапсырмаларды шешуді жылжамдата аламыз, ол
үшін қолданылып отырған алгоритмді ақпаратты тәуелсіз аймақтарға бөліп, әр
аймақты есептеуді жеке процесске жазу керек. Осындай тәсілдер керекті
есептеулерге жылдам қол жеткізуге мүмкіндік береді.
Айтып өтетін бір жағдай, паралелдендіруді қолдану ғалымдардың
болжамдарына қарамай әлі де кең қолданыс алған жоқ. Бұл жағдайдың осы күнге
дейін басты себептерінің бірі жылдам өндірістік жүйелердің қымбаттығы болды
(суперЭЕМ ді тек қана үлкен компаниялар мен мекемелер ғана ала алды).
Қазіргі заманғы түрлі конструктивті элементтерден (микропроцессорлар, жады
микросхемалары, комуникациялдық құрылғылар) тұратын паралелді есептеуіш
комплекстерді құрудың көп бөлігі өндіріспен игерілген. Осы жағдай алдыда
айтылған факторды бәсеңдетті, және қазіргі уақытта әр бір қолданушы
өндірістігі өте жоғары көп процессорлы есептеуіш жүйелерін (КПЕЖ) қолдана
алады. Паралелді есептеулер жағдайы көп ядролы процессорлардың пайда
болуымен қарқынды дамыды, 2006 жылы компьютерлік жүйелердің 70% да
қолданды.
Енді, паралелдендірудің таралуына жол бермей отырған басты себепке
көшейік. Праралелді есептеулерді жүргізу үшін ЭЕМ – де есептерді шығарудың
дәстүрлі – қайталанбалы – технологиясын «паралелдендіруіміз» керек.
Сөйтіп, көп процессорлы жүйелердегі сандық әдістер енді паралелді және бір
– біріне, тәуелсіз процесстерде әсер ететін түрге келуі қажет.
Қолданылатын алгоритмдеу тілдері және жүйелік бағдарламалық қамсыздандыру
параллелді бағдарламаларды құруды, синхронды және асинхронды процестерді
болдырмауы керек.
Параллелді есептеу жүйелерін қолданғанда туындайтын келесідей ортақ
мәселелерді айтып өткен жөн [22]:
• Параллелдендіруді ұйымдастыру үшін өнімділікті жоғалту - Минскидің
гипотезіне (Minsky) сәйкесінше, параллелді жүйелерді қолданғандағы
тежелу процесстер санының екілік логарифміне пропорционал (мысалы,
1000 процес болса тежелу 10 тең болады).
Осы айтылған жағдай анықталған алгоритмдерді параллелдеген кезде
дұрыс. Сонымен қатар көптеген есептерді параллелдеген кезде параллелді
есептеу жүйелерінің барлық процессетерін қолдану керек болады.
• Кезектеспелі есептеулердің бар болуы - Амбала заңына сәйкес есептеу
процестерін жылдамдату кезінде р процессерін қолданса ол үлкендікпен
шектеледі
[pic]
Мұндағы f мәліметтерді өңдеу алгоритімінде қолданылатын кезектеспелі
есептеулер аймағы. (ол дегеніміз, мысалға 10% кезектеспелі командалар бар
болса, онда параллелдендіруді қолданғанда мәліметтерді өңдеу жылдамдығы 10
еседен аса алмайды).
Айтылған жағдай параллелді бағдарламалаудағы ең күрделі мәселені
сипаттайды (кезектеспелі командалар бөлігі жоқ алгаритмдер болмайды).
Алайда кезектеспелі іс әрекеттер үшін есепті параллелді шешу мүмкіндігі
сипаттамайды, ал қолданылатын алгоритмдердің кезектеспелі қасиеттерді
сипаттайды. Нәтижесінде, кезектеспелі есептеулер бөлімі параллелдендіруге
қолайлы алгоритімдерді қолданғанда әлде қайда азаюы мүмкін.
Параллелді жүйелерге тән қасиеттерге параллелдендірудің эффективтілігі
байланысты – кезектеспелі ЕЭМ – нің класикалық Фон Нейман схемасының
бүтіндігіне қарағанда, параллелді жүйелер архитектуралық құрылу
принциптерімен ерекшеленеді, және параллелденудің максималды эффектілі
болуы құралдардың барлық ерекшеліктерін қолданғанда ғана жүзеге асады;
Нәтижесінде, параллелді алгориьімдерді көшіру және бағдарламаларды әр түрлі
жүйелер арасында тасымалдау қиынға соғады немесе кей жағдайда мүлде мүмкін
емес.
Осы айтылған ескертуге айтып өту керек жағдай, кезектеспелі ЭЕМ – нің
«біртектілігі» елес деуге де болады, себебі біртекті компьютерлерді
эффектілі қолдану үшін оның аппаратураның қасиеттеін ескеру керек. Бір
жағынан, параллелді жүйелердің архитектурасының әр түрлілігіне қармай,
параллелдендіруді қамтамаыз тетін «тұрақтанған» тәсілдер бар (конвейерлі
есептеулер, көп процессорлы жүйе және т.с.с.) Және де, параллелді
есептелерді қолдайтын түрлі бағдарламалық тәсілдерді қолданған кезде
құрылаын параллелді бағдарламалар инвариатты болады. (MPI, PVM және т.б.
бағдарламалық кітапханалар).
• Бар бағдарламалық жасақтмалар кезектеспелі ЭЕМ – дерге бағытталған –
бұл дегеніміз, ептердің көп бөлігіне алдын ала дайындалған
бағдарламалық жасақтама бар және бұл бағдарламалар кезектеспелі ЭЕМ –
дерге бағытталған. Осының нәтижесінде, бұндай мөлшердегі
бағдарламаларды өңдеу параллелді жүйелерге мүмкін болмайды.
Осы айтылған ойға жауап өте қарапайым: егер бар бағдарламалар қойылған
есептерді шеше алса, онда бұл бағдарламаларды өңдеудің қажеттелігі жоқ.
Алайда, кезектеспелі бағдарламалар тиесілі уақыттың ішінде есептердің
шешімін алуды қамтамасыз ете алмаса немесе жаңа есептерді шешу керек болса,
онда жаңа бағдарламалық кешен жасауға тура келеді және бұл бағдарламалар
параллелді есептеуді де жүргізе алады.
Осы айтылған мәселерді қортындылай келе, параллелді есептеу есептеуіш
техникасын қолданудың өте қолайлы (қызықты) саласы және күрделі ғылыми –
техникалық сала болып табылады. Осыған орай, параллелендіруге жету үшін ЭЕМ
– нің және аппарттық құралдардың қазіргі заманға сай даму қарқынын білу,
моделдерді құра алу, мәліметтерді өңдеу тапырмалаларын параллелді шеше алу
қолданбалы математика, информатика және септеуіш техникасы салаларының
мамандарының жоғарғы квалификациялығының көрсеткіші болып табылады.
2.1. Бөлім Параллелді есептеуіш жүйелерді құру
Глоссарий (анықтама, создік);
- MFlops - million of floating point operations per second – қалқымалы
үтірі бар сандардың секундтына миллион операциялары , GFlops -
миллиард, сәйксінше TFlops - триллион.
- ARPANET – компютерлік желіні құру компьютерлік комуникацияда
эксперементтерді жасауға, ядролық шабуыл кезінде байланыста болу,
орталықтандырылмаған басқару концепцияларын басқаруға мақсатталаған
АҚШ-тың қорғаныс Министерлігінің дамыған зерттеу проектілер
агенттігінің проектісі (Defense Advanced Research Projects Agency,
DARPA), (1966-1969 ж.)
Тақырып 1. Параллелді есептеуіш жүйелердің құрылу принциптері:
Дәріс мақсаты: параллелді есептеуіш жүйелердің құрылу принциптерін
қарастыру (ПЕЖ), параллеледіруге жетудің тәсілдеріне қысқаша сипаттама
беру, ПЕЖ – ге мысалдар келтіру . Параллелді есептеуіш жүйелердің
классификациясын, ПЕЖ – де желі арқылы ақпаратты беру типтерінің
топологиясын қарастыру.
Тақрыпқа қойылатын сұрақтар:
1. Параллелендіруге жету тәсілдерінің мақсаты неде?
2. Параллелді есептеуіш жүйелердің ерекшеліктері неде тұрады?
3. Флинн класификасының негізіне не қаланды?
4. Көп процессорлы жүйелердің мультикомпьютер және мультипроцессор бөліну
принципы неден тұрады?
5. Мультипроцессорлер үшін жүйелердің қандай класстары белгілі?
6. Мультипроцессорлердің артықшылығы мен кемшіліге неде?
7. мультикомпьютерлер үшін жүйелердің қандай класстары белгілі?
8. Кластерлі жүйелердің артықшылығы мен кемшілігі неде?
9. Микропроцессерлі жүйелерді құру кезінде ақпаратты беру жүйелерінің
қандай попологиялары кең қолданыс алады?
10. Класстерлер үшін ақпаратты беру жүйелерінің қандай ерекшеліктері бар?
11. Ақпаратты беру жүйелерінің басты сипаттамалары қандай?
12. Кластерлерді құру үшін қандай жүйелік платформалар қолданылады?
Тақырыптың қысқаша мазмұны (тезисі):
Дәрісте параллелді есптеулерді құрудың жалпы сипаттамасы, бағдарламаны
жүргізудің көп есептік, параллелді және бөлінген режимдері айтылған.
Жақындаудың мүмкін болатын тәсілдерін көрсету үшін параллелді есептеу
жүйелеріне бірқатар мысалдар қарастырылады және параллелді жүйелерді
құрудың әр түрлі тәсілдері көрсетіледі.
Көптүрлі компьютерлік есептеу жүйелері классификациялық қажеттілікті
қамтиды. Лекцияда белгілі бір тәсіл сипатталады – Флин систематикасы,
негізінде ағын командасы мен мәліметтер қойылған. Берілген классификация
қарапайым және түсінікті, бірақ та MIMD класы – на барлық көппроцессорлы
есептеу жүйелері кіреді. Лекция жүйелер типінің мақсатына көппроцессорлы
есептеу жүйелерінің құрылым кластары кіреді, екі маңызды белгіленген жүйені
көрсетеді, жалпы бөлінетін және бөлінген жад – мультипроцессорлар және
мультикомпьютерлер. Бірінші группадағы жүйегі маңызды мысал — векторлы
параллельді процессорлар (parallel vector processor немесе PVP) және
симметриялы мультипроцессорлар (symmetric multiprocessor немесе SMP).
Мультикомпьютерге массив - параллелді жүйелер (massively parallel
processor немесе MPP) және кластерлер (clusters) жатады.
Ары қарай лекцияда көппроцессорлы есептеу жүйелерінің мінездемесі
қарастырылады. Топология желісіне де мысал келтіріледі , мәліметтер
желісін беру, кластерлердің ерекшелігін бағалайды және топология
параметрін талқылайды.
Лекцияның соңында кластерлерді тұрғызу үшін жалпы мінездеме беріледі
Өзін - өзі бақылау сұрақтары:
1. Параллелды есептеу жүйелеріне қосымша мысал келтіріңдер.
2. Компьютерлік жүйенің классификациясына қосымша тәсіл қарастырыңдар.
3. Жалпы бөлінетін жадтың қамтамасыз ету когерентті кэшінің амалдарын
қарастырыңдар.
4. Бағдарламалық библиотекаға шолу, бөлінген жад жүйесі үшін,
мәліметтерді беру операциясын орындауды қамтамасыз ету.
5. екілік ағаш түрінде мәліметтерді беру желі топологиясын қарастыру.
6. мәліметтерді беру желісі бойынша, әрбір топологи я типі үшін, нақты
класстар эффектісін ерекшелеңіз.
Әдебиеттер:
Архитектура туралы қосымша ақпарат параллелды есептеу жүйесінен,
мысалы, из [2, 11, 14, 28, 45, 59]; сонымен қатар пайдалы ақпарат та болады
[24, 76].
Көппроцессорлы жүйеде мәліметтерді беру желісне шолу топологиясы және
олардың орындалуына арналған технологиялар ұсынылған, мысалы, жұмыс [29].
Кластерлік есептеу жүйелерінің тұрғызылуы және қолданылуына
байланысты, толығырық сұрақтар қаралған. Практикалық кепілдемеден
кластерлерді құру, әр түрлі жүйелік платформаларда табылуы мүмкін.
2.2. Эффектілі параллельды есептеу сараптама бөлімі.
Тақырып 2. Моделдеу және параллелды есептеу сараптамасы
Лекция мақсаты: есептеу моделін графа түрінде сипаттау "операциялар –
операндылар". Параллелды әдістердің сапа негізін көрсету — үдеткіш
(speedup), тиімділілік (efficiency), құны (cost) және құнын (scalability)
есептеу.
Тақырып сұрақтары:
1. "операцилар — операндылар" моделі қалай анықталады?
2. Бөлінген есептеулер мен процессор арасында кесте қалай анықталады?
3. Параллелды алгоритмнің орындалу уақыты қалай анықталады?
4. Қандай кесте оптималды болады?
5. Ең аз мүмкін уақыт шешімін қалай анықтауға болады?
6. паракомпьютер түсініледі және осы берілген ұғым пайдалы ма?
7. Қандай бағалаулар уақыттың мінездеме ретінде пайдалануын жүйелі
шешімдер ретінде көрсетеді?
8. Графа "операндылар – операцияларды" аз мүмкін уақытта параллелді шешу
қалай анықталады?
9. Қандай тәуелділіктер параллельді шешу уақыттары үшін азаюы немесе
көбею сандары қолданылады?
10. Қай процессор санында параллельді алгоритмнің орындалған уақытын және
салыстырмалы ретімен аз уақытта бағалауды алады?
11. Тиімділілік пен үдеткіштік ұғымы қалай анықталады?
12. Жоғары сызықты үдеткіштің жетістігі мүмкін бе?
13. Үдеткіш пен тиімділіктің қарама - қайшылығын көрсету неден тұрады?
14. Құнын есептеу ұғымы қалай анықталады?
15. Баға - ұтымды алгоритм ұғымы неден тұрады?
16. Тізбекті алгоритмнің сандық мағынасын есептеу қалай жүргізіледі?
17. Каскадты схеманы есептеу неден тұрады? Берілген схеманың
модификацияланған нұсқасы не мақсатпен қаралады?
18. Тиімділік пен үдеткіштің ерекшелігін көрсету үшін, каскадты схеманы
есептеу нұсқасы не үшін қарастырылады?
19. Параллелды алгоритмді есептеудің барлық жүйелі сандар маңызы неден
тұрады?
20. Амдаля заңы қалай формуланады? Берілген заңды параллелды есептеу қай
аспектіде көрсетіледі?
21. Густавсон – Барсис заңын дәлелдеудің қандай мүмкіндіктері бар?
22. изоэффектілік функция қалай анықталады?
23. Қандай алгоритм масштабтау болып табылады ? масштабтауға әртүрлі
деңгейде мысал келтіріңдер.
Тақырыптың қысқаша мазмұны (тезисі):
Лекцияда моделды есептеу, графа "операцилар – операндылар" түрінде
қаралады, алгоритмдік есептерді шешуде ақпараттық алгоритмді шешу жүйелері
таңдалады.
Негізінде осы моделге аэратор хабардар графы қойылған, операцияның
басында немесе шыңында көрсетілген , ал доғалар тап осы операцияға
тәуелді. Осы графқа параллелді алгоритмді анықтау үшін кесте құрады.
Теоретикалық бағаларды қарапайым тұрғызу лекцияда паракомпьютер ұғымы
параллелды жүйенің ұқсас емес процессорлар ұғымы қарастырылады.
Лекцияда бағалар үшін оптималды әдістерді жетілдіру, параллелды
есептеу теория мен практикада көп қолданылатын негізгі сапасы – үдеткіш
(speedup), көрсетілгендей, қанша рет жүзеге асырылса да, бірнеше
процессорды қолдану арқылы есепті шешуге болады және тиімділік
(efficiency), есептеуіш жүйенің процессорларын қолданылуы сипатталынады.
Маңызды жетілдіру сипаттама алгоритмі болып құнын (cost) есептеу табылады.
Демонстрация үшін лекцияда моделдер мен әдістер анализін және
жүйелілік сан мағынасының тапсырмалар жиынтығы жиі параллельды
алгоритмдік лекцияда қаралады. Берілген мысалда қиындатылған алгоритм
мәселесі анықталады, бастапқыда параллельды есептеу бағыты көрсетілмеді.
Анықтау үшін "жасырын" өзгертілген жүйелілік схемалар есептеу
параллелограмы көрсетілуі мүмкін және нәтижесінде осы өзгертілген каскадты
схема пайда болады. Мысалда орындалатын есеп – қисаптардың үлкен
жетістікке жетуіне арналған, артық есептеулердің мүмкіншілігі белгіленеді.
Лекция соңында нәтижелілік көрсеткіштердің барынша қол жетерлік
мағыналарды бағалауларды құру сұрағы қаралады. Осы бағалауларды алу үшін
Амдала заңын қолдануға болады. Густавсон – Барсис заңы (Gustafson –
Barsis's law) бағалаулардың үдеткіш масштабын қамтамасыздандырады (scaled
speedup).
Тәуелділікті анықтау үшін күрделі есептерді шешу арасында және
процессорларды, параллельды есептеулердің тиімділік деңгейін қолдану,
изоэффективности функции (isoefficiency function) ұғымын енгізеді.
Өздік бақылауға арналған тапсырма:
1. үлгіні өңдеңіздер және параллельды есептеу тиімділігін және
үдеткіш бағалауын орындаңыз:
• Екі вектордың скалярлық туындысын табыңыз
[pic]
• Берілген терімге арналған көп және аз мағыналар санын іздеу
[pic]
• Берілген терімге арналған орта мағыналар санын табыңыз
[pic]
2. 1.тапсырмасы үшін көп қол жетерлік үдеткіш бағалауын Амдала заңына
сәйкес орындаңы.
3. 1.тапсырмасы үшін үдеткіш масштабтау бағалауын орындаңыз.
4. 1.тапсырмасы үшін изоэффектілі функцияны тұрғызыңыз.
5. Үлгіні өңдеп және параллельды есептеу тиімділігіне толық сараптама
жасаңыз (үдеткіш, тиімділік, көп қол жетерлік үдеткіш , үдеткіш
масштабтау, изоэффектілі функция) векторға матрицаны көбейту үшін арналған.
Әдебиеттер:
Параллельды есептеуде үлгілеу мен анализге қосымша ақпарат алынады,
мысалы, [2, 22], қажетті ақпарат осылай беріледі [51, 63].
Сандық мағыналарды жүйелілік қосу [22] оқулықта қаралады.
Алғаш рет Амдала заңы [18] жұмыста баяндалды. Густавсона – Барсиса
заңы [43] жұмыста жарияланды. Изоэффектілі функция ұғымы [39] жұмыста
ұсынылды.
Жүйелі баяндау (жұмыс кезінде ) үлгілеу сұрақтары және параллельды
есептеу [77] талдауына тура келеді.
3 Тақырып. Параллелдік алгаритімнің еңбек сіңіргіштіктік бағасы
Лекцияның мақсаты: Параллелді алгаритмді орындау кезінде ақпараттық
топтың анализ сұрағын жарықтандыру. Мәліметтерді жіберу механизіміне
жалпылама мінездеме беру, басты жүйедегі ақпаратты ауыстыруға еңбек
сіңіргіштік анализін жүргізу, көппроцессорды шығару жүйесінің құрылымын
логикалық әдісті ұсынуда қарастыру
Тақырыпқа сұрақ:
1. Қандай басты мінездемелер мәліметтерді жүйе арқылы жіберудің
топологиясын бағалауда қолданылады? (толық граф,сызғыш,тор және тағы
басқалар.).
2. Қандай басты әдістер мәліметтерді желі арқылы жіберуде қолданылады?
3. Мәліметтерді жіберуде басты әдіс неде түзеледі?Бұл әдістерді орындау
уақытында аналитикалық баға келтіріңіз.
4. Мәліметтерді жіберу кезінде қандай операция басты болып табылады?
5. Мәліметтерді бір процессордан жүйе арқылы барлық процессорға сақина
топологиясына жіберуде тор мен гиперкубтың алгоритмдері неден
түзеледі? Осы алгоротимдерге уақытша еңбексіңіргіштік бағасын
келтіріңіз.
6. Мәліметтерді барлық процессордан жүйе арқылы барлық процессорға сақина
топологиясына жіберуде тор мен гиперкубтың алгоритмдері неден
түзеледі? Осы алгоротимдерге уақытша еңбексіңіргіштік бағасын
келтіріңіз.
7. Редукция операциясын орындауда мүмкін алгоритмдер неден түзіледі?
Уақыт өте келе орындалатын алгоритмдердің қайсысы жақсы?
8. Циклдік операция жылжуының орындалу алгоритімі неде түзіледі?
Логикалық топологияны қолдану маңыздылығы неден тұрады? Коммуникациялық
жүйе құрылымының логикалық алгоритімін ұсынуға мысал келтіріңіз.
9. Мәліметтерді тапсыру операцияларының орындалу уақыттарының бағалауына
арналған үлгілердің ерекшелігі неде түзіледі кластерлі есептеуіш
жүйелерде ме? Қай модель нақтығырақ болып табылады? Қандай үлгі алдын-
ала коммуникациялы операциялардың еңбек сіңіргіштігін уақытша талдау
үшін қолданылады?
Тақырыптың қысқаша мазмұны (тезис):
Берілген лекция параллелдік алгаритмнің қиын коммуникациялық бағасына
арналған.
3.1 бөлімде мәліметтерді жіберу әдісінің және алгоритм жолының толық
мінездемесі ұсынылған. Толық көруге хабарларды жіберу әдісі және пакетерді
жіберу әдісі ерекшеленген, олар үщін коммуникациялық операцияны баға
уақытымен орындау анықталған.
3.2 бөліменде параллелді есептеулер жүруде орындалатын, операцияның
басты тобындағы мәліметтерді жіберу анықталған. Басты коммуникациялық
операцияға жататындар:
• Процессорлық жүйе арасындағы мәліметтерді жіберу;
• бір процессордан басқа барлық процессорға жүйе арқылы мәліметтерді
жіберу және барлық процессорлық жүйеден бір хабарлама процессорына
оған екі жақты операция қабылдау;
• барлық процессордан барлық жүйе процессорынамәліметтерді жіберу және
барлық процессорлық жүйеден барлық;
• толықтай1) мәліметтерді бір процессордан барлық қалған жүйелік
процессорға жіберу және керісінше операция бір процессордан қалған
барлық жүйедегі процессорға толықтай қабылдау;
• барлық процессордан барлық жүйедегі процессорға мәліметтерді жіберу;
Мәліметтерді жіберудегі аталған барлық операцияларға топологиялық
сақина мысалында орындалған тор және гиперкуб алгоритмі қарастырылған.
Ұсынылған әрбір алгоритмге уақыттық еңбексіңіргіштік алгоритмінің
хабарламаны жіберудегі әдісі сияқты бағасы келтірілген, сондай-ақ
пакеттерді жіберудегі әдісі орындалады..
3.3 бөлімінде нақты процессорлар арасындағы құрылым негізінде
топологиялардың қисынды ұсыну әдістері қарастырылған. Логикалық топологияны
қолдану, тапсыру алгоритмдердің қатарына арналған қарапайым баяндама алуға
мүмкіндік береді, реализациялық коммуникациялық операцияға тыйымды
төмендетеді.
3.4 бөлімінде модельдер нақтығырақ талқыланады, кластерлі есептеуіш
жүйеге мәліметтерді тапсырудың операциясы баға уақытының көмегі бойынша
орындалады. Нақты қалыптастырылғандардың уақыт бағасы есептеуіш
тәжірибиесін жургізу көмегімен салыстырылады. Тәжірибие нәтижесінде ең
нақты модель анықталды (B моделі). Сонымен қатар уақытша алдын-ала
еңбексіңіргіштік коммуникациялық мақсатқа лайықты қарапайым модель-модель С
(модель Хокни) қолдану.
Өздік жұмыс:
1. Бірқалыпты тордың 3-түріндегі жүйе топологиясына арналған мәліметтерді
тапсыру негізгі операцияларының орындалу алгоримдерін өңдеңіздер.
2. Екілік ағаш түрінде топологиялық жүйемен мәліметтерді жіберудегі басты
операцияларды орындау алгоритмін өңдеңіз.
3. 3.4 бөліміндегі мәліметтерді жіберуде уақытша бағалауға арналған
операциялардың В моделін қолданыңыз. Алынған көрсеткішті салыстырыңыз.
4. 3.4 бөліміндегі мәліметтерді жіберуде уақытша бағалауға арналған
операциялардың С моделін қолданыңыз. Алынған көрсеткішті салыстырыңыз.
5. Әртүрлі физикалық топологияларына арналған екілік ағаш қисынды ұсынулы
алгоритмдарды өңдеңіз.
Әдебиеттер:
Берілген лекцияға қосымша оқулық материалдардың [51, 63] жұмыстары
ұсынылған.
Коммуникациялы операциялардың орындалу уақыттарының бағалауына
арналған үлгілердің құру сұрақтары әдебиетте кең талқыланады. Лекцияны оқу
барысында [5, 28, 68] жұмыстар тиімді болады. Хокни Моделі бірінші рет [46]
жариаланған. 3.4 бөліміндегі B моделі [3] жұмысында көрсетілген.
2.3. Бөлімі Паралелді алгоритмдердің өңделуінің жалпы принціпін құру
4 Тақырып. Паралелді әдістерінің өңделу приціпі
Лекцияның мақсаты: Паралелді алгоритмнің өңделуінде базалық принціпін
қарастыру. Негізгі түсінікті түсіндіру, жасау кезеңдері барлық паралельді
алгоритмдердің талдауын толық реттейді. Талқыланған әдіске мысал келтіру.
Тақырыпқа сұрақ:
1. Лекцияда қаралған қолдану мүмкіншілігіне арналған негізгі жорамалдары
неде түзіледі паралельді алгоритмдердің өңделу әдістерінде ме?
2. Жобалаудың қандай негізгі кезеңдері және есептеулердің паралельді
әдістерінің өңдеулері ме?
3. “аныталған-хабарлама” үлгісі қалай анықталады?
4. " каналы –процессі" моделі қалай анықталады?
5. Паралельді алгоритмді өңдеу кезінде қандай басты талаптар қамтамасыз
етіледі?
6. Белгіленген есеп кезінде негізгі әрекеттер неде түзеді?
7. Ақпараттық тәуелділікті анықтау кезеңінде басты әрекет не?
8. Есептеу бар болатын терімі масштабтау кезінде негізгі әрекет неде
түзіледі?
9. Есептеуіш жүйе процессорымен есептеу таратулары кезеңінде негізгі
әрекеттері неде түзіледі?
Қалай сызба көмегі жанында есептеуіш жүкті тиеу таратуымен " менежер
орындаушысы” динамикалық басқару болады?
Паралельді есептеудің қай әдісі денелердің гравитациялық N тел мақсаттары
үшін шешім өңделген бола ма?
10. Талдап қорытылған мәліметтерді жинау операциясының орындалуының қай
тәсілі нәтижелі болып келеді?
Тақырыпқа (тезис) қысқаша мазмұндама:
Лекцияда [32] ұсынылған паралельді өңдеу әдісі қарастырылды. Ол өзіне мына
кезеңдерді қосады есепті ерекшелеу, ақпараттық тәуелділікті анықтау,
масштабтау және есептеуіш жүйесі есепті процессор бойынша орналастыру.
Әдістемені қолдануда болжалған, есептеуіш сызбасының шешімі қаралған есеп
белгілі болады
Негізгі талаптың, паралельді алгоритмдердің өңделуі жанында тиісті
қамтамасыздандырылған болу, процесордың төменгі ақпараттық әрекеттестікке
есептің ұйымдасқан жиындары біркелкі тиуі.
Паралельді есептеу сызбасын өңдеде екі модель қаралған. Олардың
біріншісі–"ақпараттық–есептеу" паралельді алгоритмнің жобасын құруда
қарастырылады, екінші модель—" канал–процесі" паралельді бағдарламалар
түрінде мүмкін әдістердің орындау сатыларына қолданылған.
Денелердің N тел гравитация мақсаттары бөлім аяқталуына шешім
үлгісінде паралельді алгоритмдердің өңдеу қаралған әдістеме қолдануы
көрінеді
Өздік жұмыс:
1. Әдісті жобалау және паралельді әдісті өңдеу бөлімінде
қарастырылған паралельді есептеу сызбасын өңдеңіз:
• Матрицада жолында минималды элемент арасында максималды мәнді іздеу
[pic]
(жағдайға ерекше назар ықылас білдіріңіз, процесордың саны p>N
шамадан қашан асатындығына);
• Тікбұрыштардың әдісін қолданумен айқын интегралды есептеу
[pic]
(интегралдау әдісі [47] мысалында берілген).
2. векторға матрица көбейтулері мақсатқа арналған паралельді
есептеулердің схемасын өңдеңіздер, жобалау әдәістемесінің бөлімінде
паралельді әдістемелерінің өңдеулері қаралған.
Әдебиеттер:
Қарастырылған лекцияда паралельді алгоритмдардың өңдеу әдістемесі алғашқы
рет [32] ұсынылған болатын. Сонымен қатар бұл жұмыста әдістеме баяндауы
өткізіледі, оған есептеуіш мақсаттардың қатар шешіміне арналған паралельді
әдістердің өңдеуіне арналған оның қолдануының бірнеше үлгісі болады.
Жобалауды қарастырғанда пайдалы әдістеме баяндауы жобалау
сұрақтарының қарауы жанында және сонвмен қатар паралельді алгоритмдардың
өңдеулері [63] бола алады.
Денелердің N тел гравитация мақсаты [5] толық қарастырылады.
2.4. Бөлімінде Құру және есептеуіш паралельді жүйеге бағдарламалық
жүйе дамуы қамтамасыз етілген
5 тақырып. MPI негізінде паралельді бағдарламалау
Лекцияның мақсаты: MPI жадымен таратылған жүйелерде бағдарламалауға
арналған стандартты қарап шығу. Стандарт дамуына тарихи шолу беру, сонымен
қатар оның негізгі мүмкіншілігін санап шығу. Қарастырылған стандартты
жүйелеп бағдарламаға мысал келтіру
Тақырыпқа сұрақ:
1. Қандай минималды терім паралельді есептеу ұйымына таратылған жадпен
жүйені есептеу жеткілікті болып табылады?
2. Хабарлаулардың тапсыру құралдарының стандарттау маңыздылығы неде
түзіледі?
3. Паралельді бағдарламалауда нені түсіну керек?
4. Процесс пен процессор мағанасының айырмашылығы неде?
5. Қандай минималды MPI теру функциясы паралельді бағдарламалауды өңдеуді
бастауға мүмкіндік береді?
6. Жіберілетін хабарлама қалай жазылады?
7. Как можно организовать прием сообщений от конкретных процессов?
8. MPI-бағдарламасының орындалу уақытын қалай анықтайды?
9. Мәліметті жіберуде қос және ұжым операцияларының ерекшілігі неде?
10. Қандай MPI функциясы мәліметтерді бір процестен барлық процеске
жіберуді қамтамасыз етеді?
11. Редукция операциясынан нені түсінуге болады?
12. Қандай жағдайдаларда синхронды тосқауылды қолдануға болады?
13. Қандай мәліметтерді жіберу тәртібі MPI сүйенеді?
14. Мәліметтерді MPI ауыстыру қалай қорғалмайтындай (неблокирующий)
ұйымдастырылады?
15. Тұйық (тупик) ұғымы неде түзіледі? Бір уақытта орындалу функциясын
тапсыру және қабылдаудың тұйық жағдайлары жоқ болу кепілі қашан
болады?
16. Қандай топтық операция мәліметтерді MPI жіберілуінде қарастырылған?
17. MPI үлгісіндегі туындыда не түсіндіріледі?
18. MPI үлгілерінің құрастырылуының қандай түрлері болады?
19. Қандай жағдайларда мәліметтерді топтау (упаковка) және шашу
(распаковка) тиімді болып табылады?
20. MPI комуникаторының астында не түсіндіріледі?
21. Жаңа комуникаторды құру не үшін қажет?
22. Виртуалды топология астында MPI не болып түсіндіріледі?
23. Топологияның қай түрі MPI қарастырылған?
24. Виртуалды топологины қолдану не үшін тиімді болып табылады?
25. Паралельді бағдарламаны MPI қолданып өңдеу мен Fortran алгоритмдік
тілін қолданудың ерекшеліктері неде?
26. MPI-2 стандартында тағы да қандай қасымша мүмкіндіктер қарастырылған?
Тақырыпқа (тезис) қысқаша мазмұндама:
Берілген лекция паралельді бағдарламалау әдісін MPI қолданып
таратылған жадпен есептеу жүйесін қарастыруға арналған. Өзі термині
білдіреді , бір жағынан , стандарт , хабарлаулардың тапсыру ұйымдары
құралдар тиісті қанағаттандыру , ал басқа жағынан , бағдарламалық
кітапханалар белгілейді , хабарлаулардың тапсыру мүмкіншілігін
қамсыздандырады және MPI . стандарты талаптарына мыналар жанында бәріне
талапқа сай болады
Лекцияның басында манау анықталған, MPI –хабарламаны жіберу
интерфейсі (message passing interface)- жадпен таратылған есептеуіш
жүйелерге арналған паралельді бағдарламалардың өңдеуіне осы сәтте негізгісі
болып табылады. MPI қолдану есептеуіш жүйесін анықтауға мүмкіндік береді
және процесорлар арасындағы (мәліметтерді жіберу) ақпараттық әрекеттестікті
ұйымдастырады. MPI термині мынаны білдіреді, бір жағынан, стандарт,
хабарлаулардың құралдарын тапсыру ұйымдарын тиісті қанағаттандару, ал басқа
жағынан, бағдарламалық кітапхана белгілейді, хабарлаулардың тапсыру
мүмкіншілігін қамсыздандырады және MPI стандарты талаптарына мыналар
жанында бәрі талапқа сай келеді.
5.1 бөлімінде MPI стандарты үшін негіз болатын, қатар ұғымдары және
анықтамалары қарастырылған. Көбінде бір уақытта орындалатын процестерге
паралельді бағдарламаға> ұғымы беріледі. Сонымен қатар процесс әртүрлі
процесорда орындала алады, біріқ бір процесорда бірнеше процесс орналаса
алады(олардың атқарылуы уақыттардың бөліну тәртібінде жүзеге асады).
Кейінірек хабарламаны жіберу операциясына қысқаша міездеме беріледі,
мәлімет түрі, комуникатор және виртуалды топологияға..
5.2 бөлімінде MPI қолданып паралельді бағдарламаны өңдеу жылдам және
ақырын өткізіледі. Баяндалатын материал бөлімшесінде әр түрлі қиын деңгейлі
паралельді бағдарламаларының өңдеу басына арналғаны жеткілікті.
5.3 бөлімінде мәліметтерді жіберу операциясын екі процес арасында
байланыстыру. Осында орындалу тәртіптері бар болатын толық даярлықтардың
сипаттамалаы- стандарты, синхроны, буферленген. Барлық қаралған операция
артынан аралық процестермен ұйымдар-айырбастар мүмкіншілігі талқыланады.
5.4 бөлімінде мәліметтерді топтық жіберу операциясы қарастырылған.
Материал баяндауы 3 тақырыпта қолданылған комуникациялы операциялардың
зерттеу жүйелерінің талаптарына сай болады. Берілген бөлімшеде негізгі
шығару мынада, MPI процесс арасындағы барлық негізгі операцияны ақпараттық
ауыстыруды қамтамасыз етеді.
5.5 бөлімінде MPI мәліметтердің еркін типтерінде қолданумен байланысты
материал берілген. Бөлімде еркін типтерді құрастырудың барлық негізгі –
үзіліссіз, векторлық, индекстік және құрылымдық әдістері көрсетілген.
Сонымен қатар мәліметтердің топтау және таратудың көмегімен күрдел
хабарламаларды жүйелеу мүмкіндігі қарастырылады.
5.6 бөлімшесінде топтарды басқару процессі мен коммуникаторлар
сұрақтары талқыланады. Бөлімде қарастырылатын MPI мүмкіндіктері: ұжымдық
операциялар әрекеттерін және өзара ықпал етуді және әр түрлі қатар
бағдарламаларды болдырмау облысын басқарады.
5.7 бөлімшесінде виртуалды топологияны қолдану бойынша MPI
мүмкіндіктері қарастырылады. Бөлімде MPI – ға сүйенетін топологиялар
көрсетілген, тікбұрышты торлар – кез келген керек түрдің қажет өлшемі
және граф топологиясы.
5.8 бөлімшесінде MPI туралы қосымша мәліметтер келтіріледі. Соның
қатарында Fortran алгоритмдік тілінде MPI қолданылыумен қатар жүретін
бағдарламалардың өңделу сұрақтары талқыланады, MPI бағдарламасының
орындалуына қысқаша сипраттама береді және MPI-2 тұрақтысының қосымша
мүмкіндіктеріне шолу жасалынады.
Өзін өзі тексеру тапсырмасы.
5.2 бөлімшесі.
1. Вектор элементтерінің арасынан минималды (максималды) мәндерін
табатын бағдарлама құрастыр.
2. Екі вектордың скаляр көбейтіндісін есептейтін бағадарлама құр.
3. n байтты ұзындықты хабарлаиманың алмасудың екі процессті
бағдарламасын құр. Эксперименттерді орындап және мәліметтердің берілу
операциясының орындалу уақытын хабарлама ұзындығына қатысты бағаланыз.
Хокни моделі бойынша құрылған теориялық бағалауларды салыстырыңыз.
5.3 бөлімшесі.
4. Бұрын құрылған бағдарламалардың, әр түрлі мәліметтердің берілу
операциясының орындалу режимдегі тәсілдерін дайындаңыз. Әр түрлі жұмыс
режиміндегі мәліметтердің берілу операциясының орындалуының куақытын
салыстырыңыз.
5. Мәліметтердің берілу операциясының орындалу тәсіліне шек қойылмай
қолданылатын бұрын құрылған бағдарламалардың тәсілдерін дайындаңыз.
Мәліметтердің берілуін толық біріктіру және есептеу үшін есептелген
операциялардың санын бағалаңыз. Мәліметтердің берілуін күту кезінде
ешқандай кедергісіз есептейтін бағдарлама құрыңдар.
6. Бір уақытта тапсырмаларды орындау және мәліметтреді беру
операциясының қолданылуымен 3 тапсырманы орындаңыз. Есептелген
тәжірибелердің нәтижелерін салыстырыңыз.
5.4 Бөлімшесі.
7. Әрбір MPI ұжымдық операциялары бар мысалдардың бағдарламасын
құрыңыз.
8. Процесстер арасындағы жұптық алмасудың көмегімен ұжымдық
операциялардың жүзеге асу бағдарламасын құрыңыз. Тәжірибелік есептеулерді
орындаңыз және өңделген бағдарламалардың орындалу уақытын және ұжымыдық
операциялар үшін MPI функциясын салыстырыңыз.
9. Тәжірибелерді орындап және жиналған, өңделген және барлық
процесстерге мәліметтерді тарату (MPI_Allreduce функциясы) операцияларын
жүзеге асыратын әр түрлі алгоритмдер үшін нәтижелерін салыстыратын
бағдарлама құр.
5.5 бөлімшесі
10. MPI – да мәліметтердің туынды типтерін құрастыру тәсілдерінің әр
біреуі үшін мысал болатындай бағдарлама құрастыр.
11. Мәліметтерді топтау және тарату функцияларына мысал болатындай
бағдарлама құрастыр.
12. Жолдар, бағандар және матрица диогналдары үшін мәліметтредің
туынды типін құрастыр.
13. Қарастырылған функциялардың ішінен прцесстерді басқару және
коммуникаиторлар үшін мысал болатын бағдарлама құр.
14. Көптеген процесстерді тіктөртбұрышты торлар түрінде көрсететін
бағдарлама құрастыр. Әрбір процесстердің жолдары және бағаналары үшін
коммуникаторлар құрыңдар. Барлық процесстер үшін және құрылған
коммуникаторлардың біріне ұжымдық операцияны орындаңдар. Операцияның
орындалу уақытын салыстырыңдар.
15. Әр түрлі коммуникаторлар процесстері арасында мәліметтерді беру
бағдарламасына өз беттеріңше, мысал құрастырыңдар.
5.7 бөлімшесі.
16. Декарттық топология үшін мысал болатын бағдарлама құрастыр.
17. Граф топологиясына мысал болатын бағдарлама құрастыр.
18. Кейбір қосымша виртуалды топология (жұлдызша, ағаш т.б) құратын
ішкі бағдарлама құрастыр.
Әдебиеттер:
MPI туралы ақпарат алынған бірнеше қайнар көздері бар. Ең бірінші ол
MPI тұрақтысымен сипатталған Интернет ақпараттық ресурсы:
http://www.mpiforum.org/. Одна из наиболее распространенных реализаций MPI
ең көп тараған оқулықтарының бірі –MPICH кітапханасы –http://www-
unix.mcs.anl.gov/mpi/mpich (MPICH2 кітапханасы мен MPI-2 тұрақтсы
http://www-unix.mcs.anl.gov/mpi/mpich2 құрамында көрсетілген) сайтында
көрсетілген. MPI туралы орыс тіліндегі материалдар http://www.parallel.ru/
сайтында баяндалған.
Жарияланған мақалалардың ішінде [4, 40 – 42, 57] жұмыстары ұсынылады.
MPI-2 тұрақтысының сипатталуы [42] алуға болады. Орыс тіліндегі
шығарылымдардың ішінде [2, 4, 12] жұмыстары ұсынылады.
Тағы бір айта кететін жайт [63] жұмыс, MPI зерттелуі паралель
бағдарламалау – матрицалық есептеулер, сұрыптау, графтарды өңдеу және т.б
типтік тапсырмалар мысалында жүзеге асады.
2.5 Бөлім Паралель алгоритмдердің құрылцы және дамуы
6. Тақырып Матрицаларды векторларға көбейтудің паралель тәсілдері
Дәріс мақсаты: Матрицаларды векторға көбейту тапсырмасын қарастыру.
Тапсырманың орындалуын және алгоритмдердің кезектесіп келуін және оның
шешімін жүзеге асыру. Матрицалық опреацияларды паралелеь орындау үшін
қажет, есептеу жүйесінің прцессоры арасындағы матрицаларды бөлу тәсілін
сипаттау. Ары қарай матрицаның векторға көбейту алгоритмінің паралель
орындалуына жақын 3 мүмкіндікті қарастыру.
Тақырыпқа сұрақтар:
1. Есептеу жүйесінің процессорлары арасындағы матрица
элементтерінің орналасуының негізгі тәсілдерін атаңыз?
2. Матрицаны векторға көбейту тапсырмасының мақсат неден
тұрады?
3. Матрицаны векторға көбейтудегі келесі алгоритмін есептеу
қиындығы қаншалықты?
4. Неге матрицаны векторға көбейтудің паралель алгоритімін
өңдеген кезде вектор – операндтты барлық процессорға
қайталауға рұқсат етіледі?
5. Матрицаны векторға көбейтудің паралель алгоритімін өңдеу
үшін жақындаулар ұсынылады.
6. Матрицаны векторға көбейтудің паралель алгоритімінің жалпы
схемасын көз алдарына елестетіңдер.
7. Қарастырылған алгоритмдердің біреуіне анализ жасап, олардың
нәтижелерің көрсеткішін алыңыз.
8. Берілген матрицаларды векторға көбейту алгоритмдарының
ішнідегі қайсысы жылдам және нәтижелі көрсеткішке ие болып
отыр?
9. Мәліметтерді бөлудің циклдік схемасын қолдану берілген
алгоритмдерінің әрбіреунің жұмыс істеу уақытына әсер ете ала
ма?
10. Мәліметтреді ленталық схема бойынша бөлетін алгоритмдер үшін
қандай ақпараттық іс - әрекеттер орындалады? Матрицаларды
жол және баған бойынша бөлу кезіндегі мәліметтерді берудегі
қажет операциялардың айырмашылығы неде?
11. Матрицаларды векторларға көбейтудің блоктық алгоритмдері
үшн, қандай ақпараттық іс - әрекеттер орындалады?
12. Қарастырылған алгоритмдер үшін қандай коммуникациялық желі
топологиясы мақсатқа лайықты болып саналады?
13. Мәліметтерді жол бойынша бөлу кезіндегі, матрицаларды
векторларға көбейтудің бағдарламалық орындалу алгоритмдеріне
мінездеме бер. Бағдарламалық орындалуда басқа қарастырылған
алгоритмдердің айырмашылығы неден тұрады?
14. Бағдарламалық орындалуда MPI кітапханасының қандай
функциялары қажет болды?
Тақырыптың қысқаша мазмұны (тезистері):
Берілген дәрісте, матрицаларды векторларға көбейту тапсырмаларының
мысалдарында көрсетілген, матрицалық опреацияларды орындау кезінде паралель
есептеу ұйымдары үшін қолданылатын, көппроцессорлы есептеу жүйесінің
процессорлары арсындағы матрицаларды бөлудің мүмкін сахамалары
қарастырылған. Схемалармен қоса матрицаларды жолақтарға (вертикаль немес
горизанталь бойынша) немесе тіктөртбұрышты элементтерге (болктарға)
бөлшектеу тәсілдері қарасытырылған.
Ары қарай дәрісте қарастырылған тәсілдерді қолдана отырып,
матрицаларды бөлу үшін матрицаларды векторларға көбейту операциясының
паралель орындалуының үш мүмкін амалдары толық баяндалады. Бірінші
алгоритм прцессорлер арасындағы матрицаларды жол бойынша бөлуге, ал екінші
– матрицаларды бағана бойынша бөлуге, ал үшіншісі- мәліметтерді блоктық
бөлуге негізделген. Әрбір алгоритм 4 – ші тақырыпта сипатталған жалпы
схемаға сәйкес құрылған., алдымен базалық ішкі тапсырмалар анықталады,
содан кейін ақпаратқа қатысты ішкі тапсырмалар ерекшеленеді, ары қарай
прцессорлер арасындағы ішкі тапсырмалардың орнласуы мен маштабталуы
талқыланады. Аяқталуында әрбір алгоритм үшін паралель есептеулерден алынған
нәтижелеу анализі жүргізіледі, және есептелген тәжірибе нәтижелері
келтіріледі. Мәліметтерді жол бойынша ленталық бөлудегі матрицаны вектрға
көбейту алгоритмдері үшін бағдарламаның орындалу мүмкін нұсқалары
келтіріледі.
Алынған нәтижелі көрсеткіштер мәліметтерді бөлуге қолданылған барлық
тәсілдер есептеу қиындықтарын біркелкі теңестіруге әкеліп соғады және
айыру барысында процессорлар арсында әрекет ететін ақпараттың орындалуын
ғана көрсетеді. Бұл қатынаста, таңдалған мәліметтерді бөлу тәсілі
мәліметтеді берудің қажет опрецияларының мінездемелеріне қалай әсер
ететінін және әр түрлі алгоримтдердің коммуникациялық әрекетіндегі
негізгі айырмшылықтарын ерекшелеуді бақылау өте қызықты. Сонымен қатар,
паралель алгоритмніің сәйкесінше нәтижелі орындалу үшін, процессорлар
арасындағы байланыс сызығының мақсаттық құрылымын анықтау өте мыңызды.
Мысалы, мәліметтерді ленталық бөлігіне негізделген алгоритмдер, гиперкуб
немесе толық граф түріндегі желі топологиясына бағытталған. Мәліметтерді
блоктық бөлуге негізделген алгоритмі жүзеге асуы үшін, тополгиялық торларды
иемдену қажет.
6.1 суретіндегі жапы графикте барлық қарастырылған алгоритмдер үшін,
есептеу эксперментінің орындалу нәтижесінде алынған жылдамдығының
көрсеткіші көрсетілген. Тағы бір ескере кететін жайт, қосымша есептеулерге
сүйенсек, саны көп прцессорлар мен көп өлшемді марицалар үшін
алгоритмдердің блоктық көбейтінідісі тиімдірек болады.
[pic]
Сурет 6.1 Қарастырылған алгоритмдердің эксперименттік есептеулер
нәтижесі бойынша 2000x2000 матрицасының және 2000 элементің вектрларының
жылдамдық көрсеткіші
Өзін - өзі тексеруге арналған тапсырмалар:
1. Көлденең жолақта матрицаларды ленталық бөлшектеуге егіделген,
паралель алгоритмнің жүзеге асырылуын орындаңыз. Бұл алгоритмнің
есептеу жүйесінің қолданған параматрлерін ескере отырып, жұмыс
уақытының бағасын құрыңыз. Есептеу экспериментін жүзеге асырыңыз.
Бұрын дайындайындалған теориялық бағалаулармен экперименттердің
нәтижелерін салыстырыңыз.
2. Матрицаларды блоктарға бөлшектеуге нгізделген, паралель алгоритмнің
жүзеге асырылуын орындаңыз. Бұл алгоритмнің есептеу жүйесінің
қолданған параматрлерін ескере отырып, жұмыс уақытының теориялық
бағасын құрыңыз. Есептеу экспериментін жүзеге асырыңыз. Бұрын
дайындайындалған теориялық бағалаулармен экперименттердің
нәтижелерін салыстырыңыз.
Әдебиеттер:
Матрицаларды векторларға көбейту, тапсырмалары паралель
бағдарламалаудың мысалын көрсетуде жиі қолданылады және шешімдері
әдебиеттерде кең қарастырылған. Қосымша оқу құралы болып, [2, 51, 63]
жұмыстары ұсынылады. Матрицалардың паралель орындалу сұрақтары [30]
жұмысында толық талқыланады.
Сұрақтарды талқылау кезінде бағдарламалық жүзеге асырудың паралель
тәсілдерін қарастыруда [23] жұмыс ұсынылады. Мұнда бәріне мәлім және
практикада кең қолданылатын паралель есептеудің бағдарламалаудың сандық
кітапханалар тәсілі ScaLAPACK қарастырылған.
7. Тақырып. Матрицалық көбейтудің паралель әдістері.
Дәріс мақсаты: Матрицалық есептедуің негізігі тапсырмалардың бірі –
матрицаларды көбейтуді қарастыру. Тапсырмаларды орнату және келесі
алгоритмдерінің шешімін табу. Ары қарай алгоритмдердің паралель жүзеге
асыратын мүмкін жақындауларын қарастыру және кең тараған алгоритмдерін
қарастыру: мәліметтердің ленталық схема бойынша бөлуге негізделген
алгоритм, алгоритм Фокса (Fox) және алгоритм Кэннона (Cannon)
Тақырып бойынша сұрақтар:
1. Матрицаларды көбейту тапсырмасының құрылымы неден тұрады?
2. Тапсырмаға Матрицаларды көбейту операциясы қолданылатын мысал
келтір.
3. Матрицаларды көбейту операциясының орындалу алгоритмдеріне әр
түрлі мысал келтіріңдер. Олардың есептеу жұмысы ерекшлене ме?
4. Матрицалық көбейтудің паралель алгоритімін өңдеген кезде
мәліметтерді бөлудің қай тәсілі қолданылады?
5. Қарастырылған матрицаларды көбейту паралель алгоритімінің жылпы
схемасын көз алдына елестетіңдер.
6. Туынды матрицаларды горизанталь бөлшектеу кезіндегі ленталық
алгоритмнің эфектісінің көрсеткішін алып, анализ жаса.
7. Мәліметтерді бөлудегі ленталық схемасы бойынша алгоритмдер үшін
қандай ақпараттық әрекеттер орындалады?
8. Матрицаларды көбейтуде блоктық алгоритмдер үшін қандай ақпарттық
әрекеттер орындалады?
9. Әрбір қарастырылған алгоритмдер үшін коммуникациялық желінің қай
топологиясы мақсатқа жақын болып табылад?
10. Қарастырылған алгоритмдердің ішінен қайсысы жады көлемінің қажет
аз немесе көп талаптарын сипаттайды?
11. Қарасытырылған алгоритмдердің ішіндегі қайсысы жылдамдықтың және
эффектіліктік жақсы көрсеткішіне ие?
12. Матрицалық көбейтудің орындалу мүмкіндіктерін, матрицаларды
векторларға көбейту операциясы бойынша бағалаңыз.
13. Фокса алгоритімінің бағдарламалық жүзеге асырылуына жалпы
мінездеме беріңіз. Бағдарламалық жүзеге асырылудың басқа
қарастырылған алгоритмдерден айырмашылығы неде?
14. Бағдарламалық жүзеге асыруда MPI кітапханасының қандай
функциялары қажет болды?
Тақырыптың қысқаша мазмұны (тезистер):
Берілген дәрісте матрицаларды көбейту операцияларын орындау үшін үш
паралель тәсілдер қарастырылған. Бірінші алгоритм процессорлар арасындағы
ленталық бөлшектеуге негізделген. Дәрісте бұл алгоритмнің екі тәсілі
келтірілген. Алгоритмнің бірінші нұсақасы әр түрлі көбейтілген
матрицаларды бөлуге негізделген – бірінші матрица (А матрицасы) горизанталь
жолақтарға бөлшектенеді, ал екнші матрица (В матрицасы) вертикаль
жолақтарға бөлінеді. Екінші нұсқасы ленталық алгоритм қос матрицаны
горизанталь жолақтарға бөлуде қолданылады.
Ары қарай дәрісте кең таралған Фокса және Кэннона алгоритмдері
қарастырылады. Матрицаларды бөлудің бірдей схемаларын қолданған кезде
берілген алгоритмдер орындалған мәліметтерді беру операциясымен
ерекшеленеді. Фокса алгоритімі үшін есептеу кезінде, жіберу және матрица
блоктарының циклдік жылжыуы жүзеге асады, ал Кэннона алгоритімінде тек
циклдік жылжу операциясы ғана жүзеге асады.
Мәліметтердің бөлшектену тәсілдерінің айырмашылығы паралель
алгоритмдер әлдеқайда эффектілеу болатын, әр түрлі коммуникациялық желінің
топологиясына әкеледі. Сонымен, мәліметтерді ленталық бөлшектеуге
негізделген алгоритмдер, гиперкуб немесе толық граф түріндегі топологиялық
желіге бағытталған. Мәліметтерді блоктық бөлуге негізделген, алгоритмдерді
жүзеге асыру үшін, топология торын иемдену қажет.
7.1 Суреті жалпы графикте барлық қарастырылған алгоритмдер үшін
есептеу тәжірибесін орындау кезінде алынға, жылдамдық көрсеткіштері
көрсетілген. Орындалған есептеулер мынаны көрсетеді, процесстер көп болған
жағдайда матрицаларды көбейтудің блоктық алгоритмдері эффектілеу болады.
[pic]
Сурет 7.1 Матрицаларды көбейту кезіндегі төрт прцессті қолданған, үш
паралель паралель алгоритмнің жылдамдығы
Өзін - өзі тексеруге арналғана тапсырмалар:
1. Матрицаларды көбейтуде екі ленталық алгоритмнің жүзеге
асырылуын орындаңыз. Бұл алгоритмдердің орындалу уақытын
салыстырыңыз.
2. Кэннона алгоритімінің жүзеге асырылуын орындаңыз. Бұл
алгоритмнің есептеу жүйесінің қолдану параметірін ескере
отырып, жұмыс істеу уақытына теориялық баға бер. Есептеу
тәжірибесін жүргізіңдер. Бұрын алныған териялық бағалар мен
жүзеге асқан тәжірибелерді салыстырыңдар.
3. Матрицаларды көбейтудің тіктөрт ұрышыт процессор торларынң
жалпы түрінде де орындалатын блоктық алгоритімінің жүзеге
асырылуын орындаңыз.
4. Бұрын өңделеген матрицаларды векторларға көбейту
бағдарламаларын қолдана отырып, матрицалық көбейтуді жүзе
асыруды орындаңыз.
Әдебиеттер:
Матрицаларды көбейту әдебиеттерде кең қарастырылады. Қосымша оқу
материалы ретінде [2, 51, 63] жұмыстары ұсынылады. Матрицалардың паралель
орындалу сұрақтары [30] жұмысында толық талқыланады.
Сұрақтарды талқылау кезінде бағдарламалық жүзеге асырудың паралель
тәсілдерін қарастыруда [23] жұмыс ұсынылады. Мұнда бәріне мәлім және
практикада кең қолданылатын паралель есептеудің бағдарламалаудың сандық
кітапханалар тәсілі ScaLAPACK қарастырылған.
8. Тақырып Сызықтық теңдеулер жүйесін шешу.
Дәріс мақсаты: Сызықтық теңдеулер жүйесін шешу тапсырмаларын
қарастыру. Қажет анықтамалар мен тапсырмалардың орындалуын келтіру. Гаусс
әдісінің – сызықтық теңдеулер жүйесін шешудің жалпы түрінің біл әдісін және
паралель нұсқасын сипатау. Ары қарай кездесетін градиенттрдің интерациондық
әдістерін жүзеге асыратын, кездесетін және паралель алгоритмдерді сипаттау.
Тақырыпқа сұрақттар:
1. Сызықтық теңдеулер жүйесі қандай мағына береді? Қандай жүйе
түрлерін білесіңдер? Әр түрлі типтер жүйесін шешу үшін қандай
әдістер қолданылуы мүмкін?
2. Сызықтық теңдеулер жүйесін шешудің тапсырмалар құрылымы неден
тұрады?
3. Гаусс әдісін паралель жүзеге асыру идеясы неде?
4. Гаусс әдісінің паралель нұсқасы үшін базалық тапсырмалар
арасында қандай ақпараттық әрекеттер бар?
5. Гаусс әдісінің паралель нұсқасы үшін эфектілік нұсқасы
қаншалықты?
6. Гаусс әдісінің паралель нұсқасының бағдарламалық жүзеге асыру
схемасы неден тұрады?
7. Градиенттердің кездесетін әдістерін паралель жүзеге асыру
идеясы неден тұрады?
8. Алгоритмдердің қайсысының коммуникациялық қиындығы жоғары?
Тақырыптың қысқаша мазмұны.
Берілген дәріс сызықтық теідеулер жүйесін шешу кезіндегі, паралель
есептеу мәселесіне араналған. Оқу құралының бандалуы кең тараған екі
алгоритмдердің қолдануымен жүргізіледі: Гаусс әдісі тапсырманың тура
алгоритмдік шешімінің мысалы және кездесетін градиенттердің интерациондық
әдісі.
Гаусс әдісінің паралель нұсқасы жолдардың орналасуын циклдік схемасын
қолдана отырып, есептеу қиындығын теңестіруге мүмкіндік беретін,
процессорлар арасындағы матрицаларды ленталық бөлуге негізделген. Әдістің
паралель нұсқасын анықтау үшін, проектілеудің толық цикілі жүргізіледі –
базалық тапсырмалар анықталады, ақпараттық әрекеттер ерекшеленеді,
маштабталу сұрақатары талқыланады, эффектілік баға көрсеткіштері
шығарылады, бағдарламалық жүзеге асыру схемасы ұсынылады және есептеу
тәжірибелерінің нәтижесі келтіріледі. 8.8 суретіндегі графиктен көрінгендей
Гаусстың паралель алгоритімі жылдамдық пен эффектіліктің жоғарағы
көрсеткішін көрсетеді.
Кездескен градиенттердің паралель нұсқасының әдісін қарастырғанадағы
маңызды сәт – бұл әдістің паралель есептеу тәсілі – матрицаларды векторға
көбейту операциялары, векторлардың скаляр көбейтіндісі, векторларды қосу
және алу орындалған әрекеттері есептеудің паралель алгоритімі арқылы алынуы
мүмкін. Бұл оқу мысалына алынған жақындаулар, матрицаларды векторға
көбейту операцияларын паралель есептеуден тұрады, сонымен қатар векторларға
қатысты барлық есептеулер мәліметттерді беру операциясының орындалу санын
азайту үшін, әрбір процессорде қайталанады – бұл тәсілдің эфффектілік
көрсеткіштері есептеудің паралель ұйымдары 8.1 суретте көрсетілген.
[pic]
Сурет 8.1 3000x3000 матрица өлшемімен сызықтың теңдеулер жүйесінің
паралель алгоритмдер жылдамдығы
Өзін - өзі тексеруге арналған тапсырмалар.
- Гаусс әдісінің тура және кері кезеңдері үшін паралель
есептеудің эффектілігіне анализ жасаңдар. Қай кезңде төмен
көрсеткіш көрсететінін бағалаңыз.
- Матрицаны бағана бойынша вертикаль бөлшетек кезіндегі, Гаусс
әдісінің паралель нұсқасын өңдеуді орындаңыз. Есептеу
жүйесінің қолану парметрлерін ескере отырып, бұл алгоритмнің
жұмыс уақытына териялық бағалаулар құрыңыз. Есептеу
тәжірибелерін жүргізіңіз. Орындалған тәжірибе нәтижелерін
бұрын алынған теориялық бағалаулармен салыстырыңдар.
- Кездескен гардиенттертер әдісімен паралельь жүзеге асыруды
орындаңыз. Қолданған есептеу жүйесініңпараметрлерін ескере
отырып, жұмыс уақытына теориялық баға беріңіз. Орындалған
тәжірибе нәтижелерін бұрын алынған теориялық бағалаулармен
салыстырыңдар.
- Сызықтың теңдеулер жүйесін шешудің (мысалы, Kumar (1994) қара)
Зейдел және Якоби әдістерінің паралель нұсқасын өңдеуді
орындаңыз. Есептеу тәжірибелерін жүргізіңіз. Орындалған
тәжірибе нәтижелерін бұрын алынған теориялық бағалаулармен
салыстырыңдар.
Әдебиеттер:
Сызықтық теңдеулер жүйесін шешудің сандық мәселесі әдебиеттерде толық
қарастырылады. Оқу материалын қарастыру үшін [6, 13, 51, 63] жұмыстары
ұсынылады. Берілген типі тапсырмалар үшін паралель есептеу сұрақтарының кең
талықылануы [22, 30] жұмысында орындалады.
Сұрақтарды талқылау кезінде бағдарламалық жүзеге асырудың паралель
тәсілдерін қарастыруда [23] жұмыс ұсынылады. Мұнда бәріне мәлім және
практикада кең қолданылатын паралель есептеудің бағдарламалаудың сандық
кітапханалар тәсілі ScaLAPACK қарастырылған.
9. Тақырып Сұрыптаудың паралель әдістері
Дәріс мақсаты: Мәліметтерді сұрыптаудың әр түрлі алгоритмдерін
қарастыру. Оларды жалпы принцип бойынша, паралельдеу кезінде қолданылатын
нақты алгоритмдер ретніде баяндау. Қарастырылғана алгоритмдер эфектілігін
теориялық жағынана бағалау. Есептелген тәжірибелер нәтижесін анализ жасап
келтіру.
Тақырып бойынша сұрақтар:
1. Мәліметтерді сұрыптау тапсырмасының құрылымы неден тұрады?
2. Алгоритмдерді сұраптаудың бірнеше мысалдар келтір. Келтірілген
алгоритмдердің қиындығы қаншалықты?
3. Мәліметтерді сұрыптау тапсырмалары үшін қандай операция базалық
болып табылады?
4. Мәліметтерді сұрыптау тапсырмаларының базалық операцияларын
паралель талдаудың мәні неде?
5. Жұп – жұп емес алгоритмдердің орныны ауыстыру неге әкеледі?
6. Шелла алгоритімінің паралель нұмқасы неден тұрады? Бұл паралель
сұрыптау алгоритімінің жұп емес орын ауыстыру әдісінен негізгі
айырмашылықтары қандай?
7. Жылдам сұрыптау алгоритімінің паралель нұсқасы қандай мағына
береді?
8. Жылдам сұрыптау паралель алгоритімі үшін жүргізілген элементті
дүрыс таңдауға не тәуелді?
9. Жүргізілген элементтерді таңдаудың қандай тәсілдері ұсынылады?
10. Қарастырылған сұрыптау алгоритмдері қандай топологияларға
қолданылуы мүмкін?
11. Тұрақты таңдау үлгісін қолданған сұрыптау алгоритімі неден тұрады?
Тақырыптың қысқаша мазмұны (тезистер):
Дәрісте кең таралған көпіршіктелген сұрыптау, Шелла сұрыптауы және
жылдам сұрыптау берілген оқу материалында жиі кездесетін, сөйлемдерде
мәліметтерді реттеу тапсырмасы қарастырылады. Сұрыптау әдістерін айтқанда,
алгоритмдерді паралельдеу, эффектілерге анализ жасау және есептеу
тәжірибелерін орындау нәтижелерімен қоса алынған теориялық бағаларға ерекше
назар аударылады.
Көпіршіктелген сұрыптау алгоритімі ағымды түрде паралельдеуге мүлдем
берілмейді, күштеп келгенде итерация негізгі әдістері орындалады. Қажет
паралельдеуді енгізу үшін алгритмнің қрытынды нұсқасы қарастырылған – орын
ауыстырудың жұп – жұп емес әдісі. Оның мәнісі мынада, сұрыптау алгоритіміне
сұрыптау итерациясының жұп санына қатысты емес, итерациялық әдістің екі әр
түрлі орындалу ережесі енгізілген. Итерациядағы реттеу мәінінің жұбын
салыстырсақ, жұп – жұп емес әдісінің орнын ауыстыру тәуелсіз болып
табылады және паралель орындалуы да мүмкін.
Шелла алгоритімі үшін гиперкуб түріндегі топологияның ұсынуымен
схемаларды паралельдеу қарастырылады. Мұндай тополгиялардың ұсынылуы бір –
бірінен сызықтық нөмірлеу арқылы алыс орналасқан процессорлардың әрекет ету
ұйымдарымен мүмкін болып табылады. Ережеге сай, мұндай есептеу ұйымдары
сұрыптау алгоритімінің орындалу санын азайтуға мүмкіндік береді.
Жылдам сұрыптау алгоритмдері үшін паралельдеудің үш схемасы
келтірілген. Бірінші екі схемалар желідегі топологияны гиперкуб түрінде
көрсетуге негізделген. Негізігі есепттеу итерациясы, қалған барлық
гиперкуб процессорына таралатын жетекші элемент процесорының біреуін
таңдаудан тұрады. Жетекші элемент алынғанан кейін, процессорлар өз
блоктарын бөледі және алынған блок бөлшектері жұп болып байланысқан
прцессорлар арасымен беріледі. Нәтижесінде мұндай операцияның орындалуы
ағымдағы гиперкубтың екі кішкентай гиперкубқа бөледі, олар өз кезегінде
жоғырыда келтірілген схемаларға әкеп соғады.
Жылдам сұрыптау алгоритмдерін келтіру кезіндегі негізгі сәттер болып
жетекш элементтерді дұрыс таңдау болып табылады. Үйлесімді стратегия
прцессордағы мәліметтер бірдей өлшемді бөліктерге бөлінетін, жетекші
элемент мәнін дұрыс таңдаудан тұрады. Жалпы жағдайда өз бетімен
генерацияланған ағымдағы мәліметтердің мұндай жағдайдағы жетістігі
әлдеқайда күрделі тапсырма. Бірінші схемада басқарушы процессорда
арифметикалық элемент ортасы ретінде, жетекші элемент таңдау ұсынылады.
Екінші схемада,(жылдам сұрыптаудың қорытынды алгоритімі) жетекші мән
ретінде мәліметтер блогындағы орта элементті алу үші, деректер әрбір
процессорда алдын ала реттеледі. Үшінші схема (үлгілерді тұрақты теруді
қолдана отырып сұрыптау) жылдам сұрыптау алгоритімін паралельдеу көптеген
жетекші элементтерді жинақтау көпдеңгейлі схемасына негізделген. Мұндай
жақындаулар процессордың тұрақты санында, қолданылуы мүмкін, көптеген
мәліметтерді жіберуді және ереже бойынша, процессорлар арасындағы
мәліметтердің біркелкі анықталуына мүмкіндік береді.
Өзін - өзі тексеруге арналған тапсырмалар.
1. Көпіршіктелген сұрыптау паралель алгоритмдерін жүзеге асыруды
орындаңыз. Тәжірибелер жүргізіңіз. Есептеу жүйесінің параметірін
және жүзеге асырылуын қолданған кездегі мәліметтерді жіберу
операциясын ескере отырып, теориялық бағалар құрыңыз. Алынған
теориялық бағаларды тәжірибе нәтижелерімен салыстырыңыз.
2. Берілген схемалардың ішінен жылдам сұрыптау паралель алгоритімін
жүзеге асырылуын орындаңыз. Латенттау параметрінің мәнін
анықтаңыз, есептеу жүйесінде қолданылатын базалық операциялардың
жіберу қабілеті мен орындалу уақытын және паралель есептеу әдісін
жүзеге асыру үшін жылдамдығы мен эффектілігінің көрсеткішіне баға
беріңіз.
3. Кең тараған сұрыптаудың шағылысу алгоритімі үшін, есептеудің
паралель схемасын құрыңыз (әдістің толық сипаттамасын, мысалы,
[26] немесе [50] жұмыстарынан алуға болады). Өңделген алгоритмнің
жүзеге асырылуын орындаңыз және әдіс күрделілігіне теориялық баға
беріңіз.
Әдебиеттер:
Мәліметтерді реттеу тапсырмаларының мүмкін шешімдері мына
әдебиеттерде кең тараған; алгоритмдерді сұрыптауға толық шолу [50] жұмыс
құрамында, соңғы шыққан баспалардың ішінен [26] жұмыс ұсынылады.
Шелла Сұрыптауы және көпіршіктелген сұрыптау алгоритмдердің паралель
нұсқасы [51] қарастырылған.
Гиперкуб түріндегі желі топологиясындағы мәліметтерді берудегі жылдам
сұрыптаудың паралель схемасы [51, 63] сипатталған. Үлгілерді тұрақты теруді
қолданатын сұрыптау [63] жұмыста көрсетілген.
Мәліметтерді сұрыптау үшін, паралель есептеудің сұрақтарын
қарастыруда [17] жұмыстың көп пайдасы тиуі мүмкін.
10. Тақырып Графтардағы паралель әдістер
Дәріс мақсаты: Графтарды өңдеу кезінде туатын әр түрлі типтік
тапсырмаларды қарастыру. Бұл тапсырмалардың шешіміне қолданылатын
алгоритмдер келтіру және оларды паралельдеу жлдарын талқылау. Қарастырылған
алгоритмдер эффектілігіне теориялық баға беру. Есептелген тәжірибелер
нәтижелеріне анализ жасау.
Тақырып бойынша сұрақтар:
1. Граф анықтамасын келтіріңіз.Графтар тапсырмасы үшін қандай
негізгі әдістер қолданылады.
2. Іздеу тапсырмасының барлық қысқа жолдары неден тұрады?
3. Флойда алгоритімінің жалпы схемасын келтіріңіз. Алгритмнің
жұмыс сыйымдылығы қаншалықты.
4. Флойда алгоритмінің паралельдеу тәсілі неден тұрады?
5. Ағаштың минималды қамту тыпсырмасы неден тұрады? Тәжірибеда
қолданылған тапсырмалар мысалын келтіріңдер.
6. Прима алгоритімінің жалпы схемасын келтіріңдер. Алгоритмнің
жұмыс сыйымдылығы қаншалықты?
7. Прима алгоритімінің паралельдеу тәсілі неден тұрады?
8. Графтарды комбинатрикалық және геометриялық бөлудің
айырмашылығы неде? Қандай әдістер ерекше? Неге?
9. Координат бойынша бөлшектеу әдісіне және алгоритмдерді бөлуді
байланысын ескере отырып, сипаттама бер. Бұл тәсілдердің
қайсысы жүзеге асыру үшін қарапайым блып табылады?
Тақырыптың қысқаша мазмұны (тезистер).
Дәрісте графтарды өңдеуде типтік тапсырмаларды шешу үшін алгоритмдер
қатары қарастырылған. Сонымен қатар, графтрады бөлу әдісіне шолу жасалған.
Флойда алгоритіміне – келесі нұсқа әдісіне жалпы есептеу схемасы
беріледі, оларды паралельдеу тәсілі талқыланады, алынған паралель
есептеулерге эффектілік анализі жасалынады, әдістің бағдарламалық жүзеге
асырылуы қарастырылып, есептелген тәжірибелер нәтижелері келтірілген.
Қарастырылған Флойда алгоритіміне қолданылатын жақындаулар, процессорлар
арасындағы граф төбелерін бөлуден тұрады, ал ақпараттық әрекет ету
қажеттілігі, әрбір итерация әдісінде есептеу жүйесінің бір процессорынан
барлық процессорға бір матрица жолының араласып берілуінен тұрады.
Ағашты жаулаған, бейімделмеген өлшенген графтың минималды іздеу
тапсырмасын шешу үшін Прима алгоритімі қарастырылған. Граф негізі деп
қандай да бір минималды салмағы бар, ағымдағы граф пен қабырғаларының
биіктігі анықталған және циклсіз байланысқан ішкі графтарды айтады.
Алгоритмдер үшін оның келесі нұсқаларына жалпы сипаттамалар беріледі де,
оның паралель орындау мүмкін тәсілдері, паралель есептеу эффектілігі және
жылдамдығының теориялық бағалары анықталады; сонымен қатар, жасалған
эксперимент есептеулерінің нәтижелері де қарастырылады. Прима алгортімінің
паралель нұсқасы, алдыңғы жағдайдағы секілді ақпараттық әрекеттерге қатысты
бірнеше үлкен көлемдерінде - әрбір алгоритм итерациясына бір процессорда
мәліметтерді жинақтау операциясы және есептеу жүйесінің барлық процессоріне
таңдалған граф биіктігін жіберу қажет болып табылатын, процессорлар
арасындағы граф биіктігін бөлуге негіделген.
Графтарды бөлу есебінің жалпы шешімі, паралель есептеуді қолданатын
көптеген ғылыми зертеулер үшін маңызды болып саналады. Мысал ретінде
бөлімде, бір өлшемді немесе екі өлшемді желіден сәйкес графқа есептеудің
модельдеу процесіне көшудің жалпы тәсілі келтірілген. Графтарды бөлу
тапсырмасын шешу үшін желіліреді бөлу кезінде тек желі туралы координаттық
мәліметтерді қолданатын, геометриялық әдістер және граф төбелерін
қиылыстырмайтын комбинаторикалық алгоритмдер қарастырылған. Қарастырылған
геометриялық әдістер қатарына: координат бойынша бөлшектеу(the coordinate
nested dissection method), тең бөлу әдісінің рекурсивті инерциясы(the
recursive inertial bisection method), Пиано қисықтарын қолданумен желілерді
бөлу (the space-filling curve techniques) жатады. Стырылған аогоритмдер
қатарына: байланысты ескере отырып бөлу (the levelized nested dissection)
және Кернигана – Лина алгоритімі(the Kernighan – Lin algorithm) жатады.
Қарастырылған әдістерді реттеу үшін, орындалу уақыты бойынша, алынған
шешімдердің дәлдігі, паралельдеу мүмкіндіктері және т.б алгоритмдердің
жалпы салыстыру сипаттамалары жүргізіледі.
Өзін - өзі тексеру сұрақтары:
1. Бағдарламамен берілген кодтты қолдана отырып, Флойда паралельдеу
алгоритімінің жүзеге асырылуын орындаңыз. Есептеу тәжірибелерін жүргізіңіз.
Қолданған есептеу жүйесінің параметрлерін ескере отырып, теориялық бағалар
жасаңыз. Тәжірибелік мәліметтер мен алынған бағаларды салыстырыңыз.
2. Прима алгоритімінің паралельденуін жүзеге асырыңыз. Есептеу
тәжірибелерін жүргізіңіз. Қолданған есептеу жүйесінің параметрлерін ескере
отырып, теориялық бағалар жасаңыз. Тәжірибелік мәліметтер мен алынған
бағаларды салыстырыңыз.
3. Кернинг – Лина алгоритімінң жүзеге асырылу бағдарламасын құрыңыз.
Бұл алгоритмнің паралельдеу мүкіндіктеріне баға беріңіз.
Әдебиеттер:
Флойда және Прима алгоритмдері бойынша ақпарат мысалы, [26] алынуы
мүмкін.
Графтарды бөлу мәселесімен байланысты қарастырылған сұрақтар, [21,
36, 37, 44, 53, 55, 58, 61, 65, 67] жұмысының құрамында.
Графтарды бөлудің паралель алгоритімі [20, 38, 44, 48, 49, 65, 74]
жұмыстарында қарастырылады.
Пәндер
- Іс жүргізу
- Автоматтандыру, Техника
- Алғашқы әскери дайындық
- Астрономия
- Ауыл шаруашылығы
- Банк ісі
- Бизнесті бағалау
- Биология
- Бухгалтерлік іс
- Валеология
- Ветеринария
- География
- Геология, Геофизика, Геодезия
- Дін
- Ет, сүт, шарап өнімдері
- Жалпы тарих
- Жер кадастрі, Жылжымайтын мүлік
- Журналистика
- Информатика
- Кеден ісі
- Маркетинг
- Математика, Геометрия
- Медицина
- Мемлекеттік басқару
- Менеджмент
- Мұнай, Газ
- Мұрағат ісі
- Мәдениеттану
- ОБЖ (Основы безопасности жизнедеятельности)
- Педагогика
- Полиграфия
- Психология
- Салық
- Саясаттану
- Сақтандыру
- Сертификаттау, стандарттау
- Социология, Демография
- Спорт
- Статистика
- Тілтану, Филология
- Тарихи тұлғалар
- Тау-кен ісі
- Транспорт
- Туризм
- Физика
- Философия
- Халықаралық қатынастар
- Химия
- Экология, Қоршаған ортаны қорғау
- Экономика
- Экономикалық география
- Электротехника
- Қазақстан тарихы
- Қаржы
- Құрылыс
- Құқық, Криминалистика
- Әдебиет
- Өнер, музыка
- Өнеркәсіп, Өндіріс
Қазақ тілінде жазылған рефераттар, курстық жұмыстар, дипломдық жұмыстар бойынша біздің қор #1 болып табылады.
Ақпарат
Қосымша
Email: info@stud.kz