NUMA-Effekte

Auf einem Server mit zwei Sockeln kann derselbe Lesezugriff 80 ns oder 130 ns kosten, je nachdem, auf welchem Sockel die Seite liegt. Wo eine Seite liegt, wird bei der ersten Berührung entschieden. Diese Lektion modelliert zwei Knoten, zeigt, wie ein einzelner Thread, der die Daten initialisiert, die Hälfte der Arbeit entfernt macht, und behebt es, indem jeder Thread zuerst seinen eigenen Teil berührt.

Ein großer Server hat zwei Prozessorsockel, und jeder Sockel hat eigene Speichermodule. Ein Kern liest den Speicher seines Sockels direkt. Um den Speicher des anderen Sockels zu lesen, überquert die Anfrage eine Verbindung zwischen den Sockeln, was länger dauert. Eine solche Maschine ist NUMA. Jeder Sockel mit seinem Speicher bildet einen Knoten, und der Knoten eines Threads ist der, auf dem sein Kern sitzt. In unserem Modell gibt es zwei Knoten mit je zwei Threads: Threads 0 und 1 auf Knoten 0, Threads 2 und 3 auf Knoten 1. Ein lokaler Zugriff kostet 80 ns, ein entfernter 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]

Jede Zeile ist die Sicht eines Threads: Er zahlt 80 ns für Seiten auf seinem eigenen Knoten und 130 ns für Seiten auf dem anderen. Der Unterschied von 50 ns wirkt klein, gilt aber für jeden Zugriff, der den Speicher erreicht.

Das Betriebssystem gibt einem Programm Speicher in Seiten und wählt den Knoten einer Seite im Moment ihrer ersten Nutzung. Die Standardregel ist First Touch: Die Seite kommt auf den Knoten des Threads, der sie zuerst berührt, und bleibt dort. Eine Alternative ist, die Seiten über die Knoten zu verschränken. Der Code unten wendet beide Regeln auf eine kurze Liste von Zugriffen an, geschrieben als (Thread, Adresse).

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}

Die Seiten 0 und 1 wurden zuerst von Thread 0 berührt, der auf Knoten 0 sitzt, sie kommen also auf Knoten 0. Seite 2 wurde zuerst von Thread 3 auf Knoten 1 berührt, sie kommt also auf Knoten 1. Der spätere Zugriff von Thread 1 auf Seite 1 verschiebt sie nicht. Das Verschränken ignoriert, wer was berührt: Seite 1 kommt auf Knoten 1, einfach weil 1 modulo 2 gleich 1 ist.

Ein typischer paralleler Job teilt eine Tabelle in Blöcke, einen für jeden Thread. Jeder Thread liest dann nur seinen Block, idealerweise liegt also jede Seite, die er liest, auf seinem eigenen Knoten. Die Funktionen unten bauen dieses Zugriffsmuster für 400 Datensätze auf vier Threads und zählen die lokalen und entfernten Zugriffe und ihre Zeit für drei Platzierungen. In der ersten, „single“, hat ein einziger Thread alle Daten initialisiert, sodass First Touch jede Seite auf Knoten 0 gelegt hat. In der zweiten haben die Besitzer ihre eigenen Blöcke initialisiert. In der dritten sind die Seiten verschränkt.

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}

Wenn ein einziger Thread alles initialisiert, ist die Hälfte der Zugriffe entfernt, und der Job braucht 42.000 ns für 400 Lesezugriffe. Initialisieren die Besitzer ihre Blöcke, ist nichts entfernt, und es dauert 32.000 ns, etwa 1,3-mal schneller bei exakt demselben Programm. Das Verschränken hilft hier nicht: Da jeder Thread einen zusammenhängenden Block liest, legen die verschränkten Seiten die Hälfte seiner Daten auf den falschen Knoten. Verschränken ist für Daten, die jeder Thread überall liest, wo keine Platzierung für alle gut sein kann.

Das Labor folgt der Lektion: der Knoten eines Threads, die zwei Platzierungsregeln, das Zugriffsmuster eines partitionierten Jobs, die Zählung lokaler und entfernter Zugriffe und die Studie an den SPY-Datensätzen.

• Funktion · FrageBaut auf
• node_of_thread(thread, threads_per_node)Auf welchem Knoten läuft ein Thread?Die ganzzahlige Division
• first_touch_placement(trace, threads_per_node)Wohin legt First Touch jede Seite?node_of_thread
• interleaved_placement(trace, n_nodes)Und das Verschränken?Einfache Arithmetik
• partition_trace(n_records, n_threads, record_bytes)Welche Zugriffe macht jeder Thread?Einfache Arithmetik
• access_costs(trace, placement, threads_per_node)Wie viele lokale und entfernte Zugriffe, und wie lange?node_of_thread
• study(bars)Was kostet eine falsche Platzierung bei den SPY-Datensätzen?partition_tracefirst_touch_placementaccess_costs

Nächstes Thema: Wo die Bytes liegen, ist nur die halbe Geschichte; auch wie sie vergeben werden, zählt. In Allokatoren und Speicher-Pools fordert ein Programm viele kleine Objekte an, und die Reihenfolge und die Orte, an denen der Allokator sie vergibt, bestimmen, wie viele Cache-Zeilen ein späterer Durchlauf berührt.