《多核与GPU编程：工具、方法及实践》附录

本书覆盖广泛的关键并行计算技术：多核CPU编程和众核“大规模并行”技术。通过使用线程、OpenMP、MPI和CUDA，本书讲述能够利用当今的计算平台来结合CPU和GUP硬件的软件的设计与开发，解释如何从顺序编程范式转换到并行计算范式。

由于功耗墙、散热墙等因素的限制，单纯提升单核处理器的性能已经越来越困难，因此多核/众核架构成为计算机体系结构发展的重要趋势。然而，多核/众核处理器在带来更高计算能力的同时，也增加了并行软件开发、分析和优化的难度。随着多核/众核处理器的普及以及并行计算集群应用的日益广泛，如何编写正确、高效的并行程序已经成为软件开发人员面临的一大挑战，同时并行程序的调试、剖析也日益成为并行软件开发的难题。并行程序开发和优化的本质是实现算法特征向底层硬件架构特征的高效映射，这就对并行软件开发人员提出了更高的要求，他们不仅要了解算法特征，还要对底层架构有着清晰的认识。这无疑增加了并行软件开发的难度。

本书作者Gerassimos Barlas博士是阿联酋沙迦美国大学计算机科学与工程系的教授，其研究方向包括并行算法及并行软件的设计与开发、负载均衡模型框架研究等。Gerassimos Barlas博士具有10年以上的并行软件开发和教学经验，并且在并行与分布式系统的可分负载理论等领域非常活跃。

本书从并行软件的实现、调试、优化和剖析四个方面，详细讨论了当前主要的并行计算关键技术，包括CPU多核编程、分布式内存编程、GPU编程、负载均衡等。同时针对并行软件的开发效率，本书也详细介绍了Qt 线程、Thrust和Boost MPI等库和工具。面对当今异构计算平台的架构特点，书中既讲解了选择合适的工具开发高性能并行软件的步骤和方法，同时提供了大量的实际案例，更加深入地讨论不同编程和优化技术的应用方法。通过阅读本书，读者可以学习：如何使用库或者指令制导方式创建多核应用，如何使用MPI开发运行在分布式内存系统上的应用程序，如何使用CUDA开发高性能GPU程序，如何实现负载均衡，以及如何针对目标多核平台进行程序剖析和调试等。总之，本书作者根据自己多年的并行编程经验，从开发优秀并行软件的本质出发，以通俗易懂的方式对最为关键的基本知识和技术进行了细致讲解。本书既可成为并行软件初学者的参考书籍，也可供具有一定并行编程经验的软件开发人员参考。
由于时间仓促，而且书中某些术语目前业界没有统一译法，所以我们对一些术语采取了保留其英文名称的方法。书中翻译方面的错误和不妥之处，恳请广大读者不吝批评指正。

封面图

目录

