ISSN 0236-235X (P)
ISSN 2311-2735 (E)

Публикационная активность

(сведения по итогам 2016 г.)
2-летний импакт-фактор РИНЦ: 0,493
2-летний импакт-фактор РИНЦ без самоцитирования: 0,389
Двухлетний импакт-фактор РИНЦ с учетом цитирования из всех
источников: 0,732
5-летний импакт-фактор РИНЦ: 0,364
5-летний импакт-фактор РИНЦ без самоцитирования: 0,303
Суммарное число цитирований журнала в РИНЦ: 5022
Пятилетний индекс Херфиндаля по цитирующим журналам: 355
Индекс Херфиндаля по организациям авторов: 499
Десятилетний индекс Хирша: 11
Место в общем рейтинге SCIENCE INDEX за 2016 год: 304
Место в рейтинге SCIENCE INDEX за 2016 год по тематике "Автоматика. Вычислительная техника": 11

Больше данных по публикационной активности нашего журнале за 2008-2016 гг. на сайте РИНЦ

Вход


Забыли пароль? / Регистрация

Добавить в закладки

Следующий номер на сайте

4
Ожидается:
16 Декабря 2017

Экспериментальная система моделирования «wormhole» сетей передачи данных

Статья опубликована в выпуске журнала № 1 за 2004 год.[ 21.03.2004 ]
Аннотация:
Abstract:
Авторы: Машечкин И.В. () - , , , Веселов Н.А. () - , ,
Ключевое слово:
Ключевое слово:
Количество просмотров: 8259
Версия для печати
Выпуск в формате PDF (1.96Мб)

Размер шрифта:       Шрифт:

В настоящей работе рассматриваются сети передачи данных, использующие технологию передачи wormhole [17]. Подобные сети находят широкое применение при построении высокопроизводительных вычислительных комплексов, сетей управления технологическими процессами в производстве, систем управления военными объектами и т.д. Основной особенностью указанного класса сетей является используемая в них технология передачи данных, которая состоит в том, что любая информация передается в виде пакетов данных, однако для передачи каждого пакета необходимо устанавливать отдельное монопольное соединение между отправителем и адресатом, после установки которого данные пакета копируются непосредственно из памяти узла-отправителя в память узла-адресата. Пакет как бы растягивается по промежуточным узлам сети, последовательно занимая каналы от отправителя к получателю так, что в любой момент времени, в любой точке присутствует только небольшая, неделимая единица данных – часть пакета, называемая в английской терминологии flit (flow-control-unit). Обязательным условием является то, что один и тот же путь не может использоваться больше чем одним пакетом, то есть если канал занят передачей, то пришедший вновь пакет блокируется и ожидает его освобождения. В случае блокировки передача пакета приостанавливается, но он не теряется и не освобождает уже занятых каналов сети. Движение пакета возобновляется после того, как соответствующий канал становится свободным. Пакет целиком хранится только в момент отправки в узле-отправителе и в момент получения в узле-адресате, поэтому далее в работе в ряде мест мы будем использовать термин «сети без промежуточной буферизации пакетов» для обозначения wormhole сетей.

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

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

·    задержки пакета – времени, которое пакет проводит в сети.

Емкость для любой конкретной сети представляется фиксированной величиной, и ее увеличение является задачей, лежащей в области разработки сетевого оборудования. Задержка пакета, хотя и зависит от емкости, но определяется также и множеством абонентов сети, создаваемой ими нагрузкой, используемыми путями передачи пакетов и т.д., то есть текущим состоянием сети. Очевидно, что задержка пакета есть случайная величина, поэтому целесообразно рассматривать среднюю задержку пакета, которая для любой конкретной сети с фиксированной емкостью является обобщенной характеристикой и в конечном итоге определяет пропускную способность системы. Таким образом, изучение средней задержки, способов ее расчета и оптимизации является важнейшей задачей для любой сети передачи данных [2,3].

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

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

Основные проблемы построения модели

