NUMAの影響

2ソケットのサーバーでは、同じ読み出しでも、ページがどちらのソケットにあるかで80 nsにも130 nsにもなります。ページがどこにあるかは、最初に触れられたときに決まります。この講義では2つのノードをモデル化し、1つのスレッドがデータを初期化すると仕事の半分がリモートになる様子を示し、各スレッドが自分の担当部分に先に触れることで直します。

大きなサーバーにはプロセッサのソケットが2つあり、各ソケットに専用のメモリモジュールがつながっています。コアは自分のソケットのメモリを直接読みます。もう一方のソケットのメモリを読むには、要求がソケット間のリンクを通るので時間がかかります。このようなマシンはNUMAです。各ソケットとそのメモリが1つのノードを作り、スレッドのノードはそのコアがあるノードです。このモデルでは、2つのノードにそれぞれ2スレッドがあり、スレッド0と1がノード0、スレッド2と3がノード1です。ローカルアクセスは80 ns、リモートアクセスは130 nsです。

print([node_of_thread(thread, 2) for thread in range(4)])for thread_node in (0, 1):    print("thread on node", thread_node, [LOCAL_NS if page_node == thread_node else REMOTE_NS for page_node in (0, 1)])

[0, 0, 1, 1]
thread on node 0 [80.0, 130.0]
thread on node 1 [130.0, 80.0]

各行は1つのスレッドから見た値です。自分のノードのページには80 ns、もう一方のノードのページには130 nsを払います。差の50 nsは小さく見えますが、メモリに届くすべてのアクセスにかかります。

OSはプログラムにメモリをページ単位で与え、ページが最初に使われた瞬間にそのノードを選びます。既定の規則はファーストタッチで、最初に触れたスレッドのノードにページが置かれ、そこに留まります。別の方法は、ページをノードにインターリーブすることです。次のコードは、(スレッド, アドレス) の短いアクセス列に両方の規則を適用します。

def first_touch_placement(trace, threads_per_node):    placement = {}    for thread, address in trace:        page = address // PAGE_BYTES        if page not in placement:            placement[page] = node_of_thread(thread, threads_per_node)    return placementdef interleaved_placement(trace, n_nodes):    return {page: page % n_nodes for page in {address // PAGE_BYTES for _, address in trace}}trace = [(0, 0), (0, 4096), (3, 8192), (1, 4100)]print(first_touch_placement(trace, 2))print(interleaved_placement(trace, 2))

{0: 0, 1: 0, 2: 1}
{0: 0, 1: 1, 2: 0}

ページ0と1は、ノード0にあるスレッド0が最初に触れたのでノード0に置かれます。ページ2はノード1のスレッド3が最初に触れたのでノード1に置かれます。その後のスレッド1によるページ1へのアクセスは、ページを動かしません。インターリーブは誰が何に触れるかを無視します。ページ1は、1を2で割った余りが1だというだけでノード1に置かれます。

典型的並列ジョブは、表をスレッドごとのチャンクに分けます。各スレッドは自分のチャンクだけを読むので、理想的には、読むページがすべて自分のノードにあります。次の関数は、400レコードを4スレッドで読むこのアクセスパターンを作り、3つの配置について、ローカルとリモートのアクセス数と時間を数えます。1つ目の「single」では、1つのスレッドがデータをすべて初期化したので、ファーストタッチですべてのページがノード0に置かれました。2つ目では、担当者が自分のチャンクを初期化しました。3つ目では、ページがインターリーブされています。

def access_costs(trace, placement, threads_per_node):    local = 0    remote = 0    for thread, address in trace:        if placement[address // PAGE_BYTES] == node_of_thread(thread, threads_per_node):            local += 1        else:            remote += 1    return {"local": local, "remote": remote, "ns": local * LOCAL_NS + remote * REMOTE_NS}def partition_trace(n_records, n_threads, record_bytes):    chunk = n_records // n_threads    return [(thread, record * record_bytes) for thread in range(n_threads) for record in range(thread * chunk, (thread + 1) * chunk)]work = partition_trace(400, 4, 512)single = first_touch_placement([(0, address) for _, address in work], 2)owners = first_touch_placement(work, 2)spread = interleaved_placement(work, 2)for name, placement in (("single", single), ("owners", owners), ("interleaved", spread)):    print(name, access_costs(work, placement, 2))

single {'local': 200, 'remote': 200, 'ns': 42000.0}
owners {'local': 400, 'remote': 0, 'ns': 32000.0}
interleaved {'local': 208, 'remote': 192, 'ns': 41600.0}

1つのスレッドがすべてを初期化すると、アクセスの半分がリモートになり、400回の読み出しに42,000 nsかかります。担当者が自分のチャンクを初期化すると、リモートはなくなり32,000 nsで、まったく同じプログラムが約1.3倍速くなります。ここではインターリーブは役に立ちません。各スレッドは連続したチャンクを読むので、インターリーブしたページはそのデータの半分を誤ったノードに置いてしまいます。インターリーブは、どのスレッドも全体を読むデータのためのもので、全員に良い配置が存在しない場合に使います。

ラボは講義の順に進みます。スレッドのノード、2つの配置規則、分割したジョブのアクセスパターン、ローカルとリモートのアクセスの集計、そしてSPYのレコードでの研究です。

• 関数 · 問い前提
• node_of_thread(thread, threads_per_node)スレッドはどのノードで動くか？整数除算
• first_touch_placement(trace, threads_per_node)ファーストタッチは各ページをどこに置くか？node_of_thread
• interleaved_placement(trace, n_nodes)インターリーブは？単純な算術
• partition_trace(n_records, n_threads, record_bytes)各スレッドはどんなアクセスをするか？単純な算術
• access_costs(trace, placement, threads_per_node)ローカルとリモートのアクセスは何回で、時間は？node_of_thread
• study(bars)SPYのレコードで誤った配置はどれだけ高くつくか？partition_tracefirst_touch_placementaccess_costs

次のトピック：バイトがどこにあるかは話の半分にすぎず、どう割り当てられるかも重要です。アロケータとメモリプールでは、プログラムが多数の小さなオブジェクトを要求し、アロケータがそれらを渡す順序と場所が、後の走査が触れるキャッシュラインの数を決めます。