Машина считает

Глава 29 закончилась полным сумматором: деталь из девяти вентилей NAND складывает три бита — два разряда и перенос. Но регистры «Искры-8» восьмибитные, и её команда ADD R0, R1 должна складывать числа от 0 до 255, SUB — вычитать, CMP — сравнивать, а заодно сообщать, не вышел ли ноль и не случился ли перенос. Вычитателя у нас нет, умножителя тоже. Эта глава — завод, где из одного вида деталей собирают всё, что умеет считать процессор.

Завод устроен по-взрослому. Работа начинается с технического задания — спецификации «Искры-8». Цеха делают по узлу, а отдел технического контроля, прежде чем пустить узел в машину, сверяет его со спецификацией на всех входах, какие только бывают. В конце главы ОТК займётся расследованием настоящего брака — того, что прошёл все проверки Intel, разошёлся по компьютерам всего мира и обнаружился только в 1994 году.

Техническое задание

Узел, который считает, называется арифметико-логическим устройством, коротко АЛУ. Он получает два байта и код операции — номер того, что с ними сделать, — и выдаёт байт результата и несколько флагов: однобитных отметок о том, каким вышел результат. Вот выписка из спецификации «Искры-8» (полностью она понадобится в главе 32):

Флагов три. Z (zero) равен 1, если результат — ноль. N (negative) — копия старшего бита результата: если читать байт как число со знаком в дополнительном коде из главы 28, это знак. C (carry) — перенос из старшего разряда при сложении, заём при вычитании или бит, выпавший при сдвиге.

Для ОТК нужен эталон. Им будет сама «Искра-8»: в песочнице есть её эмулятор cs.iskra, и в главе 32 он же будет выполнять ваши программы. Чтобы узнать, что АЛУ обязано ответить на пару чисел, достаточно дать машине крошечную программу: положить числа в регистры, выполнить операцию, остановиться.

$200 + 100 = 300$, а байт вмещает только до 255: в регистре остаётся $300 - 256 = 44$, и поднимается флаг переноса. $5 - 7$ дало 254 — это $-2$ в дополнительном коде, поэтому N = 1, — и флаг заёма. Дальше эта функция лежит в модуле cs.alu (from cs.alu import iskra), и ОТК будет звать её, не переписывая.

Цех № 1. Восемь сумматоров в цепочку

Сложение столбиком из главы 29 подсказывает устройство. Поставим восемь полных сумматоров в ряд, по одному на разряд. Каждый получает свои биты $a_i$ и $b_i$ и перенос от соседа справа, отдаёт бит суммы $s_i$ и перенос соседу слева. Самый правый получает на вход переноса ноль, а перенос самого левого становится флагом C. Такую схему называют сумматором с последовательным переносом: перенос бежит по цепочке, как волна.

Шестьдесят пять тысяч пар — все возможные входы восьмибитного сумматора, так что перебор здесь полный: раз брака ноль, сумматор правильный. Запомните эту роскошь — у делителя Pentium её не будет.

Узкое место: перенос бежит

В коде цикл проходит разряды по очереди, и кажется, что в железе всё случается сразу. Но транзистору нужно время, чтобы переключиться, и выход вентиля устанавливается с задержкой — у современных вентилей это пикосекунды. В одиночку пикосекунды незаметны, но они складываются вдоль цепочки. Старший разряд суммы не может стать правильным, пока до него не добежит перенос, а перенос из разряда $i$ зависит от переноса из разряда $i - 1$. Прибавьте к числу 11111111 единицу: перенос родится в нулевом разряде и пробежит все восемь, по два вентиля на каждый.

Для восьми разрядов это 16 задержек, для 64-битного процессора — 128. Самая длинная цепочка в схеме определяет, как часто можно подавать ей новые числа, то есть тактовую частоту, о которой пойдёт речь в главе 31. Поэтому сумматоры в процессорах устроены хитрее.

Ускоренный перенос

