JPH07319953A

JPH07319953A - 回路分割方法

Info

Publication number: JPH07319953A
Application number: JP6151774A
Authority: JP
Inventors: Jaeseok Kim; キムジャエセオク; Nam-Sung Woo; − スングウオーナム
Original assignee: American Telephone and Telegraph Co Inc; AT&T Corp
Current assignee: AT&T Corp
Priority date: 1993-06-10
Filing date: 1994-06-10
Publication date: 1995-12-08
Also published as: US5508939A; EP0628921A2; EP0628921A3

Abstract

(57)【要約】【目的】回路ネットワークにおいてセルをブロックに
効率的に分割する。【構成】セルはまず、ランダムに、または、以前に決
定された初期分割に従って、ブロックに割り当てられて
初期分割を形成する。この初期分割に対して全品質因子
を計算する。次に、ブロックからブロックへセルを移動
することによって新たな分割が得られる。この移動は、
制約に違反しないように、かつ、品質因子を改善する見
込みに従って選択される。続いて、この新たな分割に対
して全品質因子を再計算し、分割プロセスを繰り返す。
品質因子が分割から分割へほとんど改善しなくなったと
きに、品質因子が改善された最後の分割を最良のものと
して選択する。制約は、ブロック内で許容されるセル数
や各ブロック上の端子ピン数のような因子である。品質
因子は、例えば、全ブロック上の端子ピンの総数であ
る。この場合、本方法の目標は、最小ピン数の分割を発
見することである。

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明は、回路ネットワークにお
いてセルをブロックに分割することに関し、特に、各ブ
ロックに許容されるセル数および端子ピン数のような制
約の下でそのような分割を実行することに関する。

【０００２】

【従来の技術】電子回路は、ネットワーク内で接続され
たゲートなどの回路素子からなることが多い。ある種の
電子回路では、ゲートなどの回路素子の多数のコピーが
一般的に集積回路として実装され、全電子回路はプリン
ト配線板上に組み立てられた複数の集積回路からなる。
集積回路間の接続は、プリント回路板上の配線路によっ
て与えられる。この種の代表的な電子回路の１つは、プ
ログラマブルゲートアレイというデバイスを使用するも
のである。プログラマブルゲートアレイでは、比較的多
数のゲートが集積回路内に備えられ、この集積回路内の
個々のゲートの機能およびそれらの間の接続は「プログ
ラム」によって指定される。ある種のプログラマブルゲ
ートアレイでは、プログラムは製造中にアレイの一部と
なる。フィールドプログラマブルゲートアレイ（ＦＰＧ
Ａ）として知られる他の種類のものでは、プログラムは
アレイに付属するランダムアクセスメモリまたは読み出
し専用メモリのようなメモリに含められるか、または、
プログラムは、可融性リンクを電気的に開閉することに
よってアレイに「焼き付け」られる。

【０００３】多数の回路素子を含むゲートアレイのよう
なデバイスでは、ゲートなどの回路素子をそれぞれ「セ
ル」とみなし、このようなゲートが中に製造される集積
回路を「ブロック」とみなすことができる。回路設計の
際に、設計者は、ブロック内のセル数やブロック上の端
子ピン数のような物理的制約に違反しないようにセルを
ブロック内に割り当てることによって回路を分割すると
いう問題を有する。プログラマブルゲートアレイでは、
セル間の接続はブロック内ですることができるが、回路
内のどのセルを与えられたブロックに配置するかの選択
は、そのブロック上のピン数によって制限されることが
多い。ブロックは複数種類のセルを含むことも可能であ
る。例えば、Ｘｉｌｉｎｘ４０００シリーズのＦＰＧＡ
は論理ブロックおよびデコーダの両方の配置を含む。セ
ルの種類やセルによる全パワー散逸への制限のような他
の制約が課されることもある。

【０００４】

【発明が解決しようとする課題】回路を複数のブロック
に分割する問題は多くの注目を受けている。例えば、シ
ー．エム．フィドゥッチャ(C. M. Fiduccia)、アール．
エム．マセイゼス(R. M.Mattheyses)、「ネットワーク
分割を改善する線形時間発見法(A Linear-Time Heurist
ic for Improving Network Partitions)」、Proc. of 1
9th IEEE DesignAutomation Conference、第１７５〜１
８１ページ（１９８２年）；バラクリシュナン・クリシ
ュナマーシー(Balakrishnan Krishnamurthy)、「ＶＬＳ
Ｉネットワークを分割する改善最小カットアルゴリズム
(An Improved Min-Cut Algorithmfor Partitioning VLS
I Networks)」、IEEE Transactions on Computers、第
Ｃ−３３巻第５号第４３８〜４４６ページ（１９８４
年）；ローラ．エー．サンチス(Laura A. Sanchis)、
「マルチプルウェイネットワーク分割(Multiple-Way Ne
twork Partitioning)」、IEEE Transactions on Comput
ers、第３８巻第１号第６２〜８１ページ（１９８９
年）参照。しかし、ブロック内のピン制限および複数の
セル種類によって生じる問題点は残っている。

