Compare-exchange_max(id-1);

Флинн таксономиясы

1. Процессорлар мен жады арасындағы байланыс қандай да бір өзарабайланыс желісінің формасы арқылы жүзеге асырылады. Ортақ жадылы конфигурациясы бар параллель компьютердің жалпы түрі төменде көрсетілген.

Жады келесі ерекшеліктермен шектеледі:

1. Өлшемімен – қолданушыларға көп жағдайда жады жетіспейді, сондықтан виртуал жады ұғымы ойлап табылды.

2. Жадының өткізу қабілеттілігі (latency) және иерархиясымен.

3. Жадының өткізу қабілеттілігі (bandwidth) – жадыға жазылатын немесе жадыдан оқылатын мәліметтер көлемі.

4. Жадыны қорғау – көптеген архитектуралар программалық қамсыздандыруды модификациядан не жүйелік жадыдан немесе басқа прогаммаларды қолданғандағы жадыдан қорғауды қосады.

Барлық жедел жадыдағы әрбір ұяшықтың қайталанбайтын адресі болады және берілген адресті әрбір процессор берілген ұяшықтарға хабарлау үшін қолданылады. Жады ұяшығында виртуал адрес және физикалық адрес болады. Виртуал адрестеу процессормен генерацияланған. Физикалық адрес жадыдағы нақты орынға ену үшін қолданылады. Виртуал және физикалық адрес арасында TLB (Translation Lookaside Buffer) адрестерді түрлендіру көмегімен автоматты түрде ауысу жүргізіледі.

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

Процессорлер үшін өзара байланыс бір-біріне хабарламаларды беру және қабылдау көмегімен қамтамасыз етіледі. Хабарламаларда басқа процессорлер есептеу үшін қажет мәліметтер болуы мүмкін.

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

Жұмыс станцияларының жиынынан тұратын желілік жүйе – жалпы жұмыс станциясының желісі (NOW – network of workstations) немесе жұмыс станциясының кластері (COW – cluster of workstation) д.а. Барлық жұмыс станциялары бір – бірімен байланысқан бір немесе бірнеше қосымшаларды орындайды. Үлестірілімді жадылы қымбат емес мультипроцессорды құрудың ең кең таралған әдісі – ол Beowulf машинасын құрастыру. Ол базалық аппараттық қамсыздандырудан және Pentium процессорының чипы, желілік карта, дисктер және Linux операциялық желісі сияқты ақысыз программалардан тұрады.

Флинн таксономиясы.

1. SIMD SISD MIMD MISD құрылымдары.

басқару модулі

SIMD құрылымы.

команда

басқару модулі

мәлімет нәтиже

мәлімет

басқару модулі

мәлімет

басқару модулі

-----------

МІМD құрылымы:

Басқ.. мод

ЖЕЛІ

команда

Өңд. мод

мәлімет

Нәтиже

Басқ.. мод

команда

Өңд. мод

мәлімет

Нәтиже

МІМD номері көптеген өзара байланысты процестерден тұрады, олардың әр қайсысының жеке басқару блогы бар.

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

МІМD құрылымды компьютерде жолды не үлестірілген, не барлығына жететін (обще доступный) болуы мүмкін.

Мысалы:

Cray – 2, SI;

Cray X - MP;

IBM 370/168 MP, IPSC

MISD құрылымы:

Команда Команда Команда

Басқ.. мод

...

Өңд. мод

Мәлімет... Нәтиже

Мұнда да процесстің жиыны жұмыс жол-ы, бірақ барлығы 1 – ғана мәліметтер ағынына әсер етеді.

Мұндай құрылымды 1 космпьютер белгілі. Ол, C. mmp, Carnegie – Mellon университетінде жасалған.

Бұл компьютер басқа режимде де (SIMP, MISD, MIMD)жұмыс жасай алады.

Парам-ді программалауды тиімділігін бағалау.

Ол мына функцияларға байланысты:

Орындалу уақытына

Жады конфигурациясына және

Орындалуға кететін шығынға

Қызмет көрсету және ақысына, тағы басқалары;

Мысалы: ауа райын болжау жүйесін құруда.

ЭЕМ өнімділігін қалай арттыруға болады?

1949 жылы шыққан компьютерлердің тактілік уақыты 2 микросекунд (2*10^-6 сек), яғни орташа 100 арифметикалық операцияны 1 секундта орындайды. Қазіргі заманғы компьютерлердің тактілік уақыты 1,8 наносекунд (1,8*10^-9сек), яғни 1 секундта 77 млрд.арифметикалық операция орындалады. Жарты ғасырда компьютер өнімділігі 700 млн. есе өскен, яғни 2 микросекундтан 1,8 наносекундқа дейін өскен. Бұл компьютер архитектурасы жаңаша құрылған деген сөз. Мәліметтерді параллель өңдеуді бір уақытта бірнеше әрекет жасалатындығымен түсіндіруге болады. Бұны былайша түсіндіруге болады. 1 құрылғы 1 операцияны 1 бірлік уақытта орындайды, осы құрылғы 100 операцияны 100 бірлік уақытта орындайды. Егер осындай 5 құрылғы бір мезгілде жұмыс жасаса, онда кететін уақыт 200 бірлікке тең болар еді, яғни N құрылғы 1/N уақыт бірлігінде жұмысты орындап шығады. Тағы бір мысал, 1 солдат жерді 10 сағатта қазса, рота (50 солдат) бірдей күшпен, бірдей уақытта 12 минутта қазып шығады екен. Міне, параллельділік принципі осыдан шыққан!

