Виды адресации
Одна из задач ЭВМ — работа с массивами данных, в простом случае — с набором ячеек, последовательно лежащих в памяти. В системе команд УМ-3 поддерживается единственный способ обращения к ячейке — прямая адресация, при которой адрес ячейки явно указывается в поле команды.
Самомодификация кода
Если мы хотим сделать так, чтобы одна и та же команда (например, на разных оборотах цикла) работала с разными ячейками памяти, необходимо в процессе выполнения программы изменять саму эту команду.
В частности, для последовательного прохождения памяти необходимо прибавлять по 1 к соответствующему полю команды. Рассмотри пример программы, заполняющей отрезок памяти числами от 1 до N.
mm3 ; ввести N<=0x100 и заполнить N ячеек, начиная с 0x1000, числами от 1 до N ; вывести первые 6 ячеек [config] input = 0x4 output = 0x1000, 0x1001, 0x1002, 0x1003, 0x1004, 0x1005 [code] 80 0000 0000 0006 ; 0 ; jump 0006 00 0000 0000 0001 ; 1 ; 1 00 0000 0000 0000 ; 2 ; 0 00 0000 0000 0000 ; 3 ; I 00 0000 0000 0000 ; 4 ; N ; 5 ; move I Array[0] 00 0001 0000 0003 ; 6 ; move 1 I 00 0005 0000 0009 ; 7 ; move 0005 0009 86 0003 0004 000d ; 8 ; sjg I > N -> 000d 00 0003 0000 1000 ; 9 ; move I Array[I-1] 01 0009 0001 0009 ; a ; add 0009 1 =: 0009 01 0003 0001 0003 ; b ; add I 1 =: I 80 0000 0000 0008 ; c ; jump 0008 99 0000 0000 0000 ; d ; halt [input] 16
- Команда по адресу 0009 (00 0003 0000 1000) изначально заносит содержимое 0003 в 1000
Команда по адресу 000a (01 0009 0001 0009) модифицирует содержимое ячейки 0009, прибавляя к ней 1, что соответствует увеличению на 1 адреса результата
- Согласно канонической схеме цикла «все ячейки, изменяемые в цикле, должны быть предварительно инициализированы». Поэтому начальные значения записываются не только в счётчик (команда по адресу 0006), но и в ячейку 0009, причём начальное содержимое этой ячейки (команда пересылки счётчика в нулевой элемент массива) хранится по адресу 0005 (выделено цветом). Обратите внимание: СК никогда не бывает равен 0005, содержимое этой ячейки нужно именно для инициализации
Пример: ввести 10 чисел по адресам 0x1000 — 0x1009, заполнить адреса 0x2000 — 0x2009 удвоенными значениями в обратном порядке, вывести 0x2000 — 0x2009.
Поскольку предполагается отладка программы и переписывание адресов, откажемся от них вовсе, заменим на последовательности вида "_***", где *** — любые символы. В конце работы заменим их на адреса автоматически.
mm3 ; ввести 10 чисел по адресам 0x1000 — 0x1009 ; заполнить адреса 0x2000 — 0x2009 удвоенными значениями в обрaтном порядке ; вывести 0x2000 — 0x2009 [config] input = 0x1000, 0x1001, 0x1002, 0x1003, 0x1004, 0x1005, 0x1006, 0x1007, 0x1008, 0x1009 output = 0x2000, 0x2001, 0x2002, 0x2003, 0x2004, 0x2005, 0x2006, 0x2007, 0x2008, 0x2009 [code] ___s 00 ___1 0000 ___I ; move 1 I 00 ___p 0000 ___m ; move ___p ___m ___c 86 ___I ___8 ___e ; sjg I N -> ___e ___m 03 1000 ___2 2009 ; mul A[0] 2 -> B[9] 01 ___I ___1 ___I ; add I 1 01 ___m __o1 ___m ; add ___m 100000000 02 ___m ___1 ___m ; sub ___m 1 80 0000 0000 ___c ; jump ___c ___e 99 0000 0000 0000 ; halt ___1 00 0000 0000 0001 ; 1 ___2 00 0000 0000 0002 ; 2 ___8 00 0000 0000 000A ; 10 ___I 00 0000 0000 0000 ; I ___p 03 1000 ___2 2009 ; mul A[0] 2 -> B[9] __o1 00 0001 0000 0000 ; ОП1[1] [input] 1 2 3 4 3 2 1 0 -1 -2
Ячейка ___m изначально содержит команду пересылки из начала первого массива в конец второго (инициализируется из ячейки ___p), а по ходу программы модифицируется дважды: адрес источника увеличивается на 1, а адрес результата уменьшается на 1. При этом используется константа 0x100000000, добавление которой к ячейке эквивалентно добавлению 1 к полю первого операнда.
После обработки вручную или вот такой программой на Python
$ python3 mmlabel.py < selfmod2.mmm > selfmod2.mm
программа примет вид
mm3 ; ввести 10 чисел по адресам 0x1000 — 0x1009 ; заполнить адреса 0x2000 — 0x2009 удвоенными значениями в обрaтном порядке ; вывести 0x2000 — 0x2009 [config] input = 0x1000, 0x1001, 0x1002, 0x1003, 0x1004, 0x1005, 0x1006, 0x1007, 0x1008, 0x1009 output = 0x2000, 0x2001, 0x2002, 0x2003, 0x2004, 0x2005, 0x2006, 0x2007, 0x2008, 0x2009 [code] 00 0009 0000 000C ; move 1 I 00 000D 0000 0003 ; move 000D 0003 86 000C 000B 0008 ; sjg I N -> 0008 03 1000 000A 2009 ; mul A[0] 2 -> B[9] 01 000C 0009 000C ; add I 1 =: I 01 0003 000E 0003 ; add 1000000 0003 02 0003 0009 0003 ; sub 1 0003 80 0000 0000 0002 ; jump 0002 99 0000 0000 0000 ; halt 00 0000 0000 0001 ; 1 00 0000 0000 0002 ; 2 00 0000 0000 000A ; 10 00 0000 0000 0000 ; I 03 1000 000A 2009 ; mul A[0] 2 -> B[9] 00 0001 0000 0000 ; ОП1[1] [input] 1 2 3 4 3 2 1 0 -1 -2
- Обычного арифметического сложения недостаточно для модификации команд:
- При добавлении/вычитании надо следить за переполнением поля адреса (например, из fffe+4 не должно получаться 10002)
Для того, чтобы «вырезать» поля команд в отдельные ячейки или подменять их, необходимы TODO [[.|побитовые операции]], которых в системе команд УМ нет
- Модификация кода многократно усложняет отладку программы
- Модификация кода делает практически невозможной верификацию (исследование на наличие ошибок) и оптимизацию (перегруппировку/замену команд для повышения эффективности работы)
Какой из этих недостатков привёл к тому, что в современных компьютерах cамомодификация практически не используется?
(А ещё надо заметить, что мы начали изобретать язык ассемблера для нашей модельной машины… возможно, не стоит слишком увлекаться?)
Двухадресная машина
Недостатки трёхадресной машины:
- несоответствие размера ячейки адресуемой памяти
- для передачи адреса достаточно двух байтов, для передачи содержимого нужно 7 — различные каналы передачи?
- большие команды вообще, в т. ч.
- команды с неиспользуемыми полями (типа move, halt)
- команды вида 01 0103 0107 0103 (операнд совпадает с результатом)
⇒ Неэффективное использование памяти (низкая т. н. плотность кода)
Двухадресная машина
Два поля операции — источник (он же приёмник) и операнд
Размер ячейки 8+2*16 == 40 битов (на одно целое число хватает). Формат ячейки:
КК ИИИИ ОООО
Арифметические операции изменяют первый операнд, например
01 0100 0200 ; add 0100 0200 -> 0100 или просто add 0100 0200
Такую запись можно читать как «прибавим к ячейке 0100 ячейку 0200»
Не ошибитесь! Результат записывается по адресу первого поля, а не последнего, как в УМ-3!
Если в процессе вычисления изменять один из операндов не планируется, операции, использующие все три адреса, перестают быть атомарными:
sub уменьшаемое вычитаемое разность → move разность уменьшаемое; sub разность вычитаемое (не забываем о порядке операндов)
jeq a b адрес → ?
Можно заменить на move c a; sub c b; jump-zero с адрес
При этом придётся хранить результат вычитания в отдельной ячейке c
Флаги
- Флаги
- однобитные ячейки для отображения свойств данных или состояния ЭВМ.
- изменяются автоматически в процессе выполнения команд
- арифметических
- сравнения
- …
хранятся в виде битов регистра флагов РФ
- используются для проверки свойств командами
- условного перехода
- условного присваивания (нет в системе команд УМ-) и т. п.
- изменяются автоматически в процессе выполнения команд
Команда сравнения 05 — это команда вычитания, которая не изменяет значения приёмника. но устанавливает флаги.
Ноль (Zero, ZF) возникает всякий раз, когда результат равен нулю
Перенос (Carry, CF) за пределы ячейки возникает при получении слишком большого числа (например, 0xfffffffff8+9) или при вычитании большего числа из меньшего (без учёта знака, что приводит к заёму бита за пределами ячейки)
Знаковое переполнение (Overflow, OF) фиксирует неожиданную смену знакового бита (например, если при сумме двух положительных чисел получается отрицательное или при вычитании положительного из отрицательного — положительное)
Знаковый бит (Sign, SF) результата также запоминается в флаге
Таким образом ZF==1 отражает сравнение равных чисел (ZF==0 — неравных), а CF==1 — сравнение беззнакового меньшего с большим.
Для знаковых чисел сравнение меньшего с большим (то есть вычитание большего из меньшего) приведёт
- для двух неотрицательных или двух отрицательных чисел — к отрицательному результату без переполнения (ZF==1 and OF == 0),
- для отрицательного и положительного чисел
- к отрицательному результату без переполнения, если сумма модулей чисел не превосходит наибольшее для данной целое число
- либо к положительному с переполнением (ZF==0 and OF==1),
- что в целом соответствует неравенству этих флагов.
Сравнение |
Значение флагов |
== |
ZF==1 |
≠ |
ZF==0 |
числа без знака |
|
< |
CF==1 |
⩽ |
(CF==1) or (ZF==1) |
⩾ |
CF==0 |
> |
(CF==0) and (ZF==0) |
числа со знаком |
|
< |
OF≠SF |
⩽ |
(OF≠SF) or (ZF==1) |
⩾ |
OF==SF |
> |
(OF==SF) and (ZF==0) |
В каких ситуациях удобно использовать флаги CF / OF ?
Выставление флагов при сравнении
Флаги в эмуляторе хранятся в следующих битах (цитата из исходного кода на Python3)
- CF = 2 ** 0
- OF = 2 ** 1
- SF = 2 ** 2
- ZF = 2 ** 3
- HALT = 2 ** 4 (это не свойство данных, а статус самого процессора — состояние после останова)
Для примера рассмотрим в отладчике программу flags.mm2, состоящую только из сравнений.
mm2 [config] input = 0x1000,0x1001,0x1002,0x1003,0x1004,0x1005 output = 0x1000,0x1001,0x1002,0x1003,0x1004,0x1005 [code] 05 1000 1000 05 1000 1001 05 1000 1002 05 1003 1004 05 1003 1005 99 0000 0000 [input] 25 20 31 0x8000000004 0x8000000002 1234
- Числа по адресам 1003 и 1004 содержат знаковый бит и могут быть интерпретированы как большие отрицательные (-549755813884 и -549755813886 соответственно). Посмотрим, как выставляются флаги при отладке.
$ python3 -m modelmachine debug flags.mm
Напоминаем, что команда отладчика "p" выводит состояние регистров, команда "s" выполняет один такт работы машины и выводит состояние регистров по окончании такта (в частности, после вычитания, которым является сравнение), а команда "q" завершает работу.Welcome to interactive debug mode. > p RAM access count: 12 Register states: ADDR : 0x0000 FLAGS : 0x0000000000 PC : 0x0000 R1 : 0x0000000000 R2 : 0x0000000000 RI : 0x0000000000 > s step 1: RAM access count: 15 Register states: ADDR : 0x0000 FLAGS : 0x0000000008 PC : 0x0001 R1 : 0x0000000000 R2 : 0x0000000019 RI : 0x0510001000 > s step 2: RAM access count: 18 Register states: ADDR : 0x0000 FLAGS : 0x0000000000 PC : 0x0002 R1 : 0x0000000005 R2 : 0x0000000014 RI : 0x0510001001 > s step 3: RAM access count: 21 Register states: ADDR : 0x0000 FLAGS : 0x0000000005 PC : 0x0003 R1 : 0xfffffffffa R2 : 0x000000001f RI : 0x0510001002 > s step 4: RAM access count: 24 Register states: ADDR : 0x0000 FLAGS : 0x0000000000 PC : 0x0004 R1 : 0x0000000002 R2 : 0x8000000002 RI : 0x0510031004 > s step 5: RAM access count: 27 Register states: ADDR : 0x0000 FLAGS : 0x0000000002 PC : 0x0005 R1 : 0x7ffffffb32 R2 : 0x00000004d2 RI : 0x0510031005 > q step 6: RAM access count: 28 Register states: ADDR : 0x0000 FLAGS : 0x0000000010 PC : 0x0006 R1 : 0x7ffffffb32 R2 : 0x00000004d2 RI : 0x9900000000 machine halted
- Сравнение равных установило флаг ZF (третий бит РФ),
- сравнение 25 с меньшим 20 сбросило все флаги,
- сравнение 25 с большим 31 установило флаг переноса (нулевой бит) и знаковый флаг (второй бит),
- а сравнение большого отрицательного 0x8000000004 с положительным 1234 дало в силу знакового переполнения OF (первый бит) положительное число 0x7ffffffb32 (ZF==0).
Примеры программ для УМ-2
Определить максимум из дух чисел:
mm2 ; ввести два числа, вывести максимум [config] input = 0x101, 0x102 output = 0x103 [code] 00 0103 0101 ; по умолчанию максимум — 0101 05 0101 0102 ; comp 0101 0102 — команда сравнения 86 0000 0004 ; если 0101 и вправду больше, перейти на 0004 00 0103 0102 ; иначе максимум — 0103 99 0000 0000 ; [input] 723 234
Ввести число и вычислить его факториал:
mm2 ; факториал [config] input = 0x100 output = 0x101 [code] 00 0102 0100 ; 0; Заносим N в счётчик 00 0101 0008 ; 1; Заносим 1 в результат 05 0102 0008 ; 2; Сравниваем счётчик и 1 85 0000 0007 ; 3; Если ≤, цикл окончен 03 0101 0102 ; 4; Домножаем результат на счётчик 02 0102 0008 ; 5; Уменьшаем счётчик на 1 80 0000 0002 ; 6; Переход на начало цикла 99 0000 0000 ; 7; конец 00 0000 0001 ; 8; 1 [input] 6
Уже говорилось, но всё равно обратите внимание: в двухадресной машине изменяется первый операнд (приёмник), а не последний, как в трёхадресной.
Одноадресная учебная машина
Классический цикл работы процессора включает в себя чтение данных из памяти и запись результата в память. Операции чтения и записи считаются довольно медленными по сравнению с арифметическими действиями. Если, следом за фон Нейманом, полагать что обменом данными занимается единственное устройство — шина — получим, что чем меньше адресов упомянуто в команде, тем быстрее она работает. Тем не менее принципиальное разницы между работой трёхадресной и двухадресной машины нет.
Почему такт работы трёхадресной и двухадресной машины занимает примерно одинаковой время?
Операции над регистрами не требуют работы с шиной и памятью. Если ограничить вычислительные операции исключительно регистрами, а память оставить только для чтения и записи, можно организовать более эффективное вычисление.
В одноадресной УМ:
- Размер ячейки — 8 разрядов КОП + 16 разрядов ОП = 24 бита
приёмник — всегда регистр (он называется аккумулятором), так что в операции указывается только адрес операнда
Появляется инструкция выгрузки (записи) аккумулятора по определённому адресу (10 адрес)
Появляется инструкция обмена содержимым между аккумулятором и дополнительным регистром S1, в который попадает остаток про делении (20)
Операция целочисленного деления в принципе особенная, и возвращает два результата — частное и остаток — но такое поведение не укладывается в наш вариант УМ-3 и УМ-2
- Остальные команды не нуждаются в реогранизации
Пример:
mm1 ; ввести два числа, вывести максимум [config] input = 0x100, 0x102 output = 0x104 [code] 00 0100 ; прочитать (здесь и далее — в аккумулятор, он же S1) 0100 10 0104 ; записать в 0104 (это максимум по умолчанию) 05 0102 ; сравнить с 0102 86 0006 ; перейти, если больше, на 0006 (всё хорошо) 00 0102 ; прочитать 0102 10 0104 ; записать в 0104 (это настоящий максимум) 99 0000 ; КОНЕЦ [input] 123 234
Команд в программе стало больше, но байтов она занимает меньше. Что ещё важнее, в одноаресной машине можно практически избежать «паразитных» операций чтения из памяти. Например, в данной программе после чтения ячейки в регистр и записи в другую ячейку сразу следует сравнение с регистром, в то время как на предыдущих архитектурах было бы сравнение с содержимым ячейки (следовательно, ещё одно чтение).
В УМ1 возникает понятие планирования вычислений.
Пример: вычислить b2-4ac
Если запрограммировать формулу как оня есть, получится примерно следующее:
mm1 [config] input = 0x000B, 0x000C, 0x000D output = 0x000E [code] 00 000C ; <- b 03 000C ; * b 10 000F ; -> b² 00 0011 ; <- 4 03 000B ; * a 03 000D ; * c 10 0010 ; -> 4ac 00 000F ; <- b² 02 0010 ; - 4ac 10 000E ; -> d 99 0000 ; halt 000000 ; a 000000 ; b 000000 ; c 000000 ; d 000000 ; b² 000000 ; 4ac 000004 ; 4 [input] 2 5 3
Если же обратить внимание на то, что хранить b2не обязательно, программа получится на две инструкции короче (причём обе — «медленные» инструкции работы с памятью):
mm1 [config] input = 0x0009, 0x000A, 0x000B output = 0x000C [code] 00 000E ; <- 4 03 0009 ; * a 03 000B ; * c 10 000D ; -> 4ac 00 000A ; <- b 03 000A ; * b 02 000D ; - 4ac 10 000C ; -> d 99 0000 ; halt 000000 ; a 000000 ; b 000000 ; c 000000 ; d 000000 ; 4ac 000004 ; 4 [input] 2 5 3
Замечание. Если регистр всего один, сэкономить можно только на последовательных модификациях этого регистра, для более сложных вычислений надо предусмотреть дополнительные регистры и возможность указать в инструкции, с какими из них идёт работа.