автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.05, диссертация на тему:Коммутатор с распределенными выходными очередями для параллельных систем логического управления

Введение.

ГЛАВА 1. ПРОЦЕДУРЫ И УСТРОЙСТВА КОММУТАЦИИ В МНОГОПРОЦЕССОРНЫХ УПРАВЛЯЮЩИХ СИСТЕМАХ.

1.1. Организация многопроцессорных систем логического управления.

1.1.1 Структурная модель.

1.1.2 Функциональная организация.

1.2. Задача коммутации в многопроцессорных управляющих системах.

1.2.1 Содержательная характеристика задачи коммутации.

1.2.2 Влияние алгоритма управления на коммутацию.

1.2.3 Варианты взаимодействия модулей управления и коллектива объектов управления.

1.3. Коммутаторы для многопроцессорных управляющих систем.

1.3.1 Статические коммутаторы.

1.3.2 Динамические коммутаторы.

1.4. Динамические коммутаторы с коммутацией пакетов.

1.5. Коммутация в отказоустойчивых многопроцессорных управляющих системах.

1.6. Выводы по главе.

ГЛАВА 2. ПРОЦЕДУРА КОММУТАЦИИ С РАСПРЕДЕЛЕННЫМИ ВЫХОДНЫМИ ОЧЕРЕДЯМИ ДЛЯ ПАРАЛЛЕЛЬНЫХ МНОГОПРОЦЕССОРНЫХ СИСТЕМ ЛОГИЧЕСКОГО УПРАВЛЕНИЯ.

2.1. Содержательная постановка задачи.

2.2. Формализованная постановка задачи.

2.3. Процедура коммутации с распределенными выходными очередями.

2.3.1. Общие особенности процедуры.

2.3.2. Концептуально - логические основы процедуры.

2.3.3. Функционирование предложенной процедуры, алгоритм коммутации

2.4. Анализ свойств процедуры коммутации.

2.4.1. Исследование графа коммутации.

2.3.2. Исследование процедуры на наличие тупиковых ситуаций.

2.3.3. Оценка аппаратной сложности процедуры коммутации.

2.5. Выводы по главе.

ГЛАВА 3. ЭКСПЕРИМЕНТАЛЬНОЕ ИССЛЕДОВАНИЕ ПРОЦЕДУРЫ

С РАСПРЕДЕЛЕННЫМИ ВЫХОДНЫМИ ОЧЕРЕДЯМИ.

3.1. Постановка эксперимента.

3.2. Описание аппарата расширенных (}-схем.

3.3. Архитектура библиотеки классов моделирования.

3.4. ф-схемы исследуемых коммутаторов.

3.5. Анализ результатов моделирования.

3.6. Выводы по главе.

ГЛАВА 4. АППАРАТНАЯ РЕАЛИЗАЦИЯ КОММУТАТОРА.

4.1. Функциональная схема базового модуля коммутации.

4.2. Построение масштабируемого коммутатора.

4.3. Коммутатор отказоустойчивой многопроцессорной системы логического управления.

4.4. Выводы по главе.

Актуальность темы. Параллельные многопроцессорные системы логического управления (МСЛУ) - одно из перспективных направлений развития систем управления сложными процессами и коллективами процессов. Разработкой подобных систем занимаются ведущие мировые производители вычислительной техники: 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 годах, утвержденному начальником управления планирования и финансирования научных исследований.

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

Основными задачами являются:

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

2. Разработка процедуры коммутации, обеспечивающей высокоскоростное взаимодействие модулей и объектов управления при повышении масштабируемости и отказоустойчивости параллельных МСЛУ.

3. Создание коммутатора, реализующего разработанную процедуру коммутации.

4. Аналитическое и экспериментальное исследование характеристик разработанных процедуры и коммутатора.

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

1. Проведен анализ быстродействия, масштабируемости и отказоустойчивости существующих процедур коммутации и требований МСЛУ к сети связи с объектами управления.

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

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

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

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

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

