Бөлім Паралель алгоритмдердің құрылцы және дамуы

1. 
   Есептеу жүйесінің процессорлары арасындағы матрица элементтерінің орналасуының негізгі тәсілдерін атаңыз?
   
2. 
   Матрицаны векторға көбейту тапсырмасының мақсат неден тұрады?
   
3. 
   Матрицаны векторға көбейтудегі келесі алгоритмін есептеу қиындығы қаншалықты?
   
4. 
   Неге матрицаны векторға көбейтудің паралель алгоритімін өңдеген кезде вектор – операндтты барлық процессорға қайталауға рұқсат етіледі?
   
5. 
   Матрицаны векторға көбейтудің паралель алгоритімін өңдеу үшін жақындаулар ұсынылады.
   
6. 
   Матрицаны векторға көбейтудің паралель алгоритімінің жалпы схемасын көз алдарына елестетіңдер.
   
7. 
   Қарастырылған алгоритмдердің біреуіне анализ жасап, олардың нәтижелерің көрсеткішін алыңыз.
   
8. 
   Берілген матрицаларды векторға көбейту алгоритмдарының ішнідегі қайсысы жылдам және нәтижелі көрсеткішке ие болып отыр?
   
9. 
   Мәліметтерді бөлудің циклдік схемасын қолдану берілген алгоритмдерінің әрбіреунің жұмыс істеу уақытына әсер ете ала ма?
   
10. 
    Мәліметтреді ленталық схема бойынша бөлетін алгоритмдер үшін қандай ақпараттық іс - әрекеттер орындалады? Матрицаларды жол және баған бойынша бөлу кезіндегі мәліметтерді берудегі қажет операциялардың айырмашылығы неде?
    
11. 
    Матрицаларды векторларға көбейтудің блоктық алгоритмдері үшн, қандай ақпараттық іс - әрекеттер орындалады?
    
12. 
    Қарастырылған алгоритмдер үшін қандай коммуникациялық желі топологиясы мақсатқа лайықты болып саналады?
    
13. 
    Мәліметтерді жол бойынша бөлу кезіндегі, матрицаларды векторларға көбейтудің бағдарламалық орындалу алгоритмдеріне мінездеме бер. Бағдарламалық орындалуда басқа қарастырылған алгоритмдердің айырмашылығы неден тұрады?
    
14. 
    Бағдарламалық орындалуда MPI кітапханасының қандай функциялары қажет болды?
    

Тақырыптың қысқаша мазмұны (тезистері):

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

Ары қарай дәрісте қарастырылған тәсілдерді қолдана отырып, матрицаларды бөлу үшін матрицаларды векторларға көбейту операциясының паралель орындалуының үш мүмкін амалдары толық баяндалады. Бірінші алгоритм прцессорлер арасындағы матрицаларды жол бойынша бөлуге, ал екінші – матрицаларды бағана бойынша бөлуге, ал үшіншісі- мәліметтерді блоктық бөлуге негізделген. Әрбір алгоритм 4 – ші тақырыпта сипатталған жалпы схемаға сәйкес құрылған., алдымен базалық ішкі тапсырмалар анықталады, содан кейін ақпаратқа қатысты ішкі тапсырмалар ерекшеленеді, ары қарай прцессорлер арасындағы ішкі тапсырмалардың орнласуы мен маштабталуы талқыланады. Аяқталуында әрбір алгоритм үшін паралель есептеулерден алынған нәтижелеу анализі жүргізіледі, және есептелген тәжірибе нәтижелері келтіріледі. Мәліметтерді жол бойынша ленталық бөлудегі матрицаны вектрға көбейту алгоритмдері үшін бағдарламаның орындалу мүмкін нұсқалары келтіріледі.

