- •Умножение двух матриц методом статического разделения на полосы
- •Постановка задачи
- •Последовательный алгоритм решения Умножение матриц по определению
- •Алгоритм Штрассена
- •Параллельный алгоритм решения
- •Результаты вычислительного эксперимента Матрицы 1 000 × 1 000
- •Матрицы 10 000 × 10 000
- •Матрицы 20 000 × 20 000
- •Приложение. Код программы.
Национальный Исследовательский Университет
МОСКОВСКИЙ ЭНЕРГЕТИЧЕСКИЙ ИНСТИТУТ
Институт автоматики и вычислительной техники
Кафедра прикладной математики
Лабораторная работа № 3
Умножение двух матриц методом статического разделения на полосы
Курс «Параллельные системы и параллельные вычисления»
Выполнил
студент 5 курса группы А-13-08
Захаров Антон
Преподаватель
Панков Николай Александрович
Постановка задачи
Пусть даны две прямоугольные матрицы и размерности и соответственно:
Требуется найти матрицу (произведением) размерности :
Для нахождения произведения матриц методом статического разделения на полосы необходимо составить последовательно-параллельную программу на языке C или C++, использующую принципы нитевого распараллеливания, а также исследовать характеристики разработанной программы в зависимости от числа потоков.
Тестирование проводились на компьютере со следующей конфигурацией:
ПРОЦЕССОР Intel Core i5 2500MHz Ivy Bridge
ОПЕРАТИВНАЯ ПАМЯТЬ 16Gb DDR3 1600MHz
ФИЗИЧЕСКИЙ НАКОПИТЕЛЬ OCZ-VERTEX3 (120Gb, SATA600, SSD)
ГРАФИЧЕСКИЙ ПРОЦЕССОР AMD Radeon HD 7700 (1Gb DDR5 4.6GHz)
ОПЕРАЦИОННАЯ СИСТЕМА Windows 7 Ultimate x64 (SP1)
Последовательный алгоритм решения Умножение матриц по определению
В соответствии с определением, произведение матриц состоит из всех возможных комбинаций скалярных произведений строк матрицы и столбцов матрицы . Элемент матрицы с индексами (i, j) есть скалярное произведение i-ой строки матрицы и j-го столбца матрицы .
-
for (i = 0; i < m; i++) {
-
for (j = 0; j < q; j++) {
-
C[i][j] = 0;
-
for (k = 0; k < n; k++)
-
C[i][j] += A[i][k] * B[k][j];
-
}
-
}
На первый взгляд это минимальный объем работы, необходимый для перемножения двух матриц. Однако исследователям не удалось доказать минимальность, и в результате они обнаружили другие алгоритмы, умножающие матрицы более эффективно.
Алгоритм Штрассена
Первый алгоритм быстрого умножения матриц был разработан В. Штрассеном в 1969. В основе алгоритма лежит рекурсивное разбиение матриц на блоки. Недостатком данного метода является большая сложность программирования по сравнению со стандартным алгоритмом, численная неустойчивость и большой объём используемой памяти.
Разработано большое количество алгоритмов на основе метода Штрассена, которые улучшают его численную устойчивость и уменьшают объём используемой памяти.
Алгоритм Копперсмита-Винограда
В 1990 Копперсмит и Виноград опубликовали алгоритм, умножающий матрицы со сложностью . Этот алгоритм использует идеи, схожие с алгоритмом Штрассена. На сегодняшний день алгоритм Копперсмита-Винограда является наиболее асимптотически быстрым, но он эффективен только на очень больших матрицах и поэтому не применяется.
В 2003 Кох и др. рассмотрели в своих работах алгоритмы Штрассена и Копперсмита-Винограда в контексте теории групп. Они показали возможность существования алгоритмов умножения матриц со сложностью .
Параллельный алгоритм решения
В предлагаемой реализации метода статического разделения на полосы исходная матрица A разбивается на горизонтальные полосы. Все полосы матрицы распределяются между потоками, а обращение к элементам матрицы , расположенной в общей памяти, осуществляется по мере необходимости. При этом каждый из имеющихся потоков использует только одну полосу матрицы и всю матрицу . Перемножение полосы на матрицу (а данная операция может быть выполнена параллельно) приводит к получению частей (полос) результирующей матрицы , которые затем в совокупности и дадут искомую матрицу.
– полоса матрицы ;
– число потоков.