Spice : une technique de parallélisme très fin avec une surcharge subnanoseconde en Zig
(github.com/judofyr)Spice : parallélisme avec une surcharge subnanoseconde
Spice atteint un parallélisme très efficace en Zig grâce au heartbeat scheduling
- Surcharge subnanoseconde : ajouter des capacités de parallélisme à une fonction n’introduit qu’une surcharge inférieure à la nanoseconde
- Sans contention : les threads ne se disputent pas la même tâche. Ajouter des threads au système ne ralentit pas le programme
Comparaison des performances
- Rayon (Rust) : environ 15 ns de surcharge sur 4 threads. Environ 14× d’accélération sur 16 threads
- Spice (Zig) : environ 11× d’accélération sur 16 threads. La faible surcharge donne des performances presque identiques au mode de base
Performances sur de petits arbres
- Petits arbres : temps d’exécution total du programme de 1,56 microseconde. Les performances se dégradent à mesure qu’on ajoute des threads
- Principe général du parallélisme : s’il n’y a pas assez de travail, le parallélisme n’en vaut pas la peine
Objectif de Spice
- Objectif : faire en sorte que l’ajout de parallélisme ne ralentisse pas le programme
- Temps d’exécution court : si l’exécution est trop courte, le multithreading ne fonctionne pas. Les threads supplémentaires passent en attente
Utilisation de 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;
}
- Toutes les fonctions parallèles doivent recevoir une task en paramètre
- Il faut utiliser
t.callau lieu d’appeler directement la fonction - Appeler
forkpour planifier du travail sur un autre thread - La fonction doit elle-même effectuer un travail significatif
- Appeler
joinpour attendre la fin du travail exécuté sur un autre thread - Si
joinrenvoienull, il faut exécuter soi-même le travail
Work-stealing et inefficacités
- Work-stealing : chaque thread possède sa propre file de tâches locale. Quand sa file est vide, il vole des tâches à d’autres threads
- Inefficacités : dispatch dynamique, files de tâches non locales, spin locks
Détails d’implémentation
Optimisation du dispatch statique
- Exécution parallèle de blocs de code : utilisation de
forketjoinpour exécuter des blocs de code en parallèle - Élimination des doublons : si un bloc de code n’est pas exécuté sur un autre thread, il est exécuté séquentiellement
Signal heartbeat à faible surcharge
- Heartbeat scheduling : vérifie la file de tâches locale toutes les 100 microsecondes et envoie du travail à d’autres threads
- Efficacité : les fonctions doivent rester efficaces lorsqu’aucun heartbeat ne se produit
Mutex global
- Utilisation d’un mutex global : un mutex global ne pose pas de problème en l’absence de contention
Liste doublement chaînée sans branchement
- Liste doublement chaînée : utilisée pour gérer la file de tâches. Fonctionne sans branchement
Minimisation de l’utilisation de la pile
- Optimisation de l’utilisation de la pile : l’état de
Futureest réduit au minimum afin de limiter l’usage de la pile
Passage de valeurs via les registres
- Utilisation des registres : les champs de la structure
Tasksont passés dans les registres pour optimiser les performances
Benchmark
- Benchmark : le développement initial s’est concentré sur un seul benchmark
Remerciements
- Recherche sur le heartbeat scheduling : développement fondé sur plusieurs articles de recherche
Limites
- Contraintes : une mauvaise utilisation peut produire des comportements étranges
- Manque de tests : la couverture de test est insuffisante
- Support insuffisant des tableaux/slices : le support du parallélisme pour les tableaux/slices est limité
- Documentation insuffisante : la documentation d’utilisation manque encore
- Manque de benchmarks supplémentaires : des benchmarks complémentaires sont nécessaires
- Gestion des erreurs : la gestion des erreurs a été peu prise en compte
- Manque de tests en ReleaseSafe : des tests sont nécessaires en mode ReleaseSafe
FAQ
- Origine du nom : fait référence à un parallélisme extrêmement fin
- Pourquoi une implémentation en Zig : une implémentation est possible dans différents langages
- Parallélisme sûr en Rust : la sémantique stricte de Rust rend difficile l’exploration des idées initiales
Résumé GN⁺
- Spice est un projet de recherche qui fournit un parallélisme très efficace en Zig
- Surcharge subnanoseconde et parallélisme sans contention maximisent les performances
- Le heartbeat scheduling permet de répartir efficacement le travail
- Il existe des limites, notamment des contraintes et un manque de tests
- Cela vaut la peine d’explorer des approches similaires dans d’autres langages comme Rust
1 commentaires
Avis Hacker News
Cette implémentation s’appuie sur des travaux récents autour du « heartbeat scheduling » et répartit le coût de création du parallélisme afin d’obtenir un contrôle dynamique automatique de la granularité
Je n’ai pas lu les détails du code, mais « sub-nanosecond overhead » est trompeur et relève du marketing
Je ne connais pas bien ce domaine, mais le modèle de concurrence présenté me plaît
C’est un travail de recherche intéressant, avec en plus du code une bonne argumentation et une documentation bien écrite
Liste des limites du projet :
D’après l’explication, cette implémentation utilise l’attente active pour permettre aux workers d’atteindre une latence de l’ordre de la nanoseconde
Je me demande s’il existe un moyen plus rapide pour qu’un producteur de tâches réveille un consommateur sans attente active
C’est intéressant et relié à d’excellents articles
L’ordonnancement coopératif est à la base de nombreux patterns avec d’excellentes métriques
Excellent
Voir aussi le README sur les benchmarks :