【０００５】

【課題を解決するための手段】本発明の実施例によれ
ば、相互接続されたセルは、各ブロックがその中のセル
の配置に少なくとも１つの制約を有するようなブロック
に分割される。セルはまず、ランダムに、または、以前
に決定された初期分割に従って、ブロックに割り当てら
れて初期分割を形成する。この初期分割に対して全品質
因子を計算する。

【０００６】次に、ブロックからブロックへセルを移動
することによって新たな分割が得られる。この移動は、
制約に違反しないように、かつ、品質因子を改善する見
込みに従って選択される。続いて、この新たな分割に対
して全品質因子を再計算し、分割プロセスを繰り返す。
品質因子が分割から分割へほとんど改善しなくなったと
きに、品質因子が改善された最後の分割を最良のものと
して選択する。

【０００７】制約は、ブロック内で許容されるセル数や
各ブロック上の端子ピン数のような因子である。品質因
子は、全ブロック上の端子ピンの総数とすることが可能
である。この場合、本方法の目標は、最小ピン数の分割
を発見することである。

【０００８】好ましい実施例では、はじめの分割に対し
て制約のうちの少なくとも１つを緩和し、それによっ
て、その制約があれば許容されないが後の分割に重大な
利益を有するようなセルの移動を可能にする。

【０００９】

【実施例】図１に、いくつかの回路セル１０１〜１０４
を含む例示的な回路ブロック１０を示す。回路ブロック
１００は簡単のために単純化されている。一般的な集積
回路は、数千個のセルおよび数百個のピンを有すること
が可能である。しかし、図１には、さらに複雑な回路に
存在するのと同じセル、ピンおよびネットの相互関係を
示している。

【００１０】例えば、回路ブロック１００はＦＰＧＡの
ような集積回路であり、セル１０１〜１０４は論理ゲー
トである。ブロック１００上の外部端子すなわちピン１
１０〜１１２は、相互接続ネットワーク（ネット）１２
０〜１２３によってセル１０１〜１０４のさまざまな端
子に接続されている。ブロック内のさまざまなネットに
よって形成されるセル間の接続のリストを一般に「ネッ
トリスト」という。

【００１１】ネット１２１は、セル１０１〜１０４のそ
れぞれの端子をピン１１０に接続し、ネット１２２はセ
ル１０３および１０４のそれぞれの端子をピン１１２に
接続し、ネット１２０はセル１０２および１０４のそれ
ぞれの端子をピン１１０に接続する。しかし、ネット１
２３はブロック１００の内部にある。すなわち、ネット
１２３はブロック１００上のピンには接続されていな
い。

【００１２】ブロック内の各セルは一般に複数のネット
に接続され、そのうちのいくつかはブロック上のピンに
も接続されている。多数のブロックを含む実際の回路で
は、与えられたネットは異なるブロック内のセルと相互
接続することが可能であるが、そのとき各ブロック上の
ピンは各ブロックのネットの一部と相互接続する必要が
ある。この相互接続は、例えばプリント配線板上のリー
ドによって、ブロックの外部になされる。

【００１２】図２に、いくつかのブロック２０１、２１
１および２２１を示す。これらのブロックは、ブロック
２０１内のセル２０２および２０３のようなセルを有す
る。これらのセルは、ネット２３０によって、ブロック
２１１および２２１内の同様のセルと相互接続されてい
る。各ブロックは、ネット２３０に対するピン（例えば
２０４）を有する。図２は、これから説明する分割方法
において、あるブロックから別のブロックにセルを移動
する効果を説明する際に有用である。

【００１３】一般的に、本発明の方法は、初期分割から
開始し、選択したセルをブロック間で移動することによ
って改善した分割を得るというパスをいくつか含む。パ
スによって、前の分割に比べて改善がほとんどまたは全
くないようになると、本発明の方法は終了する。

