Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску

Обзор [ править ]

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

Фон [ править ]

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

Определения [ править ]

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

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

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

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

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

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

. [9]

  • Вялость является Т 1 / ( рТ ∞ ) . Задержка меньше единицы означает (по закону диапазона), что идеальное линейное ускорение невозможно на процессорах p . [9]

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

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

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

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

.

показывающий, что размах (глубина) T ∞ и работа T 1 вместе обеспечивают разумные границы времени вычисления. [2]

Ссылки [ править ]

  1. ^ Шилоах, Йоси; Вишкин, Узи (1982). « Параллельный алгоритм максимального потока O ( n 2  log  n )». Журнал алгоритмов . 3 (2): 128–146. DOI : 10.1016 / 0196-6774 (82) 90013-X .
  2. ^ a b Брент, Ричард П. (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 . Wiley-Interscience. ISBN 978-0-471-35351-5.
  5. ^ Вишкин, Узи (2009). Параллельное мышление: некоторые основные алгоритмы и методы параллельной обработки данных, 104 страницы (PDF) . Классные заметки по курсам по параллельным алгоритмам, которые читаются с 1992 года в Мэрилендском университете, Колледж-Парке, Тель-Авивском университете и Технионе.
  6. ^ a b c d e f Казанова, Анри; Легран, Арно; Роберт, Ив (2008). Параллельные алгоритмы . CRC Press. п. 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). Структурированное параллельное программирование: шаблоны для эффективных вычислений . Эльзевир. С. 4–5.
  9. ^ a b c d e е Кормен, Томас Х .; Лейзерсон, Чарльз Э .; Ривест, Рональд Л .; Стейн, Клиффорд (2009) [1990]. Введение в алгоритмы (3-е изд.). MIT Press и McGraw-Hill. С. 779–784. ISBN 0-262-03384-4.
  10. ^ Густафсон, Джон Л. (2011). «Теорема Брента». Энциклопедия параллельных вычислений . С. 182–185. DOI : 10.1007 / 978-0-387-09766-4_80 . ISBN 978-0-387-09765-7.