MPI 기반 매트릭스 곱 하기 summa 알고리즘 구현 (원본 프로그램 첨부)

과학 과 공학 계산의 많은 문제 중에서 행렬 곱셈 은 가장 기본 적 인 알고리즘 중의 하나 이다.분포 저장 병렬 기 에 있 는 전형 적 인 행렬 곱 하기 알고리즘 은 1969 년 Cannon 이 제시 한 2 차원 mesh 의 행렬 곱 하기 알고리즘 과 1987 년 Fox 등 이 제시 한 '방송 - 곱 하기 - 스크롤' 알고리즘 이 있다.1994 년 에 Choi 등 이 제기 한 PUMMA 알고리즘 은 Fox 알고리즘 을 2 차원 블록 커튼 데이터 분포 에 보급 시 켰 다.같은 해 에 Huss - ederman 등 은 Fox 알고리즘 을 가상 2 차원 서 라운드 데이터 분포 로 보급 했다.1995 년 에 van de Geijn 과 Watts 는 간단 하고 효율 적 인 행렬 곱 하기 알고리즘 을 제 시 했 는데 이것 을 SUMMA 알고리즘 이 라 고 부른다.
      서광 4000 병행 기 는 국가 스마트 컴퓨터 연구 개발 센터 가 개발 한 분포 저장 구조 와 정보 전송 체 제 를 바탕 으로 하 는 대규모 병행 컴퓨터 시스템 이다.본 고 는 전형 적 인 매트릭스 곱셈 알고리즘 인 SUMMA 알고리즘 이 서광 4000 과 같은 대규모 병렬 기 에서 의 실현 을 논의 했다.후속 단계 에서 작 가 는 다른 행렬 곱셈 병렬 산법 의 성능 을 계속 분석 하고 비교 할 것 이다.
      SUMMA 알고리즘 은 먼저 A, B, C 를 같은 크기 의 행렬 로 나 누 어 mesh 에 대응 합 니 다.r × mesh_c 의 2 차원 mesh 에서.그러나 SUMMA 알고리즘 은 행렬 곱셈 을 일련의 순위 nb 수정 으로 분해 합 니 다. 즉, 각 프로세서 의 A 와 B 는 각각 nb 크기 의 열 블록 과 줄 블록 으로 분해 되 어 곱 합 니 다. 앞에서 말 한 블록 사 이 즈 는 nb 의 크기 를 말 합 니 다.알고리즘 에서 방송 은 논리 프로세서 행 링 이나 열 링 의 흐름 선 전송 을 실현 하여 계산 과 통신 의 중첩 에 이 르 렀 다. 구체 적 인 설명 은 알고리즘 1 과 같다.
      알고리즘 1. 2 차원 mesh 의 SUMMA 알고리즘

C= 0

for i= 0 t o k-1 step nb do

　cur col = i×c/ n

　cur row = i×r / m

　if my col = cur rol      A  i mod (k/c)     nb  ,   A′

　if my row = cur row      B  i mod (k/r)     nb  ,   B ′

　C= A′×B ′

