20190084_권민재.tar

csim.c0000775000202300020230000001434613754707303010577 0ustar  betabeta/*
 * Cache Lab: Understanding Cache Memories
 * Part A: Writing a Cache Simulator
 *
 * 20190084 권민재
 * mzg00@postech.ac.kr
 */

#include <stdio.h>
#include <stdlib.h>
#include <getopt.h>
#include <math.h>
#include "cachelab.h"

#define TRUE 1
#define FALSE 0

// Block: 캐시 블럭을 나타내기 위한 구조체/타입
typedef struct {
    int valid; // 블럭의 Valid
    unsigned long long tag; // 블럭의 Tag
    int lruCount; // 블럭의 LRU 카운터 값
} Block;

// Set: 캐시의 set를 나타내기 위한 구조체/타입
typedef struct {
    Block *blockList; // 블럭의 배열
} Set;

// Cache: 캐시를 나타내기 위한 구조체 / 타입
typedef struct {
    int numSet; // 캐시의 set 크기
    int numLine; // 각 set의 라인 수
    Set *setList; // set의 배열
} Cache;

// 전역 변수 (해당 과제에 전역 변수 제한 없음)
Cache cache = {}; // 시뮬레이션을 진행할 캐시
int s = 0, E = 0, b = 0; // 외부로부터 입력받은 s, E, b 저장
int LRU = 0; // 전역 LRU 카운터
int hits = 0, misses = 0, evictions = 0; // hit, miss, eviction 결과값이 담길 변수

// 캐시 시뮬레이션에 필요한 공간을 동적 할당하는 함수
void initCache();

// 캐시 시뮬레이션에 동적 할당된 메모리를 정리하는 함수
void freeCache();

// 캐시를 시뮬레이션 하는 함수
void simulate(FILE *file);

// 어떤 주소를 가지고 캐시에 접근하는 함수
void cacheAccess(unsigned long long int addr);

int main(int argc, char *argv[]) {
    // 파일 입출력 관련 변수 선언
    char *filename;
    FILE *file;

    // 외부 인자 파싱
    for (int opt; (opt = getopt(argc, argv, "s:E:b:t:")) != -1;) {
        switch (opt) {
            case 's': // s 저장
                s = atoi(optarg);
                break;
            case 'E': // e 저장
                E = atoi(optarg);
                break;
            case 'b': // b 저장
                b = atoi(optarg);
                break;
            case 't': // 파일 이름 저장
                filename = optarg;
                break;
            default: // 지정된 인자가 아니라면 1 반환 및 종료. (에러)
                return 1;
        }
    }

    // s, E, b, 파일 이름이 적절하게 설정되지 않았다면, 1 반환 및 종료. (에러)
    if (!s || !E || !b || !filename) {
        return 1;
    }

    // 파일을 여는데 실패했다면, 1 반환 및 종료. (에러)
    if (!(file = fopen(filename, "r"))) {
        return 1;
    }

    // 캐시 초기화. 필요한 공간 동적 할당
    initCache();

    // 캐시 시뮬레이션 수행
    simulate(file);

    // 시뮬레이션 결과 출력
    printSummary(hits, misses, evictions);

    // 동적할당된 메모리 정리 및 파일 닫기
    freeCache();
    fclose(file);

    return 0;
}

// 캐시 시뮬레이션에 필요한 공간을 동적 할당하는 함수
void initCache() {
    cache.numSet = (int) pow(2.0, s);
    cache.numLine = E;
    cache.setList = malloc(sizeof(Set) * cache.numSet);
    for (int i = 0; i < cache.numSet; ++i) {
        cache.setList[i].blockList = malloc(sizeof(Block) * cache.numLine);
        for (int j = 0; j < E; ++j) {
            cache.setList[i].blockList[j].valid = FALSE;
            cache.setList[i].blockList[j].tag = 0;
            cache.setList[i].blockList[j].lruCount = 0;
        }
    }
}

