并行計(jì)算：結(jié)構(gòu)·算法·編程

第一篇　并行計(jì)算硬件基礎(chǔ)
第一章　　并行計(jì)算機(jī)系統(tǒng)及其結(jié)構(gòu)模型
3

1.1　　并行計(jì)算
4

1.1.1　　并行計(jì)算與計(jì)算科學(xué)
4

1.1.2　　當(dāng)代科學(xué)與工程問(wèn)題的計(jì)算需求
4
　1.2　　并行計(jì)算機(jī)系統(tǒng)互連
8

1.2.1　　系統(tǒng)互連
8

1.2.2　　靜態(tài)互連網(wǎng)絡(luò)
9

1.2.3　　動(dòng)態(tài)互連網(wǎng)絡(luò)
13

1.2.4　　標(biāo)準(zhǔn)互連網(wǎng)絡(luò)
17

1.3　　并行計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)
22

1.3.1　　并行計(jì)算機(jī)結(jié)構(gòu)模型
22

1.3.2　　并行計(jì)算機(jī)訪存模型
26

*1.3.3　并行計(jì)算機(jī)存儲(chǔ)組織
30

1.4　　小結(jié)和導(dǎo)讀
34

習(xí)題
35

第二章　　當(dāng)代并行計(jì)算機(jī)系統(tǒng)介紹
39

2.1　　共享存儲(chǔ)多處理機(jī)系統(tǒng)
40

2.1.1　　對(duì)稱多處理機(jī)SMP結(jié)構(gòu)特性
40

*2.1.2　　CC-NUMA Origin 2000超級(jí)服務(wù)器　　41
2.2　　分布存儲(chǔ)多計(jì)算機(jī)系統(tǒng)
48

2.2.1　大規(guī)模并行處理機(jī)MPP結(jié)構(gòu)特性
49
　*2.2.2　　ASCI Option Red MPP系統(tǒng)
53

2.3　機(jī)群系統(tǒng)
57

2.3.1　大規(guī)模并行處理系統(tǒng)MPP機(jī)群SP2
58
　2.3.2　工作站機(jī)群COW
64

*2.3.3　Berkeley的NOW計(jì)劃
68

2.4　小結(jié)和導(dǎo)讀
73

習(xí)題
75

第三章　并行計(jì)算性能評(píng)測(cè)
77

3.1　并行計(jì)算機(jī)的一些基本性能指標(biāo)
78

3.1.1　CPU和存儲(chǔ)器的某些基本性能指標(biāo)
78
3.1.2　通信開(kāi)銷
80

3.1.3　機(jī)器的成本. 價(jià)格與性能/價(jià)格比
81
3.2　加速比性能定律
83

3.2.1　Amdahl定律
83

3.2.2　Gustafson定律
84

3.2.3　Sun和Ni定律
86

3.2.4　有關(guān)加速的討論
87

3.3　可擴(kuò)放性評(píng)測(cè)標(biāo)準(zhǔn)
88

3.3.1　并行計(jì)算的可擴(kuò)放性
88

3.3.2　等效率度量標(biāo)準(zhǔn)
89

3.3.3　等速度度量標(biāo)準(zhǔn)
90

3.3.4　平均延遲度量標(biāo)準(zhǔn)
92

3.3.5　有關(guān)可擴(kuò)放性標(biāo)準(zhǔn)的討論
94

*3.4　基準(zhǔn)測(cè)試程序
95

3.4.1　基本的測(cè)試程序
95

3.4.2　數(shù)學(xué)庫(kù)測(cè)試程序
96

3.4.3　并行測(cè)試程序
97

3.5　小結(jié)和導(dǎo)讀
98

習(xí)題
99

第二篇　并行算法的設(shè)計(jì)
第四章　并行算法的設(shè)計(jì)基礎(chǔ)
103

*4.1　　并行算法的基礎(chǔ)知識(shí)
104

4.1.1　并行算法的定義和分類
104

4.1.2　并行算法的表達(dá)
105

4.1.3　并行算法的復(fù)雜性度量
105

4.1.4　并行算法中的同步與通信
107

