Szybkie sumatory

© Janusz Biernat

, AK1-7-09 Szybkie sumatory.doc, 4 listopada 2009

FAST–

1

Algorytm dodawania i odejmowania

c

k−2

x

1

s

1

c

2

y

1

s

k−1

c

k−1

c

k

y

k−1

x

k−1

FA/FS

x

0

s

0

c

0

c

1

y

0

s

k−2

y

k−2

x

k−2

FA/FS

FA/FS

FA/FS

Schemat dodawania/odejmowania binarnego

dodawanie (X+Y)

odejmowanie (X–Y)

i

i

i

i

i

i

i

i

i

i

i

i

i

i

i

c

y

x

y

x

c

y

x

y

x

c

c

y

x

s

)

(

)

(

1

+

+

=

⊕

+

=

⊕

⊕

=

+

i

i

i

i

i

i

i

i

i

i

i

i

i

i

i

c

y

x

y

x

c

y

x

y

x

c

c

y

x

s

)

(

)

(

1

⊕

+

=

⊕

+

=

⊕

⊕

=

+

Propagacja przeniesienia

• obliczenie sumy/ró nicy na pozycji i wymaga przeniesienia z pozycji i−1
• czas wytworzenia sumy/ró nicy – stały od chwili ustalenia przeniesienia
• gwarantowany czas wykonania dodawania/odejmowania zale y od

najdłu szego czasu przesłania zmiany przeniesienia

z pozycji najni szej

• czas sekwencyjnego dodawania/odejmowania n-pozycyjnego – nT

Szybkie sumatory

© Janusz Biernat

, AK1-7-09 Szybkie sumatory.doc, 4 listopada 2009

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 tymczasowych

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

– tworzenie wariantowych sum dla bloków 2

i

kolejnych pozycji

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

– równoległe wytwarzanie alternatywnych sum cz ciowych

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

– korekcja sum blokowych przeniesieniami

• obliczanie i korekcja sum tymczasowych (ELM)

Składanie sum redundantnych

• nadmiarowa reprezentacja argumentów (SD) → dodawanie dwuetapowe

Teoretycznie osi galny czas dodawania/odejmowania n-pozycyjnego: T log

2

n

Szybkie sumatory

© Janusz Biernat

, AK1-7-09 Szybkie sumatory.doc, 4 listopada 2009

FAST–

3

Wytwarzanie i propagacja przeniesie w dodawaniu

Funkcja przeniesienia mo e mie jedn z równowa nych form

i

i

i

i

i

i

i

i

i

i

i

c

y

x

y

x

c

y

x

y

x

c

)

(

)

(

1

+

+

=

⊕

+

=

+

poniewa a+b=a⊕b+ab (OR(a,b) = XOR(a,b) + ab). Składowymi wyra enia s :

• funkcja wytwarzania (generowania) przeniesienia, okre laj ca warunki

przy których przeniesienie wyj ciowe c

i

+1

=1 niezale nie od c

i

:

i

i

i

y

x

g =

,

• funkcja półsumy, która tak e okre la warunki przekazywania (propagacji)

przeniesienia (

i

i

y

x ≠

⇒

i

i

c

c

=

+1

):

i

i

i

y

x

h

⊕

=

W wyra eniach na przeniesienie mo e j zast pi

• (nadmiarowa) funkcja przekazywania przeniesienia (

i

p

– f. wygaszania)

i

i

i

y

x

p

+

=

UWAGA:
W wyra eniach na przeniesienie funkcje p

#

i h

#

s wzajemnie zamienne.

Szybkie sumatory

© Janusz Biernat

, AK1-7-09 Szybkie sumatory.doc, 4 listopada 2009

FAST–

4

Wytwarzanie i propagacja przeniesie w odejmowaniu

Funkcja po yczki (przeniesienia wstecznego) mo e mie jedn z form

i

i

i

i

i

i

i

i

i

i

i

c

y

x

y

x

c

y

x

y

x

c

)

(

)

