VQhull: a Fast Planar Quickhull
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866917003193745408 |
|---|---|
| author | Koopman, Thomas Aaldering, Jordy van Gastel, Bernard Scholz, Sven-Bodo |
| author_facet | Koopman, Thomas Aaldering, Jordy van Gastel, Bernard Scholz, Sven-Bodo |
| contents | Finding the convex hull is a fundamental problem in computational geometry. Quickhull is a fast algorithm for finding convex hulls. In this paper, we present VQhull, a fast parallel implementation of Quickhull that exploits vector instructions, and coordinates CPU cores in a way that minimizes data movement. This implementation obtains a sequential runtime improvement of 1.6--16x, and a parallel runtime improvement of 1.5-11x compared to the state of the art on the Problem Based Benchmark Suite. VQhull achieves 85--100% of non-NUMA architectures' peak bandwidth, and 66--78% on our two-CPU NUMA system. This leaves little room for further improvements.
A 4x speedup on 8 cores has a parallel efficiency of 50%. This suggests a waste of energy, but our measurements show a more complicated picture: energy usage may even be lower in parallel. Quickhull serves as a case study that runtime and energy consumption do not go hand in hand. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2510_09417 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | VQhull: a Fast Planar Quickhull Koopman, Thomas Aaldering, Jordy van Gastel, Bernard Scholz, Sven-Bodo Computational Geometry Finding the convex hull is a fundamental problem in computational geometry. Quickhull is a fast algorithm for finding convex hulls. In this paper, we present VQhull, a fast parallel implementation of Quickhull that exploits vector instructions, and coordinates CPU cores in a way that minimizes data movement. This implementation obtains a sequential runtime improvement of 1.6--16x, and a parallel runtime improvement of 1.5-11x compared to the state of the art on the Problem Based Benchmark Suite. VQhull achieves 85--100% of non-NUMA architectures' peak bandwidth, and 66--78% on our two-CPU NUMA system. This leaves little room for further improvements. A 4x speedup on 8 cores has a parallel efficiency of 50%. This suggests a waste of energy, but our measurements show a more complicated picture: energy usage may even be lower in parallel. Quickhull serves as a case study that runtime and energy consumption do not go hand in hand. |
| title | VQhull: a Fast Planar Quickhull |
| topic | Computational Geometry |
| url | https://arxiv.org/abs/2510.09417 |