データストリーム処理における適応的なウィンドウ処理

以下、StreamGPU に関係するアイデア。森田君、注目。

以下は、GPU がなくても成立する研究テーマではあるのだが、GPU を使ってストリーム処理が高速化できたというのは、今の状態だと、CULA のライブラリに頼っているだけ。方向性としては、特異値分解のように如何にも効果がありそうなアプリケーションではないところに適応すること、もしくは、以下のような数理的なモデルを用いて味付けするかどちらかだ。

タイトル：　データストリーム処理における適応的なウィンドウ処理

[前提条件]
- アプリケーションは異常検知などレイテンシが critical なものを想定するが、あらかじめ何秒以下に反応すべき、という情報が与えられているものとする。
- また、レイテンシも重要だが、異常検知の精度も重要であり、それがウィンドウサイズとウィンドウのスライドサイズに依存する
- システムは動的に、ジョブや到着タプル数などが変化するものと仮定し、すべてのノードを使えるものとは限らない
- システムは異機種混在環境で複数ノード、複数コアから成り立つ。また、いくつかのノードには GPGPU などのアクセラレータが搭載されているとする

[我々の提案手法]
システム全体の利用可能なリソース状況（ジョブ数、ネットワーク、到着タプル数）
によって、アプリケーションによって与えられたレイテンシを満たす中で、異常検知の精度を最大化する、つまり、
- 動的にウィンドウサイズを最大化し、かつ、
- スライドサイズを小さくする
ことを動的に行う仕組みを構築する。

[実装方法：　数理的モデルの構築と更新]

まず、重回帰分析によって数理的なモデルを構築する。
変数 Y = f(x1, x2) (a1*x1 + a2*x2)

- Y : 1回の平均処理時間（レイテンシ） （平均だけでなく、最大値も見たいが）
- x1: ウィンドウサイズ (大きくできれば長いスパンでのトレンドが見れるので、大きい方が良い。SST の場合、CPU と GPU とで 512 以上のとき平均処理時間に大きな差が現れるので、もし 512 以上のときには GPU が使用できる場合にはそちらを用いる)
- x2: ウィンドウをスライドさせるサイズ（細かい粒度で異常がわかるので、サイズは小さい方がよい）

このモデルは以下に与える外部の制約条件（特に動的情報）によって、変化するので、実行時に定期的に更新する。

外部から与える制約条件は以下の通り
- 1秒間に到着するタプル数（1タプルのバイト数）
- 1回の計算処理時間
- クラスタ全体のジョブの数他のジョブがどのぐらい走っているか
- クラスタに関するスペック情報(静的に取得可能)
(ノード数、コア数、GPU あり/なし、ネットワーク、ストレージ）

また、上記のモデルは CPU と GPU でそれぞれ数理的なモデルを構築する

[ 最適なウィンドウサイズ・スライドサイズを調節し、動的にシステム状況が変化する中でスループットを最大化する]

重回帰分析によって、CPU 使用率、ウィンドウサイズ、スライドサイズ, GPU の使用有無を指定すると、得られるスループットが予測できる。 T = f(CPU utilization, Window Size, Slide Size、GPU or CPU)

グラフとしては、
CPU Utilization と GPU/CPU は与えられるものなので、上記のグラフができれば、最大のスループットをえる

パラメータとして、
- GPU が使えるか否か (0/1)
- 他のジョブが使用しているCPU 使用率はいくつか？
という制約条件が与えられているときに、最大のスループットを出すために、
ウィンドウサイズ、スライドサイズを動的に調節し、かつ、GPU を使うか否かを
動的に選択する。


目的関数: T (スループット) ＋SW + 1/SS
ウィンドウサイズ SW →最大化 (1024 ぐらいまでの中で最大化) 、スライドサイズ SS →最小化

制約条件:
- レイテンシ L < α（ある値以下）
- ウィンドウサイズ SW < 1024 で最大
- その他のジョブのCPU 使用率
- GPU が使用できるか否か