- •Лекция 1. Введение
- •Принципы параллельных вычислений
- •Лекция 2.
- •Лекция 3.
- •Эффективность параллельных вычислений (закон Амдала)
- •Закон Мура и его перспективы.
- •Каждые 2 года количество транзисторов на кристалле удваивается
- •Лекция 4. Основные этапы развития параллельной обработки
- •Лекция 5. Мелкозернистый параллелизм
- •Принципы распараллеливания и планирования базовых блоков.
- •Лекция 6. Алгоритм автоматического распараллеливания арифметических
- •Лекция 7.
- •Лекция 8.
- •Лекция 9.
- •Лекция 10.
- •Лекция 11. Крупнозернистый параллелизм
- •Классификация Флинна
- •Арифметические конвейеры
- •Лекция 12. Многопроцессорные системы с общей памятью или
- •Лекция 13. Многопроцессорные системы с индивидуальной памятью или Массивно-параллельные системы (mpp)
- •Средства параллельного программирования Параллельные алгоритмы
- •Лекция 14. Стандарт mpi
- •Mpi программа для вычисления числа π на языке с.
- •Программа умножения матрицы на вектор
- •Лекция 15.
- •Лекция 16.
- •Вычислительные кластеры.
- •Лекция 17.
- •Лекция 18. Параллельные вычисления в грид Некоторые этапы развития it технологий
- •Лекция 19. Грид
- •Облачные вычисления
- •Лекция 20. Пакет Globus Toolkit.
- •Параллельные вычислени в грид. Пакет g2.
Средства параллельного программирования Параллельные алгоритмы
Вычислительные алгоритмы обладают различным уровнем параллелизма.
Для некоторых классов задач имеется качественная оценка величины паралле-
лизма. Некоторые результаты такой оценки представлены в следующей таблице
Характеристики некоторых параллельных алгоритмов
№ |
Наименование алгоритма |
Время вычислений |
Число процессов |
1
2
3
4 5 6 7
1
2
3
1 2 3
4 5
6
1 2
|
Алгебра Решение треугольной системы уравнений, обращение треугольной матрицы Вычисление коэффициентов характеристического уравнения матрицы Решение системы линейных уравнений, обращение матрицы Метод исключения Гаусса Вычисление ранга матрицы Подобие двух матриц Нахождение LU-разложения симметричной матрицы
Комбинаторика ε —оптимальный рюкзак, n — размерность задачи Задача о покрытии с гарантированной оценкой отклонения не более, чем в (1+ε)log d раз Нахождение ε — хорошей раскраски в задаче о балансировке множеств
Теория графов Ранжирование списка Эйлеров путь в дереве Отыскание дерева минимального веса Транзитивное замыкание Раскраска вершины в Δ + 1 и Δ цветов Дерево поиска в глубину для графа
Сортировка и поиск Сортировка Слияние для двух массивов размера n и m, N = m+m
|
0( log2 n )
0( log2 n )
0( log2 n )
0( log2 n ) 0( log2 n ) 0( log2 n ) 0( log 3 n )
0(log n log (n/ε))
0(log2 n logm)
0(log3 n)
0(log n) 0(log n) 0 ( log2 n )
0 ( log2 n ) 0(log3 n loglogn)
0(log3 n)
0 (log n) 0( + log N)
|
0( n4 / log2 n )
0( n4 / log2 n )
0( n w+1 ) полиномиальное
0( n4 / log2 n )
0(n3 / ε2 )
0(n)
полиномиальное
0(n/log n) 0(n/log n)
0(n+m)
0(n)
0(n) P = 0(N / log N) |
Скрытый параллелизм. Необходимое условие параллельного выполнения i-й и j-й итераций цикла записывается как и в случае арифметических выражение в виде правила Рассела для циклов:
(OUT(i) AND IN(j)) OR (IN(i) AND OUT(j)) OR (OUT(i) AND OUT(j))=0
Приведем примеры зависимостей между итерациями – прямая (а), обратная
(б) и конкуренционная (в):
а) Итерация i а ( i ) = a ( i –1) итерация 5 а(5) = а(4)
---------------------------------------
Итерация i+1 a (i + 1) = a ( i ) итерация 6 а(6) = а(5)
б) Итерация i a (i – 1) = a ( i ) итерация 5 а(4) = а(5)
--------------------------------------
Итерация i + 1 a ( i ) = a ( i = 1) итерация 6 а(5) = а(6)
в) Итерация i s =
--------------------------------------
Итерация i + 1 s =
Знание оценок из таблицы не дает еще возможности построить практический параллельный алгоритм. Во многих случаях он не очевиден и его еще нужно различными приемами проявить в форме, доступной для программирования на некотором параллельном языке. Пример такого проявления приводится ниже.
Рассмотрим метод гиперплоскостей, предложенный L.Lamport в 1974 году на примере решения уравнений в частных производных. Метод носит название “фронта волны”. Пусть дана программа для вычисления в цикле значения Xi,j как среднего двух смежных точек (слева и сверху):
DO 1 I = 1,N
DO 1 J = 1,N
1 X (I, J) = X (I-1, J) + Y (I, J –1) + C
Рассмотрим две любые смежные по значениям индексов итерации, например:
X(2,2) = X(1,2) + X(2,1)
X(2,3) = X(1,3) + X(2,2)
Между итерациями существует прямая зависимость. Использовать для сложения смежные строки нельзя, так как нижняя строка зависит от верхней. Нельзя складывать и смежные столбцы, так как правый столбец зависит от левого. Тем не менее параллелизм в задаче есть, например, все операции в диагонали 41, 42, 43, 44 можно выполнять параллельно.
Если повернуть оси I, J на 45 градусов и переименовать операции внутри каждой диагонали,как на следующем рисунке, то можно использовать этот параллелизм. Соответствующая программа для верхних диагоналей (включая глав
ную) и нижних диагоналей приведена ниже:
DO 1 I = 1,N Пусть I =3, тогда x(3,1)=x(2,1)+x(3,0)
DO PAR J = 1, I x(3,2)=x(2,2)+x(2,1)
X (I, J) = X(I-1, J) + X(I-1, J-1) x(3,3)=x(2,3)+x(2,2)
1 CONTINUE Эти итерации действительно независимы
---------------------------------------
K + 2
DO 2 I = N +1, 2N – 1
DO PAR J + K, N
R = K + 1
X(I, J) = x(I-1, J) + X(I-1, J-1) + C
2 CONTINUE
Здесь К = 1,2 обозначает левый - верхний или правый - нижний треугольник пространства итераций.
Алгоритм метода гиперплоскостей состоит в следующем:
1. Производится анализ индексов и построение зависимостей в пространстве
итераций
2. Определяется угол наклона осей и переименование переменных
3. Строится параллельная программ
Недостаток метода гиперплоскостей состоит в том, что ширина параллелизма в каждой итерации параллельной программы неодинакова. Это исключено в методе параллелепипедов и ряде других методов.
Для параллельного программирования существует ряд языков. Основные из них:
• OpenMP – для многопроцессорных систем с общей памятью
• MPI - для многопроцессорных систем с индивидуальной памятью
Существует часто некоторая путаница между OpenMP и MPI. Эта путаница вполне понятно, поскольку есть еще версия MPI называется "Open MPI". С точки зрения программиста, MPI является библиотекой, которая содержит процедуры передачи сообщений. OpenMP, с другой стороны, представляет собой набор директив компилятора, которые сообщают OpenMP, если включен компилятор, какие части программы может быть запущены как нити. Таким образом, разница «нити» против «сообщений». Рассмотрим оба метода.
Вопросы для самоконтроля
В чем заключается сетевой закон Амдала?
Назовите пример параллельных ЭВМ с обменом сообщениями.
В чем заключается скрытый параллелизм?