一个基于无约束通孔优化的双层布线算法—FOREST

A EFFICIENT TWO-LAYER ROUTER BASED ON UNCONSTRAINED VIA MINIMIZATION-FOREST

FOREST是一个立足于无约束通孔优化的新的布线算法,它从总体上将布线过程分为拓扑布线和物理布线两部分,并把两者视为相互联系的整体。作为一种启发式算法,它试图综合考虑布通率、布线空间、通孔数和连线总长等因素,算法打破横竖严格分层的限制,并允许不同层线段重叠,FOREST算法适用于一般的通道布线,特别是不规则边界的通道,一些实例的试算表明,FOREST算法具有较好的布线效果,尤其在减少通孔数上,取得了比较满意的结果。

FOREST is a new double-layer channel router based on Unconstrained Via Minimization. It partitions the routing procedure into two parts: Topological routing and Physical routing. As a heuristic algorithm, it tries to consider the routing completion rate, area, vias and wire length as a whole. It allows horizontal segments and vertical segments to route on one layer and allows over lapping of segments on different layers. FOREST is useful for general channels, especially for irregular channels. Some examples show that it is efficent, especially in reducing vias.