任务怎么写？ （并行代码）

Question

英特尔线程构建模块给我留下了深刻的印象。我喜欢如何编写任务而不是线程代码，并且我喜欢它在我有限的理解下如何在后台工作（任务在池中，4 核上不会有 100 个线程，不能保证任务运行，因为它不在它自己的线程，并且可能远离池，但它可能与另一个相关任务一起运行，因此您不能做坏事，例如典型的线程不安全代码）。

我想更多地了解写作任务。我喜欢这里的“基于任务的多线程 - 如何为 100 个核心进行编程”视频 http:// /www.gdcvault.com/sponsor.php?sponsor_id=1（当前是倒数第二个链接。警告它不是“很棒”）。我最喜欢的部分是“解决迷宫最好并行完成”，大约在 48 分钟左右（您可以点击左侧的链接。这部分确实是您需要观看的全部内容）。

不过，我喜欢看到更多代码示例和一些如何编写任务的 API。有人有好的资源吗？我不知道一个类或一段代码在将其推入池中后会是什么样子，也不知道当您需要复制所有内容以及有多少内容被推入池中时，代码可能会看起来多么奇怪。

Answer 1

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

除了 javadoc 类文档之外，还有可用于开始使用该框架的资源。在 jsr166 页面 中，提到
“还有一个 wiki，其中包含这些课程的附加文档、注释、建议、示例等。”

fork-join 示例，例如矩阵乘法，是一个很好的选择开始的地方。

我使用 fork-join 框架来解决一些 Intel 的问题2009 年线程挑战。该框架是轻量级且低开销的 - 我的框架是解决 Kight's Tour 问题的唯一 Java 条目，并且它的性能优于竞赛中的其他条目。 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);

这是一个简单的示例，旨在使事情变得简单。实际上，性能不会那么好，因为与任务框架的开销相比，任务执行的工作是微不足道的。根据经验，任务应该执行一些重要的计算 - 足以使框架开销变得微不足道，但又不至于在问题结束时只有一个核心运行一项大型任务。将大型任务拆分为较小的任务可确保一个核心不会在其他核心闲置时执行大量工作 - 使用较小的任务可以让更多核心忙碌，但又不会太小以致任务不执行任何实际工作。

[...] 或者当
你需要复印所有的东西
以及有多少东西是被推动的
到水池上。

仅任务本身被推入池中。理想情况下，您不想复制任何内容：为了避免干扰和需要锁定（这会减慢程序速度），您的任务理想情况下应该使用独立数据。只读数据可以在所有任务之间共享，并且不需要复制。如果线程需要合作构建一些大型数据结构，最好它们单独构建各个部分，然后在最后将它们组合起来。组合可以作为单独的任务来完成，或者每个任务都可以将其一部分添加到整体解决方案中。这通常确实需要某种形式的锁定，但如果任务的工作量远大于更新解决方案的工作量，那么这不是一个严重的性能问题。 My Knight's Tour 解决方案采用这种方法来更新板上的公共旅游存储库。

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

Answer 2

玩那些声称可以解决无法解决的问题（最优任务调度是 NP 难）的“框架”根本不会对你有任何帮助——阅读有关并发算法的书籍和文章会对你有帮助。所谓的“任务”只不过是定义问题的可分离性（可以彼此独立计算的部分）的花哨名称。 可分离问题的类别非常小 - 并且它们已经在旧书中介绍过。

对于不可分离的问题，您必须规划阶段和阶段之间的数据屏障以交换数据。 > 用于同时数据交换的数据屏障的最佳编排不仅是 NP 困难，而且原则上不可能以通用方式解决 - 您需要检查所有可能的交错的历史 - 这就像已经指数集的幂集（就像去数学中从 N 到 R）。我提到的原因是为了明确指出，没有任何软件可以为您做到这一点，并且如何做到这一点本质上取决于实际算法以及并行化是否可行（即使理论上可行）的成败。

当您进入高并行度时，您甚至无法维护队列，甚至不再拥有内存总线 - 想象一下 100 个 CPU 试图在单个共享 int 上同步或尝试进行内存总线套利。您必须预先计划和预先配置将要运行的所有内容，并在白板上基本上证明其正确性。英特尔的线程构建模块在这个世界上还只是个小孩子。它们适用于仍然可以共享内存总线的少量核心。运行可分离的问题是轻而易举的事，无需任何“框架”即可完成。

因此，您又必须阅读尽可能多的不同并行算法。研究一个问题的近似最佳数据屏障布局通常需要 1-3 年的时间。当您在单个芯片上使用 16 个以上内核时，它就成为布局，因为只有第一个邻居可以有效地交换数据（在一个数据屏障周期期间）。因此，通过查看 CUDA 和论文以及 IBM 实验性 30 核 CPU 的结果，您实际上会学到比英特尔的销售宣传或某些 Java 玩具更多的知识。

请注意演示问题，这些问题所浪费的资源（核心数量和内存数量）远大于它们所实现的加速。如果需要 4 个内核和 4 倍 RAM 才能以 2 倍的速度解决某些问题，则该解决方案不可扩展以进行并行化。