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

-:ь 1 0 3'2

РОССИЙСКАЯ АКАДЕМИЯ НАУК

ОРДЕНА ЛЕНИНА ИНСТИТУТ ПРОБЛЕМ УПРАВЛЕНИЯ

(автоматики и телемеханики)

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

ГОНСАЛЕС-МЕНЕНДЕС Елена Альбертовна

МЕТОДЫ

ГЕНЕРАЦИИ ЭФФЕКТИВНЫХ КОДОВ ДЛЯ МИКРОПРОГРАММИРУЕМЫХ МНОГОПРОЦЕССОРНЫХ СИСТЕМ С ОБЩИМ ПОТОКОМ КОМАНД

Специальность 05.13.11 — Математическое и программное обеспечение машин н систем

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата технических наук

Москва — 1992 г.

Работа выполнена в ордена Ленина Институте проблем управления.

Научный руководитель — д. т. п., проф. ]Виленкин С. Я.

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

д. т. н., проф. Гливенко Е. В.

к. т. н., с. н. с. Бабичев А. В.

Ведущее предприятие —

Институт прикладной математики

Защита состоится « »..... 1992 г. в . . час.

на заседании специализированного совета № 2 (Д002.68.01) Института проблем управления : Москва, ул. Профсоюз-• ная, 65. Телефон совета: 334-93-29.

С диссертацией можно ознакомиться в библиотеке Института проблем управления.

Автореферат разослан: « »...... 1992 г.

Ученый секретарь специализированного совета канд. техн. наук

Е. В. Юркевич

I

I

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

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

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

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

Научная новизна работы. В диссертационной' работе исследованы особенности оптимизации программ для михропрограммируешх МВС с общим потоком команд.

Разработаны новые методы оптимизации программ для микропрограммируемых МВС с общим потоком команд в процессе генерации объектного кода. Предложены эффективные в • смысле времени выполнения алгоритмы, реализующие разработанные методы.

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

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

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

Апробация работы. Результаты работы докладывались на IV Всесоюзной школе-семинаре "Распараллеливание обработки информации", г.Львов, 1983г.;

конференции молодых ученых Института проблем управления, 1985г.;

v Всесоюзной школе-семинаре "Распараллеливание обработки информации", г.Львов, 1985г.;

7-ой Всесоюзной школе-семинаре "Параллельное программирование и высокопроизводительные системы", г.Киев, 1986г.:

- Vil Всесоюзной школе-семинаре "Распараллеливание обработки информации", г.Львов, 1989г.

Публикации. По материалам диссертационной работы имеется 7 опубликованных работ.

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

СОДЕРЖАНИЕ РАБОТЫ

Во введении обосновывается актуальность и формулируется цель диссертационной работы с учетом особенностей рассматриваемого класса систем.

В первой главе содержится концепция построения

иерархической системы компиляции программ для микропрограмми-руемых 'ЛВС с общим потоком команд.

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

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

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

- метод генерации циклов векторных вычислений,

- метод оптимизации использования' регистров общего назначения,

- метод локальной упаковки микроопераций.

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

Основную часть всех вычислений на МВС с общим потоком

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

На основании анализа возможных вариантов организации ЦВВ сформулированы критерии, которым должны удовлетворять эффективно организованные ЦВВ:

1. Векторные поэлементные вычисления должны быть организованы в минимальное количество ЦВВ.

2. Скалярные вычисления должны быть вынесены за пределы

ЦВВ.

3. Специальные вычисления должны быть вынесены за пределы ЦВВ.

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

1. Известные в настоящее время микропрограммируемые МВС имеют достаточно большое количество регистров общего назначения.

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

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

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

Учитывая, что упаковка микроопераций является одним из этапов оптимизации и выполняется на самом низком уровне по

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

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

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

Простым фрагментом назовем выражение, если оно является одной из следующих конструкций:

1. Выражение, содержащее только поэлементные векторные вычисления.

2. Выражение, содержащее только скалярные вычисления и специальные операции, определяющие скалярный результат.

3. Выражение, содераащее только специальные операции, определяющие векторный результат.

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

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

Для этого введены две функции:

оопс(с1,с2) - функция осуществляет конкатенацию цепочек кодов с1 и с2, результатом является цепочка, являющаяся лексикографической последовательностью цепочек С1 и с2;

оос1е(с) - функция завершает оформление кода о, и заменяет его в стеке кодов ссылкой на результат его выполнения.

Используя эти функции, типы операндов и операций генери-

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

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

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

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

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

Коротко алгоритм компиляции сводится к следующему:

1. Компилятор считывает очередную лексему.

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

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

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

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

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

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

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

Поток управления (система управляющих связей) в схеме представляется в виде управляющего графа - G(P,U), где Р -(P0tP,....pN) - множество вершин, соответствующих операторам, а и = (ut .^....и^) - множество ребер, задающих управляющие связи между операторами. В общем случае G(p,U) - представляет собой ориентированный граф с одной начальной веряиной - ро и одной конечной вершиной - рм (если конечных вершин несколько, то pN можно ввести как приемник всех этих верзил). Для правильных программ граф является связанным, т.е. для любой вершины е Р: 0<i<=N существует путь из р0 в pt.

