並行計算：模型與算法

《並行計算：模型與算法》是2016年7月1日機械工業出版社出版的圖書，作者是張雲泉、袁良。

基本介紹

• 中文名：並行計算：模型與算法
• 作者：張雲泉、袁良
• 出版社：機械工業出版社
• ISBN：9787111533405

內容簡介

本書系統介紹了三代並行計算模型，包括共享存儲並行計算模型、分散式存儲並行計算模型和存儲層次並行計算模型，並介紹了大量針對並行計算模型的算法。此外，本書還介紹了並行程式性能模型以及並發和分散式算法。書中算法和語言力求精簡明確，部分章節後配備習題，並有注釋和大量參考文獻。

圖書目錄

前言

第1章緒論1

1.1模型1

1.1.1白盒模型1

1.1.2黑盒模型2

1.2計算模型3

1.2.1計算能力模型3

1.2.2算法設計模型7

1.3並行計算模型8

1.3.1基本度量參數9

1.3.2基本並行計算模型11

1.4相關概念13

1.4.1系統結構模型13

1.4.2並行編程模型18

1.4.3並行編程模式22

1.4.4基準測試程式23

1.4.5數據一致性模型25

1.4.6並行、並發與分散式27

1.5並行算法設計30

1.5.1並行算法表示30

1.5.2算法複雜度31

1.5.3問題31

1.6小結33

第2章固定結構並行計算模型34

2.1邏輯電路35

2.1.1定義35

2.1.2加法器35

2.2比較器電路39

2.2.1定義39

2.2.2歸併39

2.2.3排序44

2.2.4選擇46

2.3代數電路48

2.3.1定義48

2.3.2FFT48

2.3.3前綴和51

2.4線性陣列53

2.4.1定義53

2.4.2排序54

2.4.3三角矩陣求解57

2.5混洗連線59

2.5.1定義59

2.5.2排序60

2.5.3FFT62

2.5.4矩陣轉置62

2.6格線64

2.6.1定義64

2.6.2歸併64

2.6.3排序66

2.6.4矩陣乘68

2.6.5疊代法70

2.7樹形71

2.7.1定義71

2.7.2排序73

2.7.3前綴和74

2.7.4圖的連通分量75

2.8超立方76

2.8.1定義76

2.8.2排序77

2.8.3通信78

2.9小結79

2.10習題80

第3章共享存儲並行計算模型(計算複雜度)83

3.1PRAM模型83

3.1.1定義83

3.1.2模型的能力84

3.1.3算法設計技術85

3.1.4問題下界85

3.2PRAM變體86

3.2.1APRAM86

3.2.2分相PRAM87

3.3選擇88

3.3.1EREW上的成本最優算法88

3.3.2CRCW上的常數時間算法89

3.3.3縮減處理器90

3.3.4算法級聯91

3.3.5下界92

3.4歸併93

3.4.1CREW上的常數時間算法93

3.4.2縮減處理器94

3.5查找95

3.5.1CREW上的最優時間算法95

3.5.2下界95

3.6排序95

3.6.1枚舉排序96

3.6.2Preparata排序96

3.6.3下界97

3.7前綴和98

3.7.1倍增法98

3.7.2算法級聯98

3.8圖算法99

3.8.1分層倍增法99

3.8.2歐拉迴路101

3.8.3Ear分解103

3.8.4破對稱方法104

3.9小結105

3.10習題106

第4章分散式存儲並行計算模型(通信複雜度)107

4.1通信複雜度模型107

4.1.1LPRAM模型107

4.1.2Yao模型109

4.2延遲頻寬模型110

4.2.1LogP模型110

4.2.2Postal模型111

4.2.3LogGP模型115

4.3其他模型116

4.3.1BSP116

4.3.2QSM116

4.3.3BPRAM模型117

4.4小結117

第5章存儲層次並行計算模型(存儲複雜度)118

5.1單層存儲層次118

5.2兩層存儲層次121

5.2.1紅藍卵石模型121

5.2.2分塊傳輸模型124

5.3多層存儲層次126

5.3.1多層卵石模型127

5.3.2HMM128

5.3.3分塊HMM131

5.3.4RAM(h)模型132

5.4快取無關模型133

5.4.1串列模型134

5.4.2並行模型136

5.5小結138

5.6習題139

第6章並行程式性能模型141

6.1性能模型與計算模型141

6.2加速比模型142

6.2.1Amdahl模型142

6.2.2Gustafson模型142

6.2.3Karp-Flatt模型144

6.2.4Sun-Ni模型145

6.2.5等效率模型145

6.2.6DAG模型146

6.3訪存序列模型147

6.3.1缺失率147

6.3.2重用距離148

6.3.3平均足跡149

6.3.4多進程模型150

6.4軟硬協同模型151

6.4.1計算密集度151

6.4.2串列平衡模型152

6.4.3並行平衡模型152

6.4.4Hill-Marty模型153

6.5算法最佳化模型154

6.5.1算法級聯154

6.5.2參數最佳化155

6.6小結156

第7章並發與分散式算法157

7.1互斥算法157

7.1.1共享存儲算法157

7.1.2分散式存儲算法164

7.1.3基於硬體操作170

7.1.4基於信號量操作172

7.2鎖算法174

7.2.1自旋鎖174

7.2.2讀寫鎖177

7.3同步算法179

7.3.1分散式存儲算法179

7.3.2共享存儲算法181

7.4佇列算法183

7.4.1有界佇列184

7.4.2無界佇列185

7.5廣播算法188

7.5.1洪水算法188

7.5.2生成樹算法188

7.6小結189

7.7習題189

參考文獻191