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

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

ЧЕРНОВ Сергей Александрович

ИССЛЕДОВАНИЕ И РЕАЛИЗАЦИЯ БАЗОВОЙ ВЫЧИСЛИТЕЛЬНОЙ МАШИНЫ С ВНУТРЕННИМ ЯЗЫКОМ ВЫСОКОГО УРОВНЯ

Специальность 05.13.15 - Вычислительные машины и системы

АВТОРЕФЕРАТ

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

Москва - 2003 г.

Работа выполнена на кафедре Вычислительных машин, систем и сетей Московского энергетического института (технического университета).

Научный руководитель - кандидат технических наук, доцент Мороховец Юрий Евгениевич

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

- доктор технических наук, профессор Фальк Вадим Николаевич

- кандидат технических наук, доцент Логинов Вадим Александрович

Ведущая организация - АО Научно-технический центр "Модуль" (г. Москва)

Защита состоится 17 октября 2003 г. в 16 ч. 00 мин., в ауд. Г-306 на заседании диссертационного совета Д 212.157.01 при Московском энергетическом институте (техническом университете) по адресу: 111250, Москва, Красноказарменная ул, д. 17.

С диссертацией можно ознакомиться в библиотеке МЭИ (ТУ).

Автореферат разослан " 8 " сентября 2003 г.

Отзывы в двух экземплярах, заверенные печатью организации, просьба направлять по адресу: 11250, г. Москва, Красноказарменная ул., д. 14, Учёный совет МЭИ (ТУ).

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

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

к.т.н., профессор

Ладыгин И.И.

I J277

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

Диссертационная работа посвящена исследованию возможности создания вычислительной машины с внутренним языком высокого уровня (ЯВУ). Создание машинного ЯВУ и ЭВМ, являющейся его аппаратным интерпретатором, позволит решить проблему семантического разрыва между архитектурами машин и ЯВУ. Соответственно, машинный язык высокого уровня будет играть роль стандартного интерфейса между языками высокого уровня и аппаратурой ЭВМ. В диссертации рассматриваются проблемы выбора базового машинного языка (БМЯ) высокого уровня; разрабатывается БМЯ; формулируются принципы создания архитектуры ЭВМ, интерпретирующей БМЯ; на основе этих принципов разрабатывается базовая вычислительная машина (БВМ), являющаяся прототипом ЭВМ с внутренним ЯВУ. В качестве основы процесса разработки БМЯ и БВМ используется не какой-либо широкораспространенный ЯВУ, а теоретический язык FALGOL, имеющий простой синтаксис, операционную семантику, описанную в виде алгоритма работы абстрактной FALGOL-машины (AM) и трансформационную семантлку, описанную в виде набора аксиом.

Актуальность темы исследования

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

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

Развитие технологии элементной базы ЭВМ, основанной на современных физических принципах, не может продолжаться бесконечно долго и в силу известных ограничений, рано или поздно, этот фактор повышения производительности будет исчерпан. По-видимому, именно с этого момента проблема повышения эффективности выч!-слтельно-го процесса за счет применения новых принципов его opi-анизации cTMrerjgjJJ^ юй и,

возможно, тогда начнется активное развитие и внедрение алкгерн^афда^архи'

J по чм-? ■кдЗЬ

естур

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

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

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

Цель и задачи работы

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

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

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

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

• разработка принципов создания БВМ с внутренним ЯВУ;

• разработка структуры БВМ, структуры ситуационного дешифратора команд,

процессора и компонентов памяти;

• разработка системы команд БВМ и алгоритмов выполнения каждой кз команд;

• разработка алгоритма машинного цикла БВМ;

• разработка алгоритма функционирования БВМ в целом;

• исследование и реализация метода компактного представления структур данных, поиск эффективных алгоритмов их обработки;

• исследование и реализация эффективных методов обработки рекурсивных процедур, удаления неконстангных процедур и команд вызовов переменных;

• создание программной модели БВМ;

• разработка языка ассемблера БВМ;

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

Методы исследования

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

Научная новизна основных результатов

1) Модифицирована и расширена элементарными константами теоретическая модель языков высокого уровня FALGOL. На основе этой модели разработан базовый машинный язык высокого уровня и программно, на платформе Intel х86, MS Y/indows 98, реализован его интерпрешшр - базовая вычислительная машина, являющаяся прототипом ЭВМ с внутренним ЯВУ. Создание такой ЭВМ, предполагается, позволит; • ■

• решить проблему семантического разрыва, препятствующую полному переводу программирования на ЯВУ;

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

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

3) Сформулирован и опробован на практике новый подход к организации вычис-

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

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

• эквивалентные преобразования программы во время вычислений, направле i-ные на сокращение числа выполняемых операций и времени выполнения программы;

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

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

Достоверность основных результатов работы

Достоверность основных результатов работы подтверждается следующим:

• результатами изучения БВМ и БМЯ с использованием разработанной программной модели БВМ и других средств программного комплекса Falgol Virtual Machine (FVM), на наборе реальных задач;

• апробацией основных результатов на конференциях, в том числе не. Международной конференции "Информационные средства и технологии" (Москва, 2000, 2001, 2002), на Международной научно-технической конференции студентов и аспирантов "Радиоэлектроника, электротехника и энергетика" (Москва, 2001, 2002, 2003), на 49-й и 50-й научно-технических конференциях МИРЭА (Москва, 2000, 2001), а также выступлением с докладом в московском представительстве фирмы LG (Москва, 2001);

• внедрением результатов выполненных исследований в учебный процесс каоед-ры ВМСиС МЭИ(ТУ).

Результаты работы, выносимые на защиту

1) Принципы создания БВМ с внутренним ЯВУ.

2) Структура, система команд и алгоритмы функционирования БВМ.

3) Язык ассемблера БВМ, структура, система команд и алгоритмы функционирования виртуальной машины компилятора (ВМК), оптимизатор машинного кода (ОМК).

