Kuljeta tallennuslisäädintä

Siirtotallennussummain [ 1] [2] on eräänlainen digitaalinen summain , jota käytetään tietokoneen mikroarkkitehtuurissa kolmen tai useamman n-bittisen luvun summan laskemiseen binäärilukujärjestelmässä . Se eroaa muista digitaalisista summaimista siinä, että sen lähdöt ovat kaksi samankokoista numeroa kuin tulot, joista toinen on bittien osasumma ja toinen siirtobittien sarja .

Motivaatio

Harkitse summaa:

12345678 + 87654322 = 100000000

Aritmetiikkaa käyttäen oikealta vasemmalle: "8+2=0, kanna 1", "7+2+1=0, kanna 1", "6+3+1=0, kanna 1" ja niin edelleen loppuun asti summasta. Tiedämme kuitenkin, että ennen kuin tuloksen viimeinen numero on saatu, emme tiedä vasemmalla olevaa ensimmäistä numeroa ennen kuin käymme jokaisen luvun läpi laskennassa ja siirrämme jokaisesta numerosta sen vasemmalle puolelle. Näin ollen kahden n-bittisen luvun lisääminen vie aikaa n:ään verrannollisesti, vaikka käyttämämme kone pystyy tekemään monta laskutoimitusta samanaikaisesti.

Elektronisesti bitteillä (binäärinumeroilla) tämä tarkoittaa, että vaikka meillä olisi käytössämme n yksibittistä summainta, meidän on silti käytettävä aikaa suhteessa n:ään, jotta siirto etenee luvun yhdestä päästä numeroon. muu. Kun teemme tätä

1. Emme tiedä lisäyksen tulosta. 2. Emme tiedä, onko summauksen tulos pienempi vai suurempi kuin annettu luku (emme esimerkiksi tiedä, onko se positiivinen vai negatiivinen).

Siirtosumma voi vähentää latenssia. Periaatteessa viivettä voidaan pienentää niin, että se on verrannollinen log n :ään , mutta suurilla luvuilla tämä ei enää pidä paikkaansa, koska jopa nopeutettua siirtoa käytettäessä signaalin kulkema matka sirua pitkin kasvaa suhteessa n:ään ja etenemisviive kasvaa tässä samassa asenteessa. Kun saamme julkisen avaimen salausjärjestelmissä vaadittavat 512-2048-bittiset numerot , edelleenlähetys ei enää auta.

Peruskonsepti

Ajatus siirron ratkaisemisen lykkäämisestä loppuun tai siirtojen säilyttämisestä kuuluu John von Neumannille . [3]

Tässä on esimerkki binäärilisäyksestä:

10111010101011011111000000001101 + 11011110101011011011111011101111.

Säilyttävä aritmetiikka toimii jättämällä binäärimerkinnät, kun se työskentelee edelleen kantassa 2. Se laskee summan numero numerolta, kuten

10111010101011011111000000001101 + 11011110101011011011111011101111 = 21122120202022022122111011102212.

Merkintä on epätavallinen, mutta tulos pysyy yksiselitteisenä. Lisäksi kun on annettu n summainta (tässä n = 32 täyttä summainta), tulos voidaan laskea sen jälkeen, kun tulot on siirretty yhden summaimen läpi (yhdessä generaattorisyklissä), koska tuloksen jokainen numero on riippumaton muista.

Jos kahden luvun lisäämiseen ja tuloksen laskemiseen tarvitaan summain, siirtosäilytys ei sovellu, koska tulos pysyy muunnettavissa takaisin binäärimuotoon, mikä tarkoittaa, että kantajat eivät ole vielä edenneet oikealta vasemmalle. Mutta suurten kokonaislukujen aritmetiikassa yhteenlasku on erittäin harvinainen operaatio, ja siirtoa säilyttäviä summaimia käytetään yleisesti keräämään osittaisia ​​summia kertoimeen.

Kanna tallennusasemia

Oletetaan, että meillä on kaksi bittiä muistia kutakin tuloksen numeroa kohden, niin voimme käyttää redundanttia binääriesitystä tallentamalla arvot 0, 1, 2 tai 3 jokaiseen numerokohtaan. Tämä johtuu siitä, että useampaa kuin yhden binääriluvun voidaan lisätä siirtoa säilyttävään tulokseemme ilman, että muistikapasiteettimme täyttyy: mutta mitä sitten?

Avain ymmärtämiseen on, että lisäämme jokaisen osittaisen lisäyksen aikana kolme bittiä:

