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

Вид материала

Содержание

Разработка виртуальных машин
Абстрактная машина AMF
Код операции (КОП)
Абстрактная машина AMS
Код операции (КОП)
Примеры программ

Подобный материал:

1 2 3 4 5

Разработка виртуальных машин

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

Абстрактная машина AMF

В качестве первого примера определим простую абстрактную машину AMF (Abstract Machine First).

Память AMF состоит из 512 ячеек-слов с адресами от 0 до 511. Одно слово памяти содержит 32 бита. В каждом слове, кроме нулевого, может быть записано целое число, вещественное число или команда. В нулевой ячейке всегда записан ноль: все биты равны 0.

Целые числа являются знаковыми, отрицательные числа представляются в дополнительном коде. Вещественные числа представляются как короткие вещественные числа по стандарту IEEE-754 [_]. В соответствии с этим стандартом вещественный ноль представляется точно так же, как целый: все биты слова равны 0.

Команды имеют следующий формат:

код операции (5 разрядов);
А1, А2, А3 – адреса операндов (каждый адрес по 9 разрядов).

Код операции представляет собой число от 0 до 31, а адресная часть составляет 27 бит. В соответствии с количеством адресов, машина AMF является 3-адресной^⁶. Состав операций представлен в табл. 1.1. В таблице определены только 21 команда из 32. Это дает нам возможность добавить при необходимости несколько новых команд. Для удобства код каждой операции обозначается мнемоническим обозначением.

Регистры процессора:

RA – регистр адреса команды, в котором процессор хранит адрес выполняемой команды; содержит 9 разрядов;
RC – регистр команды, в котором процессор хранит выбранную из памяти и выполняемую в данный момент команду;
Flag – регистр признака результата, в который процессор записывает целое число как результат некоторых операций: -1, если результат отрицательный, 0 – если результат нулевой и +1, если результат положительный;
Error – регистр ошибки: 0 – ошибки при выполнении операции отсутствуют, 1 – при выполнении операции произошла ошибка;

Таблица 1.1

Код операции (КОП)	Комментарий
00	Stop – остановка работы процессора
01	Iadd – сложение целых чисел
02	Isub – вычитание целых чисел
03	Imul – умножение целых чисел
04	Idiv – деление целых чисел
05	Imod – остаток от деления целых чисел
08	Iin – ввод целых чисел
09	Iout – вывод целых чисел
10	ItoR – перевод целого в вещественное
11	Radd – сложение вещественных чисел
12	Rsub – вычитание вещественных чисел
13	Rmul – умножение вещественных чисел
14	Rdiv – деление вещественных чисел
16	Rcmp – сравнение вещественных чисел
18	Rin – ввод вещественных чисел
19	Rout – вывод вещественных чисел
20	RtoI – перевод вещественного в целое
25	Move – пересылка (копирование)
26	Xchg – обмен содержимым двух слов
30	Go – безусловный переход
31	Jmp – условный переход

Для описания алгоритма работы процессора и алгоритмов выполнения команд введем некоторые формальные обозначения. Память представляет собой массив mem[512]. Если х — это адрес, то mem[x] представляет собой содержимое ячейки памяти с адресом x.

Процессор исполняет команды по следующему алгоритму:

RC<-mem[RA]; выборка очередной команды из памяти.
Выполнение операции, заданной в команде кодом операции; если код операции ошибочный, то Error<-1.
Если КОП=Stop или Error=1, то Конец; иначе RC<-(RC + 1).
Перейти к 1.

Процессор начинает работу при «нажатии кнопки Пуск»^⁷:

Выполняется ввод массива слов с «устройства ввода», начиная с адреса 1; этот массив слов представляет собой программу и заканчивается специальным маркером конца массива;
Error<-0; Flag<-0.
RA<-1.

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

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

R1<-mem[A1]; R2<-mem[A2]; Res<-(R1 op R2); mem[A3]<-Res.
Если при выполнении операций были ошибки, то Error<-1.
Если Error=0, то

Выбор Res: Res<0:Flag<-(-1); Res=0:Flag=0; Res>0:Flag<-(+1)

Здесь R1, R2 и Res представляю собой внутренние регистры процессора.

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

Команда пересылки копирует содержимое по адресу A3 в слово по адресу A1:

R1<-mem[A3]; mem[A1]<-R1.

Команда обмена обменивает содержимое двух слов памяти:

R1<-mem[A1]; R2<-mem[A3]; mem[A1]<-R2; mem[A3]<-R2;

Команда безусловного перехода выполняет очень простое действие: RA<-A2. Тем самым процессор выбирает следующую команду из слова с адресом A2.

Команда условного перехода изменяет адрес в регистре адреса в соответствии со значением регистра Flag:

Выбор Flag: -1:RA<-A1; 0:RA<-A2; +1:RA<-A3;

Команды преобразования чисел работают подобно команде MOVE, но в процессе пересылки выполняют преобразование числа из одного вида в другой. Команды ввода осуществляют ввод массива чисел с внешнего устройства и запись его по адресу A1; количество чисел задается непосредственно на месте A2. Команды вывода выполняют вывод массива чисел на внешнее устройство. Адрес массива задается в команде первым аргументом A1, а количество — на месте второго аргумента непосредственно в команде, аналогично тому, как это определено в командах ввода. Отметим, что в качестве массива целых чисел можно ввести массив команд.

Система команд машины AMF подобна системам команд ранних моделей реальных компьютеров, разработанных в 50-е прошлого века. В частности, команда условного перехода в точности соответствует условному оператору Фортрана в его ранних версиях. Исключение составляют команды ввода-вывода и преобразования чисел: в реальных компьютерах эти действия обычно выполнялись стандартными подпрограммами. Но как уже было сказано, мы создаем виртуальную машину такой, как нам удобно.

Абстрактная машина AMS

Для сравнения определим другую простую абстрактную машину AMS (Abstract Machine Second).

Память AMS состоит из 1024 32-разрядных слов с адресами от 0 до 1023. Нулевое слово содержит ноль. AMS обрабатывает такие же форматы данных, что и AMF. Команда AMS имеет следующий формат:

Код операции (6 разрядов);
A1 – адрес операнда (10 разрядов).

Таким образом, длина команды составляет 16 бит, и в одном слове памяти помещается две команды. AMS является одноадресным компьютером^⁸. Разрядность кода операции и позволяет определить до 64 различных операций (см. табл. 1.2). В таблице показан практически тот же набор команд с небольшими изменениями, обусловленными одноадресностью. Очевидно,

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

За один раз процессор выбирает из памяти полное слово, в котором записано две команды, поэтому состав регистров для обработки команд тоже немного отличается от состава регистров процессора AMF:

RM — регистр слова; в этот регистр процессор выбирает слово из памяти.
RC — регистр команды, в который из регистра RM по очереди помещаются первая и вторая команды.

Остальные регистры процессора — такие же, как в процессоре AMF.

Таблица 1.2

Код операции (КОП)	Комментарий
00	Stop – остановка работы процессора
01	Iadd – сложение целых чисел
02	Isub – вычитание целых чисел
03	Imul – умножение целых чисел
04	Idiv – деление целых чисел
05	Imod – остаток от деления целых чисел
06	Icmp – сравнение сумматора с целым числом
08	Iin – ввод целого числа
09	Iout – вывод целого числа
11	Radd – сложение вещественных чисел
12	Rsub – вычитание вещественных чисел
13	Rmul – умножение вещественных чисел
14	Rdiv – деление вещественных чисел
16	Rcmp – сравнение сумматора с вещественным числом
18	Rin – ввод вещественного числа
19	Rout – вывод вещественного числа
40	Load – загрузка сумматора
41	LdIR – загрузка сумматора с переводом целого в вещественное
42	LdRI – загрузка сумматора с переводом вещественного в целое
50	Store – сохранение сумматора
51	StIR – сохранение сумматора с переводом целого в вещественное
52	StRI – сохранение сумматора с переводом вещественного в целое
60	Go – безусловный переход
61	JZ – переход, если ноль
62	JG – переход, если больше
63	JL – переход, если меньше

Действия процессора AMS по «кнопке Пуск» отличаются от действий процессора AMF обнулением регистра-сумматора, и установкой адреса первого выбираемого слова в регистре RM.

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

RM<-mem[RA]; выборка очередного слова с командами из памяти.
RA<-RA + 1.
RC<-high(RM); занести команду в регистр команд из старшей половины RM.
Выполнение операции, заданной кодом операции; если КОП ошибочный, то Error<-1.
Если КОП=Stop или Error=1, то Конец;
RC<-low(RM); занести команду в регистр команд из младшей половины RM.
Выполнение операции, заданной кодом операции; если КОП ошибочный, то Error<-1.
Если КОП=Stop или Error=1, то Конец;
Перейти к 1.

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

R1<-mem[A1]; RS<-(RS op R1).
Если при выполнении операций были ошибки, то Error<-1.
Если Error=0, то

Выбор Res: Res<0:Flag<-(-1); Res=0:Flag=0; Res>0:Flag<-(+1)

Здесь R1 является внутренним регистром процессора, а RS – регистр-сумматор.

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

Команда загрузки Load копирует содержимое по адресу A1 в регистр-сумматор:

RS<-mem[A1];

Команда сохранения Store выполняет обратное действие:

mem[A1]<-RS;

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

Команда безусловного перехода практически во всех компьютерах работает одинаково: RA<-A1. Однако в машине AMS передать управление можно только на первую команду, размещенную в слове A1.

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

Команда JZ:

Если Flag=0, то RA<-A1;

