Using Timed Petri Net to Model Instruction-Level Loop Scheduling with Resource Constraints

This paper uses timed petri net to model and analyze the problem of instructionlevel 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.

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

This paper uses timed Petri net to model and analyze the problem of instructionlevel 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 ilno 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 maill 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 prograrns. Our work lightens a new idea of finding the optimum loop schedules.