并行计算：结构·算法·编程

第一篇　并行计算硬件基础
第一章　　并行计算机系统及其结构模型
3

1.1　　并行计算
4

1.1.1　　并行计算与计算科学
4

1.1.2　　当代科学与工程问题的计算需求
4
　1.2　　并行计算机系统互连
8

1.2.1　　系统互连
8

1.2.2　　静态互连网络
9

1.2.3　　动态互连网络
13

1.2.4　　标准互连网络
17

1.3　　并行计算机系统结构
22

1.3.1　　并行计算机结构模型
22

1.3.2　　并行计算机访存模型
26

*1.3.3　并行计算机存储组织
30

1.4　　小结和导读
34

习题
35

第二章　　当代并行计算机系统介绍
39

2.1　　共享存储多处理机系统
40

2.1.1　　对称多处理机SMP结构特性
40

*2.1.2　　CC-NUMA Origin 2000超级服务器　　41
2.2　　分布存储多计算机系统
48

2.2.1　大规模并行处理机MPP结构特性
49
　*2.2.2　　ASCI Option Red MPP系统
53

2.3　机群系统
57

2.3.1　大规模并行处理系统MPP机群SP2
58
　2.3.2　工作站机群COW
64

*2.3.3　Berkeley的NOW计划
68

2.4　小结和导读
73

习题
75

第三章　并行计算性能评测
77

3.1　并行计算机的一些基本性能指标
78

3.1.1　CPU和存储器的某些基本性能指标
78
3.1.2　通信开销
80

3.1.3　机器的成本. 价格与性能/价格比
81
3.2　加速比性能定律
83

3.2.1　Amdahl定律
83

3.2.2　Gustafson定律
84

3.2.3　Sun和Ni定律
86

3.2.4　有关加速的讨论
87

3.3　可扩放性评测标准
88

3.3.1　并行计算的可扩放性
88

3.3.2　等效率度量标准
89

3.3.3　等速度度量标准
90

3.3.4　平均延迟度量标准
92

3.3.5　有关可扩放性标准的讨论
94

*3.4　基准测试程序
95

3.4.1　基本的测试程序
95

3.4.2　数学库测试程序
96

3.4.3　并行测试程序
97

3.5　小结和导读
98

习题
99

第二篇　并行算法的设计
第四章　并行算法的设计基础
103

*4.1　　并行算法的基础知识
104

4.1.1　并行算法的定义和分类
104

4.1.2　并行算法的表达
105

4.1.3　并行算法的复杂性度量
105

4.1.4　并行算法中的同步与通信
107

4.2　并行计算模型
108

4.2.1　PRAM模型
109

4.2.2　异步PRAM模型
110

4.2.3　BSP模型
111

4.2.4　logP模型
113

4.2.5　对BSP和logP的评注
115

4.3　小结和导读
117

习题
118

第五章　并行算法的一般设计策略
123
5.1　串行算法的直接并行化
124

5.1.1　设计策略描述
124

5.1.2　快排序算法的并行化
124

5.2　从问题描述开始设计并行算法
127

5.2.1　串匹配算法
127

*5.2.2　KMP串行串匹配算法
128

5.2.3　并行串匹配算法的设计思路
130

5.3　借用已有算法求解新问题
131

5.3.1　设计策略描述
131

5.3.2　利用矩阵乘法求所有点对间最短路径
132
5.4　小结和导读
135

习题
136

第六章　并行算法的基本设计技术
139

6.1　划分设计技术
140

6.1.1　均匀划分技术
140

6.1.2　方根划分技术
141

6.1.3　对数划分技术
142

6.1.4　功能划分技术
143

6.2　分治设计技术
144

6.2.1　双调归并网络
145

6.2.2　凸壳问题
146

6.3　平衡树设计技术
149

6.3.1　求取最大值
149

6.3.2　计算前缀和
149

6.4　倍增设计技术
151

6.4.1　表序问题的计算
151

6.4.2　求森林的根
152

6.5　流水线设计技术
153

6.5.1　一维心动阵列上的DFT计算
154

6.5.2　一维心动阵列上的卷积计算
155

6.6　小结和导读
156

习题
158

第七章　并行算法的一般设计过程
160

7.1　PCAM设计方法学
161

7.2　划分
162

7.2.1　域分解
162

7.2.2　功能分解
163

7.2.3　划分判据
163

7.3　通信
164

7.3.1　局部通信
164

7.3.2　全局通信
166

7.3.3　非结构化. 动态和异步通信
167

7.3.4　通信判据
167

7.4　组合
167

7.4.1　增加粒度
168

7.4.2　保持灵活性和减少软件工程成本
170
　7.4.3　组合判据
171

7.5　映射
171

7.5.1　负载平衡算法
172

7.5.2　任务调度算法
173

7.5.3　映射判据
174

7.6　小结和导读
174

习题
175
第三篇　并行数值算法
第八章　基本通信操作
183

8.1　选路方法与开关技术
184

8.1.1　选路方法
184

8.1.2　开关技术
186

8.2　单一信包一到一传输
188

8.3　一到多播送
188

8.3.1　使用SF进行一到多播送
188

8.3.2　使用CT进行一到多播送
190

8.4　多到多播送
191

8.4.1　使用SF进行多到多播送
192

8.4.2　使用CT进行多到多播送
193

8.5　小结和导读
195

习题
197

第九章　稠密矩阵运算
201

