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

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

На правах рукописи УДК 681.3.06:519.68

РГБ ОД

Ледовских Илья Николаевич

2 о ^дй гт

ИССЛЕДОВАНИЕ И РАЗРАБОТКА ЯЗЫКОВЫХ СРЕДСТВ ОПИСАНИЯ НЕОДНОРОДНЫХ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМ И ИХ РЕАЛИЗАЦИЯ В СИСТЕМЕ ПРОГРАММИРОВАНИЯ шрС

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

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

Москва-2000

Работа выполнена в Институте системного программирования РАЯ

Научный руководитель:

кандидат физико-математических наук

Научный консультант:

доктор физико-математических наук

Официальные оппоненты:

доктор физико-математических наук, профессор

кандидат физико-математических наук

С.С.Гайсарян

А.Л.Ластовецкий

И.В.Машечкин А.С.Косачев

Ведущая организация:

Институт точной механики и вычислительной техники

I/

I

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

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

Автореферат разослан « ¿Я ¿¡С^уО^Л 2000 г.

Ученый секретарь специализированного совета Д.200.50.01

доктор физико-математических наук

С.Д.Кузнецов

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

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

Актуальность темы.

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

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

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

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

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

Научная новизна.

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

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

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

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

Личный вклад соискателя:

• На основе теоретических разработок А.Л.Ластовецкого и Т.Льюиса разработаны синтаксис и семантика средств описания неоднородных абстрактных вычислительных систем языка шрС.

• Разработана ЬАЬЯ-грамматика языка шрС.

• Спроектировано и реализовано внутреннее представление трС-нрограммы.

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

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

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

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

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

