The floating point unit of the next generation PowerPC is detailed. It has been tested at over 5 GHz. The design supports an extremely aggressive cycle time of 13 FO4 using a technology independent measure. For most dependent instructions, its fused multiply-add dataflow has only 6 effective pipeline stages. This is nearly equivalent to its predecessor, the Power 5, even though its technology independent frequency has increased over 70%. Overall the frequency has improved over 100%. It achieves this high performance through aggressive feedback paths, circuit design and layout. The pipeline has 7 stages but data may be fed back to dependent operations prior to rounding and complete normalization. Division and square root algorithms are also described which take advantage of high-precision linear approximation hardware for obtaining a reciprocal or reciprocal square root approximation.

The IEEE 754-R floating-point standard has defined the arithmetic and encodings of the new decimal floating-point format. The C and C++ standards as well as other language standards have proposed a new data type to help programmers exploit the performance of this new hardware format. The IBM Power6 microprocessor will soon release the first hardware implementation of this decimal floating-point format. A discussion of how the decimal division operation is implemented in high frequency BCD hardware and a comparison to other division methods is provided. This implementation reuses some popular binary division algorithms such as prescaling and non-restoring division to reduce the amount of additional hardware. Novel twists are applied to these algorithms to adapt them for BCD formatted numbers.

Decimal multiplication is important in many commercial applications including financial analysis, banking, tax calculation, currency conversion, insurance, and accounting. This paper presents a novel design for fixed-point decimal multiplication that utilizes a simple recoding scheme to produce signed-magnitude representations of the operands thereby greatly simplifying the process of generating partial products for each multiplier digit. The partial products are generated using a digit-by-digit multiplier on a word-by-digit basis, first in a signed-digit form with two digits per position, and then combined via a combinational circuit. As the signed-digit partial products are developed one at a time while traversing the recoded multiplier operand from the least significant digit to the most significant digit, each partial product is added along with the accumulated sum of previous partial products via a signed-digit adder. This work is significantly different from other work employing digit-by-digit multipliers due to the efficiency gained by restricting the range of digits throughout the multiplication process.

Denormalized numbers are the most difficult type of numbers to implement in floating-point units. They are so complex that certain designs have elected to handle them in software rather than in hardware. Traps to software can result in long execution times, which renders denormalized numbers useless to programmers. This does not have to happen. With a small amount of additional hardware, denormalized numbers and underflows can be handled close to the speed of normalized numbers. This paper summarizes the little known techniques for handling denormalized numbers. Most of the techniques described here only appear in filed or pending patent applications.

The next generation zSeries floating-point unit is unveiled which is the first IBM mainframe with a fused multiply-add dataflow. It supports both S/390 hexadecimal floating-point architecture and the IEEE 754 binary floating-point architecture which was first implemented in S/390 on the 1998 S/390 G5 floating-point unit. The new floating-point unit supports a total of 6 formats including single, double, and quadword formats implemented in hardware. The floating-point pipeline is 5 cycles with a throughput of 1 multiply-add per cycle. Both hexadecimal and binary floating-point instructions are capable of this performance due to a novel way of handling both formats. Other key developments include new methods for handling denormalized numbers and quad precision divide engine dataflow. This divider uses a radix-4 SRT algorithm and is able to handle quad precision divides in multiple floating-point and fixed-point formats. The number of iterations for fixed-point divisions depend on the effective number of quotient bits. It uses a reduced carry-save form for the partial remainder, with only 1 carry bit for every 4 sum bits, to save area and power.

