Efeitos NUMA

Num servidor de dois soquetes a mesma leitura pode custar 80 ns ou 130 ns, conforme o soquete onde a página mora. Onde uma página mora é decidido na primeira vez que ela é tocada. Esta aula modela dois nós, mostra como uma só thread que inicializa os dados deixa metade do trabalho remota e corrige isso deixando cada thread tocar primeiro a sua própria parte.

Um servidor grande tem dois soquetes de processador, e cada soquete tem seus próprios módulos de memória. Um núcleo lê diretamente a memória do seu soquete. Para ler a do outro soquete, o pedido atravessa um enlace entre os soquetes, o que leva mais tempo. Uma máquina assim é NUMA. Cada soquete e sua memória formam um nó, e o nó de uma thread é onde seu núcleo está. No nosso modelo há dois nós com duas threads cada: as threads 0 e 1 no nó 0 e as threads 2 e 3 no nó 1. Um acesso local custa 80 ns e um remoto 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]

Cada linha é a visão de uma thread: ela paga 80 ns pelas páginas do seu próprio nó e 130 ns pelas do outro. A diferença, 50 ns, parece pequena, mas vale para todo acesso que chega à memória.

O sistema operacional dá memória a um programa em páginas e escolhe o nó de uma página no momento em que ela é usada pela primeira vez. A regra padrão é o primeiro toque: a página vai para o nó da thread que a toca primeiro e fica lá. Uma alternativa é intercalar as páginas entre os nós. O código abaixo aplica as duas regras a uma lista curta de acessos escritos como (thread, endereço).

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}

As páginas 0 e 1 foram tocadas primeiro pela thread 0, que está no nó 0, então vão para o nó 0. A página 2 foi tocada primeiro pela thread 3, no nó 1, então vai para o nó 1. O acesso posterior da thread 1 à página 1 não a move. A intercalação ignora quem toca o quê: a página 1 vai para o nó 1 simplesmente porque 1 módulo 2 é 1.

Um trabalho paralelo típico divide uma tabela em pedaços, um por thread. Cada thread lê então só o seu pedaço, então o ideal é que toda página que ela lê esteja no seu próprio nó. As funções abaixo montam esse padrão de acesso para 400 registros entre quatro threads, e contam os acessos locais e remotos e seu tempo para três colocações. Na primeira, "single", uma só thread inicializou todos os dados, então o primeiro toque pôs cada página no nó 0. Na segunda, os donos inicializaram seus próprios pedaços. Na terceira, as páginas estão intercaladas.

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}

Com uma só thread inicializando tudo, metade dos acessos é remota e o trabalho leva 42 000 ns para 400 leituras. Quando os donos inicializam seus pedaços, nada é remoto e leva 32 000 ns, cerca de 1,3 vez mais rápido, para exatamente o mesmo programa. A intercalação não ajuda aqui: como cada thread lê um pedaço contíguo, as páginas intercaladas põem metade dos seus dados no nó errado. A intercalação serve para dados que todas as threads leem por toda parte, onde nenhuma colocação serve a todas.

O laboratório segue a aula: o nó de uma thread, as duas regras de colocação, o padrão de acesso de um trabalho particionado, a contagem de acessos locais e remotos e o estudo sobre os registros do SPY.

• Função · perguntaBaseia-se em
• node_of_thread(thread, threads_per_node)Em que nó uma thread roda?A divisão inteira
• first_touch_placement(trace, threads_per_node)Onde o primeiro toque põe cada página?node_of_thread
• interleaved_placement(trace, n_nodes)E a intercalação?Aritmética simples
• partition_trace(n_records, n_threads, record_bytes)Que acessos cada thread faz?Aritmética simples
• access_costs(trace, placement, threads_per_node)Quantos acessos locais e remotos, e quanto tempo?node_of_thread
• study(bars)Quanto custa uma colocação ruim nos registros do SPY?partition_tracefirst_touch_placementaccess_costs

Próximo tópico: onde os bytes moram é só metade da história; como eles são distribuídos também importa. Em Alocadores e pools de memória um programa pede muitos objetos pequenos, e a ordem e os lugares em que o alocador os entrega decidem quantas linhas de cache um percurso posterior toca.