Kogge–Stenhuggorm
| Del av en serie om | |||||||
| aritmetiska logiska kretsar | |||||||
|---|---|---|---|---|---|---|---|
| Snabbnavigering | |||||||
|
Komponenter
|
|||||||
|
Kategorier |
|||||||
|
Se även |
|||||||
Inom databehandling är Kogge –Stone-adderaren ( KSA eller KS ) ett parallellt prefix från bära framsynsadderare . Andra parallella prefixadderare (PPA) inkluderar Brent-Kung-adderaren (BKA), Han-Carlson-adderaren (HCA) och den snabbaste kända varianten, Lynch -Swartzlander-spanande trädadderaren (STA).
Kogge –Stone adderaren tar mer yta att implementera än Brent–Kung adderaren, men har en lägre fan-out i varje steg, vilket ökar prestandan för typiska CMOS processnoder. Däremot är ledningsstockningar ofta ett problem för Kogge–Stone huggormar. Lynch-Swartzlander-designen är mindre, har lägre fan-out och lider inte av ledningsstockningar; För att kunna användas måste dock processnoden stödja implementeringar av Manchester carry chain . Det allmänna problemet med att optimera parallella prefixadderare är identiskt med optimeringsproblemet med variabel blockstorlek, multi-level, carry-skip adderare , vars lösning finns i Thomas Lynchs avhandling från 1996.
Ett exempel på en 4-bitars Kogge–Stone adderare visas i diagrammet. Varje vertikalt steg producerar en "propagate" och en "generera" bit, som visas. De kulminerande genereringsbitarna ( bärarna ) produceras i det sista steget (vertikalt), och dessa bitar XOR 'd med den initiala fortplantningen efter inmatningen (de röda rutorna) för att producera summabitarna. Den första (minst signifikanta) summabiten beräknas t.ex. genom att XOR-föröka propagatet i den röda rutan längst till höger (en "1") med inlämningen (en "0"), vilket ger en "1". Den andra biten beräknas genom att XOR-förökningen i den andra rutan från höger (en "0") med C0 (en "0"), producerar en "0".
4-bitars Kogge-Stone adder utan Cin:
P00 = A0 XOR B0 '1dt, S0, dt - typfördröjningstid G00 = A0 OCH B0 '1dt, C0 P10 = A1 XOR B1 '1dt G10 = A1 OCH B1 '1dt P20 = A2 XOR B2 '1dt G20 = A2 OCH B2 '1dt P30 = A3 XOR B3 '1dt G30 = A3 OCH B3 '1dt G11 = G10 ELLER (P10 OCH G00) '3dt, C1 P21 = P20 OCH P10 '2dt G21 = G20 ELLER (P20 OCH G10) '3dt P31 = P30 OCH P20 '2dt G31 = G30 ELLER (P30 OCH G20) '3dt G22 = G21 ELLER (P21 OCH G00) '5dt, C2 G32 = G31 ELLER (P31 OCH G11) '5dt, C3, Cout S0 = P00 '1dt S1 = P10 XOR G00 '2dt S2 = P20 XOR G11 '4dt S3 = P30 XOR G22 '6dt
4-bitars Kogge-Stone adder med Cin:
G0a = A0 OCH Cin '1dt G0b = B0 OCH Cin '1dt G0c = A0 OCH B0 '1dt P00 = A0 XOR B0 '1dt G00 = G0a ELLER G0b ELLER G0c '2dt, C0 P10 = A1 XOR B1 '1dt G10 = A1 OCH B1 '1dt P20 = A2 XOR B2 '1dt G20 = A2 OCH B2 '1dt P30 = A3 XOR B3 '1dt G30 = A3 OCH B3 '1dt G11 = G10 ELLER (P10 OCH G00) '4d, C1 P21 = P20 OCH P10 ' 2dt G21 = G20 ELLER (P20 OCH G10) '3dt P31 = P30 OCH P20 '2dt G31 = G30 ELLER (P30 OCH G20) '3dt G22 = G21 ELLER (P21 OCH G00) '5P, C2 G32 = G31 ELLER ( G11) '5dt, C3, Cout S0 = P00 XOR Cin '2dt S1 = P10 XOR G00 '3dt S2 = P20 XOR G11 '5dt S3 = P30 XOR G22 '6dt
Kogge-Stone adder-konceptet utvecklades av Peter M. Kogge och Harold S. Stone , som publicerade det i en framstående tidning 1973 med titeln A Parallel Algorithm for the Efficient Solution of a General Class of Recurrence Equations .
Förbättringar
Förbättringar av den ursprungliga implementeringen inkluderar ökning av adderarens radix och sparsitet. Adderarens radix hänvisar till hur många resultat från föregående beräkningsnivå som används för att generera nästa . Den ursprungliga implementeringen använder radix-2, även om det är möjligt att skapa radix-4 och högre. Om du gör det ökar effekten och fördröjningen för varje steg, men minskar antalet nödvändiga steg. I den så kallade sparse Kogge–Stone-adderaren (SKA) avser sparsiteten hos adderaren hur många bärbitar som genereras av bärträdet. Att generera varje bärbit kallas sparsity-1, medan att generera varannan är sparsity-2 och var fjärde är sparsity-4. De resulterande bärarna används sedan som inmatningsingångar för mycket kortare rippelbäradderare eller någon annan adderardesign, som genererar de slutliga summabitarna. Ökande sparsitet minskar den totala beräkningen som behövs och kan minska mängden routingstockning.
Ovan är ett exempel på en Kogge–Stenhuggorm med sparsity-4. Element eliminerade av gleshet visas markerade med transparens. Som visat förbättras kraften och arean för överföringsgenereringen avsevärt, och routingstockningen minskas avsevärt. Varje genererad bära matar en multiplexer för en bärväljaradderare eller införandet av en rippelbäradderare.
16-bitars Kogge-Stone adder utan Cin:
P00 = A0 XOR B0 '1dt, S0, dt - typfördröjningstid G00 = A0 OCH B0 '1dt, C0 P10 = A1 XOR B1 '1dt G10 = A1 OCH B1 '1dt P20 = A2 XOR B2 '1dt G20 = A2 OCH B2 '1dt P30 = A3 XOR B3 '1dt G30 = A3 OCH B3 '1dt P40 = A4 XOR B4 '1dt G40 = A4 OCH B4 '1dt P50 = A5 XOR B5 '1dt G50 = A5 OCH B5 '1dt P60 = A6 XOR B6 ' 1dt G60 = A6 OCH B6 '1dt P70 = A7 XOR B7 '1dt G70 = A7 OCH B7 '1dt P80 = A8 XOR B8 '1dt G80 = A8 OCH B8 '1dt P90 = A9 XOR B9 '1dt G90 = A9 OCH B9 '1dt P100 = A10 XOR B10 '1dt G100 = A10 OCH B10 '1dt P110 = A11 XOR B11 '1dt G110 = A11 OCH B11 '1dt P120 = A12 XOR B12 '1dt G120 = A12 OCH B12 OCH B12 OCH B12 OCH B131AD ADJ 131 P = A13 OCH B13 '1dt P140 = A14 XOR B14 '1dt G140 = A14 OCH B14 '1dt P150 = A15 XOR B15 '1dt G150 = A15 OCH B15 '1dt G11 = G10 ELLER ( P10 OCH G00 'P10 OCH G00) OCH P10 '2dt G21 = G20 ELLER ( P20 OCH G10) '3dt P31 = P30 OCH P20 '2dt G31 = G30 ELLER ( P30 OCH G20) '3dt P41 = P40 OCH P30 '2dt G41 = G40 ELLER ( P40) ' 3dt P51 = P50 OCH P40 '2dt G51 = G50 ELLER ( P50 OCH G40) '3dt P61 = P60 OCH P50 '2dt G61 = G60 ELLER ( P60 OCH G50) '3dt P71 = P70 OCH P60 '2dt G71 ( G700 GOR OCH G60) '3dt P81 = P80 OCH P70 '2dt G81 = G80 ELLER ( P80 OCH G70) '3dt P91 = P90 OCH P80 '2dt G91 = G90 ELLER ( P90 OCH G80) '3dt P101 = P100 OCH P901 'dt G100 ELLER (P100 OCH G90) '3dt P111 = P110 OCH P100 '2dt G111 = G110 ELLER (P110 OCH G100) '3dt P121 = P120 OCH P110 '2dt G121 = G120 ELLER P1100 = P120 ELLER (P1200 OCH P1200) ' 0 '2dt G131 = G130 ELLER (P130 OCH G120) '3dt P141 = P140 OCH P130 '2dt G141 = G140 ELLER (P140 OCH G130) '3dt P151 = P150 OCH P140 '2dt G1505 OR = GPdt G15051 OCH 3dt = G21 ELLER ( P21 OCH G00) '5dt, C2 G32 = G31 ELLER ( P31 OCH G11) '5dt, C3 P42 = P41 OCH P21 '3dt G42 = G41 ELLER ( P41 OCH G21) '5dt P52 = P51 OCH P31 ' G52 = G51 ELLER ( P51 OCH G31) '5dt P62 = P61 OCH P41 '3dt G62 = G61 ELLER ( P61 OCH G41) '5dt P72 = P71 OCH P51 '3dt G72 = G71 ELLER ( P71 OCH G51) = P81 P OCH P61 '3dt G82 = G81 ELLER ( P81 OCH G61) '5dt P92 = P91 OCH P71 '3dt G92 = G91 ELLER ( P91 OCH G71) '5dt P102 = P101 OCH P81 '3dt G102 = G101 ELLER (P811) 5dt P112 = P111 OCH P91 '3dt G112 = G111 ELLER (P111 OCH G91) '5dt P122 = P121 OCH P101 '3dt G122 = G121 ELLER (P121 OCH G101) '5dt P131 = P131 OCH G131 '3 = P1121 '3 1 OCH G111) '5dt P142 = P141 OCH P121 '3dt G142 = G141 ELLER (P141 OCH G121) '5dt P152 = P151 OCH P131 '3dt G152 = G151 ELLER (P151 OCH G131 OCH G141 = G4dt = G4dt = G4dt (02) '7dt, C4 G53 = G52 ELLER ( P52 OCH G11) '7dt, C5 G63 = G62 ELLER ( P62 OCH G22) '7dt, C6 G73 = G72 ELLER ( P72 OCH G32) '7dt, C7 P83 = P82 OCH P42 '4dt G83 = G82 ELLER ( P82 OCH G42) '7dt P93 = P92 OCH P52 '4dt G93 = G92 ELLER ( P92 OCH G52) '7dt P103 = P102 OCH P62 '4dt G103 = G102 ELLER (P102 ' OCH P112) = P102 ' OCH P112) OCH P72 '4dt G113 = G112 ELLER (P112 OCH G72) '7dt P123 = P122 OCH P82 '4dt G123 = G122 ELLER (P122 OCH G82) '7dt P133 = P132 OCH P92 '4dt G13 OR = GP1dt G133 OR 7dt P143 = P142 OCH P102 '4dt G143 = G142 ELLER (P142 OCH G102) '7dt P153 = P152 OCH P112 '4dt G153 = G152 ELLER (P152 OCH G112) '7dt OCH G84 = G83dt (C83dt) G94 = G93 ELLER ( P93 OCH G11) '9dt, C9 G104 = G103 ELLER (P103 OCH G22) '9dt, C10 G114 = G113 ELLER (P113 OCH G32) '9dt, C11 G124 = G123 ELLER (P43) 'dt , C12 G134 = G133 ELLER (P133 OCH G53) '9dt, C13 G144 = G143 ELLER (P143 OCH G63) '9dt, C14 G154 = G153 ELLER (P153 OCH G73) '9dt, P15 '1dt = S10 G00 '2dt S2 = P20 XOR G11 '4dt S3 = P30 XOR G22 '6dt S4 = P40 XOR G32 '6dt S5 = P50 XOR G43 '8dt S6 = P60 XOR G53 '8dt S7 = P70 XOR G63 '8dt S8 = P80 XOR '8dt S9 = P90 XOR G84' 10DT S10 = P100 XOR G94 '10DT S11 = P110 XOR G104' 10DT S12 = P120 XOR G114 '10DT S13 = P130 XOR G124' 10DT S14 = P140 XOR 10dt
Vidare läsning
- Zeydel, Bart R. (2006). "Energifördröjningsegenskaper hos CMOS-addare". I Oklobdzija, Vojin G.; Krishnamurth, Ram K. (red.). Högpresterande energieffektiv mikroprocessordesign . Serie om integrerade kretsar och system. Dordrecht, Nederländerna: Springer . s. 147–169. doi : 10.1007/978-0-387-34047-0_6 . ISBN 0-387-28594-6 .