Simulace Barnes – Hut - Barnes–Hut simulation

The Simulace Barnes – Hut (pojmenované po Joshovi Barnesovi a Piet Hut ) je aproximační algoritmus za provedení n- simulace těla. Je pozoruhodné mít objednat Ó(n logn) ve srovnání s algoritmem přímého součtu, který by byl O (n2).[1]
Objem simulace je obvykle rozdělen na kubické buňky pomocí oktree (v trojrozměrném prostoru), takže pouze částice z blízkých buněk je třeba zacházet individuálně a s částicemi ve vzdálených buňkách je možné zacházet jako s jednou velkou částicí se středem v buňce těžiště (nebo jako nízký řád vícepólová expanze ). To může dramaticky snížit počet interakcí párů částic, které je třeba vypočítat.
Některé z nejnáročnějších vysoce výkonné výpočty projekty ano výpočetní astrofyzika pomocí algoritmu stromového kódu Barnes – Hut, jako je DEGIMA.[2][Citace je zapotřebí ]
Algoritmus
Strom Barnes – Hut
V trojrozměrném n- simulace těla, algoritmus Barnes – Hut rekurzivně rozděluje n těla do skupin jejich uložením do souboru oktree (nebo a čtyřkolka ve 2D simulaci). Každý uzel v tomto stromu představuje oblast trojrozměrného prostoru. Nejvyšší uzel představuje celý prostor a jeho osm dětí představuje osm oktanty prostoru. Prostor se rekurzivně dělí na oktanty, dokud každé další rozdělení neobsahuje 0 nebo 1 těla (některé oblasti nemají těla ve všech svých oktantech). V oktree jsou dva typy uzlů: interní a externí uzly. Externí uzel nemá žádné potomky a je buď prázdný, nebo představuje jedno tělo. Každý vnitřní uzel představuje skupinu těl pod ním a ukládá těžiště a celková hmotnost všech jejích dětských těl.
Distribuce částic připomínající dvě sousední galaxie.
Kompletní strom Barnes – Hut. (Uzly, které neobsahují částice, se nekreslí)
Uzly stromu Barnes – Hut používané pro výpočet síly působící na částici v počátečním bodě.
n- Simulace těla založená na algoritmu Barnes – Hut.
Výpočet síly působící na tělo
Pro výpočet čistá síla na určitém těle se procházejí uzly stromu, počínaje kořenem. Pokud je těžiště vnitřního uzlu dostatečně daleko od těla, považuje se tělesa obsažená v této části stromu za jedinou částici, jejíž poloha a hmotnost je příslušně těžiště a celková hmotnost vnitřního uzlu. Pokud je vnitřní uzel dostatečně blízko k tělu, proces se opakuje pro každé z jeho dětí.
Zda je nebo není dostatečně daleko od těla, záleží na kvocientu , kde s je šířka oblasti představovaná vnitřním uzlem a d je vzdálenost mezi tělem a těžištěm uzlu. Uzel je dostatečně daleko, když je tento poměr menší než prahová hodnota θ. Parametr θ určuje přesnost simulace; větší hodnoty θ zvýšit rychlost simulace, ale snížit její přesnost. Li θ = 0, žádný vnitřní uzel není považován za jedno tělo a algoritmus se degeneruje na algoritmus přímého součtu.
Viz také
Odkazy a zdroje
- Reference
- ^ Pfalzner, Susanne; Gibbon, Paul (1996). Metody stromů s mnoha těly ve fyzice. Cambridge [u.a.]: Cambridge Univ. lis. str.2, 3. ISBN 978-0-521-49564-6.
- ^ T. Hamada; et al. (2009). „Nový paralelní algoritmus více chodů pro stromový kód Barnes-Hut na GPU - směrem k nákladově efektivní a vysoce výkonné simulaci N-těla“. Comp. Sci. Res. Dev. 24 (1–2): 21–31. doi:10.1007 / s00450-009-0089-1. S2CID 31071570.
- Zdroje
- J. Barnes & P. Hut (prosinec 1986). "Hierarchický O (N logN) algoritmus výpočtu síly ". Příroda. 324 (4): 446–449. Bibcode:1986 Natur.324..446B. doi:10.1038 / 324446a0. S2CID 4267861.
- J. Dubinski (říjen 1996). "Paralelní stromový kód". Nová astronomie. 1 (2): 133–147. arXiv:astro-ph / 9603097v1. Bibcode:1996NováA .... 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 (říjen 1997). "Paralelní stromový kód pro velké Nsimulace těla: dynamická bilance zátěže a distribuce dat v systému CRAY T3D ". Komunikace počítačové fyziky. 106 (1–2): 105–113. arXiv:fyzika / 9709003. Bibcode:1997CoPhC.106..105B. doi:10.1016 / S0010-4655 (97) 00102-1. S2CID 18428101.
- T. Ventimiglia a K. Wayne. „Algoritmus Barnes – Hut“. Citováno 30. března 2012.
externí odkazy
- Treecodes, J. Barnes
- Paralelní TreeCode
- HTML5 / JavaScript Příklad Grafická simulace Barnes – Hut
- PEPC - docela efektivní paralelní Coulombův řešič, open-source paralelní stromový kód Barnes – Hut s vyměnitelným interakčním jádrem pro mnoho aplikací
- Paralelní program simulace GPU N-těla s rychlým procházením stromu bez stohování částic
- Simulátor galaxií Barnes-Hut na beltoforion.de