問題タブ [data-parallel-haskell]

2 つのリストを並行してマージしようとしています。私は2つのソートされたリストを持っています[(i, j, val)]。リストは でソートされj、jでソートされiます。2 つのリストに同じものが含まれている場合、(i, j)それらの値が追加されて 1 つに結合されます。たとえば、最初のリストに含まれ(i, j, val_1)ていて 2 番目のリストに含まれている(i, j, val_2)場合、2 つを結合すると結果が になり(i, j, val_1 + val_2)ます。

マージは非常にシーケンシャルであり、検索した結果、この論文を見つけました。この論文のアイデアは、二分探索を使用して、最終的なリスト内の要素のランクを取得することです。i最初のリストの 番目の位置にいるとしましょう。したがって、最初のリスト(i - 1)の現在の要素よりも小さい要素があり、2 番目のリストのこの要素の位置に対してバイナリ検索を実行します (この位置が であるとしますj)。したがって、最終リストの現在の要素の位置はi + j - 1( i - 1 + j - 1 + 1) になります。このために dph-par を使用して Haskell コードを作成しましたが、更新に行き詰まっています。私は2つのリストを持っています

これら2つのリストを更新した後、

Bsearch.hs

Main.hs

誰かが更新を手伝ってくれませんか。よくわかりませんが、このアルゴリズムには多くのデータ移動が含まれているため、この目的のためにもっと良いものを提案してください。

私はいくつかのデータ並列Haskellコードで遊んでいて、プレフィックス合計が必要であることに気づきました。ただし、プレフィックス合計のdphパッケージに基本的な演算子はありませんでした。

私は自分でロールしましたが、dphを初めて使用するため、並列化を適切に利用しているかどうかはわかりません。

GHC 7.4.1 を使用して、Repa を使用するプログラムをコンパイルしようとしています。しかし、コンパイルの途中で、メモリが不足しています。ではghc -v、SpecConstr フェーズでスタックしていることがわかります。

SpecConstr は、GHC の Core-to-Core 変換の 1 つです。サイモン・ペイトン・ジョーンズはここに素晴らしい説明をしており、ここにいくつかのコードがありますが、私はGHCの内部の仕組みにあまり慣れていないので、かなり時間がかかります.

どうにかしてコンパイラを助けたいのですが、どこで動かなくなっているかを知る方法はありますか? または、より大きなマシンで再コンパイルできるようになるまで、この段階でメモリ使用量を制限する方法はありますか?

ありがとう、チャド

具体的には、次のような無害に見える小さなRepa3プログラムがあります。

2Ghzコア2デュオラップトップで640x420の画像を処理するには、これだけの時間がかかります。

Repa 2を使用して、はるかに複雑なアルゴリズムでパフォーマンスが大幅に向上したため、何かがかなり間違っているに違いないことを知っています。そのAPIの下で、すべての配列変換の前に「force」への呼び出しを追加することで、大きな改善が見られました（これは理解しています）マップ、畳み込​​み、トラバースなどへのすべての呼び出しを意味します）。Repa 3で行う類似のことを完全に理解することはできません。実際、新しいマニフェストタイプのパラメーターは、配列を強制する必要がある場合にあいまいさがないことを保証することになっていると思いましたか？そして、新しいモナディックインターフェイスはこのスキームにどのように適合しますか？Don Sによるすばらしいチュートリアルを読みましたが、Repa2と3のAPIの間には、オンラインAFAIKではほとんど議論されていないいくつかの重要なギャップがあります。

もっと簡単に言えば、上記のプログラムの効率を修正するための最小限の影響を与える方法はありますか？

私は Data Parallel Haskell について多くの調査を行ってきましたが、2 つの別個の並列配列タイプを見つけました。この[::]タイプは研究論文でより多く見られるようで、理想的なタイプのPArrayようですが、どこにでも行き詰まっているようです. [::]この件に関する wiki ページでは、型の配列をベクトル化されていないコードに渡すことができないことが非常に明確になっています。なんで？なぜこの中間PArrayタイプがあるのですか？それは私には完全に不必要に思えます。ウィキではこれを「フラット配列」と呼んでいますが、ベクトル化の要点は、並列配列をフラットにすることです。

更新: より多くの論文、ドキュメント、およびソース コードを読んだ後、私はさらに混乱しました。[::]またはその同義語はフラット配列としてGHC.PArrPArrに実装されているようですが、複数の場所で「フラット」と呼ばれる中間型である は、Data.Array.Parallel.PArray.Baseおよびそこからインポートされた他のモジュールに実装されています。私が読んだ非常に多くの論文で説明されている平坦化変換を使用したデータファミリ。フラット配列がフラットではなく、ネストされた配列がフラットなのはなぜですか?PArray

更新 2: さらに調査した結果、ドキュメンテーションが完全に混乱していることがわかりました。この wiki ページには、ほぼ 1 年間コンテンツの更新がなく、ハックのドキュメントと矛盾しており ( Data.Array.Parallel.Preludeを参照してください。特別なプレリュードをインポートしないことが明示されています)、一般的に古くなっています。GHC Tracのページも古くなっています。たとえば、少なくとも Hackage に関する限り、パッケージについて言及している DPH パッケージのガイドが含まれています (私はどこを見ればよいかわかりません。存在せず、dph-lifted-vseg などのパッケージについて言及していません。

より良いことに、 GHC.PArrのコメントのこの部分によって示唆された、最初の更新に対する答えを理解したと思います:

ベクトル化が有効になっている場合、そのモジュールは、平坦化変換を使用する別の表現に自動的に置き換えられると思います。これは次のようなものかもしれません

、私の元の問題を解決します。ただし、後者の点があまり意味をなさないだけでなく ([::]ベクトル化がオフのときにフラットな配列型に制限するのはなぜですか?)、上記のコメント以外にどちらの理論も裏付ける証拠を見つけられませんでした。何かを学ぶための唯一の信頼できる方法は、GHC のソースを見ることだと思われます。そのサイズと複雑さを考えると、たとえ成功すると確信していたとしても、それは私が熱望しているものです。

DPH を使用して nqueens の問題を実装しようとしましたが、最終的に GHC.Prim.Int# をベクトル化できませんというエラーが発生しました。エラーをグーグルで調べたところ、パターンマッチングに使用されるリテラルのベクトル化について話している GHC バグが見つかりました (http://haskell.1045720.n5.nabble.com/GHC-5702-Can-t-vectorise-pattern-matching-on -numeric-literals-td5076659.html)。これが同じバグかどうかはわかりません。私のコードは次のとおりです。

何か間違ったことをしている場合はお知らせください。GHC 7.4.1 を使用しています。

前もって感謝します。

2012.4.0.0 Haskellプラットフォームでデータ並列Haskellを使用している人はいますか？

私はHaskellの初心者ですが、リストから並列配列への切り替えを試してみたかったのです。

実行してみると

ビルドの問題が発生しbmp.1.2.3.1ます：

確かにこれはある種のバージョンの不一致ですが、どうしたらよいかわかりません。そこに専門家はいますか？

Data Parallel Haskell を実行していくつかの簡単な実験をしようとしていますが、明らかにいくつかのオプションが間違っています。のような非常に単純なことをしようとしても

例外が発生します

何かが間違って設定されていると仮定します - しかし...

GHCi を使用しようとするときと、GHC で生成された実行可能ファイルを実行するときの両方で、同じエラーが発生します。

私は最近、ライブラリとライブラリでの今後の一般化されたストリームの融合に関する論文を読みました。とても面白い展開になりそうです。私は今、実験を始めています (GHC 7.6 から始めて、7.8 SIMD バージョンが出たらアップグレードする予定です)。また、ライブラリのドキュメントから、並列配列の作業ができることがわかります。GHC 7.4の時点で準備ができていないと見なされていたものと比較して、成熟したバージョンのようです. GHC 7.6 の時点で、とパッケージの間の主な長所と短所は何なのか疑問に思っています。StackOverflow と google を検索しましたが、との比較が見つかりませんでした。したがって、この質問。vectorDPHDPHRepaRepaDPHDPHRepaDPHRepaDPH

私はサブセット積を行うコードを書いています: それは要素のリストと (同じ長さの) 標識変数のリストを取ります。積はツリーで計算されます。これは、アプリケーションにとって重要です。各製品は高価であるため、私の目標は、ツリーの各レベルを並行して計算し、連続するレベルを順番に評価することでした。したがって、ネストされた並列処理は行われません。

コード全体のトップレベル近くにある 1 つの関数に repa コードしかありません。subsetProd はモナドではないことに注意してください。

手順:

1. リストをペアにまとめます (並列処理なし)
2. チャンクされたリストを圧縮します (並列処理なし)
3. このリストに製品関数をマップし (Repa マップを使用)、遅延配列を作成します。
4. computeP を呼び出してマップを並行して評価する
5. Repa の結果をリストに戻す
6. 再帰呼び出しを行います (入力の半分のサイズのリストで)

コード：

プログラム全体は、

これらの指示に従って、GHC 7.6.2 x64で。

を使用してプログラム（サブセット）を実行しました

8秒後：

-N パラメータを増やすとコードが遅くなります (-N1 の場合は 7.628 秒、-N2 の場合は 7.891 秒、-N4 の場合は 8.659 秒)。並列性が得られません。また、多数の最適化を行ってコンパイルすると、ランタイムには役立ちますが、並列処理には役立ちません。

Threadscope は、3 つの HEC で重大な作業が行われていないことを確認していますが、ガベージ コレクターは 4 つの HEC をすべて使用しているようです。

では、なぜ Repa は火花を散らさないのでしょうか? 私のプロダクト ツリーには 64 枚の葉があるので、Repa が内部ノードごとにスパークを作成したとしても、最大63 個のスパークが存在するはずです。並列処理をカプセル化する ST モナドの使用と関係があるように感じますが、これが問題を引き起こす理由はよくわかりません。おそらく、火花は IO モナドでのみ作成できますか?

この場合、各レベルが並行して行われるこのツリー製品をどのように実行できるかについてのアイデアはありますか (ネストされた並列処理が発生することなく、これは私のタスクには不要と思われます)。一般に、ツリー プロダクトを並列化するか、Repa をより有効に活用するためのより良い方法があると思われます。

スパークが作成されていない場合でも、-N パラメーターを増やすとランタイムが増加する理由を説明するためのボーナス ポイント。

編集 上記のコード例を、私の問題のコンパイル例に変更しました。プログラム フローは、実際のコードとほぼ完全に一致しています。いくつかの入力をランダムに選択し、それらに対してサブセット積を実行します。私は今アイデンティティモナドを使っています。私は自分のコードに多くの小さな変更を試みました: インライン化するかどうか、bang パターンかどうか、2 つの Repa リストと Repa zipWith を使用するバリエーションと、リストを順番に圧縮して Repa マップを使用する方法など、どれもまったく役に立ちませんでした。

サンプル コードでこの問題に遭遇したとしても、実際のプログラムははるかに大きくなります。