Рус Eng Cn Перевести страницу на:  
Please select your language to translate the article


You can just close the window to don't translate
Библиотека
ваш профиль

Вернуться к содержанию

Кибернетика и программирование
Правильная ссылка на статью:

Программная модель системы арбитража коммутатора PCI Express

Иванов Константин Владимирович

студент, кафедра Информационно-вычислительных систем, Поволжский государственный технологический университет

424000, Россия, республика Марий Эл, г. Йошкар-Ола, ул. Пл. Ленина, 3

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
Кошпаев Андрей Алексеевич

студент, кафедра Информационно-вычислительных систем, Поволжский государственный технологический университет

424000, Республика Марий Эл, г. Йошкар-Ола, пл. Ленина, дом 3.

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
Васяева Наталья Семёновна

кандидат технических наук

доцент, кафедра Информационно-вычислительных систем, Поволжский государственный технологический университет

424000, Республика Марий Эл, г. Йошкар-Ола, пл. Ленина, дом 3.

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

Дата направления статьи в редакцию:

01-08-2014


Дата публикации:

15-08-2014


Аннотация: Предметом исследований является система арбитража потоков данных между портами коммутаторов современной последовательной шины PCI Express. Статья посвящена вопросам разработки модели данной системы. При построении модели принято допущение, что коммутационная матрица коммутатора является неблокирующей. Авторами даётся описание принципов функционирования программной модели, позволяющей исследовать алгоритм арбитража и зависимость характеристик потоков от различных факторов. На основе модели исследуется влияние числа виртуальных каналов и неравномерность загрузки входных портов коммутатора на объём буферной памяти арбитра портов и арбитра виртуальных каналов. В качестве метода исследований использовался вычислительный эксперимент на основе программной модели алгоритмов арбитража шины PCI Express. Разработанная модель базируется на концепциях и алгоритмах, регламентированных официальной спецификацией протокола шины PCI Express. Получена программная модель многоступенчатого арбитра коммутатора шины PCI Express, в которой варьируется множество параметров арбитража, характерных для реальной загрузки шины в кластерных системах. За счёт модульного принципа построения программную модель можно модифицировать и включать другие схемы приоритетов. Разработанная и описанная в статье модель может использоваться при построении структуры коммутатора, а так же при конфигурировании арбитра, что может быть полезно при создании кластерных систем с внешними коммутаторами PCI Express, нашедшими практическое применение относительно недавно. Так же модель может применяться для исследования самого протокола PCI Express.


Ключевые слова:

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

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

Библиография
1. PCI Express Base 3.0 Specification [Электронный ресурс] // URL: http://www.pcisig.com/specifications/pciexpress/base3/
2. Тынкевич, М.А. Экономико-математические методы (исследование операций) [Текст] / М.А. Тынкевич. – Кемерово, 2000. – 177 c.
3. Костромина, Н.В. Основы моделирования вычислительных систем: Учебное пособие. [Текст] / Н.В. Костромина, А.В. Алдашкин, Д.В. Морохин. – Йошкар-Ола: МарГТУ, 2000. – 150 с
4. Горохов А.В. Формальный синтез структуры имитационной модели (на примере синтеза системно-динамических моделей) // Программные системы и вычислительные методы. - 2013. - 3. - C. 277 - 284. DOI: 10.7256/2305-6061.2013.3.8855.
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.