多核计算与程序设计

图书标准信息

• 作者 周伟明 著
• 出版社 华中科技大学出版社
• 出版时间 2009-03
• 版次 1
• ISBN 9787560950969
• 定价 88.00元
• 装帧 平装
• 开本 16开
• 纸张 胶版纸
• 页数 656页
• 字数 900千字
• 正文语种 简体中文
• 丛书 华中科技大学出版社计算机丛书

【内容简介】

　　《多核计算与程序设计》主要介绍适应于多核（或多处理器）计算机系统的算法和程序，共分为五个部分进行讲解。第1部分介绍多核编程的基础知识，包括多核编程常见问题、锁竞争、加速比、负载均衡等基本概念，多线程退出算法、读写锁、旋转锁、原子操作等多线程编程基础知识，基于OpenMP标准的并行程序设计基础等；
　　第2部分介绍基础的数据结构与算法，包括数组、链表、哈希表、二叉树、AVL树、复合二叉树等基本数据结构，在链表那章中还讲解了多线程并行遍历的基本方法。
　　第3部分介绍多核并行计算方面的基础知识，并行编程包括常用的编程模式如分治模式、流水线模式、任务图分解与调度模式、动态任务调度模式等，并行搜索包括顺序搜索及终止检测算法，并行最短路径搜索等，并行排序包括并行快速排序、并行归并排序、并行基数排序等，并行数值计算包括并行矩阵乘法、并行前缀和计算等方面的内容。本部分介绍的各种并行算法和程序中，重点介绍如何解决多核系统中的计算随CPU核数的扩展性，CPUCache伪共享方面的问题。
　　第4部分介绍多核共享资源计算方面的内容，也是《多核计算与程序设计》中最重要的内容，讲解了分布式计算设计模式如线程分组竞争模式、条件同步模式、批量私有化处理模式、数据本地化模式等。这部分中讲解了《多核计算与程序设计》中几个最重要的程序：分布式队列中实现了自动让每个线程带有一个本地队列、分布式查找中介绍了分段锁的哈希表、动态负载平衡的分布式查找等，分布式内存管理则介绍了适应多核的内存管理方案，尤其是基于抢夺式的分布式内存管理算法，在分配和释放共享内存时也几乎不需要使用锁，性能优异。
　　第5部分介绍任务分解与调度方面的知识，这也是《多核计算与程序设计》中最重要的内容，包括任务图分解与调度的实现方法，动态任务分解与调度的实现方法等。其中还介绍了使用动态嵌套任务调度进行并行计算的方法，给出了用动态嵌套任务调度实现ParallelForo、并行快速排序、并行归并的实例。
　　最后一章中还介绍了Lock-Free编程（使用CAS原子操作进行编程）的基础知识，如ABA问题，内存删除问题等，并给出了一个Lock-Free的队列的实现实例。

【作者简介】

　　周伟明，1994年毕业于上海交通大学，曾就职于美国加州的DASCOMInc．公司和华为技术有限公司等企业。担任过网络安全软件、网络服务器软件、机器翻译软件、工具软件、嵌入式系统软件等研发工作，亲自编写过的源代码逾40万行。著有《多任务下的数据结构与算法》（华中科技大学出版社出版）、《软件测试实践》（电子工业出版社出版）。

【目录】

