Floating Point Divider Szczegóły implementacji sprzętu

Question

Próbuję zaimplementować 32-bitowy dzielnik sprzętowy zmiennoprzecinkowy w sprzęcie i zastanawiam się, czy mogę uzyskać jakieś sugestie co do pewnych kompromisów między różnymi algorytmami?

Moja jednostka zmiennoprzecinkowa obsługuje obecnie mnożenie i dodawanie/odejmowanie, ale nie zamieniam go na zmiennoprzecinkową architekturę zmiennoprzecinkową (FMA), ponieważ jest to platforma osadzona, w której próbuję zminimalizować wykorzystanie obszaru .

Answer 1

Dawno, bardzo dawno temu i natknąć się to schludny i łatwe do wdrożenia pływaka/algorytm Division stałego punktu używany w wojskowej FPUs tego okresu czasu:

1. wejście musi być podpisane i przesunięte tak x < y i oba są w zakresie < 0.5 ; 1 >

   nie zapomnij zapisać różnicy przesunięć sh = shx - shy i oryginalnych znaków

2. znaleźć f (przez powtarzanie) tak y*f -> 1 .... po tym x*f -> x/y co jest wynikiem Division

3. przesunąć z powrotem przez shx*f i przywrócić wynik znak (sig=sigx*sigy)

   x*f można obliczyć z łatwością można to zrobić:

   z=1-y 
   (x*f)=(x/y)=x*(1+z)*(1+z^2)*(1+z^4)*(1+z^8)*(1+z^16)...(1+z^2n) 
   

   gdzie

   n = log2(num of fractional bits for fixed point, or mantisa bit size for floating point) 
   

Używam tego dzielnik w moich bignum arytmetyki, C++ realizacja wysokiego poziomu Division jest tak:

fixnum fixnum::operator/(const fixnum &x) // return = this/x 
    { 
    fixnum u,v,w; 
    int k=0,s; 
    s=sig*x.sig;    // compute result signum 
    u=this[0]; u.sig=+1; 
    v=x; v.sig=+1; 
    w.one(); 
    while (geq(v,w)) { v=v>>1; k++; } // shift input in range 
    w=w>>1; 
    while (geq(w,v)==1) { v=v<<1; k--; } 
    w.div(u,v);    // use divider block 
    w=w>>k;     // shift result back 
    w.sig=s;    // set signum 
    return w; 
    } 

ten został opracowany w czasie, gdy liczyć każdy tranzystor ... więc powinieneś być w stanie skompaktować go za pomocą jednostek + i *. mam nadzieję, że to pomoże....

[Edit1:] Oto moja pływające realizacja punkt

void arbnum::div(const arbnum &x,const arbnum &y,int acc) 
    { 
    // O(log(N)*(sqr+mul+inc)) ~ O(1.5*log(N)*(N^2)) 
    // x<y = < 0.5 ; 1 > 
    // x*f -> x/y , y*f -> 1 
    int i,nz; 
    arbnum c,z,q; 
    c=x; 
    z.one(); z.sub(z,y); // z=1-y 
    q=z; 
    q.inci(); 
    c.mul(c,q);    // (x/y)'=x*(1+z) 
    c._normalize(); 
    nz=z.nfbits(); 
    if (acc<=0) acc=(nz+c.nfbits())<<1; 
    for (i=int_log2(acc);i>=0;i--) 
     { 
//  z.mul(z,z); 
     z.sqr(z); 
     nz<<=1; if (nz>acc) nz=acc; z._normalize(nz); 
     q=z; 
     q.inci(); 
     c.mul(c,q);   // (x/y)'=x*(1+z)*(1+z^2)*(1+z^4)*(1+z^8)*(1+z^16)... 
     if (i) c._normalize(acc+nz); 
     } 
    c._normalize(acc); 
    overflow(); 
    c.sig=sig; 
    *this=c; 
    } 

numery to:

DWORD *dat; int siz,exp,sig,bits; 

dat[siz]: mantisa MSW = dat[0]
exp: podstawa 2 wykładnik MSB mantisa
sig: signum of mantisa
bits: stosowane bity mantisa do przyspieszania someoperations
a.inci(): a++
a.zero: a=0
a.one: a=1
a.geq(x,y) porównanie |x|,|y|, powroty 0 dla |x|<|y|, 1 > 2 == a.add(x,y): a=x+y
a.sub(x,y): a=x-y
a.mul(x,y): a=x*y
a.sqr(x): a=x*x
a.nfbits(): powrót Num używanych bitów ułamkowe liczby (00000100.00011100b -> 6)
a._normalize(): znormalizować ilość (MSB mantysie = 1)
a.overflow(): jeśli stwierdzi, że num ?.111111111111111111111111111111111111111111111b to zaokrąglenie do ?+1.0b
jest pożądana precyzja bitmastycznej precyzji (mój arbnum ma nielimitowane bity precyzji mantysy)