cjunderhill-sccoache-handin.tar

csim.c0000664000175100017510000002023213023604663013553 0ustar  cjunderhillcjunderhill/*
 * Chad Underhill and Sam Coache
 * cjunderhill-sccoache
 */

#include <time.h>
#include <getopt.h>
#include <stdlib.h>
#include <unistd.h>
#include <stdio.h>
#include <ctype.h>

#include "cachelab.h"

#define INPUT_CAP 250

// Structure containing Set data
struct set { 
    int *valid;				// Pointer to valid bit
    clock_t *last_accessed;	// Track access info for implementation of LRU
    long *tag;    			// Pointer to tag
};
struct set *g_set;

int hits, misses, evicts;	// Counters to track cache hits, misses, and evictions
int s = 0, b = 0, E = 0;	// Holds parameter input (s = set index, b = block offset, E = # lines/set)

char *trace_file = NULL;		// Hold pointer to the input cache trace file
long access_time = 0;	// Hold access info for LRU implementation

/* 
 * get_set - Get set number from the address
 * Params:
 *	*addr - Pointer to the memory address of the set.
 * Returns: void
 */
int get_set(void *addr) {

	int sbit = (int) ((1 << s) - 1);

    return ((long) addr >> b) & sbit;
}

/* 
 * get_tag - Get tag from the address
 * Params:
 *	*addr - Pointer to the memory address of the tag.
 * Returns: void
 */
long get_tag(void *addr) {

	int sb_bits = (s + b);

    return (long) addr >> sb_bits;
}

/*
 * operate_L - handle a LOAD operation passed in from the cache trace
 * Params:
 *	*addr - Pointer to the memory address being accessed.
 *	size - Number of bytes accessed by the operation.
 * Returns: void
 */
void operate_L(void *addr, int size) {

	// Initialize pointer to current set in cache
    struct set *current_set = &g_set[get_set(addr)];

    int i = 0, is_full = 1;
    int empty_item = 0;         // Track the empty entry
    int last_entry = 0;         // Track the evict entry
    int last_time = current_set->last_accessed[0];  

    // For each line in the set 
    for (; i < E; i++) {   
        // Find and update the access time if entry is valid and has matching tag
        if (current_set->valid[i] == 1 && get_tag(addr) == current_set->tag[i]) {
            current_set->last_accessed[i] = access_time++;
            break;

        // Else if entry is not valid, then it's considered empty and the cache is not full
        } else if (current_set->valid[i] == 0) {
            is_full = 0;
            empty_item = i;

        // Else the entry is valid but the tag is not equal
        } else { 

            // Track LRU item, which will be evicted
            if (current_set->last_accessed[i] < last_time) {
                last_entry = i;
                last_time = current_set->last_accessed[i];
            }
        }
    }

    // If we have a miss
    if (i == E) {
        misses++;

        // If cache is full, evict
        if (is_full) {
            current_set->last_accessed[last_entry] = access_time++;
            current_set->tag[last_entry] = get_tag(addr);
            evicts++;

        // Otherwise it's simply a miss
        } else {
        	// Set line bit to valid, assign an address to the cache, and set the access time
            current_set->last_accessed[empty_item] = access_time++;
            current_set->valid[empty_item] = 1;
            current_set->tag[empty_item] = get_tag(addr);
        }
    // Otherwise it's a hit!
    } else {
        hits++;
    }    

}

/* 
 * operate_S - Handle a STORE operation passed in from the cache trace;
 *				Runs a LOAD operation if miss.
 * Params:
 *	*addr - Pointer to the memory address being accessed.
 *	size - Number of bytes accessed by the operation.
 * Returns: void
 */
void operate_S(void *addr, int size) {
    
    // Initialize pointer to current set in cache
    struct set *current_set = &g_set[get_set(addr)];

    int i = 0;

    // For each line in the set
    for (; i < E; i++) {
    	// Find and update the access time if entry is valid and has matching tag
        if (current_set->valid[i] == 1 && get_tag(addr) == current_set->tag[i]) {
            current_set->last_accessed[i] = access_time++;
            break;
        }
    } 

    // If we have a miss, load the data
    if (i == E) {
        operate_L(addr, size);
    // Otherwise it's a hit!
    } else {
        hits++;
    }
}

