Skip to main content
SpringerLink
Log in

Optimization of Machine Descriptions for Efficient Use

  • Published:
International Journal of Parallel Programming Aims and scope Submit manuscript

Abstract

A machine description facility allows compiler writers to specify machine execution constraints to the optimization and scheduling phases of an instructionlevel parallelism (ILP) optimizing compiler. The machine description (MDES) facility should support quick development and easy maintenance of machine execution constraint descriptions by compiler writers. However, the facility should also allow compact representation and efficient usage of the MDES during compilation. This paper advocates a model that allows compiler writers to develop the MDES in a high-level language, which is then translated into a low-level representation for efficient use by the compiler. The discrepancy between the requirements of the high-level language and the low-level representation is reconciled with a collection of transformations that derive efficient lowlevel representations from the easy-to-understand high-level descriptions. In order to support these transformations, a novel approach to representing machine execution constraints has been developed. Detailed and precise descriptions of the execution constraints for the HP PA7100, Intel Pentium, SUN SuperSPARC, and AMD-K5 processors, as well as two hypothetical wider-issue processor configurations, are analyzed to show the advantage of using this new representation. The results show that performing these transformations and utilizing the new representation allow easy-to-maintain detailed descriptions written in high-level languages to be efficiently used by ILP-optimizing compilers.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

REFERENCES

  1. J. C. Dehnert and R. A. Towle, Compiling for the Cydra 5, J. Supercomputing, 7:181–227 (January 1993).

    Google Scholar 

  2. P. G. Lowney, S. M. Freudenberger, T. J. Karzes, W. D. Lichtenstein, R. P. Nix, J. S. O'Donnell, and J. C. Ruttenberg, The multiflow trace scheduling compiler, J. Supercomputing, 7:51–142 (January 1993).

    Google Scholar 

  3. J. C. Gyllenhaal, An efficient framework for performing execution-constraint-sensitive transformations that increase instruction-level parallelism, Ph.D. Thesis, Department of Electrical and Computer Engineering, University of Illinois, Urbana, Illinois (1997).

    Google Scholar 

  4. J. C. Gyllenhaal, B. R. Rau, and W. W. Hwu, Hmdes version 2.0 specification, Technical Report IMPACT-96–3, The IMPACT Research Group, University of Illinois, Urbana, Illinois (1996).

    Google Scholar 

  5. J. C. Gyllenhaal, A machine description language for compilation, Master's Thesis, Department of Electrical and Computer Engineering, University of Illinois, Urbana, Illinois (1994).

    Google Scholar 

  6. P. P. Chang, S. A. Mahlke, W. Y. Chen, N. J. Warter, and W. W. Hwu, IMPACT: An architectural framework for multiple-instruction-issue processors, Proc. 18th Int. Symp. Computer Archit., pp. 266–275 (June 1991).

  7. R. A. Bringmann, Compiler-controlled speculation, Ph.D. Thesis, Department of Computer Science, University of Illinois, Urbana, Illinois (1995).

    Google Scholar 

  8. E. S. Davidson, L. E. Shar, A. T. Thomas, and J. H. Patel, Effective control for pipelined computers, Spring COMPCON'75 Digests, pp. 181–184 (February 1975).

  9. G. Blanck and S. Krueger, The superSPARC microprocessor, COMPCON Spring, pp. 136–141 (1992).

  10. P. H. Winston, Artificial Intelligence, Addison-Wesley, Reading, Massachusetts (1984).

    Google Scholar 

  11. T. Asprey, G. S. Averill, E. DeLano, R. Mason, B. Weiner, and J. Yetter, Performance features of the PA7100 microprocessor, IEEE Micro, pp. 22–35 (June 1993).

  12. Intel, The Pentium Microprocessor, Santa Clara, California (1993).

  13. Dave Christie, Developing the AMD-K5 architecture, IEEE Micro, pp. 16–26 (April 1996).

  14. B. R. Rau, Iterative modulo scheduling: An algorithm for software pipelining loops, Proc. 27th Ann. Int. Symp. Microarchit., pp. 63–74 (November 1994).

  15. A. Aho, R. Sethi, and J. Ullman, Compilers: Principles, Techniques, and Tools, Addison-Wesley, Reading, Massachusetts (1986).

    Google Scholar 

  16. R. L. Kleir, A representation for the analysis of microprogram operation, Proc. Seventh Ann. Workshop Microprogr. (September 1974).

  17. D. J. DeWitt, A control-word model for detecting conflicts between microprograms, Proc. Eighth Ann. Workshop Microprogr. (September 1975).

  18. J. A. Fisher, The optimization of horizontal microcode within and beyond basic blocks; An application of processor scheduling with resources. Ph.D. Thesis, New York University (1979).

  19. P. M. Kogge, The Architecture of Pipelined Computers, McGraw-Hill, New York (1991).

    Google Scholar 

  20. A. E. Eichenberger and E. S. Davidson, A reduced multipipeline machine description that preserves scheduling constraints, Proc. Confer. Progr. Lang. Design and Implementation, pp. 12–20 (May 1996).

  21. S. A. Mahlke, W. Y. Chen, J. C. Gyllenhaal, W. W. Hwu, P. P. Chang, and T. Kiyohara, Compiler code transformations for superscalar-based high-performance systems, Proc. Supercomputing, pp. 808–817 (November 1992).

  22. S. A. Mahlke, Exploiting Instruction Level Parallelism in the Presence of Conditional Branches, Ph.D. Dissertation, Department of Electrical and Computer Engineering, University of Illinois, Urbana, Illinois (1996).

    Google Scholar 

  23. M. Schlansker, V. Kathail, and S. Anik, Height reduction of control recurrences for ILP processors, Proc. 27th Int. Symp. Microarchit., pp. 40–51 (December 1994).

  24. W. W. Hwu, R. E. Hank, D. M. Gallagher, S. A. Mahlke, D. M. Lavery, G. E. Haab, J. C. Gyllenhaal, and D. I. August, Compiler technology for future microprocessors, Proc. IEEE, 83(12):1625–1640 (December 1995).

    Google Scholar 

  25. D. M. Gallagher, W. Y. Chen, S. A. Mahlke, J. C. Gyllenhaal, and W. W. Hwu, Dynamic memory disambiguation using the memory conflict buffer, Proc. Sixth Int. Conf. Archit. Support Progr. Lang. Oper. Syst., pp. 183–193 (October 1994).

  26. T. A. Proebsting and C. W. Fraser, Detecting pipeline structural hazards quickly, 21st Ann. ACM SIGPLAN-SIGACT Symp. Principles of Progr. Lang., pp. 280–286 (January 1994).

  27. T. Müller, Employing finite automata for resource scheduling, Proc. 26th Ann. Int. Symp. Microarchit., pp. 12–20 (December 1993).

  28. V. Bala and N. Rubin, Efficient instruction scheduling using finite state automata, Int. J. Parallel Progr., pp. 53–82 (April 1997).

Download references

Authors
  1. John C. Gyllenhaal
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Wen-Mei W. Hwu
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. B. Ramakrishna Rau
    View author publications

    You can also search for this author in PubMed Google Scholar

Rights and permissions

Reprints and permissions

About this article

Cite this article

Gyllenhaal, J.C., Hwu, WM.W. & Rau, B.R. Optimization of Machine Descriptions for Efficient Use. International Journal of Parallel Programming 26, 417–447 (1998). https://doi.org/10.1023/A:1018750515365

Download citation

  • Issue Date:

  • DOI: https://doi.org/10.1023/A:1018750515365

Search

Navigation