SDOT

Appearance

Performance: Power Diagrams ​

The cost of the diagram alone, for fixed weights ( the inner loop of every solver ), and of its exact dual.

One power diagram ​

The cost of computing every cell's measure for fixed weights, the inner loop of every solver, per dirac. On the CPU, the same clouds go through CGAL ( Regular_triangulation_2/3, bulk insertion ), which then rebuilds and clips every cell so that both sides give the same result, and through geogram ( Lévy's exploragram: Delaunay triangulation of the lifted seeds, then the cells restricted to a mesh of the box ), whose cell measures match sdot's to 1e-10.

sdot is timed twice. From scratch, like the others: the tree, the diagram and its first measures. Then PREPARED: a Newton solve, a Lloyd step or a gradient flow at fixed positions computes many diagrams on the same diracs, and each new one reuses the tree and the neighbours found by the previous one. CGAL and geogram have nothing to reuse: each new weight vector costs their whole chain again. On the cards ( kernel time, double ), a diagram is a prepared one.

sdotsdot, preparedCGALgeogramsdot, RTX 2080 Ti ( 68 SMs )sdot, H100 ( 132 SMs )ideal scaling
2D uniform, Voronoi101001k10k1248163264128threads · SMssdot, 1 thread: 5.9k cycles, 1.72 µs at 3.42 GHzsdot, 2 threads: 3k cycles, 897 ns at 3.39 GHzsdot, 4 threads: 1.6k cycles, 475 ns at 3.33 GHzsdot, 8 threads: 890 cycles, 273 ns at 3.27 GHzsdot, 16 threads: 570 cycles, 187 ns at 3.04 GHzsdot, 32 threads: 430 cycles, 145 ns at 2.99 GHzsdot, 64 threads: 480 cycles, 166 ns at 2.87 GHzsdot, 96 threads: 420 cycles, 153 ns at 2.71 GHzsdot, 128 threads: 410 cycles, 167 ns at 2.48 GHzsdot, RTX 2080 Ti ( 68 SMs ): 110 cycles, 61.4 ns at 1.86 GHzsdot, H100 ( 132 SMs ): 15 cycles, 7.73 ns at 1.98 GHzsdot, prepared, 1 thread: 4.8k cycles, 1.41 µs at 3.42 GHzsdot, prepared, 2 threads: 2.4k cycles, 711 ns at 3.39 GHzsdot, prepared, 4 threads: 1.2k cycles, 359 ns at 3.33 GHzsdot, prepared, 8 threads: 600 cycles, 185 ns at 3.27 GHzsdot, prepared, 16 threads: 340 cycles, 110 ns at 3.04 GHzsdot, prepared, 32 threads: 180 cycles, 59.5 ns at 2.99 GHzsdot, prepared, 64 threads: 97 cycles, 34 ns at 2.87 GHzsdot, prepared, 96 threads: 73 cycles, 27 ns at 2.71 GHzsdot, prepared, 128 threads: 71 cycles, 28.6 ns at 2.48 GHzsdot, prepared, RTX 2080 Ti ( 68 SMs ): 110 cycles, 57 ns at 1.86 GHzsdot, prepared, H100 ( 132 SMs ): 12 cycles, 6.03 ns at 1.98 GHzCGAL, 1 thread: 5.1k cycles, 1.5 µs at 3.42 GHzCGAL, 2 threads: 4.5k cycles, 1.32 µs at 3.39 GHzCGAL, 4 threads: 4.3k cycles, 1.28 µs at 3.33 GHzCGAL, 8 threads: 3.9k cycles, 1.19 µs at 3.27 GHzCGAL, 16 threads: 3.6k cycles, 1.18 µs at 3.04 GHzCGAL, 32 threads: 3.4k cycles, 1.16 µs at 2.99 GHzCGAL, 64 threads: 3.3k cycles, 1.14 µs at 2.87 GHzCGAL, 96 threads: 3.2k cycles, 1.18 µs at 2.71 GHzCGAL, 128 threads: 2.9k cycles, 1.19 µs at 2.48 GHzgeogram, 1 thread: 8k cycles, 2.34 µs at 3.42 GHzgeogram, 2 threads: 6.4k cycles, 1.89 µs at 3.39 GHzgeogram, 4 threads: 5.2k cycles, 1.56 µs at 3.33 GHzgeogram, 8 threads: 5.3k cycles, 1.62 µs at 3.27 GHzgeogram, 16 threads: 4.7k cycles, 1.55 µs at 3.04 GHzgeogram, 32 threads: 4.2k cycles, 1.42 µs at 2.99 GHzgeogram, 64 threads: 4.1k cycles, 1.43 µs at 2.87 GHzgeogram, 96 threads: 3.5k cycles, 1.31 µs at 2.71 GHzgeogram, 128 threads: 3.2k cycles, 1.28 µs at 2.48 GHz
2D uniform, Laguerre101001k10k1248163264128threads · SMssdot, 1 thread: 6.9k cycles, 2.02 µs at 3.42 GHzsdot, 2 threads: 3.5k cycles, 1.05 µs at 3.39 GHzsdot, 4 threads: 1.9k cycles, 560 ns at 3.33 GHzsdot, 8 threads: 1.1k cycles, 325 ns at 3.27 GHzsdot, 16 threads: 650 cycles, 215 ns at 3.04 GHzsdot, 32 threads: 590 cycles, 197 ns at 2.99 GHzsdot, 64 threads: 860 cycles, 301 ns at 2.87 GHzsdot, 96 threads: 530 cycles, 194 ns at 2.71 GHzsdot, 128 threads: 530 cycles, 213 ns at 2.48 GHzsdot, RTX 2080 Ti ( 68 SMs ): 130 cycles, 67.9 ns at 1.86 GHzsdot, H100 ( 132 SMs ): 18 cycles, 8.92 ns at 1.98 GHzsdot, prepared, 1 thread: 5.5k cycles, 1.61 µs at 3.42 GHzsdot, prepared, 2 threads: 2.7k cycles, 808 ns at 3.39 GHzsdot, prepared, 4 threads: 1.4k cycles, 409 ns at 3.33 GHzsdot, prepared, 8 threads: 680 cycles, 209 ns at 3.27 GHzsdot, prepared, 16 threads: 370 cycles, 122 ns at 3.04 GHzsdot, prepared, 32 threads: 200 cycles, 66.3 ns at 2.99 GHzsdot, prepared, 64 threads: 150 cycles, 53.7 ns at 2.87 GHzsdot, prepared, 96 threads: 130 cycles, 49.1 ns at 2.71 GHzsdot, prepared, 128 threads: 110 cycles, 46.2 ns at 2.48 GHzsdot, prepared, RTX 2080 Ti ( 68 SMs ): 110 cycles, 61.1 ns at 1.86 GHzsdot, prepared, H100 ( 132 SMs ): 13 cycles, 6.58 ns at 1.98 GHzCGAL, 1 thread: 3.7k cycles, 1.09 µs at 3.42 GHzCGAL, 2 threads: 3.3k cycles, 979 ns at 3.39 GHzCGAL, 4 threads: 3.1k cycles, 934 ns at 3.33 GHzCGAL, 8 threads: 2.9k cycles, 893 ns at 3.27 GHzCGAL, 16 threads: 2.7k cycles, 886 ns at 3.04 GHzCGAL, 32 threads: 2.4k cycles, 818 ns at 2.99 GHzCGAL, 64 threads: 2.3k cycles, 812 ns at 2.87 GHzCGAL, 96 threads: 2.3k cycles, 834 ns at 2.71 GHzCGAL, 128 threads: 2.1k cycles, 847 ns at 2.48 GHzgeogram, 1 thread: 7.7k cycles, 2.24 µs at 3.42 GHzgeogram, 2 threads: 6.3k cycles, 1.86 µs at 3.39 GHzgeogram, 4 threads: 6.4k cycles, 1.91 µs at 3.33 GHzgeogram, 8 threads: 5.2k cycles, 1.58 µs at 3.27 GHzgeogram, 16 threads: 4.7k cycles, 1.53 µs at 3.04 GHzgeogram, 32 threads: 4.1k cycles, 1.36 µs at 2.99 GHzgeogram, 64 threads: 3.9k cycles, 1.36 µs at 2.87 GHzgeogram, 96 threads: 3.5k cycles, 1.28 µs at 2.71 GHzgeogram, 128 threads: 3k cycles, 1.21 µs at 2.48 GHz
2D lines, Voronoi301003001k3k10k1248163264128threads · SMssdot, 1 thread: 6.1k cycles, 1.79 µs at 3.42 GHzsdot, 2 threads: 3.6k cycles, 1.06 µs at 3.39 GHzsdot, 4 threads: 2.3k cycles, 687 ns at 3.33 GHzsdot, 8 threads: 1.8k cycles, 543 ns at 3.27 GHzsdot, 16 threads: 1.7k cycles, 550 ns at 3.04 GHzsdot, 32 threads: 1.4k cycles, 477 ns at 2.99 GHzsdot, 64 threads: 1.1k cycles, 401 ns at 2.87 GHzsdot, 96 threads: 1.4k cycles, 501 ns at 2.71 GHzsdot, 128 threads: 1.4k cycles, 556 ns at 2.48 GHzsdot, RTX 2080 Ti ( 68 SMs ): 250 cycles, 132 ns at 1.86 GHzsdot, H100 ( 132 SMs ): 68 cycles, 34.2 ns at 1.98 GHzsdot, prepared, 1 thread: 4.6k cycles, 1.34 µs at 3.42 GHzsdot, prepared, 2 threads: 2.4k cycles, 709 ns at 3.39 GHzsdot, prepared, 4 threads: 1.3k cycles, 380 ns at 3.33 GHzsdot, prepared, 8 threads: 720 cycles, 220 ns at 3.27 GHzsdot, prepared, 16 threads: 470 cycles, 154 ns at 3.04 GHzsdot, prepared, 32 threads: 410 cycles, 136 ns at 2.99 GHzsdot, prepared, 64 threads: 330 cycles, 114 ns at 2.87 GHzsdot, prepared, 96 threads: 280 cycles, 105 ns at 2.71 GHzsdot, prepared, 128 threads: 230 cycles, 93.6 ns at 2.48 GHzsdot, prepared, RTX 2080 Ti ( 68 SMs ): 220 cycles, 119 ns at 1.86 GHzsdot, prepared, H100 ( 132 SMs ): 51 cycles, 26 ns at 1.98 GHzCGAL, 1 thread: 4.4k cycles, 1.28 µs at 3.42 GHzCGAL, 2 threads: 4.1k cycles, 1.21 µs at 3.39 GHzCGAL, 4 threads: 3.9k cycles, 1.17 µs at 3.33 GHzCGAL, 8 threads: 3.7k cycles, 1.14 µs at 3.27 GHzCGAL, 16 threads: 3.4k cycles, 1.12 µs at 3.04 GHzCGAL, 32 threads: 3.4k cycles, 1.13 µs at 2.99 GHzCGAL, 64 threads: 3.3k cycles, 1.15 µs at 2.87 GHzCGAL, 96 threads: 3.2k cycles, 1.19 µs at 2.71 GHzCGAL, 128 threads: 2.8k cycles, 1.14 µs at 2.48 GHzgeogram, 1 thread: 6.3k cycles, 1.83 µs at 3.42 GHzgeogram, 2 threads: 5.3k cycles, 1.57 µs at 3.39 GHzgeogram, 4 threads: 4.9k cycles, 1.48 µs at 3.33 GHzgeogram, 8 threads: 4.4k cycles, 1.33 µs at 3.27 GHzgeogram, 16 threads: 3.9k cycles, 1.29 µs at 3.04 GHzgeogram, 32 threads: 3.6k cycles, 1.19 µs at 2.99 GHzgeogram, 64 threads: 3.2k cycles, 1.12 µs at 2.87 GHzgeogram, 96 threads: 3.2k cycles, 1.18 µs at 2.71 GHzgeogram, 128 threads: 3.1k cycles, 1.24 µs at 2.48 GHz
2D lines, equal areas1003001k3k10k1248163264128threads · SMssdot, 1 thread: 15k cycles, 4.43 µs at 3.42 GHzsdot, 2 threads: 8.2k cycles, 2.41 µs at 3.39 GHzsdot, 4 threads: 4.7k cycles, 1.4 µs at 3.33 GHzsdot, 8 threads: 2.9k cycles, 901 ns at 3.27 GHzsdot, 16 threads: 2.1k cycles, 695 ns at 3.04 GHzsdot, 32 threads: 2.1k cycles, 714 ns at 2.99 GHzsdot, 64 threads: 1.6k cycles, 541 ns at 2.87 GHzsdot, 96 threads: 1.7k cycles, 625 ns at 2.71 GHzsdot, 128 threads: 1.7k cycles, 690 ns at 2.48 GHzsdot, RTX 2080 Ti ( 68 SMs ): 350 cycles, 189 ns at 1.86 GHzsdot, H100 ( 132 SMs ): 85 cycles, 43.1 ns at 1.98 GHzsdot, prepared, 1 thread: 13k cycles, 3.9 µs at 3.42 GHzsdot, prepared, 2 threads: 6.8k cycles, 2 µs at 3.39 GHzsdot, prepared, 4 threads: 3.4k cycles, 1.03 µs at 3.33 GHzsdot, prepared, 8 threads: 1.8k cycles, 546 ns at 3.27 GHzsdot, prepared, 16 threads: 1k cycles, 335 ns at 3.04 GHzsdot, prepared, 32 threads: 780 cycles, 261 ns at 2.99 GHzsdot, prepared, 64 threads: 610 cycles, 213 ns at 2.87 GHzsdot, prepared, 96 threads: 500 cycles, 185 ns at 2.71 GHzsdot, prepared, 128 threads: 390 cycles, 158 ns at 2.48 GHzsdot, prepared, RTX 2080 Ti ( 68 SMs ): 350 cycles, 187 ns at 1.86 GHzsdot, prepared, H100 ( 132 SMs ): 65 cycles, 33 ns at 1.98 GHzCGAL, 1 thread: 3.1k cycles, 900 ns at 3.42 GHzCGAL, 2 threads: 2.9k cycles, 850 ns at 3.39 GHzCGAL, 4 threads: 2.7k cycles, 800 ns at 3.33 GHzCGAL, 8 threads: 2.5k cycles, 770 ns at 3.27 GHzCGAL, 16 threads: 2.2k cycles, 720 ns at 3.04 GHzCGAL, 32 threads: 2.2k cycles, 730 ns at 2.99 GHzCGAL, 64 threads: 2.2k cycles, 770 ns at 2.87 GHzCGAL, 96 threads: 2.1k cycles, 790 ns at 2.71 GHzCGAL, 128 threads: 2.1k cycles, 830 ns at 2.48 GHzgeogram, 1 thread: 6.3k cycles, 1.84 µs at 3.42 GHzgeogram, 2 threads: 5.3k cycles, 1.55 µs at 3.39 GHzgeogram, 4 threads: 5k cycles, 1.51 µs at 3.33 GHzgeogram, 8 threads: 4.4k cycles, 1.36 µs at 3.27 GHzgeogram, 16 threads: 4k cycles, 1.3 µs at 3.04 GHzgeogram, 32 threads: 3.5k cycles, 1.16 µs at 2.99 GHzgeogram, 64 threads: 3.5k cycles, 1.22 µs at 2.87 GHzgeogram, 96 threads: 3.2k cycles, 1.19 µs at 2.71 GHzgeogram, 128 threads: 3k cycles, 1.2 µs at 2.48 GHz
3D uniform, Voronoi3001k3k10k30k100k1248163264128threads · SMssdot, 1 thread: 56k cycles, 16.5 µs at 3.42 GHzsdot, 2 threads: 28k cycles, 8.28 µs at 3.39 GHzsdot, 4 threads: 14k cycles, 4.2 µs at 3.33 GHzsdot, 8 threads: 7.2k cycles, 2.2 µs at 3.27 GHzsdot, 16 threads: 3.7k cycles, 1.22 µs at 3.04 GHzsdot, 32 threads: 2k cycles, 662 ns at 2.99 GHzsdot, 64 threads: 1.2k cycles, 426 ns at 2.87 GHzsdot, 96 threads: 900 cycles, 331 ns at 2.71 GHzsdot, 128 threads: 820 cycles, 332 ns at 2.48 GHzsdot, RTX 2080 Ti ( 68 SMs ): 1.1k cycles, 602 ns at 1.86 GHzsdot, H100 ( 132 SMs ): 180 cycles, 92 ns at 1.98 GHzsdot, prepared, 1 thread: 32k cycles, 9.44 µs at 3.42 GHzsdot, prepared, 2 threads: 16k cycles, 4.74 µs at 3.39 GHzsdot, prepared, 4 threads: 8k cycles, 2.41 µs at 3.33 GHzsdot, prepared, 8 threads: 3.9k cycles, 1.2 µs at 3.27 GHzsdot, prepared, 16 threads: 2k cycles, 666 ns at 3.04 GHzsdot, prepared, 32 threads: 1k cycles, 340 ns at 2.99 GHzsdot, prepared, 64 threads: 550 cycles, 192 ns at 2.87 GHzsdot, prepared, 96 threads: 370 cycles, 138 ns at 2.71 GHzsdot, prepared, 128 threads: 270 cycles, 110 ns at 2.48 GHzsdot, prepared, RTX 2080 Ti ( 68 SMs ): 1.1k cycles, 591 ns at 1.86 GHzsdot, prepared, H100 ( 132 SMs ): 180 cycles, 89.7 ns at 1.98 GHzCGAL, 1 thread: 40k cycles, 11.6 µs at 3.42 GHzCGAL, 2 threads: 29k cycles, 8.49 µs at 3.39 GHzCGAL, 4 threads: 17k cycles, 4.98 µs at 3.33 GHzCGAL, 8 threads: 9.1k cycles, 2.77 µs at 3.27 GHzCGAL, 16 threads: 6.4k cycles, 2.11 µs at 3.04 GHzCGAL, 32 threads: 4.8k cycles, 1.62 µs at 2.99 GHzCGAL, 64 threads: 3.8k cycles, 1.32 µs at 2.87 GHzCGAL, 96 threads: 21k cycles, 7.89 µs at 2.71 GHzCGAL, 128 threads: 65k cycles, 26.2 µs at 2.48 GHzgeogram, 1 thread: 52k cycles, 15.2 µs at 3.42 GHzgeogram, 2 threads: 36k cycles, 10.5 µs at 3.39 GHzgeogram, 4 threads: 27k cycles, 8.13 µs at 3.33 GHzgeogram, 8 threads: 19k cycles, 5.74 µs at 3.27 GHzgeogram, 16 threads: 16k cycles, 5.19 µs at 3.04 GHzgeogram, 32 threads: 14k cycles, 4.71 µs at 2.99 GHzgeogram, 64 threads: 13k cycles, 4.44 µs at 2.87 GHzgeogram, 96 threads: 12k cycles, 4.51 µs at 2.71 GHzgeogram, 128 threads: 15k cycles, 5.9 µs at 2.48 GHz
3D planes, Voronoi1k10k100k1248163264128threads · SMssdot, 1 thread: 54k cycles, 15.6 µs at 3.42 GHzsdot, 2 threads: 27k cycles, 8.09 µs at 3.39 GHzsdot, 4 threads: 14k cycles, 4.21 µs at 3.33 GHzsdot, 8 threads: 7.7k cycles, 2.34 µs at 3.27 GHzsdot, 16 threads: 4.5k cycles, 1.48 µs at 3.04 GHzsdot, 32 threads: 2.8k cycles, 951 ns at 2.99 GHzsdot, 64 threads: 2k cycles, 710 ns at 2.87 GHzsdot, 96 threads: 2.4k cycles, 902 ns at 2.71 GHzsdot, 128 threads: 2.4k cycles, 949 ns at 2.48 GHzsdot, RTX 2080 Ti ( 68 SMs ): 1.1k cycles, 589 ns at 1.86 GHzsdot, H100 ( 132 SMs ): 230 cycles, 114 ns at 1.98 GHzsdot, prepared, 1 thread: 31k cycles, 9.15 µs at 3.42 GHzsdot, prepared, 2 threads: 16k cycles, 4.64 µs at 3.39 GHzsdot, prepared, 4 threads: 7.8k cycles, 2.35 µs at 3.33 GHzsdot, prepared, 8 threads: 4k cycles, 1.23 µs at 3.27 GHzsdot, prepared, 16 threads: 2.2k cycles, 728 ns at 3.04 GHzsdot, prepared, 32 threads: 1.2k cycles, 412 ns at 2.99 GHzsdot, prepared, 64 threads: 770 cycles, 268 ns at 2.87 GHzsdot, prepared, 96 threads: 820 cycles, 304 ns at 2.71 GHzsdot, prepared, 128 threads: 700 cycles, 283 ns at 2.48 GHzsdot, prepared, RTX 2080 Ti ( 68 SMs ): 1.1k cycles, 578 ns at 1.86 GHzsdot, prepared, H100 ( 132 SMs ): 210 cycles, 106 ns at 1.98 GHzCGAL, 1 thread: 39k cycles, 11.3 µs at 3.42 GHzCGAL, 2 threads: 29k cycles, 8.57 µs at 3.39 GHzCGAL, 4 threads: 18k cycles, 5.36 µs at 3.33 GHzCGAL, 8 threads: 11k cycles, 3.33 µs at 3.27 GHzCGAL, 16 threads: 9.1k cycles, 3 µs at 3.04 GHzCGAL, 32 threads: 22k cycles, 7.35 µs at 2.99 GHzCGAL, 64 threads: 91k cycles, 31.9 µs at 2.87 GHzCGAL, 96 threads: 210k cycles, 79.3 µs at 2.71 GHzCGAL, 128 threads: 320k cycles, 128 µs at 2.48 GHzgeogram, 1 thread: 43k cycles, 12.5 µs at 3.42 GHzgeogram, 2 threads: 34k cycles, 9.93 µs at 3.39 GHzgeogram, 4 threads: 28k cycles, 8.47 µs at 3.33 GHzgeogram, 8 threads: 23k cycles, 6.93 µs at 3.27 GHzgeogram, 16 threads: 19k cycles, 6.08 µs at 3.04 GHzgeogram, 32 threads: 17k cycles, 5.58 µs at 2.99 GHzgeogram, 64 threads: 16k cycles, 5.49 µs at 2.87 GHzgeogram, 96 threads: 14k cycles, 5.06 µs at 2.71 GHzgeogram, 128 threads: 16k cycles, 6.61 µs at 2.48 GHz
3D planes, equal volumes1k10k100k1248163264128threads · SMssdot, 1 thread: 88k cycles, 25.7 µs at 3.42 GHzsdot, 2 threads: 44k cycles, 13.1 µs at 3.39 GHzsdot, 4 threads: 23k cycles, 6.78 µs at 3.33 GHzsdot, 8 threads: 12k cycles, 3.69 µs at 3.27 GHzsdot, 16 threads: 6.9k cycles, 2.25 µs at 3.04 GHzsdot, 32 threads: 3.9k cycles, 1.32 µs at 2.99 GHzsdot, 64 threads: 2.6k cycles, 914 ns at 2.87 GHzsdot, 96 threads: 2.9k cycles, 1.05 µs at 2.71 GHzsdot, 128 threads: 2.7k cycles, 1.1 µs at 2.48 GHzsdot, RTX 2080 Ti ( 68 SMs ): 2.8k cycles, 1.51 µs at 1.86 GHzsdot, H100 ( 132 SMs ): 390 cycles, 198 ns at 1.98 GHzsdot, prepared, 1 thread: 66k cycles, 19.3 µs at 3.42 GHzsdot, prepared, 2 threads: 33k cycles, 9.79 µs at 3.39 GHzsdot, prepared, 4 threads: 17k cycles, 4.98 µs at 3.33 GHzsdot, prepared, 8 threads: 8.3k cycles, 2.54 µs at 3.27 GHzsdot, prepared, 16 threads: 4.4k cycles, 1.45 µs at 3.04 GHzsdot, prepared, 32 threads: 2.4k cycles, 803 ns at 2.99 GHzsdot, prepared, 64 threads: 1.5k cycles, 518 ns at 2.87 GHzsdot, prepared, 96 threads: 1.1k cycles, 402 ns at 2.71 GHzsdot, prepared, 128 threads: 1.1k cycles, 447 ns at 2.48 GHzsdot, prepared, RTX 2080 Ti ( 68 SMs ): 2.8k cycles, 1.49 µs at 1.86 GHzsdot, prepared, H100 ( 132 SMs ): 370 cycles, 188 ns at 1.98 GHzCGAL, 1 thread: 40k cycles, 11.6 µs at 3.42 GHzCGAL, 2 threads: 30k cycles, 8.82 µs at 3.39 GHzCGAL, 4 threads: 17k cycles, 5.13 µs at 3.33 GHzCGAL, 8 threads: 11k cycles, 3.45 µs at 3.27 GHzCGAL, 16 threads: 8.4k cycles, 2.77 µs at 3.04 GHzCGAL, 32 threads: 12k cycles, 4.07 µs at 2.99 GHzCGAL, 64 threads: 77k cycles, 27 µs at 2.87 GHzCGAL, 96 threads: 340k cycles, 126 µs at 2.71 GHzCGAL, 128 threads: 350k cycles, 140 µs at 2.48 GHzgeogram, 1 thread: 45k cycles, 13.1 µs at 3.42 GHzgeogram, 2 threads: 34k cycles, 9.98 µs at 3.39 GHzgeogram, 4 threads: 28k cycles, 8.27 µs at 3.33 GHzgeogram, 8 threads: 23k cycles, 6.89 µs at 3.27 GHzgeogram, 16 threads: 18k cycles, 6.07 µs at 3.04 GHzgeogram, 32 threads: 17k cycles, 5.66 µs at 2.99 GHzgeogram, 64 threads: 15k cycles, 5.38 µs at 2.87 GHzgeogram, 96 threads: 14k cycles, 5.31 µs at 2.71 GHzgeogram, 128 threads: 17k cycles, 6.74 µs at 2.48 GHz