Алынған нәтижелі көрсеткіштер мәліметтерді бөлуге қолданылған барлық тәсілдер есептеу қиындықтарын біркелкі теңестіруге әкеліп соғады және айыру барысында процессорлар арсында әрекет ететін ақпараттың орындалуын ғана көрсетеді. Бұл қатынаста, таңдалған мәліметтерді бөлу тәсілі мәліметтеді берудің қажет опрецияларының мінездемелеріне қалай әсер ететінін және әр түрлі алгоримтдердің коммуникациялық әрекетіндегі негізгі айырмшылықтарын ерекшелеуді бақылау өте қызықты. Сонымен қатар, паралель алгоритмніің сәйкесінше нәтижелі орындалу үшін, процессорлар арасындағы байланыс сызығының мақсаттық құрылымын анықтау өте мыңызды. Мысалы, мәліметтерді ленталық бөлігіне негізделген алгоритмдер, гиперкуб немесе толық граф түріндегі желі топологиясына бағытталған. Мәліметтерді блоктық бөлуге негізделген алгоритмі жүзеге асуы үшін, тополгиялық торларды иемдену қажет.
6.1 суретіндегі жапы графикте барлық қарастырылған алгоритмдер үшін, есептеу эксперментінің орындалу нәтижесінде алынған жылдамдығының көрсеткіші көрсетілген. Тағы бір ескере кететін жайт, қосымша есептеулерге сүйенсек, саны көп прцессорлар мен көп өлшемді марицалар үшін алгоритмдердің блоктық көбейтінідісі тиімдірек болады.

Сурет 6.1  Қарастырылған алгоритмдердің эксперименттік есептеулер нәтижесі бойынша 2000x2000 матрицасының және 2000 элементің вектрларының жылдамдық көрсеткіші

1. 
   Көлденең жолақта матрицаларды ленталық бөлшектеуге егіделген, паралель алгоритмнің жүзеге асырылуын орындаңыз. Бұл алгоритмнің есептеу жүйесінің қолданған параматрлерін ескере отырып, жұмыс уақытының бағасын құрыңыз. Есептеу экспериментін жүзеге асырыңыз. Бұрын дайындайындалған теориялық бағалаулармен экперименттердің нәтижелерін салыстырыңыз.
   
2. 
   Матрицаларды блоктарға бөлшектеуге нгізделген, паралель алгоритмнің жүзеге асырылуын орындаңыз. Бұл алгоритмнің есептеу жүйесінің қолданған параматрлерін ескере отырып, жұмыс уақытының теориялық бағасын құрыңыз. Есептеу экспериментін жүзеге асырыңыз. Бұрын дайындайындалған теориялық бағалаулармен экперименттердің нәтижелерін салыстырыңыз.
   

Әдебиеттер:

Матрицаларды векторларға көбейту, тапсырмалары паралель бағдарламалаудың мысалын көрсетуде жиі қолданылады және шешімдері әдебиеттерде кең қарастырылған. Қосымша оқу құралы болып, [2, 51, 63] жұмыстары ұсынылады. Матрицалардың паралель орындалу сұрақтары [30] жұмысында толық талқыланады.

Сұрақтарды талқылау кезінде бағдарламалық жүзеге асырудың паралель тәсілдерін қарастыруда [23] жұмыс ұсынылады. Мұнда бәріне мәлім және практикада кең қолданылатын паралель есептеудің бағдарламалаудың сандық кітапханалар тәсілі ScaLAPACK қарастырылған.

1. 
   Матрицаларды көбейту тапсырмасының құрылымы неден тұрады?
   
2. 
   Тапсырмаға Матрицаларды көбейту операциясы қолданылатын мысал келтір.
   
3. 
   Матрицаларды көбейту операциясының орындалу алгоритмдеріне әр түрлі мысал келтіріңдер. Олардың есептеу жұмысы ерекшлене ме?
   
4. 
   Матрицалық көбейтудің паралель алгоритімін өңдеген кезде мәліметтерді бөлудің қай тәсілі қолданылады?
   
5. 
   Қарастырылған матрицаларды көбейту паралель алгоритімінің жылпы схемасын көз алдына елестетіңдер.
   
