Petri网可达图的并行算法

摘要

死锁是柔性制造系统必须考虑和解决的问题。由于Petri网具有可以检测死锁并建立死锁控制策略来处理死锁的能力,它们适合建模和控制FMS系统中的死锁问题。可达图反映了一个网系统的所有动态行为,这使得它成为Petri网死锁控制的一种重要分析技术。可是,一个Petri网可达图的规模和网结构及其初始标识的大小成指数关系。这使得枚举网的所有可达状态变得困难,同时也是非常耗时的。
　　 论文致力于Petri网可达图的并行算法。传统的方法计算规模大的Petri网时经常遇到两个问题:过长的计算时间和内存溢出。为了克服以上问题,本文利用并行算法求解一个给定网的所有可达状态,并通过一些例子验证了该算法的高效性。在论文中,主要做了三方面的工作。
　　 1.单进程的算法求出一个Petri网的所有可达状态。这个算法比传统的算法在求解所有可达状态有更高的效率。
　　 2.多进程计算Petri网所有可达状态。由于每个进程在一台独立的计算机上执行任务,因此总的计算效率显然提高了并且计算时间明显减少。
　　 3.由于每个进程都存储了所有的可达标识,使得并行算法可能会产生内存溢出问题。因此,为了克服内存溢出,可达标识被划分成不同的集合并且每个进程存储集合中的一个。这样,这个算法求解效率很高并且能够处理规模大的Petri网。

目录

文摘

英文文摘

第一章 绪论

1.1 研究背景与意义

1.1.1 Petri网简介

1.1.2 死锁和基于区域理论控制方法所产生的问题

1.2 本文完成的主要工作

第二章 Petri网的基本理论

2.1 Petri网的基本定义

2.2 Petri网变迁的发射规则

2.3 Petri网的可达图

第三章 并行算法的基本理论

3.1 并行算法的基本知识

3.1.1 并行问题的求解模型图

3.1.2 并行计算机的类型

3.1.3 并行算法分类

3.2 MPI的基本知识理论

3.2.1 MPI的六个基本函数介绍

3.2.2 MPI消息发射规则

3.2.3 MPI的通信分类

3.2.4 避免死锁的通信调用次序

3.2.5 计算π的MPI程序

第四章 Petri网可达图并行算法

4.1 Petri网可达图串行算法分析

4.1.1 可达图的串行程序分析

4.1.2 并行粒度粗细问题

4.2 Petri网可达图并行算法

4.2.1 可达图的并行算法

4.2.2 可达图的改进并行算法

4.2.3 分配存储标识的并行算法

4.3 三种算法的并行程度的比较

第五章 可达图并行算法的实验结果与分析

5.1 并行环境的设置和配置

5.1.1 机群系统的原理和技术

5.1.2 硬件的选择和安装

5.1.3 系统的构建

5.1.4 机群系统配置如下:

5.1.5 软件的选择和安装

5.2 并行算法性能分析

5.2.1 加速系数

5.2.2 并行算法中通信时间分析

5.3 Petri网可达图并行算法的测试结果

5.3.1 Petri网可达图并行算法4.2与INA的测试结果

5.3.2 分析算法4.3与INA的测试结果

第六章 总结

致谢

参考文献

附录 A PNT文件