Hierarchical tree algorithm for collisional N-body simulations on GRAPE

摘要

Wepresentanimplementationofthehierarchicaltreealgorithmontheindividualtimestepalgorithm(theHermitescheme)forcollisionalN-bodysimulations,runningontheGRAPE-9system,aspecial-purposehardwareacceleratorforgravitationalmany-bodysimulations.SuchacombinationofthetreealgorithmandtheindividualtimestepalgorithmwasnoteasyonthepreviousGRAPEsystemmainlybecauseitsmemoryaddressingschemewaslimitedonlytosequentialaccesstoafullsetofparticledata.ThepresentGRAPE-9systemhasanindirectmemoryaddressingunitandaparticlememorylargeenoughtostorealltheparticledataandalsothetreenodedata.Theindirectmemoryaddressingunitstoresinteractionlistsforthetreealgorithm,whichisconstructedonthehostcomputer,and,accordingtotheinteractionlists,forcepipelinescalculateonlytheinteractionsnecessary.Inourimplementation,theinteractioncalculationsaresignificantlyreducedcomparedtodirectN2summationintheoriginalHermitescheme.Forexample,wecanachieveaboutafactor30ofspeedup(equivalenttoabout17teraflops)againsttheHermiteschemeforasimulationofanN=106system,usinghardwareofapeakspeedof0.6teraflopsfortheHermitescheme.