Cycles per dirac: the time times the clock, the median of the clocks measured on the machine at that thread count ( the cores' on the CPU, the SMs' on a card ): one run's sample is too noisy. Log-log; hover a point for its time and clock.

On the 128 cores and a uniform cloud of 1e6 diracs, a 2D diagram costs 167 ns per dirac from scratch and 29 ns prepared; a 3D one 332 ns and 110 ns. From scratch, the tree is two thirds of the 2D time on 128 cores: it gains 5× up to 32 threads, then slows down once the threads span both sockets. An H100 brings a prepared diagram down to 6 ns in 2D and 90 ns in 3D, and one from scratch to 8 ns and 92 ns: the card builds its tree in one call, for almost nothing. A 2080 Ti takes 57 ns and 590 ns prepared, 61 ns and 600 ns from scratch: its double units are few ( 13 ns and 270 ns in float ). In float, the cell measures match the double kernel to a median relative error of about 1e-14 in 2D: the mixed mode then finishes the solve in double.

Scaling with the threads ​

A diagram is cut cell by cell, with no shared state. In 3D a prepared diagram gains 86× on 128 cores ( 114× in cycles ). In 2D the cells are cheap and the memory bandwidth stops the gain past 96 cores, at 52× ( 67× in cycles ). On the clustered 2D clouds the cells are uneven and the gain is lower ( 14× to 25× ). CGAL's 2D triangulation is sequential. Its 3D one runs in parallel ( TBB ) and gains 9× up to 64 threads, then slows down once the threads span both sockets: at 128 threads it is twice as slow as on one thread. On the clustered 3D clouds it stops gaining past 16 threads and then does the same. geogram builds the cells in parallel, but its triangulation is sequential in 2D and gains about 3× in 3D, and it is most of the cost.

