tipos - C++: aceleración misteriosamente grande por mantener un operando en un registro
set de instrucciones de un procesador mips (3)
Es probable que sea una combinación de una cadena de dependencia más larga, junto con Load Misprediction *.
Cadena de dependencia más larga:
Primero, identificamos las rutas de dependencia críticas. Luego, observamos las latencias de las instrucciones proporcionadas por: http://www.agner.org/optimize/instruction_tables.pdf (página 117)
En la versión no optimizada, la ruta de dependencia crítica es:
-
addsd -72(%rbp), %xmm0 -
movsd %xmm0, -72(%rbp)
Internamente, probablemente se divide en:
- carga (2 ciclos)
- sumado (3 ciclos)
- tienda (3 ciclos)
Si miramos la versión optimizada, es solo:
- sumado (3 ciclos)
Entonces tienes 8 ciclos contra 3 ciclos. Casi un factor de 3.
No estoy seguro de cuán delicada es la línea de procesadores Nehalem para almacenar dependencias de carga y qué tan bien forwarding . Pero es razonable creer que no es cero.
Error de predicción de la tienda de carga
Los procesadores modernos usan la predicción de más formas que puedas imaginar. El más famoso de estos es probablemente la Predicción de ramas . Uno de los menos conocidos es Load Prediction.
Cuando un procesador ve una carga, inmediatamente la carga antes de que finalicen todas las escrituras pendientes. Supondrá que esas escrituras no entrarán en conflicto con los valores cargados.
Si una escritura anterior resulta en conflicto con una carga, entonces la carga debe ser re-ejecutada y el cálculo regresa al punto de la carga. (más o menos de la misma manera en que las predicciones erróneas de las ramas retroceden)
Cómo es relevante aquí:
Huelga decir que los procesadores modernos podrán ejecutar múltiples iteraciones de este bucle simultáneamente. Por lo tanto, el procesador intentará realizar la carga ( addsd -72(%rbp), %xmm0) antes de que finalice el almacenamiento ( movsd %xmm0, -72(%rbp) ) de la iteración anterior.
¿El resultado? La tienda anterior está en conflicto con la carga, por lo tanto, una predicción errónea y un retroceso.
* Tenga en cuenta que no estoy seguro del nombre "Load Prediction". Solo leí sobre esto en los documentos de Intel y no parecían darle un nombre.
He estado tratando de tener una idea del impacto de tener una matriz en la memoria caché L1 frente a la memoria al cronometrar una rutina que escala y suma los elementos de una matriz usando el siguiente código (soy consciente de que debo escalar el resultado por '' a ''al final, el punto es hacer tanto un multiplicar como un agregar dentro del ciclo, hasta ahora, el compilador no ha calculado para factorizar'' a ''):
double sum(double a,double* X,int size)
{
double total = 0.0;
for(int i = 0; i < size; ++i)
{
total += a*X[i];
}
return total;
}
#define KB 1024
int main()
{
//Approximately half the L1 cache size of my machine
int operand_size = (32*KB)/(sizeof(double)*2);
printf("Operand size: %d/n", operand_size);
double* X = new double[operand_size];
fill(X,operand_size);
double seconds = timer();
double result;
int n_iterations = 100000;
for(int i = 0; i < n_iterations; ++i)
{
result = sum(3.5,X,operand_size);
//result += rand();
}
seconds = timer() - seconds;
double mflops = 2e-6*double(n_iterations*operand_size)/seconds;
printf("Vector size %d: mflops=%.1f, result=%.1f/n",operand_size,mflops,result);
return 0;
}
Tenga en cuenta que las rutinas timer () y fill () no se incluyen por brevedad; su fuente completa se puede encontrar aquí si desea ejecutar el código:
Ahora, aquí es donde se pone interesante. Este es el resultado:
Operand size: 2048
Vector size 2048: mflops=588.8, result=-67.8
Este es un rendimiento totalmente sin memoria caché, a pesar del hecho de que todos los elementos de X deben mantenerse en caché entre iteraciones de bucle. Mirando el código ensamblador generado por:
g++ -O3 -S -fno-asynchronous-unwind-tables register_opt_example.cpp
Noto una rareza en el ciclo de la función suma:
L55:
movsd (%r12,%rax,8), %xmm0
mulsd %xmm1, %xmm0
addsd -72(%rbp), %xmm0
movsd %xmm0, -72(%rbp)
incq %rax
cmpq $2048, %rax
jne L55
Las instrucciones:
addsd -72(%rbp), %xmm0
movsd %xmm0, -72(%rbp)
indica que está almacenando el valor de "total" en suma () en la pila, y leyéndolo y escribiéndolo en cada iteración de bucle. Modifiqué el conjunto para que este operando se mantenga en un registro:
...
addsd %xmm0, %xmm3
...
Este pequeño cambio crea un gran impulso en el rendimiento:
Operand size: 2048
Vector size 2048: mflops=1958.9, result=-67.8
tl; dr Mi pregunta es: ¿por qué el reemplazo de una sola ubicación de memoria de acceso con un registro, acelera tanto el código, dado que la única ubicación debe almacenarse en caché L1? ¿Qué factores arquitectónicos lo hacen posible? Parece muy extraño que escribir una ubicación de pila en forma repetida destruiría por completo la efectividad de un caché.
Apéndice
Mi versión de gcc es:
Target: i686-apple-darwin10
Configured with: /var/tmp/gcc/gcc-5646.1~2/src/configure --disable-checking --enable-werror --prefix=/usr --mandir=/share/man --enable-languages=c,objc,c++,obj-c++ --program-transform-name=/^[cg][^.-]*$/s/$/-4.2/ --with-slibdir=/usr/lib --build=i686-apple-darwin10 --with-gxx-include-dir=/include/c++/4.2.1 --program-prefix=i686-apple-darwin10- --host=x86_64-apple-darwin10 --target=i686-apple-darwin10
Thread model: posix
gcc version 4.2.1 (Apple Inc. build 5646) (dot 1)
Mi CPU es:
Intel Xeon X5650
No puedo reproducir esto porque mi compilador (gcc 4.7.2) mantiene el total en un registro.
Sospecho que la razón principal de la lentitud no tiene que ver con la caché L1, sino que se debe a la dependencia de datos entre la tienda en
movsd %xmm0, -72(%rbp)
y la carga en la iteración siguiente:
addsd -72(%rbp), %xmm0
Supongo que el problema no está en el acceso de caché / memoria sino en el procesador (ejecución de su código). Hay varios cuellos de botella visibles aquí.
Los números de rendimiento aquí se basaron en las cajas que estaba usando (ya sea sandybridge o westmere)
El rendimiento máximo para las matemáticas escalares es 2.7Ghz x2 FLOPS / Clock x2 ya que el procesador puede hacer un add y multiplicar simultáneamente. La eficiencia teórica del código es 0.6 / (2.7 * 2) = 11%
Ancho de banda necesario: 2 dobles por (+) y (x) -> 4 bytes / Flop 4 bytes * 5.4GFLOPS = 21.6 GB / s
Si sabes que fue leído recientemente, es probable que sea en L1 (89 GB / s), L2 (42 GB / s) o L3 (24 GB / s), por lo que podemos descartar el caché B / N
El sistema de memoria de la memoria es de 18.9 GB / s por lo que incluso en la memoria principal, el rendimiento máximo debe acercarse a 18.9 / 21.6GB / s = 87.5%
- Es posible que desee agrupar las solicitudes (mediante el despliegue) lo antes posible
Incluso con la ejecución especulativa, tot + = a * X [i] las adiciones serán serializadas porque tot (n) necesita ser evaluado antes de que tot (n + 1) pueda ser iniciado
Primer ciclo de desenrollado
mover i por 8 y hacer
{//your func
for( int i = 0; i < size; i += 8 ){
tot += a * X[i];
tot += a * X[i+1];
...
tot += a * X[i+7];
}
return tot
}
Usa múltiples acumuladores
Esto romperá las dependencias y nos permitirá evitar el estancamiento en la tubería de adición
{//your func//
int tot,tot2,tot3,tot4;
tot = tot2 = tot3 = tot4 = 0
for( int i = 0; i < size; i += 8 )
tot += a * X[i];
tot2 += a * X[i+1];
tot3 += a * X[i+2];
tot4 += a * X[i+3];
tot += a * X[i+4];
tot2 += a * X[i+5];
tot3 += a * X[i+6];
tot4 += a * X[i+7];
}
return tot + tot2 + tot3 + tot4;
}
ACTUALIZACIÓN Después de ejecutar esto en un cuadro SandyBridge tengo acceso a: (2.7GHZ SandyBridge con -O2 -march = native -mtune = native
Código original:
Operand size: 2048
Vector size 2048: mflops=2206.2, result=61.8
2.206 / 5.4 = 40.8%
Código mejorado:
Operand size: 2048
Vector size 2048: mflops=5313.7, result=61.8
5.3137 / 5.4 = 98.4%