How to minimize slack for mod in numerical package?

Question

Here is the snippet of the code in VHDL. I mean this IEEE.numeric_std.all

shift_reg <= b"0011" & std_logic_vector("/" (temp_result, divisor) (3 downto 0));
temp_result <= temp_result mod divisor;
divisor <= divisor / 4d"10";

This is what I got from Timing Analysis in Quartus. There is a lot of look up tables for mod

The reason why I use divisor is that the result should be displayed one by one in LCD. For instance, 365 have to divided into 3, 6 and 5 in num_array.

-- define the new type for the 6x4 RAM 
type num_array is array (0 to 5) of unsigned (3 downto 0);
 signal my_array                        : num_array:= (others => (others => '0'));

Answer 1

Problems with your code

temp_result <= temp_result mod divisor;

That's a bad idea: integer mod is an immensely complex operation.

Unless divisor is a power of 2, the combinatorial approach to modulo will be nearly as complex as doing a division.

divisor <= divisor / 4d"10";

same problem; dividing by 10 needs a relatively complex divider with a large combinatorial depth.

Complexities of integer mod and division

Here's a slightly dated view of the combinatorial implementation of division in yosys targetting a small-cell FPGA (from an older answer of mine):

(Divide on an ICE40) (warning: ~100 Mpixel image)

So, in general, doing division or mod just in a combinatorial path like you do here is a pretty bad idea.

You'll want to implement a pipelined modulo, I'd guess. Depending of the relative lengths of temp_result and divisor, that can be relatively flat, or deep.

Ways out

Well, you'll notice

1. there's probably quite some overlap between what you need to do to calculate a mod b and to calculate a / b.
2. there's no easy way out – division is just combinatorial intense. So, we need to trade slack for pipeline depth.

The 2. issue is something you'll be quite familiar with when you look what time it takes for anything but really number-crunching optimized CPUs to divide integers – many processor instruction sets do have some kind of integer divide and integer modulo operations, but they take multiple, often many, clock cycles to complete.

So, I'd try to find an existing implementation of pipelined integer division (mod is often a side product of that) (for example, on opencores.org), or write a very naive one myself, which doesn't need to have constant throughput.

Answer 2

• Division just takes a lot of steps
• A modulo operation is basically division
• Lots of steps translates into lots of logic, or a state machine
• You're building a calculator, so it doesn't have to respond much faster than a human can see it working.

Typically, in an FPGA design, when you have something complicated to do and you have lots of clock cycles to do it in, then unless you have LUTs to burn you make a state machine that breaks the complicated thing down into simpler steps.

It's the same with discrete logic design. The end point of this process evolved from the mid 1930's to the late 1940's into general purpose computers. It's still a viable thing to do inside an FPGA: use a microprocessor block, run some code, do your business.

If I didn't just slap a microprocessor block in there (there's a lot of them, including the Nios straight from Intel) I'd either implement a little 4- or 8-bit one of my own (it's a bucket list thing) or I'd research the various available division algorithms that are out there and that use state machines for a complexity vs. clock-cycle tradeoff.

Successive subtraction (just subtract 10 from your number until it's less than 10) and CORDIC are probably your best bets. Since you're building a calculator anyway you may wish to make a division block, and use it for all your arithmetic needs.