Predicación (arquitectura informática) - Predication (computer architecture)

No confundir con la predicción de Branch .

En ciencias de la computación , la predicación es una característica arquitectónica que proporciona una alternativa a la transferencia condicional de control , implementada por instrucciones de máquina como la rama condicional , la llamada condicional , el retorno condicional y las tablas de rama . La predicción funciona ejecutando instrucciones de ambas rutas de la rama y solo permite que las instrucciones de la ruta tomada modifiquen el estado de la arquitectura. Las instrucciones de la ruta tomada pueden modificar el estado de la arquitectura porque se han asociado ( predicado ) con un predicado , un valor booleano utilizado por la instrucción para controlar si la instrucción puede modificar el estado de la arquitectura o no.

En pocas palabras: si se establece el bit de condición de registro, se ejecuta la instrucción; si el bit está claro, no lo es. Dado que el contenido de Condition Register es dinámico, la ejecución de la instrucción predicada también es dinámica, es decir (condicionalmente) determinada en tiempo de ejecución.

Los procesadores vectoriales , algunos SIMD ISA (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 escalar los conjuntos de instrucciones solo necesitan un bit de predicado. Donde las máscaras de predicado se vuelven particularmente poderosas en el procesamiento de vectores es si una matriz de códigos de condición , uno por elemento de vector, puede retroalimentar las máscaras de predicado que luego se aplican a las instrucciones de vector posteriores.

Descripción general

La mayoría de los programas de computadora contienen código condicional , que se ejecutará solo bajo condiciones específicas dependiendo de factores que no se pueden determinar de antemano, por ejemplo, dependiendo de la entrada del usuario. Como la mayoría de los procesadores simplemente ejecutan la siguiente instrucción en una secuencia, la solución tradicional es insertar instrucciones de bifurcación que permiten que un programa bifurque condicionalmente a una sección diferente de código, cambiando así el siguiente paso en la secuencia. Esto fue suficiente hasta que los diseñadores comenzaron a mejorar el rendimiento mediante la implementación de la canalización de instrucciones , un método que las ramas ralentizan. Para obtener una descripción más detallada de los problemas que surgieron y una solución popular, consulte el predictor de ramas .

Afortunadamente, uno de los patrones de código más comunes que normalmente se basa en la ramificación tiene una solución más elegante. Considere el siguiente pseudocódigo : 

if condition
    {dosomething}
else
    {dosomethingelse};

En un sistema que usa bifurcaciones condicionales, esto podría traducirse en instrucciones de máquina similares a: 

branch-if-condition to label1
dosomethingelse
branch-to label2
label1:
dosomething
label2:
...

Con la predicación, todas las posibles ramificaciones 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 manera 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 de máquina para el ejemplo anterior usando la predicación podría verse así: 

(condition) dosomething
(not condition) dosomethingelse

Además de eliminar las ramas, se necesita menos código en total, siempre que la arquitectura proporcione instrucciones predicadas. Si bien esto no garantiza una ejecución más rápida en general, lo hará si los bloques de código dosomething y dosomethingelse son lo suficientemente cortos.

La forma más simple de la predicción es la predicación parcial , donde la arquitectura tiene instrucciones de movimiento condicional o selección condicional . Las instrucciones de movimiento condicionales escriben el contenido de un registro sobre otro solo si el valor del predicado es verdadero, mientras que las instrucciones de selección condicionales eligen cuál de los dos registros tiene su contenido escrito en un tercero basándose en el 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 varias ramas anidadas o secuenciales) y la mayoría de las instrucciones en la arquitectura tienen un campo de especificador de registro para especificar qué registro de predicado proporciona el predicado.

Ventajas

El propósito principal de la predicación es evitar saltos sobre secciones muy pequeñas del código del programa, aumentando la efectividad de la ejecución canalizada y evitando problemas con la caché . También tiene una serie de beneficios más sutiles:

  • Las funciones que tradicionalmente se calculan mediante operaciones aritméticas y bit a bit pueden ser más rápidas de calcular utilizando instrucciones predicadas.
  • Las instrucciones predefinidas con diferentes predicados se pueden mezclar entre sí y con código incondicional, lo que permite una mejor programación de instrucciones y, por lo tanto, un rendimiento aún mejor.
  • La eliminación de instrucciones de bifurcación innecesarias puede hacer que la ejecución de bifurcaciones necesarias, como las que forman bucles, sea más rápida al disminuir la carga en los mecanismos de predicción de bifurcaciones .
  • Eliminación del costo de la predicción errónea de una sucursal que puede ser alta en arquitecturas profundamente interconectadas.
  • Los conjuntos de instrucciones que tienen códigos de condición completos generados por instrucciones pueden reducir aún más el tamaño del código utilizando directamente los registros de condición en o como predicado.

