Research On Circuit Partitioning Methodology Based On Graph Algorithms

The circuit partitioning methodology is the technique to partition a large circuit system to numbers of subsystems based on some partitioning criterions by using the divide-and-conquer method. The technique include three aspect problems: The first one is representation of the topology of the circuit system, The second one is the problem of partitioning criterions, and the third one is the specific partitioning method based on the partitioning criterions. And the circuit partitioning technique can be used in the circuit simulating, circuit fault location and the resource allocation widely.The circuit partitioning problem could be modeled as the graph partitioning problem.And for the representation of the electrical topology, we introduce the graph and hypergraph models of the electrical interconnection based on the previous research of circuit partitioning.And using the sparse matrix storage technology and balance search tree to store the circuit topology. We also introduce some partitioning criterions in the different application background.The article also proposes a hierarchical clustering methodology in the specific circuit partitioning problems, and introduces the iterative improvement partitioning strategies based on the circuit traits and partitioning target with the graph and hypergraph models. Also we present a hash strategy which develops the efficiency for obtaining the best node pair to swap in iterative improvement partitioning strategies. At last, for solving the problem that conventional iterative improvement strategy may fall into local minima, we propose an improvement strategy based on simulated annealing. The results obtained from using the criterions mentioned above show that the algorithms we proposed could meet the partitioning request and boost the quality of clustering.