Как и обещал, сегодня расскажу про блоки умножения и деления, которые я сделал для CPU-1 несколько дней назад. Но перед этим опишу принципы умножения и деления двоичных чисел для тех, кто их не знает. Честно говоря, я и сам их не знаю полностью, по крайней мере, я не знаю, как работать со знакомыми числами. Но с этим можно будет разобраться позже, а пока разберёмся с беззнаковыми.
Умножение.
Как же мы умножаем?
Перед тем, как делать схему для умножения двоичных чисел, разберёмся с тем, как мы умножаем десятичные числа. Тут придётся вспомнить начальную школу, а именно — умножение столбиком. Я думаю, все помнят, как это делается. Берём два множителя, и, проходя по разрядам одного из них, умножаем на их значения второго, после чего складываем всё вместе. С двоичными числами всё обстоит точно так же, и даже ещё проще. Дело в том, что так как единственные две цифры в двоичной системе — 0 и 1, то и каждый разряд наших множителей будет равен либо 0, либо 1. А это значит, что мы будем либо умножать на 0, либо на 1. При умножении на 0 получаем 0, а при умножении на 1 число не изменяется. Значит, нам даже не нужно умножать при выполнении двоичного умножения. Ниже приведу пример умножения 3 на 14 в двоичном представлении.
Как видим, мы записываем наши множители в двоичном виде, затем смотрим на разряды второго множителя, и если видим 0, то пишем нули, а если 1, то переписываем под ним первый множитель, после чего складываем всё и получаем конечный результат 42. Какой вывод мы можем сделать, увидев то, как выполняется умножение в двоичном виде? А вывод мы можем сделать такой, что умножение можно заменить условным сложением со сдвигом. Мы постепенно сдвигаем первый множитель влево и смотрим на соответствующую этому сдвигу цифру во втором множителе. Если она равна 1, то мы прибавляем сдвинутый первый множитель к результату, если же она равна 0 — не прибавляем. Вот и всё. Такой алгоритм потребует для выполнения умножения столько шагов, сколько бит занимают наши множители. Перемножение 4-битных чисел займёт 4 шага, 8-битных — 8 шагов, и так далее... При этом результат умножения будет требовать в 2 раза больше бит, чем множители. При умножении 4-битных чисел получим 8-битное произведение, при умножении 8-битных чисел получим 16-битное произведение, и так далее...
Улучшения.
Можем ли мы сделать этот алгоритм ещё быстрее? Да. Во-первых, представим, что мы перемножаем 8-битные числа: 00101101×00000010. Для этого умножения потребуется 8 шагов, так как числа 8-битные. Однако 8 шагов нам здесь не нужно, во втором множителе всего одна единица, то есть лишь на одном шаге мы будем выполнять полезные вычисления, а остальные 7 мы просто тратим впустую, считая все эти нули, которые на результат не повлияют. Если бы только был способ узнать сразу, где в записи множителя находятся единицы, чтобы мы могли пройтись только по ним, пропуская все нули. И такой способ есть, и имя ему — искатель битов. По крайней мере, в Logisim такой элемент присутствует. На вход он получает число и на выходе выдаёт номер, например, старшего бита, установленного в 1. А также может сказать, есть ли вообще единицы в записи числа. Это то, что нам нужно. Если мы будем использовать искатель битов, мы сможем сразу найти единицы в записи числа, и, узнав их места в записи, использовать их как смещения для сложения. Таким образом, нам не нужно итерироваться по всему числу, а лишь по единицам, пропуская все нули. То есть вычисление 00101101×00000010 займёт всего 1 шаг, а не 8, потому что у нас одна единица во втором множителе.
Но теперь у нас новая проблема. Допустим, мы хотим посчитать не 00101101×00000010, а наоборот, 00000010×00101101. Во втором множителе у нас 4 единицы, значит это вычисление займёт 4 шага. Но мы же знаем, что в первом множителе у нас всего одна единица, а значит быстрее будет итерироваться по единицам первого множителя, а не второго. Но это мы знаем, а блоку умножения как узнать, в каком множителе меньше единиц? Для этого есть сумматор битов. Получает на вход число, на выход подаёт количество бит, установленных в 1. Теперь мы, узнав количество единиц в каждом множителе, можем их сравнить и итерироваться по единицам того множителя, где их меньше.
Конечный алгоритм.
Итак, учитывая все наши улучшения алгоритма, повторим ещё раз, что должен делать блок умножения:
- Установить регистр результата в 0.
- Получить на вход 2 множителя.
- Сравнить количество единиц в записи множителей.
- Тот множитель, в записи которого единиц меньше, поместить в регистр второго множителя, а тот, где единиц больше — в регистр первого множителя.
- Найти любую единицу в записи второго множителя. Если единиц нет, то перейти к шагу 9.
- Узнать позицию этой единицы.
- Прибавить к результату первый множитель, смещённый влево на значение, равное позиции найденной единицы во втором множителе.
- Установить найденную единицу в 0 и вернуться к шагу 5.
- Выдать результат.
Такой алгоритм производит умножение за количество итераций, равное наименьшему количеству единиц в множителях.
А теперь схема того, как я реализовал блок умножения, использующий данный алгоритм.
Блок предназначен для умножения 64-битных чисел, так как именно такого размера будет машинное слово CPU-1. И так как в результате перемножения двух 64-битных чисел получится 128-битный результат, придётся использовать для хранения результата два регистра. И вычисление немного усложняется, потому что приходится использовать не только сдвиг влево, но и вправо, но на алгоритм это не влияет.
Также хочу указать на одну интересную деталь. До тех пор, пока результ может быть записан количеством бит, не превышающим размер множителей, этот алгоритм работает и со знакомыми числами. Посмотрите внимательно на пример, который я показывал ранее:
Здесь мы умножали 3 на 14 и получили в результате 42. Однако, если мы примем второй множитель как знаковый, мы можем сказать, что мы умножаем 3 на -2. И теперь завайте посмотрим на младшую часть произведения, то есть на младшие 4 бита, что мы там видим? 1010. Если мы примем это число как знаковое, то это -6. 3×(-2)=-6, всё сходится. То же самое относится и к моему блоку умножения. Он может работать и со знаковыми числами, но только до тех пор, пока результат может быть записан в 64 бита. Мы просто откидываем старшую часть произведения, где получился какой-то мусор, и оставляем лишь младшую, где лежит знаковый результат. Однако, если для записи произведения нужно больше 64 бит, то этот алгоритм даст неверный результат для знаковых чисел, и применим только с беззнаковыми.
Деление.
Как же мы делим?
Ну, в принципе, точно так же, как и в школе — в столбик.
Посмотрим на этот пример и сделаем вывод — деление можно заменить условным вычитанием со сдвигом. Мы сдвигаем делитель влево до упора, а затем начинаем постепенно сдвигать его вправо. При этом мы пытаемся вычесть его из делимого. Если разность больше нуля — выполняем вычитание и ставим в частное единицу с соответствующим сдвигом. Если же получается заём, то вычитание не производится, а в частном с данным сдвигом ставится 0. И так до тех пор, пока не дойдём до сдвига в 0. Всё, что останется от делимого после всех этих вычитаний, будет остатком.
Улучшения.
Ну, начнём с того, что нам не обязательно сдвигать делитель до упора. Достаточно лишь до тех пор, пока он не поравняется с делимым. Таким образом, мы не будем выполнять лишние шаги, пытаясь разделить 00000100 на 0001.
Ещё одним улучшением будет останавливать деление, если в дальнейших шагах нет смысла. Я в своём блоке деления установил остановку деления в случае, если делимое становится равным нулю. Но только сейчас до меня дошло, что лучше будет, если останавливать деление, когда делимое станет меньше делителя. До этого я додумался только недавно, так что на схеме до сих пор используется старый вариант, я её переделаю позже.
И ещё одним важным улучшением будет не пытаться делить на 0. В своей схеме я сделал отдельный выход, который будет вызывать исключение при попытке деления на 0.
Конечный алгоритм.
- Установить регистр частного в 0.
- Получить делимое и делитель.
- Если делитель равен 0, вызвать исключение и не начинать деление.
- Сдвинуть делитель влево так, чтобы он поровнялся с делимым.
- Если делимое меньше несдвинутого делителя, перейти к шагу 10.
- Попытаться вычесть делитель из делимого. Если происходит заём, то не производить вычитание и перейти к шагу 9.
- Сохранить новое делимое.
- Установить в регистре частного единицу со сдвигом, равным сдвигу делителя.
- Сдвинуть делитель на 1 вправо и перейти к шагу 5.
- Выдать частное и остаток.
Со знаковыми числами данный алгоритм не работает, только с беззнаковыми.
Если кто-то имеет вопросы, или нашёл ошибку, или хочет предложить улучшенный алгоритм, или может объяснить мне, как же правильно аппаратно выполнять операции над знаковыми числами, пишите об этом в комментариях.