Szybkie sumatory
Szybko dodawania (odejmowania)
x1 m y1 m x m y m
xk-1 yk-1 xk-2 yk-2
ck c2 m c1 m
ck-1 ck-2
c m
FA/FS FA/FS FA/FS FA/FS
s1 m s m
sk-1 sk-2
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�łlog2nłłd"TŁ d"2n
z

� Janusz Biernat, 10-06-Szybkie sumatory.doc, 2 pa dziernika 2006 FAST 1
 Szybkie sumatory
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 2i 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
z

� Janusz Biernat, 10-06-Szybkie sumatory.doc, 2 pa dziernika 2006 FAST 2
 Szybkie sumatory
Sumator z antycypacj przeniesie (carry look-ahead adder, CLA)
Funkcja przeniesienia
ci+1 = xi yi + (xi �" yi) ci = xi yi + (xi + yi ) ci
" w obliczaniu przeniesienia funkcje OR (xi+yi) i XOR (xi �"yi) s zamienne
" funkcja wytwarzania (generowania) przeniesienia
xi = yi = 1 �! przeniesienie wyj ciowe ci+1 = 1
gi = xi yi ,
" funkcja półsumy
hi = xi �" yi
precyzyjnie okre la warunek przekazywania (propagacji) przeniesienia:
xi `" yi�! ci+1 = ci , ale funkcja OR jest prostsza, wi c przyjmuje si
" funkcja przekazywania (propagacji) przeniesienia ( pi  f. wygaszania)
pi = xi + yi
" w wyra eniach na przeniesienie funkcje p# mo na zast pi funkcjami h#
z

� Janusz Biernat, 10-06-Szybkie sumatory.doc, 2 pa dziernika 2006 FAST 3
 Szybkie sumatory
Funkcje przeniesie w sumatorach CLA
Funkcje c# mo na rozwija wzgl dem kilku kolejnych pozycji
ci+1 = gi + pici
ci+2 = gi+1 + pi+1gi + pi+1pici
ci+3 = gi+2 + pi+2gi+1 + pi+2 pi+1gi + pi+2 pi+1pici
ci+4 = gi+3 + pi+3gi+2 + pi+3 pi+2gi+1 + pi+3 pi+2 pi+1gi + pi+3 pi+2 pi+1pici
" zło ono funkcji c# ro nie z kwadratem zasi gu s
" bariera technologiczna  ograniczona liczba wej bramki
ci+s+1 = gi+s + pi+sci+s = gi+s + pi+s(gi+s-1 + pi+s-1ci+s-1) = ...
= gi+s + pi+sgi+s-1 + pi+s pi+s-1gi+s-2 +...+ pi+s pi+s-1...pi+1(gi + pici)
ci+s+1 = G(gi+s, pi+s,..., gi, pi) + ciP(gi+s, pi+s,..., gi, pi) =
= G(gi+s,hi+s,..., gi,hi) + ciP(gi+s,hi+s,..., gi,hi)
z

� Janusz Biernat, 10-06-Szybkie sumatory.doc, 2 pa dziernika 2006 FAST 4
 Szybkie sumatory
Moduł sumatora z antycypacj przeniesie (CLA)
xi+3 yi+3 xi+2 yi+2 xi+1 yi+1 xi yi
pi+3 gi+3 pi+2 gi+2 pi+1 gi+1 pi gi
ci
ci+4 ci+3 ci+2 ci+1
ci+4
CLA
si+3 si+2 si+1 si
Czterobitowy sumator CLA
z

� Janusz Biernat, 10-06-Szybkie sumatory.doc, 2 pa dziernika 2006 FAST 5
 Szybkie sumatory
A
a cuch sumatorów z antycypacj przeniesie (CLA)
x x7:4
x y11:8 y7:4 x
y15:12 11:8 y3:0
15:12 3:0
c16 0
c12 c8 c4
CLA
CLA
CLA CLA
s15:12 s11:8 s7:4 s3:0
Sumator zbudowany z kaskady bloków CLA
x
y15:12
15:12 x x
y11:8 y7:4 x
11:8 7:4 y3:0
3:0
c12
c8 c4
0
CLA
CLA CLA
CLA
G,P G,P G,P
G,P
c16
CLG
s3:0
s15:12 s11:8 s7:4
Sumator CLA z blokiem wytwarzania przeniesie CLG
z

� Janusz Biernat, 10-06-Szybkie sumatory.doc, 2 pa dziernika 2006 FAST 6
 Szybkie sumatory
Propagacja i generowanie przeniesie  intuicje (1)
AB
i
out n
c c
cout=1 je li:
" cin=1 jest przesyłane przez blok AB do wyj cia cout
" wewn trz bloku AB jest wytwarzane cout=1, za cin jest dowolne
A B
i
out m n
c c c
cout=1 je li:
" cin=1 jest przesyłane przez blok B do cm a nast pnie przez blok A do cout
" wewn trz bloku A jest wytwarzane cout=1, za cm jest dowolne
" wewn trz bloku B jest wytwarzane cm=1,
a nast pnie przez blok A jest przekazywane do cout
z

� Janusz Biernat, 10-06-Szybkie sumatory.doc, 2 pa dziernika 2006 FAST 7
 Szybkie sumatory
Propagacja i generowanie przeniesie  intuicje (2)
1
GA
GBA
1 1
PA GB
PBA
GC
1 1 1
PA PB
GDC
1
PC GD
PBA PDC
1 1 1 1 1
PA PB PC PD
cout = GA + PAGB + PAPB cin / B = GBA + PBA cin / B
cout = GBA + PBAGDC + PBAPDC cin / D = GDCBA + PDCBA cin / D
z

� Janusz Biernat, 10-06-Szybkie sumatory.doc, 2 pa dziernika 2006 FAST 8
 Szybkie sumatory
Funkcje grupowej antycypacji przeniesie
Wyznaczanie funkcji przekazywania (propagacji) przeniesienia P
przez bloki sumatora (iloczyn) jest działaniem ł cznym (asocjacyjnym)
PCBA = (PAPB )PC = PA(PBPC )
Wyznaczanie funkcji wytwarzania (generowania) przeniesienia G
w bloku sumatora jest tak e działaniem ł cznym (asocjacyjnym)
GCBA = GA + PAGCB = GA + PA(GB + PBGC ) =
= GBA + PBAGC = (GA + PAGB ) + PAPBGC
Funkcje rekursywnie skojarzone  takie, które opisuje operator asocjacyjny "
yi=xi" yi 1, y0=x0
Wyznaczanie funkcji rekursywnie skojarzonej  problem prefiksowania
Funkcje G,P s rekursywnie skojarzone przez wektorowy operator asocjacyjny
(GBA, PBA) = (GA, PA) " (GB, PB) = (GA + PAGB, PAPB)
(GCBA, PCBA) = (GA, PA) " (GB, PB) " (GC , PC )
z

� Janusz Biernat, 10-06-Szybkie sumatory.doc, 2 pa dziernika 2006 FAST 9
 Szybkie sumatory
Funkcje wytwarzania przeniesie i sum
Dla dowolnego bloku sumatora pomi dzy pozycjami i oraz k (ke"se"i):
ck +1 = Gi,k + Pi,kci
przy tym Gi,k = Gs+1,k + Ps+1,kGi,s,
Pi,k = Pi,sPs+1,k .
Poniewa Gk ,k = gk = xk yk i Pk ,k = pk = xk + yk (lub Pk ,k = hk = xk �" yk ), wi c
k
Gi,k = gk + pk gk -1 +...+ p gi ,
"
j
j=i+1
k
Pi,k = pj ,
"
j=i
Je li c0=0, to warto sumy si zale y tylko od warto ci funkcji G0,i-1 oraz hi
si = hi �" ci = hi �" G0,i-1
 schemat wyznaczania funkcji G0,i i P0,i mo na optymalizowa
 wszystkie funkcje G0,i i P0,i mo na wyznaczy w sekwencji �łlog2nłł działa
z

� Janusz Biernat, 10-06-Szybkie sumatory.doc, 2 pa dziernika 2006 FAST 10
 Szybkie sumatory
Sumatory prefiksowe (PPA)
sumator prefiksowy  parallel prefix adder, PPA
si = hi �" G0,i-1
xi yi
xk 1 yk 1 xi 1 yi 1 x0 y0
GP
sk 1 si si 1 s0
Blok GP  wytwarzanie warto ci przeniesie ci=G0,i 1
z

� Janusz Biernat, 10-06-Szybkie sumatory.doc, 2 pa dziernika 2006 FAST 11
 Szybkie sumatory
Sumator uniwersalny (1)
Je li c0 nie jest ustalone to
si = hi �" ci = hi �" (G0,i-1 + P0,i-1c0)
Aby unikn wielokrotnego rozgał zienia sygnału c0 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.
1 1 2 2 3 3 3 3 2 2 1 1 0 0
xk  yk  xk  yk  xk  yk  x y x y x y x y
0
c
0
cwe=
sumator PPA
cwy
Wnoszone opó nienie w kategoriach AT jest takie samo jak w realizacji funkcji
G0,i 1+P0,i 1 c0, ale nie wyst puje problem rozgał zienia sygnału c0 (faktycznie
TXOR < TAND-OR).
Podobne rozwi zanie mo na zastosowa w uniwersalnym sumatorze U2.
z

� Janusz Biernat, 10-06-Szybkie sumatory.doc, 2 pa dziernika 2006 FAST 12
 Szybkie sumatory
Sumator uniwersalny (2)
Je li c0 nie jest ustalone to
si = hi �" ci = hi �" (G0,i-1 + P0,i-1c0)
Aby unikn konieczno ci korekcji ci w sytuacji gdy c0 nie jest znane z góry,
mo na potraktowa c0 jako funkcj generowania przeniesienia z pozycji   1 ,
g 1= c0, gdy jednocze nie p 1= 0, i wtedy wszystkie funkcje P 1,i = 0 oraz:
si = hi �"[G0,i-1 + P0,i-1(g-1 + p-1c-1)]
wi c sumy trzeba oblicza jako:
si = hi �" ci = hi �" (G-1,i-1 + P-1,i-1c-1) = hi �" G-1,i-1
To oznacza, e graf prefiksowy musi obejmowa n+1 pozycji. W szczególno ci:
G-1,0 = g0 + p0g-1, P-1,0 = p0 p-1
G-1,1 = g1 + p1G-1,0, P-1,1 = p1P-1,0
To rozwi zanie jest szybsze ni poprzednie, a problemem jest szybka realizacja
(3 poziomy logiczne) funkcji:
G-1,1 = g1 + p1g0 + p1 p0c0.
z

� Janusz Biernat, 10-06-Szybkie sumatory.doc, 2 pa dziernika 2006 FAST 13
 Szybkie sumatory
Tworzenie funkcji G,P
" regularne struktury dla n=2k,
" w innych przypadkach przyj k=intlog22n 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
z

� Janusz Biernat, 10-06-Szybkie sumatory.doc, 2 pa dziernika 2006 FAST 14
 Szybkie sumatory
Przekształcenie prefiksowe Ladnera-Fischera (Sklansky) dla funkcji G,P
Poziom 0 (i=0,1,& ,n-1) G0,0
Pi,i=xi�"yi, Gi,i=xiyi
Poziom 1 (i=0,1,& ,2- 1n-1) G0,1
(G2i,2i+1,P2i,2i+1)=(G2i+1,2i+1,P2i+1,2i+1)l(G2i,2i,P2i,2i)
Poziom 2 (i=0,1,& ,2- 2n-1; s=2,3) G0,3,G0,2
(G4i,4i+s,P4i,4i+s)=(G4i+2,4i+s,P4i+2,4i+s)l(G4i,4i+1,P4i,4i+1)
Poziom 3 (i=0,1,& ,2- 3n-1; s=4,5,6,7) G0,7,& ,G0,4
(G8i,8i+s,P8i,8i+s)=(G8i+4,8i+s,P8i+4,8i+s)l(G8i,8i+3,P8i,8i+3)
Poziom 4 (i=0,1,& ,2- 4n-1; s=8,9,& ,15) G0,15,& ,G0,8
(G16i,16i+s,P16i,16i+s)=(G16i+8,16i+s,P16i+8,16i+s)l(G16i,16i+7,P16i,16i+7)
&
z

� Janusz Biernat, 10-06-Szybkie sumatory.doc, 2 pa dziernika 2006 FAST 15
 Szybkie sumatory
Przekształcenie prefiksowe Kogge-Stone a dla funkcji G,P
Poziom 0 (i=0,1,& ,n-1) G0,0
Pi,i=xi�"yi, Gi,i=xiyi
Poziom 1 (i=0,1,& ,2- 1n-1) G0,1
(Gi,i+1,Pi,i+1)=(Gi+1,i+1,Pi+1,i+1)l(Gi,i,Pi,i)
Poziom 2 (s=0,1; i=0,1,& ,n-22)
G0,s+2=Gs+1,s+2+Ps+1,s+2G0,s (G0,3),G0,2
(Gi,i+3,Pi,i+3)=(Gi+2,i+3,Pi+2,i+3)l(Gi,i+1,Pi,i+1) G0,3
Poziom 3 (s=0,1,& ,22-1; i=0,1,& ,n-23)
G0,s+4=Gs+1,s+4+Ps+1,s+4G0,s (G0,7),G0,6,G0,5,G0,4
(Gi,i+7,Pi,i+7)=(Gi+4,i+7,Pi+4,i+7)l(Gi,i+3,Pi,i+3) G0,7
Poziom 4 (s=0,1,& ,23-1; i=0,1,& ,n-24)
G0,s+8=Gs+1,s+8+Ps+1,s+8G0,s (G0,15),& & ,G0,8
(Gi,i+15,Pi,i+15)=(Gi+8,i+15,Pi+8,i+15)l(Gi,i+7,Pi,i+7) G0,15
&
z

� Janusz Biernat, 10-06-Szybkie sumatory.doc, 2 pa dziernika 2006 FAST 16
 Szybkie sumatory
Przekształcenie prefiksowe Brenta-Kunga dla funkcji G,P
Poziom 0 (i=0,1,& ,n-1) G0,0
Pi,i=xi�"yi, Gi,i=xiyi
Poziom 1 (i=0,1,& ,2- 1n-1) G0,1
(G2i,2i+1,P2i,2i+1)=(G2i+1,2i+1,P2i+1,2i+1)l(G2i,2i,P2i,2i)
Poziom 2 (i=0,1,& ,2- 2n-1) G0,3
(G4i,4i+3,P4i,4i+3)=(G4i+2,4i+3,P4i+2,4i+3)l(G4i,4i+1,P4i,4i+1)
Poziom 3 (i=0,1,& ,2- 3n-1) G0,7
(G8i,8i+7,P8i,8i+7)=(G8i+4,8i+7,P8i+4,8i+7)l(G8i,8i+3,P8i,8i+3)
&
Poziom m=�łlog2nłł (T=2m-2)
(G0,3T-1,P0,3T-1)=(G2T,3T-1,P2T,3T-1)l(G0,2T -1,P0,2T -1) G0,3T
(G0,n-1,P0,n-1)=(G2T,n-1,P2T,n-1)l(G0,2T -1,P0,2T -1) G0,n -1
&
Poziom m+r (i=(0),1,& ,22-1, R=2m-2-s), r=1,& ,m-2
(G0,iR-1,P0,iR-1)=(G2R,iR-1,P2R,iR-1)l(G0,2R -1,P0,2R -1)
z

� Janusz Biernat, 10-06-Szybkie sumatory.doc, 2 pa dziernika 2006 FAST 17
 Szybkie sumatory
Przekształcenie prefiksowe Han a-Carlson a dla funkcji G,P
Poziom 0 (i=0,1,& ,n-1) G0,0
Pi,i=xi�"yi, Gi,i=xiyi
Poziom 1 (i=0,1,& ,2- 1n-1) G0,1
(G2i,2i+1,P2i,2i+1)=(G2i+1,2i+1,P2i+1,2i+1)l(G2i,2i,P2i,2i)
Poziom 2 (i=0,1,& ,2- 2n-1) G0,3
(G2i,2i+3,P2i,2i+3)=(G2i+2,2i+3,P2i+2,2i+3)l(G2i,2i+1,P2i,2i+1)
Poziom 3 (s=0,1; i=0,1,& ,2- 3n-1)
(G2i,2i+7,P2i,2i+7)=(G2i+4,2i+7,P2i+4,2i+7)l(G2i,2i+3,P2i,2i+3)
G0,2s+5=G2s+1,2s+5+P2s+1,2s+5G0,2s G0,7,G0,5
Poziom 4 (s=0,1,& ,22-1; i=0,1,& ,2- 3n-1)
(G2i,2i+15,P2i,2i+15)=(G2i+8,2i+15,P2i+8,2i+15)l(G2i,2i+7,P2i,2i+7)
G0,2s+9=G2s+1,2s+9+P2s+1,2s+8G0,2s G0,15,G0,13,G0,11,G0,9
...
Poziom �łlog2nłł+1 (i=0,1,& ,2- 1n-1)
G0,2i=G2i,2i+P2i,2iG0,2i-1 G0,2i,& ,G0,4,G0,2
z

� Janusz Biernat, 10-06-Szybkie sumatory.doc, 2 pa dziernika 2006 FAST 18
 Szybkie sumatory
Prefiksowe schematy generowania i propagacji przeniesienia (PPA)
15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0
0
15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0
1
0
2
1
2
3
3
4
4
Graf prefixowy (Kogge & Stone)
Graf prefixowy (Sklansky / Ladner-Fischer)
15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0
0 0
1 1
2 2
3
3
4
5
4
6
5
Graf prefixowy (Brent Kung) Graf prefixowy  (Han & Carlson)
ń  wytwarzanie funkcji Gi,i=gi oraz Pi,i=pi Ą  przekazywanie G oraz P
l  operator prefiksowy (GBA,PBA)=(GB,PB)l(GA,PA)
z

� Janusz Biernat, 10-06-Szybkie sumatory.doc, 2 pa dziernika 2006 FAST 19
 Szybkie sumatory
Charakterystyki grafów prefiksowych
Ladner-Fischer  log2n poziomów logicznych, minimum elementów GP
nierównomierne obci enia (Sklansky)
Kogge & Stone  log2n poziomów logicznych, wi cej elementów GP,
rozło ona obci alno wyj
Brent-Kung  >log2n poziomów logicznych, mniej elementów GP,
stała obci alno wyj
Han & Carlson  >log2n 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
2
RCA /3 n n 1 2 n/2
Ladner-Fischer � nlog2n log2n n/2 ź nlog2n
Brent-Kung 2n nlog2n 2 2 log2n 2 log2n+1 ~ 3/8 nlog2n
Kogge & Stone nlog2n n+1 log2n 2 � nlog2n
Han & Carlson � nlog2n log2n+1 2 ź nlog2n
z

� Janusz Biernat, 10-06-Szybkie sumatory.doc, 2 pa dziernika 2006 FAST 20
 Szybkie sumatory
Sumy warunkowe  koncepcja
xi + yi
L
1+0 0+0 1+1 1+0 0+1 1+1 1+0 0+1
0
ci0+1 0 0 1 0 0 1 0 0
si0 1 0 0 1 1 0 1 1
:i
1
ci+1 1 0 1 1 1 1 1 
1
si:i 0 1 1 0 0 1 0 
0
1
c2i+2 0 1 1 0
0
s2i+1:2i 1 0 0 1 0 0 1 1
c1i+2 0 1 1  
2
s1i+1:2i 1 1 1 0 0 1  
2
0
2
c4i+4 0 1
0
s4i+3:4i 1 1 0 1 0 0 1 1
c1i+4 0    
4
s1i+3:4i 1 1 1 0    
4
s3:0
1 1 1 0 0 0 1 1
7
z

� Janusz Biernat, 10-06-Szybkie sumatory.doc, 2 pa dziernika 2006 FAST 21
 Szybkie sumatory
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,...)
1 1
xi + yi + 0 = 2ci0i + si0i oraz xi + yi +1 = 2ci:i + si:i
: :
1
si:i = {si0i , si:i} = {xi �" yi , xi a" yi}
:
1
ci+1 = {ci0+1,ci+1} = {xi yi , xi + yi}
Poziom p (||  zło enie wektorów)
 warunkowe sumy sąri+2r -1,2ri i przeniesienia cąr (i+1) grup r=2p bitów,
2 2
 dla i=0,1,...,�łn�2 płł-1
sąri+2r -1,2ri = [cąri+r s1 + (1- cąri+r ) s1 -1,2ri+r ]|| sąri+r -1,2ri ,
2 2 2ri+2r-1,2ri+r 2 2ri+2r 2
0
cąr (i+1) = cąri+r c1ri+2r + (1- cąri+r )c2ri+2r
2 2 2 2
Ko cowy wynik sumowania powstaje na poziomie k=�łlog2nłł (r=2k).
z

� Janusz Biernat, 10-06-Szybkie sumatory.doc, 2 pa dziernika 2006 FAST 22
 Szybkie sumatory
Schemat sumatora sum warunkowych
y7 x7 y6 x6 y5 x5 y4 x4 y3 x3 y2 x2 y1 x1 y0 x0
Ł Ł Ł Ł Ł Ł Ł Ł
Ł Ł Ł Ł Ł Ł Ł Ł
Ł Ł Ł Ł Ł Ł Ł Ł
Ł Ł Ł Ł Ł Ł Ł Ł
0/1 0/1 0/1 0/1 0/1 0/1 0/1 0/1
L0
1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0
L1
1 0 1 0 1 0 1 0 1 0 1 0
L2
1 0 1 0 1 0 1 0 1 0
L3
s7 s6 s5 s4 s3 s2 s1 s0
c7
x y
c1
1 0
1 0
1 0
c0
Ł0/1
Ł
Ł
Ł
s1 s0
O miobitowy sumator sum warunkowych
T = 2 �łlog22nłł, A=�(nlog2n+2nlog2n)=3nlog2n
z

� Janusz Biernat, 10-06-Szybkie sumatory.doc, 2 pa dziernika 2006 FAST 23
 Szybkie sumatory
Sumator sterowany przeniesieniem (CSLA)
Sumator multipleksowany sterowany przeniesieniem (carry-select adder)
wybór ki-pozycyjnych sum warunkowych zale nie od przeniesienia
xm,l ym,l
xk,i yk,i
x yl,k
l,k
0
CPA CPA CPA
0
s0 yi,
xm,l ym,l s0 sl,k yk,i xi, 0 0
x yl,k xk,i
m,l l,k k,i
1
0
CPA CPA CPA CPA
1
s1 s1
sl,k
m,l k,i
MPX MPX MPX
sm,l sl,k
cm +1
si,0
sk,i
Schemat logiczny sumatora multipleksowanego sterowanego przeniesieniem
Sumy blokowe obliczane jednocze nie �! wy sze bitywi ksze bloki
Opó nienie  > 2 2n (optymalna liczba bloków  około 2n )
z

� Janusz Biernat, 10-06-Szybkie sumatory.doc, 2 pa dziernika 2006 FAST 24
 Szybkie sumatory
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
xn,m yn,m xm,l ym,l yl,k ck+1 xj,i yj,i xi,0 yi,0 c0
xl,k
CPA CPA CPA CPA CPA
cm+1 m,l sm,l cl +1 ci P0 si,0
cn+1 P sn,m P Pl,k cj+1 P sj,i +1 i,
sl,k
n,m j,i
...
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
"0 = [(k -1) + l - 2 + (k -1)]� = [2k + nk-1 - 4]� e" 2[ 2n - 2]�
z

� Janusz Biernat, 10-06-Szybkie sumatory.doc, 2 pa dziernika 2006 FAST 25
 Szybkie sumatory
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
"(u, v) = [(gu - 1) + (u - v - 1) + (gv - 1)]�
struktura cie ka opó nienie max
6 bloków 4-4-4-4-4-4 10
(4-1)+4+(4-1) = 10
3-4-5-5-4-3 5-5 8
(5-1)+0+(5-1) = 8
2-5-6-5-4-2 5-6-5-4 9
(5-1)+2+(4-1) = 9
6-5-4 9
(6-1)+1+(4-1) = 9
8 bloków 1-2-3-6-6-3-2-1 3-6-6-3
(3-1)+2+(3-1) = 6
6-6 10
(6-1)+0+(6-1) = 10
1-2-4-5-5-4-2-1 4-5-5-4 8
(4-1)+2+(4-1) = 8
1-2-3-4-5-4-3-2 4-5-4 7
(4-1)+1+(4-1) = 7
9 bloków 1-2-3-4-4-4-3-2-1 2-3-4-4-4-3-2 7
(2-1)+5+(2-1) = 7
3-4-4-4-3 7
(3-1)+3+(3-1) = 7
3-4-4-4 7
(3-1)+2+(4-1) = 7
z

� Janusz Biernat, 10-06-Szybkie sumatory.doc, 2 pa dziernika 2006 FAST 26
 Szybkie sumatory
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 gu +i = gu+i-1 +1, i=1,2,...,k , to maksymalne opó nienie
gu+k� = (gu+i-1)� +(k-i)� = (gu+k-1)� ;
je li rozmiar s bloków wytwarzaj cych bardziej znacz ce pozycje sumy
jest typu gv+i = gv+i-1 -1, i=0,1,2,...,s-1, to maksymalne opó nienie
gv+s� = (gv+i-1)� +(s-i)� = (gv+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 .
z

� Janusz Biernat, 10-06-Szybkie sumatory.doc, 2 pa dziernika 2006 FAST 27
 Szybkie sumatory
Optymalizacja sumatora z przeskokiem przeniesie - przykład
" n-bitowy ła cuch optymalny 1-2-3-...-3-2-1 zawiera 2 n -1 bloków
" sumator n-bitowy powinien mie najwy ej �ł2 n -1łł bloków
" (p 1)2d"nd"p2 s2 �! sumator n-bitowy powinien mie d"2(p s) bloków
Przykład. Sumator 32-bitowy powinien mie d"8 bloków (32=62 22)
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 d"8 bloków (24=52 12)
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
z

� Janusz Biernat, 10-06-Szybkie sumatory.doc, 2 pa dziernika 2006 FAST 28
 Szybkie sumatory
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 si = xi �" ci, ci+1 = xici
półsubtraktor (half subtracter, HS)  realizuje funkcje si = xi �" ci, ci+1 = xici
x1 x0
xk-1 xk-2
ck c2 c1
ck-1 ck-2
1
HA/HS
HA/HS HA/HS HA/HS
s1 s0
sk-1 sk-2
sumator z inkrementacj wskutek przeniesienia (carry-increment adder, CIA
układ zliczaj cy  inkrementer/dekrementer ze sprz eniem xi(t +1) = si(t)
( ) ( ) ( (
i zapami tywaniem stanu S(t) = {skt-1,skt-2,...,s1t),s0t)
z

� Janusz Biernat, 10-06-Szybkie sumatory.doc, 2 pa dziernika 2006 FAST 29
 Szybkie sumatory
Szybko działania i zło ono sumatorów
Charakterystyki AT
" sumator pełny FA  A=7, T=2+2 AT=28
 2�XOR, 1�OR, 2�AND opó nienie przeniesienia 2, sumy 2+2
" sumator RCA  A=7n, T=2n AT=14n2
 n�FA opó nienie przeniesienia n�"2
" sumator CLA  AH"7n, TH"4logn ATH"56nlogn
 n�FA logn bloków, opó nienie przeniesienia 2�"2logn
" sumator CSKA  AH"8n, TH"2�" 2 n ATH"32n n
 n�FA+2 n �MPX, 2 n bloków opó nienie przeniesienia 2�" 2 n
" sumator CSLA  AH"2�"7n, TH" 2 2n ATH"39n n
 2�RCA, 2n bloków, opó nienie przeniesienia 2�" 2n
" sumator COSA  A=3nlogn, T=2logn AT=6nlog2n
 2�RCA, logn poziomów MPX, opó nienie przeniesienia 2�"logn
z

� Janusz Biernat, 10-06-Szybkie sumatory.doc, 2 pa dziernika 2006 FAST 30
 Szybkie sumatory
Przekształcenie prefiksowe Ladnera-Fischera (Sklansky) dla funkcji G,P
Pi,i=xi�"yi, Gi,i=xiyi (i=0,1,& ,n-1) G0,0
Poziom 1 (i=0,1,& ,2- 1n-1)
P2i,2i+1=P2i+1,2i+1P2i,2i
G2i,2i+1=G2i+1,2i+1+P2i+1,2i+1G2i,2i G0,1
Poziom 2 (i=0,1,& ,2- 2n-1; s=2,3)
P4i,4i+s=P4i+2,4i+sP4i,4i+1
G4i,4i+s=G4i+2,4i+s+P4i+2,4i+sG4i,4i+1 G0,3,G0,2
Poziom 3 (i=0,1,& ,2- 3n-1; s=4,5,6,7)
P8i,8i+s=P8i+4,8i+sP8i,8i+3
G8i,8i+s=G8i+4,8i+s+P8i+4,8i+sG8i,8i+3 G0,7,& ,G0,4
Poziom 4 (i=0,1,& ,2- 4n-1; s=8,9,& ,15)
P16i,16i+s=P16i+8,16i+sP16i,16i+7
G16i,16i+s=G16i+8,16i+s+P16i+8,16i+sG16i,16i+7 G0,15,& ,G0,8
&
z

� Janusz Biernat, 10-06-Szybkie sumatory.doc ,2 pa dziernika 2006 FAST 13a
 Szybkie sumatory
Przekształcenie prefiksowe Kogge-Stone a dla funkcji G,P
Pi,i=xi�"yi, Gi,i=xiyi (i=0,1,& ,n-1) G0,0
Poziom 1 (i=0,1,& ,n-2)
Pi,i+1=Pi+1,i+1Pi,i, Gi,i+1=Gi+1,i+1+Pi+1,i+1Gi,i G0,1
Poziom 2 (s=0,1; i=0,1,& ,n-22)
Pi,i+3=Pi+2,i+3Pi,i+1
G0,s+2=Gs+1,s+2+Ps+1,s+2G0,s G0,3,G0,2
Gi,i+3=Gi+2,i+3+Pi+2,i+3Gi,i+1 (G0,3)
Poziom 3 (s=0,1,& ,22-1; i=0,1,& ,n-23)
Pi,i+7=Pi+4,i+7Pi,i+3
G0,s+4=Gs+1,s+4+Ps+1,s+4G0,s G0,7,G0,6,G0,5,G0,4
Gi,i+7=Gi+4,i+7+Pi+4,i+7Gi,i+3 (G0,7)
Poziom 4 (s=0,1,& ,23-1; i=0,1,& ,n-24)
G0,s+8=Gs+1,s+8+Ps+1,s+8G0,s G0,15,& & ,G0,8
&
z

� Janusz Biernat, 10-06-Szybkie sumatory.doc ,2 pa dziernika 2006 FAST 14a
 Szybkie sumatory
Przekształcenie prefiksowe Brenta-Kunga dla funkcji G,P
Pi,i=xi�"yi, Gi,i=xiyi (i=0,1,& ,n-1) G0,0
Poziom 1 (i=0,1,& ,2- 1n-1)
G2i,2i+1=G2i+1,2i+1+P2i+1,2i+1G2i,2i, P2i,2i+1=P2i+1,2i+1P2i,2i G0,1
Poziom 2 (i=0,1,& ,2- 2n-1)
P4i,4i+3=P4i+2,4i+3P4i,4i+1,
G4i,4i+3=G4i+2,4i+3+P4i+2,4i+3G4i,4i+1 G0,3
Poziom 3 (i=0,1,& ,2- 3n-1)
P8i,8i+7=P8i+4,8i+7P8i,8i+3,
G8i,8i+7=G8i+4,8i+7+P8i+4,8i+7G8i,8i+3 G0,7
&
Poziom m=�łlog2nłł (T=2m-2)
G0,3T-1=G2T,3T-1+P2T,3T-1G0,2T -1, P0,3T-1=P2T,3T-1P0,2T-1, G0,3T
G0,n-1=G2T,n-1+P2T,n-1G0,2T -1, P0,n-1=P2T,n-1P0,2T -1, G0,n
Poziom m+1 (i=(0),1,& ,22-1, R=2m-3)
G0,iR-1=G2R,iR-1+P2R,iR-1G0,2R-1 G0,13,G0,9,G0,5
P0,iR-1=P2R,iR-1P0,2R-1
z

� Janusz Biernat, 10-06-Szybkie sumatory.doc ,2 pa dziernika 2006 FAST 15a
 Szybkie sumatory
Przekształcenie prefiksowe Han a-Carlson a dla funkcji G,P
Pi,i=xi�"yi, Gi,i=xiyi (i=0,1,& ,n-1) G0,0
Poziom 1 (i=0,1,& ,2- 1n-1)
P2i,2i+1=P2i+1,2i+1P2i,2i
G2i,2i+1=G2i+1,2i+1+P2i+1,2i+1G2i,2i G0,1
Poziom 2 (i=0,1,& ,2- 2n-1)
P2i,2i+3=P2i+2,2i+3P2i,2i+1
G2i,2i+3=G2i+2,2i+3+P2i+2,2i+3G2i,2i+1 G0,3
Poziom 3 (s=0,1; i=0,1,& ,2- 3n-1)
P2i,2i+7=P2i+4,2i+7P2i,2i+3
G0,2s+5=G2s+1,2s+5+P2s+1,2s+5G0,2s G0,7,G0,5
G2i,2i+7=G2i+4,2i+7+P2i+4,2i+7G2i,2i+3
Poziom 4 (i=0,1,& ,2- 3n-1)
P2i,2i+15=P2i+8,2i+15P2i,2i+7
G2i,2i+15=G2i+8,2i+15+P2i+8,2i+15G2i,2i+7 G0,15,G0,13,G0,11,G0,9
...
Poziom �łlog2nłł+1 (i=0,1,& ,2- 1n-1)
G0,2i=G2i,2i+P2i,2iG0,2i-1 G0,2i,& ,G0,4,G0,2
z

� Janusz Biernat, 10-06-Szybkie sumatory.doc ,2 pa dziernika 2006 FAST 16a