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
![T_{run}=N^3 \times [T_{load}+T_{comp}+T_{store}]\\T_{run}=1000^3 \times [300T+\frac{T}{2}+100T]\\T_{run}=1000^3 \times [400.5T]\\T_{run}=200.25 s](https://tex.z-dn.net/?f=T_%7Brun%7D%3DN%5E3%20%5Ctimes%20%5BT_%7Bload%7D%2BT_%7Bcomp%7D%2BT_%7Bstore%7D%5D%5C%5CT_%7Brun%7D%3D1000%5E3%20%5Ctimes%20%5B300T%2B%5Cfrac%7BT%7D%7B2%7D%2B100T%5D%5C%5CT_%7Brun%7D%3D1000%5E3%20%5Ctimes%20%5B400.5T%5D%5C%5CT_%7Brun%7D%3D200.25%20s)
Total Wasted time is given as
![T_{waste}=N^3 \times [T_{load}+T_{store}]\\T_{waste}=1000^3 \times [300T+100T]\\T_{waste}=1000^3 \times [400T]\\T_{waste}=200 s](https://tex.z-dn.net/?f=T_%7Bwaste%7D%3DN%5E3%20%5Ctimes%20%5BT_%7Bload%7D%2BT_%7Bstore%7D%5D%5C%5CT_%7Bwaste%7D%3D1000%5E3%20%5Ctimes%20%5B300T%2B100T%5D%5C%5CT_%7Bwaste%7D%3D1000%5E3%20%5Ctimes%20%5B400T%5D%5C%5CT_%7Bwaste%7D%3D200%20s)
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
![T_{run}=N^3 \times [T_{load}+T_{comp}]+N^2 \times [T_{linit}+T_{store}]\\T_{run}=1000^3 \times [200T+\frac{T}{2}]+1000^2 \times [100T+100T]\\T_{run}=1000^3 \times [200.5T]+1000^2 \times [200T]\\T_{run}=100.35 s](https://tex.z-dn.net/?f=T_%7Brun%7D%3DN%5E3%20%5Ctimes%20%5BT_%7Bload%7D%2BT_%7Bcomp%7D%5D%2BN%5E2%20%5Ctimes%20%5BT_%7Blinit%7D%2BT_%7Bstore%7D%5D%5C%5CT_%7Brun%7D%3D1000%5E3%20%5Ctimes%20%5B200T%2B%5Cfrac%7BT%7D%7B2%7D%5D%2B1000%5E2%20%5Ctimes%20%5B100T%2B100T%5D%5C%5CT_%7Brun%7D%3D1000%5E3%20%5Ctimes%20%5B200.5T%5D%2B1000%5E2%20%5Ctimes%20%5B200T%5D%5C%5CT_%7Brun%7D%3D100.35%20s)
Total Wasted time is given as
![T_{waste}=N^3 \times [T_{load}]+N^2 \times [T_{init}+T_{store}]\\T_{waste}=1000^3 \times [200]+1000^2 \times [100T+100T]\\T_{waste}=1000^3 \times [200T]+1000^2 \times [200T]\\T_{waste}=100.1 s](https://tex.z-dn.net/?f=T_%7Bwaste%7D%3DN%5E3%20%5Ctimes%20%5BT_%7Bload%7D%5D%2BN%5E2%20%5Ctimes%20%5BT_%7Binit%7D%2BT_%7Bstore%7D%5D%5C%5CT_%7Bwaste%7D%3D1000%5E3%20%5Ctimes%20%5B200%5D%2B1000%5E2%20%5Ctimes%20%5B100T%2B100T%5D%5C%5CT_%7Bwaste%7D%3D1000%5E3%20%5Ctimes%20%5B200T%5D%2B1000%5E2%20%5Ctimes%20%5B200T%5D%5C%5CT_%7Bwaste%7D%3D100.1%20s)
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>
