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

САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

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

Булычев Дмитрий Юрьевич

ПРОТОТИПИРОВАНИЕ ВСТРОЕННЫХ СИСТЕМ НА ОСНОВЕ ОПИСАНИЯ МАКРОАРХИТЕКТУРЫ

05.13.11 — Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей

АВТОРЕФЕРАТ

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

Санкт-Петербург 2004

Работа выполнена на кафедре системного программирования математико-механического факультета Санкт-Петербургского государственного уни-

верситета.

Научный руководитель: доктор физико-математических наук,

профессор Терехов Андрей Николаевич

Официальные оппоненты: доктор физико-математических наук,

профессор Марчук Александр Гурьевич

кандидат технических наук Иванов Владимир Николаевич

Ведущая организация: Институт системного программирования

РАН

Защита диссертации состоится "2Л " 2004 года в_часов на

заседании диссертационного совета Д212.232.51 по защите диссертаций на соискание ученой степени доктора наук при Санкт-Петербургском государственном университете по адресу: 198504, Санкт-Петербург, Старый Петергоф, Университетский пр., д. 28, математико-механичеокий факультет Санкт-Петербургского государственного университета.

С диссертацией можно ознакомиться в Научной библиотеке Санкт-Петербургского государственного университета по адресу: 199034, Санкт-Петербург, Университетская наб., д. 7/9.

Автореферат разослан "__"_2004 года.

Ученый секретарь

диссертационного совета

доктор физико-математических наук,

профессор Б.К.Мартыненко

AûOG- V 3&Ï3

Общая характеристика работы Актуальность темы

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

Одним из способов построения систем обсуждаемого типа является разработка специфических для данного приложения процессоров (ASIP — Application-Specific Instruction Set Processor) [14]. Несмотря на то, что современные технологии разработки процессоров позволяют реализовать на уровне оборудования практически произвольно сложные алгоритмы, программируемые процессоры, реализующие сравнительно простые системы команд, продолжают тттироко использоваться.

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

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

ТбОбРК

РОС. НМЛ.З'НЛЬНАЯ ьиг 'я iTtKA С. Петербург

ми — то есть, фактически, разработать систему команд и написать в ее терминах программу1.

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

сания процессора. Обе эти задачи рассматриваются в современной специальной литературе.

Изучение существующих подходов к настройке компиляторов на другую аппаратную платформу выявило их незрелость применительно к исследуемой области [2] Именно, все эти подходы обеспечивали настраиваемость только при условии существенного объема ручных изменений, и, следовательно, сравнительно большого времени настройки. Все они, кроме того, требовали описания системы команд процессора на специальном формализме, непригодном ни для чего иного, кроме порождения кодогенератора Изучение возможности порождения такого описания из низкоуровневого описания устройства показало существенное падение качества кодогенератора [9].

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

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

образом, является обобщением исходной задачи, причем обобщением "сверх необходимого".

Цели работы

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

Общая методика

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

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

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

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

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

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

Научная новизна

Все основные научные результаты диссертации являются новыми.

Практическая и теоретическая ценность

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

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

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

На практике предложенные методы были использованы ири создании сред ства прототипирования встроенных систем.

Апробация работы

Результаты работы докладывались на семинаре по технологии компиляции (2004 год, г Великий Новгород) и семинаре Института системного программирования РАН (2004 год, 1. Москва).

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

Публикации

Основные результаты диссертации изложены в 4-х работах, перечисленных в конце автореферата.

Структура и объем диссертации

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

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

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

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

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

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

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

Граница между макро- и микроархитектурой таким образом может перемещаться между двумя крайними случаями, одним из которых является ситуация, когда целевая программа написана на языке описания оборудования (и, следовательно, макроархитектура совпадает с микроархитектурой), а другим — когда процессор является интерпретатором исходного языка (например, аппаратная ^уа-машина). Поэтому в каждом конкретном случае необходимо заранее договориться, где именно проходит эта граница. Если исходная программа реализована на императивном языке высокого уровня (например, С), то на уровень макроархитектуры устройства попа-

дают следующие элементы:

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

• режимы адресации;

• набор команд, их семантика, правила порождения двоичного кода и ассемблерного представления.

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

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

Наконец, из описания макроархитектуры автоматически порождается спецификация микроархитектуры на одном из языков описания оборудования (например. VHDL).

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

Во второй главе рассмотрены существующие языки описания архитектуры вычислительных устройств и введен язык описания макроархитектуры PADL (Processor Architecture Description Language).

Современная классификация этих языков [13, 8] делит их на три основных типа:

1. языки структурного описания,

2. языки поведенческого описания;

3. языки смешанного типа

Под структурным описанием понимается описание устройства в терминах v набора функциональных блоков (простейших устройств) и связей между

' ними При этом описываемое устройство может вообще не быть про-

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

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

Наконец, сметанный тип спецификации содержит черты двух этих подходов.

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

С точки зрения совокупности черт предлагаемый формализм наиболее близок к языкам Л-RTL [12] и nML [4, 5] Так, принцип ортогонального описания инструкций и явной спецификации вг-ех побочных эффектов, полиморфная типовая система и вывод типов напоминают A-RTL, в то же * время соединение описания семантики, правил порождения ассемблерного

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

■)

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

большую свободу для синтеза микроархитеклуры. Заметим также, что параллелизм на уровне инструкций и конвейеризация — это свойства именно микроархитектурной реализации, в значительной степени не имеющие отношения к системе команд. Поэтому все попытки увязать вместе два этих уровня в рамках единого формализма ведут к компромиссам, усложняя описание макроархитектуры, сужая возможности порождения эффективной низкоуровневой модели и все равно не позволяя добиться точного поведения симулятора. Отсутствие средств спецификации параллелизма на уровне инструкций (instruction-level parallelism, ILP) является не недостатком (или недоработкой), а логическим следствием того, что такой параллелизм есть свойство микроархитектурной реализации, слабо проявляющее себя на уровне системы команд.

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

