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