20019. Cooperative/Separate Dot Product

I'm a slow walker, but I never walk backwards.

題目描述

請用 OpenCL 改寫下段的計算:

main.c

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <stdio.h>
#include <assert.h>
#include <omp.h>
#include <inttypes.h>
#include "utils.h"
 
int main(int argc, char *argv[]) {
    int N;
    uint32_t key1, key2;
    while (scanf("%d %" PRIu32 " %" PRIu32, &N, &key1, &key2) == 3) {
        uint32_t sum = 0;
#pragma omp parallel for schedule(static) reduction(+: sum)
        for (int i = 0; i < N; i++) {
            sum += encrypt(i, key1) * encrypt(i, key2);
        }
 
        printf("%" PRIu32 "\n", sum);
    }
    return 0;
}

utils.h

你可以把這一段放入 kernel code 中使用,不一定要放在 host 上運行。

#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;
}
#endif

輸入格式

有多組測資,每組一行包含三個整數 $N, \; \text{key1}, \; \text{key2}$,表示向量長度 $N$、向量 $\vec{A}$ 由亂數種子 $\text{key1}$ 產生、向量 $\vec{B}$ 由亂數種子 $\text{key2}$ 產生。

  • $1 \le N \le 2^{30} = 1073741824$

輸出格式

對於每組測資輸出一行整數,為 $\vec{A} \cdot \vec{B}$ 的 unsigned 32-bit integer 結果。

範例輸入

16777216 1 2
16777216 3 5

範例輸出

2885681152
2147483648

編譯參數

1
gcc -std=c99 -O2 main.c -lOpenCL -fopenmp

特別約束

  • 建議直接在 GPU 上生成向量
  • 執行緒個數 限制解除
  • 請小心計算邊界 溢位

大測資分布

  • 3.in $N \approx 2^{26}$ 10000 組
  • 4.in $N \approx 2^{30}$ 2000 組

參考資料

Discussion