JVM 是否有能力检测并行化的机会? [英] Does the JVM have the ability to detect opportunities for parallelization?

问题描述

Java Hotspot 可以很好的优化顺序代码.但我猜测随着多核计算机的出现，运行时的信息是否可以用于检测运行时并行化代码的机会，例如检测软件流水线是否可能在循环中进行等.

The Java Hotspot can optimize the sequential code very well. But I was guessing that with the advent of multi-core computers, can the information at runtime be useful to detect opportunities to parallelize the code at runtime, for example detect the software pipelining is possible in a loop and similar things.

在这个主题上有没有做过有趣的工作?或者是研究失败或一些难以解决的停顿问题?

Was any interesting work ever been done on this topic ? Or is it a research failure or some halting problem which is very hard to solve?

推荐答案

我认为 Java 的当前保证内存模型使得在编译器或虚拟机级别进行很多(如果有的话)自动并行化变得非常困难.Java 语言没有语义来保证任何数据结构甚至有效地不可变，或者任何特定语句都是纯粹的且没有副作用，因此编译器必须自动计算出这些以进行并行化.在编译器中可以推断出一些基本的机会，但一般情况将留给运行时，因为动态加载和绑定可能会引入编译时不存在的新变化.

I think the current guarantees of the Java memory model make it quite hard to do much, if any, automatic parallelization at the compiler or VM level. The Java language has no semantics to guarantee that any data structure is even effectively immutable, or that any particular statement is pure and free of side-effects, so the compiler would have to figure these out automatically in order to parallelize. Some elementary opportunities would be possible to infer in the compiler, but the general case would be left to the runtime, since dynamic loading and binding could introduce new mutations that didn't exist at compile-time.

考虑以下代码:

for (int i = 0; i < array.length; i++) {
    array[i] = expensiveComputation(array[i]);
}

如果 expensiveComputation 是一个 纯函数，那么并行化将是微不足道的a>，它的输出只取决于它的参数，如果我们能保证 array 在循环过程中不会改变(实际上我们正在改变它，设置 array[i]=...，但在这种特殊情况下 expensiveComputation(array[i]) 总是首先被调用，所以这里没问题 - 假设 array 是本地的而不是从其他任何地方引用).

It would be trivial to parallelize, if expensiveComputation is a pure function, whose output depends only on its argument, and if we could guarantee that array wouldn't be changed during the loop (actually we're changing it, setting array[i]=..., but in this particular case expensiveComputation(array[i]) is always called first so it's okay here - assuming that array is local and not referenced from anywhere else).

此外，如果我们像这样改变循环:

Furthermore, if we change the loop like this:

for (int i = 0; i < array.length; i++) {
    array[i] = expensiveComputation(array, i);
    // expensiveComputation has the whole array at its disposal!
    // It could read or write values anywhere in it!
}

那么即使 expensiveComputation 是纯的并且不改变它的参数，并行化也不再是微不足道的了，因为并行线程会改变 的内容array 而其他人正在阅读它！并行器必须弄清楚在各种条件下expensiveComputation 数组的哪些部分是指，并相应地进行同步.

then parallelization is not trivial any more even if expensiveComputation is pure and doesn't alter its argument, because the parallel threads would be changing the contents of array while others are reading it! The parallelizer would have to figure out which parts of the array expensiveComputation is referring to under various conditions, and synchronize accordingly.

也许检测所有可能发生的突变和副作用并在并行化时将它们考虑在内并非完全不可能，但非常> 难，当然，在实践中可能不可行.这就是为什么并行化并确定一切仍然正常工作是 Java 程序员头疼的原因.

Perhaps it wouldn't be outright impossible to detect all mutations and side-effects that may be going on and take those into account when parallelizing, but it would be very hard, for sure, probably infeasible in practice. This is why parallelization, and figuring out that everything still works correctly, is the programmer's headache in Java.

函数式语言(例如 JVM 上的 Clojure)是该主题的热门答案.纯的、无副作用的函数与 persistent(有效不可变")数据结构一起可能允许隐式或几乎隐式并行化.让我们将数组的每个元素加倍:

Functional languages (e.g. Clojure on JVM) are a hot answer to this topic. Pure, side-effect-free functions together with persistent ("effectively immutable") data structures potentially allow implicit or almost implicit parallelization. Let's double each element of an array:

(map #(* 2 %) [1 2 3 4 5])
(pmap #(* 2 %) [1 2 3 4 5])  ; The same thing, done in parallel.

这是透明的，原因有二:

This is transparent because of 2 things:

1. 函数 #(* 2 %) 是纯粹的:它接受一个值并给出一个值，就是这样.它不会改变任何东西，它的输出只取决于它的参数.
2. 向量 [1 2 3 4 5] 是不可变的:无论谁在看，什么时候看，都是一样的.

1. The function #(* 2 %) is pure: it takes a value in and gives a value out, and that's it. It doesn't change anything, and its output depends only on its argument.
2. The vector [1 2 3 4 5] is immutable: no matter who's looking at it, or when, it's the same.

可以在 Java 中创建纯函数，但是 2) 不变性是这里的致命弱点.Java 中没有不可变的数组. 学究起来，Java 中没有什么 是不可变的，因为即使 final 字段也可以使用反射进行更改.因此不能保证计算的输出(或输入！)不会被并行化改变 -> 所以自动并行化通常是不可行的.

It's possible to make pure functions in Java, but 2), immutability, is the Achilles' heel here. There are no immutable arrays in Java. To be pedant, nothing is immutable in Java because even final fields can be changed using reflection. Therefore no guarantees can be made that the output (or input!) of a computation wouldn't be changed by parallelization -> so automatic parallelization is generally infeasible.

由于不变性，愚蠢的加倍元素"示例扩展到任意复杂的处理:

The dumb "doubling elements" example extends to arbitrarily complex processing, thanks to immutability:

(defn expensivefunction [v x]
  (/ (reduce * v) x))


(let [v [1 2 3 4 5]]
  (map (partial expensivefunction v) v)) ; pmap would work equally well here!

这篇关于JVM 是否有能力检测并行化的机会?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！