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

• Аль-Ашвал Муджиб Мохаммед Яхья
• кандидат технических наук
• 2010

Оглавление диссертации кандидат технических наук Аль-Ашвал Муджиб Мохаммед Яхья

Введение.

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

1.1. Особенности архитектуры однокристальных ММК на примере СБИС-систем TILE).

1.2. Коммуникационные процессы в СБИС-мультикомпьютерах.

1.3. Концепция реконфигурируемых отказоустойчивых СБИС-мультикомпьютеров.

1.4. Алгоритмы и аппаратные средства управления широковещательной передачей пакетов в СБИС-мультикомпьютерах.

Выводы.

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

2.1. Сущность разработанного метода.

2.2. Топологическая структура коммуникационной среды СБИС-мультикомпьютера.

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

2.4. Структура и формат пакетов.

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

Выводы.

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

3.1. Алгоритм управления широковещательной передачей пакетов.

3.2. Структурно-функциональная организация коммуникационных устройств.

3.3. Анализ функционирования разработанных устройств в составе коммуникационной среды СБИС-мультикомпьютера.

3.4. Оценка аппаратной сложности и избыточности предложенных схемных решений.

Выводы.

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

4.1. Методика проведения сравнительной оценки.

4.2. Особенности архитектуры инструментальных программных средств и разработанной имитационной модели.

4.3. Оценка среднего времени передачи пакетов.

4.4. Оценка уровня потерь пакетов.

Выводы.

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

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

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

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

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

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

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

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

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

Диссертационная работа выполнена в рамках совместных НИР ОХП ОКБ «Авиаавтоматика» Курского ОАО «Прибор» и ГОУ ВПО КурскГТУ, а также в соответствии с планом НИР КурскГТУ по единому заказ-наряду Министерства образования и науки РФ в 2006-2009 годах. v.

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

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

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

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

3. Синтезировать алгоритм управления широковещательной передачей пакетов на прямоугольную область приёмников в логической структуре ММК.

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

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

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

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

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

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

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

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

1. Созданный алгоритм управления широковещательной передачей пакетов позволяет снизить время передачи пакетов в КС ММК при их вещании на прямоугольную область приёмников в среднем в 1,2 раза по сравнению с известным алгоритмом организации вещания пакетов на линейную область и уменьшить потери пакетов в среднем в 2,1 раза до уровня 0,5(±0,075)-Ю,7(±0,105)% от общего числа сгенерированных пакетов.

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

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

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

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

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

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

5. Результаты оценки времени передачи пакетов и уровня их потерь в режиме вещания на прямоугольную область приёмников, полученные путём имитационного моделирования работы коллектива разработанных устройств в составе КС мультикомпьютера при различных вариантах распределения дефектов и отказов в ММК, демонстрирующие снижение времени передачи пакетов в режиме вещания на прямоугольную область приёмников по сравнению с алгоритмом вещания на линейную область в среднем в 1,2 раза и одновременное уменьшение числа потерянных пакетов в среднем в 2,1 раза до уровня 0,5(±0,075) + 0,7(±0,105)% от общего числа сгенерированных пакетов.

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

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

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

Личный вклад соискателя. Все выносимые на защиту научные результаты получены соискателем лично. В опубликованных в соавторстве работах по теме диссертации личный вклад соискателя сводится к следующему: в [10] разработан метод организации вещания пакетов при переразмещении задач в специализированном отказоустойчивом мультикомпьютере; в [9, 39] разработана методика, а также классы и функции для моделирования коммуникационных устройств вещания пакетов; в [46] выполнен сравнительный анализ алгоритмов отказоустойчивой маршрутизации; в [11] предложена структурно-функциональная организация коммуникационных устройств широковещательного обмена; в [25] определена процедура вещания координирующих пакетов в матричной структуре; в [15, 16] предложены схемные решения для оценки коммуникационных затрат.

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

Заключение диссертации по теме «Элементы и устройства вычислительной техники и систем управления», Аль-Ашвал Муджиб Мохаммед Яхья

Выводы

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

2. Результаты оценки времени передачи пакетов и уровня их потерь в режиме вещания на прямоугольную область приёмников, полученные путём имитационного моделирования работы коллектива разработанных устройств в составе КС мультикомпьютера при различных вариантах распределения дефектов и отказов в ММК, демонстрируют снижение времени передачи пакетов в режиме вещания на прямоугольную область приёмников по сравнению с алгоритмом вещания на линейную область в среднем в 1,2 раза и одновременное уменьшение числа потерянных пакетов в среднем в 2,1 раза до уровня 0,5(±0,075) 0,7(±0,105)% от общего числа сгенерированных пакетов.

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

Заключение

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

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

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

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

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

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

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

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

Список литературы диссертационного исследования кандидат технических наук Аль-Ашвал Муджиб Мохаммед Яхья, 2010 год

1. А.с. 1462344 СССР, МКИ4 G06F15/16. Устройство для формирования маршрута сообщения в однородной вычислительной системе / В.А.Мельников, В.С.Харченко, Г.Н.Тимонькин, С.Н.Ткаченко (СССР). №4284146/24-24; заявлено 13.07.87; опубл. 28.02.89, Бюл. №8. - 10 с.

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

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

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

5. Аль-Ашвал, М.М. Метод оперативного переразмещения задач в отказоустойчивых логических мультиконтроллерах / Аль-Ашвал М.М. и др. // Нейрокомпьютеры: разработка, применение, 2010, №1. С. 29-34.

6. Емельянов, С.Г. Архитектура параллельных логических мультиконтрол-леров / С.Г. Емельянов, И.В. Зотов, B.C. Титов; М.: Высшая школа, 2009. 233 с.

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

