COLA: optimizing stream processing applications via graph partitioning

COLA: optimizing stream processing applications via graph partitioning
URL

　System S などのデータストリーム処理では、オペレータ（頂点）とオペレータ間を流れるストリーム（エッジ）をデータフローグラフとしてアプリケーションを記述することが一般的になっている。このような論理的なフローを実際の物理的な計算機環境上で稼動させ、かつ最適なパフォーマンスを出すためには、ある単位でオペレータを一つのOSのプロセスとして Fusion （統合）することが不可欠となる。Fusion の仕方としては、各オペレータの処理時間とオペレータ間の通信時間のバランスを考えて、Fusion をさせるかしないかを判断するが、多くのオペレータが存在する場合には到底、人間が判断することができない。当論文では、この Fusion のアルゴリズムを最小カットのグラフ分割問題として定式化することで、最適な Fusion パターンを割り出す手法を提案している。