Введение к работе
9 I. Актуальность темы. Моделирование реальных физических процессов, обработка данных сейсмической разведки природных ископаемых, решение задач САПР и целого ряда других требует существенного повышения производительности вычислительных систем, что приводит к необходимости развития разнообразных параллельных архитектур. Разработанные к настоящему времени параллельные архитектуры позволяют достичь пиковой производительности на ограниченном наборе алгоритмов. Для оценки практической значимости параллельной архитектуры наряду с пиковой производительностью существенны такие характеристики, как:
широта класса алгоритмов и задач, допускающих адекватное отображение на архитектуру, достижение приемлемой реальной производительности;
наличие систем программирования, эффективных как в смысле достигаемой на полученном коде реальной производительности, так и в смысле технологичности программирования;
стоимость вычислительной аппаратуры, соответствие ее технологическим требованиям производства, то есть ее доступность.
Одной из наиболее перспективных разновидностей на основании этих критериев по нашему мнению является в настоящее время архитектура с длинным командным словом (Very Long Instruction Word - VLIW). VUW-процессор представляет собой совокупность исполнительных устройств, управляемых отдельными полями общего командного слова (длина командного слова достигает 1024 бит). При этом параллельная работа устройств обеспечивается синхронным выполнением командного слова всеми исполнительными устройствами. Планирование вычислений полностью возлагается на программное обеспечение, отсутствует аппаратура для опережающего просмотра потока команд л оптимизации на этапе выполнения программы, отсут-
С .
ствуют схемы синхронизации работы исполнительных устройств по потоку данных. Такой подход позволяет существенно упростить и удешевить аппаратуру, а простота способа синхронизации исполнительных устройств позволяет поднять тактовую частоту аппаратуры.
Плодотворность идеи VX-ZW-архитектуры тесно связана с успехами в области оптимизации микропрограмм и методов автоматического выделения параллелизма. Статическое планирование кода VLiW-npoueccopa, отсутствие накладных расходов на синхронизацию по потоку данных позволяет использовать мелкозернистый параллелизм. Однако наряду с этим может быть использован крупноблочный параллелизм: совмещение независимых итераций циклов, совмещение независимых модулей программы. Лля увеличения крупноблочного параллелизма могут быть использованы преобразования гнезд циклов, применяемые при векторизации (перестановки вложенных циклов, преобразования пространства итераций). Таким образом, VLIW-архитектура имеет предпосылки для эффективной обработки как кода, поддающегося векторизации, так и не векторизуемого, но содержащего достаточно "мелкозернистого параллелизма" - независимых операторов и операций.
В настоящее время имеется определенный положительный опыт создания систем программирования с автоматическим выявлением параллелизма для VLIW-ЪЪМ: транслятор Bulldog и экспериментальная машина ЕЫ-512 в Иель-ском университете, компьютеры семейства Trace фирмы Multiflow Computer, семейство процессоров AP-120/FPS-164 фирмы FPS, машина Cydra-Ь фирмы Cydrome, проект системы Элъбрус-Z и др. В целом, достоинства VXTW-архитектур достаточно очевидны, но создание-для них эффективных систем программирования требует дополнительных исследований и разработок. Необходимо расширение круга специалистов, которые в совершенстве владеют методами используемых там преобразований и способны развивать эти методы.
Целью работы является исследование и разработка способов информационного анализа, выделяющих неявный параллелизм последовательных программ в форме, адекватной архитектуре с длинным командным словом. .Для достижения поставленной цели необходимо:
разработать общую схему трансляции, учитывающую возможности предоставляемые FLiW-архитектурой, опыт ручного микропрограммирования; выбрать язык внутреннего представления и разработать интерфейс между этим представлением и алгоритмом упаковки кода;
разработать и исследовать алгоритмы выделения информационных зависимостей в .требуемой форме;
построить оптимизации, базирующиеся на выбранном внутреннем представлении кода;
реализовать предлагаемые алгоритмы в составе транслятора с Фортрана для спецпроцессора EC-27QQ.
Научная новизна полученных результатов заключается в создании новой техники упаковки гнезд циклов - "сложном конвейере", позволяющем за счет совмещения итераций внешнего цикла повышать эффективность программного конвейера внутреннего цикла; разработке внутреннего представления программы, позволяющего разделить информационный анализ программы, алгоритмы оптимизации и эвристические алгоритмы упаковки кода, в создании алгоритмов формирования этого внутреннего представления и алгоритмов, выполняющих оптимизации на его базе.
Лля анализа индексных выражений массивов разработаны алгоритмы, которые выделяют не только полный, но и частичный параллелизм обращений к массиву. Сформированный на базе идей Бенерджи алгоритм анализа имеет малую вычислительную сложность и выделяет частично параллельные обращения к массивам с приемлемым в большинстве случаев "загрублением". Алгоритм незагрубляю-щего (точного) анализа индексных выражений является развитием алгоритма Вольфа.
Сформулированы модели "сильных" зависимостей, по-
зволяющие выполнять при формировании программного конвейера оптимизации, недоступные в исходном коде. Оптимизации основываются на совмещении и сокращении ссылок на массивы, относящихся к различным итерациям.
Практическая значимость результатов заключается в разработке на основе предложенных алгоритмов фазы информационного анализа и оптимизации для транслятора NAP-FORTRAN. Этот оптимизирующий транслятор создан для процессора ЕС-2706 в рамках проекта "Сибирь" и передан в опытную эксплуатацию. Разделение процедур информационного анализа, оптимизации и процедур упаковки кода, осуществленное в указанном трансляторе, создает возможность переноса транслятора на процессор сходной архитектуры: (7-2706.1, ЕС-2709 или иной процессор с длинным командным словом.
Апробация работы. Основные результаты работы были представлены на международном семинаре "Методы конструирования программ" (Планерское, 21 - 25 сентября 1992), а. также на международной конференции "Parallel Computing Teclmologies-93" (Обнинск, 30 августа - 4 сентября) .
Публикации. По результатам диссертационной работы опубликовано 5 печатных работ.
Структура и объем работы. Диссертационная работа состоит из введения, четырех глав и заключения, изложенных на 116 страницах, содержит 4 рисунка, 60 наименований библиографии и 5 страниц приложения, всего 135 страниц.
