AxВ матрицаларды көбейтудің тізбекті коды былай болуы мүмкін:
For (i=0; i<n; i++)
For (i=0; j<n; j++)
{
c[i][j]=0
For (k=0; k<n; k++)
C[i][j]=c[i][j]+a[i][k]b[k][j];
}
Берілген алгоритм n алгоритмді қажет етеді, яғни тізбекті орындалу уақыты О(n).
Матрицаларды блокпен көбейту
әрбір берілген матрицаны ішкі матрица деп аталатын элементтер блогына бөлеміз (Ananth Gama, Anshul Fupta and George Karypis6 Vipin Kumar,2003). Біздің жағдайымызда біз s ішкі матрица аламыз (s көлденең, s төмен).
әрбір ішкі матрицаның х элементтері болады (n/s-ті m деп белгілейміз).
Сонымен, А — ішкі матрица, мұндағы р-жолдар номері, ал q-бағандар номері.
Матрицаларды көбейтудің паралель коды келесі түрде анықталуы мүмкін. (23-сурет):
Матрицаларды блокпен көбейту
берілген алгоритмнің орындалу уақытын бағалайық:
Каннон алгоритмі
p процессорлар торус типті желімен байланысқан делік..
А,В,С – рхр блокты матрица, әрбір квадрат блок 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
Көбейткіштерге жіктеуі жылжымалы нүктесі бар ең үлкен амалдар санына тұрады, 2n/3+O(n).
А матрицасының жолдарын Р-ға реттеуді pivoting (беру) деп аталады. Бұл сандық орнықтылық үшін қажет.
Біз жартылай бұрудың стандарт схемасын қолданамыз: бұл L оның диагоналлінде 1-лер бар және басқа элементтері модуль бойынша 1-мен шектелген деген сөз.
Гаусс әдісінің қарапайым нұсқасы – бас элементті таңдау. Ол А матрицасының бір жолдарын басқа жолдарға қосып, диагональ астындағы элементтерін 0-ге айналдыру керек. Сонда Гаусстың алгоритмінің тізбекті коды мынадай:
Ары қарай біз A(I,j,k,l) белгілеуін қолданамыз, бұл i-ден j-ге дей3н жолдары ж2не к-дан 1-ге дейінгі бағандары бар ішкі матрица деген сөз.
Сонда берілген алгоритмнің параллель кодын былай жазуға болады (Ananth Gama6 Anshul Fupta and George Karypis6 Vipin Kumar6 2003):
Бір қатарын түрлендіру ең үлкен жұмыс, түрлендіру өзінен кейін (n-k)x(n-k) өлшемді
A(k+1:n,k+1:n) ішкі матрицасын алып жүреді, олардың әрбіреуі паралель жаңартылуы мүмкін.
Процессорлер конвейерлік онфитгурацияға қайта құрылуы мүмкін.
хабар беру бір қадамда жасауы мүмкін деп санайық, n-1 хабар беру болады,олар тізбекті орындалу керек, өйткені жолдар әрбір хабар беру аралығында өзгереді, I – ші хабар беру n-i+1 элементтен тұрады.
Сонымен, өзарабайланысты қажетті уақыт:
tcomm= +(n-i+1)t=
=(n-1)tt
жол жіберілген кейін, әрбір piпроцессорынан жоғары pi процессорыхабар алады, оның көбейткішін есептейді, және берілген жолдың n-j+2 элементіне әсер етеді. Көбейткіштерді есептеуді ескермей n-j+2 көбейтінді және n-j+2 айырыма жасау қажет.
Сонымен, жалпы есептеу уақыты:
tcomp=2
Якобиитерациялық әдісі
a[][] және b[] теңдеу тұрақтыларынан тұратын белгісіздерден тұратын x[] массиві берілген, сондай-ақ қажетті итерациялар санын (limit) таптық деп есептейік, сонда Якоби алгоритмінің тізбекті коды келесі түрде көрсетіледі.
For (i=; i<n;i++)
{x[i]=b[i];
for (it=0; it<limit; it++)
{for (i=0; i<n; i++)
{ sum=0;
for (j=0; j<n; j++)
if (i!=j) sum=sum+a[i][j]*x[j];
new_x[i]=(b[i]-sum/a[i][j];}
for (i=0; i<n; i++) x[i]=new_x[i];}
Осыкодты паралельдейміз. Кез келген белгісіз үшін бір процесс белілген және әрбір итерацияда жақын арада есептелінген белгісіздер саны басқа барлық процесстерге берілуі керек.
Паралель кодта біз нақты бір барьер қосылуы керек, pi процессі төмендегі түрде болады:
x[i]=b[i];
for()it=0;it<limit; it++
{ for()j=0;j<n; 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] мәнін процесінен басқа кез-келген процеске жібереді және басқа процесінен жіберген деректерді жинайды.
Сонымен, broadcast_receive() n хабар беруден тұруы керек, олардың әрбіреуі белгілі бір параметрмен.
Біз теңдеу n және p процессоры бар делік. Процессор n/р белгісіздерін амал орындайды. — итерациялар саны. Бір итерацияда есептеу фазасы және байланыс фазасы бар.
Сонда есептеу уақыты:
t=n/p(2n+4)
Ал байланыс уақыты: