61

Haskell 是函数式且纯粹的，因此基本上它具有编译器能够处理隐式并行性所需的所有属性。

考虑这个简单的例子：

f = do
  a <- Just 1
  b <- Just $ Just 2
  -- ^ The above line does not utilize an `a` variable, so it can be safely
  -- executed in parallel with the preceding line
  c <- b
  -- ^ The above line references a `b` variable, so it can only be executed
  -- sequentially after it
  return (a, c)
  -- On the exit from a monad scope we wait for all computations to finish and 
  -- gather the results

执行计划的示意图可以描述为：

               do
                |
      +---------+---------+
      |                   |
  a <- Just 1      b <- Just $ Just 2
      |                   |
      |                 c <- b
      |                   |
      +---------+---------+
                |
           return (a, c)

为什么编译器中还没有使用标志或编译指示实现这样的功能？有哪些实际原因？

4

5 回答 5

81

这是一个长期研究的话题。虽然您可以在 Haskell 代码中隐式推导出并行性，但问题是对于当前硬件而言并行性太多，粒度太细。

因此，您最终将精力花在记账上，而不是更快地运行。

因为我们没有无限的并行硬件，所以一切都是为了选择正确的粒度——太粗就会有空闲的处理器，太细就会产生不可接受的开销。

我们所拥有的是更粗粒度的并行性（火花），适用于生成数千或数百万个并行任务（因此不在指令级别），它们映射到我们今天通常可用的仅有的少数内核上。

请注意，对于某些子集（例如数组处理），有具有严格成本模型的全自动并行化库。

有关这方面的背景，请参阅反馈定向隐式并行，他们在其中介绍了一种自动化方法来插入par任意 Haskell 程序。

于 2013-02-21T17:04:30.487 回答
26

a虽然由于和之间的隐式数据依赖性，您的代码块可能不是最好的示例b，但值得注意的是，这两个绑定在

f = do
  a <- Just 1
  b <- Just $ Just 2
  ...

将给出相同的结果

f = do
  b <- Just $ Just 2
  a <- Just 1
  ...

所以这仍然可以以推测的方式并行化。值得注意的是，这不需要与 monad 有任何关系。例如，let我们可以并行计算一个 -block 中的所有独立表达式，或者我们可以引入一个let可以这样做的版本。Common Lisp的lparallel 库可以做到这一点。

现在，我绝不是这方面的专家，但这是我对这个问题的理解。一个主要的绊脚石是确定何时并行计算多个表达式是有利的。启动单独的线程进行评估会产生开销，并且如您的示例所示，它可能会导致工作浪费。某些表达式可能太小而无法使并行评估值得开销。据我了解，提出一个完全准确的表达式成本指标将相当于解决停止问题，因此您只能使用启发式方法来确定要并行评估的内容。

那么在一个问题上投入更多的核心并不总是更快。即使在使用许多可用的 Haskell 库显式并行化问题时，由于大量内存分配和使用以及这给垃圾收集器和 CPU 缓存带来的压力，您通常不会仅仅通过并行评估表达式来看到太多的加速。您最终需要一个漂亮的紧凑内存布局并智能地遍历您的数据。让 16 个线程遍历链表只会成为内存总线的瓶颈，实际上可能会使事情变慢。

至少，什么表达式可以有效地并行化对于许多程序员来说并不明显（至少对这个来说不是），所以让编译器有效地做到这一点并非易事。

于 2013-02-21T15:46:19.190 回答
8

简短的回答：有时并行运行的东西变得更慢，而不是更快。弄清楚什么时候是，什么时候不是一个好主意是一个未解决的研究问题。

但是，您仍然可以“突然利用所有这些内核，而不必担心线程、死锁和竞争条件”。这不是自动的；你只需要给编译器一些关于在哪里做的提示！:-D

于 2013-02-21T18:44:04.097 回答
4

原因之一是因为 Haskell 是非严格的，默认情况下它不会评估任何内容。一般来说，编译器不知道计算a并b终止，因此试图计算它会浪费资源：

x :: Maybe ([Int], [Int])
x = Just undefined
y :: Maybe ([Int], [Int])
y = Just (undefined, undefined)
z :: Maybe ([Int], [Int])
z = Just ([0], [1..])
a :: Maybe ([Int], [Int])
a = undefined
b :: Maybe ([Int], [Int])
b = Just ([0], map fib [0..])
    where fib 0 = 1
          fib 1 = 1
          fib n = fib (n - 1) + fib (n - 2)

考虑以下功能

main1 x = case x of
              Just _ -> putStrLn "Just"
              Nothing -> putStrLn "Nothing"

(a, b)部分不需要评估。一旦你得到 x = Just _ 你就可以继续分支 - 因此它适用于所有值，但a

main2 x = case x of
              Just (_, _) -> putStrLn "Just"
              Nothing -> putStrLn "Nothing"

此函数强制对元组进行评估。因此x将因错误而终止，而休息将起作用。

main3 x = case x of
              Just (a, b) -> print a >> print b
              Nothing -> putStrLn "Nothing"

此函数将首先打印第一个列表，然后打印第二个。它适用于z（导致打印无限的数字流，但 Haskell 可以处理它）。b最终会耗尽内存。

现在通常您不知道计算是否终止以及它将消耗多少资源。无限列表在 Haskell 中非常好：

main = maybe (return ()) (print . take 5 . snd) b -- Prints first 5 Fibbonacci numbers

因此，在 Haskell 中生成线程来评估表达式可能会尝试评估一些不应该被完全评估的东西——比如所有素数的列表——但程序员将其用作结构的一部分。上面的例子非常简单，你可能会争辩说编译器会注意到它们——但是由于停机问题，通常不可能（你不能编写接受任意程序及其输入并检查它是否终止的程序）——因此它不是安全优化。

此外 - 其他答案提到过 - 很难预测额外线程的开销是否值得参与。即使 GHC 没有使用绿色线程（使用固定数量的内核线程 - 除了一些例外）为 spark 生成新线程，您仍然需要将数据从一个核心移动到另一个核心并在它们之间进行同步，这可能会非常昂贵。

然而，Haskell 确实引导了并行化，而不会破坏语言的纯度par和类似的功能。

于 2013-02-21T18:54:36.487 回答
3

实际上有这样的尝试，但由于可用内核数量较少，因此没有在普通硬件上进行。该项目称为Reduceron。它以高并行度运行 Haskell 代码。如果它曾经作为适当的 2 GHz ASIC 内核发布，我们将在 Haskell 执行速度方面取得重大突破。

于 2016-09-03T15:15:29.840 回答