Почему кэш называют ассоциативной памятью. Ассоциативная кэш-память

В такой памяти любая строка ОП может находиться в любом месте кэш-памяти, причем в любой комбинации с другими строками. Комбинационные схемы сравнения СС1-СС4 (рис. 6.4) одновременно анализируют все теги строк, находящихся в кэше в данный момент, и сравнивают их с адресом, поступившим с шины адреса от процессора. При кэш-попадании строка считывается в шину данных (ШД). При кэш-промахе происходит замещение строки в кэш-памяти на требуемую строку из ОП.

Преимущество данной памяти в высокой скорости считывания. Недостаток – сложность аппаратной реализации. Поэтому полностью ассоциативная кэш-память чаще всего используется в специализированных буферах, таких, как буфер целевых адресов переходов, с небольшим объемом строк.

3. Множественно-ассоциативная кэш-память

Этот вид памяти является промежуточным между двумя вышерассмотренными. В нем сочетаются простота кэша с прямым отображением и скорость ассоциативного поиска.

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

Если 2 n строк кэша разбивается на 2 s непересекающихся подмножеств, то S младших разрядов оперативной памяти показывают, в каком из подмножеств (индексов) должен вестись ассоциативный поиск. Старшиеn-sразрядов адреса основной памяти являются тегами.

Если S=0, то получим одно подмножество, что соответствует полностью ассоциативной кэш-памяти. Если S=n, то получим 2 n подмножеств (то есть одна строка - одно подмножество). Это кэш-память с прямым отображением. Если 1Sn-1, то имеем множественно-ассоциативную кэш-память.

На рисунке 6.5 приведен пример кэша, где S=1, то есть имеются два подмножества кэш- памяти. Физический адрес 0111, выработанный процессором, разделяется на индекс 1, равный младшему разряду, и тег 011. По индексу выбирается второе подмножество строк в кэш-памяти, а затем происходит ассоциативный поиск среди тегов строк выбранного подмножества. Найденная строка 7 с тегом 011 передается в шину данных (ШД). Ассоциативный поиск производится одновременно по всем тегам с помощью комбинационных схем сравнения СС1 и СС2.

Рис. 6.5. Множественно-ассоциативная кэш-память

В современных процессорах используется 4-х и 8-ми входовая кэш-память. Увеличение числа ее входов приводит к быстрому увеличению сложности аппаратной реализации той части кэша, которая обеспечивает ассоциативный поиск тегов.

Особенности записи и замещения информации в кэш-памяти. Когерентность кэш-памяти

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

При обращении по записи используется два метода: запись производится только в КЭШ или сразу и в КЭШ, и в ОЗУ. Эти методы получили название алгоритмов обратной WB (Write Back) и сквозной записи WT (Write Through) соответственно. Второй из них более простой, но и более медленный, хотя и гарантирует, что копии одной и той же информации в КЭШе и оперативной памяти всегда совпадают. Большинство ранних процессоров Intel используют именно этот алгоритм.

Алгоритм обратной записи WB более быстрый. Передача информации в ОЗУ производится только тогда, когда на место данной строки КЭШа передается строка из другой страницы ОП или при выполнении команды обновления содержимого КЭШа. Этот алгоритм требует более аккуратного управления, поскольку существуют моменты, когда копии одной и той же информации различны в КЭШе и ОП. Кроме того, не каждая строка изменяется за время своего пребывания в КЭШе. Если изменения не было, то нет необходимости переписывать строку обратно в оперативную память. Обычно используют флаг M (modified – изменена) в памяти тэгов. Он сбрасывается в “0” при первоначальной загрузке строки в КЭШ и устанавливается в “1” при записи в нее информации. При выгрузке строки из КЭШа запись в ОП выполняется только при единичном значении флага M.

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

FIFO (First In First Out – первый пришедший – первым выбывает);

LRU (Least Recently Used – дольше других неиспользуемый);

LFU (Least Frequently Used – реже других используемый);

Случайный (random).

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

В алгоритме FIFO для замещения выбирается строка, первой попавшая в КЭШ. Каждая вновь размещаемая в КЭШе строка добавляется в хвост этой очереди. Алгоритм не учитывает фактическое ее использование. Например, первые загруженные строки могут содержать данные, требующиеся на протяжении всей работы. Это приводит к немедленному возвращению к только что замещенной строке.

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

