Введение к работе
О-Ілр^і
Свртвций І
Актуальность проблемы. В настоящее время за рубежом широкое распространение получили векторно-конвейерные ЭВМ (ВК ЭВМ), такие как CRAY-1, CRAY Х-МР, CDC CYBER-205, Fujitsu FACOM VP, Alliar.t FX/8, IBM 3090, FPS T series. В СССР ведется подготовка к серийному производству аналогичных ЭВМ. В связи с этим становится актуальной задача выявления и использования скрытого параллелизма последовательных программ с целью достижения более полной загрузки параллельно работающих узлов ВК ЭВМ при выполнении отих программ, а следовательно, и уменьшения времени выполнения программ.
Обычно процесс трансляции программы, написанной на одном из скалярных процедурных языков высокого уровня, в объектный код ВК ЭВМ состоит из следующих этапов:
Перевоп исходной программы в последовательный промежуточный
код;
Выявление скрытого параллелизма последовательной программы пу
тем анализа зависимостей по управлению и по данным между опе
раторами программы и его усиление путем проведения оптимизиру
ющих преобразований (перестановка операторов, разбиение и слия
ние циклов, обмен циклов); при этом предполагается, что чем больше
параллелизма мы выявим на этой стадии, тем легче будет генерато
ру кода организовать при работе программы максимальную загрузку
конвейеров ВК ЭВМ;
Генерация векторного кода для конкретной ВК ЭВМ.
Выявление и усиление скрытого параллелизма является в значительной
степени машиннонезависимым и поэтому может быть поручено автоматическому преобразователю, общему для нескольких входных языков и нескольких объектных ЭВМ.
В Системо КрОСС-Трансляторов (СКТ), разрабатываемой с
1985 г. на кафедре АСВК факультета ВМиК МГУ им. М.В. Ломоносова,
таким преобразователем является Векторизатор Промежуточно
го Кода (ВПК ИЛИ VIC), разработка которого является одной из
нелеп данной работы. Его входным языком служит Унифицированное
Промежуточное Представление (УПП) — скалярный промежу
точный код, а выходным — Векторное Унифицированное Проме
жуточное ПреДСТаВЛСНИе (ВУПП) промежуточный КОД, ЯВНО
кодирующий параллелизм программы.
С исходных языков высокого уровня в УПП программа переводится одним из компиляторов системы. В настоящее время разработан компилятор языка СИ, в стадии тестирования находятся компиляторы языков ФОРТРАН-77, ПАСКАЛЬ, разрабатываются трансляторы языков ФОРТРАНАХ, СИ + + , МОДУЛА.
Цели и задачи настоящей диссертационной работы таковы;
Дополнить промежуточный код УПП средствами, позволяющими в
явном виде кодировать информацию о параллелизме программ.
)
Средства представления параллелизма не должны навязывать тот или иной вид параллелизма, а лишь давать рекомендации, которыми может воспользоваться генератор кода, обладая данными о видах параллелизма, доступных на конкретной объектной ЭВМ. Дополненное УИП называется ВУПП.
Разработать Векторизатор Промежуточного Кода, работающий в рамках Системы Кросс-Трансляторов. Задача Векторизатора заключается в подготовке для генератора кода информации о том, какой степенью параллелизма обладают те или иные параметрические циклы программы. При отом Векторизатор обязан сохранить всю информацию, которая может пригодиться для генерации эффективного скалярного кода. Однако при наличии возможности увеличить степень параллелизма программы Векторизатор должен делать ото путем применения различных векторизующих преобразований.
Существующие методы векторизации и распараллеливания ориентированы на программы, написанные на ФОРТРАНе. Так как в последнее время язык СИ стал использоваться во многих приложениях, и том числе и в приложениях вычислительного характера, перед нами стояла задача разработать методы векторизации программ, написанных не только на ФОРТРАне.но и на СИ, который к тому же является одним из входных языков СКТ.
Ныне существующие системы векторизации в основном базируются на ТЬорИИ Зависимости, в разработке которой принимали-участие D.J. Kuck, R. Allen, К. Kennedy, М. Burke, R. Cytron, M. Wolfe, U. Banerjee. Работы советских ученых А.П. Ершова, В.П. Иванникова, В.А. Вальков-ского, В.Г. Лебедева также оказали большое влияние на разработчиков систем распараллеливания и векторизации. Теоретической базой описы-наемого Векторизатора является Теория Зависимостей.
Научная новизна работы заключается в следующем.
Разработан векторный диалект промежуточного кода
(ЮПИ), позволяющий явно кодировать параллелизм циклов, как извлекаемый из скалярных программ Векторизатором, так и присут-гтиукнцнп в программах на ФОРТРАНе-8Х. Причем векторные опе-цацин ФОРТРАНа-8Х в ВУПП преобразуются к обычным скалярным операциям, охваченным циклами типа DCLSIM (одновременное вы-іи»лн«чше итераций). Такое преобразование позволяет использовать параллелизм, задаваемый векторными операциями ФОРТРАНа-8Х не только на векторных процессорах, но и на машинах с другими типами параллели л изма.
Разработан алгоритм обнаружения гнезд параметриче
ских ЦИКЛОВ (не обязательно тесновложенных), работающий на
графе потока управления процедуры. Временная сложность данно
го алгоритма является линейной функцией количества вершин гра
фа управления. Е5олее того, программная реализация алгоритма де
монстрирует весьма высокую скорость, что делает данный алгоритм
пригодным для использования в промышленных компиляторах. Вы-
сокая скорость работы алгоритма вызвана тем» что он обнаруживает только те циклы, тела которых являются линейными компонентами (именно такие циклы пригодны для векторизации), а также тем, что алгоритм работает 'изнутри наружу', что позволяет значительно сократить обход графа.
Алгоритм Тарьяна, выделяющий максимальные сильно связные компоненты (МССК) графа зависимостей, объедичен с топологической сортировкой вершин направленного ациклического графа, получающегося при замене каждой МССК одной вершимой.
Разработан алгоритм совместной делинеаризации двух обращении к массиву, проверяемых на наличие зависимости между ними. Делинеаризация обращений — ото установление возможного количества измерений массива и границ изменения индекса по каждому из его измерений посредством анализа диапазонов изменения переменных охватывающих циклов и коэффициентов, стоящих при этих переменных в обращениях. Делинеаризация позволяет разнести переменные охватывающих циклов по различным измерениям и тем самым обеспечить более точные результаты при применении неравенства Банерджи. Во время делинеаризации 'на лету' происходит проверка на независимость тестируемых обращений с точностью, превышающей суммарную точность НОД-проверкн и неравенства Банерджи.
Практическая ценность работы заключается в создании Векторизатора Промежуточного Кода — компоненты Системы Кросс-Трансляторов, обнаруживающей скрытый параллелизм последовательных программ, и усиливающей его путем проведения оптимизирующих преобразований. Информация, собранная ВПК, и выполненные им преобразования дают генератору кода ясные указания о том, какие фрагменты программы можно выполнять параллельно.
Промежуточный код, выдаваемый Векторизатором может быть также преобразован в программу на ФОРТРАНе-8Х или на каком-либо другом параллельном/векторном языке. Таким образом, настоящий Векторизатор может работать в общепринятом для программ такого класса режиме source-to-source translator.
Так как данный Векторизатор имеет весьма высокую скорость трансляции и не требует значительного объема памяти, он может быть применен в промышленных системах трансляции для параллельных и векторных компьютеров.
Программная реализация. В настоящее время Векторизатор реализован на языке Си в ОС UNIX на ЭВМ ВЕСТА, IBM PC ЛТ/286, СМ-1420, Элек-троника-85. Качество и скорость работы Векторизатора обсуждаются в главе 2.4.
На всех стадиях работы Векторизатора выводится подробная отладочная информация с использованием исходного текста векторизуемой программы и диагностируются ошибки пользователя и причины невектори-
оуемости фрагментов программы.
Апробация. Материалы диссертации докладывались на:
Всесоюзной конференции "Смешанные вычисления и преобразования программ '90" в г. Новосибирске;
Конференции ассоциации "Супер-Компьютер" в с. Непецино (стендовый доклад), 1991;
Научно-исследовательском семинаре кафедры АСВК ВМиК МГУ;
Семинаре "Вопросы распределенной обработки информации" кафедры АСВК ВМиК МГУ;
Научно-исследовательском семинаре ИТМиВТ им. Лебедева,
Семинаре ВЦ АН СССР под руководством Серебрякова В.А..
Публикации. По теме диссертации опубликовано 6 работ.
Объем и структура работы. Диссертация состоит из введения, 4-ех глав, заключения, списка литературы, и 2-ух приложений. Текст диссертации занимает около 80 страниц, список литературы включает порядка 70 наименований.
