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.

(c) 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.

P1 : X ¬ (A +B) * (A-B)
P2 : Y ¬ (C+D) * (C-D)
P3 : Z ¬ X + Y
P4 : A ¬ E × F
P5 : B ¬ (X-F) * A

(i) Use the minimum number of working registers to rewrite the above program using plus, minus, multiplication and divide exclusively. Assume a fixed instruction format with 3 register field: two for sources and one for destination.

(ii) Perform a flow analysis of the assembly language obtained in part (i) to reveal all data dependence with a data dependence graph.

2.(a) Discuss the level of parallelism in program execution and the suitability of parallel computer models at each level.

(b) Characterize the architectural operation of SIMD & MIMD computes. Differentiate between multicomputers and multiprocessors based on their structures, resource sharing and inter-process communication.

3. Answer the following questions with respect to static and dynamic interconnection network.

(a) Compare and comment on static interconnection network characteristics in terms of node degree network diameter and bisection width.

(b) Compare and comment on importance of dynamic interconnection network characteristics in terms of minimum latency for unit data transfer. Writing complexity, connectivity and routing complexity.

4. (a) Discuss the four workload growth pattern, its corresponding efficiency curves and various application models of parallel computers under resource constraints and discuss various tradeoffs.

Workload growth pattern Vs Scalability
· Workload Vs Efficiency curves
· Workload Vs Memory and I/O bounds
· Application model Vs Workload Vs Memory and I/O bounds

(b) Discuss the important characteristics of parallel algorithms which are machine implement able. Also discuss suitability of parallel machines in implementation of these characteristics.

5. Answer the following questions:

(a) Explain the effect of block size, set number, associatively and cache size on the performance of set associative cache organization.

(b) With each cache organization, explain the effects of block mapping policies on the hit ratio issues.

(c) Cache flashing policies.

6. Distinguish among the following vector processing machines in terms of architecture, performance range and cost effectiveness:

(a) Full scale vector supercomputer
(b) High end mainframes or near supercomputers
(c) Mini supercomputers or supercomputer workstations.