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

Жұлдызша тәрізді 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 тор
2
Гиперкуб
log p
p/2
log p
(p log p)/2
Амдал заңы.  Параллельді есептеулерді модельдеу
Параллельді есептеулер сапасына мына көрсеткіштер әсер етеді:
5. Есептеудің жедел орындалуы.
6. Есептелу тиімділігі.
7. Есептелу құны.
8. Есептелу көлемі.
Есептелудің жедел орындалуы (speedup) мына шамамен анықталады:
саны
ар
процессорл
p
t
t
уаќыт
кететін
есептеуге
машинада
орлы
кґппроцесс
уаќыт
кететін
есептеуге
машинада
орлы
бірпроцесс
n
S
p



,
)
(
1
Есептелудің тиімділігі мына шамамен анықталады:
саны
ар
процессорл
p
p
n
S
T
p
T
n
E
p



,
)
(
*
)
(
1
Есептелу құнының пайдалы бағасы – параллельді есептелетін уақыттың 
процессорлар санына көбейтіндісін айтамыз.
саны
ар
процессорл
р
T
p
C
p
p


,
*
Мысалдар келтірейік:
1-мысал. «Операциялар-операндтар» графы түрінде есептеу моделі.
Есептеу моделін жеңілдету үшін, есептеу барысындағы кез-келген есептеу 
операциясына кететін уақытты бірдей және 1-ге тең деп қабылдаймыз 
(өлшем бірлігін өз бетімізше аламыз).                                                                                                     
Мынадай есеп қойылсын: Қарама-қарсы бұрыштарының координаттары 
берілген тіктөртбұрыштың ауданын есептеудің алгоритмін граф түрінде 
көрсетейік.  

Бұл мысалдан, есеп шешуде таңдалған алгоритмді орындау үшін есептеу 
схемасын басқаша да құруға болады және басқаша есептеу моделін құруға 
болады. Сонда  әртүрлі  есептеу  схемалары  параллельділіктің  әр  түрлі 
мүмкіншіліктерін  қарастыруға  мүмкіндік  береді,  яғни  есептеу  моделін 
құру  кезінде  біздің  алдымызда  алгоритмді  есептеу  схемасының 
параллельді  орындалу  тәсілдерінің  ең  қолайлысын  таңдау  мақсаты 
тұрады.
2-мысал. Сандардың қосындысын табу алгоритмдерін қарастырайық.
n- қосындылардың саны.
Бұл  есепті  шешудің  параллельді  әдісін  бастамас  бұрын  алдымен 
қарапайым жағдайды қарастырамыз, яғни 
       
Мұның алгоритмі тізбектеп қосудан шығады.
S=0,
S=S+x
1
,...
Бұл алгоритмді тізбектеп есептеу схемасы мынадай:

Бұл «стандартты» алгроитм тізбекті орындалады да, параллельді орындала 
алмайды.  Параллельді  орындалу  үшін  қосындыны  табу  операциясын 
ассоциативті  орындап,  есептеу  процесін  басқаша  құру  керек.  Бірінші 
итерацияда  барлық  берілгендер  екі  бөлікке  бөлінеді,  және  әр  жұп  үшін 
олардың қосындысы табылады, Әрі қарай барлық алынған қосынды тағы 
жұп бөлікке бөлініп, жұп мәндерінің қосындысы табылады, тағы с.с.
Бұл  есептеу  схемасы  – қосындыны  есептеудің  каскадты  схемасы  деп 
аталады, оны граф түрінде тұрғызуға болады. 
n=2
k   
Мұндағы итерациялардың саны: k=log
2
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-тің  бастапқы,  соңғы  немесе  олардың 
комбинациясын алып отыр.

жүктеу/скачать 11,68 Mb.

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