行列の足し算の並列化

このページでは並列プログラミングの第一歩として，行列の足し算を並列化します．行列の足し算の並列化は非常に簡単です．実際にプログラムを動かして，並列プログラムの効果を確かめましょう．

行列の足し算

行列の足し算は行列の各要素を足し合わせたものになります．

逐次版，行列の足し算

実際に行列の足し算を行うプログラムを作成していきます．以下にプログラムの一部を掲載します．すべてのコードは配布パッケージのapp/sample/matrixadd/matrixadd_s.cに存在します．

#include <stdio.h>
#include <MClib.h>

#define MATRIX_SIZE 600

int a[MATRIX_SIZE][MATRIX_SIZE];
int b[MATRIX_SIZE][MATRIX_SIZE];
int c[MATRIX_SIZE][MATRIX_SIZE];

int main()
{
    int id_x, id_y, rank_x, rank_y;
    MC_init(&id_x, &id_y, &rank_x, &rank_y);

    if (id_x == 1 && id_y == 1) {
        // 行列の初期化
        int i, j;
        for (i = 0; i < MATRIX_SIZE; i++) {
            for (j= 0; j < MATRIX_SIZE; j++) {
                a[i][j] = i * j;
                b[i][j] = j + i;
            }
        }
        // ここから計測
        unsigned long long int start_clock;
        MC_clock(&start_clock);

        // 行列の足し算
        for (i = 0; i < MATRIX_SIZE; i++) {
            for (j= 0; j < MATRIX_SIZE; j++) {
                c[i][j] = a[i][j] + b[i][j];
            }
        }
        // 経過時間の表示
        unsigned long long int clock;
        MC_clock(&clock);
        printf("cycle: %llu\n", clock - start_clock);
    }

    MC_finalize();
    return 0;
}

このプログラムは行列aと行列bを足し合わせ，行列cを作成します．単純な2重ループですべての要素を足し合わせています．コンパイルして実行してみましょう．

## SimMc M-Core alpha : Many-Core and NoC Simulator v1.1 2010-07-30
## [SimMips: Simple Computer Simulator of MIPS Version 0.5.0 2008-11-05]
## DEBUG MODE 0, LOG MODE 0
## comp node (1,1) - (1,1)
## memory node (0,0)
## path node (0,1) - (0,1), (1,0) - (1,0)
## Multi-Core library MClib v1.0.0 2009-12-16
cycle: 3247214
## Simulation time    2.781 [sec]
## Simulation cycle  5792399
## Simulation 2083.115 kilo cycle / sec

1コア実行では325万サイクルかかりました．

行列の足し算の並列化

ここからはM-Coreアーキテクチャ上で行列の足し算を並列化していく方法について，書いていきます．並列化の方針として，与えられた行列を部分行列に分割し計算する方法をとります．

3×3のノードを持つM-Coreで，部分行列に分けて計算する例を下の図に示します．

計算はまずNode(1,1)が各コアに計算すべき部分行列を配布します．各コアは部分行列が届いたのを確認した後，足し算を行います．計算終了後，各コアはNode(1,1)に計算結果を送信します．

コードは配布パッケージのapp/sample/matrixadd/matrixadd.cに存在します．また，ソースコードに解説を加えた図をこちらから表示できます．

それではコンパイルして実行してみましょう．今回は3×3のノードで実行します．

## SimMc M-Core alpha : Many-Core and NoC Simulator v1.1 2010-07-30
## [SimMips: Simple Computer Simulator of MIPS Version 0.5.0 2008-11-05]
## DEBUG MODE 0, LOG MODE 0
## comp node (1,1) - (3,3)
## memory node (0,0)
## path node (0,1) - (0,3), (1,0) - (3,0)
## Multi-Core library MClib v1.0.0 2009-12-16
cycle: 1477073
## Simulation time   11.907 [sec]
## Simulation cycle  4024070
## Simulation  337.956 kilo cycle / sec

9コア実行では148万サイクルかかりました． 1コアと比較すると約2.2倍の高速化となります． 9コアで9倍高速化しない理由は，初期行列の配布と計算結果の集計にかかる通信時間のためです．通信を最適化することでさらなる高速化が可能です．また，行列和のほかにも並列化できるプログラムは多数存在します． SimMcを利用して，様々な並列プログラムに触れてみましょう．

M-Coreトップ