We utilize a formal model of division for determining a testbench of p-bit (dividend, divisor) pairs whose output 2p-bit quotients have properties characterizing these instances as the most challenging for verifying any division algorithm design and implementation. Specifically, our test suites yield 2p-bit quotients where the leading p-bits traverse all or a pseudo-random sample of leading bit combinations, and the next p-bits comprise a round bit followed by (p-1) identical bits. These values are proven to be closest to the p-bit quotient rounding boundaries and shown to possess other desirable coverage properties. We introduce an efficient method of generating these testbenches. We also describe applications of these testbenches at the design simulation stage and the product evaluation stage

For progressively higher radices, the reduction in partial products obtained by the well-known modified Booth multiplier recoding is offset by the need to precompute a rapidly increasing store of odd multiples of the multiplicand as inputs to each partial product generator (PPG). We propose secondary radix multiplier recoding schemes reducing the number of odd multiples required in the store for very high radix recodings (e.g., radix 2/sup r/ for 5 /spl les/ r /spl les/ 16). The proposed recoding schemes allow reduction of the number of partial products in the implementation by factors between and beyond the reduction factors of 2, 3, and 4 that can be achieved by traditional Booth recodings to radices 4, 8, and 16, respectively. We develop the theory of these recodings and provide methodology for secondary radix selection. Finally, we summarize latency and cost evaluations of selected implementations indicating potential cost and performance/cost advantages for practical operand sizes.

Many function approximation procedures can obtain enhanced accuracy by an efficient table lookup of a product z=f(x)g(y). Both x and y are represented by indices of i leading bits (typically 7<i<16) for arguments normalized to [0, 1] or [1, 2]. Direct bipartite lookup employs 1/2 bits each of x and y yielding roughly an 1/2 bit result which can lose 2 to 3 bits of accuracy when f and g are nonlinear. Indirect bipartite lookup first generates i/2 bit interval index values for f(x) and g(y) using separate j-bits-in 1/2bits-out tables for f(x) and g(y) where i/2<j

We investigate two sets of hard to round p/spl times/p bit fractions arising from division of a normalized p bit floating point dividend by a normalized p bit floating point divisor. These sets are characterized by the p/spl times/p bit fraction's quotient bit string, beginning with or just after the round bit, having the maximum number (p-1) of repeating like bits, specifically 00...01 or 11...10 for the directed rounding "RD-hard" set and 100...01 or 11...10 for the round-to-nearest "RN/sub -/hard" set. We show both the p/spl times/p bit RD-hard and RN-hard sets to be of size at least 2/sup p-2/ and at most 2/sup p-1/. Two dimensional quotient vs. divisor plots empirically reveal both the RD-hard and RN-hard sets of p/spl times/p bit fractions to be jointly widely distributed. Analysis of patterns and linear sequences of fractions visible in the quotient vs. divisor plots leads to simplified procedures for generating test suites of hard to round fractions. Our strongest computational result is the derivation of formulas that allow 2/sup (p/2)+O(1)/ RD-hard and RN-hard p/spl times/p bit fractions to be enumerated based on sequential incrementation of respective numerators and denominators.

Multipliers are used at many different places in microprocessor design. As the non-memory sub-blocks of the microprocessor with the largest size and delay, multipliers have a big impact on the cycle time of the microprocessor. Targeting deeper pipelines and higher clock frequencies, there is a growing demand for multiplier designs that can be split into shorter stages. For this purpose, the use of Booth recoding has been a popular method to cut down the number of partial products in a multiplier to reduce the delay of the partial product accumulation and to simplify the partition of the multiplier into several shorter stages. The complexity to pre-compute an increasing number of digit multiples of the multiplicand within the multiplier unit limits the use of Booth recoding mainly to radices 4 and 8. We propose novel encoding schemes for the implementation of higher radix multiplication. In particular we consider multiplication radix-32 and radix-256. The features provide more flexible multiplier designs that can be implemented in shorter pipeline stages. We compare the proposed designs with multipliers that use traditional Booth recoding.

We investigate two sets of hard to round p/spl times/p bit fractions arising from division of a normalized p bit floating point dividend by a normalized p bit floating point divisor. These sets can be characterized by the p/spl times/p bit fraction's quotient bit string, beginning with or just after the round bit, having the maximum number (p-1) of repeating like bits, specifically 00...01 or 11:..10 for the directed rounding "RD-hard" set and 100...01 or 011...10 for the round-to-nearest "RN-hard" set. We describe an algorithm for generating both the RD-hard and RN-hard sets in order of quotient value for any p, and use properties of fractions and continued fractions to characterize the distribution of these sets based on numerator, denominator, and quotient values. As a practical chip test example we summarize test runs showing our hard to round test suites are several orders of magnitude more efficient than random testing in finding erroneous quotients computed by the 1993 Pentium Processor having the well known fdiv flaw.