Метод и устройство управления маршрутизацией пакетов с коррекцией искаженных маршрутов в однокристальных матричных мультипроцессорах тема диссертации и автореферата по ВАК РФ 05.13.05, кандидат технических наук Сусин, Виктор Викторович

• Сусин, Виктор Викторович
• кандидат технических наук
• 2009

Оглавление диссертации кандидат технических наук Сусин, Виктор Викторович

Введение.

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

Список литературы диссертационного исследования кандидат технических наук Сусин, Виктор Викторович, 2009 год

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.