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-