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

ДОУ - 1. 9' %

МОСКОВСКИЙ ОРДЕНА ЛЕНИНА, ОРДЕНА ОКТЯБРЬСКОЙ РЕВОЛЮЦИИ И ОРДЕНА ТРУДОВОГО КРАСНОГО ЗНАМЕНИ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ имени М.В. ЛОМОНОСОВА

ФАКУЛЬТЕТ ВЫЧИСЛИТЕЛЬНОЙ МАТЕМАТИКИ И КИБЕРНЕТИКИ

На правах рукописи

Маслов Вадим Юрьевич

УДК 681.3

РАЗРАБОТКА ВЕКТОРИЗАТОРА

ДЛЯ СИСТЕМЫ КРОСС-ПРОГРАММИРОВАНИЯ

Специальность 05.13.11 - математическое и программное обеспечение вычислительных машин и систем

Авто ]) с ф с ]> а т диссертации на соискание ученой степени кандидата физико-математических наук

Москва - 1991

Работа выполнена на кафедре Автоматизации Систем Вычислительных Комплексов (АСВК) факультета Вычислительной Математики и Кибернетики Московского Государственного Университета им. М.В. Ломоносова.

Научные руководители:

• доктор фиоико-математическик наук, член-корреспондент АН СССР, профессор кафедры АСВК ВМиК МГУ Лев Николаевич Королев;

• кандидат фиоико-математических наук, доцент кафедры АСВК ВМиК МГУ Игорь Валерьевич Машечкин.

Официальные оппоненты:

• доктор фиоико-математических наук, оав. отделом Института Прикладной Математики АН СССР им. Келдыша Виктор Алексеевич Крюков;

• кандидат фиоико-математических наук, оав. отделом Института Точной Механики и Вычислительной Техники АН СССР Леонид Евгеньевич Карпов.

Ведущая органиоация: Вычислительный Центр АН СССР.

..14., ^Лр.

о совета Д.053.05.3

о .

Защита состоится " I V " и-'А-^К.' -_ 199_ г. в часов на оаседании

Специализированного совета Д.053.05.38 N 4 по математике при МГУ им. М.В. Ломоносова по адресу: 119899, Москва, ГСП-3, Ленинские гопы,-МГУ, факультет вычислительной математики и кибернетики, ауд.

С диссертацией можно ознакомиться в библиотеке факультета вычислительной математики и кибернетики МГУ.

Автореферат разослан "_"___ 1991 г.

Ученый секретарь совета профессор

Н.П. Трифонов

f^Sili* ; u- . |

О-для^'I Общая характеристика работы серт«цин 1

Ллчуальность проблемы. В настоящее время за рубежом широкое распространение получили векторно-конвейерные ЭВМ (ВК ЭВМ), такие как CRAY-1, CRAY Х-МР, CDC CYBER-205, Fujitsu FACOM VP, Alliar.t FX/8, IBM 3090, FPS T series. В СССР ведется подготовка к серийному производству аналогичных ЭВМ. В связи с этим становится актуальной задача выявления и использования скрытого параллелизма последовательных программ с целью достижения более полной загрузки параллельно работающих узлов ВК ЭВМ при выполнении отих программ, а следовательно, и уменьшения времени выполнения программ.

Обычно процесс трансляции программы, написанной на одном из скалярных процедурных языков высокого уровня, в объектный код ВК ЭВМ состоит из следующих этапов:

• Перевоп исходной программы в последовательный промежуточный код;

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

• Генерация векторного кода для конкретной ВК ЭВМ.

Выявление и усиление скрытого параллелизма является в значительной

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

В Системе Кросс-Трансляторов (СКТ), разрабатываемой с 1985 г. на кафедре АСВК факультета ВМиК МГУ им. М.В. Ломоносова, таким преобразователем является Векторизатор Промежуточного Кода (ВПК ИЛИ VIC), разработка которого является одной из нелеп данной работы. Его входным языком служит Унифицированное Промежуточное Представление (УПП) — скалярный промежуточным код, а выходным — Векторное Унифицированное Промежуточное Представление (ВУПП) — промежуточный код, явно кодирующий параллелизм программы.

