Hispanopedia Wiki
Articulo de referencia

SWAR

SIMD dentro de un registro ( SWAR ), también conocido como "SIMD empaquetado" [ 1 ] , es una técnica para realizar operaciones paralelas en datos contenidos en un registro del p...

Hispanopedia WikiContenido en espanolLectura gratuita

SIMD dentro de un registro ( SWAR ), también conocido como "SIMD empaquetado" [ 1 ] , es una técnica para realizar operaciones paralelas en datos contenidos en un registro del procesador . SIMD significa instrucción única, datos múltiples .

Muchos procesadores modernos de propósito general cuentan con ciertas disposiciones para SIMD , en forma de un conjunto de registros e instrucciones para su uso. SWAR se refiere al uso de dichos registros e instrucciones, en contraposición al uso de motores de procesamiento especializados diseñados para optimizar las operaciones SIMD. También se refiere al uso de SIMD con registros e instrucciones de propósito general que no fueron diseñados para ello en su momento, mediante diversas técnicas de software innovadoras. [ 3 ]

Arquitecturas SWAR

Una arquitectura SWAR incluye instrucciones diseñadas explícitamente para realizar operaciones paralelas sobre los datos almacenados en las subpalabras o campos independientes de un registro. Una arquitectura compatible con SWAR incluye un conjunto de instrucciones suficiente para permitir que los datos almacenados en estos campos se traten de forma independiente, aunque la arquitectura no incluya instrucciones específicas para tal fin.

Uno de los primeros ejemplos históricos, operativo en 1958, fue el TX-2 del Laboratorio Lincoln, que tenía una memoria de 36 bits e instrucciones que podían operar en la ALU sobre una subpalabra de 36 bits, o sobre dos subpalabras de 18 bits o cuatro de 9 bits. El TX-2 es anterior a la invención del término SIMD. [ 4 ]

Un ejemplo temprano y conocido de arquitectura SWAR fue el Intel Pentium con MMX , que implementaba el conjunto de extensiones MMX . El Intel Pentium , por el contrario, no incluía dichas instrucciones, pero aun así podía funcionar como una arquitectura SWAR mediante una programación manual cuidadosa o técnicas de compilación.

Las primeras arquitecturas SWAR incluyen DEC Alpha MVI , PA-RISC MAX de Hewlett-Packard , MIPS MDMX de Silicon Graphics Incorporated y SPARC V9 VIS de Sun. Al igual que MMX, muchos de los conjuntos de instrucciones SWAR están diseñados para una codificación de vídeo más rápida. [ 5 ]

Historia del modelo de programación SWAR

Wesley A. Clark introdujo las operaciones de datos de subpalabra particionadas en la década de 1950. Esto puede considerarse un precursor muy temprano de SWAR. Leslie Lamport presentó técnicas SWAR en su artículo titulado "Procesamiento de múltiples bytes con instrucciones de palabra completa" [ 6 ] en 1975.

Con la introducción de las extensiones del conjunto de instrucciones multimedia MMX de Intel en 1996, los procesadores de escritorio con capacidades de procesamiento paralelo SIMD se hicieron comunes. Inicialmente, estas instrucciones solo podían utilizarse mediante código ensamblador escrito a mano.

En otoño de 1996, el profesor Hank Dietz impartía el curso de Construcción de Compiladores para estudiantes de pregrado en la Facultad de Ingeniería Eléctrica e Informática de la Universidad de Purdue. Para este curso, asignó una serie de proyectos en los que los estudiantes debían construir un compilador sencillo dirigido a MMX. El lenguaje de entrada era un subconjunto del dialecto MPL de MasPar llamado NEMPL (Not Exactly MPL).

Durante el semestre, el ayudante de cátedra, Randall (Randy) Fisher, se percató de varios problemas con MMX que dificultarían la creación del back-end del compilador NEMPL. Por ejemplo, MMX incluye una instrucción para multiplicar datos de 16 bits, pero no para multiplicar datos de 8 bits. El lenguaje NEMPL no contemplaba este problema, lo que permitía al programador escribir programas que requerían multiplicaciones de 8 bits.

