1 /* =============================================================================
4 * -- Implementation of normal k-means clustering algorithm
6 * =============================================================================
11 * ECE Department, Northwestern University
12 * email: wkliao@ece.northwestern.edu
18 * Northwestern University.
24 * University of California, Irvine
27 * =============================================================================
29 * For the license of bayes/sort.h and bayes/sort.c, please see the header
32 * ------------------------------------------------------------------------
34 * For the license of kmeans, please see kmeans/LICENSE.kmeans
36 * ------------------------------------------------------------------------
38 * For the license of ssca2, please see ssca2/COPYRIGHT
40 * ------------------------------------------------------------------------
42 * For the license of lib/mt19937ar.c and lib/mt19937ar.h, please see the
43 * header of the files.
45 * ------------------------------------------------------------------------
47 * For the license of lib/rbtree.h and lib/rbtree.c, please see
48 * lib/LEGALNOTICE.rbtree and lib/LICENSE.rbtree
50 * ------------------------------------------------------------------------
52 * Unless otherwise noted, the following license applies to STAMP files:
54 * Copyright (c) 2007, Stanford University
55 * All rights reserved.
57 * Redistribution and use in source and binary forms, with or without
58 * modification, are permitted provided that the following conditions are
61 * * Redistributions of source code must retain the above copyright
62 * notice, this list of conditions and the following disclaimer.
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
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.
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.
85 * =============================================================================
95 /* =============================================================================
97 * =============================================================================
99 public static void work(int myId, GlobalArgs args) {
107 intwrapper[] new_centers_len;
108 float[][] new_centers;
109 int index, start, stop;
111 start = myId * CHUNK;
112 //manual prefetch args.feature[start-> stop]
113 short[] offsets = new short[4];
114 offsets[0] = getoffset{GlobalArgs, clusters};
115 offsets[1] = (short) 0;
116 offsets[2] = (short) 0;
117 offsets[3] = (short) nclusters;
118 System.rangePrefetch(args, offsets);
121 nclusters = args.nclusters;
122 npoints = args.npoints;
123 feature = args.feature;
124 nfeatures = args.nfeatures;
125 membership = args.membership;
126 clusters = args.clusters;
127 new_centers_len = args.new_centers_len;
128 new_centers = args.new_centers;
133 //System.out.println("myId= " + myId + " start= " + start + " stop= " + stop + " npoints= " + npoints);
134 while (start < npoints) {
135 stop = (((start + CHUNK) < npoints) ? (start + CHUNK) : npoints);
136 for (int i = start; i < stop; i++) {
138 index = Common.common_findNearestPoint(feature[i],
143 // If membership changes, increase delta by 1.
144 // membership[i] cannot be changed by other threads
146 if (membership[i] != index) {
150 // Assign the membership to object i
151 // membership[i] can't be changed by other thread
152 membership[i] = index;
154 // Update new cluster centers : sum of objects located within
155 new_centers_len[index] = new_centers_len[index] + 1;
156 for (int j = 0; j < nfeatures; j++) {
157 new_centers[index][j] = new_centers[index][j] + feature[i][j];
163 if (start + CHUNK < npoints) {
165 start = args.global_i;
166 args.global_i = start + CHUNK;
171 //l=(short)(l+(short)(t*CHUNK));
175 args.global_delta = args.global_delta + delta;
179 /* =============================================================================
181 * =============================================================================
183 public float[][] normal_exec (
185 float[][] feature, /* in: [npoints][nfeatures] */
191 Random randomPtr, /* out: [npoints] */
195 float[][] clusters; /* out: [nclusters][nfeatures] */
198 /* Randomly pick cluster centers */
200 /* Allocate space for returning variable clusters[] */
201 clusters = global new float[nclusters][nfeatures];
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];
209 for (int i = 0; i < npoints; i++) {
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.
218 intwrapper[] new_centers_len;
219 float[][] new_centers;
221 new_centers_len = global new intwrapper[nclusters];
222 new_centers = global new float[nclusters][nfeatures];
232 Barrier barr = new Barrier("128.195.136.162");
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;
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;
250 //Work in parallel with other threads
251 thread_work(tmp_args, barr);
254 delta = tmp_args.global_delta;
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];
262 new_centers[i][j] = (float)0.0; // set back to 0
264 new_centers_len[i] = 0; // set back to 0
269 //System.out.println("delta= " + delta + " loop= " + loop + " threshold= " + threshold);
270 } while ((delta > threshold) && (loop++ < 500));
276 * Work done by primary thread in parallel with other threads
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);
286 /* =============================================================================
290 * =============================================================================