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

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

Фон

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

Определения

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

• Работа вычисления , выполняемая p процессорами, равна общему числу примитивных операций, выполняемых процессорами. ^[6] Если не учитывать издержки связи, связанные с синхронизацией процессоров, это время равно времени, используемому для выполнения вычислений на одном процессоре, обозначенному T ₁ .
• Глубина или диапазон — это длина самой длинной серии операций , которые необходимо выполнять последовательно из-за зависимостей данных ( критический путь ). Глубину также можно назвать длиной критического пути вычислений. ^[7] Минимизация глубины/диапазона важна при разработке параллельных алгоритмов, поскольку глубина/диапазон определяет кратчайшее возможное время выполнения. ^[8] Альтернативно, интервал можно определить как время T _∞ , потраченное на вычисления с использованием идеализированной машины с бесконечным числом процессоров. ^[9]
• Стоимость вычислений равна величине pT _p . Это выражает общее время, затраченное всеми процессорами как на вычисления, так и на ожидание. ^[6]

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

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

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

• Ускорение — это прирост скорости при параллельном выполнении по сравнению с последовательным _: Sp = T ₁ / T _p . Когда ускорение равно Ω( p ) для p процессоров (с использованием обозначения большого O ), ускорение является линейным, что является оптимальным в простых моделях вычислений, поскольку закон работы подразумевает, что T ₁ / T _p ≤ p ( суперлинейное ускорение может происходят на практике из-за эффектов иерархии памяти ). Ситуация T ₁ / T _p = p называется идеальным линейным ускорением. ^[9] Алгоритм, демонстрирующий линейное ускорение, называется масштабируемым . ^[6]
• Эффективность — это ускорение каждого процессора, S _p / p . ^[6]
• Параллельностью называется отношение T ₁ / T _∞ . Он представляет собой максимально возможное ускорение на любом количестве процессоров. По закону размаха параллелизм ограничивает ускорение: если p > T ₁ / T _∞ , то: ^[9]
  $${\displaystyle {\frac {T_{1}}{T_{p}}}\leq {\frac {T_{1}}{T_{\infty }}}<p.}$$
• Расслабленность равна T ₁ / ( pT _∞ ) . Медленность меньше единицы означает (по закону диапазона), что идеальное линейное ускорение невозможно на p процессорах. ^[9]

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

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

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

или, менее точно, ^[6]

${\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 ₁ вместе обеспечивают разумные ограничения на время вычислений. ^[2]

Рекомендации

1. Шилоах, Йоси; Вишкин, Узи (1982). « О ( n ²  log  n ) параллельный алгоритм максимального потока». Журнал алгоритмов . 3 (2): 128–146. дои : 10.1016/0196-6774(82)90013-X.
2. Брент, Ричард П. (1 апреля 1974 г.). «Параллельное вычисление общих арифметических выражений». Журнал АКМ . 21 (2): 201–206. CiteSeerX 10.1.1.100.9361 . дои : 10.1145/321812.321815. ISSN  0004-5411. S2CID  16416106. 
3. JaJa, Джозеф (1992). Введение в параллельные алгоритмы. Аддисон-Уэсли. ISBN 978-0-201-54856-3.
4. Келлер, Йорг; Кесслер, Кристоф В.; Траефф, Джеспер Л. (2001). Практическое программирование PRAM. Уайли-Интерсайенс. ISBN 978-0-471-35351-5.
5. Вишкин, Узи (2009). Параллельное мышление: некоторые базовые алгоритмы и методы параллельного анализа данных, 104 страницы (PDF) . Конспекты курсов по параллельным алгоритмам, преподаваемых с 1992 года в Университете Мэриленда, Колледж-Парке, Тель-Авивском университете и Технионе.
6. Казанова, Анри; Легран, Арно; Роберт, Ив (2008). Параллельные алгоритмы . ЦРК Пресс. п. 10. CiteSeerX 10.1.1.466.8142 . 
7. Белллох, Гай (1996). «Программирование параллельных алгоритмов» (PDF) . Коммуникации АКМ . 39 (3): 85–97. CiteSeerX 10.1.1.141.5884 . дои : 10.1145/227234.227246. S2CID  12118850. 
8. Майкл МакКул; Джеймс Рейндерс; Арч Робисон (2013). Структурированное параллельное программирование: шаблоны для эффективных вычислений . Эльзевир. стр. 4–5.
9. Кормен, Томас Х .; Лейзерсон, Чарльз Э .; Ривест, Рональд Л .; Штейн, Клиффорд (2009) [1990]. Введение в алгоритмы (3-е изд.). MIT Press и McGraw-Hill. стр. 779–784. ISBN 0-262-03384-4.
10. Густавсон, Джон Л. (2011). «Теорема Брента». Энциклопедия параллельных вычислений . стр. 182–185. дои : 10.1007/978-0-387-09766-4_80. ISBN 978-0-387-09765-7.