Geum.ru
   Авторефераты по темам  >>  Разные специальности - [часть 1]  [часть 2]

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

Автореферат кандидатской диссертации

 

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

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

АЛГОРИТМ И УСТРОЙСТВО РАСПРЕДЕЛЕННОГО

ОТКАЗОУСТОЙЧИВОГО ВЕЩАНИЯ СООБЩЕНИЙ

С ГРУППОВОЙ ИНДЕКСАЦИЕЙ ПРИЕМНИКОВ

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

и систем управления

АВТОРЕФЕРАТ

диссертации на соискание ученой степени

кандидата технических наук

Курск - 2008


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

 


Научный руководитель:

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

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

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

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

Ведущая организация:

Белгородский государственный технологический университет

имени В.Г. Шухова

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

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

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

 

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

Ученый секретарь совета Д 212.105.02 ______________ Е.А. Титенко


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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Мультипроцессор опишем графом , вершины M которого соответствуют физическим модулям, а дуги аотражают межмодульные связи. Пусть множество M отображено на гипотетическую матрицу с N1 строками и N2 столбцами, , так, что модуль , расположенный на пересечении i-й строки и j-го столбца аимеет связи со всеми модулями, индексы которых отличаются от ане более чем на 1. Модули аасчитаем резервными.

Для индикации текущего состояния модуля введем в рассмотрение признаки статуса: , если модуль ав момент t работоспособен; аиначе. Выделим подмножество работоспособных модулей аи выберем произвольную пару модулей а. Пусть аЦ источник сообщения, а аЦ ближайший к нему начальный модуль области вещания. Допустим, передача сообщений от ак авыполняется по маршруту , причем . Обозначим через адлину маршрута R (выраженную количеством трансляций). Будем рассматривать только простые маршруты, т.е.: .

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

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

.

Соответствие между кодами аи связями , , назовем разметкой. Потребуем, чтобы разметка отвечала порядку следования направлений маршрутизации: 0,1,Е7.

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

Разобьем маршрут R на участки , таким образом, чтобы выполнялось ааи было истинным условие:

Часть маршрутного кода , соответствующую участку аобозначим как аи назовем маршрутным кодом s-го участка.

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

;

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

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

,

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

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

,

где  Ц четырехразрядное поле r-й трансляции обхода: ;  Ц трехразрядное поле кода r-й трансляции обхода;  Ц метка-признак активности r-й трансляции обхода (); h - предельная длина маршрута обхода отказов.

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

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

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

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

  • Принять .
  • Если модуль аработоспособен, то перейти к фазе компенсации, считая .
  • Если , то перейти к п.5, иначе фатальный отказ.
  • Если Sign=0, принять Sign=1, , перейти к возврату, иначе фатальный отказ.

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

  • Установить .
  • Если , то перейти к п.4.
  • Принять .
  • Если модуль аотказал, то перейти к п.5.
  • Если , то принять аи перейти к п.11.
  • Если , то принять .
  • Если , то принять .
  • Установить .
  • Выдать сообщение модулю . Конец обработки сообщения.

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

  • Если , то перейти к п.3.
  • Если , то перейти к п.5, иначе выполнить п.4.
  • Если , то конец обхода отказов.
  • Если Sign=0, принять Sign=1, , перейти к возврату, иначе фатальный отказ.
  • Установить .
  • Если , то перейти к п.11.
  • Принять .
  • Если модуль аотказал, то перейти к п.10.
  • Принять .
  • Установить аи перейти к п.6.
  • Если , то принять аи перейти к фазе отклонения.
  • Принять аи .
  • Если , то принять аи перейти к п.15.
  • Если , то принять .
  • Если , то принять .
  • Установить .
  • Выдать сообщение модулю . Конец обработки сообщения.

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

  • Если , то принять аи перейти к фазе отклонения.
  • Принять .
  • Принять .
  • Если , то принять аи перейти к п.6.
  • Если , то принять .
  • Установить .
  • Выдать сообщение модулю . Конец обработки сообщения.

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

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

Рис. 2. Укрупнённая структурная организация

устройства отказоустойчивого вещания:

