5-Prediccion de saltos - UPM ·...

Para conseguir el rendimiento óptimo de una instrucción por ciclo, otro de los obstáculos que nosencontramos es el de las dependencias de control, esencialmente, los saltos condicionales.Ya vimos que hay soluciones estáticas (en tiempo de compilación) que alivian este problema,como los saltos retardados. Ahora vamos a abordar otras técnicas relacionadas con la predicciónde lo que se determinará en la instrucción de salto condicional: ¿se saltará o no se saltará?.Veremos soluciones de predicción estática (la predicción se hace en tiempo de compilación) y depredicción dinámica (en tiempo de ejecución) para situaciones en las que no se puede predecirfácilmente, de manera estática, el comportamiento de una bifurcación.Las técnicas de predicción que abordaremos aquí van a sopesar las probabilidades de que seproduzca un salto considerando el salto de manera aislada (buffer de predicción de saltos) o surelación con otros saltos de su entorno (predictores globales).También veremos la forma de acortar el tiempo necesario para saber cuál es la dirección del saltomediante el buffer de destinos de saltos.Por último veremos una técnica que combina los predictores locales y los globales en lospredictores adaptativos.

Arquitectura de Computadores Predicción de Saltos - 1

Las estadísticas de los programas indican que los riesgos de control (saltos) se producen conmayor frecuencia que los riesgos de datos (dependencias de datos), por lo que su influencia en eltiempo de ejecución es muy alta.Anteriormente ya hemos abordado la eliminación de los riesgos de control mediante los saltosretardados y la predicción estática. Sin embargo, esto no es suficiente cuando se quiereconseguir una tasa de ejecución de una instrucción por ciclo, por lo que se requieren técnicasadicionales que, ante una instrucción de salto, permitan determinar lo antes posible si se tomaráel salto o no.En un capítulo anterior, ya vimos que el salto se decide en la etapa de Decodificación (D), por loque se pierde un ciclo de reloj en los saltos condicionales. Pues bien, con la predicción dinámicade salto, lo que se pretende es poder conocer, siempre, la dirección de la siguiente instrucción aejecutar en la etapa de alimentación de instrucción (F), lo que supone que los saltoscondicionales ya no originan ningún retardo en el flujo de alimentación de instrucciones.


Comenzaremos con las técnicas de predicción estática, en las que el problema se aborda en latemprana etapa de compilación, y la decisión de la predicción de lo que sucederá en el saltoqueda establecida, a priori, para todas las ejecuciones del programa.


Además de las soluciones estáticas que ya vimos en un capítulo anterior, otra técnica parareducir el problema de las bifurcaciones consiste en intentar predecir si una instrucción debifurcación saltará o no. Por ejemplo, una bifurcación al final de un bucle salta al comienzo deéste todas las veces excepto la última. Según esto, sería ventajoso que cuando el procesador seencuentra una instrucción de salto suponga que el salto sí se va a efectuar realmente, y cuandola etapa de alimentación detecte una bifurcación, empiece a extraer instrucciones de la direcciónde destino del salto. Si una vez que se ejecuta la instrucción de bifurcación, resulta que,efectivamente, se cumple la condición de salto, la ejecución continúa normalmente, pues lasinstrucciones de la dirección del salto son las que ya se están alimentando. Si por el contrarioresulta que no se cumple la condición y, por lo tanto, no se realiza el salto, se debe vaciar elpipeline (desechar todas las instrucciones erróneamente alimentadas) y empezar a alimentar lasinstrucciones que siguen en secuencia.


Si ahora suponemos que el control del bucle se realiza mediante una instrucción al comienzo delmismo, ahora lo normal será suponer que la bifurcación no se tomará hasta la última pasada delbucle. Es decir, hay veces que conviene suponer una cosa y otras veces otra.Esto que hemos visto se denomina ejecución especulativa, pues las instrucciones puedenempezar a ejecutarse antes de que el procesador sepa que las instrucciones alimentadas son lasrealmente correctas. Supongamos que se predice que el salto tendrá lugar, por lo que seempiezan a alimentar instrucciones y a pasarlas a las siguientes etapas del pipeline antes de quela instrucción de bifurcación finalice su etapa de ejecución. ¡Y si al ejecutar la bifurcación no serealiza el salto! ¡Nos encontramos que algunas instrucciones ya se han empezado a ejecutar enlas etapas anteriores!Con ejecución especulativa se debe tener cuidado de que en las etapas anteriores a la deejecución no se modifiquen registros o posiciones de memoria hasta que no se confirme que lapredicción realizada ha sido la acertada.


