4 - Planificacion Dinamica PDF

Preview

Summary

Download 4 - Planificacion Dinamica PDF

Description

Hasta ahora hemos visto que los procesadores en pipeline ejecutan varias instrucciones simultáneamente pero manteniendo el mismo orden del programa, es decir, dadas dos instrucciones i y j de un programa cuyo orden lógico es primero i y después j, al ejecutarlo en el pipeline, primero se arranca i y después se arranca j. También hemos visto que algunas unidades funcionales pueden requerir múltiples ciclos para su etapa de ejecución (operaciones multiciclo), dando lugar a que las instrucciones puedan terminar fuera de orden. No obstante, la emisión de las instrucciones siempre se ha hecho en orden. Como hemos podido ver, esta ejecución “ordenada” de las instrucciones puede dar lugar a riesgos o peligros debidos a dependencias de datos o a problemas estructurales, los cuales pueden acabar generando paradas del pipeline con la consiguiente pérdida de rendimiento. Para aliviar esta pérdida de prestaciones, el compilador puede tratar de planificar el orden de las instrucciones de tal manera que se minimicen los riesgos o dependencias de datos. Esto se conoce como planificación estática. En este capítulo vamos a abordar otra vía para minimizar las paradas debidas a las dependencias de datos: ejecutando las instrucciones fuera de orden, esto es, mediante planificación dinámica de instrucciones, según la cual, las instrucciones pueden arrancarse fuera del orden del programa establecido por el compilador. Así, ahora vamos a ver dos nuevos modelos de ejecución de las instrucciones (distintos del pipeline simple que hemos visto hasta ahora) que implementan planificación dinámica mediante dos técnicas: el Algoritmo del Marcador (scoreboard) y su evolución, el Algoritmo de Tomasulo.

Arquitectura de Computadores

Planificación Dinámica - 1

Como hemos visto hasta hora, para que un procesador pueda ejecutar varias instrucciones simultáneamente, tiene que tener una arquitectura segmentada (en pipeline), disponer de múltiples unidades funcionales, o ambas cosas. Nosotros trataremos con procesadores segmentados y con varias unidades funcionales. Veamos el fragmento de código de arriba. La instrucción SUB no puede arrancar su ejecución puesto que la dependencia que tiene la instrucción ADD respecto a DIV causa la parada del cauce, aunque SUB no tiene ninguna dependencia de datos de ninguna instrucción en el cauce. Cuando no hay múltiples unidades funcionales, la instrucción SUB no tiene más remedio que esperar. Por otra parte, si tenemos múltiples unidades funcionales (para sumas, divisiones, etc.), la parada del cauce puede hacer que algunas de las unidades funcionales queden ociosas, cuando hay instrucciones que sí podrían ejecutarse en ellas, pero que el orden de ejecución lo impide. Esta limitación a una ejecución eficiente puede eliminarse si no se requiere la ejecución en orden. Obviamente, no se puede alterar alegremente el orden de ejecución de cualquier grupo de instrucciones del programa, pero anteriormente ya hemos visto situaciones en las que sí se puede modificar el orden de ejecución de algunas instrucciones sin modificar la semántica del programa.

Arquitectura de Computadores

Planificación Dinámica - 2

Para permitir la ejecución fuera de orden vamos a tener que modificar nuestro cauce clásico. Para empezar, la etapa F (Fetch) se encargará, como ya sabemos, de ir extrayendo instrucciones, pero en lugar de entregárselas directamente a la siguiente etapa, las dejará en un buffer o cola de instrucciones. La etapa D se ocupaba de la decodificación de la instrucción, comprobación de riesgos estructurales y de datos, y alimentación de operandos. Ahora la vamos a descomponer en dos etapas consecutivas: • Emisión: Toma una instrucción del buffer de instrucciones, la decodifica y se comprueban los riesgos estructurales (por ej. que la unidad funcional que se necesita, está disponible). • Lectura de operandos: Se espera hasta que no haya riesgos de datos y, a continuación, se leen los operandos. La instrucción queda lista para pasar a la unidad funcional que le corresponda. En este nuevo pipeline, todas las instrucciones entran en orden en la etapa de Emisión, pero una instrucción puede detenerse en esta etapa si hay riesgos estructurales, o puede adelantar a otra instrucción parada en Emisión, y pasar a la etapa de Lectura de Operandos, por lo que entraría en la etapa de Ejecución ¡fuera de orden!.

Arquitectura de Computadores

Planificación Dinámica - 3

Los procesadores con planificación dinámica presentan estas ventajas: •  Permite la gestión de ciertos casos en los que no es fácil conocer las dependencias en tiempo de compilación, como, por ejemplo, cuando se hace referencia a datos que no están en registros, sino en direcciones de memoria, lo cual, además, simplifica el diseño del compilador. •  Aprovechan los retardos imprevistos, como los debidos a los fallos de caché (el dato no está en la caché y hay que ir a buscarlo a memoria principal), ejecutando otras instrucciones mientras espera el dato de la memoria. •  Distintos procesadores de la misma familia pueden compartir la arquitectura, pero también pueden ofrecer distintas configuraciones de su cauce, es decir, más o menos unidades funcionales o estaciones de reserva. Con la planificación dinámica se permite aprovechar eficientemente las características del pipeline concreto sobre el que se ejecuta el programa compilado para una arquitectura genérica (sin especificar las peculiaridades de cada procesador de la familia). Por el contrario, también tienen ciertos inconvenientes: •  Para ofrecer todas las ventajas anteriores, hay que complicar notablemente el hardware, haciéndolo más caro. •  La planificación dinámica trae consigo la ejecución fuera de orden, lo que también implica terminación fuera de orden, y esto significa la aparición de riesgos de datos de tipo WAR y WAW. •  Complica mucho el tratamiento de los riesgos de control, en especial, el tratamiento de las interrupciones.

Arquitectura de Computadores

Planificación Dinámica - 4

Vamos a ver aquí dos técnicas para la implementación de la planificación dinámica. Comenzaremos con el llamado Método del Marcador y, posteriormente, un refinamiento de éste, denominado Algoritmo de Tomasulo. Aunque en estos dos modelos, las instrucciones también se van a ejecutar en varias etapas o pasos, no se va a seguir el mismo modelo del cauce segmentado convencional en el que en cada etapa (de cada unidad funcional) solamente hay una instrucción en un momento dado, ya que ahora en cada etapa podrán intervenir varias instrucciones.

Arquitectura de Computadores

Planificación Dinámica - 5

El método del marcador fue implementado antiguamente por el supercomputador CDC 6600 con el nombre de Scoreboard, cuyo objetivo era obtener el rendimiento óptimo de una instrucción por ciclo, por lo que simplemente intenta ejecutar una instrucción lo antes posible (siempre que no hubiera riesgos estructurales). Así, cuando la siguiente instrucción para ejecutar está detenida, otras instrucciones pueden ser “emitidas” y ejecutadas si no dependen de ninguna instrucción activa o detenida. El módulo denominado “Marcador” se encarga de controlar la emisión, la ejecución de las instrucciones y la detección de riesgos. Para conseguir la ejecución “fuera de orden” se requiere que múltiples instrucciones estén en su etapa de Ejecución simultáneamente, para lo cual se necesitan múltiples unidades funcionales simples, segmentadas, o ambas cosas. Nosotros supondremos que disponemos de dos multiplicadores, dos sumadores, una unidad de división y una unidad de aritmética entera (para referencias a memoria, bifurcaciones y operaciones con enteros). Todas las instrucciones pasan por el Marcador, donde se construye un registro con las dependencias de datos y se comprueba si se pueden leer los operandos y arrancar la ejecución. Si no se puede arrancar la ejecución, el Marcador se queda comprobando cada cambio en el cauce hasta que se pueda arrancar la ejecución. Para evitar riesgos de tipo WAR y WAW, el Marcador también controla cuándo una instrucción puede escribir su resultado.

