авторефераты диссертаций БЕСПЛАТНАЯ БИБЛИОТЕКА РОССИИ

КОНФЕРЕНЦИИ, КНИГИ, ПОСОБИЯ, НАУЧНЫЕ ИЗДАНИЯ

<< ГЛАВНАЯ
АГРОИНЖЕНЕРИЯ
АСТРОНОМИЯ
БЕЗОПАСНОСТЬ
БИОЛОГИЯ
ЗЕМЛЯ
ИНФОРМАТИКА
ИСКУССТВОВЕДЕНИЕ
ИСТОРИЯ
КУЛЬТУРОЛОГИЯ
МАШИНОСТРОЕНИЕ
МЕДИЦИНА
МЕТАЛЛУРГИЯ
МЕХАНИКА
ПЕДАГОГИКА
ПОЛИТИКА
ПРИБОРОСТРОЕНИЕ
ПРОДОВОЛЬСТВИЕ
ПСИХОЛОГИЯ
РАДИОТЕХНИКА
СЕЛЬСКОЕ ХОЗЯЙСТВО
СОЦИОЛОГИЯ
СТРОИТЕЛЬСТВО
ТЕХНИЧЕСКИЕ НАУКИ
ТРАНСПОРТ
ФАРМАЦЕВТИКА
ФИЗИКА
ФИЗИОЛОГИЯ
ФИЛОЛОГИЯ
ФИЛОСОФИЯ
ХИМИЯ
ЭКОНОМИКА
ЭЛЕКТРОТЕХНИКА
ЭНЕРГЕТИКА
ЮРИСПРУДЕНЦИЯ
ЯЗЫКОЗНАНИЕ
РАЗНОЕ
КОНТАКТЫ


Pages:     | 1 |   ...   | 3 | 4 || 6 | 7 |

«ПРОГРАММНЫЕ СРЕДСТВА И МАТЕМАТИЧЕСКИЕ ОСНОВЫ ИНФОРМАТИКИ Серия “КОНСТРУИРОВАНИЕ И ОПТИМИЗАЦИЯ ПРОГРАММ” ...»

-- [ Страница 5 ] --

5.1. Цель Цель, которую преследовали Вольф и Лэм, состояла в построении мно жеств полностью переставляемых гнезд циклов. Полностью переставляе мые гнезда являются основой для всех техник мозаичного размещения [51, 59, 60]. Мозаичное размещение используется для выявления среднезерни стого и крупнозернистого параллелизма. Более того, множество d полно стью переставляемых циклов может быть переписано в виде одного после довательного цикла и d-1 параллельных циклов. Следовательно, этот метод также может быть использован для выявления мелкозернистого паралле лизма.

Алгоритм Вольфа—Лэма строит максимальное множество самых внеш них полностью переставляемых5 циклов. Затем он рекурсивно просматрива ет оставшиеся размерности и зависимости, не задействованные этими цик i-й и i+1-й циклы являются переставляемыми в том и только том случае, когда i-я и i+1-я компоненты любого вектора расстояния глубины i неотрицательны.

Касьянов В. Н., Мирзуитова И. Л. Алгоритмы распараллеливания циклов лами. Версия, представленная в [60], строит множество циклов с помощью анализа более простых случаев, полагаясь на эвристики для гнезд циклов с глубиной 6 и более. В оставшейся части данного раздела мы рассмотрим этот алгоритм с теоретической точки зрения и дадим его наиболее общий вариант.

5.2. Теоретическое обоснование Унимодулярные преобразования обладают двумя важными свойствами:

линейностью и обратимостью. Для данного унимодулярного преобразова ния T свойство линейности позволяет с легкостью определить, является ли T допустимым. Действительно, T является допустимым в том и только том случае, когда Td l 0 для всех ненулевых векторов расстояния d. Обрати мость позволяет легко переписывать код, так как преобразование представ ляет собой простое изменение базиса в Zn.

В общем случае справедливость выражения Td l 0 не может быть про верена для всех векторов расстояния, число которых может быть слишком большим. Следовательно, нужно попытаться гарантировать, что Td l 0 для всех ненулевых векторов направления, с обычными математическими со глашениями, в Z {} (Z {+, -}). В дальнейшем мы ограничимся рас смотрением только ненулевых векторов направления, известных как лекси кографически положительные векторы направлений.

Обозначим через t(1),..., t(n) строки T. Пусть Г — замыкание конуса, порождаемого всеми векторами направления. Для вектора направления d:

Td l 0 kd, 1 kd n | i, 1 i kd, t(i).d = 0 и t(kd).d 0.

Это означает, что зависимости, представленные вектором d, порождают ся в цикле уровня kd. Если kd = 1 для всех векторов расстояния d, тогда все зависимости порождаются в первом цикле, а все внутренние циклы являют ся циклами DOALL. Тогда t(1) называется вектором синхронизации или разделяющей гиперплоскостью. Такой вектор синхронизации существует только в том случае, когда Г является направленным, т. е. тогда и только тогда, когда Г не содержит линейного пространства. Это также эквивалент но тому факту, что конус Г+ = {y | x Г, y.x 0} 162 Программные средства и математические основы информатики является полномерным. Построение T по n линейно независимым векторам из Г+ позволяет преобразовывать циклы в n полностью переставляемых циклов.

Понятие вектора синхронизации лежит в основе метода гиперплоскостей и его вариаций (см., например, [37, 55]), особенно полезных при выявлении мелкозернистого параллелизма, тогда как понятие полностью переставляе мых циклов является базисом всех техник мозаичного размещения. Как бы ло сказано ранее, обе формулировки эквивалентны для случая Г+.

Когда конус Г не является направленным, Г+ имеет размерность r, 1 r n, r = n - s, где s — размерность пространства линейности Г. При наличии r линейно независимых векторов в Г+, можно преобразовать гнездо циклов таким образом, что r самых внешних циклов будут полностью переставляе мыми. Затем можно рекурсивно применять ту же технику для преобразова ния n-r внутренних циклов, рассматривая векторы направления, не задейст вованные еще ни одним из r внешних циклов, т. е. рассматривая векторы направления, входящие в пространство линейности Г. Это основная идея алгоритма Вольфа—Лэма [60], представленного ниже.

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

проц WOLF-LAM (D, E : множество векторов)= Определить Г как замыкание конуса, генерируемого векторами на правления из D;

Определить Г+ = {y | x Г, y.x 0}, и пусть r — размерность Г+;

Дополнить E до множества E' r линейно независимых векторов из Г+ (по построению E Г+);

Пусть D' — подмножество D, определяемое по правилу: d D v E', v.d = 0 (то есть D' = D E' = D lin.space(Г));

Вызвать WOLF-LAM(D', E') все.

Поскольку процесс, описываемый данной процедурой, может дать в итоге неунимодулярную матрицу, построение желаемой унимодулярной Касьянов В. Н., Мирзуитова И. Л. Алгоритмы распараллеливания циклов матрицы T может быть проведено выполнением следующей последователь ности шагов.

1. Взяв в качестве D множество векторов направления, а в качестве E пустое множество, вызвать WOLF-LAM(D, E).

2. Построить невырожденную матрицу T1, первые строки которой яв ляются векторами из построенного множества E (в том же порядке).

Пусть T2 = pT1-1, где p выбирается таким образом, что T2 будет цело численной матрицей.

3. Вычислить левую эрмитову форму T2, T2 = QH, где H — неотрица тельная нижняя треугольная матрица, а Q — унимодулярная матри ца.

Q-1 есть искомая матрица преобразования (поскольку pQ-1D = 4.

HT1D).

Проиллюстрируем работу описанного алгоритма на следующем гнезде циклов.

Пример 6.

DO i = 1, n DO j = 1, n DO k = 1, n a(i, j, k) = a(i-1, j+i, k) + a(i, j, k-1) + a(i, j-1, k+1) ENDDO ENDDO ENDDO Множество векторов расстояния для данного гнезда равно D = {(1,, 0), (0, 0, 1), (0, 1, -1)} (см. рис. 6).