Идея в том, чтобы предсказать перенос, не дожидаясь его. Посмотрим на разряд $i$ отдельно от остальных. Если $a_i = b_i = 1$, перенос из него будет при любом входящем — разряд рождает перенос: $g_i = a_i b_i$. Если ровно один из битов равен 1, разряд передаёт входящий перенос дальше: $p_i = a_i \oplus b_i$. Если оба нуля — гасит. Тогда

$$c_{i+1} = g_i + p_i c_i,$$

и эту формулу можно раскрыть: $c_2 = g_1 + p_1 g_0 + p_1 p_0 c_0$. Перенос во второй разряд есть, если его родил первый разряд, или его родил нулевой, а первый передал, или он пришёл снаружи, а оба передали. Все $g$ и $p$ считаются одновременно, за одну задержку, а раскрытая формула — это «или» нескольких «и», то есть два яруса вентилей, как в главе 29. Правда, для старших разрядов формулы растут. Выход — считать переносы деревом: сначала для пар соседних разрядов («пара рождает перенос» и «пара передаёт перенос»), потом для четвёрок, восьмёрок и так далее. Ярусов у такого дерева $\log_2 n$, и 64-битный перенос готов примерно через 14 задержек вместо 128. Схем ускоренного переноса придумано много, но все они платят вентилями за время: дерево больше цепочки.

Проверим, что дерево считает те же переносы, что цепочка. Обе функции ниже возвращают список переносов из каждого разряда. Вторая работает ярусами: на ярусе с шагом step каждый разряд склеивает свою пару $(g, p)$ с парой разряда на step правее, и за $\log_2 8 = 3$ яруса все переносы готовы.

Цех № 2. Вычитание без вычитателя

В задаче к главе 29 мы собирали полный вычитатель, и он оказался сумматором с одним «не». Но можно обойтись совсем без него. В главе 28 выяснилось, что в дополнительном коде $-b$ — это «переверни все биты и прибавь единицу». Значит,

$$a - b = a + \overline{b} + 1 \pmod{256}.$$

Переворот битов — восемь вентилей XOR: на один вход каждого идёт бит $b_i$, на другой — общий управляющий провод SUB. При $\mathrm{SUB} = 0$ XOR пропускает $b_i$ как есть, при $\mathrm{SUB} = 1$ переворачивает. А «прибавь единицу» не требует ничего: тот же провод SUB подаётся на вход переноса младшего сумматора, который при сложении получал ноль. Один сумматор, восемь XOR и провод — и АЛУ умеет вычитать.

Остаётся флаг C. Сумматор при вычитании выдаёт перенос 1, когда $a \ge b$: например, $7 - 5 = 7 + 250 + 1 = 258$, и девятый бит выпадает. «Искра-8» по спецификации хранит в C заём — единицу, когда $a < b$. Поэтому при вычитании перенос сумматора переворачивается ещё одним вентилем. Так делает, например, x86; у процессоров ARM соглашение обратное, и флаг после вычитания означает «заёма не было». Это частая ловушка для тех, кто пишет на ассемблере для разных машин.

Команда CMP — то же вычитание, только результат никуда не записывается, остаются флаги. После CMP R0, R1 флаг Z говорит, равны ли числа, а флаг C — меньше ли $R_0$, чем $R_1$. На этом в главе 32 будут построены все условия в программах «Искры-8»: «сравни и прыгни, если Z» — это if a == b машинного кода.

Цех № 3. Флаги

Флаги стоят дёшево. N — провод от старшего бита результата, без единого вентиля. C — провод от переноса старшего сумматора (при вычитании — через «не»). Z — один вентиль «или-не» на восемь входов: он выдаёт 1, только когда все биты результата нули. На практике такой широкий вентиль собирают деревом из маленьких, но смысл тот же.

