You can read this blog in any language using google translate as follows:

Goto http://translate.google.com/
Paste URL in the box and select "Japanese for From Language" and "To Language". Then click "Translate".

English translated pages are here:
http://bit.ly/xPuXoy

你可以閱讀這個博客,在任何使用“Google”的語言翻譯

本ブログのアクセス統計: 60万アクセスを達成しました。ご訪問ありがとうございました。

60万アクセスまでの経過

2009年12月に始めた本blog。2011年7月ごろに10万アクセスを達成し、2011年12月13日には15万アクセスを達成。
その後、私も更新しておらず、アクセスは少し減りましたが、3月1日には18万アクセス。2012/4/18に20万アクセス、2012/8/21に25万アクセス、2013/1/18に30万アクセス、2013/12/17に40万アクセスを達成しました。しばらく見ていなかったら、2015/5/1に50万2584アクセスになっていました。またまた、しばらく更新しないうちに、2017/6/11に60万7197アクセスになっていました。久しぶりに更新します。

2015年10月13日火曜日

国際学会 SOSPに行ってきた

米国シリコンバレーの南,ラッコやクジラの来訪で有名なモントレー水族館があるモントレーで2015/10/3(日)-10/7(水)に渡り開催された,ACM Symposium on Operating Systems Principles (略してSOSP)に行ってきた.

SOSPとは)

隔年で開催されている国際会議で,タイトルどおり,OSやソフトウェアシステムに関する国際学会では世界トップクラスの学会である.

http://sigops.org/sosp/sosp15/archive/index.html に学会のProceedingsがある.学会開催時に学会委員会が説明したのが以下の写真.ここにあるように,181件の投稿を以下の過程で絞り込んで30件のみが発表された.
  1. 第一の絞込
    • R1: 各投稿論文を,Program Committe(会議委員会)メンバから選んだ3人の専門家が査読
    • R2: 50%の論文が,3人の追加査読者による査読を受ける
    • R3: 幾つかの論文は,さらに委員会以外の外部の専門家による査読を受ける
  2. 全Program Committee を含めて,オンラインで2週間にわたり議論
  3. 78の論文が,Google社で開催された,対面審査(面接みたいなものか...)になる
  4. 30件の論文が採択され,これが2日半に渡り公演された.各論文の持ち時間は30分.質疑が5分ほどあるので,発表時間は25分程度.
これが1年おきに開催される.ただし,開催されない年には,OSDI (USENIX Symposium on Operating Systems Design and Implementation たとえば2014年のは https://www.usenix.org/conference/osdi14 )という別な学会が隔年で開催されるので,研究者はそちらに投稿している.
学会の開催宣言のときに,SOSP Program Committeeより説明された,審査基準
    本会場の様子
    これの後ろに,同じくらいの列のテーブルが有り,1000人は入れそう.
    論文を30件に絞ってあるので,一つの会場のみのシングルトラック
SOSPの良い所)
  1. シングルセッションなので,すべて聴ける
  2. 時間厳守で行われ,3件の発表が1時間半で行われた後,30分の休憩,ネットワーキング時間がある
  3. 発表のあとは2-3件しか質問ができないが,初日と2日目のセッションのあと夕方ににわけて1時間15分のポスターセッションがある.ここでは,全発表者と,惜しくも漏れた論文のポスターが発表者から説明されるので,じっくりと質問ができる.最終日は半日だが,この分のポスターセッションは二日目に終わっている.発表前にポスターがあるのは,若干可哀想ではある.
  4. 最終論文(カメラレディ)は,学会のひと月半前に締め切られる.これが学会開始の2-3週間まえからダウンロード可能になり,事前に勉強しておける.したがって,発表者も,「残りは,論文を読んでください」とスッキリした発表にまとめている.
History Day)
今年は,SOSP 25回,50周年にあたるということで,特別にHistory Dayというのが,会議まえの日曜のworkshopのときに開催されたので,これを聴講した.

http://www.ssrc.ucsc.edu/sosp15/workshops/HistoryDay/ がリンク.プログラムのscreen shotを以下に引用する.

公演したのは70歳以上の教授たちが多く,コンピュータの黎明期に活躍した人たち.チューリング賞受賞者(本稿末尾で解説)の以下の方も来ていた.
  1. Butler W. Lampson (71歳): 日本語wikipedia: http://bit.ly/1PbV7z2 : Xerox Alto研究所の設立メンバで,世界最初のパソコンAltoの開発,レーザプリンタ,2 phase commit protocol, 世界初のWYSIWYG ワープロ,Ethernet,Euclidなどのプログラム言語の開発
  2. Barbara Liskov (75歳): 日本語wikipedia: http://bit.ly/1PbVwRW : 1968年、スタンフォード大学でアメリカ合衆国で女性として初の計算機科学の博士号を取得.オペレーティングシステム Venus の開発 - 小型低コストの対話型システム,CLU言語の設計と実装 - 世界初のデータ抽象化機能をサポートしたプログラミング言語(1970年代)など
チューリング賞受賞者でなくても,著名な活躍をした学者が公演をした.
  1. Jack Dennis: 英語wikipedia: http://bit.ly/1QZ8aBs : 現在のwindows, Mac OS-X, スマホのAndroid, iOSの骨格として使われている,UnixやLinuxの原型になった,MITのMulticsプロジェクトの立案者
  2. Peter J. Denning: 73歳:  英語wikipedia: http://bit.ly/1PbWv4N : 仮想メモリ(Virtual Memory)の発案者,OSに関する代表的な教科書: Operating system principles の執筆者
また,
  1. Berkeley RISCの考案者: David Pattersonは,CPUとRISCの歴史.そして今の彼の提案RISC-Vを語った
  2. GoogleのJeff Deanは,DataCenterの要素技術の発展史を語り,主要な論文 GFS, Cluster Scheduling System, MapReduceを語り,今後の動向として,CPU/GPU/FPGA/専用エンジンが混在したヘテロコンピューティングのシステム論,データセンタのサービスの共通化のための抽象化の重要性を語った.
MITのCSAIL ( MIT Computer Science and Artificial Intelligence Laboratory  https://www.csail.mit.edu/) も多かった.Liskovや,Dennisらである.

印象に残ったコメントは,以下
  1. 物理屋に「現代物理を作った4つの重要な仕事」と聞くと,スッキリした答えが帰ってくる.計算機屋に聞くと,たくさんありすぎて答えが決まらない.
  2. システムを目的にあわせて作りこんで,それからTheoryが追っかけて行く
  3. 計算機の着目点は,1950年は規模(scale)と,若干遅れて速度(speed),1960年からはそれに透明性(transparency, 互換性やプログラム容易性を含む概念),1980年から堅牢性(robustness)がテーマになっている.
  4. OSをscalabilityを考えて書き直す時期だ.もっとParallelism(並列処理)を研究すべきだ
他にもあるので,メモをみておいおい追記したい.Stanfordから参加した,PhD学生たちも,このHistory Dayのセッションのプレゼンは為になったといっていた.

日本ではこういうまとめをすることがないので,システムが作れないのではなかろうか..

今年は,データベースTransactionが特異的に多かった)
今年は,分散ストレージ, Key Value Store (KVS,ケイ・ブイ・エス),とかNoSQL に,RDB(Relational Database)のSQL(米国では,エス・キュー・エルと呼ぶ人よりも,シーコールと発音する人が多い)が持つ,Transaction (ACID特性: http://bit.ly/1Pc5jaL )を入れるという発表が特異的に多かった.2セッションと2件,つまり全30件中8件の発表がこれにあたり,ポスターも入れると10件近くあったように思う.査読委員であるProf. Johnに聞いても,「故意に選んだわけではなく.良い論文を選択したらこうなった.非常に特異な現象だ.」といっていた.

Transactionに関する発表は,Stanford大のProf. JohnのRAMCloudチームからも発表したが,それぞれ特徴がある.
  1. Stanford大から: Linearizability (逐次化可能性) を利用して,Exactly Once(ノードが壊れてもパケットが落ちても,アプリが吹っ飛んで)結果,再実行しても,同じ処理であることを判定して,絶対に一度しか実行しない.従来,readや単純writeはIdempotent (べき項性)といわれ,何度実行しても同じ結果になるといわれていたが,これは,1つのプログラムが実行されている場合であり,並列に複数のプログラムがデータをアクセスするケースでは,writeの再実行があるので,普通に実装しても結果のLinearizabilityは保証されない.ほかにもLinearizabilityに関する言及はいくつかあり,ポスターセッションでも定義と理解について議論がされていた.
  2. Yesquel: 2009年にSinfoniaというTransactionを導入したKVSを開発した業界の有名人 Marcus の発表.当時HP, その後Microsoft Researchに転職し,さらに今回はVMware Researchに転職している.有名人が各所を回って技術を広めるつつ,本人もスキルアップしていく流動性こそ,Silicon Valleyの強さの源泉か.. 
    NoSQLはシステム定義ではなく,分散でスケーラブルの代償にSQLではなくなった,なので,SQLを復活させたという発表.システム名称もそれにちなんで,No+SQLではなく,YES+SQLというダジャレで,Yesquel (エスクルと発音していた)と命名していた.アルゴリズムや実装についての詳しい説明は省かれていたが,割りと標準的なTransactionの実装手法である,Multi Versioningを使っていた.
  3. その他,PAXOSを使ったTransactionの実装,Hardware Transaction Memory (Intel Haswell以降のTSX拡張でとりあえず代用)+RDMAを使った手法,sharding (グループわけ)による手法.等,皆違うアプローチをしていた.
Marcusの発表から,現在実用になっているNoSQLの機能比較,赤いところがSQLにはあるがNoSQLにない機能


良かった発表から)
 最終日のBigDataセッションにあった,以下の発表が素晴らしかったので引用する.