6. 
   Туынды матрицаларды горизанталь бөлшектеу кезіндегі ленталық алгоритмнің эфектісінің көрсеткішін алып, анализ жаса.
   
7. 
   Мәліметтерді бөлудегі ленталық схемасы бойынша алгоритмдер үшін қандай ақпараттық әрекеттер орындалады?
   
8. 
   Матрицаларды көбейтуде блоктық алгоритмдер үшін қандай ақпарттық әрекеттер орындалады?
   
9. 
   Әрбір қарастырылған алгоритмдер үшін коммуникациялық желінің қай топологиясы мақсатқа жақын болып табылад?
   
10. 
    Қарастырылған алгоритмдердің ішінен қайсысы жады көлемінің қажет аз немесе көп талаптарын сипаттайды?
    
11. 
    Қарасытырылған алгоритмдердің ішіндегі қайсысы жылдамдықтың және эффектіліктік жақсы көрсеткішіне ие?
    
12. 
    Матрицалық көбейтудің орындалу мүмкіндіктерін, матрицаларды векторларға көбейту операциясы бойынша бағалаңыз.
    
13. 
    Фокса алгоритімінің бағдарламалық жүзеге асырылуына жалпы мінездеме беріңіз. Бағдарламалық жүзеге асырылудың басқа қарастырылған алгоритмдерден айырмашылығы неде?
    
14. 
    Бағдарламалық жүзеге асыруда MPI кітапханасының қандай функциялары қажет болды?
    

Тақырыптың қысқаша мазмұны (тезистер):

Берілген дәрісте матрицаларды көбейту операцияларын орындау үшін үш паралель тәсілдер қарастырылған. Бірінші алгоритм процессорлар арасындағы ленталық бөлшектеуге негізделген. Дәрісте бұл алгоритмнің екі тәсілі келтірілген. Алгоритмнің бірінші нұсақасы әр түрлі көбейтілген матрицаларды бөлуге негізделген – бірінші матрица (А матрицасы) горизанталь жолақтарға бөлшектенеді, ал екнші матрица (В матрицасы) вертикаль жолақтарға бөлінеді. Екінші нұсқасы ленталық алгоритм қос матрицаны горизанталь жолақтарға бөлуде қолданылады.

Ары қарай дәрісте кең таралған Фокса және Кэннона алгоритмдері қарастырылады. Матрицаларды бөлудің бірдей схемаларын қолданған кезде берілген алгоритмдер орындалған мәліметтерді беру операциясымен ерекшеленеді. Фокса алгоритімі үшін есептеу кезінде, жіберу және матрица блоктарының циклдік жылжыуы жүзеге асады, ал Кэннона алгоритімінде тек циклдік жылжу операциясы ғана жүзеге асады.

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

7.1 Суреті жалпы графикте барлық қарастырылған алгоритмдер үшін есептеу тәжірибесін орындау кезінде алынға, жылдамдық көрсеткіштері көрсетілген. Орындалған есептеулер мынаны көрсетеді, процесстер көп болған жағдайда матрицаларды көбейтудің блоктық алгоритмдері эффектілеу болады.

1. 
   Матрицаларды көбейтуде екі ленталық алгоритмнің жүзеге асырылуын орындаңыз. Бұл алгоритмдердің орындалу уақытын салыстырыңыз.
   
2. 
   Кэннона алгоритімінің жүзеге асырылуын орындаңыз. Бұл алгоритмнің есептеу жүйесінің қолдану параметірін ескере отырып, жұмыс істеу уақытына теориялық баға бер. Есептеу тәжірибесін жүргізіңдер. Бұрын алныған териялық бағалар мен жүзеге асқан тәжірибелерді салыстырыңдар.
   
3. 
   Матрицаларды көбейтудің тіктөрт ұрышыт процессор торларынң жалпы түрінде де орындалатын блоктық алгоритімінің жүзеге асырылуын орындаңыз.
   
4. 
   Бұрын өңделеген матрицаларды векторларға көбейту бағдарламаларын қолдана отырып, матрицалық көбейтуді жүзе асыруды орындаңыз.
   

