Introducción

Presenter Notes

Resumen:

  • Introducción a Arquitectura de Computadoras.
  • De código fuente a ejecutable.

Nicolás Wolovick 20140311

Presenter Notes

Introducción

Presenter Notes

Memoria

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

  • 1980, 8088 4.77 MHz, DRAM 200ns.
  • 2014, Ivy Bridge 3.0 GHz, DRAM 60ns.

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.

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.

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

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