Monday, December 20, 2010

Gujarat University

MCA Semester IV

Parallel Processing

Date: 21^st July, 2003 Marks:50

Section I

Q-1 Answer the following in brief:

a. Define true speedup giving necessary details. 1

b. Explain the term ‘random scheduling’. Show its effect in parallel program with example. 2

` c. Write the parallel code segments that parallelize single loop using self scheduling mechanism. 2

d. Show the functions to remove semaphore and shared memory-using C under UNIX. 2

e. Differentiate between process and thread. 2

Q-2 a. Differentiate the dependency in the following loop. Show at least two possible solutions to resolve

it. For each solution, write the advantages and drawbacks. 4

Loop: for (i=0; i<n; i++) x[i] = x[i + 1] + y[i];

b. Discuss about the effect of creating processes at load time and at runtime. 4

OR

Q-2 a. How can indirect scheduling be used to transform two nested loops into a single one? Can it be used

when there is dependency among loop iterations? Justify your answer. Write sequential code

segment that finds sum of all elements of a matrix with m rows and n columns. Parallelize this code

segment.

b. Discuss about an effect of number processes on speedup in parallel computing. 4

Q-3 a. What do you mean by data parallelism? Explain static and quasi-dynamic scheduling methods of

data parallelism. Derive speed up for any one method. Write the assumptions, if any. 4

b. Explain creating and joining of threads under POSIX implementation. Give examples. 4

OR

Q-3 a. Obtain a task graph using the following sequential code segments. Consider each statement as a

task. 4 R5 = R1 + R2;

R6 = R3 * R4;

R7 = R6 – R2;

R5 = R3 + 1;

R4 = R7 * 2;

R7 = R4 / R5;

R8 = R2-R3;

Assuming that all operations take same time, assign these tasks to three processors to work in

parallel. Using this, find the time to finish all tasks.

b. Explain about ‘expression splitting’ parallel technique. Give example. 4

Section II

Q-4 a. Write the functionality of MPI_Init, MPI_Comm_size and MPI_Comm_rank. 3

b. Explain the use of BLOCK and CYCLIC in distributive directive in HPF. 3

c. Draw PVM architecture. Write the role of pvmd. 3

Q-5 a. Describe Flynn’s classification. Give characteristics And application for each. Show the architecture

of an one. 4

b. Discuss about the desired features of multiprocessor OS. 4

Q-5 a. What do you mean by inter-connection networks? Describe crossbar switch and time shared bus

architectures. 4

b. What do you mean by vector processor? Where should it be useful? Explain possible vector

instructions in brief. 4

Q-6 a. What is pipeline architecture? Draw the architecture. Write about different possible classifications

of pipeline processors. 4

b. Discuss about the views of any two pessimists who discourages parallel machines involving large

number of processors. 4

Q-6 Write differences: 8

a. Coarse grained vs. fine grained parallelism

b. Shared memory vs. dynamic memory programming model

c. FORALL statement vs. FORALL construct in HPF fortran

d. MPI vs PVM systems

Gujarat University

MCA Semester IV

Parallel Processing

Date: 24^th July, 2002 Marks:50

Instructions:

1. There are two sections.

2. Answer each section in separate answer books.

Section I

Q-1 Answer the following:

a. Differentiate between ideal speedup and actual speedup. [1]

b. Explain Amdahl’s law in brief. [2]

c. Differentiate between tightly and loosely coupled machines. [2]

d. Derive the speedup formula for block scheduling where excess iterations are distributed among various

processes. [2]

e. What is race condition? How to overcome it? Give example. [2]

Q-2 a. What is meant by dependency? Explain different types of dependencies. Show remedy of each giving

examples. [4]

b. Explain loop splitting and self-scheduling mechanisms. Write down the criteria for selection from these

two mechanisms. Give examples. [4]

OR

Q-2 a. Differentiate between temporal and data parallelism. Explain any two methods of parallelism in detail.

[4]

b. What is ‘mutual exclusion’? Explain the necessary semaphore operations in Unix to solve the

contention problem. Give example. [4]

Q-3 a. Discuss the effect of number of process and number of iterations on the performance of parallel code.

[4]

b. Specify the dependency in a loop containing a single statement X(i) = X(i-1) + Y(i). How can it be

removed? Write an algorithm to parallelize this loop for n=20 and nproc =5. [4]

OR

Q-3 Obtain a task graph for calculating values of A,B,C from the following expressions: [8]

A = sin(x²y) + cos(xy²) + exp(x²)

B = g(p) + exp (-x*f(y)) + h(x²) + f(y)g(p)

C = f(x²) + sin(g(p)) + cos² (h(y²))

Assuming that 3 processors are available, obtain a task assignment to processors assuming the given

timings for various operations.

Also compare the time obtained by your assignment with the ideal time needed to complete a job with 3

processors.

Timings for Multiply, sin, cos, exp: 2 units

g(x), f(x), h(x) : 3 units

Remaining operations : 1 unit

Section II

Q-4 a. What is the function of parallelising compiler? Differentiate between implicit and explicit parallelism.

[3]

b. What is condition variable? Write the advantages of using it. Give example using pthread library.

[3]

c. Define ‘parallel processing’. Why should one use it? Name few applications where it should be used. [3]

Q-5 a. Describe SIMD computer organization and its characteristics in detail. [4]

b. Discuss about the functionality to be provided for group communication in message passing

programming model. [4]

Q-5 a. Draw a block diagram of distributed memory model of parallel computer. Write its advantages over shared memory model. [4]

b. What do you mean by vector processor? Where should it be useful? Explain possible vector

instructions in brief. [4]

Q-6 a. What is pipeline architecture? Draw the architecture. Write about different possible classifications of pipeline processors. [4]

b. Write about the ‘Support from OS in multiprocessing’. [4]

OR

Q-6 Write differences: [8]

a. PVM vs. MPI

b. Fork vs. pvm_spawn

c. FORALL statement vs. FORALL construct in HPF Fortran

d. Process vs. thread

Gujarat University

MCA Semester IV

CBOM

Date: 22^nd January, 1992 Marks: 50

Instructions:

1. Question no. 1 and 5 are compulsory.

2. From the rest of the questions in each section attempt any two.

3. Answer each section in separate answer books.

Section I

Q-1 (a) A machine tool company conducts a job-training program for machinists. Trained machinists are used as

teachers in the program at a ratio of one for every ten trainees. The training program lasts for one month.

From past experience it has been found that out of ten trainees hired, only seven complete the program

successfully (the unsuccessful trainees are released). [7]

Trained machinists are also needed for machining and the company’s requirements for the next three months are as follows:

January 100

February 150

March 200

In addition the company requires 250 trained machinists by April. There are 130 trained machinists available at the beginning of the year. Payroll costs peer month are:

Each trainee $400

Each trained machinist 700

(machining or teaching)

Each trained machinist idle 500

(Union contract forbids firing trained machinists)

Set up the linear programming problem that will produce the minimum cost hiring and training schedule and meet the company requirements.

(b) Consider the following problem: [2]

Max 3x1 + 4x2 + 6x3

S.t., x1 + x2 + x3 <=1 0

2x1 + 3x3 <=50

x3 >= 0 and x1and x2 are unconstrained in sign.

You know that simplex assume that all the variables are restricted in sign. How will you tackle this in the

above problem. Do not solve. Just formulate the new problem.

Q-2 (a) For a minimization problem of LP. Consider the following simplex problem: [6]

Cj 0 1 -3 0 2 0 ans

X1 x2 x3 x4 x5 x6

- x1 - 5/2 - ¼ 2 - 10

- x2 - -1/2 - ¼ 0 - 8

- x4 - -5/2 - -1/4 8 - 1

Zj - - - - - - -

Cj-Zj - - - - - - -

Complete the above simplex tableau by filling up the missing entries. Check whether the solution is

optimal or not. If not perform one more iteration and comment.

(b) “Assignment Model is a special case of Transportation model” comment. [2]

Q-3 (a) State the algorithm of Revised simplex. [3]

(b) Consider the following transportation problem: [5]

Destinations

Origins 1 2 3 4 ai

1 2 3 4 5 6

2 5 4 3 4 8

3 1 3 3 2 10

bj 4 6 8 6 24

Apply Vogel’s method to get the initial solution and the apply MODI method to find optimal solution.

Q-4 (a) Consider the following LP problem: [5]

Max Z = 3x1 + 5x2 + 6x3 + 8x4

S.t. x1 + 2x2 + 2x3 + 3x3 =8

2x1 + 5x3 + x4 >=4

3x1 + 2x2 + 2x3 + x4 <=13

x1, x2, x3 >= 0 and x4 is unconstrained in sign.

Set up the dual problem for the above and explain the interpretation of dual variables.

(b) Anand Metal Shop does custom metal working for a number of local customers. AMS has currently five

jobs to be done and have five machines to do them. The cost matrix gives the cost of processing each job on any machine. Because of specific job requirement and machine specifications, certain jobs cannot be done on certain machines. These have been shown by X in the cost matrix. The assignment of jobs to machines must be done on a one-to-one basis. The objective is to assign the jobs to the machines so as to minimize the total cost within the restrictions mentioned above. [3]

Cost matrix

Jobs

Machines 1 2 3 4 5

1 80 40 X 70 40

2 X 80 60 40 40

3 70 X 60 80 70

4 70 80 30 50 X

5 40 40 50 X 80

Section II

Q-5 Explain the following: [9]

1. Characteristics of queuing models

2. Slacks

3. Methodology of solving OR problems

Q-6 (a) Derive expressions for Po, Pn, Ls, Lq, Ws and Wq for (M/M/1) : (N/FCFS) (Notations are as usual).

[5]

(b) Customer arrive at a box office window, being manned by a single individual according to a Poisson

input process with a mean rate of 30 per hour. The time required to serve a customer has an exponential

distribution with a mean of 90 seconds. Find the average waiting time of a customer.

Also determine the average number of customers in the system queue length. [3]

Q-7 (a) Patients arrive at a clinic according to a Poisson distribution at the rate of 30 patients per hour. The

waiting room does not accommodate more than 14 patients. Examination time per patient is exponential

with mean rate 20 per hour. [4]

(i) Find the effective arrival rate at the clinic.

(ii) What is the probability that an arriving patient will not wait? Will he find a vacant seat in the room?

(iii) What is the expected waiting time until a patient is discharged from the clinic?

(b) What is crashing? State the algorithm used in algorithm. [4]

Q-8 (a) In the following table optimistic, most-likely and pessimistic times are respectively shown against each

connected activity from 10 to 100 in a project. Find the critical path by constructing a network. [4]

The scheduled completion time for the project is 4 days. Calculate the probability of finishing the project

within this time (given that 89.5% probability corresponds to a normal deviation of +1.25).

Activity Times Activity Times

10-20 4,8,12 20-30 1,4,7

20-40 8,12,16 30-50 3,5,7

40-50 0,0,0 40-60 3,6,9

50-70 3,6,9 50-80 4, 8,6

60-100 4,6,8 70-90 4,8,12

80-90 2,5,8 90-100 4,10, 16

(b) Construct the network diagram with the following relationship. Find the critical path: [4]

1. A and B are the first activities of the project

2. A and B precede C

3. C precedes D

4. B precedes E and F

5. F and C precedes G

6. E precedes H

7. H precedes I and J

8. D and J precedes K

9. K precedes L

10. G, I and L are terminal activities of the project

Activity A B C D E F G H I J K L

Duration 5 3 2 1 3 2 8 1 2 3 4 7

(weeks)

MCA Question Paper

Monday, December 20, 2010

Parallel Processing 2003

Gujarat University

Section I

OR

OR

Section II

Q-4 a. Write the functionality of MPI_Init, MPI_Comm_size and MPI_Comm_rank. 3

Parallel Processing 2002

Gujarat University

Section I

OR

OR

Section II

OR

Q-6 Write differences: [8]

Operation Research 1992

Gujarat University

Section I

Q-1 (a) A machine tool company conducts a job-training program for machinists. Trained machinists are used as

You know that simplex assume that all the variables are restricted in sign. How will you tackle this in the

Section II

Q-5 Explain the following: [9]