Пилим восьмибитный процессор. Часть седьмая, баголовная.

Я две недели не публиковал описаний прогресса разработки процессора.
Тем не менее, это не значит, что я им не занимаюсь - занимаюсь, хотя, пожалуй, уже без той остервенелой увлечённости, что в начале, плюс, отвлекаюсь на другие занятия, да ещё сидел без клавиатуры несколько дней. Но даже с учётом всего этого, две недели - срок вполне достаточный для накопления очередной порции интересных доработок.
Я так думал, да. Всего за пару дней я переделал микросхемы, определяющие тип операндов и их количество, переделал командный блок (переупорядочил команды, добавил новые), добавил новые регистры - и очевидных проблем при этом не проявлялось. Вылезали, конечно, кое-какие баги, не найденные раньше, но ничего серьёзного.
Так что я начал было заниматься командами перехода по памяти, которые сплошь однобайтные - и оказалось, что мой управляемый счётчик неправильно работает на операции, описываемой как for ($=0;$i==0;$i++) - то есть команды без операндов им не воспринимались, что вело к неправильному разбору всей дальнейшей памяти.
Окей, проблема локализована, надо только переделать счётчик...
Я потратил на это неделю.

Несложная, казалось бы, задача - а схема не давалась ни в какую. Подход "разбить на подзадачи и решить по отдельности" не работал - решённые подзадачи просто не склеивались в целое. Расписать логику схемы в виде набора логических функций, сократить вывод и реализовать получившееся схемой вовсе нельзя (вернее, можно, но это задача довольно громоздкая, и я бы только запутался).
Тогда я применил другой подход. Если задача не даётся - займись чем-нибудь другим. Пусть подсознание само решает задачу, тебе останется только проверять выдаваемые им варианты. Что, вы так не умеете? Ха-ха, неудачники!
Прошло время, подсознание действительно выдало вариант решения (уже не помню какого, да и не важно). Я открыл схему, прогнал тестовую программу, чтобы освежить в памяти структуру - а схема-то и не работает.
То есть, допустим, какой-то простой код, вроде mov a,1h не работал совсем. При этом вся логическая цепочка работала как надо, на всех контактах были правильные значения, а нужный регистр не устанавливался и всё. Странно, как и то, что раньше-то это работало - более того, при откате не предыдущую версию схемы работало тоже.
Значит что? Значит накосячил где-то при доработках, и проглядел косяк. Попробовал поискать - нету. А различий с последним рабочим образцом накопилось уже достаточно, и разобраться, какие из них являются причиной бага уже довольно трудно.
В общем, я плюнул, откатился на последнюю рабочую версию, и стал переносить доработки понемногу, усиленно тестируя схему после каждого изменения. Снова переделал микросхемы и командный блок, всё выглядело чисто. В недоумении я хотел уже было браться за блок регистров, но тут мне "повезло" (если так можно выразиться) - одна из тестовых программ давала сбой. Программа примерно такая:

MOV REG1,VALUE ;изменяем любой регистр, не обязательно через MOV
SHL REGx,VALUE ;регистр может быть указан любой, не обязательно тот, что в предыдущей команде

Первая команда выполнялась безупречно, а на момент чтения (даже не выполнения!) первого операнда второй команды REG1 обнулялся. Путём перебора, выяснилось, что такой же баг вызывают некоторые другие операнды во второй команде, например SUB и XOR. А, скажем, SUM проходила нормально. Поэкспериментировав, я выяснил, что и не команда даже влияет на появление бага, а полный байт команда+типы параметров; причём последовательности значений "бажных" байт не выглядели хоть как-то осмысленно. Например, значения с 53h до 57h приводили к ошибке, значения в промежутке 58h-63h ошибки не вызывали, а значения выше 63h - опять приводили к багу.
Логики никакой. Да даже и не в том, дело, какая последовательность вызывает ошибку, дело в том, что процессор попросту не мог такую ошибку допустить. У него есть нога EXECUTE, сигнал на которой вызывает выполенение буферизованной команды. Если на ноге нет сигнала - состояние процессора не меняется. Вот эта нога выделена на развёрнутой схеме:


Клик для увеличения
Как видите, n-транзисторы просто отсекают процессор от буфера, так что совершенно не имеет значения, что там "вовне" - если, конечно, на ноге ноль. А на ноге был ноль (сигнал появлялся только тогда, когда счётчик доходил до нужного значения), но процессор всё время вёл себя по разному.
Ошибки не было - и, в то же время, она была. Я потратил уйму времени и нервов, пытаясь разобраться, и был уже близок к тому, чтобы сдаться, признав, что ошибка где-то в Logisim.
Хорошо, что подсознание и тут предложило мне вариант. "Может быть - подумал я - счётчик и вправду выдаёт на выход EXECUTE сигнал, но тут же убирает его?".

Взглянем снова на схему счётчика:


В начальном состоянии на элемент И подаётся единица с компаратора и ноль с тактового входа. При первом такте с тактового входа придёт единица, а с компаратора - ноль. Если значения меняются одновременно, то после И реузльтат всё равно не изменится (0&1==1&0), как и требуется. Но вдруг одновременности не существует?
Забегая вперёд, скажу, что так оно и есть. В справке Logisim, в разделе "Задержки логических элементов" читаем в описании схемы, похожей на нашу:

Но элементы НЕ не реагируют мгновенно на сигналы на входах в реальности, и в Logisim - тоже. В результате, когда значение на входе этой цепи изменяется с 0 на 1, элемент И будет короткое время видеть 1 на обоих входах, и выдаст на выходе 1 на короткое время. Вы не увидите этого на экране.

Так как же проверить такое поведение? Вариант предложен там же, в справке (к собственному удовольствию я дошёл до него самостоятельно): подключить к выходу триггер, и посмотреть, изменится ли его значение, или нет:


Бах! Триггер переключается - а, значит, ошибка вызвана именно тем, что счётчик подаёт сигнал исполнения не тогда, когда требуется. Что же, процитирую справку ещё раз:

Не могу позволить себе сказать, что Logisim всегда правильно обращается с задержками элементов. Но он по крайней мере пытается.

Почему же этот баг не проявлял себя раньше? Точно не знаю, но думаю, что просто не успел - слишком проста была схема процессора. Впервые проявлять он себя начал, видимо, уже после усложнения, что и заставило меня начать разбираться.
Устранить баг можно, но не нужно. Счётчик всё равно требуется переделывать. А переделка его мне никак не давалась - о чём я уже жаловался выше.
Помучавшись так и эдак, я применил такой подход: описал требуемую логику счётчика на псевдокоде (хотя, какой, к чёрту, псевдокод, это PHP), и попробовал потом описать этот код логической схемой (это всё равно, что строить блок-схему). Код получился такой:

$COMMANDS=array(2,10,12,0,2,11,13,1,15,1,18,0,2,9,7);
$return=array();
$set=TRUE;
$EXEC_FLAG=FALSE;
$i=0;
while (TRUE) {
if ($EXEC_FLAG) {
echo "-->EXEC ";
print_r ($return);
$EXEC_FLAG=FALSE;
$return=array();
}
if ($set) {
$for=$COMMANDS[$i];
echo "!$for ";
$lim=$for;
$set=FALSE;
$cnt=0;
}
echo ":$cnt ";
$return[$cnt]=$COMMANDS[$i];
if ($cnt==$lim) {
$EXEC_FLAG=TRUE;
$set=TRUE;
$i++;
continue;
}
$cnt++;
$i++;
}

$COMMANDS - массив, содержащий количества операндов при интерпретации ячейки памяти, как команды. Остальное, думаю, очевидно.
А вот схема, которая этот код реализует. Названия элементов соответствуют названиям переменных в коде, у регистра lim срабатывание переключено на высокий уровень (т.е. он обновляется не по переключению такта, а всегда, пока на тактовом входе есть сигнал). EXEC_FLAG и set - T-триггеры (в отличии от D-триггера они не устанавливают поданное на вход значение, а переключают собственное, т.о. их удобно использовать в качестве "флагов").


И, пока что, всё выглядит, будто он работает, как надо, и мой мозг не будет взорван. Потому, если больше не обнаружится столь же серьёзных и трудноуловимых ошибок, результат окончательной доработки процессора появится уже скоро.
Продолжение следует.

Пилим восьмибитный процессор. Часть шестая: улучшение архитектуры и снова ассемблер.

После вынужденного перерыва снова возвращаюсь к своей архиувлекательной разработке. Оставил я её в каком-то промежуточном состоянии: например, минимальный набор команд реализован, возможность менять значения в памяти есть - а перехода на нужный адрес нет (хотя всё необходимое для реализации такой команды есть, саму команду я не запилил).
Непорядок.
В общем, я достаточно долго думал и прикидывал, что делать дальше, и как лучше это что делать. Пришёл к следующему выводу: нужно менять структуру команд, пилить уже условные переходы и циклы. После этого - уже всё, настоящий хардкор.
Что плохо в текущих командах? Они были взяты от балды, и шли не в логическом порядке: скажем за логическим XOR шло арифметическое SUM, потом опять логический SHL. Добавь я сейчас команду SUB (вычитание) - её пришлось бы помещать вновь за логической командой, а не рядом с SUM, где ей самое место. Нет, если пользоваться ассемблером - то пофиг, в каком порядке идут опкоды, но при трейсе обработки команд с упорядоченными командами удобнее.
Дальше: команда NOP. Много ли можно придумать программ, где ничего не делающий операнд реально нужен? В крайнем случае для пропуска такта можно использовать MOV A,A.
Итого я пересмотрел набор команд, и выглядит теперь он так:

