Методы и средства исследования производительности сетей, использующих технологию передачи Wormhole тема диссертации и автореферата по ВАК РФ 05.13.11, кандидат физико-математических наук Веселов, Николай Александрович

• Веселов, Николай Александрович
• кандидат физико-математических наук
• 2004

Оглавление диссертации кандидат физико-математических наук Веселов, Николай Александрович

ВВЕДЕНИЕ.

ГЛАВА 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»

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

Объектом исследования настоящей работы является класс сетей передачи данных, использующих технологию передачи 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.

ЗАКЛЮЧЕНИЕ

Список литературы диссертационного исследования кандидат физико-математических наук Веселов, Николай Александрович, 2004 год

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.