Robust/src/Benchmarks/Prefetch/ManualPrefetch/KMeans/KMeans.java

   1 /* =============================================================================
   2  *
   3  * kmeans.java
   4  *
   5  * =============================================================================
   6  *
   7  * Description:
   8  *
   9  * Takes as input a file:
  10  *   ascii  file: containing 1 data point per line
  11  *   binary file: first int is the number of objects
  12  *                2nd int is the no. of features of each object
  13  *
  14  * This example performs a fuzzy c-means clustering on the data. Fuzzy clustering
  15  * is performed using min to max clusters and the clustering that gets the best
  16  * score according to a compactness and separation criterion are returned.
  17  *
  18  *
  19  * Author:
  20  *
  21  * Wei-keng Liao
  22  * ECE Department Northwestern University
  23  * email: wkliao@ece.northwestern.edu
  24  *
  25  *
  26  * Edited by:
  27  *
  28  * Jay Pisharath
  29  * Northwestern University
  30  *
  31  * Chi Cao Minh
  32  * Stanford University
  33  *
  34  * Port to Java version
  35  * Alokika Dash
  36  * University of California, Irvine
  37  *
  38  * =============================================================================
  39  *
  40  * ------------------------------------------------------------------------
  41  *
  42  * For the license of kmeans, please see kmeans/LICENSE.kmeans
  43  *
  44  * ------------------------------------------------------------------------
  45  *
  46  * Unless otherwise noted, the following license applies to STAMP files:
  47  *
  48  * Copyright (c) 2007, Stanford University
  49  * All rights reserved.
  50  *
  51  * Redistribution and use in source and binary forms, with or without
  52  * modification, are permitted provided that the following conditions are
  53  * met:
  54  *
  55  *     * Redistributions of source code must retain the above copyright
  56  *       notice, this list of conditions and the following disclaimer.
  57  *
  58  *     * Redistributions in binary form must reproduce the above copyright
  59  *       notice, this list of conditions and the following disclaimer in
  60  *       the documentation and/or other materials provided with the
  61  *       distribution.
  62  *
  63  *     * Neither the name of Stanford University nor the names of its
  64  *       contributors may be used to endorse or promote products derived
  65  *       from this software without specific prior written permission.
  66  *
  67  * THIS SOFTWARE IS PROVIDED BY STANFORD UNIVERSITY ``AS IS'' AND ANY
  68  * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  69  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
  70  * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL STANFORD UNIVERSITY BE LIABLE
  71  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
  72  * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
  73  * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
  74  * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
  75  * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
  76  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF
  77  * THE POSSIBILITY OF SUCH DAMAGE.
  78  *
  79  * =============================================================================
  80  */
  81
  82 public class KMeans extends Thread {
  83   /**
  84    * User input for max clusters
  85    **/
  86   int max_nclusters;
  87
  88   /**
  89    * User input for min clusters
  90    **/
  91   int min_nclusters;
  92
  93   /**
  94    * Check for Binary file
  95    **/
  96   int isBinaryFile;
  97
  98   /**
  99    * Using zscore transformation for cluster center
 100    * deviating from distribution's mean
 101    **/
 102   int use_zscore_transform;
 103
 104   /**
 105    * Input file name used for clustering
 106    **/
 107   String filename;
 108
 109   /**
 110    * Total number of threads
 111    **/
 112   int nthreads;
 113
 114   /**
 115    * threshold until which kmeans cluster continues
 116    **/
 117   float threshold;
 118
 119   /**
 120    * thread id
 121    **/
 122   int threadid;
 123
 124   /**
 125    * Global arguments for threads
 126    **/
 127   GlobalArgs g_args;
 128
 129   /**
 130    * Output:  Number of best clusters
 131    **/
 132   int best_nclusters;
 133
 134   /**
 135    * Output: Cluster centers
 136    **/
 137   float[][] cluster_centres;
 138
 139   /**
 140    *
 141    **/
 142   float[][] attributes;
 143
 144   int numObjects;
 145
 146   int numAttributes;
 147
 148   public KMeans() {
 149     max_nclusters = 13;
 150     min_nclusters = 4;
 151     isBinaryFile = 0;
 152     use_zscore_transform = 1;
 153     threshold = (float) 0.001;
 154     best_nclusters = 0;
 155   }
 156
 157   /*
 158   public KMeans(int threadid, GlobalArgs g_args) {
 159     this.threadid = threadid;
 160     this.g_args = g_args;
 161   }
 162   */
 163
 164   public KMeans(int threadid, GlobalArgs g_args, int nthreads, int use_zscore_transform,
 165       int max_nclusters, int min_nclusters, float threshold,
 166       float[][] attributes, int numObjects, int numAttributes) {
 167     this.threadid = threadid;
 168     this.g_args = g_args;
 169     //this.nthreads = nthreads;
 170     //this.use_zscore_transform = use_zscore_transform;
 171     //this.max_nclusters = max_nclusters;
 172     //this.min_nclusters = min_nclusters;
 173     //this.threshold = threshold;
 174     //this.attributes = attributes;
 175     //this.numObjects = numObjects;
 176     //this.numAttributes = numAttributes;
 177   }
 178
 179   public void run() {
 180     Barrier barr = new Barrier("128.195.136.162");
 181     int id;
 182     GlobalArgs tmp_g_args;
 183     atomic {
 184       id = threadid;
 185       tmp_g_args = g_args;
 186       short[] offsets = new short[4];
 187       offsets[0] = getoffset{GlobalArgs, clusters};
 188       offsets[1] = (short) 0;
 189       offsets[2] = (short) 0;
 190       offsets[3] = (short) min_nclusters;
 191       System.rangePrefetch(g_args, offsets);
 192     }
 193     //Add Manual prefetch for
 194     //args.clusters[0-> nclusters]
 195         while(true) {
 196       Barrier.enterBarrier(barr);
 197       Normal.work(id, tmp_g_args);
 198       Barrier.enterBarrier(barr);
 199     }
 200   }
 201
 202   /* =============================================================================
 203    * main
 204    * =============================================================================
 205    */
 206   public static void main(String[] args) {
 207     int nthreads;
 208     int MAX_LINE_LENGTH = 1000000; /* max input is 400000 one digit input + spaces */
 209     int[] mid = new int[8];
 210     mid[0] = (128<<24)|(195<<16)|(136<<8)|162; //dc-1.calit2
 211     mid[1] = (128<<24)|(195<<16)|(136<<8)|163; //dc-2.calit2
 212     mid[2] = (128<<24)|(195<<16)|(136<<8)|164; //dc-3.calit2
 213     mid[3] = (128<<24)|(195<<16)|(136<<8)|165; //dc-4.calit2
 214     mid[4] = (128<<24)|(195<<16)|(136<<8)|166; //dc-5.calit2
 215     mid[5] = (128<<24)|(195<<16)|(136<<8)|167; //dc-6.calit2
 216     mid[6] = (128<<24)|(195<<16)|(136<<8)|168; //dc-7.calit2
 217     mid[7] = (128<<24)|(195<<16)|(136<<8)|169; //dc-8.calit2
 218
 219
 220     /**
 221      * Read options fron the command prompt
 222      **/
 223     KMeans kms;
 224     kms = new KMeans();
 225     KMeans.parseCmdLine(args, kms);
 226     nthreads = kms.nthreads;
 227     System.out.println("nthreads= " + kms.nthreads);
 228
 229     /* Initiate Barriers */
 230     BarrierServer mybarr;
 231
 232     atomic {
 233       mybarr = global new BarrierServer(nthreads);
 234     }
 235     mybarr.start(mid[0]);
 236
 237
 238     if (kms.max_nclusters < kms.min_nclusters) {
 239       System.out.println("Error: max_clusters must be >= min_clusters\n");
 240       System.exit(0);
 241     }
 242
 243     float[][] buf;
 244     float[][] attributes;
 245     int numAttributes = 0;
 246     int numObjects = 0;
 247
 248     /*
 249      * From the input file, get the numAttributes (columns in txt file) and numObjects (rows in txt file)
 250      */
 251     if (kms.isBinaryFile == 1) {
 252       System.out.println("TODO: Unimplemented Binary file option\n");
 253       System.exit(0);
 254     }
 255
 256     FileInputStream inputFile = new FileInputStream(kms.filename);
 257     byte b[] = new byte[MAX_LINE_LENGTH];
 258     int n;
 259     while ((n = inputFile.read(b)) != 0) {
 260       for (int i = 0; i < n; i++) {
 261         if (b[i] == '\n')
 262           numObjects++;
 263       }
 264     }
 265     inputFile.close();
 266     inputFile = new FileInputStream(kms.filename);
 267     String line = null;
 268     if((line = inputFile.readLine()) != null) {
 269       int index = 0;
 270       boolean prevWhiteSpace = true;
 271       while(index < line.length()) {
 272         char c = line.charAt(index++);
 273         boolean currWhiteSpace = Character.isWhitespace(c);
 274         if(prevWhiteSpace && !currWhiteSpace){
 275           numAttributes++;
 276         }
 277         prevWhiteSpace = currWhiteSpace;
 278       }
 279     }
 280     inputFile.close();
 281
 282     /* Ignore the first attribute: numAttributes = 1; */
 283     numAttributes = numAttributes - 1;
 284
 285     /* Allocate new shared objects and read attributes of all objects */
 286     float[][] tmp_buf;
 287     atomic {
 288       buf = global new float[numObjects][numAttributes];
 289       attributes = global new float[numObjects][numAttributes];
 290       tmp_buf = buf;
 291     }
 292     KMeans.readFromFile(inputFile, kms.filename, tmp_buf, MAX_LINE_LENGTH);
 293     System.out.println("Finished Reading from file ......");
 294
 295     /*
 296      * The core of the clustering
 297      */
 298
 299     int len = kms.max_nclusters - kms.min_nclusters + 1;
 300
 301     int nloops = 1;
 302
 303     KMeans[] km;
 304     GlobalArgs g_args;
 305     atomic {
 306       km = global new KMeans[nthreads];
 307       g_args = global new GlobalArgs();
 308       g_args.nthreads = nthreads;
 309       for(int x = 0; x < numObjects; x++) {
 310         for(int y = 0; y < numAttributes; y++) {
 311           attributes[x][y] = buf[x][y];
 312         }
 313       }
 314     }
 315
 316     atomic {
 317       /* Create and Start Threads */
 318       for(int i = 1; i<nthreads; i++) {
 319         km[i] = global new KMeans(i, g_args, nthreads, kms.use_zscore_transform,
 320             kms.max_nclusters, kms.min_nclusters, kms.threshold, attributes, numObjects, numAttributes);
 321       }
 322     }
 323
 324     KMeans tmp;
 325
 326     boolean waitfordone=true;
 327     while(waitfordone) {
 328       atomic {
 329         if (mybarr.done)
 330           waitfordone=false;
 331       }
 332     }
 333
 334     for(int i = 1; i<nthreads; i++) {
 335       atomic {
 336         tmp = km[i];
 337       }
 338       tmp.start(mid[i]);
 339     }
 340
 341     System.out.println("Finished Starting threads......");
 342
 343     for (int i = 0; i < nloops; i++) {
 344       //
 345       // Since zscore transform may perform in cluster() which modifies the
 346       // contents of attributes[][], we need to re-store the originals
 347       //
 348       float[][] tmp_attributes;
 349       GlobalArgs tmp_g_args;
 350       atomic {
 351         for(int x = 0; x < numObjects; x++) {
 352           for(int y = 0; y < numAttributes; y++) {
 353             attributes[x][y] = buf[x][y];
 354           }
 355         }
 356         tmp_attributes = attributes;
 357         tmp_g_args = g_args;
 358       }
 359
 360
 361       Cluster.cluster_exec(nthreads,
 362           numObjects,
 363           numAttributes,
 364           tmp_attributes,             // [numObjects][numAttributes]
 365           kms,                    //main class that holds users inputs from command prompt and output arrays that need to be filled
 366           tmp_g_args);                // Global arguments common to all threads
 367     }
 368
 369     System.out.println("Printing output......");
 370     System.out.println("Best_nclusters= " + kms.best_nclusters);
 371
 372     /* Output: the coordinates of the cluster centres */
 373
 374     /*
 375     {
 376       for (int i = 0; i < kms.best_nclusters; i++) {
 377         System.out.print(i + " ");
 378         for (int j = 0; j < numAttributes; j++) {
 379           System.out.print(kms.cluster_centres[i][j] + " ");
 380         }
 381         System.out.println("\n");
 382       }
 383     }
 384     */
 385
 386     System.out.println("Finished......\n");
 387     System.exit(0);
 388   }
 389
 390   public static void parseCmdLine(String args[], KMeans km) {
 391     int i = 0;
 392     String arg;
 393     while (i < args.length && args[i].startsWith("-")) {
 394       arg = args[i++];
 395       //check options
 396       if(arg.equals("-m")) {
 397         if(i < args.length) {
 398           km.max_nclusters = new Integer(args[i++]).intValue();
 399         }
 400       } else if(arg.equals("-n")) {
 401         if(i < args.length) {
 402           km.min_nclusters = new Integer(args[i++]).intValue();
 403         }
 404       } else if(arg.equals("-t")) {
 405         if(i < args.length) {
 406           km.threshold = (float) Double.parseDouble(args[i++]);
 407         }
 408       } else if(arg.equals("-i")) {
 409         if(i < args.length) {
 410           km.filename = args[i++];
 411         }
 412       } else if(arg.equals("-b")) {
 413         if(i < args.length) {
 414           km.isBinaryFile = new Integer(args[i++]).intValue();
 415         }
 416       } else if(arg.equals("-z")) {
 417         km.use_zscore_transform=0;
 418       } else if(arg.equals("-nthreads")) {
 419         if(i < args.length) {
 420           km.nthreads = new Integer(args[i++]).intValue();
 421         }
 422       } else if(arg.equals("-h")) {
 423         km.usage();
 424       }
 425     }
 426     if(km.nthreads == 0 || km.filename == null) {
 427       km.usage();
 428     }
 429   }
 430
 431   /**
 432    * The usage routine which describes the program options.
 433    **/
 434   public void usage() {
 435     System.out.println("usage: ./kmeans -m <max_clusters> -n <min_clusters> -t <threshold> -i <filename> -nthreads <threads>\n");
 436     System.out.println(                   "  -i filename:     file containing data to be clustered\n");
 437     System.out.println(                   "  -b               input file is in binary format\n");
 438     System.out.println(                   "  -m max_clusters: maximum number of clusters allowed\n");
 439     System.out.println(                   "  -n min_clusters: minimum number of clusters allowed\n");
 440     System.out.println(                   "  -z             : don't zscore transform data\n");
 441     System.out.println(                   "  -t threshold   : threshold value\n");
 442     System.out.println(                   "  -nthreads      : number of threads\n");
 443   }
 444
 445   /**
 446    * readFromFile()
 447    * Read attributes from the input file into an array
 448    **/
 449   public static void readFromFile(FileInputStream inputFile, String filename, float[][] buf, int MAX_LINE_LENGTH) {
 450     inputFile = new FileInputStream(filename);
 451     int j;
 452     int i = 0;
 453
 454     byte b[] = new byte[MAX_LINE_LENGTH];
 455     int n;
 456     byte oldbytes[]=null;
 457
 458     atomic {
 459       j = -1;
 460       while ((n = inputFile.read(b)) != 0) {
 461         int x=0;
 462
 463         if (oldbytes!=null) {
 464           //find space
 465           boolean cr=false;
 466           for (;x < n; x++) {
 467             if (b[x] == ' ')
 468               break;
 469             if(b[x] =='\n') {
 470               cr=true;
 471               break;
 472             }
 473           }
 474           byte newbytes[]= new byte[x+oldbytes.length];
 475           boolean isnumber=false;
 476           for(int ii=0;ii<oldbytes.length;ii++) {
 477             if (oldbytes[ii]>='0'&&oldbytes[ii]<='9')
 478               isnumber=true;
 479             newbytes[ii]=oldbytes[ii];
 480           }
 481           for(int ii=0;ii<x;ii++) {
 482             if (b[ii]>='0'&&b[ii]<='9')
 483               isnumber=true;
 484             newbytes[ii+oldbytes.length]=b[ii];
 485           }
 486           if(x!=n)
 487             x++; //skip past space
 488           if(isnumber) {
 489             if (j>=0) {
 490               buf[i][j]=(float)Double.parseDouble(new String(newbytes, 0, newbytes.length));
 491             }
 492             j++;
 493           }
 494           if(cr) {
 495             j=-1;
 496             i++;
 497           }
 498           oldbytes=null;
 499         }
 500
 501         while (x < n) {
 502           int y=x;
 503           boolean cr=false;
 504           boolean isnumber=false;
 505           for(y=x;y<n;y++) {
 506             if ((b[y]>='0')&&(b[y]<='9'))
 507               isnumber=true;
 508             if (b[y]==' ')
 509               break;
 510             if (b[y]=='\n') {
 511               cr=true;
 512               break;
 513             }
 514           }
 515           if (y==n) {
 516             //need to continue for another read
 517             oldbytes=new byte[y-x];
 518             for(int ii=0;ii<(y-x);ii++)
 519               oldbytes[ii]=b[ii+x];
 520             break;
 521           }
 522           //otherwise x is beginning of character string, y is end
 523           if (isnumber) {
 524             if (j>=0) {
 525               buf[i][j]=(float)Double.parseDouble(new String(b,x,y-x));
 526             }
 527             j++;
 528           }
 529           if(cr) {
 530             i++;//skip to next line
 531             j = -1;//don't store line number
 532             x=y;//skip to end of number
 533             x++;//skip past return
 534           } else {
 535             x=y;//skip to end of number
 536             x++;//skip past space
 537           }
 538         }
 539       }
 540     }
 541     inputFile.close();
 542   }
 543 }
 544 /* =============================================================================
 545  *
 546  * End of kmeans.java
 547  *
 548  * =============================================================================
 549  */