способ фильтрации межпроцессорных запросов в многопроцессорных вычислительных системах и устройство для его осуществления

Формула изобретения

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

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

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

4. Устройство по п. 2, отличающееся тем, что узел межпроцессорных запросов содержит К буферных памятей межпроцессорных запросов, каждая из которых соответствует одному из К процессорных узлов многопроцессорной системы, блок сбора ответов на межпроцессорные запросы, дешифратор обратного адреса межпроцессорного запроса, блок регистров и К N-входовых элементов "ИЛИ", причем каждый элемент "ИЛИ" соответствует одной из К буферных памятей межпроцессорных запросов, информационный вход узла межпроцессорных запросов является входом блока регистров, первый выход которого соединен шиной адреса с первыми входами всех буферных памятей межпроцессорных запросов, вторые входы которых соединены шиной обратного адреса межпроцессорного запроса со вторым выходом блока регистров и входом дешифратора обратного адреса межпроцессорного запроса, выход которого подключен ко входу позиционного номера строки блоки сбора ответов на межпроцессорные запросы, N-разрядная группа входов каждой буферной памяти и N входов соответствующего ей элемента "ИЛИ" связаны с разрядами входа результатов фильтрации узла межпроцессорных запросов, соответствующими N процессорам одного из процессорных узлов многопроцессорной системы, прямой выход каждого из N-входовых элементов "ИЛИ соединен с третьим входом соответствующей ему буферной памяти межпроцессорных запросов, а инверсный выход - с одним из входов результатов фильтрации блока сбора ответов на межпроцессорные запросы, выходы буферных памятей межпроцессорных запросов и соответствующие входы ответов на межпроцессорные запросы блока сбора ответов на межпроцессорные запросы образуют соответствующие входы-выходы межпроцессорных обменов узла межпроцессорных запросов, а выход стробов готовности ответов и выход кодов ответов блока сбора ответов на межпроцессорные запросы образуют многоразрядный выход управляющей информации узла межпроцессорных запросов.

Описание изобретения к патенту

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

Обеспечение согласованности (когерентности) данных, находящихся в кэш- и основной памяти, представляет собой известную проблему многопроцессорных вычислительных систем. См. книгу "Parallel & Distributed Computing Handbook" (Edward Y. Zomaya, Ed., McGraw-Hill 1996) [1]. В имеющих широкое распространение мультипроцессорах с шинной организацией эта проблема обычно решается посредством отслеживания запросов, появляющихся на шине (bus snooping). Подобный технический прием обеспечивает достаточно простое решение проблемы, поскольку адрес на шине является видимым для всех процессоров.

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

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

Известен способ для снижения межпроцессорного трафика в многопроцессорных системах с общей памятью, заключающийся в использовании специальных битов - меток, включаемых в элементы таблицы страниц и показывающих, может ли информация из этой страницы находиться в кэш-памяти какого-либо процессора, и реализованный в известном устройстве, содержащем модифицированный блок преобразования виртуальных адресов в физические, расположенный в центральном процессоре, и включающий специальные биты - метки и схемы для их анализа (См. Патент US 6044446, кл. G 06 F 12/00, 1997).

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

По технической сущности наиболее близким к предлагаемому изобретению является способ фильтрации межпроцессорных запросов в многопроцессорных вычислительных системах, заключающийся в предварительной проверке возможности наличия копий запрашиваемых данных в кэш-памятях процессорных узлов системы при поступлении от одного из процессоров запроса на обращение к оперативной памяти и обращении к тем группам процессоров, для которых выявлена такая возможность, а также в передаче сообщений в остальные группы процессоров для обновления в них фильтрующей информации (interest map), которая при обращении к оперативной памяти позволяет с некоторой степенью вероятности определить наличие копий запрашиваемых данных в кэш-памятях системы, а также устройство для фильтрации межпроцессорных запросов ("Снуп-фильтр") в многопроцессорных вычислительных системах, содержащее блок фильтрации, позволяющий определить процессоры или группы процессоров, которые могут иметь в своих кэш-памятях данные, принадлежащие к некоторому пространству адресов (например, страницы памяти, как в предыдущем аналоге), а также специальную память фильтрующей информации для каждого процессора или группы процессоров (см. патент US 5966729, кл. G 06 F 12/12, 1997).

