Нам подвернулась возможность провести небольшое, но крайне интересное тактическое учение
В процессе исследований нового МК от известной фирмы на основе архитектуры 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.
Комментарии (23)
antonsosnitzkij
20.03.2019 16:54Предлагаю рассмотреть задачу деления с точки зрения аппаратуры
а для ее реализации без 32 сумматоров не обойтись (ну я так думаю ...)
Книга Харрисов про архитектуру компьютеров, схема умножения двух чисел, в явном виде сумматоры отсутствуют
Признаться, не до конца понял описание деления. Вы предлагаете программную реализацию при потенциально имеющихся аппаратных возможностях? Если да, то будет здорово для понимания добавить псевдокод или даже просто код симуляцииGarryC Автор
20.03.2019 17:05Так вот же они, сумматоры, в реализации, три штуки 4-разрядных сумматора, или я чего то недопонимаю.
И я ни в коем случае не предлагаю программную реализацию, просто пытаюсь представить себе возможную аппаратную.antonsosnitzkij
20.03.2019 17:19В том то и дело, что да, вот они сумматоры, только у нас нет простого доступа ко входам и выходам каждого из них — они соединены все битами переносов и пр и пр.
Аппаратное решение — это интересно. Будет крайне интересно посмотреть это решение на HDL
Только, на мой взгляд, вы не учли такт на получение чисел [делимое*2, делимое*3...]
Честно говоря чутка запутался в алгоритме. Вот я хочу разделить 1444 на 27. Из описания я так понял что я должен делать так:
1) 1444-27=…
1444-27*2=…
1444-27*3=…
1444-27*4=…
2)...? Каков формат шифратора? Аппаратно добавлять шифратор только ради деления — не известно стоит ли тогоGarryC Автор
20.03.2019 18:59Ну это у нас нет доступа к ним в учебном примере, а в настоящей реализации вполне можно их входы/выходы выпустить на границу блока и тогда они будут. Речь шла имено о физическом наличии в железе.
делимое*2 делается на мультиплексоре сдвигом, это они в ARM любят, делимое*3=делимое*2+делимое — сразу на сумматоре, так что такта точно не потребуется, будут небольшие задержки на дополнительный сумматор.
Я не совсем четко описал начальный сдвиг, в приведенном Вами примере 1444=0x5A4 и старший разряд 10, 27=0x1B и старший разряд 4. Тогда для двух-битового алгоритма нужно первоначально сдвинуть делимое влево на 10-4-1-1=4 разряда, получая 432 и мы на первом такте будет считать 1444-432 1444-432*2 1444-432*3, получая результаты +++, что нам дает первые два бита результата 11хххх. После этого принимаем в качестве нового делимого 1444-432*3=148, а в качестве нового делителя 432>>2=108. На втором такте считаем 148-108 148-108*2 148-108*3 получая +--, что дает очередные два бита результата 01 и результат 1101хх. Теперь принимаем за новый делимое 148-108=40, новый делитель 108>>2=27. Считаем 40-27 40-27*2 40-27*3 получая +--, что дает последние два бита результата 01 и весь результат 110101, что верно :).
Для 5 битов за такт начальный сдвиг будет на 5 тактов и делимое станет 27*32=864. Считаем 1444-864 1444-864*2… получая +----..., что дает старшие биты результата 00001ххххх, принимаем делитель 1444-864=580 делитель 864/32=27 и считаем 580-27 580-27*2… получая ++++...-----------, что дает очередные 5 бит результата 10101 и результат 110101, что опять таки верно.
Шифратор здесь это схема, обратная дешифратору — просто выдает номер самого старшего плюса — чисто комбинационная и несложная.
Videoman
20.03.2019 20:10Все равно не уверен что правильно понял ваш алгоритм. Вы не могли бы его описать в виде кода или псевдокода. Типа такого — классический алгоритм деления:
using native_t = uint32_t; native_t dividend = x; native_t divider = y; if (divider == 0) throw std::invalid_argument("Dividing by zero"); // Count leading zeros const uint_t leadingZeroCount = lzcnt(divider); // Normalize divider native_t mask = native_t(1) << (leadingZeroCount % bit_count<native_t>()); divider <<= leadingZeroCount; // Divide normalized integers native_t result = 0; while (mask != 0) { if (dividend >= divider) { dividend -= divider; result |= mask; } divider >>= 1; mask >>= 1; }netch80
21.03.2019 09:28Можно я опишу вместо автора? Ну по крайней мере как понял.
uint32_t divide(uint32_t number, uint32_t divisor) { /* Тут использую 62 бита от лени. Можно было бы считать максимальный допустимый сдвиг, это очевидно, но громоздко. */ uint62_t rem = number; uint32_t quot = 0; uint62_t curr_divisor; // признаки "вычитание увело в отрицательные числа" bool flags[32] = {0}; for (int offset = 30; offset >= 0; offset -= 5) { curr_divisor = divisor << offset; // 31 умножитель и компаратор (на основе сумматора), // работают параллельно. parallel_for (int c = 1; c <= 31; ++c) { flags[c] = rem < curr_divisor * c; } // А тут работает приоритетный энкодер (в советских терминах - // приоритетный шифратор), выдаёт код самого младшего флага, // который true. // Если нет ни одного true, выдаёт 32. int first_seen = prio_encode(flags); // Но нам нужно на 1 меньше, потому что если вычитанием // получили минус, то это уже не годится. // Флаг [0] никогда не будет true. // Если все false, то ответ энкодера 32 превращается в // нужное нам 31. int step_quot = first_seen - 1; quot |= step_quot << offset; // Можно не повторять умножение, если сохранить результаты перед // сравнением. Но оно дешёвое, экономия минимальна. rem -= step_quot * curr_divisor; } return quot; }GarryC Автор
21.03.2019 10:25В общем верно, но несколько мелких замечаний с точки зрения оптимизации:
1. 62 явно избыточно, если мы двигаем делитель влево, то всегда вычитаем только 32 разряда из 32, зачем тащить лишнее железо.
2. начальное значение смещения в цикле считаем на основе номеров старших битов делимого и делителя, их можно получить все тем же шифратором, но немного другим.
3. Параллельное вычитание можно реализовать в стиле
задержка будет больше, но это может быть не критично, надо смотреть.flags[c] = rem [c]< curr_divisor[c]; curr_divisor[c]=curr_divisor[c-1]+curr_divisor0;
4. Результат можно накапливать сразу в
но оптимизатор может сам так сделать.quot |= (quot | (first_seen - 1)) << offset;netch80
21.03.2019 10:43+11 — OK, оставлял 62 для ясности, но связано с пунктом 2.
2 — я не хотел углубляться — lzcnt() это такой же шифратор — но просто был бы громоздкий код там, где и так понятно по словесному описанию.
3 — боюсь, что будут слишком длинные цепочки прохождений через вентили. Хотя, если делать цепочку не через все 31, а мелкими группами, может и хватить такта на всё. Это уже чисто количественная оценка на основании задержек.
4 — я выделил step_quot потому что на него умножают потом. Оптимизатор, да, может заинлайнить. А если учитывать, что это должно быть переложено на verilog/etc., он однозначно это переделает по-своему (скорее, проще всего сдвинуть входы шифратора на 1, убрав вообще вход 0, и добавить всегда единицу в позиции 31).
netch80
20.03.2019 17:06> Чтобы получить 5 бит информации за один такт, нам потребуется 31 сумматор
Крайне интересно, почему так мало делают. Времена для x86, например, выглядят как 1 такт на бит (деление 128/64 занимает до 90 тактов), это при том, что оно уже заметно оптимизировано через SRT-алгоритм. А ведь при современных размерах в миллиарды транзисторов сделать, например, 64 параллельных сумматора — реально копейки.
Или тут влияет, что на их скоростях суммирование всей длины и кодер результата — не успевают за 1 такт?
> ведь у нас есть операция умножения 32*32 за один такт, а для ее реализации без 32 сумматоров не обойтись
Даже больше, но не одновременно.
Если матрица вентилей «И» 32*32, а затем её рассматривать по диагоналям и построить дерево сумматоров — то будет сложение 63 значений => 62 сумматора, но от корня дерева до листьев будет не более 7 значений => 6 сумматоров в цепочке (нигде не ошибся?)
Дальше зависит от соотношения скоростей переключения логических элементов и длины такта, но есть шанс успеть и за один такт.
> Интересно, что операция udiv дает только частное, хотя остаток явно где-то внутри остается лежать. В принципе, получить его нетрудно за два такта, что и делалось в исследуемом фрагменте машинного кода, выполнив псевдокод Делимое-Частное*Делитель, но это по любому 2 такта, почему не бы выдать его сразу в регистровой паре – я не знаю ответа на этот вопрос.
В случае ARM, они скорее всего решили, что смысла нет, потому что умножение и вычитание дёшевы, а отклоняться от формата стандартной трёхадресной команды «операнд1, операнд2 -> результат» будет дороже для всей исполнительной системы. Функция, которая возвращает просто n%d, под aarch64 компилируется в:
f: udiv w2, w0, w1 msub w0, w2, w1, w0 ret
то есть вообще требуется только ещё одна команда.
Аналогично в RISC длинное умножение (типа 32*32->64) стараются делать через две команды (например, UMULH+MUL, SMULH+MUL), ценой возможного дублирования операции; но чуть более умный УУ, заметив, что операции стоят парой, может переиспользовать результат первой во второй. Причины те же — так проще, чем работать с вариантом типа «а тут у нас вдруг в команде два выходных регистра».
amartology
20.03.2019 17:23А ведь при современных размерах в миллиарды транзисторов сделать, например, 64 параллельных сумматора — реально копейки.
Потребляемую мощность обычно надо экономить больше, чем площадь на кристалле. Иначе не было бы, например, упомянутых в статье SAR АЦП — параллельные ведь намного быстрее)netch80
20.03.2019 17:28Парсер команд (самый дорогой в x86 среди ходовых архитектур), OoO шедулер с синхронизацией входных и выходных данных команд, кэши — потребляют в разы больше, чем даже 1024 сумматора.
И если в не толстом Cortex-М4 сделали быстрый делитель, то в монстре размера хотя бы i3 — он не давал бы и 0.1% затрат.
DrSmile
20.03.2019 19:54+2у нас есть операция умножения 32*32 за один такт, а для ее реализации без 32 сумматоров не обойтись
В железной операции умножения всего один полноценный (с ускоренным пробросом признака переноса) сумматор, остальным занимается лестница Дадда. Но, к счастью, нам реально не нужны эти сумматоры (которые, на самом деле, не сумматоры, а умножители на x1–31), достаточно с помощью таблицы от старших бит делимого и делителя получить оценку (N) и одним сравнением с xN получить сразу несколько бит результата (SRT алгоритм). Но вполне может оказаться, что таблица + пара итераций Ньютоном окажется быстрее.
Интересно, что операция udiv дает только частное, хотя остаток явно где-то внутри остается лежать… почему не бы выдать его сразу в регистровой паре – я не знаю ответа на этот вопрос.
Потому что дополнительный write-port к регистровому файлу — это дорого и редкая операция не стоит таких заморочек.
ultrinfaern
20.03.2019 20:39-1Я не понял вашего алгоритма.
Деление никак не параллелится. На каждом шаге у вас остаток, который нужно использовать на следующем шаге. Двоичный алгоритм тормозной, никто так не делает. Результат получают вычисляя его, например, побайтно, используя таблицы.netch80
21.03.2019 09:13> Двоичный алгоритм тормозной, никто так не делает.
«Двоичный» это в двоичной системе, или по 1 биту за итерацию?
Если первое, то прошу назвать реальную альтернативу.
Если второе, то тут, как легко заметить из исходного теста, за итерацию получается 5 бит.
> Результат получают вычисляя его, например, побайтно, используя таблицы.
Можно ссылку на побайтную реализацию по таблицам?
А то даже знаменитый интеловский SRT (который дал FDIV bug) вычислял 2 бита за итерацию.
wataru
21.03.2019 12:36Тут деление в 32-ичной системе фактически. Чтобы получить очередной разряд (5 бит) по идее надо бы сдвинутый делитель вычитать из делимого, пока вычитается. Сколько раз вычли — это и записываем в ответ. Но в железе можно сделать параллельно и вычесть из делимого делитель, делитель*2,… делитель*31 одновременно и получить 31 результат и найти там самый крайний, где вычитание перескочило за 0. Эти 5 бит и записываем в ответ.
ultrinfaern
23.03.2019 01:28Для нахождения очередной цифры результата не обязательно параллельно вычислять 32 возможных варианта. Вы можете по старшим битам делимого и делителя по таблице найти цифру результата, один раз умножить на нее, вычесть из текущего делимого и если промазали, прибавлять делитель для восстановления делимого.
Это классическое деление в столбик.
ЗЫ Когда я реализовывал этот алгоритм там главный ньюанс выбрасывать все лидирующие нули делимого и делителя для определения цифры результата, и благодаря этому вы можете промазать только на единцу в угадывании цифры результата.
LevOrdabesov
20.03.2019 22:44Как-то было боязно, что выяснится, что при делении АРМ считает и отдаёт в инфо пять тактов за один.
Фольксвагену вон сколько лет можно было…
amarao
Всё хорошо, но при чём тут упоминание токсичных тем, ассоциированных с политикой?
GarryC Автор
Ну это шутка была, и вроде не как про политику, или, в полном соответствии с К. Прутковым «Не шути с женщинами, ибо шутки эти глупы и неприличны». А может, это так мое подсознательное прорывается?
Shtucer
У Пруткова ещё что-то там про фонтан было. Который прорывается.
GarryC Автор
У него было про тот фонтан, который заткнуть надо. Это вообще про мои опусы или только про упоминание в них высших должностных лиц Российской Федерации?