CS644 hw4 Caching--due Monday, Mar. 21

1.-3. P&H Ex. 5.3.2, 5.4.1-5, 5.7.1-3

4. Consider the Example on pg. 477. Find out what percentage
of the time the memory bus is in use. Worry about this for
SMP multi-core cases. See Fig. 7.2, pg. 639 to see how
the memory bus is shared in this case. Optionally, also
find how busy the memory bus is in the pg. 487-88 Example, both
with and without L2 cache.

5. A program has a large collection of name-value pairs,
where the names are set up once but the vals are rapidly changing
as the program runs.  Here are two storage schemes:

/* setup A */
#define NAMELEN 36
#define N <large number here>
struct {
  char name[NAMELEN];
  int val;
} master[N];

/* setup B--parallel arrays--old-fashioned but same storage--*/
char name[40][N];
int val[N];

One thing that often needs to be done is summing up all the vals.
For N = 10000 and N = 100000, how big is master? name? val?

a. Which storage scheme works better with a 1MB (L2) cache?
Estimate the relative times it takes to sum up all the vals
in the 4 cases (2 cases of memory layout x 2 cases of N).
Assume that the sum has recently been done, and the cache
has lots of array data still available (as much as fits.)
Assume cache access time is 4ns and memory access time is 40ns.

b. Also discuss the data placement in memory you would expect
from Java here, for an array of NameVal objects, each with
a String name and int val. Note that Strings are themselves
objects in Java, as are arrays.

6. Write a small C program called memtest.c: see the start
for it in $cs641/memtest.c and $cs641/timepack.[ch].  
Hopefully this should tell us how big the cache on sf06 is.
Also possibly how much memory it has, if that is less than 4GB. 
See what you can figure out, and write up your thoughts and
conclusions for the homework.  Also submit your code, of
course.