4) Принципы построения программной функциональной модели БВМ и программного комплекса FVM.

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

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

• БВМ реализована в виде программной модели и интегрирована а программный

комплекс ГУМ, обладающий полным набором средств, необходимых для дальнейшего исследования и развшия БВМ в направлении реальной ЭВМ с внутренним -ЯВУ.

• Комплекс программ РУМ доведен до уровня программного средстЕа учебно, о назначения (ПСУН) и может быть применен в учебном процессе кафедр МЭИ (ТУ) для углубленного изучения принципов работы вычислительных машин с внутренним ЯВУ.

Реализация результатов работы

Разработан программный комплекс ГУМ, включающий программную модель БВМ, ВМК, ОМК, средства отображения и изменения состояния БВМ, среду программирования на ассемблере БВМ. Программный комплекс может использоваться для исследования и изучения БМЯ, создания и отладки программ на БМЯ в отсутствии аппаратно реализованной БВМ, а также в качестве основы для дальнейшего совершенствования БМЯ и БВМ.

Результаты диссертационной работы внедрены в учебный процесс кафедры ВМСиС МЭИ (ТУ). Комплекс программ ГУМ доведен до уровня программного средства учебного назначения и будет применяться в учебном процессе кафедры ВМОС, начиная с 2003/2004 учебного года при проведении лабораторных работ по курсу "Высокопроизводительные вычислительные системы".

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

Основные результаты работы докладывались на Международных конференциях "Информационные средства и технологии" (Москва, 2000, 2001, 2002), па Международных научно-технических конференциях студентов и аспирантов "Радиоэлектроника, электротехника и энергетика" (Москва, 2001, 2002, 2003), на 49-й и 50-й научно-технических конференциях МИРЭА (Москва, 2000. 2001), а также в московском представительстве фирмы ЬС (Москва, 2001).

Публикации

Всего по теме диссертации опубликовано 8 научных трудов.

Структура и объём работы

Диссертация состоит из введения, восьми глав, заключения, списка использованных источников и семи приложений. Общий объем 220 е., из них основного текста 174 е., список источников из 55 наименований, 28 рисунков, 30 таблиц.

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

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

В первой главе рассмотрены предпосылки к созданию ЭВМ с внутренним ЯВУ. Проведено сравнение ЯВУ с языком ассемблера традиционных ЭВМ имеющих фо:;-Неймановскую архитектуру. Выделены основные свойства ЯВУ, определяющие их преимущества перед ассемблером и основные недостатки ЯВУ, сдерживающие их применение. Проведен анализ недостатков статической компиляции ЯВУ, осуществляемо?, на традиционных машинах, в частности, основанных на процессорах Intel х86. Проанализированы недостатки разработанных машин языков высокого уровня, таких как Lisp-, Prolog- и Рефал- машины.

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

- возможность создания эффективных интерпретаторов БМЯ;

- эффективное представление средствами БМЯ конструкций как можно большего числа ЯВУ ;

- возможность создания простых компиляюров в БМЯ с ЯВУ различных типов.

В качестве отправной точки при разработке БМЯ можно попытаться использовать

какой-либо существующий ЯВУ, но в этом случае возникают следующие трудности:

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

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

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

БВМ - это интерпретатор БМЯ. Сформулируем основные требования к БВМ:

- высокий уровень базового машинного языка;

- независимость БМЯ от аппаратуры БВМ;

- компактность программного кода, при максимально полном представлении структуры программы;

- универсальность применения;

- возможность эффективной аппаратной реализации на существующей элементной базе (предполагается реализация БВМ в интегральном виде на СБИС).

Исследование возможности создания БВМ, отвечающей этим требованиям - основная задача диссертации.

При разработке БМЯ и БВМ (рис. 1), в данной работе применяется "эльбрусов-ский" подход к созданию архитектур вычислительных систем. Так же как и при разработке многопроцессорного вычислительного комплекса (МВК) Эльбрус при выборе базового языка за основу был взят не какой-либо существующий язык, например, Pascal, а фундаментальные механизмы ЯВУ, обобщенные и изложенные в виде теоретической модели языков программирования высокого уровня FALGOL. В FALGOL'c формализованы такие механизмы ЯВУ как подстановка, присваивание и рекурсия. Это обеспечивает возможность трансляции в БМЯ конструкций ЯВУ любого типа: императивного или функционального. Поддержка языков обработки списков, таких как Lisp, может осуществляться посредствам использования структурных значений.

Базовый машинный язык, реализуемый в виде системы команд БВМ, также как и Эль-76 проектируется совместно со структурой разрабатываемой вычислительной машины - БВМ, на основе принципов, изложенных в третьей главе (см. ниже). Теоретический язык FALGOL выступает в роли "языка с ортогональными средствами". Создание БМЯ (см. рис. 1) на его основе заключается в формировании множества базисных команд исходя из множества элементов и символов FALGOL'а и включении в БМЯ команд, необходимых для поддержки операций и шпов данных, общих для большинства ЯВУ. Основными типами данных, поддерживаемыми БМЯ, являются: целый тип, бинаргый, вещественный, логический, структура и подпрограмма. Помимо типизации, БМЯ реал ■>.-зует понятие распределенного контекста и имеет средства сгрукурирования объекгов, таким образом, БМЯ - это язык высокого уровня.

В отличие от Эль-76 базовый машинный язык представляет собой мнемоническое

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

БМЯ-программа представляет собой последовательность команд БМЯ. Наличие трансформационной семантики у языка FALGOL предоставляет возможность преобразования БМЯ-программы в процессе выполнения, что позволяет повысить эффективность выполнения программ, посредствам осуществления константных вычисление на стадии просмотра подпрограмм. В БМЯ отсутствует деление программы на команды и данные. Данные входят в состав программы в виде объектных команд. Ранее выполненные команды могут являться операндами для последующих команд и, таким образом, рассматриваться как данные в обычном смысле. По сути, программа также как и её дглные является предметом преобразования для алгоритма функционирования БВМ.

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

