# HG changeset patch
# User Merten Sach <msach@mailbox.tu-berlin.de>
# Date 1317128882 -7200
# Node ID 0ce47c784647203de67e8e8ad5f1e438f004f47a

Initial commit

diff -r 000000000000 -r 0ce47c784647 .hgignore
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/.hgignore	Tue Sep 27 15:08:02 2011 +0200
@@ -0,0 +1,9 @@
+syntax: glob
+
+histograms
+kmeans
+out
+nbproject
+c-ray-mt
+*.ppm
+*.o
diff -r 000000000000 -r 0ce47c784647 Makefile
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/Makefile	Tue Sep 27 15:08:02 2011 +0200
@@ -0,0 +1,42 @@
+CC = gcc
+CFLAGS = -m64 -ffast-math -fwrapv -fno-omit-frame-pointer -O3 -D SSR -D APPLICATION=KMEANS -g -Wall
+LDFLAGS = 
+
+LIBS = -lm -lpthread
+TARGET = kmeans
+OBJ = 	\
+	SSR_lib/VMS/Histogram/Histogram.o \
+	SSR_lib/VMS/Histogram/FloatHist.o \
+	SSR_lib/VMS/CoreLoop.o \
+	SSR_lib/VMS/VMS.o \
+	SSR_lib/VMS/MasterLoop.o \
+	SSR_lib/VMS/Queue_impl/PrivateQueue.o \
+	SSR_lib/VMS/Hash_impl/PrivateHash.o \
+	SSR_lib/VMS/DynArray/DynArray.o \
+	SSR_lib/SSR_PluginFns.o \
+	SSR_lib/SSR_lib.o \
+	SSR_lib/VMS/Histogram/DblHist.o \
+	SSR_lib/SSR.o \
+	SSR_lib/VMS/probes.o \
+	SSR_lib/VMS/ProcrContext.o \
+	SSR_lib/SSR_Request_Handlers.o \
+	SSR_lib/VMS/Hash_impl/MurmurHash2.o \
+	SSR_lib/VMS/vmalloc.o \
+	SSR_lib/VMS/contextSwitch.o \
+	SSR_lib/VMS/Queue_impl/BlockingQueue.o \
+	SSR_lib/VMS/vutilities.o \
+	wtime.o \
+        file_io.o \
+	kmeans.o \
+	main.o 
+
+all: $(TARGET)
+
+$(TARGET): $(OBJ)
+	$(CC) -o $@ $(OBJ) $(LDFLAGS) $(LIBS)
+	
+%.o : %.c
+	$(CC) -c $(CFLAGS) -o $@ $<
+
+clean:
+	rm -f $(OBJ) $(TARGET)
diff -r 000000000000 -r 0ce47c784647 README.txt
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/README.txt	Tue Sep 27 15:08:02 2011 +0200
@@ -0,0 +1,22 @@
+Kernel: k-means Clustering
+
+This is a kernel-type benchmark of a simple off-line clustering algorithm. Careful: Hash Checksum Verification of the benchmark output is not feasible for kmeans. Usage of the float data type leads to imprecisions, caused by threading, up to the fifth place after the decimal point in the results.
+
+Installation:
+
+To install the kernel benchmark, navigate to the directory this file is located in, open up a terminal and simply type 'make'. For certain architectures 
+or special compilation options, you might need to change compilation parameters in the makefile.
+
+Usage:
+
+You may execute the benchmark by navigating to this directory after compilation and typing
+
+./kmeans -b -i <input filename> -n <cluster center count>
+
+The specification of the number of threads used to perform the clustering process depends on the parallel programming model.
+
+Benchmark versions:
+
+Serial
+POSIX Threads
+OpenMP SuperScalar
diff -r 000000000000 -r 0ce47c784647 color
Binary file color has changed
diff -r 000000000000 -r 0ce47c784647 edge
Binary file edge has changed
diff -r 000000000000 -r 0ce47c784647 file_io.c
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/file_io.c	Tue Sep 27 15:08:02 2011 +0200
@@ -0,0 +1,162 @@
+/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
+/*   File:         file_io.c                                                 */
+/*   Description:  This program reads point data from a file                 */
+/*                 and write cluster output to files                         */
+/*   Input file format:                                                      */
+/*                 ascii  file: each line contains 1 data object             */
+/*                 binary file: first 4-byte integer is the number of data   */
+/*                 objects and 2nd integer is the no. of features (or        */
+/*                 coordinates) of each object                               */
+/*                                                                           */
+/*   Author:  Wei-keng Liao                                                  */
+/*            ECE Department Northwestern University                         */
+/*            email: wkliao@ece.northwestern.edu                             */
+/*   Copyright, 2005, Wei-keng Liao                                          */
+/*                                                                           */
+/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
+
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>     /* strtok() */
+#include <sys/types.h>  /* open() */
+#include <sys/stat.h>
+#include <fcntl.h>
+#include <unistd.h>     /* read(), close() */
+
+#include "kmeans.h"
+
+#define MAX_CHAR_PER_LINE 128
+
+
+/*
+*	Function: file_read
+*	-------------------
+*	Function for loading input data into memory.
+*/
+double** file_read(int   isBinaryFile,  /* flag: 0 or 1 */
+                  char *filename,      /* input file name */
+                  int  *numObjs,       /* count of data objects (local) */
+                  int  *numCoords)     /* count of coordinates */
+{
+    float **objects;
+    int     i, j, len;
+    ssize_t numBytesRead;
+
+    if (isBinaryFile) {  /* input file is in raw binary format -------------*/
+        int infile;
+		fprintf(stderr, "Trying to read from binary file: %s", filename);
+        if ((infile = open(filename, O_RDONLY, "0600")) == -1) {
+            fprintf(stderr, "Error: Input File Not Found\n");
+			exit(EXIT_FAILURE);
+        }
+        numBytesRead = read(infile, numObjs, sizeof(int));
+        assert(numBytesRead == sizeof(int));
+        numBytesRead = read(infile, numCoords, sizeof(int));
+        assert(numBytesRead == sizeof(int));
+
+        /* allocate space for objects[][] and read all objects */
+        len = (*numObjs) * (*numCoords);
+        objects    = (float**)malloc((*numObjs) * sizeof(float*));
+        objects[0] = (float*) malloc(len * sizeof(float));
+
+		if(objects == NULL || objects[0] == NULL) {
+			fprintf(stderr, "Could Not Allocate Memory\n");
+			exit(EXIT_FAILURE);
+		}
+
+        for (i = 1; i < (*numObjs); i++)
+            objects[i] = objects[i-1] + (*numCoords);
+
+        numBytesRead = read(infile, objects[0], len*sizeof(float));
+        assert(numBytesRead == len*sizeof(float));
+		fprintf(stderr, " ... Input read successfully!\n");
+        close(infile);
+
+    } else {  /* input file is in ASCII format -------------------------------*/
+        FILE *infile;
+        char *line, *ret;
+        int   lineLen;
+
+		fprintf(stderr, "Trying to read from ASCII file: %s", filename);
+		if ((infile = fopen(filename, "r")) == NULL) {
+            fprintf(stderr, "Error: Input File Not Found\n");
+			exit(EXIT_FAILURE);
+        }
+
+        /* first find the number of objects */
+        lineLen = MAX_CHAR_PER_LINE;
+        line = (char*) malloc(lineLen);
+        assert(line != NULL);
+
+        (*numObjs) = 0;
+        while (fgets(line, lineLen, infile) != NULL) {
+            /* check each line to find the max line length */
+            while (strlen(line) == lineLen-1) {
+                /* this line read is not complete */
+                len = strlen(line);
+                fseek(infile, -len, SEEK_CUR);
+
+                /* increase lineLen */
+                lineLen += MAX_CHAR_PER_LINE;
+                line = (char*) realloc(line, lineLen);
+                assert(line != NULL);
+
+                ret = fgets(line, lineLen, infile);
+                assert(ret != NULL);
+            }
+
+            if (strtok(line, " \t\n") != 0)
+                (*numObjs)++;
+        }
+        rewind(infile);
+
+        /* find the no. objects of each object */
+        (*numCoords) = 0;
+        while (fgets(line, lineLen, infile) != NULL) {
+            if (strtok(line, " \t\n") != 0) {
+                /* ignore the id (first coordiinate): numCoords = 1; */
+                while (strtok(NULL, " ,\t\n") != NULL) (*numCoords)++;
+                break; /* this makes read from 1st object */
+            }
+        }
+        rewind(infile);
+
+        /* allocate space for objects[][] and read all objects */
+        len = (*numObjs) * (*numCoords);
+        objects    = (float**)malloc((*numObjs) * sizeof(float*));
+        assert(objects != NULL);
+        objects[0] = (float*) malloc(len * sizeof(float));
+        assert(objects[0] != NULL);
+        for (i=1; i<(*numObjs); i++)
+            objects[i] = objects[i-1] + (*numCoords);
+
+        i = 0;
+        /* read all objects */
+        while (fgets(line, lineLen, infile) != NULL) {
+            if (strtok(line, " \t\n") == NULL) continue;
+            for (j=0; j<(*numCoords); j++)
+                objects[i][j] = atof(strtok(NULL, " ,\t\n"));
+            i++;
+        }
+		fprintf(stderr, " ... Input read successfully!\n");
+        fclose(infile);
+        free(line);
+    }
+
+
+    double** objects_d = (double**)malloc((*numObjs) * sizeof(double*));
+    objects_d[0] = (double*) malloc(len * sizeof(double));
+    for (i = 1; i < (*numObjs); i++)
+        objects_d[i] = objects_d[i-1] + (*numCoords);
+    
+    for (i=0; i< (*numObjs); i++){
+        for (j=0; j<(*numCoords); j++){
+            objects_d[i][j] = objects[i][j];
+        }
+    }
+    free(objects[0]);
+    free(objects);
+
+    return objects_d;
+}
+
diff -r 000000000000 -r 0ce47c784647 kmeans
Binary file kmeans has changed
diff -r 000000000000 -r 0ce47c784647 kmeans.c
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/kmeans.c	Tue Sep 27 15:08:02 2011 +0200
@@ -0,0 +1,340 @@
+/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
+/*   File:         pthreads_kmeans.c  (OpenMP version)                     */
+/*   Description:  Implementation of simple k-means clustering algorithm     */
+/*                 This program takes an array of N data objects, each with  */
+/*                 M coordinates and performs a k-means clustering given a   */
+/*                 user-provided value of the number of clusters (K). The    */
+/*                 clustering results are saved in 2 arrays:                 */
+/*                 1. a returned array of size [K][N] indicating the center  */
+/*                    coordinates of K clusters                              */
+/*                 2. membership[N] stores the cluster center ids, each      */
+/*                    corresponding to the cluster a data object is assigned */
+/*                                                                           */
+/*   Author:  Wei-keng Liao                                                  */
+/*            ECE Department, Northwestern University                        */
+/*            email: wkliao@ece.northwestern.edu                             */
+/*   Copyright, 2005, Wei-keng Liao                                          */
+/*                                                                           */
+/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
+
+#include <stdio.h>
+#include <stdlib.h>
+#include <pthread.h>
+#include <time.h>
+#include <math.h>
+#include "kmeans.h"
+
+#include "SSR_lib/SSR.h"
+
+#define PREC 300
+
+#define START   1
+#define END     2
+
+extern int nthreads; /* Thread count */
+double delta; /* Delta is a value between 0 and 1 describing the percentage of objects which changed cluster membership */
+
+VirtProcr *parentVP;
+
+/*
+*	Struct: input
+*	-------------
+*	Encapsulates all the input data for the benchmark, i.e. the object list,
+*	clustering output and the input statistics.
+*/
+struct input {
+    int t;
+    double local_delta;
+    double **objects;				/* Object list */
+    double  **clusters;       		/* Cluster list, out: [numClusters][numCoords] */
+    int    *membership;				/* For each object, contains the index of the cluster it currently belongs to */
+    int    **local_newClusterSize; 	/* Thread-safe, [nthreads][numClusters] */
+    double ***local_newClusters;    	/* Thread-safe, [nthreads][numClusters][numCoords] */
+    int numObjs,numClusters,numCoords;
+};
+
+/*
+*	Function: euclid_dist_2
+*	-----------------------
+*	Computes the square of the euclidean distance between two multi-dimensional points.
+*/
+__inline static double euclid_dist_2(int numdims, double *coord1, double *coord2) {
+    int i;
+    double ans=0.0;
+
+    for (i=0; i<numdims; i++)
+        ans += (coord1[i]-coord2[i]) * (coord1[i]-coord2[i]);
+
+    return(ans);
+}
+
+/*
+*	Function: find_nearest_cluster
+*	------------------------------
+*	Function determining the cluster center which is closest to the given object.
+*	Returns the index of that cluster center.
+*/
+__inline static int find_nearest_cluster(int numClusters, int numCoords, double *object, double **clusters) {
+    int   index, i;
+    double dist, min_dist;
+    
+    /* find the cluster id that has min distance to object */
+    index    = 0;
+    min_dist = euclid_dist_2(numCoords, object, clusters[0]);
+    for (i=1; i<numClusters; i++) {
+        dist = euclid_dist_2(numCoords, object, clusters[i]);
+    
+        /* no need square root */
+        if (dist < min_dist) { /* find the min and its array index */
+            min_dist = dist;
+            index    = i;
+        }
+    }
+    return index;
+}
+
+void work(struct input *x, VirtProcr *VProc){
+    int tid = x->t;
+    x->local_delta=0;
+    int i;
+    for (i = tid; i < x->numObjs; i += nthreads) {
+        /* find the array index of nearest cluster center */
+        int index = find_nearest_cluster(x->numClusters, x->numCoords,
+                                    x->objects[i], x->clusters);
+
+        /* if membership changes, increase delta by 1 */        
+        if (x->membership[i] != index)
+            x->local_delta += 1.0;
+        /* assign the membership to object i */
+        x->membership[i] = index;
+
+        /* update new cluster centers : sum of all objects located
+        within (average will be performed later) */
+        x->local_newClusterSize[tid][index]++;
+	int j;
+        for (j=0; j < x->numCoords; j++)
+            x->local_newClusters[tid][index][j] += x->objects[i][j];
+
+    }
+    SSR__send_from_to((void*)&x->local_delta, VProc, parentVP);
+}
+
+/*
+*	Function: thread function work
+*	--------------
+*	Worker function for threading. Work distribution is done so that each thread computers
+*/
+void tfwork(void *ip, VirtProcr *VProc)
+{
+    struct input *x;
+    x = (struct input *)ip;    
+    
+    for(;;){
+        if(*((int*)SSR__receive_from_to(parentVP, VProc)) == END)
+            break;
+        else
+            work(x, VProc);
+    }
+    
+    SSR__dissipate_procr(VProc);
+}
+
+/*
+*	Function: create_array_2d_f
+*	--------------------------
+*	Allocates memory for a 2-dim double array as needed for the algorithm.
+*/
+double** create_array_2d_f(int height, int width, VirtProcr *VProc) {
+	double** ptr;
+	int i;
+	ptr = SSR__malloc_to(height * sizeof(double*), VProc);
+	assert(ptr != NULL);
+	ptr[0] = SSR__malloc_to(width * height * sizeof(double), VProc);
+	assert(ptr[0] != NULL);
+	/* Assign pointers correctly */
+	for(i = 1; i < height; i++)
+		ptr[i] = ptr[i-1] + width; 
+	return ptr;
+}
+
+/*
+*	Function: create_array_2Dd_i
+*	--------------------------
+*	Allocates memory for a 2-dim integer array as needed for the algorithm.
+*/
+int** create_array_2d_i(int height, int width, VirtProcr *VProc) {
+	int** ptr;
+	int i;
+	ptr = SSR__malloc_to(height * sizeof(int*), VProc);
+	assert(ptr != NULL);
+	ptr[0] = SSR__malloc_to(width * height * sizeof(int), VProc);
+	assert(ptr[0] != NULL);
+	/* Assign pointers correctly */
+	for(i = 1; i < height; i++)
+		ptr[i] = ptr[i-1] + width; 
+	return ptr;
+}
+
+/*
+*	Function: pthreads_kmeans
+*	-------------------------
+*	Algorithm main function. Returns a 2D array of cluster centers of size [numClusters][numCoords].
+*/
+void kmeans(void *data, VirtProcr *VProc)
+{
+    struct call_data *cluster_data = (struct call_data*)data;
+    //int is_perform_atomic = cluster_data->is_perform_atomic;	/* in: */
+    double **objects      = cluster_data->objects;           	/* in: [numObjs][numCoords] */
+    int     numCoords     = cluster_data->numCoords;         	/* no. coordinates */
+    int     numObjs       = cluster_data->numObjs;           	/* no. objects */
+    int     numClusters   = cluster_data->numClusters;     	/* no. clusters */
+    double  threshold     = cluster_data->threshold;         	/* % objects change membership */
+    int    *membership    = cluster_data->membership;        	/* out: [numObjs] */ 
+
+    int      i, j, k, loop = 0;
+    int     *newClusterSize; /* [numClusters]: no. objects assigned in each
+                                new cluster */
+    double  **clusters    = cluster_data->clusters;       /* out: [numClusters][numCoords] */
+    double  **newClusters;    /* [numClusters][numCoords] */
+    //double   timing;
+    int    **local_newClusterSize; /* [nthreads][numClusters] */
+    double ***local_newClusters;    /* [nthreads][numClusters][numCoords] */
+
+    VirtProcr **tasks;
+    volatile int       syncMsg;
+    
+    parentVP = VProc;
+
+	/* === MEMORY SETUP === */
+
+	/* [numClusters] clusters of [numCoords] double coordinates each */
+        //Set pointers
+        for(i = 1; i < numClusters; i++)
+		clusters[i] = clusters[i-1] + numCoords; 
+
+    /* Pick first numClusters elements of objects[] as initial cluster centers */
+    for (i=0; i < numClusters; i++)
+        for (j=0; j < numCoords; j++)
+            clusters[i][j] = objects[i][j];
+
+    /* Initialize membership, no object belongs to any cluster yet */
+    for (i = 0; i < numObjs; i++) 
+		membership[i] = -1;
+
+	/* newClusterSize holds information on the count of members in each cluster */
+    newClusterSize = (int*)SSR__malloc_to(numClusters * sizeof(int), VProc);
+    assert(newClusterSize != NULL);
+
+	/* newClusters holds the coordinates of the freshly created clusters */
+	newClusters = create_array_2d_f(numClusters, numCoords, VProc);
+	local_newClusterSize = create_array_2d_i(nthreads, numClusters, VProc);
+
+    /* local_newClusters is a 3D array */
+    local_newClusters    = (double***)SSR__malloc_to(nthreads * sizeof(double**), VProc);
+    assert(local_newClusters != NULL);
+    local_newClusters[0] = (double**)SSR__malloc_to(nthreads * numClusters * sizeof(double*), VProc);
+    assert(local_newClusters[0] != NULL);
+
+	/* Set up the pointers */
+    for (i = 1; i < nthreads; i++)
+        local_newClusters[i] = local_newClusters[i-1] + numClusters;
+
+    for (i = 0; i < nthreads; i++) {
+        for (j = 0; j < numClusters; j++) {
+            local_newClusters[i][j] = (double*)SSR__malloc_to(numCoords * sizeof(double), VProc);
+            assert(local_newClusters[i][j] != NULL);
+        }
+    }
+    /* Perform thread setup */
+    tasks = (VirtProcr**)SSR__malloc_to(nthreads * sizeof(VirtProcr*), VProc);
+    
+    struct input *ip = SSR__malloc_to(nthreads * sizeof(struct input), VProc);
+    /* Provide thread-safe memory locations for each worker */
+    for(i = 0; i < nthreads; i++){
+        ip[i].t = i;
+        ip[i].objects=objects;
+        ip[i].clusters=clusters;
+        ip[i].membership=membership;
+        ip[i].local_newClusterSize=local_newClusterSize;
+        ip[i].local_newClusters=local_newClusters;
+        ip[i].numObjs=numObjs;
+        ip[i].numClusters=numClusters;
+        ip[i].numCoords=numCoords;
+
+        if(i!=0)
+            tasks[i] = SSR__create_procr_with(tfwork, (void*)&ip[i], VProc);
+    }
+    
+	/* === COMPUTATIONAL PHASE === */
+    syncMsg = START;
+    do {
+        delta = 0.0;
+        
+        printf("start children 1\n");
+        for(i=0; i<nthreads; i++)
+            SSR__send_from_to((void*)&syncMsg, VProc, tasks[i]);
+        
+        //let the children do the work
+        
+        printf("receive results\n");
+        for(i=0; i<nthreads; i++)
+            delta += *(double*)SSR__receive_from_to(tasks[i],VProc);
+        printf("start children 2\n");
+        for(i=1; i<nthreads; i++)
+            SSR__send_from_to((void*)&syncMsg, VProc, tasks[i]);
+        
+		/* Let the main thread perform the array reduction */
+		for (i = 0; i < numClusters; i++) {
+			for (j = 0; j < nthreads; j++) {
+				newClusterSize[i] += local_newClusterSize[j][i];
+				local_newClusterSize[j][i] = 0.0;
+				for (k = 0; k < numCoords; k++) {
+					newClusters[i][k] += local_newClusters[j][i][k];
+					local_newClusters[j][i][k] = 0.0;
+				}
+			}
+		}
+	
+		/* Average the sum and replace old cluster centers with newClusters */
+		for (i = 0; i < numClusters; i++) {
+			for (j = 0; j < numCoords; j++) {
+				if (newClusterSize[i] > 1)
+				clusters[i][j] = newClusters[i][j] / newClusterSize[i];
+				newClusters[i][j] = 0.0;   /* set back to 0 */
+			}
+			newClusterSize[i] = 0;   /* set back to 0 */
+		}
+		
+		delta /= numObjs;
+    } while (loop++ < PREC && delta > threshold);
+    
+    // Changing to a fixed number of iterations is for benchmarking reasons. I know it affects the results compared to the original program,
+    // but minor double precision floating point inaccuracies caused by threading would otherwise lead to huge differences in computed
+    // iterations, therefore making benchmarking completely unreliable.
+
+    syncMsg = END;
+    for(i=0; i<nthreads; i++)
+            SSR__send_from_to((void*)&syncMsg, VProc, tasks[i]);
+    
+
+    SSR__free(ip, VProc);
+    SSR__free(tasks, VProc);
+
+    SSR__free(local_newClusterSize[0], VProc);
+    SSR__free(local_newClusterSize, VProc);
+        
+    for (i = 0; i < nthreads; i++)
+        for (j = 0; j < numClusters; j++)
+            SSR__free(local_newClusters[i][j], VProc);
+    SSR__free(local_newClusters[0], VProc);
+    SSR__free(local_newClusters, VProc);
+
+    SSR__free(newClusters[0], VProc);
+    SSR__free(newClusters, VProc);
+    SSR__free(newClusterSize, VProc);
+    
+    (cluster_data)->clusters = clusters;
+    
+    SSR__dissipate_procr(VProc);
+}
+
diff -r 000000000000 -r 0ce47c784647 kmeans.h
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/kmeans.h	Tue Sep 27 15:08:02 2011 +0200
@@ -0,0 +1,35 @@
+/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
+/*   File:         kmeans.h   (an OpenMP version)                            */
+/*   Description:  header file for a simple k-means clustering program       */
+/*                                                                           */
+/*   Author:  Wei-keng Liao                                                  */
+/*            ECE Department Northwestern University                         */
+/*            email: wkliao@ece.northwestern.edu                             */
+/*   Copyright, 2005, Wei-keng Liao                                          */
+/*                                                                           */
+/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
+
+#ifndef _H_KMEANS
+#define _H_KMEANS
+
+#include <assert.h>
+#include "SSR_lib/SSR.h"
+
+struct call_data{
+    int is_perform_atomic; 	/* in: */
+    double **objects;          	/* in: [numObjs][numCoords] */
+    int     numCoords;         	/* no. coordinates */
+    int     numObjs;           	/* no. objects */
+    int     numClusters;       	/* no. clusters */
+    double   threshold;         	/* % objects change membership */
+    int    *membership;
+    double **clusters;
+};
+
+void kmeans(void *data, VirtProcr *VProc);
+
+double** file_read(int, char*, int*, int*);
+
+double  wtime(void);
+
+#endif
diff -r 000000000000 -r 0ce47c784647 main.c
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/main.c	Tue Sep 27 15:08:02 2011 +0200
@@ -0,0 +1,169 @@
+/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
+/*   File:         pthreads_main.c   (an OpenMP version)                          */
+/*   Description:  This program shows an example on how to call a subroutine */
+/*                 that implements a simple k-means clustering algorithm     */
+/*                 based on Euclid distance.                                 */
+/*   Input file format:                                                      */
+/*                 ascii  file: each line contains 1 data object             */
+/*                 binary file: first 4-byte integer is the number of data   */
+/*                 objects and 2nd integer is the no. of features (or        */
+/*                 coordinates) of each object                               */
+/*                                                                           */
+/*   Author:  Wei-keng Liao                                                  */
+/*            ECE Department Northwestern University                         */
+/*            email: wkliao@ece.northwestern.edu                             */
+/*   Copyright, 2005, Wei-keng Liao                                          */
+/*                                                                           */
+/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
+
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>     /* strtok() */
+#include <sys/types.h>  /* open() */
+#include <sys/stat.h>
+#include <sys/time.h>
+#include <fcntl.h>
+#include <unistd.h>     /* getopt() */
+#include <time.h>
+#include "kmeans.h"
+
+#include "SSR_lib/SSR.h"
+
+char __ProgrammName[] = "kmeans";
+char __DataSet[255];
+
+#define seconds(tm) gettimeofday(&tp,(struct timezone *)0);\
+   tm=tp.tv_sec+tp.tv_usec/1000000.0
+
+struct timeval tp;
+
+int numClusters, numCoords, numObjs, nthreads;
+
+/*
+*	Function: usage
+*	---------------
+*	Prints information on how to call the program.
+*/
+static void usage(char *argv0) {
+    char *help =
+        "Usage: %s [switches] -i filename -n num_clusters [OPTIONS]\n"
+        "       -i filename    : file containing data to be clustered\n"
+        "       -b             : input file is in binary format (default no)\n"
+        "       -n num_clusters: number of clusters (K must be > 1)\n"
+        "       -p nproc       : number of threads (default 1)\n"
+        "       -o filename    : write output to file\n";
+    fprintf(stderr, help, argv0);
+    exit(-1);
+}
+
+/*---< main() >-------------------------------------------------------------*/
+int main(int argc, char **argv) {
+    int     opt;
+    extern char   *optarg;
+    extern int     optind;
+    int     j;
+    int     isBinaryFile;
+    
+    int    *membership;    /* [numObjs] */
+    char   *filename, *outfile;
+    double **objects;       /* [numObjs][numCoords] data objects */
+    double **clusters;      /* [numClusters][numCoords] cluster center */
+    double   threshold;
+    double  timing, io_timing, clustering_timing;
+    
+    /* some default values */
+    nthreads          = 1;		/* Amount of threads to use */
+    numClusters       = 1;		/* Amount of cluster centers */
+    threshold         = 0.001; 	/* Percentage of objects that need to change membership for the clusting to continue */
+    isBinaryFile      = 0;		/* 0 if the input file is in ASCII format, 1 for binary format */
+    filename          = NULL;	/* Name of the input file */
+	outfile   		  = NULL;	/* Name of the output file */
+
+	/* Parse command line options */
+    while ( (opt=getopt(argc,argv,"o:p:i:n:t:bh"))!= EOF) {
+        switch (opt) {
+            case 'i': filename=optarg;
+                      break;
+            case 'b': isBinaryFile = 1;
+                      break;
+            case 'n': numClusters = atoi(optarg);
+                      break;
+            case 'p': nthreads = atoi(optarg);
+                      break;
+            case 'h': usage(argv[0]);
+                      break;
+			case 'o': outfile=optarg;
+					  break;
+            default: usage(argv[0]);
+                      break;
+        }
+    }
+
+    if (filename == NULL) usage(argv[0]);
+
+	seconds(io_timing);
+
+    /* Read input data points from given input file */
+    objects = file_read(isBinaryFile, filename, &numObjs, &numCoords);
+    assert(objects != NULL);
+
+	seconds(timing);
+	io_timing         = timing - io_timing;
+	clustering_timing = timing;      
+
+    membership = (int*) malloc(numObjs * sizeof(int));
+	assert(membership != NULL);
+        
+    clusters = malloc(numClusters * sizeof(double*));
+    assert(clusters != NULL);
+    clusters[0] = malloc(numClusters * numCoords * sizeof(double));
+    assert(clusters[0] != NULL);
+
+    struct call_data data = { 0, objects, numCoords, numObjs,
+                          numClusters, threshold, membership, clusters };
+    
+    /* Launch the core computation algorithm */
+    SSR__create_seed_procr_and_do_work(kmeans, (void*)&data);
+
+    free(objects[0]);
+    free(objects);
+
+    seconds(timing);
+    clustering_timing = timing - clustering_timing;
+
+    /* Memory cleanup */
+    free(membership);
+
+	if(outfile != NULL) {
+        int l;
+        FILE* fp = fopen(outfile, "w");
+        for(j = 0; j < numClusters; j++) {
+            fprintf(fp, "Cluster %d: ", j);
+            for(l = 0; l < numCoords; l++)
+                fprintf(fp, "%f ", clusters[j][l]);
+            fprintf(fp, "\n");
+        }
+        fclose(fp);
+    }
+
+    free(clusters[0]);
+    free(clusters);
+
+    /* Print performance numbers on stdout */
+	double t1;
+	io_timing += seconds(t1) - timing;
+
+    printf("\n---- kMeans Clustering ----\n");
+    printf("Number of threads = %d\n", nthreads);
+    printf("Input file:     %s\n", filename);
+    printf("numObjs       = %d\n", numObjs);
+    printf("numCoords     = %d\n", numCoords);
+    printf("numClusters   = %d\n", numClusters);
+    printf("threshold     = %.4f\n", threshold);
+
+    printf("I/O time           = %10.4f sec\n", io_timing);
+    printf("Computation timing = %10.4f sec\n", clustering_timing);
+
+    return(0);
+}
+
diff -r 000000000000 -r 0ce47c784647 pthread.txt
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/pthread.txt	Tue Sep 27 15:08:02 2011 +0200
@@ -0,0 +1,23 @@
+kmeans Benchmark
+Input:  color
+
+Workers:  1
+time:  4.30710
+Workers:  2
+time:  2.95336
+Workers:  4
+time:  2.64520
+Workers:  8
+time:  3.01213
+-------------------
+Input:  edge
+
+Workers:  1
+time:  9.44506
+Workers:  2
+time:  5.79456
+Workers:  4
+time:  4.76466
+Workers:  8
+time:  4.35773
+-------------------
diff -r 000000000000 -r 0ce47c784647 wtime.c
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/wtime.c	Tue Sep 27 15:08:02 2011 +0200
@@ -0,0 +1,37 @@
+/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
+/*   File:         wtime.c                                                   */
+/*   Description:  a timer that reports the current wall time                */
+/*                                                                           */
+/*   Author:  Wei-keng Liao                                                  */
+/*            ECE Department Northwestern University                         */
+/*            email: wkliao@ece.northwestern.edu                             */
+/*   Copyright, 2005, Wei-keng Liao                                          */
+/*                                                                           */
+/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
+
+#include <sys/time.h>
+#include <stdio.h>
+#include <stdlib.h>
+
+/*
+*	Function: wtime
+*	---------------
+*	Provides a millisecond-resolution timer for measurement purposes.
+*/
+double wtime(void) 
+{
+    double          now_time;
+    struct timeval  etstart;
+    struct timezone tzp;
+
+    if (gettimeofday(&etstart, &tzp) == -1) {
+		fprintf(stderr, "Timing Error: Could Not Get Current Time\n");
+		exit(EXIT_FAILURE);
+	}
+
+    now_time = ((double)etstart.tv_sec) +              /* in seconds */
+               ((double)etstart.tv_usec) / 1000000.0;  /* in microseconds */
+    return now_time;
+}
+
+