/* 
 * operate_M - Handle a MODIFY operation passed in from the cache trace;
 * 				Simply a LOAD operation followed by a STORE operation.
 * Params:
 *	*addr - Pointer to the memory address being accessed.
 *	size - Number of bytes accessed by the operation.
 * Returns: void
 */
void operate_M(void *addr, int size) {

    operate_L(addr, size);
    operate_S(addr, size);
}

/*
 * get_operator - Processes input program parameters.
 *					Utilizes getopt library for core functionality.
 * Params:
 *	argc - Argument count
 *	**argv - Pointer to argument array
 * Returns: void
 */
//function to find the program parameters
void get_operator(int argc, char **argv) {
    int toggle;	// Holds input parameter character for comparison

    // Process while there are still remaining unhandled parameters (where getopt then returns -1)
    while ((toggle = getopt(argc, argv, "s:E:b:t:")) != -1) {

    	// Process input argument
    	if(toggle == 's') {
            s = atoi(optarg);
    	} else if(toggle == 'E') {
			E = atoi(optarg);
    	} else if(toggle == 'b') {
			b = atoi(optarg);
    	} else if(toggle == 't') {
			trace_file = optarg;
    	} else { // Error case
            printf("Error: Illegal operation!\n");
            exit(0);	// Terminate
    	}

    }
}

/*
 * initialize - Initialize cache data structure in memory
 * Returns: void
 */
void initialize() {
    int S = (1 << s);	// Calc number of sets (2^s)

    // Handle nonpositive set counts with error
    if (S <= 0) {
        fprintf(stderr, "Error: Attempted to initialize cache with nonpositive number of sets!\n");
        exit(0);	// Terminate
    }

    // Allocate memory for all sets in cache
    g_set = (struct set*) malloc(sizeof(struct set) * S);
    
    // Allocate memory for data in each set
    for (int i = 0; i < S; i++) {
        g_set[i].last_accessed = (clock_t *) malloc(sizeof(clock_t) * E);
        g_set[i].valid = (int *) malloc(sizeof(int) * E);
        g_set[i].tag = (long *) malloc(sizeof(long) * E);

        // Initialize all blocks on each line to empty
        for(int j = 0 ; j < E; j++) {
            g_set[i].last_accessed[j] = 0;
            g_set[i].valid[j] = 0;
            g_set[i].tag[j] = 0;
        }
    }
}

/*
 * deinitialize - Free cache data structure in memory
 * Returns: void
 */
void deinitialize() {
    int S = (1 << s);	// Calc number of sets (2^s)

    g_set = (struct set*) malloc(sizeof(struct set) * S);

    // Sequentially free memory for each set in the cache
    for (int i = 0; i < S; i++) {
        free(g_set[i].last_accessed);
        free(g_set[i].valid);
        free(g_set[i].tag);
    }

    // Free memory for entire cache
    free(g_set);
}

/*
 * main - Entry point for the program
 * Params:
 *	argc - Argument count
 *	**argv - Pointer to argument array
 * Returns: 0 if success
 */
int main(int argc, char **argv) {

	// Process input parameters
    get_operator(argc, argv);

    // Initialize cache data structure
    initialize();

    char operation[INPUT_CAP];	// Cache operation
    void *addr;					// Operation memory address
    int size;					// Size (in bytes) accessed by operation
    char buf[INPUT_CAP];		// Hold line currently read from the file
    FILE *fp = fopen(trace_file, "r");	// Hold pointer to the specified trace file    

    // Throw error if trace file is invalid
    if (fp == NULL) {
        fprintf(stderr, "Error 404: trace file not found!\n");
        exit(0);	// Terminate
    }

    // For each line in the cache file
    while (fgets(buf, INPUT_CAP, fp) != NULL) {

    	// Parse the line, store operation, address, and size
        sscanf(buf, "%s %p,%d", operation, &addr, &size);

        // Perform relevant operation based on specified operation
        if (*operation == 'S') {
            operate_S(addr, size);
        }
        else if (*operation == 'M') {
            operate_M(addr, size);
        }
        else if (*operation == 'L') {
            operate_L(addr, size);
        }
    }

    // Free cache data structure
    deinitialize();

    // Print summary of cache simulation instructions
    printSummary(hits, misses, evicts);

    return 0;	// Indicate successful run
}trans.c0002666000175100017510000002012713024001421013736 0ustar  cjunderhillcjunderhill/*
 * Chad Underhill and Sam Coache
 * cjunderhill-sccoache
 */

