符号なし除算(回復法)

[] [] []


除算をFPGAに実装するとき、自分でRTLを書くのは難しそうなのでIP生成ツールを使う人が多いと思うが、最近はVivadoHLSのような高位合成ツールがあるので、アルゴリズムを知っていると用途に合わせて除算器を作れる。そこで除算のアルゴリズムを合成可能なCコードで書いてみよう。ツールとしてVivadoHLSの固定小数点型テンプレートap_int.hを使うが、SystemCsystemc.hでも同様である。(→補足固定小数点型テンプレートの使い方)

まず、符号なし整数の除算を考える。一般の固定小数点でも、最下位ビットを合わせれば整数の除算と同じである

被除数a: 符号なし、整数部WAビット

除数d:  符号なし、整数部WDビット

q    符号なし、整数部WAビット、小数部FQビット (2WA/1=2WA だからqの整数部aと同じビット幅が必要)

剰余r = a-d*q  切捨て 0 r d*2-FQ  または丸め -d*2-FQ-1 r d*2-FQ-1

簡単な例としてWA=3,WD=2,FQ=0の場合で手計算してみると、次のように被除数を除数で引いてみて非負だったらq[i]=1として次は引いた値を使い、負だったらq[i]=0として次は引く前に戻せばよい。この方法は引き戻し法、回復法、Restoringとよばれる。

【回復法】符号なし/符号なし

例)a[2:0]=101 (5)  d[1:0]=11 (3)

         _______   10  手順

      11)  101.0   ( 1)  r={2'b00,a[2]}

       -) 11       ( 3)  d

         ---

         110       (-2)  t=r-d <0

q[2]=0    010      ( 2)  r={r[1:0],a[1]}

        -) 11      ( 3)  d

          ---

          111      (-1)  t=r-d <0

q[1]=0     101     ( 5)  r={r[1:0],a[0]}

         -) 11     ( 3)  d

           ---

           010     ( 2)  t=r-d >=0

q[0]=1      10.0   ( 4)  r={t[1:0],1'b0}

          -) 1.1   ( 3)  d

           --------

            00.1   ( 1)  t=r-d >=0

q[-1]=1

切捨の場合 q[2:0]=3'b001

丸めの場合 q[2:0]=q[2:0]+q[-1]=3'b010

 

 

 

←引き算はq[2](aMSB)から始める

 

 

if(t<0) q[i]=0 r={r[1:0],a[i-1]} 引く前の値に戻す

 else    q[i]=1 r={t[1:0],a[i-1]} 引いた値を使う

 

 

 

 

 

 

 

0<=r<d(切捨)にするにはq[0]で終わり

 

 

 

-0.5d<=r<0.5d(丸め)にするにはq[-1]まで求めて

  さらにq[2:0]=q[2:0]+q[-1]とすればよい

◇◇

このアルゴリズムをVivadoHLS合成可能なCコードで書くと次のようになる。ここで商qを小数点以下まで求めるためにa/d =q*2-FQ すなわちa*2FQ/d=qが整数になるようにしている。またa,dは整数型ap_uint< >としたが、固定小数点型ap_ufixed< >に置き換えてもそのまま使えるように、小数点の位置に依存しないa.range( )d.range( )で書いてある。

#include <ap_int.h>

/***************************************************************

 * division a/d = q + e

 *   input range: 0<=a , 0<d

 *   error range: 0<=e<2**(-FQ) (truncation)

 **************************************************************/

template <int WA,int WD,int FQ>

ap_ufixed<WA+FQ,WA> div_uint_trn

    (ap_uint<WA> a      // (i) dividend

    ,ap_uint<WD> d      // (i) divisor

    ) {

    ap_uint<WA+FQ> b = (ap_uint<WA+FQ>) a.range(WA-1,0) << FQ;

    ap_uint<WD+1> r;

    ap_int<WD+1>  t;

    ap_ufixed<WA+FQ,WA> q;      // (o) quotient

    for(int i=WA+FQ-1; i>=0; i--) {

        if(i==WA+FQ-1) {

            r = b[i];

        } else {

            r = ((q[i+1]? t.range(WD-1,0):r.range(WD-1,0)),b[i]);

        }

        t = r - d.range(WD-1,0);

        q[i] = !t[WD];

    }

    return q;

}

#include <ap_int.h>

/********************************************************************

 * division a/d = q + e

 *   input range: 0<=a , 0<d

 *   error range: -2**(-FQ-1)<=e<2**(-FQ-1) (rounding)

 *******************************************************************/

template <int WA,int WD,int FQ>

ap_ufixed<WA+FQ,WA> div_uint_rnd

    (ap_uint<WA> a      // (i) dividend

    ,ap_uint<WD> d      // (i) divisor

    ) {

    ap_uint<WA+FQ+1> b = (ap_uint<WA+FQ+1>) a.range(WA-1,0) << (FQ+1);

    ap_uint<WD+1> r;

    ap_int<WD+1>  t;

    ap_ufixed<WA+FQ,WA> q;      // (o) quotient

    for(int i=WA+FQ; i>=0; i--) {

        if(i==WA+FQ) {

            r = b[i];

        } else {

            r = ((q[i]? t.range(WD-1,0):r.range(WD-1,0)),b[i]);

        }

        t = r - d.range(WD-1,0);

        if(i==0) {

            q.range(WA+FQ-1,0) = q.range(WA+FQ-1,0) + !t[WD];

        } else {

            q[i-1] = !t[WD];

        }

    }

    return q;

}

このコードは次のテストベンチで検証してある。

int main(int argc, char *argv[]) {

    const int WA = 3;

    const int WD = 2;

    const int FQ = 0;

    ap_uint<WA> a;

    ap_uint<WD> d;

    ap_ufixed<WA+FQ,WA> q;

    double e;

   

    for(int j=1; j<pow(2,WD); j++) {

        for(int i=0; i<pow(2,WA); i++) {

            a = i;

            d = j;

            cout << "-- a=" << setw(3) << a << " d=" << setw(3) << d;

      /* 切捨ての場合 */

            q = div_uint_trn<WA,WD,FQ>(a,d);

            e = a.to_double() / d.to_double() - q.to_double();

            cout << " q_trn=" << setw(6) << q << " e=" << setw(10) << e;

            if(!(0<=e && e<pow(2,-FQ))) cout << " FAIL";

            /* 丸めの場合 */

            q = div_uint_rnd<WA,WD,FQ>(a,d);

            e = a.to_double() / d.to_double() - q.to_double();

            cout << " q_rnd=" << setw(6) << q << " e=" << setw(10) << e;

            if(!(-pow(2,-FQ-1)<=e && e<pow(2,-FQ-1))) cout << " FAIL";

            cout << endl;

        }

    }

    return 0;

}


[] [] []