JPH08212249A - グラフ分割化システム - Google Patents
グラフ分割化システムInfo
- Publication number
- JPH08212249A JPH08212249A JP7285249A JP28524995A JPH08212249A JP H08212249 A JPH08212249 A JP H08212249A JP 7285249 A JP7285249 A JP 7285249A JP 28524995 A JP28524995 A JP 28524995A JP H08212249 A JPH08212249 A JP H08212249A
- Authority
- JP
- Japan
- Prior art keywords
- nodes
- seed
- partition
- graph
- partitioning
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Granted
Links
Classifications
-
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F30/00—Computer-aided design [CAD]
- G06F30/10—Geometric CAD
- G06F30/18—Network design, e.g. design based on topological or interconnect aspects of utility systems, piping, heating ventilation air conditioning [HVAC] or cabling
-
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F30/00—Computer-aided design [CAD]
- G06F30/30—Circuit design
- G06F30/39—Circuit design at the physical level
- G06F30/392—Floor-planning or layout, e.g. partitioning or placement
Landscapes
- Engineering & Computer Science (AREA)
- Physics & Mathematics (AREA)
- Theoretical Computer Science (AREA)
- Computer Hardware Design (AREA)
- General Physics & Mathematics (AREA)
- Geometry (AREA)
- General Engineering & Computer Science (AREA)
- Evolutionary Computation (AREA)
- Computational Mathematics (AREA)
- Pure & Applied Mathematics (AREA)
- Mathematical Optimization (AREA)
- Mathematical Analysis (AREA)
- Computer Networks & Wireless Communication (AREA)
- Architecture (AREA)
- Design And Manufacture Of Integrated Circuits (AREA)
Abstract
(57)【要約】
【課題】 ノードとそれらを接続するエッジとから成る
グラフの初期分割を計算するシステムは、良好な確率的
サーチによる解析を最適に利用していない。 【解決手段】 最小カットサイズを有する分割によって
ノードとエッジの最適配置を提供するものであり、初期
分割はグラフ分割のカーニガン／リン・システムによる
以下の使用のために提示される。初期分割を計算するた
めにシード成長発見的解法と確率的サーチプロセスとの
組み合せを使用し、シード成長発見的解法はシードノー
ドの初期集合を反復的に増大することにより分割を構築
し、そのサーチプロセスは使用するのに良好なシードノ
ードの集合を探す。シード成長発見的解法、確率的サー
チプロセスおよびカーニガン／リン・アルゴリズムの結
果として生じる組み合わせはグラフを分割するための優
れたシステムを構成する。
グラフの初期分割を計算するシステムは、良好な確率的
サーチによる解析を最適に利用していない。 【解決手段】 最小カットサイズを有する分割によって
ノードとエッジの最適配置を提供するものであり、初期
分割はグラフ分割のカーニガン／リン・システムによる
以下の使用のために提示される。初期分割を計算するた
めにシード成長発見的解法と確率的サーチプロセスとの
組み合せを使用し、シード成長発見的解法はシードノー
ドの初期集合を反復的に増大することにより分割を構築
し、そのサーチプロセスは使用するのに良好なシードノ
ードの集合を探す。シード成長発見的解法、確率的サー
チプロセスおよびカーニガン／リン・アルゴリズムの結
果として生じる組み合わせはグラフを分割するための優
れたシステムを構成する。
Description
【０００１】
【発明の属する技術分野】この発明は、グラフを分割す
るためのシステムに、特に予備分割化システムに関す
る。
るためのシステムに、特に予備分割化システムに関す
る。
【０００２】
【従来の技術】グラフはノードの集合とそれらを接続す
るエッジとから成り立つ。グラフ分割化はグラフノード
の集合を部分集合に分割する問題に与えられた名称であ
り、その際、一定の基準(例えば、部分集合のサイズ、
異なる部分集合のノード間のエッジ数等)が最適化され
るようにする。この問題の幾つかの実際の例が、コンピ
ューター回路やチップの設計において現れており、ここ
では、グラフノードは回路構成要素であり、そして部分
集合への分割化は、半導体の層、またはプリント回路基
板のモジュールなどの、回路の物理的基板への割り当て
に相当する。
るエッジとから成り立つ。グラフ分割化はグラフノード
の集合を部分集合に分割する問題に与えられた名称であ
り、その際、一定の基準(例えば、部分集合のサイズ、
異なる部分集合のノード間のエッジ数等)が最適化され
るようにする。この問題の幾つかの実際の例が、コンピ
ューター回路やチップの設計において現れており、ここ
では、グラフノードは回路構成要素であり、そして部分
集合への分割化は、半導体の層、またはプリント回路基
板のモジュールなどの、回路の物理的基板への割り当て
に相当する。
【０００３】グラフ分割化の他の適用分野としては、コ
ンピューター・アーキテクチャー、コンピューター・ネ
ットワークの経路指定、データベース設計、そして分散
および並列処理がある。グラフ分割化のための現在の技
術は、適用分野の特性から生じるグラフ構造の特有の構
造を自動的に見つけて、活用することにおいては十分で
はない。
ンピューター・アーキテクチャー、コンピューター・ネ
ットワークの経路指定、データベース設計、そして分散
および並列処理がある。グラフ分割化のための現在の技
術は、適用分野の特性から生じるグラフ構造の特有の構
造を自動的に見つけて、活用することにおいては十分で
はない。
【０００４】特に、現代の複雑な電子システムの設計
は、動作要件に起因する構成要素や回路の設計の問題に
加え、構成要素の物理的レイアウトに関する問題が考慮
されなければならないことから複雑となる。回路構成要
素は、シャーシ、プリント回路カード、または半導体基
板などの物理的支持体上に配置されなければならず、こ
れらの支持体は各々、それが保持可能な構成要素の固有
の数と、他の支持体に接続できる端子の固有の数を有す
る。
は、動作要件に起因する構成要素や回路の設計の問題に
加え、構成要素の物理的レイアウトに関する問題が考慮
されなければならないことから複雑となる。回路構成要
素は、シャーシ、プリント回路カード、または半導体基
板などの物理的支持体上に配置されなければならず、こ
れらの支持体は各々、それが保持可能な構成要素の固有
の数と、他の支持体に接続できる端子の固有の数を有す
る。
【０００５】さらに、実際には、満たされなければなら
ない他の制約が課される。例えば、電気的または機械的
考慮は、構成要素の特定集合は同構造物上にあるべきで
あるとか、一定の構成要素は同構造物上にあるべきでな
い等の条件を課す。
ない他の制約が課される。例えば、電気的または機械的
考慮は、構成要素の特定集合は同構造物上にあるべきで
あるとか、一定の構成要素は同構造物上にあるべきでな
い等の条件を課す。
【０００６】大規模システムにおいて、特に大量生産さ
れる大規模システムにおいては、構成要素のレイアウト
の問題は解消されるだけでなく、効率的に解決されるこ
とが重要となる。異なる構造物上の構成要素を接続する
よりも同一構造物上の構成要素を接続する方がより容易
で、かつ安価となるので、その最適な解決方法は、支持
構造物間で要求される相互接続を最小限にすることであ
る。
れる大規模システムにおいては、構成要素のレイアウト
の問題は解消されるだけでなく、効率的に解決されるこ
とが重要となる。異なる構造物上の構成要素を接続する
よりも同一構造物上の構成要素を接続する方がより容易
で、かつ安価となるので、その最適な解決方法は、支持
構造物間で要求される相互接続を最小限にすることであ
る。
【０００７】問題解決におけるさらなる制約は、効率的
な解決を提供するだけでなく、それ自体効率的でなけれ
ばならないことである。すなわち、益々複雑化する電子
システムを考慮して、問題を解決する方法は、容易で、
かつ迅速にできるようなものでなければならない。これ
は、その方法が割り当てられる構成要素数、および有効
な支持構造物数の何れにも過度に依存しないことを意味
する。
な解決を提供するだけでなく、それ自体効率的でなけれ
ばならないことである。すなわち、益々複雑化する電子
システムを考慮して、問題を解決する方法は、容易で、
かつ迅速にできるようなものでなければならない。これ
は、その方法が割り当てられる構成要素数、および有効
な支持構造物数の何れにも過度に依存しないことを意味
する。
【０００８】最も一般的な分割化システムの１つが、カ
ーニガンとリン(Kernighan and Lin)による、ここで参
考に取り入れられている米国特許番号３、６１７、７１４
で説明されている。そこでのグラフのノードを集合に分
割する方法は、集合の最大数、特定の１つの集合に割り
当てることができるノードの最大数、そして何れかの集
合に行うことができるエッジ接続の最大数に関する制約
を利用する。
ーニガンとリン(Kernighan and Lin)による、ここで参
考に取り入れられている米国特許番号３、６１７、７１４
で説明されている。そこでのグラフのノードを集合に分
割する方法は、集合の最大数、特定の１つの集合に割り
当てることができるノードの最大数、そして何れかの集
合に行うことができるエッジ接続の最大数に関する制約
を利用する。
【０００９】この方法は、リンクされたノードの相互接
続のコストを最小限にするために利用され、そして近似
最適回路レイアウトの設計にだけでなく、ＶＬＳＩ回
路、ネットワーク、データベースのコンピューター支援
設計、分散および並列計算の構成、そしてディスプレー
上のグラフィック・オブジェクトのレイアウトにも有用
であることが分かっている。
続のコストを最小限にするために利用され、そして近似
最適回路レイアウトの設計にだけでなく、ＶＬＳＩ回
路、ネットワーク、データベースのコンピューター支援
設計、分散および並列計算の構成、そしてディスプレー
上のグラフィック・オブジェクトのレイアウトにも有用
であることが分かっている。
【００１０】例えば、マスター・スライスＶＬＳＩチッ
プ設計は米国特許番号４、５９３、３６３で示されるよう
に、構成要素を配置するためと、配線パターンを決定す
るための分割化技術を採用している。米国特許番号４、
５７７、２７６には、最大限の接続を行うサブセルへの
セルの分割を含む分割化手順を利用した回路基板上の構
成要素の配置のためのシステムが示されている。
プ設計は米国特許番号４、５９３、３６３で示されるよう
に、構成要素を配置するためと、配線パターンを決定す
るための分割化技術を採用している。米国特許番号４、
５７７、２７６には、最大限の接続を行うサブセルへの
セルの分割を含む分割化手順を利用した回路基板上の構
成要素の配置のためのシステムが示されている。
【００１１】最近、実際的に重要なグラフで典型的に見
られる固有構造を利用するための、より積極的な試みが
なされている。新システムの１つの種類のもので採用さ
れた一般的な試みは、クラスター化(群化)である。ノー
ドを密に接続されたサブグラフにグループ化することに
より、ノードのクラスター(群)は、カーニガン／リンの
ような標準的な方法を適用する際に個々のスーパーノー
ド(上位ノード)として扱うことができる。
られる固有構造を利用するための、より積極的な試みが
なされている。新システムの１つの種類のもので採用さ
れた一般的な試みは、クラスター化(群化)である。ノー
ドを密に接続されたサブグラフにグループ化することに
より、ノードのクラスター(群)は、カーニガン／リンの
ような標準的な方法を適用する際に個々のスーパーノー
ド(上位ノード)として扱うことができる。
【００１２】このような考えの種々の具体化が、以下の
論文で説明される。T.Bui、C.Heigham、C.Jones そして
T.Leighton、「"カーニンガム／リンのパフォーマンス
の改善と焼鈍法グラフ二分探索アルゴリズム(Improving
the Performance of the Kernighan-Lin and Simulate
d Annealing Graph Bisection Algorithms)"」、第２６
回、設計自動化会議の議事録、７７５〜７７８ページ、
１９８９年；J.CongとM.Smith、「"ＶＬＳＩ設計におけ
る回路分割化への適用での並列ボトムアップ・群化アル
ゴリズム(A Parallel Bottom-Up Clustering Algorithm
with Applications to Circuit Partitioning in VLSI
Design)"」、第３０回、ＡＣＭ／ＩＥＥＥ設計自動化
会議の議事録、７５５〜７６０ページ、１９９３年６
月。
論文で説明される。T.Bui、C.Heigham、C.Jones そして
T.Leighton、「"カーニンガム／リンのパフォーマンス
の改善と焼鈍法グラフ二分探索アルゴリズム(Improving
the Performance of the Kernighan-Lin and Simulate
d Annealing Graph Bisection Algorithms)"」、第２６
回、設計自動化会議の議事録、７７５〜７７８ページ、
１９８９年；J.CongとM.Smith、「"ＶＬＳＩ設計におけ
る回路分割化への適用での並列ボトムアップ・群化アル
ゴリズム(A Parallel Bottom-Up Clustering Algorithm
with Applications to Circuit Partitioning in VLSI
Design)"」、第３０回、ＡＣＭ／ＩＥＥＥ設計自動化
会議の議事録、７５５〜７６０ページ、１９９３年６
月。
【００１３】W.E.Donath、「"論理分割化(Logic Partit
ioning)"」B.PreasとM.Lorenzetti編集、ＶＬＳＩシス
テムの物理的自動設計(Physical Design Automation of
VLSI Systems)、６５〜８６ページ、Benjamin /Cummin
gs、１９８８年；J.Garbers, H.J. Promel,そしてA.Ste
ger,「"ＶＬＳＩ回路内の群化の発見(Finding Clusters
in VLSI Circuits)"」、コンピューター支援設計にお
けるＩＥＥＥ国際会議の議事録、５２０〜５２３ペー
ジ、１９９０年１１月；M.K.GoldbergとM.Burstein,「"
ＶＬＳＩネットワークの二分探索のための発見的解法改
良技術(Heuristic Improvement Technique for Bisecti
on of VLSI Networks)"」、コンピューター支援設計に
おけるＩＥＥＥ国際会議の議事録、１２２〜１２５ペー
ジ、１９８３年。
ioning)"」B.PreasとM.Lorenzetti編集、ＶＬＳＩシス
テムの物理的自動設計(Physical Design Automation of
VLSI Systems)、６５〜８６ページ、Benjamin /Cummin
gs、１９８８年；J.Garbers, H.J. Promel,そしてA.Ste
ger,「"ＶＬＳＩ回路内の群化の発見(Finding Clusters
in VLSI Circuits)"」、コンピューター支援設計にお
けるＩＥＥＥ国際会議の議事録、５２０〜５２３ペー
ジ、１９９０年１１月；M.K.GoldbergとM.Burstein,「"
ＶＬＳＩネットワークの二分探索のための発見的解法改
良技術(Heuristic Improvement Technique for Bisecti
on of VLSI Networks)"」、コンピューター支援設計に
おけるＩＥＥＥ国際会議の議事録、１２２〜１２５ペー
ジ、１９８３年。
【００１４】L.HagenとA.B.Kahng,「"効率的回路群化へ
の新たなアプローチ(A New Approach to Effective Cir
cuit Clustering)"」、コンピューター支援設計におけ
るＩＥＥＥ／ＡＣＭ国際会議の議事録、４２２〜４２７
ページ、１９９２年１１月；B. Krishnamurthy、「"ＶＬ
ＳＩネットワークを分割するための改良最小切断アルゴ
リズム(An Improved Min-Cut Algorithm for Partition
ing VLSI Networks)"」、コンピュータＣ−３３につい
てのＩＥＥＥ議事録、４３８〜４４６ページ、１９８４
年；T.-K.Ng, J.Oldfield,およびV. Pitchumani、「"最
小切断分割アルゴリズムの改善(Improvements of a Min
cut Partition Algorithm)"」、コンピューター支援設
計についてのＩＥＥＥ国際会議の議事録、４７０〜４７
３ページ、１９８７。
の新たなアプローチ(A New Approach to Effective Cir
cuit Clustering)"」、コンピューター支援設計におけ
るＩＥＥＥ／ＡＣＭ国際会議の議事録、４２２〜４２７
ページ、１９９２年１１月；B. Krishnamurthy、「"ＶＬ
ＳＩネットワークを分割するための改良最小切断アルゴ
リズム(An Improved Min-Cut Algorithm for Partition
ing VLSI Networks)"」、コンピュータＣ−３３につい
てのＩＥＥＥ議事録、４３８〜４４６ページ、１９８４
年；T.-K.Ng, J.Oldfield,およびV. Pitchumani、「"最
小切断分割アルゴリズムの改善(Improvements of a Min
cut Partition Algorithm)"」、コンピューター支援設
計についてのＩＥＥＥ国際会議の議事録、４７０〜４７
３ページ、１９８７。
【００１５】そしてY.-C.WeiとC.- K.Cheng,「"２レベ
ル２ウェイ分割化アルゴリズム(A Two-Level Two-Way P
artitioning Algorithm)"」、コンピューター支援設計
におけるＩＥＥＥ国際会議の議事録、５１６〜５１９ペ
ージ、１９９０年１１月。
ル２ウェイ分割化アルゴリズム(A Two-Level Two-Way P
artitioning Algorithm)"」、コンピューター支援設計
におけるＩＥＥＥ国際会議の議事録、５１６〜５１９ペ
ージ、１９９０年１１月。
【００１６】比較的最近の他の考え方は、特に焼鈍法(s
imulated annealing)として知られる技術である、当て
ずっぽのサーチ(stochastic search、以下確率的サーチ
とする)を使用するものであり、カーニガン／リン・ア
ルゴリズムよりももっと徹底的に可能な分割のスペース
を探究する。この考えは、下記の論文で検討されてい
る。
imulated annealing)として知られる技術である、当て
ずっぽのサーチ(stochastic search、以下確率的サーチ
とする)を使用するものであり、カーニガン／リン・ア
ルゴリズムよりももっと徹底的に可能な分割のスペース
を探究する。この考えは、下記の論文で検討されてい
る。
【００１７】D.S.Johnson、C.R.Aragon、L.A.McGeoch、
およびC.Schevon、「"焼鈍法による最適化：実験的評
価；パートＩ、グラフ分割化(Optimization by Simulat
ed Annealing:An Experimental Evaluation;Part I, Gr
aph Partitioning)"」、オペレーション・リサーチ(Ope
rations Research),３７（６）：８６５〜８９２ペー
ジ、１９８９年；S.Kirkpatrick,「"焼鈍法による最適
化：量的研究(Optimization by Simulated Annealing:Q
uantitative Studies)"」、統計物理学ジャーナル(Jour
nal of Statistical Physics),３４：９７５〜９８６ペ
ージ、１９８４年；そしてS.Kirkpatrick、C.D.Gelat
t、Jr.、およびM.P.Vecchi,「"焼鈍法による最適化(Opt
imization by Simulated Annealing)"」、サイエンス(S
cience)、２２０：６７１〜６８０ページ、１９８４
年。
およびC.Schevon、「"焼鈍法による最適化：実験的評
価；パートＩ、グラフ分割化(Optimization by Simulat
ed Annealing:An Experimental Evaluation;Part I, Gr
aph Partitioning)"」、オペレーション・リサーチ(Ope
rations Research),３７（６）：８６５〜８９２ペー
ジ、１９８９年；S.Kirkpatrick,「"焼鈍法による最適
化：量的研究(Optimization by Simulated Annealing:Q
uantitative Studies)"」、統計物理学ジャーナル(Jour
nal of Statistical Physics),３４：９７５〜９８６ペ
ージ、１９８４年；そしてS.Kirkpatrick、C.D.Gelat
t、Jr.、およびM.P.Vecchi,「"焼鈍法による最適化(Opt
imization by Simulated Annealing)"」、サイエンス(S
cience)、２２０：６７１〜６８０ページ、１９８４
年。
【００１８】
【発明が解決しようとする課題】これらのシステムは全
て、先の試みをある程度改善するが、オリジナルのカー
ニガン／リン・システムを含むそれらは、さらに改善さ
れる余地がある。特に、種々のクラスター(群化)システ
ムは、良好な確率的サーチによる戦略を最適に使用して
いない。そしてその確率的サーチ戦略はクラスター化の
概念を有効には利用していない。この発明は、クラスタ
ー化発見的解法と強力確率的サーチプロセスとの新規で
かつ効果的な組み合せにより与えられる機会を利用す
る。
て、先の試みをある程度改善するが、オリジナルのカー
ニガン／リン・システムを含むそれらは、さらに改善さ
れる余地がある。特に、種々のクラスター(群化)システ
ムは、良好な確率的サーチによる戦略を最適に使用して
いない。そしてその確率的サーチ戦略はクラスター化の
概念を有効には利用していない。この発明は、クラスタ
ー化発見的解法と強力確率的サーチプロセスとの新規で
かつ効果的な組み合せにより与えられる機会を利用す
る。
【００１９】以下のものは、種々の他の先のグラフ分割
化方法とシステムについて説明している。T.N.Bui, S.C
haudhuri, F.T.Leighton,およびM.Sipser,「"良好な平
均ケース行動を有するグラフ二分探索アルゴリズム(Gra
ph Bisection Algorithms with Good Average Case Beh
avior)"」、組み合わせ数学(Combinatorica)７(２)、１
７１〜１９１ページ、１９８７年；C.M.FiducciaとR.M.
Mattheyses,「"ネットワーク分割化を改善するための線
形時間発見的解法(A Linear-Time Heuristic for Impro
ving Network Partitions)"」、第１９回、設計自動化
会議の議事録、１７５〜１８１ページ、ラスベガス、ニ
ューメキシコ、１９８２年。
化方法とシステムについて説明している。T.N.Bui, S.C
haudhuri, F.T.Leighton,およびM.Sipser,「"良好な平
均ケース行動を有するグラフ二分探索アルゴリズム(Gra
ph Bisection Algorithms with Good Average Case Beh
avior)"」、組み合わせ数学(Combinatorica)７(２)、１
７１〜１９１ページ、１９８７年；C.M.FiducciaとR.M.
Mattheyses,「"ネットワーク分割化を改善するための線
形時間発見的解法(A Linear-Time Heuristic for Impro
ving Network Partitions)"」、第１９回、設計自動化
会議の議事録、１７５〜１８１ページ、ラスベガス、ニ
ューメキシコ、１９８２年。
【００２０】B.W.KernighanとS.Lin,「"グラフを分割す
るための効率的な発見的解法(An Efficient Heuristic
Procedure for Partitioning Graphs)"」、ベル・シス
テム技術ジャーナル４９(２)、２９１〜３０７、１９７
０年２月；U.Lauther,「 "グラフ表現に基づく一般的セ
ルアセンブリーのための最小切断配置アルゴリズム(A M
in-Cut Placement Algorithm for General Cell Assemb
lies Based on a Graph Representation)" 」、第１６
回、設計自動化会議の議事録、１〜１０ページ、サンデ
ィエゴ、カリフォルニア、１９７９年６月。
るための効率的な発見的解法(An Efficient Heuristic
Procedure for Partitioning Graphs)"」、ベル・シス
テム技術ジャーナル４９(２)、２９１〜３０７、１９７
０年２月；U.Lauther,「 "グラフ表現に基づく一般的セ
ルアセンブリーのための最小切断配置アルゴリズム(A M
in-Cut Placement Algorithm for General Cell Assemb
lies Based on a Graph Representation)" 」、第１６
回、設計自動化会議の議事録、１〜１０ページ、サンデ
ィエゴ、カリフォルニア、１９７９年６月。
【００２１】B.Mazlish, S.Shieber,およびJ.Marks,「"
グラフを二分探索するための反復的合体方法(A Recursi
ve Coalescing Method for Bisecting Graphs)"」、技
術レポートＴＲ−９４−１０、三菱電機リサーチ研究
所、Inc.,ケンブリッジ、マサチューセッツ、１９９４
年５月；C. SechenとA. Sangiovanni Vincentelli,「"
ティンバーウルフ 3.2:新標準セル配置と包括的経路指
定パッケージ(TimberWolf 3.2:A New Standard Cell Pl
acement and Global Routing Package)" 」、第２３
回、設計自動化会議の議事録、４３２〜４３９ページ、
１９８６年６月；そしてY.-C WeiとC.-X. Cheng,「"階
層的設計のためのレシオカット分割化(Ratio Cut Parti
tioning for Hierarchical Design)"」、コンピュータ
支援設計におけるＩＥＥＥ会報１０(７)、９１１〜９２
１ページ、１９９１年７月。
グラフを二分探索するための反復的合体方法(A Recursi
ve Coalescing Method for Bisecting Graphs)"」、技
術レポートＴＲ−９４−１０、三菱電機リサーチ研究
所、Inc.,ケンブリッジ、マサチューセッツ、１９９４
年５月；C. SechenとA. Sangiovanni Vincentelli,「"
ティンバーウルフ 3.2:新標準セル配置と包括的経路指
定パッケージ(TimberWolf 3.2:A New Standard Cell Pl
acement and Global Routing Package)" 」、第２３
回、設計自動化会議の議事録、４３２〜４３９ページ、
１９８６年６月；そしてY.-C WeiとC.-X. Cheng,「"階
層的設計のためのレシオカット分割化(Ratio Cut Parti
tioning for Hierarchical Design)"」、コンピュータ
支援設計におけるＩＥＥＥ会報１０(７)、９１１〜９２
１ページ、１９９１年７月。
【００２２】
【課題を解決するための手段】この発明によれば、電子
回路、コンピューターおよび電気通信ネットワークの良
好な設計を可能にするためのグラフ分割化のためのシス
テムが提供される。そして強力なクラスター化システム
と強力な確率的サーチシステムとを組み合わせることに
より他の用途は、シード成長発見的解法を使用してクラ
スター化を完遂し、並列ヒルクライム法を用いることに
より効率的確率的サーチを実行する。
回路、コンピューターおよび電気通信ネットワークの良
好な設計を可能にするためのグラフ分割化のためのシス
テムが提供される。そして強力なクラスター化システム
と強力な確率的サーチシステムとを組み合わせることに
より他の用途は、シード成長発見的解法を使用してクラ
スター化を完遂し、並列ヒルクライム法を用いることに
より効率的確率的サーチを実行する。
【００２３】ある１つの実施の形態において、この複合
システムにより計算された分割はカーニガン／リン・ア
ルゴリズムへの初期分割として提供され、それはこれら
の分割を更に洗練するために使用される。１つの実施の
形態においては、分割されるグラフはＣＡＤ／ＣＡＭ装
置の画面上で作成される。ＣＡＤ／ＣＡＭシステムはそ
の後、問題改善した分割化を行ない、グラフ内の要素の
最適位置を表示するのに使用される近似最適分割を供給
する。
システムにより計算された分割はカーニガン／リン・ア
ルゴリズムへの初期分割として提供され、それはこれら
の分割を更に洗練するために使用される。１つの実施の
形態においては、分割されるグラフはＣＡＤ／ＣＡＭ装
置の画面上で作成される。ＣＡＤ／ＣＡＭシステムはそ
の後、問題改善した分割化を行ない、グラフ内の要素の
最適位置を表示するのに使用される近似最適分割を供給
する。
【００２４】特に、シード成長発見的解法は最初、ラン
ダムに選ばれた小数のノードを分割の各部分に割り当て
る。これらはシードノードである。完全な分割は、少な
くとも結果として生じるカット集合のサイズ(分割のあ
る部分から別の部分までのエッジ数)に逆に影響をもた
らす分割の部分に未割り当てノードが割り当てられるよ
うに、分割の初期部分を反復的に増大させることにより
構築される。その分割を増加的に計算するためのこの基
準は、グラフ内のクラスターを暗黙のうちに発見し、そ
してクラスターが分割の異なる部分間で滅多に分裂しな
いことを保証し、それは典型的により大きなカット集合
となる。
ダムに選ばれた小数のノードを分割の各部分に割り当て
る。これらはシードノードである。完全な分割は、少な
くとも結果として生じるカット集合のサイズ(分割のあ
る部分から別の部分までのエッジ数)に逆に影響をもた
らす分割の部分に未割り当てノードが割り当てられるよ
うに、分割の初期部分を反復的に増大させることにより
構築される。その分割を増加的に計算するためのこの基
準は、グラフ内のクラスターを暗黙のうちに発見し、そ
してクラスターが分割の異なる部分間で滅多に分裂しな
いことを保証し、それは典型的により大きなカット集合
となる。
【００２５】シード成長発見的解法は、シードノードの
ランダム選択に依存するので、ランダムとなる。確率的
サーチプロセスは使用するシードノードの良好な集合を
探す。これは、同時に幾つかのランダムに選ばれたシー
ドノードの集合を考慮することにより達成される。シー
ドノードの各集合はシードノードの代りに非シードノー
ドを用いることによるランダム摂動(perturbations)に
さらされる。結果として生じる分割を改善する摂動は保
持される。さもなければそれらは無効にされる。これ
は、シードノードの幾つかの集合に同時に適用されるよ
うな、ヒルクライムの公知のサーチ戦略である。
ランダム選択に依存するので、ランダムとなる。確率的
サーチプロセスは使用するシードノードの良好な集合を
探す。これは、同時に幾つかのランダムに選ばれたシー
ドノードの集合を考慮することにより達成される。シー
ドノードの各集合はシードノードの代りに非シードノー
ドを用いることによるランダム摂動(perturbations)に
さらされる。結果として生じる分割を改善する摂動は保
持される。さもなければそれらは無効にされる。これ
は、シードノードの幾つかの集合に同時に適用されるよ
うな、ヒルクライムの公知のサーチ戦略である。
【００２６】さらに、シードノードの最も見込みのない
集合は、シードノードの最も見込みのある集合の複製コ
ピーと定期的に取り替えられる。このサーチプロセス
は、所定の数の摂動が考慮された後に終了し、そして見
いだされた最良の分割の幾つかがさらに洗練されるため
のカーニガン／リン・アルゴリズムへの入力として渡さ
れる。それで最良の洗練された分割が最終の解決案とし
て戻される。
集合は、シードノードの最も見込みのある集合の複製コ
ピーと定期的に取り替えられる。このサーチプロセス
は、所定の数の摂動が考慮された後に終了し、そして見
いだされた最良の分割の幾つかがさらに洗練されるため
のカーニガン／リン・アルゴリズムへの入力として渡さ
れる。それで最良の洗練された分割が最終の解決案とし
て戻される。
【００２７】シード成長発見的解法と確率的サーチプロ
セス、そしてカーニガン／リン・アルゴリズムとのこの
結合は、グラフを分割するための優れたシステムを構成
する。産業標準ＶＬＳＩ回路から得られる多数のグラフ
について、この発明のシステムの機能、功績をカーニガ
ン／リンの方法のそれと比較することを目的とする実験
において、この発明のシステムは幾つかのグラフに対し
てカーニガン／リンの方法を超える４５％の改善まで達
成した。そしてテストされたグラフの全てにおいて優勢
を証明した。
セス、そしてカーニガン／リン・アルゴリズムとのこの
結合は、グラフを分割するための優れたシステムを構成
する。産業標準ＶＬＳＩ回路から得られる多数のグラフ
について、この発明のシステムの機能、功績をカーニガ
ン／リンの方法のそれと比較することを目的とする実験
において、この発明のシステムは幾つかのグラフに対し
てカーニガン／リンの方法を超える４５％の改善まで達
成した。そしてテストされたグラフの全てにおいて優勢
を証明した。
【００２８】
【発明の実施の形態】以下、この発明によるグラフ分割
化システムの具体的な実施の形態について説明する。な
お、この発明のグラフ分割化システムはマイクロコンピ
ュータ等からなる情報処理装置を含み、以下の動作は基
本的にプログラムに従ったこの情報処理装置(共に図示
せず)の制御により行われる。
化システムの具体的な実施の形態について説明する。な
お、この発明のグラフ分割化システムはマイクロコンピ
ュータ等からなる情報処理装置を含み、以下の動作は基
本的にプログラムに従ったこの情報処理装置(共に図示
せず)の制御により行われる。
【００２９】図１はこの発明の１つの実施の形態による
グラフ分割化システムで行われるプロセス１０を示す。
このプロセス１０は、コンピューターチップのレイアウ
トと製造で利用される。一般に、まずブロック１２で例
示されるように、回路仕様が入力され、ブロック１４で
のモジュールへの回路の分割化を可能にする。分割化後
に、レイアウトが計算され、最適、または近似最適モジ
ュール分割化に従ってブロック１６に示すようにチップ
レイアウトが行われる。その後、ブロック１８で示され
るように、そのチップはレイアウトステップで指定され
たレイアウトに従って製造される。
グラフ分割化システムで行われるプロセス１０を示す。
このプロセス１０は、コンピューターチップのレイアウ
トと製造で利用される。一般に、まずブロック１２で例
示されるように、回路仕様が入力され、ブロック１４で
のモジュールへの回路の分割化を可能にする。分割化後
に、レイアウトが計算され、最適、または近似最適モジ
ュール分割化に従ってブロック１６に示すようにチップ
レイアウトが行われる。その後、ブロック１８で示され
るように、そのチップはレイアウトステップで指定され
たレイアウトに従って製造される。
【００３０】最適、または近似最適分割が達成される程
度は、多数のファクタに依存する。上述のように、カー
ニガン／リン分割化アルゴリズムは、初期分割、特にラ
ンダムに発生されるものを改善する。カーニガン／リン
分割化システムは、特に異なるランダム初期分割で何度
も走らせるならば有用な結果を与えるが、それは必ずし
も最も効率的で、また最良の結果を生成するとは限らな
い。
度は、多数のファクタに依存する。上述のように、カー
ニガン／リン分割化アルゴリズムは、初期分割、特にラ
ンダムに発生されるものを改善する。カーニガン／リン
分割化システムは、特に異なるランダム初期分割で何度
も走らせるならば有用な結果を与えるが、それは必ずし
も最も効率的で、また最良の結果を生成するとは限らな
い。
【００３１】従来、カーニガン／リン・アルゴリズムに
より達成された結果は、洗練された初期分割に到達する
ためにオリジナル回路グラフの慎重な予備処理により多
少改善された。しかしながら、発見的解法(最終結果に
至るまで試行錯誤を繰り返し評価することで解法を発見
する)を予備処理することは、確率的サーチを十分に利
用しておらず、それは複雑なサーチスペースを検討する
ためのランダム化されたプロセスに属する。
より達成された結果は、洗練された初期分割に到達する
ためにオリジナル回路グラフの慎重な予備処理により多
少改善された。しかしながら、発見的解法(最終結果に
至るまで試行錯誤を繰り返し評価することで解法を発見
する)を予備処理することは、確率的サーチを十分に利
用しておらず、それは複雑なサーチスペースを検討する
ためのランダム化されたプロセスに属する。
【００３２】それ自体で、またはカーニガン／リン・ア
ルゴリズムと関連して使用される、この発明における予
備処理における発見的解法(heuristic)は、特殊なシー
ド成長発見的解法(seed-growth heuristic)と特殊な確
率的サーチプロセス(stochastic search process)とを
組み合せることを含む。
ルゴリズムと関連して使用される、この発明における予
備処理における発見的解法(heuristic)は、特殊なシー
ド成長発見的解法(seed-growth heuristic)と特殊な確
率的サーチプロセス(stochastic search process)とを
組み合せることを含む。
【００３３】図４に関して後述されるように、特殊なシ
ード成長発見的解法は、分割による２つの半分をシード
するために、ランダムな少部分のグラフノードの選択に
基づく。これには反復的成長プロセスが後に伴い、そこ
で分割の最初に半分にされた部分は、その分割が完了す
るまで一度に１ノード増加される。完了時に、その分割
はその特質を決定するために調べられ、それは、分割の
一方の部分のノードを他方の部分のノードに接続するエ
ッジ、またはリンクの数により決定されるように、カッ
ト集合のサイズにより測定される。
ード成長発見的解法は、分割による２つの半分をシード
するために、ランダムな少部分のグラフノードの選択に
基づく。これには反復的成長プロセスが後に伴い、そこ
で分割の最初に半分にされた部分は、その分割が完了す
るまで一度に１ノード増加される。完了時に、その分割
はその特質を決定するために調べられ、それは、分割の
一方の部分のノードを他方の部分のノードに接続するエ
ッジ、またはリンクの数により決定されるように、カッ
ト集合のサイズにより測定される。
【００３４】図５に関して後述されるように、上記シー
ド成長発見的解法は、特殊な確率的サーチプロセスと組
み合わされる。それはサーチスペース内の数点の並列調
査を含む。
ド成長発見的解法は、特殊な確率的サーチプロセスと組
み合わされる。それはサーチスペース内の数点の並列調
査を含む。
【００３５】図２において、一般に、グラフ２０はノー
ド２２とエッジ２４とから構成される。いかなる分割化
システムの目標も、点線２６で例示されるようにグラフ
を２つの等しいサイズの集合に分割することであり、そ
れで分割の一方の部分から他方の部分までのエッジ数
(カット集合のサイズ)が最小限にされる。
ド２２とエッジ２４とから構成される。いかなる分割化
システムの目標も、点線２６で例示されるようにグラフ
を２つの等しいサイズの集合に分割することであり、そ
れで分割の一方の部分から他方の部分までのエッジ数
(カット集合のサイズ)が最小限にされる。
【００３６】図２に例示された分割は、４のカット集合
サイズを有するが、これは最適ではなく、３のカット集
合サイズの分割が達成可能である。グラフ分割化問題
は、集合Ｎが等しい基数(集合の要素の個数を表す数)の
ｋ個の部分集合に分割され、Ｅの各エッジには重みが割
り当てられるグラフ２分探索問題の一般化であるり、今
その目標は異なる部分集合のノード間のエッジの重み付
け合計を最小限にすることとなる。
サイズを有するが、これは最適ではなく、３のカット集
合サイズの分割が達成可能である。グラフ分割化問題
は、集合Ｎが等しい基数(集合の要素の個数を表す数)の
ｋ個の部分集合に分割され、Ｅの各エッジには重みが割
り当てられるグラフ２分探索問題の一般化であるり、今
その目標は異なる部分集合のノード間のエッジの重み付
け合計を最小限にすることとなる。
【００３７】先の分割化時に発見的解法を改善するため
に、図３に示すように、この発明のシステムでは、未分
割グラフ３０は入力として利用される。３２に示される
ように、シード成長発見的解法および確率的サーチが、
初期グラフ分割３４を行うために未分割グラフに施され
る。この初期グラフ分割は、分割化の目的のためにそれ
自体およびそれ自体に関して使用されるか、またはカー
ニガン／リン・アルゴリズム３６への入力として選択的
に使用されても良い。それは標準アルゴリズムに従って
初期分割をさらに洗練させる。その結果は最終グラフ分
割３８であり、それは一般に他の技術により生成される
これらよりも優れている。
に、図３に示すように、この発明のシステムでは、未分
割グラフ３０は入力として利用される。３２に示される
ように、シード成長発見的解法および確率的サーチが、
初期グラフ分割３４を行うために未分割グラフに施され
る。この初期グラフ分割は、分割化の目的のためにそれ
自体およびそれ自体に関して使用されるか、またはカー
ニガン／リン・アルゴリズム３６への入力として選択的
に使用されても良い。それは標準アルゴリズムに従って
初期分割をさらに洗練させる。その結果は最終グラフ分
割３８であり、それは一般に他の技術により生成される
これらよりも優れている。
【００３８】本アルゴリズムは以下のシード成長発見的
解法に基づく： 入力： 無管理グラフＧ＝(Ｎ、Ｅ)。 Ｎ内のノード数、IＮIは偶数とする。 出力：サイズIＮI／２の２つの部分集合ＸとＹへのＮの
分割、およびＸ内のノードからＹ内のノードまでのエッ
ジ数であるカット集合のサイズ。
解法に基づく： 入力： 無管理グラフＧ＝(Ｎ、Ｅ)。 Ｎ内のノード数、IＮIは偶数とする。 出力：サイズIＮI／２の２つの部分集合ＸとＹへのＮの
分割、およびＸ内のノードからＹ内のノードまでのエッ
ジ数であるカット集合のサイズ。
【００３９】手順： １．Ｎ内のノードの１％を部分集合Ｘに、そして１％を
部分集合Ｙにランダムに割り当てる。これらのノードは
ＸとＹの各々のシードである。 ２．Ｎ内の全てのノードがＸまたはＹに割り当てられる
までサブステップＡとＢを反復する： Ａ．Ｘに関する最大差の値を有するＮ内の未割り当ての
頂点ａを見つける：この値は、ａからすでにＸに割り当
てられたノードまでのエッジ数から、ａからすでにＹに
割り当てられたノードまでのエッジ数を減算した値であ
る。(もし最大差の値を有する頂点が２つ以上あれば、
それらの１つを任意に選ぶ。)頂点ａをＸに割り当て
る。 Ｂ．Ｙに関する最大差の値を有するＮ内の未割り当ての
節点ｂを見つける：この値は、ｂからすでにＹに割り当
てられたノードまでのエッジ数から、ｂからすでにＸに
割り当てられたノードまでのエッジ数を減算した値であ
る。(もし最大差の値を有する頂点が２つ以上あれば、
それらの１つを任意に選ぶ。)節点ｂをＹに割り当て
る。 ３．Ｘ内のノードをＹ内のノードに接続するエッジ数を
計算する(これはカット集合のサイズである)。
部分集合Ｙにランダムに割り当てる。これらのノードは
ＸとＹの各々のシードである。 ２．Ｎ内の全てのノードがＸまたはＹに割り当てられる
までサブステップＡとＢを反復する： Ａ．Ｘに関する最大差の値を有するＮ内の未割り当ての
頂点ａを見つける：この値は、ａからすでにＸに割り当
てられたノードまでのエッジ数から、ａからすでにＹに
割り当てられたノードまでのエッジ数を減算した値であ
る。(もし最大差の値を有する頂点が２つ以上あれば、
それらの１つを任意に選ぶ。)頂点ａをＸに割り当て
る。 Ｂ．Ｙに関する最大差の値を有するＮ内の未割り当ての
節点ｂを見つける：この値は、ｂからすでにＹに割り当
てられたノードまでのエッジ数から、ｂからすでにＸに
割り当てられたノードまでのエッジ数を減算した値であ
る。(もし最大差の値を有する頂点が２つ以上あれば、
それらの１つを任意に選ぶ。)節点ｂをＹに割り当て
る。 ３．Ｘ内のノードをＹ内のノードに接続するエッジ数を
計算する(これはカット集合のサイズである)。
【００４０】図４に示されるように、より一般的には、
上記アルゴリズムは図４の４０に示されるように、ノー
ドとこれらのノードを接続するエッジとから構成される
グラフがランダムに少部分のノードを選択するためのデ
ータを提供することに注目して表現される。４２で示さ
れるように、１％のノードはシードノードとして、Ｘと
呼ばれる、分割の半分に割り当てられ、４４で示される
ように、ノードの他の互いに共通元を持たない１％は、
Ｙと呼ばれる、分割の他方の半分のためのシードノード
として選択される。
上記アルゴリズムは図４の４０に示されるように、ノー
ドとこれらのノードを接続するエッジとから構成される
グラフがランダムに少部分のノードを選択するためのデ
ータを提供することに注目して表現される。４２で示さ
れるように、１％のノードはシードノードとして、Ｘと
呼ばれる、分割の半分に割り当てられ、４４で示される
ように、ノードの他の互いに共通元を持たない１％は、
Ｙと呼ばれる、分割の他方の半分のためのシードノード
として選択される。
【００４１】４６で示されるように、すでにＸ内のノー
ドに最大限に接続され、そしてすでにＹ内のノードに最
小限に接続される未割り当てノードは選択されて、Ｘに
割り当てられ、４８で示されるように、同じことがＹに
対する他の未割り当てノードにも行われる。
ドに最大限に接続され、そしてすでにＹ内のノードに最
小限に接続される未割り当てノードは選択されて、Ｘに
割り当てられ、４８で示されるように、同じことがＹに
対する他の未割り当てノードにも行われる。
【００４２】反復的プロセスは、５０で示されるよう
に、全ての未割り当てノードがＸまたはＹに割り当てら
れるまで続く。これが完了すると、５２で示されるよう
に、カット集合のサイズとして定義される、Ｘ内のノー
ドをＹ内のノードに接続するエッジ数が決定される。５
４で示されるように、結果として生じる分割とカット集
合のサイズは、本システムのシード成長発見的解法部分
の最終出力となる。
に、全ての未割り当てノードがＸまたはＹに割り当てら
れるまで続く。これが完了すると、５２で示されるよう
に、カット集合のサイズとして定義される、Ｘ内のノー
ドをＹ内のノードに接続するエッジ数が決定される。５
４で示されるように、結果として生じる分割とカット集
合のサイズは、本システムのシード成長発見的解法部分
の最終出力となる。
【００４３】シード成長発見的解法のある適用は、適度
に有用なグラフ２分探索を計算するが、本当に効果的と
なるためには、シード成長発見的解法は後処理としてカ
ーニガン／リン発見的解法を含む一般的サーチ手順の一
部として、複数回走らせられなければならない。そのよ
うなサーチ手順の一例がここにある。ランダム発生／テ
スト、ヒルクライミング、焼鈍法、そして遺伝子アルゴ
リズムなどの他の確率的サーチ手順はこの発明の範囲内
にあり、かつシード成長とカーニガン／リン発見的解法
と縦並びで効果的に使用されても良い。
に有用なグラフ２分探索を計算するが、本当に効果的と
なるためには、シード成長発見的解法は後処理としてカ
ーニガン／リン発見的解法を含む一般的サーチ手順の一
部として、複数回走らせられなければならない。そのよ
うなサーチ手順の一例がここにある。ランダム発生／テ
スト、ヒルクライミング、焼鈍法、そして遺伝子アルゴ
リズムなどの他の確率的サーチ手順はこの発明の範囲内
にあり、かつシード成長とカーニガン／リン発見的解法
と縦並びで効果的に使用されても良い。
【００４４】シード成長発見的解法は、以下で説明され
る特殊な確率的サーチプロセスなどの確率的サーチプロ
セスとで最も効果的に使用されることが理解されよう。 入力： 無管理グラフＧ＝(Ｎ、Ｅ)。 IＮIは偶数とする。 出力：サイズIＮI／２の２つの部分集合ＸとＹへの分
割、およびカット集合のサイズ。
る特殊な確率的サーチプロセスなどの確率的サーチプロ
セスとで最も効果的に使用されることが理解されよう。 入力： 無管理グラフＧ＝(Ｎ、Ｅ)。 IＮIは偶数とする。 出力：サイズIＮI／２の２つの部分集合ＸとＹへの分
割、およびカット集合のサイズ。
【００４５】手順： １．シード成長手順のステップ１を用いて、１００のシ
ードの集合から集合Ｐをランダムに選ぶ。 ２．シード成長手順のステップ１と３とを用いて、Ｐの
各要素ｓの部分集合ＸｓとＹｓ、および対応するカット
集合の値とを計算する。
ードの集合から集合Ｐをランダムに選ぶ。 ２．シード成長手順のステップ１と３とを用いて、Ｐの
各要素ｓの部分集合ＸｓとＹｓ、および対応するカット
集合の値とを計算する。
【００４６】３．サブステップＡからＥを５０００回反
復する： Ａ．Ｐ内のシード集合ｓをランダムに選ぶ。 Ｂ．そのシードの一つを取り除いて、Ｎからランダムに
選ばれた別のシード頂点(ノード)と取り替えることによ
りｓを摂動する；結果として生じるシード集合ｓ’を呼
び出す。 Ｃ．ｓ’に対する部分集合Ｘｓ’とＹｓ’およびカット
集合とを計算する。 Ｄ．もしもｓ’のカット集合がｓのカット集合よりも小
さいならば、Ｐ内のｓをｓ’と取り替える。 Ｅ．反復時に、１０００、２０００、３０００、そして
４０００回と、以下のステップを実行する： ｉ．カット集合のサイズでＰの要素を順序付ける。 ii．Ｐの最下位５０要素をＰの上位５０要素のコピーと
取り替える。
復する： Ａ．Ｐ内のシード集合ｓをランダムに選ぶ。 Ｂ．そのシードの一つを取り除いて、Ｎからランダムに
選ばれた別のシード頂点(ノード)と取り替えることによ
りｓを摂動する；結果として生じるシード集合ｓ’を呼
び出す。 Ｃ．ｓ’に対する部分集合Ｘｓ’とＹｓ’およびカット
集合とを計算する。 Ｄ．もしもｓ’のカット集合がｓのカット集合よりも小
さいならば、Ｐ内のｓをｓ’と取り替える。 Ｅ．反復時に、１０００、２０００、３０００、そして
４０００回と、以下のステップを実行する： ｉ．カット集合のサイズでＰの要素を順序付ける。 ii．Ｐの最下位５０要素をＰの上位５０要素のコピーと
取り替える。
【００４７】４．関連カット集合のサイズに従ってＰ内
のシード集合を順位付ける。 ５．Ｐ内の上位２０の内の各シード集合ｔに対して、カ
ーニガン／リン発見的解法を分割(Ｘｒ、Ｙｔ)に適用し
て、改善された分割(Ｘｔ’、Ｙｔ’)を得る(可能なら
ば)。 ６．２０の改善した分割を順序付けて、最小カット集合
を有する一つの分割を返す。
のシード集合を順位付ける。 ５．Ｐ内の上位２０の内の各シード集合ｔに対して、カ
ーニガン／リン発見的解法を分割(Ｘｒ、Ｙｔ)に適用し
て、改善された分割(Ｘｔ’、Ｙｔ’)を得る(可能なら
ば)。 ６．２０の改善した分割を順序付けて、最小カット集合
を有する一つの分割を返す。
【００４８】図５および図６に示すように、１つの実施
の形態においては、図４の上述のシード成長発見的解法
は、６０で示されるように、シードノードの多数の集
合、初期分割、そしてそれらの対応するカット集合サイ
ズとを発生するために利用される。６２で示されるよう
に、その結果は、シードノードの集合の一つを選び出す
ためのランダム選択プロセス６４で利用される。図示さ
れるているように、シードノードの１００の集合が利用
されるが、シード集合の数はこれに限られたものではな
い。
の形態においては、図４の上述のシード成長発見的解法
は、６０で示されるように、シードノードの多数の集
合、初期分割、そしてそれらの対応するカット集合サイ
ズとを発生するために利用される。６２で示されるよう
に、その結果は、シードノードの集合の一つを選び出す
ためのランダム選択プロセス６４で利用される。図示さ
れるているように、シードノードの１００の集合が利用
されるが、シード集合の数はこれに限られたものではな
い。
【００４９】シードノードの１つの集合を選んだ後に、
６６で示されるように、ノードのこの集合の構成が、グ
ラフ内の非シードノードを現在のシードノードの１つと
ランダムに取り替えることにより修正される。シードノ
ードの集合への修正は、その交換がカット集合サイズの
改善となるかどうかを確認するために、これに関連した
分割とカット集合サイズの再計算を必要とする。これは
６８と７０とで示される。もし何の改善もなければ、劣
っているカット集合サイズとなる交換は無視されること
は理解されよう。
６６で示されるように、ノードのこの集合の構成が、グ
ラフ内の非シードノードを現在のシードノードの１つと
ランダムに取り替えることにより修正される。シードノ
ードの集合への修正は、その交換がカット集合サイズの
改善となるかどうかを確認するために、これに関連した
分割とカット集合サイズの再計算を必要とする。これは
６８と７０とで示される。もし何の改善もなければ、劣
っているカット集合サイズとなる交換は無視されること
は理解されよう。
【００５０】７２で示されるように、ステップ６４〜７
０までの１０００回の反復毎に、７４で示されるよう
に、１００の分割が分類される。それでシードノードの
下位５０の集合は、７６で示されるように、それらの関
連する分割と計算されたカット集合サイズと供に、シー
ドノードの上位５０の集合のコピーと取り替えられる。
この操作は、再シード化と呼ばれる。
０までの１０００回の反復毎に、７４で示されるよう
に、１００の分割が分類される。それでシードノードの
下位５０の集合は、７６で示されるように、それらの関
連する分割と計算されたカット集合サイズと供に、シー
ドノードの上位５０の集合のコピーと取り替えられる。
この操作は、再シード化と呼ばれる。
【００５１】７８で示されるように、このプロセス(ス
テップ６４〜７８)は、１００の優れた分割に到達する
ように、５０００回、または適当な回数を反復して実行
される。８０で示されるように、これらの分割はカット
集合サイズに関して分類され、カーニガン／リン・アル
ゴリズムによる処理を８２で受けた２０の最良分割を得
る。その後、８４で示されるように、カーニガン／リン
・アルゴリズムによる処理後に、これらの２０の最良分
割は、カット集合サイズに関する全体の最良分割を選ぶ
ために分析される。その選択された分割は、見いだされ
た最良グラフ分割化解決案として８６で示されるように
返される。
テップ６４〜７８)は、１００の優れた分割に到達する
ように、５０００回、または適当な回数を反復して実行
される。８０で示されるように、これらの分割はカット
集合サイズに関して分類され、カーニガン／リン・アル
ゴリズムによる処理を８２で受けた２０の最良分割を得
る。その後、８４で示されるように、カーニガン／リン
・アルゴリズムによる処理後に、これらの２０の最良分
割は、カット集合サイズに関する全体の最良分割を選ぶ
ために分析される。その選択された分割は、見いだされ
た最良グラフ分割化解決案として８６で示されるように
返される。
【００５２】元々選択されたノードのパーセンテージ、
シードノードの集合数、確率的サーチプロセスの反復
数、再シード化操作間の間隔、そしてカーニガン／リン
・アルゴリズムを受ける分割数はこの発明には重要では
ないことは理解されよう。必要なのは、与えられたグラ
フの複雑さと有効計算資源に可能な限り近い最適な結果
を提供するのに十分な数のノード、集合、そして反復、
そして十分な大きさの再シード化の回数(頻度)を選択す
ることである。
シードノードの集合数、確率的サーチプロセスの反復
数、再シード化操作間の間隔、そしてカーニガン／リン
・アルゴリズムを受ける分割数はこの発明には重要では
ないことは理解されよう。必要なのは、与えられたグラ
フの複雑さと有効計算資源に可能な限り近い最適な結果
を提供するのに十分な数のノード、集合、そして反復、
そして十分な大きさの再シード化の回数(頻度)を選択す
ることである。
【００５３】上記シード成長発見的解法とサーチ手順は
一般のグラフ分割化問題に容易に一般化され、これはＮ
が任意の数の等しいサイズに作られた部分集合に分割さ
れることを要求し、そして任意の重みをＥ内のエッジと
結びつける。シード成長発見的解法の一般的バージョン
は、各部分集合へのシードの初期割当と、並列での部分
集合の全ての次の成長とを必要とする。カット集合サイ
ズの計算は分割内の部分集合の全てのペアー間のエッジ
の重み付け合計を必要とし、他の全てにおいて、シード
成長発見的解法とサーチ手順は不変である。
一般のグラフ分割化問題に容易に一般化され、これはＮ
が任意の数の等しいサイズに作られた部分集合に分割さ
れることを要求し、そして任意の重みをＥ内のエッジと
結びつける。シード成長発見的解法の一般的バージョン
は、各部分集合へのシードの初期割当と、並列での部分
集合の全ての次の成長とを必要とする。カット集合サイ
ズの計算は分割内の部分集合の全てのペアー間のエッジ
の重み付け合計を必要とし、他の全てにおいて、シード
成長発見的解法とサーチ手順は不変である。
【００５４】例えば部分集合が異なる幾つかのサイズ限
度を有する、または分割の幾つかの部分集合の集合条
件、要素数を任意に抑制するグラフ分割化問題のさらに
一般的なバージョンへの上述の技術のさらに率直な拡張
はこの発明の範囲内にある。
度を有する、または分割の幾つかの部分集合の集合条
件、要素数を任意に抑制するグラフ分割化問題のさらに
一般的なバージョンへの上述の技術のさらに率直な拡張
はこの発明の範囲内にある。
【００５５】この発明の幾つかの形態を説明してきた
が、修正や変形はこの発明の範囲内で実施可能であるこ
とは当業者には思い付くことである。故に、この発明の
範囲は特許請求の範囲にある。
が、修正や変形はこの発明の範囲内で実施可能であるこ
とは当業者には思い付くことである。故に、この発明の
範囲は特許請求の範囲にある。
【図１】 この発明による回路をモジュールに分割する
ための分割化サブプロセスを利用したコンピューターチ
ップを設計および製造するためのプロセスを示するブロ
ック図である。
ための分割化サブプロセスを利用したコンピューターチ
ップを設計および製造するためのプロセスを示するブロ
ック図である。
【図２】 この発明によるノードの集合とエッジまたは
リンクの集合を含むグラフの分割化を示す図である。
リンクの集合を含むグラフの分割化を示す図である。
【図３】 最終グラフ分割を提供するために、シード成
長発見的解法と確率的サーチプロセスとの組合わせによ
り計算された初期グラフ分割へのカーニガン／リン・ア
ルゴリズムの適用を選択的に伴う、特殊な確率的サーチ
プロセスと組み合わせた特殊なシード成長発見的解法を
利用して未分割化グラフを分割するためのこの発明によ
るプロセスを示すブロック図である。
長発見的解法と確率的サーチプロセスとの組合わせによ
り計算された初期グラフ分割へのカーニガン／リン・ア
ルゴリズムの適用を選択的に伴う、特殊な確率的サーチ
プロセスと組み合わせた特殊なシード成長発見的解法を
利用して未分割化グラフを分割するためのこの発明によ
るプロセスを示すブロック図である。
【図４】 初期グラフ分割がランダムに選ばれたシード
ノードの初期集合を増大させることにより形成されるこ
の発明によるシード成長発見的解法を示すブロック図で
ある。
ノードの初期集合を増大させることにより形成されるこ
の発明によるシード成長発見的解法を示すブロック図で
ある。
【図５】 この発明による、カーニガン／リン・アルゴ
リズムの適用により後に洗練される、初期グラフ分割を
発生するためのシード成長発見的解法と確率的サーチプ
ロセスとの組合わせを示すブロック図である。
リズムの適用により後に洗練される、初期グラフ分割を
発生するためのシード成長発見的解法と確率的サーチプ
ロセスとの組合わせを示すブロック図である。
【図６】 図５に続くブロック図である。
１０ プロセス、２０ グラフ、２２ ノード、２４
エッジ。
エッジ。
フロントページの続き (71)出願人 595151497 201 ＢＲＯＡＤＷＡＹ， ＣＡＭＢＲＩ ＤＧＥ， ＭＡＳＳＡＣＨＵＳＥＴＴＳ 02139， Ｕ．Ｓ．Ａ.
Claims (4)
- 【請求項１】 最小カットサイズを有する分割によって
ノードとエッジの最適配置を提供する、上記エッジによ
り結合された上記ノードを有するグラフを分割するため
のシステムにおいて、 未分割グラフからの初期グラフ分割を行うシード成長発
見的解法を含む手段であって、上記初期分割の一方の半
分のための上記未分割グラフの多数のノードと、上記初
期分割の他方の半分のための上記未分割グラフの互いに
共通元を持たないノード数と、を選択するための手段、
すでに半分であるノード群への未割り当てノードの最大
接続に基づく上記半分の各々に対して上記未分割グラフ
の未割り当てノードを反復的に選択し、それにより初期
分割を生成する手段、および上記初期分割のカットサイ
ズを確認する手段を含ものと、 上記初期分割について確率的サーチを実行する手段と、 からなることを特徴とするグラフ分割化システム。 - 【請求項２】 上記確率的サーチ手段は：対応する複数
の初期分割に基づくシードノードの多数の集合を発生す
るための上記反復的選択手段に結合された手段、 シードノードの上記集合の一つをランダムに選択する手
段、 上記選択されたシードノード集合内のシードノードの１
つを非シードノードと交換し、そしてこれに対応する分
割と、対応するカット集合サイズとを再計算する手段
と、 結果として生じる分割のカットサイズが上記交換なしの
分割のそれよりも大きいならば上記非シードノードを有
する集合を無視する手段と、 を含むことを特徴とする請求項１に記載のグラフ分割化
システム。 - 【請求項３】 シードノードの上記集合の１つを反復的
にランダムに選択し、上記選択されたシードノード集合
内のシードノードの上記集合の１つを非シードノードと
取り替え、これに対応する分割と、対応するカット集合
サイズとを再計算し、そして上記対応する分割のカット
サイズが上記交換なしでの分割のものよりも大きけれ
ば、上記非シードノードを有する集合を無視する手段を
さらに含むことを特徴とする請求項２に記載のグラフ分
割化システム。 - 【請求項４】 上記確率的サーチの結果についてカーニ
ガン／リン分割を行なう手段をさらに含むことを特徴と
する請求項１に記載のグラフ分割化システム。
Applications Claiming Priority (2)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| US08/333,728 US5748844A (en) | 1994-11-03 | 1994-11-03 | Graph partitioning system |
| US08/333728 | 1994-11-03 |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| JPH08212249A true JPH08212249A (ja) | 1996-08-20 |
| JP2719509B2 JP2719509B2 (ja) | 1998-02-25 |
Family
ID=23304011
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP7285249A Expired - Lifetime JP2719509B2 (ja) | 1994-11-03 | 1995-11-01 | グラフ分割化システム |
Country Status (2)
| Country | Link |
|---|---|
| US (1) | US5748844A (ja) |
| JP (1) | JP2719509B2 (ja) |
Cited By (4)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US6564367B1 (en) | 1999-07-22 | 2003-05-13 | Hitachi, Ltd. | Logic dividing method, logic dividing system and recording medium for storing logic dividing program |
| JP2007299138A (ja) * | 2006-04-28 | 2007-11-15 | Hewlett-Packard Development Co Lp | 信頼ネットワークグラフの信頼値計算装置・方法・プログラム |
| JP2009258794A (ja) * | 2008-04-11 | 2009-11-05 | Fujitsu Ltd | 情報検索プログラム、情報検索装置、および情報検索方法 |
| JP2016091504A (ja) * | 2014-11-11 | 2016-05-23 | 富士通株式会社 | 情報提示方法、情報提示装置、及びプログラム |
Families Citing this family (35)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| RU2096824C1 (ru) * | 1996-04-29 | 1997-11-20 | Государственный научно-технический центр гиперинформационных технологий | Способы автоматизированной обработки информационных материалов для персонализированного использования |
| US7047162B1 (en) * | 1996-11-18 | 2006-05-16 | Siemens Aktiengesellschaft | Computer assisted method for partitioning an electric circuit |
| US6437804B1 (en) * | 1997-10-23 | 2002-08-20 | Aprisma Management Technologies, Inc | Method for automatic partitioning of node-weighted, edge-constrained graphs |
| US6175957B1 (en) * | 1997-12-09 | 2001-01-16 | International Business Machines Corporation | Method of, system for, and computer program product for providing efficient utilization of memory hierarchy through code restructuring |
| US6065063A (en) * | 1998-01-29 | 2000-05-16 | International Business Machines Corp. | Deadlock avoidance method in a computer network |
| US6442743B1 (en) * | 1998-06-12 | 2002-08-27 | Monterey Design Systems | Placement method for integrated circuit design using topo-clustering |
| US6594624B1 (en) | 1999-06-22 | 2003-07-15 | The United States Of America As Represented By The National Security Agency | Method of identifying all minimum-cost cutsets in a network |
| US7212201B1 (en) | 1999-09-23 | 2007-05-01 | New York University | Method and apparatus for segmenting an image in order to locate a part thereof |
| US7466663B2 (en) * | 2000-10-26 | 2008-12-16 | Inrotis Technology, Limited | Method and apparatus for identifying components of a network having high importance for network integrity |
| GB0225109D0 (en) * | 2002-10-29 | 2002-12-11 | Univ Newcastle | Method of and apparatus for identifying components of a network having high importance for network integrity |
| US6978458B1 (en) * | 2000-11-17 | 2005-12-20 | Oracle International Corporation | Distributing data items to corresponding buckets for use in parallel operations |
| US7139992B2 (en) * | 2000-12-01 | 2006-11-21 | Sun Microsystems, Inc. | Short path search using tiles and piecewise linear cost propagation |
| US20020104061A1 (en) * | 2000-12-01 | 2002-08-01 | Sun Microsystems, Inc. | Systems and methods for linear minimal convolution |
| US6888960B2 (en) | 2001-03-28 | 2005-05-03 | Nec Corporation | Fast optimal linear approximation of the images of variably illuminated solid objects for recognition |
| US6792587B2 (en) * | 2002-01-28 | 2004-09-14 | Sun Microsystems, Inc. | 2.5-D graph for multi-layer routing |
| US8125922B2 (en) * | 2002-10-29 | 2012-02-28 | Searchbolt Limited | Method and apparatus for generating a ranked index of web pages |
| US7477895B2 (en) * | 2004-01-21 | 2009-01-13 | Groundhog Technologies Inc. | Method for determining registration areas in a wireless communication system |
| US8738559B2 (en) | 2011-01-24 | 2014-05-27 | Microsoft Corporation | Graph partitioning with natural cuts |
| US9600785B2 (en) * | 2011-01-31 | 2017-03-21 | International Business Machines Corporation | Automatically generated and updated graphical rendering of processes |
| WO2013145001A1 (ja) * | 2012-03-28 | 2013-10-03 | 株式会社日立製作所 | 情報処理システムおよびグラフ処理方法 |
| US8886573B2 (en) | 2012-04-04 | 2014-11-11 | Microsoft Corporation | Determining optimum graph bisection using a tree and pruning the tree using a packing lower bound |
| US10318583B2 (en) | 2013-03-15 | 2019-06-11 | The Board Of Trustees Of The Leland Stanford Junior University | Systems and methods for recommending relationships within a graph database |
| CN105474735B (zh) | 2014-03-07 | 2020-01-17 | 华为技术有限公司 | 用于无线接入虚拟化的软传输点和用户设备关联方法 |
| GB2526300A (en) | 2014-05-20 | 2015-11-25 | Ibm | Partitioning of a network using multiple poles for each part thereof |
| GB2527825A (en) | 2014-07-03 | 2016-01-06 | Ibm | Configuration of a network partition with arrangement of intercepting/regulating elements based on distribution of residual capacity of sources to parts |
| US10521809B2 (en) | 2015-03-04 | 2019-12-31 | Walmart Apollo, Llc | System and method for grouping time series data for forecasting purposes |
| US10430462B2 (en) | 2017-03-16 | 2019-10-01 | Raytheon Company | Systems and methods for generating a property graph data model representing a system architecture |
| US10496704B2 (en) | 2017-03-16 | 2019-12-03 | Raytheon Company | Quantifying consistency of a system architecture by comparing analyses of property graph data models representing different versions of the system architecture |
| US10430463B2 (en) | 2017-03-16 | 2019-10-01 | Raytheon Company | Systems and methods for generating a weighted property graph data model representing a system architecture |
| US10459929B2 (en) | 2017-03-16 | 2019-10-29 | Raytheon Company | Quantifying robustness of a system architecture by analyzing a property graph data model representing the system architecture |
| US10706376B2 (en) * | 2018-07-09 | 2020-07-07 | GoSpace AI Limited | Computationally-efficient resource allocation |
| CN110058945B (zh) * | 2019-04-22 | 2025-04-11 | 河南工业大学 | 基于割点分割机制的大规模图并行计算最大流的加速方法 |
| CN110704693A (zh) * | 2019-09-27 | 2020-01-17 | 清华大学 | 分布式图计算系统和分布式图计算方法 |
| US20250146834A1 (en) * | 2022-04-01 | 2025-05-08 | Grabtaxi Holdings Pte. Ltd. | Method and system for adaptively dividing graph network into subnetworks |
| CN116029891A (zh) * | 2022-05-19 | 2023-04-28 | 北京百度网讯科技有限公司 | 图数据存储、访问、处理方法、训练方法、设备及介质 |
-
1994
- 1994-11-03 US US08/333,728 patent/US5748844A/en not_active Expired - Lifetime
-
1995
- 1995-11-01 JP JP7285249A patent/JP2719509B2/ja not_active Expired - Lifetime
Cited By (6)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US6564367B1 (en) | 1999-07-22 | 2003-05-13 | Hitachi, Ltd. | Logic dividing method, logic dividing system and recording medium for storing logic dividing program |
| JP2007299138A (ja) * | 2006-04-28 | 2007-11-15 | Hewlett-Packard Development Co Lp | 信頼ネットワークグラフの信頼値計算装置・方法・プログラム |
| JP2009258794A (ja) * | 2008-04-11 | 2009-11-05 | Fujitsu Ltd | 情報検索プログラム、情報検索装置、および情報検索方法 |
| US8583646B2 (en) | 2008-04-11 | 2013-11-12 | Fujitsu Limited | Information searching apparatus, information searching method, and computer product |
| US8898168B2 (en) | 2008-04-11 | 2014-11-25 | Fujitsu Limited | Information searching apparatus, information searching method, and computer product |
| JP2016091504A (ja) * | 2014-11-11 | 2016-05-23 | 富士通株式会社 | 情報提示方法、情報提示装置、及びプログラム |
Also Published As
| Publication number | Publication date |
|---|---|
| US5748844A (en) | 1998-05-05 |
| JP2719509B2 (ja) | 1998-02-25 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| JP2719509B2 (ja) | グラフ分割化システム | |
| US6651235B2 (en) | Scalable, partitioning integrated circuit layout system | |
| US4967367A (en) | Synthetic netlist system and method | |
| US5930499A (en) | Method for mixed placement of structured and non-structured circuit elements | |
| Kleinhans et al. | GORDIAN: VLSI placement by quadratic programming and slicing optimization | |
| US6353918B1 (en) | Interconnection routing system | |
| US5500804A (en) | Method to optimize the wiring of multiple wiring media packages | |
| CN111898330A (zh) | 基于多层次并行策略的集成电路电磁响应计算方法及装置 | |
| US8683417B2 (en) | Multiple level spine routing | |
| JPH08212250A (ja) | 集積回路レイアウト内への標準セルの自動挿入装置 | |
| JP2004501439A (ja) | 集積回路をパーティション化して、配置及び配線をするシステム | |
| Yeh et al. | A probabilistic multicommodity-flow solution to circuit clustering problems | |
| US6904584B2 (en) | Method and system for placing logic nodes based on an estimated wiring congestion | |
| Shigei et al. | On efficient spare arrangements and an algorithm with relocating spares for reconfiguring processor arrays | |
| Fukunaga et al. | Placement of circuit modules using a graph space approach | |
| Miller et al. | Embedding-based placement of processing element networks on FPGAs for physical model simulation | |
| Li et al. | Net cluster: A net-reduction-based clustering preprocessing algorithm for partitioning and placement | |
| Bultan et al. | Circuit partitioning using parallel mean field annealing algorithms | |
| Brown | Automated placement and routing | |
| Li et al. | Net cluster: a net-reduction based clustering preprocessing algorithm | |
| Liu et al. | Pre-layout physical connectivity prediction with application in clustering-based placement | |
| CN114528799B (zh) | 基于云平台的芯片多端协同设计方法及系统 | |
| Murphy | Neural network fitness function for optimization-based approaches to pcb design automation | |
| Tanomaru et al. | An evolutionary method for automatic wire routing | |
| Tien et al. | GALA-an automatic layout system for high density CMOS gate arrays |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| R250 | Receipt of annual fees |
Free format text: JAPANESE INTERMEDIATE CODE: R250 |
|
| R250 | Receipt of annual fees |
Free format text: JAPANESE INTERMEDIATE CODE: R250 |
|
| R250 | Receipt of annual fees |
Free format text: JAPANESE INTERMEDIATE CODE: R250 |
|
| R154 | Certificate of patent or utility model (reissue) |
Free format text: JAPANESE INTERMEDIATE CODE: R154 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20081114 Year of fee payment: 11 |
|
| S533 | Written request for registration of change of name |
Free format text: JAPANESE INTERMEDIATE CODE: R313533 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20081114 Year of fee payment: 11 |
|
| R350 | Written notification of registration of transfer |
Free format text: JAPANESE INTERMEDIATE CODE: R350 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20081114 Year of fee payment: 11 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20091114 Year of fee payment: 12 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20101114 Year of fee payment: 13 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20101114 Year of fee payment: 13 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20111114 Year of fee payment: 14 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20111114 Year of fee payment: 14 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20121114 Year of fee payment: 15 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20121114 Year of fee payment: 15 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20131114 Year of fee payment: 16 |
|
| R250 | Receipt of annual fees |
Free format text: JAPANESE INTERMEDIATE CODE: R250 |
|
| EXPY | Cancellation because of completion of term |