CSCI 5451 Assignment 1: Parallel Architecture and Communication

// filestats.c : provides a useful routine for parsing some input data
// files in C, particularly the file used in the K-Means program.

#include <stdio.h>
#include <ctype.h>  // for isspace() etc.

int filestats(char *filename, ssize_t *tot_tokens, ssize_t *tot_lines){
// Sets number of lines and total number of whitespace separated
// tokens in the file. Returns -1 if file can't be opened, 0 on
// success.
//
// EXAMPLE: int ret = filestats("digits_all_1e1.txt", &toks, &lines);
// toks  is now 7860 : 10 lines with 786 tokens per line, label + ":" + 28x28 pixels
// lines is now 10   : there are 10 lines in the file
  FILE *fin = fopen(filename,"r");
  if(fin == NULL){
    printf("Failed to open file '%s'\n",filename);
    return -1;
  }

  ssize_t ntokens=0, nlines=0, column=0;
  int intoken=0, token;
  while((token = fgetc(fin)) != EOF){
    if(token == '\n'){          // reached end of line
      column = 0;
      nlines++;
    }
    else{
      column++;
    }
    if(isspace(token) && intoken==1){ // token to whitespace
      intoken = 0;
    }
    else if(!isspace(token) && intoken==0){ // whitespace to token
      intoken = 1;
      ntokens++;
    }
  }
  if(column != 0){              // didn't end with a newline
    nlines++;                   // add a line on to the count
  }
  *tot_tokens = ntokens;
  *tot_lines = nlines;
  fclose(fin);
  // printf("DBG: tokens: %lu\n",ntokens);
  // printf("DBG: lines: %lu\n",nlines);
  return 0;
}

#!/usr/bin/env python3
#
# usage: kmeans.py <datafile> <nclust> [savedir] [maxiter]

import struct
import sys
import os
import math

class KMData:                      # Data set to be clustered
  ndata    = 0                     # count of data
  dim      = 0                     # dimension of features for data
  features = []                    # pointers to individual features
  assigns  = []                    # cluster to which data is assigned
  labels   = []                    # label for data if available
  nlabels  = []                    # max value of labels +1, number 0,1,...,nlabel0

class KMClust:                     # Cluster information
  nclust   = 0                     # number of clusters, the "k" in kmeans
  dim      = 0                     # dimension of features for data
  features = []                    # 2D indexing for individual cluster center features
  counts   = []                    # number of data in each cluster
  

# Load a data set from the named file. Data should be formatted as a
# text file as:
# 
# 7 :  84 185 159 151  60  36   0   0   0   0   0   0
# 2 :   0  77 251 210  25   0   0   0 122 248 253  65
# 1 :   0   0   0   0   0   0   0   0   0  45 244 150
# 0 :   0   0   0   0 110 190 251 251 251 253 169 109
# 4 :   0   0   0   4 195 231   0   0   0   0   0   0
# 1 :   0   0   0   0   0   0   0   0   0  81 254 254
# 4 :   0  20 189 253 147   0   0   0   0   0   0   0
# 9 :   0   0   0   0  91 224 253 253  19   0   0   0
# 5 :   0   0   0   0   0   0  63 253 253 253 253 253
# 9 :   0   0   0   0   0   0   0  36  56 137 201 199
#
# with the lead number being an optional correct label for the data
# and remaining numbers being floating point values that are space
# separated which are the feature vector for each data. The abve
# example does not have any fractional values for features but it
# could.
def kmdata_load(datafile):
  data = KMData()
  with open(datafile,"r") as fin:
    for line in fin:
      data.ndata += 1
      tokens = line.split()
      data.labels.append(int(tokens[0]))
      feats = []
      for f in tokens[2:]:
        feats.append(float(f))
      data.features.append(feats)
  
  data.dim = len(data.features[0])
  data.nlabels = max(data.labels)+1
  return data

# Allocate space for clusters in an object
def kmclust_new(nclust, dim):
  clust = KMClust()
  clust.nclust = nclust
  clust.dim = dim
  for c in range(nclust):
    clust.features.append([0.0] * dim)
    clust.counts.append(0)
  return clust
  

# Save clust centers in the PGM (portable gray map) image format;
# plain text and can be displayed in many image viewers. File names re
# cent_0000.pgm and so on.
def save_pgm_files(clust,savedir):
  dim_root = int(math.sqrt(clust.dim))
  if clust.dim % dim_root == 0:                    # check if this looks like a square image
    print(f"Saving cluster centers to {savedir}/cent_0000.pgm ...")
    maxfeat = max(map(max,clust.features))
    for c in range(clust.nclust):
      outfile=f"{savedir}/cent_{c:04}.pgm"
      with open(outfile,"w") as pgm:               # output the cluster centers as
        print("P2",file=pgm)                       # pgm files, a simple image format which
        print(f"{dim_root} {dim_root}",file=pgm)   # can be viewed in most image
        print(f"{maxfeat:.0f}",file=pgm)           # viewers to show how the cluster center
        for d in range(clust.dim):                 # actually appears; nomacs is a good viwer
          if d > 0 and d%dim_root == 0:
            print(file=pgm)
          print(f"{clust.features[c][d]:3.0f} ",end="",file=pgm)
        print(file=pgm)

