走査順序とループタイリング

行列の同じセルを訪れる2つの入れ子ループでも、どちらのループを内側にするかだけで、キャッシュミスが7倍も違うことがあります。この講義では行ごと・列ごとの読み出しを比べ、次に転置をタイルに分けて、ブロックを使っている間キャッシュに残るようにし、SPYの終値から作った行列で両方を測ります。

n行n列の行列は行優先の順序で保存されます。j を変えながら行に沿って進むループは、隣り合う値を読みます。i を変えながら列を下るループは、1歩ごとに1行ぶん飛びます。次の2つのループは同じセルを訪れ、一方は j を内側、もう一方は i を内側にしています。float64の4×4行列の最初の6つのアドレスを表示します。

def row_major_trace(n):    return [(i * n + j) * 8 for i in range(n) for j in range(n)]def col_major_trace(n):    return [(i * n + j) * 8 for j in range(n) for i in range(n)]1print("row:", row_major_trace(4)[:6])print("col:", col_major_trace(4)[:6])

row: [0, 8, 16, 24, 32, 40]
col: [0, 32, 64, 96, 8, 40]

1. 1iを内側にすると、次の読み出しは1行ぶん（ここでは4値＝32バイト）先になります。

行ごとだとアドレスは8バイトずつ増え（最初のトピックのストライド）、1ラインで8回の読み出しをまかなえます。列ごとだとここでは32バイト、もっと大きな行列では1行の長さずつ飛びます。小さな4 KBのキャッシュで、16×16から73×73までの行列について、2つの順序のミスを数えましょう。

for n in (16, 32, 48, 73):    print(n, "x", n, "row:", count_misses(row_major_trace(n)), "col:", count_misses(col_major_trace(n)))

16 x 16 row: 32 col: 32
32 x 32 row: 128 col: 1024
48 x 48 row: 288 col: 2304
73 x 73 row: 667 col: 4573

16×16の行列は2 KBでキャッシュに収まるので、読み込んだ後はどちらの順序も32ミスで同じです。32×32からは行列が収まらなくなり、列の順序は毎回ミスします。128回に対して1,024回、8倍で、これは1ラインの8個の値に当たります。73×73では約7倍です。ループの形は変わらず、変わったのはデータの大きさです。

どのループ順でも解決しないことがあります。転置 B[j][i] = A[i][j] はAを読みBに書くので、ループがAの行に沿えばBの列を下ることになります。どちらを内側にしても、2つの行列の一方は大きなストライドで走査されます。対策はループタイリングです。行列を小さな正方形のタイルで処理し、タイルが触れる少数のラインが、追い出される前に何度も使われるようにします。

1. 1
   タイルの大きさtを決めるAのタイルとBのタイルがキャッシュに収まる小ささにします。
2. 2
   タイルを順に回る刻みtの外側の2つのループ ii と jj が、タイルの角を与えます。
3. 3
   タイルの中で処理する内側の2つのループは、これまでどおりこのタイルのt×tセルだけを訪れます。
4. 4
   次のタイルへ古いタイルのラインを手放すのは、ここで初めてです。

次のコードは、4×4行列でセルが訪れられる順序を、タイルなしとタイル2ありで並べるだけです。タイルありでは、左上の2×2ブロックを終えてから他のセルに触れます。

def visit_order(n, tile=None):    step = n if tile is None else tile    order = []    for ii in range(0, n, step):1        for jj in range(0, n, step):            for i in range(ii, min(ii + step, n)):                for j in range(jj, min(jj + step, n)):                    order.append((i, j))    return orderprint("plain:", visit_order(4)[:8])print("tile 2:", visit_order(4, 2)[:8])

plain: [(0, 0), (0, 1), (0, 2), (0, 3), (1, 0), (1, 1), (1, 2), (1, 3)]
tile 2: [(0, 0), (0, 1), (1, 0), (1, 1), (0, 2), (0, 3), (1, 2), (1, 3)]

1. 1外側の2つのループがタイルを巡り、内側の2つのループが1つのタイルの中を巡ります。

では実際の転置です。Aの読み出しとBへの書き込みのトレース（BはAの直後に置く）を作り、73×73の行列について、タイルなしとタイル4、8、16、32のミスを数えます。

def transpose_trace(n, tile=None):    base_b = n * n * 8    step = n if tile is None else tile    trace = []    for ii in range(0, n, step):        for jj in range(0, n, step):            for i in range(ii, min(ii + step, n)):                for j in range(jj, min(jj + step, n)):                    trace.append((i * n + j) * 8)                    trace.append(base_b + (j * n + i) * 8)    return tracefor tile in (None, 4, 8, 16, 32):    print("tile", tile, "misses:", count_misses(transpose_trace(73, tile)))

tile None misses: 5996
tile 4 misses: 2603
tile 8 misses: 2036
tile 16 misses: 1960
tile 32 misses: 1714

タイルなしの転置は5,996回ミスします。タイル4ですでに2,603回に減り、タイル8〜32では2,036〜1,714回で、約3分の1です。小さすぎるタイルは、読み込むラインの端を無駄にするので、タイルが収まらなくなるまでは大きいほど効きます。

ラボは講義の順に進みます。2つの読み出し順、任意のタイル付き転置トレース、順序とタイルごとのミス数、最良のタイルの選択、そしてSPYの行列での研究です。

• 関数 · 問い前提
• row_major_trace(n)行ごとの読み出しはどのアドレスに触れるか？単純な算術
• col_major_trace(n)列ごとの読み出しは？単純な算術
• transpose_trace(n, tile=None)タイルあり・なしの転置はどのアドレスに触れるか？4重のループ
• compare_orders(n)列の順序はどれだけ悪いか？row_major_tracecol_major_trace
• misses_by_tile(n, tiles)タイルは転置のミスをどう変えるか？transpose_trace
• best_tile(n, tiles)どのタイルが最良か？misses_by_tile
• study(bars)SPYの終値の行列でタイリングはどれだけ得か？compare_ordersbest_tile

次のトピック：タイリングはラインの再利用でミスの遅れを隠し、プリフェッチは必要になる前にラインを要求して隠します。プリフェッチでは、キャッシュにストライド検出器を加え、どのアクセスパターンを予測でき、表の中のランダムウォークのようにどれを予測できないかを見ます。