Approximate unsigned binary integer dividers for arithmetic data value speculation

Abstract

Unsigned integer dividers capable of finding an approximate quotient are presented. The approximate quotient is most often the exact integer quotient, but can contain an error. Such approximating arithmetic can be used in a speculative execution to increase the throughput of a processor pipeline, or in probabilistic computation, where speed is more important than accuracy. In this paper a new algorithm for the approximate division of unsigned binary integers, and three divider designs based on this approximating algorithm are presented. Each divider is analysed in terms of probability of producing a correct quotient and delay. Logic synthesis is used to compare the delay, area and power of the approximating dividers. An approximating 32/32 bit divider is presented with a 99.4% probability of correctness for benchmark inputs, operating 22.5% faster than an exact radix-4 SRT divider.