Реклама:

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

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

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

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

В настоящее время многие системы памяти гораздо сложнее этих. Между разделенной кэш-памятью и основной памятью часто помещается кэш-память второго уровня. Вообще говоря, поскольку требуются более совершенные системы, может быть три и более уровня кэш-памяти. На рис. 4.25 изображена система с тремя уровнями кэш-памяти. Прямо на микросхеме центрального процессора находится небольшой кэш для команд (Ы-1) и небольшой кэш для данных (Ы-Б) объемом обычно от 16 до 64 Кбайт. Есть еще кэш-память второго уровня (Ь2), которая расположена не на самой микросхеме процессора, а рядом с ним в том же блоке. Кэш-память второго уровня соединяется с процессором через высокоскоростной тракт данных. Эта кэш-память обычно не является разделенной и объединяет данные и команды. Ее размер - от 512 Кбайт до 1 Мбайт. Кэш-память третьего уровня (ЬЗ) находится на той же плате, что и процессор, и обычно состоит из статического ОЗУ в несколько мегабайтов, которое функционирует гораздо быстрее, чем динамическое ОЗУ основной памяти. Как правило, все содержимое кэш-памяти первого уровня находится в кэш-памяти второго уровня, а все содержимое кэш-памяти второго уровня - в кэш-памяти третьего уровня.

Кэш-память4

Рис. 4.25. Система с тремя уровнями кэш-памяти

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

Во всех типах кэш-памяти используется следующая модель. Основная память разделяется на блоки фиксированного размера, которые называются строками кэша. Строка кэша состоит из нескольких последовательных байтов (обычно от 4 до 64). Строки нумеруются, начиная с 0, то есть если размер строки составляет 32 байта, то строка 0 - это байты с 0 по 31-й, строка 1 - байты с 32-го по 63-й и т. д. В любой момент в кэш-памяти находится несколько строк. Когда происходит обращение к памяти, контроллер кэш-памяти проверяет, есть ли нужное слово в кэш-памяти. Если слово есть (случай кэш-попадания), то можно сэкономить время, требуемое на доступ к основной памяти. Если данного слова в кэш-памяти нет (случай кэш-промаха), то одна из строк из кэша удаляется, а вместо нее туда помещается запрошенная строка из основной памяти или из кэш-памяти более низкого уровня. Существует множество вариаций данной схемы, но в их основе всегда лежит идея держать в кэш-памяти как можно больше часто используемых строк, чтобы число кэш-попаданий было максимальным.

Кэш-память прямого отображения

Самый простой тип кэш-памяти - кэш-память прямого отображения. Пример одноуровневой кэш-памяти прямого отображения показан на рис. 4.26, а. Данная кэш-память содержит 2048 элементов. Каждый элемент (ряд) может вмещать ровно одну сроку из основной памяти. Если размер строки кэша составляет 32 байта (как в этом примере), кэш-память может вмещать 64 Кбайт. Каждый элемент кэш-памяти состоит из трех частей:

4 Бит достоверности указывает, есть достоверные данные в элементе или нет. Когда система загружается, все элементы маркируются как недостоверные.

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

4 Поле данных содержит копию данных памяти. Это поле вмещает одну строку кэша размером 32 байта.

В кэш-памяти прямого отображения заданное слово может храниться только в одном месте. Если его в этом месте нет, значит, его вообще нет в кэш-памяти. Для хранения данных в кэше и извлечения их из кэша адрес разбивается на 4 компонента, как показано на рис. 4.26, б\

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

Кэш-память4

Рис. 4.26. Кэш-память прямого отображения (а); 32-разрядный виртуальный адрес (б)

4 Поле тега соответствует битам, сохраненным в поле тега элемента кэш-памяти.

♦ Поле слова указывает, на какое слово в строке производится ссылка.

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

Когда центральный процессор выдает адрес памяти, аппаратура выделяет из этого адреса 11 бит поля строки и использует их для поиска в кэш-памяти одного из 2048 элементов. Если элемент действителен, то производится сравнение поля тега основной памяти и поля тега кэш-памяти. Если поля равны, значит, в кэш-памяти есть запрашиваемое слово. Такая ситуация называется кэш-попаданием. В случае кэш-попадания слово берется прямо из кэш-памяти, и тогда не нужно обращаться к основной памяти. Из элемента кэш-памяти берется только нужное слово, остальная часть элемента не используется. Если элемент кэш-памяти недействителен (недостоверен) или поля тега не совпадают, то нужного слова нет в памяти. Такая ситуация называется кэш-промахом. В этом случае 32-байтная строка вызывается из основной памяти и сохраняется в кэш-памяти, заменяя тот элемент, который там был. Однако если существующий элемент кэш-памяти изменяется, его нужно записать обратно в основную память до того, как он будет удален.

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

При такой схеме смежные строки основной памяти помещаются в смежные элементы кэш-памяти. Фактически в кэш-памяти может храниться до 64 Кбайт смежных данных. Однако две строки, адреса которых отличаются ровно на 64 Кбайт (65 536 байт) или на любое целое, кратное этому числу, не могут одновременно хранится в кэш-памяти (поскольку они имеют одно и то же значение поля строки). Например, если программа обращается к данным с адресом X, а затем выполняет команду, которой требуются данные с адресом X + 65 536 (или с любым другим адресом в той же строке), вторая команда требует перезагрузки элемента кэш-памяти. Если это происходит достаточно часто, то могут возникнуть проблемы. В действительности, если кэш-память плохо работает, лучше, чтобы ее вообще не было, поскольку при каждой операции с основной памятью считывается целая строка, а не одно слово.

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

Ассоциативная кэш-память с множественным доступом

Как было отмечено ранее, различные строки основной памяти конкурируют за право занять одну и ту же область кэша. Если программе, использующей кэш-память, изображенную на рис. 4.26, а, часто требуются слова с адресами 0 и 65 536, то будут иметь место постоянные конфликты, поскольку каждое обращение потенциально повлечет за собой вытеснение из кэш-памяти той или иной строки. Чтобы разрешить эту проблему, нужно сделать так, чтобы в каждом элементе кэш-памяти помещалось по две и более строки. Кэш-память с п возможными элементами для каждого адреса называется п-входовой ассоциативной кэш-памятью. 4-входовая ассоциативная кэш-память изображена на рис. 4.27.

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

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

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

Кэш-память4

Рис. 4.27. 4-входовая ассоциативная кэш-память

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

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

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

С процессом записи связана еще одна проблема: что происходит, если нужно записать что-либо в ячейку, которой нет в кэш-памяти? Должны ли данные передаваться в кэш или просто записываться в основную память? И снова ни один из ответов не является во всех отношениях лучшим. В большинстве разработок, в которых применяется обратная запись, данные передаются в кэш-память. Эта технология называется заполнением по записи (write allocation). С другой стороны, в тех разработках, где применяется сквозная запись, элемент в кэш-память при записи обычно не помещается, поскольку это усложняет систему. Заполнение по записи полезно только в том случае, если имеют место повторные записи в одно и то же слово или в разные слова в пределах одной строки кэша.

Эффективность кэширования является крайне важным условием повышения общей производительности системы в силу огромного разрыва между быстродействием процессора и памяти. Дискуссия об альтернативных стратегиях кэширования ведется постоянно [6, 96, 145, 149, 197].

Повышение производительности || Оглавление || Прогнозирование ветвлений