やかんです。
私、スパコンプログラミングを履修しております。が、出席率は4割程度というほんと、絶望的な状態です。
まじで悔やまれる、、
いやー、なんと言いますか。開発が忙しかったと言いますか。授業がオンデマだったため怠惰な部分が出てしまったと言いますか。
反省するしかないぜ、、
レポート提出間際になって駆け込みで勉強をするという、羞恥の極みみたいな勉強をします。ただ、この内容の勉強自体は僕の関心分野でもありますし、非常に有意義だと思っています。
Aセメでも開講するみたいだから、受けるしかないなこれは。とりあえずこのセメスターで単位だけ取っておきたい。
※内容は僕のパブリックメモ。
SUMMAを実装したい。
SUUMAとは、Scalable Universal Matrix Multiplication Algorithmのことで、行列 – 行列積の効率化アルゴリズムです。
発想としてはシンプルで、行列 – 行列積を部分行列に分解して計算したら効率的だよね、というアルゴリズムだと理解しています。
今回から数回かけて、SUMMAを実装しようと奮闘してみます。
最終的に実装を終えられるかはわからない。
そもそも行列 – 行列積の効率化とは？
行列のサイズが大きくなると、キャッシュに丁寧に載せてあげないとメモリバンド幅が爆増します。
「どういう分割をして、どういうメモリアクセスを期待して実装するか」によって、性能に大きな違いが生じるということですね。
これをMPIで実装する場合は（というかMPI以外の実装を知らないが）、メモリの共有をどうやるかっていう問題も性能に影響するようです。
ただ、転置はメモリ量に余裕がないと活用できないものだと思ってるんですが、どうなんですかね？転地した行列用のメモリ領域も確保しておく必要ありますよね？ポインタ操作には限界がありそうなので。
行列 – 行列積の効率化準備
まず、A * B = C（A, B, Cはn * n行列とする）を考えます。また、大前提として僕はC言語で実装するので、僕が行列 – 行列積といった場合にはC言語的な行列の扱いをする、ということです。
先に言っておくべきでした。すみません。
C言語的な行列の扱いは、シンプルに二次元配列です。C言語においてメモリアクセスが連続しているのは、二次元配列で行列を表現した場合に行方向のみです。列方向にはメモリが連続してないです、当たり前ですが。
キャッシュも考慮すると、やはり連続したメモリアクセスの方が良いに越したことはないので、A * BにおいてBを転置します。天才的ですね。転置すれば、行方向のみの計算で済むというわけです。
行列 – 行列積には3つの形式がある。
- 内積形式
- 外積形式
- 中間積形式
↑この3つです。内積は、「ベクトルの内積とか関係するのかな？」となりますが、外積ってなんぞやといった感じですよね。そうでもないですか、すみません。
ベクトルの外積とは
例の如く、「高校数学の美しい物語」がやはり神です（こちら）。
簡潔でわかりやすく、さらに深めたい場合は関連する内容も掲載されています。神としか言いようがないですね。いつもお世話になっております。ありがとうございます。
行列 – 行列積はループの順序入れ替え可能
これは、C言語とかで行列 – 行列積を実装してみたり、手動かして計算すればわかりますが、行列計算では、それぞれの計算が前の計算結果に依存しないのが特徴です。
そのため、言ってしまえば「行列計算で登場する計算は、任意の順番で行なって良い（ただし計算結果は正しく扱う必要がある）」といったようなところです。
行列 – 行列積の3形式
内積形式は、行列 – 行列積でループを回した時に一番内側のループで計算される計算が、ベクトル積になっている演算形式です。
外積形式も同様、最内ループの計算がベクトルの「外積っぽく」計算されている演算形式。あるいは、「最内ループの計算がベクトルの外積っぽくなるように、ループの順序を入れ替えた演算形式」と言った方が個人的にはしっくりきます。
中間積形式は両者の間に来る演算形式のようですが、どういうことだこれ。ちょっとよくわからんので、手を動かしてみるしかないか。これは個人的な宿題にします。
関連話題として、この辺の計算順序の入れ替えはコンパイラが最適化してくれたりします。もうほんと、コンパイラ屋さんは天才としか思えません。凄すぎます。。
Cannonのアルゴリズム
セミ・シストリック方式の行列 – 行列積におけるデータ共有方法です。方法というか、方針かな。
ん？
これはのちに登場するフル・シストリック方式と対比するとわかりやすいですが、ブロック行列化した行列において、「隣のブロックにのみ通信をする」という方式です。
また、N * N行列でプロセス数がpの場合、Nをpの平方根で割った値で1辺について分割します。そのため、1ブロックあたりに必要なメモリ量は、理想的には (N / pの平方根) ^2だと理解しています。
Foxのアルゴリズム
Cannonのアルゴリズムに対して、こちらはフル・シストリック方式の行列 – 行列積のデータ共有方針です。
もーすっごい雑ですが言語化むずいので、「隣のブロック以外にも適切なブロックに通信（放送の方が適切？）する」という方式。
ここで疑問なんだけど、Cannonの方が良くない？
SUMMA！！！
Foxの改良版的なイメージかな。
これまじで合っているかわからないんだけど、多分、ブロック行列化した後にその行、列についてブロードキャストしていくっていう方式だよね？Foxは1つのブロックごとにブロードキャストが行われていたけど、SUMMAでは1列あるいは1行ごとにブロードキャストされる、みたいな。
宿題
- 行列 – 行列積の3形式をC言語で実装。やっぱり、ループを使った実装には慣れが全てな気がする。
- Foxを実装する。
ということで、こちらのメモは終了。最後までお読みいただき、ありがとうございます。
