2008.04.29 Tuesday 21:46
分散環境の演算配置
○Network-Aware Operator Placement for Stream-Processing Systems
分散環境における演算の配置のための関連研究としてこの論文を読んだ。
今回は、声に出して朗読しながら読んだ。発音のダメさにへこんだ。。。
分散環境において、ノード間のネットワーク遅延とデータストリームの入力レートを基に、ネットワーク使用量を最小にするような演算の配置を提案。
そのために、Stream-based Overlay Network(SBON)をストリーム処理エンジンとネットワークの仲立ちとして構築した。ストリーム処理エンジンにはBorealisを使用。このSBONはCost Space管理とそれを用いた演算配置指示する機能と配置最適化の機能を有する
これらを実装した上で、演算配置(Relaxation)がシミュレーションとPlanetLab上で他の4つの演算配置に比べて、相対的によい性能を示している。
*この論文はProducer(情報源or情報源近く)とConsumer(利用者)は固定としている。また、先輩の論文は初期配置後は、この論文の式を利用したネットワーク使用量が最小となる場合、固定すべきアプリを除く演算を再配置する方法。双方と自分のする研究との違いは情報源が動的に移り変わるという点。
最適化の基準として、一問合せあたりのネットワーク使用量として以下の式を目安としている。(図の引用は論文と先輩パワポから)
演算配置のための基本的なアイデアは下図
Cost Space上で、ProducerとConsumerが配置すべき演算を引っ張りあっている図
最後の式が位置エネルギーにあたり、これを最小とする配置を考える。Cost Spaceはこの論文ではネットワーク遅延(latency space)を採用しているが、(ノード負荷も考慮したモデルは作ったみたい)他にも、availability, bandwidth, memory, processing powerなど考えられる。
全ての演算に対して、下の流れをとる。
1,Virtual operator placement
Latency Space上で、位置エネルギーが最小となる理論的な配置を探す。
2,Physical operator placement
1の理論的な最適配置に近いノードをkとりだして、負荷状況や既に他の共有できる演算があるかなども判断して、実ノード上に配置
3,適宜、配置したノードを最適化により再配置
先輩の演算配置の手法では以下のようになる(修論引用)
1、初期状態として、各演算を入力ストリームに最も近いノードに配置する。
2、情報源に近い演算から順に、式を用いてネットワーク使用量が最小になるノードに移動させる
3、すべての演算を評価し終わった後、ネットワーク使用量が前回のプランより閾値以上低下したらそのプランを出力する。そうならなければ、2を再び実行する
再配置はアプリを固定して、上記のようにネットワーク使用量を算出し、配置後のプランのネットワーク使用量が、現在のネットワーク使用量よりも閾値以上低くなっていたら、再配置させる
以上の流れ(特に、ネットワーク使用量などを参考に、情報源が変動する時の再配置やコストモデルを考える)
分散環境における演算の配置のための関連研究としてこの論文を読んだ。
今回は、声に出して朗読しながら読んだ。発音のダメさにへこんだ。。。
分散環境において、ノード間のネットワーク遅延とデータストリームの入力レートを基に、ネットワーク使用量を最小にするような演算の配置を提案。
そのために、Stream-based Overlay Network(SBON)をストリーム処理エンジンとネットワークの仲立ちとして構築した。ストリーム処理エンジンにはBorealisを使用。このSBONはCost Space管理とそれを用いた演算配置指示する機能と配置最適化の機能を有する
これらを実装した上で、演算配置(Relaxation)がシミュレーションとPlanetLab上で他の4つの演算配置に比べて、相対的によい性能を示している。
*この論文はProducer(情報源or情報源近く)とConsumer(利用者)は固定としている。また、先輩の論文は初期配置後は、この論文の式を利用したネットワーク使用量が最小となる場合、固定すべきアプリを除く演算を再配置する方法。双方と自分のする研究との違いは情報源が動的に移り変わるという点。
最適化の基準として、一問合せあたりのネットワーク使用量として以下の式を目安としている。(図の引用は論文と先輩パワポから)
演算配置のための基本的なアイデアは下図
Cost Space上で、ProducerとConsumerが配置すべき演算を引っ張りあっている図
最後の式が位置エネルギーにあたり、これを最小とする配置を考える。Cost Spaceはこの論文ではネットワーク遅延(latency space)を採用しているが、(ノード負荷も考慮したモデルは作ったみたい)他にも、availability, bandwidth, memory, processing powerなど考えられる。
全ての演算に対して、下の流れをとる。
1,Virtual operator placement
Latency Space上で、位置エネルギーが最小となる理論的な配置を探す。
2,Physical operator placement
1の理論的な最適配置に近いノードをkとりだして、負荷状況や既に他の共有できる演算があるかなども判断して、実ノード上に配置
3,適宜、配置したノードを最適化により再配置
先輩の演算配置の手法では以下のようになる(修論引用)
1、初期状態として、各演算を入力ストリームに最も近いノードに配置する。
2、情報源に近い演算から順に、式を用いてネットワーク使用量が最小になるノードに移動させる
3、すべての演算を評価し終わった後、ネットワーク使用量が前回のプランより閾値以上低下したらそのプランを出力する。そうならなければ、2を再び実行する
再配置はアプリを固定して、上記のようにネットワーク使用量を算出し、配置後のプランのネットワーク使用量が、現在のネットワーク使用量よりも閾値以上低くなっていたら、再配置させる
以上の流れ(特に、ネットワーク使用量などを参考に、情報源が変動する時の再配置やコストモデルを考える)
研究 | - | -