Microtecnolgía y Arquitecturas de Computadoras Abstracciones



Descargar 39,91 Kb.
Fecha de conversión08.06.2017
Tamaño39,91 Kb.

Objetivo

  • Se analizarán aspectos de Microarquitectura, Sistemas operativos y compiladores

Realidad importante # 1

  • Los números enteros (int) no son enteros, los números de punto flotante (float) no son reales, por ejemplo:
  • ¿Es X2  0?
    • Con float: ¡Si!
    • Con int: ¡??!
    • 04000*04000 0016,000,000 = 0X000F42400 = 0000-0000-1111-0100-0010-0100-0000-0000
    • 90000*90000  8,100,000,000 = 0X1E2CC3100 = 0001-1110-0010-1100-1100-0011-0001-0000-0000 ¿?
  • ¿Es (x + y) + z = x + (y + z)?
    • Con signed int & unsigned int: ¡Si!
    • Con float: ¡??!
      • (1e20 + -1e20) + 3.14  3.14
      • 1e20 + (-1e20 + 3.14)  ¿?
  • Los procesadores tienen una representación finita de los números !!!

Aritmética computacional

  • No debe generar valores aleatorios:
    • Las operaciones aritméticas tienen propiedades matemáticas importantes
  • No se puede asumir propiedades “usuales”:
    • Debido a la exactitud de las representaciones (Registros)
    • Las operaciones con enteros satisfacen las propiedades de un “anillo”
      • Conmutatividad, asociatividad y distributividad
    • Las operaciones de punto flotante satisfacen las propiedades de “orden”
      • Monotonicidad (conservan el orden), valores de signo
        • f es monótona para toda x
  • Observaciones:
    • Se necesita entender que abstracciones aplicar dependiendo del contexto.
    • Es un tema importante para programadores de compiladores y programadores de aplicaciones serias

Realidad importante # 2

  • ¿Se tiene que saber ensamblador?
  • En general, las oportunidades de nunca escribir un programa en ensamblador son grandes:
    • Los compiladores son mucho mejores y más pacientes de lo que son las personas.
  • Sin embargo, entender el lenguaje ensamblador es clave para ejecutar modelos a nivel máquina:
    • Para entender el comportamiento de programas en presencia de errores
      • Se analiza el Modelo de lenguaje de alto nivel
    • Para ajustar en desempeño del programa
      • Entender las fuentes de ineficiencia del programa
    • Implementando software de sistemas
      • Los compiladores tiene código máquina como objetivo
      • Los sistemas operativos deben administrar el estado del proceso

Ejemplo de código ensamblador

  • Contador
    • MSR es un registro de 64 bits especial en máquinas compatibles con procesador Intel
    • Se incrementa cada ciclo de reloj
    • Se lee con la instrucción rdtsc
  • Aplicación
    • Medir el tiempo requerido para un procedimiento P()
      • En unidades de ciclos de reloj
    • double t;
    • start_counter();
    • P();
    • t = get_counter();
    • printf("P required %f clock cycles\n", t);

Ejemplo de Código Intel X-86

  • RDTSC : Read Time-Stamp Counter into EDX:EAX
    • Carga el valor del contador MSR (64-bits)en EDX:EAX
    • Introducida con el procesador Pentium

Código para leer el contador

  • Escribe pequeñas cantidades de código ensamblador utilizando las opciones asm de GCC.
  • Inserta código ensamblador en código máquina generado por el compilador.
  • static unsigned cyc_hi = 0;
  • static unsigned cyc_lo = 0;
  • /* Set *hi and *lo to the high and low order bits
  • of the cycle counter.
  • */
  • void access_counter(unsigned *hi, unsigned *lo)
  • {
  • asm(“rdtsc; movl %%edx,%0; movl %%eax,%1
  • :"=r”(*hi), "=r" (*lo)
  • :
  • :"%edx“ , "%eax“
  • );
  • }

Código para leer el contador

  • /* Record the current value of the cycle counter. */
  • void start_counter()
  • {
  • access_counter(&cyc_hi, &cyc_lo);
  • }
  • /* Number of cycles since the last call to start_counter. */
  • double get_counter()
  • {
  • unsigned ncyc_hi, ncyc_lo;
  • unsigned hi, lo, borrow;
  • /* Get cycle counter */
  • access_counter(&ncyc_hi, &ncyc_lo);
  • /* Do double precision subtraction */
  • lo = ncyc_lo - cyc_lo;
  • borrow = lo > ncyc_lo;
  • hi = ncyc_hi - cyc_hi - borrow;
  • return (double) hi * (1 << 30) * 4 + lo;
  • }

Midiendo el tiempo

  • Es más engañoso de lo que parece
    • Existen muchas fuentes de variaciones
  • Ejemplo del procedimiento P()
    • Suma de enteros de 1 a n
      • n Ciclos Ciclos/n
      • 100 961 9.61
      • 1,000 8,407 8.41
      • 1,000 8,426 8.43
      • 10,000 82,861 8.29
      • 10,000 82,876 8.29
      • 1,000,000 8,419,907 8.42
      • 1,000,000 8,425,181 8.43
      • 1,000,000,000 8,371,2305,591 8.37

Realidad importante # 3

  • La memoria si importa
  • La memoria no es infinita
    • Debe de ser asignada y administrada
    • 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

  • 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
  • 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.5213104 se representa como 1.11011011011012213
  • 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
    • Múltiples mecanismos: estáticos, pila (stack), monticulo (heap)
    • En cualquier caso, todos los destinos están dentro de un espacio de direcciones virtuales

Codificación de valores de bytes

  • Byte = 8 bits
  • Binario 000000002 a 111111112
  • Decimal 010 a 25510
  • Hexadecimal 0016 a FF16
    • Representación numérica base 16
    • Utiliza los caracteres ‘0’ a ‘9’ y ‘A’ a ‘F’
    • Ej. Se escribe FA1D37B16 en C como 0xFA1D37B ó 0xfa1d37b
  • 0
  • 0
  • 0000
  • 1
  • 1
  • 0001
  • 2
  • 2
  • 0010
  • 3
  • 3
  • 0011
  • 4
  • 4
  • 0100
  • 5
  • 5
  • 0101
  • 6
  • 6
  • 0110
  • 7
  • 7
  • 0111
  • 8
  • 8
  • 1000
  • 9
  • 9
  • 1001
  • A
  • 10
  • 1010
  • B
  • 11
  • 1011
  • C
  • 12
  • 1100
  • D
  • 13
  • 1101
  • E
  • 14
  • 1110
  • F
  • 15
  • 1111
  • Hex
  • Decimal
  • Binario
  • Representación Numérica
  • Ejemplo

Palabras de las máquinas

  • Las máquinas tienen un “tamaño de palabra”
    • Tamaño nominal de datos con valores enteros
      • Incluyendo direcciones
    • La mayoría de las máquinas son de 32 bits (4 bytes)
      • Su direccionamiento se limita a 4 GB
      • Siendo muy lentas para aplicaciones de memoria intensiva
    • Sistemas más sofisticados son de 64 bits (8 bytes)
      • Pueden potencialmente direccionar  1.8  1019 Bytes
        • 18 PB=18,000 TB, 18’000,000 GB
    • Las máquinas soportan múltiples formatos de datos

Organización de la memoria

  • 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).
  • 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
  • 8048365: 5b pop %ebx
  • 8048366: 81 c3 ab 12 00 00 add $0x12ab,%ebx
  • 804836c: 83 bb 28 00 00 00 00 cmpl $0x0,0x28(%ebx)
  • Descifrando números
    • Valor: 0x12ab
    • Grupo de 4 bytes: 0x000012ab
    • Separado en bytes: 00 00 12 ab
    • Reversa: ab 12 00 00
  • reversa

Examinando

  • Código para imprimir la representación de datos
    • El apuntador a unsigned char * crea un arreglo byte
    • typedef unsigned char *apuntador;
    • void muestra_bytes(apuntador comienzo, int longitud)
    • {
    • int i;
    • for (i=0; i < longitud; i++)
    • printf(“0x%p\t0x%.2x\n”, comienzo+i, comienzo[i]);
    • printf(“\n”);
    • }
    • Directivas Printf: %p: Imprime apuntador
    • %x: Imprime hexadecimal
  • la representación de datos

Ejecución del ejemplo

  • int a = 15213;
  • printf(“int a = 15213;\n);
  • muestra_bytes((apuntador) &a ,sizeof(int));
  • Resultado (en Linux):
  • int a = 15213;
  • 0x11ffffcb8 0x6d
  • 0x11ffffcb9 0x3b
  • 0x11ffffcba 0x00
  • 0x11ffffcbb 0x00
  • muestra_bytes

Representando enteros

  • int A = 15213; Decimal: 15213
  • int B = -15213; Binario: 0011 1011 0110 1101
  • long int C = 15213; Hex: 3 B 6 D
  • Representación complemento a 2’s.
  • 00
  • 00
  • 00
  • 00
  • 6D
  • 3B
  • 00
  • 00
  • Alpha C
  • 3B
  • 6D
  • 00
  • 00
  • Sun C
  • 6D
  • 3B
  • 00
  • 00
  • Linux C
  • 6D
  • 3B
  • 00
  • 00
  • Linux/Alpha A
  • 3B
  • 6D
  • 00
  • 00
  • Sun A
  • 93
  • C4
  • FF
  • FF
  • Linux/Alpha B
  • C4
  • 93
  • FF
  • FF
  • Sun B

