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

В информатике , в параллельном алгоритме , в отличие от традиционного последовательного алгоритма , является алгоритм , который может сделать несколько операций в определенный момент времени. В информатике было традицией описывать последовательные алгоритмы в абстрактных моделях машин, часто известной как машина с произвольным доступом . Точно так же многие исследователи информатики использовали так называемую параллельную машину с произвольным доступом (PRAM) в качестве параллельной абстрактной машины (с разделяемой памятью). [1] [2]

Многие параллельные алгоритмы выполняются одновременно - хотя в целом параллельные алгоритмы представляют собой отдельную концепцию - и, таким образом, эти концепции часто смешиваются, причем какой аспект алгоритма является параллельным, а какой - параллельным, четко не различается. Кроме того, непараллельные, непараллельные алгоритмы часто называют « последовательными алгоритмами », в отличие от параллельных алгоритмов.

Возможность распараллеливания [ править ]

См. Также: Анализ параллельных алгоритмов.

Степень распараллеливания алгоритмов значительно различается: от легко распараллеливаемых до полностью непараллелизируемых. Кроме того, данная проблема может включать различные алгоритмы, которые могут быть более или менее распараллеливаемыми.

Некоторые проблемы таким образом легко разделить на части - их называют слишком параллельными проблемами . Примеры включают множество алгоритмов для решения кубиков Рубика и поиска значений, которые приводят к заданному хешу . [ необходима цитата ]

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

Мотивация [ править ]

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

Проблемы [ править ]

Связь [ править ]

Стоимость или сложность последовательных алгоритмов оценивается с точки зрения занимаемого ими пространства (память) и времени (циклы процессора). Параллельным алгоритмам необходимо оптимизировать еще один ресурс - связь между разными процессорами. Есть два способа связи между параллельными процессорами: общая память или передача сообщений.

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

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

Если накладные расходы на связь дополнительных процессоров перевешивают выгоду от добавления еще одного процессора, возникает параллельное замедление .

Балансировка нагрузки [ править ]

Основная статья: Балансировка нагрузки (вычисления)

Еще одна проблема с параллельными алгоритмами заключается в том, чтобы обеспечить их надлежащую балансировку нагрузки , гарантируя, что нагрузка (общая работа) сбалансирована, а не размер входных данных. Например, проверку простоты всех чисел от одного до ста тысяч легко разделить между процессорами; однако, если числа просто разделить поровну (1–1 000, 1 001–2 000 и т. д.), объем работы будет несбалансированным, так как меньшие числа легче обрабатывать с помощью этого алгоритма (легче проверить на простоту) и таким образом, у некоторых процессоров будет больше работы, чем у других, которые будут бездействовать до завершения загрузки загруженных процессоров.

Распределенные алгоритмы [ править ]

Основная статья: Распределенный алгоритм

Подтип параллельных алгоритмов, распределенные алгоритмы - это алгоритмы, предназначенные для работы в кластерных вычислительных средах и распределенных вычислительных средах, где необходимо решить дополнительные проблемы, выходящие за рамки «классических» параллельных алгоритмов.

См. Также [ править ]

  • Многоагентная система (MAS)
  • Параллельные алгоритмы умножения матриц
  • Параллельные алгоритмы для минимальных остовных деревьев
  • Параллельные вычисления
  • Парареальный

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

  1. ^ Blelloch, Guy E .; Мэггс, Брюс М. «Параллельные алгоритмы» (PDF) . США: Школа компьютерных наук Университета Карнеги-Меллона . Проверено 27 июля 2015 . Цитировать журнал требует |journal=( помощь )
  2. ^ Vishkin Узи (2009). «Параллельное мышление: некоторые основные алгоритмы и методы параллельной обработки данных, 104 страницы» (PDF) . Классные заметки по курсам по параллельным алгоритмам, которые читаются с 1992 года в Мэрилендском университете, Колледж-Парке, Тель-Авивском университете и Технионе. Цитировать журнал требует |journal=( помощь )
  3. ^ Мегсон GM; Чэнь Сиань (4 января 1997 г.). Автоматическое распараллеливание для класса регулярных вычислений . World Scientific. ISBN 978-981-4498-41-8.

Внешние ссылки [ править ]

  • Страница "Проектирование и создание параллельных программ" в Аргоннских национальных лабораториях США