A novel algorithm for automatic arrays detection in a layout

Integrated circuits suffer from serious layout printability issues associated to the lithography manufacturing process. Regular layout designs are emerging as alternative solutions to help reducing these systematic sub-wavelength lithography variations. From CAD point of view, regular layouts can be treated as repeated patterns that are arranged in arrays. In most modern mask synthesis and verification tools, cell based hierarchical processing has been able to identify repeating cells by analyzing the design's cell placement; however, there are some routing levels which are not inside the cell and yet they create an array-like structure because of the underlying topologies which could be exploited by detecting repeated patterns in layout thus reducing simulation run-time by simulating only the representing cells and then restore all the simulation results in their corresponding arrays. The challenge is to make the array detection and restoration of the results a very lightweight operation to fully realize the benefits of the approach. A novel methodology for detecting repeated patterns in a layout is proposed. The main idea is based on translating the layout patterns into string of symbols and construct a "Symbolic Layout". By finding repetitions in the symbolic layout, repeated patterns in the drawn layout are detected. A flow for layout reduction based on arrays-detection followed by pattern-matching is discussed. Run time saving comes from doing all litho simulations on the base-patterns only. The pattern matching is then used to restore all the simulation results over the arrays. The proposed flow shows 1.4x to 2x run time enhancement over the regular litho simulation flow. An evaluation for the proposed flow in terms of coverage and run-time is drafted.