Дәріс конспектілері (тезистері) уе-10-20 фр 03
жүктеу/скачать 2,05 Mb.
|
- Бұл бет үшін навигация:
- Пайдаланылған әдебиеттер
- 21-Дәріс Тақырыбы : Параллельді алгоритмдер. Жоспар
| Бақылау сұрақтары:
Жадының таратылуы. Массивті-параллель компьютерлер. Операциялық жүйенің тораптары. Тораптың желілік интерфейсі. Есептеу кластерлері. Метакомпьютинг. Пайдаланылған әдебиеттер 1. Воеводин Вл. Параллельные вычисления. Санкт-Петербург, 2012 г. 2. Грегори Р. Эндрюс. Основы многопоточного, параллельного и распределенного программирования. Пер. с. англ. –М.: Издательский дом «Вильямс», 2013 г. 3. Акжалова А.Ж. Параллельные вычисления (учебное пособие). – Алматы, 2014 г. 4. Дүйсембиев Е.Е. Параллель есептеулер. Оқулық – Алматы 2011 ж. 21-Дәріс Тақырыбы: Параллельді алгоритмдер. Жоспар: Параллель алгоритмдерді құру: декомпозиция, коммуникацияны жобалау, ірілендіру. Сұрыптау алгоритмдері. Сұрыптаудың мынадай алгоритмдері қарастырылады. 1. Ранг әдісімен сұрыптау 2. салыстыру және алмасу сұрыптауы алгоритмдер: ✓ Салыстыру және алмастыру ✓ Көпіршіктер әдісімен сұрыптау (метод пузырка) және «тақ-жұп» сұрыптауы ✓ Біріктіру бойынша сұрыптау ✓ Тез сұрыптау Салыстыру-және-алмастыру әдісімен сұрыптау. Көптеген программаларда сұрыптау кезінде ағымдағы санды басқа санмен орны бойынша алмастыру мақсатында уақытша сақтау үшін базалық айнымалылар пайдаланылады. Ал, параллельді есептеулерде ол сандарды сақтап қоюға процессорларды пайдаланады. If (A>B) temp=A; A=B; B=temp; 2. Көпіршіктер әдісімен сұрыпау. (a1 , a2 , ...,an ) сандарының тізбегі берілсін . Сандарды өсу ретімен орналастыру керек, яғни i>j үшін ai 1. procedure BUBBLE-SORT(n) 2. begin 3. for i:=n-1 downto 1 do 4. for j:=1 to i do 5. compare-exchange(aj,aj+1); 6. end BUBBLE-SORT Бұл алгоритмде ішкі цикл итерациясы Q(n) уақытта орындалса және Q(n) итерация жасалса, «көпіршіктер» әдісімен сұрыптауға кететін уақыт - Q(n 2). Бұл алгоритмді параллельділікке айналдыру үлкен қиындық келтіреді. Сондықтан бұл әдістің екінші бір түрі «тақ-жұп орын ауыстыру» алгоритмін қарастырайық. «Тақ-жұп орын ауыстыру» алгоритмі. Бұл алгоритмде n элемент n фазада сұрыпталады. Бұл алгоритмнің жұп және тақ фазалары кезектестіріледі. (a1 , a2 , ...,an) – тізбегін сұрыптау керек болсын. Тақ фаза кезінде тақ индексті элементтер оң жақтағы көрші элементпен салыстырылып, егер шарт орындалса, олар орындарын алмастырады, яғни (a1 , а 2 ), (a3 , a4 ), ..., (an-1 ,an ) жұптары салыстырылып алмастырылады. Сол сияқты жұп фаза кезінде, жұп индексті элементтер салыстырлып, егер шарт орындалса, олар орындарын алмастырады, яғни (а2, a3), (a4 , a5), ..., (an-2 ,an-1) жұптары алыстырылып алмастырылады. Сонда тақ-жұп ауыстыру n фазасынан кейін тізбек сұрыпталады. Әрбір алгоритмнің фазасында Q(n) салыстыру жасалса, барлығы n фаза болса, бұл алгоримтнің (sequential complexity) - Q(n 2 ). Программа 2. "тақ-жұп орын ауыстыру" тізбекті алгоритмі. 1. procedure ODD-EVEN(n) 2. begin 3. for i:=1 to n do 4. begin 5. if i is odd then 6. for j:=0 to n/2-1 do 7. compare-exchange(a 2j+1 , a2j+2 ) 8. if i is even then 9. for j:=1 to n/2-1 do 10. compare-exchange(a 2j ,a 2j+1 ) 11. end for 12. end ODD-EVEN Мысалы, n = 8 элементті «тақ-жұп орын ауыстыру» әдісімен сұрыптау керек. Әрбір фазада n = 8 элемент сұрыпталады. Енді осы «тақ-жұп» алгоритмді параллельділікке көшірейік. Бұл жағдайда алгоритмнің әрбір фазасы кезінде элементтердің жұбын салыстыру-алмастыру операциясы бірмезгілде орындалады. Процессорлар сақиналы желімен байланысқан болсын. ai элементі бастапқыда Рi процессорда болсын, тақ фаза кезінде, тақ номерлі процессордағы элемент оның оң жағында орналасқан процессордағы элементпен салыстыру-алмастыру процесі жүреді. Сол сияқты процесс жұп фаза кезінде де орындалады. Программа 3. n-процессорлы сақинада орындалатын "тақ-жұр орын ауыстыру" тәсілінің параллельді алгоритмі. 1. procedure ODD-EVEN-PAR(n) 2. begin 3. id := processor's label 4. for i:= 1 to n do 5. begin 6. if i is odd then7. if id is odd then 7. compare-exchange_min(id+1); 8. else 9. compare-exchange_max(id-1); 10. if i is even then 11. if id is even then 12. compare-exchange_min(id+1); 13. else 14. compare-exchange_max(id-1); 15. end for 16. end ODD-EVEN_PAR Әрбір фазада орындалатын қадамдарға Q(1) уақыт кетеді. Барлығы n фаза болса, параллельді алгоритмнің орындалуына Q(n) уақыт кетеді екен. Параллельді әдіске қысқаша сипаттама p – процессорлар саны, n – сұрыпталатын тізбектің ұзындығы, мұндағы p тағайындалады, ол бұл элементтерден іштей Q((n/p)*log(n/p)) уақытта сұрыптап шығады. Мұнан кейін процессорлар р фазыдан өтіп шығады (p/2 тақ және p/2 жұп), яғни «салыстыру-бөлу» (compare-split) операциясын орындайды. Сақинадағы процессорлар бір-біріне элементтерін алмастырады. Нәтижесінде әрбір процессорда өз элементтері және көрші процессордың элементтері сұрыпталады да, қайта бөлінеді: сол жақтағы көрші процессор элементтердің бірінші жартысын (кіші элементтерді), оң жақтағы – екінші жартысын (үлкен элементтерді) бөліп алады. Осы фазалар өткен соң тізбек сұрыпталады. Әрбір фаза кезінде екі блокты біріктіру үшін Q(n/p) салыстыру орындалады және Q(n/p) уақыт жұмсалады. жүктеу/скачать 2,05 Mb. Достарыңызбен бөлісу:
|