2011年06月20日

ICFPC2011

AIの挙動とかは後でチームの誰かが書いてくれるだろうし、覚えている限りでどういう戦い方をしたのか記録しておこうと思う。

続きを読む
posted by chun at 09:09| 関数型

2011年03月28日

続:Amazon Clusterインスタンスで計算

震災から2週間が過ぎました。
まず、今回の震災で被害に遭われた方々、またご家族が被害に遭われた方々にお見舞い申し上げます。

被災地域直接ではありませんが、震災の影響範囲に私なりに少しでも出来ることをと考え、この記事を書くことにしました。
ご存じの通り、現在の東日本では電力状況が切迫しており、輪番停電が実施されております。
これは、計算機クラスタを日常的に研究に使う者にとっては非常に厳しい状況です。
各研究室で所有しているクラスタも、節電と輪番停電のため動かせない状況が続いていると伺っています。
また、外部計算リソースについても、現在の日本の外部利用可能な計算機の状況を@plus7さんがブログで纏めて下さいました。これはほぼ壊滅的と言って良い状況です。
そこで、本記事ではAmazon Elastic Compute Cloud (EC2)を使って、即席計算リソースを作る手順を記述してみようと思います。操作環境はLinuxを想定しています。
続きを読む
posted by chun at 02:52| 日記

2011年01月01日

2010年を振り返る

2010年は卒業含め色々と大変な年でした。

1・2月はほとんど卒業に向けての何かで過ぎていった記憶があります。3月には4年過ごした部屋を引き払って京都に移り住みました。引っ越し前後のスケジュールが悲惨きわまりない状況になっていたため、ボロボロになりながら京都に到着、京都に着いてからもさらに1日大変な目にあったのが良い思い出です。4月からは京都の宇治(京大化研)でポスドクを開始。いきなり研究室の引っ越しをしたりと色々大変でした。5月からは事情により大学の仕事がデスマ進行になってしまい(ところでマーチ+進行って頭痛が痛い?)大変なことに。9月までずっと繁忙期でした。まぁこの時見つけたネタをいま色々と料理している状況なので、悪いことばかりではありません。繁忙期と言いつつ6月には休暇を取って東京に行きICFP contestに参加。チームのメンバーが凄すぎて生きているのが辛い(TM)状況に。優勝を勝ち取ったものの、ぶっちゃけ僕が居なくてもこのチームは取れたと今でも思ってます! 7月8月は繁忙期継続。9月-10月には優勝したおかげでICFPの本会議に出席してくることが出来ました。twitterでも書きましたが、英語が聞けて関数型言語に興味ある人はぜひ一度は学会に出てみると良いと思います(宿泊費も参加費も旅費も高いですけどそれでも! しかも今年は東京ですよみなさん!)。濃密な実現可能な妄想が飛び交う空間というのは素晴らしいです。出張途中に寄った大学でも新しいネタをもらって来ました。11月はちょっと休息モード。流石に5月からの進行のツケが回ってきたので一旦休憩したり。あと3ヶ月ぐらい真面目に考えていたネタが潰れて凹んだりしていました。あと長年苦しんだ論文が出版されました。なんかカバーペーパーになったらしく非常に嬉しいです。この論文は難産でしたし、結果も何かを証明するには微妙に不足しているのですが、モデルは非常に気に入っているのでこれからも頑張って育てていきたいと思います。12月は溜まりに溜まったタスクを潰したりしていました。あとFO3:NVやったりとか。近接戦闘のシステムがあんまり進化していないのでES5が心配です。

皆様2011年もよろしくお願いします。
posted by chun at 19:08| 日記

2010年10月02日

ICFP contest 2010 優勝

ICFP contest 2010で優勝しました。6人編成のチーム pure pure code++ として参加していました。参加の様子などは下記エントリを参照下さい。

http://shuns.sblo.jp/article/39084088.html
http://shuns.sblo.jp/article/39320300.html
http://shuns.sblo.jp/article/39240773.html

"please keep your status (winning the contest) a secret until you get the prize during the conference." と言われていたので渡航とかの話は途中までカモフラージュしていたのですが、ICFP(関数型言語に関する国際会議)の会場参加者から私の存在がtweetされたりして意味が無かったです。バレバレ。というかメンバーが軒並み出張はどうみても怪しいです本当にありがとうございました。

ところでこの渡航の途中にアメリカのある研究室に寄ったのですが、その会話がこんな代物でした:
「で、どんなものを競うコンテストだったんだい?」
「ああ、説明が難しいな。えぇと、僕たちは『プログラムが停止するか』を判定するプログラムを書いたんだ。」
(嘘は吐いてない、嘘は吐いてない、ちょっと、ちょこっと真実をぼかしただけ!)
posted by chun at 09:54| 日記

2010年09月30日

HLPP参加記

HLPP参加記。例によって辛口。

Dr.Hu 招待講演(NII)

  • 電車を一本逃したので途中から参加。USの列車に期待してはならない。
  • Homomorphismを使ってプログラムをバリバリ変換するお話。
  • 変換のために便利なのがweak inverse. この手の変換をするには逆関数が非常に重要。
  • 全単射ではないので変換結果が正しくなるような関数群のうちの一つを使う
  • Non-trivialな問題をMap-reduce型とかに変換できる。


J. Enmyren. SkePU Multi-GPU programming library

  • SkePUというマルチGPUのskeleton programing library. 話者はSkeep-youと発音。
  • 関数をマクロで定義する。 BINARY_FUNC(plus, double, a, b, return a + b;) みたいに。
  • 普通のスケルトン並列ライブラリ。新しいところはMulti-GPUサポート。
  • 実は時間を一番食うのはHost-GPU間のデータ転送。メモリ転送をlazyに実行することで隠蔽するよう頑張る。
  • 実例: ODEソルバ。手書きCUDAと比較して10%程度のオーバーヘッドで計算。
    www.ida.liu.se/~chrke/skepu
  • 質問: Non-uniform memory accessにどうやって対処するつもりか?
    本人は問題を把握しているようだが、回答がよく分からなかった。今回はGPUで扱いやすい問題をメインに扱うから問題ない?


K. Matsuzaki. Lessens from Implementing the BiCGStab Method with SkeTo Library

  • "Real application experience report".
  • Sparse matrixの形状が決まっている。高速な計算が可能か?
  • SkeTo はC++/MPIの普通のskeleton並列ライブラリ。
  • SkeToはC++のテンプレートを大活用してskeletonを融合する。ループ操作を纏めるとかそう言う感じ。
  • 知見: flexible data reallocation / shiftはライブラリ内でサポートしておくべき。
  • stencilで分解するとfusionが足りないので自力でoptimizationを色々やる必要がある。今回はmanual fusionしたけど本当はライブラリでやって欲しいよね
  • データのコピーオーバーヘッドが問題に。今回はsmart pointerを用いてコピーを節約するようにSkeToを改造


O. Lobachev. Estimating Parallel Performance, A Skeleton-Based Approach.

  • "Parallel penalty" の計測を考える。T(n)/p + A(n, p)
  • A(n, p)を計測して実際に掛かる時間を予測する
  • Amdahl's law に近いが単純に/pするだけじゃなくて、Divide & Conquerの時とかはコスト関数の和を真面目に考える。
  • どんな関数で補外するのが良いかも調べる。


BSP-WHY

  • Loop invariantとかを表示することでBSPのプログラムをverify.
  • 並列を直列実行でシミュレート。
  • 要はCPU1台でマルチタスクのプログラムを走らせたと思えば。
  • モデルがBSPだから確かに何とかなる気がする。
  • 並列をfor proc in 1..p の形のループにしてしまう。
  • loop variant / invariantをannotationとして入れる。
  • いろんな証明器に対応。あるinvariantが1つのプログラムで証明できなくても他の証明器で証明できるかが調べられる。
  • 質問: annotation必要なのはどーよ? Loop終了の判定とかは全自動で出来ないの?
  • 質問: ループの順番を変えても大丈夫であることはこの方法では証明できないのではないか?
  • 質問への回答は聞き取れず(French-Englishは非常に辛い。。。)


SymGrid-Par:

  • Computational Algebra (Mathematica etc.)のparallelization
  • socket経由で分散計算して回収したい。
  • 問題点: この並列はdynamic(コンパイル時にタスクサイズが決まらない)でかつ並列度がタスクごとに大きく異なる
  • Parallel Haskellバックボーン
  • 中身はよくあるskeleton並列
  • prefetch付きのidiomを導入。prefetchにより遅延を隠蔽するなど。


Parallel Greedy Graph Matching

  • Maximum cardinality matchingを考える。
  • Greedy algorithmをどう並列にするか? "find Best" "add edge" "remove edge" ... なんか並列化しづらそうですよ?
  • Karp-Sipser algorithmを実装。意外とどうにかなるものである。
  • Vertex based distribution (1D distribution) / Edge based distribution (2D distribution)
  • BSP based parallel modelling。BSPはうまく実装するとちゃんとロードバランシングできるらしい。。。
  • 確かに、待ち時間を調べてメッセージ交換すると出来るような気がする。
  • ユースケース紹介だが、得られた知見はmatching問題特有のもので今ひとつよく分からず。


Hybrid Bulk Sychronous Parallelism Library for Clustered SMP Architectures

  • BSP modelのライブラリ in C++ (BSML (gava:09) のObject-oriented versionC++)
  • C++ lambda support
  • BSP_SECTIONで開始。ま た マ ク ロ か !
  • BSPは(まぁ当然ですけど)OpenMPに比べて8倍ぐらいsync速度が遅いです
  • Hybrid BSP: 同じコードでMPI / OpenMP.
  • OpenMPはsyncのコストが問題に。False sharingが起きるとMPIの方が早いケースも。。。
  • 割と試してみたいと思う。が、C->C++以上の新奇性は?


全体感想:

  • 率直な外野からの感想からすると割とショボい。
  • 何がショボいかというと色々あるんだけれど、同じようなアプローチを同じようにみんなで実施して同じような問題を抱えているようにしか見えない。Eccentricな提案がない。
  • 計算のモデルが計算機に合わなくなってきている。今では計算そのものよりも通信やメモリ領域などがネックになりつつあるのに、そういう計算モデルを持ってきた人は皆無で、現在のHPCの人たちの問題意識などと著しく解離しているなーという気がする。かといってpost map-reduce型の計算を何か模索しているのかと思うとそうでもない。
  • つまり現実にも適合してなければ理論的に現実の先や現実にないマシンを見ているわけでもない。
  • 割とこの分野は熱的死に陥ってないか。今のやり方は過去(Flat parallelism; Map-Reduce; Calculation cost > memory transfer cost)に合わせているだけである。未来どころか現在にすら合っていない。
  • 新しい血が必要という感想。

posted by chun at 00:30| 日記

2010年07月19日

EC2 HPCを試す

EC2 HPCが出たので試してみました。結果から見ると

http://shuns.sblo.jp/article/29808872.html
http://shuns.sblo.jp/article/29809062.html
とかで書いていたEC2スケールしない問題は無事に解消されているようです。
ディスクが遅いという問題はあるものの、計算インテンシブなHPCであれば実機とほぼ同等のパフォーマンスが出るので、緊急に計算力が必要になった際にはかなり使えそうです。
posted by chun at 18:51| 日記

2010年07月11日

固有値本

oxy君の日記に倣って最近読んでいる本を紹介してみます。

Twitterでも何度つぶやいたのですが、The Matrix Eigenvalue Problem: GR and Krylov Subspace Methodsを最近読んでいます。非常に良く解説された、固有値計算について最新の研究を纏めた教科書です。但し、人を選びます。

本書では、いかにして行列を固有値計算に性質の良い形に変形していくかという点に絞り、QR法の同類(本書ではGR法と記述)と、Krylov部分空間法を解説します。説明は首尾一貫して基礎理論→実例の順に行われます。例えば3章ではeliminationの基本型をGRアルゴリズムとして紹介し、これでもかこれでもかと応用例(QR, LR, HR, SR)を示しています。

