Show simple item record

dc.contributor.authorGören, S.
dc.contributor.authorUğurdağ, Hasan Fatih
dc.contributor.authorPalaz, O.
dc.date.accessioned2012-08-17T07:37:24Z
dc.date.available2012-08-17T07:37:24Z
dc.date.issued2011-08
dc.identifier.issn1550-4832
dc.identifier.urihttps://hdl.handle.net/10679/239
dc.identifier.urihttp://dl.acm.org/citation.cfm?id=2000502.2000505
dc.descriptionDue to copyright restrictions, the access to the full text of this article is only available via subscription.en_US
dc.description.abstractNanocrossbars (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.isoengen_US
dc.publisherACMen_US
dc.relation.ispartofACM Journal on Emerging Technologies in Computing Systems
dc.rightsrestrictedAccess
dc.titleDefect-aware nanocrossbar logic mapping through matrix canonization using two-dimensional radix sorten_US
dc.typeArticleen_US
dc.peerreviewedyesen_US
dc.publicationstatuspublisheden_US
dc.contributor.departmentÖzyeğin University
dc.contributor.authorID(ORCID 0000-0002-6256-0850 & YÖK ID 118293) Uğurdağ, Fatih
dc.contributor.ozuauthorUğurdağ, Hasan Fatih
dc.identifier.volume7
dc.identifier.issue3
dc.identifier.startpage1
dc.identifier.endpage16
dc.identifier.wosWOS:000295977400003
dc.identifier.doi10.1145/2000502.2000505
dc.subject.keywordsDesignen_US
dc.subject.keywordsReliabilityen_US
dc.subject.keywordsBipartite subgraph isomorphismen_US
dc.subject.keywordsNanotechnologyen_US
dc.subject.keywordsReconfigurable architecturesen_US
dc.identifier.scopusSCOPUS:2-s2.0-80051970962
dc.contributor.authorMale1


Files in this item

FilesSizeFormatView

There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record


Share this page