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


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



Pdf көрінісі
бет35/82
Дата06.01.2022
өлшемі11,68 Mb.
#15553
1   ...   31   32   33   34   35   36   37   38   ...   82
Байланысты:
malikova narbekova paral

Программа 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 then


7. if id is odd then
8. compare-exchange_min(id+1);
9. else
10. compare-exchange_max(id-1);
11. if  i is even then
12. if id is even then
13. compare-exchange_min(id+1);
14. else
15. compare-exchange_max(id-1);
16. end for
17. 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   ...   31   32   33   34   35   36   37   38   ...   82




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

    Басты бет