Linear time algorithm to find all relocation positions for EUV defect mitigation

Due to the absence of defect-free blanks in extreme ultraviolet (EUV) lithography, defect mitigation is necessary before mass production. One effective defect mitigation approach is to cover defects by device features, such that the defects will no longer be printable. Normally die size is much smaller than the exposure field on the blank, such that one blank can accommodate multiple copies of a die, each of which can be placed independently within the exposure field. For thorough utilization of blank area, the number of valid dies that are not impacted by any defects should be maximized. To do so, all relocation positions to place a single valid die on a defective blank must be determined first [1]. To the best of our knowledge, no existing work can find all relocation positions throughout the whole blank in a reasonable amount of time. In this paper, we develop an efficient algorithm to solve this problem. The time complexity of our algorithm is linear in the number of features in the die. Experimental results with full die layouts generated from a standard cell library validate the efficiency of our algorithm. Comparing to the algorithm in [2] which runs more than one week without termination, our algorithm only takes several hours to find all relocation positions for a die with millions of features.