Purtați adăugarea de salvare

Un sumător de tip carry-save [ 1] [2] este un tip de sumător digital utilizat în microarhitectura computerelor pentru a calcula suma a trei sau mai multe numere de n biți în sistemul numeric binar . Diferă de alte sumătoare digitale prin faptul că ieșirile sale sunt două numere de aceeași dimensiune ca și intrările, unul fiind o sumă parțială a biților, iar celălalt fiind o secvență de biți de transport .

Motivație

Luați în considerare suma:

12345678 + 87654322 =100000000

Folosind aritmetica, de la dreapta la stânga: „8+2=0, carry 1”, „7+2+1=0, carry 1”, „6+3+1=0, carry 1” și așa mai departe până la sfârșit a sumei. Cu toate acestea, știm că până nu se obține ultima cifră a rezultatului, nu cunoaștem prima cifră din stânga până când trecem prin fiecare cifră din calcul, purtând transportul de la fiecare cifră la următoarea din stânga acesteia. Astfel, adăugarea a două numere de n biți va dura timp proporțional cu n, chiar dacă mașina pe care o folosim este capabilă să facă multe calcule în același timp.

În termeni electronici, folosind biți (cifre binare), aceasta înseamnă că, chiar dacă avem n sumatori de un bit la dispoziție, tot trebuie să petrecem timp proporțional cu n pentru a permite transportului să se propagă de la un capăt al numărului la alte. În timp ce facem asta

1. Nu știm rezultatul adunării. 2. Nu știm dacă rezultatul adunării va fi mai mic sau mai mare decât numărul dat (de exemplu, nu știm dacă va fi pozitiv sau negativ).

Un adaugător reportat poate reduce latența. În principiu, întârzierea poate fi redusă astfel încât să fie proporțională cu log n , dar pentru numerele mari nu mai este cazul, deoarece chiar și atunci când se aplică transferul accelerat, distanța pe care o parcurge semnalul de-a lungul cipului crește proporțional cu n și intarzierea de propagare creste in aceasta aceeasi atitudine. Odată ce obținem numerele de 512 biți până la 2048 de biți care sunt necesare în criptosistemele cu cheie publică , redirecționarea nu mai ajută.

Concept de bază

Ideea de a amâna până la final rezoluția transferului sau de a păstra transferurile îi aparține lui John von Neumann . [3]

Iată un exemplu de adunare binară:

10111010101011011111000000001101 + 11011110101011011011111011101111.

Aritmetica care păstrează transportul funcționează lăsând notația binară în timp ce încă lucrează în baza 2. Calculează suma cifră cu cifră, ca

10111010101011011111000000001101 + 11011110101011011011111011101111 = 21122120202022022122111011102212.

Notația este neconvențională, dar rezultatul rămâne fără ambiguitate. Mai mult, având în vedere n sumatori (aici, n = 32 de sumători completi), rezultatul poate fi calculat după trecerea intrărilor printr-un sumător (într-un ciclu generator), deoarece fiecare cifră a rezultatului este independentă de oricare alta.

Dacă este necesar un adunator pentru a adăuga două numere și pentru a calcula rezultatul, adăugarea care păstrează transportul este nepotrivită, deoarece rezultatul rămâne convertibil înapoi în binar, ceea ce înseamnă că transporturile nu s-au propagat încă de la dreapta la stânga. Dar în aritmetica cu numere întregi mari, adăugarea este o operație foarte rară, iar sumatorii care păstrează transportul sunt utilizați în mod obișnuit pentru a acumula sume parțiale într-un multiplicator.

Transportați unități de salvare

Să presupunem că avem doi biți de memorie pentru fiecare cifră a rezultatului, atunci putem folosi reprezentarea binară redundantă , stocând valorile 0, 1, 2 sau 3 în fiecare poziție a cifrei. Acest lucru se datorează faptului că mai mult de un număr binar poate fi adăugat la rezultatul nostru de păstrare a transportului fără a ne depăși capacitatea de memorie: dar atunci ce?

