并行计算 结构·算法·编程 第3版PDF电子书下载

第一篇 并行计算硬件平台：并行计算机 3

第一章 并行计算与并行计算机结构模型 3

1.1 计算与计算机科学 4

1.1.1 科学发现的第三支柱：计算科学 4

1.1.2 计算科学与计算机科学 5

1.2 单处理机与指令级并行 6

1.2.1 加快CPU执行速度 6

1.2.2 减少存储延迟 7

1.2.3 改善输入和输出以及网络性能 8

1.3 多核处理器与线程级并行 9

1.3.1 单核处理器结构设计 9

1.3.2 多核处理器结构设计 10

1.3.3 多核处理器实例 11

1.4 并行计算机体系结构 13

1.4.1 并行计算机结构模型 13

1.4.2 并行计算机访存模型 17

1.4.3 并行计算机存储组织 21

1.5 并行计算概述 25

1.5.1 关于并行计算 25

1.5.2 并行计算研究现状 28

1.6 小结和导读 32

习题 34

第二章 并行计算机系统互连与基本通信操作 36

2.1 并行计算机互连网络 37

2.1.1 系统互连 37

2.1.2 静态互连网络 38

2.1.3 动态互连网络 43

2.1.4 标准互连网络 46

2.2 选路方法与开关技术 52

2.2.1 选路方法 52

2.2.2 开关技术 54

2.3 单一信包一到一传输 56

2.4 一到多播送 56

2.4.1 使用SF进行一到多播送 57

2.4.2 使用CT进行一到多播送 58

2.5 多到多播送 59

2.5.1 使用SF进行多到多播送 59

2.5.2 使用CT进行多到多播送 62

2.6 小结和导读 62

习题 65

第三章 典型并行计算机系统介绍 72

3.1 共享存储多处理机系统 73

3.1.1 对称多处理机SMP结构特性 73

3.1.2 SGI Challenge系统 74

3.2 分布存储多计算机系统 77

3.2.1 大规模并行处理机MPP结构特性 77

3.2.2 ASCI Option Red MPP系统 82

3.3 分布共享存储计算机系统 86

3.3.1 分布共享存储计算机系统特性 87

3.3.2 SGI Origin 2000系统 90

3.4 机群系统 96

3.4.1 大规模并行处理系统MPP机群SP2 96

3.4.2 工作站机群COW 103

3.4.3 Berkeley的NOW计划 107

3.5 小结和导读 112

习题 114

第四章 并行计算性能评测 117

4.1 并行计算机的一些基本性能指标 118

4.1.1 CPU和存储器的某些基本性能指标 118

4.1.2 通信开销 120

4.1.3 机器的成本、价格与性能价格比 121

4.2 加速比性能定律 123

4.2.1 Amdahl定律 123

4.2.2 Gustafson定律 125

4.2.3 Sun和Ni定律 125

4.2.4 有关加速的讨论 127

4.3 可扩放性评测标准 128

4.3.1 并行计算的可扩放性 128

4.3.2 等效率度量标准 129

4.3.3 等速度度量标准 130

4.3.4 平均延迟度量标准 132

4.3.5 有关可扩放性标准的讨论 133

4.4 基准测试程序 134

4.4.1 基本的测试程序 135

4.4.2 数学库测试程序 136

4.4.3 并行测试程序 137

4.5 小结和导读 138

习题 139

第二篇 并行计算理论基础：并行算法（上）——并行算法设计 145

第五章 并行算法与并行计算模型 145

5.1 并行算法的基础知识 146

5.1.1 并行算法的定义和分类 146

5.1.2 并行算法的表达 147

5.1.3 并行算法的复杂性度量 147

5.1.4 并行算法中的同步与通信 149

5.2 并行计算模型 150

5.2.1 PRAM模型 151

5.2.2 异步PRAM模型 152

5.2.3 BSP模型 153

5.2.4 LogP模型 155

5.2.5 对BSP和LogP的评注 158

5.2.6 层次存储模型 160

5.2.7 分层并行计算模型 163

5.3 小结和导读 167

习题 168

第六章 并行算法基本设计策略 173

6.1 串行算法的直接并行化 174

6.1.1 设计策略描述 174

6.1.2 快排序算法的并行化 174

6.2 从问题描述开始设计并行算法 177

6.2.1 串匹配算法 177

6.2.2 KMP串行串匹配算法 178

6.2.3 并行串匹配算法的设计思路 180

6.3 借用已有算法求解新问题 181

6.3.1 设计策略描述 182

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

6.4 小结和导读 185

习题 186

第七章 并行算法常用设计技术 189

7.1 划分设计技术 190

7.1.1 均匀划分技术 190

7.1.2 方根划分技术 191

7.1.3 对数划分技术 192

7.1.4 功能划分技术 193

7.2 分治设计技术 194

7.2.1 双调归并网络 195

7.2.2 凸壳问题 196

