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

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

Наджаджра Мухаммед Хасан Наджи

АЛГОРИТМ И УСТРОЙСТВО РАСПРЕДЕЛЕННОГО ОТКАЗОУСТОЙЧИВОГО ВЕЩАНИЯ СООБЩЕНИЙ С ГРУППОВОЙ ИНДЕКСАЦИЕЙ ПРИЕМНИКОВ

05 13 05 - Элементы и устройства вычислительной техники и систем управления

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

В1||11 ЛИПШИ II

00316757

Курск-2008

Работа выполнена в ГОУ ВПО «Курский государственный технический университет» на кафедре вычислительной техники в совместной научно-исследовательской лаборатории Центра информационных технологий в проектировании РАН и Курского государственного технического университета «Информационные распознающие телекоммуникационные интеллектуальные системы»

Научный руководитель доктор технических наук, доцент Зотов Игорь Валерьевич

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

доктор технических наук, профессор Довгаль Виктор Митрофанович

кандидат технических наук Беляев Юрий Валентинович

Ведущая организация Белгородский государственный технологический университет имени В Г Шухова

Защита состоится 12 мая 2008 г в 14 00 часов на заседании совета по защите докторских и кандидатских диссертаций Д212 105 02 при Курском государственном техническом университете по адресу 305040, Курск, ул 50 лет Октября, 94 (конференц-зал)

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

Отзывы на автореферат в двух экземплярах, заверенные печатью, просим направлять по адресу 305040, Курск, ул 50 лет Октября, 94, КурскГТУ, ученому секретарю совета по защите докторских и кандидатских диссертаций Д 212 105 02

Автореферат разослан 10 апреля 2008 г

Ученый секретарь совета Д 212 105 02

Е А. Титенко

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

Известно широкое разнообразие подобных алгоритмов маршрутизации (Л А. За-кревский, А В Тимофеев, R V Воррапа, S Chalasam, J Duato, D К Panda, J Wu и др ) Они ориентируются на различные классы и топологические структуры систем, используют специфические правила обхода отказов и позволяют реализовать межпроцессорный обмен информацией для разных видов комбинаций отказов Известные алгоритмы маршрутизации, применяемые в мультипроцессорах, предполагают только попарный обмен сообщениями (umcast), в то время как на практике часто возникает необходимость организации так называемых вещательных режимов обмена К ним относится, в частности, передача сообщения от одного источника нескольким приемникам (broadcast) Реализация таких режимов известными алгоритмами маршрутизации требует многократной выдачи одного и того же сообщения, что приводит к росту среднего времени передачи сообщений и снижает вероятность их успешной маршрутизации Преодоление указанного недостатка возможно при условии применения алгоритмов отказоустойчивой маршрутизации, приспособленных к реализации вещательных режимов обмена сообщениями, и воплощение этих алгоритмов на аппаратном уровне в соответствующих коммуникационных устройствах Исходя из сказанного, снижение времени широковещательной передачи сообщений при одновременном повышении вероятности их успешной маршрутизации в отказоустойчивых матричных мультипроцессорах является актуальной научно-технической задачей

Объект исследования распределенные коммуникационные средства в составе процессорных модулей матричных мультипроцессоров

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

Диссертационная работа выполнена при поддержке гранта «Столетовские гранты - 2003» Министерства образования РФ, а также в рамках плана НИР Курского государственного технического университета по единому заказ-наряду Министерства

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

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

Задачи исследований

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

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

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

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

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

6 Оценка аппаратной сложности устройства распределенного отказоустойчивого вещания сообщений

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

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

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

3 На основе расширенного аппарата О-схем разработана имитационная модель процедуры отказоустойчивого вещания, позволившая получить зависимости среднего времени передачи от интенсивности потоков сообщений, подтверждающие возможность снижения указанного времени широковещательной передачи в 2 и более раз Установлено, что созданный алгоритм сокращает число потерянных сообщений в вещательных режимах обмена информацией примерно на 20% при сохранении соотношения числа потерянных и доставленных сообщений, не превышающего 0,017

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

Практическая ценность результатов исследований

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

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

3 Аппаратная сложность разработанного устройства отказоустойчивого вещания сообщений соизмерима (по числу вентилей) с аппаратной сложностью известных коммуникационных устройств матричных мультипроцессоров

На защиту выносятся следующие научные результаты

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

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

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

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

Апробация работы Основные результаты, положения и выводы диссертации обсуждались на Международной научно-технической конференции «Information and telecommunication technologies m intelligent systems» (Spam, Mallorca, 2005, Italy, Katania, 2006), на Всероссийской конференции по проблемам математики, информатики, физики и химии (Москва, 2005), на Международной научно-технической конференции «Распознавание-2005» (Курск, 2005), на Международной научно-технической конференции «Медико-экологические информационные технологии» (Курск, 2005, Курск,

2007), а также на научных семинарах кафедры вычислительной техники КурскГТУ в период с 2003 по 2007 год

Публикации по теме диссертации Содержание диссертации опубликовано в 9 работах, среди которых имеется статья в научном издании, входящем в перечень ВАК, а также решение о выдаче патента на изобретение

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

Структура и объем диссертации Работа состоит из введения, четырех глав, заключения, приложений и списка литературы, включающего 88 наименований Диссертация содержит 195 страниц текста (включая три приложения) и поясняется 30 рисунками и 5 таблицами

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

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

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

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

Постоянный рост числа модулей в многопроцессорных системах обусловливает существенное увеличение вероятности локальных отказов Отсутствие средств для их «логического изолирования» способно привести к такой ситуации, что система, содержащая 99% работоспособных модулей, может быть признана отказавшей За последние два десятилетия были разработаны методы, позволяющие перестраивать логическую структуру многопроцессорной системы, исключая из нее отказовые неоднородности (ЭВ Евреинов, А В Каляев, Н В Лаходынова,М Сами,Р Стефанелли и др) Это дало возможность снизить критичность системы ко многим комбинациям локальных отказов и обеспечить ее потенциальную работоспособность даже при наличии 20% отказов и более Однако, будучи исключенными из логической структуры системы, локальные отказы сохраняются в ее физической структуре, что накладывает специфические огра-

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

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

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

