13. Время простоя. Пример общей модели.

Время простоя. Время вычислений и коммуникаций обычно можно определить из алгоритма. Время простоя в этом смысле представляет проблему. Процессор может простаивать из-за недостатка вычислений или недостатка данных. Вспомним примеры из лабораторных работ. В 1-м случае можно использовать алгоритмы балансировки нагрузки. Во 2-м случае часто удается перепроектировать алгоритм так, чтобы во время ожидания внешних данных процессор выполнял другие вычисления или коммуникации. Это называется перекрытием вычислений и коммуникаций. Для этого используется 2 подхода. В 1-м случае на каждом процессоре создается несколько задач. Во время простоя 1-ой из них выполняется другая. Это наиболее простой подход, но он связан с затратами на запуск дополнительных задач. Во 2-м подходе сама задача строится так, что участки вычислений чередуются с участками коммуникаций.

Рассмотрим снова пример с конечными разностями. Пусть используется решетка NxNxZ точек (Z – в вертикальном направлении). Предполагаем декомпозицию в одном из горизонтальных направлений. Тогда каждая задача отвечает за часть решетки размером Nx(N/P)xZ точек, где P – число процессоров. Каждая задача выполняет одинаковые вычисления для каждой точки и на каждом шаге. Поскольку вычисления не повторяются, то время вычислений на 1 шаге составляет Tcomp = t1 * N**2 * Z, где t1 – время вычислений для 1 точки.

Примем, что вычисления выполняются с 9-точечным шаблоном. Тогда каждая задача должна обмениваться 2*N*Z значениями с каждой из 2 соседних задач, что дает 2 сообщения и 4*N*Z элементов данных (в предположении, что на каждый процессор приходится часть решетки по крайней мере 2хN, иначе требуется коммуникация более чем с 2 соседями). Следующая, модель применима не более чем при N / 2 процессорах. Общие затраты на коммуникацию, суммарно по P процессорам, составляет:

Tcomm = 2* P * (ts + tw * 2 * N * Z)

Если N делится на P и количество вычислений на каждую точку решетки постоянно, то временем простоя можно пренебречь. Тогда общая модель будет выглядеть так:

T = (Tcomp + Tcomm) / P = ts * (N**2 * Z / P) + ts * 2 + tw * 4 * N * Z

12. Эффективность и ускорение. Анализ масштабируемости – при фиксированном размере задачи, при переменном размере задачи.

Эффективность и ускорение.

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

E = T1 / (P * Tp),

где T1 – время выполнения на 1 процессоре, Tp - на P процессорах. Связанная метрика – относительное ускорение – определяется как S = P * E и показывает, на сколько уменьшится время выполнения на P процессорах. Эти метрики называются относительными, так как они определены по отношению к параллельному алгоритму, выполняемому на 1 процессоре. Они полезны при оценке масштабируемости алгоритма, но не являются абсолютно достоверными. Например, 1 алгоритм выполняется за 10000 сек на 1 процессоре и за 20 сек на 1000 процессорах, а 2-й – 1000 и 5. Очевидно, что в диапазоне 1-1000 процессоров 2-й алгоритм лучше, хотя относительное ускорение составляет для него только 200 по сравнению с 500 для 1 алгоритма.

При сравнении алгоритмов полезно иметь метрику, независящую от алгоритма, помимо времени выполнения. Определим абсолютную эффективность и ускорение, приняв за точку отсчета T1 время выполнения на 1 процессоре наилучшего известного алгоритма (часто это последовательный алгоритм).

Для конечно-разностного алгоритма T1 = t1 * N**2 * Z, поэтому при сбалансированной нагрузке и при N mod P = 0 эффективность равна:

E = T1/(P*Tp) = (t1 * N**2 * Z) / (ts * N**2 * Z + ts * 2 * P+ tw * 4 * N * Z * P) (3.7)

Так как однопроцессорный алгоритм идентичен параллельному при P=1, это выражение представляет абсолютную эффективность.

Масштабируемость при фиксированном размере задачи.

Важный аспект анализа производительности – изучение того, как производительность алгоритма зависит от таких параметров, как размер проблемы, количество процессоров и ts. В частности, мы можем оценить масштабируемость алгоритма, т.е. насколько эффективно он использует увеличение числа процессоров. Один из способов количественной оценки этого – определить, как изменяется с увеличением числа процессоров эффективность и время выполнения. Это дает ответы на такие вопросы, как «насколько быстро можно решить проблему А на компьютере Х», «сколько процессоров можно использовать, сохраняя эффективность не менее 50%» (последний вопрос важен, если ресурсы компьютера разделяются.).

При оценке масштабируемости важно исследовать как Е, так и Т. Если Е обычно растет с увеличением Р, то Т может расти или уменьшаться, часто давая предел числа процессоров.

Масштабируемость при изменении размера программы.

Большие мпк часто используются не только для того, чтобы быстрее решить проблему фиксированного размера, но и для того, чтобы решать проблему большего размера.. Это требует другого подхода к проблеме, когда анализируется не только зависимость Е от Р, но также и то, как должно меняться количество вычислений с увеличением Р, чтобы Е оставалось постоянной. Последний фактор, рассматриваемый как функция от N, называют функцией равной эффективности. Он вносит весомый вклад в изучение поведения алгоритма. Так, алгоритм с функцией равной эффективности вида О(Р) является хорошо масштабируемым, так как количество вычислений растет только линейно.

Если эффективность определилась как E = T1/(P*Tp), то для поддержания постоянной Е нужно соблюдать следующее соотношение:

Т1 = Е * (Тcomp + Tcomm+Tidle)

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

Общее правило: многомерные декомпозиции обычно более эффективны. В то время как двумерная декомпозиция посылает немного большее количество сообщений (четыре вместо двух), объем данных меньше. Полные коммуникационные затраты уменьшаются, если P и N не малы, или t_s является намного большим чем t_w.