«параллельді есептеулер» ПӘнінің ОҚУ-Әдістемелік кешені



бет2/3
Дата03.07.2016
өлшемі1.29 Mb.
#173708
1   2   3

Бақылау сұрақтары

  1. Қандай параллель компьютерлер бар?

  2. Ортақ жадылы процессорлер не үшін қолданылады?

  3. Флинн таксономиясы неше бөлімнен тұрады?


Әдебиеттер

  1. Воеводин Вл. Параллельные вычисления. Санкт-Петербург, 2002

  2. Грегори Р. Эндрюс. Основы многопоточного, параллельного и распределенного программирования. Пер. с. англ. –М.: Издательский дом «Вильямс», 2003

  3. Акжалова А.Ж. Параллельные вычисления (учебное пособие). –Алматы, 2004

  4. Немнюгин С.А., Стесик О.Л. Параллельное программирование для высокопроизводительных многопроцессорных систем – СПб., 2002


Дәріс 6-7. Есептеуіш жүйелер процессорларының мәлімет алмасу желісінің топологиясы. Амдал заңы. Густафсон заңы
Мақсаты: Студенттерді параллель программалаудағы топология принципімен таныстыру
Кілттік сөздер: желі, топология, Амдал заңы, жұлдызшалы топология, сақиналы топология, тізбектелген топология, Густафсон заңы
Жоспары

1. Параллель программалауды тиімді бағалау

2. Амдал заңы

3. Густафсон заңы


1. Есептеуіш жүйелер процессорларының мәлімет алмасу желісінің топологиясы.

1. Топология түрлері.

2. Желі топологиясына сипаттама.

3. Амдал заңы.

4. Процесстер және синхронизация

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

Топология түрлері:


  1. Толық граф немесе толық байланысқан желі – кез-келген екі процессор түзу сызықты желімен байланысады. Бұл топологияда мәліметтер берілу жағдайында шығын көлемі аз болады, бірақ процессорлар саны көбейген сайын, жұмыс істеу қабілеті баяулайды.




  1. толық граф 2) сызықты 3) сақина 4) жұлдызша




  1. екі және үш өлшемді 6) гиперкуб




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

  2. Сақиналы топология – сызғыш тәрізді топологиядағы бірінші және соңғы процессорды байланыстыру нәтижесінде пайда болады.

  3. Жұлдызша тәрізді топология – процессорлар жиыны басқарушы процессормен бір сызықпен байланысады, (кейбір параллель есептеулерде қолданылады).

  4. Торлы топология (екі және үш өлшемді) - бұл жүйе тіктөртбұрыштан тордан тұрады (математикалық модельдеуден, дифференциалдық теңдеулерді шешуде).

  5. Топологияның тағы бір түрі –гиперкуб (торлы топологияның жеке жағдайы). Бұл топология параллельді есептеулер орындалатын процессорларда қолданылады.

Оның түрлері:

-прямая соединительная линия 11 бірөлшемді куб – түзумен байланысқан екі түйін.

- екіөлшемді куб – төрттүйінді квадрат.

үшөлшемді куб – сегіз түйінді куб.



Яғни, N желімен байланысқан 2 n процессорлардан тұрады. Енді осы мәліметтер берілу желісі топологиясының сипаттамаларын беру үшін мынадай көрсеткіштер прайдаланылады:



  1. Желі диаметрі – кез-келген екі түйіннің арасын байланыстыратын ең ұзын жол. Бұл шама процессорлар арасындағы мәліметтер берілуінің максимальді уақытын сипаттайды. Себебі, мәлімет берілу уақыты жол ұзындығына тура пропорциональды. N түйінді сақиналардың диаметрі n/2 деп есептелінеді. Ал толық байланысқан желінің диаметрі 1-ге тең (түйіндер санына тәуелсіз) деп есептеледі.

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




Топология

Диаметр

Ені

Бисекцилық байланысы

Есептеу құны

Толық граф

1

p2 /4

p - 1

p(p-1)/2

Жұлдызша тәрізді

2

1

1

p-1

Толық екілік ағаш

2log((p+1)/2)

1

1

p-1

Сызғыш тәрізді

p-1

1

1

p-1

Сақиналы

[p/2]

2

2

p

N=2

-1)



2



Гиперкуб

log p

p/2

log p

(p log p)/2

Амдал заңы. Параллельді есептеулерді модельдеу

Параллельді есептеулер сапасына мына көрсеткіштер әсер етеді:


  1. Есептеудің жедел орындалуы.

  2. Есептелу тиімділігі.

  3. Есептелу құны.

  4. Есептелу көлемі.

Есептелудің жедел орындалуы (speedup) мына шамамен анықталады:


p – процессорлар саны
Есептелудің тиімділігі мына шамамен анықталады:


p-процессорлар саны
Есептелу құнының пайдалы бағасы – параллельді есептелетін уақыттың процессорлар санына көбейтіндісін айтамыз.

 р- процессорлаp саны

Мысалдар келтірейік:

1-мысал. «Операциялар-операндтар» графы түрінде есептеу моделі. Есептеу моделін жеңілдету үшін, есептеу барысындағы кез-келген есептеу операциясына кететін уақытты бірдей және 1-ге тең деп қабылдаймыз (өлшем бірлігін өз бетімізше аламыз).

Мынадай есеп қойылсын: Қарама-қарсы бұрыштарының координаттары берілген тіктөртбұрыштың ауданын есептеудің алгоритмін граф түрінде көрсетейік.

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

2-мысал. Сандардың қосындысын табу алгоритмдерін қарастырайық.

n- қосындылардың саны.

Бұл есепті шешудің параллельді әдісін бастамас бұрын алдымен қарапайым жағдайды қарастырамыз, яғни

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

S=0,

S=S+x1,...



Бұл алгоритмді тізбектеп есептеу схемасы мынадай:


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

Мұндағы итерациялардың саны: k=log2 n,

Ал, қосу операцияларының саны K посл =n/2+n/4+...+1=n–1
Процесстер және синхронизация. Семафорлар. Мониторлар.

Процесс операцияның тізбегін орындайды. Оператор бөлінбейтін әрекеттердің тізбегінен орындалады. Бөлінбейтін әрекеттер программаны бөліктерге бөлмей тексереді және өзгертеді. (Мысалы, жадыға сөздерді жүктеу, сақтау – бөлінбейтін іс-әрекеттер). Сонда параллельді программаның орындалуы бөлінбейтін іс-әрекеттер тізбегінің кезектесуіне алып келеді.

Бөлінбейтін әрекеттер кезінде бір процесте жүретін кез-келген аралық жағдайды екінші процесс байқамауы керек. Тізбектелген программада меншіктеу операторлары – бөлінбейтін әрекеттер болып табылады. Бірақ, параллельді программада ол бөлінбейтін әрекеттерге жатпайды. Мысалы, төмендегі жағдайда бөлінбейтін әрекет – айнымалыны оқу және жазу:

Int y=0, z=0;

Parallel: x=y+z; // y=1; z=2; end parallel;