La arquitectura x86 de Intel no fue la única en incluir instrucciones paralelas tipo SIMD. Los conjuntos de instrucciones VIS de Sun , MDMX de SGI y otros conjuntos de instrucciones multimedia se habían añadido a las arquitecturas de conjuntos de instrucciones existentes de otros fabricantes para dar soporte a las denominadas aplicaciones de nuevos medios . Estas extensiones presentaban diferencias significativas en la precisión de los datos y los tipos de instrucciones compatibles.

Dietz y Fisher comenzaron a desarrollar la idea de un modelo de programación paralela bien definido que permitiría programar para ese modelo sin conocer las especificaciones de la arquitectura de destino. Este modelo se convertiría en la base de la tesis doctoral de Fisher. El acrónimo "SWAR" fue acuñado por Dietz y Fisher un día en la oficina de Hank en el edificio MSEE de la Universidad de Purdue. [ 7 ] Se refiere a esta forma de procesamiento paralelo, a las arquitecturas diseñadas para realizar este tipo de procesamiento de forma nativa y al modelo de programación de propósito general que constituye la tesis doctoral de Fisher.

El problema de compilar para estas arquitecturas tan diversas se discutió en un artículo presentado en LCPC98. [ 5 ]

Algunas aplicaciones de SWAR

El procesamiento SWAR se ha utilizado en el procesamiento de imágenes, [ 8 ] emparejamientos criptográficos, [ 9 ] procesamiento raster, [ 10 ] dinámica de fluidos computacional, [ 11 ] y comunicaciones. [ 12 ]

Ejemplos

Las técnicas SWAR pueden utilizarse incluso en sistemas sin soporte de hardware especial. Las operaciones lógicas actúan bit a bit, es decir, sobre cada bit de un registro de forma independiente. La suma y la resta son más complejas, pero pueden resultar útiles si se evita la propagación de acarreo no deseada entre los carriles. Salvo por esta propagación de acarreo, una suma o resta de 64 bits equivale a realizar ocho sumas o restas de 8 bits.

Conjunto de bits de conteo

Probablemente, el ejemplo arquetípico de las técnicas SWAR sea encontrar el número de bits activados en un registro. El registro se trata sucesivamente como una serie de campos de 1 bit, 2 bits, 4 bits, etc.

Para empezar, tenga en cuenta que el recuento de población de un campo de 1 bit es simplemente el campo en sí. Para hallar el recuento de población de un campo de 2 bits, sume los recuentos de población de sus dos campos constituyentes de 1 bit. Esto se puede hacer en paralelo para 32 campos de 2 bits en un valor de 64 bits x:

x2 := (x & 0x5555555555555555) + ((x >> 1) & 0x5555555555555555);

La constante hexadecimal0x5 es binaria 0101 2 , que aísla los bits pares. La suma no puede desbordar cada campo de 2 bits, ya que la suma máxima posible es 2.

Esto se puede repetir para combinar campos de 2 bits en campos de 4 bits. Aquí, usamos una máscara binaria 0011 2 , o hexadecimal 0x3, para aislar pares de bits:

x4 := (x2 y 0x3333333333333333) + ((x2 >> 2) y 0x3333333333333333);

Ahora, cada campo de 4 bits contiene un recuento de 0 a 4. Dado que un campo de 4 bits puede contener un valor de hasta 15, no es posible que se produzca un desbordamiento al sumar dos recuentos de población de 4 bits, lo que permite que el enmascaramiento se realice después de la suma, en lugar de una vez por cada sumando:

x8 := (x4 + (x4 >> 4)) & 0x0f0f0f0f0f0f0f0f;

En este punto, los campos de 8 bits pueden contener valores de hasta 255, por lo que no es necesario aplicar más máscaras hasta el final:

x16 = x8 + (x8 >> 8); x32 = x16 + (x16 >> 16); x64 = x32 + (x32 >> 32); recuento_población = x64 & 0xff;

Refinamientos adicionales

Hay varias variantes bien conocidas de esto. En particular, los últimos tres pasos de desplazamiento y suma se pueden combinar en

recuento_de_población = (x8 * 0x0101010101010101) >> 56;

Las tres etapas de desplazamiento y suma requieren 6 instrucciones, cada una con una dependencia de datos respecto a la anterior, por lo que tardan al menos 6 ciclos de reloj. Una multiplicación suele ser más rápida. Al operar con palabras de 32 bits, la situación es menos clara, ya que es común una multiplicación de 3 ciclos.