Опкод	Команда	Описание
0x0	MEM	Переходы по памяти
0x1	MOV	Пересылка значения
0x2	XOR	Логическое ИЛИ-НЕ
0x3	OR	Логическое ИЛИ
0x4	AND	Логическое И
0x5	SHL	Левое смещение
0x6	SHR	Правое смещение
0x7	SUM	Арифметическое сложение
0x8	SUB	Арифметическое вычитание
0x9	MUL	Арифметическое умножение
0xA	DIV	Арифметическое деление
0xB	STACK	Работа со стеком

Описание команд переходов и работы со стеком чуть ниже.
Как видите - изменился и набор и порядок. При этом пока четыре опкода остаются свободными - я даже не знаю, какие команды можно ими задать. Возможно, при расширении архитектуры появятся какие-то команды (например опкод, выводящий "Hello, world!", таким образом, делающий возможным написание такой программы размером в один байт).
Думаю, с опкодами 0x1 - 0xA вопросов не возникло. Другое дело - 0x0, обозначающий различные переходы по памяти. Как одной командой можно закодировать их все?
Тут стоит вспомнить, как переходы реализованы в x86. Самый простой, безусловный переход вызывается так:

JMP @ADDRESS

где ADDRESS указывает на адрес в памяти, на который нужно совершить переход.
Соответственно, команда в памяти представлена двумя последовательностями бит: одна кодирует команду JMP, другая шифрует адрес. Просто и логично.

Условные переходы реализованы сложнее, и состоят из двух команд. Первая: CMP (compare) - она сравнивает два операнда (вычитая один из другого), в зависимости от результата сравнивания изменяя специальные флаги во флаговом регистре. А команда условного перехода (их больше десятка, и включены даже такие, как "перейти, если чётно") уже проверяет эти флаги и переходит (или не переходит) по указанному адресу.
Сложно? Не особенно, но, в общем, сложнее, чем могло быть. И хотя у такого решения наверняка есть свои плюсы, это совершенно не значит, что его необходимо копировать.
Тем более, что у нас не большой и жирный x86, у нас слабый и виртуальный meighty, и раздавать по опкоду на каждую команду перехода просто нельзя (да ещё опкод на команду сравнения). Выход достаточно очевиден: сравнивать значения, которые всегда находятся в одном и том же месте - и, применительно к процессору, такими "местами" могут стать только регистры. Также в определённом регистре можно сохранять адрес, на который необходим переход.
Допустим, такие регистры уже есть. Тогда любая команда условного или безусловного перехода не нуждается в параметрах, а это значит, что четыре младших бита из командного байта, которые использовались под обозначение типа операнда, можно отдать под команды! Так что в один опкод 0x0 может уместиться 16 команд перехода по памяти - чего более, чем достаточно, для реализации любых условий. Я реализовал следующие условия:

[7-4]	[3-0]	Команда	Описание
0x0	0x0	JMP	Безусловный переход
0x0	0x1	JE	Переход при равенстве операндов
0x0	0x2	JNE	Переход при неравенстве операндов
0x0	0x3	JL	Переход, если первый меньше
0x0	0x4	JG	Переход, если первый больше
0x0	0x5	JLE	Переход, если первый меньше или равен
0x0	0x6	JGE	Переход, если первый больше или равен

Само собой, перед сравнением и переходом нужно задать значения для сравнения и адрес для вероятного перехода, для чего нужно использовать команду MOV.
Аналогичный подход реализован и со стековыми командами. Их запланировано четыре: PUSH (поместить в стек), POP (извлечь из стека), PEEK (изменить значение на верхушке), POKE (удалить значение с верхушки). Параметр у всех стековых команд может быть только один, поэтому ничего не мешает отдать два бита на кодирование команд:

[7-4]	[3-2]	[1-0]	Команда	Описание
0x0	0x0	{TYPE}	PUSH	Поместить на вершину стека
0x0	0x1	{TYPE}	POP	Взять с вершины стека
0x0	0x2	{TYPE}	PEEK	Изменить вершину стека
0x0	0x3	{TYPE}	POKE	Удалить вершину стека

Но к стеку я вернусь ещё не скоро (его единственное предназначение - оптимизация рекурсивных вызовов, для полноценного вычислителя он не нужен), а для переходов нужны эти самые регистры.
Можно поступить так, как поступили разработчики Intel: дать каждому пользовательскому регистру своё дополнительное назначение (я без шпаргалки помню только AX - аккумулятор и CX - счётчик). Меня всегда это смущало: вот использую я регистр (который выступает в роли сверхбыстрой надоперативной памяти) для своих целей, и тут какая-нибудь команда ждёт, что я через этот регистр буду передавать ей параметр! В общем, мне всегда хотелось разделить регистры на чисто пользовательские (с которыми программист или компилятор ЯВУ может работать, как ему вздумается, и которые процессором не используются более никак), на служебные (с которыми можно работать, но которые могут выступать параметрами команд) и внутренние (которые используются процессором под свои нужды, и изменять значения которых не рекомендуется или вовсе нельзя, например, стековый указатель).
Собственно, ничего не мешает мне сделать именно так. На адресацию регистров выделен целых восемь бит, сейчас регистров восемь, и для их кодирования достаточно трёх бит. Добавлю ещё восемь служебных регистров S0-S7, которые будут кодироваться числами от 0x8 до 0xF - и никаких проблем. Три первых регистра щедро выделяю под операнды команд условных переходов: S0 пусть содержит первое сравниваемое значение, S2 - второе, S3 - адрес перехода.

Небольшое отступление:
Да, я прекрасно понимаю, что методика передачи параметров через регистр увеличивает размер программ, поскольку один условный переход может занимать 10 байт в худшем случае! Но на такие жертвы приходится идти по причинам, описанным выше. К тому же, 10 байт - это действительно худший случай; если какой-то регистр уже содержит нужное значение, размер команды уменьшится.

И вроде бы всё хорошо, но есть один маленький нюанс: все операции с памятью (чтение, запись, переход) сейчас возможны только по абсолютным адресам, заданным константой. О том, чтобы ссылаться на адреса переменными я попросту не подумал; к счастью не поздно исправить эту ошибку, убрав тип операнда "порт", и добавив тип операнда "адрес, указанный в регистре". Тип операнда "порт", если помните, был всунут для того, чтобы не пропадало значение, освободившееся после отказа от командной работы со стеком. Портов у нас нет, и отказаться от этого типа можно безболезненно (реализовать ввод-вывод в порты можно будет и отдельными командами). Так что теперь типы операндов выглядят так:

bin	hex	type
00	0x0	Константа
01	0x1	Регистр
10	0x2	Адрес в памяти, заданный константой
11	0x3	Адрес в памяти, заданный в регистре

Как видите, я также передвинул тип операнда "адрес, заданный константой" - так попросту логичнее. Это изменение потребует переделки схем Operand selector, Data selector, и, возможно, других - но об этом позже.

До того, как воплощать новые команды и новые регистры в виртуальном кремнии, я доработал ассемблер - программы получаются совсем уж сложные, писать их в опкодах долго и муторно. Изменения и добавления следующие:
- Чуточку поменялся синтаксис: портов больше нет, и символ @ отдан под обозначение меток.
- Для команды SUM добавлен алиас ADD (т.е. можно писать и так и эдак).
- Добавились операнды новых регистров (S0-S7) и все перечисленные выше команды.
- Также, как понятно из вышенаписанного, добавились метки. Метки позволяют не считать размер команд и адресов перехода "на пальцах" - ассемблер делает это сам (для чего пришлось реализовать подобие линковщика). Метки регистронезависимы, т.е. LABEL, label, Label и LaBeL - это одна и та же метка. Как работают метки понятно из нижеприведённого исходника.
- Появилась поддержка комментариев (всё, что после ; считается комментарием).
- Ну и заодно ассемблер выводит портянку команд вместе с адресами и метками, а вывод бинарного представления команд я убрал (он нафиг не нужен).
Вот как будет выглядеть программа, реализующая перезапись самой себя степенями двойки от 2^0 до 2^7:

START:   ;Метка начала выполнения программы
 MOV A,1h ;Нулевая степень двойки (и любого другого числа) - это 1.
 MOV B,0h ;В регистре B будет адрес ячейки памяти, в который нужно записать вычисленное значение
FOR:   ;Метка цикла
 MOV S1,80h ;Ограничение выполнения: седьмая степень двойки, больше целых степеней в восемь бит уже не уместится.
 MOV S2,A ;Записываем текущее значение в служебный регистр для сравнения
 MOV S3,@END ;Записываем в служебный регистр метку, на который нужно будет перейти по условию
 JE  ;Если S1=S2 то переход на метку END
 MOV [B],A ;Записать по адресу, содержащемуся в регистре B значение регистра A
 SHL A,1h ;Левое смещение двоичного числа на одну позицию - это умножение его на 2.
 SUM B,1h ;Увеличиваем значение регистра B
 MOV S3,@FOR ;Адрес метки
 JMP  ;На которую и совершается переход при очередной итерации
END:   ;Выход из цикла
 MOV [B],A ;Последняя запись в память, и конец программы.

