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

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

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

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

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

Answer 2

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

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 " байт каждый раз вокруг цикла. Читаемые вами байты больше не являются последовательными в памяти, поэтому они могут отсутствовать в кэше. Процессор должен извлекать их из (более медленной) оперативной памяти, и поэтому ваша производительность снижается.