1. Following is code for a C program that accesses elements in two different two
ID: 3548367 • Letter: 1
Question
1. Following is code for a C program that accesses elements in two different two dimensional array.
static int anArray[5][4]={{1, 2, 3, 4}, {10, 20, 30, 40},
{16, 15, 14, 13}, {11, 21, 31, 41},
{15, 14, 13, 12}};
static short mulArray[5][4] = {{2, 2, 3, 5, 1}, {3, 5, 1, 2, 2}, {3, 4, 5, 6, 1},
{2, 7, 1, 2, 2}, {8, 7, 2, 2, 1}};
int main (int argc, char **argv)
{
int idx, jdx;
for (jdx = 0; jdx < 4; jdx++) {
for (idx = 0; idx<4; idx++) {
anArray[idx][jdx] = anArray[idx][jdx] * mulArray[idx][jdx] + 1;
}
}
}
1.Suggest a simple change to the code that will make better use of spatial locality and increase the cache hit rate.
2.Unroll the for loop so that two elements are calculated in each iteration, instead of one.
Explanation / Answer
1. Interchange idx and jdx loops so that elements are accessed row wise like a[1][0], a[1][2], a[1][3], a[1][4] and next row a[2][0] ... In C arrays are stored sequentially in memory means a[1][0] comes after a[0][5]. So when you are accessing coloumn wise a[1][2], a[1][3], a[1][4] you are making the program jump back and forth unnecessarily.
2.Since you are doing it in 4x4 you can take advantage of symmetry. you can calculate a[i][j] and a[j][i] in a single iteration.
static int anArray[5][4]={{1, 2, 3, 4}, {10, 20, 30, 40},
{16, 15, 14, 13}, {11, 21, 31, 41},
{15, 14, 13, 12}};
static short mulArray[5][4] = {{2, 2, 3, 5, 1}, {3, 5, 1, 2, 2}, {3, 4, 5, 6, 1},
{2, 7, 1, 2, 2}, {8, 7, 2, 2, 1}};
int main (int argc, char **argv)
{
int idx, jdx;
for (idx = 0; jdx < 2; jdx++) {
for (jdx = 0; idx<2; idx++) {
anArray[idx][jdx] = anArray[idx][jdx] * mulArray[idx][jdx] + 1;
anArray[4-idx][4-jdx] = anArray[4-idx][4-jdx] * mulArray[4-idx][4-jdx] + 1;
}
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.