Решил я, значит, изучить, как работают компьютеры на самом низком уровне. Это тот уровень, где работают всякие железяки, транзисторы, логические элементы и так далее. Чтобы полностью закрепить материал, я решил построить простенькую ЭВМ на редстоуне в Minecraft. Эта статья о том, как работают ЭВМ на уровне логических элементов и о том, как я построил прототип такой ЭВМ в Minecraft. В конце я оставил ссылку на GitHub-репозиторий с проектом.
Введение в логические элементы
Перед тем, как начать, нам следует изучить, как работают базовые логические элементы. Все ЭВМ создаются при помощи нескольких базовых "кирпичиков", которые называются логическими элементы. Вы, вероятно, уже слышали о них. Это знакомые вам элементы AND, OR, XOR, NOT, и их производные – NAND, NOR, XNOR а также другие, подобные им элементы. Все элементы (обычно) получают на вход 2 сигнала и на выходе выдают 1 результирующий сигнал.
Сигналами в цифровой схемотехнике являются логическая единица и логический ноль. В реальной электротехнике эти значения соответствуют диапазонам напряжений (логический ноль – от 0 до 0,5 вольт, логическая единица – от 2,7 до 5 вольт в ТТЛ логике, напряжение между диапазонами соответствует неопределённому состоянию). В игре все иначе, у нас есть сигнал, либо его нет, третьего не дано. В этом плане в игре намного легче работать с сигналами.
Каждый логический элемент имеет свое условное графическое обозначение и описывается таблицей истинности, в которой показано, что получится на выходе элемента, если подать определенные сигналы на его входы. Ниже приведены основные элементы и их таблицы истинности.
Основные логические элементы
Так как мы будем строить ЭВМ в игре, нам нужны аналоги этих элементов, построенные на редстоуне. Благо их очень легко воссоздать в игре.
Логические элементы в Minecraft
Из этих элементов строятся все последующие схемы, поэтому их знание просто необходимо для понимания принципа работы ЭВМ.
Элементы ЭВМ
В любой ЭВМ есть обязательные элементы, без которых она не будет работать. К ним относятся:
АЛУ (Арифметико-логическое устройство) – мозг ЭВМ,
Регистры – для хранения информации, предназначенной для АЛУ,
Память – для хранения команд и данных,
Счётчик команд – для отслеживания текущей команды,
Декодер команд – для преобразования инструкций в сигналы, понятные для ЭВМ.
Каждый из этих элементов мы должны реализовать при помощи логических элементов, учитываю специфику игры.
Принцип работы ЭВМ
Главным элементом работы ЭВМ является цикл выполнения машинной команды: fetch-decode-execute (получить-декодировать-исполнить). Для исполнения каждой команды ЭВМ должна сначала получить команду из памяти, затем декодировать её и уже потом исполнить. Для этих целей предназначены счётчик команд, память и декодер команд.
Инструкции оперируют с регистрами. В них расположены некие полезные данные. Над данными из регистров могут производиться арифметические или логические операции. За эти действия отвечает АЛУ. А ещё данные можно заносить в память из регистров или наоборот, доставать из памяти в регистры.
АЛУ
АЛУ выполняет арифметические и логические операции над числами, которые расположены в регистрах. Для сложения и вычитания чисел существует следующая схема:
Full-adder
Эта схема называется full-adder. Взглянув на таблицу истинности можно заметить, что эта схема складывает три бита. Зачем три? Для того чтобы можно было подключить несколько таких элементов последовательно и складывать уже не два бита, а сколько нам нужно. Если мы подключим выход Cout одного full-adder'a ко входу Cin другого full-adder'a, то мы получим уже 2-разрядный сумматор. Если соединить 8 таких full-adder'ов, то мы получим 8-разрядный сумматор:
8-бинтый сумматор
А ещё третий вход на сумматоре позволяет нам выполнять операцию вычитания. Существуют так называемые дополнительные коды, при помощи которых нашу схему можно научить вычитанию. Если мы инвертируем число (в двоичном виде) и добавим к нему 1, у нас получится дополнительный код (например число 5 в двоичном виде выглядит как 0101, его дополнительный код – 1010 + 1 = 1011, 11 в десятичной системе). Нам интересны дополнительные коды потому, что они позволяют нам сымитировать вычитание. Если мы сложим число с дополнительным кодом другого числа, мы получим результат их разности (например возьмем числа 7 и 2. Переведем их в двоичную систему, 7 это 0111, а 2 – 0010. Вычисляем дополнительный код для 2: 1101 + 1 = 1110. Складываем 0111 + 1110 = 10101, отбрасываем старший бит и получаем 0101 = 5 в десятичной системе, что является результатом вычитания 2 из 7). Чтобы получить дополнительный код числа в схеме мы используем элемент XOR, для инверсии битов, а добавить единицу нам поможет свободный третий вход первого full-adder'а.
8-битный сумматор, который может и вычитать
Теперь, если мы подадим единицу на вход SUB, наша схема выполнит вычитание двух чисел, вместо сложения.
Кстати я вам немного наврал. Наша схема умеет выполнять только арифметические операции, поэтому у нас получилось не АЛУ, а АУ (Арифметическое устройство) но для нашего прототипа этого вполне будет хватать.
АЛУ (АУ). Схема
На АЛУ мы имеем два входа, по 8 бит (А и B), переключатель режима (сложение/вычитание, SUB) и один выход, тоже 8 бит (Q). Также в дальнейшем нам понадобиться сравнивать числа. Для этого предусмотрен еще один выход (ZR), который активируется, если результат операции равен нулю.
ALU в игре
Регистры
Регистры служат для хранения информации, обрабатываемой АЛУ. По факту регистры – это просто память внутри процессора. Память в ЭВМ реализуется с помощью триггеров. Эти устройства позволяют хранить 1 бит информации. Существует много различных триггеров, но мы будем использовать D-триггер, так как в игре он занимает всего два блока:
D-триггер в Minecraft
Триггеры описываются не таблицами истинности, а временными диаграммами, на которых показано, как ведет себе триггер, при подачи сигнала на разные входы.
Временная диаграмма D-тригггера
D-триггер запоминает 1 бит информации, полученный по шине D, если сигнал C равен единице. Если сигнал C равен нулю, то триггер запоминает последний полученный бит и выдает его на выходе Q. Так же как и с сумматором, мы можем расположить рядом несколько триггеров, для увелечения разрядности ячейки памяти. Поставив 8 таких триггеров параллельно и объединив их вход C, мы получим 8-битный регистр. В нашей ЭВМ будет 8 регистров, так как их можно адресовать, используя 3 бита.
Блок с регистрами. Схема
Блок с регистрами состоит из 8 регистров, одного 8-битного входа (IN), для записи данных, одной шины адреса, для записи данных (W1), двух выходов по 8 бит, для чтения информации из регистров (O1 и O2) и двух шин адреса, для выбора регистров из которых считывается информация (R1 и R2). Также в блоке с регистрами есть вход WR, который отвечает за запись данных. Косая линия у входа записи означает, что микросхема выполняет запись по положительному фронту входного сигнала. Это значит, что запись будет выполнена один раз, когда будет подан сигнал. В нашем случае мы подключим этот вход к таймеру.
Блок с регистрами в игре
Память
Любой ЭВМ нужна память, как минимум для команд, которые будут исполняться и хранения других данных, так как количество регистров ЭВМ всегда ограничено. Существует два варианта организации памяти в ЭВМ:
Архитектура Фон-Неймана,
Гарвардская архитектура.
Архитектура Фон-Неймана предполагает совместное хранение данных и команд в одной памяти, тогда как Гарвардская архитектура предполагает разделение памяти, отдельно под команды и данные.
В нашем прототипе я выбрал Гарвардскую архитектуру, так как памяти у нашей ЭВМ будет очень мало (64 байта), а машинные слова будут занимать 16-бит. Память, как и регистры, использует D-триггеры, отличие в том, что память может хранить намного больше данных.
Для произвольных данных будет использоваться RAM-память, а для команд – ROM-память.
RAM. Схема
В блоке RAM (Random Access Memory – память произвольного доступа) имеется 64 ячейки памяти по 8-бит, один 8-битный вход, для записи данных (IN), 6-битная шина адреса (AD), переключатель для чтения данных (RE), вход для записи данных (WR) и один 8-битный выход (O1). Если на вход RE подается сигнал, память выдает значение ячейки по адресу AD на шину.
RAM в игре
ROM-память похожа на RAM-память за исключением того, что в неё нельзя записывать данные, их можно только читать. ROM-память будет напрямую подключена к счётчику команд, так как она больше нигде не используется.
ROM. Схема
В блоке ROM (Read-only Memory – память только для чтения) также имеется 64 ячейки памяти по 8 бит и одна входная адресная шина, разрядностью 6 бит (AD). Эта память просто выдает команды, расположенные по соответствующему адресу. Так как размер машинного слова 16 бит, здесь у нас два выхода по 8 бит объеденины в один (O1).
ROM в игре
Программирование ЭВМ происходит путём выставления редстоун блоков в определённые позиции в ячейках ROM-памяти.
Счётчик команд
Счётчик команд нужен для того, чтобы мы могли загружать новые инструкции из памяти и выполнять их. Счётчик команд содержит регистр, в котором хранится номер текущей команды и часы. Часы через определённое количество времени увеличивают значение счетчика на единицу.
У нас счётчик напрямую подключен к ROM-памяти, для того, чтобы ЭВМ сразу получала новую команду и выполняла её. Часы в счётчике являются синхронизирующим механизмом, их период или частота рассчитываются на основе быстродействия всей системы. В моём случае мне удалось выжать из моей ЭВМ невероятные 0,2 герца (1 команда в 5 секунд).
Счётчик команд. Схема
У счётчика присутствует вход HLT, который при подаче на него сигнала останавливает работу всей ЭВМ, а также вход адресной шины (AD), для выполнения ветвления. Во время ветвления счётчик команд записывает в свой регистр значение из входа AD. Ветвление происходит, если на вход JMP подан сигнал.
Ветвление может быть как условным, так и безусловным. Условное ветвление выполняется, если флаг ZR из АЛУ равен единице и выставлен флаг условного ветвления. Безусловное ветвление выполняется если выставлен флаг обычного ветвления. Флаги ветвления выставляет декодер команд.
PC в игре
Декодер команд
Декодер команд одна из самых главных частей ЭВМ, так как он преобразовывает двоичные коды управляющие сигналы для ЭВМ.
Если вы заметили, то мы предусмотрели в предыдущих компонентах различные управляющие входы. Это входы записи и чтения для регистров, записи и чтения для памяти, вход режима АЛУ, флаги ветвление и другие. Именно с этими входами и работает декодер команд.
Декодер берет машинную инструкцию и преобразует её в управляющие сигналы для других элементов ЭВМ. Если вы помните, мы используем 16-битный машинные слова для команд в нашем прототипе. Для задания типа машинной команды используются первые 4 бита из машинного слова. Они определяют те флаги, которые нужно активировать для выполнения команды. Остальные 12 бит предназначены для номеров регистров, с которыми проводится операция, адреса памяти или другого значения.
Я реализовал 9 инструкций, которых вполне достаточно, чтобы писать простые программы. Список операций:
NOP – нет операции,
HLT – остановка часов и работы всей ЭВМ,
ADD rdest, r1, r2 – сложение r1 и r2 и запись результата в rdest,
SUB rdest, r1, r2 – вычитание r1 из r2 и запись результата в rdest,
STR rsource, address – запись rdest в ячейку памяти по адресу address,
LOD rdest, address – запись значения из ячейки памяти по адресу address в регистр rdest,
LDI rdest, value – загрузка в регистр rdest значения value,
JMP address – переход в локацию address,
JIZ address – условный переход в локацию address. Выполняется, если результат последней операции АЛУ – ноль.
Например, рассмотрим операцию вычитания. За нее отвечает инструкция SUB, с кодом 0010. Эта инструкция вычитает одно число из другого и записывает результат в регистр. Допустим, мы хотим вычесть значение второго регистра из значения первого регистра и записать результат в третий регистр. Тогда машинная инструкция будет выглядеть так: 0001_0010_0011_0010 (справа налево, первые 4 бита – код операции, вторые - регистр назначения, третье – вычитаемое, четвертые – уменьшаемое). После декодирования этой инструкции декодер выставляет флаги записи в регистр и вычитания в АЛУ. После следующего переключения счётчика результат операции будет записан в указанный регистр.
Декодер. Схема
Декодер имеет один вход, для первых четырех бит инструкции и 10 выходов, которые определяют текущую операцию. Остальные 12 бит выставляются на главную шину.
Декодер в игре
Мультиплексор
Еще один элемент, который я не упомянул в начале, но тоже очень важный для построения ЭВМ это мультиплексор. Мультиплексор – устройство, которое имеет два основных входа и один выход. Оно предназначено для переключения выходного сигнала, в зависимости от управляющего флага.
Мультиплексор
Мультиплексор имеет три входа и один выход. На входы IN1 и IN2 подаются основные сигналы, а на вход SET передается управляющий бит, который переключает мультиплексор. В зависимости от управляющего бита, на выходе мы получаем либо значение входа IN1, либо значение входа IN2.
Мультиплексор в игре
Собираем все вместе
Теперь, когда мы построили все элементы по отдельности, пришло время всех их соединить. Для этого я нарисовал красивую схему нашей ЭВМ.
Полная схема ЭВМ
Если вас уже перегружает эта схема, то представьте, как работает ваш процессор, со всякими многоуровневыми кэшами, встроенным графическим ядром, технологиями виртуализации и другими новшествами. Стоит отдать должное разработчикам современных процессоров, они выполняют очень сложную работу.
На этой схеме мы собрали воедино все компоненты ЭВМ. Числа возле входов обозначают соответствующие биты 12-разряздного числа на шине (причем включаются оба числа, поэтому 11-9 означает 3 бита – 11, 10 и 9).
На схеме также присутствуют 10 не подключенных управляющих сигналов (HLT, BRANCH, REG WRITE, WRITE IM и т.д). Сигналы на эти входы подает декодер, после декодировки команды. Возвращаясь к инструкции SUB, декодер подаст сигналы на входы ALU SUB и REG WRITE.
А вот так это все выглядит в игре:
ЭВМ в игре
Теперь, когда мы собрали все воедино, можно программировать эту ЭВМ. Это делается при помощи блоков редстоуна, которые нужно выставлять в ROM-память. На двоичных кодах писать конечно можно, но это не то чтобы удобно. Для упрощения программирования, я сделал свой язык ассемблера для этой ЭВМ.
Ассемблер для ЭВМ
Компилятор ассемблера я написал на Python. Тут как раз есть библиотека для мода Schematica на Minecraft, при помощи которой можно перенести инструкции из текстового файла в мир игры.
Мой компилятор преобразовывает инструкции ассемблера в двоичные коды. После компиляции в двоичный код, идет преобразование двоичных чисел в блоки редстоуна, которые представляют собой машинные команды для ЭВМ. Рассмотрим сам компилятор.
Сначала мы объявляем список всех доступных инструкций:
Буква r обозначает регистр, а v – числовое значение. Например, операндами для инструкций АЛУ должны быть три регистра, для инструкций ветвления – только одно числовое значение и так далее.
Обработка инструкций происходит в функции compile_line. На вход данная функция получает одну операцию (к примеру ADD r1, r2, r1) и преобразует её в двоичный код:
defcompile_line(line):
result = 0b0
operation = line[:3].upper()
operands = line[4:].split(', ')
if (operands[0] == ''):
operands = operands.pop()
try:
operations[operation]
except KeyError:
raise ValueError(line + " | Incorrect operation: " + operation)
current_operation = operations[operation]
result = result | current_operation
Здесь мы выполняем проверку названия инструкции и добавляем её код к результату. Далее идет валидации операндов:
if (current_operation in alu_operations):
operands_values = check_operation(line, operands, alu_map)
result = result | operands_values[0] << 5
| operands_values[1] << 10
| operands_values[2] << 13elif (current_operation in immediate_operations):
operands_values = check_operation(line, operands, immediate_map)
if (operands_values[1] > 255):
raise ValueError(
line + " | Incorrect value, should be less than 256: "
+ str(operands_values[1]))
result = result | operands_values[0] << 5
| operands_values[1] << 8elif (current_operation in memory_operations):
operands_values = check_operation(line, operands, memory_map)
if (operands_values[1] > 63):
raise ValueError(
line + " | Incorrect value, should be less than 64: "
+ str(operands_values[1]))
result = result | operands_values[0] << 5
| operands_values[1] << 10elif (current_operation in jump_operations):
operands_values = check_operation(line, operands, jump_map)
if (operands_values[0] > 31):
raise ValueError(
line + " | Incorrect value, should be less than 32: "
+ str(operands_values[0]))
result = result | operands_values[0] << 11return ('{:016b}'.format(result))
В зависимости от типа операции проводятся дополнительные проверки, например, если операция связана с памятью, то адрес ячейки памяти не может превышать 64, так как у нас всего 64 ячейки памяти. Функция check_operation выполняет проверку количества операндов и их соответствие типу инструкции. Эта функция возвращает массив с преобразованными в числа операндами. На выходе у нас получается двоичное число, которое затем преобразовывается в блоки редстоуна в игре.
Исходный код компилятора находится по ссылке на GitHub. Там же находятся и примеры кода, который можно написать для ЭВМ.
Тест
Я написал простую программу, для вычисления 14-го числа Фибоначчи (233):
С учетом скорости ЭВМ (умопомрачительные 0,2 герца) эта программа будет выполняться несколько минут. Так на деле и оказалось, я ждал около 5 минут, пока ЭВМ закончит вычисления. После ожидания я увидел заветное число 11101001 в нулевой ячейке памяти.
Результат вычислений
Заключение
В целом я доволен результатом. Эту ЭВМ еще можно дополнять устройствами ввода-вывода, расширять память, добавить регистр флагов и так далее. Благо прототип позволяет развивать эту идею и дальше.
Надеюсь вы узнали что-то новое про внутреннее устройство компьютеров и ЭВМ в целом. Для меня было очень интересно строить ЭВМ в игре и писать компилятор для собственного ассемблера. Я оставил ссылку на GitHub репозиторий, для того, чтобы вы могли сами опробовать данную ЭВМ. Вам понадобиться версия Minecraft 1.20.1 и мод Schematica. На GitHub указаны инструкции для компиляции кода и запуска собственных программ. Также я оставил на GitHub архив с миром, в котором строил ЭВМ. В этом мире есть все компоненты по отдельности, если вам интересно изучить, как они работают.