La repetición de la bifurcación que se toma en el bucle la puede detectar el compilador yestablecer la predicción mediante un cierto código de operación en la bifurcación, lo que quieredecir que, en ejecución, siempre que se alimente esa instrucción de bifurcación se hará la mismapredicción. Por esto, se la conoce como predicción estática.En otras situaciones puede resultar complicado predecir estáticamente. En estos casos, lapredicción se puede mejorar si se realiza dinámicamente, para lo cual el hardware delprocesador debe establecer la posibilidad de que haya o no salto cada vez que se encuentre unacierta instrucción de bifurcación.En próximos apartados abordaremos algunas técnicas de predicción dinámica de saltos.


Como hemos visto, la predicción ante un salto puede ser “saltar” o “no saltar”, para decidir pordónde continúa extrayendo instrucciones.Para la arquitectura MIPS, con una porción de código concreta y con los mismos datos, vamos aver lo que sucede cuando la predicción es “no saltar” y cuando es “saltar”, para un caso en el quela condición de salto se cumple.Predicción NO SALTAR: Después de alimentar la instrucción de salto, se continúa con laDecodificación, pero hasta el final de esta etapa no se sabrá si habrá que saltar o no. Como lapredicción es “no saltar”, en la etapa F se alimenta la siguiente instrucción en memoria. Al final dela etapa D se ve que se ha cometido un fallo en la predicción, por lo que habrá que eliminar lainstrucción daddi del cauce y empezar a extraer y ejecutar la instrucción de destino del salto. Seha perdido un ciclo de tiempo.Predicción SALTAR: Igual que antes, después de alimentar la instrucción de salto, se continúacon la Decodificación. Como la predicción es “saltar”, en este ciclo se querría extraer la siguienteinstrucción de la dirección del salto, pero como hasta el final de la Decodificación tampoco seconoce la dirección del salto, en este ciclo no se puede extraer ninguna instrucción, y hay queesperar al final de la Decodificación para poder alimentar la instrucción de destino del salto.Como vemos, en MIPS, ante una condición que establezca que se debe saltar, se pierde un ciclotanto con una predicción de “saltar” como de “no saltar”. Por el contrario, si se hace unapredicción de NO SALTAR (y se alimenta la siguiente instrucción en memoria) y se acierta, no sepierde ningún ciclo en espera a que finalice la etapa D.Por lo que hemos visto, en MIPS 64 no tiene ninguna utilidad predecir “Tomar el salto”, porlo que su predicción siempre es NO SALTAR.


Ahora abordaremos la técnicas de predicción de salto que se utilizan en tiempo de ejecución, porlo que denomina predicción dinámica de saltos.Como ya dijimos anteriormente, en algunas situaciones puede resultar complicado predecirestáticamente lo que sucederá en un salto. En tales casos, la predicción se puede mejorar si serealiza dinámicamente, para lo cual, durante la ejecución, el hardware del procesador debeestablecer la posibilidad de que haya o no salto cada vez que se encuentre una cierta instrucciónde bifurcación. Para ello, en la CPU se debe llevar la cuenta de los resultados de las últimasejecuciones de cada bifurcación. Ciertos estudios estadísticos dicen que conservando solamenteel resultado de la última ejecución (con un bit) ya se obtiene una gran probabilidad de acierto (delorden del 90%) y con la historia de las cuatro últimas ejecuciones (dos bits) se mejoraligeramente; manteniendo una historia mayor, la mejora es despreciable.En los próximos apartados veremos con cierto detalle diversas técnicas de predicción dinámicade saltos.


