The Study About Scheduling Question In Parallel And Distributed Computing Based On Petri Net

Scheduling question is modeled and analysised by Petri net in this paper. Various constraint conditions such as share resources being used in turn, buffer being requested or released, the precedence constraints among tasks being abided by in scheduling can be easily considerd using Petri net. The situation about parallel execution of tasks can be easily supervised using Petri net. Searching algorithm can be easily found in Petri net model.The questions about tasks grouping, communication and synchronization are considered in this paper. In order to obtain the scheme which is the lowest delay of communication among tasks and load balance among different processors, the task graph is partitioned. The target of task graph partition is to obtain the lowest weight of cut set which represents the quantity of communication of tasks and is to obtain weight balance among subdivisions of task graph which represents load balance among different processors. Of course, the question of graph partition is also NP-complete, the heuristic partition method which is taken forward by G Karypis is adopted in this paper.The concrete process about solving the question is as follows: Firstly, the task graph is partitioned so that the amount of communication among tasks is the lowest; Secondly, every task in the same task set which is the result of partition is allocated to the same processor or the the same local area net environment; Thirdly, different Petri net models are constructed respectively based on the different task sets. Lastly, the Petri net models are synthesize synchronously and the solution based on the Petri net state space is found. In order to allievate the complex degree of state space explosion, the synchronous reachable graph (SRG for a shot) is taken forward. The SRG only pictures the change of states which are brought by the firing of common transitions. The local reachable graph (LRG for a shot) is also taken forward in the paper. The LRG pictures the change of states which are brought by the firing of local transitions. In fact, the local states are irrelative each other, therefore the combination of local state is not needed. The LRG can be constructed in parallel.