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