MENU

CS233 Quiz3C Practice Tips

December 4, 2022 • Read: 1087 • CS 233

前言:

期末周被cache搞疯了::quyin:die::,无奈只能使出应试教育的办法了。再猛刷practice后找到了一些经验能让编程题保证在90%+的正确率,不要问我怎么得出来的,我真心不知道::quyin:shakinghead::。废话少说,经验如下:
 

  1. 只要能用prefetch,一定要用prefetch。prefetch的cache miss是不计算在你的总miss里的。
  2. 如果要用prefetch,直接fetch 40位后的element,即"builtin_prefetch(&xxx[i + 40]);"。
  3. 如果要用tiling,tile_size用32的倍数。具体大小要看你的for loop increment多少。如果是i++,tile_size就是32。如果是i+=2,那tile_size就是64。
     

quiz3c_1.png
 

int min(int, int);
#include "definitions.h"

void optimize_me() {
    int tile_size = 32;
    for (int i = 0; i < N; i+=tile_size) {
        for (int j = 0; j < N; j++) {
            for (int ii = i; ii < min(N, i + tile_size); ii++) {
                B[ii][j] = A[j][ii];
            }
        }
    }
}

quiz3c_2.png
 

int min(int, int);
void builtin_prefetch(const void *addr);
#include "definitions.h"

void optimize_me() {
    for (int i = 0; i < NUM_ANT_TYPES; i++) {
        builtin_prefetch(&total_ants[i + 40]);
        total_ants[i] = 0;
    }
        
    for (int j = 0; j < NUM_HILLS_RECORDED; j++) {
        builtin_prefetch(&hills[j + 40]);
        for (int i = 0; i < NUM_ANT_TYPES; i++) {
            builtin_prefetch(&total_ants[i + 40]);
            builtin_prefetch(&hills[j].ant_count[i + 40]);
            total_ants[i] += hills[j].ant_count[i];
        }
    }
}

quiz3c_3.png

int min(int, int);
void builtin_prefetch(const void *addr);
#include "definitions.h"

void optimize_me() {
    for (int i = 0; i < N; i++) {
        builtin_prefetch(&A[0][i+40]);
        B[i] = A[0][i];
    }
    
    for (int j = 0; j < N; j++) {
        builtin_prefetch(&A[j + 40]);
        for (int i = 0; i < N; i++) {
            builtin_prefetch(&C[j][i+40]);
            builtin_prefetch(&A[j][i+40]);
            A[j][i] = m * C[j][i];
        }
    }

    for (int k = 0; k < N; k++) {
        builtin_prefetch(&B[k+40]);
        builtin_prefetch(&D[k+40]);
        D[k] = B[k] * B[k];
    }
}
Last Modified: October 4, 2023
Archives QR Code
QR Code for this page
Tipping QR Code