High-level microprogramming: an optimizing C compiler for a processing element of a CAD accelerator

ABSTRACT

The development of a high-level language compiler for a micro-programmable processing element (PE) in the MARS multicomputer is described. MARS, an MIMD message passing machine, was designed to speed up VLSI CAD and similar other non-numerical applications. The need for support of a high-level language at the PE level of a multicomputer is considered, and the choice of C as an appropriate programming language is justified. Special features found in VLSI processors are examined along with compiler support for them. Conventional retargetable compiler techniques are shown to be inadequate for the highly concurrent micro-programmable PE. These techniques must be extended for microcode generation. The design of the MARS compiler is outlined. Performance data is provided to evaluate the benefit of various compiler optimizations, and to compare compiler generated microcode to hand generated microcode in terms of space and time performance

REFERENCES

• 1: S. Abraham and K. Pedmanabhan. Instruction reorganisation for a variable-length pipelined microprocessor. In IEEE International Conference on Computer Derign, volume ICCD-88, 1988.
• 2: D. P. AgrawaI and J. Mauney. Structure of a paraIlehsing compiler fo:c the B-HIVE multicomputer. In Microrocesring and Microprogramming. North-Holland, 1988.
• 3: P. Agrawd, V. AgrawaI, and K. T. Cheng. Fault simulation in a pipelined multiprocessor system. In Proceedings of the IEEE International Test Conference, volume ITC-89, pages 727-734, 1989.
• 4: P. Agrawd and W. J. Dally. A hardware logic simulation system. IEEE Transactions on Computer-Aided Design, 9(1):19-29, January 1990.
• 5: P. Agrawd et al. MARS: A multiprocessorbased programmable accelerator. IEEE Design & Test of Computers, 4(5):28-36, October 1987.
• 6: Alfred V. Aho , Ravi Sethi , Jeffrey D. Ullman, Compilers: principles, techniques, and tools, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1986
• 7: A. Aiken , A. Nicolau, A development environment for horizontal microcode programs, Proceedings of the 19th annual workshop on Microprogramming, p.23-31, October 15-17, 1986, New York, New York, United States
• 8: R. Allen , S. Johnson, Compiling C for vectorization, parallelization, and inline expansion, Proceedings of the ACM SIGPLAN 1988 conference on Programming Language design and Implementation, p.241-249, June 20-24, 1988, Atlanta, Georgia, United States
• 9: Richard P. Atkins, Improved instruction formation in the exhaustive local microcode compaction algorithm, Proceedings of the 17th annual workshop on Microprogramming, p.105-111, December 1984
• 10: D. K. Banerji and J. Raymond. Elements of Micro-Programming. Prentice-Hall Inc., Englewood Cliffs, NJ, 1982.
• 11: S. Chatterjee and P. Agrawd. Connected speech recognition on a multiple processor pipeline. In Proceedings of the IEEE International Conference on Acourticr, Speech, and Signal Processing, 1989.
• 12: John R. Ellis, Bulldog: a compiler for VLSI architectures, MIT Press, Cambridge, MA, 1986
• 13: J. Fisher. Trace scheduling: a technique for global microcode compaction. IEEE Transactions on Computers, C-30(7):478-490, July 1981.
• 14: C. W. Fraser, A language for writing code generators, Proceedings of the ACM SIGPLAN 1989 Conference on Programming language design and implementation, p.238-245, June 19-23, 1989, Portland, Oregon, United States
• 15: C. W. Fraser , A. L. Wendt, Automatic generation of fast optimizing code generators, Proceedings of the ACM SIGPLAN 1988 conference on Programming Language design and Implementation, p.79-84, June 20-24, 1988, Atlanta, Georgia, United States
• 16: R. Gurd. Experience developing microcode using a high level language. In Proceedings Micro- 16, 1983.
• 17: W. C. Hopkins , M. J. Horton , C. S. Arnold, Target-independent high-level microprogramming, Proceedings of the 18th annual workshop on Microprogramming, p.137-144, December 03-06, 1985, Pacific Grove, California, United States
• 18: M. Lam, Software pipelining: an effective scheduling technique for VLIW machines, Proceedings of the ACM SIGPLAN 1988 conference on Programming Language design and Implementation, p.318-328, June 20-24, 1988, Atlanta, Georgia, United States
• 19: Monica S. Lam, A Systolic Array Optimizing Compiler, Kluwer Academic Publishers, Norwell, MA, 1989

INDEX TERMS

Keywords:
code generation, front-end DAG compiler, hand vs. compiled microcode, hardware accelerator, microcode compiler, performance data, programming environment for CAD, space/time overhead