Главная страница
Контакты

    Басты бет


Қазақстан Республикасы білім және ғылым министрлігі

жүктеу 438.69 Kb.



жүктеу 438.69 Kb.
бет3/4
Дата30.03.2017
өлшемі438.69 Kb.

Қазақстан Республикасы білім және ғылым министрлігі


1   2   3   4

2.5 Бөлім Паралель алгоритмдердің құрылцы және дамуы
6. Тақырып Матрицаларды векторларға көбейтудің паралель тәсілдері
Дәріс мақсаты: Матрицаларды векторға көбейту тапсырмасын қарастыру. Тапсырманың орындалуын және алгоритмдердің кезектесіп келуін және оның шешімін жүзеге асыру. Матрицалық опреацияларды паралелеь орындау үшін қажет, есептеу жүйесінің прцессоры арасындағы матрицаларды бөлу тәсілін сипаттау. Ары қарай матрицаның векторға көбейту алгоритмінің паралель орындалуына жақын 3 мүмкіндікті қарастыру.
Тақырыпқа сұрақтар:

  1. Есептеу жүйесінің процессорлары арасындағы матрица элементтерінің орналасуының негізгі тәсілдерін атаңыз?

  2. Матрицаны векторға көбейту тапсырмасының мақсат неден тұрады?

  3. Матрицаны векторға көбейтудегі келесі алгоритмін есептеу қиындығы қаншалықты?

  4. Неге матрицаны векторға көбейтудің паралель алгоритімін өңдеген кезде вектор – операндтты барлық процессорға қайталауға рұқсат етіледі?

  5. Матрицаны векторға көбейтудің паралель алгоритімін өңдеу үшін жақындаулар ұсынылады.

  6. Матрицаны векторға көбейтудің паралель алгоритімінің жалпы схемасын көз алдарына елестетіңдер.

  7. Қарастырылған алгоритмдердің біреуіне анализ жасап, олардың нәтижелерің көрсеткішін алыңыз.

  8. Берілген матрицаларды векторға көбейту алгоритмдарының ішнідегі қайсысы жылдам және нәтижелі көрсеткішке ие болып отыр?

  9. Мәліметтерді бөлудің циклдік схемасын қолдану берілген алгоритмдерінің әрбіреунің жұмыс істеу уақытына әсер ете ала ма?

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

  11. Матрицаларды векторларға көбейтудің блоктық алгоритмдері үшн, қандай ақпараттық іс - әрекеттер орындалады?

  12. Қарастырылған алгоритмдер үшін қандай коммуникациялық желі топологиясы мақсатқа лайықты болып саналады?

  13. Мәліметтерді жол бойынша бөлу кезіндегі, матрицаларды векторларға көбейтудің бағдарламалық орындалу алгоритмдеріне мінездеме бер. Бағдарламалық орындалуда басқа қарастырылған алгоритмдердің айырмашылығы неден тұрады?

  14. Бағдарламалық орындалуда MPI кітапханасының қандай функциялары қажет болды?

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

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

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

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

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


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

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

  2. Матрицаларды блоктарға бөлшектеуге нгізделген, паралель алгоритмнің жүзеге асырылуын орындаңыз.

    Блок (лат. block, фр. bloc) - жүк көтергіш машиналардың шеңберінде арқан (трос, жіп, шынжыр) асуға ыңғайлап жасалған ойық белдеуі бар доңғалақ пішінді бөлігі. Оның айналу осі тірекке бекітіледі (жылжымайтын Блок) не кеңістікте орын ауыстырады (жылжымалы Блок).

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

Әдебиеттер:

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



Сурет 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 суретте көрсетілген.


Сурет 8.1  3000x3000 матрица өлшемімен сызықтың теңдеулер жүйесінің паралель алгоритмдер жылдамдығы

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



  • Гаусс әдісінің тура және кері кезеңдері үшін паралель есептеудің эффектілігіне анализ жасаңдар. Қай кезңде төмен көрсеткіш көрсететінін бағалаңыз.

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

  • Кездескен гардиенттертер әдісімен паралельь жүзеге асыруды орындаңыз. Қолданған есептеу жүйесініңпараметрлерін ескере отырып, жұмыс уақытына теориялық баға беріңіз. Орындалған тәжірибе нәтижелерін бұрын алынған теориялық бағалаулармен салыстырыңдар.

  • Сызықтың теңдеулер жүйесін шешудің (мысалы, Kumar (1994) қара) Зейдел және Якоби әдістерінің паралель нұсқасын өңдеуді орындаңыз. Есептеу тәжірибелерін жүргізіңіз. Орындалған тәжірибе нәтижелерін бұрын алынған теориялық бағалаулармен салыстырыңдар.

Әдебиеттер:

Сызықтық теңдеулер жүйесін шешудің сандық мәселесі әдебиеттерде толық қарастырылады. Оқу материалын қарастыру үшін [6, 13, 51, 63] жұмыстары ұсынылады. Берілген типі тапсырмалар үшін паралель есептеу сұрақтарының кең талықылануы [22, 30] жұмысында орындалады.

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





  1. Тақырып Сұрыптаудың паралель әдістері

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


