经典并行与量子并行：提升并挖掘计算系统的潜在性能

推荐序一

推荐序二

前言

第1章　计算概念的谱系

1.1　引言/ 2　

1.2　计算概念谱系化的意义/ 3　

1.3　计算概念的谱系/ 4　

1.3.1　算势/ 5　

1.3.2　算力/ 7　

1.3.3　算术/ 10　

1.3.4　算法/ 11　

1.3.5　算礼/ 13　

1.4　计算概念谱系组分的相互关系/ 14　

1.5　从场的角度认识算势与算力的异同/ 16　

1.6　证明与计算之间的关系/ 20　

1.7　本章小结/ 23　

1.8　思考题/ 23　

参考文献/ 23　

第2章　并行处理的意义及挑战

2.1　引言/ 26　

2.2　并行计算机与应用和工艺的关系/ 26　

2.3　并行处理的普遍性/ 28　

2.4　多核微处理器技术/ 31　

2.5　并行处理需要应对的挑战/ 35　

2.6　并行处理的学科任务/ 40　

2.7　本章小结/ 41　

2.8　思考题/ 41　

参考文献/ 41　

第3章　并行处理的一般原理

3.1　引言/ 44　

3.2　冯·诺依曼结构/ 44　

3.3　通过实例说明指令级并行与数据依赖/ 47　

3.4　通过实例说明线程级并行/ 49　

3.5　延迟隐藏和延迟减少/ 55　

3.6　并行处理技术的图形化表示/ 60　

3.7　费林分类法/ 63　

3.8　指令级并行/ 65　

3.8.1　流水线技术/ 65　

3.8.2　指令的动态调度/ 65　

3.8.3　多发射技术/ 66　

3.9　并行计算机系统的分类/ 67　

3.9.1　向量计算机/ 67　

3.9.2　多处理机/ 68　

3.9.3　多主机/ 68　

3.9.4　大规模并行处理计算机/ 68　

3.10　并行结构的类型/ 69　

3.10.1　单处理器的并行结构/ 69　

3.10.2　多处理器的并行结构/ 69　

3.10.3　处理机结构创新的历史/ 70　

3.10.4　多核共享内存模型/ 73　

3.10.5　多核消息传递模型/ 76　

3.11　本章小结/ 80　

3.12　思考题/ 81　

参考文献/ 81　

第4章　计算性能模型和存储性能模型

4.1　引言/ 84　

4.2　并行执行时间效率模型/ 85　

4.3　可扩展定律/ 103　

4.3.1　阿姆达尔定律/ 103　

4.3.2　古斯塔夫森-巴西斯定律/ 104　

4.3.3　存储受限的扩展定律（孙-倪定律）/ 106　

4.4　并行计算模型/ 112　

4.4.1　PRAM模型/ 112　

4.4.2　BSP模型/ 114　

4.4.3　LogP模型/ 117　

4.5　程序性能指标/ 120　

4.5.1　单道程序工作负载的性能指标/ 120　

4.5.2　多道程序工作负载的性能指标/ 122　

4.6　存储系统的性能指标/ 123　

4.6.1　平均存储访问时间/ 123　

4.6.2　存储延迟与存储带宽/ 124　

4.6.3　单位时钟周期完成的存储访问数量/ 126　

4.6.4　并发平均存储访问时间/ 127　

4.6.5　存储级并行性/ 130　

4.6.6　并发感知的局部性/ 131　

4.7　基准测试/ 133　

4.7.1　基准测试的定义和分类/ 133　

4.7.2　基准测试运行的规范/ 134　

4.7.3　基准测试程序组的要求/ 134　

4.7.4　基准测试的开发者/ 135　

4.7.5　性能测试结果的总结/ 136　

4.8　性能评估方式/ 136　

4.8.1　Roofline模型/ 136　

4.8.2　模拟器/ 151　

4.8.3　需要避免的4个陷阱/ 160　

4.9　本章小结/ 161　

4.10　思考题/ 161　

参考文献/ 161　

第5章　共享存储结构与编程

5.1　引言/ 164　

5.2　共享存储体系结构的类型/ 165　

5.3　并行编程模型/ 168　

5.3.1　抽象与实现的区别及其实例/ 168　

5.3.2　通信与协作/ 176　

5.3.3　通信层面三种并行编程模型的特点/ 187　

