Document

分散アプリケーションを支援した
カーネルレベルバジェット
スケジューラの設計と実装
近山・田浦研究室
50374 グェントアンドゥク
背景


計算資源が膨大、分散している
資源をユーザで共通
資源を効率的に利用ために、うまくスケジュール
必要
目的

広域分散資源管理システムのスケジューラ




効率的にリソースを利用
並列アプリケーションをサポート
ユーザ間の平等性を保つ
Interactiveプロセスをサポート
関連研究



Fair share scheduler
Batch queuing system (PBS, SGE…)
Co-scheduling, gang-scheduling
Fair share scheduler


各ユーザの間の平等性を保つ
実装の仕方は色々

例: fixed-budget model:


Budgetを各ユーザに配り、ユーザのプロセスが実行される
ときに、コストがかかって、budgetが減る。Budgetが0の
ユーザのプロセスは実行されない
単にbudgetとコストを使うと、並列アプリケーショ
ンに向かない
Batch queuing system



Jobsをqueueに入れて、リソースがあったら実行
するシステム
例: PBS, SGE
効率的にリソース利用のが難しい。負荷集中
Running
job
Job3
Job2 Job1
Job4
Job n
Running
job
Gang scheduling, co-scheduling

並列アプリケーションのためのスケジューリング




並列アプリケーションのプロセスをgroupに同時にス
ケジュール
スケジュールされたアプリケーションのプロセスが占
有的に資源を使用
ユーザ間の平等性はあまり考えない
分散環境でのコストが大きい
提案手法

Fixed-budget model のように、



ユーザは各プロセスの優先度を直接設定可能


並列と逐次計算アプリケーションを区別
カーネルレベルで実装



各ユーザはbudgetを持つ、スケジューラはcharging
平等性
Interactive プロセスを対応
リソースを効率的に利用
各ノードのスケジューラは独立

負荷集中なし
平等性

「平等性」の定義は難しい




使用時間が同じなら平等  Interactive processは?
短CPU時間プロセスを常に優先  どう判断する?
ユーザの目的に応じて平等性が違う
正確的に平等ではないが、目的に応じての平等
が必要  variant price と fixed-budget
Price設定可能

Priceはプロセスのdynamic priority

普通のOSでは設定できない


Fixed-budgetであれば、price設定が可能


プロセス間の平等を保てない
ずっとCPU独占できないから
Dynamic priorityをユーザが決めれば、並列ア
プリケーションを一定の時間で優先できる

全ノードで同時に優先すれば、co-schedulingの効果
Interactiveプロセスの対応

Batch queuing systemでinteractiveプロセスの
支援が難しい



Queueで待たせる
ノード探す時間がかかる
カーネルレベルで実装すれば、すぐinteractive
プロセスをスケジュール可能
分散したスケジューラ


全ノードのリソースを管理するのは大変
各ノードでスケジューラが制御


同時にノードを取得したい時に、



負荷集中なし
空いているノードを探索
高いpriceを設定
分散してもシステムの全体を協調可能
システムの構成

Budget スケジューラ


各ノードで独立に動作
リソース探索システム


各ノードの負荷情報、最大、最小priceの情報を提供
全ノードで集計するにはGXPを使う
Budget scheduler





Normal mode と budget mode
CPU intensiveなプロセス  budget mode
普通のプロセス  normal mode
実行しているうちにmodeを変更させる
Normal modeのプロセスは常に優先される


Interactive processはこのモード
CPU intensiveなプロセスはpriceを高くすれば
一時的にCPU独占可能
ノード検索システム

簡単なプログラム

各ノードで実行されて、情報を提供


負荷、CPU utilization, 最大、最小price…
全ノードの集計のために、GXPを使う
評価



Interactivity
並列アプリケーションのperformance
ユーザ間の平等
Interactive プロセスの性能

メッセージping-pongテスト



Budget scheduler と普通のLinux 2.6 schedulerで
の round-trip timeを比較
CPU intensiveなプロセスが無い時
同じユーザのCPU intensiveなプロセスが
backgroundにあった時
Round-trip time(us)
Round-trip time (backgroundプロセスなし)
700
Budget scheduler disabled
600
Budget scheduler enabled
500
400
300
200
100
0
0
20
40
60
Message number
80
100
Round-trip time (infinite-loopがbackground で実行)
Time(us)
400
350
Budget scheduler disabled
300
Budget scheduler enabled
250
200
150
100
50
0
0
20
40
60
80
Message number
100
120
NAS Parallel Benchmarksの結果
EP benchmark: CPU intensive, 4 nodes
300
Budget scheduler disabled
250
Budget scheduler enabled
Time(s)
200
150
100
50
0
0
1
2
3
Number of background processes at each node
4
IS benchmark (計算と通信性能): 4 nodes
25
Budget scheduler disabled
Budget scheduler enabled
Time(s)
20
15
10
5
0
0
1
2
3
Number of background proceses at each node
4
ユーザ間のCPU割り当て






3 users: A, B, C
A: 1つのプロセス A1 だけ実行
B: 2つのプロセス B1, B2
C: 3つのプロセス C1, C2, C3
全てのプロセスは同じコード: infinite loop
10億回のvariable update の時間を測定
各プロセスの実行時間
700
600
Time(s)
500
400
300
200
100
0
A
B1
B2
Process
C1
C2
C3
結論

並列分散アプリケーションを支援したスケジュー
ラシステムを提案した



専用でないクラスタでの並列アプリケーションの性能
を専用クラスタと同じようにできた
Interactive プロセスを支援
ユーザ間の目的に応じての平等性を実現した
今後の課題

Co-scheduling 効果は1 epochだけにあった



Budget が間もなく無くなったときに、空いている
ノードまでのプロセスmigration


その後同期しないと消える
Co-scheduling効果を維持する必要
ユーザモードでbudget run-out signal handlerでやる
実際のクラスタに運用して、正確な評価をする

Download Report