メモリ資源のある計算機システムの待ち行列網による近似性能評価法の提案と評価

全文

(1)Vol.2010-MPS-79 No.4 2010/7/12. 情報処理学会研究報告

(2) $. & * & &

(3) .

(4) *

(5)

(6) () +

(7) &. ,-.

(8) & ""#

(9) &

(10) ""#. メモリ資源のある計算機システムの待ち行列網による近似性能評価法の提案と評価.

(11) & )# ()$. .# & &

(12) *

(13).

(14) ") !

(15) !

(16) &

(17) + "

(18) #

(19) '

(20) !"

(21) "

(22) ! $. %

(23)

(24) &.

(25) + "

(26) "

(27) + " $. 木下. 俊之. Ý. 高. . 秀. 梅Ý. はじめに計算機システムを性能評価する有効な方法のひとつに，待ち行列網による方法がある．本論文では，待ち行列網を用いてメモリ資源のある計算機システムを性能評価する近似法について述べる．ジョブは外部からシステムに到着するとメモリのひとつを占有し，メモリを占有しながら処理や入出力処理を実行する．ジョブが処理や入出力処理を完了すると，メモリを解放してシステムを出ていく．メモリはや入出力装置に対して２次資源と考えられ，かつメモリ資源のある計算機システムの待ち行列網は開モデルであり，積形解を持たないため厳密解を求めることはできない．近似の考え方は，対象とする計算機システムを処理や入出力処理を実行する処理部と，ジョブがメモリをどう使うかを評価するメモリ部に分けて解析する．待ち行列網を２つの部分に分割することにより，網の状態数が増大して数値計算を実行できなくなることを防ぐことができる．数値実験により，提案した近似法の有効性を評価した．. 計算機システムの性能を評価する手法のひとつに，待ち行列網を用いる方法がある．計算機の中には複数のジョブが存在し，ハードウェアやソフトウェアなどの資源を取り合うことにより待ちが発生している．この待ちを待ち行列網を用いて評価し，ハードウェアの利用率やジョブの応答時間などの性能指標を求める方法である．待ち行列網のうち，ある条件を満たすものは積形解と呼ばれる明示的な解を持つ．この積形解を用いれば，性能指標を容易に計算することができる．しかし資源を競合に排他制御を行う場合やメモリ資源を扱う場合などには，網は積形解を持たない．積形解を持たない待ち行列網の厳密解を求めるためには，待ち行列網の確率的な特徴を記述するマルコフ連鎖の平衡方程式を数値的に解く必要がある．この平衡方程式は，網の状態数と同数の未知数を持つ連立１次方程式になる．一般に.

(28) .

(29). . 計算機システムをモデル化した待ち行列網の状態数は，. が増大し，これ解くための数値計算が実行できなくなるという問題点を含んでいる．また，網が外部との出入りのある開モデルの場合の状態数は無数であり（システム内のジョブ数は無限大まで大きくなり得る），平衡方程式を数値的に解くことは事実上不可能である．.

(30) . 本研究ではメモリ資源のある計算機システムを考える．ジョブは外部から網に到着するとメモリのひとつを占有し，これを占有しながら. !

(31)

(32) !"

(33) !. が. " ""# $ %

(34) ()

(35) !" & * . より，メモリは. ,- . 処理や処理を実行する．ジョブ. 処理や処理を完了すると占有していたメモリを解放し，網を出ていく．これや入出力装置に対して次資源と考えることができる．待ち行列網が. " #"$ % & ! " #' ! ""# *

(36) & +

(37) &. や装置数，システム内の. ジョブ数が大きくなると指数関数的に増大する．このため連立１次方程式の未知数の個数. 次資源を含むときは積形解を持たない．そしてメモリ資源のある待ち行列網は外部との出. # ""#$ % () "

(38) & , *

(39) ""#

(40) &

(41) $ ""#. 入りのある開モデルのため，積形解を持たない場合は厳密解を求めることはできない．そこ. &&

(42)

(43) &

(44) # !

(45) & ,- " *

(46) & "& ! " #" ""#

(47) *

(48).

(49)

(50) $. Ý 東京工科大学大学院コンピュータサイエンス専攻.

(51) *

(52)

(53) + "

(54) !

