2013年08月15日

SMTソルバでプログラムを作る

ICFP programming contest 2013に参加していました(よくわかる解説)。チームの成績は戦略ミスなどもあって散々だったのですが、ちょっと変わったアプローチで問題に取り組んだと思うので、自分のチームのアプローチを紹介しておきます。リポジトリはこちら

続きを読む
posted by chun at 02:55| 日記

2011年12月19日

面白CS論文紹介

この記事は、今年読んだ面白CS論文紹介カレンダー( http://bit.ly/vKrdxq )6日目の参加記事です。CSの中でも、ちょっと数値系に偏った記事になります。

Quasi-Newton Methods for Markov Chain Monte Carlo


http://homepages.inf.ed.ac.uk/csutton/publications/hmcbfgs.pdf

これはなに?



メトロポリス法(ボルツマンサンプリング)はCSにいたら一度ぐらいは聞いたことがあるかとおもいます。TopCoderのマラソンマッチに出たことがある人にはこれを用いた焼き鈍し法がおなじみではないでしょうか。また、機械学習タスクを楽しまれる淑女紳士の皆さんには、メトロポリス法は非常になじみ深いものかと思います。メトロポリス法は、構造空間を広くサンプルし、かつ目的関数の値が充分に低い場所をまとめて拾ってくるには便利な方法です。

しかし、メトロポリス法は、対象が高次元だったり目的関数の異方性が強かったりする場合には、なかなか効率よく空間をサンプル出来ません。この論文で紹介するHMCBFGS法は、こうした問題に対処する新しいサンプラーを提唱しています。

アイディア



異方性が問題になるなら、異方性が消えるように空間をねじ曲げてスケールしてしまえばいいじゃないか……というのが答えになるわけですが、単純に目的関数をスケールして正しいサンプラーを組み立てることは非常に難しい作業です。著者はHamiltonian Monte Carloという力学系を用いたサンプラーの先行研究をまず紹介します。実は、統計力学では、質量をどんなに適当にいじっても、無限時間が経った後の系の確率密度は同じであることが保証されていますから、質量に異方性を入れてスケールすれば、異方性をうまく消しながら空間をサンプルすることが可能になります。あとは、良い質量の決め方を探すだけです。

出会い



この論文は、NIPS2011のaccepted papersを眺めていたときに出会いました。タイトルで一目惚れした論文です。

なんでそんなに気に入ったのか



一つには今の自分の研究が力学系だし良いサンプラーを必要としている、というのがあります。もう一つ、単純ながら置き換えの効かないメトロポリス法を倒せる可能性のある候補である、というのがあります。メトロポリス法が作られたのは実に1953年ですから、50年も生き延びている優秀なアルゴリズムなわけです。これに勝てるかもしれない、って聞くと、みなさんワクワクしませんか?

Fixed block compression boosting in FM-indexes


http://arxiv.org/pdf/1104.3810

これはなに?



FM-indexという、文字列を圧縮したまま検索したり、元の文を復元したりできる不思議なデータ構造があるのですが、そのきわめて簡単で且つ圧縮率の高いな実装方法を見つけたよ、という話です。FM-indexの実装においては、文字の出現頻度だけを見て圧縮するwavelet treeという高速で実装も単純な方法が知られています。しかし、この手法では文字の出現頻度しか見ないため、文章のなかでたとえば頻出単語が存在する場合、圧縮率がもっと伸ばせるのに……という事態が起こりえます。

アイディア



この論文では、まずFM-indexを構成する要素であるBurrows-Wheeler Transform(BWT)を適切にぶった切れば圧縮率が理論上界まで伸ばせることを示し、しかる後に適当にぶった切っても圧縮率が大して悪化しないことを示します。

中身については、PFI社の岡野原さんもちょっと触れていますのでご参考まで。
http://www.slideshare.net/pfi/succinct-data-structure-for-analyzing-document-collection

出会い



同じくSPIRE2011のaccepted papersを眺めていたときに見つけました。Juha Karkkainen, Gonzalo Navarro, Veli Makinen その他の各先生の著作はストーキング対象です。

なんでそんなに気に入ったのか



「やぁみんな。複雑な方法で今まで、k次経験エントロピーサイズまで圧縮する面倒な手法を実装してただろう? もうそんなことは必要ない。今日からは、BWTの文字列を、ただぶった切れば良いんだ(意訳)」って言われたら、そりゃ惚れますよ。

Accelerating nearest neighbor search on manycore systems


http://people.kyb.tuebingen.mpg.de/lcayton/papers.html

これはなに?



「点の集合が与えられたとき、その点に一番近い点を求めなさい。」はい、よくある最近点・最近点対問題です。この問題を解くのには、k-D treeなどといった木のデータ構造を作成するのが普通です。これは確かに効率は良いのですが、並列化向きでないという問題があります。

アイディア



点の中からランダムに、代表点を複数抽出します。代表点の近くにある点を、順番に決まった個数取り出し、最長距離を覚えておきます。この処理はきわめて容易に並列化できます。これをインデックスとしましょう。

クエリが来たら、代表点との距離をまず測り、最長距離を用いて枝狩りをして生き残った候補との距離を測ります。この処理もまた、きわめて容易に並列化できます。これで近い順に点を出力すれば終わりです。

出会い



この問題を解く、state-of-artな方法を探していたときに見つけました。

なんでそんなに気に入ったのか



原理単純、実装単純、それでいて理論的にも実際にも優秀な性能のためです。SIMD命令を手で加えて高速化したANNとの速度比較を実際に行ってみましたが、シングルコア・マルチコア共に本手法の方が高速だったので、惚れました。行列積さえ実装できれば良いのでGPGPUでも動かせます。また、手法が単純なため容易に拡張できる点も素晴らしいです。ちょっと考えれば代表点を階層的にしてvan Emde Boas tree作ったりとか、面白そうな遊びを思いつきますよね?



ちょっと連続系的な話に偏ってしまいました。次は @kmizu さん、よろしくお願いします。/h2
posted by chun at 22:50| 日記

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| 日記

2010年04月08日

KindleDX sucks-rocks

論文読みデバイスとしてKindle DXを購入しました。以下に「論文読みデバイスとして見た」sucks-rocksを並べておきます:

Sucks
・(物理的に)重い。片手で持ち続けると疲れる。
・(論理的に)重い。特に画面遷移が遅い。そのためこの22番ってどの文献……っていう見方が出来ない。
・UIはお粗末。ページ番号入力しか2ページ以上の遷移手段がない上、数字の入力はALTキー必須ってUIはどうよ!?
・タグを付けられるとか機能はあるんだけどUI的にない方がマシ。
・Documents/の下にフォルダを掘っても一覧表示は階層表示になってくれない。なのでpdf一杯入れると扱いが面倒に。
・高い。$500レベルはちょっといただけない。
・左側にnext/prevボタンがない。何を言っているのかわからねーかもしれないが使ってみると欲しくなる。
・ほとんど意味がない検索。

Rocks
・予想していたよりずっと解像度がよい。
・e-ink読みやすいです(^q^) 特に屋外。
・Wireless offで運用しておけば電池で困ることがまずない。というかこれとe-inkがなければノートPCで読んでる。
・USBからも充電できる。もちろんコンセントからも。

前から順番に読む分に於いては不便を感じることがないので、及第点かと思います。個人的にはASUS DR-900系列に期待しています。大いに。DR-950に開発キットが公開されるかどうかが目下最大の関心事です。
posted by chun at 10:49| 日記

2010年04月01日

そうだ京都行こう

というわけで京都に移りました。皆様本年度もよろしくお願いいたします。
posted by chun at 09:06| 日記

2010年01月10日

おめでとうございます>パズルの人

まぁこれで分かる人必要がある人だけ分かるでしょう(何
posted by chun at 00:02| 日記

2009年12月31日

2009年を振り返る

1月はいろいろとごたごたしていました。未だに出版できていない某研究の草稿を渡したりとか、oxy君からT. Taoの仕事を紹介されて読んだりしていた記憶があります。2月薬剤師国家試験の勉強とCell Challenge 2009でいっぱいいっぱいでした。毎日図書館に向かって電話帳を開き、一週間に1回cellの事実上アセンブラなコードを最適化するという健康で文化的な生活をしていました。3月Biophysical Society 53rd Annual meetingに出てきました。昔の研究内容の発表でしたが、結構マニアックな人が釣れて面白かったです。あと、D. E. Shaw Researchの桁違いっぷりが素晴らしかったです。その他試験本番、Cellチャレ結果発表などがありました。Cellの作り込みが甘いとか大それた事を発言したりとか。
4月は日記には書いていないですが奈良とか京都とかの先生を訪問してネタ出しをしてきました。この辺の研究アイディアは残念ながら未だに形になっていません。まぁ予算が付かないので仕方がないかと思います。5月はSACSISに行ってチームの呼び名で主催者を困らせたりしてきました。T社の方の発言にびっくり
6月は誰がなんと言おうとICFP-Cの月でした。結構良いところまで動く代物が出来たのですが、72時間のデスマではバグを取りきれず、悲惨な結果になってしまいました……。7月は代数関係の知識とか、信号処理とかの知識を貯め込んでいました。名前にMが付く数理系の研究者の方、是非アレの論文を出してください。このころとある理由から可積分系に興味を持ったので調べたりしています。
8月はICFP-Cの結果がわかってかなり凹んだりしていました。72時間でデスマなんて無理だよバーニィ! あと、研究との両立が完全に破綻を来したので、この月にPFIを退社しました。ブログで簡潔すぎる報告しかしなかったため、id:TAKESAKO氏に凄く勘違いされるという事態が発生しました。しかしデスマ自体がなかったとは言えないのが今日もPFIのみなさんは楽しく働いています!
9月は諸事情により東京を離れていたのと、論文の修正で忙しかったのであまり記録が残っていません。自然言語の生成を楽にする方法を誰か教えてください。10月は研究で新しいネタを少しずつ試したりとか、某m先生と密談を楽しんだりしたのですが、これもちょっと表に出せるネタが無かったりします。残念。
11月は事業仕分けの激震が走った月でした。結果的に科学技術予算はまんべんなくトータルで3%減額です。スパコンはよりgdgdな計画に置き換わりましたし、仕分けられていない事業もバーターで削減って泣いていいかなこれ。12月はついにD論を提出しました。後は審査だけなので綿密に準備をします!


皆様良いお年を! 来年もよろしくお願いします。
posted by chun at 20:14| 日記

2009年11月28日

仕分け雑感(2)

ポッポのしわけ! こうかは ばつぐんだ! 知り合いで有能な人が蜘蛛の子を散らすように日本を離れていくのが興味深いです。たった2週間なんだぜ、これ……。自分も興味深いとか言ってられる状況じゃなくなりつつありますが……。
  • 仕分けの問題点の1つは議論を置いて結果だけが一人歩きするところです。
  • 仕分けのもう一つの問題点は、専門性どころか合理性のかけらもない情緒的な議論で決定されることです。 例えば国立大の基盤経費。「天下りがあるから多数決で1/3削減」って、すいません天下りによって生じている無駄な人件費と出費はいくらで、どのようにすればこの日本でミスをしていない人をクビに出来るんでしょうか。 さらに言えば、「仕分け人の印象の多数決」のどこに合理性があるのかを小一時間問い詰めたいです。
  • その上で仕分けで評価できる点はいくつかあります。まず国民のガス抜きとしては非常に良く機能したと思います。次に、予算配分の透明性を形式的に高めた事は素晴らしい事です。特に、インターネット等で公開中継されたのは素晴らしいです。
  • なのになんで対象は全体の15%で、しかも継続的にやらないんですかね。しかも時間が金額に関わらず一定ですよね。グルーピングも謎ですよね。金額が一様になるように纏めているわけでもないですし。
  • スパコンですが、僕は継続を支持しません(復活するでしょうが)。でも、平木先生のIBM/Cray/Intelについての話は考慮に値すると思います(誰か1次ソース持ってません?)。今回のプロジェクトは研究開発ラインを止めないという目的を実は既に達成しているんでないかとごにょごにょ。
  • この件について某エラい先生が某学会で「他の学会も声明出してるから出そうぜ」とか言っててうんざりしました。このコピペじゃないんですから。
  • まぁ日本には流体系でほぼ独占状態のSX-9があるから、TOP500には決して出てこないだろうけど別にいいんじゃね? 的な思いもあったり。
  • 濱田先生の成果があるからスパコン要らないとか言う人は、あやまれ! アルゴリズムもコーディングも超頑張った濱田先生にあやまれ! 成果が正しく認識されないというのは悲しいことです。
  • 問題は若手と基盤、特別研究の削減です。特に特別研究・基盤の1/3はかなりまずいです。運営が立ちゆかない研究室が多数発生し、「運用でカバー」をする研究室が出るでしょう。で、辻褄合わせに失敗して不祥事になって何人か教授の首が飛ぶんじゃないかな、と予言。
  • ノーベル賞受賞者による緊急なんちゃらですが、これって図式としては権威主義で対抗しようとしてるんですよね。あまり嬉しくありません。いや、先生方がアクションを起こしてくれたことそのものはとても嬉しいのですが。ついでに、討論はgdgd杉でした。「マスコミvs研究者」「官僚vs研究者」という大変嬉しくない図式を作っていましたね。敵を作る意味が分かりません。
  • というか野依先生とそれ以外の先生の絶妙な温度差が面白かったです。野依先生「スパコン復活!」と森先生「小さく広く配分してイノベーションの芽を」。私は森先生派で。あと野依先生、お忙しいのは分かるのですが、仕分けの議論の展開をちゃんと聞いた方が良いと思います。
posted by chun at 13:09| 日記

2009年11月18日

仕分け雑感

身の回りで激震が続いております。色々言いたいことがあるのですが、以下、3点だけ。

  • この手の議論の度に「研究の重要性を小学生にも分かるように伝えれなきゃダメだ」とか言う人がいます。さて、理系の研究者の皆様は線型代数の有用性を否定することは無いと思いますが、この現代の基盤となった数学の重要性は、どうやったら小学生に伝えられるでしょうか。それも、5分や10分といった短い時間で。これ、ここ4日間ずっと考えて居るんですが、未だに良い説明を思いつきません。
  • 若手研究予算がどうもニート生活支援(しかも更正支援ではない)と思われているふしがあります。というか、3-13の議事録読むとよく分かるんですが、学振あたりはどうもセーフティネットと見なされているようです。
  • 各所で言われているスパコンですが、あの答弁では正直仕方がないと思います。もちろん、1時間、一人だけの答弁で全額というのは非常に拙速であるという点には同意しますが。このまま共同計算機センターが存在しなくなると色々苦しいでしょうから、形を変えて(安いヤツを)作って欲しいとは思います。

とりあえず、文科省のほうでも意見を募集していますので、こちらにメールを出すことにします。

posted by chun at 04:56| 日記

2009年10月20日

perfコマンドを試してみる(3) annotateとperformance counterの実装

さて、perfコマンドの能力はこれだけではありません。perf annotateによって、プログラムの中のどの行が時間を食っているかが一目で分かるようになります。

% perf annotate
------------------------------------------------
Percent | Source code & Disassembly of saa
------------------------------------------------
:
:
:
: Disassembly of section .text:
:
: 0000000000407710 <sais_main>:
:
: /* find the suffix array SA of T[0..n-1] in {0..k-1}^n
: use a working space (excluding T and SA) of at most 2n+O(1) for a constant alphabet */
: static
: int
: sais_main(const unsigned char *T, int *SA, int fs, int n, int k, int cs, int isbwt) {
0.00 : 407710: 41 57 push %r15
0.00 : 407712: 41 56 push %r14
0.00 : 407714: 41 89 ce mov %ecx,%r14d
0.00 : 407717: 41 55 push %r13
...
: for(j = p + 1; (j < n) && (c0 == (c1 = chr(j))); ++j) { }
0.23 : 407942: 41 8d 40 01 lea 0x1(%r8),%eax
5.08 : 407946: 41 39 c6 cmp %eax,%r14d
0.07 : 407949: 7e 3b jle 407986
:
...
: for(i = 0, m = 0; i < n; ++i) {
8.29 : 4079a4: 4c 39 cf cmp %r9,%rdi
0.04 : 4079a7: 0f 85 73 ff ff ff jne 407920
0.00 : 4079ad: 44 89 54 24 18 mov %r10d,0x18(%rsp)
...

ちなみに、対応するコンソールを使えば色つきで表示されます。(例えば5.08%は赤色で、他の割合は青色で表示され、どこが最も重いのか一目瞭然です。)行単位でボトルネックを探すにはperf annotate -lが便利です。


Sorted summary for file /home/shun/work/saa/saa
----------------------------------------------

8.29 /home/shun/work/saa/sais/sais.c:198
7.23 /home/shun/work/saa/sais/sais.c:261
7.08 /home/shun/work/saa/sais/sais.c:261
6.52 /home/shun/work/saa/sais/sais.c:259
5.38 /home/shun/work/saa/sais/sais.c:242
5.08 /home/shun/work/saa/sais/sais.c:201
2.72 /home/shun/work/saa/sais/sais.c:180
2.70 /home/shun/work/saa/sais/sais.c:180
...

ボトルネックが一目瞭然です。198行目を書き換えればちょっと速くなるかなーなどと分かるわけです。これで速度が増えるよ やったねタエちゃん!

注意点とperfの実装



さて、よくよく見てみますと8.29%の処理時間を取っているのはレジスタ間cmp命令です。レジスタ同士の比較でなんでこんなに時間を取っているんでしょう? それを説明するためにはperfの実装を知る必要があります。

perfはハードウェアの持つパフォーマンスカウンタを利用します。パフォーマンスカウンタはある一定のイベントが起きるごとに加算され、指定された回数のイベントが起きるごとに割り込みを掛けます。perf recordでは、この割り込みを掛けたときのIPレジスタの値を保存することができます(perfシステムコールにPERF_SAMPLE_IPを指定)。perf reportではこの値を読み出し、対応するアドレスを逆算して行番号などに割り付けます。

さて、我々が現在使っているCPUは、大抵がアウトオブオーダー実行です。CPU内で発行されるμOPsは命令の字面とは異なる長さ、規模、順序で発行されます。そのため、実際の割り込みが起きた時点でのIPカウンタは必ずしも実際のCPU命令の実行箇所を意味しません。IPカウンタの値なんて飾りです。偉い人にはそれがわからんのです。ですので、この処理時間は「このへんにボトルネック」という意味でしかないことを理解してプロファイルを取ると良いと思います。Atom CPUならまた話が変わるかもね!

このほかperfはpidを指定してattachしたり、perf statで偏差を含めてカウントしたり、その他今回紹介しなかった様々な機能を持ちます。皆さん是非遊んでみてください。

どうでもいいこと



今使っているブログシステムは<を入力するのに&lt;と入力しなければならず、またタグも全部手打ちと大変使いづらいです。
近いうちにはてなあたりに引っ越すかもしれません。はてな記法万歳。
posted by chun at 23:37| 日記

perfコマンドを試してみる(2) 関数ごとのオーバーヘッド

perfコマンドでおそらく一番良く使われることになるのはこれでは無いかと思います。
perf recordコマンドでコマンド実行の際のデータを収集し、

% perf record -- ./saa build chr22.txt
[ perf record: Captured and wrote 20.376 MB perf.data (~890258 samples) ]

perf reportコマンドで結果を出力します。

% perf report
# Samples: 386487
#
# Overhead Command Shared Object Symbol
# ........ ....... ......................... ......
#
56.26% saa ./saa [.] induceSA
39.16% saa ./saa [.] sais_main
0.57% saa ./saa [.] suffix_array::build_buffer(std::vector<unsigned c
0.54% saa [kernel] [k] copy_user_generic_string
0.29% saa [kernel] [k] clear_page_c
0.18% saa ./saa [.] getBuckets
0.11% saa /lib/libc-2.10.1.so [.] memset
...


この例ではSA-ISを使って遊んでいたので、saisの関数が表示されれています。どこで時間を使っているかが一目瞭然ですね。

call graph付きでプロファイルを取ることもできます。この場合、-g付きでrecordを走らせ、reportも-g付きで実行します。ただ、この場合ユーザープログラムの側のcall graphは見えません。理由はちょっと謎なので後で調べてみようと思います。

% rm perf.data
% perf record -g -- ./saa build chr22.txt
% perf report -g
55.16% saa ./saa [.] induceSA

38.59% saa ./saa [.] sais_main

0.59% saa [kernel] [k] copy_user_generic_string
|
|--85.17%-- generic_perform_write
| generic_file_buffered_write
| xfs_write [xfs]
| xfs_file_aio_write [xfs]
...


しかし、perfはただのCPU時間プロファイラではありません。perf listをするとperfで取れるパフォーマンスカウンタの一覧が分かります。cache miss, branch miss, TLB miss, page faults, kernel page allocationなども取ることができます。(回数ではなく、オーバーヘッドを計測するものと思われます。この辺はprefの実装にも関係してくるのですが、後ほど時間があれば調べて書きたいです)
% perf record -e branch-misses -- ...
% perf report


常日頃からCPUに必要なのは良いプロファイラだと言っている(嘘)私ですが、perfは素晴らしいです。このご時世にC/C++をわざわざ使っているようなプログラマはこの恩恵が分かるはずです。みなさん進んで2.6.31のヒトバシラーになりましょう!!!1121!

(次回に続く)

おまけ
前回のやり方だとmanが入らないので、追加で
sudo aptitude install asciidoc
make doc && make install-doc

しておくと良いです。
posted by chun at 06:09| 日記

2009年10月19日

perfコマンドを試してみる(1)

Ubuntu 9.10 (Karmic)はLinux kernel 2.6.31が入れられています。2.6.29-2.6.31はいろいろと面白い変更が入っているのですが、その一つにperformance counterの導入があります。これを使って遊んでみます。

sudo aptitude install linux-source-2.6.31 libelf-dev binutils-dev
tar xjf /usr/src/linux-source-2.6.31.tar.bz2
cd linux-source-2.6.31/tools/perf
make && make install

すると、勝手に$HOME/binにperfコマンドをインストールしてくれます。インストールが終わったら

sudo ~/bin/perf top

とかすると、ちゃんとkernel 2.6.31以降が入っていればperformance counterが動く様子を見ることが出来ます。

(次回に続く)
posted by chun at 10:22| 日記