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
  43     for (long run = 0; ((run < 3) || Math.abs(lasttime - runtime) * 64 > Math.min(lasttime, runtime)) && run < 7; run++) {
  44       runtime = run(args);
  45       if (runtime < mintime) {
  46         mintime = runtime;
  47       }
  48       System.out.println( "Post-run garbage collection started..." );
  49       System.gc();
  50       System.out.println( "done gc" );
  51     }
  52
  53     System.out.println("minimum runtime: " + mintime + " ms");
  54     System.out.println("");
  55   }
  56
  57
  58   public long run(String args[]) {
  59     if (isFirstRun) {
  60       System.out.println();
  61       System.out.println("Lonestar Benchmark Suite v2.1");
  62       System.out.println("Copyright (C) 2007, 2008, 2009 The University of Texas at Austin");
  63       System.out.println("http://iss.ices.utexas.edu/lonestar/");
  64       System.out.println();
  65       System.out.println("application: Delaunay Mesh Refinement (serial version)");
  66       System.out.println("Refines a Delaunay triangulation mesh such that no angle");
  67       System.out.println("in the mesh is less than 30 degrees");
  68       System.out.println("http://iss.ices.utexas.edu/lonestar/delaunayrefinement.html");
  69       System.out.println();
  70     }
  71     if (args.length < 2) {
  72       System.out.println("Arguments: <input file> <num workers> [verify]");
  73       System.exit(-1);
  74     }
  75
  76     EdgeGraph mesh = new UndirectedEdgeGraph();
  77
  78     Mesh m = new Mesh();
  79     m.read(mesh, args[0]);
  80
  81     int numWorkers = Integer.parseInt( args[1] );
  82
  83     Stack worklist = new Stack();
  84
  85     // REPLACE worklist.addAll(Mesh.getBad(mesh)); WITH...
  86     HashMapIterator it = m.getBad(mesh).iterator();
  87     while (it.hasNext()) {
  88       worklist.push(it.next());
  89     }
  90
  91     if (isFirstRun) {
  92       System.out.println("configuration: " +
  93                          mesh.getNumNodes() + " total triangles, " +
  94                          worklist.size() + " bad triangles");
  95       System.out.println();
  96     }
  97
  98     System.out.println( "Post-config garbage collection started..." );
  99     System.gc();
 100     System.out.println( "done gc" );
 101
 102
 103     Node  [] nodesForBadTris = new Node  [numWorkers];
 104     Cavity[] cavities        = new Cavity[numWorkers];
 105     Cavity lastAppliedCavity = null;
 106
 107
 108     int zzz = 0;
 109
 110
 111     long startTime = System.currentTimeMillis();
 112     while (!worklist.isEmpty()) {
 113
 114       // Phase 1, grab enough work from list for
 115       // each worker in the parent
 116       for(int i=0;i<numWorkers;i++) {
 117         if(worklist.isEmpty()) {
 118           nodesForBadTris[i] = null;
 119         } else {
 120           nodesForBadTris[i] = (Node) worklist.pop();
 121         }
 122       }
 123
 124       // Phase 2, read mesh and compute cavities in parallel
 125       for(int i=0;i<numWorkers;i++) {
 126
 127         Node nodeForBadTri = nodesForBadTris[i];
 128
 129         if (nodeForBadTri != null &&
 130             nodeForBadTri.inGraph
 131             ) {
 132
 133           //System.out.println( "computing a cavity for tri "+
 134           //                    mesh.getNodeData( nodeForBadTri )+"..." );
 135
 136           sese computeCavity {
 137             //takes < 1 sec
 138             Cavity cavity = new Cavity(mesh);
 139
 140             //Appears to only call getters (only possible conflict is inherent in Hashmap)
 141             cavity.initialize(nodeForBadTri);
 142
 143             //Takes up 15% of computation
 144             //Problem:: Build is recursive upon building neighbor upon neighbor upon neighbor
 145             //This is could be a problem....
 146             //TODO check dimensions problem
 147             cavity.build();
 148
 149             //Takes up a whooping 50% of computation time and changes NOTHING but cavity :D
 150             cavity.update();
 151
 152
 153             /*
 154             LinkedList nodes  = cavity.getPre().getNodes();
 155             LinkedList border = cavity.getPre().getBorder();
 156             LinkedList edges  = cavity.getPre().getEdges();
 157
 158             String s = "nodes:  \n";
 159
 160             for( Iterator iter = nodes.iterator(); iter.hasNext(); ) {
 161               Node    node = (Node) iter.next();
 162               Element element = (Element) mesh.getNodeData(node);
 163               s += "  "+element+"\n";
 164             }
 165
 166             s += "\nborder: \n";
 167
 168             for( Iterator iter = border.iterator(); iter.hasNext(); ) {
 169               Node    node = (Node) iter.next();
 170               Element element = (Element) mesh.getNodeData(node);
 171               s += "  "+element+"\n";
 172             }
 173
 174             s += "\nedges:  \n";
 175
 176             for( Iterator iter = edges.iterator(); iter.hasNext(); ) {
 177               Edge_d  edge    = (Edge_d)  iter.next();
 178               Element element = (Element) mesh.getEdgeData(edge);
 179               s += "  "+element+"\n";
 180             }
 181
 182             System.out.println( "Pre:\n"+s );
 183             */
 184
 185           }
 186
 187           sese storeCavity {
 188             cavities[i] = cavity;
 189           }
 190
 191         } else {
 192           sese storeNoCavity {
 193             cavities[i] = null;
 194           }
 195         }
 196       }
 197
 198       // Phase 3, apply cavities to mesh, if still applicable
 199       // this phase can proceed in parallel when a cavity's
 200       // start nodes are still present
 201       for(int i=0;i<numWorkers;i++) {
 202
 203         Cavity  cavity        = cavities[i];
 204         boolean appliedCavity = false;
 205         Node    nodeForBadTri = nodesForBadTris[i];
 206
 207         sese applyCavity {
 208
 209           // go ahead with applying cavity when all of its
 210           // pre-nodes are still in
 211           if( cavity != null &&
 212               cavity.getPre().allNodesAndBorderStillInCompleteGraph() ) {
 213
 214             appliedCavity     = true;
 215             lastAppliedCavity = cavity;
 216
 217
 218             //boolean printChange = true; //(zzz % 10 == 0);
 219
 220
 221             //remove old data
 222             Node node;
 223             //if( printChange ) {
 224             //  System.out.println( "\n\n\nbad tri: "+mesh.getNodeData( nodeForBadTri ) );
 225             //  System.out.println( "\npre nodes: " );
 226             //}
 227             //Takes up 8.9% of runtime
 228             for (Iterator iterator = cavity.getPre().getNodes().iterator();
 229                  iterator.hasNext();) {
 230
 231               node = (Node) iterator.next();
 232               //if( printChange ) {
 233               //  System.out.println( "  "+mesh.getNodeData( node ) );
 234               //}
 235               mesh.removeNode(node);
 236             }
 237
 238             //add new data
 239             //if( printChange ) {
 240             //  System.out.println( "post nodes: " );
 241             //}
 242             //Takes up 1.7% of runtime
 243             for (Iterator iterator1 = cavity.getPost().getNodes().iterator();
 244                  iterator1.hasNext();) {
 245
 246               node = (Node) iterator1.next();
 247               //if( printChange ) {
 248               //  System.out.println( "  "+mesh.getNodeData( node ) );
 249               //}
 250               mesh.addNode(node);
 251             }
 252
 253             //if( printChange ) {
 254             //  System.out.println( "post edges: " );
 255             //}
 256             //Takes up 7.8% of runtime
 257             Edge_d edge;
 258             for (Iterator iterator2 = cavity.getPost().getEdges().iterator();
 259                  iterator2.hasNext();) {
 260
 261               edge = (Edge_d) iterator2.next();
 262               //if( printChange ) {
 263               //  System.out.println( "  "+mesh.getEdgeData( edge ) );
 264               //}
 265               mesh.addEdge(edge);
 266             }
 267
 268
 269
 270             for (Iterator iterator1 = cavity.getPost().getNodes().iterator();
 271                  iterator1.hasNext();) {
 272               node = (Node) iterator1.next();
 273
 274               Element e = (Element)mesh.getNodeData( node );
 275
 276               int cntOutNeighbors = 0;
 277               for (Iterator iterator = mesh.getOutNeighbors(node); iterator.hasNext();) {
 278                 ++cntOutNeighbors;
 279                 Node neighbor = (Node) iterator.next();
 280               }
 281
 282               int dim = e.getDim();
 283               int out = cntOutNeighbors;
 284
 285               if( dim == 3 && out < 3 ) {
 286                 System.out.println( e+" has dim="+dim+" and num out-neighbors in graph="+out );
 287               }
 288             }
 289
 290           }
 291         }
 292
 293
 294         sese scheduleMoreBad {
 295
 296           if( appliedCavity ) {
 297             // we did apply the cavity, and we may
 298             // have introduced new bad triangles
 299             HashMapIterator it2 = cavity.getPost().newBad(mesh).iterator();
 300             while (it2.hasNext()) {
 301               worklist.push((Node)it2.next());
 302             }
 303           }
 304
 305           // the logic of having this out here seems wacky, and overconservative,
 306           // but it matches the original algorithm and it works...
 307           if( nodeForBadTri != null && mesh.containsNode( nodeForBadTri ) ) {
 308             worklist.push( nodeForBadTri );
 309           }
 310
 311           /*
 312           if( !appliedCavity ) {
 313
 314             // if we couldn't even apply this cavity, just
 315             // throw it back on the worklist
 316             if( nodeForBadTri != null && nodeForBadTri.inGraph ) {
 317               worklist.push( nodeForBadTri );
 318             } else {
 319               System.out.println( "\n\n\nthis tri no longer a concern: "+
 320                                   mesh.getNodeData( nodeForBadTri ) );
 321             }
 322
 323           } else {
 324             // otherwise we did apply the cavity,
 325             // and we may have introduced new bad triangles
 326             HashMapIterator it2 = cavity.getPost().newBad(mesh).iterator();
 327             while (it2.hasNext()) {
 328               worklist.push((Node)it2.next());
 329             }
 330           }
 331           */
 332
 333         } // end scheduleMoreBad
 334       } // end phase 3
 335
 336       //++zzz;
 337       //Node aNode = (Node)lastAppliedCavity.getPost().getNodes().iterator().next();
 338       //mesh.discoverAllNodes( aNode );
 339       //System.out.println( "\n\ntris="+mesh.getNumNodes()+
 340       //                    " [wl="+worklist.size()+"]");
 341       //if( zzz == 10 ) { System.exit( 0 ); }
 342
 343     } // end while( !worklist.isEmpty() )
 344
 345     long time = System.currentTimeMillis() - startTime;
 346     System.out.println("runtime: " + time + " ms");
 347     //TODO note how we only verify on first run...
 348     //TODO verify is outside timing, do it each time
 349     // since we MIGHT compute something different when
 350     // we have a bug
 351     if (//isFirstRun &&
 352         args.length > 2) {
 353
 354       Node aNode = (Node)lastAppliedCavity.getPost().getNodes().iterator().next();
 355       mesh.discoverAllNodes( aNode );
 356
 357       verify(mesh);
 358     }
 359     isFirstRun = false;
 360     return time;
 361   }
 362
 363
 364   public void verify(EdgeGraph result) {
 365     //Put in cuz of static issues.
 366     Mesh m = new Mesh();
 367     if (!m.verify(result)) {
 368 //      throw new IllegalStateException("refinement failed.");
 369       System.out.println("Refinement Failed.");
 370       System.exit(-1);
 371     }
 372
 373     int size = m.getBad(result).size();
 374     if (size != 0) {
 375       System.out.println("refinement failed\nstill have "+size+" bad triangles left.\n");
 376       System.exit(-1);
 377     } else {
 378       System.out.println("OK");
 379       return;
 380     }
 381   }
 382 }