Егер x=y+z өрнегі былай алынса: регистрге у мәні жүктеліп және ары қарай z –мәні қосылып отырса, онда х айнымалының ақырлы мәндері 0,1,2,3 болады. Бұл процесте х - у пен z-тің бастапқы, соңғы немесе олардың комбинациясын алып отыр.



Бақылау сұрақтары

1. Параллель есептеулер сапасына қандай көрсеткіштер әсер етеді?

2. Есептеудің жедел орындалуы қандай шамамаен есептеледі?

3. Семофорлар, мониторлар дегеніміз не?


Әдебиеттер

1. Воеводин Вл. Параллельные вычисления. Санкт-Петербург, 2002   600с.

2. Грегори Р. Эндрюс. Основы многопоточного, параллельного и распределенного программирования. Пер. с. англ. –М.: Издательский дом «Вильямс», 2003. – 512с.

3. Акжалова А.Ж. Параллельные вычисления (учебное пособие). –Алматы, 2004


Дәріс 8. Процесстер және синхронизация. Семафорлар. Мониторлар
Мақсаты: Студенттерді параллель программалаудағы амалдардың орындалу принципімен таныстыру
Кілттік сөздер: процесстер, семафорлар, мониторлар.
Жоспары: Процесстер және семафорлар
Процесс операцияның тізбегін орындайды. Оператор бөлінбейтін әрекеттердің тізбегінен орындалады. Бөлінбейтін әрекеттер программаны бөліктерге бөлмей тексереді және өзгертеді. (Мысалы, жадыға сөздерді жүктеу, сақтау – бөлінбейтін іс-әрекеттер). Сонда параллельді программаның орындалуы бөлінбейтін іс-әрекеттер тізбегінің кезектесуіне алып келеді.

Бөлінбейтін әрекеттер кезінде бір процесте жүретін кез-келген аралық жағдайды екінші процесс байқамауы керек. Тізбектелген программада меншіктеу операторлары – бөлінбейтін әрекеттер болып табылады. Бірақ, параллельді программада ол бөлінбейтін әрекеттерге жатпайды. Мысалы, төмендегі жағдайда бөлінбейтін әрекет – айнымалыны оқу және жазу:

Int y=0, z=0;

Parallel: x=y+z; // y=1; z=2; end parallel;

Егер x=y+z өрнегі былай алынса: регистрге у мәні жүктеліп және ары қарай z –мәні қосылып отырса, онда х айнымалының ақырлы мәндері 0,1,2,3 болады. Бұл процесте х - у пен z-тің бастапқы, соңғы немесе олардың комбинациясын алып отыр.
Бақылау сұрақтары

1. Топологияның қандай түрлері бар?

2. Процесстер дегеніміз не?

3. Семофорлар, мониторлар дегеніміз не?


Әдебиеттер

  1. Воеводин Вл. Параллельные вычисления. Санкт-Петербург, 2002

  2. Грегори Р. Эндрюс. Основы многопоточного, параллельного и распределенного программирования. Пер. с. англ. –М.: Издательский дом «Вильямс», 2003

  3. Акжалова А.Ж. Параллельные вычисления (учебное пособие). –Алматы, 2004

  4. Немнюгин С.А., Стесик О.Л. Параллельное программирование для высокопроизводительных многопроцессорных систем – СПб., 2002



Дәріс 9-11. Параллельді алгоритмдер. Сұрыптаулар (ранг, көпіршіктер әдістері)
Мақсаты: Студенттерді параллель программалаудағы мәліметтер ағынын сұрыптаудың әдістеріне үйрету
Кілттік сөздер: сұрыптау, көпіршіктер әдісі, ранг әдісі, тақ-жұп әдісі, мәліметтер, алгоритмдер, программа, салыстыру және алмастыру, біріктіріп сұрыптау, тез сұрыптау.

Жоспары:

1. Көпіршіктер әдісімен сұрыптау.

2. Тақ-жұп әдісімен сұрыптау.
Сұрыптаудың мынадай алгоритмдері қарастырылады.

1. Ранг әдісімен сұрыптау

2. салыстыру және алмасу сұрыптауы алгоритмдер:


  • Салыстыру және алмастыру

    • Көпіршіктер әдісімен сұрыптау (метод пузырка) және «тақ-жұп» сұрыптауы

    • Біріктіру бойынша сұрыптау

    • Тез сұрыптау


1. Салыстыру-және-алмастыру әдісімен сұрыптау

Көптеген программаларда сұрыптау кезінде ағымдағы санды басқа санмен орны бойынша алмастыру мақсатында уақытша сақтау үшін базалық айнымалылар пайдаланылады. Ал, параллельді есептеулерде ол сандарды сақтап қоюға процессорларды пайдаланады.

if (A>B)

temp=A; A=B; B=temp;


2. Көпіршіктер әдісімен сұрыпау

(a1 , a2 , ...,an ) сандарының тізбегі берілсін . Сандарды өсу ретімен орналастыру керек, яғни i>j үшін ai j



Программа 1. «Көпіршіктер» әдісімен сұрыптаудың тізбекті алгоритмі.

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 ). Бұл алгоритмді параллельділікке айналдыру үлкен қиындық келтіреді.

Сондықтан бұл әдістің екінші бір түрі «тақ-жұп орын ауыстыру» алгоритмін қарастырайық.


3. «Тақ-жұп орын ауыстыру» алгоритмі.

Бұл алгоритмде 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 элемент сұрыпталады.





Сұрыпталмаған

Сұрыпталған

Фаза 1 (тақ)

Фаза 2 (жұп)

Фаза 3 (тақ)

Фаза 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Бастапқыда, әрбір процессор үшін n/p элементтен тұратын блок тағайындалады, ол бұл элементтерден іштей Q((n/p)*log(n/p)) уақытта сұрыптап шығады. Мұнан кейін процессорлар р фазыдан өтіп шығады (p/2 тақ және p/2 жұп), яғни «салыстыру-бөлу» (compare-split) операциясын орындайды. Сақинадағы процессорлар бір-біріне элементтерін алмастырады.

Нәтижесінде әрбір процессорда өз элементтері және көрші процессордың элементтері сұрыпталады да, қайта бөлінеді: сол жақтағы көрші процессор элементтердің бірінші жартысын (кіші элементтерді), оң жақтағы – екінші жартысын (үлкен элементтерді) бөліп алады. Осы фазалар өткен соң тізбек сұрыпталады. Әрбір фаза кезінде екі блокты біріктіру үшін Q(n/p) салыстыру орындалады және Q(n/p) уақыт жұмсалады.
Бақылау сұрақтары

1. Сұрыптаудың қандай түрлері бар?

2. Ранг әдісімен сұрыптау дегеніміз не?

3. Көпіршіктер әдісімен сұрыптаудың ерекшелігі?


Әдебиеттер

  1. Воеводин Вл. Параллельные вычисления. Санкт-Петербург, 2002

  2. Грегори Р. Эндрюс. Основы многопоточного, параллельного и распределенного программирования. Пер. с. англ. –М.:Издательский дом «Вильямс», 2003

  3. Акжалова А.Ж. Параллельные вычисления (учебное пособие). –Алматы, 2004

  4. 4. Немнюгин С.А., Стесик О.Л. Параллельное программирование для высокопроизводительных многопроцессорных систем – СПб., 2002



