Más Optimizaciones en CPU

Presenter Notes

Resumen:

Otras cosas que si tiene sentido hacer:

Aliasing.
Alineamiento de memoria.
AoS vs. SoA.
Blocking.
Ejemplos:
- Transposición de matrices.
- Multiplicación matriz por matriz.
Guías generales para optimización secuencial.

Nicolás Wolovick 20180405

Presenter Notes

¿Qué cosas si tiene sentido hacer? (Parte 2)

No usar bibliotecas low-performance como libc.
Un poco de loop unrolling.
- Desarma dependencias usando registros para lograr más ILP.
- La ganancia no está en ahorrarse un branch (99% de predicción).
- Tienen un límite: register spilling.
Exponer paralelismo dependiente del problema.
Optimizaciones de Caché y TLB.
- Reorganización de loops.
- Cache blocking o loop tiling.
- Alineamiento de memoria.
Indicar que no hay aliasing.

Presenter Notes

Aliasing

Problema de "C".

 1 void updatePtrs(int *ptrA, int *ptrB, int *val) { // se puede optimizar
 2     *ptrA += *val;
 3     *ptrB += *val;
 4 }
 5 
 6 
 7 struct node {
 8     struct node *next, *prev;
 9 };
10 
11 void foo(struct node *n) { // no se puede optimizar
12     n->next->prev->next=n;
13     n->next->next->prev=n;
14 }

Usamos la palabra clave restrict

1 void updatePtrs(int * restrict ptrA, int * restrict ptrB,
2                 int * restrict val) {

Y el compilador puede hacer lo esperable.

Presenter Notes

Alineamiento de memoria

Podemos pedirle al compilador que ponga las cosas alineadas (GNU).

1 float a[L][L] __attribute__((aligned(64))),
2       b[L] __attribute__((aligned(64))),
3       c[L] __attribute__((aligned(64)));

Ningún efecto sobre variables globales.
Originalmente alineadas a 32 bytes.

Usar aligned_alloc() para memoria dinámica.
Ejemplo pensando en líneas de caché de 64 bytes.

1 #include <malloc.h>
2 double *a = aligned_alloc(64, N*N*sizeof(double))

Tampoco parece producir efectos.

Presenter Notes

Algoritmos caché-aware

Tener en cuenta:

Localidad espacial y temporal.
Parámetros del caché.
- line size.
- associativity.

AoS vs. SoA

Figure 10. Shuffling an AoS into a SoA.

Presenter Notes

Ejemplo

AoS (array of structures)

1 struct point {
2   float dx, dy, dz, dw;
3 };
4 point p[N];
5 
6 for (int i=0; i<N; ++i) {
7   dist = sqrtf(p[i].dx*p[i].dx + p[i].dy*p[i].dy + p[i].dz*p[i].dz + p[i].dw*p[i].dw)
8 }

SoA (structure of arrays)

1 struct p {
2   float dx[N], dy[N], dz[N], dw[N];
3 };
4 
5 for (int i=0; i<N; ++i) {
6   dist = sqrtf(p.dx[i]*p.dx[i] + p.dy[i]*p.dy[i] + p.dz[i]*p.dz[i] + p.dw[i]*p.dw[i])
7 }

Presenter Notes

Ejemplo B = A^t

Presenter Notes

Transposición de matrices

Intensidad aritmética

q = 0 / (2 L²) = 0

Memory-bound 😓

Matriz en la memoria (row-major)

Organización de la matriz en memoria

Presenter Notes

Naïve

 1 #define L (1<<11)
 2 
 3 float a[L][L], b[L][L];
 4 
 5 int main(void) {
 6     unsigned int i=0, j=0;
 7     for (i=0; i<L; ++i)
 8             for (j=0; j<L; ++j)
 9                 b[j][i] = a[i][j];
10     return (int)b[(int)b[0][2]][(int)b[2][0]];
11 }

Presenter Notes

Naïve, medición

 1 $ gcc-8 -O3 mtxtransp1.c && perf stat -r 16 -e instructions,cycles,cache-references,cache-misses ./a.out
 2 
 3 Performance counter stats for './a.out' (16 runs):
 4 
 5   24,518,383 instructions     # 0.04  insn per cycle      ( +-  1.46% )  (74.72%)
 6  589,419,748 cycles                                       ( +-  0.32% )  (74.86%)
 7    5,605,508 cache-references                             ( +-  0.32% )  (74.83%)
 8    4,468,003 cache-misses     #79.707 % of all cache refs ( +-  0.28% )  (50.31%)
 9 
10    0.228426360 seconds time elapsed                       ( +-  1.93% )

Notar el bajísimo IPC.
perf muestra claramente el problema.

Intel Core2 Duo P8800@2.66GHz, gcc-8.0.1, Linux 4.15.11 x86_64

Presenter Notes

Tiled

Usamos cache blocking o loop tiling a mano.

 1 #define L (1<<11)
 2 
 3 const unsigned int BX=1<<4;
 4 const unsigned int BY=1<<4;
 5 
 6 float a[L][L], b[L][L];
 7 
 8 int main(void) {
 9     unsigned int i=0, j=0, k=0, l=0;
10     assert(0==L%BX && 0==L%BY);
11     for (i=0; i<L; i+=BY)
12         for (j=0; j<L; j+=BX)
13             for (k=i; k<i+BY; ++k)
14                 for (l=j; l<j+BX; ++l)
15                     b[l][k] = a[k][l];
16     return (int)b[(int)b[0][2]][(int)b[2][0]];
17 }

Presenter Notes

Tiled, medición

 1 $ gcc-8 -O3 mtxtransp2.c && perf stat -r 16 -e instructions,cycles,cache-references,cache-misses ./a.out
 2 
 3 Performance counter stats for './a.out' (16 runs):
 4 
 5   40,650,922 instructions     # 0.35  insn per cycle      ( +-  0.69% )  (72.24%)
 6  114,607,354 cycles                                       ( +-  0.80% )  (72.54%)
 7    4,722,970 cache-references                             ( +-  1.68% )  (77.67%)
 8      542,791 cache-misses     #11.493 % of all cache refs ( +-  1.97% )  (49.79%)
 9 
10  0.044948155 seconds time elapsed                         ( +-  1.14% )

Speedup: 0.22s/0.045s = 4.88x

clap, clap, clap ...

Intel Core2 Duo P8800@2.66GHz, gcc-8.0.1, Linux 4.15.11 x86_64

Presenter Notes

No seamos naïve

"Any sufficiently advanced (compiler) technology is indistinguishable from magic.", Jorge Luis Borges, circa 1971.

GCC Manual, 3.10 Options That Control Optimization, GNU, 2018.

1 -ftree-loop-linear
2 -floop-strip-mine
3 -floop-block
4 
5     Perform loop nest optimizations. Same as -floop-nest-optimize. To use this code transformation, GCC has to be configured with --with-isl to enable the Graphite loop transformation infrastructure.

Veamos como va ...

 1 $ rm a.out; gcc-8 -O3 -floop-block mtxtransp1.c && perf stat -r 16 -e instructions,cycles,cache-references,cache-misses ./a.out
 2 
 3 Performance counter stats for './a.out' (16 runs):
 4 
 5 92,203,819 instructions     # 0.96 insn per cycle       ( +-  0.56% )  (70.52%)
 6 95,723,528 cycles                                       ( +-  0.63% )  (78.14%)
 7  4,042,367 cache-references                             ( +-  0.25% )  (78.24%)
 8    458,531 cache-misses     #11.343 % of all cache refs ( +-  3.31% )  (43.62%)
 9 
10    0.037237697 seconds time elapsed                     ( +-  0.45% )

Presenter Notes

Compartativa de máquinas

Todos gcc-8 salvo Eulogia gcc-7.4

Plata (Penryn)

1 -O3               mtxtransp1.c    0.210
2 -O3 -floop-block  mtxtransp1.c    0.037
3 -O3               mtxtransp2.c    0.045
4 -O3 -floop-block  mtxtransp2.c    0.045

Jupiterace (Haswell)

1 -O3               mtxtransp1.c    0.053
2 -O3 -floop-block  mtxtransp1.c    0.033
3 -O3               mtxtransp2.c    0.032
4 -O3 -floop-block  mtxtransp2.c    0.032

Eulogia (KNL)

1 -O3               mtxtransp1.c    0.200
2 -O3 -floop-block  mtxtransp1.c    0.130
3 -O3               mtxtransp2.c    0.141
4 -O3 -floop-block  mtxtransp2.c    0.142

"Cada máquina es un mundo", JLB, circa 1962.

Presenter Notes

¿Cuál es el mejor tamaño de bloque?

P8800, gcc-4.7.3, Linux 3.8.0 (plata en 2016)

Exploración tamaño de bloque

De los 0.21s, llegamos a 0.031s, 6.77x de speedup!

Presenter Notes

P8800

con gcc-8 y linux-4.15 (plata hoy)

Exploración tamaño de bloque

Presenter Notes

E5-2620v3

con gcc-8 y linux-4.15 (jupiterace hoy)

Exploración tamaño de bloque

Presenter Notes

XeonPhi 7210

con gcc-7 y linux-3.10 (Eulogia hoy)

Exploración tamaño de bloque

Presenter Notes

Ejemplo `dgemm`

Presenter Notes

Multiplicación matriz por matriz

Jerarquía BLAS

Dot product: L data, 2L flops.
Matrix-vector multiply: L² data, 2L² flops.
Matrix-matrix multiply: 2L² data, 2L³ flops.

`dgemm` intensidad aritmética

q = flops/bytes = O(L)

`dgemm` uso de memoria

Memoria total: O(L²).
Memoria accedida: O(L³).
Reuso: O(L).

Presenter Notes

Muchísimas mediciones en consola

dgemm.c
dgemm_unroll.c
dgemm_blocking_CoAD.c
dgemm_blocking.f
dgemm_blocking.c
dgemm_blocking_unrolling_CoAD.c
dgemm_blas.c

Análisis de:

Scaling con el tamaño.
IPC.
Cache misses.
Tamaño del blocking.

Presenter Notes

Naïve vs. Blocking vs. Vendor

CS5220, David Bindel, Lecture 2: Tiling matrix-matrix multiply, code tuning

Core2, 10 GFLOPS performance pico usando los 2 cores. El vendor está al 70% de la performance pico.

Presenter Notes

Problemas con las arquitecturas nuevas

Knights Landing support #991, OpenBLAS, 2018.
OpenMP-based parallel implementation of matrix-matrix multiplication on the Intel Knights Landing, 2018.

Presenter Notes

Espacio de búsqueda del tamaño del bloque

SDSC, CS260, Matrix Matrix Multiply

Presenter Notes

`sgemm` y `dgemm` de BLAS3

Problema muy estudiado.
Núcleo de la medición de Top500.
Caso paradigmático: Parello'02
- Alpha 21264, 1GHz, 2 FP, 2 GFLOPS-
- A través de 9 iteraciones logran 95% de la performance pico.

We have also shown that cache tiling, on which a large share of research works focus, only accounts for 12% of the total performance improvement ...

Mucho esfuerzo en los compiladores de vendors.
Infinito esfuerzo en las bibliotecas: Magma, OpenBLAS (ex GotoBLAS), LIBXSMM ATLAS, MLK, ACML.

Presenter Notes

Consejos

Best case: good algorithm, efficient design, obvious code.
Tradeoff: speed vs readability, debuggability, maintainability ...
Only optimize when needful.
Go for low-hanging fruit first: data layouts, libraries, compiler flags.
Concentrate on the bottleneck.
Concentrate on inner loops.
Get correctness (and a test framework) first.

CS5220, David Bindel, Lecture 2: Tiling matrix-matrix multiply, code tuning.

Presenter Notes

Más consejos

CPU

Usar buenas herramientas:perf, Intel VTune, etc.
Usar buenas bibliotecas: OpenBLAS, FFTW, etc.
Flags de compilación.
- -O3: Aggressive optimization.
- -march=native: Tune for specific architecture.
- -ftree-vectorize: Automatic use of SSE (se supone).
- -funroll-loops: Loop unrolling.
- -ffast-math: Unsafe floating point optimizations.
- Usar graphite, ejemplo -floop-block.
- Profile-guided optimization (PGO): -fprofile-generate, -fprofile-correction.

Presenter Notes

Más consejos

Memoria

Prestarle atención al memory layout.
Usar la menor cantidad de memoria posible.
- Bit arrays.
- Mixed precision.
Evitar dependencias falsas.
Loop unrolling para operar sobre registros.

Presenter Notes

Conclusión

Optimizar es complejo

"Therefore my best advice is to avoid loop unrolling. An unrolled loop takes more space in the μop cache, and the advantage of loop unrolling is minimal."

(8.16, Bottlenecks in Sandy Bridge, The microarchitecture of ..., Agner Fog)

"Note that we are not making any absolute predictions on code performance for these implementations, or even relative comparison of their runtimes. Such predictions are very hard to make. However, the above discussion identifies issues that are relevant for a wide range of classical CPUs."

(p.33, Eijkhout, Intro ...)

Presenter Notes

Bibliografía

Presenter Notes

Bibliografía

Charles Severance, Kevin Dowd, "High Performance Computing", Connexions, 2010, CC3.0.
Patterson, Hennessy Computer Organization and Design, Fifth Edition, Morgan Kaufmann, 2012.
Hennessy, Patterson, Computer Architecture: A Quantitative Approach, Fourth Edition, Morgan Kaufmann, 2011.
Chatterjeey, Senz, Cache-Efficient Matrix Transposition, HPCA-6, 2000.
Parello, Temam, Verdun, On Increasing Architecture Awareness in Program Optimizations to Bridge the Gap between Peak and Sustained Processor Performance -- Matrix-Multiply Revisited, SC02.
Agner Fog, Optimizing software in C++. An optimization guide for Windows, Linux and Mac platforms, 2012.
Felix von Leitne, Source Code Optimization, 2009.
Mike Acton, Demystifying The Restrict Keyword, 2006.

Presenter Notes

La clase que viene

Límites y El Paralelismo.

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

AoS vs. SoA

AoS (array of structures)

SoA (structure of arrays)

Intensidad aritmética

Matriz en la memoria (row-major)

Plata (Penryn)

Jupiterace (Haswell)

Eulogia (KNL)

Jerarquía BLAS

dgemm intensidad aritmética

dgemm uso de memoria

CPU

Memoria

Optimizar es complejo

Table of Contents

Help

`dgemm` intensidad aritmética

`dgemm` uso de memoria