need help with c langauge questions Which kind of C programming practice could r

Question

need help with c langauge questions

Which kind of C programming practice could replace the literal (perhaps clumsy) source code for the inner loops of the matrix multiply shown below: c[row][col] = c[row][col] + a[row][i] * b[i][col];| Looking at the data accesses of matrices a[], b[], and c[] inside the inner loop, which datum will bring the greatest benefit by sitting in a data cache? Which matrix element is least likely to benefit from being moved into a data cache? Which optimization (AKA reduction optimization) do you suggest should be accomplished by an optimizer, to speed up execution of the original inner loop of a matrix multiply program? If you need to optimize execution speed by maximizing parallel execution of a matrix multiply, list other ideas you have about improving the inner loop. Perhaps restructuring the nest of 3 loops? Read about "tiling" (AKA "blocking") in the literature; e.g. here: http://csapp.cs.cmu.edu/2e/waside/waside-blockina.pdf Just outline in a brief paragraph the principle of what can be done.

Explanation / Answer

Question 1:

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

{

for(int j=0; j<n; j++)

{

c[row][col]+=a[row][col]*b[row][col];

}

}

Question 2:

By looking at data matrix and it's operations one can easily conclude that columns need to be in the data cache. Because columns are used most frequently.

Question 3:

For optimization of this algorithm if we use divide and conquer approach we can reduce it's s[ace complexity but time complexity will remain the same. Examples like strassen's matrix multiplication proved to be an optimization techniques which takes n2.32 running time instead of n3. We can use Dynamic programming as well to optimize this algorithm which is a proven technique for efficiency.

Related Questions

Navigate

• Browse (All)
• Browse N
• Subjects

---

---

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