Причина за свиване на честотната лента на паметта, когато 2KB данни са кеширани в L1-кеша

В проект за самообучение измервам честотната лента на паметта с помощта на следния код (тук перифразиран, целият код следва в края на въпроса):

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 се избира по такъв начин, че цял 64-байтов кеш ред се извлича за едно цяло число-добавяне. Моята машина (Intel-Broadwell) се нуждае от около 0,35 наносекунди за добавяне на цяло число, така че кодът по-горе може да насити честотна лента до 182GB/s (тази стойност е само горна граница и вероятно е доста отклонена, важното е съотношение на честотните ленти за различни размери). Кодът е компилиран с g++ и -O3.

Променяйки размера на вектора, мога да наблюдавам очакваните честотни ленти за L1(*)-, L2-, L3-кешове и RAM-паметта:

Има обаче ефект, който наистина се боря да обясня: срив на измерената честотна лента на L1-кеша за размери около 2 kB, тук в малко по-висока резолюция:

Бих могъл да възпроизведа резултатите на всички машини, до които имам достъп (които имат процесори Intel-Broadwell и Intel-Haswell).

Моят въпрос: Каква е причината за срива на производителността за размер на паметта около 2 KB?

(*) Надявам се, че разбирам правилно, че за L1-кеша не се четат/прехвърлят 64 байта, а само 4 байта на добавяне (няма допълнителен по-бърз кеш, където редът на кеша трябва да бъде попълнен), така че начертаната честотна лента за L1 е само горната граница, а не самата пропускателна способност.

Редактиране: Когато размерът на стъпката във вътрешния for-цикъл е избран да бъде

• 8 (вместо 16) колапсът се случва за 1KB
• 4 (вместо 16) колапсът се случва за 0,5KB

когато вътрешният цикъл се състои от около 31-35 стъпки/четения. Това означава, че колапсът не се дължи на размера на паметта, а на броя на стъпките във вътрешния цикъл.

Може да се обясни с пропуски на клонове, както е показано в страхотния отговор на @user10605163.

Списък за възпроизвеждане на резултатите

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()

Изграждане/пускане/създаване на отчет:

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