Algorithmic study on the routing reliability problem

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

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

Abstract

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
Pages483-488
Number of pages6
DOIs
StatePublished - Jul 16 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

Other

Other13th International Symposium on Quality Electronic Design, ISQED 2012
CountryUnited States
CitySanta Clara, CA
Period3/19/123/21/12

Fingerprint

Nanoribbons
Graphene
Wire
Electric wiring
Dynamic programming
Redundancy
Costs
Experiments

Keywords

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

ASJC Scopus subject areas

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

Cite this

Ma, Q., Xiao, Z., & Wong, M. D. F. (2012). Algorithmic study on the routing reliability problem. In Proceedings of the 13th International Symposium on Quality Electronic Design, ISQED 2012 (pp. 483-488). [6187537] (Proceedings - International Symposium on Quality Electronic Design, ISQED). https://doi.org/10.1109/ISQED.2012.6187537

Algorithmic study on the routing reliability problem. / Ma, Qiang; Xiao, Zigang; Wong, Martin D.F.

Proceedings of the 13th International Symposium on Quality Electronic Design, ISQED 2012. 2012. p. 483-488 6187537 (Proceedings - International Symposium on Quality Electronic Design, ISQED).

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

Ma, Q, Xiao, Z & Wong, MDF 2012, Algorithmic study on the routing reliability problem. in Proceedings of the 13th International Symposium on Quality Electronic Design, ISQED 2012., 6187537, Proceedings - International Symposium on Quality Electronic Design, ISQED, pp. 483-488, 13th International Symposium on Quality Electronic Design, ISQED 2012, Santa Clara, CA, United States, 3/19/12. https://doi.org/10.1109/ISQED.2012.6187537
Ma Q, Xiao Z, Wong MDF. Algorithmic study on the routing reliability problem. In Proceedings of the 13th International Symposium on Quality Electronic Design, ISQED 2012. 2012. p. 483-488. 6187537. (Proceedings - International Symposium on Quality Electronic Design, ISQED). https://doi.org/10.1109/ISQED.2012.6187537
Ma, Qiang ; Xiao, Zigang ; Wong, Martin D.F. / Algorithmic study on the routing reliability problem. Proceedings of the 13th International Symposium on Quality Electronic Design, ISQED 2012. 2012. pp. 483-488 (Proceedings - International Symposium on Quality Electronic Design, ISQED).
@inproceedings{559832b813bd44a39924a319faa85641,
title = "Algorithmic study on the routing reliability problem",
abstract = "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.",
keywords = "Algorithms, dynamic programming, min-cost flow, routing reliability",
author = "Qiang Ma and Zigang Xiao and Wong, {Martin D.F.}",
year = "2012",
month = "7",
day = "16",
doi = "10.1109/ISQED.2012.6187537",
language = "English (US)",
isbn = "9781467310369",
series = "Proceedings - International Symposium on Quality Electronic Design, ISQED",
pages = "483--488",
booktitle = "Proceedings of the 13th International Symposium on Quality Electronic Design, ISQED 2012",

}

TY - GEN

T1 - Algorithmic study on the routing reliability problem

AU - Ma, Qiang

AU - Xiao, Zigang

AU - Wong, Martin D.F.

PY - 2012/7/16

Y1 - 2012/7/16

N2 - 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.

AB - 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.

KW - Algorithms

KW - dynamic programming

KW - min-cost flow

KW - routing reliability

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

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

U2 - 10.1109/ISQED.2012.6187537

DO - 10.1109/ISQED.2012.6187537

M3 - Conference contribution

AN - SCOPUS:84863651865

SN - 9781467310369

T3 - Proceedings - International Symposium on Quality Electronic Design, ISQED

SP - 483

EP - 488

BT - Proceedings of the 13th International Symposium on Quality Electronic Design, ISQED 2012

ER -