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

Актуальность темы

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