MPS: Miss-Path Schedulling for Multiple-Issue Processors
En este artículo los autores proponen trasladar el hardware de planificación de instrucciones desde la ruta del procesador hacia la ruta entre la memoria principal y la caché de instrucciones. La planificación de instrucciones se hace cuando se produce un fallo de caché y es necesario traer desde la memoria principal un nuevo bloque. Este nuevo bloque se planifica y se introduce en la cache organizando las instrucciones en grupos sin dependencias. Estos grupos de instrucciones pueden ser enviados en paralelo a las distintas unidades funcionales del procesador, en cierta forma como si se tratara de una instrucción VLIW (Very Long Instruction Word). El algoritmo utilizado para la construcción dinámica de estas instrucciones tipo VLIW se apoya en dos elementos:
a) Una Tabla de Definición y Uso de Registros: Para cada registro almacena la información del último ciclo (más reciente) en el que fue escrito (definido) y leído (usado). Estos datos reciben respectivamente los nombres de def-time y last-used, y la tabla el de def-table.
b) Una Tabla de Reserva (Reservation Table): Tabla en la que anotamos para cada ciclo que instrucción hace uso de las distintas unidades funcionales del procesador.
Para ver como funciona dicho algoritmo, vamos a seguir paso a paso la planificación de un fragmento de programa de ejemplo que aparece en el artículo. Vamos a suponer que tenemos un procesador RISC que dispone de dos ALU enteras y una unidad de acceso a memoria (LD/ST). Los tiempos de latencia para las divisiones y multiplicaciones es de 3 ciclos, 1 para el resto de operaciones ALU y 2 ciclos para las operaciones de memoria. Todas las unidades funcionales están completamente segmentadas, y podemos enviarles un instrucción por ciclo. El procesador por tanto puede enviar 3 instrucciones por ciclo en paralelo.
Instrucción A: Tiene como único operando el registro r6. Como el valor de def-time no está definido, significa que el valor de r6 está disponible y la instrucción A puede enviarse a la unidad LD/ST en el primer ciclo que tenga libre, esto es el 0. En esa caso reservamos la unidad LD/ST en el ciclo 0 en la Tabla de Reserva. Como el tiempo de latencia de esta instrucción es de 2 ciclos, guaradmos en el campo def-time de r2 el valor 2. En el campo last-use de r6 indicamos que se usó por última vez en el ciclo 0.
Register def-use table |
Reservation Table |
A: ld r2, 0(r6) B: add r3, r2, 1 C: mul r4, r2, r9 D: add r8, r2, r7 E: ld r9, 0(r10) |
Instrucción B: Usa como fuente el registro r2. Vemos que el valor de def-time es 2, lo que significa la instrucción B no puede enviarse a una ALU antes de ese ciclo. Buscamos el primer ciclo que libre a partir del ciclo 2. Reservamos el ciclo 2 en una ALU en la Tabla de Reserva. Como el tiempo de latencia de esta instrucción es de 1 ciclo, en def-time de r3 el valor 3 (2+1). En el campo last-use de r2 indicamos que se usó por última vez en el ciclo 2.
Register def-use table |
Reservation Table |
A: ld r2, 0(r6) B: add r3, r2, 1 C: mul r4, r2, r9 D: add r8, r2, r7 E: ld r9, 0(r10) |
Instrucción C: Como la anterior usa como fuente el registro r2, además de r9. El registro r9 no tiene definido def-time, por lo que está disponible y como el valor de def-time es 2, la instrucción C no puede enviarse a una ALU antes del ciclo 2. Reservamos el ciclo 2 en la ALU que queda libre en la Tabla de Reserva. Como el tiempo de latencia de esta instrucción es de 3 ciclos, en def-time de r4 ponemos el valor 5 (2+3). En el campo last-use de r2 y r9 indicamos que se usaron por última vez en el ciclo 2.
Register def-use table |
Reservation Table |
A: ld r2, 0(r6) B: add r3, r2, 1 C: mul r4, r2, r9 D: add r8, r2, r7 E: ld r9, 0(r10) |
Instrucción D: Es un caso parecido al anterior. Como fuentes usa los registro r2 y r7. El valor de def-time de r2 sigue siendo 2, y r7 no lo tiene definido. El primer ciclo libre de una ALU a partir del 2 es el ciclo 3. El tiempo de latencia de esta instrucción es de 1 ciclo, y en def-time de r8 ponemos el valor 4 (3+1). En el campo last-use de r2 y r7 indicamos que se usaron por última vez en el ciclo 3.
Register def-use table |
Reservation Table |
A: ld r2, 0(r6) B: add r3, r2, 1 C: mul r4, r2, r9 D: add r8, r2, r7 E: ld r9, 0(r10) |
Instrucción E: Introducimos aquí un cambio en el código de ejemplo del artículo para explicar como gestiona este algoritmo las antidependencias (WAR). La instrucción tiene como operando fuente r10, que no tiene definido def-time. Podríamos lanzar este instrucción desde el ciclo 0. Como está ocupada la unidad funcional, pasaríamos la instrucción al ciclo 1.
| cycle | ALU | ALU | LD/ST |
| 0 | A | ||
| 1 | E | ||
| 2 | B | C | |
| 3 | D | ||
| 4 | |||
| 5 | |||
| 6 |
Esto provocaría una antidependencia no resuelta entre las instrucciones E y C. La forma de solucionarlo con este algoritmo es añadiendo un control adicional, consistente en comprobar el valor del campo last-use del registro destino. Debemos tomar el valor máximo de los guardados en los campos def-time de los registros fuente y el campo last-use del registro destino como ciclo a partir de cual buscaremos dónde ubicar la operación. En nuestro caso, con last-use de r9 igual a 2, y def-use de r10 de 0, buscaríamos a parir del ciclo 2 =máximo(2,0). Completemos las tablas.
Register def-use table |
Reservation Table |
A: ld r2, 0(r6) B: add r3, r2, 1 C: mul r4, r2, r9 D: add r8, r2, r7 E: ld r9, 0(r10) |
Con este mecanismo añadido se eliminan también las dependencias de salida. Para gestionar la planificación especulativa de saltos se utiliza un registro adicional que guarda el último ciclo para el que se ha planificado una instrucción: el LastestScheduleTime. Cuando se encuentra un salto, y se toma de forma especulativa una de las ramas, las instrucciones correspondientes se planifican a partir de dicho ciclo. De esta forma, si la predicción resulta errónea, es fácil eliminar todas esas instrucciones de la Tabla de Reserva.
El algoritmo se podría dividir en tres pasos diferenciados, lo que nos permitiría hacer una implementación del mismo de forma segmentada. Estos son los pasos:
- Calcular lo más pronto (ScheduleTime) que se puede ejecutar una instrucción comprobando cuándo estarán disponibles sus operandos y la comprobar qué recursos son necesarios (ALU, LD/ST, etc.)
- Buscar a partir del tiempo calculado en el paso anterior (ScheduleTime) un ciclo en el que el recurso esté libre y actualizar dicho tiempo si es necesario.
- Colocar la instrucción en la Tabla de Reserva y actualizar los valores def-time y last-use en la Tabla de Definición y Uso de Registros.
Ejecución Especulativa
Cuando se utiliza ejecución especulativa, se necesita un mecanismo que prevenga que los resultados de instrucciones ejecutadas incorrectamente (Por predicción errónea) sean retirados y usados. Un mecanismo que se acomoda al diseño MSP es el uso de un Buffer de Re-ordenación (Reorder Buffer) con Fichero de Futuro (Future File). Cualquiera de los métodos de predicción existente puede ser usado en está arquitectura. Cuando se realiza una predicción se ha de calcular la dirección de destino del salto. Si es un salto relativo a PC, se puede determinar en la primera fase del pipeline del planificador. Pero en los saltos indirectos basados en un registro, esa dirección no se puede saber, por lo que el MPS para el proceso de planificación (condición de parada). Lo mismo ocurre cuando encuentra un salto hacia atrás, para prevenir el desenrollado de bucles.
Cuando un conjunto de instrucciones planificadas S se ejecuta, el procesador necesita saber cuál va a ser el siguiente plan a ejecutar. Si S no contiene ningún salto, la dirección de la siguiente instrucción a ejecutar sería la dirección de la primera instrucción de S, más el número de instrucciones que contiene (Y por el ancho de palabra, se entiende). Si S contiene algún salto el cálculo de la dirección no se puede realizar cuando finaliza S. En ese caso lo que hace el planificador es calcular dicha dirección examinando las direcciones de las que provienen las instrucciones que ha planificado en S, pasándosela a la máquina para que sea usada al buscar el siguiente plan de instrucciones.
Conclusiones
La ventaja de esta técnica MPS es que, al trasladar la complejidad de la planificación dinámica desde el pipeline hacia la circuitería de carga de caché, permite realizar diseños mucho más agresivos de dicho pipeline en cuanto a reducción de la duración del ciclo de reloj. Se compara en el artículo el diseño MPS frente a uno superescalar, resultando que el rendimiento de ninguno de los dos resulta claramente superior al otro. Sin embargo afirma que los resultados permiten sugerir que los diseños basados en MPS son una alternativa viable sobre todo cuando es posible una reducción de la duración ciclo de reloj.
Resumen del artículo MPS: Miss-Path Schedulling for Multiple-Issue Processors de Sanjeev Banerjia (Hewelett-Packard Labs, Cambridge, MA), Sumedh W. Sathaye (IBM T. J. Watson Research Center, Yorktown Heights, NY), Kishore N. Menezes (Intel Corp., Santa Clara, CA) y Thomas M. Conte (North Carolina State Univ., Raleigh).