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

На правахрукописи

Анпилогов Евгений Геннадьевич

ПРОЦЕДУРА И УСТРОЙСТВО ДИНАМИЧЕСКОЙ МАРШРУТИЗАЦИИ СООБЩЕНИЙ В ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМАХ С МАССОВЫМ ПАРАЛЛЕЛИЗМОМ

Специальность 05.13.05 ""Элементы и устройства вычислительной техники и систем управления "

Автореферат диссертации на соискание ученой степени кандидата технических наук

Курск-2004

Работа выполнена в Курском государственном техническом университете

Научный руководитель: Заслуженный деятель науки РФ,

доктор технических наук, профессор B.C. Титов

Официальные оппоненты:

доктор технических наук, профессор В.В. Сюзев

кандидат технических наук В.Н. Сусин

Ведущая организация — ОКБ «Авиаавтоматика»

Защита диссертации состоится «17» декабря 2004 г. в 14 часов на заседании диссертационного совета Д 212.105.02 при Курском государственном техническом университете (305040, г. Курск, ул. 50 лет Октября, 94, конференц-зал).

С диссертацией можно ознакомиться в библиотеке университета.

Отзывы на автореферат в двух экземплярах, заверенные печатью, просьба направлять по адресу: 305040, г. Курск, ул. 50 лет Октября, 94, ученому секретарю диссертационного совета Д 212.105.02.

Автореферат разослан «12» ноября 2004 г.

Ученый секретарь диссертационного совета

ЕА. Титенко

Актуальность. Одним из перспективных направлений развития параллельных вычислительных систем (ВС) является создание массивно параллельных систем с распределенной памятью (МРР-системы). Отличительной особенностью МРР-систем является разделение физической памяти между процессорами (модулями), что дает возможность каждому модулю работать независимо от других. Благодаря такой архитектуре МРР-системы позволяют ввести средства оперативного восстановления работоспособности при появлении отказов модулей и/или связей (локальных отказовых неоднородностей). Указанные средства способны динамически исключать отказы из логической структуры системы, обеспечивая сохранение ее работоспособности в целом (возможно с деградацией производительности).

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

Существует множество алгоритмов отказоустойчивой (динамической) маршрутизации, ориентированных на системы с различными топологическими структурами (матрицы, гиперкубы, кубы циклов). Последние разработки в данной области - «Алгоритм адаптивной маршрутизации с кластерами без отказов» Л А. Закревского и М.Г. Карповского, «Алгоритм отказоустойчивой маршрутизации на основе расширенных безопасных уровней», разработанный Jie Wu, «Алгоритм отказоустойчивой маршрутизации на основе распределенного блока восстановления», предложенный Gul N. Khan, Gu Wei, «Алгоритм отказоустойчивой маршрутизации на базе вектора вероятности», созданный J. Al-Sadi, К. Day, M. Ould-Khaoua.

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

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

Работа выполнена при поддержке гранта «Столетовские гранты-2003» Министерства образования РФ, а также в рамках совместных работ с ОКБ «Авиаавтоматика» по договору №1.121.03 от 22 августа 2003 года. Основная часть диссертационной работы выполнена в рамках плана научно-исследовательских работ

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

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

Для достижения поставленной цели в работе решены следующие задачи:

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

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

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

4. Аналитические оценки аппаратной сложности устройства маршрутизации и вероятности правильной передачи сообщений в МРР-системе с использованием разработанной процедуры.

5. Исследование на имитационной модели зависимости времени доставки сообщений в МРР-системе от интенсивности потоков исходящих сообщений в процессорах при различных значениях наработки процессора на отказ и оценка потери сообщений из-за отказов при различных значениях наработки процессора на отказ.

Методы исследования. При решении поставленных задач использовались методы теории множеств, теории графов, теории вероятностей, теории проектирования ЭВМ, теории автоматов и математической статистики. Экспериментальные исследования проводились на основе библиотеки классов имитационного моделирования и визуальной среды программирования, разработанных под руководством доц. Зотова И.В.

Научная новизна результатов диссертационной работы:

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

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

3. Получены аналитические оценки вероятности правильной передачи сообщений в МРР-системе и зависимость коэффициента потерь сообщений от наработки процессора на отказ, показывающие, что разработанные

процедура и устройство маршрутизации позволяют повысить достоверность передачи не менее, чем в 2 раза, и снизить потери сообщений в 1.5 раза

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

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

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

3. Определен размер таблицы маршрутизации предлагаемого модуля для систем реальной размерности, не превышающий 1К слов.

Технические решения защищены патентами РФ (№ 2002108943, № 2003104071, №2003129963).

Реа1изация и внедрение. Результаты диссертационной работы используются в учебном процессе в Курском государственном техническом университете в дисциплинах «Организация ЭВМ и систем», «Отказоустойчивые многопроцессорные платформы» и внедрены на предприятиях ОАО «Счетмаш», ООО ПП «Микрокод», что подтверждается соответствующими актами.

Апробация работы. Основные положения диссертационной работы докладывались и получили положительную оценку на НТК «Распознавание-2001» (г. Курск, 2001), НТК «Методы и средства систем обработки информации» (г. Курск, 2003), НТК «Распознавание-2003» (г. Курск, 2003), на научно-технических семинарах Курского государственного технического университета с 2001 по 2004 год.

Публикации. Результаты диссертационной работы отражены в 8 публикациях, в том числе 3 статьях, 1 патенте на изобретение, 2 решениях о выдаче патента. В работах, опубликованных в соавторстве, лично соискателем предложено: в [1,2,7] - процедура выбора направления передачи сообщения, в [6,8] - алгоритм ретрансляции сообщений в матричных параллельных системах, в [3,4,5] - модуль для передачи сообщений.

На защиту выносятся:

1. Процедура отказоустойчивой маршрутизации сообщений для матричных МРР-систем.

2. Результаты аналитической оценки вероятности правильной передачи сообщений МРР-системой при использовании разработанной процедуры и аппаратной сложности устройства маршрутизации.

3. Результаты исследования на имитационной модели зависимости времени доставки сообщений в МРР-системе от интенсивности потоков исходящих сообщений в процессорах при различных значениях наработки процессора на отказ и оценка потерь сообщений из-за отказов при различных значениях наработки процессора на отказ.

4. Функциональные схемы устройства маршрутизации на основе созданной процедуры.

Объем и структура работы. Диссертационная работа состоит из введения, четырех глав, заключения, списка литературы и приложений. Работа содержит 160 страниц текста и поясняется 37 рисунками и 8 таблицами; список литературы включает 78 наименований; приложения содержат 71 страницу Общий объем составляет 231 страницу.

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

СОДЕРЖАНИЕ РАБОТЫ

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

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

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

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

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

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

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

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

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

Формализованное описание процедуры имеет следующий вид.

МРР-система представляется в виде графа С = вершины М

которого соответствуют модулям, а дуги отражают

межмодульные связи. Множество М отображается на множество элементов гипотетической матрицы Н, содержащей строки N2 столбцов, N¡>1, N¿>1, N¡N2 = \Мтак, что

(«»[(,Дп)[/,у + 1]), (т[1,) + 1],/»р, Д), (Ч<,Д'Ф + 1.УЗ). ('»[' + 1Лт[',Л) е Е',

где е М — модуль, расположенный на пересечении /'-й строки и у'-го

столбца матрицы Н, / = 1, Л',, у = 1, Л^ ■

Система, представленная описанным способом, обозначается далее как

Пусть Ы - маршрут, соединяющий некоторую пару модулей в системе С(Н). Разобьем маршрут R на подмаршруты (участки) таким

образом, чтобы соблюдались условия:

где h - положительное целое число.

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

я»

и назовем маршрутным кодом

го участка.

Введем обозначения Л",и назовем базовыми реализациями первого, второго ... £-го участков соответственно.

В дополнение к базовой реализации определим для 5-го участка

множество альтернативных реализаций | , ,..., Л*' | г Л (, 5 = 1, %. Требуется, чтобы ^ * {^Ур* ц, и 1 <|/?1'|</г, <7 = 1,Л,, 5-\,Х- Положим Л, = Л, где Лг - множество реализаций 5-го участка маршрута./?.

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

1. Определение маршрута Я, соединяющего источник и приемник в системе

С*"'.

2. Разбиение маршрута Я с учетом условия (1) на участки

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

4. Старт передачи сообщения от приемника к источнику по участкам Л'',

5=1,2,...,х (первоначально р=0).

5) Если передача по невозможна (р=0,1,-"> Л "" ' )> то возврат в начало текущего подмаршрута и выбор альтернативного подмаршрута для продолжения передачи сообщения по п. 4.

6) Если передача сообщения по реализации невозможна, то возврат к активной реализации предыдущего участка и так далее, пока не будет достигнута .последняя альтернативная реализация первого участка Я*1 маршрута Я, после чего возникает фатальная ситуация.

7) При невозможности возврата сообщения в подмаршруте осуществляется обход отказавшего модуля по фиксированному алгоритму.

Пункты 'процедуры 1-3 выполняются до включения системы, остальные во время работы системы.

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

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

В третьей главе рассматривается функциональная схема модуля МРР-

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

Функциональная схема устройства динамической маршрутизации представлена на рис.1.

В состав модуля входят следующие элементы и блоки: блоки организации очереди сообщений (БООС) 1.1-1.5; мультиплексор 2; блок анализа очередей сообщений (БАОС) 3; первый и второй буферные регистры 6.1, 6.2; дешифратор 8; блок синхронизации (БС) 9; триггер запуска 10; первый и второй элементы И 21.1, 21.2; с первого по четвертый элементы ИЛИ 22.1-22.4; блок анализа ситуаций (БАС) 4; блок модификации маршрутных кодов (БММК) 5; блок обхода отказавшего модуля (БООМ) 5А; второй буферный регистр 7; коммутатор кода текущей трансляции 11; мультиплексор отказа 12; демультиплексор 13; с первого по четвертый коммутаторы 14-17; триггер отказа 18; первый и второй блоки элементов И 19, 20; одновибратор 23.

Назначение основных элементов и блоков модуля следующее.

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

Блок 5 модификации маршрутных кодов служит для формирования маршрутного кода р-го участка и признаков р-го и (р+1)-го участков маршрута при переходе к р-му участку или к очередной реализации р-го участка, а также для формирования инвертированного маршрутного кода, обеспечивающего возврат сообщения первому модулю р-го участка при отказе очередного модуля. Данный блок реализует пункты 5 и 6 предложенной процедуры.

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

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

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

Аппаратная сложность модуля на основе разработанной процедуры выражается следующим образом:

£1=(Ц+1)\УБ00С +\УБАОС+(Ц+1)ММП+

+(ц+1 )2\УРг+^,БАС+ \УБММК+ ^боом»

где - число входов модуля,

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

Рис.1. Функциональная схема устройства динамической маршрутизации

Выразив А в числе эквивалентных регистров с аппаратной сложностью каждый, получим:

а=(ц2+(у+4)д+(у+7))\У0>

где v - длина очереди в БООС.

После подстановки реальных значений (ц=1...14, У=5..20 и Wo=10..140 вентилей) аппаратная сложность модуля получается в пределах 220...78260 вентилей, что является допустимым значением для подобных систем.

В четвертой главе проводится численная оценка преимуществ разработанной процедуры и устройства. Оценка осуществляется аналитически и на основании имитационного моделирования.

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

где ^(0 — вероятность доставки сообщения на б-м участке маршрута, определяется как:

>Д<)

где — вероятность обхода отказавшего модуля;

и — вероятности соответственно успеха и неудачи при

передаче сообщения, где

- количество альтернативных реализаций. Причем,

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

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

С учетом формул (3,4,5) вероятность правильной передачи сообщений

определяется в виде:

Результаты анализа вероятности правильной доставки сообщений представлены на рис. 2.

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

двукратный рост вероятности правильной передачи сообщений, при этом существенное увеличение X нецелесообразно.

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

Из зависимостей, приведенных на рис.3, видно, что даже в системе из -400 процессоров (п=20) при значительном Л (д=3) объем памяти таблицы маршрутизации модуля не превышает 1К слов. Только при Л=6 (рис.4) требуется память на -1400 слов. Поскольку (как следует из рис.2) увеличение нецелесообразно, фактически необходимый объем памяти будет менее 1 К слов для любого практически реализуемого п.

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

отказ, а также коэффициента потери сообщений от наработки процессора на отказ при фиксированных ингенсивностях исходящих потоков.

Рис.3. Графики зависимости размера таблицы маршрутизации модуля ¿'от числа модулей в строке п системы при /1=согШ

Рис.4. Графики зависимости размера таблицы маршрутизации модуля ¿'от числа альтернативных реализаций Л при п=сопз1

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

Условия проведения вычислительного эксперимента следующие:

1. Эксперимент осуществлялся отдельно над каждой процедурой. При этом регистрировалось количество сообщений (заявок) в системе, количество потерянных заявок, среднее время обработки сообщений в зависимости от интенсивности потоков сообщений и интенсивности отказа модулей в системе.

2. Частота генерации заявок (/„,) каждым модулем определялась экспоненциальным законом, параметр которого менялся от 20 до 50 тактов.

3. Наработка модуля на отказ (Тотк) также определялась экспоненциальным законом с параметрами 1000, 2000, 3000, 4000, 5000,6000.

Были получены зависимости коэффициента потерь сообщений (кп) от наработки на отказ модуля матричной системы 8x8. Кривые (рис.5) соответствуют следующим известным алгоритмам: «жадный» алгоритм, алгоритм отказоустойчивой маршрутизации на основе расширенных безопасных уровней, алгоритм отказоустойчивой маршрутизации на основе распределенного блока восстановления и разработанный алгоритм.

—"жадный" алгоритм

— »—алгоритм отказоустойчивой маршрутизации на основе распределенного блока восстановления' А алгоритм отказоустойчивой маршрутизации на основе расширенных безопасных уровней' X предложенный алгоритм

Рис.5. Графики зависимости коэффициента потерь сообщений от наработки на отказ, при среднем значении /„,=40 и Л= 1 для предложенного алгоритма

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

Также было проведено исследование зависимостей времени пребывания заявки в системе от интенсивности потока сообщений для данных алгоритмов (рис 6).

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

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

В приложениях приводятся тексты проектов моделирования, таблицы экспериментальных данных, акты внедрения.

ОСНОВНЫЕ ВЫВОДЫ И РЕЗУЛЬТАТЫ РАБОТЫ

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

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

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

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

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

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

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

Основные положения диссертации отражены в следующих работах:

1. Анпилогов Е.Г., Зотов И.В, Титов B.C. Процедура отказоустойчивой маршрутизации сообщений для параллельных вычислительных систем // Известия КурскГТУ. Курск, 2004. №2(13). С. 74 - 78.

2. Анпилогов Е.Г., Зотов И.В. Процедура вещания сообщений в матричных параллельных системах // Методы и средства систем обработки информации: сб. науч. ст. Курск, гос. техн. ун-т. Курск, 2003. Вып. 3. С. 79 - 87.

3. Патент 2222044 Россия, кл. G 06 F 15/173. Модуль для ретрансляции сообщений в матричном коммутаторе / Е.Г. Анпилогов, Ю.В. Беляев, И.В. Зотов. Заявл. 08.04.2002; Опубл. 20.01.2004. Бюл. №2. 16с.

4. Заявка 2003104071 Россия. Модуль для передачи и вещания в матричном коммутаторе / Е.Г. Анпилогов, Ю.В. Беляев, И.В. Зотов. Решение о выдаче 22.09.2004.

5. Заявка 2003129963 Россия. Модуль для обмена сообщениями / Е.Г. Анпилогов, В.В Ефремов, И.В Зотов, А.А. Иванов. Решение о выдаче 13.10.2004.

6. Анпилогов Е.Г., Беляев Ю.В., Зотов И.В. Квазиадаптивная маршрутизация сообщений в матричных микроконтроллерных сетях / Курск, гос. техн. ун-т. Курск, 2001. 26 с. Деп. в ВИНИТИ 07.06.2001, №1417-В2001.

7. Анпилогов Е.Г., Зотов И.В. Модель квазиадаптивной маршрутизации сообщений и ее оценка // Распознавание-2001. Сб. матер. 5-й междунар. конф. Курск, 2001. 4.2. С. 235 - 237.

8. Анпилогов Е.Г. Алгоритм квазиадаптивной маршрутизации сообщений с обходом отказов // Распознавание-2003. Сб. матер. 6-й междунар. конф. Курск, 2003. С. 229-231.

»2238 4

РНБ Русский фонд

2005-4 23863

V

Введение.

Глава 1. Задачи обработки сообщений в параллельных системах.

1.1. Архитектура современных параллельных систем.

1.2. Межпроцессорное взаимодействие в параллельных системах.

1.3. Задача маршрутизации сообщений и подходы к ее решению.

1.4. Алгоритмы отказоустойчивой маршрутизации.

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

Глава 2. Процедура маршрутизации сообщений с обходом отказов.

