Параллельное перемножение матриц с использованием рассылок данных broadcast
Поможем в ✍️ написании учебной работы
Поможем с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой

 

Операция broadcast используется в цикле, длина которого равна количеству модулей памяти (или процессорных элементов). Записывается следующим образом:

 

T[1..n] – горизонтально размещенный массив.

 

do i = 1, n

broadcast Ti = B

 

Семантика операции состоит в том, что переменная B рассылается по всем модулям памяти и в каждом модуле памяти с номером i присваивается переменной Ti .

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

 

Пример 19. Размещение: A по строкам, B по строкам, X по строкам.

 

  T[1..n] – горизонтально размещенный массив.

  do 99 j = 1, n

  do 99 k = 1, n

  do 88 i = 1, n

88 broadcast Ti = B(k,j)

  do par 99 i = 1, n

99 X(i,j) = X(i,j)+A(i,k)* Ti.

 

Пример 20. Размещение: A по строкам, B по столбцам, X по строкам.

 

  T[1..n] – горизонтально размещенный массив.

  do 99 j = 1, n

  do 99 k = 1, n

  do 88 i = 1, n

88 broadcast Ti = B(k,j)

  do par 99 i = 1, n

99 X(i,j) = X(i,j)+A(i,k)* Ti.

 

Пример 21. Размещение: A по столбцам, B по столбцам, X по столбцам.

 

  T[1..n] – горизонтально размещенный массив.

  do 99 i = 1, n

  do 99 k = 1, n

  do 88 j = 1, n

88 broadcast Tj = A(i,k)

    do par 99 j = 1, n

99 X(i,j) = X(i,j)+ Tj*B(k,j).

 

Пример 22. Размещение: A по столбцам, B по строкам, X по строкам.

В этом случае, формально записанная по аналогии с другими случаями, программа будет некорректна, поскольку все данные для цикла do par окажутся в одном модуле памяти и этот цикл не сможет выполниться параллельно.

 

  T[1..n] – горизонтально размещенный массив.

  do 99 j = 1, n

  do 99 k = 1, n

  do 88 i = 1, n

88 broadcast Ti = B(k,j)

  do par 99 i = 1, n

99 X(i,j) = X(i,j)+A(i,k)* Ti.

 

При таком размещении массивов все элементы матрицы A, которые должны быть умножены на фиксированный элемент матрицы B, находятся в одном модуле памяти. Поэтому рассылка элементов матрицы B  не дает эффекта. Аналогично, в одном модуле памяти находятся все элементы матрицы B, которые должны быть умножены на фиксированный элемент матрицы A.  

В этом случае можно один из двумерных массивов предварительно переразместить (транспонировать), после чего уже выполнять вычисления. При этом количество пересылок станет вдвое больше, чем в других случаях. Например, если транспонировать матрицу B, то потом следует применить случай «Размещение: A по столбцам, B по столбцам».

 

  TT[1..n] [1..n] – по столбцам размещенный двумерный массив.

  do 77 j = 1, n

  do 77 k = 1, n

77 TT(j,k) = B(k,j)

 

  T[1..n] – горизонтально размещенный массив.

  do 99 i = 1, n

  do 99 k = 1, n

  do 88 j = 1, n

88 broadcast Tj = A(i,k)

  do par 99 j = 1, n

99 X(i,j) = X(i,j)+ Tj* TT(k,j).

 

Приведем примеры алгоритмов перемножения матриц, использующих скошенную форму хранения. 

 

Пример 23. Размещение: A по строкам, B скошенная, X по строкам.

 

  T[1..n] – горизонтально размещенный массив.

  do 99 j = 1, n

  do 99 k = 1, n

  do 88 i = 1, n

88 broadcast Ti = B(k,j)

  do par 99 i = 1, n

99 X(i,j) = X(i,j)+A(i,k)* Ti.

 

 

Пример 24. Размещение: A по столбцам, B скошенная, X по строкам.

 

  T[1..n] – горизонтально размещенный массив.

  do 99 j = 1, n

  do 99 k = 1, n

  do 88 i = 1, n

88 broadcast Ti = B(k,j)

  do par 99 i = 1, n

  do 88 i = 1, n

88 T(i) ß T((i+m) mod n)    % Циклический сдвиг на m ПЭ.

 

В результате этой операции для каждого значения индекса i = 1, 2, …, n новое значение T(i) равно старому значению элемента массива T((i+m) mod n).

       При использовании кольцевых сдвигов ситуация с оптимальными алгоритмами аналогична со случаем использования рассылки данных. Различные параллельные алгоритмы перемножения матриц с пересылками на различных коммуникационных сетях, в том числе и по кольцу приводятся в [81], [127], [37], [36].

 

 

4.6 О сложности по обращениям к памяти на примере алгоритма Штрассена перемножения матриц.

 

