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

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

Абдель-Джалил Джихад Надир

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

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

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

Курск - 2006

Работа выполнена в ГОУ ВПО «Курский государственный технический университет» на кафедре «Вычислительная техника»

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

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

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

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

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

Ведущая организация: Тульский государственный университет.

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

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

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

Автореферат разослан 25 августа 2006 г.

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

Е.А. Титенко

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

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

Реализация межпроцессорного взаимодействия согласно указанным условиям требует разработки соответствующих алгоритмов отказоустойчивой маршрутизации сообщений. К настоящему моменту создан целый ряд подобных алгоритмов, ориентированных на мультикомпьютеры с различной топологией и отличающихся правилами обхода отказов (Л.А.Закревский, A.B. Тимофеев, J. Al-Sadi, R.V. Boppana, G.N. Khan, J. Wu, и др.). Основным недостатком большинства этих алгоритмов является значительный дополнительный трафик, возникающий из-за необходимости обновления информации о состоянии процессоров и допустимых направлениях маршрутизации и ведущий к росту потерь сообщений (Л.А.Закревский, A.B. Тимофеев, J. Al-Sadi, J. Wu). Известен алгоритм, не требующий подобных обменов (Е.Г. Анпилогов, И.В.Зотов). Однако его недостатком являются существенные затраты локальной памяти процессоров для хранения таблиц маршрутизации и заранее заданных альтернативных маршрутов обхода. Кроме того, ему свойственно значительное время построения (программирования) сети маршрутов. Многие алгоритмы отказоустойчивой маршрутизации допускают зацикливания сообщений без возможности их отслеживания и предупреждения.

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

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

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

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

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

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

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

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

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

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

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

5. Аналитическая оценка предельной емкости памяти таблиц маршрутизации и времени программирования сети маршрутов.

Научная новизна работы:

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

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

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

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

Практическая ценность работы:

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

2. Динамическая модификация маршрутов на основе правил отклонения, компенсации и возврата в созданном устройстве обеспечивает снижение времени построения сети маршрутов как минимум в 1,2 раза.

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

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

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

Апробация работы. Основные результаты диссертационной работы докладывались: трижды на Международной НТК «Information and telecommunication technologies in intelligent systems» (Barcelona, 2004, Mallorca, 2005, Katania, 2006), на XLI Всероссийской конференции по проблемам математики, информатики, физики и химии (Москва, 2005), на VII Международной НТК «Распознавание-2005» (Курск, 2005), на VIII Международной НТК «Медико-экологические информационные технологии» (Курск, 2005), на XXXIV вузовской НТК студентов и аспирантов «Молодежь и XXI век» (Курск, 2006).

Научные положения, выносимые на защиту:

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

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

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

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

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

Личный вклад автора. В работах, опубликованных в соавторстве и приведенных в конце автореферата, лично соискателем выполнено следующее: в [1-5] разработаны правила обхода отказавших процессоров при маршрутизации; в [7] изложена методика имитационного моделирования алгоритмов отказоустойчивой маршрутизации; в [8-10] разработана процедура маршрутизации сообщений при реализации типовых информационных обменов в управляющих мультикомпью-терах; в [11] спроектированы блоки устройства маршрутизации сообщений микроконтроллерной сети; в [12,13] предложена методика снижения межпроцессорного трафика при разбиении алгоритмов.

Объем и структура работы. Диссертационная работа состоит из введения, четырех глав, заключения, списка литературы, включающего 78 источника и приложений. Работа содержит 163 страниц текста, 45 рисунков и 6 таблицы. Приложения включают 66 страниц.

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

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

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

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

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

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

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

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

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

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

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

Маршруты для всех взаимодействий в мультикомпьютере заданы, при этом каждый маршрут разбит на множество участков ограниченной длины. Длины участков ограничены константой /г*. Участки линейны по конфигурации, и могут быть ориентированы в одном из восьми «направлений», образующих «систему координат» маршрутизации (восток, северо-восток, север, северо-запад, запад, юго-запад, юг, юго-восток). Направления различных участков маршрута в указанной системе координат произвольны. Базовым направлением при этом считается восток (0), а остальные задаются целым числом («степенью поворота») от 1 для северо-востока до 7 для юго-востока. Степень поворота отсчитывается против часовой стрелки относительно базового направления.

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

слово включает три составляющие: 1) степень поворота для текущего участка; 2) длину текущего участка; 3) указатель на слово с информацией о следующем участке.

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

Дадим формализованное представление указанных правил.

Мультикомпьютер зададим графом (Л/,£), вершины Л/ которого соответствуют процессорам (модулям), а дуги £сЛ/хЛ/ отражают межмодульные связи. Множество Л/ отобразим на гипотетическую матрицу // с Л'| строками и Л'2 столбцами, /V,Л'2 =|Л/|, так, чтобы процессор т}] е Л/ , расположенный на пересечении /-й строки иу-го столбца // (' = •>У = имел связи со всеми процессорами, индексы которых отличаются от /,_/ не более чем на 1.

Пусть - множество исходящих связей процессора т,г Каждой

связи ^ ("',/) сопоставим двоичный вектор

- («' К))=(*' К Ж(в' К ))•-•*.• К К)).

где г =

; — ближайшее целое, не меньшее д; «•» — сим-

вол конкатенации, так, чтобы:

Эг е {1,2.....='}:а, (ег (|и„))е а, (ег («,„)) = 1, V/' * /".

Соответствие между кодами и связями т0 е Л/ ,

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

Введем в рассмотрение признаки состояния процессоров: = если

процессор т в момент / работоспособен; <50(() = О иначе; <5Д0) = 1 = 1,А'|,у = 1.Л'2); 8,, (',) < 5:/ (/2) => > /2 е Л/ . Выделим подмножество работоспособных процессоров Л/ (/') с М: {у^ы е Л/ (/'): Зи (?') = 1) л л[утц е Л/ \ Л/(г'): (/') = о). Выберем произвольную пару процессоров гПу,ты е Л/(/'): (А * у) и построим маршрут Я =

Я = ( "V "W "V, =

/'е^г,...,^^)!},/"^!,^...,^^)!},...,

Через |л| обозначим длину (количество трансляций) маршрута R. Ограничим множество маршрутов такими, для которых справедливо правило:

Закодируем маршрут R путем подстановки

'"И»*)) "И-О) - -КК.О)"

ег(т„) ... ег (т.^)

Получим маршрутный код, представляющий R:

& = [сг (ег (>",,))• о- (еГ ("V, ))••■•* (^(v,))} О)

Обозначим через [^"'j длину маршрутного кода R^: |/?,<т)| = z |Л|.

Разобьем маршрут Я на участки Л,,R2,...,Rj, так, чтобы |/?Л|<й* = и-выполнялось условие:

= o(e(ma.b.,mc.d.)) V(m„6,ты),{тм.,тс.,.)^ Rs,s = 1

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

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

КО);

где £аЬ - число различных маршрутов, участки которых начинаются в таЬ;

= ^/+1. 'Ci' Фс,+1 - соответственно степень поворота, дли-

на и указатель на подтаблицу с данными об (s +1) -м участке с-го маршрута.

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

I • Rot • RC • Next • Stage *r*r*r'«e* Sign • h, RC = crh •... • cr. •... • a2 • cr,

где I - информационное поле; Rot - степень поворота для текущего (s-го) участка (Rot = F'); RC - поле маршрутного кода текущего участка (RC = /?'"'); Next-

поле указателя подтаблицы с информацией о следующем участке (Next = ); Stage - поле номера фазы маршрутизации (Stage = 00 - передача без обхода отказов; Stage = 01 — отклонение; Stage = 10 — компенсация; Stage =11— возврат); г — поле номера активной трансляции (r = l,Asc); г - поле номера трансляции начала обхода; г' - поле номера трансляции возврата; а — поле кода текущей трансляции (а = сг*); Sign - поле направления (знака) обхода отказа (0 - основное направление; 1 - дополнительное, ортогональное направление); h — поле длины текущего участка маршрута (h = h')\ ar - поле г-й трансляции, причем сг, = рг »сг*: сг" -поле кода r-й трансляции; р, - метка-признак активности r-й трансляции,

г = \К-

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

1. Положить г = г.

2. Если ¿(сг*) = 1, то перейти к фазе компенсации, иначе к п.З.

3. Если (сг* >3)л (сг* < 5), то перейти к п.9, иначе к п.4.

4. Если ^(сг*) = 0, то установить сг* =(<7,+(l-Sign *2)) mod 8 и перейти к п.З, иначе выполнить п.5.

5. Выдать сообщение в направлении (сг* + F/) mod 8.

6. Положить г = г + 1 и г' = г.

7. Если г > h, то перейти к п.9, иначе выполнить п.8.

8. Если г = h и <5(сг*) = 0, то перейти к п.9, иначе к п.2.

9. Если Sign=0, то положить Sign=l и перейти к фазе возврата, иначе фатальный отказ.

Правило (фаза) компенсации.

1. Положить а = 0, г' = г.

2. Установить сг* = (о - сг'_,) mod 8, а = ст*.

3. Если <?(а') = 0, то выполнить п.4, иначе перейти к п.9.

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

5. Положить сг* = (сг* + (1 - Sign * 2)) mod 8.

6. Если (сгг* > 3) а(ст* <5), то перейти к п. 12, иначе к п.7.

7. Если <У(<7*)=1, то выдать сообщение в направлении (<т* + F/)mod8 и

перейти к п.8, иначе выполнить п.5.

8. Принять г = г +1, г' = г' +1, г = г +1, и выполнить п.2.

9. Выдать сообщение в направлении (сг' + F'^j mod 8.

10. Положить г = г-1, 5 = (o + (l-Sign*2))mod8.

11. Если г<г, то положить г = г' и конец компенсации, иначе перейти к

п.2.

12. Если Sign=0, то положить Sign=l и перейти к фазе возврата, иначе фатальный отказ.

Правило (фаза) возврата.

1. Если г = г', то перейти к п.2, иначе перейти к п.6.

2. Если г = 1, то перейти к п.8, иначе перейти к п.З.

3. Положить г = г -1.

4. Выдать сообщение в направлении (сг* + F' + 4) mod 8.

5. Положить сг* = 0 и перейти к п.2.

6. Положить г = г +1.

7. Выдать сообщение в направлении (сг* + Ff + 4) mod 8, принять

о\ = (сг* + 4) mod 8 и перейти к п. 1.

8. Конец возврата. Перейти к фазе отклонения.

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

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

Назначение основных блоков устройства следующее. БООС 1.1-1.9 предназначены для приема сообщений с входов 24.1-24.9 модуля соответственно, временного хранения и выдачи сообщений в порядке поступления на информационные входы мультиплексора 2 соответственно. Мультиплексор 2 служит для передачи сообщений из БООС 1.1-1.9 в регистры 6.1 и 7 через коммутаторы 14.1-14.10. БАОС 3 обеспечивает выбор БООС, содержащего наибольшую очередь сообщений. БАС 4 предназначен для анализа адресной части сообщений и организации работы модуля в соответствии со значениями ее полей. БММК 5 служит для формирования маршрутного кода очередного участка и модификации маршрутных кодов по правилам обхода отказов.

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

Буферный регистр 6.1 обеспечивает хранение информационного поля сообщения во время его обработки. Буферный регистр 6.2 служит для фиксации кода выбора БООС. Буферный регистр 7 введен для хранения адресной части сообщения во время его обработки. Дешифратор 8 служит для преобразования кода выбора БООС в соответствующий унитарный код. БС 9 предназначен для формирования четырех сдвинутых друг относительно друга последовательностей импульсов 11, 12, 13 и 14, синхронизирующих работу узлов модуля. Триггер 10 запуска использован для управления блоком 9 синхронизации. Коммутатор 11 кода текущей трансляции введен с целью выделения кода очередной трансляции из маршрутного кода текущего участка. Мультиплексор 12 отказа служит для коммутации сигналов состояния восьми соседних модулей. Демультиплексор 13 предназначен для передачи сообщений на один из выходов 26.1-26.8 модуля. Сумматор 16 служит для формирования кода текущей трансляции с учетом степени поворота. Триггер 18 отказа служит для индикации текущего состояния модуля.

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

Имитационное моделирование осуществлялось при следующих условиях: 1) мультикомпьютер включает 8x8 процессоров; 2) каждый процессор генерирует пуассоновский экспоненциально распределенный поток сообщений (заявок) с интенсивностью 1/20, 1/30, 1/40, 1/50 (1/такт); 3) источник и приемник сообщения, а также его маршрут (если требуется) выбираются случайно с исключением «нереальных» вариантов (например, исключаются маршруты с циклами); 4) процессоры отказывают независимо друг от друга, поток отказов пуассоновский; 5) средняя наработка процессора на отказ составляет 1000, 2000, 3000, 4000, 5000, 6000 тактов; 6) предельная длина входных буферов не ограничена. В ходе моделирования регистрировалось число успешно доставленных сообщений (с!), число сообщений, потерянных вследствие фатальной ситуации в алгоритме маршрутизации (/), а также среднее время пребывания сообщения в КС мультиком-пьютера (О). Оценивались следующие алгоритмы маршрутизации: разработанный; алгоритм Е.Г.Анпилогова и И.В.Зотова; алгоритм расширенных уровней безопасности \\'и; алгоритм распределенного блока восстановления; «жадный» алгоритм.

В результате моделирования получены зависимости коэффициента потерь сообщений = от средней наработки процессора на отказ Г при интенсивности потока сообщений Ь равной 1/20, 1/30, 1/40, 1/50 (1/такт) и среднего времени пребывания сообщения в КС от интенсивности потока сообщений £ при средней наработке процессора на отказ Т равной 1000, 2000, 3000, 4000, 5000, 6000 (тактов). На рис.2 и 3 представлены зависимости К(Т) при ¿=50 и при

7=6000 соответственно.

0,00

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

алгоритм распределенного блока восстановления алгоритм расширенны* уровней безопасности —*— алгоритм Анпилогова-Зотова

—а— разработанный алгоритм

Т, тактов

1000 2000 3000 4000 5000 6000

Рис.2. Графики зависимости коэффициента потерь сообщений от средней наработки процессора на отказ при интенсивности потока сообщений ¿=50 (1 такт моделирования соответствует 100 часам).

ОДактов

Рис.3. Графики зависимости среднего времени пребывания сообщения в КС муль-тикомпьютера от интенсивности потока сообщений при средней наработке процессора на отказ Т=6000 (1 такт моделирования соответствует 1 периоду следования синхроимпульсов устройства).

Анализ зависимостей К(Т) показывает, что разработанный алгоритм обеспечивает наименьшие потери сообщений (как минимум в 2 раза меньше, чем лучший из аналогов), причем с ростом наработки процессора на отказ потери стремительно снижаются до нуля (при 7=1000 теряется не более 5% сообщений, в лучших аналогах потери сообщений превышают 10%; при 7"=2000 потери снижаются до 1%, известные алгоритмы теряют более 5% сообщений). Зависимости

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

Разработанный алгоритм не только снижает потери сообщений и время их маршрутизации, но и позволяет уменьшить предельную емкость памяти таблиц маршрутизации процессора. Аналитически установлено, что указанная емкость (в битах) в созданном алгоритме примерно в 4 раза меньше, чем в лучшем из известных аналогов — алгоритме Е.Г.Анпилогова и И.В.Зотова. На рис.4 представлены аналитические зависимости предельной емкости памяти таблиц маршрутизации процессора от числа процессоров в строке мультикомпьютера, выведенные для максимальной длины участка маршрута А = 5 . Снижение предельной емкости памяти таблиц маршрутизации процессора способствует упрощению реализации отдельных устройств маршрутизации и коллективов подобных устройств в базисе СБИС.

¡V, бит

—разработанный алгоритм —алгоритм Анпилогова-Зотова

Рис.4.15. Графики зависимости предельной емкости блока памяти таблиц маршрутизации от числа процессоров в строке мультикомпьютера при максимальной длине участка маршрута И — 5

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

Установлено, что отношение времен программирования маршрута для алгоритма Анпилогова-Зотова (Т ) и предложенного алгоритма (7) пропорционально ЯЛ

-г-т—, где Я - число альтернативных реализации участка маршрута в алгорит-

1 + Л/2 п

ме Анпилогова-Зотова. Минимально возможное значение отношения Т'/Т для й = 5 достигается при Л = 1, п = 4 и составляет 1,21. В то же время при к = 1, Л = 1 и и = 10 Т'/Т и 2, а при Л = 5, Д = 1 и л = 20 Т'/Т « 3. Сокращение времени построения маршрутов снижает трудоемкость проектирования мультикомпьютера в части организации взаимодействия протекающих в нем процессов.

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

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

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

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

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

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

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

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

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

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

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

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

3. Abdel-Jalil, J.N. A fault-tolerant message routing procedure with rotating coordinates [Text] / J.N. Abdel-Jalil, M.H. Najajra, E.I. Vatutin, I.V. Zotov // Third International conference «Information and telecommunication technologies in intelligent systems », Spain, Mallorca, June 02-09 2005. P. 88-93.

4. Абдель-Джалиль, Дж. H. Процедура отказоустойчивой маршрутизации с динамическим изменением последней реализации [Текст] / Дж.Н. Абдель-Джалиль, М.Х. Наджаджра, И.В. Зотов // Материалы VIII-й Международная научно-техническая конференция «Медико-экологические информационные технологии 2005», 24-25 мая 2005 г./ Курск, гос. техн. ун-т. Курск, 2005. С. 141-145.

5. Абдель-Джалиль, Дж. Н. Динамический алгоритм маршрутизации с поворотом «системы координат» [Текст] / Дж.Н. Абдель-Джалиль, И.В. Зотов; Курск, гос. техн. ун-т. Курск, 2005. 37 с. Деп. в ВИНИТИ 28.09.2005, №1259.

6. Абдель-Джалиль, Дж.Н. Процедура отказоустойчивой маршрутизации сообщений с «вращающейся системой координат» [Текст] / Дж.Н. Абдель-Джалиль // Тезисы докладов XXXIV вузовской НТК студентов и аспирантов / Курск, гос. техн. ун-т. Курск, 2006. Ч. 1. С. 13-14.

7. Абдель-Джалиль, Дж.Н. Использование аппарата q-схем для моделирования алгоритмов маршрутизации [Текст] / Дж.Н. Абдель-Джалиль, М.Х. Наджаджра, И.В. Зотов // Сборник материалов 7-й Международной НТК «Распозна-вание-2005», 4-7 октября 2005 г./ Курск, гос. техн. ун-т. Курск, 2005. С. 179-181.

8. Абдель-Джалиль, Дж.Н. Аппаратная модель барьерной синхронизации для матричных вычислительных систем [Текст] / Дж.Н. Абдель-Джалиль, A.A. Иванов, М.Х. Наджаджра, И.В. Зотов II Материалы XLI-й Всероссийской конференции по проблемам математики, информатики, физики и химии, 18-22 апреля 2005г. Москва: изд-во РУДН, 2005. С. 100-101.

9. Абдель-Джалиль, Дж.Н. Организация быстрой групповой передачи управления в мультимикропрограммной системе [Текст] / Дж.Н. Абдель-Джалиль, М.Х. Наджаджра, B.C. Титов, И.В. Зотов // Материалы XLI-й Всероссийской конференции по проблемам математики, информатики, физики и химии, 18-22 апреля 2005г. Москва: изд-во РУДН, 2005. С. 128-129.

10. Абдель-Джалиль, Дж.Н. Организация межмодульной передачи управления в системах логического управления [Текст] / Дж. Н. Абдель-Джалиль, М.Х. Наджаджра, И.В. Зотов // «Молодежь и XXI век»: Тезисы докладов XXXIV вузовской научно-технической конференции студентов и аспирантов / Курск, гос. техн. ун-т. Курск, 2006. Ч. 1. С. 14-15.

11. Пат. №2280887. Российская Федерация. Микроконтроллерная сеть [Текст] / Иванов А.А, Абдель-Джалиль Дж. Н., Зотов И.В., Виноградов С.В.; Заявка 2005104065/09(005333); опубл.27.07.2006, Бюл. № 21.

12. Abdel-Jalil, J.N. Method for the separation of a class parallel algorithms with inter module traffic optimization [Text] / J.N. Abdel-Jalil, E.I. Vatutin, I.V. Zotov // Second International conference «Information and telecommunication technologies in intelligent systems », Spain, Barcelona, May 22-29 2004. P. 105-106.

13. Abdel-Jalil, J.N. Comparison of methods for getting separation Of parallel logic control algorithms [Text] / J.N. Abdel-Jalil, M.H. Najajra, E.I. Vatutin, I.V. Zotov // Fourth International conference «Information and telecommunication technologies in intelligent systems », Italy, Katania, May 27 - June 03 2006. P. 92-94.

Соискатель _Дж. H. Абдель-Джалиль

Подписано в печать 23.08.2006 г. Формат 60x84 1/16.

Печ. л. М. Тираж 100 экз. Заказ

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

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

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

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

Введение

1. ЗАДАЧИ ОБРАБОТКИ СООБЩЕНИЙ В ПАРАЛЛЕЛЬНЫХ 8 ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМАХ

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

1.1.1. Классификация архитектур вычислительных систем.

1.1.2. Организация памяти вычислительных систем.

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

1.3. Задача и алгоритмы маршрутизации сообщений.

1.4. Отказоустойчивая маршрутизация сообщений.

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

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

2.1. Постановка задачи отказоустойчивой маршрутизации.

2.2. Процедура отказоустойчивой маршрутизации с поворотом 54 «системы координат».

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

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

3. УСТРОЙСТВО ОТКАЗОУСТОЙЧИВОЙ МАРШРУТИЗАЦИИ 82 СООБЩЕНИЙ

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

3.2. Анализ функционирования устройства маршрутизации.

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

4. СРАВНИТЕЛЬНАЯ ОЦЕНКА СОЗДАННОГО АЛГОРИТМА 122 МАРШРУТИЗАЦИИ

4.1. Экспериментальная оценка потерь сообщений и времени 122 маршрутизации.

4.1.1. Экспериментальная оценка потерь сообщений и времени 122 маршрутизации.

4.1.2. Особенности языка имитационного моделирования.

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

4.1.4. Модель разработанного устройства маршрутизации.

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

4.2. Оценка аппаратной сложности устройства маршрутизации

4.3. Оценка времени построения маршрутов.

4.4. Выводы по главе. 150 Заключение. 151 Список литературы. 153 Приложения 1 Листинг программы моделирования процедур 164 маршрутизации.

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

Реализация межпроцессорного взаимодействия согласно указанным условиям требует разработки соответствующих алгоритмов отказоустойчивой маршрутизации сообщений. К настоящему моменту создан целый ряд подобных алгоритмов, ориентированных на мультикомпьютеры с различной топологией и отличающихся правилами обхода отказов (Л.А.Закревский, А.В. Тимофеев, J. Al-Sadi, R.V. Boppana, G.N. Khan, J. Wu, и др.). Основным недостатком большинства этих алгоритмов является значительный дополнительный трафик, возникающий из-за необходимости обновления информации о состоянии процессоров и допустимых направлениях маршрутизации и ведущий к росту потерь сообщений (Л.А.Закревский, А.В. Тимофеев, J. Al-Sadi, J. Wu). Известен алгоритм, не требующий подобных обменов (Е.Г. Анпилогов, И.В.Зотов). Однако его недостатком являются существенные затраты локальной памяти процессоров для хранения таблиц маршрутизации и заранее заданных альтернативных маршрутов обхода. Кроме того, ему свойственно значительное время построения (программирования) сети маршрутов. Многие алгоритмы отказоустойчивой маршрутизации допускают зацикливания сообщений без возможности их отслеживания и предупреждения.

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

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

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

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

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

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

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

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

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

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

5. Аналитическая оценка предельной емкости памяти таблиц маршрутизации и времени программирования сети маршрутов.

Научная новизна работы:

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

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

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

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

Практическая ценность работы:

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

2. Динамическая модификация маршрутов на основе правил отклонения, компенсации и возврата в созданном устройстве обеспечивает снижение времени построения сети маршрутов минимум в 1,2 раза.

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

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

Апробация работы. Основные результаты диссертационной работы докладывались: трижды на Международной НТК «Information and telecommunication technologies - in; intelligent systems» (Barcelona, 2004, Mallorca, 2005, Katania, 2006), на XLI Всероссийской конференции по проблемам математики, информатики, физики и химии (Москва, 2005), на VII Международной НТК «Распознавание-2005» (Курск, 2005), на VIII Международной НТК «Медико-экологические информационные технологии» (Курск, 2005), на XXXIV вузовской НТК студентов и аспирантов «Молодежь и XXI век» (Курск, 2006).

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

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

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

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

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

Личный вклад автора. В работах, опубликованных в соавторстве и приведенных в конце автореферата, лично соискателем выполнено следующее: в [1-5] разработаны правила обхода отказавших процессоров при маршрутизации; в [7] изложена методика имитационного моделирования алгоритмов отказоустойчивой маршрутизации; в [8-10] разработана процедура маршрутизации сообщений при реализации типовых информационных обменов в управляющих мультикомпьютерах; в [11] спроектированы блоки маршрутизации сообщений микроконтроллерной сети; в [12,13] предложена методика снижения межпроцессорного трафика при разбиении алгоритмов.

Объем и структура работы. Диссертационная работа состоит из введения, четырех глав, заключения, списка литературы, включающего 79 источника и приложений. Работа содержит 166 страниц текста, 45 рисунков и 6 таблицы. Приложения включают 66 страниц.

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

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

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

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

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

Заключение

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

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

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

2. На основе созданного алгоритма разработаны принципы функционирования и функциональные схемы устройства отказоустойчивой маршрутизации, позволяющие строить коммуникационные средства матричных мультикомпыотеров с пониженным коэффициентом потерь сообщений. Предложенное техническое решение защищено патентом РФ № 2280887, БИ№21 от 27.07.2006.

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

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

1. Flynn, М. Very high-speed computing system Text. / M.Flynn// Proc. IEEE.- 1966. N 54. - P.l 901-1909.

2. Flynn, M. Some Computer Organisations and Their Effectiveness Text. / M.Flynn// IEEE Trans. Computers. 1972. - V.21. N 9. - P.948-960.

3. Briggs, F.A. Computer Architecture and Parallel Processing Text. / F.A.Briggs, K.Hwang // IEEE . 1984. - P.32-40.

4. Johnson, E.E. Completing an MIMD Multiprocessor Taxonomy Text. / E.E.Johnson // Computer Architecture News. 1988. - V. 16. N 2. -P.44-48.

5. Орлов, С.А. Организация ЭВМ и систем СПб Текст. / С.А.Орлов, Б.Я.Цилькер // СПб: Изд-во Питер, 2004. -668 с.

6. Воеводин, В.В. Параллельная вычисления ЭВМ Текст. / В.В. Воеводин, Вл.В.Воеводин // СПб : Изд-во БХВ, 2002. -608 с.

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

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

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

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

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

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

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

14. Lee, Y.-H. Design of HM p a hierarchical multimicroprocessor for general-purpose applications Text. / Y.-H.Lee, J.Sasidhar, K.G.Schin // IEEE Transactions on Computers. - 1982. - vol. C. 31, № It. - PP. 10451053.

15. McKeown, N. Design and Implementation of a Packet Switched Routing Chip Text. /N.McKeown, P.Kupta // Proceedings of Hot Interconnects 6. Stanford. 1998.-PP. 77-84.

16. Saad, Y. Topological properties of hypercubes Text. / Y.Saad, M.U.Schults // IEEE Transactions. 1988. - vol. C. 37, № 7. - PP. 867872.

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

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

19. Corbertt, J.C. Practical algorithms for online routing on fixed and reconfigurable meshes Text. / J.C.Corbertt, M.C.Herbort, C.C.Weems // J. Paral. Distrib. Comput. 1994. - vol.20, No.3. - PP. 341-356.

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

21. Лукьянов, A.B. Адаптивное управление маршрутизацией в коммуникационных сетях с коммутацией пакетов Текст. /

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

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

24. Шеметов, В.В. Децентрализованные алгоритмы маршрутизации для коммуникационных сетей с коммутацией пакетов Текст. /

25. B.В.Шеметов // Автоматика и вычислительная техника. 1985. -№6.-С. 17-26.

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

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

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

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

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

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

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

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

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

35. Karpovsky, M.G. Fault-Tolerant Message Routing for Multiprocessors, Parallel and Distributed Processing, Springer Text. / M.G. Karpovsky, L. Zakrevski // IEEE 1998. - p.714-731.

36. Khan, G.N. Fault-tolerant Wormhole Routing using a Variation of Distributed Recovery Block Approach Text. / G.N. Khan, G. Wei // IEEE Proceeding Computers and Digital Techniques. 2000. - Vol. 147.-№6.-P. 397-402.

37. Al-Sadi, J. Probability-based Fault-tolerant Routing in Hypercubes, Text. / J.Al-Sadi, K.Day, M.Ould-Khaoua // IEEE The Computer Journal. -2001 Vol. 44, No. 5. - p.368-373.

38. Wu, J. Fault-Tolerant Adaptive and Minimal Routing in Mesh-Connected Multicomputers Using Extended Safety Levels Text. / J.Wu // IEEE Transactions on Parallel and Distributed Systems. 2000. - Vol. 11.-№2.-P. 149-159.

39. Wu J. A Limited-Global Information Model for Dynamic Fault-Tolerant Routing in Cube-Based Multicomputers Text. / Z. Jiang, J. Wu // nca, Second IEEE International Symposium on Network Computing and Applications, 2003, p. 333.

40. Zotov, I.V. Model of fault-tolerant message routing for matrix-type microcontroller networks, Automatic Control and Computer Sciences Text. / I.V.Zotov // IEEE 2002. - Vol.36, No.2. - p. 15-26.

41. Zotov, I.V. Model of fault-tolerant message routing for matrix-type microcontroller networks Text./ I.V. Zotov// Automatic Control and Computer Sciences, 2002, Vol.36, No.2. p. 15-26.

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

43. Олифер, Н. Маршрутизация в составных сетях Текст. / Н.Олифер // Журнал сетевых решений. 2001. - №5.

44. Кун, С. Матричные процессоры на СБИС Текст. / Кун, С.// Москва, Пер. с англ. Мир, 1991г., 672 с.

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

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

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

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

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

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

51. Abdel-Barr М. Fundamentals of Computer Organization and Architecture Text. / M. Abdel-Barr, H. El-Rewini// Publisher: Wiley-Interscience, 2005, 288 p., ISBN:0-471-46741-3.

52. Abd-El-Barr M. Advanced Computer Architecture and Parallel Processing Text. / M. Abd-El-Barr, H. El-Rewini // Publisher: Wiley-Interscience, 2005 , p. 288, ISBN: 0471467405 .

53. Duato J. Interconnection Networks : An Engineering Approach Text. / Jose Duato, Lionel M. Ni, Sudhakar Yalamanchili // Publisher: IEEE, 1997, p. 515, ISBN: 0818678003.

54. Абдель-Джалиль, Дж. H. Процедура отказоустойчивой маршрутизации с динамическим изменением последней реализации Текст. / Дж.Н. Абдель-Джалиль, М.Х. Наджаджра, И.В. Зотов //

55. Материалы VIII-й Международная научно-техническая конференция «Медико-Экологические Информационные Технологии 2005». Курск: Изд-во КГТУ, 2005. - С. 141-145.

56. Абдель-Джалиль, Дж. Н. Динамический алгоритм маршрутизации с поворотом «системы координат» Текст. / Дж.Н. Абдель-Джалиль, И.В. Зотов // Курск: Изд-во КГТУ, 2005. 37с. Деп. в ВИНИТИ 28/09/2005, №1259.

57. Пат. № 2280887 РФ, МКИ G05B 19/18, G06 F 9/28. Микроконтроллерная сеть Текст./ А.А Иванов, Дж. Н. Абдель

58. Джалиль, И.В. Зотов, Виноградов С.В. -№2005104065/09; заявлено 15.02.2005; опубл. 27.07.2006, Бюл. №21.

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

60. Абдель-Джалиль, Дж. Коммутационный процессор с параллельно-конвейерной обработкой сообщений Текст. / Абдель-Джалиль Дж., Крикунов О.В., Зотов И.В., Наджаджра М. // Телекоммуникации. -2006.-№10.

61. Колосков, В.А. Поиск абонента в мультиконтроллере с репродуцированной программой поведения Текст. / В.А.Колосков, А.В.Малышев, М.В.Медведева // Телекоммуникации. 2002. - №5.

62. Малышев, А.В. Адаптационный алгоритм самоорганизации обменных взаимодействий в мультимикроконтроллерной сетиТекст. / А.В.Малышев // Тез. докл. Международной научной конференции «XXVIII Гагаринские чтения». Москва. 2002.

63. Малышев, А.В. Клеточные алгоритмы и среды отказоустойчивой маршрутизации самоорганизующегося мультиконтроллера / Дисс.на соискание ученой степени кандидата технических наук. Курск: Изд-во КГТУ, 2003. - 148с.

64. Советов, Б.Я. Моделирование систем Текст. / Советов Б.Я., Яковлев С.А. // М.: Высшая школа, 2001. 273 с.

65. Гради, Буч Объектно-ориентированный анализ и проектирование с примерами приложений на С++ Текст. / Гради, Буч // М.: издательство: Бином, 2001. 560 с.

66. Свидетельство об официальной регистрации программы для ЭВМ №2006610308 Текст. / Ватутин Э.И., Зотов И.В. Библиотекаклассов для имитационного моделирования коммуникационных сетей ; заявл. 22.10.2005; per. 16.01.2006.

67. Programming Languages С++. International Standard. - ISO/IEC 14882, 1998. 776 P.

68. Степанян, C.O. Коммуникационные сети в многопроцессорных ЭВМ Текст. / С.О. Степанян// А и ВТ, 1987, №3, С. 31-41.