摘要
在三级系统双层门阵MALS2总体布线中,我们采用不等距网格宏单元模式总体布线图、节点勾链数据结构来支持总体布线。改进了收敛点的获取算法,提出了收敛方向概念,在此基础上实现了一个并行定向搜索的STEINER树算法,该算法特点是,各个顶点独立且并行地依据收敛方向朝各自的收敛点逼近,经过逐次合并形成STEINER树。该算法运行于三级系统双层门阵MALS2中,结果证明,该算法复杂度低,收敛时间短,结果令人满意。
This paper studies the problem of Steiner tree algorithm in unequal grid of macro cell gate array, with the aim of speeding up the converge time and reducing complexity so as to obtain short length of Steiner tree. In this algorithm we improve the method of obtaining converge point and propose the concept of converge direction. Every special node goes torwards its converge point independently according to its converge direction. A Steiner tree is obrained through several merge and adjustment. This algorithm has been implemented in C on SUN4 work station and is utilized in double layer gate array of national 3 ICCAD system. The results shows this algorithm has lower complexity and the-length of Steiner tree is satisfactory.
出处
《计算机辅助设计与图形学学报》
EI
CSCD
1992年第4期63-67,25,共6页
Journal of Computer-Aided Design & Computer Graphics
关键词
门阵
树
收敛
不等距网格
STEINER
gate array, Steiner tree, converge point, converge direction.
