BC/NW 2008, №2 (13): 2.2

ФУНКЦИОНАЛЬНАЯ МОДЕЛЬ ПРОЦЕССОРА НЕТРАДИЦИОННОЙ АРХИТЕКТУРЫ С ВНУТРЕННИМ ЯЗЫКОМ ВЫСОКОГО УРОВНЯ

Нехай И. В., науч. рук. Фальк В. Н.

(Московский Энергетический Институт (технический университет), Москва, Россия)

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

Одним из факторов, усложняющих разработку программного обеспечения, является наличие существенных различий между понятиями операций и их объектов для языков высокого уровня и понятиями операций и их объектов, определяемыми архитектурой конкретного компьютера. Это обстоятельство получило название семантического разрыва. Иначе говоря, если на языке высокого уровня можно описать различные операции и типы данных, то при реализации программ в вычислительной машине классической фон-неймановской архитектуры разницы между представлениями всех этих объектов фактически нет, что усложняет трансляцию и, особенно, дальнейшую отладку программ. Одним из известных решений этой проблемы является добавление ко всем данным информации, необходимой для того, чтобы идентифицировать способ их обработки. Эта дополнительная информация называется «тег» (от английского ‘признак’ – tag). Так, например, различные типы данных характеризуются своими особыми тегами, а однотипные команды, отличающиеся только типом операндов, никак не различаются.

В языках программирования этот принцип развивается в идее полиморфизма. В современных ЭВМ для реализации полиморфизма используется динамическая проверка типа (dynamic type checking), выполняемая программно и организуемая заранее при компиляции. Аппаратная реализация проверки типов с помощью тегов должна позволить ускорить выполнение виртуальных методов объектно-ориентированных ЯВУ.

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

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

На базе новых архитектурных принципов, основанных на идее структурной интерпретации языка высокого уровня, были созданы отечественные ЭВМ «Украина», МИР, МВК семейства Эльбрус.

Развитие идеи структурной интерпретации языков программирования высокого уровня продолжилось в работах В. Н. Фалька, который в 1987 г. опубликовал теоретическую модель языков высокого уровня FALGOL [1], имеющую «двойное применение»: как модель языков программирования высокого уровня, а также как модель архитектуры перспективных ЭВМ с внутренним ЯВУ.

FALGOL (Formal ALGOrithmic Language) – фундаментальная теоретическая модель операторных языков высокого уровня, предложенная В. Н. Фальком [1], с неограниченной иерархией программных объектов, формализующая связывание, присваивание, подстановку и рекурсию, причем в отличие от других известных формальных систем такого рода в этой модели реализован принцип динамического связывания переменных, что открывает возможность применения FALGOLа для уточнения наиболее трудно формализуемых понятий современных языков объектного программирования, разработки языков высокого уровня и объектно-ориентированной архитектуры вычислительных машин.

Основной особенностью модели FALGOL, упрощающей применение её для разработки языков программирования и вычислительных систем, является то, что она не ориентирована на какой-либо конкретный язык программирования либо конкретную архитектуру ЭВМ, являясь строгим формальным описанием наиболее общих, фундаментальных механизмов реализации ЯВУ, инвариантных относительно того, какой – аппаратной или программной эта реализация будет являться.

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

На основе модели FALGOL были разработаны модель и язык программирования базовой вычислительной машины (БВМ) [2]. Однако в БВМ не были предложены расширения, позволяющие формализовать понятия класса, объекта, полиморфизма, наследования современных объектно-ориентированных языков программирования, что является одной из основных целей данной работы.

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

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

·        Тегированное представление команд и данных

·        Эквивалентные преобразования программы во время вычислений, направленные на сокращение числа выполняемых операций

·        Стековый принцип обработки, т.е. размещение операндов в стеке

·        Переменный формат команды, обеспечивающий высокую компактность программного кода.

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

 

Данная работа преследует три основных цели:

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

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

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

Построение внутреннего языка путём расширения FALGOL гарантирует независимость результата от какого-либо языка программирования или архитектуры ЭВМ. Принцип непротиворечивого расширения в рамках FALGOL и тегированного представления сводится к тому, что:

1.     Требуемое расширение выражается в примитивах FALGOL.

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

3.     Для расширения вводится новый тег (теги), с учётом возможных оптимизаций.

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

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

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

Согласно [3], тегированное представление данных и инструкций эффективно и, соответственно, имеет смысл только тогда, когда оно используется аппаратурой для реализации специальных алгоритмов, таких как:

·        оптимизация во время исполнения

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

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

Динамическое выделение памяти переменных происходит при первом обращении к переменной.

·        сборка мусора

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

·        сокращение набора инструкций за счёт принципа ассоциативного управления

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

 

По основным целям работы были достигнуты следующие результаты:

·        Формализовано понятие объекта в рамках модели FALGOL и разработано тегированное представление программных объектов языка.

Тегированное представление программных объектов соответствует представлению в современных языках программирования классов и объектов с помощью таблиц виртуальных методов (VMT) и информации о типе во время выполнения (runtime type information, RTTI).  Фактически, объект представляет собой программный объект, содержащий некий набор данных. Этот набор данных одинаков по структуре и (в общем случае) отличается по содержанию между всеми объектами заданного класса. Тегом этого объекта будет являться указатель на размещение в памяти его класса. Класс определяет структуру объектов и набор их методов.

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

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

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

·        Разработана функциональная схема и алгоритм реализации рабочего цикла процессора смешанных вычислений.

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

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

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

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

 

Планируется дальнейшее развитие описанной модели. В дальнейшем развитии видны следующие шаги:

·        Распараллеливание/конвейеризация основных системных алгоритмов с целью ускорения их работы.

·        Реализация основных системных алгоритмов непосредственно на языке моделируемой машины. Такая реализация аналогична микропрограммам (firmware) большинства современных процессоров и контроллеров.

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

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

·        Разработка имитационной модели, т.е. программной модели, непосредственно имитирующей функционирование оборудования FALGOL-машины. Для разработки этой модели могут быть использованы языки типа VHDL/Verilog

ЛИТЕРАТУРА

1.     Фальк В.Н. FALGOL - теоретическая модель языка программирования высокого уровня // Программирование, №4, 1987. – С. 3-12

2.     Чернов С.А. «Исследование и реализация базовой вычислительной машины с внутренним языком высокого уровня», дисс. на соиск. уч. степени кандидата технических наук: 05.13.15, Москва, МЭИ, 2003 г.

3.     Edward F. Gehringer, J. Leslie Keedy «Tagged Architecture: How Compelling Are its Advantages? », Special Issue: Proceedings of the 12th annual international symposium on Computer architecture (ISCA '85), Volume 13, Issue 3 (June 1985), стр. 162-170, ISSN: 0163-5964

4.     «The Direct Cost of Virtual Function Calls in C++», Karel Driesen and Urs Hölzle, Department of Computer Science, University of California, Santa Barbara, CA 93106