Parallel Cascaded Recursive Filtering on Multi-Core CPUs and GPUs

Imaginez que vous essayez de nettoyer l'enregistrement bruyant de votre chanson préférée, ou peut-être que vous construisez un robot qui doit réagir instantanément à son environnement. Dans les deux cas, vous avez besoin d'un « filtre » numérique pour séparer les bons sons des mauvais. Les outils les plus puissants pour cette tâche sont appelés filtres récursifs. Considérez-les comme une chambre d'écho magique : pour déterminer quel sera le son suivant, le filtre regarde le son actuel et les sons qu'il a produits un instant auparavant. Ce « regard en arrière » les rend incroyablement efficaces, utilisant très peu de puissance informatique pour accomplir des tâches complexes. Cependant, il y a un piège : comme chaque nouveau son dépend du précédent, le filtre doit travailler étape par étape, comme une seule personne marchant dans un long couloir. Cela crée un goulot d'étranglement, ralentissant tout lorsqu'on doit traiter des quantités massives de données, comme de la vidéo haute définition ou de la radio en temps réel.

Pendant des décennies, les scientifiques ont essayé d'accélérer cela en utilisant davantage d'ordinateurs pour aider. Le défi est que si vous répartissez le travail entre plusieurs ordinateurs, ils s'embrouillent car ils attendent tous que la personne précédente ait terminé son étape avant de pouvoir commencer la leur. C'est comme une course de relais où les coureurs sont coincés en attendant le témoin, même s'ils sont sur des pistes différentes. Cet article s'attaque précisément à ce problème. Il utilise une astuce mathématique ingénieuse qui a déjà fait ses preuves sur une puce informatique unique et ultra-rapide, et l'adapte pour fonctionner sur des ordinateurs modernes à plusieurs cœurs et sur de puissantes cartes graphiques (GPU). Les auteurs ont trouvé un moyen de permettre à ces ordinateurs de travailler ensemble sans attendre, transformant une file indienne lente en une autoroute à plusieurs voies à grande vitesse, atteignant des vitesses auparavant jugées impossibles pour ce type de calcul.

Le problème de la course de relais et l'astuce magique

Pour comprendre la percée, regardons comment ces filtres fonctionnent habituellement. Imaginez une longue file de personnes transmettant un message le long d'une chaîne. Chaque personne doit attendre que la personne devant elle lui chuchote le message avant de pouvoir ajouter sa propre partie et le transmettre à son tour. C'est la partie « récursive ». Si vous avez une longue chaîne, le message met du temps à arriver au bout.

Les auteurs de cet article avaient déjà trouvé un moyen de diviser une longue chaîne en blocs plus petits qui pourraient être traités plus rapidement. Mais lorsqu'ils ont essayé de confier ces blocs à de nombreux ordinateurs simultanément (comme une équipe de travailleurs), un nouveau problème est apparu : la fin d'un bloc est le point de départ du suivant. Si vous donnez le Bloc A au Travailleur 1 et le Bloc B au Travailleur 2, le Travailleur 2 est bloqué en attendant que le Travailleur 1 finisse le Bloc A avant de pouvoir commencer le Bloc B. L'équipe finit par travailler un par un malgré tout, ce qui annule l'intérêt d'avoir une équipe.

La découverte principale de l'article est une « astuce magique » mathématique appelée superposition. Au lieu d'attendre la réponse du bloc précédent, les travailleurs devinent quelle serait la réponse s'ils commençaient avec zéro (une supposition d'« état zéro »). Ils effectuent ce calcul immédiatement. Ensuite, ils attendent que le nombre de départ réel du travailleur précédent arrive. Une fois arrivé, ils ajoutent simplement une petite « correction » à leur supposition. C'est comme un chef qui commence à cuisiner une soupe en se basant sur une recette, en supposant qu'il n'a pas encore d'ingrédients. Quand le camion de livraison finit par déposer les vrais légumes, le chef n'a plus qu'à les ajouter et à remuer. La soupe est prête presque instantanément parce que le travail difficile de la cuisson était déjà fait en parallèle.

Deux manières différentes de courir la course

L'article montre que cette astuce magique peut être utilisée de deux manières très différentes, selon ce que vous essayez de faire.

1. Le flux en temps réel (La chaîne de montage)
Si vous traitez des données en direct, comme une émission de radio, vous ne pouvez pas attendre que tout le lot soit terminé avant de jouer la seconde suivante de l'audio. Vous avez besoin que les données sortent exactement dans l'ordre où elles sont entrées (Premier entré, Premier sorti).

• La solution : Les auteurs ont construit un « pipeline à front d'onde » pour les processeurs multi-cœurs. Imaginez une chaîne de montage où différents travailleurs manipulent différentes étapes de la même chanson en même temps. Le Travailleur 1 nettoie la basse, le Travailleur 2 répare les voix, et le Travailleur 3 ajoute l'écho. Dès que le Travailleur 1 termine un bloc, il le passe au Travailur 2, qui le passe au Travailleur 3.
• Le résultat : Sur un ordinateur moderne doté de six cœurs puissants, cette méthode a atteint une vitesse de 2,4 Gigasamples par seconde pour un filtre complexe de 16e ordre. C'est presque 4 fois plus rapide qu'en utilisant un seul cœur. Curieusement, ils ont constaté que l'ajout de cœurs d'« efficacité » plus lents au mélange ralentissait la ligne, prounant que pour cette tâche spécifique, quelques travailleurs rapides valent mieux que beaucoup de travailleurs lents.

2. Le traitement par lots (L'usine)
Si vous traitez un énorme fichier de données enregistrées (comme un film ou une base de données), l'ordre vous importe moins que la vitesse brute. Vous pouvez traiter l'ensemble du fichier d'un coup.

• La solution : Ils ont utilisé de puissants processeurs graphiques (GPU), qui possèdent des milliers de minuscules travailleurs. Ils ont utilisé une technique appelée découplage de regard en arrière (decoupled lookback). Imaginez une usine où chaque travailleur calcule sa partie du produit immédiatement. Si un travailleur a besoin d'une pièce provenant de la station précédente, il ne s'arrête pas ; il consulte simplement un « tableau de bord » pour voir si la station précédente a terminé. Si c'est le cas, il récupère la pièce. Sinon, il continue de travailler sur d'autres choses en attendant que ce soit prêt.
• Le résultat : Cette approche a été incroyablement rapide. Sur une carte graphique NVIDIA RTX 3060, le système a atteint 38,2 Gigasamples par seconde pour une seule section de filtre. Cela représente 85 % de la vitesse absolue maximale que le matériel est théoriquement capable d'atteindre (le plafond de la bande passante mémoire).

Pourquoi cela importe et ce que cela bat

Les auteurs n'ont pas seulement rendu les choses plus rapides ; ils ont prouvé que leur méthode est plus fiable que les anciennes méthodes.

• L'échec de la « forme directe » : Il existe une méthode plus ancienne appelée « forme directe » qui tente de faire le calcul en une seule étape géante. L'article montre que pour des filtres complexes (comme un filtre de 16e ordre), cette ancienne méthode échoue. Les nombres deviennent si désordonnés que l'ordinateur commence à produire des résultats erronés ou plante. La nouvelle méthode « en cascade » utilisée dans cet article reste précise, même à ces niveaux élevés.
• Battre la concurrence : Ils ont comparé leur nouveau code GPU aux moteurs de filtrage parallèles les plus puissants existants. Leur méthode était plus rapide pour chaque ordre de filtre testé.
• Le coût de la vitesse : L'article a également mesuré soigneusement le « coût » de cette vitesse. Ils ont découvert que sur les puces plus récentes et plus rapides (comme la RTX 3060), les « barrières » (les vérifications que font les travailleurs pour voir s'ils peuvent procéder) sont peu coûteuses, ils peuvent donc utiliser des méthodes plus complexes et plus rapides. Sur les puces plus anciennes, ces vérifications sont coûteuses, ils doivent donc utiliser des méthodes plus simples. Cela aide les ingénieurs à savoir exactement comment ajuster leur logiciel pour différents matériels.

L'essentiel

Cet article transforme un problème mathématique séquentiel difficile en une fête parallèle. En utilisant une stratégie intelligente de « supposition et de correction », ils ont permis aux ordinateurs de travailler ensemble sans rester bloqués à s'attendre les uns les autres.

• Pour le streaming en direct, ils ont construit un pipeline qui est 3,95 fois plus rapide sur un ordinateur standard.
• Pour le traitement par lots, ils ont construit un moteur GPU qui tourne à 38,2 Gigasamples par seconde, ce qui est un bond énorme.
• Crucialement, ils ont prouvé que cette méthode ne fonctionne pas seulement plus vite ; elle fonctionne mieux, restant précise là où les anciennes méthodes échouent.

Les auteurs ont publié leur code sous forme de bibliothèque open-source, ce qui signifie que n'importe qui peut désormais utiliser ces filtres ultra-rapides pour créer de meilleurs outils audio, des vidéos plus claires et des robots plus intelligents. Ils ont effectivement transformé un goulot d'étranglement « séquentiel » en une autoroute « parallèle », montant que même les problèmes mathématiques les plus tenaces peuvent être résolus en laissant une équipe d'ordinateurs travailler ensemble en synchronisation.