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

128 
Қосу реті анықталмағандықтан, бұл ӛрнек те алгоритмді бірмәнді 
анықтамайды. Мысалға, j индексінің ӛсуіне қарай тізбекті қосуды 
қарастырайық. Сәйкес алгоритмді келесі түрде жазуға болады 
.
,
1
...,
,
2
,
1
,
...,
,
2
,
1
,
,
)
1
(
)
1
(
)
1
(
)
(
)
0
(










i
i
i
j
j
ij
j
i
j
i
i
i
x
x
i
j
n
i
x
a
x
x
b
x
(2.7) 
 
Алгоритмнің ең негізгі операциясы a-bс түрінде берілген. Бұл барлық 
мүмкін болатын i, j индекстерінің мәндері үшін орындалады. Қалған 
операциялардың барлығы меншіктеуді орындайды. Мұнда да алгоритм 
графын тұрғызу кезінде операцияларды қарапайым қайта нӛмірлеу тиімсіз 
екені кӛрінеді. Декарттық координат жүйесінде (i, j ӛстерімен) қадамы 1-ге 
тең болатын тікбұрышты координаталық торды тұрғызайық және тор 
тораптарына (түйіндеріне) a-bс операцияларына сәйкес келетін  2 ≤ i ≤ n, 1 ≤ j 
≤ i-1 үшін граф тӛбелерін орналастырайық. Операциялар арасындағы 
байланысты талдай отыра, алгоритм графын тұрғызамыз және оған кіріс a
ij 
және
 
b
i
, деректерін білдіретін тӛбелерді енгіземіз. Бұл граф n=5 жағдайы үшін 
38, а - суретте кӛрсетілген. Жоғарғы бұрыштағы тӛбе i=1, j=0 координаталы 
нүктесінде орналасқан.
38 сурет. Үшбұрышты жүйелерге арналған графтар 
Бұл суретте параллельді форманың ең максималды түрінің бірі 
кӛрсетілген. Оның ярустары пунктирлі сызықтармен белгіленген. Егер a
ij
элементтерінің енгізілуіне сәйкес келетін тӛбелерді бірінші яруске 
орналастырса, онда параллельді форма канондық болады. а — bс түріндегі 
операциялар енетін ярустардың жалпы саны n - 1 тең. Бірінші яруста b 
векторының элементтерін енгізу операциялары орналасқан.
Егер (2.6) ӛрнегіндегі қосындыны есептеуде біз қандай да бір оймен 
қосудың тізбекті әдісіне тоқтаған болсақ, онда j индексінің ӛсуі бойынша 
қосуды таңдау жалпы кездейсоқ жасалған болатын. Бұл таңдаудың қандай да 
бір артықшылықтары кӛрініп тұрмағандықтан кері қоюдың алгоритмін j 

129 
индексінің кемуі бойынша қосу арқылы тұрғызуға болады. Онда оған сәйкес 
алгоритм келесі түрде болады: 
.
,
1
...,
,
2
,
1
,
...,
,
2
,
1
,
,
)
1
(
)
(
)
1
(
)
(
)
(
i
i
j
j
ij
j
i
j
i
i
i
i
x
x
i
i
j
n
i
x
a
x
x
b
x









 
(2.8) 
Оның графы n = 5 жағдайы үшін 40, б-суретте кӛрсетілген. Енді 
жоғарғы бұрыштағы тӛбе координатасы i = 1, j = 1 болатын нүктеде 
орналасады. Қандай да бір параллель форманың ярустарына a - bс түріндегі 
операцияларға сәйкес келетін тӛбелерді орналастыра отырып, ондағы әрбір 
яруста әрқашанда тек бір тӛбе ғана бола алатынын байқаймыз. Бұл 40-шы 
суретте графтың барлық тӛбелері бір жолда жатуымен түсіндіріледі. Бұл жол 
пунктирлі бағыттармен кӛрсетілген. Сондықтан (2.8) алгоритмі графындағы 
a – bc түріндегі операцияларды қамтитын ярустардың жалпы саны әрқашан 
(n
2
 – n + 2)/2 тең болады, бұл (2.7) алгоритмі графындағы n-1 ярустар санына 
қарағанда әлдеқайда кӛп. 
Күтпеген нәтиже алынды десе болады. Шынында, екі алгоритм де (2.7) 
және (2.8) бір ғана есепті шешуге арналған, олар (2.6) бірдей формулалары 
негізінде құрылған және дәл есептеулерге қатысты алсақ эквивалентті. Екі 
алгоритм де бірдей жады кӛлемін және азайту, кӛбейту операцияларының 
бірдей санын талап ететіндіктен, бірпроцессорлы компьютерлерде іске 
асырылу жағынын алғанда олар бірдей.
Дегенмен, екі алгоритм графтарының бір-бірінен айтарлықтай 
айырмашылығы бар. Егер бұл алгоритмдерді n әмбебап процессордан 
тұратын параллель есептеу жүйесінде іске асырса, онда (2.7) алгоритмін n-ге 
пропорционал уақыт ішінде, (2.8) алгоритмін тек n²-қа пропорционал уақыт 
ішінде іска асыруға болады. Бірінші жағдайда процессорлардың орташа 
жүктелуі 0,5-ке, екінші жағдайда 0-ге жуық болады. 
Сонымен, қарапайым компьютерлерде іске асырылуы жағынан 
қарағанда бірдей болатын алгоритмдер, параллель компьютерлерде іске 
асырылу кезінде мүлдем әртүрлі болулары мүмкін. Осы мысалды қолдана 
отырып айта кететін нәрсе, параллель компьютерлерді математикалық 
тұрғыдан игерудің басты қиындықтары да осы фактінің негізінде жатыр. 
Кӛптеген жылдар бойы «қарапайым» компьютерлерде жұмыс істейтін 
әртүрлі мамандық иелері, алгоритмдерді негізінен олардың 3 сипаттамасы 
бойынша бағалайды: операция саны, талап етілетін жадының кӛлемі және 
дәлдігі. Осы сипатттамалар негізінде барлығы дерлік тұрғызылды: есептеу 
техникасының негізгі параметрлері, есептеу ісіне үйрету процесі, есептеу 
әдістері және алгоритмдерін құрастыру, тиімділікті бағалау, тілдерді және 
трансляторларды құрастыру және кӛптеген т.б. Параллель есептеу жүйелерін 
құруда, алгоритмдерден, принципиалды түрде басқа қасиеттері мен 
сипаттамалары талап етілді, ал оларды білу тізбекті компьютерлер үшін 
қажеті де болмаған еді. Сонымен алгоритмдерді тереңірек зерттеу, олардың 
параллель қасиеттерін оқып үйрену, параллельділікті анықтау үшін 

130 
конструктивті әдістемелігін құрастыру қажетті де маңызды іс-шаралардың 
қатарына жатады. 
Математикалық физика теңдеулерін торлар әдістерімен шешу кезінде 
пайда болатын сызықты алгебраның кӛптеген есептерінің ішінде, блокты-
екідиагоналды матрицалы сызықты алгебралық теңдеулер жүйесін шешу 
есебі жиі кездеседі. Мұндағы диагоналдық емес блоктар диагоналды 
матрицалардан тұрады, ал диагональ бойындағы блоктар – екідиагоналды 
матрицалар. Анығырақ болу үшін, жүйенің матрицасы сол жақты 
үшбұрышты болсын деп есептейік. Матрицаның блоктық реті m, ал блок реті 
n болсын. Сонымен, Au = f түріндегі сызықты алгебралық теңдеулер жүйесін 
қарастырайық [10]. 
мұндағы 
(2.9) 
Егер U
0
= 0, D
0
= 0 деп алатын болсақ, блокты – екідиагоналды 
жүйенің (2.9) шешімі рекуррентті анықталады: 
U
k
 = B
k
-1
(F
k
 – D
k-1
U
k-1
), 1 ≤ k ≤ m (2.10) 

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

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