Szybkie sumatory

© Janusz Biernat, 10-06-Szybkie sumatory.doc, 2 pa

ź

dziernika 2006

FAST–1

Szybko dodawania (odejmowania)

c

k

−2

x

1–m

s

1–m

c

2–m

y

1–m

s

k

−1

c

k

−1

c

k

y

k

−1

x

k

−1

FA/FS

x

–m

s

–m

c

–m

c

1–m

y

–m

s

k

−2

y

k

−2

x

k

−2

FA/FS

FA/FS

FA/FS

Schemat dodawania / odejmowania wielopozycyjnego

Propagacja przeniesienia

•

wykonanie działania na pozycji i wymaga przeniesienia z pozycji i

−

1

•

czas wytworzenia sumy (ró nicy) – stały od chwili ustalenia przeniesienia

•

gwarantowany czas wykonania dodawania lub odejmowania zale y od

najdłu szego czasu przesłania zmiany przeniesienia z pozycji najni szej

Czas dodawania n-pozycyjnego (czas dodawania jednopozycyjnego T = 2)

2 log

2

n

≤

T

Σ

≤

2 n

Szybkie sumatory

© Janusz Biernat, 10-06-Szybkie sumatory.doc, 2 pa

ź

dziernika 2006

FAST–2

Przyspieszanie dodawania dwuargumentowego

Skracanie czasu propagacji przeniesie

•

antycypacja przeniesie (carry look-ahead adder, CLA)

•

wytwarzanie przeniesie równoległych (parallel prefix adder, PPA)

•

skracanie cie ki propagacji przeniesienia (carry skip adder, CSKA)

Składanie sum blokowych

•

składanie sum warunkowych (conditional sum adder, COSA)

o

tworzenie wariantowych sum dla bloków 2

i

kolejnych pozycji

•

sumator z przeł czaniem sum cz ciowych (carry-select adder, CSLA)

o

równoległe wytwarzanie alternatywnych sum cz ciowych

•

składanie sum korygowanych (carry-increment adder, CIA)

o

korekcja sum blokowych przeniesieniami

Składanie sum redundantnych

•

nadmiarowa reprezentacja argumentów (SD)

→

dodawanie dwuetapowe

Szybkie sumatory

© Janusz Biernat, 10-06-Szybkie sumatory.doc, 2 pa

ź

dziernika 2006

FAST–3

Sumator z antycypacj przeniesie (carry look-ahead adder, CLA)

Funkcja przeniesienia

i

i

i

i

i

i

i

i

i

i

i

c

y

x

y

x

c

y

x

y

x

c

)

(

)

(

1

+

+

=

⊕

+

=

+

•

w obliczaniu przeniesienia funkcje OR (x

i

+ y

i

) i XOR (x

i

⊕

y

i

) s zamienne

•

funkcja wytwarzania (generowania) przeniesienia

1

=

=

i

i

y

x

⇒ przeniesienie wyj ciowe

1

1

=

+

i

c

i

i

i

y

x

g

=

,

•

funkcja półsumy

i

i

i

y

x

h

⊕

=

precyzyjnie okre la warunek przekazywania (propagacji) przeniesienia:

i

i

y

x

≠

⇒

i

i

c

c

=

+

1

, ale funkcja OR jest prostsza, wi c przyjmuje si

•

funkcja przekazywania (propagacji) przeniesienia (

i

p – f. wygaszania)

i

i

i

y

x

p

+

=

•

w wyra eniach na przeniesienie funkcje p

#

mo na zast pi funkcjami h

#

Szybkie sumatory

© Janusz Biernat, 10-06-Szybkie sumatory.doc, 2 pa

ź

dziernika 2006

FAST–4

Funkcje przeniesie w sumatorach CLA

Funkcje c

#

mo na rozwija wzgl dem kilku kolejnych pozycji

i

i

i

i

c

p

g

c

+

=

+

1

i

i

i

i

i

i

i

c

p

p

g

p

g

c

1

1

1

2

+

+

+

+

+

+

=

i

i

i

i

i

i

i

i

i

i

i

c

p

p

p

g

p

p

g

p

g

c

1

2

1

2

1

2

2

3

+

+

+

+

+

+

+

+

+

+

+

=

i

i

i

i

i

i

i

i

i

i

i

i

i

i

i

i

c

p

p

p

p

g

p

p

p

g

p

p

g

p

g

c

1

2

3

1

2

3

1

2

3

2

3

3

4

+

+

+

+

+

+

+

+

+

+

+

+

+

+

+

+

+

=

•

zło ono funkcji c

#

ro nie z kwadratem zasi gu s

•

bariera technologiczna – ograniczona liczba wej bramki

)

(

...

...

...

)

(

1

1

2

1

1

1

1

1

1

i

i

i

i

s

i

s

i

s

i

s

i

s

i

s

i

s

i

s

i

s

i

s

i

s

i

s

i

s

i

s

i

s

i

s

i

s

i

c

p

g

p

p

p

g

p

p

g

p

g

c

p

g

p

g

c

p

g

c

+

+

+

+

+

=

=

+

+

=

+

=

+

−

+

+

−

+

−

+

+

−

+

+

+

−

+

−

+

−

+

+

+

+

+

+

+

+

)

,

,...,

,

(

)

,

,...,

,

(

)

,

,...,

,

(

)

,

,...,

,