El modelo más simple de predicción de saltos es el Buffer de Predicción de Saltos o BPB(Branch-Prediction Buffer), el cual consiste en una tabla indexada por los bits de menor peso dela dirección de la instrucción de bifurcación.Para cada entrada de la tabla simplemente hay un bit que indica si la bifurcación se tomó o no laúltima vez que se pasó por ella.Con esta simple tabla, ni siquiera se sabe si la predicción corresponde a la instrucción de salto encurso pues pueden producirse colisiones, es decir, que la predicción de esa entrada de la tabla lapudo establecer otra instrucción de salto cuyos bits de menor peso de su dirección coincidierancon los de la dirección de la instrucción actual. No obstante, lo peor que puede suceder en casode colisión, es que se tome una predicción equivocada, y las consecuencias no son graves, puesla predicción se entiende como un consejo, de tal manera que si al comprobar la condición delsalto, la predicción no resulta ser acertada, simplemente hay que abortar la ejecución de lainstrucción erróneamente alimentada, empezar de nuevo a extraer la instrucción de destino delsalto de la dirección correcta y establecer de nuevo el valor de la predicción en la tabla; eso sí,con la correspondiente pérdida de tiempo, que es precisamente lo que se quiere evitar con unabuena predicción.Obviamente, cuantos más bits de dirección se utilicen para indexar la tabla, menos posibilidadesde colisión habrá.


En el diagrama de arriba se indica el comportamiento de este sistema de predicción dinámica desaltos.Lo primero que se comprueba en la tabla es la predicción: saltar o no saltar. Según estapredicción se alimenta la siguiente instrucción en secuencia o la de la dirección de destino delsalto.A continuación se comprueba si la predicción fue acertada o no. Si lo fue, simplemente secontinúa con la instrucción alimentada; si no fue acertada, se debe abortar y desechar lainstrucción erróneamente extraída, alimentar la instrucción de la dirección adecuada e invertir elbit de predicción.


Este modelo simple de predicción de un bit tiene una pega. Aunque una bifurcación se tome casisiempre (como en el caso de las instrucciones de control de un bucle), cuando no se cumpla lacondición de seguir en el bucle, tendremos un fallo en la predicción y se modificará el valor del bitde predicción. Así, cuando se vuelva a entrar en el bucle, aunque lo normal sería predecir que seva a seguir en el bucle, nos encontraremos con que se predice no saltar, pues así se habráestablecido en la ejecución anterior (en la que se salió del bucle), lo que dará lugar a otro error enla predicción.Este error en la predicción originará dos fallos por cada ejecución del bucle, en lugar de uno (elde la salida del bucle). Así, la importancia de esta “pega” dependerá de la frecuencia con que seejecute cada bucle.


Para remediar la pega del buffer de predicción de un bit, lo que hacemos es aumentar la memoria históricaa dos bits, con lo que se obtiene el diagrama de 4 estados de arriba.Ahora, para modificar una predicción, no basta con un fallo, se necesitan dos fallos consecutivos.Hay dos estados estables: uno para SALTAR (11) y otro para NO SALTAR (00). Si estamos en el estado(11) SALTAR, y se produce un error en la predicción, se pasa al estado (10), en el que se sigueprediciendo SALTAR. Si en este estado se vuelve a producir un fallo en la predicción, se pasa ya a unestado (00) en el que se predice NO SALTAR. Si estando en (10) se acierta en la predicción de SALTAR,se vuelve al estado estable de (11) SALTAR.El comportamiento para cuando se está en el estado estable (00) NO SALTAR, es equivalente al estado(11) comentado.Un buffer de predicción de saltos puede implementarse como una pequeña memoria caché a la que seaccede con la dirección de la instrucción de salto en la etapa F, o bien con un par de bits asociados acada bloque en la caché de instrucciones. Si la instrucción se decodifica como una bifurcación conpredicción de saltar, la siguiente instrucción se alimenta tan pronto como se sepa la dirección del salto; encaso contrario (predicción de no saltar), la extracción de instrucciones continúa secuencialmente.El paquete de medición de prestaciones SPEC89 con un buffer de predicción de 4096 entradas arrojóuna tasa de acierto del 82% al 99%. En el 2005, un buffer de 4096 entradas ya se consideró pequeño, porlo que ya se utilizan buffers mayores, lo que probablemente conduce a mejores resultados.Como se puede ver, un buffer con 4K entradas de 2 bits tiende a comportarse como un buffer de tamañoinfinito (acierto del 99%), por lo que aumentar el número de bits de historia sin cambiar el esquema,apenas tiene impacto en los resultados prácticos.A este tipo de autómatas se les conoce con el nombre de contadores de saturación.


