From ed5e369f7507ef2062323bce658eb46c9d2cb72a Mon Sep 17 00:00:00 2001 From: adash Date: Fri, 16 Oct 2009 01:28:39 +0000 Subject: [PATCH] changes to KMeans after bug bix for parsing floats change manual prefetch placements rearrange atomic blocks to enable parallel part of the code and not use one big lock around work function --- .../Benchmarks/Prefetch/KMeans/Common.java | 1 - .../Benchmarks/Prefetch/KMeans/KMeans.java | 13 ++- .../Benchmarks/Prefetch/KMeans/Normal.java | 72 ++++++++-------- .../src/Benchmarks/Prefetch/KMeans/makefile | 2 +- .../ManualPrefetch/KMeans/Common.java | 1 - .../ManualPrefetch/KMeans/KMeans.java | 22 +++-- .../ManualPrefetch/KMeans/Normal.java | 82 +++++++++---------- .../Benchmarks/SingleTM/KMeans/Cluster.java | 16 ++-- .../Benchmarks/SingleTM/KMeans/KMeans.java | 2 +- .../Benchmarks/SingleTM/KMeans/Normal.java | 8 +- .../SingleTM/common/Makefile.builds | 14 ++-- 11 files changed, 126 insertions(+), 107 deletions(-) diff --git a/Robust/src/Benchmarks/Prefetch/KMeans/Common.java b/Robust/src/Benchmarks/Prefetch/KMeans/Common.java index bd372e23..524448ba 100644 --- a/Robust/src/Benchmarks/Prefetch/KMeans/Common.java +++ b/Robust/src/Benchmarks/Prefetch/KMeans/Common.java @@ -100,7 +100,6 @@ public class Common { { int index = -1; int i; - //double max_dist = FLT_MAX; float max_dist = (float)3.40282347e+38; float limit = (float) 0.99999; diff --git a/Robust/src/Benchmarks/Prefetch/KMeans/KMeans.java b/Robust/src/Benchmarks/Prefetch/KMeans/KMeans.java index 3038bf00..844c6efa 100644 --- a/Robust/src/Benchmarks/Prefetch/KMeans/KMeans.java +++ b/Robust/src/Benchmarks/Prefetch/KMeans/KMeans.java @@ -178,11 +178,15 @@ public class KMeans extends Thread { public void run() { Barrier barr = new Barrier("128.195.136.162"); + int id; + GlobalArgs tmp_g_args; + atomic { + id = threadid; + tmp_g_args = g_args; + } while(true) { Barrier.enterBarrier(barr); - atomic { - Normal.work(threadid, g_args); - } + Normal.work(id, tmp_g_args); Barrier.enterBarrier(barr); } } @@ -391,7 +395,8 @@ public class KMeans extends Thread { } } else if(arg.equals("-t")) { if(i < args.length) { - km.threshold = new Integer(args[i++]).intValue(); + //km.threshold = new Integer(args[i++]).intValue(); + km.threshold = (float) Double.parseDouble(args[i++]); } } else if(arg.equals("-i")) { if(i < args.length) { diff --git a/Robust/src/Benchmarks/Prefetch/KMeans/Normal.java b/Robust/src/Benchmarks/Prefetch/KMeans/Normal.java index a69859b8..d0f22f5e 100644 --- a/Robust/src/Benchmarks/Prefetch/KMeans/Normal.java +++ b/Robust/src/Benchmarks/Prefetch/KMeans/Normal.java @@ -107,14 +107,16 @@ public class Normal { intwrapper[] new_centers_len; float[][] new_centers; - feature = args.feature; - nfeatures = args.nfeatures; - npoints = args.npoints; - nclusters = args.nclusters; - membership = args.membership; - clusters = args.clusters; - new_centers_len = args.new_centers_len; - new_centers = args.new_centers; + atomic { + feature = args.feature; + nfeatures = args.nfeatures; + npoints = args.npoints; + nclusters = args.nclusters; + membership = args.membership; + clusters = args.clusters; + new_centers_len = args.new_centers_len; + new_centers = args.new_centers; + } float delta = 0.0f; int index, start, stop; @@ -124,41 +126,46 @@ public class Normal { //System.out.println("myId= " + myId + " start= " + start + " npoints= " + npoints); while (start < npoints) { stop = (((start + CHUNK) < npoints) ? (start + CHUNK) : npoints); - for (int i = start; i < stop; i++) { - index = Common.common_findNearestPoint(feature[i], - nfeatures, - clusters, - nclusters); - // - // If membership changes, increase delta by 1. - // membership[i] cannot be changed by other threads - // - if (membership[i] != index) { - delta += 1.0f; - } + atomic { + index = Common.common_findNearestPoint(feature[i], + nfeatures, + clusters, + nclusters); + // + // If membership changes, increase delta by 1. + // membership[i] cannot be changed by other threads + // + if (membership[i] != index) { + delta += 1.0f; + } - // Assign the membership to object i - // membership[i] can't be changed by other thread - membership[i] = index; + // Assign the membership to object i + // membership[i] can't be changed by other thread + membership[i] = index; - // Update new cluster centers : sum of objects located within - new_centers_len[index] = new_centers_len[index] + 1; - for (int j = 0; j < nfeatures; j++) { - new_centers[index][j] = new_centers[index][j] + feature[i][j]; + // Update new cluster centers : sum of objects located within + new_centers_len[index] = new_centers_len[index] + 1; + for (int j = 0; j < nfeatures; j++) { + new_centers[index][j] = new_centers[index][j] + feature[i][j]; + } } } // Update task queue if (start + CHUNK < npoints) { - start = args.global_i; - args.global_i = start + CHUNK; + atomic { + start = args.global_i; + args.global_i = start + CHUNK; + } } else { break; } } - args.global_delta = args.global_delta + delta; + atomic { + args.global_delta = args.global_delta + delta; + } } /* ============================================================================= @@ -261,11 +268,8 @@ public class Normal { * Work done by primary thread in parallel with other threads **/ void thread_work(GlobalArgs args, Barrier barr) { - //System.out.println("Inside thread_work\n"); Barrier.enterBarrier(barr); - atomic { - Normal.work(0, args); //threadId = 0 because primary thread - } + Normal.work(0, args); //threadId = 0 because primary thread Barrier.enterBarrier(barr); } } diff --git a/Robust/src/Benchmarks/Prefetch/KMeans/makefile b/Robust/src/Benchmarks/Prefetch/KMeans/makefile index a5c7a299..0b7b61bd 100644 --- a/Robust/src/Benchmarks/Prefetch/KMeans/makefile +++ b/Robust/src/Benchmarks/Prefetch/KMeans/makefile @@ -8,7 +8,7 @@ SRC=${MAINCLASS}.java \ ../../../ClassLibrary/JavaDSM/Barrier.java FLAGS=-mainclass ${MAINCLASS} -dsm -optimize -transstats -FLAGS1=-mainclass ${MAINCLASS} -dsm -dsmcaching -profile -optimize -transstats +FLAGS1=-mainclass ${MAINCLASS} -dsm -dsmcaching -optimize -transstats dsm: ../../../buildscript ${FLAGS} -o ${MAINCLASS}NPNC ${SRC} diff --git a/Robust/src/Benchmarks/Prefetch/ManualPrefetch/KMeans/Common.java b/Robust/src/Benchmarks/Prefetch/ManualPrefetch/KMeans/Common.java index bd372e23..524448ba 100644 --- a/Robust/src/Benchmarks/Prefetch/ManualPrefetch/KMeans/Common.java +++ b/Robust/src/Benchmarks/Prefetch/ManualPrefetch/KMeans/Common.java @@ -100,7 +100,6 @@ public class Common { { int index = -1; int i; - //double max_dist = FLT_MAX; float max_dist = (float)3.40282347e+38; float limit = (float) 0.99999; diff --git a/Robust/src/Benchmarks/Prefetch/ManualPrefetch/KMeans/KMeans.java b/Robust/src/Benchmarks/Prefetch/ManualPrefetch/KMeans/KMeans.java index f99011d7..03874818 100644 --- a/Robust/src/Benchmarks/Prefetch/ManualPrefetch/KMeans/KMeans.java +++ b/Robust/src/Benchmarks/Prefetch/ManualPrefetch/KMeans/KMeans.java @@ -178,11 +178,23 @@ public class KMeans extends Thread { public void run() { Barrier barr = new Barrier("128.195.136.162"); - while(true) { + int id; + GlobalArgs tmp_g_args; + atomic { + id = threadid; + tmp_g_args = g_args; + short[] offsets = new short[4]; + offsets[0] = getoffset{GlobalArgs, clusters}; + offsets[1] = (short) 0; + offsets[2] = (short) 0; + offsets[3] = (short) min_nclusters; + System.rangePrefetch(g_args, offsets); + } + //Add Manual prefetch for + //args.clusters[0-> nclusters] + while(true) { Barrier.enterBarrier(barr); - atomic { - Normal.work(threadid, g_args); - } + Normal.work(id, tmp_g_args); Barrier.enterBarrier(barr); } } @@ -391,7 +403,7 @@ public class KMeans extends Thread { } } else if(arg.equals("-t")) { if(i < args.length) { - km.threshold = new Integer(args[i++]).intValue(); + km.threshold = (float) Double.parseDouble(args[i++]); } } else if(arg.equals("-i")) { if(i < args.length) { diff --git a/Robust/src/Benchmarks/Prefetch/ManualPrefetch/KMeans/Normal.java b/Robust/src/Benchmarks/Prefetch/ManualPrefetch/KMeans/Normal.java index 13494362..16945206 100644 --- a/Robust/src/Benchmarks/Prefetch/ManualPrefetch/KMeans/Normal.java +++ b/Robust/src/Benchmarks/Prefetch/ManualPrefetch/KMeans/Normal.java @@ -109,31 +109,25 @@ public class Normal { int index, start, stop; start = myId * CHUNK; - nclusters = args.nclusters; - npoints = args.npoints; - - //Add Manual prefetch for //args.feature[start-> stop] short[] offsets = new short[4]; offsets[0] = getoffset{GlobalArgs, feature}; offsets[1] = (short) 0; offsets[2] = (short) start; - offsets[3] = (short) npoints; - System.rangePrefetch(args, offsets); - //args.clusters[0-> nclusters] - offsets[0] = getoffset{GlobalArgs, clusters}; - offsets[1] = (short) 0; - offsets[2] = (short) 0; - offsets[3] = (short) nclusters; + offsets[3] = (short) (10*CHUNK); System.rangePrefetch(args, offsets); - - feature = args.feature; - nfeatures = args.nfeatures; - membership = args.membership; - clusters = args.clusters; - new_centers_len = args.new_centers_len; - new_centers = args.new_centers; + atomic { + nclusters = args.nclusters; + npoints = args.npoints; + + feature = args.feature; + nfeatures = args.nfeatures; + membership = args.membership; + clusters = args.clusters; + new_centers_len = args.new_centers_len; + new_centers = args.new_centers; + } float delta = 0.0f; @@ -141,39 +135,45 @@ public class Normal { while (start < npoints) { stop = (((start + CHUNK) < npoints) ? (start + CHUNK) : npoints); for (int i = start; i < stop; i++) { - index = Common.common_findNearestPoint(feature[i], - nfeatures, - clusters, - nclusters); - // - // If membership changes, increase delta by 1. - // membership[i] cannot be changed by other threads - // - if (membership[i] != index) { - delta += 1.0f; - } + atomic { + index = Common.common_findNearestPoint(feature[i], + nfeatures, + clusters, + nclusters); + // + // If membership changes, increase delta by 1. + // membership[i] cannot be changed by other threads + // + if (membership[i] != index) { + delta += 1.0f; + } - // Assign the membership to object i - // membership[i] can't be changed by other thread - membership[i] = index; + // Assign the membership to object i + // membership[i] can't be changed by other thread + membership[i] = index; - // Update new cluster centers : sum of objects located within - new_centers_len[index] = new_centers_len[index] + 1; - for (int j = 0; j < nfeatures; j++) { - new_centers[index][j] = new_centers[index][j] + feature[i][j]; + // Update new cluster centers : sum of objects located within + new_centers_len[index] = new_centers_len[index] + 1; + for (int j = 0; j < nfeatures; j++) { + new_centers[index][j] = new_centers[index][j] + feature[i][j]; + } } } // Update task queue if (start + CHUNK < npoints) { - start = args.global_i; - args.global_i = start + CHUNK; + atomic { + start = args.global_i; + args.global_i = start + CHUNK; + } } else { break; } } - args.global_delta = args.global_delta + delta; + atomic { + args.global_delta = args.global_delta + delta; + } } /* ============================================================================= @@ -278,9 +278,7 @@ public class Normal { void thread_work(GlobalArgs args, Barrier barr) { //System.out.println("Inside thread_work\n"); Barrier.enterBarrier(barr); - atomic { - Normal.work(0, args); //threadId = 0 because primary thread - } + Normal.work(0, args); //threadId = 0 because primary thread Barrier.enterBarrier(barr); } } diff --git a/Robust/src/Benchmarks/SingleTM/KMeans/Cluster.java b/Robust/src/Benchmarks/SingleTM/KMeans/Cluster.java index 90912c29..8b36949a 100644 --- a/Robust/src/Benchmarks/SingleTM/KMeans/Cluster.java +++ b/Robust/src/Benchmarks/SingleTM/KMeans/Cluster.java @@ -88,12 +88,13 @@ public class Cluster { { float[] moments = new float[num_moments]; - float mzero=0.0f; + //float mzero=0.0f; for (int i = 0; i < num_elts; i++) { - mzero += data[i]; + //mzero += data[i]; + moments[0] += data[i]; } - moments[0] = mzero / num_elts; + moments[0] = moments[0] / num_elts; for (int j = 1; j < num_moments; j++) { moments[j] = 0; for (int i = 0; i < num_elts; i++) { @@ -125,7 +126,9 @@ public class Cluster { for (int j = 0; j < numObjects; j++) { data[j][i] = (data[j][i]-moments[0])/moments[1]; } + moments=null; } + single_variable=null; } @@ -139,8 +142,8 @@ public class Cluster { int numObjects, /* number of input objects */ int numAttributes, /* size of attribute of each object */ float[][] attributes, /* [numObjects][numAttributes] */ - KMeans kms, /* KMeans class hold the inputs and outputs */ - GlobalArgs args /* Global thread arguments */ + KMeans kms, /* KMeans class hold the inputs and outputs */ + GlobalArgs args /* Global thread arguments */ ) { int itime; @@ -160,7 +163,8 @@ public class Cluster { /* * From min_nclusters to max_nclusters, find best_nclusters - */ + */ + System.out.println("min_nclusters= " + kms.min_nclusters + " max_nclusters= " + kms.max_nclusters); for (nclusters = kms.min_nclusters; nclusters <= kms.max_nclusters; nclusters++) { randomPtr.random_seed(7); diff --git a/Robust/src/Benchmarks/SingleTM/KMeans/KMeans.java b/Robust/src/Benchmarks/SingleTM/KMeans/KMeans.java index 398850a8..7144b198 100644 --- a/Robust/src/Benchmarks/SingleTM/KMeans/KMeans.java +++ b/Robust/src/Benchmarks/SingleTM/KMeans/KMeans.java @@ -234,7 +234,7 @@ public class KMeans extends Thread { * The core of the clustering */ - int[] cluster_assign = new int[numObjects]; + //int[] cluster_assign = new int[numObjects]; int nloops = 1; int len = kms.max_nclusters - kms.min_nclusters + 1; diff --git a/Robust/src/Benchmarks/SingleTM/KMeans/Normal.java b/Robust/src/Benchmarks/SingleTM/KMeans/Normal.java index 84b99236..1ce66cc9 100644 --- a/Robust/src/Benchmarks/SingleTM/KMeans/Normal.java +++ b/Robust/src/Benchmarks/SingleTM/KMeans/Normal.java @@ -110,6 +110,7 @@ public class Normal { int index, start, stop; start = myId * CHUNK; + System.out.println("myId= " + myId + " start= " + start + " npoints= " + npoints); // System.out.println("myId= " + myId + " start= " + start + " npoints= " + npoints); while (start < npoints) { @@ -197,7 +198,6 @@ public class Normal { intwrapper[] new_centers_len = new intwrapper[nclusters]; float[][] new_centers = new float[nclusters][nfeatures]; - int count; int loop = 0; do { @@ -217,14 +217,13 @@ public class Normal { //Work in parallel with other threads thread_work(args); - count++; delta = args.global_delta; /* Replace old cluster centers with new_centers */ for (int i = 0; i < nclusters; i++) { for (int j = 0; j < nfeatures; j++) { - if (new_centers_len[i] > 0) { + if (new_centers_len != null) { clusters[i][j] = new_centers[i][j] / new_centers_len[i]; } new_centers[i][j] = (float)0.0; /* set back to 0 */ @@ -234,11 +233,10 @@ public class Normal { delta /= npoints; - //System.out.println("delta= " + delta + " loop= " + loop + " threshold= " + threshold); + System.out.println("delta= " + delta + " loop= " + loop); } while ((delta > threshold) && (loop++ < 500)); - //System.out.println("count= " + count); return clusters; } diff --git a/Robust/src/Benchmarks/SingleTM/common/Makefile.builds b/Robust/src/Benchmarks/SingleTM/common/Makefile.builds index c296ff41..8ad41032 100644 --- a/Robust/src/Benchmarks/SingleTM/common/Makefile.builds +++ b/Robust/src/Benchmarks/SingleTM/common/Makefile.builds @@ -1,26 +1,26 @@ default: lock basestm lockjopt stmjopt stmopt fission lock: prep - ../../../buildscript ${FLAGSLOCKNOJ} -o LOCKNOJ${MAINCLASS} ${SRC} +# ../../../buildscript ${FLAGSLOCKNOJ} -o LOCKNOJ${MAINCLASS} ${SRC} basestm: prep ../../../buildscript ${FLAGSSTMNOJ} -o STMNOJ${MAINCLASS} ${SRC} lockjopt: prep - ../../../buildscript ${FLAGSLOCK} -o LOCK${MAINCLASS} ${SRC} +# ../../../buildscript ${FLAGSLOCK} -o LOCK${MAINCLASS} ${SRC} stmjopt: prep - ../../../buildscript ${FLAGSSTM} -o STM${MAINCLASS} ${SRC} +# ../../../buildscript ${FLAGSSTM} -o STM${MAINCLASS} ${SRC} stmopt: prep - ../../../buildscript ${FLAGSOPTSTM} -o OPTSTM${MAINCLASS} ${SRC} +# ../../../buildscript ${FLAGSOPTSTM} -o OPTSTM${MAINCLASS} ${SRC} fission: prep - ../../../buildscript ${FLAGSFISSION} -o FIS${MAINCLASS} ${SRC} +# ../../../buildscript ${FLAGSFISSION} -o FIS${MAINCLASS} ${SRC} debug: prep - ../../../buildscript ${FLAGSDEBUG} -o DEB${MAINCLASS} ${SRC} +# ../../../buildscript ${FLAGSDEBUG} -o DEB${MAINCLASS} ${SRC} stats: prep - ../../../buildscript ${FLAGSSTATS} -o STATS${MAINCLASS} ${SRC} +# ../../../buildscript ${FLAGSSTATS} -o STATS${MAINCLASS} ${SRC} -- 2.34.1