Клик для увеличенияЯ специально написал избыточный код, для того, чтобы было легче продемонстрировать следующую возможность ассемблера.
Заметно, что задавать условия переходов несколькими командами неудобно, к тому же такая запись ухудшает читаемость программ. Поэтому для условных и безусловных переходов сделан краткий вариант записи.
Для безусловного перехода, вместо

MOV S3, ADDR
JMP

можно писать

JMP ADDR

Для условных переходов, вместо

MOV S1,VALUE1
MOV S2,VALUE2
MOV S3,ADDR
CMD

можно писать

CMD VALUE1,VALUE2,ADDR

Ассемблер самостоятельно развернёт сокращённую команду, и конечный результат ассемблирования ничем не будет отличаться от варианта с полной записью. Таким образом, вышеприведённую программу можно сократить:

START:
 MOV A,1h
 MOV B,0h
FOR:
 JE 80h,A,@END
 MOV [B],A
 SHL A,1h
 SUM B,1h
 JMP @FOR
END:
 MOV [B],A

Клик для увеличения
Этот код тоже не является оптимальным - например, нет нужды каждый раз делать присвоение MOV S1,80h, да и цикл можно организовать удобнее. Но пока и этого достаточно.
Побаловаться ассемблером и поискать в нём ошибки можно всё там же. Следующую часть постараюсь сделать "железячной", рассказав о реализации логики, способной такие программы выполнять.
Продолжение следует.

Пилим восьмибитный процессор. Часть пятая: ассемблер, тесты, запуск.

Небольшое предисловие, которое должно было быть в самой первой статье по этой теме:
Я понятия не имею, как правильно проектировать процессоры. И как неправильно - тоже. Я просто играюсь в конструктор, делаю ошибки, перекраиваю схемы на лету и наслаждаюсь этим забавным и увлекательным процессом.
Перечитывая предыдущие части, я нахожу в них заметное количество косяков и откровенных глупостей. Скажем, я так и не определился с архитектурой процессора, вроде сначала задумав сделать что-то RISC-подобное, но временами замахиваясь на CISC, и огребая от сложности реализации откатывался обратно. В итоге же получается, что я во многом копирую единственную знакомую мне архитектуру x86.
Поэтому: эти статьи рассказывают о том, как делаю я, а не о том, как надо.

Но окей, перейду к делу.
Поскольку теперь у нас есть контроллер памяти и минимально необходимые для функционирования ядра схемы, нужно попытаться собрать их все вместе и оттестировать. Пока набор инструкций крайне мал, тестирование процессора можно производить так: подать ему на вход все возможные наборы инструкций и посмотреть, как он их обработает. При этом следует учесть, что большая часть ошибочных инструкций не отлавливается - подай мы на вход несуществующую команду или несовместимый набор параметров - процессор поведёт себя непредсказуемо. Но отлов ошибок оставляю на потом, сейчас важнее и интереснее проверить работу на корректном наборе инструкций.
Итак, как выглядит вся схема в сборе:


Не очень-то впечатляет =). Но если раскрыть схемы, и представить всё это добро вместе, получится вот так:


Клик для увеличения

Я не стал раскрывать все подсхемы (в которых, в свою очередь, есть ещё подсхемы) - по-моему и так внушительно. Даже Шмигирилову показать не стыдно.
Несколько комментариев к схеме.
- Выход Execute end сделан на будущее. В дальнейшем он будет сигнализировать о том, что процессор выполнил очередь команд и ждёт новых инструкций. Пока же все инструкции выполняются за один так, так что смысла в подобной сигнализации нет.
- Выход ERR - это зачатки системы контроля ошибок. Сейчас на него подаётся сигнал в единственной ситуации: если попытаться работать с памятью на ввод и вывод одной инструкцией (пример: MOV [addr],[addr]).
- В процессе отладки (который я ещё буду описывать) была найдена незначительная ошибка: в блоке команд не стояло несколько согласующих резисторов, отчего невозможны были операции с памятью. Эта ошибка присутствует на схемах, приведённых в предыдущей статье.
- Индикаторы, если кто ещё не догадался, показывают значения регистров и предназначены только для увеличения удобства.
- Память и ядро работают на одной частоте, несмотря на то, что тактовые генераторы у них разные. Теоретически, ничто не должно мешать работать им на разных частотах (если память будет работать быстрее - нужно будет ввести простенький механизм ожидания выполнения), но logisim не позволяет задавать разные частоты двум элементам.

Пожалуй, можно переходить к тестированию, которое, как решено выше, должно заключаться в передаче процессору всех вариантов корректных команд. Такой набор можно сгенерировать вручную, а можно - и даже нужно - написать ассемблер, переводящий читаемые команды в машинный код.
На реализацию этого ассемблера на PHP ушло около часа, побаловаться можно здесь Meighty assembler (название "Meighty" у меня получилось из объединения слов might и eight, так я и назвал свой процессор). Команды вводить в чёрное окошко, жать compile. При удачной трансляции слева от окна появится двоичный байткод, снизу - его шестнадцатеричное представление, которое можно копипастить в logisim (буквально, его компонент ОЗУ корректно воспримет вставку таких данных), при ошибке выдастся описание проблемы.


Клик для увеличения
Ассемблер имеет intel-like синтаксис, регистр значения не имеет, все лишние пробелы игнорируются. Числовые значения задаются только в шестнадцатеричной системе счисления, десятичная и двоичная, возможно, будут сделаны потом. Операнды перечисляются через запятую, и задаются следующим образом:
- константа: значениеH, например 10H, FDH, 7h;
- регистр: идентификатор регистра от A до H;
- порт: @номер портаH, например @03H, @88h;
- адрес в памяти: [адресH], например [12h], [FFH], [0H];
Ассемблер пытается отлавливать ошибки, как синтаксические, так и логические, можете поиграться. Комментарии не реализованы. Порты, как понимаете, тоже отсутствуют, выполнение команд чтения-записи для них смысла не имеет.
Пример программы (абсолютно бессмысленной, её цель только продемонстрировать работу):
MOV A,10h
MOV B,A
SUM B,3h
MOV [20h],B
MOV C,[20h]
SHL [20h],2h
XOR A,[20h]
NOP
и т.д.
Меня КРАЙНЕ ломает делать гифку, которая продемонстрировала бы, что эта, да и все другие допустимые программы, выполняются корректно. Гифкоклепание займёт не меньше часа, так что предлагаю просто скачать logisim, взять мою схему и посмотреть всё самим.

Что дальше? Примерно вот что:
- реализация восьми дополнительных служебных регистров вдобавок к восьми имеющимся, которые останутся пользовательскими. Служебные регистры будут предназначены, прежде всего, для организации работ программ в памяти (требуется разделять код и данные - значит нужны аналоги CS и DS) и возможного её увеличения (для адресации за пределами двух килобайт можно ввести сегментацию, тогда понадобится регистр, указывающий на текущий сегмент), а также для выполнения команд условного перехода (команда будет сравнивать два определённых регистра), ну и давно задуманный флаговый регистр. Возможно - счётчик (это будет зависеть от того, как я реализую циклы).
- стек. Его я, как и было задумано ранее, всё-таки реализую на отдельной схеме - пусть будет хоть какое-то значимое отличие от x86. На реализацию четырёх стековых команд (стандартные POP, PUSH, не очень стандартная PEEK и совсем не стандартная POKE) понадобится всего один опкод (т.к. параметр у этих команд будет всегда один, два неиспользуемых бита можно отдать под команду).
- команды условного и безусловного перехода.
- дополнительные команды обработки данных (SUB, MUL, DIV, NOT).
- доработка ассемблера.
- отлов и обработка ошибок.
- ASCII-терминал.

Дальше можно будет думать о простой системе прерываний (например, наборе подпрограмм, зашитом в ПЗУ), но я уже не уверен, что меня на это хватит.
Продолжение, скорее всего, следует.

Пилим восьмибитный процессор. Часть четвёртая: подготовка ко взлёту.

Я, наконец-то, смог снова вернуться к своей разработке. Чувствую, что она "не отпустит" меня, пока не доведу дело до конца.
В этой части я расскажу о довольно значительных изменениях и доработках в схеме процессора. Их уровень уже таков, что процессор выполняет несложные программы; ещё немного - и надо будет писать ассемблер, большие программы в машинных кодах писать очень неудобно.

В прошлой записи я остановился на блоке регистров. Он вполне закончен, к нему возвращаться, пока что, нужды нет.
Следующим логичным шагом стала бы реализация стека. Сделать его оказалось не так уж сложно, но вот когда я попытался с ним работать, возникли затруднения.
Если помните, я решил организовать работу со стеком посредством обычных операндов, вместо того, чтобы использовать стандартные команды работы со стеком PUSH и POP. Такое решение приводило к следующей логике работы: ничего не мешало брать или помещать данные в стек, но изменять их оказалось сложно. Вместо одной операции (и, соответственно, одного такта) получалось три: взять значение, изменить значение, вернуть значение. Хотя текущая схема позволяет оптимизировать порядок исполнения (изменение может производиться одновременно со считыванием либо записью), всё равно это требовало какого-то механизма синхронизации, что было неудобно и усложняло схему.
После некоторых раздумий я отказался от идеи подобной работы со стеком, и решил реализовать классические PUSH и POP.
Это, конечно, лишило меня целых двух опкодов (на самом деле, я думаю обойтись одним), однако такое решение позволило внести упрощения в логику работы процессора и его подсхем. Например, теперь схема определения количества параметров команды OpC сократилась в разы (два десятка элементов против нескольких сотен ранее) - поскольку теперь у каждой команды одно и то же количество параметров независимо от их типа:



