В последние годы все большее распространение получают параллельные ЭВМ различной архитектуры. Для их эффективного использования программисту нужны удобные средства, позволяющие реализовать параллельность, которую допускает выбранный им алгоритм. Некоторые виды распараллеливания могут быть выполнены компилятором автоматически; в ряде стран, включая и нашу страну, проводятся исследования и уже имеются определенные результаты в этой области, однако автоматическое распараллеливание остается весьма сложной проблемой. В некоторых случаях решить ее на статическом уровне невозможно. Поэтому появилась необходимость ввести в широко используемые последовательные языки средства, поддерживающие параллельную обработку.
Введение
В статье анализируются различные методологии использования Фортрана и Си для параллельных вычислительных систем различной архитектуры. Существуют средства параллельного программирования и в других языках: Ада, Параллельный Паскаль, Модула-2, Лисп (СМ LISP) и т.п. Имеются специализированные языки программирования, ориентированные на параллельную обработку. Наибольшей популярностью среди них пользуется язык ОККАМ [1]. Хотя ОККАМ предоставляет пользователю большой арсенал средств, все же приверженность пользователей к традиционным языкам приводит к необходимости разрабатывать средства распараллеливания для систем программирования на базе более распространенных языков.
Наш выбор объясняется тем, что Фортран наиболее употребителен при решении научно-технических задач вычислительного характера и занимает лидирующее положение при программировании для параллельных ЭВМ; в последние годы все большую популярность приобретает язык Си. Обсуждаемые здесь проблемы применимы не только к Фортрану и Си, но и к другим языкам программирования.
Виды параллельной архитектуры
Архитектура параллельных вычислительных систем весьма разнообразна. Методология программирования для различных видов архитектуры отличается друг от друга и средства, вводимые в язык, обычно тоже различны.
В данном обзоре будут рассматриваться ситемы программирования для архитектур следующих видов: машины, содержащие аппаратные средства обработки массивов (векторные процессоры), и мультипроцессорные системы.
Для мультипроцессорных систем рассматривается:
- архитектура с общей памятью, характеризующаяся тем, что несколько физических процессоров могут совместно использовать общую область памяти;
- архитектура с распределенной памятью, характеризующаяся тем, что в системе имеется множество процессоров со своей локальной памятью, которые связываются между,собой различными способами.
Разные подходы к реализации параллельности
Использование библиотек
На первом этапе, при появлении новой архитектуры, параллельность часто реализуется с помощью специальной библиотеки, содержащей подпрограммы поддержки параллельности; программа на Фортране или Си должна содержать обращения к подпрограммам библиотеки [2].
Преимуществом использования библиотек является неизменность исходного языка и компилятора. Это позволяет разработчикам относительно легко и быстро вводить новые средства и экспериментировать с целью выбора наиболее удачного набора средств из возможных альтернатив. В дальнейшем наиболее оправдавшие себя средства могут быть включены в языковые расширения.
Использование библиотек менее удобно для программиста, чем использование языковых расширений, так как список параметров обычно довольно громоздок и не соответствует программированию на языке высокого уровня. Так как исходная программа содержит только обращения к библиотечным подпрограммам, то компилятор не может выполнить некоторые виды оптимизации. Недостатком этого подхода является также то, что библиотеки обычно не унифицированы, и, кроме того, возможны дополнительные накладные расходы на обращения к подпрограммам библиотек.
Макрорасширения
В ряде реализаций используются макрорасширения Фортрана и Си или специальные директивы компилятору [2,3]. Директивымакрорасширения позволяют пользователю специфицировать некоторые виды параллельности. Макрорасширения либо оформляются в виде специальных комментариев, либо записываются заглавными буквами, а основной текст - строчными. Директивы-макрорасширения обычно переводятся препроцессором в операторы Фортрана или Си с вызовами специальных подпрограмм, которые и реализуют параллельную обработку. Пример подобного пакета макрорасширений - пакет, разработанный в Аргоннской национальной лаборатории для языков Си и Фортран [4].
Описанный подход, как и подход, основанный на использовании библиотек, не очень удобен при программировании на языке высокого уровня. Кроме того, использование макрорасширений добавляет промежуточный код, что осложняет отладку программ.
Расширения в языке
Более удобным и более естественным для программиста представляется подход, основанный на введении расширений непосредственно в язык. Помимо удобства, этот подход позволяет компилятору выполнить некоторые дополнительные виды оптимизации.
Разработчики расширений для уже существующих языков программирования обычно сталкиваются с двумя проблемами:
- выбор новых средств для решения тех или иных задач, в частности, для параллельности;
- отображение выбранных средств в конкретную языковую среду.
Сложность и важность первой проблемы обычно не вызывает сомнений, однако и вторая проблема (часто недооцениваемая) весьма нетривиальна, так как при внесении расширений необходимо учесть все многообразие уже существующих языковых средств и все тонкости языка. О нетривиальности этой проблемы свидетельствует многолетний тернистый путь большого коллектива специалистов многих стран, разработавших Фортран 90.
В отсутствие унифицированных языковых средств, фирмы-изготовители обычно разрабатывают собственные средства и включают их в компиляторы. Эти средства часто ориентированы на конкретную архитектуру. Совершенно очевидно, что многообразие подходов делает программы немобильными, затрудняет перенос программ с одной ЭВМ на другую и существенно осложняет обмен прикладным программным обеспечением.
Унификация средств распараллеливания в языках высокого уровня - довольно сложная проблема. Трудность заключается в большом разнообразии архитектурных решений, позволяющих использовать возможности распараллеливания, которые, естественно, влияют на возможный выбор языковых средств.
В настоящее время многие специалисты уже видят возможность и необходимость стандартизации в языках средств спецификации распараллеливания и уже разрабатываются такие проекты. Первый шаг в этом направлении был сделан в новом международном стандарте языка Фортран - Фортране 90 [5,6,7], в который введены новые средства работы с массивами.
Ниже обсуждается реализация рассмотренных здесь подходов для систем различной архитектуры.
Векторизующие компиляторы и операции с массивами в Фортране 90
Для решения большинства задач требуется интенсивная обработка массивов. Появление на современных ЭВМ аппаратных средств векторной обработки привело к необходимости разработки соответствующих средств в системном программном обеспечении.
Одним из таких средств является создание векторизующих компиляторов [8,3,9], помогающих эффективно использовать возможности, заложенные в аппаратуре. Большинство векторизующих компиляторов разработаны для Фортрана, но имеются векторизующие компиляторы и для Си и для Паскаля (Pascal-ХТ, фирмы Siemens) [9]. Однако автоматическая векторизация (т.е. выявление скрытого параллелизма) требует довольно сложного анализа исходной программы, и при этом некоторые конструкции последовательных языков могут затруднить или даже сделать невозможной векторизацию. Некоторые компиляторы выполняют векторизацию по специальным директивам исходной программы; другие, по результатам анализа текста, сообщают пользователю, что в его программе препятствует векторизации; третьи - запрашивают (в интерактивном режиме) дополнительные указания пользователя. Все это требует от программиста дополнительных усилий и, кроме того, делает программы непереносимыми.
Но если программист все равно должен помогать компилятору векторизовать программу, то не лучше ли сразу писать ее на языке, который допускает явную спецификацию векторных операций? Параллельно с работами по совершенствованию методов векторизации было предложено несколько вариантов таких расширений как для Фортрана, так и для Си. Одним из первых и наиболее популярным был VECTRAN [9]. Использование разнообразных векторных расширений привело к необходимости унифицировать подобные средства в новом стандарте Фортрана - в Фортране 90.
Операции над массивами, введенные в Фортран 90, неявно задают внутренний параллелизм действий над компонентами массивов (массива), который носит естественный для пользователя характер. Новые средства позволяют эффективно реализовать программу практически на любой ЭВМ современной архитектуры, но наиболее целесообразно их использование на ЭВМ, имеющих аппаратные средства для векторной обработки.
Назовем некоторые из этих новых средств.
В Фортране 90 во многих местах, где традиционно разрешались только скаляры, могут использоваться массивы: полные массивы (имена массивов без индексов), секции массивов, конструктор массива.
Секция массива обеспечивает возможность адресоваться к части массива. Секция массива может состоять не только из расположенных подряд элементов исходного массива, но также и из несвязанных областей этого массива.
Семантика операций и стандартных функций расширена таким образом, что их можно применять не только к скалярам, но и к массивам; при этом операции и стандартные функции выполняются поэлементно над соответствующими элементами массива. Операнды, участвующие в одной операции, должны быть согласованы по конфигурации. Операции и стандартные функции над массивами могут выполняться параллельно, если процессор поддерживает параллельные вычисления. Массив может быть также значением выражения и значением функций (как стандартных, так и определяемых пользователем). Аналогичным образом расширена семантика операторов присваивания. Используя оператор WHERE или конструкцию WHEREEND WHERE, можно выполнить присваивание значений только некоторых элементов одного массива соответствующим элементам другого массива, т. е. выполнить присваивание под управлением логической маски.
Примеры:
REAL Х (10,20), Y (20), Z (-9:10) ............ Х (10,:) = 4.1 * Y + SQRT (2) ............ WHERE (Y > 0.0) Z = LOG (Y) ............
В языке предусмотрен механизм динамического размещения объектов в памяти.
Имеется большой набор стандартных функций для работы с массивами. Функции редукции (ALL, ANY, COUNT, MINVAL, MAXVAL, PRODUCT, SUM) выполняют арифметические, логические, счетные операции над массивами. Функции редукции могут быть применимы ко всему массиву или к какому-либо измерению массива. В качестве одного из необязательных параметров этих функций может использоваться маска, позволяющая выполнить различные вычисления над некоторым подмножеством исходного массива, как в следующем примере:
! Сумма положительных элементов массива А С = SUM (А, MASK = А > 0.0)
Функция MATMUL производит операцию умножения двух матриц, матрицы на вектор или вектора на матрицу. Функция DOTPRODUCT вычисляет скалярное произведение векторов. Функции конструирования создают новые массивы из элементов существующих массивов - объединение двух массивов путем поэлементного выбора в соответствии со значениями элементов маски (MERGE), формирование массива из нескольких копий исходного массива (SPREAD), изменение конфигурации массива (RESHAPE). С помощью функции РАСК элементы одномерного массива собираются из элементов другого массива, позиции которых определяются маской; функция UNPACK, наоборот, "разбрасывает" элементы одномерного массива в позиции (определяемые маской) другого массива. Функция TRANSPOSE производит транспонирование матрицы. Имеются функции, производящие сдвиги позиций элементов массива параллельно указанному измерению. Функции MINLOC и MAXLOC позволяют определить индексы минимального и максимального элементов массива.
Следует отметить, что новые возможности, введенные в Фортран 90, далеко не ограничиваются указанными средствами, но, поскольку они не ориентированы непосредственно на параллельную обработку, их рассмотрение находится за рамками данной статьи. Хотя в Фортране 90 отсутствуют средства, позволяющие пользователю эффективно распараллеливать программу для выполнения ее на нескольких параллельно работающих процессорах, однако дальнейшее развитие параллельных средств в последующих проектах основаны на новых возможностях Фортрана 90.
Средства поддержки параллельности в мультипроцессорных системах с общей памятью
Для вычислительных систем с общей памятью существует большое разнообразие средств, предлагаемых разработчиками [10].
В некоторых системах используются новые операторы, в других - специальные комментарии, в третьих - обращения к специальным процедурам, имеются и смешанные стратегии. Расширения для описания параллельности отличаются как синтаксисом, так и наборами выбранных примитивов.
Инициатором работы по унификации расширений языков средствами спецификации параллелизма для машин с общей памятью явилась группа PCF (Parallel Computing Forum), в дальнейшем X3H5 ANSI [11]. Эта группа объединила представителей крупнейших фирм, которые накопили большой опыт использования супер-ЭВМ с общей памятью. Группа PCF разработала языково-независимую модель машин с общей памятью. Цель группы - разработка расширений языков Фортран 77, Си, Фортран 90 на основе этой модели.
Основными управляющими параллельными конструкциями в этом проекте являются параллельные циклы и конструкция - параллельные секции. Предполагается, что витки цикла (отдельные итерации) и отдельные секции в этих конструкциях могут выполняться параллельно на разных процессорах. Предусмотрены средства задания циклов (и параллельных секций) с полностью независимыми витками (секциями), когда витки (секции) могут выполняться в произвольном порядке и циклы (секции) с зависимостью по данным, требующие синхронизации, которая обеспечивает правильный порядок вычислений.
Объекты данных, используемые в таких параллельных конструкциях, могут быть приватными для каждого витка (секции) и разделяемыми между ними. В тех случаях, когда есть зависимость между итерациями (секциями), требуется синхронизация. Предусматривается неявная синхронизация, автоматически выполняемая системой реализации и явная, задаваемая пользователем. В качестве средств явной синхронизации используются такие традиционные средства, как семафоры, события и критические области. Для этих средств вводятся новые типы данных, новые операторы и стандартные функции.
Средства поддержки параллельности для многопроцессорных систем с распределенной памяью
Для систем с распределенной памятью обычно используется механизм задач (процессов) и передачи сообщений (обмен данными). Исходная программа разбивается на задачи (подзадачи), которые могут выполняться параллельно на разных процессорах. Связь между задачами осуществляется с помощью передачи сообщений. В основе подхода лежит фундаментальная модель Хоара [12].
Очевидно, что не все программы позволяют эффективно использовать распределенные системы. Так как обмены сообщениями требуют затрат времени для своего выполнения и приостанавливают процессор при ожидании получения сообщения, очень важно, чтобы время, необходимое для обмена сообщениями, не доминировало над временем выполнения программы.
Распределенные системы лучше всего использовать для тех вычислительных задач, которые могут быть разбиты на такие подзадачи, для которых время выполнения существенно больше (долгоживущие процессы), чем время обмена между ними.
Имеются разные подходы как к выбору конкретных средств реализации механизма задач и передачи сообщений, так и отображению этих средств в языке.
Во многих системах (EXPRESS, PVM, P4, PARMACS и др.) механизм задач реализуется с помощью библиотечных вызовов. Накоплен большой опыт использования подобных систем; предпринимаются попытки унификации. Проект стандарта MPI (Message Passing Interface) [13] представляет собой стандартный набор библиотечных интерфейсов для передачи сообщений.
MPI включает большой набор средств, в число которых входят операции передачи сообщений от одного источника (процессора) к другому. Каждому из 6 разных (по способу синхронизации) видов передачи сообщений соответствует своя операция; необходимая для выполнения операции информация задается с помощью параметров процедур. Предусмотрены коллективные операции, включающие как широковещательную передачу сообщений, так и функции редукции.
Поддерживаются все типы данных, имеющиеся в Фортране и Си, имеются и собственные типы данных. Кроме того, для предотвращения коллизии с правилами типов языков верхнего уровня в MPI предусмотрены системные (так называемые "скрытые") объекты, внутреннее представление которых скрыто от пользователя. Предусмотрена возможность конструирования производных типов (структур), которые обеспечивают возможность с помощью одного вызова передать объекты данных разных типов, передать данные, не расположенные в непрерывной области памяти или передать секции массивов.
Для адресации используются группы процессов и коммуникаторы. Коммуникаторы и контексты обеспечивают возможность делить общее коммуникационное пространство на отдельные замкнутые области.
Хотя MPI предлагает большой набор средств, все же, как уже отмечалось, для прикладных программистов более предпочтительными являются системы, основанные на расширении языков.
Расширения Фортрана для рассматриваемой архитектуры реализованы, например, в языке Fortran Suprenum [14]. В этом языке используется аппарат динамического создания задач и асинхронная модель передачи сообщений. Языковые средства обеспечивают более высокий уровень программирования, так в операторах передачи сообщений можно указывать произвольный список передаваемых данных, аналогичный списку ввода/вывода Фортрана, что гораздо удобнее, чем средства, имеющиеся в системах, основанных на библиотечном подходе, в которых требуется, чтобы либо все передаваемые данные находились в непрерывной области памяти, длина которой часто указывается в байтах, либо (как в MPI) необходимо предварительно объединить эти данные в структуру.
Разработка Fortran Suprenum легла в основу проекта европейского стандарта, который разработан в Германии в рамках общеевропейского проекта ESPRIT [15]. Языковые расширения в данном проекте ориентированы на Фортран 90. Для того, чтобы вводимые расширения были машинно-независимыми, предлагается модель абстрактной машины - GENESIS.
Согласно этой модели, прикладная программа содержит одну начальную задачу и может содержать другие задачи. Несколько задач могут выполняться параллельно на разных процессорах, однако число задач не ограничивается числом процессоров. Каждая задача имеет уникальное имя. Модель предполагает динамическое создание задач; однажды созданная задача размещается в локальной памяти статически. Задача использует только локальную область памяти без разделения данных с другими задачами. Выполнение программы начинается с выполнения начальной задачи. Она создает другие задачи, которые, в свою очередь, могут также создавать новые задачи.
Обмен информацией между задачами осуществляется с помощью передачи сообщений. Предусмотрено три способа передачи сообщений: синхронный, асинхронный и передача без ожидания.
В язык введен новый тип данных (имена задач), дополнительный вид программных единиц (программные единицы-задачи), новые операторы, включая операторы передачи сообщений SEND и RECEIVE, расширен набор стандартных процедур.
Расширения языков, ориентированные на различные виды параллельной архитектуры
Разработки прежних лет
Помимо рассмотренных выше подходов, предпринимались также попытки создания языковых расширений, ориентированных одновременно и на системы с общей памятью и на системы с распределенной памятью.
В некоторых системах [3] в язык включались как средства реализации механизма задач и передачи сообщений, так и конструкции, задающие параллельное выполнение итераций цикла, параллельное выполнение ветвей и средства синхронизации (семафоры, события, барьеры и т.п.). Аналогичный подход был в свое время реализован и в языке Ада.
Более простые средства были предложены в проекте Linda [16] (Йельский университет). Linda - это не язык, а набор из четырех операторов, которые могут быть добавлены к разным языкам программирования для спецификации параллелизма. Существенным недостатком проекта является невозможность эффективной реализации и сложность в обеспечении надежности. Повидимому, именно этим объясняется тот факт, что проект Linda не получил широкого распространения.
Новые разработки, ориентированные на разбиение данных
В последнее время получил развитие новый подход к расширениям последовательных языков программирования, в частности, языков Фортран и Си. Этот подход ориентирован на разбиение данных. В язык вводятся средства, позволяющие пользователю специфицировать размещение и распределение данных по процессорам, всю остальную работу по распараллеливанию программы выполняет компилятор. Предлагаемые средства могут быть использованы как для машин с векторными процессорами, так и для разных типов многопроцессорных систем, включая системы с массовым параллелизмом.
Разработка соответствующих расширений для Фортрана выполнена в двух коллективах. Коллектив под руководством Ken Kennedy (Техасский университет) [17] разработал проект языка Fortran D; коллектив в Венском университете разработал язык Fortran Vienna [18]. Хотя на концептуальном уровне в этих подходах много общего, языки отличаются друг от друга.
С целью объединения усилий и унификации языковых средств в январе 1992 года образована группа HPF (High Permormance Forum), которая разработала проект языка HPF (High Performance Fortran) [19], являющегося расширением Фортрана 90.
Помимо векторных операций Фортрана 90, HPF содержит директивы для описания способов разбиения данных между параллельныо работающими процессорами и средства явного указания параллельности.
Директивы HPF имеют вид комментария, который начинается с символов !HPF$. Перечислим некоторые из этих директив. С помощью директивы TEMPLATE объявляется некоторое абстрактное пространство - шаблон. Директива ALIGN специфицирует элементы различных массивов, которые должны быть распределены на одном и том же процессоре, т.е. директива позволяет специфицировать взаимное выравнивание (установить отображение) массивов с элементами шаблона или друг с другом как внутри, так и между размерностями в зависимости от характера- вычислений; это нужно, чтобы минимизировать количество пересылок между процессорами. Имеются средства для установления отображения как на этапе компиляции, так и динамически.
Директива DISTRIBUTE специфицирует соответствие элементов шаблона и процессоров, т.е. определяет способ распределения по процессорам. Специфицируется характер распределения (блочный, циклический, блочно-циклический) для каждого измерения шаблона. Характер распределения по процессорам может задаваться как на статическом уровне, так и на динамическом.
Из средств явного указания параллельности отметим оператор FORALL, допускающий большее разнообразие видов секций, чем в Фортране 90, и директиву INDEPENDENT, которая указывает компилятору, что итерации в следующем DO-цикле или операторе FORALL могут выполняться независимо, в любом порядке (нет зависимостей по данным в разных итерациях).
Хотя деятельность группы HPF ведется не в рамках ISO и ANSI, этот язык становится фактическим стандартом.
Объявленный недавно фирмой NAS (NA Software Ltd) [20] компилятор HPF осуществляет перевод HPF программ на Фортран 90, дополненный вызовами подпрограмм одной из библиотечных систем поддержки концепции механизма задач и передачи сообщений: MPI, PARMACS или PVM.
Заключение
Механизм задач и передачи сообщений, используемый для распределенных систем, и средства синхронизации, используемые в системах с общей памятью, по нашему мнению, являются непривычными и неестественными для прикладных программистов.
Подход, предлагаемый в языке HPF, нам представляется наиболее перспективным, так как он обеспечивает более высокий уровень программирования; средства, вводимые в язык, более простые и более привычные для прикладного программиста; предлагаемые расширения не требуют от пользователя детального знания проблем, возникающих при параллелизации программ и избавляют его от необходимости заботиться об организации параллельных процессов (задач) и средствах их взаимодействия. Кроме того, этот язык ориентирован на более широкий класс параллельных вычислительных систем, чем предыдущие проекты.
Предполагается, что в будущие стандарты Фортрана - Фортран 95 и Фортран 2000 - войдут средства, ориентированные на HPF. Помимо этого, в будущих стандартах предполагается дальнейшее развитие средств параллельной обработки. Продолжается развитие HPF. Для языка Си также разрабатываются проекты стандартизации средств параллельной обработки.
Литература
[1] Джоунз Г. Программирование на языке ОККАМ, М. Мир, 1989.
[2] Программирование на параллельных вычислительных системах, М. Мир, 1991.
[3] Итоги науки и техники. Вычислительные науки, т.З, А.П. Черняев. Системы программирования для высокопроизводительных ЭВМ. М.: ВИНИТИ, 1990.
[4] Hempel R. The Argonne/GMD Macros in FORTRAN for Portable Parallel Programming using the Message Passing Programming Model, Feb. 1991.
[5] International Standard ISO/IES 1539:1991(Е) Information technology - Programming languages - Fortran
[6] Горелик А.М., Ушкова В.Л. Фортран сегодня и завтра. М. Наука, 1990.
[7] Международный стандарт ИСО/МЭК 1991(Р). Перевод с англ.
[8] Хокни Р., Джессхоул К. Параллельные ЭВМ. Перевод с англ. М. Радио и связь, 1986.
[9] Векторизация программ: теория, методы, реализация, Сб. статей. Пер. с англ. М., Мир, 1991.
[10] А comparison of 12 parallel Fortran dialects//IEEE Software. 1988, Vol.5, 5, р.52-67. [11] НЗН5 Parallel Extensions for Fortran. Apr., 1993 Document Number ХЗН5/93-SD2-Revision А.
[12] Хоар Ч. Взаимодействующие последовательные процессы. М. Мир, 1989.
[13] Draft. Documen1 far а Standard Message - Passing Interface Message Passing Interface Forum, Feb., 1994.
[14] Solchenbach К. Suprenum-Fortran - an MIMD/SIMD language. Supercomputer, March 1989. vol.6, N 1
[15] Thole С.-А. Proposal for а Fortran Syntax Specification for distributed memory architectures. Version 1.0, April, 1990.
[16] Pancake С., Bergmark D. Do parallel languages respond to the needs of scientific programmers? IEEE Comput. 23, 12 (Dec. 1990), 13-23.
[17] Hiranandani 5., Kennedy К., Tseng С.-W. Compiling Fortran D for MIMD Distributed-Memory Machines, Comm. of the АСМ, vol. 35, N 8,(August 1992), 66-80.
[18] Zima Н., Brezany Р., Chapman В., Mexrotra Р., Schwald А. Vienna Fortran. А Language Specification Version 1.1.
[19] High Performance Fortran Language Specification. High Performance Fortran Forum, Мау 3, 1993, Version 1.0.
[20] The NA Software HPF Mapper Debugger, Nov 28, 1994.
