并行时空处理模型下的快速N-body算法

图形处理器(graphic processing unit,GPU)的最新发展已经能够以低廉的成本提供高性能的通用计算。基于GPU的CUDA(compute unified device architecture)和OpenCL(open computing language)编程模型为程序员提供了充足的类似于C语言的应用程序接口(application programming interface,API),便于程序员发挥GPU的并行计算能力。采用图形硬件进行加速计算,通过一种新的GPU处理模型——并行时间空间模型,对现有GPU上的N-body实现进行了分析,从而提出了一种新的GPU上快速仿真N-body问题的算法,并在AMD的HD Radeon 5850上进行了实现。实验结果表明,相对于CPU上的实现,获得了400倍左右的加速;相对于已有GPU上的实现,也获得了2至5倍的加速。

Development of Multilayer Models of Globular Star Clusters and Study of Their Evolution

Usually, models of globular star clusters are created by analyzing their luminosity and other observation parameters. The goal of this work is to create stable models of globular clusters based on the laws of mechanics. It is necessary to set the coordinates, velocities and masses of the stars so that as a result of their gravitational interaction the globular cluster is not destroyed. This is not an easy task, and it has been solved in this paper. Using an exact solution of the axisymmetric gravitational interaction of N-bodies, single-layer spherical structures were created. They are combined into multilayer models of globular clusters. An algorithm and a program for their creation is described. As a result of solving the problem of gravitational interaction of N bodies, evolution of 5-, 10-, and 15-layer structures was studied. During the inter-body interaction, there proceeds a transition from the initial specially organized structure to a structure with bodies, uniformly distributed in space. The number of inter-body collisions decreases, and the globular cluster model passes into the stable form of its existence. The collisions of bodies and the acquisition of rotational motion and thermal energy by them are considered. As a result of the passage to scaled dimensions, the results were recalculated to the conditions of globular star clusters. The periods of rotation and the temperatures of merged stars are calculated. Attention is paid to a decreased central-body mass in the analyzed models of globular star clusters.

A Simulation of the Dependence of Tidal Interaction on Galaxy Type in Compact Groups

We have investigated the role that different galaxy types have in galaxy-galaxy interactions in compact groups. N-body simulations of 6 galaxies consisting of a differing mixture of galaxy types were run to compare the relative importance of galaxy population demographic on evolution. Three different groups with differing galaxy content were tested: all spiral, a single elliptical and 50% elliptical. Tidal interaction strength and duration were recorded to assess the importance of an interaction. A group with an equal number of spiral and elliptical galaxies has some of the longest and strongest interactions with elliptical-elliptical interactions being most significant. These elliptical-elliptical interactions are not dominated by a single large event but consist of multiple interactions. Elliptical galaxies tidally interacting with spiral galaxies, have the next strongest interaction events. For the case when a group only has a single elliptical, the largest magnitude tidal interaction is an elliptical on a spiral. Spirals interact with each other through many small interactions. For a spiral only group, the interactions are the weakest compared to the other group types. These spiral interactions are not dominated by any singular event that might be expected to lead to a merger but are more of an ongoing harassment. These results suggest that within a compact group, early type galaxies will not form via merger out of an assemblage of spiral galaxies but rather that compact groups, in effect form around an early type galaxy.

N-Body问题在CUDA平台上并行实现研究

CUDA(Compute Unified Device Architecture,计算统一设备架构),是由NVIDIA开发的并行运算架构。对于软件开发人员,CUDA是一种通过行业标准语言,运行于图形处理单元上的计算方式。本文基于CUDA计算平台,对N-Body问题的并行实现算法进行了讨论,结果表明,合理的并行策略能有效地提高算法的运行效率。

基于Barnes Hut算法的N-body问题模拟

文章详细分析了Barnes-Hut算法的原理,并采用了Barnes-Hut算法模拟了2D N-body问题。Barnes-Hut算法采用了树形结构对质点所在的空间进行分割,并利用质心对足够远的质点群进行近似,从而使时间复杂度从直接计算的O(N2)减少到了O(N lg N)。

