基于自由分层的通道区布线算法

摘要

本文在分析线网之间关系的基础上提出了自由分层条件下的通道区布线模型:同层限制图 Gs,相交图 Gi。基于这一模型,分析了二层布线条件下对线网分层和布线序的基本限制,导出了分层的基本原则。在此基础上,分析了线网可 overlap 的性质和条件,从总体分析的思想出发,提出了直接以完成布线通道区所需面积最小化为目标的分层布线算法。实验结果表明,通道区布线面积和通孔的数目比基于横竖分层的布线算法有较大减少,对于Deutsch's difficult example,该算法获得18个 track 解。