Spice: paralelismo de grano fino en Zig con sobrecarga subnanosegundo
(github.com/judofyr)Spice: paralelismo con overhead subnanosegundo
Spice logra un paralelismo muy eficiente en Zig usando heartbeat scheduling
- Overhead subnanosegundo: incluso al agregar capacidades de paralelismo a una función, solo se introduce un overhead menor a un nanosegundo
- Sin contención: los hilos no compiten por la misma tarea. Agregar más hilos al sistema no hace que el programa se vuelva más lento
Comparación de rendimiento
- Rayon (Rust): genera un overhead de aproximadamente 15 ns con 4 hilos. Logra una aceleración de unas 14 veces con 16 hilos
- Spice (Zig): logra una aceleración de unas 11 veces con 16 hilos. El overhead es tan bajo que el rendimiento es casi idéntico al base
Rendimiento en árboles pequeños
- Árboles pequeños: el tiempo total de ejecución del programa es de 1.56 microsegundos. El rendimiento empeora a medida que se agregan más hilos
- Sabiduría general del paralelismo: si no hay suficiente trabajo, el paralelismo no vale la pena
Objetivo de Spice
- Objetivo: que agregar paralelismo no haga más lento al programa
- Tiempos de ejecución cortos: si el tiempo de ejecución es breve, el multihilo no funciona. Los hilos adicionales pasan a estado de espera
Cómo usar 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;
}
- Todas las funciones paralelas deben recibir una task como parámetro
- No se debe llamar a la función directamente; se debe usar
t.call - Se llama a
forkpara programar trabajo en otro hilo - La función debe realizar por sí misma un trabajo significativo
- Se llama a
joinpara esperar a que termine el trabajo de otro hilo - Si
joindevuelvenull, el trabajo debe realizarse directamente
Work-stealing e ineficiencia
- Work-stealing: cada hilo tiene su propia cola local de tareas. Cuando la cola se vacía, roba trabajo de otros hilos
- Ineficiencia: despacho dinámico, colas de trabajo no locales y spin locks
Detalles de implementación
Optimización con despacho estático
- Ejecución paralela de bloques de código: se usan
forkyjoinpara ejecutar bloques de código en paralelo - Eliminación de duplicación: si un bloque de código no se ejecuta en otro hilo, se ejecuta de forma secuencial
Señal de heartbeat de bajo overhead
- Heartbeat scheduling: cada 100 microsegundos se revisa la cola local de tareas y se envía trabajo a otros hilos
- Eficiencia: la función debe operar eficientemente cuando no ocurre un heartbeat
Mutex global
- Uso de mutex global: un mutex global no representa un problema cuando no hay contención
Lista doblemente enlazada sin ramas
- Lista doblemente enlazada: se usa para gestionar la cola de tareas. Funciona sin ramas
Minimización del uso de stack
- Optimización del uso de stack: se minimiza el estado de
Futurepara reducir el uso de stack
Paso de valores mediante registros
- Uso de registros: los campos de la estructura
Taskse pasan en registros para optimizar el rendimiento
Benchmarks
- Benchmarks: el desarrollo inicial se centró en un solo benchmark
Agradecimientos
- Investigación sobre heartbeat scheduling: fue desarrollado con base en varios artículos de investigación
Limitaciones
- Restricciones: si se usa incorrectamente, puede producir comportamientos extraños
- Falta de pruebas: la cobertura de pruebas es insuficiente
- Soporte insuficiente para arreglos/slices: falta soporte de paralelismo para arreglos y slices
- Falta de documentación: hay poca documentación sobre cómo usarlo
- Faltan benchmarks adicionales: se necesitan más benchmarks
- Manejo de errores: se ha considerado poco el manejo de errores
- Faltan pruebas en ReleaseSafe: se necesitan pruebas en modo ReleaseSafe
FAQ
- Origen del nombre: se refiere a un paralelismo extremadamente fino
- Por qué fue implementado en Zig: podría implementarse en varios lenguajes
- Paralelismo seguro en Rust: las semánticas estrictas de Rust dificultan explorar la idea inicial
Resumen de GN⁺
- Spice es un proyecto de investigación que ofrece paralelismo muy eficiente en Zig
- Overhead subnanosegundo y paralelismo sin contención maximizan el rendimiento
- Heartbeat scheduling distribuye el trabajo de forma eficiente
- Tiene limitaciones como restricciones y falta de pruebas
- Vale la pena explorar enfoques similares en otros lenguajes como Rust
1 comentarios
Opiniones de Hacker News
Esta implementación se basa en una investigación reciente llamada "heartbeat scheduling" y logra un control dinámico automático de la granularidad al distribuir el costo de crear paralelismo
No he leído los detalles del código, pero "sub-nanosecond overhead" es engañoso y suena a término de marketing
No conozco mucho este campo, pero me gusta el modelo de concurrencia que presentan
Es un trabajo de investigación interesante y, además del código, tiene una buena argumentación y documentación bien redactada
Lista de limitaciones del proyecto:
Según la explicación, esta implementación usa busy-wait para que los workers logren latencias del orden de nanosegundos
Me pregunto si hay una forma más rápida de que el productor de tareas despierte al consumidor sin busy-wait
Es interesante y está vinculado con artículos excelentes
El scheduling cooperativo es la base de muchos patrones con métricas excelentes
Excelente
Consulta también el README de benchmarks: