Fast-registrarse en una especie de bytes?

Question

Dado un registro de 4 bytes (o 16 para SIMD), no tiene que ser una manera eficaz para ordenar los bytes en-registro con unas pocas instrucciones.

Gracias de antemano.

Answer 1

clasificación de la red para N = el número de bytes que le interesan (4 o 16). Convertir a que una secuencia de instrucciones de comparación y de intercambio. (Para N = 16 que va a ser más que 'unos pocos', sin embargo.)

Answer 2

encontrado! Está en el documento de 2007 "Uso de los Registros y del SIMD instrucciones para activar la instrucción a nivel de paralelismo en algoritmos de ordenación" por Furtak, Amaral, y Niewiadomski. Sección 4.

Utiliza 4 registros SSE, tiene 12 pasos, y se ejecuta en 19 instrucciones incluyendo la carga y almacenar.

El mismo papel tiene un excelente trabajo en la fabricación de redes de ordenación de forma dinámica con SIMD.

Answer 3

Para acelerar la clasificación de cadenas, terminé embalaje 7 bytes por doble y clasificación (ranking) una matriz de 16 dobles en SSE2, usando una especie bitónica para crear dos carreras de 8, y una combinación binaria de fusionar las dos carreras . Se puede ver la primera parte aquí http://mischasan.wordpress.com/2011/07/29/okay-one-more-poke-at-sse2-sorting-doubles/ (ASM) y aquí http://mischasan.wordpress.com/2011/09/ 02 / update-en-bitónica-SSE2-clase-de-16-dobles / (C), y la etapa de combinación bitónica (si quieres ir todo el camino SSE) aquí: http://mischasan.wordpress.com/ 2012/11/04 / SSE2-par-impar-merge-la-última-paso-en-clasificación / . He sustituido el tipo de inserción en la parte inferior de qsort con este tipo, y es aproximadamente 5 veces más rápido que qsort recta. HTH

No había visto el documento UofA; la lógica bitónica es de la vieja escuela (CTM) de programación GPGPU.

Lo siento por las cadenas de enlace incrustado; No sé cómo añadir hacer clic en enlaces en los comentarios Stackoverflow.

Answer 4

Todos los algoritmos de ordenación requerirá "intercambiar" los valores de un lugar a otro. Ya que estamos hablando de un registro de la CPU literal, eso significa que cualquier tipo necesitarían otro registro para su uso como un lugar temporal para almacenar los bytes se intercambian.

nunca he visto un chip con un sistema incorporado en el método para la clasificación de bytes dentro de un registro. No digo que no se ha hecho, pero no puedo pensar en muchos usos para tal instrucción.