Micropipelines

ABSTRACT

The pipeline processor is a common paradigm for very high speed computing machinery. Pipeline processors provide high speed because their separate stages can operate concurrently, much as different people on a manufacturing assembly line work concurrently on material passing down the line. Although the concurrency of pipeline processors makes their design a demanding task, they can be found in graphics processors, in signal processing devices, in integrated circuit components for doing arithmetic, and in the instruction interpretation units and arithmetic operations of general purpose computing machinery. Because I plan to describe a variety of pipeline processors, I will start by suggesting names for their various forms. Pipeline processors, or more simply just pipelines, operate on data as it passes along them. The latency of a pipeline is a measure of how long it takes a single data value to pass through it. The throughput rate of a pipeline is a measure of how many data values can pass through it per unit time. Pipelines both store and process data; the storage elements and processing logic in them alternate along their length. I will describe pipelines in their complete form later, but first I will focus on their storage elements alone, stripping away all processing logic. Stripped of all processing logic, any pipeline acts like a series of storage elements through which data can pass. Pipelines can be clocked or event-driven, depending on whether their parts act in response to some widely-distributed external clock, or act independently whenever local events permit. Some pipelines are inelastic; the amount of data in them is fixed. The input rate and the output rate of an inelastic pipeline must match exactly. Stripped of any processing logic, an inelastic pipeline acts like a shift register. Other pipelines are elastic; the amount of data in them may vary. The input rate and the output rate of an elastic pipeline may differ momentarily because of internal buffering. Stripped of all processing logic, an elastic pipeline becomes a flow-through first-in-first-out memory, or FIFO. FIFOs may be clocked or event-driven; their important property is that they are elastic. I assign the name micropipeline to a particularly simple form of event-driven elastic pipeline with or without internal processing. The micro part of this name seems appropriate to me because micropipelines contain very simple circuitry, because micropipelines are useful in very short lengths, and because micropipelines are suitable for layout in microelectronic form. I have chosen micropipelines as the subject of this lecture for three reasons. First, micropipelines are simple and easy to understand. I believe that simple ideas are best, and I find beauty in the simplicity and symmetry of micropipelines. Second, I see confusion surrounding the design of FIFOs. I offer this description of micropipelines in the hope of reducing some of that confusion. The third reason I have chosen my subject addresses the limitations imposed on us by the clocked-logic conceptual framework now commonly used in the design of digital systems. I believe that this conceptual framework or mind set masks simple and useful structures like micropipelines from our thoughts, structures that are easy to design and apply given a different conceptual framework. Because micropipelines are event-driven, their simplicity is not available within the clocked-logic conceptual framework. I offer this description of micropipelines in the hope of focusing attention on an alternative transition-signalling conceptual framework. We need a new conceptual framework because the complexity of VLSI technology has now reached the point where design time and design cost often exceed fabrication time and fabrication cost. Moreover, most systems designed today are monolithic and resist mid-life improvement. The transition-signalling conceptual framework offers the opportunity to build up complex systems by hierarchical composition from simpler pieces. The resulting systems are easily modified. I believe that the transition-signalling conceptual framework has much to offer in reducing the design time and cost of complex systems and increasing their useful lifetime. I offer this description of micropipelines as an example of the transition-signalling conceptual framework. Until recently only a hardy few used the transition-signalling conceptual framework for design because it was too hard. It was nearly impossible to design the small circuits of 10 to 100 transistors that form the elemental building blocks from which complex systems are composed. Moreover, it was difficult to prove anything about the resulting compositions. In the past five years, however, much progress has been made on both fronts. Charles Molnar and his colleagues at Washington University have developed a simple way to design the small basic building blocks [9]. Martin Rem's "VLSI Club" at the Technical University of Eindhoven has been working effectively on the mathematics of event-driven systems [6, 10, 11, 19]. These emerging conceptual tools now make transition signalling a lively candidate for widespread use.

REFERENCES

