СИСТЕМА И СПОСОБ ДЛЯ ПРЕДВАРИТЕЛЬНОЙ ВЫБОРКИ ДАННЫХ В КЭШ-ПАМЯТИ, ОСНОВАННОЙ НА ИНТЕРВАЛЕ НЕУДАЧ Российский патент 2005 года по МПК G06F9/38 

Область техники, к которой относится изобретение

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

Предшествующий уровень техники

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

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

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

Описание чертежей

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

Фиг.2 представляет частичную блок-схему последовательности серии адресов в памяти и кэш-памяти в соответствии с вариантом осуществления настоящего изобретения.

Фиг.3 представляет частичную блок-схему таблицы критических неудачных предварительных выборок в соответствии с вариантом осуществления настоящего изобретения.

Фиг.4 представляет схему последовательности операций способа управления предварительными выборками данных в соответствии с вариантом осуществления настоящего изобретения.

Фиг.5 представляет частичную блок-схему таблицы единственных неудач и таблицы критических неудачных предварительных выборок в соответствии с другим вариантом осуществления настоящего изобретения.

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

Фиг.7 представляет частичную блок-схему входной таблицы и выходной таблицы в соответствии с другим вариантом осуществления настоящего изобретения.

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

Подробное описание

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

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

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

На фиг.1 представлена частичная блок-схема компьютерной системы 100, имеющей устройство 120 предварительных выборок в соответствии с вариантом осуществления настоящего изобретения. Компьютерная система 100 включает в себя процессор 101, который имеет декодер 110, подсоединенный к устройству 120 предварительных выборок. Компьютерная система 100 также имеет исполнительное устройство 107, которое подсоединено к декодеру 110 и устройству 120 предварительных выборок. Термин "подсоединено" охватывает прямое подключение, непрямое подключение, непрямую связь и т.д. Процессором 101 может быть любой микропроцессор, способный обрабатывать команды, например, такой как универсальный процессор в семействе процессоров INTEL PENTIUM. Исполнительное устройство 107 представляет собой устройство, которое выполняет команды. Декодером 110 может быть устройство или программа, изменяющая один тип кодирования на другой тип кодирования, который может быть выполнен. Например, декодер 110 может декодировать команду LOAD, которая является частью программы, а декодированная команда LOAD затем может исполняться исполнительным устройством 107. Процессор 101 подсоединен к кэш-памяти 130 и оперативному запоминающему устройству (ОЗУ) 140. ОЗУ 140 представляет собой системную память. В других вариантах осуществления в компьютерной системе 100 вместо ОЗУ 140 или в дополнение к нему можно использовать тип системной памяти, отличающийся от ОЗУ. Кэш 130 может быть статической ОЗУ (СОЗУ). В другом варианте осуществления кэш 130 может быть частью процессора 101.

Устройство 120 предварительных выборок включает в себя диспетчер 122 предварительных выборок и память 125 предварительных выборок. Диспетчер 122 предварительных выборок может включать в себя логику для данных предварительных выборок, предназначенных для команды, основанные на интервале между неудачными обращениями к кэш, вызванными командой. Как это используется в данном применении, "логика" может включать в себя логические схемы аппаратного обеспечения, типа схем, которые "зашиты" для выполнения операций, или логику программы, типа встроенного программного обеспечения, которое выполняет операции. Память 125 предварительных выборок может хранить таблицу критических неудачных предварительных выборок, содержащую входные сообщения, которые включают в себя интервал между неудачными обращениями к кэш, вызванными командой. В варианте осуществления, память 125 предварительных выборок представляет собой ассоциативную память (АП). Примеры таблиц критических неудачных предварительных выборок обсуждаются ниже со ссылкой на фиг. 3, 5 и 7. Диспетчер 122 предварительных выборок может определять адреса элементов данных, подлежащих предварительной выборке, на основании интервала неудач, который записан для команд в таблице предварительных выборок.

