JuSER (Forschungszentrum Jülich) · 2012 · 49 citations · 28 references
ComputingComputer ScienceHigh-performance ComputingParallel AlgorithmsParallel ComputingScientific ComputingParallel Algorithm DesignParallel ArchitecturesParallel ComputationParallel Computer ArchitectureParallel Numerical MethodsParallel Performance AnalysisDiscretizationMany-core ProcessorsParallel Algorithm ScalabilityParallel EfficiencyParallel SolversSpace-time DiscretizationStrong ScalingTime Discretization
We present a novel space-time parallel version of the Barnes-Hut tree code PEPC using PFASST, the Parallel Full Approximation Scheme in Space and Time. The naive use of increasingly more processors for a fixed-size N-body problem is prone to saturate as soon as the number of unknowns per core becomes too small. To overcome this intrinsic strong-scaling limit, we introduce temporal parallelism on top of PEPC's existing hybrid MPI/PThreads spatial decomposition. Here, we use PFASST which is based on a combination of the iterations of the parallel-in-time algorithm parareal with the sweeps of spectral deferred correction (SDC) schemes. By combining these sweeps with multiple space-time discretization levels, PFASST relaxes the theoretical bound on parallel efficiency in parareal. We present results from runs on up to 262,144 cores on the IBM Blue Gene/P installation JUGENE, demonstrating that the spacetime parallel code provides speedup beyond the saturation of the purely space-parallel approach. © 2012 IEEE.
28
A fast algorithm for particle simulations
Leslie Greengard, Vladimir Rokhlin · Journal of Computational Physics · 1987 · 4.9K citations
A hierarchical O(N log N) force-calculation algorithm
Josh Barnes, Piet Hut · Nature · 1986 · 3.7K citations
A parallel hashed Oct-Tree N-body algorithm
Michael S. Warren, John K. Salmon · 1993 · 463 citations · Full text