Одним из близких к LRU является алгоритм LFU, согласно которому удаляется наименее часто использовавшаяся строка. При этом необходимо подсчитывать количество обращений к каждой строке и контролировать его. Может оказаться, что наименее интенсивно используется та строка, которая только что записана в КЭШ-память и к которой успели обратиться только один раз (в то время как к другим строкам обращались больше). Она может быть удалена, что является недостатком алгоритма LFU.

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

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

За счет чего же мы наблюдаем постоянный рост производительности однопоточных программ? В данный момент мы находимся на той ступени развития микропроцессорных технологий, когда прирост скорости работы однопоточных приложений зависит только от памяти. Количество ядер растет, но частота зафиксировалась в пределах 4 ГГц и не дает прироста производительности.

Скорость и частота работы памяти - это то основное за счет чего мы получаем «свой кусок бесплатного торта» (ссылка). Именно поэтому важно использовать память, настолько эффективно, насколько мы можем это делать, а тем более такую быструю как кэш. Для оптимизации программы под конкретный компьютер, полезно знать характеристики кэш-памяти процессора: количество уровней, размер, длину строки. Особенно это важно в высокопроизводительном коде - ядра систем, математические библиотеки.

Как же определить характеристики кэша автоматический? (естественно cpuinfo распарсить не считается, хотя-бы потому-что в конечном итоге мы бы хотели получить алгоритм, который можно без труда реализовать в других ОС. Удобно, не правда ли?) Именно этим мы сейчас и займемся.

Немного теории

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

Кэш с прямым отображением (direct mapping cache)

- данная строка ОЗУ может быть отображена в единственную строку кэша, но в каждую строку кэша может быть отображено много возможных строк ОЗУ.

Ассоциативный кэш (fully associative cache)

- любая строка ОЗУ может быть отображена в любую строку кэша.

Множественно-ассоциативный кэш

- кэш-память делится на несколько «банков», каждый из которых функционирует как кэш с прямым отображением, таким образом строка ОЗУ может быть отображена не в единственную возможную запись кэша (как было бы в случае прямого отображения), а в один из нескольких банков; выбор банка осуществляется на основе LRU или иного механизма для каждой размещаемой в кэше строки.

LRU - вытеснение самой «долго не использованной» строки, кэш памяти.

Идея

Чтобы определить количество уровней кэша нужно рассмотреть порядок обращений к памяти, на котором будет четко виден переход. Разные уровни кэша отличаются прежде всего скоростью отклика памяти. В случае «кэш-промаха» для кэша L1 будет произведен поиск данных в следующих уровнях памяти, при этом если размер данных больше L1 и меньше L2 - то скоростью отклика памяти будет скорость отклика L2. Предыдущее утверждение так же верно в общем случаи.

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

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

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

Ассоциативный кэш

Как только размер данных превышает размер кэш-памяти,
полностью ассоциативный кэш «промахивается» при каждом обращении к памяти.

Прямой кэш

Рассмотрим разные размеры строк. - показывает максимальное количество промахов, которое потратит процессор для доступа к элементам массива при следующем проходе по строке.

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

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

Если-же говорить о памяти - то самая быстрая это кэш, следом идет оперативная, самая медленная это swap, про него мы в дальнейшем говорить не будем. В свою очередь у разных уровней кэша (как правило сегодня процессоры имеют 2-3 уровня кэша) разная скорость отклика памяти: чем больше уровень, тем меньше скорость отклика. И поэтому, если строка помещается в первый уровень кэша, (который кстати полностью ассоциативный) время отклика будет меньше, чем у строки значительно превышающей размеры кэша первого уровня. По-этому на графике времени отклика памяти от размеров строки будет несколько плато - плато* отклика памяти, и плато вызванные различными уровнями кэша.

*Плато функции - { i:x, f(xi) - f(xi+1) < eps: eps → 0 }

Приступим к реализации

Для реализации будем использовать Си (ANSI C99).

Быстро написан код, обычный проход по строкам разной длины, меньше 10мб, выполняющийся многократно. (Будем приводить небольшие куски программы, несущие смысловую нагрузку).

For (i = 0; i < 16; i++) { for (j = 0; j < L_STR; j++) A[j]++; }

Смотрим на график - и видим одну большую ступеньку. Но ведь в теории получается все, просто замечательно. Стало быть нужно понять: из за чего это происходит? И как это исправить?

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

