Performance Evaluation of Parallel Surface Modeling and Generation on Actual and Virtual Multicore Systems

Authors: Nyeng P. Gyang

Abstract:

Even though past, current and future trends suggest that multicore and cloud computing systems are increasingly prevalent/ubiquitous, this class of parallel systems is nonetheless underutilized, in general, and barely used for research on employing parallel Delaunay triangulation for parallel surface modeling and generation, in particular. The performances, of actual/physical and virtual/cloud multicore systems/machines, at executing various algorithms, which implement various parallelization strategies of the incremental insertion technique of the Delaunay triangulation algorithm, were evaluated. T-tests were run on the data collected, in order to determine whether various performance metrics differences (including execution time, speedup and efficiency) were statistically significant. Results show that the actual machine is approximately twice faster than the virtual machine at executing the same programs for the various parallelization strategies. Results, which furnish the scalability behaviors of the various parallelization strategies, also show that some of the differences between the performances of these systems, during different runs of the algorithms on the systems, were statistically significant. A few pseudo superlinear speedup results, which were computed from the raw data collected, are not true superlinear speedup values. These pseudo superlinear speedup values, which arise as a result of one way of computing speedups, disappear and give way to asymmetric speedups, which are the accurate kind of speedups that occur in the experiments performed.

Keywords: Cloud computing systems, multicore systems, parallel delaunay triangulation, parallel surface modeling and generation.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1316161

References:

[1] Blelloch, G. E., Miller, G. L., Hardwick, J. C. and Talmor, D. (1999). Design and Implementation of a Practical Parallel Delaunay Algorithm. Algorithmica, 24(3-4), 243-269. doi: 10.1007/pl00008262
[2] Blelloch, G. E., Miller, G. L., and Talmor, D. (1996). Developing a practical projection-based parallel Delaunay algorithm. Paper presented at the Proceedings of the twelfth annual symposium on Computational geometry, Philadelphia, Pennsylvania, USA.
[3] Chen, M.-B., Chuang, T.-R., and Wu, J.-J. (2001). Efficient Parallel Implementations of 2D Delaunay Triangulation with High Performance Fortran. Paper presented at the PPSC.
[4] Chen, M.-B., Chuang, T.-R., and Wu, J.-J. (2002). A parallel divide-and-conquer scheme for Delaunay triangulation. Paper presented at the Parallel and Distributed Systems, 2002. Proceedings. Ninth International Conference on.
[5] Chen, M.-B., Chuang, T.-R., and Wu, J.-J. (2006). Parallel divide-and-conquer scheme for 2D Delaunay triangulation: Research Articles. Concurr. Comput. : Pract. Exper., 18(12), 1595-1612. doi: 10.1002/cpe.v18:12
[6] Cignoni, P., Laforenza, D., Perego, R., Scopigno, R., and Montani, C. (1995). Evaluation of parallelization strategies for an incremental Delaunay triangulator in E3. Concurrency: Practice and Experience, 7(1), 61-80. doi: 10.1002/cpe.4330070106
[7] Cignoni, P., Montani, C., Perego, R. and Scopigno, R. (1993). Parallel 3D Delaunay Triangulation. Computer Graphics Forum, 12(3), 129-142. doi: 10.1111/1467-8659.1230129
[8] Gyang, N. P. (2014). Performance evaluation of parallel surface generation from LiDAR point clouds on actual and virtual multicore systems (Doctoral dissertation, Colorado Technical University).
[9] Hardwick, J. C. (1997). Implementation and evaluation of an efficient parallel Delaunay triangulation algorithm. Paper presented at the Proceedings of the ninth annual ACM symposium on Parallel algorithms and architectures, Newport, Rhode Island, USA.
[10] Held, J., Bautista, J. and Koehl, S. (2006). From a few cores to many: A tera-scale computing research overview. white paper, Intel.
[11] Kohout, J. and Kolingerová, I. (2003). Parallel Delaunay triangulation in E3: make it simple. The Visual Computer, 19(7-8), 532-548. doi: 10.1007/s00371-003-0219-x
[12] Kohout, J., Kolingerová, I. and Ára, J. (2005). Parallel Delaunay triangulation in E2 and E3 for computers with shared memory. Parallel Comput., 31(5), 491-522. doi: citeulike-article id:3386087, doi: 10.1016/j.parco.2005.02.010
[13] Kolingerová, I. and Kohout, J. (2002). Optimistic parallel Delaunay triangulation. The Visual Computer, 18(8), 511-529. doi: 10.1007/s00371-002-0173-z
[14] Lo, S. H. (2012a). Parallel Delaunay triangulation – Application to two dimensions. Finite Elements in Analysis and Design, 62(0), 37-48. doi: http://dx.doi.org/10.1016/j.finel.2012.07.003
[15] Lo, S. H. (2012b). Parallel Delaunay triangulation in three dimensions. Computer Methods in Applied Mechanics and Engineering, 237–240(0), 88-106. doi: http://dx.doi.org/10.1016/j.cma.2012.05.009
[16] Park, C.-M., Lee, S., and Park, C.-I. (2001). An improved parallel algorithm for delaunay triangulation on distributed memory parallel computers. Parallel Processing Letters, 11(02n03), 341-352. doi: doi:10.1142/S0129626401000634
[17] Puppo, E., Davis, L., De Menthon, D. and Teng, Y. A. (1994). Parallel terrain triangulation. International Journal of Geographical Information Systems, 8(2), 105-128. doi: citeulike-article-id:10466135 doi: 10.1080/02693799408901989
[18] Shewchuk, J. R. (1996). Triangle: Engineering a 2D Quality Mesh Generator and Delaunay Triangulator. Paper presented at the Selected papers from the Workshop on Applied Computational Geormetry, Towards Geometric Engineering.
[19] Teng, Y. A., Sullivan, F., Beichl, I. and Puppo, E. (1993). A data-parallel algorithm for three-dimensional Delaunay triangulation and its implementation. Paper presented at the Proceedings of the 1993 ACM/IEEE conference on Supercomputing, Portland, Oregon, United States.