Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Разработка и реализация методов потокового анализа распараллеливаемых программ в Преобразователе программ СБкЗ_ПП



Оглавление

• Введение
• 1. Обзор литературы по теме «потоковый анализ программ в распараллеливающих и оптимизирующих компиляторах»
• 1.1 Распараллеливающие компиляторы
• 1.2 Представление программ
• 1.3 Задачи потокового анализа
• 1.4 Методы потокового анализа
• 1.5 Теоретические свойства методов
• 1.6 Опыт реального применения распараллеливающего компилятора
• 1.7 Средства реализации распараллеливающего компилятора
• 1.8 Компиляция с переменным набором оптимизирующих преобразований
• 1.9 .Выводы из обзора
• 2. Описание предметной области, решаемых задач и методов их решения
• 2.1 Описание предметной области
• 2.1.1 Граф алгоритма
• 2.1.2 Графы зависимостей и минимальные графы
• 2.1.3 Циклы ParDo и избыточные вычисления
• 2.1.4 Эквивалентные по вычислениям преобразования программ
• 2.2 Модель структурных программ
• 2.2.1 Термины объекта оптимизации
• 2.2.2 Описание терминов потокового анализа МСП
• 2.3 Постановка задач и методы их решения
• 2.3.1 Алгоритм добавления атрибутов ParDo
• 2.4 Представление методов потокового анализа программ
• 2.4.1 Абстрактный синтаксис языка методов потокового анализа программ
• 2.4.2 Операционная семантика языка методов потокового анализа программ
• 2.4.3 Расширение базы методов потокового анализа программ
• 3. Техническая часть
• 3.1 Назначение программного средства (ПС)
• 3.2 Архитектурно-контекстная диаграмма СБкЗ_ПП
• 3.2.1 Подсистема потокового анализа
• 3.3 Архитектурно-контекстная диаграмма ПС
• 3.4 Требования к программному средству
• 3.4.1 Общие функциональные требования
• 3.4.2 Конкретные функциональные требования
• 3.4.3 Требования к программному обеспечению
• 3.4.4 Требования к надежности
• 3.4.5 Профиль пользователя
• 3.4.6 Жизненный цикл программного средства
• 3.4.7 Требования к интерфейсу
• 3.5 Проектная документация
• 3.5.1 Архитектура программного средства
• 3.5.2 Спецификации функций
• 3.5.3 Описание реализации программного средства
• 3.5.4 Описание использования программного средства
• 4. Тестирование
• 4.1 Тестовые ситуации
• 4.2 Тесты
• 5. Экспериментальное изучение свойств программного средства
• 5.1 Цель экспериментов
• 5.2 Описание среды
• 5.3 План экспериментов
• Эксперимент №1
• Эксперимент №2
• Эксперимент №3
• 5.4 Результаты экспериментов
• 6. Доказательство того, что цели, сформулированные в задании, достигнуты. Обсуждение результатов дипломной работы
• Заключение
• Список литературы
• Приложение 1. Каталог реструктурирующих преобразований программ
• Вариант 1
• Вариант 2
• Приложение 2. Таблица соответствий понятий
• Приложение 3. Синтаксис языка методов потокового анализа (расширенная БНФ)

Введение

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

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

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

Основной задачей распараллеливающего компилятора является выявление скрытого (как правило) или явного (что редко) параллелизма. Такой анализ проводится не по самому тексту программы, а по ее модели.

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

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

Основной проблемой в сфере науки о преобразованиях программ является невозможность своевременно выполнять компьютерные эксперименты. Цель таких экспериментов - определить, насколько часто в реальных программах применимы те или иные преобразования и какой эффект дает их применение. Единственным средством проведения подобных экспериментов являются оптимизирующие компиляторы, например, GCC [14, 23], распространяемый бесплатно (по лицензии GPL), а из коммерческих разработок - компиляторы Intel C++ и Fortran [10]. Однако период времени, который обычно проходит от момента публикации описания нового преобразования до момента окончания реализации оптимизирующего компилятора, содержащего в своем наборе данное преобразование, настолько велик, что результаты компьютерных экспериментов с этим преобразованием оказываются мало актуальными. Кроме того, оптимизирующий компилятор обычно содержит большой набор преобразований и встроенную стратегию их применения. Поэтому получить результаты компьютерных экспериментов, относящихся к отдельному преобразованию (а не ко всему набору), весьма проблематично.

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

