Optimal algorithm for minimizing the number of twists in an on-chip bus

Liang Deng; Martin D. F. Wong

doi:10.1109/DATE.2004.1269040

Optimal algorithm for minimizing the number of twists in an on-chip bus

Liang Deng, Martin D. F. Wong

Office of the Provost

Research output: Chapter in book/report/conference proceeding › Conference proceeding › peer-review

2 Citations (Scopus)

Abstract

Complementary bus architecture is used to achieve higher speed and lower power in VLSI chips. However, in deep submicron circuit design, the effects of crosstalk become more and more serious, especially in the bus structure where wires are placed close to each other. Complementary bus architecture with twisted wires can reduce the coupling noise. But in current chip design flow, engineering change order (ECO) happens commonly to meet improvement requirement. Layout changes due to ECO introduce obstacles to the twists, which could reduce the number of twists and increase the coupling noise. In this paper, an ECO algorithm for generating twisted complementary architecture is proposed based on the shortest path algorithm. Our algorithm guarantees to give the minimum number of twists along the bus wires under noise constraints. Experimental results show that the twist patterns generated by our algorithm can effectively reduce the capacitive coupling noises.

Original language	English
Title of host publication	Proceedings of the Design, Automation and Test in Europe Conference and Exhibition, DATE 2004
Editors	Georges Gielen, Joan Figueras
Publisher	IEEE
Pages	1104-1109
Number of pages	6
ISBN (Print)	9780769520858
DOIs	https://doi.org/10.1109/DATE.2004.1269040
Publication status	Published - Feb 2004
Event	2004 Design, Automation and Test in Europe Conference and Exhibition, DATE 2004 - CNIT La Defense, Paris, France Duration: 16 Feb 2004 → 20 Feb 2004 https://past.date-conference.com/proceedings-archive/2004/YEAR.HTM (Conference proceedings)

Publication series

Name	Proceedings of Design, Automation and Test in Europe Conference and Exhibition, DATE
Volume	2
ISSN (Print)	1530-1591

Conference

Conference	2004 Design, Automation and Test in Europe Conference and Exhibition, DATE 2004
Country/Territory	France
City	Paris
Period	16/02/04 → 20/02/04
Internet address	https://past.date-conference.com/proceedings-archive/2004/YEAR.HTM (Conference proceedings)

Scopus Subject Areas

General Engineering

Access to Document

10.1109/DATE.2004.1269040

Cite this

Deng, L., & Wong, M. D. F. (2004). Optimal algorithm for minimizing the number of twists in an on-chip bus. In G. Gielen, & J. Figueras (Eds.), Proceedings of the Design, Automation and Test in Europe Conference and Exhibition, DATE 2004 (pp. 1104-1109). (Proceedings of Design, Automation and Test in Europe Conference and Exhibition, DATE; Vol. 2). IEEE. https://doi.org/10.1109/DATE.2004.1269040

@inproceedings{1128d1d2e08d491b835b5346ee0cf20b,

title = "Optimal algorithm for minimizing the number of twists in an on-chip bus",

abstract = "Complementary bus architecture is used to achieve higher speed and lower power in VLSI chips. However, in deep submicron circuit design, the effects of crosstalk become more and more serious, especially in the bus structure where wires are placed close to each other. Complementary bus architecture with twisted wires can reduce the coupling noise. But in current chip design flow, engineering change order (ECO) happens commonly to meet improvement requirement. Layout changes due to ECO introduce obstacles to the twists, which could reduce the number of twists and increase the coupling noise. In this paper, an ECO algorithm for generating twisted complementary architecture is proposed based on the shortest path algorithm. Our algorithm guarantees to give the minimum number of twists along the bus wires under noise constraints. Experimental results show that the twist patterns generated by our algorithm can effectively reduce the capacitive coupling noises.",

author = "Liang Deng and Wong, {Martin D. F.}",

note = "Funding information: This work was partially supported by the National Science Foundation under grants CCR-0244236 and CCR-0306244. Publisher copyright: {\textcopyright} 2004 IEEE; 2004 Design, Automation and Test in Europe Conference and Exhibition, DATE 2004 ; Conference date: 16-02-2004 Through 20-02-2004",

year = "2004",

month = feb,

doi = "10.1109/DATE.2004.1269040",

language = "English",

isbn = "9780769520858",

series = "Proceedings of Design, Automation and Test in Europe Conference and Exhibition, DATE",

publisher = "IEEE",

pages = "1104--1109",

editor = "Georges Gielen and Joan Figueras",

booktitle = "Proceedings of the Design, Automation and Test in Europe Conference and Exhibition, DATE 2004",

address = "United States",

url = "https://past.date-conference.com/proceedings-archive/2004/YEAR.HTM",

}

