A Survey of Swarm Intelligence Techniques in VLSI Routing Problems <s> 1) LAYER ASSIGNMENT <s> This paper addresses a delay-driven layer assignment problem with consideration of via delay and coupling effect in the global routing stage. A negotiation-based framework is proposed to balance delay, congestion, and via count. Coupling capacitance is considered using a probabilistic look-up table. Finally, the proposed algorithm uses both parallel wires and wide wires to reduce wire delay. The effectiveness of our layer assignment algorithm is supported by extensive experimental results. <s> BIB001 </s> A Survey of Swarm Intelligence Techniques in VLSI Routing Problems <s> 1) LAYER ASSIGNMENT <s> As very large scale integration technology scales to deep submicrometer and beyond, interconnect delay greatly limits the circuit performance. The traditional 2-D global routing and subsequent net by net assignment of available empty tracks on various layers lacks a global view for timing optimization. To overcome the limitation, this paper presents a timing driven incremental layer assignment tool, to reassign layers among routing segments of critical nets and noncritical nets. Lagrangian relaxation techniques are proposed to iteratively provide consistent layer/via assignments. Modeling via min-cost flow for layer shuffling avoids using integer programming and yet guarantees integer solutions via uni-modular property of the inherent model. In addition, multiprocessing of ${K \times K}$ partitions of the whole chip provides runtime speed up. Furthermore, a slew targeted optimization is presented to reduce the number of violations incrementally through iteration-based Lagrangian relaxation, followed by a post greedy algorithm to fix local violations. Certain parameters introduced in the models provide tradeoff between timing optimization and via count. Experimental results in both ISPD 2008 and industry benchmark suites demonstrate the effectiveness of the proposed incremental algorithms. <s> BIB002
In recent years, the work of layer assignment not only aims at minimizing the number of vias, but further attempts to reduce the delay BIB002 , BIB001 . However, these works with considerations for delay optimization do not take into account the size of vias. It is assumed that the vias do not occupy routing resources and thus do not affect the routing of metal wires, which will seriously affect the accuracy of the final global routing results guiding for detailed routing. Existing research works on layer assignment either do not consider the delay problem, or the via size, which are far from the actual chip design requirements. After the introduction of the via-pillar process, the relevant routing model needs to consider the existence of via size, and the key performance index of delay optimization. Therefore, the existing layer assignment algorithms are no longer applicable to the problems under via-pillar process. And it is necessary to design a corresponding effective algorithm.