Parallelization schemes for polygon operations

Rocky_Tseng

KLayout uses a Quadtree to partition a region, ensuring that each node contains a similar number of polygons. For polygon merging within the same region, is it possible to distribute the leaf nodes of the Quadtree across multiple threads or processes? This approach could enable each thread to independently merge polygons within its assigned node, achieving a balanced workload distribution across threads.

If this method is not generally applicable, I would be interested to know that what parallelization schemes currently supported by KLayout for polygon operations, such as merging, XOR, AND, OR, and NOT.

Thank you.

Matthias

Hi @Rocky_Tseng,

I don't know what to reply here. If the question is "is it possible to ...", then my answer is: sure, but try yourself. I personally don't think that approach has a lot of potential. First, the quad trees are not balanced - that would be a KD tree or similar. Second, not all shapes sit on leaf nodes. Shapes overlapping multiple leaf nodes sit further up in the hierarchy. This means, parallelization may not scale well if you focus on leaf nodes only.

Anyway, if you study the documentation, you will notice that KLayout has the TilingProcessor facility which allows parallelization based on splitting the region of interest into rectangular tiles and working on these individually. This scheme scales well with the number of cores, but still is a flat scheme. That is often prohibitive not because of CPU time, but in terms of memory. An alternative approach is the hierarchical mode (called "deep" in DRC), which often renders better performance on a single CPU already. It allows parallelization (on cells), but usually does not scale well with the number of cores as there is a considerable overhead that is not parallelized. Still deep mode is a favored solution as it has the greatest potential on real circuits.

As a side note, merging is an operation that cannot be confined to a region. Hierarchical processing promotes merged shapes in the hierarchy, but implements real merging. Tiling will merge only within one tile.

I'd suggest to study the effect of these options in the DRC framework, where you can conveniently switch modes.

Matthias

Rocky_Tseng

Hi @Matthias ,

Thanks for your long words, I am working on parallelize the operations and will compare the methods your suggested. Keeping you updated.

Thank you!
Rocky : )