SUBNANOSECOND ARITHMETIC for 1990-1993

Michael J. Flynn Giovanni DeMicheli R. Fabian Pease Bruce Wooley Technical May 1993

SUBNANOSECOND ARITHMETIC for 1990-1993

by Michael J. Flynn Giovanni DeMicheli R. Fabian Pease Bruce Wooley Technical May 1993

Computer Systems Laboratory Departments of Electrical Engineering and Computer Science Stanford University Stanford, California 94305-4055

Abstract

The Stanford Nanosecond Arithmetic Project is targeted at realizing an arithmetic processor with performance approximately an order of magnitude faster than currently avaiable technology. The realization of SNAP is predicated on an interdisciplinary approach and effort spanning research in algorithms, data representation, CAD, circuits and devices, and packaging. SNAP is visualized as an arithmetic coprocessor implemented on an active substrate containing several chips, each of which realize a particular arithmetic function. We have fabricated a number of prototype die.

Copyright \begin{matrix}c \\ ◯ \end{matrix} 1994

by

Michael J. Flynn Giovanni DeMicheli R. Fabian Pease Bruce Wooley

Contents

0.1 Algorithms and Systems . . . . . . . . . . . . . . . . . . . . . . . . . 1 0.1.1 Wave Pipelining . . . . . . . . . . . . . . . . . . . . . . . . . . 1 0.1.2 Addition and Floating-point Addition . . . . . . . . . . . . . . 1

Figure 1: A Wave Pipelined Multiplier . . . . . . . . . . . . . . . . . . . . 3

0.1.3 Floating-point Multiplication . . . . . . . . . . . . . . . . . . 4 Figure 2: An ECL Multiply . . . . . . . . . . . . . . . . . . . . . . . . . . 5

0.1.4 Division and Higher Level Functions . . . . . . . . . . . . . . 6 0.2 MCM Technology . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 Figure 3: Membrane MCMs . . . . . . . . . . . . . . . . . . . . . . . . . . 7 0.3 Advanced Packaging . . . . . . . . . . . . . . . . . . . . . . . . . . . 8

0.3.1 Microcontacts . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 0.3.2 Superconducting Chip-to-chip Interconnects . . . . . . . . . . 8

0.4 List of NSF-Supported (SNAP) Publications . . . . . . . . . . . . . . 9

List of Figures

1 A wave pipelined 16^{b} multiplier in CMOS (0.8 cycles). Figure shows repetition rate, latency is about 9 ns, upper and lower parts show different data patterns. . . . . . . . . . . . . . . . . . . . . . . . . . . . 3

2 An ECL 53 × 53^{b} (IEEE standard) multiply in 5.2 ns (latency). The

106^{b} addition at the multiply end takes 850 ps. . . . . . . . . . . . . . 5 3 (a) Membrane multi-chip module in Si. (b) Process steps for making

membrane MCM substrate. (c) Time domain reflectometry. . . . . . . 7

List of Tables

v

SNAP—the Stanford subnanosecond arithmetic processor—is an interdisciplinary effort to develop theory, tools, and technology realizing an arithmetic processor with execution rates under 1 ns. During the course of our SNAP project, we have made significant progress toward accomplishing a gigaflop (a billion floating-point arithmetic operations per second) computing element. This report is an extended abstract summarizing the SNAP results.

0.1 Algorithms and Systems

We have completed a number of arithmetic designs, summarized in Table 1.

0.1.1 Wave Pipelining

Ordinary pipeline systems operate at a frequency that corresponds to the maximum logic path delay between any two stages. Theoretically, it is possible to increase this frequency by an amount of time equal to the minimum path delay that might occur in the worst-case stage.

In SNAP research, we have shown that it is possible to use CAD tools to automatically increase the minimum or the fast paths to a point where the minimum path logic acts as a significant part of the storage system. We have shown that clocking ECL circuits at 2-1/2 to 3 times the maximum propagation delay is feasible. In a bipolar (ECL) experiment, Wong [P27] showed that the path of a multiplier that had a worst-case path delay of about 10 nanoseconds could be safely clocked at a 4-nanosecond rate. In further research using a CMOS multiplier, Klass [P3] has designed a 6-times improvement in clock rate, resulting in a 600 MHz integer multiplication (see Figure 1).