【００１４】パスからパスへの改善は、分割している回
路内のすべてのブロック上に使用されるピンの総数のよ
うな品質因子を使用して測定される。最良の分割は、通
常は、ピン数が最小のものと考えられる。このような品
質因子により、あるブロックから別のブロックにセルを
移動する際の目標は、サイズおよびピンの制約を満たし
つつ使用するピン総数を減少させることとなる。

【００１５】初期分割を決定する１つの方法は、使用さ
れるブロック間でランダムに回路のセルを任意分割する
ことによる。例えば、２４０個のセルを含む回路を、そ
れぞれ１００個のセルを有する３個のブロックにより実
装する場合、８０個のセルを各ブロックにランダムに割
り当てることができる。次に、その回路に対するネット
リストに指定されたセル間の相互接続が与えられると、
各ブロック上のピン数が決定される。このような初期分
割は通常ブロックのサイズ制約を満たすように形成され
るが、ピン制約は違反する可能性がある。ピン制約違反
は、分割プロセスが進行するにつれて除去されることが
期待される。

【００１６】初期分割は、回路設計者が指定することも
可能である。この方法は、設計者が、適当な分割を示唆
するセル間の特定の関係を知っている場合に有効であ
る。この場合にも、これから説明する方法を使用して分
割を最適化することができる。

【００１７】本発明の方法の各パスでは、現在のブロッ
クから回路内の他の各ブロックに各セルを移動すること
に対する「利益」尺度を決定する。次に、利益が最高の
セルから始めて、利益の降順にセルを移動する。しか
し、この移動が制約のうちの１つに違反する場合にはセ
ルは移動されない。セルは、移動された後、「ロック」
される。すなわち、このようなセルは現在のパスの間は
再び移動することはできない。最後に、移動したセルに
接続された未移動セルに対する利益を、移動を反映する
ように調整する。このような調整によって、残りのセル
の順序は変わり得る。

【００１８】各セルの移動後、全ブロックに対する全ピ
ン数を決定する。この全ピン数は、各移動後に達成され
た分割の品質を追跡するために使用される。しかし、与
えられたパスの間、全ピン数は必ずしも各移動とともに
単調に減少するとは限らない。すなわち、ある移動は全
ピン数を減少させるが、他の移動は増加を引き起こすこ
ともある。従って、パスが完了した後、最小の全ピン数
が判定された移動を、そのパスが終了すべき移動として
選択する。

【００１９】最初の数個のパスの間、全ピン数は一般に
パスとともに減少する。しかし、最終的に、このような
減少は停止し、さらにセルを移動することによって分割
の品質が改善されそうにないようになる。従って、引き
続くパスの間のピン数の差が０または微小数に達する
と、前のパスの結果を最良の分割とすることができる。

【００２０】制約のうちの少なくとも１つ、例えばピン
制約を、最初の数個のパスの間は緩和することができ
る。上記のように、初期分割に対しては、たとえサイズ
制約が満たされていてもピン制約に違反する可能性があ
る。しかし、利益を決定する際に使用される方法のため
に、全ピン数は通常減少し、最初の数個のパスの後にピ
ン制約は回復する。

【００２１】ピン数が比較的安定な値に達しながらなお
も制約に違反している場合も存在し得る。このような場
合には、パスを追加しても、制約を満たす分割が得られ
る見込みはない。しかし、新たなランダム初期分割を決
定して全プロセスを繰り返すことが可能である。何度か
のこのような繰り返しの後にも分割が成功しない場合
は、おそらく、回路を実装するためには異なる数のセル
またはピンを有するブロックを使用する必要がある。

【００２２】多数の同一のセルがブロック内に含まれる
ＦＰＧＡを使用した回路を分割する際には、ピン制約の
みを緩和し、サイズ制約は緩和しないのが好ましいこと
をわれわれは発見した。もちろん、このような場合に、
サイズ制約は初期分割で通常守られる。

【００２３】実施例では、各セル移動に対する利益はス
カラー値として計算される。これらの値は２つのスカラ
ー成分（一次利益および二次利益）を有しうる。一次利
益は、移動を行う際に節約された（または付加された）
ピン数に関して決定した、考えている移動の「良好度」
を示す。二次利益は、「前方参照」因子であり、その移
動をすることによる可能な将来の効果を示す。

【００２４】回路内のセルに対する利益を決定する際に
は、この一次利益および二次利益に重みづけをすること
ができる。この重みは、必要であれば、パスごとに変え
ることができる。例えば、二次利益、すなわち「前方参
照」利益には、はじめのほうのパスの間は高い重みを与
えることができる。以下の説明では、一次利益および二
次利益に対する重みとしてそれぞれαおよびβを使用す
る。このような重みを選択することについては後で説明
する。

