Predicación (arquitectura de computadoras)

En arquitectura de computadoras , la predicación es una característica que proporciona una alternativa a la transferencia de control condicional , implementada mediante instrucciones de máquina de bifurcación condicional. La predicación funciona asociando instrucciones no bifurcadas condicionales ( predicadas ) a un predicado , un valor booleano que la instrucción utiliza para controlar si se le permite modificar el estado arquitectónico o no. Si el predicado especificado en la instrucción es verdadero, la instrucción modifica el estado arquitectónico; de lo contrario, el estado arquitectónico permanece sin cambios. Por ejemplo, una instrucción de movimiento predicada (un movimiento condicional) solo modificará el destino si el predicado es verdadero. Así, en lugar de utilizar una bifurcación condicional para seleccionar una instrucción o una secuencia de instrucciones a ejecutar en función del predicado que controla si se produce la bifurcación, las instrucciones a ejecutar se asocian a ese predicado, de modo que se ejecutarán o no en función de si ese predicado es verdadero o falso. ^{[ 1 ]}

Los procesadores vectoriales , algunos conjuntos de instrucciones SIMD (como AVX2 y AVX-512 ) y las GPU en general hacen un uso intensivo de la predicación, aplicando un bit de un vector de máscara condicional a los elementos correspondientes en los registros vectoriales que se están procesando, mientras que la predicación escalar en conjuntos de instrucciones escalares solo necesita un bit de predicado. Donde las máscaras de predicado se vuelven particularmente poderosas en el procesamiento vectorial es cuando una matriz de códigos de condición , uno por elemento vectorial, puede retroalimentar las máscaras de predicado que luego se aplican a las instrucciones vectoriales subsiguientes.

La mayoría de los programas informáticos contienen código condicional , que se ejecuta solo bajo condiciones específicas dependiendo de factores que no se pueden determinar de antemano, por ejemplo, la entrada del usuario. Dado que la mayoría de los procesadores simplemente ejecutan la siguiente instrucción en una secuencia, la solución tradicional consiste en insertar instrucciones de salto que permiten que un programa salte condicionalmente a una sección diferente del código, cambiando así el siguiente paso en la secuencia. Esto fue suficiente hasta que los diseñadores comenzaron a mejorar el rendimiento implementando la segmentación de instrucciones , un método que se ve ralentizado por los saltos. Para una descripción más detallada de los problemas que surgieron y una solución popular, consulte el predictor de saltos .

Por suerte, uno de los patrones de código más comunes que normalmente se basa en bifurcaciones tiene una solución más elegante. Considere el siguiente pseudocódigo : ^{[ 1 ]}

Si se cumple la condición , haz algo ; de lo contrario , haz otra cosa .

En un sistema que utiliza ramificación condicional, esto podría traducirse en instrucciones de máquina similares a: ^{[ 1 ]}

ramificar_si_condición_a etiqueta1 hacer_algo_más ramificar_siempre_a etiqueta2 etiqueta1 : hacer_algo etiqueta2 : ...

Con la predicación, todas las posibles rutas de bifurcación se codifican en línea, pero algunas instrucciones se ejecutan mientras que otras no. La idea básica es que cada instrucción está asociada con un predicado (la palabra aquí se usa de forma similar a su uso en la lógica de predicados ) y que la instrucción solo se ejecutará si el predicado es verdadero. El código máquina para el ejemplo anterior usando predicación podría verse así: ^{[ 1 ]}

( condición ) hacer_algo ( no condición ) hacer_algo_otra_cosa

Además de eliminar bifurcaciones, se necesita menos código en total, siempre que la arquitectura proporcione instrucciones predefinidas. Si bien esto no garantiza una ejecución más rápida en general, sí lo hará si los do_somethingbloques do_something_elsede código son lo suficientemente cortos.

La forma más simple de predicación es la predicación parcial , donde la arquitectura cuenta con instrucciones de movimiento condicional o selección condicional . Las instrucciones de movimiento condicional escriben el contenido de un registro sobre otro solo si el valor del predicado es verdadero, mientras que las instrucciones de selección condicional eligen cuál de dos registros tiene su contenido escrito en un tercero en función del valor del predicado. Una forma más generalizada y capaz es la predicación completa . La predicación completa tiene un conjunto de registros de predicado para almacenar predicados (lo que permite eliminar simultáneamente múltiples bifurcaciones anidadas o secuenciales) y la mayoría de las instrucciones en la arquitectura tienen un campo especificador de registro (opcional) para especificar qué registro de predicado proporciona el predicado. ^{[ 2 ]}

