Р. Г. Стронгина. Ниж- ний Новгород: Изд-во Нижегородского университета, 2002, 217 с
Некоторые вопросы распараллеливания алгоритмов
жүктеу/скачать 1,64 Mb. Pdf көрінісі
|
Seminar 1
| Некоторые вопросы распараллеливания алгоритмов
преобразования цветов между различными цветовыми пространствами Как показано выше, при преобразовании цветов широко исполь- зуются операции линейной алгебры. Это, прежде всего, операции пе- ремножения матриц и умножения вектора на матрицу. Распараллели- 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 жүктеу/скачать 1,64 Mb. Достарыңызбен бөлісу:
|