Almost twenty years ago the IEEE 754 binary floating-point standard was adopted. Since then almost every microprocessor as well as many programming languages have defined the floating-point arithmetic to be IEEE 754 compliant. From the many years experience in implementing the standard in hardware and writing floating-point programs, there have been numerous suggestions for revisions. All IEEE standards must undergo a review process every 5 years or be dropped as an active standard. For past reviews this standard was extended without much discussion. But finally in January 2001 an in-depth review was started. A committee was formed and over the past two years many revisions have been evaluated. The most extensive change to the standard is to adopt formats for decimal floating-point arithmetic. This proposal creates decimal floating-point data formats for 32, 64, and 128 bits. Decimal floating-point arithmetic provides an exact representation of displayed numbers and provides a precise round at decimal radix point. This type of arithmetic is required in financial calculations. Some experts argue that decimal will replace binary due to its ability to represent decimal numbers exactly, while others think that binary will remain the key floating-point format due to its speed of execution and its more regular spacing of intervals. Another once controversial proposal is the addition of fused multiply-add. This operation only causes one rounding error, while in most implementations, provides twice the performance of separate operations. Other additions to the standard include a quadword format and many predicate functions such as comparison operators like greater than. Also operators for maximum and minimum have been accepted that after hours of arguing now favor a numeric result over a NaN. There are also deletions such as the single extended and double extended formats. And there are some items that are deleted in one meeting and resurrected in the following meeting such as signaling NaNs. Over the past two years of committee review there has been many proposals discussed. This panel discussion will enlighten the audience to the additions, deletions, and some of the current controversial proposals. The panel will consist of : • David Hough, Sun Microsystems, Editor of the Standard – Overview • Mike Cowlishaw, IBM Corp., Decimal Floating-Point Software Advocate • David Bailey, Lawrence Berkeley Lab., Quadword Precision Advocate • David Matula, Southern Methodist University, Academics / Industry Consultant • Eric Schwarz, IBM Corp., Decimal Floating-Point Hardware – Panel Chair

Denormalized numbers are the most difficult type of numbers to implement in floating-point units. They are so complex that some designs have elected to handle them in software rather than hardware. This has resulted in execution times in the tens of thousands of cycles, which has made denormalized numbers useless to programmers. This does not have to happen. With a small amount of additional hardware, denormalized numbers and underflows can be handled close to the speed of normalized numbers. We will summarize the little known techniques for handling denormalized numbers. Most of the techniques discussed have only been discussed in filed or pending patent applications.

Even though decimal arithmetic is pervasive in financial and commercial transactions, computers are still implementing almost all arithmetic calculations using binary arithmetic. As chip real estate becomes cheaper it is becoming likely that more computer manufacturers will provide processors with decimal arithmetic engines. Programming languages and databases are expanding the decimal data types available while there has been little change in the base hardware. As a result, each language and application is defining a different arithmetic and few have considered the efficiency of hardware implementations when setting requirements. We propose a decimal format which meets the requirements of existing standards for decimal arithmetic and is efficient for hardware implementation. We propose this specification in the hope that designers will consider providing decimal arithmetic in future microprocessors and that future decimal software specifications will consider hardware efficiencies.

The first high performance floating point unit to support both IBM 360 hexadecimal based floating point architecture and the IEEE 754 Standard binary floating point architecture is described. The S/390 G5 floating point unit supports the new S/390 architecture which includes hexadecimal based short, long, and extended precision formats and IEEE 754 standard single, double, and quad formats. This floating point unit is part of the microprocessor chip on the S/390 G5 mainframe computer introduced in 1998 and generally available at 500 MHz speeds. The S/390 G5 represents the current state of the art in CISC processor design. The paper describes the S/390 architecture enhancements, the internal format of the FPU, and the modifications to the FPU dataflow.

The multiplier of a S/390 CMOS microprocessor is described. It is implemented in an aggressive static CMOS technology with a 0.20-/spl mu/m effective channel length. The multiplier has been demonstrated in a single-image shared-memory multiprocessor at frequencies up to 400 MHz. The multiplier requires three machine cycles for a total latency of 7.5 ns, though the design can support a latency of 4.0 ns if the latches are removed. The design goal was to implement a versatile S/980 multiplier with reasonable performance at a very aggressive cycle time. The multiplier implements a radix-8 Booth algorithm and is capable of supporting S/390 floating-point and fixed-point multiplications, and also divisions and square roots. Logic design and physical design issues are discussed relating to the Booth decoding and counter tree implementations.

Quadratically converging algorithms for high-order arithmetic operations typically are accelerated by a starting approximation. The higher the precision of the starting approximation, the less number of iterations required for convergence. Traditional methods have used look-up tables or polynomial approximations, or a combination of the two called piecewise linear approximations. This paper provides a revision and major extension to our study (1993) proposing a nontraditional method for reusing the hardware of a multiplier. An approximation is described in the form of partial product array (PPA) composed of Boolean elements. The Boolean elements are chosen such that their sum is a high-precision approximation to a high-order arithmetic operation such as square root, reciprocal, division, logarithm, exponential, and trigonometric functions. This paper derives a PPA that produces in the worst case a 16-bit approximation to the square root operation. The implementation of the PPA utilizes an existing 53 bit multiplier design requiring approximately 1,000 dedicated logic gates of function, additional repowering circuits, and has a latency of one multiplication.

