140
вание алгоритмов выполняющих основные операции линейной алгеб-
ры, обсуждается в большом количестве литературы, посвященной па-
раллельному программированию. Одним из наиболее эффективных, с
теоретической точки зрения, параллельных алгоритмов перемножения
двух квадратных матриц порядка n можно считать следующий, осно-
ванный на идее, изложенной в [2].
1. В узлах трехмерной решетки процессоров (n
× n × n) вычисля-
ются произведения элементов перемножаемых матриц B и C следую-
щим образом: если (i, j, k) координаты процессора в решетке, то в нем
происходит вычисление произведения элементов b
ik
и c
kj
.
2. После этого процессоры решетки, начиная с уровня k = 1, по-
следовательно аккумулируют результаты предыдущего этапа следую-
щим образом: пусть a
k
ij
– результат предыдущего этапа алгоритма в
процессоре с координатами (i, j, k), новый результат вычисляется как
a
k
ij
= a
(k-1)
ij
+ a
k
ij
, далее происходит передача результата на следующий
уровень (k+1).
В результате на уровне k = n будет получена матрица A = BC. Эту
же идею можно использовать для построения эффективного парал-
лельного алгоритма умножения вектора на матрицу. В этом случае
можно разместить в узлах прямоугольной решетки процессоров (n
× n)
произведение элементов a
ij
и x
j
перемножаемых матрицы и вектора, а
вычисление результата проводить аналогичным способом, аккумули-
руя результирующий вектор на уровне j = n.
С практической точки зрения представляется удобным распарал-
леливать алгоритмы преобразования цветов покоординатно, выделяя
для операций над каждой координатой свой процессор. Такой подход
позволяет увеличить скорость выполнения преобразования, не предъ-
являя при этом особых требований к мощности параллельной вычис-
лительной системы (числу процессоров) и не требуя значительных
усилий на разработку параллельного алгоритма. Для исследования
ускорения выполнения операции преобразования цветов изображения
в этом случае был
проведен ряд вычислительных экспериментов. Была
написана программа на языке C в среде MS Visual Studio C++, реали-
зующая параллельные вычисления с помощью
функций стандарта MPI
(Message Passing Interface – стандарт для написания параллельных ал-
горитмов на системах с распределенной памятью). Использовалась
свободно доступная реализация стандарта MPI – MPICH для локаль-
ной сети на базе Windows NT/2000 (разработана в Argonne
National
141
Laboratory совместно с Mississippi State University). Результаты экспе-
риментов приведены в таблице ниже. В столбце I указано время рабо-
ты параллельного алгоритма (в секундах), в столбце II
–
соответствующего последовательного и в III – отношение двух пре-
дыдущих величин.
Результаты работы
на процессоре 0
(Intel
Pentium III
550MHz)
Результаты работы
на процессоре 1
(Intel
Pentium II
350MHz)
Результаты работы
на процессоре 2
(Intel Pentium III
550MHz)
Размеры
изображения
I
II III I II III I II III
100000
×10000 32 51 1.59 46 72 1.56 29 47 1.62
200000
×10000 63 97 1.53 91 146 1.6 58 94 1.62
300000
×10000 91 143 1.57 136 218 1.6 87 140 1.6
400000
×10000 119 192 1.61 181 290 1.6 116 186 1.6
Достарыңызбен бөлісу: