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

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

Аль-Ашвал Муджиб Мохаммед Яхья

МЕТОД, АЛГОРИТМ И УСТРОЙСТВА ОТКАЗОУСТОЙЧИВОЙ ШИРОКОВЕЩАТЕЛЬНОЙ ПЕРЕДАЧИ ПАКЕТОВ НА ПРЯМОУГОЛЬНУЮ О&Я^СТЬ ПРИЕМНИКОВ В МАТРИЧНЫХ СБИС-МУЛЬТИКОМПЬЮТЕРАХ

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

АВТОРЕФЕРАТ

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

Курск-2010

003493303

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

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

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

доктор технических наук, профессор Бурмака Александр Александрович

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

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

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

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

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

Автореферат разослан 24 февраля 2010 г.

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

И.В. Зотов

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

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

Одним из распространённых в ММК режимов межмодульного обмена является передача пакета от одного источника нескольким приёмникам. Такой режим лежит в основе реализации многих системных процедур и стандартных функций прикладного уровня (например: МР^ВсаБ^ МР1_А11гес1исе, МР1_Вагпег) и обычно называется широковещательной передачей (вещанием). Вещание пакета можно выполнить путём его многократной выдачи источником и последующей маршрутизации с использованием известных алгоритмов организации попарного межмодульного обмена (например, алгоритма ХУ-маршрутизации). Такой подход весьма прост в реализации и инвариантен к форме области приёмников. В то же время он обусловливает резкий рост интенсивности потока пакетов в КС, что существенно увеличивает среднее время их передачи.

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

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

адресов процессоров их логическим адресам и выполнять вещание на множество логических приёмников.

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

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

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

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

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

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

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

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 работах, среди которых имеется I статья в научном издании по перечню ВАК Минобрнауки РФ, а также 1 свидетельство о Государственной регистрации программы для ЭВМ.

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

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

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

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

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

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

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

Известные тиШсаз^алгоритмы базируются на двух способах задания множества приёмников в адресной части пакета. Первый способ предполагает использо-

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

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

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

Пусть Р = {Ри,Р12,...,Р1„,Р2Л,Р2г,...,Р1„,...,РМ1,РМ2,...,Ри„} - множество

процессорных модулей ММК. Модуль Рч (; = 1 ,М, ] = 1,N) находится на пересечении ¡-й строки и у-го столбца матрицы мультикомпьютера. Он включает (см. рис. 1) процессорное ядро К1 . и коммуникационное устройство (КУ) С,^, соединенные двунаправленной шиной, причём множество коммуникационных уст-

ройств {С/ ;} вместе с соответствующими связями (межмодульными шинами) образует КС ММК.

Обозначим через лг, у множество процессорных модулей, которым в ходе реконфигурации ММК алгоритмом свободного захвата может быть присвоен логический адрес /.у: я,,= ■ Введём в КС множество дополнительных коммуникационных устройств {С* обеспечивающих вещание пакетов на четвёрки соседних процессорных модулей я^. Конфигурацию связей КУ С* 7 с процессорными модулями и модуля РГ1 с КУ {С*,;| определим в

соответствии со схемами, приведенными на рис. 2, а и б соответственно. Через и

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

Рис. 1. Архитектура процессорного модуля ММК

а)

■Л,:.

г*-''*,-,

Рис. 2. Конфигурации связей между процессорным и коммуникационными устройствами

модулями

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

С*,,+1, С*,ч„ или С* (см. рис. 2, б) в зависимости от выбранного направления маршрутизации. На втором шаге это КУ осуществляет параллельную рассылку пакета модулям множества л1{ - ¡^¡л^л] (см- Рис- 2, а), при этом па-

кет принимает только тот модуль Ре я, ^ логический адрес которого совпадает

с адресом текущего приёмника.

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

Рис. 3. Схема соединения коммуникационных устройств в составе матричного мультикомпьютера

Разработанный метод предполагает наличие единственного источника пакета и множества приёмников Д образующих прямоугольную область в логической структуре ММК. В предельных случаях множество О включает все модули мультикомпьютера (Э = Р) либо единственный приёмник (£) = {Рк1}). В общем случае

Р Р Р

1 к! >' *(/+!)»■■• >г *(/ + ».)>

В =

Р Р Р

1 (4+1)/' {4+1)('+и')'

(О

Р Р Р

1 (к+Ь)!'1 («г+й)('+1)'"" ' (*■+*)(/+»)