0.1.2 Addition and Floating-point Addition

We have been able to optimize earlier work by Ling on integer adders [1] to avoid excessive fanout, yet preserve the speed advantage. We have also mapped the Ling approach over to CMOS technology [P13].

We have made basic improvements to the floating-point addition algorithm. Conventionally, floating-point addition consists of a subtraction of exponents, a shifting of fractions by an amount equal to the exponent difference, addition or subtraction of the fractions, a shifting of the result (on subtraction) to leave it in normalized form, and a rounding of the result. These steps are generally sequential, and require two shifts and three additions (the exponent subtraction, fraction addition, and rounding). Farmwald, in earlier work [2], showed that one of the shifts could be eliminated by creating two simultaneous paths, since a long preshift could not be accompanied by a long postshift following the fraction addition/multiplication. Quach has shown that it is possible to further improve the floating-point addition by integrating the

Table 1: SNAP Die Fab Status

Die  Company* Technology Status Project
Integer adder  Signetics  ECL  F.T. Measured 2ns 32-bit integer [P1]
F.P. adder (53b IEEE)  HP Research CMOS  Sub. 15ns latency [P11]
Multiplier (pp) slice  Signetics  BiCMOS F.T. Under 10ns pp tree only [P20]
Multiplier (pp) slice  Signetics  BiCMOS F.T. Under 7ns pp tree only [P20]
F.P. multiplier (53b IEEE) Sun Micro. ECL  Sub. Full FMPY in under 5ns
W.p. multiplier (pp) slice Signetics  ECL  F.T. 3.8ns cycle time measured [P28]
W.p. multiplier 16 × 16b HP**  CMOS  Sub. 1.8ns cycle time simulated (CMOS)
Divider  —  CMOS  NYS Still under study

* Company that sponsored die fab. All but one (**) were paid for by sponsor company. Abbreviations: F.T. = Fully tested Sub. = Submitted NYS = Not yet submitted W.p. = wave pipelined, F.P. = floating-point

2 Figure 1: A wave pipelined 16^{b} multiplier in CMOS (0.8 cycles). Figure shows repetition rate, latency is about 9 ns, upper and lower parts show different data patterns. rounding step with the final fraction addition [P14]. This is done by creating up to four different results and MUXing out the correct result. By careful management and integration of the paths, the overall hardware cost is only modestly increased over the state-of-the-art approach. A floating-point adder based upon this idea has been fabricated and is being tested. Using a conventional 1-micron CMOS, process, the floating-point addition delay is about 15–16 nanoseconds (IEEE standard floatingpoint addition).

0.1.3 Floating-point Multiplication

In the area of floating-point multiplication, we have completed two separate studies.

The first concentrated on the use of regular counters, after the work of Santori [3]. This study developed two structures for partial-product reduction for IEEE standard floating point multiplication, leading to structured layouts. Such layouts are desirable because they require shorter wires and therefore support faster operation. The former approach uses a reduction scheme based on a 28/5 counter followed by 55/4 counters. The latter uses a novel family of counters, called 9/2, 6/2, and 4/2 respectively. Both approaches use 3/2 counters as basic building blocks.

We have developed automatic programs for synthesizing the layout of these two structures. The programs are portable across different, but similar, circuit technologies. We have implemented two sample chips, one for each style, in BiCMOS technology. The 28/5 approach had delay of 10 ns, while the 9/2 approach had delay of 7 ns.

In the second multiplication study, we have developed a scheme based upon a redundant 3-bit Booth encoding of the multiplier. This redundant encoding reduces the number of partial products to be summed by one-third over a full (53 bit) tree partial product summation, but it avoids the requirement of forming plus or minus three multiples of the multiplicand. Coupled to the multiplier encoding, we have developed techniques that allow us to handle irregular counter implementations of the partial product tree. State-of-the-art implementations of partial product trees have focused on 4–2 and similar approaches that provide a regularity in wiring of the partial product tree. We have shown with this work that it is possible to use irregular implementations based upon 3–2 counters with the assistance of CAD tools, which automatically optimize the routing and path length through the partial product tree. Using the combined techniques of the redundant multiplier encoding, and the CAD-assisted layout of the partial product tree, we have implemented a full IEEE floating-point multiplier. This is being implemented now in ECL with the sponsorship of SUN Microsystems. The full multiplier is expected to have an overall delay of five nanoseconds (see Figure 2).