Дело в том, что сегодня далеко не топовые процессоры, помимо принципа пространственной локальности, предсказывают также и арифметическую прогрессию в порядке обращения к памяти. Поэтому нужно рандомизовать обращения к памяти.

Длина рандомизованного массива должна быть сопоставимой с длиной основной строки, чтобы избавиться от большой гранулярности обращений, так же длина массива не должна быть степенью двойки, из-за этого происходили «наложения» - следствием чего могут - быть выбросы. Лучше всего задать гранулярность константно, в том числе, если гранулярность простое число, то можно избежать эффектов наложений. А длина рандомиованого массива - функция от длинны строки.
for (i = 0; i < j; i++) { for (m = 0; m < L; m++) { for (x = 0; x < M; x++){ v = A[ random[x] + m ]; } } }

После чего мы удивили столь долгожданную «картинку», о которой говорили в начале.

Программа разбита на 2 части - тест и обработка данных. Написать скрипт в 3 строки для запуска или 2 раза запустить ручками решайте сами.

Листинг файла size.с Linux

#include #include #include #include #define T char #define MAX_S 0x1000000 #define L 101 volatile T A; int m_rand; int main (){ static struct timespec t1, t2; memset ((void*)A, 0, sizeof (A)); srand(time(NULL)); int v, M; register int i, j, k, m, x; for (k = 1024; k < MAX_S;) { M = k / L; printf("%g\t", (k+M*4)/(1024.*1024)); for (i = 0; i < M; i++) m_rand[i] = L * i; for (i = 0; i < M/4; i++) { j = rand() % M; x = rand() % M; m = m_rand[j]; m_rand[j] = m_rand[i]; m_rand[i] = m; } if (k < 100*1024) j = 1024; else if (k < 300*1024) j = 128; else j = 32; clock_gettime (CLOCK_PROCESS_CPUTIME_ID, &t1); for (i = 0; i < j; i++) { for (m = 0; m < L; m++) { for (x = 0; x < M; x++){ v = A[ m_rand[x] + m ]; } } } clock_gettime (CLOCK_PROCESS_CPUTIME_ID, &t2); printf ("%g\n",1000000000. * (((t2.tv_sec + t2.tv_nsec * 1.e-9) - (t1.tv_sec + t1.tv_nsec * 1.e-9)))/(double)(L*M*j)); if (k >

Листинг файла size.с Windows

#include #include #include #include #include #include using namespace std; #define T char #define MAX_S 0x1000000 #define L 101 volatile T A; int m_rand; int main (){ LARGE_INTEGER freq; LARGE_INTEGER time1; LARGE_INTEGER time2; QueryPerformanceFrequency(&freq); memset ((void*)A, 0, sizeof (A)); srand(time(NULL)); int v, M; register int i, j, k, m, x; for (k = 1024; k < MAX_S;) { M = k / L; printf("%g\t", (k+M*4)/(1024.*1024)); for (i = 0; i < M; i++) m_rand[i] = L * i; for (i = 0; i < M/4; i++) { j = rand() % M; x = rand() % M; m = m_rand[j]; m_rand[j] = m_rand[i]; m_rand[i] = m; } if (k < 100*1024) j = 1024; else if (k < 300*1024) j = 128; else j = 32; QueryPerformanceCounter(&time1); for (i = 0; i < j; i++) { for (m = 0; m < L; m++) { for (x = 0; x < M; x++){ v = A[ m_rand[x] + m ]; } } } QueryPerformanceCounter(&time2); time2.QuadPart -= time1.QuadPart; double span = (double) time2.QuadPart / freq.QuadPart; printf ("%g\n",1000000000. * span/(double)(L*M*j)); if (k > 100*1024) k += k/16; else k += 4*1024; } return 0; }

В общем- то думаю все понятно, но хотелось бы оговорить несколько моментов.

Массив A объявлен как volatile - эта директива гарантирует нам что к массиву A всегда будут обращения, то-есть их не «вырежут» ни оптимизатор, ни компилятор. Так-же стоит оговорить то что вся вычислительная нагрузка выполняется до замера времени, что позволяет нам, уменьшить фоновое влияние.

Файл переведен в ассемблер на Ubuntu 12.04 и компилятором gcc 4.6 - циклы сохраняются.