end for

      SUMMA 알고리즘 의 핵심 사상 은 각 프로세서 가 같은 줄 프로세서 에서 A 매트릭스 블록 의 모든 열 과 같은 열 프로세서 에서 B 매트릭스 블록 의 모든 줄 을 수집 한 다음 에 행렬 을 곱 한 후에 누적 하여 C 매트릭스 의 블록 행렬 을 만 드 는 것 이다.마지막 으로 rank = 0 의 프로세서 가 다른 프로세서 의 데 이 터 를 수집 하여 최종 행렬 C 를 형성한다.
      SUMMA 알고리즘 은 cannon 알고리즘 에 비해 SUMMA 알고리즘 은 m * l 의 A 매트릭스 와 l * n 의 B 매트릭스 상승 (m, l, n 은 같 지 않 음) 을 계산 할 수 있 고 cannon 알고리즘 은 n * n 의 A 매트릭스 와 n * n 의 B 매트릭스 상승 만 실현 할 수 있어 한계 가 크다.그러나 수준 이 제한 되 어 있 고 매트릭스 블록 을 잘 나 누 기 위해 이 MPI 가 구현 하 는 SUMMA 알고리즘 은 입력 한 매트릭스 비트 (m, l, n) 를 프로세서 개수 (사용자 가 정의) 의 정수 배 로 해 야 합 니 다. 그렇지 않 으 면 오 류 를 알려 줍 니 다.임 의 차원 의 행렬 상승 을 어떻게 실현 하 는 지 에 대해 서 는 위대 한 절차 원숭이 들 의 많은 지 도 를 바 랍 니 다.
      원본 코드 가 너무 길 기 때문에 여 기 는 일부 MPI 원본 코드 만 첨부 되 어 있 습 니 다. 모든 원본 코드 의 방문객 이 메 일 로 저 에 게 연락 할 수 있 고 연락 처 는 맨 아래 에 있 습 니 다.

/*summa   */

void My_summa(const int my_rank, int *a, int *b)

{

    int k, i, j;

    int *c;

    int len_c;

    int dest, tag;

    int my_rank_row, my_rank_col;

    int *a_col_send, *b_row_send, *a_col_recv, *b_row_recv;

    MPI_Status status_a, status_b;

    my_rank_row = my_rank / mesh_c;

    my_rank_col = my_rank % mesh_c;

    a_col_send = (int *)malloc((m / mesh_r) * sizeof(int));    

    b_row_send = (int *)malloc((n / mesh_c) * sizeof(int));    

    a_col_recv = (int *)malloc((m / mesh_r) * sizeof(int));

    b_row_recv = (int *)malloc((n / mesh_c) * sizeof(int));



        /*           A                     */

    for (k = 0; k < l / mesh_c; ++k)

    {

        for (i = 0; i < m / mesh_r; ++i)

        {

            a_col_send[i] = a[i * (l / mesh_c) + k];

        }

        for (i = 0; i < mesh_c; ++i)

        {

            dest = my_rank_row * mesh_c + i;

            tag = my_rank_col * (l / mesh_c) + k;

            MPI_Send(a_col_send, m / mesh_r, MPI_INT, dest, tag, MPI_COMM_WORLD);

        }

    }

       /*           B                     */

    for (k = 0; k < l / mesh_r; ++k)

    {                        

        for (i = 0; i < n / mesh_c; ++i)

        {

            b_row_send[i] = b[k * (n / mesh_c) + i];

        }

        for (i = 0; i < mesh_r; ++i)

        {

            dest = my_rank_col + i * mesh_c;

            tag = my_rank_row * (l / mesh_r) + k;

            MPI_Send(b_row_send, n / mesh_c, MPI_INT, dest, tag, MPI_COMM_WORLD);

        }

    }

       /*   C   */

    len_c = (m / mesh_r) * (n / mesh_c);

    c = (int *)malloc(len_c * sizeof(int));

    for (i = 0; i < len_c; ++i)

    {

        c[i] = 0;

    }

       

    for (k = 0; k < l; ++k)

    {      /*                   A               B    */

        MPI_Recv(a_col_recv, m / mesh_r, MPI_INT, my_rank_row * mesh_c + k / (l / mesh_c), k,

                MPI_COMM_WORLD, &status_a);

        MPI_Recv(b_row_recv, n / mesh_c, MPI_INT, k / (l / mesh_r) * mesh_c + my_rank_col, k,

                MPI_COMM_WORLD, &status_b);

               /*              C       ，           C  */

        for (i = 0; i < m / mesh_r; ++i)

        { 

            for (j = 0; j < n / mesh_c; ++j)

            {

                c[i * (n / mesh_c) + j] += a_col_recv[i] * b_row_recv[j]; 

            }

        }

    }

        /*     C     0   */

    MPI_Send(c, len_c, MPI_INT, 0, 99, MPI_COMM_WORLD);

    free(c);

    free(a_col_send), free(b_row_send), free(a_col_recv), free(b_row_recv);

}



 /*0       C    */

