Обходной маршрут для чипов: алгоритм LRF-3D повышает надежность процессоров

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

Однако дефекты производства или естественный износ могут выводить из строя отдельные узлы сети, создавая тупиковые зоны. Чтобы система продолжала работать, необходимо заранее предусмотреть возможность обхода поврежденных участков.

Компромисс между точностью и скоростью

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

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

Как работает LRF-3D

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

Для проверки эффективности исследователи протестировали алгоритм в 36 сценариях, разбитых на пять категорий: лабиринты, коридоры, случайные сбои и другие. Результаты показали, что при доле неисправных узлов до 50% среднее отклонение длины пути LRF-3D от эталонного A* составляет всего 1,64%. Это более чем в 137 раз превосходит показатель алгоритма LOFT по качеству маршрута.

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

В планах авторов — проверка алгоритма на реальных микросхемах, а также оценка его влияния на энергопотребление и скорость передачи данных. Если тесты подтвердят ожидания, технология позволит создать более быстрые и надежные многопроцессорные системы для самых сложных условий эксплуатации.