У процессоров побольше есть и четвёртый флаг — переполнение, V (в x86 он называется OF). Перенос C говорит о переполнении для чисел без знака: $200 + 100$ не влезло в байт. Но тот же байт можно читать как число со знаком, и тогда беда другая. $100 + 100 = 200$, и для чисел без знака всё в порядке: C = 0. А со знаком 200 — это $-56$: сложили два положительных и получили отрицательное. Знаковое переполнение случается, когда у слагаемых одинаковый знак, а у результата — другой. Его легко поймать и на уровне вентилей: переполнение есть, когда перенос в старший разряд не совпадает с переносом из него.

Сложим 127 и 1 в восьмибитном АЛУ. Какие флаги поднимутся, если считать и знаковое переполнение V?

только C N и V Z и C никакие

$127 + 1 = 128 = 10000000_2$. Старший бит стал единицей — N = 1. Переноса из старшего разряда нет — C = 0, и для чисел без знака ответ верный. Но 127 — самое большое восьмибитное число со знаком, а 10000000 со знаком — это $-128$: два положительных дали отрицательное, V = 1. Перенос в старший разряд был, а из него — нет, они не совпали.

У «Искры-8» флага V нет: машина задумана маленькой, и трёх флагов ей хватает, чтобы сравнивать числа без знака. Знаковое сравнение на ней приходится собирать вручную, из флага N и знаков чисел. А флаг V вы напишете сами, в задаче «Четвёртый флаг».

Флаги в вашем коде

Приём «каждый бит — отдельный признак» живёт далеко за пределами процессора. Права на файл в Unix — девять битов: чтение, запись и исполнение для владельца, группы и остальных. Настройки регулярных выражений в Python — тоже биты: re.IGNORECASE | re.MULTILINE складывает флаги через «или», а проверка flags & re.MULTILINE через «и» спрашивает, поднят ли нужный. Это те же операции, что в АЛУ, только над целыми числами Python.

Сдвиг вправо и маска — стандартный способ вырезать из числа поле битов, а «или» — собрать число из полей. Так же байт команды «Искры-8» разбирается на код операции и номера регистров — это понадобится в главе 32.

Цех № 4. АЛУ: все считают, один выбирает

Узлы готовы: сумматор с вычитанием, восемь «и», восемь «или», восемь XOR, сдвигатели. Осталось собрать из них одно устройство, которое по коду операции делает то, что велено. В программе мы написали бы if op == 'ADD': … elif op == 'SUB': … и посчитали бы только одно. Схема так не умеет: ток течёт по всем проводам сразу. Поэтому в АЛУ все узлы считают всегда, на каждый такт, а на выходе стоит мультиплексор из главы 29, только широкий: по коду операции он пропускает в регистр один из результатов, а остальные пропадают. Это расточительно, но вентили дешёвые, а время дорогое: ждать, пока стрелочник решит, что считать, было бы дольше, чем посчитать всё.

На пульте ADD R0, R1 — это байт 0x51: старшие четыре бита 0101 — код операции 5, дальше по два бита на номера регистров. Эти четыре бита (а у сдвигов, INC и DEC с общим кодом A — ещё и поле bb) и идут на управляющие входы мультиплексора АЛУ. Машина код операции не «понимает»: он лишь открывает один из путей.

Цех № 5. Сдвиги и умножение

Самый дешёвый узел завода не содержит ни одного вентиля. Сдвиг влево — это провода, припаянные со смещением на один разряд: бит $a_i$ подаётся на выход $i + 1$, в младший разряд приходит ноль, а старший бит выпадает во флаг C. Как дописанный справа ноль умножает десятичное число на 10, так сдвиг влево умножает двоичное на 2. Сдвиг вправо делит нацело на 2, и во флаг выпадает младший бит — остаток. В Python это операторы << и >>.

Умножения в «Искре-8» нет, но оно собирается из сдвигов и сложений. Распишем множитель $b$ в двоичной записи: $b = \sum b_i 2^i$. Тогда $a \cdot b = \sum b_i \cdot (a \cdot 2^i)$: берём $a$, сдвинутое на $i$ разрядов, там, где у $b$ стоит единица, и складываем. Это то же египетское умножение удвоением, известное по папирусу Ринда, из «Царицы наук»: чтобы умножить 13 на 21, писец удваивал 21 и складывал нужные строки. Тысячи лет назад он считал в двоичной системе, не подозревая об этом.

