Comenzaré cerca del principio, solo para asegurarme de que estamos en la misma página. Sospecho que el OP conoce parte de este material de fondo, pero puedo usar la nomenclatura de manera ligeramente diferente. Ha pasado un tiempo desde la última vez que leí a Hennessy y Patterson, por ejemplo. Inadvertidamente puedo describir un algoritmo que va más allá del algoritmo original de Tomasulo. Sin embargo, espero que mi descripción sea útil para su comprensión.
En su programa original, cada instrucción usa nombres de registro para identificar qué registros arquitectónicos leer como entradas a la instrucción, y qué registro (s) arquitectónico escribir como salidas de la instrucción.
Utilizo la frase registros arquitectónicos , ya que puede que no haya una relación uno a uno entre los nombres de registro que usa su programa y los registros físicos que la máquina realmente usa. Los registros arquitectónicos representan el conjunto de nombres de registros que puede usar en su programa de ensamblaje para acceder a los valores calculados por su programa.
- En puestos relacionados con la ingeniería de software, cuando el requisito dice al menos 2 años de experiencia en programación, ¿cómo se definen / cuantifican exactamente 2 años de programación?
- ¿Qué es lo mejor que has hecho en un hackathon?
- ¿Qué se discute durante una reunión de Scrum?
- ¿Cómo crearías Facebook ahora (con la tecnología actual)?
- ¿Qué equipos se consideran 'elite' (considerados los más inteligentes o trabajan en las tareas más difíciles) en Google?
En una implementación simple, de un solo problema, no canalizada de un conjunto de instrucciones, probablemente tenga una relación uno a uno entre los registros físicos y los registros arquitectónicos. Esto lleva a una implementación de hardware muy sencilla. Un solo problema caracteriza a la mayoría de los microprocesadores que encontraría desde la década de 1970 hasta principios de la década de 1990. Sin embargo, durante este período de tiempo, viste a los procesadores pasar de no canalizados a canalizados.
Los procesadores no interconectados de un solo problema no son muy rápidos. Para hacer que los procesadores vayan más rápido, primero comienza a canalizar. La canalización divide las operaciones de larga duración en múltiples ciclos de reloj. Lo bueno es que puede usar un tiempo de ciclo de reloj mucho más corto, haciendo que la velocidad del procesador sea más rápida. La desventaja es que algunas operaciones todavía toman múltiples relojes y pueden detener la máquina.
El primer paso para obtener un rendimiento eficiente de un procesador canalizado es agregar un marcador . El marcador lleva un registro de los resultados que aún no están listos (porque están en proceso). El marcador detiene la tubería cada vez que una instrucción solicita un resultado que aún no está listo. Si es inteligente, puede programar instrucciones para evitar paradas en la tubería. (A veces, estos puestos también se denominan enclavamientos de tuberías y son un sello distintivo de una tubería protegida ).
El marcador es responsable de detectar las dependencias de lectura-después-escritura (RAW) y escritura-después-escritura (WAW) (también llamadas peligros). Los riesgos SIN PROCESAR ocurren cuando una instrucción posterior lee un resultado generado por una instrucción anterior, pero que podría no estar listo todavía. Los riesgos de WAW ocurren cuando dos instrucciones escriben en el mismo registro. La instrucción posterior debe confirmar su escritura solo después de que se complete la instrucción anterior.
Este modelo funciona razonablemente bien para un solo problema, procesador canalizado en orden. Para extraer más rendimiento, desea hacer dos cosas: (1) Aumente el ancho de emisión de instrucciones y (2) permita que las instrucciones procedan fuera de orden.
Emitir instrucciones fuera de servicio abre nuevos desafíos. Por un lado, ahora te abres a un nuevo tipo de dependencia: dependencias / riesgos de escritura después de leer (WAR). Los riesgos de WAR surgen cuando una instrucción posterior escribe en un registro que lee una instrucción anterior. En una máquina OoO, la instrucción posterior podría emitirse antes que la instrucción anterior. Debe existir algún mecanismo para garantizar que la instrucción anterior aún reciba la entrada correcta.
Otra fuente de dolor son las excepciones precisas: si emite instrucciones fuera de orden y una de ellas desencadena una falla, ¿cómo desenrolla la ejecución de OoO para que el manejador de fallas vea un estado de la máquina que sea consistente con la ejecución secuencial?
Eso nos lleva al algoritmo de Tomasulo y al cambio de nombre del registro.
La realización clave detrás del algoritmo de Tomasulo es que la mayoría de las veces, los nombres de registros arquitectónicos simplemente sirven como identificadores para conectar la salida de una instrucción a una o más entradas de instrucciones. Es decir, los nombres de registro arquitectónicos reales no son importantes la mayoría de las veces. Una vez que conecta la salida de una instrucción a la entrada de otra instrucción, puede enviar ambas a la tubería, rastreando solo la dependencia entre esas instrucciones.
En el algoritmo de Tomasulo, cada instrucción emitida (y, por lo tanto, el resultado de la instrucción pendiente) recibe una estación de reserva. La estación de reserva rastrea las entradas a la instrucción y si la instrucción se ha completado. La estación de reserva también contiene el resultado de esa instrucción.
Aquí es donde entra el cambio de nombre de registro. Cuando emite una instrucción en el algoritmo de Tomasulo, realmente lo asocia con una estación de reserva. El resultado de esa instrucción aterrizará en el registro de esa estación de reserva. Un archivo de cambio de nombre de registro realiza un seguimiento de qué registro en la máquina tendrá el valor más actualizado para un registro arquitectónico dado, como se ve en la siguiente instrucción en la secuencia de instrucciones.
Por ejemplo, suponga que tiene la siguiente secuencia de instrucciones:
.
MPY R0, R1, R2; R2 = R0 * R1
MPY R3, R4, R0; R0 = R3 * R4
AGREGAR R0, R2, R5; R5 = R0 + R2
El primer MPY escribe en R2. El segundo MPY escribe en R0. El ADD agrega esos dos resultados juntos.
Existe una dependencia WAR entre los dos MPY, ya que el segundo MPY escribe en R0, mientras que el primer MPY lee R0. Normalmente, esto obligaría a los MPY a ejecutarse en secuencia, frustrando nuestros intentos de emitirlos en paralelo o fuera de orden.
Tomasulo resuelve esto mediante el archivo de cambio de nombre del registro, reescribiendo el ADD para decir “Agregar el resultado de la primera multiplicación al resultado de la segunda multiplicación”. El archivo de cambio de nombre dice, en el momento en que ADD emite, que el valor asociado con R2 vendrá del primer MPY, y el valor asociado con R0 vendrá del segundo MPY.
Supongamos que hay más de un multiplicador disponible. El primer MPY se ejecutará cuando R0 y R1 estén disponibles. Cuando se complete, transmitirá su finalización, actualizando su registro de estación de reserva y un registro de propósito general para mantener el resultado. El segundo MPY se ejecutará cuando R3 y R4 estén disponibles. Cuando finalice, transmitirá su finalización, actualizando su estación de reserva y un registro de propósito general para mantener el segundo resultado.
Cuando el ADD emita su propia estación de reserva, observará los resultados de todas las unidades. Cuando vea que los resultados se preparan desde la primera multiplicación (en última instancia, destinada para R2) y desde la segunda multiplicación (en última instancia, destinada para R0), capturará esos resultados y ejecutará el ADD cuando todas sus entradas estén disponibles. Y cuando el ADD complete la ejecución, escribirá su propio resultado en su estación de reserva y transmitirá el resultado destinado finalmente al registro arquitectónico R5.
Ahora hay un poco que agité a mano aquí: los MPY pueden completarse en un orden diferente al orden del programa. Cuando completan, transmiten su finalización, actualizan el registro de su estación de reserva (para que otras instrucciones que lo vean puedan obtener los resultados) y actualizan un registro de propósito general. ¿Pero qué registro de propósito general actualizan?
Aquí es donde entran las excepciones precisas y la diferencia entre los registros físicos y los registros arquitectónicos. Hay más registros físicos en el archivo de registro de propósito general que registros arquitectónicos.
En el algoritmo original de Tomasulo, según tengo entendido, cada resultado se compromete a su registro de estación de reserva, y también se vuelve a escribir en su registro arquitectónico. La escritura en el registro de la estación de reserva se transmite, por lo que las instrucciones que esperan el resultado saben cómo capturarlo, pero de lo contrario, el resultado también aterriza en un registro arquitectónico.
Esto significa que los resultados aparecen en el archivo de registro arquitectónico fuera de servicio, y una excepción expondría el hecho de que la máquina se quedó fuera de servicio. Este modelo no admite excepciones precisas.
Para mejorar esto, la máquina necesita realizar un seguimiento de qué instrucciones se han comprometido realmente, en términos del orden original del programa. Es decir, si se produce una excepción en una instrucción dada, las instrucciones que aparecen antes en la secuencia del programa original deben completarse, y las instrucciones que aparecen después en la secuencia del programa original deben aparecer para que nunca hayan sucedido.
Un enfoque para esto es agregar un segundo archivo de registro de cambio de nombre: el archivo de cambio de nombre comprometido. En este modelo, cada nuevo resultado obtiene una nueva posición en el archivo de registro general. El archivo de registro general es mucho más grande de lo que podría sugerir el archivo de registro arquitectónico. El archivo de cambio de nombre confirma qué registro físico en el archivo de registro general corresponde a cada registro arquitectónico, sobre la base de todas las instrucciones que están completamente retiradas (es decir, confirmadas).
Al agregar un archivo de cambio de nombre comprometido, el procesador puede manejar excepciones precisas, descartando limpiamente las instrucciones que se emitieron más allá del punto de la excepción.
Independientemente de si utiliza el algoritmo base de Tomasulo o el algoritmo mejorado que admite excepciones precisas, necesita un archivo de cambio de nombre para realizar un seguimiento de dónde proviene cada resultado de la instrucción. En el modelo impreciso, sin un archivo de cambio de nombre, obligaría a cada instrucción a esperar a que cada una de sus entradas provenientes de otras instrucciones en vuelo se vuelva a escribir en el archivo de registro general. También tendría que retrasar la emisión de instrucciones que causan los peligros WAR y WAW.
Ni siquiera estoy seguro de que pueda hacer que el modelo preciso funcione con una versión cobarde del algoritmo de Tomasulo que carece de un mecanismo de cambio de nombre.
Pido disculpas si mi descripción se revuelve un poco al final. El editor de texto de Quora no se presta a una larga exposición o edición cuidadosa. Siéntase libre de publicar solicitudes de aclaraciones o señalar errores en mi descripción.