NDLI: Can recursive bisection alone produce routable placements?

Please wait, while we are loading the content...

First-time-right si but to the right specification (keynote address)

System design challenges in the post-PC era (keynote address)

A case study of synthesis for industrial-scale analog IP: redesign of the equalizer/filter frontend for an ADSL CODEC

Optimal RF design using smart evolutionary algorithms

CYCLONE: automated design and layout of RF LC-oscillators

An asymptotically constant, linearly bounded methodology for the statistical simulation of analog circuits including component mismatch effects

Multi-terminal determinant decision diagrams: a new approach to semi-symbolic analysis of analog integrated circuits

To split or to conjoin: the question in image computation

Symbolic guided search for CTL model checking

Lazy symbolic model checking

Distance driven finite state machine traversal

Automatic test pattern generation for functional RTL circuits using assignment decision diagrams

Interconnect testing in cluster-based FPGA architectures

Improved fault diagnosis in scan-based BIST via superposition

On diagnosis of pattern-dependent delay faults

On-chip inductance modeling and analysis

A practical approach to parasitic extraction for design of multimillion-transistor integrated circuits

A rank-one update method for efficient processing of interconnect parasitics in timing analysis

On switch factor based analysis of coupled RC interconnects

Life at the end of CMOS scaling (and beyond) (panel session) (abstract only)

Area and search space control for technology mapping

BDS: a BDD-based logic optimization system

A fine-grained arithmetic optimization technique for high-performance/low-power data path synthesis

Optimal low powerX OR gate decomposition

Watermarking while preserving the critical path

Formal verification of superscale microprocessors with multicycle functional units, exception, and branch prediction

Assertion checking by combined word-level ATPG and modular arithmetic constraint-solving techniques

Reliable verification using symbolic simulation with scalar values

Automatic formal verification of DSP software

System chip test: how will it impact your design?

Test challenges for deep sub-micron technologies

Hierarchical analysis of power distribution networks

Fast power grid simulation

Current signature compression for IR-drop analysis

Impact of interconnect variations on the clock skew of a gigahertz microprocessor

A methodology for modeling the effects of systematic within-die interconnect and device variation on circuit performance

Design closure (panel session): hope or hype?

A multi-interval Chebyshev collocation method for efficient high-accuracy RF circuit simulation

Projection frameworks for model reduction of weakly nonlinear systems

A realizable driving point model for on-chip interconnect with inductance

Formal verification of an IBM CoreConnect processor local bus arbiter core

Formal verification of iterative algorithms in microprocessors

Efficient error detection, localization, and correction for FPGA-based debugging

Multiple Si layer ICs: motivation, performance analysis, and design implications

High-level model of a WDMA passive optical bus for a reconfigurable multiprocessor system

A design of and design tools for a novel quantum dot based microprocessor

ClariNet: a noise analysis tool for deep submicron design

Static noise analysis for digital integrated circuits in partially-depleted silicon-on-insulator technology

Dynamic noise analysis in precharge-evaluate circuits

Extended Krylov subspace method for reduced order analysis of linear circuits with multiple sources

EDA meets.COM (panel session): how E-services will change the EDA business model

Symbolic timing simulation using cluster scheduling

Critical path analysis using a dynamically bounded delay model

TACO: timing analysis with coupling

Removing user specified false paths from timing graphs

Performance driven multi-level and multiway partitioning with retiming

Domino logic synthesis minimizing crosstalk

Fast post-placement rewiring using easily detectable functional symmetries

Depth optimal incremental mapping for field programmable gate arrays

Code compression for low power embedded system design

Synthesis of application-specific memories for power optimization in embedded systems

Influence of compiler optimizations on system power

Power minimization derived from architectural-usage of VLIW processors

Power analysis of embedded operating systems

Memory aware compilation through accurate timing extraction

Compiling Esterel into sequential code

Interactive co-design of high throughput embedded multimedia

Predicting performance potential of modern DSPs

Future systems-on-chip (panel session): software of hardware design?

Embedded systems design in the new millennium (panel session)

The design and use of simplepower: a cycle-accurate energy estimation tool

An instruction-level functionally-based energy estimation model for 32-bits microprocessors

Dynamic power management of complex systems using generalized stochastic Petri nets

Wave-steering one-hot encoded FSMs

Performance analysis and optimization of latency insensitive systems

A fast algorithm for context-aware buffer insertion

Maze routing with buffer insertion and wiresizing

Routing tree construction under fixed buffer locations

A current driven routing and verification methodology for analog applications

A codesign virtual machine for hierarchical, balanced hardware/software system modeling

Operating system based software generation for systems-on-chip

YAPI: application modeling for signal processing systems

COSY communication IP's

Synthesis and optimization of coordination controllers for distributed embedded systems

Application-specific memory management for embedded systems using software-controlled caches

Designing systems-on-chip using cores

Verification of configurable processor cores

Design of system-on-a-chip test access architectures under place-and-route and power constraints

The future of system design languages (panel session)

A methodology for efficient high-level dataflow simulation of mixed-signal front-ends of digital telecom transceivers

High-level simulation of substrate noise generation including power supply noise coupling

Systematic design of a 14-bit 150-MS/s CMOS current-steering D/A converter

B*-Trees: a new representation for non-slicing floorplans

Block placement with symmetry constraints based on the O-tree non-slicing representation

Floorplan sizing by linear programming approximation

Timing-driven placement based on partitioning with dynamic cut-net control

Can recursive bisection alone produce routable placements?

Task scheduling with RT constraints

Task generation and compile-time scheduling for mixed data-control embedded software

