Vectores SoA en SPU

8

He leído mucho sobre los beneficios de organizar los datos en 'Structs of Arrays' (SoA) en lugar del típico 'Array of Structs' (AoS) para obtener un mejor rendimiento al usar instrucciones SIMD . Si bien el 'por qué' tiene mucho sentido para mí, no estoy seguro de cuánto hacer esto cuando trabajo con cosas como vectores.

Los propios vectores pueden considerarse como una estructura de una matriz de datos (de tamaño fijo), por lo que podría convertir una matriz de estos en una estructura de matrices X, Y y Z. A través de esto, puede trabajar en 4 vectores a la vez en lugar de uno a la vez.

Ahora, por la razón específica, estoy publicando esto en GameDev:

¿Tiene sentido trabajar con vectores en la SPU? Más específicamente, ¿tiene sentido para DMA múltiples matrices solo para un solo vector? ¿O sería mejor quedarse con DMA colocando la matriz de vectores y desenrollarlos en los diferentes componentes para trabajar?

Pude ver el beneficio de cortar el desenrollado (si lo hizo 'AoS'), pero parece que podría quedarse rápidamente sin canales DMA si tomara esta ruta y trabajara con múltiples conjuntos de vectores a la vez.

(Nota: todavía no hay experiencia profesional con Cell, pero he estado jugando en OtherOS por un tiempo)

Chris Waters
fuente

Respuestas:

5

Un enfoque es utilizar un enfoque AoSoA (léase: Array of Struct of Array) que es un híbrido de AoS y SoA. La idea es almacenar el valor de N structs de datos en un fragmento contiguo en forma de SoA, luego el siguiente valor de N structs en forma de SoA.

Su forma de AoS para 16 vectores (etiquetados 0,1,2 ... F), con una granularidad de 4 estructuras es:

000111222333444555666777888999AAABBBCCCDDDEEEFFF
XYZXYZXYZXYZXYZXYZXYZXYZXYZXYZXYZXYZXYZXYZXYZXYZ

para SoA, esto es:

0123456789ABCDEF
XXXXXXXXXXXXXXXX

0123456789ABCDEF
YYYYYYYYYYYYYYYY

0123456789ABCDEF
ZZZZZZZZZZZZZZZZ

para AoSoA, esto se convierte en:

01230123012345674567456789AB89AB89ABCDEFCDEFCDEF
XXXXYYYYZZZZXXXXYYYYZZZZXXXXYYYYZZZZXXXXYYYYZZZZ

El enfoque de AoSoA tiene los siguientes beneficios de AoS:

  • Solo se requiere una única transferencia de DMA para transferir una porción de estructuras a la memoria local de SPU.
  • Las estructuras todavía tienen la posibilidad de que todos los datos se ajusten en una línea de caché.
  • La captación previa de bloques sigue siendo muy fácil.

El enfoque AoSoA también tiene estos beneficios de la forma SoA:

  • Puede cargar datos desde la memoria local de la SPU directamente en registros vectoriales de 128 bits sin tener que mezclar sus datos.
  • Todavía puede operar en 4 estructuras a la vez.
  • Puede utilizar completamente la SIMD de su procesador de vectores si no hay ramificación básica (es decir, no hay carriles no utilizados en su aritmética de vectores)

El enfoque AoSoA todavía tiene algunos de estos inconvenientes de la forma SoA:

  • La gestión de objetos debe hacerse con granularidad vertiginosa.
  • las escrituras de acceso aleatorio de una estructura completa ahora necesitan tocar la memoria dispersa.
  • (Esto puede resultar sin problemas dependiendo de cómo organice / administre sus estructuras y su vida útil)

Por cierto, estos conceptos de AoSoA se aplican muy bien a SSE / AVX / LRBni, así como a las GPU que pueden compararse con procesadores SIMD muy amplios, por ejemplo. 32/48/64 de ancho dependiendo del vendedor / arquitectura.

