автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.11, диссертация на тему:Методы и средства исследования производительности сетей, использующих технологию передачи Wormhole

Московский государственный университет им. М.В.Ломоносова

На правах рукописи

Веселов Николай Александрович

МЕТОДЫ И СРЕДСТВА ИССЛЕДОВАНИЯ ПРОИЗВОДИТЕЛЬНОСТИ СЕТЕЙ, ИСПОЛЬЗУЮЩИХ ТЕХНОЛОГИЮ ПЕРЕДАЧИ WORMHOLE

Специальность 05.13.11 - математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей

Автореферат диссертации на соискание ученой степени кандидата физико-математических наук

Москва-2004

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

Научный руководитель:

доктор физико-математических наук, профессор Машечкин Игорь Валерьевич.

Официальные оппоненты:

член-корр. РАН, доктор физико-

математических наук

Воеводин Владимир Валентинович;

доктор физико-математических наук, профессор

Томилин Александр Николаевич.

Ведущая организация:

Институт Проблем Информатики РАН

Защита диссертации состоится " 19

марта

2004 г. в

П. часов на заседании диссертационного совета Д 501.001.44 в Московском государственном университете им. М.В. Ломоносова по адресу: 119992, ГСП-2, Москва, Ленинские горы, МГУ, 2-й учебный корпус, факультет ВМиК, аудитория 685.

С диссертацией можно ознакомиться в библиотеке факультета ВМиКМГУ.

Автореферат разослан '

_2004 г.

Ученый секретарь диссертационного совета профессор

Н.П. Трифонов

ОБШДЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы.

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

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

Объектом исследования настоящей работы является класс сетей передачи данных, использующих технологию передачи -^ппЬо1е. Данный класс представлен множеством современных высокоскоростных пакетных сетей, примерами которых являются сети Муппе^ 8егуегпе1 II, 8ипйш1у.

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

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

при

построении

вычислительных

комплексов,

систем

РОС. НАЦИОНАЛЬНАЯ БИБЛИОТЕКА

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

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

• Ёмкость каналов сети, или скорость передачи каждого отдельного канала. Это физическая величина, которая является фиксированной для любой конкретной сети.

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

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

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

• Отсутствует модель, которая, с одной стороны, обладает достаточной общностью для моделирования работы всего

!

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

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

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

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

Цель работы

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

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

• создания программных средств имитационного моделирования и методов настройки этих средств на реальные сети указанного типа;

• создания алгоритма расчёта средней задержки пакета в сети класса wormhole.

Научная новизна

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

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

Практическая ценность

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

• Расчёт проектной производительности сетей передачи данных. Расчёт проектной производительности информационно-вычислительных систем необходим, поскольку сложность их конфигурации и функционирования сильно уменьшает возможности интуитивной оценки производительности1. Так как средняя задержка пакета является обобщённой характеристикой производительности сети, то её расчёт необходимо проводить для оценки производительность ещё только проектируемой системы, выявления «узких мест» и т.д..

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

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

Методы исследования

При создании системы имитационного моделирования сетей передачи данных типа wormhole применялся объектно - ориентированный подход. При построении алгоритма расчёта средней задержки пакета использовались методы теории массового обслуживания и сетей массового обслуживания, в том числе метод анализа во множестве дискретных моментов времени (discrete-time domain analysis).

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

Апробация работы и публикации

По теме диссертации опубликовано 5 печатных работ [1-5]. Результаты работы докладывались на объединенном научно-исследовательском семинаре кафедр Автоматизации систем вычислительных комплексов, Алгоритмических языков и Системного программирования факультета ВМиК МГУ, на научных семинарах факультета ВМиК МГУ, а также на следующих конференциях:

• научная конференция «Проектирование научных и инженерных приложений в среде Matlab» (Москва, ИЛУ РАН, 2002).

• научная конференция «Ломоносовские Чтения» (Москва, МГУ, 2002,2003);

• научная конференция «Тихоновские Чтения» (Москва, МГУ, 2003).

Структура и объём диссертации

Диссертация состоит из введения, четырёх глав, заключения, двух приложений и библиографии. Объём диссертации 120 страниц. Библиография включает 54 наименования.

КРАТКОЕ СОДЕРЖАНИЕ РАБОТЫ

Во введении обсуждается объект и предмет исследования, поставлена цель работы и кратко изложено содержание диссертации.

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

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

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

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

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

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

• абстрактные модели параллельных вычислительных систем;

• аналитические модели работы сетей типа wormhole и близких к ним;

• имитационные модели сетей класса wormhole.

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

Во второй главе диссертационной работы рассматривается система имитационного моделирования сетей передачи данных типа wormhole.

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

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

(коммуникационная подсеть);

• подсистемы моделирования оконечных устройств сети;

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

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

Раздел 2.2 посвящен рассмотрению структуры и параметрам каждой из трёх вышеперечисленных подсистем моделирования.

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

При построении подсистемы моделирования оконечного устройства рассматривается архитектура оконечных устройств типичного представителя класса wormhole сетей — сети Myrinet и сетевая программная оболочка GM2. Основной особенностью архитектуры подобных оконечных устройств является используемый в них сетевой интерфейс, имеющий собственный процессор, на котором выполняется управляющая программа, обеспечивающая взаимодействие оконечного устройства с сетью. Построение подсистемы моделирования оконечного устройства во многом опирается на работу R.A.F. Bhoedjang3, в которой содержится анализ реализаций большинства существующих сетевых программных оболочек, применяемых в сети Myrinet. Кроме того, в указанной работе выделяются основные шаги некоторого базового протокола функционирования оконечных устройств сети, присутствующие в большинстве реализаций сетевого программного обеспечения для сетей данного класса.

Опираясь на описание базового протокола и сетевой оболочки GM, выделены следующие параметры функционирования оконечных устройств: накладные расходы центрального процессора оконечного устройства на отправку пакета 0SI накладные расходы процессора сетевого интерфейса на подготовку копирования пакета в память сетевого интерфейса LSDhu, расходы на копирование пакета «память оконечногоустройства — память сетевого интерфейса» Т^ш, время на отправку пакета по сети Т5кШсу, накладные расходы на подготовку копирования пакета из памяти сетевого интерфейса получателя в память оконечного устройства получателя время на копирование

пакета из памяти сетевого интерфейса получателя Trdma- Все указанные составляющие представляют собой время и измеряются в микросекундах. Из них Ot, LSDM и ^¡¡dua не зависят от длины пакета, так

2 The GM-1 Message Passing System, http://www.myri.com/scsyGM/doo're£man.pdf.

' R.A.F. Bboedjang. Communication Architectures for Parallel-Programming Systems. PhD. thesis, June 2000, Vrije Universiteit, Amsterdam.

как не связаны с его перемещением, а Т50МА, ^яош линейно

зависят от длины пакета.

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

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

Раздел 23 посвящен калибровке вышеперечисленных параметров имитационной модели. Для калибровки использовалась сеть Myrinet 2000 высокопроизводительного вычислительного комплекса МВС-1000М, в состав которой входит сетевой интерфейс ЬАКа19. Сеть работает под управлением сетевого программного обеспечения GM версии 1.6.4. При проведении калибровки применялся стандартный тест "приём - посылка" сообщений gm_aUsize, поставляемый совместно с сетевой оболочкой GM. В программе теста автором сделан ряд модификаций: добавлена возможность увеличивать задержку при посылке сообщения и введён параметр максимальное количество пакетов на стадии отправки, описанный в предыдущем разделе.

Первая часть раздела 2.3 посвящена калибровке параметров оконечных устройств. Эксперименты проводились для двух оконечных устройств, соединённых с соседними входными каналами одного и того

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

Для определения параметров первой стадии (Ot, L^ш, сд-¡ш, С^) используется тест посылки в одном направлении: отправитель посылает несколько пакетов и измеряет среднее время на доставку пакета получателю, при этом варьируется количество пакетов, одновременно находящихся в сети. Для определения параметров второй стадии

используется два теста: посылки в одном направлении для случая одного пакета в сети и посылки - приёма - обратной посылки (ping-pong), при котором в сети одновременно находится также один пакет. Во втором случае средняя задержка измеряется как половина средней задержки пакета от момента его отправки до момента возвращения в узел -отправитель. Сравнение средней задержки в обоих случаях позволяет определить вышеназванные параметры стадии приёма пакетов.

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

В третьей главе диссертационной работы рассматривается алгоритм расчёта средней задержки пакета для сетей передачи данных типа wormhole. Указанный алгоритм опирается на методы теории массового обслуживания и сетей массового обслуживания. В частности, при его построении используется метод анализа во множестве дискретных моментов времени (discrete-time domain analysis), разработанный P. Tran-Gia4.

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

4 р Tran-Gia. Analysis of Polling Systems with General Input Process and Finite Capacity, IEEE Transactions on Communications, vol. 40, no. 2,1992, pp.337-344

• структуру сети и используемую технологию передачи данных;

• нагрузку на сеть;

• маршрутизацию в сети.

Сеть задаётся при помощи ориентированного графа С? = (С/, К), где и - вершины (узлы сети), V - дуги (каналы связи). Множество вершин представляет собой объединение двух непересекающихся подмножеств 11 = £/1и£/2,£/1п(У2 =0, подмножества оконечных устройств С/х и подмножества коммутаторов иг. Для передачи каждого пакета между отправителем и получателем устанавливается монопольное соединение, представляющее из себя последовательность каналов сети, передающих единицы информации только данного пакета. При установке соединения возможно возникновение блокировки, при которой пакет приостанавливает своё движение, но не теряется и не освобождает уже занятых им каналов сети. Если имеется несколько заблокированных пакетов, ожидающих освобождения одного и того же канала сети, то используется круговое правило выбора входного канала. Для всех коммутаторов сети определён парамегр время переключения г/, представляющий собой время, которое любой выходной канал любого коммутатора тратит при круговом просмотре на переход к следующему просматриваемому входному каналу. После установки соединения передача пакета представляет собой непосредственное копирование данных пакета из памяти узла -отправителя в память узла - получателя. Скорость передачи при этом равна скорости работы отдельного канала сети. При разрыве соединения каналы сети освобождаются последовательно по направлению от отправителя к получателю. При установке соединения и при его разрыве отсутствуют задержки на распространение сигнала в каналах сети.

Нагрузка, поступающая в сеть, определяется множеством абонентов, которое представляет из себя множество тяготеющих пар отправитель -получатель IV = = еЦ^к е^^' Трафик (поток пакетов),

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

случайными величинами - время между двумя

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

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

который не меняется

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

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

через случайную величину - время, которое уходит на то, чтобы пакету данной пары абонентов занять канал / после того, как заголовок пакета попал в коммутатор ^ а через С - случайную величину — время, которое уходит у пакета данной пары абонентов w на то чтобы установить соединение между отправителем ] и получателем к и передать данные пакета после установки соединения. Для любого оконечного устройства сети / 6 {/,, которое является отправителем в нескольких парах абонентов обозначим через случайную величину - время, которое уходит у любого пакета, поступившего в узел на ожидание в очереди ждущих отправки пакетов перед началом установки соединения с получателем пакета. Средние задержи пакета в сети представляют собой математические ожидания случайных величин Т", V и Ц-1, для обозначения которых будем использовать символы соответственно.

Формальная постановка задачи. Необходимо разработать алгоритм, который по заданным графу сети С — (С/, V), множеству абонентов Ж = {и* = (/,£),/ 6 е £/,,./ ^ создаваемой каждой парой абонентов нагрузке (случайные величины А" и В") и маршрутам передачи р„ = (/',»| 0",'г0''ц, 0'»4используемым каждой парой абонентов, позволит рассчитывать среднюю задержку пакета при занятии определённых каналов сети £[Т"], среднюю задержку на установку соединения между отправителем и получателем и передачу данных пакета Е[С\, для любого оконечного устройства jeUíl которое является отправителем, среднюю задержку в очереди ждущих пакетов в данном узле Е[()'].

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

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

Необходимость рассмотрения каналов сети в определённом порядке обусловлена влиянием, которое оказываются заблокированные пакеты на задержки при занятии других каналов. В работе О. Lysne5 доказано следующее

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

После разбиения сети каждый канал рассматривается как система массового обслуживания с круговым опросом (polling system), а для определения характеристик его работы используется численный метод анализа во множестве дискретных моментов времени (discrete-time domain analysis)6. Суть данного метода состоит в том, что ось времени разбивается на небольшие интервалы одинаковой фиксированной длины. Затем определяются дискретные моменты времени, отстоящие друга от друга на расстоянии указанных интервалов и предполагается, что изменение состояния системы может происходить только в отмеченные моменты времени. Применимость подобного подхода обусловлена тем, что в реальной системе все события также происходят в определённые дискретные моменты времени, связанные, например, с тактовой частотой работы процессора. Так как система рассматривается в стационарном режиме работы, то для её описания достаточно использовать дискретные случайные величины. Метод анализа во множестве дискретных моментов времени позволяет рассчитать дискретное распределение вероятностей для времени ожидания занятия любого канала сети передачи данных.

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

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

5 О. Lysne. Towards an Analytical Model of Wormhole Routing Networks. Microprocessors and Microsystems,

vol.21, pp. 491-498,1998. ' P. Tran-Gia. Ук. соч.

В первом случае, выделяется множество входных каналов коммутатора у, по которым могут поступать пакеты для передачи через канал /. Данные входные каналы нумеруются в порядке их сканирования 1р, р=0,1,...,г-1 и для каждого из них формируется множество использующих его абонентов сети W^j = {и*, :3j,l(i,j)=l,l(i,j — i)=Jp\t после чего делаются следующие предположения

Предположение 1. Дня всех абонентов из множества W,mJ задержки на занятие канала / одинаковы, то есть

Предположение 2. Поток пакетов, создаваемый множеством абонентов И^, является простейшим.

Предположение 3. Случайные величины - времена занятия канала / для потоков являются независимыми.

Предположение 4. Задержки, с которыми пакет сталкивается при занятии определённых каналов сети, не зависят от будущих задержек при занятии следующих каналов сети по маршруту следования пакета.

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

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

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

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

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

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

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

В разделе 4.1 обсуждаются параллельные приложения, которые служат для формирования входной нагрузки для сети. В качестве таких приложений использовались тесты SP и ВТ одного из наиболее распространённых пакетов тестирования высокопроизводительных вычислительных комплексов NAS Parallel Benchmarks7. Обе программы являются примерами реальных параллельных приложений, при этом существует несколько вариантов этих тестов (несколько классов), отличающихся друг от друга размерностью решаемых задач. Для проведения экспериментов использовались тесты SP и ВТ класса А для 9, 16 и 25 параллельных ветвей.

В разделе 4.2 обсуждаются дополнительные параметры, которые необходимо ввести в имитационную модель, построенную во второй главе диссертации, для того, чтобы она соответствовала высокопроизводительному вычислительному комплексу МВС-1000М. Такими параметрами являются количество процессоров вычислительного модуля и правило формирования очереди ждущих пакетов в оконечном устройстве. Значение первого параметра для указанного высокопроизводительного вычислительного комплекса равно двум. Второй параметр - очередь ждущих пакетов, которая, согласно документации на сетевую программную оболочку GM, формируется следующим образом. Каждой паре абонентов сети соответствует логическое соединение и собственная очередь ждущих пакетов. Оконечное устройство просматривает по кругу очереди всех соответствующих ему логических соединений и, если в какой - либо из них имеется ждущий доставки пакет, то отправляет его. Указанные

' D IL Bailey, E.Barszcz, JXBarton, D S.Browning, R.L.Carter, L.Dagum, R-A.Fatoohi, P.O.Frederickson, T.AXasmsü, R.S. Schreiber, H.D. Simon, V.Venkatakrishnam, SX. Weeratunga. The NAS Parallel Benchmarks. International Journal of Supercomputer Applications, Vol. 5, No. 3,1991, pp. 63-73.

параметры были реализованы в системе имитационного моделирования при проведении экспериментов.

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

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

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

где средние задержки были

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

В заключении формулируются основные результаты диссертации.

Основные результаты

1. Предложен способ построения, структура и основные параметры имитационной модели сетей передачи данных типа —01т^1е, a также метод калибровки и настройки имитационной модели сети на реальную систему.

2. Предложен новый алгоритм расчёта средней задержки пакетов для сетей передачи данных типа -игогшЬоЬ, опирающийся на методы теории сетей массового обслуживания.

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

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

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

1. Н.А. Веселов, И.В. Машечкин. О некоторых экспериментальных средствах анализа колебаний длин очередей сообщений в узлах сети в условиях возникновения перегрузок. // Тематический сборник «Программные системы и инструменты» № 2, М. изд. МГУ2001.

2. Н.А. Веселов, Е.А. Журавлёв, И.В. Машечкин. Моделирование процесса коммутации многостадийных схем Клоза с использованием инструментария Simulink. // Тезисы Всероссийской Научной Конференции «Проектирование научных и инженерных приложений в средеMatlab», M. ИПУ РАН 2002.

3. Н.А. Веселов. Оптимизация пропускной способности сетей, построенных по схеме Ч. Клоза, в условиях квазистатического размещения абонентов и отсутствия информации о загруженности системы. // Тематический сборник «Программные системы и инструменты» № 3, М. изд. МГУ2002.

4. Н.А. Веселов, И.В. Машечкин. Методы и средства моделирования wormhole сетей передачи данных. // Сборник «Программные продукты и системы», № 4,2003.

5. Н.А. Веселов. Алгоритм расчёта средней задержки пакета в сетях передачи данных типа wormhole. // Тематический сборник «Программные системы и инструменты» № 4, М. изд. МГУ2003.

Издательство ООО "МАКС Пресс". Лицензия ИД № 00510 от 01.12.99 г. Подписано к печати 16.02.2004 г. Формат 60x90 1/16. Усл.печ.л. 1,0. Тираж 100 экз. Заказ 178. Тел. 939-3890,939-3891,928-1042. Тел./факс 939-3891. 119992, ГСП-2, Москва, Ленинские горы, МГУ им. М.В.Ломоносова.

ВВЕДЕНИЕ.

ГЛАВА I. СЕТИ ПЕРЕДАЧИ ДАННЫХ ТИПА WORMHOLE.

1. ПРИНЦИПЫ ОРГАНИЗАЦИИ СЕТЕЙ ТИПА WORMHOLE.

2. КЛАССИФИКАЦИЯ РАБОТ ПО МОДЕЛИРОВАНИЮ СЕТЕЙ ТИПА WORMHOLE.

2.1 Абстрактные модели параллельных вычислительных систем.

2.2 Аналитические модели работы сетей типа wormhole.

2.3 Системы имитационного моделирования сетей типа wormhole.

ГЛАВА П. СИСТЕМА МОДЕЛИРОВАНИЯ СЕТЕЙ ТИПА

WORMHOLE.

1. КОНЦЕПЦИЯ ПОСТРОЕНИЯ СИСТЕМЫ МОДЕЛИРОВАНИЯ.

2. СТРУКТУРА СИСТЕМЫ МОДЕЛИРОВАНИЯ.

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

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

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

3. КАЛИБРОВКА МОДЕЛИ.

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

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

ГЛАВА III. АЛГОРИТМ РАСЧЁТА СРЕДНЕЙ ЗАДЕРЖКИ ПАКЕТА В

СЕТЯХ ПЕРЕДАЧИ ДАННЫХ ТИПА WORMHOLE.

1. ФОРМАЛЬНАЯ ПОСТАНОВКА ЗАДАЧИ.

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

1.2 Нагрузка на сеть.

1.3 Маршрутизация в сети.

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

2. АЛГОРИТМ РАСЧЁТА.

2.1 Разбиение сети на отдельные каналы и определение последовательности проведения расчётов.

2.2 Применение метода анализа во множестве дискретных моментов времени для расчёта отдельного канала сети.

2.3 Проведение расчёта средней задержки пакетов для всей сети.

3. ПРОВЕРКА КОРРЕКТНОСТИ АЛГОРИТМА РАСЧЁТА.

ГЛАВА IV. ЭКСПЕРИМЕНТАЛЬНАЯ ПРОВЕРКА АЛГОРИТМА РАСЧЁТА.

1. НАГРУЗКА НА СЕТЬ, ПОРОЖДАЕМАЯ РЕАЛЬНЫМИ ПРИЛОЖЕНИЯМИ.

2. ДОПОЛНИТЕЛЬНЫЕ ПАРАМЕТРЫ ИМИТАЦИОННОЙ МОДЕЛИ.

3. ХАРАКТЕРИСТИКА ПАРАЛЛЕЛЬНОГО ПРИЛОЖЕНИЯ.

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

Объектом исследования настоящей работы является класс сетей передачи данных, использующих технологию передачи wormhole. Данный класс представлен множеством современных высокоскоростных пакетных сетей, примерами которых являются сети Myrinet, Servernet II, Sunfmity.

Традиционной областью применения рассматриваемого класса сетей является создание высокопроизводительных параллельных вычислительных комплексов — суперкомпьютеров с использованием кластерной архитектуры. Суть данного подхода состоит в том, что система строится из множества вычислительных модулей, которые соединяются высокоскоростной сетью. При работе подобного комплекса в проведении вычислений могут параллельно участвовать все либо некоторое подмножество вычислительных модулей, а сеть служит для обмена данными между ними в процессе решения задачи. В создаваемых кластерных вычислительных системах всё чаще используются сети передачи данных типа wormhole, например, из 500 самых быстрых суперкомпьютеров, более чем в 100 применяются сети данного класса, а 30 из них входят в первую сотню.

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

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

• Ёмкость каналов сети, или скорость передачи каждого отдельного канала. Это физическая величина, которая является фиксированной для любой конкретной сети, её увеличение представляет собой задачу разработки сетевого оборудования и . нами не рассматривается.

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

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

Как отмечено в монографии [1], исследование любой системы сводится, по существу, к созданию её модели. Следовательно, моделирование, целью которого является изучение средней задержки пакета, представляет собой основу для проведения исследования производительности сети. Проведённый обзор работ по математическому моделированию сетей передачи данных типа wormhole позволяет сделать вывод о том, что имеется дефицит работ, посвящённых их комплексному моделированию с целью изучения средней задержки пакета. Например, можно указать следующие недостатки имеющихся работ в данной области. 6

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

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

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

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

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

• создания программных средств имитационного моделирования и методов настройки этих средств на реальные сети;

• создания алгоритма расчёта средней задержки пакета в сети.

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

Подход, который чаще всего используется при её решении, состоит во 7 введении ряда упрощающих предположений, например, о независимости случайных процессов, и проведении расчёта средней задержки с использованием введённых упрощений [2, 3, 8, 11]. Естественным способом проверки корректности сделанных предположений и определения величины возникающей ошибки является применение имитационного моделирования [8]. С другой стороны, использование имитационной модели при решении любой практической задачи требует, во-первых, выполнения настройки и калибровки параметров по реальной системе, а во-вторых, проведения серии экспериментов, занимающей в определенных случаях значительное время, тогда как программная реализация алгоритма расчёта позволяет быстрее получить соответствующие показатели производительности сети. Кроме того, последняя может применяться и для систем, которые пока ещё только проектируются. Всё вышеизложенное позволяет сформулировать цель настоящей работы.

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

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

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

• Разработка оптимизирующих алгоритмов маршрутизации.

Как известно, двумя основными функциями алгоритма маршрутизации являются, во-первых, выбор маршрута для передачи пакета по сети и во-вторых, доставка пакета от отправителя к получателю [3]. Первую функцию маршрутизации, то есть выбор маршрута, обычно стараются реализовать таким образом, чтобы оптимизировать определённые характеристики сети. В работах [3, 4] и в ряде других, обсуждается алгоритм оптимальной маршрутизации. Суть его состоит в том, что, используя усреднённые нагрузки на линии сети, производится оптимизация средней задержки пакета при помощи выбора маршрутов передачи. Очевидно, что для создания подобного алгоритма необходимо иметь оценочные или расчётные формулы для средней задержки пакета в сети, чтобы использовать их в качестве целевой функции оптимизирующего алгоритма маршрутизации.

• Оценка времени выполнения параллельных задач на высокопроизводительных вычислительных комплексах.

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

• Построение систем управления прохождением заданий для высокопроизводительных вычислительных комплексов. 9

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

Диссертационная работа состоит из четырех глав.

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

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

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

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

• Функционирование системы рассматривается в стационарном (устойчивом) режиме, при котором характеристики случайных процессов, протекающих в ней, не изменяются с течением времени.

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

Третья глава состоит из трех параграфов. Первый параграф посвящен построению модели системы и формальной постановке задачи расчета средней задержки пакета в сети передачи данных типа wormhole. Данный

11

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

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

Четвертая глава состоит из трёх параграфов. В первом параграфе обсуждаются параллельные приложения, которые служат для формирования

12 входной нагрузки для сети. В качестве таких приложений использовались тесты SP и ВТ одного из наиболее распространённых пакетов тестирования высокопроизводительных вычислительных комплексов NAS Parallel Benchmarks [14]. Обе программы являются примерами реальных параллельных приложений, при этом существует несколько вариантов этих тестов (несколько классов), отличающихся друг от. друга размерностью решаемых задач. Для проведения экспериментов использовались тесты SP и ВТ класса А для 9, 16 и 25 параллельных ветвей. Во втором параграфе обсуждаются дополнительные параметры, которые необходимо ввести в имитационную модель, построенную во второй главе диссертации. Такими параметрами являются количество процессоров вычислительного модуля и правило формирования очереди ждущих пакетов в оконечном устройстве. В третьем параграфе обсуждаются характеристики работы реальных приложений и их вычисление с использованием построенного алгоритма расчёта и параметров моделирования, предложенных и измеренных выше.

Основные результаты диссертации.

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

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

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

4. Проведена серия экспериментов, подтверждающая применимость предложенного алгоритма для исследования производительности сетей класса wormhole.

ЗАКЛЮЧЕНИЕ

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

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

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

4. Н.А. Веселов. Алгоритм расчёта средней задержки пакета в сетях передачи данных типа wormhole. // Тематический сборник факультета ВМиК МГУ «Программные системы и инструменты» № 4, М., МГУ, 2003, с. 79-98.

5. В.В. Воеводин, Вл. В. Воеводин. Параллельные вычисления. — СПб.: БХВ-Петербург, 2002.

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

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

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

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

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

11. N. Boden, D. Cohen, R. Felderman, A1 Kulawic, C. Seitz, J. Seizovic, and W. Su. Myrinet: A gigabit-per-second local area network. // IEEE Micro, vol 15, no 1, 1995.

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

13. C. Clos. A Study of Non-Blocking Switching Networks. // Bell System Tech. J., vol. 32, pp. 406-424,1953.

14. S.Coll, J. Flich, M. P. Malumbres, P. Lopez, J. Duato, and F.J. Mora. 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.

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

16. W.J. Dally. Performance analysis of &-ary «-cube interconnection networks. // IEEE Transactions on Computers, vol. 39, no. 6, 1990, pp. 775-785.

17. W.J. Dally, C.L. Seitz. Deadlock-free message routing in multiprocessor interconnection networks. // IEEE Transactions on Computers, vol. 36, no. 5, 1987, pp. 547-543.

18. W.J. Dally, P. Song. Design of a Self-Timed VLSI Multicomputer Communication Controller. // Proc. Int. Conf. Сотр. Design, IEEE CS Press, Los Alamitos, Calif., Order No. 2473, 1987, pp. 230 234.

19. R. Dittmann, F. Hiiebner. Discrete-Time Analysis of a Cyclic Service System with Gated Limited Service. // Research Report Series No. 67, Institute of

20. Computer Science, University of Wurzburg, June 1993, http://www-info3.informatik.uni-wuerzburg.de/TRytr067.pdf.

21. J.T. Draper, J.Ghosh. A comprehensive analytical model of wormhole routing in multicomputer systems. // Journal of Parallel and Distributed Computing, vol. 23, pp. 202-214.

22. J. Duato. A New Theory of Deadlock-Free Adaptive Routing in Wormhole Networks. // IEEE Transactions on Parallel and Distributed Systems, vol. 4, no. 12,1993, pp. 1320-1331.

23. J. Duato. A necessary and sufficient condition for deadlock-free adaptive routing in wormhole networks. // IEEE Transactions on Parallel and Distributed Systems, vol. 6, no. 10, 1995, pp. 1055-1067.

24. D. Everitt. A Note on the Pseudoconservation Laws for Cyclic Service Systems with Limited Service Disciplines, // IEEE Transactions on Communications, vol. 37, no.7, 1989, pp.781-783.

25. I. Foster. Designing and Building Parallel Programs. Addison-Wesley, 1995, ISBN-0-201-57594-9.

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

27. Guide to Myrinet 2000 Switches and Switch Networks, 2001, http://www.mvri.com/mvrinet/m3switch/guide.

28. S.C. Kim, S. Lee. Measurement and Prediction of Communication Delays in Myrinet Networks. // J. of Parallel and Distributed Computing 61, 1692 -1704,2001, pp. 1692-1704.

29. J.H. Kim, C.R. Das. Hypercube communication delay with wormhole routing. // IEEE Transactions on Computers, vol. 43, no. 7, 1994, pp. 806 -814.

30. S.C. Kim, S. Lee. Measurement and Prediction of Communication Delays in Myrinet Networks. // J. of Parallel and Distributed Computing, vol. 61, 2001, pp.1692-1704.

31. P.J. Kuhn. Multiqueue Systems with Nonexhaustive Cyclic Service. // Bell System Technical Journal, vol.58, no.3, March 1979, pp.671 — 698.

32. D.-S. Lee, B. Sengupta. An Approximate Analysis of a Cyclic Service Queue with Limited Service and Reservations. // Queueing Systems, 11, 1992, pp. 153-178.

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

34. N. MacDonald, E. Minty, M. Antonioletti, J. Malard, T. Harding, S. Brown. Writing Message-Passing Parallel Programs with MPI, http://www.epcc.ed.ac.uk/epic/mpi/notes/mpi-course-epic.book l.html.

35. B. Mahafzah, W. Cohen. Verification of the Burst Send Queuing System Model for Parallel Programs. // Proc. The Int't Conf. Parallel and Distributed Processing Techniques and Applications '99, 1999.

36. Myricom, Inc., http://www.myri.com.

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

38. O. Rose. Interdeparture Time Correlations of the Discrete-time GI/GI/1 Queue. // Research Report Series No. 204, Institute of Computer Science, University of Wiirzburg, May 1998, http://www-info3 .informatik.uni-wuerzburg.de/TR/tr204.pdf.

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

40. C.R. Seitz, W. Su. A Family of Routing and Communication Chips Based on the Mosaic. // Proceedings of the Symposium on Research on Integrated Systems, MIT Press, March 1993, pp. 320 337.

41. M. Snir, S. Otto, S. Huss-Lederman, D. Walker, J. Dongarra. MPI: The Complete Reference, http://www.netlib.org/utk/papers/mpi-book/mpi-book.html.

42. A.K. Venkatramani, Т.М. Pinkston, J. Duato. Generalized Theory for Deadlock-Free Adaptive Wormhole Routing and its Application to Disha Concurrent. // Proceedings of IPPS '96, The 10th International Parallel Processing Symposium, 1996, pp. 815-821.

43. T.B. Tabe, Q.F. Stout. The Use of the MPI Communication Library in the NAS Parallel Benchmarks // Tech. Rep. CSE-TR-3 86-99, Department of Computer Science, University of Michigan, Nov 1999.

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

45. I. Theiss and O. Lysne. Deadlock Avoidance for Wormhole Based Switches. // Proceedings of Euro-Par 2000, Lecture Notes in Computer Science, no. 1900, Springer-Verlag, 2000, pages 890 899.

46. The GM-1 Message Passing System, http://www.mvri.com/scs/GM/doc/refinan.pdf.

47. P. Tran-Gia. Analysis of Polling Systems with General Input Process and Finite Capacity. // IEEE Transactions on Communications, vol. 40, no. 2, 1992, pp.337-344.