Falso compartilhamento e preenchimento

Quatro threads atualizam cada uma seu próprio contador, nada é compartilhado, e ainda assim o laço roda 40 vezes mais devagar do que deveria. O motivo é que os quatro contadores estão na mesma linha de cache e os núcleos brigam por ela. Esta aula constrói um pequeno modelo de coerência de cache, mostra o que o falso compartilhamento custa num laço guiado pelas datas da tabela do SPY e o corrige com alguns bytes de preenchimento.

Até agora um programa rodava em um núcleo. Uma máquina real tem vários núcleos, e cada um tem seu próprio cache pequeno e rápido. Isso cria um problema: se o núcleo 0 e o núcleo 1 guardam uma cópia de uma linha e o núcleo 0 a altera, o núcleo 1 não pode continuar lendo o valor antigo. A regra de hardware que impede isso é a coerência de cache. O jeito mais simples de impô-la: antes de um núcleo escrever numa linha, a cópia dessa linha em todos os outros núcleos é descartada. Isso é uma invalidação.

1. 1
   Olhar no próprio cacheSe a linha não está lá, este acesso é uma falta.
2. 2
   Ao escrever, expulsar os outrosCada outro núcleo que tem a linha perde sua cópia: uma invalidação cada.
3. 3
   Ficar com a linhaDepois a linha está no cache deste núcleo, pronta para o próximo acesso.

A classe abaixo guarda, para cada núcleo, o conjunto de linhas que ele tem. Repetimos três passos: o núcleo 0 escreve o byte 0, o núcleo 1 escreve o byte 8 (a mesma linha) e depois o núcleo 0 escreve de novo o byte 0.

class CoherentCaches:    def __init__(self, n_cores):        self.lines = [set() for _ in range(n_cores)]        self.misses = 0        self.invalidations = 0    def access(self, core, address, write):        line = address // LINE_BYTES        hit = line in self.lines[core]        if not hit:            self.misses += 1        if write:            for other, held in enumerate(self.lines):1                if other != core and line in held:                    held.discard(line)                    self.invalidations += 1        self.lines[core].add(line)        return hitcaches = CoherentCaches(2)print(caches.access(0, 0, True), caches.access(1, 8, True), caches.access(0, 0, True))print("misses:", caches.misses, "invalidations:", caches.invalidations)

False False False
misses: 3 invalidations: 2

1. 1Uma escrita remove a linha de cada outro núcleo que a tenha e conta uma invalidação por cópia.

Os três acessos falham. A escrita do núcleo 1 invalida a cópia do núcleo 0, e a nova escrita do núcleo 0 invalida por sua vez a cópia do núcleo 1. Os núcleos 0 e 1 nunca escreveram o mesmo byte, só bytes vizinhos, e ainda assim tiram a linha um do outro a cada escrita.

Um jeito comum de contar eventos em paralelo é dar a cada núcleo seu próprio contador, para que nenhum núcleo espere outro. Os contadores têm 8 bytes cada. Coloque-os um após o outro num array e quatro cabem numa linha de 64 bytes. Montamos as escritas de 50 rodadas de atualizações, uma escrita por núcleo em cada rodada, e as repetimos com os contadores a 8 bytes (compactos) e a 64 bytes (com preenchimento). O tempo é de 1 ns para um acesso no cache do próprio núcleo e de 60 ns para uma falta que busca a linha de outro núcleo.

def counter_address(core, stride_bytes):    return core * stride_bytesdef update_trace(n_cores, n_updates, stride_bytes):    return [(core, "w", counter_address(core, stride_bytes)) for _ in range(n_updates) for core in range(n_cores)]def run_trace(trace, n_cores):    caches = CoherentCaches(n_cores)    for core, op, address in trace:        caches.access(core, address, op == "w")    return {"accesses": len(trace), "misses": caches.misses, "invalidations": caches.invalidations}def time_ns(stats):    return (stats["accesses"] - stats["misses"]) * HIT_NS + stats["misses"] * MISS_NSfor name, stride in (("packed", 8), ("padded", 64)):    stats = run_trace(update_trace(4, 50, stride), 4)    print(name, stats, time_ns(stats), "ns")

packed {'accesses': 200, 'misses': 200, 'invalidations': 199} 12000.0 ns
padded {'accesses': 200, 'misses': 4, 'invalidations': 0} 436.0 ns

Compactos, as 200 escritas falham e 199 delas invalidam o escritor anterior: 12 000 ns. Com preenchimento, cada núcleo guarda seu contador numa linha própria: quatro faltas a frio no início, depois toda escrita acerta e não há invalidações: 436 ns. É 27 vezes mais rápido para exatamente a mesma aritmética, porque os quatro núcleos não tiram mais a linha uns dos outros.

Para dar a cada contador uma linha própria, a distância entre dois contadores precisa ser um múltiplo do tamanho da linha, então o tamanho do item é arredondado para o próximo múltiplo de 64. Um contador de 8 bytes ocupa 64 bytes, o que desperdiça 56. Um item de 65 bytes ocupa 128. A função abaixo faz o arredondamento.

def padding_needed(item_bytes):    return math.ceil(item_bytes / LINE_BYTES) * LINE_BYTESprint([padding_needed(size) for size in (8, 63, 64, 65, 100)])

[64, 64, 64, 128, 128]

No laboratório quatro núcleos contam cada um os dias de pregão que atendem, e o dia número i da tabela do SPY vai para o núcleo dia da semana % 4. Os primeiros 1000 dias guiam as escritas em ordem de data. Como os dias seguem o calendário, o mesmo núcleo raramente escreve duas vezes seguidas e a linha é tirada de novo e de novo. Com os contadores compactos, 818 das 1000 escritas falham e 817 invalidam outro núcleo; com eles preenchidos, só as quatro primeiras escritas falham.

O laboratório constrói o modelo de coerência, os rastros de contadores por núcleo com um passo dado, a repetição, a regra de preenchimento, o modelo de tempo e o estudo sobre as datas do SPY.

• Função · perguntaBaseia-se em
• CoherentCaches(n_cores).access(core, address, write)Acerto ou falta, e quem perde uma cópia?Aritmética simples
• counter_address(core, stride_bytes)Onde vive o contador de um núcleo?Aritmética simples
• update_trace(n_cores, n_updates, stride_bytes)Que escritas os núcleos fazem?counter_address
• run_trace(trace, n_cores)Quantas faltas e invalidações?CoherentCaches
• padding_needed(item_bytes)A que distância devem estar os itens?Aritmética simples
• time_ns(stats)Quanto tempo leva a execução?Os custos de acerto e falta
• study(bars)Quanto custa o falso compartilhamento nas datas do SPY?run_tracepadding_neededtime_ns

Próximo tópico: o falso compartilhamento trata de núcleos que dividem um soquete. Numa máquina com dois soquetes a própria memória é dividida: uma parte está perto de um núcleo e outra longe. Em Efeitos NUMA você coloca páginas em nós, conta os acessos locais e remotos e precifica a diferença.