The simulation of incompressible fluids including water, smoke, or fire is
widely used in various contents such as
TV commercials, feature films, virtual reality, and video games.
As time goes on, requests of an audience on the high-quality VFX have
increased, and accordingly the necessity of developing
a fast high-resolution fluid simulation method has also increased.
One of most time-demanding procedures
in the process of an incompressible fluid simulation is the projection,
which enforces zero-divergence of the velocity field
and helps to keep the original volume of fluids.
In this paper, we introduce the hybrid parallel multigrid Poisson solver
which makes full use of parallel processing on a CPU and a GPU.
First, we describe our parallelization strategy,
in which the CPU and the GPU handle
the procedures of fine grids and the coarsest grid, respectively.
This structure reflects characteristics of two processing units.
Modern CPU can directly access the main memory
which has enough space to accommodate data of high-resolution fine grids.
Whereas the GPU can accurately solve
the Poisson equation on the coarsest grid level
with thousands of cores in a short time.
Though this structure of parallelization takes advantage of both processing units,
the CPU or the GPU is idle when the other processing unit is main.
To resolve this inefficiency, we introduce the novel multigrid cycle,
which we call the {\em inverted A-cycle ($\forall$-cycle)}.
For V-cycle, each procedure depends on the result of previous procedure,
thus concurrent computation of more than one procedure is impossible.
To make the best use of the idle time on the CPU,
we decompose the residual field,
which is proportional to the difference between the current estimate and the solution,
to the high-frequency and the low-frequency components,
and then additional smoothing conducts on the high-frequency component on the CPU.
The experiments conducted on the simulation of smoke and turbulent flow with thermal buoyancy
showed that our scheme helps the estimate converge rapidly toward the solution.
We also introduce the boundary handling scheme,
which is conducted before the inter-grid transfer operations
and helps to improve the accuracy of the estimation.
Unlike the zero-filling scheme, which fills all empty and solid object cells with zeros,
our method fills extrapolated-values into the solid object cells.
Experiments show that
the residual decreases more rapidly when our proposed scheme is used.
유체 시뮬레이션은 TV광고, 영화, 애니메이션, 게임, 가상현실 등과
같은 응용 영역에서 널리 사용되고있다. HD화질의 미디어와 컨텐츠의 보급으로
관객들의 VFX에 대한 기대치는 날이 갈수록 높아지고 있다. 이에 발맞추어
고품질의 유체 애니메이션을 제작하기 위해서는 보다 빠르고 정확하게
시뮬레이션을 수행할 수 있는 기법의 개발이 필요하다.
물, 공기와 같은 비압축성 유체 시뮬레이션에 있어서 전통적으로 가장 많은 시간을
소요하는 부분은 프로젝션(projection) 단계이다. 프로젝션 단계는 유체를 움직여주는
속도장이 유체의 질량, 부피 등을 잘 보존할 수 있도록,
속도장을 발산하지 않게(divergence-free) 만들어주는 역할을 한다.
내부적으로 포아송 방정식을 풀게되는데 병렬처리가 쉽지 않고,
시뮬레이션 해상도가 증가함에 따라서 풀어야 하는 행렬의 크기가 증가하게 된다.
많은 연구자들이 비압축성 유체 시뮬레이션의 속도를 향상시키기 위해 여러
수치해석적인 기법들을 적용하였다.
초창기에는 연속 이상-휴식(succesive over-relaxation)과 같은 방법이 사용되었으며,
이후 공액 기울기 방법(conjugate gradient method), preconditioner를 사용한 공액 기울기 방법 등이 사용되었다.
공액 기울기 방법의 경우 낮은 해상도에서는 괜찮은 성능을 보이지만,
해상도가 높아짐에 따라 계산 속도가 현저하게 느려지는 단점이 있다.
고해상도 시뮬레이션에 대한 요구가 높아지고 있는 요즘은
해상도에 상관없이 빠른 계산속도를 보이는 멀티그리드(multigrid) 기법이 널리 사용되는 추세이다.
멀티그리드 기법에서는 계층구조를 가지는 일련의 그리드들(grid)을 오르내리며 빠르게 해를 구한다.
해(solution)와 현재 추측값(estimation)의 차이를 오차(error)라고 하는데
이 오차는 에러 스무딩(error smoothing)과정을 거치면서 줄어들게 된다.
이때, 오차의 고주파수 성분이 빠르게 감소하고,
저주파 성분은 느리게 감소하는 경향이 있다.
멀티그리드의 핵심 아이디어는 고해상도 그리드(fine grid)에서 정의된 문제를 저해상도 그리드(coarse grid)로 가지고 오면, 고해상도에서 쉽게 해결되지 않는
저주파성분 오차가 저해상도에서는
상대적으로 고주파 성분이 되어 빠르게 해결된다는 점이다.
멀티그리드를 이용한 프로젝션은 병렬처리 기법의 발전으로 한층 더
그 성능이 향상되었다.
병렬처리에는 주로 중앙처리장치(CPU)를 이용한 방법과 그래픽
처리장치(GPU)를 이용한 방법이 있다. 요즘 나오는 중앙처리장치는 다수의 코어를 가지며
상대적으로 용량이 큰 중앙메모리에 직접 접근할 수 있는 특징을 가진다.
이에 반해 그래픽처리장치는 중앙처리장치보다 훨씬 많은 코어를 가지지만,
상대적으로 크기가 작은 그래픽처리장치 전용 메모리를 가지며,
중앙메모리에 접근하려면 메모리복사를 수행해야하는 번거로움이 있다.
중앙처리장치 혹은 그래픽처리장치 중의 하나만을 사용해서
멀리티그리드를 병렬화하는 방법은 여러 연구자들에 의해 연구되어 왔다.
본 논문에서는 병렬처리의 효율을 보다 향상시키기 위해 중앙처리장치와 그래픽 처리장치를
동시에 활용하는 멀티그리드 기법을 소개한다. 장치의 특성에 맞추어 많은 메모리 용량을 필요로 하는
고해상도 그리드에서의 에러 스무딩과정은 중앙처리장치에서 멀티쓰레딩(multithreading)을 이용해 계산을 하고,
빠르고 정확하게 해를 계산해주는 것이 필요한 최저해상도 그리드에서의 에러스무딩 혹은 포아송 방정식 계산과정은
그래픽처리장치에서 담당한다. 이것은 각 장치의 특성을 잘 반영한 병렬 멀티그리드 구조이지만,
특정 시간에 쉬게되는(idle time) 장치가 발생하는 한계가 있다. 하지만 기존 멀티그리드 기법은 각 계산 단계가
이전 계산 단계 결과에 종속적이기 때문에 각각의 계산 단계를 동시에 서로 다른 장치에서 병렬처리할 수 없다.
우리는 멀티그리드 브이사이클(V-cycle)에 웨이블릿분해(wavelet decomposition)를 접목하여
그래픽처리장치가 최저해상도 그리드 레벨에서의 계산을 수행하는 동안
추가적인 인터미디엇 스무딩을(intermediate smoothing) 중앙처리장치에서 수행할 수 있는
인버티드에이 사이클(inverted A-cycle, ∀-cycle)을 소개한다.
각 그리드 레벨에서 프리스무딩(presmoothing)을 수행한 후에 잔차(residual field)의
고주파 성분을 웨이블릿분해하여 저장해 놓고 이에 대해 인터미디엇 스무딩을 수행한다.
연기와 열부력에 의한 난류성 유체 시뮬레이션에 제안한 방법을 적용해 보았다.
인버티드에이 사이클과 브이사이클을 이용해 각각 한번의 사이클을 수행하고 해의 정확도를 비교한 실험에서
제안한 방법은 기존 방법보다 나은 결과를 보였다. 그리고 사용자가 지정한 정확도를 만족시키기 위해
필요한 사이클의 반복 횟수와 계산 시간도 제안한 방법이 적게 소요하는 것을 확인하였다.
스칼라필드(scalar field)를 리스트릭션(restriction), 프롤롱게이션(prolongation) 과정을 통해
각 그리드 레벨 간에 이동시킬 때 유체셀(fluid cell)이 아닌 셀의 값을 적절하게 바운더리 처리해 주어야 한다.
가장 간단한 방법은 오브젝트셀(object cell)과 빈셀(empty cell)에 모두 0을 채우는 것이다.
하지만 이렇게 처리할 경우 리스트릭션, 프롤롱게이션에 트라이리니어 인터폴레이션(trilinear interpolation)이 사용되는 경우
오브젝트셀과 빈셀 인근 유체셀의 스칼라값이 감소되는 현상이 나타난다.
우리는 이를 대신해 오브젝트셀의 경우 인근 유체 셀들의 스칼라 값의 평균을 채우는 방법을 사용한다.
우리의 실험에서 이 방법은 단순히 0을 채우는 방법에 비해 보다 향상된 해의 정확도를 보여주었다.
