Методи за умножение на паралелни матрици

7.2. Последователен алгоритъм

Последователният алгоритъм за умножение на матрица е представен от три вложени цикъла:

Алгоритъм 7.1. Пореден алгоритъм за умножение на две квадратни матрици

Този алгоритъм е итеративен и се фокусира върху последователното изчисляване на редовете на матрицата C. Всъщност, когато се извършва една итерация на външния цикъл (цикъл над променливата i), се изчислява един ред от получената матрица (виж фиг. 7.1).

Тъй като всеки елемент от получената матрица е скаларен продукт на ред и колона от оригиналните матрици, за да се изчислят всички елементи на nxn матрицата C, е необходимо да се извършат n 2 x (2n - 1) скаларни операции и прекарвам време

7.3. Умножение на матрица със схема на разделяне на ивици с данни

Помислете за два успоредни алгоритма за умножение на матрици, при които матрици A и B са разделени на непрекъснати последователности от редове или колони (ивици).

7.3.1. Определяне на подзадачи

От дефиницията на операцията за умножение на матрицата следва, че изчисляването на всички елементи на матрицата C може да се извърши независимо един от друг. В резултат на това възможен подход за организиране на паралелни изчисления е да се използва процедурата за определяне на един елемент от получената матрица C като основна подзадача. За да се извършат всички необходими изчисления, всяка подпроблема трябва да съдържа един ред матрица A и една колона матрица B. Общият брой подзадачи, получени с този подход, се оказва равен на n 2 (от броя на елементите на матрицата C).

След разглеждане на предложения подход може да се отбележи, че постигнатото ниво на паралелизъм в повечето случаи е излишно. Обикновено при извършване на практически изчисления такъв брой формирани подзадачи надвишава броя на наличните процесори и прави неизбежен етапа на консолидация на основните задачи. Във връзка с това може да е полезно да се обобщят изчисленията още на етапа на идентифициране на основните подзадачи. Възможно решение може да се състои в комбиниране в рамките на една подзадача на всички изчисления, свързани не с един, а с няколко елемента от получената матрица С. За по-нататъшно разглеждане определяме основния проблем като процедура за изчисляване на всички елементи на един от редовете на матрица C. Този подход води до намаляване на общия брой подпроблеми до стойността n .

За да се извършат всички необходими изчисления, един от редовете на матрица A и всички колони на матрица B трябва да са на разположение на основната подзадача. Едно просто решение на този проблем - дублиране на матрица B във всички подзадачи - обикновено е неприемливо поради голямото количество памет, необходимо за съхранение на данни. Следователно организацията на изчисленията трябва да бъде изградена по такъв начин, че във всеки текущ момент от време подзадачите да съдържат само част от данните, необходими за изчисленията, а достъпът до останалите данни ще бъде осигурен чрез трансфер на данни между процесорите. Два възможни начина за извършване на паралелни изчисления от този тип са разгледани допълнително в раздел 7.3.2.

7.3.2. Изолиране на информационни зависимости

За да се изчисли един ред матрица C, е необходимо всяка подзадача да съдържа ред матрица A и да осигурява достъп до всички колони на матрица B. Възможните начини за организиране на паралелни изчисления са както следва.

1. Първи алгоритъм. Алгоритъмът е итеративна процедура, чийто брой повторения съвпада с броя на подзадачите. При всяка итерация на алгоритъма, всяка подпроблема съдържа един ред матрица А и една колона матрица В. При извършване на итерацията се извършва скалярно умножение на редовете и колоните, съдържащи се в подзадачите, което води до получаване на съответните елементи на получената матрица С. След приключване на изчисленията в края на всяка итерация колоните на матрицата B трябва да се прехвърлят между подзадачите, така че във всяка подзадача да има нови колони на матрицата B и да могат да се изчислят нови елементи на матрицата C. Освен това този трансфер на колони между подзадачи трябва да бъде организиран по такъв начин, че след завършване на итерациите на алгоритъма, във всяка подзадача последователно всички колони от матрицата B .

Възможна проста схема за организиране на необходимата последователност на трансфери на колони от матрица В между подзадачи е да се представи топологията на информационните връзки на подзадачи под формата на пръстенна структура. В този случай, при всяка итерация, подпроблема i, 0>