The post has been translated automatically. Original language: Russian
Most processor instructions work with numbers in their entirety: add them up, compare them, shift them, or perform logical operations. But in system programming, you often have to work not with a number per se, but with individual bits inside it.
For example, one 32-bit register can be used as a set of 32 features. Each bit shows the status of an individual device, the presence of an event, resource usage, or task readiness.
In such cases, the program solves the same problem over and over again.: find the first set or reset bit in the specified direction.
For Memora8, we decided to check whether it makes sense to put this operation directly into a set of machine commands.
Why ordinary logical operations are sometimes not enough
Let's say there is a 32-bit mask:
00100100000010000000000000100000It is necessary to find the first set bit.
An ordinary processor can solve this problem by following a sequence of actions: check a part of a word, perform a shift, check again, repeat the cycle. Alternatively, you can use multiple masks and branches.
Each individual operation is simple, but together they form a small algorithm.
If such a search is rarely performed, this is not a problem. But in the system code, bitmasks are found all the time: event queues, availability tables, resource allocation, device status, scheduling, and interrupt handling.
Therefore, the question arises: is it possible to replace a repetitive software algorithm with a single hardware operation?
What a new team should be able to do
The easiest option is to search for the first unit on the right or left. But this quickly turns out to be insufficient.
A more universal operation is being considered for Memora8. She must allow:
- search for a unit;
- Search for zero;
- You don't have to start at the edge of a word.;
- move to the higher or lower bits;
- to inform that a suitable bit has not been found.
This allows you to use the same command for a large number of system tasks.
Two forms of a single operation
At the machine level, two commands are considered:
MSB
MSBIBoth perform the same search.
The only difference is where the control value comes from. In MSB, it is located in a register, and in MSBI it is set directly in the machine command itself.
This approach is already used for other Memora8 operations: one form is convenient for constant values, the other for those calculated during program operation.
How is the search direction set?
In a 32-bit word, the bits are numbered from 0 to 31:
bit 31 ....................... bit 0The bit number does not change depending on the search direction.
The control value determines where to start and where to move. A positive value means moving to the higher numbers of the bits, a negative value means moving to the lower ones.
For example:
+12means start with bit 12 and check:
12, 13, 14, ... 31But:
-12means:
12, 11, 10, ... 0Thus, one operation can search for the desired bit in both directions.
How does the search for zero and one differ?
The control value also encodes exactly what needs to be found.
The range from 0 to 31 is used to find the unit. The range from 32 to 63 is for searching for zero.
For example:
+0 — search for a unit from bit 0 to bit 31
-31 — search for a unit from bit 31 to bit 0
+32 — search for zero from bit 0 to bit 31
-63 — search for zero from bit 31 to bit 0The lower five bits of the control value determine the starting position.
Therefore, the value 44 means searching for zero starting from bit 12.:
44 - 32 = 12Or, which is convenient for the hardware implementation:
44 & 31 = 12One hardware unit instead of multiple options
At first glance, searching for zero and searching for one look like different operations. But they can be combined in hardware.
The original 32-bit value is used to find the unit. To search for zero, it is enough to first logically invert it, after which the same search block searches for one again.
That is, the processor does not need separate devices for:
First 1 on the right
first 1 on the left
first 0 on the right
first 0 on the leftAll options are served by a single search block with little management.
This fits well with the general Memora8 logic: multiple machine operations can use a single physical mechanism.
Why start the search not only from the edge
If the task is only to find the first unit, we could limit ourselves to two options: from right to left and from left to right.
But in the system code, it is often necessary to continue the search that has already begun.
For example, the program has found the set bit with the number 5 and wants to find the next one. Instead of shifting the entire mask, you can simply start a new search from position 6.
It turns out:
We found bit 5
↓
we start the next search with bit 6This feature is especially useful for bypassing all the set bits in the mask.
An example with an event queue
Imagine that 32 bits correspond to 32 groups of devices:
bit 0 — group 0
bit 1 — group 1
...
bit 31 — group 31If the bit is one, there is a pending event in the corresponding group.
A normal program should check the mask sequentially or apply multiple shift and comparison operations.
With MSB, the processor can immediately get the number of the first active group.:
event mask
↓
MSB
↓
active bit numberAfter processing this group, you can continue the search from the next position.
This allows you to use a 32-bit mask as a compact hardware-supported pointer to events.
The search for zero is needed no less than the search for one
Zero also often carries useful information.
For example, one can mean a busy resource, and zero can mean a free one. Then the search for the first zero becomes a search for a free element.
The same applies to:
- free slots;
- unoccupied IDs;
- free buffers;
- available channels;
- empty positions in the table.
If the processor is able to search for zero and one in the same way, many resource allocation operations become noticeably easier.
What the command returns
The result of the operation is the number of the found bit from 0 to 31.
If there is no matching bit in the selected direction, a special value is returned.:
32This is convenient because 32 is not a valid bit number in a 32-bit word.
The program can immediately check:
0..31 — bit found
32 — there is no suitable bitNo additional feature or separate status register is required.
Why not make it a library function?
Such a function can be written programmatically. The question is not whether this is possible, but how often it is used and how many commands it replaces.
If one compact hardware operation replaces repeated loops, branches, and shifts, adding it may be justified.
At the same time, the cost of the equipment remains local. The search block is located inside the processor and does not require new lines through the entire memory or between a large number of devices.
This is again the case when a relatively unusual machine command may be cheaper for the entire system than a seemingly simpler function.
Why is the operation useful for a small processor?
In large modern processors, such tasks can be hidden behind complex commands, libraries, and numerous hardware tools.
Memora8 is designed differently. We try to choose a small set of operations, each of which should have an understandable reason for its existence.
The bit search is interesting because it simultaneously:
- simple for hardware implementation;
- it is often useful for system software;
- reduces the number of branches;
- simplifies mask processing;
- it fits well with the 32-bit processor model.
Therefore, MSB and MSBI are now considered as part of the updated set of commands.
It's not just "finding the highest bit"
The name MSB is usually associated with the most significant bit of a number. In Memora8, the meaning of the operation is broader.
She's not just looking for the extreme set bit. It allows you to specify the starting position, direction, and desired bit value.
Therefore, it is more correct to perceive it as a universal search using a 32-bit mask.
For example:
look for 1 from bit 12 up
look for 1 from bit 12 down
look for 0 from bit 12 up
look for 0 from bit 12 downAll four variants are executed by a single hardware mechanism.
The next step is to check the cost
Like other Memora8 changes, this operation needs to be tested on a real FPGA.
It is important to measure:
- how many logical elements will a 32-bit search block take?;
- will it affect the critical path of the processor;
- will the 125 MHz frequency be maintained;
- how well will the compiler be able to use the new command;
- does it really shorten the system code?
If the hardware cost turns out to be small and the practical benefits are confirmed, MSB and MSBI will be a good example of how a specialized team can make a processor easier to program rather than more difficult.
The main idea here is this: if the system is constantly working with bit masks, it is not necessary to assemble the search for the right bit from a few simple instructions each time. Sometimes it is more correct to make this search a single understandable processor operation.
Большинство процессорных команд работают с числами целиком: складывают их, сравнивают, сдвигают или выполняют логические операции. Но в системном программировании часто приходится работать не с числом как таковым, а с отдельными битами внутри него.
Например, один 32-битный регистр может использоваться как набор из 32 признаков. Каждый бит показывает состояние отдельного устройства, наличие события, занятость ресурса или готовность задачи.
В таких случаях программа снова и снова решает одну и ту же задачу: найти первый установленный или сброшенный бит в заданном направлении.
Для Memora8 мы решили проверить, имеет ли смысл вынести эту операцию непосредственно в набор машинных команд.
Почему обычных логических операций иногда недостаточно
Пусть есть 32-битная маска:
00100100000010000000000000100000Необходимо найти первый установленный бит.
Обычный процессор может решить эту задачу последовательностью действий: проверить часть слова, выполнить сдвиг, снова проверить, повторить цикл. В другом варианте можно использовать несколько масок и ветвлений.
Каждая отдельная операция проста, но вместе они образуют небольшой алгоритм.
Если подобный поиск выполняется редко, это не проблема. Но в системном коде битовые маски встречаются постоянно: очереди событий, таблицы доступности, распределение ресурсов, состояние устройств, планирование и обработка прерываний.
Поэтому возникает вопрос: нельзя ли заменить повторяющийся программный алгоритм одной аппаратной операцией?
Что должна уметь новая команда
Самый простой вариант — искать первую единицу справа или слева. Но этого быстро оказывается недостаточно.
Для Memora8 рассматривается более универсальная операция. Она должна позволять:
- искать единицу;
- искать ноль;
- начинать не обязательно с края слова;
- двигаться к старшим или младшим битам;
- сообщать, что подходящий бит не найден.
Это позволяет использовать одну и ту же команду для большого числа системных задач.
Две формы одной операции
На машинном уровне рассматриваются две команды:
MSB
MSBIОбе выполняют один и тот же поиск.
Разница только в том, откуда берётся управляющее значение. В MSB оно находится в регистре, а в MSBI задаётся непосредственно в самой машинной команде.
Такой подход уже используется и для других операций Memora8: одна форма удобна для постоянных значений, другая — для вычисляемых во время работы программы.
Как задаётся направление поиска
В 32-битном слове биты имеют номера от 0 до 31:
bit 31 ....................... bit 0Номер бита не меняется в зависимости от направления поиска.
Управляющее значение определяет, откуда начинать и куда двигаться. Положительное значение означает движение к старшим номерам битов, отрицательное — к младшим.
Например:
+12означает начать с бита 12 и проверять:
12, 13, 14, ... 31А:
-12означает:
12, 11, 10, ... 0Таким образом, одной операцией можно искать нужный бит в обе стороны.
Как различается поиск нуля и единицы
Управляющее значение также кодирует, что именно требуется найти.
Диапазон от 0 до 31 используется для поиска единицы. Диапазон от 32 до 63 — для поиска нуля.
Например:
+0 — искать единицу от bit 0 к bit 31
-31 — искать единицу от bit 31 к bit 0
+32 — искать ноль от bit 0 к bit 31
-63 — искать ноль от bit 31 к bit 0Младшие пять бит управляющего значения определяют начальную позицию.
Поэтому значение 44 означает поиск нуля начиная с бита 12:
44 - 32 = 12Или, что удобно для аппаратной реализации:
44 & 31 = 12Один аппаратный блок вместо нескольких вариантов
На первый взгляд поиск нуля и поиск единицы выглядят как разные операции. Но аппаратно их можно объединить.
Для поиска единицы используется исходное 32-битное значение. Для поиска нуля достаточно сначала логически инвертировать его, после чего тот же самый блок поиска снова ищет единицу.
То есть процессору не нужны отдельные устройства для:
первой 1 справа
первой 1 слева
первого 0 справа
первого 0 слеваВсе варианты обслуживает один блок поиска с небольшим управлением.
Это хорошо соответствует общей логике Memora8: несколько машинных операций могут использовать один физический механизм.
Зачем начинать поиск не только с края
Если задача состоит только в поиске первой единицы, можно было бы ограничиться двумя вариантами: справа налево и слева направо.
Но в системном коде часто нужно продолжить уже начатый поиск.
Например, программа нашла установленный бит с номером 5 и хочет найти следующий. Вместо сдвига всей маски можно просто начать новый поиск с позиции 6.
Получается:
нашли bit 5
↓
следующий поиск начинаем с bit 6Такая возможность особенно удобна для обхода всех установленных битов в маске.
Пример с очередью событий
Представим, что 32 бита соответствуют 32 группам устройств:
bit 0 — группа 0
bit 1 — группа 1
...
bit 31 — группа 31Если бит равен единице, в соответствующей группе есть ожидающее событие.
Обычная программа должна последовательно проверять маску или применять несколько операций сдвига и сравнения.
С MSB процессор может сразу получить номер первой активной группы:
маска событий
↓
MSB
↓
номер активного битаПосле обработки этой группы можно продолжить поиск со следующей позиции.
Это позволяет использовать 32-битную маску как компактный аппаратно поддерживаемый указатель на события.
Поиск нуля нужен не меньше поиска единицы
Ноль тоже часто несёт полезную информацию.
Например, единица может означать занятый ресурс, а ноль — свободный. Тогда поиск первого нуля становится поиском свободного элемента.
То же самое применимо к:
- свободным слотам;
- незанятым идентификаторам;
- свободным буферам;
- доступным каналам;
- пустым позициям в таблице.
Если процессор умеет одинаково искать ноль и единицу, многие операции распределения ресурсов становятся заметно проще.
Что возвращает команда
Результатом операции является номер найденного бита от 0 до 31.
Если подходящего бита в выбранном направлении нет, возвращается специальное значение:
32Это удобно, потому что 32 не является допустимым номером бита в 32-битном слове.
Программа может сразу проверить:
0..31 — бит найден
32 — подходящего бита нетДополнительный признак или отдельный регистр состояния не требуется.
Почему не сделать это библиотечной функцией
Такую функцию можно написать программно. Вопрос не в том, возможно ли это, а в том, насколько часто она используется и сколько команд заменяет.
Если одна компактная аппаратная операция заменяет повторяющиеся циклы, ветвления и сдвиги, её добавление может быть оправдано.
При этом стоимость аппаратуры остаётся локальной. Блок поиска находится внутри процессора и не требует новых линий через всю память или между большим числом устройств.
Это снова тот случай, когда относительно необычная машинная команда может оказаться дешевле для всей системы, чем кажущаяся более простой функция.
Почему операция полезна для небольшого процессора
В больших современных процессорах подобные задачи могут скрываться за сложными командами, библиотеками и многочисленными аппаратными средствами.
Memora8 проектируется иначе. Мы стараемся выбирать небольшой набор операций, каждая из которых должна иметь понятную причину существования.
Поиск бита интересен тем, что он одновременно:
- прост для аппаратной реализации;
- часто полезен системному программному обеспечению;
- уменьшает количество ветвлений;
- упрощает обработку масок;
- хорошо соответствует 32-битной модели процессора.
Поэтому MSB и MSBI сейчас рассматриваются как часть обновлённого набора команд.
Это не просто «найти старший бит»
Название MSB обычно ассоциируется с самым старшим битом числа. В Memora8 смысл операции шире.
Она не просто ищет крайний установленный бит. Она позволяет указать начальную позицию, направление и требуемое значение бита.
Поэтому правильнее воспринимать её как универсальный поиск по 32-битной маске.
Например:
искать 1 от bit 12 вверх
искать 1 от bit 12 вниз
искать 0 от bit 12 вверх
искать 0 от bit 12 внизВсе четыре варианта выполняются одним аппаратным механизмом.
Следующий шаг — проверка стоимости
Как и другие изменения Memora8, эту операцию необходимо проверить на реальной ПЛИС.
Важно измерить:
- сколько логических элементов займёт 32-битный блок поиска;
- повлияет ли он на критический путь процессора;
- сохранится ли частота 125 МГц;
- насколько хорошо компилятор сможет использовать новую команду;
- действительно ли она сокращает системный код.
Если аппаратная стоимость окажется небольшой, а практическая польза подтвердится, MSB и MSBI станут хорошим примером того, как специализированная команда может сделать процессор не сложнее, а наоборот — проще для программирования.
Главная идея здесь такая: если система постоянно работает с битовыми масками, поиск нужного бита не обязательно каждый раз собирать из нескольких простых инструкций. Иногда правильнее сделать этот поиск одной понятной операцией процессора.
Share
