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