15. ДЕЛЕНИЕ В CPU



	В отличии от умножения деление не так хорошо подвергается 
оптимизации (в частности многие RISC процессоры вообще не имеют
команды деления).

Базовый алгоримтм для деления:

Делили ли Вы в школе в столбик.
В общем то деление это сравнения и вычитание.





A = B * (C0*2^(m-n) + C1*2^(m-n-1) + .. + Cm-n*2^0) + ## частное R0*2^0 + .. + Rn*2^N ## остаток Алгоритм: +---------------+ | Ai | n битов +---------------+ k-я итерация +-------+ | B | m битов <-->+-------+ k битов 0) В начале B0 = B сдвинутое так чтобы его старший бит был MSB. 1) Вычисляем Ai-Bi (в смысле B на k-й позиции от начала A) Если перенос то Ai < Bi (Bi = B * 2^(m-n-k)) и Cj при 2^(m-n-k) = 0 Ai+1 = Ai Eсли нет переноса то Cj при 2^(m-n-k) = 1 Ai+1 = Ai - Bi Bi+1 = Bi shift left 1 И делаем так пока не достигнем итерации (n-m) ---------------------------- Ai-Bi Next 1bit of CF Ai Result ---------------------------- 1 Ai 0 0 Ai-B 1 ----------------------------


Таким образом схема для деления выглядет как: ^ | паралельный выход для остатка CF +---------+ +-----+-----| Adder |<--- Паралельный вход для делимого | | +---------+ | | ^ ^ ^ | | | | | | V |A/S | +------------+ | +--------+ +------------+ | | | логика | |конвертер в | +------+ | +--------+ |обратный код| |Buffer| | +------------+ +------+ | ^ ^ | | | | | +--------+ | | | | +-------------+ | | Shift Reg |<--- паралельный вход для делителя | +-------------+ | +------------+ +------>| Shift Reg | +------------+ | паралельный выход для результата V




Оптимизация деления: Можно ли убыстрить деление в столбик? Можно если паралельно обрабатывать не по 1 биту результата а по 2. Идея: Вычитаем Ai-Bi Ai-2Bi (2Bi = Bi + Bi) Ai-3Bi (3Bi = Bi + Bi + Bi) ------------------------------------------ Ai-Bi Ai-2Bi Ai-3Bi Next 2bit of CF CF CF Ai Result ------------------------------------------ 0 0 0 Ai-3B 11 0 0 1 Ai-2B 10 0 1 1 Ai-B 01 1 1 1 Ai 00 ------------------------------------------


Современные матричные методы деления:




Restore Division

Restore Division в смысле что остаток остается. 1. Частичный остаток = старшие разряды делимого 2. Частичный остаток << 1 бит В младший разряд идет очередная цифра частного 3. Из сдвинутого остатка вычитается делитель, анализируется знак вычитания 4. Следущая цифра частного равна 1, если результат положительный. Следущая цифра частного равна 0, если результат отрицательный, при этом делитель прибавляется обратно (restore). Действия со знаком: ------------------------------------------------- Знак остатка Знак делителя Действие ------------------------------------------------- + + -делитель + - +делитель - + +делитель - - -делитель ------------------------------------------------- 4x4 Restore array division:

Restore array cell:



SC Cell: ----------------- q r d Ci | Co S ---------+------- 0 0 0 0 | 0 0 0 0 0 1 | 0 0 0 0 1 0 | 0 0 0 0 1 1 | 1 0 0 1 0 0 | 0 1 0 1 0 1 | 1 1 0 1 1 0 | 1 1 0 1 1 1 | 1 1 1 0 0 0 | 0 0 1 0 0 1 | 0 1 1 0 1 0 | 0 1 1 0 1 1 | 1 0 1 1 0 0 | 0 1 1 1 0 1 | 1 0 1 1 1 0 | 1 0 1 1 1 1 | 1 1 -----------------


Non-Restore Division

