VMが利用可能なCPU数の変化に対応した 並列アプリケーション実行の最適化 九州工業大学 髙山 都旬子 光来 健一

VM内での並列アプリケーションの実行 仮想マシン（VM）内で並列アプリケーションを動か すことも増えてきた アプリケーションスレッドは仮想CPUに割り当てられる 仮想CPUは物理CPU（CPUコア）に割り当てられる 仮想CPUアフィニティを設定すると割り当てを固定 アプリケーション VM スレッド vCPU vCPU vCPU vCPU 仮想CPU 物理CPU pCPU pCPU pCPU pCPU

VMマイグレーションの影響 VMは他のホストに移動されることがある マイグレーション先で物理CPUが不足する可能性 例：サーバのメンテナンス、負荷分散 マイグレーション先で物理CPUが不足する可能性 物理CPUより多くの仮想CPUを動作させるのが一般的 オーバサブスクリプション 並列アプリケーションはCPUを占有することが多い VM1 VM1 VM2 マイグレーション 仮想CPU 仮想CPU 物理CPU 物理CPU サーバ1 サーバ2

物理 CPU の不足時の対処 (1/3) VM1 VM1 VM2 複数のVM間で物理CPUを共有 1つの物理CPUを複数のVMの仮想CPUに割り当てる 仮想CPUが使える物理CPUの割合はVMの重みで決まる 例：50%と50%（デフォルト）、33%と67% 使い切らない場合は他の仮想CPUが使う VM1 VM1 VM2 仮想CPU vCPU vCPU vCPU vCPU vCPU vCPU 物理CPU pCPU pCPU pCPU pCPU

物理CPUの不足時の対処 (2/3) VM1 VM1 VM2 VMが利用できるCPU使用率を制限 CPU使用率の上限を設定することで物理CPUを分け合う デフォルト：割り当てられた物理CPU数×100%が上限 何個の物理CPUを何%ずつ使用するかは仮想CPUスケジューラに依存 VM1 VM1 VM2 仮想CPU vCPU vCPU vCPU vCPU vCPU vCPU vCPU vCPU vCPU vCPU vCPU vCPU 物理CPU 50% 50% 40% 25% 40% pCPU pCPU pCPU pCPU 60% 75 % 60%

物理CPUの不足時の対処 (3/3) VM1 VM1 VM2 VMへの物理CPU割り当てを削減 1つの物理CPUをVMの複数の仮想CPUに割り当てる 仮想CPUアフィニティを利用 仮想CPU数より少ない数の物理CPUを占有 VM1 VM1 VM2 仮想CPU vCPU vCPU vCPU vCPU vCPU vCPU vCPU vCPU vCPU vCPU vCPU vCPU 物理CPU pCPU pCPU pCPU pCPU pCPU pCPU pCPU pCPU

予備実験 並列アプリケーションの性能低下の調査 対象とした並列アプリケーション 実験環境 物理CPUの不足時の三つの対処について Tascell [Hiraichi et al.'09] で並列化したフィボナッチ数計算 NAS Parallel Benchmarks (BT) 実験環境 CPU: AMD Operation 6367 (16コア) × 2，メモリ: 320GB 物理CPUとして16コアのみを使用 仮想化ソフトウェア: Xen 4.4.0 VM: 仮想CPU 16個，メモリ 4GB，Linux 3.13.0

複数のVM間で物理CPUを共有した場合 VMの台数を1台から8台まで増加させた 台数を増やすほど理論値より遅くなった 理論値からの増加率 n台の時の理論値：1台の時の実行時間のn倍 理論値からの増加率 fib: 12% ～ 20%，BT: 104% ～ 191%

VMのCPU使用率を制限した場合 CPU使用率の上限を1600%から100%まで減少 CPU使用率を制限するほど理論値より遅くなった c%の時の理論値：制限なしの時の実行時間の1600/c倍 物理CPUを共有した場合より大幅に性能低下 理論値からの増加率 fib: 23% ～ 328%，BT: 157% ～ 5243% 最初が１６００％ 使用率を減らしていったときの実行時間

VMへの物理CPU割り当てを削減した場合 どの場合も理論値より少し遅くなった n個の時の理論値：16個の時の実行時間の16/n倍 物理CPUを減らすほど性能低下するというわけではなかった 理論値からの増加率 fib: 4% ～ 25%，BT: 16% ～ 78%

理論値より性能が低下する原因 (1/2) 仮想CPUスケジューリングのオーバヘッド ロックホルダ・プリエンプション [Uhlig et al.'04] の発生 ロックを保持している仮想CPUが他の仮想CPUに物理CPUを奪われ、ロックの解放が遅れる pCPU 0 vCPU 0 他のｖCPU vCPU 0 pCPU 1 vCPU 1 vCPU 1 ロック解放待ち ：ロックを保持して行う処理

理論値より性能が低下する原因 (2/2) vCPUスタッキング [Sukwong et al.'11] の発生 ロック待ちの仮想CPUがロックを保持している仮想CPUよりも先に物理CPUを割り当てられ、処理が進まない pCPU 0 vCPU 0 vCPU 1 vCPU 0 vCPU 1 ロック解放待ち ：ロックを保持して行う処理

提案：pCPU-Est 物理CPUの不足時に並列アプリケーションの実行を 最適化 仮想CPUの切り替えを減らすための最適化を行う VM の仮想CPU 数の最適化 アプリケーションスレッド数の最適化 そのために、VMが実際に利用可能な物理CPU数を見積もる

VMの仮想 CPU 数の最適化 仮想CPUを減らすことでスケジューリングを回避 仮想化システムの管理者のみ変更可能 システム全体に影響が及ぶ可能性も アプリケーション VM vCPU vCPU vCPU vCPU pCPU pCPU pCPU pCPU

アプリケーションスレッド数の最適化 スレッドを減らすことで仮想CPUを間接的に減らす ユーザが容易に調整できる VMが利用可能な物理CPU数に応じて調整 ユーザが容易に調整できる 実行中に変更可能かどうかはアプリケーション依存 VM アプリケーション スレッド vCPU vCPU vCPU vCPU pCPU pCPU pCPU pCPU

利用可能な物理CPU数の見積もり 物理CPUと仮想CPUをグループに分ける VMが利用可能な物理CPU数を算出 1/2 1/3 vCPU vCPU vCPU vCPU vCPU pCPU pCPU

分割アルゴリズム システム内のすべての物理CPUと仮想CPUから なるグラフを考える 頂点：物理CPU、仮想CPU VM1 VM2 1 2 3 4 仮想CPU 物理CPU 1 2 3

グループの作成 つながっている仮想CPU数が最小の物理CPUを選択 その物理CPUとつながっている仮想CPUからなるグ ループを作成 1 2 3 4 仮想CPU 物理CPU 1 2 3

グループの拡張 (1/2) グループに追加する物理CPUを選択 その物理CPUとつながっている仮想CPUをグループ に追加 1 2 3 4 仮想CPU 物理CPU 1 2 3

グループの拡張 (2/2) 物理CPUの割合が大きくなるか変わらない場 合、拡張したグループを採用 グループの拡張を繰り返す 物理CPUの割合が小さくなる場合は採用しない 元のグループから外に出ている辺を削除 1/2 > 2/5 1 2 3 4 仮想CPU 物理CPU 1 2 3

グラフ分割 グラフの残りの部分に対して同様の作業を繰り返す 最終的にいくつかのグループに分割される グループの作成 グループの拡張 1/3 < 2/3 < 3/3 1 2 3 4 仮想CPU 1 物理CPU 2 3

グループのマージ 作成されたグループをできるだけマージする 削除した辺でつながれていた２つのグループを選択 局所的にグループを作るだけでは正しい分割ができない 削除した辺でつながれていた２つのグループを選択 辺の仮想CPU側をグループ1、物理CPU側をグループ2 グループ2の物理CPUの割合のほうが大きいか等しければマージ 1 2 3 4 仮想CPU 物理CPU 1 2 3 グループ1 グループ2

利用できる物理CPU数の例 8/5→2個 12/5→3個 2/2+1/3→2個 2/3→1個 VM1 VM2 VM1 VM2 1 2 3 4 1 2 3 4 1 1 2 3 4 1 2 3 1 1/2 1/3 4/5

実験 目的 対象とした並列アプリケーション 実験環境 最適なアプリケーションスレッド数・仮想CPU数を調査 pCPU-Estによる最適化の効果を確認 最適なスレッド数・仮想CPU数を用いた 対象とした並列アプリケーション 並列フィボナッチ数計算 (fib) NAS Parallel Benchmarks (BT) 実験環境 予備実験と同じ

最適なアプリケーションスレッド数 スレッド数を変えて実行し、最適なスレッド数を算出 物理CPUの共有時： 16/VMの台数 CPU使用率の制限時： CPU使用率に対応する物理CPU数 物理CPUの削減時：VMが利用可能な物理CPU数 いずれの場合もVMが利用可能な物理CPUの数が最適 BT

最適な仮想CPU数 VMの仮想CPU数を変えて実行し、最適な仮想 CPU数を算出 BTでは利用可能な物理CPU数が最適とは限らなかった

最適化の効果：物理CPUの共有時 どちらの最適化でも性能が改善された スレッド数の最適化のほうがよい場合があった 1.2〜3.2倍の高速化 特に理論値からの増加率が大きかったBTで改善 スレッド数の最適化のほうがよい場合があった VMが8台の時のfib (6%)、VMが2台の時のBT (69%)

最適化の効果： CPU使用率の制限時 物理CPUの共有時より性能改善が大きかった スレッド数の最適化のほうが大幅によい場合が あった 1.2〜55倍の高速化 スレッド数の最適化のほうが大幅によい場合が あった 1200〜600%の時のBT (〜113%) CPU使用率を減らしたときの最適化の効果

最適化の効果：物理CPUの削減時 他の対処の場合と似た傾向が見られた 1.1〜2.0倍の高速化 スレッド数の最適化のほうが最大60%性能がよい 仮想CPU数を利用可能な物理CPU数と同数にする と性能が悪化する場合があった

関連研究 VCPU-Bal [Song et al.'13], FlexCore [Miao et al.'15] VMの仮想CPU数を最適化することで性能を向上 仮想CPUアフィニティは考慮しない vScale [Cheng et al.'16] VMが使い切らなかった物理CPUを考慮してVMの仮想CPU数を最適化 複数のVMが物理CPUを共有する場合のみを想定 コスケージュリング [VMware'08] VMのすべての仮想CPUを同時にスケジューリング 必要な数の物理CPUがそろうまで待つ必要がある

まとめ 物理CPUの不足時の対処を行った際の並列アプリ ケーションの性能への影響を調査 並列アプリケーションを最適に実行するpCPU-Estを 提案 VMが利用可能な物理CPU数を見積もる アプリケーションスレッド数・仮想CPU数を最適化 スレッド数の最適化がより効果的

今後の課題 pCPU-Estが見積もった物理CPU数でどこまで最適な 実行が可能かを調査 Linuxのcgroupsを用いた最適化手法を検討 非対称なVMに対する仮想CPU数の最適化 VMの仮想CPU数を減らした時に利用できる物理CPU数も減る場合がある 利用できる物理CPU数は変わらないようにしたい