Veamos cómo se comportaría este mecanismo de predicción en MIPS. Recordamos que con elBuffer de Predicción de Saltos, la predicción de si se debe o no se debe saltar se realiza en laetapa de extracción de instrucción (F).Si se predice NO SALTAR, simplemente hay que continuar con la siguiente instrucción ensecuencia. La dirección de la siguiente instrucción se calcula en la etapa F por lo que se puedecontinuar la ejecución sin ningún retardo.Si se predice SALTAR, hasta el final de la siguiente etapa (D), no se sabe la dirección del salto,pues, en MIPS, la dirección del salto se calcula en esta etapa. Por tanto, mientras se estáejecutando la etapa D de la instrucción de bifurcación, no se puede ejecutar la etapa F de laalimentación de la siguiente instrucción. Es decir, que después de una instrucción de bifurcacióncon predicción de saltar hay que esperar un ciclo más, a que finalice la etapa de Decodificación,para saber la dirección de destino del salto y poder alimentar la instrucción siguiente.Aunque la predicción se ha hecho en la etapa F, no ha servido de nada, pues la dirección delsalto se calcula un ciclo más tarde.Como vemos, este tipo de predicción de saltos no es útil para procesadores en los que ladirección de destino del salto no se calcula en la etapa F.Parece que, en estas circunstancias, lo que sería muy interesante es poder conocer la direccióndel salto en la misma etapa en la que se hace la predicción.


Como hemos concluido en el Buffer de Predicción de Saltos, para algunos tipos de procesadoresno solamente es beneficioso conocer la predicción del salto, sino también la dirección del destinodel salto.Así, la tabla de predicción de saltos se convierte en un Buffer de Destinos de Saltos o BTB(Branch Target Buffer). Ahora la tabla tiene dos campos en cada entrada: la dirección de lainstrucción de bifurcación y la dirección del destino del salto. Si la dirección de la instrucción debifurcación no está en la tabla, significa que la predicción es NO SALTAR. También puededeberse a que no se haya pasado antes por esta bifurcación, en cuyo caso también se toma lapredicción de NO SALTAR. Si la dirección sí está en la tabla, se interpreta como SALTAR.En el Buffer de Predicción de Saltos, cada entrada de la tabla contenía un único campo: lapredicción, y se accedía a la tabla indexando con los bits de menor peso de la dirección de lainstrucción de bifurcación, lo cual, como ya vimos, daba lugar a colisiones. No obstante, estascolisiones no eran graves, pues lo peor que podía pasar era que la predicción obtenida fueraerrónea, por lo que habría que perder algún ciclo en alimentar la instrucción correcta.Ahora, con el Buffer de Destinos de Saltos, si se produjese una colisión se tomaría una entradaerrónea de la tabla y si se confirma que la predicción de saltar es correcta, se habría tomado unadirección de salto incorrecta, que corresponde a otra bifurcación distinta, y que conllevaría unaejecución incorrecta del programa.Para evitar las colisiones, cada entrada de la tabla debe tener la dirección completa de lainstrucción de bifurcación a la que corresponde la entrada.Obsérvese que se trata de una predicción con una historia de solo dos estados (un bit).


En este diagrama se muestra el comportamiento de este sistema de predicción basado en elbuffer de destinos de saltos. Para ello, veremos el tratamiento de una instrucción de saltocondicional a través de un pipeline con este sistema de predicción.Como vemos, todo comienza en la etapa de extracción (F) en la que al mismo tiempo que se va amemoria a extraer una nueva instrucción con la dirección indicada en el Contador de Programa(PC), se comprueba si esa dirección se encuentra en el buffer de destinos de saltos.En la etapa D se comprueba la condición de salto y se pasa a la etapa de ejecución. En estaetapa E, el comportamiento depende de si se ha acertado en la predicción o no. Si se acertó,continúa la ejecución normal con la instrucción alimentada según la predicción (y que ahora seencontrará en la etapa D).En caso de fallo en la predicción, lo primero que se debe hacer en la etapa de E de la instrucciónde salto es abortar la ejecución de la instrucción erróneamente alimentada. A continuación, ytambién en esta etapa E:• Si el fallo se debió a una predicción errónea de “no saltar”, se debe introducir la dirección de la

instrucción de salto en el BTB, aconsejando “saltar” para el futuro.• Si el fallo se debió a una mala predicción de “saltar”, lo que se debe hacer ahora eliminar del

BTB la entrada de esta instrucción.Seguidamente se debe extraer la instrucción correcta y continuar la ejecución.


