The post has been translated automatically. Original language: Russian
One of the most unusual features of Donald Knuth's MIX is the ability to work not only with the entire machine word, but also with a selected part of it. For a modern programmer, this looks unusual: usually the processor loads a byte, half a word, or a full word, and if individual bits are needed, the program uses shifts and logical operations.
In MIX, the choice of a part of a word is built directly into the architecture of the command.
This solution shows the difference between MIX and Memora8 well. Both processors must solve the same task: get data of different sizes from memory and extract the necessary fragments from them. But the place where this work is done is chosen in completely different ways.
The word MIX consists of parts
The MIX machine word contains a sign and five bytes. For Knuth, this is not just an indivisible quantity. In the instructions, you can specify which part of the word should be involved in the operation.
To do this, use the command field, which sets the left and right borders of the selected section. For example, you can work with the entire word, with several adjacent bytes, or with only one of them.
Moreover, the sign is considered as a separate part of the word and can also be included in the selected field.
As a result, the load command does not necessarily mean "take the entire value from memory". It can mean "take only the specified part of this word and put it in the register."
The same applies to data retention and a number of other operations.
This is a very powerful mechanism for the MIX architecture. Instead of multiple separate commands for different data sizes and positions, one general way is used to describe the desired fragment.
Why was it convenient for Knut
MIX was created to parse algorithms, and algorithms are constantly working not only with integers.
Several small values can be stored in one machine word. You may need to extract part of the record, process a separate field, or transfer only a few bytes without affecting the rest.
Instead of describing such an operation each time with a sequence of shifts and masks, MIX allows you to specify the desired field directly in the instructions.
This makes machine language quite expressive.
The same download command is able to work with different parts of a word. The save command may also not change the entire memory word, but only the selected area.
From the point of view of the program, this is convenient: the architecture directly understands the concept of a "field inside a word".
But this convenience has a downside.
Versatility becomes a part of every team.
If the processor allows you to select an arbitrary part of a word, the hardware has to take this choice into account when performing the operation.
It is not enough to simply read a word from memory and pass it on. It is necessary to define the boundaries of the field, select the appropriate part, process the sign correctly and generate the result.
For saving, the task becomes even more interesting. If only part of the word is changed, you must leave the remaining parts the same.
Thus, one small feature in the instruction format gradually passes through the processor device and affects several of its nodes.
This is not a problem in the training model. Moreover, this architecture helps to compactly express the operations that Knuth wanted to use when describing algorithms.
When designing Memora8, the priority turned out to be different.
There is no arbitrary word field in Memora8
Memora8 works with 32-bit registers and does not have a MIX field analog capable of selecting an arbitrary sequence of bytes inside a value.
Specific sizes are used to access the memory.
The processor can read a byte, half of a 32-bit word, or the entire word. There are options for bytes and half words that determine how a short value is converted into a 32-bit result.
Recording works similarly: you can save a byte, half a word, or a full word.
Thus, instead of the universal "select an arbitrary field" mechanism, several predefined and most common options are used.
They cover the main part of practical data accesses and at the same time have a fairly direct meaning for the hardware.
And if you need separate bits?
The absence of MIX fields does not mean that Memora8 is unable to work with parts of the value.
It's just that this problem is solved by ordinary computing teams.
If individual bits are needed, the value can be shifted to the desired position and a Boolean mask applied. If several parts need to be combined, logical operations are used. If the field needs to be replaced, the program first clears the corresponding bits, and then adds a new value.
In other words, the operation that is partially described in MIX right inside the command turns into a sequence of simple actions in Memora8.
In terms of the number of instructions, MIX can be more compact here.
From the point of view of the Memora8 device, the advantage lies elsewhere: the processor does not require a universal hardware mechanism for selecting arbitrary fields for a large number of commands.
A shift remains a shift. A logical operation remains a logical operation. A memory read remains a read of a specific size.
One difficult opportunity or several simple ones
In this example, two approaches to building a team system are particularly clearly visible.
You can give the processor a richer concept of data. Then he will know that the machine word consists of separate fields, and will be able to work with them directly.
This is the path chosen in MIX.
You can leave simpler objects for the processor: bytes, half words, full words, and regular 32-bit registers. The more complex structure of the value is then understood by the program.
This is how Memora8 works.
For example, the program knows that bits eight through eleven of a certain value have a special meaning. There is no separate "field from the eighth to the eleventh bit" for Memora8 itself. There is a 32-bit value that can be shifted and processed with a logical operation.
This is an important difference.
MIX transfers part of the representation of the data structure to the command system. Memora8 tries to keep the data structure a level above the hardware.
Why did the byte and half of the word still receive separate commands?
A logical question arises: if Memora8 strives for simplicity, why are there separate commands for reading a byte and half a word at all? After all, theoretically, it would be possible to always read 32 bits and then select the necessary part programmatically.
The reason is that minimality has a practical limit.
Reading bytes and 16-bit values is so common that it would be unprofitable to force each program to constantly reproduce the same sequence of actions. In addition, the size of the access is directly related to the memory itself, so the hardware still has to know which parts of the data are being read or written.
As a result, Memora8 supports several natural data sizes, but does not generalize them to arbitrary fields.
This is a tradeoff characteristic of architecture.
A mechanism is added to the processor if it solves a common problem directly enough. But they try to build rare or more complex variants from existing operations.
MIX saves instructions, Memora8 saves rules
Imagine a value that contains a small field.
In MIX, in many cases, you can specify the necessary part directly in the instructions. The machine itself will perform the necessary allocation.
In Memora8, the program will probably first read a byte, half a word, or a full word, and then perform a shift and logical operation if necessary.
Memora8 executes more machine commands.
At first glance, it seems that this is an unequivocal loss. But the number of executed instructions is only one of the architecture parameters.
There is also the complexity of decoding, the number of options for passing a command through the processor, the number of special cases in the data path, and the amount of logic that needs to be checked.
Memora8 consciously agrees to sometimes execute several simple commands instead of one more expressive one, if this allows you to keep the commands themselves homogeneous.
Therefore, its simplicity does not necessarily consist in the minimum number of program steps.
It consists of a small number of rules for performing these steps.
The very concept of data has also changed.
The difference between MIX and Memora8 is not only related to hardware.
Over the decades The organization of programs has also changed.
Today, the structure of complex data is largely determined by the programming language and the compiler. They are the ones who know where the structure field is located, what width it matters, whether it is signed, and which bits are used to store individual features.
The processor does not need to understand the meaning of these fields.
It is enough for him to provide operations from which the compiler can build the necessary transformation.
In MIX, the border runs differently. The machine language is much closer to the data representation, so the ability to specify a field directly in the instructions looks natural.
This creates an interesting effect: the same idea that relates to the processor architecture in MIX is partially transferred to the software level in Memora8.
The idea has not disappeared
It would be wrong to say that the MIX fields mechanism was outdated and therefore was simply dropped.
The task he solves still exists today.
Programs still extract individual bits, work with short integers, pack multiple values into a single word, and access fields of complex structures.
The location of the solution to this problem has changed.
MIX tells the processor: there is a field inside the word that needs to be worked with.
Memora8 tells the processor: here is the value, perform a simple operation on it. And the program knows exactly what the selected part of this value means.
For a small hardware architecture, this separation turned out to be more convenient.
Therefore, the MIX fields are not interesting as a forgotten feature of an old computer. They show how differently it is possible to draw the line between the capabilities of the processor and the capabilities of the program.
Knuth put the work with the parts of the word directly into the machine instruction. Memora8 retains the very ability to get the same result, but the universal hardware mechanism has been replaced by a combination of reading data of the required size, shifts, and logical operations.
The task remains the same.
The only thing that has changed is who exactly solves it.
Одна из самых необычных особенностей MIX Дональда Кнута — возможность работать не только с машинным словом целиком, но и с выбранной его частью. Для современного программиста это выглядит непривычно: обычно процессор загружает байт, половину слова или полное слово, а если нужны отдельные биты, программа использует сдвиги и логические операции.
В MIX выбор части слова встроен непосредственно в архитектуру команды.
Это решение хорошо показывает разницу между MIX и Memora8. Оба процессора должны решать одну и ту же задачу: получать из памяти данные разного размера и извлекать из них нужные фрагменты. Но место, где выполняется эта работа, выбрано совершенно по-разному.
Слово MIX состоит из частей
Машинное слово MIX содержит знак и пять байтов. Для Кнута это не просто неделимая величина. В инструкции можно указать, какая часть слова должна участвовать в операции.
Для этого используется поле команды, которое задаёт левую и правую границы выбранного участка. Например, можно работать со всем словом, с несколькими соседними байтами или только с одним из них.
Более того, знак рассматривается как отдельная часть слова и тоже может входить в выбранное поле.
В результате команда загрузки не обязательно означает «взять всё значение из памяти». Она может означать «взять только указанную часть этого слова и поместить её в регистр».
То же относится к сохранению данных и ряду других операций.
Для архитектуры MIX это очень мощный механизм. Вместо множества отдельных команд для разных размеров и положений данных используется один общий способ описать нужный фрагмент.
Почему Кнуту это было удобно
MIX создавался для разбора алгоритмов, а алгоритмы постоянно работают не только с целыми числами.
В одном машинном слове могут храниться несколько небольших значений. Может понадобиться извлечь часть записи, обработать отдельное поле или перенести только несколько байтов, не затрагивая остальные.
Вместо того чтобы каждый раз описывать такую операцию последовательностью сдвигов и масок, MIX позволяет сообщить нужное поле прямо в инструкции.
Это делает машинный язык довольно выразительным.
Одна и та же команда загрузки способна работать с различными частями слова. Команда сохранения также может изменять не всё слово памяти, а только выбранную область.
С точки зрения программы это удобно: архитектура напрямую понимает понятие «поле внутри слова».
Но у такого удобства есть обратная сторона.
Универсальность становится частью каждой команды
Если процессор позволяет выбирать произвольную часть слова, аппаратуре приходится учитывать этот выбор при выполнении операции.
Недостаточно просто прочитать слово из памяти и передать его дальше. Нужно определить границы поля, выбрать соответствующую часть, правильно обработать знак и сформировать результат.
Для сохранения задача становится ещё интереснее. Если изменяется только часть слова, необходимо оставить остальные части прежними.
Таким образом, одна небольшая возможность в формате инструкции постепенно проходит через устройство процессора и влияет на несколько его узлов.
В учебной модели это не проблема. Более того, такая архитектура помогает компактно выражать операции, которые Кнут хотел использовать при описании алгоритмов.
При проектировании Memora8 приоритет оказался другим.
В Memora8 нет произвольного поля слова
Memora8 работает с 32-битными регистрами и не имеет аналога поля MIX, способного выбрать произвольную последовательность байтов внутри значения.
Для доступа к памяти используются конкретные размеры.
Процессор может прочитать байт, половину 32-битного слова или всё слово. Для байта и половины слова предусмотрены варианты, определяющие, каким образом короткое значение превращается в 32-битный результат.
Запись устроена аналогично: можно сохранить байт, половину слова или полное слово.
Таким образом, вместо универсального механизма «выбрать произвольное поле» используются несколько заранее определённых и наиболее распространённых вариантов.
Они покрывают основную часть практических обращений к данным и при этом имеют достаточно прямой смысл для аппаратуры.
А если нужны отдельные биты?
Отсутствие полей MIX не означает, что Memora8 не способен работать с частями значения.
Просто эта задача решается обычными вычислительными командами.
Если нужны отдельные биты, значение можно сдвинуть в нужное положение и применить логическую маску. Если требуется объединить несколько частей, используются логические операции. Если поле нужно заменить, программа сначала очищает соответствующие биты, а затем добавляет новое значение.
То есть операция, которая в MIX частично описывается прямо внутри команды, в Memora8 превращается в последовательность простых действий.
С точки зрения количества инструкций MIX здесь может быть компактнее.
С точки зрения устройства Memora8 преимущество находится в другом: процессору не требуется универсальный аппаратный механизм выбора произвольных полей для большого числа команд.
Сдвиг остаётся сдвигом. Логическая операция остаётся логической операцией. Чтение памяти остаётся чтением конкретного размера.
Одна сложная возможность или несколько простых
На этом примере особенно хорошо видны два подхода к построению системы команд.
Можно дать процессору более богатое понятие данных. Тогда он будет знать, что машинное слово состоит из отдельных полей, и сможет работать с ними непосредственно.
Именно такой путь выбран в MIX.
Можно оставить для процессора более простые объекты: байты, половины слова, полные слова и обычные 32-битные регистры. Более сложную структуру значения тогда понимает уже программа.
Так устроен Memora8.
Например, программе известно, что биты с восьмого по одиннадцатый некоторого значения имеют особый смысл. Для самого Memora8 никакого отдельного «поля с восьмого по одиннадцатый бит» не существует. Есть 32-битное значение, которое можно сдвинуть и обработать логической операцией.
Это важное различие.
MIX переносит часть представления структуры данных в систему команд. Memora8 старается оставить структуру данных уровнем выше аппаратуры.
Почему байт и половина слова всё-таки получили отдельные команды
Возникает закономерный вопрос: если Memora8 стремится к простоте, зачем вообще существуют отдельные команды чтения байта и половины слова? Ведь теоретически можно было бы всегда читать 32 бита и затем выделять нужную часть программно.
Причина в том, что минимальность имеет практический предел.
Чтение байтов и 16-битных значений встречается настолько часто, что заставлять каждую программу постоянно воспроизводить одну и ту же последовательность действий было бы невыгодно. Кроме того, размер обращения имеет непосредственное отношение к самой памяти, поэтому аппаратуре всё равно приходится знать, какие части данных читаются или записываются.
В результате Memora8 поддерживает несколько естественных размеров данных, но не обобщает их до произвольных полей.
Это характерный для архитектуры компромисс.
В процессор добавляется механизм, если он решает распространённую задачу достаточно непосредственно. Но редкие или более сложные варианты стараются строить из уже существующих операций.
MIX экономит инструкции, Memora8 экономит правила
Представим значение, внутри которого хранится небольшое поле.
В MIX можно во многих случаях указать нужную часть прямо в инструкции. Машина сама выполнит необходимое выделение.
В Memora8 программа, вероятно, сначала прочитает байт, половину слова или полное слово, а затем при необходимости выполнит сдвиг и логическую операцию.
Memora8 выполняет больше машинных команд.
На первый взгляд кажется, что это однозначный проигрыш. Но число выполненных инструкций — только один из параметров архитектуры.
Есть ещё сложность декодирования, количество вариантов прохождения команды через процессор, число специальных случаев в тракте данных и объём логики, которую необходимо проверить.
Memora8 сознательно соглашается иногда выполнить несколько простых команд вместо одной более выразительной, если это позволяет сохранить сами команды однородными.
Поэтому его простота заключается не обязательно в минимальном числе шагов программы.
Она заключается в небольшом числе правил выполнения этих шагов.
Изменилось и само представление о данных
Различие между MIX и Memora8 связано не только с аппаратурой.
За десятилетия изменилась и организация программ.
Сегодня структура сложных данных в значительной мере определяется языком программирования и компилятором. Именно они знают, где находится поле структуры, какую ширину имеет значение, является ли оно знаковым и какие биты используются для хранения отдельных признаков.
Процессору необязательно понимать смысл этих полей.
Для него достаточно предоставить операции, из которых компилятор сможет построить нужное преобразование.
В MIX граница проходит иначе. Машинный язык находится значительно ближе к представлению данных, поэтому возможность указать поле непосредственно в инструкции выглядит естественно.
Отсюда возникает интересный эффект: одна и та же идея, которая в MIX относится к архитектуре процессора, в Memora8 частично переходит на уровень программных средств.
Идея не исчезла
Было бы неправильно сказать, что механизм полей MIX устарел и поэтому был просто отброшен.
Задача, которую он решает, существует и сегодня.
Программы по-прежнему извлекают отдельные биты, работают с короткими целыми числами, упаковывают несколько значений в одно слово и обращаются к полям сложных структур.
Изменилось место решения этой задачи.
MIX говорит процессору: внутри слова есть поле, с которым нужно работать.
Memora8 говорит процессору: вот значение, выполни над ним простую операцию. А что именно означает выбранная часть этого значения, знает программа.
Для небольшой аппаратной архитектуры такое разделение оказалось удобнее.
Поэтому поля MIX интересны не как забытая особенность старой вычислительной машины. Они показывают, насколько по-разному можно провести границу между возможностями процессора и возможностями программы.
Кнут поместил работу с частями слова непосредственно в машинную инструкцию. В Memora8 сохранилась сама возможность получить тот же результат, но универсальный аппаратный механизм был заменён сочетанием чтения данных нужного размера, сдвигов и логических операций.
Задача осталась прежней.
Изменилось только то, кто именно её решает.
Share
