6
Dado un registro de 4 bytes (o 16 para SIMD), tiene que haber una forma eficiente de ordenar los bytes en el registro con unas pocas instrucciones.Tipo de bytes rápido de registro?
Gracias de antemano.
A
Respuesta
5
Busque un eficiente sorting network para N = la cantidad de bytes que le interesan (4 o 16). Convierta eso en una secuencia de instrucciones de comparación e intercambio. (Para N = 16 eso será más que 'unos pocos', sin embargo).
1
Todos los algoritmos de clasificación requieren valores de "intercambio" de un lugar a otro. Ya que está hablando de un registro de CPU literal, eso significa que cualquier tipo necesitaría otro registro para usar como lugar temporal para retener los bytes que se intercambian.
Nunca he visto un chip con un método incorporado para clasificar bytes dentro de un registro. No digo que no se haya hecho, pero no puedo pensar en muchos usos para tal instrucción.
+0
Quiero decir que ordenar los bytes en un registro, por supuesto, tienen que usar al menos otro registro. Perdón por el malentendido. – alecco
+0
En realidad, hay una manera de ordenar en registro usando CMPXCHG usando el registro eax y rotándolo, como me lo mostró un amigo que tiene bastante conocimiento en x86. Poco se gana con eso, pero es posible. También CMPXCHG es bastante lento. – alecco
+1
Todas las arquitecturas SIMD que he usado tienen tales instrucciones. –
7
¡Lo encontró! Está en el documento de 2007 "Uso de Registros e Instrucciones de SIMD para Habilitar el Paralelismo a Nivel de Instrucción en Algoritmos de Clasificación" por Furtak, Amaral y Niewiadomski. Sección 4.
Utiliza 4 registros SSE, tiene 12 pasos y se ejecuta en 19 instrucciones que incluyen carga y almacenamiento.
El mismo papel tiene un excelente trabajo en la creación dinámica de redes de clasificación con SIMD.
+1
Enlace a PDF: http://www.cs.ualberta.ca/~amaral/papers/furtak-spaa07.pdf – alecco
4
Para acelerar la clasificación de cadenas, terminé empaquetando 7 bytes por doble y clasificando (clasificando) una matriz de 16 dobles en SSE2, usando clasificación bitónica para crear dos ejecuciones de 8, y una fusión binaria para fusionar las dos carreras. 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-on-bitonic-sse2-sort-of-16-doubles/ (C), y el paso de combinación bitónico (si desea ir a SSE hasta el final) aquí: http://mischasan.wordpress.com/2012/11/04/sse2-odd-even-merge-the-last-step-in-sorting/. Reemplacé 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 directo. HTH
No había visto el papel de UofA; la lógica bitónica proviene de la programación GPGPU de la vieja escuela (CTM).
Disculpe las cadenas de enlace incrustadas; No sé cómo agregar enlaces clicables en comentarios stackoverflow.
Cuestiones relacionadas
- 1. Agregar bytes con tipo de conversión, Java
- 2. Tipo de arreglo de byte rápido in situ
- 3. Convertir tipo de datos 'largo' de matriz de bytes
- 4. Registro/registro rápido de datos en una hebra separada en C#
- 5. API de tipo RandomAccessFile para matriz de bytes en memoria?
- 6. La inicialización de un PL/SQL tipo de registro
- 7. Haskell sintaxis de registro y clases de tipo
- 8. Registro de tipo C++ en tiempo de compilación truco
- 9. ¿Tamaño de bytes personalizado?
- 10. asignación de matriz de bytes
- 11. C# cálculo de hash rápido
- 12. Tomcat parado sin ningún tipo de registro o cualquier pila
- 13. Cómo registro un tipo de archivo personalizado en iOS
- 14. ¿Cómo registro un convertidor de tipo personalizado en Spring?
- 15. ¿Cómo verifico el registro de git para una combinación de "avance rápido"?
- 16. ¿Qué tan rápido es un método de registro de log4net (depuración, información, etc.)?
- 17. el tipo bytes en Python 2.7 y PEP-358
- 18. Como IPV6 necesita 128 bits (16 bytes), ¿por qué en postgres el tipo de datos CIDR tiene un almacenamiento de 24 bytes (8.1) y 19 bytes (9.1)?
- 19. qué tipo de identificación de registro de base de datos usar: ¿largo o guid?
- 20. Generador Aleatorio Rápido
- 21. Int matriz de bytes a
- 22. Usando Delphi, no se puede usar el tipo anonymus como tipo de registro?
- 23. Eliminando los primeros 16 bytes de una matriz de bytes
- 24. ¿Cuál es un buen tamaño (en bytes) para un archivo de registro?
- 25. ¿Por qué no hay un registro que contiene los bytes más altos de EAX?
- 26. representación de bytes en BINARY_CHECKSUM()?
- 27. ¿sizeof devuelve la cantidad de bytes o el número de octetos de un tipo en C?
- 28. Por curiosidad: ¿por qué las API de registro no implementan los métodos de registro de tipo printf()?
- 29. ¿Por qué los enteros procesan más rápido que los bytes en NDS?
- 30. Almacenamiento de matriz de bytes Mysql
Gracias. Estoy buscando una solución eficiente de asm. Oh, tenga en cuenta que dije unas "pocas instrucciones" y no unos "pocos ciclos";) – alecco
Ah, veo que el documento con el que se vincula toma exactamente este enfoque, utilizando instrucciones SSE2. Guay. –
Sí, no quería ser demasiado prolijo, ya que esperaba algún tipo de truco de magia con asm. De hecho, estaba buscando esta lectura "Implementación eficiente de la ordenación en la arquitectura de CPU SIMD de núcleos múltiples" (Chhugani, .. 2008), pero me frustraron las instrucciones para el algoritmo: 1) a) Realizar la clasificación In-Register para obtener secuencias ordenadas de longitud K. Supongo que para los investigadores de Intel es un procedimiento "duh", ¡pero no para mí! (Todavía no estoy seguro de que hagan todo el procedimiento de instrucción 17-19 para ordenar un registro.) [Nota: lo siento, no lo voté al alza por falta de karma] – alecco