Assignment: Theoretical parallelization

1. The serial algorithm

The goal of this first part is to identify a problem that is of the interest to the student that can be parallelized: what is solves, what inputs needs, what generates, it computational cost and what parts of it can be potentially parallelized.

1.1 Describe what the selected algorithm does (include the references that you have used):
1.1.1 Why the algorithm has been selected?
1.1.2 Inputs, outputs and pseudo-code describing the algorithm. The pseudo-code must contain comments on what each important part of it is doing.
1.2 Describe what parts of the algorithm can be potentially parallelized.

2. Parallel implementation

The goal of this second part is to propose a pseudo-code parallel implementation for the parts identified in 1.2.
2.1 There are any existing solutions? Briefly describe their approaches. List the references.
2.2 Describe in pseudo-code a two potential parallel implementations for this algorithm:
2.2.1 What strategy have you selected? (i.e: pipeline, shared memory, message passing etc.) Why?
2.2.2 What other options you could use?
2.2.3 If possible, can you compare your proposal with the existing solutions proposed in 2.1?
2.2.4 Describe the pseudo-code including comments on why the different parallel selected parts.

3. Performance projection

3.1 Given the pseudo-code proposed in 2.2 and 1.1 propose a theoretical model to project the speedup that the parallel implementation may show with respect to the serial implementation. (It's a model so it's not expected to provide 100% accuracy).

3.1.1 Extra: Can you compare your proposed solutions with one of the existing solutions identified in 2.1?

3.2 Provide a speedup analysis using the previous model for: 1, 2, 4, 16 and 32 threads.

3.3 Provide a description of what type of computational system would be better for the provided implementation and what components would be important to invest more.