Несмотря на то, что проблема оптимизации программ для компьютеров с параллельной архитектурой существует уже более 20 лет, ее решение до сих пор нельзя считать удовлетворительным. Было предложено много различных подходов к оптимизации, но ни один из них не предполагает комплексного решения всего множества возникающих проблем. Более того, как показали недавние исследования Иллинойского университета, большинство методов потокового анализа распознают лишь 15% из всех пар зависимостей. На этом фоне успешной выглядит система V-Ray [15], практическое экспериментальное исследование которой показало превосходство (порой весьма значительное) над другими системами оптимизации. Однако V-Ray является лишь инструментом для выявления параллелизма, а анализ результатов, выбор и применение ОП и производятся вручную и неинтерактивно, как и постановка экспериментов. Существуют интерактивные системы, как, например, Acovea [18] для компилятора GCC, позволяющие в диалоговом режиме управлять стратегией оптимизации, то есть выбирать оптимизирующие преобразования. Однако расширение множества целевых языков или преобразований потребует серьезной модификации программы. Разрабатывается система, в которой библиотека преобразований выделяется в отдельную самостоятельную часть - открытая распараллеливающая система (ОРС) [17]. Система предназначена для автоматического распараллеливания программ с процедурных языков программирования (Фортран, Паскаль, Си) на параллельные компьютеры, ориентированные на математические вычисления.

Помимо этого предложен новый подход - управляемый пакет оптимизаций [5]. Это пара <P,M>, где Р - пакет оптимизаций, а М - менеджер пакета оптимизаций. Пакет оптимизаций представляет собой набор оптимизаций с одним и тем же объектом применения. Менеджер оптимизаций определяет порядок запуска оптимизаций пакета. Но данный проект пока не реализован до конца.

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

Целью данной дипломной работы является разработка и реализация подсистемы потокового анализа, управляемого знаниями, для распараллеливаемых программ в МСП как части СБкЗ_ПП.

Задачи дипломной работы:

· Разработка представления методов потокового анализа программ.

· Разработка требований к системе потокового анализа распараллеливаемых программ, управляемой базой знаний.

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

· Реализация системы потокового анализа распараллеливаемых программ, управляемой базой знаний.

Работа содержит следующие разделы:

· Глава 1 - обзор литературы, в котором проанализированы существующие системы распараллеливания с акцентом на подсистему ПА, рассмотрены методы и задачи ПА и различные внутренние представления программ.

· Глава 2 - постановку задачи и математическую модель;

· Глава 3 - техническую документацию программного средства;

· Глава 4 - описание тестирования программного средства;

· Глава 5 - Экспериментальное изучение свойств программного средства.

· Глава 6 - доказательство того, что цели дипломной работы, сформулированные в задании, достигнуты. Обсуждение результатов работы.

1. Обзор литературы по теме «потоковый анализ программ в распараллеливающих и оптимизирующих компиляторах»

1.1 Распараллеливающие компиляторы

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

Открытая распараллеливающая система (ОРС) [13] предназначена для автоматического распараллеливания программ с процедурных языков программирования (Фортран, Паскаль, Си) на параллельные компьютеры, ориентированные на математические вычисления.

В работе [10] рассматривается компилятор Intel.

Характеристики компиляторов Intel

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

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

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

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

· Поддержка системы команд SSE в процессорах Pentium III

· Автоматическая векторизацияиспользование команд SSE и SSE2, вставляемых автоматически компилятором

· Поддержка OpenMP для программирования на SMP-системахна кластере рекомендуется преимущественно пользоваться интерфейсом MPI; имеет смысл пользоваться библиотеками, распараллеленными для общей памяти.

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

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

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

