Research Project: Parallelization of Serial Algorithms

Learning Outcomes

The research project aims to:

  • Foster collaborative skills through teamwork on group projects.

  • Enhance proficiency in writing scientific articles.

  • Familiarize participants with the comprehensive academic research workflow.

Objective

Explore performance optimization by proposing parallel implementations of established serial algorithms. Participants will design the solution, implement the optimized design, evaluate its performance, and discuss the results in depth.

Suggested Workflow

  1. Problem Identification: Understand and articulate the serial algorithm that needs parallel optimization.

  2. Solution Proposition: Brainstorm and propose potential parallel implementations for the identified problem.

  3. Solution Implementation: Develop the proposed parallel solutions, ensuring correct functionality.

  4. Experiment Planning: Determine the methodology to test and evaluate the performance of the parallel solutions.

  5. Performance Evaluation: Analyze the implemented solutions for efficiency and improvements over the serial algorithm.

  6. Discussion: Reflect on the results, potential challenges, and implications of the implemented parallel solutions.

  7. Project Conclusion: Sum up the entire research project, drawing key insights and takeaways.

Assessment Criteria

The project assessment will be carried out in three stages:

  1. Topic Proposal:

    Submit a 1 or 2-page proposal detailing:

    • List all team members and their roles.

    • The specific problem or algorithm targeted.

    • Background and relevance of the problem.

    • Preliminary parallelization approaches considered.

    • Anticipated outcomes and performance benchmarks.

    • Tentative project timeline highlighting key milestones.

    • Cooperation strategy among team members.

    • Foreseen challenges and potential mitigation strategies.

  2. Progress Report:

    Submit a 1-page progress update that includes:

    • A summary of tasks completed so far.

    • Outline of pending tasks.

    • Encountered challenges and any course corrections made in the project approach.

    • Reflection on the collaboration within the team.

  3. Final Report and Source Code:

    1. Full report

    2. Code Repository

      • Everything should be in a single directory.

      • Include a LOG.txt to record the timestamped updates of the code repository. Record major updates only. If you use git to manage your code, you can write meaningful commit messages as a record and skip this document. Do not forget to include the .git directory in your submission in this case.

      • Include a README file that explains the purpose of files and directories in the root of repository.

      • Provide baseline serial implementation and its optimized version.

      • Provide multiple attempts of parallel implementations.

      • Code organization option 1:

        • In a same directory

        • Compile to multiple targets

        • Include a README to introduce each target and how to compile and run.

        • Include a Makefile to compile all targets.

      • Code organization option 2:

        • Organize implementations in their own directories.

        • Each of them should have a README and a Makefile.

      • The format of README can be Markdown, reStructuredText, or plain text. Choose the corresponding file extension (.md, .rst, or .txt) for the README file.

    3. Project Presentation

      • Prepare a 5-minute video presentation to summarize the project.

      • Create simple slides to highlight the key aspects of the project.

      • Store your video in Google Drive and provide a link. Host the video on youtube as unlisted video is another option.

      • If you are new to screen recording, you can use the free tool OBS Studio.

Extended Reading