/*
        This program is similar to one from:
                Computer Architecture A Quantitative Approach, 2nd Edition
                John Hennessy & David Patterson, pg. 477.
        Original code by Andrea Dusseau.
        Modified by Peter Thairu 2001
        Modified by Dianne P. O'Leary 10/2011 and 11/2013: 
                    stripped documentation
                    and changed some declarations,
                    the use of the clock routines, and the output.
*/

#include <stdio.h>
#include <time.h>
#define CACHE_MIN (1024) /* smallest array size */
#define CACHE_MAX (4 * 1024 * 1024) /* largest array size */
#define SAMPLE 10 /* to get a larger time sample */
#define SEC_NANO 1000000000.0


int x[CACHE_MAX]; 



void main()
{
  int register i, index, stride, limit, temp;
  int steps, tsteps, csize;
  double sec0, sec;
  FILE *outm;
  
  clock_t cstart, cend;
  double elapsed;

  outm = fopen("cache.m", "w+");

  fprintf(outm,"Csize = [");
  for (csize = CACHE_MIN; csize <= CACHE_MAX; csize *= 2)
       fprintf(outm, "%d \n",csize);
  fprintf(outm,"]; \n");
  fprintf(outm,"Times = [ \n");


  for(csize=CACHE_MIN; csize <= CACHE_MAX; csize = csize * 2){
    for(stride = 1; stride <= csize/2; stride = stride * 2){
      sec = 0;
      limit = csize - stride + 1; 

      steps = 0;
      do{
	cstart = clock();                                   
	for(i=SAMPLE*stride; i!= 0; i = i-1){
	  for(index = 0; index < limit; index = index + stride){
	    x[index] = x[index] + 1;
	  }
	}
	steps = steps + 1; 
        cend = clock();
        elapsed = ((double) (cend - cstart)) / CLOCKS_PER_SEC;
	sec = sec + elapsed; 
      } while (sec < 1.0); 

      tsteps = 0; 
      do{ 
	cstart = clock();                              
	for(i = SAMPLE*stride; i!= 0; i = i-1){
	  for(index = 0; index < limit; index = index + stride){
	    temp = temp + index; 
	  }
	}
	tsteps = tsteps + 1; 
        cend = clock();
        elapsed  = ((double) (cend - cstart)) / CLOCKS_PER_SEC;
	sec = sec - elapsed;  
      }while (tsteps < steps);


      printf("Size = %7d, Stride = %7d; read+write time =  %14.1f ns\n",
	     csize * sizeof(int), stride * sizeof(int), 
	     (double)(sec * SEC_NANO)/
                     (steps*SAMPLE*stride*((limit-1)/stride+1)));

      fprintf(outm,"%7d   %14.1f\n", stride * sizeof(int),
	     (double)(sec * SEC_NANO)/
                     (steps*SAMPLE*stride*((limit-1)/stride+1)));

    }
  }

  printf("temp = %20d\n",temp);  // To prevent an optimizing compiler from
                                 // removing temp from the timing loop.
  fprintf(outm,"]; \n");
  fprintf(outm, "[m,n] = size(Times); \n");
  fprintf(outm, "Ibegin = find(Times(:,1)==8); \n");  // for a 64 bit machine.
                                   // Use 4 instead of 8 for a 32 bit machine.
  fprintf(outm, "nplots = length(Ibegin); \n");
  fprintf(outm, "Ibegin(end+1) = m+1; \n");
  fprintf(outm, "figure \n");
  fprintf(outm, "hold on \n");
/* You will want to modify this a bit so that you can get a
   well-labeled plot with clearly labeled curves. */
  fprintf(outm, "for i = 1:nplots \n");
  fprintf(outm, "   plot(log2(Times(Ibegin(i):Ibegin(i+1)-1,1)), ... \n");
  fprintf(outm, "      Times(Ibegin(i):Ibegin(i+1)-1,2)); \n");
  fprintf(outm, "end \n");
  fprintf(outm, "xlabel('log2(Stride)') \n");
  fprintf(outm, "ylabel('Time (ns) for read/write') \n");

  fclose(outm);

}