9.1　矩阵的划分
202

9.1.1　带状划分
202

9.1.2　棋盘划分
202

9.2　矩阵转置
204

9.2.1　棋盘划分的矩阵转置
204

9.2.2　带状划分的矩阵转置
207

9.3　矩阵-向量乘法
208

9.3.1　带状划分的矩阵-向量乘法
208

9.3.2　棋盘划分的矩阵-向量乘法
210

9.4　矩阵乘法
212

9.4.1　简单并行分块乘法
212

9.4.2　Cannon乘法
214

9.4.3　Fox乘法
217

9.4.4　DNS乘法
217

9.5　小结和导读
222

习题
223

第十章　线性方程组的求解
226

10.1　三角形方程组的求解
227

10.1.1　基本术语
227

10.1.2　上三角方程组的求解
228

10.2　　三对角方程组的求解
230

10.2.1　三对角方程组直接求解法
230

10.2.2　三对角方程组奇偶归约求解法
231
10.3　稠密线性方程组的求解
233

10.3.1　有回代的高斯消去法
233

10.3.2　无回代的高斯-约旦法
237

10.3.3　迭代求解的高斯-赛德尔法
239

10.4　稀疏线性方程组的求解
241

10.4.1　稀疏矩阵的存储方式
241

10.4.2　雅可比迭代法
243

10.4.3　高斯-赛德尔迭代法
247

10.4.4　超松弛迭代法
249

10.4.5　多重网格法
249

10.4.6　共轭梯度法
251

10.5　小结和导读
256

习题
257

第十一章　快速傅里叶变换
260

11.1　　离散傅氏变换
261

*11.1.1　预备知识
261

11.1.2　离散傅里叶变换
262

11.1.3　离散傅里叶逆变换
263

11.1.4　离散傅氏变换的蝶式计算
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　小结和导读
279

习题
280

第四篇　并行程序设计
第十二章　并行程序设计基础
285

12.1　并行程序设计概述
286

12.1.1　串行程序设计与并行程序设计
286
　12.1.2　并行程序设计环境与工具
287

12.1.3　并行程序设计方法
288

12.1.4　并行编程风范
290

*12.2　进程
291

12.2.1　进程的基本概念
291

12.2.2　进程的并行执行
294

12.2.3　进程的相互作用
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　高级同步结构
300

12.4.3　低级同步原语
302

12.5　通信
303

12.5.1　影响通信系统性能的因素
304

12.5.2　低级通信支持
305

12.5.3　TCP/IP通信协议组简介
307

12.6　并行程序设计模型
310

12.6.1　计算π样本程序
310

12.6.2　隐式并行模型
311

12.6.3　数据并行模型
313

12.6.4　消息传递模型
314

12.6.5　共享变量模型
315

12.6.6　并行程序设计模型比较
317

12.7　小结和导读
318

习题
319

第十三章　共享存储系统并行编程
322

13.1　基于共享变量的共享存储并行编程
323
13.1.1　共享存储并行编程的基本问题
323
13.1.2　共享存储编程环境
324

13.2　早期共享存储并行编程模型
324

13.2.1　ANSI X3H5共享存储模型
324

13.2.2　POSIX线程模型
327

13.3　OpenMP编程简介
328

13.3.1　OpenMP概述
329

13.3.2　OpenMP编程风格
329

13.3.3　OpenMP编程要素
330

13.3.4　OpenMP计算实例
339

13.3.5　运行库例程与环境变量
341

13.4　小结和导读
341

习题
342

附录　OpenMP运行库例程
345

第十四章　分布存储系统并行编程
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　导出数据类型
358

14.2.5　点到点通信
359

*14.3　PVM并行编程
364

14.3.1　PVM概貌
365

14.3.2　PVM消息传递库
365

14.4　基于数据并行的并行编程
368

14.4.1　数据并行模型的特点
368

14.4.2　数据并行编程的基本问题
369

14.5　HPF并行编程
370

14.5.1　HPF的语言特点
370

14.5.2 HPF的数据并行机制
371

14.5.3 HPF使用中的若干问题
375

14.6　小结和导读
378

习题
379

附录一　MPI的函数的C语言说明
384

附录二　MPI的函数的Fortran语言说明
386

第十五章　并行程序设计环境与工具
389

*15.1　软件工具与环境
390

15.1.1 编码工具
390

15.1.2　软件工程工具
391

15.1.3　集成工具
391

15.1.4　将来的工具与环境
392

15.2　并行编译器
393

15.2.1　编译及其并行化
394

15.2.2　相关分析
396

15.2.3　代码优化
398

15.2.4　代码生成
403

15.3　并行程序调试
403

15.3.1　并行程序调试的方法与步骤
404
　15.3.2　并行程序的调试技术
406

15.3.3　并行程序的性能调试
407

15.4　并行程序性能分析
408

15.4.1　并行程序的性能预测
408

15.4.2　并行程序的性能监控
410

15.4.3　并行程序的性能可视化
411

15.5　图形化并行程序集成开发环境
413

15.5.1　并行程序的可视化设计环境与工具
413
15.5.2　图形应用开发环境GRADE的组成
414
15.5.3　GRADE中开发并行程序过程
414

15.6　小结和导读
416

习题
417

算法索引
420
表格索引
422
示范程序索引　　423
参考文献
424
并行与分布计算Web网址
434
专业术语中英对照及索引
440