This dissertation presents a number of extensions and applications of multilevel hypergraph-partitioning algorithms for solving some of the emerging, as well as the existing complex problems in the physical-design-automation phase of electronic circuit fabrication. The technology used in electronic circuit fabrication evolves very rapidly, and as a result, it presents a number of challenges in automating the tasks involved. The key challenges are in (i) devising scalable algorithms to handle exponentially increasing design sizes, (ii) devising new algorithms to effectively counter undesirable but inevitable effects associated with the shrinking geometries of electronic circuit manufacturing technologies, and (iii) devising algorithms to solve new problems that arise because of the evolving architectures of pre-fabricated chips, such as FPGAs. This dissertation advocates the use of multilevel hypergraph-partitioning algorithms, as the underlying tools to accommodate scalability requirements because of their availability, near-linear scalability and other desirable properties, such as cut quality of the solutions generated and run time. This dissertation identifies two new partitioning problems; minimizing maximum subdomain degree and cut of k-way partitioning and multi-resource aware partitioning, and proposes effective algorithms for solving them. In addition, this dissertation enhances the primary application of partitioning---placement---by proposing two inventions, namely "bounding box aware terminal propagation" and "perimeter-degree". These are used for improving the accuracy of the objective minimized in partitioning-driven placement methods and for identifying congestion prone clusters in multilevel placement algorithms, respectively.
展开▼
