Fast and scalable parallel layout decomposition in double patterning lithography

• A window-based parallel layout decomposition framework is presented for improving both runtime and memory consumption.
• Two parallel layout decomposition approaches are presented and compared, including maximum independent set-based (MISP) and stochastic optimization-based (SOP) methods.
• MISP obtains notable runtime and memory improvements. SOP further improves the solution quality using the Cross Entropy method.
• An overlapping window-based scheme is presented, which avoids large memory consumption for constructing the whole graph of large layouts.
• The presented parallel methods do not make any assumptions about the machine architecture and hence are very generic.

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.