目录第1部分基础知识1多核计算概述中曹要垂要11.1多核CPU概述(2)1.1.1多糍计算发展趋势…………(2)1.1.2多核CPU硬件架构介绍(4)1.1.3多核给程序员带来的机遘和挑战……(5)1.2多核编程会遇到的问题(7)2.1并发性问题特和中分十世由中书非非电,号·世唐图自非非国非面(8)1.2.2CPU饥饿问题……………………………………:11(81.2.3任务的分解与调度问题(9)1.2.4加速比性能问题…………………(10)1.2.5节能、环保问题…11)1.2.6扩展性问题:……………,想··世,数非排非道(12)1.3多核编程与单核多线程编程的区别(13)1.3.1锁竞争导致的串行化的区别………(13)1.3.2线程分解与执行的区别…"……(14)1.3.3CPU核负载平衡的区别………14)1.3.4任务调度策略的区别………………415)1.3.5 pU Cache存取的区别(伪共享问题)…………………………(16)1.3.6任务优先级抢占的区别(17)1.3.7串行计算与并行及分布式计算的区别…………………………………………(17)1.4多核编程与多机分布式编程的区别世雄(18)2多核计算与程序设计1.4.1共享存储与分布式存储的区别“…a面非“由和4非非E:形图鲁图,甲(181.4.2分布式计算的区别………………………………………………………(18)1.4.3编程环境上的区别(19)1.5加速比系数…………………………19)1,5,1阿姆达尔定律(19)1.5.2 Gustafson定律+++++++“…++“+“+“““““日“年4“非国“…(20)1.5.3阿姆达尔定律和 GustAfson定律的等价性""""1.5.4 Karp Flatt度量(23)1.5.5实际情况中影响加速比系数的因素……"…"""(24)1.5.6并行计算开销的加速比……(21.6锁竞争问题及其对加速比的影响(25)1.6.1程粒度因子和锁度固子1.6.2镇竞争的性能情况“…*…………“………………(26)1.6.3集中式铺竞争中的加速比分析……(28)1.6.4随机镇竞争中的加速比分析(29)1.6.5分布式锁竞争的加速比分析1.6.6无锁编程的加速比分折““·……(35)1.7负载平衡问题及其对加速比的影响…37)1.7.1影响负载平衡的主卖因素……………………………………(37)1.7.2负载平衙的评价指标……(38)1.7.3负载平衝情况下的加速比…38)1.8参考文献“““+““““““““+““““日非非……………………………(39)2多线程编程基础(41)2.1多线程编程基本概念…………""""""(42)2.1.1线程,::(42)2.1.2锁………(43)2.1.3各种系統中常用的操作及信号量操作函数…………1462.1.4用(++实现锁的自动释放…………(47)2.1.5原子操作……………(50)2.1.6铺与原子操作的区别·(54)2.1.7有镆计算、无锁计算与本地计算的概念………(54)2.2各种锁性能比较……(54)2.2.1各种锁在单线程情况下的性能………………54)2.2.2各种镇在多线程集中式锁竞争情况下的性能………………………(562.2.3各种锁在多线程分布式锁竞争情况下的性能着,,和用非中(58)2.3读写锁算法4 hansi+如+++“和(60)日录32.3,1读写镇概念的引出(60)2.3.2读写锁算法的分析和实现…(60)2.3.3读写锁的编码实现(62)2.4多线程退出算法(64)2.4.I单个子线程退出算法(64)2.4.2多个线程访问共享资源时的退出…(66)2.4.3有镇的多线櫂资源释放退出算法实现“67)2.4.4无锁的退出算法……………170)2.4.5多线程退出算法的使用(72)2.5参考文献………………173)3 OpenMI程序设计……………………………………(75)3.1(enMP的基本概念…………………………1117603.1, I Fork/Join并行执行模式的概念………(76)3.1.2内存模型…11(77)3.1.3性能举例……………………(78)3.1.4译器对 OpenMl的支持79)3.2 OpenMP端程模型(81)3、2.1 OpenMP编译指导语句格式…(81)3.2.2 OpenMP主要命令“++“+“+“+“(82)3.2,3 Open MP主要子句……………(82)3.2.4 OpenMI主要库函数中和““““““十““(83)3.3线程创建与工作分摊……(84)3.3.1 parallel命令………(84)3.3.2or和 parallel for命令(86)3.3.3if子句(条件执行并行)(89)3.3.4动态设置并行循环的线程数量··(90)3.3.5循环并行化的问题““““+““+“·“““““““““本“生生4(92)3.3.6 sections和 sector命今…(94)33.7 single命令……………………………………………………………(96)3.3.8 master命令“……………………(97)3.4数据处理……(98)3.4.1 private子句(98)3.4,2 Irstprivale子句……………………993.4.3 lastprivate子句………………………………*………(99)3.4.4 threadprivate子句………,…,………………………非甲44+分(100)3.4,5 shared子句··和·书出分世生日非非非非(101)4|多核计算与程序设计3.4.6 default子句………(102)3.4.7 reduction子句…"……""""(102)3.4.8 copyIn子句(103)3.4.9 copyprivale子句"""""……………(104)3.5任务调度……………………(105)3.5.1 schedule子句用法………………………(106)3.5.2静态调度…4107)3.5.3动态调度……………………………………………………………(108)3.5.4 guided调度….4109)3.5.5 runtime调度…………10)3.5.6任务调度与伪共享问题……………………………………………………(111)3.6线程间的同步……………111111)3,6.1 barrier命令…………………………………………………(11)3.6.2 crItICa命令(112)3.6.3 atomic命令m+m“m++s+++++++“++…“““““(113)3.6.4 ordered命令和子句…………(114)3.6.5 nowall子句…"""(114)3.6.6 flush命令““…(115)3.7 Open MP库函数详解…(116)3.7.1执行环境函数,(117)3.7.2锁操作函数·……………………………………(118)3.7.3时间操作函数……………………(120)3.8 OpenMP环境变量…120)3.8.1 OMP DYNAMIC ..(120)3. 8.2 OMP NUM THREADS....(121)3.8.3 OMP NESTED………………………(121)3.8.1 OMP SCHEDULE……::111121)3.9 OpenMP内部控制变量及相关流程……121)3.9.1内部控制变量…121)3.9.2任务调度流程……122)3.9.3线程数量决定流程(122)3.10参考文献………………………………………………(124)第2部分基础数据结构与算法4数组生“号“+日““““““日“日日““““非非自日非车非非有非中(125)4.1栈………………………………………………………"………………(126)4.1.1栈的基本概念…(126)目录51.1.2機的编码实现(127)4,1.3多线程栈的实现…(129)4.2数组快速排序(132)4.2,1排序算法介绍……………………………(132)4.2.2串行快连排序基本思想……………(132)4.2,3串行快遠排序的代实现(134)4.2,4非归的快速排序算法……………………………………(136)4.2.5快速排序算法的复杂度分析……………………………………………(139)4.3数组查找和日和和开和和开+和中“形开开卡于世世中由世世当t世粉排世想物面图非m(140)4.3.1顺序查找·……………………………(140)4,3.2二分查找………………………………………1,,,……(11.4实例:用数组管理一个HOOK功能…142)4.4.I单个函数的H(OK实现……………………1142)4.4.2多个函数的HOOK实现“+++“+,“+++++++…+++,…++++++++,,(143)4.43H(水K功能的应用简介(148)4.4.4H00K使用的注意事项(148)4.5参考文献(148)5链表(149)5.1单向链表(150)5.1.1存储表示非··和,·日“和十开“中(150)5,1,2接口设计·………(151)5.1.3添加节点到鲢表头部…153)51.4基本功能编码实现……………1154)5.2单向链表的排序……………………(159)5.2.1插入排序………………………………………………………(159)5,2.2归并插入排序……………………………………………………………(162)5.3双向链表……(166)5.3.1双向链表的基本概念………………………………………………1166)5.3.2双向链表的设计,………………………1(16)5.3.3双向链表的操作接口……………………………………………(167)5.3.4双向链表的鳊实现(168)5.4锥表的逐个节点遍历……………6177)5.4.1逐个节点遍历的基本概念…………177)5.4.2逐个节点遍历缡码实现(178)5.5多线程遍历算法………………(179)5.5.1多线程钝表的设计和螭码实现(179)6多核计算与程序设计5.5.2多甕程链表的4种遍历方案………………………(183)5.5.3多个线程同时遍历的情况…………………186)5.6实例:使用链表管理短信息系统的 CACHE(187)5.6.1短信息系统的 CACHE管理基本概念……………………………“………(187)5.6.2短信息系鏡的发送和接收分析重·,世(187)5.6.3短信息系统 CACHE管理的錫码窦现…………………………………………(188)6哈希表…………“……………………………………(191)6.1哈希表…………192)6.1.1恰希表的基本概念………………………………1192)6.1.2哈布表的索引方法………………“……………………………193)6.1.3哈希表的冲突解决方法………1196)6.1.4哈希表基本操作的源代码“…(198)6.2哈希链表………(202)6.2.1哈希表与敬组、链表的效率比较………………,……(202)62.2时间效率与空间效率的关系(203)6.2.3哈希链表的基本概念(204)6.2.4哈希链表的操作………(205)6.2.5哈希链表的编码宏现…(206)6.3实例: Webserver的动态 CACHE文件管理(213)6.3.1基本櫬念………(213)6.3.2 CACHE文件管理功能的设计:(213)6.3.3 CACHE文件管理功能的编码实现(214)6.4参考文献(219)7普通树与二叉树……(221)7.1普通树(222)7.1.1惜通树的描球方法…………………………1222)7.1.2树的操作接口设计…………(222)7.1.3树的遍历算法·……………*………1(2237.1.4树的码实现…………………………………………………(225)7.1.5使用树的遍历算法来实现 Xcopy功能………………………(230)7.2二又树………………………………………………………………(231)7.2.1二又树的基本视念……………………………………………………(231)7.2.2二又树的树梢及二叉树的商度…………………………1232)7.2.3二丈树的描述方法(233)7.3二叉排序树………(233)录77.3.1二叉排序树的基本概念……11233)7.3.2二又排序树的查找……………………(234)7.3.3二又排序树的插(235)7.3.4二叉排序树的删除…(237)7,3.5二又排序树的遍历(240)7.3.6二叉排序树的旋转操作……………………………………(241)8AV1搜索树:1(245)8.1AVL搜索树的基本概念…………(246)8.2AV1.搜索树的插入(247)插入操作需要考虑的问题…………………………………(247)8.2.2不存在不平街节占的情况分析“…………………………(248)8.2.3不平衡A节点的情况分析(248)8.2,4存在不平衡节点的情况分析(249)8.2.51.型不平衝情况的调250)8.2.6LR型不平情况的调整………………(251)8.2.7插入操作的伪代码描述“…“…………………………………(252)8.3AVL搜索树的删除………………111(254)8.3.1A节点的确定…(254)8.3.2几种不平街惰况的分析(255)8.3.3L.0型调整分析……………………………………………………………(257)8.3.41型调整分析(258)8.3.51.1型调整分析……………………………::1258)8.3.6删除操作的伪代码描述259)8.4负载平衡的AVL树4………(262)8.4.1基本概念的引出……………………:(262)8.4.2插入操作中负栽因子的调整……1262)8,4.3删除操作中负栽因子的调整……………………………………………(264)8.4.410和L-1型调整分析……,1::1266)8.4.51.1型调整分析……………1266)8.5AVL树的源代码……………(267)8.5.1数据结构定义(267)8.5.2创建、释放、查我等操作…………………………………(267)8.5.3旋转操作画数………………………………………(270)8.5.4插入操作画数…………272)8.5.5删除操作画数(277)8.6参考文献(285)8|多核计算与程序设计9复合二叉树,287)9.1哈希红黑树…(288)9.1.1哈希红黑树的基本概念(288)9.1.2哈希红黑树的查找…………………………………………………1……1(289)9.1,3哈希红黑树的插入...44…4…………,…,…3…………(290)0.1.4哈希红黑树的删除…………………………………………………………(292)9.1,5哈希红黑树的释放…………(292)9.1.6哈希红黑树的遍历……"…(292)9.1.7哈希红黑树的码实现……""""""""""…"(293)9.1.8哈希红黑树的效率分析…………“………(298)9.2哈希AVL树………(299)9.2.1哈希AVL树的基本概念(299)9.2.2哈希AVL树的查找“……9.2.3哈希AVL树的插入(3019.2.4哈希AML树的删除…(302)9.2.5哈希AVL树的释放(303)9.2.6哈希AVL.树的遍历(303)9.2.7哈希AVL树的端码实现和中中中中十“和日“(303)复合数据结构的分类…11(307)9.3.1节点叠加型复合……副和副……………………(307)9.3.2节点链接式复合“……………………………………(308)9.4抗DoS/DDs攻击的实例………08)9.4.1DoS/DDoS攻击的概念·11989.4.2常见DoS/DDos攻击手段及防苊策略………………………………(309)9.4.3抗10SDDs攻击的实现…1310)9.4.4抗Dos/DDoS攻击的编码实现…………………(311)第3部分并行计算10并行程序设计模式……(315)10.1基本概念…………316)10.1.1强并行计其与弱开行计算(316)10.1,2并行程序设计模式的基本思路…(316)0.2各种程序设计模式(317)10.2.1数据分解模式(317)10.2.2分治模式“………………………………………(318)10.2.3流水线模式…………(319)10.2.4任务并行模式………(320)