(55)

(56) .

(57)

(58)

(59)

(60)

(61)

(62)

(63)

(64)

(65) . !"

(66) "

(67) ! " #" ""# . . . /00 !"

(68) # !

(69)

(70).

(71) Vol.2010-MPS-79 No.4 2010/7/12. 情報処理学会研究報告

(72) . p1. memory. CPU. …. . p2. pM. このセントラルサーバモデルにメモリ資源を付加する（図）．メモリ数を. で表す．ジョ. . I/O1. ブは外部から到着率. 2. . I/OM. でランダムに到着し，処理部に入る前にメモリ資源の一つを要求す. に等しいことを意味する．処理部にいるジョブを

(73) で表す．. ジョブの .

(74)

(75)

(76) . から外部への遷移をからへの遷移に置き換えることに. よって，処理部をジョブ数が一定の閉セントラルサーバモデルに変更することができる．この閉モデルでは，. からへの遷移が起きた場合は，そのジョブは終了して新しいジョブが生成したと考える．ゆえにジョブの平均応答時間は，引き続くつのからへの遷移間の平均時間間隔になる．このジョブの平均応答時間は，ジョブの生存. 方は，網を記述するマルコフ連鎖の状態数が増大して数値計算を実行できなくなることを防. 処理や処理を実行する処理部とメモリ資源の占有，解放を記述するメモリ部に分けて解析する．このつの部分はともに積形解を持つので，容易に定常確ぐため，. 時間と考えることができる．. 近似の考え方. 率を求めることができ，後で両者を結合して全体の性能指標を計算するという方法である．. ，装置など）と次資源（メモリ資源）. メモリ資源のある待ち行列網の厳密解を得るためには，網全体をひとつのマルコフ連鎖で. に分割してモデル化する方法は，階層型持ち行列の手法である．本研究は，階層型待ち. 記述する必要がる．しかしこの方法は網のノード数やジョブ数が増大した場合に，マルコフ. 連鎖の状態数の劇的な増加を引き起こす．そこで待ち行列網を処理部とメモリ部のつの部. 行列をメモリ資源のある待ち行列網に応用したひとつの応用例と考えることができる．. モデルの記述. 分に分割し，それぞれをマルコフ連鎖で記述することにより，網の状態数の増加を防ぐことができる（図）．以下，次の記号を用いる．. ，処理が実行される部分）は，従来のセントラルサーバモデルと同一で，個のノードと複数のノードからなる．ノード数をで表し，ノードはからまで添え字で番号付けられる．

(77) のときはノードを表すものとする．ノードでのサービス率を，ノードでモデルを分割したうちの処理部（. . である）．. いるジョブ数は処理部のジョブ数と同数である．このことは処理部の最大ジョブ多重度がメ. で本研究では，メモリ資源を持つ待ち行列網の解を求める近似手法を提案する．近似の考え. のサービス率を. . 処理や処理を実行し，処理や処理を完了するとメモリを解放して網から離れる．ジョブは処理部に入るときに必ずメモリをつ獲得するので，メモリを獲得して. M. メモリ資源のあるセントラルサーバモデル. このように対象のシステムを次資源（. . 待ち行列に入ってメモリが解放されるのを待つ．ジョブはメモリを占有しながら処理部で. モリ数図. . る．ジョブがメモリを要求したときにすべてのメモリが占有されていれば，ジョブはメモリ. I/O2 …. S. とし，処理. の完了確率をとする（従って. 1. 0. 1 2. の選択確率を . るかを，確率的に選択する．ノード. 0p0. p0. ジョブの生存中にノードで受ける総サービス時間

(78) ノードのジョブ数

(79) 処理部の状態ベクトル

(80)

(81) 処理部のジョブ数がのときの処理部の可能なすべての状態の集合状態の定常確率. とする．あるノードでのサービス時間は共通の指数分布に従う互いに. 独立な確率変数で，他のノードでのサービス時間とも独立である．すべてのノードでジョブ. （）規律でスケジュールされる．ジョブはノードでの処理終了時に，次にいずれのノードに進むか，または処理を完了して網から離れは. /. . /00 !"

(82) # !

(83)

(84).


(86) . モデルはサービス中の客数によってサービス率が変化すのときの処理部でのジョブの平均応答時間は，. メモリの平均占有時間に等しい．ゆえに処理部の完了率はと表されるので，は占有されているメモリ数に依存して変化する．図に，メモリを占有しているジョブ数に応じてサービス率が変化する待ち行列モデルの状態遷移を示す．これは拡張された生成死滅過程である．メモリを占有しているジョブ数がのときの定常確率は，次のように表される．

(87) 変であるが、メモリ部の. memory 1 2. p1. p0 0. …. . 1 I/O1. I/O2. pM Memory part. …. …. …. S. 0p0. 2. p2. CPU. るモデルを考える。処理部のジョブ数が. M. I/OM. Processing part 図. . 近似の考え方.

(88)

(89)

(90)

(91) . .

(92)

(93) . これらの方程式を解いて，次のような積形解が得られる． Ȝ 0. Ȟ1. Ȝ 1. …. 2Ȟ2 図. . Ȝ n Ȟn. Ȝ n. …. Ȝ. (n +1) Ȟn +1 S ȞS. Ȝ S. S ȞS. モデルの状態遷移

(94)

(95)

(96) " . Ȝ S +1. …. S ȞS. . サービス率が可変の. !. . . 式とをに代入すると，次の結果が得られる．.

(97) .

(98) .

(99) . この処理部は従来のセントラルサーバモデルと等価なので，処理部を記述するマルコフ連鎖は積形解を持つ．その処理部の定常確率. .

(100) ここで

(101) . ¾ . . は次式で求められる．. . .

(102)

(103)

(104)

(105)

(106)

(107)

(108)

(109) .

(110)

(111) .

(112)

(113)

(114)

(115) .

(116)

(117)

(118)

(119) . は，処理部のジョブ数がのときの定常確率の正規化. 定数である．この定常確率を用いて，処理部のジョブ数が. . のときの処理部でのジョブの. は，次の式で求められる．.

(120)

(121) 次にメモリ部は，窓口数が個の待ち行列モデルであると考える．ただし通常の待ち行列モデルでは、サービス中の客数に関わらず窓口でのサービス率は不. 平均応答時間. 1. . . /00 !"

(122) # !

(123)

(124).


(126) . 処理部のジョブ数がのときの処理部のジョブの平均応答時間を定常確率

(127) で重み付けて平均することにより，処理部でのジョブの平均応答時間が求められる．またにより直接に平均メモリ待ち時間が求められるので，このつ加えること. が大きくなるにつれて，最小のの場合の値から最大のの場合のにつれて最小のの場合の値から最大のの場合の値まで増加するが，が小さい範囲では最小の場合と漸近的に同様の振る舞いを示し，が大きくなって上限に近い範囲では最大の場合と漸近的に同様の振る舞いを示すことが分かる．図 ! に，メモリ資源数が ! " のときのシステム全体の平均応答時間を示す．が増加するにつれてシステムは，到着率. 値まで近似的に直線的に増加する．一方，システム全体の平均応答時間も，が大きくなる. によりシステム全体のジョブの平均応答時間を求めることができる．提案する近似法のアルゴリズムは，次のようにまとめられる．. . 処理部の閉セントラルサーバモデルの積形解を用いて，処理部のジョブ数がのときの処理部でのジョブの平均応答時間. を求める．. 全体の平均応答時間は短くなり，システムの許容量は大きくなっている．. 式により、処理部のジョブ数がのときのメモリ部の定常確率を. まとめ. 求める．. . により平均メモリ待ち時間を求め，これと処理部でのジョブの平均応答. メモリ資源を持つ計算機システムを待ち行列網で性能評価するための近似法を提案し，数. 時間を加えて，システム全体のジョブの平均応答時間を求める．. 値実験によりその評価の特性を解析した．近似の考え方は，. 処理や処理を解析す. 数値実験. る処理部とメモリの使われ方を解析するメモリ部に分割するという方法である．処理部は従. 提案した近似法を評価するために、数値実験を行った。使用したパラメータは次の通りで. るジョブ数によって完了率が変化する. 来の閉のセントラルサーバモデルの積形解を用いて解析し，メモリ部はメモリを占有してい. ある。. メモリ資源数 ! " 到着率

(128)

(129)

(130)

(131)

(132)

(133) "

(134)

(135) # ノード数ジョブの各ノードでのサービス率

(136)

(137) $ $ サービス終了後の次ノードの選択確率 # #. 向を示し，到着率が上限に近い範囲ではジョブ数が最大の場合と同等の傾向を示すことが確かめられた．今後は，厳密解またはシミュレーションによる値と比較することにより，提案手法の近似精度を調べることが必要である．. 参. 図，$ に，メモリ資源数. が. のときの処理部の平均応答時間とシステム全体の平均応. 答時間をそれぞれ示す．比較のために，処理部のジョブ数が最小のと，最大の. . 考. 文. 献. %&' ( ) *&+, - - ).+/ &+ 0 &1&2. 3+ 1 &+ )4 56' 7 8.. 6* 9:+ 1& 7 . ; < ) =1 5 33 ">!

(138) <31 #?$ @ (A&,&* )1+B &+ <+&1, <+CD1, .A1*+B 3&+, +2 #?" E (.&.B &+ (+ <334&+ )* 7 E6C1&, 8..+B )C 1 7&+2 F&1.&+ !>? 33 $$>?

(139) ### ; < -1& &+ ( 2' E* )* 7 G&, FFF E&+ + 76& F+B++B =1 5 " 33 !"#>?

(140)

(141) <.B ##$ $ E (+*& &+ H E&'&*&* < 8..+B 56' )1+B &+ 7&+2 F&1.&+ )* 7 3. , 6* -.2 -I.+ F F 9C =1 ; "C9C 5 ! 33 ?

(142) >?

(143) ;.+ ###. 従って各ノードでの総サービス時間は，次のようになる．. #

(144). "

(145). "

(146). 待ち行列モデルを用いて解析する．. 数値実験により，到着率が小さい範囲では処理部の負荷が最小の場合と漸近的に同等の傾. と仮定した場合. とした場合の処理部の平均応答時間を併記した．処理部の平均応答時間. 2. . /00 !"

(147) # !

(148)

(149).

(150) Vol.2010-MPS-79 No.4 2010/7/12. 情報処理学会研究報告. Mean Job Response Time.

(151) . 60. ! E (+*& &+ H E&'&*&* <+ <334& )* A, 8..+B 56' )1+B 7 7&+2 F&1.&+ 7 3. , 6* F421.1,C. -.2 ; =1 5 0 E)$ 33 > 92

(152)

(153) ? E (+*& 8..+B 56' )1 7 <+&1,/+B +J.+2 7 F421.1, -.2 + 7&+2 7 3. , 2+B 7 9E<

(154)

(155) 33 # >#? ;.+

(156)

(157) " E (+*& <334& E2*+I. 7 8..+B 56' 7 F&1.&+B C 7&+2 7 3. , 6* &11 -& 7 -.2 -I.+ C 2+B 7 9E<

(158)

(159) $ 33

(160) > ! ;.+

(161)

(162) $ # E @&. K 0& &+ E (+*& <+ <334&+ 8..+B 56' E2*C +I. 7 F&1.&+B 7&+2 7 3. , 6* -.2 -I.C + 2+B 7 9E<

(163)

(164) # 33 !#

(165) >!#! ;.1,

(166)

(167) #. Max.. 50 40. Appr.. 30 20. Min.. 10 0 0. 0.02. 0.04. 0.06. 0.08. 0.1. Arrival Rate. . 図処理部の平均応答時間（ # $） $ % &

(168) '

(169)

(170) ( #$). . Mean Job Response Time. 250 200 150. Max.. 100 Appr. 50. Min.. 0 0. 0.02. 0.04. 0.06. 0.08. 0.1. Arrival Rate. . メモリ待ちを含むシステム全体の平均応答時間（ # $） * % &

(171) '

(172) ( #$). Mean Job Response Time. 図. 250 S=2. 200. S=4. S=6 S=8. 150 100 50 0 0. 0.02. 0.04. 0.06. 0.08. 0.1. Arrival Rate. . 図メモリ待ちを含むシステム全体の平均応答時間（ # $ + ,） + % &

(173) '

(174) ( # $ + ,). 3. . /00 !"

(175) # !

(176)

(177).

(178)