We present a new adaptive parallel algorithm for the challenging problem of multi-dimensional numerical integration on massively parallel architectures. Adaptive algorithms have demonstrated the best performance, but efficient many-core utilization is difficult to achieve because the adaptive work-load can vary greatly across the integration space and is impossible to predict a priori. Existing parallel algorithms utilize sequential computations on independent processors, which results in bottlenecks due to the need for data redistribution and processor synchronization. Our algorithm employs a high-throughput approach in which all existing sub-regions are processed and sub-divided in parallel. Repeated sub-region classification and filtering improves upon a brute-force approach and allows the algorithm to make efficient use of computation and memory resources. A CUDA implementation shows orders of magnitude speedup over the fastest open-source CPU method and extends the achievable accuracy for difficult integrands. Our algorithm typically outperforms other existing deterministic parallel methods.

Particle colliders are essential tools in the pursuit of understanding matter interactions in the universe. The tremendous cost of their operation and requirement for finetuning, make high-fidelity particle collider simulations essential in ensuring optimal operation. Simulations of the beam-beam effects of colliding particle bunches are extremely time-consuming since they include hundreds of billions of particles that collide millions of times per second. A high degree of parallelization is required to decrease the execution time of such simulations. GPUs present an opportunity towards making such simulations viable, though several challenges must be overcome in order to achieve efficient parallelization. One major challenge addressed in this paper is an efficient simulation of multiple bunch collision on a cluster of GPUs. The numerous colliding bunches are subject to scheduling constraints, which requires the utilization of an efficient collision schedule algorithm, all the while ensuring that the processors are not underutilized and communication overheads are low. We implemented two schemes on a 8-node cluster with four K40 GPUs on each node for a total of 32 GPUs. We demonstrated an almost linear speedup for large bunches with the number of GPUs.

Parallel computing architectures like GPUs have traditionally been used to accelerate applications with dense and highly-structured workloads; however, many important applications in science and engineering are irregular and dynamic in nature, making their effective parallel implementation a daunting task. Numerical simulation of charged particle beam dynamics is one such application where the distribution of work and data in the accurate computation of collective effects at each time step is irregular and exhibits control-flow and memory access patterns that are not readily amenable to GPU's architecture. Algorithms with these properties tend to present both significant branch and memory divergence on GPUs which leads to severe performance bottlenecks.We present a novel cache-aware algorithm that uses machine learning to address this problem. The algorithm presented here uses supervised learning to adaptively model and track irregular access patterns in the computation of collective effects at each time step of the simulation to anticipate the future control-flow and data access patterns. Access pattern forecast are then used to formulate runtime decisions that minimize branch and memory divergence on GPUs, thereby improving the performance of collective effects computation at a future time step based on the observations from earlier time steps. Experimental results on NVIDIA Tesla K40 GPU shows that our approach is effective in maximizing data reuse, ensuring workload balance among parallel threads, and in minimizing both branch and memory divergence. Further, the parallel implementation delivers up to 485 Gflops of double precision performance, which translates to a speedup of up to 2.5X compared to the fastest known GPU implementation.

Accurate simulation of collective effects in electron beams is one of the most challenging and computationally intractable problems in accelerator physics. More recently, researchers have developed a GPU-accelerated, high-fidelity simulation of electron beam dynamics that models the collective effects much more accurately. The simulation, however, is heavily data-intensive and memory-bound. In particular, data-dependent, irregular memory access patterns and control-flow in the collective effects computation phase of the simulation leads to a large number of non-coalesced memory accesses on the GPU. This significantly deteriorates the overall performance. Moreover, the parallel simulation exhibits poor data locality. This, together with non-coalesced memory accesses, leads to ineffective use of the memory hierarchy. We present a novel cache-aware algorithm that uses a locality heuristic to maximize data reuse by improving data locality. Additionally, the algorithm uses a control-flow heuristic to balance the workload among threads. The control-flow heuristic also minimizes threads divergence and enables reuse of partial results of previous iterations and thereby reducing the overall operation count. Experimental results on NVIDIA Tesla K40 GPU shows that our approach delivers up to 450 Gflops of double precision performance, which translates to a speedup of up to 16X compared with the current state-of-the-art GPU implementation.

We present a memory-efficient algorithm and its implementation for solving multidimensional numerical integration on a cluster of compute nodes with multiple GPU devices per node. The effective use of shared memory is important for improving the performance on GPUs, because of the bandwidth limitation of the global memory. The best known sequential algorithm for multidimensional numerical integration CUHRE uses a large dynamic heap data structure which is accessed frequently. Devising a GPU algorithm that caches a part of this data structure in the shared memory so as to minimizes global memory access is a challenging task. The algorithm presented here addresses this problem. Furthermore we propose a technique to scale this algorithm to multiple GPU devices. The algorithm was implemented on a cluster of Intel®Xeon®CPU X5650 compute nodes with 4 Tesla M2090 GPU devices per node. We observed a speedup of up to 240 on a single GPU device as compared to a speedup of 70 when memory optimization was not used. On a cluster of 6 nodes (24 GPU devices) we were able to obtain a speedup of up to 3250. All speedups here are with reference to the sequential implementation running on the compute node.

Recent development in Graphics Processing Units (GPUs) has enabled a new possibility for highly efficient parallel computing in science and engineering. Their massively parallel architecture makes GPUs very effective for algorithms where processing of large blocks of data can be executed in parallel. Multidimensional integration has important applications in areas like computational physics, plasma physics, computational fluid dynamics, quantum chemistry, molecular dynamics and signal processing. The computationally intensive nature of multidimensional integration requires a high-performance implementation. In this study, we present an efficient deterministic parallel algorithm for adaptive multidimensional numerical integration on GPUs. Various optimization techniques are applied to maximize the utilization of the GPU. GPU-based implementation outperforms the best known sequential methods and achieves a speed-up of up to 100. It also shows good scalability with the increase in dimensionality.