Internal:4D Predicates Benchmark

Introduction

In contrast with 3D PODM, 4D-PODM exhibits currently lower efficiency. 4D-PODM non-optimized code achieves only 52% speedup with 12 threads, while 3D PODM achieves liner speedup up to 128 threads.

Optimizations

The most computationally heavy operations for 3D PODM are circumcenter evaluation and cavity expansion. For the former, the use of vector intrinsics will be evaluated for 4D. Vector intrinsics will offer instruction-level parallelism. For the cavity expansion, we expect the same behavior for 4D-PODM since the 4D analogue of in-sphere test used in the Delaunay kernel involves more floating-point operations than in 3D. Also, experimental evaluations show that in 4D the cavities contain many more elements. In 3D, they were around 30 while in 4D the size of a cavity is on average 150 elements. This suggests that there is a good potential for concurrency exploitation at this level, too. In the past the CRTC group attempted to exploit parallelism not only on the cavity level as in 3D PODM, but at even lower: in the element level. This approach did not offer any speedup in 2D. However, in 4D due to the larger size of the cavity, the expectation is that the cost of spawning a (light) thread will be amortized by the intense floating-point operations.

Benchmark Data on replacing CGAL predicates with PCK::GEO Predicates

Benchmark expanding 1000 cavities of points taken from a uniform grid in 3D(4D), OpenMP is used for threading

CGAL		PCK::GEO
Threads	4D	3D	4D	3D
1	23.5415	4.53754	0.215789	0.002668
2	16.1316	3.20129	0.116588	0.005377
3	10.7494	2.16985	0.083455	0.00541
4	8.15238	1.66742	0.076917	0.006209
5	6.54308	1.11567	0.053478	0.007489
6	4.69507	1.01726	0.047275	0.007391
7	4.09177	0.859387	0.047343	0.008369
8	4.55009	5.91685	0.047627	0.008208
9	3.87095	3.3929	0.048159	0.009607
10	3.81792	5.02684	0.049068	0.009702