Introducción

Presenter Notes

Resumen:

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

Nicolás Wolovick 20200309

Presenter Notes

8M, las computadoras

Presenter Notes

Introducción

Presenter Notes

3 gráficos

  • Evolución microprocesadores.
  • Evolución precio memoria.
  • Latencias actuales.

Presenter Notes

42 Years of Microprocessor Trend Data

42 Years of Microprocessor Trend Data

Presenter Notes

Memory Prices (1957-2015)

Memory Disk Price Graph 1957-2015

Presenter Notes

Memory Prices (2005-2017)

Memory Disk Price Graph

Presenter Notes

Time Scale of System Latencies, Brendan Gregg

Presenter Notes

Toda la verdad

All performance is from parallelism

-

Machines are power limited

(efficiency IS performance)

-

Machines are communication limited

(locality IS performance)

.

.

(Bill Dally, Efficiency and Programmability: Enablers for ExaScale, SC13)

Presenter Notes

Empecemos

Presenter Notes

Memoria

La diferencia de derivada entre la velocidad de memoria y la velocidad de la CPU con respecto al paso de los años. Conmunmente conocido como memory wall.

  • 1979, 8088, 3µm, 4.77 MHz, DRAM ~200ns, $124.80 {2017:$426.09}
  • 2017, Coffee Lake (v8), 14 nm, 4.7 GHz, DRAM DDR4 <20ns, $360

Como aliviar este problema tecnológico:

A la memoria lenta hacerla ancha.
Mezclar memoria lenta y rápida.
A la memoria lenta hacerle muchos canales en paralelo.

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, típicamente 32.
    • Pero son anchos, pero hay varios juegos de registros, pero ... son muchos más de los que suponemos.

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.
Todos los procesadores tienen mucho más registros que los que se muestran (register renaming)

Presenter Notes

Caché

Para una DEC Alpha 21164 (1994, 333MHz, 500nm, 9.2MTr)
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

Importante: 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 lo 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

¿Para qué?

Cada proceso tiene una memoria disjunta.
Puede mapear memoria en disco: swapfile.
Puede mapear archivos en memoria: mmap().
Pedir memoria sin pedir memoria (zeroed or not)
Cargar en demanda.
Proteger partes internas de un proceso.
Memorias circulares.
Compartir memoria común entre procesos (libraries).
...

Presenter Notes

Empezó con 2 niveles de indirección

I'm doing a (free) operating system (just a hobby, won't be big and professional like gnu) for 386(486) AT clones., 1991.

Presenter Notes

Luego 3 pero el ultimo chiquito (aka PAE)

2.3.23-pre4 x86 64GB RAM changes [HIGHMEM patch] explained a bit, 1999.

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

Presenter Notes

Luego 4 (hasta 256 TiB de RAM)

Four-level page tables merged, 2005.

Presenter Notes

En 2017 pasado agregaron 5

Five-level page tables, 2017.

Presenter Notes

TLB (Translation Lookaside Buffer)

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

  • Granularidad: página de 4 KiB ó 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.

Memoria paralela

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-5, gcc-6, gcc-7, gcc-8, clang-3.9, clang-4, clang-5, clang-6.
  • Diferentes arquitecturas: Nehalem, ARMv7, SandyBridge, Skylake, Merom, Barcelona, ARM A53, Abu Dhabi, etc.

Presenter Notes

Bibliografía

Presenter Notes

La clase que viene

  • Representaciones numéricas:
    • Punto flotante.
    • Punto fijo.

Presenter Notes