Параллельный алгоритм — умножение матриц

Матрица — это набор числовых и нечисловых данных, расположенных в фиксированном количестве строк и столбцов. Матричное умножение является важным проектом умножения в параллельных вычислениях. Здесь мы обсудим реализацию умножения матриц в различных сетях связи, таких как меш и гиперкуб. Сетка и гиперкуб имеют более высокое сетевое соединение, поэтому они обеспечивают более быстрый алгоритм, чем другие сети, такие как кольцевая сеть.

Сетчатая сеть

Топология, в которой набор узлов образует p-мерную сетку, называется сеточной топологией. Здесь все ребра параллельны оси сетки, и все соседние узлы могут связываться между собой.

Общее количество узлов = (количество узлов в строке) × (количество узлов в столбце)

Ячеистая сеть может быть оценена с использованием следующих факторов:

• Диаметр
• Ширина деления пополам

Диаметр — в ячеистой сети самое большое расстояние между двумя узлами — это его диаметр. P-мерная ячеистая сеть, имеющая kP узлы, имеет диаметр p (k – 1) .

Ширина деления пополам — ширина деления пополам — это минимальное количество ребер, которые необходимо удалить из сети, чтобы разделить сеть ячеек на две половины.

Умножение матриц с использованием ячеистой сети

Мы рассмотрели модель SIMD 2D ячеистой сети, имеющую циклические соединения. Мы разработаем алгоритм для умножения двух n × n массивов с использованием n ² процессоров за определенный промежуток времени.

Матрицы A и B имеют элементы a _ij и b _ij соответственно. Элемент обработки PE _ij представляет собой _ij и b _ij . Расположите матрицы A и B таким образом, чтобы у каждого процессора была пара умножаемых элементов. Элементы матрицы A будут двигаться в левом направлении, а элементы матрицы B — в направлении вверх. Эти изменения в положении элементов в матрицах A и B представляют каждому элементу обработки PE новую пару значений для умножения.

Шаги в алгоритме

• Потрясите две матрицы.
• Рассчитать все произведения, а _ik × b _kj
• Подсчитайте суммы, когда шаг 2 завершен.

Алгоритм

Procedure MatrixMulti

Begin
   for k = 1 to n-1
	
   for all Pij; where i and j ranges from 1 to n
      ifi is greater than k then
         rotate a in left direction
      end if
		
   if j is greater than k then
      rotate b in the upward direction
   end if
	
   for all Pij ; where i and j lies between 1 and n
      compute the product of a and b and store it in c
   for k= 1 to n-1 step 1
   for all Pi;j where i and j ranges from 1 to n
      rotate a in left direction
      rotate b in the upward direction
      c=c+aXb
End

Сеть гиперкубов

Гиперкуб — это n-мерная конструкция, в которой ребра перпендикулярны между собой и имеют одинаковую длину. N-мерный гиперкуб также известен как n-куб или n-мерный куб.

Особенности гиперкуба с узлом 2 ^k

• Диаметр = к
• Ширина деления пополам = 2 ^{к – 1}
• Количество ребер = k

Умножение матриц с использованием сети HyperCube

Общая спецификация сетей Гиперкуб —

• Пусть N = 2 ^m будет общим числом процессоров. Пусть процессоры будут P _0, P ₁ … ..P _N-1 .

• Пусть i и i ^b — два целых числа, 0 <i, i ^b <N-1, и его двоичное представление отличается только положением b, 0 <b <k – 1.

• Рассмотрим две матрицы n × n, матрицу A и матрицу B.

• Шаг 1 — Элементы матрицы A и матрицы B назначены n ³ процессорам, так что процессор в позиции i, j, k будет иметь _ji и b _ik .

• Шаг 2 — Весь процессор в позиции (i, j, k) вычисляет произведение

  C (i, j, k) = A (i, j, k) × B (i, j, k)

• Шаг 3 — Сумма C (0, j, k) = ΣC (i, j, k) для 0 ≤ i ≤ n-1, где 0 ≤ j, k <n – 1.

Пусть N = 2 ^m будет общим числом процессоров. Пусть процессоры будут P _0, P ₁ … ..P _N-1 .

Пусть i и i ^b — два целых числа, 0 <i, i ^b <N-1, и его двоичное представление отличается только положением b, 0 <b <k – 1.

Рассмотрим две матрицы n × n, матрицу A и матрицу B.

Шаг 1 — Элементы матрицы A и матрицы B назначены n ³ процессорам, так что процессор в позиции i, j, k будет иметь _ji и b _ik .

Шаг 2 — Весь процессор в позиции (i, j, k) вычисляет произведение

C (i, j, k) = A (i, j, k) × B (i, j, k)

Шаг 3 — Сумма C (0, j, k) = ΣC (i, j, k) для 0 ≤ i ≤ n-1, где 0 ≤ j, k <n – 1.

Блочная матрица

Блочная матрица или секционированная матрица — это матрица, в которой каждый элемент сам представляет отдельную матрицу. Эти отдельные секции известны как блок или субматрица .

пример

На рисунке (а) X представляет собой блочную матрицу, где A, B, C, D сами являются матрицами. Рисунок (f) показывает общую матрицу.

Блочное матричное умножение

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