Need help with parts b and c of the question Consider the following C-code fragm

Question

Need help with parts b and c of the question

Consider the following C-code fragment: for (i=0; i less than 10; i++) {a[i] = b[i] + c[i]} Assume that -a, b, and c are arrays of 32-bit words, -The machine code for this fragment is stored in memory starting from location 00000100 Hex. Covert this code to MIPS. You must provide the numeric offset for each branch or jump instruction that you use. Assume that the CPIs for MIPS instructions are as listed below: a.lw : 5 cycles b. R-type, addi, sw, and other immediate Arithmetic instruction : 4 Cycles beq, bne, and j: 3 cycles How many clock cycles does it take to execute the C-code fragment? Assume that this code is executed by a 2.5 GHz system. What is the cpu execution time for the code?

Explanation / Answer

It depends on the compiler and the options used for compilation. If we run the above program in a linux x86 machine, the variable case should take a bit longer than the constant case assuming compiler optimization is not enabled.

Let us take the below code:

int main(int argc, char *argv[])

{

unsigned int j = 0;

int i, n = 2000000000;

for(i = 0; i < n; i++)

{

if(i & 0x1)

j += 2;

else

j += 1;

}

return j&0xFF;

}

(It does anything useful. It is just to ensure that the compiler executes the loop the specified number of times. Large value for n is chosen so that the execution time difference is prominent).

The above code is for the variable case. Removing n and using the constant in the loop condition gives the constant case.

Compiler used : gcc (v 4.1.2)
Linux-x86 machine.
time command is used to measure the elapsed time. (Eg, time <executable>)

Case (1): No Compiler optimization

Average time taken by the constant case : 4.4 seconds
Average time taken by the variable case : 4.8 seconds

There is approx 400 msec time difference. There is an explanation for the above behaviour.

If we take the assembly code of the constant case, we can see the below instruction which checks for the loop condition:

cmpl    $1999999999, -8(%ebp)

-8(%ebp) is the location of variable i. The above instruction is comparing an immediate value (constant) with a value in the memory.

If we take the assembly code of the variable case, below are the instructions used to test the loop condition.

movl    -12(%ebp), %eax
cmpl    -8(%ebp), %eax

-8(%ebp) is the location of the variable n and -12(%ebp) is the location of the variable i.
cmpl instruction cannot use both the operands from memory. Thats why, in the variable case, we see an extra move instruction to copy the value of 'i' into the register eax. Whereas, in the constant case, it is a single instruction as it is a comparison between an immediate value (number) and the memory. Since this move instruction in the variable case is inside the 'hot loop', it does spend more machine cycles than the constant case which is clearly evident when we choose a large value for 'n'.


Case (2): Compiled with -O2

Average time taken by the constant case : 1.2 seconds
Average time taken by the variable case : 1.2 seconds

Not surprisingly both took very less time than before. Also, both took the same time to execute. The assembly generated for both of them are exactly the same. The thing to be noted is, the loop test instruction is the same in variable and constant case which made a difference in Case (1).

Related Questions

Navigate

• Browse (All)
• Browse N
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.