Выбор архитектуры локальной сети при проектировании систем реального времени | Статья в журнале «Молодой ученый»

Отправьте статью сегодня! Журнал выйдет 28 декабря, печатный экземпляр отправим 1 января.

Опубликовать статью в журнале

Авторы: ,

Рубрика: Технические науки

Опубликовано в Молодой учёный №21 (80) декабрь-2 2014 г.

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

Статья просмотрена: 520 раз

Библиографическое описание:

Погребной, А. В. Выбор архитектуры локальной сети при проектировании систем реального времени / А. В. Погребной, Д. В. Погребной. — Текст : непосредственный // Молодой ученый. — 2014. — № 21 (80). — С. 195-201. — URL: https://moluch.ru/archive/80/14283/ (дата обращения: 16.12.2024).

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

 

Введение

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

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

Постановка задачи

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

-          число станций [1], объединить в сеть;

-          информационный граф программной нагрузки, в котором определены объемы данных, передаваемых между модулями позициями за один цикл моделирования [2];

-          распределение модулей и позиций по станциям, т. е. в информационном графе выделены дуги, требующие сетевой ресурс [3];

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

Информационный граф  является двудольным взвешенным графом, где D — множество вершин данных  с указанием для каждого  размера требуемой памяти ; F — множество вершин модулей  с указанием для каждого  величины потребляемого процессорного времени ;  — матрица объемов данных, передаваемых между вершинами графа G.

На графе G заданно разрезание [3] на множество подграфов  Число подграфов n соответствует числу станций вычислительной системы. Вершины подграфа Gi по требуемой памяти Pq и процессорному времени Tm суммарно не превышают ресурсы станции si по памяти P(si) и процессорному времени T(si). Величина T(si) равна числу временных тактов, которые процессор станции si может выделить для выполнения модулей подграфа Gi за один цикл моделирования.

Разрезанию {Gi} соответствует множество С ребер графа G, , где сij — множество ребер, связывающих между собой подграфы Gi и Gj. Каждому ребру cqm, связывающему вершину dq и fm в графе G, соответствует элемент rqm матрицы R. Поэтому объем данных, передаваемых в сети между станциями si и sj можно определить величиной rij,

.                                                                                                                  (1)

Таким образом, общий объем передаваемых по сети данных за один цикл моделирования для разрезания {Gi} составит величину r,

.                                                                                                                       (2)

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

.                                                                                                                 (3)

Здесь  — число временных тактов в одном цикле моделирования; kφ — коэффициент, учитывающий факторы снижения значения φ в реальной сети.

Очевидно, что решить проблему своевременной передачи данных в сети путем увеличения числа μ нельзя, так как величина r также зависит от μ. Поэтому, если условие (3) не выполняется, то это означает, что сеть на одной магистрали с параметром  не работоспособна и необходимо принятие решений по уменьшению величины r или увеличению значения параметра φ. Среди таких решений могут быть следующие:

-       найти другое разрезание с более низким значением r;

-       увеличение пропускной способности магистрали;

-       изменить архитектуру сети.

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

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

Анализ базовых вариантов сетей

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

Рис. 1. Примеры базовых сетей и диаграмм загрузки магистралей

 

А также для каждой из архитектур построим диаграмму, которая показывает возможную загрузку магистралей сети при передаче данных между станциями. При этом предполагается, что к каждой магистрали подключается не менее двух станций, а передачи данных осуществляются как между станциями одной магистрали, так и между станциями разных магистралей. Длины отрезков, отражающих суммарные объемы передач данных в сети, выполняемые в разные моменты времени за один цикл моделирования, принимаются произвольными и измеряются числом тактов моделирования затрачиваемых для передачи соответствующих объемов данных. Над каждым отрезком указан перечень магистралей, принимающих участие в передаче данных. Например, запись 1–4-2 над отрезками диаграммы (рис. 1, г) обозначает загрузку магистралей М1, М4, М2 при передаче данных между станциями, подключенными к магистралям М1 и М2. Здесь имеется в виду, что например для варианта сети на рис. 1, г в отрезок 1–4-2 будут собраны все передачи, выполняемые между станциями С3 и С7, С4 и С6, С4 и С7, С5 и С7 в разные моменты времени в интервале одного цикла моделирования. Заметим также, что параллельно с этой передачей могут передаваться данные между станциями, подключенными к магистрали М3, то есть отрезок 3 на диаграмме рис. 1, г, может размещаться параллельно отрезкам 1–4-2.

