Petri網(wǎng)并行化理論與并行算法

目錄
前言
第1章 Petri網(wǎng)并行化的研究背景 1
1.1 Petri網(wǎng)的研究現(xiàn)狀 1
1.2 Petri網(wǎng)并行化理論與關(guān)鍵技術(shù)問題 5
1.3 基于多核機群的功能并行算法 5
1.4 Petri網(wǎng)的并行計算 6
1.5 基于多核機群的Petri網(wǎng)并行算法的研究思路 8
參考文獻 11
第2章 MPI OpenMP STM并行編程模型 17
2.1 并行計算機的分類 17
2.1.1 按指令流和數(shù)據(jù)流分類 17
2.1.2 按數(shù)據(jù)的存儲方式分類 18
2.2 并行計算模型 20
2.2.1 并行計算模型的要素 20
2.2.2 共享存儲并行計算模型 20
2.2.3 分布式存儲并行計算模型 21
2.2.4 存儲層次并行計算模型 22
2.3 并行程序設(shè)計 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 并行算法的分析與設(shè)計 38
2.5.4 實驗結(jié)果與分析 40
2.6 基于多核機群的人工魚群并行算法 44
2.6.1 相關(guān)工作 44
2.6.2 基于動態(tài)權(quán)衡與小生境技術(shù)的串行式AFSA 46
2.6.3 基于MPI OpenMP的人工魚群并行算法實現(xiàn) 47
2.6.4 實驗結(jié)果與分析 50
2.7 基于多核機群的混合群智能并行算法 54
2.7.1 相關(guān)工作 55
2.7.2 混合群智能兩階段處理方法 59
2.7.3 MPI OpenMP STM并行模型 60
2.7.4 混合群智能并行算法 63
2.7.5 實驗環(huán)境及參數(shù)設(shè)置 64
2.7.6 實驗結(jié)果與分析 65
參考文獻 68
第3章 Petri網(wǎng)系統(tǒng)的數(shù)學(xué)模型 74
3.1 Petri網(wǎng)的基本概念 74
3.2 Petri網(wǎng)系統(tǒng)分析方法 79
3.3 Petri網(wǎng)的圖形結(jié)構(gòu)模型 82
3.4 Petri網(wǎng)的代數(shù)模型 85
參考文獻 88
第4章 Petri網(wǎng)系統(tǒng)并行化預(yù)處理 89
4.1 Petri網(wǎng)的選擇 89
4.1.1 高級Petri網(wǎng)與P/T網(wǎng)的特點 90
4.1.2 高級Petri網(wǎng)與P/T網(wǎng)的內(nèi)在機理 90
4.2 結(jié)構(gòu)模型的轉(zhuǎn)化方法 90
4.3 代數(shù)模型的并行化預(yù)處理方法 92
4.3.1 轉(zhuǎn)換過程與驗證 92
4.3.2 P/T網(wǎng)與顏色Petri網(wǎng)的形式化表示 94
4.3.3 顏色Petri網(wǎng)關(guān)聯(lián)矩陣分析 95
4.3.4 顏色Petri網(wǎng)并行化預(yù)處理自動轉(zhuǎn)換算法 96
4.3.5 顏色Petri網(wǎng)轉(zhuǎn)換成P/T網(wǎng)的算法 96
4.4 實驗結(jié)果與分析 97
4.5 謂詞/變遷網(wǎng)轉(zhuǎn)換成P/T網(wǎng)的方法 98
參考文獻 100
第5章 P-不變量求解算法與T-圖子網(wǎng)劃分方法 102
5.1 P-不變量求解 102
5.1.1 Petri網(wǎng)的形式化過程 102
5.1.2 P-不變量的求解過程 102
5.1.3 P-不變量及其支集的求解算法 105
5.1.4 實驗結(jié)果與分析 106
5.2 T-圖的求解方法 107
5.2.1 T-圖的定義 107
5.2.2 T-圖的求解算法 110
5.2.3 算法的形式化 111
5.2.4 T-圖劃分的應(yīng)用示例 112
5.2.5 實驗結(jié)果與分析 113
參考文獻 113
第6章 Petri網(wǎng)系統(tǒng)并行化子網(wǎng)劃分理論 115
6.1 Petri網(wǎng)并行化子網(wǎng)劃分方法比較 115
6.1.1 基于P-不變量的子網(wǎng)劃分條件 115
6.1.2 兩種劃分方法的分析與評價 117
6.2 Petri網(wǎng)并行進程劃分的判定定理 118
6.3 Petri網(wǎng)并行化進程劃分的完備性理論 120
6.3.1 子網(wǎng)庫所標識全為零的情況 120
6.3.2 子網(wǎng)間存在共享庫所的情況 122
6.3.3 無法劃分為并行子網(wǎng)的情況 124
6.3.4 子網(wǎng)劃分的完備性定理 126
6.4 Petri網(wǎng)并行化子網(wǎng)劃分算法 126
6.5 Petri網(wǎng)并行化子網(wǎng)劃分算法的應(yīng)用 127
6.5.1 ATM存取款系統(tǒng)轉(zhuǎn)換成P/T網(wǎng)模型 127
6.5.2 各種高級Petri網(wǎng)模型子網(wǎng)劃分實例 128
6.5.3 實驗結(jié)果與分析 128
6.6 Petri網(wǎng)的并行性分析 132
6.6.1 Petri網(wǎng)子網(wǎng)內(nèi)部的并行性分析 132
6.6.2 Petri網(wǎng)子網(wǎng)之間的并行性分析 133
6.7 消息傳遞平臺的Petri網(wǎng)系統(tǒng)并行算法 133
6.8 Petri網(wǎng)系統(tǒng)并行算法的驗證 134
參考文獻 135
第7章 多核機群的Petri網(wǎng)并行模型及其算法 136
7.1 Petri網(wǎng)的并行模型 136
7.1.1 引言 136
7.1.2 Petri網(wǎng)并行幾何模型 137
7.1.3 Petri網(wǎng)并行代數(shù)模型 139
7.2 基于多核PC的Petri網(wǎng)并行算法 140
7.2.1 基于多核PC的多線程編程模式 140
7.2.2 基于多核PC的多線程Petri網(wǎng)并行算法 141
7.2.3 應(yīng)用示例與順序程序 141
7.2.4 基于多核PC的Petri網(wǎng)并行算法流程分析 144
7.2.5 基于多核PC的Petri網(wǎng)并行算法偽代碼 145
7.2.6 并行算法與實例驗證 147
7.3 基于多核機群的Petri網(wǎng)并行模型 148
7.4 多核機群的Petri網(wǎng)并行算法 150
7.4.1 多核機群的Petri網(wǎng)并行子網(wǎng)劃分算法 151
7.4.2 基于多核機群的Petri網(wǎng)并行算法 151
7.4.3 實例分析 153
7.4.4 實驗環(huán)境 160
7.4.5 串行實驗結(jié)果 161
7.4.6 MPI實驗結(jié)果 162
7.4.7 OpenMP實驗結(jié)果 163
7.4.8 MPI OpenMP STM實驗結(jié)果 164
7.4.9 實驗結(jié)果與分析 165
參考文獻 166
第8章 工作流Petri網(wǎng)系統(tǒng)的并行算法 169
8.1 國內(nèi)外研究現(xiàn)狀及發(fā)展趨勢 169
8.1.1 引言 169
8.1.2 國外研究現(xiàn)狀 170
8.1.3 國內(nèi)研究現(xiàn)狀 170
8.1.4 存在的不足 171
8.2 工作流概述 171
8.3 工作流模型與Petri網(wǎng)的映射關(guān)系 172
8.4 基于Petri網(wǎng)的工作流模型建模 173
8.5 工作流基本模式的Petri網(wǎng)模型及其并行性分析 173
8.5.1 工作流基本模式的Petri網(wǎng)模型 173
8.5.2 工作流Petri網(wǎng)并行模型 178
8.6 基于多核PC的工作流并行算法 180
8.7 算法應(yīng)用與實驗分析 181
8.7.1 工作流實例 181
8.7.2 實例的Petri網(wǎng)建模 183
8.7.3 系統(tǒng)的性能分析結(jié)果 185
8.7.4 實例的求解過程 185
8.7.5 基于多核PC的工作流并行算法的實驗結(jié)果與分析 191
參考文獻 196
第9章 基于Petri網(wǎng)的變數(shù)交通網(wǎng)絡(luò)建模及其*短路徑加權(quán)S-圖算法 199
9.1 變數(shù)交通及*短路徑研究現(xiàn)狀 199
9.1.1 研究意義 199
9.1.2 國外研究現(xiàn)狀 200
9.1.3 國內(nèi)研究現(xiàn)狀 201
9.1.4 *短路徑問題及其應(yīng)用 201
9.2 靜態(tài)交通網(wǎng)絡(luò)建模及其*短路徑算法 202
9.2.1 引言 202
9.2.2 S-圖的定義 203
9.2.3 靜態(tài)交通網(wǎng)絡(luò)的抽象與建模 203
9.2.4 基于加權(quán)S-圖的*短路徑算法 205
9.2.5 改進的加權(quán)S-圖算法 209
9.3 變數(shù)交通網(wǎng)絡(luò)建模及其*短路徑算法 212
9.3.1 引言 212
9.3.2 變數(shù)交通網(wǎng)絡(luò)的抽象與建模 213
9.3.3 基于Petri網(wǎng)的變數(shù)交通網(wǎng)絡(luò)*短路徑算法 215
9.3.4 變數(shù)交通網(wǎng)絡(luò)*短路徑算法實現(xiàn) 220
9.3.5 靜態(tài)與動態(tài)實驗的比較分析 221
參考文獻 222
第10章 Petri網(wǎng)并行算法的應(yīng)用 224
10.1 滿秩Petri網(wǎng)可達性判定算法 224
10.1.1 滿秩Petri網(wǎng) 224
10.1.2 滿秩Petri網(wǎng)可達性判定算法設(shè)計 225
10.1.3 VC 驗算 227
10.1.4 討論 229
10.2 Petri網(wǎng)共享合成及其在并行系統(tǒng)中的應(yīng)用 230
10.2.1 Petri網(wǎng)共享合成運算的概念 230
10.2.2 共享合成運算的推廣 232
10.2.3 共享合成運算構(gòu)建MPI并行程序Petri網(wǎng)模型算法 235
10.2.4 應(yīng)用實例 236
10.3 無約束**化問題的BFGS并行算法設(shè)計與分析 239
10.3.1 無約束**化問題的定義及BFGS算法 240
10.3.2 BFGS算法并行處理 242
10.3.3 數(shù)值實驗 247
10.4 無約束**化問題的BFGS松弛異步并行算法 248
10.4.1 無序松弛異步迭代 248
10.4.2 無約束**化問題松弛異步并行算法 249
10.4.3 實驗結(jié)果與分析 252
10.5 基于GEP的多數(shù)據(jù)流分類并行算法 253
10.5.1 按時序劃分的模型 253
10.5.2 按數(shù)據(jù)屬性劃分的模型 254
10.5.3 GEP概述 254
10.5.4 GEP的算法流程 257
10.5.5 一種MSA-GEP分類并行算法的實現(xiàn) 258
10.5.6 GEP的分類原理 259
10.5.7 引入粒度分析的屬性合并 260
10.5.8 MSA-GEP串行算法 262
10.5.9 GEP的并行結(jié)構(gòu)選取 262
10.5.1 0MSA-GEP并行算法 263
10.5.1 1實驗結(jié)果與分析 265
10.6 基于GEP的多數(shù)據(jù)流壓縮并行算法 267
10.6.1 GEP的函數(shù)發(fā)現(xiàn)原理 268
10.6.2 引入兩種協(xié)調(diào)機制 269
10.6.3 串行FR-GEP算法 271
10.6.4 并行FR-GEP算法 271
10.6.5 實驗結(jié)果與分析 273
10.7 基于MSA-GEP與PFR-GEP的多數(shù)據(jù)流分類壓縮 275
10.7.1 基于GEP的分類壓縮過程設(shè)計 276
10.7.2 基于GEP的分類壓縮并行算法實現(xiàn) 278
10.7.3 RSS-GEP串行算法的步驟 282
10.7.4 RSS-