Predicción de saltos

En general las instrucciones de salto son muy habituales en el código y por lo tanto los riesgos asociados a estas también, por lo que la predicción de saltos es algo inévitable en cualquier procesador moderno. Recordemos brevemente los 2 tipos de predictores dinámicos más sencillos. Uno es el predictor de 1 bit, y simplemente predice que un salto hará lo mismo que hizo la vez anterior. El 2º es el predictor de 2 bits, cuya máquina de estados es la siguiente:En este caso se tiene en cuenta lo que ha sucedido en los 2 últimos saltos. En el diagrama de estados, 'T' significa 'Taken', es decir que se salta y 'NT' significa 'Not Taken', es decir que no se toma el salto. Como puede verse, si un salto se ha tomado sistemáticamente, hace falta que no se salte 2 veces seguidas para cambiar la predicción. Este predictor permite evitar los fallos del predictor de 1 bit al salir y entrar en los bucles, pero todavía es susceptible de mejora.

El predictor del que vamos a hablar es el predictor adaptativo de 2 niveles, originalmente propuesto por Tse-Yu Yeh y Yale N. Patt en 1991 en el paper "Two-Level Adaptative Training Branch Prediction". Hay variaciones sobre el esquema original que se utilizan en los procesadores modernos.

La idea original es dividir el predictor en 2 estructuras. Por una parte un historial de saltos y por otra una tabla con un historial de patrones. En la primera tabla, para cada instrucción de salto, se almacenan en registros de desplazamientos la información de si se tomó o no en las anteriores 'n' ejecuciones. Un '1' significa que sí mientras un '0' que no se saltó. Si por ejemplo un salto se toma 3 veces seguidas y a la 4ª no, el valor de su historial de saltos será '1110'. Este valor no se utiliza directamente para hacer la predicción, sino que sirve de índice para mirar en la 2ª tabla, la que contiene los patrones de comportamiento del salto. El valor que leemos de esta segunda tabla es en realidad el estado de una máquina de estados como puede ser el predictor de 1 bit o el de 2 bits que hemos visto anteriormente. Veamoslo con un esquema.
Cómo se puede ver, básandose en el historial de saltos tenemos el índice con el que buscar en la tabla de patrones, que nos devolverá el estado con el cual haremos la predicción definitiva. Cuando el salto se resuelva definitivamente, podremos actualizar el estado correspondiente.

Veamos un ejemplo, supongamos que tenemos un salto que siempre se toma 3 veces seguidas, la 4º no se toma y este patrón se repite indefinidamente. Tras unas cuantas ejecuciones de dicha instrucción, tendremos información almacenada en la tabla de patrones, para diferentes índices. Por ejemplo, para el índice '1011' el estado almacenado indicará que hay que tomar el salto, ya que en las anteriores veces siempre se ha saltado. Sin embargo para el índice '0111' el estado almacenado en la tabla debe indicar que no hay que tomar el salto.

Este diseño ha sido el origen de una familia de predictores que mantienen 2 estructuras (una con un historial de saltos y otra con el comportamiento), pero pueden diferenciarse en 3 aspectos:

• El historial de saltos se guarda por instrúcción (P), es global (G), en cuyo caso solo hay un registro o se guarda una entrada por cada N saltos (S).
• La tabla de patrones es de tipo dinámica o adaptativa (A) o estática (S).
• La tabla de patrones tiene entradas para cada instrucción de salto (p), para conjuntos de N saltos (s) o son globales (g).

Según estos 3 parámetros decimos que tenemos un predictor PAg en el caso del expuesto en el paper de Yeh y Patt, ya que el historial de saltos se almacena para cada instrucción de salto (P), la tabla de patrones guarda un estado dinámico (A) y es una tabla global (g), es decir no guarda valores diferentes para diferentes instrucciones de salto. Por ejemplo el predictor GAg es a veces conocido como gshare y lo utilizan los últimos procesadores tanto de AMD como de Intel.