Arquitectura de Computadores

Planificación Dinámica - 6

El método del Marcador se sirve de un pipeline de 4 etapas o pasos más unas estructuras de datos en las que se registran las dependencias de datos que pueda haber entre los operandos de las instrucciones que han entrado en el cauce. Cada instrucción debe pasar por cuatro etapas (aquí no vamos a considerar el acceso a memoria). Las cuatro etapas que veremos a continuación en detalle son: • Emisión • Lectura de Operandos • Ejecución • Escritura del resultado

Arquitectura de Computadores

Planificación Dinámica - 7

En la etapa de Emisión se comprueba que la unidad funcional que necesita la instrucción está libre y que ninguna otra instrucción activa tiene el mismo registro de destino. Si es así, el Marcador emite la instrucción y actualiza su estructura interna de datos. Al comprobar que ninguna otra instrucción activa tiene el mismo registro de destino, se garantiza que no hay riesgos WAW. Si hay un riesgo estructural (no está disponible la unidad funcional necesaria) o riesgo de datos WAW, se detiene la emisión de la instrucción ¡y no se emiten más instrucciones hasta que desaparezcan tales riesgos! Esto quiere decir que la emisión de instrucciones se realiza de una en una y en orden. Cuando una instrucción se detiene en esta etapa, puede dar lugar a que el buffer de instrucciones se llene, dependiendo de si el buffer es de una única entrada (en cuyo caso la alimentación de instrucciones se detiene inmediatamente), o se trata de una cola con capacidad para múltiples instrucciones.

Arquitectura de Computadores

Planificación Dinámica - 8

En la Lectura de Operandos el Marcador comprueba la disponibilidad de los operandos de entrada. Un operando está disponible si no hay ninguna instrucción activa ya emitida que vaya a escribir en él. Si alguna instrucción activa tiene que escribir en alguno de los operandos fuente de nuestra instrucción, se espera a que esto ocurra. Cuando los operandos están disponibles, el Marcador le indica a la unidad funcional que lea los operandos de los registros correspondientes y que comience la ejecución. En esta etapa, el Marcador resuelve los riesgos RAW dinámicamente, y las instrucciones pueden enviarse a ejecución fuera de orden. Obsérvese que puede haber varias instrucciones (que no tengan conflictos) en cada una de las etapas de Lectura, Ejecución y Escritura. El número de instrucciones que haya en un momento dado dependerá del número de buses de acceso a los registros y del número de unidades funcionales disponibles. Igualmente, el que las etapas de lectura y escritura en un mismo registro puedan solaparse en el mismo ciclo (con dos subciclos distintos) dependerá también de la implementación concreta. Aquí supondremos que las lecturas y escrituras se realizan en subciclos distintos, por lo que pueden solaparse.

Arquitectura de Computadores

Planificación Dinámica - 9

La unidad funcional recibe los operandos y arranca la ejecución. Cuando la ejecución ha finalizado, se le notifica al Marcador que el resultado está disponible. Téngase en cuenta que esta etapa puede requerir múltiples ciclos de reloj para ciertas operaciones en coma flotante.

Arquitectura de Computadores

Planificación Dinámica - 10

Cuando el Marcador sabe que la unidad funcional asignada a la instrucción ha finalizado la operación, comprueba que no haya riesgos WAR y, en caso necesario, detiene la escritura del resultado hasta que desaparezca el riesgo. En general, la escritura del resultado de una instrucción j no se permite cuando hay una instrucción i que la precede que no ha leído sus operandos y que uno de ellos está en el mismo registro en el que se escribe el resultado de la instrucción j. Por ejemplo: dadd R1,R2,R3 dmul R2,R7,R8 Cuando ya no hay riesgo WAR, el Marcador le indica a la etapa de Escritura que escriba el resultado en el registro de destino.

Arquitectura de Computadores