Команда JG:

Если Flag=+1, то RA<-A1;

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

Команды ввода осуществляют ввод одного числа с внешнего устройства и запись его по адресу A1. Команды вывода выполняют вывод одного числа на внешнее устройство. Адрес числа задается аргументом A1.

Примеры программ

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

Сначала требуется распределить память: назначить конкретные адреса константам и переменным. Массив разместим в ячейках с начальным адресом 100, сумму поместим в ячейку с адресом 20. Обратная величина сохраняется в ячейке с адресом 21. Целую величина n = 100 (количество элементов массива) поместим после команды Stop. Нам потребуются еще вещественная константа 1.0, и целая константа 1. Разместим их тоже после команды Stop.

Для сравнения возможностей AMF и AMS напишем одну и ту же программу для обеих машин^⁹. Программа для AMF показана в табл. 1.3, а программа для AMS — в табл. 1.4. Вместо числовых кодов операций в таблицах записаны их мнемонические обозначения. По возможности в обеих программах используются ячейки с одними и теми же адресами.

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

Таблица 1.3

Адрес	Команда				Комментарий
001	Rin	100	100	000	Читать(x); массив x в ячейках 100 – 200
2	Move	020	000	000	S = 0
3	Rcmp	000	000	100	(0 - x[i]) < 0?; установка Flag
4	Jmp	005	009	009	да, нет, нет; если x[i]<=0, то на переадресацию
5	Rdiv	021	016	100	Обратная = 1.0 / x[i]; установка Flag
6	Rcmpsub	000	021	016	(Обратная – 1.0) > 0 ?; установка Flag
7	Jmp	009	009	008	нет, нет, да; Если разница < 0, то на переадресацию
8	Radd	020	020	021	S = S + Обратная; установка Flag
9	Isub	018	018	017	Переадресация-начало: n = n – 1; установка Flag
010	Jmp	014	014	011	Если n <= 0, то Вывод
1	Iadd	003	017	003	Модификация команды в слове 3
2	Iadd	005	017	005	Модификация команды в слове 5
3	Go	000	003	000	На 003 – обработка следующего x[i]
4	Rout	020	001	000	Вывод(S)
5	Stop	000	000	000	Стоп
6	1.0				Вещественная константа 1.0
7	00	000	000	001	Целая константа 1 – для переадресации х[i]
8	00	000	000	100	Переменная n с начальным значением 100

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

Таблица 1.4

Адрес	Команда		Комментарий
001	LoadMoven	0000	Сумматор = 0
	StoreMoveve	00202S3	Сумма = 0
2	Rin	0100	Читать(x[i]); установка Flag
	Rcmp	0100	Сумматор - X[i] < 0;
3	JG	0006	Нет – переход на переадресацию
	JZ	0006	Нет – переход на переадресацию
4	Load	0015	Сумматор = 1.0
	Rdiv	0100	Сумматор (Обратная) = 1.0 / x[i]; установка Flag
5	RcmpStore	001521	Сумматор (Обратная) - 1.0 > 0?; установка Flag
	JG	00120	ДА! Если Обратная > 1.0, то на суммирование
6	Load	00163	Сумматор = n
	Isub	00172	Сумматор = Сумматор – 1; установка Flag
7	Store	0016	n = Сумматор
	JZ	00142	Если n =0, то на финиш
8	Load	0002	Сумматор = Команда из слова 2
	Iadd	0018	Модификация обеих команд в слове
9	Store	0002	Запись команды в память
	Load	0004	Сумматор = Команда из слова 3
0010	Iadd	0017	Модификация только второй команды
	Store	0004	Запись команды в память
1	Load	0000	Очищаем сумматор
	Go	0002	На 0002 – обработка следующего x[i]
2	Radd	0020	Сумматор (Обратная) = Сумматор + Сумма
	Store	0020	Сумма = Сумматор
3	Load	0000	Очищаем сумматор
	Go	0002	На 0002 – обработка следующего x[i]
4	Rout	0020	Вывод(Сумма) - финиш
	Stop	0000
5	1.0		Вещественная константа 1.0 – полуслово 1
			Вещественная константа 1.0 – полуслово 2
6	00	0000	Целое n = 100 – полуслово 1
	00	0100	Целое n = 100 – полуслово 2
7	00	0000	Целая константа 1 – полуслово 1
	00	0001	Целая константа 1 – полуслово 2
8	00	0001	Константа переадресации x[i] (слово 0002)
	00	0001

Несмотря на то, что количество команд в программе для AMS значительно больше, чем в программе для AMF, программы занимают в памяти одинаковое количество слов.

А теперь разработаем более современную учебную виртуальную машину, которую и будем использовать в дальнейшем

Blog

Содержание

Разработка виртуальных машин

Абстрактная машина AMF

Абстрактная машина AMS

Примеры программ