Algorithmic study on the routing reliability problem

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

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


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 (US)
Title of host publicationProceedings of the 13th International Symposium on Quality Electronic Design, ISQED 2012
Number of pages6
StatePublished - 2012
Event13th International Symposium on Quality Electronic Design, ISQED 2012 - Santa Clara, CA, United States
Duration: Mar 19 2012Mar 21 2012

Publication series

NameProceedings - International Symposium on Quality Electronic Design, ISQED
ISSN (Print)1948-3287
ISSN (Electronic)1948-3295


Other13th International Symposium on Quality Electronic Design, ISQED 2012
Country/TerritoryUnited States
CitySanta Clara, CA


  • Algorithms
  • dynamic programming
  • min-cost flow
  • routing reliability

ASJC Scopus subject areas

  • Hardware and Architecture
  • Electrical and Electronic Engineering
  • Safety, Risk, Reliability and Quality


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

Cite this