以下为截止2009年3月21日前发布在本人博客中的多核相关的文章汇总，这些文章大部分摘自于我写的《多核计算与程序设计》一书。现将这些文章分类汇总，方便大家阅读。

后续如果博客中继续发布了多核相关的文章，那么本文章将会被更新。如果对多核编程技术非常感兴趣的话，可以考虑将这篇文章加入您的浏览器收藏夹中，也欢迎您将这篇文章推荐给您的朋友。

一、基础篇

1、多核编程的几个难题及其应对策略

主要讲解多核编程时的串行化方面的难题及其应对策略。阅读全文

2、多核编程中的锁竞争难题

锁竞争会导致加速系数随CPU核数增多而下降的现象。核数增加到128时，加速系数只有0.78，还不如在单核CPU上运行的速度。 S(p) = (t +1)/ (p + t/p) = p*(t+1) / (p*p+t) （锁竞争下的加速系数公式） 。阅读全文

3、多核编程中的负载平衡难题

负载平衡的难度与CPU的核数成正比，CPU核数越多，负载划分的难度就越大。 阅读全文 

二、OpenMP专题

1、OpenMP并行程序设计（一）

介绍OpenMP程序在并行计算时的效率，在双核CPU上效率增加了整整一倍。 阅读全文

2、OpenMP并行程序设计（二）

1、fork/join并行执行模式的概念 2、OpenMP指令和库函数介绍 3、parallel 指令的用法 4、for指令的使用方法 5 sections和section指令的用法。阅读全文

3、OpenMP中的数据处理子句

本文主要介绍了OpenMP中的private、firstprivate、lastprivate、threadprivate、reduction、copyin、copyprivate等数据处理子句的用法。 阅读全文

4、OpenMP中的任务调度

本文主要介绍了OpenMP中任务调度子句schedule的使用方法。阅读全文

5、OpenMP创建线程中的锁及原子操作性能比较

主要比较了原子操作，Windows CriticalSection， OpenMP库带的锁在单任务运行情况下和多任务运行情况下的性能情况，在多核CPU上，多任务的锁竞争花费的时间是单任务时的锁运行花费时间的18倍。锁竞争带来的效率下降完全出乎意料之外，由此也可见多核编程和单核多任务编程是有很大区别的。 阅读全文

6、OpenMP程序设计的两个小技巧

讲述了如何动态设置线程数量以适应硬件和软件的扩展性，如何将嵌套循环并行化的技巧。 阅读全文

三、性能篇

1、双核CPU上的快速排序效率

在双核CPU上运行后，打印出花费的时间为 234 ms , 单任务版的快速排序函数约需406ms左右，并行运行效率为：406/（2×234） = 86.7% 左右。运行速度快了172ms。 阅读全文

2、多核系统中三种典型锁竞争的加速比分析

本文主要讨论了固定式锁竞争、随机锁竞争、分布式锁竞争三种典型锁竞争情况下的加速比,并分析了任务粒度因子和锁粒度因子对加速比的影响。结论: 分布式锁竞争加速比随CPU核数成正比，可以达到和单核多任务时相当的性能，是多核编程的发展方向。 阅读全文

3、无锁编程与分布式编程那个更适合多核CPU？

本文重点比较了无锁编程和分布式锁竞争的性能，无锁（原子操作）实际上是一种细粒度锁。然后又从实现的功能，程序员掌握难易程度，现有软件的移植等方面进行了比较，得出结论：无锁编程远不如分布式编程。分布式编程更适合多核CPU系统。 阅读全文

四、多核编程模式专题

1、多核编程中的线程分组竞争模式

讨论了使用任务分组锁竞争方式来消除锁竞争导致的CPU饥饿现象，队列池就是任务分组竞争的一个非常好的实践任务分组竞争模式相对于无锁编程具有更好的优势。 阅读全文

2、多核编程中的线程随机竞争模式的概率分析

本文主要分析了多个任务在随机分布式锁竞争的情况下，有不少于CPU核数个数的任务在运行的概率。然后将随机竞争和无锁编程的性能进行了理论上的比较。阅读全文

3、多核编程中的条件同步模式

本文讲解了一种减少锁使用的方法，将每次都加锁改为满足一定条件时才加锁，非常适合具有状态机性质的场合使用。 阅读全文

五、多核数据结构与算法专题

1、多核分布式队列的实现：偷与自私的运用

本文讲述了多核系统中分布式队列的实现方法，所谓分布式队列指的是每个线程除了可以访问线程池外还自动拥有一个本地队列。实现分布式队列的基本方法就是“偷”与“自私”。 阅读全文

2、多核查找-顺序查找也疯狂

