學校課程/平行程式

批改娘 10084. Prefix Sum (pthread)

contents

  1. 1. 題目描述
    1. 1.1. utils.h
    2. 1.2. prefixsum-seq.c
    3. 1.3. secret.c (測試用)
  2. 2. 輸入格式
  3. 3. 輸出格式
  4. 4. 範例輸入
  5. 5. 範例輸出
  6. 6. 範例解釋
  7. 7. 編譯方式
  8. 8. 測試主機資訊
  9. 9. Solution

題目描述

給予序列 $A \left[ 1 \cdots n \right]$，請計算前綴和序列 $S \left[ 1 \cdots n \right]$，其中 $$S \left[ i \right] = \sum_{k=1}^{i} A \left[ k \right]$$

為了檢測方便，移除輸入和輸出時間，序列 $A$ 由一個簡單加密 $\textit{key}$ 得到序列 $$A \left[ i \right] = \textit{encrypt}(i, \textit{key})$$以及輸出部分直接呼叫$\textit{output}(\textit{S}, n)$。注意$S\left[ 0 \right] = 0$，儲存答案的範圍為$S\left[ 1 \cdots n \right]$。

utils.h

可以直接 #include "utils.h" 在你的程式中。

1
2
3
4
5
6
7
8
9
10
11
#ifndef _UTILS_H
#define _UTILS_H
#include <stdint.h>
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;
}
void output(uint32_t presum[], int n);
#endif

prefixsum-seq.c

請修改這份程序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <inttypes.h>
#include "utils.h"
#define MAXN 10000005
#define MAX_THREAD 4
uint32_t prefix_sum[MAXN];
int main() {
    int n;
    uint32_t key;
    while (scanf("%d %" PRIu32, &n, &key) == 2) {
        uint32_t sum = 0;
        for (int i = 1; i <= n; i++) {
            sum += encrypt(i, key);
            prefix_sum[i] = sum;
        }
        output(prefix_sum, n);
    }
    return 0;
}

secret.c (測試用)

實際情況會用助教寫好的平行方式進行計算且雜湊公式不同。

1
2
3
4
5
6
7
8
9
10
11
12
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <inttypes.h>
#include "utils.h"
void output(uint32_t presum[], int n) {
    uint32_t hash = 0;
    for (int i = 1; i <= n; i++)
        hash += presum[i] * i;
    printf("%" PRIu32 "\n", hash);
}

輸入格式

輸入有多組測資，每組測資一行兩個整數 $n$, $\textit{key}$，分別為序列長度 $n$，加密金鑰 $\textit{key}$。

  • $1 \le n \le 10^7$
  • $0 \le key < 2^{32}$

輸出格式

對於每一組測資呼叫 output(uint32_t presum[], int n)，隨後會輸出一個數值。

範例輸入

1
2
3 2
10 5

範例輸出

1
2
100
54560

範例解釋

  • $(n, \textit{key})=(3, 2)$，得 $A \left[ 1 \cdots 3\right] = \left[ 4, 8, 12 \right]$，$S \left[ 1 \cdots 3\right] = \left[ 4, 12, 24 \right]$，$\text{hash} = 4 + 12 \times 2 + 24 \times 3 = 100$

編譯方式

1
gcc -std=c99 -O2 -pthread prefixsum-seq.c secret.c -o prefixsum-seq

測試主機資訊

