/************************************************************************************
*                    Micro Benchmark   mbclss
*                 -----------------------------   
* File name: mbclss.c
* Author   : Yuanhua Yu
* Date     : 20/12/1999.
*
*-------------------------------------------------------------------------------------
*
*  Function:  Measuring the set size and subblock size of Cache Level I and Level II
*
*   Methods:  1. Sequential array read access
*             2. Random accessing sequence
*             3. Stride accessing sequence
*             4. Stride accessing sequence (improved) 
*
*   History:  First version : 05/10/1999
*             Second version: 20/12/1999
*
*Parameters:  STRIDE_START ---- intinial value of the stride : 1      (*4bytes)      
*             STRIDE_END   ---- max value of the stride      : 1024   (*4bytes)
*             STEP_START   ---- initial value of the step    : 256    (bytes)
*             STEP_END     ---- max value of the step        : 1024*16(bytes)
*             TOTAL_ACCESS ---- number of the accesses done  : (32768*1024*16)
*
*  Variable:  cache_size   ---- capacity of the Level-I cache in KB
*             arr_size     ---- size of the array accessed;
*             stride       ---- number of items between two accessed items
*             step         ---- increment of size of the array
*
* Functions:
*             seq_access()     :
*             rand_access()    :
*             stride_access()  :
*             stride_access_1():
*             random_sequence():
*             set_parameters() :
*             get_parameters() :
*             write_file_head():
*
*************************************************************************************/

#include <stdlib.h>
#include <stdio.h>
#include <math.h>
#include <time.h>
#include <malloc.h>
#include <string.h>

#define STRIDE_START    1               //4    bytes
#define STRIDE_END      1024            //4096 bytes
#define STEP_START      256             //256  bytes 
#define STEP_END        (1024*16)       //16384bytes

#define TOTAL_ACCESS    (32768*1024*16) //operations
#define ATYPE long

/*------------------------------------------------------------------------------------*/

void seq_access(FILE *fp, long cache_size, long step);
void rand_access(FILE *fp, long cache_size, long step);
void stride_access(FILE *fp, long cache_size);
void stride_access_1(FILE *fp, long cache_size);
void random_sequence(volatile long *array, long max_index);
void write_file_head(FILE *fp, char mname[255],int option);
void set_parameters(char mname[15],long *cache_size);
void get_parameters(char mname[15],char fname[25],long *cache_size);

/*------------------------------------------------------------------------------------*/


void main(char **av, int ac)
{
    long cache_size, step;
    char file_name[255],machine_name[255];
    int option;
	
    FILE *fp;

	option = 1;
	while(option >=0 && option <6)
	{
	     printf("\n\n  Measuring the Set and Subblock Size of Cache Level-1\n");
	     printf("-----------------------------------------------------------\n");
	     printf("        0. All of the tests\n");
	     printf("        1. Set size\n");
         printf("        2. Set size (random sequence)\n");
	     printf("        3. Subblock size\n");
         printf("        4. Subblock size (improved)\n");
		 printf("        5. Set parameters\n");
	     printf("        6. Exit\n");
	     printf("-----------------------------------------------------------\n");
	     printf("    Option (0 - 5): ");
	     scanf("%d",&option);

        if(option ==5)
	    {
              set_parameters(machine_name,&cache_size);
			  continue;
	    }

		get_parameters(machine_name,file_name,&cache_size);
    	cache_size = cache_size * 1024;

		fp = fopen(file_name,"a+");
	    if(fp == NULL)
	    {
		     perror("Error: Can't open file !");
		     exit(1);
	    }

	    if(option == 1 || option == 0)
        {  
            write_file_head(fp,machine_name,1);
            for (step=STEP_START; step <= cache_size; step *= 2)
			{
			    seq_access(fp, cache_size, step);
			}
           
			fprintf(fp,"\n\n");
	    }

	    if(option == 2 || option == 0)
	    {
            write_file_head(fp,machine_name,2);
            for (step=STEP_START; step <= cache_size; step *= 2)
			{
	             rand_access(fp, cache_size, step);
			}
			fprintf(fp,"\n\n");
	    }

		if(option == 3 || option == 0)
	    {
            write_file_head(fp,machine_name,3);
            stride_access(fp, cache_size);
	        fprintf(fp,"\n\n");
	    }

	    if(option == 4 || option == 0)
	    {
            write_file_head(fp,machine_name,4);
            stride_access_1(fp, cache_size);
	        fprintf(fp,"\n\n");
	    }
	}

	fclose(fp);
}


