plik


ÿþ 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  staBy od chwili ustalenia przeniesienia " gwarantowany czas wykonania dodawania/odejmowania zale y od najdBu szego czasu przesBania 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ównolegBych (parallel prefix adder, PPA) " skracanie cie ki propagacji przeniesienia (carry skip adder, CSKA) SkBadanie sum tymczasowych " skBadanie 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ównolegBe wytwarzanie alternatywnych sum cz ciowych " skBadanie sum korygowanych (carry-increment adder, CIA)  korekcja sum blokowych przeniesieniami " obliczanie i korekcja sum tymczasowych (ELM) SkBadanie 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). SkBadowymi 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óBsumy, 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). SkBadowymi 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óBró 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 przesyBane 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 przesyBane 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 dziaBaniem B cznym (asocjacyjnym) PHLF = PH PL PF = PH PLPF Wyznaczanie funkcji wytwarzania (generowania) przeniesienia G w bloku sumatora jest tak e dziaBaniem 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ùø dziaBa 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 " zBo 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 sygnaBami G,P dla bloku CLG © Janusz Biernat, AK1-7-09 Szybkie sumatory.doc, 4 listopada 2009 FAST 10 Szybkie sumatory WielomoduBowy 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 sygnaBu 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 sygnaBu 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 obejmujcym n+1 pozycji mamy: si = hi •" ci = hi •" Gi-1:-1 = hi •" (Gi-1:1 + Pi-1:1G0:-1) co jest równowa\ne zastpieniu sygnaBu g0 przez * g0 = G0:-1 = g0 + p0g-1 = g0 + p0c0 * Tworzenie alternatywnego sygnaBu p0 jest zbdne, bo c 1=0, wic c1 = g0. W obu wersjach opóznienie T jest takie jak w realizacji funkcji Gi 1:0+Pi 1:0 c0. Podobne rozwizania 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 WzeB 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 obejmujcych ssiadujce 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 bBdna " regularne struktury dla n=2k wej[ (pozycji), " w innych przypadkach przyj k=int(1+log2n) i usun zbdne gaBzie (sie integrujc 2k 1 pozycji poBczy sieci integrujc pozostaBe wej[cia) © Janusz Biernat, AK1-7-09 Szybkie sumatory.doc, 4 listopada 2009 FAST 14 Szybkie sumatory PrzeksztaBcenie 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 PrzeksztaBcenie 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 PrzeksztaBcenie 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 PrzeksztaBcenie 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, wicej elementów GP, rozBo\ona obci\alno[ wyj[ Brent-Kung  >log2n poziomów logicznych, mniej elementów GP, staBa 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 przeBczenia 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[ pocztkowa sumy hi=si:i na mo\e ulec zmianie, je[li ci=1. Niech si:r oznacza tymczasow sum na pozycji i z uwzgldnieniem wszystkich wcze[niejszych wej[ x#, y#, poczwszy od wej[cia xr, yr. Mamy: si:r = hi•" Gi-1:r , si:0 = hi•" (Gi-1:0 + Hi-1:0c0 ) Z rekurencyjnego powizania 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 , skd mamy: si:r = hi •" Gi-1:r , si: j = si:r •" Hi-1:rGr-1: j . przy tym bitami koDcowej sumy s si=si:0. Poniewa\ powy\sze funkcje s niezale\ne, wic mo\liwe jest wytworzenie sumy koDcowej w strukturze zawierajcej 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) Powizania 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 (||  zBo\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 KoDcowy 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’!wiksze bloki Opóznienie  > 2 2n (optymalna liczba bloków  okoBo 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 caBy 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óznienie 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 koDczy si propagacja,  czasu przeskoku przeniesienia przez bloki wewntrzne. l jednakowych bloków k-bitowych (n=kl) opóznienie 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óznienie 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* ZaBo enie: standardowe opó nienia prostych funkcji Heureza " BaDcuchy optymalne: je[li rozmiar k bloków wytwarzajcych mniej znaczce pozycje sumy jest typu gu +i = gu+i-1 +1, i=1,2,...,k , to maksymalne opóznienie gu+k´ = (gu+i-1)´ +(k-i)´ = (gu+k-1)´ ; je[li rozmiar s bloków wytwarzajcych bardziej znaczce pozycje sumy jest typu gv+i = gv+i-1 -1, i=0,1,2,...,s-1, to maksymalne opóznienie gv+s´ = (gv+i-1)´ +(s-i)´ = (gv+s-1)´ ; " BaDcuchy nieoptymalne: je[li skrajne bloki BaDcucha nie s skrajnymi blokami BaDcuchó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  przykBad* " n-bitowy BaDcuch 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 PrzykBad. Sumator 32-bitowy powinien mie d"8 bloków (32=62 22) liczba grup struktura sumatora maksymalne opóznienie 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 PrzykBad. Sumator 24-bitowy powinien mie d"8 bloków (24=52 12) liczba grup struktura sumatora maksymalne opóznienie 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 dziaBanie X±1 ’! wystarczy BaDcuch póBsumatorów (HA) lub póBsubtraktorów (HS) póBsumator (half adder, HA)  realizuje funkcje si = xi •" ci, ci+1 = xici póBsubtraktor (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 ukBad 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[ dziaBania i zBo\ono[ sumatorów Charakterystyki AT " sumator peBny 1-bitowy FA  A=7, T=2+2 ’! AT=28  2×XOR, 1×OR, 2×AND ’! opóznienie przeniesienia 2, sumy 2+2 " sumator RCA  A=7n, T=2n ’! AT=14n2  n×FA ’! opóznienie przeniesienia nÅ"2 " sumator kaskadowy CLA  AH"7n, TH"4logn ’! ATH"56nlogn  n×FA ’! logn bloków, opóznienie przeniesienia 2Å"2logn " sumator PPA  AH"5n+3nlog n , TH"3+2logn ’! ATH"3nlog2n+14nlogn  logn poziomów GP, opóznienie przeniesienia 2logn " sumator COSA  A=3nlogn, T=2+2logn ’! ATH"6nlog2n  2×RCA, logn poziomów MPX, opóznienie przeniesienia 2Å"logn " sumator CSKA  AH"8n, TH"2Å" 2 n ’! ATH"32n n  n×FA+2 n ×MPX, 2 n bloków ’! opóznienie przeniesienia 2Å" 2 n " sumator CSLA  AH"2Å"7n, TH" 2 2n ’! ATH"39n n  2×RCA, 2n bloków, opóznienie przeniesienia 2Å" 2n © Janusz Biernat, AK1-7-09 Szybkie sumatory.doc, 4 listopada 2009 FAST 32

Wyszukiwarka

Podobne podstrony:
2006 szybkie sumatory
Crocker Zbyt szybkie wycofanie oddziałów z Iraku to błąd (24 01 2009)
2009 8 sumatory csa i multyplikatory
2009 2010 rejon
2009 pytania testowe
[W] Badania Operacyjne Zagadnienia transportowe (2009 04 19)
Twilight Saga New Moon 2009 CAM XviD POISON
2009 03 Our 100Th Issue
Doghouse (2009)
Marketing Opracowane Pytania Egzaminacyjne 2009 Furtak (46)
2009 SP Kat prawo cywilne cz II
predator drone readout 2009
2009 03 BP KGP Niebieska karta sprawozdanie za 2008rid&657
2009 12 Metaprogramowanie algorytmy wykonywane w czasie kompilacji [Programowanie C C ]

więcej podobnych podstron