164 Программные средства и математические основы информатики Рис. 6. СГЗ программы примера Нетрудно видеть, что для примера 6 пространство линейности Г(D) яв ляется двумерным (оно порождается векторами (0, 1, 0) и (0, 0, 1)). Следо вательно, Г+(D) является одномерным и порождается E1 = {(1, 0, 0)}. Тогда D' = {(0, 0, 1), (0, 1, –1)}, и Г(D') является направленным. E1 пополняется двумя векторами из Г+(D'), например, E2 = {(0, 1, 0}, (0, 1, 1)}. В данном конкретном случае матрица преобразования, имеющая строки E1 и E2, уже является унимодулярной и соответствует простому перекосу цикла. Для выявления DOALL-циклов мы выбираем первый вектор E2 в относительно внутренней части Г+, например, E2 = {(0,2,1), (0,1,0)}. В терминах преобра зований циклов это сводится к перекосу цикла k со множителем 2 и после дующей перестановке циклов j и k:

DOSEQ i = 1, n DOSEQ k = 3, 3n DOALL j = max(1, (k-n)/2), min (n, (k-1)/2) a(i, j, k-2j)=a(i-1, j+i, k-2j)+a(i, j, k-2j-1)+a(i, j-1, k-2j+1) ENDDO ENDDO ENDDO 5.4. Сильные и слабые стороны алгоритма Вольф и Лэм показали оптимальность этой методологии (теорема B.6 из [60]): «алгоритм, который обнаруживает максимальный крупнозернистый параллелизм, а затем рекурсивно вызывает себя на внутренних циклах, про изводит параллелизм максимально возможной степени». Однако и в этом случае оптимальность следует понимать в контексте используемого анали за: а именно — наличие векторов расстояния при полном отсутствии какой Касьянов В. Н., Мирзуитова И. Л. Алгоритмы распараллеливания циклов либо информации о структуре графа зависимостей. Поэтому корректной является следующая формулировка данного утверждения [36].

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

Таким образом, как и для алгоритма Аллена—Кеннеди, частичная опти мальность алгоритма Вольфа—Лэма в общем случае имеет причиной не методологию алгоритма, но слабость его входного представления: то, что структура СГЗ не принимается во внимание, может повлечь потерю парал лелизма. Например, в противоположность алгоритму Аллена—Кеннеди, алгоритм Вольфа—Лэма не находит параллелизма в примере 3 (СГЗ кото рого приведен на рис. 7) из-за типичной структуры векторов направления (1,, 0), (0, 1, ), (0, 0, 1).

Рис. 7. СГЗ с векторами направлений для программы из примера 6. АЛГОРИТМ ДАРТЕ—ВИВЬЕНА В этом разделе рассматривается третий распараллеливающий алгоритм, который принимает на входе многогранные сокращенные графы зависимо стей. Вначале мы изложим некоторую мотивацию необходимости нового алгоритма (разд. 6.1), а затем приведем пошаговое описание алгоритма и обсудим его работу на примерах.

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

Это побуждает к поискам нового алгоритма, объединяющего достоинства алгоритмов Вольфа—Лэма и Аллена—Кеннеди. Чтобы достичь такой цели, можно представить себе комбинацию алгоритмов, которая одновременно использует структуру СГЗ и структуру векторов направления, осуществляя следующую последовательность шагов.

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

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

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

Такая стратегия позволяет выявить большее количество параллелизма, комбинируя унимодулярные преобразования и распределение циклов. Од нако она не является оптимальной, что демонстрирует пример 7. Действи тельно, в программе этого примера вышеописанное сочетание алгоритмов Аллена—Кеннеди и Вольфа—Лэма позволяет определить только одну сту пень параллелизма, так как на второй фазе СГЗ остается сильно связным.

Результат не лучше, чем у базового алгоритма Аллена—Кеннеди. Однако можно обнаружить две ступени параллелизма, назначив S1(i, j, k) на момент времени 4i – 2k и S2(i, j, k) на момент времени 4i – 2k + 3.

Пример 7.

DO i = 1, n DO j = 1, n DO k = 1, n S1: a(i, j, k) = b(i-1, j+i, k) + b(i, j, k+2) S2: b(i, j, k) = a(i, j-i, k+j) + a(i, j, k-1) ENDDO ENDDO ENDDO Касьянов В. Н., Мирзуитова И. Л. Алгоритмы распараллеливания циклов Рис. 8. СГЗ программы примера Нам хотелось иметь простой распараллеливающий алгоритм, который бы находил некоторый параллелизм хотя бы во всех тех случаях, в которых это может сделать алгоритм Аллена—Кеннеди или алгоритм Вольфа— Лэма. Естественным решением было бы применить сначала алгоритм Алле на—Кеннеди, а затем алгоритм Вольфа—Лэма (или комбинацию обоих ал горитмов) и выдать наилучший результат. Но такой наивный подход не бу дет достаточно мощным, поскольку он использует либо структуру графа зависимостей, либо векторы направления, но не в состоянии воспользовать ся знанием обоих структур одновременно. К примеру, предложенная ком бинация двух алгоритмов могла бы использовать структуру графа зависи мостей до или после вычисления максимального множества полностью пе реставляемых циклов, но никогда — во время этого вычисления. Утвержда ется [36], что и графовая структура, и векторы направления должны быть использованы одновременно — по той причине, что ключевым понятием при планировании СГЗ является не конус, генерируемый векторами направ ления (т. е. весами дуг СГЗ), а конус, генерируемый весами циклов СГЗ.

Все вышеописанное является мотивацией создания многомерного пла нирующего алгоритма, представленного ниже. Его можно рассматривать как комбинацию унимодулярных преобразований, распределения цикла и метода сдвига индексов. Это алгоритм, объединяющий достоинства алго ритмов Аллена—Кеннеди и Вольфа—Лэма, был предложен Дарте и Вивье ном [42]. Прежде чем переходить к его описанию, поясним выбор пред ставления зависимостей, используемый алгоритмом.

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

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

Пример 8.

DO i = 1, n DO j = 1, n S : a(i, j) = a(j, i) + a(i, j-1) ENDDO ENDDO S(i, j) S(i, j+1) для ni1, nj1, flow S(i, j) S(j, i) для nji1, flow S(j, i) S(i, j) для nij1, anti Рис. 9. Точные отношения зависимостей для гнезда циклов из примера а б Рис. 10. СГЗ для фрагмента программы примера 8, в котором дуги помечены уров нями зависимостей (а) и векторами направления (б) Касьянов В. Н., Мирзуитова И. Л. Алгоритмы распараллеливания циклов Алгоритм Аллена—Кеннеди базируется на рассмотрении уровней зави симостей. В программе примера 8 уровни трех зависимостей равны соот ветственно 2, 1 и 1. Имеется цикл зависимостей на уровне 1 и на уровне 2.

Таким образом, параллелизм не обнаруживается.

Алгоритм Вольфа—Лэма рассматривает векторы зависимостей. В про грамме примера 8 векторы зависимостей выглядят как (0, 1), (+, –) и (+, –).

Во втором измерении «1» и «–« не позволяют обнаружить два полностью переставляемых цикла. Следовательно, код остается без изменения и парал лелизм не обнаруживается.

Для сравнения рассмотрим также результат применения алгоритма Фот рие, который будет описан в разд. 7. Алгоритм воспринимает в качестве входа точные зависимости и на выходе дает допустимый план T(i, j) = 2i + j – 3. Таким образом, алгоритм обнаруживает один уровень параллелизма.

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

DO j = 3, 3n DOPAR i = max (1, (j-n)/2), min (n, (j-1)/2) a(i, j-2i) = a(j-2i, i) + a(i, j-2i-1) ENDDO ENDDO Однако для гнезда циклов примера 8 точное представление зависимо стей вовсе не является необходимым условием для обнаружения паралле лизма. Действительно, можно заметить, что имеется униформная зависи мость u = (0, 1) и множество векторов расстояний {(j – i, i – j) = (j – i) (1, –1) | 1 j – i n – 1}, которое может быть приближено (сверху) множеством P = {(1, –1) + (1, –1) | 0}. P является многогранником с одной вершиной v = (1, –1) и одним лучом r = (1, -1). Предположим теперь, что мы ищем линей Количество неравенств и переменных связано с количеством граничных усло вий, которые определяют область допустимых значений каждого отношения зави симости.

170 Программные средства и математические основы информатики ный план T(i, j) = x1i + x2j. Пусть X = (x1, x2). Чтобы план T был допусти мым, нужен такой X, чтобы выполнялось Xd 1 для любого вектора зави симости d. Следовательно, X(0, 1) 1 и Xp 1 для всех p P. Последнее неравенство эквивалентно следующему: X(1, -1) + X(1, –1) 1 при 0, что эквивалентно X(1, –1) 1 и X(1, –1) 0, т. е. Xv 1 и Xr 0. Следова тельно, достаточно решить следующие три неравенства:

Xu 1 Xv 1 Xr 0, т.е.

0 0 X 1 X 1 X 1 что ведет, как у Фотрие, к X = (2, 1). Таким образом, в данном примере приближение зависимостей с помощью уровней или даже векторов направ ления не является достаточным для определения параллелизма. Однако с помощью приближенного представления зависимостей в виде многогран ника можно обнаружить тот же параллелизм, что и с помощью точного ана лиза зависимостей, но при этом решая более простое множество уравнений.

Особенно важна здесь «униформизация», которая позволяет нам перейти от неравенства на многограннике P к униформным неравенствам на v и r.

Благодаря ей исчезают аффинные ограничения, и нам нет необходимости использовать аффинную форму леммы Фаркаша, как в алгоритме Фотрие (см. разд. 7). Чтобы лучше понять принцип «униформизации», будем рас суждать в терминах путей зависимостей. Рассмотрим дугу e, ведущую из оператора S к оператору T и помеченную вектором расстояния p = v + r, как путь, который использует один раз «униформный» вектор зависимо сти v и раз «униформный» вектор зависимости r. Такой способ рассмот рения представлен на рис. 11, где введена новая вершина S', которая позво ляет моделировать и дугу нулевого веса, ведущую из S' обратно в началь ную вершину T. Принцип «униформизации» является основной идеей алго ритма распараллеливания циклов, описанного в данном разделе.

Касьянов В. Н., Мирзуитова И. Л. Алгоритмы распараллеливания циклов Рис. 11. Моделирование дуги, помеченной многогранником, с одной вершиной и одним лучом «Униформизуя» зависимости, мы фактически «униформизовали» гра ничные условия и свели исходную проблему планирования с аффинными граничными условиями к простой проблеме планирования, где все зависи мости являются униформными (u, v и r). Однако есть два фундаментальных различия между этой структурой и классической структурой униформного гнезда циклов.

• Униформные векторы зависимостей не обязательно являются лекси чески положительными (например, луч может быть равен (0, -1)).

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

• Ограничения, налагаемые на луч r, являются более слабыми, чем в классическом случае, поскольку вместо Xr 1 требуется, чтобы Xr 0. Это ослабление должно приниматься во внимание распараллели вающим алгоритмом.

6.3. Работа алгоритма: пример Рассмотрим пример, иллюстрирующий работу алгоритма. Будем счи тать, что в сокращенном графе зависимостей дуги помечены векторами на правления. Граф зависимостей, изображенный на рис. 12, был построен с помощью анализатора зависимостей Tiny [62].

172 Программные средства и математические основы информатики Пример 9.

DO i = 1, n DO j = 1, n DO k = 1, n a(i, j, k) = с(i, j, k-1) + b(i, j, k) = a(i-1, j+i, k) + b(i, j-1, k) c(i, j, k+1) = c(i, j, k) + b(i, j-1, k+i) + a(i, j-k, k+1) ENDDO ENDDO ENDDO Рис. 12. СГЗ программы примера Нетрудно убедиться, что алгоритмы Аллена—Кеннеди и Вольфа—Лэма не способны найти весь содержащийся в этой программе параллелизм: тре тий оператор кажется полностью последовательным. Однако алгоритм об наружения параллелизма, который будет представлен в следующем разделе, способен построить следующий многомерный план: (2i + 1, 2k) для первого оператора, (2i, j) для второго и (2i + 1, 2k + 3) для третьего. Этот план соот ветствует коду с явным параллелизмом, приведенному ниже (в котором, Касьянов В. Н., Мирзуитова И. Л. Алгоритмы распараллеливания циклов однако, не было проведено никаких модификаций наподобие отшелушива ния цикла с целью устранения операторов IF). Таким образом, для каждого оператора может быть обнаружен один уровень параллелизма.

DOSEQ i = 1, n DOSEQ j = 1, n DOPAR k = 1, j b(i, j, k) = a(i-1, j+i, k) + b(i, j-1, k) ENDDO ENDDO DOSEQ k = 1, n+ IF (k n) THEN DOPAR j = k, n a(i, j, k) = c(i, j, k-1) + ENDDO ENDIF IF (k 2) THEN DOPAR j = k-1, n c(i, j, k) = c(i, j, k-1) + b(i, j-1, k+i+1) + a(i, j-k+1, k) ENDDO ENDIF ENDDO ENDDO Этот код был сгенерирован из вышеприведенного плана с помощью процедуры “codegen” программы Omega Calculator7, поставляемого в ком плекте Petit [53]. Следует напомнить, что вышеприведенный код является «виртуальным» в том смысле, что алгоритм только выявляет скрытый па раллелизм. Реальный код не обязательно должен быть именно таким.

6.4. Шаг униформизации Вначале мы покажем, как МСГЗ (многогранные сокращенные графы за висимостей) могут быть изображены с помощью эквивалентной, но более простой в обращении структуры — униформных графов зависимостей, то есть графов, дуги которых помечены константными векторами зависимо Omega Calculator служит для вычисления зависимостей, проверки допустимо сти программных преобразований и преобразования программ заданным образом.

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

Чтобы избежать путаницы между вершинами графа зависимостей и вершинами многогранника зависимостей, мы будем называть первые узла ми, а вторые — вершинами. Будут использоваться также следующие согла шения. Исходный МСГЗ, описывающий зависимости в распараллеливаемом коде, называется исходным графом и обозначается как G0 = (V, E). Уни формный СГЗ, эквивалентный G0 и построенный с помощью алгоритма трансляции, называется униформным графом или трансляцией G0 и обо значается как Gu = (W, F).

Алгоритм трансляции строит Gu путем сканирования всех дуг G0. Он на чинает с Gu = (W, F) = (V, ), и для каждой дуги e из E добавляет в Gu но вые узлы и новые дуги в зависимости от вида многогранника P(e). Будем называть вновь созданные узлы виртуальными узлами в отличие от реаль ных узлов, соответствующих узлам G0.

Пусть e — дуга из E. Обозначим через xe и ye соответственно начало и конец дуги e, т. е. узел, из которого e исходит, и узел, в который она захо дит. Это определение обобщается до путей: начало (соответственно конец) пути — это начало (соответственно конец) его первой (соответственно по следней) дуги.

Будем следовать нотациям, введенным в разделе 3.2:, и обознача ют количество вершин vi, лучей ri и линий li многогранника P(e).

Трансляцию осуществляет следующий алгоритм:

начало Пусть W = V и F = ;

для всех e: xe ye E цикл Добавить к W новый виртуальный узел ne;

Добавить к F дуг с весами v1, v2,..., v, соединяющих xe с ne;

Добавить к F петель, соединяющих ne, с весами r1, r2,..., r;

Добавить к F петель, соединяющих ne, с весами l1, l2,..., l;

Добавить к F петель, соединяющих ne, с весами -l1, -l2,..., -l;

Добавить к F дугу с нулевым весом, ведущую из ne в ye.

все конец.

Вернемся к программе примера 9. Граф МСГЗ данной программы изо бражен на рис. 12. Рис. 13 представляет связанный с ней униформный граф зависимостей. Граф имеет три виртуальных узла, соответствующих символу Касьянов В. Н., Мирзуитова И. Л. Алгоритмы распараллеливания циклов «+» и двум символам «–» в исходных векторах направления;

это узлы, по меченные символами S'1, S'2 и S'3.

Рис. 13. Транслированный униформный сокращенный граф зависимостей 6.5. Шаг планирования Шаг планирования принимает на входе транслированный граф зависи мостей Gu и строит многомерный план для каждого реального узла, т. е. для каждого узла Gu, который соответствует узлу G0. Gu предполагается сильно связным (в противном случае нужно вызывать алгоритм для каждой сильно связной компоненты Gu).

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

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

Шаг планирования описывается нижеприведенным рекурсивным алго ритмом. Первым вызовом является DARTE-VIVIEN(Gu, 1). Для каждого реального узла S из Gu алгоритм строит последовательность векторов X1S,..., XdSS и последовательность констант 1S,..., dSS, которые определяют допустимый многомерный план.

проц DARTE-VIVIEN(G: граф, k: целое)= 1. Построить G' — такой подграф G, который порожден всеми дуга ми, принадлежащими по меньшей мере одному мультициклу нуле вого веса в G;

2. Добавить к G' все дуги, ведущие из реального узла xe к виртуаль ному узлу ye, и все петли, соединяющие ye, если дуга e = (xe, ye) уже входит в G';

3. Выбрать вектор X и константу S для каждого узла S из G таким образом, чтобы выполнялось два условия:

e = (xe,ye)G' или xe — виртуальный узел X(e) + ye xe e = (xe, ye) G' или xe — реальный узел X(e) + ye xe 1, и для всех реальных узлов S из G положить kS = S и XkS = X.

4. если G' — пустой граф или содержит только виртуальные узлы то возврат все;

5. если G' — сильно связный граф и содержит реальные узлы то G является невычислимым (а исходный МСГЗ G0 — несогласованным);

возврат все;

.

Провести декомпозицию G' на сильно связные компоненты Gi;

для всех Gi, имеющих реальные узлы, цикл DARTE-VIVIEN(Gi, k+1) все.

все.

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

Касьянов В. Н., Мирзуитова И. Л. Алгоритмы распараллеливания циклов 1. Шаг (2) является необходимым только для МСГЗ общего вида:

его можно опустить, к примеру, для СГЗ, помеченных векто рами направления (см. [44] для более подробного изложения).

В этом случае решение простой линейной программы может заменить одновременно шаг (1) и шаг (3).

2. На шаге (3) мы сознательно не указываем, каким образом вы бираются вектор X и константы, что позволяет применять различные критерии выбора. Например, можно выбрать мак симальное множество линейно независимых векторов X, если целью является построение полностью переставляемых циклов (см. [46]).

Вернемся к примеру 9. Рассмотрим униформный граф зависимостей на рис. 13. Имеются два элементарных цикла с весами (1, 0, 1) и (0, 1, 1) и пять петель с весами (0, 0, 1), (0, 0, –1), (0, 1, 0) (дважды) и (0, –1, 0). Следова тельно, все дуги (кроме дуг, принадлежащих только к циклу с весом (1, 0, 1)) принадлежат к мультициклу нулевого веса. Подграф G' показан на рис. 14.

Рис. 14. Подграф мультициклов нулевого веса для примера 178 Программные средства и математические основы информатики Ограничения, следующие из дуг подграфа G', устанавливают, что X = (x, y, z) должен быть ортогонален к весам всех циклов G'. Следовательно, y = z = 0. Наконец, рассматривая остальные ограничения, мы находим реше ние: X = (2, 0, 0), S1 = S3 = 1 и S2 = 0. В G' остаются четыре сильно связ ных компоненты, две из которых не рассматриваются, так как имеют только виртуальные узлы. Две оставшиеся компоненты не содержат мультициклов нулевого веса. Сильно связная компонента с единственным узлом S2 может быть спланирована с вектором X = (0, 1, 0), тогда как исследование второй сильно связной компоненты приводит к одному из возможных решений: X = (0, 0, 2), S1 = 0 и S3 = 3.

Суммируя все результаты, мы находим уже рассмотренные в разд. 6.3.

двумерные планы: (2i, j) для S2, (2i + 1, 2k) для S1 и (2i + 1, 2k + 3) для S3.

6.6. Схематические пояснения Граф Gu не всегда соответствует СГЗ гнезда циклов, так как его векторы зависимостей не обязательно лексически неотрицательны. Фактически, если забыть о том, что некоторые узлы виртуальны, то Gu — это сокращенный граф зависимостей Системы Униформных Рекуррентных Уравнений, вве денной Карпом, Миллером и Виноградом в [52]. Карп, Миллер и Виноград исследовали проблему вычислимости таких систем. Они показали, что ее вычислимость связана с проблемой нахождения циклов нулевого веса в ее СГЗ G, что может быть проделано посредством рекурсивной декомпозиции графа, основанной на нахождении мультициклов нулевого веса. Ключевой структурой их алгоритма является G', подграф G, генерируемый дугами, принадлежащими к мультициклу нулевого веса.

G' может быть успешно построен с помощью решения простой линей ной программы (программа примера 7 или двойственная ей программа примера 8). Это решение позволяет построить алгоритм распараллеливания, принцип которого двойственен алгоритму Карпа, Миллера и Винограда:

min ve : q 0, v 0, w 0, q + v = 1 + w, Bq = 0, (4) e max ze : z 0, 0 ze 1, Xw(e) + ye xe ze, (5) e где w(e) — вектор зависимостей, связанный с дугой e, B = [CW]t, C — мат рица связей, а W — матрица векторов зависимостей.

Касьянов В. Н., Мирзуитова И. Л. Алгоритмы распараллеливания циклов Если не вдаваться в детали, X — это n-мерный вектор, имеется одна пе ременная для каждой вершины СГЗ и одна переменная z для каждой дуги СГЗ. Дугами G' (или G\G') являются дуги e = (xe, ye), для которых ze = 0 (со ответственно ze = 1) в оптимальном решении двойственной программы 8, и, эквивалентно этому, для которых ve = 0 (соответственно ve = 1) в изначаль ной программе 7. Суммируя неравенства Xw(e) + ye - xe ze в цикле C в G, мы находим, что Xw(C) = 0, если C — цикл из G', и Xw(C) l(C) 0 в про тивном случае (l(C) — количество дуг C, не принадлежащих G').

Чтобы увидеть связь с алгоритмом Вольфа—Лэма, можно рассмотреть конус Г, генерируемый весами циклов (а не весами дуг);

тогда G' — под граф, веса циклов которого генерируют пространство линейности Г, а X — вектор в относительно внутренней части Г+. Однако нет необходимости для построения G' реально строить Г. Это просто одно из любопытных свойств программ примеров 7 и 8.

Мы обрисовали основные идеи алгоритма Дарте—Вивьена [44]. Требу ются некоторые технические модификации для распознавания виртуальных и реальных узлов и для учета природы дуг (помеченных вершинами, лучами или линиями многогранника зависимостей). Отсылаем читателя к работе [42] за полным изложением алгоритма.

6.7. Сильные и слабые стороны алгоритма Теперь, когда у нас есть многомерный план T, мы можем доказать его оптимальность в терминах степени параллелизма. Можно показать [41, 42], что для каждого оператора S (то есть для каждого узла G0) количество эк земпляров S, исполняемых последовательно в результате применения T, имеет тот же порядок, что и количество экземпляров S, являющихся врож денно последовательными в силу действия зависимостей.

Теорема 3. Планирующий алгоритм является почти оптимальным, если область итерации содержит полномерный куб размера (N) (соответст венно содержится в кубе размерности O(N)) и если d — глубина (количест во вложенных рекурсивных вызовов) алгоритма, то время ожидания плана равно O(Nd) и длина самого длинного пути зависимостей равна (Nd). Более точно, после генерации кода каждый оператор S окружен в точности dS последовательными циклами, и эти циклы считаются врожденно последо вательными также после анализа зависимостей.

