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

Российская академия наук ИНСТИТУТ СИСТЕМНОГО ПРОГРАММИРОВАНИЯ

Си од

г 1\ ноп

На правах рукописи

94 £

Ластовецкий Алексей Леонидович

ЯЗЫК И СИСТЕМА ПАРАЛЛЕЛЬНОГО ПРОГРАММИРОВАНИЯ ДЛЯ РАЗРАБОТКИ ПРОГРАММ. ЭФФЕКТИВНО ПЕРЕНОСИМЫХ В КЛАССЕ РАСПРЕДЕЛЕННЫХ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМ

Специальность 05.13.11 - Математическое и программное обеспечение вычислительных машин, комплексов, систем и сетей

Автореферат диссертации на соискание ученой степени доктора физико-математических наук

Москва-1997

Работа выполнена в Институте системного программирования Российской академии наук.

Официальные оппоненты: доктор физико-математических старший научный сотрудник доктор технических наук, профессор

доктор физико-математических член-корреспондент РАН

наук.

Крюков В. А. Кутепов Б.П.

наук.

Четверушкин Б.Н.

Ведущая организация Вычислительный центр РАН

Защита состоится 1997 ГОда в ^ на засе-

дании диссертационного совета Д 200.50.01 в Институте системного программирования РАН по адресу: 109004, Москва, ул. Б.Коммунистическая, д. 25.

С диссертацией можно ознакомиться в библиотеке Института системного программирования РАН.

Автореферат разослан "_"_ 1997 года.

Ученый секретарь диссертационного совета Д 200.50.01 кандидат физико-математических наук, доцент

Прохоров С. П.

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

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

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

Для того, чтобы быть полезным широкому кругу пользователей, такой инструментарий должен:

- поддерживать и облегчать эффективное параллельное программирование;

- поддерживать переносимое параллельное программирование;

- поддерживать модульное параллельное программирование;

- поддерживать и облегчать эффективно-переносимое параллельное программирование;

- поддерживать достаточно простую и прозрачную для пользователя программную модель, обеспечивающую надежное параллельное программирование.

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

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

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

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

Наконец, лишь очень немногие даже квалифицированные программисты смогут разработать сколько-нибудь сложную правильную парал-

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

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

Первый подход базируется на языках программирования высокого уровня, таких как HPF (High Perfomance Fortran). HPF поддерживает достаточно простую и легкую в использовании программную модель и позволяет разрабатывать надежные параллельные программы. Он был стандартизирован чуть больше 2 лет тому назад, но уже появились высококачественные переносимые компиляторы, поддерживающие принятый стандарт. Поэтому HPF может быть использован для разработки переносимых и модульных параллельных прикладных программ. Однако HPF, как и его предшественники Fortran D и Vienna Fortran и другие языки программирования высокого уровня (такие как CM Fortran, С*, Dataparallel С, Modula-2*, Fortran М, СС++ и т.д.) не предназначены для эффективного параллельного программирования неоднородных сетей компьютеров. Дело в том, что моделью параллельной вычислительной машины, лежащей в основе этих языков, является однородный мультипроцессор с очень быстрыми коммуникациями между его вычислительными узлами. Эта модель уходит корнями в массивно-параллельные компьютеры, бывшие первоначально целевой архитектурой для этих языков. Поэтому. HPF, поддерживая эффективно-переносимое параллельное программирование для массивно-параллельных компьютеров и однородных сетей рабочих станций, связанных с помощью очень быстрого сетевого оборудования, не поддерживает того же самого для неоднородных сетей.

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

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

ся на расширении языков С, С++ и Fortran 77 с помощью библиотек функций передачи сообщений, таких как MPI (Message-Passing Interface). Было разработано довольно много пакетов передачи сообщений, позволяющих использовать неоднородную сеть компьютеров как единую параллельную машину, однако, в настоящее время, наиболее популярными являются PVM и MPI.

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

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

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

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

скоростью коммуникаций между ними.

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

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

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

Текущая версия системы программирования шрС написана на ANSI С и компилируется большинством компиляторов языка С (включая gcc). В качестве коммуникационной платформы используется MPI 1.1. Поэтому сама система программирования обладает высокой степенью переносимости и легко устанавливается на различных платформах. Первая версия системы программирования трС была реализована в октябре 1996 года и помещена в Internet для свободного доступа по адресу http://www.lspras.ru/~mpc. В настоящее время доступна версия 1.2.0 системы, оттестированная для неоднородных сетей, состо-

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

