A microprogramming support tool for pipelined architectures

ABSTRACT

We describe a software tool to aid the development of microcode for horizontal, pipelined architectures. The tool is a preprocessor for microcode source that allows the programmer full flexibility to optimize code, but removes many of the tedious and error-prone aspects of microprogramming. It automatically allocates floating-point registers, expands complex instructions, and analyzes code for pipeline-related errors. We have written a working version of the tool for the Weitek XL-8032 floating-point chip set, a horizontal architecture with pipelined sequencer and floating-point datapaths. Although the tool was designed for the XL architecture, the algorithms used are applicable to other parallel/pipelined architectures. This paper argues for the existence of such tools, summarizes the algorithms needed to analyze control and data flow in the presence of pipelining, and characterizes the tool's performance based on nine microcoded routines written for a real-time 3-D graphics system.

REFERENCES

• 1: Alfred V. Aho , Ravi Sethi , Jeffrey D. Ullman, Compilers: principles, techniques, and tools, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1986
• 2: A. Aiken , A. Nicolau, A Development Environment for Horizontal Microcode, IEEE Transactions on Software Engineering, v.14 n.5, p.584-594, May 1988 [doi>10.1109/32.6136]
• 3: G. J. Chaitin, M. A. Auslander, A. K. Chandra, J. Cocke. M. E. Hopkins. and P. W. Markstein, "Register allocation via coloring," Comput. Lang., vol. 6, pp. 47-57, 1981.
• 4: C. Cheung, S. Molnar, M. Surles, and R. Snodgrass, "MAXL: A microcode development tool for the Weitek XL-8032," Technical Report (forthcoming), Computer Science Dept., Univ. of North Carolina at Chapel Hill, Chapel Hill, NC.
• 5: John Eyles , John Austin , Henry Fuchs , Trey Greer , John Poulton, Pixel-Planes 4: A Summary, Advances in Computer Graphics Hardware II (Eurographics'87 Workshop), p.183-207, January 1988
• 6: J. A. Fisher, "Trace scheduling: A technique for global microcode compaction," IEEE Trans. Comput., vol. C-30, no. 7, pp. 478490, July 1981.
• 7: R. A. Mueller , M. R. Duda , P. H. Sweany , J. S. Walicki, Horizon: A Retargetable Compiler for Horizontal Microarchitectures, IEEE Transactions on Software Engineering, v.14 n.5, p.575-583, May 1988 [doi>10.1109/32.6135]
• 8: Richard Snodgrass, The interface description language: definition and use, Computer Science Press, Inc., New York, NY, 1989
• 9: Steven Roger Vegdahl, Local code generation and compaction in optimizing microcode compilers, 1982
• 10: Weitek Corporation, XL-Series Hardware Designer's Guide. Weitek Corporation, Sunnyvale, CA 94086, December 1987.

INDEX TERMS

Primary Classification:
  B. Hardware
  B.1 CONTROL STRUCTURES AND MICROPROGRAMMING

Additional Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.2 Multiple Data Stream Architectures (Multiprocessors)
          Subjects: Pipeline processors**

General Terms:
Algorithms, Design, Languages, Performance