In this exercise, we will run a program given at the bottom to evaluate the behavior of the memory system on your computer. This program can be used to evaluate the behavior of a memory system. The key is having accurate timing and then having the program stride through memory to invoke different levels of the hierarchy.

As for the code, the first part is a procedure that uses standard utility to get an accurate measure of the CPU time. The second part is a nested loop to read and write memory at different strides and cache sizes. This part is repeated many times to get accurate cache timing. The third part only measures the nested loop overhead so that it can be subtracted from the overall measured times to determine how long the accesses were. The results are output in .CSN file format to allow importing to a spreadsheet. Please keep on mind that running the program in singleuser mode or at least without other active applications will give more consistent results.

Run the code on one of your favorite machines and answer the following questions.

(a) Plot the access time results for each cache size on the y-axis and memory stride on the x-axis. Use logarithmic scale for Y-axis. To focus on cache memories and main memory access times, ignore any access times greater 100 ns.

(b) How many levels of caches are there?

(c) What are the overall size and block size of the L1-cache?

(d) What are the overall size and block size of the L2-cache?

(e) What are the overall size and block size of the L3-cache, if there is one?

(f) What are the miss penalties for the L1-cache, L2-cache, and L3-cache (if there is one)? (g) What is the time for a page fault to secondary memory (i.e., hard disk or SSD)?

Program:

// // main.c // memory_new // // Created by Ben Lee on 12/10/14. // Copyright (c) 2014 Ben Lee. All rights reserved. // //#include "stdafx.h" #include #include #include #include #include #define ARRAY_MIN (1024) /* 1/4 smallest cache */ #define ARRAY_MAX (4096*4096) /* 1/4 largest cache */ #ifndef CLK_TCK #define CLK_TCK 60 /* no. of clock ticks per second */ #endif int x[ARRAY_MAX]; /* array going to stride through */ #define BILLION 1000000000L

int label(int i) {/* generate text labels */ if (i<1e3) printf("%1dB\t",i); else if (i<1e6) printf("%1dK\t",i/1024); else if (i<1e9) printf("%1dM\t",i/1048576); else printf("%1dG\t",i/1073741824); return 0; }

int main(int argc, char **argv) { int register nextstep, i, index, stride; int csize; double steps, tsteps; float loadtime; struct timespec time_start, time_end; uint64_t total_time, loop_overhead; /* Elapsed time */ /* Initialize output */ printf(" \t"); for (stride=1; stride <= ARRAY_MAX/2; stride=stride*2) label(stride*sizeof(int)); printf(" "); /* Main loop for each configuration */ for (csize=ARRAY_MIN; csize <= ARRAY_MAX; csize=csize*2) { label(csize*sizeof(int)); /* print cache size this loop */ for (stride=1; stride <= csize/2; stride=stride*2) { /* stride = 1 4byte */ /* Lay out path of memory references in array */ for (index=0; index < csize; index=index+stride) x[index] = index + stride; /* pointer to next */ x[index-stride] = 0; /* loop back to beginning */ /* Walk through path in array for twenty seconds */ /* This gives 5% accuracy with second resolution */ steps = 0.0; /* number of steps taken */ nextstep = 0; /* start at beginning of path */ clock_gettime(CLOCK_MONOTONIC, &time_start); /* start timer */ do { /* repeat until collect 20 seconds */ for (i=stride;i!=0;i=i-1) { /* keep samples same */ nextstep = 0; do nextstep = x[nextstep]; /* dependency */ while (nextstep != 0); } steps = steps + 1.0; /* count loop iterations */ clock_gettime(CLOCK_MONOTONIC, &time_end); /* end timer */ } while ((time_end.tv_sec - time_start.tv_sec) < 20.0); /* collect 20 seconds */ total_time = BILLION * (time_end.tv_sec - time_start.tv_sec) + time_end.tv_nsec - time_start.tv_nsec; /* Total elapsed time in nsec */ /* Repeat empty loop to loop subtract overhead */ tsteps = 0.0; /* used to match no. while iterations */ clock_gettime(CLOCK_MONOTONIC, &time_start); /* start timer */ do { /* repeat until same no. iterations as above */ for (i=stride;i!=0;i=i-1) { /* keep samples same */ index = 0; do index = index + stride; while (index < csize); } tsteps = tsteps + 1.0; clock_gettime(CLOCK_MONOTONIC, &time_end); /* - overhead */ } while (tsteps