NDLI: Optimal bus sequencing for escape routing in dense PCBs

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

A fast and high-capacity electromagnetic solution for highspeed IC design

Slot allocation using logical networks for TDM virtual-circuit configuration for network-on-chip

A geometric approach for early power grid verification using current constraints

Fast exact Toffoli network synthesis of reversible logic

A self-adjusting clock tree architecture to cope with temperature variations

Monte-Carlo driven stochastic optimization framework for handling fabrication variability

Incremental component implementation selection: enabling ECO in compositional system synthesis

Data locality enhancement for CMPs

Design, synthesis and evaluation of heterogeneous FPGA with mixed LUTs and macro-gates

Thermal-aware Steiner routing for 3D stacked ICs

Scalable exploration of functional dependency by interpolation and incremental SAT solving

The coming of age of physical synthesis

An incremental learning framework for estimating signal controllability in unit-level verification

Approximation algorithm for the temperature-aware scheduling problem

Can nano-photonic silicon circuits become an INTRA-chip interconnect technology?

Hybrid CEGAR: combining variable hiding and predicate abstraction

A frequency-domain technique for statistical timing analysis of clock meshes

Exploiting symmetry in SAT-based Boolean matching for heterogeneous FPGA technology mapping

Skew aware polarity assignment in clock tree

Low-overhead design technique for calibration of maximum frequency at multiple operating points

Timing variation-aware high-level synthesis

Adaptive post-silicon tuning for analog circuits: concept, analysis and optimization

A methodology for fast and accurate yield factor estimation during global routing

CacheCompress: a novel approach for test data compression with cache for IP embedded cores

ECO timing optimization using spare cells

Equalized interconnects for on-chip networks: modeling and optimization framework

Formal verification at higher levels of abstraction

Analog placement with common centroid constraints

Variation-aware task allocation and scheduling for MPSoC

Sparse and passive reduction of massively coupled large multiport interconnects

MOSFET modeling for 45nm and beyond

Voltage island-driven floorplanning

Yield-driven near-threshold SRAM design

A nonlinear cell macromodel for digital applications

Compact modeling of variational waveforms

Estimation of statistical variation in temporal NBTI degradation and its impact on lifetime circuit performance

BioRoute: a network-flow based routing algorithm for digital microfluidic biochips

An efficient wake-up schedule during power mode transition considering spurious glitches phenomenon

Efficient decoupling capacitance budgeting considering operation and process variations

Novel wire density driven full-chip routing for CMP variation control

Stabilizing schemes for piecewise-linear reduced order models via projection and weighting functions

Impedance extraction for 3-D structures with multiple dielectrics using preconditioned boundary element method

Run-time adaptive on-chip communication scheme

Stochastic extended Krylov subspace method for variational analysis of on-chip power grid networks

A novel synthesis algorithm for reversible circuits

Exploiting STI stress for performance

Gate sizing by Lagrangian relaxation revisited

Exploiting hierarchy and structure to efficiently solve graph coloring as SAT

Mapping model with inter-array memory sharing for multidimensional signal processing

Device and architecture concurrent optimization for FPGA transient soft error rate

Extending systems-on-chip to the third dimension: performance, cost and technological tradeoffs

Incremental learning approach and SAT model for Boolean matching with don't cares

Stimulus generation for constrained random simulation

Procrastination determination for periodic real-time tasks in leakage-aware dynamic voltage scaling systems

Automated refinement checking of concurrent systems

Clustering based pruning for statistical criticality computation under process variations

Combinational and sequential mapping with priority cuts

Efficient multi-layer obstacle-avoiding rectilinear Steiner tree construction

Variation-aware performance verification using at-speed structural test and statistical timing

Early planning for clock skew scheduling during register binding

Sensitivity analysis for oscillators

Archer: a history-driven global routing algorithm

A hybrid scheme for compacting test responses with unknown values

Timing optimization by restructuring long combinatorial paths

IntSim: A CAD tool for optimization of multilevel interconnect networks

Temperature aware microprocessor floorplanning considering application dependent power load

A design flow dedicated to multi-mode architectures for DSP applications

Analysis of large clock meshes via harmonic-weighted model order reduction and port sliding

An ILP algorithm for post-floorplanning voltage-island generation considering power-network planning

Soft-edge flip-flops for improved timing yield: design and optimization

Including inductance in static timing analysis

Multi-layer interconnect performance corners for variation-aware timing analysis

An efficient method to identify critical gates under circuit aging

Performance and power evaluation of a 3D CMOS/nanomaterial reconfigurable architecture

Analysis and optimization of power-gated ICs with multiple power gating configurations

Efficient placement of distributed on-chip decoupling capacitors in nanoscale ICs

Accurate detection for process-hotspots with vias and incomplete specification

Parameterized model order reduction via a two-directional Arnoldi process

Statistical analysis of RF circuits using combined circuit simulator-full wave field solver approach

Using functional independence conditions to optimize the performance of latency-insensitive systems

Parallel domain decomposition for simulation of large-scale power grids

Checking equivalence of quantum circuits and states

Automating post-silicon debugging and repair

An efficient algorithm for statistical circuit optimization using Lagrangian relaxation

