A Parallel Algorithm For Hierarchical Circuit Extraction

In ICCAD88, 89, we proposed efficient parallel algorithms to speed up the task of VLSI circuit extraction on distributed memory multiprocessors. The input to the algorithms is a flat description of the circuit, in terms of the rectangles in different layers. In this paper, we describe an algorithm that combines the benefits of hierarchical analysis and parallelism. The input is a hierarchical description of the circuit. Towards this goal, we formulate and solve a general problem in scheduling. The parallel algorithm for hierarchical circuit extraction has been implemented on an Encore shared memory multiprocessor. 1. INTRODUCTION Given a set of rectangles in different mask levels for a VLSI layout as the input, a circuit extractor determines the circuit connectivity and estimates various electrical parameters such as the resistances of lines, capacitances of nodes, and dimensions of transistors. There are two disjoint, but orthogonal, approaches to speed up circuit extraction. The fir..