ДВА ПОДХОДА К РАСПАРАЛЛЕЛИВАНИЮ ВЫЧИСЛЕНИЙ -ПАРАЛЛЕЛИЗМ ДАННЫХ И ПАРАЛЛЕЛИЗМ ЗАДАЧ

В настоящее время существуют два основных подхода к рас­параллеливанию вычислений. Это параллелизм данных и парал­лелизм задач. В англоязычной литературе соответствующие тер­мины data parallel и message passing [3]. В основе обоих подхо­дов лежит распределение вычислительной работы по доступ­ным пользователю процессорам параллельного компьютера. При этом приходится решать разнообразные проблемы. Прежде все­го это достаточно равномерная загрузка процессоров, так как если основная вычислительная работа будет ложиться на один из процессоров, мы приходим к случаю обычных последова­тельных вычислений и никакого выигрыша за счет распаралле­ливания задачи не будет. Сбалансированная работа процессоров - это первая проблема, которую следует решать при организа­ции параллельных вычислений. Другая и не менее важная про­блема - скорость обмена информацией между процессорами. Если вычисления выполняются на высокопроизводительных процессорах, загрузка которых достаточно равномерна, но ско­рость обмена данными низкая, основная часть времени будет тратиться впустую на ожидание информации, необходимой для дальнейшей работы данного процессора. Рассматриваемые спо­собы программирования различаются методами решения этих двух проблем. Разберем их более подробно.

1. Параллелизм данных. Основная идея подхода, основанно­го на параллелизме данных, заключается в том, что одна опера­ция выполняется сразу над всеми элементами массива данных. Различные фрагменты такого массива обрабатываются на вектор­ном процессоре или на разных процессорах параллельной систе­мы. Распределением данных между процессорами занимается специальная программа. Векторизация или распараллеливание в этом случае чаще всего выполняется уже на этапе компиляции -перевода исходного текста программы в машинные коды. Роль программиста в этом случае обычно сводится к заданию опций векторной или параллельной оптимизации компилятору, дирек­тив параллельной компиляции, использованию специализирован­ных языков для параллельных вычислений. Наиболее распрост­раненными языками для параллельных вычислений являются высокопроизводительный ФОРТРАН (High Performance FORTRAN) и параллельные версии языка С (например, С*).

Более детальное описание рассматриваемого подхода по­зволяет выделить следующие его характерные особенности:

■ Обработкой данных управляет одна программа;

■ Пространство имен является глобальным, то есть для про­граммиста существует одна единственная память, а детали струк­туры данных, доступа к памяти и межпроцессорного обмена данными от него скрыты;

■ Слабая синхронизация вычислений на параллельных процессорах, то есть выполнение команд на разных процессо­рах происходит, как правило, независимо и только лишь иногда производится согласование выполнения циклов или других про­граммных конструкций - их синхронизация. Каждый процес­сор выполняет один и тот же фрагмент программы, но нет га­рантии, что в заданный момент времени на всех процессорах выполняется одна и та же машинная команда;

■ Параллельные операции над элементами массива выпол­няются одновременно на всех доступных данной программе процессорах.

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

Подход, основанный на параллелизме данных, базируется на использовании при разработке программ базового набора операций: операции управления данными; операции над масси­вами в целом и их фрагментами; условные операции; операции приведения; операции сдвига; операции сканирования; опера­ции, связанные с пересылкой данных.

Рассмотрим подробнее эти базовые наборы операций.

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

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

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

Операции приведения. Операции приведения применяются ко всем элементам массива (или его сечения), а результатом их является одно единственное значение, например, сумма элемен­тов массива или максимальное значение его элементов.

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

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

Операции пересылки данных. Это, например, операции пе­ресылки данных между массивами разной формы (т.е. имею­щими разную размерность и разную протяженность по каждо­му измерению) и некоторые другие.

При программировании на основе параллелизма данных час­то используются специализированные языки - CM FORTRAN, C*, FORTRAN+, MPP FORTRAN, Vienna FORTRAN, H. P. FORTRAN (основанный на языке программирования FORTRAN 90), что свя­зано с наличием в последнем удобных операций над массивами).

2. Параллелизм задач. Стиль программирования, основан­ный на параллелизме задач, подразумевает, что вычислительная задача разбивается на несколько относительно самостоятельных подзадач и каждый процессор загружается своей собственной подзадачей. Компьютер при этом представляет собой MIMD-машину. Для каждой подзадачи пишется своя собственная про­грамма на обычном языке программирования, обычно это Фор­тран или С. Чем больше подзадач, тем большее число процессо­ров можно использовать, тем большей эффективности можно добиться. Важно то, что все эти программы должны обмени­ваться результатами своей работы, практически такой обмен осуществляется вызовом процедур специализированной библио­теки. Программист при этом может контролировать распреде­ление данных между процессорами и подзадачами и обмен дан­ными. Очевидно, что в этом случае требуется определенная ра­бота для того, чтобы обеспечить эффективное совместное вы­полнение различных программ. По сравнению с подходом, ос­нованном на параллелизме данных, этот подход более трудоем­кий, поскольку с ним связаны следующие проблемы:

• повышенная трудоемкость разработки программы и ее отладки;

• на программиста ложится вся ответственность за равно­мерную загрузку процессоров параллельного компьютера;

• программисту приходится минимизировать обмен данны­ми между задачами, т.к. пересылка данных - наиболее «время-емкий» процесс;

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

Привлекательными особенностями данного подхода явля­ются большая гибкость и большая свобода, предоставляемая программисту в разработке программы, эффективно использу­ющей ресурсы параллельного компьютера и, как следствие, воз­можность достижения максимального быстродействия. Приме­рами специализированных библиотек являются библиотеки MPI (Message Passing Interface), PVM (Parallel Virtual Machines). Эти библиотеки являются свободно распространяемыми и существу­ют в исходных кодах.