Тақырып бойынша сұрақтар:

  1. Мәліметтерді сұрыптау тапсырмасының құрылымы неден тұрады?

  2. Алгоритмдерді сұраптаудың бірнеше мысалдар келтір. Келтірілген алгоритмдердің қиындығы қаншалықты?

  3. Мәліметтерді сұрыптау тапсырмалары үшін қандай операция базалық болып табылады?

  4. Мәліметтерді сұрыптау тапсырмаларының базалық операцияларын паралель талдаудың мәні неде?

  5. Жұп – жұп емес алгоритмдердің орныны ауыстыру неге әкеледі?

  6. Шелла алгоритімінің паралель нұмқасы неден тұрады? Бұл паралель сұрыптау алгоритімінің жұп емес орын ауыстыру әдісінен негізгі айырмашылықтары қандай?

  7. Жылдам сұрыптау алгоритімінің паралель нұсқасы қандай мағына береді?

  8. Жылдам сұрыптау паралель алгоритімі үшін жүргізілген элементті дүрыс таңдауға не тәуелді?

  9. Жүргізілген элементтерді таңдаудың қандай тәсілдері ұсынылады?

  10. Қарастырылған сұрыптау алгоритмдері қандай топологияларға қолданылуы мүмкін?

  11. Тұрақты таңдау үлгісін қолданған сұрыптау алгоритімі неден тұрады?

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

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

Көпіршіктелген сұрыптау алгоритімі ағымды түрде паралельдеуге мүлдем берілмейді, күштеп келгенде итерация негізгі әдістері орындалады. Қажет паралельдеуді енгізу үшін алгритмнің қрытынды нұсқасы қарастырылған – орын ауыстырудың жұп – жұп емес әдісі. Оның мәнісі мынада, сұрыптау алгоритіміне сұрыптау итерациясының жұп санына қатысты емес, итерациялық әдістің екі әр түрлі орындалу ережесі енгізілген. Итерациядағы реттеу мәінінің жұбын салыстырсақ, жұп – жұп емес әдісінің орнын ауыстыру тәуелсіз болып табылады және паралель орындалуы да мүмкін.



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

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

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

Арифметика (грек. arіthmētіkē, arіthmos – сан) - сандар (бүтін және бөлшек) және оларға қолданылатын амалдар туралы ғылым (грекше arіthmetіke, arіthmos – сан).

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

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

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

  3. Кең тараған сұрыптаудың шағылысу алгоритімі үшін, есептеудің паралель схемасын құрыңыз (әдістің толық сипаттамасын, мысалы, [26] немесе [50] жұмыстарынан алуға болады). Өңделген алгоритмнің жүзеге асырылуын орындаңыз және әдіс күрделілігіне теориялық баға беріңіз.

Әдебиеттер:

Мәліметтерді реттеу тапсырмаларының мүмкін шешімдері мына әдебиеттерде кең тараған; алгоритмдерді сұрыптауға толық шолу [50] жұмыс құрамында, соңғы шыққан баспалардың ішінен [26] жұмыс ұсынылады.

Шелла Сұрыптауы және көпіршіктелген сұрыптау алгоритмдердің паралель нұсқасы [51] қарастырылған.

Гиперкуб түріндегі желі топологиясындағы мәліметтерді берудегі жылдам сұрыптаудың паралель схемасы [51, 63] сипатталған. Үлгілерді тұрақты теруді қолданатын сұрыптау [63] жұмыста көрсетілген.

Мәліметтерді сұрыптау үшін, паралель есептеудің сұрақтарын қарастыруда [17] жұмыстың көп пайдасы тиуі мүмкін.




  1. Тақырып Графтардағы паралель әдістер

Дәріс мақсаты: Графтарды өңдеу кезінде туатын әр түрлі типтік тапсырмаларды қарастыру. Бұл тапсырмалардың шешіміне қолданылатын алгоритмдер келтіру және оларды паралельдеу жлдарын талқылау. Қарастырылған алгоритмдер эффектілігіне теориялық баға беру. Есептелген тәжірибелер нәтижелеріне анализ жасау.

Тақырып бойынша сұрақтар:


  1. Граф анықтамасын келтіріңіз.Графтар тапсырмасы үшін қандай негізгі әдістер қолданылады.

  2. Іздеу тапсырмасының барлық қысқа жолдары неден тұрады?

  3. Флойда алгоритімінің жалпы схемасын келтіріңіз. Алгритмнің жұмыс

1   2   3   4

  • 7. Тақырып. Матрицалық көбейтудің паралель әдістері.
  • 8. Тақырып Сызықтық теңдеулер жүйесін шешу. Дәріс мақсаты
  • Тақырып Сұрыптаудың паралель әдістері
  • Тақырып Графтардағы паралель әдістер

  • жүктеу 438.69 Kb.