#### MAIN FUNCTION ####
def main():
  if len(sys.argv) < 3:
    sys.exit("usage: kmeans.py <datafile> <nclust> [savedir] [maxiter]")
  
  datafile = sys.argv[1]
  nclust = int(sys.argv[2])
  savedir = "."
  MAXITER = 100                        # bounds the iterations
  
  if len(sys.argv) > 3:                # create save directory if specified
    savedir = sys.argv[3]
    os.system(f"mkdir -p {savedir}")
  
  if len(sys.argv) > 4:
    MAXITER = int(sys.argv[4])
  
  print("datafile:",datafile)
  print("nclust:",nclust)
  print("savedir:",savedir)
  

  data = kmdata_load(datafile)         # read in the data file, allocate cluster space
  clust = kmclust_new(nclust, data.dim)

  print("ndata:",data.ndata)
  print("dim:",data.dim)
  print()
  
  for i in range(data.ndata):          # random, regular initial cluster assignment
    c = i % clust.nclust
    data.assigns.append(c)

  for c in range(clust.nclust):
    icount = data.ndata / clust.nclust;
    extra = 0
    if c < (data.ndata % clust.nclust):
      extra = 1                        # extras in earlier clusters
    clust.counts[c] = icount + extra;
  
  
  ################################################################################
  # THE MAIN ALGORITHM
  curiter = 1                          # current iteration
  nchanges = data.ndata                # check for changes in cluster assignment; 0 is converged
  print(f"==CLUSTERING: MAXITER {MAXITER}==")
  print(f"ITER NCHANGE CLUST_COUNTS")
  
  while nchanges > 0 and curiter <= MAXITER: # loop until convergence

    # DETERMINE NEW CLUSTER CENTERS
    for c in range(clust.nclust):      # reset cluster centers to 0.0
      for d in range(clust.dim):
        clust.features[c][d] = 0.0
  
    for i in range(data.ndata):        # sum up data in each cluster
      c = data.assigns[i]
      for d in range(clust.dim):
        clust.features[c][d] += data.features[i][d]
  
    for c in range(clust.nclust):      # divide by ndatas of data to get mean of cluster center
      if clust.counts[c] > 0:
        for d in range(clust.dim):        
          clust.features[c][d] = clust.features[c][d] / clust.counts[c]
        
    # DETERMINE NEW CLUSTER ASSIGNMENTS FOR EACH DATA
    for c in range(clust.nclust):      # reset cluster counts to 0
      clust.counts[c] = 0              # re-init here to support first iteration
  
    nchanges = 0
    for i in range(data.ndata):        # iterate over all data
      best_clust = None
      best_distsq = float("inf")
      for c in range(clust.nclust):    # compare data to each cluster and assign to closest
        distsq = 0.0
        for d in range(clust.dim):     # calculate squared distance to each data dimension
          diff = data.features[i][d] - clust.features[c][d]
          distsq += diff*diff
          # print(f"DBG: curiter {curiter} i {i} c {c} d {d} diff {diff:.6f}")
        if distsq < best_distsq:       # if closer to this cluster than current best
          best_clust = c
          best_distsq = distsq
      clust.counts[best_clust] += 1
      if best_clust != data.assigns[i]:  # assigning data to a different cluster?
        # print(f"DBG: data {i} changing clusters: {data_assign[i]} to {best_clust}")
        nchanges += 1                    # indicate cluster assignment has changed
        data.assigns[i] = best_clust     # assign to new cluster
    
    # Print iteration information at the end of the iter
    print(f"{curiter:3}: {nchanges:5} |", end="") 
    for c in range(nclust):
      print(f" {clust.counts[c]:4}",end="")
    print()
    curiter += 1
  
  # Loop has converged
  if curiter > MAXITER:
    print(f"WARNING: maximum iteration {MAXITER} exceeded, may not have conveged")
  else:
    print(f"CONVERGED: after {curiter} iterations")
  print()
  

  ################################################################################
  # CLEANUP + OUTPUT

  # CONFUSION MATRIX
  confusion = []                         # confusion matrix: labels * clusters big
  for i in range(data.nlabels):
    confusion.append([0] * nclust)
  
  for i in range(data.ndata):            # count which labels in which clusters
    confusion[data.labels[i]][data.assigns[i]] += 1
  
  print("==CONFUSION MATRIX + COUNTS==")
  print("LABEL \ CLUST")
  
  print(f"{'':2} ",end="")               # confusion matrix header
  for j in range(clust.nclust):
    print(f" {j:>4}",end="")
  print(f" {'TOT':>4}")
  
  for i in range(data.nlabels):          # each row of confusion matrix
    print(f"{i:>2}:",end="")
    tot = 0
    for j in range(clust.nclust):
      print(f" {confusion[i][j]:>4}",end="")
      tot += confusion[i][j]
    print(f" {tot:>4}")
  
  print("TOT",end="")                    # final total row of confusion matrix
  tot = 0
  for c in range(clust.nclust):
    print(f" {clust.counts[c]:>4}",end="")
    tot += clust.counts[c]
  print(f" {tot:>4}")
  print()
  
  # LABEL FILE OUTPUT
  outfile = f"{savedir}/labels.txt"    
  print(f"Saving cluster labels to file {outfile}")
  with open(outfile,"w") as fout:
    for i in range(data.ndata):
      print(f"{data.labels[i]:2} {data.assigns[i]:2}",file=fout)
  

  # SAVE PGM FILES CONDITIONALLY
  save_pgm_files(clust,savedir)
