A mapping algorithm for defect-tolerance of reconfigurable nano-architectures

Self-assembled nano-fabrication processes yield regular and reconfigurable devices. However, defect densities in this emerging nanotechnology are higher than those in conventional lithography-based VLSI. In this paper, we present a defect-tolerant design flow to minimize customized post-fabrication design efforts to be performed per chip. We also present a greedy O(n log n) mapping algorithm which makes the connection between defect-unaware design steps and the final defect-aware step. Experiments show that the results obtained by this algorithm are very close to the exact solutions.