A distributed algorithm for layout geometry operations

This paper introduces a novel distributed algorithm for performing layout geometry operations usually found in design rule checking, layout verification and/or mask synthesis. Typically, during the mask synthesis flow, a large number of machines are available to the user. Also, as multiple machines/cores become more ubiquitous, even designers using layout verification tools will have access to a large set of machines. Having an efficient and scalable distributed algorithm for performing sequences of layout geometry operations will be of great value to both the designer and the mask synthesis engineer.

This paper seeks to present such an algorithm. Given a layout and a sequence of layout geometry operations, the layout is divided into several partitions. The given sequence of layout geometry operations is executed in parallel on the different partitions. The partitions are merged in a systematic manner and the sequence of operations is repeated on a suitable set of polygons in these newly derived partitions until a partition that covers the entire layout area is obtained. A key feature of the proposed algorithm is that it is correct-by-construction - i.e., each partition is guaranteed to generate a subset of the correct results. The complete and correct results are generated for each layout geometry operation for the entire layout when the operation completes execution on all the partitions. Results on large industrial layouts are very promising and show good performance and scalability.