Title :
An efficient partitioning algorithm for large-scale circuits
Author :
Hassoun, M.M. ; Lin, P.M.
Author_Institution :
Dept. of Electr. Eng. & Comput. Eng., Iowa State Univ., Ames, IA
Abstract :
A parallel circuit-partitioning algorithm aimed at minimizing the number of tearing nodes between subcircuits, the size of each subcircuit, or both, is presented. The algorithm is most suitable for circuit-simulation problems. It is currently implemented in a symbolic circuit simulator (SCAPP). The algorithm depends on the exploration of the coupling between the modified fundamental loops of the circuit. It recursively performs a hierarchical binary partitioning on the circuit and its subcircuits based on the concepts of loop index, tearing index, and branch index. Experimental results show the algorithm reaching optimum or better near-optimal solutions to problems for which existing algorithms failed or produced worse solutions
Keywords :
circuit analysis computing; digital simulation; large-scale systems; network topology; parallel algorithms; SCAPP; branch index; circuit-simulation problems; hierarchical binary partitioning; large-scale circuits; loop index; modified fundamental loops; near-optimal solutions; parallel circuit; partitioning algorithm; subcircuits; symbolic circuit simulator; tearing index; tearing nodes; Algorithm design and analysis; Circuit simulation; Circuit testing; Concurrent computing; Convergence; Coupling circuits; Integrated circuit interconnections; Large-scale systems; Partitioning algorithms; Upper bound;
Conference_Titel :
Circuits and Systems, 1990., IEEE International Symposium on
Conference_Location :
New Orleans, LA
DOI :
10.1109/ISCAS.1990.112495