8. Заявка №2008146457/09. Устройство поиска минимального значения интенсивности размещения в системах с шинной организацией при двунаправленной передаче информации / М.М. Аль-Ашвал и др. (РФ). М.: РосПатент; заявлено: 24.11.2008, приоритет: 24.11.2008.

9. Заявка №2008146458/09. Устройство поиска нижней оценки размещения в полносвязных матричных системах при двунаправленной передаче информации / М.М. Аль-Ашвал и др. (РФ). М.: РосПатент; заявлено: 24.11.2008, приоритет: 24.11.2008.

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

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

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

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

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

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

16. Наджаджра, М.Х. Алгоритм и устройство распределенного отказоустойчивого вещания сообщений с групповой индексацией приемников: дис. . канд. техн. наук: 05.13.05: Курск, 2008. 195 с.

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

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

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

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

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

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

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

24. Патент №5271014 США, МКИ 5 G06F15/00. Method and apparatus for a fault-tolerant mesh with spare nodes / J.Bruck, R.E.Cypher, C.-T.Ho (США). -№878946; заявлено 04.05.92; опубл. 14.12.93. 37 с.

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

26. Патент №5826049 США, МКИ 6 G06F15/163, G06F15/173. Partial broadcast method in parallel computer and a parallel computer suitable therefore / Y.Ogata, J.Nakagoshi et al. (Япония). №916630; заявлено 22.07.91; опубл. 20.10.98. - 45 с.

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. Программа имитационного моделирования матричных коммутаторов с отказоустойчивой маршрутизацией пакетов / М.М. Аль-Ашвал и др. // Свидетельство об официальной регистрации программы для ЭВМ №2009612576; заявл. 23.03.2009; per. 21.05.2009.

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

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

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

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

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

35. 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.

36. Benini, L. Networks on chips: a paradigm / L. Benini, G. De Micheli // IEEE Transactions on Computers, 2002. Vol. 35, N 1. PP. 70-78.

37. Bjerregaard, T. A survey of research and practices of network-on-chip / T. Bjerregaard, S. Mahadevan // ACM Computing Surveys, 2006. Vol. 38, N 1. PP. 1-51.

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

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

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

41. 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.

42. Chiluvuri, V.K.R. Layout synthesis techniques for yield enhancement / V.K.R. Chiluvuri, I. Koren // IEEE Transactions on Semiconductor Manufacturing, 1995. N 5. Vol. 8, Special Issue on Defect, Fault, and Yield Modeling, PP. 178-187.

43. Dally, W.J. Deadlock-free message routing in multiprocessor interconnection networks / W.J. Dally, C.L. Seitz // IEEE Transactions on Computers. 1987. Vol. 36, N5. PP. 547-553.

44. 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.

45. Ebrahimi, M. An Adaptive Unicast/Multicast Routing Algorithm for MPSoCs / M. Ebrahimi, M. Daneshtalab et al. // Proc. 12th Euromicro Conference on Digital System Design, Architectures, Methods and Tools, 2009. DSD '09. 27-29 Aug. 2009. PP. 203-206.

46. Fick, D. A highly resilient routing algorithm for fault-tolerant NoCs / D. Fick, A. DeOrio et al. // Proc. Design, Automation & Test in Europe Conference & Exhibition, 2009. DATE '09. 20-24 April 2009. PP. 21-26.

47. 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.

48. 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. 15-18 Aug. 2004. Vol. 1. PP. 222-231.

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

50. Zhen Zhang Greiner, A. A reconfigurable routing algorithm for a fault-tolerant 2D-Mesh Network-on-Chip / A. Zhen Zhang Greiner, S. Taktak // Proc. 45th ACM/IEEE Design Automation Conference, 2008. DAC 2008. 8-13 June 2008. PP. 441-446.

51. 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.

52. 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.

53. 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.

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

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

56. 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. 18921896.

57. Karimi, N. Online network-on-chip switch fault detection and diagnosis using functional switch faults / N. Karimi, A. Alaghi et al. // Journal of Universal Computer Science, 2008. Vol. 14, N 22. PP. 3716-3736.

58. 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.

59. 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.

60. Message Passing Interface Forum, MPI-2: Extensions to the Message-Passing Interface, July 1997.

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

62. Shan Yan Lin, B. Custom Networks-on-Chip Architectures With Multicast Routing / B. Shan Yan Lin // IEEE Transactions on Very Large Scale Integration (VLSI) Systems, 2009. Vol. 17, N 3. PP. 342-355.

63. Woojoon Lee Sobelman, G.E. Mesh-star hybrid NoC architecture with CDMA switch / G. E. Woojoon Lee Sobelman // IEEE International Symposium on Circuits and Systems, 2009. ISCAS 2009. 24-27 May 2009. PP. 1349-1352.

64. SoC (System-on-a-Chip) testing for plug and play test automation / Edited by Chakrabarty Krishnendu; Springer, 2002. 216 p.

65. 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.

66. 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. 213221.

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

68. 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.

69. Valinataj, M. Inherent reliability evaluation of networks-on-chip based on analytical models / M. Valinataj, S. Mohammadi, S. Safari // Proc. International Symposium on System-on-Chip, 2008. SOC 2008. 5-6 Nov. 2008. PP. 1-4.

70. 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. 272275.

71. VLSI-SoC: Research trends in VLSI and systems on chip / Edited by G. De Micheli, S.Mir, R.Reis; Springer, 2007. 398 p.

72. 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.

73. 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.

74. 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.

75. 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, N9. PP. 1154-1169.

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

77. Wu, J. On constructing the minimum orthogonal convex polygon for the fault-tolerant routing in 2-D faulty meshes / Jie Wu, Zhen Jiang // IEEE Transactions on Reliability. 2005. Vol. 54, N 3. PP. 449-458.

78. 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.

79. 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.

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

81. 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.