10085. Parallel Count (debug)

題目描述

這有一份由 pthread 撰寫的序列總和計算，假設不開任何的優化參數，在快取處理會有嚴重缺失。

這份程序輸入序列長度 $n$，計算 $m$ 次經由 $\text{key}, \; \text{key} + 1, \; \text{key} + 2, \; \cdots, \; \text{key} + m-1$ 加密的序列總和。

main.c

這部份將不提供修改。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <stdio.h>
#include <stdlib.h>
#include "utils.h"
 
int main() {
    int cases = 0;
    int n, m, key;
    scanf("%d %d %d", &n, &m, &key);
    for (int it = 0; it < m; it++) {
        int ret = run(n, key);
        printf("Case #%d: %d\n", ++cases, ret);
        key++;
    }
    return 0;
}

utils.h

計算工作交由 void f(int n, int key, int *p1, int *p2, int *p3, int *p4); 完成最後四個參數，將會由 4 個 thread 計算分別儲存在位址 p1, p2, p3, p4 中。

1
2
3
4
5
6
7
#ifndef __UTILS_H
#define __UTILS_H
 
void f(int n, int key, int *p1, int *p2, int *p3, int *p4);
int run(int n, int key);
 
#endif

sum.c

平行計算序列總和，特別注意到 void* subtask(void* argu) 中存取的記憶體位置。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include <stdlib.h>
#include <pthread.h>
#include <stdint.h>
#include "utils.h"
 
typedef struct Argu {
    int *result;
    int L, R, key;
} Argu;
 
static inline uint32_t rotate_left(uint32_t x, uint32_t n) {
        return  (x << n) | (x >> (32-n));
}
static inline uint32_t encrypt(uint32_t m, uint32_t key) {
        return (rotate_left(m, key&31) + key)^key;
}
 
static void* subtask(void* argu) {
    Argu *ptr = (Argu *) argu;
    *(ptr->result) = 0;
    for (int i = ptr->L; i <= ptr->R; i++)
        *(ptr->result) += encrypt(i, ptr->key);
}
 
void f(int n, int key, int *p1, int *p2, int *p3, int *p4) {
    pthread_t threads[4];
    int *output[4] = {p1, p2, p3, p4};
    for (int i = 0; i < 4; i++) {
            Argu *argu = (Argu *) malloc(sizeof(Argu));
            argu->result = output[i];
            argu->L = i * (n / 4) + 1;
            argu->R = argu->L + n / 4 - 1;
            argu->key = key;
            if (i == 3) argu->R = n;
            pthread_create(&threads[i], NULL, subtask, argu);
    }
 
    for (int i = 0; i < 4; i++)
        pthread_join(threads[i], NULL);
}

job.c

你的工作要改善下方代碼的效能。

1
2
3
4
5
6
7
8
9
10
#include "utils.h"
 
int ret[128];
int run(int n, int key) {
    int sum = 0;
    f(n, key, ret, ret+1, ret+2, ret+3);
    for (int i = 0; i < 4; i++)
        sum += ret[i];
    return sum;
}

輸入格式

輸入只有一行三個整數 $n, \; m, \; \text{key}$。

輸出格式

輸出 $m$ 序列總和結果 (無視 overflow)。

範例輸入

10000000 10 514

範例輸出

Case #1: 1397862656
Case #2: 1970821632
Case #3: -1178356736
Case #4: 1113221120
Case #5: 1401409536
Case #6: 1977786368
Case #7: -1164427264
Case #8: 1145914243
Case #9: 645957382
Case #10: 1308383748

編譯環境

Makefile

CFLAG=-std=c99 -pthread
 
all: main.c sum.c job.c
    gcc $(CFLAG) main.c -c
    gcc $(CFLAG) sum.c -c
    gcc $(CFLAG) main.o sum.o job.c -o job

參考資料

可參考以下資料，使用提及的技術解決這題

• Mind the Cache