CSC 429 Mid Fall 12

CSC429 Midterm Exam
Solve all the problems in the blue book provided.

Duration: 1hour 40minutes
Read the Problems CAREFULLY!
100 points total
ASSUMPTIONS: Throughout the exam, if not specially specified, you may assume that
n is a multiple of p, and p is a power of two. You may assume that it takes one operation
to compute a+b and one operation to compute a b (product of a and b), given a and b.
Problem 1 Multiple choices(18 points, 3 points each):
1. In the ________ PRAM, processors must write the same value into the shared
memory cell.
A. Arbitrary
B. Common
C. Priority
D. Comibing
2. Which of the following PRAM is most powerful? ___________
A. EREW
B. CREW
C. ERCW
D. CRCW
3. Which of the following is not fixed (static) connection network? ___________
A. Star-Connected Network
B. Crossbar Networks
C. 3d-mesh Network
D. Hypercube Network
4. In the completely connected network with N nodes, there are totally ________
linkes(edges).
A. N
B. 2N
C. N(N-1)/2
D. N2
5. What is diameter of hypercube network with 64 processors? __________
A. 6
B. 8
C. 12
D. 16
6. Consider the problem of sorting n input numbers. Bubble Sort runs in

approximately n2 steps and Heap Sort(which is one of the best sorting algorithm)
runs in approximately nlog n steps. With n processing nodes, Odd-even
Transposition Sort algorithm runs in approximately n steps. What is the speedup
of Odd-even Transposition Sort algorithm? __________
A. n
B. log n
C. n/log n
D. none of the above
Problem 2 (15 points)
Explain dichotomy of parallel computing platforms based on control structure (Flynn’s
taxonomy of computer architectures). Vector Processing features single instruction on
multiple data sets. Which structure does Vector Processing belongs to? In which
structure, different processors may be executing different instructions on different pieces
of data at any time?

What is the structure of a complete omega network? Please draw a figure of a complete
omega network connecting four inputs and four outputs.
What is the output of the following MPI program(You may assume any execution order
of processes)?
#include <mpi.h>
int main(int argc, char **argv) {
int nprocs, mypid, myval, i, total;
MPI_Init(&argc,&argv);
MPI_Comm_size(MPI_COMM_WORLD,&nprocs);
MPI_Comm_rank(MPI_COMM_WORLD,&mypid );
printf("Hello world from process %d of total %d\n",mypid,nprocs);
myval=mypid;
if (pid!=0)
{
MPI_Send(&myval,1,MPI_INT,0,1,MPI_COMM_WORLD);
printf("Send a number %d from processor %d\n",myval,mypid);
}
else
{
for(i=1; i<nprocs;i++)
{
MPI_Recv(&total,1,MPI_INT,i,1,MPI_COMM_WORLD,&status);
myval=myval+total;
}
printf("Receive total value of %d\n",myval);
}
MPI_Finalize();
}
Hello world from process 0 of total 4
Send a number 1 from processor 1
Receive total value of 6

Problem 5 Programming and Answer questions (22 points)
A programmer needs to write a program such that (1) each process will compute and
print out a partial sum of N numbers (2) all processes except process 0 send their partial sum to
process 0 and print this message (3) after process 0 receive the partial sums from other processes,
process 0 will print out the confirmation that it received the value, add up all the partial sums
including its own partial sum, and print out the total sum, that is, the value of 1+2+3+…
+1000(that is, ). Note he is going to apply for 10 processing nodes for his program.
1. (15 points) This user has finished the partial program named parallelSum.c as
below. Please help him complete the program.
// include the header file (1 point)
#define N 1000
main (int argc, char **argv)
{
int nprocs, mypid, i, mysum=0;
int total;
MPI_Status status;
//Initialize MPI environment (2 point)
//Find the process id (2 point)
//Find the total number of processes (2 point)
//compute the partial sum (3 points)
printf( "Partial sum from process %d of total %d is : %d. \n", mypid, nprocs,
mysum);
if (mypid!=0)
{
//send the partial sum to process 0 (2 point)
printf("Send %d to process 0 by process %d\n", mysum, mypid);

}
else
{
total=mysum;
for (i=1; i<nprocs; i++)
{
//receive partial sum from process i (2 point)
printf("Receive %d from process %d\n", mysum, i);

total+=mysum;
}
printf("Total sum is %d\n", total);
}
//finish MPI environment (1 point)
2. (2 points) What is the complete command to compile this mpi program?
3. (2 points) The programmer opened the script file, which is shown as follows.
Please help him revise the script file correctly.
#!/bin/bash
#PBS -N job4
#PBS -q production
#PBS -l select=8:ncpus=1
#PBS -l place=free
#PBS -V
cd $PBS_O_WORKDIR
mpirun -np 8 -machinefile $PBS_NODEFILE ./a.out
4. (2 points) What is the command to submit the job?
5. (1 point) What is the command to check the status of this job?

Input: A p processor EREW PRAM, n numbers x , x , … , x , and an associative operator
1 2 p
+.
Output: The parallel sum x = x + x + … + x .
1 2 p
(a) Assume p>=n, give or cite an efficient EREW PRAM algorithm that finds
the parallel sum x. (10 points)
(b) Assume p<n, give an EREW PRAM algorithm that finds the parallel sum
x in at most n/p + lg p steps. (5 points)
Extra Credit (15 points)
Input: A p-processor CRCW PRAM, and two integers x and n (Note: p>=n).
Output: The value of xn.
(1) If n is a power of 2, how fast can you calculate the value of xn on single
processor? Can you calculate faster on p-processor? (10 points)
(2) If n is not a power of 2, how fast can you calculate the value of xn on single
processor? Can you calculate faster on p-processor? (10 points)
Note: You final grade for this midterm is min{100, (your grade on problem 1-6) + (your
grade on extra credit)}
THE END OF EXAM

CSC 429 Mid Fall 12

Uploaded by

Copyright:

Available Formats

CSC 429 Mid Fall 12

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

CSC 429 Mid Fall 12

Uploaded by

Copyright:

Available Formats

CSC429 Midterm Exam

Solve all the problems in the blue book provided.

Problem 1 Multiple choices(18 points, 3 points each):

2. Which of the following PRAM is most powerful? ___________

3. Which of the following is not fixed (static) connection network? ___________

6. Consider the problem of sorting n input numbers. Bubble Sort runs in

Problem 3 (15 points)

Hello world from process 0 of total 4

Hello world from process 1 of total 4

Hello world from process 2 of total 4

Hello world from process 3 of total 4

Send a number 1 from processor 1

Send a number 2 from processor 2

Send a number 3 from processor 3

Receive total value of 6

// include the header file (1 point)

//Initialize MPI environment (2 point)

//Find the process id (2 point)

//Find the total number of processes (2 point)

//compute the partial sum (3 points)

//send the partial sum to process 0 (2 point)

printf("Send %d to process 0 by process %d\n", mysum, mypid);

//receive partial sum from process i (2 point)

printf("Receive %d from process %d\n", mysum, i);

//finish MPI environment (1 point)

2. (2 points) What is the complete command to compile this mpi program?

mpirun -np 8 -machinefile $PBS_NODEFILE ./a.out

4. (2 points) What is the command to submit the job?

5. (1 point) What is the command to check the status of this job?

Problem 6 (15 points)

THE END OF EXAM

You might also like