Memory-efficient interconnect optimization

Minghorng Lai, Martin D F Wong

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

Abstract

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.
Pages198-202
Number of pages5
ISBN (Electronic)0780366336
DOIs
StatePublished - Jan 1 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
Volume2001-January

Other

OtherAsia and South Pacific Design Automation Conference 2001, ASP-DAC 2001
CountryJapan
CityYokohama
Period1/30/012/2/01

Fingerprint

Dynamic programming
Data storage equipment
Networks (circuits)
Experiments

Keywords

  • 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

Cite this

Lai, M., & Wong, M. D. F. (2001). Memory-efficient interconnect optimization. In Proceedings of the ASP-DAC 2001: Asia and South Pacific Design Automation Conference 2001 (pp. 198-202). [913304] (Proceedings of the Asia and South Pacific Design Automation Conference, ASP-DAC; Vol. 2001-January). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/ASPDAC.2001.913304

Memory-efficient interconnect optimization. / Lai, Minghorng; Wong, Martin D F.

Proceedings of the ASP-DAC 2001: Asia and South Pacific Design Automation Conference 2001. Institute of Electrical and Electronics Engineers Inc., 2001. p. 198-202 913304 (Proceedings of the Asia and South Pacific Design Automation Conference, ASP-DAC; Vol. 2001-January).

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

Lai, M & Wong, MDF 2001, Memory-efficient interconnect optimization. in Proceedings of the ASP-DAC 2001: Asia and South Pacific Design Automation Conference 2001., 913304, Proceedings of the Asia and South Pacific Design Automation Conference, ASP-DAC, vol. 2001-January, Institute of Electrical and Electronics Engineers Inc., pp. 198-202, Asia and South Pacific Design Automation Conference 2001, ASP-DAC 2001, Yokohama, Japan, 1/30/01. https://doi.org/10.1109/ASPDAC.2001.913304
Lai M, Wong MDF. Memory-efficient interconnect optimization. In Proceedings of the ASP-DAC 2001: Asia and South Pacific Design Automation Conference 2001. Institute of Electrical and Electronics Engineers Inc. 2001. p. 198-202. 913304. (Proceedings of the Asia and South Pacific Design Automation Conference, ASP-DAC). https://doi.org/10.1109/ASPDAC.2001.913304
Lai, Minghorng ; Wong, Martin D F. / Memory-efficient interconnect optimization. Proceedings of the ASP-DAC 2001: Asia and South Pacific Design Automation Conference 2001. Institute of Electrical and Electronics Engineers Inc., 2001. pp. 198-202 (Proceedings of the Asia and South Pacific Design Automation Conference, ASP-DAC).
@inproceedings{46b5dbe44f824a14882c1a3b958d459f,
title = "Memory-efficient interconnect optimization",
abstract = "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.",
keywords = "Computer aided manufacturing, Delay systems, Design optimization, Dynamic programming, Heuristic algorithms, Integrated circuit interconnections, Production, Robustness, Very large scale integration, Wire",
author = "Minghorng Lai and Wong, {Martin D F}",
year = "2001",
month = "1",
day = "1",
doi = "10.1109/ASPDAC.2001.913304",
language = "English (US)",
series = "Proceedings of the Asia and South Pacific Design Automation Conference, ASP-DAC",
publisher = "Institute of Electrical and Electronics Engineers Inc.",
pages = "198--202",
booktitle = "Proceedings of the ASP-DAC 2001",
address = "United States",

}

TY - GEN

T1 - Memory-efficient interconnect optimization

AU - Lai, Minghorng

AU - Wong, Martin D F

PY - 2001/1/1

Y1 - 2001/1/1

N2 - 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.

AB - 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.

KW - Computer aided manufacturing

KW - Delay systems

KW - Design optimization

KW - Dynamic programming

KW - Heuristic algorithms

KW - Integrated circuit interconnections

KW - Production

KW - Robustness

KW - Very large scale integration

KW - Wire

UR - http://www.scopus.com/inward/record.url?scp=84949770323&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84949770323&partnerID=8YFLogxK

U2 - 10.1109/ASPDAC.2001.913304

DO - 10.1109/ASPDAC.2001.913304

M3 - Conference contribution

AN - SCOPUS:84949770323

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

SP - 198

EP - 202

BT - Proceedings of the ASP-DAC 2001

PB - Institute of Electrical and Electronics Engineers Inc.

ER -