Разработка HDL-модели сети на кристалле

Размещено на http://www.allbest.ru/

Аннотация

сеть кристалл программа связь

Сети на кристалле (СтнК) являются новой вехой развития микропроцессорных систем, так как позволяют увеличить число вычислительных ядер и дополнительных модулей в системах на кристалле (СнК). Поэтому требуются средства для их моделирования и прототипирования. В работе представлена реализация генерируемой сети на кристалле с различными параметрами на языке Verilog, которая поддерживает топологии mesh, torus и circulant 2 порядка. Изменяемыми параметрами модели для настройки являются: количество узлов, размер буфера маршрутизаторов, параметры передаваемых пакетов, частота их генерации, специфические параметры для каждой топологии и настройки сетевого трафика. Разработан простой маршрутизатор, система их связи, а также вспомогательные программы для работы с моделью.

Введение

В связи с увеличивающимися требованиями к мощностям вычислительных систем требуется создать новые способы повышения их производительности. Закон Мура перестает работать, а производители систем на кристалле не могут больше увеличивать их тактовую частоту. Остается увеличение числа вычислительных ядер, однако классический способ соединения - системная шина - перестает эффективно работать для количества ядер более 8, так как электрическая нагрузка снижает ее рабочую область, и шина не отвечает пропускной способности системы на кристалле. Разработчики постоянно улучшают архитектуру шины, но это решение является плохо масштабируемым для конкретных задач. Более эффективным способом решения данной проблемы может стать использование сетей на кристалле (СтнК) [1]. СтнК - множество вычислительных модулей, объединенных общей подсистемой связи, состоящей из маршрутизаторов и соединений между ними. Для их разработки требуются модели, которые могли бы симулировать работу реальных СтнК. Существует два подхода к разработке моделей: на языках высокого уровня и языках описания аппаратуры (hardware description language, HDL). Наиболее точными являются HDL модели, так как они симулируют работу каждого реального элемента, однако они гораздо медленнее высокоуровневых моделей. Появление новых подходов к построению СтнК, их сложность структуры и увеличение количества узлов требуют новых подходов моделирования и синтеза таких сетей, а также разработки новых маршрутизаторов. Обычно это достигается путем построения HDL моделей, что позволяет точно моделировать и дополнительно облегчать синтез СтнК [2]. В данной работе будет разработана модель СтнК для тестирования различных маршрутизаторов, подбора топологий и параметров сети.

1. Обзор и анализ предметной области

1.1 Обзор литературы

В статье [3] описываются общие принципы построения сетей на кристалле. Сеть состоит из маршрутизаторов, соединенных с помощью топологии mesh размером mЧn (рисунок 1). К каждому маршрутизатору подсоединен источник данных, который может быть процессорным ядром, RAM-памятью, или каким-либо другим блоком. У каждого их них есть свой адрес, и между ними происходит передача пакетов, разделенных на флиты. Маршрутизатор сам по себе состоит из входных и выходных портов, буфера (одного или нескольких), а также внутренней логики выбора портов приема и передачи.

Рисунок 1 – Общая структура СтнК.

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

В СтнК определяются 4 уровня протоколов:

1. Физический уровень, определяющий количество и длину шин;

2. Уровень передачи данных, который определяет протокол передачи данных между ресурсом и маршрутизатором, либо между 2 маршрутизаторами;

3. Сетевой уровень описывает, как пакеты устроены и будут передаваться от источника до цели. Часть пакета является данными, остальная - служебной информацией. Также пакеты могут делиться на составные части - флиты;

4. Транспортный уровень независим от технологии создания сети и описывает как полные пакеты переходят по сети.

Для моделирования СтнК используются 2 подхода: на языках высокого уровня и языках описания аппаратуры. Первый подход приобрел большее распространение, так как время моделирования значительно меньше. Он позволяет быстро опробовать различные топологии и способы передачи данных, использовать языки высокого уровня.

Среди них есть модель на Matlab [4]. Она использует SimEvents toolbox. Разработан 5-портовый маршрутизатор с виртуальными каналами (virtual channel, VC), который пропускает через себя флит за 10 тактов. Из них собрана сеть с топологией mesh размером 4x4, работающая с тактовой частотой 500 МГц. Она работает без потерь с коэффициентом загрузки флитов (flit injection rate, fir), показывающим, сколько флитов входит в сеть за единицу времени, от 0 до 53%. Модель полностью рабочая и с помощью нее можно тестировать различные топологии и алгоритмы маршрутизации.

