4

N 次元空間の 2 点間のユークリッド距離を計算する必要があり、速度が重要です。N 次元空間の 2 つのポイントを表す 2 つの C スタイルの float 配列があります。

それらの間の距離の式は次のとおりです (^ は XOR ではなく、べき乗を意味します): sqrt(sum((p1-q1)^2 + (p2-q1)^2 + .... (pn-qn) ^2))

私の現在のコードは次のようになります。

sum = 0;
for(int i=0;i<N;++i){
    sum += pow(p[i]-q[i],2);
sqrt(sum)

このコードはかなり遅いので、これを高速化するライブラリがあるかどうか疑問に思っていましたか? 誰かが c で配列に対して数学演算を実行するための簡単なライブラリを作成したと想像します。これにより、配列に対して要素ごとの演算をすばやく実行できます。

編集: nevsan への回答として、約 10 または 20 の小さな N で多くの計算を行っています。

4

2 に答える 2

2

絶対に取り除くpow()。これの最適化の大部分は、使用方法によって異なります。非常に大きな N に対してこれを 1 回実行すると、時間がかかりすぎますか? それとも、タイトなループでこれを何度も行っている可能性が高いですか?

非常に大きな N (>1000 程度) を使用している場合、これを実行できる高度に最適化された数値ライブラリがあります。たとえば、BLAS にはユークリッド ノルム (データ型 [single、double、complex single、complex double] に応じて 、 、、)*nrm2を計算する関数があります。GotoBLASは、特定のプロセッサ アーキテクチャではおそらく最速です。 MKLは Intel の手で調整された BLAS 実装を備えていますが、無料ではありません。最後に、ATLASは BLAS を実装するセルフチューニング ライブラリです。dnrm2snrm2cnrm2znrm2

N が小さいか、それほど大きくないタイトなループがある場合は、高速化するために手動で調整する必要がある場合があります。-O3または-ftree-vectorizeコンパイラ フラグを使用して自動ベクトル化を有効にすることができます。手でベクトル化することもできますが、これを行う方法を学ぶのは大変です。

ループ展開を行うことができます (つまり、N をたとえば 4 のチャンクに分割し、for ループ本体内の 4 つの連続する値の計算を明示的に書き出すことができます。これには、コンパイラーをだまして、即時の計算により多くのレジスターを使用させる効果があります。 ---そして、レジスターは、使用する必要がある最速のメモリー形式です. また、プリフェッチ (1 回のメモリーアクセス呼び出しで一連のデータを読み取る) を利用できる場合もあります。

この状況で行うべきもう 1 つのことは、入力の 1 つを上書きすることです。つまり、出力をporに書き込むことでうまくいくかもしれませんq。pこれは、書き込みの準備ができたときに、計算した の位置がまだキャッシュにあるため、役立ちます。多くの場合、キャッシュは絶対に必要な場合を除き、データをメモリに書き込みません。理由の 1 つは、キャッシュ ラインが必要であり、最後のラインを追い出す必要があるためです。入力の 1 つに書き込むことで、使用するキャッシュ ラインが少なくなります。

他にも 50 万の試してみるものがありますが、ここでやめようと思います。幸運を！

于 2012-08-24T04:21:09.360 に答える
0

私は決して pow() を使用しません - プロファイリングなしで私の推測では、これはあなたを非常に遅くしていると思います.

あなたは臨時雇用者を作り、それを二乗する必要があります。

double diff = p[i] - q[i];
sum += diff*diff;

sqrt は少し遅いですが、ここでの唯一のオプションはいくつかの近似値です。N が約 10 より大きい場合、sqrt はボトルネックにはなりません。

これを高速化する可能性のあるboostなどのライブラリもありますが、最初に pow() を取り除いてみてください。diff*diff は 1 つの浮動小数点命令であり、pow() は非整数累乗などのために設計されたプログラム全体であることに注意してください。

于 2012-08-24T03:58:36.867 に答える