Основы распараллеливания алгоритмов

Лекция 8. Оценка параллельных алгоритмов

8.1. ярусно-параллельная форма алгоритма

При разработке параллельных алгоритмов решения задач вычислительной математики принципиальным моментом является анализ эффективности использования параллелизма, состоящий обычно в оценке получаемого ускорения процесса вычисления (сокращения времени решения задачи).
Для упрощения оценки алгоритмов вводится ряд допущений:

1. 
   параллельная вычислительная система, на которой будет выполняться алгоритм, состоит из любого нужного числа процессоров и произвольно большой памяти, одновременно доступной всем процессорам.
   
2. 
   каждый процессор за единицу времени может выполнить любую унарную или бинарную операцию.
   
3. 
   время выполнения всех вспомогательных операций, а также время взаимодействия с памятью и время, затрачиваемое на управление процессом, считаются пренебрежимо малыми.
   
4. 
   все входные данные перед началом вычислений записаны в памяти. Каждый процессор считывает свои операнды из памяти и после выполнения операции записывает результат в память.
   
5. 
   после окончания вычислительного процесса все результаты остаются в памяти.
   
6. 
   все процессоры и устройство памяти объединяются в единую систему, связанную каналами передачи информации.
   

Для описания существующих информационных зависимостей в выбираемых алгоритмах решения задач может быть использована модель в виде графа алгоритмов.
Представим множество операций, выполняемых в исследуемом алгоритме решения вычислительной задачи, и существующие между операциями информационные зависимости в виде ациклического ориентированного графа
G = (V, R) , где
где V = {1, …, |V|} есть множество вершин графа, представляющее выполняемые операции алгоритма, а R есть множество дуг графа (при этом дуга r = (i, j) принадлежит графу только, если операция j использует результат выполнения операции i).
Ярусно-параллельная форма графа (ЯПФ) — деление вершин графа алгоритма на пронумерованное подмножество V_i такое, что, если дуга r идет от вершины к вершине , то обязательно j < k.
Каждое из множеств V_i называется ярусом ЯПФ, i — его номером, количество вершин в ярусе — его шириной. Количество ярусов в ЯПФ называется её высотой, а максимальная ширина её ярусов — шириной ЯПФ.
Для ЯПФ графа алгоритма важным является тот факт, что операции, которым соответствуют вершины одного яруса, не зависят друг от друга, и поэтому заведомо существует параллельная реализация алгоритма, в которой они могут быть выполнены параллельно на разных устройствах вычислительной системы. Поэтому ЯПФ графа алгоритма может быть использована для подготовки такой параллельной реализации алгоритма.