Una segunda variante consiste en modificar el primer paso. En lugar de combinar los dos bits b 1 y b 0 en cada campo de 2 bits sumándolos, se considera el valor inicial del campo de 2 bits como 2 b 1 + b 0. Al restar b 1 de este valor, se obtiene la suma deseada con una sola operación de enmascaramiento:

x2 := x − ((x >> 1) & 0x5555555555555555);

Encontrar cero bytes

Es habitual buscar un terminador nulo en una cadena de caracteres . Hacer esto byte a byte es ineficiente cuando un procesador de 64 bits puede operar con 8 bytes a la vez.

Se puede utilizar la misma técnica para buscar separadores de rutas de archivo u otros delimitadores, aplicando primero una operación OR exclusiva con el valor del byte de destino.

Algunas arquitecturas incluyen instrucciones especiales para realizar comparaciones de 8 bytes a la vez. Por ejemplo, la DEC Alpha incluía una CMPBGEinstrucción para realizar comparaciones de 8 bytes simultáneamente. Sin embargo, la búsqueda de un byte cero puede realizarse sin necesidad de soporte especial.

Una forma sería combinar 8 bits mediante una operación OR, de manera muy similar al ejemplo de conteo de bits anterior:

x2 = x | x<<1; x4 = x2 | x2<<2; x8 = x4 | x4<<4; byte_map = ~x8 & 0x8080808080808080;

Esto da como resultado un byte_mapbit con un 1 en el bit más significativo de cualquier byte que originalmente era cero.

Sin embargo, esto se puede hacer más rápidamente aprovechando la propagación de acarreo mediante operaciones aritméticas. Sumar 0x7f(binario 01111111 2 ) a cada byte provoca un acarreo en el bit 7 si los 7 bits menos significativos no son cero. El desafío es asegurar que la propagación de acarreo se detenga en el bit 7 y no afecte a otros bytes. Esto se puede lograr trabajando por separado en los 7 bits menos significativos y el bit más significativo de cada byte. Primero, extraiga los 7 bits menos significativos de cada byte mediante una operación AND0x7f antes de sumar 0x7f:

x7 = (x & 0x7f7f7f7f7f7f7f7f) + 0x7f7f7f7f7f7f7f7f;

Luego, combínalo con los fragmentos más significativos:

x8 = x7 | x;

Este valor tendrá el bit más significativo de cada campo de 8 bits establecido en 1 si ese byte no es cero. Finalmente:

byte_map = ~(x8 | 0x7f7f7f7f7f7f7f7f);

Se establecerán todos los bits bajos no deseados en cada byte, luego se complementará todo, dejando solo bits 1 donde el byte de entrada correspondiente sea cero. (Esto es equivalente a ~x8 & 0x80...80, pero usa el mismo valor constante). Si no hay bits 1, la búsqueda puede continuar con la siguiente palabra. Si hay bits 1, la longitud de la cadena se puede calcular a partir de sus posiciones.

Refinamientos adicionales

Si el objetivo se limita a encontrar el primer byte cero en un procesador little-endian , es posible encontrar el byte cero menos significativo en menos operaciones, utilizando dos constantes diferentes: [ 13 ]

x7 = x − 0x0101010101010101; byte_map = x7 & ~x & 0x8080808080808080;

Para cada byte b , esto activa su bit más significativo byte_mapsi el bit más significativo de b − 1 está activado y el bit más significativo de b está desactivado, algo que solo ocurre si b = 0.

La afirmación anterior solo es cierta si no hay ningún préstamo en ; si hay un préstamo, la condición también será cierta si b = 1. Sin embargo, dicho préstamo solo puede ser generado por un byte cero menos significativo, por lo que el byte cero menos significativo se identificará correctamente, como se desea.

Esto no solo ahorra una operación binaria, sino que además no todas son secuencialmente dependientes, por lo que puede realizarse en dos ciclos suponiendo la existencia de una instrucción "and not" (borrado de bits).

Consultas en tablas pequeñas

Como generalización de un mapa de bits , es posible almacenar tablas de búsqueda muy pequeñas en un solo registro. Por ejemplo, el número de días de un mes varía de 28 a 31, un rango de 4 valores. Esto se puede almacenar en 12 × 2 = 24 bits.

días_tabla = 0xeefbb3 + (es_año_bisiesto << 2); días_en_el_mes = 28 + (tabla_días >> 2*mes & 3);

