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

12

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

Сусин Виктор Викторович

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

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

1 ' ден 2009

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

Курск-2009

003489212

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

Научный руководитель: доктор технических наук, профессор,

Заслуженный деятель науки РФ Титов Виталий Семёнович

Официальные оппоненты: доктор технических наук, профессор,

Заслуженный деятель науки РФ Сизов Александр Семёнович

кандидат технических наук, доцент Жмакин Анатолий Петрович

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

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

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

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

Автореферат разослан 27 ноября 2009 г.

Ученый секретарь совета Д 212.105.02

Е.А. Титенко

общая характеристика работы

Актуальность темы. Уровень развития современной технологии СБИС обеспечивает возможность реализации многопроцессорных систем на одном кристалле. Причем интегральное воплощение возможно не только для SMP-систем, содержащих несколько процессорных ядер, но и для NUMA-мультипроцессоров, объединяющих десятки модулей (Raytheon MONARCH, Tilera TILE64, TlLEPro64, TILE-Gx). NUMA-системы такого рода, называемые однокристальными мультипроцессорами (ОМП), уже сегодня способны масштабироваться до 100-процессорных конфигураций (TILE-Gx).

Межмодульное взаимодействие в современных ОМП осуществляется через коммуникационную среду (КС) с непосредственными связями. В коммерческих мультипроцессорах, как правило, применяются КС с матричной или тороидальной топологической структурой, отличающиеся простотой СБИС-реализации и обеспечивающие множество альтернативных маршрутов передачи информации (Tilera TILE64, TILEPro64, TILE-Gx). Такие КС используют параллельные каналы связи (разрядностью данных 64 бита и выше), что позволяет выполнять межмодульный информационный обмен словами (пакетами) (Y. Chen, J. Liu, P.P. Pande).

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

Повышение отказоустойчивости мультипроцессоров и их коммутационной среды традиционно обеспечивается применением различных алгоритмов обхода отказов (дефектов) при маршрутизации пакетов. Они отличаются правилами обхода отказов, уровнем реализации (программный, аппаратный, смешанный), сложностью и комбинаторными возможностями (R.V. Boppana, S. Chalasani, C.-L. Chen, G.-M. Chiu, J. Duato, J. Wu и др.). Однако указанные алгоритмы предполагают достаточно грубый контроль состояния процессорных модулей (из-за чрезвычайно высокой сложности организации полного контроля) и не чувствительны к ошибкам в работе отдельных блоков управления маршрутизацией. Как результат, вполне возможно, что признанный работоспособным модуль будет выдавать пакеты в неверных направлениях. Исходя из этого, существует объективная необходимость совершенствования средств управления маршрутизацией пакетов ОМП в части организации контроля блоков управления маршрутизацией и автоматической коррекции (восстановления) искаженных маршрутов передачи пакетов.

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

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

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

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

Диссертационная работа выполнена в рамках плана НИР Курского государственного технического университета по единому заказ-наряду Министерства образования и науки РФ в 2006-2009 годах.

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

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

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

2. Создание метода управления маршрутизацией пакетов в коммутационной среде матричных ОМП с автоматической коррекцией искаженных маршрутов при дефектах, отказах и сбоях в отдельных коммутационных блоках на основе разработанных правил преобразования.

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

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

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

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

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

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

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

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

1. Созданный метод управления маршрутизацией пакетов в коммутационной среде матричных ОМП позволяет снизить вероятность нарушения средних и длинных маршрутов (длины 3 и более) не менее чем в 1.4 раза, что обусловливает повышение надёжности КС мультипроцессора.

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

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

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

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

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

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

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

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

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

Апробация работы. Основные положения, результаты и выводы диссертации обсуждались и получили положительную оценку на VIII Международной научно-технической конференции «Оптико-электронные приборы и устройства в системах распознавания образов, обработки изображений и символьной информации» (г. Курск, 2008 г.), на VIII Международной научно-практической конференции «Микропроцессорные, аналоговые и цифровые системы: проектирование и схемотехника, теория и вопросы применения» (г. Новочеркасск, 2008 г.), на VI Всероссийской конференции «Проблемы развития технологических систем государственной охраны, специальной связи и информации» (г. Орёл, 2009 г.), на региональной научно-методической конференции «Современные проблемы высшего профессионального образования» (г. Курск, 2009 г.), а также на научных семинарах кафедры вычислительной техники КурскГТУ в период с 2006 по 2009 год.

Публикации по теме диссертации. Содержание диссертации опубликовано в 9 работах, среди которых имеется 3 статьи в научных изданиях по перечню ВАК Минобрнауки РФ, а также 1 свидетельство о Государственной регистрации программы для ЭВМ.

Личный вклад соискателя. Все выносимые на защиту научные результаты получены соискателем лично. В опубликованных в соавторстве работах по теме диссертации личный вклад соискателя сводится к следующему: в [1, 4, 6] разработана методика оценки характеристик коммутатора с отказоустойчивой маршрутизацией сообщений (пакетов), в [2] предложен вариант формализованного описания коммутирующего элемента, в [3] изложен подход к управлению маршрутизацией пакетов на уровне коммутационного узла, в [8] описана методика построения проектов имитационного моделирования аппаратных средств, в [9] разработан ряд классов, шаблонов и функций для моделирования коммутационных элементов ОМП.

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

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

содержание работы

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

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

