c++ gcc linear-algebra compiler-optimization execution-time

c++ - gcc-O0 supera a-O3 en tamaños de matriz que son potencias de 2(transposiciones de matriz)



linear-algebra compiler-optimization (4)

Comentario con el código: En el caso de -O3, con

#include <cstdlib> extern void transpose(const size_t n, double* a) { for (size_t i = 0; i < n; ++i) { for (size_t j = i + 1; j < n; ++j) { std::swap(a[i * n + j], a[j * n + i]); // or your expanded version. } } }

compilando con

$ g++ --version g++ (Ubuntu/Linaro 4.8.1-10ubuntu9) 4.8.1 ... $ g++ -g1 -std=c++11 -Wall -o test.S -S test.cpp -O3

yo obtengo

_Z9transposemPd: .LFB68: .cfi_startproc .LBB2: testq %rdi, %rdi je .L1 leaq 8(,%rdi,8), %r10 xorl %r8d, %r8d .LBB3: addq $1, %r8 leaq -8(%r10), %rcx cmpq %rdi, %r8 leaq (%rsi,%rcx), %r9 je .L1 .p2align 4,,10 .p2align 3 .L10: movq %r9, %rdx movq %r8, %rax .p2align 4,,10 .p2align 3 .L5: .LBB4: movsd (%rdx), %xmm1 movsd (%rsi,%rax,8), %xmm0 movsd %xmm1, (%rsi,%rax,8) .LBE4: addq $1, %rax .LBB5: movsd %xmm0, (%rdx) addq %rcx, %rdx .LBE5: cmpq %rdi, %rax jne .L5 addq $1, %r8 addq %r10, %r9 addq %rcx, %rsi cmpq %rdi, %r8 jne .L10 .L1: rep ret .LBE3: .LBE2: .cfi_endproc

Y algo bastante diferente si agrego -m32.

(Nota: no hace ninguna diferencia en el ensamblaje si uso std :: swap o su variante)

Sin embargo, para comprender qué está causando los picos, es probable que desee visualizar las operaciones de memoria que se están realizando.

(Para propósitos de prueba) He escrito un Método simple para calcular la transposición de una Matriz nxn

void transpose(const size_t _n, double* _A) { for(uint i=0; i < _n; ++i) { for(uint j=i+1; j < _n; ++j) { double tmp = _A[i*_n+j]; _A[i*_n+j] = _A[j*_n+i]; _A[j*_n+i] = tmp; } } }

Cuando utilizaba niveles de optimización O3 o Ofast, esperaba que el compilador desarrollara algunos bucles, lo que conduciría a un mayor rendimiento, especialmente cuando el tamaño de la matriz es un múltiplo de 2 (es decir, el cuerpo del doble bucle se puede realizar en cada iteración) o similar. En cambio, lo que medí fue exactamente lo contrario. Los poderes de 2 en realidad muestran un aumento significativo en el tiempo de ejecución.

Estos picos también están en intervalos regulares de 64, más pronunciados en intervalos de 128 y así sucesivamente. Cada punta se extiende a los tamaños de matriz adyacentes como en la siguiente tabla

size n time(us) 1020 2649 1021 2815 1022 3100 1023 5428 1024 15791 1025 6778 1026 3106 1027 2847 1028 2660 1029 3038 1030 2613

Compilé con una versión de gcc 4.8.2, pero lo mismo ocurre con un clang 3.5, ¿entonces esto podría ser algo genérico?

Entonces mi pregunta básicamente es: ¿Por qué hay este aumento periódico en el tiempo de ejecución? ¿Es algo genérico que viene con alguna de las opciones de optimización (como sucede con clang y gcc por igual)? Si es así, ¿qué opción de optimización está causando esto?

¿Y cómo puede ser esto tan significativo que incluso la versión O0 del programa supera a la versión 03 en múltiplos de 512?

EDITAR: tenga en cuenta la magnitud de los picos en esta gráfica (logarítmica). Transponer una matriz de 1024x1024 con optimización en realidad toma tanto tiempo como transponer una matriz de 1300x1300 sin optimización. Si este es un problema de falla de caché / falla de página, entonces alguien tiene que explicarme por qué el diseño de la memoria es tan diferente para la versión optimizada del programa, que falla por dos poderes, solo para recuperar el alto rendimiento de Matrices ligeramente más grandes. ¿No deberían las fallas de caché crear más de un patrón escalonado? ¿Por qué los tiempos de ejecución vuelven a bajar? (¿Y por qué debería la optimización crear fallas de caché que no existían antes?)

