Multiscale Storage, Parallelisation and Programming Paradigms for Spacetrees in Scientific Computing

Abstract

More than ten years ago, the Gordon Bell Prize was awarded for a seismic calibration code [2]. According to the authors, mesh generation based upon octrees was one key feature to achieve the reported performance. Octrees look back on a long tradition of runs on the biggest machines in the world, and every year the supercomputing community continues to face new codes resting upon octree or, more general, spacetree meshes; either for solvers of partial differential equations (PDEs) or n-body codes where the original fast multipole method, being among the most important algorithms of the 20th century [24], describes spacetree meshing. Spacetrees have been and continue to be a fundamental data structure and data organisation concept for high performance computational science & engineering (CSE). Much of my own research of the last six years orbits around the concept of spacetrees—with emphasis on algorithmic problems in supercomputing and less attention to supercomputing applications and high performance engineering. I thus decided to make document present eight selected papers that all rely on this particular data structure. They either tackle a particular application challenge or study, augment or efficiently realise this data structure generically. All methodological ingredients presented are integrated into one spacetree code [94]. All applicationcentred work relies on this code base. It is thus a valid and natural question to ask whether this document is about ‘yet another spacetree code’. It is. However, this answer comes along with the footnote that this collection of papers comprises more than the documentation of an implementation well-suited to write spacetree-based solvers. The algorithms and methods are of value for any spacetree or related implementation. Their integration into one code base validates that they work hand in hand. Their comparison to other approaches facilitates a classification of and differentiation to spacetree codes in general. Their application validates their usefulness and uncovers open issues in the spacetree context.