Аль-Ашвал Муджиб Мохаммед Яхья
МЕТОД, АЛГОРИТМ И УСТРОЙСТВА ОТКАЗОУСТОЙЧИВОЙ ШИРОКОВЕЩАТЕЛЬНОЙ ПЕРЕДАЧИ ПАКЕТОВ НА ПРЯМОУГОЛЬНУЮ ОБЛАСТЬ ПРИЕМНИКОВ В МАТРИЧНЫХ СБИС-МУЛЬТИКОМПЬЮТЕРАХ
Актуальность темы. Появление СБИС, содержащих 1-2 млрд. транзисторов, уже сегодня позволяет производить однокристальные вычислительные системы (как мультипроцессоры, так и мультикомпьютеры), объединяющие десятки процессорных модулей. Одним из примеров подобных СБИС-систем являются матричные мультикомпьютеры (ММК) TILE-Gx, выпускаемые фирмой Tilera. Межмодульное взаимодействие в СБИС ММК осуществляется через матричную коммуникационную среду (КС), связывающую четвёрки соседних модулей многоразрядными шинами. Передача данных через КС выполняется словами (пакетами) за 1 или несколько тактов, при этом взаимодействие несмежных модулей предполагает маршрутизацию пакетов через другие модули.
Одним из распространённых в ММК режимов межмодульного обмена является передача пакета от одного источника нескольким приёмникам. Такой режим лежит в основе реализации многих системных процедур и стандартных функций прикладного уровня (например: MPI_Bcast, MPI_Allreduce, MPI_Barrier) и обычно называется широковещательной передачей (вещанием). Вещание пакета можно выполнить путём его многократной выдачи источником и последующей маршрутизации с использованием известных алгоритмов организации попарного межмодульного обмена (например, алгоритма XY-маршрутизации). Такой подход весьма прост в реализации и инвариантен к форме области приёмников. В то же время он обусловливает резкий рост интенсивности потока пакетов в КС, что существенно увеличивает среднее время их передачи.
Известны алгоритмы вещания, обеспечивающие возможность трансляции одного и того же пакета нескольким приёмникам (multicast-алгоритмы). Требуемое множество приёмников в таких алгоритмах, как правило, задаётся двоичным вектором (маршрутным кодом). Его разрядность определяется длиной маршрута, соединяющего источник с наиболее удалённым приёмником, причём единичные компоненты вектора указывают на модули-приёмники, а нулевые маскируют остальные модули маршрута. Однако использование подобных вещательных алгоритмов в ММК из-за переменности длины маршрутного кода и ограниченной разрядности межмодульных шин не представляется возможным. Разработан ряд алгоритмов широковещательной передачи, не требующих явного задания множества приёмников в адресной части пакета. Подобные алгоритмы хорошо согласуются с особенностями архитектуры КС ММК, но применимы лишь к простым по форме (линейным) областям приёмников и теряют свою эффективность по сравнению с традиционным попарным обменом при усложнении формы областей (для просчёта алгоритмов можно использовать Онлайн калькулятор сложения и вычитания мартиц).
Дополнительная сложность в организации вещательного обмена пакетами для СБИС ММК связана с необходимостью обхода неработоспособных областей кристалла, обусловленных производственными дефектами и отказами. Кроме того, при передаче пакетов следует учитывать принятые схемы резервирования и реконфигурации структуры мультикомпьютера. Например, в мультикомпьютерах со столбцом скользящего резерва, реализующих замещение дефектных модулей путём виртуального переназначения задач и реконфигурации логической структуры, необходимо принимать во внимание возможное несоответствие физических адресов процессоров их логическим адресам и выполнять вещание на множество логических приёмников.
Исходя из сказанного, актуальной является разработка новых подходов к организации широковещательной передачи пакетов в ММК, применимых к более сложным по форме областям приёмников (начиная с прямоугольных) и в то же время не требующих явного задания множества приёмников в адресной части пакета. При этом передача пакетов должна осуществляться с учётом возможного расхождения логических и физических адресов процессоров, возникающего в результате реконфигурации логической структуры мультикомпьютера.
Научно-технической задачей диссертации является разработка метода, алгоритма и аппаратных средств отказоустойчивой широковещательной передачи пакетов на прямоугольную область приёмников в логической структуре реконфигурируемых однокристальных матричных мультикомпьютеров, позволяющих снизить время передачи пакетов и уровень их потерь.
Объект исследования: коммуникационные средства реконфигурируемых однокристальных матричных мультикомпьютеров.
Предмет исследования: процессы, методы, алгоритмы и схемы устройств управления широковещательной передачей пакетов в реконфигурируемых однокристальных матричных мультикомпьютерах.
Диссертационная работа выполнена в рамках совместных НИР ОХП ОКБ «Авиаавтоматика» Курского ОАО «Прибор» и ГОУ ВПО КурскГТУ, а также в соответствии с планом НИР КурскГТУ по единому заказ-наряду Министерства образования и науки РФ в 2006-2009 годах.
Цель диссертации: уменьшение времени передачи пакетов и снижение уровня потерянных пакетов при реализации широковещательных режимов обмена данными в реконфигурируемых однокристальных матричных мультикомпьютерах на основе разработки метода, алгоритма и аппаратных средств отказоустойчивой широковещательной передачи пакетов на множество приёмников, образующих прямоугольную область в логической структуре мультикомпьютера.
| автореферат |