Deng, L & Wong, MDF 2004, Optimal algorithm for minimizing the number of twists in an on-chip bus. in G Gielen & J Figueras (eds), Proceedings of the Design, Automation and Test in Europe Conference and Exhibition, DATE 2004. Proceedings of Design, Automation and Test in Europe Conference and Exhibition, DATE, vol. 2, IEEE, pp. 1104-1109, 2004 Design, Automation and Test in Europe Conference and Exhibition, DATE 2004, Paris, France, 16/02/04. https://doi.org/10.1109/DATE.2004.1269040

Optimal algorithm for minimizing the number of twists in an on-chip bus. / Deng, Liang; Wong, Martin D. F.
Proceedings of the Design, Automation and Test in Europe Conference and Exhibition, DATE 2004. ed. / Georges Gielen; Joan Figueras. IEEE, 2004. p. 1104-1109 (Proceedings of Design, Automation and Test in Europe Conference and Exhibition, DATE; Vol. 2).

Research output: Chapter in book/report/conference proceeding › Conference proceeding › peer-review

TY - GEN

T1 - Optimal algorithm for minimizing the number of twists in an on-chip bus

AU - Deng, Liang

AU - Wong, Martin D. F.

PY - 2004/2

Y1 - 2004/2

N2 - Complementary bus architecture is used to achieve higher speed and lower power in VLSI chips. However, in deep submicron circuit design, the effects of crosstalk become more and more serious, especially in the bus structure where wires are placed close to each other. Complementary bus architecture with twisted wires can reduce the coupling noise. But in current chip design flow, engineering change order (ECO) happens commonly to meet improvement requirement. Layout changes due to ECO introduce obstacles to the twists, which could reduce the number of twists and increase the coupling noise. In this paper, an ECO algorithm for generating twisted complementary architecture is proposed based on the shortest path algorithm. Our algorithm guarantees to give the minimum number of twists along the bus wires under noise constraints. Experimental results show that the twist patterns generated by our algorithm can effectively reduce the capacitive coupling noises.

AB - Complementary bus architecture is used to achieve higher speed and lower power in VLSI chips. However, in deep submicron circuit design, the effects of crosstalk become more and more serious, especially in the bus structure where wires are placed close to each other. Complementary bus architecture with twisted wires can reduce the coupling noise. But in current chip design flow, engineering change order (ECO) happens commonly to meet improvement requirement. Layout changes due to ECO introduce obstacles to the twists, which could reduce the number of twists and increase the coupling noise. In this paper, an ECO algorithm for generating twisted complementary architecture is proposed based on the shortest path algorithm. Our algorithm guarantees to give the minimum number of twists along the bus wires under noise constraints. Experimental results show that the twist patterns generated by our algorithm can effectively reduce the capacitive coupling noises.

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

U2 - 10.1109/DATE.2004.1269040

DO - 10.1109/DATE.2004.1269040

M3 - Conference proceeding

AN - SCOPUS:3042558085

SN - 9780769520858

T3 - Proceedings of Design, Automation and Test in Europe Conference and Exhibition, DATE

SP - 1104

EP - 1109

BT - Proceedings of the Design, Automation and Test in Europe Conference and Exhibition, DATE 2004

A2 - Gielen, Georges

A2 - Figueras, Joan

PB - IEEE

T2 - 2004 Design, Automation and Test in Europe Conference and Exhibition, DATE 2004

Y2 - 16 February 2004 through 20 February 2004

ER -

Optimal algorithm for minimizing the number of twists in an on-chip bus

Abstract

Publication series

Conference

Scopus Subject Areas

Access to Document

Other files and links

Fingerprint

Cite this