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

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

Research output: Chapter in Book/Entry/PoemConference contribution


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 languageEnglish (US)
Title of host publicationProceedings of the International Conference on Microelectronics, ICM
PublisherInstitute of Electrical and Electronics Engineers Inc.
Number of pages4
ISBN (Print)0780366433
StatePublished - 1999
Event11th International Conference on Microelectronics, ICM 1999 - Kuwait City, Kuwait
Duration: Nov 22 1999Nov 24 1999


Other11th International Conference on Microelectronics, ICM 1999
CityKuwait City


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

ASJC Scopus subject areas

  • Electrical and Electronic Engineering


Dive into the research topics of 'Routing wires with non-uniform width and spacing in data paths'. Together they form a unique fingerprint.

Cite this