[Architettura degli elaboratori] CSA (carry-save addition)
Salve ragazzi.. ho visto questo forum veramente ricco di informazioni, e sono certo che qui risolverò il mio problema. Veniamo al dunque.. Ho un problema nel capire la tecnica per la moltiplicazione chiamata: "addizione con salvataggio del riporto o CSA (carry-save addition)". Non la capisco..quindi spero in voi xD. Grazie mille anticipatamente 
Risposte
Prendi la seguente somma in numeri binari
$111111111+$
$000000001=$
$-------------------$
$1000000000$
Come ben vedi $1+1=0 $ con il riporto di 1 che sommato a 1 da di nuovo 0 con il riporto di 1 etc.. Se ci sono N cifre vanno eseguiti N passaggi prima di sapere il risultato della somma.
Il trucco che qualcuno molto furbo si è studiato è stato questo.
"Perchè invece di sapere subito il risultato, non mi accontento di saperlo un po dopo?"
La somma precedente diventa
$111111111+$
$000000001=$
$-------------------$
$111111112$
Ora come ben sai ho bisogno di $log(N)$ "bits" per memorizzare "N" cifre diverse
00 =0
01 =1
10 =2 <--- 2!
11 =3
Quindi siccome per salvare un "riporto parziale" ci serve la cifra "2" abbiamo a disposizione anche il 3 gratuitamente.
Le vecchie CPU per sommare un numero binario lungo 32 cifre.. dovevano aspettare "32" unità di tempo. e questo accadeva ogni ciclo di clock.
Ora invece grazie al pipeline e al CSA le cose vanno molto meglio.
devo sommare
$111111111+$
$000010001=$
ottengo
$111121112$
al prossimo ciclo di clock devo sommare un altro numero? facile
Intanto muovo i riporti di una casella (2 a destra equivale a "riporto 1 a sinistra", va dimezzato!)
$111201120$
e poi sommo il nuovo numero ad es $100101101$
$111201120+$
$100101101=$
ottengo
$211302221$
al successivo ciclo di clock i riporti verranno mossi di un altra casella.
Ovvero se in una casella ho 3, vado ad aggiungere 1 a sinistra e mi rimane 1
Se in una casella ho 2 vado ad agiungere 1 a sinistra e mi rimane 1
Il problema "e se a sinistra ho 3?" non si pone perchè siccome il tutto viene eseguito in parallelo a sinistra non avrò mai 3. Avrò 0 o 1. (che ricevendo il riporto da destra diventeranno 1 o 2.. ma non 3! in pratica i "3" compaiono di tanto in tanto ma scompaiono subito)
C'è un notevole guadagno come vedi, ho eseguito 2 somme. Su una vecchia CPU avrei dovuto aspettare 64 unità di tempo (2 cicli di clock)
Invece ora ho impiegato solo 2 unità di tempo. Ovviamente però prima che i "riporti" vengano eliminati del tutto spostandoli a sinistra devo ancora aspettare LOG(N) cicli di clock.
1)Se devo sapere subito il risultato: poco male
ho aspettato 2+Log(32) unità di tempo => 7 unità di tempo/cicli di clock
2)Se il risultato non mi serve subito: ancora meglio! in quelle 5 unità di tempo avanzanti la CPU può fare "altro".
Su una vecchia CPU avresti invece impiegato sia nei casi 1 che nel caso 2 solamente 2 cicli di clock, con la differenza che in totale erano 64 unità di tempo. Hai migliorato la velocità di esecuzione del 900%(nel caso peggiore) semplicemente studiando un architettura diversa (ovvero senza andare a costruire circuiti più piccoli, ma semplicemente riorganizzandoli meglio il che è indipendente dai "nanometri" che hai a disposizione nella tua fabbrica).
Nel caso migliore invece hai migliorato del 3200%
Questo è anche il motivo per cui quando un processore esegue moltiplicazione tra 2 numeri può anche effettuare una somma "gratuitamente" (MAD operation: multiply and add).
Visto che i "3" persistono solo per un ciclo di clock, tu puoi continuare a sommare numeri anche senza conoscere il risultato poichè puoi sommare quando non ci sono "3", ma i 3 scompaiono subito allora puoi continuare a sommare (dovresti aver notato che un integer overflow viene ritardato in questo modo ponendo potenzialmente un problema)
$111111111+$
$000000001=$
$-------------------$
$1000000000$
Come ben vedi $1+1=0 $ con il riporto di 1 che sommato a 1 da di nuovo 0 con il riporto di 1 etc.. Se ci sono N cifre vanno eseguiti N passaggi prima di sapere il risultato della somma.
Il trucco che qualcuno molto furbo si è studiato è stato questo.
"Perchè invece di sapere subito il risultato, non mi accontento di saperlo un po dopo?"
La somma precedente diventa
$111111111+$
$000000001=$
$-------------------$
$111111112$
Ora come ben sai ho bisogno di $log(N)$ "bits" per memorizzare "N" cifre diverse
00 =0
01 =1
10 =2 <--- 2!
11 =3
Quindi siccome per salvare un "riporto parziale" ci serve la cifra "2" abbiamo a disposizione anche il 3 gratuitamente.
Le vecchie CPU per sommare un numero binario lungo 32 cifre.. dovevano aspettare "32" unità di tempo. e questo accadeva ogni ciclo di clock.
Ora invece grazie al pipeline e al CSA le cose vanno molto meglio.
devo sommare
$111111111+$
$000010001=$
ottengo
$111121112$
al prossimo ciclo di clock devo sommare un altro numero? facile
Intanto muovo i riporti di una casella (2 a destra equivale a "riporto 1 a sinistra", va dimezzato!)
$111201120$
e poi sommo il nuovo numero ad es $100101101$
$111201120+$
$100101101=$
ottengo
$211302221$
al successivo ciclo di clock i riporti verranno mossi di un altra casella.
Ovvero se in una casella ho 3, vado ad aggiungere 1 a sinistra e mi rimane 1
Se in una casella ho 2 vado ad agiungere 1 a sinistra e mi rimane 1
Il problema "e se a sinistra ho 3?" non si pone perchè siccome il tutto viene eseguito in parallelo a sinistra non avrò mai 3. Avrò 0 o 1. (che ricevendo il riporto da destra diventeranno 1 o 2.. ma non 3! in pratica i "3" compaiono di tanto in tanto ma scompaiono subito)
C'è un notevole guadagno come vedi, ho eseguito 2 somme. Su una vecchia CPU avrei dovuto aspettare 64 unità di tempo (2 cicli di clock)
Invece ora ho impiegato solo 2 unità di tempo. Ovviamente però prima che i "riporti" vengano eliminati del tutto spostandoli a sinistra devo ancora aspettare LOG(N) cicli di clock.
1)Se devo sapere subito il risultato: poco male
ho aspettato 2+Log(32) unità di tempo => 7 unità di tempo/cicli di clock
2)Se il risultato non mi serve subito: ancora meglio! in quelle 5 unità di tempo avanzanti la CPU può fare "altro".
Su una vecchia CPU avresti invece impiegato sia nei casi 1 che nel caso 2 solamente 2 cicli di clock, con la differenza che in totale erano 64 unità di tempo. Hai migliorato la velocità di esecuzione del 900%(nel caso peggiore) semplicemente studiando un architettura diversa (ovvero senza andare a costruire circuiti più piccoli, ma semplicemente riorganizzandoli meglio il che è indipendente dai "nanometri" che hai a disposizione nella tua fabbrica).
Nel caso migliore invece hai migliorato del 3200%
Questo è anche il motivo per cui quando un processore esegue moltiplicazione tra 2 numeri può anche effettuare una somma "gratuitamente" (MAD operation: multiply and add).
Visto che i "3" persistono solo per un ciclo di clock, tu puoi continuare a sommare numeri anche senza conoscere il risultato poichè puoi sommare quando non ci sono "3", ma i 3 scompaiono subito allora puoi continuare a sommare (dovresti aver notato che un integer overflow viene ritardato in questo modo ponendo potenzialmente un problema)
Ora come ben sai ho bisogno di log(N) "bits" per memorizzare "N" cifre diverse
00 =0
01 =1
10 =2 <--- 2! //che cosa significa? è un fattoriale?
11 =3
Quindi siccome per salvare un "riporto parziale" ci serve la cifra "2" abbiamo a disposizione anche il 3 gratuitamente.
Le vecchie CPU per sommare un numero binario lungo 32 cifre.. dovevano aspettare "32" unità di tempo. e questo accadeva ogni ciclo di clock.
Ora invece grazie al pipeline e al CSA le cose vanno molto meglio.
devo sommare
111111111+
000010001=
ottengo
111121112
al prossimo ciclo di clock devo sommare un altro numero? facile
Intanto muovo i riporti di una casella (2 a destra equivale a "riporto 1 a sinistra", va dimezzato!)
111201120 //non capisco come siamo passati dal binario precedente a questo, in che modo ti "muovi"?
e poi sommo il nuovo numero ad es 100101101
111201120+
100101101=
ottengo
211302221
al successivo ciclo di clock i riporti verranno mossi di un altra casella.
Ovvero se in una casella ho 3, vado ad aggiungere 1 a sinistra e mi rimane 1
Se in una casella ho 2 vado ad agiungere 1 a sinistra e mi rimane 1 // dove sta la differenza??
Il problema "e se a sinistra ho 3?" non si pone perchè siccome il tutto viene eseguito in parallelo a sinistra non avrò mai 3. Avrò 0 o 1. (che ricevendo il riporto da destra diventeranno 1 o 2.. ma non 3! in pratica i "3" compaiono di tanto in tanto ma scompaiono subito)
Innanzitutto grazie per la tua risposta chiara ed efficace, ho capito a differenza di quanto scritto nel mio libro di testo, come più o meno funziona e quali utilità apporta. Comunque sia..come già detto ho alcuni dubbi che ho segnato in rosso nel testo da te citato qui su. Se fossi così gentile da spiegarmelo..
grazie mille!!!
allora "dove sta la differenza":
li ho sbagliato a scrivere
Se in una casella ho 2 vado ad aggiungere 1 a sinistra e mi rimane 0
<--- 2! non è fattoriale. era per evidenziare il due (forse era meglio il grassetto).
Siamo ancora in base due in un certo senso
$101 = 1*2^2 + 0*2^1 + 1*2^1 $
$202 = 2*2^2 + 0*2^1 + 2*2^1 = 1010 = 1*2^3 + 0*2^2 + 1*2^1 + 0*2^0 $
$3 = 3*2^0 = 21 = 2*2^1 + 1*2^0 = 101$
Se riesci a capire questo sei posto. E' la parte più importante
come mi muovo:
semplice voglio ottenere 1 o 0 in tutte le caselle.
se tu hai
$n=0023110013$
puoi "immaginare di sdoppiarlo" in
$n=2*q+r$
$q=0011000001$
$r=0001110011$
ora ricalcolo n (che è sempre uguale ma scritto in modo diverso)
$2*q=0110000010$ (nota anche che $2*q =0022000002$ anche se però scritto coi "2" non ci serve a molto ora)
$0110000010+$
$0001110011=$
$---------------$
$0101110021$
ripetendo trovi
$0101110101$
li ho sbagliato a scrivere
Se in una casella ho 2 vado ad aggiungere 1 a sinistra e mi rimane 0
<--- 2! non è fattoriale. era per evidenziare il due (forse era meglio il grassetto).
Siamo ancora in base due in un certo senso
$101 = 1*2^2 + 0*2^1 + 1*2^1 $
$202 = 2*2^2 + 0*2^1 + 2*2^1 = 1010 = 1*2^3 + 0*2^2 + 1*2^1 + 0*2^0 $
$3 = 3*2^0 = 21 = 2*2^1 + 1*2^0 = 101$
Se riesci a capire questo sei posto. E' la parte più importante
come mi muovo:
semplice voglio ottenere 1 o 0 in tutte le caselle.
se tu hai
$n=0023110013$
puoi "immaginare di sdoppiarlo" in
$n=2*q+r$
$q=0011000001$
$r=0001110011$
ora ricalcolo n (che è sempre uguale ma scritto in modo diverso)
$2*q=0110000010$ (nota anche che $2*q =0022000002$ anche se però scritto coi "2" non ci serve a molto ora)
$0110000010+$
$0001110011=$
$---------------$
$0101110021$
ripetendo trovi
$0101110101$
"Vitalluni":
allora "dove sta la differenza":
Siamo ancora in base due in un certo senso
//SCUSAMI, ma non riesco a capire il ragionamento sottostante xD
$ 101 = 1*2^2 + 0*2^1 + 1*2^1 $
$ 202 = 2*2^2 + 0*2^1 + 2*2^1 = 1010 = 1*2^3 + 0*2^2 + 1*2^1 + 0*2^0 $
$ 3 = 3*2^0 = 21 = 2*2^1 + 1*2^0 = 101 $
//FINE
Se riesci a capire questo sei posto. E' la parte più importante
come mi muovo:
semplice voglio ottenere 1 o 0 in tutte le caselle.
se tu hai
$ n=0023110013 $
puoi "immaginare di sdoppiarlo" in
$ n=2*q+r $
$ q=0011000001 $
$ r=0001110011 $
ora ricalcolo n (che è sempre uguale ma scritto in modo diverso)
$ 2*q=0110000010 $ (nota anche che $ 2*q =0022000002 $ anche se però scritto coi "2" non ci serve a molto ora)
$ 0110000010+ $
$ 0001110011= $
$ --------------- $
$ 0101110021 $//perché viene questa risultato? è una somma normale tra binari, o segui le regole di sopra? cioè,
00 = 0
01 = 1
10 = 2
11 = 3
grazie per la pazienza!!!
Diciamo che la notazione binaria $101$
rappresenta concettualmente il seguente fatto:
hai 1 pallina che vale 4
hai 0 palline che valgono 2
hai 1 pallina che vale 1
Nessuno ti vieta di avere 2 palline che valgono 2. ( a patto che tu abbia una scatola abbastanza grande)
2 palline che valgono 2
1 pallina che vale 1
che puoi scrivere $21=101$
Il trucco sta nel fatto che usare le palline in questo modo è molto comodo.
Ad ogni "iterazione" puoi scambiare 2 palline che valgono N con 1 pallina che vale 2N. Quando finite le iterazioni hai soltanto "1 pallina in ogni posizione" allora puoi "trascrivere" il numero in binario.
Fino a quando non "trascrivo" il numero uso sempre le regole di sopra (ovvero ammetto di avere anche "2" o "3" come possibili valori). I Registers delle CPU ammettono fino a 3 palline per ogni posizione. Ovviamente poi però quando trascrivono il numero nella memoria RAM ( o anche nella cache) non possono più tenersi 3 palline, ma al massimo 1. Quindi devono scambiare palline con palline che valgono "di più" fino ad ottenere una sola pallina per ogni posizione.
rappresenta concettualmente il seguente fatto:
hai 1 pallina che vale 4
hai 0 palline che valgono 2
hai 1 pallina che vale 1
Nessuno ti vieta di avere 2 palline che valgono 2. ( a patto che tu abbia una scatola abbastanza grande)
2 palline che valgono 2
1 pallina che vale 1
che puoi scrivere $21=101$
Il trucco sta nel fatto che usare le palline in questo modo è molto comodo.
Ad ogni "iterazione" puoi scambiare 2 palline che valgono N con 1 pallina che vale 2N. Quando finite le iterazioni hai soltanto "1 pallina in ogni posizione" allora puoi "trascrivere" il numero in binario.
Fino a quando non "trascrivo" il numero uso sempre le regole di sopra (ovvero ammetto di avere anche "2" o "3" come possibili valori). I Registers delle CPU ammettono fino a 3 palline per ogni posizione. Ovviamente poi però quando trascrivono il numero nella memoria RAM ( o anche nella cache) non possono più tenersi 3 palline, ma al massimo 1. Quindi devono scambiare palline con palline che valgono "di più" fino ad ottenere una sola pallina per ogni posizione.
Ciao Vitalluni scusami ma per motivi di studio e di lavoro non ho potuto più risponderti. Per quanto riguarda la questione in oggetto..ho riletto ciò che hai scritto ora e posso dire che sono più confuso di prima xD..(lo ero anche allora) il problema è il mio..per tanto ti chiedo se gentilmente potresti fare un riepilogo in un post solamente te ne sarei davvero grato, poiché ancora tutt'ora ho problemi a capire questa tecnica. INFINITE GRAZIE ANTICIPATAMENTE!
forse è colpa della base binaria. Posso capirti è davvero una scocciatura farsi i conti in base due (anche se con 10 dita permetterebbe di contare fino a 1024, ma chi è che lo fa XD). Comunque, io ad esempio devo ancora comprendere la somma e la moltiplicazione se ti consola (cioè so eseguire l'algoritmo di somma a memoria, ma non ho la più pallida idea del perchè funzioni.)
Spero di non confonderti ulteriormente. Magari in base Dieci si capisce meglio
$9999+$
$9999=$
,
be intanto posso separarmi le cifre per comodità
$9.9.9.9+$
$9.9.9.9=$
$18.18.18.18$
,
Il risultato così è giusto. Nel senso che se tu guardi quanto valgono sarebbe
,
$18^1 + 18^10 + 18^100 + 18^1000 = 19998$
,
di fatto potevamo scrivere
,
$(9^1 + 9^10 + 9^100 + 9^1000) +$
$(9^1 + 9^10 + 9^100 + 9^1000)$
,
Per le proprietà delle potenze puoi sommare membro a membro i "tizi" (non saprei come chiamarli.. fattori?) con esponente uguale.
$9^1+9^1 = 18^1$
,
$9^10+9^10 = 18^10$
,
$9^100+9^100 = 18^100$
,
$9^1000+9^1000 = 18^1000$
,
Ora però 18.18.18.18 come fa a diventare un numero "normale"?
Semplice, facciamo degli scambi (come se stessimo commerciando, sempre sfruttando le proprietà delle potenze che grazie al cielo qualcuno ha dimostrato!)
,
$18^100 = 10^100 + 8^100 = 1^1000 + 8^100$
,
in pratica:
$18.18.18.18 =$
,
$8.8.8.8+$
$10.10.10.10 =$
,
$8.8.8.8+$
$1.1.1.1.0=$
,
$1. 8+1 . 8+1 . 8+1 . 8 =$
$1.9.9.9.8$
... Forse mi hai fatto capire come funziona la somma O_O.
Spero di non confonderti ulteriormente. Magari in base Dieci si capisce meglio
$9999+$
$9999=$
,
be intanto posso separarmi le cifre per comodità
$9.9.9.9+$
$9.9.9.9=$
$18.18.18.18$
,
Il risultato così è giusto. Nel senso che se tu guardi quanto valgono sarebbe
,
$18^1 + 18^10 + 18^100 + 18^1000 = 19998$
,
di fatto potevamo scrivere
,
$(9^1 + 9^10 + 9^100 + 9^1000) +$
$(9^1 + 9^10 + 9^100 + 9^1000)$
,
Per le proprietà delle potenze puoi sommare membro a membro i "tizi" (non saprei come chiamarli.. fattori?) con esponente uguale.
$9^1+9^1 = 18^1$
,
$9^10+9^10 = 18^10$
,
$9^100+9^100 = 18^100$
,
$9^1000+9^1000 = 18^1000$
,
Ora però 18.18.18.18 come fa a diventare un numero "normale"?
Semplice, facciamo degli scambi (come se stessimo commerciando, sempre sfruttando le proprietà delle potenze che grazie al cielo qualcuno ha dimostrato!)
,
$18^100 = 10^100 + 8^100 = 1^1000 + 8^100$
,
in pratica:
$18.18.18.18 =$
,
$8.8.8.8+$
$10.10.10.10 =$
,
$8.8.8.8+$
$1.1.1.1.0=$
,
$1. 8+1 . 8+1 . 8+1 . 8 =$
$1.9.9.9.8$
... Forse mi hai fatto capire come funziona la somma O_O.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo