重叠端口通道的四、五层布线算法

摘要

本文提出了一个重叠端口通道的四、五层布线算法.算法的目标是占用尽可能少的通道布线行数,为此算法中采用了扩展布线的概念,将部分线网分配到器件区域中进行布线.在通道内部布线时,引入了重叠端口通道的垂直约束矩阵的概念,并用它来指导启发式算法的线网布线顺序.算法在任何情况下都能保证布线的成功,从运行实例上来看,算法速度很快,而且结果都是近似最优的(或者是最优,或者是比最优解多一个布线行).