JPS63254568A - 配置決定装置 - Google Patents

Abstract

(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。

Description

【発明の詳細な説明】 （発明の属する技術分野） 本発明は、相互に結合されたモジュールの２次元空間に
おける配置問題の近似解を求める装置に関するものであ
る。

この装置の具体的応用例として、プリント回路基板上に
ＩＣやＬＳＩを配置する問題、ＶＬＳＩチップに論理モ
ジュールを配置する問題、並列論理シミュレーションに
おいて２次元アレイプロセッサに論理ゲートを割当てる
問題などがある。

（従来の技術） 従来、配置決定は逐次計算機による自動化がなされてい
る。この場合、モジュールの初期配置を適当に（例えば
、ランダムに）与えれば、配置替えを行なって逐次改良
を行なっていたため、モジュール数ｎ（例えば、６００
００）の１．５乗に比例する計算機処理時間を要してお
り、この方法でｎの大きな問題を扱うことは時間が掛か
り過ぎ、実用上不可能であった。

第１５図は、ＵｅｄａやＣｈｙａｎが提案した従来の配
置決定装置の構成図である。

ｎ個のプロセシング・エレメント（ＰＥ）を２次元配列
した構造を持ち、各ＰＥは上下左右隣接ＰＥと通信する
機能、論理演算および算術演算する機能を有すること、
任意の１つのＰＥから全ＰＥに放送する（同じデータを
伝えること）バスを有していることが特徴である。

各ＰＥは１つのモジュールを担当し、自身のモジュール
の現配置における評価値（例えば、ネットに属する全モ
ジュールを含む最小の矩形領域の周辺長の和）を計算す
るのに必要な全ての情報を保持する。

例えば、隣接モジュールとのペア交換の場合、奇数列の
ＰＥと右隣の偶数列のＰＥが通信した後では、各ＰＥは
両方のモジュールに関する情報を持つことになり、モジ
ュール交換（ペア交換）後の配置改良度の計算を行なう
ことができる。これらの一連の処理は、極めて高い並列
度で実行できるものである。

しかし、各ＰＥが保持する情報の中には、自身でもなく
交換相手でもない第３、第４の、・・・・・・のモジュ
ールの配置情報が含まれている。

従って、１組みのモジュールのペア交換の都度。

その情報をすべてのＰＥに放送し、各ＰＥの保持する配
置情報を更新する必要がある。この部分は逐次処理であ
り、「全処理を逐次処理する」のに比べ、放送時間だけ
余計な時間を要した。このため、十分な高速化を実現で
きなかった。

また、　Ｂａｎｅｒｊｅｅはハイパーキューブ・コンピ
ュータを用いて並列配置を行なっている。

この装置はマイクロプロセッサを６４台配列し、ハイパ
ーキューブ接続しているため、かなり大型である。配置
改良度の計算をＵｅｄａ等と同様に行なっている。

更新データの放送は、通信路にハミルトン閉路を作り、
そこを次々とデータを流してやることで。

高速に行なっている。

この装置は大型であり、致方に及ぶ大量のモジュールに
ついて処理するには、１つのＰＥに複数のモジュールを
担当させることが実用上必要になる。この部分で逐次処
理となる。

このため、小型で高性能な装置が望まれていた。

［参考文献］ ■に、　Ｕｅｄａ、　ａｔ　ａｌ、、　”Ａ　Ｐａｒａ
ｌｌｅｌ　ＰｒｏｃｅｐｓｉｎｇＡｐｐｒｏａｃｈ　ｆ
ｏｒ　Ｌｏｇｉｃ　Ｍｏｄｕｌｅ　Ｐｌａｃｅｍｅｎｔ
”、　ＩＥＥＥＴｒａｎｓ、、　Ｖｏｌ、　ＣＡＤ−２
，Ｎｏ、１．　Ｊａｎ、、　１９８３■Ｄ、　Ｊ、　Ｃ
ｈｙａｎ、　ｅｔ　ａｌ、、　”Ａ　Ｐｌａｃｅｎ＋ｅ
ｎｔＡ１ｇｏｒｉｔｈｍ　ｆｏｒ　Ａｒｒａｙ　Ｐｒｏ
ｃｅｓｓｏｒｓ”、　２０ｔｈＤｅｓｉｇｎ　Ａｕｔｏ
ｍａｔｉｏｎ　ｃｏｎｆｅｒｅｎｃｅ、　１９８３■Ｐ
、　Ｂａｎｅｒｊｅｅ、　ｅｔ　ａｌ、、“Ａ　Ｐａｒ
ａｌｌｅｌ　Ｓｉｍｕｌａｔ−ｅｄ　Ａｎｎｅａｌｉｎ
ｇ　Ａｌｇｏｒｉｔｈｍ　ｆｏｒ　５ｔａｎｄａｒｄ　
Ｃｅ１ｌＰｌａｃｅｎｉｅｎｔ　ｏｎ　ａ　Ｈｙｐｅｒ
ｃｕｂｅ　Ｃｏｍｐｕｔｅｒ”、　Ｄｉｇｅｓｔｏｆ　
Ｉｎｔｅｒｎａｔｉｏｎａｌ　Ｃｏｎｆｅｒｅｎｃｅ　
ｏｎ　ＣｏｍｐｕｔｅｒＡｉｄｅｄ　　ｄｅｓｉｇｎ、
１９８６（発明の目的） 本発明の目的は、ペア交換の配置改良度の計算および配
置情報の更新を共に並列処理することで、相互に結合さ
れたモジュールの２次元空間における配置問題の近似解
を求める高速かつ小型の装置を提供することにある。

（発明の構成） 本発明は、相互に結合されたモジュールの２次元空間に
おける配置問題の近似解を、「所定の評価方法に従って
モジュール・ペア交換を評価し、それに基づいて可否を
判定し、可のものについては交換する」の一連の過程を
繰り返すことで求める装置において、 ネット（モジュール間を接続するもの、例えば信号線）
のエクステントをリプル転送を利用して求める手段と、
各モジュールがエクステントの端にある時、そのモジュ
ールの内側方向に所定の大きさの力が働いていると見做
して、そのモジュールに働く力を計算する手段と、交換
対象ペアについて、その２モジュールに働く力の向きと
大きさによってペア交換の評価値を求める手段とを備え
たことを特徴とし、 更に、複数ネットに対してスキャン・ベクトル〔エクス
テントの範囲を示すＸ軸（またはＹ軸）平行ベクトル〕
を並列に生成する手段と、複数のスキャン・ベクトルか
らＸ方向（またはＹ方向）のペア交換の評価値を並列に
求める手段と、複数のモジュールについてペア交換の可
否判定を並列に行なう手段と、可のものについてのペア
交換を複数のモジュールについて並列処理する手段とを
備えたことを特徴とする配置決定装置である。

本発明は以上のように、ペア交換を評価する手段が従来
技術と異なる。更に、ペア交換の評価を行なう手段、ペ
ア交換の可否を判定する手段、可のものについては配置
データを更新する手段、において並列処理がなされるこ
とが従来技術と大きく異なる。

（実施例） 〔実施例１〕 第１図は本発明の第１の実施例を示す図である。

前処理部１、後処理部８、エクステントを求める手段２
、モジュールに働く力を計算する手段３゜ペア交換の評
価値を求める手段４、ペア交換の可否を判定する手段５
、ペア交換に伴うデータ更新の手段６、繰り返し制御手
段７からなる。

前処理部１は、端末から投入されたデータやディスクの
データを処理し、エクステントを求める手段２のための
データを生成するまでの一連の処理を行ない、逐次計算
機で構成する。

後処理部８、は処理結果を端末に表示したり、ディスク
に格納する処理を行ない、逐次計算機で構成する。これ
以外の各手段２〜７は、すべて同一の構成を持つ。

第２図はエクステントを求める手段２の構成図を示す。

１２は記憶部、１３はインタフェース部、１４はＰＥア
レイ部、１５は制御部、１６は選択回路、１７〜２０は
データ線、２１は制御信号線である。

第３図は、ＰＥアレ１部１４の構成図であって、１０１
〜１１６はそれぞれ同一の構成を持つＰＥである。

１２６は制御信号線２１を各ＰＥに分配する制御回路、
１１７〜１２４はデータ線、１２５は制御信号線である
。

各ＰＥは上下左右の隣接ＰＥとの間で通信する機能を有
する。

第４図は、Ｐ　Ｅ　１１１の構成図であって、２０１゜
２０２、２０６は選択回路、２０３．２０５はレジスタ
、２０４は２ボ一トＲＡＭ、２０７はＡＬＵ、２０９は
制御回路である。選択回路２０１は隣接ＰＥと通信する
場合、データを上下左右隣接ＰＥのどれから受けるかを
選択する機能を有する。

また、全ＰＥの選択回路２０１．２０２を適当に設定す
れば、各ＰＥ内のレジスタ２０３を接続することができ
る。

このレジスタ群をシフトレジスタのように制御して、各
ＰＥが一斉に右（左、上、下）隣接ＰＥにデータを送る
ことができる（以後、シフトと略記する）。記憶部１２
を読み出し状態にし、レジスタ群を下（上、右、左）隣
接ＰＥにデータ転送すると、最上段（最下段、最左段、
最左段）ＰＥには記憶部１２より読み出されたデータが
、それ以外のＰＥには上（下、左、右）隣接ＰＥのデー
タが送られる（以後、シフト読み出しと略記する）。

レジスタ２０５は制御レジスタであって、各ＰＥに与え
られる同一の制御信号１２５を各ＰＥ内でローカルに修
飾する役目を持つ。これを利用して、例えば、特定の命
令の「実施する」「実施しない」をＰＥ毎に制御できる
。選択回路２０２が「選択回路２０１の出力ＪｒＡＬＵ
の出力」の選択をすることをＰＥ毎に制御できる。

レジスタ２０５を適当に設定し、選択回路２０１と２０
２を適当に制御すれば、あるＰＥではＡＬＵの出力を１
２２より出力しくこれを発信ＰＥという）、別のＰＥで
は他のＰＥから送られてくるデータをレジスタ２０３に
書き込むと同時に、１２２より出力する（これを受信Ｐ
Ｅという）ことができる（以後、リプル転送と略記する
）。

これを動作するには、前処理部１で逐次計算機からＰＥ
アレイ部用データ（ＰＥペア定義データ、各ＰＥに配置
されるモジュールの識別番号とそのモジュールに接続す
るネット識別番号のデータ）と制御部用データを記憶部
１２ヘインタフエース１３を介して送る。

制御部１５にはモジュール配置改善を行なうための制御
プログラムが内蔵されており、制御プログラムと記憶部
１２の制御部用データ（ＰＥペア定義データが複数ある
場合、その処理順、各ＰＥ定義データ毎の繰り返し数等
を含む）に従って、以後の処理を行なうような制御信号
を逐次発生する。

先ず、記憶部１２よりＰＥアレイ部用データをデータ線
１８を経由してＰＥ７１４部１４に送り（この動作は“
シフト読み出し″により実現できる）、ＰＥ内の２ポー
トＲＡ　Ｍ　２０４に格納する。

第５図は、リプル転送を用いて、１つのＰＥ列中に複数
の“１”が散在する時、その左端のＰＥのみを抽出する
方法を示す。

（ａ）が散在するＩｔ　Ｉ　ＩＩの例である。レジスタ
２０３を０に設定後、アレイ部左右端の接続線７，９を
解放し、（ａ）がパ１”のＰＥを発信ＰＥとし、他を受
信ＰＥとして“１″を右方向へりプル転送した結果が（
ｂ）である。

（ｃ）は（ａ）と（ｂ）の論理差ａ−ｂの結果である６
（ｃ）は（ａ）の左端のＰＥを示す。

第６図は、リプル転送を用いて、１つのＰＥ列中に１つ
でもｒｅ　１　ｙｙがあればその列全体をＩＩ　１７１
とし、全く′１″が無い場合に限り、その列全体を′０
″にする方法を示す。

アレイ部左右端が選択回路６を介して接続した状態で、
レジスタ２０３を０設定後、（ａ）が“１″のＰＥを発
信ＰＥとし、他を受信ＰＥとして“１”を右方向へりプ
ル転送した結果が（ｂ）である。この時、（ａ）に全＜
　ｔ（１ｊｔがなければ、リプル転送の結果は全ＰＥで
Ｏである。

第７図（ａ）は基板上のモジュール配置を示す。

スロットは基板上のモジュール配置可能位置である。

（ｂ）は対応するＰＥアレイ上のモジュール配置を示す
。

各ＰＥにはモジュール識別番号（ここではネット番号と
区別するため、アルファベットで示す）とそのモジュー
ルに接続するネットの識別番号がついている。図ではモ
ジュールａ　＝　ｊのみ記し、他は記述を省略した。

第７図（ｂ）はＰＥアレイ部の初期状態を示す。

配置の逐次改善は第８図（１つのＰＥ対を１本の線で結
ばれた２つの丸で表現）のように、複数の横方向ＰＥ対
の並列配置換え、次に複数の縦方向ＰＥ対の並列配置換
えを繰り返して行なわれる。

初めは遠く離れたＰＥと対を組むが、次第に近傍のＰＥ
と対を組むように制御される。

まず最初に、特許請求の範囲第（１）項記載のペア交換
の評価方法を、第７図における横方向ＰＥ対の並列配置
換えを例に説明する。

第７図のネット２，４のエクステント（そのネットに接
続関係のある全モジュールを覆う最小の２次元帯状領域
）は手段２で求められ、それを第９図に示す。

ペア交換すべき２つのモジュールに接続する全ネットの
エクステントについて、その横方向幅の総和のペア交換
による減少量でペア交換を評価する。そのために、エク
ステントの端にあるモジュールについてだけ大きさが１
の力が内側に働いているとする。

右側方向の力を正とすると、各モジュールに働く力は第
１０図のようになる。これはモジュールに働く力を計算
する手段３で求められる。

ペア交換の評価は評価値を求める手段４により行なわれ
、交換ペアの交換される方向と、働く力の積和として求
める。

第１０図のモジュールａとｆを交換ペアとすると、第１
１図のように積和は３である。ペア交換の可否を判定す
る手段５により、評価値が正の時交換すべきだと判定さ
れる。

ここで、エクステントは１ネツトずつ順次水める。

まず、第６歯の方法で、縦方向の各ＰＥ列でＰＥ列中に
１つでも“１”があれば列全体を′１″とする処理を行
ない、次に、第５図の方法で、各横方向ＰＥ列の左（又
は右）端ＰＥを抽出する。

この結果が第９図に示したエクステントである（ネット
２のエクステントは１図示の都合上途中までしか示して
ないが、正しくは同じ位置で上辺から下辺に達するもの
である）。

エクステントが決まれば、エクステント左端上のＰＥは
＋１の演算を、右端上のＰＥは−１の演算を、他は以前
の値を保持することで、第１０図のようにモジュールに
働く力が求まる。

更に、交換相手ＰＥとデータの交換をしくシフトにより
実現）、第１１図のように評価値の計算ができる。

ここでは、横方向のペア交換の説明をしたが、縦方向の
ペア交換も同様である６ 〔実施例２〕 第１２図は、本発明の第２の実施例の構成図であって、
前処理部３０１、スキャン・ベクトルを求める手段３０
２、モジュールに働く力を計算する手段３０３、ペア交
換の評価値を求める手段３０４、ペア交換の可否を判定
する手段３０５、ペア交換に伴うデータ更新の手段３０
６、繰り返しを制御する手段３０７、後処理部３０８よ
りなる。

３０１．３０４〜３０８はそれぞれ１．４〜８と同じで
あり、３０２，３０３が第１の実施例と異なる。

特許請求の範囲第（２）項記載のペア交換の評価方法を
、第７図における横力向ＰＥ対の並列配置換えを例に説
明する。

前述の実施例が、エクステントの左右端を１ネツトずつ
順次求め、左端では＋１、右端では−１する処理を、１
ネツトずつ逐次処理していたのに対し、特許請求の範囲
第（２）項の方法はこれらをパイプライン処理すること
が特徴である。

第１３図は、第７図を上辺から下辺に向って走査し、複
数ネットに対する複数のエクステントについてそれぞれ
スキャン・ベクトル（エクステントの範囲を示す横方向
ベクトル）を求める方法を示す。（ａ）の下方の図はＰ
Ｅアレイ部であって、第７図（ｂ）の上辺をこの図では
左斜辺に示す。

（ａ）の上方の図は、ネット識別番号順に並んだ１次元
ベクトル（初期値Ｏ）が、ＰＥアレイ部を上辺から下辺
に向って移動する過程で、対応するＰＥ位置に１回でも
同一ネット識別番号が検出されれば値１を、それ以外な
らば値Ｏを持つ処理を示す。（ｂ）は処理結果であり、
記憶部１２に記憶する。

この処理において、各１次元ベクトルに付随したネット
識別番号は、各ＰＥ上を通過する１次元ベクトル数より
求められる。

次に、記憶部１２よりＰＥ７１４部１４に複数ネット分
の１次元ベクトル（ｂ）を入力し、第５図の方法を適用
し、その結果を記憶部１２に格納したのが（Ｑ）、（ｄ
）である。（ｃ）、（ｄ）はスキャン・ベク。

トルである。以上の処理は手段３０２で行なわれる。

次に、スキャン・ベクトルをＰＥアレイ部上辺より入力
し、それを下辺に向って順次シフトする。

その過程で、スキャン・ベクトルのネット識別番号に一
致するネット番号を含むＰＥでは、当該スキャン・ベク
トル中の１の数を累算する〔第１４図（ａ）〕。

このようにして、各ＰＥがエクステントの左端、右端の
出現回数のデータを持つゆ これを（ｂ）、（ｃ）に示す。これは手段３０３により
行なわれる。

以上の説明において、手段２〜７を異なるハードで実現
していたが、１つのハードを多重使用して実現できるこ
と、ＰＥ内の論理演算および加減算は、ＡＬＵ２０７を
用いて行なうこと、リプル転送以外のＰＥ間のデータ転
送はシフトにより行なわれることは言うまでもない。

また、ＰＥ内蔵のネット識別番号とスキャン・ベクトル
付随のネット識別番号が一致したＰＥでのみ所定の演算
を行なうこと、データ更新時に選択的にデータ更新を行
なうことは、レジスタ２０５を用いて特定の命令を「実
施する」「実施しない」の選択をローカルに指定できる
ことにより可能である。

上述のように装置を構成した場合、複数ビット長のデー
タは配置データ（モジュール識別番号とそのモジュール
に接続するネットの識別番号）のみで、それはシステム
起動時に記憶部１２からＰＥ７１４部１４に送られる他
は、配置データ更新時にＰＥ間で並列データ転送される
だけで、他の１ビツト長データ（スキャン・ベクトルデ
ータ、上・下・左・右端の各データ）に比べ、データ転
送される頻度、距離ともに極めて少ない。

このため、ＰＥ間のデータ線１１７，１１８，１１９，
１２０゜１２１．１２２，１２３，１２４を１本として
も、十分な性能が発揮できる。

ネット識別番号の生成や一致検出は、２ポートＲＡ　Ｍ
　２０４とＡＬＵ２０７を複数ビット長とすれば高速処
理できる。すなわち、２ボ一トＲＡＭは制御信号に応じ
て「１ビット幅で読み書きできる」「複数ビット幅で読
み書きできる」構成を持つことで、装置の小型化、高性
能化が得られる。

これらの特徴を有するＰＥを、基板の大きさに応じて適
当な数装置して、上記の処理を行なうことができる。

また、ＰＥの配置数を減らして、１つの基板を幾つかの
部分に割分して処理する折りたたみ処理も可能である。

また、スキャン・ベクトルの格納や右・左・上・下端デ
ータの格納のために、記憶部１２の代りにＰＥ７１４部
１４の２ボ一トＲＡＭ２０４を利用できることは当然で
ある。

実施例では、第２図のように記憶部がＰＥアレイ部の４
辺と選択的に接続できる例を示したが、記憶部をＰＥア
レイ部の２辺のみとすることも可能である。

特許請求の範囲第（２）項では、この場合、各ＰＥには
、前記の通り「モジュールの識別番号とそのモジュール
に接続するネットの識別番号」のデータを横方向ＰＥ対
の並列配置用と、縦方向ＰＥ対の並列配置用に２組用意
する必要がある。この場合、後者データを前者データの
９０°回転したものとすれば、前者について行なってき
た以上の動作説明を後者についてそのまま適用できる。

（発明の効果） 以上説明したように１本発明による装置は、同一構成で
かつ極めて限定された通信機能を持つＰＥを規則正しく
２次元配列した構成を持つので。

容易にＬＳＩ化でき、装置を小型にできる。

また、配置換え評価、データの更新のいずれも並列処理
するので、極めて高速にモジュールの配置換えを行なう
ことができるという利点がある６本発明をＶＬＳＩチッ
プ上の論理モジュールの配置決定に利用する場合、論理
モジュールをランダムに並べたデータを与えれば、論理
モジュール間の配線長を短くするように並べ換えた論理
モジュール配置が、極めて高速に得られる。

【図面の簡単な説明】

第１図は本発明の第１の実施例を示す図、第２図はエク
ステントを求める手段の構成図、第３図はＰＥアレイ部
の構成図、 第４図はＰＥ構成図、 第５図は列中に散在する複数の１（１Ｈの中から最左端
を抽出する方法の説明図、 第６図は列中に１つでもＩＩ　Ｉ　ＩＩがあれば列全体
を“１″とし、それ以外は“０”とする方法の説明図、
第７図はＰＥアレイ部と基板との関係を示す説明図、第
８図はＰＥペアとその処理順を示す説明図、第９図はエ
クステントの説明図、 第１０図はモジュールに働く力の説明図、第１１図は評
価値計算方法の説明図、 第１２図は本発明の第２の実施例の構成図、第１３図は
スキャン・ベクトル生成の説明図、第１４図はモジュー
ルに働く力の計算に用いられる左端および右端出現回数
生成の説明図、第１５図は従来の配置決定装置の構成図
である。 １　・・・前処理部、 ２・・・エクステントを求める手段、 ３　・・・モジュールに働く力を計算する手段、４　・
・・ペア交換の評価値を求める手段、５　・・・ペア交
換の可否を判定する手段、６　・・・ペア交換に伴うデ
ータの更新の手段、７　・・・繰り返し制御手段。 ８・・・後処理部、 １２・・・記憶部、１３・・・インタフェース部。 １４・・・ＰＥアレイ部、１５・・・制御部、１６・・
・選択回路、１７．１８．１９．２０・・・データ線、
２１・・・制御信号線、 １０１〜１１６・・・ＰＥ、１１７〜１２４・・・デー
タ線、１２５・・・制御信号線、１２６，２０９・・・
制御回路、２０１．２０２，２０６・・・選択回路、２
０３．２０５・・・　レジスタ、 ２０４　・・・　２ポ一トＲＡＭ、２０７　・・・　Ａ
ＬＵ、３０１・・・前処理部、 ３０２・・・スキャンベクトルを求める手段、３０３・
・・モジュールに働く力を計算する手段、３０４・・・
ペア交換の評価値を求める手段、３０５・・・ペア交換
の可否を判定する手段、３０６・・・ペア交換に伴うデ
ータ交換の手段、３０７・・・繰り返しの制御手段、 ３０８・・・後処理部。 特許出願人　日本電信電話株式会社 沖電気工業株式会社 第２図 １７、旧、＋９，２０　　　テ゛−７に隈２１ろ゛）御
格号携 第３図 旧 第４図 第５図 第６図 第７図 （ａ）　　基１反とのモシュー心配置 （ｂ）　　ＰＥアレｌｌヱ乃七ジューνし白ｎｉテ′−
夕第８図 （０）資ｊ魂３う禮方朗ＰＥ村　　　ｆｂｌ死敵３う販
オ燭ＰＥクヤ（Ｃ））ε１ｌｖ１．ｉｈＰＥＭ　（ｄｌ
’ｊＥＩｌｉｔｌ＊ＪＩＸｌａｌＰＥｔ＋（ｅ）”ｊｌ
ｌのｆｉｔＵＰＥＭ　　　　（ｆ）５Ｅａｌ＊Ｈｔ、Ｓ
ＵＰ！Ｊ＆第９図 第１０図 第１１図 イ雪力　く　２ラ　　　＋２　　　　　　　　　　　　
　　　　　　　　　　−１文硬方旬　　＋１　ち伊１］
へ　　　　　　　　　　　−１九へ！１１へ（＋２）　
　　（＋ｌｌ　　　　　　　　　　　十　　　　　　　
Ｆ−１＋＋−１１−３第１３図 （ｂ）　　生成’Ｋｆこ　１よ元へ゛７トＬ’ｃ’４瓦 忙）　九塙テ゛−夕 （ｄ）　　　ち　堝テ゛−タ 第１４図 （ｂ）左Ｉｖ５出現回数 第１５図

Claims (2)

【特許請求の範囲】
1. （１）相互に結合されたモジュールの２次元空間におけ
   る配置問題の近似解を、『所定の評価方法に従ってモジ
   ュール・ペア交換を評価し、それに基づいて可否を判定
   し、可のものについては交換する』の一連の過程を繰り
   返すことで求める装置において、 ネット（モジュール間を接続するもの、例えば信号線）
   のエクステントをリプリ転送を利用して求める手段と、
   各モジュールがエクステントの端にある時、そのモジュ
   ールの内側方向に所定の大きさの力が働いていると見做
   して、そのモジュールに働く力を計算する手段と、交換
   対象ペアについて、その２モジュールに働く力の向きと
   大きさによってペア交換の評価値を求める手段とを備え
   たことを特徴とする配置決定装置。
2. （２）複数ネットに対してスキャン・ベクトル〔エクス
   テントの範囲を示すＸ軸（またはＹ軸）平行ベクトル〕
   を並列に生成する手段と、複数のスキャン・ベクトルか
   らＸ方向（またはＹ方向）のペア交換の評価値を並列に
   求める手段と、複数のモジュールについてペア交換の可
   否判定を並列に行なう手段と、可のものについてのペア
   交換を複数のモジュールについて並列処理する手段とを
   備えたことを特徴とする特許請求の範囲第（１）項記載
   の配置決定装置。