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


Download 227.5 Kb.
bet4/6
Sana01.04.2023
Hajmi227.5 Kb.
#1316546
TuriЛекция
1   2   3   4   5   6
Bog'liq
Лекция 8

Теорема 1. Минимально возможное время выполнения параллельного алгоритма определяется длиной максимального пути вычислительной схемы алгоритма, т.е.
.
Теорема 2. Пусть для некоторой вершины вывода в вычислительной схеме алгоритма существует путь из каждой вершины ввода. Кроме того, пусть входная степень вершин схемы не превышает 2. Тогда минимально возможное время выполнения параллельного алгоритма ограничено снизу значением
,
где n есть количество вершин ввода в схеме алгоритма.
Теорема 3. При уменьшении числа используемых процессоров время выполнения алгоритма увеличивается пропорционально величине уменьшения количества процессоров, т.е.
.
Теорема 4. Для любого количества используемых процессоров справедлива следующая верхняя оценка для времени выполнения параллельного алгоритма
.
Теорема 5. Времени выполнения алгоритма, сопоставимым с минимально возможным временем T∞, можно достичь при количестве процессоров порядка p T1 / T∞, а именно,
.
При меньшем количестве процессоров время выполнения алгоритма не может превышать более чем в 2 раза наилучшее время вычислений при имеющемся числе процессоров, т.е.
.
Приведенные утверждения позволяют дать следующие рекомендации по правилам формирования параллельных алгоритмов:

  1. при выборе вычислительной схемы алгоритма должен использоваться граф с минимально возможным диаметром (см. теорему 1);

  2. для параллельного выполнения целесообразное количество процессоров определяется величиной p ≥ T1 / T∞ (см. теорему 5);

  3. время выполнения параллельного алгоритма ограничивается сверху величинами, приведенными в теоремах 4 и 5.

8.3. Показатели эффективности параллельного алгоритма


Ускорение, получаемое при использовании параллельного алгоритма для p процессоров, по сравнению с последовательным вариантом выполнения вычислений определяется
,
т.е. как отношение времени решения задач на скалярной ЭВМ к времени выполнения параллельного алгоритма (величина n используется для параметризации вычислительной сложности решаемой задачи и может пониматься, например, как количество входных данных задачи).
Максимальный фактор ускорения Sp(n)=n (линейное ускорение). В общем случае Sp(n)< p, так как параллельный алгоритм обычно не может обеспечить идеальной балансировки нагрузки процессоров.
Отсутствие максимального ускорения обусловлено различными факторами
отсутствие максимального параллелизма в алгоритме и/или несбалансированность нагрузки процессоров
обмены, конфликты памяти и затраты на временя синхронизации
Природа различная – результат один: задержки

Теоретически возможны алгоритмы с суперлинейным ускорением Sp (n)>p. Это возможно, например, в алгоритмах поиска.





Download 227.5 Kb.

Do'stlaringiz bilan baham:
1   2   3   4   5   6




Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©fayllar.org 2024
ma'muriyatiga murojaat qiling