Оценка эффективноти паралельных алгоритмов. Закон Амдала. Закон Густофсана

ВВЕДЕНИЕ
Организация параллельных вычислений, когда несколько операций обработки данных выполняются одновременно, осуществляется главным образом путем введения избыточности функциональных устройств (многопроцессорная обработка). В этом случае можно ускорить процесс решения вычислительной задачи, разделив применяемый алгоритм на независимые от информации части и организуя выполнение каждой части вычислений на разных процессорах. Такой подход позволяет выполнять необходимые расчеты с меньшими затратами времени, а возможность получения максимального ускорения ограничивается только количеством доступных процессоров и количеством «независимых» частей в расчетах.
С точки зрения параллелизма, как способа повышения эффективности расчетов, существуют две крайности. Первая - когда параллельные вычисления невозможны или очень мало эффективны. Обычно это связано с тем, что каждый шаг в алгоритме зависит от расчетов или состояния предыдущего шага. Embarrassingly parallel (чрезвычайный параллелизм) - совершенно другой тип задач, для которых не нужно прилагать больших усилий при разделении на несколько отдельных параллельных задач. Чаще всего между этими параллельными задачами нет взаимосвязи, то есть их результаты не влияют друг на друга.
Закон Амдала описывает метод, с помощью которого можно моделировать потенциальное повышение производительности в параллельных вычислениях.
Закон Густафсона оценивает максимально допустимое ускорение параллельного выполнения программ в зависимости от количества одновременно выполняемых вычислительных потоков и доли последовательных вычислений.
Оценка эффективности параллельных алгоритмов
Как и при анализе «обычных», последовательных алгоритмов, чаще всего рассматриваются асимптотические границы потребления ресурсов (в основном времени, затраченного на вычисления), но анализ выполняется при наличии нескольких процессорных блоков, которые взаимодействуют для выполнения вычислений. Таким образом, можно определить не только, сколько «шагов» занимает вычисление, но и насколько быстрее оно становится по мере увеличения числа процессоров. Интересно, что аналитический подход работает, сначала подавляя (или абстрагируя) количество процессоров.
Так называемая структура рабочего времени (WT) (иногда называемая рабочей глубиной или рабочим промежутком) была первоначально введена Шилоахом и Вишкиным для концептуализации и описания параллельных алгоритмов. В рамках WT параллельный алгоритм сначала описывается в терминах параллельных шагов. Для каждого шага характерны операции, которые должны быть выполнены, но несколько операций может быть пропущено. Структура WT полезна, поскольку, хотя она может значительно упростить начальное описание параллельного алгоритма, вставка деталей, скрытых этим начальным описанием, часто не очень сложна. Например, фреймворк WT был принят в качестве базового фреймворка представления в книгах параллельных алгоритмов (для параллельной модели Pram машины произвольного доступа), а также в примечаниях к классу.
Предположим, что вычисления выполняются на машине, имеющей P процессоров. Пусть Tp обозначает время, проходящее между началом вычисления и его окончанием. Анализ времени выполнения вычислений фокусируется на следующих понятиях:
Работа вычислений, выполняемых P процессорами, представляет собой общее число примитивных операций, выполняемых этими процессорами, игнорируя коммуникационные издержки от синхронизации процессоров, это равно времени, используемому для выполнения вычислений на одном процессоре, обозначенном T1.
Глубина или диапазон - это длина самой длинной серии операций, которые должны выполняться последовательно из-за зависимостей данных (критический путь). Глубина также может быть названа критической длиной пути вычисления. Минимизация глубины/промежутка важна при проектировании параллельных алгоритмов, поскольку глубина/промежуток определяет кратчайшее возможное время выполнения. В качестве альтернативы промежуток времени можно определить как время T∞, затраченное на вычисление с использованием идеализированной машины с бесконечным числом процессоров.
Стоимость расчета - это количество pTp. Это выражает общее время, затраченное всеми процессорами как на вычисление, так и на ожидание.
Несколько полезных результатов вытекают из определений работы, продолжительности и стоимости:
общее время, затраченное всеми процессорам на вычисление всегда равна, либо больше времени работы на одном процессоре (pTp ≥ T1). Это следует из того факта, что p процессоры могут выполнять не более p операций параллельно.
конечное число процессоров p не может превзойти бесконечное число, так что Tp ≥ T∞.
Используя эти определения и законы, можно описать следующие показатели эффективности.
Ускорение - это прирост скорости параллельного исполнения по сравнению с последовательным исполнением: Sp = T1 ∕ Tp

