본문 : Fast Fixed-Radius Nearset Neighbors: Interactive Million-particle Fluid
본문은 2013년 발표된 위 자료를 공부하며 작성한 글입니다.
Background
저는 CFD(Computational Fluid Dynamics) 해석 프로그램을 만드는 일을 하고 있습니다. 그 중에서도 Lagrangian 기반의 프로그램을 개발하고 있습니다. Lagrangian이 뭔가 하시겠지만, 어떤 입자들이 임의로 떠돌아다닌다고 생각하시면 됩니다. 아래 예시들처럼 입자의 위치가 시뮬레이션의 기반이 되는 것이죠.
이런 입자를 해석하는 프로그램들의 성능을 좌지우지하는 것 중 하나가 바로 근접 이웃 탐색 알고리즘 입니다. 입자 주변에 어떤 입자가 있는지 찾는 알고리즘이죠. 최근접 이웃 탐색과는 다르게 그냥 탐색 반경 R 내에 어떤 입자가 존재하는지 찾는 알고리즘입니다.
요런 입자 시뮬레이션은 계산하는 매 프레임마다 입자의 위치가 바뀝니다. 즉 주변의 입자가 계속 바뀐다는 말이고, 다른 말로는 근접이웃탐색 알고리즘이 매 프레임 수행돼야 한다는 말입니다. 따라서 이 알고리즘의 성능에 따라 프로그램 전체 성능이 좌지우지 된다는 것이죠.
근접이웃탐색 알고리즘은 위 그림처럼 각 입자의 반경 R 내의 이웃 입자를 탐색합니다. 뭐 다양한 알고리즘이 존재하겠다만 찾다보니 트리 형식이나 그리드 형식으로 추려지는 것 같습니다. 본문의 내용은 그 중 그리드를 기반으로 고안된 알고리즘입니다. NVIDIA에서 나온 만큼 GPU 기반이며, 구현이 필요하다면 CUDA나 Metal등 GPU 머신을 사용할 수 있는 언어를 사용해야할 필요가 있습니다.
k-Nearest Neighbor Algoithm
기존에 사용되던 그리드 기반 근접이웃탐색 알고리즘은 아래와 같습니다. 각 입자들에게 그리드의 인덱스를 부여받도록 하고, 그리드 인덱스 기준으로 정렬을 한 뒤, 그리드 인덱스별로 순회를 하는 것입니다.
여기서 정렬알고리즘이 들어가는데, 본문을 작성한 분의 이전 개발자 분은 cuda 내 thrust 라이브러리를 사용하텨 sorted by key를 적용했다고 합니다. thrust 라이브러리의 sort는 특정 조건이 맞춰지면 *기수정렬(radix sort) 알고리즘이 사용됩니다.
*기수정렬의 내용은 위 그림과 같으나, 정확한 설명은 나무위키(정렬 알고리즘)에도 잘 정리되어 있으니 참고바랍니다.
하지만 본문에서는 Counting Sort를 사용했다고 합니다. 시간 복잡도가 O(n+k)인데, k값은 데이터의 최대값입니다. 여기서는 그리드의 개수가 되겠습니다. k가 n 수준, 혹은 그것보다는 작다는 전제하에 선형적이 성능을 기대할 수 있습니다. 뭐 본문에서는 이를 통해서 효율을 높였다니 일단 믿고 갑시다.
결국에는 그리드 안의 입자개수도 세야하기 때문에 Counting sort가 더 좋다, 프레임당 커널 콜이 적어 장점이 있다는 식으로 말하는 듯 합니다. 해보기전엔 잘 모르겠습니다. ㅎㅎ 여하튼 그리드당 존재하는 입자수를 세는데도 강점이 있으니 분명 특정 조건(그리드와 입자가 존재하는 영역이 비슷한경우?)에서는 좋겠습니다.
생각해보니 이런 입자 시뮬레이션에서는 입자의 크기에 비해 그리드를 크게 잡으니, 어쩌면 그리드수와 입자수가 비슷할 듯 합니다. 입자하나가 터무니 없이 멀리 떨어지면 그리드 수가 많아 지겠지만 이런 녀석은 해석입자에서 제외해야합니다.
여하튼 유의미할 듯 합니다.
Conclusion
결국 엄청 빠르다네요! 아래 그림처럼 거의 뭐 3-4배 차이가 나는거 같은데, 제 개인 프로젝트에도 도움이 될만한지 면밀히 살펴보고 예제 코드를 짜서 실험해보면서 적용할만한지 판단해 봐야겠습니다.
마지막은 본문에서는 결국 이 알고리즘으로 11배를 이뤄냈다네요. ㅎㅎ 화려한 그림과 함께 마무리하겠습니다. 감사합니다.
댓글