Robust/src/Benchmarks/oooJava/barneshut/Barneshut.java

   1 /*
   2 Lonestar Benchmark Suite for irregular applications that exhibit
   3 amorphous data-parallelism.
   4
   5 Center for Grid and Distributed Computing
   6 The University of Texas at Austin
   7
   8 Copyright (C) 2007, 2008, 2009 The University of Texas at Austin
   9
  10 Licensed under the Eclipse Public License, Version 1.0 (the "License");
  11 you may not use this file except in compliance with the License.
  12 You may obtain a copy of the License at
  13
  14 http://www.eclipse.org/legal/epl-v10.html
  15
  16 Unless required by applicable law or agreed to in writing, software
  17 distributed under the License is distributed on an "AS IS" BASIS,
  18 WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  19 See the License for the specific language governing permissions and
  20 limitations under the License.
  21
  22 File: SerialBarneshut.java
  23  */
  24
  25
  26 public final class Barneshut {
  27   private  int nbodies; // number of bodies in system
  28   private  int ntimesteps; // number of time steps to run
  29   private  double dtime; // length of one time step
  30   private  double eps; // potential softening parameter
  31   private  double tol; // tolerance for stopping recursion, should be less than 0.57 for 3D case to bound error
  32
  33   private  double dthf, epssq, itolsq;
  34   private  OctTreeLeafNodeData body[]; // the n bodies
  35   private  double diameter, centerx, centery, centerz;
  36   private  int curr;
  37
  38   private  boolean isFirstRun;
  39
  40   public boolean validationTest;
  41
  42   public  Barneshut(){
  43     isFirstRun = true;
  44     validationTest=false;
  45   }
  46
  47   private  void ReadInput(String filename) {
  48     double vx, vy, vz;
  49     FileInputStream inputFile = new FileInputStream(filename);
  50     nbodies = Integer.parseInt(inputFile.readLine());
  51     ntimesteps = Integer.parseInt(inputFile.readLine());
  52     dtime = Double.parseDouble(inputFile.readLine());
  53     eps = Double.parseDouble(inputFile.readLine());
  54     tol =Double.parseDouble(inputFile.readLine());
  55
  56     dthf = 0.5 * dtime;
  57     epssq = eps * eps;
  58     itolsq = 1.0 / (tol * tol);
  59
  60     if (isFirstRun && !validationTest) {
  61       System.out.println("configuration: " + nbodies + " bodies, " + ntimesteps + " time steps");
  62       System.out.println("");
  63     }
  64
  65     body = new OctTreeLeafNodeData[nbodies];
  66     for (int i = 0; i < nbodies; i++) {
  67       body[i] = new OctTreeLeafNodeData();
  68     }
  69
  70     String line=null;
  71     for (int i = 0; i < nbodies; i++) {
  72       line=inputFile.readLine();
  73       if(line!=null){
  74         StringTokenizer token=new StringTokenizer(line);
  75         body[i].mass = Double.parseDouble(token.nextToken());
  76         body[i].posx = Double.parseDouble(token.nextToken());
  77         body[i].posy = Double.parseDouble(token.nextToken());
  78         body[i].posz = Double.parseDouble(token.nextToken());
  79         vx = Double.parseDouble(token.nextToken());
  80         vy = Double.parseDouble(token.nextToken());
  81         vz = Double.parseDouble(token.nextToken());
  82         body[i].setVelocity(vx, vy, vz);
  83       }
  84
  85     }
  86   }
  87
  88
  89   private  void ComputeCenterAndDiameter() {
  90     double minx, miny, minz;
  91     double maxx, maxy, maxz;
  92     double posx, posy, posz;
  93 //    minx = miny = minz = Double.MAX_VALUE;
  94     minx = miny = minz = 1.7976931348623157E308;
  95 //    maxx = maxy = maxz = Double.MIN_VALUE;
  96     maxx = maxy = maxz = 4.9E-324;
  97     for (int i = 0; i < nbodies; i++) {
  98       posx = body[i].posx;
  99       posy = body[i].posy;
 100       posz = body[i].posz;
 101       if (minx > posx) {
 102         minx = posx;
 103       }
 104       if (miny > posy) {
 105         miny = posy;
 106       }
 107       if (minz > posz) {
 108         minz = posz;
 109       }
 110       if (maxx < posx) {
 111         maxx = posx;
 112       }
 113       if (maxy < posy) {
 114         maxy = posy;
 115       }
 116       if (maxz < posz) {
 117         maxz = posz;
 118       }
 119     }
 120     diameter = maxx - minx;
 121     if (diameter < (maxy - miny)) {
 122       diameter = (maxy - miny);
 123     }
 124     if (diameter < (maxz - minz)) {
 125       diameter = (maxz - minz);
 126     }
 127     centerx = (maxx + minx) * 0.5;
 128     centery = (maxy + miny) * 0.5;
 129     centerz = (maxz + minz) * 0.5;
 130   }
 131
 132
 133 public   void ComputeCenterOfMass(ArrayIndexedGraph octree, ArrayIndexedNode root) { // recursively summarizes info about subtrees
 134     double m, px = 0.0, py = 0.0, pz = 0.0;
 135     OctTreeNodeData n = octree.getNodeData(root);
 136     int j = 0;
 137     n.mass = 0.0;
 138     for (int i = 0; i < 8; i++) {
 139       ArrayIndexedNode child = octree.getNeighbor(root, i);
 140       if (child != null) {
 141         if (i != j) {
 142           octree.removeNeighbor(root, i);
 143           octree.setNeighbor(root, j, child); // move non-null children to the front (needed later to make other code faster)
 144         }
 145         j++;
 146         OctTreeNodeData ch = octree.getNodeData(child);
 147         if (ch instanceof OctTreeLeafNodeData) {
 148           body[curr++] = (OctTreeLeafNodeData) ch; // sort bodies in tree order (approximation of putting nearby nodes together for locality)
 149         } else {
 150           ComputeCenterOfMass(octree, child);
 151         }
 152         m = ch.mass;
 153         n.mass += m;
 154         px += ch.posx * m;
 155         py += ch.posy * m;
 156         pz += ch.posz * m;
 157       }
 158     }
 159     m = 1.0 / n.mass;
 160     n.posx = px * m;
 161     n.posy = py * m;
 162     n.posz = pz * m;
 163   }
 164
 165
 166  public static void Insert(ArrayIndexedGraph octree, ArrayIndexedNode root, OctTreeLeafNodeData b, double r) { // builds the tree
 167     double x = 0.0, y = 0.0, z = 0.0;
 168     OctTreeNodeData n = octree.getNodeData(root);
 169     int i = 0;
 170     if (n.posx < b.posx) {
 171       i = 1;
 172       x = r;
 173     }
 174     if (n.posy < b.posy) {
 175       i += 2;
 176       y = r;
 177     }
 178     if (n.posz < b.posz) {
 179       i += 4;
 180       z = r;
 181     }
 182     ArrayIndexedNode child = octree.getNeighbor(root, i);
 183     if (child == null) {
 184       ArrayIndexedNode newnode = octree.createNode(b);
 185       octree.addNode(newnode);
 186       octree.setNeighbor(root, i, newnode);
 187     } else {
 188       double rh = 0.5 * r;
 189       OctTreeNodeData ch = octree.getNodeData(child);
 190       if (!(ch instanceof OctTreeLeafNodeData)) {
 191         Insert(octree, child, b, rh);
 192       } else {
 193         ArrayIndexedNode newnode = octree.createNode(new OctTreeNodeData(n.posx - rh + x, n.posy - rh + y, n.posz - rh + z));
 194         octree.addNode(newnode);
 195         Insert(octree, newnode, b, rh);
 196         Insert(octree, newnode, (OctTreeLeafNodeData) ch, rh);
 197         octree.setNeighbor(root, i, newnode);
 198       }
 199     }
 200   }
 201
 202
 203   public static void main(String args[]) {
 204     Barneshut bh=new Barneshut();
 205
 206     long runtime, lasttime, mintime, run;
 207
 208     runtime = 0;
 209     lasttime =9223372036854775807L;
 210     mintime =9223372036854775807L;
 211     run = 0;
 212
 213     if (args.length > 1 ) {
 214       bh.validationTest=true;
 215     }
 216
 217 //    while (((run < 3) || (Math.abs(lasttime-runtime)*64 > min(lasttime, runtime))) && (run < 7)) {
 218       runtime = bh.run(args);
 219       if (runtime < mintime) mintime = runtime;
 220       run++;
 221 //    }
 222     if(!bh.validationTest){
 223       System.out.println("minimum runtime: " + mintime + " ms");
 224       System.out.println("");
 225     }
 226   }
 227
 228   public  long run(String args[]) {
 229     if (isFirstRun && !validationTest) {
 230       System.out.println("Lonestar Benchmark Suite v2.1");
 231       System.out.println("Copyright (C) 2007, 2008, 2009 The University of Texas at Austin");
 232       System.out.println("http://iss.ices.utexas.edu/lonestar/");
 233       System.out.println("");
 234       System.out.println("application: BarnesHut (serial version)");
 235       System.out.println("Simulation of the gravitational forces in a galactic");
 236       System.out.println("cluster using the Barnes-Hut n-body algorithm");
 237       System.out.println("http://iss.ices.utexas.edu/lonestar/barneshut.html");
 238       System.out.println("");
 239     }
 240     if (args.length ==0 ) {
 241       System.out.println("arguments: input_file_name");
 242       System.exit(-1);
 243     }
 244     long fstart_time = System.currentTimeMillis();
 245     ReadInput(args[0]);
 246     long fend_time = System.currentTimeMillis();
 247     if(!validationTest){
 248       System.out.println("file reading time="+(fend_time-fstart_time));
 249     }
 250     long runtime = 0;
 251     int local_nbodies=nbodies;
 252     int local_ntimesteps=ntimesteps;
 253
 254     long start_time = System.currentTimeMillis();
 255     for (int step = 0; step < local_ntimesteps; step++) { // time-step the system
 256       ComputeCenterAndDiameter();
 257       ArrayIndexedGraph octree = new ArrayIndexedGraph(8);
 258       ArrayIndexedNode root = octree.createNode(new OctTreeNodeData(centerx, centery, centerz)); // create the tree's root
 259       octree.addNode(root);
 260       double radius = diameter * 0.5;
 261
 262       for (int i = 0; i < local_nbodies; i++) {
 263         Insert(octree, root, body[i], radius); // grow the tree by inserting each body
 264         body[i].root=root;
 265       }
 266       curr = 0;
 267       // summarize subtree info in each internal node (plus restructure tree and sort bodies for performance reasons)
 268       ComputeCenterOfMass(octree, root);
 269
 270       sese force {
 271         for(int i=0; i < local_nbodies; i++){
 272           // compute the acceleration of each body (consumes most of the total runtime)
 273           // n.ComputeForce(octree, root, diameter, itolsq, step, dthf, epssq);
 274           OctTreeLeafNodeData eachbody=body[i];
 275           double di=diameter;
 276           double it=itolsq;
 277           double dt=dthf;
 278           double ep=epssq;
 279           sese parallel{
 280             eachbody.ComputeForce(octree, di, it, step, dt, ep);
 281           }
 282         }
 283       }
 284
 285       for (int i = 0; i < local_nbodies; i++) {
 286         body[i].Advance(dthf, dtime); // advance the position and velocity of each body
 287       }
 288
 289     } // end of time step
 290
 291     long end_time=System.currentTimeMillis();
 292
 293     if (isFirstRun) {
 294         if(validationTest){
 295           for (int i = 0; i < local_nbodies; i++) {
 296             System.out.println(body[i].posx + " " + body[i].posy + " " + body[i].posz); // print result
 297           }
 298           System.out.println("");
 299         }
 300     }
 301     runtime += (end_time-start_time);
 302     if(!validationTest){
 303       System.out.println("runtime: " + runtime + " ms");
 304     }
 305
 306     isFirstRun = false;
 307     return runtime;
 308   }
 309
 310
 311   public static long min(long a, long b) {
 312     if(a == b)
 313       return a;
 314     if(a > b) {
 315       return b;
 316     } else {
 317       return a;
 318     }
 319   }
 320
 321 }