FINAL PROJECT

The final project for COMP481 is an application of the concepts learned in class, and will be performed in groups of 4 students.

IMPORTANT NOTE: Exceptionally well researched projects can get up to 5 extra bonus points and if accepted by the team, be invited for a revised publication on a IEEE or ACM journal.

Goals

The goal of this research project is to apply some of the basic knowledge gathered across the quarter about parallel algorithms and computing, and to introduce you to parallel computing research and state-of-the-art technologies, algorithms, and architectures.

Instructions

The final research project can be done in three different categories:

  • Implementation projects (strongly encouraged): In which your team will conduct a brief literature review of a specific subject (e.g., algorithm or a computational problem) and then build a program to test, analyze, or evaluate some of its features or the performance results.
  • Survey project: In which your team will conduct in-depth literature review of a specific subject pertaining to parallel algorithms and computing. These projects should point out, for example, the different solutions proposed in the literature for a given problem, the state of a particular field being aided by parallel computing, trade-offs between compared algorithms, and so on.
  • Evaluation projects: In which your team will conduct a brief literature review of a specific algorithm implementation and perform analytical studies to evaluate the performance with different inputs, scalability, propose changes, and so on. Your team may also compared two different implementations of the same problem (e.g. shared memory vs. distributed memory implementation)

The research project will be delivered in the following phases:

  1. Project Proposal: Your team will write a post to Teams (in the Final Project channel) with the following details:
    • Project topic, category, title (this might change as you go), specifications, and time-line.
    • Project goals
    • Team members
    • References
    You are strongly encouraged to discuss your ideas with Dr. Vargas-Pérez to make sure that your team's idea is good and that different people are not working on the same topic.
  2. Check Point: Your team will meet with Dr. Vargas-Pérez and discuss the progress so far. Describe what has been accomplished in terms of what your team proposed. We will meet for the check point during Week 8.
  3. Project Presentation: Your team will have 20 minutes to present the final project. Presentations will be held during Week 10, three groups per day (check class schedule), including on Friday. With this presentations your team will explain the work done emphasizing your implementations or findings, used technologies, contributions, and/or the trade-offs between the studied approaches. The presentation might have, among other things:
    • Project title.
    • Introduction: research/design, background information, and so on.
    • Examples or visualizations, code (if applicable)
    • Implementation and results' analysis (if applicable)
    • Conclusion: What did you learn? and so on
    • References

Evaluation

Your final project is worth 30% of your final grade, and it is going to be evaluated as follows:

  • Project Proposal: due Friday Week 8 5pts.
  • Check Point: we will meet during Week 9 5pts.
  • Presentation: during Week 10 20pts.
  • Bonus points: for exceptional work 5pts.

Topics

The following are sample topics. If your team wants to work on a topic not listed here, please talk to Dr. Vargas-Pérez to make sure the topic complies with the course learning goals.

  • Survey Projects:
    • Quantum computational model or quantum computing (as it pertains to parallel computing).
    • Dataflow computational model.
    • Trends in GPU technologies.
    • Time-line for the evolution of parallel computing.
    • Problems in AI and Machine Learning (as it pertains to parallel computing).
    • Parallel computing and game design.
    • Tsunami simulation or wave propagation.
    • Parallel algorithms for the Stock Market.
    • Analysis of distributed vs. shared memory algorithms.
    • Other problems being solve using the power of parallel computing and algorithms.
  • Implementation and Evaluation Projects:
    • Parallel computation of the number π (chapter 6 of your textbook).
    • Parallel solution of 1-D heat equation (chapter 7 of your textbook).
    • Parallel implementation of seam carving (chapter 8 of your textbook).
    • Monte Carlo simulation.
    • Parallel Radix sort.
    • Parallel fast Fourier transform.
    • The n-body problem (Barnes-Hut algorithm).
    • Parallel BLAST (simple version if implementing).
    • Parallel Motif finding algorithms.
    • Parallel implementation of the Sieve of Eratosthenes.
    • Maze-solving parallel algorithms
    • Parallel Hidden Markov Model.
    • Performance comparison between implementations of a parallel algorithms.
    • Other implementation or evaluation problems that are of interest for your team.