Однако известные способ и устройство требуют значительных аппаратных затрат для обеспечения достаточной степени фильтрации, что приводит к усложнению системы в целом. Затраты оборудования обусловлены тем, что объем памяти фильтра является функцией от объема оперативной памяти системы, а также размножением аппаратуры фильтра, так как количество фильтров равно количеству процессорных узлов (системных узлов) и сложной структурой устройства фильтрации.

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

Техническим результатом является увеличение степени фильтрации межпроцессорных запросов и повышение производительности системы при минимальных аппаратных затратах.

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

Кроме того, устройство фильтрации межпроцессорных запросов в многопроцессорной вычислительной системе, включающей М секций оперативной памяти, системный коммутатор адресов и данных и К процессорных узлов, каждый из которых включает как минимум один процессор и одну кэш-память, где М и К - целые числа, согласно изобретению, содержит узел межпроцессорных запросов и как минимум один блок фильтрации, выполненный с возможностью хранения фильтрующей информации, причем информационный вход блока фильтрации и информационный вход узла межпроцессорных запросов подключены к выходу адресной информации системного коммутатора адресов и данных, входы-выходы межпроцессорного обмена узла межпроцессорных запросов связаны группой двунаправленных шин с вышеуказанными К процессорными узлами, а выход результатов фильтрации блока фильтрации подключен к соответствующему входу узла межпроцессорных запросов, выход управляющей информации которого подключен к соответствующему входу управления системного коммутатора адресов и данных, причем блок фильтрации может содержать входной регистр, дешифратор номера запросчика, L компараторов фрагментов тегов и память фильтрующей информации, состоящую из L сегментов, каждый из которых соответствует одной из кэш-памятей системы, где L - целое число, причем вход дешифратора связан с первым выходом входного регистра шиной номера процессора, выходы дешифратора подключены к входам стробов записи соответствующих сегментов памяти фильтрующей информации, информационные входы которых соединены со вторым выходом входного регистра шиной фрагмента тега, к которой подключен первый вход каждого компаратора фрагментов тегов, второй вход которого подключен к выходу соответствующего сегмента памяти фильтрующей информации, а выход подключен к выходу результатов фильтрации блока фильтрации, третий выход входного регистра соединен шиной индекса с входом адреса каждого сегмента памяти фильтрующей информации, а вход является входом блока фильтрации, кроме того узел межпроцессорных запросов может содержать К буферных памятей межпроцессорных запросов, каждая из которых соответствует одному из К процессорных узлов многопроцессорной системы, блок сбора ответов на межпроцессорные запросы, дешифратор обратного адреса межпроцессорного запроса, блок регистров и К N-входовых элементов "ИЛИ", причем каждый элемент "ИЛИ" соответствует одной из К буферных памятей межпроцессорных запросов, информационный вход узла межпроцессорных запросов является входом блока регистров, первый выход которого соединен шиной адреса с первыми входами всех буферных памятей межпроцессорных запросов, вторые входы которых соединены шиной обратного адреса межпроцессорного запроса со вторым выходом блока регистров и входом дешифратора обратного адреса межпроцессорного запроса, выход которого подключен ко входу позиционного номера строки блока сбора ответов на межпроцессорные запросы, N-разрядная группа входов каждой буферной памяти и N входов соответствующего ей элемента "ИЛИ" связаны с разрядами входа результатов фильтрации узла межпроцессорных запросов, соответствующими N процессорам одного из процессорных узлов многопроцессорной системы, прямой выход каждого из N-входовых элементов "ИЛИ" соединен с третьим входом соответствующей ему буферной памяти межпроцессорных запросов, а инверсный выход - с одним из входов результатов фильтрации блока сбора ответов на межпроцессорные запросы, выходы буферных памятей межпроцессорных запросов и соответствующие входы ответов на межпроцессорные запросы блока сбора ответов на межпроцессорные запросы образуют соответствующие входы-выходы межпроцессорных обменов узла межпроцессорных запросов, а выход стробов готовности ответов и выход кодов ответов блока сбора ответов на межпроцессорные запросы образуют многоразрядный выход управляющей информации узла межпроцессорных запросов.

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

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