Требование независимости БМЯ от аппаратуры интерпретатора удовлетворяется посредством встраивания механизмов распределения памяти в аппаратуру БВМ. Выделение памяти и освобождение, как и в большинстве других машин языков высокого урозня, осуществляется исходя из потребностей исполняемой программы, соответственно, при создании программных объектов или при отсутствии возможности доступа к какому-либо ранее выделенному блоку памяти. БМЯ не предоставляет программисту средств прямого доступа к конкретным адресам какого-либо компонента памяти БВМ. Контекстная защита в БМЯ поддерживается аппарате.

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

В качестве аналогов БМЯ и БВМ для сравнения можно взять язык Java и его интерпретатор - Java Virtual Machine (JVM), разрабатываемые фирмой Sun Microsystems.

FALCOL

Синтаксис

символы РЛШ01.'а

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

Семантика

AM

Операционная семантика: Ет1

Трансформационная семантика

базисные команды

БМЯо

БВМ0

Макроопределения

Производные команды поддержки новых:

• типов данных

• операций

Эффективные алгоритмы выполнения базисных команд

Структура и алгоритмы функционирования БВМ0.

Возможности существующей элементной базы

Оценка эффективности БВМ на программах

Falgol Virtual Machine

Средства отображения состояния программной модели БВМ, среда отладки и прогона

Среда ассемблера БВМ

Программная модель БВМо

•Ч.Г

Язык ассемблера БВМ

Компилятор с

ассемблера БВМ

Виртуальная

машина

компилятора

Оптимизатор

машинного

кода

ХЛ.

БВМ,

ИГ

Программная модель БВМ«,

Аппаратно реализованная ЭВМ с внутренним языком высокого уровня

Рис. 1. Процесс разработки ЭВМ с внутренним языком высокого уровня

Приведем существенные отличия виртуальной Java-машины от БВМ:

1) Язык Java, как и Эль-76 МВК Эльбрус, не является мнемоническим представлением системы команд виртуальной Java-машины.

2) Каждая операция над числовыми данными предназначена для работы с даннь -ми определенных типов, т.е. нет полиморфности команд, что резко уве/.ичквает число команд в системе команд Jova-машины.

Предлагаемая БВМ является лишь первым необходимым шагом на пути к реализации ЭВМ с внутренним ЯВУ (см. рис. 1). В ней детально проработана только общеалгоритмическая часть БМЯ, а множество других вопросов, таких как организация ввода-вывода, многопроцессность и т.д. требуют дополнительных исследований. Для решения этих задач может потребоваться расширение или изменение БМЯ, разработка еще некоторого числа абстрактных базовых машин БВМ,, i~\..N, и только затем, после создания поянофункциональной БВМ/у, оценки её эффективности и конкурентоспособности, при условии соответствия этой машины внешним требованиям, станет возможен переход к её

I

воплощению в виде аппаратно реализованной ЭВМ с внутренним ЯВУ. В основном, поэтому БВМ и БМЯ названы базовыми.

На1 рис,' 1 БВМ0 - это разрабатываемая БВМ, а Falgol Virtual Machine - разрабатываемый программный комплекс. Поскольку в БВМ], i~\..N не предполагается расширение множества базисных команд, соответствующие части процесса в блоке БВМо отделены-пунктирной линией. В то же время, не исключено, что в ходе дальнейших исследований возникнет необходимость изменения теоретической модели, что может привести к пересмотру множества базисных команд.

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

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

ной машины.

Разработка БВМ - еще один шаг модификации структуры АМ и алгоритмов её функционирования в направлении реальной машины с системой команд высокого уровья (см. рис. 1).

Очевидно, что развитие и модификация АМ возможны в определенных теоретически обусловленных пределах, и не могут осуществляться бессистемно. Ниже приведены принципы, в соответствии с которыми проводилась разработка БВМ. Следование этим принципам позволяет рассматривать программы на базовом машинном языке как РА1-(30/,-программы, допускающие применение к ним семантических правил языка РАЮ01.

Алгоритм А' эквивалентен алгоритму А на заданном множестве данных И при выбранном способе представления исходных данных F и способе представлен.« данкых-результатов Н, если выполняется условие

(V£>)&((Л'№)) = ЩАШ

Программа на языке РАЮОЬ рассматривается как элемент данных с1 е О при сравнении алгоритмов интерпретации применяемых в АМ (А) и БВМ (А').

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

Функции ^ и Я должны быть выбраны максимально простыми и легко реализуемыми человеком. Другими словами, программист, знакомый с языком РАШОЬ и принципами функционирования АМ должен иметь возможность относительно легко перевести программу, состоящую из символов языка в программу, использующую систему команд БВМ, а также интерпретировать результат работы БВМ. В сочетании с высокоуровневым синтаксисом и семантикой РАЮОПа это делает программирование на машинном языке БВМ не менее простым, чем программирование на существующих языках высокого уровня (правда пока это утверждение справедливо только для общеалгэ-ритмических частей применяемых на практике ЯВУ).

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

2) Макрорасширение БМЯ. Для любой схемы Л41СО/,-программы. равно как и для последовательности команд БВМ, может быть введена реализующая её команда. При этом алгоритм обработки новой команды должен быть эквивалентен алгоритму обработки исходной схемы или последовательности команд, но, по-возможностя, белее эффективно реализован. Вводимые в машинный язык команды должны, как правиле, обеспечивать более высокий уровень программирования. Этот принцип ведет к тому, что для задания новой команды достаточно написать её макроопределение и ввести в структуру БВМ средства, поддерживающие эффективное выполнение данной команды. Семантика команды определяется её макроопределением. Полная реализация свойств макроопределения в алгоритме обработки новой команды, позволяет впоследствии применять к программам, использующим эти команды семантические правила языка FALGOL.

3) Настраиваемость. Структура БВМ может быть изменена, с целью достижения более высокой эффективности вычислений, при условии обеспечения эквивалентности любой выполняемой на ней программы, написанной на базовом языке и являющейся образом для FyiLGOL-программы р, программе р выполняемой на AM. Эквиьалентность программ определяется как эквивалентность алгоритмов их обработки.

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

Доказательство эквивалентности алгоритмов функционирования БВМ и AM задача нетривиальная. Косвенным доказательством правильности выбора решений, применяемых в БВМ, может служить факт выполнения на БВМ любого множестве, программ, являющихся образами FALGOL-прогршм и полученных с помощью функции F, с результатом, соответствующим с точностью до функции Н результату, получаемому при интерпретации соответствующих исходных F/HGOL-npoграмм на AM. Функции F и Н определяются по тексту диссертации в виде:

1) таблицы соответствия символов языка FALGOL базисным командам БВМ;

2) макроопределений для вновь вводимых команд БВМ, выражающих смысл этих команд через последовательность символов языка FALGOL и, возможно, макроопределения уже введенных команд;