EDIT: los siguientes deben ser los códigos de ensamblador que gcc produjo

sin optimización (O0):

_Z9transposemRPd: .LFB0: .cfi_startproc push rbp .cfi_def_cfa_offset 16 .cfi_offset 6, -16 mov rbp, rsp .cfi_def_cfa_register 6 mov QWORD PTR [rbp-24], rdi mov QWORD PTR [rbp-32], rsi mov DWORD PTR [rbp-4], 0 jmp .L2 .L5: mov eax, DWORD PTR [rbp-4] add eax, 1 mov DWORD PTR [rbp-8], eax jmp .L3 .L4: mov rax, QWORD PTR [rbp-32] mov rdx, QWORD PTR [rax] mov eax, DWORD PTR [rbp-4] imul rax, QWORD PTR [rbp-24] mov rcx, rax mov eax, DWORD PTR [rbp-8] add rax, rcx sal rax, 3 add rax, rdx mov rax, QWORD PTR [rax] mov QWORD PTR [rbp-16], rax mov rax, QWORD PTR [rbp-32] mov rdx, QWORD PTR [rax] mov eax, DWORD PTR [rbp-4] imul rax, QWORD PTR [rbp-24] mov rcx, rax mov eax, DWORD PTR [rbp-8] add rax, rcx sal rax, 3 add rdx, rax mov rax, QWORD PTR [rbp-32] mov rcx, QWORD PTR [rax] mov eax, DWORD PTR [rbp-8] imul rax, QWORD PTR [rbp-24] mov rsi, rax mov eax, DWORD PTR [rbp-4] add rax, rsi sal rax, 3 add rax, rcx mov rax, QWORD PTR [rax] mov QWORD PTR [rdx], rax mov rax, QWORD PTR [rbp-32] mov rdx, QWORD PTR [rax] mov eax, DWORD PTR [rbp-8] imul rax, QWORD PTR [rbp-24] mov rcx, rax mov eax, DWORD PTR [rbp-4] add rax, rcx sal rax, 3 add rdx, rax mov rax, QWORD PTR [rbp-16] mov QWORD PTR [rdx], rax add DWORD PTR [rbp-8], 1 .L3: mov eax, DWORD PTR [rbp-8] cmp rax, QWORD PTR [rbp-24] jb .L4 add DWORD PTR [rbp-4], 1 .L2: mov eax, DWORD PTR [rbp-4] cmp rax, QWORD PTR [rbp-24] jb .L5 pop rbp .cfi_def_cfa 7, 8 ret .cfi_endproc .LFE0: .size _Z9transposemRPd, .-_Z9transposemRPd .ident "GCC: (Debian 4.8.2-15) 4.8.2" .section .note.GNU-stack,"",@progbits

con optimización (O3)

_Z9transposemRPd: .LFB0: .cfi_startproc push rbx .cfi_def_cfa_offset 16 .cfi_offset 3, -16 xor r11d, r11d xor ebx, ebx .L2: cmp r11, rdi mov r9, r11 jae .L10 .p2align 4,,10 .p2align 3 .L7: add ebx, 1 mov r11d, ebx cmp rdi, r11 mov rax, r11 jbe .L2 mov r10, r9 mov r8, QWORD PTR [rsi] mov edx, ebx imul r10, rdi .p2align 4,,10 .p2align 3 .L6: lea rcx, [rax+r10] add edx, 1 imul rax, rdi lea rcx, [r8+rcx*8] movsd xmm0, QWORD PTR [rcx] add rax, r9 lea rax, [r8+rax*8] movsd xmm1, QWORD PTR [rax] movsd QWORD PTR [rcx], xmm1 movsd QWORD PTR [rax], xmm0 mov eax, edx cmp rdi, rax ja .L6 cmp r11, rdi mov r9, r11 jb .L7 .L10: pop rbx .cfi_def_cfa_offset 8 ret .cfi_endproc .LFE0: .size _Z9transposemRPd, .-_Z9transposemRPd .ident "GCC: (Debian 4.8.2-15) 4.8.2" .section .note.GNU-stack,"",@progbits

El aumento periódico del tiempo de ejecución se debe a que la memoria caché solo es asociativa en N, en lugar de totalmente asociativa. Estás presenciando una colisión de hash relacionada con el algoritmo de selección de línea de caché

El caché L1 más rápido tiene un número menor de líneas de caché que el siguiente nivel L2. En cada nivel, cada línea de caché se puede rellenar solo desde un conjunto limitado de fuentes.

Las implementaciones típicas de HW de los algoritmos de selección de línea de caché solo utilizarán algunos bits de la dirección de memoria para determinar en qué ranura de caché se deben escribir los datos. Los cambios de bits de HW son gratuitos.

Esto provoca una competencia entre rangos de memoria, por ejemplo, entre las direcciones 0x300010 y 0x341010. En un algoritmo completamente secuencial, esto no importa: N es lo suficientemente grande para prácticamente todos los algoritmos de la forma:

for (i=0;i<1000;i++) a[i] += b[i] * c[i] + d[i];

Pero cuando el número de las entradas (o salidas) aumenta, lo que ocurre internamente cuando el algoritmo está optimizado, tener una entrada en la memoria caché obliga a otra entrada a salir de la memoria caché.

// one possible method of optimization with 2 outputs and 6 inputs // with two unrelated execution paths -- should be faster, but maybe it isn''t for (i=0;i<500;i++) { a[i] += b[i] * c[i] + d[i]; a[i+500] += b[i+500] * c[i+500] + d[i+500]; }

Un gráfico en el Ejemplo 5: La asociación de caché ilustra el desplazamiento de 512 bytes entre las líneas de la matriz y es la dimensión del peor caso global para el sistema en particular. Cuando se sabe esto, una mitigación de trabajo es sobre-asignar la matriz horizontalmente a alguna otra char matrix[512][512 + 64] dimensión char matrix[512][512 + 64] .

La mejora en el rendimiento probablemente esté relacionada con el almacenamiento en caché de la CPU / RAM.

Cuando los datos no tienen una potencia de 2, una carga de línea de caché (como 16, 32 o 64 palabras) transfiere más que los datos que se requieren para atar el bus, por inútil que resulte. Para un conjunto de datos que es una potencia de 2, se utilizan todos los datos precargados.

Apuesto a que si deshabilitases el almacenamiento en caché L1 y L2, el rendimiento sería completamente suave y predecible. Pero sería mucho más lento. El almacenamiento en caché realmente ayuda al rendimiento!

Para agregar a otros: g++ -std=c++11 -march=core2 -O3 -c -S - gcc versión 4.8.2 (MacPorts gcc48 4.8.2_0) - x86_64-apple-darwin13.0.0:

__Z9transposemPd: LFB0: testq %rdi, %rdi je L1 leaq 8(,%rdi,8), %r10 xorl %r8d, %r8d leaq -8(%r10), %rcx addq $1, %r8 leaq (%rsi,%rcx), %r9 cmpq %rdi, %r8 je L1 .align 4,0x90 L10: movq %r9, %rdx movq %r8, %rax .align 4,0x90 L5: movsd (%rdx), %xmm0 movsd (%rsi,%rax,8), %xmm1 movsd %xmm0, (%rsi,%rax,8) addq $1, %rax movsd %xmm1, (%rdx) addq %rcx, %rdx cmpq %rdi, %rax jne L5 addq $1, %r8 addq %r10, %r9 addq %rcx, %rsi cmpq %rdi, %r8 jne L10 L1: rep; ret

Básicamente lo mismo que el código de @ksfone, para:

#include <cstddef> void transpose(const size_t _n, double* _A) { for(size_t i=0; i < _n; ++i) { for(size_t j=i+1; j < _n; ++j) { double tmp = _A[i*_n+j]; _A[i*_n+j] = _A[j*_n+i]; _A[j*_n+i] = tmp; } } }

Aparte de las diferencias de Mach-O (como subrayado adicional, alineación y ubicaciones DWARF), es lo mismo. Pero muy diferente de la salida de montaje del OP. Un bucle interno mucho más "apretado".