Reference no: EM133781031
Operating Systems s Multithreaded Programming Class Project
Overview
The project allows you to apply parallel programming techniques to real-world computational problems. The primary goal is to choose a computationally intensive problem, design parallel solutions, and provide a performance analysis comparing parallel and sequential implementations.
Project Requirements
Problem Identification
The selected problem should be computationally intensive, requiring substantial processing resources. Examples of suitable problems include tasks such as sorting large datasets, graph traversal, querying massive databases, or running computationally heavy scientific simulations. The key is to select a problem where parallelism significantly reduces computation time.
For instance, consider sorting algorithms. While bubble sort is a sorting algorithm, it may not be suitable for this project because its inherent limitations (O(n2) complexity) can overshadow any parallel performance improvements. A better alternative would be selecting merge sort or quick sort, which are more adaptable to parallelization and can demonstrate clear performance gains through parallel computing.
Your problem choice is essential to show meaningful performance improvement when comparing sequential and parallel versions. The suitability of your problem should reflect the potential benefits of parallelization in reducing runtime or increasing computational efficiency.
Multiple Implementations
You are required to submit three implementations of the problem:
Sequential Implementation: The baseline version of the solution, which will allow you to compare the sequential runtime with the parallel versions.
Two Parallel Implementations: You are required to implement the same problem using two different parallel programming frameworks. Frameworks you may choose from include, but are not limited to, multi-threaded programming, MPI, OpenMP, CUDA, OpenCL, or OpenACC. Feel free to explore other frameworks if they are well-suited to your problem's characteristics.
Performance Testing and Comparison
Conduct a performance analysis of all three implementations on the Rushmore cluster using different numbers of processes (e.g., 4, 8, and 16, ...). Your testing should involve running the program across multiple virtual machines. Analyze the computation time, communication overhead, and the effect of running multiple processes on each virtual machine. Pay attention to any trade-offs or performance bottlenecks encountered as you scale the number of processes. Insights gained from these tests should highlight how parallelization impacts performance and the specific trade-offs involved.
Submission 1: Submit the first report containing a brief introduction of the problem you identified (2-3 pages).
Submission 2: Submit the code and the final report in this submission. Please note that all files must be submitted as one zip file. Details are given below:
Source Code: Your submission should contain well-documented code that explains the purpose of each section and the overall flow of the program. Ensure that variable names, functions, and comments are clear and concise.
Final Report: In addition to your code, submit a detailed report (no page limit), which includes the following:
Problem Description: A clear description of the problem you chose and why it is suited for parallel programming.
Implementation: A breakdown of all implementations, including both the baseline (sequential) and parallel versions. Provide details on how you implemented the parallel programming frameworks and how they were applied for performance gains in comparison to the baseline.
Performance Analysis: Provide a detailed analysis of your program's performance across different configurations. This should include results for both the baseline (sequential) and parallel implementations. Demonstrate the execution of each implementation separately and include screenshots of output from different runs, showing the distribution of operations across processes, computation time, and any relevant performance metrics.
README Section: A section in the report detailing instructions for compiling and running the program (instead of submitting a separate README.txt file).
Group Work s Expectations
You can work on the project individually. If you choose to work in a group, you are allowed to work in groups of up to two. For group projects, a higher level of effort is expected. Below are a few examples of how you can expand the scope or complexity of your work to meet this expectation. You can think of the other ways along these lines.
Larger Problem Scope: Choose a more complex problem or scale up your problem to involve more challenging data sizes. For example, if working on graph traversal, you could work with larger graphs with more nodes and edges, showcasing better load balancing and scalability across multiple processes.
Extended Features: Implement additional functionality. For example, in a sorting algorithm, you might implement sorting in parallel across multiple machines with different data distributions, handling datasets split across several nodes.
Advanced Optimizations: Go beyond the basics by implementing optimizations that significantly improve performance, such as using more advanced MPI features, optimizing the communication patterns, or implementing fault tolerance mechanisms to ensure your program can recover from process failure.