Клик для увеличения
Освободившийся номер типа 10b (ранее обозначавший стек) я думаю отдать под операции ввода-вывода в порты (ага, я уже думаю над тем, чтобы пристроить процессору простенький ASCII-терминал и, возможно, клавиатуру).
Соответственно, была переписана таблица опкодов, у подсхем были изменены названия входов. Переделка оказалось несложной.
Поскольку теперь работа со стеком отодвинулась, следующим шагом становилась реализация полноценной работы с памятью. Если помните, контроллер памяти был реализован несколько в черновом варианте: он просто читал память по порядку, парсил содержащиеся в ней команды, но не умел изменять адресацию или менять значения.
Чтобы понять, какие доработки потребуются, перечислим операции, поддержка которых нужна:
1) Переход по адресу (JUMP). Программа выполняется-выполняется, появилась инструкция перехода - произошёл прыжок по указанному адресу, выполнение пошло оттуда.
2) Чтение по адресу (GET). Взять значение по адресу, при этом не совершая перехода.
3) Запись по адресу (SET). Аналогично, только значение записывается.
Одновременное выполнение операций GET и SET (взять значение по одному адресу, записать в другой) вполне реализуемо. Но в архитектуре x86, например, команда MOV [addr1],[addr2] не поддерживается - по той же причине, по которой я отказался от командной работы со стеком: выполнение такой операции займёт минимум два такта и усложнит логику. Поэтому пересылка данных из памяти в память реализуется только через буфер; возможно в других архитектурах однокомандная пересылка реализована, но я и x86 знаю плохо, что уж о говорить других архитектурах.
По этой причине имеем всего три новых операции. Реализуются они вот такой схемой:


Я выкинул псевдоадресный регистр и переделал всё набело. Логика такая: есть три ключа JUMP, GET, SET и восьмибитные контакты: адрес перехода Address, значение записи Set Value, считываемое значение Get Value. Ну и тактовый генератор присоединён к схеме памяти (это нужно для записи). Также был изменён интерфейс схемы памяти: вместо одного синхронного порта ввода/вывода с состоянием, переключаемым сигналом на отдельном входе, использована схема с двумя раздельными портами (это не обязательно, но упрощает конструирование).
Сигнал на JUMP изменяет значение счётчика указателя адреса на значение, считанное со входа Address.
Сигналы на GET или SET отсоединяют счётчик указателя адреса от тактового генератора, вместо этого подавая на адресный вход A схемы памяти адрес из Address. Для GET на этом всё заканчивается - на выходе Get Value всегда значение, заданное по адресу в A. SET же подаёт сигнал на порт str, и соединяет контакт Set Value с портом чтения D. При изменении значения тактового генератора значение обновится, при этом выходы GET/SET должны будут "погаснуть" (поскольку они контролируются "снаружи" схемы, требуется синхронизация, к этому вопросу ещё вернусь), и указатель памяти тут же перескочит на значение из счётчика.
Всё просто. Да, согласующие резисторы нужны поскольку на соответствующих контактах при дальнейшем подключении к процессору могут быть несогласованные значения.

Теоретически, для реализации Тьюринг-полного компьютера уже всё есть с избытком, осталось только запилить командный блок - собственно, ту штуку, которая будет складывать, делить, пересылать и умножать. Но если подумать: командный блок должен бы работать с абсолютными значениями, а не адресами/номерами. То есть сначала абсолютные значения из этих адресов/номеров нужно получить.
В прошлой части я рассказывал, что блок Data selector (DS) не был готов. Сейчас, после того как окончательно (ну я надеюсь, что окончательно) определена структура команд и готова "периферия", вроде блока регистров и контроллера памяти, его уже можно дорабатывать, благо дорабатывать там совершенно нечего. Вот его простая схема:


Семь транзисторов, вот и весь селектор. Логика простая: в зависимости от типа данных подключаем вход чтения к соответствующей схеме, подавая этой схеме на вход требуемый ей параметр (памяти - адрес, регистрам - номер). Выход GET активировать, когда нужно получить значение из памяти.

После того, как становятся известны абсолютные значения параметров, с ними уже можно производить операции. Операций, напомню, на текущий момент, задано шесть: NOP, MOV, XOR, SUM, SHL, SHR.
Реализовать сами эти операции несложно, более того - соответствующая логика уже есть в logisim. Несколько сложнее добиться того, чтобы операция и запись её результата происходили в один такт. Для этого нужно избегать всяких буферных приёмников, и писать сразу по назначению.
Рассмотрим, как реализованы команды MOV и SUM. Эти две команды выбраны потому, что в их реализации есть различие, которое я хотел бы показать. Точнее, отличия есть только у MOV, остальные команды реализованы практически идентично, за исключением базового для них логического преобразования. Да, ещё есть NOP, но его, надеюсь, показывать не нужно =)
Итак, MOV:


Режим работы команды MOV зависит от того, что и куда перемещается. В зависимости от типа приёмника, указанного на одном из входов REG, PORT или MEM, схема подключается к блоку регистров, контроллеру памяти или...
Стоп, стоп, а что с портами? Портов нет, и пока наш процессор беспортовый, контакт PORT присутствует постольку-поскольку. На будущее, так сказать.
Окей, в зависимости от того, идёт пересылка в регистр или память, коммутируем соответствующий выход со входом ADDR (считаем, что на нём либо номер регистра, либо адрес памяти) и подаём на выход значение со входа INPUT VALUE2 (соответствующее второму параметру команды MOV). Почему не первому? Потому что первый параметр - это приёмник, и на значение его плевать. Соответственно, вход INPUT VALUE1 сделан для красоты, не больше.
Вход РАЗРЕШЕНИЕ разрешает передачу такта дальше по схеме. Поскольку и память, и регистры обновляются только при переключении такта, это гарантирует, что без сигнала на этом порту данные не изменятся. Если же вход неактивен, согласующий резистор препятствует возникновению ошибочных значений в схеме, обнуляя выходной байт (который не имеет смысла без передачи такта).
Ну и логический элемент ИЛИ помогает избежать ошибки, когда ни на один из входов REG, PORT или MEM не подано значение. Дело в том, что блок регистра спроектирован так, что при ошибочном значении на входе Write Selector почему-то считает это значение единицей. Я не разбирался, баг это, или фича, но приводит это к тому, что запись происходит во все регистры сразу. Была мыслишка оставить такое поведение как фичу, но до окончательной доработки схемы от мысли этой я отказался.
Теперь SUM:


Отличие очевидно - в схеме используются оба входных значения. А ещё у этой схемы есть выход ПЕРЕНОС, на который подаётся единица, если результат сложения не умещается в байт (он пока есть только у SUM, но некоторые другие команд тоже будут иметь подобный выход).
Все команды я объединил в большой командный блок (далее будет помечен, как CMD), куда также отправилась схема Opcode selector (OS):


Клик для увеличения
Несмотря на обилие проводов, разобраться в ней довольно легко - входы блоков команд параллельно подключены к шине, в один момент выполняется только одна команда, выбранная схемой OS. Неактивные команды подают на все выходы нули, поэтому нужное значение для адреса\номера и данных можно выбрать логическим ИЛИ.
Можно заметить, что выходной такт инвертируется по отношению ко входному. Это нужно для того, чтобы всегда было различие на полтакта между командным блоком (выступающим в роли источника данных) и получателем (блоком регистров или памятью) - тогда получатель сможет обновить значение до того, как оно изменится в командном блоке. Того же результата можно добиться, изменив параметры получателей; logisim позволяет использовать даже не такты, а ключи (например, регистр будет менять значение на поданное не при смене такта, а пока активен сигнальный вход), но это чит. Это не значит, что я совсем не собираюсь этим читом пользоваться - но пока можно без него - буду без него.
Я, в общем-то, не уверен, что командный блок не содержит ошибок, и не будет переделываться в дальнейшем - но это уже зависит от результатов полноценного тестирования процессора в полной, так сказать, сборке.

Окей, все компоненты для запуска готовы, осталось только правильно соединить их - и можно пытаться пускать примитивные программы. Но об этом - в следующей части.
Продолжение следует.

Пилим восьмибитный процессор. Часть третья: ядро и блок регистров.

Эта часть будет очень короткой, не смотря на то, что должна описывать самую сложную часть процессора. Дело в том, что как раз на проектировании ядра я остановился.

Что такое ядро, и чем оно должно заниматься? Чёткого ответа на оба вопроса нет, но обобщённо - это именно та часть схемы, которая занимается выполнением инструкций. Ему на вход подали команду - он отдал результат на выход.
Со входом на данный момент более-менее порядок: контроллер памяти успешно читает и парсит команды, подавая их на вход ядру. Что дальше?
Взглянем на набросок схемы, которым представлено текущее видение ядра:


Клик для увеличенияУ процессора четыре входа: OPCODE - на неё подаётся опкод команды (который, напомню, состоит из команды и указателя типов данных переданных параметров), PARAM1 и PARAM2 - соответственно, первого и второго параметра команды и execute - сигнальной линии выполнения. Когда на входе execute ноль, то остальные контакты отсоединяются, и процессор ничего не делает. Когда на этот вход подаётся сигнал, процессор должен выполнить инструкцию.
Для выполнения нужно проделать следующий алгоритм:
1) Определить команду.
2) Определить количество параметров команды.
3) Определить тип каждого параметра.
4) Определить допустимость параметров.
5) Получить данные по параметрам.
6) Выполнить инструкцию над полученными данными.
Плюс, на каждом этапе нужно проверять корректность всего и вся. Самое очевидное - четвёртый пункт, который должен, скажем, отсечь команду MOV 1,2 (перемещение числа в число).
Часть пунктов этого алгоритма уже решена, или решается достаточно легко. Так количество параметров определяет схема Operand counter, мы можем поставить её в ядро, или же брать уже полученное значение из парсера команд (оба решения, внезапно, правильные).
Определить же саму команду призвана схема Opcode selector (обозначена, как OS), она очень простая, и похожа по устройству и действию на счётчик, что я делал самым первым:
Определение типа параметров тоже элементарно, и схоже по устройству (схема Operand selector, обозначена OpS):
Не вижу смысла разбирать эти схемы подробно, их строение очевидно.
А вот дальше начинается интересное. В зависимости от типа параметров одна и та же команда может отрабатывать совершенно по разному. Приведу примеры, сделав допущение, что на данном моменте ошибочные инструкции, вроде вышеупомянутой MOV 1,2 отсеяны:
- Команда работает с регистрами (пишет в регистр, читает в регистр, или и то и другое), допустим это команда XOR A,B. Процессор должен взять значение регистра A, значение регистра B, выполнить над ними XOR, записать результат обратно в A. Четыре действия.
- Команда работает со стеком, допустим XOR S,10h. Взять значение стека, сделать XOR, записать в стек. Три действия.
- Команда работает с памятью (это самое интересное), допустим XOR [10h],[0Fh]. Считать значение по адресу 10h, считать значение по адресу 0Аh, выполнить XOR, записать значение по адресу 10h. Снова четыре действия, которые, между прочим, совсем не атомарны - контроллеру памяти нужно перейти по адресам, что займёт три такта (ладно, два, если оптимизировать инструкцию и читать параметры в обратном порядке).
А ещё есть комбинации этих параметров - память и стек, регистр и константа, стек и регистр...
Задача не выглядит сложной: бери значения, вписывай в буфер, выполняй операцию, пиши обратно. Но: всё это потерянные такты процессора, а значит - потерянное быстродействие. Что делать? Работать со значениями напрямую, без буферов.
Получать прямые значения, подавая их на обработчик команд будет схема Data selector (помечена, как DS). Она ещё не готова, поэтому её внутренности я показывать не буду (там четыре транзистора и всё), но опишу принцип действия.
DS подключена ко всем подустройствам ввода-вывода, на вход её подаются параметры команд и типы этих параметров. В зависимости от типа, DS переключается между подустройствами, подавая им номера, адреса, или чего ещё они требуют для возврата значения. Возвращённое значение отдаётся в DS, которая тут же возвращает его на свой выход. Вся операция занимает полтакта (за исключением моментов, когда подустройство не может сразу вернуть данные). Каждый Data selector ставится за входами параметров, таким образом производя их преобразование в абсолютные значения.
В чём подвох?
Возьмём, к примеру, регистры и команду MOV A,B. Для её выполнения нужно получить данные сразу по регистрам A и B, и тут же изменить значение A (поскольку команда, очевидно, будет выполнена моментально). Возникает что-то наподобие коллизии, которая, в лучшем случае, решается буферизацией значений, а, значит потерей тактов.
Впрочем, обойти этот косяк можно проще: нужно только спроектировать подустройства так, чтобы они умели отдавать сразу два значения. Регистр - значение двух регистров, память - значение двух адресов (это вполне решаемая задача, и очень интересная, я вернусь к ней в конце статьи), стек... ну, стек это отдельная песня.
На данный момент именно так у меня спроектирован блок регистров. Он состоит из двух схем: Registry I/O и Registry I, они так и обозначены. Первая умеет как читать значения заданного регистра, так и писать, вторая - умеет только читать, но действуют они независимо друг от друга. Посмотрим на их устройство.
Registry I/O:

Клик для увеличенияRegistry I:

Клик для увеличенияВся разница в том, что у Registry I отсутствует блок изменения регистров, поэтому разберу только устройство Registry I/O.
С входом Read Selector всё понятно - там порядковый номер регистра, значение которого надо выводить на выход Value. Схема Registry Selector (RS), в зависимости от этого номера подаёт разрешающий сигнал на соответствующую ногу, подключённую к выходу того или иного регистра:

Клик для увеличенияС записью интереснее, за это отвечают аж четыре входа:
- Store: значение, которое надо писать в регистр.
- Write Selector: порядковый номер регистра, в который это значение надо писать (работает аналогично Read Selector).
- Write: флаг, разрешающий запись (иначе значения регистров будут постоянно обновляться, хотим мы этого, или нет).
- Такт: флаг, переключение которого приведёт к записи значения в регистр.
Таким образом, схема позволяет одновременно читать значение из любого регистра и писать значение в любой регистр - то, что и требуется.
Дополнительно данные с каждого регистра подаются на отдельный выход, уходящий в схему Registry I, которая, в свою очередь, тоже не терминирует выходы, таким образом, позволяя подключать параллельно несколько копий схем чтения (или просто датчиков, как это сделано у меня). Почему не сделать вторую схему пишущей, чтобы и писать сразу можно было в два регистра? Потому что а) придётся решать коллизии в ситуации, когда запись на обеих схемах производится в один и тот же регистр б) это всё равно не нужно, т.к. запись в регистр - атомарная операция, и может быть произведена только одна такая операция в один момент времени.
Вот и всё, собственно. Напоследок несколько мыслей:
Можно заметить, что у ядра свой собственный тактовый генератор, и он может работать с собственной частотой (обычно ядра работают быстрее периферии). В этом процессоре это ничего не даёт, но именно на этом принципе можно реализовать очень много интересных вещей. Например, пока контроллер памяти получает очередной набор инструкций (что занимает у него от 1 до 3 собственных тактов), ядро может выполнять какие-то другие операции. Или же можно приделать ядру немножко своей памяти, работающей на его частоте, и в работать через неё - это и называется кешем первого уровня. Этим варианты не ограничиваются, но дальше уже идёт довольно высокий пилотаж.
Как получить из памяти значение сразу по двум адресам? Один из способов я показал на примере блока регистров - а ОЗУ - это тот же самый блок регистров. Второй способ - блок предсказаний: можно сделать схему, которая предполагает, что оператор команды - это всегда адрес в памяти, и тут же буферизует его, пока процессор выполняет предыдущую команду. Но блоки предсказаний, используемые в процессорах - это пилотаж ещё более высокий. Нам бы для начала разобраться с куда более приземлёнными вещами =).
Пока что всё. Продолжение, надеюсь, следует - как только на него появится время.

Пилим восьмибитный процессор. Часть вторая: разбор команд и управляемый счётчик.

Итак, у меня есть примерное представление о том, каким должен быть процессор, какие данные он будет получать на вход, какие данные будут у него на выходе, но довольно мало понимания того, как он устроен внутри. Классический чёрный ящик.
Но любой программист знает: для выполнения сложной задачи её нужно разбить на маленькие и решать по порядку. Забегая вперёд скажу: рисование логических схем - это то же программирование, только вместо участков кода используем логические преобразования, вот и всё.
Я начал с памяти. Её, как помнится, 2048 бит - 256 блоков по байту. В Logisim есть встроенный элемент "ОЗУ", в котором настраиваются как разрядность данных, так и разрядность адреса.

Да, пока не забыл: я не стал морочиться, реализуя всю логику на базовых элементах (которых, как вы знаете, если читали предыдущие посты, три - И/ИЛИ/НЕ). Та же ОЗУ (дальше я продолжу называть её проcто памятью, что не совсем верно технически, но зато привычно) состоит из регистров, каждый из которых имеет свой адрес (т.е. у меня 256 регистров). Регистры состоят из триггеров, каждый из которых хранит состояние одного бита (так что у меня - восемь триггеров в регистре). Каждый триггер, в зависимости от типа, можно реализовать различной логикой, например T-триггер реализуется восемью элементами ИЛИ-НЕ. Итого: 16 простейших элементов в триггере, восемь триггеров в регистре, 256 регистров - итого 32768 элементов! И не будем сейчас о том, что сами элементы эти тоже состоят из транзисторов, иначе это число возрастёт ещё на порядок.
В общем - не мучить себя и вас, использовать готовое. В конце концов, когда мы программируем, то не используем только базовые команды, а работаем и с функциями языка - ну так и тут то же самое.

Чтобы исполнить программу, нужно знать адрес в памяти, на котором она начинается. Поскольку до операционных систем и прочих сложностей моему процессору пока далеко, считаем просто: исполнение начинается с первого блока (т.е. блока с адресом 0x0). Теперь нужна собственно программа, хоть самая простенькая, чтобы было на чём тестировать работу. Может показаться, что я забегаю вперёд - ещё ничего нет, а я уже что-то тестировать собрался - но это не так, с пустой памятью тоже не особо потестируешь.
Самая простая команда, пришедшая мне в голову - MOV B,1Fh. Транслировать её в двоичный (а затем и в шестнадцатеричный) код не составляет никакого труда в уме (я не издеваюсь) 00010100 00000001 00011111 -> 0x14 0x1 x1F. С помощью встроенного в программу редактора вношу эти значения в память:


...а потом трах-дибидох: и у меня уже готовая схема контроллера памяти:


