Premium
A multi‐core ready discrete element method with triangles using dynamically adaptive multiscale grids
Author(s) -
Krestenitis Konstantinos,
Weinzierl Tobias
Publication year - 2018
Publication title -
concurrency and computation: practice and experience
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.309
H-Index - 67
eISSN - 1532-0634
pISSN - 1532-0626
DOI - 10.1002/cpe.4935
Subject(s) - tree traversal , computer science , data structure , bottleneck , concurrency , tree (set theory) , algorithm , parallel computing , tree structure , theoretical computer science , distributed computing , computational science , binary tree , mathematics , mathematical analysis , embedded system , programming language
Summary The simulation of vast numbers of rigid bodies of non‐analytical shapes and of tremendously different sizes that collide with each other is computationally challenging. A bottleneck is the identification of all particle contact points per time step. We propose a tree‐based multilevel meta data structure to administer the particles. The data structure plus a purpose‐made tree traversal identifying the contact points introduce concurrency to the particle comparisons, whilst they keep the absolute number of particle‐to‐particle comparisons low. Furthermore, a novel adaptivity criterion allows explicit time stepping to work with comparably large time steps. It optimises both toward low algorithmic complexity per time step and low numbers of time steps. We study three different parallelisation strategies exploiting our traversal's concurrency. The fusion of two of them yields promising speedups once we rely on maximally asynchronous task‐based realisations. Our work shows that new computer architecture can push the boundary of rigid particle computability, yet if and only if the right data structures and data processing schemes are chosen.