基于Petri网的并行程序分析与评价

摘要

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

目录

文摘

英文文摘

声明

1绪论

1.1课题的提出

1.2国内外研究现状

1.3本文的内容安排

2基本知识

2.1 Petri网的基本知识

2.2并行计算的基本知识

3基于时延变迁Petri网的并行程序的分析

3.1概述

3.2时延变迁Petri网

3.3并行程序性能模型

3.4数据并行问题的时延变迁Petri网分析

4时延变迁Petri网分布式模拟的先行性研究

4.1概述

4.2并行模拟原理

4.3并行模拟中逻辑进程先行性研究

4.4先行性在并行模拟中的应用

5关于Process-processor映射问题的研究

5.1概述

5.2任务图

5.3分割算法

6结束语

6.1本文的主要工作

6.2进一步的工作

致谢

参考文献

作者在读期间的研究成果