Типичным представителем матричных ОМП является мультипроцессор TILE64 фирмы Tilera. Он содержит 64 процессорных модуля (ПМ), объединенных матричной коммутационной средой iMesh с конфигурацией 8x8. Каждый ПМ представляет собой полнофункциональный процессор, включающий процессорный элемент, кэш-память первого и второго уровней и неблокирующий переключатель (коммуникационный элемент) для подключения к iMesh, и способен независимо функционировать под управлением отдельной операционной системы (ОС) или работать в конфигурации с другими модулями под управлением мультипроцессорной ОС наподобие SMP Linux. Кристалл имеет широкий набор интерфейсов с периферией и встроенных контроллеров. В частности, на нём имеется 4 контроллера синхронной динамической памяти DDR2, интерфейсы PCI Express (PCIE), Gigabit Ethernet (GbE), 10 Gigabit Ethernet (XAUI), TWI, SPI, Flexible I/O. Информационный обмен внутри кристалла осуществляется пакетами в параллельном коде, поэтому на нём имеются преобразователи последовательного кода в параллельный и, наоборот, параллельного в последовательный (SerDes). Работает ОМП TILE64 на тактовых частотах в диапазоне от 500 до 866 МГц и потребляет не более 22 Вт (при полной загрузке всех 64 модулей на частоте 700 МГц). Работает ОМП на тактовых частотах в диапазоне от 500 до 866 МГц и потребляет не более 22 Вт (при полной загрузке всех 64 ядер на частоте 700 МГц). Степень интеграции ОМП, подобных TILE64, приближается к 1 млрд. транзисторов.

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

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

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

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

Процесс передачи пакета по произвольному маршруту в КС ОМП представляется в виде последовательности шагов. На каждом шаге пакет обрабатывается текущим модулем и выдаётся следующему модулю маршрута в соответствии с реализуемым алгоритмом выбора маршрутов. Например, согласно алгоритму ХУ-маршрутизации первые несколько шагов передачи пакета выполняются вдоль текущей строки КС, а по достижении требуемого столбца трансляция пакета осуществляется вдоль этого столбца до заданного приёмника.

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

• каждый модуль вычисляет код направления передачи пакета не только для данного (/-го) шага маршрута, но и для двух следующих шагов ((/+1)-го и (/+2)-го), причём коды направлений (г'+1)-го и (/+2)-го шага записываются в адресную часть пакета и выдаются вместе с ним;

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

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

Пусть / - номер текущего шага маршрута, а т, - коммутационный модуль,

являющийся источником для ;-го шага. Обозначим через с/ - код направления выдачи пакета из модуля тп вычисленный модулем тп у е {/ — 2, г — I, г'}, а через с, - код фактического направления выдачи пакета из модуля т,:

9

О)

где # - символ мажоритарной операции, причём с,1 - с" = с\ и с" =

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

С"2.С"'.С+1Л)А.8А,

где 1)А и БА - поля адресов приёмника и источника соответственно (поле вА может отсутствовать); СГ2 и С"1 - поля направлений выдачи пакета на 1-м шаге, вычисленных модулями ш(_2 и т,А соответственно; С+1 - поле направления выдачи пакета на (/ +1) -м шаге, заданного модулем т1А. Поля С"2 и С"1 содержат коды с'~2 и с,м соответственно, используемые для получения кода с, по формуле (1). Поле С+1 хранит код , который будет использован на (1 +1) -м шаге для вычисления согласно (1) кода см.

При движении пакета по заданному маршруту содержимое полей С~2.С~'.С+1 модифицируется к началу каждого (/-й, / > 2) шага по следующему правилу:

ГсГ2*-С+|;

С1 С+1

<-с,

м>

I

Для шага I = 1 правило (2) вырождается и принимает вид

-1-2 , 1

(2)

(2а)

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

. ,

ш

тм '";+:

о^-—а

т..

"1+2

с< = #(с>~\сГ,с>)

Рис.1. Порядок изменения адресной части пакета согласно правилам (2), (2а)

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

начало^

c;-2<-BR[C-2] ^'-'«-BRjC-'] i//(BR[DA],CA)

^(cU'-'.c;-2) ^(BR[DA],CA) i//(BR[DA],CA)

г— 9- '- г— 10- '-1 г- 11 -3

BR[C2]<-BR[C+']

BR[C-']<-4

BR [С]«-^

с

конец

Рис.2. Граф-схема разработанного алгоритма управления маршрутизацией пакетов

В граф-схеме жирным шрифтом выделены поля пакета. Кроме того, в ней приняты следующие обозначения: «<—» - символ операции присваивания; BR -буферный регистр, в котором фиксируются все поля пакета на время его обработки; DA - поле адреса приёмника пакета в матрице ОМП; BR[x] - текущее содер-

и

жимое поля х в регистре BR; СА - адрес данного модуля ОМП; А(х) - операция выделения адресной части пакета; S - множество пакетов, поступивших в текущий модуль; [с,] - значение в выходном канале с, текущего модуля.

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

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

Таблица 1

№ Соотношение адресов X.Y и X1.Y1 Направление выдачи пакета (i//s)

^ = 2(4)

1 X>Xl + (s-l),Y>Yl + (s-l) / / /

2 X > XI + (s -1), Y < Y1 - (î -1) \ \ \

3 X < XI - (s -1), Y > Y1 + (î -1) \ \ \

4 X < XI - (s -1), Y < Y1 - (î -1) s / /

5 X>Xl + (s-l),Y = Yl ->

6 X > XI + (s -1), Y = Y1 +1 / ->

7 X > X1 + (J -1), Y = Y1 -1 \ -> ->

8 X>Xl + (i-l), Y = Yl + 2 / ->

9 X>Xl + (i-l), Y = Yl-2 \ \

10 X<Xl-(s-l),Y = Yl •f- <- <-

11 X<Xl-(s-l), Y = Yl-1

12 X<Xl-(s-l), Y = Y1 + 1 \ <- <-

13 X < XI - (s -1), Y = Y1 - 2 ^ <-

14 X<Xl-(s-l),Y = Yl + 2 \ \

15 X = X1, Y>Yl + (s-l) t t t

16 X = X1, Y< Yl-(i-l) 1

17 X=X1, Y = Y1 - - -

Во втором столбце данной таблицы записаны возможные соотношения адресов приёмника пакета Х.У и текущего транзитного модуля XI. VI (X, XI - номера столбцов КС ОМП, У, У1 - номера строк). В трёх правых столбцах таблицы

представлены соответствующие направления выдачи пакета для текущего шаг передачи = 1, значение с)) и двух следующих шагов (я = 2, значение с'ы; 5 = 3 значение с('+2). Аналогичные расширения можно построить и для других алгорит мов выбора маршрутов. Отметим, что условием корректного применения табл. является соблюдение порядка вычисления значений с], с'м, с'м, определённо алгоритмом рис. 2.

