Internal:4D Predicates Benchmark - Revision history

Ctsolakis: /* Benchmark Data on replacing CGAL predicates with PCK::GEO Predicates */

2019-09-19T12:07:34Z

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

← Older revision		Revision as of 07:07, 19 September 2019
Line 9:		Line 9:

	{\| class="wikitable"		{\| class="wikitable"
	! ~~CGAL~~		!
	!		! colspan="2" \| CGAL
	! PCK::GEO		! colspan="2" \| PCK::GEO
	!
	!
	\|-		\|-
	\| Threads		\| Threads

Ctsolakis: /* Benchmark Data on replacing CGAL predicates with PCK::GEO Predicates */

2019-09-19T12:06:54Z

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

← Older revision		Revision as of 07:06, 19 September 2019
Line 6:		Line 6:

	== Benchmark Data on replacing CGAL predicates with PCK::GEO Predicates ==		== Benchmark Data on replacing CGAL predicates with PCK::GEO Predicates ==
	''' Benchmark expanding 1000 cavities of points ~~takesn~~ from a uniform grid in 3D(4D), OpenMP is used for threading'''		''' Benchmark expanding 1000 cavities of points taken from a uniform grid in 3D(4D), OpenMP is used for threading'''

	{\| class="wikitable"		{\| class="wikitable"

Ctsolakis: /* Benchmark Data on replacing CGAL predicates with PCK::GEO Predicates */

2019-09-19T12:06:40Z

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

← Older revision		Revision as of 07:06, 19 September 2019
Line 6:		Line 6:

	== Benchmark Data on replacing CGAL predicates with PCK::GEO Predicates ==		== Benchmark Data on replacing CGAL predicates with PCK::GEO Predicates ==
	'''~~TODO~~'''		''' Benchmark expanding 1000 cavities of points takesn from a uniform grid in 3D(4D), OpenMP is used for threading'''

			{\| class="wikitable"
			! 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
			\|}

Ctsolakis: /* Optimizations */

2019-09-18T19:44:03Z

Optimizations

← Older revision		Revision as of 14:44, 18 September 2019
Line 4:		Line 4:
	= Optimizations =		= 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.		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 ==
			'''TODO'''

Ctsolakis: /* Optimizations */

2019-09-18T19:33:13Z

Optimizations

← Older revision		Revision as of 14:33, 18 September 2019
Line 3:		Line 3:

	= Optimizations =		= 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 ~~[115]~~ 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.		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.

Ctsolakis: Created page with "= 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 ach..."

2019-09-18T19:32:43Z

Created page with "= 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 ach..."

New page

= 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 [115] 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.