この質問は、C++最適化手法に関するものです。私は大きな次元で行列 - ベクトル乗算をしており、ランタイムを減らしたいと考えています。私は、線形代数のための特別なライブラリがあることを知っていますが、実際には基礎となるプロセッサの特質について少しは学びたいと思います。これまでは\ O2(Microsoft)でコンパイルしていましたが、コンパイラは乗算の内部ループがベクトル化されていることを確認しました。行列ベクトル乗算の最適化 - キャッシュサイズ
のコード例は次のとおりです。
#include <stdio.h>
#include <ctime>
#include <iostream>
#define VEC_LENGTH 64
#define ITERATIONS 4000000
void gen_vector_matrix_multiplication(double *vec_result, double *vec_a, double *matrix_B, unsigned int cols_B, unsigned int rows_B)
{
// initialise result vector
for (unsigned int i = 0; i < rows_B; i++)
{
vec_result[i] = 0;
}
// perform multiplication
for (unsigned int j = 0; j < cols_B; j++)
{
const double entry = vec_a[j];
const int col = j*rows_B;
for (unsigned int i = 0; i < rows_B; i++)
{
vec_result[i] += entry * matrix_B[i + col];
}
}
}
int main()
{
double *vec_a = new double[VEC_LENGTH];
double *vec_result = new double[VEC_LENGTH];
double *matrix_B = new double[VEC_LENGTH*VEC_LENGTH];
// start clock
clock_t begin = clock();
// this outer loop is just for test purposes so that the timing becomes meaningful
for (unsigned int i = 0; i < ITERATIONS; i++)
{
gen_vector_matrix_multiplication(vec_result, vec_a, matrix_B, VEC_LENGTH, VEC_LENGTH);
}
// stop clock
double elapsed_time = static_cast<double>(clock() - begin)/CLOCKS_PER_SEC;
std::cout << elapsed_time/(VEC_LENGTH*VEC_LENGTH) << std::endl;
delete[] vec_a;
delete[] vec_result;
delete[] matrix_B;
return 1;
}
乗算が実行時の信頼性の推定値を得るために数回行われます。私はいくつかの異なるベクトル長さのランタイムを測定しました(この例では、ベクトルの長さであるN
という要素が1つしかなく、同時に行列のサイズを定義しますNxN
)要素の数に
あなたは十分に小さいN
ため、操作ごとの実行時間が一定であることがわかります。ただし、N=512
を超えると、ランタイムが上に飛びます。青と赤のデータポイントの違いは、プロセッサの負荷です。サンプルプログラムがほとんど単独で実行されている場合は、ランタイムは青い点で、他のコアがビジーのときは赤い点で表されます。
私は今これに関するいくつかの質問があります。私はN=512
とN=1024
間のジャンプは、6メガバイトである必要があり、私のプロセッサ(アイビーブリッジi5-3570)のL3キャッシュのサイズに関係していると仮定して修正
- アム?
512*512*8byte
は約2MB、1024*1024*8byte
は約8MBです。そのため、マトリックスがキャッシュにもう収まらないため、RAMからデータをフェッチすることが実行時間が長くなる理由です。 - 実行時間がこのしきい値を超えて増加し続けている理由は何ですか?
- ビジー状態とアイドル状態のプロセッサのカーブがしきい値を超えて大きく異なる理由は何ですか?
N>1024
で操作するためにこの乗算ルーチンを最適化する際の論理的な次のステップは何でしょうか?
私はあなたの考えを聞いて興味があります。ありがとう!
@ tobi303複雑さはありますか?これはベクトル行列の乗算であり、行列行列ではありません。 N * N操作だけがあります。 –
ups、申し訳ありませんが、この情報を欠落している必要があります;) – user463035818
オプティマイザはvector_aとmatrix_bをconst double *として宣言することを推奨します。 Cを使用している場合は、「制限」も使用することをお勧めします。これはC++ではありませんが、gccなどのコンパイラの中には拡張の形式を実装しているものもあります。 – dmuir