2.1. Модель параллельной системы и представление процесса маршрутизации4)

2.2. Характеристика предлагаемой процедуры маршрутизации.

2.3. Примеры использования процедуры маршрутизации.

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

Глава 3. Устройство маршрутизации на основе созданной процедуры.

3.1. Функциональная организация устройства маршрутизации.

3.2. Анализ работы устройства маршрутизации.

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

Глава 4. Оценка эффективности разработанной процедуры и устройства динамической маршрутизации сообщений.

4.1. Оценка допустимости и длины маршрутов.

4.2. Оценка вероятности правильной передачи сообщения.

4.3. Аналитическая оценка аппаратной сложности устройства маршрутизаци и

4.4. Определение предельной длины таблиц маршрутизации.

4.5. Оценка длины формата сообщения.

4.6. Экспериментальная оценка созданной процедуры маршрутизации.

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

4.6.2. Архитектура экспериментальных программных средств.

4.6.3. Q-схемы моделируемой системы.

4.6.4. Результаты эксперимента.

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

Одним из перспективных направлений развития параллельных вычислительных систем (ВС) является создание массивно параллельных систем с распределенной памятью (МРР-системы). Отличительной особенностью МРР-систем является разделение физической памяти между процессорами (модулями), что дает возможность каждому модулю работать независимо от других. Благодаря такой архитектуре МРР-системы позволяют ввести средства оперативного восстановления работоспособности при появлении отказов модулей и/или связей (локальных отказовых неоднородностей). Указанные средства способны динамически исключать отказы из логической структуры системы, обеспечивая сохранение ее работоспособности в целом (возможно с деградацией производительности).

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

Существует множество алгоритмов отказоустойчивой (динамической) маршрутизации, ориентированных на системы с различными топологическими структурами (матрицы, гиперкубы, кубы циклов). Последние разработки в данной области - «Алгоритм адаптивной маршрутизации с кластерами без отказов» JI.A. Закревского и М.Г. Карповского, «Алгоритм отказоустойчивой маршрутизации на основе расширенных безопасных уровней», разработанный Jie Wu, «Алгоритм отказоустойчивой маршрутизации на основе распределенного блока восстановления», предложенный Gul N. Khan, Gu Wei,

Алгоритм отказоустойчивой маршрутизации на базе вектора вероятности», созданный J. Al-Sadi, К. Day, М. Ould-Khaoua.

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

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

Работа выполнена при поддержке фанта «Столетовские гранты-2003» Министерства образования РФ, а также в рамках совместных работ с ОКБ «Авиаавтоматика» по договору №1.121.03 от 22 августа 2003 года. Основная часть диссертационной работы выполнена в рамках плана научно-исследовательских работ Курского государственного технического университета по единому заказ-наряду Министерства образования Российской Федерации в 1998-2004 годах, утвержденному начальником управления планирования и финансирования научных исследований.

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

Задачами диссертационной работы являнтя:

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

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

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

4. Аналитические оценки аппаратной сложности устройства маршрутизации и вероятности правильной передачи сообщений в МРР-системе с использованием разработанной процедуры.

5. Исследование на имитационной модели зависимости времени передачи сообщений в МРР-системе от интенсивности потоков исходящих сообщений в процессорах при различных значениях наработки процессора на отказ и оценка потери сообщений из-за отказов при различных значениях наработки процессора на отказ.

Методы исследования.

При решении поставленных задач использовались методы теории множеств, теории графов, теории вероятностей, теории проектирования ЭВМ, теории автоматов и математической статистики. Экспериментальные исследования проводились на основе библиотеки классов имитационного моделирования и визуальной среды программирования, разработанных под руководством доц. Зотова И.В.

Научная новизна результатов диссертационной работы:

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

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

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

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

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

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

3. Определен размер таблицы маршрутизации предлагаемого модуля для систем реальной размерности, не превышающий 1К слов.

Технические решения защищены патентом РФ № 2222044 и решениями о выдаче патентов по заявкам № 2003104071, № 2003129963.

Реализация и внедрение.

Результаты диссертационной работы используются в учебном процессе в Курском государственном техническом университете в дисциплинах «Организация ЭВМ и систем», «Отказоустойчивые многопроцессорные платформы» и внедрены на предприятиях ОАО «Счетмаш», ООО ПП «Микрокод», что подтверждается соответствующими актами.

Апробация работы.

Основные положения диссертационной работы докладывались и получили положительную оценку на НТК «Распознавание-2001» (г. Курск, 2001), НТК «Методы и средства систем обработки информации» (г. Курск, 2003), НТК «Распознавание-2003» (г. Курск, 2003), на научно-технических семинарах Курского государственного технического университета с 2001 по 2004 год.

Публикации.

Результаты диссертационной работы отражены в 8 публикациях, в том числе 3 статьях, 1 патенте на изобретение, 2 решениях о выдаче патента. В работах, опубликованных в соавторстве, лично соискателем предложено: в [1,2,7] - процедура выбора направления передачи сообщения, в [6,8] - алгоритм ретрансляции сообщений в матричных параллельных системах, в [3,4,5] -модуль для передачи сообщений.

На защиту выносятся:

1. Процедура отказоустойчивой маршрутизации сообщений для матричных МРР-систем.

2. Результаты аналитической оценки вероятности правильной передачи сообщений МРР-системой при использовании разработанной процедуры и аппаратной сложности устройства маршрутизации.

3. Результаты исследования на имитационной модели зависимости времени передачи сообщений в МРР-системе от интенсивности потоков исходящих сообщений в процессорах при различных значениях наработки процессора на отказ и оценка потерь сообщений из-за отказов при различных значениях наработки процессора на отказ.

4. Функциональная схема устройства маршрутизации на основе созданной процедуры.

Объем и структура работы.

Диссертационная работа состоит из введения, четырех глав, заключения, списка литературы и приложений. Работа содержит 160 страниц текста и поясняется 37 рисунками и 8 таблицами; список литературы включает 78 наименований; приложения содержат 71 страницу. Общий объем составляет 231 страницу.

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

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

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

3. Определенные зависимости времени передачи сообщений в МРР-системе от интенсивности потока исходящих сообщений показывают, что данное время для предлагаемой процедуры не хуже чем, у лучших из аналогов (лишь первое сообщение по маршруту может передаваться дольше других из-за необходимости возвратов и переходов на альтернативные реализации).

Заключение

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

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

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

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

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

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

1. А. Богданов, В. Мареев, Е. Станкова, В. Корхов Архитектуры и топологии многопроцессорных вычислительных систем. // Электронный учебник, http://www.informika.ru

2. Гибкое автоматизированное производство // Под общ. ред. С.А. Майорова, Г.В. Орловского, С.Н. Халкиопова. Л.: Машиностроение, 1985.-454 с.

3. Feng T.-Y. A survey of interconnection networks // IEEE Computer, 1981. vol.14, № 12. PP. 12-27

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

5. 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.

6. Arden B.W., lee H. Analysis of chordial ring network // IEEE Transactions on Computers, 1981. vol. C. 30, № 4. PP. 291-295.

7. Wu S.B., Liu M.T. A cluster structure as an interconnection network for large multimicrocomputer systems // IEEE Transactions on Computers, 1981. vol. C. 30, № 4. PP. 254-264.

8. Horowitz E., Zorat A. The binary tree as an interconnection network: applications of multiprocessor systems and VLSI // IEEE Transactions on Computers, 1981. vol. C. 30, № 4. PP. 247-253.

9. Schin K.G., Lee Y.-H., Sasidhar J. Design of HM2p a hierarchical multimicroprocessor for general-purpose applications // IEEE Transactions on Computers, 1982. vol. C. 31, № 11. PP. 1045-1053.

10. 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.

11. Kupta P., McKeown N. Design and Implementation of a Packet Switched Routing Chip // Proceedings of Hot Interconnects 6. Stanford, 1998. PP. 7784.

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

13. Saad Y., Schults M.U. Topological properties of hypercubes // IEEE Transactions, 1988. vol. C. 37, № 7. PP. 867-872.

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

15. Preparata F.P., Vuillemin J. The cube-connected cycles: a versatile network for parallel computation // Communications of ACM, 1981. vol. 24, № 5. PP. 300-309.

16. Апраксин Ю.К., Запевалин A.A., Кирюхин B.B. Алгоритмы маршрутизации для сетей с коммутацией сообщений // Автоматика и вычислительная техника, 1982. №2. С. 87-92.

17. Herbordt М.С., Corbertt J.C., Weems С.С. Practical algorithms for online routing on fixed and reconfigurable meshes // J. Paral. Distrib. Comput., 1994. vol.20, No.3. PP. 341-356.

18. Kunde M. Packet routing on grids of processors // Lecture Notes in Computer Science, New York: Springer-Verlag, 1998. vol.401. PP. 129-136.

19. Лукьянов A.B., Первозванский А. А. Адаптивное управление маршрутизацией в коммуникационных сетях с коммутацией пакетов // Автоматика и вычислительная техника, 1983. №1. С. 60-65.

20. Шеметов В.В. Гибридные алгоритмы маршрутизации для информационно-вычислительных сетей // Автоматика и вычислительная техника, 1986. №1. С. 50-53.

21. Шеметов В.В. Децентрализованные алгоритмы маршрутизации для коммуникационных сетей с коммутацией пакетов // Автоматика и вычислительная техника, 1985. №6. С. 17-26.

22. Самошин В.Н. Устройство формирования маршрута сообщения в однородной вычислительной системе // А.С. 1287172 СССР G 06 F15/16; опубл.23.02.93, БИ№41

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

24. Организация и синтез микропрограммных мультимикроконтроллеров // И.В. Зотов, В.А. Колосков, B.C. Титов, К.А. Сапронов, А.П. Волков, Курск: Изд-во «Курск», 1999. 368 с.

25. Valiant L.G., Bredner G.J. Universal schemes for parallel computation // Proc. 13 ACM Symp. Theory of Comput. PP. 88-92.

26. Leighton F.T., Makedon F., Tollis I. A 2n-2 step algorithm for routing in an nxn array with constant size queues // Proc. 1 ACM Symp. Parallel Alg. and Archit., 1989. PP. 328-335.

27. Устройство для формирования маршрута сообщений в однородной вычислительной системе // В.А. Мельников и др.; А.С. 1462344 СССР G 06 F 15/16; опубл.28.02.89, БИ №8.

28. Устройство для формирования маршрута сообщений в однородной вычислительной системе // В.А. Мельников и др.; А.С. 1501080 СССР G 06 F 15/16; опубл. 15.08.89, БИ №30.

29. Устройство для формирования маршрута сообщений в однородной вычислительной системе // В.А. Мельников и др.; А.С. 1508228 СССР G 06 F 15/16; опубл. 15.09.89, БИ №34.

30. Gul N. Khan, Gu Wei, Fault-tolerant wormhole routing using a variation of distributed recovery block approach // IEEE Proc. Computers and Digital Techniques, 2000. vol.147, No.6, PP. 397-402.

31. Jie Wu, Fault-tolerant adaptive and minimal routing in mesh-connected multicomputers using extended safety levels // Department of computer science and engineering, Florida, Atlantic University, 2000, vol 22., PP. 273-294.

32. Al-Sadi J., Day K., Ould-Khaoua M. Probability-based fault-tolerant routing in hypercube // The Computer Journal, 2000. vol. 44, No. 5, PP. 369373.

33. Колосков B.A., Титов B.C. Метод самоорганизации отказоустойчивой мультимикроконтроллерной сети // Автоматика и телемеханика, 1998. №3. С. 173-183.

34. Зотов И.В. Процедурно-логическая модель маршрутизации сообщений в микроконтроллерных сетях с матричной организацией // Автоматика и вычислительная техника, 1999. №3. С. 59-68.

35. Мельников В.А. и др. Модуль матричного коммутатора.; А.с. 1133594 СССР G 06F 9/22; опубл. 07.01.85, БИ№ 1

36. Советов Б.Я., Яковлев С.А. Моделирование систем. М.: Высшая школа, 2001.273 с.

37. Анпилогов Е.Г., Беляев Ю.В., Зотов И.В. Квазиадаптивная маршрутизация сообщений в матричных микроконтроллерных сетях / КГТУ, Курск, 2001, Деп. в ВИНИТИ 07.06.2001, №1417-В2001. 26 с.

38. Анпилогов Е.Г., Зотов И.В. Модель квазиадаптивной маршрутизации сообщений и ее оценка. // Сборник материалов 5-ой международной конференции. Распознавание-2001, Курск, 2001. КурскГТУ. 4.2 С. 235 -237.

39. Анпилогов Е.Г., Беляев Ю.В., Зотов И.В. Модуль для ретрансляции сообщений в матричном коммутаторе. / Патент №2222044 Россия, кл. G 06 F 15/173 заявл. 08.04.2002, опубл. 20.01.2004, БИ№2. 16 с.

40. Анпилогов Е.Г., Процедура вещания сообщений в матричных параллельных системах. // Методы и средства систем обработкиинформации. Сборник научных статей, Курск, 2003. КурскГТУ, вып. №3. С. 79 87.

41. Анпилогов Е.Г. Алгоритм квазиадаптивной маршрутизации сообщений с обходом отказов. / Сборник материалов 6-ой международной конференции «Распознавание-2003», Курск, 2003. С. 229-231.

42. Анпилогов Е.Г., Беляев Ю.В., Зотов И.В. Модуль для передачи и вещания в матричном коммутаторе. / Решение о выдаче патента от 22.09.2004, по заявке №2003104071.

43. Анпилогов Е.Г., Ефремов В.В., Зотов И.В. Модуль для обмена сообщениями. / Решение о выдаче патента от 13.10.2004, по заявке №2003129963.

44. Анпилогов Е.Г., Зотов И.В, Титов B.C. Процедура отказоустойчивой маршрутизации сообщений для параллельных вычислительных систем. / Известия КурскГТУ, Курск, 2004, №2(13). С. 74 78.

45. Morgan S., Delaney М. The Internet and the local telephone network: conflicts and opportunities // XVI International Switching Symposium, -Toronto, 1997, PP. 561-569.

46. 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.

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

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

49. Perparata P.P., Vuillemin J. The cube-connected connected cycles: a versatile network for parallel computation // Commun. OfACM., 1981. vol. 24, №5. PP. 300-309.

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

51. Tamir Y., Frazier G. High performance multi-queue buffers for VLSI communication switches // Proc. of 15th Ann. Symp. on Сотр. Arch., 1988. PP. 343-354.

52. Tassiulas L., Ephremides A. Stability properties of constrained queueing systems and scheduling policies for maximum throughput in multihop radio networks // IEEE Trans. Automatic Control, 1992, vol. 37, №12, PP. 19361948.

53. Tobagi F.A. Fast packet switch architectures for broadband integrated services digital networks // Proceedings of the IEEE, 1990, vol.78, №1, PP. 133-167.

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

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

56. Wu S.B., Liu M.T. A cluster structure as an interconnection network for large multimicrocomputer systems // IEEE Transactions on Computers, 1981. vol. C.30, №4. PP. 254-264.

57. Perparata P.P., Vuillemin J. The cube-connected connected cycles: a versatile network for parallel computation // Commun. OfACM., 1981. vol. 24, №5. PP. 300-309.

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

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

60. Tamir Y., Frazier G. High performance multi-queue buffers for VLSI communication switches // Proc. of 15th Ann. Symp. on Сотр. Arch., 1988. PP. 343-354.

61. Корн Г., Корн Т. Справочник по математике для научных работником и инженеров. М.: Наука, 1968. 720 с.

62. Кристофидес Н. Теория графов. Алгоритмический подход. М.: Мир, 1978. 432 с.

63. Кузнецов Б.П., Шалыто А.А. Метод независимых фрагментов для построения линеаризованных структурированных граф-схем алгоритмов, реализующих системы булевых формул // А и Т., 1998. №9. С. 142-154.

64. Кузнецов Б.П., Шалыто А.А. Реализация булевых формул линейными бинарными графами. I. Синтез и анализ // А и Т., 1994. №5. С. 132-142.

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

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

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

68. Лазарев В.Г., Пийль Е.И., Турута Е.Н. Построение программируем управляющих устройств. М.: Энергоатомиздат, 1984. 192 с.

69. Лукьянов А.В., Первозванский А.А. Адаптивное управление маршрутизации в коммуникационных сетях с коммутацией пакетов // А и ВТ., 1983. С. 60-65.

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

71. Микропрограммный модуль / B.C. Харченко и др.; А.с. 1427366 СССР G 06 F 9/22; опубл. 30.09.88, БИ №36.

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

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

74. Палагин А.В. и др. Реализация микропрограммных автоматов на ПЛИС//УС и М, 1991. №8. С. 18-22.

75. Самошин В.Н. Устройство формирования маршрута сообщения в однородной вычислительной системе / А.с. 1287172 СССР О 06 Р 15/16; опубл. 30.01.87, БИ №4.

76. Скляров В.А. Модульные граф-схемы алгоритмов // А и ВТ., 1984. №2. С. 82-87.