Consider the following program and its flowchart. The execution times of the blo
ID: 3732952 • Letter: C
Question
Consider the following program and its flowchart. The execution times of the blocks are as follows:
B1 = 6 cycles
B2 = 2 cycles if branch taken, 5 cycles if not taken.
B3 = 3 cycles if branch taken, 6 cycles if not taken.
B4 = 7 cycles.
B5 = 1 cycle.
for (i-0, z-0; i2) z + x[i]*c[i]; = z B2: loop test B3: test x[i] B4: update z B5: loop update a) What is the maximum number of times that each block is executed? b) What is the minimum number of times that each block is executed? c) What is the maximum execution time of the program in clock cycles? d) What is the minimum execution time of the program in clock cycles?Explanation / Answer
a) The Maximum number of times that each block is executed?
Ans:- B1 = Initialize = 1 Times (Loop Initialization happens only once at the start of the loop)
B2 = Loop Test = 16 Times (Loop starts from 0 and goes till 15 when it evaluates to false, so 16 times it tests the looping condition).
B3 = Test X[i] = 16 Times (for each value of i from 0 to 15, X[i] is evaluated)
B4 = Update Z = 13 Times (Executed when i > 2 and not executed for i = 0,1,2).
B5 = 16 Times
b) The Minimum number of times that each block is executed?
Ans:- B1 = Initialize = 1 Times (Loop Initialization happens only once at the start of the loop)
B2 = 1 Time (when the loop condition evaluates to false, ie i = 17, loop terminates)
B3 = 0 Times (if loop condition evaluates to False, loop body doesnt gets executed)
B4 = 0 Times (if loop condition evaluates to False, loop body doesnt gets executed)
B5 = 0 Times (if loop condition evaluates to False, loop body doesnt gets executed)
c) Maximum Execution Time of the Program in Cycles:-
B1 = 1*6 = 6, B2 = 16 * 2 = 32, B3 = 3*6 ( 3 times branch not taken) + 13 *3 (13 times branch taken) = 18 + 39 = 57,
B4 = 13 * 7 = 91, B5 = 16*1 = 16
Total = 6 + 32 + 57 + 91 + 16 = 202 Clock Cycles
d) Minimum Execution Time of the Program in Cycles:-
B1 + B2 + B3 + B4 + B5 = 6 + 1*5 (Branch Not Taken) = 6 + 5 = 11 Clock Cycles.
Please let me know in case of any clarifications required. Thanks!