L'algorithme d'ordonnancement Hourglass est un algorithme de tri parallèle innovant conçu pour trier efficacement de grandes ensembles de données avec des entrées parallèles et des sorties séquentielles. Il atteint une latence de log(n) pour la sortie du premier élément, avec un temps total de tri de n + log(n). Cet algorithme est particulièrement utile pour les applications nécessitant un tri rapide de grandes ensembles de données, comme le décodage LDPC quantique.
L'algorithme d'ordonnancement Hourglass est basé sur une structure arborescente de comparateurs, chaque nœud ayant deux registres de sortie pour éviter l'effet de "bubbling" qui peut se produire dans les algorithmes de tri traditionnels. Cela permet à l'algorithme de maintenir une trajectoire critique constante par rapport à la taille de l'entrée, résultant en une conception très évolutive.
L'algorithme a été mis en œuvre sur un FPGA et intégré avec succès dans une implémentation BP-OSD (Propagation de la Croyance - Décodeur de Statistiques Ordonnées) pour le codage LDPC quantique. Cette implémentation démontre les capacités de l'algorithme dans des applications réelles, telles que le décodage en temps réel des codes de correction des erreurs.
Les fonctionnalités clés de l'algorithme d'ordonnancement Hourglass incluent :
- Complexité matérielle de O(n)
- Latence de log(n) pour la sortie du premier élément
- Temps total de tri de n + log(n)
- Conception évolutive avec trajectoire critique constante
- Efficacité pour le tri de grandes ensembles de données avec entrées parallèles et sorties séquentielles
L'algorithme d'ordonnancement Hourglass représente une avancée significative dans les algorithmes de tri parallèle, offrant une solution extrêmement efficace et évolutive pour les applications nécessitant un tri rapide de grandes ensembles de données.