A new iterative structure for hardware division: the parallel paths algorithm

We present a new approach to hardware division - the parallel paths algorithm. In this approach, prescaling allows the division recurrence to be implemented by three processes which can be calculated in parallel during iterations. While two of the processes must complete in a single iteration, the third - which includes the most expensive division operations - can be calculated over multiple iterations. Iteration latency is determined by the slowest of the three paths, and in many cases can be limited to that of carry-save addition and latching. A radix-4 implementation of the algorithm is shown to achieve better performance than other commonly used methods while requiring a modest increase in area.