К вопросу о делении

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

В процессе исследований нового МК от известной фирмы на основе архитектуры Cortex-М4 (я об этом обязательно еще напишу) возник вопрос, насколько быстро может работать операция целочисленного деления в аппаратной реализации. Натурный эксперимент дал несколько неожиданный результат: деление 32-разрядного числа на 32-разрядное выполняется за 3 такта частоты процессора — ну ни фига ж себе, как быстро. Выяснилось, что это имеет место только с определенными операндами, но дальнейшие исследования показали, что никогда время выполнения деления не превосходит 7 тактов. Полученные результаты вызвали легкую оторопь («и это не некая фигура речи, которая неизвестно что означает, а вполне конкретный глагол» — Дивов, как всегда, бесподобен).

Ну нельзя же просто так взять и быстро поделить такие длинные числа, странно как то, но факты — упрямая вещь. Представил себе картину, что вызывает меня завтра к себе Президент РФ и ставит передо мной задачу сделать МК не хуже, чем у ARM (согласен, что картина бредовая, но чего на свете не бывает), а я растеряно на него гляжу и понимаю, что не смогу сделать такое деление таких чисел за такое время, и не оправдаю ожиданий, на меня возлагаемых (ну на самом то деле я всегда смогу втихую купить лицензию у ARM, и сделать вид, будто бы придумал все сам, многие так и делают, но от меня то ВВП ждет совсем другого, да и потом — его то я обмануть смогу, а вот себя вряд ли).

И стало мне грустно, что в ARM сидят ребята намного умнее меня, и пошел я с тоской во взоре подглядеть в Инете, как они это делают. На сайте ARM никакой информации по времени исполнения не нашел, в одном из материалов по STM32 было указано, что деление занимает от 2 до 7 тактов, что соответствует наблюдениям, но информации о том, как это делается, нет.

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

Прежде, чем смотреть мое решение, предлагаю Вам найти свое самостоятельно, а потом сравните с моим, и, если они отличаются то жду Вас в комментариях.

Итак, как нам быстро (не более, чем за 7 тактов) поделить два 32-разрядных числа с получением 32-разрядного результата.

Для начала вспомним, как вообще осуществляется деление в двоичной арифметике в
классической форме. Алгоритм достаточно прост и понятен — вычитаем делитель из делимого. Если результат неотрицателен (делим без-знаковые числа), то очередной разряд результата делаем равным единице и результат рассматриваем, как следующее делимое, в противном случае очередной бит результата равен 0. Перед следующим тактом уменьшаем делитель в два раза (либо сдвигаем его вправо, либо сдвигаем влево делимое) и уменьшаем вес бита в 2 раза (аналогичными сдвигами). Таким образом, мы получаем за один такт один бит результата и вся операция продлится 32 такта. В этом процессе есть еще начальный сдвиг, но на оценку ситуации в целом он не влияет. Будем ускорять, но как?

Обратим внимание, что полученный алгоритм сильно напоминает работу АЦП с последовательным приближением и вспоминаем, что есть и другой метод преобразования, намного более быстрый — параллельное преобразование. А что, если…

Будем вычитать из делителя не только делимое, но и делимое*2 и делимое*3 (одновременно, на трех сумматорах), тогда мы получим три бита (знаки результатов) информации, которые принимают 4 различных значения, значит из них можно извлечь сразу 2 бита результата. Далее экстраполируем подобный подход для 3,4,5 бит результата.
Чтобы получить 5 бит информации за один такт, нам потребуется 31 сумматор, на каждом из которых будет выполняться операция Делимое-Делитель*н(1-31), знаки результата пропускаем через шифратор и получаем сразу 5 бит результата. Затем сдвигаем делимое на 5 разрядов влево и повторяем до готовности. Тогда нам потребуется 32/5=6.4=>7 тактов для полного завершения операции.

Для работы нам потребуется 31+х сумматоров, вроде бы немало, но они у нас уже есть, ведь у нас есть операция умножения 32*32 за один такт, а для ее реализации без 32 сумматоров не обойтись (ну я так думаю ...), так что необходимая аппаратура у нас уже имеется, вопрос только в построении схемы контроля и кучи мультиплексоров для реализации быстрого сдвига, но это вполне решаемо.

Так что задача поделить за 7 тактов решена, остается вопрос – как можно ли сократить данное время, ведь в исследуемом МК оно бывает меньше 7. Напрашивающееся решение — на этапе подготовки алгоритма определить номер старшего значащего разряда делимого (Ч) и делителя (З) и сразу станет ясно, сколько старших битов частного равны нулю, так что мы можем пропустить первую либо несколько фаз алгоритма. Например, если Ч<З, то результат сразу равен нулю и мы завершаем операцию, наверняка можно вывести формулу для количества тактов, но мне уже стало скучно.

Интересно, что операция udiv дает только частное, хотя остаток явно где-то внутри остается лежать. В принципе, получить его нетрудно за два такта, что и делалось в исследуемом фрагменте машинного кода, выполнив псевдокод Делимое-Частное*Делитель, но это по любому 2 такта, почему не бы выдать его сразу в регистровой паре – я не знаю ответа на этот вопрос.

В общем, встретите ВВП, передайте ему, что блок деления в МК мы точно сделаем не хуже, если ему это по-прежнему интересно.

P.S.: Кстати, когда искал КДПВ (как вы заметили, так и не нашел), то заметил одну с откровенно неправильной надписью «На ноль делить нельзя». Должен сказать со всей определенностью, что на ноль делить можно, разделить нельзя. А если серьезно, то в разных архитектурах на ноль делят по разному, в х86 получаем исключение (о это незабвенная ошибка 200), в некоторых получаем делимое либо ноль, но я еще не разу не видел максимального целого. В ARM н/0 = 0/0 и получается 0.