Memory-efficient interconnect optimization

Minghorng Lai, D. F. Wong

Research output: Chapter in book/report/conference proceedingConference proceedingpeer-review


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
Title of host publicationProceedings of The 6th Asia and South Pacific Design Automation Conference, ASP-DAC 2001
Place of PublicationUnited States
PublisherAssociation for Computing Machinery (ACM)
Number of pages5
ISBN (Print)9780780366343
Publication statusPublished - Jan 2001
Event6th Asia and South Pacific Design Automation Conference, ASP-DAC 2001 - Conference Center, Pacifico Yokohama, Yokohama, Japan
Duration: 30 Jan 20012 Feb 2001 (Conference website ) (Conference program) (Conference proceedings)

Publication series

NameProceedings of The Asia and South Pacific Design Automation Conference, ASP-DAC
ISSN (Print)2153-6961
ISSN (Electronic)2153-697X


Conference6th Asia and South Pacific Design Automation Conference, ASP-DAC 2001
Internet address


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

Cite this