Homework Description

This problem focuses on execution time analysis. Consider the C program listed below:

$```$

int arr$1[256]$;

int arr$2[256]$;

int foo$($int flag$)\{$

int i;

int sum $=0$;

if $($flag$)\{$

for$($i$=0$;i$<mn>2</mn><mn>5</mn><mn>6</mn>$;i$++)\{$

arr$1[$i$]=$ i;

arr$2[$i$]=2*$i;

$\}$

$\}$

for$($i$=0$;i$<mn>2</mn><mn>5</mn><mn>6</mn>$;i$++)$

sum $+=$ arr$2[$i$]-$arr$1[$i$]$;

return sum;

$\}$

$```$

Assume that this program is run on a processor with a data cache of $4096$ bytes. Each block of the cache is $128$ bytes. Memory addresses are of $32$ bits. Data in arr$1$ and arr$2$ are stored in contiguous memory locations, i$.$e$.,$ in a sequence as arr$1[0],$ arr$1[1],....,$ arr$1[255],$ arr$2[0],$ arr$2[1],..,$ arr$2[255].$

$($a$)$ How many paths does the function foo$()$ of this program have? Describe what they are.

$($b$)$ If the cache is a direct mapped cache, how many bits in a $32-$bit address are used for block offset, set index and tag, respectively?

$($c$)$ Let $\backslash ($ T $\backslash )$ denote the execution time of the second for loop in the program. How does executing the first for loop affect the value of $\backslash ($ T $\backslash )?$ Explain your answer.

The following question is for EECE. $5520$ students only:

$($d$)$ if the cache is a two$-$way associative cache $($which has two cache blocks in a set$),$ would the cache benefit this foo$()$ function? Explain your answer.

Requirement

Please show your work and include as much details as possible.