Содержание к диссертации
Введение
ГЛАВА 1. Процедуры и устройства коммутации в многопроцессорных управляющих системах 12
1.1. Организация многопроцессорных систем логического управления 12
1.1.1 Структурная модель 12
1.1.2 Функциональная организация 20
1.2. Задача коммутации в многопроцессорных управляющих системах 22
1.2.1 Содержательная характеристика задачи коммутации 22
1.2.2 Влияние алгоритма управления на коммутацию 23
1.2.3 Варианты взаимодействия модулей управления и коллектива объектов управления 25
1.3- Коммутаторы для многопроцессорных управляющих систем 28
1.3.1 Статические коммутаторы 32
1.3.2 Динамические коммутаторы 45
1.4. Динамические коммутаторы с коммутацией пакетов 47
1.5. Коммутация в отказоустойчивых многопроцессорных управляющих системах.. 51
1.6. Выводы по главе 59
ГЛАВА 2. Процедура коммутации с распределенными выходными очередями для параллельных многопроцессорных систем логического управления 61
2.1. Содержательная постановка задачи 61
2.2. Формализованная постановка задачи 64
2.3. Процедура коммутации с распределенными выходными очередями 68
2.3.1. Общие особенности процедуры 68
2.3.2. Концептуально - логические основы процедуры 69
2.3.3. Функционирование предложенной процедуры, алгоритм коммутации 70
2.4. Анализ свойств процедуры коммутации 78
2.4Л. Исследование графа коммутации 78
2.3.2. Исследование процедуры на наличие тупиковых ситуаций 81
2.3.3. Оценка аппаратной сложности процедуры коммутации 81
2.5. Выводы по главе 83
ГЛАВА 3. Экспериментальное исследование процедуры с распределенными выходными очередями 84
3.1. Постановка эксперимента 84
3.2. Описание аппарата расширенных Q-схем 86
3.3. Архитектура библиотеки классов моделирования 92
3.4.,Q-схемы исследуемых коммутаторов 102
3.5. Анализ результатов моделирования 112
3.6. Выводы по главе 129
ГЛАВА 4. Аппаратная реализация коммутатора 130
4.1. Функциональная схема базового модуля коммутации 130
4.2. Построение масштабируемого коммутатора 141
4.3. Коммутатор отказоустойчивой многопроцессорной системы логического управления 148
4.4. Выводы по главе 156
Заключение 157
Список литературы 159
Приложение 1.
- Задача коммутации в многопроцессорных управляющих системах
- Процедура коммутации с распределенными выходными очередями
- Описание аппарата расширенных Q-схем
- Построение масштабируемого коммутатора
Введение к работе
Актуальность темы. Параллельные многопроцессорные системы логического управления (МСЛУ) - одно из перспективных направлений развития систем управления сложными процессами и коллективами процессов. Разработкой подобных систем занимаются ведущие мировые производители вычислительной техники: Siemens AG, ADVANTECH, Allen-Bradley, Weidmuller, Schneider electric. Данные системы позволяют решать круг задач управления, где необходима высокая динамика регулирования, точность вычислений и обширная функциональность, таких как: регулирование крутящего момента, частоты вращения и позиционирования в приводах постоянного и переменного тока; высокодинамичные гидравлические приводы; регулирование синхронности вращения; работа компенсирующих валиков; регулирование натяжения в работе наматывающих устройств; приводы с несколькими двигателями; испытательные стенды для редукторов и двигателей; комплексный расчет заданных значений и регулирование поперечной резки; «прочные» электрические валы; особые условия применения выпрямителей тока, например, при регулировании тока возбуждения, в работе высоковольтных агрегатов постоянного тока, в статических установках компенсации реактивного тока. Использование подобных систем позволяет достичь высокой оперативности управления, однако их возможности ограничены коммутационной составляющей.
Существующие лучшие системы, такие как Simatic S-300 (S-400), с модулями SYMADYN D обеспечивают коммутацию лишь 24x24 интерфейсных 32-сигнальных модулей, что не позволяет должным образом реализовать управление сложными объектами, такими как железопрокатные станы, технологические установки, где используется многоуровневая обратная связь. Кроме того, использование внутренней шины в качестве межмодульного коммутатора в приведенных системах не обеспечивает достаточного уровня надежности. Это не позволяет применять подобные системы в управлении производством, простой которого вызывает большие экономические потери,
например, в процессе обработки ценных материалов (фармацевтическая промышленность); в системах с высокими затратами на перезапуск производства в случае отказа контроллера; в системах без постоянного контроля со стороны обслуживающего персонала; в системах с небольшим количеством обслуживающего персонала.
Существующие динамические коммутаторы, применяемые в различных сферах вычислительной техники, имеют предел в размерах коммутатора -32x32, сложные весовые алгоритмы и централизованную схему управления, что делает невозможным их применение в подобных системах.
В связи с этим актуальной проблемой теории и практики параллельных систем логического управления является создание коммутаторов с минимальной задержкой обмена сообщениями между объектом управления и модулями управления, высоким уровнем отказоустойчивости и теоретически неограниченной масштабируемостью. При этом сложность аппаратно-программной составляющей должна сохранятся на приемлемом уровне.
Предметом исследования являются процессы высокоскоростной коммутации коллективов модулей и объектов управления параллельной многопроцессорной системы логического управления при увеличении ее масштабируемости и отказоустойчивости.
Работа выполнена в соответствии с программой П.Т.614 "Многопроцессорные ЭВМ с параллельной структурой и системы виртуальной реальности", приказ Министерства общего и профессионального образования Российской Федерации №572 от 2.03.98 г.
Основная часть диссертационной работы выполнена в рамках плана научно-исследовательских работ Курского государственного технического университета по единому заказ-наряду Министерства образования Российской Федерации в 1998-2003 годах, утвержденному начальником управления планирования и финансирования научных исследований.
Целью работы является обеспечение высокоскоростного взаимодействия модулей и объектов управления параллельной многопроцессорной системы
7 логического управления, при повышении ее масштабируемости и
отказоустойчивости на основе разработки коммутатора с распределенными
выходными очередями.
Основными задачами являются:
Анализ возможностей повышения быстродействия, масштабируемости и отказоустойчивости существующих процедур коммутации и коммутаторов на их основе.
Разработка процедуры коммутации, обеспечивающей высокоскоростное взаимодействие модулей и объектов управления при повышении масштабируемости и отказоустойчивости параллельных МСЛУ.
Создание коммутатора, реализующего разработанную процедуру коммутации.
Аналитическое и экспериментальное исследование характеристик разработанных процедуры и коммутатора.
Научная новизна результатов, полученных в диссертационной работе, заключена в следующем:
1. Проведен анализ быстродействия, масштабируемости и
отказоустойчивости существующих процедур коммутации и требований МСЛУ
к сети связи с объектами управления.
Созданы алгоритм и процедура коммутации с распределенными выходными очередями, обеспечивающие максимизацию числа пар коммутируемых абонентов (мощности множества ребер графа коммутации) и отсутствие тупиковых ситуаций при обработке сообщений с разными характеристиками потоков,
Получены зависимости средней и максимальной задержки сообщений, а также количества потерянных сообщений от интенсивности потоков поступающих сообщений для равновероятного и неравновероятного распределений получателей сообщений, подтвердившие увеличение скорости взаимодействия.
4. Разработан способ увеличения размера коммутации на основе
процедуры коммутации с распределенными выходными очередями, что позволяет создать коммутатор с теоретически неограниченной масштабируемостью.
5. Подтверждена возможность применения разработанной процедуры
коммутации в коммутаторе отказоустойчивой системы логического
управления, использующей метод скользящего резервирования со сдвигом.
Методы исследования основаны на использовании математического аппарата и методов теории графов, теории надежности технических систем, теории проектирования автоматов и дискретных схем, теории топологического проектирования однородных структур, теории систем массового обслуживания.
Практическая ценность диссертационной работы заключена в следующем:
1. Разработаны алгоритм и процедура коммутации, позволяющие
увеличивать масштабируемость и отказоустойчивость параллельной МСЛУ без
ограничений, присущих известным методам.
Коммутаторы, реализованные на основе созданной процедуры, позволяют уменьшить среднее время задержки на 2-5% по сравнении с известными.
На основе разработанной процедуры предложены структурные и функциональные схемы: базового модуля коммутатора, обеспечивающего коммутацию в соответствии с графом максимальной коммутации, масштабируемого коммутатора, пригодного для построения коммутаторов с размером коммутации более 1024x1024 в одном каскаде, коммутатора отказоустойчивой МСЛУ, обеспечивающего динамическую перекоммутацию коллектива объектов управления и коллектива модулей управления, начавших исполнение новых алгоритмов после отказов модулей.
4. Усовершенствован аппарат Q-схем в части имитационного
моделирования коммутаторов и коммутационных процедур, реализованный в
библиотеке классов для исследования характеристик коммутационных
процедур и коммутаторов.
9 Основные технические решения защищены патентами (№2175144,
№2175146).
Реализация и внедрение. Результаты диссертационной работы были использованы в учебном процессе Курского государственного технического университета и внедрены на предприятиях, в частности, в ООО «Компания ДЕМОС», г. Москва и ЗАО «Агентство сетевых технологий», г. Москва, что подтверждается соответствующими актами.
Апробация работы. Основные положения диссертационной работы докладывались и получили положительную оценку на 4-й МНТК «Новые информационные технологии и системы» (г. Пенза, 2000), на межвузовской электронной НТК «Управляющие и вычислительные системы. Новые технологии» (г. Вологда, 2001), на Всероссийской ЭНТК «Компьютерные технологии в науке, проектировании и производстве» (г. Н. Новгород, 2000), на 2-й Всероссийской НТК «Компьютерные технологии в науке, проектировании и производстве» (г. Н. Новгород, 2000), на 5-й МЭНК «Современные проблемы информатизации в непромышленной сфере и экономике» (г. Воронеж, 2000), на IV Международной научно-технической конференции «Медико-экологические информационные технологии - 2001» (г. Курск 2001) и на научно-технических семинарах кафедры «Вычислительная техника» Курского государственного технического университета с 1999 по 2003 гг.
Публикации. Основные результаты диссертационной работы опубликованы в трех статьях, 8 тезисах и материалах докладов и защищены 3 патентами на изобретения. В работах, опубликованных в соавторстве, лично соискателем предложены: в [48,55,56] - основные критерии анализа существующих моделей коммутации, в [50,57] - алгоритм и процедура коммутации с распределенными выходными очередями, в [52] - способ увеличения размера коммутации, в [53] - техническое решение, реализующее разработанную процедуру в отказоустойчивой МСЛУ, в [37,47,49,51,54,60,61] -отдельные решения построения масштабируемых, отказоустойчивых коммутаторов МСЛУ.
На защиту выносятся:
1. Алгоритм и процедура коммутации с распределенными выходными
очередями.
Способ увеличения размера коммутации на основе коммутатора, реализующего процедуру коммутации с распределенными выходными очередями.
Структурные и функциональные схемы базового модуля коммутации, масштабируемого коммутатора, коммутатора отказоустойчивой параллельной МСЛУ, основанные на процедуре коммутации с распределенными выходными очередями.
Результаты аналитического и экспериментального исследования характеристик разработанной процедуры и коммутаторов.
Объем и структура работы. Диссертационная работа состоит из введения, четырех глав, заключения, списка литературы и приложений. Общий объем диссертации составляет 220 страниц, включая 50 рисунков, 4 таблицы, список литературы из 144 наименований.
Во введении к диссертации обоснована ее актуальность, сформулированы цель и задачи исследований, научная новизна, практическая ценность, основные научные положения, выносимые на защиту, и приведено краткое содержание каждой из глав.
В первой главе рассмотрена структурная и функциональная организация параллельных многопроцессорных систем логического управления, исследовано влияние алгоритмов управления и связности коллективов модулей управления и объектов управления на подсистему связи с объектами управления, проведен анализ существующих коммутаторов, рассмотрены перспективные модели динамических высокоскоростных коммутаторов, проанализирована организация отказоустойчивой многопроцессорной системы логического управления с использованием метода скользящего резервирования со сдвигом.
Во второй главе приведена формализованная постановка задачи синтеза процедуры коммутации, представлены общие особенности процедуры
коммутации с распределенными выходными очередями, рассмотрены концептуально - логические основы процедуры и алгоритм коммутации, проведено аналитическое исследование графа коммутации процедуры, анализ процедуры на наличие тупиковых ситуаций, исследование аппаратной сложности процедуры.
В третьей главе представлены результаты экспериментального исследования свойств разработанной процедуры коммутации. Описана постановка эксперимента, усовершенствован аппарат Q-схем для имитационного моделирования, архитектура библиотеки классов моделирования, Q-схемы исследованных моделей коммутационных процедур. Получены зависимости средней задержки, максимальной задержки сообщений, количества потерянных сообщений от интенсивности потока входящих сообщений.
В четвертой главе описана аппаратная реализация процедуры коммутации с распределенными выходными очередями, в частности, базовый модуль коммутации, масштабируемый коммутатор и коммутатор отказоустойчивой МСЛУ.
В заключении приведены основные результаты, полученные в диссертационной работе.
Области возможного применения. Результаты диссертационной работы могут найти применение при построении параллельных многопроцессорных систем логического управления, к которым предъявляются повышенные требования в части обмена между коллективом объектов управления и модулями управления и сложности управляющих алгоритмов, а также обеспечения надежности и непрерывности функционирования в условиях отказов отдельных элементов. Областью применения параллельных МСЛУ являются системы логического управления станочными и робототехническими комплексами, сборочными автоматами, энергетическими установками, АСУТП низового уровня, системами сбора, контроля и обработки данных в электроэнергетике. Помимо основной области использования возможно применение разработанной процедуры коммутации в центральных коммутаторах узлов связи WAN, мобильных и спутниковых сетей.
Задача коммутации в многопроцессорных управляющих системах
Задача коммутации МСЛУ и коллектива объектов управления состоит в обеспечении эффективного отказоустойчивого сопряжения коллектива модулей управления с коллективом объектов управления. Из приведенной выше модели функционирования МСЛУ следует, что цикл управления (фазы Фг-Фв) существенно влияет на качество управления в МСЛУ: чрезмерное увеличение длительности цикла управления неизбежно приводит к снижению качества управления. Это объясняется следующими причинами. Во-первых, управляющее воздействие, выдаваемое через большой промежуток времени после получения порождающих его сигналов логического условия, строго говоря, уже не соответствуют состоянию системы (устаревает). Если для снижения эффекта старения информации применяется прогнозирование состояния системы (экстраполяция), то большая длительность цикла управления приводит к накоплению значительной ошибки экстраполяции. Во-вторых, при большой длительности цикла управления снижается частота выдачи управляющего воздействия коллективу объектов управления, что затрудняет согласование работы управляющего устройства с динамическими свойствами объектов управления с точки зрения характера переходных процессов [1].
Таким образом, одно из основных требований, которому должны удовлетворять средства обеспечения взаимодействия МСЛУ и коллектива объектов управления, заключается в том, чтобы время, необходимое для обмена сигналами между любой парой МУ-ОУ было меньше периода цикла управления.
Функциональные свойства средств сопряжения, в основе которых лежиткоммутатор, в целом определяются не только архитектурными особенностями ипараметрами элементной базы, но и в не меньшей степени принципамипостроения коммутатора. Недостаточная пропускная способность,значительное время прохождения сигналов, невысокая надежность, а такжевысокая сложность и стоимость коммутатора значительно могут снизитьэффект от применения многопроцессорной системы логического управления.
Требование к быстродействию коммутатора сети связи с объектами управления (минимума средней задержки сообщений), хотя и являются основным, но не является единственным. Другим немаловажным требованием является обеспечение необходимой интенсивности загрузки коммутатора ССОУ.
Определение 1.1. Интенсивность загрузки коммутатора ССОУ, 0, -количество одновременно занятых каналов связи коммутатора между множествами ОУ и МУ, задействованных в алгоритме управления.
Интенсивность загрузки коммутатора ССОУ состоит из двух составляющих: алгоритмической и пространственной.
Определение 1.2. Алгоритмическая составляющая, аь - количество одновременно исполняемых ветвей алгоритма управления.
Определение 1.3. Пространственная составляющая, ( - сумма степени связности МУ к ОУ и степени связности ОУ к УМ.
Определение 1.4. Степень связности МУ к ОУ, аму2, - количество МУ, одновременно формирующих сигналы управляющего воздействия для одного ОУ.
Определение 1.5. Степень связности ОУ к МУ, а у2, - количество ОУ,одновременно формирующих сигналы логического условия для одного МУ.0=счх(аму2 + аоу2). Для анализа интенсивности загрузки коммутатора ССОУ рассмотрим варианты взаимодействия коллектива МУ и коллектива ОУ при различных типах алгоритма управления, которые реализуется системой логического управления. Для систем логического управления можно выделить пять типов алгоритма управления (рис.1.7) [14,15,16].1. Последовательный алгоритм управления (рис. 1.7(a)). В каждый момент функционирует только один МУ. Взаимодействие в любой момент времени осуществляется только между одним МУ и одним (несколькими) ОУ (минимальная загрузка ССОУ). Межмодульный информационный обмен в любой момент времени осуществляется только между двумя МУ (C7i=l).2. Параллельный алгоритм управления без взаимодействующих ветвей (рис. 1.7(6)). Каждый МУ реализует независимый частный алгоритм управления. В каждый момент времени осуществляется обмен сигналами между множеством модулей управления и коллективом объектов управления (максимальная загрузка ССОУ), Взаимодействие между МУ отсутствует (ai=N).3. Параллельный асинхронный алгоритм управления (рис. 1.7(B)). Множество параллельных ветвей алгоритма может выполняться параллельно, но отсутствует синхронизация их завершения. В каждый момент времени осуществляется обмен сигналами между частью множества модулей управления и коллективом объектов управления (средняя загрузка ССОУ). Возможно параллельное взаимодействие пар МУ (ai=N-a, где (N-a) - число параллельно функционирующих ветвей управляющего алгоритма).4. Параллельный алгоритм управления (рис.1.7(г)). Завершение множества параллельных ветвей синхронизируется. В каждый момент времени осуществляется обмен сигналами между частью множества модулей управления и коллективом объектов управления (средняя загрузка ССОУ).
Возможно параллельное взаимодействие пар МУ (cj=N-a, где (N-a) - числопараллельно функционирующих ветвей управляющего алгоритма).5. Параллельный алгоритм управления с «мостиками» (рис. 1,7(д)). В каждый момент времени осуществляется обмен сигналами между частью множества модулей управления и коллективом объектов управления (средняя загрузка ССОУ) (ai=N-a, где (N-a) - число параллельно функционирующих ветвей управляющего алгоритма).
Для анализа пространственной составляющей интенсивности загрузки коммутатора ССОУ рассмотрим варианты взаимодействия модулей управления с коллективом объектов управления:1. Один к одному (рис. 1.8(a)). Каждый модуль управления формируетсигналы управляющего воздействия только для одного объекта управления,каждый объект управления формирует сигналы логического условия только для/ МУ і ОУ і лодного модуля управления (а г =1; ? 2=1 )2. Один к нескольким (рис, 1.8(6)). Каждый модуль управления формирует сигналы управляющего воздействия для нескольких объектов управления, каждый объект управления формирует сигналы логического условия только для одного модуля управления (a j = N-J3; а( У2=1, где (N-(3) - число параллельно управляемых объектов управления).3. Несколько к одному (рис.1.8(B)). Каждый модуль управления формирует сигналы управляющего воздействия только для одного объекта управления, каждый объект управления формирует сигналы логического условия для нескольких модулей управления (с г 1; с У2= N-х, где (N-%) -число параллельно получающих сигналы логического условия модулей управления).
Процедура коммутации с распределенными выходными очередями
Предлагаемая процедура коммутации базируется на следующих правилах;Правило 1.Сообщения, приходящие со входов Ij помещаются в выходные распределенные очереди Q выходов Oj, являющихся точкой назначения для сообщений.Правило 2. Каждая распределенная выходная очередь обеспечивает одновременную запись сообщений, поступающих с входов I,.Правило 3.
При наличии сообщений в выходной очереди ( обеспечивается передача одного из них на выход Oj.Правило 4.
Выходные распределенные очереди Qj независимы друг от друга.Данные правила определяют особенности созданной процедуры, развитые в концептуально-логические основы процедуры и алгоритм коммутации.Рассмотрим предлагаемую процедуру коммутации с распределенными выходными очередями. Она иллюстрируется схемой коммутатора на рис.2.2. Коммутатор содержит следующие компоненты: N входов и N выходов, N модулей выбора направления передачи сообщения, N указателей головы очередей, матрицы регистров, N указателей головы выходных очередей.
Рассмотрим назначение каждого модуля.Вход коммутационной сети I; предназначен для приема сообщения, которое посредством работы КС будет передано на выход-получатель сообщения Oj. Обозначим Ау(п) - функцию поступления (arrival function) на вход І; сообщения, предназначенного для передачи на выход Oj. Отсюда следует, что Aj(n) - суммарная (агрегированная) функция поступления сообщений на вход І;. Отсчет времени п поступления сообщений будем представлять дискретно, отмеряя шаг дискретизации как возможность приема одного сообщения на вход Ij. Xg - вероятность появления сообщения Ад(п). A(n) = {Aij(n); l i N, l j N} - общий суммарный трафик коммутационной сети.
Модуль выбора направления передачи сообщения на рис. 2.2 обозначен шестиугольником. Сообщение, поступившее на вход коммутационной сети, попадает на вход модуля выбора направления передачи сообщения, который на основании выхода-получателя обеспечивает помещение сообщения в распределенную очередь матрицы регистров.
Указатель головы очереди, обозначенный на рис. 2.2 кружком, определяет в какой регистр распределенной очереди будет произведена запись сообщения. Указатели головы очереди сгруппированы по номерам модулей выбора передачи сообщения.
Матрица регистров предназначена для хранения распределенных выходных очередей и играет роль буферного элемента при невозможности передачи сообщения из-за занятости выхода. Каждая строка матрицы регистров j представляет собой распределенную выходную очередь выхода Ог Внутри каждой строки распределены чередованием элементов очереди сообщений, поступивших с каждого входа для передачи их на выход Oj. Чередование элементов очереди выполнено следующим образом - первый регистр принадлежит первой очереди, второй регистр - второй очереди, ..., N-ый регистр - N-ой очереди, N+1 регистр - первой очереди, N+2 регистр - второй очереди, N+N регистр - N-ой очереди, и т.д.
Указатель на голову выходной очереди обозначен треугольником. Он предназначен для управления порядком выдачи сообщения из выходных распределенных очередей матрицы регистров во избежание переполнения.Выходы коммутационной сети обеспечивают выдачу сообщений модулям управления (объектам управления) - получателям сообщений.
Определение 2.1. Передача сообщения является возможной, если как вход коммутатора, так и выход не являются постоянно занятыми, т.е. сумма вероятностей поступления сообщений с любого входа на любой выход должна быть меньше единицы:Определение 2.2. Трафик называется равновероятным, если вероятности поступления сообщений равны и адреса-получатели равновероятно распределены между всеми выходами О. В противном случае трафик не является равновероятным.
Определение 2.3. Трафик называется независимым и равномерно распределенным тогда и только тогда, когда:1. Каждая функция поступления сообщений независима от других функций поступления сообщений.2. Все функции поступления сообщений имеют одинаковый закон распределения.
Рассмотрим функционирование предложенной процедуры. Процедуру можно разбить на две составляющие: формирование распределенных выходных очередей сообщений и алгоритм коммутации, осуществляющий выдачу сообщения на выходы коммутационной сети. К первой относятся N входов коммутационной сети, N модулей выбора направления передачи сообщения, N указателей головы очередей и матрица регистров. Ко второй можно отнести матрицу регистров, N указателей головы выходных очередей, и N выходов коммутационной сети.Рассмотрим более подробно формирование распределенных выходных очередей сообщений. В начале функционирования процедуры п=0, распределенные выходные очереди матрицы регистров пусты, каждый указатель головы выходных очередей указывают на свой первый регистр.
Сообщение Ау(1) в момент п = I поступает на і-й вход и соответственно через него на вход 1-го модуля выбора направления передачи сообщения, і-ьій модуль выбора направления передачи сообщения анализирует адресную часть сообщения и на ее основании перенаправляет сообщение в соответствующую этому значению выходную распределенную очередь. Позиция в очереди, куда передает сообщение i-ый модуль выбора направления передачи сообщения, определяется указателем головы очереди, для сообщения А;Д1) это j-й указатель головы очереди. Таким образом, сообщение помещается в выходную распределенную очередь. После его записи указатель головы очереди перемещается на следующую позицию, номер строки в матрице регистров которой будет i+N.
Сообщение Ау(2) в момент п = 2 поступает на і-й вход и соответственно через него на вход і-го модуля выбора направления передачи сообщения, i-ый модуль выбора направления передачи сообщения анализирует адресную часть сообщения и на ее основании передает сообщение в соответствующую этому значению выходную распределенную очередь. Позиция в очереди, куда передает сообщение i-ый модуль выбора направления передачи сообщения, определяется указателем головы очереди, для сообщения Ау(2) это j-й указатель головы очереди. Таким образом, сообщение помещается в выходную распределенную очередь. После его записи указатель головы очереди перемещается на следующую ячейку, номер которой в матрице регистров которой будет i+2N.
В момент п = 1, 2 и т.д. сообщения Ajj(n) могут поступать не только на вход і, но на все остальные входы. Процессы приема и помещения в выходную распределенную очередь сообщения протекают асинхронно и параллельно рассмотренному выше.В момент времени П], когда поступит сообщение Aij(ni), а в очереди Qj все ячейки будут занятыми, запись сообщения будет произведена в начальную ячейку очереди.
Описание аппарата расширенных Q-схем
Исследование характеристик функционирования коммутатора практически невыполнимо аналитическими методами из-за сложности получающихся математических моделей. Поэтому для анализа разработанной процедуры коммутации и существующих модулей использовались средства имитационного моделирования, на основе которых была построена библиотека классов моделирования.
Если рассматривать коммутатор как систему массового обслуживания, то его функционирование можно описать на языке Q-схем, в котором объектами обслуживания (обработки) являются сообщения или пакеты. Сообщения поступают в массовом порядке, моменты их поступления образуют поток, удовлетворяющий свойствам потока Пуассона (простейшего потока). Обработка сообщений выполняется также случайное время, которое зависит от текущей длины очередей сообщений в буферах, интенсивности их поступления, времени обслуживания заявок, а также других факторов.
Q-схема - полуформальный графический язык, который легко вписывается в рамки объектно-ориентированного подхода. Он универсален и позволяет описывать системы широкого класса. Поэтому данный язык был использован при решении задачи имитационного моделирования.
Q-схема - это граф, вершины которого отображают элементы системы (реальные или вспомогательные абстракции), а дуги связывают элементы между собой. Все вершины разделяются на 4 вида в зависимости от того, какой элемент они моделируют. Связи делятся на 2 вида. Графическое изображение используемых базовых элементов для построения Q-схем дано на рис.3.2 (а-г).
Первый элемент, представленный на рис. 3.2(a), обозначает генератор заявок. Его функция - имитировать поступление заявок в систему извне в соответствии с некоторым законом распределения. Параметр X задается в соответствии с законом распределения. Если закон экспоненциальный, то X является интенсивностью потока заявок. При равномерном законе X является интервалом возможных значений.
Второй элемент, представленный на рис. 3.2(6) - канал. Его функция -имитация обработки заявки в течение времени, определяемого некоторым законом распределения времени обслуживания заявок. Параметр п. аналогичен параметру X для генератора.
Третий элемент представленный на рис. 3.2(B) - накопитель (или очередь). Он имитирует в схеме возможные скопления заявок. Накопитель характеризуется предельной длиной очереди - L. Она может быть бесконечной (накопитель без потерь) или ограниченной (накопитель с потерей заявок). Также
накопитель характеризуется дисциплиной обслуживания заявок. Типовые дисциплины - FIFO (первым пришел - первым ушел) и LIFO (первым пришел -последним ушел), но возможны и иные дисциплины обслуживания, например, случайный выбор заявок.
Четвертый элемент - треугольник - это клапан (рис.3.2(г)). Он имитирует управление потоками заявок. Например, он может блокировать прохождение заявок или, наоборот, разрешить в зависимости от значений некоторых управляющих сигналов, которые поступают от других элементов по управляющим линиям.
Связи в Q-схеме разделяются на два типа. Информационные связи -изображаются сплошными стрелками (синими) (рис.3.2) - отображают пути прохождения заявок в системе. Управляющие связи - изображаются пунктирными стрелками (красными) (рис. 3.2) - передают управляющее воздействие на элементы Q-схем. На связи накладывается ряд ограничений. Так, генератор (если он не является управляемым) не может иметь входящих линий и обязан иметь хотя бы одну выходную информационную. Входящие управляющие связи допускаются только у клапанов (минимум - одна связь, максимум не ограничивается). Выходящие управляющие связи допустимы только у каналов и очередей. Число данных связей произвольно.
Базовый набор элементов Q-схем не достаточно эффективно позволяет удовлетворить требованиям при построении моделей коммутаторов. Приходится разрешать некоторые ситуации, возникающие при построении, с помощью достаточно сложных схем, использующих множество клапанов и дополнительных связей. Для упрощения решения таких задач в данной работе было предложено ввести дополнительные элементы с четко определенным синтаксисом и семантикой, при этом ввод данных элементов не влечет за собой качественную модификацию языка описания поведения систем массового обслуживания. Набор введенных дополнительных элементов представлен нарис. 3.3 (а-в).
Элемент, представленный на рис. 3.3(a), называемый простым случайным контроллером, реализует управление конечной группой клапанов по некоторому случайному закону, т.е., например, с определенной вероятностью открывает один из нескольких клапанов, над которыми он осуществляет управление. Элемент, представленный на рис. 3.3(6), - адаптивный случайный контроллер -также имитирует случайный выбор одного клапана из двух или более. Но при этом в его функцию входит изменение вероятности открытия клапанов в зависимости от состояния других элементов. Элемент, представленный на рис. З.З(в), - обобщенный массовый контроллер. Данный элемент также служит для выбора клапанов из определенной группы, однако свой выбор он может осуществлять, оперируя любым законом распределения, не обязательно случайным (закон задается разработчиком Q-схемы). Кроме того, обобщенный массовый контроллер может оперировать не только одним из N, а также М из N клапанов, возможно, учитывая состояние других элементов схемы. Выбранные клапаны могут быть либо открыты, либо закрыты, что определяется реакцией клапанов на сигналы от элементов-контроллеров.
Каждой управляющей связи в Q-схеме соответствует определенное состояние управления, например, «канал пуст» или «очередь занята». Если в текущий момент модельного времени такое состояние имеется, то управляемый элемент воспринимает его как разрешающий сигнал. Например, клапан может открыться по «пустоте» очереди. Полный список возможных состояний управления с их символическими именами приведен ниже:Empty() - контроллер пуст;Busy() - контроллер занят;Full() - контроллер заполнен;empty_or_busy( ), empty_or_full( ), busy_or_full() - комбинированные по ИЛИ состояния управления от предыдущих трех состояний;len_rel - соотношение длин очередей;time_rel - соотношение времен;
Построение масштабируемого коммутатора
Во второй главе диссертационной работы была определена задача построения масштабируемого коммутатора, как однокаскадного коммутатора, обеспечивающего высокую степень наращиваемости, с количеством входов/выходов больше 100. Для решения данной задачи был создан способ увеличения размера коммутации, на основе коммутатора с распределенными выходными очередями.
Способ заключается в разбиении распределенных выходных очередей на группы. Каждая распределенная очередь разбивается на М групп, по N/M входов в каждой группе, N - общее количество входов/выходов. Каждая группа представляет из себя коммутатор с распределенными выходными очередями, и процессы формирования распределенных выходных очередей протекают аналогично представленным в главе 2. Процесс выдачи сообщений из каждой распределенной очереди - члена группы производится в соответствии с алгоритмом коммутации, изложенным в главе 2. Выбор очереди - члена группы производится кольцевым опросом. Ограниченное число входов и выходов образовавшихся очередей, полученных при разбиении, позволяет реализовать каждую группу отдельной интегральной схемой.
Решение данной задачи в виде структурной схемы масштабируемого коммутатора, использующего процедуру коммутации с распределенными выходными очередями, представлено на рис. 4,5.
Коммутатор содержит NxM идентичных модулей, обозначенных штрих-пунктирной линией, каждый из которых реализуется отдельной интегральной схемой, N - размер коммутатора (количество входов/выходов), N/M -количество входов, обслуживаемых одним модулем. Входы коммутатора группами по N/M подключаются к входам модулей своего столбца.
Информационные выходы модулей каждой строки соединяются монтажнымИЛИ и являются информационными выходами коммутатора. Управляющийвыход каждого модуля соединен с управляющим входом модуля,расположенного правее, для крайнего правого модуля это крайний левыймодуль данной строки.
Каждый модуль состоит из блоков l.i.l-l.i.N организации очереди сообщений, регистра 2.1 идентификатора адреса, блока З.і анализа очередей сообщений, блока 4.1 синхронизации, причем информационные входы модуля подключены к соответствующим первым информационным входам блоков l.i.l-l.i.N организации очереди сообщений, выход регистра 2.і идентификатора адреса подсоединен ко вторым информационным входам блоков l.i.l-l.i.N организации очереди сообщений, управляющие выходы блоков l.i.l-l.i.N организации очереди сообщений соединены со третьим управляющим входом блока З.і анализа очередей сообщений, первый управляющий вход каждого блока l.i.l-l.i.N организации очереди сообщений соединен со вторым управляющим выходом блока З.і анализа очередей сообщений, второй управляющий вход каждого блока l.i.l-l.i.N организации очереди сообщений соединен со третьим управляющим выходом блока З.і анализа очередей сообщений, управляющий выход блока 4.І синхронизации подсоединен ко второму управляющему входу блока З.і анализа очередей сообщений, информационные выходы блоков l.i.l-l.i.N организации очереди сообщений соединены между собой по схеме «монтажного ИЛИ» и являются информационным выходом модуля, управляющий вход модуля подсоединен к первому управляющему входу блока З.і анализа очередей сообщений, первый управляющий выход которого является управляющим выходом модуля.
Блоки организации очереди сообщений, регистр идентификатора адреса, блок синхронизации абсолютно идентичны блокам базового модуля коммутации, и описаны в параграфе 4.1.
Блок З.і анализа очередей сообщений модуля масштабируемогокоммутатора (рис.4.6) содержит узел 17 постоянной памяти, элемент ИЛИ 18 иэлемент И 19, элемент И 20, RS-триггеры 21 и 22, элемент И 23, причем первыйуправляющий вход блока подключен к S-входу RS-триггера 21, прямой выход которого подсоединен к S-входу RS-триггера 22 и первому входу элемента И 19, обратный выход RS-триггера 21 соединен со вторым входом элемента И 23, выход которого является первым управляющим выходом блока и соединяется с R-входом RS-триггера 22, прямой выход которого подсоединен к первому входу элемента И 23, второй управляющий вход блока соединен с третьим входом элемента И 23 и первым входом элемента И 19, выход которого подключен к R-входу RS-триггера 21 и второму входу элемента И 20, выход которого является вторым управляющим выходом блока, третий управляющий вход блока соединен со входом узла постоянной памяти 17, выход которого является третьим управляющим выходом блока, разряды третьего управляющего входа блока, образующие функцию наличия сообщений в регистрах 6.1-б.п блоков l.i.l-l.i.N организации очереди сообщений, соединены со входами элемента ИЛИ 18, выход которого подключен к первому входу элемента И 20. Назначение элементов модуля масштабируемого коммутатора (рис.4.5) совпадает с назначением элементов модуля базового коммутатора (параграф 4.1), за исключением блока З.і анализа очередей сообщений, который предназначен, помимо реализации кольцевого опроса распределенных выходных очередей на основании состояния очередей сообщений в блоках l.i.s и предыдущего сформированного решения, для обеспечения последовательного кругового опроса модулей коммутатора одной строки. Назначение элементов, используемых в блоке З.і анализа очередей сообщений, следующее.
