Spice: técnica de paralelismo refinado em Zig com overhead abaixo de um nanossegundo
(github.com/judofyr)Spice: processamento paralelo com overhead abaixo de um nanossegundo
Spice alcança processamento paralelo extremamente eficiente em Zig usando heartbeat scheduling
- Overhead abaixo de um nanossegundo: adicionar recursos de paralelismo a uma função gera menos de um nanossegundo de overhead
- Sem contenção: as threads não competem pela mesma tarefa. Mesmo adicionando threads ao sistema, o programa não fica mais lento
Comparação de desempenho
- Rayon (Rust): cerca de 15 ns de overhead com 4 threads. Ganho de velocidade de cerca de 14x com 16 threads
- Spice (Zig): ganho de velocidade de cerca de 11x com 16 threads. O overhead é tão baixo que o desempenho fica quase igual ao da execução base
Desempenho em árvores pequenas
- Árvores pequenas: o tempo total de execução do programa é de 1,56 microssegundo. O desempenho piora à medida que mais threads são adicionadas
- Sabedoria convencional do paralelismo: sem trabalho suficiente, paralelizar não vale a pena
Objetivo do Spice
- Objetivo: permitir adicionar paralelismo sem deixar o programa mais lento
- Tempo de execução curto: quando a execução é curta, o multithreading não funciona bem. As threads extras entram em espera
Como usar o Spice
const spice = @import("spice");
fn sum(t: *spice.Task, node: *const Node) i64 {
var res: i64 = node.val;
if (node.left) |left_child| {
if (node.right) |right_child| {
var fut = spice.Future(*const Node, i64).init();
fut.fork(t, sum, right_child);
res += t.call(i64, sum, left_child);
if (fut.join(t)) |val| {
res += val;
} else {
res += t.call(i64, sum, right_child);
}
return res;
}
res += t.call(i64, sum, left_child);
}
if (node.right) |right_child| {
res += t.call(i64, sum, right_child);
}
return res;
}
- Toda função paralela deve receber uma task como parâmetro
- Em vez de chamar a função diretamente, é preciso usar
t.call - Chame
forkpara configurar o trabalho em outra thread - A função deve realizar por conta própria um trabalho significativo
- Chame
joinpara esperar a conclusão do trabalho da outra thread - Se
joinretornarnull, é preciso executar o trabalho diretamente
Work-stealing e ineficiência
- Work-stealing: cada thread tem sua própria fila de trabalho local. Quando a fila esvazia, ela rouba trabalho de outra thread
- Ineficiências: despacho dinâmico, filas de trabalho não locais, spinlocks
Detalhes de implementação
Otimização com despacho estático
- Execução paralela de blocos de código: usa
forkejoinpara executar blocos de código em paralelo - Eliminação de duplicação: se o bloco de código não for executado em outra thread, ele é executado de forma sequencial
Sinal de heartbeat de baixo overhead
- Heartbeat scheduling: a cada 100 microssegundos, verifica a fila de trabalho local e envia trabalho para outras threads
- Eficiência: a função precisa operar de forma eficiente quando o heartbeat não está acontecendo
Mutex global
- Uso de mutex global: um mutex global não é um problema quando não há contenção
Lista duplamente encadeada sem desvios
- Lista duplamente encadeada: usada para gerenciar a fila de trabalho. Opera sem desvios
Minimização do uso de pilha
- Otimização do uso de pilha: minimiza o estado de
Futurepara reduzir o uso de pilha
Passagem de valores por registradores
- Uso de registradores: os campos da struct
Tasksão passados por registradores para otimizar o desempenho
Benchmark
- Benchmark: o desenvolvimento inicial foi centrado em um único benchmark
Agradecimentos
- Pesquisa sobre heartbeat scheduling: desenvolvido com base em vários artigos de pesquisa
Limitações
- Restrições: se usado incorretamente, pode produzir comportamentos estranhos
- Poucos testes: a cobertura de testes é insuficiente
- Suporte fraco a arrays/slices: falta suporte adequado para paralelismo em arrays/slices
- Pouca documentação: faltam documentos sobre como usar
- Faltam benchmarks adicionais: são necessários benchmarks extras
- Tratamento de erros: há pouca consideração sobre tratamento de erros
- Poucos testes em ReleaseSafe: é preciso testar no modo ReleaseSafe
FAQ
- Origem do nome: significa paralelismo extremamente refinado
- Por que foi implementado em Zig: pode ser implementado em várias linguagens
- Paralelismo seguro em Rust: a semântica rígida de Rust dificulta explorar a ideia inicial
Resumo do GN⁺
- Spice é um projeto de pesquisa que oferece paralelismo extremamente eficiente em Zig
- Overhead abaixo de um nanossegundo e paralelismo sem contenção maximizam o desempenho
- Usa heartbeat scheduling para distribuir trabalho com eficiência
- Há limitações como restrições e poucos testes
- Vale a pena explorar abordagens semelhantes em outras linguagens, como Rust
1 comentários
Opinião no Hacker News
Esta implementação se baseia em uma pesquisa recente, "heartbeat scheduling", e distribui o overhead da criação de paralelismo para alcançar controle dinâmico automático de granularidade
Não li os detalhes do código, mas "sub-nanosecond overhead" é enganoso e parece termo de marketing
Não conheço bem esta área, mas gostei do modelo de concorrência apresentado
É um trabalho de pesquisa interessante, com boa argumentação e documentação bem escrita além do código
Lista de limitações do projeto:
Segundo a explicação, esta implementação usa espera ocupada para que os workers atinjam latência na escala de nanossegundos
Fico me perguntando se existe uma forma mais rápida de um produtor de tarefas acordar um consumidor sem espera ocupada
Interessante e conectado a ótimos artigos
Escalonamento cooperativo é a base de muitos padrões com ótimas métricas
Excelente
Veja também o README de benchmarks: