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

126 
бір нәтижеге алып келеді. Қандай да бір ойлардың нәтижесінде (2.4) 
формуласын іске асырудың келесі алгоритмі таңдалған делік: 
.
...,
,
2
,
1
,
,
,
,
0
)
(
)
1
(
)
(
)
0
(
n
ij
ij
kj
ik
k
ij
k
ij
ij
a
a
n
k
j
i
c
b
a
a
a






(2.5) 
 
Тағы да i, j индекстерін іріктеу параллельділігі анық кӛрсетілген. 
Бірақта к индексі бойынша паралллельділік жоқ, себебі (2.5)–тің ортаңғы 
формуласынан кӛріп отырғанымыздай, ол индекс 1-ден бастап n-ге дейін 
тізбекті түрде іріктелуі керек. 
Енді (2.5) алгоритмінің графын тұрғызайық. Граф тӛбелері a + bс 
түріндегі операцияларға сәйкес келеді деп есептейміз. Мұндағы a, b, с 
сақинаның (дӛңгелектің) элементтері, және А, В, С матрицаларының 
элементтері сол дӛңгелекке тиесілі. Кӛрнекілік үшін оларды сан ретінде 
қарастырса да болады, бірақ олар мысалы, реті бірдей квадрат матрицалар 
болуы да мүмкін. Графты тұрғызу барысында a, b, с элементтерінің 
табиғатын ескермейміз. Алғашында графта В, С матрицалары элементтерінің 
ендірілуімен және А матрицасының элементтеріне есептелінген a
ij
(n)
мәндерін 
беруге байланысты болатын тӛбелерді және оларға инцидентті доғаларды да 
кӛрсетпейміз. Алгоритм графының зерттелуіне ақталмаған қосымша 
қиындықтарды ендірмес үшін, граф тӛбелерін еркін түрде орналастыруға 
болмайды. Оларды орналастырудың қолайлы да тиімді тәсілін (2.5) 
формуласының жазылу түрі кӛрсетіп тұр десе болады. Тік бұрышты торды 
үшӛлшемді кеңістікте i, j, к координаталарымен қарастырайық. Тордың 
барлық бүтінсанды тораптарына 1 ≤ i, j, к ≤ n үшін граф тӛбелерін 
(шыңдарын) 
орналастырамыз. 
(2.5) 
формуласын 
талдай 
отырып, 
координаталары i, j, к болатын тӛбеге к > 1 үшін, координаталары i, j, к - 1 
болатын тӛбеге сәйкес келетін операцияның орындалу нәтижесі берілетініне 
кӛз жеткізу қиын емес. 
37 сурет. Матрицаларды кӛбейту графы 

127 
Алгоритм графы жеткілікті дәрежеде қарапайым тұрғызылған. Ол n² ӛз 
ара байланыспаған подграфтарға ыдырайды. Әрбір подграф к осіне 
паралллель орналасқан бір жолды кӛрсетеді және n тӛбеден тұрады. 
Күткеніміздей, (2.4) және (2.5) жазбаларындағы анық кӛрсетілген сол 
параллельділік осы графта да кӛрсетілген. Алгоритм графы n = 2 үшін 37, а
суретте келтірілген. Толық графта мәліметтерді кӛптеп жіберу кездеседі.
b
ik
элементтері координаталарының мәндері i, k болатын барлық 
тӛбелерге, ал с
kj
- координаталарының мәндері k, j болатын барлық тӛбелерге 
жіберіледі. n = 2 үшін бұл таратылым 37, б-суретте келтірілген. Графтың 
барлық тӛбелері a+bс түріндегі операцияларға сәйкес келеді. Бірақ k = 1 
болғанда олар k ≠ 1 қарағанда бірсыпыра басқаша орындалады. Осы 
жағдайда а аргументі қандайда бір операцияның нәтижесі болмайды, ал 
әрқашанда 0-ге тең деп алынады. k = 1 болғанда 0-ді алгоритмнің кіріс дерегі 
деп алып, оны барлық тӛбелерге таратылуына еш кедергі болмайды. 
Бұл мысал алгоритм графы тӛбелерін орналастырудың дұрыс тәсілін 
таңдаудың қаншалықты маңызды екенін жақсы кӛрсетеді. Егер, мысалы, 
тӛбелерді түзу сызық бойына орналастырса және олар (2.5)-гі i, j, к 
индекстерімен ешқандай байланыссыз болса, онда бұндай графта 
параллельділікті байқау сірә мүмкін емес те болар. Тӛбелердің таңдалған 
орналастырылуы бойынша паралллельділік айқын. Олай болса кезкелген 
паралллель форманың кезкелген ярусын (қабатын) жеңіл кӛрсетуге болады. 
Бұл дегеніміз бекітілген i, j кезінде бір тӛбеден артық кірмейтін тӛбелер 
жиыны. 
Канондық 
параллель 
форманың 
ярустары 
k 
= 
const 
гипержазықтығында жататын тӛбелер жиынын құрайды. Сондықтан, 
тӛбелерді орналастыру тәсілін алгоритмнің жазылуында пайдаланылатын 
индекстер жүйесімен байланыстыруға тура келетіні айқын. Берілген, яғни 
матрицаларды кӛбейту мысалы мұндай тәуелділікті анық кӛрсетіп тұр. 
Егер (2.4) ӛрнегіндегі қосындыны екіеселену схемасы бойынша 
орындайтын болсақ, онда алгоритм графы мүлдем бӛлек болатынын 
байқаймыз. Бұл жағдайда 37, а – суретіндегі графтың әрбір жолы, 36 - 
суреттегі тӛменгі графқа ауыстырылуы керек. Енді жаңа графты үш ӛлшемді 
кеңістікте орналастыру қиындау болады. Екіеселену қағидасын қолданып 
(бір индексті пайдаланып) қосындыны жазу да айтарлықтай қиыншылықтар 
туғызады. 

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

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