El objetivo principal de la predicción es evitar saltos sobre secciones muy pequeñas de código del programa, lo que aumenta la eficacia de la ejecución en paralelo y evita problemas con la caché . También tiene una serie de beneficios más sutiles:

• Las funciones que tradicionalmente se calculan mediante aritmética simple y operaciones bit a bit pueden calcularse más rápidamente utilizando instrucciones basadas en predicados.
• Las instrucciones con predicados diferentes se pueden combinar entre sí y con código incondicional, lo que permite una mejor planificación de las instrucciones y, por lo tanto, un rendimiento aún mejor.
• La eliminación de instrucciones de bifurcación innecesarias puede acelerar la ejecución de las bifurcaciones necesarias, como las que forman los bucles, al reducir la carga sobre los mecanismos de predicción de bifurcaciones .
• Eliminación del coste de una predicción errónea de bifurcación, que puede ser elevado en arquitecturas con un alto grado de segmentación.
• Los conjuntos de instrucciones que tienen códigos de condición completos generados por las instrucciones pueden reducir aún más el tamaño del código utilizando directamente los registros de condición en o como predicado.

El principal inconveniente de la predicación es el aumento del espacio de codificación. En las implementaciones típicas, cada instrucción reserva un campo de bits para el predicado que especifica bajo qué condiciones debe tener efecto dicha instrucción. Cuando la memoria disponible es limitada, como en los dispositivos embebidos , este coste de espacio puede ser prohibitivo. Sin embargo, algunas arquitecturas como Thumb-2 pueden evitar este problema (véase más abajo). Otros inconvenientes son los siguientes: ^{[ 3 ]}

• La predicación complica el hardware al agregar niveles de lógica a las rutas críticas y puede degradar la velocidad del reloj.
• Un bloque predicado incluye ciclos para todas las operaciones, por lo que las rutas más cortas pueden tardar más y ser penalizadas.
• Se requiere una lectura de registro adicional. Una suma sin predicado leería dos registros de un archivo de registros, mientras que una suma con predicado también necesitaría leer el archivo de registros del predicado. Esto aumenta los riesgos en la ejecución fuera de orden .
• La predicación no suele ser especulativa y provoca una cadena de dependencias más larga. Para datos ordenados, esto se traduce en una pérdida de rendimiento en comparación con una bifurcación predecible. ^{[ 4 ]}

La predicción es más efectiva cuando las rutas están equilibradas o cuando la ruta más larga es la que se ejecuta con mayor frecuencia, ^{[ 3 ]} pero determinar dicha ruta es muy difícil en tiempo de compilación, incluso en presencia de información de perfilado .

Las instrucciones predicadas fueron populares en los diseños de computadoras europeas de la década de 1950, incluyendo la Mailüfterl (1955), la Zuse Z22 (1955), la ZEBRA (1958) y la Electrologica X1 (1958). El diseño IBM ACS-1 de 1967 asignó un bit de "salto" en sus formatos de instrucción, y el procesador flexible CDC de 1976 asignó tres bits de ejecución condicional en sus formatos de microinstrucciones.

La arquitectura PA-RISC de Hewlett-Packard (1986) tenía una característica llamada anulación , que permitía que la mayoría de las instrucciones se basaran en la instrucción anterior. La arquitectura POWER de IBM (1990) incluía instrucciones de movimiento condicional. El sucesor de POWER, PowerPC (1993), eliminó estas instrucciones. La arquitectura Alpha de Digital Equipment Corporation (1992) también incluía instrucciones de movimiento condicional. MIPS obtuvo instrucciones de movimiento condicional en 1994 con la versión MIPS IV; y SPARC se extendió en la versión 9 (1994) con instrucciones de movimiento condicional tanto para registros enteros como de punto flotante. RISC-V inicialmente no tenía predicado, pero en la versión 2.0 del ISA no privilegiado lo adquirió a través de una extensión (Zicond) que contenía instrucciones de puesta a cero condicional con las que se puede sintetizar aritmética y selección condicional.

