Robust/src/Benchmarks/SingleTM/Labyrinth3D/Router.java

   1 /* =============================================================================
   2  *
   3  * Router.java
   4  *
   5  * =============================================================================
   6  *
   7  * Copyright (C) Stanford University, 2006.  All Rights Reserved.
   8  * Author: Chi Cao Minh
   9  *
  10  * Ported to Java
  11  * Author: Jihoon Lee
  12  * University of California, Irvine
  13  *
  14  * =============================================================================
  15  *
  16  * For the license of bayes/sort.h and bayes/sort.c, please see the header
  17  * of the files.
  18  *
  19  * ------------------------------------------------------------------------
  20  *
  21  * For the license of kmeans, please see kmeans/LICENSE.kmeans
  22  *
  23  * ------------------------------------------------------------------------
  24  *
  25  * For the license of ssca2, please see ssca2/COPYRIGHT
  26  *
  27  * ------------------------------------------------------------------------
  28  *
  29  * For the license of lib/mt19937ar.c and lib/mt19937ar.h, please see the
  30  * header of the files.
  31  *
  32  * ------------------------------------------------------------------------
  33  *
  34  * For the license of lib/rbtree.h and lib/rbtree.c, please see
  35  * lib/LEGALNOTICE.rbtree and lib/LICENSE.rbtree
  36  *
  37  * ------------------------------------------------------------------------
  38  *
  39  * Unless otherwise noted, the following license applies to STAMP files:
  40  *
  41  * Copyright (c) 2007, Stanford University
  42  * All rights reserved.
  43  *
  44  * Redistribution and use in source and binary forms, with or without
  45  * modification, are permitted provided that the following conditions are
  46  * met:
  47  *
  48  *     * Redistributions of source code must retain the above copyright
  49  *       notice, this list of conditions and the following disclaimer.
  50  *
  51  *     * Redistributions in binary form must reproduce the above copyright
  52  *       notice, this list of conditions and the following disclaimer in
  53  *       the documentation and/or other materials provided with the
  54  *       distribution.
  55  *
  56  *     * Neither the name of Stanford University nor the names of its
  57  *       contributors may be used to endorse or promote products derived
  58  *       from this software without specific prior written permission.
  59  *
  60  * THIS SOFTWARE IS PROVIDED BY STANFORD UNIVERSITY ``AS IS'' AND ANY
  61  * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  62  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
  63  * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL STANFORD UNIVERSITY BE LIABLE
  64  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
  65  * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
  66  * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
  67  * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
  68  * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
  69  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF
  70  * THE POSSIBILITY OF SUCH DAMAGE.
  71  *
  72  * =============================================================================
  73  */
  74
  75 #define MOMENTUM_ZERO 0
  76 #define MOMENTUM_POSX 1
  77 #define MOMENTUM_POSY 2
  78 #define MOMENTUM_POSZ 3
  79 #define MOMENTUM_NEGX 4
  80 #define MOMENTUM_NEGY 5
  81 #define MOMENTUM_NEGZ 6
  82 #define GRID_POINT_FULL -2
  83 #define GRID_POINT_EMPTY -1
  84
  85 public class Router {
  86     public int xCost;
  87     public int yCost;
  88     public int zCost;
  89     public int bendCost;
  90     public static Point MOVE_POSX;
  91     public static Point MOVE_POSY;
  92     public static Point MOVE_POSZ;
  93     public static Point MOVE_NEGX;
  94     public static Point MOVE_NEGY;
  95     public static Point MOVE_NEGZ;
  96
  97     public Router() {}
  98
  99 /* =============================================================================
 100  * router_alloc
 101  * =============================================================================
 102  * router_t* router_alloc (long xCost, long yCost, long zCost, long bendCost);
 103  */
 104   public static Router alloc(int xCost,int yCost,int zCost,int bendCost) {
 105     Router routerPtr = new Router();
 106
 107
 108     routerPtr.MOVE_POSX = new Point(1,0,0,0,MOMENTUM_POSX);
 109     routerPtr.MOVE_POSY = new Point(0,1,0,0,MOMENTUM_POSY);
 110     routerPtr.MOVE_POSZ = new Point(0,0,1,0,MOMENTUM_POSZ);
 111     routerPtr.MOVE_NEGX = new Point(-1,0,0,0,MOMENTUM_NEGX);
 112     routerPtr.MOVE_NEGY = new Point(0,-1,0,0,MOMENTUM_NEGY);
 113     routerPtr.MOVE_NEGZ = new Point(0,0,-1,0,MOMENTUM_NEGZ);
 114
 115     if(routerPtr != null) {
 116       routerPtr.xCost = xCost;
 117       routerPtr.yCost = yCost;
 118       routerPtr.zCost = zCost;
 119       routerPtr.bendCost = bendCost;
 120     }
 121
 122     return routerPtr;
 123   }
 124
 125
 126 /* ============================================================================
 127  * PexpandToneighbor
 128  * ============================================================================
 129  */
 130   private void PexpandToNeighbor(Grid myGridPtr,
 131                                  int x,int y,int z, int value,Queue_Int queuePtr) {
 132     if (myGridPtr.isPointValid(x,y,z)) {
 133       int neighborValue = myGridPtr.points_unaligned[x][y][z];
 134       if (neighborValue == GRID_POINT_EMPTY) {
 135         int neighborGridPointIndex = myGridPtr.getPointIndex(x,y,z);
 136         myGridPtr.points_unaligned[x][y][z] = value;
 137         queuePtr.queue_push(neighborGridPointIndex);
 138       } else if (neighborValue != GRID_POINT_FULL) {
 139         if (value < neighborValue) {
 140           int neighborGridPointIndex = myGridPtr.getPointIndex(x,y,z);
 141           myGridPtr.points_unaligned[x][y][z] = value;
 142           queuePtr.queue_push(neighborGridPointIndex);
 143         }
 144       }
 145     }
 146   }
 147
 148
 149 /* ============================================================================
 150  * PdoExpansion
 151  * ============================================================================
 152  */
 153     public boolean PdoExpansion (Router routerPtr,Grid myGridPtr,Queue_Int queuePtr,
 154                                   Coordinate srcPtr,Coordinate dstPtr) {
 155         int xCost = routerPtr.xCost;
 156         int yCost = routerPtr.yCost;
 157         int zCost = routerPtr.zCost;
 158
 159         /*
 160          * Potential Optimization: Make 'src' the one closet to edge.
 161          * This will likely decrease the area of the emitted wave.
 162          */
 163
 164         queuePtr.queue_clear();
 165
 166         int srcGridPointIndex = myGridPtr.getPointIndex(srcPtr.x,srcPtr.y,srcPtr.z);
 167
 168         queuePtr.queue_push(srcGridPointIndex);
 169
 170         myGridPtr.setPoint(srcPtr.x,srcPtr.y,srcPtr.z,0);
 171         myGridPtr.setPoint(dstPtr.x,dstPtr.y,dstPtr.z,GRID_POINT_EMPTY);
 172         int dstGridPointIndex = myGridPtr.getPointIndex(dstPtr.x,dstPtr.y,dstPtr.z);
 173         boolean isPathFound = false;
 174         int height = myGridPtr.height;
 175         int width = myGridPtr.width;
 176         int area = height * width;
 177         while (!queuePtr.queue_isEmpty()) {
 178             int gridPointIndex = queuePtr.queue_pop();
 179
 180             if(gridPointIndex == dstGridPointIndex) {
 181               isPathFound = true;
 182               break;
 183             }
 184
 185             int z = gridPointIndex / area;
 186             int index2d = gridPointIndex % area;
 187             int y = index2d / width;
 188             int x = index2d % width;
 189             int value = myGridPtr.points_unaligned[x][y][z];
 190
 191             /*
 192              * Check 6 neighbors
 193              *
 194              * Potential Optimization: Only need to check 5 of these
 195              */
 196             PexpandToNeighbor(myGridPtr, x+1, y,   z,   (value + xCost), queuePtr);
 197             PexpandToNeighbor(myGridPtr, x-1, y,   z,   (value + xCost), queuePtr);
 198             PexpandToNeighbor(myGridPtr, x, y+1,   z,   (value + yCost), queuePtr);
 199             PexpandToNeighbor(myGridPtr, x, y-1,   z,   (value + yCost), queuePtr);
 200             PexpandToNeighbor(myGridPtr, x, y,   z+1,   (value + zCost), queuePtr);
 201             PexpandToNeighbor(myGridPtr, x, y,   z-1,   (value + zCost), queuePtr);
 202
 203         } /* iterate over work queue */
 204
 205         return isPathFound;
 206     }
 207
 208
 209 /* ============================================================================
 210  * traceToNeighbor
 211  * ============================================================================
 212  */
 213     private void traceToNeighbor(Grid myGridPtr,
 214                                  Point currPtr,
 215                                  Point movePtr,
 216                                  boolean useMomentum,
 217                                  int bendCost,
 218                                  Point nextPtr)
 219     {
 220       int x = currPtr.x + movePtr.x;
 221       int y = currPtr.y + movePtr.y;
 222       int z = currPtr.z + movePtr.z;
 223
 224         if (myGridPtr.isPointValid(x,y,z) &&
 225                 !myGridPtr.isPointEmpty(x,y,z) &&
 226                 !myGridPtr.isPointFull(x,y,z))
 227         {
 228             int value = myGridPtr.getPoint(x,y,z);
 229             int b = 0;
 230
 231             if (useMomentum && (currPtr.momentum != movePtr.momentum)) {
 232                 b = bendCost;
 233             }
 234             if ((value + b) <= nextPtr.value) { /* '=' favors neighbors over current */
 235                 nextPtr.x = x;
 236                 nextPtr.y = y;
 237                 nextPtr.z = z;
 238                 nextPtr.value = value;
 239                 nextPtr.momentum = movePtr.momentum;
 240             }
 241         }
 242     }
 243 /* =============================================================================
 244  * PdoTraceback
 245  * =============================================================================
 246  */
 247
 248     private Vector_t PdoTraceback(Grid myGridPtr,
 249                                   Coordinate dstPtr, int bendCost) {
 250         Vector_t pointVectorPtr = Vector_t.vector_alloc(1);
 251
 252         Point next = new Point();
 253         next.x = dstPtr.x;
 254         next.y = dstPtr.y;
 255         next.z = dstPtr.z;
 256         next.value = myGridPtr.getPoint(next.x,next.y,next.z);
 257         next.momentum = MOMENTUM_ZERO;
 258
 259         while(true) {
 260             int gridPointIndex = myGridPtr.getPointIndex(next.x,next.y,next.z);
 261             pointVectorPtr.vector_pushBack(new Integer(gridPointIndex));
 262             myGridPtr.setPoint(next.x,next.y,next.z,GRID_POINT_FULL);
 263
 264             /* Check if we are done */
 265             if (next.value == 0) {
 266                 break;
 267             }
 268             Point curr = new Point();
 269             curr.x = next.x;
 270             curr.y = next.y;
 271             curr.z = next.z;
 272             curr.value = next.value;
 273             curr.momentum = next.momentum;
 274
 275             /*
 276              * Check 6 neibors
 277              */
 278
 279             traceToNeighbor(myGridPtr,curr,MOVE_POSX,true, bendCost, next);
 280             traceToNeighbor(myGridPtr,curr,MOVE_POSY,true, bendCost, next);
 281             traceToNeighbor(myGridPtr,curr,MOVE_POSZ,true, bendCost, next);
 282             traceToNeighbor(myGridPtr,curr,MOVE_NEGX,true, bendCost, next);
 283             traceToNeighbor(myGridPtr,curr,MOVE_NEGY,true, bendCost, next);
 284             traceToNeighbor(myGridPtr,curr,MOVE_NEGZ,true, bendCost, next);
 285             /*
 286              * Because of bend costs, none of the neighbors may appear to be closer.
 287              * In this case, pick a neighbor while ignoring momentum.
 288              */
 289
 290
 291
 292             if ((curr.x == next.x) &&
 293                 (curr.y == next.y) &&
 294                 (curr.z == next.z)) {
 295                 next.value = curr.value;
 296                 traceToNeighbor(myGridPtr,curr,MOVE_POSX,false, bendCost, next);
 297                 traceToNeighbor(myGridPtr,curr,MOVE_POSY,false, bendCost, next);
 298                 traceToNeighbor(myGridPtr,curr,MOVE_POSZ,false, bendCost, next);
 299                 traceToNeighbor(myGridPtr,curr,MOVE_NEGX,false, bendCost, next);
 300                 traceToNeighbor(myGridPtr,curr,MOVE_NEGY,false, bendCost, next);
 301                 traceToNeighbor(myGridPtr,curr,MOVE_NEGZ,false, bendCost, next);
 302
 303                 if ((curr.x == next.x) &&
 304                     (curr.y == next.y) &&
 305                     (curr.z == next.z)) {
 306                     System.out.println("Dead");
 307                     return null;
 308                 }
 309             }
 310         }
 311
 312         return pointVectorPtr;
 313     }
 314
 315 /* =============================================================================
 316  * router_solve
 317  * =============================================================================
 318  * void router_solve (void* argPtr);
 319  */
 320     public static void solve(Object argPtr)
 321     {
 322         // TM_THREAD_ENTER();
 323         //
 324         Solve_Arg routerArgPtr = (Solve_Arg) argPtr;
 325         Router routerPtr = routerArgPtr.routerPtr;
 326         Maze mazePtr = routerArgPtr.mazePtr;
 327         Vector_t myPathVectorPtr = Vector_t.vector_alloc(1);
 328
 329         Queue_t workQueuePtr = mazePtr.workQueuePtr;
 330         Grid gridPtr = mazePtr.gridPtr;
 331         Grid myGridPtr = Grid.scratchalloc(gridPtr.width,gridPtr.height,gridPtr.depth);
 332         int bendCost = routerPtr.bendCost;
 333         Queue_Int myExpansionQueuePtr = Queue_Int.queue_alloc(-1);
 334
 335         /*
 336          * Iterate over work list to route each path. This involves an
 337          * 'expansion' and 'tracback' phase for each source/destination pair.
 338          */
 339         while(true) {
 340             Pair coordinatePairPtr;
 341
 342             // TM_BEGIN();
 343             atomic {
 344                 if(workQueuePtr.queue_isEmpty()) {
 345                     coordinatePairPtr = null;
 346                 } else {
 347                     coordinatePairPtr = (Pair)workQueuePtr.queue_pop();
 348                 }
 349             }
 350             // TM_END();
 351             //
 352
 353             if (coordinatePairPtr == null) {
 354                 break;
 355             }
 356
 357             Coordinate srcPtr = (Coordinate)coordinatePairPtr.first;
 358             Coordinate dstPtr = (Coordinate)coordinatePairPtr.second;
 359
 360 //            System.out.println("SRC x = " + srcPtr.x + "  y = " + srcPtr.y + " z = " +srcPtr.z);
 361
 362             boolean success = false;
 363             Vector_t pointVectorPtr = null;
 364             boolean retry=true;
 365
 366             // TM_BEGIN();
 367             while(retry) {
 368               retry=false;
 369               atomic {
 370                 Grid.copy(myGridPtr, gridPtr); /* ok if not most up-to-date */
 371                 if(routerPtr.PdoExpansion(routerPtr,myGridPtr,myExpansionQueuePtr,srcPtr,dstPtr)) {
 372                   pointVectorPtr = routerPtr.PdoTraceback(myGridPtr,dstPtr,bendCost);
 373                   if (pointVectorPtr != null) {
 374                     if (gridPtr.TM_addPath(pointVectorPtr)) {
 375                       pointVectorPtr=null;
 376                       retry=true;
 377                     } else
 378                       success=true;
 379                   }
 380                 }
 381               }
 382             }
 383
 384             if(success) {
 385                 boolean status = myPathVectorPtr.vector_pushBack(pointVectorPtr);
 386
 387                 if(!status) {
 388                     System.out.println("Assert in Router_Solve");
 389                     System.exit(1);
 390                 }
 391             }
 392         }
 393
 394         /*
 395          * Add my paths to global list
 396          */
 397         List_t pathVectorListPtr = routerArgPtr.pathVectorListPtr;
 398
 399         atomic {
 400             pathVectorListPtr.insert(myPathVectorPtr);
 401         }
 402
 403         myGridPtr = null;
 404         myExpansionQueuePtr = null;
 405 //        System.out.println("Final Grid: ");
 406 //        gridPtr.print();
 407
 408         // TM_THREAD_EXIT();
 409     }
 410 }
 411 /* =============================================================================
 412  *
 413  * End of router.java
 414  *
 415  * =============================================================================
 416  */