На фиг.1 представлена функциональная блок-схема предлагаемого устройства фильтрации межпроцессорных запросов в составе многопроцессорной вычислительной системы, на фиг.2 - принципиальная блок-схема блока фильтрации; на фиг.3 - принципиальная блок-схема узла межпроцессорных запросов; на фиг.4 - принципиальная блок-схема блока сбора ответов на межпроцессорные запросы; на фиг. 5 - блок-схема алгоритма обслуживания запроса с поддержкой согласованности данных и предварительной фильтрацией межпроцессорных запросов.

Устройство фильтрации межпроцессорных запросов в многопроцессорной вычислительной системе (фиг.1) содержит узел 1 межпроцессорных запросов и, как минимум, один блок 2 фильтрации, выполненный с возможностью хранения фильтрующей информации. Информационные входы 3 и 4 блока 2 фильтрации и узла 1 межпроцессорных запросов подключены к выходу адресной информации системного коммутатора 5 адресов и данных, связанному первой и второй группами шин 6-1. ..6-К и 7-1...7-К, соответственно с К процессорными узлами 8-1...8-К, каждый из которых включает как минимум один процессор 9-1...9-N и как минимум одну кэш-память 10-1... 10-N, и М секциями 11-1...11-М оперативной памяти, где М, N и К - целые числа. Входы-выходы 12-1...12-К межпроцессорного обмена узла 1 межпроцессорных запросов связаны группой двунаправленных шин 13-1...13-К с вышеуказанными К процессорными узлами 8-1. ..8-К, а выход 14 результатов фильтрации блока 2 фильтрации подключен к соответствующему входу 15 узла 1 межпроцессорных запросов, выход 16 управляющей информации которого подключен к соответствующему входу управления системного коммутатора 5 адресов и данных. Входы и выходы узла 1 межпроцессорных запросов и блока 2 фильтрации являются многоразрядными.

Блок 2 фильтрации (фиг. 2) содержит входной регистр 17, дешифратор 18 номера запросчика, L компараторов 19-1...19-L фрагментов тегов, и память 20 фильтрующей информации, состоящую из L сегментов 21-1...21-L, каждый из которых соответствует одной из кэш-памятей системы, где L=КN. Вход дешифратора 18 связан с первым выходом входного регистра 17 шиной 22 номера процессора, выходы дешифратора 18 подключены ко входам 23-1...23-L стробов записи соответствующих сегментов 21-1...21-L памяти 20 фильтрующей информации, информационные входы которых соединены со вторым выходом входного регистра 17 шиной 24 фрагмента тега, к которой подключен первый вход каждого компаратора 19-1...19-L фрагментов тегов, второй вход которого подключен к выходу соответствующего сегмента 21-1...21-L памяти 20 фильтрующей информации, а выход подключен к выходу 14 результатов фильтрации блока 2 фильтрации непосредственно или через выходной регистр (см. пунктир). Третий выход входного регистра 17 соединен шиной 25 индекса с входом адреса каждого сегмента 21-1. . . 21-L памяти 20 фильтрующей информации, а вход является входом 3 блока 2 фильтрации.

