fbpx
Wikipedia

Algoritmo de marcador

Julio 25, 2022

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 qué 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 está siendo utilizada o no
    • Op (Operación): Operación a realizar en la unidad (por ejemplo: MUL, DIV or MOD)
    • Fi: Registro de destino
    • Fj,Fk: Números de registros fuente
    • Qj,Qk: Unidades funcionales que producirán el resultado a leer de los registros fuente Fj, Fk
    • Rj,Rk: Marcas que indican cuando los registros Fj, Fk 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 ( 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 no 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.

Véase también

Enlaces externos

  • Planificación dinámica - Marcador el 20 de agosto de 2013 en Wayback Machine.
  • 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.
  •   Datos: Q1242829

Julio 25, 2022
algoritmo, marcador, algoritmo, marcador, método, centralizado, utilizado, 6600, para, planificar, manera, dinámica, segmentación, forma, instrucciones, pueden, ejecutadas, fuera, orden, cuando, existen, conflictos, hardware, está, disponible, marcador, regist. El algoritmo de marcador es un metodo centralizado utilizado en el CDC 6600 para planificar de manera dinamica la segmentacion de forma que las instrucciones pueden ser ejecutadas fuera de orden cuando no existen conflictos y el hardware esta disponible En un marcador se registran las dependencias de datos de cada instruccion Las instrucciones son emitidas solamente cuando el marcador determina que ya no hay conflictos con las instrucciones previamente ejecutadas o en ejecucion Si una instruccion sufre la insercion de una burbuja por considerarse insegura su ejecucion el marcador vigila el flujo de ejecucion de las instrucciones hasta que todas las dependencias hayan sido resueltas pudiendo asi ser relanzada la instruccion detenida Indice 1 Etapas 2 Estructura de datos 3 Algoritmo 4 Observaciones 5 Vease tambien 6 Enlaces externosEtapas EditarLas instrucciones son decodificadas en orden y van pasando por las siguientes cuatro etapas Issue Emision El sistema verifica aquellos registros que van a ser leidos o modificados por la instruccion El procesador podra acceder a esta informacion 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 instruccion hasta que todas las instrucciones que pretenden escribir en el mismo registro sean completadas La instruccion tambien es detenida si alguna de las unidades funcionales se encuentra ocupada Read operands Lectura de operandos Una vez que se ha emitido la instruccion y se ha comprobado que todas las unidades funcionales necesarias estan libres la instruccion espera a que los operandos esten disponibles Este procedimiento resuelve las dependencias verdaderas RAW Read after Write ya que los registros que van a ser modificados por alguna otra instruccion no son considerados como disponibles hasta que son realmente modificados Execution Ejecucion Cuando todos los operandos han sido capturados la unidad funcional comienza la ejecucion Una vez que el resultado esta disponible el marcador recibe una notificacion Write Result Escritura de resultados En esta etapa se intenta la escritura del resultado en el correspondiente registro de destino Sin embargo esta operacion se retrasa hasta que las instrucciones que intentan leer los registros en que esta instruccion pretende escribir han completado su etapa de lectura de operandos Esto permite resolver las dependencias WAR Write after Read Estructura de datos EditarPara controlar la ejecucion de las instrucciones el marcador mantiene tres tablas de estados Instruction Status Estados de instruccion Indica para cada instruccion en ejecucion 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 Operacion Operacion a realizar en la unidad por ejemplo MUL DIV or MOD Fi Registro de destino Fj Fk Numeros de registros fuente Qj Qk Unidades funcionales que produciran el resultado a leer de los registros fuente Fj Fk Rj Rk Marcas que indican cuando los registros Fj Fk estan listos Register Status Estados de registro Indica para cada registro que unidad funcional escribira en el su resultado Algoritmo EditarEl 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 displaystyle 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 EditarEl algoritmo de marcador puede insertar burbujas en la etapa de emision si no hay ninguna unidad funcional disponible En este caso instrucciones futuras que podrian ser ejecutadas esperarian hasta que el riesgo estructural fuese resuelto Algunas otras tecnicas como el algoritmo de Tomasulo pueden evitar los riesgos estructurales y resolver las dependencias WAR y WAW mediante el renombre de registros Vease tambien EditarDLX Paralelismo a nivel de instruccion Algoritmo de Tomasulo Ejecucion fuera de ordenEnlaces externos EditarPlanificacion dinamica Marcador Archivado el 20 de agosto de 2013 en Wayback Machine Arquitectura de computadores un enfoque cuantitativo John L Hennessy amp David A Patterson EECS 252 Graduate Computer Architecture Lec XX TOPIC Electrical Engineering and Computer Sciences Berkeley University of California Datos Q1242829 Obtenido de https es wikipedia org w index php title Algoritmo de marcador amp oldid 143439796, wikipedia, wiki, leyendo, leer, libro, biblioteca,

español

, española, descargar, gratis, descargar gratis, mp3, video, mp4, 3gp, jpg, jpeg, gif, png, imagen, música, canción, película, libro, juego, juegos