Параллельный алгоритм - Parallel algorithm

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

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

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

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

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

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

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

Мотивация

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

Проблемы

Коммуникация

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

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

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

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

Балансировка нагрузки

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

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

Распределенные алгоритмы

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

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

Смотрите также

использованная литература

внешние ссылки