С исходных языков высокого уровня в УПП программа переводится одним из компиляторов системы. В настоящее время разработан компилятор языка СИ, в стадии тестирования находятся компиляторы языков ФОРТРАН-77, ПАСКАЛЬ, разрабатываются трансляторы языков ФОР-ТРАН-SX, СИ + + , МОДУЛА.

Цели И задачи настоящей диссертационной работы таковы;

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

)

z

Средства представления параллелизма не должны навязывать тот или иной вид параллелизма, а лишь давать рекомендации, которыми может воспользоваться генератор кода, обладая данными о видах параллелизма, доступных на конкретной объектной ЭВМ. Дополненное УНП называется ВУПП.

• Разработать Векторизатор Промежуточного Кода, работающий в рамках Системы Кросс-Т^ансляторов. Задача Векторизатора заключается в подготовке для генератора кода информации о том, какой степенью параллелизма обладают те или иные параметрические циклы программы. При отом Векторизатор обязан сохранить всю информацию, которая может пригодиться для генерации эффективного скалярного кода. Однако при наличии возможности увеличить степень параллелизма программы Векторизатор должен делать ото путем применения различных векторизующих преобразований.

• Существующие методы векторизации и распараллеливания ориентированы на программы, написанные на ФОРТРАНе. Так как в последнее время язык СИ стал использоваться во многих приложениях, и том числе и в приложениях вычислительного характера, перед нами стояла задача разработать методы векторизации программ, написанных не только на ФОРТРАне.но и на СИ, который к тому же является одним из входных языков СКТ.

Ныне су шествующие системы векторизации в основном базируются на Теории Зависимости, в разработке которой принимали-участие D.J. Kuck, R. Allen, К. Kennedy, М. Burke, R. Cytron, M. Wolfe, U. Banerjee. Работы советских ученых А.П. Ершова, В.П. Иванникова, В.А. Вальков-окого, В.Г. Лебедева также оказали большое влияние на разработчиков систем распараллеливания и векторизации. Теоретической базой описываемого Векторизатора является Теория Зависимостей.

Научная новизна работы заключается в следующем.

• Разработан векторный диалект промежуточного кода (liVIlll). позволяющим явно кодировать параллелизм циклов, как извлекаемый из скалярных программ Векторизатором, так и присутствующий в программах на ФОРТРАНе-8Х. Причем векторные опе-цацин ФОРТРАНа-8Х в ВУПП преобразуются к обычным скалярным операциям, охваченным циклами типа DCLSIM (одновременное выпилимте итераций). Такое преобразование позволяет использовать параллелизм, задаваемый векторными операциями ФОРТРАНа-8Х не только на векторных процессбрах, но и на машинах с другими типами и а рал лел клизма.

• РазраГш гам алгоритм обнаружения гнезд параметрических ЦИКЛОВ (не обязательно тесновложенных), работающий на графе потока управления процедуры. Временная сложность данного алгоритма является линейной функцией количества вершин графа управления. EJojiee того, программная реализация алгоритма демонстрирует весьма высокую скорость, что делает данный алгоритм пригодным для использования в промышленных компиляторах. Вы-

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

• Алгоритм Тарьяна, выделяющий максимальные сильно связные компоненты (МССК) графа зависимостей, объедичен с топологической сортировкой вершин направленного ациклического графа, получающегося при замене каждой МССК одной вершимой.

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

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

Промежуточный код, выдаваемый Векторизатором может быть также преобразован в программу на ФОРТРАНе-8Х или на каком-либо другом параллельном/векторном языке. Таким образом, настоящий Векторизатор может работать в общепринятом для программ такого класса режиме source-to-source translator.

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