Scaling with the number of diracs ​

The CPU on all its cores, and each card, from 1e3 to 1e7 uniform diracs, in time per dirac: a flat curve is a cost linear in n.

sdot, EPYC 7763, 128 coressdot, RTX 2080 Tisdot, H100sdot, prepared, EPYC 7763, 128 coressdot, prepared, RTX 2080 Tisdot, prepared, H100CGAL, 32 threads ( its best ), EPYC 7763, 128 coresgeogram, EPYC 7763, 128 cores
2D uniform10 ns100 ns1 µs10 µs1e31e41e51e61e7diracssdot, RTX 2080 Ti, n = 1e3: 982 ns at 1.86 GHzsdot, RTX 2080 Ti, n = 1e4: 146 ns at 1.86 GHzsdot, RTX 2080 Ti, n = 1e5: 27.6 ns at 1.86 GHzsdot, RTX 2080 Ti, n = 1e6: 17.9 ns at 1.86 GHzsdot, RTX 2080 Ti, n = 1e7: 18.5 ns at 1.86 GHzsdot, H100, n = 1e3: 912 ns at 1.98 GHzsdot, H100, n = 1e4: 124 ns at 1.98 GHzsdot, H100, n = 1e5: 17.4 ns at 1.98 GHzsdot, H100, n = 1e6: 6.09 ns at 1.98 GHzsdot, H100, n = 1e7: 6.08 ns at 1.98 GHzsdot, 128 threads, n = 1e3: 26.2 µs at 2.48 GHzsdot, 128 threads, n = 1e4: 3.68 µs at 2.48 GHzsdot, 128 threads, n = 1e5: 583 ns at 2.48 GHzsdot, 128 threads, n = 1e6: 167 ns at 2.48 GHzsdot, 128 threads, n = 1e7: 90.6 ns at 2.48 GHzsdot, prepared, RTX 2080 Ti, n = 1e3: 566 ns at 1.86 GHzsdot, prepared, RTX 2080 Ti, n = 1e4: 91.3 ns at 1.86 GHzsdot, prepared, RTX 2080 Ti, n = 1e5: 18.5 ns at 1.86 GHzsdot, prepared, RTX 2080 Ti, n = 1e6: 13.3 ns at 1.86 GHzsdot, prepared, RTX 2080 Ti, n = 1e7: 14.2 ns at 1.86 GHzsdot, prepared, H100, n = 1e3: 431 ns at 1.98 GHzsdot, prepared, H100, n = 1e4: 63.4 ns at 1.98 GHzsdot, prepared, H100, n = 1e5: 9.32 ns at 1.98 GHzsdot, prepared, H100, n = 1e6: 4.38 ns at 1.98 GHzsdot, prepared, H100, n = 1e7: 4.73 ns at 1.98 GHzsdot, prepared, 128 threads, n = 1e3: 6.55 µs at 2.48 GHzsdot, prepared, 128 threads, n = 1e4: 753 ns at 2.48 GHzsdot, prepared, 128 threads, n = 1e5: 91.9 ns at 2.48 GHzsdot, prepared, 128 threads, n = 1e6: 28.4 ns at 2.48 GHzsdot, prepared, 128 threads, n = 1e7: 16.4 ns at 2.48 GHzCGAL, 32 threads ( its best ), 128 threads, n = 1e3: 1 µs at 2.99 GHzCGAL, 32 threads ( its best ), 128 threads, n = 1e4: 1.3 µs at 2.99 GHzCGAL, 32 threads ( its best ), 128 threads, n = 1e5: 1.12 µs at 2.99 GHzCGAL, 32 threads ( its best ), 128 threads, n = 1e6: 1.14 µs at 2.99 GHzCGAL, 32 threads ( its best ), 128 threads, n = 1e7: 1.16 µs at 2.99 GHzgeogram, 128 threads, n = 1e3: 12.4 µs at 2.48 GHzgeogram, 128 threads, n = 1e4: 2.32 µs at 2.48 GHzgeogram, 128 threads, n = 1e5: 1.2 µs at 2.48 GHzgeogram, 128 threads, n = 1e6: 1.3 µs at 2.48 GHzgeogram, 128 threads, n = 1e7: 1.42 µs at 2.48 GHz
3D uniform100 ns300 ns1 µs3 µs10 µs30 µs1e31e41e51e61e7diracssdot, RTX 2080 Ti, n = 1e3: 647 ns at 1.86 GHzsdot, RTX 2080 Ti, n = 1e4: 384 ns at 1.86 GHzsdot, RTX 2080 Ti, n = 1e5: 272 ns at 1.86 GHzsdot, RTX 2080 Ti, n = 1e6: 289 ns at 1.86 GHzsdot, RTX 2080 Ti, n = 1e7: 315 ns at 1.86 GHzsdot, H100, n = 1e3: 698 ns at 1.98 GHzsdot, H100, n = 1e4: 131 ns at 1.98 GHzsdot, H100, n = 1e5: 75.3 ns at 1.98 GHzsdot, H100, n = 1e6: 69.2 ns at 1.98 GHzsdot, H100, n = 1e7: 73.1 ns at 1.98 GHzsdot, 128 threads, n = 1e3: 31.2 µs at 2.48 GHzsdot, 128 threads, n = 1e4: 4.44 µs at 2.48 GHzsdot, 128 threads, n = 1e5: 957 ns at 2.48 GHzsdot, 128 threads, n = 1e6: 314 ns at 2.48 GHzsdot, 128 threads, n = 1e7: 235 ns at 2.48 GHzsdot, prepared, RTX 2080 Ti, n = 1e3: 304 ns at 1.86 GHzsdot, prepared, RTX 2080 Ti, n = 1e4: 243 ns at 1.86 GHzsdot, prepared, RTX 2080 Ti, n = 1e5: 259 ns at 1.86 GHzsdot, prepared, RTX 2080 Ti, n = 1e6: 282 ns at 1.86 GHzsdot, prepared, RTX 2080 Ti, n = 1e7: 307 ns at 1.86 GHzsdot, prepared, H100, n = 1e3: 202 ns at 1.98 GHzsdot, prepared, H100, n = 1e4: 68 ns at 1.98 GHzsdot, prepared, H100, n = 1e5: 66.6 ns at 1.98 GHzsdot, prepared, H100, n = 1e6: 67 ns at 1.98 GHzsdot, prepared, H100, n = 1e7: 71 ns at 1.98 GHzsdot, prepared, 128 threads, n = 1e3: 9.36 µs at 2.48 GHzsdot, prepared, 128 threads, n = 1e4: 1.43 µs at 2.48 GHzsdot, prepared, 128 threads, n = 1e5: 351 ns at 2.48 GHzsdot, prepared, 128 threads, n = 1e6: 113 ns at 2.48 GHzsdot, prepared, 128 threads, n = 1e7: 101 ns at 2.48 GHzCGAL, 32 threads ( its best ), 128 threads, n = 1e3: 48 µs at 2.99 GHzCGAL, 32 threads ( its best ), 128 threads, n = 1e4: 49.6 µs at 2.99 GHzCGAL, 32 threads ( its best ), 128 threads, n = 1e5: 1.31 µs at 2.99 GHzCGAL, 32 threads ( its best ), 128 threads, n = 1e6: 1.17 µs at 2.99 GHzCGAL, 32 threads ( its best ), 128 threads, n = 1e7: 1.57 µs at 2.99 GHzgeogram, 128 threads, n = 1e3: 20.9 µs at 2.48 GHzgeogram, 128 threads, n = 1e4: 8.72 µs at 2.48 GHzgeogram, 128 threads, n = 1e5: 6.58 µs at 2.48 GHzgeogram, 128 threads, n = 1e6: 5.69 µs at 2.48 GHzgeogram, 128 threads, n = 1e7: 5.88 µs at 2.48 GHz

