(57)【要約】【課題】  リソースの適応割り当てを用いた自律的システム管理の方法を提供する【解決手段】  リソース割り当ての例示的な方法が提供される。少なくとも１つの制御リソースと少なくとも１つの従属パラメータとの間の関係が推定される（２０５）。少なくとも１つの制御リソースのリソース割り当てを調整して少なくとも１つの従属パラメータによって表される所望のシステム目標を達成する。【選択図】      図２
2009522686.tif 000002
【特許請求の範囲】
【請求項１】
リソース割り当ての方法であって、
少なくとも１つの制御リソースと少なくとも１つの従属パラメータとの間の関係を推定するステップと、
前記少なくとも１つの制御リソースのリソース割り当てを調整して前記少なくとも１つの従属パラメータによって表される所望のシステム目標を達成するステップと
を含む方法。
【請求項２】
前記推定ステップ及び前記調整ステップは同時に実行される、請求項１に記載の方法。
【請求項３】
前記推定ステップ及び前記調整ステップは順繰りに実行される、請求項１に記載の方法。
【請求項４】
前記推定ステップ及び前記調整ステップは繰り返される、請求項１に記載の方法。
【請求項５】
前記リソース割り当ては、コンピュータ・システム、製造システム、ロジスティック・システム、又は化学システムのうちの少なくとも１つにおける、少なくとも１つのリソースの割り当てを含む、請求項１に記載の方法。
【請求項６】
前記少なくとも１つの制御リソース、前記少なくとも１つの従属パラメータ、又は前記所望のシステム目標のうちの少なくとも１つは、少なくとも１つのノイズ又は確率的変動を受ける、請求項１に記載の方法。
【請求項７】
前記少なくとも１つの制御リソースのリソース割り当てを調整して前記少なくとも１つの従属パラメータによって表される所望のシステム目標を達成する前記ステップは、
（ａ）前記少なくとも１つの制御リソースの現行割り当てを設定するステップと、
（ｂ）前記現行割り当てにおいて、前記少なくとも１つの従属パラメータの少なくとも１つのサンプル測定値を取得するステップと、
（ｃ）前記少なくとも１つのサンプル測定値を前記現行割り当てと組み合わせてタプルを形成するステップと、
（ｄ）少なくとも１つの以前のタプルに基づいて新しい割り当てを決定するステップと、
（ｅ）前記タプルが停止基準を満たすまで、前記（ａ）、（ｂ）、（ｃ）及び（ｄ）ステップを繰り返すステップと
を含む、請求項１に記載の方法。
【請求項８】
前記タプルに基づいて新しい割り当てを決定する前記（ｄ）ステップは、
前記ステップ（ｃ）を繰り返して複数のタプルを形成するステップと、
前記複数のタプルに基づいて前記新しい割り当てを決定するステップと
を含む、請求項７に記載の方法。
【請求項９】
前記停止基準は、
目標利用率レベルからの所定の間隔と、
逐次近似の最大数と、
経過リアルタイムの最大量と
のうちの１つを含む、請求項７に記載の方法。
【請求項１０】
前記所望のシステム目標は、
前記少なくとも１つの従属パラメータの所望の利用率レベルと、
前記少なくとも１つの従属パラメータの、前記所望の利用率レベルと実際の利用率レベルとの間の間隔メトリックの最小化と、
前記少なくとも１つの従属パラメータの最大化と、
前記少なくとも１つの従属パラメータの最小化と
のうちの１つを含む、請求項１に記載の方法。
【請求項１１】
リソース割り当ての方法を実行するためのプロセッサにより実行される命令を格納する機械可読媒体であって、前記方法は、
少なくとも１つの制御リソースと少なくとも１つの従属パラメータとの間の関係を推定するステップと、
前記少なくとも１つの制御リソースのリソース割り当てを調整して前記少なくとも１つの従属パラメータによって表される所望のシステム目標を達成するステップと
を含む機械可読媒体。
【請求項１２】
前記推定ステップ及び前記調整ステップは同時に実行される、請求項１１に記載の機械可読媒体。
【請求項１３】
前記推定ステップ及び前記調整ステップは順繰りに実行される、請求項１１に記載の機械可読媒体。
【請求項１４】
前記推定ステップ及び前記調整ステップは繰り返される、請求項１１に記載の機械可読媒体。
【請求項１５】
前記リソース割り当ては、コンピュータ・システム、製造システム、ロジスティック・システム、又は化学システムのうちの少なくとも１つにおける、少なくとも１つのリソースの割り当てを含む、請求項１１に記載の機械可読媒体。
【請求項１６】
前記少なくとも１つの制御リソース、前記少なくとも１つの従属パラメータ、又は前記所望のシステム目標のうちの少なくとも１つは、少なくとも１つのノイズ又は確率的変動を受ける、請求項１１に記載の機械可読媒体。
【請求項１７】
前記少なくとも１つの制御リソースのリソース割り当てを調整して前記少なくとも１つの従属パラメータによって表される所望のシステム目標を達成する前記ステップは、
（ａ）前記少なくとも１つの制御リソースの現行割り当てを設定するステップと、
（ｂ）前記現行割り当てにおいて、前記少なくとも１つの従属パラメータの少なくとも１つのサンプル測定値を取得するステップと、
（ｃ）前記少なくとも１つのサンプル測定値を前記現行割り当てと組み合わせてタプルを形成するステップと、
（ｄ）少なくとも１つの以前のタプルに基づいて新しい割り当てを決定するステップと、
（ｅ）前記タプルが停止基準を満たすまで、前記（ａ）、（ｂ）、（ｃ）及び（ｄ）ステップを繰り返すステップと
を含む、請求項１１に記載の機械可読媒体。
【請求項１８】
前記タプルに基づいて新しい割り当てを決定する前記（ｄ）ステップは、
前記ステップ（ｃ）を繰り返して複数のタプルを形成するステップと、
前記複数のタプルに基づいて前記新しい割り当てを決定するステップと
を含む、請求項１７に記載の機械可読媒体。
【請求項１９】
前記停止基準は、
目標利用率レベルからの所定の間隔と、
逐次近似の最大数と、
経過リアルタイムの最大量と
のうちの１つを含む、請求項１７に記載の機械可読媒体。
【請求項２０】
前記所望のシステム目標は、
前記少なくとも１つの従属パラメータの所望の利用率レベルと、
前記少なくとも１つの従属パラメータの、前記所望の利用率レベルと実際の利用率レベルとの間の間隔メトリックの最小化と、
前記少なくとも１つの従属パラメータの最大化と、
前記少なくとも１つの従属パラメータの最小化と
のうちの１つを含む、請求項１１に記載の機械可読媒体。
【請求項２１】
リソース割り当てのためのシステムであって、
（ａ）少なくとも１つの制御リソースと少なくとも１つの従属パラメータとの間の関係を推定するため、及び（ｂ）前記少なくとも１つの制御リソースのリソース割り当てを調整して前記少なくとも１つの従属パラメータによって表される所望のシステム目標を達成するためのシステム・コントローラを含むシステム
【請求項２２】
中央演算処理装置（ＣＰＵ）を備え、前記システム・コントローラに動作可能に接続されたコンピュータ・システムをさらに含み、
前記システム・コントローラは、前記コンピュータ・システム内のＣＰＵの前記リソース割り当てを調整する、
請求項２１に記載のシステム。
【請求項２３】
前記少なくとも１つの制御リソースを制御する機能をもつ複合システムをさらに含む、請求項２１に記載のシステム。
【請求項２４】
前記複合システムは、製造システム、ロジスティック・システム、又は化学システムのうちの１つを含む、請求項２３に記載のシステム。
【請求項２５】
前記システム・コントローラは、前記推定ステップ及び前記調整ステップを同時に実行する、請求項２１に記載のシステム。
【請求項２６】
前記システム・コントローラは、前記推定ステップ及び前記調整ステップを順繰りに実行する、請求項２１に記載のシステム。
【請求項２７】
前記少なくとも１つの制御リソース、前記少なくとも１つの従属パラメータ、又は前記所望のシステム目標のうちの少なくとも１つは、少なくとも１つのノイズ又は確率的変動を受ける、請求項２１に記載のシステム。
【請求項２８】
前記所望のシステム目標は、
前記少なくとも１つの従属パラメータの所望の利用率レベルと、
前記少なくとも１つの従属パラメータの、前記所望の利用率レベルと実際の利用率レベルとの間の間隔メトリックの最小化と、
前記少なくとも１つの従属パラメータの最大化と、
前記少なくとも１つの従属パラメータの最小化と
のうちの１つを含む、請求項２１に記載のシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は一般に、システム・リソース割り当ての分野に関し、より具体的には、測定可能なパフォーマンス目標を満たすためのリソース割り当てによるシステム制御に関する。
【背景技術】
【０００２】
システム管理は一般に、１つまたは複数のリソース割り当てステップを含む。優れたリソース割り当ては、システムの効率的な動作を維持するために不可欠であり、一般に、コストの高いオーバー・プロビジョニングも、またシステム出力の品質を犠牲にする可能性のあるアンダー・プロビジョニングも生じない。実際には、システム・リソースの効果的な割り当ては、システム・パフォーマンス要件及び目標を維持するため又は超えるための重要な部分である。割り当ることができるリソースは、中央演算処理装置（「ＣＰＵ」）、帯域幅、メモリ、データベース・ハンドル、スレッド、及びＣＰＵスケジューラ・プライオリティ、及び入力／出力（「Ｉ／Ｏ」）スケジューラ・プライオリティを含むことができるが、これらに限定されない。
【０００３】
リソースを割り当てる１つのステップは、システム機能性に関する１つ又は複数の所望の目標を定めるステップを含む。ここで用いられる“目標”という用語は、１つ又は複数の測定可能なシステム特性のある機能に対する、所望の上限／下限の最大化／最小化、その達成、又は、それに対する何らかの目標値を達成する試み、を意味する。これらの特性は、システム・リソースの利用率の測定値、システム出力のボリューム又は品質測定値などを含むことができる。リソース間の相互依存性は、目標がシステム・リソース利用率に基づくときに非常に重要となることがある、即ち、１つのリソースの利用率は、１つ又は複数の他のリソースの利用率に依存することがある。
【０００４】
例えばコンピュータ・システムにおいて、システム上で動作しているアプリケーションに用いられるＣＰＵタイムの割合（即ちアプリケーションのＣＰＵ利用率）は、そのアプリケーションにデータを送るために割り当てられたネットワーク帯域幅の量に依存する可能性がある。言い換えれば、この例では、ＣＰＵ利用率とネットワーク帯域幅は、コンピュータ・システムにおける２つの相互依存リソースである。システム目標は、１つのリソースによって表されることが多い。例えば、２つのリソース、ＡとＢを有するシステムを考える。上で規定した様式でリソースＡがリソースＢに依存する場合、リソースＢの割り当てを適応させることによって、リソースＡの利用率を間接的に制御することができる。上の例では、リソースを同等に交換することができ、ネットワーク帯域幅の利用率は、ＣＰＵリソースの割り当てによって制御することができる。
【０００５】
特定のリソースの異なった割り当てが与えられる場合、目標が満たされる度合いを判断するためにシステムの測定値を取得することができる。これらの測定値は、システムのリソースとシステム目標の間の関係を適応“学習する”のに用いることができる（システム目標は幾つかのシステム・リソースの利用率に直接的に依存し得ることを想起されたい）。システムにおけるリソースと目標の間の関係は、通常は、先験的に知るには複雑過ぎて、正確に取得するのは難しい（又は、確率的システムにおけるように不可能である）。従って、これらの関係の学習された推定は、システム目標を達成するためにシステム内のリソース割り当てを決定するときに、正確な関係に対する非常に有用な代用物となり得る。
【０００６】
複合システム、正確には制御方法を必要とするシステムにおいては、測定値は「ノイジー」（即ち、短時間スケールにわたるランダム変動を含む）であり、従って、それらをある程度不正確にする。コンピュータ・システムにおけるこれら測定値の例は、特定のプロセスによるＣＰＵ利用率の量、及び特定のプロセスによるメモリ利用率の量を含む。ＣＰＵ利用率の測定値は、（ａ）オペレーティング・システム（“ＯＳ”）・スケジューラの複雑な動作、（ｂ）頻繁に時間変動するＣＰＵ利用率の量を用いるバックグラウンド・システム・プロセス、及び（ｃ）ＣＰＵ利用率に一時的な変動をもたらし得るプログラム実行の異なる状態、に依存するので、短時間間隔にわたり“ノイジー”となる可能性がある。
【０００７】
さらに、測定値を取得することは、しばしばシステムを乱す可能性がある。例えば、特定のリソース割り当てが与えられたシステムの品質の測定値を取得する例を考える。システムのリソースと品質の間の関係のモデルを構築することは、システムを、多くの異なるリソース割り当てレベルに設定することを必要とする可能性がある。しかしながら、リソース割り当てレベルを変更することによってシステムを乱すことは、特に繰り返し行うとき、目標機能に影響を与えるシステム測定値を含んだ、システム内の１つ又は複数の従属量の振動を生じる可能性がある。
【発明の開示】
【発明が解決しようとする課題】
【０００８】
システム管理の他の方法は、１つまたは複数以下の欠点をもつことが多い。
（ｉ）場当たり（Ａｄ−ｈｏｃ）：多くの方法において、リソース間の関係は既知ではなく推定もされない。そのようなシステムの動作において、リソース割り当て決定は、意図しない効果をもつことがある。この場合、１つのリソースの変更が１つ又は複数の他のリソースに及ぼす効果を考慮に入れないリソース割り当て決定は「場当たり」と呼ぶことができる。
（ｉｉ）非適応（Ｎｏｎ−ａｄａｐｔｉｖｅ）：他の方法は、関係の構造を仮定する古典型的な最適化に基づくリソース割り当て法におけるように、リソースにわたる関係を考慮に入れることを試みることができるが、システムの動作における変更には応答しない。
【課題を解決するための手段】
【０００９】
本発明の１つの態様において、リソース割り当ての方法が提供される。この方法は、少なくとも１つの制御リソースと少なくとも１つの従属パラメータとの間の関係を推定するステップと、少なくとも１つの制御リソースのリソース割り当てを調整して少なくとも１つの従属パラメータにより表される所望のシステム目標を達成するステップとを含む。
【００１０】
本発明の別の態様において、リソース割り当ての方法を実行するための、プロセッサによる実行のための記憶された命令を有する機械可読媒体が提供される。その方法は、少なくとも１つの制御リソースと少なくとも１つの従属パラメータとの間の関係を推定するステップと、少なくとも１つの制御リソースのリソース割り当てを調整して少なくとも１つの従属パラメータにより表される所望のシステム目標を達成するステップとを含む。
【００１１】
本発明のさらに別の態様において、リソース割り当てのシステムが提供される。このシステムは、（ａ）少なくとも１つの制御リソースと少なくとも１つの従属パラメータとの間の関係を推定し、且つ（ｂ）少なくとも１つの制御リソースのリソース割り当てを調整して少なくとも１つの従属パラメータにより表される所望のシステム目標を達成するためのシステム・コントローラを含む。
【発明を実施するための最良の形態】
【００１２】
本発明は、添付の図面と併せて以下の説明を参照することにより理解することができるが、そこで類似の参照番号は類似の要素を識別する。
【００１３】
本発明の例証となる実施形態を以下に説明する。明白にするために、実際の実施の全ての特徴を本明細書中で説明するわけではない。もちろん、何れのそのような実際の実施形態の開発においても、開発者の特定の目標を達成するためには、１つの実施形態から別の実施形態へと変化することになるシステム関連及びビジネス関連の制約に対する準拠といった、多くの実施特有の決定が為されなければならないことを理解されたい。さらに、そのような開発努力は複雑で時間がかかる可能性があるが、それでもなお、この開示の利益を有する当業者には、日常の業務であることを理解されたい。
【００１４】
本発明は様々な修正及び代替的な形態が可能であるが、その特定の実施形態を例示の目的で図面に示し、本明細書で詳細に説明する。しかしながら、特定の実施形態のここでの説明は、本発明を開示される特定の形態に限定することを意図したものではなく、むしろ反対に、本発明は、添付の特許請求の範囲によって規定される本発明の趣旨及び範囲内に入る全ての修正物、同等物、及び代替物を含むものであることを理解されたい。
【００１５】
本明細書で説明されるシステム及び方法は、ハードウェア、ソフトウェア、ファームウェア、専用プロセッサ、又はそれらの組合せの様々な形態で実施することができることを理解されたい。特に、本発明の少なくとも一部は、１つ又は複数のプログラム記憶デバイス（例えばハードディスク、磁気フロッピーディスク、ＲＡＭ、ＲＯＭ、ＣＤ  ＲＯＭ、その他）に有形に具体化され、且つ、プロセッサ、メモリ、及び入力／出力インターフェースを有する汎用デジタル・コンピュータなどの適切なアーキテクチャを備えた任意のデバイス又は機械によって実行可能な、プログラム命令を含むアプリケーションとして実施することが好ましい。さらに、添付の図面に示される構成システム・コンポーネント及びプロセス・ステップの幾つかはソフトウェアにより実施されるのが好ましいので、システム・モジュール（又は方法ステップの論理フロー）の間の接続は、本発明がプログラムされる様式によって異なり得ることを理解されたい。本明細書の教示が与えられると、当業者は本発明のこれら及び類似の実施を企図できることになる。
【００１６】
本発明の例示的な実施形態において、
（ａ）制御リソースと従属パラメータの間の関係を学ぶステップであって、いくつかの制御システムにおいてはシステム目標機能が従属パラメータにより表される、ステップと、
（ｂ）制御リソースのリソース割り当てを調整してシステムを所望の目標点に向かって動かすステップと
を同時に実行する新規のシステム・コントローラが提供される。
【００１７】
これら２つのステップの同時達成は、本発明を従来技術から差別化する。さらに、説明される方法は、最小状態（即ち、ソフトウェア実施における最小メモリ・オーバーヘッド、又はアナログ実施における最小コンポーネント複雑さ）を要し、実行システムに対する数少ない摂動で又は摂動なしに効率的に動作することができる。
【００１８】
ここで説明されるリソース割り当て方法は、当業者によって企図されるような、様々なタイプのシステムのいずれにも適用することができる。単に説明の目的で、ここで説明される例示的なシステムはコンピュータ・システムに関する。しかしながら、本発明はそのように限定されるものではなく、製造システム、ロジスティック・システム、及び化学システムを含むがそれらに限定されない制御可能な任意のシステムに適用できることを認識されたい。
【００１９】
ここで説明される本発明は、１つ又は複数の制御可能なリソースの割り当てが所望のシステム応答（即ち、目標）を達成するように調整される任意の場合に適用できる。さらに、本発明は、リソースと目標の関係に関する従来の既知のモデルには依存しない。
【００２０】
本発明に用いられる用語のいくつかを要約することから始める。複合システムは、アプリケーションを実行するために少なくとも２つのリソースを用いると仮定する。１つのリソースは、ここでは制御リソース（controlled resource）と呼ぶ。制御リソースは、複合システムのユーザがその利用率を制御するリソースである。従属パラメータ（Dependent parameter）はシステムの測定可能な特性であって、そのシステムがいかに良好に所望の目標を満たす又はそれに近づくかを測定するのに用いられる。制御リソースは、目標機能に影響を与える場合、従属パラメータとすることもできる。別のシステム・リソース（即ち、制御リソース以外のシステム・リソース）の利用率レベルは、従属パラメータとすることができ、その場合この他のシステム・リソースは、同等に、従属リソース（dependent resource）と呼ぶことができる。従属パラメータの値は、少なくとも部分的に制御リソースの割り当てに依存する。目標（ｇｏａｌ）という用語は、一般に、任意の測定可能なパフォーマンス目標を指すのに用い、それは、最小化、最大化、又は、制御リソースと従属パラメータを含むことができるパラメータを有する目標機能（goal function）のある所望のレベル近くでのエラーの最小化によって表すことができる。本発明の例示的な実施形態は、モデル（model）と呼ぶ、制御リソースと従属パラメータの間の関係の推定値を構築する。
【００２１】
目標を充足するレベルに関係するデータがノイジー（即ち、不正確）であり得る複合システム内の、１つ又は複数の制御リソースと１つ又は複数の従属パラメータとの間の関係を適応学習する例示的な方法を提示する。その関係は、例えば、制御リソースの好ましい割り当てを判断して、従属パラメータにより測定されるパフォーマンス目標を達成するのに用いることができる。ここで説明される例示的な方法は効率的であり、最小限のデータ記憶を必要とし、それゆえリソースを比較的短時間に割り当てる必要がある複合システムのリアルタイム制御に特に有用であり得る。この方法は、リソース割り当ての変更がシステムに著しい摂動を生ずる可能性のあるシステムに適用されるとき既存技術よりも特に好ましい。この方法は、制御リソース割り当ての調整を必要とする回数を大いに節約するので、その変化の悪影響は、既存の方法におけるよりも小さくなる。
【００２２】
モデル（即ち、制御リソースと従属パラメータの間の推定される関係）は、単純な線形関数、又は何らかの他の設定関数に初期化することができる。方法の各々の逐次近似（即ちステップ）において、制御リソース割り当てが設定され、従属パラメータの１つ又は複数のサンプル測定値がこの制御リソース割り当てにおいて取得され、その結果制御リソース割り当てと従属パラメータの間の関係が学習される。１つより多くのサンプルが取得される場合、そのサンプルは、ノイズ又は不正確なデータの影響を縮小するような方法で組み合わせることができる（例えば、単純平均化、低域フィルタリング）。制御リソース割り当て及び従属パラメータ測定値はタプル（ｔｕｐｌｅ）を形成する。
【００２３】
従属パラメータを測定した後、タプル（即ち、制御リソース割り当て、従属パラメータ測定値）は、実数のｎ次元空間（Ｒｎ）におけるデータ・ポイントとなる。モデル（ｍｏｄｅｌ）は、このタプルの追加により更新される。好ましい実施形態において、前に記録されたタプルのリストは線分で接続して、モデルとして使用するのに適した区分線形関数を形成することができる。しかしながら、区分線形モデルのそのような数個のタプルだけを常に記憶する必要がある。例えば、目標が、制御リソースに伴って単調に変化する単一の従属パラメータの特定の利用率レベル（ここでは「目標レベル」と呼ぶ）を達成する試みを含むとき、２つのタプル、即ち目標レベルの両側の下限値及び上限値（即ち、目標よりも小さな最大観察従属パラメータ測定値をもつタプル、及び目標よりも大きな最小観察従属パラメータ測定をもつタプル）のみを記憶することが必要となる。説明される方法は、次いで、現行の上限値と下限値の間の従属パラメータ測定値を有する新しいタプルを生じると予測される、制御リソースの新しい割り当てを選択することになる。従って、新しい割り当ては次の逐次近似後に上限値又は下限値になるはずである。上の例では、本方法によって計算されるポイントは逐次目標レベルに近づくので、各ステップにおいて、２つの限界値の間の間隔は狭まる。
【００２４】
図１は、特定のプロセスに適用される最初の３つの逐次近似（即ち（ａ）、（ｂ）、及び（ｃ））に関する、本発明の例示的な方法の例示的な展開１００を表す。図１は、各逐次近似における関数Ｃ（Ｂ）の区分線形推定を示す。ＣＴは目標値である。ＬＢは各逐次近似の下限値であり、ＵＢは各逐次近似の上限値である。
【００２５】
停止基準に達すると、目標を達成するために制御リソースの最適値が与えられる。停止基準は、目標値からの所定の間隔、逐次近似の最大数、経過リアルタイムの最大量などを含むことができるが、それらに限定されない。
【００２６】
それに限定はされないが、単純化のために、ストリーム処理（例えばマルチメディア・データをストリーミングすること）を取り扱うコンピュータ・システム上における本発明の例証となる方法を提示する。本発明の別の用途は、ロジスティック又は製造システムにおける容量割り当てを含むことができる。そのようなシステムでは、制御リソースは、システムに付加する容量のレベルとなる。従属パラメータは、観察可能であるがリアルタイム測定値が不正確となり得るロジスティック又は製造システムの品質のレベルである。そのようなシステムの例示的な目標は、システムに対する１組の所望の処理容量割り当てを達成することである。別の目標は、満足な応答時間目標を含むことができる。本発明のさらに別の用途は、化学製品製造及び処理システムにある可能性がある。
【００２７】
ここで、シングル・ノード上でホストされる１組のプロセス（例えば、あるデータ処理プログラムの実行インスタンス）から構成される、典型的なコンピュータ・システムを考える。この例証的な用途においては、制御リソースはネットワーク帯域幅であり、従属リソースはＣＰＵであり、そして目標はノード上のＣＰＵ割り当ての目標数である。
【００２８】
多くの制御リソースと各従属パラメータの間の関係を明示的に推定するのとは反対に、本方法は、各制御リソースと従属パラメータ値の間の関係のみを推定する。この近似は、本方法が非常に迅速で、かつ最小限のデータ記憶を要することを可能にする。制御リソースにわたる相互作用は、２つの仕方、即ち（ａ）使用可能な制御リソースの総量の制約（ｃｏｎｓｔｒａｉｎｔ）を通して、及び（ｂ）測定値のノイズを通して、システムに影響する。
【００２９】
より具体的には、システムの目標は、各従属パラメータと制御リソースの間の未知の関係に依存する。これらの関係の各々を記述するマッピング（ｍａｐｐｉｎｇ）は逐次的に構築され、リソース・レベルの次の値は、所望の値により近い目標メトリック（ｇｏａｌ  ｍｅｔｒｉｃ）の値に至る方向（ｄｉｒｅｃｔｉｏｎ）を調べることにより決定される。
【００３０】
各逐次近似において、従属パラメータのサンプル測定値は、制御リソースの現行割り当てにおいて取得される。これらの測定値がノイジーであり得るときは、複数の測定値を取得することができる。１組のランダム測定値から期待値（ｅｘｐｅｃｔｅｄ  ｖａｌｕｅ）を決定するような統計的手法を用いて、単一の期待値を取得することができる。そのような手法の１つの例は、外れ値（ｏｕｔｌｉｅｒｓ）（即ち測定値の平均からの標準偏差の規定値を超える測定値）を除去して、残りの値の平均を取ることである。
【００３１】
次いで、期待値を用いてモデルを更新する。期待値は、区分線形関数を調整して新しいポイント（即ち、制御リソース−目標値の対）がモデル関数に含まれるようにする。換言すると、区分線形関数は、逐次近似の数に１を加えたのと同数の、異なるスロープを有する線分（ｓｅｇｍｅｎｔ）を有する。
【００３２】
多くの目標機能に関して、関係関数の１つの線分がその下限及び上限の内部に目標値を含むことになるので、２つのポイントのみを各プロセスに対して記憶する必要がある。各々の逐次近似において、この実施例では、上限又は下限は、目標値により近い新しいポイントによって更新されることになる。故に、動作中の区分の２つの極値間の間隔は各ステップにおいて縮小することになる。
【００３３】
Ｃｉ（Ｂｉ）を、未知の関係関数のある値ｉに対する平滑推定値（例えば期待値）とする。そこで、Ｂｉは制御リソースの値を表す。未知の関係Ｃｉ（Ｂｉ）に依存する目標機能は、記号Ｆ（Ｂ）により与えられる。目標機能は、各々が方法により学習されるべきそれ自体の関係Ｃｉ（Ｂｉ）を有する、ｎ個の異なる構成要素ｉ＝１．．ｎを含むことができる。
【００３４】
以下は、本方法の例示的な実施形態における方法のステップであり、ここで、目標機能は、この場合にはＣｉを指す従属パラメータの目標値の達成を試みるものである。
（１）初期設定：目標値は、ｎ次元ベクトルＴで指示する。逐次近似カウンタをｊ＝１に設定する。初期制御リソース値を、所与の開始点Ｂｉに設定するか、又は、初期ポイントが与えられていなければ、あらゆるｉ＝１，．．ｎに対してＢｉ＝ｍａｘｉｍｕｍ＿ｃｏｎｔｒｏｌｌｅｄ＿ｒｅｓｏｕｒｃｅ＿ｃａｐａｃｉｔｙ／ｎと設定する。全てのｉ＝１，．．ｎに対して、初期値Ｃｉ（ＬＢ（ｉ））＝０及びＣｉ（ＵＢ（ｉ））＝１を定める。
（２）メイン・ループ：停止基準に達していなければ、繰り返して、
（ａ）現在のベクトルＢを用いて各ｉの利用レベルをサンプリングする。各プロセス
ｉ＝１，．．ｎに対して、Ｃｉ（Ｂｉ）をプロセスｉの平滑又は期待利用レベルに設定する。
（ｂ）各ｉ＝１，．．ｎに対して、Ｃｉ（ｊ）（Ｂｉ（ｊ）））＞Ｔｉ、目標レベル、である場合には、ＵＢ（ｉ）＝ｊと設定する。反対に、Ｃｉ（ｊ）（Ｂｉ（ｊ）））＜ｔ＿ｉ
である場合には、ＬＢ（ｉ）＝ｊと設定する。
（ｃ）方向検出： 
Ｇｊ（ｂ）＝（Ｃ（ｊ）（Ｂ（ｊ））−Ｔ）＊Ｚ（ｊ）＝（Ｃ（ｊ）（Ｂ（ｊ））−Ｔ）＊Ｍ（ｊ）となる検索方向Ｇｊ（ｂ）を決定し、ここでＭは、目標値Ｔに向かう方向に見積もられた区分線形関数Ｃ（Ｂ）の勾配のベクトルである。即ち、プロセスｉに対して、現行逐次近似カウンタｊが上限である場合、Ｍｉ（ｊ）がポイントＣｉ（ｊ）（Ｂ（ｊ））とＣｉ（ＬＢ（ｉ））（Ｂ（ＬＢ（ｉ）））の間の線分の勾配である。即ち、いくつかの動作中区分ｋに対してＭｉ（ｊ）＝Ａｉ（ｋ）である。反対に、ｊ＝ＬＢ（ｉ）であれば、Ｍｉ（ｊ）は、ポイントＣｉ（ｊ）（Ｂ（ｊ））とＣｉ（ＵＢ（ｉ））（Ｂ（ＵＢ（ｉ）））の間の線分の勾配である。
（ｄ）ニュートン・ステップ：ニュートン・ステップは、ヘッシアンのノルムによってスケールされた勾配により与えられる。目標機能を、プロセス内で分離可能なものとしてモデル化しているので、ヘッシアンのノルムは各々のアプリケーションｉに対して、動作中区分において見積った目的関数Ｆ（ｊ）（Ｂ）の第２導関数により与えられる。これは非常に低コストであり、迅速な計算である。
（ｅ）ステップ・サイズ計算：いくつかのスカラ定数ｖ及びｗに対して、単位ステップ又は発散級数ステップ、Ｓ（ｊ）＝ｗ／（ｊ＋ｖ）を用いる。
（ｆ）更新：Ｂ（ｊ＋１）＝Ｂ（ｊ）−Ｇ（ｊ）（Ｂ）＊Ｓ（ｊ）と設定し、ｊ＝ｊ＋１と
設定する。
【００３５】
図２は、本発明の例示的な実施形態のフロー図を示す。少なくとも１つの制御リソースと少なくとも１つの従属パラメータとの間の関係が推定される（２０５において）。この関係は、少なくとも１つの制御リソースの異なる割り当てが、少なくとも１つの従属パラメータにどのように影響するかの判断を可能にする。少なくとも１つの制御リソースのリソース割り当ては、少なくとも１つの従属パラメータによって表される所望のシステム目標を達成するように調整される。
【００３６】
図３は、少なくとも１つの制御リソースのリソース割り当てを、少なくとも１つの従属パラメータによって表される所望のシステム目標を達成するように調整する、例示的な方法のフロー図を表す。少なくとも１つの制御リソースの現行割当が設定される（３０５）。少なくとも１つの従属パラメータの少なくとも１つのサンプル測定値が、現行割り当てにおいて取得される（３１０）。この少なくとも１つのサンプル測定値が、現行割り当てと組み合わされてタプルを形成する（３１５）。少なくとも１つの以前のタプルに基づいて、新しい割り当てが決定される（３２０）。前のステップ（３０５から３２０まで）は、タプルが停止基準を満たすまで繰り返される（３２５）。
【００３７】
上に開示された特定の実施形態は例証的なものに過ぎず、本明細書の教示の利益を有する当業者には明白なように、本発明は様々なしかし等価な様式で変更及び実施することができる。さらに、添付の特許請求の範囲に説明されるもの以外には、ここに示される構成又は設計の詳細に限定することは意図されていない。従って、上で開示された特定の実施形態は、改変又は変更することができ、そして、全てのそのような変形物は、本発明の範囲と趣旨の範囲内にあると考えられることは明白である。従って、ここで求められる保護は、添付の特許請求の範囲において説明される。
【図面の簡単な説明】
【００３８】
【図１】本発明の１つの実施形態による、特定のプロセスに適用された最初の３つの逐次近似に関する、本発明の例示的な方法の例示的な展開を示す。
【図２】本発明の１つの実施形態による、リソース割り当ての例示的な方法のフロー図を示す。
【図３】本発明の１つの実施形態による、少なくとも１つの制御リソースのリソース割り当てを調整して少なくとも１つの従属パラメータにより表される所望のシステム目標をもたらす例示的な方法のフロー図を示す。
【符号の説明】
【００３９】
１００：本発明の例示的な方法の例示的な展開
【図１】
2009522686.tif 000003
【図２】
2009522686.tif 000004
【図３】
2009522686.tif 000005
【手続補正書】
【提出日】平成21年3月24日(2009.3.24)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
本発明の少なくとも一部は、１つ又は複数のプログラム記憶デバイス（例えばハードディスク、磁気フロッピーディスク、ＲＡＭ、ＲＯＭ、ＣＤ  ＲＯＭ、その他）に有形に具体化され、且つ、プロセッサ、メモリ、及び入力／出力インターフェースを有する汎用デジタル・コンピュータなどの適切なアーキテクチャを備えた任意のデバイス又は機械によって実行可能な、プログラム命令を含むアプリケーションとして実施することが好ましい。
プロセッサ、メモリ、及び入力／出力インターフェースを有する汎用デジタル・コンピュータにより実行されるリソース割り当ての方法であって、
前記メモリに記憶されている少なくとも１つの制御リソースと少なくとも１つの従属パラメータとの間の関係を前記プロセッサが推定するステップと、
前記制御リソースのリソース割り当てを前記プロセッサが調整して前記従属パラメータによって表される所望のシステム目標を達成するステップと
を含む方法。
【請求項２】
前記推定ステップ及び前記調整ステップは前記プロセッサにより同時に実行される、請求項１に記載の方法。
【請求項３】
前記推定ステップ及び前記調整ステップは前記プロセッサにより順繰りに実行される、請求項１に記載の方法。
【請求項４】
前記推定ステップ及び前記調整ステップは前記プロセッサにより繰り返される、請求項１に記載の方法。
【請求項５】
前記リソース割り当ては、コンピュータ・システム、製造システム、ロジスティック・システム、又は化学システムのうちの少なくとも１つにおける、少なくとも１つのリソースの割り当てを含む、請求項１乃至４のいずれかに記載の方法。
【請求項６】
前記制御リソース、前記従属パラメータ、又は前記所望のシステム目標のうちの少なくとも１つは、少なくとも１つのノイズ又は確率的変動を受ける、請求項１乃至５のいずれかに記載の方法。
【請求項７】
前記制御リソースのリソース割り当てを調整して前記従属パラメータによって表される所望のシステム目標を達成する前記ステップは、
（ａ）前記制御リソースの現行割り当てを前記プロセッサにより設定するステップと、
（ｂ）前記現行割り当てにおいて、前記従属パラメータの少なくとも１つのサンプル測定値を前記入力インタフェースを介して取得するステップと、
（ｃ）前記サンプル測定値を前記現行割り当てと組み合わせてタプルを前記プロセッサにより形成するステップと、
（ｄ）少なくとも１つの以前のタプルに基づいて新しい割り当てを前記プロセッサにより決定するステップと、
（ｅ）前記タプルが停止基準を満たすまで、前記（ａ）、（ｂ）、（ｃ）及び（ｄ）ステップを前記プロセッサにより繰り返すステップと
を含む、請求項１乃至６のいずれかに記載の方法。
【請求項８】
前記タプルに基づいて新しい割り当てを決定する前記（ｄ）ステップは、
前記ステップ（ｃ）を繰り返して複数のタプルを前記プロセッサにより形成するステップと、
前記複数のタプルに基づいて前記新しい割り当てを前記プロセッサにより決定するステップと
を含む、請求項７に記載の方法。
【請求項９】
前記停止基準は、
目標利用率レベルからの所定の間隔と、
逐次近似の最大数と、
経過リアルタイムの最大量と
のうちの１つを含む、請求項７又は８に記載の方法。
【請求項１０】
前記所望のシステム目標は、
前記少なくとも１つの従属パラメータの所望の利用率レベルと、
前記少なくとも１つの従属パラメータの、前記所望の利用率レベルと実際の利用率レベルとの間の間隔メトリックの最小化と、
前記少なくとも１つの従属パラメータの最大化と、
前記少なくとも１つの従属パラメータの最小化と
のうちの１つを含む、請求項１乃至９のいずれかに記載の方法。
【請求項１１】
リソース割り当ての方法を汎用デジタル・コンピュータに実行させるコンピュータ・プログラムであり、前記方法は、
少なくとも１つの制御リソースと少なくとも１つの従属パラメータとの間の関係を推定するステップと、
前記制御リソースのリソース割り当てを調整して前記従属パラメータによって表される所望のシステム目標を達成するステップと
を含むコンピュータ・プログラム。
【請求項１２】
前記推定ステップ及び前記調整ステップは同時に実行される、請求項１１に記載のコンピュータ・プログラム。
【請求項１３】
前記推定ステップ及び前記調整ステップは順繰りに実行される、請求項１１に記載のコンピュータ・プログラム。
【請求項１４】
前記推定ステップ及び前記調整ステップは繰り返される、請求項１１に記載のコンピュータ・プログラム。
【請求項１５】
前記リソース割り当ては、コンピュータ・システム、製造システム、ロジスティック・システム、又は化学システムのうちの少なくとも１つにおける、少なくとも１つのリソースの割り当てを含む、請求項１１乃至１４のいずれかに記載のコンピュータ・プログラム。
【請求項１６】
前記制御リソース、前記従属パラメータ、又は前記所望のシステム目標のうちの少なくとも１つは、少なくとも１つのノイズ又は確率的変動を受ける、請求項１１乃至１５のいずれかに記載の機械可読媒体。
【請求項１７】
前記制御リソースのリソース割り当てを調整して前記従属パラメータによって表される所望のシステム目標を達成する前記ステップは、
（ａ）前記少なくとも１つの制御リソースの現行割り当てを設定するステップと、
（ｂ）前記現行割り当てにおいて、前記少なくとも１つの従属パラメータの少なくとも１つのサンプル測定値を取得するステップと、
（ｃ）前記少なくとも１つのサンプル測定値を前記現行割り当てと組み合わせてタプルを形成するステップと、
（ｄ）少なくとも１つの以前のタプルに基づいて新しい割り当てを決定するステップと、
（ｅ）前記タプルが停止基準を満たすまで、前記（ａ）、（ｂ）、（ｃ）及び（ｄ）ステップを繰り返すステップと
を含む、請求項１１乃至１６のいずれかに記載のコンピュータ・プログラム。
【請求項１８】
前記タプルに基づいて新しい割り当てを決定する前記（ｄ）ステップは、
前記ステップ（ｃ）を繰り返して複数のタプルを形成するステップと、
前記複数のタプルに基づいて前記新しい割り当てを決定するステップと
を含む、請求項１７に記載のコンピュータ・プログラム。
【請求項１９】
前記停止基準は、
目標利用率レベルからの所定の間隔と、
逐次近似の最大数と、
経過リアルタイムの最大量と
のうちの１つを含む、請求項１７又は１８に記載のコンピュータ・プログラム。
【請求項２０】
前記所望のシステム目標は、
前記少なくとも１つの従属パラメータの所望の利用率レベルと、
前記少なくとも１つの従属パラメータの、前記所望の利用率レベルと実際の利用率レベルとの間の間隔メトリックの最小化と、
前記少なくとも１つの従属パラメータの最大化と、
前記少なくとも１つの従属パラメータの最小化と
のうちの１つを含む、請求項１１乃至２９のいずれかに記載のコンピュータ・プログラム。
【請求項２１】
リソース割り当てのためのシステムであって、
（ａ）少なくとも１つの制御リソースと少なくとも１つの従属パラメータとの間の関係を推定するステップ、及び（ｂ）前記制御リソースのリソース割り当てを調整して前記従属パラメータによって表される所望のシステム目標を達成するステップを実行するシステム・コントローラを含むシステム。
【請求項２２】
中央演算処理装置を備え、前記システム・コントローラに動作可能に接続されたコンピュータ・システムをさらに含み、
前記システム・コントローラは、前記中央演算処理装置の前記リソース割り当てを調整する、
請求項２１に記載のシステム。
【請求項２３】
前記制御リソースを制御する機能をもつ複合システムをさらに含む、請求項２１に記載のシステム。
【請求項２４】
前記複合システムは、製造システム、ロジスティック・システム、又は化学システムのうちの１つを含む、請求項２３に記載のシステム。
【請求項２５】
前記システム・コントローラは、前記推定ステップ及び前記調整ステップを同時に実行する、請求項２１乃至２４のいずれかに記載のシステム。
【請求項２６】
前記システム・コントローラは、前記推定ステップ及び前記調整ステップを順繰りに実行する、請求項２１乃至２４のいずれかに記載のシステム。
【請求項２７】
前記制御リソース、前記従属パラメータ、又は前記所望のシステム目標のうちの少なくとも１つは、少なくとも１つのノイズ又は確率的変動を受ける、請求項２１乃至２６のいずれかに記載のシステム。
【請求項２８】
前記所望のシステム目標は、
前記少なくとも１つの従属パラメータの所望の利用率レベルと、
前記少なくとも１つの従属パラメータの、前記所望の利用率レベルと実際の利用率レベルとの間の間隔メトリックの最小化と、
前記少なくとも１つの従属パラメータの最大化と、
前記少なくとも１つの従属パラメータの最小化と
のうちの１つを含む、請求項２１乃至２７のいずれかに記載のシステム。
【国際調査報告】
2009522686.tif 000006