Машина, которая считает без остановки
Разминка окончена. Переходим к настоящему PA.
Если PA1 — лишь разминка-повтор программирования, то PA2 — начало основного фильма. В PA2 вы почувствуете, как новый код и инженерные детали накатывают приливом: нужно постоянно читать хендауты, RTFM, RTFSC и разбирать детали. Сначала эффективность будет низкой, но когда детали освоите, дальше пойдёт повторяющаяся инженерная работа.
Кроме того, если фраза из PA1 «не зацикливайтесь на коде, не относящемся к текущему прогрессу» была, чтобы защитить ваш юный разум, в PA2 нужно храбро исследовать: хендауты уже не указывают каждую строку кода, которую стоит прочитать, как в PA1. На самом деле весь код в PA стоит прочитать, и к концу PA2 нужно уметь понимать каждую деталь NEMU. Чем глубже вы разберётесь в деталях кода, тем легче будет даже исправлять баги. Наоборот, если останетесь при настрое «лишь бы тесты прошли», «это не в баллах, какое мне дело», скоро обнаружите, что даже не знаете, где и как находить баги.
Так что больше не ленитесь.
В PA1 мы уже видели, как работает простейший компьютер TRM:
while (1) {
извлечь инструкцию из позиции памяти, указанной PC;
Выполнить инструкцию;
обновить PC;
}
Дальше поговорим об этом процессе, то есть о том, как CPU на самом деле выполняет одну инструкцию. Для большинства инструкций выполнение можно абстрагировать в цикл выборка–декодирование–выполнение. Чтобы описание было яснее, возьмём некоторые понятия из цикла инструкции и на них покажем процесс выполнения.
Выборка инструкции, IF
Чтобы выполнить инструкцию, сначала её нужно получить. Где же инструкция? Помните ядро архитектуры фон Неймана? Это «хранение программ, программное управление». Раньше, слыша эти слова, вы, возможно, не улавливали смысла, сейчас время практики. Они говорят: инструкции лежат в памяти, а PC указывает позицию текущей инструкции. На самом деле PC — это указатель! В компьютерном мире понятие указателя повсюду. Если с указателями ещё не очень знакомы, скорее повторите этот обязательный курс. Выборка инструкции естественно делает следующее: читает инструкцию, на которую указывает PC, из памяти в CPU.
Декодирование инструкции, ID
На этапе выборки компьютер получает инструкцию, которую нужно выполнить. Давайте и мы взглянем на инструкцию: открываем глаза — и это битовая строка из 0 и 1!
10111001 00110100 00010010 00000000 00000000
Что это, чёрт возьми... Но если подумать, компьютер — просто огромная цифровая схема, и понимать он может только 0 и 1. Но как такой компьютер разбирает эту путаную битовую строку?
Сначала вспомним, что делают инструкции. Мы знаем: CPU обрабатывает данные, а инструкции указывают CPU, какие данные как обрабатывать. То есть если дать CPU извлечь из таинственной битовой строки выше объект обработки и саму операцию, CPU будет знать, что мы хотим. Соответственно CPU нужно из инструкции прочитать две части информации: «opcode» (операцию) и «operand» (объект).
Чтобы компьютер понял смысл инструкции, первопроходцы придумали способ — тот самый, что вы учили на курсе цифровых схем: таблица поиска (lookup table)! Получив инструкцию, CPU по таблице узнаёт операнды и opcode этой инструкции. Этот процесс называется декодированием.
Разумеется, логика декодирования не сводится к одной таблице поиска: ещё нужно мультиплексором выбирать разные операнды для разных инструкций. Вспомните: у компьютера уже есть память и регистры, в них можно хранить операнды, а в инструкции — непосредственные числа (immediate). Возможно, есть и вторичное декодирование... Но как бы ни было сложно, нам достаточно знать: в итоге это всё равно цифровые схемы; вся нужная информация уже в инструкции, ничего таинственного нет.
Выполнение, EX
После декодирования CPU знает, что именно должна сделать текущая инструкция; этап выполнения — это уже настоящая работа инструкции. Сейчас у TRM только один исполнительный блок — сумматор: при необходимости достаточно подать на сумматор два исходных операнда и получить результат. Затем результат записывают обратно в операнд назначения — это может быть регистр или память.
Обновить PC
Выполнив инструкцию, CPU должен выполнить следующую. Перед этим CPU обновляет значение PC: прибавляет длину только что выполненной инструкции — и PC указывает на позицию следующей инструкции.
Так компьютер снова и снова повторяет эти четыре шага, выполняет инструкции — до бесконечности.
YEMU: простой эмулятор CPU
Возьмём как пример простой компьютер из подраздела 1.1.3 учебника ICS и покажем, как на C реализовать выполнение одной инструкции. У этого компьютера 4 восьмибитных регистра, 4-битный PC и 16 байт памяти. Он поддерживает форматы инструкций R-типа и M-типа, 4 инструкции. Руководство по инструкциям такое:
4 2 0
| | | +----+--+--+
mov rt,rs | R[rt] <- R[rs] | R-type | |0000|rt|rs|
| | | +----+--+--+
| | | +----+--+--+
add rt,rs | R[rt] <- R[rs] + R[rt] | R-type | |0001|rt|rs|
| | | +----+--+--+
| | | +----+--+--+
load addr | R[0] <- M[addr] | M-type | |1110| addr|
| | | +----+--+--+
| | | +----+--+--+
store addr | M[addr] <- R[0] | M-type | |1111| addr|
| | | +----+--+--+
По этому руководству на C можно написать эмулятор этого простого компьютера — YEMU:
#include <stdint.h>
#include <stdio.h>
#define NREG 4
#define NMEM 16
// определить формат инструкции
typedef union {
struct { uint8_t rs : 2, rt : 2, op : 4; } rtype;
struct { uint8_t addr : 4 , op : 4; } mtype;
uint8_t inst;
} inst_t;
#define DECODE_R(inst) uint8_t rt = (inst).rtype.rt, rs = (inst).rtype.rs
#define DECODE_M(inst) uint8_t addr = (inst).mtype.addr
uint8_t pc = 0; // PC, в C нет 4-битного типа, представляем 8-битным
uint8_t R[NREG] = {}; // регистры
uint8_t M[NMEM] = { // память, в ней программа, считающая z = x + y
0b11100110, // load 6# | R[0] <- M[y]
0b00000100, // mov r1, r0 | R[1] <- R[0]
0b11100101, // load 5# | R[0] <- M[x]
0b00010001, // add r0, r1 | R[0] <- R[0] + R[1]
0b11110111, // store 7# | M[z] <- R[0]
0b00010000, // x = 16
0b00100001, // y = 33
0b00000000, // z = 0
};
int halt = 0; // признак окончания
// выполнить одну инструкцию
void exec_once() {
inst_t this;
this.inst = M[pc]; // выборка инструкции
switch (this.rtype.op) {
// декод. opcode декод. операнда выполнение
case 0b0000: { DECODE_R(this); R[rt] = R[rs]; break; }
case 0b0001: { DECODE_R(this); R[rt] += R[rs]; break; }
case 0b1110: { DECODE_M(this); R[0] = M[addr]; break; }
case 0b1111: { DECODE_M(this); M[addr] = R[0]; break; }
default:
printf("Invalid instruction with opcode = %x, halting...\n", this.rtype.op);
halt = 1;
break;
}
pc ++; // обновить PC
}
int main() {
while (1) {
exec_once();
if (halt) break;
}
printf("The result of 16 + 33 is %d\n", M[7]);
return 0;
}
Понять, как YEMU выполняет программы
YEMU можно считать упрощённой версией NEMU, принципы те же, поэтому нужно понять, как YEMU выполняет программы. Конкретно нужно
- Нарисовать конечный автомат программы сложения, выполняемой на YEMU
- Через RTFSC понять, как YEMU выполняет одну инструкцию
Подумайте: какая связь между этими двумя вещами?
Возможно, вы сомневаетесь: этот TRM умеет только складывать — что ещё он может? Для компьютера в дополнительном коде, если умеешь складывать, умеешь и вычитать. Если добавить условный переход jnz r, addr: когда регистр r не 0, PC переходит на addr — TRM станет совсем другим. Например, комбинацией jnz и dec можно сделать цикл, циклом inc — сложение произвольных чисел, циклом сложения — умножение, вызов функции можно считать особым переходом, рекурсия по сути и есть вызов функции... Вот это да: этот хлипкий TRM прятал мощь, способную потрясти землю! Однако хотя TRM с несколькими инструкциями решает все вычислимые задачи, он невыносимо неэффективен. Поэтому Первопроходец решил добавить в TRM больше эффективных инструкций.