Как стать автором
Обновить

Комментарии 26

Всё хорошо, но при чём тут упоминание токсичных тем, ассоциированных с политикой?
Ну это шутка была, и вроде не как про политику, или, в полном соответствии с К. Прутковым «Не шути с женщинами, ибо шутки эти глупы и неприличны». А может, это так мое подсознательное прорывается?

У Пруткова ещё что-то там про фонтан было. Который прорывается.

У него было про тот фонтан, который заткнуть надо. Это вообще про мои опусы или только про упоминание в них высших должностных лиц Российской Федерации?
Предлагаю рассмотреть задачу деления с точки зрения аппаратуры
а для ее реализации без 32 сумматоров не обойтись (ну я так думаю ...)

image
Книга Харрисов про архитектуру компьютеров, схема умножения двух чисел, в явном виде сумматоры отсутствуют
Признаться, не до конца понял описание деления. Вы предлагаете программную реализацию при потенциально имеющихся аппаратных возможностях? Если да, то будет здорово для понимания добавить псевдокод или даже просто код симуляции
Так вот же они, сумматоры, в реализации, три штуки 4-разрядных сумматора, или я чего то недопонимаю.
И я ни в коем случае не предлагаю программную реализацию, просто пытаюсь представить себе возможную аппаратную.
В том то и дело, что да, вот они сумматоры, только у нас нет простого доступа ко входам и выходам каждого из них — они соединены все битами переносов и пр и пр.

Аппаратное решение — это интересно. Будет крайне интересно посмотреть это решение на HDL
Только, на мой взгляд, вы не учли такт на получение чисел [делимое*2, делимое*3...]

Честно говоря чутка запутался в алгоритме. Вот я хочу разделить 1444 на 27. Из описания я так понял что я должен делать так:
1) 1444-27=…
1444-27*2=…
1444-27*3=…
1444-27*4=…
2)...? Каков формат шифратора? Аппаратно добавлять шифратор только ради деления — не известно стоит ли того
наверное ещё кучка мультиплексоров
Ну это у нас нет доступа к ним в учебном примере, а в настоящей реализации вполне можно их входы/выходы выпустить на границу блока и тогда они будут. Речь шла имено о физическом наличии в железе.
делимое*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, что опять таки верно.

Шифратор здесь это схема, обратная дешифратору — просто выдает номер самого старшего плюса — чисто комбинационная и несложная.
Все равно не уверен что правильно понял ваш алгоритм. Вы не могли бы его описать в виде кода или псевдокода. Типа такого — классический алгоритм деления:
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;
}
Можно я опишу вместо автора? Ну по крайней мере как понял.

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;
}
В общем верно, но несколько мелких замечаний с точки зрения оптимизации:
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;
но оптимизатор может сам так сделать.
1 — OK, оставлял 62 для ясности, но связано с пунктом 2.
2 — я не хотел углубляться — lzcnt() это такой же шифратор — но просто был бы громоздкий код там, где и так понятно по словесному описанию.
3 — боюсь, что будут слишком длинные цепочки прохождений через вентили. Хотя, если делать цепочку не через все 31, а мелкими группами, может и хватить такта на всё. Это уже чисто количественная оценка на основании задержек.
4 — я выделил step_quot потому что на него умножают потом. Оптимизатор, да, может заинлайнить. А если учитывать, что это должно быть переложено на verilog/etc., он однозначно это переделает по-своему (скорее, проще всего сдвинуть входы шифратора на 1, убрав вообще вход 0, и добавить всегда единицу в позиции 31).
> Чтобы получить 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), ценой возможного дублирования операции; но чуть более умный УУ, заметив, что операции стоят парой, может переиспользовать результат первой во второй. Причины те же — так проще, чем работать с вариантом типа «а тут у нас вдруг в команде два выходных регистра».
А ведь при современных размерах в миллиарды транзисторов сделать, например, 64 параллельных сумматора — реально копейки.
Потребляемую мощность обычно надо экономить больше, чем площадь на кристалле. Иначе не было бы, например, упомянутых в статье SAR АЦП — параллельные ведь намного быстрее)
Парсер команд (самый дорогой в x86 среди ходовых архитектур), OoO шедулер с синхронизацией входных и выходных данных команд, кэши — потребляют в разы больше, чем даже 1024 сумматора.
И если в не толстом Cortex-М4 сделали быстрый делитель, то в монстре размера хотя бы i3 — он не давал бы и 0.1% затрат.
у нас есть операция умножения 32*32 за один такт, а для ее реализации без 32 сумматоров не обойтись
В железной операции умножения всего один полноценный (с ускоренным пробросом признака переноса) сумматор, остальным занимается лестница Дадда. Но, к счастью, нам реально не нужны эти сумматоры (которые, на самом деле, не сумматоры, а умножители на x1–31), достаточно с помощью таблицы от старших бит делимого и делителя получить оценку (N) и одним сравнением с xN получить сразу несколько бит результата (SRT алгоритм). Но вполне может оказаться, что таблица + пара итераций Ньютоном окажется быстрее.
Интересно, что операция udiv дает только частное, хотя остаток явно где-то внутри остается лежать… почему не бы выдать его сразу в регистровой паре – я не знаю ответа на этот вопрос.
Потому что дополнительный write-port к регистровому файлу — это дорого и редкая операция не стоит таких заморочек.
Я не понял вашего алгоритма.
Деление никак не параллелится. На каждом шаге у вас остаток, который нужно использовать на следующем шаге. Двоичный алгоритм тормозной, никто так не делает. Результат получают вычисляя его, например, побайтно, используя таблицы.
> Двоичный алгоритм тормозной, никто так не делает.

