A hashing mechanism for rule-based decomposition in Double Patterning Photolithography

In order for the semiconductor industry to continue to follow Moore´s law, both designers and foundries needed to proceed to the 22nm nodes. However, this was stalled due to the delay of the deployment of Extreme Ultra-Violet (EUV) technologies. To counteract this delay, a new technology called Double Patterning Photolithography has emerged. This technology necessitates the effective automation of layout decomposition or splitting. In this paper, we propose a hashing mechanism that can be adopted as a basis for a rule-based splitting algorithm. Results have proven this mechanism as a valuable addition to the Double Patterning decomposition techniques. Our analysis and results show that this hashing technique has an approximately linear runtime.