$30.00

Category: CS 133

Description

5/5 - (6 votes)

Homework problems:

1. Write a parallel algorithm to compute all x1

, x2

, …, x1000 for some given x, assuming that you have k

processors. Please analyze the complexity of your algorithm in terms of the runtime and the total work time. Is it

optimal?

2. Given a list of n numbers, please develop a parallel algorithm to find the maximum of the list. Please analyze the

complexity of your algorithm in terms of the runtime and the total work time. Is it optimal?

3. Given a linked list of n items, please develop a parallel algorithm to compute the rank of each item the list.

The rank is defined to be the distance to the end of the list. Please analyze the complexity of your algorithm

in terms of the runtime and the total work time. Is it optimal?

4. Please implement Problem #2 in HW2 (histogram computation) using MPI with the assumption that the N

elements in the input are (roughly) evenly distributed over k processors. Please make your implementation

as efficient as possible.

5. Consider the basic matrix multiplication algorithm for two NxN matrices using KxK processors connected

using a 2D mesh network. Please derive the isoefficiency relation and the scalability function. Assuming all

data is stored in the processor 0 in the beginning so that you have to distribute them to each processor first.

You may assume communication time needed to broadcast L data in 2D mesh network is O(L).

6. (Bonus problem, 20 points) Assuming that we have p processors, please write a parallel algorithm that runs

faster than O(logn) to search integer y in a sorted list of integers x1, x2, …, xn, and output index i such that xi

<= y < xi+1. Please make your algorithm as fast as possible. You may assume all processors can read from

a memory space in constant time (CREW model). Is your algorithm optimal?

** For problems 1, 2, 3, and 6, you are encouraged to write a pseudo-code of your parallel algorithm followed

by a concise explanation of how your algorithm works. Also, please answer any additional questions in the

problem. Please write a C code with MPI APIs for problem 4.

Late submission policy:

We allow 16 hours delay until 8am Tues. Feb. 12 with 10 points penalty. After that, no submission will be

accepted beyond that time. We’ll post the solution for preparation of midterm at that time.

WhatsApp us