1
\$\begingroup\$

I need to divide an integer by an integer in one clock cycle. how should I do this? I have a function for it I found on the internet but it always returns one.

function  divide  (a : unsigned; b : unsigned) return integer is
    variable a1 : unsigned(15 downto 0):=a;
    variable b1 : unsigned(15 downto 0):=a;
    variable p1 : unsigned(16 downto 0):= (others => '0');
    variable i : integer:=0;
    begin
        for i in 0 to b'length-1 loop
            p1(b'length-1 downto 1) := p1(b'length-2 downto 0);
            p1(0) := a1(a'length-1);
            a1(a'length-1 downto 1) := a1(a'length-2 downto 0);
            p1 := p1-b1;
            if(p1(b'length-1) ='1') then
                a1(0) :='0';
                p1 := p1+b1;
            else
                a1(0) :='1';
            end if;
        end loop;
        return to_integer(a1);
    end divide;
\$\endgroup\$
13
  • \$\begingroup\$ Division is always a bit more difficult than multiplication. Think about multiplying by the reciprocal and getting the reciprocal of the divisor from a look up table. \$\endgroup\$ Oct 11, 2015 at 20:37
  • 3
    \$\begingroup\$ Maybe "variable b1 : unsigned(15 downto 0):=b;" instead of ...":=a" \$\endgroup\$
    – TEMLIB
    Oct 11, 2015 at 20:59
  • 1
    \$\begingroup\$ Are your inputs (dividend and divisor) both variables ? Doing a 1 cycle divider is possible, but it will work at low frequency and occupy a lot of area (well, of course, it depends on the width of the operands...). \$\endgroup\$
    – TEMLIB
    Oct 11, 2015 at 21:02
  • \$\begingroup\$ One cycle latency, or one cycle throughput? \$\endgroup\$
    – Neil_UK
    Oct 11, 2015 at 21:13
  • 2
    \$\begingroup\$ One cycle latency 16 bits divider is a really bad idea. It requires 16 consecutive adders, which means a lot of area and a very long critical path. If you can live with an approximation, multiplying by inverse would be better, but for 16 bits requires a lot of ROM... Some division algorithm should yield smaller circuit (like SRT-4) and faster division, but requires the MSB of divider to be alway '1'. \$\endgroup\$ Oct 11, 2015 at 21:34

2 Answers 2

5
\$\begingroup\$

This answer isn't what you're looking for, but the basic solution to this problem is this: Don't use division.

Many processor architectures and even DSP chips do not have a division instruction at all, and where they do have division, it is usually a multi-cycle operation, because division is fundamentally iterative. Division is expensive in terms of area, and slow, so it is usually avoided if possible.

I strongly suggest that yourself or anybody reading this question tries very hard to avoid implementing a hardware divide function of any sort, let alone a single-cycle one. As some comments have said, the standard approach would be to implement a multiplication by the reciprocal of the divisor. Even here, if you expect good performance in your FPGA, this would be implemented using a pipelined architecture, and so would not have single-cycle latency.

An even better solution would be to revise your design such that there is no need for any division or an equivalent. However, without knowing what your design is supposed to do, it's impossible to suggest alternatives.

As a footnote, and as a comment noted, division by a power of two is relatively simple, because it boils down to a shift operation.

\$\endgroup\$
2
  • 1
    \$\begingroup\$ I will still NEED to do division. how would I do multi-cycle division? I am making a processor in an fpga and division will be more than necessary. Code is not required, but preferred. Sorry to bother you again. \$\endgroup\$ Oct 17, 2015 at 19:47
  • 1
    \$\begingroup\$ I suggest you create a working processor, and implement a division routine in software. This is what has been done in most processor designs for decades. Programmers are mostly aware that 'divide' is expensive, and would not put this operation in an inner loop or other critical code section. You could always go back and add some hardware division support later, if this turned out to be a real bottleneck in your application. \$\endgroup\$
    – scary_jeff
    Oct 19, 2015 at 8:14
0
\$\begingroup\$

The algorithm you gave originally is a 'restoring division' algorithm; it requires one clock cycle for each bit of the quotient. Non-restoring division is normally used in hardware; this also takes one cycle per bit of the quotient. There are about a billion Google hits on non-restoring division. It's simple, but a bit fiddly - give it a go and ask if/when it doesn't work.

Don't even think about invert/multiply unless the dividend is a constant, in which case it's easy and fast, and won't even require a multiplier (you can use adders instead).

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.