【００２５】上記の説明で、「ロック」されたセルとい
う概念を導入した。これは、すなわち、あるパスの間に
移動されたためそのパス中には再び移動することができ
ないセルである。以下で説明するように、与えられたセ
ル移動に対する一次利益および二次利益は、考えている
セルに接続されたネット上のロックされたセルの数およ
び自由な（ロックされていない）セルの数から決定する
ことができる。

【００２６】各セルは一般にいくつかのネットに接続さ
れている。例えば、ＦＰＧＡセルでは２０個ほどのネッ
トに接続されている。従って、セルの移動を考える場
合、そのセルに接続されたすべてのネットに対する影響
を考慮に入れなければならない。実施例で使用されるス
カラー利益値の利点は、セルに接続されたすべてのネッ
トに対する利益値を別々に決定し加算して、セルの移動
に対する全利益値を与えることができることである。

【００２７】マルチブロックネットは、ネット内のセル
を有する各ブロック上にピンを必要とする。例えば、図
２において、マルチブロックネット２３０は、ブロック
２０１、２１１および２２１上にそれぞれピン２０４、
２１４および２２４を必要とする。マルチブロックネッ
ト上のピンは、ネット上のセルをより少ないブロックに
グループ化することによって少なくすることができる。
ネット上のセルがロックされている場合、ピンを少なく
するには、ロックされているセルを有するブロックへ自
由セルを移動することである。ネット上のすべてのセル
を同一のブロックにグループ化することができる場合、
そのネット上のすべてのピンを除去することができる。
セル移動の利益は、このようなピン減少目標を考慮に入
れて決定される。

【００２８】従って、与えられたネットに接続された自
由セルをソースブロックからデスティネーションブロッ
クへ移動することに対する利益の決定は、そのネットに
接続されている他のセルの状態（ロックされているかま
たは自由であるか）および位置に基づく。与えられた移
動は、次の４つの場合のうちの１つに入る。

【００２９】（１）ソースブロックおよびデスティネー
ションブロックの両方にロックされたセルがある。（２）ソースブロックのみに少なくとも１つのロックさ
れたセルがある。（３）デスティネーションブロックのみに少なくとも１
つのロックされたセルがある。（４）ソースブロックにもデスティネーションブロック
にもロックされたセルはない。

【００３０】場合１では、ネットのピンが、ソースブロ
ックおよびデスティネーションブロックの両方に既に存
在する。ピン数はその移動によっては変化しない。従っ
て、一次利益は０である。しかし、デスティネーション
ブロック内のネット上のセル数がソースブロック内より
もずっと多い場合、後のパスでソースブロックからロッ
クされているセルを移動することができる可能性がある
ため、二次利益は正となる。

【００３１】場合２では、この移動は、デスティネーシ
ョンブロックにロックされたセルを追加し、これによっ
て、デスティネーションブロックにネットのピンを追加
するか、または、既に存在するピンが除去されないよう
にすることがあるため、好ましくない。また、ソースブ
ロックの外側のネット上にロックされたセルがない場
合、この移動はソースブロックにピンを追加することに
もなる。従って、この移動の一次利益は負となる。しか
し、デスティネーションブロック内でネットに接続され
ているセルの数はソースブロックよりもずっと多いた
め、場合１と同じ理由で二次利益は正となる。

【００３２】場合３で、ソースブロック内のただ１つの
セルのみがネットに接続されている場合、この移動はそ
のソースブロック上のネットのピンを除去し、一次利益
は正となる。ソースブロック内の複数のセルがネットに
接続されている場合、この移動は、後のパスにおけるソ
ースブロックのピンの除去につながる可能性があるた
め、一次利益はないが、二次利益は正となる。ネット上
のデスティネーションブロック内のセル以外のすべての
セルが自由である場合、この移動は、最終的にネット上
のすべてのピンの除去につながる可能性があるため、さ
らに大きい正の二次利益を有する。

【００３３】場合４で、移動するセルがネット上のソー
スブロック内のただ１つのセルである場合、この移動は
ピンを除去し、一次利益は正となる。しかし、ネット上
でデスティネーションブロック内にセルがない場合、こ
の移動はピンを追加し、一次利益は負となる。これら以
外の場合、この移動は二次利益のみを有する。

【００３４】与えられたネット上の移動の利益の数値
は、以下の式から決定することができる。利益＝ α（一次利益）＋ β（二次利益）（１）ただし、αおよびβは上記の重み因子である。

【００３５】上記の４つの場合に対する一次利益および
二次利益の値は表１の式から決定することができる。た
だし、ネット上のセルに対して、Ｌ（Ｓ）＝ソースブロック内のロックされているセル数Ｌ（Ｓ’）＝ソースブロック外のロックされているセル
数Ｌ（Ｄ）＝デスティネーションブロック内のロックされ
ているセル数Ｌ（Ｄ’）＝デスティネーションブロック外のロックさ
れているセル数Ｔ＝全セル数Ｔ（Ｓ）＝ソースブロック内の全セル数Ｔ（Ｄ）＝デスティネーションブロック内の全セル数とする。

【００３６】

【表１】

【００３７】こうして、ソースブロックからデスティネ
ーションブロックへセルを移動する全利益は、そのセル
に接続された各ネットに対して決定される利益を加算す
ることによって得られる。ブロック間でセルを移動する
利益を決定する他の方法も、本発明の技術思想および技
術的範囲から離れることなく、必要に応じて使用するこ
とができる。

【００３８】図３に、上記の技術を使用して回路を分割
する方法の例の流れ図を示す。このような方法は、例え
ば、ＵＮＩＸ（登録商標）を使用したＳｕｎのＳＰＡＲ
Ｃｓｔａｔｉｏｎ（商標）のような汎用ディジタルコン
ピュータで実行可能である。

【００３９】まず、分割する回路のネットリストおよび
その回路に対する最終制約（例えば、各ブロック内で許
容されるセル数および各ブロック上で許容されるピン
数）を格納する（ステップ３０１）。次に、例えば回路
のセルをブロックにランダムに割り当てることによっ
て、または、指定された初期分割を使用することによっ
て、初期分割を決定し（ステップ３０２）、ピン数およ
びパス数を初期化する（ステップ３０３）。各ブロック
のピン数は、そのブロック上にセルを有する格納された
ネットリスト内のネット数を数えることによって決定す
ることができる。

【００４０】好ましい実施例では、最初の数個のパス中
は制約は緩和される（ステップ３０４および３０５）。
制約を緩和することによって、効果的なセル移動を決定
するために利用可能な検索空間が増大する。例えば、そ
れぞれ１００個のピンをもつブロックを有する回路で
は、ピン制約はブロックあたり２００個まで緩和される
ことがある。制約は、セル移動の余地を残しつつ、初期
分割が可能となるために必要な範囲まで緩和されるのが
好ましい。例えば、ブロックが初期分割に１２０個のピ
ンを必要とした場合、緩和されたピン制約は１３０に設
定することができる。このような制約緩和によって、制
約緩和がなければ妨げられた最初の数個のパスにおける
セル移動が可能となる。後で大きな利益を有する可能性
のある移動を妨げないのが好ましい。別法として、制約
によって特に高い利益を有するセル移動が妨げられてい
るときにのみその制約を緩和することも可能である。

【００４１】次に、新たな分割が発見される（ステップ
３０６）。図４は、分割を発見するステップを示すさら
に詳細な流れ図である。まず、例えば上記の表１にリス
トされた式を使用することによって、異なるブロックへ
のセルの可能な移動のそれぞれに対して利益を計算する
（ステップ４０１）。例えば、４個のブロックに分割さ
れている回路では、ソースブロックから、可能な３個の
デスティネーションブロックのそれぞれへの移動に対し
て別々に利益を計算する。分割ステップの最初ではすべ
てのセルが自由であることに注意すべきである。従っ
て、各移動に対する利益は、表１の場合４の式に従って
計算される。一般的に、いくつかの異なる利益値が得ら
れ、複数の移動が同じ利益を有することになる。

【００４２】利益計算完了後、最大の利益値を有する自
由セルの移動が選択され（ステップ４０２）、サイズ制
約またはピン制約のようないずれかの制約に違反してい
ないかどうかチェックされる（ステップ４０３）。その
移動が制約に違反していない場合、その移動が、一時的
な分割記録において実行され、移動したセルはロックさ
れたものとして記録される。また、回路の新たなピン数
が計算され、その移動とともに記録される（ステップ４
０４）。

