OrthoRoute: FPGA-алгоритм PathFinder пересадили в KiCad-автотрассировщик на GPU
Backplane размером 200×160 мм с 8192 цепями потребовал 32 сигнальных слоя, 44 233 глухих и скрытых перехода и 68 975 сегментов дорожек. OrthoRoute получил такую топологию за 41 час на NVIDIA A100 с 80 ГБ памяти, применив к печатной плате итеративный алгоритм распределения ресурсов из FPGA. Цена связности оказалась технологической: результат ещё содержит нарушения геометрических правил и требует ручной доводки.
Проект OrthoRoute показал практическое применение FPGA-маршрутизатора PathFinder к плотной многослойной печатной плате в KiCad. Разработчик Brian Benchoff использовал его для backplane с 16 разъёмами по 1100 контактов: плата содержит 17 600 площадок и 8192 электрические цепи. По опубликованному логу, полный маршрут занял 41 час на арендованном ускорителе NVIDIA A100 с 80 ГБ видеопамяти. Пиковая потребность достигла 33.5 ГБ.
Геометрия задачи далека от привычной автотрассировки двух- или четырёхслойной платы. OrthoRoute строит Manhattan lattice: на одном сигнальном слое разрешено горизонтальное движение, на соседнем — вертикальное. Изменение направления требует межслойного перехода. Для тестового backplane получились 32 слоя, 44 233 blind/buried via и 68 975 сегментов. Такая структура хорошо ложится на регулярные зоны BGA и разъёмные поля, где число потенциальных пересечений быстро становится главным ограничением.
В основе лежит PathFinder, опубликованный для FPGA ещё в 1995 году. В этой модели дорожки, точки пересечения и via представлены общими ресурсами графа. Каждая цепь прокладывается по пути с минимальной текущей стоимостью. Если несколько цепей заняли один ресурс, штраф за перегрузку увеличивается на следующей итерации. Отдельно накапливается history cost: ресурс, регулярно становящийся узким местом, остаётся дорогим даже после временного освобождения. Итерации продолжаются до исчезновения конфликтов либо до достижения предельного числа проходов.
Для PCB такая схема требует настройки нескольких конфликтующих параметров. Слабый штраф оставляет переполненные участки графа, чрезмерный вызывает oscillation: группы цепей синхронно уходят с перегруженного участка и создают следующий затор рядом. Размер hotset, то есть набора цепей для повторной прокладки, влияет и на скорость, и на устойчивость сходимости. Полная перетрассировка слишком затратна, однако малый hotset может закрепить локально плохое решение.
GPU в OrthoRoute не выполняет одновременную трассировку тысяч nets. Цепи проходят через общую карту congestion последовательно, сохраняя порядок переговорного маршрутизатора. Ускоритель применяется к наиболее тяжёлой операции внутри маршрута одной цепи: поиску кратчайшего пути SSSP, реализованному как параллельный вариант Dijkstra через CUDA и CuPy. Это различие существенно для оценки производительности: память нужна для крупного графа и рабочих массивов поиска, а не для массово независимой укладки всей netlist.
Сравнение с FreeRouting приведено автором как ориентир для конкретной топологии: за 7 часов тот проложил около 4% соединений. Абсолютные показатели OrthoRoute также относятся к одному авторскому запуску и пока не подтверждены независимым набором тестов. Проект опубликован под лицензией MIT и подключается к KiCad через IPC API, однако ранняя версия прямо обозначалась как pre-alpha.
Полученная топология не является готовым производственным выпуском. Escape-планировщик допускает нарушения строгого DRC из-за геометрических ограничений, а в маршруте остаются отдельные overlap. После автотрассировки потребуются проверка правил конкретного производства, контроль стекапа, анализ SI/PI и ручная разводка чувствительных ВЧ-цепей. Отдельный риск создаёт сама структура результата: десятки тысяч глухих и скрытых переходов существенно усложняют изготовление, контроль качества и стоимость платы. OrthoRoute поэтому относится к классу специализированных инструментов для регулярных сверхплотных backplane и BGA-escape, где цена вычислений может быть оправдана сокращением ручной работы.