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
Ellas se comunican con otras a través de las redes de computadora
Muchos temas a nivel-sistema surgen en presencia de redes
Operaciones concurrentes por medio de procesos autónomos
Copia en medios no confiables
Compatibilidad entre las plataformas
Temas de desempeño complejos
Base10
Es una numeración difícil de almacenar.
La ENIAC (primera computadora) utilizó 10 bulbos (tubo al vacío) por cada dígito.
Se necesita alta precisión para codificar señales de 10 niveles en un simple alambre o medio de comunicación de un solo canal.
Es difícil de implementar funciones lógicas digitales como son suma, multiplicación, entre otras.
Representación binaria
Representación numérica de base 2
1521310 se representa como 111011011011012
1.2010 se representa como 1.0011001100110011[0011]…2
1.5213104 se representa como 1.11011011011012213
Implementación electrónica
Fácil de almacenar con elementos bi-estables.
Disponibilidad de ser transmitida en medios ruidosos o inadecuados.
Implementación directa de funciones aritméticas.
0.0V
0.5V
2.8V
3.3V
0
1
0
Señal Eléctrica
Representación binaria
Organización de memoria orientada a bytes
Los programas hacen referencia a memoria virtual
Conceptualmente a arreglos muy grandes de bytes
Realmente son implementadas con jerarquías de memoria de diferentes tipos
SRAM, DRAM, discos
Sólo destinadas para regiones reales utilizadas por el programa
En Unix y Windows NT, el espacio de direcciones es privado a un “proceso” en particular
Al programa que está siendo ejecutado
El programa puede destruir sus propios datos pero no los de otros
Compilador + Tiempo de ejecución del sistema controlan el destino de la información (codigo/datos)
Donde diferentes objetos del programa podrían estar almacenados
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).
Abstacción
Representación de datos
Tipos de datos en C en un procesador (en bytes)
Tipo de dato en C
Compaq Alpha Típico de 32 bits Intel IA32
Int 4 4 4
long int 8 4 4
char 1 1 1
short 2 2 2
float 4 4 4
double 8 8 8
long double 8 8 10/12
char * 8 4 4
>> ó cualquier otro apuntador
Orden de los bytes
¿Cómo deben de ordenarse en memoria las palabras multi-bytes?
Convenciones:
Las PC’s y las Alphas son máquinas “Little Endian”
El byte menos significativos tienen las direcciones más bajas
Las Sun’s y las Mac’s son máquinas “Big Endian”
El byte menos significativo tiene la dirección más grande
La variable x tiene una representación de 4 bytes 0x01234567
La dirección &x está dada por 0x100
Big Endian
Little Endian
0x100
0x101
0x102
0x103
01
23
45
67
01
23
45
67
0x100
0x101
0x102
0x103
67
45
23
01
67
45
23
01
Ordenamiento de bytes
Ejemplo
Leyendo la lista de bytes
Desensamblado
Representación del texto de código máquina binario
Generado por el programa que lee el código máquina
Ejemplo del fragmento
Dirección Código de la instrucción Código ensamblado