36 сценариев для подтверждения
Разработан алгоритм, который позволит производить более надежные процессоры для центров обработки данных
Ученые из МИЭМ ВШЭ и Самарского университета создали алгоритм LRF-3D для автоматического обхода неработающих узлов в трехмерных сетях на кристалле. Благодаря своей иерархической организации он превосходит аналоги по быстродействию и точности пути, повышая надежность процессоров для использования в ЦОД, суперкомпьютерах и ИИ-вычислениях. Исходные коды алгоритмов и тестов опубликованы в открытом доступе.
Многопроцессорные системы на кристалле (МПСнК) — электронные схемы, объединяющие тысячи вычислительных элементов в единую микросхему с помощью коммуникационной сети на чипе. Такие системы применяются для построения центров обработки данных (ЦОД), суперкомпьютеров и ИИ-вычислений.
Фото: Евгений Разумный / Коммерсантъ
Фото: Евгений Разумный / Коммерсантъ
Дефекты производства или износ кристалла могут приводить к неисправностям отдельных узлов сети и образованию тупиковых зон. Поэтому еще на этапе проектирования МПСнК нужно предусмотреть обход таких зон.
Для передачи сигналов используются разные алгоритмы. Глобальные алгоритмы способны найти оптимальный путь, но требуют информации обо всей сети и высоких вычислительных мощностей. Локальные видят только ближайших соседей и потому часто строят избыточно длинные пути по сравнению с глобальными алгоритмами.
Исследователи из учебной лаборатории систем автоматизированного проектирования МИЭМ ВШЭ и Самарского университета предложили иерархию из восьми локальных алгоритмов, ключевым из которых является 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.