Time per dirac, the measure of every cell: flat is linear in the number of diracs. Log-log; hover a point for its time.

On a card, a diagram of less than about 1e5 diracs does not fill the SMs, and below 1e4 the launches set its cost. Up there, an H100 computes a prepared 2D diagram in 5 ns per dirac at 1e7 ( float ), and a 3D one in 72 ns; a 2080 Ti in 16 ns and 310 ns. From scratch, the tree adds 1 to 4 ns per dirac.

Exact connectivity ​

sdot is not built for this: its cells are cut in floating point, and two cells may disagree about a vertex where several seeds are almost on a sphere. dual() gives the regular triangulation restricted to the box, checked against qhull's on random clouds. Where seeds are tied ( a grid, rings, seeds on a circle ) it gives one of the valid triangulations of the tie.

In 2D, the connectivity is REPAIRED. Each cell is cut in floating point and only gives its list of neighbours. An edge is kept when both of its seeds list it. When two kept edges cross ( the two diagonals of a square of a grid ), a single power test removes one. The faces left are triangulated by one seed each. A triangle that its three cells propose is kept as it is; a larger face is cut by the triangulation of its polygon that lies lowest on the lifted paraboloid. Each choice is made once, so no two cells can disagree, and the floats only rank the choices. On random clouds almost every seed takes the direct path, where its neighbours agree all around it. A tie of hidden seeds that leaves a face touching itself sends the call to the certified path below.

