ILP formulations for variation/defect-tolerant logic mapping on crossbar nano-architectures

• DOI: 10.1145/2491680
• Publication Date: 2013-10-03T13:37:30Z
• Authors: Masoud Zamani; Hanieh Mirzaei; Mehdi B. Tahoori
• Keywords: 0103 physical sciences; 01 natural sciences

Several emerging nano-technologies, including crossbar nano-architectures, have recently been studied as possible replacement or supplement to CMOS technology in the future. However, extreme process variation and high failure rates, mainly due to atomic device sizes, are major challenges for crossbar nano-architectures.

This article presents variation- and defect-tolerant logic mapping on crossbar nano-architectures. Since variation/defect-aware mapping is an NP-hard problem, we introduce a set of Integer Linear Programming (ILP) formulations to effectively solve the problem in a reasonable time. The proposed ILP formulations can be used for both diode-based and FET-based crossbars. Experimental results on benchmark circuits show that our approach can reduce the critical-path delay 39% compared to the Simulated Annealing (SA) method. It can also successfully achieve 97% defect-free mapping with 40% defect density. It can tolerate process variations to meet timing constraints in 95% of the cases, compared to only 77% achieved by SA.