Алгоритмы, структуры данных

       

Простая параллельная схема умножения матриц.


Вычисление произведения двух матриц можно осуществить с помощью представления первого матричного сомножителя в виде вектора матричных блоков. В результате умножения каждого такого блока на второй сомножитель, получаем соответствующий блок матрицы, являющейся произведением. Здесь использован естественный параллелизм задачи умножения матриц.

Был реализован статический вариант такой параллельной программы, в которой число блоков, на которые разбивается первый сомножитель, просто выбирается равным числу процессоров участвующих в вычислении, а размеры всех блоков равны между собой или отличаются не более, чем на одну строку. В каждом из процессоров вычисляется умножает одного блоков первой матрицы на вторую матрицу.

Эксперименты с этой программой показали, что при умножении матриц порядка 1024 в конечном поле коэффициент ускорения равен 77% при использовании 12 процессоров. На рис. 4 показана зависимость скорости вычислений этой параллельной программы от количества процессоров, участвующих в вычислении.


Рис. 4. Вычисление произведения матриц в конечном поле с помощью простой параллельной схемы умножения.
Коэффициент ускорения равен 77%.



Содержание раздела