ЗНАЙ ИНТУИТ, Лекция, Паралелни методи за умножение на матрици
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 .