Этот алгоритм также является оптимальным относительно анализа зави симостей. Рассмотрим следующий пример.

180 Программные средства и математические основы информатики Пример 10.

DO i = 1, n DO j = 1, n S1: a(i, j) = b(i-1, j+i) + a(i, j-1) S2: b(i, j) = a(i-1, j-i) + b(i, j-1) ENDDO ENDDO Рис. 15. СГЗ программы примера Если зависимости описываются с помощью векторов расстояния, СГЗ имеет две автозависимости (0, 1) и две дуги, помеченные многогранниками, обе имеющие по одной вершине и одному лучу — (0, 1) и (0, –1), соответ ственно (см. рис. 15). Следовательно, существует мультицикл нулевого ве са. Далее, две реальных вершины принадлежат к G'. Таким образом, глуби на алгоритма Дарте—Вивьена равна 2, и никакого параллелизма не обнару живается.

Однако вычисление итерации (i, j) первым (вторым) оператором на шагу 2i + j (соответственно i + j) приводит к допустимому плану, который обна руживает одну степень параллелизма8. Алгоритм Дарте—Вивьена не спосо бен найти параллелизм в этом примере, так как аппроксимация зависимо стей уже потеряла весь параллелизм.

Используемая здесь нами техника нахождения параллельных циклов за ключается в поиске многомерных планов, линейные части которых (векто Планы (3/2)i + j + 1/2 и (1/2)i + j минимизируют время ожидания, но напи сание кода становится более сложным.

Касьянов В. Н., Мирзуитова И. Л. Алгоритмы распараллеливания циклов ры X) могут быть разными для разных операторов, даже если они принад лежат к одной и той же сильно связной компоненте. Это является основой алгоритма Фотрие [47], математической базой которого является аффинная форма леммы Фаркаша. Однако теорема 3 показывает, что нет необходимо сти искать различные линейные части (построение которых будет более дорогим и приведет к усложнению процесса переписывания) в заданной сильно связной компоненте текущего подграфа G', если зависимости заданы с помощью векторов расстояния. С другой стороны, пример 10 показывает, что такое усовершенствование может быть полезным только тогда, когда доступен более точный анализ зависимостей.

7. АЛГОРИТМ ФОТРИЕ В работе [47] Пол Фотрие предложил алгоритм планирования статиче ских управляющих программ с аффинными зависимостями. Этот алгоритм использует точный анализ зависимостей, который всегда является осущест вимым для таких типов программ [45]. В этом его отличие от трех ранее рассмотренных алгоритмов (Аллена—Кеннеди, Вольфа—Лэма, Дарте— Вивьена), которые работают с теми или другими аппроксимациями зависи мостей.

Алгоритм Фотрие принимает на входе сокращенный граф зависимостей G, в котором дуга e: Si Sj помечена множеством пар (I, J) таких, что Sj(J) зависит от Si(I). Далее он рекурсивно строит многомерный аффинный план для каждого оператора гнезда циклов.

проц FEAUTRIER(G : граф) = Провести декомпозицию G на сильно связные компоненты Gi и то пологически отсортировать их.

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

Построить множество G'i незадействованных дуг;

если G'i то FEAUTRIER(G'i) все все все 182 Программные средства и математические основы информатики Данный алгоритм похож на алгоритм Дарте—Вивьена по своей структу ре и по выдаваемому результату, а также тем, что оба алгоритма использу ют линейные программы для построения аффинных планов. Приведем ос новные свойства, связанные со сравнением данных двух алгоритмов (см.

[36]).

1. Алгоритм Дарте—Вивьена способен планировать программы, даже если точный анализ зависимостей не является осуществимым, но дан СГЗ с многогранником зависимостей. Алгоритм Фотрие способен обрабаты вать только статические управляющие программы с аффинными зависи мостями. В этом смысле первый алгоритм является более мощным. Од нако укажет на попытки обобщить подход, реализованный в алгоритме Фотрие, путем ослабления ограничений на вход за счет использования анализа потока данных на нечетких массивах (Fuzzy Array Dataflow Analysis) [33].

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

Однако согласно теории, этот подход будет менее естественным и менее мощным.

3. Алгоритм Дарте—Вивьена основан на решении линейных программ, по добных тем, что решает алгоритм Фотрие. Единственное (но фундамен тальное) различие состоит в том, что первый ищет менее общие аффинные преобразования. Следовательно, на статических управляющих программах с аффинными зависимостями, алгоритм Фотрие всегда находит больше параллелизма, чем алгоритм Дарте—Вивьена (см. пример 10). Однако, не смотря на это различие, результат оптимальности для алгоритма Дарте— Вивьена дает некоторые указания на случаи оптимальности для Фотрие, которые были впервые введены как «жадные эвристики».

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

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

Дарте и др. [40] предложили расширение алгоритма Дарте—Вивьена, Касьянов В. Н., Мирзуитова И. Л. Алгоритмы распараллеливания циклов которое представляет собой простое обобщение Вольфа—Лэма. Лим и Лэм [57] предложили расширение алгоритма Фотрие, которое находит максимальные множества полностью переставляемых циклов, миними зируя при этом количество синхронизаций, необходимых в распаралле ленном коде.

6. Алгоритм Дарте—Вивьена производит настолько регулярные планы, насколько это возможно, чтобы получить возможно более простой код.

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

В работе [36] приводятся результаты небольшого сравнительного исследования алгоритмов, которое проводилось на четырех примерах.

Как и ожидалось авторами, в этих исследованиях сложность алгоритма Дарте—Вивьена была намного ниже, чем у алгоритма Фотрие. Более удивительным оказался тот факт, что оба алгоритма дали один и тот же результат на всех четырех рассмотренных примерах. Разумеется, для получения окончательного заключения о сравнительных характеристи ках алгоритмов данного исследования явно не достаточно: необходимо сравнительное исследование алгоритмов на существенно большем числе реальных программ.

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

