Ученые из МИЭМ ВШЭ и Самарского университета создали алгоритм LRF-3D для автоматического обхода неработающих узлов в трехмерных сетях на кристалле. Благодаря своей иерархической организации он превосходит аналоги по быстродействию и точности пути, повышая надежность процессоров для использования в ЦОД, суперкомпьютерах и ИИ-вычислениях.

Многопроцессорные системы на кристалле (МПСнК) — это электронные схемы, объединяющие тысячи вычислительных элементов в единую микросхему с помощью коммуникационной сети на чипе. Такие системы применяются для построения центров обработки данных (ЦОД), суперкомпьютеров и ИИ-вычислений. 

Дефекты производства или износ кристалла могут приводить к неисправностям отдельных узлов сети и образованию тупиковых зон. Поэтому еще на этапе проектирования МПСнК нужно предусмотреть обход таких зон. 

Для передачи сигналов используются разные алгоритмы: глобальные способны найти оптимальный путь, но требуют информации о всей сети и высоких вычислительных мощностей. Локальные алгоритмы видят только ближайших соседей и потому часто строят избыточно длинные пути по сравнению с глобальными алгоритмами. Исследователи из Учебной лаборатории систем автоматизированного проектирования МИЭМ ВШЭ и Самарского университета предложили иерархию из восьми локальных алгоритмов, ключевым из которых является LRF-3D. Он оценивает функционирующих соседей и при попадании в локальный тупик делает шаг назад на предыдущую позицию, исключая заблокированное направление.

Исследователи выяснили, что процесс подбора этих маршрутов можно ускорить в 16-22 раза, если использовать для проектирования сетей разработанный ими подход, который опирается в своей работе на восемь более простых и быстродействующих локальных алгоритмов. Подобные подходы в прошлом строили избыточно длинные пути по сравнению с глобальными алгоритмами, однако исследователям из России удалось решить эту проблему, объединив восемь разработанных ими ранее локальных подходов

Эксперименты показали, что при доле неисправных узлов до 50% среднее отклонение длины пути алгоритма LRF-3D от эталонного A* составляет всего 1,64%, что превосходит показатели LOFT по качеству маршрута более чем в 137 раз. При плотности сбоев от 13 до 30% алгоритм успешно доставляет пакеты данных в 86% случаев. По быстродействию алгоритм LRF-3D принимает решения в 16,7 раза быстрее A* и в 22,5 раза быстрее LOFT.