# 10121. Fast Matrix Multiplication (MIC)

## 題目描述

### matrix.h

1void multiply(int N, unsigned long A[][2048], unsigned long B[][2048], unsigned long C[][2048]);


### matrix.c

12345678910111213#include "matrix.h" __attribute__ ((target(mic)))void multiply(int N, unsigned long A[][2048], unsigned long B[][2048], unsigned long C[][2048]) {    for (int i = 0; i < N; i++) {        for (int j = 0; j < N; j++) {            unsigned long sum = 0;    // overflow, let it go.            for (int k = 0; k < N; k++)                sum += A[i][k] * B[k][j];            C[i][j] = sum;        }    }}


### main.c

1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253#include <stdio.h>#include "matrix.h" // #define DEBUG#define UINT unsigned long #define MAXN 2048void 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 hash(UINT x) {    return (x * 2654435761LU);}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 = hash(h + A[i][j]);    }    return h;}static UINT A[MAXN][MAXN], B[MAXN][MAXN], C[MAXN][MAXN];int main() {    int N, S1, S2;    while (scanf("%d %d %d", &N, &S1, &S2) == 3) {        rand_gen(S1, N, A);        rand_gen(S2, N, B);        #pragma offload target(mic) in(A,B) out(C)        {            multiply(N, A, B, C);        }#ifdef DEBUG        print_matrix(N, A);        print_matrix(N, B);        print_matrix(N, C);#endif        printf("%u\n", signature(N, C));    }    return 0;}


## 輸入格式

• $1 \le N \le 1000$
• $0 \le S1, S2 \le 65536$

## 範例輸入

2 2 52 2 5


## 範例輸出

573770929573770929


## 解釋

$$A = \begin{bmatrix} 2 & 3\\ 0 & 0 \end{bmatrix} , B = \begin{bmatrix} 1 & 3\\ 3 & 0 \end{bmatrix} , A \times B = \begin{bmatrix} 11 & 6\\ 0 & 0 \end{bmatrix}$$

## 編譯參數

icc -std=c99 -O2 -qopenmp main.c -cicc -std=c99 -O2 -qopenmp matrix.c -cicc -std=c99 -O2 -qopenmp main.o matrix.o -o main