Download emision multiple de instrucciones - AA-2011

EMISION MULTIPLE DE
INSTRUCCIONES
ARQUITECTURA AVANZADA
Uciel Cohen
EMISION MULTIPLE DE INSTRUCCIONES
Tabla de contenido
PROCESADORES VECTORIALES ............................................................................................................................... 2
PROCESAMIENTO VECTORIAL ............................................................................................................................ 2
TIEMPOS DE EJECUCION VECTORIAL .................................................................................................................. 3
TIEMPO DE ARRANQUE VECTORIAL Y TASA DE INICIALIZACIÓN ..................................................................... 3
UNIDADES DE CARGA/ALMACENAMIENTO VECTORIAL .................................................................................. 3
CARACTERÍSTICAS DE LOS LENGUAJES PARA PROCESO VECTORIAL .................................................................... 4
EJEMPLOS REALES DE COMPUTADORES VECTORIALES....................................................................................... 4
EL CRAY-1 DE CRAY RESERCH ......................................................................................................................... 4
EL CYBER-205 DE CONTROL DATA .................................................................................................................. 4
EL IBM-3090 .................................................................................................................................................. 5
EL EARTH SIMULATOR .................................................................................................................................. 5
CLASIFICACION DE FLYNN ...................................................................................................................................... 5
UNA INSTRUCCIÓN, UN DATO (SISD) ................................................................................................................. 5
MÚLTIPLES INSTRUCCIONES, UN DATO (MISD) .................................................................................................. 6
UNA INSTRUCCIÓN, MÚLTIPLES DATOS (SIMD) ................................................................................................. 6
MÚLTIPLES INSTRUCCIONES, MÚLTIPLES DATOS (MIMD) .................................................................................. 6
PROCESADORES SUPERESCALARES ........................................................................................................................ 6
VENTAJAS: ..................................................................................................................................................... 7
DESVENTAJAS ................................................................................................................................................ 7
PROCESADORES VLIW ............................................................................................................................................ 8
SEGUIMIENTO DE PROGRAMACIÓN ............................................................................................................... 9
PLANIFICACIÓN DE SÚPER BLOQUE (SÚPER BLOCK SCHEDULING) ................................................................ 10
EJECUCIÓN ESPECULATIVA ........................................................................................................................... 10
PARALELISMO...................................................................................................................................................... 11
PROCESAMIENTO SIMPLE .................................................................................................................. 11
ILP ....................................................................................................................................................................... 11
PARALELISMO A NIVEL DE INSTRUCCIÓN (ILP) ............................................................................................. 12
TLP ...................................................................................................................................................................... 13
PARALELISMO A NIVEL DE PROCESO ............................................................................................. 13
MULTIPROCESAMIENTO A NIVEL DE CHIP (CMP)...................................................................................... 14
MULTIPROCESADOR SIMULTÁNEO (SMT) ................................................................................................ 14
MULTIPROCESAMIENTO SIMÉTRICO (SMP) .............................................................................................. 14
ACCESO DE MEMORIA NO UNIFORME (NUMA) ........................................................................................ 14
REFERENCIAS ....................................................................................................................................................... 16
ARQUITECTURA AVANZADA
1
EMISION MULTIPLE DE INSTRUCCIONES
PROCESADORES VECTORIALES
Normalmente el cálculo científico y matemático precisa de la realización de un número elevado de operaciones
en muy poco tiempo. La mayoría de los problemas físicos y matemáticos se pueden expresar fácilmente
mediante la utilización de matrices y vectores. Aparte de que esto supone una posible claridad en el lenguaje, va
a permitir explotar al máximo un tipo de arquitectura específica para este tipo de tipos de datos, y es la de los
procesadores vectoriales.
Para comenzar veremos algunas definiciones previas:
Se llama vector a una secuencia de datos escalares del mismo tipo almacenados en memoria, normalmente en
posiciones contiguas, aunque no siempre. Para ilustrar este hecho, supongamos una matriz bidimensional
almacenada en memoria por filas. En esta matriz, se podría considerar vectores a las filas, columnas o
diagonales; en este caso, solo las filas estarán en posiciones contiguas de memoria.
Un procesador vectorial es un conjunto de recursos para efectuar operaciones sobre vectores. Estas operaciones
consistirán en funciones aritméticas y lógicas aplicadas sobre las componentes de los vectores. La diferencia
entre un procesador vectorial y uno escalar consiste en que el procesador vectorial puede decodificar
instrucciones cuyos operandos son vectores completos. La conversión de un programa correspondiente a un
procesador escalar a otro vectorial se llama vectorización.
PROCESAMIENTO VECTORIAL
Un operando vectorial contiene una secuencia de n elementos (llamados componentes), donde n es la longitud
del vector. Cada componente del vector es un escalar de cualquier tipo (entero, punto flotante, etc.). Las
máquinas vectoriales proporcionan operaciones que trabajan sobre vectores. Una instrucción vectorial es
equivalente a la ejecución de un bucle completo de instrucciones ordinarias, donde cada iteración trabaja sobre
cada una de las componentes del vector.
El paralelismo viene que al operar con matrices, normalmente, los elementos de las matrices son independientes
entre sí, es decir, no existen dependencias de datos dentro de las propias matrices, en general. Esto permite que
todas las operaciones entre elementos de unas matrices con otras puedan realizarse en paralelo, o al menos en
el mismo cauce de instrucciones sin que haya un conflicto entre los datos.
Las instrucciones vectoriales tienen unas propiedades importantes y que significan ventajas sobre las
instrucciones escalares, que se resumen a continuación:
 El cálculo de cada resultado es independiente de los resultados anteriores en el mismo vector, lo que
permite un cauce muy profundo sin generar riesgos por las dependencias de datos. La ausencia de
estos riesgos viene decidida por el compilador o el programador cuando se decidió que la instrucción
podía ser utilizada.
 Una sola instrucción vectorial especifica una gran cantidad de trabajo, ya que equivale a ejecutar un