// 캐시 시뮬레이션에 동적 할당된 메모리를 정리하는 함수
void freeCache() {
    for (int i = 0; i < cache.numSet; ++i) {
        free(cache.setList[i].blockList);
    }
    free(cache.setList);
}

// 캐시를 시뮬레이션 하는 함수
void simulate(FILE *file) {
    char opt;
    unsigned long long addr;

    while (fscanf(file, " %c %llx%*c%*d", &opt, &addr) != EOF) {
        printf("%c %llx: ", opt, addr);
        if (opt == 'I') { continue; }
        cacheAccess(addr);
        if (opt == 'M') { cacheAccess(addr); }
    }
}

// 어떤 주소를 가지고 캐시에 접근하는 함수
void cacheAccess(unsigned long long int addr) {
    // addr의 인덱스. b 만큼 오른쪽으로 쉬프트하고, 이를 associativity 에서 1 뺀 값과 and 하면 구할 수 있다.
    unsigned int INDEX = (addr >> (unsigned int) b) & ((unsigned int) pow(2, s) - 1);

    // addr의 태그. addr을 s+b 만큼 오른쪽으로 쉬프트하면 구할 수 있다.
    unsigned long long TAG = (addr >> ((unsigned int) s + (unsigned int) b));

    int blockIdx; // 블럭 탐색을 위한 임시 변수
    int evictionBlock = 0; // eviction할 블럭의 인덱스
    unsigned long long int evictionLru = -1; // eviction 할 블럭을 결정하는 LRU 지표

    int isHit = FALSE; // hit 여부를 나타내는 변수
    Set *set = &cache.setList[INDEX]; // addr으로 캐시에 접근할 때, 접근해야 할 캐시의 set.

    // set의 블럭들을 탐색하면서, 태그가 같은 valid한 블럭을 찾았다면, hit가 발생했음을 기록한다.
    for (blockIdx = 0; blockIdx < E; ++blockIdx) {
        if (TAG == set->blockList[blockIdx].tag && set->blockList[blockIdx].valid) {
            isHit = TRUE;
            break;
        }
    }

    if (isHit) { // Hit가 발생했다면,
        set->blockList[blockIdx].lruCount = LRU; // 해당 블럭에 전역 LRU 카운터를 설정한다.
        ++hits; // hits를 1 증가시킨다.
    } else { // Hit가 발생하지 않았다면,
        // 블럭들을 탐색하면서, set에서 lruCount의 값이 가장 작은 블럭을 찾는다.
        for (blockIdx = 0; blockIdx < E; ++blockIdx) {
            if (evictionLru > set->blockList[blockIdx].lruCount) {
                evictionBlock = blockIdx;
                evictionLru = set->blockList[blockIdx].lruCount;
            }
        }

        // lruCount가 가장 작은 블럭이 valid 하다면, eviction이 일어나야 하므로, evictions를 1 증가시킨다.
        if (set->blockList[evictionBlock].valid) {
            ++evictions;
        }

        // lruCount가 가장 작은 블럭의 값을 초기화 한다.
        set->blockList[evictionBlock].valid = TRUE;
        set->blockList[evictionBlock].tag = TAG;
        set->blockList[evictionBlock].lruCount = LRU;

        ++misses; // misses를 1 증가시킨다.
    }

    ++LRU; // LRU를 1 증가시킨다.
}trans.c0000775000202300020230000001316013754710174010764 0ustar  betabeta/*
 * Cache Lab: Understanding Cache Memories
 * Part B: Optimizing Matrix Transpose
 *
 * 20190084 권민재
 * mzg00@postech.ac.kr
 */

