ABSTRACT Power-Aware Placement (2009)
Yongseok Cheon, Andrew B. Kahng, Sherief Reda
Lowering power is one of the greatest challenges facing the IC industry today. We present a power-aware placement method that simultaneously performs (1) activity-based register clustering that...
Abstract Copy Detection for Intellectual Property Protection of VLSI Designs* (2009)
Andrew B. Kahng, Darko Kirovski, Stefanus Mantik, Miodrag Potkonjak, Jennifer L. Wong
We give the first study of copy detection techniques for VLSI CAD applications; these techniques are complementary to pre-vious watermarking-based IP protection methods in finding and proving...
Practical Approximations of Steiner Trees in Uniform Orientation Metrics (2009)
Andrew B. Kahng, Ion Măndoiu, Er Zelikovsky
The Steiner minimum tree problem, which asks for a minimum-length interconnection of a given set of termi-nals in the plane, is one of the fundamental problems in Very Large Scale Integration (VLSI)...
Abstract GTX: The MARCO GSRC Technology Extrapolation System (2008)
Andrew E. Caldwell, Yu Cao, Andrew B. Kahng, Farinaz Koushanfar, Hua Lu, Igor L. Markov, ...
Technology extrapolation — the calibration and prediction of achievable design in future technology generations – drives the evolution of VLSI system architectures, design methodologies, and...
Abstract On the Bounded-Skew Clock and Steiner Routing Problems � (2008)
We study the minimum-cost bounded-skewrouting tree (BST) problem under the linear delay model. This problem captures several engineering tradeoffs in the design of routing topologies with controlled...
SMM: Scalable Analysis of Power Delivery Networks by Stochastic Moment Matching (2008)
Andrew B. Kahng, Bao Liu, Sheldon Tan
This paper proposes a novel method for analyzing large onchip power delivery networks via a stochastic moment matching (SMM) method. The proposed method extends the existing direct stochastic random...
Minimum-Buffered Routing of Non-Critical Nets forSlew Rate and Reliability Control \Lambda (2008)
Charles Alpert, Andrew B. Kahng, Bao Liu, Ion M, Er Zelikovsky
ffl We give linear-time algorithms for optimal buffering of a givenrouting tree with a single (inverting or non-inverting) buffer type. ffl For simultaneous routing and buffering with a single...
ABSTRACT Fill for Shallow Trench Isolation CMP (2008)
Andrew B. Kahng, Puneet Sharma, Er Zelikovsky
Shallow trench isolation (STI) is the mainstream CMOS isolation technology. It uses chemical mechanical planarization (CMP) to remove excess of deposited oxide and attain a planar surface for...
ABSTRACT Evaluation of Placer Suboptimality Via Zero-Change Netlist Transformations (2008)
In this paper we introduce the concept of zero-change transformations to quantify the suboptimality of existing placers. Given a netlist and its placement from a placer, we formally define a class of...
Area Fill Generation With Inherent Data Volume Reduction \Lambda (2008)
Yu Chen, Andrew B. Kahng, Gabriel Robins Alex, Er Zelikovsky, Yuhong Zheng
Quantifying error in dynamic power estimation of CMOS circuits (2008)
Conventional power estimation techniques are prone to many sources of error. With increasing dominance of coupling capacitances, capacitive coupling potentially contributes significantly to UDSM...
Jason Congt, Lei Het, Andrew B. Kahng, David Noice, Nagesh Shirali
This paper addresses post-routing capacitance extraction dur-ing performance-driven layout. We first show how basic drivers in process technology (planarization and minimum metal den-sity...
Multicommodity Flow Algorithms for Buffered Global Routing (2008)
Christoph Albrecht, Andrew B. Kahng, Ion Măndoiu, Er Zelikovsky
Due to delay scaling effects in deep-submicron technologies, interconnect planning and synthesis are becoming critical to meeting chip performance targets with reduced design turnaround time. In...
47.2 Robust IP Watermarlung Methodologies for Physical Design* (2008)
Andrew B. Kahng, Stefanus Mantik, Igor L. Markov, Miodrag Potkonjak, Paul Tuckert, Huijuan Wang, ...
Increasingly popular reuse-based design paradigms create a press-ing need for authorship enforcement techniques that protect the in-tellectual property rights of designers. We develop the first...
Abstract A System for Automatic Recording and Prediction of Design Quality Metrics (2008)
Andrew B. Kahng, Stefanus Mantik
We present recent extensions to METRICS [10] infrastructure that allow optimization of design processes at the flow level, rather than only at the individual tool level. As previously reported,...
ABSTRACT Impact of Interoperability on CAD-IP Reuse: An Academic Viewpoint (2008)
Mind-boggling complexity of EDA tools necessitates reuse of intellectual property in any large-scale commercial or academic operation. However, due to the nature of software, a tool component remains...
Abstract METRICS: A System Architecture for Design Process Optimization (2008)
Stephen Fenstermaker Y, David George Y, Andrew B. Kahng, Stefanus Mantik, Bart Thielges Y
We describe METRICS, a system to recover design productivity via new infrastructure for design process optimization. METRICS seeks to treat system design and implementation as a science,rather than...
Design Aids – Layout, Place and Route (2008)
Design rules in advanced IC manufacturing processes are increasingly problematic for modern router architectures and algorithms. This paper first reviews types and causes of “difficult ” design...
Abstract Evaluation of the New OASIS Format for Layout Fill Compression ∗ (2008)
Yu Chen, Andrew B. Kahng, Gabriel Robins, Er Zelikovsky, Yuhong Zheng
SIS) has been recently proposed for replacing the GDSII format. A primary objective of the new OASIS format is to enhance the compressibility of layout data. We compare the data compression...
On the Skew-Bounded Minimum-Buffer Routing Tree Problem (2008)
Christoph Albrecht, Andrew B. Kahng, Bao Liu, Ion I. Măndoiu, Er Z. Zelikovsky
Bounding the load capacitance at gate outputs is a standard element in today’s electrical correctness methodologies for high-speed digital VLSI design. Bounds on load caps improve coupling noise...
Detailed Placement for Leakage Reduction Using Systematic Through-Pitch Variation (2008)
Andrew B. Kahng, Swamy Muddu, Puneet Sharma
We present a novel detailed placement technique that accounts for systematic through-pitch variations to reduce leakage. Leakage depends nearly exponentially on linewidth (gate length), and even...
Wirelength Minimization for Min-Cut Placements via Placement Feedback (2008)
Andrew B. Kahng, Sherief Reda, Student Member
Abstract—The advent of strong multilevel partitioners has made top–down min-cut placers a favored choice for modern placer implementations. Terminal propagation is an important step in min-cut...
Swarup Acharya, Rafael Alonso, Michael J. Franklin, Stanley B. Zdonik, Pankaj Agarwal, Lars Arge, ...
145
Fast Yield-Driven Fracture for Variable Shaped-Beam Mask Writing (2008)
Andrew B. Kahng, Xu Xu, Alex Zelikovsky
Increasing transistor densities, smaller feature sizes, and the aggressive use of RET techniques with each successive process generation have collectively presented new challenges for current...
Abstract Copy Detection for Intellectual Property Protection of VLSI Designs (2008)
Andrew B. Kahng, Darko Kirovski, Stefanus Mantik, Miodrag Potkonjak, Jennifer L. Wong
We give the first study of copy detection techniques for VLSI CAD applications; these techniques are complementary to previous watermarking-based IP protection methods in finding and proving improper...
Andrew B. Kahng, Stefanus Mantik
The incremental, “construct by correction ” design methodology has become widespread in constraint-dominated DSM design. We study the problem of ECO for physical design domains in the general...
In VLSI design for testability, a scan chain is commonly used to connect the shift registers that store the input and output vectors during the testing phase of manufacturing. Registers in the scan...
Abstract Layout-Aware Scan Chain Synthesis for Improved Path Delay Fault Coverage ∗ (2008)
Puneet Gupta, Andrew B. Kahng, Ion Măndoiu, Puneet Sharma
Path delay fault testing becomes increasingly important due to higher clock rates and higher process variability caused by shrinking geometries. Achieving high-coverage path delay fault testing...
Yield- and Cost-Driven Fracturing for Variable Shaped-Beam (2008)
Andrew B. Kahng, Alex Zelikovsky C
Mask manufacturing for the approaching 90nm and 65nm nodes increasingly deploys variable shaped beam (VSB) mask writing machines. This has led to high interest in the fracturing methods which are at...
The Road Ahead Bringing down NRE (2008)
of design, ” pp. 136, 135), I highlighted today’s staggering levels of design nonrecurring engineering (NRE) costs, which routinely reach tens of millions of dollars. But manufacturing NRE, the...
Impact of Gate-Length Biasing on Threshold-Voltage Selection (2008)
Andrew B. Kahng, Swamy Muddu, Puneet Sharma
Gate-length biasing is a runtime leakage reduction technique that leverages on the short-channel effect by marginally increasing the gate-length of MOS devices to significantly reduce their leakage...
Statistical Gate Delay Calculation with Crosstalk Alignment Consideration ABSTRACT (2008)
We study gate delay variation caused by crosstalk aggressor alignment, i.e., difference of signal arrival times in coupled neighboring interconnects. This effect is as significant as multiple-input...
Lens Aberration Aware Placement for Timing Yield (2008)
Andrew B. Kahng, Chul-hong Park, Puneet Sharma, Qinke Wang
Process variations due to lens aberrations are to a large extent systematic, and can be modeled for purposes of analyses and optimiza-tions in the design phase. Traditionally, variations induced by...
Chaitanya Bandela, Ion I. Măndoiu, Yu Chen, Andrew B. Kahng, Alexander Zelikovsky
Abstract. Auctions and exchanges are one of the most important market mechanisms for price determination and allocation of goods. In this paper we consider the case when each buyer has a limited...
On Implementation Choices for Iterative Improvement Partitioning Algorithms (2008)
Iterative improvement partitioning algorithms such as the FM algorithm of Fiduccia and Mattheyses [8], the algorithm of Krishnamurthy [13], and Sanchis's extensions of these algorithms to...
Local Unidirectional Bias for Cutsize-Delay Tradeoff in Performance-Driven Bipartitioning (2008)
Abstract — Traditional multilevel partitioning approaches have shown good performance with respect to cutsize, but offer no guarantees with respect to system performance. Timing-driven partitioning...
ABSTRACT Power-Aware Placement (2008)
Yongseok Cheon, Pei-hsin Ho, Andrew B. Kahng, Sherief Reda, Qinke Wang
Lowering power is one of the greatest challenges facing the IC industry today. We present a power-aware placement method that simultaneously performs (1) activity-based register clustering that...
Abstract On Switch Factor Based Analysis of Coupled RC Interconnects (2008)
Andrew B. Kahng, Sudhakar Muddu, Egino Sarto
We revisit a basic element of modern signal integrity analysis, the modeling of worst-case coupling capacitance effects within a switch factor (SF) based methodology. We show that the exact SF is a...
On Implementation Choices for Iterative Improvement Partitioning Algorithms � (2008)
Iterative improvement partitioning algorithms such as those due to Fiduccia and Mattheyses �FM � �2 � and Krishnamurthy �5 � exploit an e�cient gain bucket data structure in selecting...
ABSTRACT Fill for Shallow Trench Isolation CMP (2008)
Andrew B. Kahng, Puneet Sharma, Er Zelikovsky
Shallow trench isolation (STI) is the mainstream CMOS isolation technology. It uses chemical mechanical planarization (CMP) to remove excess of deposited oxide and attain a planar surface for...
Abstract Noise Model for Multiple Segmented Coupled RC Interconnects (2008)
Andrew B. Kahng, Sudhakar Muddu, Niranjan Pol, Devendra Vidhani
Performance of high-speed VLSI circuits is increasingly limited by interconnect coupling noise. We present simple and improved analytical models for noise phenomena due to coupling capacitance. We...
Yu Chen, Andrew B. Kahng, Gabriel Robins
Control of variability in the back end of the line, and hence in interconnect performance as well, has become extremely difcult with the introduction of new materials such as copper and low-k...
A Placement Methodology for Global Interconnect Reduction and Its Impact on Performance (2008)
Andrew B. Kahng, Igor L. Markov, Sherief Reda
Global interconnects are a bottleneck in today’s high-performance deep sub-micron designs. In this paper, we propose a modification to the top-down min-cut placement algorithm to reduce the number...
Performance-Aware CMP Fill Pattern Optimization (2008)
Andrew B. Kahng, Rasit Onur Topaloglu
CMP fills are inserted to make metal density uniform and hence reduce post-polish height variations. Classical methods to insert fills focus on metal density uniformity, but do not take into...
ABSTRACT Performance-Impact Limited Area Fill Synthesis ∗ (2008)
Yu Chen, Puneet Gupta, Andrew B. Kahng
Chemical-mechanical planarization (CMP) and other manufacturing steps in very deep-submicron VLSI have varying effects on device and interconnect features, depending on the local layout density. To...
Submitted to IEEE Trans. on CAD An Analytical Delay Model for RLC Interconnects (2008)
Andrew B. Kahng, Sudhakar Muddu
Elmore delay has been widely used to estimate the interconnect delays in the performance-driven synthesis and layout of VLSI routing topologies. For typical RLC interconnections, Elmore delay can...
New Monte-Carlo Algorithms for Layout Density Control (2008)
Yu Chen, Andrew B. Kahng, Gabriel Robins Y, Er Zelikovsky Z
Abstract | Chemical-mechanical polishing (CMP) and other manufacturing steps in very deep submicron VLSI have varying e ects on device and interconnect features, depending on local characteristics of...
Control of variability in the back end of the line, and hence in interconnect performance as well, has become extremely difficult with the introduction of new materials such as copper and low-k...
Fast Dual Graph Based Hotspot Detection (2008)
As advanced technologies in wafer manufacturing push patterning processes toward lower-k1 subwavelength printing, lithography for mass production potentially suffers from decreased patterning...
Timing-driven steiner trees are (practically) free (2008)
Charles J. Alpert, Andrew B. Kahng, C. N. Sze, Qinke Wang
Traditionally, rectilinear Steiner minimum trees (RSMT) are widely used for routing estimation in design optimizations like floorplanning and physical synthesis. Since it optimizes wirelength, an...
Scalable heuristics for design of dna probe arrays (2008)
Andrew B. Kahng, Ion I. Măndoiu, Pavel A. Pevzner, Sherief Reda, Er Z. Zelikovsky
Design of DNA arrays for very large-scale immobilized polymer synthesis (VLSIPS) [10] seeks to minimize ef-fects of unintended illumination during mask exposure steps. Hannenhalli et al. [11]...
ABSTRACT Requirements for Models of Achievable Routing (2008)
Andrew B. Kahng, Stefanus Mantik
Models of achievable routing, i.e., chip wireability, rely on estimates of available and required routing resources. Required routing resources are estimated from placement, or (a priori) using...
Scalable heuristics for design of dna probe arrays (2008)
Andrew B. Kahng, Ion I. Măndoiu, Pavel A. Pevzner, Sherief Reda, Alexander Z. Zelikovsky
Design of DNA arrays for very large-scale immobilized polymer synthesis (VLSIPS) (Fodor et al., 1991) seeks to minimize effects of unintended illumination during mask exposure steps. Hannenhalli et...
Layout-aware scan chain synthesis for improved path delay fault coverage (2008)
Puneet Gupta, Andrew B. Kahng, Ion I. Măndoiu, Puneet Sharma
Abstract—Path delay fault testing has become increasingly important due to higher clock rates and higher process variability caused by shrinking geometries. Achieving high-coverage path delay fault...
Abstract The Y-Architecture for On-Chip Interconnect: Analysis and Methodology ∗ (2008)
Hongyu Chen, Chung-kuan Cheng, Andrew B. Kahng, Ion Măndoiu, Qinke Wang, Bo Yao
The Y-architecture for on-chip interconnect is based on pervasive use of 0-, 120-, and 240-degree oriented semi-global and global wiring. Its use of three uniform directions exploits on-chip routing...
1 Computer-Aided Optimization of DNA Array Design and Manufacturing (2008)
Andrew B. Kahng, Ion I. Măndoiu, Sherief Reda, Xu Xu, Alex Z. Zelikovsky
DNA probe arrays, or DNA chips, have emerged as a core genomic technology that enables cost-effective gene ex-pression monitoring, mutation detection, single nucleotide polymorphism analysis and...
Chapter 1 COMPUTER-AIDED OPTIMIZATION OF DNA ARRAY DESIGN AND MANUFACTURING (2008)
Andrew B. Kahng, Ion I. Măndoiu, Sherief Reda, Xu Xu, Alex Z. Zelikovsky
Abstract DNA probe arrays, or DNA chips, have emerged as a core genomic technology that enables cost-effective gene expression monitoring, mutation detection, single nucleotide polymorphism analysis...
General Terms Algorithms, Design (2008)
This invited paper offers “roadmap and vision ” for physical design. The main messages are as follows. (1) The high-level roadmap for physical design is static and well-known. (2) Basic problems...
Abstract Can Recursive Bisection Alone Produce Routable Placements? (2008)
Andrew E. Caldwell, Andrew B. Kahng, Igor L. Markov
This work focuses on congestion-driven placement of standard cells into rows in the fixed-die context. We summarize the stateof-the-art after two decades of research in recursive bisection placement...
Abstract Evaluation of the New OASIS Format for Layout Fill Compression ∗ (2008)
Yu Chen, Andrew B. Kahng, Gabriel Robins, Er Zelikovsky, Yuhong Zheng
SIS) has been recently proposed for replacing the GDSII format. A primary objective of the new OASIS format is to enhance the compressibility of layout data. We compare the data compression...
Analytical Optimization Of Signal Delays in VLSI Placement Abstract (2008)
Andrew B. Kahng, Igor L. Markov
In analytical placement, one seeks locations of circuit modules that optimize an objective function, but allows module overlaps. Our work introduces a novel minimization of maximal path delay that...
Control of variability in the back end of the line, and hence in interconnect performance as well, has become extremely difficult with the introduction of new materials such as copper and low-k...
Ross Baldick, Andrew B. Kahng, Andrew Kennings, Igor L. Markov
When minimizing a given objective function is challenging because of, for example, combinatorial complexity or points of nondi erentiability, one can apply more e cient and easier-to-implement...
Abstract Area Fill Generation With Inherent Data Volume Reduction (2008)
Yu Chen, Andrew B. Kahng, Gabriel Robins Alex, Er Zelikovsky, Yuhong Zheng
Control of variability and performance in the back end of the VLSI manufacturing line has become extremely difficult with the introduction of new materials such as copper and low-k dielectrics....
Abstract Hypergraph Partitioning With Fixed Vertices (2008)
Andrew E. Caldwell, Andrew B. Kahng, Igor L. Markov
We empirically assess the implications of fixed terminals for hypergraph partitioning heuristics. Our experimental testbed incorporates a leading-edge multilevel hypergraph partitioner [14] [3] and...
displayProductSummary.jsp?prodId=nPX5700. (2008)
Patrice Abry, Alan Allan, Don Edenfeld, William H. Joyner, Andrew B. Kahng, Bill St. Arnaud, ...
signaling enhancements and recovery techniques. IEEE Communications Mag-
Function Smoothing with Applications to VLSI Layout (2008)
Ross Baldick, Andrew B. Kahng, Andrew Kennings, Igor L. Markov
We presentapproximations to non-smooth continuous functions by di erentiable functions which are parameterized by a scalar> 0 and have convenient limit behavior as! 0. For standard numerical...
Faster Minimization of Linear Wirelength for Global Placement (2008)
A linear wirelength objective more e ectively captures timing, congestion, and other global placement considerations than a squared wirelength objective. The GORDIAN-L cell placement tool [19]...
Abstract GTX: The MARCO GSRC Technology Extrapolation System (2008)
Andrew E. Caldwell, Yu Cao, Andrew B. Kahng, Farinaz Koushanfar, Hua Lu, Igor L. Markov, ...
Technology extrapolation — the calibration and prediction of achievable design in future technology generations – drives the evolution of VLSI system architectures, design methodologies, and...
Analysis and Justication of a (2008)
Simple Practical Capacitance, Jason Cong Y, Lei He Y, Andrew B. Kahng, David Noice, Nagesh Shirali, ...
This paper addresses post-routing capacitance extraction during performance-driven layout. We #rst showhow basic drivers in process technology #planarization and minimum metal density requirements#...
On Mismatches Between Incremental Optimizers and Instance (2007)
Andrew B. Kahng, Stefanus Mantik
The incremental, "construct by correction " design methodology has become widespread in constraint-dominated DSM design. We study the problem of ECO for physical design domains in...
Jason Cong Y, Lei He Y, Andrew B. Kahng, David Noice, Nagesh Shirali
This paper addresses post-routing capacitance extraction during performance-driven layout. We rst show how basic drivers in process technology (planarization and minimum metal density requirements)...
Yu Chen, Andrew B. Kahng, Gabriel Robins, Alexander Zelikovsky
Abstract--- To improve manufacturability and performance predictability, we seek to make a layout uniform with respect to prescribed density criteria, by inserting "fill "...
Yu Chen, Andrew B. Kahng, Gabriel Robins, Alexander Zelikovsky
Abstract--- To improve manufacturability and performance predictability, we seek to make a layout uniform with respect to prescribed density criteria, by inserting "fill "...
Design Technology Productivity in the DSM Era (2007)
platforms, and applications markets. To correctly identify the design technology need, and to deliver this technology at the right time, the design technology community-- commercial vendors, captive...
A System for Automatic Recording and Prediction of Design Quality Metrics (2007)
Andrew B. Kahng, Stefanus Mantik
We present recent extensions to METRICS [10] infrastructure that allow optimization of design processes at the flow level, rather than only at the individual tool level. As previously reported,...
Feodor F. Dragan, Andrew B. Kahng, Sudhakar Muddu, Er Zelikovsky
Abstract---To implement high-performance global interconnect without impacting the placement and performance of existing blocks, the use of buffer blocks is becoming increasingly popular in...
Noise Model for Multiple Segmented Coupled RC Interconnects (2007)
Andrew B. Kahng, Sudhakar Muddu, Niranjan Pol, Devendra Vidhani
Performance of high-speed VLSI circuits is increasingly limited by interconnect coupling noise. We present simple and improved analytical models for noise phenomena due to coupling capacitance. We...
Yu Cao, Chenming Hu, Xuejue Huang, Andrew B. Kahng, Sudhakar Muddu, Dirk Stroobandt, ...
In this paper, we quantify the impact of global interconnect optimization techniques that address such design objectives as delay, peak noise, delay uncertainty due to noise, power, and cost. In...
Monte-Carlo Algorithms for Layout Density Control (2007)
Yu Chen Andrew, Yu Chen, Andrew B. Kahng, Gabriel Robins, Alexander Zelikovsky
Chemical-mechanical polishing (CMP) and other manufacturing steps in very deep submicron VLSI have varying effects on device and interconnect features, depending on local characteristics of the...
Analysis and Justification of a Simple, Practical 2 1/2-D Capacitance Extraction Methodology (2007)
Jason Cong, Lei He, Andrew B. Kahng, David Noice, Nagesh Shirali
This paper addresses post-routing capacitance extraction during performance-driven layout. We first show how basic drivers in process technology (planarization and minimum metal density requirements)...
Simple Eigenvector-Based Circuit Clustering Can Be Effective (2007)
Charles J. Alpert, Andrew B. Kahng
Clustering has proven effective in improving the quality of VLSI netlist partitioning and placement algorithms. A wide variety of clustering schemes have been proposed, including random walks [13],...
Optimal Algorithms for Substrate Testing in Multi-Chip Modules (2007)
Andrew B. Kahng, Gabriel Robins, Elizabeth A. Walkup
Multi-chip module (MCM) packaging techniques present several new technical challenges, notably substrate testing. We formulate MCM substrate testing as a problem of connectivity verification in trees...
New Analyses Of Distributed RC Interconnections (2007)
Andrew B. Kahng, Sudhakar Muddu
This paper gives new methods for calculating the time-domain response for a finite-length distributed RC line. We begin with the solution for diffusion in a semi-infinite distributed RC line [4, 12]...
Faster Minimization of Linear Wirelength for Top-Down Placement (2007)
Charles J. Alpert, Tony F. Chan, Andrew B. Kahng, Igor L. Markov, Pep Mulet, ...
Typical modern top-down placers solve recursively generated sparse systems of linear equations, where each system captures a one-dimensional placement problem with minimum squared wirelength...
Training Minimal Artificial Neural Network Architectures for Subsoil Object Detection (2007)
Kenneth D. Boese, Donald E. Franklin, Andrew B. Kahng
We cast the training of minimal artificial neural network architectures as a problem of global optimization, and study the simulated annealing (SA) global optimization heuristic under a...
Design Aids – Layout, Place and Route (2007)
Design rules in advanced IC manufacturing processes are increasingly problematic for modern router architectures and algorithms. This paper first reviews types and causes of “difficult ” design...
Abstract Area Fill Generation With Inherent Data Volume Reduction (2007)
Yu Chen, Andrew B. Kahng, Gabriel Robins Alex, Er Zelikovsky, Yuhong Zheng
Control of variability and performance in the back end of the VLSI manufacturing line has become extremely difficult with the introduction of new materials such as copper and low-k dielectrics....
Abstract GTX: The MARCO GSRC Technology Extrapolation System (2007)
Andrew E. Caldwell, Yu Cao, Andrew B. Kahng, Farinaz Koushanfar, Hua Lu, Igor L. Markov, ...
Technology extrapolation — the calibration and prediction of achievable design in future technology generations – drives the evolution of VLSI system architectures, design methodologies, and...
Abstract METRICS: A System Architecture for Design Process Optimization (2007)
Stephen Fenstermaker Y, David George Y, Andrew B. Kahng, Stefanus Mantik, Bart Thielges Y
We describe METRICS, a system to recover design productivity via new infrastructure for design process optimization. METRICS seeks to treat system design and implementation as a science,rather than...
Abstract On Switch Factor Based Analysis of Coupled RC Interconnects (2007)
Andrew B. Kahng, Sudhakar Muddu, Egino Sarto
We revisit a basic element of modern signal integrity analysis, the modeling of worst-case coupling capacitance effects within a switch factor (SF) based methodology. We show that the exact SF is a...
Abstract Can Recursive Bisection Alone Produce Routable Placements? (2007)
Andrew E. Caldwell, Andrew B. Kahng, Igor L. Markov
This work focuses on congestion-driven placement of standard cells into rows in the fixed-die context. We summarize the stateof-the-art after two decades of research in recursive bisection placement...
1 Area Fill Synthesis for Uniform Layout Density (2007)
Yu Chen, Andrew B. Kahng, Gabriel Robins, Er Zelikovsky
Abstract--- Chemical-mechanical polishing (CMP) and other manufacturing steps in very deep submicron VLSI have varying effects on device and interconnect features, depending on local characteristics...
Closing the Smoothness and Uniformity Gap in Area Fill Synthesis (2007)
Yu Chen, Andrew B. Kahng, Gabriel Robins, Alexander Zelikovsky
Control of variability in the back end of the line, and hence in interconnect performance as well, has become extremely difficult with the introduction of new materials such as copper and low-k...
Yu Chen, Andrew B. Kahng, Gabriel Robins, Alexander Zelikovsky
Chemical-mechanical planarization (CMP) and other manufacturing steps in very deep submicron VLSI have varying effects on device and interconnect features, depending on the local layout density. To...
Abstract Copy Detection for Intellectual Property Protection of VLSI Designs (2007)
Andrew B. Kahng, Darko Kirovski, Stefanus Mantik, Miodrag Potkonjak, Jennifer L. Wong
We give the first study of copy detection techniques for VLSI CAD applications; these techniques are complementary to previous watermarking-based IP protection methods in finding and proving improper...
Abstract Effective Iterative Techniques for Fingerprinting Design IP (2007)
Andrew E. Caldwell, Hyun-jin Choi, Andrew B. Kahng, Stefanus Mantik, Miodrag Potkonjak, Gang Qu, ...
While previous watermarking-based approaches to intellectual property protection (IPP) have asymmetrically emphasized the IP provider’s rights, the true goal of IPP is to ensure the rights of both...
Jason Cong, Lei He, Andrew B. Kahng, David Noice, Nagesh Shirali
This paper addresses post-routing capacitance extraction during performance-driven layout. We first show how basic drivers in process technology (planarization and minimum metal density requirements)...
Charles J. Alpert, Lars W. Hagen, Andrew B. Kahng
This work presents a genetic circuit partitioning algorithm that utilizes the Metis graph partitioning package originally designed for sparse matrix computations [16]. Metis is an extremely fast...
Delay Models for MCM Interconnects Under Monotone and Non-Monotone Response (2007)
Andrew B. Kahng, Kei Masuko, Sudhakar Muddu
Elmore delay has been extensively used for interconnect delay estimation because its simplicity of evaluation makes it appropriate for layout design. However, since Elmore delay does not take into...
The dissertation of Raffi Dionysian is approved. (2007)
Bruce Ho, Andrew B. Kahng, Lawrence Mcnamee, Kung Yao, Milos D. Ercegovac, Committee Chair
by
Efficient Analyses and Models of VLSI and MCM Interconnects (2007)
Andrew B. Kahng, Sudhakar Muddu
In performance-driven interconnect design, delay estimators are used to determine both the topology and the layout of good routing trees. We address the class of moment-matching methods used to model...
Jason Cong, Lei He, Andrew B. Kahng, David Noice, Nagesh Shirali
This paper addresses post-routing capacitance extraction during performance-driven layout. We first show how basic drivers in process technology (planarization and minimum metal density requirements)...
Feodor F. Dragan, Andrew B. Kahng, Ion I. M, Sudhakar Muddu, Alexander Zelikovsky
Abstract. We describe fully polynomial time approximation schemes for generalized multicommodity flow problems arising in VLSI applications such as Global Routing via Buffer Blocks (GRBB). We extend...
HDL lines total latency size (1000x) CPU comb. non-c. time (2007)
Ross Baldick, Andrew B. Kahng, Andrew Kennings, Igor L. Markov
When minimizing a given objective function is challenging because of, for example, combinatorial complexity or points of nondifferentiability, one can apply more efficient and easier-to-implement...
Analytical Optimization Of Signal Delays in VLSI Placement (2007)
Andrew B. Kahng, Igor L. Markov
In analytical placement, one seeks locations of circuit modules that optimize an objective function, but allows module overlaps. Our work introduces a novel minimization of maximal path delay that...
Simplex Solutions CAD-IP Bookshelf (2007)
Andrew E. Caldwell, Andrew B. Kahng, Igor L. Markov
medium for CAD-IP reuse, undertd auspices of tT Marco Gigascale Silicon ResearchCentr (htrchTW:WGSTIG:W:TtTtT Calledtl Marco GSRC Bookshelf,it serves as a clearinghouse and areposit0fi...
Provably Good Global Buffering by Generalized Multiterminal Multicommodity Flow Approximation (2007)
Feodor F. Dragan, Andrew B. Kahng, Ion I. Măndoiu, Sudhakar Muddu, Alexander Zelikovsky
Abstract—To implement high-performance global interconnect without impacting the placement and per-formance of existing blocks, the use of buffer blocks is becoming increasingly popular in...
A fast hierarchical quadratic placement algorithm (2006)
Gi-joon Nam, Sherief Reda, Student Member, Charles J. Alpert, Senior Member, Paul G. Villarrubia, ...
Abstract—Placement is a critical component of today’s physical-synthesis flow with tremendous impact on the final performance of very large scale integration (VLSI) designs. Unfortunately, it...
Efficient decoupling capacitor planning via convex programming methods (2006)
Achieving power/ground (P/G) supply signal integrity is crucial to success of nanometer VLSI designs. Existing P/G network optimization techniques are dominated by sensitivity based approaches. In...
Multicommodity Flow Algorithms for Buffered Global Routing (2005)
Albrecht, Christoph, Kahng, Andrew B., Mandoiu, Ion I., Zelikovsky, Alexander
In this paper we describe a new algorithm for buffered global routing according to a prescribed buffer site map. Specifically, we describe a provably good multi-commodity flow based algorithm that...
Architecture and details of a high quality, large-scale analytical placer (2005)
Andrew B. Kahng, Sherief Reda, Qinke Wang
Modern design requirements have brought additional complexities to netlists and layouts. Millions of components, whitespace resources, and fixed/movable blocks are just a few to mention in the list...
Compressible area fill synthesis (2005)
Yu Chen, Andrew B. Kahng, Gabriel Robins, Er Zelikovsky, Yuhong Zheng
Abstract—Control of variability and performance in the back end of the VLSI manufacturing line has become extremely difficult with the introduction of new materials such as copper and low-k...
Compressible area fill synthesis (2005)
Yu Chen, Andrew B. Kahng, Gabriel Robins, Er Zelikovsky, Yuhong Zheng
Control of variability and performance in the back end of the VLSI manufacturing line has become extremely difficult with the introduction of new materials such as copper and low-k dielectrics. To...
Yield-driven multi-project reticle design and wafer dicing (2005)
Andrew B. Kahng, Ion Măndoiu, Xu Xu, Alex Z. Zelikovsky
The pervasive use of advanced reticle enhancement technologies demanded by VLSI technology scaling leads to dramatic increases in mask costs. In response to this trend, multiple project wafers (MPW)...
Yield-driven multi-project reticle design and wafer dicing (2005)
Andrew B. Kahng, A Ion M, Alex Zelikovsky D
The aggressive scaling of VLSI feature size and the pervasive use of advanced reticle enhancement technologies has led to dramatic increases in mask costs, pushing prototype and low volume production...
Wafer topography-aware optical proximity correction for better DOF margin and CD control (2005)
Puneet Gupta, Andrew B. Kahng, Chul-hong Park, Kambiz Samadi, Xu Xu
Depth of focus is the major contributor to lithographic process margin. One of the major causes of focus variation is imperfect planarization of fabrication layers. Presently, OPC (Optical Proximity...
Digital Layout- Placement (2005)
Placement is an essential step in the physical design flow since it assigns exact locations for various circuit components within the chip’s core area. An inferior placement assignment will not...
Selective gate-length biasing for cost-effective runtime leakage control (2004)
Puneet Gupta, Andrew B. Kahng, Puneet Sharma, Dennis Sylvester
With process scaling, leakage power reduction has become one of the most important design concerns. Multi-threshold techniques have been used to reduce runtime leakage power without sacrificing...
Reticle Floorplanning With Guaranteed Yield for Multi-Project Wafers (2004)
With the dramatic increase in mask costs, multi-project wafers have became an attractive choice for low-volume chip fabrication. By using the same set of masks to fabricate a number of different...
Placement feedback: A concept and method for better min-cut placements (2004)
The advent of strong multi-level partitioners has made topdown min-cut placers a favored choice for modern placer implementations. We examine terminal propagation, an important step in min-cut...
Boosting: Min-Cut Placement with Improved Signal Delay (2004)
Andrew Kahng Cse, Andrew B. Kahng
In this work we improve top-down min-cut placers in the context of timing closure. Using the concept of boosting factors, we adjust net weights according to net spans, so as to reduce the quadratic...
Multi-project reticle floorplanning and wafer dicing (2004)
Andrew B. Kahng, Ion Măndoiu, Qinke Wang, Xu Xu, Alex Z. Zelikovsky
Multi-project Wafers (MPW) are an efficient way to share the rising costs of mask tooling between multiple prototype and low production volume designs. Packing the different die images on a...
Variability-driven considerations in the design of integrated-circuit global interconnects (2004)
Lei He, Andrew B. Kahng, King Ho Tam, Jinjun Xiong
Chemical-mechanical planarization (CMP) is an enabling technique to achieve uniformity of dielectric and conductor height in BEOL manufacturing processes. Dummy fill insertion improves the uniformity...
Combinatorial Group Testing Methods for the BIST Diagnosis Problem (2004)
Abstract — We examine an abstract formulation of BIST diagnosis in digital logic systems. The BIST diagnosis problem has applications that include identification of erroneous test vectors, faulty...
Implementation and extensibility of an analytic placer (2004)
Andrew B. Kahng, Ieee Qinke Wang, Student Member
Abstract — Automated cell placement is a critical problem in VLSI physical design. New analytical placement methods that simultaneously spread cells and optimize wirelength have recently received...
Optimal Planning for Mesh-Based Power Distribution (2004)
Hongyu Chen, Chung-kuan Cheng, Andrew B. Kahng, Makoto Mori, Qinke Wang
Abstract — Robust power distribution within available routing area resources is critical to chip performance and reliability. In this paper, we propose a novel and efficient method for optimizing...
On legalization of row-based placements (2004)
Cell overlaps in the results of global placement are guaranteed to prevent successful routing. However, common techniques for fixing these problems may endanger routing in a different way — through...
Asymmetric binary covering codes (2003)
Cooper, Joshua N., Ellis, Robert B., Kahng, Andrew B.
An asymmetric binary covering code of length n and radius R is a subset C of the n-cube Q_n such that every vector x in Q_n can be obtained from some vector c in C by changing at most R 1's of c to...
Improved a priori interconnect predictions and technology extrapolation in the GTX system (2003)
Yu Cao, Chenming Hu, Xuejue Huang, Andrew B. Kahng, Igor L. Markov, Michael Oliver, ...
are closely intertwined. Interconnect predictions are at the core of technology extrapolation models of achievable system power, area density and speed. Technology extrapolation, in turn, informs a...
Traditional multilevel partitioning approaches have shown good performance with respect to cutsize, but offer no guarantees with respect to system performance. Timing-driven partitioning methods...
Routing-aware scan chain ordering (2003)
Puneet Gupta, Andrew B. Kahng, Stefanus Mantik
Scan chain insertion can have a large impact on routability, wirelength and timing of the design. We present a routing-driven methodology for scan chain ordering with minimum wirelength objective. A...
The Y-Architecture for on-chip interconnect: Analysis and methodology (2003)
Hongyu Chen, Chung-kuan Cheng, Andrew B. Kahng, Ion Măndoiu, Qinke Wang, Bo Yao
The Y-architecture for on-chip interconnect is based on pervasive use of 0-, 120-, and 240-degree oriented semi-global and global wiring. Its use of three uniform directions exploits on-chip routing...
The Y-Architecture for on-chip interconnect: Analysis and methodology (2003)
Hongyu Chen, Chung-kuan Cheng, Andrew B. Kahng, Ion Măndoiu, Qinke Wang, Bo Yao
The Y-architecture for on-chip interconnect is based on pervasive use of 0-, 120-, and 240-degree oriented semi-global and global wiring. Its use of three uniform directions exploits onchip routing...
Hierarchical Whitespace Allocation in Top-down Placement (2003)
Andrew E. Caldwell, Andrew B. Kahng, Senior Member, Igor L. Markov
Abstract—Increased transistor density in modern commercial ICs typically originates in new manufacturing and defect prevention technologies [15], [16]. Additionally, better utilization of such...
Accurate Pseudo-Constructive Wirelength and Congestion Andrew B. Kahng (2003)
Accurate estimation of wirelength and congestion is one of the fundamental issues in VLSI physical design. Current probabilistic estimation methods fail to produce accurate results since they ignore...
A Novel Metric for Interconnect Architecture Performance (2003)
Parthasarathi Dasgupta Andrew, Andrew B. Kahng, Swamy Muddu
We propose a new metric for evaluation of interconnect architectures. This metric is computed by optimal assignment of wires from a given wire length distribution (WLD) to a given interconnect...
The Y-Architecture for on-chip interconnect: Analysis and methodology (2003)
Hongyu Chen, Chung-kuan Cheng, Andrew B. Kahng, Qinke Wang, Bo Yao, Student Member, ...
Abstract — The Y-architecture for on-chip interconnect is based on pervasive use of 0-, 120-, and 240-degree oriented semiglobal and global wiring. Its use of three uniform directions exploits...
Performance-impact limited area fill synthesis (2003)
Yu Chen, Puneet Gupta, Andrew B. Kahng
Chemical-mechanical planarization (CMP) and other manufacturing steps in very deep-submicron VLSI have varying effects on device and interconnect features, depending on the local layout density. To...
www.elsevier.com/locate/dsw Match twice and stitch:a new TSP tour construction heuristic
Q-Tree: A New Iterative Improvement Approach for Buffered Interconnect Optimization (2003)
The “chicken-egg ” dilemma between VLSI interconnect timing optimization and delay calculation suggests an iterative approach. We separate interconnect timing transformation as Hanan grafting and...
An algebraic multigrid solver for analytical placement with layout based clustering (2003)
Hongyu Chen, Chung-kuan Cheng, Nan-chi Chou, Andrew B. Kahng, John F. Macdonald, Peter Suaris, ...
An efficient matrix solver is critical to the analytical placement. As the size of the matrix becomes huge, the multilevel methods turn out to be more efficient and more scalable. Algebraic Multigrid...
Layout-aware scan chain synthesis for improved path delay fault coverage (2003)
Puneet Gupta, Andrew B. Kahng, Ion Măndoiu, Puneet Sharma
Path delay fault testing has become increasingly important due to higher clock rates and higher process variability caused by shrinking geometries. Achieving high-coverage path delay fault testing...
Layout-aware scan chain synthesis for improved path delay fault coverage (2003)
Puneet Gupta, Andrew B. Kahng, Ion Măndoiu, Puneet Sharma
Path delay fault testing has become increasingly important due to higher clock rates and higher process variability caused by shrinking geometries. Achieving high-coverage path delay fault testing...
Accurate pseudo-constructive wirelength and congestion estimation (2003)
Accurate estimation of wirelength and congestion is one of the fundamental issues in VLSI physical design. Current probabilistic estimation methods fail to produce accurate results since they ignore...
Toward better wireload models in the presence of obstacles (2002)
Chung-kuan Cheng, Andrew B. Kahng, Dirk Stroob
Abstract — Efficient and accurate interconnect estimation is crucial to design convergence. With System-on-Chip design, IP blocks form routing obstacles that cannot be accounted for by existing...
Area fill synthesis for uniform layout density (2002)
Yu Chen, Andrew B. Kahng, Gabriel Robins, Er Zelikovsky
Abstract — Chemical-mechanical polishing (CMP) and other manufacturing steps in very deep submicron VLSI have varying effects on device and interconnect features, depending on local characteristics...
Min-Max Placement for Large-Scale Timing Optimization (2002)
Andrew B. Kahng, Stefanus Mantik, Igor L. Markov
With feature-sizes below 0�25µm, interconnect delays account for over 40 % of worst delays [12]. Transitions to 0�18µm and 0�13µm further increase this figure, and thus the relative...
Area fill synthesis for uniform layout density (2002)
Yu Chen, Andrew B. Kahng, Gabriel Robins, Er Zelikovsky
Abstract — Chemical-mechanical polishing (CMP) and other manufacturing steps in very deep submicron VLSI have varying effects on device and interconnect features, depending on local characteristics...
Toward cad-ip reuse: The marco gsrc bookshelf of fundamental cad algorithms (2002)
Andrew E. Caldwell, Andrew B. Kahng, Igor L. Markov
Free reuse of code and other types of intellectual property in CAD can be in the mutual interests of commercial EDA vendors, captive CAD organizations, and academic researchers as they together...
Toward better wireload models in the presence of obstacles (2002)
Chung-kuan Cheng, Andrew B. Kahng, Bao Liu, Dirk Stroobandt
Abstract--- Efficient and accurate interconnect estimation is crucial to design convergence. With System-on-Chip design, IP blocks form routing obstacles that cannot be accounted for by existing a...
Min-Max Placement For Large-Scale Timing Optimization (2002)
Andrew Kahng Stefanus, Andrew B. Kahng, Stefanus Mantik, Igor L. Markov
At the 250nm technology node, interconnect delays account for over 40% of worst delays [12]. Transition to 130nm and below increases this figure, and hence the relative importance of timing-driven...
Min-Max Placement For Large-Scale Timing Optimization (2002)
Andrew Kahng Stefanus, Andrew B. Kahng, Stefanus Mantik, Igor L. Markov
At the 250nm technology node, interconnect delays account for over 40% of worst delays [12]. Transition to 130nm and below increases this figure, and hence the relative importance of timing-driven...
Toward better wireload models in the presence of obstacles (2002)
Chung-kuan Cheng, Andrew B. Kahng, Bao Liu, Dirk Stroob
Abstract — Efficient and accurate interconnect estimation is crucial to design convergence. With System-on-Chip design, IP blocks form routing obstacles that cannot be accounted for by existing a...
Min-Max Placement for Large-Scale Timing Optimization (2002)
Andrew B. Kahng, Stefanus Mantik, Igor L. Markov
At the 250nm technology node, interconnect delays account for over 40 % of worst delays [12]. Transition to 130nm and below increases this figure, and hence the relative importance of timing-driven...
Joshua N. Cooper, Robert B. Ellis, Andrew B. Kahng
An asymmetric binary covering code of length n and radius R is a subset C of the n-cube Qn such that every vector x ∈ Qn can be obtained from some vector c ∈ C by changing at most R 1’s of c to...
Non-tree routing for reliability and yield improvement (2002)
Andrew B. Kahng, Bao Liu, Ion I. Măndoiu
We propose to introduce redundant interconnects for manufacturing yield and reliability improvement. By introducing redundant interconnects, the potential for open faults is reduced at the cost of...
Non-tree routing for reliability and yield improvement (2002)
Andrew B. Kahng, Bao Liu, Ion I. Măndoiu
We propose to introduce redundant interconnects for manufacturing yield and reliability improvement. By introducing redundant interconnects, the potential for open faults is reduced at the cost of...
Toward better wireload models in the presence of obstacles (2002)
Chung-kuan Cheng, Andrew B. Kahng, Bao Liu, Dirk Stroob
Abstract — Wirelength estimation techniques typically contain a site density function that enumerates all possible path sites for each wirelength in an architecture and an occupation probability...
Toward cad-ip reuse: The marco gsrc bookshelf of fundamental cad algorithms (2002)
Andrew E. Caldwell, Andrew B. Kahng, Igor L. Markov
Free reuse of code and other types of intellectual property inCADcan be in the mutual interests of commercial EDA vendors, captive CAD organizations, and academic researchers as they together address...
Provably good global buffering by multiterminal multicommodity flow approximation (2001)
Feodor F. Dragan, Andrew B. Kahng, Sudhakar Muddu, Er Zelikovsky
Abstract—To implement high-performance global interconnect without impacting the placement and performance of existing blocks, the use of buffer blocks is becoming increasingly popular in...
Minimum-buffered routing of non-critical nets for slew rate and reliability control (2001)
Charles Alpert, Andrew B. Kahng, Bao Liu, Ion Măndoiu, Er Zelikovsky
In high-speed digital VLSI design, bounding the load capacitance at gate outputs is a well-known methodology to improve coupling noise immunity, reduce degradation of signal transition edges, and...
Interconnect implications of growth-based structural models for vlsi circuits (2001)
Chung-kuan Cheng, Andrew B. Kahng, Bao Liu
Power-law scaling phenomena that govern VLSI circuits have for several decades formed the foundation of VLSI interconnect estimation. This research investigates possible alternative power-law...
Toward Accurate Models of Achievable Routing (2001)
Andrew B. Kahng, Stefanus Mantik, Dirk Stroob
Abstract—Models of achievable routing, i.e., chip wireability, rely on estimates of available and required routing resources. Required routing resources are estimated from placement or (a priori)...
New graph bipartizations for doubleexposure, bright field alternating phase-shift mask layout (2001)
Andrew B. Kahng, Shailesh Vaya, Er Zelikovsky
Abstract — We describe new graph bipartization algorithms for layout modification and phase assignment of bright-field alternating phaseshifting masks (AltPSM) [25]. The problem of layout...
The Rent parameter has been widely used to characterize interconnect complexity of designs. The Rent power-law relationship is often used for aprioriwire estimation, which is an enabling component of...
Constraint-based watermarking techniques for design IP protection (2001)
Andrew B. Kahng, John Lach, Stefanus Mantik, Student Member, Igor L. Markov, ...
Abstract—Digital system designs are the product of valuable effort and know-how. Their embodiments, from software and hardware description language program down to device-level netlist and mask...
Interconnect implications of growth-based structural models for vlsi circuits (2001)
Chung-kuan Cheng, Andrew B. Kahng, Bao Liu
Power-law scaling phenomena that govern VLSI circuits have for several decades formed the foundation of VLSI interconnect estimation. This research investigates possible alternative power-law...
Toward Accurate Models of Achievable Routing (2001)
Andrew B. Kahng, Stefanus Mantik, Dirk Stroob
Abstract--- Models of achievable routing, i.e., chip wireability, rely on estimates of available and required routing resources. Required routing resources are estimated from placement, or (a priori)...
Andrew B. Kahng, Ryan Kastner, Stefanus Mantik, Sarrafzadeh Xiaojian Yang
The Rent parameter has been widely used to characterize interconnect complexity of designs. The Rent power-law relationship is often used for a priori wire estimation, which is an enabling component...
On the Relevance of Wire Load Models (2001)
Kenneth D. Boese, Andrew B. Kahng, Stefanus Mantik
Wire load models (WLMs) are generally perceived to be inaccurate and inadequate for good optimization. The traditional wisdom is that accuracy of WLMs will worsen as die sizes expand and feature...
Toward Accurate Models of Achievable Routing (2001)
Andrew B. Kahng, Stefanus Mantik, Dirk Stroob
Abstract--- Models of achievable routing, i.e., chip wireability, rely on estimates of available and required routing resources. Required routing resources are estimated from placement, or (a priori)...
New graph bipartizations for doubleexposure, bright field alternating phase-shift mask layout (2001)
Andrew B. Kahng, Shailesh Vaya, Er Zelikovsky
Abstract--- We describe new graph bipartization algorithms for layout modification and phase assignment of bright-field alternating phaseshifting masks (AltPSM) [25]. The problem of layout...
Limitations and Challenges of Computer-Aided Design Technology for CMOS VLSI (2001)
Randal E. Bryant, Kwang-Ting Cheng, Andrew B. Kahng, Kurt Keutzer, Wojciech Maly, Richard Newton
this paper, we explore limitations to how design technology can enable the implementation of single-chip microelectronic systems that take full advantage of manufacturing technology with respect to...
Constraint-based watermarking techniques for design IP protection (2001)
Andrew B. Kahng, John Lach, Stefanus Mantik, Student Member, Igor L. Markov, ...
Abstract—Digital system designs are the product of valuable effort and know-how. Their embodiments, from software and hardware description language program down to device-level netlist and mask...
Toward Accurate Models of Achievable Routing (2001)
Andrew B. Kahng, Stefanus Mantik, Dirk Stroob
Abstract | Models of achievable routing, i.e., chip wireability, rely on estimates of available and required routing resources. Required routing resources are estimated from placement, or (a priori)...
Admissibility Proofs for the LCS* Algorithm (2000)
Marcelo O. Johann, Andrew Caldwell, Andrew B. Kahng
Bidirectional search and heuristic search are techniques that improve the performance of a shortest path graph search. Despite many attempts to use both at the same time, this combination had been...
Wiring layer assignments with consistent stage delays (2000)
Andrew B. Kahng, Dirk Stroobandt Y
Wire sizing, repeater insertion and repeater sizing are necessary to limit delay in on-chip interconnections. When these techniques are applied to nets that are already routed, the results heavily...
Practical Iterated Fill Synthesis for CMP Uniformity (2000)
Yu Chen, Andrew B. Kahng, Gabriel Robins, Er Zelikovsky
We propose practical iterated methods for layout density control for CMP uniformity, based on linear programming, Monte-Carlo and greedy algorithms. We experimentally study the tradeoffs between two...
Practical Iterated Fill Synthesis for CMP Uniformity (2000)
Yu Chen, Andrew B. Kahng, Gabriel Robins, Er Zelikovsky
We propose practical iterated methods for layout density control for CMP uniformity, based on linear programming, Monte-Carlo and greedy algorithms. We experimentally study the tradeoffs between two...
Improved Algorithms for Hypergraph Bipartitioning (2000)
Andrew E. Caldwell, Andrew B. Kahng, Igor L. Markov
Multilevel Fiduccia-Mattheyses (MLFM) hypergraph partitioning [3, 22, 24] is a fundamental optimization in VLSI CAD physical design. The leading implementation, hMetis [23], has since 1997 proved...
Yu Cao, Chenming Hu, Xuejue Huang, Andrew B. Kahng, Sudhakar Muddu, Dirk Stroob, ...
In this paper, we describe optimization techniques to minimize important design objectives such as delay, peak noise, delay uncertainty due to noise, power, and cost. In doing so, we employ a new...
Wiring layer assignments with consistent stage delays (2000)
Andrew B. Kahng, Dirk Stroobandt
Wire sizing, repeater insertion and repeater sizing are necessary to limit delay in on-chip interconnections. When these techniques are applied to nets that are already routed, the results heavily...
On Switch Factor Based Analysis of Coupled RC Interconnects (2000)
Andrew B. Kahng, Sudhakar Muddu, Egino Sarto
We revisit a basic element of modern signal integrity analysis, the modeling of worst-case coupling capacitance effects within a switch factor (SF) based methodology. We show that the exact SF is a...
GTX: The MARCO GSRC Technology Extrapolation System (2000)
Andrew E. Caldwell, Yu Cao, Andrew B. Kahng, Farinaz Koushanfar, Hua Lu, Igor L. Markov, ...
Technology extrapolation --- the calibration and prediction of achievable design in future technology generations -- drives the evolution of VLSI system architectures, design methodologies, and...
Iterative Partitioning with Varying Node Weights (2000)
Andrew Caldwell Andrew, Andrew B. Kahng, Igor L. Markov
The balanced partitioning problem divides the nodes of a [hyper]graph into groups of approximately equal weight (i.e., satisfying balance constraints) while minimizing the number of [hyper]edges that...
Can Recursive Bisection Alone Produce Routable Placements? (2000)
Andrew E. Caldwell, Andrew B. Kahng, Igor L. Markov
This work focuses on congestion-driven placement of standard cells into rows in the fixed-die context. We summarize the state of -the-art after two decades of research in recursive bisection...
Classical Floorplanning Harmful? (2000)
Classical floorplanning formulations may lead researchers to solve the wrong problems. This paper points out several examples, including (i) the preoccupation with packing-driven, as opposed to...
METRICS: A System Architecture for Design Process Optimization (2000)
Stephen Fenstermaker, David George, Andrew B. Kahng, Stefanus Mantik, Bart Thielges
We describe METRICS, a system to recover design productivity via new infrastructure for design process optimization. METRICS seeks to treat system design and implementation as a science, rather than...
Provably Good Global Buffering Using an Available Buffer Block Plan (2000)
Feodor F. Dragan, Andrew B. Kahng, Ion Mandoiu, Ion M, Alexander Zelikovsky, Sudhakar Muddu, ...
To implement high-performance global interconnect without impacting the performance of existing blocks, the use of buffer blocks is increasingly popular in structured-custom and block-based ASIC/SOC...
Monte-Carlo Algorithms for Layout Density Control (2000)
Yu Chen, Andrew B. Kahng, Gabriel Robins, Alexander Zelikovsky
Chemical-mechanical polishing (CMP) and other manufacturing steps in very deep submicron VLSI have varying effects on device and interconnect features, depending on local characteristics of the...
Andrew B. Kahng, Stefanus Mantik
The incremental, "construct by correction" design methodology has become widespread in constraint-dominated DSM design. We study the problem of ECO for physical design domains in the...
Can Recursive Bisection Alone Produce Routable Placements? (2000)
Andrew Caldwell Andrew, Andrew B. Kahng, Igor L. Markov
This work focuses on congestion-driven placement of standard cells into rows in the fixed-die context. We summarize the stateof -the-art after two decades of research in recursive bisection placement...
Hypergraph Partitioning With Fixed Vertices (2000)
Charles Alpert Andrew, Andrew E. Caldwell, Andrew B. Kahng, Igor L. Markov
We empirically assess the implications of fixed terminals for hypergraph partitioning heuristics. Our experimental testbed incorporates a leading-edge multilevel hypergraph partitioner [12] [3] and...
Design and Implementation of Move-Based Heuristics for VLSI Hypergraph Partitioning (2000)
Andrew E. Caldwell, Andrew B. Kahng, Igor L. Markov
ing with credit is permitted. To copy otherwise, to republish, to post on servers, to redistribute to lists, or to use any component of this work in other works, requires prior specific permission...
Requirements for Models of Achievable Routing (2000)
Andrew B. Kahng, Stefanus Mantik, Dirk Stroobandt
Models of achievable routing, i.e., chip wireability, rely on estimates of available and required routing resources. Required routing resources are estimated from placement, or (a priori) using...
Wiring Layer Assignments with Consistent Stage Delays (2000)
Andrew B. Kahng, Dirk Stroobandt
Wire sizing, repeater insertion and repeater sizing are necessary to limit delay in on-chip interconnections. When these techniques are applied to nets that are already routed, the results heavily...
Practical Iterated Fill Synthesis for CMP Uniformity (2000)
Yu Chen, Andrew B. Kahng, Gabriel Robins, Alexander Zelikovsky
We propose practical iterated methods for layout density control for CMP uniformity, based on linear programming, Monte-Carlo and greedy algorithms. We experimentally study the tradeoffs between two...
Classical Floorplanning Harmful? (2000)
Classical floorplanning formulations may lead researchers to solve the wrong problems. This paper points out several examples, including (i) the preoccupation with packing-driven, as opposed to...
GTX: The MARCO GSRC Technology Extrapolation System (2000)
Andrew Caldwell Yu, Yu Cao, Andrew B. Kahng, Farinaz Koushanfar, Hua Lu, Igor L. Markov, ...
Technology extrapolation --- the calibration and prediction of achievable design in future technology generations -- drives the evolution of VLSI system architectures, design methodologies, and...
Provably Good Global Buffering Using an Available Buffer Block Plan (2000)
Feodor F. Dragan, Andrew B. Kahng, Ion Mandoiu, Sudhakar Muddu, Alexander Zelikovsky, Er Zelikovsky
To implement high-performance global interconnect without impacting the performance of existing blocks, the use of buffer blocks is increasingly popular in structured-custom and block-based ASIC/SOC...
Hypergraph partitioning with fixed vertices (2000)
Charles J. Alpert, Andrew E. Caldwell, Andrew B. Kahng, Igor L. Markov
We empirically assess the implications of xed terminals for hypergraph partitioning heuristics. Our experimental testbed incorporates a leading-edge multilevel hypergraph partitioner [12] [3] and...
Practical Iterated Fill Synthesis for CMP Uniformity (2000)
Yu Chen, Andrew B. Kahng, Gabriel Robins, Er Zelikovsky
We propose practical iterated methods for layout density control for CMP uniformity, based on linear programming, Monte-Carlo and greedy algorithms. We experimentally study the tradeoffs between two...
Improved Algorithms for Hypergraph Bipartitioning (2000)
Andrew E. Caldwell, Andrew B. Kahng, Igor L. Markov
Multilevel Fiduccia-Mattheyses (MLFM) hypergraph partitioning [3, 22, 24] is a fundamental optimization in VLSI CAD physical design. The leading implementation, hMetis [23], has since 1997 proved...
Optimal Partitioners and End-case Placers for Standard-cell Layout (2000)
Andrew E. Caldwell, Andrew B. Kahng, Igor L. Markov
Abstract—We study alternatives to classic Fiduccia–Mattheyses (FM)-based partitioning algorithms in the context of end-case processing for top-down standard-cell placement. While the divide step...
Iterative Partitioning With Varying Node Weights (2000)
Andrew E. Caldwell, Andrew B. Kahng, Igor L. Markov
The balanced partitioning problem divides the nodes of a [hyper]graph into groups of approximately equal weight (i.e., satisfying balance constraints) while minimizing the number of [hyper]edges that...
Optimal Partitioners and End-case Placers for Standard-cell Layout (2000)
Andrew E. Caldwell, Andrew B. Kahng, Igor L. Markov
Abstract—We study alternatives to classic Fiduccia–Mattheyses (FM)-based partitioning algorithms in the context of end-case processing for top-down standard-cell placement. While the divide step...
Design and Implementation of Move-Based Heuristics for VLSI (2000)
Andrew E. Caldwell, Andrew B. Kahng, Igor L. Markov
We summarize the techniques of implementing move-based hypergraph partitioning heuristics and evaluating their performance in the context of VLSI design applications. Our rst contribution is a...
Iterative Partitioning with Varying Node Weights (2000)
Andrew E. Caldwell, Andrew B. Kahng, Igor L. Markov
The balanced partitioning problem divides the nodes of a [hyper]graph into groups of approximately equal weight (i.e., satisfying balance constraints) while minimizing the number of [hyper]edges that...
Filling Algorithms and Analyses for Layout Density Control (1999)
Andrew B. Kahng, Gabriel Robins Y, Anish Singh Y, Er Zelikovsky
In very deep-submicron VLSI, manufacturing steps involving chemical-mechanical polishing (CMP) have varying e ects on device and interconnect features, depending on local characteristics of the...
Optimal Phase Con ict Removal for Layout of Dark Field Alternating Phase Shifting Masks (1999)
Piotr Berman, Andrew B. Kahng, Devendra Vidhani, Huijuan Wang, Alexander Zelikovsky X
We describe new, e cient algorithms for layout modi cation and phase assignment for dark eld alternating-type phase-shifting masks in the single-exposure regime. We make the following contributions....
On the associative-skew clock routing problem (1999)
Yu Chen, Andrew B. Kahng, Gang Qu, Er Zelikovsky
We introduce the associative skew clock routing problem, which seeks a clock routing tree such that zero skew is preserved only within identified groups of sinks. The associative skew problem is...
Copy detection for intellectual property protection (1999)
Andrew B. Kahng, Darko Kirovski, Stefanus Mantik, Miodrag Potkonjak, Jennifer L. Wong
We give the first study of copy detection techniques for VLSI CAD applications; these techniques are complementary to previous watermarking-based IP protection methods in finding and proving improper...
Traversing probabilistic graphs (1999)
Murali Mani, Alex Zelikovsky, Gautam Bhatia, Andrew B. Kahng
The problem of traversing probabilistic graphs has been studied for a long time. This is because most of the graphs that we come across, whether it is a network of roads or a set of network links are...
Effective Iterative Techniques for Fingerprinting Design IP (1999)
Andrew E. Caldwell, Hyun-Jin Choi, Andrew B. Kahng, Stefanus Mantik, Miodrag Potkonjak, Gang Qu, ...
While previous watermarking-based approaches to intellectual property protection (IPP) have asymmetrically emphasized the IP provider's rights, the true goal of IPP is to ensure the rights of...
The Associative-Skew Clock Routing Problem (1999)
Yu Chen Andrew, Yu Chen, Andrew B. Kahng, Gang Qu, Er Zelikovsky
We introduce the associative skew clock routing problem, which seeks a clock routing tree such that zero skew is preserved only within identified groups of sinks. The associative skew problem is...
Optimal Phase Conflict Removal for Layout of Dark Field Alternating Phase Shifting Masks (1999)
Piotr Berman, Andrew B. Kahng, Devendra Vidhani, Huijuan Wang, Alexander Zelikovsky
We describe new, efficient algorithms for layout modification and phase assignment for dark field alternating-type phase-shifting masks in the single-exposure regime. We make the following...
Bounded-Skew Clock and Steiner Routing (1999)
Jason Cong, Andrew B. Kahng, Cheng-Kok Koh, C. -w
this paper we study the BST problem under both the pathlength (linear) and Elmore delay models [Elmore 1948]. We propose the new BST/DME algorithm which, similar to the DME construction of a...
Tuning Strategies for Global Interconnects in High-Performance Deep-Submicron ICs (1999)
Andrew Kahng Sudhakar, Andrew B. Kahng, Sudhakar Muddu, Egino Sarto
Interconnect tuning is an increasingly critical degree of freedom in the physical design of high-performance VLSI systems. By interconnect tuning, we refer to the selection of line thicknesses,...
Optimal Phase Conflict Removal for Layout of Dark Field Alternating Phase Shifting Masks (1999)
Piotr Berman, Andrew B. Kahng, Devendra Vidhani, Huijuan Wang, Alex Zelikovsky
We describe new, efficient algorithms for layout modification and phase assignment for dark field alternating-type phase-shifting masks in the single-exposure regime. We make the following...
Effective Iterative Techniques for Fingerprinting Design IP (1999)
Andrew E. Caldwell, Hyun-Jin Choi, Andrew B. Kahng, Stefanus Mantik, Miodrag Potkonjak, Gang Qu, ...
While previous watermarking-based approaches to intellectual property protection (IPP) have asymmetrically emphasized the IP provider's rights, the true goal of IPP is to ensure the rights of...
Subwavelength Lithography and its Potential Impact on Design and EDA (1999)
This tutorial paper surveys the potential implications of subwavelength optical lithography for new tools and flows in the interface between layout design and manufacturability. We review control of...
New Multilevel and Hierarchical Algorithms for Layout Density Control (1999)
Andrew B. Kahng, Gabriel Robins, Anish Singh, Alexander Zelikovsky, Er Zelikovsky
Certain manufacturing steps in very deep submicron VLSI involve chemical-mechanical polishing (CMP) which has varying effects on device and interconnect features, depending on local layout...
Piotr Berman, Andrew B. Kahng, Devendra Vidhani, Alexander Zelikovsky
. Given a graph G with weighted edges, and a subset of nodes T , the T -join problem asks for a minimum weight edge set A such that a node u is incident to an odd number of edges of A iff u 2 T . We...
The Associative-Skew Clock Routing Problem (1999)
Yu Chen, Andrew B. Kahng, Gang Qu, Alexander Zelikovsky, Er Zelikovsky
We introduce the associative skew clock routing problem, which seeks a clock routing tree such that zero skew is preserved only within identified groups of sinks. The associative skew problem is...
Noise and Delay Uncertainty Studies for Coupled RC Interconnects (1999)
Andrew B. Kahng, Sudhakar Muddu, Devendra Vidhani
The performance of high-speed VLSI circuits is increasingly limited by interconnect coupling noise. In this paper we present a closed-form crosstalk noise model with accuracy comparable to that of...
Design and Implementation of the Fiduccia-Mattheyses Heuristic for VLSI Netlist Partitioning (1999)
Andrew E. Caldwell, Andrew B. Kahng, Igor L. Markov
. We discuss the implementation and evaluation of move-based hypergraph partitioning heuristics in the context of VLSI design applications. Our first contribution is a detailed software architecture,...
Hypergraph Partitioning With Fixed Vertices (1999)
Andrew Caldwell, Andrew B. Kahng, Igor L. Markov
We empirically assess the implications of fixed terminals for hypergraph partitioning heuristics. Our experimental testbed incorporates a leading-edge multilevel hypergraph partitioner [14] [3] and...
Andrew E. Caldwell, Andrew B. Kahng, Andrew A. Kennings, Igor L. Markov
We illustrate how technical contributions in the VLSI CAD partitioning literature can fail to provide one or more of: (i) reproducible results and descriptions, (ii) an enabling account of the key...
Improved Effective Capacitance Computations for Use in Logic and Layout Optimization (1999)
Andrew B. Kahng, Sudhakar Muddu
We describe an improved iterationless approach for computing the effective capacitance of an interconnect load at a driving gate output. The speed and accuracy of our approach makes it suitable for...
Design and Implementation of the Fiduccia-Mattheyses Heuristic for VLSI Netlist Partitioning (1999)
Andrew Caldwell Andrew, Andrew B. Kahng, Igor L. Markov
. We discuss the implementation and evaluation of move-based hypergraph partitioning heuristics in the context of VLSI design applications. Our first contribution is a detailed software architecture,...
Effective iterative techniques for fingerprinting design (1999)
Andrew E. Caldwell, Hyun-jin Choi, Andrew B. Kahng, Stefanus Mantik, Miodrag Potkonjak, Gang Qu, ...
Abstract—Fingerprinting is an approach that assigns a unique and invisible ID to each sold instance of the intellectual property (IP). One of the key advantages fingerprinting-based intellectual...
Filling Algorithms and Analyses for Layout Density Control (1999)
Andrew B. Kahng, Gabriel Robins, Anish Singh, Er Zelikovsky
Abstract-In very deep-submicron very large scale integration (VLSI), manufacturing steps involving chemical-mechanical polishing (CMP) have varying effects on device and interconnect features,...
Andrew E. Caldwell, Andrew B. Kahng, Andrew A. Kennings, Igor L. Markov
We illustrate how technical contributions in the VLSI CAD partitioning literature can fail to provide one or more of: (i) reproducible results and descriptions, (ii) an enabling account of the key...
On Wirelength Estimations for Row-based Placement (1999)
Andrew E. Caldwell, Andrew B. Kahng, Stefanus Mantik, Igor L. Markov, Alex Zelikovsky
Wirelength estimation in VLSI layout is fundamental to any pre-detailed routing estimate of timing or routability. In this paper, we develop new wirelength estimation techniques appropriate for...
On the associative-skew clock routing problem (1999)
Yu Chen, Andrew B. Kahng, Gang Qu, Er Zelikovsky
We introduce the associative skew clock routing problem, which seeks a clock routing tree such that zero skew is preserved only within identified groups of sinks. The associative skew problem is...
New and Exact Filling Algorithms for Layout Density Control (1999)
Andrew B. Kahng, Gabriel Robins Y, Anish Singh Y, Er Zelikovsky
To reduce manufacturing variation due to chemicalmechanical polishing and to improve yield, layout must be made uniform with respect to density criteria. This is achieved by layout postprocessing to...
Design and Implementation of the Fiduccia-Mattheyses Heuristic for VLSI Netlist Partitioning (1999)
Andrew E. Caldwell, Andrew B. Kahng, Igor L. Markov
Abstract. We discuss the implementation and evaluation of move-based hypergraph partitioning heuristics in the context of VLSI design applications. Our rst contribution is a detailed software...
On Wirelength Estimations for Row-based Placement (1999)
Andrew E. Caldwell, Andrew B. Kahng, Stefanus Mantik, Igor L. Markov, Er Zelikovsky
Wirelength estimation in VLSI layout is fundamentaltoany pre-detailed routing estimate of timing or routability. In this paper, we develop e cient wirelength estimation techniques appropriate for...
Filling Algorithms and Analyses for Layout Density Control (1999)
Andrew B. Kahng, Gabriel Robins Y, Anish Singh Y, Er Zelikovsky
In very deep-submicron VLSI, manufacturing steps involving chemical-mechanical polishing (CMP) have varying e ects on device and interconnect features, depending on local characteristics of the...
Optimal Phase Conflict Removal for Layout of Dark Field Alternating Phase Shifting Masks (1999)
Piotr Berman, Andrew B. Kahng, Devendra Vidhani, Huijuan Wang, Alex Zelikovsky
We describe new, efficient algorithms for layout modification and phase assignment for dark field alternating-type phase-shifting masks in the single-exposure regime. We make the following...
Tuning Strategies for Global Interconnects in High-Performance Deep-Submicron ICs (1999)
Andrew B. Kahng, Sudhakar Muddu, Egino Sarto
Interconnect tuning is an increasingly critical degree of freedom in the physical design of high-performance VLSI systems. By interconnect tuning, we refer to the selection of line thicknesses,...
Automated Layout and Phase Assignment Techniques for Dark Field Alternating (1998)
Andrew B. Kahng, Huijuan Wang, Alex Zelikovsky
We describe new, e cient algorithms for layout modi cation and phase assignment for dark eld alternating-type phase-shifting masks in the single-exposure regime. We make the following contributions....
Robust IP watermarking methodologies for physical design (1998)
Andrew B. Kahng, Stefanus Mantik, Igor L. Markov, Miodrag Potkonjak, Paul Tucker, Huijuan Wang, ...
Increasingly popular reuse-based design paradigms create a pressing need for authorship enforcement techniques that protect the intellectual property rights of designers. We develop the first...
Robust IP watermarking methodologies for physical design (1998)
Andrew B. Kahng, Stefanus Mantik, Igor L. Markov, Miodrag Potkonjak, Paul Tucker, Huijuan Wang, ...
Increasingly popular reuse-based design paradigms create a pressing need for authorship enforcement techniques that protect the intellectual property rights of designers. We develop the first...
Bounded-Skew Clock and Steiner Routing (1998)
Jason Cong Andrew, Andrew B. Kahng, Cheng-kok Koh
this paper we study the BST problem under both the pathlength (linear) and Elmore delay models [Elmore 1948]. We propose the new BST/DME algorithm which, similar to the DME construction of a...
On Wirelength Estimations for Row-Based Placement (1998)
Andrew E. Caldwell, Andrew B. Kahng, Stefanus Mantik, Igor L. Markov, Alexander Zelikovsky, Er Zelikovsky
Wirelength estimation in VLSI layout is fundamental to any pre-detailed routing estimate of timing or routability. In this paper, we develop efficient wirelength estimation techniques appropriate for...
Bounded-Skew Clock and Steiner Routing (1998)
Jason Chong, Andrew B. Kahng, Cheng-kok Koh
ing with credit is permitted. To copy otherwise, to republish, to post on servers, to redistribute to lists, or to use any component of this work in other works, requires prior specific permission...
Jason Cong, Senior Member, Andrew B. Kahng, Associate Member, Kwok-shing Leung
Given an undirected graph G =(V; E) with positive edge weights (lengths) w: E !! + , a set of terminals (sinks) N ` V , and a unique root node r 2 N,ashortest path Steiner arborescence (hereafter an...
On Wirelength Estimations for Row-Based Placement (1998)
Andrew E. Caldwell, Andrew B. Kahng, Stefanus Mantik, Igor L. Markov, Alex Zelikovsky
Wirelength estimation in VLSI layout is fundamental to any pre-detailed routing estimate of timing or routability. In this paper, we develop new wirelength estimation techniques appropriate for...
New Efficient Algorithms for Computing Effective Capacitance (1998)
Andrew B. Kahng, Sudhakar Muddu
We describe a novel iterationless approach for computing the effective capacitance of an interconnect load at a driving gate output. Our new approach is considerably faster than previous methods for...
Futures for Partitioning in Physical Design (1998)
Andrew Kahng Ucla, Andrew B. Kahng
The context for partitioning in physical design is dominated by two concerns: top-down design and the focus on spatial embedding. The role of partitioning is exactly that of a facilitator of...
Jason Cong, Andrew B. Kahng, Kwok-shing Leung
Given an undirected graph G = (V; E) with positive edge weights (lengths) w : E ! ! + , a set of terminals (sinks) N ` V , and a unique root node r 2 N , a shortest-path Steiner arborescence (simply...
Interconnect Tuning Strategies for High-Performance ICs (1998)
Andrew B. Kahng, Sudhakar Muddu, Egino Sarto, Rahul Sharma
Interconnect tuning is an increasingly critical degree of freedom in the physical design of high-performance VLSI systems. By interconnect tuning, we refer to the selection of line thicknesses,...
Futures for Partitioning in Physical Design (1998)
The context for partitioning in physical design is dominated by two concerns: top-down design and the focus on spatial embedding. The role of partitioning is exactly that of a facilitator of...
algorithm, extends the DME algorithm for exact zero-skew trees via the concept of a (1998)
Merging Region, Jason Cong, Andrew B. Kahng, Cheng-kok Koh
ing with credit is permitted. To copy otherwise, to republish, to post on servers, to redistribute to lists, or to use any component of this work in other works, requires prior specific permission...
Interconnect Tuning Strategies for High-Performance ICs (1998)
Andrew Kahng Sudhakar, Andrew B. Kahng, Sudhakar Muddu, Egino Sarto, Rahul Sharma
Interconnect tuning is an increasingly critical degree of freedom in the physical design of high-performance VLSI systems. By interconnect tuning, we refer to the selection of line thicknesses,...
Efficient Algorithms for the Minimum (1998)
Shortest Path Steiner, Jason Cong, Senior Member, Andrew B. Kahng, Associate Member, Kwok-shing Leung
Given an undirected graph G =(V; E) with positive edge weights (lengths) w: E !! + , a set of terminals (sinks) N ` V , and a unique root node r 2 N,ashortest path Steiner arborescence (hereafter an...
Bounded-Skew Clock and Steiner Routing (1998)
Jason Cong Andrew, Andrew B. Kahng, Cheng-kok Koh, C. -w, Albert Tsao
this paper we study the BST problem under both the pathlength (linear) and Elmore delay models [Elmore 1948]. We propose the new BST/DME algorithm which, similar to the DME construction of a...
Filling and Slotting: Analysis and Algorithms (1998)
Andrew B. Kahng, Gabriel Robins, Anish Singh, Huijuan Wang, Er Zelikovsky
In very deep-submicron VLSI, certain manufacturing steps – notably optical exposure, resist development and etch, chemical vapor deposition and chemical-mechanical polishing (CMP) – have varying...
Robust IP watermarking methodologies for physical design (1998)
Andrew B. Kahng, Stefanus Mantik, Igor L. Markov, Miodrag Potkonjak, Paul Tucker, Huijuan Wang, ...
Increasingly popular reuse-based design paradigms create a pressing need for authorship enforcement techniques that protect the intellectual property rights of designers. We develop the first...
Relaxed partitioning balance constraints in top-down placement (1998)
Andrew E. Caldwell, Andrew B. Kahng, Igor L. Markov
Recent work of Simon and Teng [17] observes that the recursive bisection (i.e., bipartitioning with equal partition target areas, and minimum possible allowed deviation from targets) heuristic for...
Robust IP watermarking methodologies for physical design (1998)
Andrew B. Kahng, Stefanus Mantik, Igor L. Markov, Miodrag Potkonjak, Paul Tucker, Huijuan Wang, ...
Increasingly popular reuse-based design paradigms create a pressing need for authorship enforcement techniques that protect the intellectual property rights of designers. We develop the first...
Filling and Slotting: Analysis and Algorithms (1998)
Andrew B. Kahng, Gabriel Robins, Anish Singh, Huijuan Wang, Er Zelikovsky
In very deep-submicron VLSI, certain manufacturing steps – notably optical exposure, resist development and etch, chemical vapor deposition and chemical-mechanical polishing (CMP) – have varying...
New efficient algorithms for computing effective capacitance (1998)
Andrew B. Kahng, Sudhakar Muddu
recent 0.25µm high-end microprocessor project confirm the accuracy of We describe a novel iterationless approach for computing the effective our new methods. capacitance of an interconnect load at a...
Multilevel Circuit Partitioning (1997)
Charles J. Alpert, Jen-hsin Huang, Andrew B. Kahng, Associate Member, Anetlist Hypergraph
Abstract — Many previous works in partitioning have used some underlying clustering algorithm to improve performance. As problem sizes reach new levels of complexity, a single application of a...
Cooperative mobile robotics: Antecedents and directions (1997)
Alex S. Fukunaga, Andrew B. Kahng
Abstract. There has been increased research interest in systems composed of multiple autonomous mobile robots exhibiting cooperative behavior. Groups of mobile robots are constructed, with an aim to...
Partitioning-based standard-cell global placement with an exact objective (1997)
We present a new top-down quadrisection-based global placer for standard-cell layout. The key contribution is a new general gain update scheme for partitioning that can exactly capture detailed...
Andrew B. Kahng, Sudhakar Muddu
This paper gives new methods for calculating the time-domain response for a finite-length distributed RC line that is stimulated by a ramp input. The following are our contributions. First, we obtain...
Cooperative mobile robotics: Antecedents and directions (1997)
Y. Uny Cao, Alex S. Fukunaga, Andrew B. Kahng
There has been increased research interest in systems composed of multiple autonomous mobile robots exhibiting cooperative behavior. Groups of mobile robots are constructed, with an aim to studying...
Improved large-step Markov chain variants for the symmetric TSP (1997)
Inki Hong, Andrew B. Kahng, Byung-ro Moon
The large-step Markov chain (LSMC) approach is the most effective known heuristic for large symmetric TSP instances; cf. recent results of Martin et al. [17] and Johnson [12]. In this report, we...
More Practical Bounded-Skew Clock Routing (1997)
Abstract: Academic clock routing research results has often had limited impact on industry practice, since such practical considerations as hierarchical buffering, rise-time and overshoot...
Faster Minimization of Linear Wirelength for Global Placement (1997)
Charles J. Alpert, Tony F. Chan, Andrew B. Kahng, Igor L. Markov, Pep Mulet, ...
A linear wirelength objective more e#ectively captures timing, congestion, and other global placement considerations than a squared wirelength objective. The GORDIAN-L cell placement tool #16#...
More Practical Bounded-Skew Clock Routing (1997)
Andrew Kahng And, Andrew B. Kahng
: Academic clock routing research results has often had limited impact on industry practice, since such practical considerations as hierarchical buffering, rise-time and overshoot constraints,...
Jason Cong, Andrew B. Kahng, Kwok-shing Leung
Given an undirected graph G = (V; E) with positive edge weights (lengths) w : E ! ! + , a set of terminals (sinks) N ` V , and a unique root node r 2 N , a shortest-path Steiner arborescence (simply...
Faster Minimization of Linear Wirelength for Global Placement (1997)
Charles J. Alpert, Tony F. Chan, Andrew B. Kahng, Igor L. Markov, Pep Mulet
A linear wirelength objective more effectively captures timing, congestion, and other global placement considerations than a squared wirelength objective. The GORDIAN-L cell placement tool [19]...
Multilevel Circuit Partitioning (1997)
Charles J. Alpert, Jen-Hsin Huang, Andrew B. Kahng
Recent work [2] [5] [11] [12] [14] has illustrated the promise of multilevel approaches for partitioning large circuits. Multilevel partitioning recursively clusters the instance until its size is...
Splitting An Ordering into a Partition to Minimize Diameter (1997)
Charles J. Alpert, Andrew B. Kahng
Many algorithms can find optimal bipartitions for various objectives including minimizing the maximum cluster diameter ("min-diameter"); these algorithms are often applied iteratively in...
Faster Minimization of Linear Wirelength for Global Placement (1997)
Charles J. Alpert, Tony F. Chan, Andrew B. Kahng, Igor L. Markov, Pep Mulet, ...
A linear wirelength objective more effectively captures timing, congestion, and other global placement considerations than a squared wirelength objective. The GORDIAN-L cell placement tool [16]...
Faster Minimization Of Linear Wirelength For Global Placement (1997)
Charles J. Alpert, Tony F. Chan, Andrew B. Kahng, Igor L. Markov, Pep Mulet, ...
A linear wirelength objective more effectively captures timing, congestion, and other global placement considerations than a squared wirelength objective. The GORDIAN-L cell placement tool [16]...
Studies of Clustering Objectives and Heuristics for Improved Standard-Cell Placement (1997)
This paper describes ongoing studies of clustering objectives and heuristics, along with their effect on top-down partitioning based standard-cell placement. Clustering for placement has three main...
Cooperative Mobile Robotics: Antecedents and Directions (1997)
Y. Uny Cao, Alex S. Fukunaga, Andrew B. Kahng
. There has been increased research interest in systems composed of multiple autonomous mobile robots exhibiting cooperative behavior. Groups of mobile robots are constructed, with an aim to studying...
Wei Huang and Andrew B. Kahng (1997)
Ucla Computer, Wei Huang, Andrew B. Kahng
We describe a "topology advisor" for routing of critical (multisource) buses in building-block design. The tool accepts as input a block layout, a two-layer routing cost structure...
On Implementation Choices for Iterative Improvement Partitioning Algorithms (1997)
Lars W. Hagen, Andrew B. Kahng
Iterative improvement partitioning algorithms such as the FM algorithm of Fiduccia and Mattheyses [8], the algorithm of Krishnamurthy [13], and Sanchis' extensions of these algorithms to...
On Implementation Choices for Iterative Improvement Partitioning Algorithms (1997)
Lars W. Hagen, Andrew B. Kahng
Iterative improvement partitioning algorithms such as the FM algorithm of Fiduccia and Mattheyses [8], the algorithm of Krishnamurthy [13], and Sanchis's extensions of these algorithms to...
Studies of Interconnect Tuning for High-Performance Designs (1997)
Andrew B. Kahng, Sudhakar Muddu, Rahul Sharma
Interconnect tuning is an increasingly critical degree of freedom in the design of high-performance VLSI systems. By interconnect tuning, we refer to the selection by a design team of line...
On Implementation Choices for Iterative Improvement Partitioning Algorithms (1997)
Lars W. Hagen, Andrew B. Kahng
Iterative improvement partitioning algorithms such as those due to Fiduccia and Mattheyses (FM) [2] and Krishnamurthy [5] exploit an efficient gain bucket data structure in selecting modules that are...
Andrew B. Kahng, Sudhakar Muddu
We present a general and, in the limit, exact approach to compute the time-domain response for finite-length RC lines under ramp input, by summing distinct diffusions starting at either end of the...
Multilevel Circuit Partitioning (1997)
Charles J. Alpert, Jen-hsin Huang, Andrew B. Kahng, Associate Member
Cooperative mobile robotics: Antecedents and directions (1997)
Alex S. Fukunaga, Andrew B. Kahng
Abstract. There has been increased research interest in systems composed of multiple autonomous mobile robots exhibiting cooperative behavior. Groups of mobile robots are constructed, with an aim to...
Lars W. Hagen, Andrew B. Kahng
VLSI netlist partitioning has been addressed chie y by iterative methods (e.g. Kernighan-Lin [21] and Fiduccia-Mattheyses [13]) and spectral methods (e.g. Hagen-Kahng [14]). Iterative methods are the...
Efficient gate delay modeling for large interconnect loads (1996)
Andrew B. Kahng, Sudhakar Muddu
With fast switching speeds and large interconnect trees (MCMs), the resistance and inductance of interconnect has a dominant impact on logic gate delay. In this paper, we propose a new \Pi model for...
Analytical Delay Models for VLSI Interconnects Under Ramp Input (1996)
Andrew B. Kahng, Sudhakar Muddu
Elmore delay has been widely used to estimate the interconnect delays in the performancedriven synthesis and layout of VLSI routing topologies. For typical RLC interconnections, Elmore delay can...
Analytical Delay Models for VLSI Interconnects Under Ramp Input (1996)
Andrew B. Kahng, Kei Masuko, Sudhakar Muddu
For typical RLC interconnections with ramp input as the source voltage, Elmore delay can deviate significantly (by up to 100 % or more) from SPICE-computed delay since it is independent of rise time...
An Analytical Delay Model for RLC Interconnects (1996)
Andrew B. Kahng, Sudhakar Muddu
Elmore delay has been widely used to estimate the interconnect delays in the performance-driven synthesis and layout of VLSI routing topologies. For typical RLC interconnections, Elmore delay can...
Large-Step Markov Chain Variants For VLSI Netlist Partitioning (1996)
Alex S. Fukunaga, Andrew B. Kahng
We examine the utility of the Large-Step Markov Chain (LSMC) technique [13], a variant of the iterated descent heuristic of Baum [2], for VLSI netlist bipartitioning. LSMC iteratively finds a local...
A Hybrid Multilevel/Genetic Approach for Circuit Partitioning (1996)
Charles J. Alpert, Lars W. Hagen, Andrew B. Kahng
We present a genetic circuit partitioning algorithm that integrates the Metis graph partitioning package [15] originally designed for sparse matrix computations. Metis is an extremely fast iterative...
Analysis of RC Interconnections under Ramp Input (1996)
Andrew B. Kahng, Sudhakar Muddu
We present a general and, in the limit, exact approach to compute the time-domain response for finite-length RC lines under ramp input, by summing distinct diffusions starting at either end of the...
Analytical Delay Models for VLSI Interconnects under Ramp Input (1996)
Andrew B. Kahng, Kei Masuko, Sudhakar Muddu
Elmore delay has been widely used as an analytical estimate of interconnect delays in the performance-driven synthesis and layout of VLSI routing topologies. However, for typical RLC...
A Hybrid Multilevel/Genetic Approach for Circuit Partitioning (1996)
Charles J. Alpert, Lars W. Hagen, Andrew B. Kahng
We present a multilevel/genetic circuit partitioning algorithm that utilizes the Metis graph partitioning package [13], which had been previously applied to finite-element graphs. Our new technique...
An Analytical Delay Model for RLC Interconnects (1996)
Andrew B. Kahng, Sudhakar Muddu
We develop an analytical delay model based on first and second moments to incorporate inductance effects into the delay estimate for interconnection lines. Delay estimates using our analytical model...
Large-Step Markov Chain Variants For Vlsi Netlist Partitioning (1996)
Alex Fukunaga, Andrew B. Kahng
We examine the utility of the Large-Step Markov Chain (LSMC) technique [13], a variant of the iterated descent heuristic of Baum [2], for VLSI netlist bipartitioning. LSMC iteratively finds a local...
Analysis of RC Interconnections under Ramp Input (1996)
Andrew B. Kahng, Sudhakar Muddu
, ramp input response, VLSI interconnects 1. INTRODUCTION Estimating delays on VLSI interconnections is a key element in timing verification, gate-level simulation and performance-driven layout...
Planar-DME: A Single-Layer Zero-Skew Clock Tree Router (1996)
This paper presents new single-layer, i.e., planar-embeddable, clock tree constructions with exact zero skew under either the linear or the Elmore delay model. Our method, called Planar-DME, consists...
Large-Step Markov Chain Variants for VLSI Netlist Partitioning (1996)
Alex S. Fukunaga, Andrew B. Kahng, Prev Lsmc
We examine the utility of the Large-Step Markov Chain #LSMC# technique #13#, a variant of the iterated descent heuristic of Baum #2#, for VLSI netlist bipartitioning. LSMC iteratively #nds a local...
On the bounded-skew clock and steiner routing problems (1995)
We study the minimum-cost bounded-skew routing tree (BST) problem under the linear delay model. This problem captures several engineering tradeoffs in the design of routing topologies with controlled...
Bounded-skew clock and Steiner routing under Elmore delay (1995)
Jason Cong, Andrew B. Kahng, Cheng-kok Koh
ABSTRACT: For engineering tradeoffs in "zero-skew " clock tree routing, for performance-driven Steiner routing, and even for power distribution topology design [31], a bounded-skew...
When clusters meet partitions: New density-based methods for circuit decomposition (1995)
Recent research on multi-way partitioning has focused on the minimum cut [20, 26, 27] or generalized ratio cut [28, 29, 5] cost metrics. At the same time, clustering research has focused on such...
Alex Fukunaga, Andrew B. Kahng
Traditional evolutionary optimization algorithms assume a static evaluation function, according to which solutions are evolved. Incremental evolution is an approach through which a dynamic evaluation...
Old Bachelor Acceptance: A New Class of Non-Monotone Threshold Accepting Methods (1995)
Stochastic hill-climbing algorithms, particularly simulated annealing (SA) and threshold acceptance (TA), have become very popular for global optimization applications. Typical implementations of SA...
Bounded-Skew Clock and Steiner Routing Under Elmore Delay (1995)
Jason Cong Andrew, Andrew B. Kahng, Cheng-kok Koh
: We study the minimum-cost bounded-skew routing tree problem under the Elmore delay model. We present two approaches to construct bounded-skew routing trees: (i) the Boundary Merging and Embedding...
Bounded-Skew Clock and Steiner Routing Under Elmore Delay (1995)
Jason Cong, Andrew B. Kahng, Cheng-kok Koh
: We study the minimum-cost bounded-skew routing tree problem under the Elmore delay model. We present two approaches to construct bounded-skew routing trees: (i) the Boundary Merging and Embedding...
Multi-Way Partitioning Via Geometric Embeddings, Orderings, and Dynamic Programming (1995)
Charles J. Alpert, Andrew B. Kahng
This paper presents effective algorithms for multi-way partitioning. Confirming ideas originally due to Hall [27], we demonstrate that geometric embeddings of the circuit netlist can lead to...
Bounded-Skew Clock and Steiner Routing Under Elmore Delay (1995)
Jason Cong, Andrew B. Kahng, Cheng-kok Koh
: For engineering tradeoffs in "zero-skew" clock tree routing, for performance-driven Steiner routing, and even for power distribution topology design [31], a bounded-skew routing tree...
Near-Optimal Critical Sink Routing Tree Constructions (1995)
Kenneth D. Boese, Andrew B. Kahng, Bernard A. Mccoy, Gabriel Robins
We present critical-sink routing tree (CSRT) constructions which exploit available critical-path information to yield high-performance routing trees. Our CS-Steiner and "Global Slack...
VLSI netlist partitioning has been addressed chiefly by iterative methods (e.g. KernighanLin [21] and Fiduccia-Mattheyses [13]) and spectral methods (e.g. Hagen-Kahng [14]). Iterative methods are the...
Quantified Suboptimality of VLSI Layout Heuristics (1995)
Lars W. Hagen, Andrew B. Kahng
We show how to quantify the suboptimality of heuristic algorithms for NP-hard problems arising in VLSI layout. Our approach is based on the notion of constructing new scaled instances from an initial...
Cooperative Mobile Robotics: Antecedents and Directions (1995)
Y. Uny Cao, Alex S. Fukunaga, Andrew B. Kahng, Frank Meng
There has been increased research interest in systems composed of multiple autonomous mobile robots exhibiting collective behavior. Groups of mobile robots are constructed, with an aim to studying...
On the Bounded-Skew Clock and Steiner Routing Problems (1995)
We study the minimum-cost bounded-skewrouting tree (BST) problem under the linear delay model. This problem captures several engineering tradeoffs in the design of routing topologies with controlled...
Alex Fukunaga, Andrew B. Kahng
Traditional evolutionary optimization algorithms assume a static evaluation function, according to which solutions are evolved. Incremental evolution is an approach through which a dynamic evaluation...
Toward More Powerful Recombinations (1995)
Andrew B. Kahng, Byung Ro Moon
This paper suggests a flexible framework for n-dimensional crossover, consisting of cutting, classification, and copying of genes. We prove that under this framework, any cutting strategy generates...
Donald E. Franklin, Andrew B. Kahng, M. Anthony Lewis
The problem of landmine detection has been studied for decades. Mine detection systems have typically been developed by first identifying a sensor technology, then testing on particular manmade...
Old Bachelor Acceptance: A New Class of Non-Monotone Threshold Accepting Methods (1995)
Stochastic hill-climbing algorithms, particularly simulated annealing (SA) and threshold acceptance (TA), have become very popular for global optimization applications. Typical implementations of SA...
Alex Fukunaga, Andrew B. Kahng
Traditional evolutionary optimization algorithms assume a static evaluation function, according to which solutions are evolved. Incremental evolution is an approach through which a dynamic evaluation...
Bounded-Skew Clock and Steiner Routing Under Elmore Delay (1995)
Jason Cong Andrew, Andrew B. Kahng, Cheng-kok Koh
We study the minimum-cost bounded-skew routing tree problem under the Elmore delay model. We present two approaches to construct bounded-skew routing trees: (i) the Boundary Merging and Embedding...
Near-optimal critical sink routing tree constructions (1995)
Kenneth D. Boese, Andrew B. Kahng, Associate Member, Bernard A. Mccoy, Gabriel Robins
Abstract-We present critical-sink routing tree (CSRT) con-structions which exploit available critical-path information to yield high-performance routing trees. Our CS-Steiner and “global slack...
Near-optimal critical sink routing tree constructions (1995)
Kenneth D. Boese, Andrew B. Kahng, Associate Member, Bernard A. Mccoy, Gabriel Robins
Abstract-We present critical-sink routing tree (CSRT) constructions which exploit available critical-path information to yield high-performance routing trees. Our CS-Steiner and "global...
Recent directions in netlist partitioning: A survey (1995)
Charles J. Alpert, Andrew B. Kahng
This survey describes research directions in netlist partitioning during the past two decades, in terms of both problem formulations and solution approaches. We discuss the traditional min-cut and...
Multi-way system partitioning into a single type or multiple types of FPGAs (1995)
This paper considers the problem of partitioning a circuit into a collection of subcircuits, such that each subcircuit is feasible for some device from an FPGA library, and the total cost of devices...
Low-Cost Single-Layer Clock Trees With Exact Zero Elmore Delay Skew (1994)
Andrew Kahng And, Andrew B. Kahng
We give the first single-layer clock tree construction with exact zero skew according to the Elmore delay model. The previous Linear-Planar-DME method [11] guarantees a planar solution under the...
Planar-DME: Improved Planar Zero-Skew Clock Routing With Minimum Pathlength Delay (1994)
Andrew Kahng And, Andrew B. Kahng
Clock routing has become a critical issue in the layout design of high-performance systems. We show that the two passes (bottom-up and top-down) of the DME algorithm [2, 3, 4, 8] can be replaced by a...
Spectral Partitioning: The More Eigenvectors, The Better (1994)
Charles J. Alpert, Andrew B. Kahng, So-Zen Yao
The graph partitioning problem is to divide the vertices of a graph into disjoint clusters to minimize the total cost of the edges cut by the clusters. A spectral partitioning heuristic uses the...
Rectilinear Steiner Trees with Minimum Elmore Delay (1994)
Kenneth Boese, Andrew B. Kahng, Bernard A. Mccoy, Gabriel Robins
We provide a new theoretical framework for constructing Steiner routing trees with minimum Elmore delay. Earlier work [3, 13] has established Elmore delay as a high fidelity estimate of...
Low-Cost Single-Layer Clock Trees With Exact Zero Elmore Delay Skew (1994)
We give the first single-layer clock tree construction with exact zero skew according to the Elmore delay model. The previous Linear-Planar-DME method [11] guarantees a planar solution under the...
Rectilinear Steiner Trees with Minimum Elmore Delay (1994)
Kenneth D. Boese, Andrew B. Kahng, Bernard A. Mccoy, Gabriel Robins
We provide a new theoretical framework for constructing Steiner routing trees with minimum Elmore delay. Earlier work [3, 13] has established Elmore delay as a high fidelity estimate of...
When Clusters Meet Partitions: New Density-Based Methods for Circuit Decomposition (1994)
Top-down partitioning has focused on minimum cut or ratio cut objectives, while bottom-up clustering has focused on density-based objectives. In seeking a more unified perspective, we propose a new...
Optimal Equivalent Circuits for Interconnect Delay Calculations Using Moments (1994)
Andrew B. Kahng, Sudhakar Muddu
In performance-driven interconnect design, delay estimators are used to determine both the topology and the layout of good routing trees. We address the class of moment-matching, or moment...
Scan Chain Optimization: Heuristic and Optimal Solutions (1994)
Kenneth D. Boese, Andrew B. Kahng, Ren-Song Tsay
We present new methods for scan chain ordering under the minimum wirelength objective. We have adapted the standard 2-opt and 3-opt heuristics for the symmetric traveling salesman problem (TSP) to...
Best-So-Far vs. Where-You-Are: Implications for Optimal Finite-Time Annealing (1994)
Kenneth D. Boese, Andrew B. Kahng
The simulated annealing (SA) algorithm is widely used for heuristic global optimization due to its high-quality results and its ability, in theory, to yield optimal solutions with probability one....
Low-cost single-layer clock trees with exact zero Elmore delay skew (1994)
We give the rst single-layer clock tree construction with exact zero skew according to the Elmore delay model. The previous Linear-Planar-DME method [11] guarantees a planar solution under the linear...
Planar-DME: Improved planar zero-skew clock routing with minimum pathlength delay (1994)
Clock routing has become a critical issue in the layout design of high-performance systems. We show that the two passes (bottom-up and top-down) of the DME algorithm [2, 3, 4, 8] can be replaced by a...
Matching-based methods for high-performance clock routing (1993)
Jason Cong, Andrew B. Kahng, Associate Member, Gabriel Robins
Abstract--Minimizing clock skew is important in the design of high performance VLSI systems. We present a general clock routing scheme that achieves very small clock skews while still using a...
Toward Optimal Routing Trees (1993)
Kenneth D. Boese, Andrew B. Kahng, Bernard A. Mccoy, Gabriel Robins
We address the efficient construction of interconnection trees with near-optimal delay properties. We begin from first principles, and study the accuracy and fidelity of easily-computed delay models...
High-performance routing trees with identified critical sinks (1993)
Kenneth D. Boese, Kenneth D. Boese, Andrew B. Kahng, Andrew B. Kahng, Gabriel Robins, Gabriel Robins
We present critical-sink routing tree (CSRT) constructions which yield high-performance routing trees by exploiting the critical-path information that may be available during timing-driven layout....
Toward Optimal Routing Trees (1993)
Kenneth D. Boese, Andrew B. Kahng, Bernard A. Mccoy, Gabriel Robins
We address the efficient construction of interconnection trees with near-optimal delay properties. We begin from first principles, and study the accuracy and fidelity of easily-computed delay models...
Simulated Annealing of Neural Networks: the "Cooling" Strategy Reconsidered (1993)
Kenneth D. Boese, Andrew B. Kahng
The simulated annealing (SA) algorithm [12] [5] has been widely used to address intractable global optimizations in many fields, including training of artificial neural networks. Implementations of...
Optimal Robust Path Planning in General Environments (1993)
T. C. Hu, Andrew B. Kahng, Gabriel Robins
We address robust path planning for a mobile agent in a general environment by finding minimum cost source-destination paths having prescribed widths. The main result is a new approach which...
Fidelity and Near-Optimality of Elmore-Based Routing Constructions (1993)
Kenneth D. Boese, Andrew B. Kahng, Bernard A. Mccoy, Gabriel Robins
We address the efficient construction of interconnection trees with near-optimal delays. We study the accuracy and fidelity of easily-computed delay models with respect to detailed simulation (e.g.,...
High-Performance Routing Trees With Identified Critical Sinks (1993)
Kenneth Boese, Andrew B. Kahng, Gabriel Robins
We present two critical-sink routing tree (CSRT) constructions which exploit critical-path information that becomes available during timing-driven layout. Our CS-Steiner heuristics with "Global...
Best-So-Far vs. Where-You-Are: New Perspectives on Simulated Annealing for CAD (1993)
Kenneth D. Boese, Andrew B. Kahng
The simulated annealing (SA) algorithm [14] [5] has been applied to every difficult optimization problem in VLSI CAD. Existing SA implementations use monotone decreasing, or cooling, temperature...
Optimal Robust Path Planning in General Environments (1993)
T. C. Hu, Andrew B. Kahng, Gabriel Robins
We address robust path planning for a mobile agent in a general environment by finding minimum cost source-destination paths having prescribed widths. The main result is a new approach which...
Fidelity and Near-Optimality of Elmore-Based Routing Constructions (1993)
Kenneth D. Boese, Andrew B. Kahng, Bernard A. Mccoy, Gabriel Robins
We address the efficient construction of interconnection trees with near-optimal delays. We study the accuracy and fidelity of easily-computed delay models with respect to detailed simulation (e.g.,...
High-Performance Routing Trees With Identified Critical Sinks (1993)
Kenneth Boese, Andrew B. Kahng, Gabriel Robins
We present two critical-sink routing tree (CSRT) constructions which exploit critical-path information that becomes available during timing-driven layout. Our CS-Steiner heuristics with "Global...
Matching-based methods for high-performance clock routing (1993)
Jason Cong, Andrew B. Kahng, Associate Member, Gabriel Robins
Abstract-Minimizing clock skew is important in the design of high performance VLSI systems. We present a general clock routing scheme that achieves very small clock skews while still using a...
Provably good performance-driven global routing (1992)
Jingsheng Cong, Andrew B. Kahng, Associate Member, Gabriel Robins, Majid Sarrafzadeh, C. K. Wong
Abstract-We propose a provably good performance-driven global routing algorithm for both cell-based and building-block design. The approach is based on a new bounded-radius mini-mum routing tree...
Provably good performance-driven global routing (1992)
Jingsheng Cong, Andrew B. Kahng, Associate Member, Gabriel Robins, Majid Sarrafzadeh, C. K. Wong
Abstract--We propose a provably good performance-driven global routing algorithm for both cell-based and building-block design. The approach is based on a new bounded-radius minimum routing tree...
A new class of iterative Steiner tree heuristics with good performance (1992)
Andrew B. Kahng, Associate Member, Gabriel Robins, Student Member
problem is very important for such aspects of physical layout as global routing and wiring estimation. Virtually all previous heuristics for computing rectilinear Steiner trees begin with a minimum...
An Improved Graph-Based FPGA Technology Mapping Algorithm For Delay Optimization (1992)
Jason Cong, Yuzheng Ding, Andrew B. Kahng, Peter Trajmar, Kuang-chien Chen
We present a graph based technology mapping algorithm, called DAG-Map, for delay optimization in lookup-table based FPGA designs. Our algorithm carries out technology mapping and delay optimization...
A New Approach to Effective Circuit Clustering (1992)
The complexity of next-generation VLSI systems will exceed the capabilities of top-down layout synthesis algorithms, particularly in netlist partitioning and module placement. Bottom-up clustering is...
Zero Skew Clock Routing With Minimum Wirelength (1992)
Ting-Hai Chao, Yu-Chin Hsu, Jan-Ming Ho, Kenneth D. Boese, Andrew B. Kahng
In the design of high performance VLSI systems, minimization of clock skew is an increasingly important objective. Additionally, wirelength of clock routing trees should be minimized in order to...
Zero-Skew Clock Routing Trees With Minimum Wirelength (1992)
Kenneth Boese, Andrew B. Kahng
In the design of high performance VLSI systems, minimization of clock skew is an increasingly important objective. Additionally, wirelength of clock routing trees should be minimized in order to...
Improving the Quadratic Objective Function in Module Placement (1992)
Traditional placement goals for cell-based designs involve minimizing either total wirelength or channel width; each of these metrics reflects final layout area. Typically, a net model is first used...
An Improved Graph-Based FPGA Technology Mapping Algorithm For Delay Optimization (1992)
Jason Cong Yuzheng, Jason Cong, Yuzheng Ding, Andrew B. Kahng, Peter Trajmar, Kuang-chien Chen
We present a graph based technology mapping algorithm, called DAG-Map, for delay optimization in lookup-table based FPGA designs. Our algorithm carries out technology mapping and delay optimization...
Provably good performance-driven global routing (1992)
Jingsheng Cong, Andrew B. Kahng, Associate Member, Gabriel Robins, Majid Sarrafzadeh, C. K. Wong
Abstract-We propose a provably good performance-driven global routing algorithm for both cell-based and building-block design. The approach is based on a new bounded-radius minimum routing tree...
A new class of iterative Steiner tree heuristics with good performance (1992)
Andrew B. Kahng, Associate Member, Gabriel Robins, Student Member
problem is very important for such aspects of physical layout as global routing and wiring estimation. Virtually all previous heuristics for computing rectilinear Steiner trees begin with a minimum...
Match twice and stitch: a new TSP tour construction heuristic (0000)
We present a new symmetric traveling salesman problem tour construction heuristic. Two sequential matchings yield a set of cycles over the given point set; these are then stitched to form a tour....
Match twice and stitch: a new TSP tour construction heuristic
We present a new symmetric traveling salesman problem tour construction heuristic. Two sequential matchings yield a set of cycles over the given point set; these are then stitched to form a tour....
Multilevel Circuit Partitioning
Charles J. Alpert, Jen-Hsin Huang, Andrew B. Kahng, Associate Member
Many previous works [3] [7] [17] [33] [40] in partitioning have used some underlying clustering algorithm to improve performance. As problem sizes reach new levels of complexity, a single application...
Function Smoothing with Applications to VLSI Layout
Ross Baldick, Andrew B. Kahng, Andrew Kennings, Igor L. Markov
We present approximations to non-smooth continuous functions by differentiable functions which are parameterized by a scalar fi ? 0 and have convenient limit behavior as fi ! 0. For standard...
Filling Algorithms and Analyses for Layout Density Control
Andrew B. Kahng, Gabriel Robins, Anish Singh, Alexander Zelikovsky
In very deep-submicron VLSI, manufacturing steps involving chemical-mechanical polishing (CMP) have varying effects on device and interconnect features, depending on local characteristics of the...
Relaxed Partitioning Balance Constraints in Top-Down Placement
Andrew Caldwell, Andrew B. Kahng, Igor L. Markov
Recent work of Simon and Teng [17] observes that the recursive bisection (i.e., bipartitioning with equal partition target areas, and minimum possible allowed deviation from targets) heuristic for k-...
Exploiting Synergies of Multiple Crossovers: Initial Studies
Inki Hong, Andrew B. Kahng, Byung Ro Moon
Genetic algorithms (GAs) are believed to exploit the synergy between different traversals of the solution space that are afforded by crossover and mutation operators. While dozens of different...
Multilevel Circuit Partitioning
Charles J. Alpert, Jen-hsin Huang, Andrew B. Kahng
Recent work [2] [5] [11] [12] [14] has illustrated the promise of multilevel approaches for partitioning large circuits. Multilevel partitioning recursively clusters the instance until its size is...
Multi-Way System Partitioning into a Single Type or Multiple Types of FPGAs
This paper considers the problem of partitioning a circuit into a collection of subcircuits, such that each subcircuit is feasible for some device from an FPGA library, and the total cost of devices...
Multi-Way System Partitioning into a Single Type or Multiple Types of FPGAs
This paper considers the problem of partitioning a circuit into a collection of subcircuits, such that each subcircuit is feasible for some device from an FPGA library, and the total cost of devices...