Petri网并行化理论与并行算法

Petri网是复杂系统运行过程中并发、互斥、同步最直接、自然和准确的表示，已成为描述物理世界的异步并发现象并揭示其可计算规律的重要理论和模型。由于Petri网系统具有并发、同步的特点，同时存在状态空间爆炸的问题，要借助Petri网模拟复杂系统的并行运行或动画演示，以实现对Petri网系统行为与功能的分析与验证，成为人们亟须解决的问题。以并行计算和Petri网系统并行化为核心的Petri网系统并行算法成为模拟复杂系统的并行运行和系统验证的研究热点，受到许多学科领域的关注。本书全面系统地介绍Petri网并行化的基本理论和方法，重点介绍Petri网并行化划分理论和并行算法、Petri网的研究现状和国内外的新发展。本书可供分布式并行计算、Petri网、系统工程、柔性制造、很优化问题、演化计算、数据挖掘、工作流、交通网络、高性能计算等专业领域的研究人员阅读，也可供研究生及高年级本科生参考。

前言
第1章 Petri网并行化的研究背景 1
1.1 Petri网的研究现状 1
1.2 Petri网并行化理论与关键技术问题 5
1.3 基于多核机群的功能并行算法 5
1.4 Petri网的并行计算 6
1.5 基于多核机群的Petri网并行算法的研究思路 8
参考文献 11
第2章 MPI+OpenMP+STM并行编程模型 17
2.1 并行计算机的分类 17
2.1.1 按指令流和数据流分类 17
2.1.2 按数据的存储方式分类 18
2.2 并行计算模型 20
2.2.1 并行计算模型的要素 20
2.2.2 共享存储并行计算模型 20
2.2.3 分布式存储并行计算模型 21
2.2.4 存储层次并行计算模型 22
2.3 并行程序设计 23
2.3.1 并行编程模型 23
2.3.2 共享变量编程模型 24
2.3.3 消息传递编程模型 27
2.3.4 多线程编程和多进程编程 28
2.4 多核机群的并行计算 29
2.4.1 MPI+OpenMP混合编程模式 29
2.4.2 MPI+OpenMP+STM三级混合编程模式 31
2.4.3 MPI+OpenMP+STM并行算法 34
2.5 基于多核PC的人工蜂群并行算法 35
2.5.1 ABC算法 36
2.5.2 改进的ABC算法 36
2.5.3 并行算法的分析与设计 38
2.5.4 实验结果与分析 40
2.6 基于多核机群的人工鱼群并行算法 44
2.6.1 相关工作 44
2.6.2 基于动态权衡与小生境技术的串行式AFSA 46
2.6.3 基于MPI+OpenMP的人工鱼群并行算法实现 47
2.6.4 实验结果与分析 50
2.7 基于多核机群的混合群智能并行算法 54
2.7.1 相关工作 55
2.7.2 混合群智能两阶段处理方法 59
2.7.3 MPI+OpenMP+STM并行模型 60
2.7.4 混合群智能并行算法 63
2.7.5 实验环境及参数设置 64
2.7.6 实验结果与分析 65
参考文献 68
第3章 Petri网系统的数学模型 74
3.1 Petri网的基本概念 74
3.2 Petri网系统分析方法 79
3.3 Petri网的图形结构模型 82
3.4 Petri网的代数模型 85
参考文献 88
第4章 Petri网系统并行化预处理 89
4.1 Petri网的选择 89
4.1.1 高级Petri网与P/T网的特点 90
4.1.2 高级Petri网与P/T网的内在机理 90
4.2 结构模型的转化方法 90
4.3 代数模型的并行化预处理方法 92
4.3.1 转换过程与验证 92
4.3.2 P/T网与颜色Petri网的形式化表示 94
4.3.3 颜色Petri网关联矩阵分析 95
4.3.4 颜色Petri网并行化预处理自动转换算法 96
4.3.5 颜色Petri网转换成P/T网的算法 96
4.4 实验结果与分析 97
4.5 谓词/变迁网转换成P/T网的方法 98
参考文献 100
第5章 P-不变量求解算法与T-图子网划分方法 102
5.1 P-不变量求解 102
5.1.1 Petri网的形式化过程 102
5.1.2 P-不变量的求解过程 102
5.1.3 P-不变量及其支集的求解算法 105
5.1.4 实验结果与分析 106
5.2 T-图的求解方法 107
5.2.1 T-图的定义 107
5.2.2 T-图的求解算法 110
5.2.3 算法的形式化 111
5.2.4 T-图划分的应用示例 112
5.2.5 实验结果与分析 113
参考文献 113
第6章 Petri网系统并行化子网划分理论 115
6.1 Petri网并行化子网划分方法比较 115
6.1.1 基于P-不变量的子网划分条件 115
6.1.2 两种划分方法的分析与评价 117
6.2 Petri网并行进程划分的判定定理 118
6.3 Petri网并行化进程划分的完备性理论 120
6.3.1 子网库所标识全为零的情况 120
6.3.2 子网间存在共享库所的情况 122
6.3.3 无法划分为并行子网的情况 124
6.3.4 子网划分的完备性定理 126
6.4 Petri网并行化子网划分算法 126
6.5 Petri网并行化子网划分算法的应用 127
6.5.1 ATM存取款系统转换成P/T网模型 127
6.5.2 各种高级Petri网模型子网划分实例 128
6.5.3 实验结果与分析 128
6.6 Petri网的并行性分析 132
6.6.1 Petri网子网内部的并行性分析 132
6.6.2 Petri网子网之间的并行性分析 133
6.7 消息传递平台的Petri网系统并行算法 133
6.8 Petri网系统并行算法的验证 134
参考文献 135
第7章 多核机群的Petri网并行模型及其算法 136
7.1 Petri网的并行模型 136
7.1.1 引言 136
7.1.2 Petri网并行几何模型 137
7.1.3 Petri网并行代数模型 139
7.2 基于多核PC的Petri网并行算法 140
7.2.1 基于多核PC的多线程编程模式 140
7.2.2 基于多核PC的多线程Petri网并行算法 141
7.2.3 应用示例与顺序程序 141
7.2.4 基于多核PC的Petri网并行算法流程分析 144
7.2.5 基于多核PC的Petri网并行算法伪代码 145
7.2.6 并行算法与实例验证 147
7.3 基于多核机群的Petri网并行模型 148
7.4 多核机群的Petri网并行算法 150
7.4.1 多核机群的Petri网并行子网划分算法 151
7.4.2 基于多核机群的Petri网并行算法 151
7.4.3 实例分析 153
7.4.4 实验环境 160
7.4.5 串行实验结果 161
7.4.6 MPI实验结果 162
7.4.7 OpenMP实验结果 163
7.4.8 MPI+OpenMP+STM实验结果 164
7.4.9 实验结果与分析 165
参考文献 166
第8章 工作流Petri网系统的并行算法 169
8.1 国内外研究现状及发展趋势 169
8.1.1 引言 169
8.1.2 国外研究现状 170
8.1.3 国内研究现状 170
8.1.4 存在的不足 171
8.2 工作流概述 171
8.3 工作流模型与Petri网的映射关系 172
8.4 基于Petri网的工作流模型建模 173
8.5 工作流基本模式的Petri网模型及其并行性分析 173
8.5.1 工作流基本模式的Petri网模型 173
8.5.2 工作流Petri网并行模型 178
8.6 基于多核PC的工作流并行算法 180
8.7 算法应用与实验分析 181
8.7.1 工作流实例 181
8.7.2 实例的Petri网建模 183
8.7.3 系统的性能分析结果 185
8.7.4 实例的求解过程 185
8.7.5 基于多核PC的工作流并行算法的实验结果与分析 191
参考文献 196
第9章 基于Petri网的变数交通网络建模及其最短路径加权S-图算法 199
9.1 变数交通及最短路径研究现状 199
9.1.1 研究意义 199
9.1.2 国外研究现状 200
9.1.3 国内研究现状 201
9.1.4 最短路径问题及其应用 201
9.2 静态交通网络建模及其最短路径算法 202
9.2.1 引言 202
9.2.2 S-图的定义 203
9.2.3 静态交通网络的抽象与建模 203
9.2.4 基于加权S-图的最短路径算法 205
9.2.5 改进的加权S-图算法 209
9.3 变数交通网络建模及其最短路径算法 212
9.3.1 引言 212
9.3.2 变数交通网络的抽象与建模 213
9.3.3 基于Petri网的变数交通网络最短路径算法 215
9.3.4 变数交通网络最短路径算法实现 220
9.3.5 静态与动态实验的比较分析 221
参考文献 222
第10章 Petri网并行算法的应用 224
10.1 满秩Petri网可达性判定算法 224
10.1.1 满秩Petri网 224
10.1.2 满秩Petri网可达性判定算法设计 225
10.1.3 VC++验算 227
10.1.4 讨论 229
10.2 Petri网共享合成及其在并行系统中的应用 230
10.2.1 Petri网共享合成运算的概念 230
10.2.2 共享合成运算的推广 232
10.2.3 共享合成运算构建MPI并行程序Petri网模型算法 235
10.2.4 应用实例 236
10.3 无约束很优化问题的BFGS并行算法设计与分析 239
10.3.1 无约束很优化问题的定义及BFGS算法 240
10.3.2 BFGS算法并行处理 242
10.3.3 数值实验 247
10.4 无约束很优化问题的BFGS松弛异步并行算法 248
10.4.1 无序松弛异步迭代 248
10.4.2 无约束很优化问题松弛异步并行算法 249
10.4.3 实验结果与分析 252
10.5 基于GEP的多数据流分类并行算法 253
10.5.1 按时序划分的模型 253
10.5.2 按数据属性划分的模型 254
10.5.3 GEP概述 254
10.5.4 GEP的算法流程 257
10.5.5 一种MSA-GEP分类并行算法的实现 258
10.5.6 GEP的分类原理 259
10.5.7 引入粒度分析的属性合并 260
10.5.8 MSA-GEP串行算法 262
10.5.9 GEP的并行结构选取 262
10.5.1 0MSA-GEP并行算法 263
10.5.1 1实验结果与分析 265
10.6 基于GEP的多数据流压缩并行算法 267
10.6.1 GEP的函数发现原理 268
10.6.2 引入两种协调机制 269
10.6.3 串行FR-GEP算法 271
10.6.4 并行FR-GEP算法 271
10.6.5 实验结果与分析 273
10.7 基于MSA-GEP与PFR-GEP的多数据流分类压缩 275
10.7.1 基于GEP的分类压缩过程设计 276
10.7.2 基于GEP的分类压缩并行算法实现 278
10.7.3 RSS-GEP串行算法的步骤 282
10.7.4 RSS-GEP分类压缩并行算法 283
10.7.5 实验结果与分析 285
参考文献 288
附录A 基于多核PC的Petri网并行算法的自动物料处理仿真系统部分代码 291
附录B 基于多核机群三级并行模型的Petri网自动物料并行处理仿真系统部分代码 294