Российский алгоритм ускорил поиск обходных маршрутов в чипах в 16,7…

Российский алгоритм ускорил поиск обходных маршрутов в чипах в 16,7 раза
Команды НИУ ВШЭ и Самарского университета представили алгоритм LRF-3D для многопроцессорных систем на кристалле. Он ищет обходные пути, когда часть узлов внутри чипа выходит из строя, и в тестах оказался в 16,7 раза быстрее классического A*, при этом точнее конкурирующих методов.

Задача выглядит абстрактно, но у неё вполне земная суть. В крупном чипе десятки вычислительных блоков соединены сетью на кристалле; отказ одного узла или канала не должен убивать всю систему — трафик просто нужно быстро пустить в обход. Чем быстрее считается новый маршрут, тем меньше просадка производительности.

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

Практическое применение — суперкомпьютеры и крупные дата-центры, где отказ отдельных элементов происходит регулярно и считается штатным событием, а не аварией. https://www.hse.ru/