BoolCompare Program Flow

Scanning and Loading

The GDSII (or OASIS) file is read from disk, scanned and an array of quad trees are built to speed up access to data requested by the exploder routine. The entity data is stored in RAM.

  scanning and loading the layout file into memory

Estimating Vertex Count

Using the information extracted during scanning/loading the program now estimates the vertex count in the region of interest specified by the user.

  compute the total vertex count in the region of interest

Computing No of Tiles/Dimensions

Using the user specified region of interest and the number of vertices, the number of tiles and their size is determined. The total number of vertices is divided by 500K vertices/tile.

  using the number of vertices and the size of the region of interest the number of tiles and their dimensions can be determined.

Dynamic Tile Allocation

A number of Boolean threads are started based on available CPU cores. Each thread will make a request for a "window" which is provided from the pool of unprocessed tiles. Each Boolean thread must be fed polygon data by the exploder. Since there is only one exploder but multiple Boolean threads, the general assumption is that the time required to collect the polygons from a tile is much less than the time required to perform the Union/Xor function.

as a Boolean requests a tile to process, the next tile in the queue is supplied; the exploder must extract all the polygons crossing the tile.

Tile Vertex Check

Because the number of tiles was computed using an "average" value, there will be a significant number of tiles which contain much more than than the ideal 500K vertices. When a Boolean thread requests a window and the exploder extracts the geometries it is able to count the vertices. If this value significantly exceeds the target value, the tile is "subdivided" and the new smaller tiles are returned to the pool. This insures that the Boolean processes don't get hung up on the steep part of the computation curve.

each tile is tested for vertex count and subdivided if it is too large.

Download Revision History Price Benchmark