Программа дисциплины для студентов

p
88

50

28

25

Слияние

88

50

25

88

80

43

42

25

98

80

42

қ
43

42

28

25

20-сурет. Екі ішкі тізімді біріктіру. Схема 1.

98

80

42

88

80

43

42

25

98

80

42

50

28

50

28

Исходные числа

Хранит большие числа (конечные числа)

21-сурет. Екі ішкі схеманы біріктіру. Схемасы 2.

Сонымен, екі ішкі тізімді жалпы әдісі төмендегідей:

Әрбір процедурада сұрыпталған тізімді сақтау керек және енгізу тізімі бар сақталған тізімі.

Біз саннан тұратын тізім бар деп есептейміз, ол алғашында 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 қосу амалы).

Бұл пунктте біз сызықтық теңдеулер жүйесін шешудің тура әдісімен қарастырамыз: белгісіздерді шығарып тастау – Гаус әдісі және итерациялық әдіс Якоби әдісі.

Гаусс әдісі

Ах=b сызықтық алгебралық теңдеулер жүйесін шешу қажет болсын.

Мұндағы

А – берілген коэффициенттер матрицасы

b- берілген вектор

х-белгісіз вектор

белгісіздерді шығару әдісі – Гаус әдісі А матрицасын көбейткіштерге жіктеуден тұрады:

PA=LU

L – төменгі үшбұрыш матрица

U – жоғарғы үшбұрыш матрица

Р-ауыстыру матрицасы, яғни Р – А сияқты матрица, бірақ оның жолдары ауыстырылған.

Сонымен, біз үшбұрыштың теңдеулер жүйесін шешеміз:

Ly=Pb және Ux=y

Алдымен у-ті, одан кейін х-ті табамыз.

PA=LU

А матрицасының жолдарын Р-ға реттеуді pivoting (беру) деп аталады. Бұл сандық орнықтылық үшін қажет.

Біз жартылай бұрудың стандарт схемасын қолданамыз: бұл L оның диагоналлінде 1-лер бар және басқа элементтері модуль бойынша 1-мен шектелген деген сөз.

Гаусс әдісінің қарапайым нұсқасы – бас элементті таңдау. Ол А матрицасының бір жолдарын басқа жолдарға қосып, диагональ астындағы элементтерін 0-ге айналдыру керек. Сонда Гаусстың алгоритмінің тізбекті коды мынадай:

?

Ары қарай біз A(I,j,k,l) белгілеуін қолданамыз, бұл i-ден j-ге дей3н жолдары ж2не к-дан 1-ге дейінгі бағандары бар ішкі матрица деген сөз.

?

Бір қатарын түрлендіру ең үлкен жұмыс, түрлендіру өзінен кейін (n-k)x(n-k) өлшемді A(k+1:n,k+1:n) ішкі матрицасын алып жүреді, олардың әрбіреуі паралель жаңартылуы мүмкін.

?

хабар беру бір қадамда жасауы мүмкін деп санайық, n-1 хабар беру болады,олар тізбекті орындалу керек, өйткені жолдар әрбір хабар беру аралығында өзгереді, I – ші хабар беру n-i+1 элементтен тұрады.

жол жіберілген кейін, әрбір pi процессорынан жоғары pi процессоры хабар алады, оның көбейткішін есептейді, және берілген жолдың n-j+2 элементіне әсер етеді. Көбейткіштерді есептеуді ескермей n-j+2 көбейтінді және n-j+2 айырыма жасау қажет.

a[][] және b[] теңдеу тұрақтыларынан тұратын белгісіздерден тұратын x[] массиві берілген, сондай-ақ қажетті итерациялар санын (limit) таптық деп есептейік, сонда Якоби алгоритмінің тізбекті коды келесі түрде көрсетіледі.

For (i=; i

{x[i]=b[i];

for (it=0; it

{for (i=0; i

{ sum=0;

for (j=0; j

if (i!=j) sum=sum+a[i][j]*x[j];

new_x[i]=(b[i]-sum/a[i][j];}

for (i=0; iОсы кодты паралельдейміз. Кез келген белгісіз үшін бір процесс белілген және әрбір итерацияда жақын арада есептелінген белгісіздер саны басқа барлық процесстерге берілуі керек.

Паралель кодта біз нақты бір барьер қосылуы керек, pi процессі төмендегі түрде болады:

x[i]=b[i];

for()it=0;it

{ for()j=0;j

sum=sum+a[i][j]*x[j];

new_x[i]=(b[i]-sum/a[i][j];

broadcast_receive(&new_x[i]);

global_barrier();}

Хабар беру шаблоны - broadcast_receive(), жақын арада есептелген x[i] мәнін процесінен басқа кез-келген процеске жібереді және басқа процесінен жіберген деректерді жинайды.

Сонда есептеу уақыты:

Ал байланыс уақыты: