Quasi-Newton Methods for Markov Chain Monte Carlo

これはなに？

アイディア

出会い

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

Fixed block compression boosting in FM-indexes

これはなに？

アイディア

出会い

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

Accelerating nearest neighbor search on manycore systems

これはなに？

アイディア

出会い

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

// chatは投稿者名とテキストからなる
db /chat : {name: string; text: string}

  recents = Db.history(@/chat, 0, -num_print)

update_chat() = 
  // 最新の20件を取得
  recents = Db.history(@/chat, 0, -num_print)
  // 発言をxhtmlに変換
  lines = List.map((x -> <div class="line">
                           <div class="user">{x.name}:</div>
                           <div class="text">{x.text}</div>
                         </div>), recents)
  // 表示！
  Dom.transform([#chat <- lines])

// chatは投稿者名とテキストからなる
db /chat : {name: string; text: string}

num_print = 20

update_chat() = 
  // 最新の20件を取得
  recents = Db.history(@/chat, 0, -num_print)
  // 発言をxhtmlに変換
  lines = List.map((x -> <div class="line">
                           <div class="user">{x.name}:</div>
                           <div class="text">{x.text}</div>
                         </div>), recents)
  // 表示！
  Dom.transform([#chat <- lines])

submit_chat() = (
  name = Dom.get_value(#name)
  text = Dom.get_value(#text)
  // textが空でなければ発言
  do (
    if text != "" then
      do /chat <- {~name; ~text}
      Dom.clear_value(#text))
  // textの中身にかかわらず更新はする
  update_chat()
)

show_page() =
  <div>
    <input id=#name />
    <input id=#text onnewline={_ -> submit_chat()}/>
    <button type="button" onclick={_ -> submit_chat()}>投稿・更新</>
  </>
  <div id=#chat onready={_ -> update_chat()}></>

server = Server.one_page_bundle("Chat",
  [@static_resource_directory("resources")],
  ["resources/css.css"], show_page)

server = 
  Server.one_page_bundle("Hello",
    [@static_resource_directory("resources")],
    ["resources/css.css"], hello)

/*
  resources/css.css
  */
body {
    background-color: #000000;
    color: #FFFFFF;
}

p {
    text-align: center;
    font-size: 32pt;
}

database counter = @local("./hogehoge")

  result = Db.transaction(counter, atomic_incr);

  match result with
    | { none } -> incr_count() // トランザクションをやり直す
    | { some = result } -> result

database counter = @local("./counter") // DBに名前を付ける
db /counter/cnt : int // DBの"/counter/cnt"はint型

incr_count() = 
(
  result = Db.transaction(counter, atomic_incr);
  match result with
    | { none } -> incr_count() // トランザクションをやり直す
    | { some = result } -> result
)

atomic_incr() =
(
  c = /counter/cnt;
  do /counter/cnt <- c + 1;
  c + 1
)

hello() = 
  <p>
    あなたは{incr_count()}番目のお客様です。
  </>

server = 
  Server.one_page_server("Hello", -> hello())

db /counter : int

incr_count() = (
  c = /counter
  do /counter <- c + 1;
  c
)

hello() = 
  <p>
    あなたは{incr_count()}番目のお客様です。
  </>

server = 
  Server.one_page_server("Hello", -> hello())

// hello.opa
hello() = 
  <h1>
    Hello, World!
  </>

server = 
  Server.one_page_server("Hello", -> hello())

$ opa hello.opa
$ ./hello.exe

• Hello, OPA
• Hello, counter
• Hello, transaction
• Hello, CSS
• Hello, BBS

お値段と職業研究者の方への留意点

性能諸元

AWS(Amazon Web Services)アカウント準備

HPCインスタンスセットアップ - StarClusterの導入

% sudo aptitude install python-setuptools python-dev

% su -
% yum install python-setuptools-devel

% wget http://github.com/jtriley/StarCluster/tarball/master -O starcluster.tar.gz
% tar xzf starcluster.tar.gz
% cd jtriley-StarCluster-*
% python setup.py build
% sudo python setup.py install

% starcluster --help
StarCluster - (http://web.mit.edu/starcluster) (v. 0.9999)
Software Tools for Academics and Researchers (STAR)
Please submit bug reports to starcluster@mit.edu

Usage: StarCluster Command Line Interface:

starcluster [global-opts] action [action-opts] [ ...]

Available Commands:
-------------------
NOTE: Pass --help to any command for a list of its options and detailed usage information
...

HPCインスタンスセットアップ - StarClusterの設定

% starcluster help
StarCluster - (http://web.mit.edu/starcluster) (v. 0.9999)
Software Tools for Academics and Researchers (STAR)
Please submit bug reports to starcluster@mit.edu

cli.py:92 - ERROR - config file /home/shun/.starcluster/config does not exist

Options:
--------
[1] Show the StarCluster config template
[2] Write config template to /home/shun/.starcluster/config
[q] Quit

Please enter your selection: 2

>>> Config template written to /home/shun/.starcluster/config. Please customize this file.

[aws info]
# ↓この先で説明するアカウントID・秘密ID・ユーザーIDで置き換える
AWS_ACCESS_KEY_ID = ABCDEFGHIJKL123456
AWS_SECRET_ACCESS_KEY = foobarhogemogehage
AWS_USER_ID= 0000-0000-0000

[key gsg-keypair]
# ↓このファイルは後ほど作成する。ディレクトリを自分の$HOMEに修正するのを忘れずに。
KEY_LOCATION=/home/shun/.ssh/id_rsa-gsg-keypair

[cluster smallcluster]
KEYNAME = gsg-keypair

# ↓クラスタの台数。最初は1台から、追加していくことも可能。1台あたりXeon 5570 * 2 socket = 8 CPU Cores.
CLUSTER_SIZE = 1

# ↓ノードに入れるディスクイメージの識別子。この通りの番号で指定する。一覧には無いので注意。
NODE_IMAGE_ID = ami-12b6477b
# ↓GPUを利用したい場合はcg1.4xlargeとする。
NODE_INSTANCE_TYPE = cc1.4xlarge

% starcluster createkey -o ~/.ssh/id_rsa-gsg-keypair geg-keypair

% starcluster start small-cluster
StarCluster - (http://web.mit.edu/starcluster) (v. 0.9999)
Software Tools for Academics and Researchers (STAR)
Please submit bug reports to starcluster@mit.edu

>>> Using default cluster template: smallcluster
>>> Validating cluster template settings...
>>> Cluster template settings are valid
>>> Starting cluster...
>>> Launching a 1-node cluster...
...
>>> Starting cluster took 5.811 mins

プログラムの実行と、インスタンスの終了

% starcluster sshmaster smallcluster
...
The authenticity of host 'ec2-000-000-000-000.compute-1.amazonaws.com (000.000.000.000)' can't be established.
RSA key fingerprint is 00:00:00:00:00:00:...:00.
Are you sure you want to continue connecting (yes/no)? yes
..
[root@master ~]#

[root@master ~]# su - sgeadmin
[sgeadmin@master]~% 

% cat foo.sh
#!/bin/bash
/usr/lib64/openmpi/1.4-gcc/bin/mpirun -np 8 ./a.out
% qsub -pe orte 8 foo.sh

% starcluster stop smallcluster

% starcluster start -x smallcluster

% starcluster terminate smallcluster

注意点・TIPSなど

open64-4.2.3-0/bin/openf90 foo.f90 `mpif90 -showme:compile` `mpif90 -showme:link`

ベンチマークなど

GROMACS 4.5.4

NAMD-2.8b1-thread/TCP

llcbench

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

• 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で扱いやすい問題をメインに扱うから問題ない？
  

• "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を改造
  

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

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

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

• 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問題特有のもので今ひとつよく分からず。
  

• 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)に合わせているだけである。未来どころか現在にすら合っていない。
  
• 新しい血が必要という感想。