数学書として見ると、手間の掛かる(が重要でない)証明が演習問題に回されることで、全体の見通しが非常に良くなっています。演習問題は一歩一歩細かく証明のステップを示してくれるので、行間が空きすぎると言うことはありません。

私にとって収穫が特に大きかったのはproduct eigenvalue problemの部分で、ABCDEx=λFGHIJKxのような式をどう安定に解くか、という内容です。Product eigenvalue problemを紹介し、一般的な形式としてcyclic matrixに落とした後で、「特異値分解に特化した解法」としてdqdアルゴリズムを(再)紹介します。この一連の流れは非常に美しいです。私の頭の中で個々の別々のアルゴリズムとして記憶されていた固有値・特異値計算の数々の手法が繋がっていく過程が爽快でした。

欠点としては(M)RRRなどの比較的新しく、かつ重要な固有値計算方法が載っていないことが挙げられると思います。良くも悪くもこの本はQRの兄弟たちを基本としています。D&CもRRRも魔改造されたJacobi methodも載っていません。筆者は決してこれらを無視しているのではなく、はっきりと有効性を認めているので、せっかくだから纏めて欲しかった気もします。

本書は自分で固有値・特異値計算を実装する事を考えている、修士以上の学生さんや、意欲のある学部4年生などにお勧めできます。逆に、ライブラリを使うだけの場合はZ. BaiのTemplates for the Solution of Algebraic Eigenvalue Problems(Amazon
) の方がアルゴリズムの選択チャートがあるので、簡便だと思われます。
posted by chun at 23:57| 日記

2010年06月29日

2010年06月26日

All your fuel are belong to us - ICFP-PC'10 participation report

(Note: this entry contains spoilers for ICFP Programing Contest 2010) Continue...
posted by chun at 20:35| Comment(0) | 日記

2010年06月22日

ICFP Programming Contest 2010 終了速報

ブログ名を「四季記」にしたら良いんじゃないかと言われました。

チーム名「Pure Pure Code ++」でICFP-PCに参加していました。総勢6でした。結果としては、5位以内入賞と非常に良い成績を残せたと思います。(詳細な順位は私たちも分からず、ICFP学会中に発表されます)9割以上僕の成果じゃないのが頭の痛い点ですが。とりあえず速報として大会中・大会前後の名言集をあげておきます。

「ぴゅあぴゅあこーど…… いえ、なんでもないです。」
「手動パズルならまかせろ バリバリ」
「どういうことだキバヤシ」
「あと四つ葉バターとかあります」
「若者の人間離れ」
「そこちがう1」
「とけたああああああ!」
「固定資産税」
「無理ゲーと思っていた問題が運ゲーに変わった」
「点数がふえるよ やったね chunちゃん」
「とりあえず増えていくcarに対抗してcdrを出品すべき」
「こんなこともあろうかと取っておきました!(ぉ」
「最盛期のぴゅあぴゅあこーど++:
ご飯を食べている間に+200点」
「とりあえずfuelは昼食にならないっぽい」
「細かすぎて伝わらない」
「わたしです」
「よっし!……コラ画像が出来た」
http://twitter.com/wata_orz/statuses/16615142451 まったくどこのソルバーだ、酷い話だな」「けしからん話ですね」
「ご飯食べてコラ画像作ってたら400点上がった」
「まず0で割る」
「問題が焼けるのを待つか」
「やっぱり unsafePerformIO が悪いのかなぁ」
「リアルサマーウォーズ」
「すごい勢いで廃車にされていく」
「最盛期の(ry
リロードする間にsolvedが50個増えた」
「接待ゴルフ」
「ICFPCのジンバブエ化」
「今マシンがアツい!」
「なんかが解けた」
「車はすぐに焼けてしまう」
「ICFPにはルールがありませんが社会にはルールがあります」
「なぜ差が付いたのか……マシン、環境の違い」
「無限プチプチ」
「ヒューリスティック対ヒューリスティック」
「画面が真っ青です!」「画面は青かった」
「パスワードはtritではない」
「なるほど4時じゃねーの」
「5台も残しただと・・・?」

細かい話は、また後ほど。
posted by chun at 01:31| 日記