TLBとヒュージページ

読み出しがキャッシュに届く前に物理アドレスが必要で、その変換には専用の小さなキャッシュ、TLBがあり、エントリは約64個しかありません。それより多くのページの間を飛び回るプログラムは、データキャッシュが好調でも、ほぼ毎回TLBミスを起こしえます。この講義ではTLBを作り、2 MBのページが250ページを1ページにまとめる様子を示します。

プログラムが使うアドレスは仮想アドレスです。各プログラムは、ゼロから始まる長いメモリを自分だけが持っていると思っています。マシンは実際のメモリを物理アドレスで持ち、両方の世界をページに区切ります。メモリ上の表であるページテーブルが、各仮想ページをどの物理ページが持つかを示します。すべての読み出しは、まずこの変換が必要です。仮想アドレスのページ番号を取り、それを引き、ページ内のバイト位置を保ちます。キャッシュのラインと同じ分割で、ブロックが大きいだけです。

page_bytes = 4096for address in (0, 4095, 4096, 123456789):    print(address, "-> page", address // page_bytes, "byte", address % page_bytes)1

0 -> page 0 byte 0
4095 -> page 0 byte 4095
4096 -> page 1 byte 0
123456789 -> page 30140 byte 3349

1. 1ページ番号はアドレスをページサイズで割った値で、余りがページ内のバイト位置です。

読み出しのたびにメモリ上のページテーブルをたどると、メモリアクセスのコストが2倍になってしまいます。そのためプロセッサは、直近の変換結果をTLBという小さく速い表に保持します。ページがTLBにある読み出しはヒットで、ほぼコストがかかりません。ない読み出しはTLBミスで、数十ナノ秒かかるページテーブルの巡回が起きます。第1レベルのデータTLBは約64エントリを持ちます。ラインではなくページを保持する点を除けば、これまでのキャッシュと同じ動きで、最も長く使われていないものから出ていきます。

class TLB:    def __init__(self, entries):        self.entries = entries        self.pages = []        self.hits = 0        self.misses = 0    def access(self, address, page_bytes):        page = address // page_bytes        if page in self.pages:            self.pages.remove(page)            self.pages.append(page)            self.hits += 1            return True        self.misses += 1        self.pages.append(page)        if len(self.pages) > self.entries:            self.pages.pop(0)        return Falsedef tlb_misses(trace, entries, page_bytes):    tlb = TLB(entries)    for address in trace:        tlb.access(address, page_bytes)    return tlb.missesfor n_pages in (48, 64, 65, 80):    trace = [page * 4096 for page in range(n_pages)] * 5    print(n_pages, "pages, 5 rounds:", tlb_misses(trace, 64, 4096), "misses")

48 pages, 5 rounds: 48 misses
64 pages, 5 rounds: 64 misses
65 pages, 5 rounds: 325 misses
80 pages, 5 rounds: 400 misses

48ページや64ページのループは、最初の周回でしかミスしません。1ページ増えて65ページになると、5周のすべての読み出しでTLBミスが起き、325回中325回です。これは、ワーキングセットのトピックと同じLRUの崖が、今度はページで起きたものです。大事なのは到達範囲、つまりTLBが一度に覆えるメモリの量です。

1レコード512バイトのレコード2,000件の表を考えます。1日分のデータに追加フィールドがついたものです。全体で1,000 KB、4 KBのページで250ページで、TLBが保持できる64ページの4倍近くです。レコードを順に読むのは穏やかで、1ページを8レコードで共有するので、TLBミスはページごとに1回、250回です。ランダムな順に読むのは厳しく、各読み出しが250ページのどこにでも当たりえて、TLBは64ページしか覚えていません。次のコードは、4 KBページと2 MBページの両方で測ります。

import randomorder = list(range(2000))shuffled = random.Random(7).sample(order, len(order))for name, records in (("in order", order), ("shuffled", shuffled)):    trace = [record * 512 for record in records]    print(name, "4 KB pages:", tlb_misses(trace, 64, 4096), "- 2 MB pages:", tlb_misses(trace, 64, 2 * 1024 * 1024))

in order 4 KB pages: 250 - 2 MB pages: 1
shuffled 4 KB pages: 1541 - 2 MB pages: 1

順に読むと、4 KBページでは250ミスです。シャッフルすると2,000回の読み出しのうち1,541回、77%がミスし、6倍になります。2 MBページなら1,000 KBがすべて1ページに収まり、順序に関わらず1回のミスです。巡回1回30 nsとして、シャッフルした読み出しは変換だけで46マイクロ秒を使い、これは10万回の足し算に相当します。

ラボは講義の順に進みます。アドレスのページ、LRU置換のTLB、ミスの数え上げ、トレースが触れるページ、ある順序でのレコードのアドレス、ページサイズの比較、そしてSPYのレコードでの研究です。

• 関数 · 問い前提
• page_of(address, page_bytes)このアドレスはどのページにあるか？整数除算
• TLB(entries).access(address, page_bytes)この変換はTLBヒットか？page_of
• tlb_misses(trace, entries, page_bytes)トレースは何回TLBミスを起こすか？TLB
• pages_touched(trace, page_bytes)トレースは何種類のページに触れるか？page_of
• record_trace(order, record_bytes)この順でレコードを読むとどのアドレスに触れるか？単純な算術
• compare_pages(trace, entries)ヒュージページはどれだけ効くか？tlb_misses
• study(bars)SPYのレコードでヒュージページは何を節約するか？compare_pagespages_touchedrecord_trace

次のトピック：ここまでは1つのプログラムと1つのコアでした。フォルスシェアリングとパディングでは、同じキャッシュラインにある2つの別々の変数に2つのコアが書き込み、ラインが両者の間を行き来します。無効化の回数を数え、パディングで直します。