PDF de programación - Paralelismo en monoprocesadores - Planificación en ILP

Paralelismo en

monoprocesadores

Planificación en ILP

Profesor: Mag. Marcelo Tosini
Cátedra: Arquitectura de Computadoras y técnicas Digitales
Carrera: Ingeniería de Sistemas
Ciclo: 4º año

1

Conceptos básicos

• Orden secuencial: orden de las instrucciones tal como surge de la
compilación tradicional. Las instrucciones de máquina respetan el
orden computacional impuesto por el código de alto nivel.

• Consistencia secuencial: orden de ejecución de las instrucciones que no
viola ninguna dependencia entre instrucciones (control, recursos o datos)
y, por lo tanto, mantiene la consistencia computacional del algoritmo.

• Secuencia (de ejecución): orden en que se ejecutan las instrucciones en

un procesador. La secuencia de ejecución puede diferir del orden
secuencial siempre y cuando no se pierda la consistencia secuencial.

2

Planificación

Reordenamiento de las instrucciones de un programa a fin de optimizar el uso

del procesador o aumentar la posibilidad de paralelismo.

Quien planifica:

• Compilador (Planificación estática): Reordenamiento de

instrucciones en tiempo de compilación para aumentar las
posibilidades de ejecución paralela.

• Procesador (Planificación dinámica): Selección de instrucciones

para ejecución a fin de ocupar plenamente todas las unidades
funcionales disponibles dentro del procesador.

3

Papel del compilador en la planificación

• Planificación estática:

Proporcionar código paralelo optimizado y libre de dependencias

Usada en procesadores antiguos sin capacidad de planificar
(primeros Superescalares y VLIW)

•Planificación dinámica:

Disparador de rendimiento

La detección y resolución de dependencias se realiza por hardware

Procesadores modernos (Escalares y Superescalares)

4

Tipos de Planificación de instrucciones en
ILP

• Planificación estática con optimización paralela

• Realizada por el compilador
• El procesador recibe código sin dependencias y optimizado para ejecución
paralela
• Procesadores VLIW

• Planificación dinámica sin optimización paralela estática

• Realizada por el procesador
• El procesador recibe código no optimizado para ejecución paralela
• Detecta y resuelve las dependencias
• Primeros procesadores ILP

• Planificación dinámica con optimización paralela estática

• Realizada por el procesador y el compilador
• El procesador recibe código optimizado para ejecución paralela
• Detecta y resuelve las dependencias
• Mayor parte de los procesadores superescalares

5

Diferencias entre compiladores
tradicionales e ILP

• Ejecución secuencial: no hay dependencias WAW ni WAR

• Criterios de asignación de registros:

• Los compiladores tradicionales maximizan la reutilización

de registros

• Los compiladores ILP evitan la reutilización de registros para

disminuir las dependencias WAR y WAW

• Los procesadores ILP necesitan más registros

• Dependencias de datos asociadas a referencias a memoria

• Sólo se tienen en cuenta para compiladores ILP

(adelantamiento de Loads)

6

Niveles de planificación estática

Planificación

de bloque básico

Planificación

de código

Planificación

de lazos

Planificación

global o de traza

i

R
e
n
d
m
e
n
t
o

i

i

N
v
e
l

d
e

p
a
r
a
e

l

l
i
s
m
o

e
x
t
r
a
d
o

í

7

Planificación de bloque básico

• Es la técnica de planificación más simple y menos efectiva

• Sólo las instrucciones dentro de un bloque básico son elegibles para

su reordenamiento

• Un bloque básico (BB) es una secuencia de código que no contiene

saltos

• Trabaja con listas de items (tareas, instrucciones) planificables de

las cuales se selecciona el item más adecuado en cada instante (ciclo
de ejecución)

• Se debe definir:

• Regla de selección: Permite seleccionar el conjunto de ítems

planificables

• Regla de elección de la mejor planificación: Selecciona del

conjunto el ítem más apto en un instante dado

8

Reglas de selección y elección de la
mejor planificación

• regla de selección: Son instrucciones elegibles

• No tienen dependencias con instrucciones anteriores
• Los recursos hardware necesarios están disponibles

• Elección de la mejor planificación: Buscar las instrucciones

que puedan causar paradas de otras instrucciones

• Basados en:

• Prioridad: pe.: distancia al final del bloque

• Criterios: Aplicación de un conjunto de criterios en un

orden determinado

• Número de sucesores
• Longitud de la vía más lenta

9

Ejemplo: DLX

