随着计算机技术的发展，现代计算机的处理速度和计算能力无疑越来越强。然而细心的同学们可能早已注意到，从2005年起，单核的 CPU 性能没有显著提高(见下图)。原因是人们发现单核的简单改进 CPU 性能在潜力和功耗上都不划算。随着 Intel 的 NetBurst 架构退出江湖，处理器完全进入多核时代，从最初的双核飙升到现在的几百核 CPU，提高性能不是里计。同时，一系列针对特殊计算的特殊计算 accelerator 并行硬件的发展现在是百花齐放。大数据问题需要很多电脑才能并行处理，现在大部分都可以用多核电脑解决。 然而，一方面，硬件日新月异，另一方面，设计和实现如何高效正确地使用这些硬件一直是一个长期存在的问题。毕竟算法和数据结构是所有低年级本科生的必修课。然而，当我们试图并行这些熟悉的算法时，事情往往并不那么简单。以一个非常简单的排序问题为例。在串行的背景下，我们学习了许多不同特征的算法。大多数伪代码只有几行到十行。然而，这些算法很难获得令人满意的加速比。很多时候，学习并行编程只是学习和使用 OpenMP/MPI/CUDA 等待并行工具并不能保证真正的写作 scalable 并行算法。另一方面，并行编程的臭名昭著之处在于，运行结果往往难以预测和控制。比如这个著名的笑话：

如果你有问题，并行解决。所以你有两个问题。

以快排为例。快排本身使用的分治方法非常适合并行。当我们使用一个时 pivot 将数组分成左右两部分后，两侧可同时排序。但是这么简单就能得到高效的快排算法吗？考虑将数组中的数分成左右两侧的过程（partition），如果我们仍然使用传统串行算法的经典 partition 算法，即基于两个或三个指针对应的元素的比较和交换，这个过程非常串行（快速排列的效率也取决于串行扫描中的访问存储 pattern）。假如只是第一步 partition 就使用了 O(n) 即使后续分支过程的成本被忽略，无论核数多少，运行时间都不能快于第一步 partition 的开销。因此如果只是了解掌握了使用并行工具，但是局限在“并行”现有的串行快排中，是很难写出高效的并行排序算法的。至于如何并行快排，其实并不难。 17 在清华暑期课程中，有兴趣的同学可以参考课件(链接)。或者在我们的后续文章中。 还有介绍。同时，该算法的实现也非常简单。整个算法中没有两个核同时操作一个元素。换句话说，虽然算法是平行的（parallel），多核用于计算，但不需要并发（concurrency），这使得算法的效果 predictable，也不难 debug。

平衡二叉搜索树是动态维护任何有序集合的基本数据结构。一些常见的实现包括 AVL 树，红黑树，weight-balanced tree（BB[α] trees，加权平衡树)，treap 等等。许多更先进的数据结构，如 interval tree，segment tree，range tree，通过增加许多其他几何问题，甚至许多类型的数据库（augment）BST实现的方式 [2]。

长久困扰计算机界的一大问题就是处理器的性能增长是远远大于内存大小和带宽的增长的。还举 2005 年到今天的例子，处理器从单核增长到了上百核，而且还有各种新单核技术的加成。然而内存从 DDR2 到 DDR4 的带宽和容量增长都非常有限。固然新的高性能计算机通常可以通过装很多很多的内存条在短时间内在一定程度上解决问题，但是长此以往肯定不是办法。尤其是 DRAM 技术遇到瓶颈几乎无法大幅度提升性能、且能耗散热已经是很大的问题的前提下。这也对并行算法本身提出了挑战：即便有了高效的共享内存（shared-memory）并行算法，如果内存不够大，解决问题的规模就非常有限；同时随着核数的增加，每个核分到的内存反而在减小。

然而我们人类站在地球之巅不是没有道理的，遇到问题就一定会找到解决方案。在今年4月推出的 Intel® Optane™ DC Persistent Memory 就是基于完全不同技术的新内存解决方式，为了以示区分我们通常称之为 NVRAM。新技术非常的震撼，初代产品就能达到最大 512GB per DIMM，只要 12 块就可以在一台机器上达到 6TB 的内存，远远超过现有的 DRAM 技术。同时新硬件在技术上有很强的的扩展性，在可以遇见的未来容量增长都有非常大的潜力。可以说 NVRAM 的出现对于多核并行和广义的计算和数据存储的帮助是非常决定性的。

