現在、赤/青の計算を解くプログラムに取り組んでいます。プログラムはCで書かれています。
問題の説明はこちら: http://www.cs.utah.edu/~mhall/cs4961f10/CS4961-L9.pdf
tl;dr色のグリッド（赤/青/白）があり、最初に赤いセルが特定のルールに従って右に移動し、次に青いセルが他のルールに従って下に移動します。
プログラムが動作し、正しい出力が得られました。現在、プログラムをまったく高速化できないかどうかを確認しようとしています。
Intel の VTune Amplifier を使用して (これは並列プログラミング コース用であり、並列スタジオが統合された Visual Studio で pthread を実行しています)、私のコードで最大のホットスポットは青いセルを移動するときであることがわかりました。
実装の詳細: グリッドは動的に割り当てられた int ** として格納され、このように設定されます
globalBoard = malloc(sizeof(int *) * size);
for (i = 0; i < size; i++)
{
globalBoard[i] = malloc(sizeof(int) * size);
for (j = 0; j < size; j++)
globalBoard[i][j] = rand() % 3;
}
いくつかの調査の結果、ホットスポット (赤セルの移動のほぼ 4 倍の CPU 時間) の原因は、列ごとにトラバースするときのキャッシュ ミスであると考えています。
内部では、このグリッドは 1 次元配列として格納されることを理解しているため、赤いセルを右に移動して行ごとに移動する場合、ほとんどの場合、連続した値をチェックしているため、CPU をロードする必要はありません。新しい値は頻繁にキャッシュに入れられますが、列ごとに移動すると、ボードのサイズに応じて増加する量だけ配列を飛び回ることになります。
そうは言っても、この特定のセクションをより速く進めたいと思います。現在のコードは次のとおりです。
void blueStep(int col)
{
int i;
int local[size];
for (i = 0; i < size; local[i] = globalBoard[i++][col]);
for (i = 0; i < size; i++)
{
if (i < size - 1)
{
if (globalBoard[i][col] == 2 && globalBoard[i + 1][col] == 0)
{
local[i++] = 0;
local[i] = 2;
}
}
else
{
if (globalBoard[i][col] == 2 && globalBoard[0][col] == 0)
{
local[i++] = 0;
local[0] = 2;
}
}
}
for (i = 0; i < size; i++)
globalBoard[i][col] = local[i];
}
ここで、col は作業する列であり、size はグリッドの大きさです (常に正方形です)。
私はこれを高速化するためにある種の派手なポインタ演算を行うことができるかもしれないと考えていました. html .
それを見ると、2次元配列ポインター演算を利用するためにグリッドの宣言方法を変更する必要があるように感じますが、その方法を使用して列をトラバースする方法はまだわかりません。
それについての助け、またはコラムを通過するための他の迅速な方法の提案は大歓迎です.
更新: もう少し調査と議論を重ねた結果、私の仮定は間違っていたようです。実際には、結果をグローバル配列に書き戻すのに、列をループするよりもほぼ 2 倍の時間がかかっていることがわかりました。これは、偽の共有が原因です。そうは言っても、列トラバーサルを行うためのより良い方法があるかどうか、まだ少し興味があります。