HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation

A New timed Petri net model for loop scheduling with resource constraints

Abstract : This report 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 loop scheduling, functional unit allocation, register allocation and spilling into a unified theoretical framework. Secondly, we theoretically discuss the schedulability of our model. Thirdly, 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 a timed Petri net based loop scheduling approach with polynomial computation complexity, by which the optimum loop schedules can be found under resource constraints for almost all practical loop programs.
Document type :
Complete list of metadata

Contributor : Rapport de Recherche Inria Connect in order to contact the contributor
Submitted on : Wednesday, May 24, 2006 - 4:36:13 PM
Last modification on : Friday, February 4, 2022 - 3:18:45 AM
Long-term archiving on: : Sunday, April 4, 2010 - 10:02:24 PM


  • HAL Id : inria-00074862, version 1



Jian Wang, Christine Eisenbeis. A New timed Petri net model for loop scheduling with resource constraints. [Research Report] RR-1810, INRIA. 1992. ⟨inria-00074862⟩



Record views


Files downloads