Name
Title | ||
|---|---|---|
Defect-Aware Nanocrossbar Logic Mapping through Matrix Canonization Using Two-Dimensional Radix Sort |
Abstract | ||
|---|---|---|
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. |
Year | DOI | Venue |
|---|---|---|
2011 | 10.1145/2000502.2000505 | JETC |
Keywords | Field | DocType |
extreme logic density,logic mapping work,logic mapping,stuck-closed fault,bipartite subgraph isomorphism,bipartite graph,defect map,heuristic kns-2ds,defect-aware nanocrossbar logic mapping,two-dimensional radix sort,bsgi problem,graph node,matrix canonization,nanowires,regular graph,2 dimensional,adjacency matrix,nanotechnology,chip | Graph canonization,Adjacency matrix,Computer science,Bipartite graph,Radix sort,Algorithm,Induced subgraph isomorphism problem,3-dimensional matching,Blossom algorithm,Subgraph isomorphism problem | Journal |
Volume | Issue | ISSN |
7 | 3 | 1550-4832 |
Citations | PageRank | References |
8 | 0.53 | 13 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Sezer Gören | 1 | 64 | 11.62 |
| H. Fatih Ugurdag | 2 | 52 | 11.28 |
| Okan Palaz | 3 | 10 | 1.24 |