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.
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
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
Implementation and Experimental Platform:
To allow you experience parallel data processing at a significant scale,
we have acquired a 24-core machine---
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:
- Files will have to be moved in and out using
- TURNIN doesn't work directly on the machine. You must copy out your
files to a normal CS machine to do TURNIN.
- 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.
- 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
You are asked to implement the follow four applications in this assignment:
- 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
- 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
- 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.
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
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
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
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.
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.
By turning in early, you help relieve the congestion of using the shared cluster
and therefore we strongly encourage that.
- 40%: correctness of your solution. This is equally split across the
- 40%: performance of your solution. This is also equally split
across the four applications.
- 20%: a working Makefile, a clear README file, clarity of your source code
and completeness of your comments.
- 5% bonus for those who make their last turn-in by three days in advance.
- 10% bonus for those who make their last turn-in by five days in advance.
Late turn-in policy:
Late turn-ins will be accepted for up to three days, with 10% penalty for each
No turn-ins more than three-day late will be accepted.