In 3D each cell is cut in floating point, then CERTIFIED. A cell passes when no plane came within 1e-11 ( relative ) of one of its vertices during the cut, and no vertex lies that close to a plane that is not its own. Its vertices are then those of the exact cell. Only the doubtful cells are cut again with canonical predicates ( in double-double, with a symbolic perturbation of the ties ). On random clouds, about one cell in ten thousand is cut again. On a grid, every cell is. Double-double is not always enough: on a 2D grid of 10⁶ seeds nudged by 1e-14, a square is cocircular to 4e-35 and two canonical cells take different diagonals ( the repair does not depend on such a precision ).

sdotCGALgeogramsdot, RTX 2080 Ti ( 68 SMs )sdot, H100 ( 132 SMs )ideal scaling
2D uniform, Voronoi301003001k3k1248163264128threads · SMssdot, 1 thread: 5.8k cycles, 1.68 µs at 3.42 GHzsdot, 2 threads: 3k cycles, 879 ns at 3.39 GHzsdot, 4 threads: 1.6k cycles, 491 ns at 3.33 GHzsdot, 8 threads: 920 cycles, 282 ns at 3.27 GHzsdot, 16 threads: 600 cycles, 196 ns at 3.04 GHzsdot, 32 threads: 470 cycles, 158 ns at 2.99 GHzsdot, 64 threads: 520 cycles, 181 ns at 2.87 GHzsdot, 96 threads: 490 cycles, 180 ns at 2.71 GHzsdot, 128 threads: 400 cycles, 160 ns at 2.48 GHzsdot, RTX 2080 Ti ( 68 SMs ): 370 cycles, 201 ns at 1.86 GHzsdot, H100 ( 132 SMs ): 30 cycles, 15.1 ns at 1.98 GHzCGAL, 1 thread: 3.8k cycles, 1.1 µs at 3.42 GHzgeogram, 1 thread: 5.5k cycles, 1.59 µs at 3.42 GHzgeogram, 2 threads: 4.8k cycles, 1.43 µs at 3.39 GHzgeogram, 4 threads: 4.2k cycles, 1.25 µs at 3.33 GHzgeogram, 8 threads: 4.8k cycles, 1.46 µs at 3.27 GHzgeogram, 16 threads: 4.1k cycles, 1.35 µs at 3.04 GHzgeogram, 32 threads: 4.1k cycles, 1.36 µs at 2.99 GHzgeogram, 64 threads: 3.7k cycles, 1.28 µs at 2.87 GHzgeogram, 96 threads: 3.4k cycles, 1.25 µs at 2.71 GHzgeogram, 128 threads: 3.1k cycles, 1.24 µs at 2.48 GHz
2D uniform, Laguerre301003001k3k10k1248163264128threads · SMssdot, 1 thread: 6.4k cycles, 1.87 µs at 3.42 GHzsdot, 2 threads: 3.3k cycles, 966 ns at 3.39 GHzsdot, 4 threads: 1.7k cycles, 520 ns at 3.33 GHzsdot, 8 threads: 990 cycles, 302 ns at 3.27 GHzsdot, 16 threads: 620 cycles, 204 ns at 3.04 GHzsdot, 32 threads: 460 cycles, 153 ns at 2.99 GHzsdot, 64 threads: 560 cycles, 195 ns at 2.87 GHzsdot, 96 threads: 450 cycles, 166 ns at 2.71 GHzsdot, 128 threads: 370 cycles, 149 ns at 2.48 GHzsdot, RTX 2080 Ti ( 68 SMs ): 420 cycles, 228 ns at 1.86 GHzsdot, H100 ( 132 SMs ): 33 cycles, 16.5 ns at 1.98 GHzCGAL, 1 thread: 2.5k cycles, 728 ns at 3.42 GHzgeogram, 1 thread: 5.2k cycles, 1.52 µs at 3.42 GHzgeogram, 2 threads: 4.9k cycles, 1.43 µs at 3.39 GHzgeogram, 4 threads: 5.2k cycles, 1.55 µs at 3.33 GHzgeogram, 8 threads: 4.6k cycles, 1.41 µs at 3.27 GHzgeogram, 16 threads: 4.1k cycles, 1.34 µs at 3.04 GHzgeogram, 32 threads: 3.9k cycles, 1.3 µs at 2.99 GHzgeogram, 64 threads: 3.5k cycles, 1.22 µs at 2.87 GHzgeogram, 96 threads: 3.3k cycles, 1.22 µs at 2.71 GHzgeogram, 128 threads: 2.9k cycles, 1.17 µs at 2.48 GHz
2D lines, Voronoi1003001k3k10k1248163264128threads · SMssdot, 1 thread: 7.4k cycles, 2.17 µs at 3.42 GHzsdot, 2 threads: 5.5k cycles, 1.62 µs at 3.39 GHzsdot, 4 threads: 3.1k cycles, 933 ns at 3.33 GHzsdot, 8 threads: 2.1k cycles, 645 ns at 3.27 GHzsdot, 16 threads: 1.8k cycles, 604 ns at 3.04 GHzsdot, 32 threads: 1.5k cycles, 500 ns at 2.99 GHzsdot, 64 threads: 1.4k cycles, 497 ns at 2.87 GHzsdot, 96 threads: 1.4k cycles, 518 ns at 2.71 GHzsdot, 128 threads: 1.1k cycles, 462 ns at 2.48 GHzsdot, RTX 2080 Ti ( 68 SMs ): 760 cycles, 410 ns at 1.86 GHzsdot, H100 ( 132 SMs ): 110 cycles, 58 ns at 1.98 GHzCGAL, 1 thread: 3.5k cycles, 1.01 µs at 3.42 GHzgeogram, 1 thread: 4.4k cycles, 1.28 µs at 3.42 GHzgeogram, 2 threads: 3.9k cycles, 1.15 µs at 3.39 GHzgeogram, 4 threads: 4k cycles, 1.19 µs at 3.33 GHzgeogram, 8 threads: 3.7k cycles, 1.14 µs at 3.27 GHzgeogram, 16 threads: 3.4k cycles, 1.12 µs at 3.04 GHzgeogram, 32 threads: 3.2k cycles, 1.08 µs at 2.99 GHzgeogram, 64 threads: 2.8k cycles, 987 ns at 2.87 GHzgeogram, 96 threads: 2.9k cycles, 1.07 µs at 2.71 GHzgeogram, 128 threads: 2.8k cycles, 1.12 µs at 2.48 GHz
2D lines, equal areas1003001k3k10k1248163264128threads · SMssdot, 1 thread: 15k cycles, 4.26 µs at 3.42 GHzsdot, 2 threads: 7.6k cycles, 2.25 µs at 3.39 GHzsdot, 4 threads: 7.4k cycles, 2.23 µs at 3.33 GHzsdot, 8 threads: 2.5k cycles, 752 ns at 3.27 GHzsdot, 16 threads: 2k cycles, 646 ns at 3.04 GHzsdot, 32 threads: 1.8k cycles, 604 ns at 2.99 GHzsdot, 64 threads: 1.3k cycles, 453 ns at 2.87 GHzsdot, 96 threads: 1.4k cycles, 525 ns at 2.71 GHzsdot, 128 threads: 1.2k cycles, 475 ns at 2.48 GHzsdot, RTX 2080 Ti ( 68 SMs ): 1.7k cycles, 908 ns at 1.86 GHzsdot, H100 ( 132 SMs ): 130 cycles, 67.2 ns at 1.98 GHzCGAL, 1 thread: 2.4k cycles, 690 ns at 3.42 GHzgeogram, 1 thread: 4.4k cycles, 1.27 µs at 3.42 GHzgeogram, 2 threads: 3.9k cycles, 1.15 µs at 3.39 GHzgeogram, 4 threads: 3.9k cycles, 1.18 µs at 3.33 GHzgeogram, 8 threads: 3.8k cycles, 1.17 µs at 3.27 GHzgeogram, 16 threads: 3.4k cycles, 1.11 µs at 3.04 GHzgeogram, 32 threads: 3.2k cycles, 1.07 µs at 2.99 GHzgeogram, 64 threads: 3k cycles, 1.03 µs at 2.87 GHzgeogram, 96 threads: 2.9k cycles, 1.07 µs at 2.71 GHzgeogram, 128 threads: 2.7k cycles, 1.09 µs at 2.48 GHz
3D uniform, Voronoi1k3k10k30k100k1248163264128threads · SMssdot, 1 thread: 68k cycles, 19.9 µs at 3.42 GHzsdot, 2 threads: 34k cycles, 10.1 µs at 3.39 GHzsdot, 4 threads: 17k cycles, 5.15 µs at 3.33 GHzsdot, 8 threads: 8.8k cycles, 2.68 µs at 3.27 GHzsdot, 16 threads: 4.8k cycles, 1.57 µs at 3.04 GHzsdot, 32 threads: 2.7k cycles, 917 ns at 2.99 GHzsdot, 64 threads: 1.7k cycles, 598 ns at 2.87 GHzsdot, 96 threads: 1.3k cycles, 494 ns at 2.71 GHzsdot, 128 threads: 1.1k cycles, 444 ns at 2.48 GHzsdot, RTX 2080 Ti ( 68 SMs ): 8.3k cycles, 4.47 µs at 1.86 GHzsdot, H100 ( 132 SMs ): 1.2k cycles, 620 ns at 1.98 GHzCGAL, 1 thread: 14k cycles, 4.03 µs at 3.42 GHzCGAL, 2 threads: 11k cycles, 3.26 µs at 3.39 GHzCGAL, 4 threads: 6.5k cycles, 1.95 µs at 3.33 GHzCGAL, 8 threads: 3.8k cycles, 1.16 µs at 3.27 GHzCGAL, 16 threads: 3.4k cycles, 1.13 µs at 3.04 GHzCGAL, 32 threads: 2.4k cycles, 817 ns at 2.99 GHzCGAL, 64 threads: 12k cycles, 4.29 µs at 2.87 GHzCGAL, 96 threads: 21k cycles, 7.93 µs at 2.71 GHzCGAL, 128 threads: 36k cycles, 14.5 µs at 2.48 GHzgeogram, 1 thread: 31k cycles, 9.13 µs at 3.42 GHzgeogram, 2 threads: 24k cycles, 7.15 µs at 3.39 GHzgeogram, 4 threads: 21k cycles, 6.35 µs at 3.33 GHzgeogram, 8 threads: 16k cycles, 4.89 µs at 3.27 GHzgeogram, 16 threads: 14k cycles, 4.59 µs at 3.04 GHzgeogram, 32 threads: 13k cycles, 4.37 µs at 2.99 GHzgeogram, 64 threads: 12k cycles, 4.26 µs at 2.87 GHzgeogram, 96 threads: 12k cycles, 4.29 µs at 2.71 GHzgeogram, 128 threads: 11k cycles, 4.5 µs at 2.48 GHz
3D planes, Voronoi1k3k10k30k100k300k1248163264128threads · SMssdot, 1 thread: 62k cycles, 18.2 µs at 3.42 GHzsdot, 2 threads: 32k cycles, 9.3 µs at 3.39 GHzsdot, 4 threads: 16k cycles, 4.8 µs at 3.33 GHzsdot, 8 threads: 8.3k cycles, 2.54 µs at 3.27 GHzsdot, 16 threads: 4.7k cycles, 1.55 µs at 3.04 GHzsdot, 32 threads: 2.8k cycles, 943 ns at 2.99 GHzsdot, 64 threads: 1.8k cycles, 636 ns at 2.87 GHzsdot, 96 threads: 1.9k cycles, 710 ns at 2.71 GHzsdot, 128 threads: 1.6k cycles, 659 ns at 2.48 GHzsdot, RTX 2080 Ti ( 68 SMs ): 8.4k cycles, 4.51 µs at 1.86 GHzsdot, H100 ( 132 SMs ): 1.5k cycles, 769 ns at 1.98 GHzCGAL, 1 thread: 14k cycles, 3.97 µs at 3.42 GHzCGAL, 2 threads: 12k cycles, 3.42 µs at 3.39 GHzCGAL, 4 threads: 7.9k cycles, 2.36 µs at 3.33 GHzCGAL, 8 threads: 6.5k cycles, 2 µs at 3.27 GHzCGAL, 16 threads: 4.1k cycles, 1.34 µs at 3.04 GHzCGAL, 32 threads: 12k cycles, 3.92 µs at 2.99 GHzCGAL, 64 threads: 82k cycles, 28.4 µs at 2.87 GHzCGAL, 96 threads: 130k cycles, 49.8 µs at 2.71 GHzCGAL, 128 threads: 250k cycles, 101 µs at 2.48 GHzgeogram, 1 thread: 22k cycles, 6.57 µs at 3.42 GHzgeogram, 2 threads: 20k cycles, 5.83 µs at 3.39 GHzgeogram, 4 threads: 20k cycles, 6.03 µs at 3.33 GHzgeogram, 8 threads: 18k cycles, 5.52 µs at 3.27 GHzgeogram, 16 threads: 16k cycles, 5.23 µs at 3.04 GHzgeogram, 32 threads: 15k cycles, 5.02 µs at 2.99 GHzgeogram, 64 threads: 14k cycles, 5.02 µs at 2.87 GHzgeogram, 96 threads: 13k cycles, 4.74 µs at 2.71 GHzgeogram, 128 threads: 12k cycles, 4.76 µs at 2.48 GHz
3D planes, equal volumes1k3k10k30k100k300k1248163264128threads · SMssdot, 1 thread: 120k cycles, 36.2 µs at 3.42 GHzsdot, 2 threads: 62k cycles, 18.4 µs at 3.39 GHzsdot, 4 threads: 31k cycles, 9.41 µs at 3.33 GHzsdot, 8 threads: 16k cycles, 4.87 µs at 3.27 GHzsdot, 16 threads: 8.6k cycles, 2.83 µs at 3.04 GHzsdot, 32 threads: 4.8k cycles, 1.62 µs at 2.99 GHzsdot, 64 threads: 2.9k cycles, 1.03 µs at 2.87 GHzsdot, 96 threads: 2.3k cycles, 852 ns at 2.71 GHzsdot, 128 threads: 2k cycles, 825 ns at 2.48 GHzsdot, RTX 2080 Ti ( 68 SMs ): 24k cycles, 12.8 µs at 1.86 GHzsdot, H100 ( 132 SMs ): 3k cycles, 1.5 µs at 1.98 GHzCGAL, 1 thread: 14k cycles, 4.01 µs at 3.42 GHzCGAL, 2 threads: 12k cycles, 3.55 µs at 3.39 GHzCGAL, 4 threads: 8.1k cycles, 2.42 µs at 3.33 GHzCGAL, 8 threads: 5.1k cycles, 1.55 µs at 3.27 GHzCGAL, 16 threads: 11k cycles, 3.51 µs at 3.04 GHzCGAL, 32 threads: 7.2k cycles, 2.42 µs at 2.99 GHzCGAL, 64 threads: 140k cycles, 47.4 µs at 2.87 GHzCGAL, 96 threads: 82k cycles, 30.1 µs at 2.71 GHzCGAL, 128 threads: 420k cycles, 170 µs at 2.48 GHzgeogram, 1 thread: 23k cycles, 6.8 µs at 3.42 GHzgeogram, 2 threads: 21k cycles, 6.1 µs at 3.39 GHzgeogram, 4 threads: 20k cycles, 6.08 µs at 3.33 GHzgeogram, 8 threads: 19k cycles, 5.68 µs at 3.27 GHzgeogram, 16 threads: 16k cycles, 5.35 µs at 3.04 GHzgeogram, 32 threads: 16k cycles, 5.23 µs at 2.99 GHzgeogram, 64 threads: 15k cycles, 5.12 µs at 2.87 GHzgeogram, 96 threads: 14k cycles, 5.09 µs at 2.71 GHzgeogram, 128 threads: 12k cycles, 4.91 µs at 2.48 GHz