3) описания новых значений и типов данных, через макроопределения.

Проверить эквивалентность алгоритмов обработки программ на всем множестве

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

Также в третьей главе сформулированы принципы реализации компонентов про-1раммного комплекса FVM. Использование средств объектно-ориентированного про-

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

В четвертой главе предложена и обоснована структура БВМ (рис. 2).

Компоненты памяти БВМ, имеют простую организацию и могут быть реализованы на существующей элементной базе с использованием типовых элементов ЗУ. Размещение всех компонентов БВМ на одном кристалле, позволит использовать её в контроллерах, мобильных системах и других областях, предъявляющих повышенные требования по компактности.

¿5

Левый стек

га

нм

С5

Стек характеристик --

Ргос

Стек переменных

Память переменных

С

Процессор

-А.

-V

Бинарный йайл БМЯ-програм«. ы (*/Ь)

/

Л5

Правый стек

5ЬгМ

Память подпрограмм

Память структур

Рис. 2. Обобщенная структура БВМ

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

Пятая глава посвящена системе команд БВМ. Приводятся спецификации и рассматриваются алгоритмы выполнения каждой из команд БВМ.

Команды БВМ являются подмножеством множества Р-элементов, обрабатываемых БВМ, в которое, помимо команд, входят префиксы и служебные слова. В отличие от других /"-элементов, команды попадают в регистр команд (Ш) БВМ. /'-элементы 4, в частно-

ста, команды представляются в БВМ в виде двоичных термов, имеющих фориат: [<tag>][<code>\ где <tag> - двоичный код, соответствующий Teiy .'-элемента, <code>- двоичный код кодовой части Р-элемента.

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

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

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

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

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

В седьмой главе рассматривается синтаксис и семантика разработанного языка ассемблера для БВМ. Синтаксис языка ассемблера описан в расширенной форме Бэкуса-Наура. Текстуально программы на ассемблере БВМ схожи с программами на языке FALGOL. Семантика любой программы на ассемблере совпадает с семантикой FALGOL-программы, получаемой подстановкой макроопределений команд БВМ в программу на БМЯ. Поэтому для программирования на БМЯ программисту достаточно знания семантики FALGOL'a и макроопределений команд БВМ и нет необходимости в детальном изучении особенностей структуры БВМ и реализации алгоритмов выполнения каждой из её команд.

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

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

Восьмая глава посвящена исследованию возможности представления Pascal-программ средствами БМЯ. Для основных конструкций PascaP», таких как операторы if. while, for, определение и вызов функции или процедуры, приведены БМЯ-макроопределения. Рассмотрено представление строк символов, структур и массивов. Проведено сравнение характеристик Pascal- и БМЯ- программ. В результате выявлены следующие положения:

• Основные конструкции ЯВУ блочно-процедурного типа таких, как Pascal, С или Java могут быть эффективно реализованы в виде макросов БМЯ. Это обеспечизагт быстрый переход к программированию на БМЯ, программистов знакомых с ЯВУ указанного типа.

• БМЯ-программы по объему исходного текста сравнимы с аналогичными по смыслу />да,са/-программачи, а по объему машинного кода значительно более компактны и сравнимы с программами на ассемблере для процессоров семейства х86.

• Недостатком БМЯ, не ус граненным на данном этапе исследований, является генерация мусора в памяти БВМ при выполнении ей циклических конструкций программ. Этот недостаток, возможно, будет устранен за счет разработки более совершенных макроопределений для циклов, а также за счет создания эффективных алгоритмов сборки мусора. Однако, для полного устранения эффекта "замусоривания" памяти, скорее всего, необходимы: дополнительное исследование и разработка нового механизма распределения памяти под переменные блока.

В приложениях приведены следующие материалы:

• приложение 1 ~ таблица термов БВМ;

• приложение 2 - краткое описание системы команд БВМ;

• приложение 3 - сигналы ошибок БВМ;

• приложение 4 - описание сишаксиса ассемблера БВМ;

• приложение 5 - исходные данные и результаты имитационного моделирования БВМ на потоке команд с заданными характеристиками;

• приложение 6 - исходный текст программы имитационной модели БВМ;

• приложение 7 - акты о внедрении.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

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

1) Сформулированы принципы создания БВМ, обеспечивающие ее непротиворечивое и обоснованное расширение. Разработаны БМЯ, структура БВМ, и алгоритмы функционирования БВМ, т.е. разработана архитектура БВМ с внутренним ЯВУ.

2) Разработан язык ассемблера БВМ, архитектура ВМК, ОМК. В основе функционирования ВМК лежат принципы и средства, используемые в БВМ: представление команд в виде тегированных двоичных термов, обработка команд с использованием мага-зина^ полиморфность команд, принцип ситуационной дешифрации команд, машинный цикл аналогичный используемому в БВМ. Таким образом, решения найденные при разработке БВМ применимы при реализации вычислительных машин различного назначения.

