반스-헛 알고리즘

1. 개요[편집]

반스-헛 알고리즘 Barnes–Hut algorithm (treecode)
발표	Josh Barnes · Piet Hut, Nature 324 (1986)
푸는 문제	N개 입자의 전 쌍 힘 합
복잡도	O(N²) → O(N log N)
자료구조	사분트리(2D) · 팔진트리(3D)
노드에 저장	총질량 M, 질량중심 R (+선택적 사중극자)
손잡이	개구각 θ — 작을수록 정확·비쌈
상호작용	입자 ↔ 노드 (단방향)

반스-헛 알고리즘은 공간을 재귀적으로 8등분(3차원)한 트리의 각 노드에 그 안의 총질량과 질량중심을 미리 계산해 두고, 충분히 멀리 있는 노드는 «질량중심에 놓인 입자 하나»로 갈음해 힘을 계산하는 $O(N\log N)$ 알고리즘이다. 1986년 조시 반스와 피트 헛이 Nature 에 실은 네 쪽짜리 논문 하나로 계산천체물리의 규모 제한을 통째로 갈아치웠다.¹

동기는 N체 문제 쪽에 이미 정리돼 있다. 직접합은 $N(N-1)/2$ 쌍을 전부 더하므로 $N=10^6$ 이면 한 스텝에 $5\times10^{11}$ 번의 상호작용이고, 입자를 열 배 늘리면 백 배 느려진다. 반스-헛의 통찰은 우습도록 단순하다 — 멀리 있는 별 만 개가 만드는 중력은, 그 별 만 개를 뭉친 덩어리 하나가 만드는 중력과 거의 같다. 안드로메다 은하 전체가 지구에 미치는 조석력을 계산할 때 그 안의 별 $10^{12}$ 개를 하나씩 세지 않는 것과 같은 이야기다. 문제는 “거의”를 얼마나 믿을 것이냐이고, 그 신뢰도를 숫자 하나로 조절하는 것이 개구각 $\theta$ 다.

이 문서는 그 손잡이의 정체와 대가에 집중한다. 같은 계층 아이디어를 노드-노드 상호작용과 국소전개까지 밀어붙여 $O(N)$ 을 찍은 고속 다중극자법과의 비교는 그쪽 문서에 표까지 정리돼 있으니 여기서는 트리코드 고유의 사정만 판다.

2. 트리를 세운다[편집]

2차원이면 정사각형을 넷으로, 3차원이면 정육면체를 여덟으로 쪼갠다. 절차는 두 패스다.

1. 삽입. 전체를 감싸는 루트 상자에서 시작해 입자를 하나씩 넣는다. 이미 입자가 든 잎에 도달하면 그 잎을 쪼개고 둘 다 자식으로 내려보낸다. 잎 하나당 입자 한 개(또는 $s$ 개 이하)가 될 때까지 반복. 균일한 분포면 깊이가 $O(\log N)$ 이므로 삽입 총비용이 $O(N\log N)$ 이다.
2. 상향 패스. 잎에서 뿌리 방향으로 훑으며 각 노드의 총질량과 질량중심을 자식들로부터 합친다.

$$M_c = \sum_{k\in \text{child}} M_k, \qquad \mathbf R_c = \frac{1}{M_c}\sum_{k\in \text{child}} M_k \mathbf R_k$$

이 두 값이 노드에 캐시되는 전부다. 정확도를 조금 더 원하면 노드에 사중극자 모멘트 행렬(대칭 무자취라 3차원에서 성분 5개)까지 얹는데, 메모리와 상향 패스 비용이 늘어나는 대신 같은 정확도를 훨씬 큰 $\theta$ 에서 얻어 순이득인 경우가 많다. 반스-헛 원논문부터 이미 사중극자 옵션을 언급하고 있고, 오늘날 천체물리 트리코드는 대개 켜고 쓴다.

주의할 점 하나 — 질량중심을 쓰는 것 자체가 이미 최적화다. 노드 중심이 아니라 질량중심을 전개 원점으로 잡으면 쌍극자 항이 정확히 0 이 되어, 누락되는 최저차 항이 사중극자로 한 단계 올라간다. 트리코드가 단극자만으로도 쓸 만한 이유의 절반이 이 공짜 한 차수다.

3. 개구각 판정 — θ라는 손잡이[편집]

힘 계산은 입자마다 뿌리에서 시작하는 재귀 순회다. 현재 노드의 한 변 길이를 $s$, 입자에서 그 노드의 질량중심까지 거리를 $d$ 라 할 때

$$\frac{s}{d} < \theta \quad\Longrightarrow\quad \text{이 노드를 입자 하나로 취급하고 내려가지 않는다}$$

판정에 걸리지 않으면 자식 여덟 개로 내려가 같은 질문을 반복한다. 잎에 도달하면 그냥 직접 계산. 코드로는 스무 줄이 안 된다.

$\theta$ 는 정확도와 비용을 잇는 유일한 손잡이이고, 양 끝이 명확하다.

• $\theta = 0$ — 어떤 노드도 열리지 않는 조건을 만족하지 못해 항상 잎까지 내려간다. 정확히 직접합이며 트리 순회 오버헤드만큼 오히려 느리다.
• $\theta \to \infty$ — 루트에서 바로 멈춘다. 전 우주가 점 하나가 되고, 자기 자신까지 그 점에 포함되는 무의미한 답이 나온다.
• 실무 구간은 $\theta \approx 0.5{\sim}1.0$. 은하 시뮬레이션의 오랜 국룰이 $\theta = 0.5$ 이고, 통계량만 필요한 대규모 우주론 시뮬레이션에서 0.7~0.8까지 밀어 올린다.

오차 쪽 사정은 전개식을 보면 바로 읽힌다. 질량중심 원점에서 쌍극자가 죽으므로 퍼텐셜은

$$\phi(d) = -\frac{GM}{d}\left[\,1 + O\!\left(\left(\frac{s}{d}\right)^{2}\right)\right]$$

이고, 판정 조건이 $s/d<\theta$ 이니 노드 하나당 상대오차는 대략 $\theta^2$ 규모다. 사중극자 항까지 저장해서 빼 주면 다음 누락항이 팔중극자라 한 차수 더 내려간다. 다만 이건 노드 하나의 오차 규모일 뿐, 수천 개 노드 기여를 더한 뒤의 총오차가 얼마인지에 대한 보장은 아니다 — 아래에서 이야기한다.

비용은 반대 방향으로 움직인다. 3차원에서 입자 하나가 접촉하는 노드 수는 트리 깊이(∼$\log N$)에 층당 노드 수를 곱한 것인데, 각 층에서 “이제 막 열려야 하는” 노드들은 반경 $\sim s/\theta$ 짜리 껍질을 채우므로 그 개수가 $\sim\theta^{-3}$ 에 비례한다. 즉

$$\text{입자당 상호작용 수} \;\sim\; \mathcal O\!\left(\theta^{-3}\log N\right)$$

$\theta$ 를 반으로 줄이면 오차는 1/4로 줄지만 비용은 8배가 된다. 정확도 한 자리를 사는 값이 이 알고리즘에서 유난히 비싼 이유이고, 고정밀이 필요하면 $\theta$ 를 깎는 대신 아예 FMM으로 갈아타라는 조언이 나오는 이유다.

4. 오차는 «보장»되지 않는다[편집]

여기가 트리코드를 쓰는 사람이 반드시 알아야 하는 지점이다. 위의 $\theta^2$ 는 노드 하나에 대한 규모 추정이지 전체 오차의 상한이 아니다.

살몬과 워런(1994)은 표준 $s/d<\theta$ 판정이 특정 질량 분포에서 임의로 큰 오차를 낼 수 있음을 보였다. 병리의 핵심은 $s$ 와 $d$ 만 보는 판정이 노드 안에서 질량이 어떻게 놓였는지를 전혀 모른다는 데 있다. 질량중심이 상자 구석에 몰려 있으면 실제 입자들까지의 거리가 $d$ 보다 훨씬 짧을 수 있고, 그러면 전개의 수렴 조건 자체가 깨진다. 극단적으로는 노드 안의 어떤 입자가 관측 입자보다 질량중심 반대편에 있어 전개가 발산 영역에 들어간다.

그래서 현대 코드의 판정은 순수 기하가 아니다.

• 반스(1994)의 보정. 상자의 기하 중심과 질량중심의 어긋남 $\delta$ 를 판정에 넣어 $d > s/\theta + \delta$ 를 요구한다. 질량이 편중된 노드는 더 멀어야만 닫힌다.
• 상대 개구 판정. 전개 잔여항으로 힘 오차를 직접 추정해서 그것이 직전 스텝의 가속도 $|\mathbf a_{\rm old}|$ 의 일정 비율 $\alpha$ 이하일 때만 닫는다. 형태는 대략 $GM s^4/d^4 \le \alpha\,|\mathbf a_{\rm old}|$. 힘이 큰 입자에는 엄격하게, 약한 입자에는 느슨하게 굴어서 같은 비용으로 훨씬 균일한 상대오차를 준다. GADGET 계열의 기본값이 여기로 넘어간 지 오래다.

요약하면 “θ=0.5면 안전하다”는 정리가 아니라 경험칙이다. 오차를 사전에 보장하는 손잡이를 원한다면 그건 트리코드가 아니라 고속 다중극자법의 전개 차수 $p$ 다.

5. 고속 다중극자법과의 대비[편집]

한 해 뒤인 1987년에 나온 FMM은 같은 계층 아이디어를 훨씬 멀리 밀어붙인다. 구조적 차이는 딱 두 줄로 요약된다.

• BH는 입자 ↔ 노드. 관측 입자 하나마다 트리를 새로 내려간다. 노드가 아무리 커도 그 안의 입자 수와 무관하게 상호작용 한 번이지만, 관측 쪽은 언제나 입자 하나라 $N$ 번의 순회가 필요하고 그래서 $\log N$ 이 남는다.
• FMM은 노드 ↔ 노드 + 국소전개. 원천 노드의 다중극을 관측 노드의 국소전개(M2L)로 한 번에 넘기고, 그 국소전개를 하향 패스로 자식에게 물려준다(L2L). 관측 쪽도 뭉쳐서 처리하므로 $\log$ 가 사라져 $O(N)$ 이 된다.

그런데도 천체물리에서 트리코드가 살아남은 이유는 상수와 자료구조다. FMM은 상호작용 리스트·연산자 여섯 개·평면파 분해까지 구현이 수천 줄인데, 중력 시뮬레이션의 오차 예산은 어차피 초기조건·이체 완화·시간적분이 지배해서 1% 정확도면 충분하다. 밀도 동적 범위가 $10^6$ 을 넘나드는 적응 상황에서 단순한 자료구조가 잘 버틴다는 점도 크다. “하루 만에 짜서 그럭저럭 맞는 답”과 “몇 주 걸리지만 보장된 답”의 거래이고, 두 문화가 나뉜 자리가 정확히 여기다.

한편 둘 사이를 잇는 물건도 있다. 관측 입자를 하나씩 순회하는 대신 잎 상자 단위로 묶어 순회를 한 번만 하고 그 상자의 모든 입자가 같은 상호작용 리스트를 공유하게 하면(그룹 순회), 순회 비용이 잎 입자 수만큼 상각되고 SIMD 벡터화도 열린다. 여기에 관측 쪽에도 전개를 도입하면 그게 그냥 FMM이다. 두 알고리즘은 별개의 종이 아니라 같은 축의 양 끝이다.

6. 실무에서 만나는 것들[편집]