推薦使用 4 個執行緒解決此問題，平行效能接近 2 倍改進。若使用過多的執行緒，將因為要排到另一個處理器上運行而變慢。

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
processor   : 0
vendor_id   : GenuineIntel
cpu family  : 6
model       : 62
model name  : Intel(R) Xeon(R) CPU E5-2620 v2 @ 2.10GHz
stepping    : 4
microcode   : 0x415
cpu MHz     : 1200.000
cache size  : 15360 KB
physical id : 0
siblings    : 12
core id     : 0
cpu cores   : 6
apicid      : 0
initial apicid  : 0
fpu     : yes
fpu_exception   : yes
cpuid level : 13
wp      : yes
processor   : 1
vendor_id   : GenuineIntel
cpu family  : 6
model       : 62
model name  : Intel(R) Xeon(R) CPU E5-2620 v2 @ 2.10GHz
stepping    : 4
microcode   : 0x415
cpu MHz     : 1200.000
cache size  : 15360 KB
physical id : 0
siblings    : 12
core id     : 1
cpu cores   : 6
apicid      : 2
initial apicid  : 2
fpu     : yes
fpu_exception   : yes
cpuid level : 13
wp      : yes

Solution

利用 $P$ 的 thread，分開計算區間 $[1, N/P], \; [N/P+1, 2N/P], \cdots$ 的前綴和，由於前綴和只有利用加法計算，加法具有結合律，隨後傳遞前 $i$ 段的和，可以循序 $\mathcal{O}(P)$ 完成，或者利用樹形平行 (tree-based) 的方式在 $\mathcal{O}(\log P)$，在實務上直接循序即可。

由於採用分治方式，需要平行兩次，時間複雜度為 $\mathcal{O}(2 \frac{N}{P} + P)$。

  • 當 $P = 3$ 時，只獲得 1.5 倍的加速
  • 當 $P = 4$ 時，獲得 2 倍加速
  • 當 $P > 4$ 時，要將記憶體的部分傳到另一顆 CPU 上，假設搬運時間是線性正比，計算複雜度也是線性時間，那麼搬運時間不如在同一顆 CPU 上運行。
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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <inttypes.h>
#include <pthread.h>
#include "utils.h"
 
typedef struct Argu {
    int l, r;
    uint32_t *psum;
    uint32_t key;
} Argu;
int min(int x, int y) {
    return x < y ? x : y;
}
void* subtask1(void *argu) {
    Argu data = *((Argu *) argu);
    int l = data.l, r = data.r;
    uint32_t *psum = data.psum; 
    uint32_t sum = 0, key = data.key;
    for (int i = l, j = 0; i <= r; i++, j++) {
        sum += encrypt(i, key);
        psum[j] = sum;
    }
    free(argu);
}
void* subtask2(void *argu) {
    Argu data = *((Argu *) argu);
    int l = data.l, r = data.r;
    uint32_t *psum = data.psum; 
    uint32_t base = data.key;
    for (int i = l, j = 0; i <= r; i++, j++)
        psum[j] += base;
    free(argu);
}
#define MAXN 10000005
#define MAX_THREAD 4
uint32_t prefix_sum[MAXN];
int main() {
    int n;
    uint32_t key;
    while (scanf("%d %" PRIu32, &n, &key) == 2) {
        int BLOCK = (n+MAX_THREAD-1) / MAX_THREAD, m = 0;
        pthread_t threads[MAX_THREAD];
        for (int i = 1; i <= n; ) {
            Argu *argu = (Argu *) malloc(sizeof(Argu));
            argu->l = i, argu->r = min(n, i + BLOCK - 1);
            argu->psum = prefix_sum + i, argu->key = key;
            i += BLOCK;
            pthread_create(&threads[m], NULL, subtask1, argu), m++;
        }
        for (int i = 0; i < m; i++)
            pthread_join(threads[i], NULL);
 
        m = 0;
        uint32_t block_sum = 0;
        for (int i = 1; i <= n; i) {
            uint32_t tmp = block_sum;
            block_sum += prefix_sum[min(n, i+BLOCK-1)];
            Argu *argu = (Argu *) malloc(sizeof(Argu));
            argu->l = i, argu->r = min(n, i + BLOCK - 1);
            argu->psum = prefix_sum + i, argu->key = tmp;
            i += BLOCK;
            pthread_create(&threads[m], NULL, subtask2, argu), m++;
        }
        for (int i = 0; i < m; i++)
            pthread_join(threads[i], NULL);
        output(prefix_sum, n);
    }
    return 0;
}