Fast and scalable parallel layout decomposition in double patterning lithography

For 32/22 nm technology nodes and below, double patterning (DP) lithography has become the most promising interim solutions due to the delay in the deployment of next generation lithography (e.g., EUV). DP requires the partitioning of the layout patterns into two different masks, a procedure called layout decomposition. Layout decomposition is a key computational step that is necessary for double patterning technology. Existing works on layout decomposition are all single-threaded, which is not scalable in runtime and/or memory for large industrial layouts. This paper presents the first window-based parallel layout decomposition methods for improving both runtime and memory consumption. Experimental results are promising and show the presented parallel layout decomposition methods obtain upto 21× speedup in runtime and upto 7.5×reduction in peak memory consumption with acceptable solution quality.