Opteller die de overdracht (carry) parallel bepaalt uit het generatiesignaal g = a·b en het propagatiesignaal p = a ⊕ b van elke positie, zonder te wachten op doorgifte van lagere posities. De vertraging blijft klein, ook bij veel bits.
Japanse benaming: 桁上げ先見加算器
“Carry-lookahead-opteller” komt voor in 3 oefenvragen uit 2 onderwerpen, bijv. Computerarithmetiek, Logische schakelingen.
Vakgebied: Computerarithmetiek
Voor elk bit met ingangen a en b is het generatiesignaal g = a·b gelijk aan 1 als het bit een carry produceert, ongeacht de inkomende carry, en het propagatiesignaal p = a ⊕ b gelijk aan 1 als een inkomende carry wordt doorgegeven. De uitgaande carry is c(i+1) = g(i) + p(i)·c(i) en de som is s(i) = p(i) ⊕ c(i). Door de recursie uit te schrijven krijg je c1 = g0 + p0·c0 en c2 = g1 + p1·g0 + p1·p0·c0, zodat elke carry in logica met twee niveaus kan worden geschreven met alleen de g- en p-signalen en de ingangscarry c0.
In een ripple-carry-opteller moet elke full adder wachten op de carry van het bit eronder. In het slechtste geval, zoals bij het optellen van 1 bij een woord met alleen enen, loopt de carry door alle bits, zodat de vertraging lineair met de breedte toeneemt; een 64-bit ripple-carry-opteller is veel te traag voor een processor met een klokfrequentie in het gigahertzbereik. Een carry-lookahead-opteller (CLA) berekent de carries parallel rechtstreeks uit de ingangen, en met hiërarchische lookahead groeit de vertraging slechts met de logaritme van de breedte.
Volledig uitgeschreven carryvergelijkingen vereisen al snel poorten met te veel ingangen, dus praktische ontwerpen gebruiken blokken van ongeveer 4 bits. Elk blok levert een groeps-generate G = g3 + p3·g2 + p3·p2·g1 + p3·p2·p1·g0 en een groeps-propagate P = p3·p2·p1·p0. Een lookahead-eenheid op het tweede niveau behandelt deze precies als g- en p-signalen van één bit om de carries naar elk blok te berekenen, en een derde niveau breidt het schema uit tot 64 bits. Parallel-prefixoptellers zoals Kogge-Stone en Brent-Kung generaliseren hetzelfde idee en ruilen bedrading en oppervlak in tegen logische diepte.
Snelle optellers zitten in ALU's, adresgeneratoren en floating-point-eenheden, en in de laatste trap van vermenigvuldigers. Een vermenigvuldiger reduceert eerst zijn vele partiële producten met carry-save-optellers: onafhankelijke full adders die drie getallen omzetten in twee met slechts één full-adder-vertraging en zonder carrypropagatie. Alleen de laatste twee getallen hebben een optelling met carrypropagatie nodig, die één keer wordt uitgevoerd door een carry-lookahead- of prefixopteller. Andere compromissen, zoals carry-select- en carry-skip-optellers, zitten qua snelheid en oppervlak tussen ripple-carry en volledige lookahead in.
Antwoord: C. Omdat de carry van elk bit parallel uit de ingangen wordt berekend zonder te wachten op doorgifte van lagere posities
Een carry-lookahead-opteller gebruikt per bit generate G = A·B (geeft altijd een carry) en propagate P = A⊕B (geeft de carry van de lagere positie door), en berekent de carry van elke positie parallel uit de ingangen, zoals C1 = G0 + P0·C0 en C2 = G1 + P1·G0 + P1·P0·C0 … De vertraging neemt dan alleen evenredig met de logaritme van het aantal bits toe. Omdat de uitdrukkingen lang worden, worden blokken van ongeveer 4 bits hiërarchisch gecombineerd.
Antwoord: B. g = a·b, p = a ⊕ b, c(i+1) = g + p·c(i)
Als a en b op die positie beide 1 zijn, ontstaat altijd een overdracht, ongeacht de overdracht van onderaf, dus het generatiesignaal is g = a·b. Als slechts één van a en b 1 is, wordt de overdracht van onderaf ongewijzigd doorgegeven, dus het propagatiesignaal is p = a ⊕ b (soms wordt OR gebruikt). Hieruit volgt c(i+1) = g(i) + p(i)·c(i); wordt dit uitgewerkt, dan kunnen de overdrachten van alle posities parallel in twee logische niveaus worden bepaald uit uitsluitend de g en p van de ingangen en de laagste overdracht. Formules waarin generatie en propagatie zijn verwisseld, rekenen niet juist.
Een ripple-carry-opteller wacht tot de carry bit voor bit door alle posities is gelopen, zodat de vertraging lineair met de breedte groeit. Een carry-lookahead-opteller berekent alle carries parallel uit de generate- en propagate-signalen, zodat de vertraging ongeveer met de logaritme van de breedte groeit.
Ja, voor de carryketen: p = a + b geeft dezelfde carries, omdat de generate-term de carry al produceert als beide ingangen 1 zijn. Het sombit heeft nog steeds a ⊕ b nodig, dus veel ontwerpen berekenen XOR voor p en gebruiken die voor beide.
Ze vatten een blok bits samen: groeps-generate is 1 als het blok zelf een uitgaande carry produceert, en groeps-propagate is 1 als een carry die het blok binnenkomt er helemaal doorheen wordt doorgegeven. Hogere lookahead-niveaus gebruiken ze om blokcarries snel te berekenen.
Een carry-lookahead-opteller gebruikt per bit generate G = A·B (geeft altijd een carry) en propagate P = A⊕B (geeft de carry van de lagere positie door), en berekent de carry van elke positie parallel uit de ingangen, zoals C1 = G0 + P0·C0 en C2 = G1 + P1·G0 + P1·P0·C0 … De vertraging neemt dan alleen evenredig met de logaritme van het aantal bits toe.
Wat is de juiste reden dat een carry-lookahead-opteller sne…Door dit te herhalen worden de partiële producten tot twee teruggebracht, waarna één keer met bijvoorbeeld een carry-lookahead-opteller wordt opgeteld.
Wat is de belangrijkste reden dat een carry-save-opteller w…Carry-save-opteller (CSA) Volledige opteller (full adder) Afronden naar even (round to nearest even) bfloat16 Booth-algoritme Cancellation (verlies van significantie) Exponent FMA (fused multiply-add) FP8 Gedenormaliseerd getal (subnormaal getal)