Geometric partitioning for parallelizing post-placement VLSI design processes.
Kim, Jiyoun
2006
Abstract
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 <bold> 2-weight geometric load balancing</bold> 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 2<italic><super>p</super></italic>-way partitioning based on the recursive application of our bipartitioning algorithm. Our heuristic runs in <italic>O</italic>(<italic>pn</italic> + n ·2<italic><super>p</super></italic>) time, where <italic> n</italic> 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 <bold>multi-session partitioning</bold> 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.Subjects
Design Geometric Load Balancing Parallelizing Partitioning Placement Post Postplacement Processes Vlsi
Types
Thesis
Metadata
Show full item recordCollections
Remediation of Harmful Language
The University of Michigan Library aims to describe library materials in a way that respects the people and communities who create, use, and are represented in our collections. Report harmful or offensive language in catalog records, finding aids, or elsewhere in our collections anonymously through our metadata feedback form. More information at Remediation of Harmful Language.
Accessibility
If you are unable to use this file in its current format, please select the Contact Us link and we can modify it to make it more accessible to you.