Introducción

Presenter Notes

Resumen:

  • Introducción a Arquitectura de Computadoras.
  • De código fuente a ejecutable [clear.c](clear.c).

Nicolás Wolovick 20160308

Presenter Notes

Introducción

Presenter Notes

Memoria

La diferencia de derivada entre la velocidad de memoria y la CPU.

  • 1979, 8088, 3µm, 4.77 MHz, DRAM ~200ns.
  • 2015, Skylake (v6), 14 nm, 4.2 GHz, DRAM DDR4 <20ns.

Aliviar:

  • Cada parte de la memoria lo más rápido posible.
  • La memoria lenta accederla de manera circular.
  • La memoria lenta hacerla ancha.
  • Mezclar memoria lenta y rápida.

Presenter Notes

Tecnología

  • DRAM: capacitores.
  • SRAM: compuertas.

Diferencias sustanciales:

  • Capacidad.
  • Consumo.
  • Densidad.
  • Tiempos.

La gran idea:

Jerarquía de Memoria

Presenter Notes

Registros

  • Al tope de la jerarquía
  • SRAM, pegada al µP (va a la misma velocidad)
  • Muy poquitos.

Uso

Cómputo de (sub)expresiones.

1 REAL*4 G,A,W,M
2 X = G * 2.41 + A / W - W * M

Importante

No es lineal #regs y desempeño.

Presenter Notes

Cache

Para una DEC Alpha 21164. La esperanza de acceso a memoria para las siguientes probabilidades:

Jerarquía de memoria

  • L1: 0.9
  • L2: 0.07
  • L3: 0.02
  • Memoria: 0.01

0.9*4 + 0.07*5 + 0.02*30 + 0.01*220 = 6.75 ns

Presenter Notes

Organización de la Cache

Almacena celdas dispersas de la memoria.

cache lines

Granularidad: línea.
Dinámica: tener lo más frecuentemente usado.

Esto es lo mismo que explotar la

  • localidad espacial,
  • localidad temporal

del acceso a la memoria por parte de los programas.

Presenter Notes

Ejemplos

Lo ideal, accesos contiguos.

1 DO I=1,1000000
2     SUM = SUM + A(I)
3 END DO

Esto anda a la misma velocidad. Los saltos desaprovechan el ancho de banda.

1 DO I=1,1000000, 8
2     SUM = SUM + A(I)
3 END DO

Presenter Notes

Ejemplos

Un acceso lineal a memoria es común.

1 REAL*4 A(200,200)
2 DO J = 1,200
3     DO I = 1,200
4         SUM = SUM + A(I,J)
5     END DO
6 END DO

Pero también puede ser de a saltos!

1 REAL*4 A(200,200)
2 DO I = 1,200
3     DO J = 1,200
4         SUM = SUM + A(I,J)
5     END DO
6 END DO

Ayuda: Fortran es column-major, C es row-major.

Presenter Notes

Ejemplos

Algunas estructuras de datos no tienen localidad espacial (listas ligadas, árboles)

1 while (ptr) {
2     ptr = ptr->next;
3 }

Algunos problemas de tipo gather / scatter tampoco!

1 DO I=1,1000000
2     SUM = SUM + A(INDEX(I))
3 END DO

Presenter Notes

Organización

Esquema simple. Mapeo no inyectivo memoria -> cache. One-way set associative.

one-way set associative

Problema

1 REAL*4 A(1024), B(1024)
2 COMMON /STUFF/ A,B
3 DO I =1,1024
4     A(I) = A(I) * B(I)
5 END DO
6 END

Presenter Notes

Organización

Two-way set associative.

two-way set associative

Problema

1 REAL*4 A(1024), B(1024), C(1024)
2 COMMON /STUFF/ A,B,C
3 DO I =1,1024
4     A(I) = A(I) * B(I) + C(I)
5 END DO
6 END

Presenter Notes

Organización

  • Fully associative cache.
  • Carísimo: N comparadores en paralelo.
  • Algunas caché específicas o usan (TLB).

Caché de instrucciones y datos

  • División estándar en L1.
  • L2 y L3 son comunes.

Presenter Notes

Organización

 1 $ x86info --cache
 2 x86info v1.30.  Dave Jones 2001-2011
 3 Feedback to <davej@redhat.com>.
 4 
 5 Found 2 identical CPUs
 6 Extended Family: 0 Extended Model: 1 Family: 6 Model: 23 Stepping: 10
 7 Type: 0 (Original OEM)
 8 CPU Model (x86info's best guess): Core 2 Duo 
 9 Processor name string (BIOS programmed): Intel(R) Core(TM)2 Duo CPU     P8800  @ 2.66GHz
10 
11 Cache info
12  L1 Instruction cache: 32KB, 8-way associative. 64 byte line size.
13  L1 Data cache: 32KB, 8-way associative. 64 byte line size.
14  L2 cache: 3MB, 12-way associative. 64 byte line size. Unified on-die.
15  L2 cache: 3MB, 12-way associative. 64 byte line size.
16 TLB info
17  Instruction TLB: 4x 4MB page entries, or 8x 2MB pages entries, 4-way associative
18  Instruction TLB: 4K pages, 4-way associative, 128 entries.
19  Data TLB: 4MB pages, 4-way associative, 32 entries
20  L1 Data TLB: 4KB pages, 4-way set associative, 16 entries
21  L1 Data TLB: 4MB pages, 4-way set associative, 16 entries
22  Data TLB: 4K pages, 4-way associative, 256 entries.
23  64 byte prefetching.
24 Total processor threads: 2
25 This system has 1 dual-core processor running at an estimated 2.65GHz

Presenter Notes

Memoria Virtual

Mapeo arbitrario de un espacio de direcciones (virtual) a otro (físico).

virtual2physical

Pffff, dos accesos a tabla por acceso a memoria! Muy pesado, pero elegantísimo.

¿Para que?

  • Cada proceso tiene una memoria disjunta.
  • Puede mapear memoria en disco: swapfile.
  • Puede mapear archivos en memoria: mmap().

Presenter Notes

TLB (Translation Lookaside Buffer)

Caché para guardar el mapeo virtual->físico.

  • Granularidad: página de 4 KiB u 4 MiB.
  • Asociatividad: alta, de 4-way para arriba.
  • Tamaño: pequeñisimo! <1024 entradas.

Presenter Notes

Problema

Un programa raro, pero que produce muchos TLB miss (y también cache miss!).

1 REAL X(10000000)
2 COMMON X
3 DO I=0,9999
4     DO J =1,10000000,10000
5         SUM = SUM + X(J+I)
6     END DO
7 END DO

Lo lógico, salto de a uno unit stride.

1 REAL X(10000000)
2 COMMON X
3 DO I =1,10000000
4     SUM = SUM + X(I)
5 END DO

Ejercicio: hacer el bastard program que funcione lo más lentamente posible.

Presenter Notes

Sistemas de memoria anchos

Wider memory systems

  • Ráfagas de pedido
  • Bypass de cache.

Presenter Notes

De código fuente a ejecutable

clear.c, COaD5, Fig. 2.30

 1 void
 2 clear1(int array[], int size)
 3 {
 4     int i;
 5     for (i = 0; i < size; i += 1)
 6         array[i] = 0;
 7 }
 8 
 9 void
10 clear2(int *array, int size)
11 {
12     int *p;
13     for (p = &array[0]; p < &array[size]; p = p + 1)
14         *p = 0;
15 }
16 
17 void
18 clear3(int *array, int size)
19 {
20     memset(array, '\0', size*sizeof(array[0]));
21 }

Presenter Notes

Cosas para probar

Párametros de compilación

  • Optimizaciones: nada, -O0, -O1, -O2, -O3, -Os, -Ofast.
  • Versiones de compiladores: gcc-4.8, gcc-4.9, gcc-5, clang-3.5, clang-3.6, clang-3.7.
  • Diferentes arquitecturas: Nehalem, ARMv7, SandyBridge, Skylake, Merom, Barcelona, ARM A57, Abu Dhabi, etc.

Presenter Notes

Bibliografía

  • Charles Severance, Kevin Dowd, "High Performance Computing", Connexions, 2010, CC3.0.

Presenter Notes

La clase que viene

  • Punto Flotante.
  • Como funciona un µP moderno.

Presenter Notes