Доступ к памяти Haswell

Я экспериментировал с наборами инструкций AVX -AVX2, чтобы увидеть производительность потоковой передачи по последовательным массивам. Итак, у меня есть пример, где я читаю и сохраняю основную память.

#include <iostream>
#include <string.h>
#include <immintrin.h>
#include <chrono>
const uint64_t BENCHMARK_SIZE = 5000;

typedef struct alignas(32) data_t {
  double a[BENCHMARK_SIZE];
  double c[BENCHMARK_SIZE];
  alignas(32) double b[BENCHMARK_SIZE];
}
data;

int main() {
  data myData;
  memset(&myData, 0, sizeof(data_t));

  auto start = std::chrono::high_resolution_clock::now();

  for (auto i = 0; i < std::micro::den; i++) {
    for (uint64_t i = 0; i < BENCHMARK_SIZE; i += 1) {
      myData.b[i] = myData.a[i] + 1;
    }
  }
  auto end = std::chrono::high_resolution_clock::now();
  std::cout << (end - start).count() / std::micro::den << " " << myData.b[1]
            << std::endl;
}

И после компиляции с  g++ - 4.9 -ggdb -march = core-avx2 -std = С++ 11 struct_of_arrays.cpp -O3 -o struct_of_arrays

Я вижу неплохую инструкцию для каждого цикла производительности и таймингов для эталонного размера 4000. Однако, как только я увеличиваю размер теста до 5000, я вижу, что инструкция за такт значительно падает, а также латентные прыжки. Теперь мой вопрос: хотя я вижу, что ухудшение производительности похоже, связано с кешем L1, я не могу объяснить, почему это происходит так внезапно.

Чтобы дать больше понимания, если я запустил perf с Benchmark размером 4000 и 5000

| Event                               | Size=4000 | Size=5000 |
|-------------------------------------+-----------+-----------|
| Time                                |    245 ns |    950 ns |
| L1 load hit                         |    525881 |    527210 |
| L1 Load miss                        |     16689 |     21331 |
| L1D writebacks that access L2 cache |   1172328 | 623710387 |
| L1D Data line replacements          |   1423213 | 624753092 |

Итак, мой вопрос заключается в том, почему это происходит, учитывая, что haswell должен быть способен читать 2 * 32 байта, а 32 байта хранить каждый цикл?

РЕДАКТИРОВАТЬ 1

Я понял с помощью этого кода gcc решительно устраняет обращения к myData.a, так как он установлен в 0. Чтобы этого избежать, я сделал еще один тест, который немного отличается, где явно задано значение.

#include <iostream>
#include <string.h>
#include <immintrin.h>
#include <chrono>
const uint64_t BENCHMARK_SIZE = 4000;

typedef struct alignas(64) data_t {
  double a[BENCHMARK_SIZE];
  alignas(32) double c[BENCHMARK_SIZE];

  alignas(32) double b[BENCHMARK_SIZE];

}
data;

int main() {
  data myData;
  memset(&myData, 0, sizeof(data_t));
  std::cout << sizeof(data) << std::endl;
  std::cout << sizeof(myData.a) << " cache lines " << sizeof(myData.a) / 64
            << std::endl;
  for (uint64_t i = 0; i < BENCHMARK_SIZE; i += 1) {
    myData.b[i] = 0;
    myData.a[i] = 1;
    myData.c[i] = 2;
  }

  auto start = std::chrono::high_resolution_clock::now();
  for (auto i = 0; i < std::micro::den; i++) {
    for (uint64_t i = 0; i < BENCHMARK_SIZE; i += 1) {
      myData.b[i] = myData.a[i] + 1;  
    }
  }
  auto end = std::chrono::high_resolution_clock::now();
  std::cout << (end - start).count() / std::micro::den << " " << myData.b[1]
            << std::endl;
}

Второй пример будет иметь один считываемый массив и другой массив. И этот продукт производит следующий выход для разных размеров:

| Event          | Size=1000   | Size=2000   | Size=3000   | Size=4000     |
|----------------+-------------+-------------+-------------+---------------|
| Time           | 86  ns      | 166 ns      | 734 ns      | 931    ns     |
| L1 load hit    | 252,807,410 | 494,765,803 | 9,335,692   | 9,878,121     |
| L1 load miss   | 24,931      | 585,891     | 370,834,983 | 495,678,895   |
| L2 load hit    | 16,274      | 361,196     | 371,128,643 | 495,554,002   |
| L2 load miss   | 9,589       | 11,586      | 18,240      | 40,147        |
| L1D wb acc. L2 | 9,121       | 771,073     | 374,957,848 | 500,066,160   |
| L1D repl.      | 19,335      | 1,834,100   | 751,189,826 | 1,000,053,544 |

Снова такая же картина рассматривается, как указано в ответе, с увеличением данные размера набора данных больше не вписываются в L1, а L2 становится узким местом. Что также интересно, что предварительная выборка, похоже, не помогает, а L1 пропускает значительно увеличивается. Хотя, я ожидал бы увидеть как минимум 50-процентный рейтинг хитов, учитывая, что каждая строка кэша, привезенная в L1, для чтения будет хитом для второго доступа (64 байта строки байта 32 байта считывается с каждой итерацией). Однако, как только набор данных переливается на L2, кажется, что L1 снизился до 2%. Учитывая, что массивы не перекрываются с размером кеша L1, это не должно быть из-за конфликтов кэша. Поэтому эта часть мне все же не имеет смысла.

