El cuadro de indicadores es un método centralizado, que se utilizó por primera vez en la computadora CDC 6600 , para programar instrucciones dinámicamente para que puedan ejecutarse fuera de orden cuando no hay conflictos y el hardware está disponible. [1]
En un marcador, las dependencias de datos de cada instrucción se registran, se rastrean y se observan estrictamente en todo momento. Las instrucciones se publican solo cuando el marcador determina que no hay conflictos con las instrucciones emitidas previamente ("en vuelo"). Si una instrucción se detiene porque no es seguro emitirla (o no hay recursos suficientes), el marcador monitorea el flujo de ejecución de instrucciones hasta que se hayan resuelto todas las dependencias antes de que se emita la instrucción detenida. En esencia: las lecturas proceden en ausencia de peligros de escritura y las escrituras proceden en ausencia de peligros de lectura.
El marcador es esencialmente una implementación de hardware del mismo algoritmo subyacente que se ve en los lenguajes de flujo de datos , creando un gráfico acíclico dirigido , donde se aplica la misma lógica en el tiempo de ejecución del lenguaje de programación .
Etapas
Las instrucciones se decodifican en orden y pasan por las siguientes cuatro etapas.
- Problema : El sistema verifica qué registros se leen y escriben por esta instrucción y es donde los conflictos GUERRA y RAW y WAW se detectan. Los peligros RAW y WAR se registran usando una Matriz de Dependencia (construida a partir de pestillos SR NOR en el diseño 6600 original), ya que será necesario en las siguientes etapas. Simultáneamente, se registra una entrada en una segunda matriz, que registra el orden de las instrucciones como un gráfico acíclico dirigido . Para evitar dependencias de salida ( WAW - Write after Write), la instrucción se detiene hasta que se completan las instrucciones que pretenden escribir en el mismo registro. La instrucción también se detiene cuando las unidades funcionales requeridas están ocupadas actualmente. * Nunca se emite ninguna instrucción a menos que sea 100% rastreable de principio a fin *.
- Leer operandos : una vez que se ha emitido una instrucción y se ha asignado correctamente al módulo de hardware requerido (denominado Unidad de cálculo en el libro de Thornton), la Unidad espera hasta que todos los operandos estén disponibles. La lectura solo continúa cuando las dependencias de escritura ( RAW - Lectura después de escritura) se han eliminado de todas las demás Unidades. Para evitar la contención del puerto de registro de archivos, un selector de prioridades selecciona una unidad computacional (en el caso de que varias unidades estén libres de peligros).
- Ejecución : Cuando se han obtenido todos los operandos, la Unidad de Computación comienza su ejecución. Una vez que el resultado está listo, se notifica al marcador.
- Escribir resultado : en esta etapa, el resultado está listo pero aún no se ha escrito en su registro de destino. Es posible que la escritura no continúe hasta que la unidad esté libre de todos los peligros ( WAR - Write after Read). Los únicos retrasos adicionales aquí se basan en la disponibilidad de los puertos de archivo de registro: en el 6600 se utilizó un selector de prioridad para seleccionar un resultado por puerto de escritura. Una vez escrito, la unidad se marca como ya no ocupada, y se eliminan todos los peligros y el estado. Tenga en cuenta que solo en los marcadores avanzados (aumentados, precisos) con capacidad "Sombra" se evitará (retrasará) la fase de escritura de resultados. El 6600 original no tenía esta capacidad.
Es fundamental señalar anteriormente que las lecturas solo se realizan en ausencia de peligros de escritura y que las escrituras continúan en ausencia de peligros de lectura . Esto es lógico pero contraindicativo a las expectativas. En particular, tenga en cuenta que Writes debe esperar para escribir después de leer para dar a otras unidades la oportunidad de leer el valor actual en un registro, antes de sobrescribirlo con el nuevo. Por lo tanto, las escrituras deben esperar hasta la ausencia de peligros de WaR.
Estructura de datos
Para controlar la ejecución de las instrucciones, el marcador mantiene tres tablas de estado:
- Estado de la instrucción : Indica, para cada instrucción que se está ejecutando, en cuál de las cuatro etapas se encuentra.
- Estado de la unidad funcional : indica el estado de cada unidad funcional. Cada unidad de función mantiene 9 campos en la tabla:
- Ocupado: indica si la unidad se está utilizando o no
- Op: Operación a realizar en la unidad (por ejemplo, MUL, DIV o MOD)
- F i : registro de destino
- F j , F k : números de registro de origen
- Q j , Q k : Unidades funcionales que producirán los registros fuente F j , F k
- R j , R k : Indicadores que indican cuando F j , F k están listos y aún no se han leído.
- Estado del registro : indica, para cada registro, qué unidad de función escribirá los resultados en él.
El algoritmo 6600 original
El algoritmo detallado para el control del cuadro de indicadores, descrito en la patente original, se describe a continuación:
problema de función ( op , dst , src1 , src2 ) espere hasta (! Ocupado [FU] Y! Resultado [ dst ]); // FU puede ser cualquier unidad funcional que pueda ejecutar la operación op Ocupado [FU] ← Sí; Op [FU] ← op ; F i [FU] ← dst ; F j [FU] ← src1 ; F k [FU] ← src2 ; Q j [FU] ← Resultado [ src1 ]; Q k [FU] ← Resultado [ src2 ]; R j [FU] ← Q j [FU] == 0; R k [FU] ← Q k [FU] == 0; Resultado [ dst ] ← FU;
función read_operands ( FU ) espere hasta (R j [ FU ] Y R k [ FU ]); R j [ FU ] ← No; R k [ FU ] ← No;
función ejecutar ( FU ) // Ejecuta lo que FU deba hacer
función write_back ( FU ) espere hasta (∀f {(F j [f] ≠ F i [ FU ] OR R j [f] = No) Y (F k [f] ≠ F i [ FU ] OR R k [f] = No)} ) Foreach f do si Q j [f] = FU entonces R j [f] ← Sí; si Q k [f] = FU entonces R k [f] ← Sí; Resultado [F i [ FU ]] ← 0; // 0 significa que ninguna FU genera el resultado del registro RegFile [F i [ FU ]] ← valor calculado ; Ocupado [ FU ] ← No;
Observaciones
El libro de Thornton es anterior a la terminología informática moderna.
- Las unidades de función (canalizaciones) se denominaron "unidades de cálculo".
- El "Conflicto de primer orden" cubrió ambos puestos debido a que todas las Unidades estaban ocupadas y también cubrió el conflicto WAW . [2]
- "Conflicto de segundo orden" fue el término utilizado para el conflicto RAW [3]
- "Conflicto de tercer orden" cubrió el conflicto de GUERRA [4]
El bloqueo solo se produjo en la etapa del problema, cuando se detectaron conflictos de "primer orden". Algunas otras técnicas, como el algoritmo de Tomasulo, resuelven adicionalmente las dependencias de WAW con el cambio de nombre del registro . El CDC 6600 original probablemente no tenía seguimiento de peligros WAW simplemente porque sus diseñadores tenían que entregar el producto, y luego pasaron al 7600: en cambio, detenerlo era la opción más conveniente. No hay ninguna razón técnica por la que no se deba agregar el cambio de nombre del registro a los cuadros de indicadores.
Luke Leighton realizó un análisis de ambos algoritmos y se esbozó un proceso de transformación que muestra la equivalencia entre el algoritmo de Tomasulo y el algoritmo 6600 Scoreboard. [5] La resolución de peligros WAW de hecho falta en el algoritmo original: el 6600 se detendría en la primera ocurrencia de un Peligro de Escritura. [6]
- Thornton, James (1970). Diseño de una computadora: Los datos de control 6600 (PDF) . ISBN 9780673059536.
Ver también
Referencias
- ^ Thornton, James E. (1965). "Funcionamiento en paralelo en los datos de control 6600". Actas de la conferencia conjunta de otoño del 27 al 29 de octubre de 1964, parte II: sistemas informáticos de muy alta velocidad . AFIPS '64. San Francisco, California: ACM. págs. 33–40. doi : 10.1145 / 1464039.1464045 .
- ↑ Thornton (1970 , p. 125)
- ↑ Thornton (1970 , p. 126)
- ^ Thornton 1970 , p. 127
- ^ Transformando a Tomasulo en marcadores
- ^ Diseño de una computadora, James Thornton ISBN 9780673059536
- Glenford Myers , "Registro de marcadores en un chip de microprocesador", Patente de los Estados Unidos 4891753
enlaces externos
- Programación dinámica: marcador
- Arquitectura informática: un enfoque cuantitativo , John L. Hennessy y David A. Patterson
- EECS 252 Graduado en Arquitectura de Computadoras Lec XX - TEMA , Ingeniería Eléctrica y Ciencias de la Computación, Berkeley, Universidad de California.
- Ejemplo de marcador