Geometric partitioning for parallelizing post-placement VLSI design processes.

Partitioning can speed up overlong VLSI design processes by enabling process parallelization. To achieve high parallel processing efficiency, partitioning schemes should minimize imbalance or interactions among partitions by relying on the specific characteristics of the given processes. In this dissertation, we present two partitioning methodologies for parallelizing post-placement VLSI optimization processes. Unlike pre-placement VLSI design tasks, post-placement processes manipulate circuit elements that have been assigned to physical spaces on the chip die. Consequently, physically neighboring circuit components may interact even when they are independent in the circuit netlist. To achieve high parallelism, partitioning methods must therefore take into consideration both logic and geometric interactions of circuit components. First we present a linear-time bipartitioning algorithm for the 2-weight geometric load balancing problem. This algorithm uses an L-shaped separator to bipartition a 2-weighted graph in 2-dimensional space so that each partition is spatially connected and each of the two weights is distributed with asymptotically vanishing relative imbalance. We also give an efficient heuristic for 2p-way partitioning based on the recursive application of our bipartitioning algorithm. Our heuristic runs in O(pn + n ·2p) time, where n is the graph size. In experiments with geometric graphs obtained from placed circuits, our partitioning heuristic achieves good balancing, fast runtime, and netcut sizes comparable to other partitioners. The second contribution of this dissertation is a multi-session partitioning scheme. This partitioning technique divides problem tasks into multiple sessions of parallel processes, so that interprocessor communication is entirely removed during each session. The algorithm is especially useful for parallelizing processes whose tasks are heavily connected to each other and may result in high communication overhead in parallel processing. We have developed a C++ version of our multi-session partitioning scheme and applied it to two post-placement VLSI processes with heavily overlapping tasks: electrical violation correction and post-placement timing optimization. In the parallelization of electrical violation correction, our scheme achieves speedups of up to 2.3x, dynamically utilizing 1--6 processors. For the process of post-placement timing optimization, we have developed a path-based buffer insertion algorithm and software. Our partitioning scheme speeds up the software execution time by up to 4.9x over serial processing, while dynamically utilizing 1--8 processors.Ph.D.Applied SciencesComputer scienceElectrical engineeringUniversity of Michigan, Horace H. Rackham School of Graduate Studieshttp://deepblue.lib.umich.edu/bitstream/2027.42/126195/2/3237997.pd