입자계 연산의 고속 병렬화 알고리즘

Abstract

해석하고자 하는 계를 수많은 입자들의 집합체로 모델링하여 이들의 움직임과 상호작용을 연구하는 다체 문제(N-body problem)는 기본적으로 모든 개개의 입자가 그 자신을 제외한 다른 모든 입자와 가지는 상호 작용을 연산해야 하기 때문에, 입자의 수가 증가함에 따라 연산 횟수는 그 제곱에 비례한다는 어려움이 있다. 이러한 다체계 연산은 분자동역학과 같은 분자나 원자 단위에서 입자들을 다루게 되는 것으로부터 자체 중력장 조건에서의 은하나 성단의 움직임에 이르는 광범위한 스케일을 다루고 있다. 이와 같은 연산은 입자 간의 상호작용 형태에 따라 크게 두 가지 부류로 나눌 수 있는데 중력장(gravitational field)이나 전자기장(electromagnetic field)문제, 입자와법(vortex particle method)과 같은 원거리 힘 계산(long range force calculation)과 분자동역학(molecular dynamics)에서의 레너드-존스 12-6 포텐셜 혹은 평탄화 입자 유체역학(smoothed particle hydrodynamics, SPH)과 같이 상호작용을 구하기 위해 한 입자로부터 일정 거리 이내에 위치하는 입자들에 의한 영향 만을 구하는 근거리 힘 계산(short range force calculation)이다. 본 논문에서는 이들 각각에 대해 입자간 충돌이 고려되지 않는 경우를 대상으로 병렬화된 연산 환경에서 수행되는 고속의 입자계 수치해석을 위한 알고리즘에 관해 살펴보았다. 원거리 힘 계산을 수행하기 위한 새로운 트리코드인 k-tree가 제안되었다. 이 알고리즘은 입자계를 계층적 트리구조로 만드는데 있어서 입자 분포에 보다 적응적이며 좌표계에 독립적이고 주어지는 k값에 따라 트리의 차수를 달리할 수 있는 알고리즘이다. k값에 따른 특징이 분석적인 방법과 수치 실험에 의해 검토되었다. Barnes-Hut의 octtree (BH)와 비교할 때, 노드 평가 횟수 , 상호작용 횟수 그리고 연산 시간(wall-clock time) 모두 본 연구를 통해 제안되는 k-tree가 낮은 값으로 측정되어 원거리 힘 계산의 연산에 있어서 보다 효과적인 것으로 나타났다. 원거리 힘 계산을 위한 영역분할 기법으로 직교-재귀적 이분할법(ORB)과 Peano-Hilbert의 공간채움곡선을 이용하는 방법이 비교되었고, 국소 필수 트리(locally essential tree, LET)를 구현하여 이들 조합에 따라 중력장 문제를 대상으로 실제적 성능 차이에 관하여 살펴보았다. LET를 사용함에 따라서 두 영역분할 기법 모두에 대해 성능 향상이 뚜렷하였는데, 입자 수밀도의 차이가 큰 256만개의 Plummer sphere의 경우 연산 수행 시간이 최대 1/4정도로 감소하였다. k-tree를 3차원 입자와법에 적용한 결과 낮은 k값을 가지는 경우 효과적이었다. 근거리 힘 계산에 있어서 이웃 리스트(NL)를 사용하는 방법들로서 iCLL을 구현하였고 원거리 힘 계산에 사용하였던 트리코드(octtree)를 이용하여 NL을 만들고 이를 활용하는 방법(treecode)을 구현하여 이들의 성능을 비교하였는데 일반적인 모든 경우에 있어서 항상 iCLL이 treecode를 능가하였다. 그러나 열린 공간에 분사되는 액체 나노 제트 문제에 iCLL과 treecode를 적용하여 일부 유사한 조건을 가지는 문제에서는 treecode가 iCLL을 능가할 수 있음을 보였다. 병렬 연산 환경에서 근거리 힘 계산의 특성상 특별히 고려되어야 할 계산 과정들을 구분하였고, 이러한 계산이 매 타임 스텝마다 빈번한 입자 정보를 교환해야 한다는 특징을 고려하여, 국부적으로 불균일한 수밀도를 가지는 문제를 대상으로 하여 가장 통신량이 적으며 입자계 분포에 적응적인 기법에 관해 세 가지 영역 분할 기법(SLAB, CD, cORB)에 대해 수치적인 실험이 수행되었다. cORB는 입자계 분포에 가장 적응성이 뛰어난 반면 복잡한 통신으로 인해 통신에 많은 시간을 필요로 하여 프로세서 수가 증가함에 따라 성능이 감소하였으며, SLAB의 경우 제한된 조건에서 입자 분포에 대한 적응성을 가지며 가장 저렴한 비용으로 인접 프로세서 간 통신을 수행하고 많은 프로세서를 고려하는 경우에 대해서도 높은 병렬화 효율을 유지하였다.; The N-body problem is defined as the study of the effects of interaction between bodies on the behavior of a many-body system. Its difficulties come from the number of calculations increased as the square of the problem size N, because it has to evaluate the interactions on each body between all other bodies except itself. This N-body simulation handles the problems of various scales ranging from atomic or molecular scales to scales of galaxies or star clusters. The simulation of N-body problems typically involves two classes of physical phenomena: those governed by the long-range forces as seen from gravitational force calculations, electromagnetic filed problems and vortex particle methods in computational fluid dynamics and those governed by the short-range forces found from the Lennard-Jones 12-6 potential in molecular dynamics simulation or smoothed particle hydrodynamics. This study investigates each numerical algorithm for particle systems in parallel computing environments. The new 'k-tree' was proposed here for the long-range force calculations. This is more adaptable for the particle distributions in constructing hierarchical tree data structures, independent of the coordinate system and it can have different order of the tree with k provided. The characteristics of the k-tree for different k's were investigated by analytical methods and numerical experiments. Comparing with the octtree by Barnes and Hut (BH), the number of node evaluations NE, the number of interactions NI and the wall-clock time of the k-tree are measured and found to be smaller than those of the BH. As a result, the proposed k-tree algorithm was found that more effective for the long-range force calculations. The orthogonal recursive bisection method(ORB) and the method using the Peano- Hilbert space filling curve were compared for the domain decomposition for parallel long-range force calculations and also locally essential tree(LET) was implemented. By combining these schemes, the numerical experiments for the gravitational N-body problem were performed. It was remarkable that the effect of the LET for the two domain decomposition algorithms. The wall-clock time for the 2.56M Plummer sphere which has locally large differences in particle number density was decreased to 1/4. As the result of the k-tree applied to a 3-dimensional vortex particle simulation, it was found that the k-tree with small k is mostly effective. For the short-range force calculation, the iCLL(improved cell-linked list) algorithm which makes neighbor-list(NL) in a fast way and the method using tree structure to construct neighbor list were implemented and the performance of these two algorithms were compared. The results showed that the iCLL expels the treecode generally. But it was proved that a kind of counterexample which the treecode could override the iCLL from the liquid nanojet simulation injected to open space. Some special procedures in parallel stages of the short-range force calculation were suggested. Considering that the particle exchanging phase arises at every time step, we compared three domain decomposition algorithms (SLAB, CD and cORB) for the problems with non-uniform particle number density to find out the method which is adaptable to the particle distribution and communicates small amounts of data. It was proved that the cORB was the most adaptable to particle distribution, but the performance was decreased as the number of processors increased, because of the complexity of the communication of this algorithm. Under some restricted conditions the SLAB algorithm was adaptable to particle distributions, communicates with adjacent processors in the cheapest way and maintains high parallel performance when the number of processors is increased.