(

1

i

i

s

i

s

i

i

i

i

s

i

s

i

i

i

s

i

s

i

i

i

i

s

i

s

i

s

i

h

g

h

g

P

c

h

g

h

g

G

p

g

p

g

P

c

p

g

p

g

G

c

+

+

+

+

+

+

+

+

+

+

+

=

=

+

=

Szybkie sumatory

© Janusz Biernat, 10-06-Szybkie sumatory.doc, 2 pa

ź

dziernika 2006

FAST–5

Moduł sumatora z antycypacj przeniesie (CLA)

c

i+4

c

i+3

c

i+2

c

i+1

y

i

x

i

y

i+3

x

i+3

y

i+2

x

i+2

y

i+1

x

i+1

c

i

s

i+3

s

i+2

s

i+1

s

i

CLA

c

i+4

g

i

p

i

g

i+3

p

i+3

g

i+2

p

i+2

g

i+1

p

i+1

Czterobitowy sumator CLA

Szybkie sumatory

© Janusz Biernat, 10-06-Szybkie sumatory.doc, 2 pa

ź

dziernika 2006

FAST–6

Ła cuch sumatorów z antycypacj przeniesie (CLA)

s

15:12

c

12

c

16

y

15:12

x

15:12

s

11:8

c

8

y

11:8

x

11:8

s

7:4

c

4

y

7:4

x

7:4

s

3:0

0

y

3:0

x

3:0

CLA

CLA

CLA

CLA

Sumator zbudowany z kaskady bloków CLA

G,P

G,P

G,P

G,P

s

15:12

c

12

c

16

y

15:12

x

15:12

s

11:8

c

8

y

11:8

x

11:8

s

7:4

c

4

y

7:4

x

7:4

s

3:0

0

y

3:0

x

3:0

CLA

CLA

CLA

CLA

CLG

Sumator CLA z blokiem wytwarzania przeniesie CLG

Szybkie sumatory

© Janusz Biernat, 10-06-Szybkie sumatory.doc, 2 pa

ź

dziernika 2006

FAST–7

Propagacja i generowanie przeniesie – intuicje (1)

AB

c

o

u

t

c

i

n

c

out

=1 je li:

•

c

in

=1 jest przesyłane przez blok AB do wyj cia c

out

•

wewn trz bloku AB jest wytwarzane c

out

=1, za c

in

jest dowolne

A

B

c

o

u

t

c

i

n

c

m

c

out

=1 je li:

•

c

in

=1 jest przesyłane przez blok B do c

m

a nast pnie przez blok A do c

out

•

wewn trz bloku A jest wytwarzane c

out

=1, za c

m

jest dowolne

•

wewn trz bloku B jest wytwarzane c

m

=1,

a nast pnie przez blok A jest przekazywane do c

out

Szybkie sumatory

© Janusz Biernat, 10-06-Szybkie sumatory.doc, 2 pa

ź

dziernika 2006

FAST–8

Propagacja i generowanie przeniesie – intuicje (2)

G

BA

G

A

1

P

A

G

B

1

1

G

DC

G

C

P

C

G

D

1

P

BA

P

A

P

B

1

1

P

BA

P

A

P

B

1

1

P

DC

P

C

P

D

1

1

1

1

B

in

BA

BA

B

in

B

A

B

A

A

out

c

P

G

c

P

P

G

P

G

c

/

/

+

=

+

+

=

D

in

DCBA

DCBA

D

in

DC

BA

DC

BA

BA

out

c

P

G

c

P

P

G

P

G

c

/

/

+

=

+

+

=

Szybkie sumatory

© Janusz Biernat, 10-06-Szybkie sumatory.doc, 2 pa

ź

dziernika 2006

FAST–9

Funkcje grupowej antycypacji przeniesie

Wyznaczanie funkcji

przekazywania (propagacji) przeniesienia P

przez bloki sumatora (iloczyn) jest działaniem ł cznym (asocjacyjnym)

)

(

)

(

C

B

A

C

B

A

CBA

P

P

P

P

P

P

P

=

=

Wyznaczanie funkcji wytwarzania (generowania) przeniesienia G

w bloku sumatora jest tak e działaniem ł cznym (asocjacyjnym)

C

B

A

B

A

A

C

BA

BA

C

B

B

A

A

CB

A

A

CBA

G

P

P

G

P

G

G

P

G

G

P

G

P

G

G

P

G

G

+

+

=

+

=

=

+

+

=

+

=

)

(

)

(

Funkcje rekursywnie skojarzone – takie, które opisuje operator asocjacyjny

•

y

i

= x

i

•

y

i–1

, y

0

= x

0

Wyznaczanie funkcji rekursywnie skojarzonej – problem prefiksowania

Funkcje G,P s rekursywnie skojarzone przez wektorowy operator asocjacyjny

)

,

(

)

,

(

)

,

(

)

,

(

B

A

B

A

A

B

B

A

A

BA

BA

P

P

G

P

G

P

G

P

G

P

G

+

=

•

=

)

,

(

)

,

(

)

,

(

)

,

(

C

C

B

B

A

A

CBA

CBA

P

G

P

G

P

G

P

G

•

•

=

Szybkie sumatory

© Janusz Biernat, 10-06-Szybkie sumatory.doc, 2 pa

ź

dziernika 2006

FAST–10

Funkcje wytwarzania przeniesie i sum

Dla dowolnego bloku sumatora pomi dzy pozycjami i oraz k (k

≥

s

≥

i ):

i

k

i

k

i

k

c

P

G

c

,

,

1

+

=

+

przy tym

s

i

k

s

k

s

k

i

G

P

G

G

,

,

1

,

1

,

+

+

+

=

,

k

s

s

i

k

i

P

P

P

,

1

,

,

+

=

.

Poniewa

k

k

k

k

k

y

x

g

G

=

=

,

i

k

k

k

k

k

y

x

p

P

+

=

=

,

(lub

k

k

k

k

k

y

x

h

P

⊕

=

=

,

), wi c

i

k

i

j

j

k

k

k

k

i

g

p

g

p

g

G

∏

+

=

−

+

+

+

=

1

1

,

...

,

∏

=

=

k

i

j

j

k

i

p

P

,

,

Je li c

0

= 0, to warto sumy s

i

zale y tylko od warto ci funkcji G

0,i

−

1

oraz h

i

1

,

0

−

⊕

=

⊕

=

i

i

i

i

i

G

h

c

h

s

– schemat wyznaczania funkcji G

0,i

i P

0,i

mo na optymalizowa

– wszystkie funkcje G

0,i

i P

0,i

mo na wyznaczy w sekwencji log

2

n działa

Szybkie sumatory

© Janusz Biernat, 10-06-Szybkie sumatory.doc, 2 pa

ź

dziernika 2006

FAST–11

Sumatory prefiksowe (PPA)

sumator prefiksowy – parallel prefix adder, PPA

1

,

0

−

⊕

=

i

i

i

G

h

s

x

k–1

y

k–1

s

k–1

GP

x

i

y

i

x

i–1

y

i–1

x

0

y

0

s

i

s

i–1

s

0

Blok GP – wytwarzanie warto ci przeniesie c

i

= G

0,i–1

Szybkie sumatory

© Janusz Biernat, 10-06-Szybkie sumatory.doc, 2 pa

ź

dziernika 2006

FAST–12

Sumator uniwersalny (1)

Je li c

0

nie jest ustalone to

)

