Design Of Algorithm Accelerator And Software Framework For N-body Simulation

Many body problem, also be known as the N-body problem, which researches thegravitational interactions between N bodies, is a basic problem of mechanics. It hasbeen used in many disciplines such as astrophysics and molecular dynamics. In practice,the computation demand of the problem is very large. Although the computationalcomplexity of N-body algorithm has been decreased from O(N2) to O(NlogN)，thetraditional PC cannot solve the N-Body simulations for its weak computing capabilityand the explosive growth of the scale of the problems, so we need large-scale parallelcomputers to solve such problems, and there are many computers using heterogeneousmixture of CPU-GPU architecturein those large-scale parallel computers. However,many large-scale applications computed in heterogeneous architecture computersdoesn’t take full utilization of the CPU computing resources, resulted a tremendouswaste of CPU computing resources and execution time.In this paper, we design the algorithm accelerator using GPU for N-body problem,and present a two-level CPU-GPU hybrid strategy which explores both CPU and GPUcomputing potentials efficiently through allocating tasks between CPU and GPU tomake sure the load balance, which reduces the CPU performance loss from waitingGPU process. We also summerise a formula which reflects the relationship between thenumber of GPU processes and the whole time of the application to achieve the bestperformance. Finally, we present a algorithm to make sure the work-load balancebetween CPU and GPU due to the calculation performance between CPU and GPU. Allthese work introduced above lay a foundation of our future work.