0

倍精度の大きな値の行列を乗算できる効率的なアルゴリズムを作成しようとしています。アルゴリズムを作成し、最初に小さな行列でテストしました。つまり、A{4096x4096}、B{4096x4096} を試した後、ループは永遠に終了します。たとえば、これらの 2 つの行列で AB を生成するには、コンピューターが完了するまでに 30 分以上かかりました。

私のコンピューターは古い前かがみではありません... 6 コアの i7 であり、デスクトップ ワークステーションとしてはそれほど悪くはないと思います。1024x1024 までのサイズの小さな行列では、比較的短時間で完了します。つまり、30 ～ 40 秒未満で、2048x2048 の場合は約 5 分です... 16384x16384 の場合は 15 分で終了せず、実行を停止しました...

私は何か間違ったことをしていますか、それともこれは予想されることですか? :)

前もって感謝します！

コードは次のとおりです。

/* calculate */
for(travx = 0; travx < m; travx++) {
    for(travy = 0; travy < n; travy++) {
        /* we only need to calculate it ourside of Z loop */
        tIndex = (travy)+(travx*n); 
        for(travz = 0; travz < p; travz++)
            {
                if(n==1)
                    {bIndex = ((n-1)*travy)+travz;
                     aIndex = ((p)*travx)+travz;} 
                else
                    {bIndex = ((n)*travz)+travy;
                     aIndex = ((p)*travx)+travz;}

                temp = atab_ptr[aIndex]*btab_ptr[bIndex];
                outtab_ptr[tIndex] =  outtab_ptr[tIndex] + temp;
            }
    }
}

それは本当に簡単です...そして小さな行列で素晴らしい結果をもたらします...特にp4で10秒未満でdoubleを乗算する方法がわかりません...ちょっと怪しげに聞こえます...特にO(3)を考慮に入れる場合問題の複雑さ。

更新...フィードバックに基づいてコードを微調整しました...まあ、主にそれを単純化し、小さな行列をはるかに高速に完了しました。つまり、1024x1024 は 3 秒以内に完了しますが、4096x4096 は 6 分で完了します。 . 改訂されたコードは次のとおりです。

for(travx = 0; travx < m; travx++) {
    for(travy = 0; travy < n; travy++) {
      for(travz = 0; travz < p; travz++)
        {outtab_ptr[travy+travx*n] = outtab_ptr[travy+travx*n] + atab_ptr[travy+p*travz] *  btab_ptr[travz+travx*p];}
    }
  }
4

3 に答える 3

4

可能であれば、BLASが最善の方法です。

とはいえ、基本的に、行列の乗算は複雑さによって制限されるため、時間を大幅に短縮するには、よりインテリジェントである必要があります。行列は何らかの形で構造化されていますか？それらは三重対角ですか、それとも縞模様ですか？それらは三角形ですか、それとも対称ですか？

于 2012-05-24T11:55:42.930 に答える
1

あなたの「効率的な」アルゴリズムは、実際には非常に非効率的です。nが 1 でない場合に何が起こるかを確認します。

bIndex = ((n)*travz)+travy;
aIndex = ((p)*travx)+travz;
temp = atab_ptr[aIndex]*btab_ptr[bIndex];

最も内側のループは終わったtravzのでaIndex、 の各インクリメントでステップ 1 で増加しますtravz。一方bIndex、 のステップで増加しnます。btab_ptrしたがって、メモリ内で隣接していないため、同じキャッシュラインにない要素にアクセスしています。

最も内側のループの条件が可能なベクトル化にどのような影響を与えるかは言うまでもありません。

したがって、すべての行列のデータが Core i7 の L3 キャッシュに収まる場合、アルゴリズムは許容できるほど高速に動作しますが、そうでなくなるとすぐに、パフォーマンスが大幅に低下します。次に、これに O(N^3) の複雑さがさらに乗算されます。

于 2012-05-24T12:04:52.253 に答える
0

さて、行列乗算への単純なアプローチは O(n^3) です。つまり、2 つの行列を乗算するのにかかる時間は、入力のサイズに応じて 3 次的に増加します。より効率的なアプローチがあります。ここで見ることができます：

http://en.wikipedia.org/wiki/Computational_complexity_of_mathematical_operations#Matrix_algebra

それでも、これらのアプローチはいずれも O(n^2) 未満ではありません。したがって、行列のサイズを大きくすると、完了までの時間が超直線的に長くなるのが普通です。

そうは言っても、観察している時間が長すぎるかどうかは、多くの要因 (マシン、コードなど) に依存します。

ところで、非常によく似た質問がされているこのスレッドを見ることができます。また、教育目的でない限り、ATLAS などの最適化されたライブラリを使用することをお勧めします。

ここには、メモリ使用量を改善するためにアプリケーションを最適化する方法に関する古典的なドキュメントもあります。そのドキュメントでは、作成者は、行列乗算のパフォーマンスを最適化するために、整列やプリフェッチなどのいくつかの手法を使用しています。

于 2012-05-24T10:34:30.380 に答える