Четыре шага вместо тринадцати сложений: столько, сколько битов у множителя. Для 64-битных чисел это 64 сложения, а не миллиарды миллиардов. В процессорах умножитель делают ещё быстрее — складывают все сдвинутые копии сразу, деревом сумматоров. Восьмибитный умножитель — это несколько десятков полных сумматоров, 64-битный — тысячи. «Искре-8» такая роскошь не положена: в главе 32 вы напишете умножение программой из ADD, SHL, SHR и условного перехода.

С делением всё труднее. Деление столбиком в двоичной системе — это сдвиги и вычитания: пробуем вычесть делитель, получилось — пишем в частное 1, нет — 0, сдвигаемся. Каждый шаг даёт один бит частного, и каждый требует полного вычитания со всеми задержками переноса. 64 бита частного — 64 медленных шага. Конструкторы процессоров десятилетиями искали, как делить быстрее, и один из самых удачных способов привёл к самому громкому браку в истории арифметики.

ОТК: дело о делении

В песочнице лежит модель делителя Pentium, и находку Коу можно повторить. Python считает правильно, модель — как процессор 1994 года.

Ошибка в пятой значащей цифре: относительная погрешность $6 \cdot 10^{-5}$, а двойная точность обещает $10^{-16}$. Найсли повезло меньше: у него ошибка пряталась в десятой значащей цифре, и заметил он её только потому, что сверял результаты разных машин.

Как делил Pentium

Делитель Pentium работал по методу SRT — по фамилиям Свини, Робертсона и Точера, которые придумали его независимо друг от друга в конце 1950-х. За шаг он даёт два бита частного вместо одного, то есть одну цифру в четверичной системе. Чтобы не тратить время на полное сравнение остатка с делителем, следующую цифру процессор угадывает по таблице: строка таблицы — первые семь битов остатка, столбец — первые четыре бита делителя после запятой. В таблице $128 \times 16 = 2048$ клеток, из них используются 1066.

Главная хитрость SRT — в наборе цифр: частное составляют не из 0, 1, 2, 3, а из $-2, -1, 0, 1, 2$. С отрицательной цифрой чуть завышенную догадку можно исправить на следующем шаге, поэтому таблице хватает грубых, укороченных значений остатка. Но у этой свободы есть граница: остаток обязан оставаться в пределах $\pm\frac{8}{3}$ делителя. Пока он там, все ошибки догадок исправимы. Если остаток вылетел за границу, следующие цифры его уже не вернут.

Таблицу строила программа. В 1994 году Intel объяснила брак ошибкой в скрипте, а в 2024-м инженер и историк компьютеров Кен Ширрифф сфотографировал кристалл Pentium под микроскопом, прочитал таблицу по расположению транзисторов и пришёл к выводу, что ошибка сидела глубже — в математике: программа неверно провела границу области цифры 2. Пустыми остались шестнадцать клеток. До одиннадцати из них остаток добраться не может, а пять, по одной у самой верхней границы пяти столбцов, достижимы. Вместо цифры 2 они выдавали 0, остаток улетал далеко за $\frac{8}{3}$ делителя, и все следующие цифры частного становились мусором.

Испортите в виджете клетку из середины полосы цифры 1 или −1 в любом столбце, и проверка из пяти тысяч делений найдёт около сотни ошибок. Брак Pentium прошёл все проверки, потому что его пять клеток стоят на самом краю, куда остаток почти не забредает. Тим Коу и Питер Тан доказали, что попасть туда можно только с делителем, у которого биты с пятого по десятый после запятой — все единицы, а кроме того, остаток должен несколько шагов подряд подкрадываться к границе. Журнал Byte оценил, что ошибается примерно одно случайное деление из девяти миллиардов. Случайными тестами такой брак не поймать, и опыт ниже это показывает.

