Robust/src/Benchmarks/oooJava/DelaunayRefinement/SerialDelaunayRefinement.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: UndirectedEdgeGraph.java
  23
  24 */
  25
  26 public class SerialDelaunayRefinement {
  27   public boolean isFirstRun;
  28   public SerialDelaunayRefinement() {
  29     isFirstRun = true;
  30   }
  31
  32   public static void main(String args[]) {
  33     SerialDelaunayRefinement sdr = new SerialDelaunayRefinement();
  34     sdr.runMain(args);
  35   }
  36
  37   public void runMain(String args[]) {
  38     long runtime = 0;
  39     //Numbers below are Long.Max_Value
  40     long lasttime = 0x7fffffffffffffffL;
  41     long mintime = 0x7fffffffffffffffL;
  42     for (long run = 0; ((run < 3) || Math.abs(lasttime - runtime) * 64 > Math.min(lasttime, runtime)) && run < 7; run++) {
  43       runtime = run(args);
  44       if (runtime < mintime) {
  45         mintime = runtime;
  46       }
  47       System.out.println( "Post-run garbage collection started..." );
  48       System.gc();
  49       System.out.println( "done gc" );
  50     }
  51
  52     System.out.println("minimum runtime: " + mintime + " ms");
  53     System.out.println("");
  54   }
  55
  56
  57   public long run(String args[]) {
  58     if (isFirstRun) {
  59       System.out.println();
  60       System.out.println("Lonestar Benchmark Suite v2.1");
  61       System.out.println("Copyright (C) 2007, 2008, 2009 The University of Texas at Austin");
  62       System.out.println("http://iss.ices.utexas.edu/lonestar/");
  63       System.out.println();
  64       System.out.println("application: Delaunay Mesh Refinement (serial version)");
  65       System.out.println("Refines a Delaunay triangulation mesh such that no angle");
  66       System.out.println("in the mesh is less than 30 degrees");
  67       System.out.println("http://iss.ices.utexas.edu/lonestar/delaunayrefinement.html");
  68       System.out.println();
  69     }
  70     if (args.length < 2) {
  71       System.out.println("Arguments: <input file> <num workers> [verify]");
  72       System.exit(-1);
  73     }
  74
  75     EdgeGraph mesh = new UndirectedEdgeGraph();
  76
  77     Mesh m = new Mesh();
  78     m.read(mesh, args[0]);
  79
  80     int numWorkers = Integer.parseInt( args[1] );
  81
  82     Stack worklist = new Stack();
  83
  84     // REPLACE worklist.addAll(Mesh.getBad(mesh)); WITH...
  85     HashMapIterator it = m.getBad(mesh).iterator();
  86     while (it.hasNext()) {
  87       worklist.push(it.next());
  88     }
  89
  90     if (isFirstRun) {
  91       System.out.println("configuration: " +
  92                          mesh.getNumNodes() + " total triangles, " +
  93                          worklist.size() + " bad triangles");
  94       System.out.println();
  95     }
  96
  97     System.out.println( "Post-config garbage collection started..." );
  98     System.gc();
  99     System.out.println( "done gc" );
 100
 101
 102     Node  [] nodesForBadTris = new Node  [numWorkers];
 103     Cavity[] cavities        = new Cavity[numWorkers];
 104     Cavity lastAppliedCavity = null;
 105
 106
 107     long startTime = System.currentTimeMillis();
 108     while (!worklist.isEmpty()) {
 109
 110       // Phase 1, grab enough work from list for
 111       // each worker in the parent
 112       for(int i=0;i<numWorkers;i++) {
 113         if(worklist.isEmpty()) {
 114           nodesForBadTris[i] = null;
 115         } else {
 116           nodesForBadTris[i] = (Node) worklist.pop();
 117         }
 118       }
 119
 120       // Phase 2, read mesh and compute cavities in parallel
 121       for(int i=0;i<numWorkers;i++) {
 122
 123         Node nodeForBadTri = nodesForBadTris[i];
 124
 125         if (nodeForBadTri != null &&
 126             nodeForBadTri.inGraph
 127             ) {
 128
 129           System.out.println( "computing a cavity..." );
 130
 131           sese computeCavity {
 132             //takes < 1 sec
 133             Cavity cavity = new Cavity(mesh);
 134
 135             //Appears to only call getters (only possible conflict is inherent in Hashmap)
 136             cavity.initialize(nodeForBadTri);
 137
 138             //Takes up 15% of computation
 139             //Problem:: Build is recursive upon building neighbor upon neighbor upon neighbor
 140             //This is could be a problem....
 141             //TODO check dimensions problem
 142             cavity.build();
 143
 144             //Takes up a whooping 50% of computation time and changes NOTHING but cavity :D
 145             cavity.update();
 146           }
 147
 148           sese storeCavity {
 149             cavities[i] = cavity;
 150           }
 151
 152         } else {
 153           sese storeNoCavity {
 154             cavities[i] = null;
 155           }
 156         }
 157       }
 158
 159       // Phase 3, apply cavities to mesh, if still applicable
 160       // this phase can proceed in parallel when a cavity's
 161       // start nodes are still present
 162       for(int i=0;i<numWorkers;i++) {
 163
 164         Cavity  cavity        = cavities[i];
 165         boolean appliedCavity = false;
 166         Node    nodeForBadTri = nodesForBadTris[i];
 167
 168         sese applyCavity {
 169
 170           // go ahead with applying cavity when all of its
 171           // pre-nodes are still in
 172           if( cavity != null &&
 173               cavity.getPre().allNodesStillInCompleteGraph() ) {
 174
 175             appliedCavity     = true;
 176             lastAppliedCavity = cavity;
 177
 178             //remove old data
 179             Node node;
 180
 181             //Takes up 8.9% of runtime
 182             for (Iterator iterator = cavity.getPre().getNodes().iterator();
 183                  iterator.hasNext();) {
 184
 185               node = (Node) iterator.next();
 186               mesh.removeNode(node);
 187             }
 188
 189             //add new data
 190             //Takes up 1.7% of runtime
 191             for (Iterator iterator1 = cavity.getPost().getNodes().iterator();
 192                  iterator1.hasNext();) {
 193
 194               node = (Node) iterator1.next();
 195               mesh.addNode(node);
 196             }
 197
 198             //Takes up 7.8% of runtime
 199             Edge_d edge;
 200             for (Iterator iterator2 = cavity.getPost().getEdges().iterator();
 201                  iterator2.hasNext();) {
 202
 203               edge = (Edge_d) iterator2.next();
 204               mesh.addEdge(edge);
 205             }
 206           }
 207         }
 208
 209
 210         sese scheduleMoreBad {
 211
 212           if( !appliedCavity ) {
 213
 214             // if we couldn't even apply this cavity, just
 215             // throw it back on the worklist
 216             if( nodeForBadTri != null && nodeForBadTri.inGraph ) {
 217               worklist.push( nodeForBadTri );
 218             }
 219
 220           } else {
 221             // otherwise we did apply the cavity, so repair the all-nodes set of the mesh
 222             //Iterator itrPreNodes = cavity.getPre().getNodes().iterator();
 223             //while( itrPreNodes.hasNext() ) {
 224             //  System.out.println( "yere" );
 225             //  mesh.removeNodeFromAllNodesSet( (Node)itrPreNodes.next() );
 226             //  System.out.println( "yeres" );
 227             //}
 228             //Iterator itrPostNodes = cavity.getPost().getNodes().iterator();
 229             //while( itrPostNodes.hasNext() ) {
 230             //  mesh.addNodeToAllNodesSet( (Node)itrPostNodes.next() );
 231             //}
 232
 233             // and we may have introduced new bad triangles
 234             HashMapIterator it2 = cavity.getPost().newBad(mesh).iterator();
 235             while (it2.hasNext()) {
 236               worklist.push((Node)it2.next());
 237             }
 238           }
 239         } // end scheduleMoreBad
 240       } // end phase 3
 241
 242     } // end while( !worklist.isEmpty() )
 243
 244     long time = System.currentTimeMillis() - startTime;
 245     System.out.println("runtime: " + time + " ms");
 246     //TODO note how we only verify on first run...
 247     //TODO verify is outside timing, do it each time
 248     // since we MIGHT compute something different when
 249     // we have a bug
 250     if (//isFirstRun &&
 251         args.length > 2) {
 252
 253       Node aNode = (Node)lastAppliedCavity.getPost().getNodes().iterator().next();
 254       mesh.discoverAllNodes( aNode );
 255
 256       verify(mesh);
 257     }
 258     isFirstRun = false;
 259     return time;
 260   }
 261
 262
 263   public void verify(EdgeGraph result) {
 264     //Put in cuz of static issues.
 265     Mesh m = new Mesh();
 266     if (!m.verify(result)) {
 267 //      throw new IllegalStateException("refinement failed.");
 268       System.out.println("Refinement Failed.");
 269       System.exit(-1);
 270     }
 271
 272     int size = m.getBad(result).size();
 273     if (size != 0) {
 274       System.out.println("refinement failed\nstill have "+size+" bad triangles left.\n");
 275       System.exit(-1);
 276     } else {
 277       System.out.println("OK");
 278       return;
 279     }
 280   }
 281 }