Finora, per effettuare operazioni di somma, abbiamo analizzato una singola struttura, evidenziandone i pregi e i difetti: il ripple-carry adder. Come gi`a
annunciato, il problema di questa struttura `e il fatto che essa `e estremamente lenta: supponendo di dover realizzare un sommatore a 64 bit da 1 GHz, le porte dovrebbero avere una latenza inferiore ai 4 ps (provare a fare i conti per credere!), quando le migliori tecnologie, per costi elevatissimi, possono arrivare circa a 25 ps. Quello che bisogna dunque fare non `e cercare di miglio-rare la tecnologia delle porte logiche, bens`ı cercare modi per “rivoluzionare” il circuito, partendo sempre dal full adder, ma evitando di utilizzare metodi di questo tipo.
Un’idea `e gi`a stata proposta: l’introduzione di questi segnali Gi e Pi, per ciascun i-esimo full adder. Ci`o che si pu`o per ora fare `e cercare di migliorare, concettualmente parlando, il ripple-carry adder, introducendo una notazione basata sull’uso di questo nuovo concetto.
Come si pu`o dimostrare, osservando le tavole di verit`a, G e P possono essere ricavati utilizzando le seguenti espressioni:
G = A · B P = A ⊕ B
A partire da queste informazioni, proponiamo alcune idee che permettano di velocizzare l’attuale sistema.
4.3.1 Carry-bypass adder
Una prima idea potrebbe essere la seguente: avendo a disposizione il gi`a noto ripple-carry adder, avendo a disposizione i segnali di propagate, `e possibile determinare a priori un fatto: se tutti i Pi per ciascun blocco sono a 1, allora si pu`o dire che il circuito non dovr`a influenzare in alcun modo i carry; si pu`o dire per certo che Ci = Co, per l’intero circuito. Per questo motivo, si pu`o dire che far elaborare i carry sia tempo sprecato. Ci`o che si pu`o fare dunque `
e creare un percorso preferenziale, utilizzando un’idea di questo tipo:
Introducendo un multiplexer in cui per un ramo si introduce il classico ripple-carry adder, nell’altro un semplice corto circuito, e come segnale di pilotaggio si usa l’AND di tutti i segnali propagate Pi, se si ha Q
iPi = 1 si pu`o direttamente “bypassare” il ripple-carry, ottenendo immediatamente il carry finale.
4.3.2 Carry-select adder
Si propone a questo punto la seguente idea: per ogni coppia di bit da sommare si ricavano i due bit detti “generate” (G) e “propagate” (P ); il carry-select
adder calcola per ciascun bit da sommare i carry che dovrebbero esservi, mediante la semplice applicazione delle formule precedentemente introdotte, considerando due casistiche differenti, in parallelo: il fatto che il carry in ingresso al sommatore, Cin, valga “0” o “1”. Mediante un multiplexer, ai cui ingressi sono collegati i carry prodotti con le due possibilit`a, si selezionano, usando come segnale di ingresso Cin, i carry “corretti”, che verranno quindi utilizzati per produrre le somme parziali di bit, mediante i soli segnali P e Ci; sostituendo le espressioni precedentemente introdotte nell’espressione della somma di due bit, si pu`o ottenere:
Si = P ⊕ Ci
Costruendo blocchi combinatori in grado di riprodurre questa funzione logica e unendoli (secondo lo schema a blocchi fornito nell’esercitazione), si pu`o ottenere il sommatore basato sul meccanismo del carry-select.
L’idea sostanziale `e quella di “selezionare”: si producono dunque in paral-lelo due differenti uscite, che vengono poi unificate. Il blocco di produzione dei segnali di generate e propagate sono decisamente pi`u veloci rispetto al tradizionale full adder, dunque si riesce a ottenere, rispetto ai sommatori precedentemente presentati, un notevole miglioramento.
Per architetture di questo genere esistono alcune sotto-varianti, che ver-ranno ora presentate in modo quantomeno primordiale:
• Linear carry-select adder: utilizzando blocchetti “tutti uguali”, dotati degli stessi ritardi, si ottiene un buon risultato, quello “classicamente” aspettato.
• Square-root-select adder: mettendo blocchi con ritardi atti a sincroniz-zare tutte le uscite, con “numeri di bit crescenti”, si riesce ad ottenere un risultato ancora maggiore: se la velocit`a nella somma era prima lineare, ora diventa addirittura pari alla radice del numero di bit del sommatore.
4.3.3 Carry-lookahead adder
Ci`o che `e stato finora fatto sostanzialmente corrisponde in miglioramenti del ben noto ripple-carry adder. Non `e stata fatta tuttavia alcuna rivoluzio-ne concettuale rivoluzio-nell’idea della somma: si gerivoluzio-nera qualcosa passo passo, e in qualche modo si cerca di migliorare le prestazioni. Il carry-lookahead adder rappresenta un’architettura molto diversa e molto pi`u veloce rispetto alle pre-cedenti, poich`e sfrutta in modo molto pi`u potente le definizioni dei segnali “generate” e “propagate”.
L’idea fondamentale `e quella di realizzare una logica combinatoria la qua-le, per quanto complessa, possa determinare “a priori” tutti i carry in par-tenza, appena introdotto il numero. Sfruttando le definizioni di generate e propagate, nella fattispecie, si potrebbe pensare a qualcosa del genere:
ci+1= xi · yi+ xi· ci+ yi· ci = gi+ pi· ci Partendo da i = 0:
c1 = g0+ p0 · c0
Re-iterando, come si mostra in questo esempio, si pu`o ottenere: c2 = g1+ p1· c1 = g1+ p1· (g0+ p0· c0)
Allo stesso modo si potrebbe ricavare c3 e i seguenti allo stesso modo. Implementando una logica combinatoria di questo tipo si potrebbe im-mediatamente generare tutti i carry, imim-mediatamente. Il problema di questa architettura per`o risulta essere lampante: la complessit`a delle porte logiche da usare! Come si pu`o intuire, per un sommatore a 256 ingressi sarebbe necessario usare degli AND a 256 ingressi, o cose del genere; utilizzare porte con un fan-in molto elevato non `e positivo, dunque `e necessario limitarsi.
Un’alternativa potrebbe essere quella di utilizzare qualcosa del genere, con una struttura di tipo gerarchica: introducendo blocchi complessi, ma in numero limitato, si potrebbe ovviare questo problema almeno in parte, rendendo il tutto pi`u semplice e pi`u facilmente realizzabile.