Software & Systems

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

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

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

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

Классификация работ по моделированию wormhole сетей и близких к ним

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

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

2.   Работы, содержащие концептуальные и аналитические модели работы wormhole сетей или близких к ним.

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

Рассмотрим более подробно указанные классы работ.

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

Как было отмечено ранее, сети передачи данных без промежуточной буферизации пакетов находят широкое применение при построении высокопроизводительных параллельных вычислительных комплексов. Таким образом, в контексте настоящего исследования интерес представляют модели параллельных систем, в которых имеются параметры, описывающие сеть передачи данных. Среди них необходимо отметить модели LogP [5,6], LogGP [3] и модель из работы [16]. Кроме указанных моделей, мы рассмотрим работу [4], в которой содержится анализ множества существующих программных оболочек и протоколов работы сетевого оборудования высокопроизводительных вычислительных комплексов.

На основе этого обзора также может быть построена модель параллельной вычислительной системы, аналогичная LogP, LogGP и модели из работы [16].

В моделях LogP [5] и LogGP [3] относительно сети передачи данных вводятся следующие предположения:

·          предполагается надежная работа сети;

·          сеть считается полносвязной;

·          используются только посылки сообщений типа точка–точка;

·          задержка, возникающая между любыми двумя узлами сети при посылке сообщения, не зависит от самих этих узлов.

Указанные модели основываются соответственно на четырех и пяти параметрах:

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

·          o – overhead (в модели представлено двумя параметрами  и  для отправителя и получателя соответственно) – накладные расходы, связанные с посылкой или приемом сообщения, то есть время, которое центральный процессор вычислительного модуля системы занят посылкой или приемом сообщения;

·          g – gap – пропускная способность сети для коротких сообщений, минимальный временной промежуток, между двумя последовательными отсылками или приемами сообщений;

·          G – gap per byte – пропускная способность для длинных сообщений, минимальный промежуток времени между отправкой двух последовательных байтов в длинном сообщении;

·          P – processors – количество процессоров в вычислительной системе.

Модель LogGP является расширением модели LogP посредством введения линейной зависимости задержки передачи сообщения от длины сообщения (параметр G).

Для калибровки модели используется простейший тест посылки–приема сообщений между двумя вычислительными модулями системы и производятся измерения соответствующих временных характеристик при различных входных нагрузках. Это достигается при помощи варьирования задержки между отправкой двух последовательных сообщений в узле-отправителе и позволяет определить все введенные выше параметры моделей [6].

По сравнению с моделями LogP и LogGP, модель из работы [16] имеет следующие особенности. Во-первых, любая передача данных разбивается на три стадии: отправка, передач по сети и прием. В работе [16] отмечено, что данные стадии присутствуют в большинстве коммуникационных оболочек, применяемых при построении сетей высокопроизводительных вычислительных систем. Параметры, описывающие каждую из стадий, имеют много общего с параметрами моделей LogP и LogGP, однако делается ряд предположений о возможности линейной зависимости данных параметров от длины передаваемого пакета на каждой их вышеуказанных стадий. Во-вторых, предпринимается попытка учесть возможность возникновения перегрузок в сети посредством замены всей сети некоторым абстрактным коммутатором, имеющим ограниченный буфер для хранения пакетов данных. При этом предполагается, что для обмена данными все узлы параллельной вычислительной системы подключены к одному глобальному коммутатору, у которого имеется буферная память ограниченного объема. В буферную память помещаются пакеты данных в случае, если некоторый ресурс, например канал связи, необходимый для их доставки, занят. Для описания перегрузки сети вводится дополнительный параметр , который отражает доступную буферную память глобального коммутатора.

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

Работы [3-6,16], рассмотренные выше, содержат общие параметры функционирования вычислительных модулей и сетей высокопроизводительных параллельных вычислительных комплексов. В них либо никак не отражается (LogP, LogGP), либо отражается слишком обобщенно (модель из работы [16]) работа каналов связи, коммутаторов и процессы, протекающие в сети передачи данных. Кроме того, в указанных моделях не рассматриваются характеристики поступающего в сеть потока данных и влияние сетевого оборудования на эти характеристики, например параллелизм, возникающий при работе различных компонентов оконечного устройства. Решением последней проблемы могла бы стать модель, опирающаяся на работу [4]. Таким образом, для исследования сетей передачи данных без промежуточной буферизации пакетов указанные модели прежде всего интересны с точки зрения моделирования работы оконечных устройств сети.

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

Основные вопросы, которые рассмотрим далее, относятся к функционированию коммутаторов и каналов связи.