Cycles per dirac: the time times the clock, the median of the clocks measured on the machine at that thread count ( the cores' on the CPU, the SMs' on a card ): one run's sample is too noisy. Log-log; hover a point for its time and clock.

A triangulation is what CGAL and geogram are made for, and on one thread they stay ahead, in 3D especially: the certification costs about a cell's worth on top of the cell itself. On the 128 cores sdot takes 160 ns per seed in 2D and 440 ns in 3D. On a grid, where every cell is cut canonically, it is ten times slower.

Scaling with the threads ​

3D gains 45× on 128 cores ( 60× in cycles ), the clustered 3D clouds 28× and 44×. A uniform 2D cloud gains 11× and stops there from 32 threads on: a 2D cell is too little work for its memory traffic. The clustered 2D clouds gain 5× and 9×. CGAL's 2D triangulation is sequential: its time on one thread is drawn flat ( dashed ) over the threads.

The tables ​

One power diagram ​

sdotCGALgeogram
n1 / 32 / 128 threadsRTX 2080 Ti / H1001 / 32 / 128 threads1 / 32 / 128 threads
2D uniform, Voronoi1e61 414 / 60 / 2957 / 6.01 495 / 1 155 / 1 1882 340 / 1 421 / 1 276
2D uniform, Laguerre1e61 615 / 66 / 4661 / 6.61 087 / 818 / 8472 238 / 1 361 / 1 214
2D lines, Voronoi1e51 344 / 136 / 94119 / 261 281 / 1 131 / 1 1411 829 / 1 192 / 1 242
2D lines, equal areas1e53 897 / 261 / 158187 / 33900 / 730 / 8301 837 / 1 158 / 1 196
3D uniform, Voronoi1e69 444 / 340 / 110591 / 9011 558 / 1 617 / 26 15815 159 / 4 705 / 5 897
3D planes, Voronoi1e59 154 / 412 / 283578 / 10611 270 / 7 350 / 127 85012 456 / 5 581 / 6 613
3D planes, equal volumes1e519 316 / 803 / 4471 492 / 18811 570 / 4 070 / 140 33013 079 / 5 658 / 6 737