3) Созданы программные модели БВМ, ВМК, ОМК. Выявлено, что ВМК и СМК могут быть эффективно реализованы аппаратно в интегральном виде. Это открывает возможность создания интерактивной вычислительной системы, интерпретирующей исходные тексты программ на ассемблере БВМ. Разработана среда программирования на ассемблере БВМ и отладки БМЯ-программ. Все эти средства интегрированы в программный комплекс РУМ, используемый в учебном процессе кафедры ВМСиС МЭИ (ТУ).

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

числителей трансформационного типа (разработана функциональная схема блока аппаратной дешифрации ситуации).

5) Предложен и опробован новый принцип формирования системы команд ЭВМ с внутренним ЯВУ, обеспечивающий её непротиворечивое расширение (создание новых команд на основе их макроопределений). Этот принцип позволяет точно, в виде К4ЮО/,-программы, определить семантику каждой команды БВМ, что необходимо как разработчику аппаратуры, так и программисту.

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

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

Основные работы, опубликованные по теме диссертации

1) Чернов С.А. Принципы построения средств визуального отображения состояния модели вычислительной машины с внутренним языком высокого уровня // Международный форум информатизации - 2000: Доклады международной конференции "Информационные средства и технологии". 17-19 октября 2000 г. В 3-х т. - М.: Изд-во "Станкин", 2000. - Т. 1. - С. 102 - 105.

2) Чернов С.А. Организация вычислений в базовом процессоре с внутренним языком высокого уровня // "Радиоэлектроника, электротехника и энергетика": Тез. докл. Седьмой Междунар. науч.-техн. конф. студентов и аспирантов. В 3-х т. - М.: Изд-во МЭИ, 2001-Т. 1.-С. 319.

3) Чернов С.А. Представление и обработка структурных значений в вычислительной машине с внутренним языком высокого уровня // Международный форум информатизации - 2001: Доклады международной конференции "Информационные средства и технологии". 16-18 октября 2001 г. В 3-х т. - М.: Изд-во "Станкин", 2001. - Т. 2. -С. 74 - 77.

4) Чернов С.А. Представление и обработка рекурсивных конструкций в процессоре с внутренним языком высокого уровня // "Радиоэлектроника, электротехника и энергетика": Тез. докл. Восьмой Междунар. науч.-техн. конф. студентов и аспирантов. В 3-х т. -М.: Изд-во МЭИ, 2002. - Т. 1. - С. 338.

5) Мороховец Ю.Е., Чернов С.А. Дешифрация ситуаций в вычислительной машине с внутренним языком высокого уровня // Международный форум информатизации -

2002: Доклады международной конференции "Информационные средстве. /. технологии". 15-18 октября 2002 г. В 3-х т. - М.: Янус-К, 2002. - Т. 1. - С. 22 - 25.

6) Чернов С.А. Ассемблер виртуальной FALGOL-машины // "Радиоэлектроника, электротехника и энергетика": Тез. докл. Девятой Междунар. науч.-техн. конф. студенте?, и аспирантов. В 3-х т. - М.: Изд-во МЭИ, 2003. - Т. 1. - С. 351 - 352.

Подписано в печать

Zc.^-Ci

заказ № rv

fe rv J-T тираж

№

печатных листов

ш

Типография МЭИ; Красноказарменная, 13

ИСПОЛЬЗУЕМЫЕ СОКРАЩЕНИЯ.

ВВЕДЕНИЕ.

1. ПРЕДПОСЫЛКИ К СОЗДАНИЮ ЭВМ С ВНУТРЕННИМ ЯЗЫКОМ ВЫСОКОГО УРОВНЯ.

1.1 Преимущества и недостатки ЯВУ в сравнении с языком Ассемблера.

1.2 Традиционные ЭВМ с оптимизирующими компиляторами ЯВУ.

1.3 Машины языков высокого уровня.

1.4 МВК Эльбрус и язык Эль-76.

1.5 Базовая вычислительная машина с внутренним языком высокого уровня.

1.6 Выводы.

2. ТЕОРЕТИЧЕСКАЯ МОДЕЛЬ МАШИННОГО ЯЗЫКА ВЫСОКОГО

УРОВНЯ.

2.1 Синтаксис.

2.2 Абстрактная FALGOL-машина. Операционная семантика языка.

2.3 Трансформационная семантика.

2.4 Выводы.!.

3. ПРИНЦИПЫ РЕАЛИЗАЦИИ ЭВМ С ВНУТРЕННИМ ЯЗЫКОМ ВЫСОКОГО УРОВНЯ.

3.1 Основные положения.

3.2 Базовая вычислительная машина.

3.3 Язык ассемблера и система программирования.

3.4 Выводы.

4. СТРУКТУРА БАЗОВОЙ ВЫЧИСЛИТЕЛЬНОЙ МАШИНЫ.

4.1 Стеки.

4.2 Память переменных.

4.3 Память подпрограмм и память структур.

4.4 Процессор.

4.5 Выводы.

5. СИСТЕМА КОМАНД.

5.1 Представление команд в БВМ и их мнемоническое обозначение.

5.2 Схемы выполнения команд.

5.3 Базисные команды.

5.4 Команда сохранения.

5.5 Ссылки.

5.6 Элементарные объектные константы.

5.7 Индексы вхождения переменных.

5.8 Комбинаторы.

5.9 Указатели переменных.

5.10 Адреса.

5.11 Логические константы.

5.12 Команды условного выполнения.

5.13 Объектные команды и объектные термы.

5.14 Элементарные функциональные константы.

5.15 Пустая команда и команда останова.

5.16 Команды индексного доступа к элементам структур.

5.17 Структуризация.

5.18 Упаковка термов и их последовательностей.

5.19 Выводы.

6. ФУНКЦИОНИРОВАНИЕ БВМ.

6.1 Ситуационный принцип дешифрации команд.

