18

一般的なサイズは 1000 x 1000 ですが、100000 x 100000 を超えることもあります (現在、時間とメモリのために失敗しています)。通常の感情は「逆をとらないで、それを行う別の方法を見つけてください」であることは知っていますが、現時点ではそれは不可能です. この理由は、逆行列を取得することを期待する、既に作成されているソフトウェアの使用によるものです。（注：これを変更する方法を検討していますが、それには時間がかかります）

現在、数値複製からの LU 分解法を使用しており、固有ライブラリのテストを行っています。固有ライブラリはより安定しており、少し高速であるように見えますが、正確さについてはまだテスト段階です。ATLAS や LAPACK などの他のライブラリをざっと見てみましたが、これらについてはまだ実質的なテストを行っていません。

固有ライブラリは逆数を計算するために並行メソッドを使用していないように見えますが (逆数の LU 因数分解部分では使用します)、ATLAS と LAPACK はこの制限において類似していると言えます。(私は現在、openMP を使用する場合と使用しない場合の固有値の速度の違いをテストしています。)

最初の質問は、並列化によって逆行列を最適化する方法を誰でも説明できるかということです。ここで、行列反転並列アルゴリズムについて説明している記事を見つけましたが、理解できませんでした。この記事は別の方法について話しているようですか？また、scaLAPACK または PETSc が役立つかどうかもわかりません。

2 番目の質問です。GPU を使用してパフォーマンスを向上させるというこの記事を読みましたが、GPU 用にコーディングしたことがないので、何が伝えようとしているのかわかりませんが、一番下のグラフはかなり警戒しているように見えました。これはどのように可能であり、それが真実である場合、このようなものを実装するためにどこから始めればよいでしょうか。

この記事も見つけましたが、理解するためにそれを読む時間がありましたが、メモリは私たちのソフトウェアの現在の問題であるため、有望なようです.

これらの記事または一般的な問題に関する情報は、非常に役立ちます。この質問が漠然としているように思われる場合は、もう一度お詫び申し上げます。必要に応じて、さらに拡大しようとします。

4

5 に答える 5

8

最初の質問は、並列化によって逆行列を最適化する方法を誰でも説明できるかということです。

これと線形代数の関連トピックは、並列計算で最も研究されているトピックの 1 つだと思います。読み始める場所を探すのに行き詰まっている場合は、古き良きGolub と Van Loanがそのトピックに関する章を持っています。Scalapack と Petsc が有用であるかどうかについては、確かに前者、おそらく後者です。もちろん、どちらも MPI に依存していますが、この分野ではそれが当然のことと考えられています。

2番目の質問...

GPU があり、GPU がサポートするプログラミング モデルにコードを変換する余裕がある場合は、GPU を使用してください。GPU 向けのコーディングをしたことがなく、コモディティ タイプの CPU のクラスターにアクセスできる場合は、新しいテクノロジと格闘するよりも、クラスターを使用する方が速く理解できます。

あなたが言及した最後の記事に関しては、非常に急速に変化する分野で 10 年前のものです (行列反転に GPU を使用することに関する 10 年前の研究論文を探してみてください)。その卓越性やその他の属性についてコメントすることはできませんが、あなたが言及した問題のサイズは、インコア (古い用語を使用する) 計算のための最新のクラスターの能力の範囲内にあるように思えます. 行列が非常に大きい場合、それらも疎ですか?

最後に、独自のコードを開発しようとするのではなく、既存の既成のコードを使用するというあなたの明確な意図を強く支持します。

于 2012-06-27T15:56:48.140 に答える
5

100000 x 100000 は倍精度で 80GB です。ディスク上のメモリ マップト マトリックスをサポートするライブラリが必要です。特定のライブラリを推奨することはできず、Google のクイック検索では何も見つかりませんでした。しかし、Numerical Recipes のコードは確かに適切ではありません。

于 2012-06-27T15:55:30.187 に答える
5

最初の質問 (逆数の計算を並列化する方法) について:

行列の LU 分解を行い、その分解を使用して A*B = I を解くことで逆行列を計算していると仮定します。ここで、A は元の行列、B は解いた行列、I は単位行列です。このとき B は逆数です。

最後のステップは簡単に並列化できます。単位行列を列に沿って分割します。p 個の CPU があり、行列が n 行 n 列の場合、すべての部分は n/p 列と n 行を持ちます。I1、I2 などのパーツを呼び出しましょう。すべての CPU で、A*B1 = I1 の形式の連立方程式を解きます。これにより、B1、B2 などのパーツが得られ、それらを組み合わせて逆である B の形にすることができます。 .

于 2012-06-28T12:33:14.800 に答える
2

GPU での LU 分解は、CPU での場合よりも最大 10 倍速くなる可能性があります。これは現在変更されていますが、GPU は伝統的に単精度演算を中心に設計されてきたため、古いハードウェアでは単精度演算は一般に倍精度演算よりもはるかに高速です。また、ストレージ要件とパフォーマンスは、マトリックスの構造によって大きく影響されます。スパースな 100,000 x 100,000 マトリックス LU デコンプは、解決するのに妥当な問題であり、多くのメモリを必要としません。

スペシャリストになり、ハードウェアの更新に多くの時間を費やしたくない場合は、商用ライブラリを使用することを強くお勧めします。CULA ツールをお勧めします。疎と密の両方の GPU ライブラリがあり、実際、無料のライブラリは SGETRF (単精度 (密) LU デコンプ ルーチン) を提供します。倍精度ライブラリの料金を支払う必要があります。

于 2012-07-01T05:33:59.210 に答える
1

古い投稿であることは知っていますが、実際には、OpenCL（グラフィックカードに基づいて関連するものをダウンロードします）+ OpenMP +ベクトル化（この順序ではありません）が道です。

とにかく、私にとって行列に関する私の経験は、システム内外で double double 配列をコピーすることによるオーバーヘッドと、特に計算の開始前に行列を 0 でパディングまたは初期化することと関係があります。エクセルの使い方について。

上位の優先順位を付け直すとしたら -

  1. コードをベクトル化してみてください (Visual Studio 2012 と Intel C++ には自動ベクトル化があります。MinGW や GCC についてはわかりませんが、コンパイラが for ループを分析して、代わりに使用する適切なアセンブリ コードを生成するためのフラグがあると思います。データを保持するための通常のレジスタ、プロセッサのベクトル レジスタにデータを設定する. MINVERSE() を実行しているときに Excel のスレッドを監視したときに、スレッドが 1 つしか使用されていないことに気付いたので、Excel がそれを行っていると思います. アセンブリ言語はあまり知りません -だから私は手動でベクトル化する方法を知りません... (まだこれを学ぶ時間がありませんでしたが、すっごくやりたいです!)
  2. OpenMP (omp プラグマ) または MPI または pthreads ライブラリ (parallel_for) で並列化します - 非常に単純です - しかし...ここにキャッチがあります - 最初に行列クラスが完全にシングル スレッド化されている場合は、マット乗算のような操作を並列化します。または逆はスクラップ可能です-並列化すると、並列化されていない行列クラスの初期化またはコピー、またはアクセスするだけで速度が低下します。しかし...並列化が役立つのは、独自のマトリックスクラスを設計していて、そのコンストラクター操作を並列化する場合 (0 でパディングするなど)、LU(A^-1) = I の計算も高速になります。また、LU 分解を最適化することも数学的に簡単であり、ID の特殊なケースの前方後方置換も最適化します。(そうじゃない
  3. （外側のレイヤーで）並列化されると、要素ごとに必要な行列演算は、GPU（SSSSSS）によって計算されるようにマッピングできます-要素を計算するための何百ものプロセッサ-それを打ち負かします！ATI の Web サイトで、ATI の OpenCL を使用したサンプル モンテカルロ コードを利用できるようになりました。GeForce を使用するものへのコードの移植について心配する必要はありません。必要なのは、そこで再コンパイルすることだけです。

ただし、2 と 3 については、オーバーヘッドが発生するため、F* K *G HUGE 行列を処理しない限り意味がないことに注意してください。しかし、100k^2 と表示されますか? おお...

遺伝子

于 2014-01-10T03:25:21.330 に答える