一个宏单元门阵上不等距网格的STEINER树算法...

摘要

在三级系统双层门阵MALS2总体布线中,我们采用不等距网格宏单元模式总体布线图、节点勾链数据结构来支持总体布线。改进了收敛点的获取算法,提出了收敛方向概念,在此基础上实现了一个并行定向搜索的STEINER树算法,该算法特点是,各个顶点独立且并行地依据收敛方向朝各自的收敛点逼近,经过逐次合并形成STEINER树。该算法运行于三级系统双层门阵MALS2中,结果证明,该算法复杂度低,收敛时间短,结果令人满意。