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

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

1

1

АННОТАЦИЯ

сеть кристалл маршрутизация

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

Объем работы: 33666 символов с пробелами, 39 страниц.

Количество иллюстраций: 29; таблиц:7.

Количество использованных источников: 15.

ВВЕДЕНИЕ

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

Актуальность

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

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

Для достижения поставленной цели решены следующие задачи:

- проведен обзор и анализ предметной области и существующих решений в области моделирования сетей на кристалле;

- разработаны алгоритмы построения таблиц связей и маршрутизации для топологий mesh, torus и circulant;

- реализована высокоуровневая модель на Java;

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

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

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

Объекты исследования

Дадим определение основным терминам, используемым в данной работе.

Сеть на кристалле

Сетью на кристалле (СтнК) можно назвать подход для создания эффективных многопроцессорных решений. Он заключается в создании распределительной среды для обмена пакетами данных с единым интерфейсом для подключения различных элементов. Компоненты сети (Рис. 1) - это интерфейсы (rni) между сетью и ресурсами (Resource), каналы и коммутаторы (S) [1].

Рисунок 1 – СтнК из 16 узлов.

Ресурсами называются различные системы, внедренные в данную архитектуру [2]. Коммутаторы маршрутизируют и буферизуют пакеты, передаваемые между роутерами.

Типы топологий

Топология является одним из ключевых свойств сети на кристалле. Основными характеристиками топологии являются [3]:

- количество вершин-роутеров;

- количество физических соединений между роутерами;

- количество ребер, исходящих из нее;

- диаметр графа - максимум среди минимальных расстояний между любыми двумя вершинами;

- среднее расстояние среди наиболее коротких путей между всеми узлами графа.

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

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

Наиболее распространенной [3] регулярной топологией является сетчатая топология (mesh), представляющая собой сеть из mЧn узлов, каждый из которых соединен с четырьмя соседними (Рис. 2). Крайние узлы имеют незадействованные порты. Главным недостатком этой топологии является слишком большой диаметр. Попыткой устранить его за счет больших ресурсных затрат является топология torus (Рис. 3), полученная путем соединения крайних узлов сетки с противоположными.

Рисунок 2 – Топология mesh.	Рисунок 3 – Топология torus.

Еще одной распространенной топологией является circulant (Рис. 4). Циркулянтом называется неориентированный граф с множеством вершин, где каждая вершина соединена с другими вершинами с шагами k1, k2 … kn, где n - количество шагов.

В статье [6] показано, что диаметр топологии circulant при оптимальных параметрах примерно в 2 раза меньше диаметра оптимальной топологии torus.

Рисунок 4 – Топология circulant.

Таблицы соединений и маршрутизации

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

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

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

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

1.2 Обзор существующих моделей

Для моделирования сетей на кристалле используются два подхода: на языках описания аппаратуры и языках высокого уровня. Несмотря на то, что симуляторы, разработанные на языках аппаратуры по природе своей являются более точными моделями, которые фактически представляют собой сеть, они имеют недостаток в виде продолжительного по времени моделирования. У высокоуровневых моделей среднее время симуляции значительно меньше. Рассмотрим в рамках этого раздела несколько уже реализованных моделей на высокоуровневом языке программирования Java.

Модель OCNS

В работе [8] описывается алгоритм и особенности работы симулятора OCNS (On Сhip Network Simulator). Взаимодействие между IP-блоками основывается на сетевой модели OSI. Принцип передачи пакетов и соответствие уровней представлено на рисунке (Рис. 5).

Рисунок 5 – Сопоставление архитектуры OCNS с OSI [8].

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

Рисунок 6 – Модель СтнК на уровне роутера [8].

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

Модель gpNoCsim

В статье [9] приведено описание модели (Рис. 7) для симуляций сетей (gpNoCsim).

Рисунок 7 – Блок-схема симулятора gpNoCsim.

Авторы демонстрируют преимущества модульной архитектуры сети на кристалле, которая была достигнута благодаря возможностям Java. Симулятор поддерживает проектирование СтнК с различными топологиями, такими как butterfly fat tree, mesh, torus. Приведено описание алгоритма того, как проводить моделирование новой архитектуры сети с помощью изменения входных параметров симулятора. Описание конкретной топологии осуществляется в текстовый файле конфигураций. Затем, полученные из файла значения обрабатываются симулятором и на их основе формируется архитектура сети.

Недостатком gpNoCsim, как и OCNS, является то, что текстовый файл конфигураций пользователю приходится предварительно формировать вручную.

1.3 Выводы к главе 1

В результате проводимого обзора существующих решений есть много высокоуровневых моделей, способных симулировать СтнК с различными топологиями, но для всех них формирование конфигурационных файлов должно происходить отдельно. В случае, когда нужно произвести большое количество запусков моделирования, возникает необходимость в использовании отдельной программы-генератора топологий, или того хуже, в ручном формировании xml файла. Поэтому в рамках данной работы основное внимание направлено на разработку генератора распространенных топологий, таких как mesh, torus и circulant, с помощью которого, при использовании его совместимо с симулятором OCNS, получается универсальная высокоуровневая модель для симуляции СтнК с различными топологиями.

2. Обзор инструментов и методов решения

2.1 Обзор алгоритмов построения таблиц маршрутизации

Как было указано ранее, эффективность сети на кристалле зависит от используемого алгоритма маршрутизации. Рассмотрим несколько распространенных реализаций алгоритмов маршрутизации.

Алгоритм XY

XY-маршрутизация - это маршрутизация, при которой пакеты перемещаются сначала в горизонтальном направлении, а затем в вертикальном направлении к получателю [7]. XY-маршрутизация хорошо подходит для сетей с топологиями mesh или torus. В таких сетях адреса роутеров - это их координаты xy (Рис. 8).

Рисунок 8 – Передача пакета из роутера А в роутер В [7].

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

Алгоритм Surrounding XY

Маршрутизация Surrounding XY (S-XY) имеет три различных режима маршрутизации. Режим N-XY (обычный XY) работает так же, как базовая маршрутизация XY. Пакеты сначала передаются вдоль оси x, а затем вдоль оси y. Маршрутизация остается в режиме N-XY, пока сеть не заблокирована. Режим SH-XY (объемный горизонтальный XY) используется, когда левый или правый сосед маршрутизатора занят. Соответственно, третий режим SV-XY (объемное вертикальное XY) используется, когда верхний или нижний сосед роутера занят. Режим SH-XY направляет пакеты в нужный столбец на основе координат пункта назначения. Алгоритм позволяет пакетам обходить неактивные маршрутизаторы по кратчайшему пути. Работа в режимах SH-XY и SV-XY показана на рисунке 9.

Рисунок 9 – Маршрутизация Surrounding XY в режимах SH-XY и SV-XY [7].

Маршрутизаторы в режимах SH-XY и SV-XY добавляют к пакетам небольшой идентификатор, который сообщает другим маршрутизаторам, что эти пакеты маршрутизируются с использованием SH-XY или SV-XY режимов. Таким образом, другие маршрутизаторы не отправляют пакеты назад. Окружающая XY-маршрутизация используется в DyNoC. Это метод, который поддерживает связь между модулями, которые динамически размещаются на устройстве [10].

Алгоритм Дейкстры

Алгоритм Дейкстры представляет собой алгоритм поиска кратчайшего пути в ориентированном взвешенном графе G=(V,E) между заданной вершиной и всеми остальными вершинами графа.

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

Псевдокод алгоритма Дейкстры приведен на рисунке 10.

Рисунок 10 – Псевдокод алгоритма Дейкстры.

Этот алгоритм может быть использован для любой топологии.

Алгоритм A*

Алгоритм A* является одним из наиболее известных алгоритмов планирования пути, который может применяться в метрической или топологической конфигурации пространства [12]. Этот алгоритм использует комбинацию эвристического поиска и поиска по кратчайшему пути. Алгоритм A* определяется как алгоритм «best-first», потому что каждая ячейка в пространстве конфигурации оценивается значением: f(v)= h(v) + g(v)

Где h (v) - эвристическое расстояние ячейки до целевого состояния, а g (v) - длина пути от исходного состояния до целевого состояния через выбранную последовательность ячеек. Последовательность заканчивается в оцененной ячейке. Каждая смежная ячейка для достигнутой ячейки оценивается значением f (v). Ячейка с наименьшим значением f (v) выбрана следующей в последовательности. [13].

2.2 Обоснование выбора языка программирования

Исходный код симулятора OCNS [8] разработан на высокоуровневом языке программирования Java, поэтому внедряемый генератор топологий также реализован на языке Java. Стоит отметить, что сам по себе язык Java имеет ряд преимуществ. Он поддерживает возможности объектно-ориентированного программирования, а также кроссплатформенность [14]. По сравнению с многими другими высокоуровневыми языками программирования Java имеет высокую производительность [15], что показано на рисунке 11.

Рисунок 11 – Сравнение производительности языков программирования [15].

2.3 Выводы к главе 2

Исходя из обзора возможных способов решения были использованы следующие методы и инструменты:

1. Одним из наиболее распространенных алгоритмов маршрутизации для mesh является алгоритм XY. Этот алгоритм простой в реализации, и для сети, которая является статической, подойдет как нельзя лучше. На его основе для топологии mesh можно разработать алгоритм построения таблицы маршрутизации для топологии torus. Его особенностью является то, что для топологии torus есть необходимость в разработке логики нахождения минимального пути по третьему измерению, в отличие от двумерной сетки.

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

3. Разработка программного обеспечения

3.1 Описание разработанного решения

В исходный код OCNS [8] был отдельно добавлен пакет с классами следующей структуры (Рис. 12):

Рисунок 12 – Uml диаграмма структуры классов генератора.

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

Чтобы html файл можно было проанализировать, разработан парсер html на языке программирования Python.

Входные параметры программы определяются следующими шаблонами:

- Mesh количество_столбцов количество_строк;

- Torus количество_столбцов количество_строк;

- Circulant количество_узлов шаг1 шаг1;

- CirculantOpt количество_узлов.

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

Было принято, что для «сетчатых» топологий нумерация портов происходит против часовой стрелки, как показано на рисунке 13, а для топологии двухмерный circulant - по часовой (Рис. 14).

Рисунок 13 – Нумерация портов для mesh и torus.	Рисунок 14 – Нумерация портов для circulant.

Топология mesh

Алгоритм таблицы соединений. Таблица связей представляется в виде матрицы размерностью m на n, где n - кол-во строк, а m - кол-во столбцов матрицы. В такой топологии маршрутизаторы условно можно разделить на несколько категорий (Рис. 15) по количеству задействованных портов:

Рисунок 15 – Разбиение портов по категориям.

3. Угловые (отмечены синим цветом). Имеют 2 “активных” порта, дополнительно делятся по расположению:

- верхний левый;

- верхний правый;

- нижний левый;

- нижний правый.

4. Боковые (отмечены желтым цветом): имеют 3 “активных” порта, дополнительно делятся по расположению:

- левые;

- верхние;

- правые;

- нижние.

5. Средние (отмечены оранжевым цветом): все порты “активные”.

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

- [ а ], где а - вычисляемый номер роутера, соединенного с заданным узлом;

- id - идентификатор текущего узла;

- общая формула узлов для Боковых строится по шаблону:

- (левая_граница : правая_граница : шаг), то есть поиск номера узла производится между левой и правой границей (границы не включаются) с определенным шагом.

Исходя из вышеперечисленных формул можно составить алгоритм для построения таблицы связей для mesh-топологии.

Формулировка в общем виде: мы проходимся один раз по всем узлам (id - переменная цикла от 0 до размеров матрицы) и сравниваем номер каждого узла с Общей формулой угловых и боковых узлов. Если идентификатор вошел в список вышеперечисленных категорий, то для элемента матрицы связей с индексами [id][№ порта] присваивается соответствующее значение из формул связей. Если id не вошел в категории Угловых и Боковых роутеров, то по условию else ему “присваивается” категория Средние и, как описано ранее, соответствующему элементу присваивается соответствующее соединение. Номер порта порта определяется по следующему правилу (Таблица 1):

