�� Szybkie sumatory Algorytm dodawania i odejmowania x1 y1 x0 y0 xk-1 yk-1 xk-2 yk-2 ck c2 c1 ck-1 ck-2 c0 FA/FS FA/FS FA/FS FA/FS s1 s0 sk-1 sk-2 Schemat dodawania/odejmowania binarnego dodawanie (X+Y) odejmowanie (X Y) si = xi �" yi �" ci si = xi �" yi �" ci ci+1 = xi yi + (xi �" yi ) ci ci+1 = xi yi + (xi �" yi ) ci = xi yi + (xi + yi ) ci = xi yi + (xi �" yi ) ci Propagacja przeniesienia " obliczenie sumy/r� nicy na pozycji i wymaga przeniesienia z pozycji i-1 " czas wytworzenia sumy/r� nicy  staB
y od chwili ustalenia przeniesienia " gwarantowany czas wykonania dodawania/odejmowania zale y od najdB
u szego czasu przesB
ania zmiany przeniesienia z pozycji najni szej " czas sekwencyjnego dodawania/odejmowania n-pozycyjnego  nT � Janusz Biernat, AK1-7-09 Szybkie sumatory.doc, 4 listopada 2009 FAST 1  Szybkie sumatory Przyspieszanie dodawania dwuargumentowego Skracanie czasu propagacji przeniesie " antycypacja przeniesie (carry look-ahead adder, CLA) " wytwarzanie przeniesie r�wnolegB
ych (parallel prefix adder, PPA) " skracanie cie ki propagacji przeniesienia (carry skip adder, CSKA) SkB
adanie sum tymczasowych " skB
adanie sum warunkowych (conditional sum adder, COSA)  tworzenie wariantowych sum dla blok�w 2i kolejnych pozycji " sumator z przeB
czaniem sum cz ciowych (carry-select adder, CSLA)  r�wnolegB
e wytwarzanie alternatywnych sum cz ciowych " skB
adanie sum korygowanych (carry-increment adder, CIA)  korekcja sum blokowych przeniesieniami " obliczanie i korekcja sum tymczasowych (ELM) SkB
adanie sum redundantnych " nadmiarowa reprezentacja argument�w (SD) �! dodawanie dwuetapowe Teoretycznie osi galny czas dodawania/odejmowania n-pozycyjnego: T��log2n�� � Janusz Biernat, AK1-7-09 Szybkie sumatory.doc, 4 listopada 2009 FAST 2  Szybkie sumatory Wytwarzanie i propagacja przeniesie w dodawaniu Funkcja przeniesienia mo e mie jedn z r�wnowa nych form ci+1 = xi yi + (xi �" yi) ci = xi yi + (xi + yi ) ci poniewa a+b=a�"b+ab (OR(a,b)=XOR(a,b)+ab). SkB
adowymi wyra enia s : " funkcja wytwarzania (generowania) przeniesienia, okre laj ca warunki przy kt�rych przeniesienie wyj ciowe ci+1=1 niezale nie od ci: gi = xi yi , " funkcja p�B
sumy, kt�ra tak e okre la warunki przekazywania (propagacji) przeniesienia ( xi `" yi�! ci+1 = ci ): hi = xi �" yi W wyra eniach na przeniesienie mo e j zast pi " (nadmiarowa) funkcja przekazywania przeniesienia ( pi f. wygaszania) pi = xi + yi UWAGA: W wyra eniach na przeniesienie funkcje p# i h# s wzajemnie zamienne. � Janusz Biernat, AK1-7-09 Szybkie sumatory.doc, 4 listopada 2009 FAST 3  Szybkie sumatory Wytwarzanie i propagacja przeniesie w odejmowaniu Funkcja po yczki (przeniesienia wstecznego) mo e mie jedn z form ci+1 = xi yi + (xi �" yi ) ci = xi yi + (xi + yi ) ci poniewa a+b=a�"b+ab (OR(a,b)=XOR(a,b)+ab). SkB
adowymi wyra enia s : " funkcja wytwarzania (generowania) po yczki, okre laj ca warunki przy kt�rych po yczka z wy szej pozycji ci+1=1 niezale nie od ci: gi = xi yi, " funkcja p�B
r� nicy, kt�ra okre la te warunki przekazywania (wstecznej propagacji) po yczki ( xi = yi �! ci+1 = ci ): hi = xi �" yi W wyra eniach na po yczki mo e j zast pi " (nadmiarowa) funkcja przekazywania po yczki ( pi f. wygaszania) pi = xi + yi UWAGA: W wyra eniach na po yczki funkcje p# i h# s wzajemnie zamienne. � Janusz Biernat, AK1-7-09 Szybkie sumatory.doc, 4 listopada 2009 FAST 4  Szybkie sumatory Propagacja i generowanie przeniesie  intuicje (1) HL c c cout=1 je li: " cin=1 jest przesyB
ane przez blok HL do wyj cia cout " wewn trz bloku HL jest wytwarzane cout=1, za cin jest dowolne H L c c c cout=1 je li: " cin=1 jest przesyB
ane przez blok L do cm a nast pnie przez blok H do cout " wewn trz bloku H jest wytwarzane cout=1, za cm jest dowolne " wewn trz bloku L jest wytwarzane cm=1, a nast pnie przez blok H jest przekazywane do cout Uwaga: Analogiczne zale no ci mo na poda dla po yczek w odejmowaniu � Janusz Biernat, AK1-7-09 Szybkie sumatory.doc, 4 listopada 2009 FAST 5  Szybkie sumatory Propagacja i generowanie przeniesie  intuicje (2) 1 GH=1 GHL=1 1 1 PH=1 GL=1 GHLF=1 PHL=1 1 1 1 PH=1 PL=1 GF=1 PHLF=1 PHL=1 1 1 1 1 PH=1 PL=1 PF=1 cout = GH + PHGL + PHPL cin L = GHL + Phl cin L cout = GHL + PHLGF + PHLPF cin F = GHLF + PHLF cin F � Janusz Biernat, AK1-7-09 Szybkie sumatory.doc, 4 listopada 2009 FAST 6  Szybkie sumatory Funkcje grupowej antycypacji przeniesie Wyznaczanie funkcji przekazywania (propagacji) przeniesienia P przez bloki sumatora (iloczyn) jest dziaB
aniem B
cznym (asocjacyjnym) PHLF = PH PL PF = PH PLPF Wyznaczanie funkcji wytwarzania (generowania) przeniesienia G w bloku sumatora jest tak e dziaB
aniem B
cznym (asocjacyjnym) GHLF = GH + PHGLF = GH + PH GL + PLGF = = GHL + PHLGF = GH + PHGL + PH PLGF 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 GHL PHL = GH PH " GL PL = GH + PHGL PHPL GHLF PHLF = GH PH " GL PL " GF PF � Janusz Biernat, AK1-7-09 Szybkie sumatory.doc, 4 listopada 2009 FAST 7  Szybkie sumatory Funkcje wytwarzania przeniesie i sum Dla dowolnego bloku sumatora pomi dzy pozycjami i oraz k (ke"se"i): ck+1 = Gk:i + Pk:ici przy tym Gk:i = Gk:s+1 + Pk:s+1Gs:i , Pk:i = Pk:s+1Ps:i . Poniewa Gk:k = gk = xk yk i Pk:k = pk = xk + yk (lub Pk:k = hk = xk �" yk ), wi c k Gk : i = gk + pk gk-1 +...+ pjgi , " j=i+1 k Pk : i = pj , " j=i  schemat wyznaczania funkcji Gi:0 i Pi:0 mo na optymalizowa  wszystkie funkcje Gi:0 i Pi:0 mo na wyznaczy w sekwencji ��log2n�� dziaB
a Warto sumy si zale y od hi, warto ci funkcji Gi-1:0, Pi-1:0 oraz c0: si = hi �" ci = hi �" (Gi-1: 0 + Pi-1: 0c0) � Janusz Biernat, AK1-7-09 Szybkie sumatory.doc, 4 listopada 2009 FAST 8  Szybkie sumatory Sumator z antycypacj przeniesie (carry look-ahead adder, 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 " zB
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) Uwaga: Analogiczne zale no ci mo na poda dla po yczek w odejmowaniu � Janusz Biernat, AK1-7-09 Szybkie sumatory.doc, 4 listopada 2009 FAST 9  Szybkie sumatory ModuB
sumatora z antycypacj przeniesie (CLA) xi+3 yi+3 xi+2 yi+2 xi+1 yi+1 xi yi CLA pi+3 gi+3 pi+2 gi+2 pi+1 gi+1 pi gi ci ci+2 ci+1 ci+3 Gi+4:i Pi+4:i ci+4 si+3 si+2 si+1 si Czterobitowy sumator CLA z sygnaB
ami G,P dla bloku CLG � Janusz Biernat, AK1-7-09 Szybkie sumatory.doc, 4 listopada 2009 FAST 10  Szybkie sumatory WielomoduB
owy sumator�w z antycypacj przeniesie (CLA) x x7:4 x15:12 y11:8 y7:4 x3:0 y15:12 11:8 y3:0 c c12 c8 c4 16 c0 CLA CLA CLA CLA s15:12 s11:8 s7:4 s3:0 Sumator zbudowany z kaskady blok�w CLA x x7:4 x15:12 y11:8 y7:4 x3:0 y15:12 11:8 y3:0 c4 c12 c8 c0 CLA CLA CLA CLA GP7:4 GP GP GP 3:0 15:12 11:8 CLG c16 s15:12 s11:8 s7:4 s3:0 Sumator CLA z blokiem wytwarzania przeniesie CLG � Janusz Biernat, AK1-7-09 Szybkie sumatory.doc, 4 listopada 2009 FAST 11  Szybkie sumatory Sumatory prefiksowe (PPA) sumator prefiksowy  parallel prefix adder, PPA blok GP  wytwarzanie warto ci wszystkich przeniesie ci = Gi-1: 0 + Pi-1: 0c0 si = hi �" ci = hi �" (Gi-1: 0 + Pi-1: 0c0) xi yi xk 1 yk 1 xi 1 yi 1 x0 y0 GP c0 sk 1 si si 1 s0 si = hi �"ci = hi �"Gi-1: 0 Je li c0=0, to ci=Gi 1:0 i wtedy , w przeciwnym razie problem: silne rozgaB
zienie sygnaB
u przeniesienia wej ciowego c0 � Janusz Biernat, AK1-7-09 Szybkie sumatory.doc, 4 listopada 2009 FAST 12  Szybkie sumatory Sumator prefiksowy z redukcj rozgaB
zienia Aby unikn rozgaB
ziania sygnaB
u c0 w obliczaniu ci = Gi-1: 0 + Pi-1: 0c0 mo na: a) doB
czy blok wej ciowy CSA, redukuj cy sygnaB
c0 xk yk xk yk xk yk x y x y x y x y c cwe= sumator PPA cwy b) potraktowa
c0 jako funkcj
generowania przeniesienia z pozycji   1 : g 1=c0, za[
c 1=0. Wtedy w sumatorze obejmuj
cym n+1 pozycji mamy: si = hi �" ci = hi �" Gi-1:-1 = hi �" (Gi-1:1 + Pi-1:1G0:-1) co jest r�wnowa\
ne zast
pieniu sygnaB
u g0 przez * g0 = G0:-1 = g0 + p0g-1 = g0 + p0c0 * Tworzenie alternatywnego sygnaB
u p0 jest zb
dne, bo c 1=0, wi
c c1 = g0. W obu wersjach op�z
nienie T jest takie jak w realizacji funkcji Gi 1:0+Pi 1:0 c0. Podobne rozwi
zania mo\
na zastosowa
w uniwersalnym sumatorze U2. � Janusz Biernat, AK1-7-09 Szybkie sumatory.doc, 4 listopada 2009 FAST 13  Szybkie sumatory Zasady konstrukcji sieci prefiksowej GP W
zeB
sieci GP realizuje funkcje (GHL , PHL ) = (GH , PH ) " (GL , PL ) = (GH + PH GL , PH PL ) Zasada konstrukcji struktury GP: integracja funkcji GH i PH oraz GL i PL 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 GHL i PHL s
nadmiarowe integracja nadmiarowa integracja optymalna integracja bB

dna " regularne struktury dla n=2k wej[

(pozycji), " w innych przypadkach przyj

k=int(1+log2n) i usun

zb
dne gaB

zie (sie
integruj
c
2k 1 pozycji poB

czy
sieci
integruj
c
pozostaB
e wej[
cia) � Janusz Biernat, AK1-7-09 Szybkie sumatory.doc, 4 listopada 2009 FAST 14  Szybkie sumatory PrzeksztaB
cenie prefiksowe Ladnera-Fischera (Sklansky ego)* minimalna liczba element�w Pi:i=xi�"yi, Gi:i=xiyi (i=0,1,& ,n-1) G0:0 Poziom 1 (i=0,1,& ,2- 1n-1) G1:0 (G2i+1:2i,P2i+1:2i)=(G2i+1:2i+1,P2i+1:2i+1)l(G2i:2i,P2i:2i) Poziom 2 (i=0,1,& ,2- 2n-1; s=2,3) G3:0,G2:0 (G4i+s:4i,P4i+s:4i)=(G4i+s:4i+2,P4i+s:4i+2)l(G4i+1:4i,P4i+1:4i) Poziom 3 (i=0,1,& ,2- 3n-1; s=4,5,6,7) G7:0,& ,G4:0 (G8i+s,8i,P8i+s,8i)=(G8i+s,8i+4,P8i+s,8i+4)l(G8i+3,8i,P8i+3,8i) Poziom 4 (i=0,1,& ,2- 4n-1; s=8,9,& ,15) G15:0,& ,G8:0 (G16i+s,16i,P16i+s,16i)=(G16i+s,16i+8,P16i+s,16i+8)l(G16i+7,16i,P16i+7,16i) & � Janusz Biernat, AK1-7-09 Szybkie sumatory.doc, 4 listopada 2009 FAST 15  Szybkie sumatory PrzeksztaB
cenie prefiksowe Kogge-Stone a* minimalizacja rozgaB
zie Pi:i=xi�"yi, Gi:i=xiyi (i=0,1,& ,n-1) G0:0 Poziom 1 (i=0,1,& ,2- 1n-1) G1:0 (Gi+1:i,Pi+1:i)=(Gi+1:i+1,Pi+1:i+1)l(Gi:i,Pi:i) Poziom 2 (s=0,1; i=0,1,& ,n-22) Gs+2:0=Gs+2,s+1+Ps+2,s+1Gs:0 (G3:0),G2:0 (Gi+3:i,Pi+3:i)=(Gi+3,i+2,Pi+3,i+2)l(Gi,i+1,Pi,i+1) G3:0 Poziom 3 (s=0,1,& ,22-1; i=0,1,& ,n-23) Gs+4:0=Gs+1,s+4+Ps+1,s+4Gs:0 (G7:0),G6:0,G5:0,G4:0 (Gi+7:i,Pi+7:i)=(Gi+7,i+4,Pi+7,i+4)l(Gi+3:i,Pi+3:i) G7:0 Poziom 4 (s=0,1,& ,23-1; i=0,1,& ,n-24) Gs+8:0=Gs+8,s+1+Ps+8,s+1Gs:0 (G15:0),& & ,G8:0 (Gi+15:i,Pi+15:i)=(Gi+15,i+8,Pi+15,i+8)l(Gi+7:i,Pi+7:i) G15:0 & � Janusz Biernat, AK1-7-09 Szybkie sumatory.doc, 4 listopada 2009 FAST 16  Szybkie sumatory PrzeksztaB
cenie prefiksowe Brenta-Kunga* optymalizacja struktury CMOS Pi:i=xi�"yi, Gi:i=xiyi (i=0,1,& ,n-1) G0:0 Poziom 1 (i=0,1,& ,2- 1n-1) G1:0 (G2i+1:2i,P2i+1:2i)=(G2i+1:2i+1,P2i+1:2i+1)l(G2i:2i,P2i:2i) Poziom 2 (i=0,1,& ,2- 2n-1) G3:0 (G4i+3:4i,P4i+3:4i)=(G4i+3:4i+2,P4i+3:4i+2)l(G4i+1:4i,P4i+1:4i) Poziom 3 (i=0,1,& ,2- 3n-1) G7:0 (G8i+7:8i,P8i+7:8i)=(G8i+7:8i+4,P8i+7:8i+4)l(G8i+3:8i,P8i+3:8i) & Poziom m=��log2n�� (T=2m-2) (G3T-1:0,P3T-1:0)=(G3T -1:2T,P3T -1:2T)l(G2T -1:0,P2T -1:0) G3T:0 (G0,n-1:0,Pn-1:0)=(Gn-1:2T,Pn-1:2T)l(G2T -1:0,P2T -1:0) Gn -1:0 & Poziom m+r (i=(0),1,& ,22-1, R=2m-2-s), r=1,& ,m-2 (GiR-1:0,PiR-1:0)=(GiR-1: 2R ,PiR-1: 2R)l(G2R -1:0,P2R -1:0) � Janusz Biernat, AK1-7-09 Szybkie sumatory.doc, 4 listopada 2009 FAST 17  Szybkie sumatory PrzeksztaB
cenie prefiksowe Han a-Carlsona* najpierw integracja rozB
cznych par Pi:i=xi�"yi, Gi:i=xiyi (i=0,1,& ,n-1) G0:0 Poziom 1 (i=0,1,& ,2- 1n-1) G1:0 (G2i+1:2i,P2i+1:2i)=(G2i+1:2i+1,P2i+1:2i+1)l(G2i:2i,P2i:2i) Poziom 2 (i=0,1,& ,2- 2n-1) G3:0 (G2i+3:2i,P2i+3:2i)=(G2i+3:2i+2,P2i+3:2i+2)l(G2i+1:2i,P2i+1:2i) Poziom 3 (i=0,1,& ,2- 3n-1, s=0,1) (G2i+7:2i,P2i+7:2i)=(G2i+7:2i+4,P2i+7:2i+4)l(G2i+3:2i,P2i+3:2i) G2s+5:0=G2s+5,2s+1+P2s+5,2s+1G2s:0 G7:0,G5:0 Poziom 4 (s=0,1,& ,22-1; i=0,1,& ,2- 3n-1) (G2i+15:2i,P2i+15:2i)=(G2i+15:2i+8,P2i+15:2i+8)l(G2i+7:2i,P2i+7:2i) G2s+9:0=G2s+9,2s+1+P2s+9,2s+1G2s:0 G15:0,G13:0,G11:0,G9:0 ... Poziom ��log2n��+1 (i=0,1,& ,2- 1n-1) G2i:0=G2i:2i+P2i:2iG2i-1:0 G2i:0,& ,G4:0,G2:0 � Janusz Biernat, AK1-7-09 Szybkie sumatory.doc, 4 listopada 2009 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 P =pi �  przekazywanie G oraz P i:i l  operator prefiksowy (GBA,PBA)=(GB,PB)l(GA,PA) � Janusz Biernat, AK1-7-09 Szybkie sumatory.doc, 4 listopada 2009 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, rozB
o\
ona obci
\
alno[

wyj[

Brent-Kung  >log2n poziom�w logicznych, mniej element�w GP, staB
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 przeB

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 � Janusz Biernat, AK1-7-09 Szybkie sumatory.doc, 4 listopada 2009 FAST 20  Szybkie sumatory Sumator ELM  koncepcja* Obliczona warto[

pocz
tkowa sumy hi=si:i na mo\
e ulec zmianie, je[
li ci=1. Niech si:r oznacza tymczasow sum
na pozycji i z uwzgl
dnieniem wszystkich wcze[
niejszych wej[

x#, y#, pocz
wszy od wej[
cia xr, yr. Mamy: si:r = hi�" Gi-1:r , si:0 = hi�" (Gi-1:0 + Hi-1:0c0 ) Z rekurencyjnego powi
zania funkcji Gi:j wynika dalej, \
e (i>r>j): si: j = hi�" Gi-1: j = hi�" Gi-1:r �" Gi-1:r �" (Gi-1:r + Hi-1:rGr -1: j ) = = si:r �" (Gi-1:r �" (Gi-1:r + Hi-1:rGr -1: j )) = si:r �" Gi-1:r Hi-1:rGr -1: j , Metod
indukcji mo\
na pokaza
, \
e Gi: j Hi: j = hiGi-1: j Hi-1: j = Hi: j , sk
d mamy: si:r = hi �" Gi-1:r , si: j = si:r �" Hi-1:rGr-1: j . przy tym bitami koD
cowej sumy s
si=si:0. Poniewa\
powy\
sze funkcje s
niezale\
ne, wi
c mo\
liwe jest wytworzenie sumy koD
cowej w strukturze zawieraj
cej log2n poziom�w. � Janusz Biernat, AK1-7-09 Szybkie sumatory.doc, 4 listopada 2009 FAST 21  Szybkie sumatory Sumator ELM  korekcja sum tymczasowych* Z podanych zale\
no[
ci wynika zasada konstrukcji sumatora, podobna jak PPA x7 y7 x6 y6 x5 y5 x4 y4 x3 y3 x2 y2 x1 y1 x0 y0 GPk:j+1 GPj:i g7 h7 g6 h6 g5 h5 g4 h4 g3 h3 g2 h2 g1 h1 g0 h0 GPk:i 1 sk+1:j GHj 1:i 2 3 sk+1:i s5 s4 s3 s2 s1 s0 c8 s7 s6 Schemat sumatora ELM (strukturze Ladnera-Fischera) Powi
zania sum mo\
na tak\
e zrealizowa
w strukturze Kogge a-Stone a. � Janusz Biernat, AK1-7-09 Szybkie sumatory.doc, 4 listopada 2009 FAST 22  Szybkie sumatory Sumy warunkowe  koncepcja (Sklansky) xi + yi L 1+0 0+0 1+1 1+0 0+1 1+1 1+0 0+1 0 ci0 0 0 1 0 0 1 0 0 +1 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 c1 0 1 1   2i+2 s1 1 1 1 0 0 1   2i+1:2i 0 2 c4i+4 0 1 0 s4i+3:4i 1 1 0 1 0 0 1 1 c1 0     4i+4 s1 1 1 1 0     4i+3:4i s3 1 1 1 0 0 0 1 1 7:0 � Janusz Biernat, AK1-7-09 Szybkie sumatory.doc, 4 listopada 2009 FAST 23  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 = 2ci0 + si0 oraz xi + yi +1 = 2ci:i + si:i :i :i 1 si:i = {si0 , si:i} = {xi �" yi , xi a" yi} :i 1 ci+1 = {ci0 ,ci+1} = {xi yi , xi + yi} +1 Poziom p (||  zB
o\
enie wektor�w)  warunkowe sumy s� i przeniesienia c� grup r=2p bit�w, 2ri+2r -1,2ri 2r (i+1)  dla i=0,1,...,��n�2 p��-1 s� = [c� s1 + (1- c� ) s1 ]|| s� , 2ri+2r -1,2ri 2ri+r 2ri+2r-1,2ri+r 2ri+r 2ri+2r -1,2ri+r 2ri+r -1,2ri 0 c� = c� c1 + (1- c� )c2ri+2r 2r (i+1) 2ri+r 2ri+2r 2ri+r KoD
cowy wynik sumowania powstaje na poziomie k=��log2n�� (r=2k). � Janusz Biernat, AK1-7-09 Szybkie sumatory.doc, 4 listopada 2009 FAST 24  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 � Janusz Biernat, AK1-7-09 Szybkie sumatory.doc, 4 listopada 2009 FAST 25  Szybkie sumatory Sumator sterowany przeniesieniem (CSLA) Sumator multipleksowany sterowany przeniesieniem (carry-select adder) wyb�r ki-pozycyjnych sum warunkowych zale\
nie od przeniesienia x ym,l xk,i yk,i x yl,k m,l l,k 0 CPA CPA CPA 0 s0 yi, x ym,l s0 sl,k yk,i xi, 0 0 x yl,k xk,i m,l m,l l,k k,i 1 0 CPA CPA CPA CPA 1 s1 s1 sl,k m,l k,i MPX MPX MPX s sl,k c si,0 sk,i m +1 m,l Schemat logiczny sumatora multipleksowanego sterowanego przeniesieniem Sumy blokowe obliczane jednocze[
nie �! wy\
sze bity�!wi
ksze bloki Op�z
nienie  > 2 2n (optymalna liczba blok�w  okoB
o 2n ) � Janusz Biernat, AK1-7-09 Szybkie sumatory.doc, 4 listopada 2009 FAST 26  Szybkie sumatory Sumator z przeskokiem przeniesieD
(CSKA)* Suma w bloku s-bitowym zale\
y od przeniesienia wej ciowego (carry-in). propagacja przeniesienia przez caB
y blok �!  przeskok przeniesienia x yn,m x ym,l yl,k ck+1 xj,i yj,i xi,0 yi,0 c0 xl,k n,m m,l CPA CPA CPA CPA CPA c ci P0 si,0 c P sn,m m+1 P Pl,k cj+1 P sj,i +1 i, sm,l cl +1 sl,k m,l n+1 n,m j,i ... Schemat sumatora z przeskokiem przeniesieD
CSKA (carry-skip adder) Op�z
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 koD
czy si
propagacja,  czasu przeskoku przeniesienia przez bloki wewn
trzne. l jednakowych blok�w k-bitowych (n=kl) op�z
nienie wyniesie "0 = [(k -1) + l - 2 + (k -1)]� = [2k + nk-1 - 4]� e" 2[ 2n - 2]� � Janusz Biernat, AK1-7-09 Szybkie sumatory.doc, 4 listopada 2009 FAST 27  Szybkie sumatory Analiza szybko[
ci sumatora z przeskokiem przeniesieD
* 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�z
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 � Janusz Biernat, AK1-7-09 Szybkie sumatory.doc, 4 listopada 2009 FAST 28  Szybkie sumatory Optymalizacja sumatora z przeskokiem przeniesieD
* ZaB
o enie: standardowe op� nienia prostych funkcji Heureza " B
aD
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�z
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�z
nienie gv+s� = (gv+i-1)� +(s-i)� = (gv+s-1)� ; " B
aD
cuchy nieoptymalne: je[
li skrajne bloki B
aD
cucha nie s
skrajnymi blokami B
aD
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 . � Janusz Biernat, AK1-7-09 Szybkie sumatory.doc, 4 listopada 2009 FAST 29  Szybkie sumatory Optymalizacja sumatora z przeskokiem przeniesieD
 przykB
ad* " n-bitowy B
aD
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 PrzykB
ad. Sumator 32-bitowy powinien mie
d"8 blok�w (32=62 22) liczba grup struktura sumatora maksymalne op�z
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 PrzykB
ad. Sumator 24-bitowy powinien mie
d"8 blok�w (24=52 12) liczba grup struktura sumatora maksymalne op�z
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 � Janusz Biernat, AK1-7-09 Szybkie sumatory.doc, 4 listopada 2009 FAST 30  Szybkie sumatory Inkrementer i dekrementer wykonuje dziaB
anie X�1 �! wystarczy B
aD
cuch p�B
sumator�w (HA) lub p�B
subtraktor�w (HS) p�B
sumator (half adder, HA)  realizuje funkcje si = xi �" ci, ci+1 = xici p�B
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 ukB
ad zliczaj cy  inkrementer/dekrementer ze sprz eniem xi(t +1) = si(t) ( ( ( ( i zapami tywaniem stanu S(t) = {skt ) ,skt) ,...,s1t),s0t) -1 -2 � Janusz Biernat, AK1-7-09 Szybkie sumatory.doc, 4 listopada 2009 FAST 31  Szybkie sumatory Szybko[

dziaB
ania i zB
o\
ono[

sumator�w Charakterystyki AT " sumator peB
ny 1-bitowy FA  A=7, T=2+2 �! AT=28  2�XOR, 1�OR, 2�AND �! op�z
nienie przeniesienia 2, sumy 2+2 " sumator RCA  A=7n, T=2n �! AT=14n2  n�FA �! op�z
nienie przeniesienia n�"2 " sumator kaskadowy CLA  AH"7n, TH"4logn �! ATH"56nlogn  n�FA �! logn blok�w, op�z
nienie przeniesienia 2�"2logn " sumator PPA  AH"5n+3nlog n , TH"3+2logn �! ATH"3nlog2n+14nlogn  logn poziom�w GP, op�z
nienie przeniesienia 2logn " sumator COSA  A=3nlogn, T=2+2logn �! ATH"6nlog2n  2�RCA, logn poziom�w MPX, op�z
nienie przeniesienia 2�"logn " sumator CSKA  AH"8n, TH"2�" 2 n �! ATH"32n n  n�FA+2 n �MPX, 2 n blok�w �! op�z
nienie przeniesienia 2�" 2 n " sumator CSLA  AH"2�"7n, TH" 2 2n �! ATH"39n n  2�RCA, 2n blok�w, op�z
nienie przeniesienia 2�" 2n � Janusz Biernat, AK1-7-09 Szybkie sumatory.doc, 4 listopada 2009 FAST 32