3

これらの最適化のうちどれがより優れており、どのような状況で使用されますか? なんで？

直感的に、ループ タイリングは一般的に最適化に適していると感じています。

以下の例ではどうですか？常に約 20 個の要素しか格納できないキャッシュを想定します。

Original Loop:
for(int i = 0; i < 10; i++)
{
    for(int j = 0; j < 1000; j++)
    {
        a[i] += a[i]*b[j];
    }
}

Loop Interchange:
for(int i = 0; i < 1000; i++)
{
    for(int j = 0; j < 10; j++)
    {
        a[j] += a[j]*b[i];
    }
}

Loop Tiling:
for(int k = 0; k < 1000; k += 20)
{
    for(int i = 0; i < 10; i++)
    {
        for(int j = k; j < min(1000, k+20); j++)
        {
            a[i] += a[i]*b[j];
        }
    }
}
4

1 に答える 1

2

質問で公開している最初の 2 つのケースはほぼ同じです。次の 2 つのケースでは、状況が大きく変わります。

ケース 1:

for(int i = 0; i < 10; i++)
{
    for(int j = 0; j < 1000; j++)
    {
        b[i] += a[i]*a[j];
    }
}

ここでは、次のように行列 "a" にアクセスしています: a[0]*a[0]、a[0]*a 1、a[0]*a[2]、.... ほとんどのアーキテクチャでは、行列構造a[0]*a[0]、a 1 *a[0]、a[2]*a[0] (最初の行の最初の列に続いて最初の raw の 2 番目の列、... .)。キャッシュに 5 つの要素しか格納できず、マトリックスが 6x6 であるとします。キャッシュに格納される要素の最初の「パック」は、a[0]*a[0] から a[4]*a[0] になります。最初のアクセスではキャッシュ ミスが発生しないため、[0][0] がキャッシュに格納されますが、2 回目ははい!! 0はキャッシュに保存されません。次に、OS は要素のパック a 0から a 4をキャッシュします。次に、3 番目のアクセスを実行します: a[0]*a[2] これは再びキャッシュから外れています。またキャッシュミス！

結託できるように、ケース 1 は問題の適切な解決策ではありません。これにより、次のコードの変更を回避できる多くのキャッシュ ミスが発生します。

ケース 2:

for(int i = 0; i < 10; i++)
    {
        for(int j = 0; j < 1000; j++)
        {
            b[i] += a[i]*a[j];
        }
    }

ここでは、ご覧のとおり、メモリに格納されている行列にアクセスしています。したがって、ケース 1 よりもはるかに優れています (高速です)。

ループ タイリング、ループ タイリング、およびループ展開について投稿した 3 番目のコードについては、ほとんどの場合、コンパイラが自動的に行う最適化です。 これは、これら 2 つの手法を説明するスタックオーバーフローの非常に興味深い投稿です。

それが役に立てば幸い！（私の英語について申し訳ありません、私はネイティブスピーカーではありません）

于 2013-09-26T20:29:28.180 に答える