Многопроцессорные системы на кристалле (МПСнК) — это электронные схемы, объединяющие тысячи вычислительных элементов в единую микросхему с помощью коммуникационной сети на чипе. Такие системы применяются для построения ЦОДов, суперкомпьютеров и ИИ-вычислений.
Дефекты производства или износ кристалла могут приводить к неисправностям отдельных узлов сети и образованию тупиковых зон. Поэтому еще на этапе проектирования МПСнК нужно предусмотреть обход таких зон.
Для передачи сигналов используются разные алгоритмы: глобальные способны найти оптимальный путь, но требуют информации о всей сети и высоких вычислительных мощностей. Локальные алгоритмы видят только ближайших соседей и потому часто строят избыточно длинные пути по сравнению с глобальными алгоритмами.
Исследователи предложили иерархию из восьми локальных алгоритмов, ключевым из которых является LRF-3D. Он оценивает функционирующих соседей и при попадании в локальный тупик делает шаг назад на предыдущую позицию, исключая заблокированное направление.
Чтобы подтвердить объективность оценок алгоритма, исследователи протестировали его при 36 сценариях, разбитых на пять функциональных категорий (включая лабиринты, коридоры и случайные сбои).
Эксперименты показали, что при доле неисправных узлов до 50% среднее отклонение длины пути алгоритма LRF-3D от эталонного A* составляет всего 1,64%, что превосходит показатели LOFT по качеству маршрута более чем в 137 раз. При плотности сбоев от 13 до 30% алгоритм успешно доставляет пакеты данных в 86% случаев. По быстродействию алгоритм LRF-3D принимает решения в 16,7 раза быстрее A* и в 22,5 раза быстрее LOFT.
«Мы планируем проверить алгоритм на реальных микросхемах и посмотреть, как он влияет на энергопотребление и скорость передачи данных. Если результаты тестов подтвердятся, технология поможет создать новое поколение многопроцессорных систем на кристалле, которые будут работать не только быстрее, но и значительно надежнее даже в сложных условиях», - отметил Александр Романов, один из авторов исследования, руководитель Учебной лаборатории систем автоматизированного проектирования МИЭМ ВШЭ.
Исходные коды алгоритмов и тестов опубликованы в открытом доступе.
Работа выполнена при поддержке Российского научного фонда (проект № 25-11-00248), результаты опубликованы в журнале IEEE Access.
