最小直线斯坦纳树及其在详细布线中的应用

在面向区域的详细布线中,最小直线斯坦纳树(MRST)可为单个线网产生满足连线最短要求的最佳初始布线模式,可为全局最优布线大大减小搜索空间。一般说,构造MRST是NP完备问题,为了降低问题的复杂度,需要研究生成MRST的实用有效算法。本文讨论了两种这样的算法,并结合例题说明,MRST只是局部最优树,在实际布线应用中要综合考虑其它布线质量因素,对当前线网的初始MRST进行调整或动态修改。