Узел 1 межпроцессорных запросов (фиг. 3) содержит К буферных памятей 26-1...26-К межпроцессорных запросов, каждая из которых соответствует одному из К процессорных узлов 8-1...8-К многопроцессорной системы, блок 27 сбора ответов на межпроцессорные запросы, дешифратор 28 обратного адреса межпроцессорного запроса, блок 29 регистров и К N-входовых элементов 30-1...30-К "ИЛИ", каждый из которых соответствует одной из К буферных памятей 26-1... 26-К межпроцессорных запросов. Информационный вход 4 узла 1 межпроцессорных запросов является входом блока 29 регистров, первый выход которого соединен шиной 31 адреса с первыми входами всех буферных памятей 26-1...26-К межпроцессорных запросов, вторые входы которых соединены шиной 32 обратного адреса межпроцессорного запроса со вторым выходом блока 29 регистров и входом дешифратора 28 обратного адреса межпроцессорного запроса, выход которого подключен ко входу 33 позиционного номера строки блока 27 сбора ответов на межпроцессорные запросы. N-разрядная группа входов каждой буферной памяти 26-1... 26-К и N входов соответствующего ей элемента 30-1...30-К "ИЛИ" связаны с разрядами входа 15 результатов фильтрации, соответствующими N кэш-памятям 10-1...10-N, одного из процессорных узлов 8-1...8-К многопроцессорной системы. Прямой выход каждого из N-входовых элементов 30-1...30-К "ИЛИ" соединен с третьим входом соответствующей ему буферной памяти 26-1...26-К межпроцессорных запросов, а инверсный выход - с одним из входов 34-1...34-К результатов фильтрации блока 27 сбора ответов на межпроцессорные запросы. Выходы буферных памятей 26-1...26-К межпроцессорных запросов и соответствующие входы 35-1...35-К ответов на межпроцессорные запросы блока 27 сбора ответов на межпроцессорные запросы образуют соответствующие входы-выходы 12-1...12-К межпроцессорных обменов узла 1 межпроцессорных запросов. Выход 36 стробов готовности ответов и выход 37 кодов ответов блока 27 сбора ответов на межпроцессорные запросы образуют многоразрядный выход 16 управляющей информации узла 1 межпроцессорных запросов. Дешифратор 28 обратных адресов и блок 29 регистров могут быть выполнены по соответствующим стандартным схемам.

Блок 27 сбора ответов на межпроцессорные запросы (фиг.4) содержит I групп 38-1. . . 38-1 элементов сбора ответов, номер каждой из которых соответствует обратному адресу межпроцессорного запроса и К дешифраторов 39-1... 39-К обратного адреса, каждый из которых соответствует одному из К процессорных узлов многопроцессорной системы. Каждая из групп 38-1...38-1 элементов сбора ответов на межпроцессорные запросы содержит К RS-триггеров 40-1... 40-К готовности, и соответствующие им элементы 41-1...41-К "И" и элементы 42-1. ..42-K "ИЛИ", формирующие сигнал установки соответствующего триггера в "1", К RS-триггеров 43-1...43-К кода ответа и соответствующие им элементы 44-1. . . 44-К "И", формирующие сигнал установки соответствующего триггера в "1", К-входовой элемент 45 "И", формирующий сигнал готовности строки и К-входовой элемент 46 "ИЛИ", формирующий код ответа строки. Выходы элементов 45 всех групп 38-1...38-1 образуют многоразрядный выход 36 стробов готовности ответов блока 27 сбора ответов на межпроцессорные запросы. Выходы элементов 46 всех групп 38-1...38-1 образуют многоразрядный выход 37 кодов ответов блока 27 сбора ответов на межпроцессорные запросы.

На фиг.1-4 не показаны цепи синхронизации и питания, которые могут быть выполнены стандартным образом.

Пример алгоритма обслуживания запроса с поддержкой согласованности данных и фильтрацией межпроцессорных запросов представлен на фиг.5.

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

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

Способ фильтрации межпроцессорных запросов реализуется в предлагаемом устройстве и осуществляется в следующей последовательности.

При поступлении от одного из процессоров 9-1...9-L, например процессора 9-1, запроса на обращение к секциям 11-1...11-М оперативной памяти и/или запроса на уничтожение копий данных в кэш-памятях 10-2...10-L многопроцессорной системы, производят предварительную проверку возможности наличия копии данных, за которыми производится обращение, в кэш-памятях 10-2...10-L. (Копии данных - это данные, ранее считанные из оперативной памяти и помещенные в одну или несколько кэш-памятей на временное хранение).

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

Из всех сегментов 21-2...21-L памяти 20 фильтрующей информации производят считывание содержащихся в них фрагментов тегов, после чего производят сравнение считанных фрагментов с фрагментом, выделенным из тега адреса запроса.

При отсутствии совпадений делают вывод об отсутствии копий запрашиваемых данных в кэш-памятях 10-2...10-L системы.

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

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

Кроме того, производят обновление памяти 20 фильтрующей информации, для чего в ячейку сегмента 21-1, соответствующего кэш-памяти, связанной с процессором 10-1 (запросчиком), производят запись фрагмента тега, выделенного из адреса запроса.

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

Запросы процессоров 9-1...9-L на обращение к секциям 11-1...11-М оперативной памяти и/или кэш-памятям 10-1...10-L содержат адрес, код операции и данные (для операций записи).

Запросы поступают в системный коммутатор 5 адресов и данных по шинам 6-1. . . 6-К. Устройство управления системного коммутатора адресов и данных выбирает запрос для обслуживания и помещает его в буферную память ожидания ответов на межпроцессорные запросы, входящую в состав системного коммутатора адресов и данных (в зависимости от реализации, буферная память ожидания ответов на межпроцессорные запросы может быть включена в состав контроллеров секций 11-1...11-М оперативной памяти). Адрес запроса в этой буферной памяти является обратным адресом межпроцессорного запроса.

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

Часть адреса, принятая на входной регистр 17 блока 2 фильтрации, делится на фрагмент тега и индекс. Фрагмент тега по шине 24 подается на информационный вход каждого сегмента 21-1...21-L памяти 20 фильтрующей информации и первый вход каждого компаратора 19-1...19-L фрагментов тегов, второй вход которого соединен с информационным выходом соответствующего сегмента 21-1 памяти 20 фильтрующей информации. Индекс по шине 25 подается на адресные входы сегментов 21-1...21-L памяти 20 фильтрующей информации. Номер процессора-запросчика по шине 22 поступает на дешифратор 18, прямые выходы которого подключены ко входам 23-1...23-L стробов записи сегментов 21-1...21-L памяти 20 фильтрующей информации. В результате производится считывание фрагментов тегов из всех сегментов 21-1...21-L памяти 20 фильтрующей информации, кроме сегмента, соответствующего процессору-запросчику, и сравнение считанных фрагментов тегов с фрагментом, выделенным из обслуживаемого запроса. Результаты сравнения с выходов компараторов 19-1...19-L подаются на многоразрядный выход 14 результатов фильтрации блока 2 фильтрации, соединенный со входом 15 результатов фильтрации узла 1 межпроцессорных запросов. В зависимости от реализации для обеспечения правильных временных соотношений и физических требований выход 14 блока 2 фильтрации и/или вход 15 узла 1 межпроцессорных запросов могут быть снабжены регистрами. Одновременно производится запись фрагмента тега со входного регистра 17 в сегмент 21-1 памяти 20 фильтрующей информации, соответствующий процессору-запросчику, т.е. обновление памяти 20 фильтрующей информации.

В узле 1 межпроцессорных запросов формируются межпроцессорные запросы. Каждый межпроцессорный запрос соответствует одному из процессорных узлов 8-1. . . 8-К многопроцессорной системы и состоит из адреса, кода операции и обратного адреса межпроцессорного запроса, принятых на входной блок 29 регистров узла 1 межпроцессорных запросов из системного коммутатора 5 адресов и данных, а также поля результатов фильтрации, соответствующих данному процессорному узлу многопроцессорной системы и являющихся частью многоразрядного входа 15 результатов фильтрации принятых узлом 1 межпроцессорных запросов из блока 2 фильтрации. Результаты фильтрации показывают, в каких именно кэш-памятях 10-1. . .10-N данного процессорного узла могут находиться копии искомых данных. Соответственно при поступлении межпроцессорного запроса в процессорный узел данный запрос отменяется для тех кэш-памятей 10-1...10-N, для которых поле результатов фильтрации содержит 0. Одновременно на элементах 30-1. . .30-К "ИЛИ" формируются обобщенные результаты фильтрации для каждого процессорного узла (каждого межпроцессорного запроса). Если все разряды результатов фильтрации для какого-либо процессорного узла равны 0, т.е. блок 2 фильтрации не обнаружил для него ни одного сравнения фрагментов, то обобщенный результат фильтрации также равен 0 и соответствующий межпроцессорный запрос отменяется полностью.

