10084. Prefix Sum (pthread)

題目描述

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

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

輸出格式

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

範例輸入

3 2
10 5

範例輸出

100
54560

範例解釋

• $(n, \textit{key})=(3, 2)$，得 $A \left\lbrack 1 \cdots 3\right] = \left\lbrack 4, 8, 12 \right]$，$S \left\lbrack 1 \cdots 3\right] = \left\lbrack 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

測試主機資訊

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

由於 NUMA 的緣故，在主程式運行前，將其執行緒設定在 CPU0~CPU5 之間運行，其測試結果較為穩定。

#define _GNU_SOURCE
...
int main() {
        {
                cpu_set_t cpuset;
                CPU_ZERO(&cpuset);
                for (int i = 0; i < 6; i++)
                        CPU_SET(i, &cpuset);
                assert(sched_setaffinity(0, sizeof(cpuset), &cpuset) == 0);
        }
...

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