Стр. 22 - Параллельное программирование

ПАРАЛЛЕЛЬНОЕ ПРОГРАММИРОВАНИЕ
20
(эффективный параллельный алгоритм может не совпадать с наилучшим последова-
тельным методом при исполнении на одном процессоре).
Приведем без доказательства теоретические положения, характеризующие
свойства оценок времени выполнения параллельного алгоритма [18].
Теорема 1. Минимально возможное время выполнения параллельного
алгоритма определяется длиной максимального пути вычислительной схемы
алгоритма, т.е [1].
( ) ( )Gd GT =
∞ .
Теорема 2. Пусть для некоторой вершины вывода в вычислительной схеме ал-
горитма существует путь из каждой вершины ввода. Кроме того, пусть входная сте-
пень вершин схемы не превышает 2. Тогда минимально возможное время выполне-
ния параллельного алгоритма ограничено снизу значением[1]
( ) n GT 2 log =
∞ ,
где n есть количество вершин ввода в схеме алгоритма.
Теорема 3. При уменьшении числа используемых процессоров время выпол-
нения алгоритма увеличивается пропорционально величине уменьшения количества
процессоров, т.е. [1] q p cT T c cp q ≤⇒> =∀ 0 , .
Теорема 4. Для любого количества используемых процессоров справедлива
следующая верхняя оценка для времени выполнения параллельного алгоритма [1]
pT T T p
p /
1 + <⇒∀
∞ .
Теорема 5. Времени выполнения алгоритма, сопоставимым с минимально
возможным временем T∞, можно достичь при количестве процессоров порядка
∞ TTp / ~
1 , а именно [1]
∞ ∞ ≤⇒ ≥T T TTp
p 2 /
1 .
При меньшем количестве процессоров время выполнения алгоритма не может
превышать более чем в два раза наилучшее время вычислений при имеющемся
числе процессоров, т.е.
p
T T
p
T TTp
p
1 1
1 2 / ≤ ≤⇒ <
∞ .
Приведенные утверждения позволяют дать следующие рекомендации по
правилам формирования параллельных алгоритмов: