NDLI: An O(n log n) algorithm for 1-D tile compaction

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

2015 IEEE/ACM International Conference on Computer-Aided Design (ICCAD)

2014 IEEE/ACM International Conference on Computer-Aided Design (ICCAD)

2013 IEEE/ACM International Conference on Computer-Aided Design (ICCAD)

2012 IEEE/ACM International Conference on Computer-Aided Design (ICCAD)

2011 IEEE/ACM International Conference on Computer-Aided Design (ICCAD)

2010 IEEE/ACM International Conference on Computer-Aided Design (ICCAD)

2009 IEEE/ACM International Conference on Computer-Aided Design - Digest of Technical Papers

2008 IEEE/ACM International Conference on Computer-Aided Design

2007 IEEE/ACM International Conference on Computer-Aided Design

2006 IEEE/ACM International Conference on Computer Aided Design

ICCAD-2005. IEEE/ACM International Conference on Computer-Aided Design, 2005.

IEEE/ACM International Conference on Computer Aided Design, 2004. ICCAD-2004.

ICCAD-2003. International Conference on Computer Aided Design (IEEE Cat. No.03CH37486)

IEEE/ACM International Conference on Computer Aided Design, 2002. ICCAD 2002.

IEEE/ACM International Conference on Computer Aided Design. ICCAD 2001. IEEE/ACM Digest of Technical Papers (Cat. No.01CH37281)

IEEE/ACM International Conference on Computer Aided Design. ICCAD - 2000. IEEE/ACM Digest of Technical Papers (Cat. No.00CH37140)

1999 IEEE/ACM International Conference on Computer-Aided Design. Digest of Technical Papers (Cat. No.99CH37051)

1998 IEEE/ACM International Conference on Computer-Aided Design. Digest of Technical Papers (IEEE Cat. No.98CB36287)

1997 Proceedings of IEEE International Conference on Computer Aided Design (ICCAD)

Proceedings of International Conference on Computer Aided Design

Proceedings of IEEE International Conference on Computer Aided Design (ICCAD)

IEEE/ACM International Conference on Computer-Aided Design

Proceedings of 1993 International Conference on Computer Aided Design (ICCAD)

1992 IEEE/ACM International Conference on Computer-Aided Design

1991 IEEE International Conference on Computer-Aided Design Digest of Technical Papers

1990 IEEE International Conference on Computer-Aided Design. Digest of Technical Papers

1989 IEEE International Conference on Computer-Aided Design. Digest of Technical Papers

Fast test generation for sequential circuits

1989 IEEE International Conference on Computer-Aided Design. Digest of Technical Papers (Cat. No.89CH2805-0)

A powerful global router: based on Steiner min-max trees

Constructing the optimal rectilinear Steiner tree derivable from a minimum spanning tree

A minimum separation algorithm for river routing with bounded number of jogs

Module assignment and interconnect sharing in register-transfer synthesis of pipelined data paths

A new integer linear programming formulation for the scheduling problem in data path synthesis

Scheduling and hardware sharing in pipelined data paths

Automating the diagnosis and the rectification of design errors with PRIAM

Accurate logic simulation in the presence of unknowns

Restricted symbolic evaluation is fast and useful

CRACKER: a general area router based on stepwise reshaping

AGAR: a single-layer router for gate array cell generation

A new approach to sea-of-gates global routing

Manual rescheduling and incremental repair of register-level datapaths

A resource sharing and control synthesis method for conditional branches

A logic synthesis system for VHDL design descriptions

A timing model for static CMOS gates

An accurate timing model for fault simulation in MOS circuits

Event-EMU: an event driven timing simulator for MOS VLSI circuits

Automatic mixed-mode timing simulation

Global refinement for building block layout

Timing driven placement

Combining partitioning and global routing in sea-of-cells design

Layout methods for digital optical computing

Definition and assignment of complex data-paths suited for high throughput applications

Tree-height minimization in pipelined architectures

Synthesis of address generators

Timing models in VAL/VHDL

On the computation of the ranges of detected delay fault sizes

A bounded delay race model

Two-dimensional compaction for placement refinement

A custom cell generation system for double-metal CMOS technology

An O(n log n) algorithm for 1-D tile compaction

An efficient algorithm for layout compaction problem with symmetry constraints

Layout-driven test generation

Optimal granularity of test generation in a distributed system

The critical path for multiple faults

High performance test generation for accurate defect models in CMOS gate array technology

Uninterpreted modeling using the VHSIC hardware description language (VHDL)

Mixed-mode simulation of compiled VHDL programs

Switch-level VHDL descriptions

VHDL modeling for analog-digital hardware designs (VHSIS hardware description language)

An efficient method for parametric yield optimization of MOS integrated circuits

A new methodology for the design centering of IC fabrication processes

Statistical bipolar circuit design using MSTAT

Computation of bus current variance for reliability estimation of VLSI circuits

Boolean minimization and algebraic factorization procedures for fully testable sequential machines

State assignment for initializable synthesis (gate level analysis)

Optimum and heuristic algorithms for finite state machine decomposition and partitioning

State assignment for multilevel logic using dynamic literal estimation

An approach for the yield enhancement of programmable gate arrays

