Содержание к диссертации
Введение
ГЛАВА I. Сети передачи данных типа wormhole 14
1. Принципы организации сетей типа wormhole 14
2. Классификация-работ по моделированию сетей типа wormhole 18
2.1 Абстрактные модели параллельных вычислительных систем 18
2.2 Аналитические модели работы сетей типа wormhole 21
2.3 Системы имитационного моделирования сетей типа wormhole 24
ГЛАВА II. Система моделирования сетей типа wormhole 27
1. Концепция построения системы моделирования 27
2. Структура системы моделирования 28
2.1 Моделирование работы коммуникационной подсети 29
2.2 Моделирование работы оконечных устройств 31
2.3 Моделирование входной нагрузки 36
3. Калибровка модели 37
3.1 Калибровка модели оконечного устройства 38
3.2 Калибровка модели коммуникационной подсети 43
ГЛАВА III. Алгоритм расчёта средней задержки пакета в сетях передачи данных типа wormhole 47
1. Формальная постановка задачи 47
1.1 Структура сети и используемая технология передачи данных 47
1.2 Нагрузка на сеть 49
1.3 Маршрутизация в сети 50
1.4 Постановка задачи 51
2. Алгоритм расчёта 52
2.1 Разбиение сети на отдельные каналы и определение последовательности проведения расчётов 53
2.2 Применение метода анализа во множестве дискретных моментов времени для расчёта отдельного канала сети 57
2.3 Проведение расчёта средней задержки пакетов для всей сети 65
3. Проверка корректности алгоритма расчёта 72
ГЛАВА IV. Экспериментальная проверка алгоритма расчёта 75
1. Нагрузка на сеть, порождаемая реальными приложениями 76
2. Дополнительные параметры имитационной модели 78
3. Характеристика параллельного приложения 79
Заключение 84
Литература 85
Приложения
- Классификация-работ по моделированию сетей типа wormhole
- Моделирование работы коммуникационной подсети
- Структура сети и используемая технология передачи данных
- Дополнительные параметры имитационной модели
Введение к работе
Современный этап развития вычислительной техники характеризуется широким использованием сетей передачи данных, которые применяются при построении вычислительных комплексов, систем автоматизированного управления технологическими процессами, телекоммуникационных систем и т.д.. Необходимость в повышении производительности перечисленных комплексов и систем приводит к тому, что создаются новые и постоянно совершенствуются существующие методы передачи информации, протоколы и сетевые алгоритмы. В результате появляются новые сети, эффективное использование которых невозможно без проведения дополнительных исследований.
Объектом исследования настоящей работы является класс сетей передачи данных, использующих технологию передачи wormhole. Данный класс представлен множеством современных высокоскоростных пакетных сетей, примерами которых являются сети Myrinet, Servemet II, Sunfinity.
Традиционной областью применения рассматриваемого класса сетей является создание высокопроизводительных параллельных вычислительных комплексов — суперкомпьютеров с использованием кластерной архитектуры. Суть данного подхода состоит в том, что система строится из множества вычислительных модулей, которые соединяются высокоскоростной сетью. При работе подобного комплекса в проведении вычислений могут параллельно участвовать все либо некоторое подмножество вычислительных модулей, а сеть служит для обмена данными между ними в процессе решения задачи. В создаваемых кластерных вычислительных системах всё чаще используются сети передачи данных типа wormhole, например, из 500 самых быстрых суперкомпьютеров, более чем в 100 применяются сети данного класса, а 30 из них входят в первую сотню.
Основной особенностью сетей передачи данных типа wormhole является используемая в них технология передачи. К сожалению, в
отечественной литературе пока отсутствует устоявшийся перевод широко распространённого английского термина wormhole. Наиболее близким, по мнению автора, переводом может служить выражение «процесс создания червоточин». В подобных сетях применяется пакетная передача, то есть любая информация передаётся в виде пакетов данных. Каждый пакет можно представить в виде червя, который прокладывает себе путь по сети сквозь промежуточные узлы — коммутаторы. Пакет как бы растягивается по промежуточным узлам сети, последовательно занимая каналы от отправителя к получателю так, что в любой момент времени в любой точке присутствует только небольшая, неделимая единица данных - часть пакета, называемая «флит» (от английского flit — flow control unit). Обязательным условием является то, что один и тот же путь не может использоваться более, чем одним пакетом («червём»), то есть, если канал занят передачей, то пришедший вновь пакет блокируется и ожидает его освобождения. В этом случае передача данного пакета приостанавливается, но он не теряется и не освобождает уже занятых каналов сети. Движение пакета возобновляется после того, как соответствующий канал сети становится свободным. Таким образом, пакет целиком хранится только в момент отправки в узле-отправителе и в момент получения в узле-получателе [17,44].
Первый промышленный вариант сети класса wormhole (сеть Myrinet) появился сравнительно недавно, менее десяти лет назад, поэтому к настоящему моменту имеется ряд проблем, затрудняющих эффективное использование сетей указанного класса. Одна из основных проблем состоит в отсутствии методов и средств оценки и расчёта задержки пакета для сетей типа wormhole, то есть времени, которое пакет проводит в сети. Решение указанной проблемы является важным для эффективного использования сетей передачи данных, так как именно задержка пакета существенно влияет на пропускную способность системы. Действительно, пропускную способность можно определить как нагрузку, обслуживаемую сетью за единицу времени, или величину обратную времени приёма-передачи
информации в сети. Тогда очевидно, что в наиболее общем виде пропускная способность зависит от следующих параметров.
Ёмкость каналов сети, или скорость передачи каждого отдельного канала. Это физическая величина, которая является фиксированной для любой конкретной сети, её увеличение представляет собой задачу разработки сетевого оборудования и . нами не рассматривается.
Время, которое пакет проводит в ожидании в промежуточных узлах, обусловленное текущим состоянием сети: множеством абонентов, используемыми ими маршрутами передачи пакетов и нагрузкой, создаваемой на сеть.
Последняя характеристика является основной определяющей пропускной способности сети, её расчёт представляется необходимым для решения задач проектирования сетей, создания сетевого программного обеспечения, алгоритмов маршрутизации и т.п.. Очевидно, что задержка пакета есть случайная величина, поэтому целесообразно рассматривать среднюю задержку, которая, для любой конкретной сети с фиксированной ёмкостью каналов, является обобщённой характеристикой и, в конечном итоге, определяет пропускную способность системы. Таким образом, изучение средней задержки, способов её расчета и оптимизации является важнейшей задачей для любой сети передачи данных [2, 3, 8, 11].
Как отмечено в монографии [1], исследование любой системы сводится, по существу, к созданию её модели. Следовательно, моделирование, целью которого является изучение средней задержки пакета, представляет собой основу для проведения исследования производительности сети. Проведённый обзор работ по математическому моделированию сетей передачи данных типа wormhole позволяет сделать вывод о том, что имеется дефицит работ, посвященных их комплексному моделированию с целью изучения средней задержки пакета. Например, можно указать следующие недостатки имеющихся работ в данной области.
Отсутствует модель, которая, с одной стороны, обладает достаточной общностью для моделирования работы всего указанного класса сетей, а с другой, может использоваться для анализа конкретного сетевого оборудования и протоколов, применяемых на практике при построении подобных систем.
В существующих работах рассматривается ряд параметров для моделирования оконечных устройств, каналов связи и коммутаторов сети, но не содержится методов их калибровки по реальной системе.
В имеющихся работах, относящихся к аналитическому и численному моделированию рассматриваемого класса сетей, не представлен алгоритм расчёта такой характеристики, как средняя задержка пакета.
Таким образом, актуальной является задача разработки математических моделей сетей передачи данных типа wormhole с целью изучения средней задержки пакета в сети.
В работе [1] отмечено, что, в соответствие с применяемыми методами1 исследования, среди математических моделей можно выделить аналитические, численные и имитационные. Следовательно, сформулированная выше задача включает в себя подзадачи:
создания программных средств имитационного моделирования и
методов настройки этих средств на реальные сети;
создания алгоритма расчёта средней задержки пакета в сети.
Указанные подзадачи могут решаться отдельно, однако более
логичным и эффективным представляется их совместное рассмотрение. С одной стороны, численный расчёт средней задержки пакета в сети является сложной задачей, проблема точного решения которой обусловлена видом случайных процессов, протекающих в системе и их взаимозависимости. Подход, который чаще всего используется при её решении, состоит во
введении ряда упрощающих предположений, например, о независимости случайных процессов, и проведении расчёта средней задержки с использованием введённых упрощений [2, 3, 8, 11]. Естественным способом проверки корректности сделанных предположений и определения величины возникающей ошибки является применение имитационного моделирования [8]. С другой стороны, использование имитационной модели при решении любой практической задачи требует, во-первых, выполнения настройки и калибровки параметров по реальной системе, а во-вторых, проведения серии экспериментов, занимающей в определенных случаях значительное время, тогда как программная реализация алгоритма расчёта позволяет быстрее получить соответствующие показатели производительности сети. Кроме того, последняя может применяться и для систем, которые пока ещё только проектируются. Всё вышеизложенное позволяет сформулировать цель настоящей работы.
Целью настоящей работы является исследование и разработка программных средств моделирования и алгоритма расчета средней задержки пакета для сетей передачи данных типа wormhole.
Далее мы остановимся на некоторых возможных вариантах применения указанных программных средств и алгоритмов на практике.
Расчёт проектной производительности сетей передачи данных. В работе [2] отмечено, что расчёт проектной производительности информационно вычислительных систем необходим, поскольку сложность их конфигурации и функционирования сильно уменьшают возможности интуитивной оценки производительности. Нами было показано, что средняя задержка пакета является обобщённой характеристикой производительности сети. Следовательно, для оценки производительность системы уже на этапе проектирования, необходимо иметь методы и средства расчёта и оценки задержки пакета в сети.
Разработка оптимизирующих алгоритмов маршрутизации.
Как известно, двумя основными функциями алгоритма маршрутизации являются, во-первых, выбор маршрута для передачи пакета по сети и во-вторых, доставка пакета от отправителя к получателю [3]. Первую функцию маршрутизации, то есть выбор маршрута, обычно стараются реализовать таким образом, чтобы оптимизировать определённые характеристики сети. В работах [3, 4] и в ряде других, обсуждается алгоритм оптимальной маршрутизации. Суть его состоит в том, что, используя усреднённые нагрузки на линии сети, производится оптимизация средней задержки пакета при помощи выбора маршрутов передачи. Очевидно, что для создания подобного алгоритма необходимо иметь оценочные или расчётные формулы для средней задержки пакета в сети, чтобы использовать их в качестве целевой функции оптимизирующего алгоритма маршрутизации.
Оценка времени выполнения параллельных задач на
высокопроизводительных вычислительных комплексах.
Как было отмечено, сети передачи данных типа wormhole находят широкое применение при построении высокопроизводительных вычислительных комплексов. Любая задача, выполняющаяся в подобной системе, представляет собой набор параллельно работающих ветвей, взаимодействие между которыми происходит за счёт приёма и посылки сообщений по сети, посредством некоторого интерфейса передачи сообщений. Очевидно, что время выполнения задания зависит от задержки сообщений в сети, которую, в свою очередь, можно оценить при помощи соответствующих методов и средств оценки.
Построение систем управления прохождением заданий для
высокопроизводительных вычислительных комплексов.
Одной из составляющих программного обеспечения высокопроизводительных вычислительных комплексов является система управления прохождением заданий, в функции которой входит распределение ресурсов между поступающими в систему заданиями. Очевидно, что для эффективного функционирования всего вычислительного комплекса распределение . ресурсов необходимо проводить таким образом, чтобы нагрузка, создаваемая на различные каналы сети была распределена равномерно, а для этого можно использовать среднюю задержку пакета в каналах сети как показатель их загруженности. Таким образом, необходимо иметь методы и средства расчёта и оценки средней задержки пакета в каналах сети.
Диссертационная работа состоит из четырех глав.
В первой главе рассматриваются основные принципы организации сетей передачи данных типа womihole, а также дается обзор работ, близких к теме настоящего исследования. Данная глава состоит из двух параграфов. В первом параграфе излагаются принципы организации сетей рассматриваемого класса и обсуждаются особенности, к которым приводит использование указанных принципов при построении сетей. Второй параграф посвящен обсуждению работ, близких к теме настоящего исследования. Данный параграф состоит из трех частей. В первой части рассматриваются абстрактные модели параллельных вычислений, во второй содержится описание аналитических моделей работы сетей wormhole и близких к ним, третий посвящен обсуждению существующей имитационной модели типичного представителя сетей класса wormhole — сети Myrinet. Как показывает анализ, проведенный в первой главе, к настоящему моменту не существует, во-первых, имитационной модели, отражающей все особенности рассматриваемого класса сетей и включающей в себя метод
калибровки параметров по реальной системе, во-вторых, алгоритма расчета такой характеристики как средняя задержка пакета для сетей типа wormhole.
Во второй главе рассматривается система имитационного моделирования сетей передачи данных типа wormhole. Данная глава состоит из трех параграфов. В первом параграфе обсуждается концепция построения системы имитационного моделирования, второй параграф посвящен описанию структуры системы, в нём рассматривается подсистема моделирования коммуникационной подсети, подсистема моделирования оконечных устройств сети и подсистема моделирования входной нагрузки в сеть. Последний параграф содержит описание метода калибровки построенной модели, а также результаты применения этого метода для типичного представителя сетей класса wormhole — сети Myrhiet. Данный параграф состоит из двух частей, в первой описывается калибровка модели оконечного устройства, а во второй — модели коммуникационной подсети.
В третьей главе предложен алгоритм расчета средней задержки пакета для сетей передачи данных типа wormhole. Для рассматриваемых систем вводится ряд ограничений, основными из которых являются следующие.
Рассматриваются только системы, в которых невозможно возникновение тупиковых ситуаций взаимной блокировки нескольких пакетов.
Функционирование системы рассматривается в стационарном (устойчивом) режиме, при котором характеристики случайных процессов, протекающих в ней, не изменяются с течением времени.
Указанные предположения являются традиционными при проведении подобного анализа любых сетей передачи данных. Как показано в данной и последующей главах, введенные предположения могут применятся при исследовании реальных систем.
Третья глава состоит из трех параграфов. Первый параграф посвящен построению модели системы и формальной постановке задачи расчета средней задержки пакета в сети передачи данных типа wormhole. Данный
параграф состоит из четырех частей. В первой содержится формальное описание структуры исследуемых сетей и технологии передачи данных, во второй определяется способ задания входной нагрузки в сеть, третья посвящена описанию маршрутизации, применяемой при работе сети, четвертая содержит формальную постановку задачи построения алгоритма расчета средней задержки пакета в сети. Во втором параграфе описывается алгоритм расчета средней задержки пакета в сети. Данный параграф состоит из трех частей. В первой части рассматривается выбор последовательности анализа отдельных каналов сети, во второй части описаны основные положения применяемого метода анализа отдельного канала сети как системы массового обслуживания, третья часть посвящена описанию хода проведения расчетов средней задержки пакета в сети. В последнем параграфе содержится описание проведённых экспериментов для проверки предлагаемого алгоритма расчёта и сравнения результатов его работы и рассмотрен пример его работы.
Четвертая глава посвящена обоснованию практической применимости алгоритма расчета средней задержки пакета, изложенного в третьей главе. Для достижения данной цели была проведена серия экспериментов, в которой результаты имитационного моделирования сравнивались с результатами работы программной реализации алгоритма расчета. Для проведения данной серии экспериментов была собрана статистика и сформирована нагрузка на сеть путём анализа работы реальных приложений. Данная нагрузка, вместе с описанием сети, подавалась на вход системе имитационного моделирования, построенной и откалиброванной в соответствие с подходом, изложенным во второй главе настоящей работы. Результаты, полученные в ходе работы имитационной модели, сравнивались с результатами работы программной реализации метода расчета средней задержки пакета.
Четвертая глава состоит из трёх параграфов. В первом параграфе обсуждаются параллельные приложения, которые служат для формирования
входной нагрузки для сети. В качестве таких приложений использовались тесты SP и ВТ одного из наиболее распространённых пакетов тестирования высокопроизводительных вычислительных комплексов NAS Parallel Benchmarks [14]. Обе программы являются примерами реальных параллельных приложений, при этом существует несколько вариантов этих тестов (несколько классов), отличающихся друг от. друга размерностью решаемых задач. Для проведения экспериментов использовались тесты SP и ВТ класса А для 9, 16 и 25 параллельных ветвей. Во втором параграфе обсуждаются дополнительные параметры, которые необходимо ввести в имитационную модель, построенную во второй главе диссертации. Такими параметрами являются количество процессоров вычислительного модуля и правило формирования очереди ждущих пакетов в оконечном устройстве. В третьем параграфе обсуждаются характеристики работы реальных приложений и их вычисление с использованием построенного алгоритма расчета и параметров моделирования, предложенных и измеренных выше.
Классификация-работ по моделированию сетей типа wormhole
Современный этап развития вычислительной техники характеризуется широким использованием сетей передачи данных, которые применяются при построении вычислительных комплексов, систем автоматизированного управления технологическими процессами, телекоммуникационных систем и т.д.. Необходимость в повышении производительности перечисленных комплексов и систем приводит к тому, что создаются новые и постоянно совершенствуются существующие методы передачи информации, протоколы и сетевые алгоритмы. В результате появляются новые сети, эффективное использование которых невозможно без проведения дополнительных исследований.
Объектом исследования настоящей работы является класс сетей передачи данных, использующих технологию передачи wormhole. Данный класс представлен множеством современных высокоскоростных пакетных сетей, примерами которых являются сети Myrinet, Servemet II, Sunfinity.
Традиционной областью применения рассматриваемого класса сетей является создание высокопроизводительных параллельных вычислительных комплексов — суперкомпьютеров с использованием кластерной архитектуры. Суть данного подхода состоит в том, что система строится из множества вычислительных модулей, которые соединяются высокоскоростной сетью. При работе подобного комплекса в проведении вычислений могут параллельно участвовать все либо некоторое подмножество вычислительных модулей, а сеть служит для обмена данными между ними в процессе решения задачи. В создаваемых кластерных вычислительных системах всё чаще используются сети передачи данных типа wormhole, например, из 500 самых быстрых суперкомпьютеров, более чем в 100 применяются сети данного класса, а 30 из них входят в первую сотню.
Основной особенностью сетей передачи данных типа wormhole является используемая в них технология передачи. К сожалению, в отечественной литературе пока отсутствует устоявшийся перевод широко распространённого английского термина wormhole. Наиболее близким, по мнению автора, переводом может служить выражение «процесс создания червоточин». В подобных сетях применяется пакетная передача, то есть любая информация передаётся в виде пакетов данных. Каждый пакет можно представить в виде червя, который прокладывает себе путь по сети сквозь промежуточные узлы — коммутаторы. Пакет как бы растягивается по промежуточным узлам сети, последовательно занимая каналы от отправителя к получателю так, что в любой момент времени в любой точке присутствует только небольшая, неделимая единица данных - часть пакета, называемая «флит» (от английского flit — flow control unit). Обязательным условием является то, что один и тот же путь не может использоваться более, чем одним пакетом («червём»), то есть, если канал занят передачей, то пришедший вновь пакет блокируется и ожидает его освобождения. В этом случае передача данного пакета приостанавливается, но он не теряется и не освобождает уже занятых каналов сети. Движение пакета возобновляется после того, как соответствующий канал сети становится свободным. Таким образом, пакет целиком хранится только в момент отправки в узле-отправителе и в момент получения в узле-получателе [17,44].
Первый промышленный вариант сети класса wormhole (сеть Myrinet) появился сравнительно недавно, менее десяти лет назад, поэтому к настоящему моменту имеется ряд проблем, затрудняющих эффективное использование сетей указанного класса. Одна из основных проблем состоит в отсутствии методов и средств оценки и расчёта задержки пакета для сетей типа wormhole, то есть времени, которое пакет проводит в сети. Решение указанной проблемы является важным для эффективного использования сетей передачи данных, так как именно задержка пакета существенно влияет на пропускную способность системы. Действительно, пропускную способность можно определить как нагрузку, обслуживаемую сетью за единицу времени, или величину обратную времени приёма-передачи информации в сети. Тогда очевидно, что в наиболее общем виде пропускная способность зависит от следующих параметров.
Последняя характеристика является основной определяющей пропускной способности сети, её расчёт представляется необходимым для решения задач проектирования сетей, создания сетевого программного обеспечения, алгоритмов маршрутизации и т.п.. Очевидно, что задержка пакета есть случайная величина, поэтому целесообразно рассматривать среднюю задержку, которая, для любой конкретной сети с фиксированной ёмкостью каналов, является обобщённой характеристикой и, в конечном итоге, определяет пропускную способность системы. Таким образом, изучение средней задержки, способов её расчета и оптимизации является важнейшей задачей для любой сети передачи данных [2, 3, 8, 11].
Как отмечено в монографии [1], исследование любой системы сводится, по существу, к созданию её модели. Следовательно, моделирование, целью которого является изучение средней задержки пакета, представляет собой основу для проведения исследования производительности сети. Проведённый обзор работ по математическому моделированию сетей передачи данных типа wormhole позволяет сделать вывод о том, что имеется дефицит работ, посвященных их комплексному моделированию с целью изучения средней задержки пакета. Например, можно указать следующие недостатки имеющихся работ в данной области. Отсутствует модель, которая, с одной стороны, обладает достаточной общностью для моделирования работы всего указанного класса сетей, а с другой, может использоваться для анализа конкретного сетевого оборудования и протоколов, применяемых на практике при построении подобных систем.
Моделирование работы коммуникационной подсети
Анализ существующих систем и методов моделирования сетей передачи данных типа wormhole показывает, что к настоящему моменту не существует системы моделирования рассматриваемого класса сетей, которая обладает достаточной общностью, чтобы отразить работу любой сети данного класса, но при этом позволяет производить моделирование любого множества протоколов и архитектуры, используемых в той или иной реальной wormhole сети. Причиной этого служит отсутствие, во-первых, модели данного класса сетей, отражающей особенности работы оконечных устройств, коммутаторов и каналов связи wormhole сетей, а во-вторых, метода настройки подобной модели на реальную сеть. Обе указанные проблемы возникают на различных этапах моделирования [1].
Решение первой проблемы включает в себя выбор параметров модели и допущений о работе системы. Решение второй производится при помощи калибровки модели, которая представляет собой итеративный процесс сравнения модели с реальной системой, настройки или внесения изменений в модель, сравнение исправленной модели с реальной системой и т.д. [16]. Для проведения калибровки необходимо выбрать реальную систему. В качестве такой системы в настоящем исследовании используется типичный представитель сетей типа wormhole, сеть Myrinet, созданная фирмой Myricom, Inc., работающая под управлением сетевой оболочки GM, поставляемой той же фирмой вместе с исходными текстами.
Для реализации изложенной выше концепции, модель сети строится из трёх независимых подсистем, взаимодействие между которыми происходит через строго определённые интерфейсы. Для моделирования работы коммуникационной подсети используется модель, представляющая собой синтез одной из моделей организации передачи данных [12] и моделей работы wormhole коммутаторов [40, 44, 46]. Подсистема моделирования работы оконечных устройств отражает работу оконечных устройств сети Myrinet и построена с использованием документации на эту сеть, базового протокола работы сетевой оболочки, описанного в [18], документации к сетевой оболочке GM [53], распространяемой и поддерживаемой фирмой производителем сети, описания принципов работы сетевой оболочки [21], а также параметров, часть из которых описана в работах [13, 22, 23, 51], а часть предложена авторами. Подсистема моделирования входной нагрузки строится по принципу событийного управления, описанному в [19, 33], суть которого заключается в том, что нагрузка порождается событиями, возникающими в ходе работы реального приложения. Для проведения калибровки, используется реализация данной подсистемы опирающаяся на модель простого коммуникационного теста посылки - приёма сообщений, описание и исходные тексты которого поставляются вместе с сетевой оболочкой GM.
Коммуникационная подсеть задаётся ориентированным графом. Вершины графа являются узлами сети и могут принадлежать одному из двух типов: узлы с буферной памятью для хранения пакетов (оконечные устройства) и узлы, не имеющие таковой (коммутаторы). Коммутатор описывается множеством портов ввода и множеством портов вывода и способен обеспечить соединение любого свободного входа с любым свободным выходом, то есть является полносвязным. Относительно оконечных устройств в рассматриваемой подсистеме мы будем предполагать, что для их соединения с сетью служит единственный порт ввода и единственный порт вывода, и у любого оконечного устройства имеется буферная память для организации очереди пакетов. Объём буферной памяти является достаточно большим для того, чтобы не возникала ситуация переполнения. Последнее обусловлено тем, что нами не рассматривается ситуация возникновения перегрузки в сети, так как в этом случае задержка неограниченно возрастает и нет смысла обсуждать среднюю задержку пакета. Однако построенная система позволяет прогнозировать ситуации перегрузки в сети.
Любая информация передаётся в виде пакетов от одного оконечного устройства к другому через последовательность промежуточных коммутаторов. Первоначально пакет хранится в памяти оконечного устройства — отправителя, в очереди ждущих передачи пакетов. Перед отправкой по сети пакету приписывается некоторый маршрут движения, который фиксирован для любой пары оконечных устройств. При передаче пакета от отправителя до адресата устанавливается монопольное соединение, представляющее из себя непрерывную последовательность каналов, передающих единицы данных рассматриваемого пакета. Данное соединение существует только на время передачи одного пакета и для передачи следующего необходимо устанавливать соединение заново. В процессе установки соединения данные пакета хранятся в памяти узла — отправителя, а после установки соединения, пакет передаётся непосредственно из памяти узла - отправителя в память узла - получателя. Предполагается отсутствие задержек на распространение сигнала в каналах сети при установке соединения. Последнее упрощение объясняются тем, что данные задержки на порядок меньше, чем задержка на передачу данных пакета.
Если в процессе установки соединения некоторый канал сети, через который должен проследовать пакет, занят передачей, то возникает ситуация блокировки. Пакет прекращает своё движение, но не освобождает уже занятых им каналов. Далее пакет ожидает освобождения соответствующего канала и пытается его занять. Это может произойти не сразу, так как возможно существуют другие пакеты, ждущие освобождения рассматриваемого канала. При этом выбор пакета для передачи выходным каналом может осуществляться в соответствие с некоторым «правилом выбора входного канала». В модели предусмотрено три таких правила: круговой опрос (round-robin), использование одинаковых фиксированных приоритетов (fixed channel priority) и передача по правилу первым пришёл -первым передаётся (first come first served). Всё время ожидания данные пакета продолжают храниться в памяти оконечного устройства -отправителя.
Структура сети и используемая технология передачи данных
Для постановки задачи необходимо формально определить объекты, полностью описывающие процессы, протекающие в сети передачи данных. Мы воспользуемся традиционным подходом, принятым в теории сетей массового обслуживания, и определим: структуру сети и используемую технологию передачи данных; нагрузку на сеть; маршрутизацию в сети. Сеть задаётся при помощи ориентированного графа G = (u,v), где U-вершины (узлы сети), V- дуги (каналы связи). Множество вершин представляет собой объединение двух непересекающихся подмножеств U = UluU2tU}nU2=0, подмножества оконечных устройств С/, и подмножества коммутаторов U2. Будем предполагать, что каждый коммутатор является полносвязным в том смысле, что он способен соединить любой входной канал с любым выходным каналом, не занятым передачей, у любого оконечного устройства имеется единственный канал, соединяющий его с остальной сетью и топология сети фиксирована. Будем также считать, что для каждого отдельного канала известна скорость передачи или ёмкость, одинаковая для всех каналов сети.
Опираясь на обзор [44], суть технологии передачи wormhole можно сформулировать в виде следующих принципов. Для передачи каждого отдельного пакета между отправителем и получателем устанавливается монопольное соединение, представляющее из себя последовательность каналов сети, передающих единицы информации только данного пакета. Для передачи каждого нового пакета необходимо устанавливать соединение заново. При установке соединения возможно возникновение блокировки, при которой пакет приостанавливает своё движение, но не теряется и не освобождает уже занятых им каналов сети. После окончания блокировки пакет продолжает движение по сети. Если имеется несколько заблокированных пакетов, ожидающих освобождения одного и того же канала сети, то используется круговое правило выбора среди ждущих пакетов. Кроме того, для всех коммутаторов сети определён параметр время переключения (обозначим его J), представляющий из себя время, которое любой выходной канал любого коммутатора тратит при круговом просмотре на переход к следующему просматриваемому входному каналу. После установки соединения передача пакета представляет собой непосредственное копирование данных пакета из памяти узла — отправителя в память узла - получателя. Скорость передачи при этом равна скорости работы отдельного канала сети. При разрыве соединения каналы сети освобождаются последовательно по направлению от отправителя к получателю, сначала освобождается самый первый канал, непосредственно соединяющий узел отправитель с сетью, затем следующий канал и т.д. до последнего, идущего непосредственно к узлу получателю. При установке соединения и при его разрыве, который происходит, когда по каналам передачи проходит хвост пакета, отсутствуют задержки на распространение сигнала в каналах сети. Действие данного предположения можно проиллюстрировать на следующем примере. Предположим, что в сети имеется единственная пара абонентов; отправитель и получатель. Последнее предположение означает, что при прохождении заголовка пакета по каналам сети, происходящем при установке соединения, возникающие задержки связаны только с перекоммутацией каналов в промежуточных коммутаторах и обусловлены параметром коммутаторов время переключения d, описанным выше.
Будем считать, что выполняется ряд предположений, которые являются традиционными для проводимого нами анализа сетей передачи данных. Ёмкость буферной памяти у оконечных устройств является достаточно большой, чтобы память не переполнялась при работе сети. Данное предположение определяет то, что в сеть не поступает избыточного трафика, который последняя не способна принять полностью. Тем не менее, предлагаемый далее в настоящей работе алгоритм расчёта позволит предсказывать подобные ситуации. Множество абонентов и создаваемая ими нагрузка фиксированы и не изменяется в процессе функционирования сети. Последнее предположение обусловлено тем, что изменение множества абонентов и создаваемой ими нагрузки в рассматриваемых системах происходит относительно редко по сравнению со временем задержки пакета в сети вследствие высокой скорости работы каналов сети. Мы будем рассматривать стационарный режим работы, при которой сеть работает в устойчивом режиме, а характеристики случайных процессов, протекающих в системе, не изменяются со временем. 1.3 Маршрутизация в сети Будем полагать, что в сети используется статическая однопутевая маршрутизация, то есть для любой пары абонентов сети w = (j,k) фиксирован единственный путь pw=\jjjj,k\i2{j k),---,i„jj,k),k), который не меняется при функционировании сети. Все промежуточные узлы, образующие путь, являются коммутаторами, а узлы - абоненты -оконечными устройствами. Будем считать, что пути передачи выбраны таким образом, что в сети невозможно возникновение тупиковых ситуаций взаимной блокировки абонентов. Для формального определения задержки пакета в сети введём несколько дополнительных обозначений.
Рассмотрим любую пару абонентов сети w = (j,k), канал /, используемый данной парой абонентов, и коммутатор /є/г, для которого канал / является выходным. Обозначим через Т" Предлагаемый в настоящей работе алгоритм опирается на широко известный метод теории сетей массового обслуживания [3, 8], суть которого состоит в том, что сеть разбивается на отдельные каналы, после чего производится анализ работы каждого канала как независимой системы. Все действия при расчёте средних задержек в сети условно можно разбить на три этапа. 1. Определение последовательности, в которой будет производиться анализ отдельных каналов сети. Первый шаг призван определить зависимости между временами занятия отдельных каналов и учесть эти зависимости при работе алгоритма. 2. Анализ отдельных каналов сети как систем массового обслуживания. На втором шаге каждый канал рассматривается отдельно от остальных, после чего с помощью методов теории массового обслуживания производится расчёт задержки при занятии данного канала. Полученные результаты используются при анализе последующих каналов сети в порядке, определяемом п. 1. 3. Расчёт задержки пакетов на установку соединения и передачу данных для каждой пары абонентов и задержки в очереди ждущих пакетов для каждого оконечного устройства - отправителя производится с использованием результатов работы предыдущего шага алгоритма.
случайную величину — время, которое уходит на то, чтобы пакету данной пары абонентов занять канал / после того как заголовок пакета попал в коммутатор /, а через Lw -случайную величину - время, которое уходит у пакета данной пары абонентов w на то чтобы установить соединение между отправителем j и получателем к и передать данные пакета после установки.
Дополнительные параметры имитационной модели
Существует ряд исследований, посвященных изучению вида и характеристик подобной нагрузки. Среди них необходимо выделить работы [19] и [42]. В работе [19] для нескольких параллельных приложений показано, что время между двумя последовательными поступлениями сообщений от любой ветви параллельной программы может быть описано при помощи некоторого распределения вероятностей. В работе [42] построена модель работы параллельной программы, основная особенность которой состоит в использовании зависимых потоков сообщений. В данной модели рассматривается конфигурация ветвей параллельной программы, при которой каждый узел посылает сообщения четырем соседним с ним узлам, причем сообщения, адресованные различным соседям появляются в узле одновременно через промежутки времени, подчиняющиеся некоторому распределению вероятностей.
Во второй главе диссертационной работы был описан способ построения подсистемы моделирования входной нагрузки и формирования трассы статической нагрузки, возникающей в ходе работы реального приложения. Параллельное приложение, по которому формируется трасса входной нагрузки в сеть, должно быть выбрано таким образом, чтобы достаточно точно отражать производительность параллельной вычислительной системы. Мы будем рассматривать ряд параллельных приложений из пакета тестовых задач NAS Parallel Benchmarks [14]. Указанный набор тестов построен на основе реальных задач аэро динамики и получил в настоящее время наибольшую известность среди тестов производительности параллельных вычислительных комплексов [7].
В набор тестов NAS Parallel Benchmarks входит восемь параллельных задач, условные названия которых ВТ, FT, IS, LU, MG, SP, ЕР и CG. Пять тестов (FT, IS, MG, ЕР и CG) лежат в основе численных методов, используемых при решении задач аэродинамики, а оставшиеся три (ВТ, SP и LU) являются самостоятельными приложениями, которые соответствуют реальным задачам, решаемым при изучении аэродинамических процессов. Мы остановимся на двух программах ВТ и SP, которые и будем использовать для формирования трассы входной нагрузки в сеть. Данный выбор обусловлен тем, что, во-первых, оба они представляют собой реальный параллельные приложения, во-вторых, данные программы входят в набор тестов производительности параллельных вычислительных систем, в-третьих, формируемая ими нагрузка описывается достаточно просто, так как в ходе своей работы они используют в основном простейшие команды посылки и приёма сообщений [50]. Существует несколько различных вариантов данных тестов, отличающихся друг от друга размерностью решаемых задач. Для проведения экспериментов использовались тесты SP и ВТ класса А. Для формирования трассы выполнения параллельных программ воспользуемся информацией, собранное при запуске тестов SP и ВТ на вычислительном комплексе МВС-ЮООМ. Трассы работы отдельных параллельных ветвей преобразуются с учётом того, что на каждому двухпроцессорном вычислительном модуле выполняется по две параллельные ветви (кроме одного вычислительного модуля если количество параллельных ветвей нечётно). Ветви параллельной задачи, выполняющиеся на одном вычислительном модуле используют разделяемую память для передачи данных между собой, поэтому сообщения, направленные между «соседними» ветвями параллельной программы не создают дополнительной нагрузки на сеть. Таким образом, учитывая всё вышесказанное, может быть сформирована статическая нагрузка на сеть для проверки практической применимости предлагаемого метода расчёта средней задержки пакетов в сети. Данные параметры, наряду с уже введёнными во второй главе диссертационной работы, позволят полностью описать отдельные вычислительные узлы реальной вычислительной системы. Как уже было отмечено, для проведения калибровки нами использовался отечественный высокопроизводительный вычислительный комплекс МВС-1000М, поэтому значения указанных параметров также будут определяться указанным вычислительным комплексом. Необходимо подчеркнуть, что количество портов соединения вычислительного модуля с сетью мы на протяжении всей работы предполагаем равным единице (что соответствует реальной системе), поэтому соответствующий параметр не рассматривается.
Количество процессоров, соответствующих одному вычислительному модулю будем полагать равным двум, так как комплекс МВС-1000М построен с использованием двухпроцессорных вычислительных модулей. Правило формирования очереди ждущих пакетов в оконечном устройстве описано в документации на сетевую программную оболочку GM [53], используемую в указанном вычислительном комплексе. Суть данного правила состоит в следующем, для каждой пары абонентов сети (вычислительный модуль отправитель — вычислительный модуль получатель) определяется отдельное соединение. Каждому соединению соответствует отдельная очередь пакетов, ждущих передачи по данному соединению, происходит круговое сканирование данных очередей, в ходе которого из каждой очереди передаётся по одному пакету, в случае если очередь не пуста.
Проведение оценки задержки сообщения в сети требует рассмотрения для каждого оконечного устройства всех соединений, выходящих из него. Для каждого соединения необходимо вычислить среднюю задержку на установку соединения и отправку данных пакетов используя рассмотренный выше алгоритм расчёта. В качестве длины пакета необходимо использовать максимально возможную длину пакетов в сети, а в качестве интенсивности -среднюю интенсивность поступлений пакетов для каждой пары абонентов, полученную путём анализа трассы параллельной программы. Далее, используя упрощённую формулу необходимо оценить среднюю задержку сообщения Qm для любого соединения.