· разработку системы V-Ray - средства анализа и преобразования программ;

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

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

Программные средства

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

Анализ программ при помощи V-Ray system осуществляется за несколько этапов. На первом этапе система определяет основные машинно-независимые свойства программ, а именно, потенциал параллелизма и локальность использования данных. Она позволяет определить влияние на качество программ четырех основных черт архитектуры компьютеров:

· параллельной обработки;

· векторной обработки;

· распределенной памяти;

· кеш-памяти.

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

Лежащая в основе системы V-Ray математическая технология гарантирует точность анализа для широкого класса программ. Это в частности означает, что если система не помечает некоторый цикл как параллельный, то действительно существует зависимость между итерациями цикла, и никакие другие средства (препроцессоры, анализаторы и т.д.) не смогут доказать ее отсутствие.

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

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

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

Микроанализ

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

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

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

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

Разные типы зависимостей. Система позволяет также построить граф зависимости по данным по всем 4 типам зависимостей или их комбинациям. Граф может быть построен с использованием графа алгоритма, построенного с помощью V-Ray технологии или без его использования, так как не всегда возможно построение графа алгоритма.

Макроанализ

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

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

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

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

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

Одной из ключевых компонент кластерного уровня суперкомпьютеров программы «СКИФ» является система автоматического распараллеливания вычислений - «Т-система» [1]. За годы выполнения программы «СКИФ» была реализована большая часть идей, заложенных основателями разработки Т-системы ещё в начале 80-х годов. Созданная версия Т-системы обладает открытой и расширяемой архитектурой, легко адаптируемой к стремительно меняющимся аппаратным платформам современных суперкомпьютеров; Т-приложения - приложения, написанные на входном языке программирования Т-системы Т++ - могут быть запущены на широком наборе программно-аппаратных конфигураций, в том числе, на различных мета-кластерных системах.

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

Работа выполнена в рамках программы «СКИФ» Союзного государства и при поддержке программы фундаментальных научных исследований ОИТВС РАН "Высокопроизводительные вычислительные системы, основанные на принципиально новых методах организации вычислительных процессов" и программы фундаментальных исследований Президиума РАН "Разработка фундаментальных основ создания научной распределенной информационно-вычислительной среды на основе технологий GRID"

За последние два года Т-система была существенно доработана с учетом опыта её внедрения и эксплуатации в ходе первых трёх лет программы «СКИФ». Современная версия Т-системы имеет ряд ярких отличительных черт, прежде всего, к ним относятся:

Минимальные отличия диалекта языка программирования Т++ - входного языка Т-системы - от базового языка С++. Различия так невелики, что поддерживается режим компиляции Т-программ без использования Т-системы - с генерацией последовательно исполняемого кода.

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

Динамическое связывание Т-приложений с используемой средой коммуникаций. Поддерживается пересылка данных по семи различным реализациям MPI и PVM.

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

· Конвертирование программ на Т++ в код на С++ с последующей компиляцией оптимизирующим компилятором, наилучшим для целевой платформы.

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

Архитектура среды исполнения Т-системы

Архитектура системы OpenTS построена по “микроядерному” принципу: так называемая исполняемая спецификация содержит в себе определение всех необходимых базовых сущностей (классов и шаблонов классов в терминологии C++), а также реализацию методов классов по-умолчанию. Глубокая проработка отдельных аспектов (реализуемая зачастую как переопределение методов) выполняется в отдельных модулях - расширениях Т-системы, которые, как и пользовательская программа, взаимодействуют с исполняемой спецификацией - микроядром.

Микроядро системы, называемое «Т-Суперструктурой», или функционально-ориентированная супервычислительная надстройка, структурно организована как три программных уровня S, M и Т:

S-уровень

Назначение S-уровня:

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

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

· Поддержать “суперпамять”, или распределенную, программно-управляемую память, доступную для всех существующих в распределенной супервычислительной среде потоков.

S-уровень может быть по-разному реализован для разных архитектур.

M-уровень