用 数组进行查找，由于其插入和删除需要按顺序进行，需要移动较多的数据，对于大数据量的查找是无法使用的。然而，在多核时代，一切都改变了，大数据量的查找 结构也可以用数组来实现。并且用数组实现的大数据量查找结构有着比其他查找结构更明显的优势：效率高、内存占用少、并且容易避免伪共享问题。 阅读全文

3、多核中的并行前缀和计算

前缀和计算在并行计算中很有用，因为在处理负载平衡问题时，经常需要将若干段数据重新平分，而计算前缀和通常是一种有效的将数据平分的方法。 阅读全文

六、多核编程思想专题

1、多核新观念－象使用内存一样使用CPU？

象使用内存一样使用CPU？ 阅读全文

2、“老子”是伟大的多核计算科学家

本文主要论述道家的“小国寡民”，“无为”“大道自然”等思想与多核计算中使用的思想的异曲同工之处，给出了道家思想在多核计算中的实践实例分析。大道自然，“贪心”，“自私”，“偷窃”这些大自然赋给人类的自然力量，在多核计算中得到了广泛的使用。 阅读全文

3、多核编程的四层境界

从先天方法策略、目标需求评价、本质根源保障、算法实现执行四个层面阐述多核计算的含义    阅读全文

4、高房价与多核分布式计算

本文主要从多核计算的角度来论述高房价问题及其对社会的影响，并给出了高房价问题的最终解决措施。 阅读全文

5、道家·老子的算法思想分析

将 道家老子的思想与软件中的思想进行对比分析，得出结论，道家追求稳定可靠性。所以历代在拨乱反正时期，用的都是道家思想。历史上最典型的三个朝代汉、唐、 明为例，汉朝时张良等人都是好黄老之术（也就是道家思想），唐朝的宰相魏征也是道家人物，明朝的刘伯温也是属于道家人物。 阅读全文

6、屈原·渔父的算法追求

屈原与渔父两种不同的思想，相当于软件中的两种不同算法思想。“世人皆浊，众人皆醉”可以理解为软件运行的场景。  阅读全文

更多的多核相关的资源，可以访问：

1）Intel软件社区多核论坛：http://forum.csdn.net/Intel/IntelMulti-core/

2）Intel的博客：http://softwareblogs-zho.intel.com/

关于多核相关的书籍介绍可以参考下面这篇文章：

“多核编程高处并不“寒””，文章地址： http://news.csdn.net/n/20081107/120632.html

这篇文章里有我对现在市面上有关多核编程和并行计算书籍的一个点评。可以给大家购买书籍作为一个参考。

多核相关的开源项目介绍:

1、Intel 开源项目TBB库，链接：http://www.threadingbuildingblocks.org/

这是一个专门针对多核的开源项目，包含一些常见的多核数据结构与算法，如分段锁的哈希表、分布式内存管理、动态任务调度器等，其中最重要的一个是动态任务调度器，可以使用动态任务调度器将串行算法自动变成并行算法，免去程序员学习并行算法之苦。

TBB开源项目的使用方法详见O’Reilly出版的James Reinders的《Intel Threading Building Blocks》一书，如果要了解它的实现原理和方法，可以参考我写的《多核计算与程序设计》一书。

2、Capi开源项目，链接：http://gforge.osdn.net.cn/projects/capi 

这个项目是我开发的一个针对多核的数据结构与算法库，提供了许多实用的适应多核系统的数据结构与算法，主要的功能有以下一些：

1）各种并行算法，如并行归并排序、并行基数排序等并行排序算法；并行顺序搜索及终止检测算法、并行Dijikstra最短路径算法等并行搜索算法；并行前缀和、并行矩阵乘法等并行数值算法；等等。

2）分布式查找算法，如分段锁的哈希表、动态分布式哈希数组、动态哈希AVL树等。

3）抢夺式内存管理算法，即使在分配和释放共享内存时，也几乎不需要使用锁。

4）基于偷取和自私的分布式队列，用分布式队列实现的两种动态任务调度器、以及用动态嵌套任务调度器实现的Parallel_For()功能，用Parallel_For()实现的并行快速排序算法、并行归并算法等。

5）任务图调度器，可以用来实现对有依赖关系的执行块的并行计算。

这个开源项目和TBB相比起来各有特色，TBB库的优势在于它是商业化的开源项目，代码经过优化和相对完善的测试。CAPI的代码专门为学习而设计，代码没有经过优化，代码简单易懂，易于学习，并且实现了比TBB库更多的数据结构与算法容器，有一些创新的数据结构与算法在里面。其缺点是，现在发布的版本为0.2版本，如果进行商业使用需要自行增加测试用例进行更完善的测试和优化。

CAPI开源项目的实现原理和使用方法详见我写的《多核计算与程序设计》一书。