6.2 Машинный цикл.

6.3 Представление константных процедур.

6.4 Выполнение подпрограмм с использованием регистров IP, РР.

6.5 Определение характеристик процедур.

6.6 Динамическое связывание переменных. Обработка подстановки.

6.7 Обработка рекурсивных процедур.

6.8 Сборка мусора.

6.9 Исследование влияния структурных параметров БВМ на производительность.

6.9.1 Постановка задачи.

6.9.2 Описание стратегий управления активными регистрами.

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

6.9.4 Исходные данные и анализ результатов моделирования.

6.10 Выводы.

7. АССЕМБЛЕР.

7.1 Синтаксис.

7.2 Семантика.

7.3 Виртуальная машина компилятора.

7.4 Выводы.

8. ПРЕДСТАВЛЕНИЕ Л4£С4£-ПРОГРАММ СРЕДСТВАМИ БАЗОВОГО МАШИННОГО ЯЗЫКА.

8.1 Организация выбора по условию.

8.2 Циклическое выполнение.

8.3 Определение и использование структур и массивов.

8.4 Строки символов.

8.5 Процедуры и функции.

8.6 Сравнение характеристик P^sc^l-программ и программ на базовом машинном языке.

8.7 Выводы.

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

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

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

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

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

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

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

Возможно первым проектом ЭВМ, базирующимся на новых архитектурных принципах, был проект ЭВМ "Украина" [2], разработанный в СССР в конце 60-х годов прошлого века. В основу этого проекта положена идея структурной интерпретации языка высокого уровня. Впоследствии, эта идея нашла практическое воплощение в ЭВМ серии МИР [3]. Позднее были созданы МВК семейства Эльбрус и язык Эль-76 [1] (см. разд. 1.4).

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

В основе предложенной модели лежит язык FALGOL {Formal ALGOrithmic Language). Отличительными особенностями этого языка являются простота синтаксиса, наличие описания операционной семантики как алгоритма работы абстрактной FALGOL-uamimbi и описания трансформационной семантики как конечного набора схем преобразования FALGOL-программ специального вида. Впервые в языке FALGOL были одновременно формализованы подстановка, присваивание и рекурсия, причем эта формализация, в отличие, например, от \i-Lisp' а, носила естественный, органичный характер.

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

В результате исследований вариантов реализации программного интерпретатора FALGOL'а [5-7], сформировались основные принципы его структурной организации, принципы представления символов теоретического языка, а также фрагменты алгоритма функционирования интерпретатора FALGOL-щотфамм, например, алгоритмы подсчета дефицита и объектности, необходимые для выявления константных процедур (см. основную часть работы).

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

В ходе работы над диссертацией удалось на основе усовершенствованной теоретической модели разработать базовый машинный язык (БМЯ), структуру и алгоритм функционирования базовой вычислительной машины, сделав тем самым ещё один шаг на пути создания ЭВМ с внутренним ЯВУ (см. рис.1.2).

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

1) Модифицирована и расширена элементарными константами теоретическая модель языков высокого уровня FALGOL. На основе этой модели разработан базовый машинный язык высокого уровня и программно, на платформе Intel х86, MS Windows 98, реализован его интерпретатор - базовая вычислительная машина, являющаяся прототипом ЭВМ с внутренним ЯВУ. Создание такой ЭВМ, предполагается, позволит:

• решить проблему семантического разрыва, препятствующую полному переводу программирования на ЯВУ (см. разд.1.1);

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

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

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

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

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

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

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

Практическая ценность. БВМ реализована в виде программной модели и интегрирована в программный комплекс Falgol Virtual Machine (FVM), обладающий полным набором средств, необходимых для дальнейшего развития БВМ в направлении реальной ЭВМ с внутренним ЯВУ. FVM может также использоваться в качестве программного средства учебного назначения (ПСУН) в учебном процессе, поскольку предоставляет возможность изучения БМЯ и принципов работы БВМ.

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

Кроме БВМ, в состав указанного выше программного комплекса включены виртуальная машина компилятора (ВМК), оптимизатор машинного кода (ОМК), средства отображения состояния БВМ и среда ассемблера БВМ. ОМК обеспечивает высокую степень компактности машинного кода программ на БМЯ и может осуществлять упаковку программ в любой системе команд, к которой применимы средства упаковки термов, используемые в БВМ.

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

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

Цель и задачи диссертации. Диссертация преследовала две главные цели:

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

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

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

Цель I:

• сформулированы принципы создания базовой вычислительной машины с внутренним языком высокого уровня;

• разработана структура БВМ, структуры ситуационного дешифратора команд, процессора и компонентов памяти;

• разработана система команд БВМ и алгоритмы выполнения каждой из команд БВМ;

• определен алгоритм машинного цикла БВМ;

• разработан алгоритм функционирования БВМ в целом;

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

• разработаны и исследованы эффективные методы обработки рекурсивных процедур, удаления неконстантных процедур и команд вызовов переменных.

Цель II:

• разработана программная модель БВМ;

• разработан язык ассемблера БВМ;

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

В основе решения перечисленных выше задач лежит теоретическая модель языков высокого уровня, основанная на применении нового фундаментального языка FALGOL [8], и изложенные в [9] основные принципы машинного представления FALGOL-щютфамм.

Основной материал диссертации сгруппирован в восемь глав.

8.7 Выводы

1) Основные конструкции ЯВУ блочно-процедурного типа таких, как Pascal, С или Java могут быть эффективно реализованы в виде макросов базового машинного языка. Это обеспечивает быстрый переход к программированию на БМЯ, программистов знакомых с ЯВУ указанного типа. Освоение базового машинного языка может происходить поэтапно, за счет постепенного вытеснения из программ макросов, приведенных в данной главе, и замены их более эффективными последовательностями команд БМЯ.

2) Программы на базовом языке по объему исходного текста сравнимы с аналогичными по смыслу программами языка Pascal, а по объему машинного кода значительно более компактны и сравнимы с программами на ассемблере для процессоров семейства х86.