(

1

+

+

=

⊕

+

=

+

poniewa a+b=a⊕b+ab (OR(a,b)=XOR(a,b)+ab). Składowymi wyra enia s :

• funkcja wytwarzania (generowania) po yczki, okre laj ca warunki przy

których po yczka z wy szej pozycji c

i

+1

=1 niezale nie od c

i

:

i

i

i

y

x

g =

,

• funkcja półró nicy, która okre la te warunki przekazywania (wstecznej

propagacji

) po yczki (

i

i

y

x =

⇒

i

i

c

c

=

+1

):

i

i

i

y

x

h

⊕

=

W wyra eniach na po yczki mo e j zast pi

• (nadmiarowa) funkcja przekazywania po yczki (

i

p

– f. wygaszania)

i

i

i

y

x

p

+

=

UWAGA:
W wyra eniach na po yczki funkcje p

#

i h

#

s wzajemnie zamienne.

Szybkie sumatory

© Janusz Biernat

, AK1-7-09 Szybkie sumatory.doc, 4 listopada 2009

FAST–

5

Propagacja i generowanie przeniesie – intuicje (1)

HL

c



c





c

out

=1 je li:

• c

in

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

out

• wewn trz bloku HL jest wytwarzane c

out

=1, za c

in

jest dowolne

H

L

c





c



c

c

out

=1 je li:

• c

in

=1 jest przesyłane przez blok L do c

m

a nast pnie przez blok H do c

out

• wewn trz bloku H jest wytwarzane c

out

=1, za c

m

jest dowolne

• wewn trz bloku L jest wytwarzane c

m

=1,

a nast pnie przez blok H jest przekazywane do c

out

Uwaga

: Analogiczne zale no ci mo na poda dla po yczek w odejmowaniu

Szybkie sumatory

© Janusz Biernat

, AK1-7-09 Szybkie sumatory.doc, 4 listopada 2009

FAST–

6

Propagacja i generowanie przeniesie – intuicje (2)

G

HL

=1

G

H

=1

1

P

H

=1

G

L

=1

1

1

G

F

=1

P

HL

=1

P

H

=1

P

L

=1

1

1

P

HL

=1

P

H

=1

P

L

=1

1

1

P

F

=1

1

1

1

G

HLF

=1

P

HLF

=1

L

in

hl

HL

L

in

L

H

L

H

H

out

c

P

G

c

P

P

G

P

G

c

+

=

+

+

=

F

in

HLF

HLF

F

in

F

HL

F

HL

HL

out

c

P

G

c

P

P

G

P

G

c

+

=

+

+

=

Szybkie sumatory

© Janusz Biernat

, AK1-7-09 Szybkie sumatory.doc, 4 listopada 2009

FAST–

7

Funkcje grupowej antycypacji przeniesie

Wyznaczanie funkcji przekazywania (propagacji) przeniesienia P

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

F

L

H

F

L

H

HLF

P

P

P

P

P

P

P

=

=

Wyznaczanie funkcji wytwarzania (generowania) przeniesienia G

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

F

L

H

L

H

H

F

HL

HL

F

L

L

H

H

LF

H

H

HLF

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

L

H

L

H

H

L

L

H

H

HL

HL

P

P

G

P

G

P

G

P

G

P

G

+

=

•

=

F

F

L

L

H

H

HLF

HLF

P

G

P

G

P

G

P

G

•

•

=

Szybkie sumatory

© Janusz Biernat

, AK1-7-09 Szybkie sumatory.doc, 4 listopada 2009

FAST–

8

Funkcje wytwarzania przeniesie i sum

Dla dowolnego bloku sumatora pomi dzy pozycjami i oraz k (k ≥ s ≥ i ):

i

i

k

i

k

k

c

P

G

c

:

:

1

+

=

+

przy tym

i

s

s

k

s

k

i

k

G

P

G

G

:

1

:

1

:

:

+

+

+

=

,

i

s

s

k

i

k

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

i

k

g

p

g

p

g

G

∏

+

=

−

+

+

+

=

1

1

:

...

,

∏

=

=

k

i

j

j

i

k

p

P

:

,

– schemat wyznaczania funkcji G

i

:0

i P

i

:0

mo na optymalizowa

– wszystkie funkcje G

i

:0

i P

i

:0

mo na wyznaczy w sekwencji log

2

n

działa

Warto sumy s

i

zale y od h

i

, warto ci funkcji G

i−

1:0

, P

i−

1:0

oraz c

0

:

)

