The Analysis And Evaluation Of The Parallel Program Based On Petri Nets

Parallel program is an active research field presently, and it is also a difficult problem. To analyze and design parallel program, we have to face many problems which occur hardly in analyzing and designing serial program, including uncertainty, communication, synchronization, data partition and distribution, load balancing, tolerate fault, heterogeneity, sharing and distributed storage, deadlock, competition and so on. For these problems, using Petri net to describe the performance of parallel program is incomparable for other modeling methods.The main idea of this dissertation is to discuss how to use timed transition Petri net to analyze parallel program. Firstly, the author presents the basic transformation rules on transforming common parallel program into timed transition Petri net (TTPN), then using G.Chiola' s method to analyze TTPN model. As for data parallel problem, the author presents the TTPN model of a segment and the TTPN model involving several segments in logical process about parallel program. By analyzing the TTPN model of matrix multiplication algorithm, we simulate the multiplication problem of two 400x400 matrices in Dawning 2000, and compare the results gotten by this method with common inner production parallel algorithm. Secondly, we present the precise definition of lookahead based on A. Nketsa and N. B. Khalifaand' s idea in the literature [39]. As for TTPN, the author gives out the definition of no initial marking lookahead and having certain initial marking lookahead, and four basic architectures about the lookahead computation of TTPN. In order to compute no initial marking lookahead of TTPN, the author presents prediction graph algorithm. We use the lookahead to analyze TTPN, and give out the sufficient condition on existing concurrency in TTPN. According to the condition, we can partition parallel program into several logical processes. Finally, the author presents the denotation matrix of task graph, gives the partition algorithm that can decide quickly the mapping project on the mapping process-processor. Lots of experiments show that the algorithm is very effective.