Известно громадное количество последовательных (традиционных) методов и алгоритмов решения задач. «Приспособление» этих методов алгоритмов для их реализации на параллельных вычислительных системах носит название распараллеливание (paralleling). Отметим особую сложность этой задачи для вычислительных систем с распределенной памятью.

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

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

Более строго определим распараллеливание как нахождение параллельного алгоритма решения задачи и реализация этого алгоритма на параллельной вычислительной системе. Подчеркнем, что распараллеливание не обязательно предполагает получение параллельного алгоритма из последовательного алгоритма. Таким образом, мы будем понимать термин «распараллеливание» как синоним термина «синтез параллельного алгоритма».

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

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

Всякий алгоритм имеет две характеристики, по которым можно судить о его качестве: сложность алгоритма (требуемое время на вычисления); численная устойчивость (малая чувствительность к ошибкам в исходных данных и ошибкам округления). Алгоритм называется численно устойчивым, если ошибки округления не превосходят ошибок в исходных данных.

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

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

Мелкозернистый алгоритм позволяет выделить в нем параллельные ветви только малого объема. Напротив, крупнозернистый алгоритм, адекватный MIMD-системам, состоит из независимых или слабо связанных ветвей значительного объема, которые могут обрабатываться параллельно. Крупнозернистый алгоритм часто называют крупноблочным алгоритмом.

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

Параллельные алгоритмы, ориентированные на SIMD-вычислительные системы и MIMD-вычислительные системы, существенно различны.

В данном разделе рассматриваются методы и алгоритмы, ориентированные на MIMD-системы с общей памятью или на MIMD-системы с распределенной памятью.

В задачах можно выделить следующие типы параллелизма:

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

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

Распараллеливание на основе параллелизма данных называется декомпозицией по данным. Рассмотрим простейший пример декомпозиции по данным.

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

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

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

Функциональный параллелизм – это параллелизм групп операций, объединенных по функциональному признаку. Распараллеливание на основе функционального параллелизма называется функциональной декомпозицией. Тривиальным примером функциональной декомпозиции является декомпозиция задачи на три следующих подзадачи: ввод исходных данных, обработка, вывод результатов, визуализация результатов. Параллелизм при этом достигается параллельным выполнением трех указанных подзадач и созданием «конвейера» (последовательного или последовательно параллельного) между ними. Заметим, что каждая из указанных подзадач может обладать параллелизмом данных. Приведем еще один (менее очевидный) пример функциональной декомпозиции. Задачу математического моделирования самолета можно разбить на подзадачи моделирования атмосферы, фюзеляжа самолета, его левого крыла, правого крыла и т.д.

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

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

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

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

Распараллеливание на основе геометрического параллелизма называется декомпозиция области решения. Декомпозиция области решения – один из основных способов получения крупнозернистых алгоритмов и программ.

Отличие геометрического параллелизма от параллелизма по данным состоит в том, что подзадачи обработки каждой из подобластей взаимосвязаны (требуется обмен данными между этими подзадачами).

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

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

Алгоритмическим параллелизмом называется параллелизм, который выявляется путем выделения в данном алгоритме тех фрагментов, которые могут выполняться параллельно (см. рис. 3). Алгоритмический параллелизм редко порождает крупнозернистые параллельные алгоритмы и программы.

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

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

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

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

Отметим значительную общность конвейерного и функционального параллелизма.

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

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

Широко известным частным случаем алгоритмической декомпозиции является реструктуризация данных.

Рассмотрим задачу вычисления произведения =8 вещественных чисел . В простейшем случае параллельное вычисление этого произведения можно организовать в соответствии со следующей ЯПФ (высота ЯПФ , ширина ЯПФ ):

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

Более эффективным алгоритмом решения данной задачи является алгоритм сдваивания, применимый к любой ассоциативной операции (, ):

Ярус 1. Вычисление произведений ; a₃a₄; a₅a₆; a₇a₈;

Ярус 2. Вычисление произведений ; ; (a₅a₆)a₇; (a₅a₆)(a₇a₈);

Ярус 3. Вычисление произведения ; ; ;

Данный алгоритм обеспечивает полную загрузку каждого из 4-х процессоров на всех шагах вычислений. Синим цветом выделены лишние числа.

Утверждение 1. Алгоритм сдваивания для вычисления произведения (или любой другой ассоциативной операции) элементов

обеспечивает решение задачи за (log) на PRAM (см. ниже) с = процессорами.