Добавил:
Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:
учебник_Вс.doc
Скачиваний:
14
Добавлен:
01.03.2025
Размер:
13 Мб
Скачать
☆

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

Для оценки эффективности работы параллельных алгоритмов используется ряд показателей, таких как коэффициент накладных расходов, коэффициент ускорения и коэффициент эффективности p-программы.

  1. Коэффициент накладных расходов определяется по формуле

ε = t/T ,

где t – время, расходуемое ВС на организацию и реализацию всех обменов информацией между вычислительными модуляи, Т – время, требующееся на выполнение арифметических и логических операций при реализации параллельного алгоритма.

Рассмотрим использование этого показателя на примере умножения матриц (см. раздел 2.2.1).

В каждом вычислителе выполняется K*]M/n[ -умножений, (K-1)*]M/n[ - сложений.

При достаточно большом значении K можно считать, что на каждый принятый элемент матрицы А приходится ρ операций сложения и умножения:

ρ = ]M/n[

Пусть tп­ – время пересылки одного элемента матрицы, tс – время сложения двух чисел, tу – время умножения двух чисел.

Тогда эффективность можно определить в виде:

ε = tп / ρ(tу + tс) = e / ρ , где e = tп / (tу + tс).

Из этого соотношения видно, что максимум накладных расходов будет, когда ρ=1 или n=M. Величина ρ=1 информирует о минимально допустимом размере матриц, при котором ещё целесообразно вычисление задачи на n вычислителях. С другой стороны, при фиксированном n, увеличение размера матриц приводит к росту ρ, следовательно, к уменьшению накладных расходов. Ясно, что чем больше размеры матриц (чем больше размеры вычислений), тем выше эффективность параллельного алгоритма, т.е. ε→0, ρ→∞.

  1. Коэффициент ускорения определяется по соотношению

χ = τ1 /τn , (2.2.26)

где τ1 – время выполнения алгоритма (решения задачи) на одном ВМ, τn­ – время

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

Как известно, что одна и та же задача может решатся различными по эффективности алгоритмами, поэтому вводится дополнительное соотношение, учитывающее это обстоятельство:

χ’ = τ1’ /τn , (2.2.27)

где τ1’ – время выполнения последовательного наилучшего алгоритма, τn – величина, взятая из соотношения (2.2.26).

Для определения коэффициента ускорения часто используют закон Амдаля, который используется, если известны более подробные характеристики ВС и выполняемых алгоритмов:

А ≤ k / (δ+(1 – δ)/N),

где N – количество ВМ входящих в ВС, δ – относительная доля операций параллельной программы, выполненных последовательно, 0 ≤ δ ≤ 1. δ =1 – программа относительно последовательна и δ= 0 – программа относительно параллельна. k – корректирующий коэффициент 0 ≤ k ≤ 1. Он определяет качество параллельной системы, т.е. система характеризуется временными издержками, связанными с настройкой структуры системы, синхронизацией ветвей параллельной программы и временными издержками, связанными с обменом информацией между ВМ.

3) Для определения качества параллельной программы используется коэффициент её эффективности:

E = χ / N, (2.2.28)

где χ - коэффициент ускорения, определённый по формуле, N – число вычислительных модулей в ВС.

Если χ ≤ N, то E ≤ 1. Если параллельный алгоритм обеспечивает максимальное ускорение, то χ = N и E = 1. Основной целью распараллеливания сложных задач является достижение равенства max χ = N. Аналогичные соотношения получим при использовании χ’.

Основные причины, препятствующие получению этого равенства:

  1. время, расходуемое на синхронизацию параллельных ветвей процессов и на обмен информацией между ними, а также на конфликты памяти, обусловленные, например, её общедоступностью или наоборот её распределённостью.

  2. несбалансированность нагрузки вычислителей и/или невозможность построения p-алгоритма с числом ветвей, равным числу вычислителей ВС.