7.3 平衡树设计技术 198

7.3.1 求取最大值 198

7.3.2 计算前缀和 199

7.4 倍增设计技术 200

7.4.1 表序问题的计算 200

7.4.2 求森林的根 201

7.5 流水线设计技术 203

7.5.1 一维脉动阵列上的DFT计算 203

7.5.2 一维脉动阵列上的卷积计算 204

7.6 小结和导读 205

习题 207

第八章 并行算法一般设计过程 209

8.1 PCAM设计方法学 210

8.2 划分 211

8.2.1 域分解 211

8.2.2 功能分解 212

8.2.3 划分判据 212

8.3 通信 213

8.3.1 局部通信 213

8.3.2 全局通信 214

8.3.3 非结构化、动态和异步通信 215

8.3.4 通信判据 216

8.4 组合 216

8.4.1 增加粒度 217

8.4.2 保持灵活性和减少软件工程成本 219

8.4.3 组合判据 219

8.5 映射 220

8.5.1 负载平衡算法 221

8.5.2 任务调度算法 222

8.5.3 映射判据 223

8.6 小结和导读 223

习题 224

第二篇 并行计算理论基础：并行算法（下）——并行数值算法 229

第九章 稠密矩阵运算 229

9.1 矩阵的划分 230

9.1.1 带状划分 230

9.1.2 棋盘划分 231

9.2 矩阵转置 231

9.2.1 棋盘划分的矩阵转置 232

9.2.2 带状划分的矩阵转置 235

9.3 矩阵-向量乘法 236

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

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

9.4 矩阵乘法 239

9.4.1 简单并行分块乘法 240

9.4.2 Cannon乘法 241

9.4.3 Fox乘法 244

9.4.4 DNS乘法 246

9.5 小结和导读 250

习题 251

第十章 线性方程组求解 254

10.1 三角形方程组的求解 255

10.1.1 基本术语 255

10.1.2 上三角方程组的求解 256

10.2 三对角方程组的求解 258

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

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

10.3 稠密线性方程组的求解 262

10.3.1 有回代的高斯消去法 262

10.3.2 无回代的高斯-约旦法 266

10.3.3 迭代求解的高斯-赛德尔法 268

10.4 稀疏线性方程组的求解 270

10.4.1 稀疏矩阵的存储方式 270

10.4.2 雅可比迭代法 272

10.4.3 高斯-赛德尔迭代法 278

10.4.4 超松弛迭代法 279

10.4.5 多重网格法 280

10.4.6 共轭梯度法 281

10.5 小结和导读 286

习题 287

第十一章 快速傅里叶变换 289

11.1 离散傅氏变换 290

11.1.1 预备知识 290

11.1.2 离散傅里叶变换 291

11.1.3 离散傅里叶逆变换 292

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

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

11.2.1 串行FFT迭代算法 295

11.2.2 串行FFT递归算法 296

11.3 并行FFT算法 298

11.3.1 SIMD-MC2上FFT算法 299

11.3.2 SIMD-BF上FFT算法 301

11.3.3 SIMD-CC上FFT算法 303

11.3.4 MIMD-DM上FFT算法 304

11.4 小结和导读 308

习题 309

第十二章 数值计算的基本支撑技术 311

12.1 网格生成 312

12.1.1 网格生成过程与方法 312

12.1.2 并行网格生成 315

12.1.3 网格生成有关软件和网址 316

12.2 图的划分 317

12.2.1 负载平衡与图的划分 318

12.2.2 图划分算法 318

12.2.3 多约束图划分问题及算法 321

12.3 稀疏线性系统求解器 322

12.3.1 稀疏矩阵的来源和结构 322

12.3.2 稀疏线性系统直接方法 323

12.3.3 稀疏线性系统迭代方法 324

12.3.4 预条件子 326

12.3.5 稀疏线性代数库 328

12.4 算法和软件 329

12.4.1 算法和软件的可重用 329

12.4.2 算法和软件的可移植 331

12.4.3 算法和软件的可扩放 332

12.5 科学计算可视化 334

12.5.1 科学计算可视化的基本概念 334

12.5.2 并行科学计算可视化 336

12.6 小结和导读 338

习题 340

第三篇 并行计算软件支撑：并行编程 345

第十三章 并行程序设计基础 345

13.1 并行程序设计概述 346

13.1.1 串行程序设计与并行程序设计 346

13.1.2 并行程序设计环境与工具 348

13.1.3 并行程序设计方法 348

13.1.4 并行编程风范 350

13.2 进程和线程 351

13.2.1 进程和线程的基本概念 351

13.2.2 进程和线程的并行执行 353

13.3 同步和通信 355

13.3.1 同步 355

13.3.2 通信 358

13.4 单核多线程与多核多线程 359

13.4.1 单处理器核上并发程序设计 359

13.4.2 多执行核上并行程序设计 361

13.5 影响多线程性能的常见问题 362