4.2　并行計(jì)算模型
108

4.2.1　PRAM模型
109

4.2.2　異步PRAM模型
110

4.2.3　BSP模型
111

4.2.4　logP模型
113

4.2.5　對(duì)BSP和logP的評(píng)注
115

4.3　小結(jié)和導(dǎo)讀
117

習(xí)題
118

第五章　并行算法的一般設(shè)計(jì)策略
123
5.1　串行算法的直接并行化
124

5.1.1　設(shè)計(jì)策略描述
124

5.1.2　快排序算法的并行化
124

5.2　從問(wèn)題描述開(kāi)始設(shè)計(jì)并行算法
127

5.2.1　串匹配算法
127

*5.2.2　KMP串行串匹配算法
128

5.2.3　并行串匹配算法的設(shè)計(jì)思路
130

5.3　借用已有算法求解新問(wèn)題
131

5.3.1　設(shè)計(jì)策略描述
131

5.3.2　利用矩陣乘法求所有點(diǎn)對(duì)間最短路徑
132
5.4　小結(jié)和導(dǎo)讀
135

習(xí)題
136

第六章　并行算法的基本設(shè)計(jì)技術(shù)
139

6.1　劃分設(shè)計(jì)技術(shù)
140

6.1.1　均勻劃分技術(shù)
140

6.1.2　方根劃分技術(shù)
141

6.1.3　對(duì)數(shù)劃分技術(shù)
142

6.1.4　功能劃分技術(shù)
143

6.2　分治設(shè)計(jì)技術(shù)
144

6.2.1　雙調(diào)歸并網(wǎng)絡(luò)
145

6.2.2　凸殼問(wèn)題
146

6.3　平衡樹設(shè)計(jì)技術(shù)
149

6.3.1　求取最大值
149

6.3.2　計(jì)算前綴和
149

6.4　倍增設(shè)計(jì)技術(shù)
151

6.4.1　表序問(wèn)題的計(jì)算
151

6.4.2　求森林的根
152

6.5　流水線設(shè)計(jì)技術(shù)
153

6.5.1　一維心動(dòng)陣列上的DFT計(jì)算
154

6.5.2　一維心動(dòng)陣列上的卷積計(jì)算
155

6.6　小結(jié)和導(dǎo)讀
156

習(xí)題
158

第七章　并行算法的一般設(shè)計(jì)過(guò)程
160

7.1　PCAM設(shè)計(jì)方法學(xué)
161

7.2　劃分
162

7.2.1　域分解
162

7.2.2　功能分解
163

7.2.3　劃分判據(jù)
163

7.3　通信
164

7.3.1　局部通信
164

7.3.2　全局通信
166

7.3.3　非結(jié)構(gòu)化. 動(dòng)態(tài)和異步通信
167

7.3.4　通信判據(jù)
167

7.4　組合
167

7.4.1　增加粒度
168

7.4.2　保持靈活性和減少軟件工程成本
170
　7.4.3　組合判據(jù)
171

7.5　映射
171

7.5.1　負(fù)載平衡算法
172

7.5.2　任務(wù)調(diào)度算法
173

7.5.3　映射判據(jù)
174

7.6　小結(jié)和導(dǎo)讀
174

習(xí)題
175
第三篇　并行數(shù)值算法
第八章　基本通信操作
183

8.1　選路方法與開(kāi)關(guān)技術(shù)
184

8.1.1　選路方法
184

8.1.2　開(kāi)關(guān)技術(shù)
186

8.2　單一信包一到一傳輸
188

8.3　一到多播送
188

8.3.1　使用SF進(jìn)行一到多播送
188

8.3.2　使用CT進(jìn)行一到多播送
190

8.4　多到多播送
191

8.4.1　使用SF進(jìn)行多到多播送
192

8.4.2　使用CT進(jìn)行多到多播送
193

8.5　小結(jié)和導(dǎo)讀
195

習(xí)題
197

第九章　稠密矩陣運(yùn)算
201

9.1　矩陣的劃分
202

9.1.1　帶狀劃分
202

9.1.2　棋盤劃分
202

