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

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

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

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