引言

服务（Service）的本质就是提供 服务消费者期望的某种功能，服务的价值体现在两个方面：服务本身的质量和寄宿服务的平台应付消费者的数量，并发（Concurrency）的关注的是第二 个要素。WCF服务寄宿于资源有限的环境中，要实现服务效用的最大化，需要考虑如何利用现有的资源实现最大的吞吐量（Throughput）。提高吞吐量 就某个寄宿的服务实例（Service Instance）来说，一个重要的途径就是让它能够同时处理来自各个客户端（服务代理）的并发访问。WCF实现了一套完整的并发控制体系，为你提供了不 同的并发模式。

我经常说软件架构是一门权衡的艺术，需要综合考虑各种相互矛盾的因素，找到一种最优的组合方式。提高单个服务实例允许的 并发访问量能够提高整体吞吐量，这样的理论依赖于一种假设，那就是服务端所能使用的资源是无限。我们知道，这种假设无论在什么情况下都不会成立。如果我们 并发量超出了服务端所能承受的临界点，整个服务端将会崩溃。所以，WCF一方面需要允许让单个服务实例并发处理接收到的多个请求，同时也需要设置一道闸门 控制并发的数量。WCF的流量限制（Throttling）体系为你创建了这道闸门。

从本篇文章开始，我将发布一系列的文章对WCF并发架构体系进行深入剖析 ，先来看看并发的基本介绍。

一、同一个服务实例上下文同时处理多个服务调用请求

并 发的含义就是多个并行的操作同时作用于一个相同的资源或者对象，或者说同一个资源或者对象同时应付多个并行的请求。对于WCF的并发来说，这里将的“资源 或者对象”指的就是承载服务操作最终执行的服务实例（Service Instance）。而WCF将服务实例封装在一个称为实例上下文（InstanceContext）对象中，所以WCF中的并发指的是同一个服务实例上下文同时处理多个服务调用请求。

WCF服务端框架一个主要的任务是将接收到的服务调用请求分发给激活的服务实例，调用相应的服务操作并返回执行结果。也就是说，服务操作的执行最终还是会落实到某个具体的服务实例上。《WCF技术剖析（卷1）》 的第9章对WCF的实例化机制进行了深入的剖析，从中我们知道在WCF服务端框架体系中，激活的服务实例并不是单独存在的，而是被封装在一个被称为实例上 下文（InstanceContext）对象中。WCF提供了三种不同的实例上下模式（Per-Call、Per-Session和Single）实现了 不同的服务实例上下文提供机制。

所以，WCF并发框架体系解决的是如何有效地处理被分发到同一个服务实例上下文的多个服务调用请求，这些并行的调用请求可能来自不同的客户端（服务代理），也可能相同的客户端。WCF并发的本质上可以通过图1体现。

图1 通过一个InstanceContext对多个并发请求的处理

由于WCF的并发处理属于服务本身自身的行为，所以我们通过服务行为（Service Behavior）的形式对采取的并发策略进行控制，而不同的并发策略定义在相应的并发模式（Concurrency Mode）下面。

二、通过ServiceBehaviorAttribute特性定义并发模式

WCF为三种典型的并发处理策略定义了三种典型的并发模式，即Single、Reentrant和Multiple。这三种并发模式通过ConcurrencyMode的三个同名的枚举项表示，ConcurrencyMode定义如下：

   1: public enum ConcurrencyMode

   2: {

   3:     Single,

   4:     Reentrant,

   5:     Multiple

   6: }

通过ConcurrencyMode枚举项表示的三种不同的并发模式体现了WCF处理并发请求的三种不同能策略：

• Single：一个封装了服务实例的InstanceContext对象在某个时刻只能用于对某一个单一请求的处理，或者说针对某个InstanceContext对象的多个并发的请求会以一种串行的方式进行处理。具体来讲，当WCF服务端框架接收到多个针对相同InstanceContext的请求时，会先确定该InstanceContext是 否可用（是否正在处理之前的服务调用请求），如何可用，则将接收到的第一个请求分发给它，其它请求则被放入根据抵达的先后顺序被放入到一个队列中。如果之 前的请求被正常处理，队列中的第一个请求被分发给InsanceContext。如果一个请求在队列中等待的时间过长，超过了设置好的服务调用的超时实 现，客户端会跑出TimeoutException异常；
• Reentrant：该模式和Single一样，InstanceContext对象在某个时刻只能用于对某一个单一请求的处理。不过有一点不同的是，如果服务操作在执行过程中涉及对外调用（Call Out），该InstanceContext可以用于其它服务调用请求的处理；
• Multiple：在该模式下，一个InstanceContext可以同时用于处理多个服务请求，所以Multiple并发模式下针对同一个InstanceContext的多个并发请求能够得到及时的处理。不过，由于是并行的处理方式，服务操作执行过程中状态的管理以及多线程的安全问题需要服务开发者自行处理。