13.5.1 线程过多 362

13.5.2 数据竞争 364

13.5.3 死锁 365

13.5.4 Cache伪共享 366

13.6 并行程序设计模型 367

13.6.1 计算π样本程序 367

13.6.2 隐式并行模型 369

13.6.3 数据并行模型 370

13.6.4 消息传递模型 371

13.6.5 共享变量模型 372

13.6.6 并行程序设计模型比较 374

13.7 小结和导读 375

习题 375

第十四章 共享存储系统并行编程 378

14.1 基于共享变量的共享存储并行编程 379

14.1.1 共享存储并行编程的基本问题 379

14.1.2 共享存储编程环境 380

14.2 POSIX线程 380

14.2.1 POSIX线程模型 381

14.2.2 使用Pthreads编写计算π的程序实例 382

14.3 OpenMP并行编程 384

14.3.1 OpenMP概述 384

14.3.2 OpenMP编程风格 385

14.3.3 共享任务结构 389

14.3.4 OpenMP其他编程要素 393

14.3.5 OpenMP计算实例 398

14.4 小结和导读 401

习题 401

附录 OpenMP运行库例程 404

第十五章 分布存储系统并行编程 406

15.1 基于消息传递的并行编程 407

15.1.1 SPMD并行程序 407

15.1.2 MPMD并行程序 408

15.2 MPI并行编程 409

15.2.1 MPI概述 410

15.2.2 最基本的MPI 411

15.2.3 MPI消息 413

15.2.4 点对点通信 418

15.2.5 群集通信 420

15.2.6 计算π的MPI程序 425

15.3 基于数据并行的并行编程 425

15.3.1 数据并行模型的特点 426

15.3.2 数据并行编程的基本问题 426

15.4 HPF并行编程 427

15.4.1 HPF概述 427

15.4.2 HPF编程简介 428

15.4.3 数据映射 432

15.4.4 数据并行结构 435

15.4.5 HPF语言的过程 438

15.4.6 高斯消去法的HPF程序 440

15.5 小结和导读 440

习题 441

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

附录二 MPI函数的FORTRAN语言说明 449

第十六章 并行程序设计环境与工具 452

16.1 软件工具与环境 453

16.1.1 编码工具与软件工程工具 453

16.1.2 集成工具与环境 454

16.2 并行编译器 456

16.2.1 编译及其并行化 457

16.2.2 相关分析 459

16.2.3 代码优化 461

16.2.4 代码生成 466

16.3 并行程序调试 467

16.3.1 并行程序调试的方法与步骤 467

16.3.2 并行程序的调试技术 469

16.4 并行程序性能分析 470

16.4.1 并行程序的性能预测 470

16.4.2 并行程序的性能监控 472

16.4.3 并行程序性能分析工具 474

16.4.4 并行程序的性能可视化 475

16.5 图形化并行程序集成开发环境 477

16.5.1 图形应用开发环境GRADE的组成 477

16.5.2 GRADE中开发并行程序过程 478

16.5.3 基于模式的可视化并行编程环境CO2P3S 479

16.6 小结和导读 480

习题 481

附录篇 并行计算发展动力：并行应用 487

附录A 并行应用相关知识 487

A.1 应用需求 487

A.2 应用领域 488

A.3 应用实例 489

A.4 应用须知 490

附录B 应用综合练习：大气模型的并行算法设计 492

B.1 背景知识 492

B.2 设计分析 493

附录C 数值计算软件包和工具 495

C.1 高性能程序库 495

C.1.1 BLAS库 495

C.1.2 LAPACK库 497

C.1.3 ScaLAPACK库 498

C.2 软件包和工具 500

C.2.1 PETSc 500

C.2.2 FFTW 501

C.2.3 HPSEPS 503

C.2.4 Hypre 504

C.2.5 MUMPS 505

C.2.6 ParMETIS 506

C.2.7 Trilions 507

C.2.8 TAO 509

C.2.9 SUNDIALS 511

C.2.10 SLEPC 512

附录D 应用实例一：机群系统上三维傅里叶变换 515

D.1 问题背景 515

D.2 机群系统 516

D.3 三维傅里叶变换一般并行算法 517

D.4 改进的三维傅里叶变换并行算法 519

D.5 应用实例 520

D.6 编程实现 521

D.7 实验比较 523

附录E 应用实例二：多核系统上并行图像特征提取 525

E.1 问题背景 525

E.2 多核平台 527

E.3 图像特征提取的并行算法 528

E.4 编程实现 530

E.5 实验比较 533

附录F 应用实例三：个人高性能计算机上水平井射孔渗流计算 535

F.1 问题背景 535

F.2 并行计算方法 536

F.3 并行编程概述 538

F.4 KD-50-I平台 540

F.5 应用结果 541

索引 544

算法索引 544

表格索引 546

示范程序索引 547

专业术语索引 548

参考文献 561