Skip to Main content Skip to Navigation
Reports

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 :
Reports
Complete list of metadata

https://hal.inria.fr/inria-00074862
Contributor : Rapport de Recherche Inria <>
Submitted on : Wednesday, May 24, 2006 - 4:36:13 PM
Last modification on : Thursday, February 11, 2021 - 2:50:07 PM
Long-term archiving on: : Sunday, April 4, 2010 - 10:02:24 PM

Identifiers

  • HAL Id : inria-00074862, version 1

Collections

Citation

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

Share

Metrics

Record views

120

Files downloads

195