Semester
Fall
Date of Graduation
2018
Document Type
Dissertation
Degree Type
PhD
College
Statler College of Engineering and Mineral Resources
Department
Lane Department of Computer Science and Electrical Engineering
Committee Chair
K. Subramani
Committee Co-Chair
David W. Graham
Committee Member
David W. Graham
Committee Member
Vahan V. Mkrtchyan
Committee Member
Daryl S. Reynolds
Committee Member
Frances L. VanScoy
Abstract
As the modern integrated circuit continues to grow in complexity, the design of very large-scale integrated (VLSI) circuits involves massive teams employing state-of-the-art computer-aided design (CAD) tools. An old, yet significant CAD problem for VLSI circuits is physical design automation. In this problem, one needs to compute the best physical layout of millions to billions of circuit components on a tiny silicon surface. The process of mapping an electronic design to a chip involves several physical design stages, one of which is clustering. Even for combinatorial circuits, there exist several models for the clustering problem. In particular, we consider the problem of disjoint clustering in combinatorial circuits for delay minimization (CN). The problem of clustering with replication for delay minimization has been well-studied and known to be solvable in polynomial time. However, replication can become expensive when it is unbounded.
Consequently, CN is a problem worth investigating. In this dissertation, we establish the computational complexities of several variants of CN. We also present approximation and exact exponential algorithms for some variants of CN. In some cases, we even obtain an approximation factor of strictly less than two. Furthermore, our exact exponential algorithms beat brute force.
Recommended Citation
Donovan, Zola Nailah, "Algorithmic Issues in some Disjoint Clustering Problems in Combinatorial Circuits" (2018). Graduate Theses, Dissertations, and Problem Reports. 3721.
https://researchrepository.wvu.edu/etd/3721