Программная реализация. В настоящее время Векторизатор реализован на языке Си в ОС UNIX на ЭВМ ВЕСТА, IBM PC AT/286, СМ-1420, Элек-троника-85. Качество и скорость работы Векторизатора обсуждаются в главе 2.4.

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

эуемости фрагментов программы.

Апробация. Материалы диссертации докладывались на:

• Всесоюзной конференции "Смешанные вычисления и преобразования программ '90" в г. Новосибирске:

• Конференции ассоциации "Супер-Компьютер" в с. Непецино (стендовый доклад), 1991;

• Научно-исследовательском семинаре кафедры АСВК ВМиК МГУ;

• Семинаре "Вопросы распределенной обработки информации" кафедры АСВК ВМиК МГУ;

• Научно-исследовательском семинаре ИТМиВТ им. Лебедева,

• Семинаре ВЦ АН СССР под руководством Серебрякова В.А..

Публикации. По теме диссертации опубликовано 6 работ.

Объем и структура работы. Диссертация состоит из введения, 4-ех глав, заключения, списка литературы, и 2-ух приложений. Текст диссертации занимает около 80 страниц, список литературы включает порядка 70 наименований.

2 Содержание работы

2.1 Обзор систем распараллеливания и векторизации

В 1-ОИ главе содержится анализ и сравнение существующих систем векторизации, обсуждается теория, использо&анная при разработке этих систем.

2.2 ВУПП — промежуточный код с явным кодированием параллелизма

Во 2-*ои главе обсуждается возможность унификации кодирования информации о параллелизме программы в применении к Векториоатору, приводится описание ВУПП, обсуждается связь конструкций ВУПП с конструкциями векторных языков, с одной стороны, и с векторными командами распространенных ВК ЭВМ, с другой стороны.

При разработке ВУПП были приняты во внимание следующие требования: синтаксическая и семантическая минимальность ВУПП; наличие в ВУПП средств кодирования всей информации о параллелизме программ, поставляемой Векторизатором либо компилятором; альтернативность ВУПП, то есть наличие у генератора кода вооможности самому принять окончательное решение о степени параллелизма тех или иных конструкций; семантическая близость конструкций ВУПП к конструкциям обработки массивов ФОРТРАНа-8Х и к системам команд ВК ЭВМ.

■4Г

Так как распараллеливание (векторное и асинхронное) параметрических циклов дает наибольший эффект, ВУПП кодирует только один вид параллелизма — параллелизм параметрических циклов. Каждый цикл снабжается заголовком, характеризующим его максимально возможную степень параллелизма. Имеется три типа заголовков: D0.SEQ — итерации циклов могут выполняться только строго последовательно в порядке, предписываемом циклом; DCLSIM — итерации циклов могут выполняться одновременно, то есть на векторной аппаратуре либо на синхронизованных процессорах; D0.PAR — итерации циклов могут выполняться в произвольном порядке либо параллельно асинхронно.

Внутри каждого такого цикла может располагаться оператор присваивания COMPUTE, оператор условного присваивания COND.COMPUTE, и вложенный цикл. Все обращения к памяти в этих операторах происходят только посредством операции ARRELT —- элемент вектора. При этом скаляр считается вектором единичной длины. Порождаемое циклами, охватывающими оператор, пространство итераций используется в выражениях операторов присваивания посредством операций LOOP.VAR — значение переменной цикла, и LIN_FORM — линейная форма от переменных цикла. Также в этих выражениях могут присутствовать константы и. операции — арифметические, битовые и логические. Набор этих операций в основном совпадает с набором операций языка СИ.

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

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

Пример. Рассмотрим алгоритм вычисления произведения матриц А и В с записью результата в матрицу С, написанный на ФОРТРАНе-77:

REAL а(0:N-1,0:N-1) , b(0:N-l,0:N-1). c(0:N-1.0:N-l)

DO 10 i=0,N-l DO 10 j=0,N-l c(j.i) - 0 DO 10 k=0,S-l 10 c(j,i) = c(j,i) + a(k,i)«b(j,k)

