Оқулық Қазақстан Республикасы Білім және ғылым министрлігі бекіткен Алматы, 2011

133 
h қадамымен z және τ қадамымен у бойында бірқалыпты тор 
тұрғызайық. Қандай да бір себептерге байланысты айқын схема таңдап 
алынды делік. 
.
2
2
)
1
(
1
)
1
(
)
1
(
1
)
1
(
)
(
h
u
u
u
u
u
i
j
i
j
i
j
i
j
i
j











Алгоритм келесі формулаға сәйкес іске асырылатын болсын. 
).
2
(
)
1
(
1
)
1
(
)
1
(
1
2
)
1
(
)
(










i
j
i
j
i
j
i
j
i
j
u
u
u
h
u
u

(2.13) 
Алгоритм графын тұрғызу үшін i, j остерімен тік бұрышты координат 
жүйесін енгізейік. Берілген айнымалылар z, у және i, j арасындағы байланыс
j
h
z
i
y


,

қатынасымен беріледі. 
Бүтінсанды тордың әрбір торабына граф тӛбесін орналастырамыз және 
оны a, b, c аргументтерінің әртүрлі мәндері үшін орындалатын келесі скаляр 
операцияға сәйкес келеді деп есептейміз. 


.
)
2
1
(
2
2
c
b
h
h
a







(2.14) 
Алгоритм графы h = 1/8, τ = Т/6 жағдайы үшін 42 а, б - суретінде 
кӛрсетілген. Облыс шекарасында тӛбелер орналасқан, олар бастапқы 
деректердің және шектік мәндердің енгізілуін білдіреді.
Бұл мысалда алгоритмдердің кезкелген компьютерде іске асырылуына 
қатысты ӛте маңызды сұрақ та қарастырылады. Бұған дейін біз оны 
операциялардың параллельді форманың қабаттары бойынша орындалуымен 
байланыстырған болатынбыз. Әрине, бір қабаттың операциялары бір-біріне 
тәуелді емес және оларды әр түрлі құрылғыларда бір мезгілде орындауға 
болады. Бірақ, параллель есептеуді осылай ұйымдастырудың тиімділігі ӛте 
тӛмен болуы мүмкін. 42, а – суретте, (2.13) алгоритмінің максималды 
параллель формасының барлық ярустары пунктирлі сызықтармен 
кӛрсетілген. Операциялар осы ярустар бойынша орындалады делік. 
Бір ярустың (2.14) түріндегі әрбір операциясы үш аргументті талап 
етеді. Олар алдыңғы яруста орындалған операциялардың нәтижелері болып 
табылады. Егер, бір яруста алынған деректердің жадыдан тез алынуы мүмкін 
болса, онда алгоритмді параллель форманың ярустары бойынша іске асыруда 
ешқандай маңызды қиыншылықтар туындамайды. Дегенмен, үлкен 

134 
кӛпӛлшемді есептер үшін ярустар үлкен масштабты болып, олар туралы 
ақпарат жылдам жадқа сыймай қалуы мүмкін. Онда оларды орналастыру 
үшін баяу жадты пайдалануға тура келеді. Бұл жады үшін бір санның таңдалу 
уақыты (2.14) базалық операциясының орындалу уақытынан әлдеқайда асып 
түседі. Ол дегеніміз кезекті ярусқа ӛту кезінде операцияны орындауға 
жұмсалған уақыт жадымен ӛзара қатынас уақытынан біршама аз уақытты 
алуы мүмкін дегенді білдіреді. Операцияның орындалу уақытының жадыға 
қатынау уақытына қатынасы неғұрлым аз болса, параллель форманың 
ярустары бойынша (2.13) алгоритмін іске асырудың тиімділігі соғұрлым 
тӛмен болады. Бұл жағдайда, параллель компьютердің жұмыс уақытының 
басым бӛлігі есептеуге емес, баяу жадпен деректер алмасуға жіберіледі. 
42 сурет. Графтағы микро және макропараллельділік 
Қандай да бір тәсілдермен (2.13) алгоритміндегі баяу жадтың 
қолданылу тиімділігін арттыруға болады ма, егер болса қалай? Бұл сұрақтың 
жауабын алгоритм графын тереңірек зерттеу арқылы ала аламыз. Алгоритм 
графында 42, а горизонталь ярустарымен параллель формадан бӛлек, кӛлбеу 
ярустарымен жалпыланған параллель формалар да бар. Мысалы 
жалпыланған параллель формаларды i + j = const және i - j = const 
түзулерінде ярустарға тӛбелерді жинақтау арқылы алуға болады. Осындай 
ярустардың кейбірі 42, б-суретте пунктирлі сызықтармен кӛрсетілген. 
Белгіленген ярустар графтың берілу облысын кӛпқырларға бӛледі. Енді (2.13) 
алгоритмін алынған кӛпқырлар бойынша параллель іске асыруға болады. 
Сонымен қатар, бір кӛпқырға қатысты барлық операциялардың орындалуы 
барлық уақытта бір процессорға жүктеледі. Параллель орындалу кезінде ең 
алдымен 44, б-суретіндегі штрихталған тӛмендегі кӛпқырларға сәйкес 
операциялар орындалады. Одан кейін жанындағы кӛрші штрихталмаған 
кӛпқырларға сәйкес келетін операциялар параллель орындалады және т.с.с. 
Жаңа процесте бір кӛпқырдың операциялары макрооперацияға 
айналады. Макрооперацияның орындалу уақыты кӛпқырдағы тӛбелердің 
санымен анықталады, ол шамамен кӛпқырдың ауданына пропорционал. 
Кӛпқырлар ӛзара ақпараттық байланысты шекара маңында жатқан тӛбелер 
арқылы жүзеге асырады. Яғни, макрооперацияның орындалуы үшін қажетті 

135 
ақпаратты жадтан алу уақыты, кӛпқырдың шекарасының ұзындығымен 
анықталады. Кӛпқырлардың ӛлшемдерін еркін таңдауға болады. Олар тек 
жалпыланған 
параллель 
формалардың 
қандай 
ярустары 
олардың 
шекараларын құрайтынына байланысты болады. 
Әрқашанда графтың берілу облысын бӛлуді, ондағы кӛпқырлардың 
басым кӛпшілігінің шекара ұзындықтарының олардың аудандарына 
қатынастары ӛте аз болатындай етіп таңдауға болады. Бұндай 
макрооперациялардың орындалуы кезінде баяу жадқа қатынасу уақытының 
әсері ӛте қатты тӛмендейді. 
Осы уақытқа дейін алгоритмдердің параллель формалары негізінен 
тәуелсіз операциялардың жиынын анықтау үшін қолданылып келді десе 
болады. Осы мысал кӛрсеткендей, олар баяу жадтың тиімді пайдаланылу 
мүмкіндіктерін зерттеу үшін де пайдасы болуы мүмкін екені анық. Айта кету 
керек, жоғарыда жасалған ой, пікірлер параллель компьютерлер және кәдімгі 
қарапайым компьютерлер үшін де бірдей орынды болады. 
Жоғарыда 
қарастырылған 
мысалдар 
кӛрсеткендей, 
кӛптеген 
алгоритмдерде шынында да параллельділіктің үлкен қорлары бар. 
Параллельділікті анықтау үшін немесе оның жоқ екенін бекіту үшін 
алгоритмдердің графтарын және олардың параллель формаларын білу үлкен 
роль атқарады. Сонымен қатар, алгоритмдер графтарын және олардың 
параллель формаларын, компьютерлерде (параллель болуы міндетті емес) 
алгоримдерді іске асыруға қатысты кӛптеген басқа сұрақтарды шешу үшін де 
тиімді қолдануға болатыны белгілі.

жүктеу/скачать 2,81 Mb.

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