Переменный размер команды и стек

Цель: экономия памяти

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

УМ_П: переменный размер команды

Решение: ввести переменный размер команды, зависящий от КОП

• Сокращение объёма программ
• Резкое уменьшение размера адресуемой ячейки (до размера самой короткой команды)

  • => увеличение поля адреса или сокращение объёма оперативной памяти при том же размере поля

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

  • => вопрос порядка байтов: в каком порядке байты идут в машинном слове?

• Увеличение такта работы (прочесть КОП, интерпретировать, прочесть остальную часть команды вместо просто «прочесть инструкцию в РК»)
• Учёт адресов при программировании в кодах стал намного сложнее

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

Пример: Вычисление факториала для учебной машины УМ-П. Обратите внимание на минимальный размер команды в один байт (halt), как следствие — на адресацию в байтах и на то, что целое занимает 40 битов, как в УМ-2. Кроме того, в УМ-П

.cpu mm-v

.input 0x100
.output 0x10A

.code
      00 0105 0100 ; 00; Заносим N в счётчик
      00 010A 0020 ; 05; Заносим 1 в результат
      05 0105 0020 ; 0A; Сравниваем счётчик и 1
      85 001F      ; 0F; Если ≤, цикл окончен
      03 010A 0105 ; 12; Домножаем результат на счётчик
      02 0105 0020 ; 17; Уменьшаем счётчик на 1
      80 000A      ; 1C; Переход на начало цикла
      99           ; 1F; конец
      00 0000 0001 ; 20; 1

.enter 6

Потребление памяти по сравнению с УМ-2 сократилось. Насколько возросло потребление адресов по сравнению с УМ-2 (если считать в адресуемых ячейках, а не в байтах)?

Порядок байтов

Целое число состоит из нескольких адресуемых байтов. В каком порядке эти байты располагаются в памяти?

Число: 0xA1B2C3D4

Тупоконечный порядок нагляднее, зато в нём интерпретация значения целого зависит от размера целого в битах, даже если значение этого целого мало. Допустим, первые 4 байта памяти равны 03 00 00 00. Тогда по адресу 0

• Находится байт со значением 0x03 == 3

• Находится двухбайтное целое со значение 0x0300 == 768

• Находится четырёхбайтовое целое 0x3000000 == 50331648

При остроконечном порядке все три значения равны 3.

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

В УМ-П — сорокаразрядное целое, байты располагаются в порядке адресации (big-endian)

Ошибочная интерпретация инструкций.

Допустим, в примере выше в результате ошибки безусловный переход был запрограммирован на адрес 0008 вместо 000A. (80 0008). Как бы тогда выполнялась программа?

• КОП по адресу 0008 == 00 (пересылка).
• Следовательно, это двухадресная команда, надо считать два поля операндов — 2005 и 0105
• Выполняется пересылка из 0105 в 2005
• Следующий КОП находится по адресу 0008+5 = 000D.
• Это снова 00 — пересылка с операндами 2085 и 001F
• Следующая команда (по адресу 12) неожиданно начинается в правильном месте, и вычисление продолжается как ни в чём не бывало!

Отладка таких конструкций представляет известную трудность

Стековые машины

Цель: минимизировать обмен с оперативной памятью

• Задача: архитектура, в которой только операции пересылки работают с адресуемой памятью

• решение: несколько (сколько?) регистров общего назначения, в которые загружаются данные, команды работают с регистрами

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

Аппаратный стек — это хранилище данных, в котором предусмотрены две операции

• Положить значение на вершину стека
• Снять значение с вершины стека

Таким образом стек реализует абстракцию LIFO (Last In, First Oout).

В стеке может быть предусмотрена также и адресация относительно его вершины:

• Если последовательно положить на стек значения A, B и С, то A окажется со смещением 2 ячейки относительно вершины стека. B ­— со смещением 1, а C — со смещением 0
• Если после этого положить на стек ещё два значения, соответствующие смещения станут равными 4, 3 и 2

Стековая машина УМ-С

Дополним машину УМ-1 аппаратным стеком и ограничим все операции над над данными

• Переменный размер команды, побайтовая адресация
• Трёхбайтовое целое (как в УМ-1)
• Операции над данными (включая сравнение) — безадресные: со стека снимается нужное количество операндов, производится операция, результат вычисления помещается в стек
• Операции работы со стеком
  • положить на стек 5A АДРЕС
  • снять со стека 5B АДРЕС
  • дублировать вершину стека 5C
  • обмен двух последних элементов стека 5D

Пример: вычисление b²-4*a*c

.cpu mm-s

.input  0x1006, 0x1000, 0x1009
.output 0x100c
.code
5A 1000 ; загрузить b ; b
5C      ; дублировать ; b b
03      ; умножить    ; b*b
5A 1003 ; загрузить 4 ; b*b 4
5A 1006 ; загрузить a ; b*b 4 a
5A 1009 ; загрузить c ; b*b 4 a c
03      ; умножить    ; b*b 4 a*c
03      ; умножить    ; b*b 4*a*c
02      ; вычесть     ; b*2-4*a*c
5b 100C ; выгрузить d ; b*2-4*a*c
99      ; halt

.code 0x1003
00 0004 ; 4

.enter  3 5 2

Более сложные алгоритмы требуют более сложных операций над стеком.

