3

私は並列プログラミングが初めてです。2 つの行列を乗算しようとしています。問題を次のように分割しました。

操作を mat3 = mat1 x mat2 とします。mat2 をコミュニケーターのすべてのプロセスにブロードキャストし、mat1 の行のストリップを切り取り、それらをコミュニケーター グループのプロセスに分散させます。すべてのプロセスが mat2 全体と対応する mat1 のストリップを取得した後、ストリップを mat2 で乗算し、プロセスのローカル結果で収集操作を使用して、結果全体をルート プロセスに蓄積します。

汎用コンピューターで2つの行列を乗算するためのより良い問題の分割があるかどうかを知りたいと思いました。

私の実装は OpenMPI です。

4

1 に答える 1

5

行列乗算に関する文献には、MPI パラダイムに拡張できるさまざまなアルゴリズムがあります。例えば：

> 1Dsystolic [1] 
> 2D-systolic, Cannon’s algorithm [2];
> Fox’s algorithm [3];
> Berntsen’s algorithm [4];
> DNS algorithm [5].

マトリックスの妥当性 (スパース ect) を無視すると、基本的にデータがプロセス間でどのように分散され、同期と負荷の不均衡 (各プロセス間で分散される作業量) が最小限に抑えられます。

この最近の作業では、2 つの異なるデータ分散アプローチとそれらの比較を見ることができます。

論文:

[1] Golub G.H and Van C.H L., “Matrix Computations.”,Johns Hopkins University Press, 1989.
[2] Whaley R. C., Petitet A., Dongarra J. J., “Automated empirical optimizations of software and the ATLAS project” Parallel Computing 27, 1.2 (2001), 3.35.
[3] Fox G. C., Otto S. W., and Hey A. J. G., “Matrix algorithms on a hypercube I:
Matrix multiplication”,Parallel Computing, vol. 4, pp. 17-31. 1987.
[4] Berntsen J.,“Communication efficient matrix multiplication on hypercubes, Parallel Computing”, vol. 12, pp. 335-342, 1989.
[5] Ranka S. and Sahni S., “Hypercube Algorithms for Image Processing and Pattern Recognition”, Springer- Verlag, New York, NY, 1990.
于 2012-11-15T18:05:58.540 に答える