Defect-Tolerant Logic Mapping on Nanoscale Crossbar Architectures and Yield Analysis

Crossbar architectures are promising in the emerging nanoelectronic environment. However, fabrication processes for nano-scale circuits introduce numerous defects. Logic mapping on these defective nanofabrics thus emerges as a fundamental challenge. We establish a mathematical model for the logic mapping problem, followed by a probabilistic analysis to gain yield information. Since the most challenging part of the problem is the exponential runtime in searching for a solution, we examine the practical perspective of yield where a runtime limit is imposed. Yield improvement can be achieved through one of two ways: adding hardware redundancy by increasing crossbar size or allowing longer runtime. It turns out that correlations in the mapping solution space play an essential role on the complexity of the problem. Therefore, developing effective mechanisms to improve yield requires insights and analysis on correlations in the solution space. The analysis provided in this paper reveals the following points. Even though yield can always be improved through increasing crossbar size, the improvement gained by increasing crossbar size has a theoretical upperbound when a runtime limit is imposed. Consequently, there exists an optimal size for a crossbar to improve yield effectively within a runtime limit. Last but not least, for large-sized logic functions, longer runtime can be invested to improve yield significantly.