學校課程/平行程式

批改娘 10085. Parallel Count (debug)

contents

  1. 1. 題目描述
    1. 1.1. main.c
    2. 1.2. utils.h
    3. 1.3. sum.c
    4. 1.4. job.c
  2. 2. 輸入格式
  3. 3. 輸出格式
  4. 4. 範例輸入
  5. 5. 範例輸出
  6. 6. 編譯環境
    1. 6.1. Makefile
  7. 7. Solution

題目描述

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

main.c

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

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)。

範例輸入

1
10000000 10 514

範例輸出

1
2
3
4
5
6
7
8
9
10
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

1
2
3
4
5
6
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

reference

Solution

由於茵可大神給予我參考的簡報 Mind Cache 中提到不少的快取實驗，其中一部份就是在 thread 使用上，於是就拿來出題測試測試一番。

通常講到數據局部性 (Data Locality) 都希望資料盡量集中，但一不小心會犯下錯誤，就是在多個 thread 儲存答案時，雖然不會共用同一個位址，但相鄰的位址在另一個核 (core) 使用，由於彼此之間相互修改，兩個相鄰位址若放在同一個 cache line，dirty bit 勢必要讓他們從 cache line 掉到 L1 -> L2 -> L3，進行資料同步。

目前 cache line 普遍上設計大小為 64 Bytes，相當於間隔 16 個 4 bytes Integer 的差距，所以儲存答案間隔遠一點會比近一點好。當然，編譯器優化參數開到 O2 以上時，似乎就直接先存放到暫存器裡頭，不會不斷地存取 global memory 部份，如此一來，就不會發生 cache miss 問題。實驗結果效能可以差到四倍左右。

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