Abstrakt. Vi presenterar en effektiv och bevisligen bra partitionerings- och lastbalanseringsalgoritm för parallell adaptiv N-kroppssimulering. Huvudingrediensen i vår metod är en ny geometrisk karakterisering av en klass av kommunikationsgrafer som kan användas för att stödja hierarkiska N-kroppsmetoder såsom den snabba multipolmetoden (FMM) och Barnes-Hut-metoden (BH). Vi visar att kommunikationsdiagram över dessa metoder har en bra partition som kan hittas effektivt sekventiellt och parallellt. I synnerhet visar vi att en N-kropps kommunikationskurva (antingen för BH eller för FMM) kan delas upp i två subgrafer med samma beräkningsbelastning genom att ta bort endast O( ε n log n) och O(n 2/3 (log n) 1/3 ) antal noder, respektive för två och tre dimensioner. Dessa gränser på node-partition innebär gränser vid kant-partition av O( ε n(log n) 3/2 ) och O(n 2/3 (log n) 4/3 ), respektive för två och tre dimensioner. Såvitt vi vet är detta det första teoretiska resultatet på kvaliteten på partitionering av N-kroppskommunikationsgrafer för icke-uniformt fördelade partiklar. Våra resultat innebär att parallell adaptiv N-kroppssimulering kan göras så skalbar som beräkning på vanliga rutnät och lika effektiv som parallell N-kroppssimulering på jämnt fördelade partiklar.
I teoretiskt arbete på lastbalansering hierarkiska N-kroppsapplikationer, Teng partitioner kommunikationsgraf REF och visar vissa undertyper av kommunikationsgrafer kan partitioneras.
Provably Good Partitioning and Load Balancing Algorithms for Parallel Adaptive N-Body Simulation
{'venue': 'SIAM J. Scientific Computing', 'journal': 'SIAM J. Scientific Computing', 'mag_field_of_study': ['Mathematics', 'Computer Science']}