Не стану я расписывать, как составлял эту схему, просто дам результат, и покажу, как он работает. Оговорюсь: на самом деле это ещё не контроллер, хотя бы потому, что схема работает только на чтение, и, к тому же, выполняет заодно роль парсера команд. Но я уже привык думать о ней, как о контроллере, и в будущем именно эту задачу схема будет выполнять.
Что сейчас делает контроллер? Он читает память до тех пор, пока не будет считана одна команда (опкод и параметры). При этом контроллер должен учитывать то, сколько байт параметров следует за опкодом (например XOR A,B - два параметра, XOR S,[10h] - один параметр, а команды XOR S,S или NOP не имеют параметров вообще). Считанные данные запоминаются в промежуточный буфер, а после того, как считывание закончится, контроллер отдаёт их в ядро процессора и ждёт от него дальнейших инструкций. Да, ещё нужно не забывать про такие мелочи, как управление навигацией по памяти.

Вход схемы - один контакт, по которому передаются те данные из памяти (с выхода В), на который указывает значение на контакте A (для памяти это входной контакт, для контроллера - один из выходных). При включении схемы адрес в A - 0x0, соответственно выход - 0x14h. Что с этим числом происходит дальше?
Оно попадает в схему Buffer selector (на схеме обозначена как Bs). Эта схема определяет в каком именно из буферов нужно запомнить текущее значение памяти. Буферов в схеме три, поскольку максимальное количество операндов в команде - два (и один буфер на саму команду); если в дальнейшем у меня появятся команды, работающие с большим числом операндов, количество буферов может быть легко расширено.
Вот как выглядит схема Bs внутри:


На вход Operand counter подаются два бита, которыми закодирован номер операнда (откуда берутся эти биты - будет видно дальше); на первом шаге обработки там всегда будет ноль. Считаем, что 0 операнд - это сам опкод, 1 операнд - первый параметр команды и т.д. Схема Bs, как видно, занимается тем, что в зависимости от числа на входе даёт сигнал на тот или иной выход.
Каждый из выходов подключён к соответствующему буферу (буфера реализованы восьмибитными элементами "регистр"). Есть сигнал на входе "включение" - регистр запоминает то, что ему подано на вход D - а туда подведён контакт с данными из памяти.
Можно заметить, что у схемы Bs есть неиспользуемый выход. Он отвечает за ошибку и сигнал на нём возникает, когда на вход схемы подано невозможное число параметров (сейчас это три). Программно такую ошибку воспроизвести не получится, но при проектировании и отладке "железа" подобные ходы попросту необходимы.
Но вернёмся к контроллеру. Что происходит после того, как в буфер команды записалось значение? Очевидно, что нам нужно проверить, есть ли у только что записанной команды параметры, и сколько их.
Этим занимается схема Operand Сounter (на схеме обозначена OpC). Как она это делает - просто. А вот разобраться - чуть сложнее.
Для начала я составил в Excel список всех возможных операндов примерно в таком виде (на самом деле этот список полностью не нужен - достаточно взять один операнд, составить таблицу для него, а коды остальных операндов будут отличаться одним-двумя переставленными битами):


Клик для увеличения
Затем я по этому списку построил схему логических переключателей, которая и находится внутри OpC. Всю схему я приводить не буду - для шести команд там около сотни логических элементов, и это при том, что я пользовался встроенными в Logisim возможностями подключать к одному элементу до восьми входов (если бы этой возможности не было, мне бы пришлось использовать восемь аналогичных элементов, вместо одного). Вот часть участка схемы, определяющая количество параметров для команды NOP (исключительный случай - всегда ноль параметров) и различных вариаций команды MOV:


Клик для увеличения
Пояснение по вон тем загогулинкам, похожим на пружинки - это согласующие резисторы. Их задача - согласовывать значение на контакте, если оно не определено; перед резисторами стоят транзисторы n-типа, которые при закрытом вентиле обрывают цепь (выдавая в неё плавающее, неопределённое значение), при открытом - заданную константу. Поскольку логическое ИЛИ не умеет работать с плавающим значением, нам нужно привести его к нулю - вот тут и нужно согласование.
Безусловно, эту же схему можно реализовать чуть проще - но я пока не стал заморачиваться, она, скорее всего, так или иначе претерпит изменения при доработке процессора и добавлении новых команд.

На выходе из OpC стоит расширитель битов, дополняющий нулями двухбитное значение количества операндов до восьмибитного, например 10 -> 00000010. Зачем он нужен?
Он не нужен. Я поставил его на будущее - когда количество операндов разрастётся, и их перечисление двумя битами уже не зашифруешь.
Ладно, куда дальше идут эти восемь бит? В счётчик, незамысловато названный for:


