Анализ параллельных алгоритмов - Analysis of parallel algorithms

В информатике анализ параллельных алгоритмов - это процесс определения вычислительной сложности алгоритмов, выполняемых параллельно, - количества времени, памяти или других ресурсов, необходимых для их выполнения. Во многих отношениях анализ параллельных алгоритмов аналогичен анализу последовательных алгоритмов , но, как правило, более сложен, потому что необходимо рассуждать о поведении нескольких взаимодействующих потоков выполнения. Одна из основных целей параллельного анализа - понять, как использование ресурсов параллельным алгоритмом (скорость, пространство и т. Д.) Изменяется при изменении количества процессоров.

Задний план

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

Определения

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

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

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

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

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

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

${\ displaystyle {\ frac {T_ {1}} {T_ {p}}} \ leq {\ frac {T_ {1}} {T _ {\ infty}}} <p}$ .

• Вялость является Т ₁ / ( рТ _∞ ) . Задержка меньше единицы означает (по закону диапазона), что идеальное линейное ускорение невозможно на процессорах p .

Выполнение на ограниченном количестве процессоров

Анализ параллельных алгоритмов обычно проводится в предположении наличия неограниченного количества процессоров. Это нереально, но не проблема, поскольку любые вычисления, которые могут выполняться параллельно на N процессорах, могут выполняться на p < N процессорах, позволяя каждому процессору выполнять несколько единиц работы. Результат, называемый законом Брента, гласит, что можно выполнить такое «моделирование» за время T _p , ограниченное

${\ displaystyle T_ {p} \ leq T_ {N} + {\ frac {T_ {1} -T_ {N}} {p}},}$

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

${\ displaystyle T_ {p} = O \ left (T_ {N} + {\ frac {T_ {1}} {p}} \ right).}$

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

${\ displaystyle {\ frac {T_ {1}} {p}} \ leq T_ {p} \ leq {\ frac {T_ {1}} {p}} + T _ {\ infty}}$.

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

использованная литература