Область техники, к которой относится изобретение
Данное изобретение имеет отношение к устройствам кэш-памяти. Конкретнее изобретение касается распределенного разрешения противоречий в многопроцессорной системе, имеющей множество устройств кэш-памяти.
Предшествующий уровень техники
Если электронная система включает в себя множество устройств кэш-памяти (кэшей), то должна быть обеспечена достоверность доступных для использования данных. Обычно это достигается за счет манипулирования данными в соответствии с протоколом когерентности кэш-памяти. При увеличении количества кэшей и/или процессоров также усложняется поддержание когерентности кэша.
Когда многочисленные компоненты (например, кэш-память, процессор) запрашивают один и тот же блок данных, конфликт между различными компонентами должен быть решен способом, поддерживающим достоверность данных. Существующие в данное время протоколы когерентности кэш-памяти обычно имеют единственный компонент, ответственный за разрешение конфликтов. Однако так как сложность системы увеличивается, зависимость разрешения конфликтов от единственного компонента может уменьшить производительность системы в целом.
На Фиг.1a-1e показана концептуальная иллюстрация конфликтной ситуации в многоузловой системе. Узлы 110, 120 и 130 являются одноранговыми узлами, которые могут хранить копию запрашиваемых данных (например, строку кэша) в кэш-памяти. Базовый узел 140 является для запрашиваемых данных базовым (H) узлом. В примере по Фиг. с 1а по 1e одноранговые узлы 110 и 120 хранят недостоверную копию или не хранят вообще никакой копии запрашиваемых данных, а одноранговый узел 130 хранит измененную копию запрашиваемых данных, которая не была перезаписана в память. Базовый узел хранит в памяти первоначальную копию данных или измененные варианты данных, если изменения перезаписаны в память.
Как показано на Фиг.1a, одноранговый узел 120, чтобы запросить копию блока данных, например строку кэша, передает сообщение "Запрос Данных" (Data Request). Сообщение "Запрос Данных" передают одноранговому узлу 110 и одноранговому узлу 130. Однако сообщение "Запрос Данных" к одноранговому узлу 130 задерживают. Задержка может быть вызвана, например, нехваткой доступной полосы пропускания, буферизацией и т.д.
Одноранговый узел 110 отвечает на сообщение "Запрос Данных" однорангового узла 120 сообщением "Отсутствие Достоверной Копии" (No Valid Copy), которое указывает одноранговому узлу 120 на то, что одноранговый узел 110 не имеет достоверной копии запрашиваемых данных. Через некоторое время после передачи одноранговым узлом 120 сообщения "Запрос Данных" одноранговый узел 110, как показано на Фиг.1c, передает сообщение "Запрос Данных" одноранговым узлам 120 и 130, запрашивая те же данные, которые запрашивал одноранговый узел 120.
Одноранговый узел 120 отправляет одноранговому узлу 110 в ответ на сообщение "Запрос Данных" сообщение "Отсутствие Достоверной Копии". Одноранговый узел 130 отправляет запрашиваемые данные одноранговому узлу 110. Копия данных, если таковая имеется, поддерживаемая одноранговым узлом 130, помечена как недостоверная, а копия данных, сохраненная одноранговым узлом 110, помечена как Измененная.
Через некоторое время после того, как одноранговый узел 130 ответил на "Запрос Данных" однорангового узла 110 и пометил копию данных как недостоверную, как достоверное одноранговый узел 130, как показано на Фиг.1c, принимает задержанное сообщение "Запрос Данных" от однорангового узла 120. В ответ на сообщение "Запрос Данных" одноранговый узел 130 отправляет сообщение "Отсутствие Достоверной Копии" одноранговому узлу 120. Необходимо отметить, что состояние данных, хранимых одноранговым узлом 130, изменено со времени первоначального сообщения "Запрос Данных" ко времени ответа однорангового узла 130 на сообщение "Запрос Данных".
Поскольку одноранговые узлы 110 и 130 отвечают на сообщение "Запрос Данных" однорангового узла 120 сообщениями "Отсутствие Достоверной Копии", одноранговый узел 120, не обнаружив ни одной достоверной кэшированной копии запрашиваемых данных, запрашивает копию данных у базового узла 140. Таким образом, как показано на Фиг.1d, одноранговый узел передает сообщение "Чтение" (Read) базовому узлу 140. Базовый узел 140 извлекает запрашиваемые данные из памяти и отправляет данные одноранговому узлу 120. Одноранговый узел 120 затем сохраняет запрошенные данные в Исключительном (Exclusive) состоянии.
Как показано на Фиг.1e, последовательность сообщений, показанная на Фиг.с 1а по 1e, приводит в результате к существованию двух несовместимых копий строки данных. В приведенном примере одноранговый узел 110 хранит копию данных в Измененном состоянии, а одноранговый узел 120 хранит копию данных в Исключительном состоянии. Однако копия, сохраненная одноранговым узлом 120, не является исключительной по отношению к одноранговому узлу 120. Таким образом, в многоузловых системах при некоторых обстоятельствах могут возникать несовместимые копии данных, если не обеспечен механизм для разрешения конфликтов кэша.
Перечень фигур чертежей
Данное изобретение показано в виде не являющегося ограничением примера на сопроводительных чертежах, на которых одинаковые ссылочные номера обозначают подобные элементы.
Фиг. с 1a по 1e - концептуальные представления состояния конфликта в многоузловой системе.
Фиг.2a и 2b - концептуальные представления запроса совместно используемой кэшированной строки.
Фиг.3а и 3b - концептуальные представления запроса совместно используемой некэшированной строки.
Фиг. с 4a по 4f - концептуальные представления трехсторонних конфликтующих запросов совместно используемой строки.
Фиг. с 5a по 5g - концептуальные представления трехсторонних конфликтующих запросов совместно используемой строки.
Фиг.6 - блок-схема одного из вариантов выполнения узла.
Фиг.7 - один из вариантов выполнения многопроцессорной системы.
Подробное описание изобретения
Здесь описаны способы использования единственного пакета как контейнера для множества сообщений протокола кэша. В следующем далее описании с пояснительными целями изложены многочисленные частные подробности для обеспечения досконального понимания данного изобретения. Однако для любого, имеющего соответствующую квалификацию в данной области техники, будет очевидно, что изобретение может быть выполнено без этих частных подробностей. В других примерах во избежание неясного понимания изобретения схемы и устройства показаны в виде блок-схем.
Сообщения Запроса
Следующие сообщения являются запросами данных/действия от запрашиваемого узла. Эти сообщения являются широковещательными ко всем узлам системы.
Считать Строку (Port Read Line, PRL): Это запрос копии сегмента данных, такого как, например, строка кэша.
Считать Недостоверную Строку (Port Read Invalidate Line, PRIL): Это запрос копии сегмента данных, в случае если копия данных узла-поставщика является недостоверной. Это сообщение может также упоминаться как "запрос на вступление во владение".
Записать строку (Port Write Line, PWL): Это сообщение инициирует запись данных (например, измененной строки кэша) в память. Это сообщение может также упоминаться как "замещение испорченных данных".
Пометить строку как Недостоверную (Port Invalidate Line, PIL): Это сообщение вызывает изменение состояния намеченных данных c состояния Совместного Использования на Исключительное состояние.
Записать Строку и пометить как Недостоверную (Port Write Invalidate Line, PWIL): Это сообщение инициирует запись данных в память и делает целевую копию данных недостоверной.
Ответные сообщения
Следующие сообщения являются сообщениями, отправленными от одноранговых (то есть небазовых) узлов на запрашивающий узел в ответ на запросы, описанные выше.
Подтверждение Недостоверного Состояния (Invalid State Acknowledgement, IACK): Это сообщение является ответом на запрос (PRL, PRIL, PIL, PWIL), когда узел, отправляющий ответ, имеет недостоверную копию запрашиваемых данных или вообще не имеет копии запрашиваемых данных.
Подтверждение Состояния Совместного Использования (Shared State Acknowledgement, SACK): Это сообщение является ответом на запрос PRL, когда на узле, отправляющем ответ, имеется копия запрашиваемых данных в состоянии Совместного Использования.
Подтверждение Приема Данных (Acknowledgement of Data Received, DACK): Это сообщение подтверждает прием запрашиваемых данных. Это сообщение отправляет базовый узел, когда базовый узел принимает сообщение CNCL. Целевым узлом для сообщения DACK является узел пересылки, включенный в сообщение CNCL. Узел, принимающий переданные данные или данные памяти базового узла, не отвечает отправляющему узлу.
Конфликт(CNFL): Это сообщение указывает на то, что имеется одновременно обрабатываемый запрос на запрашиваемую строку кэша.
Данные [Конфликты] (Data): Это сообщение используется для пересылки данных и списков конфликтов, если таковые имеются. Список конфликтов пуст, если данные пересланы или если базовый узел отправляет данные из памяти первому владельцу. При передаче данных отправляющий узел присоединяет список конфликтов. Принимающий узел использует список для отправки ответов CNFL на соответствующие запросы, сохраненные в буфере.
Сообщения на базовый узел
Эти сообщения отправлены одноранговым узлом на базовый узел.
Чтение [Конфликты](READ): Это сообщение запрашивает данные от базового узла и перечисляет конфликты, если таковые существуют. Это сообщение отправляется после того, как одноранговым узлом приняты все ответы, если ни одно из принятых сообщений не было сообщением DATA.
Отмена (Конфликты)(CNCL): Это сообщение отправляется базовому узлу в ответ на обращение к кэшу в Одноранговом узле и перечисляет все конфликты, если таковые существуют. Это сообщение отменяет операцию выборки с упреждением, выполняемую базовым узлом.
Сообщения от базового узла
Эти сообщения отправляются базовым узлом на Одноранговые и/или Запрашивающие узлы.
Данные(DATA): Это сообщение включает в себя запрашиваемые данные и может указывать состояние данных (M/E/F), которые должны быть использованы Запрашивающим узлом.
Подтверждение (ACK): Это сообщение указывает, что запрашиваемые данные были отправлены Запрашивающему узлу. После отправки базовым узлом сообщения ACK текущий период является завершенным.
Передача (XFR): Это сообщение предписывает принимающему узлу отправлять данные узлу, указанному в сообщении. Базовый узел отправляет это сообщение текущему владельцу запрашиваемых данных, если базовый узел информирован относительно состояния конфликта, требующего, чтобы текущий владелец данных передал данные целевому узлу. Вместо сообщения XFR передается сообщение XFRI, если базовый узел определяет, что нерешенным конфликтующим запросом является сообщение PRIL или PWIL, что означает, что текущий владелец должен обозначить строку как недостоверную при инициировании передачи данных. В одном варианте выполнения первый узел за период, который отправит сообщение CNCL, является текущим владельцем. Период в данном контексте - это период между первым запросом данных и разрешением всех конфликтов запросов данных. Если базовый узел отправляет данные в узел из памяти, то этот узел является текущим владельцем. Отправка сообщения XFR/XFRI предписывает целевому узлу стать текущим владельцем. В одном варианте выполнения целевой узел выбран из списка конфликтов, предоставленного базовому узлу в сообщении READ или CNCL. Целевые узлы выбраны из узлов, от которых базовый узел принял сообщение READ. Таким образом, если базовый узел считает узел А текущим владельцем строки кэша, так как узел А отправил базовому узлу сообщение CNCL(B, C), базовый узел ждет приема сообщения READ от узлов В или С, чтобы послать сообщение XFR/XFRI на узел А, чтобы предписать узлу А переслать данные узлу (B или C), который отправил сообщение READ. Базовый узел затем ждет отправки от третьего узла сообщения READ перед отправкой сообщения XFR/XFRI, предписывающего третьему узлу послать данные.
Краткое описание протокола MESIF
Есть две основных схемы обеспечения когерентности кэша, схема наблюдения (теперь часто называемая Симметричной Многопроцессорной обработкой (SMP)) и схема каталогов (часто называемая Распределенная Совместно Используемая Память (DSM)). Фундаментальное различие между ними состоит в размещении и доступе к метаинформации, то есть информации о том, где хранятся копии строки кэша.
В случае наблюдения за кэшем эта информация распределена непосредственно с кэшированными копиями, то есть каждая достоверная копия строки кэша поддерживается модулем, который должен определить свою способность ответить всякий раз, когда какой-нибудь узел по-новому запрашивает разрешение на доступ к строке кэша. Где-нибудь - обычно в фиксированном местоположении - расположено хранилище, в котором хранятся некэшированные данные. Это местоположение может содержать достоверную копию, даже когда строка кэширована. Однако местоположение этого узла обычно неизвестно запрашивающим узлам - запрашивающие узлы просто выполняют широковещательную рассылку адреса требуемой строки кэша, наряду с необходимыми разрешениями, в широковещательном сообщении, и все узлы, которые могли бы иметь копию, должны ответить, чтобы убедиться в том, что поддерживается согласованность, причем узел, содержащий некэшированную копию, отвечает, если никакой другой (одноранговый) узел не отвечает.
Для схем на основе каталога в дополнение к фиксированному месту, где хранятся некэшированные данные, имеется фиксированное местоположение, каталог, указывающий, где постоянно хранятся кэшированные копии. Для выполнения нового доступа к строке кэша узел должен связаться с узлом, содержащим каталог, который обычно является тем же узлом, который содержит хранилище некэшированных данных, таким образом позволяя отвечающему узлу предоставить данные, если копия в основном запоминающем устройстве достоверная. Такой узел упоминается как базовый узел.
Каталог может быть распространен двумя способами. Во-первых, данные из основного запоминающего устройства (некэшированное хранилище) часто распространяются среди узлов, причем каталог распространяется тем же самым способом. Во-вторых, сама метаинформация может быть распространена, причем на базовом узле хранится минимальная информация о том, кэширована ли строка, и если это так, то где постоянно расположена единственная копия.
Схемы наблюдения основываются на широковещательной передаче, так как отсутствует отдельное место, где расположена метаинформация, поэтому все узлы должны быть уведомлены относительно каждого запроса, при этом каждый узел является ответственным за выполнение своей части для гарантированного поддержания когерентности. Эта схема включает в себя сообщения вмешательства, инструктирующие базовый узел не отвечать, когда другой узел предоставляет данные.
Схемы наблюдения имеют преимущество, состоящее в том, что ответы могут быть прямыми и быстрыми, но они плохо масштабируются, потому что все узлы обязаны отслеживать все запросы. Схемы на основе каталога масштабируются лучше, но требуют более сложных ответов, часто вовлекая три узла в двухточечную связь.
Основной протокол MESIF, описанный здесь, обеспечивает протокол, подобный наблюдению, без ограничений, связанных с единственной последовательной шиной. Подобно протоколу наблюдения за кэшем MESIF для поддержания когерентности основывается на узлах с кэшированными копиями данных. Использование двухточечных линий связи, а не синхронной централизованной широковещательной передачи приводит к возникновению проблемы изменения шкалы времени, суть которой состоит в том, что с точки зрения разных узлов кажется, что события происходят в разном порядке. Как более подробно описано ниже, протокол MESIF обрабатывает изменение шкалы времени, распознавая, когда могли возникнуть возможные ошибки, и удостоверяясь, что они правильно обработаны. Понятие "базовый узел" используется, чтобы определить, где постоянно расположена некэшированная копия, но базовый узел участвует в каждой транзакции (групповой операции с данными) - не находясь на критическом пути - для решения проблемы изменение шкалы времени и разрешения конфликтов. Из-за параллельно-широковещательной сущности схемы MESIF достигает низкого времени задержки, связанного с протоколами наблюдения, обеспечивая в большинстве случаев получение кэшированной копии данных с минимальным временем задержки: единственный запрос-ответ в прямом и обратном направлениях между двумя узлами.
Основной протокол MESIF включает в себя широковещательную передачу первоначального запроса ко всем одноранговым узлам, так же как и к базовому узлу. Если копия кэширована в состоянии E, F или М, то это включено в ответ. Затем базовому узлу отправляют второе сообщение, информирующее его о том, что запрос был удовлетворен. Если запрошенная строка некэшированная или если существуют только копии в S-состоянии, второй запрос, отправленный базовому узлу, используется для подтверждения предыдущего запроса, данные по которому базовый узел, возможно, к этому времени выбрал из своей памяти. В любом случае базовый узел должен ответить на второй запрос (и на первый, хотя они иногда могут объединяться) для обеспечения синхронизации и разрешения конфликтов. Необходимо отметить, что базовый узел может иметь один или более кэшей, так что он может ответить на первоначальный запрос точно так же, как любой другой узел.
Обработку конфликтов осуществляют распределенным способом. Проблема изменения шкалы времени затрудняет обнаружение конфликтов, потому что отдельные запросы могут быть задержаны на сколь угодно долгое время. Однако конфликт будет обнаружен, если каждый узел отслеживает возникновение конфликтов после выполнения запроса. Оба узла могут как обнаружить, так и не обнаружить конфликт, но, по меньшей мере, один узел обнаружит. Поскольку все узлы должны ответить на широковещательный запрос либо предоставлением данных, либо индикацией того, что они не имеют копии (или, при некоторых обстоятельствах, не предоставляют копию, которую они имеют), причем ответ может включать в себя индикацию конфликта, так что конфликтующие узлы обнаружат конфликт.
Трудности возникают при разрешении узлу использовать данные непосредственно после их приема, не дожидаясь приема всех ответов. Таким образом, узлу, принимающему копию данных, разрешено немедленно после приема использовать данные внутри себя, но не разрешено сделать результат использования данных видимым для остальной части системы, пока узел не принял подтверждение от базового узла. Подтверждение может также включать в себя инструкции в отношении того, что узел должен переслать свою копию другому узлу и, возможно, удалить узел из своего кэша.
Наконец, когда узел отвечает на запрос от другого узла предоставлением кэшированных данных, узел должен задержать все другие принятые им запросы на ту же самую строку кэша до тех пор, пока узел не примет ответ от базового узла, подтверждающий факт пересылки данных узлом, таким образом гарантируя, что все узлы соблюдают одинаковый порядок передачи (возможно перезаписываемой) строки кэша.
Базовый узел является хранилищем для некэшированных данных, но базовый узел также может иметь процессор, генерирующий запросы, и включать в себя один или более кэшей. Подобно любому другому узлу, когда процессор базового узла обнаруживает отсутствие необходимых данных, базовый узел должен выполнить широковещательную рассылку запросов всем остальным (одноранговым) узлам, и базовый узел должен обработать запрос внутри себя, как если это был бы любой другой запрос, прибывающий на базовый узел. Необходимо отметить, что это особый случай, так как базовый узел явно не посылает сообщения самому себе (базовому узлу). Кроме того, когда поступает внешний запрос на данные, которые кэшированы локально, базовый узел должен ответить так, чтобы гарантировать однозначность более позднего ответа базового узла. То есть базовый узел может ответить на первоначальный запрос предоставлением данных, но базовый узел должен также ответить и на второй запрос как базовый узел.
Варианты протокола позволяют базовому узлу отвечать посредством некэшированной копии данных, не обладая информацией о том, являются ли эти данные достоверными, предоставляя выяснение этого запрашивающему узлу, и второго ответа базового узла для классификации случая, когда были предоставлены несоответствующие данные.
Более подробное выполненное на базе псевдокода описание различных вариантов реализации протокола MESIF, соответствующего описанным здесь целям, приведено в конце в Приложении A.
Краткое описание неспекулятивного распределенного разрешения конфликтов
Вообще, протокол когерентности кэш-памяти требует разрешения конфликтов для обеспечения упорядоченных изменений состояния различных строк кэша или других блоков данных. Описанный здесь способ разрешения конфликтов обеспечивает последовательную согласованность, означающую, что в любое время может существовать только единственная поддающаяся изменению копия строки кэша и что никакая копия строки кэша не может изменяться, пока другие копии могут быть считаны. Поэтому для поддержания последовательной согласованности конфликтующие запросы на изменение копии строки кэша должны быть разрешены.
В одном варианте выполнения конфликт разрешают за счет использования свойства времени. То есть независимо от задержек ни один из двух узлов не может запросить строку кэша прежде другого. Таким образом, конфликты могут быть обнаружены, по меньшей мере, одним из конфликтующих запрашивающих узлов, если каждый узел отслеживает все запросы после того, как этот узел выработал свой собственный запрос.
В одном варианте выполнения, если строка находится в Исключительном (Е) состоянии, Измененном (M) состоянии или состоянии пересылки (F), конфликты разрешаются в узле, содержащем уникальную копию. Выигравший в разрешении конфликта и, возможно, проигравшие сообщают о конфликте базовому узлу, который соединяет попарно отчеты о конфликте и вырабатывает инструкции пересылки, чтобы гарантировать в конечном счете прием всеми запрашивающими узлами запрашиваемых данных. В одном варианте выполнения, если запрашиваемая строка кэша либо некэширована, либо присутствует только в состоянии совместного использования (S), то базовый узел предоставляет для запрашиваемой строки кэша копию запрашиваемых данных и разрешает конфликты.
В одном варианте выполнения распределенное разрешение конфликтов, описанное здесь, является частью протокола кэша, упоминаемого как протокол MESIF, в котором с кэшированной копией строки кэша ассоциировано одно из пяти состояний (Измененное (M) состояние, Исключительное (Е) состояние, состояние совместного использования (S), Недостоверное (I) состояние, состояние пересылки (F)). В одном варианте выполнения период молчания после всех ответов на запрос, пока не было принято сообщение подтверждения от базового узла, обеспечивает осведомленность всех конфликтующих узлов о конфликтах, в которые вовлечены эти узлы. Период молчания не ограничивает использование данных в кэше, но действительно предотвращает распространение данных в другие кэши.
В следующем далее подробном обсуждении используются понятия, относящиеся к узлам в многоузловой системе. В одном варианте выполнения узел включает в себя процессор, имеющий внутреннюю кэш-память, внешнюю кэш-память и/или внешнее запоминающее устройство. В альтернативном варианте выполнения узел является электронной системой (например, компьютерной системой, мобильным устройством) соединенной с другими электронными системами. Могут также использоваться другие варианты конфигураций узла. В следующих далее примерах пунктирные линии отображают ранее отправленные сообщения, а сплошные линии отображают описываемые сообщения. Для обеспечения большей ясности чертежей после разрешения набора сообщений (например, PRIL и соответствующего ему IACK), линии, представляющие эти сообщения, далее на чертежах не изображены.
Фиг.2a и 2b являются концептуальными представлениями запроса совместно использованной кэшированной строки. Связанная с различными сообщениями по Фиг.2a и 2b нумерация (например, 1. PRIL, 7. IACK), с целью объяснения примера конфликта обеспечивает приблизительное упорядочение. Точные временные соотношения связей, изображенных на Фиг.2a и 2b, а также и в других приведенных примерах (то есть Фиг.3a-3f), не требуются.
Как показано на Фиг.2a, одноранговый узел 210 передает сообщение PRIL одноранговым узлам 220 и 230 и базовому узлу 240. Одноранговый узел 210 также мог бы запросить тот же блок данных, используя сообщение PRL, в каковом случае одноранговый узел 230 в ответ на сообщение запроса не пометил бы свою копию как недостоверную. Одноранговый узел 220 отвечает на сообщение PRIL сообщением IACK, указывающим на то, что одноранговый узел 220 не может предоставить достоверную копию запрашиваемых данных. Одноранговый узел 220 показан изначально содержащим копию запрашиваемых данных в состоянии S, которая является достоверной копией данных, но не является копией, которая может быть предоставлена в ответ на запрос копии данных.
Так как сообщение PRIL запрашивает копию данных и предписывает всем другим копиям пометить как недостоверные оставшиеся копии данных, одноранговый узел 220 переводит свою копию данных из S-состояния в I-состояние. Поскольку одноранговый узел 230 содержит копию запрошенных данных в F-состоянии (единственная достоверная копия, которая должна быть предоставлена запрашивающему узлу), одноранговый узел 230 предоставляет одноранговому узлу 210 копию запрашиваемых данных. Одноранговый узел 230 также переводит свою копию запрашиваемых данных в I-состояние. Одноранговый узел 210 сохраняет запрошенные данные в E-состоянии. В качестве альтернативы одноранговый узел 210 хранит запрошенные данные в F-состоянии.
Как показано на Фиг.2b, в ответ на прием запрашиваемых данных от однорангового узла 230 одноранговый узел 210 отправляет базовому узлу 240 сообщение CNCL(230)(), которое предписывает базовому узлу 240 отменить извлечение запрашиваемых данных из памяти (или отменить передачу данных, если они уже извлечены). Сообщение CNCL(230)() также указывает базовому узлу 240 на то, что копия запрашиваемых данных была принята от однорангового узла 230 и что одноранговый узел 210 не обнаружил никаких конфликтов, запрашивая данные сообщением PRIL.
В ответ на сообщение CNCL(230)() от однорангового узла 210 базовый узел 240 передает сообщение ACK одноранговому узлу 210 и сообщение DACK одноранговому узлу 230. Сообщение ACK указывает одноранговому узлу 210 на то, что базовый узел 240 подтверждает прием сообщения CNCL(230)(). Сообщение DACK от однорангового узла 240 одноранговому узлу 230 подтверждает прием данных одноранговым узлом 210 и завершает процесс запроса данных одноранговым узлом 210.
Фиг.3а и 3b являются концептуальными представлениями запроса совместно используемой некэшированной строки. Как показано на Фиг.3а, одноранговый узел 210 для запроса копии блока данных передает сообщение PRIL. Поскольку одноранговые узлы 220 и 230 не хранят достоверную копию запрашиваемых данных, узлы 220 и 230 отвечают сообщением IACK.
Как изображено на Фиг.3b, так как одноранговый узел 210 принял сообщение IACK от всех одноранговых узлов, одноранговый узел 210 отправляет базовому узлу 240 сообщение READ(), которое запрашивает копию предварительно запрошенных данных, которые были извлечены из памяти базовым узлом 240. Сообщение READ() также указывает базовому узла 240 на то, что одноранговый узел 210 не обнаружил никаких конфликтов с сообщением PRIL. Базовый узел 240 предоставляет копию запрашиваемых данных с помощью сообщения DataE. В одном варианте выполнения базовый узел 240 также включает сообщение ACK в сообщение DataE (то есть в один и тот же пакет сообщений). В альтернативном варианте выполнения сообщения DataE и ACK передают отдельно.
На Фиг. с 4a по 4f показано концептуальное представление трехсторонних конфликтующих запросов на совместно используемую кэшированную строку. Как изображено на Фиг.4a, одноранговый узел 210 отправляет сообщение PRL одноранговым узлам 220 и 230 и базовому узлу 240. Сообщение PRL, предназначенное базовому узлу 240, по каким-либо причинам задержано, например, из-за задержки времени ожидания в системе 200. Так как ни одноранговый узел 220, ни одноранговый узел 230 в ответ на сообщение PRL не может предоставить достоверную копию запрашиваемых данных, одноранговый узел 220 и одноранговый узел 230 отправляют одноранговому узлу 210 сообщения IACK.
Сообщение PRL однорангового узла 210 не требует ни от одного из принимающих одноранговых узлов пометить как недостоверные копии, если таковые вообще имеются, хранящиеся на принимающих одноранговых узлах. Одноранговый узел 210 может также применять для запроса данных сообщение PRIL, требующее, чтобы все одноранговые узлы, хранящие запрашиваемые данные, независимо от того, были ли они предоставлены запрашивающему узлу или нет, пометили как недостоверную хранящуюся на узле копию запрашиваемых данных. Конфликты могут быть вызваны любой комбинацией сообщений, которые иначе вызвали бы противоречивый результат.
Как показано на Фиг.4b, через некоторое время после приема одноранговым узлом 220 от однорангового узла 210 сообщения PRL, и прежде чем базовый узел 240 принимает сообщение PRL от однорангового узла 210, одноранговый узел 220 передает сообщение PRIL, запрашивая тот же самый блок данных. Одноранговый узел 220 передает сообщение PRIL одноранговым узлам 210 и 230 и базовому узлу 240; однако сообщение PRIL, предназначенное одноранговому узлу 210, задержано. Одноранговый узел 230 и базовый узел 240 отвечают на сообщение PRIL однорангового узла 220 сообщениями IACK.
Как показано на Фиг.4c, одноранговый узел 230 впоследствии передает сообщение PRIL одноранговым узлам 210 и 220 и базовому узлу 240. Базовый узел 240 отвечает на сообщение PRIL сообщением IACK, указывающим на то, что на базовом узле 240 отсутствует достоверная копия запрашиваемых данных. Одноранговый узел 210 отвечает на сообщение PRIL однорангового узла 230 сообщением CNFL, указывающим на то, что одноранговый узел 210 имеет конфликт с сообщением PRIL, принятым от однорангового узла 230.
Одноранговый узел 220 отвечает на сообщение PRIL однорангового узла 230 сообщением CNFLI, указывающим на то, что одноранговый узел 220 имеет конфликт с сообщением PRIL, принятым от однорангового узла 230. Сообщение CNFLI указывает на то, что конфликтным сообщением однорангового узла 220 является сообщение PRIL, требующее признания копии данных недостоверной. Сообщение CNFL однорангового узла 210 указывает на то, что конфликтным сообщением однорангового узла 210 является сообщение PRL, не требующее признания копии данных недостоверной.
Как показано на Фиг.4d, после приема базовым узлом 240 задержанного сообщения PRL однорангового узла 210 базовый узел 240 отвечает сообщением IACK, указывающим на то, что на базовом узле 240 отсутствует достоверная копия запрашиваемых данных.
В ответ на прием сообщения CNFL от однорангового узла 210 и сообщения CNFLI от однорангового узла 220, одноранговый узел 230 передает базовому узлу 240 сообщение READ(210, 220*). Сообщение READ(210, 220*) запрашивает копию данных из памяти, управляемой базовым узлом 240. Сообщение READ(210, 220*) также указывает на то, что запрос данных однорангового узла 230 конфликтует с запросами одноранговых узлов 210 и 220 и что запрос однорангового узла 220 требует признания копии данных недостоверной (как обозначено звездочкой). Поскольку одноранговый узел 230 первым из узлов с конфликтующими запросами отправил сообщение READ базовому узлу 240, одноранговый узел 230 является первым одноранговым узлом, принявшим копию запрашиваемых данных, и текущим владельцем запрашиваемых данных.
В ответ на сообщение READ(210, 220*) базовый узел предоставляет одноранговому узлу 230 запрашиваемые данные в сообщении DataE. Сообщение DataE предписывает одноранговому узлу 230 сохранить данные в состоянии E. В качестве альтернативы могли быть использованы другие сообщения данных (например, DataF, DataS). Базовый узел 240 для ответа на последующие сообщения READ/CNCL одноранговых узлов 210 и 220 поддерживает список конфликтов, предоставленный одноранговым узлом 230.
Как показано на Фиг.4e, в ответ на сообщение IACK от базового узла 240 одноранговый узел 210 передает базовому узлу 240 сообщение READ(230*). Сообщение READ не указывает на конфликт с сообщением PRIL однорангового узла 220, потому что одноранговый узел 210 пока еще не принял это сообщение PRIL. Если бы одноранговый узел 210 принял сообщение PRIL от однорангового узла 220, то сообщение READ указало бы на конфликт с одноранговым узлом 220.
В ответ на сообщение READ(230*) базовый узел 240 отправляет одноранговому узлу 230 сообщение XFRI(210), предписывающее одноранговому узлу 230 отправлять запрашиваемые данные одноранговому узлу 210. Сообщение XFRI также указывает одноранговому узлу 230 на то, что конфликтующее сообщение однорангового узла, который еще не принял данные (одноранговый узел 220), требует после отправки данных одноранговому узлу 210 признания данных недостоверными.
Одноранговый узел 230 отправляет запрашиваемые данные одноранговому узлу 210 в сообщении DataE(220), которое предписывает одноранговому узлу 210 сохранить запрашиваемые данные в состоянии E, и информирует одноранговый узел 210 о том, что запросное сообщение, возможно, конфликтует с сообщением однорангового узла 220. Одноранговый узел 230 обнаружил конфликт с сообщением однорангового узла 220. До того как одноранговый узел 210 примет запрашиваемые данные, принимают задержанное сообщение PRIL от однорангового узла 220.
Поскольку одноранговый узел 210 уже доставил свой список конфликтов на базовый узел 240 и не принял запрашиваемые данные от однорангового узла 230, одноранговый узел 210 сохраняет в буфере сообщение PRIL, принятое от однорангового узла 220. В ответ на прием сообщения DATA от однорангового узла 230, имеющего конфликт с одноранговым узлом 220, одноранговый узел 210 отправляет сообщение CNFL, указывающее на то, что одноранговый узел 210 имеет конфликт с сообщением PRIL однорангового узла 220.
Как показано на Фиг.4f, в ответ на сообщение CNFL от однорангового узла 210 одноранговый узел 230 отправляет сообщение READ(210, 230*) базовому узлу 240, указывающее на наличие конфликта с сообщением PRL однорангового узла 210 и с сообщением PRIL однорангового узла 230. Базовый узел 240 отвечает на сообщение READ(210, 230*) сообщением ACK одноранговому узлу 220 и сообщением XFRI(220) одноранговому узлу 210. Одноранговый узел 210 отправляет запрашиваемые данные одноранговому узлу 220 в сообщении DataE(230). Одноранговый узел 220 предварительно определил наличие конфликта с одноранговым узлом 230. Доставка сообщения ACK одноранговому узлу 220 указывает на отсутствие дальнейших конфликтов с сообщением PRIL однорангового узла 220.
Фиг. с 5a по 5g являются концептуальными представлениями трехсторонних конфликтующих запросов на некэшированную строку данных. Как показано на Фиг.5a, одноранговый узел 210 для запроса блока данных отправляет сообщение PRIL одноранговым узлам 220 и 230 и базовому узлу 240. Доставка сообщения PRIL базовому узлу 240 задержана. Вскоре после отправки сообщения PRIL одноранговым узлом 210 одноранговый узел 220 отправляет сообщение PRIL, запрашивающее копию того же самого блока данных, одноранговым узлам 210 и 230 и базовому узлу 240.
Как изображено на Фиг.5b, одноранговый узел 230 отвечает на сообщение PRIL однорангового узла 210 сообщением IACK. Одноранговый узел 230 указывает на задержку во время обработки его ответа на сообщение PRIL однорангового узла 220. Одноранговый узел 210 отвечает на сообщение PRIL однорангового узла 220 сообщением CNFLI. Точно так же одноранговый узел 220 отвечает на сообщение PRIL от однорангового узла 210 сообщением CNFLI.
Как изображено на Фиг.5c, до приема узлами 210 и 220 копии запрашиваемых данных одноранговый узел 230 отправляет сообщение PRIL одноранговым узлам 210 и 220 и базовому узлу 240. Одноранговые узлы 210 и 220 отвечают на сообщение PRIL от однорангового узла 230 сообщениями CNFLI. Из-за задержки обработки сообщения PRIL однорангового узла 220 одноранговый узел 230 отправляет одноранговому узлу 220 вместо сообщения IACK сообщение CNFLI, чтобы указать на наличие конфликта с недавно сгенерированным одноранговым узлом 230 запросом на тот же самый блок данных.
Как изображено на Фиг.5d, после приема ответов от всех одноранговых узлов одноранговый узел 230 отправляет базовому узлу 240 сообщение READ(210*, 220*). Базовый узел 240, чтобы предоставить запрашиваемые данные одноранговому узлу 230, отвечает сообщением DataE, так как одноранговый узел 230 является первым одноранговым узлом, который посылает сообщение READ базовому узлу 240. Одноранговый узел 230 является текущим владельцем данных.
Как показано на Фиг.5e, после приема ответов от всех одноранговых узлов одноранговый узел 210 отправляет базовому узлу 240 сообщение READ(210*, 230*). Базовый узел 240 также принимает задержанное сообщение PRIL от однорангового узла 210. Базовый узел 240 отвечает на сообщение PRIL однорангового узла 210 сообщением IACK, которое указывает на то, что базовый узел 240 не предоставит копию запрашиваемых данных. Это происходит вследствие того, что на одноранговом узле 230 имеется достоверная кэшированная копия запрашиваемых данных.
Базовый узел 240 отправляет одноранговому узлу 230 сообщение XFRI(220), предписывающее одноранговому узлу 230 предоставить копию запрашиваемых данных одноранговому узлу 210. Одноранговый узел 230 является вторым одноранговым узлом, принимающим копию запрашиваемых данных, потому что одноранговый узел 230 является вторым одноранговым узлом, отправившим базовому узлу 240 сообщение READ, запрашивая данные.
Как показано на Фиг.5f, одноранговый узел 230 отправляет в сообщении DataE копию запрашиваемых данных одноранговому узлу 220. Одноранговый узел 210 отправляет базовому узлу 240 сообщение READ(220*, 230*). Базовый узел 240 отвечает на сообщение READ однорангового узла 210 отправкой одноранговому узлу 220 сообщения XFRI (210), которое предписывает одноранговому узлу 220 отправить копию запрашиваемых данных одноранговому узлу 210.
Как показано на Фиг.5g, одноранговый узел 220 отправляет копию запрашиваемых данных в сообщении DataE одноранговому узлу 210. Одноранговый узел 220 также признает недостоверной копию данных, сохраненную одноранговым узлом 220. Базовый узел 240 отправляет сообщение ACK одноранговому узлу 210, указывающее на то, что все запросы на блок данных были разрешены и удовлетворены.
Примеры систем, поддерживающих неспекулятивное распределенное разрешение конфликтов
На Фиг.6 изображена блок-схема одного варианта выполнения узла. Узел 600 изображен имеющим один процессор, кэш-память, контроллер памяти и память; однако в узел может быть включено любое количество любого из этих компонентов. Кроме того, в узел могут быть также включены дополнительные и/или другие компоненты (например, мост между шинами).
Процессор 610 может быть процессором любого типа, известного в данной области техники. В одном варианте выполнения процессор 610 включает в себя кэш-память 620. В альтернативных вариантах выполнения кэш-память 620 является для процессора 610 внешней, или могут быть использованы дополнительные устройства кэш-памяти, являющиеся для процессора 610 внутренними или внешними.
Контроллер 630 памяти соединен с кэш-памятью 620 и памятью 640. Контроллер 630 памяти работает в качестве интерфейса между кэш-памятью 620 и памятью 640. В одном варианте выполнения контроллер 630 памяти поддерживает когерентность кэш-памяти в соответствии с описанным здесь протоколом когерентности кэш-памяти. Контроллер 630 памяти взаимодействует с другими узлами через линии связи 650 узла. В альтернативном варианте выполнения процессор 610 взаимодействует с контроллером 630 памяти для поддержания, в соответствии с описанным здесь, когерентности кэш-памяти, и процессор 610 взаимодействует с другими узлами через альтернативные линии связи 655 узлов.
В одном варианте выполнения линии связи 650 узлов включают в себя выделенный интерфейс для каждого узла, с которым взаимодействует узел 600. В альтернативном варианте выполнения узловые связи 650 включают в себя множество интерфейсов, количество которых отличается от количества узлов, с которыми взаимодействует узел 600. В одном варианте выполнения узел 600 взаимодействует с одним или более агентами (посредниками), представляющими множество узлов.
На Фиг.7 показан один из вариантов выполнения многопроцессорной системы. Под многопроцессорной системой 700 подразумевается совокупность систем, имеющих множество процессоров, например компьютерные системы, системы мониторинга в реальном масштабе времени и т.д. Альтернативные многопроцессорные системы могут включать в себя большее или меньшее количество компонентов и/или другие компоненты. В некоторых случаях описанные здесь способы управления кэшем могут быть применены как к системам с одним процессором, так и к многопроцессорным системам. Многопроцессорная система 700 может быть сконфигурирована для работы в качестве многоузловой системы.
Многопроцессорная система 700 включает в себя шинную систему 710 или другое устройство (другие устройства) связи для обмена информацией. Шинная система 710 может включать в себя любое количество шин и связанных с ними схем межсоединений, например мостов между шинами. Процессор 720 соединен с шинной системой 710 для обработки информации. Процессор 720 может включать в себя кэш-память 722, например кэш-память нулевого уровня (L0), и контроллер 724 кэша. В одном варианте выполнения процессор 720 также соединен с кэшем 725, который может быть кэш-памятью любого типа. В альтернативном варианте выполнения кэш 725 может быть соединен с шинной системой 710. Могут также использоваться другие варианты конфигураций процессор-кэша.
В одном варианте выполнения контроллер 724 кэша соединен с кэш-памятью 722 через интерфейс 728 кэш-памяти, который может быть, например, внутренней шиной процессора 720. Контроллер кэша соединен с кэш-памятью 725 через интерфейс 726 кэш-памяти, который обеспечивает взаимодействие между процессором 720 и внешней кэш-памятью.
Многопроцессорная система 700 также включает в себя процессор 730 с кэш-памятью 732 и контроллером 734 кэша. Контроллер 734 кэша соединен с кэш-памятью 732 через интерфейс 738 кэш-памяти. Точно так же контроллер 734 кэша соединен с кэш-памятью 735 с помощью интерфейса 736 кэш-памяти. В одном варианте выполнения кэш-память 735 соединена с процессором 730.
Хотя многопроцессорная система 700 показана имеющей два процессора, многопроцессорная система 700 может включать в себя любое количество процессоров и/или сопроцессоров. Многопроцессорная система 700 также включает в себя систему 740 хранения, соединенную с шинной системой 710. Система 740 хранения может включать в себя любую комбинацию динамических (например, оперативное запоминающее устройство) и статических (например, постоянное запоминающее устройство (ПЗУ, ROM), ПЗУ на компакт-диске (CD-ROM), дисковый накопитель, флэш-память) запоминающих устройств и связанных с ними приводов, если такие необходимы. Запоминающие устройства системы 740 хранения используются для хранения информации и инструкций, которые должны быть выполнены процессорами многопроцессорной системы 700. Система 740 хранения также может применяться для хранения временных переменных или другой промежуточной информации во время выполнения инструкций процессорами.
Инструкции могут быть предоставлены системе 740 хранения из статического или удаленного запоминающего устройства, такого как магнитный диск, интегральная схема постоянного запоминающего устройства (ПЗУ), CD-ROM, цифровой универсальный диск (DVD), через проводное или беспроводное удаленное соединение и т.д. В альтернативных вариантах выполнения вместо или в комбинации с программными инструкциями могут использоваться аппаратные средства. Таким образом, выполнение последовательностей инструкций не ограничено никакой определенной комбинацией аппаратных средств и программных инструкций.
Многопроцессорная система 700 также включает в себя сетевой интерфейс 750 для обеспечения доступа к сети, такой как локальная сеть и/или Интернет. Сетевой интерфейс 750 может обеспечить беспроводный и/или проводной сетевые интерфейсы, которые могут включать в себя передачу инструкций к удаленной среде электронного доступа и/или от нее. Среда электронного доступа включает в себя любое средство, которое обеспечивает (то есть хранит и/или передает) содержимое (например, машинно-исполняемые инструкции) в формате, читаемом электронным устройством (например, компьютером, персональным информационным устройством, сотовым телефоном).
Например, машинно-доступная среда включает в себя постоянное запоминающее устройство (ПЗУ); оперативное запоминающее устройство (ОЗУ, RAM); накопитель на магнитных дисках; оптические носители данных; устройства флэш-памяти; электрическую, оптическую, акустическую или другую форму распространения сигналов (например, несущие волн, инфракрасные сигналы, цифровые сигналы).
Многопроцессорная система 700 может также включать в себя устройство отображения 760, такое как электронно-лучевая трубка (ЭЛТ, CRT) или жидкокристаллический дисплей (ЖКД, LCD), для отображения информации. Как правило, к шине 710 присоединено устройство (устройства) 770 ввода данных, включающее в себя, например, клавиатуру, имеющую алфавитно-цифровые и другие клавиши, для передачи информации и выбранных команд на процессоры 720 и/или 730. Другим видом пользовательского устройства ввода данных, служащим для передачи информации о направлении и выбранных команд на процессоры 720 и 730 и управления перемещением курсора на отображающем устройстве 760, является устройство управления курсором, такое как мышь, шаровой манипулятор (трекбол) или клавиши управления курсором.
Применяющиеся в описании ссылки на "один вариант выполнения" или "вариант выполнения" означают, что конкретный признак, структура или характеристика, описанные в связи с данным вариантом выполнения, включены, по меньшей мере, в один вариант выполнения данного изобретения. Употребление в различных местах описания фразы "в одном варианте выполнения" совсем не обязательно означает обращение к одному и тому же варианту выполнения.
В предшествующем описании данное изобретение было описано со ссылкой на определенные варианты его выполнения. Тем не менее, будет очевидно, что в него могут быть внесены различные модификации и изменения, не выходя за широкие рамки сущности и объема изобретения. Описание и чертежи должны соответственно рассматриваться только в иллюстративном, но не в ограничивающем контексте.
Приложение А
Ниже приведены иллюстративные описания алгоритмов MESIF в формате псевдокода. Описания основываются на пакетах; то есть каждая процедура исполняется в ответ на входящий или исходящий пакет. В качестве альтернативы алгоритмы могут быть описаны как реакция на изменение состояния вследствие приема или генерации пакета.
Для упрощения описания сделаны следующие предположения:
1. Каждый одноранговый/запрашивающий узел стороны имеет одного кэширующего агента;
2. Базовые узлы не имеют кэширующих агентов; и
3. Алгоритмы запросов к памяти в базовых узлах могут быть более сложными, чем приведенные здесь, и обрабатывать все пограничные случаи, порождаемые MESIF (больше чем одно чтение, множество периодов, перенаправление записи и т.д.).
Случай с базовым узлом, имеющим кэширующего агента (который может встречаться в некоторых вариантах выполнения), является производным от приведенных алгоритмов, а именно, посредством объединения процедур для принятых пакетов за счет включения в них процедур, относящихся к передаче на/от базового узла локальным котирующим агентом (или посредником).
В одном варианте выполнения кэши удовлетворяют следующим ограничениям:
1. Кэш будет формировать PRL, только если строка находится в состоянии I.
2. Кэш будет формировать PRIL, только если строка находится в состояниях I или S.
3. Кэш будет формировать PWL, только если строка находится в состоянии М.
4. Кэш может свободно переходить в состояние I из состояний S, F и Е.
5. Кэш может свободно переходить в состояние М из состояния Е (предположение, что запись осуществлена).
6. Другие переходы состояния кэша могут происходить только после завершения выполнения запроса, который он выдал, или после приема запроса от однорангового узла.
Описанный ниже базовый протокол охватывает только запросы PRL, PRIL и PWL и использует способ разрешения конфликтов с участием списка конфликтов, передаваемого одновременно с передачей данных. Расширения и дополнительные возможности этого базового протокола охвачены в следующих разделах.
Базовый протокол MESIF
Генерирование запроса
Вызов процедуры:
Кэш сгенерировал новый запрос для (неактивного) адреса
Алгоритм:
Пометить адрес как активный
Если запрос является PRL или PRIL
Отправить запрос всем другим одноранговым узлам и базовому узлу
Если запрос является PWL
Отправить запрос базовому узлу
Прием запроса базовым узлом
Вызов процедуры:
Базовый узел принял запрос
Алгоритм:
Если запрос является PWL
Инициировать запись в память
(обработать пересылку, отмену ожидающих выполнения операций чтения и т.д.)
Послать сообщение АСК обратно запрашивающей стороне
Если запрос является PRL или PRIL
Инициировать чтение из памяти
(Буферизировать данные, если чтение завершилось прежде, чем принято сообщение READ, и т.д.)
Прием запроса одноранговым узлом
Вызов процедуры:
Одноранговым узлом принят запрос (PRL или PRIL)
Алгоритм:
Если адрес перенаправляют
Буферизировать входящий запрос
Иначе, если адрес не активен
Отследить кэш
Иначе, если адрес активен
Если активный запрос является PWL
Буферизировать входящий запрос
- Конец Если
Если входящий запрос находится в списке конфликтов активного запроса
Если активный запрос является PRL
Ответить сообщением CNFL
Иначе (активный запрос является PRIL)
Ответить сообщением CNFLI
Иначе, если активный запрос находится в "фазе данных" (см. ниже Сбор Ответов)
Буферизировать входящий запрос
Иначе
Добавить запрашивающую сторону в список конфликтов (активного запроса)
Если входящий запрос является PRIL
Пометить запрашивающую сторону в списке конфликтов как вызвавшую конфликт PRIL
Если активный запрос является PRL
Ответить сообщением CNFL
Иначе (активным является запрос PRIL)
Ответить сообщением CNFLI
Ответы на запрос-наблюдение
Вызов процедуры:
В кэш представлен запрос в качестве запроса-наблюдения для генерирования надлежащего ответа
Алгоритм:
Искать ответ и следующее состояние в приведенной ниже таблице на основе текущего состояния кэша и типа входящего запроса (следующее состояние S/I означает, что кэш может перевести строку в любое из состояний; Примечание; по-прежнему посылать DATA_F в ответ на сообщение PRL даже при признании недостоверной локальной копии - см. ниже опцию Ответа PRL DATA E/M)
Если запрос-наблюдение PRL обнаружит нужную строку кэша в состоянии М
Инициировать запрос PWL
Буферизировать запрос-наблюдение (задержать отправку DATA_F, пока не завершится перезапись в запоминающее устройство)
Иначе
Если запрос-наблюдение обнаружит нужную строку кэша (в состоянии М, Е или F)
Пометить адрес как перенаправляемый
Перевести строку кэша в следующее состояние
Отправить ответ запрашивающей стороне
Сбор ответов
Вызов процедуры:
Принят ответ от однорангового узла на запрос PRL/PRIL
Алгоритм:
Если ответом является SACK(только в случае с PRL)
Зарегистрировать существование совместно используемой копии в системе
Иначе, если ответом является DATA
Зарегистрировать прием перенаправленных данных от отвечающего узла
Отправить в кэш строку кэша и новое состояние (примечание: строка пока еще не видна для всех!)
Иначе, если ответом является CNFL
Добавить отвечающий узел в список конфликтов
Иначе, если ответом является CNFLI
Добавить отвечающий узел в список конфликтов
Пометить отвечающий узел как вызывающий конфликт PRIL
- Конец Если
Если ответили все одноранговые узлы
Пометить запрос как находящийся в "фазе данных"
Если принят ответ DATA
Отправить базовому узлу CNCL перенаправляющий узел и список конфликтов
Иначе
Отправить базовому узлу READ и список конфликтов
Отмена на базовом узле
Вызов процедуры:
Базовый узел принял CNCL (содержащее перенаправляющий узел и список конфликтов)
Алгоритм:
Отменить ожидающие выполнения операции чтения (если существуют)
Пометить запрашивающий узел "текущим владельцем" этого адреса
Отправить DACK перенаправляющему узлу
Если конфликты отсутствуют
Отправить АСК запрашивающему узлу
-- бесконфликтный кэшированный период завершен
Иначе
Включить список конфликтов для этого адреса как "ожидающие выполнения запросы"
- ждать сообщений READ до отправки сообщений XFR
Запрос READ на базовом узле Вызов процедуры:
Базовый узел принял READ (содержащий список конфликтов)
Алгоритм:
Если отсутствует текущий владелец
Если данные не доступны
Дождаться завершения чтения
Отправить DATA E запрашивающему узлу
Если список конфликтов пуст
Отправить АСК запрашивающему узлу
- бесконфликтный некэшированный период завершен
Иначе
Включить список конфликтов для этого адреса как "ожидающие узлы"
Иначе
Добавить ожидающие разрешения конфликты к "ожидающим узлам" для этого адреса
Удалить запрашивающий узел из числа "ожидающих узлов"
Если отсутствуют (оставшиеся) ожидающие узлы
Отправить XFR (адресат: запрашивающий узел) "текущему владельцу"
Отправить АСК запрашивающему узлу
-- Период завершен
Иначе
Если один или более ожидающих узлов (включая запрашивающий узел) отправили PRIL
Отправить XFRI (адресат: запрашивающий узел) "текущему владельцу"
Иначе
Отправить XFR (адресат: запрашивающий узел) "текущему владельцу"
Обозначить запрашивающий узел "текущим владельцем"
Прием сообщения о передаче
Вызов процедуры:
Запрашивающая сторона приняла сообщение XFR или XFRI (содержащее целевой узел)
Алгоритм:
Ожидать данные, если они еще не приняты
Если принято XFRI
Отправить запрос-наблюдение PRIL в кэш
Иначе
Отправить запрос-наблюдение PRL в кэш
Добавить список конфликтов (за исключением принимающего узла) в пакет DATA. Отправить пакет DATA целевому узлу
Прием переданных данных
Вызов процедуры:
Как результат XFR, запрашивающая сторона приняла DATA (содержит список конфликтов)
Алгоритм:
Отправить данные на процессор
Включить список конфликтов в текущий список конфликтов
Если буферированные запросы совпадают с элементами списка конфликтов
Ответить сообщением CNFL на каждый совпадающий запрос
Перенаправление PACK
Вызов процедуры:
Перенаправляющий узел принял DACK
Алгоритм:
Снять с адреса метку перенаправляемого
Обработать буферированные запросы посредством алгоритма для приема запросов одноранговых узлов
Запрос АСК
Вызов процедуры:
Запрашивающая сторона приняла АСК от базового узла
Алгоритм:
Если активным запросом является PWL
Перевести строку кэша в желаемое следующее состояние (Е или I)
Если буферизирован запрос-наблюдение (PRL обнаружило строку кэша в состоянии М)
Отправить DATA F запрашивающей стороне
Перевести строку кэша в следующее состояние (S) или в состояние I
Иначе (запрос является сообщением PRL или PRIL)
Освободить буферизированные запросы (то есть обрабатывать их, как если бы они только прибыли на узел)
Ожидать данные, если они еще не приняты
Отправить процессору АСК
<<<=КОНЕЦ БАЗОВОГО ПРОТОКОЛА=>>>
Запрос PIL
В вышеприведенных алгоритмах протокола единственным способом для перевода узлом строки кэша из состояния F в состояние Е является признание строки недостоверной (перевести строку в состояние I) и затем запрос PRIL. Это вызывает передачу сообщения DATA.
Для поддержки прямого перехода F→E может использоваться запрос PIL. Этот запрос, отправленный всем одноранговым узлам и базовому узлу, предписывает остальным кэшам признать недостоверными совместно используемые копии строки кэша, содержащиеся в них. Для предотвращения вмешательства в изменение состояния со стороны переданных сообщений PRIL и/или PRL, сообщению PIL может быть присвоен более высокий приоритет.
ИЗМЕНЕНИЯ В БАЗОВОМ ПРОТОКОЛЕ:
Формирование запроса Вызов процедуры:
Кэш сгенерировал новый запрос на (неактивный) адрес
Алгоритм:
Пометить адрес как активный
Если запросом является PRL или PRIL
Отправить запрос всем другим одноранговьм узлам и базовому узлу
>> Если запросом является PIL
>> Отправить запрос всем другим одноранговым узлам
Если запросом является PWL
Отправить запрос базовому узлу
Прием запроса одноранговым узлом
Вызов процедуры:
Одноранговым узлом принят запрос (PRL или PRIL)
Единственное изменение алгоритма состоит в буферизации запроса, если существует активный запрос PIL, как это делается при существовании активного запроса PWL.
Прием одноранговым узлом запроса PIL
Вызов процедуры:
Одноранговым узлом принят запрос PIL
Алгоритм:
Отправить в кэш запрос-наблюдение PIL
Ответы на запросы-наблюдения
Использован тот же самый алгоритм с новой таблицей "Ответ/Следующее состояние" (отсутствуют связанные с PIL элементы для F, Е и М, потому что запрашивающая сторона в состоянии F и состояния F, Е и М является взаимоисключающими)
Сбор ответов
Вызов процедуры:
Принят ответ от однорангового узла на запрос PIL
Алгоритм:
Если все одноранговые узлы ответили
Предписать кэшу перевести строку в состояние Е
Освободить все буферизированные запросы
-- запрос PIL завершен
Непосредственный ответ и M→S PWL
Проблема обработки в связи с сообщениями PRL, обнаруживающими строки кэша в состоянии M, состоит в необходимости перезаписи (отправки сообщения PWL) перед перенаправлением данных. После внесения некоторых незначительных изменений данные могут быть перенаправлены и перезаписаны одновременно. Базовый узел не отправляет DACK, пока он не примет как запрос PWL, так и CNCL от запрашивающего/выигравшего узла.
ИЗМЕНЕНИЯ В БАЗОВОМ ПРОТОКОЛЕ:
Прием запроса базовым узлом
Вызов процедуры:
Базовый узел принял запрос
Алгоритм:
Если запрос - PWL
Инициировать запись в запоминающее устройство
(обработать перенаправление, отмену ожидающих выполнения операций чтения и т.д.)
>> Если PWL было для PRL-обнаружил-М
>> Если принято CNCL
>> Отправить DACK на перенаправляющий узел,
указанный в CNCL
>> Иначе
>> Пометить адрес как перезаписываемый
>> Иначе
>> Отправить АСК обратно запрашивающей стороне
Если запросом является PRL или PRIL
Инициировать чтение из запоминающего устройства
(Буферизировать данные, если чтение закончилось до получения READ, и т.д.)
Ответы на запросы-наблюдения
Вызов процедуры:
Запрос передан (как запрос-наблюдение) в кэш для генерирования надлежащего ответа
Алгоритм:
Выполнить поиск по таблице "Ответ/Следующее состояние" как в базовом протоколе
Если запрос-наблюдение обнаружит строку кэша (в состоянии М, Е или F)
Пометить адрес как перенаправляемый
Перевести строку кэша в следующее состояние
Если запрос-наблюдение PRL обнаружит строку кэша в состоянии М
Инициировать перезапись PWL, помеченным как PRL-обнаружил-М
Отправить DATA_F запрашивающей стороне, отмеченной как PRL-обнаружил-М
Иначе
Отправить ответ запрашивающей стороне
Сбор ответов
Алгоритм:
Различия заключаются в регистрации данных PRL-обнаружил-М и уведомлении базового узла о специальном перенаправлении при отправке CNCL:
Иначе, если ответом является DATA
Зарегистрировать прием отправленных данных с отвечающего узла
Если запрос является PRL и обнаружена строка в состоянии М (указано через сообщение DATA)
Пометить перенаправляющий узел как PRL-обнаружил-М
Отправить строку кэша и новое состояние в кэш (примечание: строка кэша еще не видна для всех!)
Если ответили все одноранговые узлы
Если был принят ответ DATA
Отправить CNCL, перенаправляющий узел (отмеченный как PRL-обнаружил-М, если это произошло), и список конфликтов базовому узлу
Отмена на базовом узле
Вызов процедуры:
базовый узел принял CNCL (содержащее перенаправляющий узел и список конфликтов)
Алгоритм:
Единственное отличие заключается в определении, нужно ли отправить DACK:
Если перенаправляющий узел произвел перезапись PRL-обнаружил-М
Если было принято PWL
Отправить DACK перенаправляющему узлу
Иначе
Пометить адрес как нуждающийся в перезаписи
Иначе
Отправить DACK перенаправляющему узлу
Перенаправление PACK
Отличия отсутствуют. Выданное PWL обработано как однократный пакет (или запрос, завершенный сообщением DACK).
СОСТОЯНИЕ FM
Другой альтернативой сообщениям PRL, обнаруживающим строки в состоянии М, является добавление в MESIF состояния FM. Это состояние указывает совместно используемые копии измененной строки. Как и в состоянии М, если данные вытеснены из кэша, то они должны быть перезаписаны(PWL). Как и в состоянии F, данные не могут быть изменены, и узел отвечает обнаружением на запросы чтения строки.
Если узел, имеющий строку в состоянии М, принимает PRL, он отвечает сообщением DATA_FM вместо выдачи PWL и ответа сообщением DATA_F.
Переход от состояния FM в состояние М не разрешен иначе, кроме как посредством PIL. Непосредственный переход от состояния FM в состояние Е не разрешен.
ИЗМЕНЕНИЯ В БАЗОВОМ ПРОТОКОЛЕ:
Ответы на запросы-наблюдения
Вызов процедуры:
Запрос передан в качестве запроса-наблюдения в кэш для формирования соответствующего ответа
Алгоритм:
Поиск ответа и следующего состояния в приведенной ниже таблице, основанный на текущем состоянии кэша и типе входящего запроса (следующее состояние S/I означает, что кэш может перевести строку в любое из состояний; Примечание: по-прежнему отправлять DATA_F(M) в ответ на PRL, даже если признана недостоверной местная локальная копия - см. ниже опцию Ответа PRL DATA E/M)
Если запрос-наблюдение обнаруживает строку кэша (в состоянии М, Е или F)
Пометить адрес как перенаправляемый
Перевести строку кэша в следующее состояние
Отправить ответ запрашивающей стороне
Бесконфликтные данные
Отправка списка конфликтов совместно с передаваемыми данными трудноосуществима посредством аппаратных средств. Можно отказаться от этого списка конфликтов, если запросы в середине цепи передачи знают, что они находятся в середине и им разрешено ответить на буферизированные запросы (с помощью IACK/SACK) после приема переданных данных. Это позволяет всем остальным конфликтующим узлам осуществлять дальнейшие шаги, и таким образом, выполняя оставшиеся сообщения READ, достигают базового узла.
В этом варианте запросы (PRL и PRIL, то есть запросы чтения) проходят четыре фазы:
1) Фаза отправки - отправка запросов
2) Фаза сбора - сбор ответов (сопровождаемый отправкой сообщений READ или CNCL)
3) Фаза данных - ожидание данных
4) Фаза удержания - в середине цепи конфликтов, задержать данные до сообщения XFR, отправить IACK/SACK на буферизированные и входящие запросы.
В этом варианте выполнения запрос будет знать, что он находится в середине цепочки, если отсутствует сообщение АСК, инкапсулированное в переданное сообщение DATA. Только упомянутая фаза удержания отличается от базового протокола. Фактически фаза данных базового протокола или остается той же самой (для бесконфликтных запросов или запросов в конце цепи периода/цели конфликта), или разделена на две фазы, первая из которых все еще является фазой данных, а вторая теперь является фазой удержания, заканчивающейся после приема XFR.
ИЗМЕНЕНИЯ В БАЗОВОМ ПРОТОКОЛЕ:
Прием запроса одноранговым узлом
Единственное изменение алгоритма состоит в проверке, существует ли активный запрос в фазе удержания:
Если адрес перенаправляется
[то же самое, что и прежде]
Иначе, если адрес не активен
[то же самое, что и прежде]
Иначе, если адрес активен
Если активный запрос - PWL
[то же самое, что и прежде]
Если входящий запрос находится в списке конфликтов активного запроса
[то же самое, что и прежде]
Иначе, если активный запрос находится в "фазе удержания"
Если входящий запрос - PRL
Ответить сообщением SACK (или IACK, если предыдущее PRIL получило IACK)
Иначе - входящий запрос - это PRIL
Пометить активный запрос как нуждающийся в признании недействительным
Ответить сообщением IACK
Иначе, если активный запрос находится в "фазе данных"
[то же самое, что и прежде]
Иначе
[то же самое, что и прежде]
Сбор ответов
Единственным изменением в этом алгоритме является то, что запрос завешен, если он отправляет CNCL и его список конфликтов пуст. Другими словами, система осуществила передачу КЭШ-К-КЭШу и не существовало никаких конфликтов; единственное, что осталось сделать - это уведомить базовый узел, что не требует подтверждения (сообщения АСК).
Примечание: запрос CNCL (с конфликтами) во время ожидания XFR остается в фазе данных, то есть он не входит в фазу удержания.
Отмена на базовом узле
Вызов процедуры:
Базовый узел принял CNCL (содержащее перенаправляющий узел и список конфликтов)
Алгоритм:
Отменить ожидающие выполнения операции чтения (если существуют)
Обозначить запрашивающий узел "текущим владельцем" этого адреса
Отправить DACK узлу отправки
Если конфликты отсутствуют
-- бесконфликтный кэшированный период завершен
Иначе
Включить список конфликтов в виде "ожидающих выполнения запросов" для этого адреса
-- ждать сообщений READ до отправки сообщений XFR
Запрос чтения на базовом узле
Вызов процедуры:
Базовый узел принял READ (содержащий список конфликтов)
Алгоритм:
Если отсутствует текущий владелец
Если данные не доступны
Инициировать чтение в случае необходимости
Ожидать завершения чтения Отправить DATA_E запрашивающему узлу
Если список конфликтов пуст
-- бесконфликтный некэшированный период завершен Иначе
Включить список конфликтов в виде "ожидающих узлов" для этого адреса
-- ждать сообщений READ до отправки сообщений XFR
Иначе
Добавить ожидающие разрешения конфликты к "ожидающим узлам" для этого адреса
Удалить запрашивающий узел из "ожидающих узлов"
Если отсутствуют (оставшиеся) ожидающие узлы
Отправить XFR+ACK (адресат: запрашивающий узел) "текущему владельцу"
-- период завершен
Иначе
Если один или более ожидающих узлов (включая запрашивающий узел) - это PRIL
Отправить XFRI (адресат: запрашивающий узел) "текущему владельцу"
Иначе
Отправить XFR (адресат: запрашивающий узел) "текущему владельцу"
Обозначить запрашивающий узел "текущим владельцем"
Прием сообщения о передаче
Здесь изменение (в дополнение к обработке XFR+ACK) состоит в определении того, был ли имитирован ответ IACK для PRIL во время фазы удержания. Если так, строка признается недостоверной с помощью наблюдения.
Вызов процедуры:
Запрашивающая сторона приняла XFR, XFR+ACK или XFRI (содержащие целевой узел)
Алгоритм:
Ожидать данные, если они еще не приняты
Если принято XFRI или запрос отмечен как требующий признания недостоверным
Отправить запрос-наблюдение PRIL в кэш
Иначе
Отправить запрос-наблюдение PRL в кэш
-- Конец Если
Если принято XFR+ACK
Послать целевому узлу пакет DATA+ACK
Иначе
Отправить целевому узлу пакет DATA
Прием переданных данных
Вызов процедуры:
Запрашивающая сторона приняла DATA или DATA+ACK в результате сообщения XFR (запрашивающая сторона находится в фазе данных, так что она узнает об этом через XFR)
Алгоритм:
Отправить данные на процессор
Если принят пакет DATA
Перевести запрос в фазу удержания
Для каждого буферизированного запроса
Если буферизированный запрос - это PRL
Ответить сообщением SACK (или IACK, если предыдущее PRIL приняло IACK)
Иначе -- буферизированный запрос является PRIL
Отметить локальный запрос как требующий признания недостоверным
Ответить сообщением IACK
иначе - принято DATA+ACK
-- запрос завершен и период завершен
DATA_E/M ответ на PRL
Когда запрос-наблюдение PRL обнаруживает строку кэша, оно должно для поддержания коррегентности ответить сообщением DATA_F, независимо от того, переводит кэш строку в состояние S или I. Можно поддерживать отправку DATA_E при переходе в состояние I, но это требует дополнительной связи с кэшем, чтобы оповестить его о том, что принятое им состояние Е необходимо понизить до состояния F. В основном алгоритм такой, что, если узел уже принявший DATA_E, затем принимает SACK, он должен изменить состояние кэша с Е до F.
Изобретение относится к устройствам кэш-памяти, а именно распределенного разрешения противоречий в многопроцессорной системе, имеющей множество устройств кэш-памяти. Техническим результатом является обеспечение механизма для разрешения конфликтов. Способ разрешения конфликтов обеспечивает согласованность так, что все конфликты могут быть обнаружены, по меньшей мере, одной из конфликтующих запрашивающих сторон, если каждый узел отслеживает все запросы после того, как этот узел выполнил свой собственный запрос. Если строка находится в Исключительном состоянии. Измененном состоянии или состоянии пересылки, конфликты разрешают на узле, содержащем уникальную копию. Выигравший в разрешении конфликтов, и, возможно, проигравшие, сообщают о конфликте базовому узлу, который соединяет попарно отчеты о конфликтах и выдает инструкции на пересылку для обеспечения приема, в конечном счете, всеми запрашивающими узлами запрашиваемых данных. Если запрошенная строка кэша либо некэширована, либо присутствует только в состоянии Совместного Использования, то базовый узел предоставляет копию узла кэша и разрешает конфликты. В одном варианте выполнения период молчания после всех ответов до приема сообщения подтверждения позволяет всем конфликтующим узлам быть осведомленными о конфликтах, в которые они вовлечены. 2 н. и 4 з.п. ф-лы, 7 ил., 3 табл.
1. Способ неспекулятивного распределенного разрешения конфликтующих запросов данных, содержащий этапы, на которых:
принимают от однорангового узла сообщение, содержащее запрос на копию блока данных, хранящихся в запоминающем устройстве, и список узлов, если таковые вообще имеются, выдавших конфликтующие сообщения запроса;
предоставляют копию запрашиваемых данных запрашивающему одноранговому узлу;
принимают последующий конфликтующий запрос от узла из упомянутого списка; и
посылают сообщение предыдущему запрашивающему узлу для передачи копии запрашиваемых данных следующему запрашивающему узлу.
2. Способ по п.1, в котором блок данных содержит строку кэша.
3. Способ по п.1, дополнительно содержащий этап, на котором посылают подтверждающее сообщение на пересылающий узел.
4. Способ неспекулятивного распределенного разрешения конфликтующих запросов данных, содержащий этапы, на которых:
принимают от узла многоузловой системы сообщение, указывающее один или более узлов, выдавших конфликтующие запросы на копию блока данных;
принимают от каждого из узлов, выдавших конфликтующие запросы, сообщение, указывающее конфликт с другим запросом;
посылают копию запрашиваемых данных первому узлу, передавшему сообщение, указывающее конфликт; и
посылают сообщение к текущему узлу-владельцу, предписывающее текущему узлу-владельцу послать копию запрашиваемых данных другому узлу в ответ на последующее сообщение, указывающее конфликт.
5. Способ по п.4, в котором блок данных содержит строку КЭШа.
6. Способ по п.4, в котором текущий владелец содержит узел, имеющий копию блока данных, принятую от соответствующего базового узла или от узла, имеющего копию блока данных, последнюю по времени пересылки от предыдущего текущего владельца.
| US 6405289 B1, 11.06.2002 | |||
| Дорожная спиртовая кухня | 1918 |
|
SU98A1 |
| СПОСОБ И УСТРОЙСТВО ДЛЯ ПОДДЕРЖАНИЯ УПОРЯДОЧЕНИЯ ТРАНЗАКЦИЙ И РАЗРЕШЕНИЯ КОНФЛИКТНЫХ СИТУАЦИЙ В МОСТОВОЙ СХЕМЕ ШИН | 1995 |
|
RU2182356C2 |
| Топчак-трактор для канатной вспашки | 1923 |
|
SU2002A1 |
