Модельные ЭВМ

• Адресуемая оперативная память
  • Хранит и команды, и данные

  • Ячейки памяти нумеруются последовательно с нуля (адресация)

• Команды выполняются последовательно, начиная с адреса 0

  • Команды ссылаются на данные при помощи адресов
  • Условное выполнение — изменение адреса следующей выполняемой команды

Трёхадресная ЭВМ

«Классические» операции вида «из A вычесть B, поместить результат в C» работают с тремя элементами данных — уменьшаемым, вычитаемым и разностью. В трёхадресной ЭВМ эта операция выполняется одной командой.

Оперативная память

• Максимальное количество ячеек (объём памяти)

  • 2¹⁶=65536 ячеек ⇒ 16 битов на адрес

• Размер команды в битах

  • 2⁸=256 различных команд ⇒ 8 битов на код операции

  • 3 адреса (например, уменьшаемое, вычитаемое, разность)

  • ⇒ 3*16+8=56 битов

• ⇒ Максимальное хранимое число (без знака): 256-1

  • Замечание: 2⁵⁶-1 намного больше объёма памяти

Представим в виде шестнадцатеричного числа: ККУУУУВВВВРРРР, где

1. КК — код операции

2. УУУУ — адрес первого операнда

3. ВВВВ — адрес второго операнда

4. РРРР — адрес результата

Например, 0110AE10AF10B0 (01 10AE 10AF 10B0) означает «прибавить содержимое ячейки 10AE к содержимому ячейки 10AF и записать результат в 10B0».

Все коды операция см. в учебном пособии Модельные ЭВМ¹ и на сайте эмуляторов УМ.

Вопрос для обсуждения: почему ячейка такая большая?

Регистры

• Для разбора команды: РК (регистр команд)

• Для адреса следующей команды: СА (счётчик адресов)

• Для операндов и результата: ОП1, ОП2, РЕЗ

• Для свойств данных и состояния УУ/АЛУ: РФ (регистр флагов)

Устройства ввода-вывода и хранения

Не обязательны, если предоставить возможность заполнять ОЗУ и читать оттуда.

Такт работы учебной машины

1. Чтение в РК команды из памяти по адресу, находящемуся в СК
2. Интерпретация команды в РК (для УМ-3 это просто)
3. Чтение операндов из памяти (от 0 до 2)
4. Вычисление результата (если необходимо)
   • Заполнение регистра флагов (если необходимо)
5. Запись результата в память (от 0 до 1)
6. Вычисление адреса следующей команды в СК

Пример: 01 10AE 10AF 10B0

TODO: нарисовать 6-7 состояний

Представление целых чисел

(вообще-то — школьная информатика)

Двоичные целые без знака: 2⁵⁶-1

Двоичное сложение в столбик

Разбор примера

 11010100
+01100101
 --------
100111001

Проблема переноса — решать ли её?

Предположим, в примере выше для хранения числа используется байт (8 битов). Что делать с девятым, который появился в результате сложения?

Варианты решения:

1. запомнить, что был перенос единицы, в специальном бите регистра флагов (CF, carrier flag — флаг переноса),
2. добавить перенос в дополнительную «старшую» ячейку,
3. объявить нештатную ситуацию и остановить выполнение программы,
4. забыть про то, что перенос вообще был.

В УМ-3 используется решение №1.

Представление отрицательных чисел

В виде знака и следующего за ним положительного целого числа

• ☹ неудобно (разные команды сложения и вычитания для чисел с разными знаками)

Дополнительный код как вычитание из 0 с переполнением:

• Попробуем вычесть из 0 число 26 = 11010₂ (в примере точки означают, как это принято для вычитания в столбик, заём единицы из старшего разряда)

   .......      
   …00000000
  -…00011010
   --------
   …11100110

• всё старшие биты результата, включая последний (в случае УМ-3 — 55-й), будут равны 1

  • напоминаем, что биты, как и цифры в числе, нумеруются с нуля справа налево
• полученное значение и назовём числом -26
• число отрицательно тогда и только тогда, когда старший бит равен 1