где м> и /г - соответственно ширина и высота области приёмников (прямоугольника вещания), а Ри - приёмник с минимальными координатами на множестве О, к е {1,2,...,М), / е [\,2,...,Щ, М и N - число строк и столбцов матричной структуры соответственно.

При отсутствии отказов (дефектов) в мультикомпьютере (или если маршруты реконфигурации логической структуры ММК не пересекают область приёмников) множество О будет отображаться одинаковым образом и на логическую, и на физическую структуры мультикомпьютера, обеспечивая одни и те же ширину м> и высоту А области приёмников (см. рис. 4, а). В противном случае отображение множества О в физической структуре ММК будет отличаться от прямоугольника, при этом ширина и высота физической области приёмников могут стать неопределенными (см. рис. 4, б). Такая особенность организации реконфигурируемых ММК обусловливает необходимость передачи пакетов в пространстве логических адресов, что обеспечивается разработанной схемой соединения коммуникационных устройств, представленной на рис. 2 и 3.

источник маршрут к множеству I)

й> 12(34

2 1гТ1 ЕЗ! ШНгд]

источник маршрут к множеству й 6 7 8 9

"зигага

й) 12 3 4

8П0нийн

логическим множество резервные адрес модуля приемников О модули

800000

логический дефектный ацрес модуля модуль

резервные модули множество приемникок О

Рис. 4. Определение границ области приёмников при наличии отказавших модулей

Область приёмников задаётся логической шириной и высотой И, которые определяются по максимальной разности соответствующих координат на множестве приёмников I). Направление обхода области приёмников зависит от размещения её начального модуля. Начальным может быть любой угловой модуль прямоугольника вещания в зависимости от расположения источника; соответственно, возможны четыре варианта обхода (см. выражение (1) и табл. 1).

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

руется и получаемая копия транслируется вниз по всей логической высоте области. Аналогично можно интерпретировать и остальные варианты.

___Таблица 1

№ п/п Размещение начального модуля области приёмников Направление обхода области приёмников

1 в левом верхнем углу (Рк!) вправо-вниз

2 в правом верхнем углу влево-вниз

3 в левом нижнем углу (Р^му) вправо-вверх

4 в правом нижнем углу влево-вверх

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

FINAL LD NEXT LD BR WIDTH BR HEIGHT 1 BR TRACEDIR

где FINAL_LD - поле логического адреса начального модуля области приёмников (включает поля номера строки FINAL_LD.ROW и столбца FINALLD.COL); NEXTLD - поле логического адреса очередного транзитного модуля (включает поля номера строки NEXT_LD.ROW и столбца NEXT_LD.COL); BR_WIDTH, BRJHEIGHT - размеры области приёмников (соответственно её ширина и высота); BR_TRACEDIR - направление обхода области приёмников (согласно табл. 1).

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

Разработанный алгоритм управления широковещательной передачей пакетов параллельно выполняется совокупностью КУ |с(у} и {С*и} в составе КС муль-

тикомпьютера (см. рис. 1-3). Устройства {С,7} осуществляют основную часть алгоритма, которая включает определение направлений выдачи пакетов на различных этапах вещания, счёт числа шагов передачи пакета и реализацию заданного направления обхода области приёмников. Часть алгоритма, реализуемая устройствами {с* jJ, сводится только к параллельной ретрансляции пакетов на четвёрки соседних модулей без маршрутизации.

Граф-схема алгоритма управления широковещательной передачей пакетов, реализуемая устройством Ct], изображена на рис. 5. Основная часть обозначений

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

Рис. 5. Граф-схема алгоритма управления вещанием пакетов, реализуемая КУ С,у

DIR2 - направления передачи соответственно пакета и его копии (стрелочками условно показаны значения этих направлений); Fl, F2 функции вычисления направлений DIR, DIR2; NEXT_LD_V, BR_VVIDTH V - значения полей NEXT_LD, BR_WIDTH, передаваемые по вертикали матрицы ММК; X(Ki.j), X(D1R), X(DIR2) - дополнительные логические условия. Отличительной особенностью разработанного алгоритма является использование простейших операций над двоичными векторами, что даег возможность его аппаратной реализации. Алгоритм позволяет выполнять одновременную передачу пакета в двух направлениях, что способствует увеличению скорости обработки транзитных пакетов при вещании.

На основе разработанного аппаратно-ориентированного алгоритма с учётом принятой структуры адресной части пакета предложена структурно-функциональная организация аппаратных средств управления широковещательной передачей пакетов, отличающаяся применением двух типов коммуникационных устройств iC,v] и {С*,}, соединённых по схеме рис. 2, 3.

Структурно-функциональная схема устройства С: . изображена на рис. 6. Её

основными блоками являются входные буферы пакетов BUF0-BUF4, анализатор соотношения длин очередей пакетов LRA, мультиплексор MX, дешифратор выбора буфера DC, буферные регистры RG1 и RG2, регистр логического адреса LARG, блок управления вещанием BCU, блоки идентификации приёмника пакета LDIU1-LDIU4, генератор тактовых импульсов CPG.

Рис.6. Структурно-функциональная схемаКУ С,

Назначение перечисленных блоков сводится к следующему. Буфер BUFO служит для приема, хранения и выдачи в порядке поступления пакетов, приходящих из процессорного ядра KLj. Буферы BUF1-BUF4 предназначены для приема, хранения и выдачи в порядке поступления пакетов, приходящих от коммуникационных устройств C*t/,C*MJ,C*I+}J_Í,C*IJ.Í соответственно. Анализатор LRA служит для анализа соотношения длин очередей пакетов в буферах BUF0-BUF4 и выбора буфера, содержащего наибольшее число пакетов. Мультиплексор МХ обеспечивает коммутацию очередного пакета из выбранного буфера на вход регистра RG1. Дешифратор DC служит для преобразования двоичного кода выбора буфера в соответствующий унитарный код. Регистр RG1 предназначен для хранения очередного считанного пакета в процессе его обработки. Регистр RG2 служит для хранения модифицированной адресной части обработанного пакета. Регистр LARG предназначен для постоянного хранения текущего логического адреса данного устройства в составе КС ММК. Блок управления вещанием BCU служит для формирования сигналов управления вещанием в зависимости от значений полей обрабатываемого пакета (размещенных в регистре RG1), в том числе сигналов выбора направления выдачи пакета. Возможны 5 направлений выдачи: в процессорное ядро Kt¡, а также в соседние модули Ptj4, PM¡, Pi_i J. Блоки идентификации приёмника пакета LDIU1-LDIU4 предназначены для блокировки приёма пакетов, поступающих от устройств C*IJ,C*M J,C*l+l/_vC*jJ_l, при несовпадении значения поля NEXT_LD с логическим адресом данного устройства, поступающим из регистра LARG. В состав каждого блока LDIU1- LDIU4 входят два компаратора и блок трёхвходовых элементов И.

Схема устройства С*; аналогична ядру схемы устройства С, ] (обведена

штрихпунктирной линией рис. 6). Её особенностью является отсутствие блоков для выбора направлений выдачи и модификации адресной части пакетов: после записи в буферный регистр RG1 каждый пакет сразу выдается четвёрке модулей 7г( j=\Pt.ji f¡.j+i>ñ-i j+i} чеРез соответствующие буферные усилители (на рис. 6 не показаны).

Суммарная аппаратная сложность разработанных устройств в составе КС ММК (в числе эквивалентных двухвходовых вентилей - ЭВ) определяется следующим выражением:

9-2L(L + l) + [>data + 3([log2 М] + flog, iV])](63/. + 57) + 3421

H = MN |~log;M~\2+ [log2Nf+ 79flog2M| + 99(~log2 A']+ 910 ' ^ + 2

где Мп -¿V- соответственно число строк и столбцов в матрице мультикомпьютера (с учетом резервного столбца); Ь - предельная длина входных буферов В1Ж; ^олта - разрядность поля данных пакета.

Формула (2) позволяет оценить предельную размерность КС ММК (М х N), которая может быть достигнута при заданном технологическом ограничении на число ЭВ г при фиксированной длине буферов Ь. Так, например, при г = 10 млн. ЭВ (что соответствует степени интеграции современных СБИС) и Й^„АТА = 32 бита можно реализовать КС размерности: 13x13 для ¿ = 8 (Я = 9415835 ЭВ), 17x17 для ¿ = 6 (# = 9819931 ЭВ) и 21x21 для Х = 4 (Я = 9777411 ЭВ). Таким образом, предложенный подход уже сегодня обеспечивает возможность построения отказоустойчивых КС для резервированных СБИС-систем, превосходящих по сложности ММК ПЬЕ-вх. Наименьший уровень избыточности разработанных схем относительно базовых схем КС (реализующих только попарный обмен при отсутствии отказов) составляет 242% при 1 = 8.

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

Сравнительная оценка осуществлялась на основе имитационного моделирования функционирования разработанных устройств и в составе КС

ММК. В ходе моделирования рассматривался мультикомпьютер в конфигурации 8x8 модулей. Предполагалось, что процессорное ядро (Ки) каждого модуля РГ]

независимо генерирует пуассоновский поток пакетов с интенсивностью Я = 1/50, 1/100,1/150, 1/200 и 1/250 (пакет / тактов), где такт соответствует периоду следования импульсов синхронизации модуля. Отказы модулей } считались независимыми с интенсивностью г] = 1/50000 (отказ / тактов). Поскольку аппаратная сложность модуля Ри на порядок превышает сложность КУ С* вероятность