for (I = 1 ; I <= 100 ; I++)
for (I = 1 ; I <= 100 ; I++)

x[I] = x[I] + s;
x[I] = x[I] + s;

lazo:
lazo:

LD
LD
f0, 0(r1)
f0, 0(r1)
ADDD f4, f0, f2
ADDD f4, f0, f2
SD
SD
0(r1), f4
0(r1), f4
SUBI
r1, r1, #8
r1, r1, #8
SUBI
BNEZ r1, lazo
BNEZ r1, lazo

; carga x[I]
; carga x[I]
; suma s
; suma s
; guarda x[I]
; guarda x[I]
; decrementa I
; decrementa I
; salta a inicio
; salta a inicio

Latencias:
Latencias:

ALU Pto Flotante : 3 ciclos
ALU Pto Flotante : 3 ciclos
ALU Pto Fijo
ALU Pto Fijo
: 1 ciclo
: 1 ciclo
Store : 1 ciclo
Store : 1 ciclo
Load : 2 ciclos
Load : 2 ciclos
: 2 ciclos
Saltos
Saltos
: 2 ciclos
10

Planificación en el DLX

Sin planificación

Con salto retardado

lazo:
lazo:

f0, 0(r1)
f0, 0(r1)

LD
LD
detención
detención
ADDD f4, f0, f2
ADDD f4, f0, f2
detención
detención
detención
detención
SD
SD
SUBI
SUBI
BNEZ r1, lazo
BNEZ r1, lazo
detención
detención

0(r1), f4
0(r1), f4
r1, r1, #8
r1, r1, #8

lazo:
lazo:

f0, 0(r1)
f0, 0(r1)

LD
LD
detención
detención
ADDD f4, f0, f2
ADDD f4, f0, f2
SUBI
SUBI
BNEZ r1, lazo
BNEZ r1, lazo
SD
SD

0(r1), f4
0(r1), f4

r1, r1, #8
r1, r1, #8

• SUBI y BNEZ suben a los slots de detención

del ADDD

• SD baja al slot de detención de BNEZ

Tiempo : 9 ciclos

Tiempo : 6 ciclos

11

Planificación arriba-abajo

Las operaciones se planifican en cuanto los operandos están disponibles

La mayoría de las operaciones comienzan tan pronto como es posible

La evaluación del salto se realiza en las primeras etapas del algoritmo

Pasos:

1. Selección del conjunto de instrucciones planificables (CP)
2. Elección de una instrucción del CP (preferentemente vía crítica)
3. Se planifica la instrucción.
4. Se rearma CP
5. Se repite desde 2. hasta que CP se vacíe

12

Planificación arriba-abajo

Armar un grafo de precedencia de instrucciones

• Cada nodo es una instrucción del bloque básico
• Cada arco indica la dependencia RAW entre los nodos que conecta
• Cada arco se marca con 2 valores:

• Latencia de la instrucción precedente (Li)
• Latencia total acumulada (La)
• Notación : (Li , La)

Parámetro:

• Earliest-Time (ET): para el sucesor de una instrucción planificada.

ET = tiempo actual + latencia de la instrucción planificada

13

Ejemplo

A = B + C – D

if E-D > 0 then

…..

Ld
r1, b(r0)
Ld
r2, c(r0)
Add
r3, r1, r2
Ld
r4, d(r0)
Sub
r5, r3, r4
Sd
r5, a(r0)
Ld
r6, e(r0)
Sub
r8, r6, r4
Cmp r9, r8, r0
r9, _then
Bc

Bloque básico

Instrucciones del bloque básico

14

Ejemplo…

Orden

Instrucción

Nemotecnico

Latencia (ns)

1:

2:

3:

4:

5:

6:

7:

8:

9:

Ld

Ld

Add

Ld

Sub

Sd

Ld

Sub

r1, b(r0)

r2, c(r0)

r3, r1, r2

r4, d(r0)

r5, r3, r4

r5, a(r0)

r6, e(r0)

r8, r6, r4

Cmp

r9, r8, r0

10:

Bc

r9, _then

Lb

Lc

Add

Ld

Sub

Sta

Le

Sub2

Cmp

Bc

2

2

3

2

3

1

2

3

5

2

15

Ejemplo

La traza de mayor latencia es la
del salto que tarda 12 ciclos de reloj

La planificación debiera adelantar esta
traza para que empiece cuanto antes

Lb

(2,2)

Lc

(2,2)

Add

(3,5)

Ld