1 – input (t = 0) 2 – output of tree (t = 4.3ns) 3 – final produce (t = 5.2ns) 4 – multiples ready (3x, 1x) t = 0.6ns

Figure 2: An ECL 53 × 53^{b} (IEEE standard) multiply in 5.2 ns (latency). The 106^{b} addition at the multiply end takes 850 ps.

0.1.4 Division and Higher Level Functions

SNAP has advanced both SRT and functional iteration approaches to division [P12]. In SRT, we have developed techniques for extending the SRT approach to radix 64 division [P15,P30]. We have also shown that improved methods of division by functional iteration are also possible.

Higher-level functions such as square root, logarithm, exponent, and various trig functions are normally performed in software at commensurately much slower speeds. Even if only an approximation to one of these functions is required, a significant amount of time is consumed in producing the result. Occasionally tables are stored in memory to expedite the process of developing either an approximation to, or a starting point for, an algorithm to produce a high-level function or result. These schemes necessarily are limited, as they require growing amounts of table space and still provide limited performance in developing even an approximate result.

Schwarz [P19] has shown that since these functions can generally be represented as a power series (a series of terms involving the powers of the argument of the function), they can be approximated by making special use of the partial product tree of a multiplier. The partial product tree of a multiplier is that portion of a multiplier that sums up 53 multiples of the multiplicand. Each multiple is shifted by a power of two with respect to the other multiples. Thus, the partial product tree represents a sum of 53 terms in a series with the multiplicand being the argument. Schwarz noted that it is possible to enter an argument and, instead of simply replicating it (originally the multiplicand) 53 times by providing modified versions of the argument (ANDed or exclusive-ORed with various constants), we could make approximations to the power series for these high-level functions. The basic manipulations are determined by backsolving an equation that approximates the function to be determined. Using these techniques, it is possible to get an approximation to all of the trig functions as well as the transcendental functions generally accurate to between 11 and 20 bits. This is all accomplished with only a slight increase in multiplier hardware, and it is accomplished in the same time as that to compute a product.

0.2 MCM Technology

Considerable progress has been made in the area of high-performance packaging. In particular, a technology for attaching and connecting chips onto a silicon membrane multichip module (MCM) has been demonstrated [P2]. This technology utilizes conventional IC processing techniques and offers a high density (over 500 per chip) of small (as small as 10 × 10 μm^{2}), low resistance (less than 0.024 Ω/contact) and low parasitic interconnections between a chip and the substrate (see Figure 3). In addition, controlled impedance striplines have been fabricated on the MCM substrate.

The initial experimental striplines have been implemented in a three-layer ground-Figure 3: (a) Membrane multi-chip module in Si. (b) Process steps for making membrane MCM substrate. (c) Time domain reflectometry. signal-ground configuration with aluminum conductors and polyimide dielectric. The sandwiched structure ensures a constant characteristic impedance as the stripline crosses the boundary between the MCM substrate and the chip. The stripline has been characterized with time domain reflectometry. The delay is 68 psec/cm which corresponds to a propagation velocity of 1.5 × 10^{10} cm/sec. A pulse rise time of 72 psec, which corresponds to a −3dB bandwidth of 3 GHz, has been measured on a 1-cm long line. These results are consistent with those predicted by simulations.

0.3 Advanced Packaging

Ultimately, SNAP depends on extremely fast interconnects with a large array of die to package connections. In addition to its MCM work, SNAP has undertaken other advanced experimental packaging approaches to support 50–100 picosecond signal rise times and high-density interconnects.

0.3.1 Microcontacts

Despite the fundamental advantages of high density packaging, the introduction of advanced technology has been very slow. One of the difficulties has been the unreliability of low-force pressure contacts which has hampered exhaustive testing of chips prior to mounting and has restricted our choice of high-density, reversible mounting technologies (such as the original active substrate configuration).

