Reedus0 7 июн в 10:00

Как я компьютер в Minecraft построил

11 мин

15K

Программирование*Assembler*ПроцессорыИгры и игровые консолиЭлектроника для начинающих

Решил я, значит, изучить, как работают компьютеры на самом низком уровне. Это тот уровень, где работают всякие железяки, транзисторы, логические элементы и так далее. Чтобы полностью закрепить материал, я решил построить простенькую ЭВМ на редстоуне в Minecraft. Эта статья о том, как работают ЭВМ на уровне логических элементов и о том, как я построил прототип такой ЭВМ в Minecraft. В конце я оставил ссылку на GitHub-репозиторий с проектом.

Введение в логические элементы

Перед тем, как начать, нам следует изучить, как работают базовые логические элементы. Все ЭВМ создаются при помощи нескольких базовых "кирпичиков", которые называются логическими элементы. Вы, вероятно, уже слышали о них. Это знакомые вам элементы AND, OR, XOR, NOT, и их производные – NAND, NOR, XNOR а также другие, подобные им элементы. Все элементы (обычно) получают на вход 2 сигнала и на выходе выдают 1 результирующий сигнал.

Сигналами в цифровой схемотехнике являются логическая единица и логический ноль. В реальной электротехнике эти значения соответствуют диапазонам напряжений (логический ноль – от 0 до 0,5 вольт, логическая единица – от 2,7 до 5 вольт в ТТЛ логике, напряжение между диапазонами соответствует неопределённому состоянию). В игре все иначе, у нас есть сигнал, либо его нет, третьего не дано. В этом плане в игре намного легче работать с сигналами.

Каждый логический элемент имеет свое условное графическое обозначение и описывается таблицей истинности, в которой показано, что получится на выходе элемента, если подать определенные сигналы на его входы. Ниже приведены основные элементы и их таблицы истинности.

Так как мы будем строить ЭВМ в игре, нам нужны аналоги этих элементов, построенные на редстоуне. Благо их очень легко воссоздать в игре.

Из этих элементов строятся все последующие схемы, поэтому их знание просто необходимо для понимания принципа работы ЭВМ.

Элементы ЭВМ

В любой ЭВМ есть обязательные элементы, без которых она не будет работать. К ним относятся:

АЛУ (Арифметико-логическое устройство) – мозг ЭВМ,
Регистры – для хранения информации, предназначенной для АЛУ,
Память – для хранения команд и данных,
Счётчик команд – для отслеживания текущей команды,
Декодер команд – для преобразования инструкций в сигналы, понятные для ЭВМ.

Каждый из этих элементов мы должны реализовать при помощи логических элементов, учитываю специфику игры.

Принцип работы ЭВМ

Главным элементом работы ЭВМ является цикл выполнения машинной команды: fetch-decode-execute (получить-декодировать-исполнить). Для исполнения каждой команды ЭВМ должна сначала получить команду из памяти, затем декодировать её и уже потом исполнить. Для этих целей предназначены счётчик команд, память и декодер команд.

Инструкции оперируют с регистрами. В них расположены некие полезные данные. Над данными из регистров могут производиться арифметические или логические операции. За эти действия отвечает АЛУ. А ещё данные можно заносить в память из регистров или наоборот, доставать из памяти в регистры.

АЛУ

АЛУ выполняет арифметические и логические операции над числами, которые расположены в регистрах. Для сложения и вычитания чисел существует следующая схема:

Эта схема называется full-adder. Взглянув на таблицу истинности можно заметить, что эта схема складывает три бита. Зачем три? Для того чтобы можно было подключить несколько таких элементов последовательно и складывать уже не два бита, а сколько нам нужно. Если мы подключим выход C_out одного full-adder'a ко входу C_in другого full-adder'a, то мы получим уже 2-разрядный сумматор. Если соединить 8 таких full-adder'ов, то мы получим 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), который активируется, если результат операции равен нулю.

Регистры

Регистры служат для хранения информации, обрабатываемой АЛУ. По факту регистры – это просто память внутри процессора. Память в ЭВМ реализуется с помощью триггеров. Эти устройства позволяют хранить 1 бит информации. Существует много различных триггеров, но мы будем использовать 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 (Random Access Memory – память произвольного доступа) имеется 64 ячейки памяти по 8-бит, один 8-битный вход, для записи данных (IN), 6-битная шина адреса (AD), переключатель для чтения данных (RE), вход для записи данных (WR) и один 8-битный выход (O1). Если на вход RE подается сигнал, память выдает значение ячейки по адресу AD на шину.

ROM-память похожа на RAM-память за исключением того, что в неё нельзя записывать данные, их можно только читать. ROM-память будет напрямую подключена к счётчику команд, так как она больше нигде не используется.

В блоке ROM (Read-only Memory – память только для чтения) также имеется 64 ячейки памяти по 8 бит и одна входная адресная шина, разрядностью 6 бит (AD). Эта память просто выдает команды, расположенные по соответствующему адресу. Так как размер машинного слова 16 бит, здесь у нас два выхода по 8 бит объеденины в один (O1).

Программирование ЭВМ происходит путём выставления редстоун блоков в определённые позиции в ячейках ROM-памяти.

Счётчик команд

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

