java - 自动并行化

Question

对于尝试获取代码并将其自动拆分为线程(可能是编译时，可能是运行时)的项目，您有何看法。

看看下面的代码:

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

这种代码可以自动拆分为 2 个并行运行的不同线程。你认为这有可能吗？我有一种感觉，理论上这是不可能的(这让我想起了停机问题)，但我无法证明这个想法是正确的。

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

Answer 1

这称为自动并行化。如果您正在寻找可以为您执行此操作的程序，那么目前尚不存在。但它可能最终。这是一个难题，也是一个活跃的研究领域。如果您仍然好奇...

可以将您的示例自动拆分为多个线程，但不是您所想的那样。当前的一些技术尝试在其自己的线程中运行 for 循环的每次迭代。一个线程将获得偶数索引 (i=0, i=2, ...)，另一个线程将获得奇数索引 (i=1, i=3, ...)。一旦 for 循环完成，就可以开始下一个循环。其他技术可能会更疯狂，在一个线程中执行 i++ 增量，在单独的线程中执行 rand()。

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

如果您真的对这个主题感兴趣并且不介意浏览研究论文:

1. Automatic thread extraction with decoupled software pipelining (2005) G. Ottoni。
2. Speculative parallelization using software multi-threaded transactions (2010) 作者:A. Raman。