A NEW N-BODY POTENTIAL AND ITS APPLICATION

Based on the embedded atom method (EAM) proposed by Daw and Baskes and Johnson's model, this paper constructs a new N-body potential for bcc crystal Mo. The procedure of constructing the new N-body potential can be applied to other metals. The dislocation emission from a crack tip has been simulated successfully using molecular dynamics method, the result is in good agreement with the elastic solution.

N-Body Simulation Inspired by Metaheuristics Optimization

The N-body problem in classical physics, is the calculation of force ofgravitational attraction of heavenly bodies towards each other. Solving this problem for many heavenly bodies has always posed a challenge to physicists andmathematicians. Large number of bodies, huge masses, long distances and exponentially increasing number of equations of motion of the bodies have been themajor hurdles in solving this problem for large and complex galaxies. Adventof high performance computational machines have mitigated the problem to muchextent, but still for large number of bodies it consumes huge amount of resourcesand days for computation. Conventional algorithms have been able to reduce thecomputational complexity from O n2 ð Þ to O nlogn ð Þ by splitting the space into atree or mesh network, researchers are still looking for improvements. In thisresearch work we propose a novel solution to N-body problem inspired by metaheuristics algorithms. The proposed algorithm is simulated for various time periods of selected heavenly bodies and analyzed for speed and accuracy. Theresults are compared with that of conventional algorithms. The outcomes showabout 50% time saving with almost no loss in accuracy. The proposed approachbeing a metaheuristics optimization technique, attempts to find optimal solution tothe problem, searching the entire space in a unique and efficient manner in a verylimited amount of time.

On the Semianalytical Two-Body Regularization in N-Body Simulations

A two-body regularization for N-body problem based on perturbation theory for Keplerian problem is discussed. We provide analytical estimations of accuracy and conduct N-body experiments in order to compare it with state-of-the-art Hermite integrator. It is shown that this regularization keeps some features that allow overcoming KS-regularization in some particular cases.

On a New Method of N-Body Simulations

The theoretical foundation of a new N-body simulation method for the dynamics of large numbers (N > 106) of gravitating bodies is described. The new approach is founded on the probability description of the physical parameters and a similarity method which permits a manifold reduction of the calculation time for the evolution of “large” systems. This is done by averaging the results of calculations over an ensemble of many “small” systems with total particle number in the ensemble equal to the number of stars in the large system. The method is valid for the approximate calculation of the evolution of large systems, including dissipative systems like AGN containing a supermassive black hole, accretion disc, and the surrounding stellar cluster.

Numerical Investigations of a New N-body Simulation Method

Numerical investigation of a new similarity method (the Aldar-Kose method) for N-body simulations is described. Using this method we have carried out numerical simulations for two tasks: 1) calculation of the temporal behavior of different physical parameters of active galactic nuclei (AGN) containing a super massive black hole (SMBH), an accretion disk, and a compact stellar cluster;2) calculation of the stellar capture rate to the central SMBH without accretion disk. The calculations show good perspectives for applications of the similarity method to optimize the evolution model calculations of large stellar systems and of AGN.

BH算法的几点注记

N-Body问题的直接计算方法的时间复杂度是O(2),BH算法的时间复杂度为O(log)[1]。BH算法利用质心近似计算降低了时间复杂度,但同时也降低了计算结果的准确度。为把与判断足够远的参数(=/)密切相关的计算结果的近似准确度控制在要求的范围内,应用多极扩展和Gauss数值积分方法给出了BH算法质心近似的数学解释以及误差与参数的关系,得出BH算法是FMM算法和Gauss数值积分的一个特例,并指出Gauss积分法中隐含的正交多项式较FMM中常用的che-byshev正交多项式更与求解的问题相关。

FMM算法中问题规模与空间划分的关系分析

