НОУ ИНТУИТ | Лекция | Параллельные методы матричного умножения
< Лекция 6 || Лекция 7: 123456 || Лекция 8 >
Аннотация: В лекции рассматривается одна из основных задач матричных вычислений — умножение матриц. Приводится постановка задачи и дается последовательный алгоритм ее решения. Далее описываются возможные подходы к параллельной реализации алгоритма и подробно рассматриваются наиболее широко известные алгоритмы: алгоритм, основанный на ленточной схеме разделения данных, алгоритм Фокса (Fox) и алгоритм Кэннона (Cannon)
Ключевые слова: умножение матриц, Произведение, алгоритм, вычисление, цикла, время выполнения, операции, скалярное умножение, операции передачи данных, EM64T, computer cluster, вычислительный эксперимент, представление, балансировка вычислений, программная реализация, MPI, производный тип данных, операция циклического сдвига, матрица, разбиение, алгоритмы Фокса и Кэннона, матричные вычисления
7.1. Постановка задачи
| ( 7.1) |
Как следует из (7.1), каждый элемент результирующей матрицы С есть скалярное произведение соответствующих строки матрицы A и столбца матрицы B:
| ( 7.2) |
Этот алгоритм предполагает выполнение mxnxl операций умножения и столько же
операций сложения элементов исходных матриц.
7.2. Последовательный алгоритм
Последовательный алгоритм умножения матриц представляется тремя вложенными циклами:
Алгоритм 7.1. Последовательный алгоритм умножения двух квадратных матриц
// Алгоритм 7.1 // Последовательный алгоритм умножения матриц double MatrixA[Size][Size]; double MatrixB[Size][Size]; double MatrixC[Size][Size]; int i,j,k; ... for (i=0; i<Size; i++){ for (j=0; j<Size; j++){ MatrixC[i][j] = 0; for (k=0; k<Size; k++){ MatrixC[i][j] = MatrixC[i][j] + MatrixA[i][k]*MatrixB[k][j]; } } }
..
for (i=0; i<Size; i++){
for (j=0; j<Size; j++){
MatrixC[i][j] = 0;
for (k=0; k<Size; k++){
MatrixC[i][j] = MatrixC[i][j] + MatrixA[i][k]*MatrixB[k][j];
}
}
}Этот алгоритм является итеративным и ориентирован на последовательное вычисление строк матрицы С. Действительно, при выполнении одной итерации внешнего цикла (цикла по переменной i ) вычисляется одна строка результирующей матрицы (см. рис. 7.1).
Рис. 7.1. На первой итерации цикла по переменной i используется первая строка матрицы A и все столбцы матрицы B для того, чтобы вычислить элементы первой строки результирующей матрицы С
Поскольку каждый элемент результирующей матрицы есть скалярное произведение строки и столбца исходных матриц, то для вычисления всех элементов матрицы С размером nxn необходимо выполнить n2x(2n–1) скалярных операций и затратить время
(
7. 3) |
где есть время выполнения одной элементарной скалярной операции.
7.3. Умножение матриц при ленточной схеме разделения данных
Рассмотрим два параллельных алгоритма умножения матриц, в которых матрицы A и B разбиваются на непрерывные последовательности строк или столбцов (полосы).
7.3.1. Определение подзадач
Из определения операции матричного умножения следует, что
вычисление всех элементов матрицы С может быть
выполнено независимо друг от друга. Как результат, возможный
подход для организации параллельных вычислений состоит в
использовании в качестве базовой подзадачи процедуры определения
одного элемента результирующей матрицы С. Для
проведения всех необходимых вычислений каждая подзадача должна
содержать по одной строке матрицы А и одному столбцу
матрицы В. Общее количество получаемых при таком
подходе подзадач оказывается равным n2 (по числу элементов матрицы С ).
Рассмотрев предложенный подход, можно отметить, что достигнутый уровень параллелизма является в большинстве случаев избыточным. Обычно при проведении практических расчетов такое количество сформированных подзадач превышает число имеющихся процессоров и делает неизбежным этап укрупнения базовых задач. В этом плане может оказаться полезной агрегация вычислений уже на шаге выделения базовых подзадач. Возможное решение может состоять в объединении в рамках одной подзадачи всех вычислений, связанных не с одним, а с несколькими элементами результирующей матрицы С. Для дальнейшего рассмотрения определим базовую задачу как процедуру вычисления всех элементов одной из строк матрицы С. Такой подход приводит к снижению общего количества подзадач до величины n.
Для выполнения всех необходимых вычислений базовой подзадаче
должны быть доступны одна из строк матрицы A и все
столбцы матрицы B. Простое решение этой проблемы –
дублирование матрицы B во всех подзадачах –
является, как правило, неприемлемым в силу больших затрат памяти
для хранения данных.
7.3.2. Выделение информационных зависимостей
Для вычисления одной строки матрицы С необходимо, чтобы в каждой подзадаче содержалась строка матрицы А и был обеспечен доступ ко всем столбцам матрицы B. Возможные способы организации параллельных вычислений состоят в следующем.
1. Первый алгоритм. Алгоритм представляет собой
итерационную процедуру, количество итераций которой совпадает с
числом подзадач. На каждой итерации алгоритма каждая подзадача
содержит по одной строке матрицы А и одному столбцу матрицы В.
Возможная простая схема организации необходимой
последовательности передач столбцов матрицы В между подзадачами
состоит в представлении топологии информационных связей подзадач
в виде кольцевой структуры. В этом случае на каждой итерации
подзадача i, 0<=i<n, будет передавать свой столбец матрицы В
подзадаче с номером i+1 (в соответствии с кольцевой структурой
подзадача n-1 передает свои данные подзадаче с номером 0 ) – см.
На рис. 7.2 представлены итерации алгоритма матричного умножения для случая, когда матрицы состоят из четырех строк и четырех столбцов ( n=4 ). В начале вычислений в каждой подзадаче i, 0<=i<n, располагаются i -я строка матрицы A и i -й столбец матрицы B. В результате их перемножения подзадача получает элемент cii результирующей матрицы С. Далее подзадачи осуществляют обмен столбцами, в ходе которого каждая подзадача передает свой столбец матрицы B следующей подзадаче в соответствии с кольцевой структурой информационных взаимодействий. Далее выполнение описанных действий повторяется до завершения всех итераций параллельного алгоритма.
Рис. 7.2. Общая схема передачи данных для первого параллельного алгоритма матричного умножения при ленточной схеме разделения данных
При рассмотренном способе разделения данных для выполнения операции матричного умножения нужно обеспечить последовательное получение в подзадачах всех строк матрицы B, поэлементное умножение данных и суммирование вновь получаемых значений с ранее вычисленными результатами. Организация необходимой последовательности передач строк матрицы B между подзадачами также может быть выполнена с использованием кольцевой структуры информационных связей (см. рис. 7.3).
На рис. 7.3 представлены
итерации алгоритма матричного умножения для случая, когда матрицы
состоят из четырех строк и четырех столбцов ( n=4 ).
В начале
вычислений в каждой подзадаче i, 0<=i<n, располагаются i -е строки
матрицы A и матрицы B. В результате их перемножения подзадача
определяет i -ю строку частичных результатов искомой матрицы C.
Далее подзадачи осуществляют обмен строками, в ходе которого
каждая подзадача передает свою строку матрицы B следующей
подзадаче в соответствии с кольцевой структурой информационных
взаимодействий. Далее выполнение описанных действий повторяется
до завершения всех итераций параллельного алгоритма.
Рис. 7.3. Общая схема передачи данных для второго параллельного алгорится матричного умножения при ленточной схеме разделения данных
Дальше >>
< Лекция 6 || Лекция 7: 123456 || Лекция 8 >
Реализация консольного приложения для умножения двух матриц на языке C#
УДК 004. 4
Кувайцев Александр Вячеславович
Димитровградский инженерно-технологический институт филиал национального исследовательского ядерного университета «МИФИ»
Аннотация
В данной статье представлен пример реализации простой программы для умножения двух матриц. Умножать можно такие прямоугольные матрицы, в которых число столбцов первой матрицы равно числу строк во второй.
Ключевые слова: матрицы, приложение, программирование, умножение матриц
Kuvaytsev Aleksandr Vyacheslavovich
Dimitrovgrad Engineering and Technological Institute of the National Research Nuclear University MEPHI
Abstract
This article presents an example implementation of a simple program for multiplying two matrices. To multiply such a matrix, in which the number of columns of the first matrix equals the number of rows in the second.
Keywords: application, C#, program, Visual Studio
Рубрика: 05. 00.00 ТЕХНИЧЕСКИЕ НАУКИ
Библиографическая ссылка на статью:
Кувайцев А.В. Реализация консольного приложения для умножения двух матриц на языке C# // Современные научные исследования и инновации. 2016. № 12 [Электронный ресурс]. URL: https://web.snauka.ru/issues/2016/12/75907 (дата обращения: 16.12.2022).
В данной статье описывается процесс разработки простейшей программы умножения двух матриц. Разработка любого приложения начинается с составления алгоритма [1,2], в данном случае это алгоритм умножения, представленный на рисунке 1.
Рисунок 1. – Алгоритм умножения матриц
Условно программу можно разделить на 3 модуля: модуль ввода, модуль вычисления и модуль вывода. В целом они будут образовывать небольшое консольное приложение для умножения одной матрицы на другую. Для написания этой программы подойдет практически любой язык, но был выбран C#, т.к. в первую очередь он является одним из актуальных для написания клиентских приложений под платформу Windows. Помимо этого, он обладает такими плюсами как простой синтаксис и скорость работы.
На рисунке 2 представлен код модуля ввода матриц.
Рисунок 2. – Код модуля ввода матриц
Этот фрагмент кода отвечает за ввод матриц в программу. Сначала происходит ввод размерности матрицы, а затем поочередный ввод элементов матрицы, данные заносятся в массив. Так же происходит и со второй матрицей. На этом этапе не учитывается тот факт, что количество строк в первой матрице должно быть равно количеству столбцов второй. После ввода матриц вызывается процедура вывода первой и второй матрицы на экран, затем вызов процедуры умножения и вывод полученной матрицы.
На рисунке 3, представлен код модуля вычисления.
Рисунок 3. – Код модуля вычисления
Процедура умножения начинается с проверки равно ли количество строк первой матрицы количеству столбцов второй. Если данные удовлетворяют условию код выполняется дальше, а если нет, то выводится ошибка. Для новой матрицы создается новый массив, в который заносятся результаты вычислений.
На рисунке 4 представлен код модуля вывода матриц. При вызове процедуры указывается индекс массива, который необходимо вывести, это позволяет сократить код, посредством вызова этой функции с необходимым параметром, а не указывая в коде на какой-то определенный массив.
Рисунок 4. – Модуль вывода матриц
На рисунке 5 показана выполненная программа. Выводятся обе матрицы, а также новая матрица, полученная в результате умножения.
Рисунок 5. – Результат выполнения программы
Библиографический список
- Умножение матриц [Электронный ресурс]. Режим доступа: https://ru.wikipedia.org/wiki/Умножение_матриц (дата обращения: 17.12.2016).
- Алгоритм умножения матриц [Электронный ресурс]. Режим доступа: http://vscode.ru/prog-lessons/algoritm-umnozheniya-matrits.html (дата обращения: 17. 12.2016).
Количество просмотров публикации: Please wait
Все статьи автора «Кувайцев Александр Вячеславович»
© Если вы обнаружили нарушение авторских или смежных прав, пожалуйста, незамедлительно сообщите нам об этом по электронной почте или через форму обратной связи.
Примеры умножения матриц и векторов
Пример 1
Вычисление $A \vc{x}$, где $\vc{x} = (-2, 1, 0)$ и \начать{выравнивать*} А= \левый[ \начать{массив}{ррр} 1 &2 &3\\ 4 &5 &6\\ 7 &8 &9\\ 10 и 11 и 12 \конец{массив} \правильно]. \конец{выравнивание*}
Решение :
\начать{выравнивать*}
А\ВК{х}
&=\влево[
\начать{массив}{ррр}
1 &2 &3\\
4 &5 &6\\
7 &8 &9\\
10 и 11 и 12
\конец{массив}
\правильно]
\левый[
\начать{массив}{г}
-2\\
1\\
0
\конец{массив}
\правильно]
\\
знак равно
\левый[
\начать{массив}{с}
-2\cdot 1 + 1 \cdot 2 + 0 \cdot 3\\
-2\cdot 4 + 1 \cdot 5 + 0 \cdot 6\\
-2\cdot 7 + 1 \cdot 8 + 0 \cdot 9\\
-2\cdot 10 + 1 \cdot 11 + 0 \cdot 12
\конец{массив}
\правильно]
\\
знак равно
\левый[
\начать{массив}{с}
0\\
-3\\
-6\\
-9
\конец{массив}
\правильно]
= (0, -3, -6, -9). \конец{выравнивание*}
Пример 2
Вычислить $A \vc{y}$, где $\vc{y} = (-3, -2, -1, 0)$ и $A$ как в примере 1.
Решение : произведение матрицы на вектор не определено. $A$ равно $4 \times 3$, а $\vc{y}$ равно $4 \times 1$ (рассматривается как вектор-столбец).
Пример 3
Вычислить $BC$, где \начать{выравнивать*} Б= \левый[ \начать{массив}{ррр} 1 &2 &3\\ 4 и 5 и 6 \конец{массив} \правильно] \qquad \текст{и} \qquad С= \левый[ \begin{массив}{rr} 1 &2\\ 3 и 4\\ 5 и 6 \конец{массив} \правильно]. \конец{выравнивание*}
Решение : \начать{выравнивать*} БК &= \левый[ \начать{массив}{ррр} 1 &2 &3\\ 4 и 5 и 6 \конец{массив} \правильно] \левый[ \begin{массив}{rr} 1 &2\\ 3 и 4\\ 5 и 6 \конец{массив} \правильно] \\ знак равно \левый[ \begin{массив}{ccc} 1\cточка 1 + 2\cточка 3 + 3\cточка 5 && 1\cdot 2 + 2\cdot 4 + 3\cdot 6 \\ 4\cточка 1 +5\cточка 3 +6\cточка 5 && 4\cdot 2 +5\cdot 4 +6\cdot 6 \конец{массив} \правильно] \\ знак равно \левый[ \begin{массив}{cc} 22 и 28\\ 49& 64 \конец{массив} \правильно] \конец{выравнивание*}
Пример 4
Используя $B$ и $C$, как определено в Примере 3, вычислите $CB$.
Решение :
\начать{выравнивать*}
ЦБ &=
\левый[
\begin{массив}{rr}
1 &2\\
3 и 4\\
5 и 6
\конец{массив}
\правильно]
\левый[
\начать{массив}{ррр}
1 &2 &3\\
4 и 5 и 6
\конец{массив}
\правильно]
\\
знак равно
\левый[
\begin{массив}{ccccc}
1\cточка 1 + 2\cточка 4
&&1\cdot 2 + 2\cdot 5
&&1\cdot 3 + 2\cdot 6\\
3\cточка 1 + 4\cточка 4
&&3\cdot 2 + 4\cdot 5
&&3\cdot 3 + 4\cdot 6\\
5\cточка 1 + 6\cточка 4
&&5\cdot 2 + 6\cdot 5
&&5\cdot 3 + 6\cdot 6
\конец{массив}
\правильно]
\\
знак равно
\левый[
\начать{массив}{ррр}
9& 12 & 15\\
19 и 26 и 33\\
29 и 40 и 51
\конец{массив}
\правильно]
\конец{выравнивание*}
Ясно, что умножение матриц не является коммутативным,
т. е. $BC \ne CB$. В случае примеров 3 и 4 $BC$ даже не
матрица того же размера, что и $CB$. В некоторых других случаях $BC$ может быть
определено, но $CB$ не будет определено (например, когда $B$ равно $3 \times
2$-матрица, а $C$ — матрица $2×4$). Верно даже то, что когда $B$
и $C$ — квадратные матрицы, умножение матриц не
коммутативный. Вы можете попробовать сами и увидеть, что $BC \ne CB$ если
\начать{выравнивать*}
Б=
\левый[
\begin{массив}{rr}
1 &2\\
3 и 4
\конец{массив}
\правильно]
\qquad
\текст{и}
\qquad
С=
\левый[
\begin{массив}{rr}
5 и 6\\
7 и 8
\конец{массив}
\правильно].
\конец{выравнивание*}
numpy.matmul — Руководство NumPy v1.24
- numpy.matmul ( x1 , x2 , /, Out = none , * , Casting = ‘some_kind’ , Порядок = ‘K’ , Dtype = NOME , = ‘K’ , DTYPE = NAYPE = , . = True [ подпись , extobj , оси , ось ]) =
Матричное произведение двух массивов.
- Параметры:
- x1, x2 array_like
Входные массивы, скаляры не допускаются.
- out ndarray, необязательный
Местоположение, в котором сохраняется результат. Если он предусмотрен, он должен иметь форма, соответствующая подписи (n,k),(k,m)->(n,m) . Если не если указано или None, возвращается только что выделенный массив.
- **kwargs
Другие аргументы, содержащие только ключевые слова, см. документы ufunc.
Новое в версии 1.16: Теперь обрабатывает ufunc kwargs
- Возвращает:
- y ndarray
Матричный продукт входных данных. Это скаляр только тогда, когда оба x1, x2 являются одномерными векторами.
- Поднимает:
- ValueError
Если последний размер x1 не совпадает с размером предпоследнее измерение x2 .
Если передается скалярное значение.
См. также
-
vdot Комплексно-сопряженное скалярное произведение.
-
тензордот Суммирование произведений по произвольным осям.
-
einsum Соглашение Эйнштейна о суммировании.
-
точка альтернативный матричный продукт с другими правилами вещания.
Примечания
Поведение зависит от аргументов следующим образом.
Если оба аргумента являются двумерными, они умножаются, как обычно матрицы.
Если любой из аргументов N-D, N > 2, он обрабатывается как стек матрицы, находящиеся в последних двух индексах, и транслируются соответственно.
Если первый аргумент одномерный, он преобразуется в матрицу с помощью добавляя 1 к своим размерам. После умножения матриц предшествующая 1 удаляется.
Если второй аргумент 1-D, он преобразуется в матрицу с помощью добавление 1 к его размерам. После умножения матриц добавленная 1 удаляется.
матмулотличается отточкапо двум важным параметрам:Умножение на скаляры не допускается, вместо этого используйте
*.Стеки матриц передаются вместе, как если бы матрицы были элементы, соблюдающие подпись
(н, к), (к, м) -> (н, м):>>> a = np.ones([9, 5, 7, 4]) >>> c = np.ones([9, 5, 4, 3]) >>> np.dot(a, c).shape (9, 5, 7, 9, 5, 3) >>> np.matmul(a, c).shape (9, 5, 7, 3) >>> # n равно 7, k равно 4, m равно 3
Функция matmul реализует семантику оператора
@введен в Python 3.5 после PEP 465 .По возможности использует оптимизированную библиотеку BLAS (см.
numpy.linalg).Примеры
Для двумерных массивов это матричное произведение:
>>> a = np.array([[1, 0], ... [0, 1]]) >>> b = np.array([[4, 1], ... [2, 2]]) >>> np.matmul(а, б) массив([[4, 1], [2, 2]])Для 2-D, смешанного с 1-D, результат обычный.