3) Недостатком БМЯ, не устраненным на данном этапе исследований, является генерация мусора в памяти БВМ при выполнении ей циклических конструкций программ. Этот недостаток, возможно, будет устранен за счет разработки более совершенных макроопределений для циклов, а также за счет создания эффективных алгоритмов сборки мусора. Однако, для полного устранения эффекта "замусоривания" памяти, скорее всего, необходимы: дополнительное исследование и разработка нового механизма распределения памяти под переменные блока.

ЗАКЛЮЧЕНИЕ

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

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

2) Разработан базовый машинный язык высокого уровня, реализованный в виде системы команд БВМ.

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

4) Разработаны алгоритмы функционирования БВМ - алгоритм выполнения машинного цикла и алгоритмы выполнения каждой из команд внутреннего языка. Алгоритмы выполнения команд формализованы в программной форме в виде обработчиков ситуаций, что, при аппаратной реализации БВМ, позволяет выделить логику обработки каждой команды и реализовать её на микропрограммном уровне.

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

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

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

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

9) Разработан язык ассемблера БВМ, обеспечивающий быстрое создание программ на БМЯ, за счет использования мнемонического представления команд, расширенных средств описания переменных и операций над ними и средств описания данных с минимальным указанием на их типы. Синтаксис языка ассемблера описан в расширенной форме Бэкуса-Наура. Текстуально программы на ассемблере БВМ схожи с программами на языке FALGOL. Семантика любой программы на ассемблере совпадает с семантикой /vlLGOL-программы, получаемой подстановкой макроопределений команд БВМ в программу на БМЯ. Поэтому для программирования на БМЯ программисту достаточно знания семантики FALGOL"а и макроопределений команд БВМ, и нет необходимости в детальном изучении особенностей структуры БВМ и реализации алгоритмов выполнения каждой из её команд.

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

11) Выявлено, что программы на БМЯ по уровню абстракции и объему исходного текста сравнимы с аналогичными в семантическом отношении Pascal-программами, а по объему машинного кода - с ассемблерными программами микропроцессоров семейства х86. Малый объем семантически нагруженного кода открывает перспективы использования БМЯ в качестве языка межмашинного взаимодействия.

12) Обнаружено, что недостатком БМЯ, не устраненным на данном этапе исследований, является генерация значительного объема мусора в памяти БВМ при выполнении ей циклических конструкций программ. Этот недостаток, возможно, будет устранен за счет разработки более совершенных макроопределений для циклов, а также за счет создания эффективных алгоритмов сборки мусора. Однако, для полного устранения эффекта "замусоривания" памяти, скорее всего, необходимы дополнительное исследование и разработка нового механизма распределения памяти под переменные блока.

13) Разработан программный комплекс под рабочим названием Falgol Virtual Machine, включающий программную модель БВМ, ВМК, ОМК, средства отображения и изменения состояния БВМ, среду программирования на ассемблере БВМ. Программный комплекс может использоваться для исследования и изучения БМЯ, создания и отладки программ на БМЯ в отсутствии аппаратно реализованной БВМ, а также в качестве основы для дальнейшего совершенствования БМЯ и БВМ.

14) Основным и наиболее значимым практическим результатом диссертации можно считать создание FVM, поскольку он явился первой отчуждаемой реализацией БВМ, основанной на теоретической модели языка FALGOL. Ожидается, что программный комплекс позволит существенно расширить круг лиц занимающихся разработкой или, по крайней мере, изучением БМЯ.

15) Комплекс программ Falgol Virtual Machine доведен до уровня программного средства учебного назначения и может быть применен в учебном процессе кафедр МЭИ (ТУ) для углубленного изучения принципов работы вычислительных машин с внутренними ЯВУ.

1. Пентковский В.М. Язык программирования Эль-76. Принципы построения языка и руководство к пользованию. 2-е изд. испр. и доп. - М.: Наука. Гл. ред. физ.-мат. лит., 1989 (Б-чка программиста).

2. Глушков В.М., Михновский С.Д., Рабинович 3.JI. ЭВМ со структурной интерпретацией языков высокого уровня // Кибернетика.-1981№4. С. 73-81.

3. Глушков В.М., Стогний А.А., Молчанов И.Н. Алгоритмический язык малой электронной цифровой вычислительной машины МИР, Т.2, кн. 1, изд-во "Нау-кова думка", Киев, 1971.

4. Криницкий Н.А., Мороховец Ю.Е., Мусина М.Д., Фальк В.Н. Разработка принципов построения бортовой ЭВМ с языком высокого уровня. Отчет о НИР № 02860000485, М., МИРЭА, 1985 92с.

5. Мороховец Ю.Е., Мусина М.Д., Фальк В.Н. "Принципы построения и возможности реализации базового машинного языка высокого уровня", Труды МЭИ №86, 1986 г.

6. Мороховец Ю.Е., Фальк В.Н. "Принципы построения аппаратно-программного обеспечения ВС с внутренним языком высокого уровня", Отчет о НИР №02890006301, МИРЭА, 1989 г.

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

8. Мороховец Ю.Е., Фальк В.Н. Разработка архитектуры вычислительной машины с внутренним языком высокого уровня. Отчет о НИР № 01980005592. Инв. № 02.99.00 04466. М.: МЭИ, 1999. 34 с.

9. Майерс Г. Аритектура современных ЭВМ. М.: Мир, 1985.

10. Computer architecture: some old ideas that have not quite made in yet / Dening P.-CACM, 24, 1981.

11. Ананьев JI.И. Перемещение задач в МВК Эльбрус. Препринт / ИТМ и ВТ

12. АН СССР. М., 1985. - №5. - 37 с.

13. Валиев К.А. и др. Развитие элементной базы высокопроизводительных ЭВМ // Информационные технологии и вычислительные системы. 1996. - №1.