12-13- дәріс

Тақырыбы: Параллель программалау. Ағындар және мәліметтерді өңдеу. Параллель программалау тілдері: HPF және C++ тілінің кеңеймелері, Fortran 90. PVM, MPI, OpenMP қолданып, үлестірілген мәліметтерге енуді құру.

Мақсаты: Студенттерді параллель программалауда қолданылатын тілдермен және программалармен таныстыру.

Кілттік өздер: PVM, MPI, Fortran (HPF), автопараллелизациялау, кітапханалар, тілдер кеңеймесі, тізбектелген тілдер, параллель виртуал машина, ХPVM, хабарламаларды беру интерфейсі.

Жоспары:

1. PVM – параллель виртуал машинасы;

2. MPI - хабарламаларды беру интерфейсі;

3. Тез әсер ететін Fortran (HPF).


1. Автопараллелизациялау циклдің өзімен шектеледі, қайта реттелген цикл болуы мүмкін, бұл кезде мәліметтерден тәуелділік мәселесі туындауы мүмкін, соның ішінде ішкі программаға сұраныстардан. Параллель программалау кезінде тізбекті архитектураны қоса, платформааралық мобильділікті қостайтын коментарий ретіндегі компилятор дерективалары қолданылады. Сонымен қатар, кітапханалар, қажет тізбектелген тілдер кеңеймесі: PVM, MPI қолданылады. Хабарламаларды беру моделіне жататын PVM – нің (Parallel Virtual Machine) қарастырайық.

Параллель виртуал машинаны есептеудің жалпы нәтижесін алу үшін қатысатын көптеген есептерді орындауға арналған нақты есептеу кешенінің (процессорлар, жады, қосалқы құрылғылар және т.б.) құралы ретінде анықтауға болады. Жалпы жағдайда есептер саны PVM-ге қосылған процессорлар санынан асып кетуі мүмкін.PVM – нің қызмет атқаруы онда орындалып жатқан есептер арасындағы ақпаратпен алмасу мүмкіндігіне сүйенеді.

PVM – ді қолданудың негізгі мақсаты – есептеу жылдамдығын олардың параллель орындалуы есебінен арттыру.

PVM – мен қоса осы модельдің графикалық интерфейсі де – ХPVM жасалып шықты. ХPVM процесстердің жүйелеу уақытын, күту уақытын, хабарламаларды жіберу мезетін визуальді бақылауға мүмкіндік береді.


2. МРІ – хабарламаларды беру интерфейсі.

МРІ (Message Passing Interface) параллель программалаудың ең ерте шыққан құралы болып есептеледі. МРІ кітапханасын қолдaну кезінде үлестірілген программалар процесстері С және Fortran тізбектелген тілдерінде азылады. Процесстердің өзара байланысы мен олардың синхронизациясы МРІ кітапханасының процедураларын шақыру көмегімен беріледі.

МРІ программалауының интерфейсін – 90 жылдардың ортасында университет, мемлекет және өнеркәсіптік мекемелердің өндірушілері тобы жасап шығарды. Оның мақсаты әртүрлі көппроцессорлы машиналарда тиімді жүзеге асыруға болатындай бірыңғай кітапхана жасап шығару болды.

МРІ кітапханасын қолданатын программа SPMD стилінен тұрады (Флинн таксономиясын қараңыз). Мұнда әрбір процесс бір программаның көшірмелерін орындайды. Программаның әрбір экземпляры өзіндік экземплярды анықтай алады. Демек, әртүрлі әрекеттер жасай алады.



3. Тез әсер ететін Fortran (HPF).

Тез әсер ететін Фортран (High Perfomance Fortran) – бұл Фортранға негізделген тілдер тобының ең жаңа мүшесі. HPF-тің ең алғашқы нұсқасы 1992 жылы жасалды. Екінші нұсқасы 1997 жылдың басында жарияланды. Бірнеше компиляторлары қазіргі кезде де бар, ал HPF – программалар тез әрекет ете алатын машиналардың қазіргі түрлерінде де орындала алады.

HPF - бұл мәліметтер бойынша параллель тіл. Ол массивтер және олардың бөліктерінің бірнеше амалдарын қолдайтын Фортран 90 тілінің кеңеймесі болып табылады. HPF проектісіне, мәліметтер бойынша параллель Фортранның ерте диалектісі Фортран 90 тілі әсер еттті.

HPF–тің негізгі компоненттері: массивтерді меншіктеудің мәліметтерінің параллельділігі, мәліметтерді үлестіруді басқарудың компиляторы және параллель циклдарды синхронизациялау және жазу операторлары.


Бақылау сұрақтары

1. PVM- ді қолдаднудың негізгі мақсаты?

2. МРІ кітапханасын қолданатын программаны атаңыз

3. НРҒ мен Фортран тілінің арасында қандай байланыс бар.


Әдебиеттер

  1. Воеводин Вл. Параллельные вычисления. Санкт-Петербург, 2002

  2. Грегори Р. Эндрюс. Основы многопоточного, параллельного и распределенного программирования. Пер. с. англ. –М.: Издательский дом «Вильямс», 2003

  3. Акжалова А.Ж. Параллельные вычисления (учебное пособие). –Алматы, 2004

  4. Немнюгин С.А., Стесик О.Л. Параллельное программирование для высокопроизводительных многопроцессорных систем – СПб., 2002


14- дәріс

Тақырыбы: Ғылыми есептерді шешудің параллель алгоритмдерінің

қосымшалары.

Мақсаты: Параллель программалаудың ғылыми есептерде де, қолданбалы есептерде де қолданылатынын көрсету.

Кілттік сөздер: графитациялық есеп, тізбектелген алгоритм, параллель алгоритм, Барнс және Нат, N – дене, үшөлшемді кеңістік.

Жоспары:

1. N – дененің гравитациялық есебі

2. N – дененің гравитациялық есебінің тізбектелген коды
1. N – дененің гравитациялық есебі

N – дене есебі «денелер» арасындағы күштердің өзара әсерін анықтаудан тұрады (мысалы, тартылыс күштері кқмегімен өзара әсерлесетін астрономиялық денелер). N – дене есебі молекулярлық динамика мен сұйық динамикасын қоса, басқа облыстарда да пайда болады. Мұнда есептер астрономиялық жүйелер терминімен зерттеледі. N – денелердің гравитациялық есебі. Бұл берілген есептің мақсаты-Ньютон физикасы заңына бағынатын басқа денелердің гравитациялық күшінен тәуелді кеңістіктегі денелердің қозғалысы мен позициясын табу.

Массалары m a және m b болатын денелер арасындағы гравитациялық күш сәйкесінше келесі формуламен берілген:

мұндағы G – гравитациялық тұрақты, r-денелер арасындағы ара-қашықтық. Көріп отырғанымыздай, дене жұптары арасындағы күш пропорционал. 1/ r 2

