Pontificia Universidad Católica de Chile
Escuela de Ingeniería
Departamento de Ciencia de la Computación
[ Arquitectura de Computadores ]
AUMENTO DE DESEMPEÑO
IIC 2342
Semestre 2006-2
Domingo Mery
Präsentat
ion
D.Mery
1
Arquitectura de Computadores
[ Índice ]
8.1 Arquitectura RISC
8.2 Predicción de salto y prefetching
8.3 Escalabilidad
D.Mery
2
Arquitectura de Computadores
Präsentat
ion
[ Índice ]
8.1 Arquitectura RISC
8.2 Predicción de salto y prefetching
8.3 Escalabilidad
D.Mery
3
Arquitectura de Computadores
Präsentat
ion
[ Aumento de desempeño ]
RISC
CISC:
complex instruction set computer
se basa en que cada instrucción puede corresponder a varias
operaciones de bajo nivel, tales como leer de memoria, operación
aritmética, escribir en la memoria, sumar datos… todo en una
sola instrucción.
D.Mery
4
Arquitectura de Computadores
Präsentat
ion
[ Aumento de desempeño ]
RISC
La realidad de las operaciones…
Assign
Loop
Call
If
GoTo
Other
Total
Aparición
Dinámica
Pascal C
45% 38%
5%
3%
15% 12%
29% 43%
3%
6%
1%
100% 100%
Instruc. máquina
(ponderadas)
Pascal
C
13%
13%
42%
32%
31%
33%
11%
21%
3%
1%
100%
100%
Refer. a memoria
(ponderadas)
Pascal C
14% 15%
33% 26%
44% 45%
7%
13%
2%
1%
100% 100%
Frecuencia dinámica relativa ponderada de operaciones en
high level lenguages (HLL) compilados en arquitectura CISC
D.Mery
5
Arquitectura de Computadores
Präsentat
ion
[ Aumento de desempeño ]
RISC
La realidad de las operaciones…
Aparición
Instruc. máquina
Dinámica
(ponderadas)
Pascal C
Pascal
C
Assign
45% 38% 13%
13%
Loop
5%
3%
42%
32%
Call
15% 12% 31%
33%
If
29% 43% 11%
21%
GoTo
3%
CONCLUSIÓN:
Other
6%
1%
3%
1%
Total
100% 100%de100%
100%
Las instrucciones
llamada/retorno
Refer. a memoria
(ponderadas)
Pascal C
14% 15%
33% 26%
44% 45%
7%
13%
2%
1%
100% 100%
de
procedimientos son las que consumen más tiempo en
los programas típicos escritos en HLL.
D.Mery
6
Arquitectura de Computadores
Präsentat
ion
[ Aumento de desempeño ]
RISC
La realidad de las operandos…
Constantes enteras
Variables escalares
Arreglos estructuras
Total
100%
Pascal
16%
58%
26%
100%
C
Promedio
23%
20%
53%
55%
24%
25%
100%
Porcentaje dinámico de operandos
D.Mery
7
Arquitectura de Computadores
Präsentat
ion
[ Aumento de desempeño ]
RISC
La realidad de las operandos…
CONCLUSIÓN:
Hay un predominio de referencias a operandos
escalares.
Constantes enteras
Variables escalares
Arreglos estructuras
Total
100%
Pascal
16%
58%
26%
100%
C
Average
23%
20%
53%
55%
24%
25%
100%
Porcentaje dinámico de operandos
D.Mery
8
Arquitectura de Computadores
Präsentat
ion
[ Aumento de desempeño ]
RISC
La realidad de las llamadas a procedimientos…
Al 98% de los procedimientos llamados dinámicamente se les pasan
menos de 6 argumentos,
El 92% de los procedimientos usan menos de seis variables
escalares locales.
Además es poco común tener una larga secuencia ininterrumpida de
llamadas a procedimientos seguida por la correspondiente secuencia
de retornos.
D.Mery
9
Arquitectura de Computadores
Präsentat
ion
[ Aumento de desempeño ]
RISC
La realidad de las llamadas a procedimientos…
CONCLUSIÓN:
Al 98% de los procedimientos llamados dinámicamente se les pasan
menos de 6 argumentos,
Los programas permanecen confinados en una
ventana bastante estrecha de profundidad de
invocación
procedimientos…
las referencias
a
El
92% de los a
procedimientos
usan menos
de seis variables
escalares
locales.
operandos
están muy localizadas.
Además es poco común tener una larga secuencia ininterrumpida de
llamadas a procedimientos seguida por la correspondiente secuencia
de retornos.
D.Mery
10
Arquitectura de Computadores
Präsentat
ion
[ Aumento de desempeño ]
RISC
Por lo tanto, intentar realizar una arquitectura de repertorio de
instrucciones cercano al de los HLL, no es necesariamente una
estrategia de diseño más efectiva.
Surgen las arquitecturas RISC:
reduced (or regular) instruction set computer
• Usan un gran número de registros
• Usan un diseño cuidadoso de los pipelines
• Usan un repertorio de instrucciones reducido
D.Mery
11
Arquitectura de Computadores
Präsentat
ion
[ Aumento de desempeño ]
RISC
RISC:
reduced (or regular) instruction set computer
es una forma de diseñar CPU que contiene un conjunto de
instrucciones muy simple y que casi todas las instrucciones
toman el mismo tiempo de ejecución. Muchos procesadores
modernos son RISC (ejemplos: SPARC, MIPS y PowerPC). Sin
embargo, los CPU más utilizados como los x86 son CISC.
RISC nace después de CISC!!!
D.Mery
12
Arquitectura de Computadores
Präsentat
ion
[ Aumento de desempeño ]
RISC
¿Cómo resolver el problema del tiempo consumido a las llamadas
de procedimiento?
¿Cómo resolver el problema del tiempo tan grande que se
consume en direccionar operandos escalares?
¿Cómo aprovechar la característica de las llamadas a
procedimiento con poca profundidad?
D.Mery
13
Arquitectura de Computadores
Präsentat
ion
[ Aumento de desempeño ]
RISC
¿Cómo resolver el problema del tiempo consumido a las llamadas
de procedimiento?
¿Cómo resolver el problema del tiempo tan grande que se
consume en direccionar operandos escalares?
¿Cómo aprovechar la característica de las llamadas a
procedimiento con poca profundidad?
La solución está en el uso de muchos registros, y
en su organización en ventanas de registros
solapadas!
D.Mery
14
Arquitectura de Computadores
Präsentat
ion
[ Aumento de desempeño ]
RISC
Ventanas de registros solapadas
D.Mery
15
Arquitectura de Computadores
Präsentat
ion
[ Aumento de desempeño ]
RISC
Ventanas de registros
solapadas
Organización de las
ventanas solapadas como
un buffer circular
D.Mery
16
Arquitectura de Computadores
Präsentat
ion
[ Aumento de desempeño ]
RISC
El uso optimizado de los registros es problema del
compilador
Ejemplo: ¿cómo organizar los registros?
t
D.Mery
17
Arquitectura de Computadores
Präsentat
ion
[ Aumento de desempeño ]
RISC
El uso optimizado de los registros es problema del
compilador
Ejemplo: ¿cómo organizar los registros?
A
F
D
t
D.Mery
A, B y C deben estar
cargados
simultáneamente.
Cada registro (virtual) es un
nodo, cada interferencia es un
arco entre nodos.
18
Arquitectura de Computadores
Präsentat
ion
[ Aumento de desempeño ]
RISC
El uso optimizado de los registros es problema del
compilador
Ejemplo: ¿cómo organizar los registros?
Grafo de 4
colores
F
R1 R2
t
D.Mery
R3
R4
El grafo se colorea de tal forma
que dos nodos conectados no
tengan el mismo color.
19
Arquitectura de Computadores
Präsentat
ion
[ Aumento de desempeño ]
RISC
¿Por qué entonces CISC?
El CISC ha sido motivado por dos razones:
1. El deseo de simplificar los compiladores, la idea es que
las instrucciones de la CPU se asemejen a las
instrucciones de los HLL.
2. Aumentar el desempeño de las CPU produciendo
programas más pequeños y más rápidos.
D.Mery
20
Arquitectura de Computadores
Präsentat
ion
[ Aumento de desempeño ]
RISC
¿Por qué entonces CISC?
El CISC ha sido motivado por dos razones:
1. El deseo de simplificar los compiladores, la idea es que
las instrucciones de la CPU se asemejen a las
instrucciones de los HLL.
SIN EMBARGO, la tarea de encontrar justo la instrucción en
un conjunto muy grande de instrucciones es una tarea
compleja, muchas veces los compiladores terminan
usando las instrucciones sencillas.
D.Mery
21
Arquitectura de Computadores
Präsentat
ion
[ Aumento de desempeño ]
RISC
¿Por qué entonces CISC?
El CISC ha sido motivado por dos razones:
2. Aumentar el desempeño de las CPU produciendo
programas más pequeños y más rápidos.
SIN EMBARGO, con CISC se disminuye el número de
instrucciones no el número de bytes del código máquina,
la decodificación de instrucciones más grandes no es
necesariamente más rápida que la decodificación de
instrucciones pequeñas. Las velocidades entre CISC y
RISC son comparables.
D.Mery
22
Arquitectura de Computadores
Präsentat
ion
[ Aumento de desempeño ]
RISC
Características típicas de RISC:
1. Una instrucción por ciclo
2. Operaciones registro a registro
3. Modos de direccionamiento sencillos
4. Formatos de instrucción sencillos
D.Mery
23
Arquitectura de Computadores
Präsentat
ion
[ Aumento de desempeño ]
RISC
RISC vs. CISC:
El desarrollo de RISC representa una ruptura con la filosofía
que detrás de esta tendencia.
Los que están a favor de RISC han hecho estudios que
determinan que RISC tiene mejor desempeño.
RISC y CISC son claramente dos tendencias, es difícil
determinar cuál de los dos es mejor porque
•
•
•
No existe una pareja de máquinas CISC y RISC que sean
comparables
No existe un conjunto de programas definitivos
Es difícil separar las habilidades del hardware de las
habilidades del compilador
Hoy ambas tendencias usan mezclas de ambas tecnologías!
D.Mery
24
Arquitectura de Computadores
Präsentat
ion
[ Índice ]
8.1 Arquitectura RISC
8.2 Predicción de salto y prefetching
8.3 Escalabilidad
D.Mery
25
Arquitectura de Computadores
Präsentat
ion
[ Aumento de desempeño ] Predicción de salto
Fetch
(captación)
Decodificador
Ejecución
Memoria
Escritura
Pipeline típico
D.Mery
26
Arquitectura de Computadores
Präsentat
ion
[ Aumento de desempeño ] Predicción de salto
D.Mery
LOAD A,01h
#I1
LOAD C,02h
#I2
LOAD D,03h
#I3
LOAD B,04h
#I4
HALT
#I5
1
2
3
4
5
F
D
E
M
W
F
D
E
M
W
F
D
E
M
W
F
D
E
M
W
F
D
E
M
27
6
7
8
9
W
Arquitectura de Computadores
Präsentat
ion
[ Aumento de desempeño ] Predicción de salto
if (j==2)
m = 1;
else
m = 2;
CMP A,2
BNE else
then MOV B,1
BR next
else MOV B,2
next ...
;compara j con 2
;salta a else si
no es igual
;carga 1 en B
;salta a next
;carga 2 en B
Programa original
Programa en Assembler
D.Mery
28
Arquitectura de Computadores
Präsentat
ion
[ Aumento de desempeño ] Predicción de salto
if (j==2)
m = 1;
else
m = 2;
n = 1;
CMP A,2
BNE else
then MOV B,1
BR next
else MOV B,2
next MOV C,1
;compara j con 2
;salta a else si
no es igual
;carga 1 en B
;salta a next
;carga 2 en B
;carga 1 en C
Programa original
Programa en Assembler
En este ejemplo (con ramificaciones) se introducen al pipeline
instrucciones que no se van a ejecutar!
D.Mery
29
Arquitectura de Computadores
Präsentat
ion
[ Aumento de desempeño ] Predicción de salto
La solución radica en introducir al pipeline sólo las instrucciones válidas…
¿pero es esto posible?
¿Qué pasa con los saltos incondicionales?
Pareciera que con el salto incondicional no habría problema, la CPU
debiera seguir leyendo instrucciones a partir de la dirección objetivo (el
lugar a donde se saltará), pero ¿cómo saber esta dirección a tiempo?
CMP A,2
BNE else
then MOV B,1
BR next
else MOV B,2
next MOV C,1
:
D.Mery
?
30
1
2
3
4
5
6
7
8
F
D
E
M
W
F
D
E
M
W
F
D
E
M
W
F
D
E
M
W
F
D
E
M
9
W
Arquitectura de Computadores
Präsentat
ion
[ Aumento de desempeño ] Predicción de salto
La solución radica en introducir al pipeline sólo las instrucciones válidas…
¿pero es esto posible?
¿Qué pasa con los saltos incondicionales?
Pareciera que con el salto incondicional no habría problema, la CPU
debiera seguir leyendo instrucciones a partir de la dirección objetivo (el
lugar a donde se saltará), pero ¿cómo saber esta dirección a tiempo?
CMP A,2
1
2
BNE else
F
D
then MOV B,1
F
BR next
else MOV B,2
?
next MOV C,1
Esto no es posible
:
3
4
5
6
7
8
E
M
W
D
E
M
W
F
D
E
M
W
F
D
E
M
W
F
D
E
M
9
W
Porque ya se “coló” MOV B,2
D.Mery
31
Arquitectura de Computadores
Präsentat
ion
[ Aumento de desempeño ] Predicción de salto
La solución radica en introducir al pipeline sólo las instrucciones válidas…
¿pero es esto posible?
¿Qué pasa con los saltos incondicionales?
Pareciera que con el salto incondicional no habría problema, la CPU
debiera seguir leyendo instrucciones a partir de la dirección objetivo (el
lugar a donde se saltará), pero ¿cómo saber esta dirección a tiempo?
CMP A,2
1
2
3
4
5
BNE else
F
D
E
M W
then MOV B,1
F
D
E
M
BR next
F
D
E
NOP
F
D
!
else MOV B,2
F
Esto
sí
es
posible
next MOV C,1
pero hace el programa + lento y + grande
:
D.Mery
32
6
7
8
9
W
M
W
E
M
W
D
E
M
W
Arquitectura de Computadores
Präsentat
ion
[ Aumento de desempeño ] Predicción de salto
Address
100
101
102
103
104
105
106
D.Mery
Normal
LOAD X,A
ADD 1,A
JUMP 105
ADD A,B
SUB C,B
STORE A,Z
Delayed
LOAD X,A
ADD 1,A
JUMP 105
NOOP
ADD A,B
SUB C,B
STORE A,Z
33
Optimized
LOAD X,A
JUMP 105
ADD 1,A
ADD A,B
SUB C,B
STORE A,Z
Arquitectura de Computadores
Präsentat
ion
[ Aumento de desempeño ] Predicción de salto
La solución radica en introducir al pipeline sólo las instrucciones válidas…
¿pero es esto posible?
¿Qué pasa con los saltos condicionales?
La situación es peor porque no se sabe adónde saltar sino después de
ejecutar la instrucción y saber si la condición se cumple o no!
1
D.Mery
2
F
D
CMP A,2
F
BNE else
then MOV B,1
BR next
NOP
?
else MOV B,2 Cuál de las dos
next MOV C,1
34
:
3
4
5
6
7
8
E
M
W
D
E
M
W
F
D
E
M
W
F
D
E
M
W
F
D
E
M
9
W
Arquitectura de Computadores
Präsentat
ion
[ Aumento de desempeño ] Predicción de salto
Las primeras versiones de las CPUs se detenían ante un salto condicional
hasta no saber adónde saltar, esto a veces toma tres o cuatro ciclos. Esto
arruina el desempeño de la CPU ya que más del 20% de las instrucciones
son ramificaciones.
La solución es la “predicción del salto”, con esta solución se predice si se
va a tomar el salto o no.
D.Mery
35
Arquitectura de Computadores
Präsentat
ion
[ Aumento de desempeño ] Predicción de salto
Idea de la predicción:
Predecir la dirección de la ramificación
Ejecutarla como si fuera correcta
Aceptar o descartar los resultados después de saber la
dirección de la bifurcación correcta
D.Mery
36
Arquitectura de Computadores
Präsentat
ion
[ Aumento de desempeño ] Predicción de salto
Si se predice correctamente una rama, no hay nada especial que hacer (la
ejecución simplemente continúa en la dirección objetivo).
PERO el problema surge cuando se predice erróneamente una rama.
Averiguar a dónde hay que ir e ir ahí no es difícil… la parte difícil es anular
instrucciones que ya se ejecutaron y no debieron haberse ejecutado.
Solución: uso de “registro borrador” intermedio.
D.Mery
37
Arquitectura de Computadores
Präsentat
ion
[ Aumento de desempeño ] Predicción de salto
Una estrategia simple para predecir el salto:
“Se tomarán todas las ramificaciones condicionales hacia atrás y no se
tomará ninguna ramificación condicional hacia delante”
¿Es buena esta estrategia? ¿por qué?
D.Mery
38
Arquitectura de Computadores
Präsentat
ion
[ Aumento de desempeño ] Predicción de salto
PREDICCIÓN DINÁMICA:
Se usa una tabla histórica (hardware) de consulta en la que se escribe
cómo fue la última vez que se ejecutó la instrucción de ramificación
condicional (¿se tomó la ramificación o no se tomó?)
D.Mery
39
Arquitectura de Computadores
Präsentat
ion
[ Aumento de desempeño ] Predicción de salto
ESTRATEGIA 1 DE PREDICCIÓN DINÁMICA:
La ramificación tomará la misma trayectoria que adoptó la vez anterior. En
este caso sólo es necesario almacenar un bit por instrucción de
ramificación condicional presente en el programa.
¿Problemas?
D.Mery
40
Arquitectura de Computadores
Präsentat
ion
[ Aumento de desempeño ] Predicción de salto
ESTRATEGIA 2 DE PREDICCIÓN DINÁMICA:
Se da una segunda oportunidad, es decir la predicción sólo se cambia
después de dos predicciones incorrectas consecutivas. En este caso es
necesario almacenar dos bits por instrucción de ramificación condicional
presente en el programa.
D.Mery
41
Arquitectura de Computadores
Präsentat
ion
[ Aumento de desempeño ] Predicción de salto
ESTRATEGIA 3 DE PREDICCIÓN DINÁMICA:
Muchas veces la dirección de salto es calculada en la instrucción por lo
tanto en esta estrategia se guarda no sólo se escribe cómo fue la última
ramificación, se guarda también la dirección del salto.
D.Mery
42
Arquitectura de Computadores
Präsentat
ion
[ Aumento de desempeño ] Predicción de salto
PREDICCIÓN ESTÁTICA:
Las predicciones dinámicas se definen sobre la marcha de la ejecución del
programa. Esto requiere de hardware especializado y costoso.
Las predicciones estáticas se definen a nivel de compilación
Ejemplo: ¿cómo podría ayudar el compilador con este código?
for (i=0;i<1000000;i++) {. . .}
D.Mery
43
Arquitectura de Computadores
Präsentat
ion
[ Aumento de desempeño ] Predicción de salto
PREDICCIÓN ESTÁTICA 1:
Algunas CPU poseen instrucciones especiales de ramificación (además de
las normales) que contienen un bit en el que el compilador puede
especificar que cree que la rama se tomará (o no se tomará)
D.Mery
44
Arquitectura de Computadores
Präsentat
ion
[ Aumento de desempeño ] Predicción de salto
PREDICCIÓN ESTÁTICA 2:
Una vez compilado el programa se ejecuta de forma simulada y se estudia
el comportamiento de las ramificaciones, de esta forma en la versión final
del programa se incorporan las predicciones de ramificación realizadas a
partir de este estudio. En esta modalidad también se usan las
instrucciones de ramificación especial.
D.Mery
45
Arquitectura de Computadores
Präsentat
ion
[ Índice ]
8.1 Arquitectura RISC
8.2 Predicción de salto y prefetching
8.3 Escalabilidad
D.Mery
46
Arquitectura de Computadores
Präsentat
ion
[ Aumento de desempeño ]
Escalabilidad
• Parámetros importantes:
– Rendimiento (throughput): Número de operaciones por
unidad de tiempo.
– Tiempo de respuesta (response time): Tiempo desde que
inicia un cómputo hasta que termina.
– Fiabilidad (reliability): Fiabilidad del sistema con respecto a
la fiabilidad de los componentes.
D.Mery
47
Arquitectura de Computadores
Präsentat
ion
[ Aumento de desempeño ]
Escalabilidad
• Un sistema computacional es escalable si su capacidad de
procesamiento puede crecer añadiendo nodos adicionales:
– Aumenta el rendimiento con un número creciente de
nodos (idealmente de forma lineal).
– El tiempo de respuesta decrece (o se mantiene cte. o
crece lentamente) con un número creciente de nodos.
– La fiabilidad el sistema aumenta con número creciente de
CPUs (idealmente de forma logarítmica).
D.Mery
48
Arquitectura de Computadores
Präsentat
ion
Descargar

Kein Folientitel