14. Ж.К. Голенкова, А.В. Заблоцкий, M.JI. Мархасин, С.С. Порошин,

15. Б.В. Цесин, A.M. Шугаев. Руководство по архитектуре IBM PC AT. М.: ООО "Консул", 1992.-950 с.

16. Искусственный интеллект: В 3-х кн. Кн. 3. Программные и аппаратные средства: Справочник/ Под ред. В.Н. Захарова, В.Ф. Хорошевского. М.: Радио и связь, 1990. - 368 с.

17. Андреев В.М., Голосов И.С., Самойленко С.М. Особенности проведения оптимизирующих преобразований // Методы трансляции и конструирования программ. Новосибирск: ВЦ СО АН СССР, 1986. - С.55-59.

18. Дж. Айлиф. Принципы построения базовой машины. М.: Издательство "Мир", 1973.- 120 с.

19. Задыхайло И.Б., Камынин С.С., Любимский Э.З., Вопросы конструирования вычислительных машин из блоков повышенной квалификации, изд-во ИПМ АН СССР, М., 1971, препринт №68.

20. J. Backus. Can Programming be Liberated from the Von Neumann Style? A Functional Style and its Algebra of Programs. Communications of ACM, 21 (8), 613-641 (Aug., 1978).

21. Department of Defense. Reference manual for the Ada Programming Language. Superintendent of Documents, US Government Printing Office, Wahington, D.C. 20402, 1980.

22. Вегнер П. Программирование на языке АДА / Пер.с англ. ред. В.Ш.Кауфмана. М.: Мир, 1983. - 240 с.

23. Allen J. Anatomy of LISP. New-York: McGraw-Hill, 1978. - 273 p.

24. Турчин В.Ф- Метаязык для формального описания алгоритмических языков // Цифровая вычислительная техника и программирование. М.: Сов. радио,1966.-С. 116-124.

25. Турчин В.Ф. Метаалгоритмический язык // Кибернетика. 1968. - №4 -С. 45-54.

26. Базисный Рефал и его реализация на вычислительных машинах / ЦНИИПИАСС. М„ 1977. - 238 с.

27. R.W. Doran High-Level Language Computer Architecture. Academic Press, New York, 1975, pages 63-108. Chapter: Architecture of Stack Machines.

28. Пентковский B.M. Языковые основы проектирования системы Эльбрус // Системное и теоретическое программирование: Тез. докл. 4 Всесоюзн. симпоз. -Кишинев.: Кишиневский государственный университет, 1983. С. 294—296.

29. Java Virtual Machine Specification // Sun Microsystems, Inc http://java.sun.com/docs/books/

30. Чернов C.A. "Разработка и исследование механизмов выполнения программ процессором с внутренним языком высокого уровня". Дис. на соискание степени магистра, М.: МЭИ, 2000 457 с.

31. Чернов С.А. Ассемблер виртуальной FALGOL-uam\mb\ // "Радиоэлектроника, электротехника и энергетика": Тез. докл. Девятой Междунар. науч.-техн. конф. студентов и аспирантов. В 3-х т. М.: Изд-во МЭИ, 2003. - Т. 1. С. 351 -352.

32. Б. Страуструп. Язык программирования С++. Пер. с англ. Киев: "ДиаСофт", 1993.

33. Собоцинский В.В. Практический курс Turbo С++. Основы объектно-ориентированного программирования. М.: Изд-во "Свет", 1992. - 236 с.

34. К. Рейсдорф. Borland С++ Builder 3. Освой самостоятельно: Пер. с англ. -М.: ЗАО "Издательство БИНОМ", 1999. 736 с.

35. Гладков С.А. Фролов Г.В. Программирование в Microsoft Windows: В 2-х ч.-М.: "ДИАЛОГ-МИФИ", 1992. ч.1 - 320 е., ч.2.-288 с.

36. Э. Органик. Организация системы Интел 432: Пер. с англ. М.: Мир, 1987. i • - 446 с.

37. Е. W. Dijkstra, L. Lamport, A. J. Martin, С. S. Scholten, E. M. F. Steffens. On-the-Fly Garbage Collection: An Exercise in Cooperation. Communications of the ACM 20, 966-975 (November, 1978).

38. Burroughs Corporation. The Descriptor A definition of the В 5000 Information Processing System. Burroughs Corp. Detroit, Michigan, 1961.1 45) http://www.citforum.ru/hardware/svk/glava3.shtml Оценка производительности вычислительных систем.

39. Шеннон Р. Иммитационное моделирование систем: искусство и наука . -М.: Мир, 1978,-424 с.

40. Армстронг Дж. Р. Моделирование цифровых систем на языке VHDL. М.:1. Мир, 1992.

41. Поляков А.К. Моделирование ЭВМ на языке VHDL. М.: Изд-во МЭИ,1994.

42. Р. Хантер. Проектирование и конструирование компиляторов / Пер. с англ. М.: Финансы и статистика, 1984. - 232 с.

43. Ф. Вайнгартен. Трансляция языков программирования. М.: Мир, 1977.190 с.

44. Фельдман Дж., Грайс Д., Системы построения трансляторов, пер. с англ., "Алгоритмы и алгоритмические языки", вып. 5, 1971.

45. Рейуорд-Смит В.Дж. Теория формальных языков. Вводный курс / Пер. с англ. М.: Радио и связь, 1988. - 128 с.

46. Фаронов В.В. Программировнаие на персональных ЭВМ в среде Турбо-Паскаль. М.: Изд-во МГТУ, 1991. - 580 с.

47. Пильщиков В.Н. Программирование на языке ассемблера IBM PC. М.: "ДИАЛОГ-МИФИ", 1994.-288 с.

48. The Unicode Standard: Worldwide Character Encoding, Version 1.0, Volume 1, ISBN 0-201-56788-1, and Volume 2, ISBN 0-201-60845-6. Доп. информация no Unicode 1.1 есть на ftp://unicode.org