Parallel algorithms for VLSI circuit extraction

The authors propose parallel algorithms to speedup the VLSI circuit extraction task. Given a VLSI layout as input, the problem of circuit extraction consists of determining the circuit connectivity and estimating the various electrical parameters such as the resistances of lines, capacitances of nodes, and dimensions of devices. Circuit extraction is a computationally intensive problem. The basic approach used in the parallel algorithms is the partitioning of a circuit into small regions, assigning each region to a processor and having the processors cooperate in performing the extraction procedures. The authors present a number of partitioning strategies that could be used. The authors have implemented the parallel algorithms on an Intel iPSC2 hypercube and an Encore 510 multimax shared memory multiprocessor