Barnes-Hut

This Splash2 benchmark computes the interaction between N bodies as time evolves. Each time iteration requires rebalancing a tree containing all particles, computing force interactions hierarchically, moving particles, and updating the particle tree. The original Splash2 algorithm retrieves data from remote processes on a need basis during the force computation phase. A variation of this algoritm more suitable to message passing retrieves a superset of required remote data before the force computation phase. The CGD implemention presented here relies on the original algorithm.

Types

// Domain related types
type range Tree, List;
type partition <Tree> TreePart [PartNP];
type partition <List> ListPart [PartNP];

// Data types
type data Int, Bool, File, Vector, Box, Params, Stats;
type data<Box> BoxArray [PartNP];
type data<Stats> StatsArray [PartNP];

type data BodyPM [TreePart, ListPart];
type data BodyScore [TreePart, ListPart], BodyAccel [ListPart];
type data NodePM [TreePart], NodeScore [TreePart];

Parallel Computations

// Main function

function mainloop ( pari -> stats )
  StatsArray stats[PPEn], Params pari[ALL1]
{
  // Decomposition rules
  part list = tree_loc;
  part list0 = tree_loc0;

  // Compute initial tree
  readBodies ( pari -> par, bodyi [listi], listi );
  initTop    ( par -> tree_topi );

  Minmax    ( bodyi [listi] -> Mi );
  makeTree  ( bodyi [listi], tree_topi, Mi -> 
              body0 [tree_loc0+], tree_loc0 [PPEn+] );
  aliasPart ( tree_loc0, tree_topi -> tree_bot0, tree_top0, list0 );
  initBody  ( par -> body_sc0 [list0], stats0 [PPEn] );

  // Main loop
  loop ( idx, cond ; 
	 body0 [tree_loc0], body_sc0 [tree_loc0], stats0 [PPEn],
	 tree_loc0 [PPEn], tree_top0 [PPEn], tree_bot0 [PPEn], list0 [PPEn]
	 ->
	 bodyout [tree_loc], body_sc [tree_loc], stats [PPEn],
	 tree_loc [PPEn], tree_top [PPEn], tree_bot [PPEn], list [PPEn] )
  { 

    // Build partitions
    Score   ( body_sc0 [tree_loc0], tree_top0, tree_bot0 -> 
              node_sc0 [tree_loc0] );
    balance ( par, node_sc0 [tree_loc0+] -> tree_top01 );
    
    // Build top tree
    Minmax    ( body0 [list0] -> M );
    makeTree  ( body0 [list0], tree_top01, M -> 
                body [tree_loc+], tree_loc [PPEn+] );
    aliasPart ( tree_loc, tree_top01 -> tree_bot, tree_top, list );

    // Compute center of mass
    CtrMass ( body [tree_loc], tree_top, tree_bot -> node [tree_loc] );

    // Hierarchical force calculation
    force   ( par, M, body [tree_loc+], node [tree_loc+], stats0 [PPEn] -> 
	      body_sc [list], body_ac [list], stats [PPEn] );

    // Move particles
    advance ( par, idx, body [list], body_ac [list] -> bodyout [list] );

    endCond ( par, idx -> cond );
  }
  
  // Output results
  out ( par, bodyout [list+], list[ALLn] );
}

// Compute node score starting from bodies

function Score (body_sc, tree_top, tree_bot, tree_loc -> node_sc)
  BodyScore body_sc[tree_loc],
  NodeScore node_sc[tree_loc],
  TreePart tree_top[PPEn], tree_bot[PPEn], tree_loc[PPEn]
{
  // Decomposition rules
  part tree_loc = tree_top + tree_bot;

  scoreb (body_sc [tree_bot]  -> node_sc [tree_bot]);
  scoret (node_sc [tree_bot+] -> node_s2 [tree_top]);
  copy   (node_s2 [tree_top]  -> node_sc [tree_top]);
}

// Compute node center of mass starting from bodies

function CtrMass (body_pm, tree_top, tree_bot, tree_loc -> node_pm)
  BodyPM body_pm [tree_loc],
  NodePM node_pm [tree_loc],
  TreePart tree_top[PPEn], tree_bot[PPEn], tree_loc[PPEn]
{
  // Decomposition rules
  part tree_loc = tree_top + tree_bot;

  ctrmassb (body_pm [tree_bot]  -> node_pm [tree_bot]);
  ctrmasst (node_pm [tree_bot+] -> node_p2 [tree_top]);
  copy     (node_p2 [tree_top]  -> node_pm [tree_top]);
}

// Compute bounding box for all bodies

function Minmax (body, list -> M)
  BodyPM body[list],
  Box M[ALL1],
  ListPart list[PPEn]
{
  minmaxlt <ALL1> (body [list] -> Mnp[PPEn]);
  minmaxnp <ONE1> (Mnp[ONEn] -> M[ONE1]);
}

Declarations

// Main

function balance (par, score, loc -> top2)
  Params par, 
  NodeScore score[loc+],
  Tree loc, top2;

function makeTree (body, top, M, list -> body2, loc2)
  BodyPM body[list], body2[loc2],
  Tree top, loc2, 
  List list,
  Box M;

function force (par, M, body, node, stats, list, loc -> score, accel, stats*)
  Params par, Box M,
  BodyPM body [loc+],
  NodePM node [loc+], 
  BodyAccel accel[list],
  BodyScore score[list],
  Stats stats, stats*,
  Tree loc, List list;

function advance (par, idx, body, accel, list -> body2)
  Params par, Int idx,
  BodyPM body[list], body2[list],
  BodyAccel accel[list],
  List list;

// Auxiliary

function readBodies (par -> par*, body, list)
  Params par, par*, BodyPM body[list], List list;

function out (par, body, list)
  Params par, BodyPM body[list+], ListPart list[ALLn];

function initTop (par -> top)
  Params par, Tree top;

function initBody  (par, list -> body_sc, stats)
  Params par, BodyScore body_sc[list], List list, StatsArray stats[PPEn];

function endCond (par, idx -> cond)
  Params par, Int idx, Int cond;

function aliasPart (loc, top0 -> bot, top, list)
  TreePart loc[PPEn], top0[PPEn], top[PPEn], bot[PPEn], ListPart list[PPEn];

// Aggregate

function scoreb (body, bot -> node)
  BodyScore body[bot],
  NodeScore node[bot],
  Tree bot;

function scoret (node, top, bot -> node2)
  NodeScore node[bot+], node2[top],
  Tree top, bot;

function ctrmassb (body, bot -> node)
  BodyPM body[bot],
  NodePM node[bot],
  Tree bot;

function ctrmasst (node, top, bot -> node2)
  NodePM node[bot+], node2[top],
  Tree top, bot;

function minmaxlt (body, list -> M)
  BodyPM body[list], Box M, List list;

function minmaxnp (Mnp, ra -> M)
  BoxArray Mnp[ra], RangeNP ra, Box M;

Files


ProgrammerCompiler generated
CGD sourceType DeclarationsSequential ComputationsComputation DeclarationsParallel Functions
Barnes-Hut
barnes.pdbarnes.hbarnes.cc
bn_force.cc
... (download)
barnes_decl.hbarnes_auto.cc