Fast N-Body Simulation

입자와법을 이용한 직접수치해석
Direct Numerical Simulation using Vortex Particle Method

일반적으로 유체유동의 해석에 사용되는 계산방법은 유동장 내부에 격자를 적절히 구성하고 이 격자점에서의 정보들을 계산하는 Eulerian method를 채택하고 있으나 이에 대조적인 방법으로 Lagrangean method를 이용한 유동의 해석도 시도되어지고 있는데 그 대표적인 것이 Vortex Particle Method이다. Vortex Particle Method는 1990년대 들어서 Leonard, Koumoutsakos, Winckelmans, Ploumhans 등에 의해 많은 발전이 이루어졌으며 최근 들어 비교적 낮은 레이놀즈 수에서 DNS에 견줄 정도로 매우 엄밀한 정도의 해석이 가능해지게 되었다. 이 방법은 Vorticity Transport Equation을 지배 방정식으로 사용하는데 3차원의 경우에 있어서는 Stretching항을 별도로 고려하여야 하며, Diffusion은 PSE (Particle Strength Exchange)의 방법으로 모사를 한다. 안정적인 입자계 연산을 위해서는 인접한 입자간의 거리를 일정한 정도로 유지해야 할 필요가 있는데 이를 위하여 매 3~5 step 마다 Particle Redistribution(Remesh)라는 작업을 필요로 한다.

아래의 그림은 Re=200에서 반구(Hemisphere)주위의 유동해석 결과이다. 구(Sphere)의 경우 구 후면에 생기는 후류의 형상은 레이놀즈수의 변화에 따라 크게 축대칭영역(Axisymmetric), 평면대칭영역(Plane Symmetric), 비대칭영역(Asymmetric) 이렇게 3가지로 구분되어 지는 반면, 반구의 경우 구보다 더 낮은 레이놀즈 수에서 이러한 영역이 발견된다. 실제 계산에 있어서는 무차원 시간간격은 0.02초, 고체의 반구를 구성하기 위해서 1만2천개의 입자를 사용하였으며 약 3,500,000개의 입자가 동원되었다.


입자와법의 병렬화를 위한 영역분할기법
Domain Decomposition Methods for Parallelized Vortex Element Method

고속화 방법을 사용하는 경우에 있어서, 병렬 연산환경에 맞추어 문제를 해석하는 경우 각각의 연산노드별로 이웃한 입자들이 전송되어져 별도의 계층화된 데이터구조를 가지도록 한다면 더욱 더 적은 연산횟수만으로 전체 입자들 간의 상호작용을 계산할 수 있다. 영역 분할 기법은 전체 입자계를 이웃하는 입자들로 집합을 만들어 각각의 연산노드로 할당할 수 있도록 하는 기법을 말한다. 이러한 기법으로는 다음과 같은 세가지 방법이 존재한다.

직교 재귀 이분할법(ORB,Orthogonal Recursive Bisection Method)

전체 입자들이 분포하는 공간의 각 방향 최대크기를 한 변의 길이로 하는 육면체를 만들고, 이중 가장 큰 길이 척도를 가지는 방향으로 두개의 부공간으로 분리하도록 분리 초평면을 만들어 많은 입자들 중에서 비교적 가까이 위치하는 입자들 끼리 서로 같은 부 공간으로 집합을 이루도록 한다. 이때 분리 초평면은 반복적인 방법에 의해 양쪽 부 공간에 동일한 개수의 입자가 위치하도록 결정하며, 이와 같은 과정을 재귀적(Recursive)인 방법으로 전체 연산노드의 수만큼 부공간이 분할될 때 까지 연속적인 이분할을 행하도록 한다. 이 방법은 비교적 빠르고 단순하여 사용하기에 용이하지만 몇가지 단점을 가지는데, 연산노드의 수가 2^N개가 아닌 경우 분할이 이루어지지 않거나 불균등한 분할을 초래하여 연산노드간 불균등한 부하분산을 유발할 수 있다는 점 등이다.

