Hardware Counter Driven On-the-Fly Request Signatures

ASPLOS'08の，Kai Shenさんたちの論文です．
ハードウェアカウンタの値を用いて実行中のリクエストを早期識別しちゃおう！というスゴイ話．
ゼミでやったので詳しめにまとめ．
(先輩方に色々フォローしてもらって勉強になりました！もっとしっかり読めるようになりたい)

●背景＆問題点●
OSは，実行時のワークロードのプロパティを知ることで，より良いスケジューリングが可能になったり，コストを抑えたNWサービスが可能となる．
しかし，現状では，過去のリクエストからワークロードのプロパティを予測する手法がとられている．
この手法では，入力パターンが多く，実行時の状態が変化するワークロードの予測を当てることは難しい．

●提案●
サーバリクエストを実行中の早い段階で識別し，プロパティを予測しよう．
　－プロパティとは：メモリ使用量，CPU使用量，I/O発行量など
この，リクエストの識別は，ハードウェアカウンタの値を数個組み合わせてシグネチャとすることで可能となる．

●ハードウェアカウンタの組み合わせ●
レジスタにマップできるハードウェアカウンタの数はプロセッサにより限られているため，数個選ぶ必要がある．
選ぶ際には，以下の3つに注意．
1．正規化の種類(time-based or progress-based)
　全てのハードウェアカウンタを両方で正規化し，相関係数が高い値になった方を採用する．
　調査の結果，イベントカウント数が関わる値はprogress-based，持続時間が関わる値はtime-basedが適していることが分かった．
2．環境の影響
　リクエストを並列に実行した場合の相関係数は，全ハードウェアカウンタの値で低くなっているが，その中でもなるべく影響を受けないもの(*)を採用する．(L2Refferenceなど)
　*L2キャッシュ・メモリアクセスに関わる値は，コンテキストスイッチの影響を大きく受けるため，避けたい
　*L1キャッシュ・トレースキャッシュ・TLBのイベント関連は，ハイパースレッディングの機能を持つ場合に，これらの機能を共有するために不安定な値をとるため，避けたい
3．アプリケーションによる違い
　サーバアプリケーションの種類によって効果のあるハードウェアカウンタが異なるため，それぞれのアプリケーションごとに適切なハードウェアカウンタを選ぶ必要がある．

●値の収集とリクエスト識別●
1．ハードウェアカウンタの値はインクリメントされるため，定期的に値を取り出し，その差を収集する．
2．収集したいくつかの値をシグネチャとし，そのリクエストのプロパティとの対応表を作成する．
3．対応表の値と実行中のハードウェアカウンタの値の差により，リクエストを識別する．
　－リクエスト実行してからある一定時間で識別を行う方法と，対応するリクエストが見つかるまで時間を増やして識別を行う方法の2種類がある．

●実験●
4つのサーバアプリケーションで実験した．
―TPC-C，TPC-H，RUBiS，Index search(最初の3つはCPU-bound, その他はI/O-bound)
CPU使用量，I/Oサイズの予測の正確性を評価したところ，並列実行でも7%,3%,20%,40%と非常に低いミスを実現．
RUBiSやIndexsearchは，初めに同じような経路を辿るために他と比べて識別が難しくなっているが，TPCの2つに関しては，リクエスト実行の非常に早い段階で正確な識別ができている．

●応用例●
1．効果的なスケジューリングの実現
　この提案手法を用いてレディータスク内で最も残り時間が短いタスクをキューの先頭にもってくることで(SRPTスケジューリング)，デフォルトのスケジュールに比べ70%以上応答時間の削減に成功した．
2．異例なリクエストの検出
　似たリクエストでクラスを作り，リクエストを早期に分類することで，SQLインジェクションなどの異例なリクエストの検出が行えた．


…ちょっとはしょったつもりが，詳しく書きすぎたかもｗ
長いｗ