グレートゴッドグーグルは、いくつかのループ最適化の問題についての説明で私に来ていません。それで、私がグーグルフーを十分に持っていないことを悲しんで、私はあなたにStackOverflowに目を向けます。
微分方程式の特定のシステムを解くためにCプログラムを最適化しています。数値解を見つける過程で、線形連立方程式を設定する関数を呼び出し、次にそれを解く関数を呼び出します。
解関数には元々、線形システムを定義する配列の対角線上の要素へのアクセス中にボトルネックがありました。そこで、システムの初期化中に設定され、配列の対角線に沿って値を保持する1次元配列を含めました。
楽しみのために、私は対角要素を初期化するコードで遊んで、それがかかった時間を測定し、コードを継続的に改善しようとしました。私が試したバージョンは、いくつかの質問につながりました。
注：試したすべてのバージョンを1つの関数に入れ、この関数のプロファイルを作成して、時間が費やされている場所を確認しました。バージョンの実行時間を、機能の合計時間のパーセントで報告します。関数は数百万回評価されました。数が少ないほど良いです。
コードで使用されるデータの関連する宣言：
/* quick definitions of the relevant variables, data is a struct */
static const int sp_diag_ind[98] = {2,12,23,76,120,129,137,142,.../* long list */};
double *spJ = &(data->spJ[0]);
/* data has double spJ[908] that represents a sparse matrix stored in triplet
* form, I grab the pointer because I've found it to be more
* efficient than referencing data->spJ[x] each time I need it
*/
int iter,jter;
double *diag_data = NV_DATA_S(data->J_diag);
/* data->J_diag has a content field that has an array double diag_data[150]
* NV_DATA_S is a macro to return the pointer to the relevant data
*/
diag_dataを初期化するための元のループ。タイミングは評価の16.1％でした（注を参照）。
/* try 1 */
for (iter = 0; iter<3; iter++) {
diag_data[iter] = 0;
}
jter = 0;
for (iter = 3; iter<101; iter++) { // unaligned loop start
diag_data[iter] = spJ[sp_diag_ind[jter]];
jter++; // heavy line for loop
}
for (iter = 101; iter<150; iter++) {
diag_data[iter] = 0;
}
要約すると、対角線へのポインターを取得し、いくつかのコンポーネントをゼロに設定し（これは、使用しているアルゴリズムではオプションではありません）、スパース形式で表される「配列」の対角線上にある値を取得します。 spJによる。spJは、（ほとんどがゼロの）150x150配列の908個の非ゼロの1次元配列であるため、ルックアップを使用してspJの対角要素の位置を見つける必要があります。このルックアップは、98要素の配列sp_diag_indによって定義されます。
jterは自由にインクリメントできないように見えたので、使用を削除しようとしました。2回目の試行の真ん中のループ：
for (iter = 0; iter<98; iter++) { // unaligned loop start
diag_data[iter+3] = spJ[sp_diag_ind[iter]];
}
これにより、状況が少し改善されました。このバージョンのタイミングは15.6％でした。しかし、このコード（MacのXCodeに付属するツール）のShark分析を見ると、これは整列されていないループであることが警告されます。
改善するための3番目の試みは、「ゼロ化」ループを削除し、memsetを使用してdiag_dataをゼロ化することでした。
memset(diag_data, '\0', sizeof(diag_data));
for (iter = 0; iter<98; iter++) { // unaligned loop start
diag_data[iter+3] = spJ[sp_diag_ind[iter]];
}
これは14.9％で計時されました。アラインされていないループが何であるかわからないので、私はいじり続けました。diag_dataとspJ[crazyindex]の間のアライメントオフセットをポインターで実行する、改善された4番目の実装を見つけました。
realtype * diag_mask = &diag_data[3];
for (iter = 0; iter<98; iter++) { // unaligned loop start
diag_mask[iter] = spJ[sp_diag_ind[iter]];
}
diag_maskを使用すると、速度がわずかに向上しました。13.1％で入ってきました。
編集：このセクションは、私が当初考えていたよりもばかげていたことがわかりました。iterの使用は定義されていません。それを捕まえるための@cafと@rlibbyへの小道具。
最後に、私は愚かだと思った何かを試しました。
memset(diag_data, '\0', sizeof(diag_data));
for (iter = 0; iter<98;) {
diag_mask[iter] = spJ[sp_diag_ind[iter++]];
}
これは10.9％で計時されました。また、注釈付きのソースコードを見ると、Sharkは整列されていないループの警告を発行しません。 愚かなセクションを終了する
だから、私の質問：
- アラインされていないループとは何ですか？
- 5番目の実装が調整され、4番目の実装が調整されないのはなぜですか？
- 4番目と5番目の実装間の実行速度の向上に責任がある整列ループを持っているのですか、それともsp_diag_indの値のルックアップに増分ステップを埋め込んでいるのですか？
- 他に改善できる点はありますか？
助けてくれてありがとう。
-アンドリュー