第1部分基础知识
1多核计算概述
1.1多核CPU概述
1.1.1多核计算将成为发展趋势
1.1.2多核CPU硬件架构介绍
1.1.3多核给程序员带来的机遇和挑战
1.2多核编程会遇到那些问题
1.2.1并发性问题
1.2.2CPU饥饿问题
1.2.3任务的分解与调度问题
1.2.4加速比性能问题
1.2.5节能环保问题
1.2.6扩展性问题
1.3多核编程与单核多线程编程的区别
1.3.1锁竞争导致的串行化的区别
1.3.2线程分解与执行的区别
1.3.3CPU核负载平衡的区别
1.3.4任务调度策略的区别
1.3.5CPUCache存取的区别（伪共享问题）
1.3.6任务优先级抢占的区别
1.3.7串行计算与并行及分布式计算的区别
1.4多核编程与多机分布式编程的区别
1.4.1共享存储与分布式存储的区别
1.4.2分布式计算的区别
1.4.3编程环境上的区别
1.5加速比系数
1.5.1阿姆达尔定律
1.5.2Gustafson定律
1.5.3阿姆达尔定律和Gustafson定律的等价性
1.5.4Karp-Flatt度量
1.5.5实际情况中影响加速比系数的因素
1.5.6并行计算开销情况下的加速比
1.6锁竞争问题及对加速比的影响
1.6.1线程粒度因子与锁粒度因子
1.6.2锁竞争的性能情况
1.6.3集中式锁竞争中的加速比分析
1.6.4随机锁竞争中的加速比分析
1.6.5分布式锁竞争的加速比分析
1.6.6无锁编程的加速比分析
1.7负载平衡问题对加速比的影响
1.7.1影响负载平衡的主要因素
1.7.2负载平衡的评价指标
1.7.3负载平衡情况下的加速比
1.8参考文献

2多线程编程基础
2.1多线程编程基本概念
2.1.1线程
2.1.2锁
2.1.3各种系统中常用的锁操作及信号量操作函数
2.1.4用C++实现锁的自动释放
2.1.5原子操作
2.1.6锁与原子操作的区别
2.1.7有锁计算、无锁计算与本地计算的概念
2.2各种锁性能比较
2.2.1各种锁在单线程情况下的性能
2.2.2各种锁在多线程集中式锁竞争情况下的性能
2.2.3各种锁在多线程分布式锁竞争情况下的性能
2.3读写锁算法
2.3.1读写锁概念的引出
2.3.2读写锁算法的分析和实现
2.3.3读写锁的编码实现
2.4多线程退出算法
2.4.1单个子线程退出算法
2.4.2多个线程访问共享资源时的退出
2.4.3有锁的多线程资源释放退出算法实现
2.4.4无锁的退出算法
2.4.5多线程退出算法的使用
2.5参考文献

3OpenMP程序设计
3.1OpenMP基本概念
3.1.1fork/join并行执行模式的概念
3.1.2内存模型
3.1.3性能例子
3.1.4编译器对OpenMP的支持
3.2OpenMP编程模型
3.2.1OpenMP编译指导语句格式
3.2.2OpenMP主要命令
3.2.3OpenMP主要子句
3.2.4OpenMP主要库函数
3.3线程创建与工作分摊
3.3.1parallel命令
3.3.2for和parallelfor命令
3.3.3if子句（条件执行并行）
3.3.4动态设置并行循环的线程数量
3.3.5循环并行化的问题
3.3.6sections和section命令
3.3.7single命令
3.3.8master命令
3.4数据处理
3.4.1private子句
3.4.2firstprivate子句
3.4.3lastprivate子句
3.4.4threadprivate子句
3.4.5shared子句
3.4.6default子句
3.4.7reduction子句
3.4.8copyin子句
3.4.9copyprivate子句
3.5任务调度
3.5.1Schedule子句用法
3.5.2静态调度(static)
3.5.3动态调度(dynamic)
3.5.4guided调度（guided）
3.5.5runtime调度（rumtime）
3.5.6任务调度与伪共享问题
3.6线程间的同步
3.6.1barrier命令
3.6.2critical命令
3.6.3atomic命令
3.6.4ordered命令和子句
3.6.5nowait子句
3.6.6flush命令
3.7OpenMP库函数详解
3.7.1执行环境函数
3.7.2锁操作函数
3.7.3时间操作函数
3.8OpenMP环境变量
3.8.1OMP_DYNAMIC
3.8.2OMP_NUM_THREADS
3.8.3OMP_NESTED
3.8.4OMP_SCHEDULE
3.9OpenMP内部控制变量及相关流程
3.9.1内部控制变量
3.9.2任务调度流程
3.9.3线程数量决定流程
3.10参考文献