jpaver
fuente
No veo cómo esto ofrece alguna ventaja sobre no empacarlos por componente a menos que esté empacando datos no vectoriales que realmente usa como flotantes, aunque veo que su AoS excluye W, lo que no parecería muy accesible para la memoria, yo Supongo que en ese caso hay una victoria. También tenga en cuenta que las SPU no tienen líneas de caché, excepto para comunicarse con la memoria principal.
Kaj
2
1. Como con todas las cosas, su millaje puede variar dependiendo de sus datos / algoritmos / procesadores exactos. En casos de registro restringido, puede ser útil evitar la necesidad de 4 registros temporales antes de que pueda mezclar todos sus campos X en el mismo registro. Pero de nuevo, YMMV. 2. Mi respuesta fue más general porque los conceptos se transfieren bien dentro del campo de la programación paralela de datos; Consideraciones líneas de caché son más pertinentes para GPU / SSE, pero me sentí que debería mencionar a todos ellos el mismo :)
jpaver
1
¡Muy bien, estoy iluminado y aprenderé a criticar más sutilmente! Gracias por compartir su conocimiento: o)
Kaj
3

Las SPU son en realidad un caso especial interesante cuando se trata de vectorizar código. Las instrucciones se dividen en familias "aritméticas" y "cargar / almacenar", y las dos familias se ejecutan en tuberías separadas. La SPU puede emitir uno de cada tipo por ciclo.

Obviamente, el código matemático está fuertemente vinculado a las instrucciones matemáticas, por lo que, por lo general, los bucles matemáticos en SPU tendrán muchos ciclos abiertos en la tubería de carga / almacenamiento. Dado que las mezclas se producen en la tubería de carga / almacenamiento, a menudo tiene suficientes instrucciones de carga / almacenamiento gratuitas para mezclar el formulario xyzxyzxyzxyz en el formulario xxxxyyyyzzzz sin ningún tipo de sobrecarga.

Esta técnica se usa en Naughty Dog al menos; consulte sus presentaciones de ensamblaje de SPU ( parte 1 y parte 2 ) para obtener más detalles.

Desafortunadamente, el compilador a menudo no es lo suficientemente inteligente como para hacer esto automáticamente; si decide seguir esta ruta, deberá escribir el ensamblaje usted mismo o desenrollar sus bucles utilizando intrínsecos y verificar el ensamblador para asegurarse de que sea lo que desea. Por lo tanto, si está buscando escribir código multiplataforma general que funcione bien en SPU, es posible que desee utilizar SoA o AoSoA (como sugiere jpaver).

Charlie
fuente
Ah, estamos de acuerdo después de todo: o) Swizzle en la SPU si lo necesita, tiempo suficiente para hacerlo allí.
Kaj
1

Como con cualquier optimización, perfil! La legibilidad es lo primero, y solo debe sacrificarse cuando el perfil identifica un cuello de botella en particular y ha agotado todas sus opciones para ajustar el algoritmo de alto nivel (¡la forma más rápida de hacer el trabajo es no tener que hacer el trabajo!) Siempre debe volver a crear un perfil siguiendo cualquier optimización de bajo nivel para confirmar que realmente ha hecho las cosas más rápido en lugar de lo contrario, especialmente con tuberías tan extravagantes como las de Cell.

Las técnicas que utilice dependerán de los detalles del cuello de botella. En general, cuando se trabaja con tipos de vectores, un componente de vector que ignora en un resultado representa el desperdicio de trabajo. Cambiar SoA / AoS no tiene sentido a menos que le permita hacer un trabajo más útil al llenar dichos componentes no utilizados (por ejemplo, un producto de punto en la PPU de PS3 frente a cuatro productos de punto en paralelo en la misma cantidad de tiempo). Para responder a su pregunta, ¡pasar tiempo barajando componentes solo para realizar una operación en un solo vector me parece una pesadilla!

La otra cara de las SPU es que la mayor parte del costo de las pequeñas transferencias DMA está en configuración; cualquier cosa menor a 128 bytes tomará la misma cantidad de ciclos para transferir, y cualquier cosa menor a aproximadamente un kilobyte solo unos pocos ciclos más. Por lo tanto, no se preocupe si DMA envía más datos de los estrictamente necesarios; reducir la cantidad de transferencias secuenciales de DMA activadas y realizar el trabajo mientras se realizan transferencias de DMA, y por lo tanto desplegar prólogos y epílogos de bucle para formar tuberías de software, es clave para un buen rendimiento de SPU, y es más fácil lidiar con los casos de esquina obteniendo datos adicionales / descartar resultados parcialmente calculados que saltar a través de aros para tratar de organizar la cantidad exacta de datos que es necesario leer y procesar.

