2006年度前期　応用数理工学特論　第１回質問シート集計結果


第１回の質問シートへの回答をありがとうございました。
授業でわかりにくかった点の指摘や授業方法に関する意見など，参考になりました。

以下に頂いた質問・意見とそれへの回答を載せます。意見に関しては，今後の授業にできるだけ
活かしていきたいと思います。


(1) キャッシュ向け最適化について

　　・これまで，あまりキャッシュのこととか考えていませんでしたが，より高速な計算をする
　　　にはそのようなことも考えていかねばならないのだと知らされ，驚かされました。

　　・コンピュータのキャッシュのサイズやプロセッサのFlops値などの情報はどのように調べ
　　　ればいいのか。

　　・5/25の講義でLU分解のブロック化についてのお話がありました。その中で，ブロックサイズ
　　　を「3個のブロックがキャッシュにおさまるようにとる」というのがありましたが，Windows
　　　マシンで計算させる場合，空きキャッシュサイズを調べることはできるのでしょうか？

　計算の高速化というと並列化を考える人が多いと思いますが，講義で説明した通り，最近のマイ
　クロプロセッサでは，キャッシュを効率的に使うことがそれと同程度に重要となります。ですの
　で，この講義ではキャッシュを有効利用するアルゴリズムについても詳しく説明しています。

　最近のサーバやPCでは，キャッシュのサイズがカタログに明記されていることが多いので，サイズ
　はそこから知ることができます。あるいは，C=AB という n×n の正方行列の乗算を（キャッシュ
　向けの最適化を行わずに）繰り返し計算した場合，この3個の行列がキャッシュに収まりきらなく
　なると性能が急激に落ちるはずなので，そこからキャッシュサイズを推定することもできます。

　Flops値は，（クロック周波数）×（１クロックで実行できる浮動小数点演算の数）で決まります。
　たとえば Opteron や Pentium 4 では，１クロックに浮動小数点演算が２個実行できるので，
　Flops 値は周波数の２倍となります。一方，Mac G5 に使われているプロセッサや情報連携基盤
　センターのHPC2500 に使われているプロセッサでは，１クロックで４個の浮動小数点演算ができる
　ので，Flops値は周波数の４倍となります。


(2) 密行列の連立一次方程式解法について

　　・連立一次方程式の解で，Ax = b のAをLU分解した後，何をするのですか？

　　・「ガウスの消去法」と「LU分解法」の具体的な区別がどの部分にあるかが少し疑問です。

　　・通信の隠蔽による高速化の部分の説明で,通信と計算の概念図が良く分からなかったので，
　　　もう一度説明が欲しい。

　A = LU とLU分解を行った後は，２個の連立一次方程式 Ly = b と Ux = y を順に解きます。これ
　により，Ax = b が解けたことになります。この２個の方程式は，係数行列が三角行列なので，
　前進消去と後退代入により簡単に解くことができます。

　「LU分解」と「ガウスの消去法」の関係ですが，5/18の講義ノートで説明されている通り，ガウス
　の消去法とは，係数行列 A に左から下三角行列を順々に掛けていくことにより，行列を上三角
　行列に変形する操作です。これは，ノートにある通り，行列を A = LU と積の形に表す操作と考
　えることができます。したがって，LU 分解という数学的に定義された分解を実際に計算するアル
　ゴリズムがガウスの消去法だということになります。

　通信の隠蔽については，6/1の講義ノートの図７を見てください。いま，第 K+1 のブロックピボット
　列を考えると，これを全プロセッサに送る必要がありますが，普通のやり方だと，他のプロセッサ
　はこれを受け取った後に第 K+1 段での消去演算（A_{IJ} の計算）を開始するので，データが２
　進木で送られている間，待っている必要があり，無駄な時間が生じます。そこで，もっと早くに第
　K+1 のブロックピボット列を作ってしまい，早めに他のプロセッサに送ることが考えられます。
　そうすれば，多少通信の時間が掛かっても，その間他のプロセッサは第 K 段での消去演算を行っ
　ているので，時間が無駄にはなりません。そうするためには，第 K+1 のブロックピボット列を持
　つプロセッサは，第 K 段での消去演算のうち，次のブロックピボット列となる部分の計算だけを
　先にやってしまえばよいわけです。これが図７の意味するところです。


(3) 疎行列の連立一次方程式解法について

　　・ポアソン方程式で 従属変数 u，右辺 f は物理的にどんな意味を持っているのか。

　　・フィルイン？

　　・スパースソルバの行列の斜線の部分で，L_{31} や U_{13} の中味は下三角や上三角行列に
　　　なっているのですか？

　ここで例として挙げたポアソン方程式は，物理の様々な分野に出てくる基本的な方程式です。
　たとえば静電場の場合，u は電位，f は電荷という意味を持っています。また，定常状態の温度
　分布を表す場合には，u は温度，f は熱源の大きさという意味を持っています。