/* 
 * trans.c - Matrix transpose B = A^T
 *
 * Each transpose function must have a prototype of the form:
 * void trans(int M, int N, int A[N][M], int B[M][N]);
 *
 * A transpose function is evaluated by counting the number of misses
 * on a 1KB direct mapped cache with a block size of 32 bytes.
 */ 
#include <stdio.h>
#include "cachelab.h"

int is_transpose(int M, int N, int A[N][M], int B[M][N]);
void transpose_32(int M, int N, int A[N][M], int B[M][N]);
void transpose_64(int M, int N, int A[N][M], int B[M][N]);
void transpose_other(int M, int N, int A[N][M], int B[M][N]);

/* 
 * transpose_submit - This is the solution transpose function that you
 *     will be graded on for Part B of the assignment. Do not change
 *     the description string "Transpose submission", as the driver
 *     searches for that string to identify the transpose function to
 *     be graded. 
 */
char transpose_submit_desc[] = "Transpose submission";
void transpose_submit(int M, int N, int A[N][M], int B[M][N]){

	// Determine variation of transpose function to run based on dimensions of input matrix
	switch(N) {
    	case 32:	// 32x32 matrix
    		transpose_32(M, N, A, B);
        	break;
    	case 64:	// 64x64 matrix
    		transpose_64(M, N, A, B);
      		break;
      	default:	// all matrices not 32x32 or 64x64
        	transpose_other(M, N, A, B);
        	break;
    }
}


/* 
 * You can define additional transpose functions below. We've defined
 * a simple one below to help you get started. 
 */ 

/*
 * transpose_32 - Matrix transposition function optimized for a 32x32 matrix
 					Fairly optimal solution - # of misses is ~290
 * Params: 
 *	M - Number of columns in the matrix
 *	N -	Number of rows in the matrix
 *	A[N][M] - Input matrix - the one transposed from
 *	B[N][M] - Input matrix - the one transposed to
 * Returns: void
 */
char transpose_32_desc[] = "Transpose a 32x32 matrix";
void transpose_32(int M, int N, int A[N][M], int B[M][N]){

	int n, m; 		// Indecies for rows and columns in matrix
	int row, col;	// Track current row and column in matrix
	int d_val = 0;	// Hold value of diagonal element found in matrix (detailed in below code)
	int diag = 0;	// Hold position of diagonal element found in matrix (detailed in below code)

	// Iterates through each column and row
	for (col = 0; col < N; col += 8) { 
		for (row = 0; row < N; row += 8) {

			// For each row and column in the designated block, until end of matrix
			for (n = row; n < (row + 8); n++) {
				for (m = col; m < (col + 8); m++) {

					// If row and column do not match, transposition will occur
					if (n != m) {
						B[m][n] = A[n][m];
					// Else, row and column are same and element in matrix is defined as a diagonal
					} else {

						// Assign diagonal element to a temporary variable
						// This saves an individual cache miss on each run through the matrix where the columns and rows still match up
						diag = n;
						d_val = A[n][m];
					}
				}
				// If row and column are same, element is defined as a diagonal and our temporarily saved element is assigned
				if (row == col) {
					B[diag][diag] = d_val;
				}
			}	
		}
	}
}

/*
 * transpose_64 - Matrix transposition function optimized for a 64x64 matrix
 					Not the most optimal solution - couldn't determine a way to reduce # of misses below ~1750 =(
 * Params: 
 *	M - Number of columns in the matrix
 *	N -	Number of rows in the matrix
 *	A[N][M] - Input matrix - the one transposed from
 *	B[N][M] - Input matrix - the one transposed to
 * Returns: void
 */
