PDF de programación - Tema 3 - Lanzamiento múltiple, Límites de ILP, Multithreading

Arquitectura de Computadores

TEMA 3

Lanzamiento múltiple, Límites de ILP,

Multithreading

Curso 2015-2016

Contenidos

o Introducción: CPI < 1

o Lanzamiento múltiple de instrucciones: Superescalar, VLIW

o Superescalar simple

o VLIW

o Superescalar con planificación dinámica

o Límites de ILP

o Ejemplo: Implementaciones X86

o Thread Level Parallelism y Multithreading

o Bibliografía

o Capítulo 3 y Apéndice H de [HePa12]

o Capítulos 6 y 7 de [SiFK97]

AC — Tema 3

Curso 2015-16

2

Más ILP: Lanzamiento múltiple

 Introducción

• ¿Por que limitar a una instrucción por ciclo?

• Objetivo: CPI < 1

• Lanzar y ejecutar simultáneamente múltiples instrucciones por
ciclo

• ¿Tenemos recursos?

• Más área de silicio disponible
• Técnicas para resolver las dependencias de datos (planificación )
• Técnicas para resolver las dependencias de control (especulación)

AC — Tema 3

Curso 2015-16

3

Más ILP: Lanzamiento múltiple

 Alternativas
 Procesador Superescalar con planificación estática

 Procesador Superescalar con planificación dinámica+( especulación)

 Procesadores VLIW ( very long instruction processor)

 Superescalar

 Lanza de 1 a 8 instrucciones por ciclo
Reglas de ejecución

o Ejecución en orden-planificación estática
o Ejecución fuera de orden-planificación dinámica

VLIW

 Numero fijo de instrucciones por ciclo
 Planificadas estáticamente por el compilador
 EPIC ( Explicitly Parallel Instruction Computing ) Intel/HP

AC — Tema 3

Curso 2015-16

4

Más ILP: Lanzamiento múltiple

 Alternativas

Tipo

Superescalar
estático

Superescalar
dinámico

Superescalar
especulativo

Forma del
“issue”

Detección de
riesgos

Planificación Ejemplos

Dinámico HW

estática

Embeded
MIPS, ARM

Dinámico HW

dinámica

ninguno

Dinámico HW

Dinámica con
especulación

P4, Core2,
Power5, 7
SparcVI, VII

VLIW

Estático

Básicamente
SW

estática

TI C6x
Itanium

AC — Tema 3

Curso 2015-16

5

Más ILP: Lanzamiento múltiple

 SUPERESCALAR

Grado 2
2 Vías

 Duplicar todos los recursos:

o Puertas bloque de Registros
o Fus
o Puertas de memoria,..
o Control

 Ideal CPI= 0.5 se reduce por:

o Saltos
o LOADs
o Dependencias verdaderas LDE

Necesita:

Efecto de riesgo LDE
provocado por un Load

o Predicción sofisticada
o Tratamiento de LOAD; Cargas especulativas, técnicas de prebúsqueda

Más presión sobre la memoria
Efecto incremental de los riesgos
Se puede reducir complejidad con limitaciones ( Un acceso a memoria por ciclo)

AC — Tema 3

Curso 2015-16

6

Más ILP: Lanzamiento múltiple

 SUPERESCALAR Simple ( estático, en orden)

• Regla de lanzamiento: Una instrucción FP (2ª)+ una instrucción de cualquier otro tipo (1ª)
• Buscar y decodificar dos instrucciones por ciclo ( 64 bits)

Ordenamiento y decodificación
Se analizan en orden. Sólo se lanza la 2ªsi se ha lanzado la 1ª ( conflictos)

• Unidades funcionales segmentadas ( una ope. por ciclo ) ó múltiples (división, raíz), más

puertas en el bloque de registros

• Lanzamiento simple, recursos no conflictivos ( diferentes reg y UF,.. ), excepto

Conflictos de recursos; load, store, move FP  más puertas en el bloque de reg.
Conflictos de datos LDE  más distancia entre instrucciones.

Cache de Instrucciones

Buffer de Instrucciones

Detector
riesgos

Solo detecta y

Bloquea el lanzamiento

REGISTROS

Y además... Efecto de
los saltos (delay slot)

AC — Tema 3

Curso 2015-16

7

Más ILP: Lanzamiento múltiple

SUPERESCALAR Simple ( estático, en orden)

Loop:

Instrucción entera
LD
LD
LD
LD
LD
SD
SD
SD
SUBI
SD
BNEZ
SD

F0,0(R1)
F6,-8(R1)
F10,-16(R1)
F14,-24(R1)
F18,-32(R1)
0(R1),F4
-8(R1),F8
-16(R1),F12
R1,R1,#40
16(R1),F16
R1,LOOP
8(R1),F20

Instrucción FP

ADDD
ADDD
ADDD
ADDD
ADDD

F4,F0,F2
F8,F6,F2
F12,F10,F2
F16,F14,F2
F20,F18,F2

Separadas por 2 ciclos

Ciclo
1
2
3
4
5
6
7
8
9
10
11
12

• Desarrollo para ejecución superescalar: se desarrolla una iteración más.

12 ciclos, 2.4 ciclos por iteración

• El código máquina está compacto en la memoria

AC — Tema 3

Curso 2015-16

8

Más ILP: Lanzamiento múltiple

 SUPERESCALAR Simple (estático, en orden)

 Ventajas

• No modifica código. Compatibilidad binaria

• No riesgos en ejecución

 Desventajas

• Mezcla de instrucciones. Solo obtiene CPI de 0.5 en programas con 50 % de FP

• Bloqueos en el lanzamiento

• Planificación fija: No puede adaptarse a cambios en ejecución ( Fallos de cache )

• Los códigos deben de ser replanificados para cada nueva implementación

(eficiencia)

AC — Tema 3

Curso 2015-16

9

Más ILP: Lanzamiento múltiple

 VLIW

 El análisis de dependencias en tiempo de compilación
 Muchas operaciones por instrucción ( IA64 packet, Transmeta molécula)
 Todas las operaciones de una instrucción se ejecutan en paralelo
 Instrucciones con muchos bits
 Muchas operaciones vacías (NOP)

IP

Instrucción: Incluye varias instrucciones
convencionales de tres operandos
una por ALU

Bloque de registros,
3 puertas por ALU

AC — Tema 3

Curso 2015-16

10

Más ILP: Lanzamiento múltiple

 VLIW

Ejemplo Tema 2

LOOP

LD
ADDD
SD
SUBI
BNEZ

F0,0(R1)
F4,F0,F2
0(R1),F4
R1,R1,#8
R1,LOOP

• Aplicar técnicas conocidas para minimizar

paradas

• Unrolling
• Renombrado de registros

• Latencias de uso: LD a ADD 1 ciclo, ADD a SD 2

ciclos

• Opción: desarrollar 4 iteraciones y planificar:

14 ciclos, 3.5 ciclos por iteración

LOOP:

LD
LD
LD
LD
ADDD
ADDD
ADDD
ADDD
SD
SD
SUBI
SD
BNEZ
SD

F0, 0(R1)
F6, -8(R1)
F10, -16(R1)
F14,-24(R1)
F4, F0, F2
F8, F6, F2
F12, F10, F2
F16, F14, F2
0(R1), F4
-8(R1), F8
R1, R1, #32
16(R1), F12
R1, LOOP
8(R1), F16; 8-32 = -24

AC — Tema 3

Curso 2015-16

11

 VLIW

Más ILP: Lanzamiento múltiple

Loop unrolling en VLIW (desarrollo 7 iteraciones)

LOOP:

LD F0,0(R1)
ADDD F4,F0,F2
SD 0(R1),F4
SUBI R1,R1,#8
BNEZ R1, LOOP

; F0 = array element
; add scalar in F2
; store result
; decrement pointer
; branch if R1!=0

Mem ref 1

LD F0,0(R1)

Mem ref 2

LD F6,-8(R1)

LD F10,-16(R1)

LD F14,-24(R1)

FP op

FP op

Int op/branch

LD F18,-32(R1)

LD F22,-40(R1)

ADDD F4,F0,F2

ADDD F8,F6,F2

LD F26,-48(R1)

ADDD F12,F10,F2

ADDD F16,F14,F2

ADDD F20,F18,F2

ADDD F24,F22,F2

SD 0(R1),F4

SD -8(R1),F8

ADDD F28,F26,F2

SD -16(R1),F12

SD -24(R1),F16

SD 24(R1),F20

SD 16(R1),F24

SD 8(R1),F28

SUBI R1,R1,#56

BNEZ R1, LOOP

 7 iteraciones en 9 ciclos: 1.3 ciclos por iteración
 23 operaciones en 45 slots (~50% de ocupación)
 Muchos registros necesarios