Может показаться странным, но именно это самая сложная часть всей схемы. Дело в том, что при его создании требовалось решить сразу две проблемы:
1) Логический счётчик в Logisim может считать до жёстко заданного количества тактов (о тактах я скажу чуть ниже). То есть задали ему верхний лимит в 4 - он и будет считать 0,1,2,3,4,0,1,2,3... Требовалось же сделать лимит счёта изменяемым. Первоначальный черновой вариант был "деревянным" - несколько счётчиков с заранее выставленными лимитами, переключение меж которыми происходило при необходимости, однако потом я придумал универсальный счётчик.
2) Счётчик должен работать на полтакта опережая такты считывания из памяти для того, чтобы сразу же сигнализировать о окончании счёта (иначе это может привести к паузе в один такт между окончание заполнения буферов и передачей значений на обработку в ядро процессора.

Как решены эти задачи - видно на схеме. Счётчик qt дополнен регистром en, который хранит поданное ему на вход D значение лимита счёта (поскольку значение на входе всё время обновляется, запоминать его нужно только после окончания предыдущего счёта). После каждого такта значения в регистре и на выходе счётчика сравниваются компаратором, и если значения равные - на выход "Конец цикла" подаётся сигнал, счётчик сбрасывается, а через полтакта в en грузится новое значение лимита. Ну а на выходе "Выход счётчика" - собственно текущее значение счётчика, которое подаётся уже на вход схемы Bs (предварительно от значения отбрасываются шесть старших битов).
Цикл замкнулся, в буферах - команда с параметрами, на выходе "Execution" - единица, а это значит, что ядро CPU может обрабатывать значения.

Да, тактовый генератор и указатель адреса (они в левом нижнем углу схемы). ТГ бесконечно переключает импульсы (1->0->1->0), которые подаются на вход некоторых элементов, и используются ими как сигналы для обновления значений. Например тот же счётчик по сигналу ТГ увеличивает значение, а регистр - запоминает новое значение, поданное на один из входов. Подключив несколько элементов к одному ТГ мы их синхронизируем, вызвав одновременное переключение состояний.
В реальных микросхемах никакая последовательность взаимосвязанных событий не происходит одновременно, всегда есть задержка на распространение сигнала. Но поскольку сигнал распространяется со скоростью света, этой задержкой в большинстве случаев можно пренебречь, считая синхронизацию абсолютной. Исключения есть, но в Logisim, который симулирует логику, но никак не физику, мы с ними вряд ли столкнёмся - в инструкции что-то упоминалось насчёт таких случаев, но, в целом, вывод именно такой.
Участок схемы, помеченный как "Указатель адреса" представляет собой счётчик (он, собственно, считает адреса) и регистр, хранящий текущее значение адреса. Снова возникает вопрос - а зачем регистр, если значение всегда в счётчике? А затем, что меняя значение этого регистра, мы изменим и значение счётчика, а, значит, перейдём на новый адрес памяти. Хотя в текущей схеме этот регистр никак не используется (вообще-то это адресный регистр, который должен находиться в ядре CPU, но поскольку ядра ещё нет, регистр сделан вот так), он обязательно пригодится в будущем.
Ну и напоследок, давайте посмотрим, как эта схема читает память (я немножко изменил подключения для наглядности). Разбираемый набор команд: MOV B,0Fh; MOV S,A3h; MOV [1Ah],10h (потом гифка зацикливается):


На этом пока всё, про блок регистров и наброски ядра, пожалуй, лучше рассказать отдельно. Продолжение следует.

Пилим восьмибитный процессор. Часть первая: теория.

Вступление к посту.
Изначально я не хотел разбивать статью на несколько частей, ограничившись одним подробным постом только по окончанию работы. Но обстоятельства вынуждают меня переключиться на другую задачу, так что я решил просто сбросить сюда информацию о том, что уже сделано, иначе наверняка что-то забуду (это не учитывая того, что я УЖЕ забыл).
К тому же объём информации предполагается таким, что его всё равно лучше разбить на несколько частей.
Наслаждайтесь!

---

Немногим ранее я рассказал о том, как меня увлекло проектирование логических схем в программе Logisim. Потренировавшись на простых схемах, я решил разработать процессор. И чтобы всё по настоящему, с исполнением машинного кода и полнотой Тьюринга.
Для тех, кто не в теме - краткий ликбез. Процессор в электронике - устройство, которому на вход подаются команды и, иногда, их параметры (как правило, закодированные последовательностью битов), на выходе получаются результаты выполнения этих команд над этими данными. Пример простейшего процессора - схема, выполняющая инкремент/декремент поданного на вход значения в зависимости от наличия сигнала на другом входе.
Полнота Тьюринга - свойство исполнителя (т.е. того же процессора) вычислять результат абсолютно любой вычислимой функции. То есть даже простейший тьюринг-полный процессор (если ему предоставить ресурс в виде бесконечной памяти) способен посчитать всё не хуже каких-нибудь пентиумов - только программа будет сложнее, и её исполнение займёт больше шагов. Пример того самого тьюринг-полного процессора - машина Тьюринга, придуманная знаменитым английским пидорасом великим английским математиком Аланом Тьюрингом; дабы не сверзиться в пучину всяких теорий вычислимости отправлю вас в Википедию. Впрочем, если вы пропустите этот момент - ничего страшного не случится, надеюсь - я постараюсь писать так, чтобы понятно было даже человеку, далёкому от IT (но людям, знакомым с информатикой понять будет легче).

Началу проектирования в Logisim предшествовали обширные прикидки логики на бумаге. Нужно было решить следующие вопросы:
- разрядность процессора.
- набор команд.
- архитектура.
- порядок следования данных (big-endian или little-endian).
- и ещё куча всего, что просто не приходило сразу в голову.

Сначала я хотел делать четырёхбитный процессор, который, в принципе, покрывал бы ту же машину Тюринга: ну а то, четырёх бит достаточно для операций из 16 команд над алфавитом в 16!
Но я хотел сделать не простенькую игрушку, а что-то, работающее с архитектурой фон Неймана.

И снова ликбез.
Большинство современных компьютеров реализуют именно архитектуру фон Неймана. В ней программа (набор команд) хранится там же, где и данные, которые программа (вернее, процессор, эту команду исполняющий) обрабатывает. То есть программа сама должна определять, где у неё код, а где - данные, и что из этого и в каком виде надо скармливать процессору. Эта архитектура гибкая (например, программа может сама менять свой код) и просто реализуемая, но, при этом, подвержена ошибкам, вроде переполнения буфера (одна программа бесконтрольно пишет много данных, они не умещаются в отведённый участок памяти, залезают в код другой программы, которая, при выполнении вылетает - или запускает чужой код).
А есть ещё Гарвардская архитектура, в ней код и данные хранятся раздельно. Представьте, что у вас в компе две отдельных устройства ОЗУ, которые друг с другом не взаимодействуют и не пересекаются. И когда программа запускается, её исполняемый код грузится в одно устройство, а данные, с которыми она работает - в другую. Там уже никаких переполнений буфера (по крайней мере, они не должны быть так тривиальны, как в фон Неймане), да и исполнение происходит быстрее (процессору не нужно ждать данных, следующих за инструкцией, они всегда доступны на одном из устройств) - но с гибкостью там никак, да и по реализации она сложнее в несколько раз, в зависимости от подхода. Тем не менее, эта архитектура используется во встраиваемых устройствах, где скорость и надёжность важны, а гибкость - нет.

Реализовать четырёхбитный процессор с архитектурой фон Неймана, конечно, можно. Но возникает слишком уж много ограничений.
Например, если принять, что размер команды равен размеру данных (т.е. тем же четырём битам), то получаем ограничение в 16 инструкций, из которых только минимальный набор инструкций перехода по памяти займёт половину. Затем, процессор должен определить, что обозначают данные, которые ему передали. Константу? Номер регистра? Адрес в памяти? То есть после команды ещё должно быть что-то вроде маркера типа данных - а это ещё по два бита на параметр. И, наконец, четыре бита ограничивают максимально адресуемую память всего 64 байтами (16 адресов по 4 бита).
Всё это решаемо. Можно, например, разграничить размер машинного слова: командное слово считать равным восьми битам, а команды брать четырёхбитные. И адреса тоже брать не четырёхбитные, а восьмибитные. И ещё маркеры типов данных куда-нить пристроить... И дрючиться, высчитывая смещения в памяти, вместо работы с аккуратными идентичными последовательностями.
Но почему бы сразу не сделать восемь бит, благо в Logisim разрядность элементов переключается на лету? На сём и остановился.
Кстати, первый процессор от Intel 4004, хоть и был четырёхбитным, мог адресовать 640 байт памяти, а команд в нём было аж 46. Впрочем, это достигалось тем, что он, как раз, был построен по Гарвардской архитектуре - там с этим проще.

С набором команд тоже пришлось подумать. Делать много команд - усложнять разработку процессора, делать мало команд - усложнять разработку под процессор. Так что я исходил из того, что нужно реализовать самые основные команды, а потом, по мере необходимости, добавлять остальные.
Затем я посмотрел, с чем будут работать команды. Что будет в моём процессоре:
- Восемь восьмибитных регистров, от A до H (один из которых флаговый, один - адресный, остальные пока решено сделать регистрами общего назначения).
- Память (восьмибитный процессор адресует 256 адресов по восемь бит - итого аж два килобайта).
- Отдельный стек (об этом ниже).
- Ну и просто числа (константы).
Изначально - четыре типа данных, на перечисление которых нужно два бита. Если у каждой команды по два параметра (например, MOV A,B), то получается, что нужно засунуть набор "команда"+4 бита в пространство, кратное восьми битам. Брать шестнадцать бит - несколько избыточно, восемь - как-то маловато (четыре бита на команду - не от этого ли я хотел убежать?).
Но, тем не менее, я выбрал именно восьмибитный размер опкода. Я рассудил так: вряд ли меня хватит для реализации более чем 16 полноценных команд. А если хватит - расширить размер опкода можно будет без проблем.

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

Код (hex)	Мнемоника	Действие и параметры
0x0	NOP	Пропуск такта.
0x1	MOV	Копирование (не перемещение!) значения в приёмник. MOV [R|S|M],[R|S|M|V]
0x2	XOR	Побитовый XOR значений. Результат помещается в приёмник. XOR [R|S|M],[R|S|M|V]
0x3	SUM	Суммирование значений. Результат помещается в приёмник. SUM [R|S|M],[R|S|M|V]
0x4	SHL	Левое смещение приёмника на указанное количество позиций. SHL [R|S|M],[R|S|M|V]
0x5	SHR	Правое смещение приёмника на указанное количество позиций. SHL [R|S|M],[R|S|M|V]

Обозначения: R – регистр (значение указанного регистра), M – память (значение по указанному адресу), V – значение (константа), S – стек (если указан в качестве приёмника – добавление в стек, в качестве отправителя – изъятие из стека).

Оставшиеся десять команд запланированы под условные переходы и остальную математику.
Да, типы данных пронумерованы просто: 00 - константа, 01 - регистр, 10 - стек, 11 - память.
Возьмём байт, скупо отведённый на команду, верхние четыре бита в нём считаем кодом команды, пятый и шестой бит - типом первого операнда, седьмой и восьмой бит - типом второго операнда.
Например, опкод команды MOV, пересылающей данные из регистра в память будет выглядеть так: 00011101. Та же команда, заносящая значение в регистр будет выглядеть как 00010100, а команда левого сдвига верхушки стека на заданное число - 01001000.

Кстати, о стеке. Он у меня необычный по двум причинам (чтобы понять необычность которых, нужно всё-таки знать, что такое стек).
Первая: я не стал реализовывать стек в основной памяти. Её и так мало (два килобайта, напомню), да плюс на адресацию стека нужно выделять, как минимум, один регистр. При этом совершенно ничего не мешает добавить в нашу схему ещё два килобайта памяти, и использовать под стек уже её. Это даже не ограничивает многозадачность, ежели таковую когда-нибудь придётся реализовать на этом процессоре, - стековую память точно так же можно поделить на участки по количеству исполняемых программ.
Вторая: у меня нет привычных по ассемблеру для x86 команд PUSH и POP (или аналогичных им). Во-первых, выделять ажно две отдельные команды из имеющегося лимита ой, как не хотелось. Во-вторых, ещё при изучении ассемблера, мне было интересно - а почему бы не сделать именно так? В итоге, команда MOV S,[V|R|M] должна работать аналогично PUSH [V|R|M], а MOV [R|M],S - аналогично POP. Команда MOV S,S хоть и не запрещена, но никакого действия не выполнит (при этом она не будет равна NOP по количеству тактов).

Итого, в результате у меня набралось данных на вполне себе ассемблер для моего ещё не созданного процессора. Ниже приведу примеры команд и трансляцию их в шеснадцатеричный и двоичные коды:
MOV [1Ah],10h (записать число в память)-> 0x1C 0x1A 0x10 -> 00011100 00011010 00010000
SUM B,C (прибавить к значению регистра B значение регистра С) -> 0x35 0x01 0x02 -> 00110101 00000001 00000010
XOR S,S (обнулить значение на верхушке стека) -> 0x2A -> 00101010 (параметров у команды нет, то, что работа проводится со стеком, процессор должен понимать из опкода).
и т.д.

И последнее, что осталось - определить и формализовать алгоритм работы процессора. У меня в первом приближении получилось вот что:
1. Считать байт по адресу, на который указывает адресный регистр (adr), в буфер команды, инкрементировав adr.
2. Определить количество параметров команды = pcount.
3. Инкрементируя значение адресного регистра, считывать параметры в соответствующие буфера (n_param в n_buffer) pcount раз.
4. Выполнить команду.
5. Вернуться к шагу 1.

Конечно шаг №4 - это ещё один внутренний алгоритм, который у меня пока ещё не до конца формализован. Причина в том, что при непосредственной реализации схемы по "плавающему" алгоритму ("а, мля, как получится - так и хрен с ним") возникает множество интересных решений и находок, никогда не получившихся бы, следуй я заранее написанному плану.

С теорией, по большей части - всё.

Конец первой части. В следующей - практика: опишу создание парсера команд, контроллера памяти, блока регистров и управляемого цикла.
Продолжение следует.

Оргазм робокопа

Я с детства любил головоломки и конструкторы в любом их виде, от советских клонов "Лего" (такие были, да), до всяких там скандинавских кроссвордов (которые, как и обычные, мы с батей разгадывали наперегонки в неимоверных количествах).
Оставив место для ностальгии по тем детским увлечениям, я резко перепрыгну во времена учëбы в институте. Программирование я выбрал именно потому, что это головоломка и конструктор в одном флаконе, и по той же причине я любил предметы, также сочетавшие в себе эти свойства.
К примеру, замечательная дискретная математика. Я просто кончал радугой, выводя преобразования всяких конъюнкций и стрелок Пирса (ещё там был штрих Шефнера, но мне не нравилось, как он на меня шипел), строил связные графы и оперировал множествами. Такая-то годнота - и был еë курс мал и короток. Самый базовый уровень, явно недостаточный для подготовки хорошего программиста - по-хорошему, такое надо давать ещё в школе.
Потом было низкоуровневое программирование, здорово вскипятившее мне мозг. Пожалуй, самый лучший курс за всë время - и тоже непростительно куцый. Программирование на ассемблере в реальном режиме под DOS, никакого protected mode или работы с API любых OS. Только-только пошло что-то годное - как курс закончился; зато, блин, как же мы без метрологии или без экономики?
Но самой большой несправедливостью, до сих пор отзывающейся тянущей болью в сердце, является наш курс электротехники.
Электромашины никак не давались мне, и предмет этот был жуткой пыткой. Трëхфазные электродвигатели, сельсины (или синсины? до сих пор не знаю, что это такое), реле и прочий стафф - всë это было не головоломкой и не конструктором, а только грудой мусора, работающего на физических законах, которые я отказывался соблюдать не мог упорядочить и понять. Так что электротехнику я ненавидел до тех пор, пока курс не дошëл до проектирования логических элементов.
О, прекрасные полупроводники! Как только ШМИГИРИЛОВ, ДА-ДА, ИМЕННО В ВЕРХНЕМ РЕГИСТРЕ, рассказал, как на них реализуется любимая мной булева алгебра - я, наконец, осознал, зачем был этот год пыток электричеством! Вот оно - понял я - теперь мы будем проектировать свой процессор, со своей архитектурой, если не аналог 286, то 8080 уж точно! Создадим для него свой набор команд, и собственный ассемблер! Омайгад, как же круто!
Естественно, всë ограничилось лабой на проектирование простеньких сумматоров и мультиплексоров. Одно занятие!
Я разочаровался и ушëл в запой.

Собственно, вся эта портянка была только предисловием. Дело в том, что я тут наткнулся на вот такую штуку: Logisim. Это простой и понятный даже школьнику инструмент проектирования логических схем. И, как гласит его документация, в нормальных учебных заведениях этот софт [зависть]реально используют для учëбы [/зависть]. Я повозился с ним - и мне кажется, что несколько часов работы в этой программе стоят больше всего нашего курса электротехники. Я конкретно залип, начав сначала строить элементарные схемки, вроде тех же сумматоров. Потом, было, дёрнулся собрать что посложнее - и обнаружил, что позабыл все логические правила, как что из чего выводится. Ну это не беда, в сети есть учебники, рассчитанные на читателей любого уровня: я, например, вспоминал основы по этой методичке.

Стоп, тут технически необразованый читатель спросит меня: а, собственно, что это вообще такое вот? Мудоплексоры какие-то, агебра булимическая, одна история лучше другой просто!
Так вот: булева алгебра и логические законы - это, собственно, то, благодаря чему работают все наши компьютеры, телефоны, и прочая цифровая техника.
Благодаря некоторым физическим законам (которые я сейчас понимаю не лучше прежнего) возможно создание полупроводниковых элементов, на которых, в свою очередь, реализуются элементы логические. То есть такие, которые оперируют только понятиями "истина" или "ложь"; в нашем аналоговом мире оказалось очень удобно кодировать эти понятия лепездричеством. Есть напряжение на контакте - "истина" (1), нет - "ложь" (0). Поскольку понятий у нас всего два, то и базовых операций над ними немного - но комбинируя эти базовые операции (реализованные, как раз, логическими элементами), можно вывести всё более сложные; за основами отошлю в вышеуказанную методичку. Суть же в том, что можно задать любое непротиворечивое логическое правило (или их набор), записать его формулой, а по этой формуле построить электрическую схему.
Собственно, вся электронная начинка наших девайсов и состоит из таких схем. Конечно, очень сложных, но, тем не менее: сверхсовременный многоядерный йоба-процессор на этом уровне ничем не отличается от логических машин середины прошлого века. А уж про то, что комбинациями нулей и единичек можно кодировать абсолютно любую информацию - про это я рассказывать не буду, о таком стыдно не знать.
Но хватит теории. Слева я нарисовал простейший полусумматор, реализованный только базовыми элементами - НЕ/И/ИЛИ (инвертор,/конъюнктор/дизъюнктор или, в сишной нотации, !/&/|), - два бита на вход, их сумма в двоичном виде на выходе:
Справа такой же сумматор, но в нём меньше "деталек" - из базовых элементов можно собрать новую деталь - ИСКЛЮЧАЮЩЕЕ ИЛИ (он же XOR), или, с тем же успехом, воспользоваться уже встроенной в программу деталью. Кстати, по умолчанию программа использует ANSI-стандарт изображения элементов, но в настройках можно переключиться на другие стандарты, кому как удобнее.

Собранные схемы можно использовать для дальнейшего конструирования. Так, например, из полусумматоров собирается сумматор, оперирующий уже тремя битами (то есть умеющий считать уже от нуля до трёх, а не до двух, как полусумматор):
Из сумматоров можно собрать более сложные устройства, складывающие любые числа, но это уже не так интересно - просто повторение пройденного.
А вот что показалось мне действительно интересным - так это создать схему, выводящую на восьмисегментный индикатор шестнадцатиричное представление двоичного числа, закодированного в четырёхбитном регистре (четыре бита кодируют числа от 0x0 до 0xF). Индикатор в программу встроен, позиция контактов у него аналогична индикатору TIL321 от Texas Instruments. Восьмой контакт, кстати, не понадобится - он отвечает за сегмент точки, таким образом на входе получается четыре бита, на выходе - семь.

Для начала я сделал таблицу, расписывающую, какие сегменты (R1 - R7) должны гореть при той или иной цифре, а также представление этой цифры в двоичном коде (A,B,C,D):

Затем стал выводить правила, реализующие полученную логику. Например, для сегмента R1 полное правило можно записать так (я буду использовать сишную символику, поскольку мне не хочется возиться с привычными мне символами булевой алгебры):

(!A&!B&C&!D)|(!A&!B&C&D)|(!A&B&!C&!D)|(!A&B&!C&D)|(!A&B&C&!D)|(A&!B&!C&!D)|(A&!B&!C&D)|(A&!B&C&!D)|(A&!B&C&D)|(A&B&!C&D)|(A&B&C&!D)|(A&B&C&D)

Это правило вполне рабочее, и уже по нему можно построить схему, которая даже будет включать нужный сегмент:
Но понятно, что такая схема - это дерьмос собачес, и инженера, который такое воплотит в кремний, ШМИГИРИЛОВ будет анально сношать в пукан магнитным сердечником. Чтобы сберечь пукан, применяю чудеса логических законов для получения эквивалентного правила:

!A&(!B&C)|B&(!C|!D))|A(!B|B&(C|D))

