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

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

Фон

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

Определения

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

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

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

Закон о труде . Стоимость всегда равна как минимум работе: $pT p \geq T 1$ . Это следует из того, что $p$ процессоров могут выполнять не более $p$ операций параллельно. ^[6]^[9]
Спанское право . Конечное число $p$ процессоров не может превзойти бесконечное число, так что $T p \geq T \infty$ . ^[9]

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

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

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

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

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

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

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

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

{\frac {T_{1}}{p}}\leq T_{p}\leq {\frac {T_{1}}{p}}+T_{\infty }

.

показывая, что диапазон (глубина) $T \infty$ и работа $T 1$ вместе обеспечивают разумные ограничения на время вычислений. ^[2]

Ссылки

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

[shiloach-1] Шилоах, Иосия; Вишкин, Узи (1982). «Я О ( н ² log n ) параллельный алгоритм максимального потока». Журнал алгоритмов . 3 (2): 128–146. doi : 10.1016/0196-6774(82)90013-X .

[brent-2] Jump up to: ^а ^б Брент, Ричард П. (1 апреля 1974 г.). «Параллельное вычисление общих арифметических выражений». Журнал АКМ . 21 (2): 201–206. CiteSeerX 10.1.1.100.9361 . дои : 10.1145/321812.321815 . ISSN 0004-5411 . S2CID 16416106 .

[jaja-3] ДжаДжа, Джозеф (1992). Введение в параллельные алгоритмы . Аддисон-Уэсли. ISBN 978-0-201-54856-3 .

[kkt-4] Келлер, Джордж; Кесслер, Кристофер В.; Траефф, Джеспер Л. (2001). Практическое программирование PRAM . Уайли-Интерсайенс. ISBN 978-0-471-35351-5 .

[uv-5] Вишкин, Узи (2009). Параллельное мышление: некоторые базовые алгоритмы и методы параллельного анализа данных, 104 страницы (PDF) . Конспекты курсов по параллельным алгоритмам, преподаваемых с 1992 года в Университете Мэриленда, Колледж-Парке, Тель-Авивском университете и Технионе.

[casanova-6] Jump up to: ^а ^б ^с ^д ^и ^ж Казанова, Анри; Легран, Арно; Роберт, Ив (2008). Параллельные алгоритмы . ЦРК Пресс. п. 10. CiteSeerX 10.1.1.466.8142 .

[cacm-7] Беллох, Гай (1996). «Программирование параллельных алгоритмов» (PDF) . Коммуникации АКМ . 39 (3): 85–97. CiteSeerX 10.1.1.141.5884 . дои : 10.1145/227234.227246 . S2CID 12118850 .

[spp-8] Майкл МакКул; Джеймс Рейндерс; Арч Робисон (2013). Структурированное параллельное программирование: шаблоны для эффективных вычислений . Эльзевир. стр. 4–5.

[clrs-9] Jump up to: ^а ^б ^с ^д ^и ^ж Кормен, Томас Х .; Лейзерсон, Чарльз Э .; Ривест, Рональд Л .; Стоун, Клиффорд (2009) [1990]. Введение в алгоритмы (3-е изд.). MIT Press и McGraw-Hill. стр. 779–784. ISBN 0-262-03384-4 .

[10] Кургалин Сергей; Борзунов, Сергей (2020). Рабочая тетрадь по дискретной математике: сопутствующее руководство по использованию Python . Тексты по информатике (2-е изд.). Чам, Швейцария: Springer Naturel. ISBN 978-3-030-42220-2 .

[11] Густафсон, Джон Л. (2011). «Теорема Брента». Энциклопедия параллельных вычислений . стр. 182–185. дои : 10.1007/978-0-387-09766-4_80 . ISBN 978-0-387-09765-7 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

v т и Параллельные вычисления
Общий	Распределенные вычисления Параллельные вычисления Массивная параллель Облачные вычисления Высокопроизводительные вычисления Многопроцессорность Многоядерный процессор ГПГПУ Компьютерная сеть Систолический массив
Уровни	Кусочек Инструкция Нить Задача Данные Память Петля Трубопровод
Многопоточность	Временной Одновременный (SMT) Одновременное и гетерогенное Спекулятивный (СпМТ) упреждающий Кооператив Кластерная многопоточная обработка (CMT) Аппаратный разведчик
Теория	Модель ПРАМ PEM-модели Анализ параллельных алгоритмов Закон Амдала Закон Густавсона Экономическая эффективность Метрика Карпа – Флатта Замедлять Ускорение
Элементы	Процесс Нить Волокно Окно инструкций Множество
Координация	Многопроцессорность Согласованность памяти Согласованность кэша Аннулирование кэша Барьер Синхронизация Контрольная точка приложения
Программирование	Потоковая обработка Программирование потоков данных Модели Неявный параллелизм Явный параллелизм Параллелизм Неблокирующий алгоритм
Аппаратное обеспечение	Таксономия Флинна СИСД SIMD Обработка массивов (SIMT) Конвейерная обработка Ассоциативная обработка МИСД МИМД Архитектура потока данных Конвейерный процессор Суперскалярный процессор Векторный процессор Мультипроцессор симметричный асимметричный Память общий распределенный распределенный общий ОДИН НУМА ЕСТЬ Массивно-параллельный компьютер Компьютерный кластер Кластер Беовульф Сетевой компьютер Аппаратное ускорение
API	Атеджи ПХ Способствовать росту Часовня HPX Очарование++ Том Коаррей Фортран ДРУГОЙ Дриада С++ AMP Глобальные массивы GPUОткрыть ИМБ OpenMP OpenCL OpenHMPP OpenACC Параллельные расширения НДС pthreads РафтЛиб РПЦм СКП TBB ЗПЛ
Проблемы	Автоматическое распараллеливание Тупик Детерминированный алгоритм Смущающе параллельно Параллельное замедление Состояние гонки Программная блокировка Масштабируемость Голод
Категория: Параллельные вычисления