bucle completo. Por lo tanto, el requisito de anchura de banda de las instrucciones se reduce
considerablemente. En los procesadores no vectoriales, donde se precisan muchas más instrucciones, la
búsqueda y decodificación de las instrucciones puede representar un cuello de botella (Cuello de botella
de Flynn)
 Las instrucciones vectoriales que acceden a memoria tienen un patrón de acceso conocido. Si los
elementos de la matriz son todos adyacentes, entonces extraer el vector de un conjunto de bancos de
memoria entrelazada funciona muy bien. La alta latencia de iniciar un acceso a memoria principal, en
comparación con acceder a una cache, se amortiza porque se inicia un acceso para el vector completo
en lugar de para un único elemento. Por ello, el coste de la latencia a memoria principal se paga una
sola vez para el vector completo, en lugar de una vez por cada elemento del vector.
ARQUITECTURA AVANZADA
2
EMISION MULTIPLE DE INSTRUCCIONES

Como se sustituye un bucle completo por una instrucción vectorial cuyo comportamiento está
predeterminado, los riesgos de control en el cauce, que normalmente podrían surgir del salto del bucle,
son inexistentes.
Por estas razones, las operaciones vectoriales pueden hacerse más rápidas que una secuencia de operaciones
escalares sobre el mismo número de elementos de datos, y los diseñadores están motivados para incluir
unidades vectoriales si el conjunto de las aplicaciones las puede usar frecuentemente.
TIEMPOS DE EJECUCION VECTORIAL
Tres son los factores que influyen en el tiempo de ejecución de una secuencia de operaciones vectoriales:
 La longitud de los vectores sobre los que se opera.
 Los riesgos estructurales entre las operaciones.
 Las dependencias de datos.
Dada la longitud del vector y la velocidad de inicialización, que es la velocidad a la cual una unidad vectorial
consume nuevos operandos y produce nuevos resultados, podemos calcular el tiempo para una instrucción
vectorial. Lo normal es que esta velocidad sea de uno por ciclo del reloj. Sin embargo, algunos
supercomputadores producen 2 o más resultados por ciclo de reloj, y otros, tienen unidades que pueden no
estar completamente segmentadas. Por simplicidad se supondrá que esta velocidad es efectivamente la unidad.
Para simplificar la discusión del tiempo de ejecución se introduce la noción de convoy, que es el conjunto de
instrucciones vectoriales que podrían potencialmente iniciar su ejecución en el mismo ciclo de reloj. Las
instrucciones en un convoy no deben incluir ni riesgos estructurales ni de datos (aunque esto se puede relajar
más adelante); si estos riesgos estuvieran presentes, las instrucciones potenciales en el convoy habría que
serializarlas e inicializarlas en convoyes diferentes. Para simplificar diremos que las instrucciones de un convoy
deben terminar de ejecutarse antes que cualquier otra instrucción, vectorial o escalar, pueda empezar a
ejecutarse. Esto se puede relajar utilizando un método más complejo de lanzar instrucciones.
Junto con la noción de convoy está la de toque o campanada (chime) que puede ser usado para evaluar el
rendimiento de una secuencia de vectores formada por convoyes. Un toque o campanada es una medida
aproximada del tiempo de ejecución para una secuencia de vectores; la medida de la campanada es
independiente de la longitud del vector. Por tanto, para una secuencia de vectores que consiste en m convoyes
se ejecuta en m campanadas, y para una longitud de vector de n, será aproximadamente n £ m ciclos de reloj.
Esta aproximación ignora algunas sobrecargas sobre el procesador que además dependen de la longitud del
vector. Por consiguiente, la medida del tiempo en campanadas es una mejor aproximación para vectores largos.
Se usará esta medida, en vez de los periodos de reloj, para indicar explícitamente que ciertas sobrecargas están
siendo ignoradas.
TIEMPO DE ARRANQUE VECTORIAL Y TASA DE INICIALIZACIÓN
La fuente de sobrecarga más importante, no considerada en el modelo de campanadas, es el tiempo de
arranque vectorial. El tiempo de arranque viene de la latencia del cauce de la operación vectorial y está
determinada principalmente por la profundidad del cauce en relación con la unidad funcional empleada. El
tiempo de arranque incrementa el tiempo efectivo en ejecutar un convoy en más de una campanada. Además,
este tiempo de arranque retrasa la ejecución de convoyes sucesivos. Por lo tanto, el tiempo necesario para la
ejecución de un convoy viene dado por el tiempo de arranque y la longitud del vector. Si la longitud del vector
tendiera a infinito, entonces el tiempo de arranque sería despreciable, pero lo normal es que el tiempo de
arranque sea de 6 a 12 ciclos, lo que significa un porcentaje alto en vectores típicos que como mucho rondarán
los 64 elementos o ciclos.
UNIDADES DE CARGA/ALMACENAMIENTO VECTORIAL
El comportamiento de la unidad de carga/almacenamiento es más complicado que el de las unidades
aritméticas. El tiempo de arranque para una carga es el tiempo para coger la primera palabra de la memoria y
guardarla en un registro. Si el resto del vector se puede coger sin paradas, la tasa de inicialización es la misma
ARQUITECTURA AVANZADA
3
EMISION MULTIPLE DE INSTRUCCIONES
que la velocidad a la que las nuevas palabras son traídas y almacenadas. Al contrario que en las unidades
funcionales, la tasa de inicialización puede no ser necesariamente una instrucción por ciclo.
Normalmente, el tiempo de arranque para las unidades de carga/almacenamiento es algo mayor que para las
unidades funcionales, pudiendo llegar hasta los 50 ciclos.
Para conseguir una tasa (o velocidad) de inicialización de una palabra por ciclo, el sistema de memoria debe ser
capaz de producir o aceptar esta cantidad de datos. Esto se puede conseguir mediante la creación de bancos de
memoria múltiples. Teniendo un número significativo de bancos se puede conseguir acceder a la memoria por
filas o por columnas de datos.
CARACTERÍSTICAS DE LOS LENGUAJES PARA PROCESO VECTORIAL
El uso de lenguajes secuenciales en computadores vectoriales puede hacer perder el paralelismo de un algoritmo
vectorizable. Es, por tanto, necesaria la existencia de lenguajes de alto nivel, adecuados a los computadores
vectoriales. Estos lenguajes deberían tener una serie de propiedades para expresar el paralelismo de los
algoritmos y así poderlo explotar con más eficiencia:
 Flexibilidad para declarar diferentes clases de objetos con distintas estructuras y formas de