Ноль и ноль. Даже прицельная стрельба по опасным делителям не попадает: нужно ещё, чтобы и делимое вело остаток к краю. Коу нашёл свою пару рассуждением: восстановил устройство делителя и вычислил, какие числа приведут остаток в плохую клетку. Его делитель — в последней строке вывода: после единицы идут 0111, плохой столбец, а дальше сплошные единицы.

Сумматор ОТК проверил на всех входах — их было 65 536. У делителя двойной точности входов $2^{128}$, перебрать их невозможно, а случайная выборка пропускает редкие пути. Таким узлам нужно доказательство: рассуждение, которое покрывает все входы сразу. После истории с Pentium Intel стала проверять арифметические блоки своих процессоров формальными доказательствами, правильность которых сверяет программа. При разработке Pentium 4 такие доказательства нашли ошибки, которые могли бы обернуться таким же отзывом процессоров. А читателю урок попроще: если в коде есть таблица, сгенерированная программой, проверьте и программу, и таблицу — особенно на краях.

Задачи

Четыре заказа сборочному цеху. Проверка сверяет ваши узлы с «Искрой-8» и с Python на тысячах входов, а где сказано «без плюса» — читает код.

Напишите add(a, b) — сумму неотрицательных целых любого размера, не пользуясь + и -: только &, |, ^, ~, сдвиги, сравнения, if и циклы. Подвох в размере: на числах в четыреста тысяч битов функция должна укладываться в секунду, а сумматор из цеха № 1, бегущий по разрядам один за другим, на таких числах не успеет. Потом напишите sub8(a, b) — разность байтов по модулю 256, как у команды SUB, тоже без плюса и минуса (свою add вызывать можно).

Работайте со всеми разрядами сразу. a ^ b — сумма без переносов: в каждом разряде то, что даёт XOR. a & b отмечает разряды, где родился перенос, а (a & b) << 1 — куда он должен прийти.

Значит, $a + b = (a \oplus b) + ((a \mathbin{\&} b) \ll 1)$ — снова сумма двух чисел. Повторяйте, пока переносы не кончатся. Каждый проход обрабатывает все разряды сразу, а проходов столько, какова самая длинная цепочка переносов, — у случайных чисел она короткая.

Для sub8 вспомните цех № 2: $a - b = a + \overline{b} + 1$. «Перевернуть восемь битов» — это ~b & 0xFF или b ^ 0xFF, а лишний девятый бит в конце срезает & 0xFF.

Цикл в add — это сумматор, где все разряды работают одновременно, как в железе, а проходы цикла — волны переноса. Худший случай — та же длинная цепочка, что и в сумматоре с последовательным переносом: $2^n - 1 + 1$ потребует $n + 1$ проходов. Для случайных чисел цепочки переносов редко длиннее нескольких десятков разрядов, поэтому проходов мало, и каждый — несколько операций над целым числом сразу.

Напишите alu(op, a, b) — программную модель арифметико-логического устройства «Искры-8». op — одна из строк 'ADD', 'SUB', 'AND', 'OR', 'XOR', 'SHL', 'SHR', 'INC', 'DEC', 'CMP'; a и b — байты (у сдвигов, INC и DEC второй операнд не используется). Функция возвращает (результат, z, n, c), где флаги — 0 или 1, строго по таблице из технического задания. Для CMP результат — неизменное a. На неизвестную операцию функция должна выбрасывать ValueError, как машина останавливается на неизвестной команде. Проверка сверит ваше АЛУ с эмулятором на всех операциях и сотнях пар.

Сначала посчитайте «сырой» результат — может быть, больше 255 или меньше нуля, — и флаг C, пока девятый бит ещё виден. Потом обрежьте до байта через & 0xFF и посчитайте Z и N уже от байта.

Края, которые проверит ОТК: INC от 255 даёт 0 и C = 1, DEC от 0 даёт 255 и C = 1 (заём), SHL отправляет в C старший бит, SHR — младший, а у AND, OR, XOR флаг C всегда 0.

Следите за порядком: флаг C считается от «сырого» результата, а Z и N — от обрезанного байта. У CMP флаги те же, что у SUB, но в регистр ничего не пишется. В железе всё это считается одновременно, а выбор делает мультиплексор; в программе удобнее разветвиться, и по скорости модели это всё равно.

Добавим «Искре-8» флаг, которого у неё нет. Напишите add_flags(a, b) и sub_flags(a, b) для байтов a и b (0–255). Каждая возвращает словарь с четырьмя флагами результата — {'Z': …, 'N': …, 'C': …, 'V': …}, значения 0 или 1. Z, N и C — как у ADD и SUB «Искры-8» (при вычитании C — заём). V — знаковое переполнение: 1, если результат, прочитанный как число со знаком от $-128$ до 127, не равен точной сумме или разности чисел со знаком. Например, $127 + 1$: Z = 0, N = 1, C = 0, V = 1.

Прямой путь: переведите байты в числа со знаком (x - 256, если x >= 128), сложите или вычтите и проверьте, попал ли ответ в диапазон от $-128$ до 127.

Путь через биты, как в железе: при сложении переполнение случается, когда у слагаемых одинаковый знак, а у результата другой. Знак — бит 7, и проверку можно записать одним выражением: (a ^ r) & (b ^ r) & 0x80, где r — байт результата.

Вычитание с подвохом: $a - b$ переполняется, когда у a и b знаки разные, а знак результата не совпал со знаком a. Например, $-128 - 1$: в байтах sub_flags(128, 1) — результат 127, V = 1.

Флаги C и V отвечают на один вопрос — «поместился ли ответ» — для двух прочтений одного байта: без знака и со знаком. Процессор не знает, какое прочтение имел в виду программист, поэтому считает оба, а программа смотрит на нужный флаг. В x86 после сравнения чисел без знака проверяют перенос, а для чисел со знаком — сочетание N и V (там они называются SF и OF): $a < b$, когда $N \ne V$.

Напишите multiply(a, b) — произведение двух целых, в том числе отрицательных, без *, /, //, % и **: только сложение, вычитание, сдвиги и битовые операции (плюс сравнения, if, циклы и abs). Произведение тысячезначных чисел должно считаться быстрее секунды, так что прибавлять a к сумме b раз не выйдет. Осторожно с отрицательными числами: проверьте, что делает -1 >> 1 в Python.

Египетский способ из цеха № 5: пока множитель не ноль, смотрите на его младший бит (b & 1); если он 1, прибавьте к сумме a; затем a <<= 1, b >>= 1.

Отрицательные числа Python ведут себя так, будто дополнительный код у них бесконечной ширины, и сдвиг вправо округляет вниз: -1 >> 1 равно $-1$, поэтому цикл while b при отрицательном b никогда не кончится. Запомните знак, умножайте модули и верните знак в конце.

Сложений не больше, чем битов в множителе, — для тысячезначного числа около 3300, а не $10^{1000}$. Знак произведения — XOR знаков сомножителей, это и записано в первой строке. Процессоры поступают иначе: они умеют умножать числа в дополнительном коде напрямую, с поправкой на старший разряд, но в Python модули проще.

Куда дальше

Завод выпустил АЛУ «Искры-8». ОТК проверил его на всех входах и заодно выяснил, почему делитель так проверить нельзя.

Но у нашего АЛУ нет памяти. Подайте на входы 200 и 100 — на выходе появится 44; уберите входы, и ответ исчезнет. Чтобы сложить десять чисел, промежуточную сумму нужно где-то держать до следующего шага, а схема забывает результат сразу. Считать по шагам можно, только когда есть память и время: провод, который держит бит, когда входы уже ушли, и метроном, который говорит, когда делать следующий шаг. Обе вещи, как ни странно, тоже собираются из NAND. Нужна только петля, которую в мастерской главы 29 мы запрещали. Этим займётся глава 31.