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

推荐序一
推荐序二
前言
第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