On mismatch number distribution of nanocrossbar logic mapping

Crossbar-based architectures are promising for the future nanoelectronic systems. Due to the inherent unreliability of nanotechnology, logic mapping onto highly defective crossbars needs to be performed on every chip. This posts significant challenge as the mapping problem is NP-complete. The complexity of the defect-tolerant logic mapping problems makes it hard to analyze runtime and model yield. This paper presents a new metric for evaluating the quality of the defect-tolerant logic mapping by tagging each mapping trial with a “score”, namely the mismatch number. Specifically, we look into the mismatch number distribution over: 1) crossbars having the same defect rate, 2) crossbars having the same defect number, and 3) a single crossbar with a given defect pattern. We show that the number of mismatches can be well modeled in probabilistic approaches, and the mismatch number distribution follows Normal/Poisson and Hypergeometric distribution, respectively. This new metric serves as the basis of performing runtime and yield analysis, which are difficult to estimate for logic mapping onto nanocrossbars. More importantly, the quantitative score for each underlying mapping trial serves as the basis in building the reliable nanocrossbar systems.