Анализ приведенных на рис. 1 базовых сетей по соответствующим диаграммам позволяет сделать ряд выводов. В сети (а) станции желательно подключать к магистралям М1 и М2 так, чтобы отрезки 1 и 2 были примерно равны, а отрезок 1–2 был минимальной длины. Для сети (б) критичной по загрузке является магистраль М2. В сети (в) такими магистралями являются М2 и М3, а в сети (г) магистраль М4. Для данных сетей наилучшим вариантом подключения станций к магистралям будет такой вариант, который обеспечивает равную и минимальную загрузку магистралей. Например, для сети (б) условие равенства загрузки магистралей можно записать в виде: [1]+ [1–2]= [2]+ [1–2]+ [2–3]= [3]+ [2–3]. Здесь квадратные скобки обозначают длину соответствующих отрезков. Аналогичные условия равенства загрузки магистралей можно записать для сетей (в) и (г). Минимально возможная загрузка магистралей достигается в случае, если подключение станций к магистралям удается выполнить таким образом, что между станциями, подключенными к разным магистралям, данные не передаются.

Метод решения задачи построения сети

При изложении метода решения задачи выбора базовой сети и варианта подключения станций к магистралям будем придерживаться примера информационного графа, представленного на рис. 2. Количеству станций равному 6. Кружками здесь показаны данные dq, а планками — модули fm. У каждого ребра, связывающего вершины dq и fm проставлены веса rqm, равные объему данных, передаваемых между вершинами dq и fm за один цикл моделирования [2]. Пунктирными линиями выделены подграфы разрезания и указаны номера станций, ресурсы которых занимают данные подграфы.

Пусть пропускная способность магистралей составляет 10 единиц объемов передаваемых данных за 1 такт, то есть величина =10, коэффициент kφ=1,3, а цикл моделирования μ равен 12 тактам. Тогда для принятого варианта распределения модулей и данных по станциям можно определить ориентировочное число магистралей сети. Для этого на основе матрицы R согласно (2) вычисляем общий объем данных r, передаваемых между станциями. Для нашего примера r=198 единиц. Время на передачу данных составит  тактов, что превышает цикл моделирования более чем в 2 раза. Таким образом, определяем, что в сети должно быть не менее трех магистралей. В данном случае при условии, что к магистрали подключается не менее 2-х станций, фактически выбирать более 3 магистралей не имеет смысла.

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

 

Рис. 2. Пример информационного графа

 

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

-        строится граф передачи данных между станциями сети;

-        выполняется разрезание графа передач данных на минимально связанные подграфы;

-        выбирается вариант подключения станций к магистралям сети;

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

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

Граф передачи данных P=(S,Z,R) строится на основе варианта распределения модулей и данных графа G по станциям и матрицы весов . Вершина  графа P соответствует станции si, на которую распределены модули и данные подграфа Gi разрезания {Gi}. Наличие ребра  соответствует тому, что подграфы Gi и Gj связаны между собой ребрами графа передач данных , то есть . Каждому ребру  графа P ставится в соответствие величина rij, которая вычисляется по выражению (1) и определяет объем данных, передаваемых между станциями  и  за один цикл моделирования.

Пример графа P, построенного для разрезания, показанного на рис. 2, представлен на рис. 3. Граф P содержит 6 вершин , по числу станций. Вариант разрезания графа на три его подграфа на рис. 3 выделен пунктирными линиями. К каждой магистрали следует подключать не менее двух станций. Поэтому в данном примере на каждую магистраль приходится подграф, содержащий 2 станции.

Рис. 3. Граф передачи данных P

 

Веса rij ребер zij, представленные на рис. 3, получены по выражению (4) и в сумме составляют 198 единиц.

Построение матрицы наличия конфликтов Q осуществляется на основе графа P и варианта подключения станций к магистралям выбранной базовой сети. Методику построения матрицы Q покажем на рассматриваемом примере. В качестве базовой структуры сети выберем вариант с тремя магистралями, представленный на рис. 1, б. На рис. 4, а, показан один из вариантов подключения станций к магистралям данной сети.

Рис. 4. Вариант архитектуры сети и матрица наличия конфликтов: а) вариант подключения станций к базовой сети; б) матрица наличия конфликтов Q

 

Размерность матрицы Q определяется числом ребер графа P. Множество ребер  графа P обозначим соответствующими кодовыми номерами, сохранив в них номера станций. Получим множество кодовых номеров ребер (13, 14, 23, 24, 35, 36, 45, 56) и, соответственно, номеров строк и столбцов матрицы Q. Так, например, номер ребра 24, означает наличие передач данных между станциями 2 и 4 с объемом  единиц. Элемент  матрицы наличия конфликтов  определяется следующим образом:  если пары станций ребер v и k при передачи данных в сети (рис. 4, а) имеют конфликт по доступу к магистрали и  в противном случае.

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

В матрице Q на рис. 4, б, строки и столбцы 35, 36 выделены. Они отличаются тем, что у них все элементы , . Это означает, что при передаче данных между соответствующими станциями, например, для строки 35 — это станции s3 и s5, заняты все три магистрали и параллельно с парой s3, s5 не могут выполняться передачи данных между станциями во всех других парах. Поэтому выделенные строки и столбцы могут быть исключены из матрицы Q.

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

Рис. 5. Построение диаграммы передач данных: а — граф Q; б — диаграмма совмещения передач данных; в, г, д — преобразования графа Q при построении диаграммы

 

