Scribd Logo
Upload

Welcome to Scribd!

  • 40 views

    Project CCAI 412

    Uploaded by

    tayyaba hussain
    1. The document describes a parallel computing project to identify prime numbers using the Sieve of Eratosthenes algorithm. Students must implement the algorithm in serial C/C++ code, then parallelize it using OpenMP and MPI to benchmark performance across different problem sizes and processor counts. 2. Key steps include serial and parallel implementations of the sieve algorithm to find primes up to various values of N, as well as benchmarking and analyzing speedup results. Parallelization strategies like data decomposition and collective communication must be considered. 3. Students must submit a final report by November 12th including descriptions of their parallelization approaches, benchmark diagrams, and evaluation of results against theoretical speedup models. Successful completion requires

    Copyright:

    © All Rights Reserved
    Download as DOCX, PDF, TXT or read online from Scribd

    Project CCAI 412

    Uploaded by

    tayyaba hussain
    40 views13 pages
    1. The document describes a parallel computing project to identify prime numbers using the Sieve of Eratosthenes algorithm. Students must implement the algorithm in serial C/C++ code, then parallelize it using OpenMP and MPI to benchmark performance across different problem sizes and processor counts. 2. Key steps include serial and parallel implementations of the sieve algorithm to find primes up to various values of N, as well as benchmarking and analyzing speedup results. Parallelization strategies like data decomposition and collective communication must be considered. 3. Students must submit a final report by November 12th including descriptions of their parallelization approaches, benchmark diagrams, and evaluation of results against theoretical speedup models. Successful completion requires

    Copyright

    © © All Rights Reserved

    Available Formats

    DOCX, PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    1. The document describes a parallel computing project to identify prime numbers using the Sieve of Eratosthenes algorithm. Students must implement the algorithm in serial C/C++ code, then parallelize it using OpenMP and MPI to benchmark performance across different problem sizes and processor counts. 2. Key steps include serial and parallel implementations of the sieve algorithm to find primes up to various values of N, as well as benchmarking and analyzing speedup results. Parallelization strategies like data decomposition and collective communication must be considered. 3. Students must submit a final report by November 12th including descriptions of their parallelization approaches, benchmark diagrams, and evaluation of results against theoretical speedup models. Successful completion requires

    Copyright:

    © All Rights Reserved
    Download as DOCX, PDF, TXT or read online from Scribd
    Download as docx, pdf, or txt
    40 views13 pages

    Project CCAI 412

    Uploaded by

    tayyaba hussain
    1. The document describes a parallel computing project to identify prime numbers using the Sieve of Eratosthenes algorithm. Students must implement the algorithm in serial C/C++ code, then parallelize it using OpenMP and MPI to benchmark performance across different problem sizes and processor counts. 2. Key steps include serial and parallel implementations of the sieve algorithm to find primes up to various values of N, as well as benchmarking and analyzing speedup results. Parallelization strategies like data decomposition and collective communication must be considered. 3. Students must submit a final report by November 12th including descriptions of their parallelization approaches, benchmark diagrams, and evaluation of results against theoretical speedup models. Successful completion requires

    Copyright:

    © All Rights Reserved
    Download as DOCX, PDF, TXT or read online from Scribd
    Download as docx, pdf, or txt
    of 13

    University of Jeddah

    First Trimester 2022


    PLO S2 / CLO2.2 / SO6

    CCCS 412: Parallel Computing


    Project
    Deadline 12 Nov 2022 on LMS

    1 Description

    A versatile scholar, Eratosthenes of Cyrene (today Libya) lived approximately 275195 BC.
    He was the first to estimate accurately the diameter of the earth. For several decades, he
    served as the director of the famous library in Alexandria. He was highly regarded in the
    ancient world, but unfortunately only fragments of his writing have survived. Eratosthenes
    died at an advanced age from voluntary starvation, induced by despair at his blindness.

    Eratosthenes also conceived the “Sieve of Eratosthenes”, a method for identifying prime
    numbers. Therefore, in a first step the set of natural numbers P = 2, …, N from 2 to an
    upper limit N (in arbitrary ordering) is formed. Then, after searching for the minimum element
    p of set P  the first prime number  all multiples of p are deleted from P. Successively
    repeating this step until p >  N  there are only prime numbers left.

    Example: N = 15, i.e. termination for p = 3 (=  15 )

    1. step: 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , 10 , 11 , 12 , 13 , 14 , 15  p=2

    delete multiples: 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , 10 , 11 , 12 , 13 , 14 , 15

    2. step: 3 , 5 , 7 , 9 , 11 , 13 , 15  p=3

    delete multiples: 3 , 5 , 7 , 9 , 11 , 13 , 15

    termination (only prime numbers left), i.e. PRIME = 2, 3, 5, 7, 11, 13

    2 Implementation

    1. Implement a program sieve in C or C++ following the algorithm described above.


    Think about sufficient data structures for storing the elements in order not to process
    any element more than once that has already been discarded from the set. Run your
    program for different values of N, i.e. 1,000,000, 5,000,000, 10,000,000, 25,000,000,
    and 50,000,000 if your computer permit. What do you observe? For control, always
    print the largest prime number found!
    N= 5,000,000
    N = 10,000,000
    N= 25,000,000
    N= 50,000,000
    2. For a faster processing, parallelisation is inevitable. In a first (and simple) approach,
    scan your code for ‘prominent’ blocks of instructions that would benefit from multi-
    threading. Extend these blocks of instructions with valid OpenMP directives in order
    to allow a parallel processing. Run your code for different values of N (see above)
    and different amount of threads (2, 3, and 4). What do you observe now? For control,
    always print the largest prime number found!
    3. For further parallelization, message passing is the name of the game. Think about a
    sufficient parallelization strategy and what code changes have to be made. Extend
    your program sieve from (1.) – not the OpenMP version! – with the necessary
    parallel functionality using MPI. Try to think and use the collective communication
    commands. Run your program for different values of N, i.e. 1,000,000, 5,000,000,
    10,000,000, 25,000,000, and 50,000,000 if your computer permit, and different
    amount of processes (i.e. 2, 4, and 8). What do you observe now? For control,
    always print the largest prime number found!

    3 Benchmark

    Sketch your results (i.e. execution times) of your OpenMP/MPI program for different N and
    different amount of processes in two diagrams showing speed-up or parallel efficiency. You
    can use any plotting tool (Excel, Python, etc.) of your choice. In order to ‘benchmark’ your
    results, also make a theoretical approach to compute speed-up and efficiency according to
    Amdahl. Therefore, estimate the serial part of your program and compute the corresponding
    speed-up and efficiency values. Compare those with the ones measured and discuss your
    observation!

    4 Report

    Write a final report (45 pages) including a brief description of your chosen parallelization
    strategy and the necessary MPI communication in your code (i.e. sketch the communication
    idea). The report should further highlight your achieved results for both parallelization
    approaches (i.e. OpenMP and MPI) including your diagrams and benchmark results from (3).
    Evaluate your results, i.e. discuss if in your opinion your results are good or bad and where
    you might have ‘lost’ performance within your parallelization. The quality of the write-up is
    part of the grade!
    5 Project Due

    For successfully finishing the project students have to upload their final report together with
    all programs (i.e. source code) not later than 12 Nov 2022 on LMS.

    You might also like