отказа устройств {С*(/| предполагалась пренебрежимо малой по сравнению с вероятностью отказа модулей . Конфигурации маршрутов и размещение областей приёмников выбирались случайным образом согласно равномерному закону распределения. Высота И и ширина -н> области приёмников для каждого пакета считались равными 2 (наихудший случай для разработанного алгоритма). В результате моделирования регистрировалось число пакетов (¿0, доставленных всем приёмникам области приёмников, число пакетов (I), потерянных из-за фатальной ситуации в алгоритме управления вещанием, а также среднее время передачи пакета (Т). Моделирование выполнялось циклами длительностью 2000 тактов, каждый из результатов усреднялся по 100 циклам.

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

представлены значения величин для разработанного алгоритма управления вещанием.

Т, тактов (а) р, % (б)

Рис. 7. Зависимости среднего времени передачи пакета Т (а) и уровня потерь пакетов р (б) от интенсивности потока пакетов Л, полученные в результате имитационного моделирования: доверительный интервал соответствует доверительной вероятности 0.98

Зависимости, представленные на рис.7, демонстрируют преимущества разработанного алгоритма управления вещанием перед аналогами как по времени передачи пакета Т, так и по уровню потерь пакетов р. По сравнению с динамическим алгоритмом вещания на линейную область минимальный выигрыш по времени Т составляет в среднем (см. рис.7, я) 1,2 раза и по уровню потерь пакетов р (см. рис.7, б) - в среднем 2,1 раза. При этом уровень потерь пакетов р удаётся снизить до 0,5(±0,075)-Ю,7(±0,105)% от общего числа сгенерированных пакетов (при использовании алгоритма вещания на линейную область и динамического алгоритма попарного обмена теряется соответственно от 0.7(±0,126)% до 1,4(±0,252)% и от 1.4(±0,224)% до 1,7(±0,272)% пакетов).

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Материалы конференций и тезисы докладов

2. Аль-Ашвал, М.М. Имитационное моделирование средств отказоустойчивого вещания сообщений в матричных мультипроцессорах / Аль-Ашвал М.М., Зотов И.В., Наджаджра М.Х. / Отико-электронные приборы и устройства в системах распознавания образов, обработки изображении и символьной информации: материалы 8-й Международной научно-технической конференции, Курск, 13-15 мая 2008 г.: В 2 ч. Курск: КурскГТУ, 200S. 4.1. С. 38-40.

3. AI-Ashwal, М.М. Fault-tolerant message routing algorithms for parallel computer systems / M.M. Al-Ashwal, I.V. Zotov / Медико-экологические 1шформационпые технологии: материалы XI Международной научно-технической конференции, Курск, 21-24 мая 2008 г. Курск: КурскГТУ, 2008. С. 138-140.

4. Аль-Ашвал, М.М. Об организации широковещательного обмена сообщениями в матричных мультипроцессорах 1 Аль-Ашвал М.М., Зотов И.В. / Информационно-математические технологии в экономике, технике и образовании: материалы III Международной научной конференции, Екатеринбург, 20-22 шября 2008 г. Екатеринбург: УГТУ-УПИ, 2008. С. 211-212.

5. Об ограничении области распространения координирующих сигналов при реализации барьерной синхронизации в матричных системах / Аль-Хади А.М.А., Зотов И.В., Аль-Ашвал М.М., Волобусв C.B. / Интеллектуальные и информационные системы: сборник материалов Всероссийской научно-технической конференции, Тула, 18-19 ноября 2009 г. Тула: ТулГУ, 2009. С. 80-82.

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

Заявки на изобретение

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

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

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

Соискатель

М.М. Аль-Ашвал

ИД N»06430 от 10.12.01 г. Подписано в печать 18.02.2010 г. Формат 60x84 1/16. _Печ. л. 1,0. Тираж 100 экз. Заказ 899._

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

Отпечатано: ПБОЮЛ Киселева О.В. ОГРН 304463202600213

Введение.

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 раза по сравнению с известным алгоритмом вещания пакетов на линейную область приёмников.

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.