Insertion scheduling: An alternative to list scheduling for modulo schedulers | SpringerLink
Skip to main content
Springer Nature Link
Log in

Insertion scheduling: An alternative to list scheduling for modulo schedulers

  • Conference paper
  • First Online:
Languages and Compilers for Parallel Computing (LCPC 1995)

Part of the book series: Lecture Notes in Computer Science ((LNCS,volume 1033))

Abstract

The list scheduling algorithm is a popular scheduling engine used in most, if not all, industrial instruction schedulers. However this technique has several drawbacks, especially in the context of modulo scheduling. One such problem is the need to restart scheduling from scratch whenever scheduling fails at the current value of the initiation interval. Another problem of list scheduling is that the order in which the instructions are selected for scheduling is constrained to be a topological sort of the scheduling graph, minus the loop-carried dependencies.

We present a new instruction scheduling technique, suitable for block scheduling and modulo scheduling, which addresses these restrictions, while allowing efficient implementations. The technique is fully implemented, as part of a software pipeliner we developed for an experimental version of the Cray T3D ™ cft77 Fortran compiler.

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

Access this chapter

Log in via an institution

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

References

  1. T. L. Adam, K. M. Chandy, J. R. Dickson “A Comparison of List Schedules for Parallel Processing Systems” Communications of the ACM, Vol. 17, no. 12, Dec. 1974.

    Google Scholar 

  2. B. Dupont de Dinechin “StaCS: A Static Control Superscalar Architecture” MICRO-25 / 25th Annual International Symposium on Microarchitecture, Portland, Dec. 1992.

    Google Scholar 

  3. B. Dupont de Dinechin “An Introduction to Simplex Scheduling” PACT'94, Montreal, Aug. 1994.

    Google Scholar 

  4. B. Dupont de Dinechin “Simplex Scheduling: More than Lifetime-Sensitive Instruction Scheduling” PRISM research report 1994.22, available under anonymous ftp to ftp.prism.uvsq.fr, July 94.

    Google Scholar 

  5. B. Dupont de Dinechin “Fast Modulo Scheduling Under the Simplex Scheduling Framework” PRISM research report 1995.01, available under anonymous ftp to ftp.prism.uvsq.fr, Jan 95.

    Google Scholar 

  6. C. Eisenbeis, D. Windheiser “Optimal Software Pipelining in Presence of Resource Constraints” PaCT-93, Obninsk, Russia, Sept. 1993.

    Google Scholar 

  7. P. Feautrier “Fine-Grain Scheduling Under Resource Constraints” 7th Annual Workshop on Lang. and Compilers for Parallel Computing, LNCS, Ithaca, NY, Aug 1994.

    Google Scholar 

  8. F. Gasperoni, U. Schwiegelshohn “Scheduling Loops on Parallel Processors: A Simple Algorithm with Close to Optimum Performance” Parallel Processing: COMPAR'92-VAPP V, LNCS 634, June 1992.

    Google Scholar 

  9. R. Govindarajan, E. R. Altman, G. R. Gao “Minimizing Register Requirements under Resource-Constrained Rate-Optimal Software Pipelining” MICRO-27 / 27h Annual International Symposium on Microarchitecture, San Jose, Dec. 1994.

    Google Scholar 

  10. R. A. Huff “Lifetime-Sensitive Modulo Scheduling” Proceedings of the SIGPLAN'93 Conference on Programming Language Design and Implementation, Albuquerque, June 1993.

    Google Scholar 

  11. M. Lam “A Systolic Array Optimizing Compiler” Ph. D. Thesis, Carnegie Mellon University, May 1987.

    Google Scholar 

  12. B. R. Rau, C. D. Glaeser “Some Scheduling Techniques and an Easily Schedulable Horizontal Architecture for High Performance Scientific Computing” IEEE / ACM 14th Annual Microprogramming Workshop, Oct. 1981.

    Google Scholar 

  13. B. R. Rau “Iterative Modulo Scheduling: An Algorithm for Software Pipelining Loops” IEEE / ACM 27th Annual Microprogramming Workshop, San Jose, California, Nov. 1994.

    Google Scholar 

  14. M. D. Tiemann “The GNU Instruction Scheduler” Cygnus Technical Report, available at URL http://www.cygnus.com/library-dir.html, Jul 1989.

    Google Scholar 

  15. J. Wang, C. Eisenbeis “Decomposed Software Pipelining: a New Approach to Exploit Instruction Level Parallelism for Loop Programs” IFIP WG 10.3, Orlando, Florida, Jan. 1993.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Applied Mathematics, CEA Limeil-Valenton center, 94195, Villeneuve StGeorges cedex, France

    Benoît Dupont de Dinechin

Authors
  1. Benoît Dupont de Dinechin
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Chua-Huang Huang Ponnuswamy Sadayappan Utpal Banerjee David Gelernter Alex Nicolau David Padua

Rights and permissions

Reprints and permissions

Copyright information

© 1996 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Dupont de Dinechin, B. (1996). Insertion scheduling: An alternative to list scheduling for modulo schedulers. In: Huang, CH., Sadayappan, P., Banerjee, U., Gelernter, D., Nicolau, A., Padua, D. (eds) Languages and Compilers for Parallel Computing. LCPC 1995. Lecture Notes in Computer Science, vol 1033. Springer, Berlin, Heidelberg. https://doi.org/10.1007/BFb0014190

Download citation

  • DOI: https://doi.org/10.1007/BFb0014190

  • Published:

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-60765-6

  • Online ISBN: 978-3-540-49446-1

  • eBook Packages: Springer Book Archive

Publish with us

Policies and ethics

Search

Navigation