У нас счётчик напрямую подключен к ROM-памяти, для того, чтобы ЭВМ сразу получала новую команду и выполняла её. Часы в счётчике являются синхронизирующим механизмом, их период или частота рассчитываются на основе быстродействия всей системы. В моём случае мне удалось выжать из моей ЭВМ невероятные 0,2 герца (1 команда в 5 секунд).

У счётчика присутствует вход HLT, который при подаче на него сигнала останавливает работу всей ЭВМ, а также вход адресной шины (AD), для выполнения ветвления. Во время ветвления счётчик команд записывает в свой регистр значение из входа AD. Ветвление происходит, если на вход JMP подан сигнал.

Ветвление может быть как условным, так и безусловным. Условное ветвление выполняется, если флаг ZR из АЛУ равен единице и выставлен флаг условного ветвления. Безусловное ветвление выполняется если выставлен флаг обычного ветвления. Флаги ветвления выставляет декодер команд.

Декодер команд

Декодер команд одна из самых главных частей ЭВМ, так как он преобразовывает двоичные коды управляющие сигналы для ЭВМ.

Если вы заметили, то мы предусмотрели в предыдущих компонентах различные управляющие входы. Это входы записи и чтения для регистров, записи и чтения для памяти, вход режима АЛУ, флаги ветвление и другие. Именно с этими входами и работает декодер команд.

Декодер берет машинную инструкцию и преобразует её в управляющие сигналы для других элементов ЭВМ. Если вы помните, мы используем 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, при помощи которой можно перенести инструкции из текстового файла в мир игры.

Мой компилятор преобразовывает инструкции ассемблера в двоичные коды. После компиляции в двоичный код, идет преобразование двоичных чисел в блоки редстоуна, которые представляют собой машинные команды для ЭВМ. Рассмотрим сам компилятор.

Сначала мы объявляем список всех доступных инструкций:

operations = {
    'NOP': 0b0000,
    'HLT': 0b1111,
    'ADD': 0b0001,
    'SUB': 0b0010,
    'STR': 0b0011,
    'LOD': 0b0100,
    'LDI': 0b0101,
    'JMP': 0b0110,
    'JIZ': 0b0111,
}

Я разделил все операции на группы. Для каждой группы существует свой формат входных данных, будь то регистры или ячейки памяти:

alu_operations = [
    operations['ADD'],
    operations['SUB']
]

immediate_operations = [
    operations['LDI']
]

memory_operations = [
    operations['LOD'],
    operations['STR']
]

jump_operations = [
    operations['JMP'],
    operations['JIZ']
]

alu_map = ['r', 'r', 'r']
immediate_map = ['r', 'v']
memory_map = ['r', 'v']
jump_map = ['v']

Буква r обозначает регистр, а v – числовое значение. Например, операндами для инструкций АЛУ должны быть три регистра, для инструкций ветвления – только одно числовое значение и так далее.

Обработка инструкций происходит в функции compile_line. На вход данная функция получает одну операцию (к примеру ADD r1, r2, r1) и преобразует её в двоичный код:

def compile_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] << 13
      
      elif (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] << 8
      
      elif (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] << 10
      
      elif (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] << 11
      
      return ('{:016b}'.format(result))

В зависимости от типа операции проводятся дополнительные проверки, например, если операция связана с памятью, то адрес ячейки памяти не может превышать 64, так как у нас всего 64 ячейки памяти. Функция check_operation выполняет проверку количества операндов и их соответствие типу инструкции. Эта функция возвращает массив с преобразованными в числа операндами. На выходе у нас получается двоичное число, которое затем преобразовывается в блоки редстоуна в игре.

Исходный код компилятора находится по ссылке на GitHub. Там же находятся и примеры кода, который можно написать для ЭВМ.

Тест

Я написал простую программу, для вычисления 14-го числа Фибоначчи (233):

ldi r3, 6
ldi r4, 1
ldi r1, 1
ldi r2, 1
loop:
add r1, r1, r2
add r2, r2, r1
sub r3, r4, r3
jiz end
jmp loop
end:
str r1, 0
hlt

С учетом скорости ЭВМ (умопомрачительные 0,2 герца) эта программа будет выполняться несколько минут. Так на деле и оказалось, я ждал около 5 минут, пока ЭВМ закончит вычисления. После ожидания я увидел заветное число 11101001 в нулевой ячейке памяти.

Заключение

В целом я доволен результатом. Эту ЭВМ еще можно дополнять устройствами ввода-вывода, расширять память, добавить регистр флагов и так далее. Благо прототип позволяет развивать эту идею и дальше.

Надеюсь вы узнали что-то новое про внутреннее устройство компьютеров и ЭВМ в целом. Для меня было очень интересно строить ЭВМ в игре и писать компилятор для собственного ассемблера. Я оставил ссылку на GitHub репозиторий, для того, чтобы вы могли сами опробовать данную ЭВМ. Вам понадобиться версия Minecraft 1.20.1 и мод Schematica. На GitHub указаны инструкции для компиляции кода и запуска собственных программ. Также я оставил на GitHub архив с миром, в котором строил ЭВМ. В этом мире есть все компоненты по отдельности, если вам интересно изучить, как они работают.

GitHub проекта: https://github.com/Reedus0/MinecraftComputer

Теги:

Хабы: