Large unsigned dividers with limited clock cycles, how can I

[Mr. Ken]

It seems that in shift & subtract, the number of cycles required equals to
the number of bits
in the dividend. I have dividend of 30 bits and divisor 5 bits. I am given
10 cycles to finish it.
Gate count needs to be kept small.

What's the best way to design it?

Is it customary to fix three stages of shift & subtract in one cycle?

 

[mk]

On Mon, 11 Sep 2006 22:49:28 +0800, "Mr. Ken" <Mr.Ken@novice.com>
wrote:

It seems that in shift & subtract, the number of cycles required equals to
the number of bits
in the dividend. I have dividend of 30 bits and divisor 5 bits. I am given
10 cycles to finish it.
Gate count needs to be kept small.

What's the best way to design it?

Is it customary to fix three stages of shift & subtract in one cycle?

SRT dividers retire two bits at a time and probably the best algorithm
for dividers.

 

[John_H]

"Mr. Ken" <Mr.Ken@novice.com> wrote in message
news:ee3qd4$gf9$1@mawar.singnet.com.sg...

It seems that in shift & subtract, the number of cycles required equals to
the number of bits
in the dividend. I have dividend of 30 bits and divisor 5 bits. I am given
10 cycles to finish it.
Gate count needs to be kept small.

What's the best way to design it?

Is it customary to fix three stages of shift & subtract in one cycle?

While SRTs are fast, they're not obvious as shown by Intel's Pentium. I've
also had trouble finding decent documentation online.

You didn't mention how many result bits and whether you want a remainder.
Are you in an ASIC flow with available libraries?

The Egyptian Division algorithm (shift and add/subtract depending on the
sign) implemented very well in an FPGA and might serve better in the ASIC
realm than shift/subtract as well with one add/sub stage per bit, no mux.
To get the result in 10 cycles, you need 3 add/sub stages per pipeline stage
or per clock *as long as* the dividend is well behaved with respect to the
divisor. If you need continuous throughput rather than one input every 10
clocks, pipelining needs to cut up your dividend while building your result.

As long as this isn't homework I'd be happy to send you an Excel spreadsheet
showing the division as implemented with the add/sub stages.

Since we know you need:
5 bit divisor
30 bit dividend
Questions that need to be answered:
How many result bits?
Is remainder needed?
What is the largest result value? (Dividend to divisor relationship)
or perhaps what's the range of each value?

For integers, 30 bits divided by 5 bits could result in 25 to 30 bits
depending on the ranges needed. It's actually the number of needed result
bits that determines the actual number of stages needed.