Для построения диаграммы в графе Q последовательно выделяются максимальные пустые подграфы [3] и объемы передач соответствующих вершин совмещаются на диаграмме (рис. 5, б). Так, на первой стадии выделяется максимальный пустой подграф, например, с вершинами 13, 56, 24 и соответствующие объемы 40, 54 и 42 единицы могут передаваться в сети параллельно и, следовательно, на диаграмме они совмещаются. Вершины с минимальным объемом передач данных исключаются из графа Q. В данном случае это вершина 13, а вершины 56' и 24' сохраняются в графе с новыми объемами 14 и 2 единицы (рис. 5, в) и помечаются штрихами. При формировании следующего максимального пустого подграфа вершины, помеченные штрихами, выбираются в первую очередь. Для графа на рис. 5, в, выбираются вершины 56' и 24'. Вершина 24' исключается, и процесс продолжается для графа на рис. 5, г. Здесь выбираются вершины 56" и 14. Вершина 14 исключается, а для графа на рис. 5, д, максимальный пустой подграф включает вершины 56" и 23. Обе они последовательно исключаются из графа и оставшаяся вершина 45 отражается на диаграмме.

Заметим, что при построении диаграммы (рис. 5, б) объемы передаваемых данных для каждой вершины графа отражаются на всех магистралях, участвующих в передаче этих данных. Построение диаграммы завершается отражением объемов передач для вершин 35 и 36, помеченных в матрице Q и не вошедших в граф Q.

Из диаграммы следует, что суммарный объем передач данных в сети с учетом их совмещения составляет 104 единицы или  временных тактов, что укладывается в цикл моделирования 12 тактов. Однако при этом коэффициент kφ достигает лишь величины 1,15. Общий объем передач данных согласно графа P составляет 198 единиц. Таким образом, для выбранной локальной сети и варианта подключения станций, представленного на рис. 4, а, последовательная цепь передач данных за счет использования параллельных передач сокращается с 198 до 104 единиц. Соответственно сокращается время передач с 19,8 до 10,4 тактов. Оценивая сокращение времени передач, следует иметь в виду, что выигрыш в 9,4 такта несколько сокращается на величину задержек в адаптерах, связывающих магистрали в сети.

Заключение

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

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

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

 

Литература:

 

1.                Погребной А. В. Определение числа и топологии размещения станций многопроцессорной вычислительной системы // Известия Томского политехнического университета. — 2006. — Т. 309. — № 7. — С. 160–164.

2.                Погребной А. В. Определение объемов передач данных в сети вычислительной системы для заданной модели программной нагрузки // Известия Томского политехнического университета. — 2007. — Т. 310. — № 3. — С. 103–107.

3.                Кристофидес Н. Теория графов. Алгоритмический подход. — М.: Мир, 1978. — 432 с.

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


Похожие статьи

Облик перспективной навигационной системы для подвижного наземного объекта

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

Алгоритмы оптимальной структуры компьютерной сети

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

Синтез структуры мультисервисной сети на базе генетических алгоритмов

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

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

В статье рассмотрен математический алгоритм создания цифровой топологической модели железнодорожной станции в рабочем окне программы ИСУЖТ. Математический алгоритм построен на основе теории множеств, а также представлен пример отображения подмножеств...

Применение автомата Мура для решения элементарных логических задач

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

Задача распознавания речи и выбор оптимального сервиса для использования в программно-аппаратном комплексе «Умное зеркало»

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

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

В данной статье описывается создание web-сервиса для проверки уровня безопасности построенного маршрута. Метод анализа построенного маршрута для водителя и пешехода представлен на конференции «Технические науки: проблемы и перспективы» [1].

Формирование облика навигационной системы для подвижного наземного объекта

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

Алгоритмы балансировки в сети OSPF

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

Инжиниринг трафика в программно определяемых сетях

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

Похожие статьи

Облик перспективной навигационной системы для подвижного наземного объекта

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

Алгоритмы оптимальной структуры компьютерной сети

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

Синтез структуры мультисервисной сети на базе генетических алгоритмов

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

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

В статье рассмотрен математический алгоритм создания цифровой топологической модели железнодорожной станции в рабочем окне программы ИСУЖТ. Математический алгоритм построен на основе теории множеств, а также представлен пример отображения подмножеств...

Применение автомата Мура для решения элементарных логических задач

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

Задача распознавания речи и выбор оптимального сервиса для использования в программно-аппаратном комплексе «Умное зеркало»

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

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

В данной статье описывается создание web-сервиса для проверки уровня безопасности построенного маршрута. Метод анализа построенного маршрута для водителя и пешехода представлен на конференции «Технические науки: проблемы и перспективы» [1].

Формирование облика навигационной системы для подвижного наземного объекта

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

Алгоритмы балансировки в сети OSPF

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

Инжиниринг трафика в программно определяемых сетях

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

Задать вопрос