A hybrid mapping algorithm for reconfigurable nanoarchitectures

摘要

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.