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

122 
болатын параллель алгоритмді береді. Бірақ-та биіктігі s-ке айтарлықтай 
әлсіз тәуелді болатын алгоритмді қалай тұрғызу керек екені және ондай 
алгоритмдердің бар болуы мүмкін екені туралы айқындылық жоқ. 
Рекурренттік қатынасты (2.1) - матрица және реті үлкен векторлар 
арқылы біршама басқаша жазуға болады: 
























































1
...
1
0
...
0
0
0
...
0
...
..........
..........
0
0
0
...
...
1
...
2
1
1
1
1
1
r
i
i
i
i
ir
ir
i
r
i
i
i
x
x
x
E
E
E
b
A
A
A
x
x
x
Матрицаны Q
i, 
ал сол жағындағы векторды у
i
арқылы белгілейік. Онда
s
i
y
Q
Q
Q
y
Q
у
i
i
i
i
i







1
)
(
...
0
1
1
1
Матрица мен векторлардың реті nr + 1. Екіеселену алгоритміне сәйкес, 
макрооперациялары ретінде реті nr + 1 болатын екі матрицаны кӛбейтуді 
орындайтын 
ns+1 
макропроцессорды 
пайдаланып, 
барлық 
0
1
1
)
(
y
Q
Q
Q
i
i

кӛбейтулерін [log
2
(s+1)] макроқадамда есептеуге болады. 
Екі матрицаның кӛбейтіндісін табу үшін тұрғызылған параллель алгоритмді 
ескере отырып, биіктігі log
2
× log
2
nr және ені (nr)
3
s болатын барлық x
1
, x
2
, …, 
x
s
векторларын есептеу үшін енді параллель алгоритмді жеңіл тұрғызуға 
болады. Бұл алгоритм процестің рекурренттік екіеселену атына ие болды. 
Суреттелген процестің, (2.1) теңдігіндегі х
i
векторларын тікелей 
есептеуге негізделген алгоритмнен принципиалды айырмашылықтары бар. 
Екі алгоритм дәл есептеулер жағдайында ғана бірдей нәтижелер береді. (2.1) 
сияқты рекурренттік қатынастарды қолдана отырып сызықтық алгебраның, 
математикалық физика және анализдің және т.б. кӛптеген сандық әдістері 
тұрғызылған. Рекуренттік екі еселену процесі егер де біз процессорлардың 
үлкен санын қолдана отырып, биіктігі кіші алгоритмдерді құрастыру 
жағынан қарайтын болсақ бұл әдістерден не күтетінімізді түсінуге жол 
кӛрсетеді. Мысалы реті n нӛлдік емес үшбұрышты матрицалы сызықтық 
алгебралық теңдеулер жүйесі шешілуде делік. Бір параллель қадамда, 
шамамен n
2
/2 процессорларды пайдалана отырып, матрицаның барлық 
диагональ элементтерін 1-ге тең етуге болады. Ол үшін оларға сәйкес 
теңдеулердің коэффициенттерін бӛлеміз. Кері қою әдісі кӛмегімен жүйені 
шеше отырып, біз бірден белгісіздер үшін (2.1) түріндегі рекурентті 
қатынастарды аламыз. Бұл теңдеулерде барлық матрицалар мен векторларды 
сандар кӛрсетеді, x
0
= 0, r = i, s= n. Демек, рекурренттік екіеселену процесін 
қолдану арқылы, үшбұрышты жүйені 0(log
2
2
n) параллель қадамда, 0(n
3
) 
процессорларды іске қоса отырып шешуге болады. 
Енді, реті n квадраттық матрица А үшін кері матрицаны А
-1
есептеу 
тапсырмасын қарастырайық. Жылдам параллель алгоритмді құрастыру 
негізін келесі идея құрайды. А матрицасының характеристикалық 

123 
кӛпмүшелігін былай белгілейік: 
n
n
n
c
c
f





...
)
(
1
1



. Кели-Гамильтонның 
теоремасына сәйкес f(А) = 0 болатыны белгілі. Сондықтан
)
...
(
1
1
2
1
1
1
E
c
A
c
A
c
A
n
n
n
n









(2.2) 
Егер λ
i
- характеристикалық теңдеудің түбірлері және s
k
- А
k
матрицаcының 
іздері (след матрицы) болса, онда λ
i
және s
k
Ньютон қатынастарын деп 
аталатын байланыста болады. 
.
...
...
.......
....
..........
..........
3
2
1
3
2
1
3
2
1
1
2
1
1
2
1



















































n
n
n
n
s
s
s
s
c
c
c
c
n
s
s
s
s
s
s
(2.3) 
А матрицасының кері А
-1
матрицасын анықтаудың параллель алгоритмі 
келесі этаптардан тұрады. Алдымен екіеселену схемасы бойынша А 
матрицасының біріншісінен бастап (n - 1)-ге дейінгі барлық дәрежелері 
табылады. Бұл этап log
2
n макроқадамдардан тұрады және мұндағы әрбір 
макроқадам реті n екі матрицаның саны n/2 аспайтын кӛбейтулерін есептеу. 
Барлық бірінші этап 0(n
4
) процессорларда 0(log
2
2
n) параллель қадамда 
орындала алув мұмкін. Ал екінші этапта А
к
матрицаларының барлық s
к
іздері 
0(log
2
n) қадамда 0(n
2
) процессорларын пайдалана отырып есептеледі. Ал 
үшінші этапта 0(log
2
2
n) қадамда 0(n
3
) процессорларын пайдалана отырып 
(2.3) үшбұрышты жүйені шешу арқылы характеристикалық теңдеудің с
к
коэффициенттері табылады. Ал тӛртінші этапта (2.2) формуласына сәйкес 
0(log
2
n) параллель қадамда 0(n
3
) процессорларын пайдалана отырып А
-1
матрицасы табылады. Тұтас алғанда А
-1
матрицасын есептеудің параллель 
алгоритмінің биіктігі 0(log
2
2
n) және ені 0(n
4
). Дәл қазіргі уақытта осы есепті 
шешу үшін биіктіктері бұдан әлдеқайда кіші болатын алгоритмдер 
анықталмаған. Ал алгоритмнің ені азайтылуы мүмкін.
Егер реті n - ге тең квадрат А матрицалы Ах = в сызықты алгебралық 
теңдеулер жүйесі шешілетін болса, онда параллель алгоритм ӛте оңай 
құрылады. Жүйе шешімін х = А
-1
в түрінде елестетіп кӛрейік. Алдымен, 
0(log
2
2
n) параллель қадамда 0(n
4
) процессорларын қолданып А
-1
матрицасын 
табамыз. Одан соң 0(log
2
n) параллель қадамда 0(n
2
) процессорларын 
қолданып А
-1
матрицасы мен в векторының кӛбейтіндісін х = А
-1
в, яғни 
шешімін табамыз. 
Шексіз параллельділік концепциясы шеңберінде кӛптеген биіктігі кіші 
алгоритмдер құрастырылды. Олардың кейбіреулерін [31] жұмыста және сол 
тақырыптарға берілген әдебиеттерден кездестіруге болады. Сондықтан да біз 
оларды талдамай – ақ қоямыз. Мұның себебі: практика жүзінде бұл 

124 
алгоритмдердің басым кӛпшілігі толық қолданыс таппаған. Оларға тән ортақ 
кемшіліктердің біразын айта кетсек: процессорлар сандарын кӛп қажет ету, 
операциялар арасындағы күрделі ақпараттық байланыс, сандық есептеудегі 
орнықсыздықтар, жадыдағы келіспеушіліктер санының кӛп болуы және т.б. 
Шексіз параллельділік концепциясының толық талдауын [10] кітаптан табуға 
болады. Айтылған кемшіліктерге қарамастан, кітапта біз осы концепция 
туралы қысқаша қарастырып кеттік. 

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

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