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