既然是新的技术，那就必然有一些新的 feature。一个 feature 是新硬件的 persistency，也就是说掉电后内容不会丢失，因此用新硬件就完全不需要之前的复杂的数据容错机制（fault tolerance）。当然这不是本文的重点，这里就不展开了。另一个 feature 是 NVRAM 的读写的非对称性。在新硬件上，读带宽是不错的，但是写带宽则相差数倍。同时这个差距可以认为在短期不会有所改善，因为这是由于新硬件的技术原因造成的。

上文给出了两个关于现代的算法研究的例子，实际上我们还有很多其它有趣的工作。理论上讲，其它一些我们做过的算法还有并行的增量三角剖分（Delaunay triangulation），并行强连通分支（labelly connected components），以及一个非常简单的并行最短路算法等等，这些都是并行算法中长时间未能很好解决的问题。实现方面，上述三角剖分和强连通分支的算法已经在我们维护的并行算法库中，性能要好于之前所有的算法。我们既设计和实现最快的经典算法如排序、半排序（semisort）、随机排列（random permutation），也包括并行其它领域和实际问题中的算法，比如数据库索引（database indexing），垃圾回收（garbage collection）机制，各种聚类算法等等。

上次发出了一篇关于并行语言的科普贴（和招生广告）之后，很高兴看到大家对并行算法很有兴趣。许多人留言问，有没有相关的材料可以学习。并行算法和编程作为一个发展很快又相对比较新的领域，目前我们不知道非常合适的中文教材。许多有用的英文材料，也是以美国各大学校并行算法课的 lecture notes 为主。所以我们就萌生了连载一个专栏，给大家介绍一些并行算法的背景知识的想法。希望可以引起更多同学们的兴趣 😃 同时，这个连载的内容将会是我下学期在 UC Riverside 的课程（CS260）的一个缩略版。在 UCR 的同学们有兴趣也可以来选课哦。

今天我们简单的说说第一讲。首先，要研究一个并行算法，要考虑的第一个问题是，算法是怎么被并行的？如果我们有若干抽象的处理器/核（processors/cores）和一些任务（tasks），他们如何交互？如何访存？如何使用 cache？如何同步？从系统和实现的角度来说，这里有千千万万不同的情况。而我们这个系列的文章会更多的从理论的角度去理解这个问题，也就是说，在这么多不同的硬件setting下，我们首先如何对它们进行建模，如何理论分析？

你可能会问，建模和理论分析，对于真正地去写并行算法，有什么用呢？从理论上去理解并行算法，正如你在大学第一门课里学习到的串行算法一样，它会告诉你，O(n log n) 的归并排序一般来讲比 O(n^2) 的冒泡排序效率高。它会告诉你，如果你想找到单源最短路，可以使用Dijkstra算法，如果想维护哈希表，要开出两倍你所要存的数的空间以避免频繁冲突，等等等等。学会了这些东西，不管你以后使用 C++ 还是 java，不管是自己实现还是去调用别人的实现，都可以写出对应的高效的程序来。同样的，学习并行计算不仅仅是学会使用 OpenMP，Cilk，TBB 等这些库的接口，更重要的是，应该怎么去写一个程序。计算机语言和编程工具是不断发展更迭的，而算法的核心思想总体来说是一致的，一脉相承的。即便未来的并行语言变成了OpenABCDEFG，TAA, TCC, TDD，只要算法的思想对了，你也一样会把并行程序写好。

我们这个系列文章主要讨论的是 shared-memory multicore 的并行算法。顾名思义，这是说多个处理器共用一片（通常来讲无限大的）内存。彼此之间可以通过内存“交流”。那么下一个问题就是，在使用多个核的情况下，我们如何去评价一个并行算法的时间复杂度呢？在传统串行算法设计中，大家对于 RAM（Random Access Machine） 模型应该并不陌生。简而言之，对于 RAM 模型来说，每一次计算和随机访存都花费单位时间。那么加起来总的时间就是这个算法的花费。因为这个模型比较简单，所以通常在大家本科算法课里用来分析复杂度。这个模型的简单性也是串行算法容易学习和普及的原因之一。当然，后来大家也提出了 I/O 模型等一系列别的计算模型，这里我们就不展开讨论了。总之，要研究并行算法，一个简单而行之有效的模型是非常重要的。