Planificación Dinámica - 11

El Marcador utiliza tres estructuras de datos en las que se mantienen el estado de los objetos que controla. Las tres estructuras son: • Estado de las instrucciones • Estado de las unidades funcionales • Estado de los registros Veamos en detalle cada una de estas estructuras.

Arquitectura de Computadores

Planificación Dinámica - 12

La tabla de Estado de las Instrucciones indica la etapa en la que se encuentra cada una de las instrucciones activas, es decir, que han entrado en el cauce.

Arquitectura de Computadores

Planificación Dinámica - 13

La tabla de las Unidades Funcionales indica el estado en que se encuentran éstas, utilizando para ello nueve campos: • Busy Indica si la unidad funcional está ocupada o no. • Op

Es la operación a ejecutar en esa unidad funcional (suma, resta...).

• Fi • Fj , Fk

Es el registro de destino de la operación (en el que se escribirá el resultado). Son los registros que contienen los operandos (registros de entrada).

• Qj , Qk

Son las unidades funcionales que producirán los resultados de los registros Fj y Fk.

• Rj , Rk

Flags indicando si los registros de entrada Fj y Fk están o no están preparados. Se ponen a NO después de leer los operandos.

Arquitectura de Computadores

Planificación Dinámica - 14

Esta tabla del Estado de los Registros de Resultado indica la unidad funcional que escribirá en cada registro que sea destino de alguna instrucción activa. Si una entrada no indica ninguna unidad funcional (por ejemplo, con el valor cero), es que su valor está actualizado.

Arquitectura de Computadores

Planificación Dinámica - 15

En las siguientes páginas vamos a ver cómo se irían procesando las instrucciones del fragmento de código que se muestra arriba, al ejecutar el programa sobre un procesador segmentado con planificación dinámica que utiliza el Método del Marcador. Téngase en cuenta que lo que se va a ir mostrando es cómo fluyen las instrucciones a través de las etapas y cómo van ocupándose las unidades funcionales, no se trata de estructuras de datos propias del Marcador.

Arquitectura de Computadores

Planificación Dinámica - 16

Para cada instrucción indicaremos los ciclos en que se ejecutará cada una de las etapas por las que atraviesa el pipeline, y considerando que todas las instrucciones se van extrayendo de una cola de instrucciones. Así, la primera instrucción, la división, se emite en el 1er. ciclo y se leen sus operandos en el 2º. Su ejecución, que dura 20 ciclos, tiene lugar de los ciclos 3 a 22. La escritura se efectúa en el ciclo 23, pero los riesgos estructurales se comprueban en la etapa de emisión (ciclo1), y si la unidad funcional requerida está libre, queda reservada desde el ciclo 1, liberándose cuando finaliza la operación en ella, que, en este caso, es al término del ciclo 22.

Arquitectura de Computadores

Planificación Dinámica - 17

La segunda instrucción, la suma, se emite en el 2º ciclo. Esta instrucción tiene una dependencia de datos de la instrucción anterior (por F1), lo que supone un riesgo de datos de tipo RAW. Por esto, la instrucción de suma no puede leer F1 hasta que finaliza la escritura de la instrucción anterior (la división), por lo que queda detenida en la etapa de Lectura de Operandos hasta que la instrucción anterior escriba su resultado en F1, lo que tiene lugar en el primer subciclo del ciclo 23, por lo que el registro de entrada F1 se lee en el segundo subciclo del ciclo 23. A continuación, se ejecuta en la unidad funcional de la suma, que lo hace en dos ciclos (24 y 25). Por último, escribe el resultado en F4, en el ciclo 26. En la parte inferior de la figura vemos que la segunda instrucción tiene reservada y ocupada unidad funcional de suma desde el ciclo 2 al 25. Esto que se muestra es una descripción, a posteriori, de lo sucedido. No quiere decir que en el ciclo 2 se reserve la unidad funcional hasta el 25, pues, obviamente, no puede saber a priori cuándo va a quedar libre. Simplemente indica que esa unidad funcional de suma estuvo ocupada desde el ciclo 2 hasta el 25.

Arquitectura de Computadores

Planificación Dinámica - 18

La tercera instrucción (división) se puede emitir en el ciclo 3, y leer sus operandos en el ciclo 4, pues no tiene dependencias de datos. A continuación se ejecuta en la otra unidad funcional de división durante 20 ciclos (5-24). Por último, se escribe el resultado en F5 en la etapa de Escritura (ciclo 25). Como se puede ver, esta instrucción no tiene ningún riesgo estructural ni de datos, por lo que se puede ejecutar sin producir ninguna detención ¡y termina antes que la instrucción 2!

Arquitectura de Computadores

Planificación Dinámica - 19

En el ciclo siguiente (el 4) se puede emitir la siguiente instrucción (la suma de la instrucción 4), pues al estar disponible la segunda unidad funcional de sumas, no hay riesgo estructural. Sus operandos de entrada son F8 y F9, que no se utilizan en ninguna otra instrucción activa, luego tampoco hay riesgos de datos RAW, por lo que se leen en el ciclo 5. La instrucción ya puede pasar a ejecutarse en la unidad funcional de sumas durante dos ciclos (6 y 7). En el ciclo 8, se podría proceder a escribir el resultado en el registro F3, pero la instrucción 2 está detenida en su etapa de Lectura de Operandos, esperando para poder leer F1 (resultado de la instrucción 1), por lo que tenemos un riesgo WAR, pues si en el ciclo 8, la instrucción 4 escribe en F3, la instrucción 2 no leería el valor adecuado de F3 en el ciclo 23, que es cuando queda libre del riesgo RAW por F1, y puede leer los operandos. Así, la escritura del resultado de la instrucción 4 en F3, debe detenerse hasta el ciclo 24, después de que la instrucción 2, haya leído F3 en el ciclo 23. Aunque la instrucción 1 también lee F3, lo hace en el ciclo 2, por lo que no hay riesgo WAR con las instrucción 4.

Arquitectura de Computadores

Planificación Dinámica - 20

Ciclo 5. Preparados para emitir la instrucción 5, una división, pero las dos unidades funcionales de división están todavía ocupadas. Una realiza la división en los ciclos 3-22; la otra, en los ciclos 5-24. La primera unidad funcional de división finaliza la instrucción 1 en el ciclo 22, luego la división de la instrucción 5 debe esperar su emisión hasta el ciclo 23 para que desaparezca el riesgo estructural. En el ciclo siguiente (24), esta instrucción 5 debe leer sus operandos (F3 y F10). Observemos que el registro F3 lo escribe, como resultado, la instrucción anterior, también en el ciclo 24, sin embargo no hay ningún riesgo RAW, ya que la escritura se produce en el 1er. subciclo y la lectura tiene lugar en el 2º subciclo. Así, en el ciclo 25 puede iniciarse la ejecución en su unidad funcional, hasta el ciclo 44. En el ciclo 45 se escribe el resultado en F7.

Arquitectura de Computadores

Planificación Dinámica - 21

Si en el ciclo 23 se emitió la instrucción 5, en el 24 se querría emitir la instrucción 6, pero hay un riesgo WAW, por lo que la instrucción se detiene. Obsérvese que tanto esta instrucción como la anterior escriben el resultado en el mismo registro, F7. La instrucción 6 (la suma) queda detenida hasta que la instrucción 5 escribe su resultado en el ciclo 45, por lo que la instrucción 6 se emite en el ciclo 46. En el siguiente ciclo (47) se pueden leer sus operandos (F11 y F12), ya que no dependen de ninguna otra instrucción. En los ciclos 48 y 49 se ejecuta en una unidad funcional de suma, pues las dos están libres. Y en el ciclo 50 se escribe el resultado en F7. Como ya habíamos comentado, los riesgos WAW suelen ser fruto de una programa...