第2部份基础数据结构与算法
4数组
4.1栈
4.1.1栈的基本概念
4.1.2栈的编码实现
4.1.3多线程栈的实现
4.2对数组进行快速排序
4.2.1排序算法介绍
4.2.2串行快速排序基本思想
4.2.3串行快速排序的代码实现
4.2.4非递归的快速排序算法
4.2.5快速排序算法的复杂度分析
4.3对数组进行查找
4.3.1顺序查找
4.3.2二分查找
4.4实例：用数组管理一个HOOK功能
4.4.1单个函数的HOOK实现
4.4.2多个函数的HOOK实现
4.4.3HOOK功能的应用简介
4.4.4HOOK使用的注意事项
4.5参考文献

5链表
5.1单向链表
5.1.1存储表示
5.1.2接口设计
5.1.3添加节点到链表头部
5.1.4基本功能编码实现
5.2单向链表的排序
5.2.1插入排序
5.2.2归并插入排序
5.3双向链表
5.3.1双向链表的基本概念
5.3.2双向链表的设计
5.3.3双向链表的操作接口
5.3.4双向链表的编码实现
5.4链表的逐个节点遍历
5.4.1逐个节点遍历基本概念
5.4.2逐个节点遍历编码实现
5.5多线程遍历算法
5.5.1多线程链表的设计和编码实现
5.5.2多线程链表的4种遍历方案
5.5.3多个线程同时遍历的情况
5.6实例：使用链表管理短信息系统的CACHE
5.6.1短信息系统的CACHE管理基本概念
5.6.2短信息系统的发送和接收分析
5.6.3短信息系统CACHE管理的编码实现

6哈希表
6.1哈希表
6.1.1哈希表的基本概念
6.1.2哈希表的索引方法
6.1.3哈希表的冲突解决方法
6.1.4哈希表基本操作的源代码
6.2哈希链表
6.2.1哈希表和数组、链表的效率比较
6.2.2时间效率和空间效率的关系
6.2.3哈希链表的基本概念
6.2.4哈希链表的操作
6.2.5哈希链表的编码实现
6.3实例：WebServer的动态CACHE文件管理
6.3.1WebServer的动态CACHE文件管理基本概念
6.3.2CACHE文件管理功能的设计
6.3.3CACHE文件管理功能的编码实现
6.4参考文献

7普通树与二叉树
7.1普通树
7.1.1普通树的描述方法
7.1.2树的操作接口设计
7.1.3树的遍历算法
7.1.4树的编码实现
7.1.5使用树的遍历算法来实现Xcopy功能
7.2二叉树
7.2.1二叉树的基本概念
7.2.2二叉树的树梢及二叉树的高度
7.2.3二叉树的描述方法
7.3二叉排序树
7.3.1二叉排序树的基本概念
7.3.2二叉排序树的查找
7.3.3二叉排序树的插入
7.3.4二叉排序树的删除
7.3.5二叉排序树的遍历
7.3.6二叉排序树的旋转操作

8AVL搜索树
8.1AVL搜索树的基本概念
8.2AVL搜索树的插入
8.2.1插入操作需要考虑的问题
8.2.2不存在不平衡节点的情况分析
8.2.3不平衡A节点的情况分析
8.2.4存在不平衡节点的四种情况分析
8.2.5LL型不平衡情况的调整
8.2.6LR型不平衡情况的调整
8.2.7插入操作的伪代码描述
8.3AVL搜索树的删除
8.3.1A节点的确定
8.3.2几种不平衡情况的分析
8.3.3L0型调整分析
8.3.4L-1型调整分析
8.3.5L1型调整分析
8.3.6删除操作的伪代码描述
8.4负载平衡的AVL树
8.4.1基本概念的引出
8.4.2插入操作中负载因子的调整
8.4.3删除操作中负载因子的调整
8.4.4L0和L-1型调整分析
8.4.5L1型调整分析
8.5AVL树的源代码
8.5.1数据结构定义
8.5.2创建、释放、查找等操作
8.5.3旋转操作函数
8.5.4插入操作函数
8.5.5删除操作函数
8.6参考文献

