一个基于模拟进化的VLSI多层区域布线算法

A General VLSI Multi-layer Area Routing Algorithm Based on Simulated Evolution

提出了一个VLSI版图设计的多层区域详细布线算法。算法采用有网格顺序布线技术 ,先按线网权重从大到小的次序对线网逐个布线 ,若剩有不能布通的线网则采用拆线 -重布线 ,所有线网都布通后再利用拆线 -重布线策略对布线进行优化 ,拆线 -重布线的线网选择原则基于模拟进化技术 ,对单个线网使用改进型多层迷宫算法进行布线。算法可进行严格分层模式和非严格分层模式的布线 ,布线同时能进行通孔优化 ,能优先考虑关键线网的布线 ,并采取了减少串扰的措施。实验证明该算法能得到较好的布线结果。

This paper presents a VLSI multi-layer area detailed routing algorithm. The approach is based on a ripped-up and rerouted methodology using simulated evolution technique. The rip-up and reroute first finds a feasible initial solution, then optimizes the solution. For single net a modified Lee's maze algorithm is performed. In this area routing algorithm preferred wiring directions for each layer can be fixed or unfixed meanwhile stacked via is supported and via minimization is carried out as part of routing process, and critical nets are prior to be routed and crosstalk is taken into consideration. Experiments prove that the algorithm is effective.