45 Иерархия шин
Если к шине подключено большое число устройств, ее пропускная способность падает, поскольку слишком частая передача прав управления шиной от одного устройства к другому приводит к ощутимым задержкам. По этой причине во многих ВМ предпочтение отдается использованию нескольких шин, образующих определенную иерархию.
Вычислительная машина с одной шиной. В системах соединений с одной шиной имеется одна системная шина, обеспечивающая обмен информацией между всеми устройствами ВМ (рис. 2.76, а).
Рис. 2.76. Система соединений:
а – с одной шиной; б – с двумя видами шин; в – с тремя видами шин
Для такого подхода характерны простота и низкая стоимость. Однако одношинная организация не в состоянии обеспечить высокие интенсивность и скорость транзакций, в силу чего становится «узким местом» ВМ.
Вычислительная машина с двумя видами шин. Хотя контроллеры модулей ввода/вывода (МВВ) могут быть подсоединены непосредственно к системной шине, больший эффект достигается применением одной или нескольких шин ввода/вывода (рис. 7.6, б). МВВ подключаются к шинам ввода/вывода, которые берут на себя основной трафик, не связанный с выходом на процессор или память. Адаптеры шин обеспечивают буферизацию данных при их пересылке между системной шиной и контроллерами МВВ. Это позволяет ВМ поддерживать работу множества модулей ввода/вывода и одновременно «развязать» обмен информацией по тракту процессор-память и обмен информацией с МВВ.
Подобная схема существенно снижает нагрузку на скоростную шину «процессор-память» и способствует повышению общей производительности вычислительной машины.
Вычислительная машина с тремя видами шин. Для подключения быстродействующих периферийных устройств в систему шин может быть добавлена высокоскоростная шина расширения (рис. 7.6, в).
Шины ввода/вывода подключаются к шине расширения, а уже с нее через адаптер к системной шине, что еще более снижает нагрузку на последнюю. Такую организацию шин называют архитектурой с «пристройкой» (mezzanine architecture).
46 Арбитраж шин
В реальных системах на роль ведущего вправе одновременно претендовать сразу несколько из подключенных к шине устройств, однако управлять шиной в каждый момент времени может только одно из них. Чтобы исключить конфликты, шина должна предусматривать определенные механизмы арбитража запросов и правила предоставления шины одному из запросивших устройств. Решение обычно принимается на основе приоритетов претендентов: шина предоставляется устройству с наивысшим приоритетом среди запросивших.
Алгоритмы арбитража. Каждому потенциальному ведущему присваивается определенный уровень приоритета, который может оставаться неизменным (статический или фиксированный приоритет) либо изменяться по какому-либо алгоритму (динамический приоритет). Кроме того, существуют алгоритмы, в которых понятие уровня приоритета не имеет смысла, например, если все устройства имеют одинаковый приоритет.
В системах со статическим приоритетом предполагается, что каждому ведущему изначально присваивается отличный от других уровень приоритета, который в процессе работы остается неизменным. Основной недостаток систем со статическими приоритетами в том, что устройства, имеющие высокий приоритет, в состоянии полностью блокировать доступ к шине устройств с меньшим уровнем приоритета.
Алгоритмы арбитража на основе динамических приоритетов. Системы с динамическими приоритетами дают шанс каждому из запросивших устройств рано или поздно получить право на управление шиной, то есть в таких системах реализуется принцип равнодоступности. Наибольшее распространение получили следующие алгоритмы динамического изменения приоритетов:
простая циклическая смена приоритетов;
циклическая смена приоритетов с учетом последнего запроса;
смена приоритетов по случайному закону;
алгоритм наиболее давнего использования.
В алгоритме простой циклической смены приоритетов каждое устройство имеет уникальный уровень приоритета в диапазоне от минимального до максимального. После каждого цикла арбитража приоритеты всех устройств циклически понижаются на один уровень, при этом устройство, имевшее низший уровень приоритета, получает наивысший приоритет (рис. 2.77).
Рис. 2.77. Пример арбитража по алгоритму простой циклической
смены приоритетов:
а – исходные уровни приоритета;
б, в, г – уровни приоритетов после очередного цикла арбитража
В алгоритме циклической смены приоритетов с учетом последнего запроса (RDC – Rotating Daisy Chain) функции арбитража распределены между всеми устройствами, цепи арбитража которых соединены в кольцо. После обработки очередного запроса обслуженному устройству назначается низший уровень приоритета, и оно становится арбитром для следующего цикла шины. Остальным устройствам назначаются новые приоритеты, в зависимости от их удаленности в кольце от устройства, выполняющего в данный момент роль арбитра: следующее устройство в кольце получает наивысший приоритет, а остальным устройствам приоритеты назначаются в убывающем порядке, согласно их следованию в кольце (рис. 2.78). Хотя оба алгоритма циклической смены приоритетов дают шанс каждому ведущему устройству получить шину в свое распоряжение, большее распространение получил второй алгоритм.
Рис. 2.78. Пример арбитража по алгоритму циклической смены приоритетов
с учетом последнего запроса:
а – исходные уровни приоритета;
б, в, г – уровни приоритетов после очередного цикла арбитража
с учетом запросившего устройства
При смене приоритетов по случайному закону после очередного цикла арбитража с помощью генератора псевдослучайных чисел каждому ведущему присваивается случайное, но отличное от других значение уровня приоритета.
В алгоритме наиболее давнего использования (LRU, Least Recently Used) после каждого цикла арбитража наивысший приоритет присваивается ведущему, дольше других не использовавшему шину.
Алгоритм арбитража на основе фиксированного кванта времени. Согласно данному алгоритму все устройства имеют одинаковый приоритет. Каждому устройству на циклической основе предоставляется квант времени, в течение которого устройство получает право на управление шиной. Если устройство в этот момент не нуждается в шине, выделенный квант времени остается неиспользованным. Такой метод наиболее подходит для шин с синхронным протоколом.
Алгоритм арбитража на основе очереди. В алгоритме очереди (FIFO – First In - First Out) запросы обслуживаются в порядке очереди, образовавшейся к моменту начала цикла арбитража. Сначала обслуживается первый запрос в очереди, то есть запрос, поступивший раньше остальных. Аппаратурная реализация алгоритма связана с определенными сложностями, поэтому используется он редко.
Схемы арбитража. Арбитраж запросов на управление шиной может быть организован по централизованной или децентрализованной схеме. Выбор конкретной схемы зависит от требований к производительности и стоимостных ограничений.
Централизованный арбитраж. При централизованном арбитраже в системе имеется специальное устройство – центральный арбитр, – ответственное за предоставление доступа к шине только одному из запросивших ведущих. Это устройство, называемое иногда центральным контроллером шины, может быть самостоятельным модулем или частью ЦП. Наличие на шине только одного арбитра означает, что в централизованной схеме имеется единственная точка отказа. В зависимости от того, каким образом ведущие устройства подключены к центральному арбитру, возможные схемы централизованного арбитража можно подразделить на параллельные и последовательные.
В параллельном варианте центральный арбитр связан с каждым потенциальным ведущим индивидуальными двухпроводными трактами. Поскольку запросы к центральному арбитру могут поступать независимо и параллельно, данный вид арбитража называют централизованным параллельным арбитражем или централизованным арбитражем независимых запросов.
Схема централизованного параллельного арбитража на примере восьми ведущих устройств показана рис. 2.79.
Рис. 2.79. Централизованный параллельный арбитраж
(ПШ – предоставление шины; ЗШ – запрос шины; ШЗ – шина занята)
Под «текущим ведущим» будем понимать ведущее устройство, управляющее шиной в момент поступления нового запроса. Устройство, выставившее запрос на управление шиной, будем называть «запросившим ведущим». Сигналы запроса шины (ЗШ) поступают на вход центрального арбитра по индивидуальным линиям. Ведущему с номером i, который был выбран арбитром, также по индивидуальной линии возвращается сигнал предоставления шины (ПШi), но реально занять шину новый ведущий сможет лишь после того, как текущий ведущий (пусть он имеет номер j) снимет сигнал занятия шины (ШЗ). Текущий ведущий должен сохранять сигналы ШЗ(занятие шины) и ЗШj (запрос шины), активными в течение всего времени, пока он использует шину. Получив запрос от ведущего, приоритет которого выше, чем у текущего ведущего, арбитр снимает сигнал ПШj на входе текущего ведущего и выдает сигнал предоставления шины ПШi запросившему ведущему. В свою очередь, текущий ведущий, обнаружив, что центральный арбитр убрал с его входа сигнал ПШj, снимает свои сигналы ШЗ и ЗШj, после чего запросивший ведущий может перенять управление шиной. Если в момент пропадания сигнала предоставление шины ПШ на шине происходит передача информации, текущий ведущий сначала завершает передачу и лишь после этого снимает свои сигналы. Логика выбора одного из запрашивающих ведущих обычно реализуется аппаратными средствами.
При большом числе источников запроса центральный арбитр может строиться по схеме двухуровневого параллельного арбитража. Все возможные запросы разбиваются на группы, и каждая группа анализируется своим арбитром первого уровня, который выбирает запрос, имеющий в данной группе наивысший приоритет. Арбитр второго уровня отдает предпочтение тому арбитру первого уровня, у которого выбранный запрос имеет наиболее высокий приоритет. При необходимости могут вводиться дополнительные уровни арбитража.
Схема централизованного параллельного арбитража очень гибка и обладает высоким быстродействием, но в ней затруднено подключение дополнительных устройств. Обычно максимальное число ведущих при параллельном арбитраже не превышает восьми.
Второй вид централизованного арбитража известен как централизованный последовательный арбитраж. В последовательных схемах для выделения запроса с наивысшим приоритетом используется один из сигналов, поочередно проходящий через цепочку ведущих, чем и объясняется другое название – цепочечный или гирляндный арбитраж. В дальнейшем будем полагать, что уровни приоритета ведущих устройств в цепочке понижаются слева направо.
В зависимости от того, какой из сигналов используется для целей арбитража, различают три основных типа схем цепочечного арбитража: с цепочкой для сигнала предоставления шины (ПШ), с цепочкой для сигнала запроса шины (ЗШ) и с цепочкой для дополнительного сигнала разрешения (РШ). Наиболее распространена схема цепочки для сигнала ПШ (рис. 2.80).
Запросы от ведущих объединяются на линии запроса шины по схеме «ИЛИ». Аналогично организована и линия, сигнализирующая о том, что шина в данный момент занята одним из ведущих. Когда один или несколько ведущих выставляют запросы, эти запросы транслируются на вход центрального арбитра. Получив сигнал ЗШ, арбитр анализирует состояние линии занятия шины, и если шина свободна, формирует сигнал предоставления шины. Сигнал ПШ последовательно переходит по цепочке от одного ведущего к другому. Если устройство, на которое поступил сигнал ПШ, не запрашивало шину, оно просто пропускает сигнал дальше по цепочке. Когда ПШ достигнет самого левого из запросивших ведущих, последний блокирует дальнейшее распространение сигнала по цепочке и берет на себя управление шиной.
Рис. 2.80. Централизованный последовательный арбитраж с цепочкой для сигнала предоставления шины
Еще раз отметим, что очередной ведущий не может приступить к управлению шиной до момента ее освобождения. Центральный арбитр не должен формировать сигнал ПШ вплоть до этого момента.
Цепочечная реализация предполагает статическое распределение приоритетов. Наивысший приоритет имеет ближайшее к арбитру ведущее устройство. Далее приоритеты ведущих в цепочке последовательно понижаются.
Основное достоинство цепочечного арбитража – простота реализации и малое количество используемых линий. Последовательные схемы арбитража позволяют легко наращивать число устройств, подключаемых к шине. Схема, однако, обладает и существенными недостатками. Прежде всего, последовательное прохождение сигнала по цепочке замедляет арбитраж, причем время арбитража растет пропорционально длине цепочки. Кроме того, статическое распределение приоритетов может привести к полному блокированию устройств с низким уровнем приоритета, расположенных ближе к концу цепочки.
Децентрализованный арбитраж. При децентрализованном или распределенном арбитраже единый арбитр отсутствует. Вместо этого каждый ведущий содержит блок управления доступом к шине (контроллер шины), и при совместном использовании шины такие блоки взаимодействуют друг с другом, разделяя между собой ответственность за доступ к шине.
Идею децентрализованного арбитража иллюстрирует рис. 2.81. Каждый ведущий имеет уникальный уровень приоритета и обладает собственным контроллером шины, способным формировать сигналы предоставления и занятия шины. Сигналы запроса от любого ведущего поступают на входы всех остальных ведущих. Логика арбитража реализуется в контроллере шины каждого ведущего.
Для большинства шин все-таки более характерна другая организация децентрализованного арбитража. Такие схемы предполагают наличие в составе шины группы арбитражных линий, организованных по схеме «ИЛИ». Это позволяет любому ведущему видеть сигналы, выставленные остальными устройствами. Каждому ведущему присваивается уникальный номер, совпадающий с кодом уровня приоритета данного ведущего. Запрашивающие шину устройства выдают на арбитражные линии свой номер. Каждый из запросивших ведущих, обнаружив на арбитражных линиях номер устройства с более высоким приоритетом, снимает с этих линий младшие биты своего номера. В конце концов, на арбитражных линиях остается только номер устройства, обладающего наиболее высоким приоритетом. Победителем в процедуре арбитража становится ведущий, опознавший на арбитражных линиях свой номер. Подобная схема известна также как распределенный арбитраж с самостоятельным выбором, поскольку ведущий сам определяет, стал ли он победителем в арбитраже, то есть выбирает себя самостоятельно.
Рис. 2.81. Децентрализованный арбитраж
В целом схемы децентрализованного арбитража потенциально более надежны, поскольку отказ контроллера шины в одном из ведущих не нарушает работу с шиной других, подключенных к ней устройств. Тем не менее, должны быть предусмотрены средства для обнаружения неисправных контроллеров, например, на основе тайм-аута. Основной недостаток децентрализованных схем – в относительной сложности логики арбитража, которая должна быть реализована в аппаратуре каждого ведущего.
В некоторых ВМ применяют комбинированные последовательно-параллельные схемы арбитража, в какой-то мере сочетающие достоинства обоих методов. Здесь все ведущие разбиваются на группы. Арбитраж внутри группы ведется по последовательной схеме, а между группами – по параллельной.
Ограничение времени управления шиной. Одним из вариантов стратегии ограничения времени контроля над шиной может быть разрешение ведущему занимать шину в течение одного цикла шины, с предоставлением ему возможности конкуренции за шину в последующих циклах. Другим вариантом является принудительный захват контроля над шиной устройством с более высоким уровнем приоритета, при сохранении восприимчивости текущего ведущего к запросам на освобождение шины от устройств с меньшим уровнем приоритета.