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

119 
5-ші ярус (а
1 
а
2 
а
3 
а
4 
а
5
) а
6
6-ші ярус (а
1
 а
2
 а
3
 а
4
 a
5
 а
6
) а
7
7-ші ярус (а
1
 а
2
 а
3
 а
4
 a
5
 а
6
 а
7
) a
8
Параллель форманың биіктігі 7-ге тең, ені 1-ге тең. Егер есептеу жүйесі 
бірнеше процессордан тұратын болса, онда берілген есептеу схемасы 
бойынша бір процессордан басқасының бәрі барлық қадамда тоқтап тұрады. 
Сандарды кӛбейтуді есептеудің басқа алгоритмінің келесі параллель 
формасы процессорларды тиімдірек пайдаланады: 
Деректер а
1
 а
2
 а
3
 а
4
 a
5
 а
6
 а
7
 a
8
1-ші ярус а
1
а
2
а
3
а
4 
a
5
а
6
а
7
a
8
2-ші ярус (a
1
a
2
)(a
3
а
4
) (a
5
а
6
)(а
7
a
8
) 
3-ші ярус (a
1
a
2
a
3
а
4
) (a
5
а
6
а
7
a
8
) 
Параллель форманың биіктігі 3-ке, ені 4-ке тең. Биіктіктің айтарлықтай 
тӛмендетілуі, процессорлардың пайдалы жұмыс атқаруға біршама толық 
жүктелуінің әсерінен болды. 
Соңғы схема п – нің кез-келген мәні үшін жалғасын табады. Оны іске 
асыру үшін әрбір яруста, алдыңғы ярустан алынған қиылыспайтын сандар 
жұптары кӛбейтінділерінің максималды мүмкін санын алу қажет. Жалпы 
жағдайда параллель форманың биіктігі [log
2
n] тең. Бұл параллельдік форма 
п/2 процессорларда іске асырылады, бірақ бұнда процессорлардың 
жүктелінуі ярустан ярусқа кӛшкен сайын азаяды. Жасалған схема бойынша 
әрбір яруста сандарды тұрғызу процесі екіеселену процесі деп аталады. Бұл 
екіеселену процесінің кӛмегімен, сандарды кӛбейту операциясын кӛпқайтара 
қолдану үшін ғана емес, сонымен қатар кез келген ассоциативті 
операцияларды орындау үшін де (мысалы, сандарды қосу, матрицаларды 
кӛбейту және т.б.) логарифмдік биіктігімен алгоритмдерді құрастыруға 
болады. Назар аударатын болсақ, операцияларды тізбектей қолдану 
алгоритмі және екіеселену алгоритмі - бұлар негізінде әртүрлі алгоритмдер 
болып табылады. Бірақ әртүрлі алгоритм болғанымен ӛздерінің іске асуы 
үшін бірдей операция санының орындалуын талап етеді. Оларға тек қана 
әртүрлі процессорлар саны емес, сонымен қатар әртүрлі коммуникациялық 
желі де қажет. Сонымен қатар бұл алгоритмдерге дӛңгелектеу қателіктерінің 
әсері әр түрлі беріледі және бұл алгоритмдерге бағдарламалар әртүрде 
жазылады. Жалпы жағдайда, оларда алгоритм графынан бастап бәрі әртүрлі 
болып келеді. 36-суретте n=8 болғандағы екі граф келтірілген, жоғарғысы 
операцияны тізбектей қолдану графы, тӛменгісі екіеселену қағидасы үшін 
граф. Бастапқа түйіндер деректердің кірісін кӛрсетеді. 

120 
36 сурет. Тізбектелген және екіеселенген графтар. 
Қарастырылған мысал әдістемелік жағынан ӛте маңызды бір қорытынды 
шығаруға мүмкіндік береді. 

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

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