Пример: вычисление факториала в УМ-С: сначала стек наполняется значениями от N до 1 с шагом -1, затем все они перемножаются:

.cpu mm-s

.input 0x100
.output 0x103

.code
5A 0100 ; 00 ; Заносим N                          ; N
5C      ; 03 ; дублируем перед проверкой          ; N … K K
5A 0025 ; 04 ; Заносим 1                          ; N … K K 1
05      ; 07 ; Сравниваем                         ; N … K
85 0013 ; 08 ; Если ≤, цикл окончен → 13          ; N … K
5C      ; 0B ; Дублируем                          ; N … K K
5A 0025 ; 0C ; Заносим 1                          ; N … K K 1
02      ; 0F ; Вычитаем                           ; N … K K-1
80 0003 ; 10 ; Продолжаем набивать стек → 03      ; N … K K-1
5D      ; 13 ; Посмотрим очередной сомножитель    ; N … Res K
5C      ; 14 ; Дублируем для сравнения            ; N … Res K K
5A 0100 ; 15 ; Заносим N                          ; N … Res K K N
05      ; 18 ; Сравниваем, не конец ли            ; N … Res K
81 0020 ; 19 ; Нашли N, готово → 20               ; N … Res K
03      ; 1C ; Умножим                            ; N … Res*K
80 0013 ; 1D ; Продолжим умножение → 13           ; N … Res*K
03      ; 20 ; Умножим в последний раз            ; Res N
5B 0103 ; 21 ; Выгрузим                           ; Res
99      ; 24 ; Halt                               ; Res
00 0001 ; 25 ; 1

.enter 6

Ещё раз обратим внимание на то, что одно целое занимает три однобайтовых ячейки памяти.

Непосредственная и относительная адресация

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

Безадресная машина УМ-0*

(не поддерживается modelmachine)

TODO Роль ввода в эмуляторе может выполнять предварительное заполнение стека, а вывода — выдача стека по окончании работы.

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

• Дополнительно появляется команда 40 — заполнение вершины стека значением, непосредственно указанным в самой команде (т. к. хранить значения теперь можно только в коде программы). Она имеет формат 40 NN и занимает 2 байта.

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

• Дополнительно появляются команды удаления (50), обмена (56), циклического обмена (55) и дублирования (54) K-й ячейки стека

Фактически получается не-фоннеймановская архитектура: различие памяти для команд и для данных в стеке.

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

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

Константы, задаваемые непосредственной адресацией, могут быть отрицательными. Например, 40 FE кладёт на вершину стека число -2. Таким образом, диапазон констант, которые можно использовать в УМ-0, варьируется от -128 до 127. Чтобы задать числа вне этого диапазона (например, 0xfe = 254), пришлось бы ввести дополнительные команды типа «заполнить старший байт вершины стека», но для простоты мы этого делать не станем.

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

Договоримся, что в УМ-0 операнд команды перехода — это смещение относительно адреса текущей команды, то есть относительно содержимого регистра СК.

Что не так с программным кодом, в котором начала цикла отстоит от его конца на многие тысячи инструкций? Как программисты справляются с такими ситуациями?

Если повсеместно использовать относительную и непосредственную адресацию, код приобретает два полезных свойства:

1. Код программы получается позиционно-независимым: он может быть загружен и выполнен в произвольном месте оперативной памяти.

2. Код программы не зависит также и от представления целого числа: оно может занимать и два байта, то есть совпадать с размером команды, а может, например, и 4

Договоримся, что размер целого числа УМ-0 — два байта, хотя это и маловато. Тогда характеристики УМ-0 получаются такими:

• Размер ячейки оперативной памяти и целого числа: 2 байта
• Размер адреса: 2 байта
• Арифметические вычисления производятся с вершиной стека
• Код команды помещается в одну ячейку оперативной памяти (фиксированный размер команды в 2 байта)

Напомним, что свойство «Размер ячейки оперативной памяти — 2 байта» означает, что в УМ-0, как в УМ-3 и УМ-2, операнд команды перехода — это количество команд, а не количество байтов.

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

Пример вычисления факториала на УМ-0 (исходное число N уже находится на вершине стека, результат также должен оказаться на вершине)

cpu mm-0

.input 1
.output 1

.code
40 01   ; 00 ; Будущий результат        ; N Res=1
40 01   ; 01 ; Ещё 1 (счётчик)          ; N Res i=1
5C 00   ; 02 ; Сдублируем счётчик       ; N Res i i
05 03   ; 03 ; Сравним с N              ; N Res i
85 09   ; 04 ; Если i>=N, -> +9 (конец) ; N Res i
40 01   ; 05 ; Занесём 1                ; N Res i 1
01 01   ; 06 ; Прибавим 1 к i           ; N Res i i+1
5D 02   ; 07 ; Обменяем местами         ; N i+1 i Res
03 02   ; 08 ; Умножим                  ; N i+1 i Res*(i+1)
5D 02   ; 0A ; Вернём на место          ; N Res*(i+1) i (i+1)
5D 01   ; 0B ; Обменяем i и i+1         ; N Res*(i+1) (i+1) i
5B 01   ; 0C ; Удалить i                ; N Res i
80 F6   ; 0D ; Продолжим цикл -> -10    ; N Res i
5B 01   ; 0E ; Выбросим i               ; N Res
99 00   ; 0F ; Конец                    ; N Res

.enter 6

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

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