Note : Question one is compulsory. Answer any three from the rest.

1. (i) Consider the execution of the following code segment. Use Bernstein’s condition to detect the maximum parallelism embedded in this code. Justify the portion that can be executed is parallel and the remaining portion that must be executed sequentially.

S1 : A = B + C
S2 : C = D + E
S3 : F = G + E
S4 : C = A + F
S5 : M = G + G
S6 : A = L + C
S7 : A = E + A

(ii) Draw a dependence graph to show all the dependences for the above code segment.

(iii) Answer the following questions:

(a) Distinguish between single threaded and multithreaded processor architecture. (more…)

Note : Question one is compulsory. Answer any three from the rest.

1. (i) What are the design parameters for pipeline processors? Discuss them briefly with examples. 5
(ii) Discuss the structure of superscalar pipelines and the factors causing pipeline stalling. 8
(iii) Consider the execution of an object code with 2,00,000 instructions on a 40 MHz processor. The program consists of four major types of instructions. The instruction mix and the number of cycles (CPI) needed for each instruction type are given below based on the result of a program trace experiment :

Instruction type CPI Instruction Mix
Arithmetic and logic 1 60%
Load/store with catche hit 2 18%
Branch 4 12%
Memory reference with catche miss 8 10% (more…)

Note : Question one is compulsory. Answer any three from the rest.

1. (i) Consider a catche (M1) and memory(M2) hierarchy with the following characteristics :
M1 : 16 K words, 50 ns access time
M2 : 1 M words, 400 ns access time

Assume 8 words cache blocks and a set size of 256 words with set associative mapping.

(a) Show the mapping between M2 and M1.
(b) Calculate the effective memory access time with a catche hit ratio of h = 0.95.

(ii) Answer the following questions with reference to processors and memory hierarchy: (more…)

Note : Question one is compulsory. Answer any three from the rest.

1(i) The execution times (in seconds) of four programs on three computers are given below:

Execution Time (in seconds)
Program Computer A Computer B Computer C
P1 1 10 20
P2 1000 100 40
P3 500 1000 50
P4 100 500 100

Assume that 100,000,000 instructions were executed in each of the four programs. Calculate the MIPS rating of each program on each of the three machines. Based on these ratings. Can you draw a clear conclusion regarding the relative performance of the three computers?

(ii) Answer the following questions:
(a) What causes a processor pipeline to be underpipelined? (more…)

Note : Question one is compulsory. Answer any three from the rest.

1. (i) Consider a catch (M1) and memory (M2) hierarchy with the following characteristics: M1: 16 K words, 50 ns access time M2: 1 M words, 400 ns access time Assume eight word catche blocks and a set size of 256 word with set-associative mapping

� Show the mapping between M2 and M1
�Calculate the effective memory access time with a catch hit ratio of h = 0.95.

(ii) What causes a processor pipeline to be under pipelined?

(iii) What is meant by a hierarchical bus system for multiprocessing system? `

2 Discuss the following the context of parallel languages and compilers:

(i) Parallel code generation
(ii) Parallel flow control
(iii) Parallel arrays

3(i) Describe the important characteristics of parallel algorithms which are machine implementable.

(ii) Discuss the is efficiency concept in the context of the efficiency of a parallel algorithm.

4. Discuss the following in the context of computer architecture:

(i) Distributed Arbitration
(ii) Snoopy bus protocol
(iii) Branch handling in instruction pipeline

5. (i) Discuss the architectural environment for a multithreaded computer model.

(ii) What are the limitations of conventional UNIX for parallel processing systems.

(iii) What is the sector mapping cache? Discuss with the help of an example.

6. Explain the structural and operational difference between register to register and memory to memory architecture in building multipipelined supercompter for vector processing. Comment on the advantages and disadvantages in using SIMD computers as compared with the use of pipelined supercomputer for vector processing.

Note : Question one is compulsory. Answer any three from the rest.

1. A low level memory system has eight virtual pages on a disk to be mapped into 4 page frames in the main memory. A certain program generated the following page trace:
1, 0, 2, 2, 1, 7, 6, 7, 0, 1, 2, 0, 3, 0

(a) Show the successive virtual pages residing in the 4 page frames with respect to above page trace using the LRU replacement policy. Compute the hit ratio in the main memory. Assume the page frames are initially empty.

(b) Repeat part (a) for the circular FIFO page replacement policy.

© In the following program, all 5 instructions are to be executed in minimum time. Assume that all are integer operands already loaded with working registers. No memory reference is needed for the operand fetch operation. Also all intermediate or final results are written back to working registers without conflicts. (more…)

Note : Question one is compulsory. Answer any three from the rest.

1.(i) Draw a table showing performance factors versus system attributes and explain them.

(ii) A 50 MHz processor was used to execute a benchmark program with the following instruction and clock cycles counts.

Instruction type Instruction count Clock cycles count
Integer Arithmetic 45000 1
Data transfer 32000 2
Floating point 15000 2
Control transfer 8000 2

Determine the effective CPI, MIPS rate and execution time for this program.

(iii) What cause a processor pipeline to be underpipelined? (more…)

Note : Question one is compulsory. Answer any three from the rest.

1.(a) Compare dynamic connection networks such as bus systems, multistage interconnection networks and crossbar switch networks in terms of the following characteristics:

(i) Bandwidth
(ii) Hardware complexity such as switching, arbitration, wires etc.
(iii) Network latency
(iv) Scalability

(b) Compare and also comment on the static connection networks: Linear Array, Ring, Binary tree, 2D-Mesh in terms of the following characteristic:

� Node degree
� Network diameter
� No. of Links
� Bisection width
� Symmetry (more…)

Note : Question one is compulsory. Answer any three from the rest.

1.(a) Explain in brief how instruction set, compiler technology, cache and memory hierarchy and CPU implementation affect the CPU performance and justify the effects in terms of program length, clock rate and effective CPI (cycles per instruction).

(b) Analyze the data dependence among the following statements in a given program fragment: LoadR1, M[100] / R1 � M[100] / LoadR2, M[104] / R2 � M[104] / MULT R1, R2 / R1 �( R1) x ( R2) / INCR1 / R1 � (R1) + 1 / STORE M[110], R1 / M[110] � (R1) / Also
� Draw a dependence graph to show all the dependences.
� Are there any resources dependence if only one copy of each functional unit is available in the CPU?

© Discuss the following terms in the context of the performance of a memory hierarchy. (more…)

Note : Question one is compulsory. Answer any three from the rest.

1. (a) What is superpipelining? How is it different from Superscalar pipeline?

(b) Analyse the data dependence of the statements of the following program:
S1: Load RA, M[20] /RA � M[20] /
S2: Load RB, M[25] /RB � M[25] /
S3: Sub RA, RB /RA � RA- RB /
S4: Mult RA, 5 /RA � RA * 5 /
S5: STORE M[20], RA /M[20] � RA /

Draw the dependence graph for the dependencies. (more…)