1. Частичный остаток = старшие разряды делимого 2. Частичный остаток << 1 бит В младший разряд идет очередная цифра частного 3. Из остатка вычитается делитель, если остаток положительный к остатку прибавляется делитель, елси остаток отрицательный 4. Следущая цифра частного равна 1, если результат положительный. Следущая цифра частного равна 0, если результат отрицательный 4x4 Non-restore array division:

4x4 Non-restore array cell:



AS-Cell: ------------------- q r d Ci | Co S -----------+------- -1 0 0 0 | 0 0 -1 0 0 1 | 0 1 -1 0 1 0 | 0 1 -1 0 1 1 | 1 0 -1 1 0 0 | 0 1 -1 1 0 1 | 1 0 -1 1 1 0 | 1 0 -1 1 1 1 | 1 1 1 0 0 0 | 0 1 1 0 0 1 | 1 0 1 0 1 0 | 0 0 1 0 1 1 | 0 1 1 1 0 0 | 1 0 1 1 0 1 | 1 1 1 1 1 0 | 0 1 1 1 1 1 | 1 0 -------------------


SRT-Division

SRT (Sweeney, Robertson and Tocher) независимо друг от друга SRT - модернизация деления без востановления остатка, но в отличии от него сложение и вычитание в отдельных случаях может не выполняться. Недостаток SRT - необходимость нормализации в начале вычислений (как правило сдвигом делителя влево) (поэтому SRT активно применяют в делителях для FP - так как мантиссы и так уже храняться нормализованными).

для i-й итерации: | 1, if 2R{i-1} > = D Q{i} = | 0, if -D <= 2R{i-1} < D | -1, if 2R{i-1} < -D R{i} = 2R{i-1} - Q{i}*D



Tail-Cell:

------------------ q d0 r0 | s1 s0 ---------+-------- -1 0 -1 | 0 -1 -1 1 -1 | 0 0 -1 0 0 | 0 0 -1 1 0 | 1 -1 -1 0 +1 | 1 -1 -1 1 +1 | 1 0 0 0 -1 | 0 -1 0 1 -1 | 0 -1 0 0 0 | 0 0 0 1 0 | 0 0 0 0 +1 | 1 -1 0 1 +1 | 1 -1 +1 0 -1 | 0 0 +1 1 -1 | 0 -1 +1 0 0 | 1 -1 +1 1 0 | 0 0 +1 0 +1 | 1 0 +1 1 +1 | 1 -1 ------------------ Head-Cell:

----------------------- r2 r1 r0 | s2 s1 s0 q ---------+------------- +1 +1 +1 | +1 +1 -1 +1 +1 +1 0 | +1 0 0 +1 +1 +1 -1 | +1 0 -1 +1 +1 0 +1 | +1 0 -1 +1 +1 0 0 | 0 +1 0 +1 +1 0 -1 | 0 +1 -1 +1 +1 -1 +1 | 0 +1 -1 +1 +1 -1 0 | 0 0 0 +1 +1 -1 -1 | 0 0 -1 +1 0 +1 +1 | 0 +1 -1 +1 0 +1 0 | 0 0 0 +1 0 +1 -1 | 0 0 -1 +1 0 0 +1 | 0 0 -1 +1 0 0 0 | 0 0 0 0 0 0 -1 | 0 0 0 -1 0 -1 +1 | 0 0 0 -1 0 -1 0 | 0 0 -1 -1 0 -1 -1 | 0 -1 0 -1 -1 +1 +1 | 0 0 0 -1 -1 +1 0 | 0 0 -1 -1 -1 +1 -1 | 0 -1 0 -1 -1 0 +1 | 0 -1 0 -1 -1 0 0 | 0 -1 -1 -1 -1 0 -1 | -1 0 0 -1 -1 -1 +1 | -1 0 0 -1 -1 -1 0 | -1 0 -1 -1 -1 -1 -1 | -1 -1 0 -1 -----------------------

Index Prev Next