Multiple patterning lithography (MPL) is regarded as one of the most promising ways of overcoming the resolution limitations of conventional optical lithography due to the delay of next-generation lithography technology. As the feature size continues to decrease, layout decomposition for multiple patterning lithography (MPLD) technology is becoming increasingly crucial for improving the manufacturability in advanced nodes. The decomposition process refers to assigning the layout features to different mask layers according to the design rules and density requirements. When the number of masks $k \geq 3$, the MPLD problems are NP-hard and thus may suffer from runtime overhead for practical designs. However, the number of layout patterns is increasing exponentially in industrial layouts, which hinders the runtime performance of MPLD models. In this research, we substitute the CPU's dance link data structure with parallel GPU matrix operations to accelerate the solution for exact cover-based MPLD algorithms. Experimental results demonstrate that our system is capable of full-scale, lightning-fast layout decomposition, which can achieve more than 10$\times$ speed-up without quality degradation compared to state-of-the-art layout decomposition methods.
翻译:多重图案微影(MPL)被认为是克服传统光刻技术分辨率限制的最有前途的方式之一,由于下一代光刻技术的延迟。随着特征尺寸的不断缩小,在先进节点中,多重图案布局分解(MPLD)技术对于提高可制造性变得越来越重要。分解过程是根据设计规则和密度要求将布局特征分配给不同的掩模层。当掩模数$ k \geq 3$时,MPLD问题是NP困难的,因此可能受到实用设计的运行时开销的影响。然而,工业布局中的布局模式数量呈指数增长,这制约了MPLD模型的运行时性能。在这项研究中,我们用并行GPU矩阵操作替换了CPU的跳舞链数据结构,以加速基于准确覆盖的MPLD算法的解决方案。实验结果表明,我们的系统能够进行全尺寸、超快速的布局分解,相对于现有的布局分解方法,可以实现超过10倍的加速,而没有质量降低。