Szybkie dzielenie

Metody szybkiego dzielenia

dzielenie sekwencyjne – czas dzielenia proporcjonalny do liczby cyfr ilorazu r = β r −

1 − q D

i

i

i

• uproszczenie wyznaczania cyfr ilorazu

→ iloraz w kodzie SD → q

i ∈ {β − ,

1 ...,1,

,

1

,

0 ...β − }

1

→ warunek zbieŜności dzielenia: | r | < | D |

i

• jednoczesne wyznaczanie kilku cyfr ilorazu

→ dzielenie w bazie β k

mnoŜenie przez odwrotność dzielnika

1

−

X = Q ⋅ D + R → Q ≅ X ⋅ D

• wynikiem algorytmu jest wyłącznie iloraz

normalizacja

• przeskalowanie dzielnika i dzielnej, tak aby ( D > 0): 2 1

− ≤ D < 1, | X|< D ⇒ | Q|<1

© Janusz Biernat, Szybkie dzielenie, 17 stycznia 2003

FDIV– 1

Szybkie dzielenie

Szybkie algorytmy dzielenia w systemach dwójkowych

w systemie SD równanie dzielenia nieodtwarzającego ma postać ( r

)

0 = X

r = 2 r −

, − D ≤ r < D , q

( i = 1, 2, ...)

i ∈ 1

{ ,

}

1

,

0

1 − q D

i

i

i

i

→ w zakresie reszt − D ≤ 2 r−

istnieje nadmiar reprezentacji ilorazu.

1 < D

i

ri

D

q = 1

q = 0

q = 1

i

i

i

2 ri –1

–2 D

– D

(0,0)

D

2 D

– D

Wykres dzielenia dla ilorazu w kodzie SD

© Janusz Biernat, Szybkie dzielenie, 17 stycznia 2003

FDIV– 2

Szybkie dzielenie

Tworzenie ilorazu w reprezentacji SD

nadmiar reprezentacji SD → elastyczna reguła wyboru cyfry ilorazu,

1, gdy 2 ri−

C

1 < −

,



q

(0 ≤ C ≤ D )

i =  0, g

d

y −

C ≤ 2 ri−

C

1 <

,

1, gdy 2 ri− C

1 ≥

.

ri

D

C

q = 1

q = 0

q = 1

i

i

i

–2 C

– C

C

2 C

2 ri –1

–2 D

– D

(0,0)

D

2 D

– C

– D

Zmodyfikowany wykres dzielenia dla ilorazu w kodzie SD

© Janusz Biernat, Szybkie dzielenie, 17 stycznia 2003

FDIV– 3

Szybkie dzielenie

Algorytm SRT

qi = 0 ⇒ zbędne czasochłonne dodawanie/odejmowania

C = D ⇒ średnio co drugą cyfrą ilorazu jest 0

• porównanie wszystkich pozycji reszty częściowej

C = 0 ⇒ wszystkie cyfry ilorazu są róŜne od 0

• czas porównania najkrótszy (1 cyfra)

⇒ dobór stałej C warunkuje czas porównania liczb w zapisie uzupełnieniowym algorytm SRT (Sweeney, Robertson, Tocher (‘58)

• tylko

1

C = spełnia nierówność C ≤ D dla dowolnej wartości 1 ≤ D < 1

2

2

• 1 D ≤ C ≤ D ⇒ | r | C ⇒

−

( − C

2

+ D < 2 r−

)

1 − q D <

C

2

− D

1

<

| r | < C

2

i

i

i

i

• 1 ≤ D < 1 i

1

C = ⇒ porównanie na 2 bitach | r | 1

r

i ≤

⇔ 1

,

1 ≤ i ≤ 1

,

0

2

2

2

problem gdy

1

| X | ≥

2

→ porównanie na 3 bitach dopóki

1

| r |

(generowana seria cyfr 1 albo 1 )

i

≥ 2

→ alternatywa – przeskalowanie dzielnej, tak aby 2| X|<| D|

© Janusz Biernat, Szybkie dzielenie, 17 stycznia 2003

FDIV– 4

Szybkie dzielenie

Optymalizacja algorytmu SRT

Przypuszczenie: czas dzielenia zaleŜy od stałej C i wartości dzielnika D

Skalowanie nieoptymalnego dzielnika

1

C = ⇒ średnia liczba działań N

1

=

n , ale gdy 17

3

< D < to N 1

= n.

2

2,67

28

4

3

3

D ≥ i q

⇒ r = 2 r − − q (1 D) ⇒ q q + → 0 q i ≠ 0

4

i

i 1

i 2

i i 1

i

17

D ≤

i q

⇒ r = 2 r − − q (2 D) ⇒ q q + → 0 q i ≠ 0

28

i

i 1

i

i i 1

i

(01 zamiast 1 x lub 0 1 zamiast 1 x )

• uŜycie 3 D oraz 3 D daje stopień redukcji około 3,7.

2

4

Wybór optymalnej wartoś ci stałej C

• eksperyment → optymalną wartością jest 6 C ≤ D 3

≤ C , ale

5

2

stała C moŜe mieć wiele bitów → długie porównanie

→ stała C określona stosownie do wartości D z dokładnością do 4 bitów D ≥ 0,1000 (1/2) 0,1001 (9/16) 0,1010 (5/8) 0,1100 (3/4) 0,1111 (15/16) C

0,0110 (3/8) 0,0111 (7/16) 0,1000 (1/2) 0,1010 (5/8) 0,1100 (3/4)

© Janusz Biernat, Szybkie dzielenie, 17 stycznia 2003

FDIV– 5

Szybkie dzielenie

Optymalizacja algorytmu SRT – przykład

29

3

D = 1

,

0 11 1

0

= > oraz

3

X = ,

0 001100 =

2

32

4

2

8

r 0= X

0, 0 1 1 0 0

2 r 0

0, 1 1 0 0 0

≥ 0,1 więc q 1=1

− D +

1, 0 0 0 1 1

r 1

1, 1 1 0 1 1

2 r 1

1, 1 0 1 1 0

q 2 = 0

2 r 2

1, 0 1 1 0 0 0

(≤ 1,1 więc q 3 = 1 lecz D ≥ 3/4)

+ D/2

0, 0 1 1 1 0 1

zatem zmiana

r 3

1, 1 1 0 1 0 1

q 3 = 0 oraz q 4 = 1

2 r 3

1, 1 0 1 0 1

2 r 4

1, 0 1 0 1 0

≤1,1 więc q 5= 1

+ D

+

0, 1 1 1 0 1

r 5

0, 0 0 1 1 1

końcowa reszta = 7/32 ×2–5

13

Q =

0

0

1

,

0

11 =

(oryginalny algorytm SRT daje

13

Q =

0

1

,

0

1 1 1 =

)

2

32

2

32

© Janusz Biernat, Szybkie dzielenie, 17 stycznia 2003

FDIV– 6

Szybkie dzielenie

ZbieŜność dzielenia w kodzie SD

Wyznaczenie cyfry ilorazu, przy warunku r < k D ( k ≤ 1), jest moŜliwe gdy i

− kD ≤ r = β r

1

− − q D < kD, ⇒ ≤ k ≤ 1

i

i 1

i

2

i wówczas

q − k ≤ β ( r / D

−

)

1

< q + k

i

i

i

NiezaleŜnie od znaku reszty, nierówność ta ma zawsze rozwiązanie, gdy q

α ≥ k(β − )

1

i ∈{α ,...,1,

,

1

,

0 ...,α}

r D–1

i

1

k

_

_

_

q = 3

q = 2

q = 1

q = 0

q = 1

q = 2

q =3

4

β r D–1

k

i–1

-4

-3

-2

-1

0

1

2

3

4

− k

−1

Znormalizowany wykres dzielenia w bazie β = 4 (zakres reszt dla 2

k = )

3

© Janusz Biernat, Szybkie dzielenie, 17 stycznia 2003

FDIV– 7

Szybkie dzielenie

Reguły wytwarzania cyfr ilorazu w systemie SD

Wyznaczenie kolejnej cyfry ilorazu jest moŜliwe, gdy suma rzutów prostych standaryzowanych ρ = β ρ

ρ

β ρ

−

(

1

− ) na oś

tworzy zbiór ciągły

i = r D

1 − q

i

i

i

i

i 1

−

ρ ( q

ρ

ρ

ρ

1

−

= j, = k) ≥

( q

−

= j + ,

1

= − k) ⇒ k ≥

i 1

i

i 1

i

2

ρ i

q = 0

q = 1

q = 2

q = 3

q = 4

q = 5

q = 6

1

q = 7

k

1

2

βρ

0

8k

i -1

0

1

2

3

4

5

6

7

8

− 12

− k

−1

Znormalizowany wykres dzielenia w bazie

3

β = 2 (β ρ

).

i −

≥ 0

1

Proste ρ

kβ ρ odwzorowują skalowanie poprzedniej reszty

i =

i 1

−

• większe k → większy margines wyboru cyfry (mniej cyfr porównywać)

• większe α ≥ k(β − )

1 → większa złoŜoność struktury logicznej

© Janusz Biernat, Szybkie dzielenie, 17 stycznia 2003

FDIV– 8

Szybkie dzielenie

Standaryzowane równanie dzielenia – wykres P-D

β r

i −

= ri + q D , i

i

= ,

1 ,

2 ...

1

q

P = β

= γ

| γ ≤

i zaleŜy tylko od

r oraz r

D (

| k ), więc

i 1

−

i

P = (γ + q) D , | γ |≤ k , q ∈{α ,..., 1 ,0,1,...α} , α ≥ k(β − ) 1

( q

j) ⇒

=

P

= (− k + j) D ≤ (γ + j) D ≤ ( k + j) D = P

j:min

j:max

P

P

= ( j

+

1

+ k ) D

j+1:max

P

= ( j

+ k ) D

j:max

∆ P

P

= ( j

+ 1 k

− ) D

j +1:min

∆ D

P

= j(

− k

) D

j:min

D

0

D min

D max

© Janusz Biernat, Szybkie dzielenie, 17 stycznia 2003

FDIV– 9

Szybkie dzielenie

Wykres P-D –reguła wyboru wartości cyfry ilorazu

• wykres symetryczny względem osi układu współrzędnych ( P× D)

• dzielnik znormalizowany n−1

n

β

≤ D

(skalowanie)

min ≤ D ≤ D max ≤ β

• warunek istnienia rozwiązania (spójności dziedziny zbioru funkcji P( D; q)) P +

= ( j +1− k) D ≤ ( j + k) D = P

j

:

1 min

j:max

• obszary P

= ( q − k) D ≤ P ≤ P

= ( q + k) D nakładają się

q:min

q:max

→ reguła wyboru wartości q, w obszarach wspólnych – linia graniczna ( j +1− k) D

≤ ( j + k) D ⇒ linią graniczną jest P= c max

min

( j +1− k) D

> ( j + k) D ⇒ linia graniczna jest schodkowa max

min

niezbędna dokładność porównania:

odległość w poziomie (∆ D) i w pionie (∆ P) linii P

oraz P

j:max

j

:

1

+ min

P

P

P(2 k − )

1

D

∆ =

−

=

,

j + 1 − k

j + k

( j + 1 − k)( j + k)

∆ P= Pj:max( D)– Pj+1:min( D)=(2 k–1) D

© Janusz Biernat, Szybkie dzielenie, 17 stycznia 2003

FDIV– 10

Szybkie dzielenie

Wykres P-D – optymalizacja porównania

Minimum ∆ D oraz ∆ P przy D = D

α ≥ k β

min oraz j = α −1 (

(

− )

1 :

2 k −1

2 k −1

D

∆

min = D min α

( −1 + k)

= D

α

( − k) α

( −1 + k)

min α − k

∆ P min=(2 k–1) D min

→ liczba porównywanych bitów części ułamkowej reszty ε P i dzielnika ε D

ε = − log P

∆

P

2

min 

ε = − log D

∆

D

2

min 

łączna liczba bitów potrzebnych do porównania zaleŜy od D max i wynosi N

= ε +

D

D

log D

2

max 

oraz (z bitem znaku reszty), poniewaŜ β

k

≤ ( k +α) ≤ β i 1 ≤ k ≤ 1,

2

N

= 1+ ε +

+α

= + ε +

β +

P

P

log ( k

) D

1

log

log D

2

max 

P

2

2

max

© Janusz Biernat, Szybkie dzielenie, 17 stycznia 2003

FDIV– 11

Szybkie dzielenie

Wykres P-D – poprawność wyboru

• punkt ( P,D) w rzeczywistości reprezentuje pole [ P, P + δ

[ D, D

δ

P 〉 ×

+ D〉

→ niezbędna weryfikacja wartości ε =

δ

=

δ

D

log2 D oraz ε P log2 P

margines bezpieczeństwa P +

= ( j +1− k)( D + δ )

j

:

1 H

D

• linia graniczna powinna mieścić się między prostymi P

oraz P

j

:

1

+ H

j:max

P

P

= ( j + k ) D

:

j max

δ D

δ P

P

= ( j + 1 − k ) ( D

+ δ )

j +1:H

D

∆ P

P

= ( j

+ 1 − k ) D

j +1:min

∆ D

D

0

D

D

min

max

Graficzne wyznaczenie dokładności badania dzielnika i reszty częściowej

© Janusz Biernat, Szybkie dzielenie, 17 stycznia 2003

FDIV– 12

Szybkie dzielenie

Dzielenie w bazie 22 (α= 2, k=2/3)

∆ D = D (2 k − )

1 (α − k) 1

=

1 ⇒

=

ε

N

D = 2 ∧

D = 4

min

min

4

∆ P = D (2 k − )

1

1 ⇒

=

ε

N

P = 2 ∧

P = 7

min

min

3

P

11,10

5 D

3

D= 1,001

11,00

q =2

4 D

3

10,10

10,00

q =1

01,10

2 D

3

01,00

1 D

3

00,10

q =0

D

00,00

D min = 01,00

01,01

01,10

01,11

10,00

= D max

© Janusz Biernat, Szybkie dzielenie, 17 stycznia 2003

FDIV– 13

Szybkie dzielenie

Dzielenie w bazie 22 (α= 2, k=2/3) – przykład D = 01,0010 (9/8) – prosta pionowa na wykresie

P= 4 ri

X = 0,01111110 (63/128), D = 01,0010 (9/8)∈[1,2) (− D = 10,1110) r 0 = X

0 0 0 , 0 1 1 1 1 1 1 0 0

P= 4 r 0

0 0 1 , 1 1 1 1 1 0 0 0 0

≥ 01,11 q 1=10

–2 D 1 0 1 , 1 1 0 0 0 0 0 0 0

r 1

1 1 1 , 1 0 1 1 1 0 0 0 0

P= 4 r 1

1 1 0 , 1 1 1 0 0 0 0 0 0

< 11,10 q 2 = 0 1

+ D

0 0 1 , 0 0 1 0 0 0 0 0 0

r 2

0 0 0 , 0 0 0 0 0 0 0 0 0

reszta = 0

W wyniku dzielenia bez reszty iloraz Q = 1

,

0 00 1 = 0

,

0 111 (7/16).

© Janusz Biernat, Szybkie dzielenie, 17 stycznia 2003

FDIV– 14

Szybkie dzielenie

Matrycowe układy dzielące

dzielenie odtwarzające

• w wierszu obliczana reszta i zaleŜnie od jej znaku cyfra ilorazu

• nie ma potrzeby odtwarzania reszty częściowej (multiplekser reszt) dzielenie nieodtwarzające

• w komórce matrycy wybór dzielnika lub jego uzupełnienia

• moŜliwość wykonywania dzielenia na operandach o dowolnym znaku

• moŜliwe wytworzenie niepoprawnej reszty końcowej (korekcja)

a)

d

b)

d

r

i

r we

i

we

+

c

c

+/−

/−

wy

we

FS

R

c wy

c

FA

we

CSR

d i

CAS

d i

r

r

wy

wy

Komórki matryc dzielenia odtwarzającego (CSR) i nieodtwarzającego (CAS)

© Janusz Biernat, Szybkie dzielenie, 17 stycznia 2003

FDIV– 15

Szybkie dzielenie

Matryca dzieląca w kodzie U2

• odejmowanie /dodawanie z propagacją przeniesień skrośnych

• czas dzielenia w matrycy zawierającej n wierszy jest rzędu 2

n

d

x

d

x

d

x

d

x

0

0

1

1

2

2

3

3

CAS

CAS

CAS

CAS

x 4

q 0

CAS

CAS

CAS

CAS

x 5

q 1

CAS

CAS

CAS

CAS

x 6

q 2

CAS

CAS

CAS

CAS

q 3

r

r

r

r

0

1

2

3

Układ matrycowy realizujący dzielenie nieodtwarzające liczb w kodzie U2

© Janusz Biernat, Szybkie dzielenie, 17 stycznia 2003

FDIV– 16

Szybkie dzielenie

Matryca dzieląca w kodzie U2 – działanie i szybkość

działanie

• wyjścia rwy skrajnych z lewej układów CAS są nieuŜywane (wytwarzają kod znaku reszty rwy = 1 – cwy, cwy = qi)

• w układzie jest wykonywane dzielenie ( X/2)/ D

→ indeksowanie cyfr ilorazu jest przesunięte o 1

(obliczana wartość Q/2, na pozycji 0 – znak ilorazu)

• propagacja przeniesienia przez wszystkie komórki w wierszu matrycy przyś pieszanie dzielenia nieodtwarzają cego w matrycy

• wybór cyfry ilorazu zaleŜy tylko od znaku poprzedniej reszty częściowej

→ uŜycie generatora CLG bez obliczania dokładnej wartości reszty

• pozostałe n bitów reszty mogą być obliczone w sumatorach CSA

→ redukcja równocześnie z wyznaczaniem kolejnej reszty częściowej

• komórka musi wytwarzać sygnały generacji i propagacji przeniesienia

→ czas dzielenia proporcjonalny do n log n.

© Janusz Biernat, Szybkie dzielenie, 17 stycznia 2003

FDIV– 17

Szybkie dzielenie

Jednoczesne wyznaczanie reszty częściowej i cyfry ilorazu

• do wyznaczenia kolejnej cyfry ilorazu nie jest potrzebna dokładna wartość poprzedniej reszty częściowej ri–1 lecz jej przybliŜenie ri–1:H. do najbardziej znaczących bitów

β ri–2:H qi–1 DN

DN

Sumator reszt

przybliŜonych

ri–1:H

Matryca PLA

qi

→ kolejna cyfra ilorazu moŜe być wyznaczona zanim zostanie obliczona dokładna wartość poprzedniej reszty częściowej.

• dokładność reszt ri–1:H musi być lepsza niŜ to wynika wykresu P-D, bo jeden z argumentów jest β-tą wielokrotnością reszty częściowej

© Janusz Biernat, Szybkie dzielenie, 17 stycznia 2003

FDIV– 18

Szybkie dzielenie

Szybki algorytm pierwiastkowania (w systemie SD)

• nadmiar reprezentacji SD pozwala zmniejszyć dokładność badania reszt 1 ≤ X < 1 ⇒ 1 ≤ Q < 1 ⇒ kolejne reszty częściowe r ( i ≥ 2) spełnią warunek 4

2

i 1

−

− 2( Q − 2− i ) ≤ r ≤ 2( Q

2 − i )

i 1

−

+

i 1

−

i 1

−

− ( Q

r

Q

⇒ reszta r

r jest poprawna ⇒ q

i = 2

i

− 2− i 1−) ≤ i ≤ (

2 − i 1

− )

1

−

i

+

1

−

1

−

i 1

−

i = 0,

zatem

1, gdy

i 1

r

Q

i −1 < −

i −1 +

− −

2

,



q

Q

r

Q

i = 

,

0 g

d

y −

i 1

i 1

i −1 +

− −

2

≤ i−1 < i−1 + − −

2

,



− i−

 ,

1

gdy

1

r

Q

i −1 ≥

i −1 + 2

.

a poniewaŜ 1 < (

i

Q

, więc tak jak w algorytmie SRT moŜna przyjąć

i − ± 2 − 1

− ) < 1

2

1

1, gdy − 2 ≤

1

ri−1 < − ,



2

q

r

i = 

,

0 g

d

y −

1 ≤

1

2

i −1 <

,



2

 ,

1

gdy

1 ≤ r

2

i −1 <

.

2

© Janusz Biernat, Szybkie dzielenie, 17 stycznia 2003

FDIV– 19

Szybkie dzielenie

Optymalizacja algorytmu SRT – przykład 2

9

17

D = 1

,

0 0 1

0

= < oraz

63

X = ,

0 00111111 =

2

16

28

2

256

r = X

0, 0 0 1 1 1 1 1 1

0

2 r

0, 0 1 1 1 1 1 1 0 < 0,1 więc q = 0

0

1

2 r

0 0, 1 1 1 1 1 1 (≥ 0,1 więc q = 1 lecz D < 17/28

1

2

−2 D + 1 0, 1 1 1 zatem zmiana

r

1 1, 1 1 0 1 1 1 0 0 q = 1, q = 0

2

1

2

2 r

1, 1 0 1 1 1 0 0 0 q = 0

2

3

2 r

1, 0 1 1 1 0 0 0 0 ≤ 1,1 więc q =

3

1

4

+ D

+ 0, 1 0 0 1

r

0, 0 0 0 0 0 0 0 0 reszta = 0

3

Otrzymaliśmy w ten sposób iloraz

7

Q = 1

,

0

0

0 1 =

, który jest jednocześnie

2

16

reprezentacją minimalną w kodzie SD zamiast jak w metodzie oryginalnej 7

Q =

0

,

0 111 =

.

2

16

© Janusz Biernat, Szybkie dzielenie, 17 stycznia 2003

FDIV– 20