Ответы

Ответ 1

Резюме:
Различные уровни кэша могут поддерживать разную пиковую пропускную способность для одной и той же базовой нагрузки, поэтому наличие наборов данных различного размера может значительно повлиять на производительность.

Более длинное объяснение:
Это не удивительно, учитывая, что Хасуэлл, согласно этой статье, например. может

поддерживать 2 нагрузки и 1 магазин за цикл

но только сказанное относится к L1. Если вы читаете, вы увидите, что L2

может предоставить полную строку 64B для кэша данных или команд в каждом цикле

Поскольку для каждой итерации вам требуется одна загрузка и одно хранилище, наличие набора данных в L1 позволит вам наслаждаться пропускной способностью L1 и, возможно, достигать пропускной способности цикла за итерацию, тогда как набор данных перейдет на L2 заставит вас ждать дольше. Это зависит от того, насколько большой двойник в вашей системе, но ваши результаты указывают на то, что он, вероятно, 32 бит, поэтому 4000 * 2 массива * 4 байта = 32k, именно размер L1 и 5000 превышают это.

Теперь есть две вещи, которые происходят, когда вы начинаете превышать следующий уровень кеша:

  • L1-writebacks. Обратите внимание, что в статье не упоминаются обратные записи, которые являются дополнительным штрафом, который вы должны платить с точки зрения пропускной способности (как видно из вашей производительности), хотя он выглядит немного крутым). Наличие данных, содержащихся в L1, означает, что вам не нужно делать никаких выселений вообще, а некоторые данные в L2 означают, что каждая строка, считанная с L2, должна была бы выкинуть существующую строку из L1, половина из которых была изменена ваш код и требуют явных обратных ссылок. Эти транзакции должны были бы превышать значения для двух элементов данных, которые вы используете для каждой итерации, - помните, что хранилище также должно сначала прочитать старые данные, так как часть строки не используется и требует слияния.

  • Политика замены кэша - обратите внимание, что поскольку кеш устанавливается ассоциативно и, скорее всего, использует схему LRU, и, поскольку вы последовательно переходите к своим массивам, ваш пример использования кэша, вероятно, будет заполняться первый ассоциативный способ, затем переход ко второму пути и т.д. - к тому времени, когда вы заполните последний способ, если в L2 все еще нужны данные (в случае большего набора данных), вы, вероятно, выселите все линии с первого взгляда, так как они являются наименее недавно используемыми, хотя это также означает, что они будут теми, которые вы собираетесь использовать дальше. Это недостаток LRU с наборами данных, большими, чем кеш.

Это объясняет, почему падение производительности настолько неожиданно из-за этого шаблона доступа, как только вы превысите размер кэша, по крайней мере, на размер одного пути (1/8 часть кэша L1).

Один последний комментарий о первичном результате - вы бы ожидали, что скорость попадания L1 упадет до хорошего раунда нуля для случая с 5000 элементами, что я считаю. Тем не менее, предварительная выборка HW может заставить вас выглядеть так, как будто вы все еще попадаете в нее в L1, когда она проходит впереди фактических данных. Вам все равно придется ждать, пока эти предварительные данные не приведут данные, и что еще более важно, поскольку вы измеряете полосу пропускания - они по-прежнему занимают такую ​​же полосу пропускания, что и фактические нагрузки/хранилища, но они не учитываются первыми, что заставляет вас поверить у вас был L1. Это, по крайней мере, мое лучшее предположение - вы можете проверить это, отключив предварительные выборки и снова измерив (я, кажется, слишком часто даю этот совет, извините за то, что вы так перетаскиваете).

РЕДАКТИРОВАТЬ 1 (после вашего)

Отличный выбор об устраненном массиве, который решает загадку о двойном размере - это действительно 64 бит, поэтому либо один массив из 4000 элементов, либо 2 массива из 2000 элементов каждый (после вашего исправления) - это столько, сколько вы можете поместиться в L1. Теперь разлив происходит на 3000 элементов. Сейчас уровень L1 был низким, так как L1 не мог выдавать достаточные предварительные данные, чтобы бегать впереди ваших двух разных потоков.

Что касается ожидания того, что каждая загрузка приведет к 64-байтной строке для двух итераций - я вижу что-то весьма интересное - если вы суммируете количество загружаемых из памяти единиц (L1 hits + L1 misses) Посмотрим, что случай с элементами 2000 года почти в точности равен 2x из 1000 элементов, но 3000 и 4000 случаев не 3x и 4x соответственно, а половина. В частности, с 3000 элементами на массив у вас меньше доступа, чем у вас с 2000 элементами!
Это заставляет меня подозревать, что блок памяти способен объединить каждую из двух нагрузок в один доступ к памяти, но только при переходе на L2 и далее. Это имеет смысл, если вы думаете об этом, нет причин выпускать другой доступ для поиска L2, если у вас уже есть одна очередь для этой линии, и это приемлемый способ уменьшить пропускную способность на этом уровне. Я предполагаю, что по какой-то причине вторая загрузка даже не учитывается тогда как поиск L1, и не помогает получить скорость попадания, которую вы хотели видеть (вы могли проверить счетчики, указывающие, сколько нагрузок проходит выполнение - это должно, вероятно, будь настоящим). Это просто догадка, хотя я не уверен, как определяется счетчик, но он соответствует количеству доступных нам доступов.