コメントです。行列計算の本質的なところに皆さんの目が向けられ つつあります。しかし、物理的制約のなかで不自然な目標を設定し てはいけません。 RM> =============================================================== RM> 5/15 第９回 meeting の報告 RM> ○ 考えてきた chip とメモリーの構成 について議論した。 RM> +------+ +------+ +------+ RM> |Memory| |Memory| |Memory| RM> |Large | |Large | |Large | RM> +-+--+-+ +-+--+-+ +-+--+-+ RM> A| D| A| D| A| D| RM> +-+--+-+ +-+--+-+ +-+--+-+ RM> | GS | | GS | | GS | RM> | | | | | | RM> +----+-+ +---+--+ +----+-+ RM> +-+ D| D| D| RM> | | | | | RM> |P+---------+----------+-----------+ RM> |C| | | RM> |I+------+----------+ | RM> | | A| D| A| D| RM> +-+ +-+--+-+ +-+--+-+ RM> |Memory| | GL | RM> |Small | | | RM> +------+ +------+ RM> 利点 行列 x ベクトル の計算で ベクトルをGLが送りながら、 RM> 計算できるので通信量が多少減る。 この動作手順、データの流れを見せて下さるのが来週火曜日までの 宿題です。 RM> PIN 数の制約を満足している RM> ( GL: AB 32 DB 64 GS: AB 32 DB 64*2 ) それぞれ 189 以下 RM> 電気的制約を無視すれば GS chip を 増やせる。 RM> 欠点 メモリが分割されているので、GS 間の通信が不便。 基本的に GS 間の通信は vector 以上のものはないはずです。ver 2,0 の構成がそれに敵しています。 RM> 課題 A = A + B のような計算 の場合 DRAMのメモリアクセスに淀みが出る。 行列計算の特徴は、演算量とデータ通信量の比が 1:1 に近いこと です。この比については、fortran の プログラムから正確に出す ことが出来ますので、ryouma, nguyen 君の担当のところで、演算 量入出力量を N の関数として評価してみてください。動作手順、 データの流れの表を完成したあとで、見直しを兼ねてその値を出し て下さい。 行列の計算は、N 個のベクトルをお互いに直交するように求めるわ けですから、原理的に他のベクトルの情報量 N^2 が無ければ 1 つ のベクトルを計算することはできません。従って N 個の ベクトル を求める時に必要な 情報量は N^3 になり、演算量 N^3 と同等で す。ハウスホルダー変換は、一見非常にうまいことをしているよう ですが、その本質に置いて近似計算ではありませんから、線形空間 を縮めているわけではありません。 RM> ハウスホルダー逆変換が分離可能か? => 可能 RM> RM> その他 クロック 33.3MHz チップ数 3 GS内演算 4 step とすると、 RM> 400Mflops 程度の性能(瞬関最大風速) RM> ※齋藤先生のコメント 十分です 但し、計算機を淀むこと無く動かすこ RM> とが目標です。 現在の Work Station の普通のもので、1000x1000 の対角化は 1000 秒です。Supercomputor でさえ、この 10 倍程度です。実効 速度は全て memory cash の I/O によって支配され、その速度は、 1 秒間に 平均 1M-10M word (1 word = 8 byte) です。上の構成で は、その 10 倍の 100 M word の速度が期待できそれが目標です。 このように 入出力情報量 : 演算量 = O(1) の世界では、計算速度 をあげるには、chip の 演算処理能力をあげることより、データの 入出力まで含めた pipeline の設計が必要です。33.3Mhz で 33M word しか入出力できないのであれば、演算処理能力は 33MFlops 以上のものをつくる必要はないことになります。そのかわり、デー タの入出力に決して淀みが生じないことが重要です。 このような、データ入出力速度と演算速度が 1:1 の chip を GM に作るのが目標だと考えます。松尾君が言っていましたが、演算装 置はデータとデータの間にある線の一部にしか過ぎません。重要な のは演算より、データのやり取りだと思います。 GS chip の 下に GM chip をつくって 2 分岐のように データバ スを太くしていくことが可能です。線を太くする方法論がこの chip の 基本設計になります。 GL <= 2 GS <= 4 GS <= 8 GS <= 16GM 上の場合 GS は 単に データを 2 分配する機能しかありません。 GL が GS の 分配方法を支配すればよいのです。これは、16 個の GM を 並列に置いた場合とは、本質的に違うはずです。このことを、 実際の計算において示す必要があります。 RM> # GS内演算 が 1 step の場合もありそう... 実効性能は?? 現在は GS = GS + GM と考えて memory からの入力 1 step で 内 積の pipe line が 1 つ進まなければ行けません。 RM> ○ GS 内部のレジスタ 用いて もっとデータを使い回せないか? これが出来ないのが MD-1 と違うところです。演算量を増やすこと ができません。 RM> ○ GS 内に メモリを持つか、外部に持つか? GS 内には pipeline の データの buffer としての register が必 要です。また データを一定の速度で送りつけるために、離散的に 存在するデータを貯める SRAM が必要かもしれません。 RM> # 今のところの制約では 外部に持つしかないが。 RM> もし、内部に持てるなら、bus 幅が大きくできる可能性あり。 bus 幅を大きくすることは GM を 増やすことで実現します。 将来 LSI を つくる場合には、そのような 構造を 1 つの LSI 上 に実現します。 RM> ○ LSI化 を考える時、設計が GSをコピーだけで 済む構成がないか? RM> ○ 上に関して GS の持つメモリーを小さくして、外部から高速にデータを送 RM> り込む構成は考えられないか? chip に入る速度が 33Mhz であり、pin の数が 有限である限り、 どのような構成を持ってしても、単位時間に入り得る情報量は同じ はずです。これらは 物理的制約であり、これを解決することも一 つの手段ですが、データ入出力速度と演算速度が 1:1 を解決出来 ないのであれば、斬新な構成は非常にマイナーな変更になるはずで す。 私が あっと 驚く方法があればまた話が別ですか、少なくても エ ネルギー非保存の方法のような議論に入ってはいけません。 RM> ○ 他に斬新な構成は無いか? RM> 1bit演算の並列コンピュータ ぐらいの発想.. これは、まったく別のアルゴリズムを考える必要があります。 1990 年代前半に提案された 対角化のアルゴリズムは基本的に全て 近似計算で、帯行列の対角化と同じです。共役勾配法による固有ベ クトルを N 次元空間で探索する法は厳密で限られた数の固有ベク トルを求めるのに有効ですが、この場合でも MD 1 step ごとに行 列 A の全ての情報が必要になります。この場合、情報の入出量は N^2 です。しかし計算するベクトルを複数 chip (または SRAM) の なかに貯め込めるので、A の情報を共有して使えます。 これはハウスホルダー逆変換のときや逆反復法で有効に使えると思 います。 RM> ○ もっと 仮想的なchip を考えるのは? もし現実的に設計しなければ、研究の目標が失われるように思いま す。 RM> -------- -------- 電気通信大学電子工学科 齋藤 理一郎 rsaito@tube.ee.uec.ac.jp