gnuplotでeps
12 年前
2009年5月30日土曜日
2009年5月28日木曜日
新たなハードウェアを活用した研究の価値はどこに？
ソフトウェア分野において、未来永劫続くであろう研究テーマは、新たなハードウェアを活用したソフトウェアの研究であろう。 昨今、GPU, Cell やSSD を用いた研究が流行っているが、この種の研究の価値はどこにあるのでしょうか？
一つ冷静に考えないといけないことがあります。「単にそのハードウェア上に実装した（ポーティングとも言える）」では駄目。なぜなら、そこで得られた効果はそのハードウェアの賜物であるから。
研究とは、そこに世の中にとって役に立つような技術的な新発見、知見があって始めて価値が出てきます。
例えば、
「XX (新規ハードウェア）には○○の特性があり、普通の使い方では十分な性能が得られない。これを解決する技術として■という先行技術があるが～の欠点が存在する。我々は、これを解決する△という技術を導入し、～% の性能向上を達成した。」
というようなことが言えれば、ちゃんとした研究になりますし、査読つきの論文にもちゃんと通るようになります。
一つ冷静に考えないといけないことがあります。「単にそのハードウェア上に実装した（ポーティングとも言える）」では駄目。なぜなら、そこで得られた効果はそのハードウェアの賜物であるから。
研究とは、そこに世の中にとって役に立つような技術的な新発見、知見があって始めて価値が出てきます。
例えば、
「XX (新規ハードウェア）には○○の特性があり、普通の使い方では十分な性能が得られない。これを解決する技術として■という先行技術があるが～の欠点が存在する。我々は、これを解決する△という技術を導入し、～% の性能向上を達成した。」
というようなことが言えれば、ちゃんとした研究になりますし、査読つきの論文にもちゃんと通るようになります。
GPU を活用したデータストリーム処理
GPU を流体解析、分子動力学 (Molecular Dynamics)などの科学技術計算に応用した例は多く、データベースの分野ではクエリ処理に GPU を活用して最適化する研究などがある。
ただ、データストリーム処理に GPU を用いた論文はまだわずか。とりあえず見つかったものだけでも、以下の SIGMOD 2005 の論文のみ。 今年、来年にかけて大分この辺の研究が多くなっていくと思われます。
ただ、データストリーム処理に GPU を用いた論文はまだわずか。とりあえず見つかったものだけでも、以下の SIGMOD 2005 の論文のみ。 今年、来年にかけて大分この辺の研究が多くなっていくと思われます。
- Fast and approximate stream mining of quantiles and frequencies using graphics processors (SIGMOD 2005)
2009年5月26日火曜日
次世代 DNA シーケンサー＋GPU + ストリーム処理
今日の午後、生命理工学部の黒川先生とミーティングをした。詳細は Wiki に記載しているのでそちらを参照して頂きたいが、かなりいい線の成果が出せるような気がする。
DNA シーケンサーは毎秒 1.65 MByte の画像を生成。その画像から塩基配列(A,T,C,G) を判定。１回のランは１週間にわたり、生成されるデータサイズは 1～1.5TB。 シーケンサーの高性能化に伴って、出力するデータサイズも増すばかりだ。
一つのテーマは、このシーケンサーから出てくる画像を、ストリーム処理でリアルタイムに画像認識をし、得られる塩基配列データのみをデータに蓄える技術の研究開発。また、画像認識部には GPU を用いて高速化を行う。
この研究は２つの大事な貢献がある。一つは、ストリーム処理に GPU を適用した研究でかつリアルなアプリケーションを解いた点。 もう一つは、バイオインフォマティックスへの貢献。必要なストレージ容量を劇的に下げ、かつ処理時間を 1/x に削減したと言えば、バイオインフォマティックスに携わる研究者への大きな貢献にもなる。
DNA シーケンサーは毎秒 1.65 MByte の画像を生成。その画像から塩基配列(A,T,C,G) を判定。１回のランは１週間にわたり、生成されるデータサイズは 1～1.5TB。 シーケンサーの高性能化に伴って、出力するデータサイズも増すばかりだ。
一つのテーマは、このシーケンサーから出てくる画像を、ストリーム処理でリアルタイムに画像認識をし、得られる塩基配列データのみをデータに蓄える技術の研究開発。また、画像認識部には GPU を用いて高速化を行う。
この研究は２つの大事な貢献がある。一つは、ストリーム処理に GPU を適用した研究でかつリアルなアプリケーションを解いた点。 もう一つは、バイオインフォマティックスへの貢献。必要なストレージ容量を劇的に下げ、かつ処理時間を 1/x に削減したと言えば、バイオインフォマティックスに携わる研究者への大きな貢献にもなる。
Load Shedding
最近、DSMS (Data Stream Management System、つまりストリームコンピューティングのこと) における Load Shedding 技術に注目していて、論文を読んだり、新たな手法を模索している。
Load Shedding で重要なのは、システムのキャパシティぎりぎりにロードを如何に保てるかと、間引いた後に出力の品質を如何に下げないかだ。大きく分けて２つ手法があるが、確率的にランダムに、入力タプルを落とす (Random Dropという) やり方と、データやアプリケーションの特性を生かした (Semantic Dropという）やり方がある。
いくつか論文を読んでいて 思いついたアイデアを列挙する。
(1) Semantic Load Shedding for Internet Search Queries
検索クエリの特性 (Zipf 法則)を生かした Semantic Load Shedding
(2) Compensating Load Shedded Data with Eventual Consistency
Load Shedding は基本的に間引いたものは捨てるのが普通。捨てないで、Bursty ではない状況の時に、あとから処理をするという手法もありなのではなかろうか。アプリケーションに依存するだろうが。。。分散システムの世界において、データの複製間の一貫性として Strong Consistency（常に２つの複製データの一貫性は保たれている）, Weak Consistency（一貫性が保たれていないこともある） そして、Eventual Constitency （最終的には保たれている）の3つがある。Load Shedding においても、この最後の Eventual Consistency の考え方が適応できそうだ。
(3) Efficient Load Shedding with GPU
GPU を用いた Load Shedding. これは Load Shedding というよりは Load Balancing に近い。非常に Bursty な状況では, CPU 処理ではなく GPU に処理をまかせる
(4) Load Shedding with Differential XML Processing
XML データの処理。Load Shedding に差分XML処理の技術を生かす. (WWW 2005 などの論文を参考にする)
Load Shedding で重要なのは、システムのキャパシティぎりぎりにロードを如何に保てるかと、間引いた後に出力の品質を如何に下げないかだ。大きく分けて２つ手法があるが、確率的にランダムに、入力タプルを落とす (Random Dropという) やり方と、データやアプリケーションの特性を生かした (Semantic Dropという）やり方がある。
いくつか論文を読んでいて 思いついたアイデアを列挙する。
(1) Semantic Load Shedding for Internet Search Queries
検索クエリの特性 (Zipf 法則)を生かした Semantic Load Shedding
(2) Compensating Load Shedded Data with Eventual Consistency
Load Shedding は基本的に間引いたものは捨てるのが普通。捨てないで、Bursty ではない状況の時に、あとから処理をするという手法もありなのではなかろうか。アプリケーションに依存するだろうが。。。分散システムの世界において、データの複製間の一貫性として Strong Consistency（常に２つの複製データの一貫性は保たれている）, Weak Consistency（一貫性が保たれていないこともある） そして、Eventual Constitency （最終的には保たれている）の3つがある。Load Shedding においても、この最後の Eventual Consistency の考え方が適応できそうだ。
(3) Efficient Load Shedding with GPU
GPU を用いた Load Shedding. これは Load Shedding というよりは Load Balancing に近い。非常に Bursty な状況では, CPU 処理ではなく GPU に処理をまかせる
(4) Load Shedding with Differential XML Processing
XML データの処理。Load Shedding に差分XML処理の技術を生かす. (WWW 2005 などの論文を参考にする)
コールセンターにおけるストリーム処理
世の中には、様々な業界のコールセンターがある。生命保険、自動車保険、証券会社、航空会社、メーカーの修理受付窓口など。コールセンターは、企業と顧客とを結ぶインタフェースでもあり、Customer Satisfaction を向上させる重要な役割を持つ。あまりにも対応が悪いコールセンターだと、その企業の信用度も落ちる。
しかし、昨今は、アメリカのコールセンターは、コスト削減のために、インドのコールセンターを使っていたりする。アウトソーシング化だ。アメリカに滞在していたときに、United Airlines のコールセンターにかけたのに、明らかにかかったのは、インド人なまりの英語。IP 電話で音質もあまり良くなく、あれは、明らかにインドにかかっていたのであろう。
そのような中、次世代のコールセンターではオペレータの品質を保ち、Customer Satisfaction を向上させるために、以下のようなことをリアルタイムで検知する実証実験をしたいらしい。
- オペレータが言うべきことをちゃんと言っているか？
- お客さんがどのような状態か？怒っているか？Neutral か？
- お客様からどのような苦情を受けているか？それが Critical か？
入力データは、音声データか、または、音声解析技術によって落としたテキストデータかもしれない。いずれにしても、膨大な数のデータが流れてきて、かつ、それらをリアルタイムにオペレータに伝えなくてはならない。
これはまさにストリームコンピューティングの一つの適用分野だ。
皆さんも、世の中を見て、どのような分野にストリームコンピューティングを適用できるかを考えてみてください。
しかし、昨今は、アメリカのコールセンターは、コスト削減のために、インドのコールセンターを使っていたりする。アウトソーシング化だ。アメリカに滞在していたときに、United Airlines のコールセンターにかけたのに、明らかにかかったのは、インド人なまりの英語。IP 電話で音質もあまり良くなく、あれは、明らかにインドにかかっていたのであろう。
そのような中、次世代のコールセンターではオペレータの品質を保ち、Customer Satisfaction を向上させるために、以下のようなことをリアルタイムで検知する実証実験をしたいらしい。
- オペレータが言うべきことをちゃんと言っているか？
- お客さんがどのような状態か？怒っているか？Neutral か？
- お客様からどのような苦情を受けているか？それが Critical か？
入力データは、音声データか、または、音声解析技術によって落としたテキストデータかもしれない。いずれにしても、膨大な数のデータが流れてきて、かつ、それらをリアルタイムにオペレータに伝えなくてはならない。
これはまさにストリームコンピューティングの一つの適用分野だ。
皆さんも、世の中を見て、どのような分野にストリームコンピューティングを適用できるかを考えてみてください。
ストリーム処理が必要なアプリケーションとは？
前回、グリッドとストリーム処理の違いについて述べたが、今回は分散アプリケーションの分類を行い、ストリームコンピューティングのパラダイムが必要なアプリケーションを明確にする。
(1) 疎結合型
一つ一つのジョブの粒度が大きい、または、通信と計算をオーバーラップできるぐらいの粒度のジョブを伴うアプリケーショ ン。典型的な例としては、保険や金融分野おけるリスク計算（Black Sholes 方程式など）などに使われているモンテカルロシミュレーション、タンパク質の立体構造解析（グラフの同型性問題に落ちる）などが挙げられる。この種のアプリケーションは、 Latency が数百 msec にわたる広域の WAN 上に散在する計算機を束ねるグリッドなどでも動作可能である。また、昨今、Google や Yahoo などで使われている MapReduce や Hadoop などで動作するログ解析、クラスタ分析もこの範疇に入る。
(2) 密結合型
計算機同士が密に結合し、頻繁に通信を行う必要があるアプリケーション。たとえば、分子動力学法 (Molecular Dynamics) など、生体分子間の相互作用を加味し、化学反応を計算機上でシミュレーションするようなアプリケーションでは、計算機が頻繁に通信を行う必要がある。この種のアプリケーションは、低レイテンシの通信環境が求められ、各ノードが密に結合している必要がある。
(3) ストリーム型
(1), (2) は、本質的に長時間の計算量が必要なアプリケーションを並列度を上げることによって高速化するタイプのアプリケーションである。一方、ストリーム型は、全く別のタイプのアプリケーションであり、特徴としては、(a) 複数のセンサーから恒常的にデータが到着する (b) 到着データレートが変化し、Bursty な状況もある (c) (a), (b) のデータから即座にレスポンスを返す, の３つが挙げられる。(a), (b) のレスポンスを高速化するためには、前処理が必要であり、そのような前処理には (1) や (2) のようなアプリケーションが実行される場合もある。また、(1), (2) 同様にノード数を増やすことによって、レスポンスタイムやスケーラビリティを向上できるアプリケーションも多い。例としては、msec の反応が求められるアルゴリズムトレーディング、製造工程や医療分野におけるリアルタイム異常検知、サイバーセキュリティなどが挙げられる。
(1) 疎結合型
一つ一つのジョブの粒度が大きい、または、通信と計算をオーバーラップできるぐらいの粒度のジョブを伴うアプリケーショ ン。典型的な例としては、保険や金融分野おけるリスク計算（Black Sholes 方程式など）などに使われているモンテカルロシミュレーション、タンパク質の立体構造解析（グラフの同型性問題に落ちる）などが挙げられる。この種のアプリケーションは、 Latency が数百 msec にわたる広域の WAN 上に散在する計算機を束ねるグリッドなどでも動作可能である。また、昨今、Google や Yahoo などで使われている MapReduce や Hadoop などで動作するログ解析、クラスタ分析もこの範疇に入る。
(2) 密結合型
計算機同士が密に結合し、頻繁に通信を行う必要があるアプリケーション。たとえば、分子動力学法 (Molecular Dynamics) など、生体分子間の相互作用を加味し、化学反応を計算機上でシミュレーションするようなアプリケーションでは、計算機が頻繁に通信を行う必要がある。この種のアプリケーションは、低レイテンシの通信環境が求められ、各ノードが密に結合している必要がある。
(3) ストリーム型
(1), (2) は、本質的に長時間の計算量が必要なアプリケーションを並列度を上げることによって高速化するタイプのアプリケーションである。一方、ストリーム型は、全く別のタイプのアプリケーションであり、特徴としては、(a) 複数のセンサーから恒常的にデータが到着する (b) 到着データレートが変化し、Bursty な状況もある (c) (a), (b) のデータから即座にレスポンスを返す, の３つが挙げられる。(a), (b) のレスポンスを高速化するためには、前処理が必要であり、そのような前処理には (1) や (2) のようなアプリケーションが実行される場合もある。また、(1), (2) 同様にノード数を増やすことによって、レスポンスタイムやスケーラビリティを向上できるアプリケーションも多い。例としては、msec の反応が求められるアルゴリズムトレーディング、製造工程や医療分野におけるリアルタイム異常検知、サイバーセキュリティなどが挙げられる。
2009年5月22日金曜日
グリッドコンピューティングとストリームコンピューティングの違い
本質的な質問とは思えないが、グリッドとストリームコンピューティングの違いをよく聞かれるので、その回答を書く。
- 世間のグリッドの定義とグリッド研究者の定義は大きく異なる
(1) 世間は、多数のコンピュータを利用すればグリッド、ぐらいにしか考えていない
(2) グリッド研究者は、異なる管理ドメインにある組織上の計算資源を利用して巨大な
計算基盤を作るのがグリッドと定義している。これを実現するには、さまざまな レベルのHeterogeneity（OS, マシンアーキテクチャ、ネットワークなどの異種性) の問題を解かなければならない
- ただ、現実的には (2) のグリッドは、必ずしも実現しているとは言えず、(1) の 理解も認める必要がある
- 上記の (1) をグリッドと定義すると、グリッドは単にバッチ型の計算となる。リアルタイム性は気にすることなく、スループットを重視する。数理モデルのシミュレーションや、モンテカルロシミュレーションによる金融のリスク計算などシミュレーションが主な対象だ。
- グリッドとストリームコンピューティングの本質的な違いは以下の通りである。
以上
- 世間のグリッドの定義とグリッド研究者の定義は大きく異なる
(1) 世間は、多数のコンピュータを利用すればグリッド、ぐらいにしか考えていない
(2) グリッド研究者は、異なる管理ドメインにある組織上の計算資源を利用して巨大な
計算基盤を作るのがグリッドと定義している。これを実現するには、さまざまな レベルのHeterogeneity（OS, マシンアーキテクチャ、ネットワークなどの異種性) の問題を解かなければならない
- ただ、現実的には (2) のグリッドは、必ずしも実現しているとは言えず、(1) の 理解も認める必要がある
- 上記の (1) をグリッドと定義すると、グリッドは単にバッチ型の計算となる。リアルタイム性は気にすることなく、スループットを重視する。数理モデルのシミュレーションや、モンテカルロシミュレーションによる金融のリスク計算などシミュレーションが主な対象だ。
- グリッドとストリームコンピューティングの本質的な違いは以下の通りである。
- ディスクに格納 vs. オンメモリ上で処理： グリッドなどバッチ型計算では、基本的にはデータを一旦すべて格納する。高エネルギー加速器から放出されるイベントデータはテラバイトにも及ぶが、これらの莫大なデータを貯めるために、他拠点のストレージを透過的に統合するデータ処理基盤を提供する。一方、ストリームコンピューティングは、データの受信と同時に処理をし、必要なデータのみを受信するか、必要なデータだけをディスクに格納することによって、データの爆発に対処する。
- スループット vs. リアルタイム性： グリッドのようなバッチ型計算機とは異なり、リアルタイム性を重視する。また、グリッドにおけるジョブとは異なり、ストリームコンピューティングでは、常時データが流れ続け、かつデータのトラフィックが時間によって増減し、システムのキャパシティを越えるようなトラフィックが流れることもある。このように Bursty な状況でもリアルタイム性を如何に確保するかが Research Challenge でもあり、これがグリッドと本質的に異なる点である。
以上
2009年5月18日月曜日
日本学術振興会 (がくしん) 特別研究員
ドクターに行くと、日本学術振興会という文部科学省から特別研究員として毎月給料が出る制度があります。ドクター1年からその研究員になるためには、最低でも M2 の春の応募段階で一本以上は国際学会の論文がないとつらいので、ドクターに進学を希望する人はこれを目指して頑張ってください。
http://www.jsps.go.jp/j-pd/pd_user.htm#01
http://www.jsps.go.jp/j-pd/pd_user.htm#01
GPU 上の MapReduce
PACT 2008 (Parallel Architectures and Compilation Techniques) で発表された GPU 上で MapReduce のランタイムを実装する研究。
「Mars: A MapReduce Framework on Graphics Processors」
http://www.cse.ust.hk/catalac/papers/mars_pact08.pdf
スタンフォード大学の Christos 等は Cell や Multi-Core で MapReduce を作る研究をやっているので、最近はやりのプロセッサでは一通りやられた感がある。
だが、異機種混在環境 (Cell + GPU など) などでの MapReduce はまだまだ着手されていないだろう。
「Mars: A MapReduce Framework on Graphics Processors」
http://www.cse.ust.hk/catalac/papers/mars_pact08.pdf
スタンフォード大学の Christos 等は Cell や Multi-Core で MapReduce を作る研究をやっているので、最近はやりのプロセッサでは一通りやられた感がある。
だが、異機種混在環境 (Cell + GPU など) などでの MapReduce はまだまだ着手されていないだろう。
2009年5月13日水曜日
2009年5月11日月曜日
GPU を用いたデータストリーム処理の性能最適化
GPU (Graphic Processing Unit) を用いたデータストリーム処理の最適化に関する研究。GPU などの 専用ハードウェアと CPUが混在した環境で、アプリケーションに応じてジョブを最適なプロセッサに割り振るようにスケジューリングすることも考えられる。
SPADE (System S のジョブ記述言語）は グラフ として表現されるが、ノードに属性情報を付加することにより、その処理は自動的に専用ハードウェアで実行することにより性能を最適化する。
SPADE (System S のジョブ記述言語）は グラフ として表現されるが、ノードに属性情報を付加することにより、その処理は自動的に専用ハードウェアで実行することにより性能を最適化する。
仮想マシンを活用したデータストリーム処理
Xen や VMWare などの仮想マシン上でデータストリーム処理システムを動かすことにより、耐故障性に対応し、かつ、突発的に負荷が増大したときにも、仮想マシンの数を増やすことにより対応する。
XML データストリーム処理の性能最適化
近年、様々なデータの表現方法に XML が採用されている。XML はバイナリエンコーディングよりも、可読性やインターオペラビリティが高いという利点がある。しかし、一方、その冗長性 (開始タグ、終了タグを必ずつけなければいけない）がパフォーマンスの低下につながっていることが指摘されてきている。
WWW 2005 の論文 (Deltarser) では、XML 文書の類似性を利用した性能最適化手法が提案されている。データストリーム処理システムの入力データとしても、どうように、XML が入力として使われるので、Deltarser と同様の最適化手法が使用できるのではないだろうか。
WWW 2005 の論文 (Deltarser) では、XML 文書の類似性を利用した性能最適化手法が提案されている。データストリーム処理システムの入力データとしても、どうように、XML が入力として使われるので、Deltarser と同様の最適化手法が使用できるのではないだろうか。
データストリーム処理システムのジョブスケジューリング手法に関する研究
分散システムでは長年、ジョブスケジューリングが一つの研究テーマとなっている。データストリーム処理システムにおいても同様に、DAG (Directed Acyclic Graph) として表現されるアプリケーションを計算リソースにどのように割り振るかは一つのチャレンジングなテーマだ。
様々な手法が考えられるが、スループットを最大化することを目的とすると、グラフ理論の最大フローアルゴリズム (Ford-Fulkerson など) が活用できるのではないだろうか。
様々な手法が考えられるが、スループットを最大化することを目的とすると、グラフ理論の最大フローアルゴリズム (Ford-Fulkerson など) が活用できるのではないだろうか。
2009年5月9日土曜日
ヒューリスティックスを用いた性能最適化
Zipf の法則というものを知っていますか？ 一般化したものは Power Law といいますが、様々な分野で起こる現象のヒューリスティックス（経験則）です。
Zipf のひとつのインスタンスに、パレートの法則や80:20 の法則というものがあります。たとえば、２割の顧客がその店の８割の売り上げに貢献している、などです。インターネットの検索キーワードにもこの法則が成り立つことがわかっていて、２割のキーワードが全体の８割に近くになります。
このようなヒュースリティックスは、パフォーマンスの最適化、たとえば、キャッシュのポリシーの設計方法などに大きく参考になります。たとえば、われわれは、データストリーム処理システムにおける性能最適化を研究していきますが、過負荷時に処理を間引く技術分野として Load Shedding といわれる分野があります。まだまだ発展途上の研究分野ですが、Power Law の経験則を用いた Load Shedding などは良い研究テーマになると思われます。
Zipf のひとつのインスタンスに、パレートの法則や80:20 の法則というものがあります。たとえば、２割の顧客がその店の８割の売り上げに貢献している、などです。インターネットの検索キーワードにもこの法則が成り立つことがわかっていて、２割のキーワードが全体の８割に近くになります。
このようなヒュースリティックスは、パフォーマンスの最適化、たとえば、キャッシュのポリシーの設計方法などに大きく参考になります。たとえば、われわれは、データストリーム処理システムにおける性能最適化を研究していきますが、過負荷時に処理を間引く技術分野として Load Shedding といわれる分野があります。まだまだ発展途上の研究分野ですが、Power Law の経験則を用いた Load Shedding などは良い研究テーマになると思われます。
登録:
投稿 (Atom)