从编译优化和并行优化的角度出发,根据N-Body问题求解的FMM算法的原理,将算法分解为不同的子模块。详细分析了各子模块的计算特性,包括计算量分析、并行性分析、通信量分析和存储量分析。深入剖析问题规模与空间划分层数之间的关系,提出基于问题规模的空间划分策略。以实验验证了空间划分策略的可行性。

基于混合架构的FMM算法硬件加速

以高性能计算中的经典问题——多体问题的快速多极子(FMM)算法为例,分析FMM算法的各个步骤,根据计算、通信和存储特性将算法中的子过程归类。在CPU、GPU、FPGA和CELL上分别进行测试,提出执行FMM算法的混合可重构体系结构配置方案,并进一步优化算法,分解任务流。针对不同任务流的特点,提出可行的解决方案。结果证明,该方案可提高算法效率。

Particle-Particle算法并行化及改进

介绍了particle-particle算法的基本原理,并对串行particle-particle算法进行有效的 并行化;对并行算法的受力计算和通信过程进行改进;最后给出了实验结果,并进行相关性 能分析．

FMM算法在Cell/B.E.处理器上实现的分析与验证

FMM算法[1]是基于树结构的,用于解决多体问题(N-Body)的经典算法。它将N-Body问题的计算复杂度由O(N2)降为O(N),并且能达到任意精度。通用CPU在计算规模较大的N-Body问题时需要耗费大量的时间。为了加速算法的执行,本文对FMM算法在Cell/B.E.处理器上的实现进行了分析与验证。首先从功能上将FMM算法分解为八个核心过程,在此基础上根据计算特点的不同,对八个核心过程进行归类,最后选取其中有代表性的核心步骤,阐述了其在Cell/B.E.上实现的可行性问题,以及部分核心步骤的设计和实现过程。实验结果表明,选定的FMM算法核心步骤在Cell/B.E.上可以获得相对通用CPU较高的加速比。

Accurate machine learning models based on small dataset of energetic materials through spatial matrix featurization methods

A large database is desired for machine learning(ML) technology to make accurate predictions of materials physicochemical properties based on their molecular structure.When a large database is not available,the development of proper featurization method based on physicochemical nature of target proprieties can improve the predictive power of ML models with a smaller database.In this work,we show that two new featurization methods,volume occupation spatial matrix and heat contribution spatial matrix,can improve the accuracy in predicting energetic materials' crystal density(ρ_(crystal)) and solid phase enthalpy of formation(H_(f,solid)) using a database containing 451 energetic molecules.Their mean absolute errors are reduced from 0.048 g/cm~3 and 24.67 kcal/mol to 0.035 g/cm~3 and 9.66 kcal/mol,respectively.By leave-one-out-cross-validation,the newly developed ML models can be used to determine the performance of most kinds of energetic materials except cubanes.Our ML models are applied to predict ρ_(crystal) and H_(f,solid) of CHON-based molecules of the 150 million sized PubChem database,and screened out 56 candidates with competitive detonation performance and reasonable chemical structures.With further improvement in future,spatial matrices have the potential of becoming multifunctional ML simulation tools that could provide even better predictions in wider fields of materials science.

Existence and Uniqueness of Nested Regular Quadrilateral Central Configurations

Two cases of the nested configurations in R3 consisting of two regular quadrilaterals are discussed. One case of them do not form central configuration, the other case can be central configuration. In the second case the existence and uniqueness of the central configuration are studied. If the configuration is a central configuration, then all masses of outside layer are equivalent, similar to the masses of inside layer. At the same time the following relation between r(the ratio of the sizes) and mass ratio b = m/m must be satisfied in which the masses at outside layer are not less than the masses at inside layer, and the solution of this kind of central configuration is unique for the given ratio (6) of masses.

HIKER:a halo-finding method based on kernel-shift algorithm

