We developed a parallel bordered-block-diagonal (BBD) matrix solution for parallel circuit simulation. In parallel circuit sumulation on a MIMD parallel computer, a circuit is partitioned into as many subcircuits as the processors of a parallel computer. Circuit partition produce a BBD matrix. In parallel BBD matrix solution, diagonal blocks are easily solved separately in each processor. It is difficult, however, to solve the interconnection (IC) submatrix of a BBD matrix effectively in parallel. To make matters worse, the more a circuit is partitioned into subcircuits for highly parallel circuit simulation, the larger the size of an IC submatrix becomes. From an examination, we found that an IC submatrix is more dense (about 30% of all entries are non-zeros) than a normal circuit matrix, and the non-zeros per row in an IC submatrix are almost constant with the number of subcircuits. To attain high-speed circuit simulation, we devised a data structure for BBD matrix processing and an approach to parallel BBD matrix solution. Our approach solves the IC submatrix in a BBD matrix as well as the diagonal blocks in parallel using all processors. In this approach, we allocate an IC submatrix in block-wise order rather than in dot-wise order onto all processors. Thus, we balance the processor perfomance with the communication capacity of a parallel computer system. When we changed the block size of IC submatrix allocation from dot-wise order to 88 block-wise order, the 88 block-wise order allocation almost halved the matrix solution time. The parallel simulation of a sample circuit with 3277 transistors was 16.6 times faster than a single processor when we used 49 processors.

We have studied a circuit partitioning approach in the view of parallel circuit simulation on a MIMD parallel computer. In parallel circuit simulation, a circuit is partitioned into equally sized subcircuits while minimizing the number of interconnection nodes. Besides circuit partitioning time should be short enough compared with the total simulation time. From the details of circuit simulation time, we found that balancing subcircuits is critical for low parallel processing, whereas minimizing the interconnection nodes is critical for highly parallel processing. Our circuit partitioning approach consists of four steps： Grouping transistors, initial partitioning the transistor-groups, minimizing the number of interconnection nodes, and balancing the subcircuits. It is based on an algorithmic approach, and can directly control the tradeoffs between balancing subcircuits and minimizing the interconnection nodes by adjusting the parameters. We partitioned a test circuit with 3277 transistors into 4, 9, ... , 64 subcircuits, and did parallel simulations using PARACS, our parallel circuit simulator, on an AP1000 parallel computer. The circuit partitioning time was short enough-less than 3 percent of the total simulation time. The highest performance of parallel analysis using 49 processors was 16 times that of a single processor, and that for total simulation was 9 times.