Основные характеристики коммуникационных сред Предназначением любой коммуникационной среды является передача информации от некоторого отправителя (отправителей) к некоторому получателю (получателям). Передачу информации от одного отправителя к единственному получателю называют обменом «точка-точка», а к множеству получателей – широковещательным обменом. Производительность обмена «точка–точка» зависит от того, является ли этот обмен единственным в коммуникационной среде, или одновременно с ним выполняются другие обмены. Не только обмены с одними и теми же участниками (например, две одновременных посылки из двух разных ВМ в один), но и обмены между разными парами ВМ могут, вообще говоря, влиять друг на друга. При выполнении обмена (приема или передачи сообщения) вычислительным модулем, процесс обмена разделяется на два элементарных акта: запуск обмена и проверка завершения. В то время, когда обмен запущен, но еще не завершился, ВМ может выполнять некоторые расчеты. Производительность ВМ на фоне выполняющегося обмена может, вообще говоря, снижаться, поскольку идущий асинхронно обмен потребляет ресурсы ВМ: нагружает шину памяти, выставляет прерывания центральному процессору и т.п. Производительностью коммуникационной среды для обмена «точка–точка» будем называть количество данных, передаваемых в единицу времени, в среднем за некоторый относительно большой промежуток астрономического времени. Производительность коммуникационной среды можно представить себе как среднюю (за длительное время) скорость передачи данных. Очевидно, производительность сильно зависит от того, какой длины сообщения используются при передаче данных, то есть от того, какую часть времени коммуникационная среда тратит на запуск обменов. Пусть узел A передает узлу B сообщение длиной X байтов, и при этом никаких других обменов в среде не происходит. Время T, затрачиваемое на такую передачу, довольно точно оценивается формулой , | (5.10) | где L не зависит от X. Величину S в этой формуле называютпропускной способностьюкоммуникационной среды для обмена «точка–точка» или мгновенной скоростью передачи данных. Пропускная способность измеряется в байтах (мегабайтах) в секунду. Величину L называютзадержкойили латентностью. Латентность представляет собой время запуска обмена(т.е. время, затрачиваемое коммуникационной средой на подготовку к передаче информации), не зависящее от длины сообщения, и измеряется в секундах (микросекундах). Очень часто латентность определяют как время передачи сообщения нулевой длины. Главными факторами, влияющими на величину латентности, являются: · число копирований в промежуточные буферы; · быстродействие протокола установления соединения; · алгоритм маршрутизации в составных коммутаторах; · задержки на физическом уровне, связанные с быстротой срабатывания электронных схем. Иногда удобно оперировать латентностью, приведенной к пропускной способности, или ценой обмена, которую мы обозначим как P: Эта величина измеряется в байтах и может быть интерпретирована следующим образом. Цена обмена представляет собой то число байт, которое коммуникационная среда могла бы передать при обмене «точка–точка» за время своего запуска, т.е. за время задержки. Иными словами, за счет инертности коммуникационной среды, к каждому передаваемому ей сообщению «добавляется», с точки зрения пропускной способности, P байт. Таким образом, производительность коммуникационной среды зависит от длин передаваемых сообщений. Если X много больше P, то есть длины сообщений много больше цены обмена, производительность близка к пропускной способности. Напротив, если X много меньше P, производительность практически полностью определяется латентностью, а не пропускной способностью. Наконец, при X, равном P, производительность равна в точности половине пропускной способности. Тем самым, цена обмена – это такая длина сообщения, при использовании которой производительность коммуникационной среды при обмене «точка-точка» равна половине ее пропускной способности. Очевидно, коммуникационная среда тем лучше, чем выше пропускная способность, и чем ниже латентность. Следующей важной характеристикой коммуникационной среды является ее полнота. Содержательно, полнота среды есть мера того, насколько несколько одновременно происходящих обменов влияют друг на друга, снижая производительность. Простейшее определение полноты коммуникационной среды – это понятие бисекционной полноты: среда называется бисекционно полной, если любыеобмены между разными парами ВМ, происходящие одновременно и в любом количестве, не снижают производительности друг друга. Другими словами, при любом разделении коммуникационной среды пополам (бисекции) пропускная способность потока данных из одной половины в другую есть сумма пропускных способностей независимых каналов связи, ведущих из одной половины среды в другую. Типичный пример бисекционно неполной коммуникационной среды – сеть на базе двух однородных коммутаторов, объединенных между собой единственным каналом связи. Простые коммутаторы В настоящее время в мировой практике построения ВС существует большое разнообразие коммуникационных сред. При этом постоянно ведутся теоретические и экспериментальные исследования в области построения моделей коммуникационных сред, обладающих максимальной пропускной способностью и минимальной задержкой. Любая коммуникационная среда объединяет совокупность ВМ с возможностью передачи информации от одного ВМ к другому, т.е., другими словами, осуществляет функцию коммутации ВМ между собой. Поэтому в дальнейшем, в целях унификации рассмотрения различных коммуникационных сред, будем говорить о них как о коммутаторах. Коммутаторы бывают простые и составные, компонуемые из простых. Простые коммутаторы имеют малую задержку при установлении полнодоступных соединений, но в силу физических ограничений могут быть построены только для систем с небольшим числом вычислительных модулей. Для построения коммутаторов с большим числом входов и выходов развита теория составных коммутаторов, строящихся из простых путем объединения их в многокаскадные схемы линиями «точка-точка». Способы такого объединения разнообразны и зависят от требований, предъявляемых к коммутатору как элементу вычислительной системы. Простые коммутаторы бывают с временными пространственнымразделением. Простой коммутатор с временным разделением, называемый также шиной, используется, например, в SMP-серверах Power Challenge фирмы Silicon Graphics Inc. Простой коммутатор с пространственным разделением Gigaplane применяется фирмой Sun в семействе SMP-систем Sun Ultra Enterprise. Организация шин подробно рассматривалась в разделе, посвященном вводу-выводу в ЭВМ, поэтому здесь мы ограничимся напоминанием основных достоинств и недостатков шинных структур. К достоинствам шин следует отнести простоту реализации и малое количество аппаратного оборудования, необходимого для реализации. Кроме этого, шинные структуры в силу простоты отличаются высокой надежностью. Главным недостатком шинной организации является то, что шина представляет собой критический ресурс, за доступ к которому конкурируют абоненты. Неизбежные конфликты приводят к снижению производительности шины (прежде всего, увеличиваются задержки), она становится узким местом системы. В результате число шинных абонентов является ограниченным (при том весьма небольшим числом), что существенно сдерживает масштабирование ВС. Отметим, что локальные сети Ethernet и Token Ring с протоколами, использующими общую среду распространения сигналов, также служат коммутаторами с временным разделением и реализуют логический протокол шинной структуры. Коммутаторы с пространственным разделением способны соединить любой вход с любым одним выходом (ординарные) или несколькими выходами (неординарные). Каждое соединение входов и выходов выполняется разными частями аппаратуры, что и дало название этому типу коммутаторов. Коммутатор (рис. 5.18) представляет собой совокупность мультиплексоров, число которых равно числу выходов коммутатора. Количество входов коммутатора может быть произвольным. Каждый вход должен быть заведен на все мультиплексоры коммутатора. Достоинствами коммутаторов с пространственным разделением являются полнодоступность и минимальная латентность. К недостаткам следует отнести высокую сложность при большом числе входов и выходов, приводящую, как следствие, к существенному снижению надежности. Кроме этого, существуют ограничения по количеству выходов коммутатора, связанные с возможностями размножения входов для подсоединения к каждому мультиплексору. ![](http://konspekta.net/megapredmetru/baza1/21697137076.files/image248.gif) Рис. 5.18. Простой коммутатор mxm с пространственным разделением Составные коммутаторы Простые коммутаторы, как с временным, так и пространственным разделением, имеют ограничения по числу входов и выходов, а коммутаторы с пространственным разделением, кроме того, требуют для своего построения большого объема оборудования. Коммутаторы с большим числом входов и выходов можно построить из простых коммутаторов с меньшим числом входов и выходов путем объединения простых коммутаторов линиями «точка-точка». Объем оборудования составного коммутатора значительно меньше, чем у простого коммутатора с теми же количествами входов и выходов. Однако составные коммутаторы имеют задержку, как минимум, пропорциональную числу каскадов – числу простых коммутаторов, через которые передаваемая информация проходит от входа до выхода составного коммутатора. Как правило, составные коммутаторы строятся из простых коммутаторов nxn с n входами и n выходами. Если используется коммутатор с временным разделением, то коммутации входов с соответствующими выходами разносятся во времени. ![](http://konspekta.net/megapredmetru/baza1/21697137076.files/image250.gif) Рис. 5.19. Элемент составного коммутатора На рис. 5.19 представлена схема простого коммутатора, который можно использовать в качестве элемента для построения составного коммутатора. Тонкие линии представляют управляющие сигналы, двойные линии представляют входящие и выходящие информационные сигналы. Функционирование блока коммутации данных определяется значением управляющего сигнала блока управления, задающего, какой вход с каким выходом необходимо соединить. Блок управления вырабатывает управляющий сигнал и производит арбитраж запросов двух и более входов, если они желают соединиться с одним выходом. Запрос ri воспринимается на соответствующем входе блока управления, если есть сигнал 1 на соответствующей линии запроса i. При наличии значения 1 на линии запроса i, i Î {0, n-1} вход iблока коммутации соединяется с выходом, номер которого задается управляющим числом di на входе управление i. В случае конфликта, когда есть сигнал 1 на линии запроса i и на линии запроса j, di = dj, i < j,предпочтение отдается запросу ri, и вырабатывается сигнал занятости bj. Сигнал занятости передается коммутатору предыдущего каскада. При отсутствии конфликта или его разрешении в пользу ri блок управления коммутирует сигнал линии запроса i, i Î {0, n-1}, в соответствии с управляющим числом di, так, чтобы сигнал запроса был равен 1. Важным моментом функционирования блока управления является распространение сигнала занятости. Если сигнал на входе Bi, i Î {0, n-1}, равен 1, что происходит при конфликте в коммутаторе следующего каскада, то этот сигнал распространяется на выход j, для которого верно соотношение dj = i. Отметим, что простой коммутатор nxn может иметь или не иметь внутренней буферизации. Составной коммутатор создается путем объединения простых коммутаторов mxn, входы которых либо являются входами составного коммутатора, либо подключены к выходам одного или разных других простых коммутаторов. Оставшиеся при таком объединении свободными выходы простых коммутаторов служат выходами составного коммутатора. Структура такого составного коммутатора задается ориентированным графом, каждая вершина которого имеет m входящих ребер и n выходящих. Установление соединения входов с выходами называется коммутацией. Для установления коммутации требуется подать управляющие числа di на каждый вход каждого из простых коммутаторов, образующих составной. Последовательность управляющих чиселdi для простых коммутаторов каждого каскада будет образовывать маршрут соединения. Задача определения маршрутов возлагается на управляющий блок составного коммутатора. Составной коммутатор называется полнодоступным, если может быть установлено соединение любого входа с любым выходом. В противном случае, если хотя бы один вход не может быть соединен, по крайней мере, с одним выходом, то коммутатор является неполнодоступным. Коммутатор называется неблокируемым, если может быть установлено соединение свободных входа и выхода при наличии произвольного количества установленных соединений других входов и выходов. Если хотя бы одно такое соединение не может быть установлено, коммутатор называется блокируемым. Если для вновь соединяемых входа и выхода может быть установлено соединение путем перекоммутации уже существующих соединений с их сохранением, то такой коммутатор называется неблокируемым с перекоммутацией. Составные коммутаторы с числом входов N и выходов M могут быть построены с использованием различного числа по-разному соединенных друг с другом простых коммутаторов. Используемые простые коммутаторы могут иметь различное число входов и выходов. Критериями эффективности при построении составных коммутаторов являются следующие: · количество используемых простых коммутаторов (чем меньше, тем лучше); · количество коммутаторов, участвующих в соединении любого входа с любым выходом (число каскадов); · сложность алгоритма определения маршрутов и установления коммутации. Далее рассмотрим в качестве иллюстрации два часто встречающихся типа составных коммутаторов – коммутатор Клоза и баньян-сети. Коммутатор Клоза Коммутатор Клоза является составным трехкаскадным коммутатором с mxd входами и mxd выходами. Он формируется из m входных коммутаторов dxd, m выходных коммутаторов dxd и d промежуточных коммутаторов mxm. Правила соединения простых коммутаторов следующие (рис. 5.20): · k-й выход i-го входного коммутатора соединяется с i-м входом k-го промежуточного; · k-й вход j-го выходного коммутатора соединяется с j-м выходом k-го промежуточного. ![](http://konspekta.net/megapredmetru/baza1/21697137076.files/image254.gif) Рис. 5.20. Коммутатор Клоза Коммутаторы Клоза появились в 1953 году, регулярный алгоритм соединений был разработан в 1969 году. Коммутатор способен соединять любой вход с любым выходом, однако при уже установленных соединениях части входов и выходов добавление соединения еще одного входа и выхода может потребовать переустановления всех соединений. Таким образом, коммутатор Клоза является полнодоступным неблокируемым с перекоммутацией ординарным коммутатором. Достоинством схемы Клоза является простота и масштабируемость, достигаемые при сравнительно небольшом числе простых коммутаторов. Главным недостатком следует признать то, что коммутатор Клоза в некоторых случаях требует перекоммутации. На практике возможность перекоммутации часто не может быть реализована без потери передаваемых данных, что фактически делает коммутатор Клоза блокируемым. Баньян-сети При конструировании баньян-сетей преследовалась цель максимально упростить алгоритмы определения маршрутов и установления коммутации. Баньян-сети строятся на базе простых коммутаторов axb таким образом, что существует только один путь от каждого входа к каждому выходу. Рассмотрим баньян-сети на примере их важного подкласса – так называемых дельта-сетей, введенных Пателом в 1981 году. ![](http://konspekta.net/megapredmetru/baza1/21697137076.files/image256.gif) Рис. 5.21. Схема построения дельта-сети Дельта-сеть представляет собой n-каскадный коммутатор с an входами и bn выходами. Основой построения дельта-сети служат простые коммутаторы axb (рис. 5.21). Обозначим чрез Sqc q-тасовку q∙c объектов. Sqc(i)= q∙i mod(q∙c-1) для 0 ≤ i < q∙c-1; Sqc(i)= i для i = q∙c-1; | (5.12) | При построении an xbnдельта-сети межкаскадные соединения выполняются в соответствии с a-тасовкой. Тасуемыми объектамиявляются выходы коммутаторов очередного каскада. Каскады нумеруются числами 1, 2, …,n. Первый каскад состоит из an-1 коммутаторов и имеет b xan-1 выходов, что равно, соответственно, числу входов второго каскада. Второй каскад состоит из bxan-2 коммутаторов, i-й каскад состоит из bi-1x an-i коммутаторов. На рис. 5.22 представлен пример дельта-сети 23x23, построенной на основе коммутаторов 2x2. Показатель степени числа входов определяет число каскадов (в нашем случае – 3 каскада). Числа aи b равны 2 – основанию степени числа входов/выходов. Число q в формуле q-тасовки, поскольку в дельта-сети используется a-тасовка, определяется значением a (2). Между каскадами необходимо соединить 8 выходов предыдущего каскада с 8 входами следующего, т.е. тасуется 8 объектов. Отсюда определяется число c в формуле q-тасовки (тасуется q∙c объектов) – оно равно . Выходы будут соединяться со входами согласно значениям функции S24: S24(0)=0 S24(1)=2 S24(2)=4 и т.д. Дельта-сеть является полнодоступным неблокируемым ординарным коммутатором. Неблокируемость дельта-сети и простота установления коммутации (нетрудно вычислить единственный существующий маршрут между входом и выходом) являются достоинствами приведенной схемы. ![](http://konspekta.net/megapredmetru/baza1/21697137076.files/image260.gif) Рис. 5.22. Дельта-сеть 8x8 К недостаткам следует отнести: · большее, по сравнению со схемой Клоза, число простых коммутаторов при том же числе входов и выходов составного коммутатора; · для обеспечения большого числа входов и выходов дельта-сети требуется построение многокаскадного коммутатора (поскольку число входов и выходов простых коммутаторов ограничено), что увеличивает задержки. |