(

0

1

,

0

1

,

0

c

P

G

h

c

h

s

i

i

i

i

i

i

−

−

+

⊕

=

⊕

=

Aby unikn

wielokrotnego rozgał zienia sygnału c

0

w strukturze prefiksowej

mo na uzupełni sumator o blok wej ciowy CSA, redukuj c w ten sposób jeden
sygnał na pozycji najmniej znacz cej.

c

wy

c

we

=

0

c

0

y

0

x

0

y

1

x

1

y

2

x

2

y

3

x

3

y

k

–

3

x

k

–

3

y

k

–

2

x

k

–

2

y

k

–

1

x

k

–

1

sumator PPA

Wnoszone opó nienie w kategoriach AT jest takie samo jak w realizacji funkcji
G

0,i–1

+P

0,i–1

c

0

, ale nie wyst puje problem rozgał zienia sygnału c

0

(faktycznie

T

XOR

< T

AND-OR

).

Podobne rozwi zanie mo na zastosowa w uniwersalnym sumatorze U2.

Szybkie sumatory

© Janusz Biernat, 10-06-Szybkie sumatory.doc, 2 pa

ź

dziernika 2006

FAST–13

Sumator uniwersalny (2)

Je li c

0

nie jest ustalone to

)

(

0

1

,

0

1

,

0

c

P

G

h

c

h

s

i

i

i

i

i

i

−

−

+

⊕

=

⊕

=

Aby unikn

konieczno ci korekcji c

i

w sytuacji gdy c

0

nie jest znane z góry,

mo na potraktowa c

0

jako funkcj generowania przeniesienia z pozycji „–1”,

g

–1

= c

0

, gdy jednocze nie p

–1

= 0, i wtedy wszystkie funkcje P

–1,i

= 0 oraz:

)

(

[

1

1

1

1

,

0

1

,

0

−

−

−

−

−

+

+

⊕

=

c

p

g

P

G

h

s

i

i

i

i

]

wi c sumy trzeba oblicza jako:

1

,

1

1

1

,

1

1

,

1

)