(

0

0

:

1

0

:

1

c

P

G

h

c

h

s

i

i

i

i

i

i

−

−

+

⊕

=

⊕

=

Szybkie sumatory

© Janusz Biernat

, AK1-7-09 Szybkie sumatory.doc, 4 listopada 2009

FAST–

9

Sumator z antycypacj przeniesie (carry look-ahead adder, 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

+

+

+

+

+

+

+

+

+

+

+

=

=

+

=

Uwaga

: Analogiczne zale no ci mo na poda dla po yczek w odejmowaniu

Szybkie sumatory

© Janusz Biernat

, AK1-7-09 Szybkie sumatory.doc, 4 listopada 2009

FAST–

10

Moduł sumatora z antycypacj przeniesie (CLA)

c

i

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

s

i

+3

s

i

+2

s

i

+1

s

i

CLA

g

i

p

i

g

i

+3

p

i

+3

g

i

+2

p

i

+2

g

i

+1

p

i

+1

P

i

+4:i

G

i

+4:i

Czterobitowy sumator CLA z sygnałami G,P dla bloku CLG

Szybkie sumatory

© Janusz Biernat

, AK1-7-09 Szybkie sumatory.doc, 4 listopada 2009

FAST–

11

Wielomodułowy sumatorów z antycypacj przeniesie (CLA)

c

0

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

y

3:0

x

3:0

CLA

CLA

CLA

CLA

Sumator zbudowany z kaskady bloków CLA

GP

3:0

GP

7:4

GP

11:8

GP

15:12

c

0

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

y

3:0

x

3:0

CLA

CLA

CLA

CLA

CLG

Sumator CLA z blokiem wytwarzania przeniesie CLG

Szybkie sumatory

© Janusz Biernat

, AK1-7-09 Szybkie sumatory.doc, 4 listopada 2009

FAST–

12

Sumatory prefiksowe (PPA)

sumator prefiksowy – parallel prefix adder, PPA

blok GP – wytwarzanie warto ci wszystkich przeniesie

0

0

:

1

0

:

1

c

P

G

c

i

i

i

−

−

+

=

)

(

0

0

:

1

0

:

1

c

P

G

h

c

h

s

i

i

i

i

i

i

−

−

+

⊕

=

⊕

=

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

c

0

Je li c

0

=0, to c

i

=G

i

–1:0

i wtedy

0

:

1

−

⊕

=

⊕

=

i

i

i

i

i

G

h

c

h

s

, w przeciwnym razie

problem: silne rozgał zienie sygnału przeniesienia wej ciowego c

0

Szybkie sumatory

© Janusz Biernat

, AK1-7-09 Szybkie sumatory.doc, 4 listopada 2009

FAST–

13

Sumator prefiksowy z redukcj rozgał zienia

Aby unikn

rozgał ziania sygnału c

0

w obliczaniu

0

0

:

1

0

:

1

c

P

G

c

i

i

i

−

−

+

=

mo na:

a) doł czy blok wej ciowy CSA, redukuj cy sygnał c

0

c

wy

c

we

=

c

y

x

y



x



y



x



y



x



y

k





x

k





y

k





x

k





y

k





x

k





sumator PPA













































b) potraktować c

0

jako funkcję generowania przeniesienia z pozycji „–1”:

g

–1

= c

0

, zaś c

–1

= 0. Wtedy w sumatorze obejmującym n+1 pozycji mamy:

)

