第1部分介绍多核编程的基础知识，包括多核编程常见问题、锁竞争、加速比、负载均衡等基本概念，多执行绪退出算法、读写锁、旋转锁、原子操作等多执行绪编程基础知识，基于OpenMP标準的并行程式设计基础等；

第2部分介绍基础的数据结构与算法，包括数组、鍊表、哈希表、二叉树、AVL树、複合二叉树等基本数据结构，在鍊表那章中还讲解了多执行绪并行遍历的基本方法。

第3部分介绍多核并行计算方面的基础知识，并行编程包括常用的编程模式如分治模式、流水线模式、任务图分解与调度模式、动态任务调度模式等，并行搜寻包括顺序搜寻及终止检测算法，并行最短路径搜寻等，并行排序包括并行快速排序、并行归併排序、并行基数排序等，并行数值计算包括并行矩阵乘法、并行前缀和计算等方面的内容。本部分介绍的各种并行算法和程式中，重点介绍如何解决多核系统中的计算随CPU核数的扩展性，CPUCache伪共享方面的问题。

第4部分介绍多核共享资源计算方面的内容，也是《多核计算与程式设计》中最重要的内容，讲解了分散式计算设计模式如执行绪分组竞争模式、条件同步模式、批量私有化处理模式、数据本地化模式等。这部分中讲解了《多核计算与程式设计》中几个最重要的程式：分散式伫列中实现了自动让每个执行绪带有一个本地伫列、分散式查找中介绍了分段锁的哈希表、动态负载平衡的分散式查找等，分散式记忆体管理则介绍了适应多核的记忆体管理方案，尤其是基于抢夺式的分散式记忆体管理算法，在分配和释放共享记忆体时也几乎不需要使用锁，性能优异。

第5部分介绍任务分解与调度方面的知识，这也是《多核计算与程式设计》中最重要的内容，包括任务图分解与调度的实现方法，动态任务分解与调度的实现方法等。其中还介绍了使用动态嵌套任务调度进行并行计算的方法，给出了用动态嵌套任务调度实现ParallelForo、并行快速排序、并行归併的实例。

最后一章中还介绍了Lock-Free编程（使用CAS原子操作进行编程）的基础知识，如ABA问题，记忆体删除问题等，并给出了一个Lock-Free的伫列的实现实例。

第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多核编程的四层境界

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