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