Принципы организации параллельных вычислений при трансляции последовательных языков высокого уровня на ЭВМ М-10

Л.Г. Натансон

Рассмотрены методы распараллеливания, которые были применены при построении оптимизирующих трансляторов Алгола-60 и Фортрана для векторной ЭВМ М-10.

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

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

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

Первый заключается в том, что исходный язык программирования никаким изменениям, отражающим архитектуру ЭВМ, не подвергается, и вся работа по организации векторных вычислений (по распараллеливанию) переносится на транслятор. Именно такой путь был применен при построении транслятора Алгола-60 [2], разработка которого была завершена в 1974 г.; впоследствии транслятор был подвергнут определенным переделкам, направленным главным образом на использование сервисных возможностей операционной среды. Распараллеливание рассматривалось как специфическое для векторных ЭВМ оптимизирующее преобразование, основанное на принципах, изложенных в [3; 4]. Транслятор “собственноручно” отыскивал поддающиеся распараллеливанию фрагменты программ и формировал для них эффективный машинный код, обеспечивающий одновременную загрузку нескольких векторных процессоров.

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

Транслятор Фортрана разрабатывался в два этапа. Первый был завершен в январе 1983 г. [5], когда к М-10 была подключена версия языка, являющаяся некоторым расширением Фортрана-Дубна. При реализации той версии предусматривалась лишь классическая, машинно-независимая оптимизация. В июле 1983 г. была завершена вторая и окончательная версия, которая по сравнению с первой представляла собой существенное расширение языка в части организации параллельных вычислений. Таким образом, входной язык был расширен дополнительными возможностями, позволяющими проводить эффективную обработку векторных данных, и в отличие от системы работы с Алголом-60 задача распознавания распараллеливаемых фрагментов была полностью переложена на программиста. Встретив требующую распараллеливания конструкцию, транслятор, разумеется, не “доверяет” человеку полностью, а проводит определенный контроль, который может привести к сообщениям о недопустимости распараллеливания. Если же при проведении контроля перед транслятором встает алгоритмически неразрешимая задача, то он “верит человеку на слово” и формирует объектный код, отвечающий параллельной работе процессоров. Но программист может ошибиться, посчитав распараллеливаемой ту конструкцию, которую можно выполнять только последовательно, что может привести к неправильным результатам вычислений. Чтобы подстраховать его, существует вспомогательный режим трансляции, где все указания о распараллеливаемости игнорируются, т. е. программисту предоставляется возможность тестировать свои программы, сравнивая результаты вычислений, полученные в обоих режимах.

Итак, второй подход к организации параллельных вычислений характеризуется тем, что эта задача частично переносится на человека. Очевидно, что система человек — машина может достигнуть в этом случае максимальной производительности. Тем не менее “старые” программы, написанные для традиционных ЭВМ, остаются по-прежнему малоэффективными, и оптимальный путь находится, вероятно, на стыке указанных подходов.

При втором подходе наибольший интерес представляет, конечно, выбор языковых конструкций, которые должны быть ориентированы на векторные вычисления, но, с другой стороны, не должны нарушать общей идеологии исходного языка программирования. Авторам транслятора Фортрана пришлось пойти по паллиативному пути. Он заключается в том, что акцент делается на исполняемые операторы Фортрана, а новые структуры данных, отражающие векторную природу вычислений, при этом не определяются. Получившаяся “векторная версия” языка в значительно меньшей степени отличается от исходной по сравнению с более ранними похожими разработками (см., например, [6]). Основное нововведение — это явное указание на возможность распараллеливания фрагмента программы. Применительно к векторным ЭВМ фрагментом такого рода является цикл, каждое повторение которого соответствует не единственному значению (скалярного) параметра цикла, а нескольким таким значениям одновременно (т. е. вектору, состоящему из последовательных значений параметра) [3; 4]. Такой цикл записывается в виде

PARDO L = L1, L2
<тело цикла>
ENDPAR,

где L — параметр цикла; L1 и L2 — начальное и конечное значения параметра.

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

Операторы, встречающиеся в теле цикла, должны в основном удовлетворять ограничениям, указанным в [4]. Некоторые из них контролируются транслятором, некоторые — нет. В теле цикла допускаются пять разновидностей операторов.

1. Обычные операторы присваивания, в левой части которых находится либо простая переменная, либо переменная с индексами, которая определяет вектор элементов массива, соответствующий вектору значений параметра. Простая переменная, встречающаяся в указанном контексте, должна быть описана с помощью так называемого оператора LONG. Это декларативный оператор, где перечисляются простые переменные, с которыми при распределении памяти сопоставляется не единственная ячейка памяти, а вектор, например, LONG PI, Р2, РЗ. Простые переменные, описанные в операторе LONG, могут использоваться только внутри цикла PARDO, а при выходе из цикла их значения не определены (так же, как и значение параметра).

2. Так называемые операторы “свертки”, отражающие введенное в [4] понятие “накопителя”. Это определенная разновидность операторов присваивания, в левой части которых допустима либо обычная простая переменная, которой соответствует единственная ячейка памяти, либо переменная с индексами, определяющая элемент массива, не зависящий от значения параметра. Представление об операторе свертки, формирующем (скалярное) значение накопителя, дает такая запись, как

S+=A(L)

(А — имя массива), которая соответствует записи обычного оператора присваивания

S = S + A(L).

3. Условные конструкции, к которым относятся обычный логический оператор IF и конструкция IF-THEN-ELSE, синтаксис которой почти полностью заимствован из Фортрана-77 [7]. Выполнение операторов внутри условных конструкций происходит под маской, формируемой при обработке условия [4]. (Маскирование определяет участие тех и только тех векторных процессоров, работа которых в данный момент действительно необходима.) Отметим, что конструкция IF-THEN-ELSE допустима и вне цикла PARDO; там она имеет практически ту же семантику, что в Фортране-77, что повышает общий уровень языка.

4. Операторы CALL и вызовы внешних функций, обращающиеся к специальным процедурам, написанным на Автокоде М-10 с учетом возможностей ЭВМ при параллельных вычислениях. Среди таких процедур выделен набор векторных стандартных функций и типовых подпрограмм [8].

5. Циклы DO, т. е. обычные непараллельные циклы, содержащие перечисленные выше операторы и удовлетворяющие некоторым дополнительным условиям. Отметим, что циклы PARDO, вложенные в цикл PARDO, недопустимы, что вытекает из принципов архитектуры М-10 (машина векторная, а не матричная).

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

Заключение. Итак, “векторная версия” языка содержит четыре нововведения: оператор PARDO, оператор свертки, конструкцию IF-THEN-ELSE и декларативный оператор LONG. Разумеется, использование возможностей М-10 при параллельных вычислениях не ограничивается циклами PARDO; типичным примером является сложение комплексных чисел, выполняемое с помощью единственной арифметической операции. В заключение отметим, что, по имеющимся сейчас данным, программы на Фортране превышают по быстродействию соответствующие программы на Алголе-60 в 3-6 раз. Это, конечно, объясняется не только изменением подхода к организации параллельных вычислений, но и опытом, накопленным разработчиками трансляторов, и, как следствие, возросшим классом системного программирования.

Литература

1. Карцев М. А. Вычислительная машина М-10. — Доклады АН СССР, т. 245, 1979, № 2.
2. Беляков М. И., Натансон  Л. Г. Метаязык, схема трансляции и синтаксический анализ в системе построения высокоэффективных трансляторов. — Программирование, l975, № 1.
3. Lamроrt L. The parallel execution of DO loops. — Communs ACM, v. 17, 1974, № 2.
4. Беляков М. И., Натансон  Л. Г. Распараллеливание циклов и другие оптимизирующие преобразования транслируемых программ. — Программирование, 1975, № 4.
5. Варченко В. С., Натансон  Л. Г., Туманов  А. Е. Реализация транслятора языка Фортран на ЭВМ М-10. — Вопросы радиоэлектроники, сер. ЭВТ, 1983, вып. 6.
6. Programming languages and compilers for parallel and vector machines. — SIGPLAN Notices, v. 10, 1975, № 3.
7. Катцан Г. Язык Фортран-77. — М.: Мир, 1982.
8. Шавловская С. А. Библиотека стандартных программ для многопроцессорной машины. — Вопросы радиоэлектроники, сер. ЭВТ, 1970, вып. 9.

Статья опубликована в сборнике “Вопросы радиоэлектроники”, серия “Электронная вычислительная техника”, вып. 9, 1984 г., стр. 3.