Апробация работы и публикации. Система программирования шрС была опробована созданием ряда приложений из различных областей науки и техники. Результаты работ по созданию системы программирования гпрС, равно как и результаты ряда экспериментов с приложениями, были представлены на 4-й международной конференции Parallel Architectures and Compilation Techniques (PACT'96) в октябре 1996 года в США, на семинаре по новым технологиям в NASA Ames в ноябре 1996 года, США, на научных семинарах в ряде университетов США (University of Nebraska at Omaha, California Institute of Technology, Oregon State University, Naval Postgraduate School) в октябре-ноябре 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 (II'PS'97) в рамках 7tn Heterogeneous Computing Workshop (HCW'97) в апреле 1997 года, Швейцария, на 5-м международном симпозиуме International Symposium on Solving Irregularly Structured Problems in Parallel (IRREGULAR'98), в августе 1998 года, США, на международной конференции EUROMICRO'98 в августе 1998 года, Швеция. По результатам исследования и реализации имеется 6 печатных работ. Список публикаций по теме работы приведен в конце автореферата.

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

!. Средства описания абстрактных неоднородных вычислительных систем языка шрС.

2. Анализирующая компонента компилятора с языка шрС, включающая фазы синтаксического анализа, атрибутного анализа и подсистему шрС Adviser.

3. Модуль генерации топологических функций компилятора с языка шрС.

Объем и структура диссертации. Диссертация состоит из введения, пяти глав, заключения и четырех приложений. Список литературы состоит из 42 наименований. Объем работы - 128 страниц, включая приложения. СОДЕРЖАНИЕ РАБОТЫ

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

В первой главе проводится обзор инструментальных средств, используемых для высокопроизводительных вычислении в различных классах вычислительных систем, от последовательных ЭВМ до неоднородных сетей. Распараллеливающие компиляторы не способны обеспечить эффективную переносимость программ для большинства многопроцессорных систем, так как но-разному распознают скрытый в программе параллелизм, поэтому в обзоре основное внимание уделено средствам, позволяющим явно специфицировать параллелизм - параллельным библиотекам и языкам параллельного программирования. В классе суперскалярных и векторных компьютеров это Фортран 90, Фортран 95, СП и ряд других языков, в классе мультипроцессоров с общей памятью -расширение ОрепМР языков С, С++ и Фортран, языки Adl, Orea, NESL, Sp!it-C, SuperPascal и другие, библиотека BSP library. Коммуникационные пакеты PVM, MPI и язык программирования HPF используются для систем как с общей, так и с распределенной памятью. В классе систем с распределенной памятью используются экспериментальные распараллеливающие системы (PARADIGM), большое число библиотек передачи -сообщений-(PVM, MPI, Nexus, PARMAX, р4. Chameleon, CHIMP и другие), графические системы (HeNCE, CODE, Meander и

PADE) и параллельные языки (Оккам, Fortran M, Compositional С++, Fortran D,

-

Vienna Fortran, HPF, CM Fortran, C*, Dataparallel C, Modula-2*, Parallaxis). Описаны концепции и основные конструкции параллельного программирования многих из перечисленных языков. В контексте мультипроцессорных систем с распределенной памятью и неоднородных вычислительных сетей, особое внимание уделено MPI и языкам High Performance Fortran (HPF) и Parallaxis.

Вторая глава содержит обзор и анализ средств описания архитектуры виртуальной вычислительной системы в языках и системах параллельного программирования. Данные средства задают, по сути, схему выполнения параллельного приложения, и от того, насколько полно и точно эта схема может быть описана, зависит эффективность отображения виртуальной параллельной системы на конкретную исполняющую вычислительную сеть, а следовательно, и эффективность выполнения приложения. На примере наиболее широко распространенных систем показано, что существующие инструменты для параллельного программирования поддерживают только модель однородного мультипроцессора с очень быстрыми коммуникациями между процессорами по схеме «каждый с каждым». Такая виртуальная параллельная система не всегда может быть эффективно отображена на неоднородную сеть. Более того, распространенные средства параллельного программирования вовсе не предоставляют программисту возможности явно специфицировать виртуальную неоднородную параллельную вычислительную систему (единственное исключение - язык Parallaxis III, позволяющий описать неоднородность коммуникационной среды). Следовательно, рассмотренные языки не поддерживают разработку эффективно-переносимых профамм для неоднородных сетей.

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

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

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

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

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

• Эффективно распределять данные по описанной абстрактной неоднородной параллельной системе (сети).

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

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

В разделе 3.1 обосновывается выбор модели вычислительного узла виртуальной неоднородной параллельной системы. За основу модели узла взята виртуальная Си-машина, которая в наибольшей степени удовлетворяет требованиям мобильности и эффективности последовательной про1рам.мы. Рассматривается также возможность построения модели узла на основе объектно-ориентированного языка С++; обоснован отказ от использования этого языка. Виртуальная Си-машина не позволяет явно описывать векторные объекты и не содержит векторных операций. Как следствие, язык Си не в полной мере отвечает требованию эффективности реализации для векторных и суперскалярных узлов, поэтому модель вычислительного узла строится на основе векторного расширения Си - языка С[]. Язык С[] вводит понятие вектора как значения массива, предоставляет средства доступа к этому значению и богатый набор операций над векторами.

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

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

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

В разделе 3.4 приводится описание средств распределения вычислений. Описаны расширения синтаксиса и семантики выражений и операторов языка С[]. Семантика унарных, бинарных и тернарных операции расширена таким образом, что один или все операнды могут быть распределены по некоторой области вычислительного пространства. Операции могут быть асинхронными или приводить к пересылкам между процессорами. Особое внимание уделяется расширениям операции простого присваивания - асинхронному, рассылающему, собирающему присваиванию и параллельной пересылке. Операторы мо1Л'т выполняться либо па отдельном процессоре, либо на некоторой области вычислительного пространства, либо на совокупности таких областей, либо на всем вычислительном пространстве. Если в процессе выполнения оператора не производится пересылок данных, оператор может выполняться асинхронно. Оператор может быть также помечен специальной меткой в виде спецификатора распределения.

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

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

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

Выполнение программы начинается с вызова функции инициализации МРС1пк всеми процессами, включая диспетчер. Инициализация включает инициализацию коммуникационной платформы, выделение диспетчера и хоста, локальную инициализацию узлов, инициализацию диспетчера.

Диспетчер является единственным процессом, который не покидает функцию ¡\IPC_Init. Он циклится внутри эгой функции, принимая запросы. Частным примером такого запроса является запрос на создание сети.

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

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

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

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

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

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

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

В разделе 4.2 описывается набор топологических функций.

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

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

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

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

Пятая топологическая функция возвращает в закодированной форме в виде целого числа тип и производительность заданного виртуального процессора. Для случая, когда определение топологии не содержит объявления узлов, генерируется частый случай топологической функции node, тело которой содержит лишь оператор return SCALAR; , где SCALAR - константа, значение которой является кодом узла типа scalar. Код, генерируемый для наиболее общего случая, когда топология содержит узлы типа void, использует единожды заполняемый массив типов узлов

Наконец, шестая топологическая функция возвращает длину направленного липка между заданной парой виртуальных процессоров в виде целого числа. В случае, если объявление линков опущено, генерируется тривиальный случай функции link аналогично тривиальному случаю функции node. Если между заданной парой процессоров направленный линк явно не специфицирован, то функция возвращает значение, соответствующее «очень длинному» липку. Для случая, когда определение топологии содержит узлы типа void, генерируется функция link более сложного вида, но также оптимизированная в плане накладных расходов времени создания сети.

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

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

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

При генерации топологических функций фаза анализа компилятора решает следующие задачи:

1. Обход дерева сетевого типа и вычисление атрибутов узлов.

2. Генерация внутреннего представления для заголовков и тнпоз функции.

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

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

1. Обходится дерево топологического выражения;

2. Координатные переменные заменяются на индексные выражения вида c[i], где с - локальная переменная топологической функции (целочисленный массив), а i - константа.

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

4. Идентификаторы векторных параметров топологии, если они встречены не в индексном выражении, заменяются на (ppar+i); здесь рраг и i имеют ту же семантику, что и в случае скалярного параметра.

5. Индексные выражения, специфицирующие элементы векторных параметров топологии, заменяются на *(ppar+i+j), где рраг и i имеют ту же семантику, что и в случае скалярного параметра а j - индекс элемента.

Во всех подстановках, описанных выше, компилятор осуществляет простую оптимизацию, связанную с вычислением константных подвыражений, если выражения inj- константы. Если значение константного выражения i или i+j равно 0, то дерево бинарного выражения '+' не генерируется.

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

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

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

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

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

Раздел 4.7 посвящен вопросу эффективности реализации языка шрС. Проводится сравнение компилятора с трС (трсс) и компилятора GNU С (gcc). Использованы два теста. Первый - программа на шрС, моделирующая движение многих групп небесных тел иод действием сил гравитационного притяжения (задача N тел). Для этой программы характерен достаточно большой объем как параллельной части, так и последовательной части, выполняющей визуализацию с использованием библиотеки X-Windows. В качестве второго теста использованы исходные тексты компилятора трсс. В обоих случаях объем текстов, анализируемых компиляторами трсс и gcc, практически одинаков. При этом трсс выполняет более сложные семантические проверки, a gcc, хоть и вызывается без оптимизации кода, содержит дополнительный проход трансформации внутреннего представления. Оба теста показали, что на платформе Sun компилятор трсс не уступает компилятору gcc в скорости компиляции.

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

В пятой главе рассмотрен ряд вопросов, связанных с реализацией и использованием языка. Особое внимание уделяется вопросу сложности npoipa.4-мирования на трС. Предлагается способ решения данного вопроса -

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

Раздел 5.1 рассматривает вопрос сложности использования языка. Язык трС предоставляет пользователю достаточно прозрачную модель параллельного программирования. Ксли MPI можно назвать «ассемблером параллельного программирования», то использованная в языке трС модель абстрактной неоднородной параллельной вычислительной системы позволяет считать его языком параллельного программирования достаточно высокого уровня. Поэтому, говоря о сложности программирования, имеется в виду не столько сложность выражения на данном языке параллельного алгоритма, сколько сложность понимания программы человеком. Этот вопрос имеет два аспекта - понимание правильной программы с целью се верификации или модификации и понимание программы, в которой обнаружены ошибки периода компиляции. Обе эти задачи являются • следствием сложности атрибутной грамматики языка трС, в которой, по сравнению с языками С и С[], добавлено большое число атрибутов выражений и операторов с не всегда простыми правилами вычисления значений.

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

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

ЗАКЛЮЧЕНИЕ

Ниже приводятся основные научные результаты диссертационной

работы:

1. Совместно с д.ф.-м.н. Ластовсцким создана языковая модель абстрактной параллельной неоднородной вычислительной системы.

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

3. Разработаны принципы эффективной реализации средств описания абстрактной параллельной вычислительной системы языка шрС.

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

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

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

6. Разработана и реализована не имеющая аналогов интерактивная компонента системы программирования mpC - mpC Adviser, облегчающая написание семантически сложных программ на языке шрС.

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

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

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

Высокая эффективность программирования задач для неоднородных вычислительных сетей была подтверждена путем создания ряда приложении из разных областей науки. Практическая значимость языка mpC была высоко оценена специалистами по разработке программного обеспечения для высокопроизводительных вычислительных систем. Язык mpC выбран в качестве объектного языка в совместном проекте CDAC (Centre for Development of Advanced Computing, Bangalore, India) и ИСП РАН но созданию распараллеливающего компилятора с языка Fortran 90 для системы РARAM-10000.

Язык mpC и его система программирования находятся в процессе постоянного развития и совершенствования. Новые расширения языка и его компилятора связаны как с развитием модели неоднородной вычислительной системы, так и с переносом системы программирования на новые платформы. Планируется перенос системы программирования mpC в среду Windows NT и Windows 2000.

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

работах:

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

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

3. D.Arapov, A.Kalinov, A.Lastovetsky, and I.Ledovskih, "Experiments with mpC: Efficient Solving Regular Problems on Heterogeneous Networks of Computers via Irregularization", Proceedings of the Fifth International Symposium on Solving Irregularly Structured Problems in Parallel (IRREGULAR'98), Lecture Notes in Computer Science 1457, Berkley, CA, USA, August 9-11, 1998, pp.332-343

4. D.Arapov, V.lvannikov, A.Kalinov, A.Lastovetsky, and I.Ledovskih, "Managing Processes with Network Objects and Their Translation", Proceedings of the EUROMICRO'98 International Conference, IEEE Computer Society, August 25-27, 1998, Vasteras, Sweden

5. D.Arapov, A.Kalinov, A.Lastovetsky, and I.Ledovskih, "A Language Approach to High Performance Computing on Heterogeneous Networks", accepted for publication in Parallel and Distributed Computing Practices.

6. А.Л.Ластовецкий, И.Н.Ледовских, "Анализ структурной эквивалентности описаний в компиляторе с языка С[]", Вопросы кибернетики /Приложения системного программирования/, Москва, 1995, стр.6-19

Введение

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

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

3. Язык шрС. Основные аспекты семантики.

3.1. Модель архитектуры вычислительного узла

3.2. Концепция вычислительного пространства

3.3. Средства управления вычислительным пространством

3.3.1. Средства описания сетевых типов

3.3.1.1. Объявление системы координат

3.3.1.2. Объявление узлов

3.3.1.3. Объявление связей

3.3.1.4. Объявление родительского узла

3.3.2. Описание сетей и подсетей

3.3.2.1. Объявление сетей

3.3.2.2. Спецификатор типа сети

3.3.2.3. Описатель сети

3.3.2.4. Объявление подсетей

3.3.3. Описание распределенных данных

3.3.3.1. Явное объявление распределенных объектов данных

3.3.3.2. Явное объявление нераспределенных объектов данных

3.3.3.3. Неявное объявление распределения объектов данных

3.3.3.4. Объявление размазанных объектов данных

3.3.4. Распределение вычислений

3.3.4.1. Выражения

3.3.4.2. Операторы

4. Реализация средств управления вычислительным пространством

4.1. Выбор и обоснование подхода к реализации

5.2. Компиляция определения типа сети и топологические функции

4.3. Генерация топологических функций компилятором

4.4. Анализ семантики описаний

4.5. Анализ распределенных вычислений

4.6. Эффективность реализации

5. Другие аспекты реализации и использования языка шрС

5.1. Оценка сложности программирования на языке шрС

5.2. Интерактивная подсистема mpC Adviser

5.2.1. Общая характеристика подсистемы шрС Adviser

5.2.2. Режим расширенной диагностики ошибок

5.2.3. Режим интерактивной диагностики ошибок

5.2.4. Интерактивный режим исследования программы 93 Заключение 94 Список литературы 97 ПРИЛОЖЕНИЕ 1 100 ПРИЛОЖЕНИЕ 2 109 ПРИЛОЖЕНИЕ 3 124 ПРИЛОЖЕНИЕ

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

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

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

В данной работе требованию эффективной переносимости уделяется первоочередное внимание в следующем контексте.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Практическая значимость работы Первая версия системы программирования шрС была реализована в октябре 1996 года и помещена в Internet для свободного доступа по адресу http://www.ispras.ru/~mpc. В настоящее время доступна врсия 2.1.0 системы, оттестированная для неоднородных сетей, состоящих из рабочих станций, многопроцессорных серверов и персональных компьютеров под управлением различных версий операционной системы UNIX, и различных реализаций MPI. Как и предыдущие версии системы, текущая версия переносима и легко устанавливается на различных платформах. Система программирования шрС пользуется достаточно большой популярностью среди специалистов по высокопроизводительным вычислениям и скачивается с сервера Института системного программирования РАН в среднем 1-2 раза в сутки, а ее описание - 3-4 раза в сутки.

Личный вклад автора состоит в следующем:

• На основе теоретических разработок А.Л.Ластовецкого и Т.Льюиса разработаны синтаксис и семантика (составлено описание) язысовых средств описания неоднородных вычислительных систем. Эти языковые конструкции вошли в язык параллельного программирования шрС.

• Разработана полная LALR-грамматика языка шрС.

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

• Реализованы фазы синтаксического и атрибутного анализа компилятора языка шрС, при этом использован ряд оригинальных методов и алгоритмов.

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

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

• Реализован модуль генерации топологических функций.

• Выполнен перенос системы программирования трС, первоначально реализованной на платформе Sun/Solaris, на ряд Unix-платформ: HP-UX 9.08 и 10.20, SunOS 4.1.3, OSF/1, Linux (Red Hat Linux 4.0 и 5.2), FreeBSD 3.0 и 3.4.

Диссертационная работа построена следующим образом.

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

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

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

Глава 3 описывает основные аспекты языка программирования шрС. Акцент делается на средства управления вычислительным пространством, которое является основным ресурсом шрС-машины, на распределение вычислений, а также на обусловленные этими концепциями расширения в системе типов языка.

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

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

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

Приложение 1 содержит описание языка С[], являющего подмнокеством шрС.

Приложение 2 содержит грамматику языка трС.

Приложения 3 и 4 содержат примеры кода, генерируемого компшятором по описаниям топологий сетей различной сложности.

7. ЗАКЛЮЧЕНИЕ

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

• Совместно с д.ф.-м.н. Ластовецким создана языковая модель абстрактной параллельной неоднородной вычислительной системы.

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

• Разработаны принципы эффективной реализации средств описания абстрактной параллельной вычислительной системы языка трС.

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

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

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

• Разработана и реализована не имеющая аналогов интерактивная компонента системы программирования трС - трС Adviser, облегчающая написание семантически сложных программ на языке шрС.

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

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

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

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

Высокая эффективность программирования задач для неоднородных вычислительных сетей была подтверждена путем создания ряда приложений из разных областей науки. В настоящее время запланирована разработка прикладного программного обеспечения на языке шрС для нужд Института биоорганической химии РАН и НИИ Атомных Реакторов (г.Димитровград).

Практическая значимость языка шрС была высоко оценена специалистами по разработке программного обеспечения для высокопроизводительных вычислительных систем. Язык трС выбран в качестве объектного языка в совместном проекте CD AC (Centre for Development of Advanced Computing, Bangalore, India) и ИСП РАН по созданию распараллеливающего компилятора с языка Fortran 90 для системы PARAM-10000.

Язык трС и его система программирования находятся в процессе постоянного развития и совершенствования. Новые расширения языка и его компилятора связаны как с развитием модели неоднородной вычислительной системы, так и с переносом системы программирования на новые платформы. Так, планируется перенос системы программирования трС в среду Windows NT и Windows 2000.

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

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

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

1. H.El-Rewini, and T.Lewis, Introduction To Distributed Computing. Manning Publications Co., 1997.

2. High Performance Fortran Forum, High Performance Fortran Language Specification, version 1.1. Rice University, Houston TX, November 10, 1994.

3. Extending High Performance Fortan for the Support of Unstructured Computations, Centro Svizzero di Calcolo Scientifico, Technical Report 94-08

4. P.Banerjee, J.A.Chandy, etc., "An Overview of the PARADIGM Compiler for Distributed-Memory Multicomputer", IEEE Computer, v.28,10, Oct. 1995.

5. G.Fox, S.Hiranandani, K.Kennedy, C.Koelbel, U.Kremer, C.-W.Tseng, and M.-Y.Wu, Fortran D Language Specification. Center for Research on Parallel Computation, Rice University, Houston, TX, October 1993.

6. B.Chapman, P.Mehrotra, and H.Zima, "Programming in Vienna Fortran", Scientific Programming, 1(1), 1992, pp.31-50.

7. The CM Fortran Programming Language. CM-5 Technical Summary, Thinking Machines Corporation, November 1992, pp. 61-67.

8. The C* Programming Language. CM-5 Technical Summary, Thinking Machines Corporation, November 1992, pp. 69-75.

9. P.J.Hatcher, and M.J.Quinn, Data-Parallel Programming on MIMD Computers. The MIT Press, Cambridge, MA, 1991.

10. M.Philippsen, and W.Tichy, "Modula-2* and its compilation", First International Conference of the Austrian Center for Parallel Computation, Salzburg, Austria, 1991.

11. T.Braeunl, "Parallaxis-III: A Language for Structured Data-Parallel Programming", IPVR, Univ.Stuttgart, Germany, Sept. 11,1994.

12. I.Foster, and K.M.Chandy, "Fortran M: A language for modular parallel programming", Journal of Parallel and Distributed Computing, 26(1), 1995, pp. 24-35.

13. K.M.Chandy, and C.Kesselman. CC++: A Declarative Concurrent Object Oriented Programming Language. Technical Report CS-TR-92-01, California Institute of Technology, Pasadena, CA, 1992.

14. G.E.Blennoch, "NESL: A Nested Data-Parallel Language (version 3.1)", Technical Report CMU-CS-95-170, 1995.

15. B.Alexander, D.Engelhardt, and A.Wendeborn, "An Overview of the Adl Language Project", University of Adelaide, Australia, Sept.3 1997.

16. P.Brinch Hansen, "The Programming Language SuperPascal", School of Computer and Information Science, Syracuse University, Syracuse, USA, 1993.

17. Split-C, http://www.cs.berkely.edu/projects/parallel/castle/split-c

18. A.Geist, A.Beguelin, J.Dongarra, W Jiang, R.Manchek, V.Sunderam, PVM: Parallel Virtual Machine, Users' Guide and Tutorial for Networked Parallel Computing, MIT Press, Cambridge, MA, 1994.

19. The Nexus Multithreaded Runtime System, http://www.mcs.anl.gov/nexus/index.html.

20. R.Calkin, R.Hempel, H.-C.Hoppe, and P.Wypior, "Portable Programming with the Parmacs message-passing library", Parallel Computing, Special issue on message-passing interface.

21. R.Butler and E.Lusk, "Monitors, Messages, and Clusters: the p4 Parallel Programming System", Journal of Parallel Computing, 20:547-568, 1994.

22. W.D.Gropp, and B.Smith. Chameleon Parallel Programming Tools Users Manual. Technical Report ANL-93/23, Argonne National Laboratory, March 1993.

23. CHIMP Version 1.0 Interface. Edinburgh Parallel Computing Centre, University of Edinburgh, May 1992.

24. BSP: The bulk Synchronous Parallel Model, http://www.bsp-worldwide.org.

25. A.Skjellum, and A.Leung, "Zipcode: A Portable Multicomputer Communication Library", Proceedings of the 5-th Distributed Memory Concurrent Computing Conference, IEEE Computer Society Press, 1990, pp. 767-776.

26. I.Foster, J.Geisler, C.Kesselman, and S.Tuecke, "Managing Multiple Communication Methods in High-Performance Networked Computing Systems", Journal of Parallel and Distributed Computing.

27. G.Fagg, and J.Dongarra, "PVMPI: Inter-operation and Co-ordination of MPI-1 Applications across multiple systems and MPI implementations", http://www.cs.utk.edu/~fagg/mpiglue/.

28. Message Passing Interface Forum, MPI: A Message-passing Interface Standard, version 1.1, June 1995.

29. LAM/MPI Parallel Computing, http://www.osc.edu/lam.html.

30. MPICH A Portable Implementation of MPI, http://www.mcs.anl.gov/mpi/mpich/.

31. MPI-2: Extensions to the Message-Passing Interface, http://www.mcs.anl.gov/mpi/.

32. Dome: Distributed Object Migration Environment, http://www.cs.cmu.edu/~Dome/.

33. С.С.Гайсарян, А.Л.Ластовецкий, И.Н.Ледовских, Д.А.Халецкий, "Расширение ANSI С для векторных и суперскалярных компьютеров", Программирование, 1995, N1, сс. 26-36.

34. А.Л.Ластовецкий, И.Н.Ледовских, "Анализ структурной эквивалентности описаний в компиляторе с языка С.", Вопросы кибернетики: Приложения системного программирования, Научный совет по комплексной проблеме "Кибернетика" РАН, Москва, 1995, сс. 6-19.

35. A.Lastovetsky, "mpC a Multi-Paradigm Programming Language for Massively Parallel Computers", ACM SIGPLAN Notices, 31(2), February 1996, pp.13-20.

36. 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.

37. D.Arapov, V.Ivannikov, A.Kalinov, A.Lastovetsky, and I.Ledovskih, "Managing Processes with Network Objects and Their Translation", Proceedings of the EUROMICRO'98 International Conference, IEEE Computer Society, August 25-27,1998, Vasteras, Sweden

38. D.Arapov, A.Kalinov, A.Lastovetsky, and I.Ledovskih, "A Language Approach to High Performance Computing on Heterogeneous Networks", accepted for publication in Parallel and Distributed Computing Practices.