如何编写任务？（并行代码）

Question

我对英特尔线程构建块印象深刻。我喜欢它让我写任务而不是线程代码的方式，以及我喜欢它如何在我的有限理解下工作（任务在池中，4个核心上不会有100个线程，任务不能保证运行，因为它不在自己的线程中，可能在池中较远的位置等待执行。但是它可能与另一个相关任务一起运行，因此您不能像典型的线程不安全代码那样做坏事）。

我想更多地了解编写任务的知识。我喜欢这里的“基于任务的多线程-如何为100个内核编写程序”视频http://www.gdcvault.com/sponsor.php?sponsor_id=1 （当前是倒数第二个链接。警告：它不是“很棒”的）。我最喜欢的部分是大约在48分钟处的“并行求解迷宫”（可以点击左侧的链接观看。如果你只看那部分，那真的就足够了）。

然而，我希望看到更多的代码示例和一些关于如何编写任务的API。是否有好的资源？我不知道在将类或代码片段推入池后它们会是什么样子，或者当您需要复制所有内容并将其推入池时代码会变得多么奇怪。

- user34537

Answer 1

Java有一种类似于线程构建块的并行任务框架，称为Fork-Join框架。它可用于当前的Java SE 6，并将包含在即将推出的Java SE 7中。

除了javadoc类文档外，还有可用于入门该框架的资源。从jsr166页面可以看到，还有一个维基百科，其中包含这些类的其他文档、注释、建议、示例等。

例如矩阵乘法的fork-join示例是一个很好的起点。

我在解决一些Intel 2009年线程挑战赛时使用了fork-join框架。该框架轻量且低开销 - 我的Java作品是Kight's Tour问题中唯一的参赛作品，并且在比赛中胜出了其他参赛作品。Java源代码和文稿可从挑战网站下载。

编辑：

我不知道将类或代码片段推入池后它们会变成什么样子[...]

您可以通过对ForKJoinTask子类之一进行子类化来创建自己的任务，例如RecursiveTask。以下是如何并行计算斐波那契数列的方法（摘自RecursiveTask javadocs - 注释为我的）。

 // declare a new task, that itself spawns subtasks. 
 // The task returns an Integer result.
 class Fibonacci extends RecursiveTask<Integer> {
   final int n;      // the n'th number in the fibonacci sequence to compute
   Fibonnaci(int n) { this.n = n; } // constructor
   Integer compute() {   // this method is the main work of the task
     if (n <= 1)         // 1 or 0, base case to end recursion
        return n;
     Fibonacci f1 = new Fibonacci(n - 1);  // create a new task to compute n-1
     f1.fork();                            // schedule to run asynchronously
     Fibonacci f2 = new Fibonacci(n - 2);  // create a new task to compute n-2
     return f2.invoke() + f1.join();       // wait for both tasks to compute.
       // f2 is run as part of this task, f1 runs asynchronously. 
       // (you could create two separate tasks and wait for them both, but running
       // f2 as part of this task is a little more efficient.
   }
 }

然后运行此任务并获取结果

// default parallelism is number of cores
ForkJoinPool pool = new ForkJoinPool(); 
Fibonacci f = new Fibonacci(100);
int result = pool.invoke(f);

这只是一个简单的例子，以保持事情简单。实际上，性能不会那么好，因为与任务框架的开销相比，任务执行的工作微不足道。作为一个经验法则，任务应该执行一些重要的计算 - 足以使框架开销微不足道，但不要过多地让你最终只剩下一个核心运行一个大任务。将大型任务分成较小的任务可以确保一个核心不会在其他核心处于空闲状态时做大量的工作 - 使用较小的任务可以使更多的核心保持繁忙，但不要太小，以至于任务没有真正的工作。

“[...]或者当您需要复制所有内容并将所有内容推送到池中时，代码可能会看起来多么奇怪。”

只有任务本身被推入池中。理想情况下，您不希望复制任何内容：为了避免干扰和需要锁定，这会减慢程序的速度，您的任务应该使用独立数据进行操作。只读数据可以在所有任务之间共享，并且不需要复制。如果线程需要协作构建某些大型数据结构，则最好将它们分别构建，然后在最后将它们组合起来。组合可以作为单独的任务完成，或者每个任务都可以将其拼图片段添加到整体解决方案中。这通常需要某种形式的锁定，但如果任务的工作量比更新解决方案的工作量大得多，则这不是一个重要的性能问题。我的骑士巡游解决方案采用这种方法来更新棋盘上的公共旅游存储库。

处理任务和并发与常规单线程编程相比是一种范式转变。通常有多种设计可用来解决给定问题，但只有其中一些适合线程解决方案。需要尝试几次才能掌握如何将熟悉的问题重新构建为多线程方式。学习的最佳方法是查看示例，然后自己尝试。始终进行性能分析，并测量更改线程数量的影响。您可以在池构造函数中显式设置要使用的线程（核心）数。当任务被线性分解时，随着线程数量的增加，您可以期望近似线性的加速。

- mdma

Answer 2

玩弄声称能解决不可解问题（最优任务调度是NP难题）的"框架"对你毫无帮助——阅读关于并发算法的书籍和文章才有用。所谓的“任务”只不过是一个花哨的名字，用于定义问题的可分离性（可以独立计算的部分）。

可分离问题的类别非常少，而且早已在古老的书籍中有所涵盖。

对于不可分离的问题，你需要规划阶段和数据屏障，以便在阶段之间交换数据。同时进行数据交换的数据屏障的最佳协调不仅是NP难题，而且从原则上来说是无法以一般方式解决的——你需要检查所有可能的交错历史，这就像是指数级的集合的幂集（就像在数学中从N到R的转换）。我提及这一点的原因是为了让清楚地明白，没有任何软件能够代替你完成这个任务，并且如何做取决于实际算法本身，也是并行化是否可行的决定因素（即使从理论上讲是可行的）。

当你进入高并行性时，你甚至无法维护一个队列，你甚至不再有内存总线 - 想象一下100个CPU试图在一个共享int上同步或者尝试进行内存总线套利。你必须预先计划和预先配置所有即将运行的东西，并在白板上证明正确性。英特尔的线程构建块在那个世界里只是小儿科。它们适用于仍然可以共享内存总线的少数核心。运行可分离问题是一个轻而易举的任务，你可以不用任何“框架”来完成。

因此，你又得阅读尽可能多的不同并行算法。通常需要1-3年时间来研究近似最佳数据屏障布局的一个问题。当你在单个芯片上使用16个以上的核心时，它就变成了布局问题，因为只有相邻的核心才能在一个数据屏障周期内有效地交换数据。所以，通过查看CUDA、IBM的实验性30核CPU的论文和结果，你会真正学到更多，而不是听英特尔的销售宣传或者一些Java玩具。

要注意的是，演示问题往往浪费资源（核心数量和内存）的规模要比它们实际获得的加速更大。如果解决某个问题需要4个核心和4倍的内存才能以2倍的速度解决，那么这个解决方案在并行化方面就不具备可伸缩性。

- ZXX