c++ - sirve - Motivo del colapso del ancho de banda de la memoria cuando se almacenan en caché 2KB de datos en el caché L1

si borro la memoria cache se borran mis fotos

Question

En un proyecto autoeducativo, mido el ancho de banda de la memoria con la ayuda del siguiente código (parafraseado, el código completo aparece al final de la pregunta):

unsigned int doit(const std::vector<unsigned int> &mem){
   const size_t BLOCK_SIZE=16;
   size_t n = mem.size();
   unsigned int result=0;
   for(size_t i=0;i<n;i+=BLOCK_SIZE){           
             result+=mem[i];
   }
   return result;
}

//... initialize mem, result and so on
int NITER = 200; 
//... measure time of
   for(int i=0;i<NITER;i++)
       resul+=doit(mem)

BLOCK_SIZE se BLOCK_SIZE de tal manera que se obtenga una línea de caché de 64 bytes por cada suma de entero. Mi máquina (una Intel-Broadwell) necesita aproximadamente 0,35 nanosegundos por entero, por lo que el código anterior podría saturar un ancho de banda de hasta 182 GB / s (este valor es solo un límite superior y probablemente está bastante apagado, lo que es importante es el relación de anchos de banda para diferentes tamaños). El código se compila con g++ y -O3 .

Al variar el tamaño del vector, puedo observar los anchos de banda esperados para cachés L1 (*) -, L2, L3 y la memoria RAM:

Sin embargo, hay un efecto que realmente me cuesta explicar: el colapso del ancho de banda medido de la memoria caché L1 para tamaños de aproximadamente 2 kB, aquí en una resolución algo más alta:

Podía reproducir los resultados en todas las máquinas a las que tengo acceso (que tienen procesadores Intel-Broadwell e Intel-Haswell).

Mi pregunta: ¿Cuál es la razón del colapso del rendimiento para los tamaños de memoria de aproximadamente 2 KB?

(*) Espero entender correctamente, que para la memoria caché L1 no es de 64 bytes sino que solo se leen / transfieren 4 bytes por adición (no hay una memoria caché más rápida donde se debe llenar una línea de memoria caché), por lo que el ancho de banda trazado para L1 es Sólo el límite superior y no el mal ancho en sí.

Edición : cuando el tamaño de paso en el for-loop interno se elige para ser

• 8 (en lugar de 16) el colapso ocurre para 1KB
• 4 (en lugar de 16) el colapso ocurre para 0.5KB

es decir, cuando el bucle interno consta de aproximadamente 31-35 pasos / lecturas. Eso significa que el colapso no se debe al tamaño de la memoria, sino a la cantidad de pasos en el bucle interno.

Se puede explicar con las faltas de sucursal como se muestra en la gran respuesta de @ user10605163 .

Listado para reproducir los resultados.

bandwidth.cpp

#include <vector>
#include <chrono>
#include <iostream>
#include <algorithm>


//returns minimal time needed for one execution in seconds:
template<typename Fun>
double timeit(Fun&& stmt, int repeat, int number)
{  
   std::vector<double> times;
   for(int i=0;i<repeat;i++){
       auto begin = std::chrono::high_resolution_clock::now();
       for(int i=0;i<number;i++){
          stmt();
       }
       auto end = std::chrono::high_resolution_clock::now();
       double time = std::chrono::duration_cast<std::chrono::nanoseconds>(end-begin).count()/1e9/number;
       times.push_back(time);
   }
   return *std::min_element(times.begin(), times.end());
}


const int NITER=200;
const int NTRIES=5;
const size_t BLOCK_SIZE=16;


struct Worker{
   std::vector<unsigned int> &mem;
   size_t n;
   unsigned int result;
   void operator()(){
        for(size_t i=0;i<n;i+=BLOCK_SIZE){           
             result+=mem[i];
        }
   }

   Worker(std::vector<unsigned int> &mem_):
       mem(mem_), n(mem.size()), result(1)
   {}
};

double PREVENT_OPTIMIZATION=0.0;


double get_size_in_kB(int SIZE){
   return SIZE*sizeof(int)/(1024.0);
}

double get_speed_in_GB_per_sec(int SIZE){
   std::vector<unsigned int> vals(SIZE, 42);
   Worker worker(vals);
   double time=timeit(worker, NTRIES, NITER);
   PREVENT_OPTIMIZATION+=worker.result;
   return get_size_in_kB(SIZE)/(1024*1024)/time;
}