Обработка данных

Для обработки данных логично использовать производные. И несмотря на то что с повышением порядка дифференцирования шумы возрастают, будет использована вторая производная и её свойства. Как бы не была зашумлена вторая производная, нас интересует лишь знак второй производной.

Находим все точки, в которых вторая производная больше нуля (с некоторой погрешностью потому-что вторая производная, помимо того что считается численно, - сильно зашумлена). Задаем функцию зависимости знака второй производной функции от размера кэша. Функция принимает значение 1 в точках, где знак второй производной больше нуля, и ноль, если знак второй производной меньше или равен нулю.

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

Листинг файла data_pr.с
#include #include #include double round (double x) { int mul = 100; if (x > 0) return floor(x * mul + .5) / mul; else return ceil(x * mul - .5) / mul; } float size, time, der_1, der_2; int main(){ size = 0; time = 0; der_1 = 0; der_2 = 0; int i, z = 110; for (i = 1; i < 110; i++) scanf("%g%g", &size[i], &time[i]); for (i = 1; i < z; i++) der_1[i] = (time[i]-time)/(size[i]-size); for (i = 1; i < z; i++) if ((time[i]-time)/(size[i]-size) > 2) der_2[i] = 1; else der_2[i] = 0; //comb for (i = 0; i < z; i++) if (der_2[i] == der_2 && der_2 != der_2[i]) der_2 = der_2[i]; for (i = 0; i < z-4; i++) if (der_2[i] == der_2 && der_2[i] != der_2 && der_2[i] != der_2) { der_2 = der_2[i]; der_2 = der_2[i]; } for (i = 0; i < z-4; i++) if (der_2[i] == der_2 && der_2[i] != der_2 && der_2[i] != der_2 && der_2[i] != der_2) { der_2 = der_2[i]; der_2 = der_2[i]; der_2 = der_2[i]; } // int k = 1; for (i = 0; i < z-4; i++){ if (der_2[i] == 1) printf("L%d = %g\tMb\n", k++, size[i]); while (der_2[i] == 1) i++; } return 0; }

Тесты

CPU/ОС/версия ядра/компилятор/ключи компиляции - будут указаны для каждого теста.

Intel Pentium CPU P6100 @2.00GHz / Ubuntu 12.04 / 3.2.0-27-generic / gcc -Wall -O3 size.c -lrt
L1 = 0.05 Mb
L2 = 0.2 Mb
L3 = 2.7 Mb
Не буду приводить все хорошие тесты, давайте лучше поговорим о «Граблях»

Давайте поговорим о «граблях»

Грабля обнаружилась при обработке данных на серверном процессоре Intel Xeon 2.4/L2 = 512 кб/Windows Server 2008

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

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

Хотелось бы услышать ваши предложения, по поводу решения этой проблемы.

Список литературы

Макаров А.В. Архитектура ЭВМ и Низкоуровневое программирование.
Ulrich Drepper What every programmer should know about memory

Немного теории

Кэш с прямым отображением (direct mapping cache)

Ассоциативный кэш (fully associative cache)

- любая строка ОЗУ может быть отображена в любую строку кэша.

Множественно-ассоциативный кэш

LRU - вытеснение самой «долго не использованной» строки, кэш памяти.

Идея

Ассоциативный кэш

Прямой кэш

*Плато функции - { i:x, f(xi) - f(xi+1) < eps: eps → 0 }

Приступим к реализации

Для реализации будем использовать Си (ANSI C99).

For (i = 0; i < 16; i++) { for (j = 0; j < L_STR; j++) A[j]++; }

После чего мы удивили столь долгожданную «картинку», о которой говорили в начале.

Листинг файла size.с Linux

Листинг файла size.с Windows

В общем- то думаю все понятно, но хотелось бы оговорить несколько моментов.

Файл переведен в ассемблер на Ubuntu 12.04 и компилятором gcc 4.6 - циклы сохраняются.

Обработка данных

Тесты

CPU/ОС/версия ядра/компилятор/ключи компиляции - будут указаны для каждого теста.

Intel Pentium CPU P6100 @2.00GHz / Ubuntu 12.04 / 3.2.0-27-generic / gcc -Wall -O3 size.c -lrt
L1 = 0.05 Mb
L2 = 0.2 Mb
L3 = 2.7 Mb
Не буду приводить все хорошие тесты, давайте лучше поговорим о «Граблях»

Давайте поговорим о «граблях»

Грабля обнаружилась при обработке данных на серверном процессоре Intel Xeon 2.4/L2 = 512 кб/Windows Server 2008

Хотелось бы услышать ваши предложения, по поводу решения этой проблемы.

Список литературы

Макаров А.В. Архитектура ЭВМ и Низкоуровневое программирование.
Ulrich Drepper What every programmer should know about memory

В ассоциативной памяти элементы выбираются не по адресу, а по содержимому. Поясним последнее понятие более подробно. Для памяти с адресной организацией было введено понятие минимальной адресуемой единицы (МАЕ) как порции данных, имеющей индивидуальный адрес. Введем аналогичное понятие для ассоциативной памяти , и будем эту минимальную единицу хранения в ассоциативной памяти называть строкой ассоциативной памяти (СтрАП). Каждая СтрАП содержит два поля: поле тега (англ. tag - ярлык, этикетка, признак) и поле данных. Запрос на чтение к ассоциативной памяти словами можно выразить следующим образом: выбрать строку (строки), у которой (у которых) тег равен заданному значению.

Особо отметим, что при таком запросе возможен один из трех результатов:

имеется в точности одна строка с заданным тегом;
имеется несколько строк с заданным тегом;
нет ни одной строки с заданным тегом.

Поиск записи по признаку - это действие, типичное для обращений к базам данных, и поиск в базе зачастую чвляется ассоциативным поиском. Для выполнения такого поиска следует просмотреть все записи и сравнить заданный тег с тегом каждой записи. Это можно сделать и при использовании для хранения записей обычной адресуемой памяти (и понятно, что это потребует достаточно много времени - пропорционально количеству хранимых записей!). Об ассоциативной памяти говорят тогда, когда ассоциативная выборка данных из памяти поддержана аппаратно. При записи в ассоциативную память элемент данных помещается в СтрАП вместе с присущим этому элементу тегом. Для этого можно использовать любую свободную СтрАП. Рассмотрим разновидности структурной организации КЭШ-памяти или способы отображения оперативной памяти на КЭШ .

Полностью ассоциативный КЭШ

Схема полностью ассоциативного КЭШа представлена на рисунке (см. рисунок ниже).

Опишем алгоритм работы системы с КЭШ-памятью. В начале работы КЭШ-память пуста. При выполнении первой же команды во время выборки ее код, а также еще несколько соседних байтов программного кода, - будут перенесены (медленно) в одну из строк КЭШа, и одновременно старшая часть адреса будет записана в соответствующий тег. Так происходит заполнение КЭШ-строки.

Если следующие выборки возможны из этого участка, они будут сделаны уже из КЭШа (быстро) - "КЭШ-попадание". Если же окажется, что нужного элемента в КЭШе нет, - "КЭШ-промахом". В этом случае обращение происходит к ОЗУ (медленно), и при этом одновременно заполняется очередная КЭШ-строка.

Схема полностью ассоциативной КЭШ-памяти

Обращение к КЭШу происходит следующим образом. После формирования исполнительного адреса его старшие биты, образующие тег, аппаратно (быстро) и одновременно сравниваются с тегами всех КЭШ-строк. При этом возможны только две ситуации из трех, перечисленных ранее: либо все сравнения дадут отрицательный результат (КЭШ-промах), либо положительный результат сравнения будет зафиксирован в точности для одной строки (КЭШ-попадание).

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

Если произошел КЭШ-промах, а в КЭШе нет свободных строк, необходимо заменить одну строку КЭШа на другую строку.

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

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

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

Наиболее эффективным является алгоритм замещения на основе наиболее давнего использования (LRU - Least Recently Used ), при котором замещается та строка КЭШ-памяти, к которой дольше всего не было обращения. Проводившиеся исследования показали, что алгоритм LRU, который "смотрит" назад, работает достаточно хорошо в сравнении с оптимальным алгоритмом, "смотрящим" вперед.

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

Второй способ реализуется с помощью очереди, куда в порядке заполнения строк КЭШ-памяти заносятся ссылки на эти строки. При каждом обращении к строке ссылка на нее перемещается в конец очереди. В итоге первой в очереди каждый раз оказывается ссылка на строку, к которой дольше всего не было обращений. Именно эта строка прежде всего и заменяется.