　フィルインについては，時間の関係で説明できなくてすみません。疎行列に対して消去法を行う
　と，元々ゼロであった要素が非ゼロになることが起こります。これをフィルインと呼びます。
　フィルインが多く生じると，それだけ行列要素の格納に必要なメモリが増え，演算量も大きくな
　ります。そのためスパースソルバのオーダリングでは，並列性の抽出ということに加え，フィル
　インをなるべく少なくするということも考慮してオーダリングを行います。

　スパースソルバの行列（6/8の講義ノートの図４参照）では，L_{31} や U_{13} の中味は一般には
　下三角や上三角行列にはなりません。ただし，疎行列にはなるので，実際にはゼロでない要素
　のみを取り出して格納・演算を行い，メモリ量や演算量を減らしています。


　　・疎行列において反復法が高速化を望めるようですが，密においてはどうなるのか。また，
　　　疎行列として判別する基準はあるのでしょうか。

　　・今日6/8の講義は，A_{kk} の部分に一枚のバンド構造をもっている疎行列の解法でしたが，
　　　バンドが何枚もあるような構造をしている行列にも適用可能でしょうか？

　　・任意の疎行列に対してスパースソルバを使用するためにブロック対角化する方法，又は，
　　　他の高速な解法はありますか？

　疎行列として判別する基準は，絶対的なものはありませんが，非ゼロ要素が全体の10%以下ならば
　疎行列用の解法の適用を検討する価値はあると思います。ただし，疎行列だからと言って，反復
　法が必ず有利とは限りません。反復法は，ガウスの消去法と違って，行列の性質によっては収束
　せず解が求まらない場合もあるからです。一方，密行列であっても，極めて特別な形をした行列
　（たとえば対角線に沿って同じ要素が並ぶような行列）に対しては，反復法が有利な場合もあり
　ます。

　対角線に沿ってバンドが何本も並ぶ行列，あるいはより一般に任意の疎行列に対しても，スパース
　ソルバは適用可能です。一般の疎行列に対しては，講義での例と異なり，格子を見てセパレータを
　決めることは難しいため，行列の非ゼロパターンから自動的にセパレータを見つけ，行列を縁付き
　ブロック対角形に変換してくれるソフトウェアがあります。METIS というフリーソフトで，非常に
　広く使われています。


(4) 発展

　　・研究でGillespie Algorithm（モンテカルロ計算）を用いたシミュレーションをしているの
　　　ですが，こういった確率シミュレーションを少しでも高速化するアイディアはありませんか？
　　　並列化もほとんどできないので，CPUのクロックが上がる以外に計算がはやくなりません。

　Gillespie Algorithm について詳しく知らないので，あまりコメントできないのですが，例えば
　インターネットで Gillespie Algorithm と parallelization をキーワードとして検索してみては
　どうかと思います。ちょっとやってみたところ，このような論文が見つかりましたが，参考になり
　そうでしょうか。

　あるいは，期末発表のときに，Gillespie Algorithm の概要を紹介し，並列化のためのアイディア
　を皆で出し合うというのもいいかもしれません。


(5) 全般的な感想など

　　・計算機による演算において,様々な工夫により高速化が図られているが，その1つ1つの手法
　　　はそれぞれ面白いと感じている。少しの工夫で格段に改善されることもある。それらの手法
　　　の考え方に触れることが出来，今後自分の行う研究にもそのような発想が活かせればと思う。

　　・今まで計算速度の高速化をあまり意識せずにプログラムを組んでいたが，解析量が多くなっ
　　　たり，解析が複雑になってくると，効率のよい計算手法が求められてくると感じた。この講
　　　義では，マトリックス計算のさまざまな高速化処理方法を学んだので，今後の研究における
　　　シミュレーションで生かしたいと思う。

　　・授業のスピードも内容量も適度で分かりやすいです。これらの高速化アルゴリズムがどのく
　　　らい（すでにPC等で使われているのか … 等）使われているのかということが気になります。

　　・今の所はけっこう理解できました。質問は特にないです。

　　・並列計算の様々な活用法を知ることができて，役に立っている。

　　・とても分かりやすいです。

　感想をありがとうございます。高速化・並列化の手法は，実際に活用してこそ価値があるので，
　講義で学んだことをぜひ自分の研究に活かして欲しいと思います。


(6) 講義の進め方についての意見

　　・少し講義の進行速度が速いと思いました。スライドにまとめられていた方が理解し易いと
　　　思いました。

　　・毎回ノートをとるのに時間がかかり，話が全く聞けません。図やアルゴリズムはプリント
　　　にして下さい。細かい書き込みは自分で書くので。

　意見をありがとうございます。講義の後半では，時間の制約もあり，なるべくスライドを使って
　話をするようにしました。スライドはHPに載せますので，それ以外の，黒板に書いた部分を中心
　にノートを取ってもらえればと思います。

　図やアルゴリズムを書いたプリントだけを配り，そこに自分で書き込んでもらうというのはいい
　案ですね。検討します。


それでは，また何か意見や質問があれば，気軽に出してください。


応用数理工学特論のページに戻る
講義のページに戻る
Topに戻る