На фиг.2 представлена частичная блок-схема серии адресов в памяти и кэш-памяти в соответствии с вариантом осуществления настоящего изобретения. Фиг. 2 изображает часть ОЗУ 140 и кэш 130. ОЗУ 140 содержит серию ячеек или местоположений памяти, каждое из которых имеет однозначный адрес. На фиг.2 каждый десятый адрес в последовательности от адреса 1000 до 1100 помечен номером адреса. Фиг. 2 показывает, что в кэш 130 хранится копия данных по адресам 1010, 1020, 1040, 1050, 1070, 1080 и 1100 из ОЗУ 140.

Фиг.2 используется для иллюстрации комбинации неудачных обращений к кэш для команды, которая неоднократно выполняется процессором 101. Команда может быть, например, конкретной командой LOAD (загрузки) в программе. Эта команда может быть идентифицирована значением указателя команды, которое упоминается в общем как УК = XXXX. В примерной программе, команда неоднократно исполняется процессором 101 в относительно коротком периоде времени. Это обычно происходит, если команда является частью цикла, но это также может происходить в других случаях. Команда LOAD при УК = XXXX, используемая в этом примере, может загружать элемент данных, хранящийся по отличающемуся адресу памяти, каждый раз, когда исполняется команда LOAD. В иллюстрируемом на фиг. 2 примере сделано предположение, что команда начинается загрузкой из адреса 1000 и что команда имеет шаг 201 по индексу, равный десяти. То есть, в течение соответствующей части рассматриваемой программы команда в этом примере сначала загружается из адреса 1000, а затем загружается из каждой десятой ячейки, которая следует за ним (например, 1000, 1010, 1020, 1030, 1040, 1050, 1060, 1070, 1080, 1090, 1100,...).

Когда команда LOAD согласно этому примеру включена в исполнительный цикл, процессор 101 пытается получить данные, необходимые для исполнения команды LOAD, из кэш-памяти 130. В показанном на фиг. 2 примере данные, необходимые для исполнения команды LOAD при загрузке из адресов 1010, 1020, 1040, 1050, 1070, 1080 и 1100, находятся в кэш. Эти адреса можно назвать "кэшированными". Для простоты, в этом примере адреса запоминаются в кэш в таком же порядке, в каком они появляются в ОЗУ 140, но, конечно, они могут запоминаться в кэш 130 в любом порядке. Фиг. 2 изображает, что адреса 1000, 1030, 1060 и 1090 не кэшированы. Таким образом, неудачное обращение к кэш будет происходить, когда команда LOAD загружается из адресов 1000, 1030, 1060 и 1090. В этом примере, интервал неудач 202 между первым адресом в серии адресов, который вызвал неудачное обращение к кэш, и следующим адресом, который вызвал неудачное обращение к кэш, составляет 30 (то есть, 1030-1000=30).

Устройство критических неудачных предварительных выборок в соответствии с одним вариантом осуществления данного изобретения выполняет предварительную выборку данных, которая может привести к неудачному обращению к кэш при исполнении команды LOAD с УК = XXXX. В варианте осуществления, эти данные предварительно выбираются посредством предварительной выборки, основанной на информации из таблицы критических неудачных предварительных выборок, которая может храниться в памяти 125 предварительных выборок.

