Efficient VLSI routing algorithm employing novel discrete PSO and multi-stage transformation
- PDF / 1,910,411 Bytes
- 16 Pages / 595.276 x 790.866 pts Page_size
- 21 Downloads / 159 Views
ORIGINAL RESEARCH
Efficient VLSI routing algorithm employing novel discrete PSO and multi‑stage transformation Genggeng Liu1 · Weida Zhu1 · Saijuan Xu2 · Zhen Zhuang1 · Yeh‑Cheng Chen3 · Guolong Chen1 Received: 28 July 2020 / Accepted: 29 October 2020 © Springer-Verlag GmbH Germany, part of Springer Nature 2020
Abstract For routing industrial circuits, the Steiner minimal tree (SMT) model can be applied in different routing problems, such as wirelength optimization, congestion reduction, and delay optimization. In this paper, an efficient VLSI routing algorithm employing novel discrete particle swarm optimization (PSO) and multi-stage transformation is proposed to build two types of SMT, including X-architecture Steiner minimal tree and rectilinear Steiner minimal tree. Firstly, to simultaneously handle two types of SMT problems, an effective encoding strategy is proposed to be more suitable for PSO and thus it can overcome the difficulty of designing different algorithms for different routing architectures. Secondly, a multi-stage transformation strategy is presented to expand the search space of the proposed algorithm and accelerate the convergence speed of the proposed algorithm. Various combinations of multi-stage transformation strategies have been tested to highlight the best combination. Furthermore, the various genetic operators combined with union-find data structure strategy are proposed to construct the novel and effective discrete particle update formula. Experimental simulation results on industrial circuits show that the proposed algorithm can get the best solutions among the existing algorithms. Keywords Particle swarm optimization (PSO) · Multi-stage transformation · Genetic operation · X-architecture Steiner minimal tree · Rectilinear Steiner minimal tree
1 Introduction Integrated circuit chip design includes mobile communication chip, Internet of things chip, RF chip, wireless connection chip, security chip, TV chip and other fields (Pan et al. 2019b; Chen et al. 2019b). Electronic design automation technology plays a very important role in the field of integrated circuit design, in which the routing problem is the key step to determine the final performance of the chip. The Steiner minimal tree (SMT) model can be applied in different routing problems, such as wirelength optimization, congestion reduction, and delay optimization. At present, most routing algorithms on industrial circuits were proposed for * Saijuan Xu [email protected] 1
College of Mathematics and Computer Sciences, Fuzhou University, Fuzhou, China
2
Department of Information Engineering, Fujian Business University, Fuzhou, China
3
Department of Computer Science, University of California, Davis, CA, USA
rectilinear architecture (Zhang et al. 2020; Liu et al. 2019; Siddiqi and Sait 2017). Those routing algorithms optimized the wire length and delay by optimizing the Steiner tree topology, changing the width of metal wire, inserting buffer and so on (Held et al. 2017; Dai et al. 2009, 2011; Chang et al. 20
Data Loading...
