Procesadores de emisión múltiple - UTMfsantiag/ArqComputadoras/08_Procesadores_de... ·...

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