Одно из наиболее полных описаний сетей передачи данных без промежуточной буферизации содержится в [14]. В данной работе наряду с общими вопросами функционирования и организации сетей обсуждаются возможные модели работы коммутаторов wormhole сетей. Важной характеристикой таких коммутаторов, как отмечается в [14], является так называемое правило выбора входного канала (input policy, или arbitration policy). Данное правило определяет, каким образом в момент освобождения некоторого выходного канала коммутатора производится выбор следующего пакета для передачи среди нескольких входных каналов, в каждом из которых имеется ждущий пакет. В данной работе указаны следующие возможные «правила выбора входного канала»:

·          круговой опрос (round robin) состоит в том, что все входные каналы коммутатора замыкаются в круг, и выбор следующего канала для передачи осуществляется среди ждущих каналов по кругу в некотором фиксированном направлении;

·          использование фиксированных приоритетов (fixed channel priority) при выборе входного канала предусматривает случайный выбор среди ждущих входных каналов в соответствии с некоторым дискретным распределением вероятностей, задающим приоритеты входных каналов;

·          первым пришел – первым передается (first come first served) – правило, при котором среди ждущих входных каналов коммутатора выбирается тот, который ожидает дольше всех остальных.

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

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

Одна из первых таких моделей обсуждается в [7]. В данной работе рассматриваются вопросы проектирования сетей без промежуточной буферизации пакетов. В качестве критерия оптимизации архитектуры сети используется средняя задержка пакета, которая вычисляется с учетом определенных предположений о множестве абонентов и создаваемой ими нагрузке на сеть. В работе предлагается методика расчета средней задержки пакета при занятии канала сети для частного случая, когда на канал поступает два входных потока пакетов. При этом любому пакету в случае возникновения блокировки при прохождении некоторого канала сети приходится сталкиваться с единственным пакетом другого потока. Данное положение выполняется только для сетей, в которых используются коммутаторы с небольшим количеством портов или в случае невысокой нагрузки на сеть. В работе [10] предложена модель, использующая комбинаторные свойства сетей, построенных по топологии гиперкуба, и применимая только к данному классу топологий. В [8] предложена аналитическая модель для n-мерных сетей с циклическими каналами по каждому измерению (k-ary n-cubes), построенная при помощи методов теории массового обслуживания. Исследование [12] содержит описание аналитической модели работы wormhole коммутатора с использованием кругового правила выбора входного канала и концептуальный план расчета производительности любой сети без промежуточной буферизации пакетов, в которой невозможно возникновение тупиковых ситуаций. Для расчета производительности сети в указанном исследовании используются свойства случайных процессов, протекающих в системе в случае ее устойчивой работы. В [11] рассматривается конкретный пример сети без промежуточной буферизации пакетов – сеть Myrinet. Целью работы является исследование задержки пакетов, а для достижения данной цели используются результаты серии экспериментов, проведенных авторами в реальной сети. При этом для определения задержки пакета эмпирически выбирается некоторая функция, а для проверки качества подобной оценки используются результаты экспериментов.

Анализ данного класса работ позволяет выявить общие черты построения wormhole сетей, особенности работы каналов связи и коммутаторов. Однако описанные выше модели имеют ряд недостатков. В большинстве из них используются различные эмпирические предположения о характере поступающей в сеть нагрузки, но при этом не учитываются особенности работы оконечных устройств сети, рассмотренные нами в предыдущем разделе настоящей статьи. Кроме того, модели работы коммутаторов и каналов связи даже в простейших случаях являются слишком сложными для проведения расчета и оценки производительности системы. Последнее приводит либо к рассмотрению некоторых строго определенных классов нагрузок на сеть и топологий сетей [7,8,10], либо к многочисленным упрощениям [12], либо к фиксации конкретной сети и настройке модели на эту сеть [11]. Таким образом, несмотря на достаточно большое количество исследований, существует явный дефицит работ, посвященных моделированию сетей без промежуточной буферизации пакетов, отражающих особенности функционирования оконечных устройств и не накладывающих значительных ограничений на топологию сети и поступающую в сеть нагрузку.

Системы имитационного моделирования реальных wormhole сетей

Рассмотрим систему моделирования типичного представителя класса сетей без промежуточной буферизации пакетов – сети Myrinet [13] и особенности системы имитационного моделирования данной сети [9].

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

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

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

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

·          Верификация аналитических предположений. В процессе построения системы [9] авторами делается ряд предположений о пропускной способности коммутаторов сети.

Адекватность этих предположений проверяется серией экспериментов.

·          Калибровка модели. Для калибровки модели использовалась нагрузка, создаваемая реальным параллельным приложением.

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

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

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

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

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

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

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

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

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

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

6.        Culler D.E., Liu L.T., Martin R.P., Yoshikawa C. LogP performance assessment of fast network interfaces. IEEE Micro, vol. 16, no. 1, pp. 35-43, February 1996.

7.        Dally W.J.. Performance analysis of k-ary n-cube interconnection networks. IEEE Transactions on Computers, vol. 39, no. 6, pp. 775-785, 1990.

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

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

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

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

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

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

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

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

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