(57)【要約】【課題】本発明は、テストコードの実行がシミュレートされている間に選択された機能状態の適用範囲で作られる評価をするテストプログラムの生成の自動化を提供する。を提供する。【解決手段】データ処理装置のためのテストプログラムは、テストプログラムを形成している集団におけるプログラム命令の順序付けられたリストからなる例の変更について、遺伝子アルゴリズムを使用して生産される。集団は、特定の例が集団の中又は外へ交換されるべきであるか否かについてなされる決定がされているとき、集団全体がデータ処理装置において所定の機能ポイントの刺激に対して採点されることによる測定を使用して評価される。【選択図】図４
2006164282.tif 000002
【特許請求の範囲】
【請求項１】
データ処理装置のためにテストを生成する方法であって、
前記テストは、プログラム命令の順序づけられたリストからなる複数の列で形成されたプログラム命令の集団を構成し、
（ｉ）前記集団のシミュレートされた実行中に発生する前記データ処理装置の機能状態をシミュレートするステップと、
（ｉｉ）前記集団のシミュレートされた実行中に、前記データ処理装置の所定の機能状態のシミュレートされた発生を記録するステップと、
（ｉｉｉ）前記集団のシミュレートされた実行中に、前記所定の機能状態の発生に依存した前記所定の機能状態に対する各機能状態スコア値を算出するステップと、
（ｉｖ）前記各機能状態スコア値の組み合わせに依存する集団スコア値を形成するステップと、
（ｖ）１つ以上の候補例を形成するように、１つ以上の前記例を変化させるステップと、
（ｖｉ）候補集団を形成するように、前記候補例のうちの１つで前記集団の前記例の少なくとも１つを置き換えるステップと、
（ｖｉｉ）候補集団スコア値を形成するために、前記候補集団に関して前記ステップ（ｉ）、（ｉｉ）、（ｉｉｉ）および（ｉｖ）を繰り返すステップと、
（ｖｉｉｉ）前記集団スコア値と前記候補集団スコア値とを比較するステップと、
（ｉｘ）前記候補集団のシミュレートされた実行が多数の前記所定の機能状態のシミュレートされた発生となることを、前記候補集団スコア値が示す場合に、前記候補集団で前記集団を置き換えるステップと、
（ｘ）１つ以上の所定の終了条件が満たされるまで、前記ステップ（ｖ）、（ｖｉ）、（ｖｉｉ）、（ｖｉｉｉ）および（ｉｘ）を繰り返すステップと、
を有することを特徴とする方法。
【請求項２】
前記機能状態スコア値は、所定の各機能状態のシミュレートされた発生回数の非線形関数である請求項１に記載の方法。
【請求項３】
前記集団スコア値は、前記集団を形成しているプログラム命令の前記順序づけられたリストの全体的な長さにも依存しており、前記集団を置き換る前記候補集団を選ぶ候補集団スコア値となる前記集団よりも、候補集団は、全体的な長さが短くなっている請求項１に記載の方法。
【請求項４】
ステップ（ｉｉ）および（ｉｉｉ）は、各列に対して機能状態スコア値を各々決定するとともに、ステップ（ｖｉ）は、各例に対する前記各機能状態スコア値の１つ以上に依存して、置き換えられるべき前記集団の中から１つの例を選択する請求項１に記載の方法。
【請求項５】
ステップ（ｖｉ）は、前記所定の機能状態の最小発生に対応する各機能状態スコア値を有するものとして置換される前記集団の中から前記例を選択する請求項４に記載の方法。
【請求項６】
前記候補集団は、前記各機能状態スコア値のそれぞれに対してそれぞれ順番に選択を実行することで選択される請求項４に記載の方法。
【請求項７】
ステップ（ｉ）、（ｉｉ）および（ｉｉｉ）は、前記集団および前記候補集団を構成する例を含む複数の例で構成された拡張集団に関して実行される請求項１に記載の方法。
【請求項８】
ステップ（ｉ）は、命令セットシミュレータによって実行される請求項１に記載の方法。
【請求項９】
前記データ処理装置の構造の定義は、前記データ処理装置の少なくとも機能動作を定義するとともに、前記データ処理装置の機能状態を示す注釈が付けられており、前記命令セットシミュレータは、前記構造定義から少なくとも部分的に自動的に生成されてなる前記所定の機能状態の表示を具備している請求項８に記載の方法。
【請求項１０】
前記ステップ（ｖ）での変更は、前記構造定義から少なくとも部分的に自動的に生成された、許可された変更ルールの制御の下で実行される請求項９に記載の方法。
【請求項１１】
プログラム命令の順序づけられたリストの例は、前記構造定義から少なくとも部分的に自動的に生成される請求項９に記載の方法。
【請求項１２】
前記所定の機能状態は、機能状態の所定の時間的な順序、又は前記データ処理装置の機能状態を構成する独立状態変数の組み合わせのどちらかである１つ以上の複合機能状態を有する請求項１に記載の方法。
【請求項１３】
ステップ（ｉ）は、複数の独立シミュレータを使用して実行され、前記所定の機能状態の少なくとも１つは、前記独立シミュレータのうちの１つのみで決定される請求項１に記載の方法。
【請求項１４】
前記独立シミュレータのうちの１つは、前記データ処理装置のＲＴＬシミュレーションである請求項１３に記載の方法。
【請求項１５】
前記独立シミュレータのうちの１つは、前記データ処理装置のＦＰＧＡシミュレーションである請求項１３に記載の方法。
【請求項１６】
データ処理装置にテストを生成するために処理可能なデータを処理するための装置であって、
前記テストは、プログラム命令の順序づけられたリストからなる複数の列で形成されたプログラム命令の集団を構成し、
（ｉ）前記集団のシミュレートされた実行中に発生する前記データ処理装置の機能状態をシミュレートするステップと、
（ｉｉ）前記集団のシミュレートされた実行中に、前記データ処理装置の所定の機能状態のシミュレートされた発生を記録するステップと、
（ｉｉｉ）前記集団のシミュレートされた実行中に、前記所定の機能状態の発生に依存した前記所定の機能状態に対する各機能状態スコア値を算出するステップと、
（ｉｖ）前記各機能状態スコア値の組み合わせに依存する集団スコア値を形成するステップと、
（ｖ）１つ以上の候補例を形成するように、１つ以上の前記例を変化させるステップと、
（ｖｉ）候補集団を形成するように、前記候補例のうちの１つで前記集団の前記例の少なくとも１つを置き換えるステップと、
（ｖｉｉ）候補集団スコア値を形成するために、前記候補集団に関して前記ステップ（ｉ）、（ｉｉ）、（ｉｉｉ）および（ｉｖ）を繰り返すステップと、
（ｖｉｉｉ）前記集団スコア値と前記候補集団スコア値とを比較するステップと、
（ｉｘ）前記候補集団のシミュレートされた実行が多数の前記所定の機能状態のシミュレートされた発生となることを、前記候補集団スコア値が示す場合に、前記候補集団で前記集団を置き換えるステップと、
（ｘ）１つ以上の所定の終了条件が満たされるまで、前記ステップ（ｖ）、（ｖｉ）、（ｖｉｉ）、（ｖｉｉｉ）および（ｉｘ）を繰り返すステップと、
を実行するのに処理可能なロジックを有することを特徴とする装置。
【請求項１７】
データ処理装置のためにテストを生成する方法を実行するためのコンピュータを制御するコンピュータ・プログラムを有するコンピュータ・プログラム製品であって、
前記テストは、プログラム命令の順序づけられたリストからなる複数の列で形成されたプログラム命令の集団を構成し、
（ｉ）前記集団のシミュレートされた実行中に発生する前記データ処理装置の機能状態をシミュレートするステップと、
（ｉｉ）前記集団のシミュレートされた実行中に、前記データ処理装置の所定の機能状態のシミュレートされた発生を記録するステップと、
（ｉｉｉ）前記集団のシミュレートされた実行中に、前記所定の機能状態の発生に依存した前記所定の機能状態に対する各機能状態スコア値を算出するステップと、
（ｉｖ）前記各機能状態スコア値の組み合わせに依存する集団スコア値を形成するステップと、
（ｖ）１つ以上の候補例を形成するように、１つ以上の前記例を変化させるステップと、
（ｖｉ）候補集団を形成するように、前記候補例のうちの１つで前記集団の前記例の少なくとも１つを置き換えるステップと、
（ｖｉｉ）候補集団スコア値を形成するために、前記候補集団に関して前記ステップ（ｉ）、（ｉｉ）、（ｉｉｉ）および（ｉｖ）を繰り返すステップと、
（ｖｉｉｉ）前記集団スコア値と前記候補集団スコア値とを比較するステップと、
（ｉｘ）前記候補集団のシミュレートされた実行が多数の前記所定の機能状態のシミュレートされた発生となることを、前記候補集団スコア値が示す場合に、前記候補集団で前記集団を置き換えるステップと、
（ｘ）１つ以上の所定の終了条件が満たされるまで、前記ステップ（ｖ）、（ｖｉ）、（ｖｉｉ）、（ｖｉｉｉ）および（ｉｘ）を繰り返すステップと、
を有することを特徴とするコンピュータ・プログラム製品。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、データ処理システムの分野に関するものである。より具体的には、この発明はデータ処理システムをテストするために使用されるテストプログラムの自動的な生成に関するものである。
【背景技術】
【０００２】
データ処理システムをテストするために、データ処理システムで実行可能なプログラム命令の長い列（sequences）を生成することが知られている。そのテストは多種多様な形式をとることができる。１つの形式としては、実行後の最終結果の状態が、望ましいデータ処理システムを正確に表しているＲＴＬモデルと同じであることを示すことを確認するために、命令セットシミュレータとデータ処理システムのＲＴＬモデルとの両方でテストプログラムの実行をシミュレートすることによって、データ処理システムの設計を検査することが可能である。もう１つのレベルとして、テストプログラムは、ゲートレベルの設計を実証するため、例えばＦＰＧＡについての設計を実証するため、工業製品の試作においての設計又は正確な製造を確認するため等に、動作されることが可能である。データ処理システムを刺激するテストプログラムは、広い適用範囲を持っていることが上記から理解される。データ処理システムの設計がより複雑化し、且つ開発の高度化が必要とされるにつれて、データ処理システムについての徹底的な且つ高速なテストは、ますます重要になっている。
【０００３】
高品質のテストを達成するために、テストプログラムは、データ処理システムにおける故障又は誤りを検出することについての蓋然性を高めるように、すべての可能な機能の状態の中から多種多様な機能状態を採用するために当該データ処理システムを刺激することが望ましい。このような広範囲に及ぶテストプログラム適用範囲を得るものとして、従来は、手書きによるテストプログラムが知られている。データ処理システムをテストするための大量の知識を持っているプログラマが、データ処理システムの広範な異なった回路要素および動作を刺激して、その中の誤りが検出されるように、プログラム命令の列を選択するために、この知識を使用することができる。しかしながら、データ処理システムの複雑化が増加し、且つ、テストプログラムを作るために利用可能な時間が減少するので、このようなテストプログラムをこのようにして手作業で作成することは困難となる。手作業での作成は、その上、高度な熟練を必要として、労働集約的であるとともに、従って費用がかかる。
【０００４】
遺伝子アルゴリズムを利用して、ＣＰＵをテストするためのテストプログラムを自動的に生成することが知られている。しかしながら、これらの公知の方法は、静的なコード生成を使用するため、厳しく制限されているとともに、それらの方法は自動生成におけるフィードバックのための測定としてＲＴＬコードの適用範囲に集中するので、システムの機能的状態についてのテスト網羅度の品質又は正確性を決定することができない。
【発明の開示】
【課題を解決するための手段】
【０００５】
本発明の１つの様相としての目的は、
データ処理装置のためにテストを生成する方法であって、
前記テストは、プログラム命令の順序づけられたリストからなる複数の列で形成されたプログラム命令の集団を構成し、
（ｉ）前記集団のシミュレートされた実行中に発生する前記データ処理装置の機能状態をシミュレートするステップと、
（ｉｉ）前記集団のシミュレートされた実行中に、前記データ処理装置の所定の機能状態のシミュレートされた発生を記録するステップと、
（ｉｉｉ）前記集団のシミュレートされた実行中に、前記所定の機能状態の発生に依存した前記所定の機能状態に対する各機能状態スコア値を算出するステップと、
（ｉｖ）前記各機能状態スコア値の組み合わせに依存する集団スコア値を形成するステップと、
（ｖ）１つ以上の候補例を形成するように、１つ以上の前記例を変化させるステップと、
（ｖｉ）候補集団を形成するように、前記候補例のうちの１つで前記集団の前記例の少なくとも１つを置き換えるステップと、
（ｖｉｉ）候補集団スコア値を形成するために、前記候補集団に関して前記ステップ（ｉ）、（ｉｉ）、（ｉｉｉ）および（ｉｖ）を繰り返すステップと、
（ｖｉｉｉ）前記集団スコア値と前記候補集団スコア値とを比較するステップと、
（ｉｘ）前記候補集団のシミュレートされた実行が多数の前記所定の機能状態のシミュレートされた発生となることを、前記候補集団スコア値が示す場合に、前記候補集団で前記集団を置き換えるステップと、
（ｘ）１つ以上の所定の終了条件が満たされるまで、前記ステップ（ｖ）、（ｖｉ）、（ｖｉｉ）、（ｖｉｉｉ）および（ｉｘ）を繰り返すステップと、
を有することを特徴とする方法
を提供することにある。
【０００６】
本発明は、テストコードの実行がシミュレートされている間に選択された機能状態の適用範囲で作られる評価によるテストプログラム生成の自動化を提供する。変更がテストプログラムの適用範囲を改善するか否かについて決定するとき、フィードバックメカニズムが全体として集団を採点するのに使用される。集団内の例（テスト）が変更されるとき、全体として集団を採点するこのフィードバックメカニズムがテスト適用範囲の所望の程度でテストプログラムを迅速で確実に収束する。
【０００７】
機能状態スコア値が、例えば、テストの間に機能状態が選択された時の数の単純なカウント、を含む、多種多様な異なる形式をとることができると同時に、本発明の好ましい実施形態がカウントのような非線形関数として機能状態スコア値を生成することはいうまでもない。非線形関数の使用は、例えば、テストプログラムの時間中に既に十分に何度も刺激された機能ポイントへの度重なる刺激に対して選択することによって、より高速に生成されるようにテストプログラムの性能をより良くすることを可能にする。
【０００８】
決定された機能状態の発生に依存していることと同様に、集団スコア値は、また、可能な場合にはより短いテストが選択されるようなテストの長さに依存する距離を一因とすることができる。
【０００９】
個々の例（テスト）は、また、それぞれの機能状態に対して採点されることとしてもよいとともに、この情報は、集団の例が変更されている間に置換されることを制御するために使用することができる。
【００１０】
テストプログラムを発展させるプロセスは、変更、評価およびトーナメントプロセスの反復シーケンスであると考えることができる。これらのプロセスは、更なる例が評価可能とされるとともに、母集団の範囲内で例を置換することの適合性が決定されるような、更なる変化のために、母集団を形成するために必要な数を越える例の拡張集団上で実行される。
【００１１】
シミュレーションステップがいろいろな異なるシミュレータを使用して実行可能であると同時に、このシミュレーションを実行するために命令セットシミュレータを使用することが望ましい。命令セットシミュレータは、迅速で有効なシミュレーションを行うとともに、広範囲にわたる機能状態が選択されているか否か決定し、且つ、それらの状態を採点するためのデータ処理装置の機能状態に関して十分詳細に追跡することができる。
【００１２】
データ処理装置の構造上の定義には、データ処理装置の機能状態を示すための注釈を付けることが可能であるとともに、この注釈が付けられた構造上の定義は、命令セットシミュレータ、許可された変更規則および評価される例（テスト）を、少なくとも部分的に自動的に生成するために使用することができる。
【００１３】
テストプログラムによって目標とされる機能状態は、多種多様な異なる形式をとることができるとともに、好ましくは、機能状態の所定の時間的シーケンス又は独立状態変数の並列な組み合わせのいずれかである複合され機能状態を具備している。
【００１４】
テストプログラムの実行のシミュレーションは、１つのシミュレータで、あるいはＲＴＬシミュレーション又はＦＰＧＡシミュレーションを含む複数のシミュレータで交互に、行うことが可能である。その異なるシミュレータは、命令セットシミュレータの範囲内で利用できない、電力消費指標のような、機能状態変数の異なるタイプへのアクセスを提供することができ、したがって、生成されたテストプログラムの有効性を広げるものであってもよい。その違いは、異なるシミュレータの動作範囲内で確認されることがあり得るとともに、また、これは更なる調査に値するテストにおける設計の範囲内の問題を強く示す。
【００１５】
本発明における他の構成は、
データ処理装置にテストを生成するために処理可能なデータを処理するための装置であって、
前記テストは、プログラム命令の順序づけられたリストからなる複数の列で形成されたプログラム命令の集団を構成し、
（ｉ）前記集団のシミュレートされた実行中に発生する前記データ処理装置の機能状態をシミュレートするステップと、
（ｉｉ）前記集団のシミュレートされた実行中に、前記データ処理装置の所定の機能状態のシミュレートされた発生を記録するステップと、
（ｉｉｉ）前記集団のシミュレートされた実行中に、前記所定の機能状態の発生に依存した前記所定の機能状態に対する各機能状態スコア値を算出するステップと、
（ｉｖ）前記各機能状態スコア値の組み合わせに依存する集団スコア値を形成するステップと、
（ｖ）１つ以上の候補例を形成するように、１つ以上の前記例を変化させるステップと、
（ｖｉ）候補集団を形成するように、前記候補例のうちの１つで前記集団の前記例の少なくとも１つを置き換えるステップと、
（ｖｉｉ）候補集団スコア値を形成するために、前記候補集団に関して前記ステップ（ｉ）、（ｉｉ）、（ｉｉｉ）および（ｉｖ）を繰り返すステップと、
（ｖｉｉｉ）前記集団スコア値と前記候補集団スコア値とを比較するステップと、
（ｉｘ）前記候補集団のシミュレートされた実行が多数の前記所定の機能状態のシミュレートされた発生となることを、前記候補集団スコア値が示す場合に、前記候補集団で前記集団を置き換えるステップと、
（ｘ）１つ以上の所定の終了条件が満たされるまで、前記ステップ（ｖ）、（ｖｉ）、（ｖｉｉ）、（ｖｉｉｉ）および（ｉｘ）を繰り返すステップと、
を実行するのに処理可能なロジックを有することを特徴とする装置を提供することである。
【００１６】
本発明の更に他の構成は、
データ処理装置のためにテストを生成する方法を実行するためのコンピュータを制御するコンピュータ・プログラムを有するコンピュータ・プログラム製品であって、
前記テストは、プログラム命令の順序づけられたリストからなる複数の列で形成されたプログラム命令の集団を構成し、
（ｉ）前記集団のシミュレートされた実行中に発生する前記データ処理装置の機能状態をシミュレートするステップと、
（ｉｉ）前記集団のシミュレートされた実行中に、前記データ処理装置の所定の機能状態のシミュレートされた発生を記録するステップと、
（ｉｉｉ）前記集団のシミュレートされた実行中に、前記所定の機能状態の発生に依存した前記所定の機能状態に対する各機能状態スコア値を算出するステップと、
（ｉｖ）前記各機能状態スコア値の組み合わせに依存する集団スコア値を形成するステップと、
（ｖ）１つ以上の候補例を形成するように、１つ以上の前記例を変化させるステップと、
（ｖｉ）候補集団を形成するように、前記候補例のうちの１つで前記集団の前記例の少なくとも１つを置き換えるステップと、
（ｖｉｉ）候補集団スコア値を形成するために、前記候補集団に関して前記ステップ（ｉ）、（ｉｉ）、（ｉｉｉ）および（ｉｖ）を繰り返すステップと、
（ｖｉｉｉ）前記集団スコア値と前記候補集団スコア値とを比較するステップと、
（ｉｘ）前記候補集団のシミュレートされた実行が多数の前記所定の機能状態のシミュレートされた発生となることを、前記候補集団スコア値が示す場合に、前記候補集団で前記集団を置き換えるステップと、
（ｘ）１つ以上の所定の終了条件が満たされるまで、前記ステップ（ｖ）、（ｖｉ）、（ｖｉｉ）、（ｖｉｉｉ）および（ｉｘ）を繰り返すステップと、
を有することを特徴とするコンピュータ・プログラム製品を提供することである。
【００１７】
本発明の上記の目的及びその他の目的、特徴および効果は、添付図面に関連して理解されることとなる以下の実施形態の詳細な説明から明らかとなる。
【発明を実施するための最良の形態】
【００１８】
図１は、各例がテストを構成するプログラム命令の順序づけられたリストからなり、複数の例で構成された集団と考えられるテストプログラム２の例示である。テストプログラム２は、全体として、命令セットシミュレータ４、ＲＴＬシミュレータ６、ＦＰＧＡシミュレータ８、又は製造されたデータ処理装置１０の１つ以上によって、シミュレートされるか又は実行されることが可能である。これらの実行のそれぞれが、シミュレートされるか又は現実のものであるかにかかわらず、結果の状態データを作り出す。この状態データは、テストプログラムの実行について異なるメカニズムの製造又は設計における誤りを検出するように、テストプログラムの実行のもう１つの形式によって生成される他の状態データと比較される。
【００１９】
命令セットシミュレータ上で実行されるテストプログラムが、最終結果状態を作り出すことは理解されるであろう。同じテストプログラムが、データ処理装置の提案されたＲＴＬシミュレーション上で実行されるとき、そのＲＴＬシミュレーションが正しい場合、そのＲＴＬシミュレータ上の同じテストプログラムを実行した結果は、命令セットシミュレータで得られるものと同じであるべきである。相違がある場合、これはデータ処理装置のＲＴＬレベルの設計において誤りがある可能性が高いことを示す。このような誤りは、そのＲＴＬ設計による生産がされる前に、修正することができる。同様に、テストプログラムを実行しいる製造されたデータ処理装置は、そのテストプログラムのために命令セットシミュレータと同じ最終状態を作り出すべきである。相違は、物理的なデータ処理装置１０における設計又は製造の欠陥を示すことが可能である。
【００２０】
徹底的に種々のシミュレーションおよび設計をテストするために、データ処理装置によって採用され得る広範囲な機能状態は、シミュレートされている間又はテストプログラムを実際に実行している間に発生するべきものであることが望ましい。本発明の技術は、機能状態の刺激を広範囲に得ることができるテストプログラムの少なくとも部分的に自動的な生成をすることを対象とする。
【００２１】
図２は、データ処理装置の構造定義ＡＤが注釈付き構造定義１２を作り出すように、機能ポイントＦＰとともに、注釈を付けられることを可能とする方法を例示する。この注釈付き構造定義１２から、同じく注釈付きの機能ポイントデータとともに命令セットシミュレータ１４が、自動的に生成され得る。機能ポイントは、テストシミュレーションの間に、基本的に重要な進化の発生を示す。これらの注釈付けは、好ましい特徴を持った進化するテストが変化する間に、遺伝子アルゴリズムに使用される。
【００２２】
また、命令ジェネレータ１６は、命令重み付けデータ１８と、命令列テンプレート２０とともに注釈付き構造定義１２を使用して、最終プログラムに向かって変化し且つ進化するために集団２２を形成するように構築されるプログラム命令の順序付けられたリストである候補例（テスト）を生成する。重み付け１８は、これらがより一般的に利用されることが知られている場合、他のものに対してプログラム命令をある特定の種類を含むようにするために使われる。命令テンプレートは、同様に、設計を強調することが知られ、それに応じて問題を明らかにすることに役立つ可能性が高くなる特定の列のプログラム命令を含むようにするために使用される。
【００２３】
後述するように、命令セットシミュレータ１４は、集団２２の実行をシミュレーションすることができるとともに、採点メトリック２４を使用してこれを採点することができる。採点メトリックは、集団２２を実行する付加シミュレータ３０によって追跡することができる外部機能ポイント２８だけでなく、注釈付き構造定義１２と、人手で作成された複合機能ポイント２６（これらは、機能状態の時間的順序、又はテストにとって良い候補としてユーザによって選ばれる独立状態変数の並列の組み合わせであること）から提供される機能ポイントデータによって識別された機能状態を用いて、所定の機能状態の発生を記録する。採点機構２４は、テストプログラムのテスト適用範囲の性能を向上させる交換がなされなければならないか否かを決定するために、集団２２内の例（インスタンス）と新しい例の候補との間でトーナメントを行う変化機構３２に、その得点を供給する。そのような変化は、その後、再評価することができる。採点機構２４は、また、例えば少なくとも局地的に最適値に設定されている得点、繰り返し数、又は終了時間、又は他の適当な終了状態のような、終了状態をモニタすることができる。
【００２４】
図３は、本発明の評価、トーナメントおよび変更処理の概要を例示するフローチャートである。ステップ３４では、プログラム命令の順序づけられたリストとして各々形成された複数の例を具備する初期集団が選択される。テンプレート２０および重み付け１８を使用する命令ジェネレータ１６は、この集団をシード（seed）することに使用される。
【００２５】
ステップ３６では、シミュレートされた集団の実行が命令セットシミュレータ１４および全ての追加シミュレータ３０で行われる。ステップ３８では、全ての集団のための集団スコア値が計算される。与えられた例によって生成される機能ポイントの算出値は、機能状態スコア値がその機能ポイントについて算出される前に、例の集団全体で平均される。それらの機能状態スコア値は、次いで、集団スコア値を生成するために合計される。
【００２６】
次いで、ステップ４０では、ステップ３８で採点された集団が以前の集団に対して比較されている候補集団であったか否か確認する。これが「Ｎｏ」の場合は、処理はステップ４２に進行して、集団が新しい候補集団を作るために変更されるとともに、処理がステップ３６に戻される。
【００２７】
ステップ３８において実行された採点が候補集団のものであった場合（例えば、これは、現在、２回又はより多くの回数だけシミュレーションが行われている）、次いで、候補集団が現在の集団より高い集団得点を持っているか否かについての決定がなされるステップ４４へ処理を進める。これが「Ｙｅｓ」の場合は、ステップ４６において、現在の集団を候補集団で置き換える。「Ｎｏ」の場合は、ステップ４６が回避される。ステップ４８は、例えば、進化のための時間が時間切れとなったことによって解決が収束したなど、テストプログラムの進化についての終了基準が達せられたか否かについて検査する。新しい候補集団を形成する現在の集団の変化は、ステップ４２において、より詳細に提示される。
【００２８】
トーナメントのための出発点として、候補集団はシミュレータによって採点されるとともに、それらの計数は、それぞれのＦＰがシミュレーションの間にヒットした回数による得点で満たされている。新しい候補は、最初のＮ候補が前の母集団を代表し、且つ、次の候補が新しく変更させられたテストを代表するような順番になっている。
【００２９】
アルゴリズムの概要は、以下のとおりである。
「ＴｒｙＭｅ」フラグを使用して新しい集団に目標が定められるように、最初のＮ候補の全てをマーキングすることによりスタートする。
【００３０】
この例としては、１０の候補があり、Ａ−Ｊ、および４人の市民（citizens）の新しい世代が望まれ、それで、候補Ａ，Ｂ，ＣおよびＤは現在における最高の新しい世代であるとマーキングされる。
【００３１】
特定のＦＰに対して候補者がどのようにうまく得点するかによって候補者の順位付けとなる、各ＦＰｓに対するスコアカードが作られる。
【００３２】
【表１】
2006164282.tif 000003
【００３３】
打ち切りポイントは、新しい集団で望まれる市民の数に設定される。
【００３４】
【表２】
2006164282.tif 000004
【００３５】
各ＦＰ列に対して順番に、打ち切りポイントより下、又は既に新しい集団に入っている全ての市民を無視する。
【００３６】
ＦＰ０に対しては、ＡおよびＢが既に新しい集団にあるので、ＦおよびＧをそのままにしておく。
【００３７】
【表３】
2006164282.tif 000005
【００３８】
残っている市民から、このＦＰに対して最高得点を持っているものを選択するとともに、リストの終端でスタートし上昇している、現在の最新の集団において現れる列の下の各市民に対して順番に、新しい集団への交換を試みる。
【００３９】
そして、ＦＰ０において、Ｆが選択される（ＦＰ０における最高得点候補）とともに、試行により順番にＤ，Ｃ，ＢおよびＡと交換される（ＦＰ０についての得点が、最低から最高まで、順序付けられている）。
【００４０】
この最新に生成された最高の集団を再度採点するとともに、交換前よりも高い得点であるか否か確認する。もしそうであるなら、その変化を保持するとともに、このＦＰの処理を停止する。
【００４１】
交換したＦとＣがより高い全体的得点をもたらしこの置換は保持されると判断された場合、新しい最良集団はＡ，Ｂ，ＤおよびＦとなる。
【００４２】
全てのＦＰ列が評価されたとき、中止する。
【００４３】
ＦＰ１について、例を続行し、ＡおよびＦは既に新しい集団であるので、ＧおよびＥをそのままにしておく。
【００４４】
Ｇが選ばれ、最高がＦＰ１におけるＦＰを得点し、さらに、試行によりＤおよびＢが順番に交換される（Ａは、ＦＰ１におけるＧより高得点であるので、交換で除外される候補とはならない）。ＧとＤとの交換が全体的な得点をより高めると判断した場合、この置換が保持される。
【００４５】
新しい最良集団は、Ａ，Ｂ，ＦおよびＧとなる。
【００４６】
ＦＰ２において、Ｂ，ＧおよびＦが新しい集団に既に入っているので、Ｉのみを残す。Ｉは、Ａに、次にＦに、取り替えられる試行がされる（この集団の中で低い得点か又は最初に最も低い得点を有する、ＡおよびＦは、現在における最良の新集団のメンバーである）。ＩとＡとの交換が全体的得点をより高める場合、この置換は保持される。
【００４７】
最終的に最良の新集団は、Ｂ，Ｆ，ＧおよびＩとなる。
【００４８】
図４は、その集団内の例が交換されるべきか否かを決定する場合、全体的に集団を採点することの重要性を概略的に例示している。カウント値に適用される採点関数は、図４で例示されるように非直線性であり、例えば、カウントが「０」でない場合、得点は「１」であり、カウントが「０」である場合、得点は「０」である。例えば、
ａ．ｌｏｇ（ｂ＋ｃｎ），−０．０５ｎ２＋５０ｎ  ．．．
など、多くの他の非直線形採点関数が同様に使用可能である。図４に例示するように、集団は、プログラム命令のリストが順序付けられてなる４列を具備している（例は、複数のテストの集団における１つのテストである）。集団（テストプログラム）をシミュレーションしている間に特定機能状態（ポイント）が出現したことのカウント値は、配列形式で示される。それぞれの機能ポイントが少なくとも一度出現することが望ましいが、一度ならず出現することによる更なる利益はない。図４の部分（ａ）では、例Ｔ１，Ｔ２，Ｔ３およびＴ４について示されている。各例がそれ自身について評価されるとき、配列の一番下に示される例の得点と合計値「９」とが生成される。これは、望まれる手法ではない。それよりも、機能ポイント得点は、水平に得られる得点によって示されるもので、集団の全体にわたって評価される。この例では、部分（ａ）で図示されたテストの間、各機能ポイントは１度刺激される。それは、ＦＰ４を刺激する唯一の例がＴ２であることを示している。しかしながら、この例は、他の機能ポイントのいずれも刺激しないので、それだけ低い得点となっている。
【００４９】
変更装置は、例Ｔ２を新しい候補の例Ｔ５に置き換えるべきか否か決定しなければならない。この例は、それ（Ｔ２）は機能ポイントの３つを刺激するが、ＦＰ４を刺激しないので、それだけ例として高い得点となる。
【００５０】
図４の部分（ｂ）は、Ｔ２がＴ５に取り換えられたときの得点を例示する。この場合、もし、個別の例がそれら自身得点されるとともに、次いでこれらの得点が合計されるなら、全ての集団の得点が増加する。しかしながら、ＦＰ４を刺激した唯一の例が取り除かれたので、機能ポイント得点の適用範囲を全体的に達成することについて、現在の集団がもっと悪いことが理解されるであろう。しかしながら、全体として集団が各機能ポイントに関して得点されるとともに、それらの集団の機能ポイント得点が合計されるその方式は、集団の得点がこのような交換およびそれに対するこのような交換がされるべきでなかったことにより減らされることを表示する正しい結果を生成する。
【００５１】
図５は、上述の技術を実行するために使用可能な汎用コンピュータ２００の概要を図示する。汎用コンピュータ２００は、中央処理装置２０２、ランダムアクセスメモリ２０４、リードオンリメモリ２０６、ネットワークインタフェースカード２０８、ハードディスク装置２１０、ディスプレイドライバ２１２およびモニタ２１４、並びにキーボード２１８およびマウス２２０を有してなるユーザ入出力回路２１６を有しており、すべて共通バス２２２を経由して接続されている。動作では中央処理装置２０２は、ランダムアクセスメモリ２０４、リードオンリメモリ２０６およびハードディスク装置２１０の１つ以上に記憶されているか、又はネットワークインタフェースカード２０８を経由して動的にダウンロードされるコンピュータ・プログラム命令を実行する。処理実行された結果は、ディスプレイドライバ２１２およびモニタ２１４によってユーザに対して表示することができる。汎用コンピュータ２００の動作を制御するためのユーザの入力は、キーボード２１８又はマウス２２０からユーザ入出力回路２１６を経由して受け取られる。コンピュータ・プログラムが各種の異なったコンピュータ言語で書かれることは理解されているであろう。コンピュータ・プログラムは、記憶媒体で記憶されるとともに配付されることができ、汎用コンピュータ２００に動的にダウンロードされることができる。汎用コンピュータ２００は、適切なコンピュータ・プログラムの制御により動作するとき、上述の実施形態について機能することができるとともに、上述の実施形態について機能する装置を構成するとみなすことができる。汎用コンピュータ２００の構造としては、かなり様々なものとすることができるとともに、図５は単なる一例である。
【００５２】
本発明の実施形態の説明が図面を参照して上述のように詳細に記載されているが、本発明は、実施形態に寸分違わぬものに限定されないとともに、特許請求の範囲で定義された本発明の思想および範囲から逸脱しないで、様々な変更および修正が当業者にとって可能であることが理解されるであろう。
【図面の簡単な説明】
【００５３】
【図１】データ処理システムの設計、製造、性能等についての試験および／又は妥当性を検査するために比較される結果状態の情報および種々のメカニズムで実行されるテストプログラムの概略的な例示である。
【図２】テストプログラムを生成するための本発明における種々の要素およびステップの概略的な例示である。
【図３】テストプログラムを構成するための採点選択および変化を例示するフローチャートである。
【図４】本発明で使用される採点測定例の概略的な例示である。
【図５】上記技術を実行するために使用可能な汎用コンピュータの概略的な例示である。
【符号の説明】
【００５４】
２    テスト命令
４    命令セットシミュレータ
６    ＲＴＬシミュレータ
８    ＦＰＧＡシミュレータ
１０  データ処理装置
１２  注釈付き構造定義
１４  命令セットシミュレータ
１６  命令ジェネレータ
１８  重み割り当て
２０  テンプレート
２２  集団
２４  採点メトリック（採点機構）
２６  複合機能ポイント
２８  外部機能ポイント
３０  追加シミュレータ
３２  変化機構
【図１】
2006164282.tif 000006
【図２】
2006164282.tif 000007
【図３】
2006164282.tif 000008
【図４】
2006164282.tif 000009
【図５】
2006164282.tif 000010
【外国語明細書】
2006164282.tif 000011
2006164282.tif 000012
2006164282.tif 000013
2006164282.tif 000014
2006164282.tif 000015
2006164282.tif 000016
2006164282.tif 000017
2006164282.tif 000018
2006164282.tif 000019
2006164282.tif 000020
2006164282.tif 000021
2006164282.tif 000022
2006164282.tif 000023
2006164282.tif 000024
2006164282.tif 000025
2006164282.tif 000026
2006164282.tif 000027
2006164282.tif 000028
2006164282.tif 000029
2006164282.tif 000030
2006164282.tif 000031
2006164282.tif 000032
2006164282.tif 000033
2006164282.tif 000034
2006164282.tif 000035
2006164282.tif 000036
2006164282.tif 000037