void seq_access(FILE *fp, long cache_size, long step )
/*-----------------------------------------------------------------------*/
/* Function: Measuring the cache set size using a sequential accessing   */
/*           sequence given the cache size                               */
/*-----------------------------------------------------------------------*/ 
{
	volatile ATYPE  *va;
	register ATYPE  s1;
	register long	i;

	unsigned long start_time, stop_time, sum;
	long          arr_size, arr_item;
	double	      time_cost, cost_per_op;

    printf("step = %d\n",step);
	fprintf(fp,"step = %d\n", step);

	for (arr_size=cache_size/2; arr_size <= cache_size*2; arr_size+=step)
    {
 	     arr_item = arr_size / (sizeof(ATYPE));
	     va = (ATYPE *) calloc(arr_item, sizeof(ATYPE));

         sum=0;
         for (i=0; i<arr_item; i+=1)   /* build up a sequential accessing   */
              va[i] = i + 1  ;         /* sequence                          */
         va[i-1] = 0; 

		 s1 = 0;
	     start_time = clock();         /* -------------- start clock tickle */   
	     for (i=0; i<TOTAL_ACCESS; i+=16)    
	     {     
		      s1 = va[s1]; s1 = va[s1]; s1 = va[s1]; s1 = va[s1];
		      s1 = va[s1]; s1 = va[s1]; s1 = va[s1]; s1 = va[s1];
		      s1 = va[s1]; s1 = va[s1]; s1 = va[s1]; s1 = va[s1];
		      s1 = va[s1]; s1 = va[s1]; s1 = va[s1]; s1 = va[s1];
           
	     }
	     stop_time = clock();          /* --------------- stop clock tickle */

         time_cost = ((double)(stop_time - start_time));
	     time_cost = time_cost/((double)CLOCKS_PER_SEC);
 	     cost_per_op = (1000000000.0*time_cost)/TOTAL_ACCESS;

         printf("%10d\t\t%6.3f\t\t%6.3f %d\n",
	       	       arr_item*sizeof(ATYPE),cost_per_op,time_cost,s1);
	     fprintf(fp,"%10d\t\t%6.3f\t\t%6.3f\n",
		           arr_item*sizeof(ATYPE),cost_per_op,time_cost);
	     free(va);
    }
	return;

}


void rand_access(FILE *fp, long cache_size, long step)
/*------------------------------------------------------------------------*/
/* Function: Measuring the cache set size using a random accessing        */
/*           sequence given the cache size                                */
/*------------------------------------------------------------------------*/ 
{
	volatile ATYPE  *va;
	register ATYPE  s1;
	register long	i,j;

	unsigned long start_time,stop_time,sum;
	long          arr_size, arr_item;
	double	      time_cost, cost_per_op;

    printf("step = %d\n",step);
	fprintf(fp,"step = %d\n", step);
	for (arr_size=cache_size/2; arr_size <= cache_size*2; arr_size+=step)
    {
 	     arr_item = arr_size / (sizeof(ATYPE));
	     va = (ATYPE *)calloc(arr_item, sizeof(ATYPE));

         sum=0;
      
         random_sequence(va,arr_item);  /* build up a random sequence        */
      
	     start_time = clock();         /* -------------- start clock tickle */   
		 for (i=0; i<TOTAL_ACCESS/arr_item; i++)    
	     {       
             s1 = 0;
		     for (j=0; j<arr_item; j+=16)
		     {
		          s1 = va[s1]; s1 = va[s1]; s1 = va[s1]; s1 = va[s1];
		          s1 = va[s1]; s1 = va[s1]; s1 = va[s1]; s1 = va[s1];
		          s1 = va[s1]; s1 = va[s1]; s1 = va[s1]; s1 = va[s1];
		          s1 = va[s1]; s1 = va[s1]; s1 = va[s1]; s1 = va[s1];         
             }
	     }
	     stop_time = clock();          /* --------------- stop clock tickle */ 
       
	     sum = sum + s1;  

         time_cost = ((double)(stop_time - start_time));
	     time_cost = time_cost/((double)CLOCKS_PER_SEC);
 	     cost_per_op = (1000000000.0*time_cost)/TOTAL_ACCESS;

         printf("%10d\t\t%6.3f\t\t%6.3f %d\n",
	       	       arr_item*sizeof(ATYPE),cost_per_op,time_cost,s1);
	     fprintf(fp,"%10d\t\t%6.3f\t\t%6.3f\n",
		           arr_item*sizeof(ATYPE),cost_per_op,time_cost);
	     free(va);
    }
	return;
}

void random_sequence(volatile long *array, long max_index)
/*-----------------------------------------------------------------------------------*/
/* Function: *  build up a random accessing addresses sequence                       */
/*-----------------------------------------------------------------------------------*/
{	
    long i, index, block_no;
       
	for(i=0; i<max_index; i++) array[i]=0;

	index = 0;
	for(i=1; i<max_index; i++)
	{	
	    for(;;)
	    {	
	        block_no = (long)( ( (double)(max_index)*rand()) / RAND_MAX );
	        if( block_no==0 || block_no==index || array[block_no]>0 
				                               || block_no >=max_index)
			{
	            continue;
		    }
		    else
            {
	            array[index] = block_no;	
                index = block_no;
                break;
	        }
	    }
    }
    return;
}




void stride_access(FILE *fp, long cache_size)
/*------------------------------------------------------------------------*/
/* Function: Measuring the cache line size using a sequential accessing   */
/*           sequence in terms of stride from 1 to 512                    */
/*------------------------------------------------------------------------*/ 
{		
	volatile ATYPE *va;
	register long  i, j, s1, stride;
	unsigned long  start_time,stop_time;
	double	       time_cost, cost_per_op;
	long	       arr_size, arr_item;

	arr_size = 4*cache_size;
	arr_item = arr_size /  sizeof(ATYPE);
	va = (ATYPE *)calloc(arr_item,sizeof(ATYPE));

	for (stride=STRIDE_START; stride<STRIDE_END; stride*=2)
	{
        for(j=0; j<arr_item; j+=stride)
                 va[j] = j + stride;
		va[j-stride] = 0;

		s1 = 0;
		start_time = clock();  /* ---------- start clock tickle */
		for (i=0; i<TOTAL_ACCESS; i+=16) 
		{	
	         s1=va[s1]; s1=va[s1]; s1=va[s1]; s1=va[s1];    
	         s1=va[s1]; s1=va[s1]; s1=va[s1]; s1=va[s1];    
	         s1=va[s1]; s1=va[s1]; s1=va[s1]; s1=va[s1];    
	         s1=va[s1]; s1=va[s1]; s1=va[s1]; s1=va[s1];    
		}
		stop_time = clock();   /* ----------- stop clock ticklw */
			

		time_cost = ((double)(stop_time-start_time))/((double)CLOCKS_PER_SEC);
	    cost_per_op  = (1000000000.0 * time_cost)/TOTAL_ACCESS;

        printf("%10d\t\t%6.3f\t\t%6.3f %d\n",
	       	       stride*sizeof(ATYPE),cost_per_op,time_cost,s1);
	    fprintf(fp,"%10d\t\t%6.3f\t\t%6.3f\n",
		           stride*sizeof(ATYPE),cost_per_op,time_cost);
  
	}
}



void stride_access_1(FILE *fp, long cache_size)
/*--------------------------------------------------------------------------*/
/* Function: Measuring the cache subblock size using a sequential accessing */
/*           sequence in terms of stride from 1 to 512                      */
/*--------------------------------------------------------------------------*/ 
{		
	volatile ATYPE *va;
	register long	i, j, s1, stride;
	unsigned long start_time,stop_time;
	long    arr_size, arr_item, total_access;
	double	time_cost,cost_per_op;

	arr_size = 4 * cache_size;
	arr_item = arr_size / (sizeof(ATYPE));
	va = (ATYPE *) calloc(arr_item,sizeof(ATYPE));

	for (stride=STRIDE_START; stride<STRIDE_END; stride*=2)
	{ 
         total_access = TOTAL_ACCESS/arr_item*stride;
	     for (i=0; i<arr_item; i+=stride)/* Initialization of the array     */
	          va[i] = i+stride;

	     for (i=0; i<arr_item; i+=stride)/* Prefetch the data to eliminate */
	          s1=va[i];                  /* the prefetching cost           */
		         	
	 
	     if (stride==1) 
	     {		                  	
	         start_time = clock();
	       	 for (i=0; i<total_access; i++)
	       	 {
	       	     for (j=0; j<arr_item; j+=16*stride)
	       	     {
		       	      #define STRX 1
		              s1=va[j];        s1=va[j+1*STRX];
		              s1=va[j+2*STRX]; s1=va[j+3*STRX];
		              s1=va[j+4*STRX]; s1=va[j+5*STRX];
		              s1=va[j+6*STRX]; s1=va[j+7*STRX];
		              s1=va[j+8*STRX]; s1=va[j+9*STRX];
		              s1=va[j+10*STRX];s1=va[j+11*STRX];
                      s1=va[j+12*STRX];s1=va[j+13*STRX];
      			      s1=va[j+14*STRX];s1=va[j+15*STRX];
       	              #undef STRX
				 }
       		 }
	       	 stop_time = clock();
	     }
         else if(stride==2) 
	     {		                    	
	         start_time = clock();
	       	 for (i=0; i<total_access; i++)
	       	 {
	       	     for (j=0; j<arr_item; j+=16*stride)
	       	     {
		       	      #define STRX 2
		              s1=va[j];        s1=va[j+1*STRX];
		              s1=va[j+2*STRX]; s1=va[j+3*STRX];
		              s1=va[j+4*STRX]; s1=va[j+5*STRX];
		              s1=va[j+6*STRX]; s1=va[j+7*STRX];
		              s1=va[j+8*STRX]; s1=va[j+9*STRX];
		              s1=va[j+10*STRX];s1=va[j+11*STRX];
                      s1=va[j+12*STRX];s1=va[j+13*STRX];
      			      s1=va[j+14*STRX];s1=va[j+15*STRX];
       	              #undef STRX
				 }
       		 }
	       	 stop_time = clock();
         }
         else if(stride==4) 
	     {		                    		
	         start_time = clock();
	       	 for (i=0; i<total_access; i++)
	       	 {
	       	     for (j=0; j<arr_item; j+=16*stride)
	       	     {
		       	      #define STRX 4
		              s1=va[j];        s1=va[j+1*STRX];
		              s1=va[j+2*STRX]; s1=va[j+3*STRX];
		              s1=va[j+4*STRX]; s1=va[j+5*STRX];
		              s1=va[j+6*STRX]; s1=va[j+7*STRX];
		              s1=va[j+8*STRX]; s1=va[j+9*STRX];
		              s1=va[j+10*STRX];s1=va[j+11*STRX];
                      s1=va[j+12*STRX];s1=va[j+13*STRX];
      			      s1=va[j+14*STRX];s1=va[j+15*STRX];
       	              #undef STRX
				 }
       		 }
	       	 stop_time = clock();
	     }
	     else if(stride == 8) 
	     {		                      		
	         start_time = clock();
	       	 for (i=0; i<total_access; i++)
	       	 {
	       	     for (j=0; j<arr_item; j+=16*stride)
	       	     {
		       	      #define STRX 8
		              s1=va[j];        s1=va[j+1*STRX];
		              s1=va[j+2*STRX]; s1=va[j+3*STRX];
		              s1=va[j+4*STRX]; s1=va[j+5*STRX];
		              s1=va[j+6*STRX]; s1=va[j+7*STRX];
		              s1=va[j+8*STRX]; s1=va[j+9*STRX];
		              s1=va[j+10*STRX];s1=va[j+11*STRX];
                      s1=va[j+12*STRX];s1=va[j+13*STRX];
      			      s1=va[j+14*STRX];s1=va[j+15*STRX];
       	              #undef STRX
				 }
       		 }
	       	 stop_time = clock();
	     }
	     else if(stride==16) 
	     {	       	                  
	         start_time = clock();
	       	 for (i=0; i<total_access; i++)
	       	 {
	       	     for (j=0; j<arr_item; j+=16*stride)
	       	     {
		       	      #define STRX 16
		              s1=va[j];        s1=va[j+1*STRX];
		              s1=va[j+2*STRX]; s1=va[j+3*STRX];
		              s1=va[j+4*STRX]; s1=va[j+5*STRX];
		              s1=va[j+6*STRX]; s1=va[j+7*STRX];
		              s1=va[j+8*STRX]; s1=va[j+9*STRX];
		              s1=va[j+10*STRX];s1=va[j+11*STRX];
                      s1=va[j+12*STRX];s1=va[j+13*STRX];
      			      s1=va[j+14*STRX];s1=va[j+15*STRX];
       	              #undef STRX
				 }
       		 }
	       	 stop_time = clock();
	     }
	     else if(stride==32) 
	     {	  	                         
	         start_time = clock();
	       	 for (i=0; i<total_access; i++)
	       	 {
	       	     for (j=0; j<arr_item; j+=16*stride)
	       	     {
		       	      #define STRX 32
		              s1=va[j];        s1=va[j+1*STRX];
		              s1=va[j+2*STRX]; s1=va[j+3*STRX];
		              s1=va[j+4*STRX]; s1=va[j+5*STRX];
		              s1=va[j+6*STRX]; s1=va[j+7*STRX];
		              s1=va[j+8*STRX]; s1=va[j+9*STRX];
		              s1=va[j+10*STRX];s1=va[j+11*STRX];
                      s1=va[j+12*STRX];s1=va[j+13*STRX];
      			      s1=va[j+14*STRX];s1=va[j+15*STRX];
       	              #undef STRX
				 }
       		 }
	       	 stop_time = clock();
	     }
	     else if(stride==64) 
	     {	  	                         
	         start_time = clock();
	       	 for (i=0; i<total_access; i++)
	       	 {
	       	     for (j=0; j<arr_item; j+=16*stride)
	       	     {
		       	      #define STRX 64
		              s1=va[j];        s1=va[j+1*STRX];
		              s1=va[j+2*STRX]; s1=va[j+3*STRX];
		              s1=va[j+4*STRX]; s1=va[j+5*STRX];
		              s1=va[j+6*STRX]; s1=va[j+7*STRX];
		              s1=va[j+8*STRX]; s1=va[j+9*STRX];
		              s1=va[j+10*STRX];s1=va[j+11*STRX];
                      s1=va[j+12*STRX];s1=va[j+13*STRX];
      			      s1=va[j+14*STRX];s1=va[j+15*STRX];
       	              #undef STRX
				 }
       		 }
	       	 stop_time = clock();
	     }
	     else if(stride==128) 
         {		                     
	         start_time = clock();
	       	 for (i=0; i<total_access; i++)
	       	 {
	       	     for (j=0; j<arr_item; j+=16*stride)
	       	     {
		       	      #define STRX 128
		              s1=va[j];        s1=va[j+1*STRX];
		              s1=va[j+2*STRX]; s1=va[j+3*STRX];
		              s1=va[j+4*STRX]; s1=va[j+5*STRX];
		              s1=va[j+6*STRX]; s1=va[j+7*STRX];
		              s1=va[j+8*STRX]; s1=va[j+9*STRX];
		              s1=va[j+10*STRX];s1=va[j+11*STRX];
                      s1=va[j+12*STRX];s1=va[j+13*STRX];
      			      s1=va[j+14*STRX];s1=va[j+15*STRX];
       	              #undef STRX
				 }
       		 }
	       	 stop_time = clock();
	     }
	     else if(stride==256) 
	     {		                    
	         start_time = clock();
	       	 for (i=0; i<total_access; i++)
	       	 {
	       	     for (j=0; j<arr_item; j+=16*stride)
	       	     {
		       	      #define STRX 256
		              s1=va[j];        s1=va[j+1*STRX];
		              s1=va[j+2*STRX]; s1=va[j+3*STRX];
		              s1=va[j+4*STRX]; s1=va[j+5*STRX];
		              s1=va[j+6*STRX]; s1=va[j+7*STRX];
		              s1=va[j+8*STRX]; s1=va[j+9*STRX];
		              s1=va[j+10*STRX];s1=va[j+11*STRX];
                      s1=va[j+12*STRX];s1=va[j+13*STRX];
      			      s1=va[j+14*STRX];s1=va[j+15*STRX];
       	              #undef STRX
				 }
       		 }
	       	 stop_time = clock();
	     }
	     else if(stride==512) 
         {		                    
	         start_time = clock();
	       	 for (i=0; i<total_access; i++)
	       	 {
	       	     for (j=0; j<arr_item; j+=16*stride)
	       	     {
		       	      #define STRX 512
		              s1=va[j];        s1=va[j+1*STRX];
		              s1=va[j+2*STRX]; s1=va[j+3*STRX];
		              s1=va[j+4*STRX]; s1=va[j+5*STRX];
		              s1=va[j+6*STRX]; s1=va[j+7*STRX];
		              s1=va[j+8*STRX]; s1=va[j+9*STRX];
		              s1=va[j+10*STRX];s1=va[j+11*STRX];
                      s1=va[j+12*STRX];s1=va[j+13*STRX];
      			      s1=va[j+14*STRX];s1=va[j+15*STRX];
       	              #undef STRX
				 }
       		 }
	       	 stop_time = clock();
	     }

       	 time_cost = ((double)(stop_time-start_time))/((double)CLOCKS_PER_SEC);
         cost_per_op = (1000000000.0*time_cost) / TOTAL_ACCESS;

         printf("%10d\t\t%6.3f\t\t%6.3f %d\n",
	       	       stride*sizeof(ATYPE),cost_per_op,time_cost,s1);
	     fprintf(fp,"%10d\t\t%6.3f\t\t%6.3f\n",
		           stride*sizeof(ATYPE),cost_per_op,time_cost);
  
	  }
}




