Translate this page:
Please select your language to translate the article


You can just close the window to don't translate
Library
Your profile

Back to contents

Cybernetics and programming
Reference:

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

DOI:

10.7256/2306-4196.2014.4.12758

Received:

01-08-2014


Published:

15-08-2014


Abstract: The authors study arbitration system for data threads between ports of modern serial PCI Express bus. The article is devoted to the development of a model for that system. For the model the authors make an assumption, that switching matrix of the switch is non-blocking. Authors describe principles of the software model operation that allows to study the arbitration algorithm and the dependence of flow characteristics upon various factors. Using the mentioned above model the authors examines the influence of the virtual channels quantity and of the unevenness of the input ports load of the commutator on the amount of buffering memory of the port and virtual channels’ arbiters. The article uses computational experiment based on the software model of PCI Express bus arbitration as a method of the research. The produced model is based on the concepts and algorithms regulated by the official protocol specification for PCI Express. The authors present a software model of multistage arbitrator switch for PCI Express, in which varies the set of parameters of the arbitration specific for the real bus load on the cluster systems. The modular approach allows to modify the software model and include different priority schemes. The model designed and described in the article may be used in the building of the switch structure, as well as in configuration of an arbitrator, which can be useful when creating a cluster system with external PCI Express switches, which found practical use relatively recently. The model can be also used during the study of the PCI Express protocol.


Keywords:

arbitration, switch, PCI Express, serial interface, simulation model, priority scheme, cyclic scheme, virtual channels, waiting-line theory, transaction level


Введение

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

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

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

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

Структура модели и её параметры

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

z_pic1

Рис. 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 необходимо учитывать, что объем памяти, отводимой под очереди арбитража портов, должен быть больше и заполнение очередей может происходить более неравномерно.

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

z_pic3

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

Заключение

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

References
1. PCI Express Base 3.0 Specification [Elektronnyi resurs] // URL: http://www.pcisig.com/specifications/pciexpress/base3/
2. Tynkevich, M.A. Ekonomiko-matematicheskie metody (issledovanie operatsii) [Tekst] / M.A. Tynkevich. – Kemerovo, 2000. – 177 c.
3. Kostromina, N.V. Osnovy modelirovaniya vychislitel'nykh sistem: Uchebnoe posobie. [Tekst] / N.V. Kostromina, A.V. Aldashkin, D.V. Morokhin. – Ioshkar-Ola: MarGTU, 2000. – 150 s
4. Gorokhov A.V. Formal'nyi sintez struktury imitatsionnoi modeli (na primere sinteza sistemno-dinamicheskikh modelei) // Programmnye sistemy i vychislitel'nye metody. - 2013. - 3. - C. 277 - 284. DOI: 10.7256/2305-6061.2013.3.8855.