Part II:

$($PLO S$2/$ CLO$2\mathrm{.}2/$ SO$6)$

The Prime Factorization algorithm finds the prime factors of a given number. The Parallel

Prime Factorization approach can be effective for huge numbers. This can be implemented

as a shared$-$memory or distributed$-$memory versions.

Here's a high$-$level overview of the Parallel Prime Factorization algorithm:

Domain Decomposition: In MPI, the range of numbers to be factored is split among

the processes that are available; in OpenMP, it is split among the threads.

Local Factorization: Each process or thread performs the prime factorization on its

assigned range of numbers.

Communication: In the case of MPI, the processes exchange information about the

prime factors they discovered, ensuring that all processes have a complete view of

the factorization findings.

Global Reduction: The processes or threads combine their results to provide the

final prime factorization of a given number.

$($i$)$ Implementation:

Implement a program in C or C$++$ using OpenMP following the algorithm described

above. Think about sufficient data structures for storing the elements. Run your program

for different values of N$,$ i$.$e$.1234567890,23423456780,234780234562$ and

$5067891002343$ if your computer permit. Run your code for different amount of threads

$(4,8,$ and $16).$ What do you observe? For control, always print the list of prime factors

found.

Extend your program with the necessary parallel functionality using MPI. Try to think and

use the collective communication commands. Run your program for same values of $N$

$($from previous implementation$),$ and different amount of processes $($i$.$e$.4,8,$ and $16).$

What do you observe now? For control, always print the list of prime factors found.

$($ii$)$ 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 and 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. Please refer to Chapter $3$ in

introduction to parallel programming textbook: section $3\mathrm{.}6\mathrm{.}3$ and $3\mathrm{.}6\mathrm{.}4$ when you are

writing up the analysis part of your report.

$($iii$)$ Report and presentation:

$$ Write a final report $(4-5$ pages$)$ including a brief description of your 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.

$$ Evaluate your results by discussing if in your opinion the results obtained 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. Moreover, please provide a presentation along with the

report including your observations from Part I.