Рассмотрим вопрос об эффективности задачи перемножения квадратных матриц размера n*n. Здесь, конечно, следует отметить замечательный алгоритм Штрассена для быстрого перемножения матриц [137], [10], [81, стр. 220]. Сложность стандартного алгоритма (в котором, согласно определению, строки одной матрицы скалярно умножаются на столбцы другой) равна n3. В данном случае n3 – это количество умножений. У алгоритма Штрассена сложность равна n2.81 (более точно, показатель степени равен log27). Этот неожиданный алгоритм дал импульс развитию теории сложности. Напомним, что сложность алгоритма – это количество операций как функция от количества входных данных, а сложность задачи – это сложность самого быстрого алгоритма. При этом под операциями подразумевались арифметические операции, как правило – умножения, как операции, требующие существенно большего времени, чем сложение. Позднее были найдены алгоритмы перемножения матриц асимптотически еще менее сложные, чем алгоритм Штрассена. Сложность задачи перемножения матриц пока не определена. Есть результаты, позволяющие сомневаться в том, что самый эффективный алгоритм перемножения матриц существует: в [83] указывается существование такой задачи, у которой для любого алгоритма решения существует более быстрый алгоритм.

       Но давайте рассмотрим реальные преимущества алгоритма Штрассена по сравнению со стандартным. В 1988 г. на кафедре алгебры и дискретной математики мехмата Ростовского госуниверситета (сейчас Южный федеральный университет) был запрограммирован алгоритм Штрассена (студенческая работа, руководитель доц. Козак А.В.). Выяснилось, что алгоритм Штрассена начинает давать преимущества по сравнению со стандартным алгоритмом, начиная с размерности матриц n=32. В 2002 г. опять был реализован алгоритм Штрассена (тоже студенческая работа, руководитель автор). В этот раз преимущество алгоритма Штрассена начиналось с размерности матриц n=512. Попытаемся объяснить этот эффект. За примерно 15 лет компьютеры стали совсем другими. Изменилось соотношение времени выполнения арифметических операций и времени обращения к памяти. А соотношение количества этих операций в алгоритме Штрассена и в стандартном алгоритме различно.

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

       Предполагается, что размерность матрицы является степенью двойки: n = 2k .

Исходные и результирующая матрицы представляются как блочные 2*2 матрицы с блоками размерности n/2. Тогда произведение матриц имеет вид

 

C = A * B  

C = {Cij }, A = {Aij }, B = {Bij }, i, j = 1, 2. 

 

Здесь Cij , Aij , Bij , i, j = 1, 2. – блоки матриц C, A и B соответственно.

По алгоритму Штрассена вычисляются 7 вспомогательных матриц (размера n/2):

 

M1 = (A12 – A22)*(B21 + B22)               

M2 = (A11 + A22)*(B11 + B22)               

M3 = (A11 – A21)*(B11 + B12)               

M4 = (A11 + A12)*B22               

M5 = A11 *( B12 – B22)           

M6 = A22 *( B21 – B11)     

M7 = (A21 + A22)*B11

 

После этого элементы результирующей матрицы вычисляются по формулам:

 

C11 = M1 + M2 – M4 + M6               

C12 = M4 + M5               

C21 = M6 + M7               

C22 = M2 – M3 + M5 – M7           

 

Первые 7 формул содержат умножение матриц меньшей размерности, которое тоже может выполняться рекурсивно по такому же алгоритму.

Обозначим через F(n) количество операций обращения к памяти (чтение или запись) в алгоритме Штрассена. 

Во всех 11 формулах матрицы размера n/2 встречаются 37 раз. При этом первые 7 формул содержат умножения матриц размера n/2, каждое из которых потребует количество обращений к памяти F(n/2). Итого, можно записать рекуррентную формулу

 

    F(n) = 7*F(n/2) + 37 * (n/2)2

 

Учитывая, что F(1) = 3, из рекуррентной формулы можно получить аналитическую

 

    F(n) = 7*F(n/2) + 37 * (n/2)2 = 7*{ 7*F(n/4) + 37 * (n/4)2 } + 37 * (n/2)2 =

 7k * F(1) + 37 * { 7k-1 *(n/2k )2 + … + 7*(n/4)2 + (n/2)2 } =

7k * 3 + 37/7 * n2 * { (7/4)k  + … + (7/4)2 + 7/4 } = 7k * 3 + 37/7 * n2 * 7/3 * ( (7/4)k – 1 ) = 7k * 3 + 37/3 * n2 * ( (7/4)k – 1 )

 

Пренебрегая в скобках слагаемым (-1) и вспоминая, что k = log2n, получим, что количество обращений к памяти в алгоритме Штрассена равно

 

    F(n) ≈ 7k * 3 + 37/3 * n2 * (7/4)k  = 7k * 3 + 37/3 * 7k  = 7k  * 46/3 ≈ n2.81 * 46/3 

 

Рассмотрим количество обращений к памяти в стандартном алгоритме. Каждый элемент результирующей матрицы вычисляется как скалярное произведение двух векторов (строки первой матрицы на столбец второй). Такое скалярное произведение вычисляется накоплением суммы произведений в регистре и требует n2 чтений и одну запись в память. Итого 2 * n3 + n2 ≈ 2 * n3 обращений к памяти.

       Асимптотически количество обращений к памяти алгоритма Штрассена меньше, чем у стандартного алгоритма. Рассмотрим, начиная с какой размерности матриц n в алгоритме Штрассена количество обращений к памяти будет меньше, чем в стандартном алгоритме.

 

2 * n3 = n2.81 * 46/3                     

n ≈ 25000                     

 

Численный эксперимент для матриц такой размерности не представляется разумным, поскольку матрицы такой размерности будут размещаться не в оперативной, а во внешней памяти.

Следует отметить, что рекурсивность алгоритма Штрассена тоже может вызвать дополнительные обращения к памяти (обращения к стеку, в котором хранятся параметры вызовов). Глубина рекурсивных вызовов равна k = log2n . Если столько параметров вызовов не поместится в регистровой или кэш памяти, то они будут помещаться в памяти оперативной. 

 


 


Дата: 2018-12-21, просмотров: 398.