Robust/src/Benchmarks/Prefetch/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
 110     atomic {
 111       feature = args.feature;
 112       nfeatures = args.nfeatures;
 113       npoints = args.npoints;
 114       nclusters = args.nclusters;
 115       membership = args.membership;
 116       clusters = args.clusters;
 117       new_centers_len = args.new_centers_len;
 118       new_centers = args.new_centers;
 119     }
 120
 121     float delta = 0.0f;
 122     int index, start, stop;
 123
 124     start = myId * CHUNK;
 125
 126     //System.out.println("myId= " + myId + " start= " + start + " npoints= " + npoints);
 127     while (start < npoints) {
 128       stop = (((start + CHUNK) < npoints) ? (start + CHUNK) : npoints);
 129       for (int i = start; i < stop; i++) {
 130         atomic {
 131           index = Common.common_findNearestPoint(feature[i],
 132               nfeatures,
 133               clusters,
 134               nclusters);
 135           //
 136           // If membership changes, increase delta by 1.
 137           // membership[i] cannot be changed by other threads
 138           //
 139           if (membership[i] != index) {
 140             delta += 1.0f;
 141           }
 142
 143           // Assign the membership to object i
 144           // membership[i] can't be changed by other thread
 145           membership[i] = index;
 146
 147           // Update new cluster centers : sum of objects located within
 148           new_centers_len[index] = new_centers_len[index] + 1;
 149           for (int j = 0; j < nfeatures; j++) {
 150             new_centers[index][j] = new_centers[index][j] + feature[i][j];
 151           }
 152         }
 153       }
 154
 155       // Update task queue
 156       if (start + CHUNK < npoints) {
 157         atomic {
 158           start = args.global_i;
 159           args.global_i = start + CHUNK;
 160         }
 161       } else {
 162         break;
 163       }
 164     }
 165
 166     atomic {
 167       args.global_delta = args.global_delta + delta;
 168     }
 169   }
 170
 171   /* =============================================================================
 172    * normal_exec
 173    * =============================================================================
 174    */
 175   public float[][] normal_exec (
 176       int       nthreads,
 177       float[][]   feature,    /* in: [npoints][nfeatures] */
 178       int       nfeatures,
 179       int       npoints,
 180       int       nclusters,
 181       float     threshold,
 182       int[]      membership,
 183       Random     randomPtr,  /* out: [npoints] */
 184       GlobalArgs args)
 185   {
 186     float delta;
 187     float[][] clusters;      /* out: [nclusters][nfeatures] */
 188
 189
 190     /* Randomly pick cluster centers */
 191     atomic {
 192       /* Allocate space for returning variable clusters[] */
 193       clusters = global new float[nclusters][nfeatures];
 194
 195       for (int i = 0; i < nclusters; i++) {
 196         int n = (int)(randomPtr.random_generate() % npoints);
 197         for (int j = 0; j < nfeatures; j++) {
 198           clusters[i][j] = feature[n][j];
 199         }
 200       }
 201       for (int i = 0; i < npoints; i++) {
 202         membership[i] = -1;
 203       }
 204     }
 205
 206     /*
 207      * Need to initialize new_centers_len and new_centers[0] to all 0.
 208      * Allocate clusters on different cache lines to reduce false sharing.
 209      */
 210     intwrapper[] new_centers_len;
 211     float[][] new_centers;
 212     atomic {
 213       new_centers_len  = global new intwrapper[nclusters];
 214       new_centers = global new float[nclusters][nfeatures];
 215     }
 216
 217     int loop = 0;
 218
 219     GlobalArgs tmp_args;
 220     atomic {
 221       tmp_args = args;
 222     }
 223
 224     Barrier barr = new Barrier("128.195.136.162");
 225     do {
 226       delta = (float) 0.0;
 227
 228       atomic {
 229         tmp_args.feature         = feature;
 230         tmp_args.clusters        = clusters;
 231         tmp_args.new_centers_len = new_centers_len;
 232         tmp_args.new_centers     = new_centers;
 233
 234         tmp_args.nfeatures       = nfeatures;
 235         tmp_args.npoints         = npoints;
 236         tmp_args.nclusters       = nclusters;
 237         tmp_args.membership      = membership;
 238         tmp_args.global_i = nthreads * CHUNK;
 239         tmp_args.global_delta = delta;
 240       }
 241
 242       //Work in parallel with other threads
 243       thread_work(tmp_args, barr);
 244
 245       atomic {
 246         delta = tmp_args.global_delta;
 247
 248         // Replace old cluster centers with new_centers
 249         for (int i = 0; i < nclusters; i++) {
 250           for (int j = 0; j < nfeatures; j++) {
 251             if (new_centers_len[i] > 0) {
 252               clusters[i][j] = new_centers[i][j] / new_centers_len[i];
 253             }
 254             new_centers[i][j] = (float)0.0;   // set back to 0
 255           }
 256           new_centers_len[i] = 0;   // set back to 0
 257         }
 258       }
 259
 260       delta /= npoints;
 261       //System.out.println("delta= " + delta + " loop= " + loop + " threshold= " + threshold);
 262     } while ((delta > threshold) && (loop++ < 500));
 263
 264     return clusters;
 265   }
 266
 267   /**
 268    * Work done by primary thread in parallel with other threads
 269    **/
 270   void thread_work(GlobalArgs args, Barrier barr) {
 271     Barrier.enterBarrier(barr);
 272     Normal.work(0, args); //threadId = 0 because primary thread
 273     Barrier.enterBarrier(barr);
 274   }
 275 }
 276
 277 /* =============================================================================
 278  *
 279  * End of normal.java
 280  *
 281  * =============================================================================
 282  */