(57)【要約】【課題】自動化された、すなわちアプリケーションの実行のパラメータ化における人的介入を最小限に抑えるか、さらには不要にする、ソフトウェアアプリケーションの実行の最適化を提供する。【解決手段】本発明は、情報処理プラットフォーム上でソフトウェアアプリケーションの実行パラメータを最適化する方法において、上記アプリケーションの各実行毎に上記パラメータを繰り返し最適化するステップからなる方法であって、上記アプリケーションの各実行（１）について、上記実行のために使用される上記パラメータと関連付けて、性能測定が行なわれ（２）て記憶され（３）、上記アプリケーションの各実行の開始時点で、上記パラメータの第２のサブセットに対応する上記実行のサブセットに対応する上記記憶された測定からの推論により、上記パラメータの第１のサブセットについて値が決定される（４、６）、方法に関する。【選択図】図１
2020004409.tif 000002
【特許請求の範囲】
【請求項１】
情報処理プラットフォーム上でソフトウェアアプリケーションの実行パラメータを最適化する方法において、前記アプリケーションの各実行毎に前記パラメータを繰り返し最適化するステップからなる方法であって、
−  前記アプリケーションの各実行（１）について、前記実行のために使用される前記パラメータと関連付けて、性能測定が行なわれ（２）て記憶され（３）、
−  前記アプリケーションの各実行の開始時点で、前記パラメータの第２のサブセットに対応する前記実行のサブセットに対応する前記記憶された測定からの推論（６）により、前記パラメータの第１のサブセットについて値が決定される（４、６）、方法。
【請求項２】
前記第１のパラメータサブセットは、前記ソフトウェアアプリケーションと関連付けられた入力／出力インタフェースの最適化パラメータに対応する、請求項１に記載の方法。
【請求項３】
前記第１のパラメータサブセットは、前記ソフトウェアアプリケーションの前記入力／出力を最適化するソフトウェアモジュールの構成パラメータに対応する、請求項２に記載の方法。
【請求項４】
前記第２のサブセットは、アプリケーション識別子などの判別パラメータによって形成される、請求項１ないし３のいずれか一項に記載の方法。
【請求項５】
前記実行のサブセットは、さらに、異常値データフィルタ（５）によって決定される、請求項１ないし４のいずれか一項に記載の方法。
【請求項６】
データは、前記実行のサブセットについての前記性能測定の値の他の値とは異なる挙動を表わす性能測定の値に関係する場合に、異常値とみなされる、請求項５に記載の方法。
【請求項７】
異常値データは、前記サブセットの前記実行に関するデータ間の一対の比較によって決定される、請求項６に記載の方法。
【請求項８】
前記推論のために回帰メカニズムが実現される、請求項１ないし７のいずれか一項に記載の方法。
【請求項９】
情報処理プラットフォーム上でソフトウェアアプリケーションの実行パラメータを最適化するデバイスであって、請求項１ないし８のいずれか一項に記載の方法を実現するソフトウェアモジュールを有する、デバイス。
【請求項１０】
プログラムがデータ処理プラットフォームによりトリガされた場合に請求項１ないし８のいずれか一項に記載の方法を実現するのに好適であるソフトウェア手段を有するコンピュータプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、情報処理プラットフォーム上でのソフトウェアアプリケーション実行の最適化の分野に関する。
【０００２】
これは、詳細には、高性能コンピューティングおよびスーパコンピュータ、とりわけ「エクサスケール」に向かうそれらの発展した分野に適用可能である。
【背景技術】
【０００３】
現在の情報処理プラットフォームのサイズの発展および複雑性の増大には、すでに、それらの使用および管理におけるパラダイムシフトが巻き込まれている（involve）。実際、最適な演算状態の維持に巻き込まれる情報の量から見て、次第に人間の介入が困難であることが判明しつつある。
【０００４】
さらに、将来のエキサスケールコンピュータ、すなわちエキサフロップのオーダの出力を目指すコンピュータは、はるかに多数の計算ノードを取り入れることになり、高いデータの一貫性（consistency）が巻き込まれスケーリングがかなり制限されるＰＯＳＩＸ並列ファイルタイプのシステムの現在のデータのアクセス方法は、もはや使用不可能になる。
【０００５】
代替的な解は存在する。一部は、ＰＯＳＩＸモデルの拡張を模索している。すなわち、２０１２年、ＩＥＥＥ  ２８ｔｈ  Ｓｙｍｐｏｓｉｕｍ  ｏｎ  Ｍａｓｓ  Ｓｔｏｒａｇｅ  Ｓｙｓｔｅｍｓ  ａｎｄ  Ｔｅｃｈｎｏｌｏｇｙ（ＭＳＳＴ）中のＮ．Ｌｉｕ、Ｊ．Ｃｏｐｅ、Ｐ．Ｃａｒｎｓ、Ｃ．Ｃａｒｏｔｈｅｒｓ、Ｒ．Ｒｏｓｓ、Ｇ．Ｇｒｉｄｅｒ、Ａ．ＣｒｕｍｅおよびＣ．Ｍａｌｔｚａｈｎ著「Ｏｎ  ｔｈｅ  ｒｏｌｅ  ｏｆ  ｂｕｒｓｔ  ｂｕｆｆｅｒｓ  ｉｎ  ｌｅａｄｅｒｓｈｉｐ−ｃｌａｓｓ  ｓｔｏｒａｇｅ  ｓｙｓｔｅｍｓ」に記載の通りの「バーストバッファ」タイプの技術を特に挙げることができる。
【０００６】
他の解は、例えば、２００３年、ＩＥＥＥ  Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ  Ｍａｇａｚｉｎｅ、４１（８）：８４〜９０中のＭ．Ｍｅｓｎｉｅｒ、Ｇ．Ｒ．ＧａｎｇｅｒおよびＥ．Ｒｉｅｄｅｌ著「Ｏｂｊｅｃｔ−ｂａｓｅｄ  ｓｔｏｒａｇｅ」に記載のオブジェクトストレージ、または、例えば、２０１７年、ａｒＸｉｖ  ｐｒｅｐｒｉｎｔ  ａｒＸｉｖ：１７１２．００４２３中のＢｒｅｉｔｅｎｆｅｌｄ、Ｍ．Ｓｃｏｔら著「ＤＡＯＳ  ｆｏｒ  Ｅｘｔｒｅｍｅ−Ｓｃａｌｅ  Ｓｙｓｔｅｍｓ  ｉｎ  Ｓｃｉｅｎｔｉｆｉｃ  Ａｐｐｌｉｃａｔｉｏｎｓ」に記載のＤＡＯＳなどの他のアクセスモデルを提供している。
【０００７】
しかしながら、これらの代替的な解には、インスタンス化される（instantiated）対象のアプリケーションの挙動に適合した特定のパラメータを用いて、オンデマンドで実現することが巻き込まれる。今日の技術的現状では、このパラメータ化は、完全に手作業で行なわれ、ユーザに依存するが、ユーザは、極めて稀にしかそれを定義するスキルをもたない。
【０００８】
したがって、この自動化を可能にするためには、最も関連性の高い入力／出力高速化（input-output acceleration）ストラテジを適用し、かくしてスーパコンピュータの演算の最適化に寄与する目的で、アプリケーションの挙動を極めて高度に理解することが不可欠である。
【発明の概要】
【発明が解決しようとする課題】
【０００９】
本発明の目的は、上述の欠点を少なくとも部分的に是正する方法を提供することにある。
【００１０】
詳細には、本発明によれば、アプリケーションおよびその挙動に関していかなる知識がなくても、先験的情報に基づかなくてもよい。取扱うべきアプリケーションは、その挙動が極めて不均一であり得ることから、それらの特定の挙動のモデル化は、非常に複雑であり得る。そこで、本発明では、ブラックボックスタイプのメカニズムを使用し、これにより、より容易な利用およびより広い応用範囲が可能になる。
【００１１】
より詳細には、本発明は、自動化された、すなわちアプリケーションの実行のパラメータ化における人的介入を最小限に抑えるか、さらには不要にする、ソフトウェアアプリケーションの実行の最適化を提供することを目的としている。
【課題を解決するための手段】
【００１２】
この目的で、本発明は、情報処理プラットフォーム上でソフトウェアアプリケーションの実行パラメータを最適化する方法において、アプリケーションの各実行毎にパラメータを繰り返し最適化するステップからなる方法であって、
−  アプリケーションの各実行について、実行のために使用されるパラメータと関連付けて、性能測定が行なわれて記憶され、
−  アプリケーションの各実行の開始時点で、パラメータの第２のサブセットに対応する実行のサブセットに対応する記憶された測定からの推論により、パラメータの第１のサブセットについて値が決定される、方法を提供する。
【００１３】
好ましい実施形態によると、本発明は、別個に、または互いに部分的に組み合わせた形で、または互いに全面的に組み合わせた形で使用可能である以下の特徴の１つまたは複数を有する。
−  第１のパラメータサブセットは、ソフトウェアアプリケーションと関連付けられた入力／出力インタフェースの最適化パラメータに対応する。
−  第１のパラメータサブセットは、ソフトウェアアプリケーションの入力／出力を最適化するソフトウェアモジュールの構成パラメータに対応する。
−  第２のサブセットは、アプリケーション識別子などの判別パラメータによって形成される。
−  実行のサブセットは、さらに、異常値データフィルタによって決定される。
−  データは、実行のサブセットについての性能測定値の他の値とは異なる挙動を表わす性能測定値に関係する場合に、異常値とみなされる。
−  異常値データは、サブセットの実行に関するデータ間の一対の比較によって決定される。
−  推論のために回帰（regression）メカニズム（線形または非線形）が実現される。
【００１４】
本発明の別の態様は、情報処理プラットフォーム上でソフトウェアアプリケーションの実行パラメータを最適化するデバイスであって、前述の方法を実現するソフトウェアモジュールを有するデバイスに関する。
【００１５】
本発明の別の態様は、情報処理プラットフォームによりトリガされた場合に前述の方法を実現するのに好適であるソフトウェア手段を有するコンピュータプログラムに関する。
【００１６】
本発明の他の特徴および利点は、添付図面を参考にしながら一例として示されている本発明の好ましい実施形態についての以下の説明を読了した時点で明らかになるものである。
【図面の簡単な説明】
【００１７】
【図１】本発明の一実施形態に係る最適化ループを、概略的かつ機能的に表す図である。
【図２ａ】本発明の一実施形態に係るテスト結果を概略的に表す図である。
【図２ｂ】本発明の一実施形態に係るテスト結果を概略的に表す図である。
【図３ａ】本発明の一実施形態に係る例を概略的に示す図である。
【図３ｂ】本発明の一実施形態に係る例を概略的に示す図である。
【図４】本発明のさまざまな実施形態と関連付けられた異なる態様を概略的に示す図である。
【図５】本発明のさまざまな実施形態と関連付けられた異なる態様を概略的に示す図である。
【図６】本発明のさまざまな実施形態と関連付けられた異なる態様を概略的に示す図である。
【図７】本発明のさまざまな実施形態と関連付けられた異なる態様を概略的に示す図である。
【図８】本発明のさまざまな実施形態と関連付けられた異なる態様を概略的に示す図である。
【発明を実施するための形態】
【００１８】
以下で、「ジョブ（job）」とは、情報処理プラットフォーム上でのアプリケーションの実行モダリティ（モード）（modalities of execution of an application）を定義するメタデータセットからなる抽象的表現を意味する。これらのメタデータは、特に以下のものを含む。
−  アプリケーション識別子（実行可能バイナリ（executable binary）の名前、スーパコンピュータ上のアプリケーション実行ツールに由来する情報、アクセスされるファイルなど）
−  使用されるハードウェアトポロジ（hardware topology）（計算および記憶）
−  実行コンテキストのパラメータ、特に、当該ソフトウェアアプリケーションと関連付けられた入力−出力インタフェースの最適化パラメータ。
【００１９】
所与の「ジョブ」について、２つの実行（または「ラン（runs）」）によって、データに対する同時アクセス、他のアプリケーション実行による処理リソースの使用、などに関係し得る異なる挙動がもたらされることになる。
【００２０】
本発明によると、１つのジョブのメタデータの部分をその実行のために自動的に最適化することが探求されている。この最適化は、１つまたは複数の性能測定により表現される既定の基準（criterion）に従って行なわれる。
【００２１】
最適解は、目的関数の性能値が、１つの既定の基準と関連付けられた最小または最大（最適）値である状況に対応する。例えば、高性能（または「Ｈｉｇｈ  Ｐｅｒｆｏｒｍａｎｃｅ  Ｃｏｍｐｕｔｉｎｇ」を略してＨＰＣ）アプリケーションの場合、最少化すべき性能基準の良い例は、総実行時間である。
【００２２】
ユーザは、１つのジョブを開始する場合、そのジョブの定義に対応する全てのメタデータを確定せ（fix）ず、そのうちのいくつかをフリー（free）のままに残すことを選択することができる。
【００２３】
典型的な事例では、ユーザは、特定のアプリケーションを開始することを望む。したがって、メタデータ「アプリケーション識別子」は確定される。
【００２４】
他方では、ユーザに使用すべきハードウェアトポロジについて先験的な考えが全く無い場合、ハードウェアトポロジーメタデータは、フリーのままに残され得る。同様にして、ユーザにコンテキストに適応する入力−出力インタフェースの構成に関する考えが全く無い場合、入力−出力インタフェースの最適化パラメータは、フリーのままに残される。
【００２５】
この場合、自己最適化方法は、ユーザに、このようにフリーのまま残されたパラメータについて、これらのパラメータを任意に確定した場合に比べてアプリケーションの実行を改善できるようにするはずの値を提供する。
【００２６】
本発明は、先験的にジョブの挙動をモデル化しようとすることが不可能であるか、または充分効果的でないという原則に基づいている。したがって、ジョブを１つの「ファミリ」として記述または特徴付ける１組の実行の挙動を帰納的に観察するために測定を行なうことが目的とされる。
【００２７】
１つのアプリケーションファミリは、共通のメタデータを有する一組の実行に対応する。例えば、同じアプリケーション名および同じハードウェア展開トポロジを有するジョブに由来する全ての実行が、１つのファミリを形成する。
【００２８】
したがって、観察中に、ファミリによって、フリーパラメータに関して使用可能な空間の作成がオファーされる。実行の数が増えれば増えるほど、フリーパラメータがとる値の空間は、関係するファミリに関する性能値の変動をより良く表現するものとなる。
【００２９】
フリーパラメータのために最適な値を探索することは、繰り返し処理（iterative process）である。各々の繰り返しは、異なるファミリの特徴に関する知識を全体として豊富にする。
【００３０】
同様に、パラメータ空間を効率良く（すなわち非網羅的に）走査するために、新たな実行の開始毎に、最適値の探索を行なうことができる。この最適値は、恐らくは大域的なものではないが、この「局所」解は、その後、次の繰り返しおよびこのファミリの次のジョブ実行のためのフリーパラメータの新たな推論に再投入され得る。
【００３１】
こうして、現実に各繰り返し毎に推論を行なうことにより、連続的な改善ループおよび大域的最適値に向かう収束を創出することが可能になる。
【００３２】
図１は、最適化ループを描いている。
【００３３】
最初に、ステップ１において、実行パラメータを用いてアプリケーションが実行される。
【００３４】
これらの実行パラメータは、ユーザにより確定されたパラメータを含む。これらの確定パラメータは、特に判別（discriminant）パラメータ、例えば、実行すべきアプリケーションの識別子などを含み得るが、例えば、基盤となるインフラストラクチャのトポロジ構成などの他のパラメータを確定することも可能である。
【００３５】
実行パラメータは、同様に、フリーパラメータも含み、その値の最適化が求められる。これらのフリーパラメータは、後続する繰り返しのためにベース２内に記憶された測定からの推論により決定され得る。最初の繰り返し中、値は、ユーザにより定められてもよいし、あるいは、無作為にまたは「デフォルト」値に基づいてといった手段を含めた他の手段により決定されてもよい。
【００３６】
本発明の一態様によると、確定メタデータとフリーメタデータ（パラメータ）との間の選択は、ユーザに委ねられる。この場合、本発明は、ユーザが自ら確定することを望まなかったパラメータの値の最適化を目的とする。
【００３７】
本発明によると、実行（またはジョブ）の全てまたは一部が監視される。性能測定がステップ２で行なわれ、結果は、対象の実行のために使用されたパラメータと関連付けて、ベース３内に記憶される。
【００３８】
これらの性能測定は、ジョブの実行中にリアルタイムで、またはひとたびジョブが完了した時点で帰納的に行なわれてよい。これらの測定は、実行時間、入力−出力数、入力−出力にかかった時間、などを含み得る。
【００３９】
データベース３は、性能測定が実行パラメータ（確定およびフリー）の値と関連付けられるような形で構造化される。したがって、データは、性能測定とジョブに関連付けられたメタデータとの両方を含む。
【００４０】
ステップ４において、ベース３内に記憶されたデータは、確定メタデータ（またはパラメータ）に基づいて抽出を行なう上で使用される。結果は、確定メタデータに対応する、または、換言するとユーザが実行を望むジョブのファミリに対応する、実行に関連するデータサブセット（性能測定、メタデータ）である。したがって、このサブセットは、フリーパラメータの推論の実施に関連する。
【００４１】
ステップ６において、これらのフリーパラメータは、先に抽出されたサブセットに対応する性能測定値から推論される。
【００４２】
可能なかぎり最も有効な推論を生みだすためには、考慮されるファミリ内で最も関連性の高い実行を優先的に使用することが有用であり得る。実際、一部の実施形態では、そのファミリの残りの実行と相違していることから、異常値（outliers）とみなされ得る。
【００４３】
この選択またはフィルタリングは、ファミリのデータの抽出４と推論６との間に挿入されるオプションのステップ５において行なわれ得る。
【００４４】
推論は、この繰り返しまでに獲得した知識に基づいて、最良解に対応するフリーパラメータのための値を提供することを目的とする。これは、局所最適値であり、大域的最適値に向かって繰り返しが行なわれるにつれて収束する。
【００４５】
推論を実現するためにさまざまなメカニズムが可能であり、そのうちのいくつかには、当業者であればアクセス可能である。
【００４６】
特に、推論は、線形または非線形回帰メカニズムにより実現可能である。これらのメカニズムについては、入力−出力に関係する実行パラメータに適用される一実施形態の中で詳述されるが、一般に、他のタイプの実行パラメータにもこれらのメカニズムを適用することが可能であり得る。
【００４７】
入力−出力パラメータを最適化するための実施形態
一実施形態によると、フリーパラメータは、少なくとも部分的に、対象のソフトウェアアプリケーションに関連付けられた入力−出力インタフェースの最適化パラメータに対応する。
【００４８】
一部の状況下では、入力−出力を最適化するためのソフトウェアモジュールを使用することができる（または「アクセラレータ」）。一実施形態によると、この場合、フリーパラメータは、これらのソフトウェアモジュールの構成パラメータ（またはパラメータ）に対応し得る。
【００４９】
ＨＰＣアプリケーションは、その実行時間の大部分を入力／出力の実施に充てる。その主たる原因は、処理されるデータの量そのものである。すなわち、データを交換するために使用されるネットワークは有限帯域幅を有することから、読取りおよび書込み時間は、理論上の最小値未満でないことがある。しかしながら、他の要因も有意な影響を有し得る。例えば、２つのアプリケーションの同時実行は、共通記憶リソースに対するアクセスの競合（access conflicts）をひき起こす可能性があり、これは、性能に影響を及ぼすことになる。アプリケーションがその入力／出力を行なう方法も同様に、非常に多数の「小規模」演算の処理を必要とすることによって記憶用機器を飽和状態にする（saturates）場合、性能に劇的な影響を及ぼし得る。
【００５０】
一実施形態によると、高性能コンピューティング（High Performance Computing；ＨＰＣ）アプリケーションによるデータに対するアクセスのプロファイリング専用の、実行されるアプリケーションを監視するためのデバイスが設置される。これによって、ＨＰＣクラスタ上でのプログラムの実行の進捗に関する多くのメトリック（metric）（ＩＯ量、ＩＯ時間、アクティブプロセスの数など）をリアルタイムで記録することが可能になる。収集されたメトリックセットは、アプリケーションの動的挙動の記述をもたらし、これは、自動パラメータ化方法（automatic parameterization methods）の開発のための確かな基礎を成す。
【００５１】
以下で説明する実施形態においては、入力−出力インタフェースに関係するフリーパラメータのみを推論すべきであることが考慮される。
【００５２】
このような場合には、フィルタ４が、開始すべきジョブと同じ判別子（同じアプリケーション識別子）および同じトポロジを有する全ての実行を集約する。このステップは、単にデータベース３内の確定メタデータをクエリすることにより実行を選択することからなるにすぎないため、ここでは詳述しない。
【００５３】
分類５および推論６のステップについて、より詳細に説明する。
【００５４】
分類ステップ５は、推論ステップ６と関連性の無い実行を検出することを目的とする。次の２つの主要な原因が、このステップにおける実行の排除を導く可能性がある。
−  入力−出力（Ｉ／Ｏ）の挙動が、同じファミリの他の実行と比べて非常に異なるものである。この場合、それは、異常値として分類される。
−  実行のサブセットの入力−出力、Ｉ／Ｏ、挙動が、初期の安定した挙動からゆっくりと発散する（diverges）。この実行セットが発散するジョブは、このとき、不安定なものとして特徴付けされる（それは、開発中のアプリケーション、ハードウェア性能の緩慢な変化などであり得る）。
【００５５】
推論の前に排除されなければならないこれらの異常値の実行を検出するために、分類段階は、そのＩ／Ｏ挙動に関する全ての利用可能なデータを使用する。
【００５６】
ＩＯの挙動を表現するこれらのデータは、収集されたメトリックのセットである。
【００５７】
提供される１つの分類方法は、同じファミリに属する全ての実行の一対の比較に基づくものである。したがって、各々の実行対について、収集された測定は、本明細書の以下の部分で説明する統計学的方法を使用することによって比較される。この比較は、結果として、比較された実行の一対あたりの性能測定と同じ数の距離をもたらし、これらの距離はその後集約されて、２つの実行間の一意の距離が得られる。
【００５８】
最終的に、Ｎ個の実行間の全ての比較に関係する距離行列Ｎ×Ｎは、階層分類の創出を可能にする。
【００５９】
収集された測定は、１つの特徴（例えば、読取り量、１Ｍｂ〜４Ｍｂのサイズの書込み時間など）のプリズムを通した実行のＩＯ挙動の経時的（例えば５秒スロットあたりの）推移を表わす。したがって、各々の測定は、経時的に推移する値のシーケンスに対応し得る。
【００６０】
分類に対する従来のアプローチでは、スカラ特徴を測定シーケンスから抽出することができると考えられる。これにより、この場合、全ての特徴ベクトル（feature vectors）が同じ次数（dimension）（すなわち抽出された特徴の数）を有することから、異なる実行の特徴ベクトル間の距離を計算することが可能になる。
【００６１】
逆に、実行を分類するために選択されたアプローチにおいては、直接２つずつシーケンスを比較することが選ばれた。しかしながら、実行は、必ずしも類似の総持続時間を示さない。このため、シーケンスをフォーマッティングして、このフォーマットを受け入れる統計学的方法（本明細書で後述）によりこれらのシーケンスを比較できるようにすることが求められる。
【００６２】
「ｇｏｏｄｎｅｓｓ−ｏｆ−ｆｉｔ（適合度）」ノンパラメトリック仮説検定（non-parametric hypotheses test）の使用は、２つのサンプルを比較する優れた手段である。コルモゴロフスミルノフおよびクラメールフォンミーゼスの検定は、この目的のための優れた候補であり、本明細書中で詳しく後述される。これらの２つの検定では、比較されるサンプルの同じフォーマット（formatting）、すなわち累積分布関数（Cumulative Distribution Function；ＣＤＦ）が使用される。
【００６３】
図２ａは、正規の法則（正規分布）（normal law）の確率密度関数（Probability Density Function；ＰＤＦ）およびＣＤＦを描き、したがって、ＣＤＦはＰＤＦの累積バージョンである。ＣＤＦは、増加し（increasing）、０と１との間に制限される（bounded between 0 and 1）という点に留意されたい。図２ｂは、ＣＤＦと連続法則からのサンプルを表わす離散インスタンスである実験上の（empirical）ＣＤＦとの差を描いている。
【００６４】
ＩＯ測定シーケンスに基づき、これらのシーケンスのデータの２つの表現方法を、実験上のＣＤＦの形で抽出することができる。
【００６５】
「時間（temporal）」ＣＤＦ
実験上のＣＤＦは、正規化されたヒストグラム（すなわち実験上のＰＤＦ）の累積バージョンに対応する。このフォーマットは、ＩＯ測定の収集方法に特に呼応する（echoes）ものである。実際、５秒スロットあたりで、各測定に関連付けられたイベント（events）が統合され（integrated）、こうして、各「ビン」の間隔が５秒のタイムスロットとなるヒストグラムを形成する。
【００６６】
本明細書の残りの部分では、考慮されるデータが常にサンプルに由来することから、実験上のＣＤＦは、誤称により単にＣＤＦと呼ばれるという点に留意されたい。
【００６７】
図３ａは、「アクティブＩＯプロセス」を測定するためのデータシーケンスを表わす。
【００６８】
図３ｂは、先に説明したシーケンスに対応するＣＤＦを例示する。この表現を用いて、以下では、異なるジョブについて測定のシーケンス間の距離を得ることができるということを見ていく。
【００６９】
「値」ＣＤＦ
１つのシーケンスのデータを表わすより古典的な方法は、データの順序は重要でない単一のサンプルとしてシーケンスを考慮することにある。この場合、ＣＤＦは、このシーケンス内に含まれる値の分布を表わす。
【００７０】
図４は、図３ｂの原初のシーケンスについて、この場合において得られたＣＤＦを表わす。
【００７１】
このバージョンでは、シーケンスの時間的側面がもはやＣＤＦによって再転写され（retranscribed）ないということに留意されたい。
【００７２】
２つずつ（two-by-two）（一対（pairwise））の比較
先に記述した統計学的表現（ＣＤＦ）を使用することによって、２つのＣＤＦを比較し、こうしてこれらのＣＤＦ間の距離を得るために、ノンパラメトリック仮説検定を使用することができる。
【００７３】
コルモゴロフスミルノフおよびクラメールフォンミーゼス検定は、２つのサンプルをそれらのＣＤＦを使用して比較することを可能にする。
【００７４】
コルモゴロフスミルノフ検定
２サンプルコルモゴロフスミルノフ検定は、２つのデータサンプルを直接比較して、それらのサンプルが同じ分布法則に由来するか否かを、この法則についての知識の如何に関わらず決定する。
【００７５】
当該検定は、つねに、それぞれが次数ｎ１とｎ２との２つのＣＤＦ  ＦｍとＭｓとの間の最大の距離Ｄｓを探索する（The test always searches for the maximum distance Ds between two CDFs Fm and Ms, of size n1 and n2 respectively）。
＜数式１＞
【数１】
2020004409.tif 000003
【００７６】
図５は、この２サンプルバージョンの原理を示す。
【００７７】
統計値Ｄｓから、テスト対象の２つのＣＤＦが同じ分布法則、すなわち
＜数式２＞
【数２】
2020004409.tif 000004
に由来する、ｐ−Ｖａｌｕｅと呼ばれる確率ｐｓを計算することが可能である。なお式中、
【数３】
2020004409.tif 000005
およびｎ＝ｎ１・ｎ２である。
【００７８】
クラメールフォンミーゼス検定
コルモゴロフスミルノフ検定の代替案として知られるこの検定は、同じ使用手順に従って同じ仮説をテストする。クラメールフォンミーゼス検定は、統計値Ｄｓを生成するために使用される基準が異なっている。コルモゴロフスミルノフ検定が２つのＣＤＦ間の最大距離を探索していたのに対して、クラメールフォンミーゼス検定は、２つのＣＤＦ間の差の積分を計算する。
【００７９】
Ｄｓは、２つの実験上のＣＤＦ、Ｆｍ＝｛ｘ１，．．．，ｘＮ｝およびＭｓ＝｛ｙ１，．．．，ｙＭ｝を考慮に入れることによって計算され、
＜数式３＞
【数４】
2020004409.tif 000006
式中Ｕは
【数５】
2020004409.tif 000007
であり、さらに式中ｒｉおよびｓｊは、それぞれｘｉおよびｙｊの組合せサンプル内のランクである（with ri and sj respectively the ranks in the combined sample of xi and yj）。２つのサンプルが同じ分布法則からのものである確率も、同様に、クラメールフォンミーゼス統計から演繹される。
【００８０】
クラメールフォンミーゼス統計の計算は、コルモゴロフスミルノフ検定の計算に比べてより多くの計算を必要とするという点に留意されたい。
【００８１】
距離計算
前述の検定のうちの一つを使用することにより、２つのジョブ間の距離を明らかにするための測定が提供される（実際には、４つの異なる距離測定の可能性、すなわち２×ＤｓまたはＰｓさえ提供される）。
【００８２】
Ｎ個のジョブのセットについて、１つの測定における複数のシーケンスの２つずつの比較により、ジョブ間の２つずつの距離のＮ×Ｎの行列を得ることが可能になる。こうして、ＩＯＩにより収集されたＩＯ測定（例えば６８の異なる測定）を全て比較することにより、各々Ｎ×Ｎという次数の６８の距離行列を得ることができる。
【００８３】
階層分類
階層分類は、データ解析において広く使用されている自動分類方法である。ｎ個の個（個別要素）（individuals）のセットΩから、その目的は、これらの個を一定数のクラスに分配することにある。階層の性質は、この性質により、アルゴリズムの全てのステップにおいて以下の特性を満たすクラスのセットである階層Ｈを生成するという事実から規定される（The hierarchical qualifier comes from the fact that it produces a hierarchy H, the set of the classes at all the steps of the algorithm, which satisfies the following properties）。
−  Ω∈Ｈ：階層の最上位において、単一のクラスを得るためにグループ化される場合、全ての個は、一緒にグループ化される。
−  ∀ω∈Ω、｛ω｝∈Ｈ：階層の最下位で、全ての個は単独である。
−  ∀（ｈ、ｈ’）∈Ｈ２、この場合、ｈ∩ｈ’＝φまたはｈ⊂ｈ’またはｈ’⊂ｈ：階層グループにおける２つのクラスが考慮される場合、これらのクラスが共通の個を共有しないか、またはこれらのクラスの一方が他方を含む（またはその逆）。
【００８４】
当該方法は、全ての個間の類似性（または非類似性）の測定が存在すると仮定している。そこから出発して、以下の２つのやり方が可能である。
−  全ての個が１つのクラスの中で単独であり、それからより大きくなるクラスの中に集められる状況を前提とする、上昇型（または凝縮型）階層分類（Ascendant (or Agglomerative) Hierarchical Classification；ＡＨＣ）。
−  逆に、下降型階層分類（Descendant Hierarchical Classification；ＤＨＣ）は、全ての個を含む単一のクラスから出発して、この初期グループを、全ての個が隔離されるまで繰り返し増大する数のクラスに分割する。
【００８５】
樹形図（dendrogram）は、階層分類のグラフィック表現である。それは、多くの場合２分木として描かれ、その葉は、横軸上に整列された個である。２つのクラスまたは２つの個が遭遇するとき、垂直線が２つのクラスの横座標から縦座標まで引かれ、次に、これらの線は、水平な線分によって連結される。
【００８６】
図６は、樹形図の一例を描いており、これにより、選択された閾値（水平線）について、３つのクラスを識別することが可能になる。
【００８７】
樹形図は、分類すべきＮ個の要素の２つずつの距離を含む距離行列から構築される。要素間の距離は、２つのノードを連結する枝の長さによって樹形図上に記されている。したがって、２つの要素（すなわち葉）間の距離は、葉のレベルと２つの葉を連結するノードとの間の垂直方向の距離によって表わされる。
【００８８】
距離行列の集約（aggregation）
この事例においては、特定のメトリックについて２つずつのジョブ間の距離を各々含む６８の距離行列（またはより一般的には、同数の収集された性能測定）が存在する。ジョブセットを分類するための樹形図を構築する目的で、測定に応じて距離行列を集約させ、ジョブ間の「総」距離を含むことになる単一の測定を得なければならない。
【００８９】
次節で分類結果を示すために選択された距離行列の集約は、６８の距離行列の単純な総和である。
【００９０】
しかしながら、好適な熟練した知識があれば、集約段階は、一定の測定のみを使用し、かつ／または最も関連性の高いものを重みづけする好機であり得る。
【００９１】
分類
「総」距離行列がひとたび生成されると、ジョブを、階層分類法を用いて分類することができる。図７は、前述のジョブ間の距離測定を用いた、９０の実行の分類結果を描く。
【００９２】
この実行セットは、３つの異なるジョブから生成された。しかしながら、図７の樹形図は、４つの異なるクラス（Ａ、Ｂ、Ｃ、Ｄ）を明らかにしている。この結果を解析することにより、クラスＣおよびＤの両方が単一のジョブからの実行を含んでいることが識別された。この実行セットの２つのクラスへの分離は、使用された閾値（黒色線）の選択によって説明可能である。
【００９３】
閾値がわずかに高ければ、２つのクラスＣおよびＤを単一のものとみなすことが可能になる。同様にして、閾値がわずかに低ければ、５つのクラスを識別することになったはずである。
【００９４】
したがって、これらの階層分類法を使用する上での問題点の１つは、最終的に識別されるクラスの数に大きな影響を及ぼすことを理由として、この閾値の選択にある。一般的に採用されている一つの解は、２つの要素間の最大距離との関係において閾値の値を設定すること（例えば最大距離の７０％）からなる。しかしながら、クラスの要素が異質な距離（heterogeneous distances）（例えばクラスＤ対クラスＢ）を有する事例においては、要素を適切に分類することを可能にする閾値を見い出すことが困難である。
【００９５】
ただし、この困難さは、異常値データの検出に焦点をあてている本使用事例については、比較的少ないものである。実際、分類において使用される実行セットは、事実上１つのジョブファミリに由来し、したがって、これらの実行は、全て単一のクラスにグループ化されるべきである。したがって、異常値実行は、例えば、全ての実行間の平均または中央距離に基づいて、相対閾値を用いて容易に識別可能である。
【００９６】
説明してきた実行の分類方法は、同じジョブファミリからの実行セット内の異常値実行を識別することを可能にする。
【００９７】
このために、実行間の距離は、収集されたＩＯ測定のシーケンス間の距離から計算される。測定シーケンスは、統計的検定に基づいて比較され、次に、実行間の総距離を得るために比較済み測定のセットについて距離が集約される。生成された距離行列によって、階層分類法に従って実行を分類することができ、異常値実行は、相対閾値に基づいて検出される。
【００９８】
異常値実行のこの検出により、メタデータ推論段階のために関連する実行のみを選択することができる。
【００９９】
メタデータ推論
新しい実行の開始時点で、最適値が推論されることになる一部のメタデータは、フリーのまま残されるべく選択される。
【０１００】
ファミリへのフィルタリングおよび分類によって、前述のように推論のために関連性のある実行セットが選択される。これらの実行の各々について、有用なデータのセットが、フリーメタデータの推論のために抽出される。
【０１０１】
これらのデータセットの中で、一部の変数は、従属（dependent）変数（被説明（explained）変数）と呼ばれ、一方、他の変数は、独立（independent）変数（説明（explanatory）変数）と呼ばれる。もともと、推論が求められているメタデータは、独立変数である。従属変数と独立変数との間には或る関係が存在すると仮定されている。回帰の原則は、この関係を記述するモデルを構築することにある。
【０１０２】
回帰によりひとたびモデルが得られたならば、システムに適用されるべき最適なパラメータの探索を、最適化アルゴリズムを使用することによって行なうことができる。
【０１０３】
本使用事例については、性能測定との関係における入力／出力アクセラレータの最適なパラメータを推論することが求められている。
【０１０４】
図８は、スピードアップの最大化基準（maximization criterion of the speed-up）に基づく３つの「Ｆａｓｔ  ＩＯ  Ｌｉｂｒａｒｉｅｓ（高速ＩＯライブラリ）」パラメータの最適化を描いている。ここでは、スピードアップフィールドは、テストアプリケーションによって開始された多数の実行に関する１セットの性能測定の補間によって生成される。最適化されるＦａｓｔ  ＩＯ  Ｌｉｂｒａｒｉｅｓパラメータの値は、以下の通りである。
・  ＳＲＯ＿ＣＬＵＳＴＥＲ＿ＴＨＲＥＳＨＯＬＤ（ｃｔ）
・  ＳＲＯ＿ＤＳＣ＿ＢＩＮＳＩＺＥ（ｂｓ）
・  ＳＲＯ＿ＰＲＥＦＥＴＣＨ＿ＳＩＺＥ（ｐｓ）
【０１０５】
このアプリケーションにおいて、最適化問題の最良の解決法を決定する上で基準として役立つ関数（目的関数）は、サンプリングされたスピードアップのフィールド（field of the sampled speed-ups）（２６４の収集された測定）の補間によって得られる。
【０１０６】
製作の観点からすると、すなわち、アプリケーションの性能値を多数の点において入念に評価することができない場合には、連続関数としてパラメータ空間をモデル化するために多数の回帰ステップを追加しなければならない。このとき、これは、有利にも最適化方法のための目的関数として役立つことができる。これについては、次の節で詳述する。
【０１０７】
回帰による性能変動のモデル化
回帰処理によって、アクセラレータパラメータの一関数として性能変動（例えば、アプリケーションの実行時間）をモデル化する連続モデルを得ることができる。
【０１０８】
関係のタイプ（例えば線形または非線形）、独立変数の数（例えば、単一または多重（multiple））、および従属変数の数（例えば、一変量または多変量）に従って、回帰技術をカテゴリ化することが可能である。
【０１０９】
本使用事例においては、性能値との関係において複数のアクセラレータパラメータを決定することが求められている。したがって、これは、一変量重回帰（multiple, univariate regression）である。
【０１１０】
「Ｆａｓｔ  ＩＯ  Ｌｉｂｒａｒｉｅｓ」のＳＲＯモジュールパラメータ推論の具体的応用では、複数の方法が実験の対象となった。
【０１１１】
線形回帰方法：ベイジアンリッジ回帰（Bayesian Ridge Regression；ＢＲＲ）
ＢＲＲは、Ｌ−２タイプの正則化（regularization）を用いた線形単回帰技術（simple linear regression technique）である。
【０１１２】
これは、単純かつ説明的なモデルを提供するという利点を有するが、さまざまなパラメータと性能測定との間に存在する関係を充分に表現していない。
【０１１３】
パラメータ化問題に固有のものである複雑性をより良く反映するために、変数間の非線形従属性の面を考慮に入れることのできる高度な方法が存在する。
【０１１４】
カーネル技術に基づく非線形回帰方法
カーネル技術に基づく方法は、出発空間（starting space）における非線形問題を到着空間（arrival space）内の線形問題へと変換できるようにする。変換演算子を任意の点において決定することは難しいため、当該方法は、カーネル技術を統合する（「カーネル方法」）。これにより、２つの点についての類似性測定を確立することによって到着空間の特性が使用される。異なるタイプのカーネルが存在する（例えば「放射基底関数（radial basis function）」、多項式、線形、指数など）。
【０１１５】
「回帰のためのサポートベクタ（Support Vector for Regression；ＳＶＲ）」方法は、回帰のためのサポートベクタマシン（Support Vector Machine；ＳＶＭ）の「カーネル」変形（variant）である。これにより、サポートベクタのみに基づくスパースモデル（sparse model）を得ることが可能である。このモデルによって、高速予測ができる。
【０１１６】
「回帰のためのガウス過程（Gaussian Process for Regression；ＧＰＲ）」方法は、「ベイジアン（ベイズ）回帰（Bayesian Regression）」のカーネルバージョンである。
【０１１７】
これには、トレーニングがより速いという利点があり、不完全データの場合を含め、正しく機能する。
【０１１８】
本使用事例において、これらの２つの方法を評価する際には、「放射基底関数（Radial Basis Function；ＲＢＦ）」カーネルが使用された。
＜数式３＞
【数６】
2020004409.tif 000008
先験的にモデル関数に求められる度合を決定することを必要とする多項式カーネルとは異なり、ＲＢＦカーネルは、いかなる先験的仮定も無く機能する。
【０１１９】
使用される回帰方法の如何に関わらず、アクセラレータのパラメータのあらゆる値について、性能値を評価するために１つのモデルに到達する。
【０１２０】
このモデルは、収束ストラテジにおける最適な解の探索を可能にする。
【０１２１】
アクセラレータパラメータの最適化
アクセラレータと性能値との関係をモデル化する関数を推定した後、最適なパラメータを見い出すために最適化アルゴリズムを使用することが可能である。
【０１２２】
次の２つのグループに分類できる異なるタイプの数値最適化アルゴリズムが存在する。
−  勾配法
これらは、極値を迅速に決定するための目的関数の導関数の概念を用いる方法である。
−  勾配独立法（Gradient independent methods）
これらは、目的関数の微分可能な性質に関係する情報無しで機能する方法である。
【０１２３】
勾配の計算を含むかまたは含まない複数の最適化方法が、実験の対象となってきた。多くの場合、多数の局所的最適値を示す空間のパラメータを探索するために、我々の実験においては多くの場合局所的最適値に捕われる勾配法とは異なり、勾配独立法によれば、大域的最適値に向かって収束するさらなる可能性が提供される。
【０１２４】
アプリケーションの実行時間を最小化することを目的とする「Ｆａｓｔ  ＩＯ  Ｌｉｂｒａｒｉｅｓ」のＳＲＯモジュールのパラメータの推論の具体的応用においては、複数の方法が実験の対象となってきた。
【０１２５】
ネルダーミード（Nelder-Mead；ＮＭ）アルゴリズム
ネルダーミード法は、多次元空間内の連続関数を最少化しようとする非線形最適化アルゴリズムである。
【０１２６】
「滑降シンプレックス法（downhill simplex method）」としても知られているこのアルゴリズムは、Ｎ次元空間内のＮ＋１個の頂点の凸多面体であるシンプレックスの概念を使用する。最初は、このようなシンプレックスから出発し、これは、繰り返し中に単純な変換を受ける。すなわち、それは、関数が局所的に最小である点にその頂点が接近するまで、変形し、移動し、漸進的に縮小する。
【０１２７】
「粒子群最適化（Particle Swarm Optimization；ＰＳＯ）」アルゴリズム
ネルダーミードアルゴリズムとは異なり、「粒子群最適化（Particle Swarm Optimization）」では、マルチエージェントタイプのモデル化を用いる確率アプローチが採用される。この方法は、異なる点において目的関数の評価された値を共有する多数の粒子を変数空間内でスウォームさせて（swarm）、粒子群の大域的知識に貢献する。
【０１２８】
この情報共有は、近傍の粒子に交換を限定する局所的なやり方と、目的関数の最良の評価を有する粒子と他の粒子との間の好適な共有を保証する大域的なやり方と、の２つのやり方で行なわれ得る。
【０１２９】
「フリー」メタデータの自己最適化のストラテジは、アプリケーションの性能を最適化する（すなわち、実行時間を最短にする）ことができるＩＯアクセラレータのパラメータの決定からなる一実施形態によって例示されてきた。
【０１３０】
選択されたアプローチは、最適なパラメータを推論するために過去の実行で計装（インストルメンテーション）（instrumentation）ＩＯによって収集されたデータを使用することからなる。このために、関連性のある実行だけが、連続的にその確定メタデータ（ステップ４）およびその時間的ＩＯ挙動（temporal IO behaviours）（ステップ５）によって選択される。
【０１３１】
そして、この実行セットを使用して、アクセラレータパラメータの一関数として性能値のモデルを回帰によって得る。最後に、使用すべきパラメータは、コスト関数を最適化する最適化方法によって得られたモデルから決定される。
【０１３２】
推論されたパラメータを用いて開始される実行は、それ自体が監視され、収集されたデータは、後続の推論で使用される。このようにして、実行ベース（executions base）は、連続する推論に伴って増大し、それと同時に、アクセラレータパラメータ空間内の性能フィールドの知識が増大する。各繰り返しにおいて、この成長する知識は、理論的モデルに増々近い回帰されたモデルを得ることを可能にし、こうして、考慮されるジョブについての大域的最適値に向かって収束する自己最適化の好循環でループが行われる。
【０１３３】
当然のことながら、本発明は、説明され図示された実施例および実施形態に限定されるものではなく、当業者にとってアクセス可能な数多くの変形形態で運用されるものである。
【符号の説明】
【０１３４】
１  アプリケーション実行
２  性能測定
３  データベース
４  抽出
５  分類
６  推論
【図１】
2020004409.tif 000009
【図２ａ】
2020004409.tif 000010
【図２ｂ】
2020004409.tif 000011
【図３ａ】
2020004409.tif 000012
【図３ｂ】
2020004409.tif 000013
【図４】
2020004409.tif 000014
【図５】
2020004409.tif 000015
【図６】
2020004409.tif 000016
【図７】
2020004409.tif 000017
【図８】
2020004409.tif 000018
【外国語明細書】
2020004409000001.pdf