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) уақыт жұмсалады.
12-13- дәріс
Тақырыбы: Параллель программалау. Ағындар және мәліметтерді
Достарыңызбен бөлісу: 