Рассматривается двухуровневая общая память И, состоящая из множества ячеек, в каждой из которых можно разместить единицу данных. Уровни памяти различаются временем доступа и числом ячеек. Обозначим память нижнего уровня (оперативную память) - ом, а память верхнего уровня (регистры) - REG, тогда MEM = ом w REG. Время доступа к памяти типа REG существенно меньше времени доступа к памяти типа ом. При этом число ячеек памяти reg значительно меньше числа ячеек ом.

Глобальная задача распределения регистров для программы в целом может быть разбита на две подзадачи:

1.Задачу оптимизации использования регистров на линейном участке;

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

Такое разбиение задачи целесообразно как с точки зрения

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

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

Тогда с точки зрения управляющих связей можно рассматривать граф G(£,I), где Я = (Lt ,L2,...Ln) - множество вершин, соответствующих линейным участкам программы, а Ж = ,...Хш) - множество ребер, задающих передачу управления между ними.

Обозначим множества аргументов линейного участка l и его результатов соответственно A(L ) и в(ь ).

Размещением некоторого множества переменных в точке программы назовем совокупность адресов этих переменных в данной точке.

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

В конечной точке ь , являющегося непосредственным предшественником , размещение переменных из A(L ) может быть иным. Тогда для того, чтобы разместить переменные A(L ) на регистрах необходимо произвести ряд операций чтения из памяти и записи в память. Кроме того, в случае независимой генерации кодов для L и ь одноименные переменные, принадлежащие ЩЬ. ) и A(L ), могут размещаться на разных регистрах. Тогда для обеспечения правильности необходимо произвести ряд операций пересылки регистр-регистр. Обозначим совокупность этих операций ST.<1, .1) и назовем ее обобщенной операцией стыковки L. и 'L ,

j <■

В случае произвольной структуры возникают трудности, связанные с тем, что в начальную точку L - управление может передаваться из нескольких линейных участков. В этом случае необходимо в первую очередь оптимизировать те связи, которые реализуются чаще. Кроме того, возникает проблема, где размещать оператор SL(i, j) в L , или в ь . Ее решение также

зависит от того, какой из двух смежных линейных участков выполняется чаще, поскольку размещение оператора sb(i-,j) в режа выполняемом линейном участке снижает совокупное время выполнения программы.

Частоты выполнения элементов графа G(£,I ) предлагается

О ft h

оценивать векторами PL = (Fl, Fl,... Рь ), для вершин и

I t к I

О « ь

РХ = (Fx' Fx• • • • РХ ребер- \ . Рх е [0,1], для любых

J 1 1 1 i i

led ,n], jeH.ra], ke[0,h] оценивают частоту выполнения L и , соответственно, как элемента- циклических участков уровня вложенности к. Известен эффективный алгоритм подсчета векторов частоты исполнения для структурных программ.

Решение задачи размещения оператора стыковки сводится к решению еле,дующих двух подзадач:

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

2. Размещение оператора стыковки таким образом, чтобы он выполнялся как можно реже.

Для решения первой подзадачи разработана эвристическая процедура i'KOU_TRACE, осуществляющая выбор в управляющем графе пути, который на каждом шаге выбирает наиболее часто исполняемое ребро.

Вводится следующее отношение > на множестве векторов Р: ?L > Fl , если выполняются следующие условия: VI е CO.h]

£ >= F| И 3j е [0,h]: ?' > P,j ; Р, = Р, , если ViefO.hi

'■ж Ь1 S *"*

Р^ = р^. Для ребер отношение определяется аналогично.

1 2

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

-то-

пор, пока в качестве исходной вершины не будет выбрана р0.

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

Лемма Пусть \ и Ь, - вершины графа С(«,Х). \ -ребро, исходящее из Ь и заходящее в \, БЫ 1,2) - оператор стыковки ь с \. Тогда оптимальное размещение оператора 31,(1,2) определяется следующими условиями:

1. Если р, = Р^. и Р, < Р, ,то оператор БЬ(1,2) должен

<Г1 ** Ч '-А

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

. 2. Если = Р и Рь > Ри, то оператор БЬ(1,2) должен

г I >2

размещаться в начале \, образуя с ним один линейный участок с теш же связями в графе 0(£,£) что и Ъ2.

3. Во всех остальных случаях оператор БЬО,2) должен образовывать новый линейный участок с единственным предшественником и единственным приемником .

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

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

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

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

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

Общее время работы ТМ =» 0(п*га)+0(га(п+ш+п*Т11В)Х где п -число вершин графа управления, т.е. - число линейных участков т - число ребер, а тьв - время работы алгоритма для линейного

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

п п

торов лжейпого участка, выполняется ) = Р^^к.)), а ■