DOPAR i = 1, n/ a(i) = 1 + a(n-i) DO i = 1, n ENDDO a(i) = 1 + a(n-i) DOPAR i = n/2 + 1, n ENDDO a(i) = 1 + a(n-i) ENDDO Рис. 16. Пример исходного (слева) и распараллеленного (справа) кода 184 Программные средства и математические основы информатики 8. ЗАКЛЮЧЕНИЕ В статье рассмотрены основные существующие алгоритмы распаралле ливания циклов — одного из наиболее важных реструктурирующих преоб разований. Суммируя их свойства, следует отметить следующее: алгоритм Аллена—Кеннеди является оптимальным для представления зависимостей в виде уровней, а алгоритм Вольфа—Лэма — для представления зависимо стей в виде векторов направления (но для гнезда циклов с единственным оператором). Ни один из двух алгоритмов не охватывает другой, поскольку каждый использует информацию, которая не может быть использована вто рым (графовая структура для первого алгоритма, векторы направления — для второго). Однако оба алгоритма охватываются алгоритмом Дарте— Вивьена, который является оптимальным для любого многогранного пред ставления векторов расстояния. Алгоритм Фотрие охватывает алгоритм Дарте—Вивьена в случаях, когда зависимости могут быть представлены как аффинные, но вопрос об его оптимальности остается открытым.

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

СПИСОК ЛИТЕРАТУРЫ 1. Булышева Л.А. Методы и средства оптимизации вычислений для процессоров с VLIW-архитектурой. — Новосибирск, 1993. — (Препр. / РАН. Сиб.отд-ние. ВЦ;

N 976).

2. Вальковский В. А. Распараллеливание алгоритмов и программ. Структурный подход. — М.: Радио и связь, 1989.

3. Векторизация программ: теория, методы, реализация: Сб. статей / Под ред. Г.Д.

Чинина. — М.: Мир, 1991.

4. Воеводин В. В. Математические основы параллельных вычислений. — М.: МГУ, 1991.

5. Воеводин Вл. В. Теория и практика исследования параллелизма последователь ных программ // Программирование. — 1992. — N 3. — С. 38–54.

6. Глушков В.М., Капитонова Ю.В., Летичевский А.А. Алгебра алгоритмов и ди намическое распараллеливание последовательных программ // Кибернетика. — 1982. — N 5. — С. 4–10.

Касьянов В. Н., Мирзуитова И. Л. Алгоритмы распараллеливания циклов 7. Дорошенко А.Е. Математические модели и методы организации высокопроизво дительных параллельных вычислений. — Киев: Наукова думка, 2000.

8. Дорошенко А.Е. О преобразованиях циклических операторов к параллельному виду // Кибернетика. — 1984. — N 4. — С. 22–28.

9. Евстигнеев В.А., Касьянов В.Н. Оптимизирующие преобразования в распаралле ливающих компиляторах // Программирование. — 1996. — N 6. — С. 12–26.

10. Евстигнеев В.А., Мирзуитова И.Л. Анализ циклов: выбор кандидатов на распа раллеливание. — Новосибирск, 1999. — (Препр. / ИСИ СО РАН;

N 58).

11. Евстигнеев В. Анализ зависимостей: состояние проблемы // Системная инфор матика. — Новосибирск: Наука, 2000. — Вып. 7. — С.112–173.

12. Иванников В.П., Гайсарян С.С. Особенности систем программирования для век торно-конвейерной ЭВМ // Кибернетика и вычислительная техника. — М.: Нау ка, 1986. — Вып. 2. — С. 3–17.

13. Касьянов В.Н., Евстигнеев В.А. Графы в программировании: обработка, визуа лизация и применение. — СПб.: БХВ-Петербург, 2003.

14. Касьянов В.Н. Оптимизация программ // Прикладная информатика. — М.: Ста тистика, 1983. — Вып. 2. — С. 38–76.

15. Касьянов В.Н. Оптимизирующие преобразования программ. — М.: Наука, 1988.

16. Касьянов В.Н. Трансформационный подход к конструированию и оптимизации программ // Смешанные вычисления и преобразование программ. — Новоси бирск, 1991. — С. 30–43.

17. Касьянов В.Н. Трансформационные методы и средства конструирования эффек тивных и надежных программ // Кибернетика и системный анализ. — 1993. — N 2. — C. 30–39.

18. Системное и математическое обеспечение многопроцессорного вычислительно го комплекса ЕС / Под ред. Ю.В. Капитоновой. — М.: ВВИА им. Н.Е. Жуковско го, 1985.

19. Трантенгерц Э. А. Программное обеспечение параллельных процессов. — М.:

Наука, 1987.

20. Французов Ю. А. Обзор методов распараллеливания кода и программной кон вейеризации // Программирование. — 1992. — N 3. — С. 16–37.

21. Черняев А.П. Системы программирования для высокопроизводительных ЭВМ.

— Т.3. Вычислительные науки. — М., 1990. — С. 1–141. — (Итоги науки и техн.

ВИНИТИ АН СССР).

22. Черняев А.П. Программные системы векторизации и распараллеливания Фор тран-программ для некоторых векторно-конвейерных ЭВМ (обзор) // Програм мирование. — 1991. — N 2. — С. 53–68.

23. Allan V.H., Jones R.B., Lee R.M., Allan S.J. Software pipelining // ACM Computing Surveys. — 1996. — Vol. 27, N 3. — P.367–432.

24. Allen J.R., Kennedy K. Automatic translation of Fortran programs to vector form // ACM Trans. Program Lang. Syst. — 1987. —Vol. 9, N 4. — P. 491–542.

186 Программные средства и математические основы информатики 25. Allen J.R., Kennedy K. PFC: a program to convert programs to parallel form. — Houston, 1982. — (Tech. Rep. / Dept. of Math. Sciences, Rice University;

MASC TR82-6).

26. Bacon D. F., Graham S. L., Sharp O. J. Compiler transformations for high performance computing // ACM Computing Surveys. — 1994. — Vol. 26, N 4. — P.345–420.

27. Banerjee U. A theory of loop permutations // Languages and Compilers for Paral lel Computing. — MIT Press, 1990. — P. 54–74.

28. Banerjee U. Data dependence in ordinary programs. — Urbana, 1976. — (Tech. Rep. / Univ. Ill., 76-837).

29. Banerjee U. Dependence analysis for supercomputing. —Norwell: Kluwer Academic Publishers, 1988.

30. Bernstein A. J. Analysis of programs for parallel processing. // IEEE Trans. on Elec tronic Computers. — 1966. — Vol. 15, N 5. — P. 757–763.

31. Bockle G. Exploitation of fine-grain parallelism. — Berlin: Springer-Verlag, 1995. — (Lect. Notes Comput. Sci.;

Vol. 942).

32. Callahan D. A Global Approach to Detection of Parallelism: PhD thes. — Dept. of Computer Science, Rice University. — Houston, 1987.

33. Collard J.-F., Barthou D., and Feautrier P. Fuzzy Array Dataflow Analysis // Proc. of 5th ACM SIGPLAN Symp. on Principles and practice of Parallel Programming. — Santa Barbara, CA, 1995.

34. Collard J.-F., Feautrier P., Risset T. Construction of DO loops from systems of affine constraints // Parallel Processing Letters. — 1995. — Vol. 5, N 3. — P. 421–436.

35. Collard J-F. Code generation in automatic parallelizers // Proc. Int. Conf. on Applica tion in Parallel and Distributed Computing. — North Holland, 1994. — P. 185–194.

36. Computer optimizations for scalable parallel systems: languages, compilation tech niques, and run time systems / Santosh Pande;

Dharma P. Agrawal (ed.). — Berlin:

Springer-Verlag, 2001. — (Lect. Notes Comput. Sci.;

Vol. 1808).

37. Darte A., Khachiyan L., Robert Y. Linear scheduling is nearly optimal // Parallel Processing Letters. — 1991. — Vol. 1, N 2. — P. 73–81.

38. Darte A., Robert Y. Affine-by-statement scheduling of uniform and affine loop nests over parametric domains // J. Parallel and Distributed Computing. — 1995. — Vol.

29. — P. 43–59.

39. Darte A., Robert Y. Mapping uniform loop nests onto distributed memory architec tures // Parallel Computing. — 1994. — Vol. 20. — P. 679–710.

40. Darte A., Silber J.-A., Vivien F. Combining retiming and scheduling techniques for loop parallelization and loop tiling. — ENS-Lyon, 1996. — (Tech. Rep. / LIP;

96-34).

41. Darte A., Vivien F. Automatic parallelization based on multi-dimensional scheduling.

— Lyon, 1994. — (Tech. Rep. / LIP;

94-24).

42. Darte A., Vivien F. On the optimality of Allen and Kennedy's algorithm for parallel ism extraction in nested loops //. J. of Parallel Algorithms and Application. — 1996.

— (Special issue on Optimizing Compilers for Parallel Languages).

Касьянов В. Н., Мирзуитова И. Л. Алгоритмы распараллеливания циклов 43. Darte A., Vivien F. Optimal fine and medium grain parallelism detection in polyhedral reduced dependence graphs. — Lyon, 1996. — (Tech. Rep. / LIP;

96-06).

44. Darte A., Vivien F. Optimal fine and medium grain parallelism detection in polyhedral reduced dependence graphs // Proc. of PACT'96. — Boston: IEEE Computer Society Press, 1996.

45. Feautrier P. Dataflow analysis of array and scalar references // Int. J. Parallel Pro gramming. — 1991. — Vol. 20, N 1. — P. 23–51.

