(57)【特許請求の範囲】
【請求項１】
設計パラメタの組を複数入力して、所定の計算に基づいて複数の目的関数を計算し、その複数の目的関数に対して多目的最適化処理を実行することにより、最適な設計パラメタの組の決定を支援する設計支援装置において、
所定組数の前記設計パラメタのサンプルの組に対する前記複数の目的関数の組を計算し、該所定組数の設計パラメタのサンプルの組とそれに対応して計算された複数の目的関数の組とに基づいて、前記各目的関数を数式近似して複数の目的関数モデル式を生成する目的関数モデル式生成部と、
前記各設計パラメタの定義域が指定され、前記各目的関数値に対応する所定の設計変数の値が前記複数の目的関数モデル式によって計算される複数の目的関数値の最小値以下である又は該最小値より小さいという範囲制約が指定され、設計者が消去したい設計パラメタに対して限定記号が指定された入力論理式を生成する限定記号付論理式生成部と、
前記入力論理式中の前記所定の設計変数と限定記号が指定されていない設計パラメタとからなる設計変数空間を、（前記各目的関数モデル式群−前記所定の設計変数）に関して符号不変な領域である細胞領域に分割し、該細胞領域を前記所定の設計変数と前記限定記号が指定されていない設計パラメタとで表した論理式と、該細胞領域中から選択された標本点に対応する前記所定の設計変数の値と前記限定記号が指定されていない設計パラメタの値とからなる細胞情報をリスト１に記憶する細胞分割部と、
前記リスト１から前記限定記号が指定されていない設計パラメタの値が同じである標本点を含む細胞情報をリスト２に移動させた後、該リスト２から該細胞情報を１つずつ選択しながら、該選択した細胞情報に含まれる標本点を前記入力論理式に代入して計算することにより該標本点が該入力論理式を満たすか否かを評価し、該入力論理式が満たされる場合に、該選択した細胞情報と、該選択した細胞情報に含まれる標本点に対応する前記所定の設計変数の値以下の値の所定の設計変数を有する標本点が含まれる細胞情報を該リスト２からリスト３に移動させ、該入力論理式が満たされない場合に、該選択した細胞情報と、該選択した細胞情報に含まれる標本点に対応する前記所定の設計変数の値以上の値の所定の設計変数を有する標本点が含まれる細胞情報を該リスト２から削除する一連の処理を、該リスト２が空になるまで繰り返し実行し、該リスト２が空になる毎に該リスト１から該リスト２への移動処理を該リスト１が空になるまで繰り返し実行する第１の細胞処理部と、
を含み、
前記リスト３に最終的に得られた各細胞情報に含まれる各論理式を結合して得られる論理式を、前記入力論理式と等価であって、前記限定記号が付かない設計パラメタと前記所定の設計変数のみを含む論理式として出力し、該出力された論理式に基づいて前記限定記号が付かない設計パラメタと前記所定の設計変数との関係を提示しながら設計支援を行う、
ことを特徴とする多目的最適化設計支援装置。
【請求項２】
前記リスト２に含まれる細胞情報において、該細胞情報に含まれる標本点に対応する前記所定の設計変数の値が設計仕様として入力される該所定の設計変数の下限値よりも小さい場合に、該細胞情報を該リスト２から前記リスト３に移動させ、該細胞情報に含まれる標本点に対応する前記所定の設計変数の値が設計仕様として入力される該所定の設計変数の上限値よりも大きい場合に、該細胞情報を該リスト２から削除する第２の細胞処理部を更に含む、
ことを特徴とする請求項１に記載の多目的最適化設計支援装置。
【請求項３】
コンピュータを用いて、複数の設計パラメタの組と、所定の計算に基づいて計算された複数の目的関数とに対して多目的最適化処理を実行することにより、最適な設計パラメタの組の決定を支援する設計支援方法において、
前記コンピュータが有するプロセッサが、所定組数の前記設計パラメタのサンプルの組に対する前記複数の目的関数の組を計算し、該所定組数の設計パラメタのサンプルの組とそれに対応して計算された複数の目的関数の組とに基づいて、前記各目的関数を数式近似して複数の目的関数モデル式を生成し、
前記プロセッサが、前記各設計パラメタの定義域が指定され、前記各目的関数値に対応する所定の設計変数の値が前記複数の目的関数モデル式によって計算される複数の目的関数値の最小値以下である又は該最小値より小さいという範囲制約が指定され、設計者が消去したい設計パラメタに対して限定記号が指定された入力論理式を生成し、
前記プロセッサが、前記入力論理式中の前記所定の設計変数と限定記号が指定されていない設計パラメタとからなる設計変数空間を、（前記各目的関数モデル式群−前記所定の設計変数）に関して符号不変な領域である細胞領域に分割し、該細胞領域を前記所定の設計変数と前記限定記号が指定されていない設計パラメタとで表した論理式と、該細胞領域中から選択された標本点に対応する前記所定の設計変数の値と前記限定記号が指定されていない設計パラメタの値とからなる細胞情報を前記コンピュータが有するメモリ内のリスト１に記憶し、
前記プロセッサが、前記リスト１から前記限定記号が指定されていない設計パラメタの値が同じである標本点を含む細胞情報を前記メモリ内のリスト２に移動させた後、該リスト２から該細胞情報を１つずつ選択しながら、該選択した細胞情報に含まれる標本点を前記入力論理式に代入して計算することにより該標本点が該入力論理式を満たすか否かを評価し、該入力論理式が満たされる場合に、該選択した細胞情報と、該選択した細胞情報に含まれる標本点に対応する前記所定の設計変数の値以下の値の所定の設計変数を有する標本点が含まれる細胞情報を該リスト２から前記メモリ内のリスト３に移動させ、該入力論理式が満たされない場合に、該選択した細胞情報と、該選択した細胞情報に含まれる標本点に対応する前記所定の設計変数の値以上の値の所定の設計変数を有する標本点が含まれる細胞情報を該リスト２から削除する一連の処理を、該リスト２が空になるまで繰り返し実行し、該リスト２が空になる毎に該リスト１から該リスト２への移動処理を該リスト１が空になるまで繰り返し実行し、
前記プロセッサが、前記リスト３に最終的に得られた各細胞情報に含まれる各論理式を結合して得られる論理式を、前記入力論理式と等価であって、前記限定記号が付かない設計パラメタと前記所定の設計変数のみを含む論理式として出力し、該出力された論理式に基づいて前記限定記号が付かない設計パラメタと前記所定の設計変数との関係を提示しながら設計支援を行う、
ことを特徴とする多目的最適化設計支援方法。
【請求項４】
前記プロセッサが、前記リスト２に含まれる細胞情報において、該細胞情報に含まれる標本点に対応する前記所定の設計変数の値が設計仕様として入力される該所定の設計変数の下限値よりも小さい場合に、該細胞情報を該リスト２から前記リスト３に移動させ、該細胞情報に含まれる標本点に対応する前記所定の設計変数の値が設計仕様として入力される該所定の設計変数の上限値よりも大きい場合に、該細胞情報を該リスト２から削除する、
ことを特徴とする請求項３に記載の多目的最適化設計支援方法。
【請求項５】
設計パラメタの組を複数入力して、所定の計算に基づいて複数の目的関数を計算し、その複数の目的関数に対して多目的最適化処理を実行することにより、最適な設計パラメタの組の決定を支援する設計支援を実行するコンピュータに、
所定組数の前記設計パラメタのサンプルの組に対する前記複数の目的関数の組を計算し、該所定組数の設計パラメタのサンプルの組とそれに対応して計算された複数の目的関数の組とに基づいて、前記各目的関数を数式近似して複数の目的関数モデル式を生成し、
前記各設計パラメタの定義域が指定され、前記各目的関数値に対応する所定の設計変数の値が前記複数の目的関数モデル式によって計算される複数の目的関数値の最小値以下である又は該最小値より小さいという範囲制約が指定され、設計者が消去したい設計パラメタに対して限定記号が指定された入力論理式を生成し、
前記入力論理式中の前記所定の設計変数と限定記号が指定されていない設計パラメタとからなる設計変数空間を、（前記各目的関数モデル式群−前記所定の設計変数）に関して符号不変な領域である細胞領域に分割し、該細胞領域を前記所定の設計変数と前記限定記号が指定されていない設計パラメタとで表した論理式と、該細胞領域中から選択された標本点に対応する前記所定の設計変数の値と前記限定記号が指定されていない設計パラメタの値とからなる細胞情報をリスト１に記憶し、
前記リスト１から前記限定記号が指定されていない設計パラメタの値が同じである標本点を含む細胞情報をリスト２に移動させた後、該リスト２から該細胞情報を１つずつ選択しながら、該選択した細胞情報に含まれる標本点を前記入力論理式に代入して計算することにより該標本点が該入力論理式を満たすか否かを評価し、該入力論理式が満たされる場合に、該選択した細胞情報と、該選択した細胞情報に含まれる標本点に対応する前記所定の設計変数の値以下の値の所定の設計変数を有する標本点が含まれる細胞情報を該リスト２からリスト３に移動させ、該入力論理式が満たされない場合に、該選択した細胞情報と、該選択した細胞情報に含まれる標本点に対応する前記所定の設計変数の値以上の値の所定の設計変数を有する標本点が含まれる細胞情報を該リスト２から削除する一連の処理を、該リスト２が空になるまで繰り返し実行し、該リスト２が空になる毎に該リスト１から該リスト２への移動処理を該リスト１が空になるまで繰り返し実行し、
前記リスト３に最終的に得られた各細胞情報に含まれる各論理式を結合して得られる論理式を、前記入力論理式と等価であって、前記限定記号が付かない設計パラメタと前記所定の設計変数のみを含む論理式として出力し、該出力された論理式に基づいて前記限定記号が付かない設計パラメタと前記所定の設計変数との関係を提示しながら設計支援を行う、
処理を実行させるためのプログラム。
【請求項６】
前記リスト２に含まれる細胞情報において、該細胞情報に含まれる標本点に対応する前記所定の設計変数の値が設計仕様として入力される該所定の設計変数の下限値よりも小さい場合に、該細胞情報を該リスト２から前記リスト３に移動させ、該細胞情報に含まれる標本点に対応する前記所定の設計変数の値が設計仕様として入力される該所定の設計変数の上限値よりも大きい場合に、該細胞情報を該リスト２から削除する、
処理を更に実行させるための請求項５に記載のプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、設計に用いられる多目的最適化設計支援技術に関する。
【背景技術】
【０００２】
ものづくりにおける設計段階では、設計条件を設計パラメタの関数（目的関数）として表現し、その目的関数の出力値（＝目的関数値）が所望の値になるように設計パラメタを設定（最適化）することが必要となる。その際、設計者はベースとなる形状を決めた後で各設計パラメタの振り幅を設定し、設計パラメタ空間内で最適化を行う。
【０００３】
しかし設計パラメタの数が多い場合、その空間内をくまなく探索しようとすると組合せ爆発が起こり、実時間内では最適化の計算が不可能となる。
今、ものづくりの一例として、ＳＲＡＭ（スタティクランダムアクセスメモリ）の設計を例として考える。
【０００４】
ＳＲＡＭの設計における設計目標は、「外乱に対する動作安定性の余裕度」と「書込みの安定性の余裕度」を共に確保することである。前者の性能は、スタティックノイズマージン（Static Noise Margin：以降、SNMと略記する）と呼ばれる。SNMは、ＳＲＡＭの動作に対して許容される雑音振幅の最大値として定義され、値が大きいほど安定性が高いことを示す。後者の性能は、ライトマージン（Write Margin：以降、WMと略記する）及びホールドノイズマージン（Hold Noise Margin：以降、HNMと略記する）と呼ばれる。WM及びHNMも、値が大きいほど安定性が高いことを示す。
【０００５】
SNMとWM又はWMとHNMは一般に、互いに相殺する関係を有しており、一方の値を高くしようとすると他方の値が低くなってしまうという特性を有している。
そこで、ＳＲＡＭ設計においては、下記に示されるようなＳＲＡＭの設計パラメタに対して、SNMとWMという２つの物理量、或いは、SNMとWMとHNMという３つの物理量を同時に最大化するような多目的最適化が必要となる。
【０００６】
＜ＳＲＡＭの設計パラメタ＞
・セル電圧、
・Loadゲート長
・Driverゲート長
・Transferゲート長
・Load幅
・Driver幅
・Transfer幅
・Wl（ワードライン電位）制御変数
・LoadのVth（Vth変化量）
・DriverのVth（Vth変化量）
・TransferのVth（Vth変化量）
【０００７】
例えば、SNMとWMを例に考えると、一般的な傾向として、例えば図８に示されるＳＲＡＭ形状８０１において、L1、L2、W1、W2等で示されるサイズ（上記の例でいうゲート長や幅）が大きいほうが、また、セル電圧等の電圧値が高いほうが、ＳＲＡＭの歩留まりが高い、即ちSNM及びWM共に大きな値となる。
【０００８】
このとき、SNMとWMに関して同時に歩留まりを最大化するという最適化問題は、SNMを表現する目的関数値とWMを表現する目的関数値を同時に最大化するという問題になる。即ち、SNMとWMに対応する歩留まりの同時最適化問題は、
歩留まり＝min（SNMの目的関数，WMの目的関数）      ・・・（１）
を計算し、その最大値を見つけるという問題になる。
【０００９】
ここで、SNM及びWM等に関する目的関数は通常、所定の複数種類の設計パラメータから構成される設計パラメタ群を用いて、シミュレータにより数値計算することができる。従って一般には、上記（１）式等を多くのサンプル組の設計パラメータ組に対して数値計算し、その結果得られるSNMの目的関数値とWM目的関数値を同時に最大にするような設計パラメタ群の組を認識することにより、設計の目的を達成することができる。
【００１０】
しかし、ＳＲＡＭにおけるSNM及びWMのような目的関数は、一般に、多種類の設計パラメータから構成される設計パラメタ群を入力とする複雑な関数計算となる。従って、各設計パラメータの値を例えば０から１までの間で変化させながら（１）式を数値計算した場合、目的関数値を同時に最大にする最適な設計パラメータ組を算出するためには、膨大な計算量が必要となり、実質的には実時間内で最適化を行うことが困難である。
【００１１】
そこで、ＳＲＡＭなどのものづくり設計における上述の多目的最適化問題を効率的に解くための従来技術として、以下に示される目的関数の数式モデル化による解法が知られている。
【００１２】
まず、複数種類からなる設計パラメータ群のサンプル組が複数組用意される。このサンプル組数は、それほど多くは必要とされない。
次に、設計シミュレータにおいて、上記複数のサンプル組に対するシミュレータ計算が実行され、各サンプル組に対応するSNMの目的関数及びWMの目的関数が数値計算される。１サンプルの設計パラメータ群に対する各目的関数の数値計算には例えば2〜3分程度の時間がかかるが、サンプル組数がそれほど多くはないので、この計算処理は困難な処理ではない。
【００１３】
次に、SNMの目的関数値及びWMの目的関数値と設計パラメータ群とからなる対の複数のサンプル組に対して、例えば最小２乗法による近似処理が実行される。この結果、SNMの目的関数及びWMの目的関数をそれぞれ設計パラメータを含む多項式で数式近似した、次式で例示されるような各目的関数モデル式が算出される。
f1=-3.70880619227755703-1.815535443549214242e-2*x1+0.362756928799239723e-1*x2+0.529879430721035828e-1*x3-0.186187407180227748e-1*x4+0.378882808207316458e-1*x5+0.577218911880007530e-2*x6+15.4475497344388622*x7+7.61316609791377275*x8+11.1015094199909559*x9+11.1015094199909399*x10-1.84551068765900172*x11
・・・（２）
一般的には、SNMとWMの各目的関数モデル式は、次式のように表現できる。次式において、f1及びf2は、それぞれ例えば設計パラメータx1,...,x11に関する多項式の関数である。
SNMの目的関数モデル式=f1(x1,...,x11)
WMの目的関数モデル式=f2(x1,...,x11)
・・・（３）
【００１４】
この従来技術では、少ないサンプル組数の設計パラメータ群を使って、実用的な近似精度を有する各目的関数モデル式を得ることができる。このようなモデル化により、わずかな数の設計パラメータ群のサンプル値を選択するだけで、サンプル値以外の目的関数部分を滑らかに近似することができ、実用上十分な精度を有する目的関数モデル式を得ることができる。
【００１５】
次に、このようにして算出された目的関数モデル式に、このモデル式に含まれる設計パラメータに対して制約条件と限量記号（又は限定記号）を付加して得られる論理式が生成される。
【００１６】
例えば動作例１として、設計者が、（３）式で示される目的関数モデル式f1及びf2を用いて、歩留まりの同時最大値を知りたいとする。
この場合、前述の（１）式及び（３）式に基づいて、制約条件が、下記のように設定される。
SNMの目的関数モデル式=f1(x1,...,x11)
WMの目的関数モデル式=f2(x1,...,x11)
歩留まり＝min（f1,f2）
0 < xi < 1     (i=1,2,...,11)
上述の制約条件を論理式で表現すると、次式のようになる。
ex({x1,x2,x3,x4,x5,x6,x7,x8,x9,x10,x11}, 
(0 < x1 < 1)  and  (0 < x2 < 1)  and (0 < x3 < 1)  and (0 < x4 < 1) and
(0 < x5 < 1)  and  (0 < x6 < 1)  and (0 < x7 < 1)  and (0 < x8 < 1) and
(0 < x9 < 1)  and  (0 < x10 < 1)  and (0 < x11 < 1)  and
f1 ≧ z and f2 ≧ z);
・・・（４）
ここで、exはexistsの意味であり、設計パラメータ（＝設計変数）x1〜x11 に、存在限定記号が付されていることを示している。即ち、上記（４）式には、
∃x1, ∃x2, ∃x3, ∃x4, ∃x5, ∃x6, ∃x7, ∃x8, ∃x9, ∃x10, ∃x11
が設定されている。また、（４）式では、各設計パラメータxiが、０より大きく１より小さい値をとり得ることを示している。更に（４）式のf1とf2は、（３）式のf1とf2に等価な目的関数モデル式であり、x1〜x11 に関する多項式表現となっている。zは歩留まりを表す設計変数である。
【００１７】
今、例えば上記（４）式の論理式から、下記非特許文献１及び２等として公知なＱＥ法（Quantifier Elimination：限定記号消去法）により、限定記号が付されている設計変数（＝設計パラメータ）x1〜x11 を消去する処理が実行される。この結果、設計変数zの範囲のみを示す論理式を得ることができ、設計者は設計変数zの最大値を容易に推測することができる。
【００１８】
次に、従来技術の動作例２として、設計者が、（３）式で示される目的関数モデル式f1及びf2を用いて、歩留まりと特定の設計パラメータx1との関係を知りたいとする。
この場合、次式のような論理式が設定される。
ex({x2,x3,x4,x5,x6,x7,x8,x9,x10,x11}, 
(0 < x1 < 1)  and  (0 < x2 < 1)  and (0 < x3 < 1)  and (0 < x4 < 1) and
(0 < x5 < 1)  and  (0 < x6 < 1)  and (0 < x7 < 1)  and (0 < x8 < 1) and
(0 < x9 < 1)  and  (0 < x10 < 1)  and (0 < x11 < 1)  and   f1 ≧ z and f2 ≧ z);
・・・（５）
ここでは、設計パラメータx1においてのみ、限定記号が設定されていない。
【００１９】
この場合、上記（５）式の論理式から、ＱＥ法により、限定記号が付されている設計変数（＝設計パラメータ）x2〜x11 を消去する処理が実行される。この結果、設計パラメータx1と歩留まりを表す設計変数zのみからなる論理式を得ることができる。
【００２０】
以上のようにして、特定の設計変数（設計パラメタ）のみを含む論理式が得られた後、例えば上述の動作例２の場合、得られた論理式内に残っている設計パラメタ、例えばx1に関するサンプル点群（0 < x1 < 1）が生成される。そして、各サンプル点について、上述の論理式が計算されることにより、設計変数zが取り得る値、即ち設計変数zの可能領域が算出される。そして、上記サンプル点とそれに対応するzの値とから、x1とzをそれぞれ軸とする２次元座標上にプロットが行われることにより、zの可能領域がディスプレイ等に描画される。
【００２１】
このようにして、設計者は、設計パラメータx1と歩留まりに対応する設計変数zの関係を容易に推測することができる。
論理式において限定記号が付されている設計変数（＝設計パラメータ）をＱＥ法により消去する具体的な計算方法として、非特許文献２に記載のＣＡＤ（Cylindrical Algebraic Decomposition）と呼ばれる手法が知られている。
【００２２】
今、前述したSNMとWMに関する多目的最適化問題の論理式を、次式に示されるように一般化する。
ex({x1,...,xt}, 
(0 < x1 < 1)  and  ...  and (0 < xt < 1)  and 
(0 < xt+1 < 1)  and  ...  and (0 < xk < 1)  and
f1 ≧ z and f2 ≧ z);
SNMの目的関数モデル式=f1(x1,...,xt,xt+1,...,xk)
WMの目的関数モデル式=f2(x1,...,xt,xt+1,...,xk)
・・・（６）
この論理式においては、設計パラメタx1からxtまでに限定記号が付き、xt+1からxkまでは限定記号が付かない場合が示されている。
【００２３】
この前提のもとでの多目的最適化問題は、入力された論理式から限定記号が付いた設計パラメタx1〜xtが消去されることにより限定記号が付かない設計パラメタxt+1〜xkと歩留まりを表す設計変数ｚのみを含む論理式を算出し、その論理式を使って、設計変数ｚを同時に最大にするような、限定記号が付かない設計パラメタxt+1〜xkの組を求めることである。今、ＱＥ／ＣＡＤ法によって、入力された論理式から限定記号が付いている設計パラメタx1〜xtが消去されたとする。その後、図９に示されるように、設計パラメタxt+1〜xkのうちの１つを横軸にとり、設計変数ｚを縦軸にとると、目的関数f1とf2が図９の座標平面に射影されることにより、目的関数に関する何本かの多項式曲線が得られる。これらの曲線の中で、各設計パラメタ値毎にｚに関して最小値をとる曲線が選択されながらｚの値が最大となる図９の矢印で示される点に対応する設計パラメタxt+1〜xkの値の組が最適解であると、設計者は認識できる。この最適解は、それに対応する設計パラメタxt+1〜xkの値の組が選択されたときに、設計仕様として要求される歩留まりの精度範囲の中で、SNMとWMを同時に最大にすることができることを示している。なお、図９において、黒塗りされた部分は、上述の最適解よりは歩留まりは悪くなるが、設計パラメタxt+1〜xkの値の組として選択することが可能な領域を示している。この領域は、可能領域と呼ばれる。逆に、可能領域よりも上の黒塗りされていない領域は、設計パラメタxt+1〜xkの値の組として選択することができない領域である。
【００２４】
この場合、ＱＥ／ＣＡＤ法では、以下のような処理が実行される。
まず、設計変数ｚと限定記号が付かない設計パラメタxt+1〜xkからなる入力された論理式によって示される設計変数空間が、f1-z、f2-zに関して符号不変な領域（これを「細胞」と呼ぶ）に分割される。限定記号が付かない１つの設計パラメタと歩留まりを表す設計変数ｚとで構成される２次元平面上で見ると、例えば図１０の○（丸印）で示される各領域（細胞）が、f1-z、f2-zに関する符号不変な領域である。分割された細胞は、設計パラメタxt+1〜xkの何れか１つ以上と設計変数ｚを用いてその細胞の範囲を不等式等を含む論理式で表現される。１つの細胞内では、その範囲内でどの設計パラメタxt+1〜xkの各値と設計変数ｚの値の組をとっても、各目的関数モデル式の符号は変化しないことが保証される。これらの細胞分割が、限定記号が付かない設計パラメタxt+1〜xkと設計変数ｚの全ての組合せについて行われる。分割された細胞の全体の数はおおよそ、各設計パラメタに対応する各分割数を順次乗算した数となる。
【００２５】
次に、このようにして分割された細胞毎に、その細胞を代表する設計パラメタxt+1〜xkと設計変数ｚの値（これを「標本点」と呼ぶ）が決定され、これらの値が限定記号が付けられた設計パラメタx1〜xtを含む（６）式に代入されることにより、その標本点が（６）式を満たすか否かが判定される。そして、（６）式が満たされるならば、その細胞に対応する限定記号が付かない設計パラメタxt+1〜xkの何れか１つ以上と設計変数ｚを用いた論理式が記憶される。
【００２６】
上述の判定処理が全ての細胞について実行された後、記憶された論理式を結合して得ら
れる論理式が、入力された論理式と等価であって、限定記号が付かない設計パラメタxt+1〜xkと設計変数ｚのみを含む論理式として算出される。
【先行技術文献】
【非特許文献】
【００２７】
【非特許文献１】「計算実代数幾何入門：ＣＡＤとＱＥの概要（数学セミナー、１１号  ２００７  ６４−７０頁（穴井宏和、横山和弘共著））
【非特許文献２】Partial Cylindrical Algebraic Decomposition for Quantifier Elimination, George E. Collins and Hoon Hong, Journal of Symbolic Computation, Volume 12, Number 3, 1991, pp.299-328.
【発明の概要】
【発明が解決しようとする課題】
【００２８】
上述の従来技術において、設計対象がＳＲＡＭである場合、入力される論理式には、目的関数モデル式のほかに、所定の設計パラメータ組からサイズ（面積）、Vth、リーク電流、電源電圧等の設計量を計算するための関数等も含めることができる。
【００２９】
ここで、サイズsizeは例えば、次式の関数で表現される。
size＝(1 + 2 * x4 + 3 * x5) * (6 + x2 + x3)      ・・・（７）
ここで、x2、x3、x4、x5等の設計パラメータは、図８に示されるサイズを示す幅Ｗ１，Ｗ２，・・・や長さＬ１，Ｌ２・・・等に対応する。
【００３０】
また、Vth は例えば、多項式による関数f3を用いて、次式で表現される。
Vth = f3(x1,x4,x7)      ・・・（８）
【００３１】
更に、リーク電流Leakは例えば、指数関数f4を用いて、次式で表現される。
Leak = f4(x1,x4,x7)      ・・・（９）
上記（８）式及び（９）式において、x1、x4、x7等は、所定の設計パラメータである。
【００３２】
（７）式〜（９）式は、設計者が、単純に歩留まりと設計パラメータとの関係だけでなく、歩留まりとサイズの関係、歩留まりとサイズとVth の関係、或いは、歩留まりとサイズとリーク電流の関係も知りたいというような場合に導入される。
【００３３】
今、動作例３として、設計者が、歩留まりとサイズの関係を知りたい場合、前述の（１）式、（６）式、及び（７）式に基づいて、制約条件が、下記のように設定される。
SNMの目的関数モデル式=f1(x1,...,x5,...,xt,xt+1,...,xk)
WMの目的関数モデル式=f2(x1,...,x5,...,xt,xt+1,...,xk)
歩留まり＝min（f1，f2）
0 < xi < 1     (i=1,2,...,xk)
size=(6 + x2 + x3) * (1 + 2 * x4 + 3 * x5)
上述の制約条件を論理式で表現すると、次式のようになる。
ex({x1,x2,x3,x4,x5,...,xt}, 
(0 < x1 < 1)  and  (0 < x2 < 1)  and (0 < x3 < 1)  and (0 < x4 < 1) and
(0 < x5 < 1)  and  ...  and (0 < xt < 1)  and 
(0 < xt+1 < 1)  and  ...  and (0 < xk < 1)  and
(1 + 2 * x4 + 3 * x5) * (6 + x2 + x3) = size and
f1 ≧ z and f2 ≧ z);
・・・（１０）
【００３４】
上述の論理式に対して、ＱＥ／ＣＡＤ法により、限定記号が付されている設計変数（設計パラメータ）x1〜xt を消去する処理を実行しようとした場合を考える。この場合、（１０）式においてsizeを示す関数は、設計パラメータに関する２次式となっている。前述したように、ＱＥ／ＣＡＤ法では、細胞分割をした上で、各細胞について、その細胞を代表する設計パラメタxt+1〜xkと歩留まりを表す設計変数ｚの値が（１０）式を満たすか否かを判定する処理が繰り返し実行される。ここで、前述したように、細胞の全体の分割数はおおよそ、各設計パラメタxt+1〜xkに対応する各細胞分割数を順次乗算して得られる数である。図１０に示されるように、１つの設計パラメタに対応する細胞の数だけでも数十〜百近くになる。従って、限定記号が付かない設計パラメタの種類がたとえ３種類程度であったとしても、全体の細胞数は数十万から百万前後になる。そして、ＱＥ／ＣＡＤ法では、これらの全ての細胞について、入力された論理式、即ち例えば（１０）式を計算して評価する必要がある。
【００３５】
このため、入力された論理式に２次式等が含まれるだけで、ＱＥ／ＣＡＤ法における計算量が爆発的に増加してしまい、ＱＥ／ＣＡＤの計算処理が実時間内に終了しなくなる可能性があるという問題点を有していた。
【００３６】
また、２次式等が含まれない（６）式に示されるような通常の論理式であっても、ＱＥ／ＣＡＤの計算処理時間は設計作業の効率に大きな影響を与えるため、その高速化が望まれていた。
【００３７】
そこで、本発明の１つの側面では、ＱＥ／ＣＡＤの計算量を削減することを目的とする。
【課題を解決するための手段】
【００３８】
態様の一例では、設計パラメタの組を複数入力して、所定の計算に基づいて複数の目的関数を計算し、その複数の目的関数に対して多目的最適化処理を実行することにより、最適な設計パラメタの組の決定を支援する設計支援装置として実現され、以下の構成を有する。
【００３９】
目的関数モデル式生成部は、所定組数の設計パラメタのサンプルの組に対する複数の目的関数の組を計算し、該所定組数の設計パラメタのサンプルの組とそれに対応して計算された複数の目的関数の組とに基づいて、各目的関数を数式近似して複数の目的関数モデル式を生成する。
【００４０】
限定記号付論理式生成部は、各設計パラメタの定義域が指定され、各目的関数値に対応する所定の設計変数の値が複数の目的関数モデル式によって計算される複数の目的関数値の最小値以下である又はその最小値より小さいという範囲制約が指定され、設計者が消去したい設計パラメタに対して限定記号が指定された入力論理式を生成する。
【００４１】
細胞分割部は、入力論理式中の所定の設計変数と限定記号が指定されていない設計パラメタとからなる設計変数空間を、（各目的関数モデル式群−所定の設計変数）に関して符号不変な領域である細胞領域に分割し、その細胞領域を所定の設計変数と限定記号が指定されていない設計パラメタとで表した論理式と、その細胞領域中から選択された標本点に対応する所定の設計変数の値と限定記号が指定されていない設計パラメタの各値とからなる細胞情報をリスト１に記憶する。
【００４２】
第１の細胞処理部は、リスト１から限定記号が指定されていない設計パラメタの値が同じである標本点を含む細胞情報をリスト２に移動させた後、リスト２から細胞情報を１つずつ選択しながら、選択した細胞情報に含まれる標本点を入力論理式に代入して計算することによりその標本点が入力論理式を満たすか否かを評価し、入力論理式が満たされる場合に、選択した細胞情報と、選択した細胞情報に含まれる標本点に対応する所定の設計変数の値以下の値の所定の設計変数を有する標本点が含まれる細胞情報をリスト２からリスト３に移動させ、入力論理式が満たされない場合に、選択した細胞情報と、選択した細胞情報に含まれる標本点に対応する所定の設計変数の値以上の値の所定の設計変数を有する標本点が含まれる細胞情報をリスト２から削除する一連の処理を、リスト２が空になるまで繰り返し実行し、リスト２が空になる毎にリスト１からリスト２への移動処理をリスト１が空になるまで繰り返し実行する。
【００４３】
そして、リスト３に最終的に得られた各細胞情報に含まれる各論理式を結合して得られる論理式が、入力論理式と等価であって、限定記号が付かない設計パラメタと所定の設計変数のみを含む論理式として出力され、その出力された論理式に基づいて限定記号が付かない設計パラメタと所定の設計変数との関係が提示されながら設計支援が行われる。
【発明の効果】
【００４４】
同じ設計パラメタの値毎に、或る細胞情報に含まれる標本点について入力論理式が満たされるならば、その標本点での歩留まり等を表す所定変数の値以下の値を所定変数の値として有する他の標本点が含まれる細胞情報については、入力論理式を評価する必要がなくなる。また、同じ設計パラメタの値毎に、或る細胞情報に含まれる標本点について入力論理式が満たされないならば、その標本点での所定変数の値以上の値を所定変数の値として有する他の標本点が含まれる細胞情報についても、入力論理式を評価する必要がなくなる。この結果、ＱＥ／ＣＡＤの計算処理において、その計算量の大幅な削減が実現される。
【図面の簡単な説明】
【００４５】
【図１】ＳＲＡＭ形状パラメータの多目的最適化設計支援装置の実施形態の構成図である。
【図２】本実施形態の制御動作を示す動作フローチャートである。
【図３】細胞選択・評価処理を示す動作フローチャートである。
【図４】本実施形態の動作説明図（その１）である。
【図５】本実施形態の動作説明図（その２）である。
【図６】本実施形態の動作説明図（その３）である。
【図７】本実施形態を実現可能なハードウェアシステムの構成図である。
【図８】ＳＲＡＭにおける設計パラメタの説明図である。
【図９】ＱＥ／ＣＡＤ法における限定記号が付かない設計パラメタと設計変数ｚとの関係を示す図である。
【図１０】ＱＥ／ＣＡＤ法における細胞分割の説明図である。
【発明を実施するための形態】
【００４６】
以下、本発明を実施するための形態について図面を参照しながら詳細に説明する。
まず、本実施形態の基本的な考え方について説明する。
本実施形態では、入力される論理式として、設計パラメタの値又は論理式とその範囲が与えられ、目的関数モデル式が与えられたときに、入力される論理式に関して次のような制約条件が規定される。
【００４７】
第１の制約条件として、論理式中の所定変数（例えば歩留まりを表す設計変数ｚ）の値が、複数の目的関数モデル式によって計算される複数の目的関数値の最小値よりも小さい（又はそれ以下である）という範囲制約が設定される。この第１の制約条件は、例えばＳＲＡＭ設計においては、歩留まりがSNMとWM（及びHNM）の中で最も悪い値で決定され、かつSNMとWM（とHNM）に関する目的関数値を同時に最大化するような歩留まりを提供するという設計要求に、良く合致する制約条件である。ＳＲＡＭ設計に限らず、このような制約条件が要求される設計事案は多い。
【００４８】
例えば、SNMとWMに関する多目的最適化問題の論理式において、次式のような制約条件が付加される。
z ≦ f1 かつ z ≦ f2      ・・・（１１）
この例では、設計変数ｚの値（値域）が、f1及びf2のうちの最小値以下であるという範囲制約が設定されている。
【００４９】
（１１）式の例では、例えば前述した図９において、限定記号が付いていない設計パラメタのうちの１つを横軸にとり、歩留まりを表す設計変数ｚを縦軸にとったとする。このときに、目的関数モデル式を座標平面に射影して得られる何本かの曲線のうちｚの最小値をとる曲線の下側の黒塗りされた領域が、設計変数として取り得る領域、即ち可能領域となる。そして、本実施形態における多目的最適化問題は、図９の矢印で示される点に対応する設計パラメタの値の組を見つけることである。この点に対応する設計パラメタxt+1〜xkの値の組が、設計仕様として要求される歩留まりの精度範囲の中で、SNMとWMを同時に最大化できる最適解である。
【００５０】
上述した第１の制約条件を考慮して、入力される論理式は、例えば次のように定義される。
ex({x1,...,xt}, 
(0 < x1 < 1)  and  ...  and (0 < xt < 1)  and 
(0 < xt+1 < 1)  and  ...  and (0 < xk < 1)  and
f1 ≧ z and f2 ≧ z);
SNMの目的関数モデル式=f1(x1,...,xt,xt+1,...,xk)
WMの目的関数モデル式=f2(x1,...,xt,xt+1,...,xk)
・・・（１２）
【００５１】
これは、前述した（６）式と同じ形態である。この論理式においては、設計パラメタx1からxtは、消去したい設計変数として限定記号が付けられ、xt+1からxkまでは残したい設計変数として限定記号が付けられない。また、各設計パラメータxi（１≦ｉ≦ｋ）は０より大きく１より小さい値の定義域が制約条件として付加される。また、f1とf2は、SNMとWMの各目的関数を数式モデル化することによって得られる目的関数モデル式であり、x1〜x11 に関する多項式表現となっている。なお、前述した（１０）式に示されるように、入力される論理式に、（７）式〜（９）式で示されるような、目的関数モデル式のほかに、所定の設計パラメータ組からサイズ、Vth、リーク電流、電源電圧等の設計量に対応する関数等を含めてもよい。
【００５２】
入力される論理式に上述のような制約条件が付加された上で、入力された論理式に対してＱＥ／ＣＡＤ法が適用される。
まず、前述した図１０に示されるようにして、歩留まりを表す設計変数ｚと限定記号が付かない設計パラメタxt+1〜xkとからなる設計変数空間が、f1-z、f2-zに関して符号不変な領域である細胞に分割される。限定記号が付かない１つの設計パラメタとｚとで構成される２次元平面上で見ると、例えば図１０の○（丸印）で示される各領域（細胞）が、f1-z、f2-zに関する符号不変な領域である。分割された細胞は、設計パラメタxt+1〜xkの何れか１つ以上と設計変数ｚを用いてその細胞の範囲を不等式等を含む論理式で表現される。１つの細胞内では、その範囲内でどの設計パラメタxt+1〜xkと設計変数ｚの値の組をとっても、各目的関数モデル式の符号は変化しないことが保証される。これらの細胞分割が、限定記号が付かない設計パラメタxt+1〜xkと設計変数ｚの全ての組合せについて行われる。次に、分割された細胞毎に、その細胞中の任意の１点を標本点として、限定記号が付いていない設計パラメタxt+1〜xkの各値と設計変数ｚの値が選択される。細胞中の要素はすべて同じ符号をもつので、或る細胞中の任意の1点を標本点として選択して評価すればその細胞全体を評価したことになる。各細胞を表現する論理式と各細胞の標本点に対応する設計パラメタxt+1〜xkの各値と設計変数ｚの値が、各細胞情報としてリスト１に記憶される。
【００５３】
次に、例えば図４の４０１又は４０２などとして示されるように、設計パラメタxt+1〜xkの各値が１組固定され、変数ｚの値のみが変化する各標本点に対応する各細胞情報がリスト２に取り出される。次に、リスト２の中から１つの細胞情報、例えば設計変数ｚについてその範囲の中間値付近を設計変数ｚの値として有する標本点を含む細胞情報が任意に１個選択される。そして、その細胞情報の標本点に対応する設計パラメタxt+1〜xkの各値と設計変数ｚの値が入力論理式（例えば（１２）式）に代入されることにより、入力論理式が満たされるか否かが評価される。そして、入力論理式が満たされるならば、その標本点が含まれる細胞情報が、リスト２からリスト３に移動させられる。
【００５４】
このとき、入力論理式が満たされる標本点は、例えば図４でいえば黒丸●の点に相当し、設計変数ｚの値がf1及びf2のうちの最小値以下である点になる。従って、前述の第１の制約条件のもとでは、或る標本点が入力論理式を満たせば、その標本点での設計変数ｚの値以下の値を設計変数ｚの値として有し、その標本点と同じ設計パラメタxt+1〜xkの各値を有するリスト２中の他の標本点は全て入力論理式を満たすと判定できる。即ち、これらの他の標本点については入力された論理式を評価する必要はなくなる。従って、これらの他の標本点がそれぞれ含まれる各細胞情報が、リスト２からリスト３に移動させられる。
【００５５】
逆に、入力論理式が満たされない標本点は、例えば図４でいえば白丸○の点に相当し、設計変数ｚの値がf1及びf2のうちの最小値よりも大きい点になる。従って、前述した第１の制約条件を前提とすれば、選択された標本点が入力論理式を満たさなければ、その標本点における設計変数ｚの値以上の値を設計変数ｚの値として有し、その標本点と同じ設計パラメタxt+1〜xkの各値を有する他の標本点は全て入力論理式を満たさないと判定できる。即ち、これらの他の標本点についても入力論理式を評価する必要はなくなる。従って、これらの他の標本点と選択された標本点がそれぞれ含まれる各細胞情報が、リスト３としては記憶されずに、リスト２から削除される。
【００５６】
以上の２つの評価を行いながら、リスト２中に残っている各細胞情報の同じ設計パラメタxt+1〜xkの各値を有する標本点について、設計変数ｚの値をf1及びf2のうちの最小値に近づくように追い込んでゆくことによって、リスト３として、現在選択されている設計パラメタxt+1〜xkの各値の組に関して、入力論理式を満たす細胞情報の集合が得られる。
【００５７】
そして、設計パラメタxt+1〜xkの各値の組が順次変更されながらリスト１中の全ての細胞情報について、上述の処理が繰り返し実行される。
このように、同じ設計パラメタxt+1〜xkの各値の組毎に、或る細胞情報に含まれる標本点について入力論理式が満たされるならば、その標本点での設計変数ｚの値以下の値を設計変数ｚの値として有する他の標本点が含まれる細胞情報については、入力論理式を評価する必要がなくなる。また、同じ設計パラメタxt+1〜xkの各値の組毎に、或る細胞情報に含まれる標本点について入力論理式が満たされないならば、その標本点での設計変数ｚの値以上の値を設計変数ｚの値として有する他の標本点が含まれる細胞情報についても、入力論理式を評価する必要がなくなる。即ち、前述の第１の制約条件が設定されることにより、ＱＥ／ＣＡＤの計算処理において、その計算量の大幅な削減が実現される。
【００５８】
次に、本実施形態では、第２の制約条件として、例えば図５の５０１として示されるように、歩留まりを表す設計変数ｚの値（値域）に、範囲制限が設定される。言い換えれば、歩留まりが一定の精度範囲に入ることが要求される。「SNMとしてはこの範囲の精度が必要で、WMとしてはこの範囲の精度が必要である」という如くである。例えばＳＲＡＭ設計においては、歩留まりが一定の精度範囲に入ることは、一般的に要求される設計仕様である。従って、設計仕様として、第２の制約条件を課すことは、妥当である。ＳＲＡＭ設計に限らず、目的関数値である値域に範囲制約が設定される設計事案は多い。
【００５９】
上述の第２の制約条件を考慮して、本実施形態では、次のような処理が実行される。即ち、前述のリスト１中の各細胞情報において、歩留まりを表す設計変数ｚの値の精度範囲が予め設計仕様として与えられた例えば図６の５０１として示される精度範囲の上限値より大きい標本点が含まれる細胞情報は、入力論理式の評価をせずに除外してしまって問題ない。例えば、図６において、６０５と６０６によって囲まれた矩形領域に含まれる細胞が該当する。この範囲は、歩留まりが高すぎるため、SNMやWMそれぞれがある設計パラメータの組で満たすことがあっても、ｚがその値を満たすことは稀である。もし制約条件１を満たすものがあるならばより良い設計仕様が存在することを示唆している。逆に、前述のリスト１中の各細胞情報において、設計変数ｚの精度範囲が予め設計仕様として与えられた例えば図６の５０１として示される精度範囲の下限値より小さい標本点が含まれる細胞情報は、歩留まりが低すぎるため設計パラメタの組として選択の対象にならない。このため、このような細胞情報は、入力論理式の評価をせずに、前述のリスト３に加えてしまって問題ない。例えば、図６において、６０１と６０２によって囲まれた黒塗りされた矩形領域、又は６０３と６０４によって囲まれた黒塗りされた矩形領域に含まれる細胞が該当する。
【００６０】
このようにして第２の制約条件が設定されることによっても、ＱＥ／ＣＡＤの計算処理において、その計算量の大幅な削減が実現される。
以上のようにして、最終的にリスト３として、入力論理式を満たす細胞情報の集合が得られる。前述したように、各細胞情報は、限定記号が付かない設計パラメタxt+1〜xkの何れか１つ以上と設計変数ｚを用いた不等式等を含む論理式を含む。従って、リスト３に含まれる全ての細胞情報に含まれる論理式が結合されて出力されることにより、入力された論理式と等価であって、限定記号が付かない設計パラメタxt+1〜xkと設計変数ｚのみを含む論理式を得ることができる。
【００６１】
以上の基本的な考え方に基づく本実施形態の具体的な構成及び動作を以下に説明する。
図１は、ＳＲＡＭ形状パラメータの多目的最適化設計支援装置の実施形態の構成図でありる。また、図２及び図３は、本実施形態の制御動作を示す動作フローチャートである。本実施形態は、例えばＳＲＡＭ形状に関する設計パラメータの組を複数組入力して、例えばSNMとWM（又はHNM）の目的関数の各値を計算しながら多目的最適化処理を実行する設計支援装置の一部として実現することができる。
【００６２】
図１において、目的関数モデル式生成部１０１は、各設計パラメータの定義域を荒く分割して得られる所定組数からなるサンプルを入力し、シミュレータ計算によって、SNM目的関数値とWM目的関数値を計算する。そして、入力された設計パラメタのサンプル組とそれらに対して計算されたSNM目的関数値及びWM目的関数値とを用いて、それぞれ線形回帰分析に基づく数式近似を実行することにより、SNM目的関数モデル式及びWM目的関数モデル式を算出する。
【００６３】
次に、限定記号付論理式生成部１０２は、目的関数モデル式生成部１０１にて算出されたSNM目的関数モデル式及びWM目的関数モデル式と共に、各設計パラメタの定義域の指定を含む論理式を生成する。具体的な論理式の形態は、例えば前述した（１２）式で示される。このとき、前述した（１１）式で示されるような形式の第１の制約条件が付加される。また、最終的に消去したい設計パラメタx1からxtには限定記号が付けられる。更に、この論理式には、必要に応じてVth、リーク電流、電源電圧等の設計量に対応する関数式が含まれてもよい。
【００６４】
次に、細胞分割部１０３は、設計変数ｚと限定記号が付かない設計パラメタxt+1〜xkからなる設計変数空間を、f1-z、f2-zに関して符号不変な領域である細胞に分割する。細胞分割部１０３は、各細胞を表現する論理式と各細胞の標本点に対応する設計パラメタxt+1〜xkの各値と設計変数ｚの値を、各細胞情報としてリスト１に記憶する（以上、図２のステップＳ２０１）。
【００６５】
次に、リスト１から細胞情報が１つ選択され、その細胞情報の標本点と一致する設計パラメタxt+1〜xkの各値の組を有する各標本点に対応する細胞情報群がリスト１から取り出されてリスト２に移動される（図２のステップＳ２０３）。つまり、リスト１から、同じ設計パラメタxt+1〜xkの各値の組を有する標本点群に対応する細胞情報群（図４の４０１や４０２）が取り出されて、リスト２が生成される。そして、リスト２が生成される毎、即ち同じ設計パラメタxt+1〜xkの各値の組を有する標本点群に対応する細胞情報群毎に、図１の第１の細胞処理部１０４と第２の細胞処理部１０５による以下の細胞選択・評価処理（図２のステップＳ２０４）が繰り返し実行される。この処理は、リスト１が空になったと判定されるまで（図２のステップＳ２０２）、繰返し実行される（図２のステップＳ２０２→Ｓ２０３→Ｓ２０４→Ｓ２０２の繰返し処理）。
【００６６】
図１の第１の細胞処理部１０４及び第２の細胞処理部１０５の処理の詳細は、図３の動作フローチャートによって示される。
まず、設計仕様として、歩留まりを表す設計変数ｚに関して、その精度範囲の上限値ｈｉｇｈと下限値ｌｏｗが入力され、それぞれ現在上限値ｈ及び現在下限値ｌ（「ｌ」はアルファベットのエル）として設定される（図３のステップＳ３０１）。
【００６７】
そして、第１の細胞処理部１０４として、図３のステップＳ３０２からＳ３０８までの一連の処理が実行される。
即ちまず、図２のステップＳ２０３で生成されたリスト２内から、現在上限値ｈと現在下限値ｌの範囲内で「（ｈ＋ｌ）／２」に最も近い設計変数ｚの値を有する標本点に対応する細胞情報が任意に１つ選択される（図３のステップＳ３０２）。
【００６８】
次に、ステップＳ３０２にて細胞情報を選択できたか否かが判定される（図３のステップＳ３０３）。
細胞情報を選択できステップＳ３０３の判定がＹＥＳの場合には、ステップＳ３０２で選択された細胞情報の標本点に対応する設計パラメタxt+1〜xkの各値と設計変数ｚの値が、リスト２から取得される。そして、それらの値が図１の限定記号付利子生成部１０２で生成された入力論理式（例えば（１２）式）に代入されて計算されることにより、入力論理式が満たされるか否かが評価される（図３のステップＳ３０４）。
【００６９】
入力論理式が満たされてステップＳ３０４の判定がＹＥＳならば、その標本点が含まれる細胞情報と、その標本点の設計変数ｚの値以下の値の設計変数ｚを有する各標本点に対応する細胞情報群が、リスト２からリスト３に移動させられる（図３のステップＳ３０５）。これ以後、上記設計変数ｚの値以下の値の設計変数ｚを有する標本点が含まれる細胞情報はリスト２には存在しなくなり、上記設計変数ｚの値以下の範囲は探索する必要がなくなるため、現在下限値ｌに上記設計変数ｚの値が設定される（図３のステップＳ３０６）。
【００７０】
逆に、入力論理式が満たされずステップＳ３０４の判定がＮＯならば、その標本点が含まれる細胞情報と、その標本点の設計変数ｚの値以上の値の設計変数ｚを有する各標本点に対応する細胞情報群が、リスト２から削除される（図３のステップＳ３０７）。これらの細胞情報は、リスト３には登録されない。これ以後、上記設計変数ｚの値以上の値の設計変数ｚを有する標本点が含まれる細胞情報はリスト２には存在しなくなり、上記設計変数ｚの値以上の範囲は探索する必要がなくなるため、現在上限値ｈに上記設計変数ｚの値が設定される（図３のステップＳ３０８）。
【００７１】
上記ステップＳ３０７又はＳ３０８の処理の後、更新されたリスト２内から、新たに設定し直された現在上限値ｈと現在下限値ｌの範囲内で「（ｈ＋ｌ）／２」に最も近い設計変数ｚの値を有する標本点に対応する細胞情報が任意に１つ選択される（図３のステップＳ３０２）。そして、上述したのと同様のステップＳ３０２からＳ３０８までの一連の処理が繰り返し実行される。
【００７２】
図１の第１の細胞処理部１０４による上述した処理の結果、現在上限値ｈと現在下限値ｌの範囲内でリスト２から選択される細胞情報がなくなってステップＳ３０３の判定がＮＯとなった時点で、例えば図６の５０１と６０７で囲まれた矩形範囲内の黒塗りされた可能領域に相当する細胞情報が、リスト３に得られることになる。
【００７３】
次に、図１の第２の細胞処理部１０４が、図３のステップＳ３０９からＳ３１２までの一連の処理を実行する。
即ちまず、リスト２の内容が空か否かが判定される（図３のステップＳ３０９）。
【００７４】
リスト２の内容が空ではなくステップＳ３０９の判定がＮＯならば、リスト２から任意の細胞情報が１つ選択され、選択された細胞情報の標本点の設計変数ｚの値が、ステップＳ３０１にて設計仕様として入力された歩留まりの設計変数ｚの下限値ｌｏｗよりも小さいか否かが判定される（図３のステップＳ３１０）。
【００７５】
ステップＳ３１０の判定がＹＥＳならば、その選択された細胞情報は、入力論理式における前述した第１の制約条件を満たしており、入力論理式の評価をせずにリスト３に加えてしまって問題ない。よって、その細胞情報がリスト２からリスト３に移動させられる（図３のステップＳ３１１）。例えば、図６において、６０１と６０２によって囲まれた黒塗りされた矩形の可能領域、又は６０３と６０４によって囲まれた黒塗りされた矩形の可能領域に含まれる細胞が該当する。
【００７６】
逆に、ステップＳ３１０の判定がＮＯならば、その選択された細胞情報は入力論理式における前述した第１の制約条件を満たさないため、入力論理式の評価をせずにリスト２から削除してしまって問題ない。よって、その細胞情報がリスト２から削除される（図３のステップＳ３１２）。例えば、図６において、６０５と６０６によって囲まれた矩形領域に含まれる細胞が該当する。
【００７７】
以上のステップＳ３１１又はＳ３１２の処理の後、ステップＳ３０９の処理に戻って、リスト２が空となってステップＳ３０９の判定がＹＥＳとなるまで、同様の処理が繰り返し実行される。
【００７８】
以上、図３の動作フローチャートで示される図２のステップＳ２０４の細胞選択・評価処理がリスト１が空になるまで繰り返し実行される。最後に、リスト１が空となって図２のステップＳ２０２の判定がＹＥＳとなると、最終的にリスト３として、入力論理式を満たす細胞情報の集合が得られる。前述したように、各細胞情報は、限定記号が付かない設計パラメタxt+1〜xkの何れか１つ以上と設計変数ｚを用いた不等式等を含む論理式で表現されている。従って、リスト３に含まれる全ての細胞情報に含まれる論理式が結合されて出力されることにより、入力された論理式と等価であって、限定記号が付かない設計パラメタxt+1〜xkと設計変数ｚのみを含む論理式が出力されて、本実施形態の処理を終了する。
【００７９】
次式は、出力結果の論理式の一例を示すものであり、限定記号が付かない設計パラメタx1,x2と、設計変数ｚのみを含む論理式となっている。
0 < x1 < 1 and  0 < x2 < 1 and
10258300076526653522074537080000 z + 14539183428429855735191201280000 x2 + 
1787196417913386819524693102400 x1 - 55381371086295177952599446709553 ≦ 0
設計パラメタx1,x2の値の組を順次入力して上記論理式を計算し、ディスプレイ等に描画することにより、設計パラメタx1,x2と歩留まりを表す設計変数ｚの関係を簡単に把握することが可能となる。
【００８０】
図７は、図１の実施形態のシステムを実現できるコンピュータのハードウェア構成の一例を示す図である。
図７に示されるコンピュータは、ＣＰＵ７０１、メモリ７０２、入力装置７０３、出力装置７０４、外部記憶装置７０５、可搬記録媒体７０９が挿入される可搬記録媒体駆動装置７０６、及びネットワーク接続装置７０７を有し、これらがバス７０８によって相互に接続された構成を有する。同図に示される構成は上記システムを実現できるコンピュータの一例であり、そのようなコンピュータはこの構成に限定されるものではない。
【００８１】
ＣＰＵ７０１は、当該コンピュータ全体の制御を行う。メモリ７０２は、プログラムの実行、データ更新等の際に、外部記憶装置７０５（或いは可搬記録媒体７０９）に記憶されているプログラム又はデータを一時的に格納するＲＡＭ等のメモリである。ＣＵＰ７０１は、プログラムをメモリ７０２に読み出して実行することにより、全体の制御を行う。
【００８２】
入力装置７０３は、例えば、キーボード、マウス等及びそれらのインタフェース制御装置とからなる。入力装置７０３は、ユーザによるキーボードやマウス等による入力操作を検出し、その検出結果をＣＰＵ７０１に通知する。
【００８３】
出力装置７０４は、表示装置、印刷装置等及びそれらのインタフェース制御装置とからなる。出力装置７０４は、ＣＰＵ７０１の制御によって送られてくるデータを表示装置や印刷装置に出力する。
【００８４】
外部記憶装置７０５は、例えばハードディスク記憶装置である。主に各種データやプログラムの保存に用いられる。
可搬記録媒体駆動装置７０６は、光ディスクやＳＤＲＡＭ、コンパクトフラッシュ（登録商標）等の可搬記録媒体７０９を収容するもので、外部記憶装置７０５の補助の役割を有する。
【００８５】
ネットワーク接続装置７０７は、例えばＬＡＮ（ローカルエリアネットワーク）又はＷＡＮ（ワイドエリアネットワーク）の通信回線を接続するための装置である。
本実施形態によるシステムは、図１〜図３で示される上述した機能を搭載したプログラムをＣＰＵ７０１が実行することで実現される。そのプログラムは、例えば外部記憶装置７０５や可搬記録媒体７０９に記録して配布してもよく、或いはネットワーク接続装置７０７によりネットワークから取得できるようにしてもよい。
【符号の説明】
【００８６】
１０１  目的関数モデル式生成部
１０２  限定記号付論理式生成部
１０３  細胞分割部
１０４  第１の細胞処理部
１０５  第２の細胞処理部
７０１  ＣＰＵ
７０２  メモリ
７０３  入力装置
７０４  出力装置
７０５  外部記憶装置
７０７  ネットワーク接続装置
７０６  可搬記録媒体駆動装置
７０９  可搬記録媒体
７０８  バス
【図１】
0005402351.tif 000002
【図２】
0005402351.tif 000003
【図３】
0005402351.tif 000004
【図４】
0005402351.tif 000005
【図５】
0005402351.tif 000006
【図６】
0005402351.tif 000007
【図７】
0005402351.tif 000008
【図９】
0005402351.tif 000009
【図１０】
0005402351.tif 000010
【図８】
0005402351.tif 000011