Effets NUMA

Sur un serveur à deux sockets, la même lecture peut coûter 80 ns ou 130 ns, selon le socket où la page se trouve. L'endroit où vit une page est décidé à sa première utilisation. Ce cours modélise deux nœuds, montre comment un seul thread qui initialise les données rend la moitié du travail distante, et corrige cela en laissant chaque thread toucher d'abord sa propre part.

Un gros serveur a deux sockets de processeur, et chaque socket a ses propres barrettes de mémoire. Un cœur lit directement la mémoire de son socket. Pour lire celle de l'autre socket, la requête traverse un lien entre les sockets, ce qui prend plus de temps. Une telle machine est NUMA. Chaque socket et sa mémoire forment un nœud, et le nœud d'un thread est celui où se trouve son cœur. Dans notre modèle, il y a deux nœuds de deux threads chacun : les threads 0 et 1 sur le nœud 0, les threads 2 et 3 sur le nœud 1. Un accès local coûte 80 ns et un accès distant 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]

Chaque ligne est la vue d'un thread : il paie 80 ns pour les pages de son propre nœud et 130 ns pour celles de l'autre. La différence, 50 ns, paraît petite, mais elle s'applique à chaque accès qui atteint la mémoire.

Le système d'exploitation donne de la mémoire à un programme par pages, et il choisit le nœud d'une page au moment où elle est utilisée pour la première fois. La règle par défaut est la première touche : la page va sur le nœud du thread qui la touche en premier, et elle y reste. Une alternative est d'entrelacer les pages sur les nœuds. Le code ci-dessous applique les deux règles à une courte liste d'accès écrits (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}

Les pages 0 et 1 ont été touchées d'abord par le thread 0, qui est sur le nœud 0 : elles vont donc sur le nœud 0. La page 2 a été touchée d'abord par le thread 3, sur le nœud 1 : elle va sur le nœud 1. L'accès ultérieur du thread 1 à la page 1 ne la déplace pas. L'entrelacement ignore qui touche quoi : la page 1 va sur le nœud 1 simplement parce que 1 modulo 2 vaut 1.

Un travail parallèle typique découpe une table en morceaux, un par thread. Chaque thread ne lit ensuite que son morceau : idéalement, chaque page qu'il lit est sur son propre nœud. Les fonctions ci-dessous construisent ce motif d'accès pour 400 enregistrements sur quatre threads, et comptent les accès locaux et distants et leur temps pour trois placements. Dans le premier, « single », un seul thread a initialisé toutes les données, donc la première touche a mis chaque page sur le nœud 0. Dans le deuxième, les propriétaires ont initialisé leurs propres morceaux. Dans le troisième, les pages sont entrelacées.

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}

Avec un seul thread qui initialise tout, la moitié des accès sont distants et le travail prend 42 000 ns pour 400 lectures. Quand les propriétaires initialisent leurs morceaux, rien n'est distant et cela prend 32 000 ns, environ 1,3 fois plus vite, pour exactement le même programme. L'entrelacement n'aide pas ici : comme chaque thread lit un morceau contigu, les pages entrelacées mettent la moitié de ses données sur le mauvais nœud. L'entrelacement sert pour des données que tous les threads lisent partout, où aucun placement ne peut convenir à tous.

Le labo suit le cours : le nœud d'un thread, les deux règles de placement, le motif d'accès d'un travail partitionné, le décompte des accès locaux et distants, et l'étude sur les enregistrements SPY.

• Fonction · questionS'appuie sur
• node_of_thread(thread, threads_per_node)Sur quel nœud tourne un thread ?La division entière
• first_touch_placement(trace, threads_per_node)Où la première touche place-t-elle chaque page ?node_of_thread
• interleaved_placement(trace, n_nodes)Et l'entrelacement ?De l'arithmétique simple
• partition_trace(n_records, n_threads, record_bytes)Quels accès chaque thread fait-il ?De l'arithmétique simple
• access_costs(trace, placement, threads_per_node)Combien d'accès locaux et distants, et combien de temps ?node_of_thread
• study(bars)Que coûte un mauvais placement sur les enregistrements SPY ?partition_tracefirst_touch_placementaccess_costs

Sujet suivant : savoir où vivent les octets n'est que la moitié de l'histoire ; la façon dont on les distribue compte aussi. Dans Allocateurs et pools mémoire, un programme demande beaucoup de petits objets, et l'ordre et les endroits où l'allocateur les distribue décident du nombre de lignes de cache qu'un parcours ultérieur touche.