void write_file_head(FILE *fp,char mname[255],int option)
{
    time_t tm;
    char time_buf[255];
    char method[4][80] = { "1. Set size measurement (sequential)",
	                       "2. Set size measurement (random)",
                           "3. Subblock size measurement",
                           "4. Subblock size measurement (improved)"};

    time(&tm);
    strcpy(time_buf, ctime(&tm));
	
    printf("\nTest date: %s", time_buf );
    printf("-----------------------------------------------------------\n");

    fprintf(fp,"---------  Measurement of Cache Set_size  -----------\n");
    fprintf(fp,"\n     Manchine :  %s", mname );
    fprintf(fp,"\n       Method :  %s", method[option-1]);
    fprintf(fp,"\n    Test date :  %s", time_buf );
    fprintf(fp,"-----------------------------------------------------\n");

	if(option == 3 || option == 4)
	{
         printf("Stride_size(byte) Access_T(ns)\tTotal_T(s)\n");
	     fprintf(fp,"Stride_size(bytes) Access_T(ns)\tTotal_T(s)\n");
	}
	else
	{
         printf("Step_size(byte)       Access_T(ns)  \tTotal_T(s)\n");
         fprintf(fp,"Array_size(bytes)       Access_T(ns)  \tTotal_T(s)\n");
	}
}


