0

線形代数のツリーステップを何度も繰り返すアルゴリズムがあります。

loop{
  first I multiply a Vector and a Matrix, 
  Second I calculate the sum of elements in the Vector 
  and Thirdly I scale the vector using the sum, making sure the vectors elements scale to one.
}

私はBLASを使用して操作を行っています。これはやや高速ですが、ステップごとに1つずつ、データに対してツリーを実行する必要があります。ここで、ステップを1つにまとめて、データを1回だけ実行することで、何かが得られるのではないかと考えています。

これらの呼び出しを最適な方法で実装する方法について経験がある人はいますか。私の行列は約100*100で、ベクトルは100個の要素を持っています。

ベクトルは8つの128バイトmmxレジスタのようなものに収まると思います。掛け算をかなり速くする、何かアイデアはありますか？

4

1 に答える 1

5

最適化された BLAS ライブラリは非常にトリッキーなコードであり、asm プログラミングの専門家であり、CPU のキャッシュ パフォーマンスを理解しており、さまざまなアプローチのテストに多くの時間を費やす意思がない限り、これを改善することはまずありません。それがどのように行われるかを確認したい場合は、GOTO BLAS のソース コードをダウンロードして参照できます (asm で実装されています)。

コードを大幅に最適化する方法がわかりません。すでに N=100 では、行列ベクトル積の O(N^2) がランタイムを支配し、アルゴリズムの 2 番目と 3 番目のステップはかなり重要ではないと思われます。そのため、3 つの手順をすべて組み合わせようとしても、あまり役に立ちません。

すでに実行していない限り、できる小さなことの1つは、3番目のステップで、合計で割る代わりに合計の逆数を掛けることです。除算は乗算よりもはるかにコストがかかります。例えば


double my_sum = sum(my_vector);
double tmp = 1 / my_sum;
for (i=...) {
   my_vector[i] *= tmp;
}
于 2011-08-22T12:20:49.350 に答える