ЧАСТЬ II. Языки для параллельного программирования, основанные на Фортране
5. Введение. Подходы к реализации параллельности
Появление суперкомпьютеров с параллельной архитектурой, как за рубежом, так и в нашей стране (см., например, [25-27]), приводит к необходимости разработки эффективных и удобных для программиста средств, обеспечивающих возможность реализовать параллельность, которую допускает выбранный им алгоритм.
Достаточно полный обзор и анализ зарубежных и отечественных систем для высокопроизводительных ЭВМ по состоянию на 1990 год содержится в работе [28]. В работах [29-31] анализируются различные аспекты параллельного программирования. В последующие годы это направление исследований развивалось очень интенсивно.
Некоторые виды распараллеливания могут быть выполнены компилятором автоматически. Проблемам автоматического распараллеливания последовательных программ посвящено большое количество исследований как за рубежом (см., например, [32]), так и в нашей стране (проект РФФИ №97-01-00977, [33]). Описание некоторых зарубежных систем автоматического распараллеливания (наряду с другой весьма полезной информацией) можно найти на сайте http://www.parallel.ru/. В решении этой проблемы имеются определенные результаты, однако автоматическое распараллеливание остается весьма сложной проблемой, а в некоторых случаях решить ее на статическом уровне невозможно.
Разработаны и продолжают разрабатываться как специальные языки для параллельного программирования, так и расширения для традиционных языков в т.ч. и для современного Фортрана [31].
Очевидно, что для обеспечения переносимости с одной платформы на другую необходима стандартизация и унификация таких средств. Унификация средств распараллеливания в языках высокого уровня - довольно сложная проблема. Трудность заключается в том, что имеется большое разнообразие архитектурных решений, позволяющих использовать возможности распараллеливания. Тем не менее в настоящее время уже разработаны системы, включающие средства, которые стали фактическими стандартами для параллельных вычислительных систем различной архитектуры (см. 6-8). Эти средства реализованы для многих параллельных компьютеров.
Рассмотренные в первой части обзора стандарты Фортрана, хотя и содержат некоторые средства поддержки параллельности, не имеют специальных средств, ориентированных на многопроцессорные системы. Однако разработанные на базе этих стандартов параллельные языки существенно используют новые возможности Фортрана 90/95 (динамические и размещаемые массивы, указатели, структуры, модули, явный интерфейс, определяемые пользователем операции, большое число новых встроенных процедур и др.).
Во многих системах параллельность реализуется с помощью специальной библиотеки, содержащей подпрограммы поддержки параллельности; программа на Фортране для таких машин должна содержать обращения к подпрограммам этой библиотеки. Библиотечный подход имеет как преимущества, так и недостатки.
Преимуществом использования библиотек является то, что исходный язык и компилятор остаются неизменными. В то же время использование библиотек менее удобно для разработчиков прикладных программ, чем использование языковых расширений, так как список параметров обычно довольно громоздкий и не соответствует программированию на языке высокого уровня. Так как исходная программа содержит только обращения к библиотечным подпрограммам, то компилятор не может выполнить некоторые виды оптимизации. Кроме того, в некоторых случаях могут быть дополнительные накладные расходы на обращения к подпрограммам библиотек.
Для разработки прикладных программ более удобным и более естественным по сравнению с библиотечными средствами, нам представляется подход, основанный на введении расширений непосредственно в язык. Помимо удобства, этот подход позволяет компилятору выполнить некоторые дополнительные виды оптимизации.
При разработке языковых расширений обычно возникают две основные проблемы:
выбор специальных средств для поддержки параллельности;
отображение выбранных средств в конкретную языковую среду.
Сложность и важность первой проблемы обычно не вызывает сомнений, однако и вторая проблема (часто недооцениваемая) весьма нетривиальна, т.к. при внесении расширений необходимо учесть все многообразие уже существующих языковых средств и все тонкости языка.
При разработке языковых средств для поддержки параллельности имеется две основные стратегии:
создание новых языковых конструкций, или
разработка специальных директив, которые позволяют пользователю специфицировать некоторые виды параллельности; такие директивы обычно оформляются в виде комментариев и переводятся препроцессором в операторы Фортрана с вызовами подпрограмм, которые и реализуют параллельную обработку.
Директивы-комментарии позволяют программисту использовать один вариант исходной программы и для последовательного, и для параллельного выполнения, поскольку компилятор, ориентированный на последовательное выполнение, будет игнорировать такие комментарии.
Ниже рассматриваются следующие модели параллельных вычислений, для которых разработаны языковые средства:
модель, ориентированная на архитектуру с распределенной памятью (см. 6);
модель, ориентированная на архитектуру с общей памятью (см. 7);
модель, ориентированная на разбиение данных (см. 8).
Cредства, ориентированные на архитектуру с векторными операциями, были рассмотрены в первой части данного обзора (см. 3.5. и 3.11.).
6. Средства поддержки параллельности для многопроцессорных систем с распределенной памятью
6.1 Общие сведения
Система с распределенной памятью (distributed memory) обычно состоит из некоторого количества вычислительных узлов, соединенных коммуникационной сетью. Каждый узел имеет только локальную память. Такая архитектура обеспечивает независимое выполнение различных частей параллельной программы на выделенных процессорных узлах. Обмен информацией между различными частями программы осуществляется посредством посылки и приема сообщений по межпроцессорной сети.
Программы для систем с распределенной памятью обычно используют механизм задач (процессов) и передачи сообщений (обмен данными). Исходная программа разбивается на задачи (подзадачи), которые могут выполняться параллельно на разных процессорных узлах, и связь между задачами осуществляется с помощью передачи сообщений. В основе такого подхода лежит фундаментальная модель Хоара [34].
Очевидно, что не все программы позволяют эффективно использовать распределенные системы. Так как обмены сообщениями требуют затрат времени для своего выполнения, важно, чтобы время, необходимое для обмена сообщениями, не доминировало над временем выполнения программы. Распределенные системы целесообразнее использовать для тех вычислительных задач, которые могут быть разбиты на такие слабосвязанные подзадачи, для которых время выполнения существенно больше, чем время обмена между ними.
Имеются разные подходы как к выбору конкретных средств реализации механизма задач и передачи сообщений, так и отображению этих средств в языке. В большинстве систем (PVM, MPI, EXPRESS, P4, PARMACS и др.) механизм задач реализуется с помощью библиотечных вызовов [35-39].
6.2 Система MPI
Из сиcтем, ориентированных на архитектуру с распределенной памятью и представляющих собой набор библиотечных интерфейсов, наибольшее распространение получили MPI и PVM. Система MPI (Message Passing Interface) [37] фактически является международным стандартом, в ней обобщен опыт использования подобных систем, который получил дальнейшее развитие.
MPI включает большой набор средств, среди которых операции передачи сообщений от одного источника (процесса) к другому. Каждому из предусмотренных (по способу синхронизации) видов передачи сообщений соответствует своя операция; необходимая для выполнения операции информация эадается с помощью параметров процедур. Имеется возможность одновременного выполнения вычислений и коммуникаций. Предусмотрены коллективные операции, которые включают как широковещательную передачу сообщений, так и функции редукции. Имеются средства, позволяющие пользователю специфицировать топологию процессов.
Поддерживаются все типы данных, имеющиеся в Фортране и С, имеются и собственные типы данных. Кроме того, для предотвращения коллизии с правилами типов языков верхнего уровня в MPI предусмотрены системные (так называемые "скрытые") объекты, внутреннее представление которых скрыто от пользователя. Предусмотрена возможность конструирования производных типов (структур), которые обеспечивают возможность с помощью одного вызова передать объекты данных разных типов, передать данные, не расположенные в непрерывной области памяти или передать секции массивов.
Для адресации используются группы процессов и коммуникаторы. Коммуникаторы и контексты обеспечивают возможность делить общее коммуникационное пространство на отдельные замкнутые области.
Дальнейшее развитие эти средства получили в системе MPI-2 [39]. MPI не поддерживает объектно-ориентированное программирование, хотя в MPI-2 сделан некоторый шаг в этом направлении. Работа [40] содержит аналитический обзор систем, которые вводят объектную ориентацию в параллельные вычисления с использованием MPI.
В работе [41] описываются средства использования MPI в программах на Фортране 90. Система MPI реализована на многих параллельных компьютерах; система адаптирована для отечественных многопроцессорных вычислительных систем: МВС-100 и МВС-1000 (проекты РФФИ №99-01-00922 и №99-07-90443 [42]).
Подводя некоторые итоги, отметим, что система MPI является хорошим инструментом для распараллеливания широкого класса задач, однако относительно низкий уровень библиотечных средств, чрезмерная детализация приводят к определенным неудобствам при использовании таких систем прикладными специалистами. Подобные системы являются хорошим инструментальным средством для реализации языков более высокого уровня (см. раздел 8).
6.3 Система GNS
В нашей стране разработана и реализована система программирования GNS (включающая Фортран GNS и С GNS; проект РФФИ №96-01-00493) [43-45], которая ориентируется не на библиотечные вызовы, а на введение непосредственно в язык новых конструкций для использования в распределенных системах. Система является развитием предложений в работах [46, 47]. Использование языковых расширений обеспечивает больше удобств для программистов, чем библиотечные вызовы.
Рассмотрим некоторые основные черты этой системы. Прикладная программа может содержать несколько задач, которые могут выполняться параллельно на разных процессорах, при этом число задач не ограничивается числом процессоров.
Каждая задача получает уникальный идентификатор, который служит в качестве адреса отправителя или получателя при передаче сообщения. Задача использует только локальную область памяти без разделения данных с другими задачами.
В системе предусмотрены две модели параллелизма - динамическая и статическая. В статическом варианте все задачи запускаются непосредственно после загрузки. В динамической модели прикладная программа должна содержать одну начальную задачу, в статическом варианте это требование не является обязательным. Динамическая модель предполагает динамическое создание и завершение задач. Выполнение программы начинается с выполнения начальной задачи. Она создает другие задачи, которые, в свою очередь, могут также создавать новые задачи. Динамическое порождение задач позволяет эффективно использовать вычислительные ресурсы и разрабатывать настраиваемые программы.
Обмен информацией между задачами, как в статической, так и в динамической модели, осуществляется с помощью передачи сообщений. Допускается взаимодействие произвольных пар процессоров. Имеются средства широковещательной передачи сообщений. Предусмотрено три способа (режима) передачи сообщений: синхронный, асинхронный и передача без ожидания.
Для реализации указанных возможностей в язык введены новые операторы (SEND, RECEIVE и др.), новый тип данных для идентификации задач (TASKID), конструкция выбора (SELECT MESSAGE - END SELECT), новый вид программных единиц (программные единицы-задачи) и новые стандартные процедуры.
Существенным фактором является возможность указывать в операторах передачи сообщений произвольный список передаваемых данных, аналогичный списку ввода/вывода языка Фортран, что гораздо удобнее, чем средства, имеющиеся в системах, основанных на библиотечном подходе.
Однако реализованный вариант Фортрана GNS ориентирован на устаревший вариант языка - Фортран 77; это вызвано тем, что базовое программное обеспечение системы, для которой первоначально была предназначена эта разработка, не снабжено компиляторами, соответствующими современным стандартам Фортрана.
Новые средства, введенные в Фортран 90/95, позволяют расширить Фортран GNS. В работе [48] (проект РФФИ № 97-01-00361) описываются предложения по дальнейшему развитию Фортрана GNS, которые ориентированы на новые возможности, предоставляемые современными стандартами Фортрана. Новые средства обеспечивают больше удобств для пользователя и более широкие возможности параллельной обработки.