Далее описан предлагаемый в диссертации алгоритм разложения исходной программы на систему команд и исполняемый машинный код. С целью точного анализа задачи она бы ia сформулирована в терминах деревянных грамматик [3] и систем восходящего переписывания деревьев [1, 6, 7, 10, 11].

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

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

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

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

Заключительная часть главы посвящена обсуждению характеристик предлагаемого подхода и изложению результатов апробации Описанный алгоритм был реализован и испробован на подмножестве тестового набора ОЗР81;опе [15]. Результаты апробации показывают, что даже при отсутствии ограничений на сложность индивидуальных машинных команд синтез системы команд занимает время, сравнимое с временем обычной компиляции. В результате получается прототип системы, состоящий из машинного кода и описания макроархитектуры. Длина порожденного кода в целом существенно превышает длину эталонной реализации, написанной вручную; в то же время полученные машинные программы оказались существенно короче программ, сгенерированных для стандарнтых архитектур с помощью специализированных компиляторов.

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

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

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

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

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

Список литературы

[1] Aho A.V., Ganapathi М., Tjiang S.W.K. Code Generation Using Tree Matching and Dynamic Programming // ACM Transactions on Programming Languages and Systems. — 1989. — Vol. 11, No 4 — P. 491516.

[2J Boulytchev D., Lomov D. An Empirical Study of Retargetable Compilers // Proc. of 4th International Andrei Ershov Memorial Conference on Perspectives of System Informatics. LNCS 2244. - P. 328-331.

[3] Comon H., Dauchet M. et al. Tree Automata Techniques and Applications // http://www.grappa.univ-lille3.fr/tata

[4J Fauth A. Beyond Tool-Specific Machine Description // Code Generation for Embedded Processors. — Kluwer Academic Publishers. — 1995. — P. 138-152.

[5] Fauth A., Van Praet J , Freenckb M. Desciibing Instruction Set Processors Using nML // Proc. on the European Design and Test Conference. — 1995.

P. 503-507.

|6] Fraser C.W., Hanson D.R.. Proebsting T.A. Engeneenng a simple, efficient code generator generator // ACM Letters on Programming Languages and Systems. - 1992. Vol. 1, No. 3 - P. 213-226.

[7] Fraser C.W., Henry R.R, Proebsting T.A. BURG - Fast Optimal Instruction Selection and Tree Parsing // SIGPLAN Notices. — 1992. — Vol. 27, No. 4 - P. 68-76.

[8] Halambi A., Grun P., Tomiyama H., Dutt N., Nicolau A. Automatic Software Toolkit Generation for Embedded Systems-on-Chip // Proc. ICVC-99, Seoul. Korea. - October 1999.

[9] Leupers R., Marwedel P. Retargetable Generation of Code Selectors from HDL Processor Models // Proc. of the 1997 European Design and Test Conference. - 1997. P. 140-144.

[10] Pelegri-Llopait E , Graham S.L. Optimal Code Generation for Expression Trees: An Application of BURS Theory // Proceedings of the Conference On Principles of Programming Languages. — 1988. P. 294-308.

[11] Proebsting T.A. BURS Automata Generation // ACM Transactions on Programming Languages and Systems — 1995. — Vol. 17, No 3 — P. 461486.

[12] Ramsey N., Davidson J.W. Specifying Instructions' Semantics Using A-RTL (Interim Report). — http://www.es. virginia.edu/zephyr/csdl/lrtlindex. html.

[13] Tomiyama H., Halambi A., Grun P, Dutt N., Nicolau A. Architecture Description Languages for Systems-on-Chip Design // Proc. ICVC-99, Seoul, Koiea. October 1999.

[14] Weaver C., Krishna R, Wu L., Austin T. Application Specific ^ Architectures' a Recipe for Fast, Flexible and Power Efficient Designs

// Proc of the International Conference on Compilers, Architecture, and !

Synthesis sfor Embedded Systems. - 2001. - P. 181-185.

[15] Zivojnovic V., Martinez J., Schlager С., Meyr H. DSPstone: A DSP-Oriented Benchmarking Methodology // Proc. of ICSPAT'94. 1994.

Работы автора по теме диссертации

1. Булычев Д.К) Разработка алгоритма взаимного синтеза целевой про-1раммы и системы команд для реализации программно-аппаратных систем // Восьмая Санкт-Петербургская ассамблея молодых ученых и специалистов. СПб.: 2003 — с. 20.

2. Булычев Д.Ю Разработка программно-аппаратных систем на основе описания макроархитектуры // Системное программирование. — СПб.: 2004. - с. 7-22

3. Булычев Д.Ю. Язык описания макроархитектуры для технологии совместной программно-аппаратной разработки // Системное программирование. — СПб.: 2004. - с. 23-48.

4. Boulytchev D , Lomov D An Empirical Study of Retargetable Compilers // Proc. of 4th International Andrei Ershov Memorial Conference on Perspectives of System Informatics. - 2001. - LNCS 2244. - P. 328331

Подписано к печати 01 11.2004 г Формат бумаги 60X84 1/16 Бумага офсетная. Печать риюграфическая. Объем 1 усл. п. л. Тираж 100 экз. Заказ 3397. Отпечатано в отделе оперативной полиграфии НИИХ СПбГУ с оригинал-макета заказчика 198504, Санкт-Петербург, Старый Петергоф, Университетский пр 26.

РНБ Русский фонд

2006-4 3273

19 НОЯ