En la arquitectura IA-64 de Hewlett-Packard / Intel , la mayoría de las instrucciones son predicadas. Los predicados se almacenan en 64 registros de predicados especiales ; uno de estos registros siempre es verdadero, de modo que las instrucciones sin predicado son simplemente instrucciones con el predicado verdadero. El uso de la predicación es esencial en la implementación de la segmentación de software de IA-64 , ya que evita la necesidad de escribir código separado para prólogos y epílogos.

En la arquitectura x86 , el procesador Intel Pentium Pro (1995) añadió una familia de instrucciones de movimiento condicional ( CMOVy ). Estas instrucciones copiaban el contenido del registro de origen al registro de destino en función de un predicado proporcionado por el valor del registro de indicadores.FCMOVCMOV

En la arquitectura ARM , el conjunto de instrucciones original de 32 bits proporciona una función llamada ejecución condicional que permite que la mayoría de las instrucciones se basen en uno de 13 predicados, los cuales dependen de alguna combinación de los cuatro códigos de condición establecidos por la instrucción anterior. El conjunto de instrucciones Thumb de ARM (1994) eliminó la ejecución condicional para reducir el tamaño de las instrucciones y que cupieran en 16 bits, pero su sucesor, Thumb-2 (2003), superó este problema mediante el uso de una instrucción especial cuyo único efecto es proporcionar predicados para las cuatro instrucciones siguientes. El conjunto de instrucciones de 64 bits introducido en ARMv8-A (2011) reemplazó la ejecución condicional con instrucciones de selección condicional.

Algunos conjuntos de instrucciones SIMD dentro de un registro (SWAR), como AVX2, tienen la capacidad de usar una máscara lógica para cargar/almacenar valores en memoria de forma condicional, en una forma paralela de la operación de movimiento condicional. También pueden aplicar bits de máscara individuales a unidades aritméticas individuales que ejecutan una operación paralela. Hay un bit de máscara de predicado disponible para cada subpalabra del registro SWAR o para cada valor de carga/almacenamiento. Esta forma de predicado multibit también se utiliza en procesadores vectoriales a nivel de elemento (sinónimo de subpalabras SWAR).

para cada ( sub - palabra i ) de SWAR ( o Vector ) registrar ( condición - maskbit i ) hacer_algo ( sub - palabra i ) ( no condición - maskbit i ) hacer_algo_algo más ( sub - palabra i )

El enmascaramiento es una parte integral de los procesadores de matriz como el ILLIAC IV . Los procesadores de matriz se conocen hoy en día como de instrucción única, múltiples hilos (SIMT), y un bit de predicado por PE utilizado para activar o desactivar cada elemento de procesamiento. Cuando el PE no tiene instrucciones SIMD dentro de un registro , cada PE puede ser predicado individualmente:

para cada ( PE j ) // de matriz síncrona concurrente no SWAR ( active - maskbit j ) broadcast_scalar_instruction_to ( PE j )

Las GPU SIMT modernas utilizan (o utilizaban, pero la documentación de ILLIAC IV lo denominaba "ramificación" ) la predicación para habilitar/deshabilitar elementos de procesamiento individuales y , por separado y además, también para enmascarar subpalabras dentro de la ALU SWAR de cualquier PE dado.

para cada ( PE j ) de SIMT síncronamente - matriz concurrente ( activo - maskbit j ) { // transmitir solo a PE SWAR activos para cada ( sub - palabra i ) del registro SWAR en ( PE j ) ( condición - maskbit i ) hacer_algo ( sub - palabra i ) ( no condición - maskbit i ) hacer_algo_algo más ( sub - palabra i ) }

Todas las técnicas, ventajas y desventajas de la predicación escalar simple se aplican igualmente bien al caso del procesamiento paralelo, donde los problemas asociados con la ramificación se vuelven mucho más complejos. ^{[ 5 ]}

• Clements, Alan (2013). "8.3.7 Predicación" . Organización y arquitectura de computadoras: temas y variaciones . Cengage Learning. págs. 532–539 . ISBN  978-1-285-41542-0.