Cheia pentru înțelegere este că în timpul fiecărei adăugări parțiale, adăugăm trei biți:

Cu alte cuvinte, luăm cifra de transport din poziția din dreapta și purtăm cifra de transport la stânga, la fel ca în plus tradițional; dar cifra de transport pe care o trecem la stânga este rezultatul calculului anterior , nu al celui curent. Pentru fiecare ciclu al generatorului, transporturile se deplasează doar cu un pas înainte, nu n pași ca în adaosul tradițional.

Deoarece semnalele nu se deplasează atât de departe, generatorul poate bifa mai repede.

La sfârșitul calculului, rămâne nevoia de a converti rezultatul în binar, ceea ce înseamnă, de fapt, să permiteți transporturilor să parcurgă numărul la fel ca într-un adunator tradițional. Dar dacă am făcut 512 adunări în procesul de a face o înmulțire pe 512 de biți, costul mare al acestei transformări finale este de fapt împărțit la toate cele 512 adunări, astfel încât fiecare adunare poartă doar 1/512 din costul mare al „normalului” final. plus.

Dezavantaje

La fiecare etapă de adăugare cu conservare prin transfer,

  1. Știm imediat rezultatul adăugării.
  2. Încă nu știm dacă rezultatul adunării este mai mare sau mai mic decât numărul dat (de exemplu, nu știm dacă este pozitiv sau negativ).

Acest ultim punct este un dezavantaj atunci când se utilizează sumatori care păstrează transportul pentru a efectua înmulțiri modulo (înmulțiri după împărțire, păstrând doar restul). Dacă nu putem ști dacă rezultatul intermediar este mai mare sau mai mic decât modulele, cum putem ști dacă să scădem module sau nu?

Înmulțirea Montgomery , care depinde de cifra cea mai din dreapta a rezultatului, este o soluție; care seamănă mai mult cu adăugarea care păstrează transportul în sine, are o suprasarcină constantă, astfel încât secvența de înmulțire Montgomery economisește timp, dar cea simplă nu. Din fericire, exponențiarea, care este de fapt o secvență de înmulțiri, este cea mai comună operație în criptografia cu cheie publică.

Detalii tehnice

Un dispozitiv de salvare a transportului constă din n sumatori completi , fiecare dintre acestea calculând o sumă de un bit și un bit de transport bazat în întregime pe biții corespunzători celor trei numere de intrare. Având în vedere trei numere de n biți a , b și c , se produce o sumă parțială ps și un sc de transport deplasat :

Suma totală poate fi apoi calculată:

  1. Prin deplasarea secvenței de transfer sc spre stânga cu un loc.
  2. Adăugând 0 la stânga secvenței de sumă parțială ( bitul cel mai semnificativ ) ps .
  3. Folosind un adunator carry-to-carry pentru a adăuga cele două împreună și a produce valoarea rezultată de n + 1 bit.

Când se adună trei sau mai multe numere, folosirea unui adunator de transportare-salvare urmată de un numărător consecutiv este mai rapidă decât utilizarea a două sumatoare de transport consecutive. Acest lucru se datorează faptului că sumatorul secvențial nu poate calcula suma biților fără a aștepta ca bitul de transport anterior să fie calculat și, prin urmare, are aceeași latență ca n sumatori completi. Un sumător de tip carry-save calculează toate cantitățile sale de ieșire în paralel și, prin urmare, are aceeași latență ca un singur sumator complet. Astfel, timpul total de calcul (în unități de întârziere de adunare completă) pentru un adunator carry-save plus un sumator carry-in-secvență este n + 1, în timp ce pentru doi sumatori consecutivi ar trebui să fie 2 n .

Vezi și

Note

  1. ↑ Earle, JG și colab . Brevetul SUA 3.340.388 „Latched Carry Save Adder Circuit for Multipliers” depus la 12 iulie 1965
  2. ↑ Earle, J. (martie, 1965), Latched Carry-Save Adder, IBM Technical Disclosure Bulletin Vol . 7 (10): 909–910  
  3. ↑ John von Neumann, Opere colectate.