УСТРОЙСТВО И СПОСОБЫ ДЛЯ УМЕНЬШЕНИЯ ВЫТЕСНЕНИЙ В МНОГОУРОВНЕВОЙ ИЕРАРХИИ КЭША
APPARATUS AND METHOD FOR REDUCING DISPLACEMENTS IN MULTILEVEL CACHE HIERARCHY

Область техники, к которой относится изобретение
Настоящее раскрытие в целом относится к области кэш-памяти и, более конкретно, к системам памяти с кэшем «жертвенных» данных, данных и команд.
Предшествующий уровень техники
Многие мобильные продукты, например, сотовые телефоны, ноутбуки, "карманные" компьютеры и т.п. используют исполняемые процессором программы, например, программы связи и мультимедийные программы. Система обработки для таких продуктов включает в себя комплекс процессора и памяти для сохранения команд и данных. Оперативная память большой емкости обычно имеет большие времена доступа по сравнению с временем цикла процессора. Как следствие, комплекс памяти традиционно организован в иерархию на основе емкости и производительности кэшей, причем кэш с самой большой производительностью и самой маленькой емкостью расположен ближе всех к процессору. Например, кэш команд первого уровня и кэш данных первого уровня, как правило, непосредственно присоединены к процессору. В то время как унифицированный кэш второго уровня связан с кэшами данных и команд первого уровня (L1). Кроме того, системная память связана с унифицированным кэшем второго уровня (L2). Кэш команд первого уровня обычно функционирует со скоростью процессора, а унифицированный кэш второго уровня функционирует медленнее, чем кэш первого уровня, но имеет меньшее время доступа, чем системная память. Существует много альтернативных организаций памяти, например, иерархий памяти, имеющих кэш третьего уровня в дополнение к кэшу L1 и L2. Другая организация памяти может использовать только кэш первого уровня и системную память.
Организация памяти может состоять из иерархии кэшей, функционирующих как включающие (inclusive) кэши, строго включающие кэши, исключающие (exclusive) кэши, или комбинации этих типов кэшей. По определению в этом документе любые два уровня кэша, которые являются исключающими по отношению друг к другу, не могут содержать идентичную строку кэша. Любые два уровня кэша, которые являются включающими друг друга, могут содержать идентичную строку кэша. Любые два уровня кэша, которые являются строго включающими друг друга, подразумевают, что больший кэш, обычно кэш более высокого уровня, должен содержать все строки, которые находятся в меньшем кэше, обычно в кэше более низкого уровня. В многоуровневой организации кэш-памяти с тремя или большим количеством уровней любые два или большее количество уровней кэша могут функционировать как один тип кэша, например, исключающий, и оставшиеся уровни кэша могут функционировать как один из альтернативных типов кэша, например, включающий.
Кэш команд, как правило, создается для поддержания множества команд, расположенных по одному адресу в кэше команд. Кэш данных, как правило, создается для поддержания множества элементов данных, расположенных по одному адресу в кэше данных, где элемент данных может быть переменным количеством байтов, зависящим от процессора. Это множество команд или элементов данных, как правило, называют строкой кэша или просто строкой. Например, процессор выбирает команду или элемент данных из кэша L1, и если команда или элемент данных присутствуют в кэше, то происходит "попадание", и команда или элемент данных обеспечивается в процессор. Если команда или элемент данных отсутствуют в кэше L1, то происходит "промах". Промах может произойти по обращению к команде или элементу данных во всей строке кэша. Когда происходит промах, строка в кэше заменяется новой строкой, содержащей отсутствующую команду. Для определения того, какую строку кэша заменять, используется политика замены. Например, выбор или вытеснение строки-«жертвы» кэша, которая использовалась меньше всего, представляет политику с наиболее длительным отсутствием обращений (LRU). Строка кэша, выбранная для вытеснения, является строкой-«жертвой» кэша.
Строка кэша также может объединяться с несколькими битами состояния, например, битом достоверности и битом очистки. Бит достоверности указывает, что команды или данные находятся в строке кэша. Бит очистки указывает на то, имела ли место модификация строки кэша. В кэше с обратной записью бит очистки указывает, что, когда строка кэша должна быть заменена, модификации должны быть записаны обратно на следующий более высокий уровень памяти в иерархии системы памяти.
Кэш-память «жертвенных» данных может быть отдельным буфером, связанным с кэшем, например, кэшем первого уровня или интегрирована в смежный кэш более высокого уровня. Строки кэш-памяти «жертвенных» данных могут размещаться в кэш-памяти «жертвенных» данных согласно предположениям о том, что строка-«жертва» может потребоваться через относительно короткое время после вытеснения, и что доступ к строке-«жертве», когда необходимо, из кэша «жертвенных» данных быстрее, чем доступ к этой строке-«жертве» из более высокого уровня иерархии памяти. С кэш-памятью «жертвенных» данных, интегрированной в смежный кэш более высокого уровня, вытеснение происходит, когда строка смещается из кэша более низкого уровня и размещается в кэше более высокого уровня, соответственно, с кэшированием «жертв» кэша более низкого уровня. Кэш более низкого уровня посылает все смещенные строки, и модифицированные, и немодифицированные, в кэш более высокого уровня. В некоторых случаях, строка-"жертва" может уже существовать в кэш-памяти «жертвенных» данных и при перезаписи уже существующих строк растрачивается энергия и уменьшается ширина полосы до кэш-памяти «жертвенных» данных.
Сущность изобретения
В настоящем раскрытии признается важность сокращения требований по питанию в системе памяти для мобильных приложений и, в целом, для сокращения требований по питанию в обрабатывающих системах. Для этих целей предназначен вариант осуществления изобретения способа отслеживания для сокращения размещения смещенных строк кэша. Выбирается строка для смещения в кэш более низкого уровня. Идентифицируется информация, связанная с выбранной строкой, которая указывает, что выбранная строка присутствует в кэше более высокого уровня. Размещение выбранной строки в кэше более высокого уровня предотвращается на основе идентифицированной информации. Предотвращение размещения выбранной строки сохраняет энергию, которая была бы связана с размещением.
Другой вариант осуществления изобретения предназначен для способа для уменьшения вытеснения. В ответ на промах кэша уровня X, сохраняется информация размещения в кэше уровня X в теге строки кэша, связанной с промахом. Эта информация размещения указывает, была ли строка кэша размещена в кэше уровня X+1. Выбирается строка для вытеснения в кэш уровня X. Вытеснение выбранной строки из кэша уровня X в кэш уровня X+1 предотвращается в зависимости от информации размещения выбранной строки, указывающей, что строка кэша была размещена в кэше уровня X+1.
Другой вариант осуществления изобретения предназначен для системы памяти, имеющей множество уровней кэша. Конфигурируется кэш более низкого уровня для сохранения множества первых строк кэша, каждая с битом размещения. Бит размещения, связанный с одной из множества первых строк кэша, указывает на то, была ли эта строка из множества первых строк кэша размещена в кэше более высокого уровня. Логическая схема вытеснения сконфигурирована для определения того, является ли первая строка кэша, выбранная для смещения из множества первых строк кэша, строкой кэша, которая является избыточной со строкой кэша в кэше более высокого уровня, на основе бита размещения, связанного с выбранной первой строкой кэша. Вытеснение выбранной первой строки кэша в кэш более высокого уровня предотвращается в зависимости от бита размещения выбранной первой строки кэша.
Понятно, что другие варианты осуществления настоящего изобретения станут очевидны специалистам в данной области техники из следующего подробного описания, в котором различные варианты осуществления изобретения изображены и описаны для иллюстрации. Как будет понятно, изобретение можно применять для различных других вариантов осуществления, и можно модифицировать некоторые его детали в различных других отношениях, и все это не отступая от настоящего изобретения. Соответственно, чертежи и подробное описание должны рассматриваться как иллюстративные по природе, а не как ограничительные.
Краткое описание чертежей
На фиг.1 изображена система радиосвязи.
Фиг.2 - функциональная блок-схема иллюстративного комплекса процессора и памяти, в котором сокращаются вытеснения.
Фиг.3 - блок-схема, иллюстрирующая процесс сокращения вытеснений.
Подробное описание
Подробное описание, изложенное ниже согласно приложенным чертежам, предназначено для описания различных иллюстративных вариантов осуществления настоящего изобретения, и нет намерения представлять единственно возможные варианты осуществления настоящего изобретения. Для обеспечения полного понимания настоящего изобретения это подробное описание содержит конкретные детали. Однако специалистам в данной области техники будет очевидно, что настоящее изобретение может быть осуществлено на практике без этих конкретных деталей. В некоторых случаях, общеизвестные структуры и компоненты представлены в форме блочной диаграммы во избежание затруднения понимания концепций настоящего изобретения.
На фиг.1 изображена иллюстративная система 100 радиосвязи, в которой преимущественно может применяться вариант осуществления изобретения. С целью иллюстрации, на фиг.1 изображено три удаленных устройства 120, 130 и 150 и две базовых станции 140. Следует понимать, что общепринятые системы радиосвязи могут иметь намного больше удаленных устройств и базовых станций. Удаленные устройства 120, 130 и 150 включают в себя аппаратные компоненты, программные компоненты или и те и другие, как представлено компонентами 125A, 125C и 125B, соответственно, которые были адаптированы для осуществления изобретения, как обсуждается ниже. На фиг.1 изображены сигналы 180 прямой линии связи из базовых станций 140 в удаленные устройства 120, 130 и 150, и сигналы 190 обратной линии связи из удаленных устройств 120, 130 и 150 в базовые станции 140.
На фиг.1, удаленное устройство 120 изображено как мобильный телефон, удаленное устройство 130 изображено как переносной компьютер и удаленное устройство 150 изображено как удаленное устройство с фиксированным местоположением в системе беспроводного локального шлейфа. Например, удаленные устройства могут в качестве альтернативы быть сотовыми телефонами, пейджерами, портативными дуплексными радиостанциями, малогабаритными устройствами комплектов персональной связи (PCS), портативными устройствами данных, например, "карманными" компьютерами, или устройствами данных с фиксированным местоположением, например, оборудованием с показаниями измерительного прибора. Хотя на фиг.1 изображены удаленные устройства согласно идеям раскрытия, раскрытие не ограничено этими иллюстративными изображенными устройствами. Варианты осуществления изобретения могут соответственно применяться в любом устройстве, имеющем процессор, по меньшей мере, с двумя уровнями иерархии памяти, например, кэшем первого уровня и кэшем второго уровня.
Фиг.2 является функциональной блок-схемой иллюстративного комплекса 200 процессора и памяти, в котором сокращаются вытеснения. Иллюстративный комплекс 200 процессора и памяти включает в себя процессор 202, кэш первого уровня (кэш L1) 203, содержащий массив 204 строк кэша L1, и устройство 206 управления кэшем L1, включающий кэш второго уровня (кэш L2) 208 и системную память 210. Устройство 206 управления кэшем L1 включает в себя логическую схему 212 вытеснения и ассоциативную память первого уровня (CAM L1) 214 для согласования тегов, которые могут использоваться в различных типах кэшей, например, наборно-ассоциативном кэше или полностью ассоциативном кэше. Периферийные устройства, которые могут соединяться с комплексом процессора, не изображены для ясности обсуждения. Иллюстративный комплекс 200 процессора и памяти может соответственно использоваться в различных вариантах осуществления изобретения в компонентах 125 A-C для исполнения программного кода, который хранится в кэшах 203 и 208 и системной памяти 210.
Массив 204 строк кэша L1 может включать в себя множество строк, например, строки 215-217 кэша. В одном варианте осуществления, кэш 203 L1 является кэшем данных, причем каждая строка состоит из множества элементов данных. В другом варианте осуществления, кэш 203 L1 является кэшем команд, причем каждая строка состоит из множества команд. В еще одном варианте осуществления, кэш 203 L1 является унифицированным кэшем, причем каждая строка состоит из множества команд или элементов данных. Например, каждая строка состоит из множества элементов (U0, U1,..., U7) 218-225, соответственно, соответствующих иллюстративному варианту осуществления кэша. С каждой строкой связан тег 226, бит очистки (D) 228 и бит вытеснения принудительной замены (FRC) 230, которые будут обсуждаться более подробно ниже. Строки 215-217 кэша находятся в массиве 204 строк кэша L1 по адресам 231-233 строк, соответственно. Устройство 206 управления кэшем L1 содержит логику управления адресами, чувствительную к адресу команды или адресу данных (I/DA) 234, принятому по интерфейсу 235 I/DA для обращения к строкам кэша. I/DA 234 может состоять из тега 236, поля 238 адреса строки, поля 240 команда/данные "U" и поля 242 байта "B".
Для выборки команды или элемента данных в иллюстративном комплексе 200 процессора и памяти, процессор 202 формирует адрес команды/данных (I/DA) 234 требуемой команды/данных, которые будут выбираться, и посылает адрес выборки в устройство 206 управления кэшем L1. На основе принятого I/DA 234, устройство 206 управления кэшем L1 проверяет, присутствуют ли команда или данные в массиве 204 строк кэша L1. Эта проверка выполняется, например, посредством использования логики сравнения, которая ищет соответствующий тег 244, связанный со строкой 215, которая была выбрана посредством I/DA 234. Если команда или данные присутствуют, то имеет место соответствие или попадание, и устройство 206 управления кэшем L1 указывает, что команда или данные присутствуют в кэше 203 L1. Если команда или данные отсутствуют, то обнаружится несоответствие или промах, и устройство 206 управления кэшем L1 обеспечит индикатор промаха, что команда или данные отсутствуют в кэше 203 L1.
Если команда или данные присутствуют, то команда или данные по адресу выборки команды/данных выбираются из массива 204 строк кэша L1. После этого команда или данные посылаются по шине 246 команд/данных в процессор 202.
Если команда/данные отсутствуют в кэше, то в кэш 208 L2 обеспечивается информация о промахе посредством сигнала 248 промаха, указывающего, что произошел промах. После обнаружения промаха кэша 203 L1, делается попытка выбрать требуемые команда/данные из кэша 208 L2. Если требуемые команда/данные присутствует в кэше 208 L2, то они обеспечиваются в интерфейс 250 шины памяти. Если требуемые команда/данные отсутствуют в кэше 208 L2, то они выбираются из системной памяти 210.
Из кэша 208 L2 посылается сигнал 254 вытеснения принудительной замены (FRC) в кэш 203 L1 нижнего уровня, при этом требуемые команда/данные посылаются по интерфейсу 250 шины памяти. Сигнал 254 FRC указывает, были или не были получены обеспечиваемые команда/данные вследствие попадания кэша 208 L2 верхнего уровня. Например, сигнал 254 FRC в состоянии "0" указывает, что требуемые команда/данные были обеспечены из кэша 208 L2. Сигнал 254 FRC в состоянии "1" указывает, что требуемые команда/данные были обеспечены из памяти другого уровня, выше кэша 208 L2, например, из системной памяти 210. Сигнал 254 FRC сохраняется в кэше 203 L1, например, как биты 256-258 FRC вместе с тегом, связанным с соответствующей строкой кэша, например, строки 215-217. Когда запрошенная строка отсутствует в кэше 208 L2 и кэше 203 L1, кэш 203 L1 обеспечивается посредством следующего уровня памяти, выше кэша 208 L2, тогда как кэш 208 L2 не размещает строку во время этого промаха.
Когда кэш более низкого уровня должен сместить строку, эта строка может быть размещена в кэше следующего уровня, в зависимости от информации, хранящейся со строкой в кэше более низкого уровня. Например, когда кэш более низкого уровня, например, кэш 203 L1, выбирает строку для смещения, например, строку 215 кэша, с индикатором очистки, как обозначено битом 259 очистки в состоянии "1", логическая схема 212 вытеснения принимает решение, что строка 215 кэша должна быть размещена на следующем уровне иерархии памяти. Если для смещения выбрана строка кэша, которая не является модифицированной, например, строка 216 кэша с битом 260 очистки в состоянии "0", и ассоциированный с ней бит 256 FRC установлен активным, например, в состояние "1", то строка 216 кэша также размещается на следующем уровне иерархии памяти. Бит 256 FRC устанавливается активным, в зависимости от индикатора сигнала 254 FRC, обеспечиваемого следующим уровнем иерархии памяти, что строка не была найдена в его директории. Если строка кэша, которая выбрана для вытеснения, не является модифицированной, например, строка 217 кэша со своим битом 261 очистки в состоянии "0", и ассоциированный с ней бит 258 FRC установлен неактивным, например, в состояние "0", то строка 217 кэша не размещается на следующем уровне иерархии памяти. Вытеснение не требуется из-за того, что строка не модифицирована и бит 258 FRC указывает своим неактивным состоянием, что эта строка 217 кэша присутствует на следующем уровне иерархии памяти. Одним словом, кэш более высокого уровня в ответ на смещение строки кэша размещает строку кэша на более низком уровне, когда установлен бит очистки или установлен бит FRC. Посредством такого использования бита FRC подавляются избыточные вытеснения, тем самым сохраняя энергию и циклы доступа посредством ухода от ненужных обращений к верхним уровням иерархии памяти.
Фиг.3 является блок-схемой, иллюстрирующей процесс 300 для сокращения вытеснений. В процессе 300, уровень памяти обозначен индексами (X), (X+1) или (X+2), где, например, посредством X=1 может быть обозначен уровень памяти L1, L2 и L3. Кроме того, описания этапов процесса 300 включают в себя ссылочные позиции для функциональных элементов по фиг.2.
Процесс 300 начинается посредством процессора, например, процессора 202, который выбирает команду или элемент данных на этапе 302. На этапе 304 принятия решения, определяется, могут ли запрошенные команда/данные быть размещены в кэше L(X), например, кэше 203 L1. Если команда/данные могут быть размещены, то запрошенные команда/данные выбираются из кэша L(X), на этапе 306, и команда/данные возвращаются в процессор на этапе 308.
Если команда/данные не могут быть размещены в кэше L(X), то формируется индикатор промаха, и на этапе 310 принятия решения определяется, могут ли запрашиваемые команда/данные быть размещены в кэше L(X+1), например, кэше 208 L2. Если команда/данные могут быть размещены, то запрашиваемые команда/данные выбираются из кэша L(X+1) на этапе 316. На этапе 318, бит вытеснения принудительной замены (FRC), например, бит 258 FRC, устанавливается в состояние "0" в строке тега, например, связанной со строкой 217 кэша 203 L1, для предотвращения посылки этих команды/данных кэшем 203 L1 в кэш 208 L2. Процесс 300 далее переходит к этапу 320 принятия решения.
Возвращаясь к этапу 310, если команда/данные не могут быть размещены в кэше L(X+1), то формируется индикатор промаха. На этапе 312, из уровня иерархии памяти, который больше или равен уровню L(X+2), например, кэша L3 или системной памяти 210 комплекса 200 процессора и памяти, выбираются запрошенные команда/данные. На этапе 314, бит FRC, например, бит 256 FRC, устанавливается в состояние "1" и сохраняется с тегом, связанным с выбранной строкой, например, строкой 216 кэша.
На этапе 320 принятия решения, определяется, должна ли быть заменена строка в кэше L(X), например, кэше 203 L1. Если определено, что строка должна быть заменена в кэше L(X), то также определяется на этапе 322 принятия решения, является ли выбранная строка, строка-"жертва", модифицированной, например, обозначенной битом 259 очистки в состоянии "1". Если выбранная строка-"жертва" является модифицированной, то строка-"жертва" размещается на этапе 324 в кэше L(X+1), например, кэше 208 L2. Если выбранная строка-"жертва" не является модифицированной, например, обозначенной битами 260 и 261 очистки, то на этапе 326 принятия решения проверяется бит FRC для определения того, установлен ли он активным. Если на этапе 326 принятия решения определяется, что бит FRC является активным, например, как в случае бита 256 FRC, то на этапе 324 строка-"жертва" размещается в кэше L(X+1), например, кэше 208 L2.
Если на этапе 320 принятия решения определяется, что строка не должна быть заменена, или, если на этапе 326 принятия решения определяется, что бит FRC не является активным, например, в состоянии "0", как в случае бита 258 FRC, то на этапе 328 запрошенные команда/данные размещаются в кэше L(X), например, кэше 203 L1. На этапе 330 запрошенные команда/данные также возвращаются в запрашивающий процессор, например, процессор 202. Соответственно, избегают избыточное вытеснение в кэш L(X+1), тем самым сохраняют энергию и улучшают ширину полосы доступа кэша в иерархии памяти.
Различные иллюстративные логические блоки, модули, схемы, элементы и/или компоненты, описанные согласно раскрытым здесь вариантам осуществления, могут быть реализованы или выполнены с универсальным процессором, цифровым сигнальным процессором (DSP), специализированной интегральной схемой (ASIC), программируемой пользователем вентильной матрицей (FPGA) или другими программируемыми логическими компонентами, дискретным вентилем или транзисторной логикой, дискретными аппаратными компонентами или любой их комбинацией, предназначенной для выполнения описанных здесь функций. Универсальный процессор может быть микропроцессором, но в качестве альтернативы, процессор может быть любым общепринятым процессором, контроллером, микроконтроллером или конечным автоматом. Процессор также может быть реализован как комбинация вычислительных компонентов, например, комбинация DSP и микропроцессора, множества микропроцессоров, одного или нескольких микропроцессоров вместе с ядром DSP или как любая другая такая конфигурация, подходящая для требуемого применения.
Способы, описанные согласно раскрытым здесь вариантам осуществления, могут быть воплощены непосредственно в аппаратных средствах, в исполнимом процессором программном модуле, или в комбинации их обоих. Программный модуль может находиться в памяти RAM, флэш-памяти, памяти ROM, памяти EPROM, памяти EEPROM, регистрах, жестком диске, сменном диске, CD-ROM или любом другом виде носителя информации, известном в данной области техники. Носитель информации может быть соединен с процессором так, что процессор может считывать информацию из носителя информации и записывать информацию на него. В качестве альтернативы, носитель информации может быть неотъемлемой частью процессора.
Несмотря на то, что изобретение раскрыто в контексте иллюстративных вариантов осуществления для кэшей команд, кэшей данных и других типов кэшей, следует понимать, что специалистами в данной области техники может применяться широкое разнообразие реализаций, соответствующих вышеизложенному обсуждению и формуле изобретения, которая следует ниже.