Апробация работы. Результаты работы были представлены на:

- 4-й международной конференции Parallel Architectures and Compilation Techniques (PACT'96), октябрь 1996 года, США;

- семинаре по новым технологиям в NASA Ames, ноябрь 1996 года, США;

- 30-й международной конференции Hawaii International Conference on System Sciences (HICSS'30), январь 1997 года, США;

- 2-м международном симпозиуме Aizu International Symposium on Parallel Algorithms/Architectures Synthesis (pAs'97), март 1997 года. Япония;

- на 11-ом международном симпозиуме International Parallel Processing Symposium (IPPS'97) в рамках 7th Heterogeneous Computing Workshop (HCW'97), апрель 1997 года, Швейцария;

- научных семинарах в ряде ведущих университетов США (University of Nebraska at Omaha, California Institute of Technology, Oregon State University, Naval Postgraduate School), октябрь-ноябрь 1997 года.

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

Структура и объем работы. Диссертация изложена на 141 странице и имеет четыре приложения. Она состоит из четырех глав и заключения. Библиография насчитывает 37 наименований.

КРАТКОЕ СОДЕРЖАНИЕ РАБОТЫ

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

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

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

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

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

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

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

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

/* Строка 1 */ nettype Rectangle {

/* Строка 2 */ coord 1=4;

/* Строка 3 */ node {

/* Строка 4 */ I<2 : fast scalar;

/* Строка 5 */ I>=2: slow scalar;

/* Строка 6 */ };

/* Строка 7 */ llnk {

/* Строка 8 */ I>0: [1]<->[1-1];

/* Строка 9 */ I==0: [1]<->[3];

/* Строка 10 */ };

/* Строка 11 */ parent [0];

/* Строка 12 */ };

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

Здесь строка 1 содержит заголовок объявления сетевого типа. Она вводит имя сетевого типа.

Строка 2 содержит объявление системы координат, к которой привязываются процессоры. Она вводит целую координатную переменную I со значениями от 0 до 3.

Строки 3-6 содержат объявление процессорных узлов. Оно привязывает процессоры к системе координат и объявляет их типы и производительности. Строка 4 соответствует предикату для всех К4 если К2, то быстрый процессор типа scalar привязывается к точке с координатами III. Строка 5 соответствует предикату для всех К4 если 1>=2, то медленный, процессор типа scalar привязывается к лючке с координатами. II]. Спецификаторы производительности fast и slow задают относительные производительности процессорных узлов одного типа. Для любой сети этого типа эта информация позволяет компилятору приписать каждому процессорному узлу его вес, нормализованный относительно родительского узла сети. Отметим, что хост-процессор всегда имеет тип scalar и нормальную производительность.

Строки 7-10 содержат объявление линков. Оно специфицирует линки между процессорами. Строка 8 соответствует предикату для всех 1<4 если 1>0 то имеется ненаправленный линк обычной длины, связывающий процессоры с координатами [I] и [1-1], а строка 9 со-

ответствует предикату для всех К4 если 1==0 то имеется ненаправленный линк обычной длины, связывающий процессоры с координатами [I] и 13]. Отметим, что если линк между двумя процессорами не специфицирован явно, то это означает наличие между ними линка максимальной для данной сети длины.

Строка 11 содержит объявление родителя и специфицирует, что родительский процессор имеет координату [0] в создаваемой сети.

Имея объявление сетевого типа, можно объявить идентификатор сетевого объекта этого типа. Например, объявление

net Rectangle rl; вводит идентификатор rl сетевого объекта типа Rectangle.

По определению, объект данных, распределенный по некоторой области вычислительного пространства, составляется из обычных (нераспределенных) объектов одного типа, размещенных в процессорных узлах этой области таким образом, что каждый процессорный узел содержит одну и только одну компоненту распределенного объекта. Например, объявления net Rectangle r2: int [*]de, [г2] da[10] ; repl int [*]di;

вводит целую переменную de, распределенную по всему вычислительному пространству, массив da из десяти целых, распределенный по сети г2, а также переменную di, размазанную по всему вычислительному пространству. По определению, распределенный объект является размазанным, если все его компоненты равны между собой.

Кроме простого сетевого типа можно объявлять параметризованное семейство сетевых типов, называемое топологией или родовым сетевым типом. Например, объявление

nettype Ring(n, p[n]) { coord I=n; node {

I>=0: fast*p[I] scalar;

};

link {

I>0: [IK-HI-11; I==0: [IK-Hn-ll:

};

parent [0];

/* Строка 1 */

/* Строка 2 */

/* Строка 3 */

/* Строка 4 */

/* Строка 5 */

/* Строка 6 */

/* Строка 7 */

/* Строка 8 */

/* Строка 9 */

/* Строка 10 */

/* Строка 11 */

вводит топологию с именем Ring, соответствующую сетям, состоящим из п процессоров типа scalar, связанных в кольцо с помощью ненаправленных линков нормальной длины. Заголовок объявления (строка 1) вводит параметры топологии Ring, а именно, целый параметр п и векторный параметр р, состоящий из п целых. Соответственно, координатная переменная I пробегает значения от 0 до п-1, строка 4 соответствует предикату для всех Кп если 1>-0, то быстрый процессор типа scalar, чья относительная производительность специфицируется значением pill, привязывается к точке с координатами [I] и т.д. Здесь, спецификатор производительности fast*p[I] содержит так называемый спецификатор мощности *рШ. В общем случае, значение выражения в спецификаторе мощности должно быть положительным целым числом, а его операнды должны состоять только из констант, координатных переменных и параметров топологии. Если значение этого выражения равно 1, то спецификатор мощности можно опустить.

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

Имея объявление топологии, можно объявить идентификатор сетевого объекта подходящего типа. Например, фрагмент repl [*]а[4]={10, 20, 30, 40}; net Ring(4. а) г: вводит целый массив а, размазанный по всему вычислительному пространству, сетевой тип Ring(4, а) как экземпляр топологии Ring, а также идентификатор г сетевого объекта этого типа.

Экземпляр топологии может быть получен не только статически, но и динамически. Например, фрагмент repl [*]m, [»Ш1001:

/# Вычисление in, ntOl, ____n[m-l] */

{

net Ring(m, n) rr;

}

вводит идентификатор rr сетевого объекта, чей тип определяется

- И -

полностью только во время выполнения программы.

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

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

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

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

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

Вычислительное пространство под новую сеть может отводиться не только путем выделения еще не использованного вычислительного пространства, но и путем размещения новой сети в области вычислительного пространства, уже выделенной под некоторую сеть. Это может быть сделано путем явного или неявного определения подсети уже существующей сети. Например, фрагмент repl [*]а[6]={10, 20, 30, 40, 50, 60}; net Ring(6. а) гб; subnet [гб:I<5] sr5; subnet [sr5:I<3] sr3; subnet [гб:I<4] sr4; определяет сеть гб и его подсети sr3, sr4 и sr5. Здесь конструкции [г6:К5] и [гб: К41 специфицирует те процессоры сети гб, которые образуют подсети sr5 и sr4 соответственно, a [sr5:I<3] -процессоры подсети sr5, образующие подсеть sr3.

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

На множестве подсетей любой сети определено отношение частичного порядка "быть подсетью", которое необходимо компилятору для правильной трансляции многих выражений и должно явно специфицироваться в программе. Существует два основных способа такой спецификации. Во-первых, это отношение может быть специфицировано с помощью объявления подсети, аналогичного объявлению подсети sr3 в последнем фрагменте, которое специфицирует, что подсеть sr3 является подсетью подсети sr5. Во-вторых, это может быть сделано с помощью специального объявления отношения. Например, хотя, фактически, подсеть sr4 и является подсетью подсети sr5, компилятор будет считать эти подсети несравнимыми, если в соответствующем блоке не будет объявления вида

relation sr4<sr5;

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

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

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

ветствущем объявлении прямо перед идентификатором поместить спецификатор соответствующей сети. Например, объявления net Ring(ll,pll) Netl;

int [*]Derror, [Hetl]Da[10], *[Hetl:I<7]Dpi[5]; объявляют Derror как объект данных целого типа, распределенный по всему вычислительному пространству, объявляют Da как массив из десяти целых, распределенный по сети Netl, объявляют неявно подсеть сети Netl, а также объявляют Dpi как массив из пяти указателей на целое, распределенный по этой подсети.

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

Специальным видом распределенного объекта данных является т. н. размазанный, объект, все значения компонент которого равны между собой на протяжении всего времени выполнения программы. Для спецификации размазанных объектов используется квалификатор repl в манере, аналогичной использованию квалификаторов типа const и volatile. Например, объявление

int repl [*] n=10; определяет переменную п как размазанный по всему вычислительному пространству объект данных.

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

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

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

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

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

Оператор языка может выполняться на хост-процессоре, на процессоре одной из сетей, на сети или подсети, на совокупности сетей/подсетей или на всем вычислительном пространстве. В последних трех случаях оператор называется распределенным. Распределенный оператор - это либо обычный последовательный оператор языка Си. расширенный на случай распределенных данных, либо специальный параллельный оператор fan, par или pipe.

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

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

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

Выполнение трС-программы начинается с вызова функции main на всем вычислительном пространстве.

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

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

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

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

В трС нет средств спецификации отдельной сети, принадлежащей распределенной сети. Поэтому, всегда, когда специфицируется под-

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

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

В общем случае, родителем распределенной сети может быть как сеть, так и подсеть.

Как и в ANSI С, минимальной единицей трансляции языка шрС является файл.

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

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

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

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

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

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

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

За исключением случая, когда обозначение функции используется в качестве операнда операции взятия адреса, обозначение базовой функции преобразуется в распределенный по всему вычислительному пространству указатель на нераспределенную функцию; обозначение узловой функции преобразуется в указатель на узловую функцию, распределенный по области вычислительного пространства, на которой вызвана вызывающая функция; обозначение сетевой функции

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

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

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

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

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

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

коммуникационный пакет (в настоящее время, МР1 1.1) и обеспечивает независимость компилятора от конкретной целевой платформы.

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

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

В настоящее время, компилятор использует две модели целевой программы, в зависимости от режима компиляции:

- модель БРИБ, когда все процессы, составляющие работающую целевую программу, выполняют идентичный код;

- модель, при которой компилятор транслирует исходный шрС-файл в два отдельных целевых файла - один для виртуального хост-процессора, а второй для всех остальных виртуальных процессоров.

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

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

ному пространству.

Выполнение целевой программы начинается с вызова функции инициализации МРС_1пИ всеми процессами, составляющими выполняющуюся целевую программу (включая диспетчер). Инициализация включает:

- инициализацию коммуникационной платформы, которую использует система поддержки времени выполнения;

- выделение диспетчера и хоста;

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

- инициализацию диспетчера.

Диспетчер является единственным процессом, который не покидает функцию МРС_1пН. Он циклится внутри этой функции, принимая запросы. Частным примером такого запроса является запрос на создание сети.

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

Сразу после инициализации вычислительное пространство представляется хостом и множеством свободных узлов. Узел является свободным тогда и только тогда, когда вызов на нем функции МРС_1з_Ьизу() возвращает 0.

Доступ к области осуществляется через ее дескриптор. Если дескриптор гб соответствует некоторой созданной области, то любой узел вычислительного пространства принадлежит этой области тогда и только тогда, когда вызов функции МРС_1з_щетЬег(&гс1) на этом узле возвращает значение 1. В этом случае, дескриптор г<3 позволяет узлу получать всю информацию о соответствующей области, а так-

же идентифицировать себя внутри нее.

В создании области, представляющей сеть (сетевой области), участвуют родительский узел, диспетчер и все свободные узлы. При этом родительский узел вызывает функцию МРС_Ие1_сгеа1е, а все свободные вызывают функцию ожидания МРС_С^ег. Родительский узел вычисляет топологические характеристики сети и передает диспетчеру запрос на создание области. Запрос содержит присваиваемый компилятором номер сети, уникальный в пределах компилируемого файла, и топологические характеристики сети, основываясь на которых диспетчер отображает множество виртуальных процессоров создаваемой сети во множество свободных узлов. Затем диспетчер посылает каждому свободному узлу сообщение, извещающее его о том, включен он или нет в создаваемую область. Для включенных узлов это сообщение дополнительно содержит номер сети в файле и информацию, необходимую для завершения инициализации дескриптора области. По номеру сети узлы, включенные в область, определяют дескриптор, соответствующий создаваемой области, и завершают его инициализацию. После этого они покидают функцию ожидания. Узлы оставшиеся свободными покидают функцию ожидания МРС_0ГГег, только получив соответствующую команду от диспетчера.

В освобождении сетевой области участвуют все ее члены, диспетчер и все свободные узлы. Узлы, входящие в область, вызывают функцию МРС_Не1_Ггее. При этом родительский узел сетевой области посылает запрос диспетчеру на освобождение области. Получив этот запрос, диспетчер посылает свободным узлам, находящимся внутри функции ожидания МРС_0ГГег, команду на объединение с освобождающимися узлами. Освободившиеся узлы затем также вызывают функцию ожидания, внутри которой они начинают ожидать команд диспетчера.

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

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

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

Когда диспетчер отображает виртуальные процессоры создавае-

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

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

- число физических вычислительных узлов, составляющих вычислительную машину с распределенной памятью, и их производительности;

- число узлов вычислительного пространства (процессов), связанных с каждым из физических вычислительных узлов;

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

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

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

Диспетчер приписывает вес, являющийся положительным вещест-

венным числом, каждому виртуальному процессору размещаемой сети, таким образом, что:

- чем мощнее виртуальный процессор, тем больший вес он получает;

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

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

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

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

узлов, связанных с Р, разбито на N подмножеств ht_____hN. Пусть

Vj - вес виртуального процессора, размещенного в данный момент на j-ом узле множества ht. Тогда оценка мощности свободного узла, связанного с Р, вычисляется по формуле

( W ^

шах { ---------- }

i I v + I v13 J j

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

w

( w ^

шах { ----------- }

1 V v + I v13 )

3

V + I VkJ

j

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

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

Каждый блок шрС-программы транслируется в блок целевой С-программы с обращениями к функциям системы поддержки времени выполнения.

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

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

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

имеет следующий вид: {

объявления, соответствующие объявлениям, переменных в исходном трС-блоке

{

пролог создающей точки ожидания

1Г(!МРС_1з_Ьизу{}) {

целевой код, выполняемый свободными узлами для создания сетевых областей для сетей, определенных в исходном трС-блоке

}

1г(мрс_1Б_:ьизу()) {

целевой коЭ, выполняемой, занятыми узлсиш для создания областей для сетей и подсетей, определенных в исходном трС-блоке, а также

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

}

эпилог создающей точки ожидания

}

целевой код для операторов исходного трС-блока,

начинающихся с оператора разрыва точки ожидания {

целевой код, выполняемый заняты/ш узлами для

освобождения сетевых областей для сетей и подсетей,

определенных в исходном трС-блоке

метка освобождающей точки ожидания : 1Г(!МРС_1з_ЬизуО) {

целевой код, выполняемый свободными узлами для освобождения сетевых областей для сетей, определенных в исходном трС-блоке

}

эпилог освобождающей точки ожидания>

}

}

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

случае целевой блок имеет следующий вид: {

объявления, соответствующие объявлениям переменных в исходном трС-блоке

{

пролог общей точки ожидания метка общей точки ожибания> : Ш!МРС_18_Ы18у()) {

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

}

ШМРС_1з_ЬизуО) {

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

целевой код для операторов исходного трС-блока

}

эпилог общей точки ожиЗания

}

}

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

Глава 4 посвящена технологии разработки эффективно-переносимых программ на шрС. В ней приводятся экспериментальные результаты практического использования системы программирования трС.

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

В диссертационной работе сделаны лишь первые шаги в этом направлении. Разработка сколько-нибудь полного каталога типичных технологических приемов требует обобщения длительного опыта программирования на шрС больших программных систем.

Раздел 4.1 на примере моделирования эволюции системы галактик демонстрирует подход к эффективно переносимому программированию на шрС нерегулярных задач.

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

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

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

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

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

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

Программа на шрС реализует следующую схему: Инициализировать галактику на виртуальном хост-процессоре Создать сеть для дальнейших вычислений и обменов данными Разослать группы тел по виртуальным процессорам сети Вычислить (параллельно) массы групп

Обменяться массами групп между виртуальными процессорами »(1п1е<1) {

Визуализировать галактику на виртуальном хост-процессоре

Вычислить (параллельно) центры масс групп

Обменяться центрами масс между виртуальными процессорами

Параллельно обновить атрибуты групп

Собрать группы на виртуальном хост-процессоре

}

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

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

вает.

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

Полный текст программы на шрС, моделирующей эволюцию галактик, приводится в приложении 3.

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

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

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

В разделе 4.3 приводятся экспериментальные результаты, демонстрирующие значительное ускорение решения задач на неоднород-

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

В заключении сформулированы новые научные результаты работы, обоснована ее практическая значимость и перечислены основные результаты. выносимые на защиту.

В диссертационной работе получены следующие новые научные результаты:

- создана модель параллельного программирования для неоднородных сетей компьютеров;

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

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

- разработаны технологические приемы эффективно-переносимого программирования на трС.

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

Практическая значимость диссертационной работы определяется тем, что система программирования трС реализована, помещена в Internet для свободного доступа и используется для программирования неоднородных сетей персональных компьютеров и рабочих станций (в компании West Virginia Network, Университете Миссури, Московском институте инженеров транспорта, Университете Луизианы. Институте высокопроизводительных вычислений и баз данных и т.д.).

Язык и его система программирования использовались автором как в теоретической, так и в практической частях курсов по параллельному программированию и системам параллельного программирования, читаемым на факультете ВМиК Московского государственного университета им. М.В.Ломоносова и в Московском физико-техническом институте. Кроме того, язык трС и его система программирования используются или планируются к использованию в качестве базы для курсов по параллельному программированию в Московском институте

инженеров транспорта, Университете Луисвилля (США), Университете штата Небраска в Омахе (США) и Военно-морской академии (Монтерей, США).

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

На защиту выносятся следующие основные результаты:

- язык программирования шрС;

- система программирования шрС.

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

Автор благодарит В.П.Иванникова за неизменную поддержку и постоянное внимание к работе, С.С.Гайсаряна, научившего его программированию, а также Д.М.Арапова, А.Я.Калинова и И.Н.Ледовских, участвовавших в разработке и реализации системы программирования шрС.

Публикации:

[1] А.Л.Ластовецкий, "Предварительное сообщение о языке программирования шрС", Вопросы кибернетики: Приложения системного программирования, Научный совет по комплексной проблеме "Кибернетика" РАН. Москва, 1995, сс. 20-39.

[2] A.Lastovetsky, "шрС - a Multi-Paradigm Programming Language for Massively Parallel Computers". ACM SIGPLAN Notices, 31(2), February 1996, pp.13-20.

[3] D.Arapov, A.Kalinov, and A.Lastovetsky. "Managing the Computing Space in the mpC Compiler", Proceedings of the 1996 Parallel Architectures and Compilation Techniques (PACT'96) Conference. IEEE CS Press, Boston, MA. Oct. 1996, pp.150-155.

[4] D.Arapov. A.Kalinov, and A. Lastovetsky,. "Resource Management in the mpC Programming Environment". Proceedings of the 30th Hawaii International Conference on System Sciences (HICSS'30), IEEE CS Press. Maui, HI. January 1997.

[5] D.Arapov, V.Ivannikov, A.Kalinov, A.Lastovetsky, I.Ledovskih, and T.Lewis, "Modular Parallel Programming in mpC for Distributed Memory Machines", Proceedings of the 2nd Aizu International Symposium on Parallel Algorithms/Architectures Synthesis (pAs'97), IEEE Computer Society Press, Aizu-Wakamatsu, Japan, March 1997. pp.248-255.

[6] D.Arapov, A.Kalinov, A.Lastovetsky, I.Ledovskih, and T.Lewis, "A Programming Environment for Heterogeneous Distributed Memory Machines", Proceedings of the 7-th Heterogeneous Computing Workshop (HCW'97) of the 11th International Parallel Processing Symposium (IPPS'97), IEEE CS Press, Geneva, Switzerland, April 1997, pp.32-45.

Atl

Подписано к печати 08.09.1997 г. Заказ 317-97. Объем 1,5 уч. изд. Бумага 60x84 1/16. Тираж 100 экз.

ООО "Микопринт". 109004, Москва, ул. Таганская. 1/2