(57)【特許請求の範囲】
【請求項１】
少なくとも遅延解析手段と，遅延改善量・コスト計算手段と，ノード挿入手段と，セパレータ集合抽出手段と，遅延改善箇所特定手段とを備える計算機によりネットワークにおける遅延改善可能な箇所を特定する方法であって，
前記遅延解析手段が，遅延改善対象となるネットワークのネットワークデータと遅延制約データとをもとに各ノードごとに遅延解析を行う第１の処理過程と，
前記遅延改善量・コスト計算手段が，前記遅延解析の処理結果に基づき，ネットワーク中の全てのノードの遅延改善可能量，遅延改善コストおよび遅延的な余裕を示すスラックを計算し，これらの値を各ノードに対応させて記憶装置に記憶する第２の処理過程と，
前記ノード挿入手段が，前記記憶装置に記憶されたデータをもとに，ネットワーク中の全ての中間ノードｎについて，中間ノードｎへの入力ノード中で最小のスラックを持つノード以外の全ての各入力ノードと前記中間ノードｎとの間に，当該入力ノードのスラックと前記最小のスラックを持つノードのスラックとの差を遅延改善可能量とし遅延改善コストを０としたダミーノードをそれぞれ挿入し，また，前記中間ノードｎからの出力ノード中で最小のスラックを持つノード以外の全ての各出力ノードと前記中間ノードｎとの間に，当該出力ノードのスラックと前記最小のスラックを持つノードのスラックとの差を遅延改善可能量とし遅延改善コストを０としたダミーノードをそれぞれ挿入する第３の処理過程と，
前記セパレータ集合抽出手段が，前記ダミーノード挿入後のネットワークについて，そのネットワークを入力側と出力側に二分するノード集合であるセパレータ集合を抽出する第４の処理過程と，
前記遅延改善箇所特定手段が，前記第４の処理過程で求められた一つのセパレータ集合で改善できる遅延改善量を当該セパレータ集合に含まれるノードの遅延改善可能量の最小値とし，１または複数のセパレータ集合による遅延改善量の合計が目標とするネットワークの遅延改善量を達成するセパレータ集合の組を探索し，探索されたセパレータ集合の組に含まれるノードの遅延改善コストの和が小さいものを選択することにより，ネットワークの遅延改善箇所を特定する第５の処理過程とを有する
ことを特徴とするネットワークにおける遅延改善箇所特定処理方法。
【請求項２】
請求項１記載のネットワークにおける遅延改善箇所特定処理方法において，
前記第４および第５の処理過程では，一つのセパレータ集合を求める操作を繰り返して，目標とするネットワークの遅延改善量を達成するセパレータ集合の組の中で遅延改善コストの和が最小となる多重セパレータ集合の近似最適解を得る
ことを特徴とするネットワークにおける遅延改善箇所特定処理方法。
【請求項３】
請求項２に記載のネットワークにおける遅延改善箇所特定処理方法において，
前記第４および第５の処理過程では，ネットワークに対応したフローネットワークを作り，遅延改善箇所の目的とするセパレータ集合を求めるために“最大フロー＝最小カット”アルゴリズムを用い，該アルゴリズムの実行において２回目以降の最大フローを求める際に前回求められた最大フローを初期フローとして用いる
ことを特徴とするネットワークにおける遅延改善箇所特定処理方法。
【請求項４】
計算機によりネットワークにおける遅延改善可能な箇所を特定する装置であって，
遅延改善対象となるネットワークのネットワークデータと遅延制約データとをもとに各ノードごとに遅延解析を行う遅延解析手段と，
前記遅延解析の処理結果に基づき，ネットワーク中の全てのノードの遅延改善可能量，遅延改善コストおよび遅延的な余裕を示すスラックを計算し，これらの値を各ノードに対応させて記憶装置に記憶する遅延改善量・コスト計算手段と，
前記記憶装置に記憶されたデータをもとに，ネットワーク中の全ての中間ノードｎについて，中間ノードｎへの入力ノード中で最小のスラックを持つノード以外の全ての各入力ノードと前記中間ノードｎとの間に，当該入力ノードのスラックと前記最小のスラックを持つノードのスラックとの差を遅延改善可能量とし遅延改善コストを０としたダミーノードをそれぞれ挿入し，また，前記中間ノードｎからの出力ノード中で最小のスラックを持つノード以外の全ての各出力ノードと前記中間ノードｎとの間に，当該出力ノードのスラックと前記最小のスラックを持つノードのスラックとの差を遅延改善可能量とし遅延改善コストを０としたダミーノードをそれぞれ挿入するノード挿入手段と，
前記ダミーノード挿入後のネットワークについて，そのネットワークを入力側と出力側に二分するノード集合であるセパレータ集合を抽出するセパレータ集合抽出手段と，
前記セパレータ集合抽出手段で求められた一つのセパレータ集合で改善できる遅延改善量を当該セパレータ集合に含まれるノードの遅延改善可能量の最小値とし，１または複数のセパレータ集合による遅延改善量の合計が目標とするネットワークの遅延改善量を達成するセパレータ集合の組を探索し，探索されたセパレータ集合の組に含まれるノードの遅延改善コストの和が小さいものを選択することにより，ネットワークの遅延改善箇所を特定する遅延改善箇所特定手段とを備える
ことを特徴とするネットワークにおける遅延改善箇所特定処理装置。
【請求項５】
計算機によりネットワークにおける遅延改善可能な箇所を特定する装置を実現するためのプログラムを記録した計算機読み取り可能な記録媒体であって，
前記計算機を，
遅延改善対象となるネットワークのネットワークデータと遅延制約データとをもとに各ノードごとに遅延解析を行う遅延解析手段と，
前記遅延解析の処理結果に基づき，ネットワーク中の全てのノードの遅延改善可能量，遅延改善コストおよび遅延的な余裕を示すスラックを計算し，これらの値を各ノードに対応させて記憶装置に記憶する遅延改善量・コスト計算手段と，
前記記憶装置に記憶されたデータをもとに，ネットワーク中の全ての中間ノードｎについて，中間ノードｎへの入力ノード中で最小のスラックを持つノード以外の全ての各入力ノードと前記中間ノードｎとの間に，当該入力ノードのスラックと前記最小のスラックを持つノードのスラックとの差を遅延改善可能量とし遅延改善コストを０としたダミーノードをそれぞれ挿入し，また，前記中間ノードｎからの出力ノード中で最小のスラックを持つノード以外の全ての各出力ノードと前記中間ノードｎとの間に，当該出力ノードのスラックと前記最小のスラックを持つノードのスラックとの差を遅延改善可能量とし遅延改善コストを０としたダミーノードをそれぞれ挿入するノード挿入手段と，
前記ダミーノード挿入後のネットワークについて，そのネットワークを入力側と出力側に二分するノード集合であるセパレータ集合を抽出するセパレータ集合抽出手段と，
前記セパレータ集合抽出手段で求められた一つのセパレータ集合で改善できる遅延改善量を当該セパレータ集合に含まれるノードの遅延改善可能量の最小値とし，１または複数のセパレータ集合による遅延改善量の合計が目標とするネットワークの遅延改善量を達成するセパレータ集合の組を探索し，探索されたセパレータ集合の組に含まれるノードの遅延改善コストの和が小さいものを選択することにより，ネットワークの遅延改善箇所を特定する遅延改善箇所特定手段として，
機能させるためのネットワークにおける遅延改善箇所特定処理プログラムの記録媒体。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は，ネットワークにおける遅延改善箇所特定処理方法，特にネットワークにおける遅延を改善するために，ネットワークにスラックの差に応じたダミーノードを挿入することにより，セパレータ集合（separator-set ）を用いた効率のよい改善箇所の特定処理方法に関する。
【０００２】
ネットワーク上に信号や貨物などが流れる場合を考えると，ネットワークの遅延時間をできるだけ小さくするという問題は，産業界のあらゆる面で生ずるものである。ネットワークと遅延時間の例として，電子回路における信号遅延時間，通信システムにおける情報伝送時間，物流システムにおける貨物等の輸送時間などが挙げられる。そして，いずれの例でも，遅延時間はネットワークの性能を決める重要な指標である。
【０００３】
ネットワークの遅延改善を施す手段がある場合に，ネットワーク全体の遅延制約を満たし，かつ，遅延改善にかかるコストを最小にすることが重要である。例えば，遅延時間に余裕がある経路（非クリティカルパス）については，遅延改善が不要か，または，少しの遅延改善で済むケースが多い。そのような経路について最大限に遅延を改善しても，他のクリティカルパスの存在によっては，ネットワーク全体の性能が向上しない。このような場合には，改善される遅延量よりも遅延改善コストを抑制するほうが重要である。
【０００４】
【従来の技術】
ネットワークにおける遅延の例を図８に示す。例えば，ネットワークがＬＳＩ内の電子回路であるとすると，丸で示すノードが論理ゲートに相当し，ノード間のエッジが論理ゲート間の配線に相当し，矢印の向きが信号の流れる方向に相当する。
【０００５】
図８において，各ノード内には，上段にノード名Ｎと下段にノードを通過するためにかかる遅延Ｄを記している。（ａ，ｒ，ｓ）は，ａ＝到着時刻（arrival time），ｒ＝必要時刻（required time ），ｓ＝スラック（slack ）を表す。
【０００６】
スラックとは，遅延的な余裕を意味し，
スラック（ｓ）＝必要時刻（ｒ）−到着時刻（ａ）
の式で定義される。スラックが負数のときは，遅延制約に違反していることを示し，この状態を「遅延に関してクリティカルである」という。負数のスラックは，その絶対値が大きい程，遅延制約違反量が大きい。
【０００７】
遅延制約違反を侵しているネットワークにおいて，具体的にどの箇所を遅延改善すればよいかという「遅延改善箇所の特定」は難しい問題である。例えばＬＳＩ内の電子回路のように，ノード数もエッジ数も非常に多いネットワークの場合には，全体について一度に遅延改善を行うことは不可能である。そのため，部分的な遅延改善を繰り返さざるを得ない。
【０００８】
図８に示すネットワークの例において，ノードＴ，ノードＸおよびノードＷの遅延改善が可能で，その他のノードは遅延改善ができないものとする。そして，ノードＴ，ノードＸおよびノードＷの遅延改善後のノード自身の遅延の減少分とコストの上昇分とを，それぞれ，Ｔが（２，３），Ｘが（３，６），Ｗが（２，５）とする。
【０００９】
遅延改善を施すノード集合を“ selection set（セレクション集合）”と定義する。遅延改善可能な３つのノード全てをselection set に選ぶと，出力Ｏ1 のスラックは「−３」から「１」になり，遅延制約を満たす。ただし，遅延改善コストは，３＋６＋５＝１４となる。
【００１０】
一方，｛Ｘ，Ｔ｝をselection set に選ぶと，出力Ｏ1 のスラックは，「０」で，コストは先のケースよりも小さい６＋３＝９である。したがって，この場合に，最適なselection set は，｛Ｘ，Ｔ｝である。
【００１１】
以上のように，遅延制約を満たすために，部分的な遅延改善をシステマティックに繰り返す手法として，「Singh法」が提案されている（参考文献：K.J.Singh,“Performance Optimization of Digital Circuits”, Phd thesis, Univ. of California, Berkeley, 1992 ) 。
【００１２】
図９は，従来方法による部分的な遅延改善処理の例を示す。
［ステップＳ９１］：ネットワークと遅延制約のデータを読み込む。
［ステップＳ９２］：ネットワークの遅延解析を行い，全てのノードのスラックを求める。全ての出力ノードでスラックが非負ならば，すなわち遅延制約違反がなければ，“成功”を返して終了する。
［ステップＳ９３］：ネットワーク中の各ノードについて，ノード自身の遅延改善量とそれにかかるコストを計算する。
［ステップＳ９４］：最適なselection set を選びだし，これに含まれるノードに対して遅延改善を施す。
［ステップＳ９５］：ステップＳ９４の処理の結果，遅延制約違反量が減る場合には，ステップＳ９２の処理へ戻り，同様に処理を繰り返す。そうでない場合には，“失敗”を返して処理を終了する。
【００１３】
Singh法では，ステップＳ９４の処理において，selection set を決める手段として，separator-set とselection functionのそれぞれを用いる手法を提案している。
【００１４】
separator-set を用いる手法では，最適なネットワークを入力側と出力側とに二分するノード集合を見つける。このノード集合を“separator-set （セパレータ集合）”という。このseparator-set は，ネットワークの遅延をε改善するノード集合の中で，コストの和が最小のものである。ここで，εとは，ユーザまたはシステムが定めた１回当たりの遅延改善目標量である。
【００１５】
このようなseparator-set は, ネットワークフローグラフにおける“最大フロー＝最小カット”アルゴリズムで，多項式時間内に求めることができる（参考文献：E.A.Dinic,“Algorithm for solution of a problem of maximum flow in a network with power estimation”, Soviet Mathmatics Doklady, 11, pp1277-1280, 1970）。
【００１６】
しかし，この手法では，ＤＡＧ（Directed Acyclic Graph）になっているようなネットワークでは最適解を求めることができない。例えば，図８に示すネットワークの遅延改善箇所を，従来のseparator-set を用いる手法を用いて求めると，ネットワークを入力側と出力側とに二分するseparator-set として，図１０に示すように，｛Ｘ，Ｗ｝が求まる。図１０に示すｉ番目のノード内の上段は，ノード名（name(i) ），中段の左側はノードｉのスラック，中段の右側はそのノードｉで改善可能な遅延の量，下段は遅延改善のコストを表している。
【００１７】
この図１０におけるseparator-set は｛Ｘ，Ｗ｝であり，これらのノード｛Ｘ，Ｗ｝について遅延改善を図ると，遅延制約は満たされる。しかし，このseparator-set の遅延改善コストは６＋５＝１１なので，selection set として最適ではない。
【００１８】
２番目のselection functionを用いる手法では，ネットワークの遅延をε改善するノード集合を論理関数として構築する。例えば図１０におけるselection functionは，Ｆ（Ｏ1 ）＝Ｘ・（Ｗ＋Ｔ）である。この関数を１にする変数集合が一つのselection set となる。この場合，selection set の候補として，｛Ｘ，Ｗ｝と｛Ｘ，Ｔ｝があり，前者のコストが１１，後者のコストが９であるため，コストが９と小さい後者が選ばれる。
【００１９】
selection functionは，ＢＤＤ（Binary Decision Diagram ）によって表現する（参考文献： R.E.Bryant,“Graph-based Algorithms for Boolean Function Manipulation”,IEEE Trans. on Computers, C-35, August 1986）。この手法では，ＤＡＧのネットワークでも最適解が得られるという利点があるが，大規模なネットワークに対して適用した場合には，メモリ不足でＢＤＤが構築できないことがあるという欠点がある。
【００２０】
【発明が解決しようとする課題】
本発明の目的は，ＢＤＤのようにメモリ不足を招かずに，最適または最適に近い解を求めることができ，かつ，計算時間の効率を損なわずに，selection set を選びだすことにより，ネットワークの遅延改善が可能な箇所を特定する方法を実現することである。
【００２１】
【課題を解決するための手段】
本発明は，計算機によりネットワークにおける遅延改善可能な箇所を特定するにあたって，遅延改善の処理対象として与えられたネットワークに，出力ノードごとに与えられる遅延制約の違いを吸収するための遅延改善コストを０としたダミーノードを挿入し，ダミーノード挿入後のネットワークについて，そのネットワークを入力側と出力側に二分するノード集合であるセパレータ集合を抽出し，求めたセパレータ集合を用いて，ネットワークの遅延改善箇所を特定することを主要な特徴とする。
【００２２】
セパレータ集合を用いて，ネットワークの遅延改善箇所を特定する場合，複数のセパレータ集合を用いて，目標とするネットワークの遅延改善量を達成可能な遅延改善箇所を選出する。この際に，一つのセパレータ集合を求める操作を繰り返して，多重セパレータ集合の近似最適解を得るようにしてもよい。さらに，２回目以降の最大フローを求める際に前回求められた最大フローを初期フローとして用いることにより，効率的に近似最適解を求めることができる。
【００２３】
以上の処理を計算機に実行させるためのプログラムは，計算機が読み取り可能な可搬媒体メモリ，半導体メモリ，ハードディスクなどの適当な記録媒体に格納することができる。
【００２４】
【発明の実施の形態】
図１は，本発明の実施の形態に係るシステム構成図である。遅延改善装置１は，例えばＬＳＩ設計のＣＡＤシステムとして用いられるような装置であって，ＣＰＵおよびメモリなどのハードウェアと，本処理を実現するソフトウェアプログラムとからなる。
【００２５】
データ入力部２は，対象となるネットワークデータ１０およびその遅延制約データ１１を入力して，これらのデータを内部データベース３として蓄える。遅延解析部４は，これらのデータをもとに各ノードごとに遅延解析を行う。遅延改善量・コスト計算部５は，遅延解析の処理結果に基づき遅延改善が可能な量およびその遅延改善に必要なコストを計算する。計算結果は，内部データベース３に記録される。
【００２６】
遅延改善箇所特定処理部６は，ダミーノード挿入部６１，セパレータ集合抽出部６２，セレクション集合選択部６３を備え，最適または最適に近い遅延改善箇所を求める。このため，ダミーノード挿入部６１は，内部データベース３を参照し，遅延改善の処理対象として与えられたネットワークに，出力ノードごとに与えられる遅延制約の違いを吸収するためのスラックの差に応じた遅延改善コストを０としたダミーノードを生成して挿入する。セパレータ集合抽出部６２は，ダミーノード挿入後のネットワークについて，そのネットワークを入力側と出力側に二分するノード集合であるseparator-set を抽出する。セレクション集合選択部６３は，セパレータ集合抽出部６２が求めたseparator-set を用いて，Selection Set を選択する。このとき，セパレータ集合抽出部６２およびセレクション集合選択部６３により，一つのseparator-set を求める操作を繰り返して，目標とするネットワークの遅延改善量が達成されるように，逐次改善箇所を特定し，多重separator-set の近似最適解を得る。この結果を内部データベース３に記録する。
【００２７】
データ出力部７は，内部データベース３を参照し，遅延改善箇所特定処理部６が求めた多重Selection Set に含まれるノードについて遅延改善を行い，遅延最適化されたネットワークデータ１２を出力する。
【００２８】
図２は，本発明の実施の形態による処理の流れの概要を示す図である。図２に示す処理の前提として，図１に示す遅延解析部４および遅延改善量・コスト計算部５の処理によって，全てのノードのスラック，遅延改善可能量，コストが既に計算されているものとする。
【００２９】
［ステップＳ１］：ネットワークの入力ノードと出力ノードを除く，全ての中間ノードｎについて，ステップＳ２〜ステップＳ４の処理を繰り返す。
【００３０】
［ステップＳ２］：ノードｎへの入力ノード中で最小のスラックを持つものをｆ＿ｍｉｎとする。図３は，ノードｎの入力側にダミーノードを挿入する処理を説明するための図である。図３（Ａ）では，ノードｆk が最小のスラックを持ち，これがｆ＿ｍｉｎであるとする。
【００３１】
［ステップＳ３］：ノードｆ＿ｍｉｎ以外のノードｎの全ての入力ノードｆについて，ステップＳ４の処理を繰り返す。
【００３２】
［ステップＳ４］：ダミーノードｄa をノードｆとノードｎとのエッジ上に挿入する。挿入するダミーノードｄa には，ノード自身の遅延と遅延改善可能量として，ノードｆとノードｆ＿ｍｉｎのスラックの差（＝ｓ（ｆ）−ｓ（ｆ＿ｍｉｎ））を持たせ，コストとして０を持たせる。なお，「エッジ上にダミーノードを挿入する」とは，ネットワークにダミーノードｄa を作った後に，ノードｆからノードｎへの１本のエッジを，ノードｆからダミーノードｄa へのエッジと，ダミーノードｄa からノードｎへのエッジの２本に分割することを意味する。この結果，図３（Ｂ）に示すように，ノードｆk を除く各ノードｆ1 〜ｆm とノードｎとの間にダミーノードｄa1〜ｄamが挿入されることになる。
【００３３】
［ステップＳ５］：続いて，出力ノードの中で最小のスラックを持つものをｐｏ＿ｍｉｎとする。図４は，ノードｎの出力側にダミーノードを挿入する処理を説明するための図である。図４（Ａ）では，ノードｐｏj が最小のスラックを持ち，これがｐｏ＿ｍｉｎであるとする。
【００３４】
［ステップＳ６］：ノードｐｏ＿ｍｉｎ以外の全ての出力ノードｐｏについて，ステップＳ７の処理を繰り返す。
【００３５】
［ステップＳ７］：ダミーノードｄb をノードｐｏへの入力エッジ上に挿入する。挿入するダミーノードｄb には，ノード自身の遅延と遅延改善可能量としてノードｐｏとノードｐｏ＿ｍｉｎとのスラックの差（＝ｓ（ｐｏ）−ｓ（ｐｏ＿ｍｉｎ））を持たせ，コストとして０を持たせる。この結果，図４（Ｂ）に示すように，ノードｎと，ノードｐｏj を除く各ノードｐｏ1 〜ｐｏr との間にダミーノードｄb1〜ｄbrが挿入されることになる。
【００３６】
［ステップＳ８］：ダミーノードｄa ，ｄb を含んだネットワークに対して，目標遅延改善量を達成する最適な多重separator-set を抽出する。
【００３７】
例えば図８に示すネットワークに対して，本方式により遅延改善箇所を特定する処理を行うと，図５に示すように，遅延改善可能量がそれぞれ２，１のダミーノードｄ1 ，ｄ2 が挿入されることになる。この場合には，出力は一つしか存在しないので，出力ノードの入力エッジにはダミーノードは挿入されない。
【００３８】
ここで，ダミーノードｄ1 ，ｄ2 を挿入したネットワークのseparator-set を考える。一つのseparator-set で改善できる遅延量は，separator-set に含まれるノードの改善量の最小値である。複数のseparator-set を選択して，それらの遅延改善量の合計が目標の遅延改善量を達成するようにすれば，遅延制約を満たすことができる。このような複数のseparator-set の集合を多重separator-set と呼ぶ。
【００３９】
さらに，多重separator-set に含まれるノードのコスト和が最小なものを「最適な多重separator-set 」と呼ぶ。一つの多重separator-set に含まれる複数のseparator-set が，同じノードを共有することは許容される。ただし，共有するseparator-set の遅延改善量の合計が，共有されるノードの遅延改善量を越えてはならない。
【００４０】
本方式の作用は，以下のとおりである。上述したように，ダミーノードをネットワークに挿入することは，一度分岐した二つのパスが再び合流する再収斂のような場合のパス長の差や，出力ノードごとに与えられる遅延制約の違いを吸収して，全てのノードのスラックを等しくする。
【００４１】
このような，ネットワークに含まれる有限コストを持つ任意のseparator-set は，そのノード集合の全てがダミーノードとなることはない。なぜなら，separator-set は必ず一つ以上のクリティカルパス上のノードを含み，かつ，ダミーノードはその定義からクリティカルパス上には作られないからである。したがって，ダミーノードを挿入したネットワークに，有限コストのseparator-set が存在すれば，必ず遅延改善を行うことができる。
【００４２】
ダミーノードのコストが０なのは，ダミーノードをスラックの余裕分まで遅延改善できるノードとして扱うことを意味する。すなわち，ダミーノードの遅延改善コストは０であるので，ダミーノードは他の通常ノードよりも優先的にseparator-set に選ばれる。ダミーノードがseparator-set に選ばれたとき，ダミーノードについての遅延改善は，当然ながら不要である。
【００４３】
図５に示すネットワークの例では，コストが最小のseparator-set を求めると，｛Ｔ，ｄ1 ｝となる。しかし，このseparator-set ｛Ｔ，ｄ1 ｝での遅延改善可能量は２であり，これだけでは目標の遅延改善量＝３を達成できない。そこで，もう一つのseparator-set ｛Ｘ，ｄ2 ｝も追加する。そうすると，遅延改善可能量の合計は３となり，その遅延改善コストも９である。これは，Singh法のselection functionによる処理結果と同じ結果である。
【００４４】
本発明は，この例のように，従来では，例えばＤＡＧや大規模なネットワークには適用ができなかったselection functionと同程度の最適解（またはその近似解）を，多重separator-set によって得ることができる。
【００４５】
さらに，フローネットワークの“最大フロー＝最小カット”アルゴリズムを用いることで，ネットワークのサイズに関して比例したメモリ使用量と多項式オーダの処理時間によって，最適解（またはその近似解）を得ることができる。
【００４６】
以下に，図２に示す本実施の形態の処理の流れのうち，ステップＳ８の処理について，さらに詳しく説明する。
【００４７】
多重separator-set を求める処理手法として，以下の二つの手法がある。
・多重separator-set の最適解を求める手法
・多重separator-set の近似最適解を求める手法
１）多重separator-set の最適解を求める手法
この手法では，まず全てのseparator-set を列挙し，それらのいくつかを組み合わせて遅延改善量を達成し，かつ，コストが最小のものを求める。
２）多重separator-set の近似最適解を求める手法
１）に示した多重separator-set の最適解を求める手法は，理論的には可能であるが，全てのseparator-set を列挙し，その最適な組み合わせを求めることは計算時間やメモリ使用量などの計算機資源の関係から実際上容易ではない。そこで，本例では，より現実的な多重separator-set の近似最適解を求める手法を用いる。
【００４８】
図６は，多重separator-set の近似最適解を求める処理の流れの概要図である。
【００４９】
［ステップＳ１１］：ネットワークに対応したフローネットワークを作る。以下の手順により行う。
〔１〕ネットワークの各ノード（ダミーノードを含む）ｎを二つのノードに置き換える。それらを“ｆｒｏｍノード”と“ｔｏノード”と名付ける。ｆｒｏｍノードには，ｎの全ての入力エッジを繋ぐ。ｔｏノードには，ｎの全ての出力エッジを繋ぐ。これらのエッジの容量を「＋∞」にする。次に，ｆｒｏｍノードからｔｏノードにエッジを作る。このエッジは，元のネットワークのノードに１対１に対応するものである。このエッジの容量には，元のノードのコストを設定する。また，このエッジに“遅延改善残量”を表す変数を設け，その初期値をノード自身の遅延改善可能量に設定する。
〔２〕フローのソースノードを作り，そのソースノードから，ネットワークの全ての入力ノードへ，容量＝＋∞のエッジを作る。
〔３〕フローのシンクノードを作り，ネットワークの全ての出力ノードからシンクノードへ，容量＝＋∞のエッジを作る。
【００５０】
［ステップＳ１２］：フローネットワークの最大フローを，Ｄｉｎｉｃ法（参考文献：E.A.Dinic,“Algorithm for solution of a problem of maximum flow in a network with power estimation”, Soviet Mathmatics Doklady, 11, pp1277-1280, 1970）を用いて求める。求められたフローが＋∞であるならば，ステップＳ１５の処理へ進む。
【００５１】
［ステップＳ１３］：ステップＳ１２の処理で求められたフローに対応するcut-set を求める。
【００５２】
［ステップＳ１４］：ステップＳ１３の処理で求められたcut-set について以下の処理を行った後，ステップＳ１２の処理へ戻る。
〔１〕cut-set に含まれるエッジの遅延改善残量で最小のものを求め，これをｄと置く。
〔２〕cut-set に含まれる全てのエッジについて，その遅延改善残量をｄだけ減ずる。その結果，遅延改善残量が０になったエッジは，以降のcut-set に選ばれないように，その容量を＋∞に設定する。遅延改善残量が０より大きいその他のエッジについて，その容量を０にする。これは，以降に求められるcut-set に対して，遅延改善コストを２回以上計上しないための処理である。
【００５３】
［ステップＳ１５］：ステップＳ１３の処理で求められたcut-set の和集合を求め，その和集合の各エッジに対応するノードに置き換えたものを，多重separator-set の近似解とする。
【００５４】
なお，上記の処理の例では，ステップＳ１１の処理において，エッジの容量を，元のノードの遅延改善コストに設定したが，これを「平均遅延改善コスト＝遅延改善コスト／遅延改善可能量」に設定する方法も考えられる。これは，遅延改善量とコストが比例するようなケースに有効である。この場合には，ステップＳ１４の〔２〕の処理において，遅延改善可能量が０より大きいエッジの容量を変える必要はない。
【００５５】
最後のコスト例のように，多重separator-set を求める最中にエッジの容量が決して減少しない場合で，かつ，最大フローを求めるアルゴリズムにＤｉｎｉｃ法のような「増加路法」を用いる場合には，計算効率が上がる。ステップＳ１２の処理において，最大フローを求めたならば，それを毎回保存しておき，２回目以降のステップＳ１２では，前回の最大フローの結果を初期フローとして使い，容量が増加したエッジに沿ってフローを増加させるのである。これによって，最大フローを求める時に毎回エッジを０にしてから増加させる処理を省略でき，計算時間の大幅な短縮が可能となる。
【００５６】
ノード数ｎ，エッジ数ｍのフローネットワークの最大流量，またはcut-set を求める計算量は，Ｄｉｎｉｃ法で，オーダがＯ（ｎ2 ｍ）である。本実施の形態による多重separator-set の近似解を求める方法で，separator-set の個数ｃだけ改善箇所を求めるとすると，計算量のオーダはＯ（ｃ・ｎ2 ｍ）になり，計算時間は多項式オーダとなる。使用するメモリ量は線形オーダである。従来手法によるＢＤＤを用いたselection functionが，計算時間もメモリ使用量も最悪指数オーダになることを考慮すれば，本発明の処理効率の優位性は明らかである。
【００５７】
図７に，本発明をＬＳＩ回路の遅延最適化に適用した場合の，効果測定のための実験結果を示す。比較対象は，従来手法の一つであるselection function法である。使用した計算機は，ＣＰＵにIntel 社のIntel Pentium II (400MHz) を，メモリに１ＧＢを搭載したものである。図７に示す実験結果から，本発明は，従来手法に比べて面積増加を抑えつつ，遅延の改善能力が劣っていないことが明らかである。計算時間も同等である。しかし，s13207-comb ，s38417-comb ，s38584-comb に見られるように，大きな回路については，従来手法ではメモリ不足により対応することができなかったのに対し，本発明では，全ての回路に対して，実用的な時間内で遅延最適化を行うことが可能であった。実験中，本発明における最大使用メモリ量は８５ＭＢであった。したがって，１ＧＢのメモリを搭載した計算機を用いた場合には，今回の実験の対象とした回路の１０倍以上大きな回路についても処理することが可能であることがわかる。
【００５８】
【発明の効果】
以上説明したように，本発明によれば，ネットワークの遅延改善において，ネットワークにノードのスラックの差に応じたダミーノードを挿入することにより，separator-set を用いた効率の良い，かつ，遅延改善コストが最適な，または最適に近い遅延改善箇所の特定が可能になる。
【図面の簡単な説明】
【図１】本発明の実施の形態に係るシステム構成図である。
【図２】本発明の実施の形態による処理の流れの概要図である。
【図３】ダミーノードの挿入方法を説明する図である。
【図４】ダミーノードの挿入方法を説明する図である。
【図５】特定した多重separator-set の例を示す図である。
【図６】多重separator-set の近似最適解を求める処理の流れの概要図である。
【図７】本発明をＬＳＩ回路の遅延最適化に適用した場合の効果測定のための実験結果を示す図である。
【図８】ネットワークにおける遅延の例を示す図である。
【図９】従来方法による部分的な遅延改善処理の例を示す図である。
【図１０】従来の手法によるseparator-set の例を示す図である。
【符号の説明】
１    遅延改善装置
２    データ入力部
３    内部データベース
４    遅延解析部
５    遅延改善量・コスト計算部
６    遅延箇所特定処理部
７    データ出力部
１０  ネットワークデータ
１１  遅延制約データ
１２  遅延最適化されたネットワークデータ
６１  ダミーノード挿入部
６２  セパレータ集合抽出部
６３  セレクション集合選択部
【図１】
0003766234.tif 000002
【図２】
0003766234.tif 000003
【図３】
0003766234.tif 000004
【図４】
0003766234.tif 000005
【図５】
0003766234.tif 000006
【図６】
0003766234.tif 000007
【図７】
0003766234.tif 000008
【図８】
0003766234.tif 000009
【図９】
0003766234.tif 000010
【図１０】
0003766234.tif 000011