Procesadores de emisión múltiple
Arquitectura de Computadoras
M. C. Felipe Santiago EspinosaMayo/2018
Procesadores superescalares• La segmentación permite la ejecución simultánea de
instrucciones, pero sólo una instrucción puede estar en cada etapa del cauce.
• Una arquitectura superescalar dispone de múltiples cauces de instrucciones independientes, y a su vez segmentados, de modo que puede iniciarse la ejecución de varias instrucciones en forma simultánea.• MIP: multiple issue precessors, procesadores de emisión múltiple.
• Una arquitectura superescalar requiere la duplicación de recursos y la utilización de diversas técnicas que permitan optimizar su utilización.
2
Procesadores superescalares• Un procesador superescalar puede alcanzar una productividad
mayor a una instrucción por ciclo de reloj porque puede iniciar la ejecución de varias instrucciones en el mismo ciclo (CPI < 1).• En la práctica se consiguen aceleraciones cercanas a dos (CPI = 0.5).
• Ejemplo de organización superescalar:
3
Procesadores superescalares• Desde 1998 todos los procesadores comerciales son
superescalares. • S u s o r í ge n e s e stá n e n p ro c e s a d o re s R I S C p o r s e r d e
implementación más simple. • Luego lo incorporan los CISC, al incluir múltiples micro-
arquitecturas internas.
• INTEL Pentium Pro y Pentium II son procesadores CISC con microarquitectura RISC superescalar (2 ALU + 1 FP).
• Los más modernos, PowerPC970: 4 ALU + 1 MEM + 2 FP + 2 SIMD (Single Instruction Multiple Data).
4
Supersegmentación• En la segmentación, muchas etapas requieren menos de la
mitad de un ciclo de reloj para completarse.• La supersegmentación aprovecha este hecho y divide las
etapas de un cauce en sub-etapas, con ello, se aumenta el número de instrucciones en el cauce en un determinado instante.
• Una supersegmentación de grado dos divide cada etapa en dos y utilizando un reloj interno del doble de frecuencia, se pueden obtener dos instrucciones por cada ciclo del reloj original.• El rendimiento no se duplica porque hay etapas que si requieren
el periodo completo.5
Representación gráfica
Segmentación a 4 etapas:
Supersegmentación:
Superescalar:
6
ParalelismoDiscusión importante:• Paralelismo a nivel de instrucciones (ILP) vs.• Paralelismo a nivel de la máquina (MLP)
luego...• Paralelismo a nivel de threads (TLP)
7
Paralelismo a nivel de instrucciones
• Existe ILP cuando las instrucciones que componen un programa son independientes.
• El código puede ser reordenado sin alterar el resultado.• Existe la posibilidad de ejecutar instrucciones en paralelo,
rompiendo la secuencialidad implícita en un programa estático.
• Las dependencias de datos son críticas en este contexto.• Ejemplo de operaciones independientes:
for(i=0;i<1000;i++) x[i]=x[i]+y[i];• Ejemplo de operaciones dependientes:
for(i=1;i<1000;i++) x[i]=(x[i]+x[i-1])/2;• Se debe detectar el ILP. 8
Paralelismo a nivel de la máquina• MLP es una medida de la capacidad del procesador para sacar
partido del ILP.• Depende del número de instrucciones que puedan captarse y
ejecutarse simultáneamente (número de cauces paralelos).
• Dos aproximaciones:• Planificación Dinámica (HW): P4, Athlon, UltraSPARCIII.
• Algoritmo de Tomasulo: disminuye RAW y elimina WAW y WAR con renombrado de registros.
• Por la cantidad de recursos, son procesadores SUPERESCALARES.
• Planificación estática (SW): IA-64.• VLIW (Very long instruction word). 9
Arquitectura Superescalar• Explotación dinámica (por hardware, via MLP) del ILP
presente en el programa
FETCH DECODE DISPATCH ISSUE EXECUTE COMMITCaptura Decodificar Encolar Emitir Ejecutar Finalizar
10
Ciclo de Instrucción• CAPTURA ( fetch) : Múlt ip les inst rucc iones son captadas
simultáneamente, utilizando técnicas de predicción de saltos.• DECODIFICACION (decode): En dos pasos,
1. Predecodificación entre la memoria y caché para la identificación de saltos
2. Determinación de la operación, localización de operandos y localización del resultado.
• VENTANA DE EJECUCION = ENCOLADO (dispatch) y EMISION (issue): Identificación de las instrucciones de la cola que están listas para comenzar su ejecución, aquellas con sus dependencias satisfechas.
• EJECUCION (execute): En paralelo, en diferentes unidades funcionales.
• FINALIZACION (commit): El resultado es confirmado en su destino.11
LimitacionesEl rendimiento de una Arquitectura Superescalar se ve afectado por:
• Conflictos en los recursos: Similar a los riesgos estructurales de los cauces. La solución consiste en la duplicación de recursos.
• Dependencia de control: Los saltos reducen la eficiencia.• Insertar un retardado es simple en RISC pero no en superescalares
CISC, ya que se deben insertar varias detenciones. El rendimiento mejora si el compilador desenrolla ciclos (Loop unrolling).
• Dependencia de datos: Se produce cuando dos instrucciones utilizan el mismo registro. Impiden que las instrucciones puedan reordenarse. La verificación de la dependencia de datos incrementa la complejidad del despachador.
12
(Re) Clasificación de las dependencias de datos
• Dependencias verdaderas: una instrucción necesita un operando generado por una instrucción anterior. Son intrínsecas del programa y no pueden eliminarse (RAW).
• Dependencias artificiales: son conflictos de almacenamiento que pueden solucionarse con más registros (internos de la CPU, usualmente x2) (Register renaming):• Dependencia de salida: dos instrucciones van a escribir en el
mismo destino (WAW).• Antidependencia: todavía se está usando un registro y otra
instrucción siguiente lo reescribe (WAR).
13
Técnicas de optimización• Se utilizan básicamente tres técnicas de hardware para
aumentar el paralelismo de la máquina (MLP) y por lo tanto las prestaciones del sistema:1. Duplicación de recursos2. Política de emisión de instrucciones3. Renombrado de registros
• Se agregan, de ser posible, técnicas de software (compilador) para asistir al hardware en la detección.
• IMPORTANTE: Si no existe ILP no es posible que haya MLP eficiente. 14
1. Duplicación de recursos• No só lo se requieren recursos para ejecutar var ias
instrucciones en paralelo, también para captar y decodificar varias instrucciones simultáneamente.
• El despachador es crucial, ya que debe mantener ocupadas las unidades funcionales (UF). Es el único elemento “inteligente”; el resto es fuerza bruta.
• Tipos de Unidades Funcionales:• Multiplicación/División en punto flotante• Suma/Resta en punto flotante• Operaciones con enteros• Accesos a memoria: Load/Store• Branch, etc. 15
FETCH DECODE DISPATCH ISSUE EXECUTE COMMITCaptura Decodificar Encolar Emitir Ejecutar Finalizar
16
2. Políticas de emisión de instrucciones
• Se clasifican según dos factores:• El orden según el cual las instruccciones son enviadas para su
ejecución (issue).• El orden en que las instrucciones finalizan al escribir en registros o
memoria (commit).• La polít ica más simple es emitir y f inalizar en orden
secuencial.• Tiene pocas probabilidades de encontrar instrucciones que
puedan ejecutarse en paralelo y depende mucho de cómo está escrito y compilado el programa.
• El procesador sólo se ocupa por dependencias reales ya que las dependencias de salida y antidependencias no existen.
• La Segmentación genera detenciones del cauce (stall). 17
2. Políticas de emisión de instrucciones (2)
• El rendimiento aumenta si se permite alterar el orden de emisión o finalización (o ambos), siempre que se mantenga la exactitud del resultado.
• Finalización desordenada: no espera a que terminen las instrucciones anteriores para enviar la actual. Aparecen las dependencias de salida (además de las verdaderas), por lo que se necesita una lógica de emisión más complicada. Peligroso ante interrupciones.
• Emisión desordenada (implica la anterior): evaluando una ve nta n a d e e j e c u c i ó n s e b u s ca n i n st r u c c i o n e s s i n dependencia de datos ni conflictos de recursos (anticipación). Aparecen las antidependencias. 18
2. Políticas de emisión de instrucciones (3)
Ventana de ejecución• Es el conjunto de instrucciones que se consideran para su
ejecución en un determinado momento. El hardware determina qué instrucciones de la ventana pueden enviarse a ejecutar en paralelo, limitado por dependencias de datos y disponibilidad de recursos.
• La ventana debe ser lo más grande posible. La limitan la capacidad de captar instrucciones y los saltos.
• Se utiliza predicción de saltos y ejecución especulativa. La porción de código predicha se incorpora a la ventana y se ejecuta. Si la predicción fue correcta el resultado se hace visible y permanente (commit), si no se elimina. 19
2. Políticas de emisión de instrucciones (4)
• Emisión y finalización en orden:
20
2. Políticas de emisión de instrucciones (5)
• Emisión ordanada y finalización fuera de orden:
21
2. Políticas de emisión de instrucciones (6)
• Emisión y finalización fuera de orden:
22
3. Renombrado de registros
• La emisión fuera de orden hace que los valores de los registros no se conozcan completamente en cada instante de tiempo.
• Las instrucciones entran en conflicto y el procesador debe resolverlo de alguna forma.
• Las técnicas de software pueden empeorar la situación.• El renombrado se realiza por hardware y para ello el
procesador dispone de registros adicionales (internos y ocultos al programador) para una asignación automática.
• Lo usual es tener duplicado el banco de registros (existen R3a y R3b, por ejemplo).
• Los efectos de las dependencias art if ic iales pueden disminuirse por esta técnica.
23
4. Técnicas de compilación
• La planif icac ión por medio del compi lador está condicionada a que el programa pueda ser recompilado repetitivamente para optimizar en cada pasada.
• Algunas técnicas que pueden utilizarse:a) Reagrupación de instrucciones independientes (por
ejemplo de a cuatro en el Pentium II).b) Adelanto de instrucciones que generen dependencia
real de datos.c) Desenrollo de lazos, etc.
24
Juntando todoLas Arquitecturas Superescalares se caracterizan por:
• Captura y decodificación simultánea de varias instrucciones.• Varias unidades funcionales segmentadas en paralelo.• Emisión y finalización desordenada con ventana de
instrucciones.• Renombrado de registros.• Asistencia desde el compilador.
25
MIPS R10000
26
MIPS R10000
27
Pentium 4• 80486 - CISC• Pentium – some superscalar components
• Two separate integer execution units• Pentium Pro – Full blown superscalar• Subsequent models refine & enhance superscalar design
28
Pentium 4 - Block Diagram
29
Pentium 4 - Operation• Fetch instructions form memory in order of static program• Translate instruction into one or more fixed length RISC
instructions (micro-operations)• Execute micro-ops on superscalar pipeline
• micro-ops may be executed out of order• Commit results of micro-ops to register set in original program
flow order• Outer CISC shell with inner RISC core• Inner RISC core pipeline at least 20 stages
• Some micro-ops require multiple execution stages• Longer pipeline
• c.f. five stage pipeline on x86 up to Pentium30
Pentium 4 - Pipeline
31
Pentium 4 - Pipeline Operation (1)
32
Pentium 4 - Pipeline Operation (2)
33
Pentium 4 - Pipeline Operation (3)
34
Pentium 4 - Pipeline Operation (4)
35
Pentium 4 - Pipeline Operation (5)
36
Pentium 4 - Pipeline Operation (6)
37
PowerPC• Direct descendent of IBM 801, RT PC and RS/6000• All are RISC• RS/6000 first superscalar• PowerPC 601 superscalar design similar to RS/6000• Later versions extend superscalar concept
38
PowerPC 601 General View
39
PowerPC 601 Pipeline Structure
40
PowerPC 601 Pipeline
41
Conclusiones
• Con solo agregar unidades funcionales, sin otras técnicas, las mejoras en rendimiento serán mínimas.
• La emisión desordenada es importante porque permite buscar instrucciones independientes hacia adelante.
• El renombrado de registros puede mejorar el rendimiento hasta en un 30%, con la única limitación de la dependencia real de datos.
• Es importante disponer de una buena capacidad de captación y decodificación para poder utilizar una ventana grande de instrucciones.
42
Arquitecturas VLIW• Las arquitecturas VLIW (very long instruction word) también
corresponden a procesadores de emisión múltiple.• A diferencia de los procesadores superescalares, la
planificación de las instrucciones la realiza el compilador.• Durante la compilación se crean paquetes de emisión que
contienen varias instrucciones en un orden de ejecución que no afecte la semántica del programa.
• Una típica instrucción VLIW tiene cientos de bits de longitud.• Históricamente se construyeron pocas CPU’s VLIW de
propósito general. A pesar de explotar mucho ILP, no tuvieron éxito comercial. Actualmente algunos DSP’s explotan esta técnica. 43
44
Diferencias y Semejanzas con Superescalares
• Semejanzas: misma estructura básica:• Compuesta por múltiples U.F. operando en
paralelo• Banco Único de Registros (o dos para FX y FP)
• Diferencias: Tipo de instrucciones y planificación de instrucciones
45
Diferencias y Semejanzas con Superescalares
EUEUEU
Única Instrucción MultioperaciónUnidad de Fetch
Caché de Instr.
Banco de Registros
VLIW
46
Diferencias y Semejanzas con Superescalares
EUEUEU
Múltiples InstruccionesUnidad de Fetch
Caché de Instr.
Banco de Registros
Superescalar
Decode/ Inicio
47
Tipos de Instrucciones• Las arquitecturas VLIW están controladas por instrucciones
largas que contienen un campo de control por cada una de las UF disponibles en la arquitectura.
• La longitud de la instrucción depende de dos factores: número de UF disponibles y número de bits necesarios para controlar cada UF.
• El número de UF suele ser grande : de 5 a 30. El número de bits de control para cada UF suele ser de 16 o 32 ====> palabras de instrucción de 100-1kbit
• Ejemplos: Trace 7/200 ejecuta 7 operaciones por ciclo y utiliza una palabra de instrucción de 256 bits.
El concepto
48
Situación real
49
50
Arquitectura VLIWVentaja: • Se reduce la complejidad del hardware (no hay detección de
riesgos, ni renombre, ni despacho en desorden o retiro ordenado, y además la etapa de decodificación es más sencilla) y permite incrementar la velocidad del reloj o aumentar el paralelismo o ambas a la vez.
Desventaja: • Mayor complejidad en el compilador, le toca detectar y eliminar los
riesgos por dependencias de datos, control y recursos. • El compilador necesita conocer todas las características del hardware,
tales como: número, tipo, latencia, intervalo de iniciación de las UF, detenciones por cargas, etc., aspectos que no sólo dependen de la arquitectura sino de la tecnología de implementación. ===>>>
• un mismo compilador NO puede utilizarse para distintos modelos aún de la misma familia. !!!!!
51
Planeación de Instrucciones• Mas problemas:
• El compilador no sabe cuando se producirán fallas en Caché, debe considerar el peor de retardo al generar su planeación. (cargas especulativas...)
• El formato de la instrucción VLIW no siempre contiene información útil en todos los campos ===>>pérdida de espacio y ancho de banda con memoria.
• Debido a la alta complejidad de la tarea, los VLIW NO pueden ser programados en lenguaje ensamblador !!!
52
GPP VLIW: Trace 2000
• Desarrollado por la empresa Multiflow en 1987. (Tanto Multiflow como Cydrome quebraron a principios de los 90)
• Son tres modelos: Trace 7/200, 14/200, 28/200 (7,14,28 instrucciones por ciclo)
53
GPP VLIW: Trace 2000
Registros FP (32x64)
FADDFMUL
Store Registers (32x32)
Registros FX (64x32)
ALU1ALU0
TLB
Dirección Física Store Buses
I boardF board
54
• Instrucción: 256 bits (7 instrucciones).• Fetch: una instrucción por ciclo mayor ( 2 ciclos menores
llamados beats).• Latencia de operaciones de enteros: 1 ciclo menor.• Latencia de operaciones de CF: 6 (FADD), 7 (FMUL) y 25 (FDIV)
ciclos menores. UF segmentadas.
GPP VLIW: Trace 2000
55
Trace 2000: Instrucción opcode dest dest_bank src1branch_test src2 inm
opcode dest dest_bank src1branch_test src2 inm
Constante Inmediata
Subword 0: ALU0, primer beat
Subword1: constante
Subword 2: ALU1, primer beat
opcode dest dest_banksrc1 src2
Subword3: FADD
L
opcode dest dest_bank src1branch_test src2 inm
Subword 4: ALU0, ultimo beat
Constante InmediataSubword 5: constante
opcode dest dest_bank src1branch_test src2 inm
Subword 6: ALU1, ultimo beat
opcode dest dest_banksrc1 src2
Subword 7 : FMUL
L
56
• Hay 4 subwords que permiten especificar salto condicional, pero sólo pueden utilizarse dos. Los saltos codifican su prioridad (cual es el primero) en el campo inmediato.
• De las 8 palabras, 6 especifican los bits de control para las UF, mientras que dos contienen operandos inmediatos.
• Las palabras de control contienen:• 7 bits de código de operación• dos campos para designar operandos fuentes y uno para destino (6 bits)• especificación del Banco de Registros (FX, FP o local store)
Trace 2000: Instrucción
57
• Las instrucciones se almacenan en una caché de 8K VLIW, que provee una instrucción por ciclo.
• Las subwords vacías no se almacenan en memoria. Cada palabra de 1K bit se asocia con una máscara de 32 bits que indica que subpalabras están vacías y cuales no.
• Comparado con el código compilado para un VAX, el código para TRACE es al menos 3 veces más largo.
• Números de rendimiento:• Trace 7/200 130 instrucciones/ciclo 6 Mflops• Cray XMP 8 instrucciones/ciclo 24 Mflops
Trace 2000: Instrucción
58
DSP: Digital Signal Processing• Orientados al procesado digital de señales: se utilizan
p a r a t e l é f o n o s c e l u l a r e s , m o d e m s , d i s c o s , contestadoras, etc.
• Al bajar el precio de los microprocesadores, éstos pueden ser incorporados a productos del mercado que demandan bajo costo, rapidez, pequeñez y poco consumo de energía===> se desarrollan chips que implementan el procesado de señales.
• El mercado de DSP está creciendo.
59
• Una de las funciones más comunes en DSP: filtrado de señales.
DSP: Funciones de Filtro
x x
+
D Dxn xn-1
c1 c2 x
+
Dx1
cn
yn
x
+
Cn-1
yn = xn c1 + xn-1c2 +........ + x1 cn
Tap
Tipos de DSP• Bajo Costo, Bajo Rendimiento:
• TI TMS320C2xx, Motorola DSP560xx (Familias)• Operan a razón de 20-50MIPS Nativos• Poco consumo de energía, poca memoria.• Uso: productos que requieren poco rendimiento pero
tienen mucho consumo, por ejemplo disk drivers, contestadoras.
• DSP medios:• Mayor frecuencia de reloj : 100-120 MIPS• TI TMS320C54xx, Lucent Technologies DSP16xx (Familias)• Hardware más sofisticado: pipeline, cachés de instrucciones• Uso: productos que requ ieren a l to rend im ie nto
computacional y poco consumo, por ejemplo modems de alta velocidad. 60
Tipos de DSP• Alto Rendimiento: Procesamiento ultrarrápido,
Diversidad de Arquitecturas.• Convencionales Mejorados• Inicio de Múltiples Instrucciones por Ciclo
• Convencionales Mejorados:• Se agregan UF (Multiplicadores, Sumadores), soporte
dentro del juego de instrucciones para el hardware adicional.
• Ejemplo: Lucent Technologies DSP16210 100MIPS• Inicio Múltiple:
• En GPP, el inicio múltiple se consigue con técnicas superescalares
• En DSP, con VLIW61
VLIW DSP’s• Texas Instruments TMS320C6000
• 256 bits por instrucción, divididas en 8 palabras de 32 bits controlan 8 UF’s independientes
• clock: 200Mhz• MIPS: 1600• Las subinstrucciones son más simples que las de los DSP
convencionales• No siempre están ocupadas todas las UF• Consumen más energía y los programas ocupan más memoria
que los DSP’s convencionales• Compiladores agrupan las instrucciones en palabras. Si no
puede agrupar el conjunto completo de subinstrucciones, inserta NOP’s.
• Mecanismo de compresión hardware y software para solucionar el problema del tamaño del código.
62
VLIW DSP’s• Un bit por instrucción se reserva para indicar si la instrucción
se ejecuta en paralelo con sus vecinas. El bit lo ajusta el programador o el compilador.
• Los bits p se escanean de izquierda a derecha. Si p de la instrucción i es igual a 1, entonces la instrucción i + 1 se ejecuta en paralelo con la instrucción i. El último p es siempre 0.
63
64
VLIW DSP’s
65
Ejemplo de código
MPY .M1 A0, A1, A2
|| ADD .L1 A4, A5, A2
|| ADD .L1X A7, B1, A6
• El lenguaje ensamblador especifica, además de los registros, modos de direccionamiento y operación a ser realizada, la Unidad Funcional, los Caminos de Datos ut i l izados, y el paralel ismo entre las instrucciones.
Multi-Threading
• Threads (hilos):
• Extensión de los lenguajes de programación que permite dividir una aplicación en tareas pseudo-simultáneas.
• Históricamente ayudaban al planificador del SO a realizar la división de tiempo (en el caso de un monoprocesador) o a distribuir la carga (multiprocesadores).
• Es diferente al concepto de proceso, pues entre hilos se comparte el estado y el espacio de memoria.
• Es más “liviano”. Los cambios de contexto son más rápidos a expensas de un cierto nivel de dependencia.
66
Multi-Threading (2)• El paralelismo a nivel de threads (TLP) es una medida de esta
propiedad en los programas. Puede ser explotado por los procesadores superescalares, ya que es más explícito que el ILP.
• Se pueden asignar diferentes UFs a los threads. • Muy útil para evitar que el procesador quede detenido ante una falla
de caché: continúa ejecutando otro hilo.• Son necesarios más registros y la captación simultánea desde
diferentes threads (al menos dos).• Si el SO está preparado, puede ver el HW como dos procesadores
lógicos.• Ejemplos:• INTEL HyperThreading (Pentium 4 HTT). Según Intel mejora 30%.• Simultaneus Multithreading (SMT) Power, SPARC.• P4x2 (S=1.3), Power5 x2, SPARC x4 (x8).
67
Multi-Threading (3)
68
Referencias
• 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, 4a Edición.
69