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.

通过将 CPU 数据结构替换为 GPU 并行矩阵运算，提出了一种用于解决多重图案刻蚀技术中面向确切覆盖的布局分解算法的加速方案，实验结果表明，该系统能够实现全尺寸、超快速的布局分解，并且与现有的布局分解方法相比，可以实现超过 10 倍的速度提升而不降低质量。