Integer division by small constants

Abstract

Integer division is considered within the context of the development of iHARP, an integrated circuit version of HARP, the HAtfield RISC Processor architecture. The paper demonstrates that execution times for division by small constants can be significantly reduced. Two cases are considered, division by powers of two and division by other small constants. In each case specialised instruction primitives are introduced to reduce the execution time. If an arithmetic shift right instruction is used to implement division by a power of two, an incorrect result is produced for negative dividends. The first iHARP primitive corrects the shift result and allows division by powers of two to be performed in a single machine cycle. The second iHARP primitive allows division by other small constants to be implemented efficiently as a finite series of multiplication steps. Execution time is reduced both by decreasing the number of operations involved and by exploiting the parallel nature of the iHARP architecture.