A hybrid mapping algorithm for reconfigurable nanoarchitectures
AbstractNanotechnology is emerging as one of the most promising alternative technology toCMOS technology because of its higher density, high speed, lighter, and lower powerconsumption; however, defects are much higher in nanotechnology. Therefore, theneed for defect-tolerance techniques becomes crucial in nanotechnology. This paperaddresses an important intractable problem of finding a maximum size defect-freesub-crossbar in defective nano-scale crossbars for a higher yield. We propose a hybridmapping algorithm by embedding known greedy heuristics with genetic algorithm(GA) to search a large solution space effectively. The proposed algorithm exploits thedegrees of nodes, which play a crucial role in the selection mechanism in the greedymapping heuristics to generate a better quality solution. In the proposed algorithm,GA provides the selection order by generating a new set of degrees that are used by thegreedy mapping heuristic to find a new value for the defect-free sub-crossbar (k). Theexperimental results demonstrate the effectiveness of the proposed hybrid algorithmin finding a large size defect-free sub-crossbar compared to the existing state-of-theartgreedy heuristics.
Al-Yamani, A. A., Ramsundar, S., & Pradhan, D. K. 2007. A defect tolerance scheme for nanotechnology
circuits. IEEE Transactions on Circuits and Systems-I 54(11): 2402-2409.
Bonam, R., Kim, Y. B., & Choi, M. 2007. Defect-tolerant gate macro mapping and placement in clockfree
nanowire crossbar architecture. In Proceedings of the IEEE International Symposium on Defect
and Fault Tolerance in VLSI Systems. pp. 161-169.
Dhodhi, M. K., Ahmad, I., Ahmad. I., & Yatama, A. 2002. An integrated technique for task matching and
scheduling onto distributed heterogeneous computing systems. Journal of Parallel and Distributed
Computing 62(9): 1338-1361.
Ghavami, B., Tajary, A., Raji, M., & Pedram, H. 2010. Defect and variation issues on design mapping
of reconfigurable nanoscale crossbars. In Proceedings of the IEEE Annual Symposium on VLSI.
Gören, S., Ugurdag, H. F., & Palaz, O. 2011. Defect-aware nanocrossbar logic mapping through
matrix canonization using two-dimensional radix sort. ACM Journal on Emerging Technologies in
Computing Systems 7(3), article 12.
Langguth, J., Manne, F., & Sanders, P. 2010. Heuristic initialization for bipartite matching problems.
ACM Journal of Experimental Algorithmics 15, 1.3.
Lim, T. Y. 2014. Structured population genetic algorithms: a literature review. Artificial Intelligence
Review 41: 385-399.
Magun, J. 1998. Greedy matching algorithms, an experimental study. Journal of Experimental
Algorithmics 3, 6.
Paul, S., & Bhunia, S. 2012. A scalable memory-based reconfigurable computing framework for
nanoscale crossbar. IEEE Transaction on Nanotechnology 11(3): 451-462.
Peeters, R. 2003. The maximum edge biclique problem is NP-complete. Journal of Discrete Applied
Mathematics 131(3): 651-654.
Rao, W., Orailoglu, A., & Karri, R. 2006. Topology aware mapping of logic functions onto nanowirebased
crossbar architectures. In Proceedings of the 43rd ACM/IEEE Design Automation Conference.
Shrestha, A. M., Takaoka, A., Tayu, S., & Ueno, S. 2011. On two problems of nano-PLA design. IEICE
Transactions on Information and Systems E94-D(1): 35-41.
Storer, R. H., Wu, D. S. & Vaccari, R. 1992. New search space for sequencing problems with application
to job shop scheduling. Management Science 38(10): 1495-1509.
Su, Y., & Rao, W. 2009. Defect-tolerant logic mapping on nanoscale crossbar architectures and yield
analysis. In Proceedings of the IEEE International Symposium on Defect and Fault Tolerance in
VLSI Systems. pp. 322-330.
Su, Y., & Rao, W. 2014. An integrated framework toward defect-tolerant logic implementation onto
nanocrossbars. IEEE Transaction on Computer-Aided Design of Integrated Circuits and Systems
Tahoori, M. B. 2005. A mapping algorithm for defect-tolerance of reconfigurable nano architectures.
In Proceedings of the IEEE/ACM International Conference on Computer-Aided Design. pp. 668-
Tahoori, M. B. 2006. Application-independent defect tolerance of reconfigurable nanoarchitectures. ACM
Journal on Emerging Technologies in Computing Systems 2(3): 197-218.
Yang, J. S., & Datta, R. 2011. Efficient function mapping in nanoscale crossbar architecture. In
Proceedings of the IEEE International Symposium on Defect and Fault Tolerance in VLSI and
Nanotechnology Systems. pp. 190-196.
Yaun, B., Chen, H., & Yao, X. 2014. A new evolutionary algorithm with structure mutation for
the maximum balanced biclique problem. IEEE Transactions on Cybernetics, DOI:10.1109/
Yuan, B., & Li, B. 2011. Low time complexity defect-tolerance algorithm for nanoelectronic crossbar. InProceedings of the International Conference on Information Science and Technology. pp. 143-148.
Yuan, B., & Li, B. 2014. A fast extraction algorithm for defect-free subcrossbr in nanoelectronic crossbar.
ACM Journal on Emerging Technologies in Computing Systems 10(3), article 25.
Zamani, M., Mirzael, H., & Tahoori, M. B. 2014. ILP formulations for variation/defect-tolerant logic
mapping on crossbar nano-architectures. ACM Journal on Emerging Technologies in Computing
Systems 9(3), article 21.
Zheng, Y., & Huang, C. 2009. Defect-aware logic mapping for nanowire-based programmable logic
arrays via satisfiability. In Proceedings of the Design, Automation & Test in Europe Conference &
Exhibition. pp. 1279-1283.
Zieglar, M., & Stan, M. R. 2003. CMOS/Nano co-design for crossbar-based molecular electronic systems.
IEEE Transactions on Nanotechnology, 2(4): 217-230.