Frédéric Pétrot

Grenoble INP - UGA, France

Experimental Software and Hardware Evaluation of Ad-Hoc Constant Division Routines

Abstract

Dividing by a constant is an operation that is often needed in algorithms, be they implemented in software or in hardware. Given the fact that general purpose processors have had fast hardware multipliers for decades, the solution for software is to multiply by a compile time computed reciprocal and perform some adjustment. However, for hardware implementations, in particular with relatively small and exotic bit sizes, shift-and-add solutions might be worth looking at. In this presentation, we report our study on implementing constant unsigned division based on Li’s work. We found that a few of his algorithms are wrong
and propose corrections that need a bit more computations. For software, we show that the approach can be useful only for low-end microcontrollers. For hardware, our FPGA and ASIC synthesis outline that it has good scalability, although being not very efficient for small dividends. As delay and area are very dependent on the value of the divisors, this approach appears as yet another possibility to choose from when looking on how to divide by a given constant.

Biography

Frederic Petrot received the PhD degree in Computer Science from Universite Pierre et Marie Curie (Paris VI), Paris, France, in 1994, where has been Assistant Professor in Computer Science until September 2004. He joined TIMA in September 2004, where he holds a professor position at Grenoble Institute of Technology, France. His research interests are in multiprocessor systems on chip architectures, including circuits and software aspects, and CAD tools for the design and evaluation of hardware/software systems.

Download