What parts of the algorithms can be potentially parallelized

Assignment Help Computer Engineering

Reference no: EM131455222

Assignment

Objectives

The main goal of this exercise is introducing the student to the basic concepts of parallel programming. To do that, two different options are provided. The first one is more theoretical and is oriented to those students that do not have strong computer science background (i.e: programming, linux etc.). This option will let the student to propose a parallelization of a specific scientific problem. The second one is more practical and it is oriented to those students that have programming and system skills. In this second option the student will implement a parallel application using OpenMP and MPI+OpenMP.

What it is expected

1) the sources for the developed code; 2) one document with the answers with the proposed questions, the performance evaluation and the comments that the student wants to make. The developments must be done in C and with the required extensions for OpenMP and MPI.

The maximum length for the document is 4 pages.

1. The serial algorithm

The goal of this first part is to understand the nature of the smith-waterman algorithm: what is solves, what inputs needs, what generates, it computational cost and what parts of it can be potentially parallelized.

Describe what the smith-waterman algorithm does (include the references that you have used): inputs, outputs and pseudo-code describing the algorithm. The pseudo-code must and comments on

Describe the computational complexity of the algorithm. It is expected to provide a description on the serial implementation (i.e: O(n^2), O(nlogn))

Describe what parts of the algorithms 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.3.

Describe in pseudo-code a potential parallel implementation for this algorithm:

What strategy have you selected? (i.e: pipeline, shared memory, message passing etc.) Why?

What other options you could use?

Describe the pseudo-code including comments on why the different parallel selected parts.

Describe the computational complexity of the algorithm. It is expected to provide a description on the serial implementation (i.e: O(n^2), O(nlogn))

3. Performance projection

Given the pseudo-code proposed in 2.1 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).

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

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:

Software
Hardware.

Reference no: EM131455222

Questions Cloud

Organizational development and change : Consider the aggregate of the concepts you have learned over the past few units and then engage in class discussion for the final unit with your classmates.

What does modeling mean to you : What does modeling mean to you? How would you model something from your life now that you know about technology models?

What is the new probability of finding oil : An oil company purchased an option on land in Alaska. Preliminary geologic studies assigned the following prior probabilities.

Evolution of the human resource department : To start off the class, we will discuss the evolution of the Human Resource Department from the Personnel Department of the 1950s to the Human Resource Manageme

What parts of the algorithms can be potentially parallelized : Describe what parts of the algorithms can be potentially parallelized. Describe in pseudo-code a potential parallel implementation for this algorithm.

Implement a recursive version of these algorithms : Comp 251 Assignment. Download the java file multiply.java from the course web page. Here, your task is to implement a recursive version of these algorithms

Provide a brief example of a grey hat hacker : Explain main differences between white hat and grey hat hackers. Provide an example of a grey hat hacker. Discuss any recent story concerning session hijacking.

What is the revised probability : ParFore created a website to market golf equipment and apparel. Management would like a certain offer to appear for female visitors.

Cognitive behavior theory : Choose a theory that you have studied in this course. Do not choose one of the three theories listed above - Compare your selected theory against the three theories listed above.

User Account

All Pages