Defect- and Variation-Tolerant Logic Mapping in Nanocrossbar Using Bipartite Matching and Memetic Algorithm
Defect- and Variation-Tolerant Logic Mapping in Nanocrossbar Using Bipartite Matching and Memetic Algorithm
复制标题
DOI：
10.1109/tvlsi.2016.2530898
复制
发表时间：
2016-03
影响因子：
2.8
通讯作者：
Bo Yuan;Bin Li;Huanhuan Chen;X. Yao
中科院分区：
文献类型：
--
作者：
Bo Yuan;Bin Li;Huanhuan Chen;X. Yao
高缺陷密度和极端的参数变化使得在基于交叉杆的纳米架构中实现可靠的逻辑功能变得非常困难。这是一个主要的设计挑战，同时容忍缺陷和变化，这样的架构。提出了一种基于二分匹配和模因算法的方法，用于解决基于交叉杆的纳米结构中的容差和容差逻辑映射（D/VTLM）问题。该方法通过引入最小-最大权值最大二部匹配（MMW-MBM）和相关的启发式二部匹配方法，大大减小了D/VTLM问题的搜索空间. MMW-MBM是在加权二部图上定义的MBM，其中匹配中的边的最大权具有最小值。此外，缺陷和变化感知的局部搜索（D/VALS）运营商提出了D/VTLM和嵌入在一个全球性的搜索框架。D/VALS算子能够利用从问题实例中提取的领域知识，因此具有更有效地搜索解空间的潜力。与现有的启发式算法、递归算法和模拟退火算法相比，该方法在3位加法器和大量不同规模的随机基准测试中表现出良好的性能.
High defect density and extreme parameter variation make it very difficult to implement reliable logic functions in crossbar-based nanoarchitectures. It is a major design challenge to tolerate defects and variations simultaneously for such architectures. In this paper, a method based on a bipartite matching and memetic algorithm is proposed for defect- and variation-tolerant logic mapping (D/VTLM) problem in crossbar-based nanoarchitectures. In the proposed method, the search space of the D/VTLM problem can be dramatically reduced through the introduction of the min-max weight maximum-bipartite-matching (MMW-MBM) and a related heuristic bipartite matching method. MMW-MBM is defined on a weighted bipartite graph as an MBM, where the maximal weight of the edges in the matching has a minimal value. In addition, a defect- and variation-aware local search (D/VALS) operator is proposed for D/VTLM and embedded in a global search framework. The D/VALS operator is able to utilize the domain knowledge extracted from problem instances and, thus, has the potential to search the solution space more efficiently. Compared with the state-of-the-art heuristic and recursive algorithms, and a simulated annealing algorithm, the good performance of our proposed method is verified on a 3-bit adder and a large set of random benchmarks of various scales.