NDLI: Optimality and scalability study of existing placement algorithms

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

BEAM: bus encoding based on instruction-set-aware memories

A statistical gate delay model for intra-chip and inter-chip variabilities

An on-line approach for power minimization in QoS sensitive systems

SAT-based sequential depth computation

Typing abstractions and management in a component framework

Approximate formulae approach for efficient inductance extraction

Recent developments in ESD protection for RF ICs

A BDD-based fast heuristic algorithm for disjoint decomposition

Combining architecture exploration and a path to implementation to build a complete SoC design flow from system specification to RTL

Adaptive wire adjustment for bounded skew Clock Distribution Network

Statistical delay computation considering spatial correlations

Gate-level simulation of quantum circuits

A simulated annealing approach with sequence-pair encoding using a penalty function for the placement problem with boundary constraints

Anatomy of platform-based design: is it the savior of UDSM SoC design crisis?

Efficient LUT-based FPGA technology mapping for power minimization

Advanced power management techniques: going beyond intelligent shutdown

Fast buffer planning and congestion optimization in interconnect-driven floorplanning

VCore-based design methodology

Adaptive computing: what can it do, where can it go?

Implementation of the super-systolic array for convolution

Accelerating design space exploration using pareto-front arithmetics

Roles of funding agencies in technology-driven economic development

Legal protection for semiconductor Intellectual Property (IP)

Design and implementation of a video-oriented network-interface-card system

Run-time energy estimation in system-on-a-chip designs

Optimality and scalability study of existing placement algorithms

Efficient loop-back testing of on-chip ADCs and DACs

Capturing and analyzing requirement: in case of software and applying to hardware

Semi-formal test generation and resolving a temporal abstraction problem in practice: industrial application

Congestion driven incremental placement algorithm for standard cell layout

Experience in critical path selection for deep sub-micron delay test and timing validation

Using red-black interval trees in device-level analog placement with symmetry constraints

Low power synthesis of finite state machines with mixed D and T flip-flops

Highly scalable algorithms for rectilinear and octilinear Steiner trees

Routing-aware scan chain ordering

Periodic steady-state analysis of coupled ODE-AE-CGE systems for MOS RF autonomous circuit simulation

Irredundant address bus encoding techniques based on adaptive codebooks for low power

A fast and accurate method for interconnect current calculation

Energy minimization of real-time tasks on variable voltage processors with transition energy overhead

Logic verification based on diagnosis techniques

Event-driven observability enhanced coverage analysis of C programs for functional validation

Accurate prediction of the impact of on-chip inductance on interconnect delay using electrical and physical parameter-based RSF

Temperature-independence-point properties for 0.1μm-scale pocket-implant technologies and the impact on circuit design

Logic optimization for asynchronous speed independent controllers using transduction method

Towards on-chip fault-tolerant communication

Power minimization by clock root gating

Predicting short circuit power from timing models

Enhanced symbolic simulation for efficient verification of embedded array systems

Multi-level placement for large-scale mixed-size IC designs

Optimal reconfiguration sequence management

Design methodology of low-power microprocessors

Interconnect-driven floorplanning by searching alternative packings

Synthesis for SoC architecture using VCores

DARPA's adaptive computing systems program

Design of a scalable RSA and ECC crypto-processor

Quality-driven design by bitwidth optimization for video applications

A highly efficient AES cipher chip

SEA: fast power estimation for micro-architectures

IBM's 50 Million gate ASICs

A novel LCD driver testing technique using logic test channels

A comparison of the RTU hardware RTOS with a hardware/software RTOS

Scan-chain based watch-points for efficient run-time debugging and verification of FPGA designs

Performance-driven multi-level clustering for combinational circuits

On effective criterion of path selection for delay testing

Current-driven wire planning for electromigration avoidance in analog circuits

Don't cares in logic minimization of extended finite state machines

UTACO: a unified timing and congestion optimizing algorithm for standard cell global routing

Multiple test set generation method for LFSR-based BIST

A frequency separation macromodel for system-level simulation of RF circuits

Multi-parametric improvements for embedded systems using code-placement and address bus coding

Calculating the effective capacitance for the RC interconnect in VDSM technologies

Register aware scheduling for distributed cache clustered architecture

Algorithms for compacting error traces

Trace-driven rapid pipeline architecture evaluation scheme for ASIP design

A metric for analyzing effective on-chip inductive coupling

Behavioral modeling of EM devices by selective orthogonal matrix least-squares method

Technology mapping for low leakage power and high speed with hot-carrier effect consideration

Energy-aware mapping for tile-based NoC architectures under performance constraints

BBE: hierarchical computation of 3-D interconnect capacitance with BEM block extraction

RCLK-VJ network reduction with Hurwitz polynomial approximation

Hardware verification using ANSI-C programs as a reference

Selected sequence-pair: an efficient decodable packing representation in linear time using sequence-pair

On improving FPGA routability applying multi-level switch boxes

Design methodology of low-power CMOS RF-ICs

Noise-aware buffer planning for interconnect-driven floorplanning

VCore-based platform for SoC design

Applications of adaptive computing systems for signal processing challenges

A reconfigurable, power-scalable rake receiver IP for W-CDMA

Arbitrary long digit integer sorter HW/SW co-design

Implementation of fast CRC calculation

HyPE: hybrid power estimation for IP-based programmable systems

Silicon virtual prototyping: the new cockpit for nanometer chip design

An implementation of memory-based on-chip analogue test signal generation

Linux kernel customization for embedded systems by using call graph approach

A novel approach for digital waveform compression

Cross talk driven placement

DFT timing design methodology for at-speed BIST

Efficient DDD-based term generation algorithm for analog circuit behavioral modeling

Performance optimization of synchronous control units for datapaths with variable delay arithmetic units

The Y-architecture: yet another on-chip interconnect solution

A seed selection procedure for LFSR-based random pattern generators

Nonlinear distortion analysis via linear-centric models

Memory access pattern analysis and stream cache design for multimedia applications

Reduction of crosstalk noise by optimizing 3-D configuration of the routing grid

Data partitioning for maximal scratchpad usage

Transaction-based waveform analysis for IP selection

A hardware/software partitioning algorithm for SIMD processor cores

Determination of worst-case crosstalk noise for non-switching victims in GHz+ interconnects

Synthesis of high performance low power PTL circuits

Improving boundary element methods for parasitic extraction

Evaluation of multiple-output logic functions using decision diagrams

An extended representation of Q-sequence for optimizing channel-adjacency and routing-cost

An image retrieval system using FPGAs

Minimizing total power by simultaneous Vdd/Vth assignment

Floorplanning with power supply noise avoidance

VCDS tool demonstration

Interactive ray tracing on reconfigurable SIMD MorphoSys

Robust high-performance low-power carry select adder

Design of a CMOS test chip for package models and I/O characteristics verification

An efficient IP-level power model for complex digital circuits

Design flow and methodology for 50M gate ASIC

Delta-sigma modulator based mixed-signal BIST architecture for SoC

Topology selection for energy minimization in embedded networks

A deep submicron power estimation methodology adaptable to variations between power characterization and estimation

VLSI module placement with pre-placed modules and considering congestion using solution space smoothing

An automated method for test model generation from switch level circuits

5Gbps serial link transmitter with pre-emphasis

Integer linear programming-based synthesis of skewed logic circuits

A novel timing-driven global routing algorithm considering coupling effects for high performance circuit design

Efficient BIST design for sequential machines using FiF-FoF values in machine states

Parasitic-aware design and optimization of a fully integrated CMOS wideband amplifier

Design tools for 3-D integrated circuits

An automatic interconnection rectification technique for SoC design integration

A technology mapping algorithm for heterogeneous FPGAs

Non-slicing floorplans with boundary constraints using generalized polish expression

Logic foundry: rapid prototyping of FPGA-based DSP systems

A low power CMOS circuit with Variable Souce Scheme (VSCMOS)

Simultaneous floorplanning and buffer block planning

An overview of a compiler for mapping MATLAB programs onto FPGAs

Full-custom vs. standard-cell design flow: an adder case study

A still image encoder based on adaptive resolution vector quantization employing needless calculation elimination architecture

A hierarchical analysis methodology for chip-level power delivery with realizable model reduction

A path-based timing-driven quadratic placement algorithm

Graph matching-based algorithms for array-based FPGA segmentation design and routing

A new design-for-test technique for reducing SOC test time

A buffer planning algorithm based on dead space redistribution

Issues in debugging highly parallel FPGA-based applications derived from source code

A 500-MHz low-power five-port CMOS register file

Speech encoding and encryption in VLSI

An effective SDRAM power mode management scheme for performance and energy sensitive embedded systems

The design of an i8080A instruction compatible processor with extended memory address

Branch predictor design and performance estimation for a high performance embedded microprocessor

The design of a USB device controller IYOYOYO

MAPLE chip: a processing element for a static scheduling centric multiprocessor

Finding the best system design flow for a high-speed JPEG encoder

The design of PCI bus interface

Low-power digital CDMA receiver

Hardware implementation of an EAN-13 bar code decoder

Error correction circuit using difference-set cyclic code

Design of a digital CDMA receiver

Standard cell libraries with various driving strength cells for 0.13, 0.18 and 0.35 μm technologies

A nearest-hamming-distance search memory with fully parallel mixed digital-analog match circuitry

Optimality and scalability study of existing placement algorithms

Content Provider	ACM Digital Library
Author	Chang, Chin-Chih Cong, Jason Xie, Min
Abstract	Placement is an important step in the overall IC design process in DSM technologies, as it defines the on-chip interconnects, which have become the bottleneck in determining circuit performance. The rapidly increasing design complexity, combined with the demand for the capability of handling nearly flattened designs for physical hierarchy generation, poses significant challenges to existing placement algorithms. There are very few studies on understanding the optimality and scalability of placement algorithms, due to the limited sizes of existing benchmarks and limited knowledge of optimal solutions. The contribution of this paper includes two parts: 1) We implemented an algorithm for generating synthetic benchmarks that have known optimal wirelengths and can match any given net distribution vector. 2) Using benchmarks of 10K to 2M placeable modules with known optimal solutions, we studied the optimality and scalability of three state-of-the-art placers, Dragon [4], Capo [1], mPL [24] from academia, and one leading edge industrial placer, QPlace [5] from Cadence. For the first time our study reveals the gap between the results produced by these tools versus true optimal solutions. The wirelengths produced by these tools are 1.66 to 2.53 times the optimal in the worst cases, and are 1.46 to 2.38 times the optimal on the average. As for scalability, the average solution quality of each tool deteriorates by an additional 4% to 25% when the problem size increases by a factor of 10. These results indicate significant room for improvement in existing placement algorithms.
Starting Page	621
Ending Page	627
Page Count	7
File Format	PDF
ISBN	0780376609
DOI	10.1145/1119772.1119914
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2003-01-21
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