Algoritmo de Tomasulo

El algoritmo de Tomasulo es un algoritmo de hardware de arquitectura de computadora para la programación dinámica de instrucciones que permite la ejecución fuera de orden y permite un uso más eficiente de múltiples unidades de ejecución. Fue desarrollado por Robert Tomasulo en IBM en 1967 y fue implementado por primera vez en el IBM System / 360 modelo 91 ‘s unidad de coma flotante .

Las principales innovaciones del algoritmo de Tomasulo incluyen el cambio de nombre de registros en hardware, estaciones de reserva para todas las unidades de ejecución y un bus de datos común (CDB) en el que los valores calculados se transmiten a todas las estaciones de reserva que puedan necesitarlos. Estos desarrollos permiten una ejecución paralela mejorada de instrucciones que de otro modo se estancarían con el uso de tablas de puntuación u otros algoritmos anteriores.

Robert Tomasulo recibió el premio Eckert-Mauchly en 1997 por su trabajo en el algoritmo. ^[1]

Conceptos de implementación

Unidad de coma flotante de Tomasulo

Los siguientes son los conceptos necesarios para la implementación del algoritmo de Tomasulo:

Bus de datos común

El Common Data Bus (CDB) conecta las estaciones de reserva directamente a las unidades funcionales. Según Tomasulo, "conserva la precedencia al tiempo que fomenta la concurrencia". ^{[2] : 33} Esto tiene dos efectos importantes:

1. Las unidades funcionales pueden acceder al resultado de cualquier operación sin involucrar un registro de punto flotante, lo que permite que varias unidades que esperan un resultado continúen sin esperar a resolver la disputa para acceder a los puertos de lectura de archivos de registro.
2. Se distribuyen la detección de peligros y la ejecución del control. Las estaciones de reserva controlan cuándo se puede ejecutar una instrucción, en lugar de una sola unidad de peligro dedicada.

Orden de instrucción

Las instrucciones se emiten secuencialmente de modo que los efectos de una secuencia de instrucciones, como las excepciones generadas por estas instrucciones, se produzcan en el mismo orden en que se producirían en un procesador en orden, independientemente del hecho de que se estén ejecutando fuera de orden. orden (es decir, no secuencialmente).

Registrar cambio de nombre

El algoritmo de Tomasulo usa el cambio de nombre de registros para realizar correctamente la ejecución fuera de orden. Todos los registros de estaciones de reserva y de uso general tienen un valor real o un valor de marcador de posición. Si un valor real no está disponible para un registro de destino durante la etapa de emisión, inicialmente se usa un valor de marcador de posición. El valor del marcador de posición es una etiqueta que indica qué estación de reserva producirá el valor real. Cuando la unidad termina y transmite el resultado en el CDB, el marcador de posición se reemplazará con el valor real.

Cada unidad funcional tiene una única estación de reserva. Las estaciones de reserva contienen la información necesaria para ejecutar una sola instrucción, incluida la operación y los operandos. La unidad funcional comienza a procesar cuando está libre y cuando todos los operandos fuente necesarios para una instrucción son reales.

Excepciones

En términos prácticos, puede haber excepciones para las que no se dispone de suficiente información sobre el estado de una excepción, en cuyo caso el procesador puede plantear una excepción especial, denominada excepción "imprecisa". No se pueden producir excepciones imprecisas en implementaciones en orden , ya que el estado del procesador solo se cambia en el orden del programa (consulte Excepciones de canalización RISC ).

Los programas que experimentan excepciones "precisas", donde se puede determinar la instrucción específica que tomó la excepción, pueden reiniciarse o volver a ejecutarse en el punto de la excepción. Sin embargo, aquellos que experimentan excepciones "imprecisas" generalmente no pueden reiniciar o volver a ejecutar, ya que el sistema no puede determinar la instrucción específica que tomó la excepción.

Ciclo de vida de la instrucción

Las tres etapas enumeradas a continuación son las etapas por las que pasa cada instrucción desde el momento en que se emite hasta el momento en que se completa su ejecución.

Registrar leyenda

• Op - representa la operación que se realiza en operandos
• Qj, Qk: la estación de reserva que producirá el operando fuente relevante (0 indica que el valor está en Vj, Vk)
• Vj, Vk - el valor de los operandos fuente
• A: se utiliza para almacenar la información de la dirección de la memoria para una carga o almacenamiento
• Ocupado: 1 si está ocupado, 0 si no está ocupado
• Qi - (Única unidad de registro) la estación de reserva cuyo resultado debe almacenarse en este registro (si está en blanco o 0, no hay valores destinados a este registro)

Etapa 1: problema

En la etapa de emisión, se emiten instrucciones para su ejecución si todos los operandos y estaciones de reserva están listos o de lo contrario están bloqueados. Los registros se renombran en este paso, eliminando los peligros WAR y WAW.

• Recupere la siguiente instrucción del encabezado de la cola de instrucciones. Si los operandos de la instrucción están actualmente en los registros, entonces
  • Si una unidad funcional coincidente está disponible, emita la instrucción.
  • De lo contrario, como no hay una unidad funcional disponible, detenga la instrucción hasta que una estación o búfer esté libre.
• De lo contrario, podemos asumir que los operandos no están en los registros y, por lo tanto, usar valores virtuales. La unidad funcional debe calcular el valor real para realizar un seguimiento de las unidades funcionales que producen el operando.

Pseudocódigo ^{[3] : 180}

Estado de instrucción	Esperar hasta	Acción o contabilidad
Asunto	Estación r vacía	if ( RegisterStat [ rs ]. Qi ¦ 0 ) { RS [ r ]. Qj ← RegisterStat [ rs ]. Qi } else { RS [ r ]. Vj ← Regs [ rs ]; RS [ r ]. Qj ← 0 ; } si ( RegisterStat [ rt ]. Qi ¦ 0 ) { RS [r ]. Qk ← RegisterStat [ rt ]. Qi ; } más { RS [ r ]. Vk ← Regs [ rt ]; RS [ r ]. Qk ← 0 ; } RS [ r ]. Ocupado ← sí ; RegisterStat [ rd ]. Q ← r ;
Cargar o almacenar	Búfer r vacío	if ( RegisterStat [ rs ]. Qi ¦ 0 ) { RS [ r ]. Qj ← RegisterStat [ rs ]. Qi ; } más { RS [ r ]. Vj ← Regs [ rs ]; RS [ r ]. Qj ← 0 ; } RS [ r ]. A ← imm ; RS [ r ].Ocupado ← sí ;
Cargar solo		RegisterStat [ rt ]. Qi ← r ;
Solo tienda		si ( RegisterStat [ rt ]. Qi ¦ 0 ) { RS [ r ]. Qk ← RegisterStat [ rt ]. Qi ; } más { RS [ r ]. Vk ← Regs [ rt ]; RS [ r ]. Qk ← 0 };

Ejemplo del algoritmo de Tomasulo ^[4]

Etapa 2: ejecutar

En la etapa de ejecución, se llevan a cabo las operaciones de instrucción. Las instrucciones se retrasan en este paso hasta que todos sus operandos estén disponibles, lo que elimina los peligros RAW. La corrección del programa se mantiene a través del cálculo efectivo de direcciones para prevenir peligros a través de la memoria.

• Si uno o más de los operandos aún no están disponibles, entonces: espere a que el operando esté disponible en la CDB.
• Cuando todos los operandos están disponibles, entonces: si la instrucción es una carga o almacenamiento
  • Calcule la dirección efectiva cuando el registro base esté disponible y colóquelo en el búfer de carga / almacenamiento
    • Si la instrucción es una carga, entonces: ejecutar tan pronto como la unidad de memoria esté disponible
    • De lo contrario, si la instrucción es una tienda, entonces: espere a que se almacene el valor antes de enviarlo a la unidad de memoria.
• De lo contrario, la instrucción es una operación de unidad lógica aritmética (ALU), luego: ejecute la instrucción en la unidad funcional correspondiente

Pseudocódigo ^{[3] : 180}

Estado de instrucción	Esperar hasta	Acción o contabilidad
Operación FP	(RS [r] .Qj = 0) y (RS [r] .Qk = 0)	Calcular resultado: los operandos están en Vj y Vk
Cargar / almacenar paso 1	RS[r].Qj = 0 & r es el jefe de la cola de almacenamiento de carga	RS [r] .A ← RS [r] .Vj + RS [r] .A;
Cargar paso 2	Cargar paso 1 completo	Leer de Mem[RS[r].A]

Etapa 3: escribir el resultado

En la etapa de escritura de resultados, los resultados de las operaciones de ALU se vuelven a escribir en los registros y las operaciones de almacenamiento se vuelven a escribir en la memoria.

• Si la instrucción fue una operación ALU
  • Si el resultado está disponible, entonces: escríbalo en el CDB y desde allí en los registros y en cualquier estación de reserva que esté esperando este resultado.
• De lo contrario, si la instrucción era una tienda, entonces: escriba los datos en la memoria durante este paso

Pseudocódigo ^{[3] : 180}

