Defect-aware nanocrossbar logic mapping through matrix canonization using two-dimensional radix sort

Name: Defect-aware nanocrossbar logic mapping through matrix canonization using two-dimensional radix sort
Author: Gören, S., Uğurdağ, Hasan Fatih, Palaz, O.

İsim	Defect-aware nanocrossbar logic mapping through matrix canonization using two-dimensional radix sort
Yazar	Gören, S., Uğurdağ, Hasan Fatih, Palaz, O.
Basım Tarihi:	2011-08
Basım Yeri	- ACM
Konu	Design, Reliability, Bipartite subgraph isomorphism, Nanotechnology, Reconfigurable architectures
Tür	Süreli Yayın
Dil	İngilizce
Dijital	Evet
Yazma	Hayır
Kütüphane:	Özyeğin Üniversitesi
Demirbaş Numarası	1550-4832
Kayıt Numarası	3dd829f2-c849-4517-a805-9000e8c7c59f
Lokasyon	Electrical & Electronics Engineering
Tarih	2011-08
Notlar	Due to copyright restrictions, the access to the full text of this article is only available via subscription.
Örnek Metin	Nanocrossbars (i.e., nanowire crossbars) offer extreme logic densities but come with very high defect rates; stuck-open/closed, broken nanowires. Achieving reasonable yield and utilization requires logic mapping that is defect-aware even at the crosspoint level. Such logic mapping works with a defect map per each manufactured chip. The problem can be expressed as matching of two bipartite graphs; one for the logic to be implemented and other for the nanocrossbar. This article shows that the problem becomes a Bipartite SubGraph Isomorphism (BSGI) problem within sub-nanocrossbars free of stuck-closed faults. Our heuristic KNS-2DS is an iterative rough canonizer with approximately O(N2) complexity followed by an O(N3) matching algorithm. Canonization brings a partial or full order to graph nodes. It is normally used for solving the regular Graph Isomorphism (GI) problem, while we apply it to BSGI. KNS stands for K-Neighbor Sort and is used for initializing our main contribution 2-Dimensional-Sort (2DS). 2DS operates on the adjacency matrix of a bipartite graph. Radix-2 2DS solves the problem in the absence of stuck-closed faults. With the addition of Radix-3 and our novel Radix-2.5 sort, we solve problems that also have stuck-closed faults. We offer very short runtimes (due to canonization) compared to previous work and have success on all benchmarks. KNS-2DS is also novel from the perspective of BSGI problem as it is based on canonization but not on a search tree with backtracking.
DOI	10.1145/2000502.2000505
Cilt	7

Kaynağa git Özyeğin Üniversitesi

Aramaya Dön

Özyeğin Üniversitesi

Kaynağa git

Defect-aware nanocrossbar logic mapping through matrix canonization using two-dimensional radix sort

Yazar Gören, S., Uğurdağ, Hasan Fatih, Palaz, O.

Basım Tarihi 2011-08

Basım Yeri - ACM

Konu Design, Reliability, Bipartite subgraph isomorphism, Nanotechnology, Reconfigurable architectures

Tür Süreli Yayın

Dil İngilizce

Dijital Evet

Yazma Hayır

Kütüphane Özyeğin Üniversitesi

Demirbaş Numarası 1550-4832

Kayıt Numarası 3dd829f2-c849-4517-a805-9000e8c7c59f

Lokasyon Electrical & Electronics Engineering

Tarih 2011-08

Notlar Due to copyright restrictions, the access to the full text of this article is only available via subscription.

Örnek Metin Nanocrossbars (i.e., nanowire crossbars) offer extreme logic densities but come with very high defect rates; stuck-open/closed, broken nanowires. Achieving reasonable yield and utilization requires logic mapping that is defect-aware even at the crosspoint level. Such logic mapping works with a defect map per each manufactured chip. The problem can be expressed as matching of two bipartite graphs; one for the logic to be implemented and other for the nanocrossbar. This article shows that the problem becomes a Bipartite SubGraph Isomorphism (BSGI) problem within sub-nanocrossbars free of stuck-closed faults. Our heuristic KNS-2DS is an iterative rough canonizer with approximately O(N2) complexity followed by an O(N3) matching algorithm. Canonization brings a partial or full order to graph nodes. It is normally used for solving the regular Graph Isomorphism (GI) problem, while we apply it to BSGI. KNS stands for K-Neighbor Sort and is used for initializing our main contribution 2-Dimensional-Sort (2DS). 2DS operates on the adjacency matrix of a bipartite graph. Radix-2 2DS solves the problem in the absence of stuck-closed faults. With the addition of Radix-3 and our novel Radix-2.5 sort, we solve problems that also have stuck-closed faults. We offer very short runtimes (due to canonization) compared to previous work and have success on all benchmarks. KNS-2DS is also novel from the perspective of BSGI problem as it is based on canonization but not on a search tree with backtracking.

DOI 10.1145/2000502.2000505

Cilt 7