Другой возможный алгоритм замещения - алгоритм, работающий по принципу "первый вошел, первый вышел" (FIFO - First In First Out ). Здесь заменяется строка, дольше всего находившаяся в КЭШ-памяти. Алгоритм легко реализуется с помощью рассмотренной ранее очереди, с той лишь разницей, что после обращения к строке положение соответствующей ссылки в очереди не меняется.

Еще один алгоритм - замена наименее часто использовавшейся строки (LFU - Least Frequently Used). Заменяется та строка в КЭШ-памяти, к которой было меньше всего обращений. Принцип можно воплотить на практике, связав каждую строку со счетчиком обращений, к содержимому которого после каждого обращения добавляется единица. Главным претендентом на замещение является строка, счетчик которой содержит наименьшее число.

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

Кроме тега и байтов данных в КЭШ-строке могут содержаться дополнительные служебные поля, среди которых в первую очередь следует отметить бит достоверности V (от valid - действительный имеющий силу) и бит модификации M (от modify - изменять, модифицировать). При заполнении очередной КЭШ-строки V устанавливается в состояние "достоверно", а M - в состояние "не модифицировано". В случае, если в ходе выполнения программы содержимое данной строки было изменено, переключается бит M, сигнализируя о том, что при замене данной строки ее содержимое следует переписать в ОЗУ. Если по каким-либо причинам произошло изменение копии элемента данной строки, хранимого в другом месте (например в ОЗУ), переключается бит V. При обращении к такой строке будет зафиксирован КЭШ-промах (несмотря на то, что тег совпадает), и обращение произойдет к основному ОЗУ. Кроме того, служебное поле может содержать биты, поддерживающие алгоритм LRU.

Оценка объема оборудования

Типовой объем КЭШ-памяти в современной системе - 8…1024 кбайт, а длина КЭШ-строки 4…32 байт. Дальнейшая оценка делается для значений объема КЭШа 256 кбайт и длины строки 32 байт, что характерно для систем с процессорами Pentium и PentiumPro. Длина тега при этом равна 27 бит, а количество строк в КЭШе составит 256К/ 32=8192. Именно столько цифровых компараторов 27 битных кодов потребуется для реализации вышеописанной структуры.

Приблизительная оценка затрат оборудования для построения цифрового компаратора дает значение 10 транз/бит, а общее количество транзисторов только в блоке компараторов будет равно:

10*27*8192 = 2 211 840,

что приблизительно в полтора раза меньше общего количества транзисторов на кристалле Pentium. Таким образом, ясно, что описанная структура полностью ассоциативной КЭШ-памяти () реализуема только при малом количестве строк в КЭШе, т.е. при малом объеме КЭШа (практически не более 32…64 строк). КЭШ большего объема строят по другой структуре.

Если 2 n строк кэша разбивается на 2 s непересекающихся подмножеств, то S младших разрядов оперативной памяти показывают, в каком из подмножеств (индексов) должен вестись ассоциативный поиск. Старшие n-s разрядов адреса основной памяти являются тегами.

Если S=0, то получим одно подмножество, что соответствует полностью ассоциативной кэш-памяти. Если S=n, то получим 2 n подмножеств (то есть одна строка - одно подмножество). Это кэш-память с прямым отображением. Если 1£ S £ n-1, то имеем множественно-ассоциативную кэш-память.

временно по всем тегам с помощью комбинационных схем сравнения СС1 и СС2.

Рис. 6.5. Множественно-ассоциативная кэш-память

Особенности записи и замещения информации в кэш-памяти.
Когерентность кэш-памяти

При обращении по записи используется два метода: запись производится только в КЭШ или сразу и в КЭШ, и в ОЗУ. Эти методы получили название алгоритмов обратной WB (Write Back) и сквозной записи WT (Write Through) соответственно. Второй из них более простой, но и более медленный, хотя и гарантирует, что копии одной и той же информации в КЭШе и оперативной памяти всегда совпадают. Большинство ранних процессоров Intel используют именно этот алгоритм.

1) FIFO (First In First Out – первый пришедший – первым выбывает);

2) LRU (Least Recently Used – дольше других неиспользуемый);

3) LFU (Least Frequently Used – реже других используемый);

4) Случайный (random).

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

Главная » Кровля » Почему кэш называют ассоциативной памятью. Ассоциативная кэш-память