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.gc();
  48     }
  49
  50     System.out.println("minimum runtime: " + mintime + " ms");
  51     System.out.println("");
  52   }
  53
  54
  55   public long run(String args[]) {
  56     if (isFirstRun) {
  57       System.out.println();
  58       System.out.println("Lonestar Benchmark Suite v2.1");
  59       System.out.println("Copyright (C) 2007, 2008, 2009 The University of Texas at Austin");
  60       System.out.println("http://iss.ices.utexas.edu/lonestar/");
  61       System.out.println();
  62       System.out.println("application: Delaunay Mesh Refinement (serial version)");
  63       System.out.println("Refines a Delaunay triangulation mesh such that no angle");
  64       System.out.println("in the mesh is less than 30 degrees");
  65       System.out.println("http://iss.ices.utexas.edu/lonestar/delaunayrefinement.html");
  66       System.out.println();
  67     }
  68     if (args.length < 1) {
  69       System.out.println("Arguments: <input file> [verify]");
  70       System.exit(-1);
  71     }
  72
  73     EdgeGraph mesh = new UndirectedEdgeGraph();
  74
  75     Mesh m = new Mesh();
  76     m.read(mesh, args[0]);
  77
  78     //treat LinkedList as a stack
  79     Stack worklist = new Stack();
  80     //    LinkedList worklist = new LinkedList();
  81
  82     // worklist.addAll(Mesh.getBad(mesh));
  83     HashMapIterator it = m.getBad(mesh).iterator();
  84     while (it.hasNext()) {
  85       worklist.push(it.next());
  86     }
  87
  88     if (isFirstRun) {
  89       System.out.println("configuration: " + mesh.getNumNodes() + " total triangles, " + worklist.size() + " bad triangles");
  90       System.out.println();
  91     }
  92
  93     System.gc();
  94
  95 //    long id = Time.getNewTimeId();
  96     long startTime = System.currentTimeMillis();
  97     while (!worklist.isEmpty()) {
  98
  99       Node[] bad_elements = new Node[23];
 100       for(int i=0;i<23;i++) {
 101         if(worklist.isEmpty()) {
 102           bad_elements[i] = null;
 103         } else {
 104           bad_elements[i] = (Node) worklist.pop();
 105         }
 106       }
 107
 108   //      Node bad_element = (Node) worklist.pop();
 109       for(int i=0;i<23;i++) {
 110         Node bad_element = bad_elements[i];
 111         if (bad_element != null && mesh.containsNode(bad_element)) {
 112
 113           sese P {
 114           //takes < 1 sec
 115           Cavity cavity = new Cavity(mesh);
 116
 117           //Appears to only call getters (only possible conflict is inherent in Hashmap)
 118           cavity.initialize(bad_element);
 119
 120           //Takes up 15% of computation
 121           //Problem:: Build is recursive upon building neighbor upon neighbor upon neighbor
 122           //This is could be a problem....
 123           //TODO check dimensions problem
 124           cavity.build();
 125
 126           //Takes up a whooping 50% of computation time and changes NOTHING but cavity :D
 127           cavity.update();
 128           }
 129
 130           sese S {
 131             //28% of runtime #Removes stuff out of our mesh
 132             middle(mesh, cavity);
 133
 134             //1.5% of runtime # adds stuff back to the work queue.
 135             end(mesh, worklist, bad_element, cavity);
 136           }
 137         }
 138
 139       }
 140     }
 141     long time = System.currentTimeMillis() - startTime;
 142     System.out.println("runtime: " + time + " ms");
 143     //TODO note how we only verify on first run...
 144     if (isFirstRun && args.length > 1) {
 145       verify(mesh);
 146     }
 147     isFirstRun = false;
 148     return time;
 149   }
 150
 151   private void end(EdgeGraph mesh, Stack worklist, Node bad_element, Cavity cavity) {
 152     HashMapIterator it2 = cavity.getPost().newBad(mesh).iterator();
 153     while (it2.hasNext()) {
 154       worklist.push((Node)it2.next());
 155     }
 156
 157     if (mesh.containsNode(bad_element)) {
 158       worklist.push((Node) bad_element);
 159     }
 160   }
 161
 162   private void middle(EdgeGraph mesh, Cavity cavity) {
 163     //remove old data
 164     Node node;
 165
 166     //Takes up 8.9% of runtime
 167     for (Iterator iterator = cavity.getPre().getNodes().iterator(); iterator.hasNext();) {
 168       node = (Node) iterator.next();
 169       mesh.removeNode(node);
 170     }
 171
 172     //add new data
 173     //Takes up 1.7% of runtime
 174     for (Iterator iterator1 = cavity.getPost().getNodes().iterator(); iterator1.hasNext();) {
 175       node = (Node) iterator1.next();
 176       mesh.addNode(node);
 177     }
 178
 179
 180     //Takes up 7.8% of runtime
 181     Edge_d edge;
 182     for (Iterator iterator2 = cavity.getPost().getEdges().iterator(); iterator2.hasNext();) {
 183       edge = (Edge_d) iterator2.next();
 184       mesh.addEdge(edge);
 185     }
 186   }
 187
 188   public void verify(EdgeGraph result) {
 189     //Put in cuz of static issues.
 190     Mesh m = new Mesh();
 191     if (!m.verify(result)) {
 192 //      throw new IllegalStateException("refinement failed.");
 193       System.out.println("Refinement Failed.");
 194       System.exit(-1);
 195     }
 196
 197     int size = m.getBad(result).size();
 198     if (size != 0) {
 199       System.out.println("refinement failed\nstill have "+size+" bad triangles left.\n");
 200       System.exit(-1);
 201     } else {
 202       System.out.println("OK");
 203       return;
 204     }
 205   }
 206 }