Анализ существующих систем и методов моделирования сетей без промежуточной буферизации пакетов показывает, что к настоящему моменту не существует системы моделирования рассматриваемого класса сетей, которая обладает достаточной общностью, чтобы отразить работу любой сети данного класса, но при этом позволяет производить моделирование любого множества протоколов и архитектуры, используемых в той или иной реальной wormhole сети [8]. Причиной этого служит отсутствие, во-первых, модели данного класса сетей, отражающей особенности работы оконечных устройств, коммутаторов и каналов связи, а во-вторых, методов проверки адекватности и корректировки модели. Обе указанные проблемы возникают на определенных этапах построения модели [1].

Решение первой проблемы включает в себя выбор параметров модели и допущений о работе системы. Решение второй производится при помощи калибровки модели, которая представляет собой итеративный процесс сравнения модели с реальной системой, настройки модели или внесения изменений в модель, сравнение исправленной модели с реальной системой и т.д. [8]. Для проведения калибровки необходимо выбрать реальную систему. В качестве такой системы в настоящем исследовании будет использоваться типичный представитель рассматриваемого класса сетей – сеть Myrinet, созданная фирмой Myricom Inc., работающая под управлением сетевой оболочки GM, поставляемой той же фирмой вместе с исходными текстами.

Концептуальная модель системы

Концептуально система моделирования строится из следующих подсистем:

·    подсистемы коммутаторов и каналов связи (коммуникационная подсеть);

·    подсистемы оконечных устройств сети;

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

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

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

Структура системы моделирования

Для реализации изложенной выше концепции, модель сети строится из трех независимых подсистем, взаимодействие между которыми происходит через строго определенные интерфейсы. Для моделирования работы коммуникационной подсети используется модель, представляющая собой синтез одной из моделей организации передачи данных [6] и моделей работы wormhole коммутаторов [16-18]. Подсистема моделирования работы оконечных устройств отражает работу оконечных устройств сети Myrinet и построена с использованием: документации на эту сеть; базового протокола работы сетевой оболочки, описанного в [10]; документации к сетевой оболочке GM [20], распространяемой и поддерживаемой фирмой-производителем сети; описания принципов работы сетевой оболочки [12], а также параметров, часть из которых описана в работах [7,13,14,19], а часть предложена авторами. Подсистема моделирования входной нагрузки строится по принципу событийного управления [11,15], суть которого заключается в том, что нагрузка строится по событиям, возникающим в ходе работы реальной программы. Для реализации данной подсистемы выбрана модель простого коммуникационного теста посылки–приема сообщений, описание и исходные тексты которого поставляются вместе с сетевой оболочкой.

Моделирование работы коммуникационной подсети

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

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

Если в процессе установки соединения канал сети, через который должен проследовать пакет, занят передачей, то возникает ситуация блокировки. Пакет прекращает свое движение, но не освобождает уже занятых им каналов. Далее пакет ожидает освобождения соответствующего канала и пытается его занять. Это может произойти не сразу, так как, возможно, существуют другие пакеты, ждущие освобождения рассматриваемого канала. При этом выбор пакета для передачи выходным каналом может осуществляться в соответствии с некоторым «правилом выбора входного канала». В модели предусмотрено три таких правила: круговой опрос (round-robin), использование одинаковых фиксированных приоритетов (fixed channel priority) и передача по правилу "первым пришел – первым передается" (first come first served). Все время ожидания данные пакета продолжают храниться в памяти оконечного устройства-отправителя.

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

Моделирование работы оконечных устройств

Архитектура моделируемого оконечного устройства сети Myrinet представлена на рисунке 1 в соответствии с [10].

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

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

Основные действия указанной базовой модели представлены на рисунке 2 в соответствии с [10].

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

Основное достоинство данного протокола состоит в том, что любой его шаг возможен без вмешательства операционной системы, что исключает излишние копирования пакета и накладные расходы на его пересылку. Необходимо отметить, что шаги (1), (4), (5), (7) и (8) могут выполняться параллельно, образуя тем самым сетевой конвейер.

Подпись: Рис. 2. Основные операции базового протоколаРассматриваемая нами сетевая оболочка GM следует описанному протоколу, за исключением ряда деталей, которые необходимо учитывать при реализации подсистемы моделирования и проведении калибровки. Во-первых, шаги (1) и (8) отсутствуют, то есть любая посылка и прием сообщения производятся только из памяти с прямым доступом, которая должна быть выделена в самом начале работы программы еще до любых передач. Во-вторых, в библиотеке GM реализуется надежная доставка сообщений, что обеспечивается при помощи протокола «скользящего окна» (Go-Back-N protocol). Этот же протокол используется и для защиты сети от перегрузок. Так как ошибки в каналах связи чрезвычайно редки, и в данном исследовании мы рассматриваем работу системы без перегрузок, то реализация протокола «скользящего окна» является нецелесообразной для подсистемы моделирования оконечного устройства. Задержка, привносимая данным протоколом, может быть измерена средствами библиотеки GM и будет учитываться нами при проведении калибровки. В-третьих, в базовом протоколе отсутствует использование программируемого ввода-вывода (PIO) для копирования данных между памятью оконечного устройства и памятью сетевого интерфейса. Подобная возможность реализована в ряде версий сетевых протоколов и применяется для ускорения отправки небольших сообщений [10]. Имеется она также и в оболочке GM. Однако, как показывают результаты экспериментов, ее влияние несущественно, поэтому моделирование программируемого ввода-вывода отсутствует в подсистеме, хотя и может быть легко туда добавлено.

Функциональность базового протокола реализуется в управляющей программе сетевого интерфейса, структура которой представлена на рисунке 3 в соответствии с документацией фирмы Myricom Inc. на сетевую оболочку GM. Управляющая программа представляет собой композицию четырех детерминированных конечных автоматов, реализующих функции:

·    копирования пакетов из памяти оконечного устройства в локальную память сетевого интерфейса («автомат SDMA»);

·    отправки пакетов по сети из локальной памяти сетевого интерфейса («автомат Send»);

·    приема пакетов из сети в локальную память сетевого интерфейса («автомат Recv»);

·    копирования пакетов из локальной памяти сетевого интерфейса в память оконечного устройства («автомат RDMA»).

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

Подпись: Рис. 3. Структура управляющей программы сетевого интерфейсаПодсистема моделирования работы оконечных устройств построена по тому же принципу, что и управляющая программа, в ней выделено 4 модуля для моделирования работы конечных автоматов, также имеются модули, моделирующие основные характеристики работы процессора сетевого интерфейса и центрального процессора оконечного устройства. В соответствии с базовым протоколом (рис. 2) задержка пакета в сети формируется следующими составляющими: накладные расходы центрального процессора оконечного устройства на отправку пакета на стадии (2) ; накладные расходы процессора сетевого интерфейса на подготовку копирования пакета в память сетевого интерфейса на стадии (3) ; расходы на копирование пакета «память оконечного устройства – память сетевого интерфейса»  на стадии (4); время на отправку пакета по сети  на стадии (5); накладные расходы на подготовку копирования пакета из памяти сетевого интерфейса получателя в память оконечного устройства получателя на стадии (6) ; время на копирование пакета из памяти сетевого интерфейса получателя на стадии (7) . Все указанные составляющие представляют собой время и измеряются в микросекундах (). Из них ,  и  не зависят от длины пакета, так как не связаны с его перемещением по сети или между памятью оконечного устройства и памятью сетевого интерфейса, а , и  линейно зависят от длины пакета, то есть , , , где  и  – пропускная способность шины ввода-вывода при копировании «память оконечного устройства – память сетевого интерфейса» и «память сетевого интерфейса – память оконечного устройства» соответственно;  – пропускная способность каналов сети передачи данных;  – длина пакета. Единица измерения пропускных способностей байт в микросекунду (), а единица измерения длины пакета байт (B).

Необходимо отметить, что, в отличие от моделей [7,14,19], мы не рассматриваем накладные расходы центрального процессора на получение сообщения (параметр ), так как согласно работе [9] и результатам проведенных авторами экспериментов теста LogP данная величина очень мала и может не учитываться. Это вполне соответствует [10] и принципу организации сетевой оболочки GM, который состоит в том, что для получения сообщения из сети, используется механизм опроса (polling) вместо механизма прерываний (interrupt), что обеспечивает малую величину накладных расходов центрального процессора.

Моделирование входной нагрузки

Для построения подсистемы моделирования входной нагрузки нами выбрана модель простейшего коммуникационного теста посылки-приема сообщений в сети, суть которого состоит в том, что один узел последовательно посылает пакеты другому узлу сети, производя при этом измерение среднего времени пересылки. Основные параметры данного теста: минимальная длина пакета; максимальная длина пакета; шаг, на который увеличивается длина пакета; количество пакетов, которые должны быть отправлены на каждом шаге теста; максимальное количество пакетов на стадии отправки. Отправитель последовательно перебирает все длины, от минимальной до максимальной с определенным шагом и для каждой длины посылает заданное количество пакетов, после чего измеряет среднюю задержку пакета в сети. Параметр максимальное количество пакетов на стадии отправки регулирует количество пакетов, которые были отправлены, но еще не получены адресатом, то есть находятся на стадиях (1)–(5) базового протокола (рис. 2). Данный параметр аналогичен параметру, определяющему задержку между двумя последовательными пересылками пакетов, то есть нагрузку на сеть, и используемому при калибровке модели LogP [14].

Подпись: Рис. 4. Схема расчета параметров , , и Калибровка модели

Калибровка системы проводилась в соответствии с подходами, изложенными в работах [14,16,19], и оригинальным методом, предложенным авторами. Для калибровки использовалась сеть Myrinet 2000 (емкость 2 Гбита в секунду, то есть 250 ) высокопроизводительного вычислительного комплекса МВС-1000М, в состав которой входит сетевой интерфейс LANai9, соединенный через шину PCI 64bit/33MHz (емкость 264 ) с вычислительным модулем. Сеть работает под управлением сетевого программного обеспечения GM версии 1.6.4. При проведении калибровки параметров использовался стандартный тест “прием-посылка” сообщений gm_allsize, поставляемый совместно с сетевой оболочкой GM. Так как максимальная длина пакета, поддерживаемая в сетевой оболочке GM, составляет 4096 байт, то длина посылаемых сообщений будет варьироваться нами от 1 до 4096 байт и представлять собой отправку единственного пакета. В программе теста авторами был сделан ряд модификаций: добавлена возможность увеличивать задержку при посылке сообщения (аналогично [14]) и введен параметр максимальное количество пакетов на стадии отправки, описанный ранее.

Калибровка модели оконечного устройства

Подпись: Рис. 5. Задержка пакета на стадии отправки для слу-чаев 1 и 10 пакетов в сетиЦелью калибровки модели оконечного устройства является определение параметров , , , ,  и . Мы будем рассматривать два узла сети, передача пакетов между которыми осуществляется через один коммутатор. Это позволит не учитывать задержки, связанные с возможными блокировками пакетов, и рассматривать передачу пакета по сети как копирование из памяти оконечного устройства-отправителя в память оконечного устройства-получателя. Рассмотрим стадии отправки и приема пакета.

·    Стадия отправки пакета (параметры , , , ).

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

При небольшой длине пакета задержки  и  малы и их можно не учитывать (в рассматриваемой ситуации при длине пакета меньше 250 байт указанные величины не превышают 1 ms). Таким образом, в точках A, B, C (рис. 4) присутствуют только задержки  и  (стадии (2) и (3)). Так как на кривой I на стадии отправки имеется только один пакет, а на кривой II – несколько пакетов, то очевидно, что длина отрезка AC равна задержке при последовательном выполнении этих стадий, а длина отрезка BC – при параллельном. Следовательно, длина отрезка AC равна сумме , а длина отрезка BC – значению наибольшего из параметров  и  (). Чтобы определить, какой из указанных параметров является наибольшим, в программу коммуникационного теста необходимо внести задержку при отсылке пакета аналогично [14]. Данная задержка увеличивает параметр , следовательно, если вид кривой II изменится даже при незначительной дополнительной задержке, то это означает, что , в противном случае  (рис. 6).

Для определения параметров  и  необходимо рассмотреть углы наклона кривых I и II (рис. 5). Действительно, точки D и E соответствуют задержкам, которые возникают, если длина пакета равна CF, а точки G и H – задержкам, которые возникают, если длина пакета равна CK. Длины отрезков DF и GK равны суммарным задержкам по всем шагам стадии отсылки, а длины Подпись: Рис. 6. Определение наибольшего из параметров ( или )отрезков EF и HK – задержкам, формируемым наибольшей из задержек  и  (так как соответствующие им шаги (4) и (5) базового протокола могут выполняться параллельно) и некоторой постоянной задержкой (формируемой шагами (2) и (3) базового протокола). Для вычисления параметров  и  необходимо рассмотреть коэффициенты наклона прямых DG и EF и воспользоваться следующими соотношениями:  и . Чтобы вычислить наибольший из параметров  и , необходимо провести еще один дополнительный Подпись: Рис. 7. Определение наибольшего из параметров ( или )Подпись: Рис. 8. Сравнение результатов работы модели и запус-ка тестаэксперимент, суть которого состоит в том, чтобы искусственно увеличить задержку , а затем проанализировать, как это повлияет на вид кривой II (рис. 4). Для этого мы запустим простейший коммуникационный тест на трех оконечных устройствах сети таким образом, чтобы две машины были отправителями для одной машины-получателя. Очевидно, что между двумя отправителями будут возникать конфликты, которые приведут к увеличению задержки . Результаты, представленные на рисунке 6, свидетельствуют о том, что наибольшей является задержка , так как даже небольшое ее увеличение приводит к изменению общего вида кривой задержки.

·    Стадия приема пакетов (параметры , ).

Для определения указанных параметров необходимо выполнить коммуникационный тест в двух вариантах: случай последовательной посылки пакета в обоих направлениях (ping pong) и случай посылки пакета в одном направлении при значении параметра максимальное количество па- кетов на стадии отправки, равного единице (рис. 10). Так как в первом варианте полная задержка формируется как сумма задержек на всех шагах стадии отправки, а во втором варианте к ней добавляется время, необходимое на прием пакета (шаги (6) и (7) базового протокола рис. 2), то параметры  и  можно вычислить, используя разность рассматриваемых задержек по схеме рисунка 9.

Так как параметр  не зависит от длины пакета, то он может быть вычислен как длина отрезка AB. Параметр  может быть получен по значениям задержек на кривых I и II в точ- ках F и G, соответствующих двум различ- ным длинам пакета при помощи соотношения .

Подпись: Рис. 10. Сравнение результатов экспериментов при по-сылке в оба направления (ping pong) и в одном направле-нии при 1 пакете на стадии отправки	Подпись: Рис. 9. Схема расчета параметров и В таблице представлены параметры, вычисленные по предложенным схемам (рис. 4 и рис. 9), а на рисунках 8 и 11 приведено сравнение работы подсистемы моделирования оконечного устройства с результатами экспериментов.

Таблица

Значения параметров модели оконечного устройства

6.4

8.5

220.0

220.0

2.5

240.0

Калибровка модели коммуникационной подсети

Подпись: Рис. 11. Сравнение результатов работы модели и запус-ка коммуникационного теста в обоих направлениях (ping pong)Целью калибровки модели коммуникационной подсети является определение правила выбора входного канала в коммутаторе. Для калибровки параметров коммуникационной подсети также будет использоваться коммуникационный тест, применявшийся в предыдущем разделе при определении параметров модели оконечного устройства, только теперь программа будет запускаться на трех и более узлах сети, подключенных к одному и тому же коммутатору. Чтобы достичь поставленной цели, мы будем проводить эксперименты по следующему концептуальному плану, который опирается на последовательное рассмотрение возможных правил выбора входного канала и отбрасывание неподходящих правил.

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

2.  Если правило выбора с различными фиксированными приоритетами не используется, то необходимо определить, применяется ли стратегия кругового опроса. Для этого коммуникационный тест нужно запустить в той же конфигурации, что и в п. 1, но длины пакетов при этом должны быть выбраны следующим образом. Отправитель 1 посылает пакеты максимальной длины, а отправители 2, 3, …, n – пакеты минимальной длины. Выходной канал коммутатора большую часть времени будет занят передачей пакетов отправителя 1, так как он создает наибольшую нагрузку по сравнению с другими отправителями. Таким образом, после окончания передачи любого пакета отправителя 1, в первую очередь будут передаваться пакеты тех абонентов, которые находятся «ближе» к отправителю 1 в соответствии с направлением кругового просмотра. Следовательно, чем ближе любой отправитель k расположен к отправите- лю 1, тем меньше у него должна быть задержка. Если это выполняется, то используется стратегия кругового опроса.

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

Подпись: Рис. 13. Результаты коммуникационного теста для конфигурации На рисунках 12 и 13 показаны результаты запуска тестов п.1 и 2 концептуального плана.

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

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

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

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

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

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

Список литературы

1.  Альянах И.Н. Моделирование вычислительных систем. – Л.: Машиностроение, 1998.

2.  Башарин Г.П., Бочаров П.П., Коган Я.А. Анализ очередей в вычислительных сетях. Теория и методы расчета. – М.: Наука, 1989.

3.  Бертсекас Д., Галлагер Р. Сети передачи данных. – М.: Мир, 1989.

4.  Клейнрок Л. Коммуникационные сети. Стохастические потоки и задержки сообщений. – М.: Наука, 1970.

5.  Шварц М. Сети связи: протоколы, моделирование и анализ. / Пер. с англ. под ред. В.И. Неймана. – М.: Наука, 1992.

6.  Шоргин С.Я. Модели сетей связи со смешанной нагрузкой. // Техника средств связи. Сер. СС, 1985. - Вып. 1. - С. 60 – 63.

7.  Alexandrov A., Ionescu M., Schauser K. E., Scheiman C. LogGP: Incorporating Long Messages into the LogP model - One step closer towards a realistic model for parallel computation. 7th Annual Symposium on Parallel Algorithms and Architecture (SPAA'95), July 1995.

8.  Banks J., Carson J.S. II, Nelson B.L. Discrete-Event System Simulation. Second Edition. Prentice Hall, 1995.

9.  Baker M., Ong H. A Quantitative Study on the Communication Performance of Myrinet Network Interfaces. University of Portsmouth, Portsmouth, UK March 15, 2002. http://l59.dsg.port. ac.uk/JEM/pubs/DSG200203_MyriPerf.pdf.

10.     Bhoedjang R.A.F. Communication Architectures for Parallel-Programming Systems. Phd. thesis, June 2000, Vrije Universiteit, Amsterdam.

11.     Chodnekar S., Srinivasan V., Vaidya A., Sivasubramaniam A., Das C. Towards a Communication Characterization Methodology for Parallel Applications. Proceedings of the 3rd International Symposium on High Performance Computer Architecture (HPCA), February 1997.

12.     Coll S., Flich J., Malumbres M.P., López P., Duato J., and Mora F.J. A First Implementation of In-Transit Buffers on Myrinet GM Software. IEEE Computer Society Press (CAC 2001) (ISBN: 0-7695-0990-8), pp. 232-237, 2001.

13.     Culler D.E., Karp R.M., Patterson D.A., Sahay A., Schauser K.E., Santos E., Subramonian R., von Eicken T. LogP:Towards a Realistic Model of Parallel Computation. 4th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, San Diego, CA, May 1993.

14.     Culler D.E., Liu L.T., Martin R.P., Yoshikawa C. LogP performance assessment of fast network interfaces. IEEE Micro, 16(1): 35-43, February 1996.

15.     George A.D., VanLoon R.A. High-fidelity Modelling and Simulation of Myrinet System Area Networks. International Journal of MODELLING AND SIMULATION, vol.21, no.1, 2001.

16.     Lysne O. Towards an Analytical Model of Wormhole Routing Networks. Microprocessors and Microsystems, vol.21 (1998), pp. 491-498.

17.     Ni L.M., McKinley P.K. A survey of wormhole routing techniques in direct networks. Computer, pp. 62-76, 1993.

18.     Seitz C., Boden C.L., Seizovic N.J., Su W. The Design of the Caltech Mosaic C. Multicomputer. Proceedings of the Washington Symposium On Integrated Systems, Seattle, WA, 1993.

19.     Tam A.T.C. Performance Studies of High-Speed Communication on Commodity Cluster. Phd. thesis, December 2001, University of Hong Kong.

20.     The GM-1 Message Passing System, http://www.myri. com/scs/GM/doc/refman.pdf.


Постоянный адрес статьи:
http://swsys.ru/index.php?page=article&id=602
Версия для печати
Выпуск в формате PDF (1.96Мб)
Статья опубликована в выпуске журнала № 1 за 2004 год.

Возможно, Вас заинтересуют следующие статьи схожих тематик: