Everything You Always Wanted to Know About Synchronization - resumo em slides desse artigo

Prévia do material em texto

Everything You Always Wanted to 
Know About Synchronization 
Tudo o que você sempre quis saber sobre sincronização mas teve medo de 
perguntar
But Were Afraid to Ask
Hosana Gomes e Samara Almendane
 Agenda
• Sobre
• Introdução
• Objetivo do artigo
• Contextualização
• Metodologia utilizada pelos autores
• Conclusões
• Trabalhos relacionados 
• Trabalhos futuros
• Avaliação do artigo
 Sobre
- Autores: Tudor David, Rachid Guerraoui, Vasileios Trigonakis
- Ano: 2013 
- Local de publicação: School of Computer and 
 Communication Sciences, Ecole Polytechnique
 Fédérale de Lausanne (EPFL), Switzerland
Introdução
 O que é Sincronização ?
- É o ato de coordenar o tempo de execução de um conjunto de processos.
- Muitos cores podem retardam um ao outro: 
 - Afeta a performance. 
 - Aniquila o propósito de aumentar esse número.
- A sincronização é efetiva se a performance não diminui conforme o número de 
cores aumenta.
 Problema dos estudos na área:
- Difícil generalização
 - Muita especificação da aplicação e da arquitetura.
- Falta de clareza no que está sendo tratado:
 - Hardware, algoritmo de sincronização por si , uso de operações 
atômicas, carga de trabalho...
Objetivos
 Neste artigo:
- Duas direções de análises:
 Tipos usados
- Multi-socket: 
 - Baseada em:
 - diretórios: Opteron (4 sockets)
 - broadcast: Xeon (8 sockets)
- Single-socket:
 - Uniforme: Niagara (8 cores)
 - Não-uniforme: Tilera (36 cores)
Contextualização
 Sincronização baseada em hardware
- Protocolo de coerência de cache: responsável por manter os dados nas cache.
- MESI
- Possui quatro estados para uma linha de cache:
- Modified (Modificado): os dados estão obsoletos na memória e nenhum outro cache tem 
uma cópia desta linha
- Exclusive (Exclusivo): os últimos dados ficam na memória e nenhum outro cache tem uma 
cópia desta linha
- Shared (Partilhado): os últimos dados ficam na memória, mas outro cache tem uma cópia 
desta linha
- Invalid (Inválido): os dados são inválidos
 Sincronização baseada em software
- O que são Locks ?
 - Abstração de software para garantir a exclusão mutúa.
 - Spin Lock
 - Processo fica num loop(spin) até conseguir o bloqueio.
 - Possuem baixa escalonabilidade: muita contenção numa única linha de
 cache.
 
 - Locks hierárquicos
 - Locks de exclusão mútua que encorajam threads com alta localidade de
 memória mútua a adquirir o lock consecutivamente.
 - Reduz a quantidade de cache misses ao executar instruções na 
 região crítica.
- Nesse estudo:
 - Alternativa para locks: particionamento de recurso do sistema entre
 processos.
 - Sincronização atingida por passagem de mensagens
 Explicaremos mais tarde! 
SSYNC
 O que é? 1/2
- Plataforma de cruzamento construída pelos autores do artigo.
- Bibliotecas:
- libslock: Abstrai vários algoritmos de lock por trás de uma interface comum. 
- libssmp: Tem implementações de transmissões de mensagens para cada uma das quatro 
plataformas.
- Microbenchmarks: 
- utilizados para testar um específico aspecto do sistema, sendo capaz de comparar 
performances de soluções equivalentes e avaliar componentes do sistema, tais como, CPU e 
memória.
- ccbench: ferramenta para medir o custo de operações numa linha de cache. Dependendo do 
estado e colocação MESI da linha no sistema.
- Testes providos pela SSYNC para libslock e libssmp. Servem para medir a 
latência ou o throughput dessas primitivas sob várias condições. 
 O que é? 2/2
- Software concorrente
 - HashTable(ssht) : Manipular os dados de modo mais eficiente 
 possível.
 - Transactional memory (TM²C): é um sistema de memória baseada
 em passagem de mensagens de software transacional para 
 many-cores.
- SSYNC está disponível em: http://lpd.epfl.ch/site/ssync
Análise nível de
hardware
 Análise de nível de hardware
- Objetivo: analisar as latências efetuadas no hardware pelo os protocolos de 
Coerência de Cache e discutir como reduzir em determinados casos.
- Usando ccbench para medir as operações básicas.
 Acessos Locais
Latências para acessar os caches locais de um núcleo.
 Acessos Remotos
Latências(ciclos) para carregar, armazenar ou executar uma operação atômica 
em uma linha de cache baseado em seu estado anterior e localização.
Análise nível
de software
 Análise de nível de software
- Objetivo: discutir como reduzir em determinados casos as latências 
efetuadas pelos protocolos de coerência de cache.
 Uncontested Locking - Bloqueio incontestável
- Objetivo: medir a latência para obter um lock com base na localização do suporte 
anterior .
- As latências sofrem aumentos importantes sobre as multi-sockets(Opteron e Xeon).
- Em geral, aquisições, que precisam de transferência de dados através de sockets têm 
um custo elevado.
- Aquisições remotas podem ser de até 12,5 e 11 vezes mais caras do que as locais no 
Opteron e do Xeon respectivamente. Por outro lado, devido às LLCs partilhadas e 
distribuídas, o Niagara e o Tilera não sofrem desempenho de vinco ligeiro, 
respectivamente, como a localização da segunda alterações da linha.
 Lock Algorithm Behavior
- Como funciona: (Passo a passo)
- Objetivo: medir a taxa de transferência total de aquisições de lock que podem 
ser realizadas usando cada uma dos locks.
- Estudos com alta e baixa contençao.
Thread A Thread A Thread A
1 - Adquirir 
bloqueio 
aleatório
2 - ler/escrever 
linha de cache 
correspondente
3 - Liberar o 
bloqueio
 Contenção extrema
Como funciona: uma thread faz uma pausa após ela liberar o bloqueio, a 
fim de assegurar que a libertação torna-se visível para os outros cores 
antes de repetir a adquirir o lock.
 Lock Algorithm Behavior 
Resultados: Em geral, locks simples igualam ou mesmo superam os locks mais complexos. No 
Xeon as diferenças entre locks tornam-se insignificantes para um grande número de cores. E o 
ticket lock tem o melhor desempenho na Opteron, no Niagara, e no Tilera. Em um cenário de 
baixo contenção é, portanto, difícil de justificar os requisitos de memória que os algoritmos 
complexos de lock têm.
 Contenção muito baixa
 Cross-Platform Lock Behavior
- Comportamento do lock sob vários níveis de contenção entre arquiteturas. 
 Message Passing
- Objetivo: avaliar as mensagens que passa nas implementações de SSYNC.
- Como funciona: captura os padrões de comunicação mais importante de um 
aplicativo de passagem de mensagem, avaliando a comunicação um-para-
um e cliente-servidor.
- Tamanho da mensagem: 64 bytes (uma linha de cache).
 Um-para-um (one-to-one) 1/2
Core X Core Y
1 - Traz o buffer recebedor da 
mensagem para o local de cache.
2 - Escreve uma nova mensagem 
no buffer.
3 - Pega a mensagem.
 Um-para-um (one-to-one) 2/2
 Cliente-servidor
 Hash Table (ssht)
- Objetivo: Avaliar a execução simultânea da tabela hash SSYNC, sob baixa e 
alta de contenção, bem comode curta duração e buckets longos.
- Como funciona: o ssht configura de modo que cada bucket é protegido por 
um único bloqueio. Configura-se a passagem de mensagens na versão (mp), 
para usar um servidor por três núcleos e todas as operações de bloquear, à 
espera da resposta do servidor.
 Baixa contenção
