複数連鎖待ち行列ネットワークに対するマルコフ連鎖モンテカルロ法―――クライアント・サーバモデルの性能評価
数理第五研究室 杉村 由花;

指導教員 杉原 厚吉 教授，松井 知己 教授

2007 年 7 月 30 日
サーバ

1 はじめに
本研究では，複数連鎖待ち行列に対してマルコフ連鎖···モンテカルロ法 (MCMC 法) を適用し，クライアント・サーバモデルの性能評価を行う．
本研究では 2 種類のモデル化を行う．一つめのモデル
図1

は，各連鎖の客数が 1 のモデルである．このモデルにおクライアント・サーバモデルいて，客数 m に対し O(m2 ) の計算時間でシステムの正規化定数が厳密に計算できることを示した．また，システ
ムの定常分布からのサンプリングを CFTP アルゴリズムにより行うため，システムの定常分布と等しい定常分布を持ち，単調性というよい性質を持つマルコフ連鎖 MSを人工的に構成した．MS を用いた CFTP アルゴリズムの性能を調べるため，計算機実験を行った．
二つめのモデルは，各連鎖の客数が一般のモデルであり，パラメータの似通ったジョブを同じ連鎖に属させる．
一つめのモデルにおいて，計算時間は客数 n に依存するが，その一部をパラメータの種類数 m への依存に置き換えることで計算時間の短縮を狙うものである．正規化定

シン i を利用してジョブ j = J(i) ∈ U を走らせているとする．ここで J(i) は利用者 i のジョブの種類を表す．
ジョブ j は対応する部分連鎖 j を持つとする．部分連鎖j は，サーバと対応するノード j を交互に回る部分連鎖である．ジョブ j のサーバにおける平均サービス要求時間は 1/µsj , クライアントにおける平均の思考時間は 1/µcjとする．
一つめのモデルとして，n = m の場合を考える．このとき，利用者 i とそのジョブ j = J(i) は同一視できる．
このとき αj := µcj /µsj とおくと，システムの定常分布は|X|! ∏αj ,GSj∈X∑∏GS =|X|!
αj

数の計算を行うため，サーバに滞在する客数 h を固定す

PS (X) =ることによる定常分布の条件付き分布を考え，それを定常分布に持つ人工的マルコフ連鎖 MhM を構成した．また，MhM の収束が速いことを示した．よって，MhM を用いてMCMC 法を行うことにより，MhM の正規化定数を推定X⊂Uj∈Xと表される．

でき，いくつかの h について MCMC 法を行うことで残二つめのモデルは n > m の場合であり，サーバに滞在りの h についても正規化定数を推定できれば，システムするジョブ数ベクトルを x ∈ Nm とすると，定常分布はれる．

2 準備2.1

クライアント・サーバモデルm
αj jkxk! ∏,GM j=1 xj !(nj − xj )!
x

全体の正規化定数を精度保証つきで推定できると期待さ

PM (x) =GM =∑x∈ΩMm∏x

αj jkxk!
x !(nj − xj )!
j=1 j

図 1 に示すクライアント・サーバモデルを考える．シと表される．なお，kxk = x1 +x2 +· · ·+xm と定義した．

ステムはサーバ 1 台とクライアント n 台を持つものとし，このような形を積形式解と呼び，GS や GM を正規化定

ジョブの集合を U := {1, . . . , m}, クライアントの集合を数と呼ぶ．システムの定常分布が積形式解で表される場

V := {1, . . . , n} とする．利用者 i ∈ V はクライアントマ合，その正規化定数の計算はシステムの性能評価において重要な部分を担う．一例として，正規化定数が計算できれば，ただちにシステムのスループットを計算するこ
サーバ3
クライアント 01とができる．スループットとは，単位時間当たりにシステムが処理を行ったトランザクションあるいはジョブの件数のことを言い，システム効率に関する性能評価指標·········

1 ··· 65 ··· 4i ··· j·········

82mとして用いられている．

2.20 76 3CFTP アルゴリズム

Coupling From The Past (CFTP) アルゴリズムは，

1 65 42 54 5···

6 10 9αi 0 αj 7 : αi 1 αj 6 : αi 2 αj 5 :· · ·: αi 6 αj 1
0!7!6!3! 1!6!5!4! 2!5!4!5!
6!1!0!9!

1996 年に Propp と Wilson によって考案された．このアルゴリズムは確率的に停止し，そのときマルコフ連鎖の図2定常分布に厳密に従うサンプルを返す．

マルコフ連鎖 MhM

標準 CFTP アルゴリズムは停止したとき，マルコフ連鎖の定常分布に厳密に従って状態を出力する．しかしこの標準アルゴリズムでは状態空間中のすべての状態に対して操作を行わねばならず，現実的に実行が困難である．ただし，マルコフ連鎖 M : x 7→ x0 の更新関数表現

x0 = φ(x, Λ) (Λ ∈ [0, 1), 一様乱数) が以下に定義する単調性を持つとき，最大元および最小元に対してのみ操作を行えばよく，現実的に実行可能となる．
定義 1 (単調な更新関数). 状態空間 Ω 中に半順序関係“º” が存在し，「唯一の最大元 xmax および唯一の最小3.3

CFTP アルゴリズムの実行時間の指標となる coalescence time T∗ について，その期待値を計算機実験によって計測した．E[T∗ ] はデータの範囲内では m に対し指数関数的に増大することはなく，O(m1.5 ) 程度で押さえられると予想されるが，αj の値にも依存し必ずしも両対数グラフ上できれいな直線には載らない．

4 各連鎖の客数が一般のクライアント・サー
バモデル

元 xmin が存在」し，かつ「任意の推移は半順序を保存する．すなわち，任意の x º y なる x, y ∈ Ω について，計算機実験

正規化定数 GM を求めるため，φ(x, λ) º φ(y, λ) が成り立つ」とき，φ は単調な更新関数であるという．

GM =3 各連鎖の客数が 1 のクライアント・サーバ

GhM =正規化定数の計算法

正規化定数の計算は，変数 x を持つ多項式 (x + α1 )(x +α2 ) · · · (x + αm ) を展開することで，客の人数 m に対し2O(m ) の時間複雑度で行うことができる．
3.2

定常分布からの完璧サンプリング法の構成

更新関数 φS によって表されるマルコフ連鎖 MS を，以下のように新たに構成する．
更新関数 φS : 2U × U × [0, 1) → 2U を{X ∪ {j} (λ < θjX )φS (X, j, λ) =X \ {j} (otherwise)

h!GhM ,h=0m∑ ∏kxk=hモデル
3.1n∑x

αj jx !(nj − xj )!
j=1 jと分解して，GhM (h = 0, 1, . . . , n) を求めることにする．
そのため，各 h について，もとのネットワークの定常分布に対してサーバに滞在するジョブ数が h であるという条件付き分布を定常分布に持つマルコフ連鎖 Mh
M を構成
し，MhM の定常分布からの近似サンプリングを行う．

4.1

マルコフ連鎖の構成

マルコフ連鎖 Mh
M は，一様ランダムに選ばれたジョブi, j についてのみ，サーバに滞在するジョブ数を変更するものである．その際，xi + xj は一定に保たれる．概要を
図 2 に示す．

4.2

Mixing time

以下の命題を示した．なお，mixing time τ (ε) は，マ|X∪{j}|αjとする．これにと定義する．なお，θjX := |X∪{j}|αj +10よりマルコフ連鎖 MS : X 7→ X を，それぞれ独立に一様ランダムに選んだ j ∈ U および Λ ∈ [0, 1) によってX 0 = φS (X, j, Λ) と定義する．MS の定常分布はシステ
ムの定常分布に等しい．
本研究では，φS が単調性を持つことを示した．

ルコフ連鎖モンテカルロ法において，定常分布からの誤差が ε となるのにかかる推移回数を意味する．
h
命題 2. マルコフ連鎖 Mh
M の mixing time τM (ε) は，hτM(ε) ≤ m(m−1)
ln nε をみたす．
2