Hierarkiska N-kroppsmetoder, som bygger på en grundläggande insikt i många fysiska processers natur, används i allt högre grad för att lösa storskaliga problem inom en mängd olika vetenskapliga/tekniska områden. Tillämpningar som använder dessa metoder är utmanande att parallellisera effektivt, men på grund av deras icke-uniforma, dynamiskt föränderliga egenskaper och deras behov av långdistanskommunikation. I detta dokument studerar vi de uppdelnings- och schemaläggningstekniker som krävs för att uppnå effektiv parallell prestanda på applikationer som använder en rad hierarkiska N-kroppsapplikationer. För att få representativ täckning undersöker vi ansökningar som använder de tre mest lovande metoderna som används idag. Två av dessa, Barnes-Hut-metoden och Fast Multipole-metoden, är de bästa metoderna kända för klassiska N-kroppsproblem (såsom molekylära eller galaktiska simuleringar). Den tredje är en ny hierarkisk metod för radiositetsberäkningar i datorgrafik, som tillämpar den hierarkiska N-kroppsmetoden på ett problem med mycket olika egenskaper. Vi finner att enkla nedbrytning tekniker som en automatisk schemaläggare kan genomföra inte skala väl, eftersom de inte kan samtidigt tillhandahålla lastbalansering och data lokalisering. Alla tillämpningar ger dock mycket goda parallella prestanda om lämpliga uppdelnings- och schemaläggningstekniker genomförs av programmeraren. För applikationerna Barnes-Hut och Fast Multipole visar vi att enkla men effektiva separationstekniker kan utvecklas genom att utnyttja några nyckelinsikter i både lösningsmetoderna och de klassiska problem som de löser. Med hjälp av en ny partitioneringsteknik uppnår även relativt små problem 45-faldiga speedups på en 48-processor Stanford DASH-maskin (en cache-sammanhängande, delad adressutrymme multiprocessor) och 118-faldiga speedups på en 128-processor simulerad arkitektur. De mycket olika egenskaperna hos radiosity applikationen kräver en annan partitionering / schemaläggning för att användas för det; men det ger också mycket bra parallell prestanda.
I detta sammanhang har metod för beräkningsfördelning och planering av arbetsbördan föreslagits i Ref.
Load Balancing and Data Locality in Adaptive Hierarchical N-body Methods: Barnes-Hut, Fast Multipole, and Radiosity
{'venue': 'Journal Of Parallel and Distributed Computing', 'journal': None, 'mag_field_of_study': ['Computer Science']}