«Двоичный» это в двоичной системе, или по 1 биту за итерацию?
Если первое, то прошу назвать реальную альтернативу.
Если второе, то тут, как легко заметить из исходного теста, за итерацию получается 5 бит.

> Результат получают вычисляя его, например, побайтно, используя таблицы.

Можно ссылку на побайтную реализацию по таблицам?

А то даже знаменитый интеловский SRT (который дал FDIV bug) вычислял 2 бита за итерацию.

Тут деление в 32-ичной системе фактически. Чтобы получить очередной разряд (5 бит) по идее надо бы сдвинутый делитель вычитать из делимого, пока вычитается. Сколько раз вычли — это и записываем в ответ. Но в железе можно сделать параллельно и вычесть из делимого делитель, делитель*2,… делитель*31 одновременно и получить 31 результат и найти там самый крайний, где вычитание перескочило за 0. Эти 5 бит и записываем в ответ.

Для нахождения очередной цифры результата не обязательно параллельно вычислять 32 возможных варианта. Вы можете по старшим битам делимого и делителя по таблице найти цифру результата, один раз умножить на нее, вычесть из текущего делимого и если промазали, прибавлять делитель для восстановления делимого.
Это классическое деление в столбик.
ЗЫ Когда я реализовывал этот алгоритм там главный ньюанс выбрасывать все лидирующие нули делимого и делителя для определения цифры результата, и благодаря этому вы можете промазать только на единцу в угадывании цифры результата.

Я не специалист, может в железе это сделать сложнее, чем вариант от GarryC.

Скорее всего быстрее не получится, поскольку придется делать Делимое-Делитель*Ожидание, что займет то же самое время при Ожидаемом=31, а потом еще и корректировать — смысла в подобных манипуляциях по быстродействию не вижу.
Сэкономить в железе — вот тут не знаю, надо смотреть, общая идея была в том, что у нас уже есть 32 сумматора и их надо использовать.
Сложнее, но делается. Это как раз многобитный вариант SRT. Например, при 2 битах результата на цикл он может давать «цифру» от -2 до +2. Затем результат финализируется уже в чисто двоичный выхлоп.
(И именно он дал знаменитый Pentium FDIV bug: криво заполнили таблицу.)
Как-то было боязно, что выяснится, что при делении АРМ считает и отдаёт в инфо пять тактов за один.
Фольксвагену вон сколько лет можно было…

Про умножение и деление можно почитать в книжке: Организация ЭВМ и систем: Учебник для вузов. 3-е изд. Орлов Сергей Александрович, Цилькер Борис Яковлевич

Мне она понравилась тем, что делитель (устройство) в ней описан более менее понятно.

А так, в википедии есть статья "Алгоритм деления" (https://ru.wikipedia.org/wiki/Алгоритм_деления)

Зарегистрируйтесь на Хабре , чтобы оставить комментарий

Публикации

Истории