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
	-----------------------