sombra de Luna
fuente
Si terminas desempacándolos, según el enfoque de AOSAO, al menos extrae múltiples vectores a la vez. Además, querrá incorporar un lote y, mientras procesa, extraerá el siguiente lote. Mientras envía el primer lote, procesa el segundo y extrae el tercero. De esa manera escondes tanta latencia como puedas.
Kaj
0

No, eso no tendría mucho sentido en general, ya que la mayoría de los códigos de operación de vectores operan en un vector en su conjunto y no en componentes separados. Por lo tanto, ya puede multiplicar un vector en 1 instrucción, mientras que al dividir los componentes separados gastaría 4 instrucciones en él. Entonces, dado que básicamente realiza muchas operaciones en general en parte de una estructura, es mejor empaquetarlas en una matriz, pero casi nunca hace cosas solo en un componente de un vector, o es muy diferente en cada componente, por lo que los divide fuera no funcionaría.
Por supuesto, si encuentra una situación en la que tiene que hacer algo solo con los componentes (digamos) x de los vectores, podría funcionar, sin embargo, la penalización de devolver todo cuando necesita el vector real no sería barato, por lo que podría me pregunto si no debería usar vectores para comenzar, sino solo una serie de flotantes que permiten que los códigos de operación de vectores hagan sus cálculos específicos.

Kaj
fuente
2
Te estás perdiendo el punto de SoA para las matemáticas vectoriales. Rara vez tiene un solo objeto en el que está trabajando: en la práctica, está iterando una matriz y haciendo lo mismo con muchos objetos. Considere hacer productos de 4 puntos. Si está almacenando vectores como AoS en forma xyz0, tomar el punto de dos vectores requiere multiplicar-barajar-agregar-mezclar-agregar - 5 instrucciones. Hacer productos de 4 puntos requiere 20 instrucciones. Por otro lado, si tiene 8 vectores almacenados de modo SoA (xxxx, aaaa, zzzz, xxxx, aaaa, zzzz) puede hacer 4 productos de puntos con solo 3 instrucciones (mul, madd, madd), eso es 6 veces más rápido.
Charlie
Punto justo. Sin embargo, dos observaciones. Siempre mantendría el W presente para no necesitar 20 instrucciones, en segundo lugar, la mayor parte de la sobrecarga restante puede estar oculta en la latencia de otras instrucciones: su circuito cerrado sufriría graves paradas en la tubería, ¿no? Hacer las 6 veces es una optimización teórica. Entonces, si bien sí, desea agrupar sus operaciones, casi nunca necesitará hacer un lote rápido de productos de punto sin nada más que hacer en dichos datos. El costo de deswizzling / scatter en el lado de PPU sería un gran sacrificio para mí.
Kaj
Gruño, estoy corregido: en SPU necesitaría 20 si lo hiciera ingenuamente (pero barajaría en su lugar). Es una de las cosas en las que terminé haciendo muchas olas para que sea óptimo. 360 tiene un buen punto intrínseco (pero carece de la increíble manipulación de bits).
Kaj
Sí, ahora que lo pienso, si estás tratando de hacer "productos de 4 puntos", puedes hacer algo mejor que 20 instrucciones porque puedes combinar algunas de las adiciones posteriores. Pero tener sus vectores en registros como xxxx, aaaa, zzzz, ya sea que se haya swizzled o almacenado como SoA, elimina esos shuffle por completo. De todos modos, tiene razón en que SoA hace que el código de lógica ramificada sea más lento, pero diría que la solución en muchos casos como ese es agrupar sus datos y refactorizar la lógica ramificada en agradables bucles planos.
Charlie
Convenido. Estoy bastante seguro de que si reviso mi antiguo código SPU (no puedo, compañía anterior) hay casos en los que lo moví al formato xxxxyyyyzzzz para la optimización sin darme cuenta específicamente. Sin embargo, nunca lo ofrecí desde el PPU en ese formato. Eso sí, OP lo que contemplando hacer x, y, z por separado. Eso definitivamente no funcionaría para mí. También (como lo hice) preferiría mezclarme localmente ya que no todo funciona mejor en formato xxxxyyyyzzzz. Tengo que elegir tus batallas, supongo. La optimización para SPU es una maravilla y te sientes terriblemente inteligente una vez que tienes esa solución apretada: o)
Kaj