BUFxy - FIFO-буферы; SW - коммутатор; f(LA,Rot) - схема вычисления логического адреса следующего приемника; DISP0-DISP7 - блоки диспетчеризации сообщений; BA - шинный арбитр; RGLA - регистр логического адреса модуля; CTL1, CTL2 - блоки управления; CLK - блок синхронизации

Устройство имеет входы IN0, IN1, Е, IN7 и выходы OUT0, OUT1, Е, OUT7, предназначенные для организации непосредственных связей с другими аналогичными устройствами (модулями) и используемые для передачи сообщений на первом этапе вещания. Отдельные вход INP и выход OUTP служат для подключения разработанного устройства к процессорному модулю. Совокупность шин BUS(i,j) используется для вещательной передачи сообщений на втором этапе вещания. Каждая шина BUS(i,j) объединяет четыре физических модуля матричной структуры , , , , которые могут иметь логический адрес .

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

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

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

На рисунке 3 представлены зависимости ряда величин (среднего времени передачи сообщения T - рис.3,а, числа потерянных сообщений l - рис.3,б и отношения числа потерянных к числу доставленных сообщений l/d - рис.3,в) от средней интенсивности потока сообщений модуля l, полученные в ходе имитационного моделирования с учетом введенных ограничений. Темными столбиками на рисунке 3 показаны значения величин, соответствующие динамическому алгоритму попарного обмена, светлыми столбиками отображены значения для разработанного алгоритма вещания.

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

T, тактоваа (а)

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

l, сообщенийаа (б)

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

l/dаа (в)

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

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

доверительный интервал соответствует вероятности P=0.98

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

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

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

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

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

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

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

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

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

Статьи

  • Наджаджра, М.Х. Алгоритм отказоустойчивой маршрутизации сообщений с вращающейся системой координат [Текст] / М.Х.Наджаджра [и др.] // Методы и средства систем обработки информации. Сборник научных статей. Курск: КурскГТУ, 2007. Вып.4. С.40-47.
  • Наджаджра, М.Х. Организация распределенного отказоустойчивого вещания сообщений в матричных мультипроцессорах с использованием групповой идентификации приемников [Текст] / М.Х.Наджаджра; Курск, гос. техн. ун-т. ЦКурск, 2007. 32 с. - Деп. в ВИНИТИ 4.12.07, №1125-В2007.

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

  • Najajra, M.H. A fault-tolerant message routing procedure with rotating coordinates [Текст] / M.H. Najajra [et al.] // Proc. 3rd Int. Conf. Information and Telecommunication Technologies in Intelligent Systems, Spain, Mallorca, June 02-09 2005. - Mallorca, 2005. - P. 88-93.
  • Наджаджра, М.Х. Использование аппарата Q-схем для моделирования алгоритмов маршрутизации [Текст] / М.Х.Наджаджра [и др.] // Оптико-электронные приборы и устройства в системах распознавания образов, обработки изображений и символьной информации: материалы 7-й Международной научно-технической конференции, Курск, 4-7 октября 2005 г. - Курск: КурскГТУ, 2005. - C. 179-181.
  • Абдель-Джалил, Дж.Н. Процедура отказоустойчивой маршрутизации с динамическим изменением последней реализации [Текст] / Дж. Н. Абдель-Джалил, М.Х. Наджаджра // Медико-экологические информационные технологии: материалы докладов VIII Международной научно-технической конференции, Курск, 2005 г. - Курск: КурскГТУ, 2005. - С. 141-144.
  • Зотов, И.В. Универсальная коммуникационная процедура для параллельных вычислительных систем [Текст] / И.В.Зотов, М.Х.Наджаджра [и др.] // Медико-экологические информационные технологии: материалы докладов Юбилейной Международной научно-технической конференции, Курск, 24-25 апреля 2007 г. - Курск: КурскГТУ, 2007. - С.163-167.

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

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

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

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

Подписано в печать __.04.2008 г. Формат 60?84 1/16.

Печ. л. 1,0. Тираж 100 экз. Заказ _________.

Курский государственный технический университет.

Издательско-полиграфический центр

Курского государственного технического университета.

305040, г. Курск, ул. 50 лет Октября, 94.

     Авторефераты по темам  >>  Разные специальности - [часть 1]  [часть 2]