В информатике параллельный алгоритм , в отличие от традиционного последовательного алгоритма , представляет собой алгоритм , который может выполнять несколько операций за заданное время. В информатике было традицией описывать последовательные алгоритмы в абстрактных моделях машин, часто известных как машины с произвольным доступом . Точно так же многие исследователи информатики использовали так называемую параллельную машину с произвольным доступом (PRAM) в качестве параллельной абстрактной машины (с общей памятью). [1] [2]
Многие параллельные алгоритмы выполняются одновременно – хотя, как правило, параллельные алгоритмы представляют собой отдельную концепцию – и поэтому эти концепции часто объединяются, причем какой аспект алгоритма является параллельным, а какой параллельным, четко не различается. Кроме того, непараллельные и непараллельные алгоритмы часто называют « последовательными алгоритмами », в отличие от параллельных алгоритмов.
Алгоритмы значительно различаются по степени распараллеливаемости: от легко распараллеливаемых до полностью нераспараллеливаемых. Кроме того, данная задача может включать в себя различные алгоритмы, которые могут быть более или менее распараллеливаемыми.
Некоторые проблемы легко разделить таким образом на части — их называют досадно параллельными задачами. Примеры включают множество алгоритмов для решения кубиков Рубика и поиска значений, которые приводят к заданному хешу . [ нужна цитата ]
Некоторые проблемы невозможно разделить на параллельные части, поскольку для эффективного перехода к следующему шагу требуются результаты предыдущего шага.по своей сути серийная проблема. Примеры включают итеративныечисленные методы, такие какметод Ньютона, итеративные решения задачитрёх тели большинство доступных алгоритмов для вычислениячисла Пи(π).[ нужна цитация ]Некоторые последовательные алгоритмы могут быть преобразованы в параллельные алгоритмы с использованиемавтоматического распараллеливания.[3]
Параллельные алгоритмы на отдельных устройствах стали более распространенными с начала 2000-х годов из-за существенных улучшений в многопроцессорных системах и появления многоядерных процессоров. Вплоть до конца 2004 года производительность одноядерных процессоров быстро увеличивалась за счет масштабирования частоты , и поэтому было проще построить компьютер с одним быстрым ядром, чем компьютер со многими более медленными ядрами с одинаковой пропускной способностью , поэтому многоядерные системы имели более ограниченные возможности. использовать. Однако с 2004 года масштабирование частоты зашло в тупик, и, таким образом, многоядерные системы стали более распространенными, что сделало параллельные алгоритмы более общими.
Стоимость или сложность последовательных алгоритмов оценивается с точки зрения занимаемого ими пространства (памяти) и времени (циклов процессора). Параллельным алгоритмам необходимо оптимизировать еще один ресурс — связь между разными процессорами. Существует два способа взаимодействия параллельных процессоров: общая память или передача сообщений.
Обработка в общей памяти требует дополнительной блокировки данных, требует дополнительных циклов процессора и шины, а также сериализует некоторую часть алгоритма.
При обработке передачи сообщений используются каналы и ящики сообщений, но такая связь увеличивает нагрузку на передачу по шине, дополнительную потребность в памяти для очередей и ящиков сообщений, а также задержку сообщений. В конструкциях параллельных процессоров используются специальные шины, такие как перекрестная шина , поэтому накладные расходы на связь будут небольшими, но объем трафика определяется параллельным алгоритмом.
Если накладные расходы на связь дополнительных процессоров перевешивают выгоду от добавления еще одного процессора, происходит параллельное замедление .
Другая проблема с параллельными алгоритмами заключается в том, чтобы гарантировать, что они надлежащим образом сбалансированы по нагрузке , гарантируя, что нагрузка (общая работа) сбалансирована, а не сбалансирован размер входных данных. Например, проверку всех чисел от единицы до ста тысяч на простоту легко разделить между процессорами; однако если числа просто разделить поровну (1–1000, 1001–2000 и т. д.), объем работы будет несбалансированным, поскольку меньшие числа легче обрабатывать этим алгоритмом (проще проверить на простоту), и таким образом, некоторым процессорам будет выполняться больше работы, чем другим, которые будут простаивать до тех пор, пока загруженные процессоры не завершат работу.
Подтип параллельных алгоритмов, распределенные алгоритмы , представляют собой алгоритмы, предназначенные для работы в кластерных вычислениях и средах распределенных вычислений , где необходимо решать дополнительные проблемы, выходящие за рамки «классических» параллельных алгоритмов.