Учебное пособие москва мади 2020 ббк 32. 81 В 683 Волосова, А. В. В683

 
6.4. Внутренний параллелизм 
Если для алгоритма, предполагающего реализацию в непараллельной 
вычислительной системе, удастся построить граф, найти для этого графа 
параллельную форму с достаточной шириной ярусов, то данный алгоритм, 
теоретически можно реализовать на параллельном компьютере. При этом 
вычислительные свойства алгоритма сохранятся. Численная устойчивость 
алгоритма сохраняется в любой форме. Такой параллелизм в алгоритмах 
называется внутренним. 
Пример. Вычисление произведения 
А = ВС
двух квадратных матриц 
В,
С
порядка 
n
.
Будем считать элементы матриц 
А, В, С
 
числами и обозначим их 
a
ij
, b
ik
, c
kj
. Согласно определению операции умножения матриц имеем
 
a
ij
 = b
ik
 c
kj
, где i, j = 1, 2,.., n.
На рис. 24 представлен граф для
n = 2
.
Рис. 24. Графы перемножения матриц: а) граф алгоритма для n = 2,
б) граф с рассылками элементов 
b
ik
и 
c
kj
для n = 2
 

---

71 
Граф алгоритма распадается на 
n
2
не связанных между собой 
подграфов. Каждый подграф содержит n вершин и представляет один путь, 
расположенный параллельно оси 
k
граф алгоритма представлен на рис 24 а. В 
полном графе имеется множественная рассылка данных. Элемент 
b
ik 
рассылается по всем вершинам, имеющим те же самые значения координат