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

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

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

Обзор

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

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

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

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

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

Ускорение - это выигрыш в скорости за счет параллельного выполнения по сравнению с последовательным выполнением: $S п = Т 1 ∕ Т п$ . Когда ускорение $Ω (п)$ для размера ввода $п$ (с помощью нотация большой O ) ускорение является линейным, что оптимально для простых моделей вычислений, поскольку из закона работы следует, что $Т 1 ∕ Т п \leq п$ (сверхлинейное ускорение может возникнуть на практике из-за иерархия памяти последствия). Ситуация $Т 1 ∕ Т п = п$ называется идеальным линейным ускорением.^[9] Алгоритм, демонстрирующий линейное ускорение, называется масштабируемый.^[6]
Эффективность это ускорение на процессор, $S п ∕ п$ .^[6]
Параллелизм это соотношение $Т 1 ∕ Т \infty$ . Он представляет собой максимально возможное ускорение на любом количестве процессоров. По закону диапазона параллелизм ограничивает ускорение: если $п > Т 1 ∕ Т \infty$ , тогда:

${ displaystyle { frac {T_ {1}} {T_ {p}}} leq { frac {T_ {1}} {T _ { infty}}}$ .^[9]

В расслабленность является $Т 1 ∕ (pT \infty)$ . Слабость меньше единицы означает (по закону диапазона), что идеальное линейное ускорение невозможно на $п$ процессоры.^[9]

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

Анализ параллельных алгоритмов обычно проводится в предположении наличия неограниченного числа процессоров. Это нереально, но не проблема, поскольку любые вычисления, которые могут выполняться параллельно на $N$ процессоры могут выполняться на $п < N$ процессоров, позволяя каждому процессору выполнять несколько единиц работы. Результат называется Закон Брента заявляет, что можно выполнить такое «моделирование» во времени $Т п$ , ограниченный^[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).}

Альтернативное изложение закона границ $Т п$ сверху и снизу

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

.

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

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

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

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

[brent-2] а ^б Брент, Ричард П. (1974-04-01). «Параллельное вычисление общих арифметических выражений». Журнал ACM. 21 (2): 201–206. CiteSeerX 10.1.1.100.9361. Дои:10.1145/321812.321815. ISSN 0004-5411. S2CID 16416106.

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

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

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

[casanova-6] а ^б ^c ^d ^е ^ж Казанова, Анри; Легран, Арно; Роберт, Ив (2008). Параллельные алгоритмы. CRC Press. п. 10. CiteSeerX 10.1.1.466.8142.

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

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

[clrs-9] а ^б ^c ^d ^е ^ж Кормен, Томас Х.; Лейзерсон, Чарльз Э.; Ривест, Рональд Л.; Штейн, Клиффорд (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.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

Параллельные вычисления
Общий	Распределенных вычислений Параллельные вычисления Массивно параллельный Облачные вычисления Высокопроизводительные вычисления Многопроцессорность Многоядерный процессор ГПГПУ Компьютерная сеть Систолический массив
Уровни	Кусочек Инструкция Нить Задача Данные объем памяти Петля Трубопровод
Многопоточность	Временный Одновременный (SMT) Спекулятивный (SpMT) Упреждающий Кооператив Кластерная многопоточность (CMT) Аппаратный разведчик
Теория	PRAM модель Модель PEM Анализ параллельных алгоритмов Закон Амдала Закон Густафсона Эффективность затрат Метрика Карпа – Флатта Замедлять Ускорение
Элементы	Процесс Нить Волокно Окно с инструкциями Структура данных массива
Координация	Многопроцессорность Когерентность памяти Согласованность кеша Аннулирование кеша Барьер Синхронизация Контрольные точки приложения
Программирование	Потоковая обработка Программирование потока данных Модели Неявный параллелизм Явный параллелизм Параллелизм Неблокирующий алгоритм
Аппаратное обеспечение	Таксономия Флинна SISD SIMD SIMT MISD MIMD Архитектура потока данных Конвейерный процессор Суперскалярный процессор Векторный процессор Мультипроцессор симметричный асимметричный объем памяти общий распределен распределенный общий UMA NUMA КОМА Массивно-параллельный компьютер Компьютерный кластер Сетевой компьютер Аппаратное ускорение
API	Ateji PX Способствовать росту Часовня HPX Очарование ++ Силк Coarray Fortran CUDA Дриада C ++ AMP Глобальные массивы GPUOpen MPI OpenMP OpenCL OpenHMPP OpenACC Параллельные расширения PVM Потоки POSIX RaftLib UPC TBB ZPL
Проблемы	Автоматическое распараллеливание Тупик Детерминированный алгоритм Смущающе параллельный Параллельное замедление Состояние гонки Блокировка программного обеспечения Масштабируемость Голодание
Категория: Параллельные вычисления