自动并行化

Question

对于一个试图自动将代码分割为线程的项目，你有什么意见（也许在编译时，可能是在运行时）。

请查看下面的代码：

for(int i=0;i<100;i++)
   sum1 += rand(100)
for(int j=0;j<100;j++)
   sum2 += rand(100)/2

这种代码可以自动分割成2个并行运行的线程。您认为这种情况可能吗？我有一种感觉，从理论上讲它是不可能的（它让我想起了停机问题），但我无法证明这个想法。

您认为这是一个有用的项目吗？是否有类似的东西？

- DuduAlul

---

在这种情况下，即使手动操作也是不可能的，因为 rand 修改了全局状态；任何尝试并行化此过程都会改变代码的语义。 - Philipp

@Philipp：我刚想在我的答案中指出这一点；）（尽管某些随机函数是线程安全的...） - Reed Copsey

@philipp 你能解释一下吗？ 为什么不能同时运行两个线程，其中第一个线程调用第一个循环，第二个线程调用第二个循环？ - DuduAlul

@MrOhad：因为“rand()”在内部不一定是线程安全的。如果你从多个线程同时调用它，就会引入竞态条件。 - Reed Copsey

我明白你的意思了，我是指一个线程安全的rand()函数。 - DuduAlul

Answer 1

这被称为自动并行化。如果你正在寻找可以为你完成此操作的程序，那么目前还没有这样的程序。不过，这可能会出现。这是一个难题，并且是一个活跃研究领域。如果你仍然感兴趣...

可以自动将示例拆分为多个线程，但不是您想象的方式。一些当前的技术尝试在其自己的线程中运行每次迭代的 for -loop。其中一个线程将获得偶数索引（i = 0，i = 2，...），另一个将获得奇数索引（i = 1，i = 3，...）。完成该 for -loop后，可以启动下一个循环。其他技术可能会更疯狂，执行 i ++ 增量在一个线程中进行，而在另一个线程中执行 rand（）。

正如其他人所指出的那样，迭代之间存在真正的依赖性，因为 rand（）具有内部状态。这本身并不妨碍并行化。编译器可以识别内存依赖性，并且可以从一个线程转发 rand（）的修改状态到另一个线程。但是它可能会限制您只能使用少数几个并行线程。如果没有依赖关系，您可以在所有可用的核心上运行此代码。

如果您真正对此主题感兴趣，并且不介意阅读研究论文：

1. 使用解耦软件管道自动提取线程（2005年）G. Ottoni。
2. 使用软件多线程事务进行推测并行化（2010年）A. Raman。

- Karmastan

---

+1，特别是对于那些有趣的文章。我简要地阅读了第二篇文章，虽然我没有完全理解所有细节，但它似乎为每个线程提供了工作内存的副本，并在计算后合并它（这可能会失败）。尽管结果令人印象深刻，但我认为我们距离自动化并行化一般代码的工具还需要数年时间。 - waxwing

Answer 2

这几乎是不可能的。

问题在于，为了有效地并行化，您需要知道比编译器甚至运行时更多的信息，而这些信息是不容易获得的。

虽然可能对非常简单的循环进行并行化，但是即使如此，也存在风险。例如，如果rand()不是线程安全的，则上述代码只能并行化。 （Java的Math.random()已经为您同步。）

目前来看，尝试进行这种类型的自动并行化对于任何“真实”应用程序都不实用。

- Reed Copsey

---

编译器能否以某种方式检查特定函数是否线程安全？例如，它是否仅使用本地变量？此外，程序员如何启用注释线程安全的函数/代码块？ - DuduAlul

只是一个提醒，即使 Math.random() 是同步的，它仍然会修改内部 Random 对象的状态。即使使用相同的种子值初始化 Random 对象，并行化也可能产生不同的结果。 - waxwing

@waxwing：确实是一种竞争条件，这可能或可能不重要。@MrOhad：在这种情况下，存在许多因素，自动并行化任何“重要”的代码块将非常困难。这就是为什么所有这些都通过引导并行化完成。请参考Intel的TBB，Microsoft的CCR或TPL，以了解此领域的工作示例。 - Reed Copsey

Answer 3

当然可以，但这是一项非常困难的任务。几十年来，编译器研究的核心就在于此。基本问题在于，我们不能制作一个工具，能够为Java代码找到最佳线程分区（这相当于停机问题）。

相反，我们需要将目标从最佳分区放松到对代码的某些分区。总的来说，这仍然非常困难。因此，我们需要找到简化问题的方法，其中之一是忘记通用代码，开始关注特定类型的程序。如果您具有简单的控制流（常量有界for循环，有限的分支...），那么您可以取得更多进展。

另一种简化是减少您尝试保持繁忙的并行单元数量。如果将这两种简化方式结合起来，则会得到自动矢量化的最新技术水平（一种用于生成MMX / SSE样式代码的特定类型的并行化）。达到这个阶段已经花费了几十年的时间，但是如果您看看像Intel这样的编译器，性能正在变得相当不错。

如果您从单个线程内的矢量指令转移到进程内的多个线程，则在代码的不同点之间移动数据的延迟会大大增加。这意味着您的并行化必须更好，才能克服通信开销。目前，这是研究的一个非常热门话题，但是没有自动用户定向的工具可用。如果您能编写一个起作用的工具，那么对许多人来说将会非常有趣。

对于您的具体示例，假设rand()是并行版本，因此您可以从不同的线程独立调用它，那么很容易看出代码可以分为两部分。编译器只需要进行依赖性分析，就可以看到两个循环均不使用另一个循环中的数据或影响其他循环。因此，在用户级别代码中它们之间的顺序是一种虚假依赖关系，可以通过将它们放在不同的线程中来拆分。

但是，这并不是您想要并行化代码的方式。看起来每个循环迭代都依赖于前一个循环，因为sum1 += rand(100)与sum1 = sum1 + rand(100)相同，其中右侧的sum1是上一次迭代的值。然而，涉及的唯一操作是加法，它是可结合的，因此我们可以以许多不同的方式重写总和。

sum1 = (((rand_0 + rand_1) + rand_2) + rand_3) ....
sum1 = (rand_0 + rand_1) + (rand_2 + rand_3) ...

第二种方法的优点在于，括号内的每个单独的加法都可以与其他所有加法并行计算。一旦你有了50个结果，它们就可以组合成另外25个加法，以此类推...这样做需要更多的工作量，50+25+13+7+4+2+1=102个加法，而原来只有100个，但除了并行分叉/合并和通信开销之外，只有7个连续步骤，因此运行速度快14倍。这种加法树在并行体系结构中称为聚集操作，往往是计算的昂贵部分。

在GPU等非常并行的体系结构上，上述描述将是并行化代码的最佳方式。如果在进程内使用线程，则会被开销淹没。

总之：完美地做到这一点是不可能的，很难做到好，目前还有许多积极的研究正在寻找我们能够做到多少。

- Andrew

Answer 4

有一些项目尝试简化并行化，比如Cilk。然而，它并不总是有效。

- Amber

Answer 5

在一般情况下，能否知道一段代码是否可以并行化并不重要，因为即使你的算法无法检测出所有可以并行化的情况，也许它可以检测出其中的一些。

但这并不意味着这样做会有用。考虑以下几点：

1. 首先，在编译时要检查所有可能进入要并行化的结构的代码路径。除了简单计算之外，这可能会很棘手。
2. 其次，你必须以某种方式决定什么是可并行化的，什么是不可并行化的。例如，你不能简单地将修改相同状态的循环分成多个线程。这可能是一个非常困难的任务，在许多情况下，你最终会不确定 - 两个变量实际上可能引用同一个对象。
3. 即使你能够实现这一点，对用户来说也会变得混乱。很难解释为什么他的代码无法并行化以及应该如何更改。

我认为，如果你想在Java中实现这一点，你需要将其写成一个库，并让用户决定要并行化什么（库函数与注解一起使用？只是随便想想）。函数式语言更适合这样的任务。

作为一则趣闻：在并行编程课程中，我们必须检查代码并决定它是否可并行化。我记不清具体细节了（关于“最多一次”属性的什么东西？有人能告诉我吗？），但故事的寓意是，即使对于看似微不足道的情况，这也是极其困难的。

- waxwing

Answer 6

我学到了自JDK 1.8（Java 8）起，可以使用parallelStream()在流使用中利用多个CPU核心。

然而，在最终决定使用parallelStream()进入生产之前，最好通过基准测试比较sequential()和parallel()的性能，然后决定哪个更理想。

为什么呢？原因是：在需要进行自动拆装箱操作时，平行流可能会比顺序流表现得差得多。对于这些情况，建议使用Java 8的原始流，例如IntStream、LongStream、DoubleStream。

参考资料：《现代Java实战》：曼宁出版社2019年

- mobileappDev

Answer 7

编程语言是Java，而Java是一种虚拟机。因此，一个人应该能够在VM拥有的不同线程上在运行时执行代码。由于所有的内存等都是这样处理的，它不会造成任何破坏。您可以将代码视为指令堆栈，估计执行时间，然后将其分配到一个数组的线程上，每个线程都有大致相同的执行堆栈时间。尽管如此，某些图形（如OpenGL立即模式）需要维护顺序，并且大多数情况下不应该被线程化。

- Deathlymad