Особенностью разработанного метода управления маршрутизацией являете возможность коррекции маршрутов как при ошибках в коммутационных блока так и при аномалиях в каналах связи (при отказах и дефектах, а также при сбоях При переходе к СБИС-реализации требуется незначительная аппаратной избы точности, которая сводится к добавлению мажоритарных элементов для восст новления маршрутного кода из трех кодов направлений выдачи по формуле (1), также схем для вычисления кода направления текущего шага с! и кодов двух сл дующих шагов с'+1 и с'+2. Также необходимо небольшое увеличение разрядност пакетов за счёт включения в их адресную часть полей С~2.С"'.С+1 (разрядност каждого из них равна ["г"|, где г - число каналов связи у каждого модуля ком мутационной среды).

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

Структурная схема устройства приведена на рис.3.

оито

оип

мх2 —>- ош2

Рис.3. Структурная схема разработанного устройства управления маршрутизацией пакетов

В основу устройства положена архитектура параллельно-последовательного коммутатора (Беляев Ю.В., Зотов И.В.), который способен одновременно обрабатывать несколько пакетов. Основными блоками устройства являются следующие: входные буферы пакетов (CBUFO-CBUFn); матрица регистров (RM); анализатор размещения пакетов (CAA); генератор адреса текущего модуля ОМП (СА); блоки маршрутизации (CRO-CRn); выходные мультиплексоры (МХО-МХп); блоки модификации адресной части (АМО-АМп); мажоритарные модули (MUO-MUn); блок синхронизации (CPG).

Процесс функционирования разработанного устройства в качестве модуля коммутационной среды может быть представлен следующим образом. Пакеты, движущиеся в коммутационной среде ОМП, поступают на входы INO-INn текущего модуля (вход IN0 связывает устройство с вычислительным ядром, а входы INI-INn подключаются к соответствующим выходам аналогичных соседних устройств матрицы ОМП). Поступившие пакеты записываются в буферы CBUFO-CBUFn, откуда считываются группами в порядке, определяемом дисциплиной В процессе считывания пакетов происходит аппаратное выделение их полей С"2-С"1, что необходимо согласно операторам 3, 4 алгоритма управления маршрутизацией (см. рис.2). Одновременно в блоках CRO-CRn сразу для нескольких пакетов формируются значения c¡ в соответствии с оператором 5 алгоритма

В следующем такте блоки CRO-CRn вырабатывают пары значений с('+1,с('+2 в соответствии с операторами 7, 8 алгоритма, а мажоритарные модули MUO-MUn параллельно формируют коды c¡ согласно оператору 6 алгоритма (см. также формулу (1)). Далее блоки АМО-АМп осуществляют модификацию полей адресной части группы обрабатываемых пакетов согласно операторам 9-11 алгоритма (правило (2)). По завершении модификаций пакеты записываются в матрицу регистров RM (выбор строк при этом осуществляется по полученным кодам направлений сД Блок CAA анализирует вариант размещения пакетов в RM и инициирует процесс их выдачи на выходы OUTO-OUTn c одновременным сдвигом очередей в буферах CBUFO-CBUFn (выход OUTO связан с вычислительным ядром модуля, а остальные выходы подключают текущее устройство к соответствующим соседям в матрице ОМП).

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

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

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

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

Первоначально оценку проведём аналитически, учитывая известные форм лы для расчёта надёжности мажоритарных элементов.

Вероятность искажения маршрута, включающего И шагов (/¡>1), при отсу

ствии средств коррекции маршрутов в фиксированный момент времени I состави

& = (

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

где х{а) -функция, такая, что х{а) = а при а>0 и х(а) = 0 при а<0. Формул (4) соответствует случаю абсолютно надёжного мажоритарного элемента, реал зующего выражение (1). Предполагая, что вероятность безотказной работы это элемента может отличаться от единицы, формулу (4) можно переписать в сл дующем виде:

где р0 - вероятность безотказной работы мажоритарного элемента.

Вычитая (5) из (3), после элементарных преобразований получим абсолютн снижение вероятности искажения маршрутов

де=а-а=рг[{зрг-2рг)Ы -2Л3)У(М V- (

Весьма показательным является также относительное снижение вероятное

искажения маршрутов 5£?, которое несложно получить, поделив (3) на (5):

___ (

На рис.4,а и б представлены зависимости величин Д<2 и 62 от длины ма шрута А > 3, полученные по формулам (6) и (7) для нескольких значений вероя ностир при р0= 0,99 (отметим, что при к<3 Л(2 = 0,¿>2 = 1). Эти зависимое показывают, что разработанный метод управления маршрутизацией даёт бол весомый результат с точки зрения снижения вероятности искажения маршрута увеличением длины И (начиная с А = 3) и вероятности р. Учитывая тенденцию росту сложности ОМП и, как следствие, увеличение средней длины маршрут между взаимодействующими модулями, с одной стороны, и постоянное повыш ние надёжности элементов и устройств вычислительной техники, с другой стор ны, такой результат представляется весьма продуктивным для мультипроцессор будущих поколений.

« (б)

Рис.4. Зависимости абсолютного (а) и относительного (б) снижения вероятности искажения маршрута от его длины h при использовании разработанного метода управления маршрутизацией пакетов (для ра = 0.99)

Для подтверждения достоверности полученных теоретических выводов было проведено имитационное моделирование процесса функционирования разработанного устройства в качестве модуля коммутационной среды ОМП. Имитационная модель (/'-го модуля КС ОМП показана на рис. 5 (для графического представления модели использовался расширенный язык Q-схем; моделирование осуществлялось в графической среде Visual Q-Chart Simulator, разработанной на кафедре вычислительной техники КурскГТУ под руководством проф. И.В. Зотова).

Назначение основных элементов и особенности модели заключаются в следующем. Генератор CellGen_i_j отображает поступление пакетов от (/-го процессорного модуля в моделируемое устройство. Генератор FaultGen_iJ имитирует поток ошибок коммутационных блоков устройства (отказов, дефектов или сбоев). При возникновении ошибки очередь FaultQueJJ становится занятой, что учитывается новым элементом - массовым контроллером RoutCtrl iмоделирующим разработанный алгоритм управления маршрутизацией (листинг функции управления, ассоциированной в этим контроллером, имеется в приложении 1 к диссертации). Если возникшая ошибка - отказ (дефект), то состояние очереди FaultQueJ_j в дальнейшем не изменяется (т.е. ошибка будет проявляться всегда). Если же речь идёт о сбое, то в случайный момент времени контроллер RoutCtrl iJ открывает клапан FaultGat_i_j, что позволяет заявке покинуть очередь FaultQue_i_j (таким образом моделируется самоустранение ошибки). Пакет считается переданным заданному приёмнику после его обработки в канале FinalDev_iJ (такие пакеты включаются в число доставленных). При невозможности доставки пакета (маршрут пакета искажён и его невозможно скорректировать) осуществляется его передача через клапан Gat_i j_9 в очередь FatalQue_i_j. Суммарное число

заявок, накопленных в очередях Ра1а1рие_^' всех модулей мультипроцессора, дет количество потерянных пакетов.

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

Отметим, что результаты имитационного моделирования разработанно устройства полностью согласуются с теоретическими зависимостями и выводам Как показывают проведенные исследования, избыточность разработанно устройства не зависит от размеров матрицы ОМП и слабо зависит от п, что весь полезно с точки зрения масштабируемости ОМП по числу модулей. Наибольш влияние на аппаратную сложность и избыточность устройства оказывает пр дельная длина очередей в буферах СВиРг (К). Однако, для большинства практ чески важных случаев (8 < К < 18) аппаратная сложность устройства лежит в ди пазоне от 100 тыс. до 20 млн. эквивалентных вентилей, что вписывается в во можности современной элементной базы ОМП. При этом его избыточность превышает 14%.

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

основные результаты и выводы работы

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

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

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

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

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

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

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

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

1

список публикаций по теме диссертации

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

1. Сусин, В.В. Статистическая оценка характеристик коммутации сообщ ний при использовании мультиплексора с выходными очередями / В.В. Сусш Д.Б. Борзов, B.C. Титов, A.A. Царёв // Интеллектуальные информационные си темы. 2009. №1. С. 85-88.

2. Сусин, В.В. Аналитическая модель мультиплексора с выходными оч редями / В.В. Сусин, П.В. Сусин // Информационно-измерительные и управлж щие системы. 2009. №4. С. 90-92.

3. Титов, B.C. Проблема динамической коммутации с распределенны выходными очередями / B.C. Титов, В.В. Сусин, П.В. Сусин // Изв. ТулГУ. Се вычислительная техника, информационные технологии, системы управлени 2006. вып. 1. С. 71-76.

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

4. Сусин, В.В. Статическая модель мультиплексора с выходными очеред ми / В.В. Сусин, П.В. Сусин // Оптико-электронные приборы и устройства в си темах распознавания образов, обработки изображений и символьной информаци материалы 8-й Международной научно-технической конференции, Курск, 13-1 мая 2008 г.: В 2 ч. Курск: КурскГТУ, 2008.4.1. С. 111-112.

5. Сусин, В.В. О проблеме избыточности матрицы хранения в коммутат pax с выходными очередями / В.В. Сусин // Оптико-электронные приборы и у ройства в системах распознавания образов, обработки изображений и символьн информации: материалы 8-й Международной научно-технической конференци Курск, 13-15 мая 2008 г.: В 2 ч. Курск: КурскГТУ, 2008.4.1. С. 112-113.

6. Борзов, Д.Б. Структура мультиплексора с адаптивной матрицей хран ния выходных очередей / Д.Б. Борзов, В.В. Сусин // Микропроцессорные, анал говые и цифровые системы: проектирование и схемотехника, теория и вопрос применения: материалы 8-й Международной научно-практической конференци Новочеркасск, 20 октября 2008 г. Новочеркасск: ЮРГТУ, 2008. С. 4-6.

7. Сусин, В.В. О проблеме восстановления искаженных маршрутов соо щений в однокристальных матричных мультипроцессорах / В.В. Сусин // Пробл мы развития технологических систем государственной охраны, специальной свя и информации: материалы 6-й Всероссийской конференции, Орёл, 5-6 февр 2009 г. Орёл: Академия ФСО России, 2009. С. 283-285.

8. Зотов, И.В. Организация имитационного моделирования аппаратнь средств при подготовке дипломных проектов по вычислительной технике И.В. Зотов, В.В. Сусин, Ю.А. Векленко // Современные проблемы высшего пр фессионального образования: материалы региональной научно-мегодическ конференции, Курск, 16-17 апреля 2009 г. Курск: КурскГТУ, 2009.4.1. С. 30-32.

Свидетельство о государственной регистрации программы для ЭВМ

9. Сусин, В.В. Программа имитационного моделирования матричных коммутаторов с отказоустойчивой маршрутизацией пакетов / В.В. Сусин [и др.] У/ Свидетельство об официальной регистрации программы для ЭВМ №2009612576; заявл. 23.03.2009; per. 21.05.2009.

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

Печ. л. У). Тираж 100 экз. Заказ_.

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

Соискатель

В.В. Сусин

Введение.

1. Архитектура однокристальных матричных мультипроцессоров и коммутационные процессы в отказоустойчивых ОМП.

1.1. Особенности архитектуры ОМП.

1.2. Коммутационные процессы в ОМП.

1.3. Дефекты, отказы и сбои в ОМП. Концепция отказоустойчивых мультипроцессоров.

1.4. Организация отказоустойчивой маршрутизации пакетов в ОМП.

Выводы.

2. Организация управления маршрутизацией пакетов с коррекцией искаженных маршрутов в матричных ОМП.

2.1. Принципы управления маршрутизацией пакетов с автоматической коррекцией искаженных маршрутов.

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

2.3. Распределённый алгоритм управления маршрутизацией пакетов.

2.3.1. Алгоритм обработки пакетов на уровне коммутационного модуля матричного ОМП.

2.3.2. Расширенные алгоритмы выбора маршрутов в коммутационных модулях.

Выводы.

3. Структурно-функциональная организация коммутационного устройства матричного ОМП с коррекцией искаженных маршрутов.

3.1. Структурная организация коммутационного устройства.

3.2. Функциональные схемы основных блоков коммутационного устройства.

3.3. Анализ функционирования разработанного устройства в составе коммутационной среды матричного О МП.

Выводы.

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

4.1. Оценка вероятности искажения маршрутов в коммутационной среде матричного ОМП.

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

4.1.2. Имитационное моделирование коммутационной среды матричного ОМП.

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

Выводы.

Актуальность темы. Уровень развития современной технологии СБИС обеспечивает возможность реализации многопроцессорных систем на одном кристалле. Причем интегральное воплощение возможно не только для SMP-систем, содержащих несколько процессорных ядер, но и для NUMA-мультипроцессоров, объединяющих десятки модулей (Raytheon MONARCH, Tilera TILE64, TILEPro64, TILE-Gx). NUMA-системы такого рода, называемые однокристальными мультипроцессорами (ОМП), уже сегодня способны масштабироваться до 100-процессорных конфигураций (TILE-Gx).

Межмодульное взаимодействие в современных ОМП осуществляется через коммуникационную среду (КС) с непосредственными связями. В коммерческих мультипроцессорах, как правило, применяются КС с матричной или тороидальной топологической структурой, отличающиеся простотой СБИС-реализации и обеспечивающие множество альтернативных маршрутов передачи информации (Tilera TILE64, TILEPro64, TILE-Gx). Такие КС используют параллельные каналы связи (разрядностью данных 64 бита и выше), что позволяет выполнять межмодульный информационный обмен словами (пакетами) (Y. Chen, J. Liu, P.P. Pande).

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

Повышение отказоустойчивости мультипроцессоров и их коммутационной среды традиционно обеспечивается применением различных алгоритмов обхода отказов (дефектов) при маршрутизации пакетов. Они отличаются правилами обхода отказов, уровнем реализации (программный, аппаратный, смешанный), сложностью и комбинаторными возможностями (R.V. Boppana, S. Chalasani, C.-L. Chen, G.-M. Chiu, J. Duato, J. Wu и др.). Однако указанные алгоритмы предполагают достаточно грубый контроль состояния процессорных модулей (из-за чрезвычайно высокой сложности организации полного контроля) и не чувствительны к ошибкам в работе Отдельных блоков управления маршрутизацией. Как результат, вполне возможно, что признанный работоспособным модуль будет выдавать пакеты в неверных направлениях. Исходя из этого, существует объективная необходимость совершенствования средств управления маршрутизацией пакетов ОМП в части организации контроля блоков управления маршрутизацией и автоматической коррекции (восстановления) искаженных маршрутов передачи пакетов.

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

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

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

Диссертационная работа выполнена в рамках плана НИР Курского государственного технического университета по единому заказ-наряду Министерства образования и науки РФ в 2006-2009 годах.

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

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

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

2. Создание метода управления маршрутизацией пакетов в коммутационной среде матричных ОМП с автоматической коррекцией искаженных маршрутов при дефектах, отказах и сбоях в отдельных коммутационных блоках на основе разработанных правил преобразования.

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

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

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

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

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

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

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

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

1. Созданный метод управления маршрутизацией пакетов в коммутационной среде матричных ОМП позволяет снизить вероятность нарушения средних и длинных маршрутов (длины 3 и более) не менее чем в 1.4 раза, что обусловливает повышение надёжности КС мультипроцессора.

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

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

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

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

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

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

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

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

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

Апробация работы. Основные положения, результаты и выводы диссертации обсуждались и получили положительную оценку на УШ Международной научно-технической конференции «Оптико-электронные приборы и устройства в системах распознавания образов, обработки изображений-и символьной информации» (г. Курск, 2008 г.), на УШ Международной научно-практической конференции «Микропроцессорные, аналоговые и цифровые системы: проектирование и схемотехника, теория и вопросы применения» (г. Новочеркасск, 2008 г.), на VI Всероссийской конференции «Проблемы развития технологических систем государственной охраны, специальной связи и информации» (г. Орёл, 2009 г.), на региональной научно-методической конференции «Современные проблемы высшего профессионального образования» (г. Курск, 2009 г.), а также на научных семинарах кафедры вычислительной техники КурскГТУ в период с 2006 по 2009 год.

Публикации по теме диссертации. Содержание диссертации опубликовано в 9 работах, среди которых имеется 3 статьи в научных изданиях по перечню ВАК Минобрнауки РФ, а также 1 свидетельство о Государственной регистрации программы для ЭВМ.

Личный вклад соискателя. Все выносимые на защиту научные результаты получены соискателем лично. В опубликованных в соавторстве работах по теме диссертации личный вклад соискателя сводится к следующему: в [12, 43, 44] разработана методика оценки характеристик коммутатора с отказоустойчивой маршрутизацией сообщений (пакетов), в [39] предложен вариант формализованного описания коммутирующего элемента, в [45] изложен подход к управлению маршрутизацией пакетов на уровне коммутационного узла, в [16] описана методика построения проектов имитационного моделирования аппаратных средств, в [42] разработан ряд классов, шаблонов и функций для моделирования коммутационных элементов ОМП.

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

Выводы

1., Созданный метод управления маршрутизацией пакетов в коммутационной среде матричных ОМП позволяет снизить вероятность нарушения средних и длинных маршрутов (длины 3 и более) не менее чем в 1.4 раза, сохраняя указанную вероятность для коротких маршрутов (длины 1 и 2), что обусловливает повышение надёжности КС мультипроцессора.

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

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

Заключение

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

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

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

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

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

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

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

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

1. А.с. №1273941 СССР, МКИ 3 G06F15/20. Устройство для разбиения графа на подграфы / В.М. Глушань, Л.И. Щербаков, И.П. Левин (СССР), опубл. 1986; Бюл. №44.

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

3. А.с. 1566362 СССР, МКИ 5 G06F15/16, 13/00. Многоканальное устройство для обмена управляющей информацией в вычислительной системе / В.А.Мельников, В.С.Харченко, С.Б.Кальченко и др. (СССР). №4464412/24-24; заявлено 21.07.88; опубл.2305.90, Бюл. №19.-11 с.

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

5. А.с. 1793436 СССР, МКИ 5 G06F7/00, 15/16. Модуль матричного коммутатора /

6. B.А.Мельников, А.В.Галицкий, В.В.Копылов и др. (СССР). №4893395/24; заявлено 30.10.90; опубл. 07.02.93, Бюл. №5. - 8 с.

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

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

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

10. Ватутин, Э.И. Использование схемных формирователей и преобразователей двоичных последовательностей при построении комбинаторно-логических акселераторов / Э.И. Ватутин, И.В. Зотов, B.C. Титов // Известия КурскГТУ. 2008. №4 (25). С. 32-39.

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

12. Зотов, И.В. Процедурно-логическая модель ретрансляции сообщений для распределенных вычислительных сетей / И.В.Зотов, Ю.В.Беляев // Телекоммуникации. 2000. №6. С. 18-23.

13. Зотов, И.В. Теоретические основы синтеза схем быстродействующих устройств распределенной децентрализованной координации параллельных микропрограмм в мульти-контроллерах: дис. . д-ра техн. наук: 05.13.05: Курск, 2007. 383 с.

14. Колоскова, Г.П. Модели и алгоритмы реконфигурации многопроцессорных систем / Г.П. Колоскова; Курск, гос. техн. ун-т. Курск, 2004. 257 с.

15. Корнеев, В.В. Вычислительные системы / В.В. Корнеев. М.: Гелиос АРВ, 2004.512 с.

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

17. Лаходынова, Надежда Владимировна. Методы обеспечения отказоустойчивости процессорных матриц СБИС : дис. д-ра техн. наук : 05.13.15 : Томск, 2003.236 с.

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

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

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

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

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

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

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

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

26. Патент №5333279 США, МКИ 5 G06F13/14. Self-timed mesh routing chip with data broadcasting / D.Dunning (США). №892535; заявлено 01.06.92; опубл. 26.07.94. - 17 с.

27. Патент №7058062 США, МКИ 8 H04L12/56. Packet switching system having self-routing switches / S.Tanabe, T.Suzuki, S.Gohara et al. (Япония). №040466; заявлено 09.01.2002; опубл. 06.06.2006. - 29 с.

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

29. Райншке, К. Оценка надежности систем с использованием графов / Райншке К., Ушаков И.А.; Под ред. Ушакова И.А. М.: Радио и связь. 1988. 208 с.

30. Свидетельство о регистрации программы для ЭВМ №2007611310. Визуальная среда имитационного моделирования VisualQChart / И.В. Зотов и др.. Заявл. 13.02.07; дата регистрации 27.03.07.

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

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

33. Сусин, В.В. Аналитическая модель мультиплексора с выходными очередями /

34. B.В. Сусин, П.В. Сусин // Информационно-измерительные и управляющие системы. 2009. №4. С. 90-92.

35. Сусин, В.В. Программа имитационного моделирования матричных коммутаторов с отказоустойчивой маршрутизацией пакетов / В.В. Сусин и др. // Свидетельство об официальной регистрации программы для ЭВМ №2009612576; заявл. 23.03.2009; per. 21.05.2009.

36. Сусин, В.В. Статистическая оценка характеристик коммутации сообщений при использовании мультиплексора с выходными очередями / В.В. Сусин, Д.Б. Борзов, B.C. Титов, А.А. Царёв // Интеллектуальные информационные системы. 2009. №1. С. 85-88.

37. Титов, B.C. Проблема динамической коммутации с распределенными выходными очередями / B.C. Титов, В.В. Сусин, П.В. Сусин // Изв. ТулГУ. Сер. вычислительная техника, информационные технологии, системы управления. 2006. вып. 1. С. 71-76.

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

39. Al-Sadi, J. Probability-based fault-tolerant routing in hypercubes / J. Al-Sadi, K. Day, M. Ould-Khaoua // The Computer Journal. 2001. Vol. 44, N 5. PP. 368-373.

40. Cbalasani, S. Communication in multicomputers with nonconvex faults / S. Chalasani, R.V. Boppana // IEEE Transactions on Computers, 1997. Vol. 46, N 5. PP. 616-622.

41. Chen, C.-L. A fault-tolerant routing scheme for meshes with nonconvex faults / Chun-Lung Chen, Ge-Ming Chiu // IEEE Transactions on Parallel and Distributed Systems. 2001. Vol. 12, N5. PP. 467-475.

42. Chen, Y.-S. Multinode broadcasting in a wormhole-routed 2-D torus using an aggregation-then-distribution strategy / Y.-S. Chen, C.-Y. Chen // IEE Proceedings Computers and Digital Techniques. 2000. Vol. 147, N 6. PP. 403-413.

43. Chen, Yu. Cell Switched Network-on-Chip Candidate for Billion-Transistor System-on-Chips / Yu. Chen // Proc. IEEE International SoC Conference, Sept. 2006. PP. 57-60.

44. Chiluvuri, V.K.R. Layout Synthesis Techniques for Yield Enhancement / V.K.R. Chiluvuri, I. Koren // IEEE Transactions on Semiconductor Manufacturing, 1995. N5. Vol. 8, Special Issue on Defect, Fault, and Yield Modeling, PP. 178-187.

45. Cote, E. Implementation of a Configurable Crossbar Switch for Prototyping of Single

46. Chip Multiprocessors / E. Cote, N. Manjikian // Proc. IEEE North-East Workshop on Circuits and Systems, June 2006. PP. 197-200.

47. Dally, W.J. Deadlock-Free Message Routing in Multiprocessor Interconnection Networks / W.J. Dally, C.L. Seitz // IEEE Transactions on Computers. 1987. Vol. 36, N 5. PP. 547553.

48. Duato, J. A theory of fault-tolerant routing in wormhole networks / J. Duato // Proc. International Conference on Parallel and Distributed Systems, ICPDS 1994. 19-21 Dec. 1994. P. 600-607.

49. Gao, F. Fault-tolerant routing algorithms based on optimal path matrices / Feng Gao, Zhongchen Li // Proc. Pacific Rim International Symposium on Dependable Computing. 16-17 Dec. 1999. PP. 227-233.

50. Gomez, M.E. An effective fault-tolerant routing methodology for direct networks / M.E. Gomez, J. Flich, P. Lopez // Proc. International Conference on Parallel Processing, ICPP 2004. 1518 Aug. 2004. Vol. 1. PP. 222-231.

51. Gomez, M.E. A routing methodology for achieving fault tolerance in direct networks / M.E. Gomez, N.A. Nordbotten, J. Flich et al. // IEEE Transactions on Computers. 2006. Vol. 55, N 4. PP. 400-415.

52. Ho, C.-T. A new approach to fault-tolerant wormhole routing for mesh-connected parallel computers / C.-T. Ho, L. Stockmeyer // IEEE Transactions on Computers. 2004. Vol. 53, N 4. PP. 427-438.

53. Hou, Y. Broadcasting on wormhole-routed 2D tori with arbitrary size / Yomin Hou, Chien-Min Wang, Ming-Jer Tsai, Lih-Hsing Hsu // Proc. International Conference on Parallel and Distributed Systems. 14-16 Dec. 1998. PP. 334-341.

54. Huang, Ch.-M. Implementation and prototyping of a complex multi-project system-on-a-chip / Ch.-M. Huang, Ch.-M. Wu, Ch.-Ch. Yang et al. // Proc. IEEE International Symposium on Circuits and Systems, ISCAS 2009. 24-27 May 2009. PP. 2321-2324.

55. Huang, Jing. On the defect tolerance of nano-scale two-dimensional crossbars / Jing Huang, M.B. Tahoori, F. Lombardi // Proc. 19th IEEE International Symposium on Defect and Fault Tolerance in VLSI Systems, DFT 2004. 10-13 Oct. 2004. PP. 96-104.

56. Jerraya, A. Guest Editors' Introduction: Multiprocessor Systems-on-Chips / A. Jerraya, H. Tenhunen, W. Wolf// Computer. 2005. Vol. 38, N 7. PP. 36-40.

57. Jiang, Z. A limited-global information model for dynamic fault-tolerant routing in cube-based multicomputer^ / Zhen Jiang, Jie Wu // Proc. 2nd IEEE Internationa. Symposium on Network Computing and Applications, NCA 2003. 16-18 April 2003. PP. 333-340.

58. Jum, Jong Arm. A two-dimensional scalable crossbar matrix switch architecture / Jong Arm Jum, Sung Hyuk Byun, Byung Jun Ahn et al. // Proc. IEEE International Conference on Communications, ICC 2003. 11-15 May 2003. Vol. 3. PP. 1892-1896.

59. Kim, D. A reconfigurable crossbar switch with adaptive bandwidth control for networks-on-chip / Donghyun Kim; Kangmin Lee et al. // Proc. IEEE International Symposium on Circuits and Systems, ISCAS 2005. 23-26 May 2005. Vol. 3. PP. 2369-2372.

60. Koren, I. Defect Tolerant VLSI Circuits: Techniques and Yield Analysis / I. Koren, Z. Koren//Proceedings of the IEEE. Sept. 1998. Vol. 86. PP. 1817-1836.

61. Lee, Y.-T. Low power SoC in deep-submicron era / Y.-T. Lee // Proc. IEEE International Systems-on-Chip Conference, 17-20 Sept. 2003. P. 421.

62. Mekkittikul, A. A practical scheduling algorithm to achieve 100% throughput in input-queued switches / A. Mekkittikul, N. McKeown // Proc. INFOCOM-98. 29 March 2 April, San Francisco, 1998. Vol. 2. P. 792-799.

63. Mir, N.F. Analysis of fault-tolerant multipath crossbars / N.F. Mir // Proc. IEEE Global Telecommunications Conference, GLOBECOM 2003. Vol. 5. PP. 2908-2912.

64. Murali, S. An Application-Specific Design Methodology for On-Chip Crossbar Generation / S. Murali, L. Benini, G. De Micheli // IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems. 2007. Vol. 26, N 7. PP. 1283-1296.

65. Nomura, K. Novel Design of Three-Dimensional Crossbar for Future Network on Chip based on Post-Silicon Devices / K. Nomura, K. Abe et al. // Proc. 1st International Conference on Nano-Networks and Workshops, NanoNet '06. Sept. 2006. PP. 1-5.

66. Seo, D. Table-lookup based Crossbar Arbitration for Minimal-Routed 2D Mesh and Toms Networks / D. Seo, M. Thottethodi // Proc. IEEE International Parallel and Distributed Processing Symposium, IPDPS 2007. 26-30 March 2007. PP. 1-10.

67. Sui, P.-H. An improved algorithm for fault-tolerant wormhole routing in meshes / P.-H. Sui, S.D. Wang // IEEE Transactions on Computers. 1997. Vol. 46, N 9. PP. 1040-1042.

68. Tahoori, M.B. Application-Independent Defect-Tolerant Crossbar Nano-Architectures / M.B. Tahoori // Proc. IEEE/ACM International Conference on Computer-Aided Design, ICCAD 2006. Nov. 2006. PP. 730-734.

69. Takanami, I. Built-in self-reconfiguring systems for mesh-connected processor arrays with spares on two rows/columns / I. Takanami // Proc. IEEE International Symposium on Defect and Fault Tolerance in VLSI Systems. 25-27 Oct. 2000. PP. 213-221.

70. Tarek, E.-G. A general framework for developing adaptive fault-tolerant routing algorithms / E.-G. Tarek, Y. Abdou // IEEE Transactions on Reliability. 1993. Vol.42, N2. PP. 250-258.

71. TILE64 Processor, Tilera Corp., http://www.tilera.com. 2007.

72. Tobagi, F.A. Fast packet switch architectures for broadband integrated services digital networks / F.A. Tobagi // Proc. IEEE. 1990. Vol.78, N1. P. 133-167.

73. Tsuda, N. Fault-tolerant processor arrays using additional bypass linking allocated by graph-node coloring / N. Tsuda // IEEE Transactions on Computers. 2000. Vol. 49, N 5. P. 431442.

74. Vial, J. Yes, we can improve SoC yield / J. Vial, A. Virazel // Research in Microelectronics and Electronics, 2009. PRIME 2009. Ph.D. 12-17 July 2009. PP. 272-275.

75. Wang, K. Design and implementation of fault-tolerant and cost effective crossbar switches for multiprocessor systems / K. Wang, C.-K. Wu // IEE Proceedings Computers and Digital Techniques, Jan. 1999. Vol. 146, Issue 1'. PP. 50-56.

76. Wang, G. A new fault-tolerant routing scheme for 2-dimensional mesh networks / Gaocai Wang, Jianer Chen // Proc. 4th International Conference on Parallel and Distributed Computing, Applications and Technologies, PDCAT 2003. 27-29 Aug. 2003. PP. 95-98.

77. Wang, G. A probabilistic approach to fault-tolerant routing algorithm on mesh networks / Gaocai Wang, Taoshen Li, J. Chen // Proc. 10th International Conference on Parallel and Distributed Systems, ICPADS 2004. 7-9 July 2004. PP. 577-584.

78. Wijetunga, P. High-performance crossbar design for system-on-chip / P. Wijetunga // Proc. 3rd IEEE International Workshop on System-on-Chip for Real-Time Applications. 30 June 2 July 2003. PP. 138-143.

79. Wu, J. A fault-tolerant and deadlock-free routing protocol in 2-D meshes based on odd-even turn model / J. Wu // IEEE Transactions on Computers. 2003. Vol. 52, N 9. PP. 1154-1169.

80. Wu, J. Fast reconfiguring mesh-connected VLSI arrays / Wu Jigang, T. Srikanthan // Proc. International Symposium on Circuits and Systems, ISCAS 2004. 23-26 May 2004. Vol. 2. PP. 949-952.

81. Wu, J. On constructing the minimum orthogonal convex polygon for the fault-tolerant routing in 2-D faulty meshes / Jie Wu, Zhen Jiang // IEEE Transactions on Reliability. 2005.

82. Vol. 54, N 3. PP. 449-458.

83. Wu, Т. A 2 Gb/s 256*256 CMOS crossbar switch fabric core design using pipelined MUX / Ting Wu, Chi-Ying Tsui, Hamdi, M. // Proc. IEEE International Symposium on Circuits and Systems, ISCAS 2002. 26-29 May 2002. Vol. 2. PP. 568-571.

84. Xiang, D. Fault-tolerant routing in 2D tori or meshes using limited-global-safety information / Dong Xiang, Ai Chen // Proc. International Conference on Parallel Processing, ICPP 2002. 18-21 Aug. 2002. PP. 231-238.

85. Xiang, D. Fault-tolerant routing in meshes/tori using planarly constructed fault blocks / Dong Xiang, Jia-Guang Sun, J. Wu, K. Thulasiraman // Proc. International Conference on Parallel Processing, ICPP 2005. 14-17 June 2005. PP. 577-584.

86. Zakrevski, L. Fault-tolerant message routing for multiprocessors / L. Zakrevski, M.G. Karpovsky// Parallel and Distributed Processing. Springer. 1998. PP. 714-731.

87. Zhao, T. VLSI yield optimization based on the sub-processing-element level redundancy / Tianxu Zhao, Yue Hao, Yongchang Jiao // IEEE International Symposium on Defect and Fault Tolerance in VLSI Systems. 25-27 Oct. 2000. PP. 41-46.

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