私の研究には、確率が関係するもの、最適化が関係するもの、確率と最適化の 両方が関係するものがあります。以下では、2008年ごろまでの研究テーマである 「確率モデルを用いた性能の最適化」「確率モデルを用いた性能の解析」 「最適化アルゴリズム」について簡単に紹介します。
確率モデルを用いた性能の解析（ウェブシステムを例に）
主に2005年から、確率モデルを用いた性能の最適化の研究をしています。
ウェブシステムなどのコンピュータシステムや、コールセンターなどのサービ スシステムは不確定な入力を伴うシステム、すなわち確率モデル、と考えるこ とができます。例えば、ウェブシステムに対しては、ユーザーがウェブページ (サービス)をリクエストしますが、どのウェブページをリクエストするか、ま たどのタイミングでリクエストするかは予め知ることはできません。しかし過 去の履歴などから、各ウェブページをリクエストする確率や、どのくらいの頻 度やばらつきでリクエストがあるか(すなわちリクエストの確率過程)を推定す ることができます。まず、ウェブシステムを例として、確率モデルにおける 性能の最適化の研究の目的を紹介します。
どのようにリクエストがあるか(リクエストの確率過程)によって、ウェブシス
テムの性能(例えばリクエストを処理するのに要する時間、すなわち応答時間)は大きく変
わってきます。したがって、ウェブシステムの性能を知るには、
1. リクエストの確率過程を推定する
2. 推定された確率過程に従って、リクエストを生成する
3. 生成されたリクエストをウェブサーバに与え、その応答時間を測定する
ことが必要になります。
ウェブシステムの性能を測定する目的のひとつに、性能を最大にするような最 適な構成を見出すことがあげられます。例えばウェブシステムには「最大接続 数」、「初期ヒープ・サイズ」、「最大ヒープ・サイズ」、「最大スレッド・ サイズ」、「最大プール・サイズ」などの構成パラメータがありますが、これ らの構成パラメータの値によってウェブシステムの性能は大きく異なり、また 性能を最大にするような構成パラメータの最適値はどのようにリクエストがあ るか(リクエストの確率過程)によって大きく異なってきます。
推定されたリクエストの確率過程のもとで、平均応答時間を最短にするウェブ システムの構成(構成パラメータの値)を求める問題を考えます。原理的には、 全ての可能な構成パラメータの値の組み合わせについて、その平均応答時間を 測定し、平均応答時間の測定値が最短となる構成パラメータの値を見つけるこ とで、最適なウェブシステムの構成が見つかりそうです。ところが、平均の応 答時間を精度良く測定しようとすると、30分くらいの時間が必要になります。 また、構成パラメータが「最大接続数」、「初期ヒープ・サイズ」、「最大ヒー プ・サイズ」、「最大スレッド・サイズ」、「最大プール・サイズ」の5つだ けで、それぞれ「大」「中」「小」の3つの値しかとりえないとしても、3^5 = 243通りの構成が考えられます。これら243通りの構成全てについて、30分間 かけて平均の応答時間を測定しようとすると、243 x 30分 = 5日も要してしまいます。 実際のウェブシステムにおいては、より多くの構成パラメータがあるので、 全てのウェブシステムの構成について性能を精度良く測定することは 現実には不可能であることが用意に想像できるでしょう。
確率モデルにおける性能の最適化のプロジェクトにおいては、
ウェブシステムのように、
1. 性能を精度良く測定するのに時間がかかる
2. 多数の構成があり、構成によって性能が大きく変わる
ような性質を持つシステムにおいて、性能を最大にする構成(最適な構成を)高速に
見つけるための手法を研究しています。
目標の一つは、専門家が最適化したウェブサーバの構成よりも良い構成をより 高速に自動的に見つけることです。現在は、専門家が経験と知識そして試行錯 誤によって、ウェブサーバの構成を最適化しています。単に自動化しただけで は、豊富な経験と知識を持つ専門家が見つけるような構成を、自動的に発見す ることはできません。どの構成をどの順番でどのくらいの時間測定するかの 指針を科学的に与えることで、専門家の職人技を凌駕することを目指します。
確率モデルにおける性能の最適化はウェブシステムに限らず、 その他のコンピュータシステム、コールセンターなどのサービスシステム の性能の最適化に広く応用が考えられます。
まず候補となる243通りのシステム構成の中から最も高性能なシステム構成を 選択する問題を考えてみます。複雑なウェブシステムなどではもっと多くのシ ステム構成が考えられますが、ここでは簡単のために比較的数が少ない場合に ついて考えます。
これだけ候補となるシステム構成が少なくても、それぞれのシステム構成の性 能を30分間かけて高い精度で測定しようとすると、243x30分=5日もかかってし まいます。もっと短い時間しか使えなければ、測定時間を短くするか、一部の システム構成だけしか測定しないことが考えられます。しかし、測定時間を短 くすると、精度が低くなってしまい、誤った選択をしてしまいます。また、一 部のシステム構成だけしか測定しないと、最適なシステム構成が測定されず、 最適なシステム構成として選択されないことがあります。
私たちのアルゴリズムは、全てのシステム構成を測定するけど、どれも高精度 で測定するわけではなく、それぞれのシステム構成を最低限の精度で測定する、 というものです。例えば、極めて性能の悪いシステム構成であれば15分程度測 定した段階で、最適なシステム構成ではないと精確に判定できるかもしれませ ん。15 分程度ではその性能は精確に測定できていませんが、「最適なシステ ム構成ではない」という判定は精確にできるということです。この原理を最大 限に利用して、それぞれの性能は精確に測定しないけれども、精確に短時間で 最適なシステム構成を選択するアルゴリズムができます。
このアルゴリズムで重要になるのは、どのような基準で「最適なシステム構成 ではない」と判定するかです。できるだけ測定時間が短くなるように、かつ誤っ た判定をしないように基準を設けることが必要です。私たちのアルゴリズムで はその基準に図のような三角形を使います。これまでに測定されたシステム構 成の中で最も性能が良かったシステム構成の性能の測定値と、現在測定してい るシステム構成の性能の測定値の差を比較していきます。図の赤い折れ線はそ の測定値の差を縦軸に、測定時間を横軸にして示してあります。
性能の差が三角形の中にある限り測定を続け、性能の差が三角形の外に出たと きに、2つのシステム構成の性能の良し悪しを判定します。三角形の上の方に 性能の差のグラフが出て行ったときには、現在測定しているシステム構成のほ うが性能値が大きいと判定します。例えば、性能値がスループットを表してい るなら、現在測定しているシステム構成のほうがこれまでに最も性能が良かっ たシステム構成よりも性能が良いと判定されます。反対に、三角形の下の方に 性能の差のグラフが出て行ったときには、現在測定しているシステム構成のほ うが性能値が小さいと判定します。
三角形を用いることによって、必要十分な測定精度が得られたときに性能の良 し悪しを判定できます。すなわち、測定時間が短いときには測定値の精度が低 いので、性能の測定値の差が大きくないと性能の良し悪しを判定しません。長 い間測定を続けるにしたがって測定値の精度が上がるので、性能の測定値の差 が小さくても性能の良し悪しを判定するようになります。
残された問題はどのように三角形のサイズを決めるかです。三角形のサイズが 大きすぎると、性能の良し悪しの判定に時間がかかってしまい、三角形のサイ ズが小さすぎると、誤った判定をしてしまいます。私たちのアルゴリズムでは、 ブラウン運動と正規分布の性質を解析することによって、最適な三角形のサイ ズを求めています。
発表論文
確率モデルを用いた性能の解析（タスク割り当てを例に）
主に2001年から、確率モデルを用いた性能の解析手法とそのコンピュータシス テムやサービスシステム の性能解析への応用に関する研究をしています。研 究成果の多くは、米国カーネギーメロン大学計算機科学科に留学中のもので、 博士論文[THESIS05]にまとめられています。
ここでは、博士論文の中の研究の一部を簡単に紹介したいと思います。
例として、スーパーマーケットで買い物を終えたお客様にどのレジに並んでも らうと良いかを考えてみましょう。簡単のためにレジは2つだけあり、誰も並 んでいなければどちらのレジで精算しても同じだけの時間がかかるとします。 目標は平均の待ち時間ができるだけ短くなるような並び方のルールを考えるこ とです。どのようなルールが良いと思いますか？
まず思いつくルールは「並んでいる人の少ないレジに並んでもらう」ではない でしょうか？このルールをShortest Queueと呼ぶことにします。一見すると Shortest Queueは非常にうまいルールのような気がします。実際にレジでの精 算にかかる時間がどの人もまったく同じであれば、Shortest Queueはほぼ最適 なルールであることが示せます。ところが実際にはたくさん買い物をした人も いれば、少ししか買っていない人もいて、精算にかかる時間は違ってきます。 同じ3人が並んでいても、1週間分の買い物をした3人が並んでいるレジと、 牛乳だけを買った人が3人並んでいるレジでは、待ち時間が大きく異なってきます。
そこで思いつくルールは「並ぶ時間が短い方のレジに並んでもらう」ではない でしょうか？このルールをLeast Remaining Workと呼ぶことにします。現実の スーパーマーケットでは並ぶ時間を正確に知ることは難しいので、Least Remaining Workに厳密に従うことはできないかもしれません。しかし、もし待ち 時間を厳密に知ることができたとしたら、Least Remaining Workに従うべ きでしょうか？一人一人のお客様の視点から見るとLeast Remaining Workにし たがって並ぶのが最適なように思われます。確かにLeast Remaining Workに従 わなかったお客様は、Least Remaining Workに従った場合に比べて長く待たな ければなりません。ところが、全てのお客様の待ち時間の平均を考えた場合に はLeast Remaining Workは最適なルールではありません。それどころか、 Least Remaining Workにおける平均の待ち時間が最適なルールに比べて無限に 長くなることがありえるのです。
Least Remaining Workの最大の問題点は、1週間分の買い物をした2人のお客様 が2つのレジを長い時間占有してしまい、そのあとに牛乳だけを買いたい大多 数のお客様がたくさん並んでしまう様な状況になりえることです。日本のスー パーマーケットでは一度に大量に購入する人はそれほどいないかもしれません が、アメリカのスーパーマーケットでは巨大なカートに山ほど買い物をする人 をよく見かけます。全てのレジで山ほど買い物をしたお客様の精算をしている と、その後には長い行列ができてしまいます。牛乳を一本だけ買いたくても何 十分と並ぶ必要がでてきます。
Least Remaining Workの問題点を解決するルールのひとつに、「たく さん買うお客様に一方のレジに並んでもらい、あまり買わないお客様 に他方のレジに並んでもらう」というのが考えられます。このルールを Dedicatedと呼ぶことにします。例えば、買う商品の数が20個以上のお客様に は一方のレジに並んでもらい、20個未満のお客様には他方のレジに並んでもら うようにします。Dedicatedにおいては、20個以上買う少数のお客様のあとに 20個未満しか買わない大多数のお客様が長い列を成して待つような状況がなく なります。実際に、精算にかかる時間のばらつきが大きいときには、 Dedicated に従ったときの平均の待ち時間はLeast Remaining Workに従ったと きの平均の待ち時間に比べてはるかに短くなることが示せます。 ところがDedicatedも最適なルールではありません。Dedicatedの問題点は、 20個未満しか購入していないお客様がたくさん並んでいるにもかかわらず、 他方のレジでは誰も精算をしていないという状況がありえることです。
Dedicatedの問題点を解決するルールのひとつに、「たくさん買うお客様に 一方のレジ（レジ１）に並んでもらい、あまり買わないお客様に他方のレ ジ（レジ２）に並んでもらう。ただし、レジ１に誰も並んでいないときにあま り買わないお客様が精算のために並ぼうとするときには、レジ１に並んで もらう。」というのが考えられます。このルールをCycle Stealingと呼ぶこと にします。Cycle StealingはDedicatedの問題点を解決し、かつたくさん買う 少数のお客様のあとにあまり買わない大多数のお客様が長い列を成して待つよ うな状況がないので、Least Remaining Workのような問題点もありません。
Cycle Stealingよりも良いルールは存在するでしょうか？存在するとしたら最 適なルールはどのようなルールなのでしょうか？これらの問いに対する回答は いくらかありますが、まだ完全な答えは分かっていません。もう少し研究が進 んだら紹介したいと思います。ただし次のようなルールは望ましくないことに 注意してください。「たくさん買うお客様に一方のレジ（レジ１）に並んでも らい、あまり買わないお客様に他方のレジ（レジ２）に並んでもらう。ただし、 レジ１に誰も並んでいないときにあまり買わないお客様が精算のために並ぼう とするときには、レジ１に並んでもらう。また、レジ２に誰も並んでいないと きにたくさん買うお客様が精算のために並ぼうとするときには、レジ２に並ん でもらう。」このルールを2-way Cycle Stealing と呼ぶことします。2-way Cycle Stealingがなぜ望ましくないかはもうお分かりでしょうか。2-way Cycle Stealingにおいては、両方のレジにたくさん買うお客様が並んでしまう ことがあります。そうなると、そのあとに多くのあまり買わないお客様が ならんでしまい、これはLeast Remaining Workの問題点でもありました。
ここまでCycle Stealingにおける平均の待ち時間は、Shortest Queue, Least Remaining Work, Dedicatedなどに比べてずっと短いということを、言葉で直 感的に説明してきました。本当にCycle Stealingにおける平均の待ち時間は短 いのでしょうか？どんな場合でも平均の待ち時間が短いのでしょうか？そうで ないとしたら、どのような場合に平均の待ち時間が短いのでしょうか？このよ うな疑問に答えるためには、Cycle Stealingやその他のルールに従ったときの 平均の待ち時間を求めることが必要になります。現実のスーパーマーケットで 実験をしても良いですし、コンピューター上でシミュレーションをしても良いで しょう。しかし、実験やシミュレーションによって、正確に平均の待ち時間を 求めようとすると、非常に時間がかかってしまうために、限られた状況におい てしかCycle Stealingと他のルールの比較ができません。解析的に数学を使って 平均の待ち時間を求めることができれば、様々な状況における比較が可能となり、 結果的により多くの知見を得ることができるでしょう。
「確率モデルにおける性能の解析」の研究では、単にCycle Stealingのような ルールを考えるだけではなく、そのルールの性能、例えば平均の待ち時間がど れくらいになるかを解析する手法についても考えます。性能を解析するには、 まず厳密にモデルを定義する必要があります。お客様が買い物をしてレジにやっ てくる確率過程、レジで精算にかかる時間の確率分布などを過去の履歴などか ら推定して、それらの確率過程、確率分布のもとで平均の待ち時間を解析しま す。（このあたりから専門的になります。博士論文[THESIS05]ではもう少し分 かりやすく解説していますので参照してください。）一般に解析は非常に困難 であるため、確率過程はMarkovian Arrival Process (MAP)、確率分布は Phase-type distribution (PH 分布)で近似します。こうすると、平均の待ち 時間はMarkov chainを解析することで求めることができるようになります。 MAPはどんな確率過程でも任意の精度で近似でき、PH分布はどんな確率分布で も任意の精度で近似できますが、精度を上げると解析時間により長い時間がか かってしまいます。またCycle Stealingのようなモデルでは得られるMarkov chainは多次元に巨大な状態空間を持ち、通常の解析手法ではうまく解析でき ません。そこで、Markov chainの状態空間の次元をうまく下げてあげて効率的 に解析できるようにしました。詳細は論文[SPAA03]や博士論文[THESIS05]を参 照してください。
発表論文
最適化アルゴリズム
主に1998年から2001年までは、組み合わせ最適化アルゴリズムを研究してきま した。組み合わせ最適化アルゴリズムはは非常に多くの解の候補の中から最適 な解を高速に発見する手法です。その研究成果は、病院における看護師さんの 最適勤務スケジュールの自動作成や、製鉄所における最適在庫充当などに応用 しました。
最適化技術の詳細については、 プロジェクトのページをご覧ください。
発表論文