ns per dirac, the measure of every cell, double ( GPU: kernel time ). CGAL: triangulation ( in parallel in 3D only ), then each cell rebuilt and clipped ( over the threads ). geogram: triangulation of the lifted seeds, then the cells restricted to a mesh of the box. Shaded: the fastest on the CPU, and on the GPU.

On the GPU, each card in its own columns:

floatdouble
RTX 2080 Ti / H100RTX 2080 Ti / H100
2D uniform, Voronoi13 / 4.457 / 6.0
2D uniform, Laguerre11 / 4.761 / 6.6
2D lines, Voronoi37 / 21119 / 26
2D lines, equal areas49 / 28187 / 33
3D uniform, Voronoi270 / 67591 / 90
3D planes, Voronoi278 / 82578 / 106
3D planes, equal volumes437 / 1391 492 / 188

ns per dirac, kernel time only.

A sequence of diagrams on the same diracs: the preparation, then each next diagram.

preparationnext diagram
1 / 32 / 128 threads1 / 32 / 128 threads
2D uniform, 1e6398 / 73 / 1261 712 / 88 / 69
3D uniform, 1e6455 / 86 / 15910 546 / 407 / 159

ns per dirac. 10 diagrams on the same positions, the weights going from 0 to a Laguerre diagram: the preparation ( tree, structures ) once, then each diagram reuses it.