Según lo visto en la página anterior, si se utiliza el BTB con MIPS, no se produce ningún retardoen los saltos con acierto en la predicción.Recordamos que, en MIPS, sin BTB, ante una bifurcación evaluada como cierta, habría quedetener la alimentación de instrucciones hasta que se tenga la dirección del salto al final de laetapa D.


En cambio, si falla la predicción de “no saltar”, provocará dos ciclos de retardo, ya que en la etapa deejecución de la instrucción de salto habrá que abortar la ejecución de la instrucción erróneamentepredicha, y hasta el siguiente ciclo no se alimentará la instrucción correcta.La secuencia de ejecución es la siguiente:• Ciclo 1: Se alimenta la instrucción de salto BNE.• Ciclo 2: Como la predicción es “no saltar”, se alimenta la siguiente instrucción en secuencia (XOR). En

este mismo ciclo, se realiza la decodificación de la instrucción de salto. En esta etapa se comprueba sise cumple o no la condición de salto y, si se debe saltar, también se obtiene la dirección de la siguienteinstrucción a alimentar.Al término de la decodificación de la instrucción de salto, ya se conoce el error de la predicción.

• Ciclo 3: Se aborta la ejecución de la instrucción erróneamente predicha (XOR). También se debeactualizar el BTB para incluir en él la dirección de esta instrucción de salto. Aunque ya se conoce ladirección de la siguiente instrucción a alimentar y ejecutar, ya que desde la etapa E se está accediendoal BTB para actualizarlo (insertando en él la dirección de la reciente instrucción de salto), no se puedealimentar la siguiente instrucción, pues en la etapa F se debe consultar el BTB con cada instrucciónextraída, aunque no sea una instrucción de salto (ya que hasta la etapa D no se decodifica y se averiguacuál es el cometido de cada instrucción).

• Ciclo 4: El acceso al BTB ha quedado libre, por lo que ya puede alimentarse la siguiente instrucción aejecutar (AND) y realizar la consulta obligatoria al BTB.

• Ciclo 5: Continúa la decodificación y la ejecución normal en el cauce.En el caso de fallar ante una predicción de “saltar”, el proceso es similar al descrito para el fallo ante “nosaltar”, pues ante un fallo en cualquier predicción, el error se conoce al término de la etapa D, y hay queutilizar la etapa E para abortar la ejecución de la instrucción errónea y actualizar debidamente el BTB.


Ante un fallo en la predicción, uno de los ciclos que se pierde se debe a que desde la etapa E dela instrucción de salto se debe modificar el BTB y, al mismo tiempo, desde la etapa F se querríaalimentar la siguiente instrucción y consultar el BTB, por lo que nos encontramos ante unproblema estructural de acceso simultáneo al BTB desde dos etapas distintas.Este ciclo de retardo que acabamos de describir, se podría ahorrar si el BTB fuera de doblepuerto, lo que permitiría realizar simultáneamente lecturas y escrituras.Otra forma de eliminar este ciclo de retardo consiste en dividir las etapas F y E en dos subciclos.En el primer subciclo, se escribiría el BTB desde la etapa E. Por otra parte, en la etapa F, en elprimer subciclo se alimentaría la instrucción y en el segundo subciclo se consultaría el BTB.


En la tabla presentada anteriormente como Buffer de Destinos de Saltos, la única informaciónutilizada para realizar la predicción era si la dirección de la bifurcación se encontraba en la tabla.Si estaba en la tabla, se predecía SALTAR; si no estaba, se predecía NO SALTAR; es decir, secomportaba como un mecanismo de predicción de un bit.Ya vimos que aumentando la historia se obtienen mejores resultados (especialmente, en lascondiciones de salida de los bucles), así que se puede añadir un bit más de estado a la tabla dedestinos de saltos para minimizar las equivocaciones en las predicciones.El hecho de que la dirección de la instrucción de salto esté o no en el BTB, más este nuevo bit depredicción, permiten utilizar el BTB como algo parecido a un predictor de 2 bits. (Tiene 3 estados:“No está”, “Está y es 0” y “Está y es 1”).