AC — Tema 3

Curso 2015-16

12

Más ILP: Lanzamiento múltiple

VLIW
VENTAJAS

 Hardware de control muy simple

 No detecta dependencias
 Lógica de lanzamiento simple

 Puede explotar paralelismo a todo lo largo del programa (compilador)

DESVENTAJAS

 Planificación estática; Muy sensible a fallos de cache
 Necesita desenrollado muy agresivo
 Bloque de registros muy complejo en área y tiempo de acceso
 Muchas NOP

 Poca densidad de código
 Capacidad y AB de la cache de instrucciones

 Compilador muy complejo
 No binario compatible
 Operación síncrona para todas las operaciones de una instrucción

AC — Tema 3

Curso 2015-16

13

Más ILP: Lanzamiento múltiple

EPIC: Explicitly Parallel Instruction Computing (IA64)

 Instrucciones de 128 bits

 Operaciones de tres operandos
 TMP (Template) codifica dependencias entre las operaciones
 128 registros enteros (64bits), 128 registros FP (82bits)
 Ejecución predicada. 64 registros de predicado de 1 bit
 Cargas especulativas
 Hw para chequeo de dependencias

Instrucción 1 Instrucción 2 Instrucción 3 TMP

128 bits

Ope Reg1 Reg2 Reg3 Predicado

41 bits

Primera implementación Itanium (2001), 6 operaciones por ciclo, 10 etapas, 800Mhz

Segunda implementación Itanium2 (2005), 6 operaciones por ciclo, 8 etapas, 1,66Ghz

AC — Tema 3

Curso 2015-16

14

Más ILP: Lanzamiento múltiple

SUPERESCALAR con Planificación Dinámica.Fuera de orden

 Un Diseño Simple
• Estaciones de reserva separadas para enteros (+reg) y PF (+reg)
• Lanzar dos instrucciones en orden ( ciclo de lanzamiento: partir en dos subciclos)
• Solo FP load causan dependencias entre instrucciones enteras y PF

• Reemplazar buffer de load con cola. Las lecturas se hacen en orden
• Ejecución Load: “check” dirección en cola de escritura para evitar LDE
• Ejecución Store: “check” dirección en cola de lecturas para evitar EDL

 Rendimiento del procesador

Iteración Instrucción
no.
1
1
1
1
1
2
2
2
2
2

LD F0,0(R1)
ADDD F4,F0,F2
SD 0(R1),F4
SUBI R1,R1,#8
BNEZ R1,LOOP
LD F0,0(R1)
ADDD F4,F0,F2
SD 0(R1),F4
SUBI R1,R1,#8
BNEZ R1,LOOP

Lanzada

Comienza
Ejecución
(número de ciclo)

Escribe resultado

1
1
2
3
4
5
5
6
7
8

2
5
9
4
6
6
9
13
8
10

4
8

5

8
12

9

4 ciclos por
iteración

AC — Tema 3

Curso 2015-16

15

Más ILP: Lanzamiento múltiple

 SUPERESCALAR con Planificación Dinámica y Especulación

Ejecución fuera de orden. Finalización en orden

decodificación

+

renombramiento

registros

emisión

ejecución

reordenación

+

finalización

búsqueda inst

+

predicción

saltos

ventana de
ejecución

programa
estático

flujo dinámico
instrucciones

planificación dinámica y

ejecución fuera de

escritura
en orden

orden

AC — Tema 3

Curso 2015-16

16

Más ILP: Lanzamiento múltiple

 EV7 ALPHA 21364 Core (2003)

FETCH MAP QUEUE REG EXEC DCACHE
Stage: 0 1 2 3 4 5 6

Branch
Predictors

Int
Reg
Map

Int

Issue
Queue

(20)

Next-Line
Address

L1 Ins.
Cache
64KB
2-Set

80 in-flight instructions
plus 32 loads and 32 stores

4 Instructions / cycle

FP
Reg
Map

FP

Issue
Queue

(15)

Reg
File
(80)

Reg
File
(80)

Reg
File
(72)

Exec

Exec

Exec

Exec

Addr

Addr

L1
Data
Cache
64KB
2-Set

L2 cache
1.75MB

7-Set

FP ADD
Div/Sqrt

FP MUL

Victim
Buffer

Miss

Address

AC — Tema 3

Curso 2015-16

17

Límites del ILP

 El lanzamiento múltiple permite mejorar el rendimiento sin