Answer:
<em>For 1st algorithm</em><em>: The total run time is 200.25 s, while that of total waste time is 200 sec and the percentage of the waste time is 99.8%.</em>
<em>For 2nd algorithm:</em><em>The total run time is 100.35 s, while that of total waste time is 100.1 sec and the percentage of the waste time is 99.75%.</em>
Explanation:
As the complete question is not visible, therefore, the question is searched online and following reference question is obtained.
Following data is given as
Floating point operation time=T/4
Memory Access Time =100T
Frequency =2 GHz
Number of Cycles=1000
<u>1st Algorithm</u>
<em>/*dgemm0: simple ijk version triple loop</em>
<em>algorithm*/</em>
<em>for (i=0; i<n; i++)</em>
<em>for (j=0; j<n; j++)</em>
<em>for (k=0; k<n; k++)</em>
<em>c[i*n+j] += a[i*n+k] * b[k*n+j];</em>
First by rewriting the operation inside the inner loop:
= + ×
Now first A, B and C are loaded into the registers so
For 2 floating point computations (addition and multiplication)
Finally, to store and repeat the cycle as N^3 times the time is estimated as
Total Run time is given as
Total Wasted time is given as
Percentage of Waste time is given as
<em>The total run time is 200.25 s, while that of total waste time is 200 sec and the percentage of the waste time is 99.8%.</em>
<u>2nd Algorithm</u>
<em>/*dgemm1: simple ijk version triple loop</em>
<em>algorithm with register reuse*/</em>
<em>for (i=0; i<n; i++)</em>
<em>for (j=0; j<n; j++) {</em>
<em>register double r = c[i*n+j];</em>
<em>for (k=0; k<n; k++)</em>
<em>r += a[i*n+k] * b[k*n+j];</em>
<em>c[i*n+j] = r;</em>
<em>}</em>
Initialize register r with the content of C for N2 Times as given as
Time for Loading Operands A and B into registers for N3 Times is given as
For 2 floating point computations (addition and multiplication)
Final Memory update to store result in the register r to the memory for N2 Times
Total Run time is given as
Total Wasted time is given as
Percentage of Waste time is given as
<em>The total run time is 100.35 s, while that of total waste time is 100.1 sec and the percentage of the waste time is 99.75%.</em>
