• 主記憶量
• ネットワークバンド幅

来年くらいには 4GB DDR3 のモジュールも安くなると思うので、なんらかの形 で 24GB とか48GB まで増強すれば効率はかなり上がることになります。

HPC Linpack の性能は、基本的には以下のように書けます。

現在動作している GRAPE-DR のクロック 380MHz でも、カードを2枚つけた時 演算速度は 1.5Tflops にもなり、ホストの Core i7 920 の 40倍近くになり ます。メモリバンド幅は連続アクセスで 16GB/s 程度、つまり2G語/秒程度で すから、演算速度とはほぼ 1000倍の差が連続アクセスでもあるわけです。と ころが、HPL の場合、メモリアクセスは連続にはなりません。というのは、

• ピボット探索のための列方向アクセス・小さい幅での列パネル変形
• ピボット行交換のための行方向アクセス

並列版になると、これらは通信にもなるのでもうちょっと面倒ですが、本質的 には議論は変わりません。まず、計算量やメモリアクセス量の比は、1ノード当 りの行列サイズで決まる、というのは落ち着いて計算すればわかります。 のプロセスグリッドを考えると、行列サイズは 倍、DGEMM の速度は 倍、ピボット探索や行交換の速度は 倍だからです。

現在の通常の HPL の実装・実行では、行列は列方向が連続になるようにメモリ に格納します。この結果、ピボット探索を高速化し、行交換は速度が落ちても やむをえない、としているわけです。1ノードの場合には、これはそんなに悪い 選択ではありません。1列毎に入れ替えをする形のループにすることで、ある程 度までメモリアクセスの局所性を保つことができるからです。但し、並列版で は普通に書くと行方向のアクセスになるので大きな間隔でのストライドアクセ スになって性能がかなり低下します。

現代の計算機でのストライドアクセスの性能低下の理由は、キャッシュライン の一部しか使われないことと、 TLB ミスです。 TLB ミスは 2MB とか 4MB の いわゆる Huge TLB を使うことで抑えることができますが、キャッシュライン の一部しか使われない、というのはメモリ格納オーダーを変えるしかありませ ん。最近の機械はラインサイズが 64バイトになっていて結構大きいので、TLB ミスがなくても不連続アクセスの速度は 1/8 まで落ちることになります。

格納オーダーを変えるのは色々考え方があって、一つはペアノ曲線やモートン オーダーを使った再帰的な配置にすることです。ペアノ曲線の場合には大雑把 にいって、縦方向のアクセスでも横方向のアクセスでも、半分が隣接、1/4 が 2倍離れ、、、、というような感じになるので、どちら方向でも性能低下か 3 倍程度に抑えられるはずです。実際にこのようなアクセス方式で Level 3 BLAS を自動チューニングする、といった研究もあります。

しかし、そうはいってもペアノ曲線とかではデータがどこにあるのかすぐには わからない(HPL 専用プロセッサを作るならアドレス変換をハードウェアでや るといった可能性もあります。これはビットシャッフルだけなので本当は時間 かからないので)ので、もうちょっと単純な方式を使いたいところです。例え ば、サイズ2とか4の短いベクトル単位で行方向に格納し、それを列方向に格納 する、といった形の行列を考えてみます。

この場合には、サイズを m とすると最大値探索の速度は単純な列方向格納の場 合の 1/m になり、行交換の速度は m 倍になります。列パネル変形は微妙で、 上手く書けばあまり変わらないはずです。最大値探索と行交換のどっちが元々 大変か、というと、最大値探索は行列全体の半分を read するだけですが、行 交換はやはり半分について、交換なので 2回 read, 2 回 store となり形式的 には4倍のアクセスになります。実際にはキャッシュヒットがどれだけか、とい うのがあるので4倍にはならないですが、それなりに多いはずです。

と思うと、元々行方向に格納しておけばよいのではないかという気もします。 が、 HPL のコードは入力行列については必ず列方向格納をする (分解後の L, U については選択できる)ので、これは HPL を全部書き直さないと実験できま せん。

何故 HPL のコードが列方向格納になっているかというと、これはおそらく歴史 的な理由ではないかと思います。つまり、 Linpack benchmark というと 100x100 とか 1000x1000 であった時代、つまり、シングルプロセッサのスカラ 機やベクトル機がベンチマークの対象であった時代には、使われていたアルゴ リズムもせいぜい縦ブロックガウス消去法くらいなので、基本的に演算量の多 い操作ではベクトル化の方向が縦(列)方向になります。なので、列方向格納で ないと性能的には全く話にならないわけです。

しかし、現代的なアルゴリズムでは、そもそも演算量の多いところは殆ど全て 行列乗算に置き換わっているので、演算ではないピボット操作とか行入れ替え が究極的には問題になるはずです。なので、これらの時間を最小化するような データ配置が望ましいです。もちろん、実際には、そんなところが問題になる ところまで行列乗算の性能を引き上げてしまったのはアクセラレータ付きシス テムの中でも GRAPE-DR が初めてであり、このために従来のシステムでは全く 問題にならなかったところの実行時間が問題になってきているわけです。

ずっと上で述べたように、このようなところの実行時間が問題になるもう ひとつの理由は単純にホスト計算機のメインメモリ容量が不足していることで すが、やはり、根本的な問題はこれまでの他のシステムでの経験の蓄積がない ところまで行列乗算を高速化した、ということ自体にあり、このために 従来なされてきたのとは違う部分の高速化が必要になっているわけです。

というわけで、現在のところ DGEMM 本体についてはピーク性能の 75%以上が でるところまでチューニングできていますが、 HPC Linpack についてはもう ちょっとお待ちを、、、という状況です。

DGEMM 以外のもの、としてピボット探索と行交換をあげましたが、実際にはこ れらが全てではもちろんありません。一つのポイントは、 GRAPE-DR では(実は、 ClearSpeed 等のアクセラレータや、また GPU を使う場合でも事情は同じです が)、 DGEMM が速くなるための条件があるのです。それは、行列の幅が大きい ことです。行列乗算を式で書くと

    for(j=0;j<N;j++){
        for(i=0;i<M;i++){
            C[j][i]=0;
            for(p=0;p<K;p++){
                C[j][i]+= A[p][i]*B[j][p];
            }
        }
    }