Finding linear building-blocks for RTL synthesis of polynomial datapaths with fixed-size bit-vectors

Increasing data-bandwidth to instruction-set extensions through register clustering

Design methodology to trade off power, output quality and error resiliency: application to color interpolation filtering

Strategies for improving the parametric yield and profits of 3D ICs

A performance-driven QBF-based iterative logic array representation with applications to verification, debug and test

Probabilistic decision diagrams for exact probabilistic analysis

The FAST methodology for high-speed SoC/computer simulation

Inductive equivalence checking under retiming and resynthesis

Timing budgeting under arbitrary process variations

A general model for performance optimization of sequential systems

A simultaneous bus orientation and bused pin flipping algorithm

Estimation of delay test quality and its application to test generation

Compatibility path based binding algorithm for interconnect reduction in high level synthesis

Yield-aware analog integrated circuit optimization using geostatistics motivated performance modeling

High-performance routing at the nanometer scale

A selective pattern-compression scheme for power and test-data reduction

Engineering change using spare cells with constant insertion

A fast band-matching technique for interconnect inductance modeling

3D-STAF: scalable temperature and leakage aware floorplanning for three-dimensional integrated circuits

The design and synthesis of a synchronous and distributed MAC protocol for wireless network-on-chip

Principle Hessian direction based parameter reduction with process variation

Module assignment for pin-limited designs under the stacked-Vdd paradigm

Remote activation of ICs for piracy prevention and digital right management

A robust finite-point based gate model considering process variations

An efficient method for statistical circuit simulation

Efficient computation of current flow in signal wires for reliability analysis

Fault-tolerant multi-level logic decoder for nanoscale crossbar memory arrays

Sizing and placement of charge recycling transistors in MTCMOS circuits

A novel technique for incremental analysis of on-chip power distribution networks

TIP-OPC: a new topological invariant paradigm for pixel based optical proximity correction

Efficient VCO phase macromodel generation considering statistical parametric variations

Practical method for obtaining a feasible integer solution in hierarchical layout optimization

Unified adaptivity optimization of clock and logic signals

Enhancing design robustness with reliability-aware resynthesis and logic simulation

Optimal polynomial-time interprocedural register allocation for high-level synthesis and ASIP design

Computation of minimal counterexamples by using black box techniques and symbolic methods

A novel SoC design methodology combining adaptive software and reconfigurable hardware

Timing constraint-driven technology mapping for FPGAs considering false paths and multi-clock domains

Optimal bus sequencing for escape routing in dense PCBs

Efficient path delay test generation based on stuck-at test generation using checker circuitry

Operation chaining asynchronous pipelined circuits

Device-circuit co-optimization for mixed-mode circuit design via geometric programming

BoxRouter 2.0: architecture and implementation of a hybrid and robust global router

Methodology for low power test pattern generation using activity threshold control logic

Simultaneous input vector selection and dual threshold voltage assignment for static leakage minimization

Selective shielding: a crosstalk-free bus encoding technique

Victim alignment in crosstalk aware timing analysis

A methodology for timing model characterization for statistical static timing analysis

The effect of process variation on device temperature in FinFET circuits

Combining static and dynamic defect-tolerance techniques for nanoscale memory systems

Minimizing leakage power in sequential circuits by using mixed $V_{t}$ flip-flops

Architectural power models for SRAM and CAM structures based on hybrid analytical/empirical techniques

A novel intensity based optical proximity correction algorithm with speedup in lithography simulation

Bounding L2 gain system error generated by approximations of the nonlinear vector field

An efficient algorithm for time separation of events in concurrent systems

Untangling twisted nets for bus routing

Modeling, optimization and control of rotary traveling-wave oscillator

Variable domain transformation for linear PAC analysis of mixed-signal systems

Optimal bus sequencing for escape routing in dense PCBs

Content Provider	ACM Digital Library
Author	Wong, Martin D. F. Yan, Tan Ozdal, Muhammet Mustafa Kong, Hui
Abstract	The PCB routing problem has become so difficult that no commercial CAD software can provide an automatic solution for high-end boards. Existing algorithms for escape routing, an important step in PCB routing, are net-centric. Directly applying these algorithms will result in mixing nets of different buses together. But in practice, it is preferred to bundle together nets in a bus. Thus the bus-centric escape routing problem can be naturally divided into two subproblems: (1) finding a subset of buses that can be routed on the same layer without net mixings and crossings, which we refer to as the bus sequencing problem, and (2) finding the escape routing solutions for each chosen bus, which can be solved by a net-centric escape router. In this paper, we solve the bus sequencing problem. We introduce a new optimization problem called the Longest Common Interval Sequence (LCIS) problem and model the bus sequencing problem as an LCIS problem. By using dynamic programming and balanced search tree data structure, we present an LCIS algorithm which can find an optimal solution in O(n log n) time. We also show that O(n log n) is a lower-bound for this problem and thus the time complexity of our algorithm is also the best possible.
Starting Page	390
Ending Page	395
Page Count	6
File Format	PDF
ISBN	1424413826
ISSN	10923152
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2007-11-05
Access Restriction	Subscribed
Content Type	Text
Resource Type	Article
Subject	Computer Graphics and Computer-Aided Design Software Computer Science Applications

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