Анализ параллельных алгоритмов
В информатике анализ параллельных алгоритмов — это процесс определения вычислительной сложности алгоритмов, выполняемых параллельно, — количества времени, памяти или других ресурсов, необходимых для их выполнения. Во многих отношениях анализ параллельных алгоритмов аналогичен анализу последовательных алгоритмов , но, как правило, он более сложен, поскольку необходимо учитывать поведение нескольких взаимодействующих потоков выполнения. Одна из основных целей параллельного анализа — понять, как меняется использование ресурсов параллельным алгоритмом (скорость, пространство и т. д.) при изменении количества процессоров.
Фон
[ редактировать ]Так называемая структура рабочего времени (WT) (иногда называемая глубиной работы или продолжительностью работы) была первоначально представлена Шилоахом и Вишкиным. [1] для концептуализации и описания параллельных алгоритмов. В рамках WT параллельный алгоритм сначала описывается в терминах параллельных раундов. Для каждого раунда описываются операции, которые необходимо выполнить, но некоторые проблемы можно скрыть. Например, не обязательно указывать количество операций в каждом раунде, не нужно упоминать процессоры и не нужно учитывать любую информацию, которая может помочь в распределении процессоров по заданиям. Во-вторых, предоставляется скрытая информация. Включение скрытой информации основано на доказательстве теоремы планирования Брента: [2] что объясняется далее в этой статье. Структура WT полезна, поскольку, хотя она может значительно упростить первоначальное описание параллельного алгоритма, вставка деталей, скрытых в этом первоначальном описании, часто не очень сложна. Например, структура WT была принята в качестве базовой структуры представления в книгах по параллельным алгоритмам (для параллельной машины с произвольным доступом модели PRAM ). [3] и, [4] а также в конспектах занятий . [5] В приведенном ниже обзоре объясняется, как структуру WT можно использовать для анализа более общих параллельных алгоритмов, даже если их описание недоступно в структуре WT.
Определения
[ редактировать ]Предположим, вычисления выполняются на машине с p процессорами. Обозначим через Tp время , прошедшее между началом вычисления и его окончанием. вычислений Анализ времени выполнения фокусируется на следующих понятиях:
- Работа p вычисления, выполняемая процессорами , равна общему числу примитивных операций, выполняемых процессорами. [6] Если не учитывать издержки связи, возникающие при синхронизации процессоров, это время равно времени, используемому для выполнения вычислений на одном процессоре, обозначенному T 1 .
- Глубина зависимостей или диапазон — это длина самой длинной серии операций, которые необходимо выполнять последовательно из-за данных ( критический путь ). Глубину также можно назвать длиной критического пути вычислений. [7] Минимизация глубины/диапазона важна при разработке параллельных алгоритмов, поскольку глубина/диапазон определяет кратчайшее возможное время выполнения. [8] Альтернативно, интервал можно определить как время T ∞ , потраченное на вычисления на идеализированной машине с бесконечным числом процессоров. [9]
- Стоимость . вычислений равна pT p величине Это выражает общее время, затраченное всеми процессорами как на вычисления, так и на ожидание. [6]
Из определений работы, продолжительности и стоимости следует несколько полезных результатов:
- Закон о труде . Стоимость всегда равна как минимум работе: pT p ≥ T 1 . Это следует из того, что p процессоров могут выполнять не более p операций параллельно. [6] [9]
- Спанское право . Конечное число p процессоров не может превзойти бесконечное число, так что T p ≥ T ∞ . [9]
Используя эти определения и законы, можно определить следующие показатели эффективности:
- Ускорение прирост скорости при параллельном выполнении по сравнению с последовательным: Sp — это = T 1 / T p . Когда ускорение равно Ω( p ) для p процессоров (с использованием обозначения большого O ), ускорение является линейным, что является оптимальным в простых моделях вычислений, поскольку закон работы подразумевает, что T 1 / T p ≤ p ( суперлинейное ускорение может происходят на практике из-за эффектов иерархии памяти ). Ситуация T 1 / T p = p называется идеальным линейным ускорением. [9] Алгоритм, демонстрирующий линейное ускорение, называется масштабируемым . [6] В этой книге представлены аналитические выражения для ускорения многих важных параллельных алгоритмов. [10] .
- Эффективность — это ускорение каждого процессора, S p / p . [6]
- Параллельностью называется отношение T 1 / T ∞ . Он представляет собой максимально возможное ускорение на любом количестве процессоров. По закону размаха параллелизм ограничивает ускорение: если p > T 1 / T ∞ , то: [9]
- Расслабленность pT равна T 1 / ( ∞ ) . Медленность меньше единицы означает (по закону диапазона), что идеальное линейное ускорение невозможно на p процессорах. [9]
Выполнение на ограниченном количестве процессоров
[ редактировать ]Анализ параллельных алгоритмов обычно проводится в предположении, что имеется неограниченное количество процессоров. Это нереально, но не проблема, поскольку любые вычисления, которые могут выполняться параллельно на N процессорах, могут выполняться на p < N процессорах, позволяя каждому процессору выполнять несколько единиц работы. Результат, называемый законом Брента, гласит, что такое «моделирование» можно выполнить за время T p , ограниченное [11]
или, менее точно, [6]
Альтернативная формулировка закона ограничивает T p сверху и снизу величиной
- .
показывая, что диапазон (глубина) T ∞ и работа T 1 вместе обеспечивают разумные ограничения на время вычислений. [2]
Ссылки
[ редактировать ]- ^ Шилоах, Иосия; Вишкин, Узи (1982). «Я О ( н 2 log n ) параллельный алгоритм максимального потока». Журнал алгоритмов . 3 (2): 128–146. doi : 10.1016/0196-6774(82)90013-X .
- ^ Перейти обратно: а б Брент, Ричард П. (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 года в Университете Мэриленда, Колледж-Парке, Тель-Авивском университете и Технионе.
- ^ Перейти обратно: а б с д и ж Казанова, Анри; Легран, Арно; Роберт, Ив (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.
- ^ Перейти обратно: а б с д и ж Кормен, Томас Х .; Лейзерсон, Чарльз Э .; Ривест, Рональд Л .; Штейн, Клиффорд (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 .