(

−

−

−

−

−

−

−

⊕

=

+

⊕

=

⊕

=

i

i

i

i

i

i

i

i

G

h

c

P

G

h

c

h

s

To oznacza, e graf prefiksowy musi obejmowa n+1 pozycji. W szczególno ci:

0

,

1

1

1

,

1

0

,

1

1

1

1

,

1

1

0

0

,

1

1

0

0

0

,

1

,

,

−

−

−

−

−

−

−

−

=

+

=

=

+

=

P

p

P

G

p

g

G

p

p

P

g

p

g

G

To rozwi zanie jest szybsze ni poprzednie, a problemem jest szybka realizacja
(3 poziomy logiczne) funkcji:

0

0

1

0

1

1

1

,

1

c

p

p

g

p

g

G

+

+

=

−

.

Szybkie sumatory

© Janusz Biernat, 10-06-Szybkie sumatory.doc, 2 pa

ź

dziernika 2006

FAST–14

Tworzenie funkcji G,P

•

regularne struktury dla n = 2

k

,

•

w innych przypadkach przyj

k = int log

2

2n i usun

zb dne gał zie grafu

•

Ladner-Fischer (Sklansky)

– tworzenie funkcji G i P dla par, czwórek, ósemek, ... s siednich bitów

•

Kogge-Stone

– optymalizacja ze wzgl du na liczb rozgał zie

•

Brent-Kung

– optymalizacja dla struktur CMOS

•

Han-Carlson

– tworzenie funkcji G i P dla par, czwórek, ósemek, ... s siednich bitów
poczynaj c od bitu parzystego, potem doł czenie nieparzystych

Szybkie sumatory

© Janusz Biernat, 10-06-Szybkie sumatory.doc, 2 pa

ź

dziernika 2006

FAST–15

Przekształcenie prefiksowe Ladnera-Fischera (Sklansky) dla funkcji G,P

Poziom 0 (i = 0, 1, … , n

−

1)

G

0,0

P

i,i

= x

i

⊕

y

i

, G

i,i

= x

i

y

i

Poziom 1 (i = 0, 1, … , 2

−

1

n

−

1)

G

0,1

(G

2i,2i+1

, P

2i,2i+1

) = ( G

2i+1,2i+1

, P

2i+1,2i+1

)

l

(G

2i,2i

, P

2i,2i

)

Poziom 2 (i = 0, 1, … , 2

−

2

n

−

1; s = 2, 3)

G

0,3

, G

0,2

(G

4i,4i+s

, P

4i,4i+s

) = ( G

4i+2,4i+s

, P

4i+2,4i+s

)

l

( G

4i,4i+1

, P

4i,4i+1

)

Poziom 3 (i = 0, 1, … , 2

−

3

n

−

1; s = 4, 5, 6, 7)

G

0,7

, …, G

0,4

(G

8i,8i+s

, P

8i,8i+s

) = ( G

8i+4,8i+s

, P

8i+4,8i+s

)

l

( G

8i,8i+3

, P

8i,8i+3

)

Poziom 4 (i = 0, 1, … , 2

−

4

n

−

1; s = 8, 9, …, 15)

G

0,15

, …, G

0,8

(G

16i,16i+s

, P

16i,16i+s

) = ( G

16i+8,16i+s

, P

16i+8,16i+s

)

l

( G

16i,16i+7

,P

16i,16i+7

)

…

Szybkie sumatory

© Janusz Biernat, 10-06-Szybkie sumatory.doc, 2 pa

ź

dziernika 2006

FAST–16

Przekształcenie prefiksowe Kogge-Stone’a dla funkcji G,P

Poziom 0 (i = 0, 1, … , n

−

1)

G

0,0

P

i,i

= x

i

⊕

y

i

, G

i,i

= x

i

y

i

Poziom 1 (i = 0, 1, … , 2

−

1

n

−

1)

G

0,1

(G

i,i+1

, P

i,i+1

) = ( G

i+1,i+1

, P

i+1,i+1

)

l

(G

i,i

, P

i,i

)

Poziom 2 (s = 0, 1; i = 0, 1, … , n

−

2

2

)

G

0,s+2

= G

s+1,s+2

+ P

s+1,s+2

G

0,s

( G

0,3

) , G

0,2

(G

i,i+3

, P

i,i+3

) = ( G

i+2,i+3

, P

i+2,i+3

)

l

(G

i,i+1

, P

i,i+1

)

G

0,3

Poziom 3 (s = 0, 1, …, 2

2

−

1; i = 0, 1, … , n

−

2

3

)

G

0,s+4

= G

s+1,s+4

+ P

s+1,s+4

G

0,s

(G

0,7

) , G

0,6

, G

0,5

, G

0,4

(G

i,i+7

, P

i,i+7

) = ( G

i+4,i+7

, P

i+4,i+7

)

l

(G

i,i+3

, P

i,i+3

)

G

0,7

Poziom 4 (s = 0, 1, …, 2

3

−

1; i = 0, 1, … , n

−

2

4

)

G

0,s+8

= G

s+1,s+8

+ P

s+1,s+8

G

0,s

(G

0,15

) , … …, G

0,8

(G

i,i+15

, P

i,i+15

) = ( G

i+8,i+15

, P

i+8,i+15

)

l

(G

i,i+7

, P

i,i+7

)

G

0,15

…

Szybkie sumatory

© Janusz Biernat, 10-06-Szybkie sumatory.doc, 2 pa

ź

dziernika 2006

FAST–17

Przekształcenie prefiksowe Brenta-Kunga dla funkcji G,P

Poziom 0 (i = 0, 1, … , n

−

1)

G

0,0

P

i,i

= x

i

⊕

y

i

, G

i,i

= x

i

y

i

Poziom 1 (i = 0, 1, … , 2

−

1

n

−

1)

G

0,1

(G

2i,2i+1

, P

2i,2i+1

) = ( G

2i+1,2i+1

, P

2i+1,2i+1

)

l

(G

2i,2i

, P

2i,2i

)

Poziom 2 (i = 0, 1, … , 2

−

2

n

−

1)

G

0,3

(G

4i,4i+3

, P

4i,4i+3

) = ( G

4i+2,4i+3

, P

4i+2,4i+3

)

l

(G

4i,4i+1

, P

4i,4i+1

)

Poziom 3 (i = 0, 1, … , 2

−

3

n

−

1)

G

0,7

(G

8i,8i+7

, P

8i,8i+7

) = ( G

8i+4,8i+7

, P

8i+4,8i+7

)

l

(G

8i,8i+3

, P

8i,8i+3

)

…

Poziom m = log

2

n (T = 2

m

−

2

)

(G

0,3T

−

1

, P

0,3T

−

1

) = ( G

2T,3T

−

1

, P

2T,3T

−

1

)

l

(G

0,2T

−

1

, P

0,2T

−

1

)

G

0,3T

(G

0,n

−

1

, P

0,n

−

1

) = ( G

2T,n

−

1

, P

2T,n

−

1

)

l

(G

0,2T

−

1

, P

0,2T

−

1

)

G

0,n

−

1

…
Poziom m+r (i = (0), 1, … , 2

2

−

1, R = 2

m

−

2

−

s

), r = 1, … , m

−

2

(G

0,iR

−

1

, P

0,iR

−

1

) = ( G

2R,iR

−

1

, P

2R,iR

−

1

)

l

(G

0,2R

−

1

, P

0,2R

−

1

)

Szybkie sumatory

© Janusz Biernat, 10-06-Szybkie sumatory.doc, 2 pa

ź

dziernika 2006

FAST–18

Przekształcenie prefiksowe Han’a-Carlson’a dla funkcji G,P

Poziom 0 (i = 0, 1, … , n

−

1)

G

0,0

P

i,i

= x

i

⊕

y

i

, G

i,i

= x

i

y

i

Poziom 1 (i = 0, 1, … , 2

−

1

n

−

1)

G

0,1

(G

2i,2i+1

, P

2i,2i+1

) = ( G

2i+1,2i+1

, P

2i+1,2i+1

)

l

(G

2i,2i

, P

2i,2i

)

Poziom 2 (i = 0, 1, … , 2

−

2

n

−1

)

G

0,3

(G

2i,2i+3

, P

2i,2i+3

) = ( G

2i+2,2i+3

, P

2i+2,2i+3

)

l

(G

2i,2i+1

, P

2i,2i+1

)

Poziom 3 (s = 0, 1; i = 0, 1, … , 2

−

3

n

−

1)

(G

2i,2i+7

, P

2i,2i+7

) = ( G

2i+4,2i+7

, P

2i+4,2i+7

)

l

(G

2i,2i+3

, P

2i,2i+3

)

G

0,2s+5

= G

2s+1,2s+5

+ P

2s+1,2s+5

G

0,2s

G

0,7

, G

0,5

Poziom 4 (s = 0, 1, …, 2

2

−

1; i = 0, 1, … , 2

−

3

n

−

1)

(G

2i,2i+15

, P

2i,2i+15

) = ( G

2i+8,2i+15

, P

2i+8,2i+15

)

l

(G

2i,2i+7

, P

2i,2i+7

)

G

0,2s+9

= G

2s+1,2s+9

+ P

2s+1,2s+8

G

0,2s

G

0,15

, G

0,13

, G

0,11

, G

0,9

...
Poziom log

2

n+1 (i = 0, 1, … , 2

−

1

n

−

1)

G

0,2i

= G

2i,2i

+ P

2i,2i

G

0,2i

−

1

G

0,2i

, … , G

0,4

, G

0,2

Szybkie sumatory

© Janusz Biernat, 10-06-Szybkie sumatory.doc, 2 pa

ź

dziernika 2006

FAST–19

Prefiksowe schematy generowania i propagacji przeniesienia (PPA)

15 14 13 12 11 10

9

8

7

6

5

4

3

2

1

0

4

3

2

1

0

Graf prefixowy (Sklansky / Ladner-Fischer)

15 14 13 12 11 10

9

8

7

6

5

4

3

2

1

0

4

3

2

1

0

Graf prefixowy (Kogge & Stone)

15 14 13 12 11 10

9

8

7

6

5

4

3

2

1

0

4

3

2

1

0

5

6

Graf prefixowy (Brent–Kung)

15 14 13 12 11 10

9

8

7

6

5

4

3

2

1

0

4

3

2

1

0

5

Graf prefixowy – (Han & Carlson)

¤

– wytwarzanie funkcji G

i,i

= g

i

oraz P

i,i

= p

i

¡

– przekazywanie G oraz P

l

– operator prefiksowy (G

BA

,P

BA

) = (G

B

,P

B

)

l

(G

A

,P

A

)

Szybkie sumatory

© Janusz Biernat, 10-06-Szybkie sumatory.doc, 2 pa

ź

dziernika 2006

FAST–20

Charakterystyki grafów prefiksowych

Ladner-Fischer – log

2

n poziomów logicznych, minimum elementów GP

nierównomierne obci

enia (Sklansky)

Kogge & Stone – log

2

n poziomów logicznych, wi cej elementów GP,

rozło ona obci

alno wyj

Brent-Kung

– >log

2

n poziomów logicznych, mniej elementów GP,

stała obci

alno wyj

Han & Carlson – >log

2

n poziomów logicznych, najmniej elementów GP,

najmniejsza obci

alno wyj

Parametry sieci GP jako elementy PPA

Typ struktury

liczba ogniw GP liczba poziomów obci

enie

przeł czenia

RCA

2

/

3

n

n – 1

2

n /2

Ladner-Fischer

½ n log

2

n

log

2

n

n /2

¼ n log

2

n

Brent-Kung

2n – n log

2

n –2

2 log

2

n – 2

log

2

n + 1 ~

3

/

8

n log

2

n

Kogge & Stone

n log

2

n – n + 1

log

2

n

2

½ n log

2

n

Han & Carlson

½ n log

2

n

log

2

n + 1

2

¼ n log

2

n

Szybkie sumatory

© Janusz Biernat, 10-06-Szybkie sumatory.doc, 2 pa

ź

dziernika 2006

FAST–21

Sumy warunkowe – koncepcja

L

i

i

y

x

+

1+0 0+0 1+1 1+0 0+1 1+1 1+0 0+1

0

0

1

+

i

c

0

0

1

0

0

1

0

0

0

:i

i

s

1

0

0

1

1

0

1

1

1

1

+

i

c

1

0

1

1

1

1

1

—

1

:i

i

s

0

1

1

0

0

1

0

—

1

0

2

2

+

i

c

0

1

1

0

0

2

:

1

2

i

i

s

+

1

0

0

1

0

0

1

1

1

2

2

+

i

c

0

1

1

—

—

1

2

:

1

2

i

i

s

+

1

1

1

0

0

1

—

—

2

0

4

4

+

i

c

0

1

0

4

:

3

4

i

i

s

+

1

1

0

1

0

0

1

1

1

4

4

+

i

c

0

—

—

—

—

1

4

:

3

4

i

i

s

+

1

1

1

0

—

—

—

—

3

0

:

7

s

1

1

1

0

0

0

1

1

Szybkie sumatory

© Janusz Biernat, 10-06-Szybkie sumatory.doc, 2 pa

ź

dziernika 2006

FAST–22

Sumator sum warunkowych (conditional sum adder, COSA)

Tworzenie alternatywnych sum jedno-, dwu-, cztero-, o mio-, ...-bitowych

Poziom 0 – sumy i przeniesienia warunkowe dla osobnych bitów (

i = 0,1,...)

0

:

0

:

2

0

i

i

i

i

i

i

s

c

y

x

+

=

+

+

oraz

1

:

1

:

2

1

i

i

i

i

i

i

s

c

y

x

+

=

+

+

}

