integer division, si fa in fretta a dire divido

Sezione dedicata al linguaggio di descrizione hardware per logiche programmabili

integer division, si fa in fretta a dire divido

Postby legacy » 26 Aug 2016, 17:30

Image

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 :lol: :lol: :lol:
(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}
legacy
 
Posts: 862
Joined: 12 Mar 2012, 11:30

Re: integer division, si fa in fretta a dire divido

Postby Leonardo » 26 Aug 2016, 21:48

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 :twisted:

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.
Il mio blog di elettronica: http://electro-logic.blogspot.it
User avatar
Leonardo
 
Posts: 502
Joined: 29 May 2013, 22:31
Location: Parma

Re: integer division, si fa in fretta a dire divido

Postby legacy » 27 Aug 2016, 01:24

Leonardo wrote: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

Leonardo wrote: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
legacy
 
Posts: 862
Joined: 12 Mar 2012, 11:30


Return to VHDL x FPGA

Who is online

Users browsing this forum: No registered users and 14 guests

cron