(

1

:

0

1

:

1

1

:

1

1

:

1

−

−

−

−

−

+

⊕

=

⊕

=

⊕

=

G

P

G

h

G

h

c

h

s

i

i

i

i

i

i

i

i

co jest równoważne zastąpieniu sygnału g

0

przez

0

0

0

1

0

0

1

:

0

*

0

c

p

g

g

p

g

G

g

+

=

+

=

=

−

−

Tworzenie alternatywnego sygnału p

0

jest zbędne, bo c

–1

= 0, więc

*

0

1

g

c =

.

W obu wersjach opóźnienie T jest takie jak w realizacji funkcji G

i

–1:0

+P

i

–1:0

c

0

.

Podobne rozwiązania można zastosować w uniwersalnym sumatorze U2.

Szybkie sumatory

© Janusz Biernat

, AK1-7-09 Szybkie sumatory.doc, 4 listopada 2009

FAST–

14

Zasady konstrukcji sieci prefiksowej GP

Węzeł sieci GP realizuje funkcje

)

,

(

)

,

(

)

,

(

)

,

(

L

H

L

H

H

L

L

H

H

HL

HL

P

P

G

P

G

P

G

P

G

P

G

+

=

•

=

Zasada konstrukcji struktury GP:

integracja funkcji G

H

i P

H

oraz G

L

i P

L

obejmujących sąsiadujące bloki H i L:

• bloki H i L

powinny być styczne

• bloki H i L

nie mogą być rozdzielone

• bloki H i L mogą mieć część wspólną – funkcje G

HL

i P

HL

są nadmiarowe

integracja nadmiarowa

integracja optymalna

integracja błędna

• regularne struktury dla n = 2

k

wejść (pozycji),

• w innych przypadkach przyjąć k = int (1+log

2

n

) i usunąć zbędne gałęzie

(sieć integrującą 2

k

–1

pozycji połączyć siecią integrującą pozostałe wejścia)

Szybkie sumatory

© Janusz Biernat

, AK1-7-09 Szybkie sumatory.doc, 4 listopada 2009

FAST–

15

Przekształcenie prefiksowe Ladnera-Fischera (Sklansky’ego)*

minimalna liczba elementów

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

1:0

(G

2i+1:2i

, P

2i+1:2i

) = ( 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

3:0

, G

2:0

(G

4i+s:4i

, P

4i+s:4i

) = ( G

4i+s:4i+2

, P

4i+s:4i+2

) l ( G

4i+1:4i

, P

4i+1:4i

)

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

− 3

n−

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

G

7:0

, …, G

4:0

(G

8i+s,8i

, P

8i+s,8i

) = ( G

8i+s,8i+4

, P

8i+s,8i+4

) l ( G

8i+3,8i

, P

8i+3,8i

)

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

− 4

n−

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

G

15:0

, …, G

8:0

(G

16i+s,16i

, P

16i+s,16i

) = ( G

16i+s,16i+8

, P

16i+s,16i+8

) l ( G

16i+7,16i

, P

16i+7,16i

)

…

Szybkie sumatory

© Janusz Biernat

, AK1-7-09 Szybkie sumatory.doc, 4 listopada 2009

FAST–

16

Przekształcenie prefiksowe Kogge-Stone’a*

minimalizacja rozgał zie

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

1:0

(G

i

+1:i

, P

i

+1:i

) = ( 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

s

+2:0

= G

s

+2,s+1

+ P

s

+2,s+1

G

s

:0

( G

3:0

) , G

2:0

(G

i

+3:i

, P

i

+3:i

) = ( G

i

+3,i+2

, P

i

+3,i+2

)l (G

i,i

+1

, P

i,i

+1

)

G

3:0

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

2

−1; i = 0, 1, … , n−2

3

)

G

s

+4:0

= G

s

+1,s+4

+ P

s

+1,s+4

G

s

:0

(G

7:0

) , G

6:0

, G

5:0

, G

4:0

(G

i

+7:i

, P

i

+7:i

) = ( G

i

+7,i+4

, P

i

+7,i+4

)l (G

i

+3:i

, P

i

+3:i

)

G

7:0

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

3

−1; i = 0, 1, … , n−2

4

)

G

s

+8:0

= G

s

+8,s+1

+ P

s

+8,s+1

G

s

:0

(G

15:0

) , … …, G

8:0

(G

i

+15:i

, P

i

+15:i

) = ( G

i

+15,i+8

, P

i

+15,i+8

)l (G

i

+7:i

, P

i

+7:i

)

G

15:0

…

Szybkie sumatory

© Janusz Biernat

, AK1-7-09 Szybkie sumatory.doc, 4 listopada 2009

FAST–

17

Przekształcenie prefiksowe Brenta-Kunga*

optymalizacja struktury CMOS

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

1:0

(G

2i+1:2i

, P

2i+1:2i

) = ( 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

3:0

(G

4i+3:4i

, P

4i+3:4i

) = ( G

4i+3:4i+2

, P

4i+3:4i+2

) l ( G

4i+1:4i

, P

4i+1:4i

)

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

− 3

n−

1)

G

7:0

(G

8i+7:8i

, P

8i+7:8i

) = ( G

8i+7:8i+4

, P

8i+7:8i+4

) l ( G

8i+3:8i

, P

8i+3:8i

)

…

Poziom m = log

2

n

(T = 2

m−

2

)

(G

3T−1:0

, P

3T−1:0

) = ( G

3T −1:2T

, P

3T −1:2T

)l (G

2T −1:0

, P

2T −1:0

)

G

3T:0

(G

0,n−1:0

, P

n−

1:0

) = ( G

n−

1:2T

, P

n−

1:2T

)l (G

2T −1:0

, P

2T −1:0

)

G

n −

1:0

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

2

−1, R = 2

m−

2−s

), r = 1, … , m−2

