.Определение 5. Ускорением параллельного алгоритма называется отношение:
.
Для задачи сложения векторов следовало бы ожидать, что
,
т.е. ускорение максимально. Заметим, однако, что в
определении подразумеваются действительные времена вычислений. Это делает
определение более реалистичным, но затрудняет его использование в том случае,
если требуемые времена неизвестны. Рассмотрим сложение n чисел с помощью алгоритма
сдваивания в системе из n/2 процессоров с локальной памятью. Пусть а1 и а2 хранятся в памяти процессора 1,
a3
и а4 – в памяти процессора 2 и т. д. Прежде, чем можно будет выполнять сложения
второго этапа, необходимо передать число а3+a4
процессору 1, число а7+a8
– процессору 3 и т.д. Аналогичные переносы данных требуются на каждом этапе,
что, конечно, увеличивает общее время выполнения алгоритма. Предположим, что для
одного сложения нужно время t, а для переноса одного числа - время at;
обычно a больше единицы. Игнорируя прочие издержки, имеем для алгоритма сложения (с
учетом равенства р=n/2)
.
Заметим, что в данном случае ускорение есть средняя степень параллелизма, деленная на 1+a. Если a - величина, близкая к единице, т.е. на обмены затрачивается примерно столько же времени, сколько на арифметику, то ускорение уменьшится приблизительно вдвое по сравнению с идеальной ситуацией, когда a=0. С другой стороны, если a велико, скажем, a=10, то время на обмены доминирует над временем вычислений; соответственно падает ускорение. Ускорение позволяет сравнивать поведение данного алгоритма для одного и p процессоров.
С ускорением связана эффективность параллельного алгоритма.
Определение 6.
Эффективностью параллельного
алгоритма называется величина:
.
Поскольку
.
Если алгоритм достигает максимального ускорения
(), то
.
