Multilayer obstacle-avoiding x-architecture steiner minimal tree construction based on particle swarm optimization.

Area of Science:

• Electrical Engineering and Computer Science
• VLSI Design and Routing Algorithms

Background:

• Steiner Minimal Tree (SMT) is fundamental for Very Large Scale Integration (VLSI) routing.
• SMT applications include wire length optimization, congestion, and time delay estimation.
• Existing methods struggle with multilayer obstacle-avoiding routing.

Purpose of the Study:

• To develop an effective algorithm for constructing multilayer obstacle-avoiding X-architecture SMT (ML-OAXSMT).
• To improve routing efficiency and solution quality in VLSI design.
• To address the challenge of non-Manhattan architectures in chip design.

Main Methods:

• Particle Swarm Optimization (PSO) based algorithm.
• Pretreatment strategy to reduce routing condition judgments.
• Edge transformation and union-find partition for obstacle avoidance and solution validity.
• Edge-vertex encoding and a penalty mechanism for efficient routing and via reduction.

Main Results:

• The proposed algorithm effectively constructs ML-OAXSMT.
• Achieved superior solution quality from a global multilayer perspective.
• Demonstrated ability to bypass obstacles and reduce via generation.

Conclusions:

• The novel PSO-based algorithm provides an effective solution for ML-OAXSMT construction.
• Redefined edge cost and introduced obstacle-avoiding preferred direction X-architecture Steiner trees.
• Offers theoretical support for non-Manhattan architecture-based chip design.