Rapide enregistrer en sorte d'octets?
https://stackoverflow.com/questions/1580686
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianQuestion
Compte tenu un registre de 4 octets (ou 16 pour SIMD), il doit y avoir un moyen efficace pour trier les octets registre avec quelques instructions.
Merci d'avance.
La solution
Recherchez un efficace tri réseau N = le nombre d'octets que vous aimez (4 ou 16). Convertir en une séquence de comparaison et des instructions échange. (Pour N = 16 ce sera plus que 'quelques', bien que.)
Autres conseils
Je l'ai trouvé! Il est dans le document de 2007 « Utilisation SIMD registres et Instructions pour activer l'instruction niveau Parallélisme dans le tri des algorithmes » par Furtak, Amaral et Niewiadomski. Section 4.
Il utilise 4 registres SSE, a 12 étapes, et fonctionne dans 19 instructions, y compris la charge et à stocker.
Le même papier a un excellent travail à rendre dynamique les réseaux de tri avec SIMD.
Pour accélérer le tri des chaînes, j'ai fini par emballage 7 octets par double et de tri (classement) un tableau de 16 doubles en SSE2, en utilisant sorte Bitonic pour créer deux séries de 8 et une fusion binaire pour fusionner les deux pistes . Vous pouvez voir la première partie ici http://mischasan.wordpress.com/2011/07/29/okay-one-more-poke-at-sse2-sorting-doubles/ (asm) et ici http://mischasan.wordpress.com/2011/09/ 02 / update-sur-Bitonic SSE2 tri-of-16-doubles ici / (C), et l'étape de fusion Bitonic (si vous voulez aller tout le chemin SSE): http://mischasan.wordpress.com/ 2012/11 / 04 / SSE2-impair même de fusion-la-dernière étape dans le tri / . Je l'ai remplacé le genre d'insertion au bas de qsort avec ce genre, et il est à peu près 5 fois plus vite que qsort droite. HTH
Je ne l'avais pas vu le papier UofA; la logique Bitonic est de la vieille école (CTM) programmation GPGPU.
Désolé sur les chaînes de liens intégrés; Je ne sais pas comment ajouter des liens cliquables dans les commentaires StackOverflow.
Tous les algorithmes de tri nécessitent « échange » valeurs d'un endroit à l'autre. Puisque vous parlez d'un registre CPU littéral, cela signifie que toute sorte aurait besoin d'un autre registre à utiliser comme lieu temporaire pour contenir les octets étant permutées.
Je ne l'ai jamais vu une puce avec une méthode intégrée pour le tri octets dans un registre. Ne pas dire qu'il n'a pas été fait, mais je ne peux pas penser à de nombreuses utilisations pour une telle instruction.