Следующая модель [5] создана с использованием расширенной библиотеки SystemC под названием Asynchronous SystemC library (ASC). В работе сравниваются методы моделирования с помощью HDL моделей, на SystemC, сравниваются их преимущества и недостатки. Затем с помощью ASC создается элементная база для разработки асинхронной логики и СтнК. Дальнейшая цель работы - получить возможность отслеживать состояние регистров в устройствах.

В работе [6] представлена среда Nostrum Network-on-Chip Simulation Environment (NNSE), созданная для подбора оптимальных параметров работы сети для решения конкретных задач. Ядро системы называется Semla и основано на systemC. Доступные в модели топологии: mesh и torus. Маршрутизаторы используют виртуальные каналы, глубину которых можно указать в параметрах. Для передачи пакетов может быть использована передача типа wormhole или deflection. После конфигурирования сети будет собрана статистика ее работы по схеме передачи пакетов. Это главное отличие модели от остальных. На момент публикации модель обладала ограниченным списком доступных параметров, однако разработчики планировали увеличить их количество.

Все эти модели объединяет то, что они не синтезируются в реальную СтнК. HDL модель лишена этого недостатка по своей природе, однако моделирование происходит гораздо дольше, так как обрабатывается каждый элемент цепи в каждый момент времени. Таких моделей на данный момент разработано очень мало. Одна из них [7] создана на языке Verilog с использованием простого маршрутизатора с центральным буфером и схемой передачи пакетов wormhole [8]. Соединение маршрутизаторов происходит с помощью программы на C++, что делает библиотеку недостаточно гибкой и автоматизированной. После моделирования подсчитывается статистика работы сети также с использованием сторонней программы. В данном случае это применимо, так как это вспомогательные действия. Разработанная модель может быть синтезирована для ПЛИС, например, Cyclone II и Stratix II, где тактовая частота работы 200 MHz и 310 MHz соответственно. Также в статье рассказано, как использовать регулярные топологии с числом узлов, не предназначенным для нее. При использовании такой модели удалось увеличить пропускную способность на 20 % для квази-оптимальных топологий по сравнению с виртуальными каналами.

В [9] приведено описание маршрутизатора с VC и способы их оптимизации с различными параметрами. Они в теории позволяют уменьшить задержку доставки пакетов и справляться с deadlock. Это состояние, когда сеть перестает функционировать, если пакеты пытаются попасть в маршрутизаторы с заполненными буферами. Однако увеличение размера виртуального канала значительно улучшает использование буферного пространства. Описано влияние на пропускную способность размера буфера. Наилучший результат в исследовании показала конфигурация из 4 VC размером в 1 флит.

Аналитические выводы

Из анализа литературы следует, что разработка HDL моделей является актуальной, так как их гораздо меньше, чем высокоуровневых моделей СтнК. Они позволяют быстро подбирать оптимальные параметры сети, однако их нельзя использовать для тестирования отдельных компонентов или для разработки полноценной сети. В то же время, с использованием HDL моделей можно тестировать компоненты сети и строить рабочие сети на кристалле. Модель должна быть гибкой к изменениям, то есть поддерживать различные топологии и виды маршрутизаторов, а также добавление новых.

Для быстрой разработки модели выбран маршрутизатор с центральным буфером из работ [7][8], так как он прост в разработке и отладке. Планируется в дальнейших работах сравнить его с маршрутизатором, использующим виртуальные каналы, а также модернизировать для повышения пропускной способности при возможности.

Цели и задачи

Целью данной работы является создание HDL модели сети на кристалле для выбора оптимальных топологий, типов маршрутизаторов и параметров сети, тестирования различных компонентов СтнК, а также иметь возможность использовать модель для разработки прототипа на ПЛИС. Необходимо разработать маршрутизаторы, создать способ генерации передаваемых в сети данных, объединить все в одну рабочую модель с возможностью задавать ее параметры. Также требуются вспомогательные программы для создания таблиц маршрутизации маршрутизаторов, сбора статистики работы сети, автоматизированного запуска модели и тестов.

Описание методов решения

Требуется выполнить следующие этапы работы над проектом:

1. Разработка элементов сети на кристалле (компоненты маршрутизатора, полный маршрутизатор, модуль для соединений модуль для создания нагрузки сети);

2. Тестирование всех компонентов на соответствие ожидаемым выходным сигналам;

3. Сбор всех компонентов в полную модель и ее отладка. На этом этапе может поменяться логика работы компонентов, так как работа полной сети может не соответствовать ожидаемой;

4. Сбор статистики работы СтнК с различными параметрами и топологии. Анализ результатов.

Модель разработана на языке Verilog. Ее симуляция выполняется в среде Modelsim, однако модель может быть перенесена на другую. Для создания таблиц маршрутизации используются дополнительные программные средства на языке Python, но сама модель генерируется по параметрам сети. Для удобного запуска модели требуется разработать дополнительные скрипты. Модель будет разрабатываться от меньших элементов к большим и тестироваться на каждом уровне. В первую очередь будет реализован маршрутизатор с одним буфером как в статье [7], так как он является простым для разработки. Взаимодействие маршрутизаторов между собой происходит с помощью контрольных сигналов (in_r, in_w, out_r, out_w). Модули receiver and transceiver определяют, заполнен ли буфер, а также есть ли доступный маршрутизатор для чтения или записи флита. В них реализованы конечные автоматы, которые управляют маршрутизатором. Процесс передачи данных происходит по следующему алгоритму: каждый маршрутизатор ожидает, когда другой будет готов записывать данные. После этого он последовательно принимает флиты, блокируя другие порты для чтения. Они сохраняются в очередь до тех пор, пока требуемый маршрутизатор не будет доступен для записи. С помощью таблицы маршрутизации выбирается порт, на который отправится следующий флит. Порты маршрутизаторов объединены в общую шину для возможности увеличения их количества. На передачу флита через маршрутизатор требуется 3 такта. Алгоритмически будут заданы связи между маршрутизаторами в виде одной из регулярных топологий с возможностью считывания стороннего Verilog-файла с соединениями.

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

2. Разработка элементов СтнК

2.1 Структура системы

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

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

Рисунок 2 – Структура флита.

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

2.2 Маршрутизатор

Маршрутизатор - это модуль, предназначенный для передачи пакетов с одного порта на другой с возможностью их хранения. В работе используется маршрутизатор, разработанный на основе работы [8]. Он состоит из входных портов, центрального буфера и выходных портов (рисунок 3).

Рисунок 3 – Структура маршрутизатора.

Модуль receiver отвечает за прием флитов из входных портов. В данной реализации будут использоваться 4 порта, однако модель позволяет изменить их количество с помощью параметра PORTS_NUM. Также у маршрутизатора есть дополнительный порт для связи с IP ядром. Каждый входной порт состоит из данных и служебных сигналов in_r и in_w. Изначально модуль находится в режиме ожидания и последовательно опрашивает все сигналы in_r. Когда на один из них приходит единица, это значит, что другой маршрутизатор готов передать пакет. После этого флиты последовательно принимаются и записываются в буфер, если он не заполнен. После приема каждого флита на сигнал in_w отправляется сигнал подтверждения получения. Флиты перестают приниматься при получении последнего, тогда receiver снова переходит в режим ожидания пакета.

Буфер является циклической очередью. Размер буфера определяется параметром MEM_LOG2 и равен 2^(MEM_LOG2). Он имеет порты для ввода и вывода, сигналы о состоянии памяти (full и empty, означающие соответственно заполнена ли память или пустая) и управляющие сигналы (wr_req и mem_readed, отвечающие за запись и чтение в текущий момент времени). В очереди указатели на текущий записываемый и читаемый элементы, регистр заполненности filling. Когда на wr_req приходит 1, filling увеличивается на один, а указатель записи смещается вперед. При mem_readed = 1 регистр filling уменьшается на 1 и указатель чтения смещается вперед.

Модуль transceiver - выходные порты маршрутизатора. Их то же количество, что и в модуле receiver. Управляющие сигналы - out_r и out_w. Первый флит пакета, который готов для считывания, определяет порт, через который будут отправлены все остальные флиты. Это происходит при соотнесении конечного адреса с таблицей маршрутизации. Таблица маршрутизации задается модулем routing_module. В нем хранится статическая таблица маршрутизации, которая считывается из инициализирующего файла. Когда из очереди приходит флит, его адрес доставки соотносится с таблицей маршрутизации и получается порт, на который его нужно отправить в данный момент. Если получатель готов читать флит, на out_w будет установлен 0. После этого флит отправляется на нужный порт, на out_r устанавливается 1, модуль ждет подтверждения на сигнале out_w. Когда на нем появляется 1, модуль готов передать следующий флит либо закончить передачу пакета и ждать следующий.

2.3 Модуль топологии

В общем случае топология СтнК представляет собой неориентированный связный граф, состоящий из вершин - маршрутизаторов и ребер - физических линий связи между ними. Основными характеристиками топологии являются: количество вершин-маршрутизаторов (N); количество ребер - физических соединений между маршрутизаторами (Ed); cтепень вершины -количество ребер, исходящих из нее (St); диаметр графа -максимум среди минимальных расстояний между любыми двумя вершинами (D); среднее расстояние среди наиболее коротких путей между всеми узлами графа (Lav). Чем ниже Ed, тем меньше ресурсные затраты, а чем меньше Lav и D, тем быстрее пакеты достигают цели [10].

В модуле присутствуют две шины, вход и выход, которые имеют размер PORT_SIZE*PORTS_NUM*NODES_NUM. PORT_SIZE - размер одного порта маршрутизатора, в который входят управляющие сигналы. NODES_NUM - количество маршрутизаторов в сети. Обе шины имеют вид: 0 порт 0 маршрутизатора, 1 порт 0 маршрутизатора, …, 0 порт 1 маршрутизатора, 1 порт 1 маршрутизатора и так далее. Это сделано для обеспечения гибкости системы и возможности изменять ее для любого количества маршрутизаторов и портов.

В модуле с помощью директивы generate происходит перебор индексов маршрутизаторов. Благодаря этому можно алгоритмически задать регулярные топологии, такие как mesh, torus и circulant (рисунок 4), а также избавиться от однообразного кода и дополнительных средств для генерации файла со связями. Также возможно добавить собственный файл с собственной нерегулярной топологией.

Рисунок 4 – Используемые топологии (mesh, torus и circulant 2 порядка)