5.3.4　混合编程模型/ 188　

5.4　并行处理的流程/ 189　

5.4.1　思路和实例/ 189　

5.4.2　问题分解/ 193　

5.4.3　任务分配/ 193　

5.4.4　协调/ 194　

5.4.5　进程映射/ 194　

5.5　并行编程优化/ 205　

5.5.1　静态分配与动态分配/ 206　

5.5.2　延迟与带宽/ 214　

5.5.3　内在通信与人为通信/ 217　

5.6　减少通信的技术/ 221　

5.6.1　利用时间局部性/ 221　

5.6.2　利用空间局部性/ 222　

5.7　共享内存体系结构/ 228　

5.8　共享内存体系结构编程——OpenMP/ 242　

5.9　实验——OpenMP/ 274

5.9.1　实验——OpenMP求sinx/ 274　

5.9.2　实验——OpenMP求π值/ 278　

5.9.3　实验——OpenMP求斐波那契数列第n项/ 283　

5.9.4　实验——Gauss-Seidel迭代算法的并行实现及其优化/ 291　

5.10　本章小结/ 296　

5.11　思考题/ 296　参考文献/ 296　

第6章　分布式存储结构与编程

6.1　引言/ 300　

6.2　向量处理机体系结构/ 300　

6.2.1　结构特点/ 300　

6.2.2　性能分析/ 305　

6.2.3　向量指令并行/ 307　

6.2.4　向量链/ 307　

6.2.5　向量分解strip-mining技术/ 308　

6.2.6　向量条件执行/ 308　

6.2.7　压缩/展开操作/ 309　

6.2.8　向量归约/ 310　

6.2.9　存储访问/ 311　

6.2.10　分散和聚集/ 312　

6.3　SIMD编程/ 327　

6.3.1　SIMD简介/ 327　

6.3.2　实现向量化的几种方法/ 327　

6.3.3　向量化编译指令/ 328　

6.3.4　向量化过程中的主要挑战/ 330　

6.3.5　编译器向量化方式/ 335　

6.3.6　循环变换/ 339　

6.3.7　数据地址对齐/ 341　

6.3.8　别名/ 341　

6.3.9　条件语句/ 342　

6.3.10　原生SIMD支持/ 342　

6.4　CUDA编程/ 343　

6.4.1　异构计算的定义/ 344　

6.4.2　CUDA/ 345　

6.4.3　GPU的并发控制/ 346　

6.4.4　GPU的内存管理/ 347　

6.4.5　SIMT/ 348　

6.4.6　CUDA编程/ 349　

6.4.7　CUDA与GPU硬件之间的映射/ 355　

6.4.8　深流水线设计/ 356　

6.4.9　GPU内存/ 356　

6.4.10　GPU并发策略/ 358　

6.4.11　库函数介绍/ 358　

6.5　MPI编程/ 363　

6.5.1　MPI在编程模型内的分类定位/ 363　

6.5.2　信息交互模型与通信方式/ 364　

6.5.3　MPI基本函数/ 367　

6.5.4　MPI程序执行（以C on linux为例）/ 370　

6.5.5　MPI集群通信函数/ 370　

6.6　实验——编写MPI并行程序/ 379　

6.6.1　编写MPI程序并行计算平均值/ 379　

6.6.2　编写MPI程序并行计算矩阵向量乘法/ 381　

6.6.3　编写MPI程序并行计算圆周率/ 383　

6.7　实验——基于CUDA并发的矩阵乘法/ 386　

6.8　本章小结/ 391　

6.9　思考题/ 392　

第7章　并行计算机系统的互连网络

7.1　引言/ 394　

7.2　互连网络的基本概念/ 394　

7.2.1　互连网络分层架构/ 394　

7.2.2　互连网络相关参数/ 395　

7.3　互连网络物理层/ 397　

7.3.1　消息结构/ 397　

7.3.2　物理层流控制/ 397　

7.4　互连网络交换层/ 398　

7.4.1　互连网络交换层功能与架构/ 398　

7.4.2　互连网络交换层技术/ 399　

7.5　互连网络路由层/ 402　

7.5.1　互连网络拓扑结构/ 402　

7.5.2　互连网络路由方式/ 409　

7.5.3　路由协议结构/ 410　

7.5.4　蝴蝶形拓扑结构路由算法/ 411　

