Bär spara adder

En bärsparadderare [ 1] [2] är en typ av digital adderare som används i datormikroarkitektur för att beräkna summan av tre eller fler n-bitars tal i det binära talsystemet . Den skiljer sig från andra digitala adderare genom att dess utgångar är två tal av samma dimension som ingångarna, den ena är en delsumma av bitarna och den andra är en sekvens av bärbitar .

Motivation

Tänk på summan:

12345678 + 87654322 =100000000

Använd aritmetik, från höger till vänster: "8+2=0, bär 1", "7+2+1=0, bär 1", "6+3+1=0, bär 1" och så vidare till slutet av summan. Men vi vet att tills den sista siffran i resultatet erhålls, vet vi inte den första siffran till vänster förrän vi går igenom varje siffra i beräkningen, och bär bäringen från varje siffra till nästa till vänster om den. Att lägga till två n-bitars tal kommer alltså att ta tid proportionellt mot n, även om maskinen vi använder kan göra många beräkningar samtidigt.

I elektroniska termer, med hjälp av bitar (binära siffror), betyder detta att även om vi har n en-bits adderare till vårt förfogande, måste vi fortfarande spendera tid proportionell mot n för att tillåta överföringen att fortplanta sig från ena änden av numret till Övrig. Medan vi gör det här

1. Vi känner inte till resultatet av tillägget. 2. Vi vet inte om resultatet av tillägget blir mindre eller större än det givna talet (vi vet till exempel inte om det blir positivt eller negativt).

En överföringsadderare kan minska latensen. I princip kan fördröjningen minskas så att den är proportionell mot log n , men för stora antal är detta inte längre fallet, eftersom även när accelererad överföring tillämpas ökar avståndet som signalen färdas längs chippet proportionellt mot n och spridningsfördröjningen ökar i denna samma attityd. När vi väl har fått 512-bitars till 2048-bitars numren som krävs i kryptosystem med offentliga nyckel , hjälper vidarebefordran inte längre.

Grundkoncept

Idén att fördröja lösningen av överföringen till slutet, eller behålla överföringarna, tillhör John von Neumann . [3]

Här är ett exempel på binär addition:

10111010101011011111000000001101 + 11011110101011011011111011101111.

Bärbevarande aritmetik fungerar genom att lämna binär notation medan du fortfarande arbetar i bas 2. Den beräknar summan siffra för siffra, som

10111010101011011111000000001101 + 11011110101011011011111011101111 = 211221202020220221221110111102212.

Notationen är okonventionell, men resultatet förblir entydigt. Dessutom, givet n adderare (här, n = 32 hela adderare), kan resultatet beräknas efter att ingångarna har passerat genom en adderare (i en generatorcykel), eftersom varje siffra i resultatet är oberoende av någon annan.

Om en adderare krävs för att addera två tal och beräkna resultatet, är bärbevarande addition olämpligt, eftersom resultatet förblir konverterbart tillbaka till binärt, vilket innebär att bärarna ännu inte har spridits från höger till vänster. Men i aritmetik med stora heltal är addition en mycket sällsynt operation, och överföringsbevarande adderare används vanligtvis för att ackumulera delsummor i en multiplikator.

Bär spara enheter

Anta att vi har två minnesbitar för varje siffra i resultatet, då kan vi använda redundant binär representation och lagra värdena 0, 1, 2 eller 3 i varje sifferposition. Detta beror på att mer än ett binärt tal kan läggas till vårt bärbevarande resultat utan att vår minneskapacitet fylls över: men vad då?

Nyckeln till förståelsen är att under varje deltillägg lägger vi till tre bitar:

Med andra ord tar vi bärsiffran från positionen till höger och bär bärsiffran till vänster, precis som i traditionell addition; men bärsiffran vi skickar till vänster är resultatet av den tidigare beräkningen, inte den nuvarande. För varje cykel av generatorn rör sig bärarna endast ett steg framåt, och inte n steg, som i traditionell addition.

Eftersom signalerna inte går så långt kan generatorn ticka snabbare.

I slutet av beräkningen återstår behovet av att konvertera resultatet till binärt, vilket egentligen bara innebär att låta bär gå hela vägen genom numret precis som i en traditionell adderare. Men om vi gjorde 512 additioner i processen att göra en 512-bitars multiplikation, delas den stora kostnaden för denna slutliga transformation faktiskt med alla 512 additioner, så varje addition bär bara 1/512 av den stora kostnaden för den slutliga "normala" tillägg.

Nackdelar

Vid varje tillsatssteg med överföringskonservering,

  1. Vi vet resultatet av tillägget direkt.
  2. Vi vet fortfarande inte om resultatet av additionen är större eller mindre än det givna talet (vi vet till exempel inte om det är positivt eller negativt).

Denna sista punkt är en nackdel när man använder överföringsbevarande adderare för att utföra modulo-multiplikationer (multiplikationer efter division, behåller bara resten). Om vi ​​inte kan veta om det mellanliggande resultatet är större eller mindre än modulerna, hur kan vi då veta om vi ska subtrahera moduler eller inte?

Montgomery-multiplikationen , som beror på siffran längst till höger i resultatet, är en lösning; som är mer som bärbevarande addition i sig, den har en konstant overhead, så Montgomery multiplikationssekvensen sparar tid, men den enstaka gör det inte. Lyckligtvis är exponentiering, som faktiskt är en sekvens av multiplikationer, den vanligaste operationen i kryptografi med offentliga nyckel.

Tekniska detaljer

En bärsparande anordning består av n fulla adderare , som var och en beräknar en enbitssumma och en bärbit helt baserat på motsvarande bitar av de tre ingångstalen. Givet tre n -bitars tal a , b och c , producerar det en partiell summa ps och en skiftad carry sc :

Det totala beloppet kan sedan beräknas:

  1. Genom att flytta överföringssekvensen sc åt vänster ett ställe.
  2. Genom att lägga till 0 till vänster om (den mest signifikanta biten ) partiella summasekvensen ps .
  3. Använda en carry-to-carry-adderare för att addera de två tillsammans och producera det resulterande n + 1-bitarsvärdet.

När tre eller fler siffror läggs ihop är det snabbare att använda en lagringsadderare följt av en på varandra följande adderare än att använda två på varandra följande bäradderare. Detta beror på att den sekventiella adderaren inte kan beräkna summan av bitarna utan att vänta på att den föregående överföringsbiten ska beräknas, och har således samma latens som n fulla adderare. En överföringssparadderare beräknar alla sina utgångskvantiteter parallellt och har således samma latens som en enda fulladderare. Sålunda är den totala beräkningstiden (i enheter av full additionsfördröjningstid) för en överföringssparadderare plus en överförings-i-sekvensadderare n + 1, medan den för två på varandra följande adderare bör vara 2 n .

Se även

Anteckningar

  1. ↑ Earle, JG et al . US-patent 3 340 388 "Latched Carry Save Adder Circuit for Multipliers" inlämnad 12 juli 1965
  2. ↑ Earle, J. (mars, 1965), Latched Carry-Save Adder, IBM Technical Disclosure Bulletin Vol 7 (10): 909–910  
  3. ↑ John von Neumann, Samlade verk.