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 -
суреттегі тӛменгі графқа ауыстырылуы керек. Енді жаңа графты үш ӛлшемді
кеңістікте орналастыру қиындау болады. Екіеселену қағидасын қолданып
(бір индексті пайдаланып) қосындыны жазу да айтарлықтай қиыншылықтар
туғызады.
Достарыңызбен бөлісу: