CPU·IV Машина Глава 31 из 65
Память и такт
Сумматор из прошлой главы забывает ответ, как только меняются входы. Здесь мы возьмём осциллограф и увидим, как петля из двух вентилей начинает помнить. А заодно узнаем, зачем процессору метроном и как программу лунного модуля «Аполлона» вплетали в провода.
Машина
- 28 Биты
- 29 Вентили
- 30 Сумматор и АЛУ
- 31 Память вы здесь
- 32 Процессор
- 33 Ниже Python
- 34 Кэши
- 35 Конвейер
Опирается на: 30 · Машина считает
Что вы унесёте из главы
- читать временные диаграммы и предсказывать, что защёлка, триггер, регистр или счётчик сделают на следующем фронте такта
- объяснять, как обратная связь превращает вентили в память, а тактовый сигнал — в машину, которая шагает
- понимать, что значат регистры и гигагерцы в характеристиках процессора и как устроены ОЗУ и ПЗУ
Глава 30 собрала АЛУ «Искры-8» и закончилась опытом, от которого становится неуютно. Подайте на входы 200 и 100 — на выходе появится 44, а то, что не влезло в байт, уйдёт во флаг переноса. Уберите входы — и ответ исчезнет. Чтобы сложить десять чисел, промежуточную сумму надо куда-то положить, а на следующем шаге взять снова. Положить её некуда: в схеме нет места, где число могло бы полежать.
В Python такой вопрос не возникает. В главе 4 мы завели копилку total и прибавляли к ней число за числом, и значение спокойно ждало следующего шага. А схемы глав 29 и 30 устроены как чистые функции из главы 5: выход зависит только от того, что сейчас на входах. Вчерашних входов для них не существует.
Чтобы считать по шагам, машине не хватает двух вещей. Нужно место, где число лежит, пока его не попросят, — память. И нужен сигнал «сейчас», по которому все части машины разом делают следующий шаг, — время. В мастерской главы 29 провод, который возвращал выход детали на её же вход, протянуть не давали: петли там были запрещены. Здесь мы их разрешим, и из петли получится и память, и метроном. Всё это происходит во времени, так что главный прибор главы — осциллограф. Будем смотреть на сигналы, угадывать следующий скачок и проверять себя.
Развёртка: как читать осциллограмму
Осциллограф рисует напряжение на проводе как функцию времени: время бежит слева направо, напряжение откладывается вверх. В цифровой схеме уровней всего два, поэтому картинка выходит ступенчатой: высокий уровень — 1, низкий — 0. Несколько таких дорожек одна под другой, с общим временем, называют временной диаграммой. Скачок снизу вверх называют фронтом, сверху вниз — спадом, или задним фронтом. Почти всё в этой главе происходит на фронтах.
Первый опыт — самая глупая схема, какую можно придумать. Возьмём инвертор, вентиль «не», и соединим его выход с его же входом. Если на выходе 1, на входе тоже 1, и инвертор обязан выдать 0. Но тогда на входе 0, и он обязан выдать 1. Логика противоречит сама себе.
Что покажет осциллограф на выходе инвертора, замкнутого сам на себя? Подсказка: вентиль отвечает с задержкой, пусть и крошечной.
В цифровой модели с задержкой противоречие превращается в колебание. Выход меняется, через одну задержку изменение возвращается на вход, ещё через одну задержку вентиль отвечает на него — и так без конца: 0, 1, 0, 1 с периодом в две задержки. В реальной схеме одиночный инвертор хитрее: его выход повисает посередине между 0 и 1. Вентиль по природе усилитель, и в такой короткой петле он находит равновесие. Поэтому на практике кольца собирают минимум из трёх инверторов, и тогда колебание устойчиво.
Задержка — главное действующее лицо этой главы. Без неё схема с петлёй была бы уравнением без решения, а с ней превращается в процесс, который можно проследить по шагам. Проследим его так же, как в главе 18 считали приёмный покой: каждое переключение — событие в календаре, календарь — куча, наверху которой ближайшее событие. Программа ниже собирает кольца из одного, двух, трёх и пяти инверторов и печатает моменты, когда меняется выход последнего.
У трёх инверторов выход меняется каждые три задержки, у пяти — каждые пять: по кольцу бежит один фронт, и полный период — это два его круга, $2 \cdot n$ задержек. Такое кольцо называют кольцевым генератором. Его ставят прямо на кристалл, когда хотят измерить, насколько быстрыми получились вентили: частоту мерить легко, а по ней сразу видна задержка.
А кольцо из двух инверторов молчит. В виджете ниже это режим «2»: у первого инвертора на выходе 1, у второго 0, и каждый согласен со своим входом. Менять нечего, и схема так и будет стоять сколько угодно долго, пока есть питание. Она помнит, в каком состоянии её оставили, — это один бит памяти.
Толкните провод в кольце из двух. Фронт обежит петлю один раз, вернётся туда, откуда вышел, и согласится с новым значением. Петля переписана. Выход здесь снова подаётся на вход, и у такого соединения есть имя — обратная связь. С нечётным числом инверторов в петле она даёт колебания, с чётным — память. Не хватает малого: толкать провод пальцем — не способ записи.
Петля с дверцами
В главе 29 инвертор собирался из NAND, на оба входа которого подан один сигнал. Годится и другой способ: «не-и», у которого на втором входе 1, тоже переворачивает первый вход, ведь $\overline{x \cdot 1} = \overline{x}$. Заменим оба инвертора петли на такие NAND. Пока на свободных входах единицы, ничего не изменилось: петля из двух инверторов хранит свой бит. Но теперь у неё есть дверцы. Подайте 0 на свободный вход верхнего вентиля — и NAND выдаст 1, что бы ни пришло к нему по петле: если хоть один вход «не-и» равен нулю, ответ 1. Верхний выход стал единицей, фронт обежал петлю, нижний выход стал нулём. Верните на дверцу 1 — петля останется в новом положении.
Получилась защёлка, по-английски latch. Верхний выход называют $Q$ — это хранимый бит, нижний $\overline{Q}$ — его отрицание. Вход, который ставит $Q = 1$, обозначают $\overline{S}$ (от set, черта — потому что он срабатывает от нуля), второй вход $\overline{R}$ (reset) сбрасывает $Q$ в 0. По этим двум входам её и называют RS-защёлкой.
| $\overline{S}$ | $\overline{R}$ | что будет с $Q$ |
|---|---|---|
| 1 | 1 | хранится прежнее значение |
| 0 | 1 | $Q = 1$ |
| 1 | 0 | $Q = 0$ |
| 0 | 0 | $Q = \overline{Q} = 1$ — запрещённое состояние |
Последняя строка — ловушка. Если открыть обе дверцы, оба вентиля выдадут 1, и выходы перестанут быть отрицаниями друг друга. Это ещё полбеды. Беда наступает, когда обе дверцы закрываются одновременно: оба вентиля видят на входах единицы и оба одновременно падают в 0, потом оба видят нули и прыгают в 1. В коде ниже оба вентиля переключаются разом, шаг за шагом, пока схема не успокоится.
В идеальной модели защёлка мечется вечно. Реальные вентили не бывают в точности одинаковыми: рано или поздно один чуть обгонит другой, и защёлка свалится в одно из состояний. В какое и когда, заранее сказать нельзя, а какое-то время выход может и вовсе висеть между 0 и 1. Это явление называется метастабильностью. Беда эта вполне практическая: когда в схему приходит сигнал извне, например нажатие кнопки, его пропускают через две ячейки памяти подряд, чтобы вторая получила уже успокоившееся значение. В виджете выше есть режим «защёлка»: нажмите обе дверцы, затем «Отпустить обе разом» — с галочкой «настоящие вентили» и без неё.
Один провод данных и разрешение
RS-защёлка неудобна дважды: у неё запретное сочетание входов, и чтобы записать бит, надо решить, на какую из двух дверец нажимать. Обе беды лечатся двумя вентилями спереди. Входов становится два, но других: $D$ — что записать, и $E$ (enable) — можно ли писать. Дверцы получают $\overline{S} = \overline{D \cdot E}$ и $\overline{R} = \overline{\overline{D} \cdot E}$. Пока $E = 0$, на обеих дверцах единицы — защёлка хранит. Когда $E = 1$, открыта одна из дверец (какая — решает $D$), и защёлка копирует $D$. Запретное состояние не возникает никогда.
Такую ячейку называют D-защёлкой, а про открытую говорят, что она прозрачна: пока $E = 1$, выход $Q$ повторяет $D$, как окно. Предскажите выход сами.
Прозрачность кажется удобством, но она ломает то, ради чего мы всё затеяли. Вспомним копилку: регистр, сумматор и петля между ними, чтобы на каждом шаге выполнялось total = total + 5. Пусть регистр — восемь D-защёлок. Открываем их на мгновение, чтобы записать сумму. Сумма проходит в регистр, тут же появляется на входе сумматора, через шестнадцать задержек на его выходе уже $total + 10$, и защёлки, всё ещё открытые, пропускают и её. Сколько пятёрок прибавится за один шаг, зависит от того, сколько раз сумма успеет обежать петлю, пока открыто окно. Хуже того, разряды сумматора успокаиваются в разное время, и в регистр может попасть смесь старых и новых битов.
Метроном
Решение похоже на шлюз на канале. Поставим две D-защёлки подряд и будем открывать их по очереди: первую — когда управляющий сигнал равен 0, вторую — когда он равен 1. Сквозного прохода нет никогда: одна из двух створок всегда закрыта. Пока сигнал равен 0, первая защёлка слушает $D$, а вторая держит старое значение. В момент, когда сигнал прыгает из 0 в 1, первая закрывается, запомнив $D$ за мгновение до фронта, а вторая открывается и показывает это значение на выходе. Пока сигнал равен 1, $D$ может меняться как угодно — первая створка закрыта.
Такую пару называют D-триггером. Он меняет выход только в момент переднего фронта, и только один раз за период. Управляющий сигнал, который равномерно перескакивает 0, 1, 0, 1, называется тактовым, а один его период — тактом. Все триггеры процессора подключены к одному тактовому сигналу и по каждому фронту разом принимают новые значения.
Между двумя фронтами комбинационные схемы успевают досчитать: сумматор получает новые входы сразу после фронта, и к следующему фронту на его выходе стоит готовый ответ. На этом держится главное правило синхронной схемы: период такта должен быть длиннее самого медленного пути от одного триггера до другого. В главе 30 перенос бежал по сумматору шестнадцать задержек — эти шестнадцать задержек и ограничивают частоту «Искры-8».
Теперь можно прочесть строчку из характеристик процессора. «3 ГГц» — это три миллиарда тактов в секунду, один такт длится треть наносекунды. Свет успевает пролететь за это время около десяти сантиметров. Всё начинается с кварцевого резонатора на десятки мегагерц. Из его колебаний получают опорную частоту, обычно 100 МГц, а схема-умножитель на кристалле процессора поднимает её дальше: множитель 36 в настройках компьютера означает $36 \times 100$ МГц $= 3{,}6$ ГГц. Разгон процессора — игра на запасе, который оставили инженеры. Если поднять частоту слишком высоко, самый длинный путь в какой-то момент перестанет успевать к фронту. Тогда в регистр попадёт недосчитанное значение, и программа поведёт себя странно.
Регистр: восемь триггеров на одном такте
Восемь D-триггеров с общим тактом хранят байт. Это регистр. Обычно перед каждым триггером ставят стрелочник из главы 29 с общим управляющим входом LOAD: при LOAD = 1 на вход $D$ идёт новое значение, при LOAD = 0 — собственный выход триггера, и на фронте он перезаписывает сам себя тем же. Так регистр принимает число, только когда его попросили, а в остальные такты держит прежнее.
У «Искры-8» шесть восьмибитных регистров: четыре рабочих R0–R3 и два служебных, PC и SP, про которые будет следующая глава. Это 48 триггеров, плюс по одному на каждый из трёх флагов АЛУ. В процессоре вашего ноутбука рабочих регистров 16 (архитектура x86-64) или 31 (ARM64), по 64 бита. Немного: регистры — самая быстрая и самая дорогая память, она стоит прямо у АЛУ.
Регистр плюс сумматор плюс провод обратно — и копилка из главы 4 существует в железе: на каждом фронте $total \leftarrow total + x$. Правило «все триггеры принимают новые значения разом» в Python тоже есть, это множественное присваивание из главы 2: сначала по старым значениям вычисляется вся правая часть, и только потом все имена меняются вместе. Строка a, b = b, a + b — это фронт такта для двух регистров. Если разбить её на две строки, новое a успеет протечь во вторую, как сквозь прозрачную защёлку.
С фронтом получились числа Фибоначчи, без него — степени двойки, которые к восьмому шагу переполнили восьмибитный регистр и обнулились. Так же устроена клеточная «Жизнь» и любая симуляция, где все клетки меняются разом: новое поколение считают полностью по старому и только потом подменяют. Кто обновляет клетки по одной, получает другую, неправильную игру.
Счётчик и часы на руке
Если в копилку на каждом такте класть единицу, получится счётчик: регистр, к выходу которого подключена схема «+1», а её выход — снова к входу. Схема «+1» проще сумматора. При прибавлении единицы разряд меняется тогда и только тогда, когда все разряды младше него равны 1: $0111 + 1 = 1000$. Нулевой разряд меняется на каждом такте, первый — на каждом втором, второй — на каждом четвёртом. Это наблюдение превращается в схему из одних «и» и XOR, и вы соберёте её в задаче «Счётчик без плюса».
Есть и совсем ленивый счётчик. Соединим выход каждого триггера с его же входом через инвертор: тогда на каждом фронте триггер переключается. А тактом для следующего триггера сделаем выход предыдущего, перевёрнутый. Первый переключается на каждом такте, второй — когда первый падает из 1 в 0, то есть вдвое реже, третий — ещё вдвое реже. Каждый триггер делит частоту пополам.
Такая цепочка тикает в кварцевых часах. Кварцевый резонатор в них колеблется 32 768 раз в секунду, и это число выбрано не случайно: $32\,768 = 2^{15}$. Пятнадцать триггеров подряд делят частоту ровно до одного герца, и раз в секунду последний из них толкает стрелку. Проверим.
Цепочка обнуляется на 32 768-м колебании, на 65 536-м и на 98 304-м, то есть раз в секунду. Кстати, внутренний цикл while — это перенос, который бежит по разрядам, как в сумматоре из главы 30. У ленивого счётчика есть цена: разряды меняются по очереди, и пока волна бежит, на выходах на мгновение видны неверные числа. Часам это безразлично, процессору нет, поэтому в процессоре счётчики синхронные — все триггеры на одном такте.
Светофор: автомат из регистра и таблицы
Регистр, комбинационная схема и такт — этого хватает на устройство, которое ведёт себя по-разному в зависимости от того, что было раньше. Возьмём светофор. Сейчас горит зелёный, через несколько тактов будет жёлтый, потом красный, потом красный вместе с жёлтым — знак, что скоро зелёный. Что зажечь на следующем такте, зависит от того, что горит сейчас и сколько уже горит. Эти два числа хранятся в регистрах. Таблица «из какого состояния в какое» — комбинационная схема, которая по выходам регистров считает их следующее значение. Фронт такта переписывает регистры, и всё повторяется.
Устройство с конечным числом состояний, которое на каждом шаге по текущему состоянию и входу выбирает следующее, называется конечным автоматом. Вы его уже видели: в главе 27 алгоритм КМП бежал по тексту, помня единственное число — сколько букв образца совпало. В железе автомат — это всегда регистр состояния и таблица переходов. Так устроены лифт, стиральная машина, контроллер клавиатуры. В главе 54 автоматы станут математическим объектом, и выяснится, на что их хватает, а на что нет.
У нашего светофора нет входов: он ходит по кругу и никого не слушает. В задаче «Светофор с кнопкой» появится кнопка для пешехода и ещё один бит памяти: запомнить, что кнопку нажали, даже если зелёный для машин ещё не отгорел положенное.
ОЗУ: 256 ящиков с номерами
У «Искры-8» 256 байт памяти, от 0x00 до 0xFF. Это 256 регистров по восемь триггеров — 2048 бит. Регистров много, а проводов к ним хочется мало: восемь линий адреса, восемь линий данных и сигнал «записать». Как по номеру добраться до одного из 256?
Для записи нужен дешифратор: схема с восемью входами и 256 выходами, из которых по адресу загорается ровно один. Линия номер 42 — это «и» восьми битов адреса, где на месте нулей стоят инверторы: $42 = 00101010_2$, значит, линия горит при $\overline{a_7}\,\overline{a_6}\,a_5\,\overline{a_4}\,a_3\,\overline{a_2}\,a_1\,\overline{a_0}$. Выход дешифратора, пропущенный через «и» вместе с сигналом «записать», становится LOAD нужного регистра, и на фронте такта байт с линий данных ложится в эту ячейку и больше никуда.
Для чтения нужно обратное: из 256 байтов выбрать один и вывести на линии данных. Это дерево стрелочников, обещанное в главе 29. Нижний ярус из 128 стрелочников по младшему биту адреса выбирает из каждой пары ячеек одну, следующий ярус по следующему биту — из каждой пары победителей, и через восемь ярусов остаётся одна ячейка.
Две тысячи стрелочников только на чтение — дорого. Промышленные микросхемы памяти экономят: раскладывают ячейки квадратом и делят адрес пополам. Старшие четыре бита выбирают одну из 16 строк, младшие — один из 16 столбцов, и вместо 256 линий дешифратора хватает 16 + 16. В виджете ниже так устроена память «Искры-8». Выберите адрес переключателями или пальцем по сетке, наберите байт и запишите.
0xF0–0xF7 выведены на экран 8 × 8: каждый байт — строка пикселей. Запишите туда что-нибудь.Память, в которую можно и писать, и читать любую ячейку по номеру за одно обращение, называют оперативной, или ОЗУ. Английское RAM — random access memory, память с произвольным доступом: ячейка номер 200 достаётся так же быстро, как ячейка номер 0. Именно на это свойство опиралась глава 14, когда объясняла, почему a[i] в списке Python стоит одинаково для любого i.
В промышленных ОЗУ вместо NAND стоят схемы поэкономнее. Ячейка статической памяти, из которой сделаны кэши процессора, — шесть транзисторов, та же петля из двух инверторов плюс два ключа для записи и чтения. В регистрах ключей ставят больше, чтобы за такт читать несколько чисел сразу. Динамическая память, обычные гигабайты «оперативки», хранит бит зарядом крошечного конденсатора при одном транзисторе. Заряд утекает, и каждую ячейку приходится перечитывать и перезаписывать заново, обычно раз в 64 миллисекунды. На такой памяти, которая всё время забывает и всё время вспоминает, держится почти вся «оперативка» в мире.
ПЗУ: программа, вплетённая в провода
Бывает память, которую не нужно перезаписывать никогда: программа запуска компьютера, таблица шрифта, прошивка стиральной машины. Её делают проще. Дешифратор адреса остаётся, а триггеры не нужны: выходная линия дешифратора проходит мимо восьми линий данных и с теми, где должна быть единица, соединена, а с остальными — нет. Содержимое задаётся при изготовлении, рисунком соединений, и изменить его нельзя. Это постоянная память, ПЗУ, по-английски ROM — read-only memory.
Самое знаменитое ПЗУ в истории соткано руками.
За сто шестьдесят лет до этого на станке Жаккара из главы 4 игла проходила там, где в карте дырка, и поднимала свою нить. В верёвочной памяти провод проходит сквозь колечко там, где в программе единица. Ада Лавлейс писала, что Аналитическая машина ткёт алгебраические узоры. Программу «Аполлона» действительно соткали.
У верёвочной памяти было и другое достоинство: плотность. Один провод, продетый сквозь колечко, — это бит, а сквозь одно колечко шло много проводов, поэтому верёвка хранила в несколько раз больше бит на кубический сантиметр, чем перезаписываемая память на сердечниках того же компьютера. Чтобы заметить ошибку ткачихи, к каждому слову добавляли бит чётности: шестнадцатый провод проходил сквозь колечко или мимо так, чтобы единиц в слове всегда было нечётное число. Неверный проход меняет число единиц на одну, чётность ломается, и компьютер замечает порчу. Это родственник контрольной цифры Луна из главы 5.
Задачи
Четыре задачи, в каждой схема с памятью живёт по тактам. Сигналы — списки нулей и единиц, по значению на каждый момент времени, как на дорожках осциллографа.
Сигнал записан списком: d[t] — значение провода в момент $t = 0, 1, 2, \ldots$ Напишите две функции, которые по входам возвращают список значений выхода $Q$ в те же моменты.
latch(en, d) — D-защёлка: в момент $t$, если en[t] == 1, выход равен d[t], иначе остаётся прежним. flipflop(clk, d) — D-триггер: выход меняется только в момент переднего фронта, то есть когда clk[t - 1] == 0 и clk[t] == 1, и становится равным d[t]. До начала записи и $Q$, и clk были равны 0. Списки бывают длиной в сотни тысяч.
Обе функции идут по моментам времени и держат в переменной текущее значение $Q$; эта переменная и служит триггером. В каждый момент решают, обновить её или оставить, и дописывают в ответ.
Чтобы узнать фронт, нужен ещё один бит памяти: значение clk в прошлый момент. Начните его с нуля — тогда clk[0] == 1 тоже окажется фронтом.
Защёлке хватает одного бита состояния, $Q$. Триггеру нужно два: $Q$ и прошлое значение такта. В железе этот второй бит хранит первая защёлка пары: она помнит, что было до фронта.
Состояние четырёхбитного счётчика — кортеж (q3, q2, q1, q0), старший бит слева. Напишите step(q, en): при en == 1 вернуть следующее состояние ($q + 1$ по модулю 16), при en == 0 — то же самое. Затем decade(q, en) — десятичный счётчик, как в электронных часах: он считает 0, 1, …, 9 и снова 0 и возвращает пару (новое состояние, перенос), где перенос равен 1 только на шаге 9 → 0.
Пользоваться можно только вентилями: операциями &, | и ^, своими функциями и распаковкой кортежей. Никаких +, if, сравнений и not: «не $x$» — это x ^ 1. Проверка соединит два ваших десятичных счётчика в цепочку — перенос младшего станет en старшего — и проверит, что табло досчитает до 99 и вернётся к 00.
Разряд $i$ меняется, когда разрешён счёт и все младшие разряды равны 1. Заведите «разрешения переключиться»: $t_0 = en$, $t_1 = t_0 \cdot q_0$, $t_2 = t_1 \cdot q_1$, $t_3 = t_2 \cdot q_2$. Новый разряд — $q_i \oplus t_i$.
Из состояний 0–9 только у девятки, $1001_2$, единицы и в $q_3$, и в $q_0$. Перенос wrap = en & q3 & q0. Если он равен 1, все биты результата надо обнулить: «и» каждого бита step(q, en) с wrap ^ 1.
Цепочка $t_0, t_1, t_2, t_3$ — тот же перенос, что бежал по сумматору в главе 30, только прибавляется всегда единица. Подавая перенос десятичного счётчика на en следующего, соединяют разряды в часах, в счётчике километров и в табло на стадионе. Чтобы получились секунды от 00 до 59, старшему разряду нужен свой сброс на шестёрке.
Автомат светофора для машин на пешеходном переходе. Его состояние — тройка (light, t, request): какой свет горит, сколько тактов он горел до текущего (при смене света t = 0) и бит вызова — нажимал ли кто-нибудь кнопку. Напишите step(state, button), которая по состоянию и кнопке в текущем такте (0 или 1) возвращает состояние на следующем.
| свет | горит | потом |
|---|---|---|
green | не меньше 3 тактов и пока нет вызова | yellow |
yellow | 1 такт | red — пешеходы идут |
red | 3 такта | red-yellow |
red-yellow | 1 такт | green |
Нажатие ставит request = 1 в любом свете, кроме red, и вызов учитывается в том же такте. При переходе в red вызов сбрасывается: пешеход дождался. Пока горит red, кнопка ничего не делает.
Посчитайте done = t + 1 — сколько тактов свет горит вместе с текущим. Время вышло, если done дошло до длительности. Тогда новый свет и t = 0, иначе тот же свет и t = done.
Ловушка — нажатие, которое пришло раньше, чем отгорел минимальный зелёный. Если смотреть только на button в текущем такте, пешеход, нажавший один раз, не дождётся никогда. Поэтому сначала request = request | button, а уже потом решение о переходе.
В железе request — RS-защёлка из начала главы: кнопка ставит её в 1, переход в красный сбрасывает. Остальное — регистр света, счётчик тактов и таблица переходов. Нажатие на красном с жёлтым запоминается и вызовет следующий круг, как только зелёный отгорит свои три такта.
Верёвочная память на $n$ колечек: колечко $i$ хранит байт data[i]. Проводов девять: провод $k$ от 0 до 7 несёт бит $k$ (вес $2^k$) и проходит сквозь колечко $i$, если этот бит в data[i] равен 1. Девятый провод, номер 8, — чётность: он проходит сквозь колечко, если единиц среди восьми битов чётное число, так что всего проводов сквозь каждое колечко — нечётное число, как у «Аполлона».
Напишите weave(data) — список из девяти списков номеров колечек по возрастанию, и read(wires, n) — обратно список из $n$ байтов, где на месте колечка с нарушенной чётностью стоит None. Слова бывают длиной в десятки тысяч колечек.
Для weave пройдите по байтам и по восьми битам каждого: byte >> k & 1. Попутно считайте единицы — по их числу решается провод чётности.
Для read не спрашивайте у каждого колечка, есть ли оно в каждом проводе: i in wire по списку — это проход по списку, и на 60 000 колечек выйдут миллиарды сравнений. Пройдите один раз по каждому проводу и для каждого номера в нём прибавьте бит и единицу в счётчик проходов.
Обе функции линейны: каждый проход провода сквозь колечко трогаем один раз. Так читала и машина: перемагниченное колечко за один импульс отвечает во все свои провода сразу. Чётность ловит любую одиночную ошибку ткачихи, но не две сразу: две ошибки в одном слове вернут нечётность, и порча пройдёт незамеченной.
Куда дальше
У «Искры-8» теперь есть почти всё. АЛУ из главы 30 складывает, вычитает, сравнивает и сдвигает. Регистры R0–R3 держат числа между тактами, флаги помнят, каким вышел последний результат, ОЗУ на 256 байт хранит что угодно по адресу, и восемь его байтов видны на экране. Есть счётчик, который прибавляет единицу на каждом такте, и тактовый сигнал, который раз за разом командует «шаг».
Но всё это пока стоит. Кто-то должен решить, что АЛУ делает на этом такте — складывает или вычитает, — из какого регистра брать числа, куда класть ответ и что делать на следующем такте. В примерах этой главы это решали мы сами, руками. Подсказка лежит на виду: счётчик может показывать на ячейку памяти, а в ячейке может лежать не число, а приказ. Как машина сама пойдёт по таким приказам, покажет глава 32: там «Искра-8» оживёт, а процессором сначала побудете вы сами.