(G

iR−

1:0

, P

iR−

1:0

) = ( G

iR−

1: 2R

, P

iR−

1: 2R

)l (G

2R −1:0

, P

2R −1:0

)

Szybkie sumatory

© Janusz Biernat

, AK1-7-09 Szybkie sumatory.doc, 4 listopada 2009

FAST–

18

Przekształcenie prefiksowe Han’a-Carlsona*

najpierw integracja rozł cznych par

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

1:0

(G

2i+1:2i

, P

2i+1:2i

) = ( 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

3:0

(G

2i+3:2i

, P

2i+3:2i

) = ( G

2i+3:2i+2

, P

2i+3:2i+2

) l ( G

2i+1:2i

, P

2i+1:2i

)

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

− 3

n−

1, s = 0, 1)

(G

2i+7:2i

, P

2i+7:2i

) = ( G

2i+7:2i+4

, P

2i+7:2i+4

) l ( G

2i+3:2i

, P

2i+3:2i

)

G

2s+5:0

= G

2s+5,2s+1

+ P

2s+5,2s+1

G

2s:0

G

7:0

, G

5:0

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

2

−1; i = 0, 1, … , 2

− 3

n−

1)

(G

2i+15:2i

, P

2i+15:2i

) = ( G

2i+15:2i+8

, P

2i+15:2i+8

) l ( G

2i+7:2i

, P

2i+7:2i

)

G

2s+9:0

= G

2s+9,2s+1

+ P

2s+9,2s+1

G

2s:0

G

15:0

, G

13:0

, G

11:0

, G

9:0

...
Poziom log

2

n

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

− 1

n−

1)

G

2i:0

= G

2i:2i

+ P

2i:2i

G

2i−1:0

G

2i:0

, … , G

4:0

, G

2:0

Szybkie sumatory

© Janusz Biernat

, AK1-7-09 Szybkie sumatory.doc, 4 listopada 2009

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

, AK1-7-09 Szybkie sumatory.doc, 4 listopada 2009

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

, AK1-7-09 Szybkie sumatory.doc, 4 listopada 2009

FAST–

21

Sumator ELM – koncepcja*

Obliczona wartość początkowa sumy h

i

= s

i:i

na może ulec zmianie, jeśli c

i

=1.

Niech s

i:r

oznacza tymczasow sumę na pozycji i z uwzględnieniem wszystkich

wcześniejszych wejść x

#

, y

#

, począwszy od wejścia x

r

, y

r

. Mamy:

)

