Robust/src/Benchmarks/Prefetch/ManualPrefetch/KMeans/Normal.java

   1 /* =============================================================================
   2  *
   3  * normal.java
   4  * -- Implementation of normal k-means clustering algorithm
   5  *
   6  * =============================================================================
   7  *
   8  * Author:
   9  *
  10  * Wei-keng Liao
  11  * ECE Department, Northwestern University
  12  * email: wkliao@ece.northwestern.edu
  13  *
  14  *
  15  * Edited by:
  16  *
  17  * Jay Pisharath
  18  * Northwestern University.
  19  *
  20  * Chi Cao Minh
  21  * Stanford University
  22  *
  23  * Alokika Dash
  24  * University of California, Irvine
  25  * Ported to Java
  26  *
  27  * =============================================================================
  28  *
  29  * For the license of bayes/sort.h and bayes/sort.c, please see the header
  30  * of the files.
  31  *
  32  * ------------------------------------------------------------------------
  33  *
  34  * For the license of kmeans, please see kmeans/LICENSE.kmeans
  35  *
  36  * ------------------------------------------------------------------------
  37  *
  38  * For the license of ssca2, please see ssca2/COPYRIGHT
  39  *
  40  * ------------------------------------------------------------------------
  41  *
  42  * For the license of lib/mt19937ar.c and lib/mt19937ar.h, please see the
  43  * header of the files.
  44  *
  45  * ------------------------------------------------------------------------
  46  *
  47  * For the license of lib/rbtree.h and lib/rbtree.c, please see
  48  * lib/LEGALNOTICE.rbtree and lib/LICENSE.rbtree
  49  *
  50  * ------------------------------------------------------------------------
  51  *
  52  * Unless otherwise noted, the following license applies to STAMP files:
  53  *
  54  * Copyright (c) 2007, Stanford University
  55  * All rights reserved.
  56  *
  57  * Redistribution and use in source and binary forms, with or without
  58  * modification, are permitted provided that the following conditions are
  59  * met:
  60  *
  61  *     * Redistributions of source code must retain the above copyright
  62  *       notice, this list of conditions and the following disclaimer.
  63  *
  64  *     * Redistributions in binary form must reproduce the above copyright
  65  *       notice, this list of conditions and the following disclaimer in
  66  *       the documentation and/or other materials provided with the
  67  *       distribution.
  68  *
  69  *     * Neither the name of Stanford University nor the names of its
  70  *       contributors may be used to endorse or promote products derived
  71  *       from this software without specific prior written permission.
  72  *
  73  * THIS SOFTWARE IS PROVIDED BY STANFORD UNIVERSITY ``AS IS'' AND ANY
  74  * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  75  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
  76  * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL STANFORD UNIVERSITY BE LIABLE
  77  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
  78  * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
  79  * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
  80  * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
  81  * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
  82  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF
  83  * THE POSSIBILITY OF SUCH DAMAGE.
  84 *
  85 * =============================================================================
  86 */
  87
  88 public class Normal {
  89   int CHUNK;
  90
  91   public Normal() {
  92     CHUNK = 3;
  93   }
  94
  95   /* =============================================================================
  96    * work
  97    * =============================================================================
  98    */
  99   public static void work(int myId, GlobalArgs args) {
 100     int CHUNK=3;
 101     float[][] feature;
 102     int nfeatures;
 103     int npoints;
 104     int nclusters;
 105     int[] membership;
 106     float[][] clusters;
 107     intwrapper[] new_centers_len;
 108     float[][] new_centers;
 109     int index, start, stop;
 110
 111     start = myId * CHUNK;
 112     //args.feature[start-> stop]
 113     short[] offsets = new short[4];
 114     offsets[0] = getoffset{GlobalArgs, feature};
 115     offsets[1] = (short) 0;
 116     offsets[2] = (short) start;
 117     offsets[3] = (short) (10*CHUNK);
 118     System.rangePrefetch(args, offsets);
 119
 120     atomic {
 121       nclusters = args.nclusters;
 122       npoints = args.npoints;
 123
 124       feature = args.feature;
 125       nfeatures = args.nfeatures;
 126       membership = args.membership;
 127       clusters = args.clusters;
 128       new_centers_len = args.new_centers_len;
 129       new_centers = args.new_centers;
 130     }
 131
 132     float delta = 0.0f;
 133
 134     //System.out.println("myId= " + myId + " start= " + start + " stop= " + stop + " npoints= " + npoints);
 135     while (start < npoints) {
 136       stop = (((start + CHUNK) < npoints) ? (start + CHUNK) : npoints);
 137       for (int i = start; i < stop; i++) {
 138         atomic {
 139           index = Common.common_findNearestPoint(feature[i],
 140               nfeatures,
 141               clusters,
 142               nclusters);
 143           //
 144           // If membership changes, increase delta by 1.
 145           // membership[i] cannot be changed by other threads
 146           //
 147           if (membership[i] != index) {
 148             delta += 1.0f;
 149           }
 150
 151           // Assign the membership to object i
 152           // membership[i] can't be changed by other thread
 153           membership[i] = index;
 154
 155           // Update new cluster centers : sum of objects located within
 156           new_centers_len[index] = new_centers_len[index] + 1;
 157           for (int j = 0; j < nfeatures; j++) {
 158             new_centers[index][j] = new_centers[index][j] + feature[i][j];
 159           }
 160         }
 161       }
 162
 163       // Update task queue
 164       if (start + CHUNK < npoints) {
 165         atomic {
 166           start = args.global_i;
 167           args.global_i = start + CHUNK;
 168         }
 169       } else {
 170         break;
 171       }
 172     }
 173
 174     atomic {
 175       args.global_delta = args.global_delta + delta;
 176     }
 177   }
 178
 179   /* =============================================================================
 180    * normal_exec
 181    * =============================================================================
 182    */
 183   public float[][] normal_exec (
 184       int       nthreads,
 185       float[][]   feature,    /* in: [npoints][nfeatures] */
 186       int       nfeatures,
 187       int       npoints,
 188       int       nclusters,
 189       float     threshold,
 190       int[]      membership,
 191       Random     randomPtr,  /* out: [npoints] */
 192       GlobalArgs args)
 193   {
 194     float delta;
 195     float[][] clusters;      /* out: [nclusters][nfeatures] */
 196
 197
 198     /* Randomly pick cluster centers */
 199     atomic {
 200       /* Allocate space for returning variable clusters[] */
 201       clusters = global new float[nclusters][nfeatures];
 202
 203       for (int i = 0; i < nclusters; i++) {
 204         int n = (int)(randomPtr.random_generate() % npoints);
 205         for (int j = 0; j < nfeatures; j++) {
 206           clusters[i][j] = feature[n][j];
 207         }
 208       }
 209       for (int i = 0; i < npoints; i++) {
 210         membership[i] = -1;
 211       }
 212     }
 213
 214     /*
 215      * Need to initialize new_centers_len and new_centers[0] to all 0.
 216      * Allocate clusters on different cache lines to reduce false sharing.
 217      */
 218     intwrapper[] new_centers_len;
 219     float[][] new_centers;
 220     atomic {
 221       new_centers_len  = global new intwrapper[nclusters];
 222       new_centers = global new float[nclusters][nfeatures];
 223     }
 224
 225     int loop = 0;
 226
 227     GlobalArgs tmp_args;
 228     atomic {
 229       tmp_args = args;
 230     }
 231
 232     Barrier barr = new Barrier("128.195.136.162");
 233     do {
 234       delta = (float) 0.0;
 235
 236       atomic {
 237         tmp_args.feature         = feature;
 238         tmp_args.clusters        = clusters;
 239         tmp_args.new_centers_len = new_centers_len;
 240         tmp_args.new_centers     = new_centers;
 241
 242         tmp_args.nfeatures       = nfeatures;
 243         tmp_args.npoints         = npoints;
 244         tmp_args.nclusters       = nclusters;
 245         tmp_args.membership      = membership;
 246         tmp_args.global_i = nthreads * CHUNK;
 247         tmp_args.global_delta = delta;
 248       }
 249
 250       //Work in parallel with other threads
 251       thread_work(tmp_args, barr);
 252
 253       atomic {
 254         delta = tmp_args.global_delta;
 255
 256         // Replace old cluster centers with new_centers
 257         for (int i = 0; i < nclusters; i++) {
 258           for (int j = 0; j < nfeatures; j++) {
 259             if (new_centers_len[i] > 0) {
 260               clusters[i][j] = new_centers[i][j] / new_centers_len[i];
 261             }
 262             new_centers[i][j] = (float)0.0;   // set back to 0
 263           }
 264           new_centers_len[i] = 0;   // set back to 0
 265         }
 266       }
 267
 268       delta /= npoints;
 269       //System.out.println("delta= " + delta + " loop= " + loop + " threshold= " + threshold);
 270     } while ((delta > threshold) && (loop++ < 500));
 271
 272     return clusters;
 273   }
 274
 275   /**
 276    * Work done by primary thread in parallel with other threads
 277    **/
 278   void thread_work(GlobalArgs args, Barrier barr) {
 279     //System.out.println("Inside thread_work\n");
 280     Barrier.enterBarrier(barr);
 281     Normal.work(0, args); //threadId = 0 because primary thread
 282     Barrier.enterBarrier(barr);
 283   }
 284 }
 285
 286 /* =============================================================================
 287  *
 288  * End of normal.java
 289  *
 290  * =============================================================================
 291  */