Analyzing Clustering and Partitioning Problems in Selected VLSI Models
- PDF / 2,302,794 Bytes
- 31 Pages / 439.642 x 666.49 pts Page_size
- 38 Downloads / 202 Views
Analyzing Clustering and Partitioning Problems in Selected VLSI Models Z. Donovan1,2 · K. Subramani3
· V. Mkrtchyan4
© Springer Science+Business Media, LLC, part of Springer Nature 2020
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-ofthe-art computer-aided design (CAD) tools. An old yet significant CAD problem for VLSI circuits is physical design automation. In physical design automation, we need 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 are several models for the clustering problem. In particular, we consider the problem of clustering without replication in combinatorial circuits with a view towards minimizing delay (CN). The corresponding problem with replication has been well-studied and solvable in polynomial time. However, replication can become expensive when it is unbounded. Consequently, CN is a problem worth investigating. We establish the computational complexities of several variants of CN. Additionally, we obtain approximability and inapproximability results for some NP-hard variants of CN. We also present approximation and exact exponential algorithms for some This article belongs to the Topical Collection: Special Issue on International Workshop on Combinatorial Algorithms (IWOCA 2019) Guest Editors: Charles Colbourn, Roberto Grossi, Nadia Pisanti This research was supported in part by the Air-Force Office of Scientific Research through Award FA9550-19-1-0177 and by the Air-Force Research Laboratory through Contract FA8750-17-S-7007. The work of the third author has been partially supported by the Italian MIUR PRIN 2017 Project ALGADIMAR “Algorithms, Games, and Digital Markets.” DISTRIBUTION A. Approved for public release: distribution unlimited. PA #: 88ABW-2020-1666 K. Subramani
[email protected] 1
West Virginia University, Morgantown, WV, USA
2
Air Force Research Laboratory, Information Directorate, Rome, NY, USA
3
LDCSEE, West Virginia University, Morgantown, WV, USA
4
Gran Sasso Science Institute, L’Aquila AQ, Italy
Theory of Computing Systems
variants of CN. We prove that for some cases there exists an approximation factor of strictly less than two and that our exact exponential algorithms beat brute force. Furthermore, we provide the first parameterized approximation algorithm in which the approximation ratio is also a parameter. Keywords Disjoint clustering · Delay minimization · VLSI design
1 Introduction In this paper, we focus on the problem of clustering without replication in combinatorial circuits for delay minimization. This problem is referred to as CN to indicate that logic replication is not allowed. Generally, it is not possible to place every circuit element in one chip because of various requirements and cons
Data Loading...
