Muchas aplicaciones son dominadas por el uso de la memoria
El desempeño de la memoria no es uniforme
La memoria cache y virtual afectan en gran medida el desempeño de un programa
Adaptar los programas a las características de los sistemas de memoria puede llevar a mejorar la velocidad de ejecución del programa.
Error de referencia a memoria
La versión de Linux da un resultado correcto, pero implementando el programa como una función separada da una falla de segmentación.
main ()
{
long int a[2];
double d = 3.14;
a[2] = 1073741824; /* Out of bounds reference */
printf("d = %.15g\n", d);
exit(0);
}
A
lph
a
M
I
PS
Linux
-g
5.30498947741318e-315
3.1399998664856
3.14
-O
3.14
3.14
3.14
Errores de referencia a memoria
C y C++ no tienen protección a memoria
Las referencias a arreglos pueden estar fuera del límite
Se pueden generar valores de apuntadores inválidos
Se pueden dar abusos de las funciones de manejo de la memoria malloc/free
Se pueden generar errores graves
Los errores pueden tener o no pueden tener efectos que dependen del sistema y el compilador
Acción a distancia
Objetos lógicos corrompidos sin relación con uno que esta siendo accedido
El efecto de los errores pueden ser observados mucho después de ser generados
¿Cómo se puede superar esto?
Programar en Java, Lisp, o ML (Meta-Lenguaje)
Entender las posibles interacciones que pueden ocurrir
Utilizar o desarrollar herramientas que detecten referencias a errores
Depuradores
Errores de desempeño de memoria
Implementación de multiplicación de matrices
Múltiples formas de anillos anidados
/* ijk */
for (i=0; i
for (j=0; j
sum = 0.0;
for (k=0; k
sum += a[i][k] * b[k][j];
c[i][j] = sum;
}
}
/* jik */
for (j=0; j
for (i=0; i
sum = 0.0;
for (k=0; k
sum += a[i][k] * b[k][j];
c[i][j] = sum
}
}
Multiplicación de Matrices 1
Para calcular cada elemento de C se requiere la sumatoria del los productos de cada elemento de la columna (indexado por i, k) de A y cada elemento del renglón (indexada por k, j) de B . El resultado se guarda en la columna (indexada por i,j) de C
Columna(i, k) X Renglón(j, k) = Columna(i, j)
/* ijk */
for (i=0; i
for (j=0; j
sum = 0.0;
for (k=0; k
sum += a[i][k] * b[k][j];
c[i][j] = sum;
}
}
B
A
C
k
k
j
i
j
i
Nota: Por cada acceso a un elemento de columna salta n datos
Multiplicación de Matrices 2
B
A
C
i
j
j
/* jik */
for (j=0; j
for (i=0; i
sum = 0.0;
for (k=0; k
sum += a[i][k] * b[k][j];
c[i][j] = sum
}
}
k
k
i
Para calcular cada elemento de C se requiere la sumatoria de los productos de cada elemento del renglón (indexada por i, k) de A y cada elemento de la columna (indexado por k, j) de B. El resultado se guarda en el renglón C (indexada por i,j)
Renglón(i, k) X Columna(k, j) = Renglón(i, j)
Nota: Los datos de un elemento de renglón son contiguos
Mult. mat. (Alpha 21164)
0
20
40
60
80
100
120
140
160
matrix size (n)
ijk
ikj
jik
jki
kij
kji
Demasiado grande para Cache L1
Demasiado grande para Cache L2
50
75
100
150
200
250
300
350
400
450
500
Mem bloqueante
0
20
40
60
80
100
120
140
160
50
75
100
125
150
175
200
225
250
275
300
325
350
375
400
425
450
475
500
matrix size (n)
bijk
bikj
ijk
ikj
Realidad importante # 4
Hay más que mejorar que la “Complejidad asintótica”
Cuando el tamaño de la entrada es lo suficientemente grande que solo el orden de crecimiento del tiempo de ejecucion es importante.
Los factores constantes también importan:
Se puede ver un rango de desempeño 10:1 dependiendo en la forma en que el código es escrito.
Se puede optimizar a múltiples niveles: algoritmos, representación de datos, procedimientos y anillos.
Se debe de entender el sistema para mejorar el desempeño:
Hay que saber cómo son compilados y ejecutados los programas
Hay que saber cómo medir el desempeño de un programa e identificar los cuellos de botella.
Hay que saber cómo mejorar el desempeño sin destruir la modularidad y generalidad del código.
Realidad importante # 5
Las computadoras hacen mas que ejecutar programas…
Ellas necesitan obtener datos de entrada y generar datos de salida
La entrada/salida de un sistema es un factor crítico de los programas para la confianza y desempeño
Las direcciones de una memoria especifican localizaciones de Bytes
Se da la dirección del primer byte en la palabra
Las direcciones de palabras sucesivas difieren en 4 bytes (32 bits) u 8 bytes (64 bits)
Orientada a palabras
0000
0001
0002
0003
0004
0005
0006
0007
0008
0009
0010
0011
32-bit
Words
Bytes
Addr.
0012
0013
0014
0015
64-bit
Words
Addr
=
??
Addr
=
??
Addr
=
??
Addr
=
??
Addr
=
??
Addr
=
??
0000
0004
0008
0012
0000
0008
Abstracción
Un modelo que oculta detalles de bajo nivel de un sistema de computadora temporalmente invisible para facilitar el diseño de un sistema sofisticado.
Wikipedia: La abstracción, es un principio por el cual se aísla toda aquella información que no resulta relevante a un determinado nivel de conocimiento.
La abstracción consiste en aislar un elemento de su contexto o del resto de los elementos que lo acompañan. En programación, el término se refiere al énfasis en el "¿qué hace?" más que en el "¿cómo lo hace?" (característica de caja negra). El común denominador en la evolución de los lenguajes de programación, desde los clásicos o imperativos hasta los orientados a objetos, ha sido el nivel de abstracción del que cada uno de ellos hace uso.
Los lenguajes de programación son las herramientas mediante las cuales los diseñadores de lenguajes pueden implementar los modelos abstractos. La abstracción ofrecida por los lenguajes de programación se puede dividir en dos categorías: abstracción de datos (pertenecientes a los datos) y abstracción de control (perteneciente a las estructuras de control).