20029. Matrix Operation (CUDA)

題目描述

小明的數學作業要計算方陣，現在請你幫幫他！

題目給定$2$個 $N \times N$ 的矩陣和 $2$ 小題。

• $X = AB+BA$
• $Y = ABA+BAB$

sequence.c

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 <stdint.h>
// #define DEBUG
#define UINT uint32_t
#define MAXN 1024
void multiply(int N, UINT A[][MAXN], UINT B[][MAXN], UINT C[][MAXN]) {
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            UINT sum = 0;    // overflow, let it go.
            for (int k = 0; k < N; k++)
                sum += A[i][k] * B[k][j];
            C[i][j] = sum;
        }
    }
}
void add(int N, UINT A[][MAXN], UINT B[][MAXN], UINT C[][MAXN]) {
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++)
            C[i][j] = A[i][j] + B[i][j];
    }
}
void rand_gen(UINT c, int N, UINT A[][MAXN]) {
    UINT x = 2, n = N*N;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            x = (x * x + c + i + j)%n;
            A[i][j] = x;
        }
    }
}
void print_matrix(int N, UINT A[][MAXN]) {
    for (int i = 0; i < N; i++) {
        fprintf(stderr, "[");
        for (int j = 0; j < N; j++)
            fprintf(stderr, " %u", A[i][j]);
        fprintf(stderr, " ]\n");
    }
}
UINT signature(int N, UINT A[][MAXN]) {
    UINT h = 0;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++)
            h = (h + A[i][j]) * 2654435761LU;
    }
    return h;
}
UINT IN[2][MAXN][MAXN], TMP[6][MAXN][MAXN];
int main() {
    int N, S[2];
    scanf("%d", &N);
    for (int i = 0; i < 2; i++) {
        scanf("%d", &S[i]);
        rand_gen(S[i], N, IN[i]);
    }
    // AB
    multiply(N, IN[0], IN[1], TMP[0]);
    // BA
    multiply(N, IN[1], IN[0], TMP[1]);
    // AB+BA
    add(N, TMP[0], TMP[1], TMP[2]);
    printf("%u\n", signature(N, TMP[2]));
 
    // ABA
    multiply(N, TMP[0], IN[0], TMP[3]);
    // BAB
    multiply(N, TMP[1], IN[1], TMP[4]);
    // ABA+BAB
    add(N, TMP[3], TMP[4], TMP[5]);
    printf("%u\n", signature(N, TMP[5]));
    return 0;
}

特別約束

• 建議使用多張GPU平行加速
• 執行緒個數 限制解除
• Hint: multi-thread 配合 cudaSetDevice(GPUIndex)

輸入格式

輸入有多組測資，每組第一行會有一個整數 $N$，表示題目給定 $N \times N$ 矩陣，第二行上會有 $2$ 個整數，分別為矩陣 $A, B$ 的生成種子。

• $1 \le N \le 1024$
• $0 \le S_i \le 2^{31}$
• 最多 $512$ 組測資

輸出格式

每組測資輸出兩行 $X$ 和 $Y$ 的雜湊值，可參考 sequence.c 的流程。

編譯參數

$ nvcc -Xcompiler "-O2 -fopenmp" main.cu -o main

Sample Input

2
0 1
10
2 3

Sample Output

1047750017
1747023753
3808810853
1395844153