(Esto supone que el número de mes empieza en 0. Se puede adaptar un número de mes empieza en 1 desplazando el punto days_table).

El hecho de que la tabla encaje perfectamente en un solo registro facilita su modificación para los años bisiestos .

Véase también

Referencias

  1. ↑ Miyaoka, Y.; Choi, J.; Togawa, N.; Yanagisawa, M.; Ohtsuki, T. (2002). Un algoritmo de generación de unidades de hardware para la síntesis de núcleos de procesador con instrucciones SIMD empaquetadas . Conferencia Asia-Pacífico sobre Circuitos y Sistemas. Vol.  1. pp. 171–176 . doi : 10.1109/APCCAS.2002.1114930 . hdl : 2065/10689 . 
  2. ↑ Flynn, Michael J. (septiembre de 1972). "Algunas organizaciones informáticas y su eficacia" (PDF) . IEEE Transactions on Computers . C-21 (9): 948–960 . doi : 10.1109/TC.1972.5009071 .
  3. ↑ Fisher, Randall J (2003). SIMD de propósito general dentro de un registro: procesamiento paralelo en microprocesadores de consumo (PDF) (Ph.D.). Universidad de Purdue.
  4. ↑ "Copia archivada" (PDF) . Archivado del original (PDF) el 22/04/2021.{{cite web}}: CS1 mantenimiento: copia archivada como título ( enlace )
  5. 1 2 Fisher, Randall J.; Henry G. Dietz (agosto de 1998). S. Chatterjee; JF Prins; L. Carter; J. Ferrante; Z. Li; D. Sehr; P.-C. Yew (eds.). "Compilación para SIMD dentro de un registro". Actas del 11.º Taller Internacional sobre Lenguajes y Compiladores para Computación Paralela .
  6. ↑ Lamport, Leslie (agosto de 1975). "Procesamiento de múltiples bytes con instrucciones de palabra completa" . Communications of the ACM . 18 (8): 471– 475. doi : 10.1145/360933.360994 . S2CID 1593593 . 
  7. ↑ Dietz, Hank. "Los algoritmos mágicos agregados" .
  8. ↑ Padua, Flavio LC; Pereira, Guilherme AS; Neto, José P. de Queiroz; Campos, Mario FM; Fernandes, Antonio O. (enero de 2001). Mejora del tiempo de procesamiento de imágenes grandes mediante paralelismo a nivel de instrucción (PDF) . Semana Chilena de la Computación, V Taller de Sistemas Paralelos y Distribuidos. Punta Arenas. Archivado desde el original (PDF) el 25 de febrero de 2007 . Consultado el 5 de diciembre de 2012 .
  9. ↑ Grabher, Philipp; Johann Großschädl; Dan Page (2009). «Sobre la implementación paralela de software de emparejamientos criptográficos». Áreas selectas en criptografía . Notas de clase en ciencias de la computación. Vol. 5381. págs. 35–50 . doi : 10.1007/978-3-642-04159-4_3 . ISBN   978-3-642-04158-7.
  10. ↑ Persada, Onil Nazra; Thierry Goubier (12–14 de septiembre de 2004). "Aceleración del procesamiento ráster con paralelismo de grano fino y grueso en GRASS". Actas de la Conferencia de Usuarios de FOSS/GRASS 2004 .
  11. ↑ Hauser, Thomas; TI Mattox; RP LeBeau; HG Dietz; PG Huang (abril de 2003). "Optimizaciones de código para microprocesadores complejos aplicadas al software CFD". SIAM Journal on Scientific Computing . 25 (4): 1461– 1477. doi : 10.1137/S1064827502410530 . ISSN 1064-8275 . 
  12. ↑ Spracklen, Lawrence A. (2001). Sistemas SWAR y aplicaciones de comunicaciones (PDF) (Ph.D.). Universidad de Aberdeen.
  13. ↑ Fisher, James (24-01-2017). "Comprobación rápida de un byte cero en C mediante operaciones bit a bit" . Recuperado el 21-12-2024 .
  • El agregado - SWAR: SIMD dentro de un registro
  • Trucos de manipulación de bits
  • Técnicas SIMD y SWAR en ChessProgramming.org, que incluye ejemplos de operaciones aritméticas: suma, resta y promedio.