Morton Order

매 분할마다 8개의 부동간을 만든다는 점에서 ORB와 차이가 있으며 Barnes의 oct-tree와 동일하다. 우선 전체 입자가 분포하는 공간을 포함하는 정육면체를 생성하고 매 분할마다 이들을 각 방향으로 2분할하여 총 8개의 부공간을 동시에 생성한다. 이때 분리평면은 ORB와는 달리, 입자 분포와는 무관하게 원래의 정육면체 한변의 길이를 1/2로하는 부공간이 생성되도록 하는데, 이들 부공간들 간의 상대적인 위치별로 주소를 부여한다. 이때, 주소를 부여하는 방법은 이들 8개의 부공간들의 중심을 연결하는 전체 선분의 길이합이 최소가 되도록 한다. 이 방법은 위와 같은 분할이 하나의 부공간에 하나이하의 입자들이 존재할 때 까지 재귀적인 방법으로 행하여지며, 분할이 완료되면 만들어지는 트리의 끝단에는 이웃하는 입자들이 규칙적인 순서에 따라 배열되게 된다. ORB에서의 단점은 Fig.1(a)에서 알 수 있듯이 일부의 경우 이웃하는 입자와 입자가 실제 이웃하지 않으면서도 배열상에서 이웃할 수 있다는 점인데 Morton order는 이를 일부 개선한 것으로 생각할 수 있다.

Peano-Hilbert Order

입자계를 재배치하는 과정은 기본적으로는 Morton order와 동일하나 8개의 부공간을 생성할 때, 트리의 깊이별로 8개의 부공간의 상대적인 위치에 따른 주소 부여방식이 다르다. 이 방법은 다시 Morton order가 가지는 단점을 보완하도록 한 것으로서, Fig.1(b)에서 알 수 있듯이 일부 상위 부공간과 하위 부공간의 입자들이 바로 이웃하고 있지 않지만 이웃하는 것으로 배열상에 위치하도록 하는 문제점을 해결한 것이지만 부공간에 주소를 할당하는 방식이 복잡하여 구현하기가 어려운 편이다.

각각의 영역 분할 기법에 대해서 입자수를 달리 하여 연산을 수행 하였다. 병렬화된 입자와법의 연산에 있어서 영역분할 기법을 사용함으로 연산시간을 대폭적으로 단축할 수 있었으며 입자수가 증가함에 따라 그 차이가 커짐을 알 수 있었다. 그러나 각각의 기법에 따른 차이는 미미하였다. 영역분할기법을 입자와법에 적용하여 Re=100에서 구주위의 유동을해석하였으며, 고속화 알고리즘은 BH 알고리즘을 사용하였다. 이때 3가지 영역 분할 기법에 대하여 결과와 연산시간을 비교하였다. 항력계수는 모두 1.1로 측정되었으며 영역 분할 기법의 차이에 따른 오차는 존재하지 않았다. 연산은 32 node(AMD64 3000+ 와 512MB의 메모리)와 1GB swiching hub로 구성된 Linux Cluster System에서 하였으며, 연산하는데 걸린 시간은 약 72시간이 걸렸고, 입자수는 초기 3만개에서 무차원 시간 7초 후 약 120만개 였다.

단일 입자당 대류, 신장, 확산항을 모두 연산한 시간을 비교한 결과 영역분할 기법을 사용하지 않고 병렬화된 고속화 알고리즘만을 사용할 때와 영역분할 기법을 사용할때의 연산시간은 대략 3배 이상의 차이를 보인다. 각각의 영역 분할기법에 따른 연산시간의 차이는 정규화한 공간내에 규칙적으로 분포된 이상적인 경우의 차이보다는 미미하게 나타나며, 일부구간에서는 그 순서 또한 역전되는 경향을 보이기도 한다. 이것은 임의의 공간에 규칙성 없이 배열되어 있는 입자들을 분할 할때 Morton Order와 Peano-Hilbert Order가 입자의 개수로 분할을 하는 ORB와는 달리 공간을 중심으로 분할을 하기 때문에 분할된 공간에 입자가 없음으로 인한 배열 순서의 오류에서 생기는 문제점 일 것이다.

