Настоящее изобретение относится к системам обработки данных. В частности, это изобретение относится к системам обработки данных, использующим кэш-память, которая содержит по меньшей мере один разряд состояния, связанный с каждым словом данных в кэш-памяти.
Известны устройства кэш-памяти, такие как показаны на фиг.1 сопроводительных чертежей, которые включают в себя запоминающее устройство 2, содержащее адресные теги для строк данных в запоминающем устройстве с произвольной выборкой (ЗУПВ) 4 кэша. ЗУПВ 4 кэша содержит множество строк 6 кэша, причем каждая строка 6 кэша хранит четыре слова данных. С каждой строкой 6 кэша связано множество разрядов 8 достоверности и разрядов недействительности ("испорченности"). Общепринятыми типами разрядов 8 состояния являются разряд 10 достоверности и разряд 12 недействительности. Разряд 10 достоверности показывает, хранятся ли в строке кэша действительные данные, например в начале работы каждая строка 6 кэша должна быть помечена как строка, хранящая недействительные данные. Разряд 12 недействительности показывает в контексте архитектуры кэша с обратной записью, что по меньшей мере одно слово данных с этой строкой 6 кэша было изменено с тех пор, как оно было считано из основной памяти, и соответственно необходима запись обратно в основную память, когда данная строка 6 кэша очищается или заменяется в кэш-памяти. Можно убедиться в том, что в качестве компромисса между схемной площадью и точностью управления, которая может быть достигнута с разрядами 8 состояния, каждая строка 6 кэша может иметь связанный с ней один разряд 10 достоверности и связанный с ней один разряд 12 недействительности (именно такая компоновка используется в большинстве вариантов реализации кэш-памяти). Таким образом, четыре слова данных в строке 6 кэша совместно используют указанные разряды 8 состояния.
В некоторых рабочих ситуациях желательно выполнять глобальные изменения разрядов 8 состояния всех строк 6 кэш-системы. Например, после инициализации системы вслед за изменением БУП (блок управления памяти) или после контекстного переключения часто необходимо очистить все содержимое кэша, отметив все разряды 10 достоверности каждой строки 6 кэша как недействительные. Одним из способов выполнения вышеуказанного является последовательное обращение к каждому из разрядов 10 достоверности и запись их в качестве недействительных. В кэш-системе, которая может содержать тысячи строк 6 кэша, эта операция может занять тысячи циклов обработки, что значительно ухудшает производительность системы. Альтернативой последовательного и индивидуального изменения каждого из разрядов 8 состояния является глобальное изменение посредством специализированных аппаратных средств, способных изменять разряды состояния параллельно. Хотя это и может обеспечить быстрое выполнение операции, этот вариант имеет недостаток, связанный с тем, что увеличивается схемная площадь для таких специализированных аппаратных средств и, кроме того, для каждой реализации более общего проекта системы обычно требуется индивидуальное проектирование.
В патентной заявке США №5475849 раскрыто устройство управления памятью для мультипроцессорной системы с множеством процессоров, каждый из которых вместе с другими использует одну основную память, имея при этом свои собственные буферные запоминающие устройства или кэши. Система использует массивы начальных адресов (МНА) для согласования управления отдельными буферными запоминающими устройствами и основной памятью. Для ограничения необходимого количества МНА без чрезмерного увеличения времени ожидания для поиска в МНА система имеет блочные запоминающие устройства (для разрядов) достоверности блоков (ЗУДБ), которые имеют записи для каждой ячейки памяти в основной памяти, и таблицы достоверности групп блоков (ТДГБ), которые имеют записи для каждой группы ячеек памяти, связанных с каждым буферным запоминающим устройством. При запросе на сохранение сначала производится обращение к ТДГБ и, если часть или весь блок, содержащий запрошенную ячейку, имеется в буферном запоминающем устройстве, связанном с этой ТДГБ, то тогда формируется сигнал достоверности. После этого осуществляется обращение к соответствующему ЗУДБ и, если формируется сигнал достоверности, значит, данная ячейка памяти есть в буфере, и выполняется обращение к МНА. Если формируется хотя бы один сигнал недостоверности, то запрос игнорируется и не посылается в МНА.
В патентной заявке США №5539894 раскрыта кэш-память, имеющая теги кэша с разрядами достоверности блоков и разрядами достоверности подблоков.
Настоящее изобретение связано с обеспечением механизмов изменения разрядов состояния с высокой скоростью, по возможности за время одного цикла обработки, без необходимости иметь заказные аппаратные средства для параллельного доступа ко всем разрядам состояния.
Согласно одному аспекту настоящее изобретение обеспечивает устройство для обработки данных, причем устройство содержит
память для сохранения множества слов данных, причем каждое слово данных связано по меньшей мере с одним разрядом состояния, дающим информацию, которая относится к состоянию указанного слова состояния;
запоминающее устройство для разрядов состояния для хранения разрядов состояния в иерархическом соотношении, так что комбинированное состояние, относящееся к множеству разрядов состояния первого уровня на первом уровне в иерархическом соотношении, указывается разрядом состояния второго уровня в иерархическом соотношении, причем второй уровень в указанной иерархическом соотношении выше, чем первый уровень;
логическая схема запросов состояния, пригодная для определения состояния слова данных в памяти путем анализа разрядов состояния в запоминающем устройстве для разрядов состояния, начиная с верхнего уровня в иерархическом соотношении, и обработки сверху вниз по иерархическому соотношению, пока не будет достигнут разряд состояния, который указывает состояние слова данных независимо от любого разряда состояния, находящегося в иерархическом соотношении ниже; и отличающееся тем что устройство пригодно для индикации глобального изменения состояния всех слов данных, сохраненных в памяти, путем изменения только тех разрядов состояния, которые находятся на высшем уровне в иерархическом соотношении.
Изобретение обеспечивает разряды состояния, расположенные в иерархическом соотношении (имеющем по меньшей мере два уровня), так что могут быть осуществлены глобальные или крупномасштабные изменения состояния множества слов данных в памяти путем изменения относительно небольшого количества разрядов в верхней части иерархического соотношения или по направлению к верхней части иерархического соотношения без необходимости индивидуального изменения каждого разряда состояния, относящегося к каждому слову данных, для которого изменяется состояние. При этом может быть существенно сокращено время, затрачиваемое на глобальные или крупномасштабные изменения, без необходимости обеспечения заказных аппаратных средств для крупномасштабных изменений одновременно всех разрядов состояния. Очевидно, что многие слова данных могут совместно использовать разряды состояния. В некоторых вариантах осуществления иерархическая структура может быть построена из разрядов достоверности, и слова данных, к которым они относятся, включают в себя значения тегов, слова данных, разряды недействительности и другие разряды состояния.
Разряды состояния могут представлять множество различных характеристик слов данных, к которым они относятся. Однако изобретение, в частности, подходит для вариантов осуществления, в которых разряды состояния представляют собой разряды достоверности, указывающие достоверность слов данных, хранящихся в памяти.
Разряды достоверности часто подвергаются глобальным или крупномасштабным изменениям, и поэтому изобретение, в частности, полезно тем, что допускает более быстрые изменения этих разрядов с меньшими затратами на аппаратные средства.
Следует иметь в виду, что на низшем уровне в иерархическом соотношении отдельный разряд состояния может быть обеспечен для каждого слова данных. Таким образом, если память представляет собой кэш-память, а в строке кэша хранятся четыре слова данных, то тогда можно связать с этой строкой кэша четыре отдельных разряда достоверности для индикации достоверности каждого отдельного слова данных. Однако в предпочтительных вариантах изобретения разряд состояния низшего уровня относится к множеству слов данных. Это обеспечивает удовлетворительный компромисс между степенью детализации точного управления, которая может быть достигнута, и аппаратными ресурсами, необходимыми для обеспечения разрядов состояния.
В частности, весьма удобно связать разряд состояния на низшем уровне со всеми словами данных в строке кэш-памяти. Можно рассмотреть ряд вариантов осуществления, где строка кэша может включать в себя соответствующие значения тегов и разряды недействительности.
Установлено, что такая структура работает эффективно, поскольку обращения с участием кэша к основной памяти и из нее обычно выполняются на построчной основе, так что потребность в информации о состоянии ниже уровня строки кэша возникает редко из-за временной и пространственной локальности, которая на практике характерна для большинства обращений к памяти.
Настоящее изобретение само по себе подходит к вариантам осуществления, в которых запоминающее устройство для разрядов состояния включает в себя ЗУПВ, где хранятся слова разрядов состояния, которые сформированы из множества разрядов состояния. Иерархическое соотношение между этими разрядами состояния и логической схемой запросов состояния такова, что разряды состояния по направлению к более низким уровням в иерархическом соотношении могут запоминаться в ЗУПВ без значительного влияния на рабочие характеристики, в результате чего сильнее проявляются преимущества в плотности хранения в ЗУПВ по сравнению с разрабатываемыми на заказ схемами-защелками или регистрами.
Запоминание разрядов состояния в ЗУПВ позволяет удобно манипулировать ими в виде слов разрядов состояния, доступных из ЗУПВ.
При манипулировании словами разрядов состояния типовой операцией может быть операция считывания-модификации-записи, которая легко поддерживается существующими структурами обработки данных во многих системах. Также могут потребоваться отдельные операции считывания и записи, и в некоторых ЗУПВ поддерживаются только операции считывания и записи.
В отличие от использования ЗУПВ высокой плотности на низших уровнях в запоминающем осуществления устройстве разрядов состояния в предпочтительных вариантах осуществления по меньшей мере на высшем уровне в иерархическом соотношении для хранения разрядов состояния используются схемы регистров (D-типа). Быстрое обращение и изменение состояния схем-защелок может быть осуществлено в ответ на заранее определенные входные сигналы или состояния, такие как инициализация, изменения БУП, контекстные переключения и т.д., и поэтому быстрые глобальные или крупномасштабные изменения состояния обеспечиваются при использовании относительно небольших заказных аппаратных средств либо вообще без них.
К разрядам состояния, хранящимся в схеме-защелке, обычно можно обращаться и манипулировать ими индивидуально по сравнению с разрядами состояния, хранящимися в ЗУПВ, доступ и манипулирование которыми осуществляется на пословной основе.
В некоторых вариантах осуществления высший уровень в иерархическом соотношении может содержать один разряд состояния. В таких случаях общее состояние слов данных кэш-памяти может быть изменено путем единственного изменения этого одного разряда состояния на высшем уровне.
Для того, чтобы усилить существенные преимущества, обеспечиваемые запоминающим устройством разрядов состояния и логической схемой запросов состояния согласно изобретению, весьма желательно обеспечить, чтобы глобальные изменения для всей памяти можно было выполнить путем модификации только высшего уровня иерархического соотношения, и чтобы была предусмотрена достаточная аппаратная поддержка, с тем чтобы глобальное изменение можно было провести в одном цикле обработки. Это особенно выгодно в контексте кэш-памяти.
Следует иметь в виду, что, хотя глобальное изменение разрядов состояния может быть выполнено путем изменения меньшего количества разрядов в указанном иерархическом соотношении, можно ожидать, что установка отдельных разрядов состояния, начиная с самого нижнего уровня, займет больше времени, так как эти изменения должны отразиться вверх по всему иерархическому соотношению. Однако изобретение определяет, что в контексте кэш-памяти операция заполнения кэша обычно является относительно медленной, так что для множества изменений разрядов состояния, связанных с заполнением кэша, в действительности имеется достаточно времени, позволяющего выполнить все необходимые изменения разрядов состояния в иерархическом соотношении, которые должны быть сделаны, без снижения общей скорости операции. Разряды состояния могут изменяться параллельно, что дополнительно повышает эффективность.
В предпочтительных вариантах осуществления глобальное изменение состояния всех слов данных в кэш-памяти выполняется в ответ на одно из следующих действий: (i) операцию очистки кэш-памяти, (ii) изменение в конфигурации блока управления памятью, управляющего доступом к словам данных, и (iii) контекстное переключение операционной системы, управляющей программными операциями в указанном устройстве.
Предпочтительно, слова данных запоминаются в кэш-памяти с использованием операции заполнения кэша, длящейся множество циклов обработки, а запоминающее устройство разрядов состояния выполнено с возможностью модификации разрядов состояния, относящихся к словам данных, которые хранятся в кэш-памяти, в течение множества циклов обработки.
Согласно другому аспекту настоящее изобретение обеспечивает способ обработки данных, причем способ содержит этапы:
запоминают множество слов данных в памяти, причем каждое слово данных связано по меньшей мере с одним разрядом состояния, дающим информацию, которая относится к состоянию слова данных;
запоминают разряды состояния в иерархическом соотношении, так что комбинированное состояние, относящееся к множеству разрядов состояния первого уровня на первом уровне в иерархическом соотношении, указывается разрядом состояния второго уровня на втором уровне в иерархическом соотношении, причем второй уровень в иерархическом соотношении выше, чем первый уровень;
определяют состояния слова данных в памяти путем анализа разрядов состояния, начиная с верхнего уровня в иерархическом соотношении, и обрабатывают иерархическое соотношение сверху вниз, пока не будет достигнут разряд состояния, который указывает состояние указанного слова данных независимо от любых разрядов состояния, находящихся в иерархическом соотношении ниже; и отличающийся тем, что
указывают глобальное изменение состояния всех слов данных, хранящихся в памяти, путем модификации только разрядов состояния на высшем уровне иерархического соотношения.
Далее описываются варианты осуществления изобретения, приведенные лишь в качестве примера, со ссылками на сопроводительные чертежи, на которых:
фиг.1 - известная система кэша с отдельными разрядами состояния для каждой строки кэша;
фиг.2 - запоминающее устройство разрядов состояния кэша и разряды состояния, связанные с ними в иерархическом соотношении;
фиг.3 - схематическая иллюстрация части системы кэша для обработки значений тегов строк кэша и разрядов состояния;
фиг.4 - пример архитектуры кэша с взаимосвязью между адресными разрядами слова данных и разрядами состояния для слова данных в иерархическом соотношении разрядов состояния; и
фиг.5 - другой вариант части системы кэш-памяти.
На фиг.2 показана кэш-память 14 слов данных, содержащая множество строк 16 кэша, каждая из которых хранит четыре слова данных. С каждой строкой 16 кэша связан один разряд 18 достоверности. Разряды достоверности для восьми последовательных строк 16 кэша запоминаются в одном слове 20 разрядов состояния, хранящемся в ЗУПВ разрядов состояния. Слова 20 разрядов состояния образуют низший уровень в иерархическом соотношении, хранящем разряды состояния.
Каждое слово 20 разрядов состояния связано с разрядом 22 состояния, хранящимся на более высоком уровне в иерархическом соотношении и указывающим комбинированное состояние всех разрядов 18 состояния в слове 20 состояния. Таким образом, состояние восьми слов 20 состояния может быть указано восемью разрядами 22 слова состояния на следующем высшем уровне иерархического соотношения. Этот следующий более высокий уровень может быть предусмотрен в ЗУПВ разрядов состояния или на некотором уровне в направлении верхней части иерархического соотношения, которому он положил начало для большей эффективности, чтобы обеспечить запоминание разрядов состояния с помощью схем-защелок (разряды регистра), которые могут быть изменены с относительно высокой скоростью путем использования специализированной логической схемы. Над двумя показанными уровнями могут быть предусмотрены дополнительные уровни.
На фиг.3 показана часть системы кэш-памяти для запоминания значений тегов строк кэша и соответствующих разрядов состояния. Если кэш имеет 256 строк кэша, то тогда для запоминания соответствующих значений тегов для каждой строки кэша предусматривается 256-строчное запоминающее устройство 24 тегов. Если предположить, что каждая строка кэша имеет только один разряд состояния (например, разряд достоверности), то тогда разряды состояния для этих 256 строк кэша могут запоминаться в восьми 32-разрядных словах, находящихся в ЗУПВ 26 разрядов состояния. 32-разрядные слова представляют низший уровень в иерархическом соотношении, хранящем разряды состояния. Следующий высший уровень в иерархическом соотношении (в этом примере - самый высокий уровень) обеспечен 8-разрядным регистром 28, причем каждый разряд регистра 28 представляет комбинированное состояние одного из 32-разрядных слов разрядов состояния в ЗУПВ 26 разрядов состояния.
Контроллер 30 кэша соединен с запоминающим устройством 24 тегов, ЗУПВ 26 разрядов состояния и регистром 28 разрядов состояния. Контроллер 30 кэша действует как логическая схема запросов состояния, когда происходит обращение к слову данных в кэш-памяти, а также обеспечивает выполнение других функций. При наличии запроса на доступ к слову данных контроллер 30 кэша анализирует разряды состояния, хранящиеся в регистре 28 разрядов состояния и ЗУПВ 26 разрядов состояния. Если на высшем уровне разряд в регистре 28 разрядов состояния, соответствующий конкретному слову данных на низшем уровне, указывает, что слово данных достоверно, то тогда контроллер 30 кэша переходит к проверке индивидуального разряда для этого слова данных (строки кэша) в ЗУПВ 26 разрядов состояния. Если разряд в регистре 28 разрядов состояния указывает на недействительность данных, то тогда нет необходимости проверять ЗУПВ 26 разрядов состояния (хотя в действительности такая проверка может выполняться параллельно), поскольку недействительность, указанная на более высоком уровне, отменяет все, что было представлено на более низком уровне.
Контроллер 30 кэша позволяет обеспечить высокоскоростные обращения к разрядам состояния в регистре 28 разрядов состояния, так что все разряды в регистре 28 разрядов состояния могут быть установлены на значения, указывающие недействительность, в одном цикле, например, как это требуется при быстрой очистке кэша. Слова разрядов состояния в ЗУПВ 26 разрядов состояния могут быть доступны для операции считывания-модификации-записи, как это требуется для внесения одиночных изменений в разряды состояния на данном низшем уровне в иерархическом соотношении. В альтернативном варианте могут выполняться отдельные операции считывания и записи.
На фиг.4 показан пример того, как адрес слова данных в кэш-памяти объемом 128 КБ, которая имеет четыре слова данных на строку и прямое отображение, может быть связан с разрядами состояния и другими данными управления.
Старшая часть адреса 32 образует значение тега, которое сравнивается со значением тега, хранящимся в запоминающем устройстве 24 тегов, чтобы определить, кэшируются ли эти конкретные данные. Так как кэш-память имеет прямое отображение, средняя часть 34 адреса обеспечивает индекс для кэша, указывающий позицию в запоминающем устройстве тегов, где будет храниться значение тега, если эти данные имеются в кэш-памяти. В младшей части адреса разряды W слова и байтовые разряды В показывают адресуемую позицию слова в строке кэша и байтовую позицию в слове данных, если разрешена байтовая адресация.
Информация в разрядах состояния для данной кэш-памяти запоминается в трехуровневой иерархической структуре. Разряды состояния запоминаются для каждой строки кэша, и соответственно имеется разряд состояния, связанный с каждым значением индекса. Эти разряды состояния значения индекса могут запоминаться в матрице 256·16, образованной из скомпилированного ЗУПВ. Каждая строка в матрице третьего уровня имеет соответствующий разряд состояния на втором уровне иерархического соотношения, который сам хранится в матрице 16·16. Эта матрица 16·16 также может храниться в скомпилированном ЗУПВ. На высшем уровне (первый уровень) в иерархическом соотношении предусмотрено 16 разрядов регистра, причем один разряд регистра соответствует каждой строке матрицы второго уровня.
На фиг.5 в качестве примера показана еще одна структура кэш-памяти. В этом примере для запоминания значений тегов предусмотрена 1024-строчное запоминающее устройство 36 тегов. Каждая строка в запоминающем устройстве 36 тегов соответствует строке кэша и имеет связанный с ней разряд состояния. Соответственно разряды состояния для 1024 строк кэша могут запоминаться в ЗУПВ 38 объемом 32·32-разрядных слов, которое образует часть запоминающего устройства 40 разрядов состояния. Это ЗУПВ 38 разрядов состояния представляет собой низший уровень в иерархическом соотношении. Высший уровень в иерархическом соотношении обеспечивается 32 разрядами регистра 42, причем один разряд регистра соответствует каждому 32-разрядному слову в ЗУПВ 38 разрядов состояния.
Этапы, входящие в различные операции для манипулирования словами данных, хранящимися в системе кэш-памяти, где имеется иерархическая взаимосвязь между разрядами состояния, могут выглядеть, например, следующим образом.
Состояние проверки
считывание соответствующих разрядов из всех уровней иерархической структуры,
обработка иерархической структуры сверху вниз с проверкой достоверности каждого последующего более низкого уровня, если какой-либо уровень указывает, что более низкие уровни недействительны, то возврат к значению по умолчанию (исходное состояние или сброс), в противном случае возврат к значению, извлеченному из запоминающего устройства разрядов достоверности низшего уровня.
Разряды состояния имеют два состояния. В случае разряда достоверности имеется состояние сброса, которое является недействительным, и состояние достоверности. Для отметки состояния как достоверного необходимо пометить все уровни в иерархической структуре. Состояние сброса можно рассматривать как "сильное" состояние, которое может быть указано разрядом высокого уровня, а другое состояние - как "слабое" состояние, для которого должны быть согласованы все разряды в иерархической структуре.
В системе, хранящей множество разрядов состояния на ячейку, необходимо, чтобы более высокие уровни иерархической структуры для указания достоверности более низких уровней в иерархической структуре содержали только один разряд.
Состояние записи
обработка иерархической структуры сверху вниз с установкой соответствующих разрядов, указывающих, что нижеследующий уровень является достоверным, если новая строка (на любом уровне в иерархической структуре), которая ранее была недействительна, помечена как достоверная, вся строка должна быть инициализирована с использованием значения сброса, за исключением записываемого значения, в случае, когда строка ранее была достоверной, необходима операция считывания-модификации-записи для обновления только соответствующих разрядов, на низшем уровне иерархической структуры должны быть записаны соответствующие данные и, если это необходимо, другие разряды состояния должны быть установлены равным значению сброса.
Состояние сброса
чтобы пометить всю иерархическую структуру как недействительную, необходимо "сбросить" (установить в исходное значение) разряды состояния высшего уровня.
В системе с кэшем операция считывания-модификации-записи может занять множество циклов. Это открывает ряд интересных возможностей, а именно
необходимо поддерживать только иерархическую структуру разрядов достоверности независимо от того, сколько разрядов состояния поддерживается на низшем уровне (например, четыре разряда достоверности + разряд недействительности + другие разряды состояния), то есть на разных уровнях иерархической структуры могут храниться разные разряды состояния;
если такая возможность реализована, то тогда логическая схема, которая считывает матрицы, должна обеспечить возврат в состояние "сброса", если происходит обращение к недействительной ячейке;
вместо того, чтобы поддерживать иерархическую структуру только разрядов достоверности, может оказаться выгодным отслеживать другое состояние в иерархической структуре. Например, поддерживать как иерархическую структуру достоверности, так и иерархическую структуру недействительности, что позволит ускорить поиск ячеек кэша с недействительными данными.
Изобретение относится к системам обработки данных. Техническим результатом является возможность изменения разрядов состояния с высокой скоростью и отсутствие необходимости иметь заказные аппаратные средства для параллельного доступа ко всем разрядам состояния. Устройство для обработки данных содержит память, предназначенную для хранения множества слов данных, запоминающее устройство разрядов состояния, логическую схему запросов состояния. Способ обработки данных заключается в том, что запоминают множество слов данных в памяти, запоминают разряды состояния в иерархическом соотношении, определяют состояние слова данных в памяти путем анализа разрядов состояния и обрабатывают иерархическое соотношение сверху вниз, пока не будет достигнут разряд состояния, который указывает состояние слова данных независимо от любых разрядов состояния, находящихся в иерархическом соотношении ниже. 2 н. и 15 з.п.ф-лы, 5 ил.
| US 5539894 А, 23.07.1996 | |||
| Компьютеры | |||
| Справочное руководство в трех томах/Под ред | |||
| Г | |||
| ХЕЛМСА | |||
| - М.: Мир, 1986, т.1, с.42-44, т.3, с.65-137, 300-303 | |||
| US 4426682 А, 17.01.1984 | |||
| DE 3919802 A, 21.12.1989 | |||
| DE 19516949 А, 15.02.1996. |
