Project #3: Your Choice!

Due Dates:

  • Graduating Students: Thursday May 26th at 11:59pm CDT. No extensions can be used for Project #3

  • Non-graduating Students: Wednesday, June 1st at 11:59pm CDT. No extensions can be used for Project #3

Getting started

For each assignment, a Git repository will be created for you on GitHub. However, before that repository can be created for you, you need to have a GitHub account. If you do not yet have one, you can get an account here: https://github.com/join.

To actually get your private repository, you will need this invitation URL:

When you click on an invitation URL, you will have to complete the following steps:

  1. You will need to select your CNetID from a list. This will allow us to know what student is associated with each GitHub account. This step is only done for the very first invitation you accept.

Note

If you are on the waiting list for this course you will not have a repository made for you until you are admitted into the course. I will post the starter code on Ed so you can work on the assignment until you are admitted into the course.

  1. You must click “Accept this assignment” or your repository will not actually be created.

  2. After accepting the assignment, Github will take a few minutes to create your repository. You should receive an email from Github when your repository is ready. Normally, it’s ready within seconds and you can just refresh the page.

  3. You now need to clone your repository (i.e., download it to your machine).

    • Make sure you’ve set up SSH access on your GitHub account.

    • For each repository, you will need to get the SSH URL of the repository. To get this URL, log into GitHub and navigate to your project repository (take into account that you will have a different repository per project). Then, click on the green “Code” button, and make sure the “SSH” tab is selected. Your repository URL should look something like this: git@github.com:mpcs52060-spr22/proj3-GITHUB-USERNAME.git.

    • If you do not know how to use git clone to clone your repository then follow this guide that Github provides: Cloning a Repository

If you run into any issues, or need us to make any manual adjustments to your registration, please let us know via Ed Discussion.

Assignment

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:

Part 1: Minimum Requirements (85 points)

You are free to implement any parallel algorithm you like. However, 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.

  • Parallel Implementation #1: Implement the work-stealing algorithm using a unbounded-dequeue implemented as linked-list (i.e., a chain of nodes similar to project #1). Golang does not have the keyword volatile; therefore, you will need to either use sync.Mutex or sync.Atomics or any other sync package object. I would recommend using sync.Mutex. You will need to adapt the array based version shown in class to a linked-list version. A few additional notes:

  1. To handle the ABA problem, make sure to define an internal node structure that holds the actual item being held in the dequeue. Every time an item is inserted then a new node is created for that item. The ABA problem only occurs when reusing memory addresses so creating unique ones will stop this from happening. Thus, you will not need a stamp mechanism in this implementation. However, it does come at the cost of cache performance.

  2. You need to define the structure of the algorithm to be a clean separation between application logic and the work-steal logic. This means that I should be able to take your implementation and use it as a library for any other application that wants to use a work-stealing scheduler. Professor Samuels will go over this in Week 8 so check your notes about how to think about this portion.

  • 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 design 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.

  • We should also be able to run specific versions of the system. There should be a option (e.g. via command line argument) to run the sequential version, or the various parallel versions. Please make sure to document this in your report or via the printing of a usage statement.

  • 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.

  • There is a directory called proj3 with a single go.mod file inside your repositories. Place all your work for project 3 inside this directory.

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. 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,12}. You can go lower/larger than those numbers based on the machine you are running your system on. You are not required to run project 3 on the Peanut cluster. You can run it on your local machine and base your N threads on the number of logical cores you have on your local machine. If you choose to run your system on your local machine then please state that in your report and the your machine specifications as well.

  • Produce speedup graph(s) for those data sets. You should have one speedup graph per parallel implementation you define in your system. This means either one or two speedup graphs.

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 detailed of 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 synchronization 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)

*** Due to time constraints, graduating students do not need to complete this portion. Your grade will be based on completing the minimum requirements, will be judged out of 100 points. Non-graduating are not required to complete the advance feature section unless they want a higher grade.*

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 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.

  • Parallel Implementation #2: Choose your own parallel partitioning mechanism (split up tasks to your goroutines). 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.

Implementations could include:

  • In your parallel component, using one of the work distribution mechanisms we discussed in week 7 and 8:

    • Work Balancing

    • Bulk Synchronous Parallel (BSP)

    • Tree based barrier implementation

    • A channel multiplex implementation or another type of channel system.

    • Futures and Work-Stealing are not allowed to be used for an advance feature..

  • 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.

Make sure to talk about how your advance feature affects the overall performance of the system.

Don’t know What to Implement?

If you are unsure what to implement then by default you can reimplement the image processing assignment without using multiplex channels configuration or BSP as a parallel implementation. You cannot reimplement project 1 or other assignments.

Grading

The sections above provide the point break-down for this project.

Design, Style and Cleaning up

Before you submit your final solution, you should, remove

  • any Printf statements that you added for debugging purposes and

  • all in-line comments of the form: “YOUR CODE HERE” and “TODO …”

  • Think about your function decomposition. No code duplication. This homework assignment is relatively small so this shouldn’t be a major problem but could be in certain problems.

Go does not have a strict style guide. However, use your best judgment from prior programming experience about style. Did you use good variable names? Do you have any lines that are too long, etc.

As you clean up, you should periodically save your file and run your code through the tests to make sure that you have not broken it in the process.

Submission

Before submitting, make sure you’ve added, committed, and pushed all your code to GitHub. You must submit your final work through Gradescope (linked from our Canvas site) in the “Project #3” assignment page via two ways,

  1. Uploading from Github directly (recommended way): You can link your Github account to your Gradescope account and upload the correct repository based on the homework assignment. When you submit your homework, a pop window will appear. Click on “Github” and then “Connect to Github” to connect your Github account to Gradescope. Once you connect (you will only need to do this once), then you can select the repsotiory you wish to upload and the branch (which should always be “main” or “master”) for this course.

  2. Uploading via a Zip file: You can also upload a zip file of the homework directory. Please make sure you upload the entire directory and keep the initial structure the same as the starter code; otherwise, you run the risk of not passing the automated tests.

As a reminder, for this assignment, there will be no autograder on Gradescope. We will run the program the CS Peanut cluster and manually enter in the grading into Gradescope. However, you must still submit your final commit to Gradescope.