Algorithmic study on the routing reliability problem

Qiang Ma, Zigang Xiao, Martin D.F. Wong

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

3 Citations (Scopus)


Conventional CMOS devices are facing an increasing number of challenges as the feature sizes scale down. In the meantime, new nanoscale materials, like graphene nanoribbons (GNR), have been shown to have large integration capability, and thus will probably replace CMOS devices in the future. However, in practice, the GNR wire segments can have a connection defective rate. Particularly, each wire segment has a survival probability, and thus has a chance to fail. This makes the routing in traditional ways very unreliable. In this paper, we study the routing reliability problem and propose an algorithm flow to solve it. Given a s-t routing path on a routing graph, we try to reinforce the reliability of the routing path by adding redundant wiring segments in such a way that its survival probability is maximized with a reasonable overhead of routing resources. Our proposed algorithm flow is two-fold: (1) generation of candidate redundancy segment via min-cost max-flow; (2) optimal selection among the candidates by dynamic programming. The results of extensive experiments confirm the effectiveness and efficiency of our approach.
Original languageEnglish
Title of host publicationThirteenth International Symposium on Quality Electronic Design (ISQED)
PublisherIEEE Canada
Number of pages6
ISBN (Electronic)9781467310352, 9781467310369
ISBN (Print)9781467310345
Publication statusPublished - 19 Mar 2012
EventThirteenth International Symposium on Quality Electronic Design (ISQED) - Santa Clara, CA, USA
Duration: 19 Mar 201221 Mar 2012

Publication series

NameIEEE International Symposium on Quality Electronic Design
ISSN (Print)1948-3287
ISSN (Electronic)1948-3295


ConferenceThirteenth International Symposium on Quality Electronic Design (ISQED)

User-Defined Keywords

  • Redundancy
  • Routing
  • Dynamic programming
  • Joining processes
  • Wires
  • Heuristic algorithms
  • Algorithms
  • routing reliability
  • min-cost flow


Dive into the research topics of 'Algorithmic study on the routing reliability problem'. Together they form a unique fingerprint.

Cite this