RITS, BHOPAL
M.Tech I SEM (CSE)
MCSE (103) - ADVANCED COMPUTER ARCHITECTURE
Note: Solve all the questions.
Q.1 (a) Give the classification criteria of parallel computers suggested by Handler?
(b) Differentiate between a vector processor and an array processor from the view of their
Characteristics?
Q.2 (a) Describe the following terminology associated with pipeline computers:
(i) Simple cycle (ii) Greedy cycle
(iii)Forbidden latency (iv) Bottleneck
(b) Suppose you have 25 magnetic tapes each containing 40 GB . Assume that you have
enough readers to keep any network busy. how long will it take to transmit the data over
a distance of 1 KM? Assume the choice are category 5-twisted pair wire at 100 MBPS.
multimode fiber at 1000 Mbps and Single mode fiber at 2500 Mbps.
Q.3 (a) Consider the following pipeline reservation table:
1 2 3 4 5 6
S1 x x
S2 x x
S3 x
S4 x x
(i) What are the forbidden latencies and initial collision vector?
(ii) Draw the State transition diagram for scheduling pipeline?
(iii) Determine the minimal average latency associated with the shortest greedy cycle?
(iv) Determine the pipeline throughput corresponding to the MAL and given p?
(b)Explain the following terminology associated with SIMD computers.
(i) Lock- Step Operation
(ii) Masking of processing elements
(iii) shuffle exchange functions
(iv) Recalculating networks
(v) Cube routing functions
(vi) Adjacency search
(vii) Bit serial associative processor
Q.4 (a)Describe the type of pipeline for efficiency computing matrix multiplication?
(b) Explain the difference among UMA, NUMA, COMA and NORMA architecture?
Q.5 (a) Consider an Omega network with N inputs and N outputs where N=2m. Describe how to
set the exchange switches so that every input i is connected to output j where j differ from i
by 2k for some fixed K<M, O< i C N-1 ?
(b) Describe at least four characteristics of MIMD multiprocessor that distinguish them
from multicomputer systems or computer networks?
Q.6 (a) Write a parallel algorithm to implement the concurrent quick sort algorithm?
(b) Give parallel version of any typical serial algorithm and propose the architecture to
implement the same?
Q.7 (a) Describe the following terminology associated with multiprocessor system:
(i) A cluster of computer modules
(ii) Private cache versus shared cache.
(iii) Semaphore for synchronization
(iv) Multiport Memory
(v) Master-Slave Operating system
(vi) Floating supervision System
(vii) Explicit parallelism
(viii) Computation communication trade-off
(b) A sequential program consists of the following five statements, S1 through S5.
Considering each statement as a separate process, clearly identify input set Ii and output
set Oi of each process. Restructure the program using Bernstein's conditions in order to
achieve maximum parallelism between processes. If any pair of processes cannot be
executed concurrently, specify which of the three conditions is not satisfied.
S1: A= B+C
S2: C=BxD
S3: S=0
S4: Do I = A, 100
S = S + X (I) End Do
S5: IF (S .GT. 1000) C = C x 2
Q.8 (a) Explain data dependence and explain various kind of data dependency with example?
(b)Define the following basics terms associated with memory hierarchy design with
example:
(1) Virtual address space (2) Physical address space (3) address mapping (4) cache block
(5) Multilevel page table (6) Hit ratio (7) Page fault (8)Hashing function
(9)Inverted page table (10) memory replacement policies.
Q.9 (a) Prove that a K-stage linear pipeline can be at most K times faster than that of a non
pipelined serial processor?
(b) Distinguish among computer terminologies in each of the following groups:
(1) Data processing, information processing, knowledge processing, and intelligence
processing.
(2) Batch processing, multiprogramming, time sharing, and multiprocessing.
(3) Uniprocessor systems versus multiprocessor systems.
(4)parallelism versus pipelining.
(5) Parallelism versus parallel processing.
(6) Serial processing versus parallel processing.
(7) Control flow computers versus data flow computers.
Q.10 (a) Describe the following terminologies associated with pipeline computers and vector
processing:
(i) Static pipeline (ii) Dynamic pipeline (iii) Unifunctional pipeline (iv) Multifunctional
pipeline (v)Pipeline Efficiency (vi) Pipeline Throughput
(b).Let A be a 2 ×2m matrix stored in row-major order in the main memory .prove the
m
transposed matrix AT can be obtained by performing m perfect shuffles on A.
Q.11 (a). Consider an N-input omega network where each switch cell is individually controlled
and N=2n
(b)How many different permutation functions (one-to one and onto mapping) can be
defined over N inputs?
Q.12(a)How many different permutation function can be performed by the omega network in one
pass? If N=8, what is the percentage of permutation functions that can be performed in
one pass?
(b) Prove or disprove that the omega network can perform any shift permutation in one
pass. The shift permutation is defined as follows: given N=2n inputs, a shift permutation
is either a circular left shift or a circular right shift of k position. Where 0≤ k<N