void set_parameters(char mname[15],long *cache_size)
/*----------------------------------------------------------------------------*/
/* Function:  Config the needed parameters from keyboard and                  */
/*            form a name for the data file and save the them                 */
/*            in the TLB_Config.data       .                                  */
/*----------------------------------------------------------------------------*/
{
	char	fname[25];
	FILE	*fp;

    printf("             The Machine Name: ");
    scanf("%s",mname);
    printf("    Cache_size of Level-I(KB): ");
    scanf("%d", cache_size);

    strcpy(fname,"Subblock_");
    strcat(fname,mname);
    strcat(fname,".dat");

 	fp = fopen("Subblock_Config.dat","w");
	if(fp == NULL)
	{
		perror("Error: Can't open file !");
		exit(1);
	}
    fprintf(fp,"%s\n",mname);
    fprintf(fp,"%s\n",fname);
	fprintf(fp,"%d\n",*cache_size);

    fclose(fp);
    return;
}


void get_parameters(char mname[15],char fname[25],long *cache_size)
/*---------------------------------------------------------------------------*/
/* Function:  get the parameters needed from file TLB_Config.dat             */
/*---------------------------------------------------------------------------*/
{
	FILE *fp;

 	fp = fopen("Subblock_Config.dat","r");
	if(fp == NULL)
	{
		perror("Error: Can't open file !");
		exit(1);
	}
    fscanf(fp,"%s\n",mname);
    fscanf(fp,"%s\n",fname);
	fscanf(fp,"%d\n",cache_size);
	
	fclose(fp);
    return;
}