Таблица 1 – Алгоритм нахождения индексов матрицы соединений.

№ порта	Индекс связанного порта
0	id- 1
1	id + m
2	id + 1
3	id - m

Таблица 2 – Формулы инициализации для узлов топологии mesh.

Категория	Угловые
Подкатегория	Левый верхний	Правый верхний	Левый нижний	Правый нижний
Общая формула узла	0	m - 1	m(n-1)	mn - 1
Формулы связей	[ id + 1 ] [ id + m ]	[ id - 1 ] [ id + m ]	[ id - m ] [ id + 1 ]	[ id - 1 ] [ id - m ]
Категория	Боковые
Подкатегория	Левые	Верхние	Правые	Нижние
Общая формула узлов	(0 : m(n-1) : m)	(0 : m-1 : 1)	(m - 1 : mn-1 : m)	(m(n-1) : m(n-1) : 1)
Формулы связей	[ id - m ] [ id + 1 ] [ id + m ]	[ id - 1 ] [ id + 1 ] [ id + m ]	[ id - 1 ] [ id - m ] [ id + m ]	[ id - 1 ] [ id + 1 ] [ id - m ]
Категория	Средние
Формулы связей	[ id - m ] [ id + 1 ] [ id - 1 ] [ id + m ]

Алгоритм таблицы маршрутизации. В общем виде формулировка реализованного алгоритма выглядит следующим образом. В случае, если индекс отправляющего узла равен индексу принимающего, выбирается порт 4. Иначе происходит поиск нужного порта. Для отправки пакета по вертикали требуется узнать номера строк, в которых находятся узлы. Они получаются делением номера узла на длину строки m. Если номер строки отправляющего роутера больше номера принимающего, то выбирается порт 1, если меньше - порт 3. Если узлы находятся в одной строке, то сравниваются их номера, и при направлении в сторону большего индекса выбирается порт 0, а в сторону меньшего - порт 2.

Топология torus

Алгоритм таблицы соединений. Как и топология mesh, топология torus может быть как квадратной, так и прямоугольной. Структура этих топологий очень схожа, поэтому алгоритм строится на основе имеющегося для Mesh. В нем используются те же категории, но с учетом того, что у Угловых и Боковых роутеров теперь задействованы все порты. Формулы, объявленные для активных портов в топологии Mesh, не поменяются. Таким образом, необходимо выявить зависимость для портов, которые были «неактивными» для mesh. В таблице 3 отражены дополнения к данным таблицы 2.

Таблица 3 – Дополненные формулы для узлов топологии torus.

Категория	Угловые
Подкатегория	Левый верхний	Правый верхний	Левый нижний	Правый нижний
Формулы связей	[ id + m*(n - 1) ] [ id + (m - 1) ]	[ id + m*(n - 1) ] [ id - (m - 1) ]	[ id + (m - 1) ] [ id - m*(n - 1) ]	[ id- (m - 1) ] [ id - m*(n - 1) ]
Категория	Боковые
Подкатегория	Левые	Верхние	Правые	Нижние
Формулы связей	[ id + (m - 1) ]	[ id + m*(n - 1) ]	[ id - (m - 1) ]	[ id - m*(n - 1) ]

Номер порта определяется по следующему правилу (Таблица 4):

Таблица 4 – Алгоритм нахождения индексов матрицы соединений.

№ порта	Индекс связанного порта
0	id+ (m - 1)
1	id - m*(n - 1)
2	id - (m - 1)
3	id

Алгоритм таблицы маршрутизации. Общая суть алгоритма построения таблицы маршрутизации такая же, как и у топологии mesh, но добавляется логика для поиска минимального расстояния между столбцами и строками, где находятся начальный и конечный роутеры. В общем виде алгоритм направленного поиска выглядит следующим образом: происходит сравнение строк, в которых находятся отправляющий и принимающий пакеты маршрутизаторы. Если источник и приемник находятся в одной строке, то рассчитываются расстояния между маршрутизаторами в оба направления и по наименьшему значению модуля расстояния выбирается по какому из портов двигаться: по 0-му или 2-му. Если строки отправляющего и принимающего роутеров различны, передача пакетов происходит через порты 1 или 3, и проводится аналогичное сравнение столбцов заданных маршрутизаторов.

Топология двухмерный circulant

Алгоритм таблицы соединений. Особенность этой топологии в том, что топология двухмерный circulant задается количеством узлов k и шагов s1, s2. Для данного типа топологии существует оптимальный граф [6]. Предельно оптимальный граф гарантирует достижение минимумов максимальной и средней структурных задержек. Для этого графа существуют формулы нахождения шагов s1, s2. Так как одна из основных задач при инициализации таблиц связей и маршрутизации в том, чтобы пакеты передавались максимально быстро и с наименьшими потерями, то применение предельно оптимального графа способствует этой концепции.

Проще и экономичнее по ресурсам проходить по циклу, где в каждой итерации происходит установка значений только для двух портов (0 и 1) текущего узла и по одному порту (2 и 3) у соответствующе связанных с текущим узлов. 0-й порт всегда соединяется с 3_м, а 1й порт - со 2_м.

Общая формула для вычисления значений связанных узлов по 0_му и 1_му портам выглядит так:

- 0-й: id+s1 = A;

- 1-й: id+s2 = В.

Для связанных узлов (с индексами [А][3] и [B][2]) задается значение связанного узла, как id. Для идентификаторов, чья сумма с шагами превышает k-1, устанавливаются другие формулы расчета значений связанных роутеров для соответствующих портов:

- 0-й: А - k;

- 1-й: В - k.

Алгоритм таблицы маршрутизации. Для данной топологии был программно реализован алгоритм Дейкстры. На вход основного метода алгоритма подается матрица смежности, формируемая исходя из таблицы соединений, и номер каждого узла (переменная цикла). Результатом является список узлов, для каждого из которых вычислен кратчайший путь (список вершин). Для каждого узла, используя первую пару значений кратчайшего пути и таблицу соединений, вычисляется порт, по которому нужно двигаться, чтобы достичь текущую вершину. Значение порта записывается в таблицу маршрутизации с индексами [текущий_узел][каждый_узел].

3.2 Полученные результаты

В итоге разработки алгоритмов построения таблиц соединений (Netlist) и маршрутизации (Routing) были получены следующие результаты (Таблица 5, 6, 7).

Таблица 5 – Сгенерированные таблицы связей для различных топологий.

Топология	mesh (3, 4)	torus (3, 4)	Circulant (12, 2, 3)
Netlist	-1 4 1 -1 0 5 2 -1 1 6 3 -1 2 7 -1 -1 -1 8 5 0 4 9 6 1 5 10 7 2 6 11 -1 3 -1 -1 9 4 8 -1 10 5 9 -1 11 6 10 -1 -1 7	3 4 1 8 0 5 2 9 1 6 3 10 2 7 0 11 7 8 5 0 4 9 1 6 5 10 7 2 6 11 4 3 11 0 9 4 8 1 10 5 9 2 11 6 10 3 8 7	2 3 9 10 3 4 10 11 4 5 11 0 5 6 0 1 6 7 1 2 7 8 2 3 8 9 3 4 9 10 4 5 10 11 5 6 11 0 6 7 0 1 7 8 1 2 8 9

Таблица 6 – Сгенерированные таблицы маршрутизации для топологий mesh и torus.

Топология	mesh (3, 4)	torus (3, 4)
Routing	4 2 2 2 1 1 1 1 1 1 1 1 0 4 2 2 1 1 1 1 1 1 1 1 0 0 4 2 1 1 1 1 1 1 1 1 0 0 0 4 1 1 1 1 1 1 1 1 3 3 3 3 4 2 2 2 1 1 1 1 3 3 3 3 0 4 2 2 1 1 1 1 3 3 3 3 0 0 4 2 1 1 1 1 3 3 3 3 0 0 0 4 1 1 1 1 3 3 3 3 3 3 3 3 4 2 2 2 3 3 3 3 3 3 3 3 0 4 2 2 3 3 3 3 3 3 3 3 0 0 4 2 3 3 3 3 3 3 3 3 0 0 0 4	4 2 0 0 1 1 1 1 3 3 3 3 0 4 2 0 1 1 1 1 3 3 3 3 2 0 4 2 1 1 1 1 3 3 3 3 2 2 0 4 1 1 1 1 3 3 3 3 3 3 3 3 4 2 0 0 1 1 1 1 3 3 3 3 0 4 2 0 1 1 1 1 3 3 3 3 2 0 4 2 1 1 1 1 3 3 3 3 2 2 0 4 1 1 1 1 1 1 1 1 3 3 3 3 4 2 0 0 1 1 1 1 3 3 3 3 0 4 2 0 1 1 1 1 3 3 3 3 2 0 4 2 1 1 1 1 3 3 3 3 2 2 0 4

Таблица 7 – Сгенерированные таблицы маршрутизации для топологии circulant.

Топология	circulant (12, 2, 3)
Routing	4 1 0 1 0 0 1 2 3 2 3 0 0 4 1 0 1 0 0 1 2 3 2 3 3 0 4 3 0 1 0 0 1 3 3 2 2 3 2 4 3 0 1 0 0 2 2 3 3 2 3 2 4 3 0 1 0 0 2 2 2 3 2 3 2 4 3 0 1 0 0 2 2 2 3 2 3 2 4 3 0 1 0 0 0 2 2 3 2 3 2 4 3 0 1 0 0 0 2 2 3 2 3 2 4 3 0 1 1 0 1 1 2 3 2 3 2 4 1 0 0 1 0 0 1 2 3 2 3 0 4 1 1 0 1 0 0 1 2 3 2 3 0 4

Для проведения сравнительного анализа производительности сетей с различными топологиями были проведены симуляции СтнК на основе реализованных алгоритмов. Сначала сравнивается работа неоптимальной (25, 3, 7) и предельно оптимальной (25, 3, 4) топологий circulant (Рис. 16).

Рисунок 16 – Время доставки пакета от среднего периода генерации пакетов

В соответствии с диаграммой, время доставки пакета у оптимальной топологии circulant меньше, чем у неоптимальной, из чего можно сделать вывод, что предельно оптимальный circulant работает производительнее неоптимального. В связи с этим выводом в дальнейших сравнениях будет использоваться circulant оптимального типа. Также стоит отметить остановку моделирования у неоптимальной топологии circulant. Данное явление происходит за счет того, что сеть входит в, так называемый, dead-lock. Иными словами, сеть перестает как-либо функционировать, и задержка сети стремится к бесконечности. Такое явление можно наблюдать для всех, рассматриваемых в данной работе, топологий

Для определения формы топологии (квадрат/прямоугольник) с минимальным временем доставки пакетов для топологий mesh и torus производится моделирование с параметрами: 2x32, 4x16, 8x8. Общее количество узлов остается неизменным и равняется 64-ем. На рисунке 17 и рисунке 18 показаны итоги моделирования.

Рисунок 17 – Время доставки пакета от среднего периода генерации пакетов (mesh).

Рисунок 18 – Время доставки пакета от среднего периода генерации пакетов (torus).

Из приведенных диаграмм можно видеть закономерность, что чем меньше топология похожа на квадратную, тем выше время доставки пакета. Следующим шагом будет сравнение различных топологий между собой. Для этого используются torus и mesh с размерностями 5х10 и 7х7, двухмерный циркулянт с параметрами (49, 4, 5) и (50, 4, 5).

Для начала возьмем топологии с общим количеством узлов равным 50. На рисунке 19 приведено сравнения времени доставки пакета.

Рисунок 19 – Время доставки пакета от среднего периода генерации пакетов для различных топологий (50 узлов).

Как видно из графика, при данных параметрах, топология типа circulant является более производительной, чем mesh или torus. Для подробного рассмотрения разницы между torus и двухмерным циркулянтом на рисунке 20 приведен график без mesh. Также на рисунке 21 показан график разности времени передачи пакетов в процентах в зависимости от среднего периода генерации пакетов между torus и топологией двухмерный circulant.

Рисунок 20 – Время доставки пакета от среднего периода генерации пакетов для torus и circulant (50 узлов).



Рисунок 21 – Разности времени передачи пакетов в процентах от среднего периода генерации пакетов между torus и circulant (50 узлов).

Из рисунка 21 хорошо видно, что чем меньше средний период генерации пакетов, тем больше разница во времени передачи пакетов.

Далее сравним топологии с общим количеством узлов равным 49. На рисунках ниже представлены графики моделирования. Рисунки 23, 24, 25 приведены для более тщательного анализа между torus и circulant.

Рисунок 22 – Время доставки пакета от среднего периода генерации пакетов для различных топологий (49 узлов).

Рисунок 23 – Время доставки пакета от среднего периода генерации пакетов для torus и circulant (49 узлов).



Рисунок 24 – Ошибки генерации пакетов от среднего периода генерации пакетов для различных топологий (49 узлов).

Рисунок 25 – Пропускная способность сети от среднего периода генерации пакетов для torus и circulant (49 узлов).

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

Следующим шагом исследуется зависимость времени передачи пакета от количества узлов для всех трех топологий. Рассматриваемые количества узлов: 16, 25, 36, 49, 64. На рисунке 26 изображены кривые для топологии mesh, на рисунке 27 - torus, на рисунке 28 - circulant.



Рисунок 26 – Кривые времени доставки пакета от среднего периода генерации пакетов и количества узлов (mesh).

Рисунок 27 – Кривые времени доставки пакета от среднего периода генерации пакетов и количества узлов (torus).

Рисунок 28 – Кривые времени доставки пакета от среднего периода генерации пакетов и количества узлов (circulant).

Для torus и circulant производится сравнение времени доставки пакетов. Данное сравнение показано на рисунке 29.



Рисунок 29 – Разности времени передачи пакетов в процентах от среднего периода генерации пакетов между torus и circulant при разных количествах узлов.

Из рисунка 29 видно, что топология двухмерный circulant передает пакеты быстрее, чем torus вне зависимости от количества узлов и, чем меньше период генерации пакетов, тем существеннее разница.

Исходя из проведенного анализа можно сделать вывод, что топология circulant является более эффективной и производительной, чем топологии mesh и torus. Также стоит отметить, что топология circulant менее подвержена dead-lock, чем torus, что видно на рисунках 27 и 28.

Перспективы развития

В рамках данной работы была разработана модель, которая моделирует СтнК только с топологиями mesh, torus и circulant второго порядка, в связи с этим у текущего проекта имеются следующие перспективы развития:

- разработка алгоритмов маршрутизации и таблиц соединений для других регулярных топологий, к примеру, дерево или звезда;

- разработка алгоритмов построения таблиц соединений и маршрутизации для нерегулярных топологий;

- реализация оптимальных алгоритмов маршрутизации для реализованных топологий;

- внедрение поддержки многопоточности для ускорения моделирования;

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

ЗАКЛЮЧЕНИЕ

В рамках выполнения выпускной квалификационной работы были выполнены следующие задачи:

- проведен обзор и анализ существующих решений в области моделирования сетей на кристалле;

- разработан алгоритм построения таблиц связей для топологий mesh, torus, двухмерный circulant;

- создан алгоритм построения таблиц маршрутизации для топологий mesh, torus, двухмерный circulant;

- все алгоритмы реализованы на высокоуровневом языке программирования Java;

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

Разработаны и имплементированы алгоритмы построения таблиц связей и маршрутизации, что позволило на основе OCNS реализовать универсальную высокоуровневую модель СтнК с настраиваемой топологией. Проведено сравнительное моделирование СтнК с топологиями mesh, torus и двумерный circulant, в результате чего показано, что:

- СтнК с 50 узлами с топологией двухмерный circulant (50,4,5) на 20% быстрее передает пакеты, чем torus(5x10);

- Квадратная форма топологии у mesh и torus более производительна, чем прямоугольная;

- СтнК с топологией двухмерный circulant различным количеством узлов производительнее, чем torus и mesh;

- СтнК с топологией двухмерный circulant меньше подвержены dead-lock, чем torus.

СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ

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

...