Әдебиеттер:

Сұрақтарды талқылау кезінде бағдарламалық жүзеге асырудың паралель тәсілдерін қарастыруда [23] жұмыс ұсынылады. Мұнда бәріне мәлім және практикада кең қолданылатын паралель есептеудің бағдарламалаудың сандық кітапханалар тәсілі ScaLAPACK қарастырылған.

1. 
   Сызықтық теңдеулер жүйесі қандай мағына береді? Қандай жүйе түрлерін білесіңдер? Әр түрлі типтер жүйесін шешу үшін қандай әдістер қолданылуы мүмкін?
   
2. 
   Сызықтық теңдеулер жүйесін шешудің тапсырмалар құрылымы неден тұрады?
   
3. 
   Гаусс әдісін паралель жүзеге асыру идеясы неде?
   
4. 
   Гаусс әдісінің паралель нұсқасы үшін базалық тапсырмалар арасында қандай ақпараттық әрекеттер бар?
   
5. 
   Гаусс әдісінің паралель нұсқасы үшін эфектілік нұсқасы қаншалықты?
   
6. 
   Гаусс әдісінің паралель нұсқасының бағдарламалық жүзеге асыру схемасы неден тұрады?
   
7. 
   Градиенттердің кездесетін әдістерін паралель жүзеге асыру идеясы неден тұрады?
   
8. 
   Алгоритмдердің қайсысының коммуникациялық қиындығы жоғары?
   

Тақырыптың қысқаша мазмұны.

Берілген дәріс сызықтық теідеулер жүйесін шешу кезіндегі, паралель есептеу мәселесіне араналған. Оқу құралының бандалуы кең тараған екі алгоритмдердің қолдануымен жүргізіледі: Гаусс әдісі тапсырманың тура алгоритмдік шешімінің мысалы және кездесетін градиенттердің интерациондық әдісі.

Гаусс әдісінің паралель нұсқасы жолдардың орналасуын циклдік схемасын қолдана отырып, есептеу қиындығын теңестіруге мүмкіндік беретін, процессорлар арасындағы матрицаларды ленталық бөлуге негізделген. Әдістің паралель нұсқасын анықтау үшін, проектілеудің толық цикілі жүргізіледі – базалық тапсырмалар анықталады, ақпараттық әрекеттер ерекшеленеді, маштабталу сұрақатары талқыланады, эффектілік баға көрсеткіштері шығарылады, бағдарламалық жүзеге асыру схемасы ұсынылады және есептеу тәжірибелерінің нәтижесі келтіріледі. 8.8 суретіндегі графиктен көрінгендей Гаусстың паралель алгоритімі жылдамдық пен эффектіліктің жоғарағы көрсеткішін көрсетеді.

Өзін - өзі тексеруге арналған тапсырмалар.

• 
  Гаусс әдісінің тура және кері кезеңдері үшін паралель есептеудің эффектілігіне анализ жасаңдар. Қай кезңде төмен көрсеткіш көрсететінін бағалаңыз.
  
• 
  Матрицаны бағана бойынша вертикаль бөлшетек кезіндегі, Гаусс әдісінің паралель нұсқасын өңдеуді орындаңыз. Есептеу жүйесінің қолану парметрлерін ескере отырып, бұл алгоритмнің жұмыс уақытына териялық бағалаулар құрыңыз. Есептеу тәжірибелерін жүргізіңіз. Орындалған тәжірибе нәтижелерін бұрын алынған теориялық бағалаулармен салыстырыңдар.
  
• 
  Кездескен гардиенттертер әдісімен паралельь жүзеге асыруды орындаңыз. Қолданған есептеу жүйесініңпараметрлерін ескере отырып, жұмыс уақытына теориялық баға беріңіз. Орындалған тәжірибе нәтижелерін бұрын алынған теориялық бағалаулармен салыстырыңдар.
  
• 
  Сызықтың теңдеулер жүйесін шешудің (мысалы, 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] жұмысының құрамында.