《并行计算 结构·算法·编程》求取 ⇩

第一篇并行计算硬件基础3

第一章 并行计算机系统及其结构模型3

1.1 并行计算与高端并行计算机3

1.1.1 并行计算与计算科学3

1.1.2 当代科学与工程问题的计算需求4

1.1.3 万亿次高端并行机7

1.2 并行计算机系统互连9

1.2.1 系统互连9

1.2.2 表态互连网络10

1.2.3 动态互连网络13

1.2.4 宽带互连网络17

1.3 并行计算机系统结构21

1.3.1 并行计算机结构模型21

1.3.2 并行计算机访存模型25

1.3.3 并行计算机存储组织29

1.4 小结和导读33

习题34

第二章 当代并行机系统：SMP、MPP和COW38

2.1 对称多处理机SMP38

2.1.1 SMP和CC-NUMA结构特性38

2.1.2 SGL/Cray Origin 2000超级服务器40

2.2 大规模并行机MPP47

2.2.1 MPP结构特性47

2.2.2 机群型大规模并行机SP251

2.3 工作站机群COW57

2.3.1 COW的基本原理与技术58

2.3.2 Berkeley的NOW计划61

2.4 国产曙光毓并行机系统67

2.4.1 全对称共享存储多处理机系统：曙光1号68

2.4.2 大规模并行处理系统：曙光-100072

2.4.3 超级并行计算机系统：曙光-200075

2.5 小结和导读80

习题81

3.1.1 Amdahl定律83

第三章 并行计算性能评测83

3.1 加速比性能定律83

3.1.2 Gustafson定律85

3.1.3 Sun和Ni定律85

3.1.4 有关加速的讨论87

3.2 可扩放性评测标准88

3.2.1 并行计算的可护放性88

3.2.2 等效率度量标准89

3.2.3 等速度度量标准91

3.2.4 平均延迟度量标准95

3.2.5 有关可扩放性标准的讨论97

3.3 基准测试程序99

3.3.1 基本测试程序99

3.3.2 数学库测试程序100

3.3.3 并行测试程序101

3.4 小结和导读102

习题102

4.1.1 并行算法的定义和分类107

4.1 并行算法的基础知识107

第二篇 并行算法的设计107

第四章 并行算法的设计基础107

4.1.2 并行算法的表达108

4.1.3 并行算法的复杂性度量109

4.1.4 并行算法中的同步与通信110

4.2 并行计算模型112

4.2.1 PRAM模型112

4.2.2 异步PRAM模型113

4.2.3 BSP模型114

4.2.4 logP模型116

4.2.5 C3模型118

4.2.6 对BSP和logP的评注121

4.3 小结和导读123

习题124

5.1.1 设计方法描述129

第五章 并行算法的一般设计方法129

5.1 串行算法的直接并行化129

5.1.2 快排序算法的并行化130

5.2 从问题描述开始设计并行算法132

5.2.1 串匹配算法132

5.2.2 KMP串行串匹配算法133

5.2.3 并行串区配算法的设计思路136

5.3 借用已有算法求解新问题137

5.3.1 设计方法描述137

5.3.2 利用矩阵乘法求所有点对间最短路径138

5.4 小结和导读141

习题141

第六章 并行算法的基本设计技术144

6.1 划分设计技术144

6.1.1 均匀划分技术144

6.1.2 方根划分技术146

6.1.3 对数划分技术146

6.1.4 功能划分技术148

6.2 分治设计技术149

6.2.1 双调归并网络149

6.2.2 凸壳问题151

6.3 平衡树设计技术153

6.3.1 求取最大值153

6.3.2 计算前缀和154

6.4 倍增设计技术155

6.4.1 表序问题的计算155

6.4.2 求森林的根156

6.5 流水线设计技术158

6.5.1 一维心动阵列上的DFT计算158

6.5.2 一维心动阵列上的卷积计算159

6.6 小结和导读161

习题162

第七章 并行算法的一般设计过程164

7.1 PCAM设计方法学164

7.2 划分165

7.2.1 域分解166

7.2.2 功能分解166

7.2.3 划分判据167

7.3 通信167

7.3.1 局部通信168

7.3.2 全局通信169

7.3.3 非结构化、动态和异步通信170

7.3.4 通信判据170

7.4 组合171

7.4.1 增加粒度171

7.4.2 保持灵活性和减少软件工程成本174

7.4.3 组合判据174

7.5 映射175

7.5.1 负载平衡算法175

7.5.2 任务调度算法177

7.5.3 映射判据177

7.6 小结和导读178

习题179

第三篇 并行数值算法185

第八章 基本通信操作185

8.1 选路方法与开关技术185

8.1.1 选路方法185

8.1.2 开关技术187

8.2 单一信包一到一传输189

8.3 一到多播送190