Una variación del buffer de destinos es almacenar en la tabla no solo la dirección de destino delsalto, sino la instrucción que hay en la dirección de destino del salto.Esto permite una optimización denominada branch folding, mediante la cual se pueden realizarsaltos incondicionales en “cero ciclos”.Ya que la única función de un salto incondicional es modificar el valor del Contador de Programa(PC), cuando el buffer de destinos indica un acierto (la dirección de la instrucción de salto está enel buffer) y se trata de un salto incondicional, lo único que tiene que hacer el pipeline es sustituirla propia instrucción de salto incondicional por la almacenada en el buffer de destinos y continuarla ejecución con la instrucción sustituida (la de destino del salto). Por otra parte, también habráque modificar el valor del PC para que se continúe alimentando instrucciones a partir de la nuevadirección de destino del salto.En el fragmento de código que se muestra arriba, se puede ver que el salto incondicional J ETQestá ubicado en la dirección 2032, y la dirección de ETQ es 2168. Estos son los eventos que seproducen en la ejecución de este fragmento:• En la etapa F se comprueba que la instrucción de salto está en el buffer de destinos de saltos.• Se aborta la ejecución de la instrucción de salto incondicional.• Se trae la instrucción de destino (ADD R1,R2,R3) al pipeline y se introduce directamente en la

etapa D.• Se actualiza el PC para seguir alimentando instrucciones de la dirección siguiente a la

instrucción de destino.• Continúa la ejecución de la instrucción de destino del salto.


Un buen porcentaje de aciertos es fundamental para mantener un promedio elevado deinstrucciones procesadas por ciclo. Por esto, ha habido bastantes propuestas de procedimientosde predicción para aumentar la tasa de aciertos respecto a los procedimientos sencillos. Entreellos están los esquemas de predicción de dos niveles. Como su nombre indica, estos esquemasutilizan dos niveles de información para realizar la predicción. Por un lado se guarda informaciónde comportamiento del salto (tomado/no tomado) que ha tenido la instrucción en sus últimasejecuciones. Por otro, también se utilizan los bits de estado del autómata de predicción quehemos visto en el Buffer de Predicción de Saltos.En el ejemplo de arriba se muestran los dos niveles comentados, donde la tabla con la “historiade este salto” contiene la información de lo que sucedió con las últimas ejecuciones de ésainstrucción de salto. El “esquema de predicción dinámica del salto” contiene los bits que indican elestado del autómata de predicción para la instrucción, tal como vimos anteriormente en el BPB.Como vemos, en cualquier caso, toda la información considerada para hacer la predicción estábasada en la historia de la propia instrucción de salto, esto es, en información local al salto.Otra posibilidad de los predictores multinivel es utilizar información correspondiente alcomportamiento reciente de otras instrucciones de salto distintas, como es el caso de lospredictores globales.


Los mecanismos de predicción de una bifurcación que hemos visto hasta ahora, únicamentetienen en cuenta el comportamiento reciente de una instrucción de bifurcación para predecir elcomportamiento futuro inmediato de esa instrucción bifurcación.La precisión de la predicción puede mejorarse si también se considera el comportamiento de lasúltimas instrucciones de bifurcación ejecutadas (instrucciones distintas de la que se estáprediciendo su futuro comportamiento) y que pueden estar relacionadas con el comportamientode la instrucción de salto actual, dando lugar a los predictores globales o correlacionados(correlating predictors).Veamos un ejemplo en la página siguiente.


En este fragmento de código, si se considera aisladamente el comportamiento de la bifurcación(C), no parece que sea fácil o inmediato predecir si se tomará el salto o no.En cambio, si se atiende a la historia reciente de los saltos (A) y (B), sí se puede determinar si secumplirá o no la condición del sato (C).Resulta fácil ver que …Si se toma el salto (A), la variable a tomará el valor cero. Lo mismo sucederá con el salto (B), quesi se cumple la condición, la variable b también tomará el valor cero.Así, al llegar a la bifurcación (C), si se tomaron los saltos de (A) y (B), es fácil concluir con que lasvariables a y b tienen el valor cero, por lo que se puede predecir que la condición del salto secumplirá.Este es un ejemplo sencillo de cómo el comportamiento global de varias bifurcaciones puedeayudar en la predicción de otras.A estos predictores se les denomina predictores globales, de dos niveles, o correlacionados(correlating predictors).


Un descriptor global se describe mediante la tupla (G,L), donde:• G es el número de bifurcaciones globales que se consideran en la predicción.• L es el número de bits empleados en la predicción local de la instrucción de bifurcación en