Фиг.3 представляет частичную блок-схему таблицы 300 критических неудачных предварительных выборок в соответствии с вариантом осуществления настоящего изобретения. Таблица критических неудачных предварительных выборок имеет восемь записей, которые показаны номером 310 записи от 1 до 8, хотя в этом варианте осуществления номер записи дан только для целей, иллюстрации и не является полем (элементом) в таблице. В другом варианте осуществления, таблица 300 критических неудачных предварительных выборок может иметь больше или меньше записей. Каждая запись может содержать информацию для одной команды. Как показано на фиг.3, таблица 300 критических неудачных предварительных выборок имеет пять полей, но в других вариантах осуществления она может иметь больше или меньше полей. Первое поле в таблице 300 критических неудачных предварительных выборок представляет собой поле 301 УК команды. Это поле содержит указатель команд для команды, с которой связана запись. Как показано на фиг. 3, первая запись хранит значение указателя команды XXXX. Следующим полем в таблице 300 критических неудачных предварительных выборок является поле 302 адресов последних неудач. Это поле хранит адрес последнего неудачного обращения к кэш для команды. Показанный на фиг.3 пример содержит адрес последней неудачи 1030, который указывает, что последним адресом, пропущенным при выполнении команды LOAD с УК = XXXX, был адрес 1030. Следующим полем в таблице 300 критических неудачных предварительных выборок является поле 303 интервалов неудач. В варианте осуществления это поле хранит интервал между последними двумя последовательными неудачными обращениями к кэш для команды. Например, если первое неудачное обращение к кэш произошло при загрузке адреса 1000, а следующее неудачное обращение к кэш произошло при загрузке адреса 1030, то интервал неудач, хранящийся в поле 303 интервалов неудач, представляет собой 30. Следующими полями в таблице 300 критических неудачных предварительных выборок являются поле 304 повторяющихся неудач и подтвержденное поле 305. Эти поля можно использовать в варианте осуществления изобретения, который включает в себя шумовой фильтр для предотвращения загрязнения таблицы 300 критических неудачных предварительных выборок и/или данных неудач шумовыми неудачами. В варианте осуществления, каждое из этих полей занимает один бит. Действие этих полей и общее действие устройства критических неудачных предварительных выборок описано ниже со ссылкой на фиг.4.

Фиг.4 представляет схему последовательности операций способа управления предварительной выборки данных в соответствии с вариантом осуществления настоящего изобретения. Эта схема последовательности операций может использоваться для иллюстрации того, как устройство 120 предварительных выборок согласно фиг.1 может осуществлять предварительную выборку набора данных, типа показанной на фиг.2. Ради этого примера предположим, что таблица 300 критических неудачных предварительных выборок теперь не имеет никаких записей, что процессор 101 исполняет команду с УК = XXXX в первый раз и что команда УК = XXXX в первый раз выполняет эту загрузку из адреса 1000 и каждого десятого адреса после него. Предположим также, что кэш находится в состоянии, показанном на фиг.2.

Как показано на фиг.4, способ включает в себя определение, что неудачное обращение к кэш было во время исполнительного цикла команды XXXX, когда она загружалась из первого адреса (401 на фиг.4). На основании состояния кэш, показанного на фиг.2, команда УК = XXXX приводит к неудачному обращению к кэш для адреса 1000. Затем, диспетчер 122 предварительных выборок определяет, содержит ли таблица 300 критических неудачных предварительных выборок запись для УК = XXXX (402 на фиг.4). Для первого неудачного обращения к кэш, таблица 300 критических неудачных обращений к кэш не будет содержать записи для УК = XXXX. В соответствии с вариантом осуществления, в таблице 300 критических неудачных предварительных выборок для УК = XXXX будет тогда создана запись (403 на фиг. 4). В варианте осуществления создание новой записи включает в себя запоминание в таблице адреса последней неудачи (здесь 1000). В этом варианте осуществления, когда позже происходит вторая неудача для этой команды, диспетчер 122 предварительных выборок определяет, что интервал неудач равен 30 (1030-1000) и сохраняет это значение в поле 303 интервалов неудач. Отметим на основании фиг.2, что для адресов 1010 и 1020 неудача не будет происходить, поскольку эти адреса имеются в кэш.

В другом варианте осуществления, в котором используется методика фильтрации шума, адрес последней неудачи не запоминается до тех пор, пока для этой команды не происходит вторая неудача. В этом варианте осуществления используется поле 304 повторяющихся неудач для указания, произошли ли по меньшей мере две неудачи для команды, которая соответствует записи. В этом варианте осуществления, бит повторяющихся неудач стирается, когда создается новая запись в таблице 300 критических неудачных предварительных выборок. Когда происходит следующая неудача для команды XXXX по адресу = 1030, устройство предварительных выборок проверяет таблицу 300 критических неудачных предварительных выборок, определяет, что таблица имеет запись для команды XXXX, но что для этой записи бит повторяющихся неудач не установлен, устанавливает бит повторяющихся неудач, и только после этого сохраняет значение в поле 302 адресов последних неудач. В этом случае адрес последней неудачи будет 1030. В соответствии с этим вариантом осуществления, адрес последней неудачи для шумовых неудач, которые происходят только однажды, даже не будет записан.