To attack this problem, we designed, built, and carried out preliminary experiments with a novel instrument that is essentially a combined scanning tunneling microscope and atomic force microscope (STAFM). This allowed us to measure the electrical properties of contacts with controllable forces down to a few nN, many orders of magnitude below those normally employed. In this way, we can not only study low-force contacts per se, but can build up a model of macroscopic contacts as arrays of STM’s in parallel.

In the preliminary experiments carried out under this contract, we were able to demonstrate electrical conduction between gold surfaces quite close to the value predicted by the deformation of a gold surface under the action of the tip. This apparatus was the subject of a paper presented at the Holm conference on contacts in 1992. Because this work was judged to have medium-to-short term applicability, the project was picked up by the SRC in 1991.

0.3.2 Superconducting Chip-to-chip Interconnects

High density of on-chip circuitry leads to higher speed, lower power, and, apparently, to greatly reduced cost per function. Higher density at the system level should also lead to equivalent gains. Indeed, it is now being argued that achieving such gains is much more practical by increasing the density of chip-to-chip interconnects because we are not pushing the state of the art in high-resolution fabrication in such interconnects; dimensions of chip-to-chip interconnects are typically expressed in mils, not microns. However, studies both in the U.S. and abroad show that the limit to achieving such density in normal metallic interconnects is set by the the resistivity of the metal (see, for example, Masaki [4]). In our previous work, it appeared that a signal line pitch of about 35 microns was the practical limit for terminated, matched transmission lines operating at a clock frequency of 1 GHz.

Given the above limit, the possible application of (high temperature) superconductors in such transmission lines is obvious. An early (paper) study treated the high temperature superconductors as high-temperature analogs of low-temperature, metallic superconductors and predicted significant advantages at clock frequencies up to several GHz.

Under this contract, we built transmission lines using the high-temperature superconductor YBCO, and experimentally demonstrated that the predictions of the paper study held good for lines down to a few microns; i.e., the effects of the kinetic inductance (due to the low density of superconducting electron-pairs) in this material were negligible for frequencies up to 20GHz. The PhD dissertation of B. W. Langley [5] describing this work is in the final stages of preparation.

0.4 List of NSF-Supported (SNAP) Publications

P1. G. Bewick, P. Song, G. De Micheli and M. Flynn, “Approaching a Nanosecond: A 32 Bit Adder,” ICCD, Proceedings of the International Conference on Circuit and Computer Design, Rye, NY, pp. 221–226, October 1988.

P2. W. Cheng, M. Beiley and S. Wong. “Membrane Multi-Chip Module Technology on Silicon,” to be presented at IEEE Multi-Chip-Module Conference, Santa Cruz, March 1993.

P3. F. Klass. Balancing Circuits for Wave Pipelining. Technical report CSL-TR-92-549, October 1992.

P4. B. W. Langley and R. F. W. Pease. “Superconducting Interconnects for VLSI Multi-chip System Integration.” In Proceedings, Symposium on VLSI Technology, June 1990.

P5. J. M. Mulder, Nhon T. Quach, and Michael J. Flynn. “An area model for on-chip memories and its application.” Journal of Solid State Circuits, 26(2), February 1991.

P6. R. F. W. Pease. “System Level Packaging: An Alternative to Monolithic ULSI.” Invited Plenary Paper, International Electron Devices Meeting, December 1990.

P7. N. T. Quach and M. J. Flynn. High-Speed Addition in CMOS. Technical report CSL-TR-90-415, February, 1990.

P8. N. T. Quach and M. J. Flynn. An Improved Algorithm for High-Speed Floating-Point Addition. Technical Report CSL-TR-90-442, August, 1990.

P9. N. T. Quach, N. Takagi, and M. J. Flynn. On fast IEEE rounding. Technical Report CSL-TR-91-459, Stanford University, January 1991.

P10. N. T. Quach and M. J. Flynn. Leading one prediction—implementation, generalization, and application. Technical Report CSL-TR-91-463, Stanford University, March 1991.

P11. N. T. Quach and M. J. Flynn. Design and Implementation of the SNAP Floating-Point Adder. Technical Report CSL-TR-91-501, December 1991.

P12. N. T. Quach and M. J. Flynn. A Radix-64 Floating-Point Divider. Technical report CSL-TR-92-529, June, 1992.

P13. Nhon Quach and M. J. Flynn. “High-Speed Addition in CMOS.” IEEE Transactions on Computers, Vol. 41, No. 12, December 1992.

