Рекурсивная блочная схема умножения матриц.
Когда порядки квадратных матриц сомножителей равны 2n, то матрицы разбиваются на четыре одинаковых квадратных блока и вычисление произведения матриц сводится к вычислению 8 умножений таких блоков, с последующим парным суммированием. Для вычисления произведения блоков снова используется эта же схема. Так можно продолжать вплоть до элементов.
Был реализован динамический вариант такой программы. Одно умножение матриц, которые разбиты на четыре блока, сводится к восьми блочным умножениям и может выполняться параллельно на 8 процессорах. Если при этом еще не все процессоры участвуют в вычислениях, то каждое такое блочное умножение может, в свою очередь, быть реализовано с помощью 8 умножений подблоков. Для управления свободными процессорами и организации блочных операции умножения на конкретных процессорах используется программа диспетчера.
Эксперименты для матриц 512 порядка с небольшими целыми коэффициентами (~228) показали, что при умножении в кольце целых чисел коэффициент ускорения равен 85%, а при умножении в конечном поле коэффициент ускорения равный 86.4%. Использовались 2 и 14 процессоров.
На рис. 5 и 6 показаны результаты двух экспериментов, проведенных для динамических параллельных программ умножения матриц. В этих программах использовался QT-формат хранения коэффициентов. В каждом эксперименте выполнялось умножение матриц 512 порядка. В первом случае коэффициенты матриц – это целые числа в пределах 228. Коэффициент ускорения при переходе с двух на 14 процессоров был равен 85%. Во втором случае коэффициенты матриц берутся из конечного поля, характеристика которого не превосходит 2·108. Коэффициент ускорения при переходе с двух на 14 процессоров составляет 85%.
Рис. 5. Вычисление произведения целочисленных матриц в QT формате с помощью рекурсивной схемы умножения.
Коэффициент ускорения равен 85%.
Рис. 6. Вычисление произведения матриц в конечном поле в QT формате с помощью рекурсивной схемы умножения.
Коэффициент ускорения равен 86%.
