多核计算与程序设计

图书信息

图书特色

《多核计算与程序设计》特色内容是并行遍历的基本方法，常见并行算法如并行搜索、并行排序、并行数值计算等在多核系统中的实现。 共享资源分布式计算的基本编程模式和方法，分布式队列，它能自动给每个线程赋予一个本地队列，它是基于偷取的共享队列和队列池来实现的。 分布式查找，包括分段锁的哈希表，动态负载平衡的多级查找等。 分布式内存管理，它自动给每个线程生成一个本地的内存管理器，并且几乎不需要使用锁进行内存分配和释放（抢夺式内存管理）。 任务图分解与调度及实现方法，非嵌套任务调度，可用于网络服务器软件等地方进行任务调度。 嵌套任务调度，是另一种更广泛的任务调度方法，可以用它实现各种并行计算。 各种程序和算法中的伪共享问题的处理，Lock-Free编程基础知识。

内容简介

多核计算与程序设计。内容简介：本书主要介绍适应于多核（或多处理器）计算机系统的算法和程序，共分为五个部分进行讲解。

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

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

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

第4部分介绍多核共享资源计算方面的内容，也是本书中*重要的内容，讲解了分布式计算设计模式如线程分组竞争模式、条件同步模式、批量私有化处理模式、数据本地化模式等。这部分中讲解了本书中几个*重要的程序：分布式队列中实现了自动让每个线程带有一个本地队列、分布式查找中介绍了分段锁的哈希表、动态负载平衡的分布式查找等，分布式内存管理则介绍了适应多核的内存管理方案，尤其是基于抢夺式的分布式内存管理算法，在分配和释放共享内存时也几乎不需要使用锁，性能优异。 第5部分介绍任务分解与调度方面的知识，这也是本书中*重要的内容，包括任务图分解与调度的实现方法，动态任务分解与调度的实现方法等。其中还介绍了使用动态嵌套任务调度进行并行计算的方法，给出了用动态嵌套任务调度实现parallel_for()、并行快速排序、并行归并的实例。

*后一章中还介绍了lock-free编程（使用cas原子操作进行编程）的基础知识，如aba问题，内存删除问题等，并给出了一个lock-free的队列的实现实例。

本书的特色内容：1、并行遍历的基本方法。2、常见并行算法如并行搜索、并行排序、并行数值计算等在多核系统中的实现。3、共享资源分布式计算的基本编程模式和方法。4、分布式队列，它能自动给每个线程赋予一个本地队列，它是基于偷取的共享队列和队列池来实现的。5、分布式查找，包括分段锁的哈希表，动态负载平衡的多级查找等。6、分布式内存管理，它自动给每个线程生成一个本地的内存管理器，并且几乎不需要使用锁进行内存分配和释放（抢夺式内存管理）。7、任务图分解与调度及实现方法。8、非嵌套任务调度，可用于网络服务器软件等地方进行任务调度。9、嵌套任务调度，是另一种更广泛的任务调度方法，可以用它实现各种并行计算。10、各种程序和算法中的伪共享问题的处理。11、lock-free编程基础知识。

目录

