반스-허트 시뮬레이션

반스 가족을 이용한 100대 신체 시뮬레이션푸른색 상자처럼 시각적으로 움푹 패인 나무.

반스-더Hut 시뮬레이션(Josh Barnes and Piet Hut의 이름)은 n-body 시뮬레이션을 수행하기 위한 근사 알고리즘이다. O(n²)가 될 다이렉트섬 알고리즘에 비해 오더 O(n log n)가 있다는 점이 눈에 띈다.^[1]

시뮬레이션 용적은 보통 8진법(3차원 공간에서)을 통해 입방세포로 나뉜다. 그래서 인근 세포의 입자만 개별적으로 처리하면 되고, 먼 세포의 입자는 세포 질량 중심을 중심으로 한 하나의 큰 입자(또는 저차 멀티폴 팽창)로 취급할 수 있다. 이것은 계산되어야 하는 입자 쌍 상호작용의 수를 극적으로 줄일 수 있다.

가장 까다로운 고성능 컴퓨팅 프로젝트 중 일부는 Barnes-를 사용하여 계산 천체물리학을 수행한다.DEGIMA와 같은 Hut 트리코드 알고리즘.^[2]^{[citation needed]}

알고리즘.

반스-더오두막 나무

3차원 n-body 시뮬레이션에서 반즈-Hut 알고리즘은 n체를 8진수(또는 2D 시뮬레이션에서 쿼드 트리)에 저장하여 반복적으로 그룹으로 나눈다. 이 트리의 각 노드는 3차원 공간의 영역을 나타낸다. 가장 위쪽의 노드는 전체 공간을 나타내며, 그것의 여덟 명의 아이들은 공간의 여덟 옥텟을 나타낸다. 공간은 각 구획이 0개 또는 1개의 몸체를 포함할 때까지 8진법으로 재귀적으로 세분된다(일부 지역은 모든 옥타트에 몸을 포함하지 않는다). 8진수에는 내부 노드와 외부 노드의 두 가지 유형이 있다. 외부 노드는 자녀가 없으며 비어 있거나 단일 본체를 나타낸다. 각각의 내부 노드는 그 아래에 있는 몸의 그룹을 나타내며, 질량의 중심과 모든 아이들의 총 질량을 저장한다.

두 개의 인접한 은하를 닮은 입자 분포.
전체 반스-오두막 나무 (입자를 포함하지 않는 노드는 그려지지 않음)
반스-노드즈오두막 나무는 기원 지점에서 입자에 작용하는 힘을 계산하는 데 사용된다.
미디어 재생

반스-바디 시뮬레이션에 기반 n-Body 시뮬레이션오두막 알고리즘.

신체에 작용하는 힘 계산

특정 본체에 대한 순력을 계산하기 위해 트리의 노드가 루트부터 통과된다. 내부 노드의 질량 중심이 신체에서 충분히 멀리 떨어져 있는 경우, 나무의 그 부분에 포함된 신체는 각각 내부 노드의 질량과 총 질량의 중심이 되는 단일 입자로 처리된다. 내부 노드가 신체에 충분히 가까이 있으면 그 과정은 각각의 자식에게 반복된다.

노드가 신체에서 충분히 멀리 떨어져 있는지 여부는 인수의 $s/d$ / $s/d$ ${\d$ 디스플레이 $스타일$ s/ $d}$ 에 따라 달라지는데 $s/d$ 여기서 s는 내부 노드로 대표되는 영역의 폭이며 d는 신체와 노드의 질량 중심 사이의 거리이다. 이 비율이 임계값 θ보다 작을 때 노드는 충분히 멀리 있다. 매개변수 θ은 시뮬레이션의 정확도를 결정한다. θ 값이 클수록 시뮬레이션 속도는 증가하지만 정확도는 감소한다. θ = 0이면 내부 노드를 단일 본체로 취급하지 않고 알고리즘이 직접섬 알고리즘으로 변질된다.

참고 항목

참조 및 출처

참조

^ Pfalzner, Susanne; Gibbon, Paul (1996). Many-body tree methods in physics. Cambridge [u.a.]: Cambridge Univ. Press. pp. 2, 3. ISBN 978-0-521-49564-6.
^ T. Hamada; et al. (2009). "A novel multiple-walk parallel algorithm for the Barnes-Hut treecode on GPUs – towards cost effective, high performance N-body simulation". Comp. Sci. Res. Dev. 24 (1–2): 21–31. doi:10.1007/s00450-009-0089-1. S2CID 31071570.

원천

J. Barnes & P. Hut (December 1986). "A hierarchical O(N log N) force-calculation algorithm". Nature. 324 (4): 446–449. Bibcode:1986Natur.324..446B. doi:10.1038/324446a0. S2CID 4267861.
J. Dubinski (October 1996). "A Parallel Tree Code". New Astronomy. 1 (2): 133–147. arXiv:astro-ph/9603097v1. Bibcode:1996NewA....1..133D. doi:10.1016/S1384-1076(96)00009-7. S2CID 119464486.
U. Becciani; R. Ansalonib; V. Antonuccio-Delogua; G. Erbaccic; M. Gamberaa & A. Pagliarod (October 1997). "A parallel tree code for large N-body simulation: dynamic load balance and data distribution on a CRAY T3D system". Computer Physics Communications. 106 (1–2): 105–113. arXiv:physics/9709003. Bibcode:1997CoPhC.106..105B. doi:10.1016/S0010-4655(97)00102-1. S2CID 18428101.
T. Ventimiglia & K. Wayne. "The Barnes–Hut Algorithm". Retrieved 30 March 2012.

외부 링크

트리코드, J. 반스
병렬 트리코드
HTML5/JavaScript 예제 그래픽 반즈-허트 시뮬레이션
PEPC – 오픈 소스 병렬 Barnes – PEPC-Pretty Efficient Parallel Coulomb 해결사다수의 애플리케이션에 대해 교환 가능한 상호 작용 커널이 있는 오두막 트리 코드
빠른 스택 없는 입자 트리를 이용한 병렬 GPU N-body 시뮬레이션 프로그램
벨토포리온의 반스허트 은하 시뮬레이터.드

[1] Pfalzner, Susanne; Gibbon, Paul (1996). Many-body tree methods in physics. Cambridge [u.a.]: Cambridge Univ. Press. pp. 2, 3. ISBN 978-0-521-49564-6.

[2] T. Hamada; et al. (2009). "A novel multiple-walk parallel algorithm for the Barnes-Hut treecode on GPUs – towards cost effective, high performance N-body simulation". Comp. Sci. Res. Dev. 24 (1–2): 21–31. doi:10.1007/s00450-009-0089-1. S2CID 31071570.

[1]

[2]

Search