A hybrid mapping algorithm for reconfigurable nanoarchitectures
Abstract
Nanotechnology 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.References
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.
pp. 173-178.
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.
pp. 723-726.
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
(1): 64-75.
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/
TCYB.2012.2343966.
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.
