やかんです。
引き続きスパコンプログラミングに関して、SUMMAの実装に励んでいきます。それはそうと、SUMMAってマイナーなアルゴリズムなんですかね？ググってもあまり出てきません。そもそもスパコンプログラミング自体、母数が限られるのだろうか？
とりあえず頑張ります。
※内容は僕のパブリックメモです。
まずは行列-行列積に慣れる。
SUMMAもやってることは行列-行列積に変わりないので、まずこの演算の実装になれるところから始めたいと思います。前回記事でも触れた通り、プリミティブな行列-行列積は3つの方式があります。内積、外積、中間積の3つですね。順に見ていきます。
内積形式
いわゆる「線形代数」みたいな文脈からしたら一番素直な形式だと思われます。このブログは数式の記号に対応してないのでコードと日本語でお茶を濁しますが、
C = A * B
という行列演算において、Aについては行方向に見ていき、Bについては列方向に見ていくという積の計算方法です。計算方法というか、これが行列積の定義だと理解してるんだけど、これは合ってるのかな？後に見る外積形式とかはこの定義をもとに同値変形したものだと思ってます。違うのかな。
さて、Cで実装すると以下のようになると思います。非常にシンプルですね。シンプルですが、気を抜いていると添え字を間違えます。
// 正方行列のみ考える
void matrix_multiply(int n, int p, double **A, double **B, double **C)
{
for (int i = 0; i < n; i++) // 行についてインクリメント
{
for (int j = 0; j < n; j++) // 列についてインクリメント
{
C[i][j] = 0.0; // 演算結果の行列におけるi行j列
for (int k = 0; k < n; k++) // 行列の1要素を計算
{
C[i][j] += A[i][k] * B[k][j];
}
}
}
}Cで実装してみるとより明らかなように、配列のメモリアクセスがこのままだと随分乱暴です。行列のサイズが大きくなると、キャッシングがうまくいかずメモリアクセスが増えます。コンピュータアーキテクチャでも学習した通り、メモリアクセスはクロックのサイクル数が桁違いに多いので、見るからに性能低下の要因です。
そのためキャッシュをうまく利用したいということで、キャッシュに関する時間的局所性、空間的局所性の性質に鑑みて配列における連続したメモリアクセスを実現したいです。これは、C = A * BにおいてBを転置すればいいですね。
転置した場合に追加で必要になるメモリ量との相談なのかもしれませんが、転置してA, Bともに同じ方向に要素を見ていくようにすれば、メモリアクセスによる遅延を抑えることができるはずです。
外積形式
これ、ややこしいからほんとやめてほしいんですけど、行列積に関して「外積形式」と言われる場合、ベクトルの外積とは別物であるという点に注意が必要です。賢い人は双方の共通点を得て納得するのかもしれませんがね。。
さて。というわけなので、「外積形式」という特殊な行列積の計算方法だ、という理解が良いのではと思っています。どちらかというと、「行列積の定義に基づき、この演算を工夫して実行する一つのアルゴリズム」について、「外積形式」という名前を付していると理解した方が良さそうです、というのが僕の今の理解です。
これは、なんというか、言葉で説明するのがむずいです。数式書いて説明を試みたいところですが、このブログじゃ数式書けないのでまたまたコードでお茶を濁します。
// 正方行列のみ考える（外積形式）
void matirx_muptiply_outer_product(int n, double **A, double **B, double **C)
{
// 外積形式の場合は、演算結果である行列Cの各要素を順次更新するという手法であるため、最初にCの各要素を初期化する必要がある。
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
C[i][j] = 0.0;
}
}
// 行列積の計算
for (int k = 0; k < n; k++) // kを一番外側のループに置く
{
// 以下、iとjが i -> jの順になっているが、この2つは等価だから入れ替えても良いはず。要は、AとBのどっちを転置しますか、という話だから。
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
C[i][j] += A[i][k] * B[k][j];
}
}
}
}外積形式だと何が嬉しいかというと、何も嬉しくないのでは、というのが僕の理解です。メモリアクセスは相変わらず乱暴だし、さらにCの全要素に毎回触れるため、その分キャッシュも圧迫するからむしろ性能としてはマイナスなんじゃないのかな、、、どうなんだろう。誰か教えてください。
この辺は頭こんがらがるので理解に自信がない
中間積形式
これはマジでわからんのだが。内積形式と同じではないのか？有識者の方、教えてください。。
この程度で「行列積習熟しました！」とか言えるわけないんですけど、レポートの提出期限も近いのでこの辺で慣れたことにして次に進みます。
次は、MPIを使いながらCannonのアルゴリズムを実装していきます。てなわけで、こちらのメモは以上。最後までお読みいただき、ありがとうございます。
