【作者】 方贤文；

【导师】 吴哲辉；

【作者基本信息】 山东科技大学 ， 计算机软件与理论， 2004， 硕士

【摘要】 并行程序目前是一个活跃的研究领域，也是一个困难问题。在进行并行程序的分析和设计过程中，必须面对不确定性、通信、同步、数据划分和分配、负载平衡、容错、异构、共享或分布存储、死锁及竞争等问题，这些问题在串行程序的分析和设计中是很少遇到的。针对这些问题，用Petri网来分析并行程序的性能是其它模型无法比拟的。 本文的主要工作是借助时延变迁Petri网来分析并行程序，首先给出了一般并行程序转化为TTPN的基本转换规则，对TTPN模型采用G.Chiola的方法进行分析。对于数据并行问题，提出了并行程序逻辑进程中一个块的TTPN模型以及包含多个块的循环的TTPN模型。通过分析矩阵乘法算法的TTPN模型，在曙光2000并行机上对两个400×400矩阵相乘的问题进行了模拟，并与一般内积并行算法的运行结果作了比较。然后，基于A.Nketsa和N.B.Khalifa在文献中提出的先行值概念，我们给出了先行值的确切定义。结合TTPN，本文给出了无初始标识先行值和有确定初始标识先行值的定义，以及先行值计算的四种基本结构。为了求无初始标识先行值，提出了预测图算法。我们用先行值来分析TTPN，给出了存在并发的充分条件，为并行程序分成多个逻辑进程提供了依据。最后提出了任务图表示矩阵，对进程到处理器的映射问题给出了分割算法，这个算法能够快速确定进程到处理器的映射方案。通过大量的实验，证明这个算法是很有效的。更多还原

【Abstract】 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.更多还原