9复合二叉树
9.1哈希红黑树
9.1.1哈希红黑树的基本概念
9.1.1哈希红黑树的查找
9.1.3哈希红黑树的插入
9.1.4哈希红黑树的删除
9.1.5哈希红黑树的释放
9.1.6哈希红黑树的遍历
9.1.7哈希红黑树的编码实现
9.1.8哈希红黑树的效率分析
9.2哈希AVL树
9.2.1哈希AVL树的基本概念
9.2.2哈希AVL树的查找
9.2.3哈希AVL树的插入
9.2.4哈希AVL树的删除
9.2.5哈希AVL树的释放
9.2.6哈希AVL树的遍历
9.2.7哈希AVL树的编码实现
9.3复合数据结构的分类
9.4抗DoS/DdoS攻击的实例
9.4.1DoS/DdoS攻击的概念
9.4.2常见DoS/DdoS攻击手段及防范策略
9.4.3抗DoS/DdoS攻击的实现
9.4.4抗DoS/DdoS攻击的编码实现
9.5参考文献

第3部分并行计算
10并行程序设计模式
10.1基本概念
10.1.1强并行计算与弱并行计算
10.1.2并行程序设计模式的基本思路
10.2模式数据分解模式
10.3分治模式
10.3.1子问题求解时的负载平衡问题
10.3.2子问题的解的合并可能引起的串行化问题
10.4流水线模式
10.5任务并行模式
10.6任务调度模式
10.6.1任务图调度模式
10.6.2动态任务调度模式

11并行搜索
11.1并行顺序搜索
11.1.1并行搜索指定数据
11.1.2并行搜索最大数
11.1.3终止检测算法
11.2串行Dijkstra最短路径搜索
11.2.1Dijkstra最短路径算法的描述
11.2.2Dijkstra最短路径算法的过程图解
11.2.3伪代码描述
11.2.4算法流程图
11.2.5C/C++代码实现
11.3并行最短路径算法
11.3.1Dijkstra算法的并行化
11.3.2并行Dijkstra算法的代码实现
11.3.3其他并行最短路径算法的介绍和分析
11.4参考文献

12并行排序
12.1并行排序概述
12.2冒泡排序
12.2.1串行冒泡排序
12.2.2奇偶排序
12.3快速排序
12.3.1串行快速排序基本思想
12.3.2串行快速排序的代码实现
12.3.3快速排序并行化方法
12.3.4开源项目mcstl中的并行快速排序
12.3.5基于任务窃取的快速排序
12.4并行归并排序
12.4.1串行归并算法
12.4.2Cole并行归并算法
12.4.3并行快速归并排序
12.5基数排序
12.5.1串行链式基数排序
12.5.2串行数组基数排序
12.5.3一步到位的分层排序
12.5.4负载平衡的并行基数排序
12.5.5分区的并行基数排序

13并行数值计算
13.1多核并行数值计算面临的问题
13.1.1Cache的命中率问题
13.1.2伪共享问题
13.2求和及前缀求和
13.3矩阵相加
13.4矩阵相乘
13.4.1基本概念
13.4.2串行算法
13.4.3并行算法
13.5矩阵向量相乘
13.6并行随机数生成
13.7参考文献

第4部分共享资源分布式计算
14分布式计算设计模式
14.1基本概念
14.1.1共享资源的计算分解
14.1.2共享资源计算的负载均衡问题
14.1.3共享资源计算的算法设计思路与方法
14.2线程分组竞争模式
14.2.1标准的线程分组竞争模式
14.2.2线程分组竞争模式的变种
14.3线程随机竞争模式
14.3.1基本概念
14.3.2加速比性能的保证
14.4数据本地化模式
14.4.1取得比单核多线程更好的性能
14.4.2数据本地化模式
14.4.3优缺点分析
14.5分布式数据结构设计
14.5.1复合数据结构设计方法
14.5.2分布式数据结构设计
14.5.3分布式数据结构主要问题
14.6参考文献

15分布式队列
15.1串行队列
15.1.1简单环形队列
15.1.2STL中的Deque
15.1.3动态环形队列
15.2队列池
15.2.1共享队列
15.2.2消息队列
15.2.3队列池
15.2.4队列池的几种实现方案
15.2.5队列池的使用实例
15.3带本地计算的分布式队列
15.3.1基本思想
15.3.2本地化队列的实现
15.3.3任务偷取队列的实现
15.3.4分布式队列的实现
15.3.5线程池CThreadPool的实现
15.3.6线程池CThreadPool的代码实现
15.3.7CDistributedQueue源代码
15.3.8CDistributedQueue的使用实例