В работе рассматриваются мультипроцессоры, состоящие из идентичных модулей, объединенных матричной коммуникационной структурой (любой модуль имеет непосредственные связи не более чем с восемью соседями) Каждый модуль состоит из операционной и коммуникационной частей Физически модуль может быть представлен на отдельной плате или СБИС (возможен вариант интеграции на одном кристалле нескольких модулей) Крайний правый столбец матрицы содержит резервные модули, которые замещают основные модули в случае обнаружения их отказа (рассматриваются только отказы модулей в целом) Замещение основных модулей осуществляется согласно известному алгоритму ограниченного захвата (М Сами,Р Стефанелли)

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

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

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

На первом этапе вещания сообщение движется по фиксированному базовому маршруту Каждый такой маршрут разбивается на множество участков ограниченной длины А*, которая зависит от разрядности пакетов Передача сообщения в пределах участка может выполняться только «по прямой», в одном из восьми возможных направлений восток, северо-восток, север, северо-запад, запад, юго-запад, юг, юго-восток Направления идентифицируются целыми числами в возрастающем порядке, от О д ля востока до 7 для юго-востока (восток условно считается базовым направлением)

Участки маршрутов сообщений кодируются в локальных таблицах маршрутизации, которые модифицируются при загрузке выполняемой параллельной программы Каждый модуль содержит одну такую таблицу В ней хранится набор слов с информацией обо всех участках, которые начинаются данным модулем Каждое слово включает три поля поле направления текущего участка (Rot), поле длины текущего участка (Len), указатель на следующий участок (Next) Поле Rot может принимать одно из восьми возможных значений, от 0 до 7, в зависимости от направления передачи сообщения для данного участка Длина участка Len определяется соответствующим числом шагов передачи сообщения (трансляций) Указатель Next представляет собой адрес ячейки таблицы маршрутизации конечного модуля текущего участка, в которой размещено слово, представляющее очередной участок данного маршрута (при отсутствии следующего участка данный указатель нулевой) Таким образом, маршрут любой длины фактически задается в виде распределенного односвязного списка

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

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

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

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

Мультипроцессор опишем графом {М,Е), вершины М которого соответствуют физическим модулям, а дуги £сМхМ отражают межмодульные связи Пусть множество М отображено на гипотетическую матрицу с ЭД строками и Иг столбцами, =\М\, так, что модуль т%<аМ, расположенный на пересечении 2-й строки и ;-го

столбца (г = 1,N,,7=1,7^ имеет связи со всеми модулями, индексы которых отличаются от I,] не более чем на 1 Модули тМг еМ (г = считаем резервными

Д ля индикации текущего состояния модуля введем в рассмотрение признаки статуса §ч (/) = 1, если модуль т^ в момент / работоспособен, 3}) (?) = 0 иначе Выделим

подмножество работоспособных модулей М (/') с М и выберем произвольную пару модулей тч,ты еМ(г') (£г) V(/#у) Пусть тч - источник сообщения, а тк1 -ближайший к нему начальный модуль области вещания Допустим, передача сообщений от тч к тк1 выполняется по маршруту Я = Я(ту,тк1}, причем

* 'К,-*,'™«)) 0бозначим чеР63 И даииУ маршрута Я

(выраженную количеством трансляций) Будем рассматривать только простые маршруты, те УтаЬ е Я таЬ£Я\{таЬ)

Определим способы кодирования и разбиения маршрутов

Пусть У{тц) = |еу е Е - множество исходящих связей модуля тц (по определению 3<|к(оту)|<8, ае{г,г-1,г + 1}, Ь1,7 + 1})

Каждой связи ef (my )еК(ш9) поставим в соответствие трехразрядный двоичный вектор <т(ef (тч)) = a^ef (т0))• сгг[е1 {т^)) • сг3 {ef (тц)), где «•» - символ конкатенации, таким образом, чтобы выполнялось условие

£ {1,2,3} or, (ef' (mv )) ® <7, (er (m„ )) = 1, V/' * f

Соответствие между кодами jcr^e7и связями ef (m^eV^m^, Vmy eM, назовем разметкой Потребуем, чтобы разметка отвечала порядку следования направлений маршрутизации 0,1, 7

Закодируем маршрут R, применяя к каждой его трансляции ef (mai)e R подстановку вида a (ef (таЬ)) ef {таЬ) Получим маршрутный код, состоящий из цепочки векторов а(еГ(т<,ь)) и представляющий маршрут R /г^0'' = J^o-^e^ (и^)) • •а{е,"{тп^ Обозначим через длину

полученного маршрутного кода ji^J = 3|/?|

Разобьем маршрут R на участки 7?,,^, ,RX, таким образом, чтобы выполнялось 1^1 < A* (s = и было истинным условие

аг{тф,ты) = ^{maV,tnc,d) V(mab,mcc/),(maV,mcW)eRs, s =

Часть маршрутного кода соответствующую участку Rs обозначим как R^ и назовем маршрутным кодом j-ro участка

Каждому модулю тл е М поставим во взаимно однозначное соответствие таблицу маршрутизации

т{шаьу(т^{шаь),т^{гпаь),

где Т{с) (mab) = (f/+1 , , <pcs4 ) — подтаблица, соответствующая с-му маршруту, — число участков, начинающихся в модуле таЬ, F°+l, hcs+l, <p"s+i - соответственно направление, длина (s +1)-го участка с-го маршрута и указатель на подтаблицу с данными об

очередном участке с-го маршрута

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

I • Stage • Phase • Rot • Next • Len • Step • LA • NLast • Sign • Dev • RC, где I - информационное поле, Stage - поле номера этапа вещания, Phase - поле номера фазы передачи сообщения, Rot - поле направления текущего участка, Next - поле указателя на следующий участок, Len - поле длины текущего участка, Step - поле номера активной трансляции, LA- поле логического адреса приемника, NLast - одноразрядное поле индикации предпоследнего участка маршрута, Sign - поле направления обхода отказов, Dev - поле степени отклонения, RC - поле кода маршрута обхода

Поле I хранит данные для передачи модулям-приемникам (например, результат вычислений, адрес удаленного доступа, признак состояния процесса и тп) Остальные

поля составляют адресную часть и предназначены для управления процессом передачи сообщения Одноразрядное поле Stage определяет текущий этап широковещательной передачи (Stage=0 - первый этап, Stage=l - второй этап) Двухразрядное поле Phase содержит номер текущей фазы передачи сообщения. Значение Phase=00 соответствует отсутствию отказов, остальные - различным фазам обхода отказов В трехразрядном поле Rot задается направление передачи сообщения на текущем участке или направление вещания Поле Next хранит указатель на следующий участок Поле Len служит для хранения длины текущего участка или размера области вещания Поле Step хранит номер активной трансляции текущего участка В поле NLast фиксируется порядковый признак текущего участка 1 для предпоследнего участка и 0 д ля остальных участков Поле LA используется для задания логического адреса приемника области вещания в формате i»j, где i - номер строки, a j - номер столбца матрицы Поле Sign указывает направление обхода отказов (0 - основное направление, 1 - противоположное направление) Поле Dev служит для учета числа шагов, выполненных сообщением в направлении ортогональном к Rot Поле RC определяет маршрут сообщения при обходе отказов на текущем участке маршрута и имеет формат

RC = Zft*.*Zr* *Z2*ZX, где Zr - четырехразрядное толе r-й трансляции обхода Zr=ar* Z*r, 2* - трехразрядное поле кода г-н трансляции обхода, аг - метка-признак активности г-й трансляции

обхода {г -1, h), h - предельная длина маршрута обхода отказов

На рисунке 1 представлена граф-схема алгоритма, описывающего один цикл обработки сообщений при выполнении отказоустойчивого вещания В этой граф-схеме приняты следующие обозначения BUF1 и BUF2 - группы входных буферов для приема сообщений от соседних модулей на первом и втором этапах вещания соответственно, LA - логический адрес текущего модуля, f - функция вычисления логического адреса очередного приемника сообщения, m(z) - физический соседний модуль, расположенный в направлении z относительно текущего модуля, a BUSz — избыточная шина для передачи сообщения в направлении г на втором этапе вещания (z =0,1, , 7)

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

Разработанные алгоритм и правила обхода отказов прошли верификацию и являются логически корректными

Правило отклонения

1 Принять z = Rot

2 Если модуль m{z) работоспособен то перейти к фазе компенсации, считая s = 1

3 Если г < h, то перейти к п 5, иначе фатальный отказ

4 Если Sign=0, принять Sign=l, Z* = 0, перейти к возврату, иначе фатальный отказ

КОНЕЦ J

Рис 1 Граф-схема алгоритма отказоустойчивого вещания

5 Установить Zr* = (z' + (l -Sign * 2)) mod 8

6 Если Z* = 4, то перейти к п 4

7 Принять z = (Z'r + Rot) mod 8

8 Если модуль m(z) отказал, то перейти к п 5

9 Если Z* е{0,1,7}, то принять Step=Step+l иперейгакп И

10 Если Z* е {3,5}, то принять Step = Step -1

11 Если Z* £ {0,4}, то принять Dev = Dev +1

12 Установить г = г +1

13 Выдать сообщение модулю m(z) Конец обработки сообщения

Правило компенсации

1 Если Dev = 0, то перейти к п 3

2 Если г < h, то перейти к п 5, иначе выполнить п 4

3 Если Step < Len, то конец обхода отказов

4 Если Sign=0, принять Sign=l, Z* = 0, перейти к возврату, иначе фатальный отказ.

5 Установить z' = 8

6 Если Z* = 2 + 2(1 - s) + 4i(l - Sign), то перейти к п 11

7 Принять z = (z* + Rot) mod 8

8 Если модуль m(z) отказал, то перейти к п 10

9 Принять z' = Z*

10 Установить Z* = (Z* + (2 * Sign -1)) mod 8 и перейти к п 6

11 Если z' = 8, то принять Z* = 0 и перейти к фазе отклонения

12 Принять z = (z' + Rot) mod 8 и j = 0

13 Если z' е {0,1,7}, то принять Step = Step +1 и перейти к п 15

14 Если z' € {3,5}, то принять Step = Step -1

15 Если z' £ {0,4}, то принять Dev = Dev-1

16 Установить г = г +1

17 Выдать сообщение модулю Конец обработки сообщения

Правило возврата

1 Если г = 1, то принять Dev = 0 и перейти к фазе отклонения

2 Принять г = г -1

3 Принять z = (Z* + Rot + 4) mod 8

4 Если Z* е {0,1,7}, то принять Step = Step -1 и перейти к п 6

5 Если Z* е {3,5}, то принять Step = Step + 1

6 Установить Z* = 0

7 Выдать сообщение модулю m(z) Конец обработки сообщения

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

На рисунке 2 дано укрупненное представление структурной организации разработанного устройства вещания

Рис 2 Укрупненная структурная организация устройства отказоустойчивого вещания BUFxy - FIFO-буферы, S W - коммутатор, fllARot) - схема вычисления логического адреса следующего приемника, DISP0-DISP7 - блоки диспетчеризации сообщений, ВА - шинный арбшр, RGLA - регистр логического адреса модуля, CTL1, CTL2 -блоки управления, CLK - блок синхронизации

Устройство имеет входы INO, INI, , IN7 и выходы OUTO, OUT1, , OUT7, предназначенные для организации непосредственных связей с другими аналогичными устройствами (модулями) и используемые для передачи сообщений на первом этапе вещания Отдельные вход INP и выход OUTP служат для подключения разработанного устройства к процессорному модулю Совокупность шин BUS(y') используется для вещательной передачи сообщений на втором этапе вещания Каждая шина BUS(y') объединяет четыре физических модуля матричной структуры г • j, i + \»j, i» j+l, i +1 • j +1, которые могут иметь логический адрес i • j

Основными блоками устройства являются FIFO-буферы, коммутирующие блоки и элементы управления Буферы BUF10-BUF17 используются для хранения сообщений, поступающих от соседних физических модулей на первом этапе вещания Буфер BUF18 хранит сообщения, пришедшие от процессорного модуля Буферы BUF19, BUF20-BUF23 предназначены для хранения сообщений, поступающих от соседних логических модулей на втором этапе вещания, причем в BUF19 передаются сообщения, для которых второй этап вещания еще не завершен Коммутатор SW вместе с блоком управления CTL1 выполняют функцию маршрутизации сообщений согласно алгоритму на рисунке 1 (правая параллельная ветвь) и разработанным правилам обхода отказов Мультиплексор MX с блоком управления CTL2 служат для коммутации сообщений, пришедших от логических соседних модулей Блоки диспетчеризации DISP0-DISP7 обеспечивают перераспределение обработанных сообщений между соответствующими выходами OUT и шинами BUS в зависимости от этапа их вещания

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

В ходе имитационного моделирования рассматривался мультипроцессор в конфигурации 8x8 процессорных модулей Предполагалось, что каждый модуль независимо генерирует поток сообщений с интенсивностью Л = 1/50,1/100,1/150,1/200 и 1/250 (сообщение/тактов), где такт соответствует периоду следования импульсов синхронизации модуля, а модули отказывают независимо друг от друга с интенсивностью тр1/50000 (отказ/тактов) Конфигурации маршрутов вещания выбирались случайно (рассматривались маршруты, содержащие от 1 до 3 участков), при этом число г приемников каждого сообщения считалось равным 2 (наихудший случай для разработанного алгоритма) В результате моделировании регистрировалось число доставленных сообщений (d), число сообщений, потерянных из-за фатальной ситуации в алгоритме вещания (Г), а также среднее время передачи сообщения (Т) Моделирование выполнялось циклами продолжительностью по 2000 тактов, каждый из результатов усреднялся по 100 циклам

На рисунке 3 представлены зависимости ряда величин (среднего времени передачи сообщения Г - рис 3,а, числа потерянных сообщений I - рис 3,6 и отношения числа потерянных к числу доставленных сообщений lid- рис 3,в) от средней интенсивности потока сообщений модуля Я, полученные в ходе имитационного моделирования с учетом введенных ограничений Темными столбиками на рисунке 3 показаны значения величин, соответствующие динамическому алгоритму попарного обмена, светлыми столбиками отображены значения для разработанного алгоритма вещания

Рис 3,а демонстрирует существенное (в 2 и более раз) снижение среднего времени передачи сообщения Т при использовании разработанного алгоритма (в особенности при более высоких интенсивностях потоков сообщений), которое является следствием сокращения среднего числа сообщений, находящихся в коммуникационной среде Рис 3,6 показывает некоторое уменьшение абсолютного числа потерянных сообщений (примерно на 20%), что обусловливает снижение числа повторных передач Соотношение числа потерянных и доставленных сообщений сопоставляемых алгоритмов примерно одинаково и составляет не более 0,017 (см рис 3,в)

Г, тактов

(а)

I'

£

;

1

1 |_| т

| 1 1 ■ 1 Я 1_

I, сообщений

50

(б)

г

т Т г

¿1— ■Я _т

8

1/150 1/200 11250

Я, сообщение/тактов Ш

0.025 у--

1/150 1/200 1Е50

Л, сообщение/тактов

(в)

0,02----

Л, сообщение/тактов

Рис. 3. Зависимости, полученные в результате вычислительного эксперимента: доверительный интервал соответствует вероятности Р=0.98

В заключении сформулированы основные результаты и выводы диссертации.

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

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

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

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

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

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

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

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

4 На основе имитационного моделирования получено подтверждение преимуществ разработанного алгоритма перед лучшими известными аналогами по среднему времени передачи сообщений (в 2 и более раз) Установлено, что созданный алгоритм и устройство на его основе обеспечивают снижение числа потерянных сообщений на 20% при сохранении соотношения числа потерянных и доставленных сообщений не выше 0,017

СПИСОК ПУБЛИКАЦИЙ ПО ТЕМЕ ДИССЕРТАЦИИ

Статья в научном издании по перечню ВАК Минобрнауки РФ

1 Наджаджра, М X Организация отказоустойчивого межпроцессорного взаимодействия в матричных мультикомпьютерах [Текст] / MX Наджаджра [и др] // Известия ТулГУ Бизнес-процессы и бизнес-системы 2006 Вып 4 С 3-9

Статьи

2 Наджаджра, М X Алгоритм отказоустойчивой маршрутизации сообщений с «вращающейся системой координат» [Текст] / MX Наджаджра [и др] // Методы и средства систем обработки информации Сборник научных статей Курск КурскГТУ, 2007 Вып 4 С 40-47

3 Наджаджра, М X Организация распределенного отказоустойчивого вещания сообщений в матричных мультипроцессорах с использованием групповой идентификации приемников [Текст] / М X Наджаджра, Курск, гос техн ун-т -Курск, 2007 32 с -Деп в ВИНИТИ 4 12 07,№1125-В2007

Материалы и тезисы докладов

4 Najajra, М Н A fault-tolerant message routing procedure with rotating coordinates [Текст] / M H Najajra [et al ] // Proc 3rd Int Conf Information and Telecommunication Technologies m Intelligent Systems, Spain, Mallorca, June 02-09 2005 - Mallorca, 2005 -P 88-93

5 Наджаджра, M X Использование аппарата Q-схем для моделирования алгоритмов маршрутизации [Текст] / М X Наджаджра [и др ] // Оптико-электронные приборы и устройства в системах распознавания образов, обработки изображений и символь-

ной информации материалы 7-й Международной научно-технической конференции, Курск,4-7октября2005г -Курск КурскГТУ,2005 -С 179-181

6 Абдель-Джалил, ДжН Процедура отказоустойчивой маршрутизации с динамическим изменением последней реализации [Текст] / Дж Н Абдель-Джалил, МХ Наджаджра // Медико-экологические информационные технологии материалы докладов VIII Международной научно-технической конференции, Курск, 2005 г - Курск КурскГТУ,2005 -С. 141-144

7 Зотов, ИВ Универсальная коммуникационная процедура для параллельных вычислительных систем [Текст] / И В Зотов, МХ Наджаджра [и др.] // Медико-экологические информационные технологии материалы докладов Юбилейной Международной научно-технической конференции, Курск, 24-25 апреля 2007 г - Курск КурскГТУ, 2007 - С 163-167

Свидетельство о регистрации программы

8 Свидетельство о регистрации программы для ЭВМ №2007611310 Визуальная среда имитационного моделирования У^иаК^СИаП /ИВ Зотов, М Х.Наджаджра [и др ] (РФ) - М РосПатент, заявлено 13 02 2007, дата регистрации 27 03 2007

Решение о выдаче патента на изобретение

9 Решение о выдаче патента по заявке №2007114559 Микроконтроллерная сеть / С В Волобуев, О В Крикунов, М X Наджаджра [и др ] (РФ) - М РосПатент, заявлено 17 04 2007

Соискатель

МХ Наджаджра

Подписано в печать 07 04 2008 г Формах 60x841/16

Печ л 10 Тираж 100 экз Заказ 8_

Курский государственный технический университет Издагельско-полиграфический центр Курского государственного технического университета 305040, г Курск, ул 50 лет Октября, 94

Введение.

1. Коммуникационные процессы и устройства в современной вычислительной технике и системах управления.

1.1. Значение и виды коммуникационных процессов.

1.2. Организация коммуникационных устройств и систем.

1.3. Реализация коммуникационных процессов в условиях наличия отказов и дефектов.

Выводы.

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

2.1.Особенности класса рассматриваемых многопроцессорных систем.

2.2. Организация межмодульного информационного обмена в рассматриваемых системах. Вещание сообщений.

2.3. Процедура отказоустойчивого вещания с групповой индексацией приемников сообщения.

2.3.1. Содержательная характеристика процедуры вещания. Принцип групповой индексации приемников сообщения.35!

2.3.2. Формализованное представление процедуры вещания.392.3.3. Структура широковещательного сообщения.

2.4. Алгоритм отказоустойчивого вещания. Правила обхода отказов.43'

Выводы.

3. Организация устройства отказоустойчивого вещания-сообщений'.503.1. Принципы организации и архитектура устройства вещания-.

3.2. Структурная организация устройства вещания.52'

3.2.1. Организация входного тракта устройства^.

3.2.2. Организация блока анализа ситуаций.

3.2.3; Организация блока модификации маршрутных кодов.

3.2.4. Синхронизация работы блоков устройства.

3.3. Процесс функционирования устройства вещания.

3.3.1. Исходное состояние.

3.3.2'. Запуск устройства.

3.3.3. Вещание сообщений при отсутствии отказов.

3.3.4. Фаза отклонения.

3.3.5. Фаза компенсации.

3.3.6. Фаза возврата.

3.3.7. Иллюстративный пример.101*

Выводы.

4. Исследование функциональной эффективности алгоритма и устройства отказоустойчивого вещания.

4.1. Задачи и методика исследования функциональной эффективности

4.1.1. Задачи исследования функциональной эффективности.

4.1.2. Методика оценки среднего времени передачи сообщений.

4.1.3. Методика оценки вероятности успешной маршрутизации сообщений.

4.1.4. Методика оценки аппаратной сложности устройства.

4.2. Организация и результаты имитационного моделирования.

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

4.2.2. Организация вычислительного эксперимента.

Синтез имитационной модели.

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

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

4.3. Результаты оценки аппаратной сложности устройства.

Выводы.

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

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

Известно широкое разнообразие подобных алгоритмов маршрутизации (Л.А. Закревский, А.В. Тимофеев, R.V. Boppana, S. Chalasani, J. Duato, D.K. Panda, J. Wu и др.). Они ориентируются на различные классы и топологические структуры систем, используют специфические правила обхода отказов и позволяют реализовать межпроцессорный обмен информацией для разных видов комбинаций отказов. Известные алгоритмы маршрутизации, применяемые в мультипроцессорах, предполагают только попарный обмен сообщениями (uni-cast), в то время как на практике часто возникает необходимость организации так называемых вещательных режимов обмена. К ним относится, в частности, передача сообщения от одного источника нескольким приемникам (broadcast).

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

Объект исследования: распределенные коммуникационные средства в составе процессорных модулей матричных мультипроцессоров.

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

Диссертационная работа выполнена при поддержке гранта «Столетов-ские фанты — 2003» Министерства образования РФ, а также в рамках плана НИР Курского государственного технического университета по единому заказ-наряду Министерства образования РФ в 2003-2007 годах, утвержденному начальником управления планирования и финансирования научных исследований.

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

Задачи исследований'.

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

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

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

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

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

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

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

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

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

3. На основе расширенного аппарата С)-схем разработана имитационная модель процедуры отказоустойчивого вещания, позволившая получить зависимости среднего времени передачи от интенсивности потоков сообщений; подтверждающие возможность снижения указанного времени широковещательной передачи в 2 и более раз. Установлено, что созданный алгоритм сокращает число потерянных сообщений в вещательных режимах обмена информацией» примерно на 20% при сохранении соотношения числа потерянных и доставленных сообщений, не превышающего 0,017.

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

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

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

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

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

На защиту выносятся следующие научные результаты:

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

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

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

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

Апробация работы. Основные результаты, положения и выводы диссертации обсуждались на Международной научно-технической конференции «Information and telecommunication technologies in intelligent systems» (Spain, Mallorca, 2005; Italy, Katania, 2006), на Всероссийской конференции по проблемам математики, информатики, физики и химии (Москва, 2005), на Международной научно-технической конференции «Распознавание-2005» (Курск, 2005), на Международной научно-технической конференции «Медико-экологические информационные технологии» (Курск, 2005; Курск, 2007), а также на научных семинарах кафедры вычислительной техники КурскГТУ в период с 2003 по 2007 год.

Публикации по теме диссертации. Содержание диссертации опубликовано в 9 работах, среди которых имеется статья в научном издании, входящем в перечень ВАК, а также решение о выдаче патента на изобретение.

Личный вклад соискателя. Все выносимые на защиту научные результаты получены соискателем лично. В опубликованных работах по теме диссертации личный вклад соискателя сводится к следующему: в [8, 23, 25, 53] разработаны различные фазы алгоритма распределенного отказоустойчивого вещания сообщений, а также принципы структурно-функциональной организации и функциональные схемы узлов устройства вещания, в [24] описана методика проведения имитационного моделирования аппаратных средств отказоустойчивой маршрутизации и вещания сообщений на основе аппарата С)-схем, в [15] предложены правила выбора направления выдачи сообщения коммуникационным устройством, в [43] разработан ряд программных модулей визуальной среды для поддержки имитационного моделирования устройств отказоустойчивого вещания, в [41] предложен вариант реализации коммуникационных блоков.

Структура и объем диссертации. Работа состоит из введения, четырех глав, заключения, приложений и списка литературы, включающего 88 наименований. Диссертация содержит 195 страниц текста (включая три приложения) и поясняется 30 рисунками и 5 таблицами.

Выводы

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

2. Разработанное устройство обеспечивает существенное снижение среднего времени передачи сообщения в коммуникационной среде матричного мультипроцессора по сравнению с лучшими известными аналогами (в особенности при более высоких интенсивностях потоков сообщений). Минимальный выигрыш по времени передачи (в 2 раза) зарегистрирован при наименьшей интенсивности потока сообщений, составляющей 1/250 (сообщение/тактов). Одновременно при использовании разработанного устройства достигается сокращение числа сообщений, потерянных при маршрутизации вследствие возникновения фатальных ситуаций в алгоритме вещания (примерно на 20%). Относительные потери сообщений при этом составляют не более 1,5%.

3. Аппаратные затраты на реализацию режима отказоустойчивого вещания в предлагаемом устройстве составляют 20000-25000 ЭВ, а суммарная аппаратная сложность устройства равна порядка 50000 ЭВ, что удовлетворяет ограничениям современной элементной базы по допустимому числу вентилей на кристалле СБИС.

Заключение

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

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

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

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

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

4. На основе имитационного моделирования получено подтверждение преимуществ разработанного алгоритма перед лучшими известными аналогами по среднему времени передачи сообщений (в 2 и более раз). Установлено, что созданный алгоритм и устройство на его основе обеспечивают снижение числа потерянных сообщений на 20% при сохранении соотношения числа потерянных и доставленных сообщений не выше 0,017.

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

1. A.c. 1508228 СССР, МКИ 4 G06F15/16. Устройство для формирования маршрута сообщения в однородной вычислительной системе / В.А.Мельников, В.С.Харченко, П.И.Кныш, С.Б.Кальченко (СССР). -№4390961/24-24; заявлено 14.01.88; опубл. 15.09.89, Бюл. №34. 8 с.

2. A.c. 1575167 СССР, МКИ 5 G06F7/00, 15/16. Модуль матричного коммутатора / В.А.Мельников, П.И.Кныш, Ю.Н.Силантьев и др. (СССР). — №4486837/24-24; заявлено 26.09.88; опубл. 30.06.90, Бюл. №24. 6 с.

3. A.c. 1793436 СССР, МКИ 5 G06F7/00, 15/16. Модуль матричного коммутатора / В.А.Мельников, А".В.Галицкий, В.В .Копылов и др. (СССР). -№4893395/24; заявлено 30.10.90; опубл. 07.02.93, Бюл. №5. 8 с.

4. Абдель-Джалил, Дж.Н. Алгоритмы межпроцессорного взаимодействия в отказоустойчивых многопроцессорных системах Текст. / Дж.Н.Абдель-Джалил, Э.И.Ватутин, И.В.Зотов, А.А.Иванов // Методы и системы обработки информации. Муром, 2004. С. 117-125.

5. Артамонов, Г.Т. Топология регулярных вычислительных сетей и сред Текст. / Г.Т.Артамонов. -М.: Радио и связь, 1985. 192 с.

6. Архитектура и синтез параллельных логических мультимикрокон-троллеров: в 2 ч. Текст. / И.В.Зотов, В.С.Титов, В.И.Штейнберг [и др.]. -Курск: КурскГТУ, 2006. 359 с.

7. Воеводин, B.B. Параллельные вычисления Текст. / В.В. Воеводин, Вл.В. Воеводин. СПб.: БХВ-Петербург, 2004. - 608 с.

8. Захаров, И.С. Информационные технологии проектирования отказоустойчивых мультиконтроллеров Текст. : учеб. пособие / И.С. Захаров, В.А. Колосков, М.В. Медведева. Курск: КурскГТУ, 2003. - 300 с.

9. Клеточная самоорганизация программируемых отказоустойчивых мультимикроконтроллеров Текст. / М.В. Медведева, A.B. Медведев, В.А. Колосков, Ф. А. Старков. Курск: КурскГТУ, 2000. - 200 с.

10. Колосков, В.А. Архитектура отказоустойчивых сетей самонастраиваемых микроконтроллеров Текст. / В.А.Колосков, В.С.Титов. Курск: КурскГТУ, 1995. - 176 с.

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

12. Колосков, В.А. Управляющая система с самоорганизующим слоем Текст. / В.А. Колосков, B.C. Титов // Автометрия. 1997. №4. С. 113-120.

13. Колоскова, Г.П. Модели и алгоритмы реконфигурации многопроцессорных систем Текст. : учеб. пособие / Г.П. Колоскова. — Курск: КурскГТУ, 2004. 257 с.

14. Корнеев, В.В. Вычислительные системы Текст. / В.В. Корнеев. — М.: «Гелиос АРВ», 2004. 512 с.

15. Кун, С. Матричные процессоры на СБИС Текст. / С.Кун; Пер. с англ. Ю.Г. Дадаева и др.; Под ред. Ю.Г. Дадаева. М.: Мир, 1991. - 672 с.

16. Наджаджра, М.Х. Алгоритм отказоустойчивой маршрутизации сообщений с «вращающейся системой координат» Текст. / М.Х.Наджаджра [и др.] // Методы и средства систем обработки информации. Сборник научных статей. Курск: КурскГТУ, 2007. Вып.4. С.40-47.

17. Наджаджра, М.Х. Организация отказоустойчивого межпроцессорного взаимодействия в матричных мультикомпьютерах Текст. /

18. М.Х.Наджаджра и др. // Известия ТулГУ. Бизнес-процессы и бизнесс-системы. 2006. Вып. 4. С. 3-9.

19. Организация и синтез микропрограммных мультимикроконтролле-ров Текст. / И.В.Зотов, В.А.Колосков, В.С.Титов [и др.]. Курск: КурскГТУ, 1999.-368 с.

20. Патент №2110827 РФ, МКИ 6 G05B19/18, G06F9/28. Дискретная микроконтроллерная сеть / И.В.Зотов, В.А.Колосков, В.С.Титов (РФ). — №97102528/09; заявлено 18.02.97; опубл. 10.05.98, Бюл. №13.-24 с.

21. Патент №2116664 РФ, МКИ 6 G06F7/00, G06F15/163. Модуль матричного коммутатора / И.В.Зотов, В.А.Колосков, В.С.Титов (РФ). — №96108431/09; заявлено 24.04.96; опубл. 27.07.98, Бюл. №21. 13 с.

22. Патент №2133054 РФ, МКИ 6 G05B19/18, G06F9/28. Распределенная система для программного управления / Л.М.Миневич, А.В.Медведев, М.В.Медведева, И.В.Зотов и др.. (РФ). -№98108934/09; заявлено 13.05.98; опубл. 10.07.99, Бюл. №19. 16 с.

23. Патент №2168204 РФ, МКИ 7 G06F15/173; Н03К17/56. Модуль матричного коммутатора / К.А.Попов, И:В.Зотов, В.С.Титов (РФ). — № 99119675/09; заявлено 13.09.99; опубл. 27.05.2001, Бюл. №15.-11 с.

24. Патент №2168755 РФ, МКИ 7 G06F13/14, 15/163. Модуль матричной коммуникационной сети / И.В.Зотов (РФ). — №2000106883/09; заявлено 20.03.2000; опубл. 10.06.2001, Бюл. №16. 41 с.

25. Патент №2222044 РФ, МКИ 7 G06F15/173. Модуль для ретрансляции сообщений в коммутационной структуре / Ю.В.Беляев, Е.Г.Анпилогов, И.В.Зотов (РФ). №2002108943/09; заявлено 8.04.2002; опубл. 20.01.2004, Бюл. №2. - 16 с.

26. Патент №2249848 РФ, МКИ 7 G06F15/163. Модуль для передачи и вещания сообщений в матричном коммутаторе / Е.Г.Анпилогов, Ю.В.Беляев, И.В.Зотов (РФ). -№2003104071/09; заявлено 11.02.2003; опубл. 10.04.2005, Бюл. №10.-23 с.

27. Патент №2249849 РФ, МКИ 7 G06F15/163. Модуль для обмена сообщениями / А.А.Иванов, Е.Г.Анпилогов, И.В.Зотов, В.В.Ефремов (РФ). -№2003129963/09; заявлено 08.10.2003; опубл. 10.04.2005, Бюл. №10. 19 с.

28. Патент №5151996 США, МКИ 5 G06F15/16. Multi-dimensional message transfer router / W.D.Hillis (США). №497003; заявлено 20.03.90; опубл. 29.09.92.-44 с.

29. Патент №7080156 США, МКИ 8 G06F15/173. Message routing in а torus interconnect / W.S.Lee, N.Talagala, F.Chong(Jr.) et al. (США); -№104923; заявлено 21.03.2002; опубл. 18.07.2006. 17 с. .

30. Решение о выдаче патента по заявке №2007114559: Микроконтроллерная сеть / С.В; Волобуев, 0:В. Крикунов; М.Х. Наджаджра и др. (РФ). — М.: РосПатент; заявлено 17.04.2007.

31. Свидетельство о регистрации программы для ЭВМ №2006610308. Библиотека классов^ для имитационного моделирования коммуникационных сетей / Э.И.Ватутин, И.В.Зотов (РФ). М.: РосПатент; заявлено 22.10:2005; дата регистрации 16.01.2006.

32. Свидетельство о регистрации программы для- ЭВМ №2007611310. Визуальная среда имитационного моделирования: VisualQChart / И;В.Зотов, М.Х.Наджаджра и др. (РФ). М.: РосПатент; заявлено 13.02.2007; дата регистрации 27.03.2007. . '

33. Советов, Б.Я. Моделирование, систем Текст.: учеб. пособие / Б.Я.Советов, С.А.Яковлев:-М>: Высшая школа; 2005. — 343тс.

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

35. Сусин, Г1.В. Коммутатор с распределенными выходными очередями: для. параллельных систем логического управления: дис.канд. техн. наук: 05.13.05: защищена 20.06.2003: утв. 14.11.2003 / Сусин Павел Викторович. -Курск, 2003. -220 с.

36. Угрюмов, Е.П. Цифровая схемотехника Текст.: учеб. пособие / Е.П.Угрюмов. СПб.: БХВ-Петербург, 2004. - 800 с.

37. Функционально-топологическая организация микропрограммных мультимикроконтроллеров группового логического управления Текст. / И.В.Зотов, В.А.Колосков, В.С.Титов, И.В.Абузова. - Тула: ТулГУ, 1997. — 226 с.

38. Al-Sadi, J. Probability-based fault-tolerant routing in hypercubes Текст. / J. Al-Sadi, K. Day, M. Ould-Khaoua // The Computer Journal. 2001. Vol.44, №5. P. 368-373.

39. Chen, C.-L. A fault-tolerant routing scheme for meshes with nonconvex faults Текст. / Chun-Lung Chen, Ge-Ming Chiu // IEEE Transactions on Parallel and Distributed Systems. 2001. Vol. 12, №5. P.467-475.

40. Chen, Y.-S. Multinode broadcasting in a wormhole-routed 2-D torus using an aggregation-then-distribution strategy Текст. / Y.-S. Chen, C.-Y. Chen // IEE Proceedings Computers and Digital Techniques. 2000. Vol.147, №6. P. 403413.

41. Duato, J. A theory of fault-tolerant routing in wormhole networks Текст. / J. Duato // Proc. Intl Conf. Parallel and Distributed Systems, ICPDS 1994, 19-21 Dec. 1994. P. 600-607.

42. Gao, F. Fault-tolerant routing algorithms based on optimal path matrices Текст. / Feng Gao, Zhongchen Li // Proc. Pacific Rim Intl Symp. Dependable Computing, 16-17Dec. 1999.-P. 227-233.

43. Gomez, M.E. An effective fault-tolerant routing methodology for direct networks Текст. / M.E. Gomez, J. Flich, P. Lopez // Proc. Intl Conf. Parallel Processing, ICPP 2004, 15-18 Aug. 2004.-2004. Vol.1. P. 222-231.

44. Gomez, M.E. A routing methodology for achieving fault tolerance in direct networks Текст. / MiE. Gomez, N.A. Nordbotten, J. Flich [et al] // IEEE Transactions on Computers. 2006. Vol.55, №4. P. 400-415.

45. Ho, C.-T. A new approach to fault-tolerant wormhole routing for mesh-connected parallel computers Текст. / C.-T. Ho, L. Stockmeyer // IEEE Transactions on Computers. 2004. Vol.53, №4. P. 427-438.

46. Hou, Y. Broadcasting on wormhole-routed 2D tori with arbitrary size Текст. / Yomin Hou, Chien-Min Wang, Ming-Jer Tsai, Lih-Hsing Hsu // Proc. Intl Conf. Parallel and Distributed Systems, 14-16 Dec. 1998. -P. 334-341.

47. Jiang, Z. A limited-global information model for dynamic-fault-tolerant routing in cube-based multicomputer Текст. / Zhen Jiang, Jie Wu // Proc. 2nd IEEE Intl Symp. Network Computing and Applications, NCA 2003, 16-18 April 2003.-P. 333-340.

48. Keshav, S. Issues and trends in router design Текст. / S.Keshav, KSharma // IEEE Communications Magazine. 1998. Vol.36, №5. Pi 144-151.

49. Kunde, M. Packet routing on grids of processors / M.Kunde //Lecture Notes in Computer Science. 1988. Vol.401. P: 129-136.

50. Lin, X. Deadlock-free multicast wormhole routing in 2-D mesh multicomputers Текст. / Xiaola Lin, P.K. McKinley,.L.M; Ni // IEEE Transactions on Parallel and Distributed Systems. 1994. Vol.5, №8. P. 793-804.

51. McKinley, P.K. Collective communication in wormhole-routed massively parallel computers Текст. / P.K. McKinley, Yih-jia Tsai, D;F. Robinson // Computer. 1995. Vol.28, №12. P: 39-50. . .

52. Programming Languages С++. International Standard. - ISO/IKC 14882, 1998.-776 p.

53. Stratix II. 90-nm high-performance & high-density FPGAs. Stratix II Brochure. Februaiy 2004. ALTERA, 2004. - 8 p. ,

54. Takanami, I. Built-in self-reconfiguring systems for fault tolerant mesh-connected processor arrays by direct spare replacement Текст. / I. Takanami // Proc. IEEE Intl Symp. Defect and Fault: Tolerance in VLSI Systems, 24-26 Get.2001.-P. 134-142.

55. Takanami, I. Built-in self-reconfiguring systems for mesh-connected processor arrays with spares on two rows/columns Текст. / I. Takanami // Proc. IEEE Intl Symp. Defect and Fault Tolerance in VLSI Systems, 25-27 Oct. 2000. -P. 213-221.

56. Tarek, E-G. A general framework for developing adaptive fault-tolerant routing algorithms Текст. / E.-G.Tarek, Y.Abdou // IEEE Transactions on Reliability. 1993; Voi.42, №2. P: 250-258.

57. Theiss, I. FRoots: A fault-tolerant and topology-flexible routing technique Текст. / I. Theiss, О. Lysne // IEEE Transactions on Parallel and Distributed Systems. 2006. Vol.17, №10. P.l 136-1150.

58. Tseng, Y.-C. Efficient broadcasting in wormhole-routed multicomputer: a network-partitioning approach Текст. / Yu-Chee Tseng, San-Yuan Wang, Chin-Wen Ho // IEEE Transactions on Parallel and Distributed Systems. 1999. Vol.10, №1. P. 44-61.

59. Tsuda, N. Fault-tolerant processor arrays using additional bypass linking allocated by graph-node coloring Текст. / N. Tsuda // IEEE Transactions on Computers. 2000. Vol.49, №5. P. 431-442.

60. Wang, G. A new fault-tolerant routing scheme for 2-dimensional mesh networks Текст. / Gaocai Wang, Jianer Chen // Proc. 4th Intl Conf. Parallel and Distributed Computing, Applications and Technologies, PDCAT'2003, 27-29 Aug. 2003.-P. 95-98.

61. Wang, G. A probabilistic approach to fault-tolerant routing algorithm on mesh networks Текст. / Gaocai Wang, Taoshen Li, J. Chen // Proc. 10th Intl Conf. Parallel and Distributed Systems, ICPADS 2004, 7-9 July 2004. P. 577-584.

62. Wittie, L.D. Communication structures for large networks of microcomputers Текст. / L.D. Wittie // IEEE Transactions on Computers. 1981. Vol.C-30, №4. P. 264-273.

63. Wu, J. Fast reconfiguring mesh-connected VLSI arrays Текст. / Wu Ji-gang, T. Srikanthan // Proc. Intl Symp. Circuits and Systems, ISCAS '04, 23-26 May 2004. 2004. Vol.2. P. 949-952.

64. Wu, J. On constructing the minimum orthogonal convex polygon for the fault-tolerant routing in 2-D faulty meshes Текст. / Jie Wu, Zhen Jiang // IEEE Transactions on Reliability. 2005. Vol.54, №3. P. 449-458.

65. Xiang, D. Fault-tolerant routing in meshes/tori using planarly constructed fault blocks Текст. / Dong Xiang, Jia-Guang Sun, J. Wu, K. Thulasira-man // Proc. Intl Conf. Parallel Processing, ICPP 2005, 14-17 June 2005. P. 577584.

66. Xiang, D. Fault-tolerant routing in 2D tori or meshes using limited-global-safety information Текст. / Dong Xiang, Ai Chen // Proc. Intl Conf. Parallel Processing, ICPP 2002, 18-21 Aug. 2002. P. 231-238.

67. Zakrevski, L. Fault-tolerant message routing for multiprocessors Текст. / L. Zakrevski, M.G. Karpovsky // Parallel and Distributed Processing. Springer. 1998.-P. 714-731.

68. Zotov, I.V. Model of fault-tolerant message routing for matrix-type microcontroller networks Текст. / I.V.Zotov // Automatic Control and Computer Sciences. 2002. Vol.36, №2. P. 15-26.

69. Zotov, I.V. Procedure-logical routing model in microcontroller networks with matrix organization Текст. / I.V.Zotov // Automatic Control and Computer Sciences. 1999. Vol.33, №3. P. 48-56.