curso.Según esto, de los predictores que hemos visto anteriormente, los que solamente contemplan lahistoria del último salto, se describirían como un predictor (0,1), es decir, no utiliza ningún saltoglobal, y solamente emplea un bit para la historia de esa bifurcación (dos estados: se saltó o nose saltó).Los predictores con más historia, como los de 4 estados vistos anteriormente, serían del tipo(0,2), pues utilizan 2 bits para codificar los 4 estados posibles que describen la historia.


En esta página y las dos siguientes se muestra cómo serían las tablas de los predictores globalesde tres configuraciones distintas: (1,1), (1,2) y (2,2).En el predictor (1,1) que mostramos arriba, se dispone de una tabla de predicción para las últimasinstrucciones de salto ejecutadas, indexadas por su dirección en memoria. Cada entrada, ademásde la dirección de la instrucción, contiene dos campos, correspondientes a si el último salto globalse tomó o no se tomó. A su vez, cada uno de estos dos campos contiene un predictor local de unbit, correspondiente a la propia instrucción de salto. La predicción local de un bit indica si para lapredicción global elegida, interesa tomar o no tomar el salto.Para elegir la rama SI o NO del último salto global, solamente hay que tener un registro de 1 biten el que se guarda el comportamiento de la última instrucción de salto ejecutado, indicando si elsalto se tomó o no. En general, para un predictor global (m,n), simplemente hay que disponer deun registro de desplazamiento de m bits en el que se van guardando los comportamientos (salto -no salto) de las últimas m instrucciones de bifurcación. Con estos m bits se indexa dentro de latabla de predicción, dentro de la entrada correspondiente a la dirección de la instrucción de saltocuyo comportamiento se quiere predecir.


En el predictor (1,2), se dispone igualmente de una tabla de predicción para las últimasinstrucciones de salto ejecutadas, indexada por su dirección en memoria.Como en el caso (1,1), cada entrada contiene dos campos, correspondientes a si el último saltoglobal se tomó o no se tomó. Ahora, con el predictor (1,2), cada campo de la tabla contiene dosbits, correspondientes a un predictor local de 2 bits como el visto en el Buffer de Predicción deSaltos.


Obsérvese que cuando se considera un predictor global que considera los dos últimos saltosglobales, las combinaciones de historia de estos dos saltos son las 4 siguientes:• No se tomaron ninguno de los dos (No, No)• No se tomó el primero y sí el segundo (No, Si)• Se tomó el primero, pero no el segundo (Si, No)• Se tomaron los dos saltos (Si, Si)Como en los casos anteriores, para cada una de estas entradas de la tabla se dispone de dos bitsque se corresponden con los de los predictores locales de 2 bits vistos en el Buffer de Predicciónde Saltos.El tamaño que ocupa el campo de estado en una tabla de predicción de saltos, para unapredicción correlacionada del tipo (m,n), es el siguiente:

Nº bits utilizados = 2m x n x nº de entradas en la tabla

Ahora se utiliza una mezcla de información global (últimas 2 instrucciones de salto) más elautómata de predicción local simple de la propia instrucción de salto en ejecución.Estos esquemas de predicción global pretenden aprovechar la información propia del contexto enel que se encuentra la instrucción de salto actual.


Existe la posibilidad de definir esquemas de predicción a partir de la hibridación de otros, deforma que para cada instrucción de salto se selecciona el esquema más adecuado en cada caso.Un ejemplo de estos predictores híbridos son los predictores adaptativos o “por torneo”(tournament predictors).


Los predictores adaptativos (tournament predictors) utilizan un esquema de predicción local y otroglobal, y seleccionan la predicción de uno de ellos según el estado de un contador de saturacióno diagrama de estados visto en Buffer de Predicción de Saltos, en el que se requiere un ciertonúmero de fallos consecutivos para cambiar de estrategia.Por ejemplo, se toma el predictor global con los estados 00 y 01, y el predictor local con losvalores 10 y 11. Si se parte de elegir el comportamiento del predictor global, ante dos fallosconsecutivos, se cambia al predictor local. Igualmente, si se producen dos fallos consecutivos delpredictor local, se cambia a la estrategia del predictor global.


5-Prediccion de saltos - UPM ·...

Documents

Transcript of 5-Prediccion de saltos - UPM ·...