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

This is a long studied topic. While you can implicitly derive parallelism in Haskell code, the problem is that there is too much parallelism, at too fine a grain, for current hardware.

So you end up spending effort on book keeping, not running things faster.

Since we don't have infinite parallel hardware, it is all about picking the right granularity -- too coarse and there will be idle processors, too fine and the overheads will be unacceptable.

What we have is more coarse grained parallelism (sparks) suitable for generating thousands or millions of parallel tasks (so not at the instruction level), which map down onto the mere handful of cores we typically have available today.

Note that for some subsets (e.g. array processing) there are fully automatic parallelization libraries with tight cost models.

For background on this see Feedback Directed Implicit Parallelism, where they introduce an automated approach to the insertion of par in arbitrary Haskell programs.

于 2013-02-21T17:04:30.487 に答える
26

あなたのコード ブロックは、aとの間の暗黙的なデータ依存性のために最良の例ではないかもしれませんが、bこれら 2 つのバインディングがその中で交換されることに注意する価値があります。

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

同じ結果が得られます

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

したがって、これはまだ投機的な方法で並列化できます。これはモナドとは何の関係もないことに注意してください。たとえば、let-block 内のすべての独立した式を並列に評価することも、そうするバージョンを導入することもできletます。Common Lispのlparallel ライブラリがこれを行います。

さて、私は決してこのテーマの専門家ではありませんが、これは問題に対する私の理解です. 主な障害は、複数の式の評価を並列化することが有利な場合を判断することです。評価のために個別のスレッドを開始することに関連するオーバーヘッドがあり、例が示すように、無駄な作業が発生する可能性があります。一部の式は小さすぎて、オーバーヘッドに見合う並列評価を行うことができない場合があります。私が理解しているように、式のコストの完全に正確なメトリックを考え出すことは、停止問題を解決することになるため、何を並行して評価するかを決定するためにヒューリスティックなアプローチを使用することになります。

その場合、問題により多くのコアを投入することが常に高速であるとは限りません。利用可能な多くの Haskell ライブラリを使用して問題を明示的に並列化する場合でも、大量のメモリ割り当てと使用量、およびこれがガベージ コレクターと CPU キャッシュに与える負担のために、式を並列で評価するだけではあまり高速化されないことがよくあります。最終的には、コンパクトなメモリ レイアウトと、データをインテリジェントにトラバースする必要があります。16 個のスレッドがリンクされたリストをトラバースすると、メモリ バスでボトルネックが発生し、実際には動作が遅くなる可能性があります。

少なくとも、どの式を効果的に並列化できるかは、多くのプログラマーには明らかではないため (少なくともこのプログラマーにはそうではありません)、コンパイラーに効果的に並列化させることは自明ではありません。

于 2013-02-21T15:46:19.190 に答える
8

簡単な答え: 並行して実行すると、高速ではなく低速になることがあります。そして、いつそれが良いアイデアで、いつそれが良いアイデアではないかを理解することは、未解決の研究課題です.

ただし、「スレッド、デッドロック、競合状態に煩わされることなく、これらすべてのコアを突然利用する」ことはできます。自動ではありません。どこでそれを行うべきかについてのヒントをコンパイラに与えるだけです! :-D

于 2013-02-21T18:44:04.097 に答える
4

その理由の1つは、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"

この関数は、最初に最初のリストを印刷し、次に2番目に印刷します。それはうまくいくでしょうz（結果として無限の数のストリームを出力しますが、Haskellはそれを処理できます）。b最終的にメモリが不足します。

これで、一般的に、計算が終了するかどうか、および計算が消費するリソースの数はわかりません。Haskellでは無限のリストは完全に問題ありません：

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

したがって、Haskellで式を評価するためにスレッドを生成すると、完全に評価されることを意図していないもの（たとえば、すべての素数のリスト）を評価しようとする可能性がありますが、プログラマーは構造の一部として使用します。上記の例は非常に単純で、コンパイラがそれらに気付く可能性があると主張するかもしれません-しかし、停止問題（任意のプログラムとその入力を受け取り、それが終了するかどうかをチェックするプログラムを書くことはできません）のために一般的には不可能です-したがって、そうではありません安全な最適化。

さらに、他の回答で言及されているように、追加のスレッドのオーバーヘッドが関与する価値があるかどうかを予測することは困難です。GHCはグリーンスレッドを使用してスパーク用の新しいスレッドを生成しませんが（カーネルスレッドの数は固定されています-いくつかの例外はあります）、データを1つのコアから別のコアに移動し、それらの間で同期する必要があります。これは非常にコストがかかる可能性があります。

parただし、Haskellは、同様の機能によって言語の純粋さを損なうことなく、並列化をガイドしてきました。

于 2013-02-21T18:54:36.487 に答える
3

実際にそのような試みはありましたが、利用可能なコアの数が少ないため、一般的なハードウェアではそうではありませんでした. このプロジェクトはReduceronと呼ばれます。Haskell コードを高レベルの並列処理で実行します。それが適切な 2 GHz ASIC コアとしてリリースされた場合、Haskell の実行速度が大幅に向上するでしょう。

于 2016-09-03T15:15:29.840 に答える