Назначение M-уровня:

· Поддержать мобильные потоки исполнения, объекты и ссылки

· Поддержать “копирование по необходимости” (Copy-On-Write) для данных суперпамяти.

· Поддержать операцию блокирования и освобождения мобильных объектов.

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

T-уровень

Назначение T-уровня:

· Реализовать понятия неготового значения и ссылки на неготовое значение

· Реализовать понятие Т-функции - мобильной функции, являющейся гранулой параллелизма.

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

Приложения и пользовательские библиотеки

К настоящему времени, с использованием современной версии Т-системы созданы и создаются ряд приложений, в том числе в ходе работ по мероприятиям программы «СКИФ». Вот некоторые из них:

· Инструментальное средство построения динамических интеллектуальных систем «Миракл» - в рамках выполнения мероприятия 20 программы «СКИФ»

· Система «MultiGen» - оценка биологической активности веществ

· Программа численного моделирования разрушения кильватерной волны

· Программа для численной оценки скорости приближения к глобальному аттрактору уравнений Навье-Стокса в задаче о двумерной каверне

· Программа моделирования фолдинга белков

· Программа синтеза радиолокационного изображения из голограммы РЛС космического базирования - в рамках выполнения работ по мероприятию 13 программы «СКИФ».

OpenTS и GRID-вычисления

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

Поддержка мета-кластерных реализаций MPI: MPICH-G2, IMPI, PACX-MPI

Обеспечение возможности пользовательского расширения стандартного алгоритма планирования - через механизмы расширения Т-системы.

Информационная система ТРАНСФОРМ (ИС ТРАНСФОРМ) [11] по преобразованиям программ создается для нужд лаборатории конструирования и оптимизации программ ИСИ СО РАН. Система предназначена для накопления и систематизации информации по преобразованиям программ и интеграции работы сотрудников лаборатории. Предполагается при помощи ИС ТРАНСФОРМ выпускать аналитические обзоры, обучать специалистов и внедрять преобразования программ в повседневную практику программирования.

· Гибкость создаваемой системы приобретает первостепенное значение, для достижения которой необходимо добиться наиболее точного отражения характерных черт предметной области (ПрО). Поскольку база данных является основой ИС, то требуемые возможности должны быть заложены в схему базы данных, что позволит в дальнейшем корректировать режимы использования ИС. Для ее решения как первый этап предлагается инфологическая схема, дающая представление об области преобразований программ (не учитывая ограничений, накладываемых конкретной СУБД) и призванная представить ясное, общедоступное описание БД для уточнения требований и облегчения взаимодействия с пользователями системы. В работе используется модель, называемая "объекты-связи". Она определяется в терминах: атрибут, объект, структурная связь, запросная связь. Под атрибутом понимается логически неделимый элемент структуры информации, характеризуемый множеством атомарных значений. Каждый атрибут идентифицируется именем. Объект инфологической схемы соответствует некоторой сущности реального мира, представляющей интерес для ПрО. Под Структурной связью понимается иерархическое отношение между объектами двух типов: владельцем и подчиненным. Для изображения информационных структур используются диаграммы. Запросная связь -- pro некоторая операция, предусматривающая в алгоритме процесса переход от экземпляров одних объектов, называемых исходными, к множеству экземпляров объекта, называемого конечным в запросной связи.

В работе [6] рассматривается проект системы Прогресс.

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

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

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

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

В качестве входных языков предполагается использовать Фортран-77, Модула-2, Си++, а также язык функционального программирования SISAL (версии 2.0 или SISAL-90). Предполагается, что языки расширены за счет средств аннотирования программ формализованными комментариями. Эти средства должны позволять пользователю управлять процессом преобразования программы (например, заданием дополнительной информации о свойствах программы), а системе -- комментировать результирующую программу информацией о процессе преобразования программы. Предусматривается возможность реализации в рамках расширенного языка преобразования последовательных программ в параллельные для параллельных версий входного языка (например, перевод программы на языке Фортран 77 в программу на языке Фортран 90).

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

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

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

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

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

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

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

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

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

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