【００４３】移動の完了後、移動したセルに接続された
ネット上の各自由セルに対して、次の移動の利益が再計
算される。これは、移動から生じる利益値の増分を計算
し、各ネットに対するその増分値をｍ×ｍ配列の形に配
列することによって効率的に実行される（ステップ４０
６）。ただし、ｍはブロック数である。このような配列
を「デルタ利益」配列という。

【００４４】デルタ利益配列の各要素（ｉ，ｊ）は次の
ようにして決定される。 Δ利益（ｉ，ｊ）＝移動後の利益（ｉ，ｊ）−移動前の利益（ｉ，ｊ）（２）ただし、利益（ｉ，ｊ）はブロックｉからブロックｊへ
自由セルを移動する利益である。

【００４５】移動したセルに接続された各ネットに対し
てこのような配列を計算した後、移動したセルに接続さ
れた自由セルの各移動に対する利益を更新することがで
きる（ステップ４０７）。与えられた自由セル移動に対
する利益を更新する際に、自由セルに接続された各ネッ
トに対するΔ利益配列からのこのような移動に対するΔ
利益値が現在の利益に加算される。

【００４６】制約に違反することなく可能なすべての自
由セルの移動が完了するまで、ステップ４０２、４０
３、４０４、４０６および４０７が反復される（ステッ
プ４０８）。選択したセル移動が制約に違反する場合
（ステップ４０３）、このような移動は無視される（ス
テップ４０５）。しかし、後で、別のデスティネーショ
ンブロックへの同じセルの移動に対する利益値に達した
ときに、その移動が可能となることはある。ステップ４
０５またはステップ４０８からステップ４０２に復帰す
ると、最大利益値を有するすべてのセルを考慮し終える
まで、その利益値を有する他のセルが選択される。その
利益値を有するすべてのセルを選択した場合、次に大き
い利益値が使用され、以下同様である。

【００４７】最後の移動の完了後、ステップ４０４で格
納された全ピン数が最小の移動を、そのパスに対する最
終的な最良の移動として選択する（ステップ４０９）。
ここで図３の流れ図に戻り、新たなピン数が、前のパス
中に決定されたもの（または最初に格納されたもの）よ
り少ない場合、このピン数を更新し（ステップ３０
８）、分割の主記録を、ステップ４０４中の一次記録に
格納された移動からステップ４０９で選択された移動ま
でによって更新する。

【００４８】分割パスは、パス後の新たなピン数が前の
ピン数より減少しなくなるまで（または大幅に減少しな
くなるまで）反復される（ステップ３０７）。ピン数が
減少しないことは、それ以上のパスは意味がないことを
示す。Ｎ個のパスの完了後（ただしＮはユーザがパラメ
ータとして選択し、例えば、Ｎは３とすることができ
る）、制約は緩和されなくなり、各セル移動は、格納さ
れた最終的制約を満たさなければならない。

【００４９】最後のパスの後、制約に違反していないか
どうかの最終チェックが行われる（ステップ３１１）。
違反している場合、新たな初期分割を決定し（ステップ
３１２）、分割プロセスを繰り返す。違反していない場
合、プロセスは終了し、主記録に格納されている最終分
割を出力して使用することができる（ステップ３１
３）。ステップ３１２までのループの反復回数を制限す
ることが好ましい。すなわち、いくつかの新たな分割が
失敗した場合、分割成功のためにはより緩やかな制約が
おそらく必要である。

【００５０】重み因子αおよびβの値を選択するに際し
て、われわれは、最良の分割（最小のピン数）は、α＞
２βの場合、例えば、α＝１０、β＝３の場合に達成さ
れることを発見した。しかし、最良の分割を得るために
は、これらの重み因子の異なる組合せとともに異なる初
期分割を試みる必要があることもある。従って、ステッ
プ３１２は、新たな初期分割の決定に加えて、αおよび
βの新たな値の決定を含むことも可能である。

【００５１】上記のように、重み因子αおよびβを変え
る効果的な方法は、はじめのいくつかのパスではある値
のセットを使用し、後のパスでは別の値のセットを使用
することである。例えば、パス数が所定のしきい値に達
した後に重み因子を変化させることができる。このよう
な変化は、ステップ３１０の後および反復ステップ３０
４の前で行うことができる。

【００５２】重み因子を変える代わりに、または、変え
るのに加えて、利益を計算するために使用する式も、パ
ス数に基づいて変えることが可能である。すなわち、表
１に示したような式は、初期の１以上のパスに対して使
用し、その後のパスには別の式を使用することができ
る。

