376.kdtree
SPEC Benchmark Description File

Benchmark Name

376.kdtree

Benchmark Author

R. Brown

Benchmark Program General Category

Sorting and Searching

Benchmark Description

The program builds a k-d tree using random coordinate points, then searches the k-d tree for points that are proximate to each point in the tree.

The build phase is single threaded, but the search phase is multi-threaded using the OpenMP task directive.

The points that are sorted into the tree are defined using a random number gener ator to generate either 3D (x,y,z) or 4D (x,y,z,w) points that are stored one large 2 D array, xyzw. In order to build the k-d tree, four index arrays xi, yi, zi and wi are created then heap-sorted using the x, y, z and w coordinate data from the xy zw array. The k-d tree is a balanced tree, and is built in O[n*log(n)] time.

Once the k-d tree is built, the k-d tree is walked to visit each point, and that point is used as a query point to search the k-d tree for all other points that lie within a specific radius of that query point. The default value for that radius is one-tenth the range of the random numbers. The total number of points found by using each point successively as a query point, as well as the total execution time, are reported. Note that the walking and searching of the k-d tree imply two recursive traversals of the k-d tree.

Input Description

Input parameters

1. n = 100000 (default), the number of points to generate
2. cutoffdivisor = 10 (default), the number by which to divide the range of random numbers to obtain the radius to search
3. maxdepth = 2 (default), the number of levels from the root of the k-d tree where the OpenMP task directive will immediately execute the child task that it creates, instead of adding that child task to a queue

Output Description

The program returns the number of points found to meet the input criteria.

Programming Language

C++

Known portability issues

None

Reference