stringtranslate.com

Marcador

El cuadro de indicadores es un método centralizado, utilizado por primera vez en la computadora CDC 6600 , para programar dinámicamente instrucciones de modo que puedan ejecutarse fuera de orden cuando no hay conflictos y el hardware está disponible. [1]

En un tablero de resultados, las dependencias de datos de cada instrucción se registran, rastrean y observan estrictamente en todo momento. Las instrucciones se liberan solo cuando el tablero de resultados determina que no hay conflictos con instrucciones emitidas previamente ("en vuelo"). Si una instrucción se detiene porque no es seguro emitirla (o no hay suficientes recursos), el tablero de resultados monitorea el flujo de instrucciones en ejecución hasta que se hayan resuelto todas las dependencias antes de emitir la instrucción bloqueada. En esencia: las lecturas continúan en ausencia de peligros de escritura y las escrituras continúan en ausencia de peligros de lectura.

El marcador es esencialmente una implementación de hardware del mismo algoritmo subyacente visto 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.

  1. Problema : El sistema verifica qué registros serán leídos y escritos por esta instrucción y dónde se detectan conflictos de escritura tras lectura (WAR), lectura tras escritura (RAW) y escritura tras escritura (WAW). Los peligros de RAW y WAR se registran utilizando una Matriz de Dependencia (construida a partir de pestillos SR NOR en el diseño original del 6600) ya que será necesaria en las siguientes etapas. Simultáneamente, se registra una entrada en una segunda Matriz, que registra el orden de instrucción como un Gráfico Acíclico Dirigido . Para evitar dependencias de salida (WAW), la instrucción se detiene hasta que se completen las instrucciones que pretenden escribir en el mismo registro. La instrucción también se detiene cuando las unidades funcionales requeridas están ocupadas en ese momento. Nunca se emite ninguna instrucción a menos que sea completamente rastreable de principio a fin.
  2. Operandos de lectura : después de que se ha emitido una instrucción y se la 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 se realiza cuando se han eliminado las dependencias de escritura (RAW) de todas las demás Unidades. Para evitar la contención del Puerto de Archivo de Registro, un Selector de Prioridad selecciona una Unidad de Cálculo (en el caso de que varias Unidades estén libres de peligros).
  3. Ejecución : cuando se han obtenido todos los operandos, la unidad de cálculo comienza su ejecución. Una vez que el resultado está listo, se notifica al marcador.
  4. Resultado de escritura : en esta etapa, el resultado está listo, pero aún no se ha escrito en su registro de destino. La escritura no puede continuar hasta que la unidad esté libre de todos los peligros de WAR. Los únicos retrasos adicionales aquí se basan en la disponibilidad de los puertos de archivo de registro: en el 6600 se utilizaba un selector de prioridad para seleccionar un resultado por puerto de escritura. Una vez escrito, la unidad se marca como no ocupada y se descartan todos los peligros y estados. Tenga en cuenta que solo en los tableros de puntuación avanzados (aumentados, precisos) con capacidad "Sombra" se evitará (retrasará) la fase de Resultado de escritura. El 6600 original no tenía esta capacidad.

Es fundamental tener en cuenta que las lecturas solo se realizan en ausencia de peligros de escritura y que las escrituras se realizan en ausencia de peligros de lectura . Esto es lógico, pero contrario a las expectativas. En particular, tenga en cuenta que las escrituras deben esperar para escribir después de la lectura para dar a otras unidades la oportunidad de leer el valor actual en un registro, antes de sobrescribirlo con el nuevo. Por eso las escrituras deben esperar hasta que no haya peligros de WAR.

Estructura de datos

Para controlar la ejecución de las instrucciones, el marcador mantiene tres tablas de estado:

El algoritmo original 6600

El algoritmo detallado para el control del marcador, descrito en la patente original, se describe a continuación:

 problema de función ( op , dst , src1 , src2 ) esperar hasta (!Busy[FU] AND !Result[ 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 leer_operandos( FU ) esperar hasta (R j [ FU ] Y R k [ FU ]); R j [ FU ] ← No; R k [ FU ] ← No;
 función ejecutar( FU ) // Ejecuta lo que FU debe hacer
 función write_back( FU ) esperar hasta que (∀f {(F j [f]≠F i [ FU ] O R j [f]=No) Y (F k [f]≠F i [ FU ] O R k [f]=No)}) para cada f hacer si Q j [f]= FU entonces R j [f] ← Sí; si Q k [f]= FU entonces R k [f] ← Sí; Result[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.

El bloqueo sólo se produjo en la etapa de emisión, cuando se detectaron conflictos de "primer orden". Otras técnicas, como el algoritmo de Tomasulo, resuelven además las dependencias de WAW con el cambio de nombre de los registros . El CDC 6600 original probablemente no tenía seguimiento de peligros de WAW simplemente porque sus diseñadores tuvieron que entregar el producto y luego pasaron al 7600: el bloqueo en su lugar 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 de los registros a los marcadores.

Luke Leighton realizó un análisis de ambos algoritmos y describió un proceso de transformación que muestra la equivalencia entre el algoritmo 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 aparición de un peligro de escritura. [6]

Véase también

Referencias

  1. ^ Thornton, James E. (1965). "Operación paralela en el sistema de datos de control 6600". Actas de la conferencia conjunta de informática 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 .
  2. ^ Thornton (1970, pág. 125)
  3. ^ Thornton (1970, pág. 126)
  4. ^ Thornton 1970, pág. 127
  5. ^ Transformando a Tomasulo en Marcadores
  6. ^ Thornton, James (1970). Diseño de una computadora: los datos de control 6600 (PDF) . pág. 126. ISBN 9780673059536.

Enlaces externos