ᵡᵿᵱᵮᵟ ᵣᶌᶅᶇᶌᶃ
6.5 ジョブのクラスター化に関する検討
6.
dŚƌĞĂĚϭ dŚƌĞĂĚϮ
dŚƌĞĂĚE
͙ ͘͘
00000000 00000000 00000000
00000000 00000000 00000000 00000000
0000000000 0000000000 0000000000
00000000 00000000 00000000
000000000 000000000 000000000
000000 000
LJĐůĞ ĞŐŝŶ LJĐůĞŶĚ
͙ ͙͘͘
͗džĞĐƵƚŝŶŐŐĞŶƚ:Žď
0000000000000000000000000000 0000000000000000000000000000
0000000000000000000000000000 ͗tĂŝƚŝŶŐƚŽ&ĞƚĐŚ
00000000000000000000000000000 00000000000000000000000000000
00000000000000000000000000000 ͗&ĞƚĐŚŝŶŐŐĞŶƚ:ŽďĨƌŽŵŐĞŶƚDĂŶĂŐĞƌ
ŐĞŶƚ:Žď
00000000000000000000000000000 00000000000000000000000000000
00000000000000000000000000000 ͗tĂŝƚŝŶŐKƚŚĞƌdŚƌĞĂĚƐ
ŐĞŶƚDĂŶĂŐĞƌ
0000000000 0000000000 0000000000 00000000 00000000 00000000
00000000 00000000 00000000
00000000 00000000 000000 000000
00000000000000000000 00000000000000000000 00000000000000000000 0000000000000 0000000000000 0000000000000
図 6.6: ソートを利用したジョブ分配の例
ジョブをクラスター化して処理するためには，クラスターの適切な大きさを検討す る必要がある．クラスターの大きさが過大であれば，負荷の推定誤差が大きかった場 合に待ちが発生する問題は解消せず，過少であればジョブを1つずつ処理するのと変 わらなくなる．
本方法においては，クラスターの大きさを制御するため，初期レシオIと減少レシ オRというパラメーターを用意した．初期レシオはクラスターの初期サイズを決める ものであり，減少レシオはクラスターのサイズが減少する割合を決めるものである．
ここで，エージェントのジョブの総処理量を正規化したものをWとした場合，Wは 初期値I，公比Rの等比数列の和として表現できるため，IとRとW の関係は下記の ように表すことができる．
W =
∑n
k=1
IRk−1 (6.1)
= I(1−Rn
1−R ) (6.2)
ここで，処理を分担するためのスレッドの数をN と置く．正規化されたジョブの総 処理量Wは各スレッドが処理する計算量の合計と考えることもできるため，スレッド 数Nと置き換えることができる．
この場合，0< R < 1かつn → ∞としたとき，N，R，Iの関係は以下のように記
6.5 ジョブのクラスター化に関する検討
dŚƌĞĂĚϭ dŚƌĞĂĚϮ
dŚƌĞĂĚE
͙͘͘
00000000 00000000 00000000
0000000000 0000000000 0000000000
00000000 00000000 00000000
000000 000
LJĐůĞ ĞŐŝŶ LJĐůĞŶĚ
͙ ͙͘͘
͗džĞĐƵƚŝŶŐŐĞŶƚ:Žď
0000000000000000000000000000 0000000000000000000000000000
0000000000000000000000000000 ͗tĂŝƚŝŶŐƚŽ&ĞƚĐŚ
00000000000000000000000000000 00000000000000000000000000000
00000000000000000000000000000 ͗&ĞƚĐŚŝŶŐŐĞŶƚ:ŽďĨƌŽŵŐĞŶƚDĂŶĂŐĞƌ
ŐĞŶƚ:Žď ůƵƐƚĞƌ
00000000000000000000000000000 00000000000000000000000000000
00000000000000000000000000000 ͗tĂŝƚŝŶŐKƚŚĞƌdŚƌĞĂĚƐ
ŐĞŶƚDĂŶĂŐĞƌ
00000000 00000000 00000000
00000000 00000000 00000000
000000000000 000000000000 000000000000
000000 000000 000000
00000000 00000000 00000000
図 6.7: クラスター化したジョブ分配の例 述できる．
N = I 1
1−R (6.3)
R = N−I
N (6.4)
このとき，RはNとIによって求められるため，スレッド数Nが決まっている場合，
自由に設定できるパラメーターは初期レシオIとなる．この初期レシオをどの程度の 大きさに設定すべきかはMASのエージェント構成及びジョブの負荷変動に依存するた め，事前に設定することは困難であり，適切な初期レシオはシミュレーションの実行 中にも変動すると考えられる．
そこで，本方法では初期レシオIの値をシミュレーション実行中に調整する仕組み を導入した．
初期レシオの決定方法を図6.8に示す．
初期レシオIに比べて小さな値を取る変動値dif f を用意し，シミュレーションの実 行ステップごとに初期レシオIに対して変動値dif f の減少と増加を交互に実施する．
次のステップを実施する場合には，過去10回分について，減少から増加させた場合と 増加から減少させた場合について，どちらがシミュレーション時間が短かったかを調 査し，多数決によって初期レシオIの値を変動させる．
6.
ϭ Ϯ ϯ
ϵ ϭϬ
LJĐůĞƚŝŵĞ
^ŝŵƵůĂƚŝŽŶĐLJĐůĞ dĞŵƉŽƌĂů/ͲƌĂƚŝŽ Ǧ
Ǧ
Ǧ
͙
ĞƚƚĞƌ;ďŝŐŐĞƌǁŝŶƐͿ tŽƌƐĞ;ďŝŐŐĞƌǁŝŶƐͿ ĞƚƚĞƌ;ďŝŐŐĞƌǁŝŶƐͿ ĞƚƚĞƌ;ƐŵĂůůĞƌǁŝŶƐͿ
͙
図 6.8: 初期レシオの決定方法
上記のアルゴリズムによって，その時点でのエージェントの状況に応じた初期レシ オIを維持することを試みた．
6.5.1 テストプログラムによる実験
本方法の効果に関する初期評価を実施するため，テストプログラムを作成し，実験 を行った．実験に利用した計算機の性能等を表6.1に示す．
表 6.1: 実験に利用した計算機 CPU Intel Corei7 4771 3.5 GHz
Memory DDR3 32GB
OS Ubuntu 14.04
Java VM Java7 OpenJDK 7u75
このテストプログラムのために，単純な計算を繰り返すエージェントを用意した．各 エージェントのジョブは乱数を用いた円周率の計算であり，(0,0)から(1,1)の範囲に 乱数によって点を置き，それが1/4円弧に含まれるかどうかによって近似的に円周率 を求めるものである．本テストプログラムは，その試行回数によってエージェントご との負荷の違いを表現する．エージェントの数は1000エージェントとし，負荷は指数 分布によって設定した．エージェントの負荷の分布を図6.9に示す．
6.5 ジョブのクラスター化に関する検討