Abstract:
With the dramatic increase of integrated circuit scale,the traditional global routing methods have become infeasible from the computability point of view.In this paper,the multi-terminal net routing problem is remodeled, a novel method for minimal rectangle Steiner tree construction is proposed, and a discrete particle swarm optimization with mutation to resolving minimum rectangular Steiner tree in very large scale integration global routing is presented (MDPSO -RA in short).In the improved discrete particle swarm optimization algorithm,a special encoding and several updating operations are adopted respectively and the mutation of genetic algorithm was introduced to improve the performance of particle swarm optimization on the foundation of its global optimization and fast convergence.The experimental results show that this method has the features of fast global optimization and great robustness,and it could fast get the optimal or approximate optimal multi-terminal interconnect topology within certain time.