9.2　矩陣轉(zhuǎn)置
204

9.2.1　棋盤劃分的矩陣轉(zhuǎn)置
204

9.2.2　帶狀劃分的矩陣轉(zhuǎn)置
207

9.3　矩陣-向量乘法
208

9.3.1　帶狀劃分的矩陣-向量乘法
208

9.3.2　棋盤劃分的矩陣-向量乘法
210

9.4　矩陣乘法
212

9.4.1　簡(jiǎn)單并行分塊乘法
212

9.4.2　Cannon乘法
214

9.4.3　Fox乘法
217

9.4.4　DNS乘法
217

9.5　小結(jié)和導(dǎo)讀
222

習(xí)題
223

第十章　線性方程組的求解
226

10.1　三角形方程組的求解
227

10.1.1　基本術(shù)語(yǔ)
227

10.1.2　上三角方程組的求解
228

10.2　　三對(duì)角方程組的求解
230

10.2.1　三對(duì)角方程組直接求解法
230

10.2.2　三對(duì)角方程組奇偶?xì)w約求解法
231
10.3　稠密線性方程組的求解
233

10.3.1　有回代的高斯消去法
233

10.3.2　無(wú)回代的高斯-約旦法
237

10.3.3　迭代求解的高斯-賽德?tīng)柗?br />239

10.4　稀疏線性方程組的求解
241

10.4.1　稀疏矩陣的存儲(chǔ)方式
241

10.4.2　雅可比迭代法
243

10.4.3　高斯-賽德?tīng)柕?br />247

10.4.4　超松弛迭代法
249

10.4.5　多重網(wǎng)格法
249

10.4.6　共軛梯度法
251

10.5　小結(jié)和導(dǎo)讀
256

習(xí)題
257

第十一章　快速傅里葉變換
260

11.1　　離散傅氏變換
261

*11.1.1　預(yù)備知識(shí)
261

11.1.2　離散傅里葉變換
262

11.1.3　離散傅里葉逆變換
263

11.1.4　離散傅氏變換的蝶式計(jì)算
264

*11.2　快速傅氏變換串行算法
266

11.2.1　串行FFT迭代算法
266

11.2.2　串行FFT遞歸算法
267

11.3　并行FFT算法
270

11.3.1　SIMD-MC2上FFT算法
270

11.3.2　SIMD-BF上FFT算法
272

11.3.3　SIMD-CC上FFT算法
274

11.3.4　MIMD-DM上FFT算法
275

11.4　小結(jié)和導(dǎo)讀
279

習(xí)題
280

第四篇　并行程序設(shè)計(jì)
第十二章　并行程序設(shè)計(jì)基礎(chǔ)
285

12.1　并行程序設(shè)計(jì)概述
286

12.1.1　串行程序設(shè)計(jì)與并行程序設(shè)計(jì)
286
　12.1.2　并行程序設(shè)計(jì)環(huán)境與工具
287

12.1.3　并行程序設(shè)計(jì)方法
288

12.1.4　并行編程風(fēng)范
290

*12.2　進(jìn)程
291

12.2.1　進(jìn)程的基本概念
291

12.2.2　進(jìn)程的并行執(zhí)行
294

12.2.3　進(jìn)程的相互作用
295

12.3　　線程
297

12.3.1　線程的基本概念
297

12.3.2　線程的管理
298

12.3.3　線程的同步
299

*12.4　　同步
299

12.4.1　原子與互斥
300

12.4.2　高級(jí)同步結(jié)構(gòu)
300

12.4.3　低級(jí)同步原語(yǔ)
302

12.5　通信
303

12.5.1　影響通信系統(tǒng)性能的因素
304

12.5.2　低級(jí)通信支持
305

12.5.3　TCP/IP通信協(xié)議組簡(jiǎn)介
307

12.6　并行程序設(shè)計(jì)模型
310

12.6.1　計(jì)算π樣本程序
310

12.6.2　隱式并行模型
311

12.6.3　數(shù)據(jù)并行模型
313

12.6.4　消息傳遞模型
314

12.6.5　共享變量模型
315

12.6.6　并行程序設(shè)計(jì)模型比較
317

