Настоящее изобретение касается области передачи данных в вычислительной системе. Более конкретно, настоящее изобретение касается передачи данных между большим количеством шин, используя мостовые схемы шин.
Предпосылки создания изобретения
Современные вычислительные системы обычно включают в себя большое количество исполнительных устройств, например микропроцессоров, запоминающих устройств, устройств отображения и так далее, которые соединены между собой через системную шину. Системная шина действует таким образом, чтобы передавать адрес, информацию и управляющие сигналы между этими исполнительными устройствами. В некоторых современных вычислительных системах используется большое количество шин, в которых различные исполнительные устройства подсоединены к одной или более шинам. Обычно каждое исполнительное устройство подсоединяют к одной шине.
Мостовые схемы шин часто используют в системах с большим количеством шин для соединения шин и благодаря этому обеспечения возможности исполнительным устройствам, подсоединенным к одной шине, осуществлять доступ к исполнительным устройствам, подсоединенным к другой шине. Функция мостовой схемы обычно включает передачу команд между двумя шинами. Команды, передаваемые посредством мостовой схемы шин, часто имеют связанные с ними данные (например, команды на считывание или запись).
Одна проблема, часто возникающая в вычислительных системах с большим количеством исполнительных устройств, состоит в необходимости сохранения упорядочения транзакций. Поддержание упорядочения транзакций означает, что, если исполнительное устройство записывает в ячейку А в запоминающем устройстве с последующей записью в ячейку В в запоминающем устройстве, другое исполнительное устройство не может считывать новые данные в ячейке В и устаревшие (то есть старые) данные в ячейке А. Ряд программно-реализованных алгоритмов требует взаимоотношения "поставщика-потребителя" и, таким образом, зависят от этого поддержания для гарантирования правильного выполнения функции. Например, предположим, что в системе, содержащей большое количество процессоров, процессор Р1 представляет собой поставщика информации, а процессор Р2 является потребителем информации. Процессор Р1 выполняет операцию записи W1 в ячейке 1 с последующей операцией записи в ячейке 2. Ячейка 2 содержит переменную признака, которая сигнализирует о том, что данные в ячейке 1 действительные. Процессор Р2 непрерывно выполняет операцию считывания R2 в ячейке 2 до тех пор, пока признак станет действительным. После того как признак станет действительным, процессор Р2 выполняет операцию считывания R1 в ячейке 1 с целью считывания данных. Для успешного выполнения алгоритма в многопроцессорной системе очередность, в которой осуществляются записи W1 и W2 процессором Р1, должна быть такой же, в которой, по-видимому, операции R1 и R2 обновлены для процессора Р2.
Мостовая схема шин в системе с большим количеством шин должна учитывать проблему упорядочения транзакций. В вышеприведенном примере процессоры Р1 и Р2 могут быть подсоединены к одной шине, тогда как ячейки 1 и 2 подсоединены ко второй шине, а мостовая схема шин обеспечивает доступ между двумя шинами. Таким образом, мостовая схема шин должна гарантировать, что упорядочение транзакций поддерживается. То есть мостовая схема шин должна поддерживать очередность, в которой осуществляется запись W1 и W2 исполнительным устройством (устройствами).
Один способ поддержания очередности транзакций показан на фиг.1. Показана мостовая схема 100, которая обеспечивает сопряжение между двумя шинами: первой системной шиной 102 и второй системной шиной 104. Исполнительное устройство 130 подсоединено к системной шине 102, а исполнительное устройство 140 подсоединено к системной шине 104. В этой системе мостовая схема шин 100 содержит в себе первую очередь 110, содержащую в себе запросы, выдаваемые на системной шине 102, которые адресованы исполнительному устройству на системной шине 104. Мостовая схема шин 100 содержит в себе также вторую очередь 115, содержащую в себе запросы, выдаваемые на системной шине 104, которые адресованы исполнительному устройству на системной шине 102. В мостовой схеме 100 может также содержаться буферное временное запоминающее устройство 120.
Мостовая схема 100 передает команды между шинами 102 и 104. Например, предположим, что исполнительное устройство 130 выдает запрос, адресованный исполнительному устройству 140. Этот запрос принимает мостовая схема 100 и располагает в очереди 110. В качестве альтернативы, если исполнительное устройство выдает запрос, адресованный исполнительному устройству 130, запрос располагается в очереди 115.
Данные, передаваемые между шинами, запоминаются во временном буферном запоминающем устройстве 120. Например, запрос на считывание, размещенный в очереди 110, исполняется на системной шине 104. Когда исполнительное устройство адресата отвечает, считываемые данные размещаются во временном буферном запоминающем устройстве 120. Исполнительное устройство, выдающее исходящий запрос, в этом случае знает, что данные, предназначенные для удовлетворения его запроса, содержатся во временном буферном запоминающем устройстве 120.
В показанной на рисунке известной системе обе очереди 110 и 115 содержат задержанные запросы и передают запросы на соответственные шины. Когда либо исполнительное устройство 130, либо исполнительное устройство 140 выдает запрос на запись, мостовая схема 100 форсирует упорядочение транзакций посредством предотвращения размещения любых транзакций считывания в противоположной очереди, пока очередь с запросами на запись выключена из работы (то есть транзакция записи выполняется на адресованной шине). Например, если операция записи была размещена в очереди 115, мостовая схема 100 предотвращает размещение любых операций считывания в очереди 110, пока выключена из работы очередь 115.
Хотя этот известный способ эффективно разрешает проблему упорядочения транзакций, но не очень эффективен потому, что он предотвращает использование одной очереди, когда выключена из работы другая. Как описано выше, танзакции не размещаются в одной очереди, когда другая очередь содержит операцию записи.
Таким образом, было бы полезно обеспечить систему, которая разрешает проблему упорядочения транзакций эффективным и рациональным способом. Настоящее изобретение обеспечивает такое решение.
Дополнительно к поддержанию упорядочения транзакций мостовая схема шин должна также избегать ситуаций взаимоблокировки в мостовой схеме. Ситуация взаимоблокировки требует по меньшей мере временной приостановки операции системы, если не восстановления всей системы. Ситуация самоблокировки возникает, например, в том случае, если мостовая схема содержит два запроса, один из которых адресован исполнительному устройству на первой шине, а второй адресован исполнительному устройству на второй шине, и ни один из запросов не может быть удовлетворен, пока не будет выполнен второй. Таким образом, взаимоблокировка препятствует правильной работе мостовой схемы.
Следовательно, было бы выгодно обеспечить систему, которая предотвращает появление взаимоблокировки в мостовой схеме шин, поддерживая в то же время эффективную работу. Как будет показано ниже, настоящее изобретение обеспечивает такое решение.
Краткое описание сущности изобретения
Настоящее изобретение содержит в себе способ и устройство, предназначенные для поддержания упорядочения транзакций и разрешения конфликтных ситуаций в мостовой схеме шин. Мостовая схема шин осуществляет сопряжение между двумя отдельными шинами и содержит в себе две очереди: очередь исходящих запросов и очередь входящих запросов. Запросы, появляющиеся на первой шине, которые предназначены адресату на второй шине (называемые "исходящими запросами"), передаются посредством запросов, тогда как появляющиеся на второй шине запросы, которые предназначены адресату на первой шине (называемые "входящими запросами"), передаются посредством очереди входящих запросов.
Мостовая схема шин включает в себя блок разрешения конфликтных ситуаций при транзакции (БРКСТ), который поддерживает упорядочение обработки запросов и предотвращает взаимоблокировку в мостовой схеме. БКРСТ содержит в себе логическую схему, предназначенную для определения, можно ли запросы размещать в очереди входящих запросов. Если входящий запрос нельзя разместить в очереди, то на инициирующее исполнительное устройство возвращается ответ, чтобы оно позже повторило запрос. БКРСТ включает в себя также логическую схему, предназначенную для определения, можно ли фиксировать запрос или будет ли первая шина остановлена для ожидания ответа.
На исходящий или входящий запрос, который фиксируется, сразу же поступает ответ, то есть инициирующее исполнительное устройство сразу же получает ответ. Однако запрос, который не фиксируется, ожидает ответ, то есть инициирующее исполнительное устройство ожидает попытки запроса на шине адресата.
Блок БРКСТ включает в себя также логическую схему, предназначенную для определения, может ли выполняться запрос на целевой шине. При выполнении этого определения БКРСТ определяет, разблокирована ли или блокирована регистрация в соответствующую очередь (то есть очередь входящих запросов для создания транзакций на второй шине и очередь исходящих запросов для создания транзакций на первой шине), имеются ли какие-либо зарегистрированные транзакции в противоположной очереди запросов и имеется ли право монопольного использования шины адресата.
Краткое описание чертежей
Настоящее изобретение иллюстрируется посредством примера, а не ограничения на рисунках прилагаемых чертежей, на которых подобными ссылочными позициями показаны аналогичные элементы и на которых:
Фиг.1 представляет блок-схему известного варианта осуществления мостовой схемы шин в системе вычислительных машин.
Фиг. 2 представляет общий вид соответствующей настоящему изобретению примерной многопроцессорной вычислительной системы.
Фиг. 3 представляет временную диаграмму двух транзакций шины для одного варианта осуществления настоящего изобретения.
Фиг. 4 представляет примерную блок-схему шин одного варианта осуществления настоящего изобретения.
Фиг. 5а и 5в представляют блок-схему, иллюстрирующую этапы, выполняемые при манипулировании запросом, принимаемым на одной шине, мостовой схемой в одном варианте осуществления настоящего изобретения.
Фиг.6а и 6в представляют блок-схему, иллюстрирующую этапы выполнения при манипулировании запросом, принимаемым на второй шине, мостовой схемой в одном варианте осуществления настоящего изобретения.
Фиг. 7 представляет диаграмму состояний, используемую при определении, разблокирована ли или блокирована регистрация в одной очереди в одном варианте осуществления настоящего изобретения.
Фиг. 8 представляет диаграмму состояний, используемую для определения, разблокирована ли или блокирована регистрация во второй очереди в одном варианте осуществления настоящего изобретения.
Фиг. 9 представляет диаграмму состояний, используемую при определении, выдан ли сигнал разрешения или неразрешения для обслуживания запроса в одном варианте осуществления настоящего изобретения.
Подробное описание изобретения
В последующем подробном описании приводятся многочисленные специфические детали, чтобы обеспечить полное понимание настоящего изобретения. Однако специалисты в данной области техники поймут, что настоящее изобретение можно использовать без этих специфических деталей. В других примерах не приводится подробное описание хорошо известных способов, методов, компонентов и схем, чтобы не затенять аспекты настоящего изобретения.
Некоторые части последующих подробных описаний представлены в виде алгоритмов и символических представлений операций над информационными двоичными разрядами в памяти вычислительной машины. Эти описания и представления в виде алгоритмов являются средствами, используемыми специалистами в области техники обработки данных для более эффективной передачи сущности их работы специалистам в данной области техники. Полагают, что алгоритм здесь и вообще является логической последовательностью этапов, ведущих к требуемому результату. Этапы представляют собой этапы, требующие физических манипулирований физическими величинами. Обычно, хотя и не обязательно, эти величины принимают форму электрических или магнитных сигналов, которые можно запоминать, передавать, сравнивать и подвергать другим манипуляциям. Иногда оказывается удобным, особенно для целей обычного использования, называть эти сигналы двоичными разрядами, значениями, элементами, символами, знаками, терминами, числами и так далее.
Однако необходимо помнить, что все эти и аналогичные термины должны быть связаны с соответствующими физическими величинами и являются просто обычными элементами, применяемыми к этим величинам. Как будет видно из последующего описания, если не установлено специально другим образом, то следует понимать, что использующиеся во всем описании настоящего изобретения такие термины, как "обработка", или "вычисление", или "подсчет", или "определение", или "отображение" и так далее, относятся к действиям и процессам вычислительной системы или аналогичного электронного вычислительного устройства, которое манипулирует и преобразует данные, представляемые в виде физических (электронных) величин в регистрах и запоминающих устройствах вычислительной системы, в другие данные, аналогично представляемые в виде физических величин в запоминающих устройствах или регистрах вычислительной системы или других таких устройств запоминания, передачи и отображения информации.
Соответствующая настоящему изобретению система
На фиг.2 показан общий вид соответствующей настоящему изобретению примерной многопроцессорной вычислительной системы. Настоящее изобретение в общем содержит в себе шину процессоров и запоминающих устройств или другое устройство связи 201, предназначенное для передачи информации между одним или более процессорами 202, 203, 204 и 205. Шина процессоров и запоминающих устройств 201 включает в себя адресные, информационные и управляющие шины. Процессоры 202-205 могут включать в себя небольшую чрезвычайно быстродействующую внутреннюю кэш-память, обычно называемую сверхоперативной памятью (кэш-памятью) первого уровня (L1), предназначенную для временного запоминания данных и команд в микросхеме. Кроме того, к такому процессору, как процессор 205, может быть подсоединена более крупная, менее быстродействующая кэш-память второго уровня (L2), предназначенная для временного запоминания данных и команд с целью использования процессора 205. В одном варианте осуществления соответствующая настоящему изобретению вычислительная система включает в себя в качестве процессоров 202-205 микропроцессоры структуры компании Intel; однако в настоящем изобретении можно использовать любой тип архитектуры микропроцессора или любое из главных устройств обработки цифровых сигналов или других исполнительных устройств.
Ясно, что процессор 202, 203 или 204 может включать в себя также параллельный процессор, например процессор, аналогичный или такой же, как процессор 205. В качестве альтернативы процессор 202, 203 или 204 может содержать в себе сопроцессор, такой как процессор цифровых сигналов. Кроме того, процессоры 202-205 могут представлять собой процессоры различных типов архитектуры.
Шина процессоров и запоминающих устройств обеспечивает доступ системы к подсистемам памяти и ввода-вывода. Контроллер запоминающего устройства 222 соединен с шиной процессоров и запоминающих устройств 201 для управления доступом к запоминающему устройству с произвольной выборкой (ЗУПВ) или другому динамическому устройству запоминания 201 (обычно называемому основной памятью) предназначенному для запоминания информации и команд для процессоров 202-205. К шине процессоров и запоминающих устройств 201 можно подсоединять запоминающее устройство большой емкости 225 типа магнитного диска и дискового запоминающего устройства, предназначенное для запоминания информации и команд, и устройство отображения 223 типа электронно-лучевой трубки (ЭЛТ), жидкокристаллического дисплея (ЖКД) и так далее, предназначенное для отображения информации для пользователя вычислительной машиной.
Мостовую схему ввода-вывода 224 можно подсоединять к шине процессоров и запоминающих устройств 201 и системной шине ввода-вывода 231 с целью обеспечения канала связи или межсетевого перехода для устройств как на шине процессоров и запоминающих устройств 201, так и на шине ввода-вывода 231 с целью выборки или передачи данных между устройствами на другой шине. Мостовая схема 224 функционирует по существу как интерфейс между системной шиной ввода-вывода 231 и шиной процессоров и запоминающих устройств 201.
Кроме того, шину ввода-вывода 242 можно соединить с шиной процессоров и запоминающих устройств 201 через мостовую схему 240. Шину ввода-вывода можно подсоединять к дополнительным периферийным устройствам, таким как устройства 232-236, подсоединенным к системной шине ввода-вывода 231.
В одном варианте осуществления настоящего изобретения шина ввода-вывода 246 подсоединена к системной шине ввода-вывода 231 через мостовую схему 245. Шину ввода-вывода 246 можно подсоединять к дополнительным периферийным устройствам, например устройствам 232-236, подсоединенным к системной шине ввода-вывода 231. В одном варианте осуществления шина ввода-вывода работает на стандарте (например, ЕTSА (расширенный промышленный стандарт шинной архитектуры)), отличном от стандарта шины ввода-вывода 231 (например, РСI (интерфейс периферийных устройств)).
Шина ввода-вывода 231 обеспечивает связь между периферийными устройствами в вычислительной системе. Устройства, которые можно подсоединять к системной шине 231, включают в себя устройство отображения 232 типа электронно-лучевой трубки, жидкокристаллического дисплея и так далее, буквенно-цифровое входное устройство 233, включающее в себя буквенно-цифровые и другие клавиши и так далее, предназначенные для передачи и выбора информации и команд на другие устройства вычислительной системы (например, процессор 202), и устройство управления курсором 234, предназначенное для управления перемещением курсора. Кроме того, к системной шине 231 можно также подсоединять устройства для получения твердых копий 235 типа графопостроителя или печатающего устройства, предназначенного для обеспечения визуального представления изображений, полученных вычислительной машиной, и запоминающее устройство большой емкости 236 типа магнитного диска и дискового запоминающего устройства, предназначенного для запоминания информации и команд.
Следует понимать, что в некоторых реализациях может не потребоваться обеспечивать устройство, предназначенное для отображения информации. Некоторые реализации настоящего изобретения могут включать в себя дополнительные процессоры или другие компоненты. Кроме того, некоторые реализации настоящего изобретения могут не потребовать включения всех вышеперечисленных компонентов. Например, процессоры 202-204, устройство отображения 223, шина ввода-вывода 242 или запоминающее устройство большой емкости 225 могут не подсоединяться к шине процессоров-запоминающих устройств 201. Более того, многие из показанных периферических устройств, подсоединенных к системной шине ввода-вывода 231, можно подсоединять к шине процессоров-запоминающих устройств 201.
В настоящем изобретении транзакции шин появляются на процессорных шинах (например, показанной на фиг. 2 шины процессоров и запоминающих устройств 201) в вычислительной системе конвейерным способом. То есть в одно и то же время может задерживаться большое количество транзакций шин, каждая из которых не полностью завершена. Следовательно, когда запрашивающее исполнительное устройство начинает транзакцию шины посредством передачи адреса в шину, транзакцией шины может быть только одна из группы ожидающих в данный момент транзакций шины. Хотя транзакции шины конвейеризированы, транзакции шины в настоящем изобретении не должны полностью выполняться одна за другой, так что настоящее изобретение выполняет разделение транзакций шины. Следовательно, настоящее изобретение позволяет завершать ответы на запросы не по порядку. Примерный протокол шины для ответов не по порядку описан в заявке на патент США с регистрационным номером 07/____, зарегистрированной 30 июня 1993 года под названием "Способ и устройство, предназначенные для выполнения транзакций шины в вычислительной системе", применение которой переуступлено правоприемнику настоящего изобретения.
Настоящее изобретение приспособлено для разделения транзакций посредством расщепления транзакций шины по существу на две независимые транзакции. Первая транзакция включает в себя запрос данных (или сигнал завершения) запрашивающим запоминающим устройством и ответ отвечающим исполнительным устройством. Запрос может состоять из посылки адреса на адресную шину и первого маркера. Ответ может включать в себя посылку запрашиваемых данных (или сигналов завершения), если отвечающее исполнительное устройство готово для ответа. В этом случае транзакция шины оканчивается. Однако, если отвечающее исполнительное устройство не готово выдать запрос (то есть данные или сигналы завершения), ответ может включать в себя посылку второго маркера. В этом случае вторая транзакция содержит в себе повторную посылку второго маркера с запрашиваемыми данными (или сигналами завершения) отвечающим исполнительным устройством запрашивающему исполнительному устройству, так что запрашивающее исполнительное устройство принимает первоначально запрашиваемые данные для завершения транзакции.
Если отвечающее исполнительное устройство не готово завершить транзакцию шины, то отвечающее исполнительное устройство посылает задержанный ответ по шине в его соответственное время ответа. Запрашивающее исполнительное устройство принимает задержанный ответ. Когда отвечающее исполнительное устройство оказывается готовым завершить задержанную транзакцию шины, отвечающее исполнительное устройство разрешает конфликтную ситуацию в отношении права монопольного пользования шиной. После получения права монопольного использования шины отвечающее исполнительное устройство посылает задержанный ответ, включающий в себя второй маркер на шине. Запрашивающее исполнительное устройство контролирует шину и принимает второй маркер в качестве части задержанного ответа. В настоящем изобретении запрашивающее исполнительное устройство фиксирует второй маркер. Затем запрашивающее исполнительное устройство определяет, соответствует ли второй маркер, посылаемый отвечающим исполнительным устройством, первому маркеру. Если запрашивающее исполнительное устройство определяет, что второй маркер от отвечающего исполнительного устройства не соответствует первому маркеру (который выработан запрашивающим исполнительным устройством), то данные на шине (или сигнал завершения) не учитываются, а запрашивающее исполнительное устройство продолжает контроль шины. Если запрашивающее исполнительное устройство определяет, что второй маркер, полученный от отвечающего исполнительного устройства, соответствует первому, то данные на шине (или сигналы завершения) представляют собой данные, первоначально запрашиваемые запрашивающим устройством, и запрашивающее исполнительное устройство фиксирует данные на информационной шине.
В одном варианте осуществления настоящего изобретения деятельность шины иерархически организована в операции транзакции и этапы. Операция представляет собой процедуру шины, которая является элементарной для программного обеспечения, например, считывания естественным образом расположенной ячейки запоминающего устройства. Исполнение операции обычно требует одну транзакцию, но может потребоваться большое количество транзакций, например, в случае задержанных ответов, при которых запросы и ответы представляют собой различные транзакции. Транзакция представляет собой набор действий шины, связанных с сигнальным запросом, от разрешения конфликтной ситуации шины запроса до передач иницируемых ответом данных на шине данных. В этом варианте осуществления транзакция представляет собой набор действий шины, связанных с сигнальным запросом, от разрешения конфликтной ситуации шины запроса до передачи инициируемых ответом данных на шине данных.
Транзакция содержит до шести различных этапов. Однако некоторые этапы на основании типа транзакции и ответа являются необязательными. На этапе используется конкретная группа сигналов для передачи конкретного типа информации.
Этими этапами являются:
Этап разрешения конфликтной ситуации.
Этап запроса.
Этап ошибки.
Этап поиска.
Этап ответа.
Этап передачи данных.
В одном режиме этап передачи данных является необязательным и используется в том случае, если транзакция представляет собой передачу данных. Этап данных инициируется запросом, если в момент инициирования запроса имеются данные (например, в случае транзакции записи). Этап данных инициируется ответом в том случае, если во время вырабатывания ответа транзакции имеются данные (например, в случае транзакции считывания). Транзакция может содержать и инициируемую запросом передачу данных, и инициируемую ответом передачу данных.
Кроме того, различные этапы от различных транзакций могут перекрываться, обеспечивая благодаря этому конвейеризацию использования шины и улучшая производительность шины. На фиг. 3 показаны примерные перекрываемые этапы запроса-ответа для двух транзакций. Рассматривая фиг.3, отметим, что каждая транзакция начинается с этапа разрешения конфликтной ситуации, на котором запрашивающее исполнительное устройство становится владельцем шины. Второй этап представляет собой этап запроса, на котором владелец шины возбуждает информацию запроса и адреса на шине. После этапа запроса новая транзакция поступает в очередь обратного магазинного типа в порядке очередности. Все исполнительные устройства шины, включая запрашивающее исполнительное устройство, поддерживают идентичные последовательные очереди и добавляют каждый новый запрос к этим очередям. На фиг.3, например, запрос 1 возбуждается в CLK3, наблюдается в CLK4 и в последовательной очередности, начинающейся в СLК5. Третий этап транзакции представляет собой этап ошибки через три трактовых импульса после этапа запроса. Этап ошибки показывает любые немедленные ошибки, запускаемые запросом. Четвертый этап транзакции представляет собой этап поиска, начинающийся через четыре или более трактовых импульсов от этапа запроса. Этап поиска показывает, действительная ли связанная кэш-строка в транзакции или видоизменена (загрязнена) в какой-либо быстродействующей буферной памяти исполнительного устройства. Этап поиска показывает также, завершается ли транзакция в последовательности или задерживается для возможного последовательного завершения.
Транзакции следуют последовательно в очереди обратного магазинного типа. Самая верхняя транзакция в последовательной очереди поступает на этап ответа. Этап ответа показывает, неуспешно или успешно завершена транзакция, сразу ли прошел ответ или задержан и включает ли в себе транзакция этап данных.
Если транзакция содержит в себе этап иницируемых ответом данных, то она вводит передачу данных вместе с этапом ответа, транзакция удаляется из последовательной очереди при завершении этапа ответа и (необязательно) этапа иницируемой ответом передачи данных. Как показано на фиг.3, транзакция 1 эффективно изымается из последовательной очередности при импульсе CLK15.
Вследствие описанной выше сущности расщепления транзакции шины можно видеть, что в любой данный момент может ожидать обработки большое количество запросов, на которые не получены ответы. В одном варианте осуществления настоящего изобретения каждое исполнительное устройство на шине может иметь до восьми ожидающих транзакций.
Мостовая схема шин
На фиг. 4 представлена примерная блок-схема мостовой схемы шин одного варианта осуществления настоящего изобретения. В одном варианте осуществления показанная на фиг.4 мостовая схема 400 шин представляет собой показанную на фиг.2 мостовую схему 223. В одном варианте осуществления настоящего изобретения шина ввода-вывода 402 функционирует в соответствии с хорошо известным стандартом шин PCI. Однако следует отметить, что шина ввода-вывода 402 может функционировать в соответствии с любым из широкого разнообразия стандартов, таких как хорошо известные стандарты шин ELSA (расширенный промышленный стандарт шинной архитектуры), ISA (архитектура промышленного стандарта) или VESA (Ассоциация по стандартам в области видеоэлектроники).
В последующем описании мостовая схема 400 шин представлена в виде подсоединенной к процессорной шине и шине ввода-вывода. Однако специалисты в данной области техники должны понимать, что описываемые ниже примеры и варианты осуществления применимы в равной степени к взаимному соединению любых двух шин, а не только процессорной шины и шины ввода-вывода.
Шинный интерфейс 410 включает в себя блок разрешения конфликтных ситуаций 411, регистры конфигурации 412, логическую схему отображения адресов 413, последовательную очередь 414 и конечный автомат процессора 417. Блок разрешения конфликтных ситуаций 411 управляет разрешением конфликтных ситуаций мостовой схемы шин 400 в отношении доступа к процессорной шине 401. Разрешение конфликтных ситуаций в отношении доступа к процессорной шине 401 можно выполнять любым из широкого разнообразия обычных способов. Регистры конфигурации 412 обеспечивают значения конфигурации для работы мостовой схемы 400 в вычислительной системе. Эти значения включают в себя, например, идентификатор мостовой схемы для мостовой схемы 400 и протоколы контроля ошибок для процессорной шины 401 и шины ввода-вывода 402. Конечный автомат процессора 417 передает запросы между очередью входящих запросов 430 и процессорной шиной 401, как более подробно описано ниже.
Логическая схема отображения адресов 413 преобразует адреса, принимаемые с шины ввода-вывода 402 в надлежащий формат для процессорной шины 401, если это необходимо. То есть в системах, где процессорная шина 401 и шина ввода-вывода 402 используют различные стандарты, запрос с шины ввода-вывода 402 может назначить адрес, который не соответствует формату, подлежащему размещению на процессорной шине 401. Логическая схема отображения адресов 413 выполняет транзакцию таким образом, что адрес соответствует стандартам для процессорной шины 401. Эта транзакция базируется на стандартах двух шин и выполняется обычным способом.
Мостовая схема 400 включает в себя также очередь исходящих запросов 420, которая принимает запросы с процессорной шины 401 через интерфейс шины 410 и декодирующее устройство исходящих запросов 415. В одном варианте осуществления очередь 420 представляет собой обычную очередь обратного магазинного типа. Декодирующее устройство исходящих запросов 415 определяет, фиксирует ли мостовая схема 400 запрос (то есть задерживает ли запрос или регистрирует его), и отвечает инициирующему исполнительному устройству на процессорной шине 401, показывая, зафиксирован ли был запрос. Затем декодирующее устройство 415 располагает запрос в очередь исходящих запросов 420. В одном варианте осуществления настоящего изобретения очередь исходящих запросов 420 содержит в себе четыре участка, предназначенных для содержания до четырех исходящих транзакций.
В одном варианте осуществления настоящего изобретения каждый участок очереди исходящих запросов 420 включает в себя поле признака. Это поле признака показывает информацию о том, представляет ли запрос на конкретном участке часть блокированной транзакции или фиксирована ли мостовой схемой 400 транзакция.
Транзакции изымаются из верхней части очереди исходящих запросов 420 организующей программой шины ввода-вывода 425 и выдаются в шину ввода-вывода 402 через интерфейс шины 450. При приеме ответа с исполнительного устройства адресата на шине ввода-вывода 402 организующая программа шины ввода-вывода 425 возвращает ответ в интерфейс шины 410 либо непосредственно, либо через очередь входящих запросов 430. Если мостовая схема 400 зафиксировала транзакцию, то ответ размещается в очередь входящих запросов 430. Если мостовая схема 400 не зафиксировала транзакцию, то ответ возвращается непосредственно в интерфейс 410. В одном варианте осуществления настоящего изобретения сведения о том, зафиксировала ли мостовая схема 400 транзакцию, содержатся в поле признака, связанного с запросом в очереди исходящих запросов 420. Таким образом, организующая программа шины 425 на основании этого поля признака определяет, следует ли разместить ответ в очереди входящих запросов 430 или вернуть его непосредственно в интерфейс 410.
Интерфейс шины ввода-вывода 450 включает в себя блок разрешения конфликтных ситуаций 451, логическую схему декодирования команд 452 и логическую схему отображения адресов 453. Логическая схема отображения адресов 453 преобразует адреса, принимаемые от организующей программы шины ввода-вывода 425 в формате процессорной шины 401 в надлежащий формат для шины ввода-вывода 402. Это преобразование аналогично преобразованию, выполняемому описанной выше логической схемой отображения адресов 413. Блок разрешения конфликтных ситуаций 451 управляет запросами мостовой схемы 400 в отношении доступа к шине ввода-вывода. Блок разрешения конфликтных ситуаций 451 работает обычным образом, определяемым протоколом разрешения конфликтных ситуаций для шины ввода-вывода 402.
Логическая схема декодирования команд 452 преобразует команды между форматом процессорной шины 401 и форматом шины ввода-вывода 402 аналогично логической схеме отображения адресов 453. В одном варианте осуществления настоящего изобретения процессорная шина 401 и шина ввода-вывода 402 используют различные протоколы. Таким образом, команды, выдаваемые на процессорной шине 401, вначале преобразуются перед выполнением на шине ввода-вывода 402. В одном варианте осуществления это преобразование выполняет логическая схема декодирования команд 452. Это преобразование можно выполнять, используя любой из большого разнообразия обычных технических приемов, понятных специалистами в данной области техники.
Очередь входящих запросов 430 передает запросы с шины ввода-вывода 402 на интерфейс процессорной шины 410. Эти запросы образуются на шине ввода-вывода 402 и передаются в очередь 430 через интерфей шины 450 и устройство управления места назначения (целевое) шины ввода-вывода 445. В одном варианте осуществления очередь 430 содержит четыре участка, предназначенных для содержания до четырех исходящих транзакций, и действует в качестве обычной очереди FIFO (обратного магазинного типа). Целевое устройство управления шины 445 либо размещает запрос в очереди 430, либо повторно передает запрос. Если запрос передается повторно, на инициирующее исполнительное устройство на шине ввода-вывода 402 передается повторный ответ, информируя это исполнительное устройство о том, что оно должно позже повторно передать запрос.
В одном варианте осуществления настоящего изобретения каждый участок очереди входящих запросов 430 включает поле признака. Это поле признака содержит информацию о том, зарегистрировала ли мостовая схема 400 транзакцию на конкретном участке.
Схема управления адресата (целевая) 445 определяет необходимо ли повторно передать запрос или разместить его в очередь входящих запросов 430 на основании входного сигнала, поступающего с блока размещения входящей очереди 425 и блока разрешения конфликтных ситуаций при транзакции (БРКСТ) 418. Блок распределения входящей очереди 425 контролирует количество имеющихся участков в очереди входящих запросов 430. Если участок имеется, то схема управления адресата 445 размещает запрос в очередь 430, если блок БРКСТ 418 выдает разрешение на запрос; если участок отсутствует, то схема управления адресата 445 повторно передает запрос.
В одном варианте осуществления настоящего изобретения блок БРКСТ 418 включает в себя конечный автомат приоритета 421, конечный автомат разблокирования регистрации исходящих запросов 422, конечный автомат разблокирования регистрации входящих запросов 423 и регистр повторной передачи 424. Конечный автомат приоритета 421 используется блоком БРКСТ 418 при определении, следует ли выдавать разрешение на запрос, как более подробно описывается ниже со ссылкой на фиг. 9. Конечный автомат разблокирования регистрации исходящих запросов 422 определяет, разблокирована ли или блокирована регистрация в очередь исходящих запросов 420, как описано более подробно ниже со ссылкой на фиг.7. Конечный автомат разблокирования регистрации входящих вызовов 423 определяет, блокирована ли или разблокирована регистрация в очередь входящих запросов 430, как описывается более подробно ниже со ссылкой на фиг.8. Регистр повторной передачи 424 используется блоком БРКСТ 418 с целью контроля, принимает ли запрос от процессорной шины 401 два последовательных повторно передаваемых ответа, как более подробно описывается ниже.
Очередь входящих запросов 430 принимает также ответы на задержанные запросы, которые были размещены в очереди исходящих запросов 420. Эти ответы принимаются очередью 430 через формирователь задержанных ответов 440 и организующую программу шины ввода-вывода 425. Таким ответом может быть, например, ответ на задержанное считывание, размещенное в очереди 420.
Запросы (или ответы) в очереди входящих запросов 430 передаются на процессорную шину 401 через интерфейс шины 410. Когда одна или более транзакций задерживаются в очереди входящих запросов 430, очередь 430 показывает это условие посредством посылки сигнала на конечный автомат процессоров 417. Затем интерфейс шины 410 разрешает конфликтную ситуацию в отношении доступа к процессорной шине 401 и при разрешении доступа конечный автомат процессоров 417 передает задерживающуюся транзакцию (транзакции) в очереди 430 адресуемому исполнительному устройству (устройствам) на процессорной шине 401.
И очередь входящих запросов 430, и очередь исходящих запросов 420 имеют связанные с ним буферы данных. Эти буферы данных требуются для некоторых транзакций, например, запрос на считывание, поступающий с процессорной шины 401, требует буферизации входящих данных, потому что он осуществляет поиск данных на шине ввода-вывода 402. Блок назначения буферизации входящих данных, который включен в блок размещения в очереди входящих запросов 435, контролирует возможность использования буферов поступающих данных, то есть общего имеющегося количества и количества использованных в данный момент. Если запрос требует буферизации поступающих данных, то блок БРКСТ 418 запрашивает один буфер и либо принимает один буфер, либо нет.
В одном варианте осуществления настоящего изобретения и очередь исходящих запросов 420, и очередь входящих запросов 430 включает в себя двоичные разряды, показывающие, содержит ли конкретный участок достоверное содержимое. Эти двоичные разряды называются "разрядами достоверности". Таким образом, если конкретный участок в очереди содержит транзакцию, его разряд достоверности устанавливается; либо участок, разряд достоверности которого не установлен, не содержит достоверного содержимого.
Описанное выше требуемое многими программно-реализованными алгоритмами взаимоотношение поставщика-потребителя будет поддерживаться в мостовой схеме шин. Поддержание упорядочения транзакций в мостовой схеме гарантирует, что соблюдается взаимоотношение поставщика-потребителя.
В одном варианте осуществления настоящего изобретения упорядочение транзакций поддерживается посредством блокирования регистрации в "противоположном направлении" всякий раз, когда обслуживается считывание. То есть, если в очередь исходящих запросов 420 размещается запрос на считывание, регистрация входящих запросов блокируется. Ни один запрос не регистрируется в очереди входящих запросов 430, пока разблокирована регистрация входящих запросов. Точно так же, если в очередь входящих запросов 430 размещается запрос на считывание, регистрация исходящих запросов блокируется. Ни один запрос не регистрируется в очереди исходящих запросов 420, пока разблокирована регистрация исходящих запросов.
В одном варианте осуществления настоящего изобретения процессорная шина 401 обеспечивает четыре различных типа запросов на считывание-запись. Этими типами являются:
1) регистрируемые запросы на запись, 2) нерегистрируемые запросы на запись, 3) допускающие задержку запросы на считывание, 4) не допускающие задержку запросы на считывание. Регистрируемые запросы на запись представляют собой запросы на запись, которые фиксирует мостовая схема. То есть мостовая схема возвращает ответ фиксирования на запрос инициирующего исполнительного устройства, даже если запрос запомнен в очереди и на самом деле еще не передан адресуемому исполнительному устройству. Нерегистрируемые запросы на запись представляют собой запросы, которые не могут быть сразу же зафиксированы; мостовая схема 400 останавливает процессорную шину 401, пытается выполнить запрос на шине ввода-вывода 402 и посылает ответ на инициирующее исполнительное устройство. Допускающие задержку запросы на считывание являются запросами, на которые мостовая схема выдает задержанный ответ. Инициирующее исполнительное устройство освобождает шину, зная, что мостовая схема 400 несколько позже вернет ответ. Не допускающие задержку запросы на считывание аналогичны нерегистрируемым запросам на запись: мостовая схема 400 останавливает процессорную шину 401, предпринимает запрос на шине ввода-вывода 402 и возвращает ответ инициирующему исполнительному устройству.
В одном варианте осуществления настоящего изобретения могут задержаться максимум два запроса на считывание. Таким образом, если мостовая схема 400 принимает от процессорной шины 401 два запроса на считывание, то оба задерживаются и выводятся в очередь исходящих запросов 420. Однако, если с процессорной шины 401 принимается третий запрос на считывание, то запрос становится не допускающим задержку считыванием. Когда предпринимается попытка выполнить один из задержанных запросов на считывание на шине ввода-вывода 402 и ответ размещается в очереди входящих запросов 430, может быть задержан последующий запрос на считывание, поступающий в очередь исходящих запросов 420.
В одном варианте осуществления настоящего изобретения мостовая схема 400 классифицирует поступающие с шины ввода-вывода 402 запросы на считывание-запись на две категории: 1) нерегистрируемые запросы и 2) регистрируемые запросы. Обе эти категории включают в себя запросы на считывание и запросы на запись. Нерегистрируемые запросы представляют собой запросы, которые нельзя сразу же фиксировать. Мостовая схема 400 удерживает шину ввода-вывода 402 (то есть препятствует выдаче запросов по шине другим подсоединенным к шине исполнительным устройством), пока делается попытка исполнить нерегистрируемый запрос на процессорной шине 401. Регистрируемые запросы представляют собой запросы, которые сразу же могут фиксироваться. Эти запросы размещаются в очереди входящих запросов 430 и шина ввода-вывода 402 не удерживается.
Таким образом, посредством блокирования регистрации в противоположном направлении мостовая схема 400 предотвращает регистрацию запроса на запись в противоположном направлении. Как более подробно будет показано ниже, нерегистрируемый запрос на запись не обслуживается до обслуживания запроса на считывание, регистрация которого блокирована. Это предотвращает считывание ранее выданного запроса на считывание данных, записанных посредством ранее выданной транзакции на запись.
Блок БРКСТ представляет собой также возникновение ситуации самоблокировки в мостовой схеме 400. Ситуация самоблокировки может возникнуть, например, в том случае, если задержанный запрос на считывание был на верху очереди исходящих запросов 420, незадержанный запрос на считывание был в очереди 420 позади задержанного запроса на считывание, а запрос на считывание был на верху очереди входящих запросов 430. Запрос на считывание в очереди 430 будет удерживать шину ввода-вывода 402, предотвращая тем самым исполнение задержанного запроса на считывание в очереди исходящих запросов в шине ввода-вывода 402. Точно также не задержанный запрос на считывание в очереди 420 остановит процессорную шину 401, предотвращая тем самым исполнение запроса на считывание в очереди 430 на процессорной шине 401. Таким образом, можно видеть, что при этих условиях мостовая схема взаимоблокируется, потому что ни очередь 420, ни очередь 430 не могут продвинуться.
Блок БРКСТ 418 устраняет такую ситуацию самоблокировки посредством предотвращения ввода нерегистрируемых запросов в очередь входящих запросов 430, пока блокируется регистрация исходящей заявки и отсутствует зарегистрированная исходящая заявка или задержанные заявки задерживаются в очереди исходящих заявок 420. Транзакции, поступающие в мостовую схему 400 из процессорной шины 401, не задерживаются и не фиксируются, пока в очереди входящих запросов 430 больше не задерживается нерегистрируемый входящий запрос (запросы). Это более подробно описано ниже со ссылкой на фиг.9.
В одном варианте осуществления настоящего изобретения процессорная шина 401 и шина ввода-вывода 402 функционируют в различных областях тактовых импульсов. В одном варианте осуществления процессорная шина 401 работает на частоте 66 МГц, тогда как шина ввода-вывода 402 работает на частоте 33 МГц. Блок БРКСТ 418 обеспечивает интерфейс между двумя областями тактовых сигналов, позволяя и декодирующему устройству исходящих запросов 415, и целевому управляющему устройству шины ввода-вывода 425 фиксировать или не фиксировать запросы, основываясь на том, какие типы других запросов уже зафиксированы.
Когда процессорная шина 401 и шина ввода-вывода 402 работают в различных областях тактовых частот, некоторые элементы мостовой схемы 400 работают в области тактовых частот процессорной тины 401, а некоторые элементы работают в области тактовых частот шины ввода-вывода 402. В одном варианте осуществления это разделение элементов между областями тактовых частот показано на фиг. 4 пунктирной линией 403. Элементы на стороне процессорной шины 401 от линии 403 работают в области тактовых частот процессорной шины 401, а элементы на стороне шины ввода-вывода 402 от линии 403 работают в области тактовых частот шины ввода-вывода 402. Сигналы, которые передаются между элементами двух областей тактовых частот, синхронизируются, используя блоки синхронизации. Эти блоки работают обычным способом, передавая сигналы из одной области тактовых импульсов в другую.
Например, в одном варианте осуществления настоящего изобретения блок разрешения конфликтных ситуаций при транзакции (БРКСТ) 418 и целевое устройство управления шины ввода-вывода 445 работают в той же области тактовых частот, как и процессорная шина 401. Блок БРКСТ 418 показывает целевому управляющему устройству шины ввода-вывода 445, разблокирована ли регистрация в очередь входящих запросов 430, и показывает декодирующему устройству 415, разблокирована ли регистрация в очередь исходящих запросов 420, как более подробно описано ниже. Таким образом, благодаря использованию этих сигналов разблокирования регистрации и целевое управляющее устройство шины ввода-вывода 445, и декодирующее устройство 415 могут сразу же фиксировать транзакции в их собственных областях тактовых импульсов: когда регистрация разблокирована в обоих направлениях, синхронизация не нужна,
Инициирующиеся на процессорной шине транзакции
На фиг.5а и 5в представлена блок-схема этапов, выполняемых при манипулировании запросом, принимаемым мостовой схемой 400 с процессорной шины 401 в одном варианте осуществления настоящего изобретения. На этапе 505 мостовая схема 400 принимает запрос с инициирующего исполнительного устройства, подсоединенного к процессорной шине 401. Необходимо отметить, что хотя исполнительное устройство является инициирующим исполнительным устройством на процессорной шине 401, это исполнительное устройство может быть не инициировало запрос. Например, запрос может инициировать исполнительное устройство, подсоединенное к показанной на фиг.2 шине ввода-вывода 242, которая адресует исполнительное устройство на системной шине ввода-вывода 231. Этот запрос инициируется на шине процессоров и запоминающих устройств 201 мостовой схемы 240 и принимается мостовой схемой 224. Таким образом, хотя инициирующим исполнительным устройством на шине 201 является мостовая схема 240, мостовая схема 240 не инициирует запрос.
Возвращаясь к фиг. 5а, отметим, что при приеме запроса с процессорной шины 401 на этапе 510 мостовая схема 400 определяет, является ли запрос запросом на считывание. Если запрос не является запросом на считывание, то декодирующее устройство 415 определяет на описываемом ниже этапе 525, следует ли фиксировать транзакцию. Если запрос является запросом на считывание, то декодирующее устройство 415 на этапе 512 посылает сигнал на блок БРКСТ 418, показывающий, что регистрация входящего запроса будет блокирована. Блокирование регистрации входящего запроса более подробно описывается ниже со ссылкой на фиг.8.
На этапе 525 декодирующее устройство 415 определяет, следует ли фиксировать принятый запрос. В одном режиме работы это определение осуществляется одновременно с сигнализацией блока БРКСТ 418 на этапе 515. Определение, следует ли фиксировать транзакцию, базируется на сигнале разблокирования регистрации входящего запроса, принятого с БРКСТ 418. Как более подробно описано ниже, БРКСТ 418 отвечает за разблокирование и блокирование регистрации и в очереди исходящих запросов 420, и в очереди входящих запросов 430.
На фиг.7 показана диаграмма состояний, которой следует БРКСТ 418 при определении, разблокирована ли или блокирована регистрация в очереди исходящих запросов в одном варианте осуществления настоящего изобретения. Как показано на фиг.7, регистрация исходящего запроса либо разблокирована, либо блокирована. В одном варианте исходящего запроса блокируется всякий раз, когда с шины ввода-вывода 402 принимается запрос, который имеет требования упорядочивания. В одном варианте осуществления транзакции считывания заранее определяются таким образом, чтобы имели требования упорядочения. Например, если с шины ввода-вывода 402 был принят запрос на считывание, то выходная регистрация будет блокирована с целью обеспечения поддержания упорядочения транзакций.
При блокировании исходящей регистрации БРКСТ 418 запускает работу таймера. Выходная регистрация остается блокированной, пока запущенный блоком БКРСТ 418 таймер завершит счет или достигнет цели запрос, которым запущен таймер. В одном варианте осуществления настоящего изобретения схема разрешения конфликтов шины ввода-вывода содержит таймер, который устанавливается при повторной передаче запроса. Схема разрешения конфликтных ситуаций не позволяет выдавать никакие запросы повторно передаваемым исполнительным устройством до тех пор, пока не закончит счет этот таймер. Таймер в блоке БРКСТ 418 можно программировать и устанавливать в соответствии с этим таймером схемы разрешения конфликтных ситуаций, таймер в блоке БРКСТ 418 устанавливается на завершение счета сразу же после завершения счета таймера в схеме разрешения конфликтных ситуаций шины ввода-вывода. Блок БРКСТ 418 не фиксирует поступающие с шины ввода-вывода 402 запросы, которые поступают, когда приводится в действие ее таймер, вызывая тем самым повторную передачу этих запросов целевой схемой управления шины ввода-вывода 445, как более подробно описывается ниже.
Следует отметить, что этот способ предполагает хорошую работу схемы разрешения конфликтных ситуаций шины ввода-вывода. То есть способ предполагает, что, когда заканчивает счет таймер схемы разрешения конфликтных ситуаций шины ввода-вывода, схема разрешения конфликтных ситуаций позволяет повторно передаваемому исполнительному устройству повторно передавать запрос. Таким образом, если исполнительное устройство повторно передает запрос, когда исходящая регистрация остается блокированной (потому что запрос принимается с шины ввода-вывода 402 с требованиями упорядочения) и осуществляется попытка завершения запроса. Если попытка успешная, то исходящая регистрация разблокируется; если попытка оказалась безуспешной, то запрос передается повторно и блок БРКСТ 418 снова запускает таймер. Однако, если исполнительное устройство повторно не передает запрос через короткое время после истечения времени работы схемы разрешения конфликтных ситуаций шины ввода-вывода, то блок БРКСТ 418 предполагает, что исполнительное устройство не осуществляет повторную передачу запроса (например, исполнительному устройству больше не нужно выполнять запрос).
Таким образом, можно видеть, что использование таймера позволяет блокировать исходящую регистрацию в ответ на конкретный запрос на шине ввода-вывода 402. Это блокирование дает блоку БРКСТ 418 благоприятную возможность удовлетворить требования упорядочения транзакций и предотвращения взаимоблокирования в отношении запросов, как более подробно описывается ниже со ссылкой на фиг.9. Если запрос возвращается, то может быть осуществлена новая попытка. Если запрос не возвращается, то блок БРКСТ 418 вновь разблокирует исходящую регистрацию.
Возвращаясь к фиг.5а, отметим, что если БРКСТ 418 показывает, что регистрация разблокирована, то декодирующее устройство 415 фиксирует транзакцию, если она представляет собой регистрируемый или допускающий задержку запрос. То есть, на этапе 530 декодирующее устройство 415 возвращает ответ инициирующему исполнительному устройству на процессорной шине 401, что будет сделана попытка запроса на шине ввода-вывода 402. Затем на этапе 535 декодирующее устройство 415 размещает запрос в очередь исходящих запросов 420.
Дополнительно к размещению запроса в очереди 420 декодирующее устройство 415 на этапе 535 посылает также сигнал задержания исходящей регистрации на блок БРКСТ 418. Сигнал задержания исходящей регистрации показывает блоку БРКСТ 418, что зарегистрированная (или задержанная) транзакция оказывается в очереди исходящих запросов 420. БРКСТ 418 использует этот сигнал, если он принимает запрос с шины ввода-вывода 402, который требует выключения из работы очереди исходящих запросов, как более подробно описано ниже.
Транзакции, размещенные в очереди исходящих запросов 420, на этапе 540 проходят на верх очереди. Когда зафиксированная транзакция находится на верху очереди, на этапе 545 запрос изымается и делается попытка передачи на шине ввода-вывода 402 через управляющую программу шины ввода-вывод 425 и интерфейс шины ввода-вывода 450. Организующая программа шины ввода-вывода 425 пытается передать запрос по шине ввода-вывода 402 посредством запрашивания разрешения от БРКСТ 418. Поскольку транзакция была зарегистрирована на этапе 525, должны удовлетворяться требования к БРКСТ 418 выдать разрешение (и перейти в состояние приоритета процессорной шины) и, следовательно, разрешение будет выдано. Эти требования более подробно будут описаны со ссылкой на фиг. 9. При приеме ответа от целевого исполнительного устройства на шине ввода-вывода 402 управляющая (организующая) программа шины ввода-вывода 425 помещает ответ в очередь входящих запросов 430 через формирователь задержанного ответа 440, если транзакция была задержана.
В случае незадержанной транзакции мостовая схема 400 уже зафиксировала (в этапе 530) транзакцию и ответная информация уже возвратилась инициирующему исполнительному устройству на процессорной шине 401. Таким образом, если производится повторная передача транзакции с целевого исполнительного устройства на шине ввода-вывода 402, управляющая программа шины ввода-вывода 425 продолжает пытаться осуществлять транзакцию, пока не будет получен ответ об успешном завершении.
Возвращаясь к этапу 525, отметим, что если сигнал разблокированной исходящей регистрации, принятый с блока БРКСТ 418, показывает, что регистрация блокирования или запрос является нерегистрируемым или не допускающим задержки запросом, то на этапе 550 декодирующее устройство 415 размещает запрос в очереди исходящих запросов 420. Если регистрация не разблокирована, то мостовая схема 400 не фиксирует транзакцию; интерфейс шины 410 скорее останавливает этап ответа процессорной шины 401 до тех пор, пока запрос не сможет попытаться выполниться на шине ввода-вывода 402 и ответ вернется инициализирующему исполнительному устройству.
Запрос, размещенный в очереди 420, переходит на этапе 555 на верх очереди. Управляющая программа шины ввода-вывода 425 изымает запрос из верхней части очереди 420 и пытается выполнить запрос на шине ввода-вывода 402. Способна ли управляющая программа шины ввода-вывода 425 выполнить запрос на шине ввода-вывода 402, зависит от двух факторов: во-первых, удовлетворяются ли требования упорядочения (этап 558) и, во-вторых, дает ли блок БРКСТ 418 разрешение организующей программе шины ввода-вывода 425 обслужить запрос (этап 560). В случае первого фактора организующая программа шины ввода-вывода 425 определяет на этапе 558, удовлетворяются ли требования упорядочения. В одном варианте осуществления это определяется сигналом, принимаемым с блока БРКСТ 418, показывающим, что входящая регистрация блокируется. Если требования упорядочивания не удовлетворяются, то на этапе 575 фиг.5В дается запрос на повторный ответ, как более подробно описано ниже.
Если требования упорядочения удовлетворяются, то исполнение запроса зависит от того, дает ли на этапе 560 блок БРКСТ 418 организующей программе шины ввода-вывода 425 разрешение обслужить запрос в ответ на требование разрешения управляющей программе шины ввода-вывода 425. В одном варианте осуществления управляющая программа шины ввода-вывода 425 может осуществлять три различных запроса на разрешение, включающих, является ли запрос не задержанным запросом на считывание, задержанным запросом или не зарегистрированным запросом на запись. Следует отметить, что управляющая программа шины ввода-вывода 425 отменяет этот сигнал, когда либо сделана попытка обслуживания запроса на шине ввода-вывода 402, либо от блока БРКСТ 418 получено неразрешение.
На фиг.9 показана диаграмма состояний блока БРКСТ 418, используемая при определении, дает ли управляющая программа шины 425 разрешение или неразрешение на обслуживание запроса. Если БРКСТ 418 находится в состоянии ожидания, то БРКСТ 418 переходит к попытке усилить приоритет процессорной шины 401, как более подробно описано ниже. Если БРКСТ 418 находится в состоянии приоритета шины ввода-вывода, то БРКСТ 418 выдает неразрешение на все запросы от процессорной шины 401. Однако, если БРКСТ 418 находится в состоянии приоритета процессорной шины, то БРКСТ 418 выдаст разрешение на запрос.
Чтобы дать разрешение управляющей программе шины 425, БРКСТ 418 должен перейти из состояния ожидания в состояние приоритета процессорной шины. Чтобы сделать этот переход, должны удовлетворяться четыре условия: 1) должны удовлетворяться требования упорядочения; 2) должен удовлетворяться критерий избежания взаимоблокировки; 3) должен иметься в наличии буфер входящих данных; 4) БРКСТ 418 должен иметь возможность монопольного использования шины ввода-вывода 402. Если БРКСТ 418 способен перейти к состоянию приоритета процессорной шины, то он выдает разрешение организующей программе шины 425; в противном случае он выдает неразрешение.
Во-первых, должны удовлетворяться требования упорядочения транзакций. В одном варианте осуществления настоящего изобретения требования упорядочения транзакций выполняются в том случае, если блокирована входящая регистрация, как описано ниже.
Во-вторых, должен удовлетворяться критерий избежания взаимоблокировки. В одном варианте осуществления настоящего изобретения критерий избежания взаимоблокировки удовлетворяется посредством "выключения из работы" очереди входящих запросов. То есть, БРКСТ 418 определяет, что в очереди входящих запросов 430 отсутствуют зарегистрированные транзакции. БРКСТ 418 осуществляет это определение на основе сигнала задержания входящей регистрации, принимаемого с целевой схемы управления шины ввода-вывода 445, когда транзакция регистрируется во входящей очереди. Целевая схема управления шины ввода-вывода 445 утверждает сигнал задержания входящей регистрации столько времени, пока устанавливается двоичный разряд достоверности по меньшей мере одного участка очереди входящих запросов 430; когда все двоичные разряды достоверности устанавливаются в исходное состояние (благодаря наличию удаленных запросов в очереди входящих запросов 430), целевая схема управления шины ввода-вывода 445 отменяет сигнал задержания входящей регистрации. Чтобы удовлетворить критерий избежания взаимоблокировки, сигнал задержания входящей регистрации должен быть отменен.
В-третьих, если необходимо, то должен быть в наличии буфер входящих данных. Некоторые транзакции требуют использования буфера входящих данных. Если запрос, который пытается обслужить организующая программа шины 425, требует буфера входящих данных, то БРКСТ 418 не выдает разрешения организующей программе шины 425, пока не окажется в наличии буфер. Выдача разрешения без наличия буфера приводит к отсутствию ячейки в памяти, в которой можно разместить связанные с запросом данные. Организующая программа шины 425 информирует блок БРКСТ 418, что запрос требует буфера данных посредством утверждения сигнала на БРКСТ 418, когда он запрашивает разрешение на обслуживание запроса на этапе 560. В одном варианте осуществления настоящего изобретения БРКСТ 418 запрашивает буфер входящих данных у блока распределения 435, когда запрос требует буфер входящих данных, и блок распределения 435 возвращает сигнал либо разрешения, либо неразрешения в блок БРКСТ 418, указывая на наличие или отсутствие буфера соответственно. В одном варианте осуществления блок распределения 435 показывает также идентичность (например, адрес) буфера данных для БРКСТ 418, который можно использовать при подаче сигнала разрешения на блок БРКСТ 418.
В-четвертых, БРКСТ 418 должен иметь право монопольного пользования шиной ввода-вывода 402. В этом варианте осуществления настоящего изобретения БРКСТ 418 разрешает конфликтную ситуацию в отношении доступа к шине ввода-вывода 402. В одном варианте осуществления БРКСТ 418 разрешает конфликтную ситуацию в отношении доступа к шине ввода-вывода 402 через блок разрешения конфликтных ситуаций 451 интерфейса шины ввода-вывода 450. Если вышеперечисленные три условия удовлетворяются, то когда БРКСТ 418 получает право монопольного пользования шиной ввода-вывода 402 от устройства разрешения конфликтных ситуаций шины ввода-вывода, может быть выдано разрешение. Благодаря ожиданию получения права монопольного пользования шиной ввода-вывода 402, БРКСТ 418 гарантирует, что организующая программа шины 425 может сразу же выполнить запрос на шине ввода-вывода 402 при выдаче блоком БРКСТ 418 разрешения.
В одном варианте осуществления настоящего изобретения БРКСТ 418 разрешает конфликтную ситуацию в отношении доступа к шине ввода-вывода 402 только в том случае, если удовлетворяются вышеперечисленные три условия. Таким образом, БРКСТ 418 не препятствует другим исполнительным устройствам, подсоединенным к шине ввода-вывода 402, в получении права на монопольное пользование шиной ввода-вывода 402, если только организующая программа шины 425 не выдержит транзакцию, которая готова для выполнения на шине ввода-вывода 402.
При удовлетворении этих четырех условий БРКСТ 418 переходит от состояния ожидания к состоянию приоритета процессорной шины. Во время нахождения в состоянии приоритета процессорной шины БРКСТ 418 выдает сигнал разрешения организующей программе шины 425 и возвращения в состояние ожидания или переходит к состоянию удержания. В состоянии ожидания БРКСТ 418 переходит тогда, когда организующая программа шины 425 отменяет свой запрос на разрешение. В качестве альтернативы БРКСТ 418 может перейти в состояние удержания, как более подробно описывается ниже.
В одном варианте осуществления настоящего изобретения организующая программа шины 425 может также выдавать сигнал на БРКСТ 418 с целью запроса внутренних ресурсов, например, буферов входящих данных, не требуя монопольного пользования шиной ввода-вывода 402. Это можно осуществлять, например, в том случае, когда организующая программа шины ввода-вывода 425 ожидает получения буфера входящих данных или проверяет его наличие, но не сразу же выполняет транзакцию на шине ввода-вывода 402.
В одном варианте осуществления настоящего изобретения очередь входящих запросов 430 при некоторых обстоятельствах не должна выключаться из работы. Например, один запрос, который может быть принят с процессорной шины 401, представляет собой считывание кадрового буфера (то есть, считывание видеографических областей). Программно-реализованные алгоритмы, использующие модель поставщика-потребителя, обычно не запоминают данные в графических областях, поэтому описанные выше возможности упорядочения обычно не представляют проблему. В этом варианте осуществления организующая программа шины 425 выдает сигнал на БРКСТ 418 при требовании разрешения, показывающего, что этот запрос представляет собой считывание кадрового буфера. Этот сигнал информирует БРКСТ 418, что не нужно выключать из работы очередь входящих запросов 430, поэтому, если остальные три критерия удовлетворяются, БРКСТ 418 может выдать разрешение, даже если в очереди входящих запросов 430 задерживаются зарегистрированные транзакции.
В одном варианте осуществления настоящего изобретения БРКСТ 418 может также переходить в состояние удержания из состояния приоритета процессорной шины. Находясь в состоянии удержания, БРКСТ 418 выдает сигнал неразрешения на запросы, принимаемые с шины ввода-вывода 402. При некоторых обстоятельствах для состояния удержания может потребоваться транзакция, например, в одном варианте осуществления настоящего изобретения, если запрос снимается с шины ввода-вывода 402 до его завершения, запрашивающее исполнительное устройство (то есть мостовая схема в этом примере) должно отпустить свой сигнал запроса шины в течение двух тактовых импульсов, а затем попытаться возобновить или повторно выполнить транзакцию. Таким образом, если организующая программа шины 425 принимает разрешение с БРКСТ 418 и начинает исполнять запрос на шине ввода-вывода 402, мостовая схема 400 может внезапно отсоединиться. Например, это может произойти в том случае, если целевое исполнительное устройство на шине ввода-вывода 402 не может передать такое большое количество данных, как инициирующее исполнительное устройство на процессорной шине 401 (например, пытаясь передать 32-байтовую строку данных на исполнительное устройство только с одним 4-байтовым буфером данных). При этих обстоятельствах желательно поддерживать приоритет мостовой схемой, поэтому другим запросам нельзя дать разрешение при нахождении в состоянии удержания. БРКСТ 418 переходит из состояния удержания в состояние ожидания (в ответ на сигнал запроса удержания, утвержденный организующей программой шины 425). Однако вследствие того, что приоритет поддерживала мостовая схема, БРКСТ 418 должен иметь возможность сразу же снова перейти в состояние приоритета процессорной шины.
Обращаясь к фиг. 5а, отметим, что если БРКСТ 418 дает организующей программе шины 425 разрешение, то организующая программа шины 425 на этапе 565 обслуживает запрос. Запрос исполняется на шине ввода-вывода 402 через интерфейс шины 450 (напомним, что БРКСТ 418 уже разрешил конфликтную ситуацию и получил доступ к шине ввода-вывода 402). Организующая программа шины 425 получает ответ от целевого исполнительного устройства на шине ввода-вывода 402, который возвращается к инициирующему устройству на процессорной шине 401 через интерфейс шины 410. Ответ возвращается не через очередь входящих запросов 430, потому что мостовая схема 400 останавливает процессорную шину 401, ожидающую этот ответ.
Возвращаясь к этапу 560, отметим, что если БРКСТ 418 дает управляющей программе шины 425 неразрешение, то организующая программа шины 425 определяет на этапе 570, является ли запрос частью операции блокирования. Операция блокирования представляет собой операцию на шине, которая должна оставаться неделимой; операция обычно включает транзакцию считывания и транзакцию записи, одна или обе из которых могут проходить через мостовую схему 400. В одном варианте осуществления настоящего изобретения исполнительное устройство на процессорной шине 401, которое выдает транзакцию блокировки, выдает сигнал блокировки вместе с транзакцией, которую принимает мостовая схема 400 через интерфейс 410. Таким образом, мостовая схема 400 и, следовательно, организующая программа шины 425 знает, что транзакция является транзакцией блокировки. В одном варианте осуществления настоящего изобретения независимо от того, является ли транзакция частью транзакции блокировки, запоминается в области признака, связанной с транзакцией очереди входящих запросов 420.
Если запрос является частью операции блокировки, то организующая программа шины 425 знает, что запрос должен быть завершен. Неспособность принять разрешение на обслуживание запроса от БРКСТ 418 показывает, что транзакция была размещена в очередь входящих запросов 430 после приема этого запроса блокировки мостовой схемой 400, но до прохождения запроса блокировки на верх очереди исходящих запросов 420. Когда запрос во входящей очереди 430 проходит на верх очереди 430, процессорный конечный автомат 417 наблюдает, что транзакция блокировки находится в процессе обработки на процессорной шине 401 и выдает повторную передачу на запрос, как более подробно описано ниже. Таким образом, что касается запроса, который является частью операции блокировки, то организующая программа шины 425 знает, что в конечном счете она примет разрешение от БРКСТ 418. Следовательно, организующая программа шины 425 продолжает запрашивать разрешение у БРКСТ 418 до тех пор, пока не будет получено разрешение, как показано повторяющимися этапами 560 и 570.
Если запрос на верху очереди исходящих запросов 420 не является частью операции блокирования, то на этапе 575 фиг. 5в дается запрос на повторную передачу ответа. Эта повторная передача ответа возвращается инициирующему исполнительному устройству сразу же, когда начинается остановка этапа ответа процессорной шине 401.
Дополнительно к выдаче повторной передачи БРКСТ 418 определяет на этапе 580, является ли эта повторная передача второй последующей повторной передачей ответа для этого процессора. В одном варианте осуществления настоящего изобретения эта информация запоминается в регистре повторной передачи 424, который включает в себя идентификатор исполнительного устройства, и передавался ли повторно раньше этот идентификатор. Этот регистр устанавливается в исходное состояние, когда последующая транзакция запрашивает разрешение от БРКСТ 418. Если это вторая последующая повторная передача, то БРКСТ 418 предполагает, что это происходит вследствие того, что запрос сохраняется после повторной передачи из-за того, что транзакции, размещенные в очереди входящих запросов 430, получают приоритет, чтобы предотвратить зависание исполнительного устройства на процессорной шине 401, БРКСТ 418 на этапе 585 маскирует запросы с шины ввода-вывода 402. То есть даются запросы ввода-вывода на повторную передачу ответов до тех пор, пока этому исходящему запросу дается приоритет (или последующий запрос принимается с другого процессора). Таким образом, следующему запросу этим процессором должен отдаваться приоритет. Следует отметить, что это маскирование запросов из шины ввода-вывода 402 позволяет этому исполнительному устройству осуществлять доступ к шине ввода-вывода 402; однако нет гарантии того, что целевое исполнительное устройство на шине ввода-вывода 402 не дает повторного ответа на запрос. Должно быть ясно, что маскировка запросов от шины ввода-вывода 402, как показано на этапах 580 и 585, не является необходимым для работы в соответствии с настоящим изобретением. То есть в одном варианте осуществления после выдачи запроса на повторную передачу ответа на этапе 575 БРКСТ 418 пытается усилить приоритет для процессорной шины 401 на описываемом ниже этапе 590.
Независимо от того, маскируются ли запросы на шине ввода-вывода 402, на этапе 590 БРКСТ 418 пытается усилить приоритет для процессорной шины 401. Эта попытка усилить приоритет производится так, как описано выше со ссылкой на фиг.9. БРКСТ 418 пытается удовлетворить эти условия, чтобы, когда запрос передается повторно и переходит снова на верх очереди исходящих запросов 420, можно было выдать разрешение на обслуживание запроса. Однако следует отметить, что БРКСТ 418 не разрешает конфликтной ситуации в отношении доступа к шине ввода-вывода 402 до тех пор, пока организующая программа шины 425 снова потребует разрешение на обслуживание запроса.
Исполнительное устройство, которое разместило запрос на процессорной шине 401, в соответствии с этапом 505 на фиг. 5а снова делает попытку запроса. Вышеуказанные этапы повторяются либо при обслуживании запроса на шине ввода-вывода 402, либо при повторной передаче.
Транзакции, инициирующиеся на шине ввода-вывода
На фиг. 6а и 6в представлена блок-схема этапов, выполняемых при манипулировании запросом, принятым мостовой схемой 400 с шины ввода-вывода 402 в одном варианте осуществления настоящего изобретения. На этапе 605 запрос принимает мостовая схема 400 от инициирующего исполнительного устройства на шине ввода-вывода 402. Следует отметить, что хотя запрос принимается от инициирующего исполнительного устройства на шине ввода-вывода 402, это исполнительное устройство может не инициировать запрос. Например, запрос может инициировать исполнительное устройство, подсоединенное к показанной на фиг.2 шине ввода-вывода 246, которая указывает действие исполнительному устройству на шине процессоров и запоминающих устройств 201. Этот запрос создается на системной шине ввода-вывода 231 с мостовой схемой 245 и принимается мостовой схемой 224. Таким образом, хотя запрос порождается на шине 231 с мостовой схемой 245, мостовая схема 245 не инициирует запрос.
Обращаясь к фиг. 6а, отметим, что при приеме запроса с шины ввода-вывода 402, БРКСТ 418 определяет на этапе 607, маскируются ли запросы ввода-вывода. Как описано выше, запросы ввода-вывода будут маскироваться в том случае, если исполнительное устройство на процессорной шине 401 приняло два последовательно повторяемых ответа. Если запросы ввода-вывода маскируются, то на этапе 608 БРКСТ 418 выдает повторную передачу ответа на этот запрос. Эта повторная передача показывает инициирующему исполнительному устройству, что оно снова должно позже выдавать запрос.
Если запрос ввода-вывода не маскируется, то на этапе 610 мостовая схема 400 определяет, является ли запрос запросом на считывание. В другом варианте осуществления настоящего изобретения мостовая схема 400 определяет, имеет ли принятый запрос требования упорядочения транзакций на основании принятой команды (декодируемой посредством схемы декодирования команд 452). Если команда согласует набор заранее определенных команд с требованиями упорядочения транзакций, то мостовая схема 400 знает, что этот запрос имеет требования упорядочения.
Если запрос не является запросом считывания, то на описанном выше этапе 615 целевое устройство управления шины ввода-вывода 445 определяет, необходимо ли регистрировать запрос. Если запрос является запросом считывания, то на этапе 612 целевое управляющее устройство 445 посылает сигнал на БРКСТ 418, показывающий, что исходящее регистрирование будет блокировано. Блокирование исходящего регистрирования описано выше со ссылкой на фиг.7.
Целевое устройство управления шины ввода-вывода 445 затем на этапе 615 определяет, следует ли регистрировать принятый запрос. В одном варианте осуществления можно регистрировать только некоторые заранее определенные запросы (например, запросы на запись). В одном варианте осуществления настоящего изобретения на этапе 612 выполняется определение, следует ли регистрировать запрос одновременно с сигнализацией блока БРКСТ 418. Это определение выполняется на основании того, разблокируется ли или блокируется входящая регистрация и имеется ли в наличии участок входящей очереди, полагая, что запрос является регистрируемым запросом. Как описано выше, сигнал, показывающий, имеется ли в наличии участок входящей очереди, принимается с блока распределения входящей очереди 435. Если входящая регистрация блокируется или отсутствует участок входящей очереди, или запрос является нерегистрируемым запросом, то на этапе 640 фиг. 6в целевое устройство управления шины ввода-вывода 445 определяет, удовлетворяются ли требования упорядочения, как описано более подробно ниже.
Однако, если входящая регистрация разблокирована и имеется участок входящей очереди, то на этапе 620 ответ регистрируется и размещается в очереди входящих запросов 430. После регистрации инициирующее исполнительное устройство информируется о том, что будет осуществлена попытка обслуживания запроса на процессорной шине 401 (то есть мостовая схема 400 фиксирует запрос); таким образом, инициирующее исполнительное устройство может освобождать шину ввода-вывода 402, не ожидая ответа от целевого исполнительного устройства на процессорной шине 401. Входящая регистрация либо разблокируется, либо блокируется на основании сигнала разблокированной входящей регистрации, поступающего на целевое управляющее устройство шины ввода-вывода 445 с БРКСТ 418.
На фиг. 8 показана диаграмма состояний, которой следует блок БРКСТ 418 при определении, следует ли разблокировать или блокировать регистрацию в очереди входящих запросов 430 в одном варианте осуществления настоящего изобретения. Как показано на фиг.8, входящая регистрация либо разблокируется, либо блокируется. В одном варианте осуществления настоящего изобретения входящая регистрация блокируется всякий раз, когда с процессорной шины 401 поступает запрос на считывание. Когда входящая регистрация блокируется, БРКСТ 418 запускает работу таймера.
После блокирования входящая регистрация остается блокированной до тех пор, пока либо таймер, установленный блоком БРКСТ 418, завершит счет, либо достигнет цели запрос на считывание, вызывающий блокирование входящей регистрации. Когда декодирующее устройство 415 принимает запрос, оно принимает также информацию исполнительного устройства, которое выдает запрос. Таким образом, декодирующее устройство 415 знает, когда созданный запрос на считывание возвращает блокирование (и оно может отметить свой сигнал, которым будет блокирована входящая регистрация, предполагая, что в очередь исходящих запросов 420 не поступят другие транзакции, которые требуют от декодирующего устройства показать, что входящая регистрация будет блокирована).
Блок БРКСТ 418 содержит таймер, аналогичный таймеру, описанному выше со ссылкой на фиг. 7 и блокирующему входящую регистрацию. Этот таймер в БРКСТ 418 базируется на алгоритме разрешения конфликтных ситуаций процессорной шины 401. В одном варианте осуществления настоящего изобретения алгоритм разрешения конфликтных ситуаций на процессорной шине 401 следует методу циклического обслуживания. Таким образом можно определить максимальное количество времени, которое должно пройти, прежде чем процессор может повторить запрос. Устанавливая таймер БРКСТ 418 на эту максимальную величину времени, БРКСТ 418 гарантирует, что входящая регистрация не блокируется до тех пор, пока повторяющее исполнительное устройство не получит благоприятную возможность повторить запрос.
При определенных обстоятельствах исполнительное устройство, которое вызвало блокирование, может повторить запрос до завершения счета таймера в БРКСТ 418. В этой ситуации входящая регистрация остается блокированной, пока запрос не достигнет цели. Если запрос передается повторно, то таймер восстанавливается в исходное состояние и запускается снова. Если запрос достигает цели, то блокирование очереди входящих запросов больше не требуется и разблокируется входящая регистрация.
Возвращаясь к фиг. 6а, отметим, что на этапе 620 целевое управляющее устройство 445 регистрирует запрос, если это возможно, и разрешает запрос в очереди входящих запросов 430. Как и в случае очереди исходящих запросов, на этапе 630 транзакции в очереди входящих запросов перемещаются на верх очереди. На этапе 635 конечный автомат процессоров 417 изымает запрос из верхней части очереди входящих запросов и исполняет его.
В одном варианте осуществления настоящего изобретения исполнение запроса на процессорной шине 401 приводит к одному из двух возможных ответов. Во-первых, с целевого исполнительного устройства на процессорной шине 401 может вернуться ответ успешного завершения. В этой ситуации транзакция завершается, когда зарегистрированный ответ от этапа 620 показывает инициирующему исполнительному устройству на шине ввода-вывода 402, что транзакция будет завершена. Второй возможной реакцией является повторная передача ответа. В этой ситуации исполнительное устройство адресата на процессорной шине 401 выдает повторную передачу запроса, показывающую, что оно не готово к обслуживанию запроса и поэтому его необходимо передать повторно. Мостовая схема 400 принимает этот повторно передаваемый ответ и продолжает повторять запрос до тех пор, пока не будет получен ответ успешного завершения.
Возвращаясь к этапу 615 фиг. 6а, отметим, что если запрос не регистрируется, то на этапе 640 фиг. 6в целевое управляющее устройство 445 определяет, удовлетворяются ли требования упорядочения в отношении запроса. В этом варианте осуществления это определяется сигналом, принятым с блока БРКСТ 418, показывающим, что исходящая регистрация блокируется. Если требования упорядочения не удовлетворяются, то подается запрос на повторную передачу ответа, как описано ниже на этапе 665.
Однако, если требования упорядочивания удовлетворяются, то целевое управляющее устройство шины ввода-вывода 445 определяет на этапе 645, принято ли с блока БРКСТ 418 разрешение или неразрешение в ответ на запрос разрешения с целевого управляющего устройства шины ввода-вывода 445. Выдает ли блок БРКСТ 418 разрешение, более подробно описывается ниже со ссылкой на фиг.9. В одном варианте осуществления, выдача блоку БРКСТ 418 целевым исполнительным устройством 445 запроса разрешения показывает, что запрос является нерегистрируемым запросом. Целевое управляющее устройство шины ввода-вывода 445 освобождает свой запрос на разрешение, когда либо с БРКСТ 418 поступает сигнал неразрешения, либо завершается запрос. Если в очереди входящих запросов 430 имеется участок и принят сигнал разрешения, то на этапе 650 целевое управляющее устройство 445 размещает запрос в очереди входящих запросов 430. Затем на этапе 655 запрос перемещается на верх очереди входящих запросов 430. На этапе 660 конечный автомат процессора 417 отыскивает запросы в верхней части очереди входящих запросов и пытается выполнить их. При попытке выполнить запрос на процессорной шине 401 процессорный конечный автомат 417 определяет на этапе 662, имеется ли процессорная шина 401. Если шина имеется, то на этапе 663 процессорный конечный автомат 417 выполняет транзакцию на процессорной шине 401.
После выполнения на процессорной шине 401 запроса мог быть принят повторный ответ с целевого исполнительного устройства или ответ об успешном выполнении. Этот ответ возвращается инициирующему исполнительному устройству на шине ввода-вывода 402, которое ожидает ответ (то есть инициирующее исполнительное устройство на шине ввода-вывода 402 предотвращает выдачу другими исполнительными устройствами на шине ввода-вывода 402 запросов на шине ввода-вывода 402).
Возвращаясь к этапу 662, отметим, что при некоторых обстоятельствах процессорная шина 401 может оказаться недоступной. Например, как описано выше, транзакция могла бы находиться в очереди исходящих запросов 420, которая является частью операции блокировки. В этом случае процессорная шина 401 будет недоступна. Когда процессорная шина 401 недоступна, конечный процессорный автомат 417 на этапе 664 возвращает повторный ответ исполнительному устройству, выдающему запрос. Таким образом, исполнительное устройство должно попытаться снова сделать запрос позже, позволяя тем самым выполнить операцию блокирования.
Возвращаясь к этапу 645, отметим, что если участок отсутствует или принимается сигнал неразрешения, то на этапе 665 запрос повторяется. Если БРКСТ 418 выдает сигнал неразрешения, то на этапе 670 БРКСТ 418 пытается получить приоритет для входящего запроса, как более подробно будет описано ниже. Исполнительное устройство, выдающее запрос, затем позже повторяет запрос на этапе 605 фиг. 6а.
На фиг.9 показана диаграмма состояний блока БРКCT 418, используемая при определении, выдает ли целевое управляющее устройство 445 разрешение или неразрешение для обслуживания запроса. Если БРКСТ 418 находится в состоянии ожидания, то БРКСТ 418 переходит к попытке усилить приоритет для шины ввода-вывода 402, как более подробно описано ниже. Если БРКСТ 418 находится в состоянии приоритета процессорной шины или в состоянии удержания, то БРКСТ 418 выдает неразрешение на запрос с шины ввода-вывода 402. Однако, если БРКСТ 418 находится в состоянии приоритета шины ввода-вывода 402, то БРКСТ 418 выдает разрешение на запрос.
Чтобы дать разрешение целевому управляющему устройству 445, БРКСТ 418 должен перейти из состояния ожидания в состояние приоритета шины ввода-вывода. Для осуществления этого перехода должны удовлетворяться три условия, аналогичные вышеописанным условиям, касающимся перехода от состояния ожидания в состояние приоритета процессорной шины: 1) исходящая регистрация должна быть блокирована; 2) очередь исходящих запросов должна быть выключена из работы; 3) при необходимости должен быть в наличии буфер входящих данных. Отметим, что нет необходимости получать право монопольного пользования шины ввода-вывода 402, потому что запрашивающее исполнительное устройство уже имеет право монопольного использования.
Во-первых, исходящая регистрация должна быть блокирована. Выходящая регистрация блокируется, как описано выше со ссылкой на фиг.7.
Во-вторых, очередь исходящих запросов должна быть выключена из работы, то есть очередь исходящих запросов не содержит никаких зарегистрированных транзакций. БРКСТ 418 делает это определение на основе сигнала задержания исходящей регистрации, получаемого с декодирующего устройства 415, когда транзакция регистрируется в выходящей очереди. В одном варианте осуществления настоящего изобретения декодирующее устройство 415 поддерживает счетчик, содержимое которого получает приращение каждый раз, когда оно регистрирует или откладывает запрос. Организующая программа шины ввода-вывода 425 в этом случае обеспечивает отрицательное приращение содержимого этого счетчика каждый раз, когда она завершает зарегистрированные или задержанные запросы. Таким образом, декодирующее устройство 415 отменяет сигнал задержания исходящей регистрации, когда это содержимое счетчика составляет нуль, и утверждает сигнал задержания исходящей регистрации, когда содержимое этого счетчика имеет положительное значение. Как описано выше, в одном варианте осуществления настоящего изобретения декодирующее устройство 415 и организующая программа шины ввода-вывода 425 работают в двух различных режимах синхронизации; таким образом, сигнал от организующей программы шины ввода-вывода на декодирующее устройство 415, показывающий приращение содержимого счетчика, проходит через блок синхронизации. БРКСТ 418 знает, что исходящая очередь выключается из работы, когда отменяется сигнал задержания исходящей регистрации.
В-третьих, при необходимости должен быть в наличии буфер входящих данных. Некоторые транзакции требуют использования буфера входящих данных. Например, запрос на запись требует буфер входящих данных, потому что он передает данные с шины ввода-вывода 402. Если запрос, который целевое управляющее устройство 445 пытается обслужить, требует буфер входящих данных, то, если буфер отсутствует, БРКСТ 418 не выдает разрешения целевому управляющему устройству 445. Выдача разрешения без наличия буфера приводит к отсутствию ячейки памяти, в которой можно разместить данные, связанные с запросом. Целевое управляющее устройство 445 информирует блок БРКСТ 418, что запрос требует буфер данных посредством утверждения сигнала на БРКСТ 418, когда он запрашивает разрешение на обслуживание запроса на этапе 655. Запрашивание буфера входящих данных блоком БРКСТ 418 осуществляется, как описано выше.
При удовлетворении этих трех условий БРКСТ 418 переходит из состояния ожидания в состояние приоритета шины ввода-вывода. При нахождении в состоянии приоритета шины ввода-вывода блок БРКСТ 418 выдает сигнал разрешения целевому управляющему устройству 445. При завершении запроса (показываемом отменой запроса на разрешение целевым управляющим устройством шины ввода-вывода 445) БРКСТ 418 возвращается в состояние ожидания.
Таким образом, из вышеприведенного описания можно видеть, что мостовая схема передает запросы в оба направления между процессорной шиной 401 и шиной ввода-вывода 402. БРКСТ 418 контролирует деятельность обеих очередей. При разблокировании регистрации в обоих направлениях две очереди работают независимо друг от друга. Когда работа очередей зависит друг от друга, БРКСТ 418 сохраняет упорядочение транзакций и устраняет ситуации взаимоблокировки.
В то время как специалисты в данной области техники после прочтения вышеприведенного описания поймут возможность обеспечения большого количества вариантов и модификаций настоящего изобретения, следует понимать, что конкретные варианты осуществления, показанные и описанные в качестве иллюстрации, ни в коем случае нельзя рассматривать ограничивающими. Следовательно, ссылки на детали конкретных вариантов осуществления не предполагают ограничить объем формулы изобретения, в которой перечисляются только те особенности, которые считаются важными для изобретения.
Таким образом, описаны способ и устройство, предназначенные для поддержания упорядочения транзакций и разрешения конфликтных ситуаций в мостовой схеме шин.
Надписи на чертежах
Фиг. 4
401. Процессорная шина.
402. Шина ввода-вывода.
411. Блок разрешения конфликтных ситуаций.
412. Регистры конфигурации.
413. Логическая схема отображения адресов.
414. Последовательная очередь.
415. Декорирующее устройство исходящих запросов.
417. Процессорный конечный автомат.
420. Очередь исходящих запросов: участок (2), участок (3), ..., участок ().
421. Конечный автомат приоритета.
422. Конечный автомат разблокирования исходящей регистрации.
423. Конечный автомат разблокирования входящей регистрации.
424. Регистр повторной передачи.
425. Организующая программа шины ввода-вывода.
430. Очередь входящих запросов: участок (2), участок (3), ..., участок ().
435. Блок назначения входящей очереди.
440. Формирователь задержанных ответов.
445. Целевое управляющее устройство шины ввода-вывода.
451. Блок разрешения конфликтных ситуаций.
452. Схема декодирования команд.
453. Логическая схема отображения адресов.
418. Блок разрешения конфликтных ситуаций при транзакции (БРКСТ).
410. Интерфейс процессорной шины.
450. Интерфейс шины ввода-вывода.
Фиг. 5а
1. Начало.
2. Да
3. Нет
4. Окончание.
505. Принятие запроса с инициирующего исполнительного устройства, подсоединенного к процессорной шине.
510. Определение, является ли запрос запросом на считывание.
515. Выдача сигнала на блокирование входящей регистрации.
525. Определение, следует ли фиксировать принятый запрос.
530. Возвращение ответа инициирующему исполнительному устройству.
535. Размещение запроса в очереди исходящих запросов. Выдача сигнала задержания исходящей регистрации на блок БРКСТ.
540. Размещение транзакции на верх очереди исходящих запросов.
545. Обслуживание запроса и размещение ответа в очереди входящих запросов.
550. Размещение запроса в очереди исходящих запросов.
555. Расположение транзакции на верх очереди исходящих запросов.
558. Определение, удовлетворяется ли требование упорядочения.
560. Определение, дает ли БРКСТ разрешение на обслуживание запроса.
565. Обслуживание запроса и возвращение ответа инициирующему исполнительному устройству.
570. Определение, является ли запрос частью блокированной транзакции.
Изобретение относится к области передачи данных в вычислительной системе. Технический результат заключается в создании системы, которая предотвращает появление взаимоблокировки в мостовой схеме шин. Мостовая схема шин имеет исходящую и входящую очереди запросов. Запросы, инициирующиеся на первой шине, которые адресованы пункту назначения на второй шине, размещаются в исходящей очереди. Запросы, инициирующиеся на второй шине, которые адресованы пункту назначения на первой шине, размещаются во входящей очереди. Блок разрешения конфликтных ситуаций при транзакциях, находящийся в мостовой схеме, поддерживает упорядочение транзакций и устраняет взаимоблокировки. Он определяет возможность размещения запросов во входящей очереди, ответов на запросы, инициирующихся на первой шине, выполнения запросов в исходящей очереди на второй шине. Данный блок определяет, разблокирована ли регистрация во входящую очередь, существуют ли зарегистрированные транзакции в ней и имеется ли право монопольного использования второй шины. 5 с. и 24 з.п.ф-лы, 11 ил.
| US 5307505 А, 26.04.1994 | |||
| Устройство приоритета | 1990 |
|
SU1741133A1 |
| US 5269005 А, 07.12.1993 | |||
| Устройство для приоритетного обслуживания запросов | 1991 |
|
SU1807485A1 |