Representando apuntadores

  • int B = -15213;
  • int *p = &B;
  • Dirección en la Alpha
  • Hex: 1 F F F F F C A 0
  • Binario: 0001 1111 1111 1111 1111 1111 1100 1010 0000
  • Dirección en la Sun
  • Hex: E F F F F B 2 C
  • Binario: 1110 1111 1111 1111 1111 1011 0010 1100
  • Dirección en Linux
  • Hex: B F F F F 8 D 4
  • Binario: 1011 1111 1111 1111 1111 1000 1101 0100
  • Diferentes compiladores y máquinas asignan diferentes localidades a los objetos
  • FB
  • 2C
  • EF
  • FF
  • Sun P
  • 01
  • 00
  • 00
  • 00
  • A0
  • FC
  • FF
  • FF
  • Alpha P
  • FF
  • BF
  • D4
  • F8
  • Linux P

Representando números

  • Flotante F = 15213.0
  • IEEE Representación en punto flotante de precisión simple
  • Hex: 4 6 6 D B 4 0 0
  • Binario: 0100 0110 0110 1101 1011 0100 0000 0000
  • 15213: 1110 1101 1011 01
  • No es como la representación de enteros, pero es consistente entre diferentes máquinas.
  • Se puede ver alguna relación en la representación a enteros, ¡¡¡pero no es obvio!!!.
  • 00
  • B4
  • 6D
  • 46
  • Linux/Alpha F
  • B4
  • 00
  • 46
  • 6D
  • Sun F
  • Punto flotante

Representando cadenas

  • Cadenas en C
    • Representadas por arreglos de caracteres
    • Cada caracter se codifica en un formato ASCII
      • Codificación en un estándar de 7 bits del conjunto del caracteres
      • Existen otras codificaciones, pero no son comunes
      • El caracter cero “0” tiene el código 0x30
        • Dígito i tiene el código 0x30 + i
    • La cadena debe de terminar con un caracter nulo
      • Carácter final = 0
  • Compatibilidad
    • El ordenamiento de bytes no es importante
      • Los datos son cantidades de bytes simples
    • Los archivos de texto son independientes de la plataforma
      • Excepto por diferentes convenios de terminación de líneas de caracteres
  • Caracteres

Ejemplo

  • char S[6] =“15213”
  • Linux/Alpha S
  • Sun S
  • 32
  • 31
  • 31
  • 35
  • 33
  • 00
  • 32
  • 31
  • 31
  • 35
  • 33
  • 00
  • Se codifica un programa como una secuencia de instrucciones
    • Cada operación simple
    • Instrucciones codificadas como bytes
      • Las Alpha’s, Sun’s y Mac’s utilizan instrucciones de 4 bytes
        • Computadoras con Conjunto de Instrucciones Reducidas (RISC)
      • Las PC’s utilizan instrucciones de longitud variable
        • Computadoras con Conjunto de Instrucciones Complejas (CISC)
    • Diferentes tipos de instrucciones como bytes
      • La mayoría del código binario no es compatible
  • Los programas son también secuencias de bytes
  • Representación de código
  • a nivel máquina

Representación de instrucciones

  • int sum (int x, int y)
  • {
  • return x + y;
  • }
  • Para este ejemplo, las Alpha’s
  • y las Sun’s utilizan dos instrucciones de 4 bytes
  • Utilizan diferentes números de instrucciones
  • en otros casos.
  • Las PC’s (Intel) utilizan 7 instrucciones
  • con longitudes de 1, 2, y 3 bytes
  • Lo mismo para NT y Linux
  • (NT/Linux no son compatibles)
  • en código binario completamente
  • Diferentes máquinas utilizan instrucciones y codificaciones totalmente diferentes
  • 00
  • 00
  • 30
  • 42
  • Alpha sum
  • 01
  • 80
  • FA
  • 6B
  • E0
  • 08
  • 81
  • C3
  • Sun sum
  • 90
  • 02
  • 00
  • 09
  • E5
  • 8B
  • 55
  • 89
  • PC sum
  • 45
  • 0C
  • 03
  • 45
  • 08
  • 89
  • EC
  • 5D
  • C3

Resumen

  • Todo en cómputo es acerca de Bits y Bytes
    • Números
    • Programas
    • Texto
  • Realidades
    • Representacion finita de los números
    • Factores constantes importantes (tamaño de la cache)
  • Diferentes máquinas siguen diferentes convenciones
    • Tamaño de palabra
    • Orden de los bytes
    • Representación de instrucciones
  • Cadenas de caracteres
    • Los archivos de texto son independientes de la plataforma


La base de datos está protegida por derechos de autor ©absta.info 2016
enviar mensaje

    Página principal