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

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

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

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

Answer 2

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

Существует, конечно, множество информации по этой теме, см., Например, this wikipedia entry on locality of reference. Или, я думаю, ваш собственный учебник по курсу. :)

Answer 3

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

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

Answer 4

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

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

Answer 5

Существует очень хорошая бумага Ульриха Дреппера из Red Hat и glibc fame, What Every Programmer Should Know About Memory. В одном разделе подробно обсуждались тайники. Например, в системах SMP есть кеш-эффекты, в которых процессоры могут в конечном итоге испортить владение модифицированной строкой кэша взад и вперед, что сильно вредит производительности.