Chaos: Scale-out Graph Processing from Secondary Storage
Amitabha Roy (Intel), Laurent Bindschaedler, Jasmina Malicevic, Willy Zwaenepoel (EPFL)

発表者は2人めの著者であるEPFLのLaurent Bindschaedler 結構若いのでポスドクかも.EPFLはスイス連邦工科大学ローザンヌ校 http://bit.ly/1VFrAlk  である.

 発表は,質問時間を十分残して,終わり大変分かりやすかった.隣りにいた,History Day公演者MIT名誉教授のJack Dennisも,スクリーンを凝視して話を聞き入っており,公演後盛大に拍手していた.

 終わったあと時間切れで打ち切られるまで,Microsoft researchから賞賛とコメント,Google, MIT, ハーバード大と他1件の計5件の質疑があった.
 発表の完成度が大変高かったのと,前日のポスターである程度議論を済ましていたのか,内容についての細かい質問はなく,質問もレベルが高かった.

気づいた点)
  1. 発表の旨さと道具) 最近,パワポは使うなとか短絡的な記事もあるが,パワポがダメなわけでなく,話す内容と,プレゼンのうまさと,そういうものなのだろう.省くところは省き,必要なところに時間を割く.
  2. 人格と気配り)著者が的確に質問に答えると,質問者はこういった論文がある,手法がある,これはやったほうが良い...などと次に繋がる提案をして,著者も丁寧に感謝を伝えていた.
    1. Stanford大でのアドバイザ,Prof. Johnも,論文や発表資料では,聞き手に対する配慮,聞き手の理解を助ける努力が必要である.といっている.何かものを作って終わりならよいが,普通は,その手法の説明,得た知見の共有ができてこそ,良い研究になる.コミュニケーション能力に欠けていては,一流の研究者にはなれないのだろう.
  3. 賞とは)そんな発表なのに,全30件の発表に対して3件選ばれたBest Paperからは漏れていた.論文選考とポイントが違うかもしれないが,賞というものはそれぐらいの基準なのかもしれない.
内容とポイント)
 質疑込で30分の持ち時間なので30枚超えのスライドがあったと思うが,学会側がビデオを撮影していたので,全体像はそれに譲る.ざっと以下に内容を説明する.