1. 多核计算与程序设计 目录
2. 第1部分 基础知识
3. 1 多核计算概述
4. 1.1 多核CPU概述
5. 1.1.1 多核计算将成为发展趋势
6. 1.1.2 多核CPU硬件架构介绍
7. 1.1.3 多核给程序员带来的机遇和挑战
8. 1.2 多核编程会遇到那些问题
9. 1.2.1 并发性问题
10. 1.2.2 CPU饥饿问题
11. 1.2.3 任务的分解与调度问题
12. 1.2.4 加速比性能问题
13. 1.2.5 节能环保问题
14. 1.2.6 扩展性问题
15. 1.3 多核编程与单核多线程编程的区别
16. 1.3.1 锁竞争导致的串行化的区别
17. 1.3.2 线程分解与执行的区别
18. 1.3.3 CPU核负载平衡的区别
19. 1.3.4 任务调度策略的区别
20. 1.3.5 CPU Cache存取的区别（伪共享问题）
21. 1.3.6 任务优先级抢占的区别
22. 1.3.7 串行计算与并行及分布式计算的区别
23. 1.4 多核编程与多机分布式编程的区别
24. 1.4.1 共享存储与分布式存储的区别
25. 1.4.2 分布式计算的区别
26. 1.4.3 编程环境上的区别
27. 1.5 加速比系数
28. 1.5.1 阿姆达尔定律
29. 1.5.2 Gustafson定律
30. 1.5.3 阿姆达尔定律和Gustafson定律的等价性
31. 1.5.4 Karp-Flatt度量
32. 1.5.5 实际情况中影响加速比系数的因素
33. 1.5.6 并行计算开销情况下的加速比
34. 1.6 锁竞争问题及对加速比的影响
35. 1.6.1 线程粒度因子与锁粒度因子
36. 1.6.2 锁竞争的性能情况
37. 1.6.3 集中式锁竞争中的加速比分析
38. 1.6.4 随机锁竞争中的加速比分析
39. 1.6.5 分布式锁竞争的加速比分析
40. 1.6.6 无锁编程的加速比分析
41. 1.7 负载平衡问题对加速比的影响
42. 1.7.1 影响负载平衡的主要因素
43. 1.7.2 负载平衡的评价指标
44. 1.7.3 负载平衡情况下的加速比
45. 1.8 参考文献
46. 2 多线程编程基础
47. 2.1 多线程编程基本概念
48. 2.1.1 线程
49. 2.1.2 锁
50. 2.1.3 各种系统中常用的锁操作及信号量操作函数
51. 2.1.4 用C++实现锁的自动释放
52. 2.1.5 原子操作
53. 2.1.6 锁与原子操作的区别
54. 2.1.7 有锁计算、无锁计算与本地计算的概念
55. 2.2 各种锁性能比较
56. 2.2.1 各种锁在单线程情况下的性能
57. 2.2.2 各种锁在多线程集中式锁竞争情况下的性能
58. 2.2.3 各种锁在多线程分布式锁竞争情况下的性能
59. 2.3 读写锁算法
60. 2.3.1 读写锁概念的引出
61. 2.3.2 读写锁算法的分析和实现
62. 2.3.3 读写锁的编码实现
63. 2.4 多线程退出算法
64. 2.4.1 单个子线程退出算法
65. 2.4.2 多个线程访问共享资源时的退出
66. 2.4.3 有锁的多线程资源释放退出算法实现
67. 2.4.4 无锁的退出算法
68. 2.4.5 多线程退出算法的使用
69. 2.5 参考文献
70. 3 OpenMP程序设计
71. 3.1 OpenMP基本概念
72. 3.1.1 fork/join并行执行模式的概念
73. 3.1.2 内存模型
74. 3.1.3 性能例子
75. 3.1.4 编译器对OpenMP的支持
76. 3.2 OpenMP编程模型
77. 3.2.1 OpenMP编译指导语句格式
78. 3.2.2 OpenMP主要命令
79. 3.2.3 OpenMP主要子句
80. 3.2.4 OpenMP主要库函数
81. 3.3 线程创建与工作分摊
82. 3.3.1 parallel命令
83. 3.3.2 for和parallel for命令
84. 3.3.3 if子句（条件执行并行）
85. 3.3.4 动态设置并行循环的线程数量
86. 3.3.5 循环并行化的问题
87. 3.3.6 sections和section命令
88. 3.3.7 single命令
89. 3.3.8 master命令
90. 3.4 数据处理
91. 3.4.1 private子句
92. 3.4.2 firstprivate子句
93. 3.4.3 lastprivate子句
94. 3.4.4 threadprivate子句
95. 3.4.5 shared子句
96. 3.4.6 default子句
97. 3.4.7 reduction子句
98. 3.4.8 copyin子句
99. 3.4.9 copyprivate子句
100. 3.5 任务调度