2(к )=Н, где N - число операторов исходной программы. Тогда ТМ = 0(п*т)+0(т(п+т+п*№)).

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

Рассмотрено устройство управления, используемое в МВС семейства ПС-2000.

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

Задача локальной упаковки состоит в том, чтобы по исходному тексту линейного участка программы, заданному в виде последовательности микроопераций то ,то2,...топ построить последовательность микрокоманд т!( ,ш12,...ш1т минимальной длины эквивалентную исходной в смысле получаемого результата для любых допустимых наборов входных данных. Иными словами требуется организовать совмещение микроопераций из МЬ с микрооперациями из ми, которое не нарушало бы заданных

исходной микропрограммой отношений информационного предшествования микроопераций.

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

Величина 1. задает время, которое ресурс г, (имеются ввиду регистры и триггеры) остается занятым при выполнении микрооперации шо1 . ^ . >=0 и выражается целым числом тактов системы. Случай когда означает, что то^ не использует ресурс г. .

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

ресурсов г. , для которых \.>0. Используя эту информацию определяется самый ранний такт, в который может исполнятся микрооперация ток. Для микроопераций другой зоны используется значение шах{^.}.

Время работы алгоритма пропорционально величине а*з*п, где а - число микроопераций в системе команд, Б - число используемых ими ресурсов. В системах типа ПС-2100 о и Б числа порядка Ю*. Однако, система обладает некоторыми особенностями, позволяющими улучшить характеристики алгоритма.

С одной стороны каждая микрооперация использует небольшое число рисурсов. С другой стороны большинство микроопераций занимает ресурсы один такт. Тогда если г. 1 -0 или э'-й ресурс не влияет на значение шах{1 . ,т+1}. При этом объем необходимой информации существенно сокращается. Для ПС-2100 получается 0=80, Б=8.

следует отметить, что исключение элементов \, =1 возможно лишь в случае сохранения исходного линейного порядка следования микроопераций внутри каждого из полей, что

несколько снижает качество получаемого результата.

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

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

Среднее значение получаемого от применения алгоритма выигрыша по длине программы и времени выполнения составляет 18-25%. Результат можно улучшить, если воспользоваться многозональным вариантом данного метода.

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

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

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

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

Для определения качества работы алгоритма с точки зрения использования памяти микропрограмм был рассмотрен самый "плохой" случай, когда каздая последующая микрооперация использует результат предыдущей. При этом коэффициент использования памяти в результате работы алгоритма составил 72,75%. Средний коэффициент использования памяти микропрограмм при применении алгоритма составляет 90$, при этом отклонение от оптимального результата по памяти составило 2%, а по • времени - Ю%.

В заключении приведены основные выводы и результаты, полученные в диссертационной работе.

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

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

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

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

используемых для линейных участков.

5. Предложен новый алгоритм локальной упаковки микроопераций для многозонального устройства микропрограммного управления, используемого в МВС семейства ГТС-2000, с линейно-ограниченкым временем работы.

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

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

Основное содержание диссертации отражено в следующих опубликованных работах:

1. Гонсалес-Менендес Е.А. Организация эффективного выполнения микропрограммы устройствами многопроцессорной вычислительной системы. - Тезисы докладов IV всесоюзной сколц-семянара "Распараллеливание обработки информации". Львов, 1983.

2. Гонсалес-Менендес Е.А. Операторный символический язык программирования параллельных систем (ОСПС). - Тезисы докладов V всесоюзной школы-семинара "Распараллеливание обработки информации". Львов, 1985.

3. Гонсалес-Менендес Е.А. Комплексный подход к повышению качества программ для высокопроизводительных систем в процессе трансляции. - Тезисы докладов 7-ой всесоюзной сколы

семинара "Параллельное программирование * и высокопроизводительные системы" Киев, 1986.

4. Гонсалес-Менендес Е.А. Алгоритм многозональной упаковки с помощью указателей. - Тезисы докладов VII всесоюзной школы-семинара "Распараллеливание обработки информации". Львов, 1989.

5. Гонсалес-Менендес Е.А., Куприянов Б.В. Эффективная генерация кодов векторных вычислений в вычислительных системах типа ОКМД. - Программирование, М.: 1991, й1, о. 49- 57.

6. Гонсалос-Менендес Е. А. Метод статического распределения регистров, учитывающий частоту выполнения линейных участков программы. - Параллельные алгоритмы и программы для ЭВМ с общим управлением: Сб. тр. - М.: Институт проблем управления. 1901, с. 35-41.

7. Гонсалэс-Менвндес Е.А., Лапикова О.И. Метод локальной упаковки микроопераций с линейно-ограниченным временем работы. - Параллельные алгоритмы и программы для ЭВМ с общим управлением: Сб. тр. - М.: Институт проблем управления. 1991, с. 42-45.

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

В работе [Б], написанной в соавторстве, автором предложен метод генерации эффективных кодов векторных вычислений.

В работе [7] автором разработан метод локальной упаковки микроопераций.