almacenamiento. El lenguaje debe poder expresar las diferentes formas de almacenar las componentes
de un mismo objeto: por filas, columnas, diagonales, etc.
 Efectividad para la manipulación de matrices y vectores dispersos, es decir, matrices o vectores con la
mayoría de sus elementos nulos. Las matrices dispersas son muy habituales en problemas reales, por
ello, el lenguaje de programación debe suministrar los medios para almacenarlas de forma eficiente sin
ocupar excesiva memoria.
 Disponer de operaciones vectoriales nativas que trabajen directamente con las estructuras de datos
anteriormente declaradas sin necesidad de bucles. Será el compilador del lenguaje el que transforme
estas operaciones de alto nivel en las instrucciones vectoriales de la máquina. Muchas veces, el número
de componentes del vector declarado en el lenguaje de alto nivel, será superior a la capacidad de los
registros vectoriales. Por ello, el compilador deberá aplicar la técnica de seccionamiento para
descomponer algunas instrucciones vectoriales de alto nivel, en otras instrucciones vectoriales más
sencillas que puedan ejecutarse con la capacidad de almacenamiento de los registros vectoriales de la
máquina. Esto no significa, sin embargo, que estos lenguajes no admitan programación mediante
bucles. Esto es debido a que puede haber muchas operaciones combinadas que sólo pueden detallarse
mediante bucles específicos. Evidentemente, el lenguaje vectorial no puede tener como operaciones
nativas todas las posibles combinaciones de operaciones vectoriales, aunque sí las más frecuentes.
EJEMPLOS REALES DE COMPUTADORES VECTORIALES
EL CRAY-1 DE CRAY RESERCH
El Cray-1, operativo desde 1976, puede considerarse como el primer computador vectorial.
Como muchos supercomputadores (el Cray-1 en su tiempo lo fue), necesita un procesador auxiliar (front end
host) que efectúe labores de administración, E/S, etc. De esta forma, el Cray-1 se dedica sólo a computación
pura. El Cray-1 posee tres secciones (Russell, 1978): la sección de computación, la sección de memoria y la
sección de E/S. El sistema dispone de 12 unidades funcionales segmentadas divididas en cuatro grupos:
vectoriales (enteras y de punto flotante), escalares y de direcciones. Cada unidad funcional puede trabajar con
total independencia de las demás, por lo que todas ellas pueden funcionar concurrentemente siempre que no
haya conflictos en cuanto a los registros que utilicen. Las unidades funcionales pueden acceder directamente a
los registros primarios, pero no a los temporales.
EL CYBER-205 DE CONTROL DATA
Esta máquina es un curioso ejemplo de computador vectorial memoria-memoria. Por ello, la memoria de esta
máquina es muy rápida y está entrelazada con cuatro vías. La ventaja de que este computador sea del tipo
memoria-memoria radica en que la longitud de los vectores puede ser muy grande. Concretamente en el CyberARQUITECTURA AVANZADA
4
EMISION MULTIPLE DE INSTRUCCIONES
205, la longitud máxima de los vectores es de 65635 palabras. El control de la ejecución de las instrucciones
reside en la unidad escalar, que recibe y decodifica las instrucciones procedentes de la memoria y las reparte
entre los diferentes bloques en función de su tipo: escalar, vectorial o de cadena (aquí la palabra cadena se
refiere a cadenas de bits); a partir de ahí, diferentes instrucciones pueden ejecutarse de forma concurrente en
diferentes unidades funcionales. La unidad de flujo sirve para controlar el tráfico de datos entre la memoria y los
cauces.
EL IBM-3090
El procesamiento vectorial en esta máquina es una opción llamada vector facility. Existen 16 registros de 32 bits
que pueden unirse de dos en dos para convertirse en 8 registros de 64 bits. Cualquiera de los registros puede
contener tanto números enteros como representados en punto flotante (ambos de 32 o 64 bits). En el diseño de
la arquitectura no se determina de forma concreta la longitud de los registros vectoriales que pudiera oscilar
entre 8 y 512. En la implementación del 3090 se eligió el número de 128. Esta elección se debió a un compromiso
entre el tiempo perdido en los arranques, que será alto si los registros son pequeños, porque habrá que efectuar
más arranques de instrucciones vectoriales si los vectores son largos, y el tiempo empleado en la carga y
almacenamiento de los registros vectoriales, que será tanto más grande cuanta más longitud tengan. Una de las
más importantes características de esta máquina es que su juego de instrucciones vectoriales contiene
instrucciones de tipo CVF (recuérdese: funciones vectoriales compuestas) tales como multiplicar y sumar,
multiplicar y restar, etc., esto da mucha agilidad y velocidad a las operaciones sin tener que recurrir al
encadenamiento.
EL EARTH SIMULATOR
El Earth Simulator es un computador que ha estado durante más de un año en la cabeza del TOP500. Se trata
de un multi-computador constituido por 640 nodos (llamados PN, processor nodes) interconectados. Cada
nodo, a su vez, es un multiprocesador con 8 procesadores vectoriales (denominados AP, arithmetic procesor)
que comparten una memoria de 16 Gbytes, un procesador de E/S y una unidad de control para el acceso remoto
(RCU, Remote Control Unit). Cada uno de los 5.120 (640 × 8) procesadores vectoriales AP (figura 3.7), está
constituido por una unidad de procesamiento superescalar (SU, superescalar unit) capaz de emitir 4
instrucciones por ciclo, y de una unidad de procesamiento vectorial (VU, vectorial unit). Estas dos unidades,
junto con las correspondientes cachés y la unidad de control de acceso a la memoria principal están integradas
en un único circuito integrado.
CLASIFICACION DE FLYNN
Las cuatro clasificaciones definidas por Flynn se basan en el número de instrucciones concurrentes (control) y en
los flujos de datos disponibles en la arquitectura:
UNA INSTRUCCIÓN, UN DATO (SISD)
Computador secuencial que no explota el paralelismo en las instrucciones ni en flujos
de datos. Ejemplos de arquitecturas SISD son las máquinas con uni-procesador o
monoprocesador.
ARQUITECTURA AVANZADA
5
EMISION MULTIPLE DE INSTRUCCIONES
MÚLTIPLES INSTRUCCIONES, UN DATO (MISD)
Poco común debido al hecho de que la efectividad de los múltiples flujos de
instrucciones suele precisar de múltiples flujos de datos. Sin embargo, este
tipo se usa en situaciones de paralelismo redundante, como por ejemplo en
navegación aérea, donde se necesitan varios sistemas de respaldo en caso de
que uno falle. También se han propuesto algunas arquitecturas teóricas que
hacen uso de MISD, pero ninguna llegó a producirse en masa.
UNA INSTRUCCIÓN, MÚLTIPLES DATOS (SIMD)
Un computador que explota varios flujos de datos dentro de un único flujo de
instrucciones para realizar operaciones que pueden ser paralelizadas de
manera natural. Por ejemplo, un procesador vectorial.
MÚLTIPLES INSTRUCCIONES, MÚLTIPLES DATOS (MIMD)
Varios procesadores autónomos que ejecutan simultáneamente
instrucciones diferentes sobre datos diferentes. Los sistemas
distribuidos suelen clasificarse como arquitecturas MIMD; bien sea
explotando un único espacio compartido de memoria, o uno distribuido.
PROCESADORES SUPERESCALARES
La ejecución segmentada permite instrucciones simultáneas, pero sólo una instrucción puede estar en cada
etapa del cauce.
Superescalar es el término utilizado para designar un tipo de micro-arquitectura de procesador capaz de ejecutar
más de una instrucción por ciclo de reloj. El término se emplea por oposición a la micro-arquitectura escalar que
sólo es capaz de ejecutar una instrucción por ciclo de reloj. En la clasificación de Flynn, un procesador
superescalar es un procesador de tipo MIMD (multiple instruction multiple data).
Una arquitectura superescalar tiene las prestaciones de la segmentación, permitiendo además la existencia
simultánea de varias instrucciones en la misma etapa. Para ello es necesaria la duplicación de recursos y la
utilización de diversas técnicas que permitan optimizar su utilización. Como puede iniciarse la ejecución de varias
instrucciones en el mismo ciclo, puede alcanzarse una productividad mayor que una instrucción por ciclo de
reloj. En la práctica se consiguen aceleraciones cercanas a dos.
La micro-arquitectura superescalar utiliza el paralelismo de instrucciones además del paralelismo de flujo, éste
último gracias a la estructura en pipeline. La estructura típica de un procesador superescalar consta de un
pipeline con las siguientes etapas:
• Lectura (fetch): múltiples instrucciones son captadas simultáneamente, utilizando técnicas de predicción de
saltos y ejecución especulativa.
• Decodificación (decode): en dos pasos, i) Pre decodificación entre la memoria y el cache para identificación de
saltos, y ii) Determinación de la operación, localización de operandos y localización del resultado.
• Lanzamiento (dispatch): identificación de las instrucciones de la cola que están listas para comenzar su
ejecución, o sea que tienen sus dependencias satisfechas.
ARQUITECTURA AVANZADA
6
EMISION MULTIPLE DE INSTRUCCIONES
• Ejecución (execute): en paralelo, en diferentes unidades funcionales.
• Escritura (writeback).
• Finalización (retirement): El resultado es confirmado en su destino.
En un procesador superescalar, el procesador maneja más de una instrucción en cada etapa. El número máximo
de instrucciones en una etapa concreta del pipeline se denomina grado, así un procesador superescalar de grado
4 en lectura (fetch) es capaz de leer como máximo cuatro instrucciones por ciclo. El grado de la etapa de
ejecución depende del número y del tipo de las unidades funcionales.
Un procesador superescalar suele tener unidades funcionales independientes de los tipos siguientes:
• Unidad aritmético lógica (ALU)
• Unidad de lectura/escritura en memoria (Load/Store Unit)
• Unidad de punto flotante (Floating Point Unit)
• Unidad de salto (Branch unit)
Un procesador superescalar es capaz de ejecutar más de una instrucción simultáneamente únicamente si las
instrucciones no presentan algún tipo de dependencia (hazard). Los tipos de dependencia entre instrucciones
son:
• Dependencia estructural, esta ocurre cuando dos instrucciones requieren el mismo tipo unidad funcional y su
número no es suficiente.
• Dependencia de datos, esta ocurre cuando una instrucción necesita del resultado de otra instrucción para
ejecutarse, por ejemplo R1<=R2+R3 y R4<=R1+5.
• Dependencia de escritura o falsa dependencia o nombre, esta ocurre cuando dos instrucciones necesitan
escribir en la misma memoria, por ejemplo R1<=R2+R3 y R1<=R1+5.
• Dependencia de control, esta ocurre cuando una instrucción depende de una estructura de control y no se
puede determinar el flujo correcto hasta la evaluación de la estructura de control, por ejemplo, if R1<="R4+R5"
else="" r6<="R7+5."
La detección y resolución dinámica de las dependencias entre instrucciones suele realizarse mediante alguna
variante del algoritmo de Tomasulo que permite la ejecución de instrucciones en un orden distinto al del
programa también llamada ejecución en desorden, es decir ejecutar simultáneamente instrucciones
independientes y detectar las instrucciones dependientes y gestionarlas correctamente. La eficacia de un
procesador superescalar viene limitada por un lado por la dificultad en suministrar al procesador suficientes
instrucciones que puedan ser ejecutadas en paralelo y por otro lado por las prestaciones de la jerarquía de
memorias.
Si las instrucciones de salto son un problema para los procesadores con pipeline en general, en el caso de los
procesadores superescalares, el problema se multiplica ya que un parón en el pipeline tiene consecuencias en un
número mayor de instrucciones. Una forma de obtener un mayor número de instrucciones paralelizables es
aumentar la ventana de instrucciones, es decir el conjunto de instrucciones que la unidad de lanzamiento
considera como candidatas a ser lanzadas en un momento dado
VENTAJAS:


El HW resuelve todo: detecta el paralelismo, emite, renombra registros, etc.
Compatibilidad binaria: puedo agregar unidades funcionales.
DESVENTAJAS

Hardware muy complejo, se llega rápidamente a un limite
ARQUITECTURA AVANZADA
7
EMISION MULTIPLE DE INSTRUCCIONES

Ventana de ejecución limitada por el hardware, lo cual limita la capacidad de detección de instrucciones
paralelas.
Figura. Procesadores VLIW y superescalares
PROCESADORES VLIW
Del inglés Very Long Instruction Word. Esta arquitectura de CPU implementa una forma de paralelismo a nivel de
instrucción. Es similar a las arquitecturas superescalares, ambas usan varias unidades funcionales (por ejemplo
varias ALUs, varios multiplicadores, etc.) para lograr ese paralelismo.
Los procesadores con arquitecturas VLIW se caracterizan, como su nombre indica, por tener juegos de
instrucciones muy simples en cuanto a número de instrucciones diferentes, pero muy grandes en cuanto al
tamaño de cada instrucción. Esto es así porque en cada instrucción se especifica el estado de todas y cada una de
las unidades funcionales del sistema, con el objetivo de simplificar el diseño del hardware al dejar todo el trabajo
de planificar el código en manos del programador/compilador, en oposición a un procesador superescalar, en el
que es el hardware en tiempo de ejecución el que planifica las instrucciones.
Un microprocesador típico VLIW es el IA-64.
 Varias operaciones que pueden ser ejecutadas en paralelo (ILP) se empaquetan en una instrucción larga,
una por cada UF disponible.
 La detección del paralelismo lo hace el compilador (off-line)
 Luego de la captación y decodificación de una instrucción, las operaciones contenidas son emitidas en
paralelo.
ARQUITECTURA AVANZADA
8
EMISION MULTIPLE DE INSTRUCCIONES
SEGUIMIENTO DE PROGRAMACIÓN
Muchos compiladores para procesadores ILP de primera generación utiliza un método de tres fases para generar
código. Las fases fueron:
Generar un programa secuencial. Analizar cada bloque básico en el programa secuencial de operaciones
independientes.
Calendario de operaciones independientes en el mismo bloque en paralelo si hay suficientes recursos de
hardware disponibles.
Trasladar las operaciones entre los bloques cuando sea posible.
Este enfoque de tres fases no explota gran parte de la ILP disponibles en el programa por dos razones.
Muchas veces, las operaciones en un bloque básico son dependientes el uno del otro. Por lo tanto ILP suficiente
puede no estar disponible dentro de un bloque básico.
Decisiones arbitrarias, mientras que la programación de los bloques básicos hace que sea difícil moverse entre
los bloques de las operaciones.
La programación de rastreo es un método de perfil impulsado desarrollado por Joseph Fisher para evitar este
problema. En la programación de rastreo, un conjunto de secuencias comunes de los bloques es ejecutado
congregó en el rastreo y el seguimiento de todo está programado juntos.
El algoritmo de programación rastro funciona de la siguiente.
1. Generar una versión posiblemente sin optimizar del programa, que se ejecutan en la entrada de la muestra y
obtener estadísticas. Estimar la probabilidad de cada rama condicional.
2. Desde el nivel básico de bloques de datos gráfica de prioridad del programa (también comúnmente llamado
DAG de grafo dirigido Acylic), seleccione un bucle sin secuencia lineal de los elementos básicos que tienen una
alta probabilidad de ejecución. Esa secuencia se llama dejar rastro. El compilador puede usar otras
optimizaciones como desenrollar bucle o procedimiento de procesos en línea para generar DAG de que los
rastros adecuados pueden ser seleccionados.
3. Considerar el seguimiento como si se tratara de un bloque básico. Construir un DAG para que las ramas
considerando como todas las demás operaciones. Si una operación controlada por un salto condicional más
podría escribir un valor que es vivir en el borde fuera del rastro, añadir un borde que hace que la operación
depende de la rama para que la operación no pueda ser colocada por delante de la sucursal. Además, añadir
bordes para preservar el orden relativo de las ramas condicionales.
4. Calendario de la DAG resultante como si fuera un bloque básico la distribución, registro y selección de la
unidad de función, ya que cada operación está programada.
ARQUITECTURA AVANZADA
9
EMISION MULTIPLE DE INSTRUCCIONES
5. Generar código de compensación por los errores cometidos al considerar el seguimiento como un bloque
básico. En particular:
a. Si una operación que se utiliza para preceder a una rama condicional en el código secuencial se mueve
después de esa rama, a continuación, agregar una copia de la operación anterior, el objetivo fuera de la traza del
salto condicional.
b. Si una operación que logró un punto de entrada en la traza de fuera de la traza se desplaza por delante de la
puerta de entrada, coloque una copia de esa operación fuera de la traza, en el camino que conduce a ese punto
de entrada.
c. Asegúrese de que vuelve a unir que utiliza para ingresar la traza entrar en la nueva traza sólo en un punto
después de que no se encuentra en funcionamiento la nueva traza que no estaban por debajo del punto de
reunirse en la traza de edad.
6. Enlace la nueva traza de nuevo en el viejo DAG.
7. Después de la programación de la traza primera, las operaciones nuevas se han añadido al original DAG. Elige
un rastro frecuente diferente y programar la misma. Repita hasta que el DAG se ha cubierto con restos inconexos
y no quedan las operaciones programadas.
PLANIFICACIÓN DE SÚPER BLOQUE (SÚPER BLOCK SCHEDULING)
Programación súper bloque es un algoritmo de programación de la región desarrollada en conjunto con el
compilador de Impacto en la Universidad de Illinois. Al igual que la programación de rastreo, programación súper
bloque se basa en la premisa de que la extracción de ILP de los programas secuenciales requiere el movimiento
de código a través de múltiples bloques básicos. A diferencia de la programación de rastreo, programación súper
bloque está impulsado por el análisis estático no poder, los datos del perfil. Un súper-bloque es un conjunto de
elementos básicos en los que el control puede entrar sólo en la parte superior, pero puede salir en más de un
punto. Súper Blocks se identifican, en primer lugar la identificación de las huellas y luego la eliminación de las
entradas laterales en un rastro por un proceso llamado cola de duplicación. Cola de duplicación de obras de la
creación de una copia por separado fuera de la traza de los bloques básicos en medio de una entrada lateral y la
salida de la traza y reorientar el borde correspondiente a la entrada lateral a la copia. Las huellas se identifican
mediante el análisis estático de la rama, basado en la detección de bucles, prevención de riesgos heurística y la
heurística de selección de ruta. Detección de bucles identifica los bucles y los bordes de las marcas de bucle
tomada ya salen del bucle que no toma. Prevención de riesgos utiliza un conjunto de heurísticas para detectar
situaciones como las tiendas de ambiguo y llamadas a procedimientos que podrían causar un compilador que
utilice las estrategias conservadoras de optimización y predice las ramas a fin de evitar tener que optimizar los
riesgos. Heurística camino selección utilice el código de operación de una sucursal, sus operandos y el contenido
de los bloques de su sucesor para predecir su dirección, si ningún otro método puede ser utilizado para predecir
el resultado de la rama. Estos se basan en patrones de programación comunes, como el hecho de que los
punteros son poco probable que sea NULL, las comparaciones en coma flotante es improbable que sean iguales,
etc. Una vez que la información está disponible rama, las huellas han crecido y se siguió Súper Blocks creado por
la cola mediante la programación de la duplicación de los súper bloque. Los estudios han demostrado que el
análisis estático basado en la programación de súper-bloque puede alcanzar resultados que son comparables a
los métodos basados en el perfil.
EJECUCIÓN ESPECULATIVA
La ejecución fuera de orden y la ejecución especulativa se han utilizado con éxito durante muchos años para
incrementar la ejecución en paralelo del código de software de los microprocesadores más comunes. Sin
embargo, debido a la complejidad creciente que supone el escalamiento de estos enfoques, la industria de
ARQUITECTURA AVANZADA
10
EMISION MULTIPLE DE INSTRUCCIONES
microprocesadores a mediados de los años 90 comenzó a reexaminar los conjuntos de instrucciones que
codificaban explícitamente múltiples operaciones por instrucción. El fundamento de dicha investigación es VLIW
(Very Long Instruction Word o palabra de instrucción muy larga), en el que se codifican múltiples operaciones en
cada instrucción para procesarse después mediante unidades de ejecución múltiple.
Uno de los objetivos de esta estrategia es desplazar la complejidad de la programación de instrucciones desde el
componente hardware, la CPU, al componente software, el compilador, que puede realizar la programación de
instrucciones de forma estática (con la ayuda de la información de retroalimentación de rastros). Elimina así la
necesidad de una circuitería de programación compleja en la CPU, lo que a su vez ahorra espacio y consumo
eléctrico utilizable en otras funciones, incluidos recursos de ejecución adicionales. Otro objetivo igualmente
importante es conseguir una mayor explotación del ILP (paralelismo en el nivel de instrucciones) mediante el uso
del compilador para encontrar y explotar oportunidades adicionales para la ejecución en paralelo.
Las arquitecturas vectoriales tradicionales han demostrado ser muy efectivas ejecutando códigos regulares
En los que un compilador vectorial es capaz de detectar paralelismo a nivel de datos. Este paralelismo también
está presente en códigos irregulares aunque no se puede detectar con mucha facilidad. Se presenta un
mecanismo que es capaz de detectar el paralelismo SIMD en aplicaciones irregulares y explotarlo
especulativamente. Para esto, intenta ejecutar instrucciones escalares en modo vectorial basándose en previas
ejecuciones escalares de estas instrucciones. Estas nuevas instrucciones vectoriales especulativas se ejecutan en
extensiones vectoriales y almacenan sus resultados en registros vectoriales (registros con varios elementos). Las
instancias escalares de las instrucciones vectoriales comprueban si la ejecución especulativa es correcta,
validando los resultados. En caso de que la especulación sea incorrecta, las instrucciones se vuelven a ejecutar de
forma escalar, desechando los datos almacenados en registros vectoriales, hasta que se detecte un nuevo patrón
de vectorización. Con este mecanismo se obtiene un 21% de mejora del rendimiento en códigos irregulares.
PARALELISMO
PROCESAMIENTO SIMPLE
Note que toma quince ciclos para terminar tres instrucciones.
Este tipo de CPU, opera sobre y ejecuta una sola instrucción. Esto da lugar a una ineficacia en los elementos del
CPU. Todo el CPU debe esperar que esa instrucción se complete antes de proceder a la siguiente. Como
resultado, el CPU queda "paralizado" mientras se buscan los operandos en memoria, la ALU mientras la UC
decodifica la instrucción, etc.
Cuando se refiere al paralelismo en los CPU, generalmente son usados dos términos para clasificar estas técnicas:
El paralelismo a nivel de instrucción, busca aumentar la tasa en la cual las instrucciones son ejecutadas dentro de
un CPU, es decir, aumentar la utilización de los recursos de ejecución en la pastilla
El paralelismo a nivel de proceso que se propone incrementar el número de programas individuales que un CPU
pueda ejecutar simultáneamente.
ILP
ARQUITECTURA AVANZADA
11
EMISION MULTIPLE DE INSTRUCCIONES
PARALELISMO A NIVEL DE INSTRUCCIÓN (ILP)
ILP es una medida de cómo muchas de las operaciones en un programa de computadora se pueden realizar
simultáneamente. Considere el siguiente programa:
1. e = a + b
2. f = c + d
3. g = e * f
Operación 3 depende de los resultados de las operaciones 1 y 2, por lo que no se puede calcular hasta que
ambos se han completado. Sin embargo, las operaciones 1 y 2 no dependen de ninguna otra operación, por lo
que se puede calcular de forma simultánea. (Véase también: la dependencia de datos) Si suponemos que cada
operación se puede completar en una sola unidad de tiempo, estas tres instrucciones se puede completar en un
total de dos unidades de tiempo, dando una ILP de 3 / 2.
Uno de los objetivos del compilador y el procesador de los diseñadores es el de identificar y aprovechar las ILP
tanto como sea posible. Programas ordinarios son típicamente escritos en un modelo de ejecución secuencial en
las instrucciones se ejecutan una tras otra y en el orden especificado por el programador. ILP permite que el
compilador y el procesador a la superposición de la ejecución de múltiples instrucciones o incluso cambiar el
orden en que las instrucciones se ejecutan.
¿Cuánto ILP existe en los programas es muy aplicación específica? En algunos campos, tales como gráficos y
computación científica de la cantidad puede ser muy grande. Sin embargo, las cargas de trabajo tales
como criptografía de exhibición paralelismo mucho menos.
Micro-arquitectura técnicas que se utilizan para explotar ILP incluyen:
Canalización de instrucción donde la ejecución de múltiples instrucciones puede ser parcialmente superpuesta.
Superescalar ejecución, VLIW, y la estrecha relación de instrucciones explícitamente Parallel
Computing conceptos, en el que varias unidades de ejecución se utilizan para ejecutar múltiples instrucciones en
paralelo.
Fuera de la orden de ejecución en las instrucciones se ejecutan en el orden que no viola las dependencias de
datos. Tenga en cuenta que esta técnica es independiente de la canalización y superescalar. Las
implementaciones actuales de ejecución fuera de orden de forma dinámica (es decir, mientras que el programa
se está ejecutando y sin ninguna ayuda del compilador) extraer ILP de los programas ordinarios. Una alternativa
es la extracción de este paralelismo en tiempo de compilación y de alguna manera transmitir esta información en
el hardware. Debido a la complejidad de la ampliación de la técnica de ejecución fuera de orden, la industria ha
vuelto a examinar los conjuntos de instrucciones que explícitamente codificar varias operaciones independientes
por instrucción.
Registro de cambio de nombre que se refiere a una técnica utilizada para evitar la serialización innecesaria de las
operaciones del programa impuesto por la reutilización de los registros de las operaciones, que se utiliza para
permitir que fuera de la orden de ejecución.
La ejecución especulativa que permite la ejecución de las instrucciones completas o partes de las instrucciones
antes de tener la certeza de si esta ejecución debe llevarse a cabo. Una forma común de ejecución especulativa
es la especulación de control de flujo en las instrucciones de más allá de una instrucción de control de flujo (por
ejemplo, una rama) se ejecutan antes de que el objetivo de la instrucción de control de flujo se
determina. Existen otras formas de ejecución especulativa se han propuesto y están en uso, incluyendo la
ejecución especulativa impulsada por el valor de predicción, la predicción de la dependencia de la memoria y la
predicción de latencia de la caché.
De predicción que se utiliza para evitar el estancamiento de las dependencias de control para ser
resueltos. Predicción de saltos se utiliza con ejecución especulativa.
Arquitecturas de flujo de datos son otra clase de arquitecturas en las ILP se especifica explícitamente, pero que
no han sido activamente investigado desde la década de 1980.
ARQUITECTURA AVANZADA
12
EMISION MULTIPLE DE INSTRUCCIONES
En los últimos años, las técnicas de ILP se han utilizado para proporcionar mejoras de rendimiento, a pesar de la
creciente disparidad entre las frecuencias de funcionamiento del procesador y los tiempos de acceso a memoria
(ILP primeros diseños, tales como el IBM 360 utiliza técnicas ILP para superar las limitaciones impuestas por un
archivo de registro relativamente pequeño). En la actualidad, un fallo de caché a la memoria principal pena de
los costos de varios cientos de ciclos de CPU. Si bien en principio es posible utilizar ILP de tolerar latencias de
memoria como el recurso asociado y los costos de energía de disipación son desproporcionados. Por otra parte,
la complejidad y la frecuencia de la latencia de las estructuras subyacentes de hardware resultado en la
frecuencia de funcionamiento reducido aún más la reducción de los beneficios. Por lo tanto, las técnicas antes
mencionadas no resultan adecuadas para mantener a la CPU de estancamiento de los datos fuera del chip. En
cambio, la industria se dirige hacia la explotación de un mayor nivel de paralelismo que puede ser explotado a
través de técnicas como el multiprocesamiento y el multithreading. [1]
En esta versión, cada paso X es ejecutado para la siguiente instrucción cuando el CPU termina de ejecutar el paso
X para la presente instrucción.
Una mejora adicional sobre la idea del paralelismo condujo al desarrollo de un método que disminuye incluso
más el tiempo ocioso de los componentes del CPU, llamado procesadores superescalares. Incluyen una larga
tubería de instrucción y múltiples unidades de ejecución idénticas (UC, ALU, etc.). En una tubería superescalar,
múltiples instrucciones son leídas, y se decide si las instrucciones se pueden o no ejecutar en paralelo
(simultáneamente). De ser así, son enviadas a las unidades de ejecución disponibles, dando por resultado la
capacidad para que varias instrucciones sean ejecutadas simultáneamente.
La mayoría de los modernos diseños de CPU son por lo menos algo superescalares, y en la última década, casi
todos los diseños de CPU de propósito general son superescalares.
TLP
PARALELISMO A NIVEL DE PROCESO
Otra estrategia comúnmente usada para aumentar el paralelismo de los CPU es incluir la habilidad de correr
múltiples procesos (programas) al mismo tiempo.
ARQUITECTURA AVANZADA
13
EMISION MULTIPLE DE INSTRUCCIONES
En procesadores individuales, las dos metodologías principales usadas para lograr el TLP son:
MULTIPROCESAMIENTO A NIVEL DE CHIP (CMP)
Un procesador de varios núcleos de procesamiento es un sistema compuesto por dos o más núcleos (o CPU). Los
núcleos suelen ser integrados en un único circuito integrado (conocido como un chip multiprocesador o CMP). La
cantidad máxima de núcleos es aquel número en que las técnicas de Multi-procesamiento ya no son eficientes
(varias decenas de núcleos) y que requiere de una red de procesadores.
Un Dual-Core contienen dos núcleos, y un Quad-Core contiene cuatro. Los núcleos pueden o no compartir
cachés, y pueden comunicarse entre sí mediante el traspaso de mensajes, sea por conexiones entre sí, o
levantándolos desde posiciones compartidas de memoria.
Mientras la fabricación de tecnología sigue mejorando, la reducción del tamaño de un procesador se ha
convertido en una importante preocupación de diseño, ya que aumenta la disipación de calor y la sincronización
de datos. Es por ello que se intento agrupar varios núcleos para intentar mitigar estos inconvenientes.
MULTIPROCESADOR SIMULTÁNEO (SMT)
El SMT se diferencia, en que procura duplicar tan pocas porciones del CPU como sea posible. A pesar que se
considera paralelismo a nivel de proceso, su implementación se asemeja más a un diseño superescalar. En lugar
de duplicar todo el CPU, los diseños SMT solamente duplican las piezas necesarias para lectura, decodificación, y
despacho de instrucciones, así como cosas como los registros de propósito general. Esto permite a un CPU SMT
mantener sus unidades de ejecución ocupadas más frecuentemente al proporcionarles las instrucciones desde
dos diferentes procesos. Una vez más esto es similar al paralelismo a nivel de instrucción, pero ejecuta
simultáneamente instrucciones de múltiples procesos en lugar de ejecutar concurrentemente múltiples
instrucciones del mismo proceso.
En cambio, cuando hablamos de computadores con múltiples CPU totalmente independientes podemos
encontrar:
MULTIPROCESAMIENTO SIMÉTRICO (SMP)
Consiste en una arquitectura multiprocesador en que dos o más procesadores idénticos pueden conectarse a una
única memoria principal compartida.
Los sistemas SMP permiten que cualquier procesador trabaje en cualquier tarea no importa en qué parte de la
memoria se encuentren los datos. Con buen apoyo del sistema operativo, sistemas SMP pueden mover
fácilmente tareas entre los procesadores para equilibrar la carga de trabajo de manera eficiente.
SMP tiene muchos usos en la ciencia, la industria y las empresas que utilizan a menudo la costumbre de software
programado para multiproceso (multitasked). Sin embargo, la mayoría de los productos de consumo tales como
procesadores de texto y juegos están escritos de tal manera que no pueden obtener grandes beneficios de
sistemas concurrentes. Para los juegos esto sucede ya si se escribe un programa para aumentar el rendimiento
en sistemas SMP puede producir una pérdida de rendimiento en sistemas monoprocesador.
ACCESO DE MEMORIA NO UNIFORME (NUMA)
NUMA es algo similar al SMP pero usa un modelo de acceso a memoria no uniforme, que significa que no
siempre se accede a memoria para leer/escribir datos, sino que se traspasa información entre procesadores. Esto
es importante para los computadores con muchos CPU porque el tiempo de acceso a la memoria, de cada
procesador, es agotado rápidamente con el modelo de memoria compartido del SMP, resultando en un
significativo retraso debido a los CPU esperando por la memoria. Esto puede mejorar considerablemente el
rendimiento de memoria. Como desventaja, la NUMA hace que el costo de trasladar datos de un procesador a
ARQUITECTURA AVANZADA
14
EMISION MULTIPLE DE INSTRUCCIONES
otro, como en el balanceo de carga, perjudique el rendimiento. Los beneficios de la NUMA se limiten a trabajo
compartido, en particular en los servidores donde los datos a menudo se asocian fuertemente con determinadas
tareas o usuarios.
Por lo tanto, NUMA es considerado un modelo mucho más escalable, permitiendo con éxito que en un
computador sean usados muchos más CPU que los que pueda soportar de una manera factible el SMP.
1 CPU/1 Thread
ARQUITECTURA AVANZADA
2 CPU/1 Thread
1 CPU/2 Thread
15
EMISION MULTIPLE DE INSTRUCCIONES
REFERENCIAS