另外值得一提的是，在分析算法的时候，我们通常采用的是渐进（asymptotical）分析，比如使用大 O O O 记号来表示（类似的还有 o ( ) o() o(), Ω \Omega Ω, Θ \Theta Θ 等等符号）。它的核心思想是只在意算法花费的高阶项，忽略常数和低阶项。

并行算法这个问题从上个世纪七八十年代就被数学家们和计算机科学家们提出和研究了，远远在还没有真正的多核电脑之前。科学研究的许多领域都是如此，理论的模型（和想象）通常会领先现实数十到数百年。这些东西可以活在理论家的脑子里，然后可能有一天一个相似的东西就实现了，还发现以前的人 YY 的那些东西挺有用的。对应于 RAM，一个叫做 Parallel RAM （PRAM） 的模型曾经在上世纪风靡一时。你去看看有点年纪的教授们，尤其是做理论的老师们，甭管现在干什么的，他们的 paper 历史里，多多少少都在二十多年前研究过那么几个 PRAM 的算法。PRAM 它和 RAM 一样，假设在每个单位时间，每一个 processor 可以做一个计算或者访存的操作。一共 P 个核共享一个 shared memory。像这样：

在这个模型中，通常设计算法就是要告诉所有的 P 个核，每一个单位时间做什么。每一个单位时间过去后，所有的processor们就完成了它们对应的操作，写内存的写内存，做算术的做算术。注意，这里暗含了一个十分强的假设，就是既然所有操作都是单位时间，memory又是共享的，那么这些 processor 们通过这个shared-memory是高度同步的，举个例子来讲，这里有两个processor： 在第三个时间单位，P1就会知道上一个时间里的A已经被P2改成了6，所以最后P1会把D的值改成8。惊不惊喜，意不意外？这件事在我们现在看来，自然是非常不现实的（这一点我们后面会展开讲）。但是大家在上个世纪，真情实感地在这个模型上设计了不计其数的算法……

所以这个模型本身在现在，尤其是真正的多核电脑普及之后，是没有太大价值的。但是当年提出的许多算法和思想，还是给后人有很多的启发。我们后面会见到许多有趣的算法，都在那个时候就被研究过了。

在 PRAM 里，评价一个算法的的主要指标是它运行的时间 T，也就是一共需要几个并行的时间单位。另一个就是这个算法执行需要的 processor 的数量 P。另外，这个模型通常来讲有几种模式：

• Exclusive read exclusive write (EREW) — 多个processor不可以同时读或者同时写同一个内存位置
• Concurrent read exclusive write (CREW) — 多个processor不可以同时写，但是可以同时读同一个内存位置
• Exclusive read concurrent write (ERCW) — 不能同时读但是竟然能同时写，这个没什么意义，所以没人用它
• Concurrent read concurrent write (CRCW) —两个processor既可以同时读也可以同时写同一位置，花费单位时间。关于这个同时写最后结果是什么，也有许多说法，不过我们的重点不在这个模型上，就不展开了。

那么 PRAM 主要的不现实之处有哪些？我们又应该怎么改进呢？首先第一点，在PRAM里，一个算法需要几个 processor，这个 P 是固定的。在我们现代的多核电脑里，虽然你知道它有几个 processor，但是实际上，你不知道你能用几个。你的操作系统可能把其中的几个 processor 分给了的别的应用，即便你在程序运行的过程中，你能用的 processor 数也会动态变化。可能前半截你还有 8 个核可以用，跑着跑着有 4 个就被调度去干别的了，那你这个算法，还能跑不能跑？还对不对？还够不够快？第二点，就是上面说到的高度同步问题。这件事总体来说是非常难的，在现实中，访存比算术计算的花费要大得多，即便同样是访存，数据在不同层的cache里，在内存里，这些花的时间也都不一样。就算都是算术计算，也没有说全都一样快的。如果强行同步，这将可能花费比计算还长的时间。

所以在现在，已经很少有人使用这个模型看待并行算法了。而且基于这个模型设计出来的并行算法，有很大可能在现实里也跑不太通。

到这里你可能会拍案而起：我看了这么多，你现在告诉我这个模型其实没用？先不要着急，首先，这是并行算法发展历史上影响比较大的一个模型。当你在读相关文献的时候，很可能会看到一些算法，它们和我们现在的设计思路不太切合，或者得到了一些匪夷所思的 bound。理解 PRAM 的一些简单原理（和局限性）有助于你们理解这些前人的算法，并且从中提取出对自己有用的部分。

那么下面我们讲一个现在大家用得比较多的计算花费模型（cost model），叫做 work-depth 模型。

Work-depth（或者work-span）模型将会是我们这个系列文章主要会使用的模型。也是现在大家认为比较实用的模型之一。它的中心思想是说，对于我们所有算法中的操作，根据其依赖关系可以画成一张 DAG（Directed acyclic graph，有向无环图）。其中每一个节点代表一个操作，每一条有向边 A->B 意味着B这个操作必须等待A操作进行完才可以执行。我们管这张图叫 computation graph 或者computation DAG。 一个算法的代价用两个量来衡量，一个叫 work，用 W 表示，也就是这个图总的结点数。它告诉你这个算法如果你只有一个 processor，串行地跑，它的时间复杂度是什么。 比如上图，这个数就是 17。第二就是这个图本身的深度，叫 Depth (D)，也叫 Span (S)，也就是最长的并行依赖链。在上图里，这个数是 8。这个 depth 告诉你，如果你有无数个 processor，你这个算法需要多少时间——因为即便你有无数个 processor，这些依赖关系还是要被按顺序一个等一个地执行的。

我们来用一个简单的算法作为例子。比如我现在有一个数组 A，我想计算出它里面所有元素的和。这个操作被称为 reduce 操作，是并行算法里最基础的一个。一个简单的方法大概也许是这样的：如果有 P 个 processor，就把数组拆成 P 份，计算出每个部分里的和，最后把所有的再串行加起来，也就是像这样：

Sum(A, n) { 
        
  int B[p];
  start p threads with id 0 to p-1
  In each thread i { 
        
    for (j = i*n/p to i*n/p+p) B[p] += A[j];
  }
  sync all threads;
  for (j = 0 to p) ret += B[p];
  return ret; }

不过，和上面提到过的 PRAM 算法类似，它也有这么几个问题：第一，你如何确定你其实有几个可以用的处理器？第二，如果你有三个五个处理器还好，如果你有 n 个处理器，上面这个算法岂不是和串行算法没有任何区别？咦？？怎么处理器越多感觉越慢呢？

所以让我们忘记什么到底有几个处理器这样的事情，试图用 work-depth 的思路分析一下这个问题。这里我们采用这样的算法：我们把n个数两两相加，得到一个长度为n/2的数组，递归地完成这个过程，直到只剩一个数，就是我们要的结果。 上图既是这个算法的示意图，也可以直接看成是它的DAG，从上到下就是依赖关系：比如要计算左边的 3+7=10，必须要等 1+2=3 和 3+4=7 这两个操作都完成。写成伪代码可以有递归非递归两种形式： 非递归写法：

reduce(A, n) { 
        
  int B[n], B2[n];
  parallel_for i=1 to n B[0][i]=A[i];
  for i = log(n)-1 downto 1 { 
        
    parallel_for j = 1 to 2^i 
      B2[j] = B[2*j] + B[2*j+1];
    parallel_for j = 1 to 2^i B[i]=B2[i];} 
  return B[0]; }

递归写法：

reduce(A, n) { 
        
    if (n == 1) return A[0];
    In parallel:
        L = reduce(A, n/2);
        R = reduce(A+n/2, n-n/2);
    return L+R;
}

你可能会问，既然是并行算法，为什么要在意 work 呢？第一，通常情况下，我们所拥有的处理器数远远不能和无穷相提并论，连输入规模 n 都远比不上，这时候，主导计算时间的不是 depth，反而是 work（这一点我们马上会展开讲）。第二，work 作为操作总数，它还反映了许多其它的东西，比如能耗，比如占用的总资源。所以让一个算法 work-efficient 是非常重要的。通常来讲，我们设计一个好的并行算法，它的 work 在渐进意义上不应该超过最优的（或者已知最好的）的串行算法的复杂度。这意味着即便你只有一个处理器，或者很少的处理器数量，也可以跑出令人满意的结果。而不是为了并行，引入了更多别的overhead。

那既然我们没有足够多的处理器，depth 又有什么用呢？depth 这个量主要反映的是，当我们的核，从三个增加到三十个，增加到无穷多个，这个算法的 scalability 如何。如果 depth 很大，有更多的核很快就没有意义了。也就是说，depth 意味着当我们拥有更多的处理器时，算法的性能可以提升的潜能。depth 我们通常的目标是什么呢？我们希望它是 p o l y − l o g poly-log poly−log的，也就是说，是关于 l o g n logn logn 的一个多项式。这表明这个depth和输入规模 n n n 比起来不值一提，基本上现实中有的处理器数量都能期望看到好的加速比。即便不行，也至少是 O ( n ϵ ) O(n^{\epsilon}) O(nϵ), ϵ < 1 \epsilon < 1 ϵ<1 的。

这里多提一点，work-depth 是一个 cost model。它没有指明我在并行的前提下，可以做什么以及怎么做（如并发写，原子操作，新建线程，等等）。它只是告诉你，你有一个算法，在它的依赖关系下，它可能的花费（cost）是什么。

说到这里，你可能还有一个疑问：我是写出了一个并行算法，可是那是伪代码，我怎么让我的处理器去认领这些任务，怎么知道哪些核做哪些加法，怎么保证 load-balancing 呢。如果要把这些东西都写在代码里，难道不是会让实现变得十分复杂吗？这就引入了我们的下一个话题：调度算法。

没错，在设计上面的 reduce 的算法设计当中，我们没有具体地说，这些并行的任务，应该怎么分配给处理器。没有像一开始那么具体地讲“分成P份，第 i 个处理器去加第 i 份的和”这样的话。这是因为，在我们的算法设计和真正的底层实现中，我们假设了一个调度器（Scheduler）。

调度算法可以说是过去15年来并行计算中最天才的概念。很多人觉得并行很复杂、很系统、很难debug，都是因为没有很好的利用调度算法或者调度器。 有了调度算法，并行才能上升到理论的高度，设计简洁又复杂度低的算法才能真正在实际中提升程序的性能。不然，算法再简单，实现的时候也要和复杂的底层系统打交道。这就仿佛给你台电脑让你写个快排，结果你发现得从操作系统写起一样。

调度器就像是一个在我们的并行算法和处理器之间的一个黑盒子。 并行算法告诉它：现在我这两个（或者多个）task（我们有时候管这些task们叫线程，threads）可以并行地跑。调度器记住之后，会把这些 task 排队分给当前有空的处理器。为什么说它是一个黑盒子呢？是因为作为算法的设计者，你从此就可以只用关心哪些任务之间能并行，哪些之间有依赖关系，而不用具体操心每个任务被映射到哪个处理器上了。而这个黑盒子里的具体的调度算法本身，也是有很多不同的实现方法的。但总体的目标，就是在合适的时候把任务交给合适的处理器。以后如果有机会，我们可以开一个专题讲一讲。这里还是只简单地介绍这个东西的基本概念。

调度器对于算法设计者来说，无疑是做了一层有用的抽象。这个东西有效地隔离了算法设计和具体的任务调度，让算法设计变简单。在我们之后的算法设计中，我们都假设有一个有效的调度器帮我们调度任务。

说到这里，你可能又会问：使用调度器多一层操作，不是会比我亲自操作每个核执行什么任务，增加了 overhead 吗？这样不就让我的程序变慢了？其次，调度器它行不行啊？我不亲手把任务精巧地划分好，让每个处理器都接到差不多的任务，总是不大放心。会不会有 load-balancing 的问题啊？

从理论上讲——当然，调度器的方法不会比你用手写出来的最好的方法好，至少你总可以（理论上讲）手动分配出一个和调度器一样的方法吧。可是，随着调度器算法的完善，各个并行工具，库等东西的完善，手动操作超过调度器的方法，将会变得越来越难且越来越没有必要。想要理解这个，我们做一个简单的类比。当人类刚开始写串行算法的时候，是写机器码，汇编语言，这些东西都要和底层体系结构直接打交道。那时候，写代码是个很难的事情。全世界能干这件事的人寥寥无几。后来随着高级语言的出现，编译器，解释器的普及，曾经几千行的机器码可能只要几十行的高级语言就能实现了。一个高中生也完全可以自学两天，就写出简单的程序来。当然，就在十几年前，写汇编还是程序员的重要自我修养，因为一旦非常需要高性能的代码，就要用汇编来一段 free，啊不，assembly style，以避免编译器给你编译出来的一些overhead，但是在如今这个年代，这件事的重要性已经大大降低，因为你用手写的大量汇编代码，已经很难赛过发展了几十年的C语言编译器了。更何况对于复杂的大型的工程来讲，把它们用汇编写出来都近乎不可能了，更不要提考虑 debug 这样的问题了。