• 1: Chaney, T.J., and Mo lnar, C.E. Anomalous behavior of synchronizer and arbiter circuits, i EEI:: Trans. Comput. C-22, 4 (Apr. 1973), 421- 422.
• 2: Clark, W.A. Macrom~dular computer systems. In Proceedings of the Spring Joint Computer Conference, AFIPS, April 1967,
• 3: Clark, W.A., and Molnar. C.E. Macromodular computer systems. Computers in Biomedi:al Research, Vol. 4, R. Stacy and B. Waxman, Eds., Academic Pres:, New York, 1974, 45-85.
• 4: W. J. Dally , C. L. Seitz, Deadlock-free message routing in multiprocessor interconnection networks, IEEE Transactions on Computers, v.36 n.5, p.547-553, May 1987 [doi>10.1109/TC.1987.1676939]
• 5: David L. Dill , Steven M. Nowick , Robert F. Sproull, Specification and automatic verification of self-timed queues, Stanford University, Stanford, CA, 1989
• 6: Ebergen, J.C. Translating programs into delay-insensitive circuits. Ph.D. dissertation, EJndhoven University of Technology, 1987.
• 7: Levy, J.V. Buses, the skeleton of computer structures. In Computer Engineering, C.G. Bell, J.C. Mudge, and J.E. McNamara, Eds., Digital Press, 1978.
• 8: Miller, R.E. "Sequenl ial Circuits", Chapter I0, In Switching Theory, Vol 2, Wiley, NY, 19,35.
• 9: Molnar, C.E., Fang, 'I'.P., and Rosenberger, F.U. Synthesis of delayinsensitive modules. In Proceedings of the 1985 Chapel Hill Conference on VLSI, H. Fuchs, E~I., Computer Science Press, 1985.
• 10: Rem, M., van de Snepscheut, J.L.A., and Udding, J.T. Trace theory and the definition of hierarchical components. In Proceedings of the Caltech Conference on VLSI, 1983.
• 11: M Rem, Trace theory and systolic computations, Volume I: Parallel architectures on PARLE: Parallel Architectures and Languages Europe, p.14-33, March 1987, Eindhoven, The Netherlands
• 12: F. U. Rosenberger , C. E. Molnar , T. J. Chaney , T.-P. Fang, Q-Modules: Internally Clocked Delay-Insensitive Modules, IEEE Transactions on Computers, v.37 n.9, p.1005-1018, September 1988 [doi>10.1109/12.2252]
• 13: Seitz, C.L. System Timing. In Introduction to VLSI Systems, C.A. Mead and L.A. Conway, Eds., Addison-Wesley, 1980.
• 14: Sproull, R.F., and Sutherland, I.E. A clipping divider. FJCC 1968, Thompson Books, Washington, D.C., 765.
• 15: Ivan E. Sutherland , Gary W. Hodgman, Reentrant polygon clipping, Communications of the ACM, v.17 n.1, p.32-42, Jan. 1974 [doi>10.1145/360767.360802]
• 16: Sutherland, I.E. Asynchronous queue system, U.S. Patent 4,679,213, July 7, 1987.
• 17: Sutherland, I.E., Asynchronous first-in-first-out register structure. US Patent Pending.
• 18: Sutherland, I.E. Asynchronous pipelined data processing system. US Patent pending.
• 19: Udding, J.T. A formal model for defining assifying delay-insensitive circuits and systems. J. Distrib. Comptg. 1, 1986, 197-2(14.

INDEX TERMS

Primary Classification:
  B. Hardware
  B.5 REGISTER-TRANSFER-LEVEL IMPLEMENTATION
      B.5.1 Design
          Subjects: Control design

Additional Classification:
  B. Hardware
  B.1 CONTROL STRUCTURES AND MICROPROGRAMMING
      B.1.1 Control Design Styles
          Subjects: Hardwired control**
  B.5 REGISTER-TRANSFER-LEVEL IMPLEMENTATION
      B.5.1 Design
          Subjects: Styles (e.g., parallel, pipeline, special-purpose); Data-path design
  B.7 INTEGRATED CIRCUITS
      B.7.1 Types and Design Styles
          Subjects: VLSI (very large scale integration)

General Terms:
Design, Performance