Memory-efficient interconnect optimization

Minghorng Lai, D. F. Wong

Research output: Chapter in Book/Report/Conference proceedingConference contribution


Interconnect design has emerged as one of the major challenges facing chip designers as VLSI manufacturing progresses and gate sizes scale down. Dynamic programming (DP) is an efficient and robust technique for finding optimal solutions to interconnect optimization problems in VLSI design. However, DP's huge memory requirement often limits its effectiveness and sometimes, due to limited storage resources, even makes it impossible to solve a problem of practical size. Since interconnect optimization is often a subprocess embedded in an upper level design procedure, a memory and time efficient implementation of DP can be very favorable to circuit designers. In this paper, we develop a new memory-efficient dynamic programming approach to interconnect optimization problems. Our method utilizes selective storage and recomputation technique. This memory and time efficient algorithm speeds up the dynamic programming method without compromising solution quality. Experiments show tremendous saving, both in storage and time, over traditional dynamic programming algorithms. Our novel approach can also be generalized for other VLSI applications using DP algorithms.

Original languageEnglish (US)
Title of host publicationProceedings of the ASP-DAC 2001
Subtitle of host publicationAsia and South Pacific Design Automation Conference 2001
PublisherInstitute of Electrical and Electronics Engineers Inc.
Number of pages5
ISBN (Electronic)0780366336
StatePublished - 2001
Externally publishedYes
EventAsia and South Pacific Design Automation Conference 2001, ASP-DAC 2001 - Yokohama, Japan
Duration: Jan 30 2001Feb 2 2001

Publication series

NameProceedings of the Asia and South Pacific Design Automation Conference, ASP-DAC


OtherAsia and South Pacific Design Automation Conference 2001, ASP-DAC 2001


  • Computer aided manufacturing
  • Delay systems
  • Design optimization
  • Dynamic programming
  • Heuristic algorithms
  • Integrated circuit interconnections
  • Production
  • Robustness
  • Very large scale integration
  • Wire

ASJC Scopus subject areas

  • Computer Science Applications
  • Computer Graphics and Computer-Aided Design
  • Electrical and Electronic Engineering


Dive into the research topics of 'Memory-efficient interconnect optimization'. Together they form a unique fingerprint.

Cite this