8.3.1 使用SF进行一到多播送190

8.3.2 使用CF进行一到多播送191

8.4 多到多播送193

8.4.1 使用SF进行多到多播送193

8.4.2 使用CT进行多到多播送195

8.5 小结和导读196

习题198

9.1.1 带状划分203

9.1 矩阵的划分203

第九章 稠密矩阵运算203

9.1.2 棋盘划分204

9.2 矩阵转置205

9.2.1 棋盘划分的矩阵转置205

9.2.2 带状划分的矩阵转置208

9.3 矩阵-向量乘法209

9.3.1 带状划分的矩阵-向量乘法210

9.3.2 棋盘划分的矩阵-向量乘法211

9.4 矩阵乘法213

9.4.1 简单并行分块乘法214

9.4.2 Cannon乘法215

9.4.3 Fox乘法218

9.4.4 DNS乘法218

9.5 小结和导读223

习题224

10.1.1 基本术语227

10.1 三角形方程组的求解227

第十章 线性方程组的求解227

10.1.2 上三角方程组的求解228

10.2 三对角方程组的求解230

10.2.1 三对角方程组直接求解法230

10.2.2 三对角方程组奇偶归约求解法232

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 离散博氏变换260

11.1.1 预备知识260

11.1.2 离散傅里叶变换261

11.1.3 离散傅里叶逆变换263

11.1.4 离散傅氏变换的蝶式计算263

11.2 快速傅氏变换串行算法265

11.2.1 串行FFT迭代算法265

11.2.2 串行FFT递归算法267

11.3 并行FFT算法269

11.3.1 SIMD-MC2上FFT算法269

11.3.2 SIMD-BF上FFT算法272

11.3.3 SIMD-CC上FFT算法273

11.3.4 MIMD-DM上FFT算法275

11.4 小结和导读278

习题279

第四篇并行程序设计283

第十二章 并行程序设计基础283

12.1 并行程序设计概述283

12.1.1 串行程序设计与并行程序设计283

12.1.2 并行程序设计环境285

12.1.3 并长程序设计方法285

12.2 进程287

12.2.1 进程和基本概念287

12.2.2 进程的并行执行290

12.2.3 进程的相互作用291

12.3 线程292

12.3.1 线程的基本要领293

12.3.2 线程的管理293

12.3.3 线程的同步295

12.4 同步295

12.4.1 原子与互斥295

12.4.2 高级同步结构296

12.4.3 低级同步原语297

12.5 通信299

12.5.1 影响通信系统性能的因素300

12.5.2 低级通们支持301

12.5.3 TCP/IP通信协议组简介302

12.6 小结和导读306

习题306

第十三章 并行程序设计模型和共享存储系统编程309

13.1 并行编程风范和样本程序309

13.1.1 五种并行骗程风范309

13.1.2 计算?样本程序310

13.2 并行程序设计模型312

13.2.1 隐式并行模型312

13.2.2 数据并行模型313

13.2.3 消息传递模型314

13.2.4 共享变量模型316

13.3 共享存储并行编程318

13.3.1 ANSI X3H5共享存储模型320

13.3.2 POSIX线程模型322

13.3.3 Open MP标准323

13.4 小结和导读326

习题327

第十四章 分布存储系统并行编程332

14.1 基于消息传递的并行编程332

14.1.1 SPMD并行编程333

14.1.2 MPMD并行程序334

14.2 MPI并行编程335

14.2.1 最基本的MPI336

14.2.2 群体通信338

14.2.3 通信体340

14.2.4 导出数据类型342

14.2.5 点到点通信343

14.3 PVM并行编程348

14.3.1 PVM概貌348

14.3.2 PVM消息传递库349

14.4 基于数据并行的并行编程352

14.4.1 数据并行模型的特点352

14.4.2 数据并行编程的基本问题352

14.5 HPF并行编程353

14.5.1 HPF的语言特点354

14.5.2 HPF的数据并行机制354

14.5.3 HPF使用中的若干问题359

14.6 小结和导读361

习题362

附录一 MPI的函数的C语言说明366

附录二 MPI的函数的Fortran语言说明368

第十五章 并行程序设计环境与工具371

15.1 软件工具与环境371

15.1.1 编码工具371

15.1.2 软件工程工具372

15.1.3 集成工具372

15.1.4 将来的工具与环境373

15.2 并行编译器374

15.2.1 编译及其并行化375

15.2.2 相关分析377

15.2.3 代码优化379

15.2.4 代码生成384

15.3 并行程序调试和性能分析384

15.3.1 并行程序的调试384

15.3.2 并行程序的性能分析387

15.3.3 并行程序的可视化设计环境与工具389

15.4 小结和导读390

习题391

算法索引394

表格索引396

示范程序索引398

参考文献399

并行与分布计算Web网址409

术语中-英对照及索引415