Анализ параллельных алгоритмов

В этой статье обсуждается анализ параллельных алгоритмов. Как и при анализе «обычных», последовательных алгоритмов, обычно интересуют асимптотические границы потребления ресурсов (в основном время, затрачиваемое на вычисления), но анализ выполняется при наличии нескольких процессорных блоков, которые сотрудничать для выполнения вычислений. Таким образом, можно определить не только, сколько «шагов» занимает вычисление, но также насколько быстрее оно становится по мере увеличения числа процессоров. Подход к анализу работает, сначала подавляя (или абстрагируясь) количество процессоров. В следующем абзаце поясняется, как впервые возникла абстракция числа процессоров.

Фреймворк так называемого рабочего времени (WT) (иногда называемый глубиной работы или продолжительностью работы) был первоначально введен Шилоачем и Вишкиным для концептуализации и описания параллельных алгоритмов. В рамках WT параллельный алгоритм сначала описывается в терминах параллельных раундов. Для каждого раунда описываются операции, которые необходимо выполнить, но некоторые проблемы могут быть устранены. Например, количество операций в каждом цикле не обязательно должно быть ясным, процессоры не должны упоминаться, и любая информация, которая может помочь с назначением процессоров для заданий, не должна учитываться. Во-вторых, предоставляется скрытая информация. Фактически, включение скрытой информации основывается на доказательстве теоремы о расписании, полученной Брентом, которая объясняется далее в этой статье. Структура WT полезна, поскольку, хотя она может значительно упростить начальное описание параллельного алгоритма, вставка деталей, подавленных этим начальным описанием, часто не очень сложно. Например, структура WT была принята в качестве базовой структуры представления в книгах по параллельным алгоритмам (для модели Параллельная машина с произвольным доступом PRAM), а также в примечаниях к классам. В приведенном ниже обзоре объясняется, как можно использовать структуру WT для анализа более общих параллельных алгоритмов, даже если их описание недоступно в рамках структуры WT.

Предположим, что вычисления выполняются на машине с p процессорами. Пусть T p обозначает время, которое истекает между началом вычисления и его концом. Анализ времени выполнения вычислений фокусируется на следующих понятиях:

• Работа вычисления, выполняемая p процессорами, - это общее количество примитивных операций, которые выполняют процессоры. Игнорируя накладные расходы связи от синхронизации процессоров, это равно времени, используемому для выполнения вычислений на одном процессоре, обозначается T 1.
• . Глубина или интервал - это длина самой длинной серии операций, которые должны выполняться последовательно из-за зависимости данных (критический путь). Глубину также можно назвать критической длиной пути вычисления. Минимизация глубины / диапазона важна при разработке параллельных алгоритмов, поскольку глубина / диапазон определяет минимально возможное время выполнения. В качестве альтернативы диапазон может быть определен как время T ∞, затраченное на вычисления с использованием идеализированной машины с бесконечным числом процессоров.
• Стоимость вычислений равна величине pT p. Это выражает общее время, затраченное всеми процессорами как на вычисления, так и на ожидание.

Из определений работы, продолжительности и стоимости следует несколько полезных результатов:

• Закон о работе. Стоимость всегда не меньше работы: pT p ≥ T 1. Это следует из того факта, что p процессоров могут выполнять не более p операций параллельно.
• Закон диапазона. Конечное число процессоров p не может превзойти бесконечное число процессоров, поэтому T p ≥ T ∞.

Используя эти определения и законы, можно дать следующие показатели производительности:

• Speedup is выигрыш в скорости за счет параллельного выполнения по сравнению с последовательным выполнением: S p = T 1 ∕ T p. Когда ускорение составляет Ω (n) для размера входа n (с использованием нотации большого O ), ускорение является линейным, что является оптимальным для простых моделей вычислений, поскольку закон работы подразумевает, что T 1 ∕ T p ≤ p (сверхлинейное ускорение может иметь место на практике из-за эффектов иерархии памяти ). Ситуация T 1 ∕ T p = p называется идеальным линейным ускорением. Алгоритм, демонстрирующий линейное ускорение, называется масштабируемым.
• Эффективность - это ускорение на процессор, S p ∕ p.
• Параллелизм - это отношение T 1 ∕ T ∞. Он представляет собой максимально возможное ускорение на любом количестве процессоров. По закону диапазона параллелизм ограничивает ускорение: если p>T 1 ∕ T ∞, то:

.

• вялость составляет T 1 ∕ (pT ∞). Промежуток меньше единицы означает (по закону диапазона), что идеальное линейное ускорение невозможно на процессорах p.

Анализ параллельных алгоритмов обычно выполняется в предположении, что доступно неограниченное количество процессоров. Это нереально, но не проблема, поскольку любые вычисления, которые могут выполняться параллельно на N процессорах, могут выполняться на p < N processors by letting each processor execute multiple units of work. A result called Brent's law states that one can perform such a "simulation" in time Tp, ограниченном

$T\; p\; \le \; TN\; +\; T\; 1\; -\; TN\; p,\; \{\backslash \; displaystyle\; T\_\; \{\; p\}\; \backslash \; leq\; T\_\; \{N\}\; +\; \{\backslash \; frac\; \{T\_\; \{1\}\; -T\_\; \{N\}\}\; \{p\}\},\}$

или, менее точно,

$T\; p\; =\; O\; (TN\; +\; T\; 1\; p).\; \{\backslash \; displaystyle\; T\_\; \{p\}\; =\; O\; \backslash \; left\; (T\_\; \{N\}\; +\; \{\backslash \; frac\; \{T\_\; \{1\}\}\; \{p\}\}\; \backslash \; right).\}$

Альтернативная формулировка закона ограничивает T p сверху и снизу на

$T\; 1\; p\; \le \; T\; p\; \le \; T\; 1\; p\; +\; T\; \infty \; \{\backslash \; displaystyle\; \{\backslash \; frac\; \{T\_\; \{1\}\}\; \{p\}\}\; \backslash \; leq\; T\_\; \{p\}\; \backslash \; leq\; \{\backslash \; frac\; \{T\_\; \{1\}\}\; \{p\}\}\; +\; T\; \_\; \{\backslash \; infty\}\}$.

, показывающий, что интервал (глубина) T ∞ и работа T 1 вместе обеспечивают разумные границы по времени вычислений.