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. Полезные ссылки здесь и здесь.