Algoritmo de marcador

El algoritmo de marcador es un método centralizado, utilizado en el CDC 6600 para planificar de manera dinámica la segmentación, de forma que las instrucciones pueden ser ejecutadas fuera de orden cuando no existen conflictos y el hardware está disponible. En un marcador se registran las dependencias de datos de cada instrucción. Las instrucciones son emitidas solamente cuando el marcador determina que ya no hay conflictos con las instrucciones previamente ejecutadas o en ejecución. Si una instrucción sufre la inserción de una burbuja por considerarse insegura su ejecución, el marcador vigila el flujo de ejecución de las instrucciones hasta que todas las dependencias hayan sido resueltas, pudiendo así ser relanzada la instrucción detenida.

Etapas

Las instrucciones son decodificadas en orden y van pasando por las siguientes cuatro etapas:

1. Issue (Emisión): El sistema verifica aquellos registros que van a ser leídos o modificados por la instrucción. El procesador podrá acceder a esta información cuando sea necesario en alguna de las siguientes etapas. Para poder evitar dependencias de salida (WAW - Write after Write) se inserta una burbuja en la instrucción hasta que todas las instrucciones que pretenden escribir en el mismo registro sean completadas. La instrucción también es detenida si alguna de las unidades funcionales se encuentra ocupada.
2. Read operands (Lectura de operandos): Una vez que se ha emitido la instrucción y se ha comprobado que todas las unidades funcionales necesarias están libres, la instrucción espera a que los operandos estén disponibles. Este procedimiento resuelve las dependencias verdaderas (RAW - Read after Write) ya que los registros que van a ser modificados por alguna otra instrucción no son considerados como disponibles hasta que son realmente modificados.
3. Execution (Ejecución): Cuando todos los operandos han sido capturados, la unidad funcional comienza la ejecución. Una vez que el resultado está disponible, el marcador recibe una notificación.
4. Write Result (Escritura de resultados): En esta etapa se intenta la escritura del resultado en el correspondiente registro de destino. Sin embargo, esta operación se retrasa hasta que las instrucciones que intentan leer los registros en que esta instrucción pretende escribir han completado su etapa de lectura de operandos. Esto permite resolver las dependencias (WAR - Write after Read).

Estructura de datos

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

• Instruction Status (Estados de instrucción): Indica, para cada instrucción en ejecución, en que etapa de las 4 se encuentra.
• Functional Unit Status (Estados de unidad funcional): Indica el estado de cada unidad funcional, manteniendo cada una de ellas 9 campos en la tabla:
  • Busy (Ocupado): Indica si la unidad esta siendo utilizada o no
  • Op (Operación): Operación a realizar en la unidad (por ejemplo: MUL, DIV or MOD)
  • F_i: Registro de destino
  • F_j,F_k: Números de registros fuente
  • Q_j,Q_k: Unidades funcionales que producirán el resultado a leer de los registros fuente F_j, F_k
  • R_j,R_k: Marcas que indican cuando los registros F_j, F_k están listos
• Register Status (Estados de registro): Indica, para cada registro, qué unidad funcional escribirá en él su resultado.

Algoritmo

El algoritmo detallado para el control del marcador se describe como sigue:

 function issue(op, dst, src1, src2)
    wait until (!Busy[FU] AND !Result[dst]); // FU can be any functional unit that can execute operation op
    Busy[FU] ← Yes; 
    Op[FU] ← op;
    Fi[FU] ← dst;
    Fj[FU] ← src1;
    Fk[FU] ← src2;
    Qj[FU] ← Result[src1];
    Qk[FU] ← Result[src2];  
    Rj[FU] ← not Qj;
    Rk[FU] ← not Qk;
    Result[dst] ← FU;
 
 function read_operands(FU)
    wait until (Rj[FU] AND Rk[FU]);
    Rj[FU] ← No;
    Rk[FU] ← No;
 
 function execute(FU)
    // Execute whatever FU must do
 
 function write_back(FU)
    wait until ($\forall$f {(Fj[f]≠Fi[FU] OR Rj[f]=No) AND (Fk[f]≠Fi[FU] OR Rk[f]=No)})
    foreach f do
        if Qj[f]=FU then Rj[f] ← Yes;
        if Qk[f]=FU then Rk[f] ← Yes;
    Result[Fi[FU] ] ← 0;
    Busy[FU] ← No;

Observaciones

El algoritmo de marcador puede insertar burbujas en la etapa de emisión si ni hay ninguna unidad funcional disponible. En este caso, instrucciones futuras que podrían ser ejecutadas esperarían hasta que el riesgo estructural fuese resuelto. Algunas otras técnicas como el algoritmo de Tomasulo pueden evitar los riesgos estructurales y resolver las dependencias WAR y WAW mediante el renombre de registros.

Enlaces externos

• Planificación dinámica - Marcador
• Arquitectura de computadores: un enfoque cuantitativo, John L. Hennessy & David A. Patterson
• EECS 252 Graduate Computer Architecture Lec XX - TOPIC, Electrical Engineering and Computer Sciences, Berkeley, University of California.

Véase también

• Paralelismo a nivel de instrucción
• Algoritmo de Tomasulo
• Ejecución fuera de orden