Toisin sanoen otamme kantonumeron oikealta paikalta ja kannamme siirtonumeron vasemmalle, aivan kuten perinteisessä summauksessa; mutta siirtonumero, jonka siirrämme vasemmalle, on tulos edellisestä laskelmasta, ei nykyisestä. Jokaisella generaattorin jaksolla kuljettimet liikkuvat vain yhden askeleen eteenpäin, eivät n askelta, kuten perinteisessä summauksessa.

Koska signaalit eivät kulje niin pitkälle, generaattori voi tikittää nopeammin.

Laskennan lopussa on edelleen tarve muuntaa tulos binääriksi, mikä tarkoittaa itse asiassa vain sitä, että siirtojen sallitaan kulkea luvun läpi aivan kuten perinteisessä summaimessa. Mutta jos teimme 512 lisäystä 512-bittisen kertolaskuprosessin aikana, tämän lopullisen muunnoksen suuri hinta jaetaan itse asiassa kaikilla 512 lisäyksellä, joten jokainen lisäys sisältää vain 1/512 lopullisen "normaalin" suuresta hinnasta. lisäys.

Haitat

Jokaisessa lisäysvaiheessa siirtosäilönnällä,

  1. Tiedämme lisäyksen tuloksen heti.
  2. Emme vieläkään tiedä , onko summauksen tulos suurempi vai pienempi kuin annettu luku (emme esimerkiksi tiedä, onko se positiivinen vai negatiivinen).

Tämä viimeinen kohta on haittapuoli käytettäessä siirtoa säilyttäviä summaimia modulo-kertolaskujen suorittamiseen (jakoa seuraavien kertolaskujen säilyttäminen, vain jäännös). Jos emme voi tietää, onko välitulos suurempi vai pienempi kuin moduuli, kuinka voimme tietää, vähennetäänkö moduulit vai ei?

Montgomeryn kertolasku , joka riippuu tuloksen oikeanpuoleisesta numerosta, on yksi ratkaisu; joka on enemmän kuin itse siirto-säilytyslisäys, sillä on jatkuva yläraja, joten Montgomeryn kertolasku säästää aikaa, mutta yksittäinen ei. Onneksi eksponentiointi, joka on itse asiassa kertolaskujen sarja, on yleisin operaatio julkisen avaimen salauksessa.

Tekniset tiedot

Kuljetussäästölaite koostuu n : stä täydestä summaimesta , joista kukin laskee yhden bitin summan ja siirtobitin perustuen kokonaan kolmen syötenumeron vastaaviin bitteihin. Kun annetaan kolme n - bittistä lukua a , b ja c , se tuottaa osittaissumman ps ja siirretyn kantoarvon sc :

Kokonaissumma voidaan sitten laskea:

  1. Siirtämällä siirtosekvenssiä sc vasemmalle yhden paikan verran.
  2. Lisäämällä 0 ( merkittävimmän bitin ) osasummasekvenssin ps vasemmalle puolelle .
  3. Lisäämällä nämä kaksi yhteen ja tuottamaan tuloksena oleva n + 1 - bittinen summa.

Kun kolme tai useampia numeroita lasketaan yhteen, siirtotallennussummaimen ja peräkkäisen summaimen käyttäminen on nopeampaa kuin kahden peräkkäisen siirtosummaimen käyttäminen. Tämä johtuu siitä, että peräkkäinen summain ei voi laskea bittien summaa odottamatta edellisen siirtobitin laskemista, ja siten sillä on sama latenssi kuin n :llä täydellä summaimella. Siirtotallennussummain laskee kaikki lähtömääränsä rinnakkain, ja siten sillä on sama latenssi kuin yhdellä täyssummaimella. Näin ollen kokonaislaskenta-aika (täyden lisäysviiveen yksiköissä) siirtotallennussummaimelle plus siirtosekvenssin summaimelle on n + 1, kun taas kahdelle peräkkäiselle summaimelle sen pitäisi olla 2 n .

Katso myös

Muistiinpanot

  1. ↑ Earle, JG et ai. US-patentti 3 340 388 "Latched Carry Save Adder Circuit for Multipliers", jätetty 12. heinäkuuta 1965
  2. ↑ Earle, J. (maaliskuu 1965), Latched Carry-Save Adder, IBM Technical Disclosure Bulletin Vol . 7 (10): 909–910  
  3. ↑ John von Neumann, Kerätyt teokset.