Software model of PCI Express switch arbitration

Ivanov Konstantin Vladimirovich student, Department of Information and Computing Systems, Volga State University of Technology 424000, Russia, respublika Marii El, g. Ioshkar-Ola, ul. Pl. Lenina, 3 ikv1992@yandex.ru Koshpaev Andrei Alekseevich student, Department of Information and Computing Systems, Volga State University of Technology 424000, Russia, Mari El, Yoshkar-Ola, pl. Lenina, 3. koshpaev1991@yandex.ru

Vasyaeva Natal'ya Semenovna PhD in Technical Science Associate Professor, Department of Information and Computing Systems, Volga State University of Technology 424000, Russia, Mari El, Yoshkar-Ola, pl. Lenina, 3. vasjaeva@mail.ru

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

В архитектуре PCI Express шины, с подсоединенными к ней устройствами, как таковой не существует. Обмен данными между устройствами происходит посредством коммутатора. Следовательно, арбитраж устройств на шине рассматривается как арбитраж между портами коммутатора с учётом специфики, накладываемой протоколом PCI Express.

При передаче трафика с нескольких входных портов коммутатора PCI Express на один выходной порт происходит конфликт, который решается при помощи арбитража, производимого на основе номеров виртуальных каналов (VC) и их приоритетов. Арбитраж в коммутаторе PCI Express проводится в два шага. Во-первых, транзакции, направленные на один виртуальный канал выходного порта и исходящие от разных входных портов, должны подвергнуться арбитражу, прежде чем они будут переданы соответствующим ресурсам виртуального канала в выходном порту. Данный арбитраж называется арбитражем портов и выполняется для каждого виртуального канала отдельно. Во-вторых, трафик, достигший ресурсов виртуального канала в выходном порту, подлежит арбитражу для попадания на общую линию передачи. Данный арбитраж называется арбитражем виртуальных каналов.

Поскольку арбитраж в коммутаторе PCI Express достаточно сложный, обеспечивает поддержку дифференцированных по классу обслуживания классов трафика (QoS) и производится в два этапа, исследователю может потребоваться средство определения характеристик потоков данных, таких как время ожидания пакета в очереди и длина очереди, для заданных параметров арбитража. В основе описываемой модели лежат алгоритмы, регламентированные спецификацией протокола PCI Express ^[1].

Арбитраж в коммутаторе PCI Express можно описать при помощи теории массового обслуживания, при этом пакеты представляются как заявки, буферная память – как очереди, а арбитр вместе с коммутирующей структурой – как обслуживающее устройство. В таком случае структура модели приобретает вид, изображенный на рисунке 1.

Рис. 1. Структура модели арбитража PCI Express, где КМ – коммутационная матрица

Перед началом работы с моделью необходимо задать ряд параметров:

• Количество входных портов
• Количество виртуальных каналов
• Количество виртуальных каналов в нижней группе – не больше заданного количества виртуальных каналов
• Схемы приоритетов, как для арбитража портов, так и для арбитража виртуальных каналов
  • Весовые коэффициенты (при использовании взвешенной циклической схемы приоритетов)
• Интенсивность потоков заявок (пакетов) на входных портах
• Вероятности нахождения в пакетах определенных меток класса трафика
• Временные величины, указывающие на производительность отдельных частей коммутатора или арбитра: время обслуживания заявок арбитром портов, время обслуживания заявок выходным портом, время поступления заявки в очередь арбитра портов

Арбитр коммутатора обрабатывает пакеты уровня транзакций (TLP), так как метка класса трафика входит в заголовок TLP. Согласно спецификации PCI Express длина пакета уровня транзакций может иметь различную длину в зависимости от типа транзакции и размера поля полезных данных ^[1]. В данной модели было принято допущение, что в системе PCI Express преобладают однотипные транзакции. В связи с этим длина пакета принимается постоянной, поэтому время обслуживания заявок выходным портом, как и время поступления заявки в очередь арбитра портов, тоже принимается постоянным.

Длины очередей принимаются неограниченными, поскольку в данной модели не будет учитываться управление потоком. Таким образом, модель будет представлять собой разомкнутую систему массового обслуживания (СМО) с неограниченным временем ожидания (без отказов). В результате моделирования для заданных параметров можно получить такие характеристики, как средние и максимальные длины очередей в обоих арбитрах, а так же средние и максимальные времена ожидания пакетов в очереди.