Предположим для иллюстрации, что методика фильтрации шума не используется, что вторая неудача уже произошла и, таким образом, что запись содержит значение 30 в качестве интервала неудач и значение 1030 в качестве адреса последней неудачи. Когда происходит следующая неудача для УК = XXXX по адресу 1060, устройство предварительных выборок определяет, имеет ли таблица 300 критических неудачных обращений к кэш запись для УК = XXXX (402 на фиг.4). Затем устройство критических неудачных предварительных выборок определяет, является ли адрес предыдущей неудачи (в этом примере, значение 1030 в поле 302 адресов последних неудач) интервалом неудач от адреса данной неудачи (404 на фиг.4). Поскольку новая неудача находится на предсказанном интервале неудач, то в этом варианте осуществления диспетчер 122 предварительных выборок осуществляет предварительную выборку данных, которые находятся на расстоянии интервала неудач от данной неудачи (405 на фиг. 4). Таким образом, для более позднего использования при выполнении команды с УК = XXXX будут предварительно выбраны данные по адресу 1090. В варианте осуществления изобретения данные, подлежащие предварительной выборке, предварительно выбираются в кэш-память 130 и отмечаются для указания, что они были предварительно выбраны. В варианте осуществления маркировка выполняется с использованием бита в записи кэш для элемента данных, и этот бит может упоминаться как "виртуальный бит". В дополнительном варианте осуществления виртуальный бит может служить в качестве универсального бита. Для целей поддержания правильной комбинации в таблице критических неудачных предварительных выборок, если загруженные из кэш данные отмечены как предварительно выбранные, то такая загрузка определяется и понимается устройством предварительных выборок как неудачное обращение к кэш. То есть, когда такие отмеченные данные запрашиваются из кэш 130 во время исполнения команды, данные будут выдаваться из кэш 130, но диспетчер 122 предварительных выборок будет действовать, как будто произошло неудачное обращение к кэш. В другом варианте осуществления, предварительно выбираемые данные загружаются в буфер (не показанный), а не в кэш. Этот буфер действует, как кэш предварительно выбираемых данных. В этом варианте осуществления, неудачное обращение к кэш происходит даже при том, что данные находятся в буфере, но поскольку данные могут быть получены из буфера без загрузки из ОЗУ, выполнение команды по-прежнему эффективно.

После посылки запроса на предварительную выборку данных, диспетчер 122 предварительных выборок обновляет запись таблицы 300 критических предварительных выборок для УК = XXXX команды (406 на фиг.4). Например, диспетчер предварительных выборок сохраняет адрес текущего неудачного обращения к кэш в поле адресов последних неудач.

Если интервал неудач, хранящийся в поле 303 интервалов неудач, отличается от интервала неудач для текущей неудачи (404 на фиг.4), то в варианте осуществления данные не являются предварительно выбираемыми. В этом варианте осуществления диспетчер предварительных выборок может обновлять запись таблицы 300 критических неудачных предварительных выборок для УК = XXXX команды, запоминая новый интервал неудач и новый адрес последней неудачи (407 на фиг.4). Вариант осуществления, который включает в себя фильтр для предотвращения пересчета интервала неудач на основании шумовых неудач, обсуждается ниже в отношении поля 514 несовпадений на фиг.5.

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

В другом варианте осуществления, в котором используется методика фильтрации шума, интервал неудач не используется для данных предварительных выборок до тех пор, пока не будет получено подтверждение. В этом варианте осуществления, подтвержденное поле 305 (поле подтверждения) таблицы 300 критических неудачных предварительных выборок может использоваться для указания, произошли ли две последовательные неудачи для команды на интервале неудач. В этом варианте осуществления бит подтверждения может быть очищен, когда в таблице 300 критических неудачных предварительных выборок создается новое входное сообщение. Предположим, что в записи сохраняется интервал неудач, когда для команды XXXX происходит вторая неудача. Когда для команды XXXX происходит третья неудача, устройство предварительных выборок проверяет таблицу 300 критических неудачных предварительных выборок и определяет, находится ли адрес, пропущенный для третьей неудачи, на расстоянии интервала неудач от адреса последней неудачи. Если интервал адресов неудач, хранящийся в поле 303 интервалов неудач, точно предсказал интервал неудачи для текущей неудачи, то устанавливается бит подтверждения. Если интервал неудачи для третьей неудачи отличается от интервала неудачи, хранящегося в записи, то бит подтверждения в этот раз не устанавливается. В соответствии с этим вариантом осуществления, диспетчер 122 предварительных выборок не заставляет делать предварительную выборку данных для команды, пока в таблице 300 критических неудачных предварительных выборок не установлен бит подтверждения, который соответствует команде.

