Assignment #4 - Parallel Data Processing on Threads

Due by 11:59pm, Monday, November 11.

You earn 5% bonus if you make your last (therefore final) turn-in by 11:59pm, Friday, November 8. You earn 10% bonus if you make your last turn-in by 11:59pm, Wednesday, November 6.

Please direct your questions to the TA about this assignment.

Assignment Overview:

If the dataset can fit into a single machine's memory, it is feasible to perform parallel data processing on a multicore machine. In this assignment, you will program four parallel data processing applications using threads. Three of the applications are the same ones that you implemented using Hadoop in Assignment #2. The goal of this assignment is to allow you gain practical experience on threads-based parallel data processing and contrast with your experience on Hadoop programming.

You can complete this assignment using either Java or C/C++ threads. Given your recent experience with Hadoop programming, we expect that many of you will program in Java threads. There are many online information and tutorials on Java programming, including Java Threads and Java Concurrency Tutorial. If needed, you should be able to find more online information on your own. Note that for big data processing, you will likely have to run your Java program with a very large heap, which can be done with the -Xmx2g option.

Implementation and Experimental Platform:

To allow you experience parallel data processing at a significant scale, we have acquired a 24-core machine---node2x12x1a---to be used for this assignment. Note that since all of you will be sharing one machine, please do not run more than 16 threads in your testing and experiments. More information on sharing the machine is provided later in the assignment description.

A critical issue about this machine is that it does not have NFS mounting. In other words, you will not see the files in your CS account there. You will be using the machine's local disk in this assignment. There are several important implications:

  1. Files will have to be moved in and out using scp.
  2. TURNIN doesn't work directly on the machine. You must copy out your files to a normal CS machine to do TURNIN.
  3. Data on the machine's local disk is not automatically backed up. Though the chance of disk failure during the next 2-3 weeks is small, it is prudent to manually back up valuable data (by copying them to your normal CS account) once in a while.
  4. We will remove your data on this machine shortly after the assignment ends. So please copy out your data as soon as you finish this assignment.

Applications:

You are asked to implement the follow four applications in this assignment:
  1. Word Count
    The input to your word count program will be one or more text files. You should count the number of files each word appears in. Your word identification should be case-insensitive and ignore anything that isn't a letter. You can use the dataset at /localdisk/cs576/input/gutenberg/* for testing.
  2. Matrix-Vector Multiplication
    Matrix-vector multiplication takes a file describing a matrix as an input and has to also load a file with a vector. Both files are text files with one entry per line. The matrix file has an integer row, a space, an integer column, a space, and a floating point value for that location in the matrix. The rows and columns are numbered starting from 1, not 0. The vector file is simply one floating point value per line. The vector and matrix files can be found at /localdisk/cs576/input/matrix.1 and /localdisk/cs576/input/vector.dat.
  3. Matrix-Matrix Multiplication
    Matrix-matrix multiplication multiplies two input matrices and produces a result matrix. For testing, you can multiply the matrix at /localdisk/cs576/input/matrix.1 by itself.
  4. K-means
    The data file for k-means is a text file with one point per line. The X and Y coordinates are separated by a tab. The coordinates are both integers and range from 0 to 1048576 (2^20). The TA's program was designed to stop after the centers moved less than 10 units each, or 50 units total. A set of points to use as input can be found at /localdisk/cs576/input/points.txt. It was generated at random in 5 clusters.

Approach and Performance:

Since you already have a Hadoop/MapReduce implementation for most of the applications, the easiest way to complete this assignment is probably to reuse your previous code and then realize MapReduce control and data transfer in threads. Specifically, you can run parallel threads for the map() tasks. Then you can join the map() threads when they are done. And finally you can use a main thread to collect all the map() results and perform all the reduce() tasks.

While the above approach provides a correct solution, its performance can be further improved. For instance, you may distribute the work of reduce() tasks to multiple threads. You may also try to enable more efficient, dynamic thread synchronizations. You may find that your best performance is not realized at the highest thread count---e.g., the runtime at 8 threads may be shorter than the runtime at 16 threads. Please clearly specify, in your README file, the best performance (shortest runtime) for each of your four applications as well as the thread count to realize the best performance.

Your performance grade will be based on two factors---how your performance compares to the TA's reference implementation, and how your performance compares to those of your follow students. We will use our discretion in assigning the specific performance grades. We will try our best to reward your efforts, if successful, on improving the performance.

Courtesy of Sharing A Machine:

In order to test your program and ensure that others can test their programs, you must pay attention to what jobs are running on the machine. You can do this by using top or ps -ef commands. Please do not run more than 16 threads in your testing and experiments. Note that correctness testing oftentimes does not require a large number of threads. Please limit your large-scale (a large number of threads) testing as much as possible. When you have to run large-scale performance tests, please watch out for others' uses of the machine at the same time.

All of you will be sharing the local disk on the machine. Please use the disk space in a measured way. In particular, please try to limit your disk space usage under 2GB, which should be sufficient for this assignment. Note again that your use of the machine is temporary (for the purpose of this assignment only) and we will remove your data on this machine shortly after the assignment ends.

Turn-in:

You are asked to turn in your source files, a Makefile that compiles/builds your program, and a README file. The README file should be in plain text format. It should contain a description of your design, what is and what is not realized in your implementation. The README file should also clearly specify the best performance (shortest runtime) for each of your four applications as well as the thread count to realize the best performance.

You should electronically turn in the required files. Instructions for electronic turn-in can be found on the course Web site. Since you must copy out your files to run TURNIN at a normal CS machine, please be very careful not to miss any files in your turnin.

Grading guideline:

By turning in early, you help relieve the congestion of using the shared cluster and therefore we strongly encourage that.

Late turn-in policy:

Late turn-ins will be accepted for up to three days, with 10% penalty for each late day. No turn-ins more than three-day late will be accepted.