Schedulability-driven performance analysis of multiple mode embedded real-time systems

System design of active basestations based on dynamically reconfigurable hardware

Hardware-software co-design of embedded reconfigurable architectures

Communication architecture tuners: a methodology for the design of high-performance communication architectures for systems-on-chips

Embedded systems education (panel session) (abstract only)

Passive model order reduction algorithm based on Chebyshev expansion of impulse response of interconnect networks

Passive model order reduction of multiport distributed interconnects

Predicting coupled noise in RC circuits by matching 1, 2, and 3 moments

Singularity-treated quadrature-evaluated method of moments solver for 3-D capacitance extraction

Optimal two level partitioning and loop scheduling for hiding memory latency for DSP applications

On lower bounds for scheduling problems in high-level synthesis

Efficient building block based RTL code generation from synchronous data flow graphs

System-level data format exploration for dynamically allocated data structures

MOSFET modeling and circuit design (tutorial): re-establishing a lost connection

Using general-purpose programming languages for FPGA design

An architecture-driven metric for simultaneous placement and global routing for FPGAs

MorphoSys: case study of a reconfigurable computing system targeting multimedia applications

Survival strategies for mixed-signal systems-on-chip (panel session)

Forensic engineering techniques for VLSI CAD tools

Fingerprinting intellectual property using constraint-addition

Hardware/software IP protection

A Web-CAD methodology for IP-core analysis and simulation

Optimizing sequential verification by retiming transformations

Efficient methods for embedded system design space exploration

Synthesis-for-testability of controller-datapath pairs that use gated clocks

Self-test methodology for at-speed test of crosstalk in chip interconnects

Embedded hardware and software self-testing methodologies for processor cores

Modeling and simulation of real defects using fuzzy logic

Closing the gap between ASIC and custom: an ASIC perspective

The role of custom design in ASIC Chips

Case studies (panel session) (abstract only): Chip design on the bleeding edge

MINFLOTRANSIT: min-cost flow based transistor sizing tool

Convex delay models for transistor sizing

Macro-driven circuit design methodology for high-performance datapaths

Model-based dummy feature placement for oxide chemical-mechanical polishing manufacturability

Practical iterated fill synthesis for CMP uniformity

Boolean satisfiability in electronic design automation

Analysis of composition complexity and how to obtain smaller canonical graphs

Efficient variable ordering using aBDD based sampling

GTX: the MARCO GSRC technology extrapolation system

A system simulation framework

METRICS: a system architecture for design process optimization

Web-based frameworks to enable CAD R&D (abstract)

“Timing closure by design,” a high frequency microprocessor design methodology

Multiprocessing design verification methodology for Motorola MPC74XX PowerPC microprocessor

A methodology for formal design of hardware control with application to cache coherence protocols

CGaAs PowerPC FXU

When bad things happen to good chips (panel session)

Fast methods for extraction and sparsification of substrate coupling

Large-scale capacitance calculation

Fast temperature calculation for transient electrothermal simulation by mixed frequency/time domain thermal model reduction

Unifying behavioral synthesis and physical design

Hardware implementation of communication protocols modeled by concurrent EFSMs with multi-way synchronization

The use of carry-save representation in joint module selection and retiming

Closing the gap between analog and digital

A switch level fault simulation environment

Universal fault simulation using fault tuples

A novel algorithm to extract two-node bridges

Power minimization using control generated clocks

Bus encoding for low-power high-performance memory systems

Run-time voltage hopping for low-power real-time systems

Function-level power estimation methodology for microprocessors

Emerging companies—acquiring minds want to know (panel session)

Can recursive bisection alone produce routable placements?

Content Provider	ACM Digital Library
Author	Kahng, Andrew B. Markov, Igor L. Caldwell, Andrew E.
Abstract	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 placement and implement a new placer, called Capo, to empirically study the achievable limits of the approach. From among recently proposed improvements to recursive bisection, Capo incorporates a leading-edge multilevel min-cut partitioner [7], techniques for partitioning with small tolerance [8], optimal min-cut partitioners and end-case min-wirelength placers [5], previously unpublished partitioning tolerance computations, and block splitting heuristics. On the other hand, our “good enough” implementation does not use “overlapping” [17], multi-way partitioners [17, 20], analytical placement, or congestion estimation [24, 35]. In order to run on recent industrial placement instances, Capo must take into account fixed macros, power stripes and rows with different allowed cell orientations. Capo reads industry-standard LEF/DEF, as well as formats of the GSRC bookshelf for VLSI CAD algorithms [6], to enable comparisons on available placement instances in the fixed-die regime.Capo clearly demonstrates that despite a potential mismatch of objectives, improved mincut bisection can still lead to improved placement wirelength and congestion. Our experiments on recent industrial benchmarks fail to give a clear answer to the question in the title of this paper. However, they validate a series of improvements to recursive bisection and point out a need for transparent congestion management techniques that do not worsen the wirelength of already routable placements. Our experimental flow, which validates fixed-die placement results by violation-free detailed auto-routability, provides a new norm for comparison of VLSI placement implementations.
Starting Page	477
Ending Page	482
Page Count	6
File Format	PDF
ISBN	1581131879
DOI	10.1145/337292.337549
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2000-06-01
Publisher Place	New York
Access Restriction	Subscribed
Content Type	Text
Resource Type	Article

Central Library (ISO-9001:2015 Certified)
Indian Institute of Technology Kharagpur
Kharagpur, West Bengal, India | PIN - 721302

See location in the Map
03222 282435
Mail: support@ndl.gov.in

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in