Сформированные таким образом межпроцессорные запросы поступают на выходные интерфейсы входов-выходов 12-1...12-К межпроцессорных запросов через соответствующие буферные памяти 26-1...26-К межпроцессорных запросов, в которых запросы могут временно храниться при невозможности немедленной передачи (занятости соответствующего входа-выхода).

С входов-выходов 12-1...12-К по шинам 13-1...13-К межпроцессорные запросы передаются в соответствующие процессорные узлы, где производятся обращения к тем кэш-памятям 10-1...10-N, для которых поле результатов фильтрации межпроцессорного запроса содержит "1".

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

Ответы на межпроцессорные запросы по шинам 13-1...13-К через входы-выходы 12-1...12-К узла 1 межпроцессорных запросов поступают на входы 35-1... 35-К блока 27 сбора ответов на межпроцессорные запросы.

Параллельно с формированием межпроцессорных запросов выполняют инициализацию группы элементов сбора ответов на межпроцессорные запросы блока 27 сбора ответов на межпроцессорные запросы. Для этого обратный адрес межпроцессорного запроса со входного блока 29 регистров дешифрируют на дешифраторе 28 и продешифрированный (позиционный) обратный адрес межпроцессорного запроса с выхода дешифратора 28 подают на вход 33 блока 27 сбора ответов на межпроцессорные запросы. Каждый разряд позиционного обратного адреса со входа 33 соответствует одной из групп 38-1...38-1 блока 27 сбора ответов на межпроцессорные запросы. Одновременно на входы 34-1...34-К блока 27 сбора ответов на межпроцессорные запросы подают обобщенные результаты фильтрации для каждого процессорного узла (каждого межпроцессорного запроса) с инверсных выходов N-входовых элементов 30-1...30-К "ИЛИ".

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

Каждый из триггеров 43-1...43-К кода ответа группы устанавливают в "1", если из соответствующего ему процессорного узла для межпроцессорного запроса с обратным адресом, соответствующим номеру группы, приходит ответ с кодом "1", означающим, что обращение к оперативной памяти должно быть отменено (чтение данных будет производиться из одной из кэш-памятей процессорного узла). Необходимые для этого сигналы формируются на дешифраторах 39-1...39-К и элементах 44-1. ..44-К. Код ответа для каждого межпроцессорного запроса является логической суммой (ИЛИ) выходов всех триггеров 43-1...43-К соответствующей строки ожидания ответов и формируется на элементах 46 "ИЛИ".

Межпроцессорный запрос считается выполненным, когда все триггеры 40-1... 40-К соответствующей группы ожидания ответов установлены в "1". В этом случае на выходе элемента 45 "И" появляется "1", после чего все триггеры 40-1... 40-К и 43-1...43-К данной группы ожидания ответов сбрасываются в "0". Кроме того, выходы элементов 45 "И" всех групп 38-1...38-1 ожидания ответов образуют многоразрядный выход 36 стробов готовности, а выходы элементов 46 "ИЛИ" - многоразрядный выход 37 кодов ответов блока 27 сбора ответа на межпроцессорные запросы. С выходов 36 и 37 управляющая информация передается на выход 16 устройства межпроцессорных запросов и далее в системный коммутатор 5 адресов и данных.

Таким образом, в предлагаемых технических решениях достигается высокая по сравнению с прототипом степень фильтрации и повышается производительность системы в целом при меньших аппаратных затратах.