Runtime analysis for defect-tolerant logic mapping on nanoscale crossbar architectures

Crossbar architectures are promising in the emerging nanoscale electronic environment. Logic mapping onto highly defective crossbars emerges as a fundamental challenge and defect tolerance techniques therefore become crucially important. In this paper we investigate the most challenging part of the problem - the exponential runtime inevitably involved in finding a valid mapping. Runtime depends on solution density of the searching space. Yet, the complexity of the problem is caused by the correlations in the searching space. When defect rate is trivially low, such impact is negligible. When defect rate increases, correlations drive up runtime by not only decreasing the expectation of solution density, but also increasing the standard deviation. Consequently, runtime improvement can be achieved through means which reduce the correlations in the solution space.