Los procesasdores modernos hacen una predicción de saltos muy compleja ya que esto puede suponer una ventaja apreciable de rendimiento sobre sus competidores. En la actualidad es bastante común que los procesadores tengan predictores híbridos, es decir, mezclen la estimación de distintos tipos de predictores, como puede ser uno de 2 niveles GAg con uno de 2 bits. Además pueden incluir predictores especializados en detectar bucles o en predecir las direcciones de retorno de llamadas a funciones entre otros.

Patxi Astiz

Resolución de riesgos

En la actualidad, como ya hemos visto, la mayoría de los procesadores son RISC y su arquitectura se basa en muchos puntos en la arquitectura MIPS, que se ve en la siguiente imagen:


Como se puede ver en la imagen, el procesador está segmentado en 5 etapas, que son:

1. Emisión de instrucciones
2. Decodificación de instrucciones
3. Ejecución
4. Acceso a memoria
5. Escritura de resultados

En teoría, un procesador de este tipo podría finalizar una instrucción por ciclo pero en la práctica hay una serie de circunstancias que hacen que no sea así. A estas circunstancias las llamamos riesgos. Veremos 3 tipos de riesgos y qué se puede hacer para evitarlos o minimizarlos.

En primer lugar hay riesgos estructurales. Estos se dan cuando 2 o más instrucciones necesitan utilizar el mismo recurso a la vez. Si por ejemplo intentamos leer una instrucción a la vez que un dato de memoria (LOAD), nos encontramos con un riesgo estructural. Hay varias formas de actuar ante una situación así:

• Que todas las instrucciones en conflicto menos una esperen a otro ciclo.
• Replicar recursos.
• Si el recurso lo permite, establecer turnos de uso dentro de un ciclo.

Por ejemplo, para resolver el riesgo que se ha planteado en el parrafo anterior, los procesadores MIPS duplican la memoria, pasando a tener una de instrucciones y una de datos. Cada solución tiene su inconveniente. Si hacemos que las instrucciones esperen, el procesador está perdiendo rendimiento. Si replicamos recursos, la fabricación será más cara. Si establecemos turnos, el recurso debe ser lo suficientemente rápido para relizar varias operaciones por ciclo, lo que seguramente aumente la complejidad y el precio.

El segundo tipo de riesgos que nos podemos encontrar son los riesgos de datos y son de alguno de estos 3 tipos:

• RAW (Read After Write): Se produce cuando una instrucción necesita el resultado de una anterior que aún no se ha computado. Por ejemplo:
  

ADD R3,R1,R4
SUB R9,R3,R7

• WAR (Write After Read): Sucede cuando una instrucción escribe en un registro que lee una instrucción anterior, como en este ejemplo:

ADD R3,R1,R4
SUB R1,R7,R8

Si la 2ª instrucción termina antes de que la 1ª lea sus operandos, el valor de R1 será incorrecto.

• WAW (Write after Write): Se produce cuando una instrucción escribe en un registro en el que también escribe otra instrucción anterior, como en este ejemplo:

ADD R3,R1,R4
SUB R3,R8,R5

En este caso, si la 2ª instrucción termina antes que la primera, cuando esta lo haga modificará el valor de R3 incorrectamente.

Para evitar estos riesgos, se pueden utilizar las siguientes técnicas:

• Se puede parar la ejecución hasta que la instrucción correspondiente haya terminado
• Si nos fijamos en el diagrama del principio, tras la fase de ejecución ya podemos tener el resultado de la operación por si una posterior lo necesita. Si modificamos el procesador para conectar la salida de la ejecución directamente con la decodificación de instrucciones, podemos minimizar los riesgos RAW. Esto está implementado en los procesadores MIPS.
  
• Como no todas las instrucciones tienen dependencias entre sí, podemos reordenarlas en tiempo de compilación de manera que las que sí tienen dependencias estén los más separadas que se pueda. De esta manera se minimizan los riesgos vistos anteriormente.
  

El último tipo de riesgos son los riesgos de control. Aparecen cuando hay un salto condicional. La resolución del salto no es inmediata, por lo que no sabemos cual es la siguiente instrucción hasta que la instrucción pase por la fase de ejecución. Esto hace que el procesador tenga que pararse momentáneamente. Para mitigar esto podemos hacer lo siguiente:

• Como ya hemos dicho, una posibilidad es pararse hasta que se resuelva el salto
• El procesador predice si se salta o no. En caso de acertar no hay penalización. Si no, el resultado es el mismo que si se hubiera parado.
• Se añade lógica a la fase de decodificación de instrucción para saber si se toma el salto lo antes posible. De todas formas en esta arquitectura habría un ciclo en el que todavía no se ha resuelto el salto. Para evitar perderlo, ese ciclo se utiliza para ejecutar (si es posible) una instrucción que no dependa del salto. Esto último puede realizarlo el procesador o el compilador.
  

Aunque en todos los casos parar la ejecución, o lo que es lo mismo intercalar instrucciones NOOP (no operation) en el flujo de ejecución evita todos los riesgos, esta solución siempre reduce el rendimiento del procesador y hay que recurrir a otras técnicas que añaden más o menos complejidad al procesador. Más adelante veremos cómo en la práctica las técnicas que se utilizan son más complejas que las descritas y los procesadores son capaces de reordenar las instrucciones dinámicamente para evitar los riesgos que hemos visto, evitando las paradas y la pérdida de rendimiento que conllevan.

Patxi Astiz

CISC y RISC

Una de las primeras decisiones a la hora de diseñar un procesador es el conjunto de instrucciones. Básicamente hay 2 tipos diferentes, que son CISC y RISC. Vamos a ver en que consiste cada uno de ellos.

CISC significa Complex Instruction Set Computer. Los procesadores de este tipo tienen un conjunto de instrucciones amplio y que realizan operaciones complejas entre operandos en memoria o en registros. Este tipo de procesadores son los primeros que se desarrollaron. Los motivos para seguir esta estrategia a la hora de diseñar este tipo de conjunto de instrucciones fueron muchos. En aquella época era habitual programar en lenguaje ensamblador por lo que instrucciones de este tipo hacían el procesador más sencillo de cara al programador. Se consideraba más sencillo diseñar un procesador CISC que un compilador más complicado. De hecho en muchas ocasiones ni se disponía de uno. Otro motivo era que al describir con una sola instrucción acciones más o menos complejas, que de otra manera supondrían varias instrucciones más sencillas, se ahorraba memoria que resultaba cara y de acceso lento. Más adelante, según se extendían los lenguajes de alto nivel y los compiladores, se añadían instrucciones muy especificas, que no estaban pensadas para ser usadas para programar en ensamblador, pero que eran prácticas para el compilador, ampliando y haciendo más complejo el conjunto de instrucciones. El problema de estos procesadores es que son dificiles de optimizar. Hay muchas instrucciones y algunas demasiado complejas, mientras que los recursos hardware a la hora de diseñar un procesador son limitados. También se dificulta el paralelismo, debido a lo heterogeneo del conjunto de instrucciones.

Más adelante surgió la idea de limitar el conjunto de instrucciones y hacer que cada una haga una tarea sencilla. A los procasadores que utilizan este tipo de estrategia se les conoce como RISC (Reduced Instruction Set Computer). Este tipo de procesadores que aparecieron desde el final de los años 70, se basan en operaciones load-store que permiten pasar datos de memoria a registro y viceversa y operaciones básicas cuyos operandos siempre son registros. De esta manera lo que en un procesador CISC suponía una instrucción, puede y suele traducirse en varias instrucciones RISC. Las ventajas de esto es que cada instrucción es más sencilla por lo que puede ejecutarse más rápidamente y no hay tanta diferencia en el tiempo de ejecución de instrucciones diferentes. También se puede fijar el tamaño de una instrucción. Por todo esto la segmentación y el paralelismo en la ejecución es más sencilla para el diseñador del procesador. También se limita la gestión del acceso a memoria y su retardo a 2 únicas instrucciones.

Existen otras tecnologías como VLIW y EPIC, aunque RISC y CISC son las que se utilizan en la gran mayoría de los casos.

Vistas las diferencia y teniendo en cuenta lo que han evolucionado los compiladores desde su aparición, es lógico que RISC sea lo que utilizan todos los procesadores modernos.

