Hall Ticket No Question Paper Code: BCS003
INSTITUTE OF AERONAUTICAL ENGINEERING
(Autonomous)
M.Tech I Semester End Examinations (Regular) February, 2017
Regulation: IARE-R16
HIGH PERFORMANCE ARCHITECTURE
(Computer Science and Engineering)
Time: 3 Hours Max Marks: 70
Answer ONE Question from each Unit
All Questions Carry Equal Marks
All parts of the question must be answered in one place only
UNIT I
1. Illustrate the primary compiler problem for vector pipelined machines.
What is Bernstein's condition? Given an example of loop that violates the third Bernstein
Condition.
2. Dependences represent two kinds of constraints on program transformations- What are they?
Give an example for each.
Movement of statements must be prohibited from their original iteration vectors to avoid transformations
Justify with a suitable example.
UNIT II
3. Test for dependences on S. Write down the subscripts. Which positions are separable, which are
coupled? Which dependence test would you apply to each position?
i. for k<100;
for j<100;
for i<100;
S



ii. for k<100;
for j<100;
for i<100;
S



Outline the Subscript Partitioning Algorithm
Page 1 of 3
4. Construct valid breaking conditions for the following
for k<100;
for j<100;
for i<100;
S



Explain briefly delta test for coupled groups with a suitable example.
UNIT III
5. Discuss legality of loop interchange with a suitable example.
Consider the following code
DO I 100
S1 T
S2 T T
S3 T
S4 T T
ENDDO
What will be the effect of renaming the scalar T
6. What is loop alignment? Explain with a suitable example.
Consider the following loop-nest
for i 1:100
for j 1:100
S1
S2


Can loop interchange be used here to parallelize or vectorize the loop.
UNIT IV
7. In general, backward branches are complicated Justify
Outline the procedure for Strip Mine and Interchange.
8. Exit branches are more complicated to eliminate than are forward branches Comment.
Illustrate how Simple Blocking algorithm performs on the inner loop of matrix multiplication
after loop interchange:
DO J N
DO K N
DO I N

ENDDO
ENDDO
ENDDO
Page 2 of 3
UNIT V
9. Explain how different types of dependences can affect memory hierarchy management.
Consider the following code
DO I N
DO J N
0.0
DO K N

ENDDO
ENDDO
ENDDO
What is the effect of using unroll-and-jam with a factor of 2 to each of the outer loops?
10. Bring out the three-phase for pruning edges.
What is the impact of loop order on register reuse?