Marching Tetrahedrons on the GPU

Project reference: 2024

Creating a mesh^* – a discretized surface enclosing a given spatial object – is a compute-intensive task central to many scientific fields ranging from physics (Maxwell’s Eq., CFD, MD) to computational biology (PB, MM/PBSA, cryo-EM, Struct. Bio). The marching cubes algorithm (doi: 10.1145/37402.37422) has become a standard technique to compute meshes in an efficient way. Despite its ubiquitous use, a few fundamental limitations have been reported, in particular geometric ambiguities (doi:10.1016/j.cag.2006.07.021). Such problems can be alleviated – and the entire algorithm made significantly less complex – by switching from cubes to tetrahedrons as basic building blocks. Therefore, this project aims to explore basic feasibility and potential limitations of the marching tetrahedrons algorithm specifically targeting GPU  implementations on modern HPC platforms. A large variety of individual activities are planned (according to skill level and interest of the trainee) starting with simple geometric considerations and including all essential steps of the development cycle characteristic of contemporary scientific software development.

Apart from the promising outlook, i.e. having worked and gained experience with an important subject of very broad applicability, there is a large body of reference work that can help to jump-start the project, e.g. plenty of literature, a public domain implementation (http://paulbourke.net/geometry/polygonise/), a closely related GPU sample in the CUDA SDK (https://docs.nvidia.com/cuda/cuda-samples/index.html#marching-cubes-isosurfaces) and a number of alternative surface computation programs for comparison in terms of performance as well as robustness.

^*Note the spelling difference to ‘mess’.

Mesh creation for ubiquitin (a small protein, pdb code 1UBQ) can be achieved from applying the marching cubes/tetrahedrons algorithm resulting in a closed surface discretized into triangular elements (white envelope in panel to the right).

Project Mentor: Siegfried Hoefinger

Project Co-mentor: Markus Hickel and Balazs Lengyel

Site Co-ordinator: Claudia Blaas-Schenner

Participants: Jake Love, Federico Julian Camerota Verdù, Aarushi Jain

Learning Outcomes:
Familiarity with basic development strategies in HPC environments. A deepened understanding of basic scientific key algorithms and how to obtain efficient implementations.

Student Prerequisites (compulsory):
Just a positive attitude towards HPC for scientific applications and the readiness for critical and analytical thinking.

Student Prerequisites (desirable):
Familiarity with Linux, basic programming skills in C/Fortran, experience with GPUs, basic understanding of formal methods and their translation into scientific applications;

Training Materials:
Public domain materials mentioned in the Abstract and first steps with CUDA (https://tinyurl.com/cuda4dummies)

Workplan:

• Week 1: Basic HPC training; accustom to local HPC system;
• Week 2: Literature research and first exploratory runs;
• Week 3: Set up a working plan;
• Weeks 4-7: Actual implementation and performance evaluation;
• Week 8: Write up a final report and submit it;

Final Product Description:
The ideal – yet very unrealistic – outcome was a fully functional MT program running efficiently on the V100 (at approx 0.01 sec per system composed of  50 k objects), but equally  satisfactory was a returning summer student having gained good experience with practical work in HPC environments.

Adapting the Project: Increasing the Difficulty:
Increasing performance gains in absolute terms as well as relative to existing implementations;

Adapting the Project: Decreasing the Difficulty:
Various optional subtasks can either be dropped or carried out in greater detail

Resources:
Basic access to the local HPC infrastructure (including various GPU architectures) will be granted. Additional resources in the public domain have been listed in the Abstract.

Organisation:
VSC Research Center