We introduce a new halo/subhalo finder,HIKER(a Halo fInder based on KERnel-shift algorithm),which takes advantage of a machine learning method–the mean-shift algorithm combined with the Plummer kernel function,to effectively locate density peaks corresponding to halos/subhalos in density field.Based on these density peaks,dark matter halos are identified as spherical overdensity structures,and subhalos are bound substructures with boundaries at their tidal radius.By testing HIKER code with mock halos,we show that HIKER performs excellently in recovering input halo properties.In particular,HIKER has higher accuracy in locating halo/subhalo centres than most halo finders.With cosmological simulations,we further show that HIKER reproduces the abundance of dark matter halos and subhalos quite accurately,and the HIKER halo/subhalo mass functions and Vmax functions are in good agreement with two widely used halo finders,SUBFIND and AHF.

A New Kind of Conjugate-nested Central Configurations in Consisted of One Regular Tetrahedron and One Regular Octahedron

A new case configuration in R^3, the conjugate-nest consisted of one regular tetrahedron and one regular octahedron is discussed. If the configuration is a central configuration, then all masses of outside layer are equivalent, the masses of inside layer are also equivalent. At the same time the following relation between ρ（r =√3/3ρ is the radius ratio of the sizes） and mass ratio τ=~↑m/m must be satisfied τ=~↑m/m=ρ（ρ＋3）（3＋2ρ＋ρ^2）^-3/2＋ρ（-ρ＋3）（3-2ρ＋ρ^2）^-3/2-4.2^-3/2ρ^-2-^-1ρ^-2/2（1＋ρ）（3＋2ρ＋ρ^2）^-3/2＋2（ρ-1）（3-2ρ＋ρ^2）^-3/2-4（2√2）^-3ρ, and for any mass ratio τ, when mass ratio r is in the open interval （0, 0.03871633950 ... ）, there exist three central configuration solutions（the initial configuration conditions who imply hamagraphic solutions） corresponding radius ratios are r1, r2, and r3, two of them in the interval （2.639300779… , ＋∞） and one is in the interval （0.7379549890…, 1.490942703… ）. when mass ratio τ is in the open interval （130.8164950… , ＋∞）, in the same way there have three corresponding radius ratios, two of them in the interval （0, 0.4211584789... ） and one is in the interval （0.7379549890…, 1.490942703…）. When mass ratio τ is in the open interval （0.03871633950…, 130.8164950…）, there has only one solution r in the interval （0.7379549890…, 1.490942703… ）.

Hydrodynamical simulations of the triggering of nuclear activities by minor mergers of galaxies

Major mergers of galaxies are considered to be an efficient way to trigger Active Galactic Nuclei and are thought to be responsible for the phenomenon of quasars. This has however recently been challenged by observations of a large number of low luminosity Active Galactic Nuclei at low redshift(z■1) without obvious major merger signatures. Minor mergers are frequently proposed to explain the existence of these Active Galactic Nuclei. In this paper, we perform nine high resolution hydrodynamical simulations of minor galaxy mergers, and investigate whether nuclear activities can be efficiently triggered by minor mergers, by setting various properties for the progenitor galaxies of those mergers. We find that minor galaxy mergers can activate the massive black hole in the primary galaxy with an Eddington ratio of f Edd > 0.01 and> 0.05(or a bolometric luminosity > 10^43 and > 10^44 erg s^-1) with a duration of 2.71 and 0.49 Gyr(or 2.69 and 0.19 Gyr), respectively. The nuclear activity of the primary galaxy strongly depends on the nucleus separation, such that the nucleus is more active as the two nuclei approach each other. Dual Active Galactic Nuclei systems can still possibly be formed by minor mergers of galaxies, though the time duration for dual Active Galactic Nuclei is only ~ 0.011 Gyr and ~ 0.017 Gyr with Eddington ratio of f Edd > 0.05 and bolometric luminosity > 10^44 erg s^-1. This time period is typically shorter than that of dual Active Galactic Nuclei induced by major galaxy mergers.