Exact connectivity ​

sdotCGALgeogram
1 / 32 / 128 threadsRTX 2080 Ti / H1001 / 32 / 128 threads1 / 32 / 128 threads
2D uniform, Voronoi1 681 / 158 / 160201 / 151 103 / – / –1 593 / 1 360 / 1 235
2D uniform, Laguerre1 871 / 153 / 149228 / 17728 / – / –1 520 / 1 300 / 1 171
2D lines, Voronoi2 167 / 500 / 462410 / 581 011 / – / –1 278 / 1 078 / 1 120
2D lines, equal areas4 257 / 604 / 475908 / 67690 / – / –1 273 / 1 072 / 1 091
3D uniform, Voronoi19 900 / 917 / 4444 466 / 6204 032 / 817 / 14 5139 129 / 4 366 / 4 500
3D planes, Voronoi18 193 / 943 / 6594 512 / 7693 970 / 3 920 / 100 7506 570 / 5 018 / 4 757
3D planes, equal volumes36 176 / 1 623 / 82512 812 / 1 4994 010 / 2 420 / 170 2906 804 / 5 227 / 4 910

ns per dirac, the exact dual: the regular triangulation, with exact predicates and a symbolic perturbation of the ties. sdot: `dual()`, the cells cut with canonical predicates, each simplex written by the cell of its smallest seed ( restricted to the box ); GPU: kernel time, double. CGAL and geogram: their regular triangulation of the whole space ( CGAL in parallel in 3D only; geogram's 2D one is sequential ). Shaded: the fastest on the CPU, and on the GPU.

The machines and the protocol ( cold starts, repetitions, clocks ) are on the overview.

SDOT — H. Leclerc, Q. Mérigot, T. Gallouët · LMO / INRIA PARMA