P14. Nhon Quach. Performance Improvement in Basic Floating-Point Operation. PhD thesis, Stanford University, 1993.

P15. E. M. Schwarz and M. J. Flynn. “Cost-efficient high-radix division.” Journal of VLSI Signal Processing, August 1991.

P16. E. M. Schwarz and M. J. Flynn. Direct combinatorial methods for approximating trigonometric functions. Technical report CSL-TR-92-525, May 1992.

P17. E. M. Schwarz and M. J. Flynn. “Approximating the sine function with combinational logic.” In Proc. of 26th Asilomar Conf. on Signals, Systems, and Computers. October 1992.

P18. E. M. Schwarz and M. J. Flynn. Using a floating-point multiplier to sum signed Boolean elements. Technical report CSL-TR-92-540, August 1992.

P19. E. M. Schwarz. High Radix Algorithms for High-Order Arithmetic Operations. PhD thesis, Stanford University, January 1993.

P20. P. Song and G. De Micheli, “Circuit and Architecture Trade-offs for High-Speed Multiplication,” IEEE Journal on Solid State Circuits, Vol. 26, No. 9, pp. 1184– 1198, September 1991.

P21. Paul Song. New Circuits and Structures for Combinational Multipliers, PhD thesis, Stanford University, March 1993.

P22. Naofumi Takagi. A radix-4 modular multiplication hardware algorithm. Technical Report CSL-TR-91-458, Stanford University, January 1991.

P23. D. Wong. “A High-Speed Hardware Unit for a Subset of Logic Resolution.” In Proceedings of MICRO-21, pp. 73–78, November 1988.

P24. D. Wong, G. De Micheli, and M. Flynn. “Designing High-Performance Digital Circuits Using Wave Pipelining.” In Proceedings of VLSI ’89, pp. 241–252, August 1989.

P25. D. Wong, G. De Micheli, and M. Flynn. “Inserting Active Delay Elements to Achieve Wave Pipelining.” In Proceedings of ICCAD ’89, pp. 270–273, November 1989.

P26. D. Wong and M. Flynn. “Fast Division Using Accurate Quotient Approximations to Reduce the Number of Iterations.” In Proceedings of the 10th IEEE Symposium on Computer Arithmetic, pp. 191–201, June 1991.

P27. D. Wong. Techniques for Designing High-Performance Digital Circuits Using Wave Pipelining. PhD thesis, Stanford University, August 1991.

P28. D. Wong, G. De Micheli, and M. Flynn. “A Bipolar Population Counter Using Wave Pipelining to Achieve 2.5x Normal Clock Frequency.” In Proc. International Solid-State Circuits Conference, pp. 56–57, February 1992.

P29. D. Wong, G. De Micheli, and M. Flynn. “A Bipolar Population Counter Using Wave Pipelining to Achieve 2.5x Normal Clock Frequency.” Journal of Solid-State Circuits, Vol. 27, No. 5, pp. 745–753, May 1992.

P30. D. Wong and M. Flynn. “Fast Division Using Accurate Quotient Approximations to Reduce the Number of Iterations.” IEEE Transactions on Computers, 41(8):981–995, August 1992.

P31. D. Wong, G. De Micheli and M. Flynn, “Algorithms for Designing High-Performance Digital Circuits Using Wave Pipelining,” IEEE Transactions on CAD/ICAS, pp. 25–46, January 1993.

References

[1] H. Ling. “High-Speed Binary Adder.” IBM Journal of Research and Development, Vol. 25, No. 2 and 3, pages 156–166, May 1981.

[2] M. P. Farmwald. On the Design of High-Performance Digital Arithmetic Units. PhD theses, Stanford University, August 1981.

[3] M. Santoro. Design and Clocking of VLSI Multipliers. PhD thesis, Stanford University, October 1989.

[4] Akira Masaki. “Electrical Resistance as a Limiting Factor for High Performance Computer Packaging.” IEEE Circuits and Devices Magazine 5(22), 1989.

[5] B. W. Langley. High-Temperature Superconducting Microstrip Lines: Digital System Interconnect Applications and Magnetic Penetration Studies PhD Dissertation, Stanford University, in preparation (1993).