并发模式的采用是服务单边的选择，是服务端个人的行为，所以并发模式以服务行为的方式定义，我们只需要在服务类型上应用 ServiceBehaviorAttribute特性，为ConcurrencyMode属性设置相应的值即 可，ServiceBehaviorAttribute定义如下：

   1: [AttributeUsage(AttributeTargets.Class)]

   2: public sealed class ServiceBehaviorAttribute : Attribute, IServiceBehavior

   3: {

   4:     //其它成员

   5:     public ConcurrencyMode ConcurrencyMode { get; set; }

   6: }

如果显示指定服务采用的并发模式，默认使用的是ConcurrencyMode.Single，所以下面两种服务定义方式是等效的。

   1: public class CalculatorService : ICalculator

   2: {

   3:     //省略成员

   4: }

   5:  

   6: [ServiceBehavior(ConcurrencyMode = ConcurrencyMode.Single)]

   7: public class CalculatorService : ICalculator

   8: {

   9:     //省略成员

  10: }

三、回调（Callback）中的并发

WCF并发解决的是同一个InstanceContext对象在处理并发请求是采用怎样的处理策略。我们知道InstanceContext不仅仅是封装真正服务实例的容器，当我们通过双向通信的机制从服务端回调客户端操作时，真正执行回调操作的回调对象也是封装在InstanceContext中。

在双向通信的场景中，如果多个服务端或者同一个客户端的多个并发的服务调用操作所指定的回调实例上下文（即封装回调操作的InstanceContext对象），就可能出现针对同一个InstanceContext的并发回调的现象。WCF采用与正常服务调用相同的机制来处理并发回调，实际上WCF采用几乎一样的机制来实现正常的服务调用和回调。

与通过将ServiceBehaviorAttribute特性应用到服务类型并指定采用的并发模式相类似，回调采用的并发模式通过应用在回调类型上的CallbackBehaviorAttribute特性来指定。CallbackBehaviorAttribute中同样定义了ConcurrencyMode属性：

   1: [AttributeUsage(AttributeTargets.Class)]

   2: public sealed class CallbackBehaviorAttribute : Attribute, IServiceBehavior

   3: {

   4:     //其它成员

   5:     public ConcurrencyMode ConcurrencyMode { get; set; }

   6: }

下面的代用中，我们通过在回调类型CalculatorCallbackService上应用CallbackBehaviorAttribute特性，将回调并发模式设置成ConcurrencyMode.Multiple。

   1: [CallbackBehavior(ConcurrencyMode = ConcurrencyMode.Multiple)]

   2: public class CalculatorCallbackService:ICalculatorCallback

   3: {

   4:     //省略成员

   5: }

四、 事务行为与并发

相信你还会记得在上面一章介绍事务编程（《上篇》、《中篇》、《下篇》）的时候，可以在服务类型上面应用ServiceBehaviorAttribute特性将ReleaseServiceInstanceOnTransactionComplete属性设成True，这样可以让WCF在事务结束之后将封装了服务实例的InstanceContext对象释放掉。不过这样的设置之后再并发模式为ConcurrencyMode.Single的前提下方才有效，否则在进行服务寄宿的时候将会抛出异常。

比如说，我们定了如下一个BankingService服务类型，通过ServiceBehaviorAttribute特性指定 ReleaseServiceInstanceOnTransactionComplete为True，并采用 ConcurrencyMode.Multiple并发模式。

   1: [ServiceBehavior(ReleaseServiceInstanceOnTransactionComplete = true,ConcurrencyMode = ConcurrencyMode.Multiple)]

   2: public class BankingService : IBankingService

   3: {

   4:     [OperationBehavior(TransactionScopeRequired = true)]

   5:     public void Transfer(string accountFrom, string accountTo, decimal amount)

   6:     {

   7:        //省略实现

   8:     }

   9: }

当我们试图寄宿该BankingService服务的时候，如图2所示的 InvalidOperationException异常会被抛出，并提示对于已经将 ReleaseServiceInstanceOnTransactionComplete设置成True的服务来说，必须将并发模式设成 ConcurrencyMode.Multiple。

图2 在Multiple+ReleaseServiceInstanceOnTransactionComplete导致的异常 

WCF提供的三种不同的并发模式，使开发者可以根据具体的情况选择不同的并发处理的策略。对于这三种并发模式，Multiple采用的并行的执行方 式，而Single和Reentrant则是采用串行的执行方式。串行执行即同步执行，在WCF并发框架体系中，这样的同步机制是如何实现的呢？请关注下篇文章。