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

ПАРАЛЛЕЛЬНОЕ ПРОГРАММИРОВАНИЕ
19
Для выбранной схемы вычислений желательно использование множества,
обеспечивающего минимальное время исполнения алгоритма
( ) ( )
p
H p HGT GT
p
, min = .
За счет подбора наилучшей вычислительной схемы можно существенно
уменьшить время выполнения
( )GT T p G p min = .
Оценки ( )
p p H,GT, ( )GT
p и p T могут быть использованы в качестве показателей
времени выполнения параллельного алгоритма. Для определения минимально
возможного времени выполнения параллельного алгоритма при использовании
неограниченного количества процессоров (вычислительная система с бесконечным
количеством процессоров или паракомпьютер) можно использовать соотношение
p
p
T T
1
min
≥ ∞ = .
Оценка T1 определяет время выполнения алгоритма при использовании одного
процессора и представляет тем самым время выполнения последовательного вари-
анта алгоритма решения задачи. Построение подобной оценки является важной про-
блемой при анализе параллельных алгоритмов, поскольку применяется для опреде-
ления эффекта использования параллельности (ускорения времени решения задачи).
Очевидно
( ) V GT =
1 ,
где V , напомним, есть количество вершин вычислительной схемы G без вершин
ввода. Важно отметить, что если при определении оценки T1 ограничиться
рассмотрением только одного выбранного алгоритма решения задачи
( )GT T G 1 1 min = ,
то получаемые при использовании такой оценки показатели ускорения будут харак-
теризовать эффективность распараллеливания выбранного алгоритма. Для оценки
эффективности параллельного решения исследуемой задачи вычислительной мате-
матики величину T1 следует определять с учетом всех возможных последовательных
алгоритмов
1
*
1 min T T = .