Поскольку моделируемая система достаточно сложная и использует оригинальную схему приоритетов, данную систему затруднительно описать в аналитическом виде. Поставленную задачу можно решить при помощи имитационного моделирования.

Время функционирования системы разделяется на достаточно большое количество подинтервалов. В данной работе под подинтервалом понимается единица времени, в течение которой не может возникнуть более одной заявки или завершиться выполнение более одной заявки. Для каждого такого подинтервала последовательно моделируется факт появления новой заявки, проверяется наличие свободного канала (закончено ли обслуживание какой-то заявки) и загрузка его заявкой из очереди. При этом фиксируется время ожидания заявок в очереди и в системе вообще, число заявок в очереди в каждый момент и другие значения ^[2].

Поток заявок характеризуется интенсивностью λ — частотой появления событий или средним числом событий, поступающих в СМО в единицу времени. Интервал времени между двумя соседними произвольными событиями имеет экспоненциальное распределение, для которого математическое ожидание равно среднему квадратическому отклонению случайной величины и обратно по величине интенсивности потока λ

`a=Sigma=1/Lambda` (1)

Имитацию случайной величины, распределенной по экспоненциальному закону, обычно выполняют при помощи метода обратной функции. Тогда требуемую случайную величину y можно получить из случайной величины x, распределенной равномерно на интервале (0;1), следующим образом ^[3]:

`y=-1/Lambda*ln(x)` (2)

Перед началом функционирования модели заранее вычисляются моменты поступления заявок на входных портах. Если x – случайная величина, распределенная по экспоненциальному закону, то массив значений моментов времени для n заявок заполняется следующим образом:

`t_(n)=t_(n-1)+x_(n)` (3)

Арбитр коммутатора PCI Express реализует циклическую и взвешенную циклическую схемы приоритетов, а на этапе арбитража виртуальных каналов также поддерживается статическая смена приоритетов, которая при необходимости может быть применена ко всем виртуальным каналам или только к некоторым.

При работе системы с циклической или взвешенной циклической схемой приоритетов может возникнуть ситуация, когда наивысшим приоритетом в определенный момент времени обладает очередь без заявок. Во избежание простоя и серьезного падения пропускной способности коммутатора арбитр должен принимать решение о передаче заявки и просматривать другие очереди быстрее, чем заявка поступает в систему. Поэтому за минимальный интервал времени (цикл) в модели принимается так называемый «такт арбитража». При вычислении массива моментов времени прихода заявок в систему следует учитывать, что время поступления заявки (`t_(receipt)`) в очередь больше, чем такт арбитража. Тогда момент времени прихода i-й заявки можно вычислить по формуле

` ` `t_(n)=t_(receipt)+t_(n-1)+x_(n)` (4)

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

Время обслуживания зависит от времени передачи пакета выходным портом. Оно может отличаться от времени прохождения пакета, заданного для входного порта, в случае, когда скорость передачи входного и выходного порта отличается (из-за разного количества каналов, например, x1 и x4).

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

Например, в одном из экспериментов исследовалась зависимость средней длины очереди от средней интенсивности потока входных пакетов.

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

Среднее время между появлениями входных пакетов изменялось в диапазоне от 1 до 10 тактов. Время обслуживания для всех трех исполнительных устройств было установлено равным 10 тактам.

Результаты эксперимента приведены на рис. 2 и 3. Из графиков видно, что среднее время ожидания в очередях арбитра портов подчиняется экспоненциальному закону и увеличивается с ростом средней интенсивности потока входных пакетов. Аналогичная величина арбитража виртуальных каналов ведет себя иначе. При увеличении средней интенсивности
потока входных пакетов средняя длина очереди арбитра виртуальных каналов возрастает логарифмически. Это связано с тем, что при равномерной загрузке портов и равных приоритетах очереди в арбитре виртуальных каналов заполняются равномерно.

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

Опыт показал, что при разработке коммутатора PCI Express необходимо учитывать, что объем памяти, отводимой под очереди арбитража портов, должен быть больше и заполнение очередей может происходить более неравномерно.

Рис. 2. Результаты эксперимента для арбитра портов

Рис. 3. Результаты эксперимента для арбитра виртуальных каналов

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