46. Feautrier P. Some efficient solutions to the affine scheduling problem, part I, one dimensional time // Int. J. Parallel Programming. — 1992. — Vol. 21, N 5. — P. 313–348.

47. Feautrier P. Some efficient solutions to the affine scheduling problem, part II, multi dimensional time // Int. J. Parallel Programming. — 1992. — Vol. 21, N 6. — P. 389–420.

48. Goff G., Kennedy K., Tseng C.-W. Practical dependence testing // Proc. of the SIG PLAN Conf. on Programming Language Design and Implementation. — SIGPLAN Not. — 1991. —Vol. 26, N 6. — P. 15–29.

49. Irigoin F., Jouvelot P., Triolet R. Semantical interprocedural parallelization: an over view of the PIPS project // Proc. of the 1991 ACM Internat. Conf. on Supercomputing.

—Cologne, 1991.

50. Irigoin F., Triolet R. Computing dependence direction vectors and dependence cones with linear systems. — Fontainebleau, 1987. — (Tech. Rep. / Ecole des Mines de Paris;

ENSMP-CAI-87-E94).

51. Irigoin F., Triolet R. Supernode partitioning // Proc. 15th Annual ACM Symp. Princi ples of Programming Languages. — San Diego: CA, 1988. — P. 319–329.

52. Karp R.M., Miller R.E., Winograd S. The organization of computations for uniform recurrence equations // J. of the ACM. — 1967. — Vol. 14, N 3. — P. 563–590.

53. Kelly W., Maslov V., Pugh W., Rosser E., Shpeisman T., and Wonnacott D. New user interface for Petit and other interfaces: user guide. — University of Maryland, 1995.

54. Kong X., Klappholz D., Psarris K. The I test: an improved dependence test for auto matic parallelization and vectorization // IEEE Trans. Par. Distr. Syst. — 1991. — Vol. 2, N 3. — P. 342–349.

55. Lamport L. The parallel execution of DO loops // Commun. of the ACM. — 1974. — Vol. 17, N 2. — P. 83–93.

56. Li Z. Array privatization for parallel execution of loops // Proc. of the 1992 Intern.

Conf. on Supercomputing. — 1992. — P. 313—322.

57. Lim A.W., Lam M.S. Maximizing parallelism and minimizing synchronization with affine partitions // Parallel Computing. — 1998. — Vol. 24, Iss. 3-4. — P. 445–475.


58. Pugh W. A practical algorithm for exact array dependence analysis // Commun. ACM.

— 1992. — Vol. 35, N 8. — P. 102–115.

59. Schreiber R., Dongarra J.J. Automatic blocking of nested loops. — Knoxville, 1990.

— (Tech. Rep. / The University of Tennessee;

90-38).

188 Программные средства и математические основы информатики 60. Wolf M.E., Lam M.S. A loop transformation theory and an algorithm to maximize parallelism // IEEE Trans. Parallel Distributed Systems. — 1991. — Vol. 2, N 4. — P.

452–471.

61. Wolfe M. High Performance Compilers For Parallel Computing. — Addison-Wesley Publishing Company, 1996.

62. Wolfe M. Optimizing Supercompilers for Supercomputers: PhD thes. — Dept. of Computer Science, University of Illinois. — Urbana-Champaign, 1982.

63. Wolfe M. Optimizing Supercompilers for Supercomputers. —Cambridge: MIT Press, 1989.

64. Wolfe M. TINY, a loop restructuring research tool. — Oregon Graduate Institute of Science and Technology, 1990.

65. Xue J. Automatic non-unimodular transformations of loop nests // Parallel Computing, 1994. — Vol. 20, N 5. — P.711–728.

66. Zima H. and Chapman B. Supercompilers for Parallel and Vector Computers. — ACM Press, 1990.

Е. В. Касьянова ЯЗЫК ПРОГРАММИРОВАНИЯ ZONNON ДЛЯ ПЛАТФОРМЫ.NET* ВВЕДЕНИЕ Данная статья описывает состояние пока еще не завершенной работы над языком, получившим название языка Zonnon [1]. Это новый универ сальный язык программирования в семействе языков Паскаль, Модула-2 и Оберон. Он сохраняет стремление к простоте, ясному синтаксису и незави симости концепций, а также уделяет внимание параллельности и легкости композиции и выражения. Унификация абстракций является стержнем про ектирования языка Zonnon, и она отражается в его концептуальной модели, основанной на модулях, объектах, определениях и реализациях. Язык Zon non содержит такие новые черты, как активность в объектах, основанный на межобъектном взаимодействии диалог, перегрузка операций и обработка исключительных ситуаций. Язык Zonnon специально разрабатывается как платформно-независимый язык.

Сам проект по разработке Zonnon языка возник как продолжение работы его авторов над языком Оберон (Oberon) в проекте 7, который был начат Microsoft Research в 1999 году с целью реализации значительного числа нестандартных языков программирования для платформы.NET [2]. Язык Оберон [3, 4] является хорошо известным преемником языков Паскаль (Pas cal) и Модула-2 (Modula-2). Мотивация авторов на продолжение работы по развитию языка Оберон связана со следующими двумя целями [5]:

a) экспериментально исследовать потенциальные возможности плат формы.NET в комбинации с новой технологией CCI интеграции компиляторов для проектирования языков;

b) реализовать для платформы.NET язык Zonnon, являющийся эво люцией языка Oberon для.NET.

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

* Работа выполнена при финансовой поддержке Министерства образования РФ (грант № Е02-1.0-42) и компании Майкрософт.

190 Программные средства и математические основы информатики • более развитая модульная структура языка;

• продвинутая и одновременно простая и ясная объектная модель;

• концепция активных объектов.

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

Язык Zonnon возник как естественный результат исследований, прово дившихся в течение последних нескольких лет в Федеральном Технологи ческом Институте (ETH) в Цюрихе. Непосредственными предшественника ми языка следует считать Active Oberon [6], реализованный как базовый язык ядра операционной системы BlueBottle, а также реализацию языка Oberon для платформы.NET (Oberon.NET). Язык Zonnon, имея ряд общих черт с указанными языками, вместе с тем, существенно отличается от них по ряду принципиальных моментов. Первая реализация Zonnon выполняет ся для платформы.NET. Кроме того, предполагается интеграция компиля тора в систему программирования Visual Studio.NET (в сотрудничестве с компанией Microsoft).

Статья начинается с изложения основных особенностей языка Zonnon (разд. 1). Разд. 2 посвящен вопросам отображения языка Zonnon на плат форму.NET. Разд. 3 содержит описание разрабатываемого компилятора с языка Zonnon для платформы.NET. Полный синтаксис языка Zonnon в его состоянии на август 2003 г. приведен в приложении.

1. ЯЗЫК ПРОГРАММИРОВАНИЯ ZONNON Язык Zonnon — это универсальный императивный язык программиро вания. Он характеризуется богатой и мощной, но сильно унифицированной объектной моделью, которая поддерживает разнообразные стили програм мирования, включая обычный стиль алгоритмов и структур данных, стили модульного и объектно-ориентированного программирования, а также мо дели вычислений, основанные на агентах (actor-based computing models).

Основными чертами объектной модели являются • унифицированная концепция абстракции, так называемое определение (definition), • соответствующее понятие реализации (implementation) по умолчанию, • комбинация обычных объекта и нити (thread), называемая активным объектом (active object), Касьянова Е. В. Язык программирования Zonnon для платформы.NET • конструкция модуля (module).

Нестрого говоря, определения относят к одной категории и унифициру ют общие абстракции суперкласса и интерфейса и в комбинации с механиз мом статического агрегирования реализаций заменяют концепции иерархии классов и единственного наследования. Активные объекты появляются вме сте с интегрированной нитью управления, которая описывает их поведение во время исполнения. Модули — это объекты с управляемой системой жиз ненным циклом. Кроме того, к языку добавлен оператор блока (block state ment) с факультативными модификаторами обработки в фигурных скобках и предложением перехвата исключений. Типичными модификаторами об работки являются ACTIVE (исполнять как отдельный поток), EXCLUSIVE (исполнять при взаимном исключении с соответствующей областью дейст вия объекта) и CONCURRENT (все операторы потенциально могут испол няться параллельно). Ниже данные новые языковые понятия будут проил люстрированы на небольшом наборе простых, но типичных примеров, при веденных авторами языка [3].

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

DEFINITION Store;

PROC Clear;

Add (s: Lib.Song);

END Store.

DEFINITION Player;

VAR cur: Lib.Song;

PROC Play (s: Lib.Song);

PROC Stop;

END Player.

Предположим, что, кроме того, имеется следующая реализация Store по умолчанию:

IMPLEMENTATION Store;

VAR rep: Lib.Song;

PROC Clear;

BEGIN rep := NIL 192 Программные средства и математические основы информатики END Clear;

PROC Add (s: Lib.Song);

BEGIN s.next := rep;

rep := s END Add;

BEGIN Clear END Store.

Тогда можно использовать следующее определение объекта патефона автомата:

OBJECT JukeBox IMPLEMENTS Player, Store;

IMPORT Store;

(* aggregate *) PROCEDURE Play (s: Lib.Song);

IMPLEMENTS Player.Play;

PROCEDURE Stop IMPLEMENTS Player.Stop;

..

END JukeBox.

Заметим, что реализация Store по умолчанию неявно агрегируется с пространством объектного состояния.

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

OBJECT Creature;

VAR X, Y, temp, hunger, kill: INTEGER;

PROCEDURE NEW (x, y, t: INTEGER);

BEGIN X := x;

Y := y;

