A Fast Extraction Algorithm for Defect-Free Subcrossbar in Nanoelectronic Crossbar
A Fast Extraction Algorithm for Defect-Free Subcrossbar in Nanoelectronic Crossbar
复制标题
DOI：
10.1145/2517137
复制
发表时间：
2014-04
期刊：
影响因子：
--
通讯作者：
Bo Yuan;Bin Li
中科院分区：
文献类型：
--
作者：
Bo Yuan;Bin Li
由于新兴纳米电子学的超大规模、高缺陷密度和每芯片设计范式，从实用性的角度来看，容错设计算法的运行时间至关重要。在本文中，提出了一种高效且有效的启发式无缺陷子交叉开关提取算法，该算法通过混合两种最先进算法的启发式方法来提高性能，然后通过显着减少主要循环的数量来显着加快速度。与当前最有效的以高时间复杂度 O(n3) 为代价提高解质量（即获得的无缺陷子交叉开关的大小）的算法相比，所提出的启发式算法的时间复杂度被证明为 O(n2)。使用大量不同规模和缺陷密度的实例，仿真结果表明，所提出的算法可以提供与当前最有效算法类似的高质量解决方案，同时比当前最有效算法消耗更短的运行时间（减少到约1/3至1/5）。
Due to the super scale, high defect density, and per-chip designing paradigm of emerging nanoelectronics, the runtime of the algorithms for defect-tolerant design is of vital importance from the perspective of practicability. In this article, an efficient and effective heuristic defect-free subcrossbar extraction algorithm is proposed which improves performance by mixing the heuristics from two state-of-the-art algorithms and then is speeded up significantly by considerably reducing the number of major loops. Compared with the current most effective algorithm that improves the solution quality (i.e., size of the defect-free subcrossbar obtained) at the cost of high time complexity O(n3), the time complexity of the proposed heuristic algorithm is proved to be O(n2). Using a large set of instances of various scales and defect densities, the simulation results show that the proposed algorithm can offer similar high-quality solutions as the current most effective algorithm while consuming much shorter runtimes (reduced to about 1/3 to 1/5) than the current most effective algorithm.