A novel reconfiguration scheme for 2-D processor arrays

Fault detection and location in reconfigurable VLSI arrays

Optimal wafer probe testing and diagnosis of k-out-of-n structures

A table look-up model using a 3-D isoparametric shape function with improved convergency

Piecewise approximate circuit simulation

SPECS simulation validation with efficient transient sensitivity computation

Thermal analysis in SPICE

Translating concurrent programs into delay-insensitive circuits

Practicality of state-machine verification of speed-independent circuits

Inserting active delay elements to achieve wave pipelining

A data model and architecture for VLSI/CAD databases

SLIP: a software environment for system level interactive partitioning

A data management interface as part of the framework of an integrated VLSI-design system

DEC's engineering to manufacturing BRIDGE system based on the D-BUS architecture

Optimal layout via Boolean satisfiability

Towards efficient hierarchical designs by ratio cut partitioning

Pin assignment with global routing

On optimal extraction of combinational logic and don't care sets from hardware description languages

PLA decomposition with generalized decoders

An exact minimizer for Boolean relations

WireLisp: combining graphics and procedures in a circuit specification language

Fast incremental netlist compilation of hierarchical schematics

Structure optimization in logic schematic generation

A new approach to optimal cell synthesis

CLEO: a CMOS layout generator

An optimal transistor-chaining algorithm for CMOS cell layout

CETUS-a versatile custom cell synthesizer

Design of sequential machines for efficient test generation

Test generation for highly sequential circuits

FACT-a testability analysis methodology

Analogue circuit optimization in a graphical environment

A manufacturing-oriented environment for synthesis of fabrication processes

Yoda: a framework for the conceptual design VLSI systems

The EVE VLSI information management environment

Interconnection length estimation for optimized standard cell layouts

Early matching of system requirements and package capabilities

A clock distribution scheme for nonsymmetric VLSI circuits

A Newton waveform relaxation algorithm for circuit simulation

PGS and PLUCGS-two new matrix solution techniques for general circuit simulation

Waveform relaxation for transient simulation of two-dimensional MOS devices

Synthesis of delay fault testable combinational logic

On properties of algebraic transformation and the multifault testability of multilevel logic

Consistency and observability invariance in multi-level logic synthesis

An efficient channel routing algorithm for defective arrays

Routing using a pyramid data structure

HAM-a hardware accelerator for multi-layer wire routing

FDT-a design tool for switched capacitor filters

LADIES: an automatic layout system for analog LSI's

Functional comparison of logic designs for VLSI circuits

Specification and verification of VLSI systems

Dynamic redundancy identification in automatic test generation

FANHAT: fanout oriented hierarchical automatic test generation system

Exact critical path tracing fault simulation on massively parallel processor AAP2

High-speed compiled-code simulation of transition faults

An algorithm for hierarchical floorplan design

Constrained floorplan design for flexible blocks

Multi-terrain partitioning and floor-planning for data-path chip (microprocessor) layout

Hierarchical compiled event-driven logic simulation

A model for comparing synchronization strategies for parallel logic-level simulation

Portable parallel logic and fault simulation

Modeling the driving-point characteristic of resistive interconnect for accurate delay estimation

Modeling uncertainty in RC timing analysis

Critical path issue in VLSI design

PACE2: an improved parallel VLSI extractor with parameter extraction

C3DSTAR: a 3D wiring capacitance calculator

The Stickizer: a layout to symbolic converter

A layout defect-sensitivity extractor

Fast two-level logic minimizers for multi-level logic synthesis

New ATPG techniques for logic optimization

SYLON-DREAM: a multi-level network synthesizer

Multi-level logic optimization using binary decision diagrams

TIGER: testability insertion guidance expert system

Fault detection in a testable PLA with low overhead for production testing

Arithmetic and galois checksums

A diagnosis method using pseudo-random vectors without intermediate signatures

[1988] IEEE International Conference on Computer-Aided Design (ICCAD-89) Digest of Technical Papers

An O(n log n) algorithm for 1-D tile compaction

Content Provider	IEEE Xplore Digital Library
Author	Anderson, R. Kahan, S. Schlag, M.
Copyright Year	1989
Description	Author affiliation: Dept. of Comput. Sci., Washington Univ., Seattle, WA, USA (Anderson, R.; Kahan, S.)
Abstract	A simple O(n log n) algorithm is presented for performing one-dimensional tile compaction on a planar constraint network. The algorithm works only on planar constraints networks: those resulting from considering all components to be on single layer. The top and bottom zones in this example attain their minimum widths of 15 only by forcing the other zone to have width 25, while the best configuration has width 20 which is the minimum width of the middle zone. VLSI circuits often result in nonplanar constraint networks, even though interconnect parallel to the direction of compaction is not part of the constraint network. The algorithm could be used to obtain an initial guess at the width, possibly saving several iterations of the more expensive minimum-cost flow method.<>
Starting Page	144
Ending Page	147
File Size	355181
Page Count	4
File Format	PDF
ISBN	0818619864
DOI	10.1109/ICCAD.1989.76923
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	1989-11-05
Publisher Place	USA
Access Restriction	Subscribed
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Tiles Compaction Very large scale integration Iterative algorithms Computer science Iterative methods Geometry Shape
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