18-548/15-548 Fall 1998

Homework 4:
Cache Data Organization,
& Data Management Policies

Due Wednesday September 23, 1998

Cache Data Organization

Problem 1:

Consider an L1 uniprocessor-architecture cache with the following characteristics:

1a) How many total bits are within each cache block? Support this answer with a sketch showing all the bits in one block (not only data bits, but all overhead bits as well).

1b) How many total bits are within each cache sector? Support this answer with a sketch showing all the bits in on sector (not only data bits, but all overhead bits as well -- you can "point" to the sketch of a block in (1a) instead of having to draw each block out in complete detail).

1c) How many total bits are required to implement this cache in order to get the benefit of 8 KB of cached memory locations?

Data Management Policies

Problem 2:

Consider a cache memory with the following characteristics:

2a) Assume the cache starts out completely invalidated. For each access indicate whether it is a hit, a compulsory miss, a capacity miss, or a conflict miss. Assume cache starts out completely invalidated. State in ten or fewer words why you selected each category.

read  0x0010
read  0x0014
read  0x001C
read  0x0110
read  0x001C

2b) Assume the cache starts out completely invalidated. For each access below state whether it is a "hit" or a "miss", and indicate the number of words of memory traffic generated by the access.

write 0x0024
write 0x0020
write 0x0124
read 0x0024


Problem 3:

Note: this is representative of a "hard" test question you might see on Test #1 or Test #2. Therefore it is not as obvious/straightforward as previous homework questions. You are encouraged to discuss this question with other students and the course staff to ensure that you thoroughly understand what is going on here.

You have instrumented only data references from the subroutine "sum_array" in the following program on an Alpha workstation ("long" values are 64 bits). The resultant data reads and writes have counted with a particular cache configuration. In this question you'll deduce the cache configuration used.

#include <stdio.h>
#include <stdlib.h>

void sum_array(int N, long *a, long *b, long *c, long *d, long *e)
{ int i;
  for (i = 0; i < N; i++)
  { *(a++) = *(b++) + *(c++) + *(d++) + *(e++); }

int main(int argc, char *argv[])
{ int N, offset, i;
  long *a, *b, *c, *d, *e;    /* 64-bit elements in each array */

  if (argc != 3)
  { fprintf(stderr, "\nUsage: test <size> <offset>\n"); exit(-1); }
  sscanf(argv[1], "%d", &N);      sscanf(argv[2], "%d", &offset);

  a = (long *) malloc(5 * ( (N*sizeof(long)) + offset) );
  b = a + N;
  c = b + N;
  d = c + N;
  e = d + N;

  sum_array(N, a, b, c, d, e);


The program was executed with a command line having successively higher values of N from 1 to 2100. The below graph shows the number of combined data misses for each value of N. · Bus size and word size are both 8 bytes.

{Total Data Cache Misses}

Some data that might be of interest from the above chart ar:

N   # Misses  Total Traffic (words)
500   626      2516
501   628      2533
502   629      2534
503   630      2535
504   630      2520
505   632      2537
506   633      2538
507   696      3531
508  1020      8700
509  1277     12797
510  1597     17902
511  1853     21983
512  2079     25584
513  1862     22097
514  1606     17986
515  1288     12883
516  1032      8772
517   717      3717
518   651      2646
519   653      2663
520   652      2632
521   655      2665
522   655      2650
523   657      2667
524   658      2668

Answer the following questions, giving brief support for your answer of (unsupported answers will not receive full credit).

3a) Ignoring overhead for the subroutine call, what is the theoretical minimum possible data total traffic (in 8-byte words) that this program has to move (combined into and out of the cache) for N = 500?

3b) Does the cache perform write allocation?

3c) What is the actual associativity of the cache that produced the data given? (and how did you figure that out?)

3d) How many bytes does the cache hold (data only, not counting control+tag bits)?

18-548/15-548 home page.