EDSAC aka «Very simple machine»

Обучаясь в техническом вузе невольно сталкиваешься с такими профильными предметами, как например "низкоуровневое программирование". Первые ассоциации - конечно ассемблер, во вторую очередь - C и C++. Но не тут то было, вашему вниманию представляется актуальнейшая электронная вычислительная машина EDSAC.

Согласно Википедии, EDSAC (Electronic Delay Storage Automatic Calculator) был создан в 1949 году в Кембриджском университете по заказу Министерства Обороны Великобритании. Разработка EDSAC стала следствием своего рода «гонки вооружений» между Великобританией и США за первенство в разработке высокопроизводительных ЭВМ военного назначения. Первый в мире действующий и практически используемый компьютер с хранимой в памяти программой.

Я был бы не против поработать с этой машиной вживую, но к сожалению в нашей статье будем работать в EDSAC Simulator, найти который вы можете здесь.

Программа состоит из двух загрузчиков: Initial Orders 1 (IO1) и Initial Orders (IO2). В свою очередь загрузчики состоят из инструкций. В IO1 инструкции загружаются в ячейки 0-30, программа начинает работу с 31 ячейки. Ячеек памяти всего 1024. "Пустая" программа примет следующий вид:

[31] T 32 S

В квадратных скобках записываются комментарии к коду, в данном случае в комментарии указан адрес начала программы. Теперь к самой инструкции. Первая инструкция программы обязательно должна иметь вид T <N+1> S, где N - адрес последней инструкции программы, S - код длины слова. S обозначает "короткое слово" (17 бит), L - "длинное" слово (35 бит). Так же имеется аккумулятор aka оперативная память размером 71 бит, 35-битный умножающий регистр (2 "коротких" слова). Первое слово в умножающим регистре используется для целых чисел, с помощью второго (правого) слова можно задать дробное число.

Старший бит sign отвечает за знак числа. "Короткие" слова разделены на перфоленте одним битом (sandwich digit). В "длинном" слове sandwich digit считается частью слова, прибавляется к ячейке справа. Получается, что "длинное" слово состоит из 2 ячеек (n и n+1; n - обязательно чётное число). Чётная (правая) ячейка составляет 18 бит (само слово + sandwich digit), нечётная (левая) состоит из 17 бит, при этом старший бит отвечает за знак числа.

В инструкции T 32 S буква T обозначает код операции, в данном случае программа запишет значение из аккумулятора в ячейку 32 и обнулит аккумулятор. Возникает вопрос: что за операции и как понять за что отвечают эти самые операции? Ниже представлен список операций для EDSAC.

EDSAC работает в бинарной системе, поэтому у каждого символа есть бинарное представление. Символ # (π) вызывает режим figure shift (печать цифр), символ * (Erase) вызывает режим letter shift (печать букв и символов). В EDSAC Simulator “θ” представляется символом “@“, "φ” представляется символом “!".

Теперь перейдём к самому интересному - напишем программу. По божьему веленью, по хотенью преподавателя мне выпала нелёгкая доля разработки программы, реализующую расчёт значения многочлена по схеме Горнера с «длинным» результатом, при этом переполнение игнорируется. Если вы вдруг не знаете что такое схема Горнера, то почитать об этом вы можете здесь. Задание звучит совсем просто, но смущает только одно словосочетание - «длинный» результат. Вот тут и начинаются интересности. Под «длинным» результатом очевидно подразумевают представление ответа в виде "длинного" слова, что несколько усложняет нам задачу. С заданием мы разобрались, приступим к разбору самой программы.

[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 строчку мы вводим значение X₀, для которого нам нужно посчитать значение многочлена. В 68 строчке находится константа 1 для работы с счётчиком необработанных чисел массива. В 69 строчке находится степень многочлена. В 70 строчку занесён адрес 1-го элемента массива. В 71 строчке находится значение старшего коэффициента (предполагается, что многочлен хотя бы первой степени). С 72 по 75 строчку (многочлен 4 степени) идёт массив чисел, представляющий собой значения всех коэффициентов многочлена, кроме старшего. Многочлен примет следующий вид:

Далее с 32 по 39 строчку идёт запись констант в ячейки памяти, с которыми мы будем работать в дальнейшем. В 35 строчке идёт запись старшего коэффициента в "короткую" ячейку 2, дальше число из этой короткой ячейки умножается на 1, для того чтобы преобразовать его в "длинное" слово, записываем старший коэффициент в "длинную" ячейку 2, то есть запись в ячейки 2-3, в этих ячейках в итоге у нас и будет записан результат.

С 40 по 43 строчки идёт создание инструкции чтения для передачи следующего коэффициента. Передаётся адрес элемента и в ячейке 54 идёт чтение числа по этому адресу.

С 44 строчки по 59 строчку находится цикл, на каждом этапе цикла число из "длинной" ячейки 2 умножается на X₀ и к полученному числу прибавляется следующий коэффициент, который в свою очередь превращается в "длинное" слово умножением на 1. Как видно по коду, в 1 ячейке находится счётчик необработанных чисел массива, когда расчёт будет окончен, счётчик будет равен нулю и программа в 47 строчке закончит работу.

С 61 по 64 строчку создаётся инструкция чтения следующего коэффициента. К адресу элемента (который там уже записан) прибавляется 1 и в ячейке 54 произойдёт чтение числа по новому адресу. В 65 строчке стоит пустая операция, зачем это нужно? Это нужно для возможного дебагинга программы, вместо X S можно записать Z S и выполнить пошаговый дебагинг (в данном случае в инструкциях упущено число, по умолчанию программа будет считать, что там записан ноль).

66 строчка возвращает нас к началу цикла, возвращать она будет всегда, потому что к этому моменту у нас всегда будет обнулённый аккумулятор.

Как видно по рис. 6, программа вывела нам число 0.0000000000000000000000011100111101, где первый ноль отвечает за знак числа, а остальные 34 бита за само число. Переведём полученное число в десятичную систему и получим верный результат - 1853. Проведём теперь эксперимент с отрицательными числами, введём новые коэффициенты:

Теперь нам придётся немного видоизменить программу, а конкретно значение констант.

[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]      

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

Делая выводы, можно отметить, что всё что мы сегодня делали - бесконечно устарело было очень интересно и познавательно. Сегодня мы рассмотрели программу только на IO1, в планах есть написать вторую небольшую статью с той же программой на IO2. Это моя первая статья, очень надеюсь, что она Вам понравилась.

P.S. Полезные ссылки здесь и здесь.