The post has been translated automatically. Original language: Russian
Almost any algorithm has to make a decision sooner or later. If the value is zero, perform one action, if it is greater than the other, choose another path, if the condition is not met, continue the cycle.
At the processor level, all these constructions come down to a few simple things: get a condition, determine its result, and, if necessary, change the address of the next executed command.
In Donald Knuth's MIX and Memora8, this task is solved in different ways. MIX stores some of the condition information in a special state of the machine and offers transition commands that check this state. Memora8 tries to make the comparison result look like regular data, and keep the transition as simple as possible.
The difference seems small, but it clearly shows two different approaches to the processor device.
How is the condition stored in MIX
MIX has a special comparison indicator. After executing the comparison command, it assumes one of three states: the first value is less than the second, equal to it, or greater.
This state exists separately from the regular registers.
The following command can check the indicator and make a transition depending on its value. Thus, the comparison and the subsequent decision are connected through the hidden state of the processor.
This scheme is convenient for the program. First, the comparison is performed, then you can immediately use one of the appropriate transition commands.
In addition to the comparison indicator, the MIX has an overflow indicator. It can also influence the course of the program.
As a result, the processor has not only the values in the registers, but also an additional state that commands can set and check.
For the MIX architecture, this is a natural solution: the condition becomes part of the machine's state.
A transition can know quite a lot
MIX provides various options for conditional transitions.
You can check the result of a previous comparison, the overflow status, or the value of a specific register. Depending on the specific command, the processor understands which condition needs to be checked.
This allows you to express common branches quite directly.
The program does not have to turn the condition into a number itself, put a mask on it, or prepare a separate value for the transition. A significant part of this work has already been described by the command system.
This approach has an obvious advantage: a conditional construction in machine code can be short.
But the hardware has to know a lot of different conditions.
The transition team must not only change the command counter, but also understand exactly what state of the machine is currently being checked.
Memora8 draws this line differently.
In Memora8, the result of the comparison becomes data.
In Memora8, the CMP and CMPI commands do not set separate processor flags.
The result of the comparison is written in a regular register.
"This" is a 32-bit value, the lower-order bits of which show the result of several comparisons: equality, the ratio "less" and "more" for signed and unsigned numbers.
This result can be used just like any other number.
It can be stored in a register, processed with a logical operation, passed on, or checked later.
At the same time, the processor itself does not have to remember that a comparison took place a few commands ago.
Everything you need is already in its usual architectural condition — in registers.
Why are there only two crossings?
For conditional branching, Memora8 uses two simple commands: BNZ and BEQZ.
The first one performs a transition if the value of the selected register is not zero. The second one is if it is zero.
At first glance, this is very little.
""""""if less than", """if more than", """" if the numbers are equal" or """ if the unsigned value is less than another"" commands are not available.
But the processor doesn't need them.
The necessary condition can be prepared in advance.
First, CMP creates a set of features. The logical operation then allocates the bit or combination of bits of interest. After that, BNZ or BEQZ makes the final decision.
A universal scheme is obtained: calculate the condition, bring it to zero or a non-zero value, and perform a simple transition.
More commands, but fewer behaviors
Let's say the program needs to move to another branch if a is less than b.
An architecture with a well-developed conditional transition system can perform a comparison, and then use the special "transition if less" command.
In Memora8, you will need to get the comparison result, select the desired feature and check it.
At the program level, this may mean an additional instruction.
But for the hardware, the picture looks different.
CMP always performs the comparison in the same way. The logical command always handles regular registers. BNZ always answers one question: is the value equal to zero or not?
There is no need to create a separate transition option for each possible relationship between the numbers.
Thus, part of the complexity is transferred from the transition command to a sequence of simple operations.
The signed and unsigned comparison are also explicitly separated.
The same 32-bit value can be interpreted as a signed or unsigned number.
For example, a value with the highest bit set can be negative for signed arithmetic, and a large positive number for unsigned arithmetic.
In Memora8, CMP generates attributes for both variants at once.
The program chooses which one to use.
This eliminates the need for the processor to have separate comparison instructions for each case or to store an additional interpretation mode.
The comparison instruction provides information, and the meaning of this information is determined by the program.
This approach fits well with the general Memora8 model: if possible, do not hide an important state inside the processor if it can be represented by a regular value.
What happens to the transition inside the pipeline
Conditional transition is interesting not only for its logic.
It changes the very flow of program execution.
Memora8 uses a five-stage pipeline. While one instruction is running, the next ones can already be selected from memory and be in the previous stages.
If BNZ, BEQZ, JAL, or JALR decides to switch to another address, some of the commands already selected turn out to be incorrect. They belong to a path that the program should no longer follow.
Therefore, the processor must redirect the selection to a new address and cancel the younger instructions.
This shows why even a simple transition command remains an important part of the architecture.
The "zero or not zero" check itself is very simple. The main difficulty is related to the fact that the result of the transition affects the operation of the entire pipeline.
Therefore, adding a large number of different conditional transitions is not always beneficial. Each new option must work consistently with the same mechanism for redirecting and canceling already selected instructions.
JAL and JALR solve a different problem
Not all traffic is related to conditions.
Memora8 has JAL and JALR. They are used for direct and indirect transfers while maintaining the return address.
This allows you to build function calls and return from them without a separate special return register.
JAL works with the address set relative to the current program position. JALR gets the address base from the register, so it is suitable for indirect calls and returns.
The same principle is visible here again.
Instead of a large number of commands for different types of calls, the architecture provides two common mechanisms. The specific meaning — a normal transition, a function call, a return, or a jump to a calculated address— is determined by how the program uses these commands.
MIX makes the condition part of the machine
The MIX approach is more specialized.
The comparison indicator, the overflow indicator, and various jump commands make conditional execution a noticeable part of the processor's internal state.
This is convenient for machine language, because common checks are expressed directly.
The program can consider a comparison as an action, after which the machine already "knows" what relationship exists between the two values.
The transition can only ask this condition.
Memora8 tries not to store such information separately.
After the comparison, the processor does not "remember" that one number was less than the other. He just wrote the corresponding result in the register.
If the program no longer needs this information, the register can be used for something else.
The comparison state exists for exactly as long as the program itself requires it.
Hidden state or normal data
This distinction has a more general meaning.
Special flags are convenient because they don't take up regular registers and allow some commands to be more compact.
But they create an additional type of dependency between instructions.
The command may not explicitly read any register modified by the previous instruction, but it still depends on the flags set by it.
When analyzing processor execution, this relationship must be taken into account.
When the result of the comparison is in a regular register, the dependency becomes explicit.
One command writes a register, the other reads it.
This is a convenient model for a pipelined processor: the data flow between instructions is described by the same rules as for ordinary arithmetic.
Two ways to express one solution
There is almost no difference at the algorithm level.
The program must still answer the question: is the condition true or not?
MIX helps you get an answer using a special machine state and a set of conditional transitions.
Memora8 first turns the condition into a regular value, and then uses one of two simple transitions.
The first approach allows you to put more meaning directly into the command system.
The second one reduces the number of special mechanisms that the processor must support.
Both methods lead to the same result — the program changes the direction of execution.
But for Memora8, it turned out to be more important to maintain uniformity.
The comparison produces data. Logical instructions transform data. The transition verifies the data.
Each part performs one relatively simple task.
That is why there is no need to have dozens of conditional transitions in Memora8. A large number of conditions are built from a small number of basic mechanisms.
This again shows the main difference from MIX: Memora8 does not strive to make each individual instruction as expressive as possible.
He strives to make their combination expressive enough.
Почти любой алгоритм рано или поздно должен принять решение. Если значение равно нулю — выполнить одно действие, если больше другого — выбрать другой путь, если условие не выполнено — продолжить цикл.
На уровне процессора все эти конструкции сводятся к нескольким простым вещам: получить условие, определить его результат и при необходимости изменить адрес следующей выполняемой команды.
В MIX Дональда Кнута и Memora8 эта задача решается по-разному. MIX хранит часть информации об условии в специальном состоянии машины и предлагает команды перехода, которые это состояние проверяют. Memora8 старается сделать результат сравнения обычными данными, а сам переход оставить максимально простым.
Разница кажется небольшой, но она хорошо показывает два разных подхода к устройству процессора.
Как условие хранится в MIX
MIX имеет специальный индикатор сравнения. После выполнения команды сравнения он принимает одно из трёх состояний: первое значение меньше второго, равно ему или больше.
Это состояние существует отдельно от обычных регистров.
Следующая команда может проверить индикатор и выполнить переход в зависимости от его значения. Таким образом, сравнение и последующее решение связаны через скрытое состояние процессора.
Для программы такая схема удобна. Сначала выполняется сравнение, затем можно сразу использовать одну из подходящих команд перехода.
Кроме индикатора сравнения, MIX имеет признак переполнения. Он также может влиять на ход программы.
В итоге процессор располагает не только значениями в регистрах, но и дополнительным состоянием, которое команды могут устанавливать и проверять.
Для архитектуры MIX это естественное решение: условие становится частью состояния машины.
Переход может знать довольно много
MIX предоставляет различные варианты условных переходов.
Можно проверить результат предыдущего сравнения, состояние переполнения или значение определённого регистра. В зависимости от конкретной команды процессор понимает, какое условие нужно проверить.
Это позволяет выразить распространённые ветвления достаточно непосредственно.
Программа не обязана сама превращать условие в число, накладывать на него маску или готовить отдельное значение для перехода. Значительная часть этой работы уже описана системой команд.
У такого подхода есть очевидное преимущество: условная конструкция в машинном коде может быть короткой.
Но аппаратуре приходится знать множество разновидностей условий.
Команда перехода должна не только изменить счётчик команд, но и понимать, какое именно состояние машины сейчас проверяется.
Memora8 проводит эту границу иначе.
В Memora8 результат сравнения становится данными
В Memora8 команды CMP и CMPI не устанавливают отдельные флаги процессора.
Результат сравнения записывается в обычный регистр.
Это 32-битное значение, младшие биты которого показывают результат нескольких сравнений: равенство, отношения «меньше» и «больше» для знаковых и беззнаковых чисел.
Такой результат можно использовать так же, как любое другое число.
Его можно сохранить в регистре, обработать логической операцией, передать дальше или проверить позже.
Сам процессор при этом не обязан помнить, что несколько команд назад произошло сравнение.
Всё необходимое уже находится в обычном архитектурном состоянии — в регистрах.
Почему переходов всего два
Для условного ветвления Memora8 использует две простые команды: BNZ и BEQZ.
Первая выполняет переход, если значение выбранного регистра не равно нулю. Вторая — если оно равно нулю.
На первый взгляд этого очень мало.
Нет отдельных команд «перейти, если меньше», «перейти, если больше», «перейти, если числа равны» или «перейти, если беззнаковое значение меньше другого».
Но процессору они и не нужны.
Нужное условие можно подготовить заранее.
Сначала CMP создаёт набор признаков. Затем логическая операция выделяет интересующий бит или комбинацию битов. После этого BNZ или BEQZ принимает окончательное решение.
Получается универсальная схема: вычислить условие, привести его к нулю или ненулевому значению и выполнить простой переход.
Больше команд, но меньше видов поведения
Допустим, программе нужно перейти на другую ветвь, если a меньше b.
Архитектура с развитой системой условных переходов может выполнить сравнение, а затем использовать специальную команду «переход, если меньше».
В Memora8 потребуется получить результат сравнения, выделить нужный признак и проверить его.
На уровне программы это может означать дополнительную инструкцию.
Но для аппаратуры картина выглядит иначе.
CMP всегда выполняет сравнение одинаковым способом. Логическая команда всегда обрабатывает обычные регистры. BNZ всегда отвечает на один вопрос: равно значение нулю или нет?
Не требуется создавать отдельный вариант перехода для каждого возможного отношения между числами.
Таким образом, часть сложности переносится из команды перехода в последовательность простых операций.
Знаковое и беззнаковое сравнение тоже разделены явно
Одно и то же 32-битное значение можно интерпретировать как знаковое или беззнаковое число.
Например, значение с установленным старшим битом для знаковой арифметики может быть отрицательным, а для беззнаковой — большим положительным числом.
В Memora8 CMP формирует признаки для обоих вариантов сразу.
Программа сама выбирает, какой из них использовать.
Это избавляет процессор от необходимости иметь отдельные команды сравнения для каждого случая или хранить дополнительный режим интерпретации.
Инструкция сравнения выдаёт информацию, а смысл этой информации определяет программа.
Такой подход хорошо соответствует общей модели Memora8: по возможности не скрывать важное состояние внутри процессора, если его можно представить обычным значением.
Что происходит с переходом внутри конвейера
Условный переход интересен не только своей логикой.
Он меняет сам поток выполнения программы.
Memora8 использует пятистадийный конвейер. Пока одна инструкция выполняется, следующие уже могут быть выбраны из памяти и находиться на предыдущих стадиях.
Если BNZ, BEQZ, JAL или JALR решает перейти на другой адрес, некоторые уже выбранные команды оказываются неправильными. Они принадлежат пути, по которому программа больше не должна идти.
Поэтому процессор должен перенаправить выборку на новый адрес и отменить более молодые инструкции.
Это показывает, почему даже простая команда перехода остаётся важной частью архитектуры.
Сама проверка «ноль или не ноль» очень проста. Основная сложность связана с тем, что результат перехода влияет на работу всего конвейера.
Поэтому добавление большого числа различных условных переходов не всегда выгодно. Каждый новый вариант должен согласованно работать с тем же механизмом перенаправления и отмены уже выбранных инструкций.
JAL и JALR решают другую задачу
Не все переходы связаны с условиями.
В Memora8 есть JAL и JALR. Они используются для прямых и косвенных переходов с сохранением адреса возврата.
Это позволяет строить вызовы функций и возвращаться из них без отдельного специального регистра возврата.
JAL работает с адресом, заданным относительно текущей позиции программы. JALR получает основу адреса из регистра, поэтому подходит для косвенных вызовов и возвратов.
Здесь снова виден тот же принцип.
Вместо большого числа команд для разных видов вызовов архитектура предоставляет два общих механизма. Конкретный смысл — обычный переход, вызов функции, возврат или переход по вычисленному адресу — определяется тем, как эти команды использует программа.
MIX делает условие частью машины
Подход MIX более специализирован.
Индикатор сравнения, признак переполнения и различные команды перехода делают условное выполнение заметной частью внутреннего состояния процессора.
Это удобно для машинного языка, потому что распространённые проверки выражаются непосредственно.
Программа может рассматривать сравнение как действие, после которого машина уже «знает», какое отношение существует между двумя значениями.
Переходу остаётся только спросить это состояние.
Memora8 старается не сохранять такую информацию отдельно.
После сравнения процессор не «помнит», что одно число было меньше другого. Он просто записал соответствующий результат в регистр.
Если программе эта информация больше не нужна, регистр может быть использован для чего-нибудь другого.
Состояние сравнения существует ровно столько, сколько этого требует сама программа.
Скрытое состояние или обычные данные
Это различие имеет более общий смысл.
Специальные флаги удобны, потому что не занимают обычные регистры и позволяют некоторым командам быть компактнее.
Но они создают дополнительный тип зависимости между инструкциями.
Команда может явно не читать никакой регистр, изменённый предыдущей инструкцией, но всё равно зависеть от установленных ею флагов.
При анализе выполнения процессора такую связь необходимо учитывать.
Когда результат сравнения находится в обычном регистре, зависимость становится явной.
Одна команда записывает регистр, другая его читает.
Для конвейерного процессора это удобная модель: поток данных между инструкциями описывается теми же правилами, что и для обычной арифметики.
Два способа выразить одно решение
На уровне алгоритма разницы почти нет.
Программа всё равно должна ответить на вопрос: истинно условие или нет?
MIX помогает получить ответ с помощью специального состояния машины и набора условных переходов.
Memora8 сначала превращает условие в обычное значение, а затем использует один из двух простых переходов.
Первый подход позволяет поместить больше смысла непосредственно в систему команд.
Второй уменьшает число специальных механизмов, которые должен поддерживать процессор.
Оба способа приводят к одному результату — программа меняет направление выполнения.
Но для Memora8 оказалось важнее сохранить единообразие.
Сравнение производит данные. Логические инструкции преобразуют данные. Переход проверяет данные.
Каждая часть выполняет одну относительно простую задачу.
Именно поэтому в Memora8 нет необходимости иметь десятки условных переходов. Большое количество условий строится из небольшого количества базовых механизмов.
В этом снова проявляется главное отличие от MIX: Memora8 не стремится сделать каждую отдельную инструкцию максимально выразительной.
Он стремится сделать достаточно выразительным их сочетание.
Share
