Un algorithme de tri est un algorithme qui met des éléments d’une liste dans un certain ordre. Les ordres plus utilisées sont l’ordre numérique et l’ordre lexicographique. Un tri efficace est importante pour l’optimisation de l’utilisation d’autres algorithmes (par exemple des algorithmes de recherche et fusion) qui nécessitent des listes triées pour fonctionner correctement ; Il est aussi souvent utile canonicalisation des données et de produire la sortie lisible par l’homme. Plus formellement, la sortie doit satisfaire à deux conditions :
1. la production est en non décroissante (chaque élément n’est pas plus petit que l’élément précédent selon l’ordre total souhaité) ;
2. le résultat est une permutation (l’ordre) de l’entrée.
-Tri est l’une des fonctions clés
nécessaire pour de nombreuses applications telles que des décodeurs pour les communications numériques, traitement numérique du signal, VLSI CAD etc.. En conséquence, il y a un intérêt énorme à accélérer de tri dans le logiciel comme matériel.
-Le temps pris dans le tri dépend de nombre de mots dans le cas où des algorithmes logiciels l’amélioration que nous essayons de faire dans ce projet est de rendre les temps dépendant du nombre de bits par mot k et non le nombre de mots
Énoncé du problème :
Trier les algorithmes de tri traditionnels comme bulle, tri d’insertion, Tri par fusion et beaucoup plus ont un scénario de référence qui exige l’échange de deux éléments à la fois. Même en utilisant une combinaison de deux algorithmes de tri telles que l’utilisation de tri rapide et tri par fusion ensemble pour trier un tableau de nombres, le scénario de référence implique toujours la permutation des éléments de données seulement deux à un moment donné. Ainsi la motivation à la découverte des algorithmes de tri mis en œuvre par l’intermédiaire de matériel provient du fait que par le biais de matériel, on est en mesure de mieux exploiter le parallélisme, ce tri nombreux numéros simultanément.
Parallélisme non seulement assure l’accès concurrentiel, mais vise également à réduire la complexité des algorithmes. D'où le problème à portée de main est de concevoir un nouvel algorithme de tri et l’implémenter dans le matériel tel qu’il extrait le parallélisme.