temp := t;

hunger := END;

PROCEDURE SetTemp (dt: INTEGER);

BEGIN { EXCL } temp := temp + dt END SetTemp;

BEGIN { ACTIVE } LOOP AWAIT temp = minTemp;

Касьянова Е. В. Язык программирования Zonnon для платформы.NET WHILE hunger minHunger DO HuntStep(5, kill);

hunger := hunger — kill;

WHILE (kill 0) & (hunger 0) DO HuntStep(7, kill);

hunger := hunger — kill END;

RandStep(2) END;

RandStep(4);

hunger := hunger + END END Creature;

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

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


MODULE System.WindowManager;

IMPORT System.DisplayManager;

(* static import *) OBJECT { VALUE } Pos;

VAR X, Y, W, H: INTEGER END Pos;

DEFINITION Window;

VAR pos: Pos;

194 Программные средства и математические основы информатики PROCEDURE Draw ();

END Window;

VAR { PRIVATE } W, H: INTEGER;

bot: OBJ { Window };

PROCEDURE Open(this:OBJECT{Window},p:Pos);

BEGIN...

END Open;

PROCEDURE Change(this:OBJECT{Window},p:Pos);

BEGIN...

END Change;

BEGIN (* module initialization *) bot:=NIL;

W := System.DisplayManager.Width();

(* delegation *) H := System.DisplayManager.Height();

END WindowManager.

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

2. ОТОБРАЖЕНИЕ ЯЗЫКА ZONNON НА ПЛАТФОРМУ.NET Для любого языка необходимым условием возможности его реализации для.NET является существование отображения его конструкций на обще языковую исполняющую среду CLR (Common Language Runtime) [2]. В за висимости от парадигмы и модели, представленных языком, это может соз давать серьезную проблему. В данном случае императивного языка отобра жение исполнимой части на механизм исполнения CLR осуществляется непосредственным образом. Что нужно уточнить по существу — это спе цифицировать отображение определений, реализаций, активных объектов и модулей.

2.1. Отображение определений и реализаций Существуют различные опции отображения. Если переменные состоя ний в определениях отображаются в properties или virtual fields (пусть они существуют), полное пространство состояний может теоретически синтези роваться в реализующем объекте, но с некоторой потерей эффективности. В отличие от этого решение по отображению на C# (канонический язык для Касьянова Е. В. Язык программирования Zonnon для платформы.NET.NET), приведенное ниже, основывается на внутреннем подручном классе, который обеспечивает пространство агрегированных состояний.

DEFINITION D;

TYPE e = (a, b);

VAR x: T;

PROCEDURE f (t: T);

PROCEDURE g (): T;

END D;

IMPLEMENTATION D;

VAR y: T;

PROCEDURE f (t: T);

BEGIN x := t;

y := t END f;

END D;

отображается на interface D_i { T x { get;

set;

} void f(T t);

T g ();

} internal class D_b { private T x_b;

public enum e = (a, b);

public T x { get { return x_b };

set { x_b =... } } } public class D_c: D_b { T y;

void f(T t) { x_b = t;

y = t;

} } 2.2 Отображение активных объектов Отображение активных объектов в большей степени техническая, а не концептуальная проблема. Очевидно, что средства многопоточности плат формы.NET [6] должны служить в этом случае как образы активных конст рукций языка Zonnon. Ниже приводится «лобовое» решение для отображе ния оператора AWAIT. Оно основывается на массовом упоминании ожи даемых объектов в конце каждой критической секции. Авторы надеются, что в дальнейшем им удастся уточнить это решение.

196 Программные средства и математические основы информатики BEGIN { ACTIVE } S END Method void body() { S };

Field Thread thread;

NEW(x) x.thread = new Thread( new ThreadStart(body));

x.thread.Start() AWAIT c while !c { Monitor.Wait(this);

} BEGIN { EXCL } S END Monitor.Enter(this);

S;

Monitor.PulseAll(this);

Monitor.Exit(this);

2.3. Отображение модулей По существу модули просто отобразить на “статические” классы, кото рые представляют собой классы только со статическими членами. Ниже приведен набросок описания образа при отображении Zonnon-программ на платформу.NET для приведенного в разд. 1.3. менеджера окнами:

namespace System { namespace WindowManager { public struct Pos {... };

public class Window { public Pos pos;

public virtual Draw ();

} public sealed class WindowManager { private static int W, H;

Window bot;

public static Open (Window this;

Pos p) {... };

public static Change(Window this;

Pos p) {... } public static void WindowManager () {...

W := System.DisplayManager.DisplayManager.Width();

...

}} } Касьянова Е. В. Язык программирования Zonnon для платформы.NET 3. КОМПИЛЯТОР С ЯЗЫКА ZONNON ДЛЯ.NET Компилятор с языка Zonnon разработан для платформы.NET и работает наверху нее. Компилятор воспринимает Zonnon исходники (единицы ком пиляции) и производит обычный ассемблерный код платформы.NET, со держащий MSIL код и метаданные.

Имеются две версии компилятора: компилятор командной строки и компилятор, интегрированный в среду Visual Studio [7]. Компилятор реали зован на языке C# с использованием Common Compiler Infrastructure frame work (см. ниже), он спроектирован и разработан в Microsoft Research, г.

Редмонде [5].

3.1. Common Compiler Infrastructure Общекомпиляторная инфраструктура CCI (Common Compiler Infrastruc ture) — это множество ресурсов программирования (C# классы), обеспечи вающих поддержку для реализации компиляторов и других языковых инст рументов для платформы.NET. Эта поддержка не является полной: не под держаны некоторые аспекты функциональности компилятора, например, лексический и синтаксический анализ. Но очень важно то, что CCI поддер живает интеграцию в среду MS Visual Studio. Потенциально, возможно дос тичь полной интеграции компилятора со всеми компонентами VS, такими как редактор, отладчик, менеджер проектов, система онлайновой помощи и т.д.

Среда CCI могла бы рассматриваться как часть всей платформы.NET;

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

Промежуточное представление IR (Intermediate Representation) — это богатая иерархия C# классов, представляющих наиболее общие и типичные понятия современных языков программирования. IR иерархия основывается на архитектуре языка C#: ее классы отражают все C# и CLR понятия, такие как класс, метод, оператор, выражение и т.д. Это позволяет разработчику компилятора представлять напрямую подобные понятия его языка. В слу чае, когда язык имеет понятия или конструкции, которые не представлены множеством IR классов, есть возможность расширять исходную IR иерар хию добавлением новых IR классов. При этом должны быть добавлены также соответствующие трансформации — либо как расширения стандарт ных “визитёров” (см. ниже), либо в виде полностью нового визитёра.

198 Программные средства и математические основы информатики Трансфомеры (“визитёры”) представляют собой множество основан ных классов, выполняющих последовательные преобразования из IR в ас семблерный код платформы.NET. Имеются пять стандартных визитёров, предопределенных в CCI: наблюдатель (Looker), описатель (Declarer), ре шатель (Resolver), проверяющий (Checker), и нормализатор (Normalizer).

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

Все визитёры реализованы как классы, наследуемые от класса Standard Visitor из CCI. Допускается как расширение функциональности некоторого визитёра путем добавления методов, обрабатывающих специфические язы ковые конструкции, так и создание некоторого нового визитёра. CCI требу ет, чтобы все визитёры, используемые в компиляторе, наследовались (пря мо или косвенно) от класса StandardVisitor.

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

3.2. Архитектура компилятора с языка Zonnon Концептуально организация компилятора вполне традиционна: сканер (Scanner) осуществляет преобразование исходного текста в лексическую свертку, которая воспринимается парсером (Parser). Парсер осуществляет синтаксический анализ и строит абстрактное синтаксическое дерево (AST), используя для входной единицы компиляции классы CCI IR. Каждая вер шина AST является экземпляром класса IR. “Семантическая” часть компи лятора состоит из серии последовательных преобразований AST, построен ного парсером. Результатом таких трансформаций является ассемблерный код платформы.NET, который и является результатом работы компилятора.

Однако с архитектурной точки зрения компилятор с языка Zonnon отли чается от большинства “традиционных” компиляторов. Вместо использова ния технологии “черного ящика”, когда все алгоритмы компилятора и структуры данных инкапсулируются в компиляторе и не видны извне, ком Касьянова Е. В. Язык программирования Zonnon для платформы.NET пилятор с языка Zonnon, по существу, представляет собой открытый набор ресурсов. В частности, такие структуры данных, как лексическая свертка и дерево AST доступны (через специальный интерфейс) извне компилятора.

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

Такая архитектура поддерживается схемой CCI и обеспечивает глубо кую и естественную интеграцию компилятора в среду Visual Studio. Для того чтобы поддержать интеграцию, CCI содержит прототипные классы для сканера и парсера. Фактические реализации компонентов сканера и парсера компилятора с языка Zonnon представляют собой классы, наследуемые от этих прототипных классов.

Компилятор расширяет множество вершин IR путем добавления боль шого числа конкретных типов вершин для понятий Module, Definition, Im plementation, Object и для некоторых других конструкций языка Zonnon, которые не имеют прямых прототипов среди CCI-вершин. Дополнительные вершины обрабатываются расширенным визитёром-наблюдателем, который наследует стандарный класс Looker из CCI. Результат работы расширенного наблюдателя семантически эквивалентен дереву AST, содержащему только предопределенные типы CCI. Следовательно, расширенный наблюдатель реализует отображение, описанное в разд. 2.

ЗАКЛЮЧЕНИЕ В статье представлен язык программирования Zonnon, работа над кото рым ведется в Цюриховском институте информатики. Разрабатываемый язык задуман как дальнейшая эволюция хорошо известного языка Оберон, являющегося преемником языков Паскаль и Модула-2. Развивая язык Обе рон, исходя из современных потребностей в программировании, авторы стремятся сохранить такие важные черты Оберона и его предшественников, как компактность языка, ясность, недвусмысленность и ортогональность его основных понятий. Поэтому можно ожидать, что язык будет востребо ван теми учебными заведениями, которые в настоящее время используют Паскаль в качестве языка начального обучения программированию, но имеют желание перейти к более современному курсу программирования, охватывающему концепции языков программирования нового поколения, 200 Программные средства и математические основы информатики таких как Java и C#, но осуществить этот переход плавно, без резкого изме нения сложившегося стиля преподавания программирования.

СПИСОК ЛИТЕРАТУРЫ 1. Gutknecht J., Zueff E. Zonnon Language Report. — Zurich: Institute of Computer Systems ETH Zentrum, 2003.

2. Уоткинз Д., Хаммонд М., Эйбрамз Б. Программирование на платформе.NET. — М.: Вильямс, 2003.

3. Wirth N. The programming language Oberon // Software — Practice and Experience.

— 1988. — Vol. 18, N 6. — P. 671–690.

4. Wirth N. From Modula to Oberon // Software — Practice and Experience. — 1988. — Vol. 18, N 6. — P. 661– 670.

5. Gutknecht J., Zueff E. Zonnon Language Experiment, or How to Implement a Non Conventional Object Model for.NET // OOPSLA’02. — Seattle, Washington, 2002.

6. Просиз Дж. Программирование для.NET. — М.: Русская Редакция, 2003.

7. Джонсон Б., Скибо К., Янг М. Основы Microsoft Visual Studio.NET 2003. — М.:

Русская Редакция, 2003.

ПРИЛОЖЕНИЕ Ниже для описания синтаксиса языка Zennon используется Расширен ный Бекуса—Наура Формализм (Extended Backus—Naur Formalism, EBNF), который характеризуется следующими свойствами:

• альтернативы разделяются символом |;

• скобки [ и ] обозначают факультативность выражения в скобках;

• скобки { и } обозначают повторение (возможно 0 раз);

• скобки ( и ) используются для формирования групп элементов;

• нетерминальные символы начинаются с прописной буквы (например, Statement);

• терминальные символы либо начинаются со строчной буквы (напри мер, letter), либо записывается целиком строчными буквами (напри мер, BEGIN), или представляются в виде строк (например, ":=");

• комментарии начинаются с символа // и продолжаются до конца строки.

Касьянова Е. В. Язык программирования Zonnon для платформы.NET // Синтаксис языка Zonnon в EBNF // Версия от 8 августа // 1. Программа и программные единицы CompilationUnit = { ProgramUnit "." }.

ProgramUnit = ( Module | Definition | Implementation | Object ).

// 2. Модули Module = MODULE ModuleName [ ImplementationClause ] ";

" [ ImportDeclaration ] ModuleDeclarations ( BlockStatement | END ) SimpleName.

ModuleDeclarations = { SimpleDeclaration | NestedUnit ";

" } { ProcedureDeclaration | OperatorDeclaration } { ActivityDeclaration }.

NestedUnit = ( Definition | Implementation | Object ).

ImplementationClause = IMPLEMENTS DefinitionName { "," DefinitionName }.

ImportDeclaration = IMPORT Import { "," Import } ";

".

Import = ImportedName [ AS ident ].

ImportedName = ( ModuleName | DefinitionName | ImplementationName | Namespace Name ).

// 3. Определения Definition = DEFINITION DefinitionName [ RefinementClause ] ";

" [ ImportDeclaration ] DefinitionDeclarations END SimpleName.

RefinementClause = REFINES DefinitionName.

DefinitionDeclarations = { SimpleDeclaration } { ProcedureHeading | ActivitySignature ";

" }.

ActivitySignature = ACTIVITY ActivityName[ TYPE "{" ProtocolEBNF "}" [ EnumType] END Simple Name] ";

".

ProtocolEBNF = Спецификация протокола в EBNF на основе алфавита лексем.

// 4. Реализации Implementation = IMPLEMENTATION ImplementationName ";

" [ ImportDeclaration ] Declarations ( BlockStatement | END ) SimpleName.

// 5. Объекты Object = OBJECT [ ObjModifier ] ObjectName [ FormalParameters ] [ Implementation Clause ] ";

" [ ImportDeclaration ] Declarations { ActivityDeclaration } ( BlockStatement | END ) SimpleName.

202 Программные средства и математические основы информатики ObjModifier = "{" ident "}". // VALUE or REF;

VALUE by default ActivityDeclaration = ACTIVITY ActivityName [ ImplementationClause ] ";

" Declarations ( BlockStatement | END SimpleName ).

// 6. Объявления Declarations = { SimpleDeclaration } { ProcedureDeclaration }.

SimpleDeclaration = ( CONST [DeclModifier] { ConstantDeclaration ";

" } | TYPE [DeclModifier] { TypeDeclaration ";

" } | VAR [DeclModifier] { VariableDeclaration ";

" } ).

DeclModifier = "{" ident "}". // PUBLIC or PRIVATE or IMMUTABLE ConstantDeclaration = ident "=" ConstExpression.

ConstExpression = Expression.

TypeDeclaration = ident "=" Type.

VariableDeclaration = IdentList ":" Type.

// 7. Типы Type = ( TypeName [ Width ] | EnumType | ArrayType | ProcedureType | InterfaceType ).

Width = "{" ConstExpression "}".

ArrayType = ARRAY Length { "," Length } OF Type.

Length = ( Expression | "*" ).

EnumType = "(" IdentList ")".

ProcedureType = PROCEDURE [ ProcedureTypeFormals ].

ProcedureTypeFormals = "(" [ PTFSection { ";

" PTFSection } ] ")" [ ":" FormalType ].

PTFSection = [ VAR ] FormalType { "," FormalType }.

FormalType = { ARRAY OF } ( TypeName | InterfaceType ).

InterfaceType = OBJECT [ PostulatedInterface ].

PostulatedInterface = "{" DefinitionName { "," DefinitionName } "}".

// 8. Процедуры и знаки операций ProcedureDeclaration = ProcedureHeading [ ImplementationClause ] ";

" [ ProcedureBody ";

" ].

ProcedureHeading = PROCEDURE [ ProcModifiers ] ProcedureName [ FormalParameters ].

ProcModifiers = "{" ident { "," ident } "}". // PRIVATE, PUBLIC, SEALED ProcedureBody = Declarations BlockStatement SimpleName.

FormalParameters = "(" [ FPSection { ";

" FPSection } ] ")" [ ":" FormalType ].

FPSection = [ VAR ] ident { "," ident } ":" FormalType.

OperatorDeclaration = OPERATOR [ OpModifiers ] OpSymbol [ FormalParameters ] ";

" OperatorBody ";

".

OperatorBody = Declarations BlockStatement OpSymbol.

OpModifiers = "{" ident { "," ident } [ "," Priority ] "}".| "{" Priority "}".

Priority = ConstExpression.

OpSymbol = string. // Строка из 1, 2 или 3 символов из // ограниченного множества возможных символов Касьянова Е. В. Язык программирования Zonnon для платформы.NET // 9. Операторы StatementSequence = Statement { ";

" Statement }.

Statement = [ Assignment | ProcedureCall | IfStatement | CaseStatement | WhileStatement | RepeatStatement | LoopStatement | ForStatement | AWAIT Expression | EXIT | RETURN [ Expression ] | BlockStatement | Send | Receive ].

Assignment = Designator ":=" Expression.

ProcedureCall = Designator.

IfStatement = IF Expression THEN StatementSequence { ELSIF Expression THEN StatementSequence } [ ELSE StatementSequence ] END.

CaseStatement = CASE Expression OF Case { "|" Case } [ ELSE StatementSequence ] END.

Case = [ CaseLabel { "," CaseLabel } ":" StatementSequence ].

CaseLabel = ConstExpression [ ".." ConstExpression ].

WhileStatement = WHILE Expression DO StatementSequence END.

RepeatStatement = REPEAT StatementSequence UNTIL Expression.

LoopStatement = LOOP StatementSequence END.

ForStatement = FOR ident ":=" Expression TO Expression [ BY ConstExpression ] DO StatementSequence END.

BlockStatement = BEGIN [ BlockModifiers ] StatementSequence { ExceptionHandler } [ CommonExceptionHandler ] END.

BlockModifiers = "{" ident { "," ident } "}". // LOCKED, CONCURRENT, BARRIER ExceptionHandler = ON ExceptionName { "," ExceptionName } DO StatementSequence.

CommonExceptionHandler = ON EXCEPTION DO StatementSequence.

Send = [Designator] "!" Expression.

204 Программные средства и математические основы информатики Receive = [Designator] "?" Designator.

// 10. Выражения Expression = SimpleExpression [ ( "=" | "#" | "" | "=" | "" | "=" | IN ) SimpleExpression ] | Designator IMPLEMENTS DefinitionName | Designator IS TypeName.

SimpleExpression = [ "+"|"" ] Term { ( "+" | "" | OR ) Term }.



Pages:     | 1 |   ...   | 3 | 4 || 6 | 7 |
 





 
© 2013 www.libed.ru - «Бесплатная библиотека научно-практических конференций»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.