Routing wires with non-uniform width and spacing in data paths

B. Krishna; Chien Yi Roger Chen; N. K. Sehgal

doi:10.1109/ICM.2000.884811

Routing wires with non-uniform width and spacing in data paths

B. Krishna, Chien Yi Roger Chen, N. K. Sehgal

Department of Electrical Engineering & Computer Science

Research output: Chapter in Book/Entry/Poem › Conference contribution

Abstract

Datapath layout designs exhibit special layout properties in that most wires connect one stage to another and are straight wires. Use of track based routing algorithms suffices for the routing needs of the bit-lines. The left edge algorithm (LEA) may be used for this purpose. With the increase in performance requirements for deep sub-micron datapath designs, the use of nonuniform wire widths and spacing is becoming necessary and using LEA is not feasible. This paper defines the datapath bit-line assignment problem. We then present a heuristic algorithm that achieves optimal results in most test cases when the wire widths are nonuniform. The time complexity of our solution is O(NlogN), where N is the number of bit-wire segments to be assigned.

Original language	English (US)
Title of host publication	Proceedings of the International Conference on Microelectronics, ICM
Publisher	Institute of Electrical and Electronics Engineers Inc.
Pages	85-88
Number of pages	4
Volume	2000-January
ISBN (Print)	0780366433
DOIs	https://doi.org/10.1109/ICM.2000.884811
State	Published - 1999
Event	11th International Conference on Microelectronics, ICM 1999 - Kuwait City, Kuwait Duration: Nov 22 1999 → Nov 24 1999

Other

Other	11th International Conference on Microelectronics, ICM 1999
Country/Territory	Kuwait
City	Kuwait City
Period	11/22/99 → 11/24/99

Keywords

Crosstalk
Data engineering
Delay
Design engineering
Educational institutions
Heuristic algorithms
Routing
Signal design
Testing
Wires

ASJC Scopus subject areas

Electrical and Electronic Engineering

Access to Document

10.1109/ICM.2000.884811

Cite this

Krishna, B, Chen, CYR & Sehgal, NK 1999, Routing wires with non-uniform width and spacing in data paths. in Proceedings of the International Conference on Microelectronics, ICM. vol. 2000-January, 884811, Institute of Electrical and Electronics Engineers Inc., pp. 85-88, 11th International Conference on Microelectronics, ICM 1999, Kuwait City, Kuwait, 11/22/99. https://doi.org/10.1109/ICM.2000.884811

@inproceedings{9a4052599ae94aa4bf5d7f721dcdd50f,

title = "Routing wires with non-uniform width and spacing in data paths",

abstract = "Datapath layout designs exhibit special layout properties in that most wires connect one stage to another and are straight wires. Use of track based routing algorithms suffices for the routing needs of the bit-lines. The left edge algorithm (LEA) may be used for this purpose. With the increase in performance requirements for deep sub-micron datapath designs, the use of nonuniform wire widths and spacing is becoming necessary and using LEA is not feasible. This paper defines the datapath bit-line assignment problem. We then present a heuristic algorithm that achieves optimal results in most test cases when the wire widths are nonuniform. The time complexity of our solution is O(NlogN), where N is the number of bit-wire segments to be assigned.",

keywords = "Crosstalk, Data engineering, Delay, Design engineering, Educational institutions, Heuristic algorithms, Routing, Signal design, Testing, Wires",

author = "B. Krishna and Chen, {Chien Yi Roger} and Sehgal, {N. K.}",

year = "1999",

doi = "10.1109/ICM.2000.884811",

language = "English (US)",

isbn = "0780366433",

volume = "2000-January",

pages = "85--88",

booktitle = "Proceedings of the International Conference on Microelectronics, ICM",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

note = "11th International Conference on Microelectronics, ICM 1999 ; Conference date: 22-11-1999 Through 24-11-1999",

}

TY - GEN

T1 - Routing wires with non-uniform width and spacing in data paths

AU - Krishna, B.

AU - Chen, Chien Yi Roger

AU - Sehgal, N. K.

PY - 1999

Y1 - 1999

N2 - Datapath layout designs exhibit special layout properties in that most wires connect one stage to another and are straight wires. Use of track based routing algorithms suffices for the routing needs of the bit-lines. The left edge algorithm (LEA) may be used for this purpose. With the increase in performance requirements for deep sub-micron datapath designs, the use of nonuniform wire widths and spacing is becoming necessary and using LEA is not feasible. This paper defines the datapath bit-line assignment problem. We then present a heuristic algorithm that achieves optimal results in most test cases when the wire widths are nonuniform. The time complexity of our solution is O(NlogN), where N is the number of bit-wire segments to be assigned.

AB - Datapath layout designs exhibit special layout properties in that most wires connect one stage to another and are straight wires. Use of track based routing algorithms suffices for the routing needs of the bit-lines. The left edge algorithm (LEA) may be used for this purpose. With the increase in performance requirements for deep sub-micron datapath designs, the use of nonuniform wire widths and spacing is becoming necessary and using LEA is not feasible. This paper defines the datapath bit-line assignment problem. We then present a heuristic algorithm that achieves optimal results in most test cases when the wire widths are nonuniform. The time complexity of our solution is O(NlogN), where N is the number of bit-wire segments to be assigned.

KW - Crosstalk

KW - Data engineering

KW - Delay

KW - Design engineering

KW - Educational institutions

KW - Heuristic algorithms

KW - Routing

KW - Signal design

KW - Testing

KW - Wires

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

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

U2 - 10.1109/ICM.2000.884811

DO - 10.1109/ICM.2000.884811

M3 - Conference contribution

AN - SCOPUS:84949760233

SN - 0780366433

VL - 2000-January

SP - 85

EP - 88

BT - Proceedings of the International Conference on Microelectronics, ICM

PB - Institute of Electrical and Electronics Engineers Inc.

T2 - 11th International Conference on Microelectronics, ICM 1999

Y2 - 22 November 1999 through 24 November 1999

ER -

Routing wires with non-uniform width and spacing in data paths

Abstract

Other

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this