• 译者序
• 前言
• 第1章概述1
• 1.1多核计算机时代1
• 1.2并行计算机的分类3
• 1.3现代计算机概览4
• 1.3.1Cell BE处理器5
• 1.3.2NVIDIA Kepler6
• 1.3.3AMD APU9
• 1.3.4从多核到众核：Tilera TILE-Gx8072和Intel Xeon Phi10
• 1.4性能指标12
• 1.5并行程序性能的预测与测量16
• 1.5.1Amdahl定律18
• 1.5.2Gustafson-Barsis定律20
• 第2章多核和并行程序设计23
• 2.1引言23
• 2.2PCAM方法学24
• 2.3分解模式26
• 2.3.1任务并行27
• 2.3.2分而治之分解28
• 2.3.3几何分解30
• 2.3.4递归数据分解32
• 2.3.5流水线分解35
• 2.3.6基于事件的合作分解39
• 2.4程序结构模式39
• 2.4.1单程序多数据40
• 2.4.2多程序多数据40
• 2.4.3主/从41
• 2.4.4map-reduce41
• 2.4.5fork/join42
• 2.4.6循环并行44
• 2.5匹配分解模式和程序结构模式44
• 第3章共享内存编程：线程46
• 3.1引言46
• 3.2线程48
• 3.2.1线程的定义48
• 3.2.2线程的作用49
• 3.2.3线程的生成和初始化49
• 3.2.4在线程间共享数据55
• 3.3设计考虑57
• 3.4信号量58
• 3.5经典问题中的信号量62
• 3.5.1生产者–消费者63
• 3.5.2终止处理66
• 3.5.3理发师问题：引入公平性75
• 3.5.4读者–写者问题80
• 3.6monitor84
• 3.6.1设计方法1：monitor内部的关键区87
• 3.6.2设计方法2：monitor控制关键区的入口87
• 3.7经典问题中的monitor91
• 3.7.1重新考虑生产者–消费者问题91
• 3.7.2重新考虑读者–写者问题95
• 3.8动态线程管理与静态线程管理102
• 3.8.1Qt线程池102
• 3.8.2线程池的创建和管理103
• 3.9调试多线程应用111
• 3.10高层次结构：无须显式利用线程的多线程编程115
• 3.10.1并发map116
• 3.10.2map-reduce118
• 3.10.3并发过滤120
• 3.10.4filter-reduce121
• 3.10.5案例研究：多线程存储122
• 3.10.6案例研究：多线程图像匹配131
• 第4章共享内存编程：OpenMP140
• 4.1引言140
• 4.2第一个OpenMP程序141
• 4.3变量作用域144
• 4.3.1定积分OpenMP版本V.0：人工划分146
• 4.3.2定积分OpenMP版本 V.1：无竞争条件的人工划分147
• 4.3.3定积分OpenMP V.2：基于锁的隐式划分148
• 4.3.4定积分OpenMP V.3：基于归约的隐式划分150
• 4.3.5变量作用域总结151
• 4.4循环级并行152
• 4.4.1数据依赖154
• 4.4.2嵌套循环162
• 4.4.3调度162
• 4.5任务并行166
• 4.5.1sections指令166
• 4.5.2task指令171
• 4.6同步结构177
• 4.7正确性与优化问题183
• 4.7.1线程安全183
• 4.7.2假共享187
• 4.8案例研究：OpenMP中的排序算法192
• 4.8.1自下而上归并排序算法的OpenMP实现192
• 4.8.2自上而下归并排序算法的OpenMP实现195
• 4.8.3性能评估200
• 第5章分布式内存编程203
• 5.1通信进程203
• 5.2MPI204
• 5.3核心概念205
• 5.4你的第一个MPI程序206
• 5.5程序体系结构208
• 5.5.1SPMD208
• 5.5.2MPMD209
• 5.6点对点通信210
• 5.7可选的点对点通信模式214
• 5.8非阻塞通信216
• 5.9点对点通信小结220
• 5.10错误报告与处理220
• 5.11集合通信简介222
• 5.11.1分发226
• 5.11.2收集231
• 5.11.3归约233
• 5.11.4多对多收集237
• 5.11.5多对多分发240
• 5.11.6多对多归约245
• 5.11.7全局同步245
• 5.12通信对象245
• 5.12.1派生数据类型246
• 5.12.2打包/解包253
• 5.13节点管理：通信器和组254
• 5.13.1创建组255
• 5.13.2建立内部通信器257
• 5.14单边通信259
• 5.14.1RMA通信函数261
• 5.14.2RMA同步函数262
• 5.15I/O注意事项270
• 5.16MPI多进程和多线程混合编程276
• 5.17时序和性能测量279
• 5.18调试和分析MPI程序279
• 5.19Boost.MPI库283
• 5.19.1阻塞和非阻塞通信285
• 5.19.2 数据序列化289
• 5.19.3 集合通信292
• 5.20案例研究：有限扩散聚合模型295
• 5.21案例研究：暴力加密破解300
• 5.21.1版本1：“基本型”MPI300
• 5.21.2版本2：MPI与OpenMP的结合305
• 5.22案例研究：主/从式并行模型的MPI实现308
• 5.22.1简单主/从式设置309
• 5.22.2多线程主/从式设置316
• 第6章GPU编程333
• 6.1GPU编程简介333
• 6.2CUDA编程模型：线程、线程块、线程网格335
• 6.3CUDA执行模型：流多处理器和warp340
• 6.4CUDA程序编译过程344
• 6.5构建CUDA项目347
• 6.6内存层次结构349
• 6.6.1本地内存/寄存器355
• 6.6.2共享内存356
• 6.6.3常量内存363
• 6.6.4texture和surface内存368
• 6.7优化技术369
• 6.7.1线程组织设计369
• 6.7.2kernel结构378
• 6.7.3共享内存访问382
• 6.7.4全局内存访问388
• 6.7.5page-locked与zero-copy内存392
• 6.7.6统一内存394
• 6.7.7异步执行和流397
• 6.8动态并行403
• 6.9CUDA程序的调试407
• 6.10CUDA程序剖析410
• 6.11CUDA和MPI412
• 6.12案例研究417
• 6.12.1分形集合计算417
• 6.12.2块加密算法426
• 第7章Thrust模板库452
• 7.1引言452
• 7.2使用Thrust的第一步453
• 7.3Thrust数据类型456
• 7.4Thrust算法459
• 7.4.1变换算法460
• 7.4.2排序与查询463
• 7.4.3归约468
• 7.4.4scan /前缀和471
• 7.4.5数据管理与处理472
• 7.5花式迭代器475
• 7.6交换设备后端480
• 7.7案例研究481
• 7.7.1蒙特卡洛积分481
• 7.7.2DNA序列比对485
• 第8章负载均衡493
• 8.1引言493
• 8.2动态负载均衡：Linda的遗赠494
• 8.3静态负载均衡：可分负载理论方法495
• 8.3.1建模开销496
• 8.3.2通信设置502
• 8.3.3分析503
• 8.3.4总结 ：简短的文献综述510
• 8.4DLTlib：分割工作负载的库513
• 8.5案例研究516
• 8.5.1Mandelbrot集“电影”的混合计算：动态负载均衡案例研究516
• 8.5.2分布式块加密：静态负载均衡案例研究526
• 在线资源
• 附录A编译Qt程序
• 附录B运行MPI程序：准备与配置步骤
• 附录C测量时间
• 附录DBoost.MPI
• 附录ECUDA环境搭建
• 附录FDLTlib
• 术语表
• 参考文献