Resultado: em todas as plataformas o aumento do comprimento das secções críticas aumenta a 
escalabilidade do ssht à base de lock, exceto para o Tilera.
Nota-se que o Xeon escala ligeiramente mesmo fora dos 10 núcleos de uma threads, transmitindo 
assim a mais alta taxa de transferência entre todas as plataformas.
Finalmente, o melhor desempenho neste cenário é alcançado por locks de rotação simples.
 Alta contenção
Resultados: a versão de mensagem que passa não só supera as base de lock em três das quatro 
plataformas (por altas contagens de core), mas também oferece a mais alta taxa de transferência.
As threads do Niagara não favorecem soluções cliente-servidor: os servidores são atrasados devido 
à partilha de recursos do core com outras threads. Entretanto, alcança um aumento de desempenho 
de 10 vezes em 36 threads, que é a melhor escalabilidade entre as versões baseadas em lock.
 Key-Value Store (Memcached)
- É um valor de chave na memória, baseado na hash table.
- Objetivo: implantar a ferramenta memslap em um servidor remoto e usar sua 
configuração padrão. Usando 500 threads de cliente e executar os testes get-
only e set-only
- Resultados: não causa qualquer troca para locks globais. Devido à 
contenção essencialmente inexistente, o algoritmo de lock tem pouco efeito 
neste teste.
 Get
 Set
Trabalhos 
Relacionados
 Maximização da coerência de cache
- Estudos de protocolo de cache em multi-soquetes x86, com foco na limitação 
da largura de banda. [Molka]
 - Latências da coerência de cache medidas de acordo com o 
 carregamento de dados.
- Uso de simulações para mostrar que aumentando a não-uniformidade 
envolve uma diminuição na performance do TTAS lock sob baixa disputa
(contention). [Moses]
 Escalonamento de locks
- Necessidade de escalonamento com spin locks. [Mellor-Crumney] [Anderson]
 
- Estudo de lock CLH hieráquico num NUMA-aware. Compara a performance 
desses locks com outros locks conhecidos.[Luchangco]
- Foco no kernel do Linux. A implementação padrão do ticket lock causa um 
gargalo significativo no SO num multi-core. [Morris]
 Escalonamento de sistemas em many-cores
- O Sistema Operacional é re-estruturado para :
 - Melhorar localidade [Tornado];
 - limitar compartilhamento [Corey];
 - evitar compartilhamento de recursos completo pelo uso de passagem 
 de mensagens [Barrelfish].
- Verifica se os problemas de escalonabilidade são do design do kernel Linux.
 Otimização com técnicas de programação,eliminando problemas de
 escalonamento do kernel e de aplicações. [Boyd-Wickizer]
Conclusões
 Conclusões
- Cruzar soquetes impacta significantemente na sincronização, independente 
da camada(coerência de cache, locks, operações atômicas) 
- Sincronização escalona muito melhor dentro de um único soquete, não 
diferente do nível de disputa. (contention) 
- Se possível, sistemas com muito compartilhamento deveria reduzir 
sincronização de soquetes cruzada ao mínimo.
- A não uniformidade afeta a escalabilidade mesmo dentro de um many-core 
de soquete único. (A sincronização no Sun Niagara 2 escalona melhor do 
que no Tilera TILE-Gx36).
- Se reduzido o contexto da sincronização para um soquete único, seja um 
soquete de um multi-soquete ou um many-core de soquete único, os 
resultado indica que spin locks devem ser escolhidos em relação a muitos 
locks complexos . 
- Implementar coerência em multi-soquete usando broadcast ou diretório 
incompleto(Opteron) não é favorável para a sincronização.
Trabalhos Futuros
 Ampliar os experimentos
- Estudar as técnicas de lock-free, uma maneira interessante de modelar livre 
exclusão mútua (mutual exclusion-free) nas estruturas de dados.
- Serialização de seções críticas sobre passagem de mensagem enviando 
requests para um único servidor.
- Comparar diferentes plataformas e esquemas de sincronização por watt.
- Estudar as Transactional Synchronization Extensions (TSX) no SSYNC.