• диапазон знаковых целых чисел: от -2^w-1 до 2^w-1-1, где w — это длина машинного слова в битах

  • например, в байте можно хранить числа от -128 до 127

Формула отрицательного числа в дополнительном коде: -N = ~(N-1), где «~» — операция дополнения (замены битов на противоположные)

В таком представлении можно складывать и вычитать числа с произвольным знаком ( проверьте, точно ли это работает для двух отрицательных чисел?).

Более того, одно и то же число со старшим битом, равным 1, может считаться отрицательным в диапазоне -1 … -2⁵⁵, а может — положительным в диапазоне 2⁵⁵ … 2⁵⁶-1, операции сложения и вычитания будут работать над ними совершенно одинаково.

Когда при сложении двух чисел с одинаковым знаком сумма меняет знак, значит, модуль суммы был слишком велик, и результат «налез» на знаковый бит. В этом случае в регистре флагов взводится флаг переполнения (OF, overfuul flag), и если кому-то захотелось считать числа знаковыми, он должен проверить этот флаг.

Может ли так случиться, что в описанной ситуации переполнение произойдёт (полученное число не уместится в диапазон целых), но знаковый бит не изменится?

Сформулируйте аналогичное правило для вычитания.

Умножение и деление целых

Таблица умножения на 1 + умножение в столбик:

•     01001011
    × 00001100
      --------
      00000000
     00000000
    01001011
   01001011
   -----------
   0111000010

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

• решать её (например, вводить операцию «длинного умножения», результат которой записывается в две ячейки),
• или не решать её.

Деление в столбик — последовательно вычитаем (соответствующий бит частного равен 1) или не вычитаем (=0) делительn, в зависимости от того, больше или меньше это число текущей разности.

•  1010111|101
  -101¹   ---------
     00⁰  |10001
     001⁰
     0011⁰
     00111¹
   -   101
        10

Различие беззнаковых и знаковых умножения и деления принципиально:

• восьмибитное без знака 11010110×110 = 214*6 = 000010100000100
• восьмибитное со знаком 11010110×110 = -(00101010)*6 = -42*6 = 1111111100000100

: Насколько отличается алгоритм умножения беззнаковых и знаковых целых?

Базовые операции трёхадресной УМ-3

• Учебные машины не имеют внешних устройств

  • ⇒ не имеют операций В/В
  • Исходные данные помещаются в заданное место памяти
  • Результат проверяется также в заданном месте памяти
• ⇒ Эмулятор должен поддерживать задание «ввода» и «вывода»

• Содержимое оперативной памяти при включении УМ не определено

  • ⇒ там может содержаться что угодно (т. н. «грязная» память)
• Эмулятор может отслеживать обращение к грязной памяти на чтение
• Регистры УМ при включении обнулены (в частности, счётчик команд)
  • ⇒ выполнение программы начинается с ячейки №0 (адреса 0000)

Полная таблица команд: «Система команд модельных машин»

Базовые операции (в УМ-3 три поля адреса — ОП1, ОП2 и РЕЗ)

Установка эмулятора модельных машин на персональный компьютер

Базовая статья — сайт modelmachine.

Эмуляторы учебных машин написаны на Python3, оформлены в виде модуля и доступны в PyPi.

Эмулятор выполнен как интерпретатор командной строки. Вся работа по установке и и использованию эмулятора также идёт из командной строки.

• $ pip3 install modelmachine
  Collecting modelmachine
  …
  Installing collected packages: …

Проверка работоспособности модуля

• $ modelmachine
  usage: modelmachine [-h] [-m] {run,debug,test,asm} ...
  
  Modelmachine 0.1.6
  
  options:
    -h, --help            show this help message and exit
    -m, --protect_memory  raise an error, if program tries to read dirty memory
  
  commands:
    {run,debug,test,asm}  commands of model machine emulator
      run                 run program
      debug               run program in debug mode
      test                run internal tests end exit
      asm                 assemble model machine program

Особенности эмулятора:

Обрабатывается так называемый «образ»: текстовый файл, в котором:

• Задана эмулируемая архитектура
• Заданы адреса ячеек памяти, которые необходимо ввести и вывести
• Задано содержимое оперативной памяти (в шестнадцатеричном формате)
• Может быть задан ввод (в десятичном формате)

При запуске эмулятора в память загружается содержимое, ячейки, перечисленные для ввода, заполняются заданными (или введёнными с клавиатуры) значениями, после чего программа начинает выполнение с адреса 0.

Работа с эмулятором

Формат файла-программы

• Первая строчка - обязательное название архитектуры. Список поддерживаемых архитектур смотри ниже.

• После этого должна идти секция config, описывающая ячейки памяти, по которым нужно производить ввод и вывод.
• После этого секция кода, содержащая набор 16-ричных чисел, записываемых в память модельной машины. Пропускать часть машинного слова нельзя. Рекомендуется писать по одному машинному слову в строке, по желанию разбивая разряды на части пробелами.
• Все, что идет после символа ; - комментарий.
• Пустые строки игнорируются.
• После этого идет секция ввода - несколько чисел, разделенных пробельными символами. Их число должно совпадать с числом ячеек для ввода в параметре input в секции config.
• По окончании работы на экран будут напечатаны десятичные числа со знаком, лежащие в ячейках, перечисленных в параметре output в секции config.

Пример: сложение двух чисел. Программа add.mmach

• .cpu    mm-3
  .input  0x0100, 0x0101
  .output 0x0102
  
  .code
  01 0100 0101 0102
  99 0000 0000 0000
  
  .enter 1234 3232

Другие примеры

Запуск программы

$ python3 -m modelmachine run add.mmach
4466

• В большинстве вариантов установки достаточно modelmachine run add.mmach

Поддерживается пошаговое выполнение программы и просмотр памяти/регистров во время пошагового выполнения.

Рассмотрим более сложную программу discr.mmach, вычисляющую b²-4*a*c, где a, b и c — произвольные числа. Для простоты константу 4 также будем вводить.

.cpu mm-3
; a,b,c и d разместим по адресам 010a, 010b, 010c и 010d
; константу 4 (по адресу 0104) не будем задавать как константу, а тоже введём
.input 0x010a,0x010b,0x010c,0x0104
.output 0x010d

.code
03 010b 010b 0100 ; b*b (умножение со знаком), результат в ячейке 0100
03 010a 010c 0101 ; a*c, результат в 0101
03 0101 0104 0101 ; ac*4, результат в 0101
02 0100 0101 010d ; b²-4ac
99 0000 0000 0000

.enter 5 8 3 4

Обратите внимание: никаких имён в кодах нет, использование a,b,c и d стало возможным только по совпадению.

Используется умножение со знаком (код операции 03). Также обратите внимание на команду 03 0101 0104 0101, в которой результат записывается в одну из ячеек-операндов, то есть одна и та же ячейка выступает в качестве источника и приёмника одновременно.

Почему это возможно?

Отладка программы

В эмулятор modelmachine встроен простой, но достаточно удобный отладчик. Загрузим в него пример с дискриминантом:

• Непосредственно после старта выводится описание подсветки элементов, содержимое памяти и кратка справка по командам.
• Выделено содержимое команды, которая должна выполниться (по адресу 0x0000) и содержимое памяти, в которой отличаются заполненные ячейки (по адресам 0x0104, 0x010a, 0x010b и 0x010c) и «грязные» (значение которых формально говоря не определено), а также значение регистров

Выполним команду step (выполнение одной команды и останов):

• В памяти отмечена следующая команда, а также только что обновлённая ячейка по адресу 0x0100
• Среди регистров выделены те, что изменили значение за время выполнения команды

Поставим точку останова (breakpoint) по адресу 0x0003, и продолжим выполнение программы с помощью continue:

• Выполнилось ещё две команды, а когда выполнение дошло до точки останова, управление передалось отладчику
• Точка останова помечена отдельно
• За это время поменялась ячейка 0x101 и почти все регистры

Посмотрим содержимое памяти:

Продолжим работу:

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

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