JPH03211859A - 配置位置決定装置 - Google Patents
配置位置決定装置Info
- Publication number
- JPH03211859A JPH03211859A JP2006435A JP643590A JPH03211859A JP H03211859 A JPH03211859 A JP H03211859A JP 2006435 A JP2006435 A JP 2006435A JP 643590 A JP643590 A JP 643590A JP H03211859 A JPH03211859 A JP H03211859A
- Authority
- JP
- Japan
- Prior art keywords
- logical connection
- network
- minimum cost
- flow
- divided
- 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.)
- Pending
Links
Landscapes
- Semiconductor Integrated Circuits (AREA)
- Design And Manufacture Of Integrated Circuits (AREA)
Abstract
(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。
め要約のデータは記録されません。
Description
【発明の詳細な説明】
〔産業上の利用分野〕
本発明は配置位置決定装置、特にＬＳＩの配置位置決定
装置に関するものである。
装置に関するものである。
従来、ＬＳＩの配置を決定する打力手法の一つであるミ
ニカット法では、次の条件のもとて全素子集合を二つの
集合に分割する処理を扱っている。
ニカット法では、次の条件のもとて全素子集合を二つの
集合に分割する処理を扱っている。
■それぞれの集合の素子数の差は、あらかしめ指定され
た許容値以下とする。
た許容値以下とする。
■集合をまたがる配線本数を最小とする。
従来の手法では、まず大まかに二つの集合に分割した後
、局所的な変換により初期解の改良を行っていた。
、局所的な変換により初期解の改良を行っていた。
このような従来の手法は、予稿集「枝広、吉村：階層ク
ラスタリングを用いたスタンダードセルのための配線ア
ルゴリズムＪ １９Ｂ９年電子情報通信学会秋期全国大
会、 Ａ−９４に詳しく述べられている。
ラスタリングを用いたスタンダードセルのための配線ア
ルゴリズムＪ １９Ｂ９年電子情報通信学会秋期全国大
会、 Ａ−９４に詳しく述べられている。
前記のように、初期解を改良する方式では、解の良さは
初期分割の善し悪しに大きく依存し、良い解が得られな
い場合があった。
初期分割の善し悪しに大きく依存し、良い解が得られな
い場合があった。
本発明の目的は、配置素子間の論理接続情報を表現する
ネットワーク上でフローを最適化することにより、良好
な集合分割を行う配置位置決定装置を提供することにあ
る。
ネットワーク上でフローを最適化することにより、良好
な集合分割を行う配置位置決定装置を提供することにあ
る。
本発明の配置位置決定装置は、
入力として与えられる配置素子間の論理接続情報を表す
論理接続ネットワークを格納する論理接続ネットワーク
格納部と、 前記ネットワーク上で最小コストフローを計算する最小
コストフロー計算部と、 前記ネットワーク上のフローの状態に基づき素子集合を
二つの集合に分割する集合分割部とからなることを特徴
とする。
論理接続ネットワークを格納する論理接続ネットワーク
格納部と、 前記ネットワーク上で最小コストフローを計算する最小
コストフロー計算部と、 前記ネットワーク上のフローの状態に基づき素子集合を
二つの集合に分割する集合分割部とからなることを特徴
とする。
［作用］
本発明による素子集合分割を第３図〜第５図に基づいて
説明する。なお、第３図は論理接続および素子集合分割
の説明図、第４図は論理接続ネット、ワークの説明図、
第５図は論理接続ネットワークの各アークのフロー量と
コストの関係を表す説明図である。
説明する。なお、第３図は論理接続および素子集合分割
の説明図、第４図は論理接続ネット、ワークの説明図、
第５図は論理接続ネットワークの各アークのフロー量と
コストの関係を表す説明図である。
格納部に、例えば第３図（ａ）に示すような配置素子間
の論理接続情報、すなわち全素子集合の論理接続情報が
与えられると、論理接続情報を表す論理接続ネットワー
クを格納する。第３図（ａ）において、口は外部入出力
端子２１の論理接続情報を、Ｏは配置素子２２の論理接
続情報を、−は素子間の配線２３の論理接続情報を表し
ている。第４図は格納された論理接続ネットワークであ
り、■はフローのソース３１を、■はフローのシンク３
２を、口は仮想ノード３４を、−は仮想アーク３３．３
５ａ、 ３５ｂ。
の論理接続情報、すなわち全素子集合の論理接続情報が
与えられると、論理接続情報を表す論理接続ネットワー
クを格納する。第３図（ａ）において、口は外部入出力
端子２１の論理接続情報を、Ｏは配置素子２２の論理接
続情報を、−は素子間の配線２３の論理接続情報を表し
ている。第４図は格納された論理接続ネットワークであ
り、■はフローのソース３１を、■はフローのシンク３
２を、口は仮想ノード３４を、−は仮想アーク３３．３
５ａ、 ３５ｂ。
３５ｃ、３６ａ、３６ｂ、３６ｃを、○は配置すべき素
子または外部入出力端子に対応するノード３７を、は配
線に対応するアーク３８を表している。
子または外部入出力端子に対応するノード３７を、は配
線に対応するアーク３８を表している。
最小コストフロー計算部は、論理接続ネットワークにお
いて、仮想アーク３５ａ、３５ｂ、３５ｃ、３６ａ、３
６ｂ、３６ｃの容量を無限大とし、ソース３１につなが
る仮想アーク３３の容量を１から順次増やしながら、ソ
ース３１からシンク３２への最小コストフローを、第５
図に示すアークのフロー量とコストの関係に基づいて計
算する。
いて、仮想アーク３５ａ、３５ｂ、３５ｃ、３６ａ、３
６ｂ、３６ｃの容量を無限大とし、ソース３１につなが
る仮想アーク３３の容量を１から順次増やしながら、ソ
ース３１からシンク３２への最小コストフローを、第５
図に示すアークのフロー量とコストの関係に基づいて計
算する。
素子集合は、最小コストフロー計算部において求まった
フロー量が非零となるアークの集合を用いて、第３図（
ｂ）に示すごとく素子集合を二つに分割する。第３図（
ｂ）では、カットライン２５で分割された素子集合２４
ａ、２４ｂを示している。
フロー量が非零となるアークの集合を用いて、第３図（
ｂ）に示すごとく素子集合を二つに分割する。第３図（
ｂ）では、カットライン２５で分割された素子集合２４
ａ、２４ｂを示している。
〔実施例］
次に、本発明の詳細な説明する。第１図は本発明の配置
位置決定装置の一実施例を示すブロック図である。
位置決定装置の一実施例を示すブロック図である。
論理接続ネットワーク格納部１は、論理接続情報を表す
論理接続ネットワークを格納する。
論理接続ネットワークを格納する。
最小コストフロー計算部２は、論理接続ネットワーク上
で最小コストフローを計算する。
で最小コストフローを計算する。
集合分割部３は、論理接続ネットワーク上の最小コスト
フローに基づいて素子集合を二つに分割する。
フローに基づいて素子集合を二つに分割する。
続いて、本実施例の動作を第２図の流れ図を参照して説
明する。
明する。
論理接続ネットワーク格納部１が、論理接続情報を表す
論理接続ネットワークを格納すると（ステップＳ１）、
最小コストフロー計算部２は論理接続ネットワーク上で
ソースにつながる仮想アークの容量を１としくステップ
Ｓ２）、論理接続ネットワーク上で最小コストフローを
計算する（ステップＳ３）。
論理接続ネットワークを格納すると（ステップＳ１）、
最小コストフロー計算部２は論理接続ネットワーク上で
ソースにつながる仮想アークの容量を１としくステップ
Ｓ２）、論理接続ネットワーク上で最小コストフローを
計算する（ステップＳ３）。
集合分割部３では、フロー量が非零のアークの集合によ
り素子集合が二つに分割できるか否かを判断しくステッ
プＳ４）、分割できれば終了し、分割できなければ、ス
テップＳ２で設定した仮想アークの容量に１を加えステ
ップＳ３にもどる（ステップＳ５）。
り素子集合が二つに分割できるか否かを判断しくステッ
プＳ４）、分割できれば終了し、分割できなければ、ス
テップＳ２で設定した仮想アークの容量に１を加えステ
ップＳ３にもどる（ステップＳ５）。
以上述べた通り本発明によれば、（最適な）最小コスト
フローに基づいて素子集合を分割するため、従来手法に
比べ解の質の向上がはかれる。
フローに基づいて素子集合を分割するため、従来手法に
比べ解の質の向上がはかれる。
第１図は本発明の配置位置計算装置の一実施例を示すブ
ロック図、 第２図は第１図の実施例の動作を説明するための流れ図
、 第３図は論理接続および素子集合分割の説明図、第４図
は論理接続ネットワークの説明図、第５図は論理接続ネ
ットワークの各アークのフロー量とコストの関係を表す
説明図である。 １・・・・・論理接続ネットワーク格納部２・・・・・
最小コストフロー計算部 ３・・・・・集合分割部 ２１・・・・・外部入出力端子 ２２・・・・・配置素子 ２３・・・・・配線 ２４ａ、２４ｂ・・・分割された素子集合２５・・・・
・カットライン ３１・・・・・ソース ３２・・・・・シンク ３３、３５．３６・ ・ ・仮想アーク３７・・・・・
ノード ３８・ ・ ・ ・ ・アーク
ロック図、 第２図は第１図の実施例の動作を説明するための流れ図
、 第３図は論理接続および素子集合分割の説明図、第４図
は論理接続ネットワークの説明図、第５図は論理接続ネ
ットワークの各アークのフロー量とコストの関係を表す
説明図である。 １・・・・・論理接続ネットワーク格納部２・・・・・
最小コストフロー計算部 ３・・・・・集合分割部 ２１・・・・・外部入出力端子 ２２・・・・・配置素子 ２３・・・・・配線 ２４ａ、２４ｂ・・・分割された素子集合２５・・・・
・カットライン ３１・・・・・ソース ３２・・・・・シンク ３３、３５．３６・ ・ ・仮想アーク３７・・・・・
ノード ３８・ ・ ・ ・ ・アーク
Claims (1)
- （１）入力として与えられる配置素子間の論理接続情報
を表す論理接続ネットワークを格納する論理接続ネット
ワーク格納部と、 前記ネットワーク上で最小コストフローを計算する最小
コストフロー計算部と、 前記ネットワーク上のフローの状態に基づき素子集合を
二つの集合に分割する集合分割部とからなることを特徴
とする配置位置決定装置。
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP2006435A JPH03211859A (ja) | 1990-01-17 | 1990-01-17 | 配置位置決定装置 |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP2006435A JPH03211859A (ja) | 1990-01-17 | 1990-01-17 | 配置位置決定装置 |
Publications (1)
| Publication Number | Publication Date |
|---|---|
| JPH03211859A true JPH03211859A (ja) | 1991-09-17 |
Family
ID=11638319
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP2006435A Pending JPH03211859A (ja) | 1990-01-17 | 1990-01-17 | 配置位置決定装置 |
Country Status (1)
| Country | Link |
|---|---|
| JP (1) | JPH03211859A (ja) |
Cited By (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JPH05128205A (ja) * | 1991-10-30 | 1993-05-25 | Kawasaki Steel Corp | 配置配線決定方法 |
-
1990
- 1990-01-17 JP JP2006435A patent/JPH03211859A/ja active Pending
Cited By (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JPH05128205A (ja) * | 1991-10-30 | 1993-05-25 | Kawasaki Steel Corp | 配置配線決定方法 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| EP1264451B1 (en) | Method and system for controlling data traffic in a network | |
| US4893303A (en) | Method and apparatus for parallel computation | |
| US5502816A (en) | Method of routing a request for a virtual circuit based on information from concurrent requests | |
| JPH0241053A (ja) | データ通信ネツトワークにおけるルート選択方法 | |
| JP2002199005A (ja) | 相互接続構造を設計する方法 | |
| Masson | Binomial switching networks for concentration and distribution | |
| US20120198093A1 (en) | Interconnection Fabric Connection | |
| EP0984655B1 (en) | Method for generating the optimal PNNI complex node representations for restrictive costs | |
| JPH03211859A (ja) | 配置位置決定装置 | |
| Girard et al. | Dimensioning of adaptively routed networks | |
| Wang et al. | Performance-driven interconnect global routing | |
| JP2605605B2 (ja) | パス帯域設定制御方法 | |
| CN114070803A (zh) | 一种数据流的传输方法、装置、存储介质及电子装置 | |
| Kakuda et al. | Automated synthesis of protocol specifications with message collisions and verification of timeliness | |
| JP2929978B2 (ja) | 自動配線方法及びその装置 | |
| JPH0345598B2 (ja) | ||
| JPH11163890A (ja) | 複数の情報を考慮したａｔｍ交換機におけるｐｎｎｉ経路計算システム | |
| JP3064315B2 (ja) | パケット交換網の伝送路帯域管理方式 | |
| JP2982866B2 (ja) | パケット通信網の帯域割当て方式 | |
| JP4009277B2 (ja) | 特定用途集積回路において自動伝送線路選択を行う方法、プログラム製品、および設計ツール | |
| Aida et al. | Optimal routing in communication networks with delay variations | |
| WO2024174588A1 (zh) | 转发路径确定方法、装置、电子设备以及存储介质 | |
| JP2611659B2 (ja) | 伝送容量とトラヒックフローの算出方法 | |
| CN121585604A (zh) | 数据路由方法、装置、电子设备、存储介质及程序产品 | |
| JPH04168835A (ja) | Ａｔｍ交換機のルーティング方式及びａｔｍ交換網のルーティング方式 |