트리 선형화. 포인터를 따라다니는 재귀 순회는 캐시와 GPU의 천적이다. 그래서 입자를 공간 채움 곡선(모턴 Z-order 또는 힐베르트) 키로 정렬해 트리를 평평한 배열로 편다. 좌표 비트를 교차로 끼워 넣은 모턴 키는 상위 비트가 곧 트리 경로라, 정렬만 하면 트리가 사실상 완성된다. 순회도 재귀 대신 “건너뛸 노드 인덱스”를 각 노드에 저장해 반복문으로 바꾼다. 힐베르트 곡선은 모턴보다 국소성이 좋아 통신량이 줄지만 키 계산이 비싸다.

도메인 분할. 같은 곡선을 잘라 프로세스에 나눠 주면 그대로 병렬 컴퓨팅 분할이 된다. 각 프로세스는 자기 계산에 필요한 원격 노드만 미리 받아 국소 필수 트리(LET)를 만들어 두고 이후 통신 없이 순회한다. 노드마다 비용이 다르므로 입자 수가 아니라 직전 스텝의 실측 작업량으로 가중해 자르는 것이 부하 분산의 표준이다. 1990년대 초 워런과 살몬의 해시 팔진트리 구현이 이 패턴을 정착시켰고 고든 벨 상을 여러 번 받았다.

소프트닝 $\varepsilon$. 트리코드와 직접 상관은 없지만 세트로 붙어 다닌다. 은하 시뮬레이션의 “입자”는 별 하나가 아니라 $10^5\,M_\odot$ 짜리 통계 표본이므로 그 사이의 진짜 이체 산란은 물리가 아니라 잡음이고, 그래서 퍼텐셜을 $-GM/\sqrt{r^2+\varepsilon^2}$ 로 무르게 만든다. 자세한 사정과 “충돌계에서는 금기”라는 반대편 이야기는 N체 문제 쪽에 있다. 트리코드 입장에서 중요한 것은 $\varepsilon$ 이 잎 상자 크기와 같은 눈금에서 놀아야 한다는 것 — 잎보다 훨씬 큰 $\varepsilon$ 은 트리를 깊게 판 노력을 통째로 낭비한다.

트리 재구축 빈도. 매 스텝 다시 세우는 것이 기본이고 비용은 힘 계산의 10~20% 수준이라 대개 감수한다. 입자가 조금만 움직이는 국면에서는 트리 구조를 재사용하고 질량중심만 상향 패스로 갱신하는 절충이 쓰이는데, 위험이 하나 있다. 트리 구조가 바뀌는 순간 힘이 불연속적으로 튄다. 심플렉틱 적분기의 장기 에너지 보존성은 힘이 위치의 매끄러운 함수라는 것을 전제로 하므로, 이 불연속이 섀도 해밀토니안 논증을 훼손한다. 장기 궤도 적분에서 $\theta$ 를 보수적으로 잡고 재구축 규칙을 고정하는 이유다.

주기 경계. 우주론 상자는 주기 경계인데 중력은 상쇄가 없어 무한 격자합이 조건부 수렴이다. 트리코드는 근거리 힘을 트리로 구하고 이미지 상자들의 기여를 에발트 합산 보정표로 미리 만들어 더한다. 아예 원거리를 격자 고속 푸리에 변환에 맡기고 근거리만 트리로 하는 TreePM이 오늘날 우주론 코드의 표준이 됐다.

7. 중력 바깥으로[편집]

“모든 쌍을 더한다”는 구조를 가진 문제라면 커널만 갈아 끼우고 그대로 쓸 수 있다.