(

,

0

0

:

1

0

:

1

0

:

:

1

:

c

H

G

h

s

G

h

s

i

i

i

i

r

i

i

r

i

−

−

−

+

⊕

=

⊕

=

Z rekurencyjnego powiązania funkcji G

i:j

wynika dalej, że (i>r>j):

,

))

(

(

)

(

:

1

:

1

:

1

:

:

1

:

1

:

1

:

1

:

:

1

:

1

:

1

:

1

:

1

:

1

:

j

r

r

i

r

i

r

i

j

r

r

i

r

i

r

i

r

i

j

r

r

i

r

i

r

i

r

i

i

j

i

i

j

i

G

H

G

s

G

H

G

G

s

G

H

G

G

G

h

G

h

s

−

−

−

−

−

−

−

−

−

−

−

−

−

⊕

=

+

⊕

⊕

=

=

+

⊕

⊕

⊕

=

⊕

=

Metodą indukcji można pokazać, że

j

i

j

i

j

i

i

j

i

j

i

H

H

G

h

H

G

:

:

1

:

1

:

:

=

=

−

−

, skąd mamy:

.

,

:

1

:

1

:

:

:

1

:

j

r

r

i

r

i

j

i

r

i

i

r

i

G

H

s

s

G

h

s

−

−

−

⊕

=

⊕

=

przy tym bitami końcowej sumy są s

i

=s

i

:0

.

Ponieważ powyższe funkcje są niezależne, więc możliwe jest wytworzenie
sumy końcowej w strukturze zawierającej log

2

n

poziomów.

Szybkie sumatory

© Janusz Biernat

, AK1-7-09 Szybkie sumatory.doc, 4 listopada 2009

FAST–

22

Sumator ELM – korekcja sum tymczasowych*

Z podanych zależności wynika zasada konstrukcji sumatora, podobna jak PPA

s

6

s

5

s

4

s

3

s

2

s

1

s

0

s

7

s

k

+1:i

x

7

y

7

g

7

h

7

GP

k

:j+1

GP

j

:i

3

2

1

GP

k

:i

s

k

+1:j

GH

j

–1:i

x

6

y

6

g

6

h

6

x

5

y

5

g

5

h

5

x

4

y

4

g

4

h

4

x

3

y

3

g

3

h

3

x

2

y

2

g

2

h

2

x

1

y

1

g

1

h

1

x

0

y

0

g

0

h

0

c

8

Schemat sumatora ELM (strukturze Ladnera-Fischera)

Powiązania sum można także zrealizować w strukturze Kogge’a-Stone’a.

Szybkie sumatory

© Janusz Biernat

, AK1-7-09 Szybkie sumatory.doc, 4 listopada 2009

FAST–

23

Sumy warunkowe – koncepcja (Sklansky)

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

, AK1-7-09 Szybkie sumatory.doc, 4 listopada 2009

FAST–

24

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

, AK1-7-09 Szybkie sumatory.doc, 4 listopada 2009

FAST–

25

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

, AK1-7-09 Szybkie sumatory.doc, 4 listopada 2009

FAST–

26

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

, AK1-7-09 Szybkie sumatory.doc, 4 listopada 2009

FAST–

27

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

, AK1-7-09 Szybkie sumatory.doc, 4 listopada 2009

FAST–

28

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

, AK1-7-09 Szybkie sumatory.doc, 4 listopada 2009

FAST–

29

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

, AK1-7-09 Szybkie sumatory.doc, 4 listopada 2009

FAST–

30

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

, AK1-7-09 Szybkie sumatory.doc, 4 listopada 2009

FAST–

31

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

, AK1-7-09 Szybkie sumatory.doc, 4 listopada 2009

FAST–

32

Szybkość działania i złożoność sumatorów

Charakterystyki AT

• sumator pełny 1-bitowy 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 kaskadowy 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 PPA – A

≈

5n+3n log n , T

≈

3 + 2 log n → A T

≈

3n log

2

n

+14n log n

– log n poziomów GP, opóźnienie przeniesienia 2 log n

• sumator COSA – A = 3n log n, T = 2 + 2 log n → A T

≈

6 n log

2

n

– 2×RCA, log n poziomów MPX, opóźnienie przeniesienia 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