冒頭スライド
 発表者は,2nd authorのEPFL (スイス連邦工科大学ローザンヌ校:  http://bit.ly/1VFrAlk )のポスドク? 割りと若い

 世の中では,今後,最大8T edgeぐらいのグラフ探索が必要になる.Memory, SSD, HDDを組み合わせて,32台のサーバ程度でこれを実現する.

使う技術は4つ

どれも何ら新しくなく過去の論文発表の組み合わせ.

これらを使いランダマイゼーションをうまく活用した(先のスライド).過去の最高の研究成果を調べて,それを修正しつつ,不足分を補っているのだが,それを,「自分の研究は何ら新しくない」と言い切るところが余裕.

とはいっても,巨大なグラフを効率的に格納するデータ形式,SSD, HDDへの格納方式,並列処理をさせるための負荷分散方式と,さらに性能を落とさないためのwork stealingなど,徹底的に工夫をしている.


規模的にいうと スパコンのGraph500 (http://bit.ly/1VFncmw)の世界5位ぐらいの規模のグラフ探索を圧倒的に小さい計算機(Nodesがサーバ数)で実現できた

Graph500のサイトにいくと処理速度(GTEPS - Giga Edge Traverse per Second) がでている.日本の京速計算機(K-Computer ) はGTEPSでは世界一.


Chaosのスライドでは,性能が省かれていたのでGraph500のどこに来るのかexcelで計算してみると以下のようになる.sizeのlogとsizeのT Edgeの関係がよくわからないのだが,上記の発表にある数値が正しいとして,Chaosでの値を入れた.

ChaosとGraph500の関係,特に計算速度,処理時間

 流石に32サーバしかないうえに,データをHDDにおき,さらにSSDにcacheして,全部で1ラックにおさめているので,8T edgeのグラフのトラバースが104時間かかって圧倒的に遅い.(ただし,グラフデータの格納形式と配置を工夫し,HDDとネットワークのバンド幅を最大活用しつつ負荷バランスもとるところがポイント)

 ただし,仮に京速で32T Edgeのグラフを1.4 秒で処理できても,実はグラフを転送する時間のほうが圧倒的にかかるように思う.104時間は遅すぎるかもしれないが,数時間ぐらいの速度が妥当なのかもしれない.円周率の計算がスパコンからHDD利用の個人パソコンに移ったように,手法の進化でグラフ探索もよりコストの安い方法に移っていくかもしれない.

チューリング賞) 
日本人はまだ一人も受賞していない.

http://bit.ly/1OfkeiE にあるように,グーグルがスポンサーになって,チューリング賞の賞金が1億円になったらしい.そして,今年発表された2014年のチューリング賞はDatabaseのMicheal Stonebracker (現MIT教授)が受賞した.
StonebrakerはPostgres で儲け,VoltDB社を創業して傭けてているから1億円を貰ってもさほど嬉しくないかもしれないが...

昨年の受賞者,Lamportは,学会投稿などで広く使われるLaTeXの開発者で,かつ,Google, Yahoo等,Datacenterで,堅牢なシステムを構築するための分散アルゴリズム PAXOS (多数決を取って,コンセンサスを取る)を提案し,数学的に証明した人.

History Dayよもやま)
 冗談交じりで,面白おかしく昔話をしたが,タイムキーパは大御所だといっても容赦はなく,皆,時間を気にして,持ち時間の30分以内で公演していた.というか,時間が守れないようでは,一流の研究者ではないのだろう..

公演ではIBM 360/370 を産んだシステム設計の歴史とか反省が語られたと同時に,今の技術,そして将来への期待なども語られた.

 もちろん自分の専門分野も語ったが,あくまで,その研究分野での周りの動きの中での,自分の研究として語っていた.プロは彼らの業績を知っているので自慢する必要はない.
 「自分はすごいことをやった」とか,「すごい友達がいる」とか,そういう自慢で「キャーキャー」いってくれるのは,あくまで素人なのであって,タレントとかメディアとか大衆商売(つまりタレント学者)ならいざしらず,学者がそんなに世俗化してしまうようでは残念に思う.


blog comments powered by Disqus