6,7 – дәріс

Тақырыбы: Есептеуіш жүйелер процессорларының мәлімет алмасу желісінің топологиясы. Амдал заңы. Густафсон заңы.

Жоспары

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

2. Амдал заңы

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

- бірөлшемді куб – түзумен байланысқан екі түйін.

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

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

Яғни, N желімен байланысқан 2ⁿ процессорлардан тұрады.

Енді осы мәліметтер берілу желісі топологиясының сипаттамаларын беру үшін мынадай көрсеткіштер прайдаланылады:

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

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

Төменде мәліметтер берілу желісітопологиясына сипаттама берілген. (р-процессорлар саны).


Топология	Диаметр	Ені	Бисекцилық байланысы	Есептеу құны
Толық граф		p²/4	p–1	p(p–1)/2
Жұлдызша тәрізді				p–1
Толық екілік ағаш	2log((p+1)/2)			p–1
Сызғыш тәрізді	p–1			p–1
Сақиналы	p/2			P
N=2 тор
Гиперкуб	log p	p/2	log p	(p log p)/2

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

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

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

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

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

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

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

Есептелудің тиімділігі мына шамамен анықталады:

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

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

1-мысал. «Операциялар-операндтар» графы түрінде есептеу моделі.

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

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

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

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

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

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

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

S=0,S=S+x₁,...

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

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

Бұл есептеу схемасы – қосындыны есептеудің каскадты схемасы деп аталады, оны граф түрінде тұрғызуға болады.

n=2^k

Мұндағы итерациялардың саны: k=log₂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-тің бастапқы, соңғы немесе олардың комбинациясын алып отыр.

8-дәріс

Тақырыбы: Процесстер және синхронизация. Семафорлар. Мониторлар.

Жоспары: Процесстер және семафорлар

Int y=0, z=0;

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

9-11 - дәріс

Тақырыбы: Параллельді алгоритмдер.

Сұрыптаулар (ранг, көпіршіктер әдістері).

Жоспары:

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

2. Тақ-жұп әдісімен сұрыптау.

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

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

2. салыстыру және алмасу сұрыптауы

алгоритмдер:

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

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

сұрыптауы

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

Тез сұрыптау

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

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

if (A>B)

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

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

(a₁, a₂,...,a_n) сандарының тізбегі берілсін. Сандарды өсу ретімен орналастыру керек, яғни i>j үшін a_i<a_j

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

Procedure BUBBLE-SORT(n)

Begin

3. for i:=n-1 downto 1 do

4. for j:=1 to i do

5. compare-exchange(aj,aj+1);

End BUBBLE-SORT

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

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

Бұл алгоритмде n элемент n фазада сұрыпталады. Бұл алгоритмнің жұп және тақ фазалары кезектестіріледі. (a₁, a₂,...,a_n) – тізбегін сұрыптау керек болсын. Тақ фаза кезінде тақ индексті элементтер оң жақтағы көрші элементпен салыстырылып, егер шарт орындалса, олар орындарын алмастырады, яғни (a₁, а₂), (a₃, a₄),..., (a_n-1,a_n) жұптары салыстырылып алмастырылады. Сол сияқты жұп фаза кезінде, жұп индексті элементтер салыстырлып, егер шарт орындалса, олар орындарын алмастырады, яғни (а₂, a₃), (a₄, a₅),..., (a_n-2,a_n-1) жұптары салыстырылып алмастырылады. Сонда тақ-жұп ауыстыру n фазасынан кейін тізбек сұрыпталады. Әрбір алгоритмнің фазасында Q(n) салыстыру жасалса, барлығы n фаза болса, бұл алгоримтнің (sequential complexity) - Q(n²).

Программа 2. "тақ-жұп орын ауыстыру" тізбекті алгоритмі.

Procedure ODD-EVEN(n)

Begin

3. for i:=1 to n do

Begin

If i is odd then

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

7. compare-exchange(a_2j+1,_a2j+2)

If i is even then

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

10. compare-exchange(a_2j,a_2j+1)

End for

End ODD-EVEN

Мысалы, n = 8 элементті «тақ-жұп орын ауыстыру» әдісімен сұрыптау керек.. Әрбір фазада n = 8 элемент сұрыпталады.

Енді осы «тақ-жұп» алгоритмді параллельділікке көшірейік. Бұл жағдайда алгоритмнің әрбір фазасы кезінде элементтердің жұбын салыстыру-алмастыру операциясы бірмезгілде орындалады. Процессорлар сақиналы желімен байланысқан болсын. a_i элементі бастапқыда Р_i процессорда болсын., тақ фаза кезінде, тақ номерлі процессордағы элемент оның оң жағында орналасқан процессордағы элементпен салыстыру-алмастыру процесі жүреді.. Сол сияқты процесс жұп фаза кезінде де орындалады.

Программа 3. n-процессорлы сақинада орындалатын "тақ-жұр орын ауыстыру" тәсілінің параллельді алгоритмі.

Procedure ODD-EVEN-PAR(n)

Begin

3. id:= processor's label

4. for i:= 1 to n do

Begin

If i is odd then

If id is odd then

8. compare-exchange_min(id+1);

Else

compare-exchange_max(id-1);

If i is even then

If id is even then

13. compare-exchange_min(id+1);

Else