Back to Search

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

Title	Defect-aware nanocrossbar logic mapping through matrix canonization using two-dimensional radix sort
Author	Gören, S., Uğurdağ, Hasan Fatih, Palaz, O.
Publication Date:	2011-08
Publication Place	- ACM
Subject	Design, Reliability, Bipartite subgraph isomorphism, Nanotechnology, Reconfigurable architectures
Type	Periodical
Language	English
Digital	Yes
Manuscript	No
Library:	Özyeğin University
Library Asset ID	1550-4832
Record ID	3dd829f2-c849-4517-a805-9000e8c7c59f
Library Location	Electrical & Electronics Engineering
Date	2011-08
Notes	Due to copyright restrictions, the access to the full text of this article is only available via subscription.
Sample Text	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

View in source Özyeğin University Özyeğin University - Ottoman library catalog search

Özyeğin University

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

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

Publication Date 2011-08

Publication Place - ACM

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

Type Periodical

Language English

Digital Yes

Manuscript No

Library Özyeğin University

Library Asset ID 1550-4832

Record ID 3dd829f2-c849-4517-a805-9000e8c7c59f

Library Location Electrical & Electronics Engineering

Date 2011-08

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

Sample Text 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