A hybrid mapping algorithm for reconfigurable nanoarchitectures

  • Hessa K. Al-Mutairi Computer Engineering Department, Kuwait University
  • Imtiaz Ahmad Computer Engineering Department, Kuwait University
Keywords: Biclique problem, defect tolerance, genetic algorithm (GA), mapping algorithm, nano-crossbar switches, nanotechnology


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.

Author Biography

Imtiaz Ahmad, Computer Engineering Department, Kuwait University
High level synthesis, scheduling, design autmation


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/


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.

Computer Engineering