【００５３】図５は、上記の方法の改良を示す部分流れ
図である。ステップ３０６、３０７、３０８および３１
３は図３と同じである。新たなステップ５０１、５０２
および５０３が追加されている。ステップ３０７で、新
たなピン数のほうが少ない場合、いずれかのブロックに
制約違反があるかどうかをチェックする（ステップ５０
１）。違反がない場合、本方法は図３のステップ３０８
に続く。しかし、違反がある場合、前のパスの後に制約
違反があったかどうかをさらにチェックする（ステップ
５０２）。そのような違反でない場合、プロセスはステ
ップ３１３を実行することによって終了する。ステップ
３１３では、前のパスの更新された結果を反映する主記
録を出力する。しかし、前のパスの後に制約違反が存在
した場合、ピン数はまだ減少しており、次のパスがその
違反を除去する可能性があるため、プロセスは継続され
る。

【００５４】同様に、ステップ３１１で制約違反が発見
された場合、前のパスがチェックされ（ステップ５０
３）、そのパスが違反していない場合、ステップ３１３
が実行されて、前のパスを出力としてプロセスを終了す
る。この場合、前のパスもまた違反している場合は、新
たな初期分割を決定する（ステップ３１２）。

【００５５】

【発明の効果】以上述べたごとく、本発明によれば、回
路ネットワークにおいて、セルをブロックに分割する場
合に、各ブロックに許容されるセル数および端子ピン数
のような制約の下でそのような分割を実行することが効
率的に行われる。

【図面の簡単な説明】

【図１】いくつかのセルを含む回路ブロックの図であ
る。

【図２】ネットワークによって相互接続されたブロック
内のいくつかのセルの図である。

【図３】セルをブロックに割り当てる例示的な方法の流
れ図である。

【図４】図３の分割ステップを詳細に示す流れ図であ
る。

【図５】図３の方法の変形を示す部分流れ図である。

【符号の説明】

１００ブロック１０１セル１０２セル１０３セル１０４セル１１０ピン１１１ピン１１２ピン１２０ネット１２１ネット１２２ネット１２３ネット２０１ブロック２０２セル２０３セル２０４ピン２１１ブロック２２１ブロック

───────────────────────────────────────────────────── フロントページの続き (72)発明者ナム − スングウオーアメリカ合衆国、07974 ニュージャージー、ニュープロビデンス、ダーバイコート 10

Claims

【特許請求の範囲】

