CPU·IV Машина Глава 32 из 65
Ты — процессор
У «Искры-8» есть АЛУ, регистры и память, но нет того, кто ими распоряжается. Эту роль сначала сыграете вы: возьмёте байт по адресу из счётчика команд, расшифруете и исполните — такт за тактом. Потом напишете программы, которые машина исполнит сама, и получите ответ на четвёртый большой вопрос курса.
Машина
- 28 Биты
- 29 Вентили
- 30 Сумматор и АЛУ
- 31 Память
- 32 Процессор вы здесь
- 33 Ниже Python
- 34 Кэши
- 35 Конвейер
Опирается на: 31 · Память и такт
Что вы унесёте из главы
- исполнять машинный код вручную — выборка, декодирование, исполнение — и читать программу в шестнадцатеричных байтах
- писать для «Искры-8» программы на ассемблере: с метками, циклами, вводом и рисованием на экране
- объяснять, как биты, вентили, сумматор, память и такт складываются в машину, которая исполняет любую программу
4Как из выключателей получается компьютер?
Глава 31 оставила «Искру-8» в странном виде. АЛУ умеет складывать и вычитать, регистры держат числа, память хранит 256 байт, тактовый сигнал раз за разом даёт команду «шаг». Но кто решает, что делать на этом шаге? В главе 31 это решали мы сами, руками: подавали числа на входы и нажимали кнопки. Машина, которой каждый шаг диктует человек, остаётся калькулятором.
Ответ спрятан в самой памяти. Пусть в ячейках лежат не только числа, но и приказы: «сложи R2 и R0», «уменьши R0 на единицу», «если не ноль, вернись назад». Пусть счётчик из главы 31 показывает, какой приказ следующий. Тогда остаётся маленькая схема, которая на каждом такте читает приказ, понимает его и переключает стрелочники. Прежде чем строить её, сыграем её роль. В этой главе процессор — вы.
Действующие лица
На сцене пятеро, и троих вы уже знаете. Память — 256 байт из главы 31, в начале которых лежит программа. АЛУ из главы 30 с тремя флагами: Z — результат ноль, C — был перенос или заём, N — старший бит результата равен 1. Рабочие регистры R0–R3. И два новых персонажа, оба тоже регистры.
Первый — счётчик команд, PC (program counter). В нём адрес команды, которую пора выполнять. Это счётчик из главы 31: после каждой команды он прибавляет к себе её длину и показывает на следующую. Второй — регистр команды: в него кладут только что прочитанный байт, чтобы разглядеть его. А разглядывает его блок управления — ваша роль.
Правила игры одни и те же для любой команды. Ход состоит из трёх действий.
- Выборка. Взять из памяти байт по адресу из PC и прибавить к PC единицу.
- Декодирование. Понять, что это за команда. Если ей нужен второй байт — число или адрес, — взять и его, снова прибавив к PC единицу.
- Исполнение. Сделать то, что велит команда: положить число в регистр, сложить, записать в память или поменять PC.
Потом всё сначала, со следующего адреса. Этот круг называют циклом «выборка — декодирование — исполнение», а устройство, которое ходит по нему, — процессором. У «Искры-8» каждая команда, от выборки до исполнения, занимает один такт. Процессоры в наших компьютерах дробят команду на несколько стадий и ведут сразу несколько команд, каждую на своей стадии; об этом конвейере — глава 35.
Первая смена
В главе 31 в начале памяти «Искры-8» лежали одиннадцать байтов, и мы обещали объяснить, что это такое. Вот почти те же байты, только одно число мы уменьшили, чтобы вам не пришлось долго ходить по кругу:
10 03 18 00 58 A3 C8 04 38 FE 00
Это программа. Что она делает, вы узнаете, исполнив её. В виджете память и процессор, а наверху написано, какого действия от вас ждут. Шпаргалка по командам открывается кнопкой «Коды». Ошибка не страшна: виджет покажет, где она, и даст попробовать ещё раз.
Программа сложила $3 + 2 + 1$ и напечатала 6. Чтобы это сделать, вы прошли тринадцать ходов: две команды подготовки, три круга по три команды, вывод и остановка. Каждое ваше решение умеет принимать какая-нибудь схема из прошлых глав.
- Нажать на ячейку по адресу из PC — это подать выход регистра PC на линии адреса ОЗУ и прочитать байт деревом стрелочников из главы 31. Прибавить к PC единицу — это счётчик оттуда же.
- Понять, что за команда, помогает дешифратор из главы 31: старшие четыре бита байта — код операции, и по нему загорается одна из шестнадцати линий.
- Выбрать, какой регистр складывать, — это стрелочник, которым управляют биты
aaиbbиз того же байта. Выбрать, что делает АЛУ, — стрелочник на его выходе из главы 30. - Прыгать ли, решает «и» перевёрнутого флага Z с линией дешифратора «JNZ». Сам прыжок — запись нового значения в PC, то есть регистр с входом LOAD.
Блок управления, который сначала берёт байт, потом второй байт, потом исполняет, — это автомат из главы 31 с несколькими состояниями. Новых деталей не понадобилось, новой была только мысль: приказы лежат в той же памяти, что и числа.
Программа в той же памяти
Первой такую программу исполнила не EDVAC, а маленькая манчестерская машина Baby: 21 июня 1948 года. Меньше чем через год заработал кембриджский EDSAC, с которым мы встречались в главе 5. С тех пор так устроены почти все компьютеры, и «Искра-8» тоже. Такое устройство называют архитектурой с хранимой программой.
Новую программу теперь загружают в память так же, как числа, и задачу меняют за секунду — у ENIAC на это уходили дни. А ещё программу можно читать как данные. Вот программа, которая проходит по памяти от адреса 0 до своего конца и печатает всё, что там лежит, — то есть саму себя.
Это машинный родственник куайна из главы 7, только жульнический: своего текста программа не хранит и читает собственные байты прямо из памяти. На машине с хранимой программой это можно. А раз программы — данные, одна программа может писать другую. Так работают ассемблер, о котором чуть ниже, и компилятор, который вы напишете в главе 52. У этой силы есть изнанка: если злоумышленник сумеет подложить свои байты туда, куда потом прыгнет процессор, машина послушно исполнит их как команды. Как это делают и как от этого защищаются, расскажет глава 61.
Машинный код
Команды, которые процессор понимает напрямую, и их числовую запись называют машинным кодом, а полный их список — системой команд. У «Искры-8» 26 команд, и каждая начинается с байта одного и того же вида: оооо aa bb. Старшие четыре бита — код операции, следующие два — номер первого регистра, младшие два — номер второго или уточнение, какая именно это команда в семействе. Если команде нужно число или адрес, оно лежит во втором байте.
| код | команды | что делают |
|---|---|---|
0 | HLT, NOP, RET | остановка; ничего; возврат из подпрограммы — по полю bb |
1 | LDI ra, n | положить число из второго байта в регистр |
2, 3 | LD ra, [a], ST ra, [a] | из памяти в регистр и из регистра в память |
4 | MOV ra, rb | скопировать регистр |
5, 6 | ADD, SUB | $ra \leftarrow ra \pm rb$ по модулю 256 |
7, 8, 9 | AND, OR, XOR | побитовые операции |
A | SHL, SHR, INC, DEC | сдвиги и $\pm 1$ — по полю bb |
B | CMP ra, rb | флаги от $ra - rb$, сам регистр не меняется |
C | JMP, JZ, JNZ, JC, CALL | переходы по адресу из второго байта |
D, E | LDR ra, [rb], STR ra, [rb] | память по адресу, который лежит в регистре |
F | PUSH, POP | стек |
Расшифруем байт 58 из программы, которую вы исполняли. $58_{16} = 0101\,10\,00_2$. Код 5 — сложение. Поле aa равно $10_2 = 2$, то есть R2, поле bb равно 0, то есть R0. Получается ADD R2, R0: $R2 \leftarrow R2 + R0$. Байт C8 — это $1100\,10\,00_2$: код C — переход, поле aa = 10 уточняет, что это JNZ, «прыгнуть, если не ноль», а куда — сказано во втором байте, 04.
Каждая команда «Искры-8» записывается в 4 бита кода, по 2 бита на регистры и, может быть, ещё байт. Из этого и растут ограничения машины: регистров четыре, потому что на номер отведено два бита; кодов операций шестнадцать, потому что их номер — четыре бита. Поэтому часть команд и делит один код, различаясь полем bb. У промышленных процессоров те же компромиссы, только битов больше.
Попробуйте пример «слово HELLO». Буквы — тоже байты, и процессор, если направить его туда, без колебаний попробует исполнить их как команды. Байт 48, буква H, окажется командой MOV R2, R0. Где кончается программа и начинаются данные, байты сами не знают: это знает только тот, кто их положил. Ещё забавнее сдвиг на один байт. Команды «Искры-8» бывают длиной в байт и в два, и если начать читать не с того места, второй байт одной команды примут за первый байт другой, и вся программа превратится в иную.
Ассемблер
Писать программы байтами — пытка. Надо помнить таблицу кодов, складывать биты полей и, хуже всего, считать адреса: команда JNZ в нашей программе прыгает на адрес 04, и если вставить перед циклом ещё одну команду, адрес сдвинется, и прыжок придётся переписать. Поэтому программы пишут словами, мнемониками, а адреса заменяют метками — именами строк. Перевод из такой записи в байты делает программа-ассемблер. Сам язык мнемоник тоже часто называют ассемблером.
Ассемблер выдал знакомые одиннадцать байтов — программу, которую вы исполняли вручную. У метки loop адрес 4: перед ней две команды по два байта. Ассемблер узнаёт это, считая длины команд. Труднее с прыжком вперёд: JMP done в начале программы ссылается на метку, до которой ассемблер ещё не дочитал. Поэтому он читает текст дважды. В первый проход только считает длины команд и записывает адреса всех меток. Во второй — переводит команды в байты, уже зная каждый адрес. Такой двухпроходный ассемблер вы напишете в задаче «Свой ассемблер».
Ассемблер «Искры-8» понимает ещё несколько слов, которые не становятся командами. .byte 1, 2, 3 кладёт в память байты как есть, .text "HI" — коды букв строки, .equ N, 10 даёт числу имя, .org 0x80 велит продолжать с другого адреса. Комментарий начинается с точки с запятой. У бортового компьютера «Аполлона» был свой ассемблер, YUL, написанный в той же лаборатории MIT. Он выдавал перфоленту, и по ней станок из главы 31 подводил к игле нужное колечко. Программа на мнемониках превращалась в байты, а байты — в провода.
«Искра-8» целиком
Теперь машина в сборе, и роль процессора можно вернуть ей. Ниже «Искра-8» со всеми частями: текст программы, регистры, флаги, экран, вывод и вся память. Выберите пример или напишите свою программу, нажмите «Собрать», потом «Шаг» или «Пуск». Во время работы вместо текста виден листинг: адреса, байты и строка, которая сейчас исполняется. Ползунок меняет скорость, от одной команды в секунду до тысяч.
0xF0–0xF7, вывод чисел через 0xFE и символов через 0xFF. Числа для ввода через 0xFE пишутся в поле «ввод» через пробел.Те же программы запускаются и в Python: модуль cs.iskra в песочнице — та же машина бит в бит. Им же проверяются ваши решения задач.
Развилки и циклы из прыжков
В системе команд «Искры-8» нет ни if, ни while. Есть флаги и условные переходы, и этого хватает. Условие из главы 3 — это сравнение и прыжок через кусок кода. CMP R0, R1 вычитает R1 из R0, никуда не записывая разность, и только выставляет флаги. Если числа равны, разность — ноль, и поднят флаг Z. Если R0 меньше R1, вычитание заняло единицу из несуществующего девятого разряда, и поднят флаг C. Вот как переводится развилка:
Здесь a, b и x живут в регистрах R0, R1 и R2. Цикл while из главы 4 — это прыжок назад: тело, проверка, прыжок на начало, пока условие верно. Так устроен цикл в программе, которую вы исполняли: DEC R0 уменьшает счётчик и заодно выставляет Z, а JNZ loop возвращает на начало, пока счётчик не дошёл до нуля. В машинном коде в такие прыжки превращаются все циклы, функции и рекурсия.
Повторим её на «Искре-8». Наши регистры восьмибитные, поэтому возьмём число поменьше, 221, и тот же метод: кандидаты 220, 219, …, деление — вычитанием до нуля или до заёма.
$221 = 13 \cdot 17$, и машина нашла 17 за 3177 команд. Ноль и заём после SUB вместе не бывают: если разность ровно 0, заёма нет, так что две проверки можно поставить и в другом порядке. Поменяйте N на простое число, например 251, — и программа переберёт всех кандидатов до единицы.
Экран и вывод — тоже память
У «Искры-8» нет команд «нарисовать» и «напечатать». Зато несколько адресов в конце памяти особые. Ячейки 0xF0–0xF7 выведены на экран: каждый байт — строка из восьми пикселей, старший бит слева. Запись в 0xFE печатает число, а чтение оттуда берёт число из ввода. Запись в 0xFF печатает символ с этим кодом. Такой приём называют вводом-выводом через память. Процессору не нужно знать про устройства: он пишет по адресу, а откликается на этот адрес не ячейка, а экран или принтер.
Здесь работают команды LDR и STR: адрес они берут из регистра, и его можно увеличивать в цикле. Это указатель — номер ячейки, который сам хранится в ячейке. В Python указателей не видно, но список из главы 14 и a[i] внутри устроены именно так. Видеопамять домашних компьютеров когда-то работала так же, как экран «Искры-8»: у ZX Spectrum картинка на экране была обычной областью памяти, и игры рисовали, записывая в неё байты.
Подпрограммы: прыжок Уилера в железе
В главе 5 Дэвид Уилер учил подпрограммы EDSAC возвращаться: перед прыжком вызывающая программа оставляла свой адрес, и подпрограмма прыгала обратно по нему. У «Искры-8» для этого есть пара команд. CALL square кладёт адрес следующей команды на стек и прыгает на метку square. RET снимает адрес со стека и прыгает по нему. Стек живёт в верхней части памяти, прямо под экраном, и растёт вниз: на его вершину показывает регистр SP, в начале равный 0xF0. Каждый вызов кладёт свой адрес возврата поверх предыдущего, поэтому подпрограмма может вызвать другую, а та — третью, и все вернутся по своим местам. Получился стек вызовов из главы 5, только в байтах. Пример «Квадраты» в машине выше вызывает подпрограмму пять раз.
Процессор на одном кристалле
«Искра-8» по устройству ближе к 4004, чем к процессору вашего телефона: одна команда за раз, несколько регистров, крошечная память. Современный процессор содержит десятки миллиардов транзисторов, сотни, а то и тысячи команд, конвейеры и кэши. Но цикл у них тот же: взять команду по адресу из счётчика, понять её, выполнить.
Хватит ли этого на всё
У «Искры-8» 26 команд. Можно ли написать на ней любую программу — сортировку из главы 20, Дейкстру из главы 24, интерпретатор Python? Есть основания думать, что да, если хватит памяти. Список — это ряд ячеек и указатель в регистре, LDR и STR ходят по нему. Функция — CALL и RET, рекурсия — тот же стек. Умножение, деление, дроби — программы из сложений, вычитаний и сдвигов, как деление на манчестерской Baby. Машину ограничивает объём памяти, а бедность команд ей не мешает: у Baby их было семь, и известно, что хватает даже одной, удачно выбранной: например, «вычти и прыгни, если результат не положительный».
Что значит «любую программу» точно и есть ли задачи, которые не решит никакая машина, сколько ей ни дай памяти, — разговор для главы 55, где Алан Тьюринг построит машину ещё проще нашей. А пока можно подвести итог четырёх глав.
Выключатель — реле или транзистор — либо пропускает ток, либо нет. Это бит, и в главе 28 мы видели, что числа, буквы и картинки записываются битами. Выключатели, соединённые последовательно и параллельно, вычисляют логику, а из одного вентиля NAND собирается любая схема без памяти (глава 29). Из таких схем получаются сумматор и АЛУ, которые складывают, вычитают и сравнивают байты и поднимают флаги (глава 30). Петля из двух вентилей хранит бит, тактовый сигнал заставляет тысячи таких петель переключаться разом, и появляются регистры, счётчики и память с доступом по адресу (глава 31). Последний шаг — положить в память команды, такие же числа, как данные, и поручить счётчику показывать на следующую. Маленький автомат на каждом такте берёт команду, дешифратор раздаёт приказы стрелочникам, АЛУ считает, переходы меняют счётчик — и машина сама идёт по программе. Внутри нет ничего, кроме выключателей и проводов; всё дело в том, как они соединены. А как программа на Python сама превращается в такие команды, мы увидим в главах 33 и 52.
Задачи
Три программы для «Искры-8» и одна программа о программах. В первых трёх решение — строка PROGRAM с текстом на ассемблере; проверка соберёт её модулем cs.iskra, запустит с разными вводами и посмотрит на вывод или на экран. Отлаживать удобно в машине из раздела «Искра-8» целиком: скопируйте туда текст программы.
Программа читает числа из 0xFE, пока не прочитает 0, и печатает их сумму по модулю 256 — одно число, как сложила бы сама машина. Если первое же число 0, сумма равна 0. Числа после нуля читать не нужно.
Возьмите копилку в регистре: LDI R2, 0. Потом цикл: прочитать число LD R0, [0xFE], проверить на ноль, прибавить, прыгнуть назад.
LD сам выставляет флаги Z и N по прочитанному числу, так что JZ done можно ставить сразу после чтения. Если не уверены, добавьте MOV R0, R0: копирование регистра в себя ничего не меняет, кроме флагов.
Это цикл while с проверкой в начале. Переполнение не нужно обрабатывать специально: восьмибитный регистр сам считает по модулю 256, поэтому $200 + 100$ даёт 44 — то же, что АЛУ из главы 30.
Команды умножения у «Искры-8» нет. Программа читает из 0xFE два числа $a$ и $b$ от 0 до 255 и печатает $a \cdot b$ по модулю 256. Подвох в скорости: на любых двух числах машина должна уложиться в 150 тактов. Если прибавлять $a$ к сумме $b$ раз, то при $b = 255$ понадобится больше 750 тактов.
Умножение сдвигами из главы 30: $a \cdot b$ — это сумма $a \cdot 2^k$ по тем битам $k$, где в $b$ стоит единица. Бит за битом: если младший бит $b$ равен 1, прибавить $a$ к сумме; потом $a$ удвоить, а $b$ сдвинуть вправо. Кругов не больше восьми.
SHR R1 отправляет младший бит во флаг C, а JC прыгает, если он был единицей. Удвоение — SHL R0. Цикл кончается, когда в $b$ не осталось единиц: проверьте его на ноль через MOV R1, R1 и JZ.
На каждом круге семь команд, кругов не больше восьми — на $255 \cdot 255$ уходит около шестидесяти тактов вместо семисот с лишним. Это та же разница, что между линейным и логарифмическим временем из главы 13: число кругов равно числу битов в $b$, а не самому $b$. Так умножают программы на процессорах без команды умножения, а таких было много: её не было, например, у популярных в 1980-х процессоров 6502 и Z80.
Программа читает из 0xFE восемь чисел от 0 до 8 и рисует на экране горизонтальную гистограмму: в строке $i$ горят первые слева $v_i$ пикселей, остальные погашены. Например, ввод 3, 0, 8, … даёт в первой строке ###....., во второй — пустую строку, в третьей — все восемь пикселей.
Строку из $v$ пикселей слева удобно строить в цикле: начать с байта 0 и $v$ раз сдвинуть его вправо и зажечь левый пиксель — OR с 0x80. После трёх кругов получится 11100000.
Адрес строки экрана держите в регистре и пишите туда командой STR R1, [R3]. После каждой строки — INC R3, и цикл по строкам кончается, когда адрес дошёл до 0xF8: CMP и JNZ.
Два вложенных цикла: внешний по строкам, внутренний по пикселям. Есть и решение без внутреннего цикла: положить в память таблицу из девяти байтов .byte 0x00, 0x80, 0xC0, …, 0xFF и брать нужный командой LDR по адресу «начало таблицы + $v$». Обмен памяти на время — тот же, что у мемоизации из главы 22.
Напишите на Python двухпроходный ассемблер для части команд «Искры-8»: HLT, NOP, LDI, LD, ST, MOV, ADD, SUB, CMP, INC, DEC, JMP, JZ, JNZ, JC. Функция assemble(src) получает текст программы и возвращает список байтов от адреса 0 до конца программы. В тексте бывают метки (loop:, в том числе на отдельной строке), комментарии после ;, пустые строки, числа в десятичной записи и с 0x, адреса в квадратных скобках. Мнемоники и регистры пишутся в любом регистре букв. Метка может стоять и там, где ждут число: LDI R1, table. Неизвестная метка — исключение. Пользоваться модулем cs.iskra нельзя, но таблица кодов уже дана.
Сначала научитесь разбирать одну строку: отрезать комментарий по ;, отделить метку по :, взять первое слово как мнемонику, а остаток разрезать по запятым. Пусть функция возвращает тройку (метка, мнемоника, операнды), где пустые части — None.
Первый проход: идите по строкам со счётчиком адреса, запоминайте адрес каждой метки и прибавляйте длину команды — 2, если в её виде есть n, иначе 1. Второй проход: собирайте байт из кода и полей и, если нужно, второй байт — число, 0x-число или адрес метки из словаря первого прохода.
Первый проход нужен из-за прыжков вперёд: когда второй проход дойдёт до JMP done, адрес done уже известен. Ассемблер курса устроен так же, только понимает все 26 команд, директивы и выдаёт сообщения об ошибках с номером строки. В главе 52 этот ассемблер станет последним звеном вашего компилятора: тот будет выдавать текст на ассемблере «Искры-8», а дальше — байты.
Куда дальше
«Искра-8» ожила. Счётчик показывает на команду, блок управления её разбирает, АЛУ считает, переходы ведут программу по кругу и в обход. Вы написали для неё сумму, умножение и рисунок и, наверное, заметили, сколько сил это стоило. Умножение двух чисел — дюжина строк, каждую переменную приходится держать в одном из четырёх регистров и помнить, в каком. Гистограмма, которую на Python пишут в две строки, на ассемблере — шестнадцать.
А ведь всё, что вы писали в этом курсе на Python, в итоге исполняет такой же цикл «выборка — декодирование — исполнение», только на процессоре побольше. Значит, между строкой total += x и командами процессора кто-то проделывает огромную работу перевода. Как строки Python превращаются в команды? В главе 33 мы просветим одну функцию слой за слоем: Python, байт-код, C, ассемблер x86-64 — и снова «Искра-8».