Лентови алгоритми за умножение на матрица, DPT
Формулиране на проблема
Матрицата е математически обект, написан под формата на правоъгълна таблица от елементи на пръстен или поле, която представлява съвкупност от редове и колони, в пресечната точка на която се намират нейните елементи. Броят на редовете и колоните на матрицата определя размера на матрицата (wiki). Действието на матричното умножение е една от основните задачи на матричните изчисления. Умножението на матрица A с размер височина A * ширина A и матрица B с размер височина B * ширина B (ширина A е равна на височина B) води до матрица C с размер височина A * ширина B, всеки елемент от който се определя от точковото произведение на съответния ред на матрица A и колона от матрица B.
В тази работа е поставен проблемът да се приложат два паралелни алгоритма за умножение на матрица със схема на раирано представяне на данни.
Метод на решение
1. Последователен алгоритъм
Този алгоритъм предполага изпълнението на операции за умножение на височинаA * widthA * widthB и същия брой операции на събиране на елементите на оригиналните матрици. При умножаване на квадратни матрици с размер n * n, броят на извършените операции е от порядъка на O (n 3).
Този алгоритъм е итеративен и фокусиран върху последователното изчисляване на редовете на матрицата C. Всъщност, когато се извършва една итерация на външния цикъл (цикъл над променлива i), се изчислява един ред от получената матрица.
Тъй като всеки елемент от получената матрица е скаларен продукт на ред и колона от оригиналните матрици, за да се изчислят всички елементи на матрицата C с размер n * n, е необходимо да се изпълни n 2 * (2 n - 1) скаларни операции и прекарване на време T1 = n 2 * (2 n - 1) * t, където t е времето за изпълнение на една елементарна скаларна операция.
2. Паралелна верига
Изчисляването на всички елементи на матрицата C = A x B може да се извърши независимо един от друг. Оригиналните матрици могат да бъдат разделени на блокове, всеки от които от своя страна ще бъде прехвърлен в съответния процес.
За да се изчисли редът на матрица C, е необходимо всяка подзадача да съдържа ред (редове, ако предаденият блок на тази матрица съдържа повече от един ред или броят на процесите е поне 2 пъти повече от броя на редовете в matrix) на матрица A и достъп до всички колони на матрицата B.
Има различни начини за организиране на паралелни алгоритми:
Този алгоритъм е итеративна процедура. Оригиналните матрици са разделени на блокове. Броят на тези блокове зависи от броя нишки в програмата. При всяка итерация на алгоритъма всички подпроблеми съдържат един или няколко реда матрица А и една или повече колони матрица Б. При изпълнение на итерацията блоковете, съдържащи се в подпроблемите, се умножават скаларно един от друг, което води до получаване на съответния блок от елементи в изчислената матрица C. След завършване на изчисленията в края на всяка итерация колоните на матрица B трябва да се прехвърлят между подзадачи, така че всяка подзадача да съдържа нови блокове от тази матрица, за да продължи изчисленията на матрица C. последната стъпка се прехвърлят останалите редове от матрици A и B. По този начин се намира матрица C. Броят на подзадачите зависи от броя на редовете в блокове, предадени на нишки. Например, ако всеки блок съдържа само един ред от началните матрици A и B, тогава избраните основни подзадачи се характеризират със същата изчислителна сложност, равна на n 2 (от броя на елементите на матрица C).