char transpose_64_desc[] = "Transpose a 64x64 matrix";
void transpose_64(int M, int N, int A[N][M], int B[M][N]){

	int n, m; 		// Indecies for rows and columns in matrix
	int row, col;	// Track current row and column in matrix
	int d_val = 0;	// Hold value of diagonal element found in matrix (detailed in below code)
	int diag = 0;	// Hold position of diagonal element found in matrix (detailed in below code)

	// Iterates through each column and row
	for (col = 0; col < N; col += 4) { 
		for (row = 0; row < N; row += 4) {

			// For each row and column in the designated block, until end of matrix
			for (n = row; n < (row + 4); n++) {
				for (m = col; m < (col + 4); m++) {

					// If row and column number do not match, transposition will occur
					if (n != m) {
						B[m][n] = A[n][m];
					// Else, row and column number are same and element in matrix is defined as a diagonal
					} else {

						// Assign diagonal element to a temporary variable
						// This saves an individual cache miss on each run through the matrix where the columns and rows still match up
						diag = n;
						d_val = A[n][m];
					}
				}
				// If row and column are same, element is defined as a diagonal and our temporarily saved element is assigned
				if (row == col) {
					B[diag][diag] = d_val;
				}
			}	
		}
	}
}

/*
 * transpose_other - Matrix transposition function optimized for matricies that aren't 32x32 or 64x64
 					Appears to be a fairly optimal solution - # of misses for a 61x67 matrix is ~1800
 * Params: 
 *	M - Number of columns in the matrix
 *	N -	Number of rows in the matrix
 *	A[N][M] - Input matrix - the one transposed from
 *	B[N][M] - Input matrix - the one transposed to
 * Returns: void
 */
char transpose_other_desc[] = "Transpose any matrix that isn't 32x32 or 64x64";
void transpose_other(int M, int N, int A[N][M], int B[M][N]){

	int n, m; 		// Indecies for rows and columns in matrix
	int row, col;	// Track current row and column in matrix
	int d_val = 0;	// Hold value of diagonal element found in matrix (detailed in below code)
	int diag = 0;	// Hold position of diagonal element found in matrix (detailed in below code)

	// Iterates through each column and row
	for (col = 0; col < M; col += 16) {
		for (row = 0; row < N; row += 16) {

			// For each row and column after current one, until end of matrix
			for (n = row; (n < row + 16) && (n < N); n++) {
				for (m = col; (m < col + 16) && (m < M); m++) {

					// If row and column number do not match, transposition will occur
					if (n != m) {
						B[m][n] = A[n][m];
					// Else, row and column number are same and element in matrix is defined as a diagonal
					} else {

						// Assign diagonal element to a temporary variable
						// This saves an individual cache miss on each run through the matrix where the columns and rows still match up
						diag = n;
						d_val = A[n][m];
					}
				}
				// If row and column are same, element is defined as a diagonal and our temporarily saved element is assigned
				if (row == col) {
					B[diag][diag] = d_val;
				}
			}
	 	}
	}
}

/* 
 * trans - A simple baseline transpose function, not optimized for the cache.
 */
char trans_desc[] = "Simple row-wise scan transpose";
void trans(int M, int N, int A[N][M], int B[M][N])
{
    int i, j, tmp;

    for (i = 0; i < N; i++) {
        for (j = 0; j < M; j++) {
            tmp = A[i][j];
            B[j][i] = tmp;
        }
    }    

}

/*
 * registerFunctions - This function registers your transpose
 *     functions with the driver.  At runtime, the driver will
 *     evaluate each of the registered functions and summarize their
 *     performance. This is a handy way to experiment with different
 *     transpose strategies.
 */
void registerFunctions()
{
    /* Register your solution function */
    registerTransFunction(transpose_submit, transpose_submit_desc); 

    /* Register any additional transpose functions */
    registerTransFunction(trans, trans_desc);

    // Register custom transpose functions
    registerTransFunction(transpose_32, transpose_32_desc);
    registerTransFunction(transpose_64, transpose_64_desc);
    registerTransFunction(transpose_other, transpose_other_desc);

}

/* 
 * is_transpose - This helper function checks if B is the transpose of
 *     A. You can check the correctness of your transpose by calling
 *     it before returning from the transpose function.
 */
int is_transpose(int M, int N, int A[N][M], int B[M][N])
{
    int i, j;

    for (i = 0; i < N; i++) {
        for (j = 0; j < M; ++j) {
            if (A[i][j] != B[j][i]) {
                return 0;
            }
        }
    }
    return 1;
}