БАҒдарламасы ( Syllabus ) Павлодар, 2014ж Пән бағдарламасы (Syllabus) ф фсо пгу 18. 4/19 бекітемін фмжат факультетінің деканы Н. А. Испулов

Біз саннан тұратын тізім бар деп есептейміз, ол алғашында d өлшемді гиперкуб торабының біреуіне орналастырылған. әрбір тораптың сәйкес номері бар.

P0

4

2

7

8

5

1

3

6

P0

P4

P2

P6

8

7

		P0 P1 P6 P8

6

Pivot

Жоғарыда сипатталған жылдам сұрыптау алгоритмінің процесі келесі схемада сәйкес көрсетіледі:

1-қадам: 000 001 (числа, большие чем pivot, идут на Р1)

2-қадам: 000 010 (числа, большие чем pivot, идут на Р2)

001 011 (числа, большие чем pivot, идут на Р3)

3-қадам: 000 100 (числа, большие чем pivot, идут на Р4)

001 101 (числа, большие чем pivot, идут на Р5)

010 110 (числа, большие чем pivot, идут на Р6)

011 111 (числа, большие чем pivot, идут на Р7)

Соңында осы бөліктер тізбекті алгоритмді қолдана отырып сұрыпталуы мүмкін, ал бәрі бірге параллель.

● Матрицаларды блокпен көбейту

● Каннон алгоритмі

● Страссен алгоритмі

● Гаусс әдісі

● Якобидің итерациялық әдісі

AxВ матрицаларды көбейтудің тізбекті коды былай болуы мүмкін:

For (i=0; i

For (i=0; j
{

c[i][j]=0

For (k=0; k

C[i][j]=c[i][j]+a[i][k]b[k][j];

Матрицаларды көбейтудің паралель коды келесі түрде анықталуы мүмкін. (23-сурет):

C21 C22

B21 B22

A21 A22

= X

23-сурет. Матрицаларды блокпен көбейту

берілген алгоритмнің орындалу уақытын бағалайық:

?

Каннон алгоритмі

А,В,С – рхр блокты матрица, әрбір квадрат блок n/p дәрежелі (I,j) блокты (I,j) процесске орналастырайық әрбір процесс келесі схемамен жұмыс істейді:

Қадам 1.

● А матрицасындағы менің блогымды I орынға батысқа жылжытамыз.

● В матрицасындағы менің блогымды j орынға солтүстікке жылжытамыз.

● менің С блогымды оған А және В-ң менің жаңа блоктарымен көбейтіндісін қосу арқылы түрлендір.

Қадам k,k=2,3, …, p.

● А матрицасындағы менің блогымды бір орынға шығысқа жылжытамыз.

● В матрицасындағы менің блогымды бір орынға оңтүстікке жылжытамыз.

● менің С блогымды оған А және В-ң менің жаңа блоктарымның көбейтіндісін қосу арқылы түрлендір.

Сұрақ: каннон алгоритмінің орындалуы қандай?

Страссен алгоритмі

А,В және С-ны 2х2 блоктар матрицасына бөлейік. Әдеттегі алгоритм матрицалардың 8 көбейтіндісінен тұрады (және 4 қосу амалы). Старссен алгоритмі келесі қадамдардан тұрады:

Анықтаңдар

Сонымен, матрицаларды көбейтудің жалпы саны =7 (және 18 қосу амалы).