SNAP-the Stanford subnanosecond arithmetic processor-is an interdisciplinary effort to develop theory, tools, and technology for realizing an arithmetic processor with execution rates under 1 ns. Specific improvements in clocking methods, floating-point addition algorithms, floating-point multiplication algorithms, division and higher-level function algorithms, design tools, and packaging technology were studied. These improvements have been demonstrated in the implementation of several VLSI designs.>

A method for obtaining high-precision approximations of high-order arithmetic operations is presented. These approximations provide an accurate starting approximation for high-precision iterative algorithms, which translates into few iterations and a short overall latency. The method uses a partial product array to describe an approximation and sums the array on an existing multiplier. By reusing a multiplier the amount of dedicated hardware is made very small. For the square-root operation, a 16-bit approximation costs less than 1000 dedicated logic gates to implement and has the latency of approximately one multiplication. This is 1/500 the size of an equivalent look-up table method and over twice as many bits of accuracy as an equivalent polynomial method. Thus, a high-precision approximation of the square root operation and many other high-order arithmetic operations is possible at low cost.>

An algorithm for high-radix nonrestoring division is proposed which combines a cost-efficient quotient estimation technique with collapsing of the division into one operation each iteration. The quotient estimation technique is a direct combinatorial algorithm which allows a more generalized partial remainder than similar studies. In addition, the successor partial remainder is calculated directly from the previous partial remainder. The intermediate steps of calculating the next quotient estimate, multiplying it by the divisor, and then subtracting the result from the previous remainder are telescoped into one step. This is possible due to the use of simple direct combinatorial equations for the quotient estimate. Thus, one operation is used to generate the next remainder from the previous remainder. This operation is similar to a multiplication with a reduced carry propagate adder. This algorithm reduces the latency of each iteration to less than the delay of one multiplication. Thus, high-radix nonrestoring division is possible with a low latency and no need for an off-chip ROM to hold a quotient estimate.>

A multibit overlapped scanning multiplication algorithm for sign-magnitude and two's complement hard-wired multipliers is presented. The theorems necessary to construct the multiplication matrix for sign-magnitude representations are emphasized. Consequently, the algorithm for sign-magnitude multiplication and its variation to include two's complement numbers are presented. The proposed algorithm is compared to previous algorithms that generate a sign extended partial product matrix, with an implementation and with a study of the number of elements in the partial product matrix. The proposed algorithm is shown to yield significant savings over well known algorithms for the generation and the reduction of the partial product matrix of a multiplier designed with multibit overlapped scanning.>

Algorithms are presented for finite state machine (FSM) verification and image computation which improve on the results of O. Coudert et al (1989), giving 1-4 orders of magnitude speedup. Novel features include primary input splitting-this PODEM feature enlarges the search space but shortens the search due to implications. Another new feature, identical subtree recombination, is shown to be effective for iterative networks (eg, serial multipliers). The free-variable recognition feature prevents unbalanced bipartitioning trees in tautological subspaces. Finally, reached set pruning is significant when the image contains large numbers of previously reached states.>

The authors describe efficient polynomial algorithms for the extraction of topologically minimal multilevel Boolean equations and don't care conditions from the C-based hardware description language CHDL, which has control constructs switch, if-then-else, and go-to. They show that significant savings in CPU cost, area cost, and robustness may be obtained by applying these algorithms as a preprocessing step before using higher cost minimization tools such as BOLD or misII. The approach is based on a control-flow-graph construct with embedded set-use-graph information. The algorithms parse a CHDL description into a directed, nonseries parallel control flow graph. In cases where the graph is also acyclic, graph search and decomposition algorithms are used to derive a Boolean network representing the implied combinational logic. The derived equations are topologically irredundant in the sense that the topological identities are associated with the fork, and join nodes of the control flow graph are accounted for in the code generation. Without this feature, multilevel logic optimizers would have to flatten the control expressions down to primary inputs to discover these identities.>

Because of recent advances in technology, multibit scanning implementations can be considered that exceed three-bit and four-bit groupings. The generalized proof for the multibit overlapped scanning multiplication is introduced, and the multiplication process is discussed. The proofs are intended to establish the correctness of the decode and the actions taken to produce the multiplication of any valid scheme proposed in the past, and to dictate the correct decode and actions taken for any overlapped s-bit scanning algorithm such that s is a natural number greater than or equal to two. The multiplication is considered to be between two fractional numbers, which are represented in two's-complement form.>