Chipress

In our 1st book in “Crack the Hardware Interview”, we discussed how to implement arbitrary integer division in RTL, and such division takes several clock cycles to complete and is costly in physical implementation.

It is also quite common to implement integer division by constant in hardware design. We will cover a few cases in this post, where integer division by constants can complete in a single clock cycle.

Divide by a Known-at-Compile-Time Constant

If the constant divisor is known at compile time, there will be a few more sub-cases to consider.

If the constant is a power-of-2 number, we can simply use left shift operation.

If the constant is a non-power-of-2 number, the most straightforward way is to use Verilog’s division operator “/”. Typically, the RTL is synthesizable and is able to meet single-cycle timing if the divisor is small, for example, “/3” and “/5”.

Separately, RTL designers often convert division to multiplication. For example:

1. “/3” can be converted to (x * 10922) / 32768 = (x * 10922) >> 15
2. “/6” can be converted to (x * 683) / 4096 = (x * 683) >> 12
3. “/9” can be converted to (x * 455) / 4096 = (x * 455) >> 12

Of course, the above example is an approximation to division, and the results of the multiplication may only be the same as the real division if the dividend falls within a certain range. RTL designers must carefully analyze the dividend values and make sure the error of the final results is within the expectations.

In addition, converting division to multiplication often involves rounding, and the result from multiplication will often add a rounding term before being right shifted.

Divide by an Unknown-at-Compile-Time Constant

If the constant divisor is unknown at compile time, we can ask SW to configure (1/divisor) value to a configuration register before HW operation starts. The HW can again convert the division to multiplication.