Если вы дочитали до этого места, сейчас вы ругаетесь. Примерно так: каким это хреном автор выкинул больше половины закорючек?
На самом деле я выкинул все промежуточные приведения и расчёты - а их там на несколько страниц, если с подробностями, которые вам тут совершенно неинтересно будет читать (а мне лениво писать) Поначалу я себе так и расписывал, тратя по несколько часов на одно правило. Потом, когда запомнил законы - стал пропускать промежуточные записи, тратя минут по десять на правило. А потом совсем научился, и стал записывать правило, просто глядя на таблицу; в этом действительно нет ничего сложного, если уметь в логику.

Итак, по сокращённому правилу получается такая схема:

Причём, благодаря всё тем же логическим законам, схема может быть и такой (количество элементов одно, а контакты разные), они полностью эквивалентны:

Но не суть.
В итоге, потратив некоторое время (если честно, меня так увлёк процесс, что я даже не мог заснуть), я нарисовал схему полностью:
Да, собственного удовольствия ради я снова использовал только базовые элементы; введи я, скажем, тот же XOR - схема выглядела бы (но не была на самом деле!) на порядок проще и меньше. Например, если не выпендриваться, и заключить каждую цепь в отдельный блок, то схема будет выглядеть лишь так:
Смотрим на работу:
Кайф испытываю неописуемый, хочется даже написать про это в бложек... WAIT, AW SHIT!
Файл со схемой можно загрузить по ссылке.

Следующая задача - смоделировать простенький процессор. Тут в самом деле нет ничего сложного, самый простой четырёхбитный процессор будет сложнее только в два-три раза. Затем можно пытаться добавить к нему память, ввод, вывод, в общем - реализовать архитектуру фон Неймана. Но всё это - если не перегорю.

Поскольку мой блог читают, в основном, люди с техническим образованием и Констпаус, думаю, что это было интересно.