Оптимизация кэша кода C ++

Question

Это может показаться бессмысленным, но у меня возникают проблемы с оптимизацией фрагмента кода C ++ для нескольких процессоров и кэша.

Кеш важнее многих процессоров: я перебираю 2 вложенных цикла

for(int i=0; i<n; i++){
  //do a little something here with a single array
  for(int j=0; j<whoaAnotherArray[n].size(); j++){
    * access array[i][j] and otherArray[i][j] and store in a variable
       - an example is: "int x = array[i][j] + otherArray[i][j]"
    * compare variable to some other array[index calculated from i and j]
       - an example is: "if (x < yetAnotherArray[i*n+j]){ //do something to yetAnotherArray }"
  }
}

Мои массивы (array и otherArray) имеют очень большой размер. п их размер.

Есть ли способ сделать этот кеш более дружественным? Я уже перешел от использования связанных списков, которые ужасны для кеша. Я где-то читал, что мой порядок доступа [i] [j] также эффективен для кэширования.

FWIW, это часть алгоритма обнаружения цикла с отрицательным весом.

Я подумал, может быть, поскольку мои массивы такие огромные (кстати, это массивы целых чисел), было бы лучше разбить их немного, чтобы они лучше помещались в кеше? Но я не уверен, правильно ли это или нет, как это сделать.

Я также начал использовать openmp. Единственное, что я делал, это добавляю

#pragma omp parallel for

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

Answer 1

Одной из возможностей улучшения использования кэша является изменение схемы доступа к array и otherArray. Когда вы читаете array[i][j], ваша машина, конечно, переместит «строку» памяти в кеш. Когда вы прочитаете otherArray[i][j], ваша машина, конечно же, переместит «строку» памяти в кэш. Возможно, что для чтения второй «строки» первая должна быть сброшена из кэша в ОЗУ. И тогда вы делаете ситуацию еще хуже (потенциально), читая значение из yetAnotherArray.

То, что происходит на самом деле, во многом зависит от того, что еще происходит одновременно, что еще находится в кеше и любых других выполняемых операциях. Это может быть очень трудно понять.

Если ваш (доминирующий) шаблон доступа к массиву требует element[i][j] от обоих (или всех 3) массивов одновременно, то вы хотите расположить вопросы так, чтобы они находились в одной «строке» памяти, которая читать. Один из способов сделать это - объединить 3 массива в один массив m*n*3, в котором superArray[i][j][1] находится рядом с superArray[i][j][2], что рядом с superArray[i][j][3] и в котором каждая из трех плоскостей массива представляет одну оригинальные массивы. Конечно, это работает, только если я правильно упорядочил индекс, поэтому подумайте больше, чем я.

* * 1016 Наконец: * * 1017

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

2. под «линией» я имею в виду любой кусок ваша платформа загружается из ОЗУ в кеш за один раз.

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

Answer 2

Прочитайте эти 2 статьи Херба Саттера, особенно первую

http://www.ddj.com/go-parallel/article/showArticle.jhtml?articleID=217500206

http://ddj.com/architect/208200273

Answer 3

Есть программа под названием Cachegrind (плагин Valgrind), которая может помочь вам профилировать, как ваш код работает с виртуальным кешем.Я бы поработал с этим, чтобы увидеть, как ваш код работает с кешем вашего процессора.(Прошло много времени с тех пор, как я его использовал, поэтому я не помню, может ли он автоматически определять атрибуты кэша вашего ЦП. Возможно, вам потребуется указать точные параметры кэша для вашего ЦП.)

Вытакже можно попробовать несколько оптимизаций, которые в идеале должен выполнять ваш компилятор:

1) Заменить эту строку:

for(int j=0; j<whoaAnotherArray[n].size(); j++){

на:

  int len = whoaAnotherArray[n].size();
  for(int j=0; j<len; j++){

2) Создайте указатели на массивы в вашем внешнем цикле:

int* pArray = array[i] - 1;
int* pOtherArray = pOtherArray[j] - 1;

и используйте преинкременты для доступа к первому указателю в цикле:

int x = *(++pArray) + *(++pOtherArray);

(Да, Я знаю это ужасно. Я знаю компилятор должен был сделать это для вас. Но не так много месяцев назад я обнаружил, что это действительно имеет значение с gcc 4.3 (?) На linux. YMMV.)

3) Если есть какой-либо способ реструктурировать код так, чтобы вы перебрали array за один проход, а затем перебрали otherArray за второй проход, попробуйте это сделать.Кажется маловероятным в вашем случае, но я не знаю.Дело в том, что вы хотите, чтобы доступ к памяти был как можно более сфокусированным для одного массива за раз.

Удачи.