После векторизации этот фрагмент на ВУПП будет выглядеть так:

AUTOMATIC "a" AREA V'N' V'N' MUL T0_TYPE*real <0> AUTOMATIC "b" AREA V'N' V'N' MUL TO_TYPE*real <0>

AUTOMATIC "с" AREA V'N' V'N' MUL TO_TYPE*real <0> AUTOMATIC "i" AREA C»int_l <0> AUTOMATIC "j" AREA C«int.l <0> DO.SIM 'i' Cint.O <0> V'N' <0> Cint.l <Q> DO.SIM 'j' Cint.O <0> V'N' <0> Cint.l <0>

COMPUTE LIN.FORM.2 V'N' <0> Cint.l <0> ARRELT'с' Creal.0.0 ASMOVE <0>

DO.END DO.END

DO.SEq 'k' Cint.O <0> V'N' <0> Cint.l <0> DO.SIM 'i' Cint.O <0> V'SI' <0> Cint.l <0> DO.SIM 'j' Cint.O <0> V'N' <0> Cint.l <0>

COMPUTE LIN.FORM.3 Cint.O <0> V'N' <0> Cint.l LIN.FORM.3 Cint.l <0> V'N' <0> Cint.O LIN.FORM.3 V'N' <0> Cint.O <0> Cint.l MUL ASADD <0>

DO.END DO.END DO.END

В данном фрагменте первые 3 оператора AUTOMATIC объявляют вектора А, В и С, каждый длиной по N»N чисел типа real. Вместо номера объекта указывается его имя в апострофах. Конструкции типа Cint.lOO, Creal_0_0 обозначают константу (CONSTANT) с указанием ее типа и значения. Конструкция V'N' обозначает значение переменной N. Точка либо подчеркивание, стоящая перед числом, обозначает формат, в котором оно записано; <0> означает NULL — код конца выражения. Выражения ВУПП записываются в польской постфиксной записи.

2.3 Теория и алгоритмы Векторизатора

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

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

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

<0> ARRELT'с' <0> ARRELT'а' <0> ARRELT'Ь'

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

Алгоритм выделения параметрических циклов на графе управления базируется на 1Ч-обратном обходе вершин графа управления. При посещении каждой вершины:

• Вершина, в которую входит 1Ч-обратная дуга и не 1Ч-обратная дуга, является кандидатом на уЬ — начальную вершину параметрического цикла. Вершина, из которой выходит М-обратная дуга, является кандидатом на уз —- конечную вершину цикла. Если в вершину не входят зги дуги, продолжаем- обход.

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

• После обнаружения переменной цикла и его параметров производится обход всех вершин цикла, расположенных между уЬ и ув, алгоритмом обнаружения Р^-области. Если тело цикла не является ^областью, то сК-^'ом оно и подавно не является; в этом случае продолжаем обход.

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

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

Так как алгоритм выделения циклов проходит каждую вершину и дугу графа потока управления ровно один раз, он требует времени О(У-)-Е),

где V — количество вершин графа, а^ -— количество дуг графа.

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

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

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

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

Практически все известные методы не способны доказать независимость для пары линеаризованных обращений, заключенных в два цикла. Так, обращения С(1*10»з) и С(1 + 10*^+5), заключенные в циклы 00 1=0,4 и 00 ^ =0,9, независимы, так как для всех целых »,,«3 € [о>4Ь ЗиЗ* € [о,9] ». + 10.7, >, + ю], + 5. Однако, уравнение г, + loj1 = », + ю+ 5 имеет вещественные решения. Например, = = а, = 4.5, ], = 4 являются решениями этого уравнения.

Наш подход заключается в том, чтобы разбить уравнение зависимости 10Л — + «1 — «> — 5 = о> «»»«'. € [0,4), ЗчЗг £ [0,9] на два уравнения ЮЗ^ — loj1 = о и », — «, — 5 = о, которые затем решаются независимо друг от друга. Докажем, что это может быть сделано. Сделаем следующие замены: А = 107, — loj„ В = », — »,— 5. Принимая во внимание границы циклов, имеем |В| < ю, |А| = о или |А| > ю. Следовательно, А + В = о выполняется только тогда, когда выполняются А = о и В = о.

