超大规模集成电路(VLSI)中的详细布线是物理设计中一个重要且具有挑战性的环节.在这一阶段,所有导线的路径都会被确定下来,布线的优劣直接关系到芯片的面积和性能,路径搜索是布线中最为耗时的步骤之一.本文介绍了基于网格的布线模型,将布线问题抽象为一个图搜索问题或者多商品流问题;总结了迷宫搜索算法、A*算法、整数线性规划(ILP)算法和并行加速算法在路径搜索中的应用和针对设计约束作出的优化,结合在布线器中应用情况分析其优劣;总结回顾了基于机器学习求解算法的研究进展,分析了存在的问题,并对详细布线算法的发展趋势做了展望.分析表明,A*算法在布线质量、稳定性和速度等方面的综合性能较其他算法更为优异,其难点在于设计合理的布线排序策略和图模型.强化学习具有巨大的研究潜力,目前的研究仅在规模较小的设计中测试,仍需要进一步改进和探索.
详细布线 机器学习 强化学习 迷宫搜索 整数线性规划