/*
 * 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 blocking(int M, int N, int A[N][M], int B[M][N], int ROW, int COL);
void blocking_diag(int M, int N, int A[N][M], int B[M][N], int ROW, int COL);
void blocking_64(int M, int N, int A[N][M], int B[M][N], int ROW, int COL);
/*
 * 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])
{
    // 행렬 탐색을 위한 임시 변수
    int row, col;

    // 사이즈에 따른 transpose 함수 포인터
    void (*trans_function)(int M, int N, int A[N][M], int B[M][N], int ROW, int COL);

    // 64 x 64 행렬에는 blocking_64 함수를 지정.
    if(M == 64 && N == 64){
        trans_function = blocking_64;
    } else {
        trans_function = blocking;
    }

    // 8x8 부분 행렬로 쪼개서 계산
    for(row = 0; row < N; row+=8){
        for(col = 0; col < M; col+=8){
            trans_function(M, N, A, B, row, col);
        }
    }
}

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

void blocking(int M, int N, int A[N][M], int B[M][N], int ROW, int COL){
    if(ROW == COL){ // 대각선을 포함한 부분에 대해서는 blocking_diag를 수행한다.
        blocking_diag(M, N, A, B, ROW, COL);
        return;
    }

    // 8x8 부분 행렬에 대해 transpose를 수행하되, M과 N은 넘지 않도록 한다.
    int row, col;
    for(row = COL; row < COL + 8 && row < M; ++row){
        for(col = ROW; col < ROW + 8 && col < N; ++col){
            B[row][col] = A[col][row];
        }
    }
}

void blocking_diag(int M, int N, int A[N][M], int B[M][N], int ROW, int COL){
    int row, col, tmp;
    // 8x8 부분 행렬에 대해 transpose를 수행하되, M과 N은 넘지 않도록 한다.
    for(row = ROW; row < N && row < ROW + 8; ++row){
        tmp = A[row][row]; // 두 인덱스가 같은 곳의 값을 미리 변수에 저장한다.
        for(col = COL; col < M && col < COL + 8; ++col){
            if(row == col){ // 두 인덱스가 같을 때에는 transpose를 수행하지 않는다.
                continue;
            }
            B[col][row] = A[row][col];
        }
        // 저장된 변수로 B를 설정한다.
        B[row][row] = tmp;
    }
}

void blocking_64(int M, int N, int A[N][M], int B[M][N], int ROW, int COL){
    // A의 오른쪽 위 4개의 값을 미리 저장한다.
    int r0 = A[ROW][COL + 4];
    int r1 = A[ROW][COL + 5];
    int r2 = A[ROW][COL + 6];
    int r3 = A[ROW][COL + 7];
    int t0, t1, t2, t3;
    int i = 0;

    // A의 왼쪽 반에 대해 위에서부터 4개씩 전치를 수행한다.
    for(i = 0; i < 8; ++i){
        t0 = A[ROW + i][COL + 0];
        t1 = A[ROW + i][COL + 1];
        t2 = A[ROW + i][COL + 2];
        t3 = A[ROW + i][COL + 3];
        B[COL + 0][ROW + i] = t0;
        B[COL + 1][ROW + i] = t1;
        B[COL + 2][ROW + i] = t2;
        B[COL + 3][ROW + i] = t3;
    }

    // A의 오른쪽 반에 대해 아래에서 부터 4개씩 전치를 수행하되, 제일 위의 줄은 제외된다.
    for(i = 7; i > 0; --i){
        t0 = A[ROW + i][COL + 4];
        t1 = A[ROW + i][COL + 5];
        t2 = A[ROW + i][COL + 6];
        t3 = A[ROW + i][COL + 7];
        B[COL + 4][ROW + i] = t0;
        B[COL + 5][ROW + i] = t1;
        B[COL + 6][ROW + i] = t2;
        B[COL + 7][ROW + i] = t3;
    }

    // 미리 저장해둔 오른쪽 위 4개의 값을 transpose한다.
    B[COL + 4][ROW] = r0;
    B[COL + 5][ROW] = r1;
    B[COL + 6][ROW] = r2;
    B[COL + 7][ROW] = r3;
}
/* 
 * 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); 

}

/* 
 * 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;
}