[clear.c](clear.c)
.Nicolás Wolovick 20160308
La diferencia de derivada entre la velocidad de memoria y la CPU.
Aliviar:
Diferencias sustanciales:
La gran idea:
Jerarquía de Memoria
Cómputo de (sub)expresiones.
1 REAL*4 G,A,W,M
2 X = G * 2.41 + A / W - W * M
No es lineal #regs y desempeño.
Para una DEC Alpha 21164. La esperanza de acceso a memoria para las siguientes probabilidades:
0.9*4 + 0.07*5 + 0.02*30 + 0.01*220 = 6.75 ns
Almacena celdas dispersas de la memoria.
Granularidad: línea.
Dinámica: tener lo más frecuentemente usado.
Esto es lo mismo que explotar la
del acceso a la memoria por parte de los programas.
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
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.
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
Esquema simple. Mapeo no inyectivo memoria -> cache. One-way set associative.
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
Two-way set associative.
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
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
Mapeo arbitrario de un espacio de direcciones (virtual) a otro (físico).
Pffff, dos accesos a tabla por acceso a memoria! Muy pesado, pero elegantísimo.
swapfile
.mmap()
.Caché para guardar el mapeo virtual->físico.
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.
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 }
-O0
, -O1
, -O2
, -O3
, -Os
, -Ofast
.gcc-4.8
, gcc-4.9
, gcc-5
, clang-3.5
, clang-3.6
, clang-3.7
.Table of Contents | t |
---|---|
Exposé | ESC |
Full screen slides | e |
Presenter View | p |
Source Files | s |
Slide Numbers | n |
Toggle screen blanking | b |
Show/hide slide context | c |
Notes | 2 |
Help | h |