Assignment
Project 3
MPCS 52060 – Parallel Programming
The final project gives you the opportunity to show me what you learned in this course and to build your own parallel system. In particular, you should think about implementing a parallel system in the domain you are most comfortable in (data science, machine learning, computer graphics, etc.). The system should solve a problem that can benefit from some form of parallelization. Similar to how the performance of an image processing system benefits from parallel data decomposition of an image. If you are having trouble coming up with a problem for your system to solve then consider the following:
• https://en.wikipedia.org/wiki/Embarrassingly_parallel
• https://en.wikipedia.org/wiki/Parallel_computing#Algorithmic_methods
Part 1: Minimum Requirements (85 points)
The level of difficulty you should aim for when implementing your system should be equal to the level of difficulty of project 2 (e.g., the amount of code written, the computational complexity, etc.). For example, writing the an implementation of the Mandelbrot or Julia set is trivial and not an acceptable project. If you’re in doubt then ask me on Piazza before beginning your project. You are required to at least have the following features in your parallel system:
• An input/output component that allows the program to read in data or receive data in some way. The system will perform some computation(s) on this input and produce an output result.
• A sequential implementation of the system. Make sure to provide a usage statement.
• Use a parallel partitioning mechanism (functional, data, or both) to split up tasks to your threads. You are only required to have at least one partitioning mechanism not both. There are no limits on the number of goroutines you spawn or when you spawn them. You have the freedom and flexibility to implement the parallel version as you wish. This also goes for using any synchronization primitives you want.
• Provide a detailed write-up and analysis of your system. For this assignment, this write-up is required to have more detail to explain your parallel system since we are not giving you a problem to solve. See the System Write-up section for more details.
• Provide all the dataset files you used in your analysis portion of your write up. If these files are to big then you need to provide us a link so we can easily download them from an external source.
• These points also include style points. You should think about the modularity of the system you are creating. Think about splitting your code into appropriate packages, when necessary.
• You must provide a script or specific commands that shows/produces the results of your system. We need to be able to enter in a single command in the terminal window and it will run and produce the results of your system. Failing to provide a straight-forward way of executing your system that produces its result will result in significant deductions to your score. We prefer running a simple command line script (e.g., shell-script or python3 script). However, providing a few example cases of possible execution runs will be sufficient enough.
1
You are free to use any additional standard/third-party libraries as you wish. However, all the parallel work is required to be implemented by you.
System Write-up
In prior assignments, we provided you with the input files or data to run experiments against a your system and provide an analysis of those experiments. For this project, you will do the same with the exception that you will produce the data needed for your experiments. In all, you should do the following for the writeup:
• Run experiments with data you generate for both the sequential and parallel versions. As with the data provided by prior assignments, the data should vary the granularity of your parallel system. The experiments should be run on at least three different data sets. For the parallel version, make sure you are running your experiments with at least producing work for N threads, where N = {2, 4, 6, 8}. You can go lower/larger than those numbers if you wish.
• Produce speedup graph(s) for those data sets.
Please submit a report (pdf document, text file, etc.) summarizing your results from the experiments and the conclusions you draw from them. Your report should include your plot(s) as specified above and a self-contained report. That is, somebody should be able to read the report alone and understand what code you developed, what experiments you ran and how the data supports the conclusions you draw. The report must also include the following:
• Describe in detail your system and the problem it is trying to solve.
• A description of how you implemented your parallel solution.
• Describe the challenges you faced while implementing the system. What aspects of the system might make it difficult to parallelize? In other words, what to you hope to learn by doing this assignment?
• Specifications of the testing machine you ran your experiments on (i.e. Core Architecture (Intel/AMD), Number of cores, operating system, memory amount, etc.)
• What are the hotspots and bottlenecks in your sequential program? Were you able to parallelize the hotspots and/or remove the bottlenecks in the parallel version?
• What limited your speedup? Is it a lack of parallelism? (dependencies) Communication or synchro- nization overhead? As you try and answer these questions, we strongly prefer that you provide data and measurements to support your conclusions.
Part 2: Advance Feature(s) (15 points)
The above work guarantees a B for the assignment. If you want a higher grade then you need to go the extra mile that adds more complexity to your parallel version of the system. Please add a separate section in your report the explicitly explaining the advance features you implemented and where in your code they are implemented. One to two paragraphs is enough for your explanation.
Additional features could include:
• In your parallel component using one of the work distribution mechanisms we discussed in week 7 and 8:
– Work Stealing
– Work Balancing
– Bulk Synchronous Parallel (BSP) – Tree based barrier implementation
2
– Futures (however, you’ll need to do little more than just futures for this part).
• Using a concurrent data structure that we did not cover in class. This means researching other
concurrent data structures that you can use within your project.
• Adding in a parallel pattern or system/architecture component we did not discuss in class. For example, adding a GPU component. If you do this then please check with me before you submit your assignment. This step ensures that I have the necessary libraries, components to run your system. Not checking with me could result in zero points for this section.
I will not answer the following question (or any variation of it):
Are these advance features good enough for a … (e.g. B+, A, etc.)?
This part will be solely graded by Professor Samuels. Thus, he knows based on your designated due date what warrants a higher grade. Typically, implementing one or two complex features is enough to achieve an A; however, it’s based on the complexity those features. You can plead your case in the advance features section of your report.
Graduating Students
Due to time constraints for graduating students, those students who are graduating are not required to implement Part 2. However, if you do plan to resubmit your project after the graduating students deadline then you are required to complete part 2.
Submission
Submit all your code and report into a directory named proj3. You should include a README that explains how to run your system. Overall your proj3 directory should include:
• A src directory that includes all your code for project 3.
• A report file that has your write-up and analysis. Also include your graph(s).
• A README that very briefly explains in little more detail how to run your parallel system.
• Any datasets that were used to run your experiments. Again you can provide a link in the README file if those files are too big.
Due Dates
• Graduating Students: Friday August 21st at 08:00 am (We are a strict deadline this quarter so this is the very lateness time I can accept)
• Non-Graduating Students: Tuesday August 25th at 11:59 pm
You cannot use extensions for this assignment. We need all the time we have to grade these projects thoroughly and fairly.
3