Question

Half of the integers stored in the array data are positive, and half are negative. Determine the

Absolute speed of the following algorithm, assuming; the time to execute a memory access is

100 nanoseconds and that all other operations (arithmetic, register access, etc0 take 10 nanoseconds

for (int i= 0; i<1000000;i++)

{ if (data[i] <0)

Data [i] = data [i] *2;

}

Answer 1

Check the explanation

Step-by-step explanation:

Below is the approx assembly code for above `for loop` :-

1). mov ecx, 0

2). loop_start :

3). cmp ecx, ARRAY_LENGTH

4). jge loop_end

5). mv temp_a, array[ecx]

6). cmp temp_a, 0

7). branch on nge

8). mv array[ecx], temp_a*2

9). add ecx, 1

10). jmp loop_start

11). loop_end :

Assumptions :-

*ARRAY_LENGTH is register with value 1000000

*temp_a is a register

Frequency of statements :-

1) will be executed one time

3) will be executed 1000000 times

4) will be executed 1000000 times

5) will be executed 1000000 times

6) will be executed 1000000 times

7) `nge` will be executed 1000000 times, branch will be executed 500000 times

8) will be executed 500000 times

9) will be executed 1000000 times

10) will be executed 1000000 times

Cost of statements :-

1) 10 ns

3) 10ns + 10ns + 10ns [for two register accesses and one cmp]

4) 10ns [for jge ]

5) 10ns + 100ns + 10ns [10ns for register access `ecx`, 100ns for memory access `array[ecx]`, 10ns for mv]

6) 10ns + 10ns [10ns for register_access `temp_a`, 10ns for mv]

7) 10ns for nge, 10ns for branch

8) 30ns + 110ns + 10ns

10ns + 10ns + 10ns for temp_a*2 [10ns for moving 2 into a register, 10ns for multiplication],

110ns for array[ecx],

10ns for mv

9) 10ns for add, 10ns for `ecx` register access

10) 10ns for jmp

Total time taken = sum of (frequency x cost) of all the statements

1) 10*1

3) 30 * 1000000

4) 10 * 1000000

5) 120 * 1000000

6) 20 * 1000000

7) (10 * 500000) + (10 * 1000000)

8) 150 * 500000

9) 20 * 1000000

10) 10 * 1000000

Sum up all the above costs, you will get the answer.

It will equate to 0.175 seconds