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