Дәріс конспектілері (тезистері) уе-10-20 фр 03
жүктеу/скачать 2,05 Mb.
|
Дәріс мәтіні
- Бұл бет үшін навигация:
- Пайдаланылған әдебиеттер
- 14-Дәріс Тақырыбы : Процесстер мен синхронизациялану. Сұрыптаулар. Жоспар
| Бақылау сұрақтары:
Уақытты есептеу жүйесі және оның өлшем бірлігі. Функционалдық құрылғы (ФҚ). Конвейерлік ФҚ-ның жұмыс істеу принципі. Операцияның бағасы. Конвейердің баспалдақтары (сатылары). Конвейердің ұзындығы. Пайдаланылған әдебиеттер 1. Воеводин Вл. Параллельные вычисления. Санкт-Петербург, 2012 г. 2. Грегори Р. Эндрюс. Основы многопоточного, параллельного и распределенного программирования. Пер. с. англ. –М.: Издательский дом «Вильямс», 2013 г. 3. Акжалова А.Ж. Параллельные вычисления (учебное пособие). – Алматы, 2014 г. 4. Дүйсембиев Е.Е. Параллель есептеулер. Оқулық – Алматы 2011 ж. 4. Гук М. Аппаратные средства IBM PC Әнциклопедия – спб.:«Издательство Питер», 2011 14-Дәріс Тақырыбы: Процесстер мен синхронизациялану. Сұрыптаулар. Жоспар: Аппаратты деңгейдегі синхронизациялану. Программалау тілінің синхронизациясы. Хабарламаларды беру синхронизациясы. Процесстер және синхронизация. Семафорлар. Мониторлар. Процесс операцияның тізбегін орындайды. Оператор бөлінбейтін әрекеттердің тізбегінен орындалады. Бөлінбейтін әрекеттер программаны бөліктерге бөлмей тексереді және өзгертеді. (Мысалы, жадыға сөздерді жүктеу, сақтау – бөлінбейтін іс-әрекеттер). Сонда параллельді программаның орындалуы бөлінбейтін іс-әрекеттер тізбегінің кезектесуіне алып келеді. Бөлінбейтін әрекеттер кезінде бір процесте жүретін кез-келген аралық жағдайды екінші процесс байқамауы керек. Тізбектелген программада меншіктеу операторлары – бөлінбейтін әрекеттер болып табылады. Бірақ, параллельді программада ол бөлінбейтін әрекеттерге жатпайды. Мысалы, төмендегі жағдайда бөлінбейтін әрекет – айнымалыны оқу және жазу: Int y=0, z=0; Parallel: x=y+z; // y=1; z=2; end parallel; Егер x=y+z өрнегі былай алынса: регистрге у мәні жүктеліп және ары қарай z –мәні қосылып отырса, онда х айнымалының ақырлы мәндері 0,1,2,3 болады. Бұл процесте х - у пен z-тің бастапқы, соңғы немесе олардың комбинациясын алып отыр. Процесс операцияның тізбегін орындайды. Оператор бөлінбейтін әрекеттердің тізбегінен орындалады. Бөлінбейтін әрекеттер программаны бөліктерге бөлмей тексереді және өзгертеді. (Мысалы, жадыға сөздерді жүктеу, сақтау – бөлінбейтін іс-әрекеттер). Сонда параллельді программаның орындалуы бөлінбейтін іс-әрекеттер тізбегінің кезектесуіне алып келеді. Бөлінбейтін әрекеттер кезінде бір процесте жүретін кез-келген аралық жағдайды екінші процесс байқамауы керек. Тізбектелген программада меншіктеу операторлары – бөлінбейтін әрекеттер болып табылады. Бірақ, параллельді программада ол бөлінбейтін әрекеттерге жатпайды. Мысалы, төмендегі жағдайда бөлінбейтін әрекет – айнымалыны оқу және жазу: Int y=0, z=0; Parallel: x=y+z; // y=1; z=2; end parallel; Егер x=y+z өрнегі былай алынса: регистрге у мәні жүктеліп және ары қарай z – мәні қосылып отырса, онда х айнымалының ақырлы мәндері 0,1,2,3 болады. Бұл процесте х - у пен z-тің бастапқы, соңғы немесе олардың комбинациясын алып отыр. Сұрыптаудың мынадай алгоритмдері қарастырылады. Ранг әдісімен сұрыптау салыстыру және алмасу сұрыптауы алгоритмдер: ✓ Салыстыру және алмастыру ✓ Көпіршіктер әдісімен сұрыптау (метод пузырка) және «тақ-жұп» сұрыптауы ✓ Біріктіру бойынша сұрыптау ✓ Тез сұрыптау Салыстыру-және-алмастыру әдісімен сұрыптау. Көптеген программаларда сұрыптау кезінде ағымдағы санды басқа санмен орны бойынша алмастыру ақсатында уақытша сақтау үшін базалық айнымалылар пайдаланылады. Ал, параллельді есептеулерде ол сандарды сақтап қоюға процессорларды пайдаланады. if (A>B) temp=A; A=B; B=temp; Көпіршіктер әдісімен сұрыпау. (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(n2). Бұл алгоритмді параллельділікке айналдыру үлкен қиындық келтіреді. Сондықтан бұл әдістің екінші бір түрі «тақ-жұп орын ауыстыру» алгоритмін қарастырайық. «Тақ-жұп орын ауыстыру» алгоритмі. Бұл алгоритмде 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 және p/2 жұп), яғни «салыстыру-бөлу» (compare-split) операциясын орындайды. Сақинадағы процессорлар бір-біріне элементтерін алмастырады. Нәтижесінде әрбір процессорда өз элементтері және көрші процессордың элементтері сұрыпталады да, қайта бөлінеді: сол жақтағы көрші процессор элементтердің бірінші жартысын (кіші элементтерді), оң жақтағы – екінші жартысын (үлкен элементтерді) бөліп алады. Осы фазалар өткен соң тізбек сұрыпталады. Әрбір фаза кезінде екі блокты біріктіру үшін Q(n/p) салыстыру орындалады және Q(n/p) уақыт жұмсалады. жүктеу/скачать 2,05 Mb. Достарыңызбен бөлісу:
|