delucagiovanni forum

Quale e' l'implementazione della MULU (1) piu' veloce in assoluto in termini di colpi di clock ? Il risultato ovviamente occupa, a rigore, 64bit e relativo segnale di overflow, ovvero attenzione che il risultato non ci sta in 32bit.


(1) MULU, moltiplicazione unsigned integer a 32bit
uint32_t source1;
uint32_t source2;
uint64_t result;

result = MULU(source1,source2);

Basta anche un solo colpo di clock con un moltiplicatore della dimensione corretta per eseguire una moltiplicazione senza segno.

Se utilizzi una FPGA commerciale conviene in genere utilizzare i blocchi appositi su silicio.

Ad esempio i Cyclone IV hanno moltiplicatori embedded 18x18 bit con frequenza massima di 287 MHz (Speed Grade C6). Una moltiplicazione 32x32 bit viene realizzata (automaticamente dal compilatore) componendo più moltiplicatori ed altra logica di contorno, quindi otterrai una frequenza leggermente inferiore (es. 250 MHz)

Esistono ad ogni modo diversi modi per implementare moltiplicatori con diversi trade-off, qui hai una panoramica Altera-centrica: http://www.altera.com/literature/an/an306.pdf

ma a prescindere dalle fpga, in termini di logica, che trucchi pratici usano, questo mi interessava.

legacy wrote:Quale e' l'implementazione della MULU (1) piu' veloce in assoluto in termini di colpi di clock ?

Se usi i moltiplicatori già presenti sulle fpga, potresti effettuare teoricamente la tua "MUL-U" in un colpo di clock...
e quindi la velocità sarebbe fortemente dipendente dal tipo di hw-fpga e dal clock che l'hw-sintetizzato può supportare.

E per la divisione unsigned DIVU e relativo modulo resto ?

@legacy,
ecco un esempio di "Utilization and Performance" di un LPM_divide nel caso di utilizzo di Stratix III / IV

e su ASIC come fanno ?
p.e. un stadio ALU32 di un core RISC che strategia impiega per MULU e DIVU ?

Hai provato a consultare qualche libro come "Synthesis of arithmetic circuits: FPGA, ASIC and Embedded Systems"?

L'ho solo sfogliato e descrive prima matematicamente e con l'utilizzo di pseudocodice alcuni algoritmi (es. Shift and Add Multiplication, Complement Multiplication, Booth Multiplication, etc..) dopodiché tratta della loro implementazione in VHDL.

L'implementazione su silicio dei moltiplicatori embedded delle FPGA non penso sia però nota, viene caratterizzata sotto alcuni punti di vista (es. prestazioni) sul datasheet ma non ho mai trovato dettagli di quali algoritmi ci siano sotto.

Lo possiedo già dal 2007 e lo conosco benissimo;
uno dei testi che consiglierei, ben strutturato e chiaro....

Leo, sai di altre edizioni più recenti?

Ciao Giovanni,

Alcuni autori del libro hanno anche scritto più recentemente (non gli ho ancora letti però):

- "Hardware Implementation of Finite-Field Arithmetic" (2009), un po' più specifico, sull'aritmetica dei campi finiti

- "Guide to FPGA Implementation of Arithmetic Functions" (2012), dal sommario sembra maggiormente approfondito dal punto di vista implementativo, in effetti probabilmente può essere visto come un'edizione più recente del libro

Ci sono poi approcci completamente diversi dalle ALU classiche, come processori logaritmici. Un progetto europeo che voglio segnalare: http://www.ncl.ac.uk/eee/elm/

So bene come funzionano gli algoritmi a micro codice, ma mangiano troppi cicli di clock, p.e. una MULU ed una DIVU si mangia 38 colpi di clock se approcciata in quel modo, mentre srotolando l'algoritmo della MULU32 in 32 stadi sommatori "furbi" e confidando che i tempi di propagazione siano + o - costanti si riesce far propagare il segnale in una rete a 32 strati in modo da infilare una MULI in ASIC al costo di 2 soli colpi di clock; il casotto pero' e' la DIVU: non conosco nessuno modo per srotolare l'algoritmo della divisione, quindi mi chiedo come accipicchia fanno macchine super scalari del 1997 (ovvero dotate di 2 ALU, tipicamente con constraints di 2 colpi di clock massime per mantenere gli stadi della pipeline sincroni) a fare divisioni intere in 2 colpi di clock. Misteri misteriosi.

@deluca
quanti cicli di clock di mangia la DIVU nella vostra implementazione Super-AVR8 ?

altrimenti, tocca giocarsela sporca, e giocarsela di "pipeline bubbling"