EDSAC aka «Very simple machine»
Обучаясь в техническом вузе невольно сталкиваешься с такими профильными предметами, как например «низкоуровневое программирование». Первые ассоциации — конечно ассемблер, во вторую очередь — C и C++. Но не тут то было, вашему вниманию представляется актуальнейшая электронная вычислительная машина EDSAC.
Рис. 1. Непосредственно EDSACСогласно Википедии, EDSAC (Electronic Delay Storage Automatic Calculator) был создан в 1949 году в Кембриджском университете по заказу Министерства Обороны Великобритании. Разработка EDSAC стала следствием своего рода «гонки вооружений» между Великобританией и США за первенство в разработке высокопроизводительных ЭВМ военного назначения. Первый в мире действующий и практически используемый компьютер с хранимой в памяти программой.
Я был бы не против поработать с этой машиной вживую, но к сожалению в нашей статье будем работать в EDSAC Simulator, найти который вы можете здесь.
Рис. 2. EDSAC SimulatorПрограмма состоит из двух загрузчиков: Initial Orders 1 (IO1) и Initial Orders (IO2). В свою очередь загрузчики состоят из инструкций. В IO1 инструкции загружаются в ячейки 0–30, программа начинает работу с 31 ячейки. Ячеек памяти всего 1024. «Пустая» программа примет следующий вид:
[31] T 32 SВ квадратных скобках записываются комментарии к коду, в данном случае в комментарии указан адрес начала программы. Теперь к самой инструкции. Первая инструкция программы обязательно должна иметь вид T , где N — адрес последней инструкции программы, S — код длины слова. S обозначает «короткое слово» (17 бит), L — «длинное» слово (35 бит). Так же имеется аккумулятор aka оперативная память размером 71 бит, 35-битный умножающий регистр (2 «коротких» слова). Первое слово в умножающим регистре используется для целых чисел, с помощью второго (правого) слова можно задать дробное число.
Рис. 3. Короткое слово
Рис. 4. Длинное словоСтарший бит sign отвечает за знак числа. «Короткие» слова разделены на перфоленте одним битом (sandwich digit). В «длинном» слове sandwich digit считается частью слова, прибавляется к ячейке справа. Получается, что «длинное» слово состоит из 2 ячеек (n и n+1; n — обязательно чётное число). Чётная (правая) ячейка составляет 18 бит (само слово + sandwich digit), нечётная (левая) состоит из 17 бит, при этом старший бит отвечает за знак числа.
В инструкции T 32 S буква T обозначает код операции, в данном случае программа запишет значение из аккумулятора в ячейку 32 и обнулит аккумулятор. Возникает вопрос: что за операции и как понять за что отвечают эти самые операции? Ниже представлен список операций для EDSAC.
Инструкция | Комментарий |
A n | Добавление числа из ячейки памяти n в аккумулятор |
S n | Вычитание числа из ячейки памяти n из аккумулятора |
H n | Копирование числа из ячейки памяти n в умножающий регистр |
V n | Умножение числа из ячейки памяти n на число в умножающем регистре; добавление результата в аккумулятор |
N n | Умножение числа из ячейки памяти n на число в умножающем регистре; вычитание результата из аккумулятора |
T n | Перенос числа из аккумулятора в ячейку памяти n с обнулением аккумулятора |
U n | Перенос числа из аккумулятора в ячейку памяти n без обнуления аккумулятора |
C n | Побитовое «И» числа в ячейке памяти n с числом в умножающем регистре; добавление результата в аккумулятор |
R 2n-2 | Сдвиг числа в аккумуляторе на n битов вправо |
L 2n-2 | Сдвиг числа в аккумуляторе на n битов влево |
E n | Если число в аккумулятор >= 0, то совершается переход в ячейку n, иначе программа просто продолжает работу |
G n | Если число в аккумулятор < 0, то совершается переход в ячейку n, иначе программа просто продолжает работу |
I n | Считать следующий символ с бумажной ленты и сохранить его как младшие 5 бит в ячейке n. |
O n | Вывести символ, представленный старшими 5 битами ячейки памяти n |
F n | Прочесть вывод последнего символа для проверки |
X | Отсутствие операции |
Y | Округлить число в аккумуляторе до 34 бит |
Z | Остановить машину; Зазвенит очень странный предупреждающий звонок. |
Рис. 5. Бинарные коды символов в EDSACEDSAC работает в бинарной системе, поэтому у каждого символа есть бинарное представление. Символ # (π) вызывает режим figure shift (печать цифр), символ * (Erase) вызывает режим letter shift (печать букв и символов). В EDSAC Simulator «θ» представляется символом »@», «φ» представляется символом »!».
Теперь перейдём к самому интересному — напишем программу. По божьему веленью, по хотенью преподавателя мне выпала нелёгкая доля разработки программы, реализующую расчёт значения многочлена по схеме Горнера с «длинным» результатом, при этом переполнение игнорируется. Если вы вдруг не знаете что такое схема Горнера, то почитать об этом вы можете здесь. Задание звучит совсем просто, но смущает только одно словосочетание — «длинный» результат. Вот тут и начинаются интересности. Под «длинным» результатом очевидно подразумевают представление ответа в виде «длинного» слова, что несколько усложняет нам задачу. С заданием мы разобрались, приступим к разбору самой программы.
Листинг 1. EDSAC order code. Расчёт значения многочлена по схеме Горнера.[31] T 76 S [инструкция, ссылающаяся на последнюю инструкцию + 1]
[32] A 69 S [загрузка в аккумулятор степени многочлена]
[33] T 1 S [запись степени многочлена в ячейку 1]
[34] A 71 S [загрузка старшего коэффициента в аккумулятор]
[35] T 2 S [запись старшего коэффициента в рабочую ячейку 2]
[36] H 68 S [запись 1 в умножающий регистр]
[37] V 2 S [умножение числа из ячейки 2 на число в умножающем регистре]
[38] R 1 S [сдвиг числа вправо на 2 бита, для коррекции умножения]
[39] T 2 L [запись старшего коэффициента в длинную ячейку]
[40] A 70 S [загрузка в аккумулятор адреса 1-го элемента массива]
[41] L 0 L [сдвиг аккумулятора, для коррекции]
[42] A 54 S [прибавляем код инструкции с нулевым полем адреса]
[43] T 54 S [запись сформированной инструкции, обнуление аккумулятора]
[44 loop] A 1 S [загружаем в аккумулятор счётчик необработанных элементов массива]
[45] S 68 S [вычитание константы = 1]
[46] E 48 S [if (acc >= 0) goto 48 else end]
[47] Z 0 S [точка остановки, завершение программы]
[48] T 1 S [обновляем значение счетчика и обнуляем аккумулятор]
[49] H 67 S [запись X0 в умножающий регистр]
[50] V 2 L [умножение числа из ячейки 2 на число в умножающем регистре]
[51] L 1024 S [сдвиг числа влево на 12 бит, для коррекции умножения]
[52] L 4 S [сдвиг числа влево на 4 бита, для коррекции умножения]
[53] T 2 L [запись результата умножения в длинную ячейку]
[54 r1] A 0 S [загрузка в аккумулятор значения из ячейки 0]
[55] T 4 S [запись в рабочую ячейку 4]
[56] H 68 S [запись 1 в умножающий регистр]
[57] V 4 S [умножение числа из ячейки 4 на число в умножающем регистре]
[58] R 1 S [сдвиг числа вправо на 2 бита, для коррекции умножения]
[59] A 2 L [добавление числа из "длинной" ячейки 2 в аккумулятор]
[60] T 2 L [запись этого значения в "длинную" ячейку 2, обнуление аккумулятора]
[61] A 68 S [загрузка в аккумулятор значение константы = 1]
[62] L 0 L [сдвиг аккумулятора, для коррекции]
[63] A 54 S [прибавляем код инструкции, исполненной на предыдущем шаге]
[64] T 54 S [записываем сформированную инструкцию в память]
[65] XS
[66] E 44 S [повторяем все операции; аккумулятор обнулен]
[67] P 1 L [X0 - фиксированное значение X, по которому мы вычисляем значение многочлена ]
[68 const 1] P 0 L [1]
[69 power] P 2 S [степень многочлена]
[70 addr] P 36 S [адрес 1-го элемента массива]
[71] P 0 L [a4 = 1]
[72] P 30 S [a3 = 60]
[73] P 7 S [a2 = 14]
[74] P 3 L [a1 = 7]
[75] P 2 L [a0 = 5] Разберём по строчкам. С 31 ячейкой мы уже разобрались — начало программы, ссылка на ячейку с последней инструкцией + 1. Дальше объяснение лучше всего начать с конца. В конце программы с 67 по 75 строчку идёт объявление констант. В 67 строчку мы вводим значение X0, для которого нам нужно посчитать значение многочлена. В 68 строчке находится константа 1 для работы с счётчиком необработанных чисел массива. В 69 строчке находится степень многочлена. В 70 строчку занесён адрес 1-го элемента массива. В 71 строчке находится значение старшего коэффициента (предполагается, что многочлен хотя бы первой степени). С 72 по 75 строчку (многочлен 4 степени) идёт массив чисел, представляющий собой значения всех коэффициентов многочлена, кроме старшего. Многочлен примет следующий вид:
Далее с 32 по 39 строчку идёт запись констант в ячейки памяти, с которыми мы будем работать в дальнейшем. В 35 строчке идёт запись старшего коэффициента в «короткую» ячейку 2, дальше число из этой короткой ячейки умножается на 1, для того чтобы преобразовать его в «длинное» слово, записываем старший коэффициент в «длинную» ячейку 2, то есть запись в ячейки 2–3, в этих ячейках в итоге у нас и будет записан результат.
С 40 по 43 строчки идёт создание инструкции чтения для передачи следующего коэффициента. Передаётся адрес элемента и в ячейке 54 идёт чтение числа по этому адресу.
С 44 строчки по 59 строчку находится цикл, на каждом этапе цикла число из «длинной» ячейки 2 умножается на X0 и к полученному числу прибавляется следующий коэффициент, который в свою очередь превращается в «длинное» слово умножением на 1. Как видно по коду, в 1 ячейке находится счётчик необработанных чисел массива, когда расчёт будет окончен, счётчик будет равен нулю и программа в 47 строчке закончит работу.
С 61 по 64 строчку создаётся инструкция чтения следующего коэффициента. К адресу элемента (который там уже записан) прибавляется 1 и в ячейке 54 произойдёт чтение числа по новому адресу. В 65 строчке стоит пустая операция, зачем это нужно? Это нужно для возможного дебагинга программы, вместо X S можно записать Z S и выполнить пошаговый дебагинг (в данном случае в инструкциях упущено число, по умолчанию программа будет считать, что там записан ноль).
66 строчка возвращает нас к началу цикла, возвращать она будет всегда, потому что к этому моменту у нас всегда будет обнулённый аккумулятор.
Рис. 6. Результат выполнения программыКак видно по рис. 6, программа вывела нам число 0.0000000000000000000000011100111101, где первый ноль отвечает за знак числа, а остальные 34 бита за само число. Переведём полученное число в десятичную систему и получим верный результат — 1853. Проведём теперь эксперимент с отрицательными числами, введём новые коэффициенты:
Теперь нам придётся немного видоизменить программу, а конкретно значение констант.
Листинг 2. Изменение констант[67] P 5 S [X0 - фиксированное значение X, по которому мы вычисляем значение многочлена ]
[68 const 1] P 0 L [1]
[69 power] P 2 S [степень многочлена]
[70 addr] P 36 S [адрес 1-го элемента массива]
[71] P 55536 S [a4 = -20000]
[72] P 2 S [a3 = 4]
[73] P 9 L [a2 = 19]
[74] P 5 L [a1 = 11]
[75] P 268 S [a0 = 536] 
Рис. 7. Результат выполнения программыВ результате работы программы мы получаем 1.11111110100000101000101011110010010, знаковый бит говорит нам, что число отрицательное. Отрицательные числа в EDSAC представлены в виде дополнительного кода, подробнее об числах в EDSAC можно почитать в статье моего друга и коллеги. Переведём число в прямой код — 0.0000001011111010111010100001101110. Переведём полученное число в десятичную систему и получим верный результат — -199993454.
Делая выводы, можно отметить, что всё что мы сегодня делали — бесконечно устарело было очень интересно и познавательно. Сегодня мы рассмотрели программу только на IO1, в планах есть написать вторую небольшую статью с той же программой на IO2. Это моя первая статья, очень надеюсь, что она Вам понравилась.
P.S. Полезные ссылки здесь и здесь.
