Видеоролик с демонстрацией возможностей ОРС

ОРС — Оптимизирующая распараллеливающая система — программная инструментальная система, ориентированная на разработку

1. распараллеливающих компиляторов; оптимизирующих компиляторов с параллельных языков, систем полуавтоматического распараллеливания;
2. систем автоматического проектирования электронных схем;
3. автоматическое создание (проектирование) программно-аппаратных комплексов на основе ПЛИС.

ОРС ориентирована на различные целевые параллельные архитектуры.

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

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

Структура ОРС

Парсеры.

• Си.
• Урезанный Фортран (конвертируется через внутреннее представление ОРС2)
• Урезанный Паскаль (конвертируется через внутреннее представление ОРС2)

Генерация выходного кода.

• Преобразованный код С.
• Экспериментальная автоматическая генерация Си с процедурами MPI.
• Код Си с выделенными циклами ParDO.
• Код Си с выделенными конвейеризуемыми циклами.
• Автоматический расчет синхронизации конвейеризуемых циклов.
• Автоматизация оценки погрешности вычислений.

Графовые модели программ.

• Граф информационных связей.
• Граф вычислений (автоматическая конвейеризация цикла с синхронизацией).
• Решетчатый граф программы.
• Управляющий граф программы.
• Граф вызовов подпрограмм.

Внутреннее представление.

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

Библиотека преобразований.

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

В ОРС постоянно обновляются или дописываются новые функции.

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

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

• Смешанные вычисления в арифметических выражениях.
• Подстановка значений переменных, в т.ч. протягивание констант.
• Переименование скалярных переменных
• Удаление мертвого кода.
• Перестановка операторов

Преобразования одномерных циклов.

• Развертка цикла.
• Раскрутка цикла.
• Канонизация цикла.
• Разбиение циклов.
• Слияние циклов.
• Вынос инварианта из цикла
• Расщепление вершин (Введение дополнительных массивов).
• Растягивание скаляров (Замена скалярной переменной массивом).
• Избавление от индуктивных переменных.

Преобразования циклов с линейной рекуррентной зависимостью.

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

Преобразование гнезд циклов.

• Перестановка циклов.
• Tiling (Квантование многомерного цикла).
• Неунимодулярные преобразования тесных гнезд циклов.
• Расщепление многомерных циклов.
• Подстановка индексных переменных в гнездах циклов
• Переименование индексных переменных в гнездах циклов.

Преобразования одномерного цикла в гнездо циклов.

• Гнездование цикла
• Разрыв итераций.

Преобразования ОРС используют СЕРВИСНЫЕ ФУНКЦИИ:

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

Исследовательские интересы группы ОРС

• Автоматическое распараллеливание программ.
• Многоконвейерные вычисления
• Преобразования программ, основанные на решетчатом графе
• Автоматический контроль погрешности вычислений
• Автоматизация разработки преобразований программ
• Автоматизация разработки электронных схем.

Система визуализации ОРС

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

Ниже приводятся копии экранных форм системы визуализации ОРС2. (Система визуализации ОРС3 ожидается в сентябре 2005 г.)

Граф информационных зависивостей ОРС:

Отображение цикла на реконфигурируемый конвейер средствами ОРС:

Решетчатый граф ОРС, постороенный по двум выделенным вхождениям (используется для переименования и подстановки индексных переменных):

Выделяются два исходных цикла, выбирается "слияние циклов":

Выполнено преобразование "слияние циклов":

Команда разработчиков ОРС и участников семинара ОРС (лето 2004):

(Слева направо верхний ряд) Зиновий Нис, Константин Гуфан, Александр Шульженко, Роман Морылев, Виктор Петренко, Михаил Шилов, Милена Еремеева, Мария Цибулина, Сергей Науменко, Александр Бутов, Полина Шатерникова.

(Нижний ряд) Олег Штейнберг, Александр Тузаев, Роман Штейнберг, Денис Черданцев, Людмила Миронова.

Еще в 2003 году наша команда была значительно меньше:

(Слева направо) Виктор Петренко, Роман Штейнберг, Сергей Науменко, Борис Яковлевич Штейнберг, Денис Черданцев, Александр Шульженко, Александр Бутов.