• 정전기·분자동역학. $1/r$ 커널이 같으니 원리상 바로 되지만, 전하는 양·음이 섞여 원거리 상호작용이 상쇄되고 계가 주기적이라 에발트 합산/PME가 여전히 강하다. 트리코드는 비주기·불균일 계에서 경쟁력이 생긴다.
• 소용돌이 입자법. 2차원 소용돌이 요소 사이의 비오-사바르 합이 $1/r$ 구조라 사분트리 트리코드가 그대로 붙는다. 보텍스 방법 계열이 실용적 규모로 올라간 것이 이 덕이다.
• 차원 축소. 의외의 손님인데, Barnes-Hut t-SNE(van der Maaten, 2014)가 $N^2$ 짜리 척력 항을 사분트리로 근사해 $O(N\log N)$ 으로 낮췄다. $\theta=0.5$ 라는 값이 은하 시뮬레이션에서 그대로 넘어와 쓰인다. 커널 밀도 추정과 $n$-점 상관함수 계산도 같은 골격이다.
• 레이 트레이싱·충돌 감지와의 사촌 관계. 경계 볼륨 계층은 “노드를 열지 말지 판정하며 트리를 내려간다”는 뼈대를 공유한다. 다만 그쪽 판정은 근사가 아니라 정확한 배제(교차하지 않으면 그 아래는 볼 필요가 없다)라 오차가 0이다. 근사냐 배제냐가 두 계보의 갈림길이다.²

8. 여담[편집]

• 반스와 헛의 논문은 학계에서 **“Nature에 실린 알고리즘 논문”**이라는 희귀 카테고리에 속한다. 본문이 짧고 그림 두 장에 의사코드도 없는데, 그 짧음이 오히려 아이디어의 명료함을 증명한 사례로 자주 인용된다.
• 트리코드 계열은 오랫동안 GPU에 잘 안 맞는다는 평을 들었다. 워프 안의 스레드들이 서로 다른 노드로 갈라져 순회 발산(divergence)이 심하기 때문. 그룹 순회로 리스트를 공유하고 트리를 선형 배열로 펴는 지금의 관행이 그 평판을 상당히 뒤집었지만, 여전히 직접합만큼 예쁜 GPU 컴퓨팅 커널은 아니다.³
• $\theta$ 를 조정하다 보면 반드시 겪는 일이 있다. 에너지 보존이 갑자기 좋아져서 기뻐했는데, 알고 보니 $\theta$ 를 키워 생긴 계통 오차가 시간적분 오차와 우연히 반대 부호로 상쇄된 것이었다는 결말. 보존량이 좋아 보인다고 해가 정확한 것은 아니다.

9. 관련 문서[편집]

• N체 문제 · 고속 다중극자법 · 다중극 전개
• 적응 격자 세분화 · 경계 볼륨 계층 · 충돌 감지
• 공간 채움 곡선 · 부하 분산 · 그래프 분할 · 병렬 컴퓨팅 · GPU 컴퓨팅
• 심플렉틱 적분기 · 베를레 적분
• 에발트 합산 · 분자동역학 · 고속 푸리에 변환
• 우주론 시뮬레이션 · SPH · 레이 트레이싱

10. Footnotes[편집]

1. Barnes, J. & Hut, P. (1986). “A hierarchical $O(N\log N)$ force-calculation algorithm”. Nature 324, 446–449. 복잡도를 아예 제목에 박아 넣은 배짱이 인상적이다. 참고로 두 사람이 같은 해 프린스턴 고등연구소에 있었고, 이 알고리즘은 은하 충돌 시뮬레이션을 돌리다가 “직접합으로는 도저히 안 되겠다”는 지극히 현실적인 좌절에서 나왔다. ↩

2. 그래서 게임 엔진 사람과 천체물리 사람이 트리 이야기를 하면 30분쯤 대화가 잘 통하다가 갑자기 어긋난다. 한쪽은 “노드를 닫으면 오차가 생긴다”고 하고 다른 쪽은 “노드를 닫으면 계산이 정확히 필요 없어진다”고 하기 때문이다. 같은 자료구조인데 판정의 의미가 정반대다. ↩

3. 튜토리얼과 벤치마크가 죄다 소프트닝 넣은 고정 스텝 직접합인 것도 이 때문이다. 직접합은 산술강도가 높고 분기가 없어 GPU 성능 그래프가 예쁘게 나오지만, 실제 연구 코드는 트리를 쓰고 그 그래프는 훨씬 못생겼다. 벤치마크에 나오는 N체는 아무도 연구에 쓰지 않는 N체다. ↩