【請求項１】相互接続されたセル（１０１〜１０４）
を、内部へのセルの配置に対する少なくとも１つの制約
を有するブロック（１００）に分割する方法において、
この方法は、セルをブロックに割り当てて初期分割を形成するステッ
プと、前記初期分割に対する全体の品質因子を計算する計算ス
テップと、前記制約に違反しないように、かつ、前記品質因子を改
善するように、ブロックからブロックへセルを移動する
ことによって新たな分割を見つける分割発見ステップ
と、前記新たな分割に対して全体の品質因子を再計算する再
計算ステップと、前記品質因子の改善がほぼ停止するまで前記分割発見ス
テップおよび前記再計算ステップを反復する反復ステッ
プとからなり、前記分割発見ステップは、各可能なセル移動に対して、そのセル移動が前記品質因
子を改善する尤度を示す利益値を計算する利益値計算ス
テップと、前記制約に違反するセル移動を除いて、前記利益値の高
い順に前記セル移動を実行するステップと、各セルの移動後に、現在の分割発見ステップ中に前記セルが再び移動しない
ように前記セルをロックするステップと、前記セル移動の結果生じた分割の品質を反映するように
前記品質因子を修正し、その修正した品質因子を前記セ
ル移動に関係づけるステップと、実行したセル移動の効果を反映するように残りの可能な
セル移動に対する利益値を再計算するステップと、最後のセル移動を実行後に、最良の品質因子に関係づけられたセル移動を選択するス
テップと、その選択したセル移動の結果生じた分割を新たな分割と
して使用するステップとからなることを特徴とする回路
分割方法。
【請求項２】前記品質因子が前記ブロック上の端子ピ
ンの総数であり、前記分割方法の目的がその総数を最小
化することであることを特徴とする請求項１の方法。
【請求項３】前記制約のうちの１つが各ブロック内の
セルの数であることを特徴とする請求項１の方法。
【請求項４】前記制約のうちの１つが各ブロック上の
端子ピンの数であることを特徴とする請求項１の方法。
【請求項５】前記制約のうちの少なくとも１つを緩和
して前記分割発見ステップの反復を少なくとも１回実行
するステップをさらに有することを特徴とする請求項１
の方法。
【請求項６】前記分割発見ステップおよび再計算ステ
ップの最後の反復の後に前記制約のうち違反しているも
のがある場合、前記セルを前記ブロックにランダムに再
割当して新たな初期分割を形成し、前記計算ステップ、
分割発見ステップ、再計算ステップおよび反復ステップ
を繰り返すステップをさらに有することを特徴とする請
求項１の方法。
【請求項７】前記分割発見ステップおよび再計算ステ
ップのある反復後に前記制約のうち違反しているものが
あり、かつ、前記分割発見ステップおよび再計算ステッ
プの先行する反復では前記制約に違反しているものはな
い場合、その先行する反復の結果生じた分割を本方法の
結果として選択するステップをさらに有することを特徴
とする請求項１の方法。
【請求項８】前記利益値計算ステップが、各可能なセル移動に対して、移動するセルに接続された
各ネットに対して別々に利益値を計算するステップと、各ネット（１２０〜１２２）に対する利益値を組み合わ
せて前記セル移動に対する全利益値を取得するステップ
とからなることを特徴とする請求項１の方法。
【請求項９】前記利益値計算ステップが、移動前に位置するソースブロック内の前記ネット上のロ
ックされたセルの数と、移動後に位置することになるデスティネーションブロッ
ク内の前記ネット上のロックされたセルの数と、前記ソースブロックの外側の前記ネット上のロックされ
たセルの数と、前記デスティネーションブロックの外側の前記ネット上
のロックされたセルの数と、前記ネット上のセルの総数と、前記ソースブロック内の前記ネット上のセルの総数と、前記デスティネーションブロック内の前記ネット上のセ
ルの総数と、のうちの１つ以上の因子に基づいて前記ネ
ットに対して各利益値を計算するステップをさらに有す
ることを特徴とする請求項８の方法。
【請求項１０】前記利益値計算ステップが、前記セル移動の実際の利益を反映する一次利益値を計算
するステップと、前記セル移動の将来の可能な利益値を反映する二次利益
値を計算するステップと、前記一次利益値および前記二次利益値を組み合わせて前
記別々の利益値を取得する組合せステップとをさらに有
することを特徴とする請求項８の方法。
【請求項１１】前記組合せステップの前に、前記一次
利益値および前記二次利益値のうちの少なくとも１つに
重み因子を作用させるステップをさらに有することを特
徴とする請求項１０の方法。
【請求項１２】前記再計算ステップにおいて、移動す
るセルに接続された各ネットに対して、追加セルを各ブロックから他の各ブロックへ移動するに
際して、移動完了前に追加セルを移動する利益と、移動
完了後に追加セルを移動する利益とに基づく増分利益値
を計算するステップと、前記移動するセルに接続された自由セルの残りの可能な
各移動に対して、その可能な移動の現在の利益値に、前
記移動するセルに前記自由セルを接続するネットに対し
て計算したその移動の増分利益値を組み合わせるステッ
プとをさらに有することを特徴とする請求項１の方法。
【請求項１３】各利益値計算ステップが、前記利益値
をスカラー量として計算するステップからなり、各組合せステップが、前記利益値を加算するステップか
らなることを特徴とする請求項１３の方法。
【請求項１４】完了した前記分割発見ステップの反復
数に従って前記利益値の計算方法を変えるステップをさ
らに有することを特徴とする請求項１の方法。
【請求項１５】完了した前記分割発見ステップの反復
数に従って前記重み因子を変えるステップをさらに有す
ることを特徴とする請求項１１の方法。
【請求項１６】相互接続されたセルを、内部へのセル
の配置に対する少なくとも１つの制約を有するブロック
に分割する方法において、この方法は、セルをブロックに割り当てて初期分割を形成するステッ
プと、前記初期分割に対する全体の品質因子を計算する計算ス
テップと、前記制約に違反しないように、かつ、前記品質因子を改
善するように、ブロックからブロックへセルを移動する
ことによって新たな分割を見つける分割発見ステップ
と、前記新たな分割に対して全体の品質因子を再計算する再
計算ステップと、前記品質因子の改善がほぼ停止するまで前記分割発見ス
テップおよび前記再計算ステップを反復する反復ステッ
プとからなり、前記反復のうちの少なくとも１つは前記制約のうちの少
なくとも１つを緩和させて実行され、前記反復のうちの少なくとも最後のものは前記制約のす
べてが満たされて実行されることを特徴とする回路分割
方法。