Теория и практика параллельных вычислений
Последовательный алгоритм
Последовательный алгоритм умножения матриц представляется тремя вложенными циклами:
Алгоритм 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]; } } }
Этот алгоритм является итеративным и ориентирован на последовательное вычисление строк матрицы С. Действительно, при выполнении одной итерации внешнего цикла (цикла по переменной i) вычисляется одна строка результирующей матрицы (см. рис. 7.1).
Рис. 7.1. На первой итерации цикла по переменной i используется первая строка матрицы A и все столбцы матрицы B для того, чтобы вычислить элементы первой строки результирующей матрицы С
Поскольку каждый элемент результирующей матрицы есть скалярное произведение строки и столбца исходных матриц, то для вычисления всех элементов матрицы С размером n?n необходимо выполнить n2·(2n–1) скалярных операций и затратить время
|
(7.3) |
где ? есть время выполнения одной элементарной скалярной операции.