,

{

}

,

{

1

:

0

:

:

i

i

i

i

i

i

i

i

i

i

y

x

y

x

s

s

≡

⊕

=

=

s

}

,

{

}

,

{

1

1

0

1

1

i

i

i

i

i

i

i

y

x

y

x

c

c

+

=

=

+

+

+

c

Poziom p (|| – zło enie wektorów)

– warunkowe sumy

α

ri

r

ri

2

,

1

2

2

−

+

s

i przeniesienia

α

)

1

(

2

+

i

r

c

grup r = 2

p

bitów,

– dla i = 0,1,...,n·2

–p



−

1

α

α

α

α

ri

r

ri

r

ri

r

ri

r

ri

r

ri

r

ri

r

ri

ri

r

ri

c

c

2

,

1

2

1

2

,

1

2

2

2

1

2

,

1

2

2

2

2

,

1

2

2

||

]

)

1

(

[

−

+

+

−

+

+

+

−

+

+

−

+

−

+

=

s

s

s

s

,

0

2

2

2

1

2

2

2

)

1

(

2

)

1

(

r

ri

r

ri

r

ri

r

ri

i

r

c

c

c

c

c

+

+

+

+

+

−

+

=

α

α

α

Ko cowy wynik sumowania powstaje na poziomie k = log

2

n (r = 2

k

).

Szybkie sumatory

© Janusz Biernat, 10-06-Szybkie sumatory.doc, 2 pa

ź

dziernika 2006

FAST–23

Schemat sumatora sum warunkowych

s

0

s

1

s

2

s

3

c

7

L 0

x

1

y

1

ΣΣΣΣ

0/1

s

0

s

1

c

0

c

1

x

y

1 0

1 0

x

2

y

2

x

0

y

0

ΣΣΣΣ

0/1

x

3

y

3

ΣΣΣΣ

0/1

ΣΣΣΣ

0/1

1 0

1 0

x

4

y

4

x

5

y

5

ΣΣΣΣ

0/1

ΣΣΣΣ

0/1

1 0

1 0

x

6

y

6

x

7

y

7

ΣΣΣΣ

0/1

ΣΣΣΣ

0/1

1 0

1 0

1 0

1 0

1 0

1 0

1 0

1 0

1 0

1 0

1 0

1 0

1 0

L 1

L 2

L 3

s

4

s

5

s

6

s

7

ΣΣΣΣ

0/1

1

0

0

0

1

1

O miobitowy sumator sum warunkowych

T = 2 log

2

2 n , A = ½ (n log

2

n + 2n log

2

n)= 3n log

2

n

Szybkie sumatory

© Janusz Biernat, 10-06-Szybkie sumatory.doc, 2 pa

ź

dziernika 2006

FAST–24

Sumator sterowany przeniesieniem (CSLA)

Sumator multipleksowany sterowany przeniesieniem (carry-select adder)

wybór

i

k -pozycyjnych sum warunkowych zale nie od przeniesienia

x

m,l

y

m,l

x

l,k

y

l,k

x

k,i

y

k,i

x

i,

y

i,

0

0

x

m,l

y

m,l

x

l,k

y

l,k

x

k,i

y

k,i

s

m,l

s

l,k

s

k,i

s

i, 0

0

0

0

CPA

CPA

CPA

MPX

CPA

CPA

MPX

CPA

CPA

MPX

0

1

0

s

m,l

1

s

l,k

1

s

k,i

1

s

m,l

s

l,k

s

k,i

c

m +1

Schemat logiczny sumatora multipleksowanego sterowanego przeniesieniem

Sumy blokowe obliczane jednocze nie ⇒ wy sze bity

→

wi ksze bloki

Opó nienie – > 2

n

2 (optymalna liczba bloków – około

n

2 )

Szybkie sumatory

© Janusz Biernat, 10-06-Szybkie sumatory.doc, 2 pa

ź

dziernika 2006

FAST–25

Sumator z przeskokiem przeniesie (CSKA)

Suma w bloku s-bitowym zale y od przeniesienia wej ciowego (carry-in).

propagacja przeniesienia przez cały blok

→

„przeskok” przeniesienia

x

n,m

y

n,m

s

P

n,m

c

n

n,m

+1

CPA

x

m,l

y

m,l

s

P

m,l

c

m

m,l

+1

CPA

x

l,k

y

l,k

s

P

l,k

c

l

l,k

+1

CPA

x

j,i

y

j,i

s

P

j,i

c

j

j,i

+1

CPA

x

i,

y

i,

s

c

i

i,

+1

CPA

0

0

0

c

0

...

c

k+1

P

i, 0

Schemat sumatora z przeskokiem przeniesie CSKA (carry-skip adder)

Opó nienie wnoszone przez sumator CSKA zale y od
– czasu wytworzenia przeniesienia w bloku, w którym zaczyna si propagacja,
– czasu wytworzenia sumy w bloku ,w którym ko czy si propagacja,
– czasu przeskoku przeniesienia przez bloki wewn trzne.
l jednakowych bloków k-bitowych (n = kl) opó nienie wyniesie

δ

δ

δ

]

2

2

[

2

]

4

2

[

)]

