Устранение уязвимости алгоритма PathFinder для программируемых чипов

Исследователи из EPFL, AMD и Университета Нови-Сада обнаружили фундаментальную неэффективность в алгоритме PathFinder, который десятилетиями использовался для программирования миллионов реконфигурируемых чипов по всему миру. Это открытие может изменить подход к проектированию и программированию будущих поколений FPGA.

Такие отрасли, как телекоммуникации, автомобилестроение, аэрокосмическая промышленность и физика элементарных частиц, активно используют программируемые вентильные матрицы (FPGA). В отличие от традиционных чипов, FPGA можно перенастраивать многократно, что делает их незаменимыми в динамичных сферах, где разработка специализированных чипов занимает годы и требует огромных затрат. Однако гибкость этих чипов имеет обратную сторону: их эффективность сильно зависит от программного обеспечения, используемого для программирования.

С конца 1990-х годов алгоритм PathFinder служил основой для маршрутизации FPGA. Его задача — соединять тысячи微小ых компонентов схемы без создания пересечений. Долгое время он работал настолько хорошо, что стал отраслевым стандартом. Но по мере увеличения сложности схем инженеры стали сталкиваться с замедлениями и occasionalными сбоями. Даже рабочие проекты иногда признавались «немаршрутизируемыми».

В своей работе, отмеченной наградой Best Paper на 33-м IEEE International Symposium on Field-Programmable Custom Computing Machines, исследователи раскрыли причины этих сбоев и предложили пути устранения ограничений PathFinder.

«На самом деле неудивительно, что PathFinder иногда терпит неудачу, — объясняет Шашват Шривастава, аспирант лаборатории PARSA и первый автор статьи. — Уже давно было показано, что проблема маршрутизации FPGA чрезвычайно сложна. Создатели оригинального алгоритма отмечали, что в практических сценариях такие случаи не должны возникать, но мы доказали обратное».

Стефан Николич, выпускник EPFL и ныне профессор Университета Нови-Сада, добавляет: «Когда алгоритм давал сбой,很少有人 заглядывали внутрь него. Вместо этого параметры tweaked, схемы модифицировали или переходили на более крупные FPGA».

Команда разработала framework для автоматического извлечения сложных задач из реальных схем. Наблюдая за тем, как PathFinder справляется с ними, исследователи обнаружили, что алгоритм часто строит избыточно большие деревья маршрутизации, увеличивая риск пересечений. Проблема кроется в порядке создания и добавления новых ветвей.

«В ретроспективе это кажется очевидным, но почему-то это упускалось из виду годами, — отмечает Шривастава. — Наше первое решение было простым: пробовать разные порядки и выбирать тот, который даёт наименьшее дерево. Экспериментально это сработало впечатляюще хорошо».

Миряна Стоилович, научный руководитель Шриваставы, подчёркивает важность сотрудничества с индустрией: «Без поддержки AMD, в лице Chirag Ravishankar и Dinesh Gaitonde, нам было бы гораздо сложнее добиться результатов, имеющих практическое значение».

Команда продолжает исследования, привлекая талантливых стажёров, и уверена, что их открытие повлияет на проектирование и программирование FPGA в будущем.