Фиг.5 представляет частичную диаграмму таблицы 520 единственных неудач и таблицы 510 критических неудачных предварительных выборок в соответствии с другим вариантом осуществления настоящего изобретения. Эта частичная диаграмма иллюстрирует, помимо прочего, две различные методики фильтрации шума. Одна методика ограничивает создание новых записей в таблице 510 критических неудачных предварительных выборок, используя таблицу 520 единственных неудач для хранения УК команд, для которых имеется только одна неудача. Эта методика, которую можно назвать как "подход с двумя таблицами", обеспечивает меньший размер таблицы. Вторая методика использует поле 514 несовпадений для предотвращения пересчета интервала неудач на основании шумовых неудач. Эти методики можно использовать отдельно или в комбинации.

Теперь будет описан подход с двумя таблицами. В иллюстрируемом варианте осуществления таблица 510 критических неудачных предварительных выборок обеспечивает возможность четырех записей, а таблица 520 единственных неудач обеспечивает возможность более четырех записей. Каждая запись в таблице 520 единственных неудач может иметь единственное поле, а именно, поле 521 УК команды. Таким образом, каждая запись в таблице 520 единственных неудач может хранить указатель команды для команды (например, XXXX, YYYY, ZZZZ и т.д.). Таблица 510 критических неудачных предварительных выборок подобна таблице 300 критических неудачных предварительных выборок на фиг. 3. Таблица 510 критических неудачных предварительных выборок имеет поле 511 УК команды, поле 512 адресов последних неудач, поле 513 интервалов неудач, поле 514 несовпадений и поле 515 подтверждения. Таблица 500 критических неудачных предварительных выборок не имеет поля 304 повторяющихся неудач, показанного в таблице 300 критических неудачных предварительных выборок, поскольку выполняемые функции поля повторяющихся неудач заранее выполняются таблицей 520 единственных неудач. В этом варианте осуществления, когда происходит неудача, устройство 120 предварительных выборок определяет, имеет ли таблица 510 критических неудачных предварительных выборок запись для команды, которая вызвала неудачу. Если таблица 510 критических неудачных предварительных выборок не имеет записи для команды, то устройство 120 предварительных выборок определяет, имеет ли таблица 520 единственных неудач запись для команды. Если таблица 520 единственных неудач не имеет запись для команды, то входное сообщение для команды создается в таблице 520 единственных неудач. Если таблица 520 единственных неудач имеет запись для команды, то запись для команды создается в таблице 510 критических неудачных предварительных выборок. Когда используется методика фильтрации шума по данному варианту осуществления, запись для команды не будет создаваться в таблице 510 критических неудачных предварительных выборок, если для команды не произошли две неудачи. (Более точно, запись для команды не будет создаваться в таблице 510 критических неудачных предварительных выборок, если таблица 520 единственных неудач не имеет записи о более ранней неудаче, которая произошла для команды.) Таким образом, запись не будет создаваться в таблице 510 критических неудачных предварительных выборок, если команда вызвала только одну шумовую неудачу.

Поле 514 несовпадений таблицы 510 критических неудачных предварительных выборок используется для предотвращения пересчета интервала неудач на основании шумовых неудач. Если интервал неудач был установлен для команды и позже происходит неудача, которая находится не на интервале неудач, это может указывать на начало новой комбинации неудач, когда интервал неудач должен быть пересчитан. Однако, неудача на новом интервале может быть просто шумовой неудачей, и в этом случае интервал неудач не должен быть пересчитан. Например, если мы видоизменили набор данных, показанный на фиг. 2, так, чтобы адрес 1070 не хранился в кэш-памяти 130, по некоторым причинам, не связанным с истинной комбинацией интервалов неудач для команды, то загрузка адреса 1070 после этого вызовет неудачу с интервалом неудач, равным 10 (1070-1060=10), даже при том, что истинная комбинация интервалов неудач для команды имеет интервал неудач, равный 30. В соответствии с вариантом осуществления, всякий раз, когда неудача происходит на интервале, отличающемся от интервала, хранящегося в поле 513 интервалов неудач, устройство предварительных выборок проверяет бит соответствия в поле 514 несовпадений. Если бит соответствия в этой ситуации не установлен, то устройство предварительных выборок устанавливает бит соответствия и не сохраняет новый интервал в поле 513 интервалов неудач. Если бит соответствия установлен, то устройство предварительных выборок сохраняет новый интервал неудач в поле 513 интервалов неудач и очищает бит соответствия. Наконец, бит неудачи очищается всякий раз, когда неудача происходит на интервале, хранящемся в поле 513 интервалов неудач. Таким образом, единственная неудача на новом интервале неудач полагается, как шумовая неудача, но две неудачи в строке на интервале, отличающемся от интервала неудач, вызывают перерасчет бита несовпадения.

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

Компьютерная система 600 может иметь процессор 601, имеющий декодер 110 и исполнительное устройство 107, которая может быть аналогична компьютерной системе 100 на фиг.1. Кроме того, компьютерная система 600 может иметь кэш 130 и ОЗУ 140. Кэш 130 представляет собой часть процессора 601, но в других вариантах осуществления кэш 130 может быть вне процессора 601. Процессор 601 может иметь второе устройство 650 предварительных выборок, которое подсоединено к декодеру 110, исполнительному устройству 107 и ОЗУ 140. Устройство 620 критических неудачных предварительных выборок может иметь логику 621 создания входных сообщений, логику 622 обновления интервала неудач, логику 623 противопомехового фильтра и логику 624 замены входных сообщений. Процессор 601 может иметь память 626 и память 628, которые подсоединены к устройству 620 критических неудачных предварительных выборок и используются им.

Второе устройство 650 предварительных выборок может содержать логику предварительной выборки с целью предварительного выбора элемента данных для использования командой. В варианте осуществления, второе устройство 650 предварительных выборок работает вместе с устройством 620 критических неудачных предварительных выборок, но использует отличающийся механизм предварительных выборок. Например, второе устройство 650 предварительных выборок может быть буфером «подсказок», и устройство критических неудачных предварительных выборок и буфер «подсказок» оба могут обеспечивать данные предварительных выборок для программы в одно и то же время. В этом варианте осуществления, устройство критических неудачных предварительных выборок и буфер подсказок могут дополнять друг друга.

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

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

На фиг.7 представлена частичная блок-схема входной таблицы 710 и выходной таблицы 720 в соответствии с другим вариантом осуществления настоящего изобретения. В варианте осуществления используется схема индексации для повышения эффективности устройства критических неудачных предварительных выборок посредством разбиения критической таблицы неудачных предварительных выборок на две части и расположения части таблицы критических неудач (входную таблицу) в начале процессорного конвейера. В этом варианте осуществления, входная таблица 710 и выходная таблица 720 обеспечивают возможность для одинакового количества записей, и каждая запись во входной таблице 710 соответствует записи в выходной таблице 720. Как и прежде, каждая запись в таблицах имеет отношение к команде. В варианте осуществления, записи во входной таблице 710 содержат значение указателя команды в поле 701 УК команды. В этом варианте осуществления выходная таблица 720 содержит поле 702 адресов последних неудач, поле 703 интервалов неудач, поле 704 повторяющихся неудач и поле 705 подтверждения. Выходная таблица 720 составляет основную таблицу предварительных выборок, но она не сохраняет любую информацию, идентифицирующую команду, с которой связана запись. Устройство предварительных выборок определяет местоположение записи, которую нужно считать или обновить в выходной таблице 720, посредством поиска УК команды во входной таблице 710. Например, чтобы обновить поле 702 адресов последних неудач записи для XXXX в выходной таблице 720, устройство предварительных выборок определяет, что первая запись в обеих таблицах имеет отношение к команде с УК = XXXX, находя значение XXXX в первой записи входной таблицы 710. Таким образом, входную таблицу 710 и выходную таблицу 720 можно обрабатывать, как будто они составляют единую таблицу.

В варианте осуществления, память 626 на фиг. 6 хранит входную таблицу 710, а память 628 хранит выходную таблицу 720. В дополнительном варианте осуществления, память 628 расположена ближе к кэш 130, чем к декодеру 110, а память 626 расположена ближе к декодеру 110, чем к кэш 130. Таким образом, УК, который может составлять 32 бита, не должен распространяться полностью до конца конвейера.

На фиг. 8 представлена частичная блок-схема компьютерной системы 800, имеющей устройство предварительных выборок в соответствии с другим вариантом осуществления настоящего изобретения. Компьютерная система 800 может иметь процессор 801, имеющий декодер 110, исполнительное устройство 107 и память 125 таблицы предварительных выборок, которая может быть подобна компьютерной системе 100 на фиг.1. Кроме того, компьютерная система 800 может иметь кэш 130 и ОЗУ 140. Процессор 801 также может иметь устройство 820 предварительных выборок, которое включает в себя аппаратное средство 822 устройства предварительных выборок и машиночитаемый носитель информации 823. Машиночитаемый носитель информации 823 может хранить команды 824 устройства предварительных выборок, которые могут быть исполняемыми командами, которые исполняются с помощью аппаратного средства 822 устройства предварительных выборок для выполнения одного или больше способов критических неудачных предварительных выборок, описанных выше. Подразумевается, что фраза "исполняемые команды", используемая здесь, охватывает объектную программу, исходную программу, встроенные программы, микропрограмму и т.д. и включает в себя команды, хранящиеся в сжатом и/или зашифрованном формате, а также команды, которые должны быть скомпилированы или инсталлированы инсталлятором перед исполнением процессором.

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

Изобретение относится к вычислительной технике и, в частности, к способу выполнения команд с использованием предварительной выборки данных и процессору для реализации такого способа. Его использование позволяет получить технический результат в виде повышения эффективности работы компьютерных систем при снижении количества неудачных обращений к кэш-памяти и в виде снижения времени, затрачиваемого на ожидание доступа к ОЗУ. Технический результат достигается за счет того, что процессор содержит первую память для хранения данных, кэш-память для хранения данных, декодер для декодирования команды, подлежащей выполнению, при этом команда имеет операнд данных, схему предварительной выборки для предварительной выборки операнда данных для команды из первой памяти в кэш-память на основании интервала между неудачными обращениями к кэш, вызванными командой, как указано записью, соответствующей команде, в таблице предварительных выборок, которая сохранена в памяти схемы предварительной выборки. При этом, таблица предварительных выборок содержит записи, которые включают в себя интервал между неудачными обращениями к кэш, вызванными командами, а таблица предварительных выборок содержит запись для команды, только если эта команда вызвала по меньшей мере два неудачных обращения к кэш. 2 н. и 11 з.п. ф-лы, 8 ил.

1. Процессор, содержащий первую память для хранения данных, кэш-память для хранения данных, декодер для декодирования команды, подлежащей выполнению, при этом команда имеет операнд данных, схему предварительной выборки для предварительной выборки операнда данных для команды из первой памяти в кэш-память на основании интервала между неудачными обращениями к кэш, вызванными командой, как указано записью, соответствующей команде в таблице предварительных выборок, которая сохранена в памяти схемы предварительной выборки, причем таблица предварительных выборок содержит записи, которые включают в себя интервал между неудачными обращениями к кэш, вызванными командами, и при этом таблица предварительных выборок содержит запись для команды, только если эта команда вызвала по меньшей мере два неудачных обращения к кэш, и блок выполнения для выполнения декодированной команды с использованием предварительно выбранного операнда данных.2. Процессор по п.1, в котором схема предварительных выборок имеет «шумовой» фильтр для предотвращения по меньшей мере одного типа «шумовой» неудачи от изменения интервала неудач, используемого для предварительной выборки данных.3. Процессор по п.1, в котором записи в таблице предварительных выборок имеют поле повторяющихся неудач для указания, была ли обнаружена для команды больше, чем одна неудача.4. Процессор по п.1, в котором записи в таблице предварительных выборок также имеют поле несовпадений для указания, имела ли место предыдущая неудача на интервале, который соответствует интервалу, хранящемуся в поле интервалов неудач.5. Процессор по п.1, в котором таблица предварительных выборок не хранит какую-либо информацию, идентифицирующую команду, к которой относится каждая запись.6. Процессор по п.1, в котором схема предварительной выборки сохраняет предварительно выбранные данные в кэш-памяти с индикацией, что эти данные были подвергнуты предварительной выборке.7. Способ выполнения команд с использованием предварительной выборки данных, содержащий этапы: определяют, что было неудачное обращение к кэш во время исполнительного цикла команды, которая загружается из первого адреса, определяют, содержит ли первая таблица предварительных выборок запись для этой команды, причем эта запись хранит интервал неудач и хранит второй адрес, который был вызван последним неудачным обращением к кэш для команды, и запись, хранящую поле подтверждения для указания, был ли подтвержден сохраненный интервал между неудачными обращениями к кэш, предварительно выбирают операнд данных для последующего выполнения команды, если первая таблица предварительных выборок содержит запись для команды, на основании, частично, информации, хранящейся в записи, создают новую запись в первой таблице предварительных выборок для команды, если первая таблица предварительных выборок не содержит запись для команды, причем новая запись заменяет запись в таблице предварительных выборок, которая имеет поле подтверждения, указывающее, что интервал между неудачными обращениями к кэш, сохраненный в этой заменяемой записи, был подтвержден, только если другие записи в таблице предварительных выборок также содержат поле подтверждения, которое указывает, что интервал между неудачными обращениями к кэш, сохраненный в этих других записях, был подтвержден, и выполнение команды с использованием предварительно выбранного операнда.8. Способ по п.7, в котором этап определения - следует ли предварительно выбирать данные - содержит этап определения того, что запрос предварительной выборки должен быть послан, если интервал между первым адресом и вторым адресом равен хранящемуся интервалу неудач.9. Способ по п.7, в котором этап определения - содержит ли первая таблица предварительных выборок запись для команды - содержит этап определения, если запись во второй таблице предварительных выборок содержит информацию, идентифицирующую команду, причем вторая таблица предварительной выборки хранится в памяти, отличной от памяти для первой таблицы предварительных выборок.10. Способ по п.7, в котором запись для команды в первой таблице предварительных выборок содержит поле несовпадений и при этом поле несовпадений указывает, произошла ли последняя неудача для команды на интервале неудач, хранящемся в записи, когда была обработана последняя неудача.11. Способ по п.7, дополнительно содержащий этапы: определяют, что интервал между первым адресом и вторым адресом не равен интервалу неудач, если поле несовпадений указывает, что последняя неудача произошла на хранящемся интервале неудач, обновляют поле несовпадений для указания, что последняя неудача для команды не произошла в хранящемся интервале неудач, и, если поле несовпадений указывает, что последняя неудача не произошла на хранящемся интервале неудач, сохраняют интервал неудач в поле интервалов неудач и обновляют поле несовпадений для указания, что последняя неудача для команды не произошла в хранящемся интервале неудач.12. Способ по п.7, в котором создают запись в первой таблице предварительных выборок для команды, если первая таблица предварительных выборок не содержит запись для команды, а вторая таблица предварительных выборок содержит запись для команды, и в котором дополнительно создают запись во второй таблице предварительных выборок для команды, если первая таблица предварительных выборок не содержит запись для команды и вторая таблица предварительных выборок не содержит запись для команды.13. Способ по п.7, в котором первая таблица предварительных выборок не хранит какую-либо информацию, идентифицирующую команду, к которой относится запись.