Réseau de tri

En informatique , les réseaux comparateurs sont des dispositifs abstraits constitués d'un nombre fixe de « fils », transportant des valeurs, et de modules comparateurs qui connectent des paires de fils, échangeant les valeurs sur les fils si elles ne sont pas dans un ordre souhaité. De tels réseaux sont généralement conçus pour effectuer un tri sur un nombre fixe de valeurs, auquel cas ils sont appelés réseaux de tri .

Les réseaux de tri diffèrent des tris par comparaison généraux en ce qu'ils ne sont pas capables de gérer des entrées arbitrairement grandes et en ce que leur séquence de comparaisons est définie à l'avance, quel que soit le résultat des comparaisons précédentes. Afin de trier de plus grandes quantités d'entrées, de nouveaux réseaux de tri doivent être construits. Cette indépendance des séquences de comparaison est utile pour l'exécution parallèle et pour l'implémentation matérielle . Malgré la simplicité des réseaux de tri, leur théorie est étonnamment profonde et complexe. Les réseaux de tri ont été étudiés pour la première fois vers 1954 par Armstrong, Nelson et O'Connor, qui ont ensuite breveté l'idée.

Les réseaux de tri peuvent être implémentés soit au niveau matériel , soit au niveau logiciel . Donald Knuth décrit comment les comparateurs pour les entiers binaires peuvent être implémentés sous forme de dispositifs électroniques simples à trois états. Batcher , en 1968, a suggéré de les utiliser pour construire des réseaux de commutation pour le matériel informatique, remplaçant à la fois les bus et les commutateurs crossbar plus rapides, mais plus coûteux . Depuis les années 2000, les réseaux de tri (en particulier le tri par fusion bitonique ) sont utilisés par la communauté GPGPU pour construire des algorithmes de tri à exécuter sur des unités de traitement graphique .

Un réseau de tri se compose de deux types d'éléments : les comparateurs et les fils. Les fils sont considérés comme allant de gauche à droite, transportant des valeurs (une par fil) qui traversent le réseau en même temps. Chaque comparateur relie deux fils. Lorsqu'une paire de valeurs, voyageant à travers une paire de fils, rencontre un comparateur, le comparateur échange les valeurs si et seulement si la valeur du fil supérieur est supérieure ou égale à la valeur du fil inférieur.

Dans une formule, si le fil supérieur porte x et le fil inférieur porte y , alors après avoir atteint un comparateur, les fils portent et , respectivement, donc la paire de valeurs est triée. Un réseau de fils et de comparateurs qui triera correctement toutes les entrées possibles dans l'ordre croissant est appelé un réseau de tri ou un hub Kruskal. En reflétant le réseau, il est également possible de trier toutes les entrées dans l'ordre décroissant.

Le fonctionnement complet d'un réseau de tri simple est illustré ci-dessous. Il est évident que ce réseau de tri triera correctement les entrées ; notez que les quatre premiers comparateurs « feront couler » la plus grande valeur vers le bas et « feront flotter » la plus petite valeur vers le haut. Le dernier comparateur trie les deux fils du milieu.

L'efficacité d'un réseau de tri peut être mesurée par sa taille totale, c'est-à-dire le nombre de comparateurs dans le réseau, ou par sa profondeur , définie (de manière informelle) comme le plus grand nombre de comparateurs que toute valeur d'entrée peut rencontrer sur son chemin à travers le réseau. En notant que les réseaux de tri peuvent effectuer certaines comparaisons en parallèle (représentées dans la notation graphique par des comparateurs qui se trouvent sur la même ligne verticale), et en supposant que toutes les comparaisons prennent un temps unitaire, on peut voir que la profondeur du réseau est égale au nombre d'étapes de temps nécessaires pour l'exécuter.

Nous pouvons facilement construire un réseau de n'importe quelle taille de manière récursive en utilisant les principes d'insertion et de sélection. En supposant que nous ayons un réseau de tri de taille n , nous pouvons construire un réseau de taille n + 1 en « insérant » un nombre supplémentaire dans le sous-réseau déjà trié (en utilisant le principe sous-jacent au tri par insertion ). Nous pouvons également accomplir la même chose en « sélectionnant » d'abord la valeur la plus basse parmi les entrées, puis en triant les valeurs restantes de manière récursive (en utilisant le principe sous-jacent au tri à bulles ).

La structure de ces deux réseaux de tri est très similaire. Une construction des deux variantes différentes, qui regroupe des comparateurs pouvant être exécutés simultanément, montre qu'en fait, ils sont identiques.

Le réseau d'insertion (ou de manière équivalente, le réseau à bulles) a une profondeur de 2 n - 3 , où n est le nombre de valeurs. C'est mieux que le temps O ( n log n ) nécessaire aux machines à accès aléatoire , mais il s'avère qu'il existe des réseaux de tri beaucoup plus efficaces avec une profondeur de seulement O (log ² n ) , comme décrit ci-dessous.

Bien qu'il soit facile de prouver la validité de certains réseaux de tri (comme le trieur à insertion/bulle), ce n'est pas toujours aussi simple. Il existe n ! permutations de nombres dans un réseau à n fils, et les tester toutes prendrait beaucoup de temps, surtout lorsque n est grand. Le nombre de cas de test peut être réduit de manière significative, à 2 ⁿ , en utilisant le principe dit zéro-un. Bien que toujours exponentiel, ce nombre est inférieur à n ! pour tout n ≥ 4 , et la différence augmente assez rapidement avec l'augmentation de n .

Le principe zéro-un stipule que si un réseau de tri peut trier correctement toutes les séquences 2 ⁿ de zéros et de uns, il est également valable pour des entrées ordonnées arbitrairement. Cela réduit non seulement considérablement le nombre de tests nécessaires pour vérifier la validité d'un réseau, mais s'avère également très utile pour créer de nombreuses constructions de réseaux de tri.

Le principe peut être démontré en observant d'abord le fait suivant à propos des comparateurs : lorsqu'une fonction f monotone croissante est appliquée aux entrées, c'est-à-dire que x et y sont remplacés par f ( x ) et f ( y ) , alors le comparateur produit min( f ( x ), f ( y )) = f (min( x , y )) et max( f ( x ), f ( y )) = f (max( x , y )) . Par induction sur la profondeur du réseau, ce résultat peut être étendu à un lemme affirmant que si le réseau transforme la séquence a ₁ , ..., a _n en b ₁ , ..., b _n , il transformera f ( a ₁ ), ..., f ( a _n ) en f ( b ₁ ), ..., f ( b _n ) . Supposons qu'une entrée a ₁ , ..., a _n contienne deux éléments a _i < a _j , et que le réseau les échange incorrectement dans la sortie. Ensuite, il triera également de manière incorrecte f ( a ₁ ), ..., f ( a _n ) pour la fonction

a_{i}\\0\ &{\mbox{sinon.}}\end{cases}}}" data-src="https://wikimedia.org/api/rest_v1/media/math/render/svg/a5f3d2f660d246c38763227f47a6025cac83361f">

Cette fonction est monotone, nous avons donc le principe zéro-un comme contraposé .

Il existe différents algorithmes permettant de construire des réseaux de tri de profondeur O (log ² n ) (donc de taille O ( n log ² n ) ) tels que le tri par fusion impair-pair par lots , le tri bitonique , le tri par coquille et le réseau de tri par paires . Ces réseaux sont souvent utilisés dans la pratique.

Il est également possible de construire des réseaux de profondeur O (log n ) (donc de taille O ( n log n ) ) en utilisant une construction appelée réseau AKS , d'après ses découvreurs Ajtai , Komlós et Szemerédi . Bien qu'il s'agisse d'une découverte théorique importante, le réseau AKS a une application pratique très limitée en raison de la grande constante linéaire cachée par la notation Big-O . Ceux-ci sont en partie dus à la construction d'un graphe d'extension .

Une version simplifiée du réseau AKS a été décrite par Paterson en 1990, qui a noté que « les constantes obtenues pour la limite de profondeur empêchent toujours la construction d'avoir une valeur pratique ».

Une construction plus récente appelée réseau de tri en zigzag de taille O ( n log n ) a été découverte par Goodrich en 2014. Bien que sa taille soit bien plus petite que celle des réseaux AKS, sa profondeur O ( n log n ) le rend inadapté à une implémentation parallèle.

Pour un nombre fixe d'entrées n , des réseaux de tri optimaux peuvent être construits, avec une profondeur minimale (pour une exécution parallèle maximale) ou une taille minimale (nombre de comparateurs). Ces réseaux peuvent être utilisés pour augmenter les performances de réseaux de tri plus grands résultant des constructions récursives de Batcher, par exemple, en arrêtant la récursivité plus tôt et en insérant des réseaux optimaux comme cas de base. Le tableau suivant résume les résultats d'optimalité pour les petits réseaux pour lesquels la profondeur optimale est connue :

Pour les réseaux de plus grande taille, ni la profondeur ni la taille optimales ne sont actuellement connues. Les limites connues à ce jour sont fournies dans le tableau ci-dessous :

Les seize premiers réseaux optimaux en profondeur sont répertoriés dans Knuth's Art of Computer Programming , et ce depuis l'édition de 1973 ; cependant, alors que l'optimalité des huit premiers a été établie par Floyd et Knuth dans les années 1960, cette propriété n'a été prouvée pour les six derniers qu'en 2014 (les cas neuf et dix ayant été décidés en 1991 ).

Pour une à douze entrées, des réseaux de tri minimaux (c'est-à-dire optimaux en taille) sont connus, et pour des valeurs plus élevées, des bornes inférieures sur leurs tailles S ( n ) peuvent être dérivées de manière inductive en utilisant un lemme dû à Van Voorhis (p. 240) : S ( n ) ≥ S ( n − 1) + ⌈log ₂ n ⌉ . Les dix premiers réseaux optimaux sont connus depuis 1969, les huit premiers étant à nouveau connus comme optimaux depuis les travaux de Floyd et Knuth, mais l'optimalité des cas n = 9 et n = 10 n'a été résolue qu'en 2014. L'optimalité des plus petits réseaux de tri connus pour n = 11 et n = 12 a été résolue en 2020.

Certains travaux de conception de réseaux de tri optimaux ont été réalisés à l'aide d'algorithmes génétiques : D. Knuth mentionne que le plus petit réseau de tri connu pour n = 13 a été trouvé par Hugues Juillé en 1995 « en simulant un processus évolutif de sélection génétique » (p. 226), et que les réseaux de tri de profondeur minimale pour n = 9 et n = 11 ont été trouvés par Loren Schwiebert en 2001 « en utilisant des méthodes génétiques » (p. 229).

À moins que P=NP , le problème de tester si un réseau candidat est un réseau de tri risque de rester difficile pour les réseaux de grande taille, car le problème est co-NP -complet.

• Angel, O.; Holroyd, AE; Romik, D.; Virág, B. (2007). « Réseaux de tri aléatoire ». Progrès en mathématiques . 215 (2) : 839–868. arXiv : math/0609538 . doi : 10.1016/j.aim.2007.05.019 .