(2,2)

Sub

(3,8)

Sta

(1,9)

(2,2)

Le
(2,2)

Sub2

(3,5)

Cmp

(5,10)

Bc

(2,12)

16

Existe una dependencia
de control entre BC y
Sta

Traza mas larga

Ejemplo
Planificación para tiempo 0

Ciclo

Conjunto de
planificables

Elegida

0

Lb , Lc, Ld , Le

Le

Lb

(2,2)

Lc

(2,2)

Add

(3,5)

Ld

(2,2)

Sub

(3,8)

Sta

(1,9)

(2,2)

Le
(2,2)

Sub2

(3,5)

Cmp

(5,10)

Bc

(2,12)

17

Ejemplo
Planificación para tiempo 1

Ciclo

0

1

Conjunto de
planificables

Lb , Lc, Ld , Le

Lb , Lc, Ld

Elegida

Le

Ld

Lb

(2,2)

Lc

(2,2)

Add

(3,5)

Ld

(2,2)

Sub

(3,8)

Sta

(1,9)

(2,2)

Sub2

ET = 2

(3,5)

Cmp

(5,10)

Bc

(2,12)

18

Ejemplo
Planificación para tiempo 2

Ciclo

0

1

2

Conjunto de
planificables

Lb , Lc, Ld , Le

Lb , Lc, Ld

Lb , Lc

Elegida

Le

Ld

Lb

Lb

(2,2)

Lc

(2,2)

Add

(3,5)

Sub

ET = 3

(3,8)

Sta

(1,9)

Sub2

ET = 3

(3,5)

Cmp

(5,10)

Bc

(2,12)

19

Ejemplo
Planificación para tiempo 3

Lc

(2,2)

ET = 4

Add

(3,5)

Conjunto de
planificables

Lb , Lc, Ld , Le

Lb , Lc, Ld

Lb , Lc

Elegida

Le

Ld

Lb

Ciclo

0

1

2

3

Lc , Sub2

Sub2

Sub

ET = 3

(3,8)

Sta

(1,9)

Sub2

ET = 3

(3,5)

Cmp

(5,10)

Bc

(2,12)

20

Ejemplo
Planificación para tiempo 4

Ciclo

0

1

2

3

4

Conjunto de
planificables

Lb , Lc, Ld , Le

Lb , Lc, Ld

Lb , Lc

Lc , Sub2

Lc

Elegida

Le

Ld

Lb

Sub2

Lc

Lc

(2,2)

ET = 4

Add

(3,5)

Sub

ET = 3

(3,8)

Sta

(1,9)

Cmp

ET = 6

(5,10)

Bc

(2,12)

21

Ejemplo
Planificación para tiempo 6

Ciclo

0

1

2

3

4

6

Conjunto de
planificables

Lb , Lc, Ld , Le

Lb , Lc, Ld

Lb , Lc

Lc , Sub2

Lc

Add , Cmp

Elegida

Le

Ld

Lb

Sub2

Lc

Cmp

ET = 6

Add

(3,5)

Sub

ET = 3

(3,8)

Sta

(1,9)

Cmp

ET = 6

(5,10)

Bc

(2,12)

22

Ejemplo
Planificación para tiempo 7

Ciclo

0

1

2

3

4

6

7

Conjunto de
planificables

Lb , Lc, Ld , Le

Lb , Lc, Ld

Lb , Lc

Lc , Sub2

Lc

Add , Cmp

Add

Elegida

Le

Ld

Lb

Sub2

Lc

Cmp

Add

ET = 6

Add

(3,5)

Sub

ET = 3

(3,8)

Sta

(1,9)

Bc

ET = 11

(2,12)

23

Ejemplo
Planificación para tiempo 10

Ciclo

0

1

2

3

4

6

7

10

Conjunto de
planificables

Lb , Lc, Ld , Le

Lb , Lc, Ld

Lb , Lc

Lc , Sub2

Lc

Add , Cmp

Add

Sub

Elegida

Le

Ld

Lb

Sub2

Lc

Cmp

Add

Sub

Sub

ET = 10

(3,8)

Sta

(1,9)

Bc

ET = 11

(2,12)

24

Ejemplo
Planificación para tiempo 11

Ciclo

0

1

2

3

4

6

7

10

11

Conjunto de
planificables

Lb , Lc, Ld , Le

Lb , Lc, Ld

Lb , Lc

Lc , Sub2

Lc

Add , Cmp

Add

Sub

Bc

Elegida

Le

Ld