Навигатор для процессоров: ученые разработали алгоритм, который находит путь в обход неисправных узлов

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

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

Для передачи сигналов используются разные алгоритмы: глобальные способны найти оптимальный путь, но требуют информации о всей сети и высоких вычислительных мощностей. Локальные алгоритмы видят только ближайших соседей и потому часто строят избыточно длинные пути по сравнению с глобальными алгоритмами.

Исследователи из Учебной лаборатории систем автоматизированного проектирования МИЭМ ВШЭ и Самарского университета предложили иерархию из восьми локальных алгоритмов, ключевым из которых является 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. Исходные коды алгоритмов и тестов опубликованы в открытом доступе.