メモリ階層とレイテンシの数値

プロセッサは2つの数をナノ秒の何分の一かで足しますが、キャッシュにない数を取りに行くと80 nsかかることがあります。この講義ではそのレイテンシの数値を、メモリアクセスの平均コストという1つの数にまとめ、どのメモリ階層が時間を食っているかを示します。

トレーディングのプログラムは、価格、注文、表の1行といったデータを待つことに生涯の大半を費やします。そのデータに対する計算はほぼ無料ですが、データはまずメモリからプロセッサまで運ばれなければならず、遠いほど時間がかかります。机、本棚、図書館のフロア、街の反対側の倉庫を思い浮かべてください。机の上の数枚は即座に、本棚は数秒、図書館は1分、倉庫は午後いっぱいかかります。コンピュータはよく使うデータをプロセッサのそばの小さく速いメモリに写し、これをキャッシュと呼びます。こうして大半の要求が机の上で片付きます。

典型的サーバーコアには、メインメモリの手前に3つのキャッシュがあります。これらをL1、L2、L3、メインメモリをRAMと呼びます。キャッシュが答えた要求がヒット、次の階層へ進まなければならない要求がミスです。下のコードは4つのレイテンシを並べたものです。

LATENCY_NS = {"L1": 1.0, "L2": 4.0, "L3": 15.0, "RAM": 80.0}for level, ns in LATENCY_NS.items():    print(level, ns, "ns", ns / LATENCY_NS["L1"], "x L1")

L1 1.0 ns 1.0 x L1
L2 4.0 ns 4.0 x L1
L3 15.0 ns 15.0 x L1
RAM 80.0 ns 80.0 x L1

各階層は1つ上の階層の何倍も遅く、RAMはL1の80倍遅いのです。このスキル全体が、アクセスの大半を上のほうで片付けることを目指しています。

アクセスはL1から始まります。値があればL1のレイテンシだけで終わります。なければプロセッサはL2、L3、そして必ず値を持つRAMの順に尋ねます。尋ねた階層はヒットしてもしなくても時間がかかるので、L3で見つかったアクセスはL1、L2、L3の分を払っています。

1. 1
   L1に尋ねる1 nsかかります。ヒットならアクセスは終わりです。
2. 2
   ミスならL2に尋ねるさらに4 nsかかります。ヒットなら終わりです。
3. 3
   ミスならL3に尋ねるさらに15 nsかかります。ヒットなら終わりです。
4. 4
   ミスならRAMへさらに80 nsかかります。RAMには必ず値があります。

LATENCY_NS = {"L1": 1.0, "L2": 4.0, "L3": 15.0, "RAM": 80.0}cost_found_in_l3 = LATENCY_NS["L1"] + LATENCY_NS["L2"] + LATENCY_NS["L3"]print(cost_found_in_l3, "ns")

20.0 ns

L3が答えたアクセスのコストは15ではなく20 nsです。先の2回のミスに使った1 nsと4 nsも請求に含まれます。

典型的な1回のアクセスというものはないので、多数のアクセスの平均を求めます。各経路のコストを、その起こる頻度で重み付けします。すべてのアクセスがL1のレイテンシを払い、L1でミスした分だけがL2を払い、両方でミスした分だけがL3を払い、以下同様です。階層のように入れ子になる括弧で1つの式に書くと次のとおりです。

これが平均メモリアクセス時間です。括弧は内側から読みます。いちばん内側はL3でミスしたときのコスト、その外側でL3の分が加わり、以下同様に、すべてのアクセスが払うL1の分まで進みます。

LATENCY_NS = {"L1": 1.0, "L2": 4.0, "L3": 15.0, "RAM": 80.0}h1, h2, h3 = 0.9, 0.8, 0.7t = LATENCY_NSamat = t["L1"] + (1 - h1) * (t["L2"] + (1 - h2) * (t["L3"] + (1 - h3) * t["RAM"]))1print(round(amat, 2), "ns")

2.18 ns

1. 11 - h はミスするアクセスの割合なので、各括弧はそこまで到達した割合を掛けています。

アクセスの90%がL1でヒットしても、平均は2.18 nsで、L1のレイテンシの2倍以上です。深くまで行く少数のアクセスが高価なので、平均を押し上げます。だから一見すばらしいヒット率でも、遅いプログラムが隠れていることがあります。

似ている2つの問いには、違う答えがあります。どの階層がアクセスに答えるのか。どの階層が時間を取るのか。前者はアクセスの数を、後者は待ち時間を数えます。各階層にはアクセスの一部が到達し、訪問のたびにそのレイテンシがかかるので、めったに到達しなくても遅い階層が待ち時間を支配することがあります。

h1, h2, h3 = 0.9, 0.8, 0.7served = [h1, (1 - h1) * h2, (1 - h1) * (1 - h2) * h3, (1 - h1) * (1 - h2) * (1 - h3)]reach = [1.0, 1 - h1, (1 - h1) * (1 - h2), (1 - h1) * (1 - h2) * (1 - h3)]1cost = [r * ns for r, ns in zip(reach, [1.0, 4.0, 15.0, 80.0])]2print([round(x, 3) for x in served])print([round(c / sum(cost), 3) for c in cost])

[0.9, 0.08, 0.014, 0.006]
[0.459, 0.183, 0.138, 0.22]

1. 1reach は各階層を訪れるアクセスの割合です。L1には全アクセスが来ます。
2. 2sum(cost) は平均アクセス時間で、先ほどと同じ2.18 nsです。

RAMが答えるのはアクセスのわずか0.6%ですが、待ち時間の22%を占めます。一方L1は90%に答えて、時間の46%です。これがこのスキルのあらゆる最適化の根底にある事実です。アクセスの数ではなく、時間がどこへ行くかを数えましょう。

これは実際の表でどれほど効くのでしょうか。ラボのSPY日足の表は5,405行5列（始値、高値、安値、終値、出来高）で、27,025個の値があります。各値を1回ずつ読むとして、ほぼ全部ヒットする熱いキャッシュ、温かいキャッシュ、各階層でアクセスの半分がミスする冷たいキャッシュの3つの条件で比べます。

ラボではこの講義を6つの小さな関数にします。各関数は前の関数の上に作り、最後に実際のSPYの表を読むコストを見積もります。各関数が答える問いを次に示します。

• 関数 · 問い前提
• average_access_time(hit_rates)1回のアクセスの平均コストは？レイテンシ表
• slowdown(hit_rates)常にL1でヒットする場合の何倍遅いか？average_access_time
• levels_served(hit_rates)どの階層がアクセスに答えるか？局所ヒット率
• time_shares(hit_rates)どの階層が時間を取るか？average_access_time
• scan_time_us(n_accesses, hit_rates)n回のアクセスにかかる時間は？average_access_time
• study(bars)SPYの表全体を読むコストは？scan_time_ustime_shares

次のトピック：この講義ではヒット率を与えられたものとして扱いました。キャッシュラインと空間的局所性では、それを生み出すキャッシュ自体を作り、読んだばかりの値の隣の値を読むのがほぼ無料になる理由を学びます。