Как работает кеш-память?

Question

Сегодня, когда я учился в компьютерном классе, учитель говорил о чем-то интересном для меня. Когда речь зашла о том, почему работает кеш-память, он сказал, что:

for (i=0; i<M; i++)
   for(j=0; j<N; j++)
      X[i][j] = X[i][j] + K; //X is double(8 bytes)

Нельзя менять первую строку на вторую. Что вы думаете об этом? И почему это так?

Answer 1

Ульрих Дреппер из Red Hat и glibc Fame написал очень хорошую статью, Что каждый программист должен знать о памяти . В одном разделе обсуждались кеши очень подробно. Например, в системах SMP существуют эффекты кеширования, когда процессоры могут в конечном итоге перебивать владение измененной строкой кеша взад и вперед, что значительно снижает производительность.

Answer 2

Местонахождение ссылки. Поскольку данные хранятся по строкам, для каждой строки столбцы j находятся в соседних адресах памяти. ОС обычно загружает всю страницу из памяти в кэш, и ссылки на соседние адреса, вероятно, ссылаются на эту же страницу. Если вы увеличиваете на индекс строки во внутреннем цикле, возможно, что эти строки будут на разных страницах (так как они разделены j, удваивается каждая), и кэшу, возможно, придется постоянно вводить и выбрасывать страницы памяти, на которые он ссылается данные. Это называется избиением и ухудшает производительность.

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

[РЕДАКТИРОВАТЬ] Ответ выше специфичен для C и может отличаться для других языков. Единственное, что я знаю, отличается от Фортрана. FORTRAN хранит вещи в главном порядке столбца (выше - основной ряд), и было бы правильно изменить порядок операторов в FORTRAN. Если вы хотите / нуждаетесь в эффективности, важно знать, как ваш язык реализует хранение данных.

Answer 3

Это похоже на то, что тайники как местность. Одно и то же количество доступной памяти, но расположенное дальше друг от друга, попадет в разные «строки» кеша или может вообще пропустить кеш. Поэтому хорошо, когда у вас есть выбор, организовать данные таким образом, чтобы доступы, которые могут происходить близко друг к другу во времени, также делались в пространстве. Это увеличивает вероятность попадания в кэш и повышает производительность.

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

Answer 4

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

do jj = 1,N
  do ii = 1,M
    x(ii,jj) = x(ii,jj) + K;
  enddo
enddo

Answer 5

Кэш-память - это очень быстрая и очень дорогая память, которая находится рядом с процессором. Вместо того, чтобы каждый раз получать один маленький фрагмент данных из ОЗУ, ЦП выбирает кусок данных и сохраняет его в кеше. Ставка на то, что если вы просто прочитаете один байт, то следующий прочитанный байт, вероятно, будет сразу после него. Если это так, то он может прийти из кеша.

Располагая ваш цикл так, как он есть, вы читаете байты в порядке их сохранения в памяти. Это означает, что они находятся в кэше и могут быть очень быстро прочитаны процессором. Если вы поменялись местами в строках 1 и 2, то вы будете читать каждый «N» байт каждый раз в цикле. Читаемые вами байты больше не являются последовательными в памяти, поэтому они могут отсутствовать в кэше. Процессор должен получать их из (более медленной) оперативной памяти, и поэтому ваша производительность снижается.