pipelined divider

would like to know which is the best algorithm to 
make a pipelined divider in hardware. newton raphson,
goldshmit .. srt(is it possible?)
if i have space as much as to have as much as 5 radix-4
srt dividers in a xilinx v2 fpga..

thanks in advance--

"ykagarwal" <yog_aga@yahoo.co.in> wrote in message
news:4d05e2c6.0309090919.261490a1@posting.google.com...
> would like to know which is the best algorithm to
> make a pipelined divider in hardware. newton raphson,
> goldshmit .. srt(is it possible?)
> if i have space as much as to have as much as 5 radix-4
> srt dividers in a xilinx v2 fpga..

Pipelined dividers have been used on machines like the IBM 360/91 and the
Cray-1, and are well described in pipelined computer architecture books for
many years after those machines were built.

Though in both cases they are used for floating point, where the
requirements are different.  The 360/91, for example, rounds the low bit
instead of truncating as the architecture specifies, and would be usual in
fixed point.  I don't know how hard that would be to change.

-- glen

"Glen Herrmannsfeldt" <gah@ugcs.caltech.edu> wrote in message news:<F7q7b.408266$uu5.74285@sccrnsc04>...
> "ykagarwal" <yog_aga@yahoo.co.in> wrote in message
> news:4d05e2c6.0309090919.261490a1@posting.google.com...
> > would like to know which is the best algorithm to
> > make a pipelined divider in hardware. newton raphson,
> > goldshmit .. srt(is it possible?)
> > if i have space as much as to have as much as 5 radix-4
> > srt dividers in a xilinx v2 fpga..
> 
> Pipelined dividers have been used on machines like the IBM 360/91 and the
> Cray-1, and are well described in pipelined computer architecture books for
> many years after those machines were built.
> 
> Though in both cases they are used for floating point, where the
> requirements are different.  The 360/91, for example, rounds the low bit
> instead of truncating as the architecture specifies, and would be usual in
> fixed point.  I don't know how hard that would be to change.
> 
> -- glen

well my requirement is too for double precision .. would u like to
suggest me a pipelined
comp arch book for this purpose.. anyway what is the best way, that's
what i want to explore first.

Xilinx coregen divider core doesn't offer that much width in its
pipelined divider .. don't know why
may be xilinx gurus can justify .. anybody knows which algorithm they
are using ?

regards
--yka

Look up online arithmetic.

Steve

>
> well my requirement is too for double precision .. would u like to
> suggest me a pipelined
> comp arch book for this purpose.. anyway what is the best way, that's
> what i want to explore first.
>
> Xilinx coregen divider core doesn't offer that much width in its
> pipelined divider .. don't know why
> may be xilinx gurus can justify .. anybody knows which algorithm they
> are using ?
>
> regards
> --yka

"ykagarwal" <yog_aga@yahoo.co.in> wrote in message
news:4d05e2c6.0309092246.2ead33f0@posting.google.com...

(snip regarding pipelined divider)

> well my requirement is too for double precision .. would u like to
> suggest me a pipelined
> comp arch book for this purpose.. anyway what is the best way, that's
> what i want to explore first.

The one I have here is "The Architecture of Pipelined Computers" by Kogge.

> Xilinx coregen divider core doesn't offer that much width in its
> pipelined divider .. don't know why
> may be xilinx gurus can justify .. anybody knows which algorithm they
> are using ?

I don't know that, either.  It might be because they didn't imagine anyone
wanting to put something like that into an FPGA.  They are likely pretty
big, but in some cases it might be worth the size.

-- glen

"Glen Herrmannsfeldt" <gah@ugcs.caltech.edu> wrote in message news:<HHM7b.410438$Ho3.64641@sccrnsc03>...
> "ykagarwal" <yog_aga@yahoo.co.in> wrote in message
> news:4d05e2c6.0309092246.2ead33f0@posting.google.com...
> 
> (snip regarding pipelined divider)
> 
> > well my requirement is too for double precision .. would u like to
> > suggest me a pipelined
> > comp arch book for this purpose.. anyway what is the best way, that's
> > what i want to explore first.
> 
> The one I have here is "The Architecture of Pipelined Computers" by Kogge.
> 
> > Xilinx coregen divider core doesn't offer that much width in its
> > pipelined divider .. don't know why
> > may be xilinx gurus can justify .. anybody knows which algorithm they
> > are using ?
> 
> I don't know that, either.  It might be because they didn't imagine anyone
> wanting to put something like that into an FPGA.  They are likely pretty
> big, but in some cases it might be worth the size.
> 
> -- glen

fine, thanks i cud find the book (bit old edition probably)
here but there is no detail abt pipelined divider as such ..
anyway if somebody comes across the thing may suggest.
and xilinx probably shud give a sequential version at least for
larger width
(i've made it anyway)

--yka

Check these IEEE references:

Efficient designs of unified 2's complement division and square root
algorithm and architecture
Sau-Gee Chen; Chieh-Chih Li; 
TENCON '94. IEEE Region 10's Ninth Annual International Conference.
Theme: 'Frontiers of Computer Technology'. Proceedings of 1994 , 22-26
Aug. 1994
Page(s): 943 -947 vol.2

A new pipelined divider with a small lookup table 
Jong-Chul Jeong; Woong Jeong; Hyun-Jae Woo; Seung-Ho Kwak; Woo-Chan
Park; Moon-Key Lee; Tak-don Han;
ASIC, 2002. Proceedings. 2002 IEEE Asia-Pacific Conference on , 6-8
Aug. 2002
Page(s): 33 -36


Efficient semisystolic architectures for finite-field arithmetic 
Jain, S.K.; Song, L.; Parhi, K.K.; 
Very Large Scale Integration (VLSI) Systems, IEEE Transactions on ,
Volume: 6 Issue: 1 , March 1998
Page(s): 101 -113

"ykagarwal" <yog_aga@yahoo.co.in> wrote in message
news:4d05e2c6.0309110200.71793e02@posting.google.com...

(snip)

> fine, thanks i cud find the book (bit old edition probably)
> here but there is no detail abt pipelined divider as such ..
> anyway if somebody comes across the thing may suggest.
> and xilinx probably shud give a sequential version at least for
> larger width
> (i've made it anyway)

The references for the 360/91 are to the IBM Research and Development
Journal, I believe Vol. 11.,
January 1967.

-- glen

soar2morrow@yahoo.com (Tom Seim) wrote in message news:<6c71b322.0309111000.5458aeee@posting.google.com>...
> Check these IEEE references:
> 
> Efficient designs of unified 2's complement division and square root
> algorithm and architecture
> Sau-Gee Chen; Chieh-Chih Li; 
> TENCON '94. IEEE Region 10's Ninth Annual International Conference.
> Theme: 'Frontiers of Computer Technology'. Proceedings of 1994 , 22-26
> Aug. 1994
> Page(s): 943 -947 vol.2
> 
> A new pipelined divider with a small lookup table 
> Jong-Chul Jeong; Woong Jeong; Hyun-Jae Woo; Seung-Ho Kwak; Woo-Chan
> Park; Moon-Key Lee; Tak-don Han;
> ASIC, 2002. Proceedings. 2002 IEEE Asia-Pacific Conference on , 6-8
> Aug. 2002
> Page(s): 33 -36
> 
> 
> Efficient semisystolic architectures for finite-field arithmetic 
> Jain, S.K.; Song, L.; Parhi, K.K.; 
> Very Large Scale Integration (VLSI) Systems, IEEE Transactions on ,
> Volume: 6 Issue: 1 , March 1998
> Page(s): 101 -113

thanks for the pointers .. i have found some of them. looking into the
NR and its variants .. whether it's possible to fit it into some 3000 slices
in virtex-ii .. may be i'll have to increase no of iteration per div step ..

"ykagarwal" <yog_aga@yahoo.co.in> wrote in message
news:4d05e2c6.0309112255.3dbc30e4@posting.google.com...
> soar2morrow@yahoo.com (Tom Seim) wrote in message
news:<6c71b322.0309111000.5458aeee@posting.google.com>...
> > Check these IEEE references:
> >
> > Efficient designs of unified 2's complement division and square root
> > algorithm and architecture
> > Sau-Gee Chen; Chieh-Chih Li;
> > TENCON '94. IEEE Region 10's Ninth Annual International Conference.
> > Theme: 'Frontiers of Computer Technology'. Proceedings of 1994 , 22-26
> > Aug. 1994
> > Page(s): 943 -947 vol.2
> >
> > A new pipelined divider with a small lookup table
> > Jong-Chul Jeong; Woong Jeong; Hyun-Jae Woo; Seung-Ho Kwak; Woo-Chan
> > Park; Moon-Key Lee; Tak-don Han;
> > ASIC, 2002. Proceedings. 2002 IEEE Asia-Pacific Conference on , 6-8
> > Aug. 2002
> > Page(s): 33 -36
> >
> >
> > Efficient semisystolic architectures for finite-field arithmetic
> > Jain, S.K.; Song, L.; Parhi, K.K.;
> > Very Large Scale Integration (VLSI) Systems, IEEE Transactions on ,
> > Volume: 6 Issue: 1 , March 1998
> > Page(s): 101 -113
>
> thanks for the pointers .. i have found some of them. looking into the
> NR and its variants .. whether it's possible to fit it into some 3000
slices
> in virtex-ii .. may be i'll have to increase no of iteration per div step
..

The 360/91 was built from transistors glued onto ceramic substrates, and
wired together.  It did double precision floating point divide in 18 clock
cycles, though.  I think it is three clock cycles per iteration, so six
iterations.

I do wonder how many Virtex devices it would take to implement a 360/91.

-- glen