12.7　小結(jié)和導(dǎo)讀
318

習(xí)題
319

第十三章　共享存儲(chǔ)系統(tǒng)并行編程
322

13.1　基于共享變量的共享存儲(chǔ)并行編程
323
13.1.1　共享存儲(chǔ)并行編程的基本問(wèn)題
323
13.1.2　共享存儲(chǔ)編程環(huán)境
324

13.2　早期共享存儲(chǔ)并行編程模型
324

13.2.1　ANSI X3H5共享存儲(chǔ)模型
324

13.2.2　POSIX線程模型
327

13.3　OpenMP編程簡(jiǎn)介
328

13.3.1　OpenMP概述
329

13.3.2　OpenMP編程風(fēng)格
329

13.3.3　OpenMP編程要素
330

13.3.4　OpenMP計(jì)算實(shí)例
339

13.3.5　運(yùn)行庫(kù)例程與環(huán)境變量
341

13.4　小結(jié)和導(dǎo)讀
341

習(xí)題
342

附錄　OpenMP運(yùn)行庫(kù)例程
345

第十四章　分布存儲(chǔ)系統(tǒng)并行編程
348
14.1　基于消息傳遞的并行編程
349

14.1.1　SPMD并行程序
349

14.1.2　MPMD并行程序
350

14.2　MPI并行編程
351

14.2.1　最基本的MPI
352

14.2.2　群體通信
355

14.2.3　通信體
357

14.2.4　導(dǎo)出數(shù)據(jù)類型
358

14.2.5　點(diǎn)到點(diǎn)通信
359

*14.3　PVM并行編程
364

14.3.1　PVM概貌
365

14.3.2　PVM消息傳遞庫(kù)
365

14.4　基于數(shù)據(jù)并行的并行編程
368

14.4.1　數(shù)據(jù)并行模型的特點(diǎn)
368

14.4.2　數(shù)據(jù)并行編程的基本問(wèn)題
369

14.5　HPF并行編程
370

14.5.1　HPF的語(yǔ)言特點(diǎn)
370

14.5.2 HPF的數(shù)據(jù)并行機(jī)制
371

14.5.3 HPF使用中的若干問(wèn)題
375

14.6　小結(jié)和導(dǎo)讀
378

習(xí)題
379

附錄一　MPI的函數(shù)的C語(yǔ)言說(shuō)明
384

附錄二　MPI的函數(shù)的Fortran語(yǔ)言說(shuō)明
386

第十五章　并行程序設(shè)計(jì)環(huán)境與工具
389

*15.1　軟件工具與環(huán)境
390

15.1.1 編碼工具
390

15.1.2　軟件工程工具
391

15.1.3　集成工具
391

15.1.4　將來(lái)的工具與環(huán)境
392

15.2　并行編譯器
393

15.2.1　編譯及其并行化
394

15.2.2　相關(guān)分析
396

15.2.3　代碼優(yōu)化
398

15.2.4　代碼生成
403

15.3　并行程序調(diào)試
403

15.3.1　并行程序調(diào)試的方法與步驟
404
　15.3.2　并行程序的調(diào)試技術(shù)
406

15.3.3　并行程序的性能調(diào)試
407

15.4　并行程序性能分析
408

15.4.1　并行程序的性能預(yù)測(cè)
408

15.4.2　并行程序的性能監(jiān)控
410

15.4.3　并行程序的性能可視化
411

15.5　圖形化并行程序集成開(kāi)發(fā)環(huán)境
413

15.5.1　并行程序的可視化設(shè)計(jì)環(huán)境與工具
413
15.5.2　圖形應(yīng)用開(kāi)發(fā)環(huán)境GRADE的組成
414
15.5.3　GRADE中開(kāi)發(fā)并行程序過(guò)程
414

15.6　小結(jié)和導(dǎo)讀
416

習(xí)題
417

算法索引
420
表格索引
422
示范程序索引　　423
參考文獻(xiàn)
424
并行與分布計(jì)算Web網(wǎng)址
434
專業(yè)術(shù)語(yǔ)中英對(duì)照及索引
440