Введение к работе
Актуальность темы. Появление СБИС, содержащих 1-2 млрд. транзисторов, уже сегодня позволяет производить однокристальные вычислительные системы (как мультипроцессоры, так и мультикомпьютеры), объединяющие десятки процессорных модулей. Одним из примеров подобных СБИС-систем являются матричные мультикомпьютеры (ММК) TILE-Gx, выпускаемые фирмой Tilera. Межмодульное взаимодействие в СБИС ММК осуществляется через матричную коммуникационную среду (КС), связывающую четвёрки соседних модулей многоразрядными шинами. Передача данных через КС выполняется словами (пакетами) за 1 или несколько тактов, при этом взаимодействие несмежных модулей предполагает маршрутизацию пакетов через другие модули.
Одним из распространённых в ММК режимов межмодульного обмена является передача пакета от одного источника нескольким приёмникам. Такой режим лежит в основе реализации многих системных процедур и стандартных функций прикладного уровня (например: MPI_Bcast, MPI_Allreduce, MPI_Barrier) и обычно называется широковещательной передачей (вещанием). Вещание пакета можно выполнить путём его многократной выдачи источником и последующей маршрутизации с использованием известных алгоритмов организации попарного межмодульного обмена (например, алгоритма XY-маршрутизации). Такой подход весьма прост в реализации и инвариантен к форме области приёмников. В то же время он обусловливает резкий рост интенсивности потока пакетов в КС, что существенно увеличивает среднее время их передачи.
Известны алгоритмы вещания, обеспечивающие возможность трансляции одного и того же пакета нескольким приёмникам (multicast-алгоритмы). Требуемое множество приёмников в таких алгоритмах, как правило, задаётся двоичным вектором (маршрутным кодом). Его разрядность определяется длиной маршрута, соединяющего источник с наиболее удалённым приёмником, причём единичные компоненты вектора указывают на модули-приёмники, а нулевые маскируют остальные модули маршрута. Однако использование подобных вещательных алгоритмов в ММК из-за переменности длины маршрутного кода и ограниченной разрядности межмодульных шин не представляется возможным. Разработан ряд алгоритмов широковещательной передачи, не требующих явного задания множества приёмников в адресной части пакета. Подобные алгоритмы хорошо согласуются с особенностями архитектуры КС ММК, но применимы лишь к простым по форме (линейным) областям приёмников и теряют свою эффективность по сравнению с традиционным попарным обменом при усложнении формы областей.
Дополнительная сложность в организации вещательного обмена пакетами для СБИС ММК связана с необходимостью обхода неработоспособных областей кристалла, обусловленных производственными дефектами и отказами. Кроме того, при передаче пакетов следует учитывать принятые схемы резервирования и реконфигурации структуры мультикомпьютера. Например, в мультикомпьютерах со столбцом скользящего резерва, реализующих замещение дефектных модулей путём виртуального переназначения задач и реконфигурации логической структуры, необходимо принимать во внимание возможное несоответствие физических адресов процессоров их логическим адресам и выполнять вещание на множество логических приёмников.
Исходя из сказанного, актуальной является разработка новых подходов к организации широковещательной передачи пакетов в ММК, применимых к более сложным по форме областям приёмников (начиная с прямоугольных) и в то же время не требующих явного задания множества приёмников в адресной части пакета. При этом передача пакетов должна осуществляться с учётом возможного расхождения логических и физических адресов процессоров, возникающего в результате реконфигурации логической структуры мультикомпьютера.
Научно-технической задачей диссертации является разработка метода, алгоритма и аппаратных средств отказоустойчивой широковещательной передачи пакетов на прямоугольную область приёмников в логической структуре реконфигурируемых однокристальных матричных мультикомпьютеров, позволяющих снизить время передачи пакетов и уровень их потерь.
Объект исследования: коммуникационные средства реконфигурируемых однокристальных матричных мультикомпьютеров.
Предмет исследования: процессы, методы, алгоритмы и схемы устройств управления широковещательной передачей пакетов в реконфигурируемых однокристальных матричных мультикомпьютерах.
Диссертационная работа выполнена в рамках совместных НИР ОХП ОКБ «Авиаавтоматика» Курского ОАО «Прибор» и ГОУ ВПО КурскГТУ, а также в соответствии с планом НИР КурскГТУ по единому заказ-наряду Министерства образования и науки РФ в 2006-2009 годах.
Цель диссертации: уменьшение времени передачи пакетов и снижение уровня потерянных пакетов при реализации широковещательных режимов обмена данными в реконфигурируемых однокристальных матричных мультикомпьютерах на основе разработки метода, алгоритма и аппаратных средств отказоустойчивой широковещательной передачи пакетов на множество приёмников, образующих прямоугольную область в логической структуре мультикомпьютера.
Задачи исследований:
-
Выполнить сравнительный анализ известных методов, алгоритмов и аппаратных средств управления широковещательной передачей сообщений (пакетов) в мультикомпьютерах при наличии локальных неоднородностей в их физической структуре.
-
Создать метод управления широковещательной передачей пакетов на произвольное множество приёмников, образующих прямоугольную область в логической структуре реконфигурируемого однокристального ММК.
-
Синтезировать алгоритм управления широковещательной передачей пакетов на прямоугольную область приёмников в логической структуре ММК.
-
Разработать структурно-функциональную организацию аппаратных средств управления широковещательной передачей пакетов в составе КС мультикомпьютера, определить аппаратную сложность и избыточность предложенных схемных решений.
-
Оценить время передачи и уровень потерь пакетов в ММК при реализации широковещательной передачи в условиях наличия дефектов и отказов при различных вариантах их распределения в мультикомпьютере.
Научная новизна результатов диссертации:
-
Создан метод управления широковещательной передачей пакетов в реконфигурируемых однокристальных матричных мультикомпьютерах, отличающийся определением области приёмников тремя параметрами – шириной, высотой и направлением обхода, а также параллельной передачей пакета на каждом шаге маршрутизации на четвёрки соседних модулей с целью выбора текущего логического приёмника, и позволяющий реализовать однократную трансляцию пакета от источника в произвольную область приёмников прямоугольной формы в условиях наличия неоднородностей физической структуры мультикомпьютера при несоответствии физических и логических адресов процессорных модулей.
-
Синтезирован аппаратно-ориентированный алгоритм управления широковещательной передачей пакетов на прямоугольную область приёмников, новизна которого заключается в чередовании пошаговой передачи пакета в заданном направлении обхода области приёмников с его параллельным вещанием четвёркам логических приёмников на каждом шаге реализуемого маршрута, позволяющий уменьшить время передачи и уровень потерь пакетов в режиме вещания.
-
Разработана структурно-функциональная организация аппаратных средств управления широковещательной передачей пакетов, отличающаяся применением двух типов коммуникационно-вычислительных устройств, реализующих соответственно выбор направлений трансляции пакетов на уровне отдельных модулей и параллельное вещание пакетов на четвёрки соседних модулей, и обеспечивающая возможность построения высоконадёжной коммуникационной среды широковещательного обмена данными.
Достоверность результатов диссертации обеспечивается корректным и обоснованным применением положений и методов математической логики, теорий: множеств и графов, вероятностей и математической статистики, надёжности технических систем, систем и сетей массового обслуживания, проектирования ЭВМ и систем, а также подтверждается совпадением теоретических выводов с результатами имитационного моделирования.
Практическая ценность результатов диссертации:
-
Созданный алгоритм управления широковещательной передачей пакетов позволяет снизить время передачи пакетов в КС ММК при их вещании на прямоугольную область приёмников в среднем в 1,2 раза по сравнению с известным алгоритмом организации вещания пакетов на линейную область и уменьшить потери пакетов в среднем в 2,1 раза до уровня 0,5(±0,075)0,7(±0,105)% от общего числа сгенерированных пакетов.
-
Разработанная структурно-функциональная организация аппаратных средств позволяет строить высоконадежные коммуникационные среды СБИС-мультикомпьютеров, включающих до нескольких сотен процессорных модулей, в рамках ограничений существующей микроэлектронной элементной базы.
На защиту выносятся следующие научные результаты:
-
Метод управления широковещательной передачей пакетов в реконфигурируемых однокристальных ММК, отличающийся параллельной передачей пакета на каждом шаге маршрутизации на четвёрки соседних модулей и заданием области приёмников тремя параметрами – шириной, высотой и направлением обхода в логической структуре мультикомпьютера.
-
Аппаратно-ориентированный алгоритм управления широковещательной передачей пакетов в реконфигурируемых однокристальных ММК, отличающийся чередованием пошаговой передачи пакета в заданном направлении обхода области приёмников с его параллельным вещанием четвёркам соседних модулей на каждом шаге реализуемого маршрута с целью локализации корректного логического приёмника.
-
Структурно-функциональная организация аппаратных средств управления широковещательной передачей пакетов, сущность которой заключается в использовании двух типов коммуникационно-вычислительных устройств, реализующих выбор направлений трансляции пакетов отдельными модулями в соответствии с заданным алгоритмом маршрутизации и параллельное вещание пакетов на четвёрки соседних модулей с автоматическим выбором корректного логического приёмника.
-
Результаты оценки аппаратной сложности и избыточности схемных решений, полученные на основе подсчёта числа эквивалентных вентилей в составе функциональных схем разработанных устройств, демонстрирующие возможность построения на их основе коммуникационных средств мультикомпьютеров, содержащих до нескольких сотен процессорных модулей, при имеющихся ограничениях базиса СБИС, и показывающие, что избыточность предложенных схем линейно снижается с ростом размерности ММК и длины входных буферов.
-
Результаты оценки времени передачи пакетов и уровня их потерь в режиме вещания на прямоугольную область приёмников, полученные путём имитационного моделирования работы коллектива разработанных устройств в составе КС мультикомпьютера при различных вариантах распределения дефектов и отказов в ММК, демонстрирующие снижение времени передачи пакетов в режиме вещания на прямоугольную область приёмников по сравнению с алгоритмом вещания на линейную область в среднем в 1,2 раза и одновременное уменьшение числа потерянных пакетов в среднем в 2,1 раза до уровня 0,5(±0,075) 0,7(±0,105)% от общего числа сгенерированных пакетов.
Практическое использование результатов работы. Основные научные результаты и выводы диссертационной работы внедрены в ООО «Сайнер-Курск» (г. Курск), а также используются в учебном процессе на кафедре вычислительной техники КурскГТУ в рамках дисциплин «Теоретические основы проектирования отказоустойчивых мультимикропроцессоров», «Отказоустойчивые многопроцессорные платформы», в курсовом и дипломном проектировании.
Апробация работы. Основные положения, результаты и выводы диссертации обсуждались и получили положительную оценку на III Международной научной конференции «Информационно-математические технологии в экономике, технике и образовании» (г. Екатеринбург, 2008 г.), XI Международной научно-технической конференции «Медико-экологические информационные технологии» (г. Курск, 2008 г.), VIII Международной научно-технической конференции «Оптико-электронные приборы и устройства в системах распознавания образов, обработки изображений и символьной информации» (г. Курск, 2008 г.), Всероссийской научно-технической конференции «Интеллектуальные и информационные системы» (г. Тула, 2009 г.), а также на научных семинарах кафедры вычислительной техники КурскГТУ в период с 2006 по 2009 год.
Публикации по теме диссертации. Содержание диссертации опубликовано в 8 работах, среди которых имеется 1 статья в научном издании по перечню ВАК Минобрнауки РФ, а также 1 свидетельство о Государственной регистрации программы для ЭВМ.
Личный вклад соискателя. Все выносимые на защиту научные результаты получены соискателем лично. В опубликованных в соавторстве работах по теме диссертации личный вклад соискателя сводится к следующему: в [1] разработан метод организации вещания пакетов при переразмещении задач в специализированном отказоустойчивом мультикомпьютере; в [2, 6] разработана методика, а также классы и функции для моделирования коммуникационных устройств вещания пакетов; в [3] выполнен сравнительный анализ алгоритмов отказоустойчивой маршрутизации; в [4] предложена структурно-функциональная организация коммуникационных устройств широковещательного обмена; в [5] определена процедура вещания координирующих пакетов в матричной структуре; в [7, 8] предложены схемные решения для оценки коммуникационных затрат.
Структура и объем диссертации. Работа состоит из введения, четырех глав, заключения, приложений и списка литературы, включающего 95 наименований. Диссертация содержит 186 страниц текста (включая 2 приложения) и поясняется 33 рисунками и 10 таблицами.
Области возможного использования. Результаты диссертационной работы могут быть использованы при построении высоконадежных многопроцессорных систем с регулярной топологической структурой, а также матричных локальных вычислительных сетей и кластеров высокой готовности.