Модуль связи маршрутизаторов содержит в себе директивы компилятора `ifdef, `elsif, `endif, благодаря которым выбирается, какая из топологий будет использована. Выбор происходит по тому, какой из макросов определен в момент сборки проекта. На данный момент из топологий доступны mesh, torus и circulant 2 порядка, однако имеется возможность добавить любую другую, дописав в условии собственный модуль со связями.

Для алгоритма соединения маршрутизаторов необходимо условиться о расположении портов. На рисунке 5 указано направление портов в топологиях mesh и torus.

Рисунок 5 – Размещение портов маршрутизатора в топологиях mesh и torus.

На примере топологии torus приведен алгоритм соединения различных портов в разных участках шины:

1. Вручную составляются несколько таблиц связей размера NxN, где N - количество узлов в сети. Ряды означают маршрутизатор-источник, а столбцы - маршрутизатор-назначение. Цифра означает порт, на который будут отправлены пакеты источником. Прочерки означают, что соединений нет. Пример такой таблицы на рисунке 5.



Рисунок 6 – Пример таблицы соединений для топологии torus 4х4.

2. По данной таблице составляются правила, по которым каждый порт одного маршрутизатора будет соединен с портами других. Запись будет вестись так, что первый номер порта является портом источника, а второй - назначения. Для топологии torus это:

Таблица 1 – Правила соединений портов в топологии torus.

Номер порта маршрутизатора sw_src	Номер порта маршрутизатора sw_dst	Правило, при соблюдении которого будет создано соединение
0	2	(sw_dst == sw_src + 1 and sw_src % h_size != h_size - 1) or (sw_src % h_size == h_size - 1 and sw_src-sw_dst-h_size+1 == 0)
1	3	sw_dst == sw_src + h_size or nodes_num - sw_src + sw_dst == h_size

Здесь sw_dst - маршрутизатор назначения, sw_src - маршрутизатор-источник, h_size - размер меша по горизонтали.

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

Ниже приведены правила для составления связи у топологий mesh. Они получены по алгоритму, описанному выше.

Таблица 2 – Правила соединений портов в топологии mesh.

Номер порта маршрутизатора sw_src	Номер порта маршрутизатора sw_dst	Правило, при соблюдении которого будет создано соединение
0	2	sw_dst == sw_src + 1 and sw_dst % h_size != 0
1	3	sw_dst == h_size + sw_src

Правила для circulant 2 порядка отличаются, так как такая топология имеет другой принцип построения. Вместо проверки индекса узла назначения на соответствие правилу нужный индекс высчитывается с помощью операций сложения и вычитания по модулю.

Направления портов для топологии circulant 2 порядка:

Рисунок 7 – Размещение портов маршрутизатора в топологии circulant 2 порядка.

Операции сложения и вычитания по модулю можно записать в виде формул (a + b) % c и (a - b) % c соответственно. Однако для удобного использования они реализованы в коде на Verilog в виде макроподстановок. Для работы с generate требуется использовать тип genvar, который является беззнаковым. Выполнить правильное вычитание для беззнаковых переменных нельзя, поэтому формулы выше были заменены условные конструкции в виде тернарных операторов (1-2).

,(1)

(2)

Таблица 3 – Правила соединений портов в топологии circulant 2 порядка.

Номер порта маршрутизатора sw_src	Номер порта маршрутизатора назначения	Индекс маршрутизатора назначения
0	3	(sw_src + s1) % nodes_num
3	0	(sw_src - s1) % nodes_num
1	2	(sw_src + s2) % nodes_num
2	1	(sw_src - s2) % nodes_num

Nodes_num - количество узлов в сети, s1 и s2 - длина 1 и 2 шагов.

2.4 Модуль загрузки сети

Модуль загрузки сети fabric должен сгенерировать определенное количество пакетов для передачи. Это число задается параметром PACKS_TO_GEN. Длина пакета случайная от 1 до MAX_PACK_LEN. Адреса пакетов случайные, поэтому число отправленных пакетов не будет равно числу полученных. Однако оно никогда не будет равно 0 из-за равномерного распределения функции $random, с помощью которой генерируется весь пакет и адрес назначения. После создания пакета он делится на флиты. Это сделано для того, чтобы после получения пакета и сборки можно было проверить целостность доставленного пакета.

В модуле fabric реализованы два конечных автомата. Первый конечный автомат создан для генерации пакетов и отправки флитов в маршрутизатор. В случае, если адрес доставки пакета совпал с адресом текущего маршрутизатора, весь пакет будет создан заново. Также существуют параметры FLIT_DELAY и PACK_DELAY, которые отвечают за задержку отправки флита и генерации пакетов соответственно. Благодаря ним возможно регулировать такие параметры как flit injection rate и packet injection rate. Флит передается также, как это делает маршрутизатор, с использованием тех же сигналов. Блок-схема конечного автомата представлена на рисунке 8.

Рисунок 8 – Блок-схема конечного автомата генерации пакетов модуля fabric.

Второй конечный автомат ответственен за прием флитов. В нем всего два состояния: в первом считывается флит, когда он доступен, собирается пакет и проверяется, правильный ли адрес доставки у флита. Во втором состоянии происходит подтверждение считывания (рисунок 9).

Рисунок 9 – Блок-схема конечного автомата получения пакетов модуля fabric.

Также модуль ведет логирование всех событий. Все экземпляры модуля на протяжении симуляции делают свои записи в один файл (рисунок 10). Этот файл будет обработан и по нему собрана статистика работы сети. Однако в режиме отладки, который задается параметром DEBUG все логи будут выведены в консоль Modelsim, а не отдельный файл. Кроме этого, он считает количество полученных флитов и пакетов, время работы, которое выражается в тактах.

Рисунок 10 – Фрагмент файла логирования.

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

2.5 Разработка ПО для создания таблиц маршрутизации

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

Для mesh используется алгоритм маршрутизации XY [11]. Таблица создается следующим образом: 2 цикла итерируют индексы узла-источника и узла-цели. Если индексы равны, то выбирается порт 4 (то есть данные отправляются в модуль fabric). Иначе проверяется, надо ли двигаться влево или вправо (порты 0 и 2). Это делается с помощью деления на значение параметра h_size, которое определяет размер сети по горизонтали. Если остаток от деления индекса источника больше, чем остаток от деления индекса цели, то выбирается 2 порт (движение влево), если меньше, то порт 0 (движение вправо). Если остатки равны, значит, что узлы находятся на одной линии и выбирается движение по вертикали (порты 1 и 3). Сравниваются индексы, и если индекс цели больше источника, то выбирается порт 1, иначе - 3.

Для тора общий принцип идентичный, за исключением того, что используется операция вычитания по модулю. Сначала сравниваются остатки от деления на h_size. Если они равны (то есть источник и приемник находятся в одном столбце), то считается расстояние от одного маршрутизатора до другого в оба направления. Таким образом выбирается 1 либо 3 порт. Если узлы находятся в разных рядах, то точно также считаются расстояния по горизонтали, и выбирается минимальное.

Для топологии circulant использован адаптивный алгоритм маршрутизации из работы [10]. Данный алгоритм накладывает ограничения на топологию: возможно использовать только первую образующую равную 1. Такой тип называется ring circulant. При этом достаточно вычислить маршруты для одного узла, а затем использовать их для всех остальных. Передающие порты у всех узлов будут аналогичны. Топология ring circulant не является оптимальной, однако при этом ее Lav почти всегда совпадает с оптимальными с тем же количеством узлов.

Пример таблицы маршрутизации представлен на рисунке 11.



Рисунок 11 – Таблица маршрутизации для топологии torus 4Ч4.

Таблица маршрутизации перевернута по вертикали, так как это требуется для инициализации в Verilog с помощью встроенной функции $readmemh [12].

2.6 Сборка модели

Все настройки модели задаются в специальном файле configs.vh. Он импортируется в файл верхнего уровня и далее передаются в виде параметров в модули. Это сделано для избегания переопределения или ошибки импорта. Список параметров модели:

1. Количество узлов в сети;

2. Количество портов в маршрутизаторах;

3. Размер поля адреса флита;

4. Размер поля данных флита;

5. Размер буфера маршрутизатора;

6. Максимальный размер пакета;

7. Количество пакетов для генерации каждым узлом;

8. Ограничение на время моделирования;

9. Задержка генерации пакетов;

10. Задержка генерации флитов;

11. Параметры для топологий;

12. Параметры режима работы модели.

Модель собрана с помощью конструкции generate. Создается NODES_NUM маршрутизаторов и fabric-модулей, соединенных вместе. Все порты маршрутизатора последовательно соединяются с входной и выходной шинами размером NODES_NUM*PORTS_NUM*PORT_SIZE, где PORT_SIZE - размер порта, в который входит размер передаваемых данных и два бита на служебные сигналы. Шины подключены к модулю топологий, который задает последовательность соединений входов и выходов. Вся схема продемонстрирована на рисунке 12:

Рисунок 12 – Блок-схема модуля верхнего уровня.

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

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

2.7 Автоматизация запуска модели

Для автоматизации запуска моделирования написаны bat и tcl скрипты. Bat-скрипт принимает из консоли параметры для запуска модели. Затем он очищает рабочую папку для симуляции, если она сохранилась после предыдущего запуска. Генерируется файл таблицы маршрутизации с помощью python-скрипта. Запускается tcl-скрипт, в котором создается рабочая библиотека, компилируются все исходные файлы, запускается симуляция. После ее завершения Modelsim закроется самостоятельно.

Результатом работы модели является файл с логами работы сети. Его требуется обработать отдельным скриптом-парсером, который также написан на Python. Главная функция скрипта проходит по всему файлу, собирая информацию о параметрах сети, количество отправленных и полученных флитов и пакетов, их среднее время передачи, проверяет их целостность пакетов, адреса доставки, полное время работы модели. Временем работы модели является время получения последнего флита в сети. Изначально эта статистика собирается для каждого узла, затем суммируется в общую. Подсчитываются fir и pir. При этом обрабатываются ошибки в случае, если модель отработала некорректно и файл с логами дает заведомо неправильную информацию (например, если время моделирования или количество узлов равно 0). Результаты подсчета статистики форматированно выводятся в консоль и сохраняются в файл.

Пример файла со статистикой для топологии circulant представлен на рисунке:



Рисунок 13 – Рисунок 7. Файл со статистикой работы сети.

Так как в сети 25 узлов, на рисунке приведены полная статистика работы сети и статистика для 0 узла.

3. Тестирование модели

Для тестирования работы сети проводилось моделирование с 9 узлами. Каждый узел должен был сгенерировать 11000 пакетов. Экспериментально установлено, что время задержки генерации пакетов должно составлять 150 тактов. При меньшей задержке возникает deadlock, что приводит к остановке работы сети [13]. Результаты моделирования представлены в таблице 4.

Таблица 4 – Результаты моделирования сетей с 9 узлами.

Топология	mesh 3Ч3	torus 3Ч3	circulant С(9; 1, 2)
Среднее время доставки флита (в тактах)	47.71	23.25	23.64
Время моделирования (в тактах)	2135601	2091808	2093121

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

После отладки модели на сети с маленьким количеством узлов было проведено моделирование сети с 25 узлами. Использовалась задержка генерации пакетов в 300 тактов.

Таблица 5 – Результаты моделирования сетей с 25 узлами.

Топология	mesh 5Ч5	torus 5Ч5	circulant C(25; 1, 2)
Среднее время доставки флита (в тактах)	56.96	31.9	29.81
Время моделирования (в тактах)	3717561	3684439	3684114

Время моделирования, как и среднее время доставки, ожидаемо увеличилось, так как сумма пакетов для генерации стала 275000 вместо 99000.

4. Оптимизация параметров модели

4.1 Разработка вспомогательного ПО

Важнейшими показателями работы сети являются время моделирования и среднее время передачи пакета. Так как маршрутизатор в один момент времени может задействовать один порт, наибольшее влияние на пропускную способность сети оказывает параметр packet_delay, отвечающий за время задержки ввода пакета в сеть в тактах. Для анализа его влияния на сеть реализован скрипт на языке Python, строит графики зависимости времени моделирования и среднего времени передачи пакета от любого параметра. Так как Modelsim не может самостоятельно распараллеливать симуляцию, одновременно запускаются несколько симуляций с разными параметрами с помощью Pool из библиотеки multiprocessing [14].

Для оптимизации работы с моделью она запускается прямо из python-скрипта, минуя bat. Добавлен способ получения конфигураций из командной строки, параметры хранятся в json-файле. При запуске производится текстовый анализ данного файла, в результате чего генерируются конфигурации для запуска одной или нескольких моделей. Происходит проверка полученных параметров. Все результаты сохраняются в дампы, также хранящиеся в формате json. Таким образом, в случае прерывания работы скрипта или при повторном построении не требуется проводить повторные моделирования. Функция построения графиков идет по точкам в отрезке с фиксированным шагом, моделируя работу сети с данной задержкой. По полученным точкам строятся графики.

Разработан скрипт для нахождения минимальной допустимой задержки ввода пакета в сеть. Из анализа графиков на рисунках 13-17 видно, что в точках, где сеть полностью передает отправленные пакеты, есть определенная зависимость. Аппроксимировать точки удалось с помощью функции:

(3)

Для поиска условного минимума функции потребуется ее производная:

(4)

Используя ее, можно уменьшить время минимизации параметра. Для этого разработан алгоритм:

1. Высчитывается первая точка (start_delay), в которой полностью переданы отправленные пакеты. Это происходит увеличением параметра на 1, параллельно выполняется сразу jobs_num (как правило, количество ядер процессора в используемом компьютере) симуляций. В тот момент, когда одна из точек подходит, итерирование прекращается.

2. Отрезок от start_delay до start_delay + 1000 делится на jobs_num точек. В них параллельно получаются точки, по которым будет происходить аппроксимация. Важно чтобы точек было больше 3.

3. По полученным точкам происходит аппроксимация функции (3). Для этого используется функция curve_fit из библиотеки scipy [15]. После ее выполнения получаются коэффициенты a, b, c, d, используя которые можно по формуле получать примерное среднее время моделирования по задержке.

4. Происходит поиск условных минимумов функции (3) по jobs_num точкам с помощью функции opt_n_points. Границы поиска от start_delay до start_delay + 1000. Для получения новых минимумов параметр эпсилон меняется по правилу:

(5)

Параметр eps_pow устанавливается при запуске алгоритма. В данном случае он равен 8. Индекс i итерируется для получения каждой новой точки. Каждый минимум проверяется передачей в 5 раз большим количеством пакетов. В случае нахождения точки переход к пункту 5.

5. Происходит одна итерация для поиска минимума от максимальной нерабочей задержки до минимальной рабочей. Индекс i в (5) итерируется от 0 до предыдущего i в квадрате. Полученные точки проверяются, и наименьшая из них является результатом работы алгоритма.

Ниже представлен алгоритм работы функции opt_n_points:

1. Отрезок от a до b делится на n-1 одинаковых отрезков. Из них исключаются возможные повторы.

2. Для каждого значения из отрезка высчитывается значение целевой функции (в данном случае это производная (4)).

3. Выбирается 1 и 2 условные минимумы. Они инициализируются первым и вторым значениями списка. Если разница между 1 минимумом и текущим значением больше eps, и минимум больше значения, то 1 минимум становится 2, а значение функции - 1 минимумом.

4. Функция рекурсивно применяется для отрезка от 1 до 2 минимума. Это происходит до тех пор, пока разница между значениями x больше 1. Возвращается 1 минимум.

4.2 Исследование зависимостей параметров сети

Для изучения выбраны 3 неоптимальных топологии (mesh 2Ч8, torus 2Ч8 и circulant ) и 3 оптимальных (mesh 4Ч4, torus 4Ч4, ring circulant [16]). Каждый узел должен сгенерировать 11000 пакетов для передачи. Ограничение времени моделирования равно 10⁷ тактов. Графики зависимости среднего времени передачи пакета и времени моделирования от задержки ввода пакета в сеть представлены на рисунках 14-19.

Рисунок 14 – График зависимости среднего времени передачи пакета и времени моделирования от параметра pack_delay в топологии mesh 2Ч8.

Рисунок 15 – График зависимости среднего времени передачи пакета и времени моделирования от параметра pack_delay в топологии torus 2Ч8.

Рисунок 16 – График зависимости среднего времени передачи пакета и времени моделирования от параметра pack_delay в топологии circulant C(16, 1, 2).



Рисунок 17 – График зависимости среднего времени передачи пакета и времени моделирования от параметра pack_delay в топологии mesh 4Ч4.

Рисунок 18 – График зависимости среднего времени передачи пакета и времени моделирования от параметра pack_delay в топологии torus 4Ч4.

Рисунок 19 – График зависимости среднего времени передачи пакета и времени моделирования от параметра pack_delay в топологии circulant C(16; 1, 6).

Так как среднее время передачи пакетов начинает уменьшаться слишком медленно, требуется найти такую задержку, при которой пакеты будут передаваться достаточно быстро, а время моделирования останется приемлемым.

Результаты нахождения минимальных задержек для тестовых топологий представлены в таблице 6.

Таблица 6 – Минимальные рабочие задержки.

Топология	mesh 4Ч4	mesh 2Ч8	torus 4Ч4	torus 2Ч8	circulant C(16; 1, 2)	circulant C(16; 1, 6)
Задержка (такт)	260	387	143	201	232	165
Среднее время передачи пакета (такт)	44.34	56.78	40.49	42.64	42.83	32.06

Из результатов моделирования следует, что параметры топологии сильно влияют на производительность сети. Так, у топологии mesh 2Ч8 неоптимальной формы среднее время передачи пакетов значительно выше, чем у mesh 4Ч4. При этом невозможно создать топологии mesh и torus с количеством узлов, не являющимся квадратом. В этом заключается преимущество топологии circulant перед ними. Также у топологий torus и mesh большие диаметр и средняя длина пути между узлами, по сравнению с circulant. Поэтому у топологии ring circulant наименьшее время передачи пакетов среди тестируемых топологий, и этот тип топологии с оптимальными образующими будет использоваться в дальнейших экспериментах.

Для изучения влияния количества узлов на задержку была проведена оптимизация топологий C(4; 1, 2), C(9; 1, 2), C(16; 1, 6), C(25; 1, 7), C(36; 1, 8), C(49; 1, 9), C(64; 1, 14), C(81; 1, 24), C(100; 1, 18) [16]. Для передачи использовалось только 5500 пакетов, так как с увеличением количества узлов значительно возрастает время моделирования, а для проверки минимальных задержек используется в 5 раз большее количество пакетов. При попытках моделирования СтнК с большим количеством было выявлено, что это занимает слишком много времени в связи с ограничениями производительности Modelsim [17]. Результаты оптимизаций представлены на рисунке 20.



Рисунок 20 – График зависимости минимальной задержки ввода пакета в сеть от количества узлов.

Точками на графике обозначены результаты моделирований, а линией - аппроксимированная функция корня.

Для оценки зависимости среднего времени передачи пакетов от количества узлов взята минимальная задержка для сети со 100 узлами и проведено моделирование тех же параметров, что и в предыдущем опыте. Для передачи также использовалось 11000 пакетов.

Рисунок 21 – График зависимости среднего времени передачи пакетов от количества узлов при одинаковой задержке.

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

Выводы к разделу 5

Создан набор функций для работы с моделью на языке python для автоматизации работы с ней. На основе анализа графиков удалось получить функцию общего вида для ускорения оптимизации с минимальным количеством симуляций. С данными задержками через сеть с данными маршрутизаторами возможно передать любое (или достаточно большое) количество пакетов. Выявлено большое влияние типа топологии и ее параметров на производительность СтнК. Среди тестируемых наиболее удачной топологией оказалась ring circulant с оптимальными образующими. На основе полученных результатов можно делать выводы о зависимостях и оценивать параметры и результаты работы сетей различных конфигураций без проведения моделирования. Разработанная модель не является эффективной для симуляции работы сетей с большим количеством узлов, однако дает очень точные результаты и позволяет проверять и сравнивать показатели разных топологий и маршрутизаторов.

Заключение

В результате работы разработана HDL модель сети на кристалле. В ней доступно множество параметров для изменения. Модель поддерживает 3 топологии mesh, torus и circulant 2 порядка, а также возможность добавить собственный конфигурационный файл со связями маршрутизаторов.

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

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

Модель реализована на уровне HDL, что обеспечивает высокую точность моделирования, но имеет достаточно высокое время симуляции с увеличением количества узлов. Для повышения скорости работы модели при необходимости провести несколько моделирований с различными параметрами существует возможность параллельного исполнения нескольких процессов. Кроме того, при небольшой доработке модель может быть синтезирована, что позволяет использовать ее для прототипирования сетей на кристалле.



Размещено на Allbest.ru

...