Rendimiento. Complejidad. Ecuación.
Ley de Amdhal
Complejidad
P1. (Fácil: 2 minutos) Un cierto programa P tiene complejidad O(n2). Cuando lo ejecutamos con un tamaño de
problema de n= 200, el tiempo de ejecución es 80 segundos. Calcular el tiempo de ejecución estimado con n= 600.
P2. (Fácil: 3 minutos) Un cierto programa P tiene los siguientes tiempos de ejecución, en función de un parámetro n,
que define el tamaño del problema. Estimar la complejidad del algoritmo:
T(n=100) = 40; T(n=200) = 92; T(n=400) = 208.
Ecuación de Rendimiento
P3.a. (Fácil: 5 minutos) Modificamos un cierto programa P aumentando el nº de instrucciones máquina ejecutadas
un 20%, e incrementando el IPC de 1,2 a 1,5. ¿Cuál es el speedup (mejora)?
P3.b. (Fácil: 5 minutos) Modificamos un cierto programa P aumentando el nº de instrucciones máquina ejecutadas
un 30%, e incrementando el IPC de 1,5 a 1,8. ¿Cuál es el speedup (mejora)?
P4.a (Fácil: 10 minutos) Un cierto programa P ejecuta 200 G instrucciones máquina con IPC=0,5. La frecuencia de
reloj del procesador es 2 GHz. Calcular: (a) el rendimiento de la ejecución del programa medida en programas P
ejecutados por hora, y (b) la mejora (speedup) respecto al caso (a) si se aumenta la frecuencia de reloj a 3 GHz, pero
a cambio IPC= 0,4.
P4.b (Fácil: 10 minutos) Un cierto programa P ejecuta 300 G instrucciones máquina con IPC=0,8. La frecuencia de
reloj del procesador es 2,5 GHz. Calcular: (a) el rendimiento de la ejecución del programa medida en programas P
ejecutados por hora, y (b) la mejora (speedup) respecto al caso (a) si se aumenta la frecuencia de reloj a 4 GHz, pero
a cambio IPC= 0,6.
Ley de Amdahl
P5. (Medio: 15 minutos) La ejecución de un programa P se compone de dos fases, la primera fase supone el 30%
del tiempo y la segunda fase supone el 70% del tiempo. Se modifica el código y se consigue reducir a la mitad la
cantidad de instrucciones ejecutadas en la fase 2, aunque, a cambio, el IPC de la ejecución de la fase 2 disminuye un
20%. ¿Calcula la relación de mejora total del programa?
Combinación
P6.a (Medio: 15 minutos) Un cierto programa P tiene complejidad O(n3). Cuando lo ejecutamos con un tamaño de
problema correspondiente a n= 20.000 se alcanza un rendimiento de 16 programas P ejecutados por hora y un número
de 2,5 instrucciones ejecutadas en promedio por ciclo de reloj. Al duplicar el valor de n, debido a un incremento de la
tasa de fallos en las memorias caché, el valor del IPC disminuye a 2,0. Calcular el tiempo de ejecución del programa
P, en segundos, para n= 40.000.
P6.b (Medio: 15 minutos) Un cierto programa P tiene complejidad O(n3). Cuando lo ejecutamos con un tamaño de
problema correspondiente a n= 10.000 el tiempo de ejecución es de 100 segundos y se logra un IPC de 2,0. Al
aumentar el valor de n a 15.000, debido a un incremento de la tasa de fallos en las memorias caché, el valor del IPC
disminuye a 1,25. Calcular el tiempo de ejecución del programa P, en segundos, para n= 15.000.
P6.c (Medio: 15 minutos) Tenemos un cierto programa compuesto por tres funciones A, B y C que tardan,
respectivamente, 400s, 350s y 250s (el tiempo total del programa es 1000s = 400s + 350s + 250s). Un programador
propone un cambio que reduce a la mitad el tiempo de ejecución de la función A. Otro programador propone un cambio
que supone una mejora (speedup) de 1,75 en la ejecución de la función B.
a) Si solo se aplica un cambio, ¿cuál proporciona mejor speedup global?
b) ¿Qué speedup se alcanzaría si se aplican los dos cambios?
c) ¿Qué mejora en el tiempo de ejecución de la función C sería necesario para conseguir un speedup global de
2, suponiendo que también se aplican los cambios de A y B?
Ejercicios Formativos Opcionales 1
Rendimiento. Complejidad. Ecuación. Ley de Amdhal
P7. (Medio: 20 minutos) Se compila el siguiente código en lenguaje C con el compilador gcc 9.2.0, opción –O2, para
un repertorio x86-64. También se compila para el repertorio RISC-V. El código ensamblador resultante de los dos
casos se muestra abajo, a la izquierda y a la derecha, respectivamente.
void F ( double *O, double *I, double *X, int N )
{
for (int j = 0; j < N; j++)
for (int i = 0; i < N; i++)
O[j] = O[j] + I[i]*X[j*N+i];
}
a. La ejecución del programa con N= 50 mil en un procesador basado en x86-64, y que funciona con una frecuencia
de reloj de 3 GHz, tarda 4 segundos. Calcular el IPC.
b. Si aumentamos el valor de N a 80 mil y el IPC se reduce a la mitad, ¿Cuál será el tiempo de ejecución del programa
en el mismo procesador de antes?
c. Para el caso N= 50 mil, calcular la mejora (speedup) del tiempo de ejecución que se produciría al ejecutar el
programa en un procesador basado en RISC-V, con una frecuencia de reloj de 1,2 GHz, y suponiendo que el IPC
es 1,8x mejor que el del caso (a).
P8. (Difícil: 30 minutos a 1 hora) Abajo se muestra el código en lenguaje Python/Cython de un cierto programa.
Abajo se muestra el resultado de varias ejecuciones de la función run() instrumentadas con el comando perf stat.
$ perf stat -e instructions,cycles python –c "import str as S; [Link](1,0)"
CheckSum = 0.0
365.528.978 instructions # 1,08 IPC
339.258.778 cycles
0,125288338 seconds time elapsed
$ perf stat -e instructions,cycles python –c "import str as S; [Link](8000000,0)"
CheckSum = -5097665.0
[Link] instructions # 2,26 IPC
[Link] cycles
2,791346202 seconds time elapsed
$ perf stat -e instructions,cycles python –c "import str as S; [Link](8000000,100)"
CheckSum = 4840114.0
[Link] instructions # 1,76 IPC
[Link] cycles
4,070280948 seconds time elapsed
Ejercicios Formativos Opcionales 2
Rendimiento. Complejidad. Ecuación. Ley de Amdhal
Finalmente, abajo se muestra el resultado del perfilado de la última de la ejecuciones de la función run(), con los
parámetros X= 8 millones, y T= 100.
$ perf record python –c "import str as S; [Link](8000000,100)"
$ perf report
Overhead Command Shared Object Symbol
31,31% python [Link] [.] __pyx_f_5str_evolve.isr
7,19% python python3.6 [.] _PyObject_GenericGetAttrW
5,99% python [Link] [.] __sin_avx
4,69% python [Link] [.] __pyx_f_5str_init.isra.
4,42% python [Link] [.] __cos_avx
Calcular una aproximación al tiempo total de ejecución y al número total de instrucciones máquina ejecutadas
de la función run(16.000.000, 400). Indicar de forma explícita las expresiones numéricas que dan lugar al resultado
(sin más explicaciones)
Fichero: [Link] (continúa el código de la izquierda)
import numpy as np
cdef float checkSUM ( float [::1] In,
import math,cython
int X ):
def run( int X, int T ): cdef float S= 0
cdef int t for x in range(1,X):
cdef float L= 0.345678 S = S + In[x]
cdef float [::1] U1, U2, Uout return S
U1 = [Link](X+1, dtype=np.float32)
U2 = [Link](X+1, dtype=np.float32) cdef evolve( float [::1] U1,
Uout=[Link](X+1, dtype=np.float32) float [::1] U2,
float [::1] Uout,
init ( U1, U2, X, T+1 ) int X, float L ):
for t in range(0,T): cdef int x
evolve( U1, U2, Uout, X, L ) cdef float L2 = 2.0*(1.0-L)
U1,U2,Uout = Uout,U1,U2 for x in range(1,X):
print("CheckSum= ",checkSUM(U1,X)) Uout[x] = L2*U1[x] +
L*(U1[x+1]+U1[x-1]) - U2[x]
cdef init ( float [::1] U1,
float [::1] U2, int X, int T ):
cdef int x
for x in range (1,X):
U2[x]= [Link](x * [Link] / X)
U1[x]= U2[x]*[Link]([Link]/T)
Ejercicios Formativos Opcionales 3