Desventajas

El principal inconveniente de la predicción es el aumento del espacio de codificación. En implementaciones típicas, cada instrucción reserva un campo de bits para el predicado que especifica bajo qué condiciones debe tener efecto esa instrucción. Cuando la memoria disponible es limitada, como en los dispositivos integrados , este costo de espacio puede ser prohibitivo. Sin embargo, algunas arquitecturas como Thumb-2 pueden evitar este problema (ver más abajo). Otros perjuicios son los siguientes:

  • La predicción complica el hardware al agregar niveles de lógica a las rutas críticas y potencialmente degrada 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.
  • La predicación generalmente no se especula y provoca una cadena de dependencia más larga. Para los datos ordenados, esto se traduce en una pérdida de rendimiento en comparación con una rama predecible.

La predicción es más eficaz cuando las rutas están equilibradas o cuando la ruta más larga es la que se ejecuta con más frecuencia, pero determinar dicha ruta es muy difícil en el momento de la compilación, incluso en presencia de información de creación de perfiles .

Historia

Las instrucciones específicas fueron populares en los diseños de computadoras europeos de la década de 1950, incluidos Mailüfterl (1955), Zuse Z22 (1955), ZEBRA (1958) y 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 en 1976 asignó tres bits de ejecución condicional en sus formatos de microinstrucción.

Hewlett-Packard 's PA-RISC de arquitectura (1986) tenía una característica llamada anulación , lo que permitió a la mayoría de las instrucciones que se basan por la instrucción anterior. La arquitectura POWER de IBM (1990) presentaba instrucciones de movimiento condicionales. El sucesor de POWER, PowerPC (1993), eliminó estas instrucciones. Digital Equipment Corporation 's Alfa arquitectura (1992) también contó con instrucciones de movimiento condicional. MIPS obtuvo instrucciones de movimiento condicionales en 1994 con la versión MIPS IV; y SPARC se amplió en la Versión 9 (1994) con instrucciones de movimiento condicionales para registros de enteros y de coma flotante.

En la arquitectura Hewlett-Packard / Intel IA-64 , se predica la mayoría de las instrucciones. Los predicados se almacenan en 64 registros de predicados de propósito especial ; y uno de los registros de predicado siempre es verdadero, de modo que las instrucciones no predecidas son simplemente instrucciones predicadas con el valor verdadero. El uso de predicación es esencial en la implementación de canalización de software de IA-64 porque evita la necesidad de escribir código separado para prólogos y epílogos.

En la arquitectura x86 , el procesador Intel Pentium Pro (1995) agregó una familia de instrucciones de movimiento condicionales ( CMOVy FCMOV) a la arquitectura . Las instrucciones copiaron el contenido del registro de origen en el registro de destino dependiendo de un predicado proporcionado por el valor del registro de bandera. CMOV

En la arquitectura ARM , el conjunto de instrucciones original de 32 bits proporciona una característica llamada ejecución condicional que permite que la mayoría de las instrucciones sean predicadas por uno de los 13 predicados que se basan en 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 para que pudieran caber en 16 bits, pero su sucesor, Thumb-2 (2003) superó este problema mediante el uso de una instrucción especial que no tiene otro efecto que proporcionar predicados para las siguientes cuatro instrucciones. El conjunto de instrucciones de 64 bits introducido en ARMv8-A (2011) reemplazó la ejecución condicional con instrucciones de selección condicional.

Predicación SIMD, SIMT y Vector

Algunos conjuntos de instrucciones SIMD , como AVX2, tienen la capacidad de usar una máscara lógica para cargar / almacenar valores en la memoria de manera condicional, una forma paralela del movimiento condicional, y también pueden aplicar bits de máscara individuales a unidades aritméticas individuales que ejecutan una operación en paralelo. La técnica se conoce como "Procesamiento asociativo" en la taxonomía de Flynn .

Esta forma de predicación también se utiliza en procesadores vectoriales e instrucción única, computación GPU de múltiples subprocesos . Todas las técnicas, ventajas y desventajas de la predicación escalar única se aplican igualmente al caso de procesamiento paralelo.

Ver también

Referencias

Otras lecturas