http://es.wikipedia.org/wiki/Procesador_vectorial
http://informatica.uv.es/iiguia/AAC/AA/apuntes/aac_vector.pdf
http://dac.escet.urjc.es/~lrincon/uned/etc3/Etc3 -07.PDF
http://es.wikipedia.org/wiki/VLI
http://www.siliconintelligence.com/people/binu/pubs/vliw/node19.html
http://www.siliconintelligence.com/people/binu/pubs/vliw/node18.html
http://www.siliconintelligenc e.com/people/binu/pubs/vliw/node17.html
http://www.siliconintelligence.com/people/binu/pubs/vliw/node16.html
http://es.wikipedia.org/wiki/Superescalar
http://en.wikipedia.org/wiki/Simultaneous_multithreading
http://citavia.blog.de/2009/09/06/architecture -cpu-clustermicroarchitecture-multithreading-6910375/
J. Smith and G. Sohi, The Microarchitecture of Superscalar Processors.
Proceedings IEEE, Vol. 83, No. 12, Diciembre 1995.
William Stallings, Organización y Arquitectura de Computadores,
Capítulo 13: Paralelismo a nivel de instrucciones y procesadores
superescalares.
John Hennessy – David Patterson, Arquitectura de Computadores –
Un enfoque cuantitativo 3a Edición, Capítulo 3.
M. Jonhson, Superescalar Microprocessor Design– Prentice Hall, 1999.
ARQUITECTURA AVANZADA
16