Skip to main content
SpringerLink
Log in

Using timed Petri net to model instruction-level loop scheduling with resource constraints

  • Published:
Journal of Computer Science and Technology Aims and scope Submit manuscript

Abstract

This paper uses timed Petri net to model and analyze the problem of instruction-level loop scheduling with resource constraints, which has been proven to be an NP complete problem. First, we present a new timed Petri net model to integrate functional unit allocation, register allocation and spilling into a unified theoretical framework. Then we develop a state subgraph, called Register Allocation Solution Graph, which can effectively describe the major behavior of our new model. The main property of this state subgraph is that the number of all its nodes is polynomial. finally we present and prove that the optimum loop schedules can be found with polynomial computation complexity, for almost all practical loop programs. Our work lightens a new idea of finding the optimum loop schedules.

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

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

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

Explore related subjects

Discover the latest articles, news and stories from top researchers in related subjects.

References

  1. A Aiken, A Nicolau. Perfect pipelining: A new loop parallelization technique. Research Report 87-873, Dept. of Computer Science, Cornell Univ., 1987.

  2. G S Almasi, A Gottlieb. Highly Pparallel Computing. The Benjamin/Cummings Publishing Company, Inc., 1989.

  3. F Bodinet al. Overview of a high-performance programmable pipeline architecture In: Proc. of ACM International Conference on Supercomputing, Crete, 1989.

  4. D G Bradleeet al. Integrating register allocation and instruction scheduling for RISCs. In: Proc Intl Conf ASPLOS, April 1991.

  5. J Carlieret al. Modelling scheduling problems with timed Petri nets. In: Advances in Petri Nets 1984.

  6. J Carlieret al. Timed Petri net schedules. In: Advances in Petri Nets 1988.

  7. A E Charlesworth. An approach to scientific array processing: The architecture design of the AP-120B/FPS-164 family.Computer, 1981, 9: 18–27.

    Article  Google Scholar 

  8. F Commoner, A W Holt Marked directed graphs.Journal of Computer and System Sciences, 1971, 5:511–523.

    MATH  MathSciNet  Google Scholar 

  9. C Eisenbeis. Optimization of horizontal microcode generation for loop structures. In: Proc of ACM International Conference on Supercomputing, Saint-Malo, France, 1988.

  10. C Eisenbeiset al. Compile-time optimization of memory usage on the CRAY-2. In: Proc. NATO Supercomputer Workshop, Trondheim, Norway, 1989.

  11. G R Gaoet al. A time Petri-net model for fine-grain loop scheduling. In: Proc of ACM SIGPLAN'91 Conference on PLDI, June, 1991.

  12. Q Ning, G R Gao. Optimal memory allocation for argument fetching dataflow machines. ACAPS Technical Memo 32, Mac Gill University, Montreal, Canada.

  13. C Hanen. Problemes D'Ordonnancement des architectures pipelines: Modelisation, optimisation, algorithmes. These de Doctorat de L'Universite Paris 6, 1987.

  14. C Hanen. Study of a NP-hard cyclic scheduling problem: The periodic recurrent job-shop. Research Rapport, Laboratoire MASI, Universite P. et M. Curie, 1991.

  15. M S Lam. Software pipelining: An effective scheduling technique for VLIW machine. In: Proc. SIGPLAN'88 Conference on PLDI, Atlanta, June, 1988.

  16. J L Peterson, Petri Net Theory and the Modeling of Systems. Prentice-Hall, Inc., Englewood Cliffs, NJ, 1981.

    Google Scholar 

  17. W Reisig. Petri Nets: An Introduction. Springer-Verlag, Berlin Heidelberg, 1985.

    MATH  Google Scholar 

  18. Bogong Su, Jian Wang. Loop-carried dependence and the general URPR software pipelining approach. Proc. 24th HAWAII International Conference on System Sciences, Kailua-Kona, Hawaii, Jan. 1991.

  19. R F Touzeau. A Fortran compiler for the FPS-164 scientific computer. In Proc ACM SIGPLAN Symposium on Compiler Construction, 1984.

  20. Jian Wang, Christine Eisenbeis. A new timed Petri net model for loop scheduling with resource constraints. INRIA Research Report, No. 1810, Dec. 1992.

  21. Jian Wang, Christine Eisenbeis, Philippe Canalda. Using time Petri net to analyze the maximum computation rate for loop programs. In: Proc of 3rd International Conference for Young Computer Scientists, Beijing, China, 1993.

Download references

Author information

Author notes

  1. Jian Wang

    Present address: Institut für Computersprachen, Technische Universität Wien, Argentinierstraße 8, A-1040, Wien, Austria

  2. Su Bogong (visiting professor)

    Present address: Dept. of Computer Science, The College of Staten Island, USA

Authors and Affiliations

  1. INRIA Rocquencourt, Domaine de Voluceau, BP 105, 78153, Le Chesnay Cedex, France

    Jian Wang, Christine Eisenbeis & Su Bogong (visiting professor)

Authors
  1. Jian Wang
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Christine Eisenbeis
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Su Bogong
    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

Wang, J., Eisenbeis, C. & Bogong, S. Using timed Petri net to model instruction-level loop scheduling with resource constraints. J. of Compt. Sci. & Technol. 9, 128–143 (1994). https://doi.org/10.1007/BF02939494

Download citation

  • Received:

  • Revised:

  • Issue Date:

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

Keywords

Search

Navigation