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.
Type de document :
[Research Report] RR-1810, INRIA. 1992
Liste complète des métadonnées

Contributeur : Rapport de Recherche Inria <>
Soumis le : mercredi 24 mai 2006 - 16:36:13
Dernière modification le : vendredi 16 septembre 2016 - 15:19:38
Document(s) archivé(s) le : dimanche 4 avril 2010 - 22:02:24



  • 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〉



Consultations de la notice


Téléchargements de fichiers