The Spy Element Method – A universal approach to complex computing on manycore processors

This work presents a general approach, coined “Spy Element Method” (SEM), for parallelising workloads to run on manycore processors and featuring dynamic dependencies between different data items, such as graph traversals, remeshing methods and particle simulations. In the SEM, appropriately defined entities, denominated “spy elements”, inspect their neighbourhood and without atomic memory operations update in parallel all the dynamic data dependencies, including those between themselves, between the original objects of the current problem and among entities of different kind. The application of the SEM to meshless simulation models obviates the use of binning algorithms relying on sorting or atomics, and concomitantly renders their implementation fully particle centric. On the NVIDIA GeForce GTX 480, an optimised particle-based fluid simulator runs 1.4–2.3 times faster when the binning aided by the state-of-the-art parallel sorter is eliminated and data updating is delegated to the SEM, and is at least 40 times faster than a highly optimised single-threaded version running on a single core of the Intel Xeon X5650 2.66 GHz.

► This work presents new ideas for successfully porting complex applications to manycore processors and accelerate them.
► Core contributions comprise novel data structures and algorithms for parallelizing various computational problems, e.g. graph traversal, rebuilding of trees and particle simulations.
► The new programming methodology renders a state-of-the-art software technology in the field of parallel particle-based fluid simulations substantially faster.
► Numerous extensions of the core algorithms are discussed.