S>

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

Может возникнуть мысль, что линеаризованные обращения весьма экзотичны и, следовательно, не заслуживают отдельного рассмотрения. Это не так. Прежде всего, линеаризованные обращения могут присутствовать в программе пользователя, как таковые. Для того, чтобы понять, насколько часто линеаризованные обращения используются в реальных программах, мы проанализировали 8 фортрановских программ из набора тестов RiCEPS (Rice Compiler Evaluation Program Suite). Было обнаружено, что вручную линеаризованные обращения использованы в 6 ио 8 программ.

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

В ФОРТРАНе-77 наложение массивов может быть вызвано применением операторов EQUIVALENCE и COMMON (статическое наложение), а также связыванием формальных и фактических параметров вызова процедуры или функций (динамическое наложение). Стандарт ФОРТРАНа-77 утверждает, что накладываемые друг на друга массивы считаются линеаризованными. Это позволяет программистам накладывать друг на друга массивы, имеющие различную форму и длину, н заставляет компиляторы считать накладываемые массивы линеаризованными для того, чтобы обработать произвольный случай наложения. Линеаризация зачастую приводит к увеличению количества переменных, участвующих в индексе, и следовательно, затрудняет обнаружение зависимостей.

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

Ниже приводится формулировка теоремы и алгоритма делинеаризации. Рассмотрим уравнение зависимости, записанное для линейных индексных функций (все величины в нем — целые, п, — это число неизвестных. et — коэффициенты, z* — неизвестные, Zk — границы циклов):

с0 + c,z, + •• • + cnjznj = о Z.ekzj, ..., 2„з6[О,я„5]

Теорема. Множество решений уравнения (1) и множество решений стемы уравнений

{<t, + c,z, + • • • + cmzm = о

JD„ + ст+1*т+1 + ••• + c„Jz„J = о C¿)

