Defect-aware nanocrossbar logic mapping through matrix canonization using two-dimensional radix sort
dc.contributor.author | Gören, S. | |
dc.contributor.author | Uğurdağ, Hasan Fatih | |
dc.contributor.author | Palaz, O. | |
dc.date.accessioned | 2012-08-17T07:37:24Z | |
dc.date.available | 2012-08-17T07:37:24Z | |
dc.date.issued | 2011-08 | |
dc.identifier.issn | 1550-4832 | |
dc.identifier.uri | https://hdl.handle.net/10679/239 | |
dc.identifier.uri | http://dl.acm.org/citation.cfm?id=2000502.2000505 | |
dc.description | Due to copyright restrictions, the access to the full text of this article is only available via subscription. | en_US |
dc.description.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. | en_US |
dc.language.iso | eng | en_US |
dc.publisher | ACM | en_US |
dc.relation.ispartof | ACM Journal on Emerging Technologies in Computing Systems | |
dc.rights | restrictedAccess | |
dc.title | Defect-aware nanocrossbar logic mapping through matrix canonization using two-dimensional radix sort | en_US |
dc.type | Article | en_US |
dc.peerreviewed | yes | en_US |
dc.publicationstatus | published | en_US |
dc.contributor.department | Özyeğin University | |
dc.contributor.authorID | (ORCID 0000-0002-6256-0850 & YÖK ID 118293) Uğurdağ, Fatih | |
dc.contributor.ozuauthor | Uğurdağ, Hasan Fatih | |
dc.identifier.volume | 7 | |
dc.identifier.issue | 3 | |
dc.identifier.startpage | 1 | |
dc.identifier.endpage | 16 | |
dc.identifier.wos | WOS:000295977400003 | |
dc.identifier.doi | 10.1145/2000502.2000505 | |
dc.subject.keywords | Design | en_US |
dc.subject.keywords | Reliability | en_US |
dc.subject.keywords | Bipartite subgraph isomorphism | en_US |
dc.subject.keywords | Nanotechnology | en_US |
dc.subject.keywords | Reconfigurable architectures | en_US |
dc.identifier.scopus | SCOPUS:2-s2.0-80051970962 | |
dc.contributor.authorMale | 1 |
Files in this item
Files | Size | Format | View |
---|---|---|---|
There are no files associated with this item. |
This item appears in the following Collection(s)
Share this page