Estado de instrucción	Esperar hasta	Acción o contabilidad
Operación FP o carga	Ejecución completa en r & CDB disponible	∀ x ( if ( RegisterStat [ x ]. Qi = r ) { regs [ x ] ← resultado ; RegisterStat [ x ]. Qi = 0 }); ∀ x ( si ( RS [ x ]. Qj = r ) { RS [ x ]. Vj ← resultado ; RS [ x ]. Qj ← 0 ; }); ∀ x ( si ( RS [ x ]. Qk = r ) { RS [ x ]. Vk ← resultado ; RS [ x ]. Qk ← 0 ; }); RS [ r ]. Ocupado ← no ;
Tienda	Ejecución completa en r & RS [r] .Qk = 0	Mem [ RS [ r ]. A ] ← RS [ r ]. Vk ; RS [ r ]. Ocupado ← no ;

Mejoras en el algoritmo

Los conceptos de estaciones de reserva, cambio de nombre de registros y bus de datos común en el algoritmo de Tomasulo presentan avances significativos en el diseño de computadoras de alto rendimiento.

Las estaciones de reserva asumen la responsabilidad de esperar los operandos en presencia de dependencias de datos y otras inconsistencias, como la variación del tiempo de acceso al almacenamiento y la velocidad del circuito, liberando así las unidades funcionales. Esta mejora supera los retrasos prolongados de punto flotante y los accesos a la memoria. En particular, el algoritmo es más tolerante con las pérdidas de caché. Además, los programadores se liberan de la implementación de código optimizado. Esto es el resultado de que el bus de datos común y la estación de reserva trabajan juntos para preservar las dependencias y fomentar la concurrencia. ^{[2] : 33}

Al rastrear operandos para obtener instrucciones en las estaciones de reserva y registrar el cambio de nombre en el hardware, el algoritmo minimiza la lectura tras escritura (RAW) y elimina los peligros de la arquitectura informática de escritura tras escritura (WAW) y Escritura tras lectura (WAR) . Esto mejora el rendimiento al reducir el tiempo perdido que de otro modo sería necesario para los puestos. ^{[2] : 33}

Una mejora igualmente importante en el algoritmo es que el diseño no se limita a una estructura de tubería específica. Esta mejora permite que el algoritmo sea adoptado más ampliamente por procesadores de múltiples problemas. Además, el algoritmo se amplía fácilmente para permitir la especulación de ramas. ^{[3] : 182}

Aplicaciones y legado

El algoritmo de Tomasulo, fuera de IBM, no se usó durante varios años después de su implementación en la arquitectura System / 360 Model 91. Sin embargo, experimentó un gran aumento en el uso durante la década de 1990 por 3 razones:

1. Una vez que las cachés se volvieron algo común, la capacidad del algoritmo de Tomasulo para mantener la concurrencia durante tiempos de carga impredecibles causados ​​por fallas de caché se volvió valiosa en los procesadores.
2. La programación dinámica y la especulación de la rama que permite el algoritmo ayudaron al rendimiento a medida que los procesadores emitían cada vez más instrucciones.
3. La proliferación de software de mercado masivo significaba que los programadores no querrían compilar para una estructura de canalización específica. El algoritmo puede funcionar con cualquier arquitectura de canalización y, por lo tanto, el software requiere pocas modificaciones específicas de la arquitectura. ^{[3] : 183}

Muchos procesadores modernos implementan esquemas de programación dinámica derivados del algoritmo original de Tomasulo, incluidos los populares chips Intel x86-64 . ^{[5] [ verificación fallida ] [6]}

Ver también

• Reordenar búfer (ROB)
• Paralelismo a nivel de instrucción (ILP)

Referencias

1. "Robert Tomasulo - ganador del premio" . Premios ACM . ACM . Consultado el 8 de diciembre de 2014 .
2. Tomasulo, Robert Marco (enero de 1967). "Un algoritmo eficiente para la explotación de múltiples unidades aritméticas". IBM Journal of Research and Development . IBM. 11 (1): 25–33. doi : 10.1147 / rd.111.0025 . ISSN 0018-8646 .  
3. Hennessy, John L .; Patterson, David A. (2012). Arquitectura informática: un enfoque cuantitativo . Waltham, MA: Elsevier . ISBN 978-0123838728.
4. "CSE P548 - Tomasulo" (PDF) . washington.edu . Universidad de Washington. 2006 . Consultado el 8 de diciembre de 2014 .
5. Manual del desarrollador de software de arquitecturas Intel 64 y IA-32 (informe). Intel. Septiembre de 2014 . Consultado el 8 de diciembre de 2014 .
6. Yoga, Adarsh. "Diferencias entre el algoritmo de Tomasulo y la programación dinámica en la microarquitectura Intel Core" . El más borracho . Consultado el 4 de abril de 2016 .

Lectura adicional

• Savard, John JG (2018) [2014]. "Ejecución canalizada y fuera de servicio" . quadibloc . Archivado desde el original el 3 de julio de 2018 . Consultado el 16 de julio de 2018 .

Enlaces externos

• Programación dinámica: algoritmo de Tomasulo
• Simulación del subprograma Java HASE del algoritmo de Tomasulo