«i € [o, Z,¡, ..., z„,€[o,Z„J

совпадают (m € [i,n3]), если существуют целые числа da, D0, такие что

g«l(A.,cm+,,...,Cf,3) > max(K + ¿;cjZ4|, |d„ + ¿ c*Zk\) (3)

k=i

И

c„ = d„ + D0. (4)

Здесь и далее |я| обооначает абсолютное значение х, gcd(x,J/,...,z) обозначает наибольший общий делитель (НОД) чисел x,y,...,z , с+ = пых(с,о) , с" = min(c, о).

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

ВВОД: уравнение зависимости (1), то есть, цепые числа с0, c,,...,cnj, Ziy...,Zns. ВЫВОД: множество векторов направлений, описывающее решения дэнного уравнения (=0, если нет решении).

Упорядочить сц, то есть, вычислить I/,, такое что Vfc £ [i)"3 — i] lc/i+,| > lc/Jl

Присвоить ка минимальное целое, такое что с/^ ^ о;

Вычислить : Vi £ [к0,п3] дк = gcd(c/„ciítl,...,с/.з): д„3+, = оо;

DirVecs = {(*,.-,*)}; кВед = к0\ smin — smax = о;

DO к = fc„, п3 + i,x

г — с0 mod <7j¿; emin = smin + г; стпах = smax + г; IF niax(|cmin|, |cmax|) < gk THEN

IF emin > o or стпах < о THEN RETURN 0 (независимость); Вычислить мн-во векторов направлений NV = (пю,,...,nv¡) для уравнения г + Yli^kBíícI¡z¡l — о, используя существующие методы; DirVecs = {de П nv : dv £ DirVecs, nv £ NV, d» П n» 0} smin = smax = о; кВед = к; c0 — c0 — r; ENDIF

smin = smin + cJ^Z;,; smax = smax + ENDDO •

RETURN DirVecs,

Рисунок 1: Алгоритм обнаружения зависимостей, базирующийся на делинеаризации

Алгоритм. На рисунке 1 приводится алгоритм делинеаризации, записанный на некоем языке спецификации. Этот алгоритм разбивает

Л

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

Генерация выходной программы. В построенном мультиграфе проводится! поиск максимальных сильно связных компонент (МССК) по алгоритм^ Tarjan'a, совмещенный с топологической сортировкой вершин результирующего ациклического направленного графа. Это совмещение базируется на следующем наблюдении: алгоритм Тарьяна выдает МССК. в порядке, обратном порядку, получаемому при топологической сортировке. Складывая МССК н стек, мы потом сможем извлечь их в необходимом порядке. Применение объединенного алгоритма ведет к отсутствию затрат нремени на топологическую сортировку.

Для МССК. состоящей из одной вершины без контуров, генерируется векторный код. К МССК, являющейся контуром, сначала применяется алгоритм обмена (выворачивания) циклов, призванный вытянуть контур зависимостей из внутренних на внешние уровни циклов и тем самым позволить сгенерировать векторный код на внутренних уровнях. После ¿»того скалярно генерируется один охватывающий МССК цикл и в МССК проводится >даление дуг, имеющих уровень, равный уровню сгенерированного цикла. Затем процесс идет рекурсивно вглубь — данный шаг выполняется л л я получившегося после удаления дуг подграфа.

2.4 Оценка качества Векторизатора

В 4-ОИ главе приводятся данные о тестировании Векторизатора на Ли~ верморских циклах и делаются выводы об аналнзируемости Векторизатором наиболее часто встречающихся Фортрановских конструкций. В конце главы настоящий Векторизатор сранивается с аналогичными продуктами с целью определения 'экологической ниши', им занимаемой.

Скорость векторизации. Испытания Векторизатора были проведены на ЭВМ БЕСТА, построенной на базе микропроцессора фирмы Motorola, а также на IBM PC АТ/286 с тактовой частотой 12 MHz, и на ЭВМ Олектроннка-85.

Результаты замера времени векторизации Лпверморских циклов и вычисленная исходя из этого времени скорость векторизации в исходных строках в секунду, присваиваниях в секунду, и циклах и секунду приведены в таблице 1.

Программа, содержащая данные циклы, состоит из 185 строк. В ней содержится 15 параметрических циклов и С6 операторов присваивания. Следует отметить, что каждое присваивание содержит от 2 до 10 обра-

ЭВМ время сек. исх. строки в сек. присваивания в сек. циклы в сек.

ВЕСТА 3.5 52 18 4

IBM PC АТ/286 5.0 37 13 3

Электр он ика-85 18 10 4 1

Габ.ппы I: Скорость векторизации

щений к элементам массива, а каждый цикл содержит от 1-го до 19-ти операторов присваивания.

Качество векторизации Ливерморских циклов. Возможности Векторизатора были проверены с использованием Ливерморских циклов, взятых па публикации В.П. Иванникова, C.B. Нестерова, А.П. Черняева.

Показателями качества векторизации считались две величины:

• Отношение числа циклов, векторизованных автоматически, к числу циклов, векторизуемых вручную. Для Векторизатора ото 60%. Если цикл не векторизуем ни вручную, ни автоматически, но Векторизатор строит для него недостаточно точный граф зависимостей, то такой цикл включался в число циклов, векторизуемых вручную.

• Отношение числа операторов присваивания, векторизованных автоматически, к числу операторов присваивания, векторизуемых вручную. Для Векторизатора это 75%. Невекторизуемые операторы, анализируемые Векторизатором недостаточно точно, включались в число вручную векторизуемых операторов.

Сравнение с аналогичными продуктами и выводы. Векторизатор Промежуточного Кода по скорости векторизации соответствует промышленным векторизаторам. Однако он превосходит многие из них по качеству анализа: Векторизуется не только самый внутренний цикл, но и охваты-пающие его параметрические циклы; В теле векторизуемого цикла допускается наличие условных операторов; Использование наложения масси-uoii, в том числе имеющих разную форму, и связанных измерений не снижает точности обнаружения зависимостей; Распознаются GOTO-циклы.

О другой стороны, сравнивая данный Векторизатор с лучшими академическими векторизаторами/распараллеливателями PFC, Parafrase не-.'II.: 1 я не отметить, что они проводят гораздо более глубокий анализ программы. В векторизаторе в настоящее время отсутствуют: Межпроцедурный анализ; Символьные вычисления, позволяющие в некоторых случаях доказывать независимость обращений к элементам массива; Некоторые достаточно сложные для реализации распараллеливающие преобразования.

Таким образом, данный Векторизатор оанимает промежуточное место между 'глупыми', но быстрыми промышленными векторизаторами и слишком 'умными', но весьма медленными и требовательными к ресурсам

ЭВМ академическими векторизаторами.

Кроме того, данная разработка делает весьма важные шаги на пути к построению промышленного векторизатора для программ на языке СИ: Выявление структуры циклов программы исходя не из готовых ОО-циклов ФОРТРАНа, а из графа потока управления процедуры; Анализ зависимостей между линеаризованными обращениями к массивам, свойственным языку СИ.

3 Основные результаты работы

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

• Разработан векторный диалект Унифицированного Промежуточного Представления Системы Кросс-Программирования (ВУПП), позволяющий явно кодировать векторный параллелизм, извлекаемый из скалярных программ. Также с помощью ВУПП возможно кодирование явного векторного параллелизма, присутствующего в программах на ФОРТРАНе-8Х.

• Разработан и реализован Векторизатор, выявляющий скрытый век-торный'параллелизм скалярных программ и кодирующий его п форме ВУПП. Отличие Векторизатора от аналогичных продуктов состоит в отсутствии жесткой ориентации на ФОРТРАН (среди входных языков присутствует СИ).

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

• Разработан алгоритм совместной делинеаризации дпух обращении К массиву, проверяемых на наличие зависимости между ними. Во время делинеаризации 'на лету' происходит проверка на независимость тестируемых обращений с точностью, превышающей суммарную точность НОД-проверки и неравенства Банерджи.

• Проведено тестирование Векторизатора на Ливерморских циклах и сравнение его с существующими системами векторизации и распараллеливания. С использованием данных о частоте появления различных конструкций ФОРТРАНа проанализированы возможности Векторизатора по обработке реальных программ. Проведено измерение скорости векторизации на ЭВМ различных типов.

Публикации. По теме диссертации опубликовано 6 работ:

• Маслов В.Ю., Машечкин И.В., Расширение промежуточного кода системы трансляторов векторными операциями, в сб. научных трудов

кафедры Л С В К, М., 1991.

• Маслов В.Ю., Машечкин И.В., Векторные конструкции в промежуточном коде системы кросс-трансляторов, в Сб. "Вопросы распределенной обработки информации", М., 1991.

• Маслов В.Ю., Автоматическая векторизация параметрических циклов н рамках системы кросс-трансляторов, Деп. в ВИНИТИ 01.03.91, номер il l I-B91.

• Маслов В.Ю., Машечкин И.В., Кодирование векторной обработки в промежуточном коде системы трансляторов, Деп. в ВИНИТИ 01.03.91, номер 945-В91.

• Маслов Ц.Ю., Машечкин И.В., Принципы построения системы программирования для векторно-конвейерных ЭВМ, Материалы конференции ''Смешанные вычисления и преобразования программ '90", г. Новосибирск.

• Маслов В.Ю., Векторизация программ в системе кросс-трансляторов, Материалы конференции "Смешанные вычисления и преобразования программ '90", г. Новосибирск.

Подписано в печать 27.II.91 г. Формат 60x84/16. Объём 1,0 п.л. Тирак 100 экз. Заказ № 51. Бесплатно.

Ротапринт НИЩ МГУ II9899, Москва, Ленинские горн