Antes de terminar, una puntualización. Los procesadores que utilizamos están basados en la arquitectua x86 que utiliza un conjunto de instrucciones de tipo CISC. En la época de los 486 (segmentados) y los primeros Pentium, (superescalares) estos procesadores optimizaban ciertas instrucciones en detrimento de otras. Las instrucciones optimizadas eran un subconjunto similar a lo que sería un procesador RISC. En la actualidad los procesadores convierten las instrucciones CISC en una o varias micro-operaciones según convenga al diseño del procesador que se hace siguiendo la filosofía RISC.

Patxi Astiz

Breve historia de las APIs gráficas

Aunque en un principio era habitual que en una aplicación accediera directamente al hardware gráfico, según aumentó su complejidad se comenzaron a utilizar APIs que cumplieran con un estándar para abstraer al programador de la tarjeta gráfica. De esta manera se evitaba el esfuerzo que suponía escribir código específico para cada modelo de hardware gráfico.

El desarrollo del primer estándar comenzó en 1972 cuando el ACM SIGGRAPH (Association for Computing Machinery's Special Interest Group on Computer Graphics and Interactive Techniques) formó el grupo Graphics Standards Planning Committee. Del trabajo de este grupo surgió "Core" en 1977, que se trata del primer estándar gráfico que sirvió de base a las que serían las primeras APIs. La primera de ellas fue GKS (Graphic Kernel System) que se estandarizó al principio de los 80 y es el conjunto de la propuesta del instituto DIN con algunas modificaciones tomadas de "Core". Aunque "Core" tenía en cuante los gráficos en 3D, GKS solo contemplaba gráficos vectoriales en 2D. Para superar esta limitación se propuso utilizar un estándar diferente llamado PHIGS (y su posterior ampliación PHIGS+) o utilizar GKS-3D, que es un superset que permite especificar y generar gráficos en 3D. Finalmente ambos coexistieron.

Por otra parte, en esta época (principios de los 90), Silicon Graphics era la empresa lider en la informática gráfica y había creado su propio API propietario para sus productos. Este se llamaba IRIS GL, que se consideraba muy superior a los estándares mencionados anteriormente, aunque solo disponible para los clientes de Silicon Graphics. La llegada y crecimiento de la competencia, que utilizaba PHIGS y extensiones de esta API, hizo que la compañía se replanteara su estrategia y surgió OpenGL como un estándar gráfico independiente del resto del sistema operativo, sistema de ventanas, etc... De esta manera cualquier fabricante podia escribir un driver y permitir al desarrollador utilizar OpenGL. Finalmente en 1992 se constituyó el ARB (architectural review board), un grupo formado por varias empresas que mantiene y expande la especificación. De esta manera, si uno o varios fabricantes añaden una nueva funcionalidad al hardware, puede proponer una extensión a la API que permita hacer uso de esta mejora.




Las tarjetas gráficas con GPU comienzan a llegar a los ordenadores domésticos en la última mitad de los 90, principalmente de la mano de 3dfx. Estas tarjetas tienen que tener un precio moderado por lo que no pueden tener toda la funcionalidad de una estación de silicon graphics utilizando OpenGL. La estrategia que siguieron es la de utilizar un API con una cantidad limitadad de llamadas, totalmente implementada en el hardware. A este API le llamaron Glide y durante varios años fue el que dominó este sector del mercado. Un hito especialmente importante fue MiniGL, que consistía en un driver que implementaba el subconjunto de llamada de OpenGL que utilizaba la versión de quake con soporte para esta API. Más adelante salieron más versiones de este driver que incluían más y más llamadas. De esta manera OpenGL apuntaba como una posible API para las tarjetas gráficas de consumo y Glide se fue abandonando en favor de esta según la competencia de 3dfx (principalmente ATI y nVidia) mejoraba sus productos y los superaba en rendimiento y en ventas.

Por esta época, Microsoft que formaba parte de los fundadores del ARB de OpenGL decide impulsar su propia API, llamada Direct3D, que competiría con Glide (en un primer momento) y OpenGL. Las primeras versiones fueron muy impopulares entre los programadores, que preferían utilizar OpenGL y aunque hubo un primer intento por unificar OpenGL y Direct3D en un único API, este fracasó y Microsoft continuó evolucionando su API propietaria.

Desde el final de los 90, OpenGL es la API mayoritaria excepto en el campo de los juegos para plataformas Windows donde coexiste con Direct3D y para Xbox, donde tan solo se utiliza Direct3D. Ambas APIs han evolucionado en estos años de distintas maneras.

Tal y como hemos visto, las decisiones acerca de OpenGL los toma un comité en el que están implicadas varias empresas. Una empresa puede proponer una extensión a la API y utilizarla. Más adelante el ARB si lo considera oportuno la aceptará, modificandola o incluso mezclandola con otras extensiones de otros fabricantes que tengan una funcionalidad parecida. Con el paso del tiempo, se han publicado versiones nuevas de OpenGL que incluyen al nucleo de la API lo que en su momento eran extensiones. Estas modificaciones pueden ser desde nuevos tipos de texturas hasta llamadas que permiten usar la memoria gráfica para almacenar vertices. Una de las modificaciones más importantes fue la inclusión de GLSL en la versión 2.0, en Septiembre del 2004. Esto consiste en un lenguaje con el que se pueden programar las GPUs que por la época comienzan a incluir este tipo de funcionalidades. La última versión es la 3.2 que fue publicada en Agosto del 2009. También existen versiones reducidas del estándar bajo el nombre OpenGL ES. Las versiones de OpenGL ES son subsets del conjunto completo de llamadas de la API completa y están pensadas para dispositivos móviles o con recursos limitados.

Por su parte Microsoft ha públicado 6 versiones diferentes de Direct3D hasta la época. Durante este tiempo, además de incluir funcionalidades según el hardware evolucionaba, han cambiado partes de la API. Por ejemplo se eliminaron los criticados execution buffer de las primeras versiones, se incluyó la funcionalidad otra API llamada DirectDraw en Direct3D y se hicieron más cambios para hacerlo más sencillo para los desarrolladores, pasando a ser una buena API en la que se han corregido los errores iniciales. La última versión se lanzó junto con el sistema operativo Windows Vista, mientras que la siguientes (Direct3D 11) ha sido anunciada como parte de Windows 7, de próxima publicación.

Existen y han existido más APIs gráficas, pero consideramos que estas son las más importantes por cuota de mercado o por importancia histórica y especialmente OpenGL y Direct3D serán las que más se usen en el futuro cercano. El ámbito de cada una en los próximos años parece estar claro, mientras que Direct3D se utiliza en la mayoría de los juegos para Windows y en todos los de la consola Xbox360, OpenGL está presente en algunos juegos para PC, en gran cantidad de software profesional y en las demás consolas, como Playstation 3, psp, Wii y Nintendo DS, por lo que parece claro que estos 2 APIs van a seguir cubriendo la mayor parte del mercado.

Patxi Astiz

SPECviewperf 10.0

En primer lugar, antes de comenzar con las entradas más técnicas vamos a comenzar con algo al alcance de todo el mundo. Vamos a probar el rendimiento de la tarjeta gráfica del ordenador desde el que escribo.

Muchas veces el análisis del rendimiento de una GPU se realiza ejecutando una serie de programas, típicamente juegos, con una configuración predeterminada. Esto permite comparar el rendimiento de distintas GPUs entre sí. En este caso vamos a utilizar un benchmark gráfico, es decir un programa específicamente creado para probar la tarjeta gráfica y puntuar su rendimiento.

Hay 2 benchmarks gráficos que son los más utilizados. Uno es 3DMark que está orientado a probar las capacidades de una tarjeta con videojuegos modernos que demandan mucho procesado gráfico. Además de los jugadores suelen utilizarlo aficionados a la informática en general, especialmente al overclocking, que suelen competir por conseguir la mayor puntuación modificando el hardware para ello. El API que utiliza es Direct3D. El otro benchmark, que es el que vamos a utilizar es SPECviewperf. Este benchmak está orientado a probar el rendimiento de la tarjeta gráfica con aplicaciones de diseño y modelado profesional, en lugar de con videojuegos. De hecho está formado por una serie de test pensado cada uno para un programa entre los que están 3DStudio, Catia o Maya entre otros. En este caso el API es OpenGL.

El equipo es un portátil con un procesador centrino 1.6 GHz y una tarjeta gráfica ATI Mobility X700. Los test los hemos ejecutado bajo Windows XP y Linux 2.6.28 y en ambos casos hemos utilizado el driver oficial, aunque hay que decir que en el caso de Linux el soporte está abandonado para esta tarjeta, por lo que la última versión del driver que funciona con el kernel y servidor gráfico instalado es mas vieja que en el caso de windows. Lógicamente hemos usado la versión de 32 bits del test y un único hilo de ejecución. La resolución del test ha sido 1280x1024 que aunque no coincide con el tamaño de la pantalla, es la más parecida. Y sin más dilación, estos son los resultados:

Test 3dsmax-04	Windows 5.49	Linux 5.48
catia-02	3.38	3.72
ensight-03	4.83	4.57
maya-02	11.41	9.35
proe-04	2.90	2.78
sw-01	6.87	6.45
tcvis-01	1.89	N/A
ugnx-01	2.43	N/A

Lo primero es apuntar que la versión de Linux del benchmark está en estado alpha por lo que no todos los test han dado un resultado válido. Aunque en general las puntuaciones son similares, sí que aparecen ciertas diferencias, especialmente en el test maya-02. Las tarjetas gráficas de los últimos años son un hardware complejo y la forma de programar hace que mejore o empeore el rendimiento. Conocer la arquitectura del hardware para el que se va a programar es muy importante y más en estos casos al tratarse de un driver. Como se ve, la diferencia en el rendimiento puede llegar a ser notable.

También podemos comparar nuestros resultados con los que aparecen en la propia página de SPEC (results overview). Nuestro sistema seguramente no sea apropiado para utilizar las herramientas que se prueban con suficiente fluidez. Como se puede ver, los resultados de los equipos utilizados en la tabla del enlace son prácticamente un orden de magnitud mayores. Hay que tener en cuenta que las tarjetas gráficas utilizadas son mucho más modernas (aproximadamente 4 años) que la de nuestro ordenador y además son modelos pensados para utilizar con programas de diseño y modelado. Esta diferencia de rendimiento nos da una idea de como los sistemas gráficos han evolucionado durante los últimos años y lo siguen haciendo.

Si queréis podéis descargar un benchmark vosotros mismos, tanto 3DMark como SPECviewperf y probarlos en vuestros equipos. En esas mismas páginas hay resultados de otros equipos con los que comparar. También hay varias páginas dedicadas al hardware de PC en general, que entre otras cosas analizan y prueban el rendimiento de las tarjetas gráficas, generalmente utilizando juegos para ellos. Las 2 páginas más conocidas son tomshardware.com y anandtech.com.

Según se vayan explicando más conceptos de arquitectura de GPUs haremos una breve reseña a la GPU utilizada en estas pruebas y podremos compararla con una actual para ver las diferencias del hardware y comprender mejor el motivo de la diferencia de rendimiento.

Patxi Astiz

Presentación

Este primer post va a ser una presentación. Mi nombre es Patxi Astiz y soy estudiante de la Universidad Rey Juan Carlos, donde estoy cursando el Máster en Informática Gráfica, Juegos y Realidad Virtual.

Este blog va a servir para ir publicando pequeños artículos acerca de los contenidos de la asignatura Arquitecturas para Gráficos y Multimedia. Los temas centrales de esta asignatura son la arquitectura de procesadores de proposito general, que servirá de introducción a la arquitectura de procesadores gráficos, arquitectura de memoria y entrada/salida, arquitectura de consolas modernas y finalmente evaluación de rendimiento en arquitecturas para gráficos. Aunque estos son los temas principales, habrá contenido sobre otros temas siempre relacionados con tecnología que permita generar gráficos por ordenador.

Espero que según vaya escribiendo en este blog os parezca al menos interesante y os animéis a leerlo, apuntaros al RSS y a dejar vuestros comentarios.

Patxi Astiz