3차원 입자와법과 같은 입자계 연산에 있어서 병렬화와 고속화 알고리즘의 개발도 중요하지만 영역분할 기법의 적용으로 그 차이는 크게는 3배까지 그 차이를 보여 주는 결과를 볼때 영역분할 기법 또한 많이 중요하다는 것을 알 수 있다. 일반적으로 ORB 와 Morton Order, Peano Hilbert Order의 3가지방법에서는 Peano Hilbert Order가 가장 이득을 많이 보며 그 다음이 Morton Order 그리고 ORB의 순서로 알려져 있으나 실제문제에 적용한 결과 데이터의 구조에 따라 이 순서는 역전 될 수 있음을 보여 준다. 후류를 표현하는 입자들이 주 흐름 방향으로 길게 늘어서 있는 입자분포를 가지는 입자와법의 경우에 입자수가 많이 증가한 경우 ORB 그리고 Morton Order, Peano Hilbert Order의 순서로 나타났다. 이것은 데이터 구조의 차이로 인해 발생하는 각각 기법의 오차에서 생기는 결과 이다. 본 연구에서 다루었던 3가지 기법의 결과를 보면, 데이터의 구조에 따라 그 이득이 다르게 나타 날수 있음을 알 수 있으며, 데이터의 구조가 임의의 공간에 임의로 분포되어 있는 경우, 3가지 방법 중에 프로그램이 간단한 ORB 방법을 추천한다. 하지만 ORB 방법은 그 특성상 2n의 노드를 가지는 병렬 시스템에서만 적용이 가능하다는 문제점이 있으며, 반면 Morton Order와 Peano Hilbert Order는 병렬시스템의 노드수에 자유로운 장점을 가지고 있으므로 데이터 구조와 보유하고 있는 병렬시스템에 따라 영역 분할 기법의 적용을 다르게 해야 할 것이다.


다체계 연산의 새로운 고속화방법
A New Fast Algorithm for N-Body Simulation

다체계(N-body)문제는 천체물리 혹은 입자와법(Vortex Particle Method)에 의한 유동해석과 같이 전체 입자간의 상호작용을 모두 계산해야 하는 원거리(Long Range) 문제와, 분자동역학(Molecular Dynamics)과 같이 입자가 위치한 일정 영역내부에 포함된 입자들과의 상호작용만을 계산하는 근거리 문제(Short Range)로 나누어 생각할 수 있는데, 이러한 모두는 대규모 입자 데이터를 트리 구조(Tree Structure)로 만들어 이를 이용함으로써 고속화가 가능하며, 따라서 효율 좋은 트리 구조를 이용한 병렬화된 고속화 알고리즘(Fast Algorithm)이 다체계 연산에 있어서 가장 중요한 개발목표가 된다.

본 연구실에서는 입자의 공간분포에 맞도록 적응적으로 cell을 분할하도록 하여 기존의 Barnes & Hut 의 알고리즘에 비하여 보다 공간 효율이 향상된 트리 구조 데이터를 이용하는 새로운 고속화 알고리즘(Adaptive Tree)을 개발하였으며, 다양한 문제에 적용한 결과 입자간 상호작용 연산횟수가 약 30%정도 감소함을 확인하였고, 근거리 성능의 경우에 있어서도 기존의 방법에 비해 상당한 고속화가 가능한 것을 확인하였다. 따라서 입자와법을 사용하는 유동해석이나 분자동역학 시뮬레이션과 같은 다체계문제의 해석에 있어서, HW적으로는 병렬컴퓨터에 의하여, SW적으로는 새로운 고속화 알고리즘을 이용함으로써 연산능력이 비약적으로 향상되었다고 할 수 있다.