integer division, si fa in fretta a dire divido

[legacy]

per lavoro, m'e' toccato implementare una alu a 128bit
a fatica sono riuscito a completare una mul{u,s} che impiega *solo* 3 colpi di clock
ma la integer division ... guardate un po' qui sopra, e fate conto che sono solo 8 bit

per 32 bit impiega 35 colpi di clock
(almeno non sbaglia i calcoli (cosi' sembra))

dovendo risolvere il problema Q=N/D

metodi + furbi mi sa che passano dalla stima di (1/D)
p.e. tramite Newton-Raphson (per n>32bit e' l'ideale)
che costa il dover implementare logica fractional

una volta trovato (1/D): fractional number
va moltiplicato per N~: fractional number of N

dopo di che va convertito il risultato (1/D)*(N~) in integer (1)
e finalmente si ha Q, il risultato !

direi che tutta questa faccenda occupa aree, risorse, e sopratutto ...
... aggiunge complexity al design

insomma, si fa in fretta dire "divido, cosa vuoi che sia"
e' che la divisione-intera-veloce e' una faccenda tosta

(1) le conversioni integer da/a fractional, se fatte in modo furbo, sono tutte shift{R,L}

[Leonardo]

Un'istruzione IDIV r32 ha una latenza di:
- 41 cicli su un AMD K7
- 50 cicli su un Pentium 4 Netburst
- 29 cicli su un Intel i7 Haswell

se sei a 35 colpi di clock con 32 bit non sei messo così male..
Poi chiaramente dipende dalla fmax che hai raggiunto

Io sinceramente uso l' LPM_DIVIDE che permette di scegliere la lunghezza della pipeline in base all'fmax che si vuole raggiungere anche se il trucco.. è sfruttare il più possibile le proprietà matematiche delle operazioni che si vogliono svolgere per semplificare il calcolo. In molti caso le divisioni possono diventare moltiplicazioni (lo fanno in automatico i compilatori odierni) o shift, ma quest'ultima ottimizzazione è abbastanza banale e funziona in pochi casi.

[legacy]

35 colpi di clock con 32 bit

e se hai 128 bit ... sono 142 colpi di clock X_______________X

a parte che non e' vero, gia' sui RISC di seconda generazione si arrivava allo stesso risultato che ho raggiunto, per altro con la forma + semplice di algoritmica di divisione, e i primi cray implementavano proprio l'idea qui sopra, (1/D)*N

Io sinceramente uso l' LPM_DIVIDE che permette di scegliere la lunghezza della pipeline in base all'fmax che si vuole raggiungere

devo implementare a manina, niente trucchi e magheggi coi tool, altrimenti non mi pagano