1

(

2

)

1

[(

1

0

−

≥

−

+

=

−

+

−

+

−

=

∆

−

n

k

n

k

k

l

k

Szybkie sumatory

© Janusz Biernat, 10-06-Szybkie sumatory.doc, 2 pa

ź

dziernika 2006

FAST–26

Analiza szybko ci sumatora z przeskokiem przeniesie

Czas dodawania:

•

czas wytworzenia przeniesienia na wyj ciu u–go bloku wej ciowego

•

czas przeskoku przeniesienia przez [v

−

(u+1)] bloków

•

czas wytworzenia sumy od ustalenia przeniesienia na wej ciu bloku v

δ

)]

1

(

)

1

(

)

1

[(

)

,

(

−

+

−

−

+

−

=

∆

v

u

g

v

u

g

v

u

struktura

cie ka

opó nienie

max

6 bloków

4-4-4-4-4-4

(4

−

1)+4+(4

−

1) = 10

10

3-4-5-5-4-3

5-5

(5

−

1)+0+(5

−

1) = 8

8

2-5-6-5-4-2

5-6-5-4

(5

−

1)+2+(4

−

1) = 9

9

6-5-4

(6

−

1)+1+(4

−

1) = 9

9

8 bloków

1-2-3-6-6-3-2-1

3-6-6-3

(3

−

1)+2+(3

−

1) = 6

6-6

(6

−

1)+0+(6

−

1) = 10

10

1-2-4-5-5-4-2-1

4-5-5-4

(4

−

1)+2+(4

−

1) = 8

8

1-2-3-4-5-4-3-2

4-5-4

(4

−

1)+1+(4

−

1) = 7

7

9 bloków

1-2-3-4-4-4-3-2-1

2-3-4-4-4-3-2

(2

−

1)+5+(2

−

1) = 7

7

3-4-4-4-3

(3

−

1)+3+(3

−

1) = 7

7

3-4-4-4

(3

−

1)+2+(4

−

1) = 7

7

Szybkie sumatory

© Janusz Biernat, 10-06-Szybkie sumatory.doc, 2 pa

ź

dziernika 2006

FAST–27

Optymalizacja sumatora z przeskokiem przeniesie

Zało enie: standardowe opó nienia prostych funkcji

Heureza

•

ła cuchy optymalne:

je li rozmiar k bloków wytwarzaj cych mniej znacz ce pozycje sumy
jest typu

,...,k

,

i=

g

g

i

u

i

u

2

1

,

1

=

1

+

−

+

+

, to maksymalne opó nienie

g

u+k

δ

= (g

u

+ i

−

1)

δ

+(k

−

i)

δ

= (g

u

+ k

−

1)

δ

;

je li rozmiar s bloków wytwarzaj cych bardziej znacz ce pozycje sumy
jest typu

1

2

1

0

,

1

=

1

,...,s-

,

,

i=

g

g

i

v

i

v

−

−

+

+

, to maksymalne opó nienie

g

v+s

δ

= (g

v

+ i

−

1)

δ

+(s

−

i)

δ

= (g

v

+ s

−

1)

δ

;

•

ła cuchy nieoptymalne:

je li skrajne bloki ła cucha nie s skrajnymi blokami ła cuchów
optymalnych, to tworz cie k krytyczn propagacji przeniesienia.

Wnioski

•

optymalna struktura sumatora powinna by typu 1-2-3-...-3-2-1.

•

optymaln struktur sumatora jest tak e „1-2-3-...-3-2-1”\”1-2-…-s”.

Szybkie sumatory

© Janusz Biernat, 10-06-Szybkie sumatory.doc, 2 pa

ź

dziernika 2006

FAST–28

Optymalizacja sumatora z przeskokiem przeniesie - przykład

•

n-bitowy ła cuch optymalny 1-2-3-...-3-2-1 zawiera

1

2

−

n

bloków

•

sumator n-bitowy powinien mie najwy ej 

1

2

−

n

 bloków

•

(p–1)

2

≤

n

≤

p

2

–s

2

⇒ sumator n-bitowy powinien mie

≤

2(p–s) bloków

Przykład

. Sumator 32-bitowy powinien mie

≤

8 bloków (32=6

2

–2

2

)

liczba grup struktura sumatora

maksymalne opó nienie

9

2-3-4-5-4-5-4-3-2

(5

−

1)+1+(5

−

1) = 9

8

3-4-5-4-4-5-4-3

(5

−

1)+2+(5

−

1) = 10

8

2-3-4-6-6-5-4-2

(6

−

1)+2+(4

−

1) = 10

8

2-3-4-5-6-5-4-3

(6

−

1)+0+(5

−

1) = 9

Przykład

. Sumator 24-bitowy powinien mie

≤

8 bloków (24=5

2

–1

2

)

liczba grup struktura sumatora

maksymalne opó nienie

8

2-3-4-5-4-3-2-1

(5

−

1)+0+(4

−

1) = 7

8

1-2-3-4-5-4-3-2

(5

−

1)+0+(4

−

1) = 7

7

2-3-4-6-4-3-2

(6

−

1)+0+(4

−

1) = 8

Szybkie sumatory

© Janusz Biernat, 10-06-Szybkie sumatory.doc, 2 pa

ź

dziernika 2006

FAST–29

Inkrementer i dekrementer

wykonuje działanie X

±

1

→

wystarczy ła cuch półsumatorów (HA) lub półsubtraktorów (HS)

półsumator (half adder, HA) – realizuje funkcje

i

i

i

c

x

s

⊕

=

,

i

i

i

c

x

c

=

+

1

półsubtraktor (half subtracter, HS) – realizuje funkcje

i

i

i

c

x

s

⊕

=

,

i

i

i

c

x

c

=

+

1

c

k

−2

x

1

s

1

c

2

s

k

−1

c

k

−1

c

k

x

k

−1

HA/HS

x

0

s

0

1

c

1

s

k

−2

x

k

−2

HA/HS

HA/HS

HA/HS

sumator z inkrementacj wskutek przeniesienia (carry-increment adder, CIA

układ zliczaj cy – inkrementer/dekrementer ze sprz eniem

)

(

)

1

(

t

i

t

i

s

x

=

+

i zapami tywaniem stanu

)

(

0

)

(

1

)

(

2

)

(

1

,

,...,

,

{

)

(

t

t

t

k

t

k

s

s

s

s

t

S

−

−

=

Szybkie sumatory

© Janusz Biernat, 10-06-Szybkie sumatory.doc, 2 pa

ź

dziernika 2006

FAST–30

Szybko działania i zło ono sumatorów

Charakterystyki AT

•

sumator pełny FA – A = 7, T = 2 + 2

→

A T = 28

– 2

×

XOR, 1

×

OR, 2

×

AND

→

opó nienie przeniesienia 2 , sumy 2 + 2

•

sumator RCA – A = 7n, T = 2n

→

A T = 14n

2

– n

×

FA

→

opó nienie przeniesienia n

⋅

2

•

sumator CLA – A

≈

7n, T

≈

4 log n

→

A T

≈

56 n log n

– n

×

FA

→

log n bloków, opó nienie przeniesienia 2

⋅

2 log n

•

sumator CSKA – A

≈

8n, T

≈

2

⋅

n

2

→

A T

≈

32 n n

– n

×

FA+2 n

×

MPX, 2 n bloków

→

opó nienie przeniesienia 2

⋅

n

2

•

sumator CSLA – A

≈

2

⋅

7n, T

≈

n

2

2

→

A T

≈

39 n n

– 2

×

RCA,

n

2 bloków, opó nienie przeniesienia 2

⋅

n

2

•

sumator COSA – A = 3n log n, T = 2 log n

→

A T = 6 n log

2

n

– 2

×

RCA, log n poziomów MPX, opó nienie przeniesienia 2

⋅

log n

Szybkie sumatory

© Janusz Biernat, 10-06-Szybkie sumatory.doc ,2 pa

ź

dziernika 2006

FAST–13a

Przekształcenie prefiksowe Ladnera-Fischera (Sklansky) dla funkcji G,P

P

i,i

= x

i

⊕

y

i

, G

i,i

= x

i

y

i

(i = 0, 1, … , n

−

1)

G

0,0

Poziom 1 (i = 0, 1, … , 2

−

1

n

−

1)

P

2i,2i+1

= P

2i+1,2i+1

P

2i,2i

G

2i,2i+1

= G

2i+1,2i+1

+ P

2i+1,2i+1

G

2i,2i

G

0,1

Poziom 2 (i = 0, 1, … , 2

−

2

n

−

1; s = 2, 3)

P

4i,4i+s

= P

4i+2,4i+s

P

4i,4i+1

G

4i,4i+s

= G

4i+2,4i+s

+ P

4i+2,4i+s

G

4i,4i+1

G

0,3

, G

0,2

Poziom 3 (i = 0, 1, … , 2

−

3

n

−

1; s = 4, 5, 6, 7)

P

8i,8i+s

= P

8i+4,8i+s

P

8i,8i+3

G

8i,8i+s

= G

8i+4,8i+s

+ P

8i+4,8i+s

G

8i,8i+3

G

0,7

, …, G

0,4

Poziom 4 (i = 0, 1, … , 2

−

4

n

−

1; s = 8, 9, …, 15)

P

16i,16i+s

= P

16i+8,16i+s

P

16i,16i+7

G

16i,16i+s

= G

16i+8,16i+s

+ P

16i+8,16i+s

G

16i,16i+7

G

0,15

, …, G

0,8

…

Szybkie sumatory

© Janusz Biernat, 10-06-Szybkie sumatory.doc ,2 pa

ź

dziernika 2006

FAST–14a

Przekształcenie prefiksowe Kogge-Stone’a dla funkcji G,P

P

i,i

= x

i

⊕

y

i

, G

i,i

= x

i

y

i

(i = 0, 1, … , n

−

1)

G

0,0

Poziom 1 (i = 0, 1, … , n

−

2)

P

i,i+1

= P

i+1,i+1

P

i,i

, G

i,i+1

= G

i+1,i+1

+ P

i+1,i+1

G

i,i

G

0,1

Poziom 2 (s = 0, 1; i = 0, 1, … , n

−

2

2

)

P

i,i+3

= P

i+2,i+3

P

i,i+1

G

0,s+2

= G

s+1,s+2

+ P

s+1,s+2

G

0,s

G

0,3

, G

0,2

G

i,i+3

= G

i+2,i+3

+ P

i+2,i+3

G

i,i+1

(G

0,3

)

Poziom 3 (s = 0, 1, …, 2

2

−

1; i = 0, 1, … , n

−

2

3

)

P

i,i+7

= P

i+4,i+7

P

i,i+3

G

0,s+4

= G

s+1,s+4

+ P

s+1,s+4

G

0,s

G

0,7

, G

0,6

, G

0,5

, G

0,4

G

i,i+7

= G

i+4,i+7

+ P

i+4,i+7

G

i,i+3

(G

0,7

)

Poziom 4 (s = 0, 1, …, 2

3

−

1; i = 0, 1, … , n

−

2

4

)

G

0,s+8

= G

s+1,s+8

+ P

s+1,s+8

G

0,s

G

0,15

, … …, G

0,8

…

Szybkie sumatory

© Janusz Biernat, 10-06-Szybkie sumatory.doc ,2 pa

ź

dziernika 2006

FAST–15a

Przekształcenie prefiksowe Brenta-Kunga dla funkcji G,P

P

i,i

= x

i

⊕

y

i

, G

i,i

= x

i

y

i

(i = 0, 1, … , n

−

1)

G

0,0

Poziom 1 (i = 0, 1, … , 2

−

1

n

−

1)

G

2i,2i+1

= G

2i+1,2i+1

+ P

2i+1,2i+1

G

2i,2i

, P

2i,2i+1

= P

2i+1,2i+1

P

2i,2i

G

0,1

Poziom 2 (i = 0, 1, … , 2

−

2

n

−

1)

P

4i,4i+3

= P

4i+2,4i+3

P

4i,4i+1

,

G

4i,4i+3

= G

4i+2,4i+3

+ P

4i+2,4i+3

G

4i,4i+1

G

0,3

Poziom 3 (i = 0, 1, … , 2

−

3

n

−

1)

P

8i,8i+7

= P

8i+4,8i+7

P

8i,8i+3

,

G

8i,8i+7

= G

8i+4,8i+7

+ P

8i+4,8i+7

G

8i,8i+3

G

0,7

…

Poziom m = log

2

n (T = 2

m

−

2

)

G

0,3T

−

1

= G

2T,3T

−

1

+ P

2T,3T

−

1

G

0,2T

−

1

, P

0,3T

−

1

= P

2T,3T

−

1

P

0,2T

−

1

,

G

0,3T

G

0,n

−

1

= G

2T,n

−

1

+ P

2T,n

−

1

G

0,2T

−

1

, P

0,n

−

1

= P

2T,n

−

1

P

0,2T

−

1

,

G

0,n

Poziom m+1 (i = (0), 1, … , 2

2

−

1, R = 2

m

−

3

)

G

0,iR

−

1

= G

2R,iR

−

1

+ P

2R,iR

−

1

G

0,2R

−

1

G

0,13

,G

0,9

,G

0,5

P

0,iR

−

1

= P

2R,iR

−

1

P

0,2R

−

1

Szybkie sumatory

© Janusz Biernat, 10-06-Szybkie sumatory.doc ,2 pa

ź

dziernika 2006

FAST–16a

Przekształcenie prefiksowe Han’a-Carlson’a dla funkcji G,P

P

i,i

= x

i

⊕

y

i

, G

i,i

= x

i

y

i

(i = 0, 1, … , n

−

1)

G

0,0

Poziom 1 (i = 0, 1, … , 2

−

1

n

−

1)

P

2i,2i+1

= P

2i+1,2i+1

P

2i,2i

G

2i,2i+1

= G

2i+1,2i+1

+ P

2i+1,2i+1

G

2i,2i

G

0,1

Poziom 2 (i = 0, 1, … , 2

−

2

n

−1

)

P

2i,2i+3

= P

2i+2,2i+3

P

2i,2i+1

G

2i,2i+3

= G

2i+2,2i+3

+ P

2i+2,2i+3

G

2i,2i+1

G

0,3

Poziom 3 (s = 0, 1; i = 0, 1, … , 2

−

3

n

−

1)

P

2i,2i+7

= P

2i+4,2i+7

P

2i,2i+3

G

0,2s+5

= G

2s+1,2s+5

+ P

2s+1,2s+5

G

0,2s

G

0,7

, G

0,5

G

2i,2i+7

= G

2i+4,2i+7

+ P

2i+4,2i+7

G

2i,2i+3

Poziom 4 (i = 0, 1, … , 2

−

3

n

−

1)

P

2i,2i+15

= P

2i+8,2i+15

P

2i,2i+7

G

2i,2i+15

= G

2i+8,2i+15

+ P

2i+8,2i+15

G

2i,2i+7

G

0,15

, G

0,13

, G

0,11

, G

0,9

...

Poziom log

2

n+1 (i = 0, 1, … , 2

−

1

n

−

1)

G

0,2i

= G

2i,2i

+ P

2i,2i

G

0,2i

−

1

G

0,2i

, … , G

0,4

, G

0,2