Введение к работе
Актуальность темы
Основной задачей разработки программно-аппаратных систем является построение "подходящей" реализации некоторого набора алгоритмов. Использованный здесь неформальный термин "подходящий" объединяет много факторов, обычно принимаемых во внимание, например, производительность, энергопотребление, стоимость, вес и т.д. Мы ограничимся случаем, когда нужный набор алгоритмов представлен в виде программ на языке высокого уровня, поскольку этот способ описания представляется наиболее полезным среди всех возможных.
Одним из способов построения систем обсуждаемого типа является разработка специфических для данного приложения процессоров (ASIP — Application-Specific Instruction Set Processor) [14]. Несмотря на то, что современные технологии разработки процессоров позволяют реализовать на уровне оборудования практически произвольно сложные алгоритмы, программируемые процессоры, реализующие сравнительно простые системы команд, продолжают широко использоваться.
Существуют две основные причины этого. Во-первых, программируе-мость позволяет обеспечить гибкость. Система, построенная на программируемом процессоре (интерпретаторе) позволяет исполнять потенциально неограниченный набор программ. Во-вторых, система команд позволяет переиснользовать мощности процессора. Поскольку гибкость и универсальность в интересующей нас области отходят на второй план (в силу ограниченности множества программ, исполняемых на встроенном устройстве), остановимся подробнее на переиспользовании.
Пусть нас интересует реализация какого-либо алгоритма в виде непрограммируемого устройства, обладающего таким же поведением, как и некоторая программа Простейшим путем его реализации является синтез из поведенческой спецификации на каком-либо языке описания оборудования (например, VHDL). При прямолинейном написании такой спецификации синтезированное устройство практически всегда окажется сильно избыточным. Например, разные вхождения одного и того же выражения в описание поведенческой модели приведет к синтезу разных устройств, его реализующих. Во избежание этого придется разбить исходную спецификацию на похожие фрагменты и реализовать соответствующую диспетчеризацию между ни-
РОС. НМЛ'Й'КЛЬНАЯ
ЬИГ 'я іТЬКА
С. Петербург
гвобрк
ми — то есть, фактически, разработать систему команд и написать в ее терминах программу1.
Подобная факторизация на уровне микроархигектуры (т.е. аппаратной ре
ализации) в свою очередь ведет к сложной проблеме — настройке компиля
тора и оптимизатора. Для ее решения либо необходимо поддерживать со
ответствие между программой и факторизуемой микроархитектурой, либо
научиться автоматически извлекать кодогенератор из поведенческого они- і
сания процессора. Обе эти задачи рассматриваются в современной специальной литературе.
Изучение существующих подходов к настройке компиляторов на другую аппаратную платформу выявило их незрелость применительно к исследуемой области [2] Именно, все эти подходы обеспечивали настраиваемость только при условии существенного объема ручных изменений, и, следовательно, сравнительно большого времени настройки. Все они, кроме того, требовали описания системы команд процессора на специальном формализме, непригодном ни для чего иного, кроме порождения кодогенератора Изучение возможности порождения такого описания из низкоуровневого описания устройства показало существенное падение качества кодогенератора [9].
С другой стороны, оказалось, что подход, основанный на предварительном выборе базовой архитектуры с последующей настройкой компилятора страдает от любопытного принципиального недостатка: несмотря на то, что базовая архитектура выбирается с тем. чтобы целевое приложение компилировалось в нее наиболее естественным образом, сложность задачи генерации кода при этом не уменьшается, а возрастает Иными словами, сперва должны быть затрачены некоторые усилия на то, чтобы определить основные черты базовой архитектуры, а затем — чтобы настроить на нее компилятор, при этом последняя задача может оказаться весьма сложной в силу того, что прагматические соображения, принятые во внимание при выборе архитектуры, недоступны компилятору. Наконец, приведем еще одно принципиальное соображение: в то время как свойства базовой архитектуры определяются исходя из "интересов" конкретного целевого приложения, компилятор для этой архитектуры должен по существу порождать эффективный код для любой программы Задача настройки компилятора, таким
1Современные методы порождения высокоэффек гигшого устройства по поведенческому описанию включают в себя < іадию оптимизации, которая может существенно сниш іь избыточность порождения Одинако і дубина и состав этих оптимизаций не позволяет рассматривать их как среде гво выделения системы команд
образом, является обобщением исходной задачи, причем обобщением "сверх необходимого".
Цели работы
Целями работы являются: разработка подхода, который обеспечивал бы возможность быстрого получения прототипа встроенной системы (машинного кода и описания системы команд) непосредственно по тексту программного обеспечения на языке высокого уровня; разработка универсального языка описания вычислительного устройства на уровне системы команд; построение алгоритма разложения исходной программы на машинный код и систему команд.
Общая методика
Работа проводилась в контексте общих методов техники трансляции, разработки встроенных систем и систем команд программируемых процессоров. Рассматривались известные технологические подходы к разработке встроенных систем, языки описания устройств, алгоритмы порождения эффективных систем команд. Для обоснования результатов работы использовалась формальная модеть на основе деревянных грамматик оценка применимости полученных алгоритмов осуществлялась экспериментально.
Основные результаты
В работе получены следующие основные результаты:
предложен технологический подход к прототипированию встроенных систем, основанный на понятии макроархитектуры устройства, сформулированы требования к языку описания макроархитектуры:
разработан язык описания макроархитектуры устройства, удовлетворяющий всем сформулированным выше требованиям:
разработан алгоритм синтеза макроархитектуры устройства из текста программы на языке высокого уровня, сопровождающегося порождением готового к исполнению машинного кода
Научная новизна
Все основные научные результаты диссертации являются новыми.
Практическая и теоретическая ценность
Сформулирован технологический подход, позволяющий быстро получать прототип встроенной системы непосредственно из текста программного обеспечения на языке высокого уровня.
Описан универсальный язык спецификации вычислительного устройства на уровне системы команд, позволяющий автоматически порождать все необходимые средства разработки.
Предложен алгоритм полного перечисления всех частичных поддеревьев в заданном абстрактном синтаксическом дереве программы, что позволяет описать всевозможные его разбиения и, следовательно, решить задачу выбора системы команд.
На практике предложенные методы были использованы при создании сред ства прототипирования встроенных систем.
Апробация работы
Результаты работы докладывались на семинаре по технологии компиляции (2004 год, г Великий Новгород) и семинаре Института системного программирования РАН (2004 год, і. Москва).
Предложенная технология была реализована в виде набора технологических средств для прототипирования встроенных систем.
Публикации
Основные результаты диссертации изложены в 4-х работах, перечисленных в конце автореферата.
Структура и объем диссертации
