一种以改变目标为策略的改进型三层通道布线算法

摘要

本文提出了一种改进型的三层通道布线算法——以改变目标为策略的三层通道布线算法.根据不同的布线问题,分别采用不同的布线方法,即首先从分析布线问题的最大垂直限制链长和最大通道密度出发,当以完成布线所需的通道数为最小作为目标时,采用HVH的三层通道布线算法;当以缩短最大垂直限制链长为目标时,采用HVH_m的布线算法.因此,它综合了曲干布线和直干布线两方面的优点,即不仅充分利用了通道区的空间,而且又一定程度地限制了导通孔数的增加.本算法已用FORTRAN语言编程实现,对引文中已发表的若干布线实例,都获得了较满意的结果.