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 基于多核機(jī)群的功能并行算法 5
1.4 Petri網(wǎng)的并行計(jì)算 6
1.5 基于多核機(jī)群的Petri網(wǎng)并行算法的研究思路 8
參考文獻(xiàn) 11
第2章 MPI OpenMP STM并行編程模型 17
2.1 并行計(jì)算機(jī)的分類 17
2.1.1 按指令流和數(shù)據(jù)流分類 17
2.1.2 按數(shù)據(jù)的存儲(chǔ)方式分類 18
2.2 并行計(jì)算模型 20
2.2.1 并行計(jì)算模型的要素 20
2.2.2 共享存儲(chǔ)并行計(jì)算模型 20
2.2.3 分布式存儲(chǔ)并行計(jì)算模型 21
2.2.4 存儲(chǔ)層次并行計(jì)算模型 22
2.3 并行程序設(shè)計(jì) 23
2.3.1 并行編程模型 23
2.3.2 共享變量編程模型 24
2.3.3 消息傳遞編程模型 27
2.3.4 多線程編程和多進(jìn)程編程 28
2.4 多核機(jī)群的并行計(jì)算 29
2.4.1 MPI OpenMP混合編程模式 29
2.4.2 MPI OpenMP STM三級(jí)混合編程模式 31
2.4.3 MPI OpenMP STM并行算法 34
2.5 基于多核PC的人工蜂群并行算法 35
2.5.1 ABC算法 36
2.5.2 改進(jìn)的ABC算法 36
2.5.3 并行算法的分析與設(shè)計(jì) 38
2.5.4 實(shí)驗(yàn)結(jié)果與分析 40
2.6 基于多核機(jī)群的人工魚群并行算法 44
2.6.1 相關(guān)工作 44
2.6.2 基于動(dòng)態(tài)權(quán)衡與小生境技術(shù)的串行式AFSA 46
2.6.3 基于MPI OpenMP的人工魚群并行算法實(shí)現(xiàn) 47
2.6.4 實(shí)驗(yàn)結(jié)果與分析 50
2.7 基于多核機(jī)群的混合群智能并行算法 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 實(shí)驗(yàn)環(huán)境及參數(shù)設(shè)置 64
2.7.6 實(shí)驗(yàn)結(jié)果與分析 65
參考文獻(xiàn) 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
參考文獻(xiàn) 88
第4章 Petri網(wǎng)系統(tǒng)并行化預(yù)處理 89
4.1 Petri網(wǎng)的選擇 89
4.1.1 高級(jí)Petri網(wǎng)與P/T網(wǎng)的特點(diǎn) 90
4.1.2 高級(jí)Petri網(wǎng)與P/T網(wǎng)的內(nèi)在機(jī)理 90
4.2 結(jié)構(gòu)模型的轉(zhuǎn)化方法 90
4.3 代數(shù)模型的并行化預(yù)處理方法 92
4.3.1 轉(zhuǎn)換過程與驗(yà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ù)處理自動(dòng)轉(zhuǎn)換算法 96
4.3.5 顏色Petri網(wǎng)轉(zhuǎn)換成P/T網(wǎng)的算法 96
4.4 實(shí)驗(yàn)結(jié)果與分析 97
4.5 謂詞/變遷網(wǎng)轉(zhuǎn)換成P/T網(wǎng)的方法 98
參考文獻(xiàn) 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 實(shí)驗(yàn)結(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 實(shí)驗(yàn)結(jié)果與分析 113
參考文獻(xiàn) 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 兩種劃分方法的分析與評(píng)價(jià) 117
6.2 Petri網(wǎng)并行進(jìn)程劃分的判定定理 118
6.3 Petri網(wǎng)并行化進(jìn)程劃分的完備性理論 120
6.3.1 子網(wǎng)庫(kù)所標(biāo)識(shí)全為零的情況 120
6.3.2 子網(wǎng)間存在共享庫(kù)所的情況 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 各種高級(jí)Petri網(wǎng)模型子網(wǎng)劃分實(shí)例 128
6.5.3 實(shí)驗(yàn)結(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 消息傳遞平臺(tái)的Petri網(wǎng)系統(tǒng)并行算法 133
6.8 Petri網(wǎng)系統(tǒng)并行算法的驗(yàn)證 134
參考文獻(xiàn) 135
第7章 多核機(jī)群的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 并行算法與實(shí)例驗(yàn)證 147
7.3 基于多核機(jī)群的Petri網(wǎng)并行模型 148
7.4 多核機(jī)群的Petri網(wǎng)并行算法 150
7.4.1 多核機(jī)群的Petri網(wǎng)并行子網(wǎng)劃分算法 151
7.4.2 基于多核機(jī)群的Petri網(wǎng)并行算法 151
7.4.3 實(shí)例分析 153
7.4.4 實(shí)驗(yàn)環(huán)境 160
7.4.5 串行實(shí)驗(yàn)結(jié)果 161
7.4.6 MPI實(shí)驗(yàn)結(jié)果 162
7.4.7 OpenMP實(shí)驗(yàn)結(jié)果 163
7.4.8 MPI OpenMP STM實(shí)驗(yàn)結(jié)果 164
7.4.9 實(shí)驗(yàn)結(jié)果與分析 165
參考文獻(xiàn) 166
第8章 工作流Petri網(wǎng)系統(tǒng)的并行算法 169
8.1 國(guó)內(nèi)外研究現(xiàn)狀及發(fā)展趨勢(shì) 169
8.1.1 引言 169
8.1.2 國(guó)外研究現(xiàn)狀 170
8.1.3 國(guó)內(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)用與實(shí)驗(yàn)分析 181
8.7.1 工作流實(shí)例 181
8.7.2 實(shí)例的Petri網(wǎng)建模 183
8.7.3 系統(tǒng)的性能分析結(jié)果 185
8.7.4 實(shí)例的求解過程 185
8.7.5 基于多核PC的工作流并行算法的實(shí)驗(yàn)結(jié)果與分析 191
參考文獻(xiàn) 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 國(guó)外研究現(xiàn)狀 200
9.1.3 國(guó)內(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 改進(jìn)的加權(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ò)*短路徑算法實(shí)現(xiàn) 220
9.3.5 靜態(tài)與動(dòng)態(tài)實(shí)驗(yàn)的比較分析 221
參考文獻(xiàn) 222
第10章 Petri網(wǎng)并行算法的應(yīng)用 224
10.1 滿秩Petri網(wǎng)可達(dá)性判定算法 224
10.1.1 滿秩Petri網(wǎng) 224
10.1.2 滿秩Petri網(wǎng)可達(dá)性判定算法設(shè)計(jì) 225
10.1.3 VC 驗(yàn)算 227
10.1.4 討論 229
10.2 Petri網(wǎng)共享合成及其在并行系統(tǒng)中的應(yīng)用 230
10.2.1 Petri網(wǎng)共享合成運(yùn)算的概念 230
10.2.2 共享合成運(yùn)算的推廣 232
10.2.3 共享合成運(yùn)算構(gòu)建MPI并行程序Petri網(wǎng)模型算法 235
10.2.4 應(yīng)用實(shí)例 236
10.3 無約束**化問題的BFGS并行算法設(shè)計(jì)與分析 239
10.3.1 無約束**化問題的定義及BFGS算法 240
10.3.2 BFGS算法并行處理 242
10.3.3 數(shù)值實(shí)驗(yàn) 247
10.4 無約束**化問題的BFGS松弛異步并行算法 248
10.4.1 無序松弛異步迭代 248
10.4.2 無約束**化問題松弛異步并行算法 249
10.4.3 實(shí)驗(yàn)結(jié)果與分析 252
10.5 基于GEP的多數(shù)據(jù)流分類并行算法 253
10.5.1 按時(shí)序劃分的模型 253
10.5.2 按數(shù)據(jù)屬性劃分的模型 254
10.5.3 GEP概述 254
10.5.4 GEP的算法流程 257
10.5.5 一種MSA-GEP分類并行算法的實(shí)現(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實(shí)驗(yàn)結(jié)果與分析 265
10.6 基于GEP的多數(shù)據(jù)流壓縮并行算法 267
10.6.1 GEP的函數(shù)發(fā)現(xiàn)原理 268
10.6.2 引入兩種協(xié)調(diào)機(jī)制 269
10.6.3 串行FR-GEP算法 271
10.6.4 并行FR-GEP算法 271
10.6.5 實(shí)驗(yàn)結(jié)果與分析 273
10.7 基于MSA-GEP與PFR-GEP的多數(shù)據(jù)流分類壓縮 275
10.7.1 基于GEP的分類壓縮過程設(shè)計(jì) 276
10.7.2 基于GEP的分類壓縮并行算法實(shí)現(xiàn) 278
10.7.3 RSS-GEP串行算法的步驟 282
10.7.4 RSS-