Jump to content

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

(Перенаправлено из Анализа алгоритмов PRAM )

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

Так называемая структура рабочего времени (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]

  1. ^ Шилоах, Иосия; Вишкин, Узи (1982). «Я О ( н 2 log n ) параллельный алгоритм максимального потока». Журнал алгоритмов . 3 (2): 128–146. doi : 10.1016/0196-6774(82)90013-X .
  2. ^ Перейти обратно: а б Брент, Ричард П. (1 апреля 1974 г.). «Параллельное вычисление общих арифметических выражений». Журнал АКМ . 21 (2): 201–206. CiteSeerX   10.1.1.100.9361 . дои : 10.1145/321812.321815 . ISSN   0004-5411 . S2CID   16416106 .
  3. ^ ДжаДжа, Джозеф (1992). Введение в параллельные алгоритмы . Аддисон-Уэсли. ISBN  978-0-201-54856-3 .
  4. ^ Келлер, Йорг; Кесслер, Кристоф В.; Траефф, Джеспер Л. (2001). Практическое программирование PRAM . Уайли-Интерсайенс. ISBN  978-0-471-35351-5 .
  5. ^ Вишкин, Узи (2009). Параллельное мышление: некоторые базовые алгоритмы и методы параллельного анализа данных, 104 страницы (PDF) . Конспекты курсов по параллельным алгоритмам, преподаваемых с 1992 года в Университете Мэриленда, Колледж-Парке, Тель-Авивском университете и Технионе.
  6. ^ Перейти обратно: а б с д и ж Казанова, Анри; Легран, Арно; Роберт, Ив (2008). Параллельные алгоритмы . ЦРК Пресс. п. 10. CiteSeerX   10.1.1.466.8142 .
  7. ^ Беллох, Гай (1996). «Программирование параллельных алгоритмов» (PDF) . Коммуникации АКМ . 39 (3): 85–97. CiteSeerX   10.1.1.141.5884 . дои : 10.1145/227234.227246 . S2CID   12118850 .
  8. ^ Майкл МакКул; Джеймс Рейндерс; Арч Робисон (2013). Структурированное параллельное программирование: шаблоны для эффективных вычислений . Эльзевир. стр. 4–5.
  9. ^ Перейти обратно: а б с д и ж Кормен, Томас Х .; Лейзерсон, Чарльз Э .; Ривест, Рональд Л .; Штейн, Клиффорд (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 .
Arc.Ask3.Ru: конец переведенного документа.
Arc.Ask3.Ru
Номер скриншота №: 618edd3b0fc66b59e3e7573b5417c60e__1721917080
URL1:https://arc.ask3.ru/arc/aa/61/0e/618edd3b0fc66b59e3e7573b5417c60e.html
Заголовок, (Title) документа по адресу, URL1:
Analysis of parallel algorithms - Wikipedia
Данный printscreen веб страницы (снимок веб страницы, скриншот веб страницы), визуально-программная копия документа расположенного по адресу URL1 и сохраненная в файл, имеет: квалифицированную, усовершенствованную (подтверждены: метки времени, валидность сертификата), открепленную ЭЦП (приложена к данному файлу), что может быть использовано для подтверждения содержания и факта существования документа в этот момент времени. Права на данный скриншот принадлежат администрации Ask3.ru, использование в качестве доказательства только с письменного разрешения правообладателя скриншота. Администрация Ask3.ru не несет ответственности за информацию размещенную на данном скриншоте. Права на прочие зарегистрированные элементы любого права, изображенные на снимках принадлежат их владельцам. Качество перевода предоставляется как есть. Любые претензии, иски не могут быть предъявлены. Если вы не согласны с любым пунктом перечисленным выше, вы не можете использовать данный сайт и информация размещенную на нем (сайте/странице), немедленно покиньте данный сайт. В случае нарушения любого пункта перечисленного выше, штраф 55! (Пятьдесят пять факториал, Денежную единицу (имеющую самостоятельную стоимость) можете выбрать самостоятельно, выплаичвается товарами в течение 7 дней с момента нарушения.)