Матрицата умножение с колан

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

Алгоритъмът е итеративна процедура, броя на повторенията е равен на броя на подзадачи. На всяка итерация на алгоритъма, всяка подзадача съдържа един ред от матрицата и една колона на матрицата В. Когато итерация се извършва скаларна умножение съдържа в подзадачи на редове и колони, в резултат на съответните елементи на резултат матрица С. След приключване на изчислението в края на всяка итерация, матрични колони в трябва да бъдат прехвърлени между задачи, така че всяка подзадача оказа нови колони на матрицата и нови елементи могат да бъдат изчислени матрица С. Освен това, това прехвърляне колони m напред подзадачи трябва да бъдат разположени така, че след приключване на повторения във всяка подзадача последователно беше всички колони на матрицата Б. Възможни проста схема на предаване изисква последователност на колони в между подзадачи е да се осигури информация за топологията съобщителни подзадачи на пръстенна структура. В този случай, на всяка итерация подзадача аз, 0I

Когато размерът на матрица п е по-голям от броя на процесорите р, основни подзадачи могат да бъдат обобщени, обединени в една подзадача няколко съседни редове и колони от матрици умножени. Размер ленти в същото време трябва да бъдат избрани за к = N / P (приемем, че п е неделими от п).