Heterogeneous Platform Design For Accelerating MOND Numerical Simulation

In modern cosmology,scientists have put forward many new theories to explain the astronomical phenomena.Therefore,they need precise numerical simulation,which can be compared with the observed phenomenon,to verify the correctness of the new theory.The astronomical observation results show that,the modern cosmological model base on Newtonian dynamics cannot explain the observed of galactic rotation curves.In order to solve the problem,theoretical physicists point out that,Newtonian dynamics may not be accurate at the large scale Galaxy space.So a Modified Newtonian Dynam-ics theory(MOND),which is different from dark matter theory,is put forward.But the numerical simulation of MOND theory is consist of N-body simulation which has high computing complexity.So limited by the development of computer,the size of the MOND numerical simulation has always been small.N-body simulation is one of the most important numerical calculation.It is always used to simulate the evolution of the system to verified the correctness of the theory,as well as to extract the relevant information of the system.So it plays an important part in astrophysics,plasma physics,molecular dynamics,fluid dynamics and other fields.In recent years,with the rapid development of the computer,the scale of N-body simulation has become larger and larger,and play a more and more important role in relative field.Nowaday,the demand for N-body simulation is still growing.To simplify the calculation of N-body,researchers have made a lot of assumptions,proposing many algorithms,such as PM(Particle-Mesh),Tree,TreePM(Tree+PM)as well as P3M(Particle-Particle+PM)algorithm.Among all of these,TreePM algorithm,which can balance the requirements of calculation precision and speed,has been widely used in astronomy simulation.In order to improve the speed of the simulation,many kinds of computing acceler-ation technology have been applied to N-body simulation.With the rapid development of the technology,calculation of N-body with new ideas and new solutions has become the spot in the academia and the business community.Field-Programmable Gate Ar-ray(FPGA)and General Purpose Graphic Processing Units(GPGPU),which are good at acceleation,have always been used in the simulation.This thesis focuses on the accelaration of MOND simulation.Based on the re-quirements of the application,appropriate N-body simulation algorithm is selected,the bottleneck of the algorithm is analyzed,and the calculation task is assigned to GPU and FPGA according to the computing features.Then using heterogeneous platform consist of CPU,GPU and FPGA,this thesis achieves the acceleration of MOND numerical sim-ulation.Experimental results show that the heterogeneous platform has better perfor-mance and lower power consumption than traditional high-performance CPU servers.When the system has 3x106 particles,the size of the grid is 1283 and the angle is set to be 0.5,compared to CPU server,the heterogeneous platform has a speedup of 9.37,and the energy reduction is 24.42.Finally,the thesis discusses the way to extend the platform to multiple computing nodes,analyzing the scalability of the design.The main research work of this thesis is as follows:(1)Based on features of MOND simulation,the thesis discusses the pros and cons of different N-body simulation algorithms and chooses TreePM algorithm,for the scale of simulation is large,the time of simulation is long,and the particles of the astro-physical system tend to be strongly clustered.It runs a sigle-thread TreePM program,analyzes the consuming of time of every part and discusses the bottleneck of the al-gorithm.For the establishment of Tree,the force calcultion of Tree part and the Fast Fourier Transform,the most time-consuming parts of TreePM,it compares the perfor-mance and power consumption of the accelarations on different platforms.In addition,it analyses the memory access of the TreePM algorithm and sorts the particle for the Tree,accelerating the potential calculation of Tree parts.(2)The thesis accelerates MOND simulation based on TreePM algorithm using a heterogeneous platform.FPGA is mainly used for the core calculation.Taking ad-vantage of dynamically reconfigurable feature,the solution can distribute the logic re-sources to Fast Fourier Transform and the potential calculation of the Tree parts.Mean-while,for the establishment of the tree,which is suitable for recursive calculation,is fulfilled by GPU.And the rest tasks,such as the distribution,the update of the position and the velocity of the particles as well as the input and output of the data,are assigned to CPU.The design takes full advantage of the features of different platforms,improves the performance per Watt of the TreePM algorithm.For the first time,the TreePM is run on a heterogeneous platform consist of FPGA,CPU and GPU.It provides a new way to accelerate N-body simulation.(3)To further explore the rationality of the design,the thesis puts forward a solution to expend the design.Using Peano-Hilbert curve for domain decomposition for the Tree parts,and taking advantage of the dynamic reconfiguration features,the expansion solution can assign the resource with fine-grained,reducing the cost due to work-load imbalance and achieving better extensibility.