int main(){

   int size=BLOCK_SIZE*16;
   std::cout<<"size(kB),bandwidth(GB/s)/n";
   while(size<10e3){
       std::cout<<get_size_in_kB(size)<<","<<get_speed_in_GB_per_sec(size)<<"/n";
       size=(static_cast<int>(size+BLOCK_SIZE)/BLOCK_SIZE)*BLOCK_SIZE;
   }

   //ensure that nothing is optimized away:
   std::cerr<<"Sum: "<<PREVENT_OPTIMIZATION<<"/n";
}

create_report.py :

import sys
import pandas as pd
import matplotlib.pyplot as plt

input_file=sys.argv[1]
output_file=input_file[0:-3]+''png''
data=pd.read_csv(input_file)

labels=list(data)    
plt.plot(data[labels[0]], data[labels[1]], label="my laptop")
plt.xlabel(labels[0])
plt.ylabel(labels[1])   
plt.savefig(output_file)
plt.close()

Creación / ejecución / creación de informe:

>>> g++ -O3 -std=c++11 bandwidth.cpp -o bandwidth
>>> ./bandwidth > report.txt
>>> python create_report.py report.txt
# image is in report.png

Answer 1

Cambié los valores ligeramente: NITER = 100000 y NTRIES=1 para obtener un resultado menos ruidoso.

No tengo un Broadwell disponible en este momento, sin embargo, probé su código en mi Coffee-Lake y obtuve una caída en el rendimiento, no de 2KB, sino de alrededor de 4.5KB. Además, encuentro un comportamiento errático del rendimiento ligeramente por encima de 2 KB.

La línea azul en el gráfico corresponde a su medida (eje izquierdo):

La línea roja aquí es el resultado de perf stat -e branch-instructions,branch-misses , que dan la fracción de ramificaciones que no se predijeron correctamente (en porcentaje, eje derecho). Como puede ver, hay una clara correlación entre los dos.

Al perf informe de perf más detallado, descubrí que, básicamente, todas estas predicciones erróneas de ramificaciones se producen en el bucle más interno en Worker::operator() . Si el patrón tomado / no tomado de la rama del bucle se vuelve demasiado largo, el predictor de la rama no podrá seguirlo y, por lo tanto, la rama de salida del bucle interno se predecirá erróneamente, lo que provocará una caída brusca en el rendimiento. Con un número cada vez mayor de iteraciones, el impacto de este error de cálculo solo será menos significativo, lo que llevará a una recuperación lenta del rendimiento.

Para obtener más información sobre el comportamiento errático antes de la caída, consulte los comentarios realizados por @PeterCordes a continuación.

En cualquier caso, la mejor manera de evitar las predicciones erróneas de las sucursales es evitar las ramificaciones, por lo que desenrollo manualmente el bucle en Worker::operator() , como por ejemplo:

void operator()(){
    for(size_t i=0;i+3*BLOCK_SIZE<n;i+=BLOCK_SIZE*4){
         result+=mem[i];
         result+=mem[i+BLOCK_SIZE];
         result+=mem[i+2*BLOCK_SIZE];
         result+=mem[i+3*BLOCK_SIZE];
    }
}

El desenrollado de 2, 3, 4, 6 u 8 iteraciones proporciona los resultados a continuación. Tenga en cuenta que no corregí los bloques al final del vector que se ignoraron debido al desenrollado. Por lo tanto, los picos periódicos en la línea azul deben ignorarse, la línea de base del límite inferior del patrón periódico es el ancho de banda real.

Como puede ver, la fracción de las predicciones erróneas de las ramas no cambió realmente, pero como el número de sucursales se reduce por el factor de las iteraciones sin enrollar, ya no contribuirán en gran medida al rendimiento.

También hay un beneficio adicional de que el procesador sea más libre para realizar los cálculos fuera de orden si el bucle se desenrolla.

Si se supone que esto tiene una aplicación práctica, sugeriría intentar darle al bucle activo un número fijo de iteración en tiempo de compilación o alguna garantía de divisibilidad, de modo que (quizás con algunas sugerencias adicionales) el compilador pueda decidir el número óptimo de iteraciones para desenrollar.

Answer 2

Puede que no esté relacionado, pero su máquina Linux puede jugar con la frecuencia de la CPU. Sé que Ubuntu 18 tiene un gouverner que está equilibrado entre potencia y rendimiento. También desea jugar con la afinidad del proceso para asegurarse de que no se migre a un núcleo diferente mientras se ejecuta.