Una rama es una instrucción en un programa de computadora que puede hacer que una computadora comience a ejecutar una secuencia de instrucción diferente y, por lo tanto, se desvíe de su comportamiento predeterminado de ejecutar instrucciones en orden. [a] Rama (o bifurcación , bifurcada ) también puede referirse al acto de conmutar la ejecución a una secuencia de instrucción diferente como resultado de ejecutar una instrucción de bifurcación. Las instrucciones de bifurcación se utilizan para implementar el flujo de control en bucles de programa y condicionales (es decir, ejecutar una secuencia particular de instrucciones solo si se cumplen ciertas condiciones).
Una instrucción de bifurcación puede ser una bifurcación incondicional , que siempre resulta en bifurcación, o una bifurcación condicional , que puede o no causar bifurcación dependiendo de alguna condición. Además, dependiendo de cómo especifica la dirección de la nueva secuencia de instrucciones (la dirección "objetivo"), una instrucción de bifurcación se clasifica generalmente como directa , indirecta o relativa , lo que significa que la instrucción contiene la dirección objetivo o especifica dónde se encuentra el objetivo. se debe encontrar la dirección (por ejemplo, un registro o una ubicación de memoria), o especifica la diferencia entre la dirección actual y la de destino.
Implementación
Mecánicamente, una instrucción de bifurcación puede cambiar el contador de programa (PC) de una CPU . El contador de programa almacena la dirección de memoria de la siguiente instrucción que se ejecutará. Por lo tanto, una rama puede hacer que la CPU comience a obtener sus instrucciones de una secuencia diferente de celdas de memoria.
Cuando se toma una bifurcación , el contador de programa de la CPU se establece en el argumento de la instrucción de salto. Entonces, la siguiente instrucción se convierte en la instrucción en esa dirección en la memoria . Por tanto, el flujo de control cambia.
Cuando no se toma una rama , el contador de programa de la CPU no cambia. Por lo tanto, la siguiente instrucción ejecutada es la instrucción después de la instrucción de bifurcación. Por lo tanto, el flujo de control no cambia.
El término rama se puede utilizar cuando se hace referencia a programas en lenguajes de alto nivel, así como a programas escritos en código máquina o lenguaje ensamblador . En los lenguajes de programación de alto nivel , las ramas suelen adoptar la forma de declaraciones condicionales de diversas formas que encapsulan la secuencia de instrucciones que se ejecutará si se cumplen las condiciones. Las instrucciones de bifurcación incondicional como GOTO se utilizan para "saltar" incondicionalmente a (comenzar la ejecución de) una secuencia de instrucciones diferente.
Las instrucciones de bifurcación a nivel de máquina a veces se denominan instrucciones de salto . Las instrucciones de salto a nivel de la máquina suelen tener formas incondicionales y condicionales en las que estas últimas pueden tomarse o no según alguna condición. Por lo general, existen formas distintas para los saltos unidireccionales, a menudo llamadas invocaciones de saltos y subrutinas conocidas como llamada, que guardan automáticamente la dirección de origen como una dirección de retorno en la pila, lo que permite invocar una sola subrutina desde múltiples ubicaciones en el código.
En las CPU con registros de banderas , una instrucción anterior establece una condición en el registro de banderas. La instrucción anterior puede ser aritmética o lógica . A menudo está cerca de la rama, aunque no necesariamente la instrucción inmediatamente antes de la rama. La condición almacenada se usa luego en una rama como jump if overflow-flag set . Esta información temporal a menudo se almacena en un registro de banderas, pero también puede estar ubicada en otro lugar. Un diseño de registro de bandera es simple en computadoras simples y lentas. En las computadoras rápidas, un registro de banderas puede producir un cuello de botella en la velocidad, porque las instrucciones que de otro modo podrían operar en paralelo (en varias unidades de ejecución ) necesitan establecer los bits de las banderas en una secuencia particular.
También hay máquinas (o instrucciones particulares) donde la condición puede ser verificada por la propia instrucción de salto, como la rama
Algunas arquitecturas de CPU tempranas y simples, que todavía se encuentran en los microcontroladores, pueden no implementar un salto condicional, sino solo una operación condicional de "omitir la siguiente instrucción". Por tanto, un salto o llamada condicional se implementa como un salto condicional de una instrucción de salto o llamada incondicional.
Ejemplos de
Dependiendo de la arquitectura de la computadora , el mnemónico en lenguaje ensamblador para una instrucción de salto es típicamente una forma abreviada de la palabra salto o la palabra rama , a menudo junto con otras letras informativas (o un parámetro adicional) que representan la condición. A veces, también se incluyen otros detalles, como el rango del salto (el tamaño de la compensación) o un modo de direccionamiento especial que debe usarse para ubicar la compensación efectiva real.
Esta tabla enumera las instrucciones de salto o rama a nivel de máquina que se encuentran en varias arquitecturas conocidas:
condición o resultado | x86 | PDP-11, VAX | BRAZO (en parte 6502) | ecuación |
---|---|---|---|---|
cero (implica igual para sub / cmp) | JZ; JNZ | BEQ; BNE | BEQ; BNE | cero; no cero |
negativo (N), signo (S) o menos (M) | JS; JNS | IMC; BPL | IMC; BPL | negativo; no negativo |
desbordamiento aritmético (bandera llamada O o V) | JO; JNO | BVS; BVC | BVS; BVC | Desbordamiento; no desbordar |
llevar (de add, cmp, shift, etc.) | JC; JNC | BCS; BCC | BCS; BCC | llevar; no transporte |
sin firmar a continuación (inferior) | JB | BLO | BLO * | tomar prestado |
sin firmar abajo o igual (menor o igual) | JBE | BLOS | BLS * | pedir prestado o cero |
sin firmar arriba o igual (mayor o igual) | JAE | BHIS | BHS * | no pedir prestado |
sin firmar arriba (más alto) | JA | BHI | BHI * | no pedir prestado y no cero |
firmado menos de | JL | BLT | BLT | signo ≠ desbordamiento |
firmado menor o igual | JLE | BLE | BLE | (signo ≠ desbordamiento) o cero |
firmado mayor o igual | JGE | BGE | BGE | signo = desbordamiento |
firmado mayor que | JG | BGT | BGT | (signo = desbordamiento) y no cero |
* x86, el PDP-11, VAX y algunos otros, configuran el indicador de acarreo para señalar el préstamo y borran el indicador de acarreo para indicar que no hay préstamo . ARM, 6502 , el PIC y algunos otros, hacen lo contrario para las operaciones sustractivas. Esta función invertida del indicador de acarreo para ciertas instrucciones está marcada con ( * ), es decir, pedir prestado = no llevar en algunas partes de la tabla, pero si no se indica lo contrario, pedir prestadocargar. Sin embargo, la mayoría de las arquitecturas manejan las operaciones aditivas de la misma manera.
Problemas de rendimiento con instrucciones de bifurcación
Para lograr un alto rendimiento, los procesadores modernos se canalizan . Consisten en varias partes, cada una de las cuales procesa parcialmente una instrucción, alimenta sus resultados a la siguiente etapa de la tubería y comienza a trabajar en la siguiente instrucción del programa. Este diseño espera que las instrucciones se ejecuten en una secuencia particular que no cambia. Las instrucciones de bifurcación condicionales hacen imposible conocer esta secuencia. Por lo tanto, las ramas condicionales pueden provocar "paradas" en las que la canalización debe reiniciarse en una parte diferente del programa.
Mejorar el rendimiento al reducir los puestos de venta de las sucursales.
Varias técnicas mejoran la velocidad al reducir las pérdidas de las ramas condicionales.
Sugerencias de predicción de ramas
Históricamente, la predicción de ramas tomaba estadísticas y usaba el resultado para optimizar el código. Un programador compilaría una versión de prueba de un programa y la ejecutaría con datos de prueba. El código de prueba contó cómo se tomaron realmente las ramas. A continuación, el compilador utilizó las estadísticas del código de prueba para optimizar las ramas del código publicado. La optimización permitiría que la dirección de bifurcación más rápida (tomada o no) fuera siempre la ruta de flujo de control que se toma con más frecuencia. Para permitir esto, las CPU deben diseñarse con (o al menos tener) una temporización de bifurcación predecible. Algunas CPU tienen conjuntos de instrucciones (como Power ISA ) que se diseñaron con "sugerencias de rama" para que un compilador pueda decirle a una CPU cómo debe tomarse cada rama.
El problema con la predicción de ramas de software es que requiere un proceso de desarrollo de software complejo.
Predictores de rama de hardware
Para ejecutar cualquier software, los predictores de rama de hardware trasladaron las estadísticas a la electrónica. Los predictores de rama son partes de un procesador que adivinan el resultado de una rama condicional. Luego, la lógica del procesador apuesta por la conjetura al comenzar a ejecutar el flujo de instrucciones esperado. Un ejemplo de un esquema de predicción de rama de hardware simple es asumir que se toman todas las ramas hacia atrás (es decir, a un contador de programa más pequeño) (porque son parte de un ciclo), y que no se toman todas las ramas hacia adelante (a un contador de programa más grande) (porque dejan un bucle). Se desarrollan y validan estadísticamente mejores predictores de ramas ejecutándolos en simulación en una variedad de programas de prueba. Los buenos predictores suelen contar los resultados de ejecuciones anteriores de una rama. Las computadoras más rápidas y costosas pueden funcionar más rápido invirtiendo en una mejor electrónica de predicción de ramas. En una CPU con predicción de rama de hardware, las sugerencias de rama permiten que la predicción de rama supuestamente superior del compilador anule la predicción de rama más simplista del hardware.
Código sin sucursales
Alguna lógica se puede escribir sin ramas o con menos ramas. A menudo es posible utilizar operaciones bit a bit , movimientos condicionales u otra predicación en lugar de ramas. [1] [2] De hecho, el código sin ramificaciones es imprescindible para la criptografía debido a los ataques de tiempo . [3]
Ranura de retardo
Otra técnica es una ranura de retardo de rama . En este enfoque, siempre se ejecuta una instrucción después de una rama. Por lo tanto, la computadora puede usar esta instrucción para realizar un trabajo útil, ya sea que su tubería se detenga o no. Este enfoque fue históricamente popular en las computadoras RISC . En una familia de CPU compatibles, complica las CPU multiciclo (sin canalización), CPU más rápidas con canalizaciones más largas de lo esperado y CPU superescalares (que pueden ejecutar instrucciones fuera de orden).
Ver también
Notas
- ^ Al menos conceptualmente; ver ejecución fuera de servicio .
Referencias
- ^ Knuth, Donald (2008). El arte de la programación informática . Volumen 4, Pre-fascículo 1A (Revisión 6 ed.). págs. 48–49.
|volume=
tiene texto extra ( ayuda ) - ^ "Evitar ramas" . Wiki de programación de ajedrez .
- ^ "Cripto a tiempo constante" . BearSSL .
enlaces externos
- Documentación gratuita de IA-32 y x86-64 , proporcionada por Intel
- Preguntas frecuentes sobre PDP-11
- El conjunto de instrucciones ARM