. Когда ускорение составляет Ω (n) для входного размера n (с использованием нотации big O), ускорение является линейным, что является оптимальным в простых моделях вычислений, поскольку закон работы подразумевает, что T1∕Tp ≤ p (сверхлинейное ускорение может происходить на практике из-за эффектов иерархии памяти). Ситуация T1∕Tp = p называется идеальным линейным ускорением. Алгоритм, который демонстрирует линейное ускорение, считается масштабируемым.
Эффективность - это ускорение на процессор, Sp∕p.
Параллелизм - это отношение T1∕T∞. Он представляет собой максимально возможное ускорение на любом количестве процессоров. По закону размаха параллелизм ограничивает ускорение: если p T1∕T∞, то: Т1Тр≤Т1Т∞р.
Оценка эффективности параллельных алгоритмов обычно проводится в предположении, что доступно неограниченное количество процессоров. Это нереально, но не является проблемой, поскольку любые вычисления, которые могут выполняться параллельно на N процессорах, могут выполняться на pN процессорах, позволяя каждому процессору выполнять несколько единиц работы. Результат, называемый законом Брента, гласит, что можно выполнить такое «моделирование» за время Tp, ограниченное Тр≤Тn+T1-Tnp, или более точно, Тр=О(Тn+T1p).
Альтернативное утверждение закона ограничивает Тр сверху и снизу, т.е. T1p≤Тр≤T1p+Т∞, показывая, что промежуток (глубина) Т∞ и работа T1 вместе дают разумные границы времени вычисления.
Закон Амдала
Закон Амдала предоставляет математическую формулу, которая вычисляет значение потенциального улучшения скорости совместной программы обработки за счет увеличения ее ресурсов (в частности, общего числа доступных процессоров). Закон Амдала посвящен исключительно потенциальному ускорению задержки из-за параллельного выполнения некоторой задачи. Хотя совместная обработка здесь не рассматривается, результаты Закона Амдала о параллельном исполнении, тем не менее, дадут нам оценку в отношении программ совместной обработки.
Значение скорости программы означает количество времени, необходимое для выполнения всей программы. Это может быть измерено в любой момент времени.
Ускорение - это значение времени, которое измеряет преимущество, полученное от параллельного выполнения вычислений. Оно определяется как время, которое требуется программе для последовательного выполнения (с одним процессором), деленное на значение времени, которое затрачивается на параллельное выполнение (со многими процессорами). Формула для расчета ускорения выглядит следующим образом:
S=T(1)T(j)
В нашей предыдущей формуле T(j) равно времени выполнения программы при использовании j процессоров.
Прежде чем мы перейдем к самой формуле закона Амдала, опишем концепцию ускорения. Предположим, что есть N исполнителей, обрабатывающих определенную задачу, которая может быть полностью выполнена параллельно, то есть эту задачу можно разделить исключительно на N эквивалентных разделов. Это означает, что N исполнителей, работающих вместе для выполнения этой задачи, будут тратить только 1/N времени, которое один исполнитель потратит на выполнение той же задачи.
Тем не менее, большинство вычислительных программ можно считать способными выполнять параллельно не на 100%: одна часть программы может иметь внутреннюю последовательность, а другая разделена на параллельные задачи.
Теперь пусть B обозначает ту часть программы, которая является строго последовательной, и рассмотрим следующее:
А) B * T(1) - количество времени, необходимое для выполнения той части программы, которая является по существу последовательной.
В) T(1) - B * T(1) = (1 - B) * T(1) равно времени, необходимому для выполнения той части программы, которая может выполняться параллельно с одним процессором. Тогда (1 - B)*T (1)/N - это время, которое занимает выполнение этой части с N процессорами.
С) Итак, B * T(1) + (1 - B) * T(1) / N - это общее время выполнения всей программы на N процессорах.
Возвращаясь к формуле определения ускорения, получим следующее:
S = T (1) / T (j) = T (1) / (B * T (1) + (1 - B) * T (1) / j) = 1 / (B + (1 - B) / j)
Эта формула фактически является формой закона Амдала, используемой для оценки ускорения в параллельной программе.
Рассмотрим пример