16分布式查找
16.1多核中查找的问题与主要思路
16.2静态负载平衡的二级查找结构设计
16.2.1二级查找结构设计
16.2.2分布式哈希AVL树
16.2.3分布式顺序AVL树
16.3动态负载平衡的多级查找结构设计
16.3.1分布式查找中的负载平衡问题
16.3.2多级查找结构设计方法
16.3.3多级查找表的查找算法
16.3.4多级查找表的插入操作算法
16.3.5多级查找表的删除操作算法
16.3.6多级顺序表
16.3.7多级索引AVL树
16.3.8分布式哈希多级AVL树
16.3.9分布式顺序多级AVL树
16.4多核环境中查找算法的选用方法
16.5动态WebCache设计实例

17分布式内存管理
17.1多核内存管理的基本思想
17.1.1内存管理方面的需求
17.1.2多核系统中的内存管理思路
17.2等尺寸内存管理
17.2.1Freelist内存管理基本概念
17.2.2Freelist编码实现
17.2.3FreeLists内存管理
17.3Intel开源项目TBB中的内存管理
17.3.1伪共享问题
17.3.2Cache对齐的内存管理
17.3.3数据结构
17.3.4将内存管理器映射到线程
17.3.5分配和释放算法
17.3.6线程退出时的内存回收
17.4抢夺式内存管理算法
17.4.1算法基本思想
17.4.2碎片重组回收利用技术
17.4.3抢夺式算法的详细算法流程
17.4.4代码实现
17.5伪共享问题的深入分析
17.5.1内存释放时的伪共享问题
17.5.2伪共享问题的概率分析
17.5.3用户程序使用内存过程中的伪共享问题
17.5.4分布式内存管理的进一步改进措施
17.6参考文献

第5部分任务分解与调度
18任务图分解与调度
18.1任务分解与调度的问题
18.1.1使用OpenMP调度的问题
18.1.2任务图调度模型
18.1.3任务图调度算法简介
18.2任务组调度算法
18.2.1基本思路
18.2.2任务组调度算法
18.2.3算法流程图
18.2.4数据结构与接口设计
18.2.5代码实现
18.2.6任务组调度的应用分析
18.2.7误差下降调度算法
18.3任务图调度算法
18.3.1任务图的分层算法
18.3.2分层算法过程图解
18.3.3数据结构和接口设计
18.3.4分层算法的代码实现
18.3.5任务调度器的代码实现
18.3.6实例：任务图调度器的使用
18.4手工任务分解的原则和方法
18.4.1任务间负载均衡的影响因素
18.4.2任务分解原则和方法
18.5参考文献

19动态任务分解与调度
19.1动态任务分解的两种类型
19.2非嵌套型动态任务调度
19.2.1网络服务器软件中的任务调度
19.2.2使用分布式队列的调度方法
19.2.3CTaskScheduler的设计
19.2.4CTaskScheduler的代码实现
19.3嵌套型动态任务调度
19.3.1基本思想
19.3.2CNestTaskScheduler的设计
19.3.3CNestTaskScheduler的代码实现
19.3.4CNestTaskScheduler使用方法
19.4实例：用任务调度器实现parallel_for
19.4.1parallel_for的实现
19.4.2用parallel_for进行并行快速排序
19.4.3用parallel_for进行并行归并
19.5参考文献

20Lock-Free编程基础
20.1Lock-Free编程基本概念和问题
20.1.1CAS原子操作
20.1.2ABA问题
20.1.3ABA问题的解决方法
20.1.4内存删除问题
20.1.5数据竞争问题
20.2Lock-Free的队列
20.2.1无锁队列的链式实现方法
20.2.2串行实现方法
20.2.3出队操作的Lock-Free实现
20.2.4进队操作的Lock-Free实现
20.2.5CLockFreeQueue的实现代码
20.3Lock-Free程序的问题分析
20.4参考文献
附录1本书代码和CAPI开源项目源文件对照表
附录2多核编程的四层境界