Title :
Partitioning issues in circuit simulation on multiprocessors
Author :
Yeh, D.C. ; Rao, V.B.
Author_Institution :
Dept. of Electr. & Comput. Eng., Illinois Univ., Urbana, IL, USA
Abstract :
A decomposition technique known as node tearing is used to perform circuit simulation on a multiprocessor. The effect of partitioning the circuit on the final speedup achieved is considered. Using a very simple model for the LU decomposition time of sparse matrices, a circuit-partitioning problem based on node tearing is formulated to maximize speedup on a multiprocessor. An abstract hypergraph partitioning problem is then posed along with an algorithm for its solution. The original circuit partitioning problem is then transformed into an equivalent hypergraph partitioning problem, thereby generating partitions for the circuit. The effect of the tradeoff of circuit-partitioning time versus the number of available processors on the speedup factor is also studied.<>
Keywords :
circuit analysis computing; matrix algebra; multiprocessing systems; LU decomposition time; abstract hypergraph partitioning problem; circuit simulation; circuit-partitioning problem; circuit-partitioning time; decomposition technique; final speedup; multiprocessor application; node tearing; partitioning issues; simple model; sparse matrices; speedup factor; speedup maximization; Circuit simulation; Differential equations; Integrated circuit modeling; Integrated circuit reliability; Integrated circuit technology; Matrix decomposition; Nonlinear equations; Partitioning algorithms; Sparse matrices; Vectors;
Conference_Titel :
Computer-Aided Design, 1988. ICCAD-88. Digest of Technical Papers., IEEE International Conference on
Conference_Location :
Santa Clara, CA, USA
Print_ISBN :
0-8186-0869-2
DOI :
10.1109/ICCAD.1988.122515
