Оптимизация с помощью блокировки цикла в C

Question

В настоящее время я изучаю оптимизацию на языке C, и у меня было предыдущее задание по оптимизации фрагмента кода.Среди других оптимизаций (развертывание циклов и снижение прочности) я использовал блокировку в соответствии с размером кэша (следуя инструкциям Intel по этому вопросу):

https://software.intel.com/en-us/articles/how-to-use-loop-blocking-to-optimize-memory-use-on-32-bit-intel-architecture.

Теперь я думаю, что понимаю, почему этот метод работаетв этом случае, когда шаг равен единице, он загружает в кеш блоки и уменьшает количество пропусков при доступе к следующему месту в памяти.Но в моем коде dst[dim * jj + ii], кажется, перепрыгивает повсюду, так как он умножается на jj в самом внутреннем цикле.Как кеш учитывает это?dim умножается на 0, затем на 1, затем на 2 и т. д., в какой-то момент он превзойдет то, что может удерживать блок, и оптимизация будет бессмысленной.Я правильно понимаю?

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

   void transpose(int *dst, int *src, int dim)
   {
      int i, j, dimi, jj,ii;
      dimi = 0;
      for(i=0; i < dim; i+=block_size)
      {
        for(j=0; j<dim; j+=block_size)
        {
          for(ii = i; ii < i+block_size; ii++)
          {
            dimi = dim * ii;
            for(jj = j; jj < j+block_size; jj++)
            {
              dst[dim*jj + ii] =  src[dimi + jj];
            }
          }
        }
      }
    }

Answer 1

У вас плохая пространственная локальность в dst, но с блокировкой для обоих измерений все еще достаточно локальности во времени и пространстве, вместе взятых, что строки кэша обычно остаются горячими в L1d-кэше, когда вы сохраняете следующую int.

Допустим, dst[dim*jj + ii] - это первое int в строке кэша.Магазин до dst[dim*jj + ii + 1] будет в той же строке кэша.Если эта строка все еще остается горячей в кэше L1d, ЦП не потратил никакой полосы пропускания на удаление грязной строки из L2 и последующего возврата ее в L1d для следующего хранилища.

С блокировкой для обоих измерений этоследующий магазин появится после block_size больше магазинов до dst[ dim*(jj+1..block_size-1) + ii ].(Следующая итерация цикла ii.)

Если dim и block_size являются степенями 2, линия, вероятно, будет удалена из-за конфликтов.Адреса в 4 кБ идут в том же наборе в L1d, хотя проблемный шаг больше для L2.(Кэш-память Intel L1d имеет 32-килобайтный и 8-сторонний набор ассоциаций, так что всего 8 хранилищ к одному и тому же набору, вероятно, вытеснят строку. Но кэш L3 использует хеш-функцию для индексации набора вместо простого по модулю с использованием диапазонанепосредственно из битов адреса. IDK, какой бит у вас в буферах, или вся ваша матрица может оставаться горячей в вашем кэше L3.)

Но если dim или block_size не являются степенью 2, товсе 64 набора по 8 строк по 64 байта (L1d) вступают в игру.Таким образом, в кэше L1d может быть до 64 * 8 = 512 грязных строк.Но помните, что все еще данные загружаются последовательно, и это займет некоторое пространство.(Не так много, потому что вы читаете 16 дюймов подряд из каждой строки загруженных данных и используете это для очистки 16 различных строк данных назначения.)

С блокировкой только в 1 измерении вы 'мы делаем еще много магазинов, прежде чем вернуться к строке назначения, поэтому к тому времени она, вероятно, будет выселена в L2 или, возможно, в L3.

Кстати, я поместил ваш код в проводник компилятора Godbolt (https://godbolt.org/g/g24ehr), и gcc -O3 для x86 не пытается сделать ничего особенного, использует векторную загрузку в регистр XMM, распаковывает с перемешиванием и делает 4 отдельных хранилища int.

clang6.0 делает что-то интересное, включая копирование блока размером 256 байт. IDK, если он делает это для обхода псевдонимов (потому что без int *restrict dst он не знает, что src и dst не перекрываются).

---

Кстати, непрерывные записи и разбросанные чтения, вероятно, были бы лучше (т.е. инвертировали два ваших внутренних цикла, поэтому ii изменяет самый внутренний цикл вместо jj).Че-то строка дороже, чем вычистить чистую строку и просто перечитать ее позже.