Архивная подсистема (база данных) -- обеспечивает хранение информации о результатах применений систем преобразований.

Монитор -- обеспечивает диалог с пользователем и взаимодействие подсистем между собой.

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

В работе [7] был проведен обзор распараллеливающих систем. Некоторые из них:

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

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

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

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

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

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

Редактирование преобразований -- достаточно простая задача, хотя некоторые из них требуют аккуратного межпроцедурного анализа программ. Примерами таких преобразований могут служить приватизация массивов и превращение цикла в параллельный цикл. Редактирующее действие приватизации массивов состоит в перемещении объявлений данных из исходной позиции в заголовок цикла и создании параллельного цикла заменой DO на DOALL. Однако анализ приватизируемых массивов требует внимательного определения связей def-use, а превращение цикла в полностью параллельный цикл требует анализа зависимостей по данным.

Другие преобразования легче анализируются, но более утомительны для редактирования. Они могут быть кандидатами на поддержку со стороны ИС. Примерами служат преобразования сегментирование (strip mining) и сжатие цикла (loop coalescing).

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

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

PTOOL позволяет пользователю выбрать цикл в последовательной Фортран-программе и спросить, могут ли его итерации исполняться параллельно. Если ответ -- "нет", то PTOOL отображает все зависимости, препятствующие распараллеливанию. При обработке цикла PTOOL определяет множество переменных, которые могут быть объявлены частными (private) для каждой итерации. Это -- ключевая особенность в уменьшении числа зависимостей, показываемых пользователю, так как именно переменные, не относящиеся к частным, могут порождать зависимости. Кроме того, PTOOL может работать с вызовами внутри циклов.

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

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

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

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

Опыт эксплуатации PTOOL сразу после ее создания позволил выделить три категории недостатков.

PTOOL не полностью интерактивен,

PTOOL не может использоваться как отладчик.

PTOOL отображает слишком много ложных зависимостей.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Parascope и система D, разработанные в университете Раиса, используют для межпроцедурного анализа систему FIAT так же, как это сделано в FIAT/SUIF. Parascope обеспечивает проведение некоторых видов межпроцедурного анализа, таких как MOD/REF анализ, анализ массивных областей, основанный на дескрипторах регулярных секций, анализ смешивания, протягивание констант и анализ символьных величин. Система D построена в контексте Parascope и имеет целью трансляцию Фортран-Б-программ. Фортран D -- диалект Фортрана, подобный HPF -- требует проведения специальных видов анализа, таких как достигающая декомпозиция и перекрытие.

Система SUIF [25] (Stanford University Intermediate Format), разработанная в Стэнфордском университете, представляет собой инфраструктуру для исследований в области распараллеливающих и оптимизирующих компиляторов.

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

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

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

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

Строение и функции ядра. Ядро системы SUIF реализует три главные функции:

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

· обеспечивает функции для доступа и манипулирования с промежуточным представлением;

· структурирует интерфейс между проходами компилятора.

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

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

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

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

Для того чтобы система SUIF могла распараллеливать циклы, содержащие вызовы процедур, она дополняется системой FIAT, ориентированной на межпроцедурный анализ. Более точно, FIAT представляет собой инструмент для построения компиляторов, дающий возможность быстро прототипировать межпроцедурный анализ и компилирующие системы. Первоначально FIAT был интегрирован в систему ParaScope. При работе с FIAT программист должен только обеспечить функции инициализации, оператор объединения, функцию передачи и направление анализа. FIAT -- система, управляемая спросом: программист не должен беспокоиться о порядке межпроцедурного анализа. В FIAT/SUIF доступны несколько видов межпроцедурного анализа. Вначале обратный анализ вычисляет передаточную функцию, затем некоторые виды предусловий, которые дают каждое значение переменной в терминах инвариантов цикла и индексов вложенных циклов. Дополнительная фаза протягивает ограничения в виде неравенств из тестовых условий. Наконец, реализуются некоторые виды обратного межпроцедурного анализа массивов.