(57)【特許請求の範囲】
【請求項１】
データ格納部に格納されている複数のサンプル点の複数種類の性能項目値を、当該複数種類の性能項目で張られる空間を分割することで得られる複数のメッシュ要素のうち該当するメッシュ要素の座標値に変換し、前記データ格納部に格納する第１の処理と、
前記データ格納部に格納されている前記複数のサンプル点の座標値の集合を表現する二分決定グラフを生成する第２の処理と、
前記データ格納部に格納されている前記複数のサンプル点に含まれる第１のサンプル点の各座標値以下の座標値に対応するノードを、前記二分決定グラフにおける１を表す葉ノードから辿って根ノードに至るパスの数を計数することで、前記第１のサンプル点の数と前記複数のサンプル点のうち前記第１のサンプル点を支配する第２のサンプル点の数との合計の数を算出する第３の処理と、
算出された前記数を前記複数のサンプル点の数で除することで、前記第１のサンプル点の歩留り率を算出し、前記データ格納部に格納する第４の処理と、
を、コンピュータに実行させるプログラム。
【請求項２】
前記複数のサンプル点に含まれる各サンプル点を前記第１のサンプル点に設定して、前記第３の処理及び前記第４の処理を実施させる第５の処理
をさらに前記コンピュータに実行させる請求項１記載のプログラム。
【請求項３】
前記第３の処理は、
前記第１のサンプル点の各座標値以下の座標値に対応するノードを有し且つ当該ノードの全てが真の場合に１を表す葉ノードに達する第２の二分決定グラフを生成する処理と、
前記第２の二分決定グラフに含まれるノードに対応するノードを、前記第２の二分決定グラフにおける根ノードから１を表す葉ノードに至るパスの数を計数する処理と、
を含む請求項１又は２記載のプログラム。
【請求項４】
前記第３の処理において、
前記二分決定グラフの根ノードから前記葉ノードの方向にノードを順番に探索し、
前記第１のサンプル点の各座標値以下の座標値に対応するノードではないと確認された場合及び前記二分決定グラフにおける０を表す葉ノードに到達した場合には探索を中止し、
前記二分決定グラフにおける１を表す葉ノードに到達した場合には、逆方向に前記根ノードまで探索の経路を戻ることで前記パスの数を計数する
請求項１又は２記載のプログラム。
【請求項５】
前記逆方向に前記根ノードまで探索の経路を戻る処理において、当該経路上のノードにおいて、偽の枝方向のパス数と真の枝方向のパス数とを加算して、前記根ノードの方向の次のノードに移行する
請求項４記載のプログラム。
【請求項６】
データ格納部に格納されている複数のサンプル点の複数種類の性能項目値を、当該複数種類の性能項目で張られる空間を分割することで得られる複数のメッシュ要素のうち該当するメッシュ要素の座標値に変換し、前記データ格納部に格納する第１の処理と、
前記データ格納部に格納されている前記複数のサンプル点の座標値の集合を表現する二分決定グラフを生成する第２の処理と、
前記データ格納部に格納されている前記複数のサンプル点に含まれる第１のサンプル点の各座標値以下の座標値に対応するノードを、前記二分決定グラフにおける１を表す葉ノードから辿って根ノードに至るパスの数を計数することで、前記第１のサンプル点の数と前記複数のサンプル点のうち前記第１のサンプル点を支配する第２のサンプル点の数との合計の数を算出する第３の処理と、
算出された前記数を前記複数のサンプル点の数で除することで、前記第１のサンプル点の歩留り率を算出し、前記データ格納部に格納する第４の処理と、
を、コンピュータが実行する情報処理方法。
【請求項７】
複数のサンプル点の複数種類の性能項目値を格納するデータ格納部と、
前記データ格納部に格納されている複数のサンプル点の複数種類の性能項目値を、当該複数種類の性能項目で張られる空間を分割することで得られる複数のメッシュ要素のうち該当するメッシュ要素の座標値に変換し、前記データ格納部に格納する変換部と、
前記データ格納部に格納されている前記複数のサンプル点の座標値の集合を表現する二分決定グラフを生成する生成部と、
前記データ格納部に格納されている前記複数のサンプル点に含まれる第１のサンプル点の各座標値以下の座標値に対応するノードを、前記二分決定グラフにおける１を表す葉ノードから辿って根ノードに至るパスの数を計数することで、前記第１のサンプル点の数と前記複数のサンプル点のうち前記第１のサンプル点を支配する第２のサンプル点の数との合計の数を算出し、算出された前記数を前記複数のサンプル点の数で除することで、前記第１のサンプル点の歩留り率を算出し、前記データ格納部に格納する歩留り算出部と、
を有する情報処理装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本技術は、設計支援技術に関する。
【背景技術】
【０００２】
アナログ回路の自動設計技術には、歩留りを考慮したものがある。このような自動設計技術では、特定の設計パラメータ値及び特定の設計変数値の組み合わせに対するシミュレーション結果である複数種類の性能項目値（これらをまとめて性能とも呼ぶ。例えば、ゲイン、消費電力、線形性、面積、ノイズ、精度、ダイナミックレンジ、インピーダンス整合性など。）を有しているサンプル点を、上記組み合わせの値を変化させて複数生成し、当該複数のサンプル点の各々について、以下に示すような歩留りが定義されている。
【０００３】
前提として、サンプル点１の性能Ｐ1がサンプル点２の性能Ｐ2を支配するとは、以下のように定義される。
【数１】
0005772381.tif 000002
【０００４】
なお、ｐ1iは、性能Ｐ1に含まれるｉ番目の性能項目の値を表し、ｐ2iは、性能Ｐ2に含まれるｉ番目の性能項目の値を表す。（１）式は、サンプル点１の全ての性能項目の値がサンプル点２の対応する性能項目の値と同じ又は優れており、且つサンプル点１のいずれかの性能項目の値がサンプル点２の対応する性能項目の値より優れている場合に、性能Ｐ1が性能Ｐ2を支配するという。性能Ｐ1が性能Ｐ2を支配する場合には、サンプル点１がサンプル点２を支配するともいう。
【０００５】
また、性能についての支配関係については図１を用いて説明しておく。ここでは性能項目が２つだけであると仮定し、第１の性能項目を縦軸に性能項目１として設定し、小さい値ほど性能が高いものとする。また、第２の性能項目を横軸に性能項目２として設定し、小さい値ほど性能が高いものとする。ここで、シミュレーションを実施して性能項目１及び２の値を特定すると、図１に示すような２次元空間にプロットすることができる。図１の例ではＡ乃至Ｆの６つのサンプル点（解とも呼ぶ）が得られている。このような状況において、当然ながら性能項目１も２も小さい値の方が好ましいので、原点に近いほど良いサンプル点である。
【０００６】
そして、「Ｘ支配Ｙ」とは、Ｙの成分（即ち性能項目値）は全てＸの成分と同一又は劣っており、Ｙの成分の少なくとも１つはＸの成分より劣っていることを示す。図１のような２次元空間では、性能項目１も２も値が小さいＢの方がＥよりも良いサンプル点であるから「Ｂ支配Ｅ」であり、同様にＣの方がＦよりも良いサンプル点であるから「Ｃ支配Ｆ」である。一方ＡとＢとを比較すると、Ａの方が性能項目２の値は小さいが性能項目１の値はＢの方が小さいので「Ａ支配Ｂ」とは言えない。Ａ乃至Ｄについてはこのように支配関係が成り立たない。このように性能空間において他のサンプル点に支配されないサンプル点（非劣解とも呼ぶ）をパレートと呼ぶ。そして、パレートを結ぶ曲線（３次元以上の空間であれば曲面）Ａをパレート曲線（又は曲面）と呼ぶ。
【０００７】
また、図２に示すように、サンプル点はその性能項目値により丸印の位置にプロットされ、今回注目するサンプル点を黒丸で示す。なお、ハッチング付きの楕円は、サンプル点の分布領域を仮想的に示したものである。このような場合、注目するサンプル点に対して、全ての性能項目について同一又は優れた値を有するサンプル点は、黒丸の点を右上の頂点とする矩形の計測範囲に含まれるサンプル点である。なお、性能項目が３つ以上であっても条件は同様である。
【０００８】
上で述べた技術では、注目しているサンプル点の性能以上の性能を有するサンプル点の出現確率を歩留り率と規定している。従って、図２に示す計測範囲に出現するサンプル点の数＋１（注目しているサンプル点の分）を計数し、全サンプル点の数で除することによって、歩留り率を算出することになる。
【０００９】
しかしながら、各サンプル点について歩留りを算出する場合には、注目しているサンプル点毎に、支配関係を他の全てのサンプル点との間で確認するという処理が行われており、サンプル点の数が多くなると非常に処理時間がかかる。
【先行技術文献】
【特許文献】
【００１０】
【特許文献１】特開平６−９６０８３号公報
【特許文献２】特開平１０−２００３９４号公報
【非特許文献】
【００１１】
【非特許文献１】Yu Liu,et al,"Generation of yield-embedded Pareto-front for simultaneous optimization of yield and performances", Design Automation Conference (DAC), 2010 47th ACE/IEEE, 13-18, June 2010, pp.909-912
【発明の概要】
【発明が解決しようとする課題】
【００１２】
従って、本技術の目的は、一側面において、サンプル点間の支配関係に基づく歩留り率を高速に算出するための技術を提供することである。
【課題を解決するための手段】
【００１３】
本技術に係る歩留率算出方法は、（Ａ）データ格納部に格納されている複数のサンプル点の複数種類の性能項目値を、当該複数種類の性能項目で張られる空間を分割することで得られる複数のメッシュ要素のうち該当するメッシュ要素の座標値に変換し、データ格納部に格納する第１のステップと、（Ｂ）データ格納部に格納されている複数のサンプル点の座標値の集合を表現する二分決定グラフを生成する第２のステップと、（Ｃ）データ格納部に格納されている複数のサンプル点に含まれる第１のサンプル点の各座標値以下の座標値に対応するノードを、二分決定グラフにおける根ノードから１を表す葉ノードに至るパスの数を計数することで、複数のサンプル点のうち第１のサンプル点を支配する第２のサンプル点及び第１のサンプル点の数を算出する第３のステップと、（Ｄ）算出された数を上記複数のサンプル点の数で除することで、第１のサンプル点の歩留り率を算出し、データ格納部に格納する第４のステップとを含む。
【発明の効果】
【００１４】
サンプル点間の支配関係に基づく歩留り率を高速に算出できるようになる。
【図面の簡単な説明】
【００１５】
【図１】図１は、性能の支配関係を説明するための図である。
【図２】図２は、サンプル点の歩留りを説明するための図である。
【図３】図３は、第１の実施の形態に係る情報処理装置の機能ブロック図である。
【図４】図４は、データ格納部に格納されているデータの一例を示す図である。
【図５】図５は、第１の実施の形態に係るメインの処理フローを示す図である。
【図６】図６は、性能空間の一例を示す図である。
【図７】図７は、性能空間のメッシュ化について説明するための図である。
【図８】図８は、データ格納部に格納されるデータ（座標リストＬ）の一例を示す図である。
【図９】図９は、真理値表の一例を示す図である。
【図１０】図１０は、二分決定グラフＢＤＤの一例を示す図である。
【図１１】図１１は、ノードの統合を行った場合の二分決定グラフの一例を示す図である。
【図１２】図１２は、冗長ノードの削除を行った場合の二分決定グラフの一例を示す図である。
【図１３】図１３は、真理値表の一例を示す図である。
【図１４】図１４は、二分決定グラフの一例を示す図である。
【図１５】図１５は、葉ノードの統合後の二分決定グラフの一例を示す図である。
【図１６】図１６は、冗長ノード削除後の二分決定グラフの一例を示す図である。
【図１７】図１７は、ＺＤＤ生成過程の状態を表す図である。
【図１８】図１８は、ＺＤＤの一例を示す図である。
【図１９】図１９は、ＺＤＤ生成処理の処理フローを示す図である。
【図２０】図２０は、レベルのデータの一例を示す図である。
【図２１】図２１は、ＺＤＤ生成処理の処理フローを示す図である。
【図２２】図２２は、ＺＤＤ生成の具体例を説明するための図である。
【図２３】図２３は、ＺＤＤ生成の具体例を説明するための図である。
【図２４】図２４は、ＺＤＤ生成の具体例を説明するための図である。
【図２５】図２５は、ＺＤＤ生成の具体例を説明するための図である。
【図２６】図２６は、生成されたＺＤＤが表す頻度表を表す図である。
【図２７】図２７は、サンプル数計数処理の処理フローを示す図である。
【図２８】図２８は、特定のサンプル点の座標を示すための図である。
【図２９】図２９は、ＺＤＤ＿ｂの一例を示す図である。
【図３０】図３０は、サンプル数計数処理の処理フローを示す図である。
【図３１】図３１は、ＺＤＤ＿ｆ［１］のノード識別子を説明するための図である。
【図３２】図３２は、ＺＤＤ＿ｂのノード識別子を説明するための図である。
【図３３Ａ】図３３Ａは、ハッシュ表Ｐの第１の状態を示す図である。
【図３３Ｂ】図３３Ｂは、ハッシュ表Ｐの第２の状態を示す図である。
【図３３Ｃ】図３３Ｃは、ハッシュ表Ｐの第３の状態を示す図である。
【図３３Ｄ】図３３Ｄは、ハッシュ表Ｐの第４の状態を示す図である。
【図３３Ｅ】図３３Ｅは、ハッシュ表Ｐの第５の状態を示す図である。
【図３３Ｆ】図３３Ｆは、ハッシュ表Ｐの第６の状態を示す図である。
【図３４】図３４は、関数Ｈの処理フローを示す図である。
【図３５】図３５は、関数Ｈの処理フローを示す図である。
【図３６】図３６は、ＺＤＤ＿ｆ［１］の探索を説明するための図である。
【図３７】図３７は、ＺＤＤ＿ｆ［２］のノード識別子を説明するための図である。
【図３８】図３８は、ハッシュ表Ｐの一例を示す図である。
【図３９】図３９は、サンプル数算出処理の処理フローを示す図である。
【図４０】図４０は、データ格納部に格納されるデータの一例を示す図である。
【図４１】図４１は、処理結果の表示例を示す図である。
【図４２】図４２は、処理結果の表示例を示す図である。
【図４３】図４３は、第２の実施の形態に係る処理フローを示す図である。
【図４４】図４４は、辿るべきノードのリストを示す図である。
【図４５】図４５は、ＺＤＤ＿ｆ［１］におけるノード探索を示す図である。
【図４６】図４６は、ＺＤＤ＿ｆ［２］におけるノード探索を示す図である。
【図４７】図４７は、他のＺＤＤにおけるノード探索を示す図である。
【図４８】図４８は、データ格納部に格納されるデータの一例を示す図である。
【図４９】図４９は、コンピュータの機能ブロック図である。
【発明を実施するための形態】
【００１６】
［実施の形態１］
図３に、本実施の形態に係る情報処理装置１００の機能ブロック図を示す。情報処理装置１００は、データ格納部１１０と、データ格納部１１０に格納されているデータを用いて処理を行う処理部１２０とを有する。処理部１２０は、変換部１２１と、生成部１２２と、歩留り算出部１２３とを有する。
【００１７】
データ格納部１１０は、例えば図４に示すようなデータを格納している。本実施の形態では、サンプル点の識別子（ＩＤ）と、性能項目１乃至Ｍの値とを登録するようになっている。別途、各サンプル点について、該当する回路構成、設計変数値及び設計パラメータ値などを対応付けて登録する場合もあるが、本実施の形態では直接関係ないので省略する。例えば、本情報処理装置１００又は他のコンピュータで、設計変数値及び設計パラメータ値などに応じて回路シミュレーションを実施して、当該回路シミュレーションの結果（すなわち性能項目１乃至Ｍの値）を取得して、データ格納部１１０に格納しておく。
【００１８】
処理部１２０の変換部１２１は、各性能項目で張られる性能項目空間をメッシングして、各サンプル点について、そのサンプル点を包含するメッシュ要素を特定し、当該メッシュ要素の座標値を、当該サンプル点の座標値として特定する。
【００１９】
処理部１２０の生成部１２２は、データ格納部１１０に格納されているサンプル点の集合を表す二分決定グラフ（例えばＺＤＤ（Zero-suppressed BDD(Binary Decision Diagram)）を生成する。
【００２０】
処理部１２０の歩留り算出部１２３は、二分決定グラフを用いた処理を行って、各サンプル点の歩留り率を算出し、データ格納部１１０に格納する。
【００２１】
次に、図５乃至図４２を用いて、処理部１２０の処理について説明する。
【００２２】
まず、処理部１２０の変換部１２１は、性能空間をメッシュ化して、データ格納部１１０に格納されている各サンプル点の座標値（すなわち性能項目値）を、当該サンプル点を包含するメッシュ要素の座標値に変換して、データ格納部１１０に格納する（図５：ステップＳ１）。
【００２３】
例えば、図６に示すような性能空間を一例にして説明する。ここでは説明を簡単にするために、性能項目１及び２で張られる平面において、サンプル点sample1乃至sample5の５つのサンプル点を考える。例えば、sample1＝（１．１，１．１）、sample2＝（２．７，３．２）、sample3＝（３．２，２．７）、sample4＝（２．８，４．９）、sample5＝（５．１，１．６）であるとする。ここで、図７に示すように、この平面を３×３のメッシュ要素に分割すると、サンプル点sample1乃至sample5の座標値は、sample1＝（１，１）、sample2＝（２，２）、sample3＝（２，２）、sample4＝（２，３）、sample5＝（３，１）に変換される。
【００２４】
一般的には、例えば図８に示すようなデータをデータ格納部１１０に格納する。すなわち、サンプル点のＩＤと、性能項目１乃至Ｍの座標値とが格納される。但し、以下で述べる処理においてサンプル点数と歩留り率とがさらに格納される。このようなデータを座標リストＬと呼ぶものとする。
【００２５】
次に、処理部１２０の生成部１２２は、データ格納部１１０に格納されているサンプル点の集合を表すＺＤＤを生成するＺＤＤ生成処理を実施する（ステップＳ３）。ＺＤＤ生成処理については、図１９乃至図２６を用いて説明する。
【００２６】
なお、具体的な処理の説明より前に、ＺＤＤの前提となるＢＤＤから説明する。最初に、図９に示すような真理値表についての二分決定グラフＢＤＤについて説明する。この真理値表は、以下のような論理関数ｆ（ｘ1，ｘ2，ｘ3）で表される。なお、ダッシュ「’」は「ＮＯＴ」を表す。
ｆ（ｘ1，ｘ2，ｘ3）＝ｘ1’ｘ2ｘ3’＋ｘ1ｘ2’＋ｘ1ｘ2ｘ3’
【００２７】
二分決定グラフは、このような論理関数又は真理値表をグラフの形に圧縮して表現するものであり、論理関数同士の演算も圧縮したグラフ間の処理で行うことができる。
【００２８】
このような真理値表は、図１０のような二分決定木で表される。図１０の二分決定木では、ｘ1を根ノードとして、ｘ1が真「１」の場合の枝と、偽「０」の場合の枝とに分岐する。さらに、これらの枝の各々にはｘ2のノードが接続されており、ｘ2が真「１」の場合の枝と、偽「０」の場合の枝とに分岐する。さらに、これらの枝の各々にはｘ3のノードが接続されており、ｘ3が真「１」の場合の枝と、ｘ3が偽「０」の場合の枝とに分岐する。ｘ3の各々の枝には、葉ノードとして真理値表に従った「１」を表す葉ノード又は「０」を表す葉ノードが接続されている。
【００２９】
このように、根ノードから１を表す葉ノードに至るパスが、出力を１にする入力組み合わせを表す。
【００３０】
一般的には、等価ノードの統合を行うことで図１０のような二分決定木は圧縮される。図１０の場合、四角で囲った２つのｘ3については、偽「０」の枝に接続された葉ノードは「１」であり、真「１」の枝に接続された葉ノードは「０」であるということで等価なノードである。従って、いずれか１つに統合することができる。このような等価ノードの統合を行うと、図１１に示すような仮の二分決定グラフが得られる。
【００３１】
さらに、冗長ノードの削除を行うことで図１１のようにグラフが圧縮される。図１１のグラフにおいて四角で囲われた左側のｘ3は、真「１」の枝についても偽「０」の枝についても０についての葉ノードに接続されており、このノードは冗長である。さらに、右側のｘ3は、真「１」の枝についても偽「０」の枝についても１についての葉ノードに接続されており、このノードは冗長である。従って、これらのノードを削除すると、図１２に示すような二分決定グラフが得られる。ノードが削除されたため、図１２において四角で囲われた部分にはノードがなくなっている。このように、二分決定木から等価ノードと冗長ノードの削除を行ったグラフを二分決定グラフと呼ぶ。
【００３２】
次に、ＢＤＤの変種であるＺＤＤについて説明する。ＺＤＤは、出力が１となる入力組み合わせの中に、偽「０」が多い場合（すなわち疎な組み合わせの場合）に効果的であることが知られている。
【００３３】
例えば、図１３のような真理値表の場合、二分決定木は、図１４のように表される。なお、葉ノードを統合すると、図１５のように表される。上でも述べたように、ＢＤＤであれば、真「１」でも偽「０」でも同じノードに繋がるノードは冗長ノードであるから、図１５の４つのｘ3のノードのうち一番左側のノードと、左から３番目のノードとが冗長ノードとして特定されて、図１６に示すような二分決定グラフが得られる。
【００３４】
一方、ＺＤＤでは、真「１」の枝が、０を表す葉ノードに接続されているようなノードを削除して、削除されたノードの上位のノードの枝を、削除されたノードの偽「０」の枝に接続されたノードに接続する。
【００３５】
図１５の場合には、四角で囲われた右側のノードｘ3の真「１」の枝は、０を表す葉ノードに接続されているので、このｘ3のノードを削除して、上位のノードｘ2の偽「０」の枝を１を表す葉ノードに接続する。また、四角で囲われた左側のノードｘ3の真「１」の枝は、０を表す葉ノードに接続されているので、このノードｘ3も削除して、上位ノードｘ2の真「１」の枝を０を表す葉ノードに接続する。そうすると、図１７のような仮の二分決定グラフが得られる。この仮の二分決定グラフにおいて、四角で囲われたノードｘ2の真「１」の枝は、０を表す葉ノードに接続されているので、このノードｘ2も削除する。そうすると、このノードｘ2の上位ノードの真「１」の枝を１を表す葉ノードに接続する。このような圧縮を行うと、図１８に示すようなＺＤＤが完成する。図１８のＺＤＤにおいて四角の点線部分がノードが削除された部分である。
【００３６】
本実施の形態では座標リストＬを表すＺＤＤの生成処理を、図１９乃至図２６の処理フローで説明する。生成部１２２は、座標リストＬにおけるサンプル数からｎを設定する（図１９：ステップＳ２１）。具体的には、以下の式に従って算出する。
【数２】
0005772381.tif 000003
これは、座標リストＬにおけるサンプル数の、２を底とする対数値の小数点以下を繰り上げて整数値化したものである。
【００３７】
そして、生成部１２２は、メッシングの結果に基づき、各性能項目の軸について取り得る値各々について、ＺＤＤのレベルを１つ対応付け、対応付けを表すデータをデータ格納部１１０に格納する（ステップＳ２３）。例えば、図７に示すような性能空間において性能項目１をｘ、性能項目２をｙと表すものとすると、各軸の取り得る値各々とレベルとの対応付けは、図２０に示すように表される。図２０の例では、ｘもｙも１乃至３の値をとるので、ｘ1、ｘ2、ｘ3、ｙ1、ｙ2、ｙ3の順に、１から６までレベルを割り当てる。なお、ここでは葉ノードのレベルは７以上の値とする。
【００３８】
次に、生成部１２２は、ＺＤＤ＿ｆ［ｉ］（ｉは１以上ｎ以下の整数）に、恒偽関数のＺＤＤ（０を表す葉ノードのみ）を設定する（ステップＳ２５）。
【００３９】
そして、生成部１２２は、座標リストＬにおいて未処理のサンプル点があるか判断する（ステップＳ２７）。座標リストＬにおいて未処理のサンプル点が存在しない場合には、呼び出し元の処理に戻る。一方、未処理のサンプル点が存在する場合には、生成部１２２は、座標リストＬにおいて未処理のサンプル点を１つ特定し、当該サンプル点をｃｕｒに設定する（ステップＳ２９）。そして、生成部１２２は、桁上がりのためのＺＤＤ＿ｃに、サンプル点ｃｕｒのＺＤＤを設定する（ステップＳ３１）。そして処理は端子Ａを介して図２１の処理に移行する。
【００４０】
図２１の処理の説明に移行して、生成部１２２は、カウンタｉを１に設定する（ステップＳ３３）。そして、生成部１２２は、ＺＤＤ＿ｆ［ｉ］をＺＤＤ＿ｇに設定する（ステップＳ３４）。ＺＤＤ＿ｆ［ｉ］をＺＤＤ＿ｇに待避させる。その後、生成部１２２は、ＺＤＤ＿ｆ［ｉ］＋ＺＤＤ＿ｃ（ここで「＋」は排他的論理和を表す）の結果をＺＤＤ＿ｆ［ｉ］に設定し、ＺＤＤ＿ｇ＊ＺＤＤ＿ｃの結果をＺＤＤ＿ｃに設定する（ステップＳ３５）。その後、ＺＤＤ＿ｃが恒偽関数、すなわち桁上がりがない場合には、端子Ｂを介して図１９のステップＳ２７に戻る。一方、ＺＤＤ＿ｃが恒偽関数ではない場合には、生成部１２２は、ｉを１インクリメントして（ステップＳ３９）、ステップＳ３４に戻る。
【００４１】
このような処理にてサンプル点の出現状況に応じたＺＤＤ＿ｆ［ｉ］が生成されるようになる。
【００４２】
ここで図７に示すような５つのサンプル点を表すＺＤＤ＿ｆ［ｉ］を生成する過程を、図２２乃至図２５を用いて説明する。最初に、サンプル点（１，１）を処理する場合には、ＺＤＤ＿ｆ［１］は恒偽関数であり、サンプル点（１，１）のＺＤＤがＺＤＤ＿ｃに設定される。そしてステップＳ３５を実施すると、恒偽関数であるＺＤＤ＿ｆ［１］とサンプル点（１，１）のＺＤＤ＿ｃとの排他的論理和が行われ、ＺＤＤ＿ｆ［１］はサンプル点（１，１）のＺＤＤになる。なお、ＺＤＤ＿ｇ＊ＺＤＤ＿ｃ＝０で桁上がりはないので、次のサンプル点の処理に移行する。
【００４３】
次に、サンプル点（３，１）を処理する場合を、図２２を用いて説明する。図２２に示すように、（１，１）を表すＺＤＤと、（３，１）を表すＺＤＤとについて排他的論理和を算出すると、（１，１）と（３，１）とが出現することを表すＺＤＤが生成される。なお、ＺＤＤ＿ｇ＊ＺＤＤ＿ｃ＝０で桁上がりはないので、次のサンプル点の処理に移行する。
【００４４】
次に、サンプル点（２，２）を処理する場合を、図２３を用いて説明する。図２３に示すように、前回の結果を表すＺＤＤと、（２，２）を表すＺＤＤとについて排他的論理和を算出すると、（１，１）、（３，１）及び（２，２）が出現することを表すＺＤＤが生成される。なお、ＺＤＤ＿ｇ＊ＺＤＤ＿ｃ＝０で桁上がりはないので、次のサンプル点の処理に移行する。
【００４５】
次に、サンプル点（２，３）を処理する場合を、図２４を用いて説明する。図２４に示すように、前回の結果を表すＺＤＤと、（２，３）を表すＺＤＤとについて排他的論理和を算出すると、（１，１）、（３，１）、（２，２）及び（２，３）が出現することを表すＺＤＤが生成される。なお、ＺＤＤ＿ｇ＊ＺＤＤ＿ｃ＝０で桁上がりはないので、次のサンプル点の処理に移行する。
【００４６】
最後に、サンプル点（２，２）を処理する場合を、図２５を用いて説明する。図２５に示すように、前回の結果を表すＺＤＤと、（２，２）を表すＺＤＤとについて排他的論理和を算出すると、（１，１）、（３，１）及び（２，３）が出現することを表すＺＤＤ＿ｆ［１］（ｆ1と表す）が生成される。さらに、ＺＤＤ＿ｇ＊ＺＤＤ＿ｃ＝１で桁上がりがあるので、（２，２）を表すＺＤＤ＿ｃが生成され、これがそのままＺＤＤ＿ｆ［２］（ｆ2と表す）に設定される。
【００４７】
このように、２つのＺＤＤが生成されて、以下の処理で用いられる。
【００４８】
なお、このような２つのＺＤＤを、頻度表形式で表せば、図２６に示すような表になる。図２６の頻度表では、各軸について取り得る座標値の組み合わせの各々について、ｆ2ｆ1の２ビットの出現頻度を表している。すなわち、Ｆの列で示すように、「０１」は「１」であり、「１０」は２を表している。
【００４９】
図５の処理の説明に戻って、処理部１２０の歩留り算出部１２３は、座標リストＬにおいて未処理のサンプル点を１つ特定する（ステップＳ５）。そして、歩留り算出部１２３は、特定されたサンプル点についてサンプル数計数処理を実施する（ステップＳ９）。サンプル数計数処理については、図２７乃至図４０を用いて説明する。
【００５０】
まず、歩留り算出部１２３は、ＺＤＤ＿ｂに、恒真関数のＺＤＤを設定する（図２７：ステップＳ４１）。そして、歩留り算出部１２３は、性能項目数をｒに設定する（ステップＳ４２）。また、歩留り算出部１２３は、ｊを１に設定する（ステップＳ４３）。
【００５１】
さらに、歩留り算出部１２３は、ａに対して、特定されたサンプル点の座標のｊ番目の要素の要素値を設定する（ステップＳ４５）。例えば、図２８に示すように、サンプル点（２，２）が特定されたとする。そうすると、ｊ＝１であればａ＝２であり、ｊ＝２でもａ＝２となる。なお、ｊ番目の要素をｖとおくものとする。
【００５２】
なお、サンプル点（２，２）が特定されると、このサンプル点を支配するサンプル点（存在するかしないかをとわず）の座標は（１，２）、（１，１）及び（２，１）となる。さらに、歩留り率を算出する場合には、同じ座標（２，２）及びそれ自身もカウント対象である。すなわち、ｘ≦２及びｙ≦２がサンプル数計数の条件となる。
【００５３】
そして、歩留り算出部１２３は、ｋを１に初期化する（ステップＳ４７）。その後、歩留り算出部１２３は、ｋがａ以下であるか判断する（ステップＳ４９）。ｋがａ以下であれば、ＺＤＤ＿ｂ＊ｖkを、ＺＤＤ＿ｂに設定し、ｋを１インクリメントする（ステップＳ５１）。そしてステップＳ４９に戻る。
【００５４】
ｖkは、ｊ＝１であれば、ｖ＝ｘであり、ｊ＝２であればｖ＝ｙである。すなわち、恒真関数のＺＤＤ＿ｂに対してｘ1と、ｘ2とを最初のｊに関するループで乗ずる。さらに、２回目のループでは、ｊ＝２であるから、ｙ1及びｙ2がＺＤＤ＿ｂに乗じられる。
【００５５】
ステップＳ４９でｋがａを超えた場合には、歩留り算出部１２３は、ｊがｒ以下であるか判断する（ステップＳ５３）。ｊがｒを超えた場合には、端子Ｃを介して図３０の処理に移行する。一方、ｊがｒ以下である場合には、歩留り算出部１２３は、ｊを１インクリメントして（ステップＳ５５）、処理はステップＳ４５に戻る。
【００５６】
このような処理を実施することで、サンプル点（２，２）を特定した場合には、図２９に示すようなＺＤＤ＿ｂが生成される。図２９のように、サンプル点（２，２）で特定される条件ｘ≦２及びｙ≦２に該当する各座標値に対応するノードｘ1、ｘ2、ｙ1及びｙ2が全て真である場合に１を表す葉ノードに達するＺＤＤが生成される。
【００５７】
処理は端子Ｃを介して図３０の処理に移行して、歩留り算出部１２３は、カウンタｉを１に初期化する（ステップＳ５７）。また、歩留り算出部１２３は、ＺＤＤ＿ｆ［ｉ］の各ノードに対応するパス数を登録するためのハッシュ表Ｐを、ＺＤＤ＿ｆ［ｉ］から生成する（ステップＳ５９）。ハッシュ表Ｐは、ノード毎にパス数を登録するものである。以下では、説明を分かり易くするために、図３１に示すように識別子を付与するものとする。図３１の例では、０を表す葉ノードの識別子は０であり、１を表す葉ノードの識別子は１であり、根ノードのｘ1の識別子は２であり、ｘ2のノード識別子は３であり、ｘ3のノード識別子は４であり、ｙ1のノード識別子は５であり、ｙ3のノード識別子は６である。そして、ハッシュ表Ｐは、例えば図３３Ａに示すように、ノードの識別子０乃至６の各々について、パス数が登録されるようになっている。なお、この段階ではパス数は登録されていない。また、ＺＤＤ＿ｂについても図３２に示すように、以下の説明を分かり易くするために、ノードに識別子を付与しておく。
【００５８】
次に、歩留り算出部１２３は、ハッシュ表Ｐ［葉ノード］＝葉の値、Ｐ［他のノード］＝−１を設定する（ステップＳ６１）。初期値を設定するものである。これにて図３３Ａの状態になる。
【００５９】
その後、歩留り算出部１２３は、ＺＤＤ＿ｆ［ｉ］及びＺＤＤ＿ｂの根ノードを引数として設定して、関数Ｈ（ｆｎｏｄｅ，ｂｎｏｄｅ）を呼び出す（ステップＳ６３）。関数Ｈは、ハッシュ表を完成させて、第一引数のパス数を得るための関数である。この関数Ｈの処理については図３４乃至図４０を用いて説明する。
【００６０】
歩留り算出部１２３は、Ｐ［ｆｎｏｄｅ］＝−１であるか判断する（図３４：ステップＳ７１）。−１は初期値であり、−１以外の値が設定されているということは、ｆｎｏｄｅのノードについての処理は完了しているので、呼び出し元の処理に戻る。一方、初期値である−１が設定されたままである場合には、歩留り算出部１２３は、ｆｎｏｄｅの変数をｐに設定し、ｐのレベルをａに設定する（ステップＳ７３）。今、ｆｎｏｄｅが図３１のノード２である場合には、ｐ＝ｘ1であり、図２０からａ＝１である。
【００６１】
また、歩留り算出部１２３は、ｂｎｏｄｅのノードの変数をｑに設定し、ｑのレベルをｂに設定する（ステップＳ７５）。ｂｎｏｄｅが、図３２のノード７である場合には、ｑ＝ｘ1であり、図２０からｂ＝１である。
【００６２】
そして、歩留り算出部１２３は、ａ＝ｂであるか判断する（ステップＳ７７）。ａ＝ｂではない場合には、端子Ｄを介して図３５の処理に移行する。一方、ａ＝ｂであれば、歩留り算出部１２３は、Ｐ［ｆｎｏｄｅの偽（０）枝の子ノード］＝−１であるか判断する（ステップＳ７９）。ハッシュ表Ｐ（図３３Ａ）において、ｆｎｏｄｅが図３１のノード２である場合、ｆｎｏｄｅの偽（０）枝の子ノードであるノード３の値は「−１」である。
【００６３】
Ｐ［ｆｎｏｄｅの偽（０）枝の子ノード］＝−１でなければ、ステップＳ８３に移行する。一方、Ｐ［ｆｎｏｄｅの偽（０）枝の子ノード］＝−１であれば、歩留り算出部１２３は、関数Ｈ（ｆｎｏｄｅ｜s=0，ｂｎｏｄｅ｜t=1）を再帰的に呼び出す（ステップＳ８１）。s＝０は、ｆｎｏｄｅの偽（０）枝が指す子ノードを表し、t＝１は、ｂｎｏｄｅの真（１）枝が指す子ノードを表す。従って、上で述べた例では、図３１のノード３と図３２のノード８をＨの第一引数と第二引数に設定する。ステップＳ８１が完了すると、ステップＳ８３に移行する。
【００６４】
ステップＳ８１の後又はＰ［ｆｎｏｄｅの偽（０）枝の子ノード］＝−１でなければ、歩留り算出部１２３は、Ｐ［ｆｎｏｄｅの真（１）枝の子ノード］＝−１であるか判断する（ステップＳ８３）。Ｐ［ｆｎｏｄｅの真（１）枝の子ノード］＝−１でなければ端子Ｅを介して図３５の処理に移行する。一方、Ｐ［ｆｎｏｄｅの真（１）枝の子ノード］＝−１であれば、歩留り算出部１２３は、関数Ｈ（ｆｎｏｄｅ｜s=1，ｂｎｏｄｅ｜t=1）を再帰的に呼び出す（ステップＳ８５）。s＝１は、ｆｎｏｄｅの真（１）枝の子ノードを表し、t＝１は、ｂｎｏｄｅの真（１）枝の子ノードを表す。従って、上で述べた例では、図３１のノード５と図３２のノード８を、Ｈの第一引数と第二引数に設定する。ステップＳ８５が完了すると、端子Ｅを介して図３５の処理に移行する。
【００６５】
図３５において端子Ｅ以降の処理の説明に移行して、歩留り算出部１２３は、Ｐ［ｆｎｏｄｅ］＝Ｐ［ｆｎｏｄｅの偽（０）枝の子ノード］＋Ｐ［ｆｎｏｄｅの真（１）枝の子ノード］と設定する（ステップＳ８７）。そして呼び出し元の処理に戻る。
【００６６】
さらに、図３５において端子Ｄ以降の処理の説明に移行して、歩留り算出部１２３は、ａ＞ｂであるか判断する（ステップＳ８９）。ｆｎｏｄｅのレベルａが、ｂｎｏｄｅのレベルｂより上である場合には、ｂｎｏｄｅのレベルをレベルａに近づけるため、歩留り算出部１２３は、Ｈ（ｆｎｏｄｅ，ｂｎｏｄｅ｜s=1）を再帰的に呼び出す（ステップＳ９３）。ｆｎｏｄｅについては変更せず、ｂｎｏｄｅについては真（１）枝の子ノードに変更することを意味する。ステップＳ９３の後には呼び出し元の処理に戻る。
【００６７】
一方、ａ＜ｂである場合には、ｆｎｏｄｅのレベルと同一のレベルのノードがｂｎｏｄｅには存在しないので、歩留り算出部１２３は、Ｐ［ｆｎｏｄｅ］＝０を設定する（ステップＳ９１）。そして、呼び出し元の処理に戻る。
【００６８】
上で述べた例では、ステップＳ８１で、図３１のノード３と図３２のノード８を、Ｈの第一引数と第二引数に設定して、図３４の最初から処理を実施する。図３６においては、（ｖ，ｗ）は、図３１におけるノード識別子ｖと、図３２におけるノード識別子ｗを表すものとする。ここでは、（１）の遷移を行ったことになる。
【００６９】
この場合も、ステップＳ７７でａ＝ｂとなり、Ｐ［ノード３の偽（０）枝の子ノードであるノード４］＝−１であるので、再度ステップＳ８１に移行する。図３６においては、（２）の遷移を行ったことになる。
【００７０】
そうすると、図３１のノード４と図３２のノード９をＨの第一引数及び第二引数に設定する。そうすると、ａ＝３でｂ＝４となるので、ステップＳ７７からステップＳ８９に移行する。ステップＳ８９では、ａ＜ｂであるから、ステップＳ９１に移行する。そして、ｆｎｏｄｅのノード識別子は「４」であるから、Ｐ［４］＝０を設定する。すなわち、図３３Ｂに示すようなハッシュ表Ｐに変化する。図３６においては、（３）の遷移を行って１つ上位の階層の処理に戻る。
【００７１】
そうすると、ステップＳ８３で、Ｐ［ｆｎｏｄｅであるノード３の真（１）枝の子ノード］＝−１であるので、ステップＳ８５において、図３１のノード６と図３２のノード９をＨの第一引数及び第二引数に設定して、図３４の最初から処理を実施する。図３６においては、（４）の遷移を行ったことになる。
【００７２】
そうすると、ａ＝６でｂ＝４であるから、ステップＳ７７からステップＳ８９に移行して、さらにａ＞ｂであるから、ステップＳ９３に移行する。ここでは、図３１のノード６と図３２のノード１０をＨの第一引数及び第二引数に設定して、図３４の最初から処理を実施する。図３６においては、（５）の遷移を行ったことになる。
【００７３】
そうすると、ａ＝６でｂ＝５であるから、ステップＳ７７からステップＳ８９に移行して、さらにａ＞ｂであるから、ステップＳ９３に移行する。ここでは、図３１のノード６と図３２において１を表す葉ノードに設定して、図３４の最初から処理を実施する。図３６においては、（６）の遷移を行ったことになる。
【００７４】
そうすると、ａ＝６でｂ＝７であるから、ステップＳ７７からステップＳ８９に移行して、さらにａ＜ｂであるから、ステップＳ９１に移行する。そして、ｆｎｏｄｅのノード識別子は「６」であるから、Ｐ［６］＝０を設定する。すなわち、図３３Ｃに示すようなハッシュ表Ｐに変化する。図３６においては、（７）の遷移を行って１つ上位の階層の処理に戻る。但し、ステップＳ９３が終了すると、さらに１つ上位の階層の処理に戻るので、図３６においては、（８）の遷移を行って１つ上位の階層の処理に戻る。さらに、この階層においてもステップＳ９３が終了することになるので、さらに１つ上位の階層の処理に戻るので、図３６においては、（９）の遷移を行って１つ上位の階層の処理に戻る。
【００７５】
そうすると、ステップＳ８５が終了してステップＳ８７に移行し、Ｐ［ノード３の偽（０）枝の子ノードであるノード４］＋Ｐ［ノード３の真（１）枝の子ノードであるノード６］＝Ｐ［３」＝０＋０＝０が設定される。すなわち、図３３Ｄに示すようなハッシュ表Ｐに変化する。そして、図３６においては、（１０）の遷移を行って１つ上位の階層の処理に戻る。
【００７６】
根ノードの処理に戻ると、ステップＳ８３でＰ［ノード２の真（１）枝の子ノード］＝Ｐ［５］＝−１であるので、ステップＳ８５に移行する。そして、図３１のノード５と図３２のノード８をＨの第一引数及び第二引数に設定して、図３４の最初から処理を実施する。図３６においては、（１１）の遷移を行ったことになる。
【００７７】
そうすると、ａ＝４でｂ＝２であるので、ステップＳ７７からステップＳ８９に移行して、ａ＞ｂであるから、ステップＳ９３に移行する。ここでは、図３１のノード５と図３２のノード９をＨの第一引数と第二引数に設定して、図３４の最初から処理を実施する。図３６においては、（１２）の遷移を行ったことになる。
【００７８】
そうすると、ａ＝４でｂ＝４であるので、ステップＳ７７からステップＳ７９に移行して、Ｐ［ノード５の偽（０）枝の子ノード＝０を表す葉ノード］＝０であるから、ステップＳ８３に移行する。さらに、Ｐ［ノード５の真（１）枝の子ノード＝１を表す葉ノード］＝１であるから、ステップＳ８７に移行する。ステップＳ８７では、Ｐ［ノード５］＝Ｐ［０を表す葉ノード］＋Ｐ［１を表す葉ノード］＝０＋１＝１となる。これにより、ハッシュ表Ｐは図３３Ｅの状態に変化する。図３６においては、（１３）の遷移を行って１つ上位の階層の処理に戻る。但しステップＳ９３が終了すると、さらに１つ上位の階層に戻るので、図３６においては、（１４）の遷移を行って１つ上位の階層（根ノードの階層）の処理に戻る。
【００７９】
根ノードの階層の処理ではステップＳ８５が完了したのでステップＳ８７に移行して、Ｐ［ｆ１の根ノード２］＝Ｐ［３］＋Ｐ［５］＝０＋１＝１となる。これにより、ハッシュ表Ｐは図３３Ｆの状態に変化する。これによって、Ｐ［２］＝１という根ノードについての結果を得ることができたことになる。
【００８０】
図３０の処理の説明に戻って、歩留り算出部１２３は、ｉがｍ以下であるか判断する（ステップＳ６５）。ｍは、ＺＤＤ＿ｆ［ｉ］（ｉは１以上ｎ以下の整数）のうち恒偽関数でない最も上位の桁を表す。ｉがｍ未満であれば、歩留り算出部１２３は、ｉを１インクリメントして（ステップＳ６７）、ステップＳ５９に戻る。
【００８１】
上で述べた例では、ＺＤＤ＿ｆ［２］についても処理を行う。この場合、図３７に示すように、ノードに識別子を付与すると、ハッシュ表Ｐは、図３８に示すようになる。この図３８の例でも、根ノードの識別子２についての値Ｐ［２］＝１が得られる。
【００８２】
一方、ｉがｍ以上になった場合には、歩留り算出部１２３は、サンプル数算出処理を実施する（ステップＳ６９）。サンプル数算出処理については、図３９を用いて説明する。そして処理は呼び出し元の処理に戻る。
【００８３】
歩留り算出部１２３は、サンプル数Ｓを０に初期化する（図３９：ステップＳ１０１）。また、歩留り算出部１２３は、カウンタｉ＝１と初期化する（ステップＳ１０３）。そして、歩留り算出部１２３は、Ｓ＋Ｐ［ＺＤＤ＿ｆ［ｉ］の根ノード］＊２i-1をＳに設定する（ステップＳ１０５）。ｉ＝１では、Ｐ［ＺＤＤ＿ｆ［１］の根ノード］＝１＊２0＝１であるから、最初はＳ＝１となる。
【００８４】
そして、歩留り算出部１２３は、ｉがｍ以上であるか判断する（ステップＳ１０７）。ｉがｍ未満であれば、歩留り算出部１２３はｉを１インクリメントして（ステップＳ１０９）、処理はステップＳ１０５に戻る。
【００８５】
ｉ＝２であれば、Ｐ［ＺＤＤ＿ｆ［２］の根ノード］＝１＊２1＝２であるから、Ｓ＝３となる。
【００８６】
ｉがｍ以上である場合には、歩留り算出部１２３は、Ｓをサンプル数として、データ格納部１１０に格納する（ステップＳ１１１）。そして呼び出し元の処理に戻る。
【００８７】
なお、このサンプル数は、同一の座標値の他のサンプル点と自サンプル点とを併せた数である。
【００８８】
図５の処理の説明に戻って、歩留り算出部１２３は、歩留り率を、サンプル数Ｓ／全サンプル点数によって算出し、データ格納部１１０に格納する（ステップＳ１１）。これによって、例えば図４０に示すようなデータがデータ格納部１１０に格納される。すなわち、各サンプル点について、サンプル数の列及び歩留り率の列に値が設定されるようになる。
【００８９】
そして、歩留り算出部１２３は、座標リストＬにおいて未処理のサンプル点が存在するか判断する（ステップＳ１３）。未処理のサンプル点が存在する場合にはステップＳ５に戻る。一方、未処理のサンプル点が存在しない場合には処理を終了する。
【００９０】
このような処理を実施すれば、各サンプル点について歩留り率が高速に算出されるので、例えば図４１のようなグラフを高速に表示させることができるようになる。図４１の例は、性能項目１が遅延（Delay(ps)）（Ｘ軸に相当）であり、性能項目２が電流値（Current(mA)）（Ｙ軸に相当）である場合に、Ｚ軸方向に歩留り率（Yield）を表すと、遅延が大きく電流値が大きいほど歩留り率が高くなる曲面が得られる。なお、ある特定の歩留り率を指定して、ＸＹ平面に平行な平面で切断すると、図４２に示すような図も表示できる。図４２の例では、８０％の歩留り率を得るサンプル点を丸印で示し、５０％の歩留り率を得るサンプル点を三角印で示している。このようにそれぞれの分布を把握できるようになる。
【００９１】
［実施の形態２］
本実施の形態に係る情報処理装置の構成は、第１の実施の形態と同じであるので、説明を省略する。但し、個々の要素の処理内容については、以下のように変更される。
【００９２】
本実施の形態に係る情報処理装置１００は、図４３乃至図４７の処理を実施する。処理部１２０の変換部１２１は、性能空間をメッシュ化して、データ格納部１１０に格納されている各サンプル点の座標値（すなわち性能項目値）を、当該サンプル点を包含するメッシュ要素の座標値に変換して、データ格納部１１０に格納する（図４３：ステップＳ２０１）。この処理は、図６及び図７を用いて説明したような処理である。また、図８に示すようなデータを、データ格納部１１０に格納する。
【００９３】
次に、生成部１２２は、データ格納部１１０に格納されているサンプル点の集合を表現する二分決定グラフ（例えばＺＤＤやＢＤＤ）を生成する（ステップＳ２０３）。ＺＤＤなどの生成方法については、第１の実施の形態で説明したものと同様である。
【００９４】
そして、歩留り算出部１２３は、二分決定グラフの探索を以下で述べるように行って、特定のサンプル点を支配するサンプル点及び当該特定のサンプル点の数を算出し、データ格納部１１０に格納する（ステップＳ２０５）。具体的には、特定のサンプル点の各座標値以下の座標値に対応するノードを、二分決定グラフにおける根ノードから辿って１を表す葉ノードに至るパスの数を計数するように、二分決定グラフの探索を実施する。例えば、サンプル点（ｘ，ｙ）＝（２，２）が特定のサンプル点であるとすると、ｘ≦２及びｙ≦２に対応するノードであるｘ1とｘ2とｙ1とｙ2とが辿るべきノードとして特定される（図４４）。そして、二分決定グラフにおいて根ノードから、このように特定されたノードを辿って１を表す葉ノードに至るパスを探索する。図４５のようなＺＤＤの場合には、根ノードｘ1から、図４４に示すようなノード以外のノードを経由することなく、ｙ1を経由して、１を表す葉ノードに至るパスが１本特定される。
【００９５】
図４６のようなＺＤＤの場合には、根ノードｘ2から、図４４に示すようなノード以外のノードを経由することなく、ｙ2を経由して、１を表す葉ノードに至るパスが１本特定される。
【００９６】
また、図４７のようなＺＤＤの場合には、根ノードｘ1から、ノードｘ2とノードｙ2とを経由する第１のパスと、ノードｙ1を経由する第２のパスとが得られる。
【００９７】
なお、ＺＤＤは１桁分のＺＤＤだけではなく、２桁分以上のＺＤＤが存在する場合もある。その場合には、それぞれの桁についてパスを計数して、各桁ｉの重み２i-1を乗じた上で加算する。例えば図４５が１桁目のＺＤＤで、図４６が２桁目のＺＤＤであるとすると、１×２1-1＋１×２2-1＝３が算出される。
【００９８】
その後、歩留り算出部１２３は、ステップＳ２０５で算出された数を、データ格納部１１０に格納されている全サンプル点の数で除することで、歩留り率を算出し、データ格納部１１０に格納する（ステップＳ２０７）。これによって、図４８に示すようなデータが、データ格納部１１０に格納される。図４８の例では、サンプル点ＩＤが１のサンプル点を特定のサンプル点として処理した例を示している。他のサンプル点についても、ステップＳ２０５及びＳ２０７を実施すれば、同様にサンプル点数及び歩留り率もデータ格納部１１０に格納される。
【００９９】
このようにすれば、二分決定グラフの生成は一度に済み、二分決定グラフの探索を、サンプル点毎に実施すればよいので、各サンプル点について他の全てのサンプル点について支配関係を特定するよりも効率的に、即ち高速に歩留り率を算出することができるようになる。なお、同じメッシュ要素に属するサンプル点については、１度だけ上で述べた処理を実施すれば良いので、この点においても処理が高速化される。
【０１００】
以上本技術の実施の形態を説明したが、本技術はこれに限定されるものではない。例えば、機能ブロック図は一例であって、必ずしも実際のプログラムモジュール構成とは一致しない場合もある。さらに、処理フローについても、処理結果が変わらない限り処理順番を入れ替えるようにしても良い。
【０１０１】
なお、上で述べた情報処理装置１００は、コンピュータ装置であって、図４９に示すように、メモリ２５０１とＣＰＵ（Central Processing Unit）２５０３とハードディスク・ドライブ（ＨＤＤ：Hard Disk Drive）２５０５と表示装置２５０９に接続される表示制御部２５０７とリムーバブル・ディスク２５１１用のドライブ装置２５１３と入力装置２５１５とネットワークに接続するための通信制御部２５１７とがバス２５１９で接続されている。オペレーティング・システム（ＯＳ：Operating System）及び本実施例における処理を実施するためのアプリケーション・プログラムは、ＨＤＤ２５０５に格納されており、ＣＰＵ２５０３により実行される際にはＨＤＤ２５０５からメモリ２５０１に読み出される。ＣＰＵ２５０３は、アプリケーション・プログラムの処理内容に応じて表示制御部２５０７、通信制御部２５１７、ドライブ装置２５１３を制御して、所定の動作を行わせる。また、処理途中のデータについては、主としてメモリ２５０１に格納されるが、ＨＤＤ２５０５に格納されるようにしてもよい。本技術の実施例では、上で述べた処理を実施するためのアプリケーション・プログラムはコンピュータ読み取り可能なリムーバブル・ディスク２５１１に格納されて頒布され、ドライブ装置２５１３からＨＤＤ２５０５にインストールされる。インターネットなどのネットワーク及び通信制御部２５１７を経由して、ＨＤＤ２５０５にインストールされる場合もある。このようなコンピュータ装置は、上で述べたＣＰＵ２５０３、メモリ２５０１などのハードウエアとＯＳ及びアプリケーション・プログラムなどのプログラムとが有機的に協働することにより、上で述べたような各種機能を実現する。
【０１０２】
以上述べた本実施の形態をまとめると以下のとおりである。
【０１０３】
本実施の形態に係る情報処理方法は、（Ａ）データ格納部に格納されている複数のサンプル点の複数種類の性能項目値を、当該複数種類の性能項目で張られる空間を分割することで得られる複数のメッシュ要素のうち該当するメッシュ要素の座標値に変換し、データ格納部に格納する第１の処理と、（Ｂ）データ格納部に格納されている複数のサンプル点の座標値の集合を表現する二分決定グラフを生成する第２の処理と、（Ｃ）データ格納部に格納されている複数のサンプル点に含まれる第１のサンプル点の各座標値以下の座標値に対応するノードを、二分決定グラフにおける１を表す葉ノードから辿って根ノードに至るパスの数を計数することで、複数のサンプル点のうち第１のサンプル点を支配する第２のサンプル点及び第１のサンプル点の数を算出する第３の処理と、（Ｄ）算出された数を複数のサンプル点の数で除することで、第１のサンプル点の歩留り率を算出し、データ格納部に格納する第４の処理とを含む。
【０１０４】
このようにすることで、各サンプル点について残余のサンプル点との支配関係を確認した上で歩留り率を算出するよりも、効率的に且つ高速に歩留り率を算出することができるようになる。
【０１０５】
また、本実施の形態に係る情報処理方法が、複数のサンプル点に含まれる各サンプル点を第１のサンプル点に設定して、第３の処理及び第４の処理を実施させる第５の処理をさらに含むようにしても良い。多数のサンプル点について処理を行えば、より効果が大きくなる。
【０１０６】
なお、上で述べた第３の処理は、（ｃ１）第１のサンプル点の各座標値以下の座標値に対応するノードを有し且つ当該ノードの全てが真の場合に１を表す葉ノードに達する第２の二分決定グラフを生成する処理と、（ｃ２）第２の二分決定グラフに含まれるノードに対応するノードを、上記二分決定グラフにおける根ノードから辿って１を表す葉ノードに至るパスの数を計数する処理とを含むようにしても良い。
【０１０７】
さらに、上で述べた第３の処理においては、（ｃ１１）二分決定グラフの根ノードから葉ノードの方向にノードを順番に探索し、（ｃ１２）第１のサンプル点の各座標以下の座標値に対応するノードではないと確認された場合及び二分決定グラフにおける０を表す葉ノードに到達した場合には探索を中止し、（ｃ１３）二分決定グラフにおける１を表す葉ノードに到達した場合には、逆方向に根ノードまで探索の経路を戻ることで上記パスの数を計数するようにしても良い。これによって、適切にパス数を計数できるようになる。
【０１０８】
なお、上で述べた逆方向に根ノードまで探索の経路を戻る処理において、当該経路上のノードにおいて、偽の枝方向のパス数と真の枝方向のパス数とを加算して、根ノードの方向の次のノードに移行するようにしても良い。処理を効率化するためである。
【０１０９】
なお、上記方法による処理をコンピュータに行わせるためのプログラムを作成することができ、当該プログラムは、例えばフレキシブルディスク、ＣＤ−ＲＯＭ、光磁気ディスク、半導体メモリ、ハードディスク等のコンピュータ読み取り可能な記憶媒体又は記憶装置に格納される。尚、中間的な処理結果はメインメモリ等の記憶装置に一時保管される。
【０１１０】
（付記１）
データ格納部に格納されている複数のサンプル点の複数種類の性能項目値を、当該複数種類の性能項目で張られる空間を分割することで得られる複数のメッシュ要素のうち該当するメッシュ要素の座標値に変換し、前記データ格納部に格納する第１の処理と、
前記データ格納部に格納されている前記複数のサンプル点の座標値の集合を表現する二分決定グラフを生成する第２の処理と、
前記データ格納部に格納されている前記複数のサンプル点に含まれる第１のサンプル点の各座標値以下の座標値に対応するノードを、前記二分決定グラフにおける１を表す葉ノードから辿って根ノードに至るパスの数を計数することで、前記複数のサンプル点のうち前記第１のサンプル点を支配する第２のサンプル点及び前記第１のサンプル点の数を算出する第３の処理と、
算出された前記数を前記複数のサンプル点の数で除することで、前記第１のサンプル点の歩留り率を算出し、前記データ格納部に格納する第４の処理と、
を、コンピュータに実行させるプログラム。
【０１１１】
（付記２）
前記複数のサンプル点に含まれる各サンプル点を前記第１のサンプル点に設定して、前記第３の処理及び前記第４の処理を実施させる第５の処理
をさらに前記コンピュータに実行させる付記１記載のプログラム。
【０１１２】
（付記３）
前記第３の処理は、
前記第１のサンプル点の各座標値以下の座標値に対応するノードを有し且つ当該ノードの全てが真の場合に１を表す葉ノードに達する第２の二分決定グラフを生成する処理と、
前記第２の二分決定グラフに含まれるノードに対応するノードを、前記二分決定グラフにおける根ノードから１を表す葉ノードに至るパスの数を計数する処理と、
を含む付記１又は２記載のプログラム。
【０１１３】
（付記４）
前記第３の処理において、
前記二分決定グラフの根ノードから前記葉ノードの方向にノードを順番に探索し、
前記第１のサンプル点の各座標以下の座標値に対応するノードではないと確認された場合及び前記二分決定グラフにおける０を表す葉ノードに到達した場合には探索を中止し、
前記二分決定グラフにおける１を表す葉ノードに到達した場合には、逆方向に前記根ノードまで探索の経路を戻ることで前記パスの数を計数する
付記１又は２記載のプログラム。
【０１１４】
（付記５）
前記逆方向に前記根ノードまで探索の経路を戻る処理において、当該経路上のノードにおいて、偽の枝方向のパス数と真の枝方向のパス数とを加算して、前記根ノードの方向の次のノードに移行する
付記４記載のプログラム。
【０１１５】
（付記６）
データ格納部に格納されている複数のサンプル点の複数種類の性能項目値を、当該複数種類の性能項目で張られる空間を分割することで得られる複数のメッシュ要素のうち該当するメッシュ要素の座標値に変換し、前記データ格納部に格納する第１の処理と、
前記データ格納部に格納されている前記複数のサンプル点の座標値の集合を表現する二分決定グラフを生成する第２の処理と、
前記データ格納部に格納されている前記複数のサンプル点に含まれる第１のサンプル点の各座標値以下の座標値に対応するノードを、前記二分決定グラフにおける１を表す葉ノードから辿って根ノードに至るパスの数を計数することで、前記複数のサンプル点のうち前記第１のサンプル点を支配する第２のサンプル点及び前記第１のサンプル点の数を算出する第３の処理と、
算出された前記数を前記複数のサンプル点の数で除することで、前記第１のサンプル点の歩留り率を算出し、前記データ格納部に格納する第４の処理と、
を、コンピュータが実行する情報処理方法。
【０１１６】
（付記７）
複数のサンプル点の複数種類の性能項目値を格納するデータ格納部と、
前記データ格納部に格納されている複数のサンプル点の複数種類の性能項目値を、当該複数種類の性能項目で張られる空間を分割することで得られる複数のメッシュ要素のうち該当するメッシュ要素の座標値に変換し、前記データ格納部に格納する変換部と、
前記データ格納部に格納されている前記複数のサンプル点の座標値の集合を表現する二分決定グラフを生成する生成部と、
前記データ格納部に格納されている前記複数のサンプル点に含まれる第１のサンプル点の各座標値以下の座標値に対応するノードを、前記二分決定グラフにおける１を表す葉ノードから辿って根ノードに至るパスの数を計数することで、前記複数のサンプル点のうち前記第１のサンプル点を支配する第２のサンプル点及び前記第１のサンプル点の数を算出し、算出された前記数を前記複数のサンプル点の数で除することで、前記第１のサンプル点の歩留り率を算出し、前記データ格納部に格納する歩留り算出部と、
を有する情報処理装置。
【符号の説明】
【０１１７】
１００  情報処理装置
１１０  データ格納部
１２０  処理部
１２１  変換部
１２２  生成部
１２３  歩留り算出部
【図１】
0005772381.tif 000004
【図２】
0005772381.tif 000005
【図３】
0005772381.tif 000006
【図４】
0005772381.tif 000007
【図５】
0005772381.tif 000008
【図６】
0005772381.tif 000009
【図７】
0005772381.tif 000010
【図８】
0005772381.tif 000011
【図９】
0005772381.tif 000012
【図１０】
0005772381.tif 000013
【図１１】
0005772381.tif 000014
【図１２】
0005772381.tif 000015
【図１３】
0005772381.tif 000016
【図１４】
0005772381.tif 000017
【図１５】
0005772381.tif 000018
【図１６】
0005772381.tif 000019
【図１７】
0005772381.tif 000020
【図１８】
0005772381.tif 000021
【図１９】
0005772381.tif 000022
【図２０】
0005772381.tif 000023
【図２１】
0005772381.tif 000024
【図２２】
0005772381.tif 000025
【図２３】
0005772381.tif 000026
【図２４】
0005772381.tif 000027
【図２５】
0005772381.tif 000028
【図２６】
0005772381.tif 000029
【図２７】
0005772381.tif 000030
【図２８】
0005772381.tif 000031
【図２９】
0005772381.tif 000032
【図３０】
0005772381.tif 000033
【図３１】
0005772381.tif 000034
【図３２】
0005772381.tif 000035
【図３３Ａ】
0005772381.tif 000036
【図３３Ｂ】
0005772381.tif 000037
【図３３Ｃ】
0005772381.tif 000038
【図３３Ｄ】
0005772381.tif 000039
【図３３Ｅ】
0005772381.tif 000040
【図３３Ｆ】
0005772381.tif 000041
【図３４】
0005772381.tif 000042
【図３５】
0005772381.tif 000043
【図３６】
0005772381.tif 000044
【図３７】
0005772381.tif 000045
【図３８】
0005772381.tif 000046
【図３９】
0005772381.tif 000047
【図４０】
0005772381.tif 000048
【図４１】
0005772381.tif 000049
【図４２】
0005772381.tif 000050
【図４３】
0005772381.tif 000051
【図４４】
0005772381.tif 000052
【図４５】
0005772381.tif 000053
【図４６】
0005772381.tif 000054
【図４７】
0005772381.tif 000055
【図４８】
0005772381.tif 000056
【図４９】
0005772381.tif 000057