EE5902 Multiprocessor Systems Qn. Paper

Subject: EE5902 Multiprocessor Systems
Department: ECE Dept, NUS
Semester I, AY 2009-10 Question Paper

Here I go again. My second exam for this semester also didn’t have previous year question papers published. Remembering the questions this time was a bit tough as it contained 20 one word type questions. I have somehow managed to remember bits and pieces of up to 16 questions. The rest, I hope my friends will help me. If you have attended this exam and have any comments about this post or if you know any missing questions, please post a comment. Please don’t mail them to me. I don’t need them. I am doing this in the hope that I may help some students in the upcoming batches. If you find this helpful, please leave a comment so that I know I have helped someone. Thanks to my 2 friends who helped me in remembering these questions.
Q1. [These questions are not in the order in which they are asked. I am putting the questions I remember in the order I jot down them right after the exam]
1. State only the correct statements
a. [Don’t Remember]
b. Data parallelism is not scalable [Something similar]
c. [Don’t Remember]
d. Control Parallelism is not limited by pipeline length
The correct statements are __________
2. [Summation]j,k [Summation]j,k(aik + bik) Computations like these are best suited in __________
3. Write a typical RT for a CV 1011 in the space provided (page 278)
4. __________ level parallelism is prohibiting the increment of factor k for a k-issue superscalar architecture
5. Baseline network has only one path from input to output (T/F)
6. For a superscalar processor of degree m and n instructions, as n tends to infinity, the speed up factor becomes __________ (notes chap 6, page 55)
7. Pentium is RISC in the higher level and computes CISC operations in the inner core level (T/F) (Notes Chap 3, slide 30)
8. If hit ratio of level Mi of memory is pi, the expression for access frequency for Mi __________ (Notes Chap 3, slide 69)
9. If the number of processing elements are between 1024 and 16384, it is typically considered to be a __________ (page 32)
10. If the time complexity of a problem is of O(2^n . n^2), it is clearly of polynomial complexity (T/F) (page 34)
11. What is the time complexity of the expression () [Forgot the exact expression]
12. MAL is greater than or equal to maximum number of check parks in the RT and less than or equal to the average latency of any greedy cycle. Also the average latency of any greedy cycle will be one greater than the number of ones in the initial collision vector. So, MAL is greater than the number of ones in the ICV. Point out what is wrong with this statement in the space provided below.
13. Non-linear pipelines and the reservation tables have a many to many mapping (T/F)
14. Loop level parallelism is considered to be __________ grain with less than 2000 instructions (Page 61 and it was given 200 instructions, not 500)
15. Power is proportional to the square of the frequency in embedded processors. (T/F) [Not sure about this statement, but it was relation between power and frequency which is given in slide 40 in the first lecture]
16. [One problem with coming up with an expression with some T1, T2, T3 and T3 and E1, E2, E3 and E4 for something. Don’t remember, I didn’t get time to look at this as this was the last question in the set]

Q2. We have a system with cache and memory. The cache capacity is 8 blocks and each block is one word. We have a 4 x 10 array, X(i, j) which is stored in main memory from address 7A00 to 7A27 in a column major fashion. (7A00 contains X(0, 0), 7A01 contains X(1, 0) etc). MM is also word addressable. The following program is executed

TOT = 0
For j = 0 to 9, do
TOT = TOT + x(0, j)
End do
AVE = TOT / 10;
For i = 9 to 0, do
X(0, i) = X(0, i)/AVE; /* Normalizing all the elements in the first row */
End do

Run the LRU algorithm on the above code for both the following scenarios
(i). Direct Mapping
(ii). Associative Mapping
Draw the mapping diagram also.
Hint: The memory is in hex [and some more, which I don’t remember]

Q3. A computer architect wants to connect 8 processor nodes to 8 memory modules using an MIN. He/she decides to use a baseline network, but wanted to have more connections from input to output and decided to have 5 stages. The first 3 stages – stage 1 to stage 3 – is done as normal self-routing network. Then from stage 5 through stage 3 is also self-routing network. For e.g., if we partition the whole network into two parts around stage 3, we will get exact mirror image. For this network, answer the following questions,
a. Draw the above stated network
b. How many paths are there for a given input-output pair
c. Device a strategy to route a given input node to an output node
d. A processor connected to the first switch in the first stage, P(0) is connected with memory module in the last switch in the last stage – M(7). Now the processor P(3) wants to connect to M(3). Show how the connections are reconfigured for the above design (qn. Q3 - c)

Q4. (Same question as problem 6.13 in text) For the same 4 pipelined stage in Qn 6.13,
a. Specify the reservation table
b. Find the collision vector
c. Draw the state diagram and mark the transitions

Q5. Formulate the differential equations for the reliability model for memory with state diagrams and with full equations (Same question as the reliability model for memory in notes)

[---- Questions Paper Ends Here ----]

Some doubts I had during my preparation for this exam. There are more which I never wrote down and now I don’t remember them. I had all these doubts by the end of my preparation which was just before the exam, so I didn’t get time to clarify them.

Qn. 19 in self test. The answer given is False. But in the text page 55 says “Bernstien’s conditions simply imply that two processes can execute in parallel if they are flow independent, anti independent and output independent”. Does it directly contradict the answer or is it ‘cos it doesn’t say anti-independence?
Qn. 28 in self test. The answer given is CRCW, but in text page 37, 38, it is clear that the ‘uncommon’ type is ERCW.
Qn. 43 in self test. “All processors need not be executing an instruction concurrently in a MIMD machine”. The answer for this one says False as per the self test answers, but the qn no. 10 in the qn bank “In a MIMD computer, all processors must execute the same instruction at the same time simultaneously” which is given as False too, directly contradicts this.

Page 346 in text. The input to the switch from both p1 and p2 shows e1 as the increment factor. It should be e1 and e2 right?
Can we consider pipelines as a MISD stage or a systolic array. Cos they are multiple fn units acting on a single data stream with specific function. In linear pipelines, the stages cannot be programmed. But in non-linear, different stages can be programmed also right?
In the Pentium, why do we need 2 bits for the history in the BTB? We need only one bit right?
Qn. 29 in self test, given a CV, how can we uniquely say the number of pipeline stages in the RT? Even is no stage is left unutilized in any cycle, the m of the CV will be less than n-1 right?

Some points I wish to note here, (just like my previous post)
1. I am not sure about the answers of the multiple choice questions and that is why I have given pointers to the page where they are mentioned.
2. There is no guarantee for any of these questions to be exactly the same as seen in the question paper. I simply wrote down what I remember after the exams.
3. I am publishing this the next day of my exams and so I don’t know the results, yet.
4. Please don’t send me mails asking for answers, please post comments in the comments section so that someone else may answer.