void Collect_C()

{

    int k, i, j;

    int len_c, id_recv;

    int *c_recv;

    int c_imin, c_imax, c_jmin, c_jmax;

    MPI_Status status;



    len_c = (m / mesh_r) * (n / mesh_c);

    c_recv = (int *)malloc(len_c * sizeof(int));

        /* C       C      */

for (k = 0; k < num_procs; ++k)

    {

        MPI_Recv(c_recv, len_c, MPI_INT, MPI_ANY_SOURCE, MPI_ANY_TAG, MPI_COMM_WORLD, &status);

        id_recv = status.MPI_SOURCE;

        c_imin = (id_recv / mesh_c) * (m / mesh_r);

        c_imax = c_imin + m / mesh_r - 1;

        c_jmin = (id_recv % mesh_c) * (n / mesh_c);

        c_jmax = c_jmin + n / mesh_c - 1;

        for (i = c_imin; i <= c_imax; ++i)

        {

            for (j = c_jmin; j <= c_jmax; ++j)

            {

                C[i][j] = c_recv[(i - c_imin) * (n / mesh_c) + (j - c_jmin)];

            }

        }    

    }



    free(c_recv);

}



 /*     */

void Print(char *str, int **matrix, int m, int n)

{

    int i, j;

    printf("%s", str);

    for (i = 0; i < m; ++i)

    {

        for (j = 0; j < n; ++j)

        {

            printf("%-6d", matrix[i][j]);

        }

        printf("
");

    }

    printf("
");

}

 컴 파일: mpicc summa.c -o summa -lm       주: p0 나타 나 면18495:  p4_error: Child process exited while making connection to remote process on node2: 0                                                                           Killed by signal 2.  이러한 오류, 해결 방법: 홈 디 렉 터 리 에 직접 입력: source / home / guest /. bashrc 실행: mpirun -np 9 summa 9 6 12
 실행 결과:

Allocate_A_B_C cheers!

Random_A_B cheers!

Scatter_A_B cheers!

Collect_C cheers!

random matrix A:

54    9     90    76    54    45    

52    70    1     99    64    31    

40    34    34    31    7     16    

82    26    18    70    29    44    

64    58    29    71    98    89    

42    5     50    84    81    4     

29    86    26    83    85    42    

66    77    76    0     8     35    

69    91    13    87    13    43    



random matrix B:

83    77    1     12    0     51    53    94    56    3     78    90    

60    8     28    38    43    65    81    9     42    9     61    50    

97    30    41    10    17    54    53    52    84    6     17    84    

58    70    79    66    26    57    8     38    17    36    76    60    

1     9     21    43    19    83    94    16    13    87    78    83    

94    32    35    78    90    4     62    48    75    93    67    53    



Matrix C = A * B:

22444 14176 12709 12738 8969  17193 16835 15749 16331 12402 19294 24297 

17333 13092 12303 14998 9607  18335 17209 11844 10776 12807 22936 21159 

11967 7117  5542  5707  4419  8498  8574  7892  8342  3843  9746  11445 

18337 13631 9227  11451 7755  13417 13420 14114 12063 9723  18818 19131 

24187 14962 13659 19104 14705 21137 24925 16584 17612 20247 28026 28207 

13965 11511 10709 10533 5148  16694 13815 11273 9543  10914 17401 20205 

18936 11620 13315 16285 11693 20427 21139 11382 13086 15306 23702 23355 

20768 9170  6731  7552  7905  13279 16685 12657 16043 5298  14106 18693 

21549 14014 11801 14071 10513 16346 16301 13559 13651 9366  21661 20430 



Print cheers!

successful run time is 0.109375