Понятие параллельных алгоритмов

Параллельные алгоритмы.

Тема 6.

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

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

Примеры задач, в которых используется распараллеливание:

1) Одновременное выполнение операций ввода/вывода.

2) Формирование и обнуление массива.

3) Арифметические и логические операции над векторами и матрицами.

4) Одновременное отслеживание ветвей в различных узлах дерева.

5) Конвейерная обработка.

6) Решение СЛАУ большого порядка.

7) Параллельная сортировка.

8) Поиск максимума/минимума функции.

Сложность полученного параллельного алгоритма (ПА) дает выигрыш как минимум на порядок по сравнению с последовательным алгоритмом.

Сложность ПА оценивается гипотезой Минского: параллельные вычислительные системы, выполняющие последовательную программу под множеством исходных данных размера N, дают прирост производительности по крайней мере на показатель 1/log(N).

Однако при распараллеливании задач есть ряд «подводных камней»:

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

Кроме того, выбор средств разработки ПА весьма ограничен, а полученный параллельный код менее оптимизирован, чем для последовательных ЭВМ на этапе компиляции.

2) Быстрые последовательные алгоритмы во многих случаях дают более высокое быстродействие, чем ПА, построенные на основе прямого алгоритма решения задачи, а распараллеливание быстрого последовательного алгоритма является сложной задачей.

3) Для разработки ПА необходимо разбить задачу на независимые подзадачи с объединением результатов подзадач на последнем этапе. Этот процесс не поддается отладке, и быстродействие всего алгоритма сильно зависит от размеров подзадач и последнего этапа. В лучшем случае подзадачи должны быть маленьких и одинаковых размеров.

Пример 1:

ПА отыскания минимального остовного дерева.

Если одновременно выбрать для каждой вершины связанное с ней ребро с минимальным весом, то в остовном дереве возникнут замкнутые циклы, а это недопустимо.

V1: (V1, V2)

V2: (V2, V4)

V3: (V3, V2)

V4: (V4, V1)

V5: (V5, V4)

V6: (V6, V2)

Однако если выбрать для каждой вершины V_i ребро наименьшего веса, которое идентично вершине V_j (j¹i) с наименьшим индексом j, то исключается возможность циклов.

Это условие позволяет найти остовное дерево минимального веса за один шаг ПА. Однако при большом числе вершин рассмотренный алгоритм не настолько быстрый. Модификация этого алгоритма, предложенная Соллином, более эффективна. При этом сложность задачи уменьшается с O(N²) до O(log₂N).

Пример 2:

Задача сортировки массива из N целых чисел.

P_i –процессоры (i=1…N).

P₁ P₂ P₃ P₄ P₅ P₆ P₇ P₈

¯ ¯

¯ ¯

¯ ¯

¯ ¯

Дата добавления: 2014-01-07