Причина падения пропускной способности памяти при кэшировании 2 КБ данных в 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 наносекунды на целочисленное добавление, поэтому приведенный выше код может насыщать полосу пропускания до 182 ГБ/с (это значение является лишь верхней границей и, вероятно, вполне отключено, важно то, что соотношение полос пропускания для разных размеров). Код скомпилирован с g++ и -O3.

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

Однако есть эффект, который я действительно изо всех сил пытаюсь объяснить: коллапс измеренной полосы пропускания L1-кэша для размеров около 2 кБ, здесь в несколько более высоком разрешении:

Я мог бы воспроизвести результаты на всех машинах, к которым у меня есть доступ (на которых установлены процессоры Intel-Broadwell и Intel-Haswell).

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

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

Редактировать: когда размер шага во внутреннем цикле for выбран

8 (вместо 16) обвал происходит за 1КБ
4 (вместо 16) обвал происходит за 0.5КБ

т.е. когда внутренний цикл состоит из примерно 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

Ответ 1

Я немного изменил значения: NITER = 100000 и NTRIES=1 чтобы получить менее шумный результат.

У меня сейчас нет Broadwell, но я попробовал ваш код на Coffee-Lake и получил снижение производительности не на 2 КБ, а примерно на 4,5 КБ. Кроме того, я нахожу ошибочное поведение пропускной способности чуть выше 2 КБ.

Синяя линия на графике соответствует вашему измерению (левая ось):

Красная линия здесь - это результат perf stat -e branch-instructions,branch-misses, дающих долю ветвей, которые не были правильно предсказаны (в процентах, правая ось). Как вы можете видеть, между ними существует четкая антикорреляция.

Заглядывая в более подробный perf доклад, я обнаружил, что в основном все эту ошибочность прогнозирования ветвления происходит в самом внутреннем цикле в Worker::operator(). Если взятый/не взятый шаблон для ветки цикла становится слишком длинным, предиктор ветки не сможет отследить его, и поэтому выходная ветвь внутреннего цикла будет ошибочно предсказана, что приведет к резкому падению пропускной способности. При дальнейшем увеличении числа итераций влияние этого единственного неверного прогноза станет менее значительным, что приведет к медленному восстановлению пропускной способности.

Для получения дополнительной информации о нестабильном поведении перед выпадением см. Комментарии, сделанные @PeterCordes ниже.

В любом случае, лучший способ избежать неправильных предсказаний ветвлений - избегать ветвей, поэтому я вручную развернул цикл в Worker::operator(), например, например:

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];
    }
}

Развертывание 2, 3, 4, 6 или 8 итераций дает следующие результаты. Обратите внимание, что я не исправил блоки в конце вектора, которые были проигнорированы из-за развертывания. Поэтому периодические пики в синей линии следует игнорировать, нижняя граница базовой линии периодического шаблона - это фактическая ширина полосы.

Как вы можете видеть, доля неправильных прогнозов ветвей на самом деле не изменилась, но, поскольку общее число ветвей уменьшается из-за коэффициента развернутых итераций, они больше не будут сильно влиять на производительность.

Существует также дополнительное преимущество, заключающееся в том, что процессор более свободен для выполнения вычислений не по порядку, если цикл развернут.

Если предполагается, что это имеет практическое применение, я бы предложил попытаться дать горячему циклу фиксированное число итераций во время компиляции или некоторую гарантию делимости, чтобы (возможно, с некоторыми дополнительными подсказками) компилятор мог выбрать оптимальное число итерации развернуть.

Ответ 1

Ответ 2