(57)【要約】  システム性能を最適化するシステムおよび方法は、サンプリングベースの最適化を適用して、いくつかの構成サンプルを選択すること（１６２）および該サンプルに基づいてシステム性能を評価すること（１６６）によって、コンピューティングシステムの最適構成を特定すること（１６０）を含んでいる。評価されたサンプルのフィードバックに基づいて、最適構成のロケーションが推測される（１７０）。追加サンプルを推測された最適構成のロケーションの方へ生成し、システム構成をさらに最適化する（１７６）。【選択図】図５
2011504254.tif 000002
【特許請求の範囲】
【請求項１】
システム性能を最適化する方法であって、
いくつかの構成サンプルを選択すること（１６２）、
前記サンプルに基づいてシステム性能を評価すること（１６６）、
評価されたサンプルのフィードバックに基づいて、最適構成のロケーションを推測すること（１７０）、
追加サンプルを前記推測された最適構成のロケーションの方へ生成し、システム構成をさらに最適化すること（１７６）、
によって、サンプリングベースの最適化を適用してコンピューティングシステムの最適構成を特定すること（１６０）、
を含む方法。
【請求項２】
前記いくつかの構成サンプルを選択すること（１６２）は、大域的範囲のサンプルおよび局所構造を考慮して配置空間内のサンプル数を決定することを含む、請求項１に記載の方法。
【請求項３】
前記いくつかの構成サンプルを選択すること（１６２）は、複数の構成パラメータを用いる分散確率ベースのアクティブサンプリング（ＤＰＡＳ）法を実行すること（１６３）を含む、請求項１に記載の方法。
【請求項４】
前記ＤＰＡＳ法は、過去のサンプルからの経験を利用したサンプリング戦略を含み、前記方法は、前記過去のサンプルからの履歴データに基づいて、新たなサンプルを生成する確率を作り出すこと（１６４）をさらに含む、請求項３に記載の方法。
【請求項５】
前記確率を作り出すこと（１６４）は、報酬−ペナルティ戦略が探索プロセスを最適設定の方へ導くように、該報酬−ペナルティ戦略に基づいて、各評価されたサンプルを動的に更新することを含む、請求項３に記載の方法。
【請求項６】
サンプリングを、各モジュールが特定の構成パラメータを探索する責任を負う１群の個別のモジュールに分解すること（１６５）をさらに含む、請求項１に記載の方法。
【請求項７】
前記システム性能を評価することは、受け入れ可能なシステム性能の定義を許容するために複数の性能次元を同時に組み込むこと（１６８）を含む、請求項１に記載の方法。
【請求項８】
前記評価されたサンプルのフィードバックに基づいて、最適構成のロケーションを推測すること（１７０）は、
一連のパラメータをいくつかのビンに分割すること（１７１）、
そのビンから生じたテストサンプルから、最良の、観察された性能評価を決定すること（１７２）、
を含む請求項１に記載の方法。
【請求項９】
複数のビンの最良の履歴性能に基づいて該複数のビンにわたる確率分布を構築すること（１７３）、
をさらに含み、
１つのビンが他のビンよりも高い評価得点を得た場合、そのビンは、新たなサンプルを生成する高い確率を得る、
請求項８に記載の方法。
【請求項１０】
新たなサンプルが報酬−ペナルティベースの方法を用いて評価されるごとに前記確率分布を更新すること（１７４）をさらに含む、請求項９に記載の方法。
【請求項１１】
解を得るのに適合関数に基づいた局所探索を行うこと（１７８）をさらに含む、請求項１０に記載の方法。
【請求項１２】
システム性能を最適化するコンピュータ読み取り可能なプログラムを有するコンピュータ読み取り可能な記録媒体であって、該コンピュータ読み取り可能なプログラムは、コンピュータ上で実行されるときに、該コンピュータに、
いくつかの構成サンプルを選択すること（１６２）、
前記サンプルに基づいてシステム性能を評価すること（１６６）、
評価されたサンプルのフィードバックに基づいて、最適構成のロケーションを推測すること（１７０）、
追加サンプルを前記推測された最適構成のロケーションの方へ発生させ、システム構成をさらに最適化すること（１７６）、
によって、サンプリングベースの最適化を適用してコンピューティングシステムの最適構成を特定するステップ（１６０）、
を行わせるコンピュータ読み取り可能な記録媒体。
【請求項１３】
前記評価されたサンプルのフィードバックに基づいて、最適構成のロケーションを推測すること（１７０）は、
一連のパラメータをいくつかのビンに分割すること（１７１）、
そのビンから生じたテストサンプルから、最良の、観察された性能評価を決定すること（１７２）、
を含む請求項１２に記載のコンピュータ読み取り可能な記録媒体。
【請求項１４】
複数のビンの最良の履歴性能に基づいて該複数のビンにわたる確率分布を構築すること（１７３）、
をさらに含み、
１つのビンが他のビンよりも高い評価得点を得た場合、そのビンは、新たなサンプルを生成する高い確率を得る、
請求項１３に記載のコンピュータ読み取り可能な記録媒体。
【請求項１５】
新たなサンプルが報酬−ペナルティベースの方法を用いて評価されるごとに前記確率分布を更新すること（１７４）をさらに含む、請求項１４に記載のコンピュータ読み取り可能な記録媒体。
【請求項１６】
解を得るのに適合関数に基づいた局所探索を行うこと（１７８）をさらに含む、請求項１５に記載のコンピュータ読み取り可能な記録媒体。
【請求項１７】
コンピューティングシステムの構成を最適化する分散化されたテストシステム（２００）であって、
テスト用の負荷を発生させることおよび性能データを収集することによってコンピューティング環境の構成を評価するように構成されているテストエージェント（２０４）と、
前記テストエージェントと並列に接続され、構成エージェントに関連づけられた現在の構成設定の妥当性チェックを行うことにより、該テストエージェントに応答するように適応されている、複数の構成エージェント（２０２）と、
を有し、
前記構成エージェントは、コンピューティングシステムの全体にわたって分散され、前記テストエージェントから効用得点を受け取り、次の評価反復用の新たなサンプルを生成する確率を更新するように構成されている、
テストシステム。
【請求項１８】
前記各構成エージェント（２０２）は１つの性能パラメータに関連づけられていて、該１つの性能パラメータの最適化は１つの構成エージェントに割り当てられている、請求項１７に記載のシステム。
【請求項１９】
前記構成エージェント（２０２）は前記コンピューティングシステム（２００）の複数のノードにわたって分散されている、請求項１７に記載のシステム。
【請求項２０】
前記テストエージェント（２０２）は、前記構成エージェントの評価から受け取ったすべての結果に従って、評価得点を発生させる、請求項１７に記載のシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
本出願は、２００７年１０月２９日に出願された仮出願番号第６０／９８３，３１１号を基礎とする優先権を主張し、その開示をここに取り込む。
【０００２】
本発明は、コンピュータシステムの最適化に関し、特に、分散確率のアクティブサンプリング法を用いてコンピュータシステム性能を改善するシステムおよび方法に関する。
【背景技術】
【０００３】
コンピューティングシステムの性能は、そのシステムの種々の構成パラメータの選択に大きく左右される。適切な構成設定を行うと、短い応答時間、高スループット、およびユーザ間の公平性といった最良のサービス品質（ＱｏＳ）へと、システムを導くことができる。しかしながら、現在のコンピューティングシステムにおける拡張性、複雑性、および、多様性の増大は、システム動作の最適な構成設定を決定するにあたって、多くの課題を生み出している。例えば、今日のデータセンターは、種々のウェブアプリケーションをホストするために、一般に、何千もの物理的なマシンを備えている。人間オペレータがそのような大規模システムに対する最良の構成設定を見つけるのは困難である。
【０００４】
現在、一般に用いられているシステム構成のための手法は、システムコンポーネントのベンダーから、各システムコンポーネントと共に提供されるデフォルト設定に依存している。そのようなデフォルト設定は、異なるシステムコンポーネント間の相互依存性を無視しているので、従前の方法でシステムを配置することになる。例えば、ウェブベースのシステムにおけるアプリケーションサーバの構成は、そのシステムに配置される特定のアプリケーションと、それらのアプリケーションが通信するバックエンドデータベースの種類と、に大きく依存する。通常、これらのシステムコンポーネントは異なる複数のベンダーから提供される。これらのシステムコンポーネントがそのデフォルト構成で動作する場合、最適でない性能になりやすい。
【０００５】
そのため、コンピューティングシステムの性能を全体として最適化できる構成設定を、自動的に発見する方法を開発する必要がある。
【０００６】
コンピューティングシステムの複雑性が増大したため、大規模システムの最適化および管理において、システムの最適構成を自動的に特定（identification）することが重要になる。この問題に対処するために、近年いくつかの手法が開発されている。これらの手法は上記の問題を最適化問題として定式化し、異なるアルゴリズムを用いて最良の構成を探索するものである。しかしながら、勾配ベースのアルゴリズムのような多くの標準的な最適化技術と比較して、これらのアルゴリズムは、複数の極大値を持つ、未知の非凸関数を扱う点で異なる。
【０００７】
調整されたサンプリング空間を持つランダムサンプリングにおける絶えずリスタートするメカニズムだけでなくランダムサンプリングにおける初期の高効率な特徴にも基づいて配置空間（configuration space）を発見するために、再帰的ランダムサンプリング（ＲＲＳ：recursive random sampling）法が用いられている。スマートな山登り（ＳＨＣ：smart hill climbing）アルゴリズムも、インポータンスサンプリング（importance sampling）法およびラテンハイパーキューブサンプリング（ＬＨＳ：Latin Hypercube Sampling）法のアイデアを用いて提案されたものである。この手法では、各ポテンシャル領域で局所関数を推定し、推定された関数の最も急勾配な降下方向に向かって探索を行う。
【発明の概要】
【発明が解決しようとする課題】
【０００８】
アクティブ調和プロジェクトでは、各構成設定に関する未知の性能関数を最適化するのに、シンプレックスベースの直接探索法を利用している。この方法は、いくつかのサンプルによって母数空間（parameter space）にシンプレックスを形成し、鏡映、拡張、収縮を含む操作によりシンプレックスを反復して更新し、新しいサンプルを生成している。しかしながら、シンプレックスベースの探索法は少数の構成パラメータに対してのみ有効であり、局所最適解では簡単に行き詰まってしまう。
【０００９】
パラメータ数が多い場合、他の手法では、構成パラメータを、異なるパラメータ間の依存関係をモデル化することによって、いくつかの小さな部分集合に分解する。次に、パラメータの各部分集合において、シンプレックス法を実行する。その他の手法も提案されている。
【課題を解決するための手段】
【００１０】
従来の手法と比較して、本構成発見法は少なくとも次の優れた特徴を備えている。１）我々は、複数の性能次元（performance dimension）を組み込むことによってシステム性能を評価する一般的な方法を導入した。その結果、システムプロバイダーは、優れたシステム性能に関する彼ら自身の期待値を柔軟に定義することができるようになる。２）我々が提案している分散確率ベースのアクティブサンプリング（ＤＰＡＳ）法は、コンピューティングシステムの増大する構成パラメータ数に関する要求を満たすように、分散化手法で実行することができる。３）さらに、実験結果は、我々のＤＰＡＳシステムおよび方法が現在の構成特定技術よりも優れていることを実証している。
【００１１】
一実施形態では、もし、我々がシステム性能をそのシステムの構成設定の関数であると考えた場合、構成の発見は、その関数の最適化プロセスと見なすことができる。しかしながら、実際には、そのような従属関数は、通常、コンピューティングシステムの複雑性により利用できない。別の方法では、我々がシステムをブラックボックスとして取り扱い、サンプリングベースの最適化を適用して最適構成を特定する。すなわち、我々がいくつかの構成サンプルを選択し、それらのサンプルに対するシステム性能をテストする。評価されたサンプルのフィードバックに基づいて、最適化プロセスは最適構成のロケーションを推測し、次に、その方向に向けてより多くのサンプルを生成する。なお、基礎的な性能関数は複雑であり、多くの極大値を持っている。優れたサンプリングプロセスは、配置空間のいくつかの有望な領域の局所構造だけでなく、大域的範囲をも考えなければならない。さらに、システム性能評価を行う時間的コストが最適化プロセスで問題となる可能性がある。ウェブベースのシステムにおいては、評価のための信頼性のある性能測定値を収集するのに、通常、約２０分間、システムを実行する必要がある。したがって、最小限のサンプル数で最適構成を特定できることは有用である。
【００１２】
システム性能を最適化するシステムおよび方法は、サンプリングベースの最適化法を適用して、いくつかの構成サンプルを選択することによってコンピューティングシステムの最適構成を特定すること、そのサンプルに基づいてシステム性能を評価すること、を含んでいる。評価されたサンプルのフィードバックに基づいて、最適構成のロケーションが推測される。追加サンプルは、推測された最適構成のロケーションの方に生成し、システム構成をさらに最適化する。
【００１３】
これらおよび他の特徴および効果は、添付の図面に関連して参照される実施形態に関する以下の詳細な説明から明白になるであろう。
【００１４】
その開示によって、以下の図面に関連する、以下の好ましい実施形態の説明は詳細になっていくであろう。
【図面の簡単な説明】
【００１５】
【図１】本原理に係る基本システムを示す概略図である。
【図２Ａ】効用関数対応答時間を示すプロットである。
【図２Ｂ】効用関数対スループットを示すプロットである。
【図２Ｃ】効用関数対要求拒否率を示すプロットである。
【図３】本原理に係る概念を実証する３次元関数を示す図である。
【図４】図３の最大関数の射影をそれぞれ示した、関数ｇ1（ｘ1）およびｇ2（ｘ2）の２つのプロットである。
【図５】１つの例示的な実施形態に係るコンピューティングシステム構成を最適化するシステム／方法を示すブロック／フロー図である。
【図６】１つの例示的な実施形態に係る、分散されたテストシステムアーキテクチャを示すブロック図である。
【図７】図６のシステムアーキテクチャにおけるテストエージェントと構成エージェントとの間の通信を示す図である。
【図８】従来の方法よりも優れているＤＰＡＳ法を示した、システム最適化の異なる方法のプロットである。
【発明を実施するための形態】
【００１６】
大規模なコンピューティングシステムの複雑性が増大するにつれて、最良のシステム性能を得るために、そのシステムの多数の構成パラメータを調整することは、標準の人間の能力を越えてきている。本原理によれば、分散確率ベースのアクティブサンプリング（ＤＰＡＳ）法を用いて、システムの最適構成が自動的に決定される。１つの例示的な実施形態では、構成の発見がブラックボックスの最適化問題として取り扱われ、解の探索が有限の構成サンプル数を評価することによって行われる。ＤＰＡＳシステム／方法は、過去のサンプルからの経験を利用して新たなサンプルを生成する確率を作り出す効率的サンプリングの戦略（strategy）を提供する。そのような確率は、探索プロセスを最終的に最適設定へ導く報酬（reward）−ペナルティ戦略に基づき、評価されたサンプルごとに動的に更新される。さらに、ＤＰＡＳ法ベースの最適化により、各モジュールが特定の構成パラメータを探索する責任を負う、１群の個別のモジュールに分解することができる。
【００１７】
その結果、本原理に係るシステム／方法は、多数の構成パラメータを検査する分散化手法で実行することができる。このシステム／方法の１つの実施形態は、実際のウェブベースのテストベッドシステムだけでなくベンチマーク関数も用いることによって、実験において、従来の構成探索法と比較される。この実験では、複雑な母数空間において最終的に特定された解に関して、本システム／方法が他の方法より性能が優れていることが実証される。
【００１８】
分散確率ベースのアクティブサンプリング（ＤＰＡＳ）法は、システムの性能メトリクス、最適化、および、実行に関していくつかの有利な特徴を備えている。例えば、システム応答時間のような単一の性能メトリックに着目する代わりに、システムスループット、要求応答時間、および拒否率を含む複数の観点からシステム性能を評価する、より一般的な方法であることである。これは、そのような性能メトリックによって導かれ、異なる複数のマシンにわたって分散された構成およびパラメータを持つシステムを検査する、システムの最適構成を探索する分散型の方法によって達成される。構成の探索は、各々が特定のパラメータを最適化する責任を負ういくつかのモジュール（エージェントと呼ばれる）に分解される。このエージェントは、その関連する一連のパラメータをいくつかのビンに分割し、そのビンから生じたテストサンプルから、各ビン毎に、最良の、観察された性能評価を保持する。
【００１９】
複数のビンの最良の履歴性能に基づいて、それら複数のビンにわたって確率分布が構築される。１つのビンが他のビンよりも高い評価得点を得た場合、そのビンは、新たなサンプルの生成において、高い確率を得ることになる。そのような確率分布は新たなサンプルが評価されるたびに更新される。報酬−ペナルティベースの方法を用いて、探索プロセスが最終的に最適構成を含むビンに収束するように、確率を更新する。その後、適合二次関数等に基づく局所探索を行い、解を得る。
【００２０】
ここで説明された実施形態は、すべてがハードウェア、すべてがソフトウェアであってもよく、または、ハードウェア要素およびソフトウェア要素の両方を含んでいてもよい。好ましい実施形態において、本発明は、ファームウェア、常駐ソフトウェア、マイクロコードなどを含むソフトウェアによって実行されるが、これらに限定されるものではない。
【００２１】
実施形態は、コンピュータまたは任意の命令実行システムに関連してまたはそれらに使用されるプログラムコードを提供するコンピュータ使用可能またはコンピュータ読み取り可能な記録媒体からアクセス可能なコンピュータプログラム製品を含んでいてもよい。コンピュータ使用可能またはコンピュータ読み取り可能な記録媒体は、命令実行システム、装置またはデバイスに関連してまたはそれらに使用されるプログラムを、格納、通信、伝搬または搬送する任意の装置を含んでいてもよい。この記録媒体は、磁気、光学、電子、電磁気、赤外線、または半導体のシステム（または装置またはデバイス）、または伝搬媒体とすることができる。記録媒体は、半導体または固体メモリ、磁気テープ、リムーバブルコンピュータディスケット、ランダムアクセスメモリ（ＲＡＭ）、読み取り専用メモリ（ＲＯＭ）、剛性磁気ディスクおよび光ディスク等のような、コンピュータ読み取り可能な記録媒体を含んでいてもよい。
【００２２】
ここで、同一または同様の要素を同じ符号で表した図面を参照すると、まず、図１には、有限のサンプル数を評価することによって最良のシステム構成を特定するシステム１０が例示的に示されている。サンプルは１つの特定のシステム構成設定を示している。構成パラメータ／値１２が与えられると、システム１０は一定の負荷１４で動作を行い、システムの複数の性能メトリック１６がそのサンプルに対して評価される。システム１０は、単一のコンピュータ装置、コンピュータ装置のネットワーク、コンピュータプログラム、またはそれらの組み合わせを含んでいてもよい。このコンピュータ装置は、特定の構成パラメータまたは設定の選択によって最適な性能を達成する方法以上の方法で構成され得る装置を含んでいてもよい。
【００２３】
従来の方法は、通常、応答時間のような単一のメトリックに依存して、システム性能を特徴づけている。本原理によれば、システムスループット、要求応答時間、要求拒否率、および／またはその他の、多次元をカバーするシステム性能を表す、より一般的な枠組みが提供される。
【００２４】
多くのウェブベースのシステム、特に、電子商取引アプリケーションのシステムでは、サービスプロバイダーは、システムがサービスプロバイダーの収益を最大にできる最高のスループットを持つことを望んでいる。しかしながら、要求量の増加は、同時に、要求応答時間および拒否率の増大を招き、その結果、ユーザに不満が生まれ、それによりシステムに対する悪評を生むことになる。特に、システム挙動が「非線形区間」に入った場合、システムスループットが低下する一方で、要求応答時間は劇的に大きくなる。
【００２５】
より多くのユーザを引きつけるシステム応答時間および利用可能性を保証するだけでなくシステムスループットをも改善するためには、応答時間Ｒ、スループットＸ、および要求拒否率Ｌを含んだ複数の性能を基準として、総合的なシステム性能を定めることが考えられる。我々は、性能メトリックの観点から、優れたシステム性能についての期待値を表すために、経済分野で用いられている関数に類似する効用関数の概念を導入する。
【００２６】
効用関数はシステム性能を特徴づけるのに用いられる。これは、性能メトリックの異なる値が総合的なシステム性能に対して異なる寄与率を持っていてもよいという所見に由来している。例えば、２秒から１秒への応答時間の短縮は、８秒から７秒への応答時間の短縮よりも、システム性能に対する重要度は低い。なぜならば、後者の方が、システムのユーザ満足度により影響を与えるからである。そのような知識は、平均応答時間
【００２７】
【数１】
2011504254.tif 000003
【００２８】
の式には含まれない。
【００２９】
【数２】
2011504254.tif 000004
【００３０】
平均応答時間は、評価中に、Ｎ個の完了した要求、｛Ｒ1，Ｒ2，．．．，ＲN｝が与えられる伝統的な性能評価において、頻繁に用いられている。効用関数Ｕ1（Ｒ）は、システム性能への異なる応答時間値の影響を明確にすることができる。Ｕ（・）値が大きいことは、優れたシステム性能に対するより大きな寄与を意味しており、逆もまた同様である。その結果、我々はＮ個の収集された要求の応答時間に対する期待効用値を次式のように算出することができる。
【００３１】
【数３】
2011504254.tif 000005
【００３２】
なお、関数Ｕ1（Ｒ）＝１の場合、数式（２）の期待効用値は数式（１）の平均応答時間と同じである。ここで、我々は次の関数
【００３３】
【数４】
2011504254.tif 000006
【００３４】
を用いて、システム性能への応答時間の影響を差別化する。異なるシステムは優れた性能について異なる期待値を持っていてもよいので、数式（３）には関数の形状を調整するａおよびｕの２つのパラメータがあり、これがシステム性能の柔軟な特徴づけを可能にしている。
【００３５】
図２Ａ〜図２Ｃを参照すると、応答時間（Ｒ）（図２Ａ）、スループット（Ｘ）（図２Ｂ）、および要求拒否率（Ｌ）（図２Ｃ）の効用関数のプロットが例示的に示されている。図２Ａでは、秒で表される応答時間に対してパラメータａ＝１およびｕ＝１０を持つ数式（３）が示されている。短い応答時間が高い効用値になることが理解できるであろう。しかしながら、応答時間がある値、例えば、この場合には４秒よりも小さい場合、応答時間に対する効用値はあまり変わらない。このことは、いったん応答時間が特定の範囲内になると、応答時間は、スループット（Ｘ）および要求拒否率（Ｌ）のような他の性能次元よりも重要度が高くなることを意味している。同様に、応答時間がより高いしきい値、例えば１５秒よりも大きい場合、効用関数はほぼ０になる。このことは、応答時間を６０秒から４０秒に改善するために多くのリソースを用いるといった取り組みが不要であることを意味している。なぜならば、そのような改善はユーザ満足度という観点で多くの利益をもたらさないからである。
【００３６】
図２Ｂにおいて、システム性能に対して用いた同じ説明をスループットＸに対しても用いることができる。我々は評価期間をＴ間隔に分割し、各間隔の平均スループットとなるスループット測定値｛Ｘ1，Ｘ2，．．．，ＸT｝を収集する。スループットに関するシステム性能はその期待効用値により次式で表される。
【００３７】
【数５】
2011504254.tif 000007
【００３８】
ここで、Ｕ2（Ｘi）はスループットの効用関数である。なお、我々はシステムが高スループットを持つことを常に期待しているので、Ｕ2（Ｘi）は応答時間の効用関数とは異なっていることに留意されたい。その結果、我々は次式を定義する。
【００３９】
【数６】
2011504254.tif 000008
【００４０】
ここで、Ｘmaxはシステムに期待される最大のスループットである。図２Ｂは、Ｘmax＝５００の場合の効用関数をプロットしたものである。
【００４１】
要求拒否率に関しては、要求損失のわずかな増加が、システムに対するユーザの知見に大きな影響をもたらすので、我々は次の指数関数を用いて、
【００４２】
【数７】
2011504254.tif 000009
【００４３】
その効用値を表す。加えて、要求失敗率が例えば１０パーセントよりも高い場合、システムは、多くのユーザを失い、そのユーザは代りに他のウェブサイトへの「クリック」をする可能性がある。なお、要求損失率Ｌは全体の評価期間から計算されるので、その期待効用値は、
【００４４】
【数８】
2011504254.tif 000010
【００４５】
であることに留意されたい。
【００４６】
全体として、総合的なシステム性能は、次式のように３つの期待効用値を合成したものと特徴づけられる。
【００４７】
【数９】
2011504254.tif 000011
【００４８】
重みｗ1、ｗ2、およびｗ3は、最終性能メトリックにおいて各要素の重要度を制御するものである。これらの重みの値は、異なるアプリケーションには異なる値を設定することができる。我々の実験では、ｗ1＝ｗ2＝ｗ3＝１に設定する。その結果、システムの効用値の範囲は０と３との間になる。
【００４９】
アクティブサンプリング法で導かれた効用値：
システムのｐ個の構成パラメータ、ｘ＝［ｘ1，ｘ2，．．．，ｘp］Tが与えられた場合、我々の最終目的は、数式（７）に定義された最高のシステム効用値をもたらすことができる最適設定
【００５０】
【数１０】
2011504254.tif 000012
【００５１】
を見つけることである。システム効用値を構成の関数
【００５２】
【数１１】
2011504254.tif 000013
【００５３】
として表すことができると仮定すると、我々は実際には次の最適化問題を解いていることになる。
【００５４】
【数１２】
2011504254.tif 000014
【００５５】
関数ｆ（・）は通常、実際のアプリケーションでは未知なので、サンプリングベースの関数評価に頼って最適パラメータを発見する。我々は、効率的に配置空間を調査し、最小のサンプル評価数で最適パラメータ設定を見つけるインテリジェントな方法を必要とする。インテリジェントなサンプリングの重要な１つの要素は、システム効用を著しく改善できるサンプルのロケーションを推測するために、過去のサンプルからの経験を利用することである。例えば、我々がｍ個のサンプル、ｘ(1)，ｘ(2)，．．．，ｘ(m)に対する関数評価を既に行ったとすると、新たなサンプルｘ(m+1)は次式によって生成する。
【００５６】
【数１３】
2011504254.tif 000015
【００５７】
ここで、Ｍ（・）は最適解の方に新たなサンプルを生成する戦略を表している。以下では、Ｍ（・）の機能性を達成するために、確率ベースのアクティブサンプリング法を提案する。
【００５８】
確率的サンプリング：
各変数ｘiに対して、我々は次式の関数
【００５９】
【数１４】
2011504254.tif 000016
【００６０】
を、ｘiを除くすべてのパラメータにわたり関数ｆ（・）の最大値を表す関数として定義する。この関数は、ｘi座標上の関数ｆ（・）の最大値の射影（projection）と見なすことができる。
【００６１】
図３および図４を参照すると、座標ｘ1およびｘ2について図３に示した２つの射影関数ｇ1（ｘ1）およびｇ2（ｘ2）が、それぞれ図４にプロットされている。なお、ｇ1（ｘ1）は、特定のｘ2値に対するｘ1上のｆ（ｘ1，ｘ2）の射影とは全く異なり、ｘ2が取りうるすべての値にわたる図３の（ｘ1，ｘ2）の最大値であることに留意されたい。このことは、関数ｇ2（ｘ2）についても同じである。ここで、数式（８）の最適パラメータは、次のように他の形式で再構成することができる。
【００６２】
【数１５】
2011504254.tif 000017
【００６３】
ここで、ｉ＝１，．．．，ｐである。我々が各パラメータｘiの対応するｇi（ｘi）を知っている場合には、そのように再構成した形式に基づいて、ｐ個の一次元最適化問題を個々に解くことによって、最終解を得ることができる。この観察に動機づけられて、我々は最適パラメータを発見する分散型の方法を開発する。パラメータ値ｘiの範囲がＩiとして表される場合、システム効用関数ｆ（・）は、母数空間Ｉ＝Ｉ1×...×Ｉp内で定義される。ここで、最適点
【００６４】
【数１６】
2011504254.tif 000018
【００６５】
の存在が保証されるように、我々は関数ｆ（・）が連続的なものであるとする。我々は、各パラメータｘiの範囲Ｉiをｒ個の重複しない間隔Δ1，Δ2，．．．，Δrに分割する。次に、サンプルｘ＝［ｘ1，．．．，ｘp］はｐ次元ベクトルになり、各要素ｘiはｒ個のビンのうちの１つから取り出される。
【００６６】
我々のアクティブサンプリング法の１つの特徴は、最適値
【００６７】
【数１７】
2011504254.tif 000019
【００６８】
を含むビンを特定することである。我々は、いったん、そのような最適領域を局所化することができると、その領域からほぼ最適なサンプルを常に生成することができる。次に、最終解は、それらのほぼ最適値に基づいて局所探索を行うことにより得られる。各パラメータに対する最適ビンの推測は、履歴サンプルおよびそれら履歴サンプルに関連する関数値に基づいて行われる。この推測は各パラメータに対し個々に行うことができる。したがって、以下では、我々は過去のサンプルからの最適ビンの推測に基づいて、パラメータｘiの新たな値ｘi(m+1)を生成する手順に注目する。
【００６９】
ｍ個の履歴サンプルｘ(k)＝［ｘ1(k)，ｘ2(k)，．．．，ｘp(k)］（ここで、ｋ＝１，．．．，ｍ）、および、それらの履歴サンプルに関連する関数値ｆ（ｘ(k)）が与えられると、我々は、座標
【００７０】
【数１８】
2011504254.tif 000020
【００７１】
上の射影関数
【００７２】
【数１９】
2011504254.tif 000021
【００７３】
について
【００７４】
【数２０】
2011504254.tif 000022
【００７５】
個の評価を、次式に基づいて得ることができる。
【００７６】
【数２１】
2011504254.tif 000023
【００７７】
なお、
【００７８】
【数２２】
2011504254.tif 000024
【００７９】
は、以前のｍ個のインスタンス｛ｘi(1)，．．．，ｘi(m)｝でｘiのいくつかの値が同じになる可能性があるので、利用可能なサンプルおよび
【００８０】
【数２３】
2011504254.tif 000025
【００８１】
に基づいた関数ｇ（・）の推定値であることに留意されたい。ｇi（ｘi）に関する適切な観察に基づいて、我々は過去のサンプルからの最良の効用値を表すパラメータｘiに対する最良の効用ベクトルΨ＝［ψ1，ψ2，．．．，ψr］を定義する。ここで、ｘiは、個々のビンのそれぞれから得られる。すなわち、Ψにおける各要素ψjは、以前のサンプルについての
【００８２】
【数２４】
2011504254.tif 000026
【００８３】
の最大値を表している、ここで、ｘiはビンΔjから得られる。
【００８４】
【数２５】
2011504254.tif 000027
【００８５】
値ψjは、新たなサンプルを生成するビンΔjの重要度を反映している。例えば、要素ψjがΨの中で最大である場合、最適サンプル要素
【００８６】
【数２６】
2011504254.tif 000028
【００８７】
はビンΔjから得られる可能性が高い。そのような情報は、新たなサンプルｘi(m+1)の生成のために利用される。ビンの離散化および以前のサンプルサイズが有限であることに起因する不確実性を理由に、我々はｘi(m+1)を生成する確率的サンプリング戦略を提案する。そこでは、確率ベクトル
【００８８】
【数２７】
2011504254.tif 000029
【００８９】
は、新たなサンプルｘi(m+1)を生成する各ビンの優先度を表すように定義される。確率ベクトルＰにおける各要素の値は、ベクトルΨの要素値に密接に関係している。例えば、ψjがΨの最大の要素である場合、我々は、高い確率ｐjを持つビンΔjからｘi(m+1)を取り出す必要がある。さらに、我々が、いったん新たなサンプルの評価結果を得ると、最良の効用ベクトルΨおよび確率ベクトルＰの両方が更新される。
【００９０】
確率ベクトルＰは、最初、Ｐ＝［１／ｒ，１／ｒ，．．．，１／ｒ］として初期化される。我々が、ｍ個のサンプルが評価された後、現在の確率Ｐ(m)＝［ｐ1(m)，ｐ2(m)，．．．，ｐr(m)］および最良の効用ベクトルΨ(m)＝ψ1(m)，ψ2(m)，．．．，ψr(m)が分かっていると仮定すると、新たな値ｘi(m+1)が、確率ＰjでそのビンΔjのうちの１つから生成される。具体的には、我々は０と１との間の確率変数ｕを生成する。その変数に基づいて、次式が満足される場合には、新たな値ｘi(m+1)がそのｌ番目のビンΔlから生じる。
【００９１】
【数２８】
2011504254.tif 000030
【００９２】
我々は、すべてのパラメータｘ(m+1)＝［ｘ1(m+1)，．．．，ｘp(m+1)］の新たな値を生成した後、システムをテストし、新たな構成設定下でシステムの効用値ｆ(m+1)（ｘ(m+1)）を得る。説明を簡単にするために、我々は、新たなサンプルｘ(m+1)の効用値を表すためにｆ(m+1)を用いる。新たな効用値に基づいて、ｘiの確率ベクトルは、Ｐ(m)→Ｐ(m+1)に更新される。
【００９３】
以下に、新たなサンプルおよび現在の最良の効用ベクトルの効用値に基づいて確率ベクトルの更新が行われる、我々の確率の更新ルールを説明する。ここでは、要素ｘi(m+1)がｘiのｌ番目のビンから取り出される新たなサンプルによって生成される効用値ｆ(m+1)だけでなく、パラメータｘiの効用ベクトルΨ(m)＝［ψ1(m)，ψ2(m)，．．．，ψr(m)］および確率ベクトルＰ(m)＝［ｐ1(m)，ｐ2(m)，．．．，ｐr(m)］も与えられるものとする。確率の更新は次を含む。
【００９４】
【数２９】
2011504254.tif 000031
【００９５】
すべてのｊ＝１，．．．，ｒおよびｊ≠ｌに対して、Ψj(m)がｆ(m+1)よりも大きい場合、
【００９６】
【数３０】
2011504254.tif 000032
【００９７】
が得られ、Ψj(m)がｆ(m+1)よりも小さい（または等しい）場合、
【００９８】
【数３１】
2011504254.tif 000033
【００９９】
が得られ、
ｊ＝ｌに対して、
【０１００】
【数３２】
2011504254.tif 000034
【０１０１】
が得られる。
【０１０２】
我々は、ｘiのｒ個のビンを、それらのビンに関連する最良の効用値と新たな効用値ｆ(m+1)との比較に基づいて、３つのグループに分類する。第１のグループは、最良の効用値ψjが新たな効用値ｆ(m+1)よりも大きいビンを含んでいる。我々は、数式（１６）を用いてそれらのビンの確率を上げ、それらのビンの重要度を高める。他方では、最良の効用値ψjが新たな効用値ｆ(m+1)よりも低い第２のグループのビンに対しては、我々は、数式（１７）によってそれらの関連する確率を下げる。最後のグループは、たった１つの要素ｘi(m+1)を生成したｌ番目のビンを含んでいる。その確率は、新たな効用値ｆ(m+1)が他のビンの最良の効用値に比べてどれだけ高いかまたは低いかに応じて、確率の上昇または低下のいずれかに帰結する、数式（１８）に記述されている正規化によって更新される。
【０１０３】
確率の更新ルール（例えば、数式（１６）、（１７）、および（１８））は、例えば、オートマトン形式ベースの機械学習理論等の他の数式を用いることで代用することもできる。パラメータλの適切な選択により、数式（１６）は、確率ベクトルを、最適点
【０１０４】
【数３３】
2011504254.tif 000035
【０１０５】
を含んだビンに対して要素「１」を持つ単位ベクトル
【０１０６】
【数３４】
2011504254.tif 000036
【０１０７】
に収束させる。λの値は反復（iterative）プロセスの収束速度を決定する。小さなλが選ばれた場合、探索プロセスの処理速度は非常に低速になるが、大域的最適解を見つける確率は高くなる。大きなλはより速い収束を意味することになるが、大域的最適点を得られる保証はない。探索プロセスにおけるそのような「探査（exploration）」と「功績（exploitation）」の取り組みのバランスを保つために、我々は他のパラメータ「初期のサンプルサイズ」を定義する。
【０１０８】
ここで説明した実験では、我々は、第１の「初期のサンプルサイズ」のいくつかのサンプルに対してλ＝０から始めている。これは母数空間のランダムな均一サンプリングと等価である。後の反復に対しては、我々はλを定数値として設定する。なお、一定のλ値の選択の際には、システムの効用値の範囲も考慮して、更新された確率値を０と１との間にする必要があることに留意されたい。
【０１０９】
パラメータλの他に、次の要因も、各反復における確率の上昇または低下を表すΔｐj＝ｐj(m+1)−ｐj(m)に寄与する。
・現在の最大効用値ψj(m)と新たに得られた効用値ｆ(m+1)との間の差
大きな差値は大きな確率変動を引き起こし、その逆もまた同様である。
・確率上昇に対する（１−ｐj(m+1)）および確率減少に対するｐj(m)
既に分かっているように、確率ベクトルＰは、最終的に、最適点を含むビンに対して１を、他のビンに対してゼロを持つ単位ベクトルに収束する。（１−ｐj(m+1)）またはｐj(m)の役割は、値がその最終状態（１または０）により近くなるように、確率変動の大きさを低減することであり、それにより、収束点近傍の発振を回避することができる。
・確率上昇に対する
【０１１０】
【数３５】
2011504254.tif 000037
【０１１１】
これは、ｘi(m+1)を生成するｌ番目のビンの重要度に基づいて確率を上昇させる従前の方法を提供する。大きなｐl(m)は、最適点を含むビンからｘi(m+1)が得られる可能性が高いことを意味している。したがって、確率上昇の量は大きくなり得る。しかしながら、ｐl(m)が比較的小さい場合、それにしたがって確率上昇は小さくなければならない。
【０１１２】
我々がいったんｆ(m+1)を得ると、最良の効用ベクトルΨ(m)も更新される。
【０１１３】
【数３６】
2011504254.tif 000038
【０１１４】
【数３７】
2011504254.tif 000039
【０１１５】
次に、次回のサンプリングおよび確率の更新が再び始められる。最終的には、最適構成点を含むビンを特定する。我々は、そのビン内のサンプルを収集し、二次曲線を用いて効用関数をその領域（ｆ＝ａｘi2＋ｂｘi＋ｃ）に適合させる。次に、勾配を適合関数
【０１１６】
【数３８】
2011504254.tif 000040
【０１１７】
に適用することによって、最終解
【０１１８】
【数３９】
2011504254.tif 000041
【０１１９】
が得られる。
【０１２０】
分散化実施：
各構成パラメータの探索プロセスは独立したモジュールであるので、本実施形態は、大規模なパラメータ最適化の要求を満たす分散化手法で実施することができる。
【０１２１】
図５を参照すると、システム性能を最適化するシステム／方法を示すブロック／フロー図が例示的に示されている。ブロック１６０では、コンピューティングシステムの最適構成を特定するために、サンプリングベースの最適化が用いられる。これは以下のことを含んでいる。ブロック１６２では、いくつかの構成サンプルが選択される。このサンプルの選択は戦略に従って行われるのが好ましい。例えば、この戦略は、配置空間内のサンプル数を決定するために、大域的範囲のサンプルおよび局所構造の両方を考慮すべきである。いくつかの構成サンプルを選択することは、ブロック１６３において、複数の構成パラメータを用いる分散確率ベースのアクティブサンプリング（ＤＰＡＳ）法を実行することを含むことが好ましい。ＤＰＡＳ法は、過去のサンプルからの経験を利用するサンプリング戦略を含み、その過去のサンプルからの履歴データに基づいて、新たなサンプルを生成する確率を作り出す。確率を作り出すことは、ブロック１６４において、探索プロセスを最適設定の方に導くような報酬−ペナルティ戦略に基づいて、各評価されたサンプルを動的に更新することを含んでいる。
【０１２２】
ブロック１６５において、サンプリングは、各モジュールが特定の構成パラメータを探索する責任を負う１群の個別のモジュールに分解されてもよい。
【０１２３】
ブロック１６６において、システム性能がサンプルに基づいて評価される。ブロック１６８において、受け入れ可能なシステム性能の定義を許容するために複数の性能次元が同時に組み込まれる。
【０１２４】
ブロック１７０において、評価されたサンプルのフィードバックに基づいて、最適構成のロケーションが推測される。これは、ブロック１７１において、一連のパラメータをいくつかのビンに分割すること、ブロック１７２において、そのビンから生じたテストサンプルから、最良の、観察された性能評価を決定すること、を含んでいてもよい。ブロック１７３において、確率分布が、複数のビンの最良の履歴性能に基づいて、その複数のビンにわたって構築される。ここでは、１つのビンが他のビンよりも高い評価得点を得た場合、そのビンは、新たなサンプルを生成する高い確率を得ることになる。ブロック１７４において、確率分布は、新たなサンプルが報酬−ペナルティベースの方法を用いて評価されるたびに更新される。ブロック１７６において、推測された最適構成のロケーションの方に追加サンプルを生成し、システム構成をさらに最適化する。ブロック１７８において、適合関数に基づく局所探索を行い、解を得る。
【０１２５】
図６を参照すると、テストエージェント２０４と並列に動作する複数の構成エージェント２０２を示すアーキテクチャ２００が例示的に示されている。各構成エージェント２０２は、特定の構成パラメータの最適値を探索する責任を負う。このエージェント２０２を、関連する構成パラメータが配置された、異なる物理的なマシンに分散させることができる。テストエージェント２０４は、テスト用の負荷を発生させて各評価プロセスに対する性能データを収集するような構成評価を行うモジュールである。
【０１２６】
図７を参照すると、テストエージェント２０４と各構成エージェント２０２との関係が例示的に示されている。構成エージェント２０２は、最適化プロセスを始める前に、テストエージェント２０４に自分自身を登録する必要がある（３０２）。各評価の初めに、テストエージェント２０４は、構成エージェント２０２に対して「実験開始」または「評価開始」コマンドを送る（３０４）。構成エージェント２０２は、コマンドを受け取ると（３０４）、ブロック３０６において、現在の構成設定の妥当性をチェックする。ウェブベースのシステムでは、構成設定を有効にするために、関連するコンポーネントの再起動が必要になる可能性がある。次に、テストエージェント２０４は、ブロック３０７において、システムに対するテスト用の負荷を発生させ、その負荷の下でシステム性能を測定する。
【０１２７】
評価が終了した後、テストエージェント２０４は、数式（７）に基づいて効用得点を算出し、その結果をすべての構成エージェント２０２に対してブロードキャストする（３０８）。いったん構成エージェント２０２が新たな結果を得ると、テストエージェントは、ブロック３１０において、数式（１６）、１７、および（１８）に基づいて、その生成確率を更新し、その後、次の評価に対する新たなテスト値を生成する。いったんテストエージェントがすべての構成エージェント２０２から通知を受け取ると、次回の評価を開始できるように、「レディ」信号３１２もテストエージェントに送られる。
【０１２８】
再度図６を参照すると、本分散化実施は、多くのアプリケーションに対して、特に、システム内の種々のノードにわたって分散された多数の構成パラメータを持つアプリケーションに対して、多くの利点をもたらす。まず、本分散化実施は、各個々の構成エージェント２０２に最適化を割り当てることにより、最適化プロセスの計算時間を短縮する。これは、構成パラメータ数が多い場合に有用である。本分散化実施は、全体の母数空間にわたって、効用ベクトルおよび確率分布を記憶するために大規模なメモリを使用することも回避できる。各構成エージェント２０２は、関連するパラメータの空間上にある、それらの値の射影を記憶するだけである。
【０１２９】
本分散化実施の他の魅力的な特徴は、テストエージェント２０４に構成エージェント自身を登録またはその登録を取り消すことだけで、構成エージェント２０２をシステム２００に追加またはシステム２００から取り除くことが容易であることである。アーキテクチャ２００は、最適化されるべきパラメータ数に左右されない。さらに、各構成エージェント２０２は別々に動作しているので、いくつかのアプリケーションでは、我々は構成パラメータの事前のシステム知識に基づいて複数のエージェントを別々に処理することにより、最適化を高速化することができる。例えば、我々は、いくつかの構成パラメータがシステム性能と単純な関係（例えば、単調な関係）を持つことを知っている場合、数式（１６）および（１７）で関連する更新係数λを増加させることで、探索プロセスにおけるいくつかの不必要な探査演算を回避でき、それにより、最適化を高速化することができる。
【０１３０】
各エージェント２０２は１つの構成パラメータを最適化する責任を負うが、実際には、いくつかのパラメータを１つの構成エージェント２０２の配下に入れることができる。パラメータのグルーピング化は、構成パラメータの依存関係だけでなく、構成パラメータの物理的なロケーションに基づいて行われてもよい。例えば、我々は、２つのパラメータが強い依存関係を持つことを知っている場合、その２つのパラメータを１つの構成エージェント２０２で一緒に調整することができる。この場合、最良の効用値Ψおよび確率分布はベクトルというよりもむしろ２次元マトリックスである。エージェントはパラメータの漸進的な変化に関してより大域的な視野を持つことができるので、そのようなグルーピング化は最適化プロセスの収束を高速化することができ、それにより、サンプリングにおけるいくつかの不必要な試みを回避することができる。
【０１３１】
なお、我々の分散化実施は、異なる属性間の依存関係を無視することを意味しているものではないことに留意されたい。ｘjの異なる設定がｘiの異なる最良の値になる場合およびその場合にのみ、パラメータｘiはパラメータｘjに依存する。ＤＰＡＳ法では、各パラメータｘiの探索プロセスは、他のパラメータを固定せずに行われる。すなわち、複数の構成エージェント２０２は、すべての構成パラメータに寄与する過去のサンプルの性能評価を共有する。そのように共有された情報によって、パラメータの依存関係が最適化プロセスに組み込まれていく。以下の実験結果は、分散化技術が最適化の性能を劣化させないことも実証している。
【０１３２】
実験結果：
我々は、母数空間内で最適点を発見するＤＰＡＳシステム／方法の有効性を実証するのに、合成データと実際のテストベッドシステムとの両方を用いる。我々の手法の性能は、他の現在の構成最適化技術の性能とも比較される。
【０１３３】
合成データ：
我々は、我々のＤＰＡＳ法の最適化プロセスを示すのに既知のＲａｓｔｒｉｇｉｎ関数を用いる。Ｒａｓｔｒｉｇｉｎ関数は、その非常に多様な形態により、ブラックボックスの最適化技術を評価するために一般に用いられるベンチマークである。しかしながら、そのような関数は通常、関数最小化の評価に用いられ、ＤＰＡＳ法は母数空間の最大値を探索する。したがって、我々は、実験では、次式で記述される負のＲａｓｔｒｉｇｉｎ関数を用いる。
【０１３４】
【数４０】
2011504254.tif 000042
【０１３５】
ここで、Ｎは入力ｘの次元数であり、βは関数の形状を制御する定数である。この関数は、サンプリングアルゴリズムの評価に適した多くの極大値を有していることが理解できよう。
【０１３６】
我々は、数式（１６）、（１７）の確率更新に対して、λ＝０．０５を選択し、探索ステップ数を２００以内に制限する。評価サンプルは最初一様に散乱されているが、最適化が進むにつれ最適領域の方へと分散される。探索アルゴリズムは実関数の最大値の方に進む。最良のサンプルは１２０番目の評価で発見された。しかしながら、サンプリングの確率的な性質により、この方法は、なおそのサンプルの後の関数空間を探査する。１６０番目の反復の後で初めて、この方法は、１８７番目のサンプルのような僅かな探査操作でほぼ最適領域に収束する。そのような制限された探査数は探索に適している。なぜならば、探索によって大域的なパラメータ空間でより有望な領域を見つけることができる場合、そのような探索は局所関数の最大値から脱するプロセスに寄与し得るからである。
【０１３７】
本分散化実施は、焼きなまし（ＳＡ）法、再帰的ランダムサンプリング（ＲＲＳ）法、およびスマートな山登り（ＳＨＣ）法のような既存のアルゴリズムと比較された。我々は、負のＲａｓｔｒｉｇｉｎ関数を用いるが、関数の次元は高い（Ｎ＝２０）。Ｒａｓｔｒｉｇｉｎ関数のパラメータβとして８８を選択し、各次元の範囲を−６と６との間にする。我々は、関数の最小値を捜す代わりに関数の最大値を探索するように、それらのアルゴリズムも修正する。なお、すべての最適化はいくつかのパラメータに関連づけられていることに留意されたい。我々の実験で用いるパラメータの値を表１に示す。
【０１３８】
【表１】
2011504254.tif 000043
【０１３９】
各アルゴリズムに対して、我々は関数評価数を２０００以内に制限する。探索プロセスの確率的な性質を考慮して、我々は各方法に対して５０の最適化試行を実行し、比較のためにその平均的な結果を用いた。
【０１４０】
図８を参照すると、特定された関数の最大値が、ＳＡ法、ＲＲＳ法、ＳＨＣ法、およびＤＰＡＳ法（初期サイズ３０と初期サイズ５０）についての各関数評価で示されている。３００番目のサンプルの後の、より高い２つの曲線４０２および４０４は、それぞれ初期のサンプルサイズ５０および３０を持つＤＰＡＳ法の結果である。これは、５０個の初期サンプルを持つＤＰＡＳ法が、すべての方法の中で最良の最終結果を達成していることを示している。しかしながら、その性能は、探索の初期段階（１から２００まで）では他の方法よりも勝っている訳ではない。これは、ＤＰＡＳ法が、一定のランダムサンプリングを用いて初期サンプルを選択したからである。３００番目のサンプルの後の曲線４０４は３０個の初期サンプルを持つＤＰＡＳ法の結果である。これは、初期のサンプルサイズを小さくすることにより、性能を初期段階で改善できることを示している。しかしながら、初期のサンプルサイズを小さくすると、その方法を局所関数の最大値に導く可能性が高くなる。実際には、そのようなパラメータを、探索プロセスのタイムバジェットに基づいて選択することで、良好な初期性能と最終特定結果との間のトレードオフを最良にすることができる。
【０１４１】
いずれにしても、ＤＰＡＳ法は、焼きなまし（ＳＡ）法４１０、再帰的ランダムサンプリング（ＲＲＳ）法４０８、およびスマートな山登り（ＳＨＣ）法４０６といった他の方法よりも良好に機能する。さらに、ＤＰＡＳ法は、表１に示すように、ＲＲＳ法４０８およびＳＨＣ法４０６と比較して、より小さい値に調整可能なパラメータを必要とする。
【０１４２】
実際のテストベッド：
我々の手法も、Ｊ２ＥＥの多層アーキテクチャに基づく実際の電子商取引アプリケーション上でテストされる。Ｊ２ＥＥは、Ｅｎｔｅｒｐｒｉｓｅ  ＪａｖａＢｅａｎｓ（ＥＪＢ）と呼ばれる配置可能なＪａｖａコンポーネントに基づき企業アプリケーションを構築するために、広く採用されているプラットフォーム標準である。我々はＡｐａｃｈｅ（商標登録）をｗｅｂサーバとして使用する。このアプリケーションサーバは、ウェブコンテナ（Ｔｏｍｃａｔ）とＢＩＢコンテナ（ＪＢｏｓｓ）とを含んでいる。ＭｙＳＱＬがバックエンドで動作してデータの永続的な記憶を可能にする。ＰｅｔＳｔｏｒｅ  １．３．２が我々のテストベッドアプリケーションとして配置される。その機能は、店頭、ショッピングカート、商品追跡等からなる。我々は、クライアントエミュレーターを構築し、典型的なユーザ挙動によって生成されたものと同等の負荷を発生させる。エミュレーターは、新たなアカウントの生成、キーワードによる探索、項目詳細のブラウジング、ユーザプロファイルの更新、注文、および照合といった一連の要求を含むいくつかの共通のシナリオに基づいてセッションをシミュレートする各クライアントとの同時接続数を変化させる。
【０１４３】
システム性能は、個々のコンポーネントではなくシステム全体のパラメータに左右される。例えば、最適でないいくつかの構成設定によりｗｅｂサーバに性能障害がある場合、システム全体の性能は、アプリケーションサーバおよびデータベースサーバをどのように調整しても制限されてしまう。しかしながら、システムレベルでの構成調整には、最適化タスクに対してより多くのパラメータが必要になる。例えば、Ａｐａｃｈｅ（登録商標）構成ファイル「ｈｔｔｐｄ．ｃｏｎｆ」では、異なるサービスモジュールおよびパラメータ設定を規定する非コメント行が２４０行以上存在する。ＪＢｏｓｓの主要な構成ファイル「ｊｂｏｓｓ−ｓｅｒｖｉｃｅ．ｘｍｌ」は、パラメータを説明するために属性ノードを７０個以上含んでいる。我々は、実験では、システム性能にとって重要ないくつかの構成パラメータを選択する。それらを表２に示す。パラメータ名の接頭語（「Ｗ．」、「Ａ．」、または「Ｄ．」）は、パラメータがウェブ層、アプリケーションサーバ層、またはデータベース層のどの層からもたらされるものであるかを示している。この表には、それらのデフォルト設定だけでなく、それらの構成の最大値から最小値も示されている。
【０１４４】
人間オペレータが、システム効用値を最大にする構成パラメータを手動で調整するのは容易ではない。ＡｐａｃｈｅモジュールのＷＭａｒＣｌｉｅｎｔｓを例に取ると、パラメータが増加するにつれてシステムスループットは向上するが、ＴＣＰ接続を許容するｗｅｂサーバのプロセスのオーバヘッドにより、システム応答時間も同様に増加する。我々は、システム効用を最大化することができるシステムスループットと応答時間との間の最良のトレードオフを見つける必要がある。
【０１４５】
【表２】
2011504254.tif 000044
【０１４６】
さらに、構成がクライアントの予約接続数を決定するので、Ｗ．ＭａｘＣｌｉｅｎｔｓの最適設定は、ｗｅｂサーバのＷ．ＫｅｅｐＡｌｉｖｅＴｉｍｅＯｕｔのような他のパラメータの値に左右され、その結果、システムが提供できる実際の最大接続数に影響を与える。
【０１４７】
したがって、我々は、テストベッドシステムの最適構成設定を自動的に発見するために、サンプリングベースの最適化法を用いる。我々は、各サンプルについて、システムに対する負荷を発生させて、特定の構成設定下でシステム性能を測定する。この負荷はシステムを訪れている同時ユーザ数として表される。実験では、我々は、最初に、初期の同時ユーザ数を発生させ、その後、システムが最大容量に達するまでさらなるユーザを徐々に追加していく。システムは、その高負荷状況においてしばらくの間動作し、次に、すべてのユーザがシステムを去るまでユーザを徐々に減少させていく。全体の評価期間の間、システムの暖気および冷却が約５分を占め、高負荷の下での動作が１０分以上かかる。なお、通常、高負荷の状況では、システム性能は異なる設定に対して大きく変化するので、高負荷の下で異なる構成を比較することが重要であることに留意されたい。
【０１４８】
我々は、最高のシステム効用を得られる構成を発見する際に、再帰的ランダムサンプリングアルゴリズム（ＲＲＳ）、スマートな山登りアルゴリズム（ＳＨＣ）、および、我々のＤＰＡＳアルゴリズムを比較する。再度述べるが、我々は、アルゴリズムが最小値の代わりに関数の最大値を探索するように、ＲＲＳアルゴリズムおよびＳＨＣアルゴリズムを修正する。数式（７）の効用値計算において、我々は、ミリ秒で表される要求応答時間に対して数式（３）でａ＝０．０１およびｕ＝４００を、システムスループットに対して数式（５）でＸmax＝２００を、要求拒否率に対して数式（６）でｃ＝５０を、それぞれ選択する。
【０１４９】
我々は、λ＝０．２を選択し、「初期のサンプルサイズ」は３０とする。ＤＰＡＳ法は１００番目のサンプルの後で最適領域を特定し、徐々に収束していくつかの探査サンプルを除外する。この方法は、１３５番目の反復で、効用値２．６９８１を持つ最良のサンプルを最終的に発見する。この結果は、ＤＰＡＳ法が３つのアルゴリズムの中で最良の機能を果たすことを実証している。
【０１５０】
表３は、平均スループット、要求応答時間、要求拒否率、および最終効用値に関して、システムのデフォルト構成の性能と、３つの方法で特定された最良の構成の性能と、を示している。これは、３つの方法はすべて、デフォルト構成設定と比較して、システム性能を著しく改善できることを示している。３つの方法の中で、ＳＨＣ法は、最低の応答時間で最適構成を発見するが、システムスループットは最低である。ＲＲＳ法で特定された最良の構成は、ＳＨＣ法の解よりも高いスループットを持っている。しかしながら、ＲＲＳ法は応答時間が相当に増加してしまう。ＲＲＳ法およびＳＨＣ法と比較すると、ＤＰＡＳ法は最高のシステム効用値を持つ解を発見する。ＤＰＡＳ法は、システム応答時間を僅かに犠牲にするだけで、最高のスループットを達成する。要求拒否率も３つの解の中で最も小さい。
【０１５１】
【表３】
2011504254.tif 000045
【０１５２】
新たに評価されたサンプルに基づいて確率を動的に更新する報酬−ペナルティ戦略だけでなく、各パラメータの空間をアクティブにサンプリングする確率モデルにも依存するような、最適なシステム構成を発見する新たな手法を説明してきた。実験結果は、本方法が他の構成探索法に比べてより適切な解を特定することができることを示していた。さらに、本方法は、分散されたウェブベースのシステムや大規模な通信システム等のような、異なる装置にわたって分散された大群の構成パラメータを持つアプリケーションにとって有用な分散型の方法で簡単に行うことができる。
【０１５３】
本書では、システムの最適構成を発見するのに固定の負荷パターンを用いているが、システム性能は、システム負荷の瞬時値に応じた設定を用いて動的に調整することができる。
【０１５４】
以上、分散確率ベースのアクティブサンプリング法を用いて、最適なシステム構成を発見するシステムおよび方法の好ましい実施形態（それらは、例示であって、それに限定されるようことを意図したものではない）を説明したが、上記の教示を考慮して、当業者により修正および変形がなされてもよいことに留意されたい。したがって、添付の請求項に記述された本発明の範囲および思想を逸脱することなく、上記の実施形態において、変更がなされてもよいことが理解されるべきである。このように、特許法により要求された細目および詳細にしたがって本発明の態様を説明したが、特許証によって保護された要求および所望のものは、添付の請求項で説明されている。
【図１】
2011504254.tif 000046
【図２Ａ】
2011504254.tif 000047
【図２Ｂ】
2011504254.tif 000048
【図２Ｃ】
2011504254.tif 000049
【図３】
2011504254.tif 000050
【図４】
2011504254.tif 000051
【図５】
2011504254.tif 000052
【図６】
2011504254.tif 000053
【図７】
2011504254.tif 000054
【図８】
2011504254.tif 000055
【国際調査報告】
2011504254.tif 000056
2011504254.tif 000057
2011504254.tif 000058