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

Некоторые алгоритмы достаточно просто поддаются разбиению на независимо выполняемые фрагменты. Например, распределение работы по проверке всех чисел от 1 до 100000 на предмет того, какие из них являются простыми , может быть выполнено путём назначения каждому доступному процессору некоторого подмножества чисел с последующим объединением полученных множеств простых чисел (похожим образом реализован, например, проект GIMPS ).

С другой стороны, большинство известных алгоритмов вычисления значения числа пи ${\displaystyle \left(\pi \right)}$ не допускают разбиения на параллельно выполняемые части, так как требуют результата предыдущей итерации выполнения алгоритма. Итеративные численные методы , такие как, например, метод Ньютона или задача трёх тел , также являются сугубо последовательными алгоритмами. Некоторые примеры рекурсивных алгоритмов достаточно сложно поддаются распараллеливанию. Одним из примеров является поиск в глубину на графах .

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

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

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

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

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

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

См. также

• Искусственная нейронная сеть
• Параллельные вычислительные системы

Ссылки

web-архивы