X-architecture Steiner minimal tree algorithm based on multi-strategy optimization discrete differential evolution.

Area of Science:

• Computer Science
• Electrical Engineering
• Computational Mathematics

Background:

• Global routing is critical in Very Large Scale Integration (VLSI) design.
• The X-architecture Steiner minimal tree (XSMT) is an effective model for wire length optimization.
• Constructing XSMT is an NP-hard problem, necessitating advanced algorithmic approaches.

Purpose of the Study:

• To propose a novel algorithm, XSMT-MoDDE, for efficient XSMT construction in VLSI global routing.
• To enhance the performance of discrete differential evolution for solving the NP-hard XSMT problem.
• To achieve superior wire length optimization and solution quality for large-scale VLSI designs.

Main Methods:

• Developed an effective encoding strategy, fitness function, and population initialization for XSMT representation and evaluation.
• Implemented multi-strategy optimization within a discrete differential evolution framework, including elite selection, cloning, multiple mutations, and adaptive learning factors.
• Introduced a refining strategy to further enhance the quality of the generated Steiner trees.

Main Results:

• The proposed XSMT-MoDDE algorithm successfully generates XSMTs with significant wire length reduction.
• Experimental results demonstrate that XSMT-MoDDE achieves the shortest wire length reported to date for XSMT construction.
• The algorithm shows improved optimization degrees, particularly on larger-scale VLSI routing problems.

Conclusions:

• XSMT-MoDDE provides an effective and efficient solution for the NP-hard XSMT problem in VLSI global routing.
• The multi-strategy optimization discrete differential evolution approach significantly enhances the performance of Steiner minimal tree generation.
• The algorithm offers a state-of-the-art method for achieving optimal wire length and high-quality routing solutions in complex VLSI designs.