7.5.5　维序路由算法/ 412　

7.5.6　死锁问题/ 413　

7.6　互连网络软件层/ 415　

7.6.1　互连网络软件层架构/ 415　

7.6.2　性能分析/ 417　

7.7　本章小结/ 418　

7.8　思考题/ 419　

第8章　并行计算机系统的资源调度

8.1　引言/ 422　

8.2　相关工作/ 425　

8.2.1　延迟敏感型应用延迟测量与建模/ 426　

8.2.2　数据中心干扰的测度方法/ 427　

8.2.3　资源管理使能技术/ 427

8.2.4　资源调度策略/ 429

8.3　延迟敏感型应用分析与建模/ 432　

8.3.1　延迟敏感型应用概述/ 433　

8.3.2　延迟敏感型应用延迟的组成及影响因素/ 435　

8.3.3　平均延迟与尾延迟的关系/ 436　

8.3.4　Littles law的尾延迟形式/ 441　

8.4　数据中心干扰的测度/ 444　

8.4.1　信息熵与系统熵/ 445　

8.4.2　场景1：仅存在延迟敏感型应用时/ 445　

8.4.3　场景2：仅存在尽力交付型应用时/ 446　

8.4.4　场景3：延迟敏感型和尽力交付型应用混合运行时/ 447　

8.4.5　系统熵的优点/ 447　

8.5　资源调度策略/ 449　

8.5.1　调度方法/ 450　

8.5.2　实验验证/ 453　

8.6　本章小结/ 459　

8.7　思考题/ 460　

参考文献/ 460　

第9章　并行输入输出

9.1　引言/ 468　

9.2　I/O软件栈/ 468　

9.3　并行文件系统/ 469　

9.4　常见并行文件系统/ 475　

9.4.1　并行虚拟文件系统PVFS/ 475　

9.4.2　通用并行文件系统GPFS/ 478　

9.4.3　集群文件系统Lustre/ 479　

9.5　POSIX/ 482　

9.6　MPI-I/O/ 483　

9.6.1　MPI-I/O的特性/ 483　

9.6.2　MPI-I/O示例/ 485　

9.6.3　MPI-I/O的底层读写优化/ 487　

9.7　PnetCDF/ 490　

9.8　本章小结/ 495　

9.9　思考题/ 496　

参考文献/ 496　

第10章　高速缓存一致性、同步和事务性内存

10.1　引言/ 498　

10.2　高速缓存一致性/ 498　

10.2.1　基于总线的一致性协议/ 500　

10.2.2　基于目录的一致性协议/ 502　

10.3　目录结构/ 503　

10.3.1　全映射位向量目录/ 503　

10.3.2　有限指针目录/ 504　

10.3.3　链式目录/ 505　

10.3.4　粗糙向量目录/ 506　

10.3.5　树形压缩向量目录/ 506　

10.3.6　单级混合目录/ 507　

10.3.7　多级目录/ 508　

10.4　实现高速缓存一致的典型系统/ 511　

10.4.1　Dash/ 511　

10.4.2　Origin 2000/ 512　

10.4.3　Alewife/ 513　

10.4.4　Exemplar X/ 514　

10.4.5　NUMA-Q/ 514　

10.5　同步原语和锁机制/ 515　

10.5.1　同步原语/ 515　

10.5.2　互斥锁的实现/ 516　

10.5.3　栅障/ 520　

10.5.4　实验——无锁算法/ 524　

10.5.5　并行软件优化/ 533　

10.6　事务性内存/ 537　

10.6.1　事务性内存的特性/ 537　

10.6.2　事务性内存的优点/ 538　

10.6.3　事务性内存的实现/ 543　

10.7　本章小结/ 549　

10.8　思考题/ 549　

参考文献/ 550　

第11章　量子并行计算

11.1　引言/ 554　

11.2　对量子力学的基本理解/ 555　

11.2.1　量子力学与经典力学有本质区别/ 555　

11.2.2　量子计算的优势在于并行/ 555　

11.2.3　量子的概念/ 555　

11.2.4　不确定性原理/ 556　

11.2.5　对叠加态的理解/ 558　

11.2.6　张量积/ 561　

11.2.7　左矢与右矢/ 561　

11.3　几种重要的熵及其联系/ 563　

11.3.1