Ньютонның екінші заңы бойынша

мұндағы m – дене массасы, F – оған әсер ететін күш, ал а- үдеу нәтижесі. Нақты сандық сипаттамасын беру үшін дифференциалдық теңдеуді қолданған жөн:



мұндағы v – жылдамдық.

Үшөлшемді кеңістік.

Дене үшөлшемді кеңістікте болғандықтан, барлық вектор- мәндер үш бағытта x,y және z есептелуі керек. (x,y,z) координаталы үшөлшемді кеңістікте (xа, yа, zа ) және (xb, yb, zb) болғандағы денелер арасындағы ара – қашықтық келесі формуламен берілген:




Күш осы үш бағытта есептеледі:

Fx =((G m a m b ) / r 2)((x b -x a ) /r),

F x =((G m a m b ) / r 2)((y b -y a ) /r),

F x =((G m a m b ) / r 2)((z b -z a ) /r).
2. Тізбектелген коды:

N- денелер гравитациясының барлық есептеулері келесі алгоритммен сипатталуы мүмкін

For (t=0; t

For (i=0; i

{

F= Force_routine(i);



V[i]=v[i]+F*dt;

}

For (i=0; i

{

X[i]=x[i];

V[i]=v[i];

}

Параллель коды

Алгоритмнің тізбектелген кодын параллельдеу үшін әрбір процессорге арналған денелер тобын қолдануы мүмкін. Алгоритм шамамен процессорлардың О(N2 ) әрекетін алады.

Есептеу уақыты келесі бақылауды қолданғандықтан аяаюы мүмкін: N-дене кластері кластер массасының ортасында орналасқан толық массалы жеке қашықтықтағыдай жуықталуы мүмкін.



Барнс және Нат алгоритмі

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

Жапырақ ұяшықты береді, оның әрқайсысында бір денеден болады. Екі өлшемді есеп үшін, әрбір рекурсивті бөлім төрт ішкі облыстан тұрады да, шаршыағаш құрады.

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



Бақылау сұрақтары

1. N – дене есебі неден тұрады?

2. N – дене есебінің тізбектелген кодын келтіріңіз

3. N – дене есебінің параллель алгоритмін келтіріңіз.


Әдебиеттер

  1. Воеводин Вл. Параллельные вычисления. Санкт-Петербург, 2002

  2. Грегори Р. Эндрюс. Основы многопоточного, параллельного и распределенного программирования. Пер. с. англ. –М.: Издательский дом «Вильямс», 2003.



15-дәріс.

Тақырыбы: Кескіндерді өңдеу. Төменгі, ортаңғы және жоғарғы деңгейлерде кескіндерді өңдеу түрлері. Фурье түрлендіруі және Фурье алгортимдері

Мақсаты: Кескіндерді параллель өңдеу, соның ішіне Фурье түрлендіруін қолданып, өңдеу әдісін үйрету

Кілттік сөздер: кескін, төменгі деңгей, Фурье түрлендіруі, Фурье алгоритмі, ортаңғы деңгей, жоғарғы деңгей, пиксель.

Жоспары:

1. Кескіндерді өңдеудің төменгң деңгейі

2. Кескіндерді өңдеудің Фурье түрлендіруі
Кескіндерді өңдеудің төменгі деңгейі кескінді дұрыстау үшін және адам мен компьютер оны тануы үшін сақталған кескінге тікелей әсер етеді. Кескіндерді бұлай өңдеу көптеген облыстарда, соның ішінде, медициналық диагностикада, ішкі істердегі бармақ ізін тануда, өндірістік өнімдердегі ақауларды табу үшін және киноиндустрияда қолданылады. Басында кескін камераға түсіріліп, цифрлық түрде сақталынады. Сақталға кескін екіөлшемді пиксельдер массивінен тұрады. Кескін монохромды деп алып, сұр түсті пиксельдерге хабарлама жібереді. Кескін түсі әрқайсысы үш қарапайым түстің реңі болып табылатын үш мәнді (қызыл, жасыл, көк) қолданады. Біз сақталған кескін сол жақ жоғары бұрыштан басталтын қарапайым координаталар жүйесін қолданады деп болжаймыз. Кескін пиксельдері екі өлшемді массивте сақталады да, оның элементтерін p[i][j] деп белгілеп аламыз және әрбір пиксельдің интенсивтілігі берілген массивтен табылады. Өңдеудің төменгі деңгейі әрбір пиксельдің мәнін кескінді қандай да бір тәсілмен модификациялау үшін қолданылады. Көп жағдайда мұндай амалдар параллель орындалады. Кей кездері пиксельдер идентификацияланатын тік сызықтар немесе қисықтармен ассоцияцияланады. Идентификацияның ең тиімді тәсілі Hough түрлендіруін қолдану. Hough түрлендіруі пиксель координаталарын сызық теңдеуіне жақын тәуелділік теңдеуін анықтау үшін қолданылады.

Есептерге қойылатын талаптар.

Әректтің басында өңдеудің төменгі деңгейінде параллель өңдеуді қолданудың маңыздылығын айта кеткен жөн. Айталық, кескін 1024×1024пиксельден тұрады делік, мүндай пиксельдер картасымен және пиксельге 8 битпен сақтау өте қажет.

Ең критикалық фактор – есептеу жылдамдығы. Айталық, әрқайсысы тек бір рет қана өңделеді делік. Онда тек қаңқасының өзіне ғана 210 операциялар қажет. Қазіргі кезде барлық компьютерлер мүндай әрекет жасай алмайды. Нақты уақыт режимінде қосымшалар үшін есептеу шамамен секундына 60-85 каркас болуы керек. Чиптерді сигналды өңдейтін арнайы аппараттық қамсыздандыру ойлап табылды. Бірақ мұндай жүйелер параллель компьютерлер сияқты икемді емес.

Теңдеуі

Берілген өңдеудің бір деңгейінде қандай да порогты пиксельдер мәні

сақталады, ал оден төмен басқалары 0 мәнін қабылдайды. Мысалыға, х мәнді пиксель берілсін, онда пиксельге орындалатын амал:

If (x< threshold) x=0; else x=1;


Контрастпен жұмыс

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



Сұр түс деңгейін азайту.

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



Параллель орындалуы.

Айталық бір процессор бір пиксельге тіркелген делік. Тура параллель орындалу әрбір процессорден бір уақытта орындалып жатқан әрбір процессорден 9 қадам орындауды талап етер еді. Мұнда барлық хабарлау тек оқу болғандықтан мәліметтер ену қарама – қайшылығы болмайды.

Нүкте мәндерін орталандырудың параллель нұсқасы төрт қадамнан тұрады:

Қадам 1. Әрбір процессор өзінің сол жағындағы пиксельдер санын алып, мәндерді өзі сақатап жатқан пиксельдер санына қосады.

Қадам 2. Әрбір процессор өзінің оң жағындағы пиксельдер мәнін алады да, жиналып жатқан сомаға қосады.

Қадам 3. Әрбір процессор төменнен жиналған мәндер жиынын екінші қадамдағыдан алып тастап, осы мәнді өзінің жиналған мәндеріне қосады. Ол сонымен қатар, келесі қадам үшін жиналған соманың ағымдағы мәнін сақтап қалу керек.

Қадам 4. Әрбір процессор үстінен жиналған мәндер жиынын екінші қадамдағыдан алып тастап, осы мәнді өзінің жиналған мәндеріне қосады. Және, ақырында, әрбір процессор жиналған мәндерін ортақ мәнді табу үшін 9-ға бөледі. Сонда әәрбір процессорда төрт қосу байланысы және бір бөлу болады.

2.Кескіндерді өңдеудің Фурье түрлендіруі.

Кескіндерді өңдеу есебінің кең көлемі әртүрлі облыстарда жасалынды. Дискретті Фурье түрлендіруінің бір қолданылуы тегістеуде де үшкір шеттерді табуда да қолданылатын фильтрлеу. Фильтрлеу төмендегі екі функцияны салыстырып есептеу көмегімен жүзеге асырылады:



H(j,k)=G(j,k)xF(j,k)

мұндағы F(j,k) – бұл f(j,k) Фурье функциясының түрлендірілуі, ал G(j,k)(g(j,k ) Фурье функциясының түрлендірілуі. (j,k – х пикселінің координаталары).

Фурьенің дискретті түрлендірілу функциясы:

Хк =1/N∑хj e-2π(jk/n)

мұндағы хi N пиксельдер мәні, i- комплестік сан.

және Фурьенің кері түрлендіруі

хк =1/N∑Хj e-2π(jk/n).

Практикада көбіне формуланы 1/N көпмүшесіз қолданады.

Сондықтан, әрі қарай біз бұл көпмшені түсіріп тастаймыз.



w=e -2πi/N

деп белгілейік.

Сонда формула мына түрде болады:

Хк =∑хj wjk)

болады.


Берілген формуланы жүзеге асырудың тізбектелген коды келесі түрде болады:

For (k=0; k

{ X[k]=0

For (j+0; j

X[k]=X[k]+a*X[j];

a=a*pow(w,k);

}
Бақылау сұрақтары


  1. Фурье әдісі не үшін қолданылады?

  2. Фурьенің дискреттң түрлендіру әдісі қандай?

  3. Параллель орындалу неше қадамнан тұрады? Атаңыз.


Әдебиеттер:

  1. Воеводин Вл. Параллельные вычисления. Санкт-Петербург, 2002

  2. Грегори Р. Эндрюс. Основы многопоточного, параллельного и распределенного программирования. Пер. с. англ. –М.: Издательский дом «Вильямс», 2003.

1-4 Зерханалық жұмыс



Параллель программалау. С++ тілінің кеңеймесін қолдана отырып, параллель алгоритмдерге программалық код құру
Жұмыстың мақсаты: Параллельді есептеулер, параллельді компьютерлер, параллельді программалау, сұрыптаудың параллельді алгоритмдері түсініктерімен танысу.

Материалдар және жабдықтар: ДК, параллельді есептеулер программалау ортасы, ПараЛаб программалау жүйесі.

Жұмыстың мазмұны және орындалу тәртібі:

Параллель компьютер дегеніміз – есепті сандық түрде шешіп, үйлесімді шешуге қабілетті процессорлардың жиынтығы.

Параллельді программа – бұл әр процесс өзінің меншікті процессорныда жүріп қана қоймай, параллель орындалатын программа.

Параллельді компьютерлер мен параллельді есептеулер қолданылатын облыстарға тоқталсақ:


  • күрделі жүйені сандық модельдеуде: ауа-райын болжау, гендік инженерия, интегралдық схеманы жобалау, жаңалықтар, кезекті космосқа ұшырылу туралы жедел хабар, т.б.

  • бизнесте, коммерциялық салада: видеоконференциялар, параллель мәліметтер қоры, банктік транзакция, т.б.

  • техникада: медицина саласында, автоматты түрде диагноз қою, жер сілкінуді болжау, айналадағы ортаның ластануын анализдеу, дәрі-дәрмек препараттарын жасау, т.б.

  • білім беру саласында: кеңейтілген графика және виртуальды әлем, әсіресе, компьютерлік ойындар құрастыру.

    1. Салыстыру-және-алмастыру әдісімен сұрыптау.

Көптеген программаларда сұрыптау кезінде ағымдағы санды басқа санмен орны бойынша алмастыру мақсатында уақытша сақтау үшін базалық айнымалылар пайдаланылады. Ал, параллельді есептеулерде ол сандарды сақтап қоюға процессорларды пайдаланады.
if (A>B)

temp=A; A=B; B=temp;

2. Көпіршіктер әдісімен сұрыпау

(a1, a2, ...,an) сандарының тізбегі берілсін. Сандарды өсу ретімен орналастыру керек, яғни i>j үшін aij



Программа 1. «Көпіршіктер» әдісімен сұрыптаудың тізбекті алгоритмі.
procedure BUBBLE-SORT(n)

begin


for i:=n-1 downto 1 do

for j:=1 to i do

compare-exchange(aj,aj+1);

end BUBBLE-SORT


Бұл алгоритмде ішкі цикл итерациясы Q(n) уақытта орындалса және Q(n) итерация жасалса, «көпіршіктер» әдісімен сұрыптауға кететін уақыт - Q(n2). Бұл алгоритмді параллельділікке айналдыру үлкен қиындық келтіреді. Сондықтан бұл әдістің екіншібір түрі «тақ-жұп орын ауыстыру» алгоритмін қарастырайық.
3. «тақ-жұп орын ауыстыру» алгоритмі.

Бұл алгоритмде 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(n2).
Программа 2. "тақ-жұп орын ауыстыру" тізбекті алгоритмі.

procedure ODD-EVEN(n)

begin

for i:=1 to n do



begin

if i is odd then

for j:=0 to n/2-1 do

compare-exchange(a2j+1,a2j+2)

if i is even then

for j:=1 to n/2-1 do

compare-exchange(a2j,a2j+1)

end for


end ODD-EVEN
Өз бетімен орындауға арналған тапсырмалардың нұсқалары:

  1. Параллельді компьютерлердің және параллельді есептеулер қолданылатын облыстарды талдап, жазыңдар.

  2. Программалар деңгейінің параллельділігіне мысал ретінде екі массив элементтерінің қосындысын тап.

  3. Куб көлемі - 100х100х100 нүктелерден тұрады.Әрбір нүктеде орындалатын функциялар – жылдамдық, қысым, температура, компоненттің концентрациясы (су, газ, мұнай, т.б. ). Барлығы 5-20 функция (орташа-10). Бұл функциялар сызықты емес. Сондықтан оларды есептеу үшін 200-1000 операция орындалу керек (орташа -500). Жүріп жатқан процестер стандартты емес, сондықтан қадамдар саны 100-1000 (орташа-500). Сонда куб ішінде орындалатын арифметикалық операциялар санын есептеп тап.

4.Берілген сандар жиынының ең кіші k-сыншы ретті санды табатын параллельді программаны жазыңдар.

5.Тақ-жұп сұрыптаудың салыстыру-және-алмастыру тәсілін пайдаланып, төмендегі 16 санды сұрыптаңдар: 12 2 11 4 9 1 10 15 5 7 14 3 8 13 6 16.

6.Тақ-жұп сұрыптауды орындауға кететін уақыттың O(log2n)-ге тең екенін дәлелдеңдер.

Зертханалық жұмыстың орындалуы туралы есебінің формасы:


  1. Берілген есептердің қойылымын талдап, түсіндіру.

  2. Берілген есептерді шешу алгоритмін түсіндіру.

  3. Орындалған жұмыс жөнінде есеп беру.


Бақылау сұрақтары.

  1. Параллелді компьютер түсінігі. Параллель компьтерлерді қолдану облыстары және олардың даму бағыттары.

  2. Параллельділік. Мәліметтер параллельдігі.

  3. Параллельділік. Тапсырма деңгейінің паралельділігі.

  4. Параллельділік. Программа деңгейінің параллельділігі.

  5. Параллельділік. Командалар деңгейінің параллельділігі.

  6. Параллелді компьютерлер типтері. Көппроцессорлы жүйе.

  7. Параллельді компьютерлер типтері. Үлестірімді жадылы мультикомпьютерлер.

  8. Параллельді программалық жабдықтау үшін қандай талаптар орындалу керек?


Глоссарий

Параллельді компьютер – есепті сандық түрде шешіп, үйлесімді шешуге қабілетті процессорлардың жиынтығы.

Параллельді программа – бұл әр процесс өзінің меншікті процессорында жүріп қана қоймай, параллель орындалатын программа.



Тапсырма деңгейінің параллельділігі - параллельділіктің ең жоғарғы деңгейі. Бұл деңгейде орталық процессор мен енгізу-шығару жүйесі параллель жұмыс жасайды.

Программа деңгейінің параллельдігі - бір программа оны құраушы бөліктеріне бөлініп орындалатын процесс.

Командалар деңгейінің параллельдігі - бұл типті іске асыратын негізгі тәсіл –конвейерлер. Бұл жағдайда не жеке командалар қалқаланады, не берілген команда бағыныңқы операцияларға жіктеледі.

Арифметикалық және биттік туралау параллельдігі -параллельдігінің ең төменгі деңгейі. Бұл деңгей - орталық процессордағы арифметика-логикалық құрылғыға жатқызылады.

Программалау модельдері: параллельді және тізбекті.

Көпшілік қолданарлық (общедоступный) көп процессорлы жүйе -көптеген процессордың жыйынынан тұрады, олар бір-бірімен жадының модульдер жиынымен өзара байланысты.
Әдебиеттер

  1. А. Ж. Акжалова. Параллельные вычисления. Учебное пособие. – Алматы: Издательство ТОО «Print S»,- 2004

  2. Грегори Р. Эндрюс. Основы многопоточного, параллельного и распределенного программирования. Пер. с англ.-М.: Издательский дом «Вильямс», 2003.

  3. Воеводин Вл. Параллельная обработка данных. Санкт-Петербург, 2002.

  4. Немнюгин С.А., Стесик О.Л. Параллельное программирование для высокопроизводительных многопроцессорных систем. Санкт-Петербург, 2002.

5-8 лабораториялық жұмыс



Тақырыбы: Программалау тілдерінің синхронизациясын қолдана отырып, есептерді шешу: блоктар/блоктан алу; критикалық секция; семафорлар.
Жұмыстың мақсаты: Семафорларды қолданып, параллель программалау құру.

Материалдар және жабдықтар: ДК, параллельді есептеулерді программалау ортасы, ПараЛаб программалау жүйесі.

Жұмыстың мазмұны және орындалу тәртібі:

«Өндіруші - тұтынушы» типті синхронизация. Блоктау және кедергілер. Критикалық секция есебі.



Өз бетімен орындауға арналған тапсырмалардың нұсқалары:

  1. Сандар жиынының ең кіші kth номерін табу үшін параллель программа жазу. Тез сұрыптаудың параллель нұсқасын қолданыңыз, тек kth кіші номерден тұратын сандар жиынына хабарлаңыз.

  2. Критикалық секция есебін талдаңыз.


Зертханалық жұмыстың орындалуы туралы есебінің формасы:

  1. «Өндіруші - тұтынушы» типті синхронизация есебін талдау.

  2. Программасын С ++ тілінде жазу

  3. Орындалған жқмыс жөнінде есеп беру.


Бақылау сұрақтары.

  1. Синхронизация дегеніміз не?

  2. Семафорлар дегеніміз не?

  3. Мониторлар қай кезде қолданылады.

  4. Блоктар мен кедергі дегеніміз не?


Глоссарий.

Параллельді компьютер – есепті сандық түрде шешіп, үйлесімді шешуге қабілетті процессорлардың жиынтығы.

Параллельді программа – бұл әр процесс өзінің меншікті процессорында жүріп қана қоймай, параллель орындалатын программа.

Жұмыстың қысқаша мазмұны:

Екі процес берілсін: Produser (өндіруші) және Consumer(тұтынушы). Produser процессі а[n] бүтін сандардың локальді массивінен тұрсын. Consumer – b[n] болсын. а массиві иннициялизацияланған болсын.



Мақсат: оның мазмұнын b массивіне көшіру.

buf айнымалысы – өзара әсер ету буфері болып табылатын жеке бөлінетін бүтін айнымалылар.

Produser (өндіруші) және Consumer(тұтынушы)процесстері buf айнымалысына кезекпен кезек ене алады. Produser а массивінің бірінші элементін buf –ке салып, сонан соң Consumer оны алады, сонан соң Produser buf буферіне а массивінің келесі элементін салады, және т.с.с. р және с бөлінетін айнымалылыар айнымалылар санының санағышы болсын. Олардың бастапқы мәні =0. Сонда Produser (өндіруші) және Consumer(тұтынушы) процесстерінің синхронизацилану шарты төменгі түрде жазылады:

РС: c<=p<=c+1

с және р айнымалыларының мәні 1 ден артық мәнге айырмашылығы болмайды. Осы екі процесстің коды төменде берілген:

int buf, p=0, c=0; process Procedur

{

Int a[n]; While (p

{ buf =a[p];

p=p+1;


}

}

Process Consumer



{

Int b[n]; While (c

{ c); > b[c]=buf; c=c+1;

}

}


Әдебиеттер

  1. А. Ж. Акжалова. Параллельные вычисления. Учебное пособие. – Алматы: Издательство ТОО «Print S»,- 2004

  2. Грегори Р. Эндрюс. Основы многопоточного, параллельного и распределенного программирования. Пер. с англ.-М.: Издательский дом «Вильямс», 2003.

  3. Воеводин Вл. Параллельная обработка данных. Санкт-Петербург, 2002.

  4. Немнюгин С.А., Стесик О.Л. Параллельное программирование для высокопроизводительных многопроцессорных систем. Санкт-Петербург, 2002.

9,10 Зертханалық жұмыс.



Ағындарды қолданып, Linux- те программалар құру
Жұмыстың мақсаты: Linux операциялық жүйесінде ағындарды қолдану

Материалдар және жабдықтар: ДК, параллельді есептеулерді программалау ортасы, Linux операциялық жүйесі.
Жұмыстың мазмұны және орындалу тәртібі:

Өз бетімен орындауға арналған тапсырмалардың нұсқалары:

  1. Linux операциялық жүйесінің ерекшеліктері талдау

  2. Ағындар. Ағындар түрлерін қарастыру

Зертханалық жұмыстың орындалуы туралы есебінің формасы:

  1. Linux операциялық жүйесіндегі ағындар туралы конспекті жазып, түсіндіру.

  2. Орындалған жұмыс жөнінде есеп беру.


Зертханалық жұмыстың мазмұны:

Ағындарды құру үшін pthread кітапханасы қолданылып, pthread_create функциясы шақырылады, осы кітапханада синхронизациялау үшін арнайы объектілер мен текстер сипатталған.


/*sem.h*/

#include #include #include

// semafore #include

#include #include #include

/*


  • В моей системе данное объединение не объявлено в подключенных файлах -

  • если компилятор напишет что оно ранее объявлено - просто сотрите :)

*/

union semun {

int val; /* Value for SETVAL */

struct semid_ds *buf; /* Buffer for IPC_STAT, IPC_SET */

unsigned short *array; /* Array for GETALL, SETALL */

struct seminfo *__buf; /* Buffer for IPC_INFO

(Linux specific) */

};

class sem



{

private:


int sid; // идентификатор семафора

key_t key; // ключ по которому получаем идентификатор

int res_count; // количество ресурсов у семафора

public:


/*

  • кол-во ресурсов

  • некое случайное число

  • путь в системе - обязательно должен существовать !

*/

sem(int max_res, int id, const char* identify); /*



  • деструктор - тут удаляем семафор, иначе он останется до

  • следующей перезагрузки системы или пока его кто-то явно не удалит

*/

~sem();


/*

* обертки для занятия/освобождения ресурсов

*/

bool lock(int res); bool unlock(int res);



};

typedef sem* psem;

Cледующий файл:

/*sem.cpp*/ #include "sem.h"

sem::sem(int max_res, int id, const char* identify)

{

sid = -1; res_count = 0; /*



* получаем ключ для семафора

*/

if ((key = ftok(identify,id)) == -1)



{

return;


}

/*


  • 0666 - rw для всех, чтобы потом можно было обратиться к семафору

  • от любого пользователя системы, в общем то личное дело каждого

  • сначала пытаемся открыть имеющийся семафор с таким ключом - и

  • удалить его, старый нам ни к чему

*/

if ((sid = semget(key, 0, 0666)) != -1)

{

if (semctl(sid, 0, IPC_RMID, 0) == -1)



{

sid = 0;


}

}

if (sid != 0) // проверяем что семафор был найден и удален или не существовал



{

/*


  • создаем с флагом IPC_EXCL - означает что в случае если семафор уже

  • имеется - вызов будет провален c значением EEXIST,

  • без возврата значения отрытого уже существующего семафора

*/

if ((sid = semget( key, 1, IPC_CREAT | IPC_EXCL | 0666 )) != -1)

//

{

union semun semopts; semopts.val = max_res;



semctl(sid, 0, SETVAL, semopts); res_count = max_res;

}

} else sid = -1;



}

sem::~sem()

{

if (sid != -1)



{

semctl(sid, 0, IPC_RMID, 0);

}

}

bool sem::lock(int res)



{

/*


  • отсекаем неверные запросы сразу, не используя обращения к структурам семафора

*/

if ((res > res_count) || (sid == -1))

{

return false;



}

/*


  • параметры в структуре

  • 0 - номер семафора

  • количество ресурсов - если захватываем, должно быть отрицательным

  • 0 - ждать если на данный момент нет достаточного

  • количества ресурсов или IPC_NOWAIT - возвращать ошибку

*/

struct sembuf sem_lock={0,(-1)*res,0}; /*



  • параметры запроса

  • - идентификатор семафора

структура которую заполняли выше - ее адрес

  • - сколько раз выполнить операцию

*/

if ((semop(sid, &sem_lock, 1)) == -1)

{

return false;



}

return true;

}

bool sem::unlock(int res)



{

/*

* аналогично функции lock */



if ((res > res_count) || (sid == -1))

{

return false;



}

struct sembuf sem_unlock= { 0, res, IPC_NOWAIT}; if ((semop(sid, &sem_unlock, 1)) == -1)

{

return false;



}

return true;

}
Бақылау сұрақтары.


  1. Linux операциялық жүйесі мен Windows операциялық жүйесінің айырмашылығы

  2. Неліктен ағындарды Linux операциялық жүйесінде құрады.


Глоссарий.

Параллельді компьютер – есепті сандық түрде шешіп, үйлесімді шешуге қабілетті процессорлардың жиынтығы.

Параллельді программа – бұл әр процесс өзінің меншікті процессорында жүріп қана қоймай, параллель орындалатын программа.

Әдебиеттер

  1. А. Ж. Акжалова. Параллельные вычисления. Учебное пособие. – Алматы: Издательство ТОО «Print S»,- 2004

  2. Грегори Р. Эндрюс. Основы многопоточного, параллельного и распределенного программирования. Пер. с англ.-М.: Издательский дом «Вильямс», 2003.

  3. Воеводин Вл. Параллельная обработка данных. Санкт-Петербург, 2002.

  4. Немнюгин С.А., Стесик О.Л. Параллельное программирование для высокопроизводительных многопроцессорных систем. Санкт-Петербург, 2002.

11-12 Зертханалық жұмыс Хабарламаларды беруді программалау



Жұмыстың мақсаты: MPI - параллельді программалау құралымен жұмыс жасау принципімен танысу.

Материалдар және жабдықтар: ДК, параллельді есептеулер программалау ортасы, MPI кітапханасы.
Жұмыстың мазмұны және орындалу тәртібі:

1. MPI_Send және MPI_Recv процедураларын қарастырайық:


int MPI_Send (void* buf, int count, MPI_Datatype dataType,

int dest, int tag, MPI_Comm_comm)


Мұндағы: buf - буфер адресінің басы;

count – міндетті түрде жіберілетін элементтер саны;

dataType – әрбір элементтің типі, мысалы: MPI_INT, MPI_DOUBLE, MPI_CHAR, және т.с.с.;

dest - адресат рангісі (процесс идентификаторы); tag – хабарлама тэгі;

comm - коммуникатор.

int MPI_Recv (void* buf, int count, MPI_Datatype dataType, int source, int tag, MPI_Comm comm, MPI_Status* status)

Мұндағы: status – кері қайту жағдайын қайтарады,

source – MPI_Send процедурасындағыдай берілу идентификаторы.

MPI программасында белгілі бір ережелерді қатаң сақтау керек, онсыз жұмыс жүруі мүмкін емес. Алдымен, программының басталуында, оның тақырыбынан кейін сәйкес тақырыптық файлды іске қосу керек. С тіліндегі программада бұл - mpi.h. Программада MPI кітапханалық процедурасының алғашқы шақырылымы MPI_Init инициализациясының ішкі программасын шақыру болып табылады. С тілінде инициализация функциясының параметрі негізгі программа қосылған жағдайда оның аргументінің адресін алады: MPI_Init(&argc, &argv);

2. MPI кітапханасының көмегімен екі процесс арасындағы мәндермен алмасу программасын қарастырайық:

#include #include

Main(int argc, char *argv[]) {int myid, otherid, size;

Int length=1, tag=1;

Int myvalue, othervalue; MPI_Status status;

MPI_Init(&argc, &argv);

MPI_Comm_size(MPI_COMM_WORLD, &size);

MPI_Comm_rank (MPI_COMM_WORLD, &myid);

if (myid==0) (otherid=1; myvalue=14;}

else


{otherid=0; myvalue=25;}

MPI_Send(&myvalue, length, MPI_INT, otherid, tag, MPI COMM_WORLD, &status);

MPI_Recv(&othervalue, length, MPI_INT, MPI_ANY_SOURCE, tag, MPI COMM_WORLD, &status);

printf("npoцecc номер %d алынды %d\n", myid, othervalue);

MPl_Finalize();}


  1. Әр біреуі стандартты құрылғыға процесс номерін және іске қосылған процесстердің саны туралы хабарлама шығаратын бірнеше поцессті іске қосатын қарапайым программаны келтірейік:

#include #include

int main(int argc,char *argv[])

{

int myid, numprocs;



MPI_Init(&argc, &argv);

MPI_Comm_size(MPI_COMM_WORLD, &numprocs);

MPI_Comm_rank(MPI_COMM_WORLD, &myid);

printf(stdout,"Process %d of %d\n", myid, numprocs)

MPI_Finalize();

return 0;

}


  1. Келесі программа жұп және тақ рангілі процесстер арасындағы хабарламалар алмасуға мысал болады, size мәні жұп болсын делік:

#include

#include

int main(int argc,char *argv[])

{

int myrank, size, message; int TAG = 0;



MPI_Status status; MPI_ Init(&argc, &argv);

MPI_Comm_rank(MPI_COMM_WORLD, &myrank);

MPl_Comm_size(MPI_COMM_WORLD, &size);

message=myrank;

if((myrank%2)-0)

{

If((myrank+1)1-size)



MPI

{

if((myrank+ 1)1- size)



MPI_Send(&message, 1, MPI_INT, myrank+1, TAG,MPI_COMM_WORLD);

else {if (myrank !- 0)

{ MPI__Recv(&message, 1, MPI_INT, myrank-1, TAG, MPI_COMM_WORLD, &status);

printf("I am %i received :%i \n", rank, message);

return 0;

}
Өз бетімен орындауға арналған тапсырмалардың нұсқалары:



  1. MPI программасын қондыру және күйін келтіру.

  2. Процессорлардың жалпы санын анықтау (MPI_Comm_Size).

  3. Процесстердің жеке номерін анықтау (MPI_Comm_Rank).

  4. “Нүкте-Нүкте” типті блокталынған коммуникациялық функция көмегімен мәліметті жіберуді ұйымдастыру (MPI_Send, MPI_Recv).

  5. Бір мезгілде мәліметті жіберуді ұйымдастыру (MPI_Sendrecv)


Зертханалық жұмыстың орындалуы туралы есебінің формасы:

  1. Берілген есептердің қойылымын талдау, қолданылатын процедураны түсіндіру.

  2. Берілген есептерді шешудің параллельді алгоритмін түсіндіру.

  3. Орындалған жұмыстың программасын ЭЕМ –де көрсетіп, есебін рәсімдеп, тапсыру.


Бақылау сұрақтары.

  1. Хабарламаларды беруді программалауды түсіндір.

  2. MPI (Message Passing Interface ) программалау құралы не үшін қажет?

  3. MPI функционалдық сұраныстарын ата.

  4. MPI_Send процедурасын түсіндір.

  5. MPI_Recv процедурасын түсіндір.


Глоссарий.

MPI(Message Passing Interface ) – хабарламаларды беру интерфейсі.

MPI_Send – хабарламаның блокталынып берілуі. MPI_Recv – хабарламаның блокталынып алынуы. MPI_Comm_size - процесстер санын анықтайды. MPI_Comm_rank – процесстер рангісін анықтайды.
Әдебиеттер

  1. А. Ж. Акжалова. Параллельные вычисления. Учебное пособие. – Алматы: Издательство ТОО «Print S»,- 2004

  2. Грегори Р. Эндрюс. Основы многопоточного, параллельного и распределенного программирования. Пер. с англ.-М.: Издательский дом «Вильямс», 2003.

  3. Воеводин Вл. Параллельная обработка данных. Санкт-Петербург, 2002.

  4. Немнюгин С.А., Стесик О.Л. Параллельное программирование для высокопроизводительных многопроцессорных систем. Санкт-Петербург, 2002.

13-15 Зертханалық жұмыс.



PVM-де жұмыс. Ағындарды құру және PVM-де мәліметтерді параллель өңдеу

Жұмыстың мақсаты: PVM - параллельді виртуальді машинасының жұмыс жасау принципімен танысу, хабарламаларды беру және процессті синхронизациялауға арналған кітапханалармен жұмыс жасау.

Материалдар және жабдықтар: ДК, параллельді есептеулер программалау ортасы, PVM кітапханасы.

Жұмыстың мазмұны және орындалу тәртібі:

1. PVM жүйесін қондыру (1-әдіс).

Linux ОЖ-мен жұмыс жасайтын компьютерге PVM жүйесін қондыру үшін бума құру керек, мысалы /pvm3 бумасы құрылсын. Осы бумада tar zxvf pvm3.3.4.tgz архивтелген файлын ашу керек. PVM қосылу үшін $PVM_ROOT айнымалысына буманың жолын көрсету керек. Командалық қабықша ретінде csh қолданылса, .cshrc файлына келесі командалық жолды қосу керек:

setenv PVM_ROOT=/pvm3

Егер командалық қабықша ретінде sh немесе ksh қолданылса, онда .profile файлына келесі командалық жолды қосу керек:

export PVM_ROOT=/pvm3

2-әдіс. pvm_spawn() функциясы үшін орындалатын файл қатаң түрде бумада сақталынады. Linux ОЖ-де мына каталогтар пайдаланылады:

$PVM_ROOT/bin/$PVM ARCH/ және $HOME/pvm3/bin/$PVM_ARCH,

PVM_ROOT/ usr/local/pvm/current

PVM-де орындалу үшін aimk қолданылады, сонда master және slave компиляцияланады және байланысады.

PVM-ді іске қосу үшін pvmd.exe –даемонды пайдалану керек. Жаңа компьютерлер қосу керек: addhost <хост аты>. Тапсырманы орындау үшін spawn->



Достарыңызбен бөлісу:
1   2   3




©dereksiz.org 2024
әкімшілігінің қараңыз

    Басты бет