Практическая ценность диссертационной работы заключена в следующем:

1. Разработаны алгоритм и процедура коммутации, позволяющие увеличивать масштабируемость и отказоустойчивость параллельной МСЛУ без ограничений, присущих известным методам.

2. Коммутаторы, реализованные на основе созданной процедуры, позволяют уменьшить среднее время задержки на 2-5% по сравнении с известными.

3. На основе разработанной процедуры предложены структурные и функциональные схемы: базового модуля коммутатора, обеспечивающего коммутацию в соответствии с графом максимальной коммутации, масштабируемого коммутатора, пригодного для построения коммутаторов с размером коммутации более 1024x1024 в одном каскаде, коммутатора отказоустойчивой МСЛУ, обеспечивающего динамическую перекоммутацию коллектива объектов управления и коллектива модулей управления, начавших исполнение новых алгоритмов после отказов модулей.

4. Усовершенствован аппарат (^-схем в части имитационного моделирования коммутаторов и коммутационных процедур, реализованный в библиотеке классов для исследования характеристик коммутационных процедур и коммутаторов.

Основные технические решения защищены патентами (№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. Алгоритм и процедура коммутации с распределенными выходными очередями.

2. Способ увеличения размера коммутации на основе коммутатора, реализующего процедуру коммутации с распределенными выходными очередями.

3. Структурные и функциональные схемы базового модуля коммутации, масштабируемого коммутатора, коммутатора отказоустойчивой параллельной МСЛУ, основанные на процедуре коммутации с распределенными выходными очередями.

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

Объем и структура работы. Диссертационная работа состоит из введения, четырех глав, заключения, списка литературы и приложений. Общий объем диссертации составляет 220 страниц, включая 50 рисунков, 4 таблицы, список литературы из 144 наименований.

§4.4 Выводы по главе

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

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

3. Разработанная функциональная схема масштабируемого коммутатора, использующего процедуру коммутации с распределенными выходными очередями, предназначена для построения коммутаторов, размер коммутации которых может превышать 1024x1024 в одном каскаде.

4. Созданная функциональная схема коммутатора отказоустойчивой МСЛУ, использующего процедуру коммутации с распределенными выходными очередями, обеспечивает динамическую перекоммутацию коллектива объектов управления и коллектива модулей управления, начавших исполнение новых частных алгоритмов.

Заключение

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

При решении поставленной задачи в диссертационной работе получены следующие результаты.

1. Анализ быстродействия, масштабируемости и отказоустойчивости существующих процедур коммутации и требований МСЛУ к ССОУ, показавший невозможность применения известных процедур для организации сопряжения коллективов модулей и объектов управления МСЛУ.

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

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

4. Проведены экспериментальные исследования, подтвердившие, что разработанная процедура коммутации обеспечивает меньшую среднюю задержку сообщений на 2-5%, меньшую максимальную задержку сообщений на 3% и меньший процент потерянных сообщений для разных вариантов трафика, чем существующие коммутаторы.

5. На основе процедуры коммутации с распределенными выходными очередями разработаны структурные и функциональные схемы: базового модуля коммутатора, обеспечивающего коммутацию в соответствии с графом максимальной коммутации, масштабируемого коммутатора, пригодного для построения коммутаторов с размером коммутации более 1024x1024 в одном каскаде, коммутатора отказоустойчивой МСЛУ, обеспечивающего динамическую перекоммутацию коллектива объектов управления и коллектива модулей управления, начавших исполнение новых алгоритмов после отказов модулей.

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

1. Автоматное управление асинхронными процессами в ЭВМ и дискретных системах/ Под ред. В.И. Варшавского. М.: Наука, 1986. 336с.

2. Апраксин Ю.К., Запевалин AJL, Кирюхин В.В. Алгоритмы маршрутизация ДМ сетей с коммутацией сообщений // А и ВТ. 1982. - №2. - С. 87-92.

3. Арсеньев Ю.Н., Журавлев В.М. Проектирование систем логического управления на микропроцессорных средствах. М.: Высшая школа, 1991. - 319 с.

4. Балабанов A.C. Многопроцессорные системы. Основные принципы организации. Управляющие системы и машины. - 1983. - №3. - С. 3-10.

5. Бернштейн JI.C., Калычев Д.П., Дедюлин К.К. Устройство для оценки размещения элементов / A.c. №1430949 СССР. G 06 F 7/00, 15/20; 25.03.87, БИ 38.

6. Валях Е. Последовательно-параллельные вычисления. -М.:Мир, 1985.^-56 с.

7. Воеводин В.В. Математические модели и методы в параллельных процессах. М.: Наука., 1986. - 296 с.

8. Высокоскоростные вычисления. Архитектура, производительность, прикладные алгоритмы и программы Супер ЭВМ / Под ред. Ковалика. -М.: Радио и связь, 1988.-432 С.

9. Головкин Б.А. Параллельные вычислительные системы. М.: Наука, 1980. -520 с.

10. Горбатов В.А., Смирнов М.И., Хлытчцев И.С. Логическое управление распределенными системами-М.: Энергоатомиздат, 1991.-248с.

11. Гремальский A.JI. Микропрограммное устройство управления / A.c. 1647566 СССР О 06 Р 9/22; опубл. 07.05.91, БИ №17.

12. Гремальский A.A. Мультимикропрограммная управляющая система / A.c. 1631542 СССР С 06 Р 9/22, 9/00; опубл. 28.02.91, БИ №8.

13. Евреинов Э.В. Однородные вычислительные системы, структуры и среды;. М.: Радио и связь, 1981. - 208с.

14. Закревский А.Д. К теории параллельных алгоритмов логического управления // Изв. АН СССР. Техн. кибернетика. 1989. - №5. - С. 179-191.

15. Закревский А.Д. Параллельные алгоритмы логического управления // Доклады АН БССР. 1982. - Т.26, №12. - С. 1088-1091.

16. Зотов И.В. и др. Функционально-топологическая организация микропрограммных мультимикроконтроллеров группового логического управления. -Тула.: Тул. гос. ун-т, 1997. 226 с.

17. Зотов И.В. и др. Организация и синтез микропрограммных мультимикроконтроллеров. Курск.: Изд-во «Курск», 1999. - 368 с.

18. Интегральные микросхемы: Справочник / Тарабрин Б.В., Лунин Л.Ф., Смирнов Ю.Н. М.: Радио и связь, 1984. -528 с.

19. Колосков В.А. Метод восстановления логической структуры мультимикро-контроллерной сети // Известия КГТУ. 1997. - №1. - С. 82-90.

20. Коршунов Ю.М. Математические основы кибернетики. М.: Энергоатом-издат, 1987.-496 с.

21. Курейчик В.М., Глушань В.М. Щербаков Л.И. Комбинаторные аппаратные модели и алгоритмы в САПР. М.: «Радио и связь», 1990. - 216 с.

22. Кюблер Ф.Д., Пагиев К.Х., Панфилов П.Б. Системы логического управления на базе транспьютерных сетей / Информационные процессы, технологии, системы, коммуникации и сети. М.: МАИ, 1995. - С. 54-59.

23. Лазарев В.Г, Пийль Е.И. Синтез управляющих автоматов. М.; Энерго-атом-издат, 1989 - 328 с.

24. Микросхемы и их применение / Батушев В.А., Вениаминов В.Н., Ковалев В. М.: Энергия, 1978. - 248 с.

25. Микропрограммный модуль / В.А. Мельников и др.; A.c. 1193675 СССР О 06 Р 9/22; опубл. 23.11.85, БИ№43.

26. Микропрограммный модуль / B.C. Харченко и Др.; A.c. 1427366 СССР О 06 Р 9/22; опубл. 30.09,88, БИ№36.

27. Микропрограммное устройство для управления обменом управляющей информации в распределенной системе / B.C. Харченко и др.; A.c. 1325477 СССР О 06 Р 9/22; опубл. 23.07.87, БИ №27.

28. Микропрограммное устройство управления / B.C. Харченко и др.; A.c. 1133595 СССР С 06 Р 9/22, С 06 Р 1/00; опубл. 07.01.85, БИ№1.

29. Микропрограммное устройство управления / B.C. Харченко и др.; A.c. 1168936 СССР С 06 Р 9/22; опубл. 23.07.85, БИ №27.

30. Микропрограммное устройство управления модуля вычислительной системы / В. С. Харченко и др.; A.c. 1108447 СССР О 06 Р 9/22; опубл. 15.08.84, БИ №30.

31. Микропрограммное устройство управления модуля распределенной параллельной вычислительной системы / В.П. Улитенко и др.; A.c. 1252775 СССР О 06 Р 9/22; опубл. 23.08.86, БИ №31.

32. Микропрограммное устройство управления с контролем / В. С, Харченко и др.; A.c. 1142832 СССР О 06 Р 9/22,0 06 Р 11/00; опубл. 28.02.85, БИ №8.

33. Микропроцессоры и микропроцессорные комплекты интегральных микросхем: Справочник. В 2 т. / Под ред. &.А. Шахноеа. М.: Радио и связь, 1988. -Т.1. - 368с.

34. Михайлов Г.И., Руднев В.В. Автоматная система взаимосвязанных графов с простейшими связками // А и Т. — 1980. №5. - С. 132-142.

35. Многоканальное устройство для обмена управляющей информацией в вычислительной системе / В.А. Мельников и др.; A.c. 1566362 СССР С 06 Р 15/16, 13/00; опубл. 23.05.90, БИ №19.

36. Многоканальное устройство для программного управления технологическими процессами / В А. Мельников и др.; A.c. 17К4940 СССР О 05 В 19/18; опубл. 30.12.92, БИ №48.

37. Модуль коммутационной сети / Сусин П.В. и др.; Патент на изобретение RU 2175146 С1 7 G 06 F 15/163, 15/173, 15/17; опубл. 20.10.2001, Бюл. №29.

38. Модуль матричного коммутатора / В.А. Мельников и др.; A.c. 1575167 СССР С 06 Р 7/00, 15/16; опубл. 30.06.90, БИ №24.

39. Модульное устройство для программного управления и контроля / В. С. Харченко и др.; A.c. 1647519 СССР С 05 В 19/18; опубл. 07.05.91, БИ №17.

40. Морозов К.К., Одиноков В.Г., Курейчик В.М. Автоматизированное проектирование конструкций радиоэлектронной аппаратуры: Учебное пособие для вузов. М.: «Радио и связь», 1983. - 280 с.

41. Мячев A.A., Степанов В.Н., Щербо В.К. Интерфейсы систем обработки данных: Справочник. М.: Радио и связь, 1989. - 416 с.

42. Надежность технических систем: Справочник/ Ю.К. Беляев, В.А. Богатырев, В.В. Болотин; Под ред. H.A. Ушакова М.: Радио и связь, 1985. - 608 с.

43. Новиков Ю.В., Калашников O.A., Гуляев С.Э. Разработка устройств сопряжения. М.: «ЭКОМ», 1997. - 224 с.

44. Ope О. Теория графов. М.: Наука, 1968. - 352 с.

45. Сами М., Стефанелли Р. Перестраиваемые архитектуры матричных процессорных СБИС// ТИИЭР. 1986. - №5 - С. 107-118.

46. Степанян С.О. Коммуникационные сети в многопроцессорных ЭВМ // Автоматика и вычислительная техника. 1987. - №3. - С. 31-43.

47. Сусин П.В., Борзов Д.Б., Зотов И.В. Аппаратная модель задачи размещения в параллельных системах с кольцевой структурой // Известия вузов. Приборостроение. Санкт-Петербург, 2002. - №7. - С. 21-29.

48. Сусин П.В., Зотов И.В., Титов B.C. Модель буферного элемента коммутационной структуры// Труды 5-й МЭНК «Современные проблемы информатизации в непромышленной сфере и экономике», Воронеж, 2000. С. 133-134.

49. Сусин П.В., Зотов И.В., Беляев Ю.В. Элемент матричного коммутатора с общей очередью входящих сообщений // Материалы межвузовской электронной НТК «Управляющие и вычислительные системы. Новые технологии», Вологда:ВГТУ, 2001.-С. 77.

50. Тербер К.Дж. Архитектура высокопроизводительных вычислительных систем. М.: Наука, 1985. - 272 с.

51. Труды института инженеров по электротехнике и радиоэлектронике // 1989. -Т. 77, №12.

52. Устройство для формирования маршрута сообщения / Сусин П.В. и др.; Патент на изобретение RU 2175144 С1 7 G 06 F 7/00, 13/00; опубл. 20.10.2001, Бюл. №29.

53. Устройство задержки / Сусин П.В. и др.; Патент RU 2071169, 6Н 03 К 5/13; опубл. 27.12.1996, Бюл. №36.

54. Хвощ С.Т., Варлинасий Н.Н., Попов Е.А. Микропроцессоры и микроЭВМ в системах автоматического управления: Справочник. JL: Машиностроение, Ленингр. отд., 1987. - 640 с.

55. Цифровая и вычислительная -техника / Под ред. Э.В. Евреинова. М,: Радио и связь. 1991.—464с.

56. Шило В.Л. Популярные цифровые микросхемы: Справочник. Металлургия, Челябинск, 1988. - 352 с.

57. Юдицкий С.А., Магергут В.З. Логическое управление дискретными процессами. Модели, анализ, синтез-М.: Машиностроение, 1987 176 с.

58. АН, М., Nguyen, Н. A neural network implementation of an input access scheme in a high-speed packet switch// Proceedings of GLOBECOM 1989, PP.1192-1196.

59. Anderson G.A., Jensen L.D. Computer interconnection structures, taxonomy, characteristics and examples // Computing Surveys of AC. 1975. - Vol. 7, №4. -PP. 197-213.

60. Anderson Т., Owicki S., Saxe J., Thacker C. High speed switch scheduling for local area networks // ACM Transaction, on Computer Systems, Nov. 1993, - PP. 319-352.

61. Arden B.W., Lee H. Analysis of chordial ring network // IEEETC. 1981. -Vol. C-30, №4. - PP. 291-295.

62. Awdeh R.Y., Mouftah H.T. Survey of ATM switch architectures // Computer Networks & ISDN Systems, 1995, - vol. 27, - PP. 1567-1613.

63. Batcher K.E. Sorting networks and their applications// Proceedings of 1968 Spring Joint Computer Conference.

64. Bhuyan L.N., Agrawal D.P. Generalized hypercube and hyperbus structures for a computer network // IEEETC. 1984. - Vol. C-33, №4. - PP. 323-333.

65. Chancy T., Fingerhut J.A., Flucke M., Turner J.S. Design of a gigabit ATM switch// Proceedings of IEEE INFOCOM '97, Kobe, - Japan, - 7-11 April 1997, -vol.1,-PP. 2-11.

66. Chen M., Georganas N.D. A fast algorithm for multi-channel/port traffic scheduling // Proceedings of IEEESupercom/ICC '94, PP.96-100.

67. Chi H.C., Tamir Y. Starvation prevention for arbiters of crossbars with multiqueue input buffers// Proceedings of COMPCON '94, San Francisco, - February, 1994,-pp. 292-297.

68. Chi H.C., Tamir Y. Decomposed arbiters for large crossbars with multi-queue input buffers // IEEE International Conference on Computer Design: VLSI in Computers and Processors, Cambridge, - October, - 1991, - PP. 233-238.

69. Choudhury A.K., Hahne L.E. Dynamic queue length thresholds in a shared memory ATM switch// Proceedings of IEEE INFOCOM '96, San Francisco, - March, 1996,-vol.2,-PP. 679-687.

70. Chuang S.-T., Goel A., McKeown N., Prabhakar B. Matching output queueing with a combined input output queued switch // Computer Systems Technical Report CSL-TR-98-758, March 1998.

71. Cisco Systems, Fast switched backplane for a gigabit switched router // http://www.cisco.com/warp/public/733/12000/technical.shtml.

72. Cormen T., Leiserson C.E., Rivest R.L. Introduction to Algorithms // The MIT Press, Cambridge, - Massachusetts, - March 1990.

73. Coudreuse J.P., Servel M. Prelude: an asynchronous time-division switched network// Proceedings of IEEE International Conference on Communications '87, New York, - 1987, - vol.2, - PP. 769-773.

74. Dally W.J., Carvey P.P., Dennison L.R. The Avici terabit switch/router // Proceedings of Hot Interconnects 6, Stanford, - Aug 1998, - PP. 41-49.

75. Demers A., Keshav S., Shenker S. Analysis and simulation of a fair queueing algorithm // Internetworking: Research and Experience, Sept. 1990, - vol.1, - no. 1, -PP. 3-26.

76. Despain A.M., Patterson D.A. X-tree: a tree structured multiprocessor computer architecture / Proceedings of 5th Symp. on Computer Architecture, Palo Alto, Calif. -1978.-PP. 144-151.

77. Dinic E.A. Algorithm for solution of a problem of maximum flow in a network with power estimation // Soviet Math. Dokl., -1970, vol.11, - PP. 1277-1280.

78. Endo N., Kozaki T., Ohuchi T., Kuwahara H., Gohara S. Shared buffer memory switch for an ATM exchange // IEEE Transactions on Communications, Jan. 1993, - vol.41, -no.l, -PP. 237-245.

79. Feng T-Y. A survey of interconnection network // IEEE Computer. 1981. -Vol. 14, №12.-PP. 12-27.

80. Giacopelli J., Hickey J., Marcus W., Sincoskie D., Littlewood M. Sunshine: A high-performance self-routing broadband packet switch architecture // IEEEJ. Selected Areas Communications, Oct 1991, - vol.9, - no.8, - PP.1289-1298.

81. Gottlieb A., Schawarts J.T. Networks and algorithms for very-large-scale parallel computation // Computer. 1982. - Vol. 15, №1. - PP. 27-36.

82. Hockney R. Classification and Evaluation of ParallelComputer Systems // Lecture Notes in Computer Science. 1987, №295. - PP.13-25.

83. Horowits E., Zorat A. The binary tree as an interconnection network: application of multiprocessor systems and VLSI // IEEETC. 1981. - Vol. C-30, №4. - PP. 247-253.

84. Huang A., Knauer S. Starlite: A wideband digital switch // Proceedings of GLO-BECOM '84, 1984, - PP.121-125.

85. Jafari H., Lewis T.G., Spragins J.D. Simulation of a class of ring structured networks // IEEE Transactions on Computers. 1980. - Vol. C-29, №5. - PP. 385-392.

86. Joo Y.M., McKeown N. Doubling memory bandwidth for network buffers // Proceedings of INFOCOM, San Francisco, - April 1998, - vol.2, - PP. 808-818.

87. Karol M., Eng K., Obara H. Improving the performance of input-queued ATM packet switches // Proceedings of INFOCOM/92, PP.110-115.

88. Karol M., Hluchyj M. Queueing in high-performance packet-switching // IEEEJ. Selected Area Communications, Dec. 1988, - vol.6, - PP. 1587-1597.

89. Karol M., Hluchyj M., Morgan S. Input versus output queueing on a space division switch // IEEETrans. Communications, 1987, - PP.1347-1356.

90. Katsube Y., Nagami K., Matsuzawa S., Esaki H. Internetworking based on cell switch router-architecture and protocol overview // Proceedings of the IEEE, December, - 1997, - vol.85, - no. 12, - PP. 1998-2006.

91. Keshav S., Sharma R. Issues and trends in router design // IEEE Communications magazine, May 1998, - vol.36, - no.5, - PP. 144-151.

92. Kozdrowski E.W., Theis D.I. Second generation of vector supercomputer // Computer. 1984. - Vol. 13, №11. - PP. 71-83.

93. Kumar P.R., Meyn S.P. Stability of queueing networks and scheduling Policies // IEEE Transactions on Automatic Control, Feb. 1995, - vol.40, - no.2, - PP. 251260.

94. Kupta P., McKeown N. Design and implementation of a fast crossbar scheduler // Proceedings of Hot Interconnects 6, Stanford, - Aug 1998, - PP. 77-84.

95. Lawton G. In search of real-time Internet service // IEEE Computer. Society, -Nov. 1997,-vol.30,-no.il,-PP. 14-16.

96. Li M., Yan J. Dimensioning of line-access systems serving Internet traffic // XVI International Switching Symposium, Toronto, - 21-26 September 1997, - PP. 67-73.

97. Lund C., Phillips S., Reingold N. Fair prioritized scheduling in an input-buffered switch // Proceedings of the International IFIP-IEEE Conference on Broadband Communications, Montreal, - Que., - Canada April 1996, - PP. 358-369.

98. Matsuzawa S., Nagami K., Mogi A., Jinmei T., Esaki H., Katsube Y. Architecture of cell switch router and prototype system implementation // IEICE Transactions on Communications, Aug. 1997, - vol.E80-B, - no.8, - PP. 1227-1238.

99. McKeown N., Izzard M., Mekkittikul A., Ellersick W., Horowitz M. The Tiny Tera: a packet switch core // Proceedings of Hot Interconnects IV, Stanford, - Aug 1996,-PP. 161-173.

100. McKeown N., Anantharam V., Walrand J. Achieving 100% throughput in an input-queued switch // Proceedings of INFOCOM, 1996, - PP. 296-302.

101. Mekkittikul A., McKeown N. A starvation-free algorithm for achieving 100% throughput in an input-queued switch. // Proceedings of ICCCN'96, October,1996,-PP. 226-231.

102. Mekkittikul A., McKeown N., Izzard M. A small high-bandwidth ATM switch // Proceedings of SPIE, Boston, - November, - 1996.

103. Mekkittikul A., McKeown N. A practical scheduling algorithm to achieve 100% throughput in input-queued switches // Proceedings of INFOCOM, 1998, - San Francisco, - 29 March - 2 April 1998, - vol.2, - PP. 792-799.

104. Morgan S., Delaney M. The Internet and the local telephone network: conflicts and opportunities // XVI International Switching Symposium, Toronto, - 21-26 September 1997, - PP. 561-569.

105. Naldi M. Size estimation and growth forecast of the Internet // Centra Vito Volterra preprints. University of Rome, Tor Vergata, - Preprint no. 303, - October1997.

106. Nath D., Maheshwari S.N., Bhatt P.C.P. Efficient VLSI networks for parallel processing based on orthogonal trees // IEEETC. 1983. - Vol. C-32, №6. - PP. 569-581.

107. O.I. El-Dessouki, W.H. Huan. Distributed enumeration on network computer // Transactions Comput. 1980. - C-29(9). - PP. 818 - 825.

108. Obara H. Optimum architecture for input queueing ATM switches // IEE Electronics Letters, 28th March 1991, - PP.555-557.

109. Obara H., Hamazumi Y. Parallel contention resolution control for input queueing ATM switches // IEE Electronics Letters, 23rd April 1992, - vol.28, - no.9, -PP.838-839.

110. Obara H., Okamoto, S., Hamazumi Y. Input and output queueing ATM switch architecture with spatial and temporal slot reservation control // IEE Electronics Letters, 2nd Jan 1992, - PP.22-24.

111. P. Sadayappan, F. Ercal, J. Ramanujam. Cluster partitioning approaches to mapping parallel problems onto a hypercube // Parallel Comput. 1987. - №13(1). -PP. 1-6.

112. Parekh A.K., Gallager R. A generalized processor sharing approach to flow control in integrated services networks: the multiple node case // IEEE/ACM Transactions on Networking, April 1994, - vol.2, - no.2, - PP. 137-150.

113. Partridge C. et al. A 50-Gb/s IP router // IEEE/ACM Transactions on Networking, June 1998, - vol.6, - no.3, - PP. 237-248.

114. Patyra M., Maly W. Circuit design for a large area high-performance crossbar switch // Proceedings. 1991 International Workshop on Defect and Fault Tolerance on VLSI Systems, 18-20 Nov. 1991, - PP. 32-45.

115. Perparata F.P., Vuillemin J. The cube-connected connected cycles: a versatile network for parallel computation // Commun. Of ACM. 1981. - Vol. 24, №5. - PP. 300-309.

116. Reames C.C., Liu M. T. A loop network simultaneous transmission of variable length message // In: 2nd ASCA, Houston, Tex. 1975. - PP. 7-12.

117. Rose C. Rapid optimal scheduling for time-multiplex switches using a cellular automaton // IEEE Transactions on Communications, May 1989, - vol.37, - no.5, -PP. 500-509.

118. Siegel H.J., McMillen R.J., Mueller P.T. A survey of interconnection methods for reconfigurable parallel processing systems // In: AFIPS Conf. Proc., Washington, D.C. 1979. - Vol. C-29, №2. - PP. 108-115.

119. Suzuki H., Nagano H., Suzuki T., Takeuchi T., Iwasaki S. Output-buffer switch architecture for asynchronous transfer mode // IEEE International Conference on Communications, Boston, - June 1989, - vol. 1, - PP. 99-103.

120. Tamir Y., Frazier G. High performance multi-queue buffers for VLSI communication switches // Proc. of 15th Ann. Symp. on Comp. Arch., June 1988, -PP.343-354.

121. Tamir Y., Chi H.C. Symmetric crossbar arbiters for VLSI communication switches // IEEE Transactions on Parallel and Distributed Systems, Jan 1993. vol.4, -no. 1,-PP. 13-27.

122. Tassiulas L., Ephremides A. Stability properties of constrained queueing systems and scheduling policies for maximum throughput in multihop radio networks // IEEE Trans. Automatic Control, Dec. 1992, - vol. 37, - no. 12, - PP. 1936-1948.

123. Tobagi F.A. Fast packet switch architectures for broadband integrated services digital networks // Proceedings of the IEEE, Jan. 1990, - vol.78, - no. 1, - PP. 133167.

124. Troudet T.P., Walters S.M. Hopfield neural network architecture for crossbar switch control // IEEE Trans. Circuits and Systems, Jan. 1991, - vol.CAS-38, -PP.42-57.

125. Wittie L.D. Communication structures for large networks of microcomputers // IEEE Transactions on Computers. 1981. - Vol. C-30, №4. - PP. 264-273.

126. Zhang H. Service disciplines for guaranteed performance service in packet-switching networks // Proceedings of the IEEE. Oct. 1995, - vol.83, no.10 - PP. 1374-96.

127. Zhang L. VirtualClock: a new traffic control algorithm for packet-switched networks // ACM Transactions on Computer Systems, May 1991, - vol.9, - no.2, -PP. 101-124.

128. МИНИСТЕРСТВО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ КУРСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ

129. На правах рукописи УДК 681.51. Сусин Павел Викторович

130. КОММУТАТОР С РАСПРЕДЕЛЕННЫМИ ВЫХОДНЫМИ ОЧЕРЕДЯМИ ДЛЯ ПАРАЛЛЕЛЕНЫХ СИСТЕМ ЛОГИЧЕСКОГО УПРАВЛЕНИЯ