### END MAIN ###      
  
main()

# Demo of running the python kmeans clustering on several provided
# data files. The C version you construct should behave similarly.

>> cd kmeans-code

>> ls
filestats.c  kmeans.py	sample-mnist-data

>> chmod u+x kmeans.py

>> ./kmeans.py
usage: kmeans.py <datafile> <nclust> [savedir] [maxiter]

>> ./kmeans.py sample-mnist-data/digits_all_1e2.txt 10 outdir
datafile: sample-mnist-data/digits_all_1e2.txt
nclust: 10
savedir: outdir
ndata: 100
dim: 784

==CLUSTERING: MAXITER 100==
ITER NCHANGE CLUST_COUNTS
  1:    35 |    9   14    9    7   10    6   15   10    8   12
  2:    15 |    8   14    9    6    9    6   16   12    8   12
  3:     8 |    8   15    9    6   10    4   16   15    8    9
  4:     4 |    9   15    9    7   10    4   14   15    8    9
  5:     2 |    9   14    9    7   10    4   14   16    8    9
  6:     0 |    9   14    9    7   10    4   14   16    8    9
CONVERGED: after 7 iterations

==CONFUSION MATRIX + COUNTS==
LABEL \ CLUST
       0    1    2    3    4    5    6    7    8    9  TOT
 0:    0    1    0    4    0    1    0    0    2    0    8
 1:    0    0    0    0    9    0    0    5    0    0   14
 2:    0    3    1    0    0    1    0    3    0    0    8
 3:    4    0    1    0    1    0    0    0    5    0   11
 4:    0    0    3    1    0    1    8    1    0    0   14
 5:    0    0    1    2    0    1    0    2    1    0    7
 6:    0    9    1    0    0    0    0    0    0    0   10
 7:    5    0    0    0    0    0    3    3    0    4   15
 8:    0    1    0    0    0    0    0    1    0    0    2
 9:    0    0    2    0    0    0    3    1    0    5   11
TOT    9   14    9    7   10    4   14   16    8    9  100

Saving cluster labels to file outdir/labels.txt
Saving cluster centers to outdir/cent_0000.pgm ...
>> ls outdir/
cent_0000.pgm  cent_0002.pgm  cent_0004.pgm  cent_0006.pgm  cent_0008.pgm  labels.txt
cent_0001.pgm  cent_0003.pgm  cent_0005.pgm  cent_0007.pgm  cent_0009.pgm
>> ./kmeans.py sample-mnist-data/digits_1x9_2e3.txt 4 two-nine-dir
datafile: sample-mnist-data/digits_1x9_2e3.txt
nclust: 4
savedir: two-nine-dir
ndata: 2000
dim: 784

==CLUSTERING: MAXITER 100==
ITER NCHANGE CLUST_COUNTS
  1:  1398 |  530  393  548  529
  2:   591 |  734  359  369  538
  3:   180 |  738  397  294  571
  4:   119 |  674  423  322  581
  5:    86 |  612  435  379  574
  6:    68 |  563  444  423  570
  7:    54 |  522  451  462  565
  8:    33 |  501  456  480  563
  9:    17 |  488  458  490  564
 10:     8 |  481  459  496  564
 11:     5 |  476  459  501  564
 12:     5 |  471  459  506  564
 13:     4 |  468  460  508  564
 14:     5 |  464  461  511  564
 15:     5 |  461  462  514  563
 16:     2 |  460  463  514  563
 17:     1 |  459  463  515  563
 18:     1 |  458  463  516  563
 19:     0 |  458  463  516  563
CONVERGED: after 20 iterations

==CONFUSION MATRIX + COUNTS==
LABEL \ CLUST
       0    1    2    3  TOT
 0:    0    0    0    0    0
 1:    1  450    1  548 1000
 2:    0    0    0    0    0
 3:    0    0    0    0    0
 4:    0    0    0    0    0
 5:    0    0    0    0    0
 6:    0    0    0    0    0
 7:    0    0    0    0    0
 8:    0    0    0    0    0
 9:  457   13  515   15 1000
TOT  458  463  516  563 2000

Saving cluster labels to file two-nine-dir/labels.txt
Saving cluster centers to two-nine-dir/cent_0000.pgm ...
>> ls two-nine-dir/
cent_0000.pgm  cent_0001.pgm  cent_0002.pgm  cent_0003.pgm  labels.txt