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

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

Фон

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

Определения

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

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

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

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

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

• Ускорение — это выигрыш в скорости, достигаемый параллельным выполнением по сравнению с последовательным выполнением: S _p = T ₁ / T _p . Когда ускорение равно Ω( p ) для p процессоров (используя нотацию big O ), ускорение линейно, что оптимально в простых моделях вычислений, поскольку закон работы подразумевает, что T ₁ / T _p ≤ p ( суперлинейное ускорение может иметь место на практике из-за эффектов иерархии памяти ). Ситуация T ₁ / T _p = p называется идеальным линейным ускорением. ^[9] Алгоритм, демонстрирующий линейное ускорение, называется масштабируемым . ^[6] Аналитические выражения для ускорения многих важных параллельных алгоритмов представлены в этой книге. ^[10]
• Эффективность – это ускорение на процессор, 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 , ограниченное ^[11]

${\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). « Параллельный алгоритм максимального потока O ( n ²  log  n )». Журнал алгоритмов . 3 (2): 128–146. doi :10.1016/0196-6774(82)90013-X.
2. Брент, Ричард П. (1974-04-01). "Параллельная оценка общих арифметических выражений". Журнал ACM . 21 (2): 201–206. CiteSeerX 10.1.1.100.9361 . doi :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). Thinking in Parallel: Some Basic Data-Parallel Algorithms and Techniques, 104 страницы (PDF) . Заметки о курсах по параллельным алгоритмам, преподаваемых с 1992 года в Мэрилендском университете, Колледж-Парке, Тель-Авивском университете и Технионе.
6. Казанова, Анри; Легран, Арно; Роберт, Ив (2008). Параллельные алгоритмы . ЦРК Пресс. п. 10. CiteSeerX 10.1.1.466.8142 . 
7. Blelloch, Guy (1996). "Программирование параллельных алгоритмов" (PDF) . Сообщения ACM . 39 (3): 85–97. CiteSeerX 10.1.1.141.5884 . doi :10.1145/227234.227246. S2CID  12118850. 
8. Майкл МакКул; Джеймс Рейндерс; Арч Робинсон (2013). Структурированное параллельное программирование: шаблоны для эффективных вычислений . Elsevier. стр. 4–5.
9. Кормен, Томас Х .; Лейзерсон, Чарльз Э .; Ривест, Рональд Л .; Стайн, Клиффорд (2009) [1990]. Введение в алгоритмы (3-е изд.). MIT Press и McGraw-Hill. стр. 779–784. ISBN 0-262-03384-4.
10. Кургалин, Сергей; Борзунов, Сергей (2020). Дискретная математика рабочая тетрадь: сопутствующее руководство с использованием Python . Тексты по информатике (2-е изд.). Cham, Швейцария: Springer Naturel. ISBN 978-3-030-42220-2.
11. Густафсон, Джон Л. (2011). «Теорема Брента». Энциклопедия параллельных вычислений . С. 182–185. doi :10.1007/978-0-387-09766-4_80. ISBN 978-0-387-09765-7.