所以，做一个不一定非常精确的类比，如今我们看待并行算法和并行编程，也是这么个道理。大家总觉得并行编程难，尤其是并行代码debug起来如同愤怒的男/女朋友一样蛮不讲理。这是因为我们看待并行编程的时候，一眼就看到了和底层体系结构打交道的那一步。cache，memory，处理器，同步，通信，并发，冲突，内存管理，load-balancing……这些东西搅和在一起，并行算法当然难了。可是，这时候你应该问问自己：凭什么？？我要干这些？？？我写串行算法的时候受这些委屈了吗？？我像舔狗一样为我的代码费了这么大劲处理这些东西，有用吗？？值得吗？？ 正如编译器把我们写串行算法的时候把我们和底层隔开一样，调度器这个时候就应该起到同样的作用。设计算法只需要纯粹地从问题出发，电脑有几个处理器，每个处理器什么时候干些什么，会不会运行到一半少了两个能用的处理器，都不再重要了。你就可以优雅地看看算法的 work，depth，写写算算，问题就解决了。只有让编程这件事变得简单，才能写出功能更复杂的程序。

那让我们来看看，一个调度器可以怎么调度上面的程序。我们回顾一下这张图。 显然，如果有 p p p 个核执行这 n n n 个加法，一个最简单的方法就是——按顺序从上到下执行。按照拓扑排序（topological sort）的顺序，先拿出最早的，相互不依赖的，最多 p p p个任务一起执行，然后再拿最多 p 个，以此类推。在这个例子里，大致来说，就要 O ( n / p ) O(n/p) O(n/p) 的时间。想象一下 p = 2 p=2 p=2，那就是每次从上到下从左到右按顺序用这两个处理器执行两个加法，需要 n / 2 n/2 n/2 的时间。如果 p p p 越变越大呢？最快也不能超过 O ( l o g n ) O(log n) O(logn)吧，因为 1->3->10->36 这条链必须花四轮进行（这就是 depth 的意义）。总体来说，你可以证明这种分配任务的方法在 O ( n / p + l o g n ) O(n/p+log n) O(n/p+logn) 的时间里可以把这 n 个加法做完。

这就是最简单的一个调度算法。可以证明，给定一个 DAG，W 的 work 和 D 的 depth，你总是可以通过一定的调度算法，在 W/p+O(D) 的时间内给它执行完。 最简单的方法就是像上面那样（大家可以自行证一证，上面的算法其实是 W/p+D）。这个结果可以说是相当棒的，为什么呢，因为它也是这样一个 DAG 执行时间的下界（lower bound）。W 的 work，p 个处理器，就算任何时候每个处理器都忙得团团转，完全平衡地分配所有任务，也得要 W/p 的时间吧。O(D) 这一项就不用说了，你就算是有无穷个处理器，也要这么多时间吧？所以就这么一个简单的调度算法，渐进程度上就已经是最优的了。所以，放心把这些事情都交给它们吧！你再怎么使劲用手调度，划分任务，也就是和调度器在渐进程度上一样的。

当然具体实现一个调度器的时候，没有这么简单，调度器本身自己的实现也是很 tricky 的，因为调度器本身就是一个和底层操作打交道的，你可能并不想写的，并行算法啊！不过这里就不展开了。还有一个事情是，现实中的任务都是动态生成的，不是程序一运行，就把这个 DAG 交给调度器的。不过放心，调度器也能处理这种情况。Again，这里不细讨论调度器的实现，只是让大家理解一下它的原理，有机会我们开个专题讲一讲~

回到这个 W / p + O ( D ) W/p+O(D) W/p+O(D) 的值上来——目前来讲，我们的多核系统所能使用的处理器数 p p p 和我们的 w o r k W work W workW（通常至少是 O ( n ) O(n) O(n)的吧）相比，可以说小得可以当成一个常数，所以一般来讲，这个数是被 W / p W/p W/p 所主导的。这也就是前面所说的，为什么在实际中 W 比 D 对并行时间的影响还大，也是为什么我们要设计算法，work-efficiency 是很重要的。

很多已有的并行语言库都支持调度器，很多人也喜欢自己写自己的调度器，不管怎么说，都是要把调度器和真正的算法隔离开，做到互不影响。我个人用 cilk 用得比较多，这里用 cilk 的接口给大家举个例子：