Newton-Raphson Integer Division for Area-Constrained Microcontrollers
Nima Badizadegan · 2023
Many small microcontrollers today are equipped with single-cycle multipliers, but use division algorithms that compute only one bit at a time, resulting in division operations with up to 32 (or more) CPU cycles of latency, stalling the core during computing. This is primarily due to area constraints, since fast division algorithms based on iterative approximation require relatively large lookup tables to produce a useful speedup over slower algorithms.We propose an alternative to using lookup tables for the initial approximation. Instead, we augment the single-cycle multiplier to compute a heavily-quantized polynomial approximation of 1/D. The resulting approximation has 8-bit precision and computes in a single cycle at a cost of 400 added logic gates.Finally, we demonstrate a state machine that performs 32-bit integer division using the augmented multiplier and a microcontroller ALU to compute quotient and remainder with 3–11-cycle latency. When synthesized in a MAX 10 FPGA, the datapath with fast division used 3,260 logic elements, compared to 2,759 LEs for a microcontroller datapath without division, an area increase of only 18%, or 4x less than the area of a single-cycle multiplier.