JPS58153A - 配線径路決定方法 - Google Patents

Abstract

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

Description

【発明の詳細な説明】 技術分野 本発明は大規模集積回路（ＬＳＩ）及び超大規模集積回
路（ＶＬＳＩ）の物理的設計の分野、特にチップ上に形
成された回路間の相互接続及び配線径路決定（ｗｉｒｅ
　　ｒｏｕｔｉｎｇ　）に関するワより具体的には、セ
ルから構成されたＬＳＩ又はＶＬＳＩ回路構造における
配線径路を決定するための装置が開示される。但しそれ
らのセルは論理ゲートとして機能する電子デバイスか□
ら成り、セルの群はフリップ・フロップ、シフトレジス
タ等トして機能するように相互接続される。本発明の装
置は、ｎ個（ｎは整数）の同一の多ポート・プロセッサ
と通信する管理コ／トローラ？含み、１つのプロセッサ
は谷セルに専用に割り当てられ、各セル間の配線径路を
決定するっ各プロセッサは同時にその４つの隣接プロセ
ッサと通信し、セルの配列中の１点から次の点）のチャ
ネル径路？決定するっ但しチャネル径路は垂直及び水平
の径路を含むっ大局的なチャネル径路の決定に続いて、
配線径路に関する正催な垂直及び水平のトラックが割り
台てられ、でしてオーバーフロー・ルーティングが考慮
てれる。タイミング解析、配置、形状生成及び検査は、
適当な方式でその並列計算能カケ賢明に用いる事によっ
て行なう事ができる。

１０００個以下のセルを有する全てのＬＳ　Ｉｌｌ造の
物理的設計において現行の方式は、長時間、高速計算機
全使用する必要があり、例えば２０分から１時間のＣＰ
Ｕ時間を要する。次世代のＶＬＳＩにおいて、１５００
０〜１５００００の接続配線を持つ５０００〜５ｏｏｏ
ｏ回路のマスク・スライス・チップの場合、２〜５時間
以上のＣＰＵ時間を要する。従って非専用システムの場
合少なくとも１日のターン・アラワンド時間がかかる可
能性がある。技術的変更により同じチップに付き数回配
線決定を繰り返さなければならない可能性を考慮すると
、この時間？大幅に減少させる事は非常に利益がある。

物理的設計に費やされる全時間及びシステム開発時間の
減少は、製造コストの低下及び他の市場的利益全生み出
す。より迅速な配線決定は、ターン・アラウンド時間の
減少によシ、より迅速々技術的変更の能力を提供する。

この高速配線と共に対話式設計能力により、全設計がよ
り短時間に完了する。

現在使用されている多くのＬＳＩチップは、構成要素及
び配線のレイアクトに関して対称的な構造を持ち、それ
らのチップはゲート・アレイ又はマスク・スライス・チ
ップと呼ばれている。マスク・スライス・チップは、１
つの面の能動回路領域の配列及びこれらの能動領域の間
全直交する方向に走る別の面の配線チャネルから成る。

装置中の種°々の配線の適当な径路を決定する物理的設
計オートメーンヨン・システムの部分は配線演算（ｗｉ
ｒｉｎｇ　ｏｐｅｒａｔｉｏｎ）と呼ばれる。

配線演算に関与する機能の注意深い解析により、現在直
列に実行されている多くの演算が実際は同時に実行し得
る事が示される。従って演算の能率は、ホスト・マシン
が同時並行演算全実行できない事によって制限されてい
る。

配線演算は、多数回反復されるいくつかのステップを含
み、これらの演算は必ず通常のＣＰＵにおける非常に多
数の命令が関係している。これらの演算は頻繁に起きる
ので、もしこれらの特殊な演算がスピード・アップされ
るならば配線の速度が非常に改善できる。これらの状況
を考慮して、多くの演算を並列に実行できる特性を持つ
専用の高速計算機を用い、ＣＰＵの配線演算の能率？低
下させている反復的動作を、複数の処理要素の各々に実
現された特殊化されたノ・−ドウエアによって実行する
事によって、配線の計算が効率的計つ経済的に実行され
る。

本発明によるＶＬＳ　Ｉ物理的設計装置は、マスク・ス
ライス・チップ・イメージに対応するｎ×ｎのマトリッ
クスの形に配列された複数のマイクロプロセッサ様の特
殊な処理要素（ＳＰＥ）から構成されたアレイ構造″ｆ
ｒ：有する。升ツブの各セル毎にＳＰＥが関連付けられ
、各ＳＰＥは、マスク・スライス・チップ上の隣接する
能動構成要素及びチャネル交差に対応する。各ＳｐＥは
論理及びメモリの両者全音み、従ってマイクロプロセッ
サ様の要素である。通常の汎用のマイクロプロセッサと
違って、各ＳＰＥは、反復的に実行される汎用計算機に
おける命令の系列に対応する特殊比された機能をそのノ
・−ドウエアに組み込まれている。

従ってＳＰＥは最小限のマシン・サイクル、好マしくは
１マシン・サイクルで各命令系列を実行するように設計
できる。カスタム設計により、ＳＰＥは約１００本のピ
ン金有し１００ｎｓ以下のサイクル・タイムを持つ単一
のＶＬ、ＳＩチップとして反計する事ができる。各ＳＰ
Ｅは管理制御ユニットに加えて、その４つの隣接ＳＰＥ
とだけ通信する。

ＳＰＥの配列に対する管埋制御は階層的でも又大局的で
も良い。前者の場合、局所的なＳＰ’Ｅの群が少数の配
列から成る制御要素の１要素と通信し、さらに制御要素
は相互間で及び高位の制′＃Ｊ機構に通信する。大局的
な方式の場合、全てのＳＰＥが直接中央のスーパバイザ
と通信し、スーパバイザが情報のローディング及びアン
ローディング並びにタスク削り当てを制御する。中央ス
ーパバイザは個々の要素又は要素の群をアドレスすると
同様に回報通信できなければならない。

背景技術 標準的セルの集積回路に関するマス・パターンの製造に
関していくつかの技術が知られているが、以下に示す技
術はＶＬＳ　Ｉのセル間の配線技術に係るものではない
。

米国特許第４０９３９９０号明細書は、標準的セルから
成る集積回路に関するマス・パターンの製造方法の１例
を示している。セルは最初に、群の間に出来るだけ少数
の接続しか存在しないように所定の数のセルの群に分け
られる。各群の場所的要求は等しい。

米国特許第３６５３０７０号明細書は、プリント回路技
術によって製造される論理回路に関するアート・ワーク
の製造方法を示している。このアート・ワークは、パッ
ケージ・ルーチン、配置ルーチン、径路ルーチン及び検
査ルーチンを実行するようにプログラムされたデータ処
理機械によって作成、される。

以下の米国特許明細書及び防衛特許出願（Ｄｅｆｅｎｓ
ｉｖｅ　Ｐｕｂｌｉｃａｔｉｏｎ）は集積回路に関する
マ＼ス・パターン等の種々の製造技術を示している。

米国特許第３５６７９１４号；第３５７５５８８号：第
３６０１５９０号；第３６０３７７１号；第３６５３０
７１号：第ｚ、　６．５３０７２号：第３６５４６１５
号：第５９６８４７８号；及び防衛特許第Ｐ９４０．．
０２０号。

波動方程式、画像処理の問題等を解くためにデータ・マ
トリックスに対して変換を行なうために矩形のディジタ
ル論理アレイを用いるための種々の技術が知られている
。しかしながら半導体構成要素の物理的設計及び配線径
路決定に関してアレイ処理を応用した例は知られていな
いつ米国特許第４２１５４０１号明細書は、中央プロセ
ッサの制御の下にデータ・マトリックスに対して順次の
変換演算を行なう、相互接続された複数の同一のセル’
に！する型のディジタル・アレイ・プロセッサを、より
具体的には独特な形式のセル購Ｆｊｙ、及び処理セル間
の相互接続を開示しているうそのアレイ・プロセッサは
、嚇−命令多数データ・フロー（ＳＩＭＤ）マシンであ
って、順次シフトンジ、スタによってその４つの隣接セ
ルと通信し、従って同時アクセスを許をない。制御は、
ｖＬＳ■設計に必要な個体本位の自律的なものではなく
、中央集権化されたものである。アレイ内の内部ノード
は独立に選択する事はできず、即ち独立なＸ／Ｙ選択機
構は存在しない。従ってこのプロセッサのアレイ１ｄＶ
ＬｓＩ又は物理的設計には有用ではない。

米国特許第５９７９７２８号明細書は、通常の計算機の
周辺装置として動作可能なアレイ・プロセッサを示して
いるう各処理要素はピット・シリアル方式で組織され、
シングル°ビットのレジスタ及びビット・アドレス可能
な記憶装置を有し、アレイはマイクロプログラムされた
主制御ユニットによって鯖御される。従ってこの装置は
上記装置と同様のＳＩＭＤマシンである。この装置は、
与えられた時間に複数の列及び行孕選択するのではなく
、一時にアレイ中の１つの行及び１つの列を選択する。

ＳＩＭＤ処理装置はＳＯＬＯＭＯＮ計算機（Ｓｌｏｔｎ
ｉｃｋ他、Ｆａｌｌ　Ｊｏｉｎｔ　Ｃｏｍｐｕｔｅｒ　
Ｃｏｎｆｅｒｅｎｃｅ１９６２、ｐ、　９７　：　Ｇｒ
ｅｇｏｒｙ他、ＩＥＥＥＴｒａｎｓａｃｔｉｏｎｓ　ｏ
ｎ　Ｅｌｅｃｔｒｏｎｉｃ　Ｃｏｍｐｕｔｅｒｓ。

Ｉ）ｅｃｅｍｂｅｒ　１９６３、ｐ、７７４）に説明さ
れて−いる。この装置は比較的単純な処理要素のアレイ
から成り、その各々はピント・シリアル方式の入力デー
タに灯して算術演算？行なうように構成される。この装
置の発達したものはＩＬＬＩＡＣ■計算機（Ｂａｒｎｅ
ｓ他、Ｉ　ＥＥＥ、　Ａｐｒｉｌ　　１９７２、ｐ、３
６９）である。

Ｎｏｒｔｈ−Ｈｏｌｌａｎｄ　Ｐｕｂｌｉｓｈｉｎｇ　
Ｃｏｍｐａｎｙ、　１９７９年刊のＣｏｍｐｕｔｅｒ−
Ａｉｄｅｄ　Ｄｅｓｉｇｎ　　ｏｆＤｉｇｉｔａｌ　Ｅ
ｌｅｃｔｒｏｎｉｃ　Ｃ４ｒｃｕｉｔｓ　ａｎｄ　Ｓｙ
ｓｔｅｍｓ”の中の５ｔｅｐｈａｎ　Ｃ，Ｈｏｆｆｍａ
ｎによる”　ＡｕｔｏｍａｔｉｃＧａｔｅ　Ａ１１ｏｃ
ａｔｉｏｎ　Ｐｌａｃｅｍｅｎｔ　ａｎｄ　Ｒｏｕｔｉ
ｎｇ”と題する記事は、ＶＬＳＩ回路網のための自動的
ゲート割ｇ当て、配置及び配線経路決定に関して用いら
れるアルゴリズムを示している。このアルゴリズムは１
度に１つのネッＩｆ経路決定し、将来の経路の経路決定
可能性に対する現在の経路の結果全考慮しない。

本発明によれば、セルから構成されるＶＬＳ　Ｉ回路構
造における配線経路を決定する装置が示される。そこで
は複数のネットに関する複数の経路が同時に考慮され、
混雑評価を行なう事によって他の経路の経路決定可能性
（ｒｏｕｔａｂｉｌｉｔｙ　　）を考慮した所定の経路
が得られる。これは、１つのプロセッサがＶＬＳ　Ｉチ
ップの各セルに専用に割り当てられた、１司−のマルチ
・ポート・プロセッサの配列と通信する管理ユニットに
よって達成さレル。Ｍ　Ｉ　ＭＤモードで動作する各プ
ロセッサＵその４つの隣接プロセッサと同時に通信し、
混雑評価全同時に実行し且っＶＬＳ　Ｉアレイの１点か
ら次の点へのチャネル経路を決定する。但しチャネル経
路決定は垂直及び水平な経路を含む。

発明の開示 論理素子の配列から成る大規模集積回路構造の物理的設
計のための装置が示される。管理装置が同一のマルチポ
ート処理装置と通信し、そのような処理装置の１つは種
々の論理素子の間の配線経路を決定するために各論理素
子に専用的に割り当てられている。各処理装置はその４
つの隣接する処理装置と同時に通信し、配列中の１点か
ら他の点へのチャネル経路環？決定するために種々の計
算？行なう。但しチャネル経路は垂直及び水平な経路ケ
ゴむ。最適のチャネル経路の決定に続いて、垂直及び水
平の正確な経路が次に決定され、そしてオーバーフロー
・ルーティングが考慮される。

発明ケ実施するための最良の形態 基板上に形成された論理装置の配列を相互接続するため
に用いられる、マルチポート・プロセッサの／ステム全
管理ユニットと共に示す。第１図全参照すると、ｎＸｎ
の配列が示され、行と列との交点にある論理装置は論理
サービス端子（ＬＳＴ）と呼ばれる複数個の端子（例え
ば０．１．２．３と番号の付σれた４つの端子）を含む
。この論理装置及び配列中の他の論理装置はレジスタ、
フリップフロップ、及びＮＡＮＤ、０ＲＮＮＯＲ等のゲ
ート回路でも良い。例えば図中の装置は６人力ＮＡＮＤ
装置又１−１：４端子を有する何か他の装置でも良い。

この端子の数は１例であって、ある論理装置は４以外の
端子？持つ事もある。例えばインバータの場合、４つの
端子のうち２つしか使われない。各論理装置に付随して
、順次の層に水平及び垂直の配線トラックが設けられる
。）ＬＳＴの直接上部には絶縁層が存在する。絶縁層の
上には、垂、直な配線が付着され得る。もし論理装置上
のＬＳＴのいずれか？垂直配線に接続する必要があれば
、垂直なビン又はバイアを形成し、絶縁層を経て垂直配
線１ＬｓＴに接続する。垂直配線は０〜７の番号が付け
られているが、この番号は例であって垂直配線の数はこ
れよシも少なくても又多くても良い。この上にざらに他
の絶縁層が設けられ、この第２の絶縁層の上に水平配線
が付着される。

次にこれらの水平配線は、水平配線と垂直配線との交点
に挿入されそれらの間の絶縁層？貫通するビンあるいは
バイアによって、垂直配線に接続される。これらの回路
製造技術は当分針で周知の事でアシ、本発明の本質は各
論理装置間の配線経路の決定にあるので、詳しくは説明
しない。４つの水平配線トラックＡ、３　ｃ及びＤが示
されているが、４・発明全実施する時それ以外の数の配
線トラックを用いる事もでさる。ここでチャネルとは、
配列中の論理装置に付随する複数の配線トラックケ意味
する。例えばトラックＯ〜７は第１図に示したチップの
垂直チャネル全購戎し、トラックＡ、ＢｌＣ及びＤは水
モチャネル全構成する。装置及びその隣りのチャネル交
点は４つの境界を持ち、そのような境界金有する格子領
域は配列のセルと呼ばれる。

以前に述べたように、セルは配列中の行及び列の位置に
よって識別される。そのような論理装置の各々に付さ、
専用多ボート処理装置（ＳＰＥ）が存在する。ＳＰＥの
動作を説明すると、各ＳＰＬは制御装置とも呼ばれる管
理計算機と通信する。

制御装置は各ＳＰＥにそれが必要とする情報を与え、各
ＳＰＥが制御装置によって指定された機能を終えると、
制御装置はＳＰＥから情報を受は取る。種々の論理サー
ビス端子（ＬＳＴ）ｉ接続する配線経路ｔｆ　Ｓ　Ｐ　
Ｅがいかにして決定するかは、後述する。

以前に示した通り、配列中の各セルは水平及び垂直のチ
ャネル並びにチャネルの各交点の能動回路素子から構成
される。各チャネルは特定の数の配線トラックを有し、
その上に各回路要素間において各ＬＳＴに至る信号配線
を決定しなければならない。各セルは隣のセルとの間に
４つの境界を有し、その境界により分割された格子領域
はセルと呼ばれる。１つのＳＰＥは１つのそのようなセ
ル？表現する。

そのようなチップの配線における最も重要な段階は、配
線すべき各ネットに関する大局的なチャネルの割り当て
である。ネットとは、配線接続によって電気的に共通に
でれるべき端子点と定義される。大局的配線は、所定の
配線がどの具体的なトラックに割り当てるかに無関係に
、利用可能なチャネル？経て全てのネットｉ経路決定す
る。大局的割り当ての主な拘束はチャネル容量、即ち各
セル境界における利用可能なトラック数でるる。

目標は、チャネル容量に反する事なく全配線長を最小化
するように全てのネットヲ経路決定する事である。さら
に、０Ｔｑ’ｅならば、次の正確なトラック割り当ての
過程を容易にするために、残りのチャネル容量ｆｄ大叱
する、即ちトラックの利用率を均等化するという付加的
目標が存在する。大局的配線ば、後述する非線型コスト
迷路走行法を用いて行なわれる。この大局的経路決定過
程は、最短到達ＯＴ能距離に迂回限界（ｄ）を加えたも
のの範囲内で、ノース配線から７７２点への最良コスト
の経路を発見する。

製造技術の急速な進歩に、１辺が約６ｍｍ以下のチップ
上に数万個の直子回路金載せる事を現在可能にしている
。そして集積ｆヒのレベルは少なくとも近い将来におい
ては高くなり続ける事が予想σれる。しかしながら、こ
の洗練でれた技術とこの技術ヶ利用するために利用でさ
る道具との間にはギャップが存在している。物理的設計
とは、相互接続された論理ゲートによって表わされたデ
ィジタル・システムの設計を、そのシステムのための１
つのチップ又は１組のチップ全製造する時に使われるべ
き１組のマスクに関するパターンに変換する技術を言う
。物理的設計のための道具は、一般に、種々の変換のス
テップ？助けるソフトウェア・パッケージの形式を取る
。その３つの共通な別々の−といっても決して無関係で
はないが−ステップは分割、配置及び配線である。分割
とは、単一のチップが全体の設計全音み得ない時に、大
きな設計の一部を異なったチップに割り当てる工程の事
である、また配置工程では、チップの構成要素、普通は
ゲート全チップ内に配置する。

しばしばそれらの構成要素が配置され得る位置は明確に
定まったスロットであって、それらにその構成要素を相
互接続するための配線即ち金属セグメントが通る事ので
きる領域によって互いに隔てられている。そのような構
造がスロットの矩形配列の形を収る時、それはゲート・
アレイ又はマスク・スライス・チップと呼ばれる。また
相互接続のために構成要素間の空間ケ割り当てるのに用
いられるアルゴリズムは配線パッケージに含まれる。

物理的設計の道具と進歩する技術との間のギャノブは、
分割、配置及び配線のためのアルゴリズムの性能がチッ
プ上の構成要素の数の線型関数ではなく、チップの複雑
での増大と共に次第に悪ｆヒするという事実によって生
じている。また速いアルゴリズムは一般に良好なレイア
ラトラ作製するのに成功する事が少ない。

配＠化力を犠牲にする事なくアルゴリズムのスピード紫
改善する１つの方法は、そのアルゴリズムの実行に高速
の機械ケ使用する事である。既存のプログラム？より速
く実行するために新しい世代の高速汎用計−機を待つの
は容易である。しかしながら、ハードウェアが物理的設
計アルゴリズムの特別な性質のあるものケ利用している
機械？設訂する事は、より効率的である。この事孕、配
線工程？考察する事によって説明する。

ｎＸｎの大きさの２次元マ）　ＩＪラックス形に構成さ
れた計算機の配列紫考える。各計算機はプロセッサ　メ
モリ・ユニット、隣接計算機（境界にある場合？除けば
４つ）の各々への１つのポート及び制御装置と呼ばれる
付加的計算機へのリンクから成る。またＸ選択線及びＸ
選択線は、制御装置が配列中の任意の所望のノード又は
ノードの部分集合にアクセスする事を可能にする。ざら
に各ノードの計算機のメモリは、ｎＸＨの大きざのマス
ク・スライス・チップ中の対応する回路セルについての
完全な情報を保持しているものと仮にする。このような
計算機の複合体は数年前は考えらｎなかったでろろうが
、マイクロプロセッサの出現がそのような方式全今日で
は安価で実用的なものにしている。そのようなアーキテ
クチャが配線アルゴリズムの性能全大幅に改善できるし
くみは２つ存在する。第１に、各ノードに計算機の存在
する事は配線アルゴリズム中のパラレリズムン利用する
重金可能にする。第２に、頻繁に使われる機能９は各ノ
ードの計算機の処理要素中に特殊命令としてハードウェ
アｒ＜できる。

例えば各々市販の８ビツトのマイクロプロセッサ、２キ
ロバイトのメモリそして隣シ及び制御装置との通信を可
能にする補助回路から構成される８×８の計算機の配列
が配線機能に使用できる。

制（財）装置も８ビツトのマイクロプロセッサであって
、４８キロバイトのメモリ、フロッピー及びハードのテ
ィスフ・ユニット、プリンタ、端末及び機構のホスト・
コンピュータ・システムへのリンフケ何する。次に配［
−実行する時のステップの詳細を述べる。８×８の配列
は、６４個以上の゛構成要素金有するチップ？配線する
ようにプログラムする事ができる。

大局的配線とは、チャネル内のトラック全具体的に割り
当てる事なくチップ内のチャネルに対して配＠全割り当
てる配線の段階に対して与えられた名称でるる。チャネ
ル内でのトラックの割ｇ当て汀、そ！Ｊ）後の正確な埋
め込みアルゴリズムによって実行される。大局的配線を
始める前に、各ノードば、４つの方向の各々において利
用可能なトラックの総数を計算する。またそのノードに
端子？有するネットのリストも与えられる（ネットとは
共に接続すべき２つ以上の端子の集合である）。

（ａ）　　配線すべきネット毎に、それがそのノードに
端子全方する場合も有さない場合も、ノードはそれが各
方向においてそのネットのある接続の一員でろる見込み
を計算し、その方向における混雑評価に対して適当なコ
ストヲ付は加える。

混雑評価値はネットの端子ノードからそのノードまでの
距離の減少関数である。

（ｂ）　　ステップ（、）が全てのネットについて完了
した後、以下概観するステップ（ｃ）〜（ｇ）が第１の
ネットに関して実行され、その後ネット毎に繰り返され
る。

（ｃ）　　与えられたネットに関して、ノードは現在の
総計混雑評価値からそのネットに関する混雑評価の寄与
ヲサし引く。この動作は４つのポートの各々に付き行な
われるう （ｄ）　　不使用トラックの数及び各ポートにおける更
新された混雑評価に基づいて、ノードは４つのポートの
各々に付きポート・コストを計算する。このコストＵそ
の方向においてトラックを占有する事に関するペナルテ
ィの表示である。

従ってトラックが１つしか残っていないポートを通る場
合のペナルティは多くのトラックが残ツテイル場合より
も重い。しかしこのペナルティだけがポート・コストと
して働く事はあり得ない。というのはそれは、例えその
ポートの使用？求めて競争するネットが僅がしか残って
いない場合でも、少ししがトラックの残っていないポー
トにペナルティを課すからである。未配線ネットの需要
はポートにおける混雑評価値で表わσれる。従って残存
混雑評価値と残存容量の関数がポート・コスト関数とし
てより良く働く。

（ｅ）　　次に前方伝搬段階が来る。ネットの端子ノー
　）”ノ１　ツｈ　７−ス、他の全てはシンクト呼ばれ
る。ンース駆　４つの方向の各々において、憐り一その
方向のポートに関するポート・コスト音速る。同時に全
ての他のノードはその隣りに任意の大きな数値を送る。

その後の各タイム・ステップにおいて、各ノードはその
ポートに到来した数値勿ピック・アップし、それらの最
小値を決定する。そしてこの最小値が到来した方向にポ
インタがセットされる。ボート毎にし一ドは、（ｄ）で
計算されたポート・コストをその最小値に加算し、修正
した数値をその方向の隣接ノードに送る。１度ノードが
意味のある数値即ち上述の任意の犬さな値ではない数値
を送ると、そのノードは次のタイム・ステップではこの
任意に大きな値葡送るようになる。

（ｆ）　　６るシンクが意味のある値を受は取ると、そ
のシンクは制御装置に通報する事によって前方伝搬過程
を停止でせる。同時に２以上のシンクに到達する事が可
能なので、制御ＶＣ置はセルをポーリングするか又は他
の何らかの方式によって、最も小さな最小値を有するシ
ンク・セル全決定する。この後バックトレースが開始す
る。

シンクはその記憶じているポインタの方向にある隣接ノ
ードにプロンプトする。次の各タイム・ステップにおい
て、その隣接ノードによってプロンプトされたノードは
前方伝搬段階の間に記憶された方向にろる他のノードを
プロンプトする。この過程はソースに到達するまで続く
。

プロンプトされたノードは適当・なポートのチャネル容
ｔｋ減らし、そのネットに対する入口点及び出口点？記
録する。

（ｇ）　　現在のネットに関して入ロ／出ロ点會記録し
た全てのノードは次の前方伝搬に関してソースになる。

接続されるべき状態に残された全てのネット端子はシン
クとして作用する。１つのネットに関する過程は、その
ネットに関してシンクが全く残らなくなった時に終了す
る。

これまでに述べた工程は、ソースと任意のシンクとの間
の最短の経路を決定し、もし２つ以上のものがあれば最
小のコスト？持つ経路を選択する。

これはソースと最近接シンクとの間の直線距離に比例す
る時間で行なわれる。配置が良好な時、この距離はチッ
プ寸法の増加と共に非常に緩やかに増加する。事実、１
００００回路のチップの場合でさえもこの距離の妥当な
評価１ｌ−１：５である。しかしながら配線すべきネッ
トの数はチップ寸法のほぼ線型関数であり、従って上述
の全工程に関する時間はほぼチップ寸法の線型関数であ
る事が結論される。

最短の経路が最小コストの経路にはならない場合が存在
する。ソースとシンクとの間の最短経路からの何らかの
ずれは迂回路と呼ばれる。配線町・能件の観点からは、
アルゴリズムが適当な迂回路を実行する時に、より良い
性能が得られる。この概念においては、初期に配置きれ
たネットは必ずしも最短経路に配置されない。むしろ、
将来のネットが阻害、されないように、それらは避ける
事が好ましい領域に到達すると迂回する事？許される。

これは、上述の手順に対して以下の修正？加える事によ
って達成される。

迂回路がｄよりも長くない、最小コストの経路が望まれ
ると仮定する。前方伝搬段階の間、各ノードは、１つの
意味のめる数値を送った後に休止する（任意の大きな数
値を隣りに送る）代りに、今回はｄ＋１個の意味のある
数値を送った後に休止する。（ポートにおける阻害はポ
ート・コスト自体を非常に高くする原因になり得る事に
注意つ゛その結果、もしどのシンクにも到達しなければ
、ネットは後に配線するために別に取って置かれる。

しかしながら、ノードが意味のある数値を送り始めると
、その後のりタイム・ステップのいずれにおいてもそれ
はより高い数値を送る事が不可能である。）各ノードは
、数値が到着したタイム・ステップに関してそれが最良
の数値を受は取った方向ｒ表示するテーブルも保持して
いる。もし方向の選択が存在するならば、可能であれば
前のステップにおける方向が好ましい。（これは、同じ
最小総計コスト’に持つ異なった長さの経路があれば最
短の経路を得るのに役立つ。）パックトレース工程は、
最小コストのシンクが最近の活動タイム・ステップ例え
ばｔに関して記憶でれていた方向のｐＪＩ　４ｍノード
ケプロンプトする事によって開始される。隣接ノード奮
プロンプトする時、それば数値ｔ−１も隣接ノードに送
る。そして隣接ノードばそのテーブルを参照して、タイ
ム・ステップｔ−１に対して記憶されていた方向にある
隣接ノード葡、数値ｔ−２と共に、プロンプトする。こ
の工程は、以前と同様に、シンクに到達するまで続く。

上記手順に対して単純な修正を行なえば上記アルゴリズ
ムの時間的及び令聞的な複雑性？少し改善できる。しか
し記載を簡潔にするため、ここには記さない。また４方
向の各々に付き１つのテーブルを保持し、前方伝搬の間
に（バイアのコストも含む）最良のコスト及び各出口ポ
ートに関する最良の方向を計算する事によってターン（
バイアの使用）にペナルティを課す事もできる。アルゴ
リズムは、バイアのコスト全決定するためにセルにおい
て許される最小数のバイア及び最大数のバイアを使用し
ている。

前述の機械？用いた小さな例に上記アルゴリズムを使用
すると、所要時間はリアルタイムが２秒以下でめった。

迂回路限界ｄ全０にセットした時、プログラムは全ての
ネツｔｆ最小５ｔｅｉｎ６ｒ　　接続の形に接続した。

迂回限界を増加させた時、ネットはより長い経路を取っ
たが、実行終了時に残ったチャネル容量はチップ全体に
わたって一様な拡がシを示した。これは、ネットが迂回
？許された時にそれらが将来のネットの配線をよシ容易
にするようなやり方で迂回を行なう事を立証している。

この事は、大局的配線に引き続く正確な埋め込みの段階
にとってかなり役立つ事が判明している。

また残りのネットが少ない事によりチャネル需要が減少
した時の終了時にはネットは最小５ｔｅｔｎｅｒ長さで
配線された事も観察されている。

より大きなチップを配線する時に配線機械をより有用に
するために、小ざなノ・−ドウエアの修正を行なう事が
できる。即ち、北端のノードがその北隣りのノードとし
て南端のノードｒ有し、東端のノードがその東隣りのノ
ードとして西端のノードを有するように、計算機の配列
の端を巻き付けるような形に接続する事ができる。

例えば８Ｘ８の計算機配列を用いて２４Ｘ２４の回路チ
ップの配線を試みる事のできる２つの基本的方法がある
。第１の方法でに、計算機配列の各ノードにおいて３×
３の大きさの回路配列が表現されるように、単に大きな
チップを大きな区画に分割する。折９たたみ（ｆｏｌｄ
ｉｎｇ　）と呼ばれる第２の方法では、回路分割は２４
Ｘ２４の形に保たれる。しかしながら異なった時点では
チップの種々の８×８のフレームが物理的な８×８の大
きさの計算機配列によって処理される。明らかに前記の
巻き付は接続は、チップの任意の連続した８×８の部分
の各回路セルが配列中の別個のノード計算機によって表
現される＠を可能にしている。

この第２の方法は、配線工程の分解能全犠牲にする事な
くノード計算活動の分布において比較的高い局所性全利
用しているので、第１の方法よりもすぐれている。ノー
ド計算機は水平方向及び垂直方向の各８番目の回路セル
毎の回路データ會保持しなければならない。従って各ノ
ードにおけるメモリ容量の要求は増加するであろう。こ
こで説明した方法は厳密なアコーディオン型の折やたた
み法ではなく、よシ正確にはカット・アンド・スタック
法である。前者の方法は、実現可能でろって巻き付は接
続ハードウェアの必要性がないが、連続し之フレームに
関する方向を変える不便さがある。

折りたたみ法の広範な解析によれば、この方法は非常に
価格効率の良い方法である事が示されている。８×８の
配列の機械で２４Ｘ２４のチップに関する前方伝搬ｒ行
なうのに要する時間は、２４×２４の配列の機械を用い
た場合の９倍ではなくて、約４倍でしかない。このファ
クターは迂回限界を１０に増やすと、約８に悪化する。

１９×２６の回路”ｘ−にするチップに関するデータを
用いて、実験的機械に対していくつかの実験が行なわれ
た０２９３のネットに関する大局的配線工程の実行のた
めの実時間はｄ＝ｏの場合の４６秒からｄ二１０の場合
の１６［１秒まで増加した。またネットは大きなチップ
上であってもかなシ局所的になる傾向があるので、５２
×５２のノード計算機ケ有する機械は、全ての妥当な迂
回限界の場合大きなＶＬＳ　Ｉチップに関して、任意に
大きな機械の２倍遅い以上に悪くはない。但しノード計
算機におけるメモリの必要性は、ノードで表現されるフ
レームの数と共に線型的に増大する事を銘記しなければ
ならない。

大局的配線の次に正確な埋め込み工程が続く。

この段階では、各ノードは大局的配線の段階でそれに割
り当てられたネットに正確なトラック？割り当てなけれ
ばならない。割り当てが調和の取れる（１つの回路セル
においてネットに割り当てられたトラックは、隣りの回
路セルにおいてそのネットに割り当てられたトラックと
同じでなければならない）ように、ノードは互いに通信
する必要がある。そのアルゴリズムは、チップの中上・
にある回路セルに関して完全な割り当てを行なう事から
始まる。セルの境界と交差するネットに割り当てられた
トラックは適当な隣りの処理要素に送られ、その処理要
素はその回路セルに関する割り当て上行なう時にこのデ
ータｒ用いる。この工程は、チップの隅にある回路セル
においてトラックが割シ当てられるまで、ダイヤモンド
形の波面の形で進行する。この工程の詳細はここでは説
明しないが、広範な予測により、１つのプロセッサによ
ってネットに割り当てられたトラックが隣りの未割り当
てのセルによって妥当に好まれるものになる事が保証さ
れる。反対方向の即ち隅のセルから中７シ・のセルへ向
う波面伝搬が、割り当ての衝突？調節するためにアルゴ
リズムの終了時に組み込まれ得る。

第２１ｇは本発明による′ｍ哩的設計装置のブロック図
である。例えばＩＢＭ５７０計算機等の上位システム１
０が、マスク作成装置１２に、及び直列Ｉ１０バス・イ
ンタフェース１６’ｉ経てシステム・バス１４に接続さ
れる。また印！１１装置１８を、システム・バス１４か
ら入力を受は取るためにインタフェース１６に接続して
もよい。制御プロセッサ２０はバス１４及びコンソール
２２に接続される。また制御装置メモリ２４も・（ス１
４に接続される。さらに直接アクセス記は装置（ＤＡＳ
　Ｄ　）２６がバス・アタ゛７す２８を経てシステム・
ノ（ス１４に接続でれる。制御プロセッサ２０は、配列
Ｉ１０プロセッサ３４？Ｉｌ−介して５ＰＥ３２から成
るプロセンサ配列３０と通信する。プロセッサ配列３０
は、第１図に示したセルに等しい数の、又はその約数に
等しい数のｎＸｎの５ＰＥ３２の配列から構成てれ、第
２図のシステムと共にセルの配線経路決定？行なう。

７　制御プロセッサ２０とプロセッサ配列３０との間の
全ての通信はメモ１ルマツビング技術によって行なわれ
る。即ち、制御装置２０から配列３０への通信は、制御
装置が特別なメモリ・アドレスに書込みを行ない、これ
が配列Ｉ１０プロセッサろ４によって傍受され、さらに
最終的な宛先に送られる事によって行なわれる。同様に
配列５０中の５ＰＥ３２ｕ、）・−ドクエアによるメツ
セージの適当な送付２生じさせるそれ自身の特別なメモ
リ・アドレスに香込みを行なう事によって制御装置２０
と通信する。ＳＰＥからＳＰＥへの通信は、後述の技術
を用いて実現される。

プロセッサ配列３０は５ＰＥＯ行及び列から構成され、
各５ＰＥｕその４つの隣接ｓｐｇ、即ち北、南、東及び
西の隣接ＳＰＥと通信し、また特別なバス機構を通じて
制御装置２０と通信する。

本発明全実施する時、任意の数の行Ｎ及び列Ｒ１−用い
る事ができる。

次に第３６１図及び第３２図を参照する。これらの図は
、システム・バス・インタフェース動作のプロトコルを
処理する論理ハードウェアを一部に有する配列Ｉ１０プ
ロセッサ６４の詳細なブロック図である。プロセッサ３
４は、プロセッサ配列３０ケ駆動し制御するために制御
装置２０及び他の論理Ｈｉｔからメモリ・マツプされる
特殊なレジスタｒ有する。

制御装置２０とプロセッサ配列３０のＳ　ＰＥ３２との
間の全ての通＠ハ、選択されたＳＰＥとの間たけて転送
される。制御装置２０は、Ｘ及びＹ即ち列及び行の各々
の選択ビット’ｘセントする事によって複数個又は所定
の１個のＳＰＥ２選択する。制御装置２０はＸ選択レジ
スタ及びＹ選択レジスタのために２つのピット・ベクト
ルケ組み立てる。但し論理１はそのピント位置に対応す
る列あるいは行が選択きれる重音意味する。ＳＰＥは、
列選択信号及び行選択信号の両者が一致する場合に限っ
て、それ自身を選択されたものと考える。

従って制御装置２０は、Ｘ選択レジスタ及びＹ選択レジ
スタであるメモリ・マツプでれた位置に書込みを行なう
事によって、２つのレジスタの内容の論理積に対応する
ＳＰＥの群？選択する事ができる。午列中のＳＰＥは、
どのＳＰＥの群に情報？伝送しあるいはどのＳＰＥの群
から情報を受は取るかｔ決定できるのが制御装置だけで
あるという意味で、制御装置の完全な奴隷でろる。Ｘ−
Ｙ一致選択の機構によって選択されないＳＰＥは、デー
タ、制御又はアドレスであろうと、いかなる通信にも関
与できない。もし制御装置が全てのＳＰ、Ｅとの通信、
例えば全てのＳＰＥへの回報通信又はあらゆるＳＰＥか
らの集信を望めば、制御装置は単にＸ及びＹ選択レジス
タの両者に全て１をセットする。

配列■１０プロセッサ３４は、双方向アドレス、データ
及びシステム・バス・サービス信号を与えるために、シ
ステム・バス１４に接続される。データ信号は、双方向
バス６６からデータ・バス６８に与えられ、そこからＸ
選択レジスタ４０、Ｙ選択レジスタ１４２及びデータ駆
動装置４４４に与えられる。またデータは、ＯＲゲート
４８．５０及び５２の各々を介して配列の列１〜列ｍか
らのＸＬ心答を受は取るデータ・バス４６からデータ・
バス５６に与えられる。ｙ７答は配列の行１〜行ｎから
各々ＯＲゲート５４．５６及び５８を介して与えられる
。全てのＳＰＥからの配列データ゛・バスからのデータ
は、全ＳＰＥからＯＲゲート６１を経て与えられる。

アドレス信号は、システム・バス１４からアドレス・バ
ス６２へ与えられ、そこから配列Ｉ１０制御論哩回路６
４及び駆動回路６６に与えられる。

システム・バス及びメモリ・サービス信号ハシステム・
バス１４からバス７０をｌＩてシステム・バス・　１ン
タフ工−ス論理回路６８に与えられる。

レジスタ４０及び４２に与えられた選択信号は駆動回路
７２及び７４を経て各々列選択信号及び゛行選択１ぎ号
として配列中のＳＰＥに与えられる。

捷だデータ信号は駆動回路４４から配列のＳＰＥに与え
られる。制御論理信号は、制御論理６４からバス７６を
経て駆動回路７８に、配列中のＳＰＥへの側脚信号とし
て与えられる。バス６２上のアドレス信号は配列前の全
てのＳＰＥをアドレスするために駆動回路６６に与えら
れる。

アドレス・バス６２の内容に依存して、種々の型の動作
がメモリ・マツプされた動作によって実行される。第１
に、これらの信号のある部分は配列中の各ＳＰＥ中の実
際の記憶位置を構成する。

ここで全ＳＰＥの局所メモリは同一にアドレスされ、ど
の局所メモリがアドレスされるかはＸ選択レジスタ４０
及びＹ選択レジスタ４２によって支配される。第２に、
これらのアドレス信号のある部分は、アドレスが特別な
メモリ・マツプされた位置であって、そのあるものがプ
ロセッサ３４内にありあるものが個々のＳＰＥ内にある
事を意味する。

普通のシステム・バス・インタフェース論理６８の管理
の下に配列Ｉ１０制御論理６４は、バス６２上の到来し
たアドレス信号を解読してプロセッサ３４内及び配列中
の種々のデータ制御信号路を制御する。アドレスの本質
的な位置及び対応する間通は後で詳細に示される。この
解読及び制御がいかにして行なわれるかは周知なので、
詳細には示さない。

表１は配列Ｉ１０制御論理６４によって実行される論理
的機能を示す。

第４図は、第３２図の駆動回路４４．７８及び６６中の
個々のビットに関して用いられる駆動回路８０の図であ
る。駆動回路８０は入力線８２上の１ぎ斜線上のピント
毎にビットＫを受は取り、このビットは制御論理６４か
らのエネーブル信号８４に応答してゲートされ、出力線
８６上めピントを与える。このビットは配列中の各ＳＰ
Ｅにファン・アウトされる。駆動回路８０は、周知のよ
うに、駆動負荷を分担するために駆動回路のファン・ア
ウト・ツリーから構成する事ができる。

第５図は、隣接ＳＰＥ及び配列Ｉ１０プロセッサへの及
びそれらからの制御人力及びデータ入力を含む５ＰＥ３
２を示す。ＯＲを行なうデータ・バス８８は駆動回路４
４及び６０の出力に接続され、アドレス・バス９０は駆
動回路６６に接続され、制御バス９２は駆動回路７８に
接続され、そシテサービス・バス９４はプロセッサ３４
のＯＲゲート６２の入力に接続される。

各ＳＰＥはその隣りの、東西南北の隣接ＳＰＥと、ＳＰ
Ｅ毎に与えられた通信信号を用いて通信する。ＳＰＥ毎
に、各信号線９６にス）ｏ−ブ・アウト信号が、各信号
線９８にフラグ・イン信号が、各信号線１００にス）ｏ
−プ・イン信号が、各信号線１０２にフラグ・アウト信
号が、各信号線１０４に隣接データ・インが、そして各
信号線１０６に隣接データ・アウトが与えられる。Ｘ選
択信号及びＸ選択信号は各々列毎及び行毎に信号線１０
８及び１１０から全てのＳＰＥに与えられる。Ｘ選択信
号は信号線１１２から５ＰＥ３２に、Ｘ選択信号は信号
線１１４に与えられる。Ｘ応答信号及びＸ応答信号は各
々ＳＰＥから信号線１１６及び１１８に与えられ、さら
に各々配列用のＸ及びＹ応答河号線１２０及び１２２に
与えられる。

北、南、東及び西の隣接ＳＰＥへの隣接通信線は、配列
の北、南、東及び西の境界のＳＰＥを除けば、全てのＳ
ＰＥに付き同一である。それらの境界ＳＰＥは、配列の
反対側のセルを、配列の外側の方向の隣接セルと考える
。５ＰＥ３２の詳細な機能的動作は第６．１図及び第６
．２図並びに流れ図に示される。

次に第６．１図及び第６．２図を参照する。これらは５
ＰＥ３２の詳細なブロック図である。信号線９２上の制
御ハス信号は制（財）バッファ１２６を経てＳＰＥ制（
財）論理回路１２４に与えられ、また制御バッファ１２
６から匿号線１２８及び１６０を経て各々ＡＩＮラッチ
１６２及びＡＯＵＴラッチ１３４に与えられる。Ｘ選択
信号１１２及びＹ選択恰号１１４も各々論理回路１２４
に入力として与えられる。バス９０上のアドレス、・バ
ス信号は外部アドレス・バッファ１３６に与えられる。

０Ｒｆ−夕・バス線８８は、イン・レジスタ１４６、ア
ウト・レジスタ１４８、データ・イン・バッファ１５０
、及びデータ・アウト・バッファ１５２に接続するため
に各々バス１３８．１４０．１４２及び１４４に接続さ
れる。サービス・バス９４はサービス・バッファ１５４
に接続され、さらにバス１５８を経てサービス・ワード
１５６に接続さね、る。サービス・ワード回路１５６は
ラッチ１３２及び１３４の他にサービス・ラッチ１５９
を含む。サービス・ワード１５６はバス１６１を経てＳ
ＰＥデータ・バス１６０に接続される・。

各信号線１００のストローブ・イン信号は化イン・フラ
グランチ１６２Ｎ、東イン・フラグ・ランチ１６２Ｅ、
南イン・フラグ・ラッチ１６２Ｓ及び西イン・フラグ・
ランチ１６２Ｗに各々接続される。これらのランチは各
信号線１０２にフラグ・アウト信号を出し、又これらの
信号は・くス１６８を経てフラグ・ノ（ソファ１７０に
も与えられる。各信号線９８上の隣接フラグ・イン信号
も・くス１６８を経てフラグ・・（ソファ１７０に与え
られる。フラグ・バッファ１７０の出力はＳＰＥデータ
・バス１６０に供給される。ストローブ・アウト信号は
ＳＰＥ制御論理回路１２４から各信号線９乙に与えられ
る。各信号線１０４上の隣接データ・イン信号は化イン
・ラッチ１７２　Ｎ、東イン・ラッチ１７２Ｅ％南イン
・ランチ１７２Ｓ及び西イン・ランチ１７２Ｗに与えら
れる。これらのランチからの出力はＳＰＥデータ・〕（
ス１６０に供給される。データ・・（ス１６０は隣接デ
ータ・アウト・バッファ１８０の入力に接続され、隣接
データ・アウト・バッファ１８０は隣接データ・アウト
１器号を各信号線１０６に与える。

Ｓ　ｆ）　Ｅ制（財）論理回路１２４は双方向バス１８
４を経てマイクロプロセッサ１８２に接続される。

マイクロプロセッサ１８２は例えばザイログｚ８０等の
市販のマイクロプロセッサでモ良イ。マイクロノロセッ
サ１８２はバス１８８ｔｕてアドレス・バッファ１８６
にアドレスを与え、双方向ハス１９２を経てデータ・バ
ッファ１９０と７’−５全交換する。アドレス・バッフ
ァ１８乙の出力は、局所メモリ１９６にも接続されだＳ
ＰＥアドレス・バス１９４に接続される。局所メモリ１
９６は例えばランダム・アクセス・メモリ（ＲＡＭ）ｆ
も良い。

アドレス・バス１９４はバス１９Ｅｌｃ−ｄてバッファ
１３６の出力、及びバス２００を経てＳＰＥ制（財）論
理回路１２４のアドレス入力にも接続される。局所メモ
リ１９６は双、方向バス２０２を経てＳＰＥデータ・バ
ス１６０に接続される。レジスタ１４６．１４８及びバ
ッファ１５０．１５２も各々バス２０４．２０６．２０
８及び２１０を経てデータ・バス１６０に接続される。

さらにランチ１７２Ｎ、１７２Ｅ、１７２Ｓ、１７２Ｗ
及びバッファ１８０もバス２１２．２１４．２１６．２
１８及び２２０？経てデータ・バス１６０に接続される
。

ＳＰＥ制御論理１２４は、グローバルな制御装置２０及
び隣接ＳＰＥに対して、５ＰＥ３２内での王なデータ経
路指定機構として機能する。通信線９２はバッファ１２
６を経て、９０はバッファ１６６を経て、８８はＩ１０
レジスタ１４６．１４８及びバッファ１５０．１５２を
経て、並びに９４はバッファ１５４を経て全てＳＰＥ制
御論理１２４内のＸ−Ｙ選択機構によってゲートされる
。

論理１２４内のＸ−Ｙ選択機構は第７図に示されている
。ＡＮＤゲート２２２は、信号線１１４及び１１２から
各々Ｘ選択信号及びＹ選択信号を受は取り、一致を検出
すると、出力線２２４にエネーブル信号を与える。これ
は上述の５ＰＥ３２の全てのグローバルなバッファ及び
レジスタに供給される。後述する全てのグローバルな通
信もこの選択機構によって支配される。

第６１図及び第６２図に戻る。信号線９２上のｉ！１１
　砥信号の一部分であるリセット信号は、バッフ７１２
６ｉ経てマイクロプロセッサｊ８２ｅ’Ｊセットする。

マイクロプロセッサ１８２・ｆｄ局局所バス処理及び１
６０のプロトコルを定める。従って制御装置２０から配
列Ｉ１０プロセンサ６４を経由して来る制御信号線９２
のあるものは、周知の方法でＳＰＥ制御論理１２４によ
って信号線１８４全経てマイクロプロセッサ１８２に経
路指定あるいは処理されるコマーシャルに特定された局
所バス処理に専用比される。これらの信号は例えば普通
、バス応答信号及びバス要求信号等を含む。

また制御信号線９２は、割り込み、リセット等の普通の
マイクロプロセッサ制御コマンド信号線及びＳＰＥ局所
メモリ読取り、書込みコマンド信号線も含む。これらの
信号の機能はマイクロプロセッサ技術で良く知られてい
る。制御装置２０によって配列Ｉ１０プロセッサ３４を
経て局所バスのグローバルな要求が即始されると、マイ
クロプロセッサ１８２は一時的に中断され、バス１９４
及び１６０は局所タスクに優先するグローバル・タスク
に与えられる。信号線９２のうち２つの制御信号線部ち
１２８及び１５０は、グローバルなデータ・バス９４を
経てＩ１０レジスタの使用のためにプロトコル・ピット
のセントに専用に用いられる。信号線１２８はＡＩＩＮ
ランチ１３２を論理１にセントし、信号線１３０はＡＯ
ＵＴラッチ１６４を論理りにリセットする。これらの動
作ｑ１グローバルな制御装置２０が前述のように５ＰＥ
Ｉ１０レジスタを読取り又は書込む時に、配列Ｉ１０プ
ロセッサ３４によって全面的に制御される。

他のグローバルな通信は制御装置２０及びＳＰＥデータ
によるＤＭＡ方式によって行なわれる。Ｉ１０プロセッ
サカラのグローバルなコマントニ対する応答における５
ＰＥｊ１５１Ｊ８論理１２４の動作を以下に示す。制御
論理１２４が局所バスに関するグローバルな要求を認識
する時、外部アドレス・バッファ１３６は、タスクの継
続する間の一時的な中断の後に、バス１９４にアドレス
を与える事を許される。次に、制御論理１２４は、バス
２００によってバス１９４から受は取ったアドレスを解
読して、以下の表２に示すような適当なデータ経路決定
の動作を行なう。

ＳＰＥは北、南、東及び西の方向の各々においてデータ
・ポート１０４及び１０６を経て隣ＷＳＰＥと通信する
。通信の保全性を保証するために、フラグ・ラッチ１６
２（Ｎ、Ｅ、５ＸＷ）、信号線９８上の隣接フラグ・イ
ン、信号線９６上のストローブ・アウト信号、フラグ・
アウト１０２、及びストローブ・イン信号１００が用い
られる。

これらの信号及びランチの使用並びに動作は後で説明す
る。

以下、ｓｐｇ制御論理１２４のデータ経路決定を示す。

内部要求は、マイクロプロセッサ１８２からＤＭＡの形
で種々のＳＰＥランチ、レジスタ及びポート並びにＳＰ
Ｅ局所メモリ１９６に与えられる。これらの要求の全て
は、マイクロプロセッサ１８２からバス１８４を経て制
御論理１２４によって処理される普通の局所バス・プロ
トコルによって優先される。以下の衣３は内部データ経
路決定のために制御論理１２４によって行なわれる動作
を示す。

凶　　　　　　　　　坏　　　　　　　坏第８図は、メ
ール・ボックス・フラグ・プロトコル又は要求応答プロ
トコルとして知られている隣接ＳＰＥＰＥ通溝機構す。

この機構は、データの転送時に受は取る側のプロセッサ
がデータを予期する事なく２つのプロセッサがデータを
転送する時にデータの保全性全保証するために関われる
多くの可能な方〆去の１つである。メール・ボックス・
フラグ機構は、第６１図に示したＡＩＮランチ１６２及
びＡＯＵＴラッチ１６４に関するメール・ボックス機構
と同じ原理で動作する。第８図のユニットＡ及びＢは、
南北の隣接ＳＰＥでも、東西の隣接ＳＰＥでも、又■１
０レジスメ１４６及び１４８（第６１図）の通信が関係
している限りにおいてはＳＰＥ及び配列Ｉ１０プロセッ
サ３４を表わすものでも良い。二二ソ）ＡがユニットＢ
に送信する場合を考える事にする。

ユニットＡはデータ・バス１６Ｇ、送信バッファ１８０
及び制御論理回路１２４を含む。ユニットＢは受信ラン
チ１７２、イン・フラグ・ラッチ１６２、制御論理回路
１２４及びデータ・バス１６０を含む。送信バッファ１
８０と受信ランチ１７２との間の通信はバス２１６及び
１０４を経由する。

メール・ボックス・フラグ機構の動作は以下のステップ
による。

（１）　　データを二二ツ）Ｈに送る前に、ユニットＡ
はユニットＢのイン・フラグ・ラッチ１６２を尋問する
事によって、以前にユニソ）Ｂに送られたデータが二二
ソ）Ｂによって読取られている事を確認する事ができる
。グローバルな読取りの場合はサービス・ワードを読取
る事によって、又隣接ＳＰＥの場合はフラグ・バッファ
１７０全読取る事によって、その確認が行なわれる。フ
ラグ・イン９８のビット値が論理１である事が感知され
ると、それは隣接ＳＰＥが以前に送信されたデータを読
取っていない事を意味する。ユニン）Ａはこのピントラ
、論理ａｔ感知するまで質関し続ける事ができる。もし
ユ　　。

ニラ）Ａが以前に送信したデータについて注意を払わな
いか、又は充分な時間の経過によってユニットＢが他の
データ・ワードを受は取る用意の出来ている手が雁かで
あれば、ステップ１全省略して以下のステップ２に直接
に進む。

（２）　　ユニットＡはデータ・バス１６０へのデータ
をエネーブルし、パンノア１８０Ｔｈエネーブルシ、同
時にユニソ）Ｂのノ・−ドウエアにおいて２つの事象を
直接制量するストローブ信号をユニノｌ−Ｂに送信する
。第１に、ストローブ信号はユニットＢの受信ラッチ１
７２をクロックし、送信されたデータをランチさせる。

第２に、同時にユニットＢのイン・フラグ・ラッチ１６
２を論理１にセントする。これはデータ・ワードがユニ
ットＡから二二ソ）Ｂに伝送された事を表わす。

（３）　　ある時間の後、ユニットＢがユニン）Ａから
のデータを予期又は必要とした時、及びユニットＢがユ
ニットＡからデータの送られたことを確認する事を望む
場合、ユニットＢはそれ自身のイン・フラグ・ランチ１
６２を質関し得る。

この時ユニットＢはその値が論理１になるまで、このラ
ンチを質関し続ける事ができる。もしユニットＢが、何
らかの理由でユニットＡからデータが伝送されたはずで
あるという事実を確信できれば、直接ステップ４に進む
事ができる。

（４）　　ユニットＢは読取るためにその受信ランチ１
７２をバスにエネーブルし、同時にイン・フラグ・ラッ
チ１６２と論理０にリセフトする。

これはユニットＡからざらに清報を受は喉る用意の出来
ている事を表わす。

第６．１図、第６．２図に戻る。ＳＰＥ制御論理１２４
はＳＰＥ内部及び外部のデータの移動の経路決定を担当
しているが、制御論理１２４は配列■１０プロセッサ３
４又はマイクロプロセッサ１８２のコマンドによってだ
けその動作を行なう。ＳＰＥにおける実際のデータの処
理及びデータ移動の指令はこのマイクロプロセンサ１８
２によって実行される。即ちＳＰＥによって実行される
計算及び機能は、ＳＰＥ局所メモリ１９６に記憶された
種々の利用可能な命令及びデータを用いたプログラミン
グ手段によって、制御装置の管理の下に、他のＳＰＥと
同時に並列に実行される。いくつかの特殊な命令例えば
同時４ポ一ト通信及び算術論理演算は市販のマイクロプ
ロセッサの標準的命令セントによってエミュレートされ
る。しかしながら、そのような特殊な命令セントにある
特殊な機能的・・−ドウエア論理の上で動作させる事の
実用性及びスピードの利点全考慮して、ＳＰＥに４ボー
ト的性質の特殊な・・−ドウエア命令の一部又は全てを
組み込んでも良い。もつともどのような命令セントが用
いられようとも、ディジタル・プロセッサのプログラミ
ング技術においては、機能的動作のフローが特定されれ
ばプログラムの作成は定型作業である。

次に大局的配線経路決定に関する物理的設計工程の一般
的な説明を行なう。ここではシステムにとって本質的な
システム・レベルの一般的な作業を説明し、主なシステ
ム機能だけを説明する。システム割り込み処理、自動配
列再構成、時分割タスク、’ＳＰＥプログラム・オーバ
ーレイ機構等の機能は説明しない。

システム・リセットは、第２図の制御プロセッサ２０に
おいて、プロセッサ（５ＲＯＭの固定されたアドレスに
ジャンプさせる）・−ドウエア・スイッチによって行な
われる。ＲＯＭは、必要な制御装置及びＳＰＥ用のアプ
リケーション・プログラム’：ＤＡＳＤからネガティブ
・メモリ２４及び１９６にロードするようにプログラム
されている。

配列中の全ての動作は選択されたＳＰＥだけに限定され
る。全てのＳＰＥに同報通信するか、又は全配列を動作
させる場合は、第６．１図のＸ−Ｙ選択レジスタ４０及
び４２が全て１のベクトルを含む。もし任意のＸ−Ｙ部
分集合が何かの動作に関して望まれるならば、そのよう
な部分集合ベクトルは、さらに何らかの動作が起きる前
に制御装置によって分解され、Ｘ−Ｙ選択レジスタ４０
及び４２に記憶される。

応答するＳＰＥの決定は制御装置が、メモリ・マツプさ
れた特別な位置、Ｘ−Ｙ応答線を読取る事によって為さ
れる。制御装置は最初に全配列のＸ応答を読取シ、配列
のどの列が応答しているかを見い出す。各々の応答して
いる列毎に、制御装置はその列及び全ての行？選択し、
その列の中の応答しているＳＰＥの正確な位置と決定す
るためにＹ応答を読取る。ｉ！１１呻装、置は、応答し
ているＳＰＥの位置を見い出すと、それに対してＳＰＥ
メモリ中のある値又はＩ１０レジスタの読取り及びそれ
らに対する作業等の動作を行なう事ができる。

ＳＰＥメモリのローディングは、制御装置がプログラム
又はデータをＤＡＳＤから又は直接その主記憶から取り
出して前述のＤＭＡ機購によって同時に全てのＳＰＥメ
モリにロードする事によって行なわれる。一般にデータ
及びプログラムの共通部分は、Ｘ−Ｙ選択ベクトルの論
理積として選択ＯＴ能なＳＰＥの任意の群に対してロー
ドできる。

ＳＰＥのＩ１０レジスタを用いる゛通信は次の点で５Ｐ
Ｆ２メモリへのＤＭＡと区別される。即ち、ＳＰＥメモ
リへのＤＭＡはＤＭＡ動作のためにＳＰＥ局所バスを使
用する事によりＳＰＥ動作を中断させる。一方Ｉ１０レ
ジスタはＳＰＥ局所パスを妨害する事なく用いる事がで
きる。ＳＰＥは、前述のＡＩＮ及びＡＯＵＴのフラグ機
構を通じて、制御装置によってＩ１０レジスタに置かれ
た又はそこから読取られたデータ翳り扱いを通知される
。

制御装置は単に選択されたＳＰＥ　　ｒ１０レジスタを
読取り及び書込む事によってこれらのステータス・ピン
トをセットする。また前述のサービス・ワードの読取り
によってステータスを観察する事ができる。

ＳＰＥは、配列をリセットするために制御装置がデータ
を特別なりＭＡアドレスに書込む事によって起動される
。配列Ｉ１０プロセッサはこのアドレスを解読し、選択
されたＳＰＥのマイクロプロセッサをリセットするりセ
ント用の制御信号綴金付勢する。マイクロプロセッサが
リセットされると、マイクロプロセッサは記憶位＃０を
実行させられ、記憶立置０の命令はＳＰＥ局所メモリ中
に記憶された種々のプログラムの開始点を含むジャンプ
・テーブルへ適当なインデックスを伴なうジャンプを引
き起こす。ジャンプ・テーブルへの適当なインデックス
は制御装置によってＳＰＥメモリの固定された位置にＤ
ＭＡ転送するか、又は次の実行ンーケンスの開始を予期
したＳＰＥによってそこに記憶される。

配列内の通信は隣接するＳＰＥ間でデータを送置及び受
信する事によって実行される。送信受信が行なわれる機
構は以前に述べた。各ＳＰＥは境界状況が記憶きれる特
別な記憶位置を有する。従って各ＳＰＥはどの特定の方
向に隣接ＳＰＥが存在するか又はしないかという事実を
認識している。

プログラム・フローチャートが隣接通信を指定するたび
に、ＳＰＥは送信又は受信の動作の前に最初に隣接ＳＰ
Ｅの存在を確認する。そして境界ＳＰＥは、フローチャ
ートの一般的な記述の例外として、単にその空白の方向
への送信あるいは受信のステップを省略する。

同期ｒヒ磯溝は、ＳＰＥのサービス・ワードを全てのＳ
ＰＥステータス（その最も重要なものはジョブ終了ステ
ータスである）の報告に用いる事によって達成される。

タスクを始める前に、全てのＳＰＥは所定のビット位置
を、ビジー・ステータスを表わす論理１にセットできる
。与えられたタスクが終了すると、ＳＰＥはサービス・
ワードを読嘔り、ピントラ論理Ｏにリセットし、そして
サービス・ワードに戻して記憶する。サービス・ノ；ス
は、選択されたＳＰＥの全てのサービス・ワードの論理
和ヲ取るＯＲバスなので、選択されたＳＰＥのどれかが
ビジーであればそのピントは論理１になり、選択された
ＳＰＥの全てがタスクを終えている時に限り論理０にな
る。従って制御装置は、次の副工程のために配列′ｆ：
制ａする前に全ＳＰＥの作業終了を決定する。

以下は本発明による物理的設計工程の例である。

論理設計が完了すると、第９図に示す物理的設計工程が
始まる。一般的なステップは次の通りである（第９図参
照）。

（１）　　ブロック２２６に示すように、論理ゲートを
チップ、カード、ボード等の物理的実装体に分割する。

（２）　　ブロック２２８に示すように、各実装体内で
部品を配置する。

（３）　　ブロック２６０に示すように、各実装体内の
論理素子の端子への配線経路決定を行なう。

（４）　　ブロック２３２に示すように、製造データを
生成する。

配置及び配線はある応用においては組み合わされた工程
である可能性がある。物理的設計工程の最終出力は、第
２図の装＃１２に示すような′マスク作成装置又は他の
リングラフィ・システムによる製造工場における論理実
装体の実際の物理的実現のだめの入力として役立つ。

第９図の配線経路決定工程２３０は第１０図に、より詳
細に示されている。この工程の前の部品の配置工程２８
８はチップのどの位置にどの論理素子が置かれるか、及
びこれらの論理素子のどの端子が他の論理素子のどの端
子に接続されるかを決定する。次に論理サービス端子（
ＬＳＴ）間の最適のチャネル経路を決定するためにブロ
ック２３４に示すように大局的経路決定工程が行なわれ
る。

これに続いて、選択されたチャネル内のトランクへの水
平及び垂直な配線の正確な埋め込みがブロック２３６に
示すように行なわれる。この決定の後、ブロック２３８
に示すようにオーバーフロー処理及び検査が行なわれ、
そして第９図のブロック２３２に戻る。１例として、マ
スク・スライス・チップ又はゲート・アレイ・チップと
して一般に知られているチップを用いて詳細な説明ヲ行
なう。

第１１図に示されるマスタ・スライス・チップ２４０は
セル２４２の行及び列から構成される。

このセルを、水平方向の複数の配線トランク２４６から
成る水平チャネル２４４及び垂直方向の複数の配線トラ
ンク２５０から成る垂直チャネル２４８が通過している
。この水平及び垂直の配線チャネルは、絶縁層で隔てら
れた各配線面中に２ある。

能動論理素子は、さらに他の絶縁層で隔てられた、これ
ら２つの配線面の下側にある。

第１２図はセル２４２の詳細を示す。セルは論理装置２
５−２とそれに対応する水平及び垂直チャネル交点との
組み合せと解される。セルの４つの仮想的境界線はＮ、
Ｅ、Ｓ、Ｗポートと呼ばれる。

各ボート上の利用可能な配線トランクの数はチャネル容
量と呼ばれる。各セル中の論理装置２５２は、ＡＮＤ、
ＯＲ，ＮＡＮＤ、ＮＯＲ，ＮＯＴ。

ＥＸ−ＯＲ、ランチ、等の基本的論理機能を実行するよ
うにパーンナライズされた能動半導体論理装置である。

その場所に配置された論理機能は論理装置がどのように
パーンナライズされるかを決定するが、これは配線経路
決定の工程には無関係である。しかしながら、論理装置
２５２にどの機能が割り当てられるかに依存して、垂直
配線トランク２５０に沿って論理サービス端子（ＬＳＴ
）２５４と呼ばれる位置が固定される。またあるＬＳＴ
は水平トランク２４６に沿って配置しても良く、これは
同様に割り当てられた他のセルのＬＳＴに接続しなけれ
ばならない。配線工程の他に、論理装置のバーソナリゼ
ーションのだめに水平及び垂直配線トラックの一部分ヲ
使用しても良い。

但しこれは影響を受けたトランクにおいて障害物になる
。従って化ポート及び南ポートのチャネル容量は同一で
はない可能性があり、また東方向及び西方向も同様であ
る。

ネットとは、配置されたセルのＬＳＴの集まりであって
、配線トランクに沿って設置された配線によって電気的
に共通に接続されるべきものを意味する。配線がその方
向全室えなければならない時、それは水平及び垂直の配
線トランクの交点２５６にプログラムされたバイアを用
いる事によって配線面を変える事によって行なわれる。

チップ又はモジュール技術及び与えられた配置に依存し
て、全てのセル境界線のチャネル容量が固定される。チ
ップ入出力ビンは、ある指定された位置にある駆動器セ
ル及び受信器セルに接続される。普通これらのセルはチ
ップの周辺部にあるが、他の多くの構成も実用化されて
いる。

また技術はセル内のバイアの配置も決定する。

その拘束は普通、トランクに沿って用いられるある隣接
バイアの禁止として表われる。この拘束がいかにして処
理されるかの詳細な解析はＩＢＭＪｏｕｒｎａｌ　ｏｆ
　Ｒｅ５ｅａｒｃｈ　ａｎｄ　Ｄｅｖｅｌｏｐｍｅｎｔ
。

Ｊｕｌｙ　　１９８１号の１）−Ｔ、Ｌｅｅ　　外によ
る論文″Ｎｕｍｂｅｒ　　ｏｆ　　Ｖｉａｓ　　ａ　Ｃ
ｏｎｔｒｏｌ　　Ｐａｒａｍｅｔｅｒｆｏｒ　Ｇｌｏｂ
ａｌ　Ｗｉｒｉｎｇ　ｏｆ　Ｈｉｇｈ　Ｄｅｎｓｉｔｙ
　Ｃｈｉｐｓ”に見い出す事ができる。上記文献の教え
る理論に従って、与えられたセル内でセルの水平及び垂
直チャネル容量の関数として２つの数ＶＩＡＭＩＮ及び
Ｖ　Ｉ　ＡＭＡＸを決定する事ができる↓数ＶＩＡＭＩ
Ｎは、技術的拘束を侵す事なくセル内に配置され得るバ
イアの最小の許された数を意味する。

即ち、もしセル内にＶＩＡＭＩＮよりも１つ少ない数の
バイアが配置されると、拘束を侵犯する事なく同じセル
内のどこかにもう１つ他の・くイアを付加する事が常に
出来る。数Ｖ　ＩＡＭＡＸは、最も性別な配置の下でセ
ル内に割り当てる事のできるバイアの最大数を意味する
。即ちＶＩＡＭＡＸす、■の数のバイアはセルに割り当
てる事が可能である。即ちＶ　Ｉ　ＡＭＡＸ以下の屈曲
配線をセルを経て配線する事ができる。

第１０図を参照すると、配線経路決定工程は配置及びチ
ップ構造のデータを用いて始められる。

工８２２８によって与えられる配置データは、経路決定
されるべき各ネット毎に、（４）全てのＬＳＴの数、（
Ｂ）各ＬＳＴのセル位置、及び（Ｃ）セル内の正確なＬ
ＳＴの物理的位置を与えるネット・リストである。チッ
プ構造データは、各セルの妨害状況及び全てのセルの全
ポートのチャネル容量に関する情報から成る。

配線経路決定工程２５０における最初の且つ最も重要な
主要ステップは大局的経路決定２３４と呼ば扛る。この
ステップにおいて、全てのネットの経路がセル分解能で
大局的に決定される。セル内での正確なＬＳＴの位置、
経路の正確なトランク又はバイアの正確な位置はこのス
テップでは無視される。次にその後のステップ２３６で
、微細な分解能における詳細な技術的拘束を満足させな
がら、大局的に経路決定された配線セグメントがチャネ
ル内の正確なトランクに埋め込まれる。これまでの２段
階の手順からあふれ出だものとして配線セグメントが残
れば、オーバーフロー処理ステップ２３８が呼ばれる。

現在の技術的慣行によれば、多くのオーバーフローは手
作業によって埋め込塘れており、チップの全開発時間に
長い遅れを生じさせている。本発明のねらいはオーバー
フローを減らし、且つ発生したオーバーフローを高速に
自動処理する事である。

第１０図のブロック２３４に示される大局的経路決定工
程を説明する流れ図、第１３図を参照する。ネット・デ
ータ、チャネル容量及び迂回限界が流れ１図のブロック
２６０に対して与えられる。

ブロック２６０において、配線経路によるトランクの予
期される使用により、チップの各セル境界線である各ボ
ートにおける混雑評価を行なうために第１のステップが
行なわれる。次に工程は、ブロック２６２．２７２及び
２７６に示すように一時に１ネツトヲ蛯路決定する。又
、ブロック２６２．２７２及び２７６に示すような単純
なネット処理順序の代わりに何らかの他の適当な手続き
により、配線すべきネットの順序を決定しても良い。

ネットが経路決定される前に、そのネットの寄与による
混雑評価がブロック２６４に示すようにさし引かれ、そ
れによって、まだ経路決定されていないネットによる混
雑評価だけを反映するようにする。この更新された混雑
評価及びチャネル容量を用いて、各セル境界線毎にブロ
ック２６６に示すように交差に関するコス）（ＣＯ８Ｔ
）が決定される。またバイア・コストと呼ばれる、セル
中の配線を折り曲げる事に関するコストも、ブロック２
６６の工程中に各セル毎に決定される。次にブロック２
６８に示すように、プロセッサ配列ンステムを用いる事
によって、ネットを接続する最小コストの経路が決定さ
れる。もし配線工程が成功している事がブロック２７０
で判定されれば、プｏツク２７２でネット数工が増計数
される。もしネット■の配線が不成功であれば、ブロッ
ク２フ４’ｔ４−バーフローが記録され、ブロック２７
２に移る。ブロック２７６では［全ネットが終了したか
？」という質問がなされる。もし答が否であればブロッ
ク２６４に戻り、これまでに示した処理？次のネットに
付き行なう。もし全ネットが処理済であれば、２７８に
示すように工程は外に出る。

第１４図は第１３図の混雑評価工程２６０の一般的な流
れを示す。ネット・データが２８０に示すように与えら
れ、ブロック２８２に示すように評価がゼロに初期値設
定される。与えられたネットの混雑評価はブロック２８
６で行なわれる。ここでは２つの妥当な仮定がなされて
いる。第１に配線は最短の可能な経路を辿るのが最もあ
りそうな事であり、第２に２点間の接続はおそらく多数
のジグザグ経路は含まずむしろ高々２つの屈曲しか含ｆ
ないであろうという事である。ブロック２８８に示すよ
うに、あらゆるセル境界において評価値が累算σれる。

ブロック２８６と同じ副工程が、２８８（ｒ減算で置き
換えて、第１３図のブロック２６４で用いられる事に注
意されたい。ブロック２９０及び２９２は全ネットにわ
たる順序付け？制御する。もし全部のネットが終了すれ
ば、２９４に示すように工程は外へ出る。

第１５図は、上述の２つの仮定が満足されるような、セ
ルＡ及びＢの２点を接続する全ての配線経路を示す。境
界最小長方形２９６は、２点Ａ及びＢを含む最小の長方
形と定棧される。２点金接続する全ての最短経路は最小
長方形２９６の内部に存在しなければならない。図から
明らかなように、−与えられたセル境界７適過する配線
経路の数は最小長方形２９６内で変（ヒする。経路の数
は、２点Ａ、Ｂからのセル距離が水平及び垂直チャネル
に沿って増加すると共に、１に減少する。長方形の中央
部分のセルは全部す１で表わされるように、いずれかの
方向に１つだけの経路を有する。

第１５図から明らかになった原理に従って、与えられた
ネットによる混雑評価が次のように行なわれる。但し以
下に示す方法同様に、多くの他の評価値を定式ｆヒし用
いる事もできる。

第１６図は、２９８に示すような与えられたネットの各
ＬＳＴ■に関する混雑評価への寄与のテンプレート・パ
ターン（Ｔ）である。与えられたネットの混雑評価寄与
は、迂回路のｏ′Ｊ能性を許し且つ最小長方形の内側を
強調して、決定される。

与えられたネットのＬＳＴによる混雑評価値は、垂直な
場合が対称であるような、水平セル境界線交差に関して
示されている。セルから逃げるだめの水平パースを保存
するとして、これらの値の別の解釈を与える事ができる
。最小長方形の内側では、０値全持つセル境界に１の値
が割り当てられる。最小長方形の左右の辺の外側では、
全ての値は口になる。最小長方形の右又は左の辺のネッ
ト・ノード全部に関して、辺の値は４にされる。これは
町ｈヒな迂回経路に関する半分の強さである。

５つのＬＳＴネットに関して今述べたように計算された
混雑評価を与の例が第１７図に示されている。ＬＳＴは
第１６図のように■印で表わされ、最小長方形は太い線
で示されている。任意の数のＬＳＴに関する混雑評価が
同様の方法で行なわれる。

第１８図及び第１９図は各々、セル境界における水平及
び垂直の混雑評価値の６次元的グラフである。垂直軸は
多くのネットにわたって合計された混雑評洒値に比例す
るように描かれている。このグラフは、第１３図のブロ
ック２６０及び２６４の後に得られる混雑評価の値を表
わしている。

上述の説明に従って、第１４図のブロック２８６を実行
するために制御装置及びＳＰＥによって行なわれるステ
ップを第２０図の流れ図に示す。

各ＳＰＥは、特定のＳＰＥメモリ・アドレス中にそれ自
身の水平セル位置（ＸＩＤ）及び垂直セル位置（ＹＩＤ
）のデータを有する。制御装置は各ネット毎にネツ）Ｌ
ＳＴの水平位置の最大及び最小（Ｘｍ　ｉ　ｎ、Ｘｍａ
ｘ　）並びに垂直位置の最大及び最小（Ｙｍｉ　ｎ、Ｙ
ｍａｘ）のデータを有する。ざらにチップ中のセル位置
？表わす各ＳＰＥは、そのセル中にＬＳＴ：有するネッ
トのリストをそのメモリに記憶している。

次に、与えられたネットに付き水平混雑評価及び垂直混
雑評価の工程が連続して実行される。水平評価において
は、最初に第１６図のテンプレート（Ｔ）が作られ、次
に最小長方形領域に依存して値が変更される。第２０図
の流れ図は水平工程及び垂直工程が同様に且つ対称的な
方式で実行される事を示している。

第２０．１図〜第２０３図は、所定のネットの混雑評価
を行なう時に制御装置及びＳＰＥ配列が論理的にどのよ
うに進むかを示す、物理的設計装置に関する流れ図であ
る。制御装置は論理ブロック６０２に入ると、上述のネ
ットのＮ　Ｅ　Ｔ　Ｉ　Ｄ　、Ｘｍ１ｎ。

Ｘｍａｘ、Ｙｍ　ｉ　ｎ、Ｙｍａｘｉ全部のＳＰＥへ同
報通信する。ネット混雑評価値を加算するか又は減算す
るかの条件もこの時に同報通信される。

次に工程は論理ブロック３０４に准む。ここでは水平テ
ンプレート工程に関するジャンプ・アドレスのＤＭＡが
開始される。次に工程はブロック６０６に進み、配列を
リセットししばらく待機する。

このリセット信号は全部のＳＰＥの論理ブロック６４０
を開始させる。３０４及び３０６で説明した論理機能は
適当なプログラムで配列を起動させる。３０乙の待ち時
間はＳＰＥがサービス・ワードのビジー・ピントをセン
トする時間を有するように充分に長く取られる。次にブ
ロック５１０及び３１４に示すようにサービス・ワード
のビジー・ビットが論理０になるまで、サービス・ワー
ドが質問される。この後、工程はブロック３１８に入り
、水平修正工程のために全部のＳＰＥへＤＭＡによって
ジャンプ・アドレスを同報通信する。

次にブロック３２０で配列をリセットし待機する。

このリセット信号は３２２に示すように、全部のＳＰＥ
に論理ブロック６６２の実行全開始させる。

次に工程はブロック３２４に進み、ブロック５２４及び
３２８に示すようにビジー・ビットが０になるまで配列
の全部のＳＰＥからサービス・ワードを読取り続ける。

この後、与えられたネットの垂直混雑評価に関して類似
のステップ系列６０４〜３２８が繰り返される。

３０４．６０６．５１０．６１８及び６２０に示す標準
的作業は配列のりセントとして以前に説明したものであ
る。

制御装置の動作全要約すると、副工程３０４．５０６及
び６１０は水平混雑評価のためのテンプレート作成に関
する。副工程５１８．３２０７Ｊび３２４は以前説明し
た最小長方形に関する修正を行なう。

ＳＰＥはリセット論理ブロック３０６の作用により制御
装置によってリセットされるまで、６３８に示すように
待機モードにある。ブロック３゜６は水平テンプレート
工程金始めるために論理ブロック３４０ｉ開始させる。

次に工程はブロック３４２に進み、サービス・ワードの
ビジー・ビントラ論理１にセットする。次にブロック３
４４に示すようにＳＰＥは変数ＴＥＭＰの値全０に初期
値設定し、ＬＳＴ隣と呼ばれる論理変数を論理〇に七ノ
ｉ・する。この時ＳＰＥの動作はネットのＬＳＴがセル
中にあるが否かに依存して異なったコース２敗る。ブロ
ック６４８及び３５０に示すように、もしセルがネット
のＬＳＴを含めばＳＰＥはその論理変数ＬｓＴを１にし
、もしセルがＩ、ＳＴｉ含寸なければ変数ＬＳＴを０に
セントする。

そのＬＳＴ値が１であるようなＳＰＥだけが、ブロック
３５４に示すようにこの時８のＴＥＭＰ値を割り当てら
れ、その隣シに適当な値を送信する。

次に全部のＳＰＥが、ブロック３６２で制御装置からり
セントされるまで、３５６．３５８及び５６０又は６６
２及び３３４の動作を繰り返す。工程は全ての隣接セル
から読取りを行なうためにブロック６５６に進み、次に
ブロック３５８で「何らかの数値が受信されたか否か？
」の質問がなされる。もしこの質問に対する答が否であ
ればブロック３６６に進みビジー・ビットをオフにセッ
トし再びブロック５５６に戻る。従って５ＰＥｉｌ″ｒ
、、数値が受信されない限り、隣接セルから受信するた
めの試みを繰り返し、ビジー・ピンＨａにリセットする
。しかしながら隣りから何らかの数値？受は取ると（３
５８からのイエスの分岐）、ＳＰＥはプロンクロ５２で
ビジー・ピント全１にセントし、ブロック３６４の動作
に進む。ブロック６６４が終了すると、工程はブロック
６５６に戻り、隣接セルからの数値金堂は喉る試み？繰
り返す。

ブロック６６０に示すようにどのＳＰＥも隣、りから数
値を受は取らなくなるまでに、副工程６５４．５５６及
び３３４によってテンプレートが基本的に作成される。

ブロック３２０における制御装置からの再プロンプティ
ングの時、各ＳＰＥはブロック６６２において修市工程
を開始する。変数ＴＥＭＰとして計算された数値は各セ
ルの西ポートの混雑評価のためのものである。もしセル
が前述の最小長方形の左側境界の向う側にあれば、ブロ
ック３７４が数値ｔＯに変更し、一方セルが境界ＬＳＴ
の隣りにあればブロック３８０がそれを４にセットする
。もしセルが最小長方形の上側にあれＱま、ブロック３
８４がそれＩｎにセットし、もしセルが最小長方形の下
側又は右にあればブロック３９０がそれを０にセットす
る。ブロック４００及び４０２は、境界の右側のセルが
ＬＳＴ’ｉ含むか否かに依存して、数値を４又はＤにセ
ントする。ブロック６９８は、もし数１直がＯであれば
、最小長方形の内側において、内部の値を１にする。

このようにしてＴＥＭＰ値が変更された後、ＳＰＥは西
ポー１−混雑評価の総計に対してＴＥＭＰ値を、ブロッ
ク４０６では加算又はブロック４０８では減算する。次
にそのＴＥＭＰ値は西隣に転送され、そのＴＥＭＰ値は
ブロック４１０に示すように与えられたネットからの東
ポート寄与とじて用いられる。次にブロック４１２にお
いて東隣から送られた数値を受は取り、東ポート混雑評
価値に対してその受信した数値をブロック４１６では加
算又はブロック４１８では減算する。次にブロック４２
０で、ビジー・ピット？０にセントする。

これは混雑評価の水平部分の完了を表わす。そしてＳＰ
Ｅは４２２に示すように対称的な垂直工程又は他の工程
に関する制御装置からのプロンプティングを待つ。

制御装置のブロック５１０．３１４．５２４．６２８及
びＳＰＥのブロック３４２．６６０．３６２．３６４及
び４２２に示すように配列のＳＰＥと共に制御装置によ
って実行される工程は以前に同期化機構と名付けたもの
である二 第１６図に戻り、ブロック２６６の副工程をより詳細に
説明する。セル境界のポート・コストは、チャネル容量
及びそのポートの混雑評（ＨｆｌＦの関数として、次の
理論に従って計算される。これらのホード・コストは、
もしあればバイア・コスト即ち配線を経路上で曲げる事
のコストと共に経路に沿って累計された時、配線経路の
コスト？構成する。

ポート・コストの良好な実施例に関する背景理−輪はい
くつかの方針を取る。

（ａ）チャネル容量が等しければ、ポート・コストはそ
のポートの混雑評価に比例すべきである。

（ｂ）　　もしポートのチャネル容量が０であれば、コ
ストは無限大であるべきである。

（ｃ）　　多数のトランクが利用ｏＪ能な時、混雑評価
はコストに対して小心な影響しか与えるべきでない。

（ａ）　　ポート毎に同じ混雑評価が与えられた時、異
なったチャネル容量を有するポートに割ｇ当てられたポ
ート・コストの意味は次のように説明する事ができる。

チャネル容量Ｃに関するポート・コストヲ、チャネル容
量Ｃ＋１のポート・コストｐのα倍であるとする（αは
１．２．６．４・・・・・・等〕。その容量がＣである
ポートたけを通過する長さＬの経路は、総コストがαＰ
Ｌである。一方１つトランクの数の多い（Ｃ＋１トラツ
ク）ポートだけから成る経路は、長さがαＬであっても
同じコストである。見方を変えると、もし迂回路がＣト
ランクのポート全１回通る代わりにＣ＋１トランクのポ
ートを通れば、（α−１）の長さの迂回経路の方が好ま
しいという重金αは意味している。従ってαの良好な選
択はチャネル容量の減少関数である。

即ちトランクの数が小さければαは高い（実際トランク
が存在しなければα−ωである）。また多数のトラック
が利用可能ならばαは１に近づく。これは多数のトラン
クが利用可能な時は迂回する理由が存在しない事？意味
している。

チャネル容量の関数としてのαの望ましい傾向は第２１
図に示しである。このαの望ましい傾向は多くの方式で
定量的に達成する事ができる。

例えば、 （１）　　ａ　１四了 但し０≦βく１及びｃ＞。

（ｅ）需要が供給よりも高ければポート・コストは尚く
なければならず、供給が需要よりも高ければ非辞に小さ
くなければならない。ＣＥの混雑評Ｉ（ＩｌＩ値が与え
られれば、（ＣＥ÷１６）が需要全近似するために用い
られる。

上、ｆｅｉ由により、ポート・コストＰＣの計算は次の
ような形？取る。

（１）Ｃ二〇ならば、ｐｃ−■ Ｌ２）　　”５ｃ即ち供給過剰の場合、６ ＣＥ ＰＣ＝ＣＤ＋ＣＥＸ２ｅＸｐ（（−−Ｃ）Ｘニー１）１
６　　　　２ （３）ｃ−！−〉Ｃ即ち需要過剰の場合、６ Ｃ＝１に関して、ＰＣ＝ＣＤ＋４．５ＣＥＣ＝２に関し
て、ＰＣ＝ＣＤ＋４．５ＣＥＣ≧６に関して、Ｐ　Ｃ＝
　ＣＤ−ｔ−０，５ＣＥ−ｆｃＥ　Ｘ２　ｅ　ｘ　ｐ　
（”　）但し２　ｅｘｐ　Ａは２のＡ乗を意味する。

第２２図はＣＥ及びＣの関数としてポート・コスト’２
図示したもの、第２３′図は２変数の関数として垂直軸
方向にポート・コストヲ定性的に描いたものである。

他の項がポート・コストに加算されても良い。

この項はどこのセル境界を交差する場合でも固定値であ
る、直接距離コストの形ｉｆつてもよく、又は内部セル
の複雑性のある測度を表わしてもよい　このパラメータ
は上式中ではＣＤで表わされている。ポート・コストの
計算は制御装置にプロンプトされた時に配列中のあらゆ
るＳＰＥにおいて行なわれる。この工程の正確な流れ図
は明白なので省略した。

セルのバイア・コストＶＣは、セル中で既に便ＩＩＩさ
れたバイアの数Ｖｕｓｅｄの関数として計算される。ま
た関数にセルの特定のパラメータＶｍａｘ及びＶ　ｍｉ
ｎも利用する。各セルあるいは対応する５ＰＥｆ／Ｊ、
利？ｉ１１装置によってプロンプトされた時に次のよう
にバイア・コストヲ計Ｗする。

（ａ）　　Ｖ　ｕ　ｓ　ｅ　ｄ＜　Ｖｍｉ　ｎの場合：
　ｖｃＨ殆んど０゜しかしタイ・プレーカーとして役立
つために小さな数１直が割り当てられても良い。この目
的のためＫ　Ｖ　Ｃ＝　Ｖｕｓｅｄ　ｆ用い得る。

Ｑ））、　　Ｖ　ｕｓｅｄ　＝Ｖｍａｘの場合：ｖｃ＝
ｃ。

（ｃ）　　Ｖｍｉｎ≦Ｖ　ｕｓｅｄ　＜　Ｖ　ｍａｘの
場合：　Ｖ　ｕｓｅｄ＝＝ＶｍａｘにおいてＶＣが無限
大になるような、Ｖ　ｕｓｅｄ　の指数関数的に増大す
る関数。現在の実施例では無限大はＭ＝（２ｅｘｐ１６
　）−１，＝６５５３５という最大の計算機ワード値と
して実現きれている。従ってこの場合のＶＣは次式の通
りに６土算される。

ＶＣ＝ｍａｘ　（Ｖｕｓｅｄ、　ＭＸ２　ｅｘｐ（−δ
Ｘ　（Ｖｍａｘ−Ｖ　ｕ　ｓ　ｅ　ｄ但しδは２以下の
小さな定数である。

再び第１３図に戻り、主な処理工程２６８、即ちネソ）
Ｉの配線を以下詳細に説明する。最初に各ＳＰＥにおい
て次の数値が計算される。

（、）　　配線すべきネット（ネットＩ）（ｂ）　　全
４ポートに関する現在のポート・コスト（ｃ）　　セル
に関する現在のバイア その他にＳＰＥはメモリ中に次の数値を含む。

これらはセルに対応するか又は初期に記憶されたグロー
バルな定数等である。

（ｄ）　　迂回限界（ＤＬＩＭ） （ｅ）全４ポートの現在のチャネル容量（ｆ）４ポート
の現在の混雑評価 （ｇ）　　セルに関するＶｍｉｎ、Ｖｍａｘ、Ｖｕｓｅ
ｄ及びＤ 第２４図は第１３図の大局的経路決定工程のブロック２
６８のより詳細な流れ図である。前に述べたようにポー
ト・コスト及びバイア・コストは、ら与えられる。ソー
スとは工程において既に接続されたネット部分金言う。

□次に、最初、普通ネットのＬＳＴの１つが４２４に示
すように初期ソースに選択される。しばしば大局的配線
工程の前にネットの一部が既に部分的に経路決定されて
いる事がある。その場合はその部分的ネット全体がソー
スとして働く。任意のＬＳＴｉ初期ソースとして選択す
る事ができるが、一般的な配線０Ｔ能性金高めるために
初期ソースの選択において異なった方式金剛いてもよい
。ネットの残りのＬＳＴはシンクと考えられる。ブロッ
ク４２６において、経路コスト２伝搬ブせ、次にブロッ
ク４２８で伝搬が成功したか否かを決定する。もし不成
功ならば、線４６０のオーバーフロー出口が存在する。

もし成功であれば、ブロック４５２で、到達したシンク
のどれがソースに接続てれるかを決定する。次にブロッ
ク４５４でバンク・トレースを開始し、ノ／りからソー
スへ更新全行なっていく。次に工程はブロック４３６に
進み、新しく接続された経路全体ｔノースに付は加える
。次にブロック４′６８で、全てのＬＳＴが接続された
かどうかが決定される。もし否であれば工程はブロック
４２６にループ・バンクする。もし全てのＬＳＴが接続
されれば、第１６図のブロック２７０へ移る。

副工程４２６〜４６８を通過するたびに、既に接続され
たネット部分に付加的なＬＳＴが接続されて、全てのＬ
ＳＴが接続される。ブロック４２６〜４６４は、ソース
全体からシンクＬＳＴのいずれかへの最小コスト経路を
決定しＬＳＴｉ経路で接続する。経路の長さは、ソース
からシンクへの最短到達可能距離の差迂回限界（ＤＬＩ
Ｍ）内に制御される。ＬＳＴがソースに接続されると、
ブロック４３６に示すように新しく接続されたＬＳＴｉ
含む部分経路全体が新たなソースとなり、ブロック４２
６〜４３４の工程が、全てのＬＳＴの接続されるまで反
復される。もしもそれ以上のＬＳＴがソースから接続不
可能ならば、ブロック４２８で不幸なオーバーフロー状
態が生じ、線４６０においてオーバーフロー出口が必要
になる。

これは別の方法で処理される。

種々の評価値やコスト全計算する方法、迂回限界の選択
（チップ寸法及びその複雑度に依存して、０から１５程
度までの範囲にある）、配線されるネットの順序及び初
期ソースの選択、これら全てが全ネットの配線の成功に
寄与する。しかしながらこれらが一度決定されると、本
発明の機械は与えられた拘束の範囲内で迅速且つ効率的
に真の最良コストの経路全決定する。全ての実用的な目
的のために、従来技術の方法は、最良コストヲ有さない
かもしれないある可能な経路を見つけ出す事しかできな
かった。上記パラメータの採用は、主に配列における並
列処理のスピードによって可能になっている。従ってオ
ーバーフロー出口４３０は工程中の例外的な事象でなけ
ればならない。

第１３図に示す副王程２７４はオーバーフロー状態を処
理するために用いられる。この状態を処理する１つの方
法はオーバーフローを記録し、図示されているように次
のネットに進む事である。

次に大局的配線全体が終了した時、オーバーフロー処理
用の別の工程を開始する事ができる。またその代りに、
副工程２７４をその場でのオーバーフロー処理側工程で
置き換える事も可能である。

この処理は以前に経路決定したネットのあるものを修正
し現在のネット経路決定？再試行してもよい。

制御装置は、全てのＬＳＴ’ｉ接続するために、普通ネ
ット中のＬＳＴの総数よりも１回少ない回数、第２４図
の副工程４２６〜４６６を実行する。

第２５図は制御装置に関する第２４図の主要な副工程４
２６（経路コストの伝搬）の流れ図である。この工程は
ブロック４４４で開始し、ブロック４４６に進んで最初
に伝搬初期値設定のために配列ｋ　’Ｊ上セツトる。次
に工程は４４８及び４５０に示すようにビジー・ビット
がオフになるまで普通の方式で待機する。次にブロック
４５２で伝搬のために配列をリセツトする。そしてビジ
ー・ビットがオフになるまで普通の方式で待機Ｔる。

もしビジー・ビットがオフになれば、工程はブロック４
６０に進み、エンド・フラグがオンがどうかを判定する
。もしエンド・フラグがオンであれば、工程は第１５図
のブロック２６２に出る。もしエンド・フラグがオンで
なければ、工程はブロック４６４に進み活動フラグがオ
フかどうかを判是する。もし活動フラグがオフでなけれ
ば工程はブロック４５２に戻る。もし活動フラグがオフ
でめれば第１３図のブロック２７４に行く。

第２６１図、第２６２図、第２６６図及び第２７図は配
列中のＳＰＥに関する第２４図の経路コスト伝搬副王程
４２６の流れ図である。ブロック４７２にお・いてＳＰ
Ｅは伝１６初期値設定のためにリセソトジれ、ブロック
４７４ではビジー・ビットがオンにセソトサれる。次に
ブロック４７６で伝搬初期値設定が行なわれ、伝搬ステ
ップ中で用いられる関連のある変数及びフラグがこのブ
ロックに示すようにセントされる。最初全ポートが、全
隣接Ｓ　ＰＥを読取り且つその内容を無視する事により
クリアされる（４７．！５．１）。この操作によす全ポ
ートはポート・メールボンクス・フラグ機構ヲＩＪセン
トする事によって隣から情報を受は取る準備ができる。

ボート毎に長さがＤ＝１＋ＤＬＩＭのフラグ値のスタッ
クが割り当てられ、スタック・ポインタによってインデ
ックスされる。有効なインデックス（ｌ″Ｘ、０〜（Ｄ
’−１）である。スタックは、与えられた出力ボートに
関して、スタック・ポインタによって巡回的に指示され
た時間に最良のコストの経路？含む入力ポートがどれか
という情報を含む。

肩効な経路コストを最初に受は取ると、全てのＳＰＥは
多くてＤ回の間、経路コストの伝搬に関与する。活動カ
ウンタ（４７’６．２）Ｕその期間の後のＳＰＥの関与
を停止させるために用いられる。

活動フラグ・ビット（４７６，５）は、ＳＰＥがまだ活
動伝搬期間内にある事を制御装置に示すために萌われる
サービス・ワード・ピントの１つである。エンド・フラ
グ（４７６，５）はサービス・ワードの他のビットであ
って、論理１にセントされた時に、ネットのＬＳＴｉ有
するセル（シンク・セルのみ）が特定の活動肋間（Ｄ）
Ｋ於てどこかから経路コスト？受は取った事即ちソース
からシンクへの全ての経路が迂回限界内でトラバースざ
れた手金制御装置に表示する。／ツク・セルの使用に関
する最良値はＭ即ち無限大を表わす数に初ＫＡ値設定さ
れる。

第２５図に戻って、初期直設定４４６の後、制御装置は
ブロック４５２で伝搬をプロンプトする。

伝搬のプロンプティングの各々は１セルのピンチで経路
を伸ばす。制鐸装＃は、全てのＳＰＥがこの１セル伝搬
を終えたか否か？検査し、さらにブロック４６０でエン
ド・フラグがオンか否かを検査する。エンド・フラグが
オンであれば、これは迂回限界内でソースから／ツクへ
の全経路がトラバースされた手金意味する。もしエンド
・フラグが丑だオンでなければ、ブロック４６４で制御
装＃はまだ活動り伝搬サイクル中のＳＰＥがあるか否か
を検査し、もしそうであればブロック４５２で配列に他
の伝搬サイクルをプロンプトする。しかしながら、もし
もどのＳＰＥも活動期間内にないならば、オーバーフロ
ーが検出され、第１６図のブロック２７４に示すような
適当な動作が行なわれる。伝搬工程４５２を通過する毎
に、配列はセルきざみに経路に付加される拳Ｍ長全処理
する。

ＳＰ、Ｅが伝搬初期値設定？終了した後、制御装置が伝
搬を再プロンプトし続ける回数だけ、実際の伝搬動作が
上述のようにブロック４８２から４９４金経て５１６又
は５５４まで反復される。その各々において、５ＰＥｆ
ｌブロツク４８６で活動カウンタ匝がＤに等しいかどう
かを検査する。もし活動カウンタ値がＤであれば、ブロ
ック４８８に進み全ホートラクリアし、次にブロック４
９０で活動フラグ全オフにセントする。次にブロック４
９２に進み、ビジー・ビットをオフにセットし、４９４
に示すように待機する。もし活動カウンタ１直がＤでな
ければ、ＳＰＥがソース・セルを表わしているか否かに
依存して工程は異なったコースを取る（ブロック４９６
）。ノース・セルＳＰＥは第２７図のブロック５００に
進み、活動カウンタを増計数し活動フラグ全オンにセン
トする。これに続いて論理工程はブロック５０２に進み
全ホートラクリアし次にブロック５０４に進み全４ポー
トに関する経路コストに対して直接にポートコスト全学
に割り当てる事によって各ポートにｉｊＬで経路コスト
を計算し、次にこれを隣に送る。

次にノース・セルＳＰＥはビジー・フラグ全オフにセッ
トしく普通医の伝搬工程の通過？）待機する。経路コス
トが隣に「送信」される時５ブロツク５０６．５１０及
び５１２に示すように、実際の数値の送信は経路コスト
がＭ即ち無限大を表わす数値よりも小さい場合にしか起
きていない。この事情はり、下に承すように隣に経路コ
ストを「送ｆぎ」する全ての場合に当てはする。

第２６１図に戻る。もしＳＰＥがソース・セルを表わさ
なければ、工程はブロック４９６から第２６２ｉのブロ
ック５２０に進み隣全部即ちＮ１Ｅ、Ｓ、Ｗから経路コ
ストヲ読取る。もし隣から何の数１直も送信されなけれ
ば５数値はＭにセントされる。次に論理工程はブロック
５２２に進みＭ以外の何らかの数値が受信されたか否か
を判定する。もし有限値が受信されなかったならば、工
程は第２６３図のブロック５４８に進む。もし何らかの
有限の経路コストが受信されたならば、工程はブロック
５２６に進み活動フラグ全オンにセントし活動カウンタ
を増計数する。次に工程はブロック５２８において、シ
ンク・セルの場合はブロック５６８に、中間のセルの場
合はブロック５ろ２に分岐する。中間セルを表わｆｓＰ
Ｅは次にブロック５３２に示すように屈曲経路コスト？
計算する。屈曲経路コストは単にバイア・コストと受信
した経路コストとの和である。ブロック５３２中の■記
号で表わされた和動作については後述する。次にブロッ
ク５３４で各ポート毎に次の動作が行なわれる。

（１）　　向い側のポートの経路コスト及び直交方向の
ポートに関する２つの屈曲経路コストのうち最小の経絡
コスト、例えば化ポートに関しては、（Ｓ、ＥＥ％ＷＷ
）の最小値の方向を見い出す。

（２）　　スタック・ポインタによって指示されるスタ
ック中に最良の方向全記録する。

（３）経路コストに対して出ポ１−ト・コストヲ加算す
る。

（４）経路コストを隣に送る。

次に工程はブロック５５４から第２６６図のプロッタ５
４８に進む。前に述べたよつに／ツク・セルＳＰＥの動
作はブロック５２８からブロック５３８に分岐し、そこ
で活動カウンタの値がＤにン・１して検査される。もし
活動カウンタがＤに等しケレばブロック５４０において
エンド・フラグがオンにセントされる。次にシンク・セ
ルＳＰＥはブロック５４２に進み、到来した経路コスト
の最良のものを見い出し、新しい最良の方向全記録する
。次に工程はブロック５４４に進み、ここで新しい最良
の値と以前に記憶されていた最良の値とが比較される。

もし以前の値が悪くなければ、工程は直接プロッタ５４
８に進む。もし新しい最良１直の方が良ければ、Ｉ４は
ブロック５４６に進み最良値、最良インデックス及び最
良ポートを更新する。ＳＰＥの行なう最終の動作はプロ
ッタ５４８．５５０及び５５′２に示すような、スタッ
ク・ポインタｋＤｋ法として増計数する事である。

次に工程はビジー・ピッＨ−オフにセントし待機する。

ブロック５５８．５６０及び５６２はプロッタ５６２を
より詳細に示したものであり、ブロック５５８では数値
が加算され、ブロック５６０では結果がＭよりも大きい
か否かが判定され、もしＭよシも大きければプロッタ５
６２でＭに戻される。

この変型された加算は、無限大にいかなる数？加算して
も無限大が生じるため、無限大表示の変換によって生じ
る。

ソース・セルを表わすＳＰＥぽ、Ｄ回の通過の間、基本
的には適当なポート・コストをその隣に経路コストとし
て伝える。各通過において活動カウンタは増計数され、
それがＤに到達する時、ブロック４８乙に示すようにソ
ースＳＰＥは伝搬に関与するのを停止し活動フラグを下
ろす。中間セルは、基本的には伝搬に関与するために隣
から最初の有効な経路コストが送られて来るまで待機す
る。中間セル及びシンク・セルを表わすＳＰＥは各通過
毎にブロック５４８に示すようにそれらのスタッタ・ポ
イン、ｉｆ増計数する。この変数は実際にはブロック５
４８．５５０及び５５２の機構によって循環方式で増計
数される。非ソース・セルは、ブロック５２０及び５２
２に示すように最初に隣から有効な経路コストを受は取
る事によって活動状態になると、活動フラグｔオンにセ
ットし活動力ラン５を増計数する。活動力ランｌ値は、
ブロック４８乙に示すように自己終端のために用いられ
、活動層Ｍはプロッタ４９０に示すよりにソース・セル
の場合と同様に用いられる。プロッタ５４０に示すよう
に／フタＳＰＥのどれかが活動期間の終了？知らせるた
めにエンド・フラグ？上げると、これは全伝搬工程を終
了される。

これらの動作の性質から生じる２つの事実は、（１）セ
ル（Ｓｐｌがひとたび活動状態になると、それは０回１
曳過するまで（即ちブロック５２２からのイエス分岐ま
で）連続して活動状態を維持する。

（２）Ｓｌ）Ｅのポートが受は取る最良の経路匝はｄ過
の数の非増加関数である。

活動期間の間、中間セルはプロッタ５３２及び５５４に
示すようにざらに処理全行なう。ここで各々北、東、南
及び西から到来した経路コス）Ｎ、Ｅ、Ｓ、Ｗは、セル
内の屈曲の経路コス）ＮＮ。

ＥＥ、ＳＳ及びＷＷ？得るためにバイア・コストＶＣに
加算される。プロッタ５３２内に示されている和のはブ
ロック５５８，５６０及び５６２に示すように実行され
る。即ち値が、無限大？表わすＭｉ越えれば、それはＭ
に戻される。ブロック５３４において、出ポート毎にＳ
ＰＥは最良の到来経時方向及びコストを決定し、スタッ
クにその方向を記録し、更新された経路コストｆ隣に送
る。

但し隣に経路コストヲ送ると言う場合に、プロッタ５０
８に示すように無限大Ｍよシも小ざい場合に限って経路
コストが実際に送られている事ｆｆ１Ｅ！解されたい。

北ポート？例に取ると、 （１）最良の経路コストは数値Ｓ、ＥＥ及びＷＷを比較
する事によって決定される。後者の２つは、北へ出るた
めにセル内で折れ曲らなければならない経路に関するコ
スト？表わす。

（２）勝った方向（この場合は、到来方向Ｓ、Ｅ又はＷ
）が現在のスタック・ポインｌによって指示される北ボ
ートのフラグ・スタックに記録される。

（３）　次に北隣に対して到来経路コストとして与える
ために、この最良の経路コストに化ポート・コストが加
算される。

（４）次に更新された経路コストが北隣に送られる。

他の全てのボートに関して同機の動作が行なわれる。

活動期間中シンク・セルはブロック５４２，５４４反び
５４６に示′ｊ＠作を行なう。シンク・セルは到来する
経路コストＮ、Ｅ、Ｓ、Ｗの最良のもの？見い出し、プ
ロッタ５４２に示すよりに勝った方向全記録する。もし
新しい最良の経路コストが古い最良の直よりも艮ければ
、ブロック５４６に示すように最良値、最良ボート、最
良インデツクスは（新きれる。

制御装置が伝搬のために配列をプロンプトする全回数は
、ＤＬＩＭにソースとシンクとの間の到達ｏＴ能距離及
び１を加えたものである。

第２８．１図〜＄２８８図は経路コストの伝搬？計算す
る時に敗られるステップの例？示す。セルＡはソース・
セルであって、部分ネットとして描かれている。セルＢ
及びＣはネットの２つの付加的なＬＳＴである。ソース
からシンクへの到達町ａヒ距離は、Ａ’：Ｃに接続する
４セル・ピンチである。４＋２＋１　＝７回のパスの全
部が第２８１図〜第２８．８図に示されている。セルの
中の数はパスの開始時のセルの活動力ラン３？表わす。

活動パターンはソースから開始し、波状に外側へ伝搬し
、第２８４図に示す６番目のパスによってＤ＝３の厚で
ｔ育するセルの活動帯？徐々に形成する。

活動帯は、第２８．８図に示すように最近接ＬＳＴ（Ｃ
）がＤ＝５回活動するまで外方へ進行する。

そしてＣの５ＰＥｕエンド・フラグ？上げ、経路コスト
伝搬過程？停止させる。

上述のよりに、第３図に示す配列から配列Ｉ１０プロセ
ッサを経て制御装置に至るＯＲパス構造はｉｌ制御装置
−配列間の通信において有利に用いられている。特に全
ＳＰＥから配列にＯＲされるサービス・ワードに制御装
置が次のもの？認識する事ｆｏＴ能にする。

（ａ）　　ビジー・ビット：もしどこかのＳＰＥがビジ
ーであればこれがオンになる。どのＳＰＥもビジーでな
い時だけ、ビジー・ビットはオフになる。

（ｂ）　　活動フラグ・ビット：どこかのＳＰＥが有効
な伝搬フェーズに関与している限り、活動フラグ、ビッ
トがオンになる。

（ｃ）エンド・フラグ：どこかのシンクにこのビットが
生じると、制御装置にコスト伝搬工程の停止が命ぜられ
る。

第２４図に戻ると、プロッタ４２６に示される経路コス
ト伝搬フェーズが成功裏に終る時、制御装置は（停正時
に２つ以上のセルに到達した場合。

例えば第２８１図〜第２８．８図に示すようにＢ及びＣ
の両方に到達した場合）到達したシンク・セルのどちら
？ソースに接続すべきか？決定する工程４６２を開始す
る。

ソースに接続すべき候補シンク・セルは、最良値の中で
最も良いもの？含むシンクである。活動フラグがオンで
あるシンク・セルは、全てこの段階に関与し、制御装置
はそれら？ポーリングする事によってそのどれが候補か
ｒ決定する。これは、到達されたシンク５ＰＥ（その活
動フラグはオンである）がＸＹ応答線全上昇させ、次に
制ｍ装置が応答している行と列を一時に１回選択し、最
小値？見い出すためにそれらの最良＠？質関する事によ
って行なわれる。候補シンクがこのよりにして決定でれ
ると、制御装［は選ばれたＳＰＥにその状態を知らせる
。

ブロック４３４に示すバンクトレース及び更新工程は、
選ばれた候補シンク？ソースに接続する。

制御装置は配列をプロンプトし、適当なフラグ？初期値
設定し、■１０レジス５通信Ｆｌ＆溝（即ちＡＩＮラッ
チのフラグ機構）を通じて候補シンクに情報全厚えて、
バッタトレースを初期値設定する。

第２９１図及び第２９２図は、第２９１図を上に第２９
２図を下につなげて見ると、配列中の各ＳＰＥプログラ
ムを表わす流れ図になる。利８装置はエンド・フラグの
上昇？検出する時・（ツタトレース工程を終了させる。

サービス・ワード中の指定さｒたビットである。エンド
・フラグは最初ダウン・レベルにあす、ソース・セルＳ
ＰＥが）（ツクトレースの終了ｒ１キ号するのに用いら
れる。

バンクトレース・ルーチンに関する制御装置の動作は簡
明なので５その詳細な流れ図は示していない。

バックトレースの過程において、経路上のセルは全て自
分自身ｔネットの一部として呂己録し、チャネル容量及
び、もしあれば使用した・（イア−の数を更新する。セ
ルがネットの一部として記録全行な９方式は、オン）Ｉ
Ｄに関係したｇＸＩ　Ｔマスクの使用による。ＥＸＩＴ
マスク灯、各々のビットがＮ、Ｅ、Ｓ、Ｗの対応する方
向７表わす４ビツトの変叙である。ネットに関連するＥ
ＸＩＴマスタぽ、そのネットがセルを通過しＥＸＩＴマ
スクの１にセットされたピントに対応するポート全通っ
て接続される事？意味する。

ＳＰＥは、ｉｌｌ　Ｎ装置によってプロンプトされた時
、ブロック５６８で最初エンド・フラグを０にリセット
し全てのボートをクリアする。次にＳＰＥは、与えられ
たＳＰＥがどのセル？表わしているかに依存して特定の
動作全行なう。セル状態即ちソース、シンク、又は中間
のセルのどれであるかはブロック５７０で決定される。

次にシンク・セルＳＰＥはそのセルが候補シンクか否か
が決定される。これはブロック５７２に示すよりにＡＩ
Ｎピットが１になるまでサービス・ワードを読取る事に
よって行なわれる。ＡＩＮピントがオンとして読取られ
ると、候補シンクＳＰＥにおける工程はプロッタ５７６
に進む。制御装置は、セル？一意的に選択しそのセルの
■レジスタに任意のワードを送信する事によって候補シ
ンクのＡＩＮフラグ・ビットをセントする。ＡＩＮフラ
グハＳＰＥのブロック図に関して以前に示したようにセ
ント　さ才１．る。

次に候補シンク・セルのＳＰＥは、ブロック５７６に示
すように最良方向？バンクトレースの方向（’ＤＩＲＣ
）に最良インデンクス？ス５ツク・ポインタにコピーす
る事によってバッタトレース茫開始する。バンクトレー
ス出ボートのチャネル容量はプロッタ５７８に示すより
にネットによるトラツタの１史用を示すために減計数さ
れる。ネットＥＸＩＴマスタはプロッタ５８０にｒｒ＜
ＴようにＤＩＲＣに対応するピントをセントする事によ
って変更され、スタック・ポインタはブロック５８２に
示ｆよりに循環式に（即ちもし−１であればＤ−１にリ
セットする）減計数され１最後にスタック・ポイン３は
プロッタ５８４に示すようにＤＩＲＣによって指定され
た隣に送られる。

中間Ｓ　Ｐ　Ｅにブロック５８８に示すように育効なデ
ータが渡されるまで隣り全部を読取る。もし数値が受信
されると、これはス５ツク・ポインｌ値であるが、ＳＰ
Ｅはブロック５９２に示すよりにその到来した方向を人
ポートとして記録する。

そしてブロック５９４に示すように受信した数値？その
スタック・ポインｌとして割り当て、ブロック５９６に
示すように入ボート・チャネル容量ｒ減計数する。バン
クトレースに関する出方向にブロック５９８に示すよう
にスタック・ポインタによって指示される入ポート・フ
ラグ・スタック中に記憶された方向をルック・アップす
る事によって決定され、次にブロック５７８〜５８４　
カ以前に示したように実行される。ブロック５８０に示
すようにＥＸＩＴマスクが記録されている時、入ボート
・ピント＆びＤＩＲＣポート・ピントハ１にセントされ
る。

ソース・セルの場合、ブロック６０２に示すよりに数値
が受信されるまで隣全部が読取られる。

もし数値が受信されると、工程はプロッタ６０６に進み
、数値の到来したポートを入ポートとして記録する。隣
から数値を受は収ったソース・セルは、プロッタ６０８
に示すように入ボートのチャネル容量を更新し、ブロッ
ク６１０に示すようにネットＥＸＩＴマスクを記録し、
ブロック６１２でエンド・フラグを上げる。

この動作は第２４図のブロック４６４に示されるバック
トレース工程？終了させる。これまでに接続されたネッ
ト、即ちそのネットに関するＥＸＩＴマスタが空でない
（「全部Ｏ」でない）セルは、接続すべきネットのＬＳ
Ｔが残っている限り制御Ｈｊｔによって制御される伝搬
及びバッタトレース？反復するための新しいソースとな
る。これで与えられたネットの大局的配線に関する説明
を終える。

プロセッサの配列及びここで説明したンステムオ利用す
る効率的な大局的配４工程を説明するために用いる事の
できる多くの有用な変型が存在している。例えば２以上
のネットに関する活動セルが互いに重なり合わない事が
知られている時は、２以上のネットｉ同時に配線する事
がｏＴｆＴ目である。

また１つのネット全体チ一時に配線せずに、複数のネッ
トの種々の部分を、局所的な混雑測定に依存して、１ン
タリ一ブ方式で、１つのネットの１つの接沈の後に他の
ネットの他の接続ｆｈなって配線してもよい。

上述の説明は、プロセッサ配列が水平及び垂直の寸法に
おいて、問題のチップと少なくとも同じ大きさである事
？仮定していた。配列寸法よりも大きな寸法の問題を取
り扱うためにＳＰＥの特殊目的時分割を利用する有用な
方法を以下説明する。

プロセッサ配列は実用的であるためには妥当な寸法を持
だなければならないが、小さな配列を用いて、与えられ
た機械よりもはるかに大きな寸法のチップを表現する機
械？大きなペナルティなしにエミュレートする事が原理
的には可能である。配列の寸法に無関係に、機械よりも
大きな寸法の問題のチップ？処理しなければならないが
、ここで説明する機構はこの目的に対する新規な解決を
与える。

第１１図に戻り、■及びＮによって各々水平及び垂直の
次元のチップのセルの数を表記する。ざらにｍ及びｎに
よって第２図のＳＰＥのプロセッサ配列の列及び行の数
全表記する。第３０図に関して、Ｍ　＝　Ｑ　ｍ　＋　
ｒ但し０＜Ｑ及び０≦ｒ＜ｍ：並〈 びにＮ　＝　Ｓ　ｎ　＋　を但しａｓ及びＯ≦ｔａｎと
する。チップは機械と同じ大きさの１行ｍ列のセルから
成るフレームに概念的に分割される。従って水平方向に
は（Ｑ＋１）個のフレームが、垂直方向には（Ｓ＋１）
個のフレームが存在し、最初のＳＸＱフレームはフル・
サイズで、各次元の最後のフレームは各次元の残りのセ
ル１列及びｔｈｉ収容するために部分サイズになってい
る。

第２図に示すよりな機械の配列の境界線はチップのセル
のフレームの境界線に対応する。境界セルの近傍の端部
周回接続はチップのフレーム境界における瞬接セル間の
通信ヲｏＴ能にする。この場合機械の各ＳＰＥはチップ
の１つのセルだけではなく、チップ全体に規則的な間隔
で分布した（Ｑ＋１）ｘ（Ｓ＋１）個のセル？表わす。

配列の端部周回隣接接続はフレーム概念の実現に敗って
絶対的に必要なものではない。フレームは両方の次元に
アコーディオン方式で折りたたまれているものと考える
事もできる。そのような方式の折りタタみの１つの欠点
は、交互のフレームのセル・４ンデツクスが反転し、従
ってこの方向の反転？考慮するために大きなプログラミ
ング・オーバーヘッドが必要な事である。もう１つの欠
点は、この構成の下では１方向の掃引動作を行な９時に
多フレーム分の掃引のパイプライン化が不可能な事であ
る。

概念的にはチップは、各々機械プロセッサ配列と同一の
大きさのフレームから成る配列上に重ね合わされたもの
と考えられる。このチップはフレーム配列の左辺及び底
辺に対して整列される。各フレームは次の範囲内にある
ＦＩＤと呼ばれるフレームＩＤ２有する。

Ｏ８Ｆ■Ｄ〈（Ｓ＋１）×（Ｑ＋１） フレームに関する（機械配列に関する）水平及び垂直の
セル座標は各々ＦＸＩＤ及びＦＹＩＤと呼ばれる。チッ
プ・セル座標ＸＩＤ及びＹＩＤからフレーム相対値への
変換は次のようにして行なわれる。

ＹＩＤ　　　　ＸＩＤ （１）　　Ｆ　Ｉ　Ｄ　＝　（Ｑ　＋１　）　Ｘ　Ｌ　
−Ｊ　　＋　Ｌ−Ｊｎ　　　　　　　　　　　　　ｍ （２）　　ＦＸＩＤ＝ＸＩＤ　　ｍｏｄ　ｍ（３）　　
ＦＹＩＤ＝ＹＩＤ　ｍｏｄ　　ｎ但しＬ−ｊは商を、ｘ
　　ｍｏｄ　　ｙは剰余？、表わす。

ｙ 逆にＸ　Ｉ　Ｉ）及びＹＩＤは次の関係式で表わされる
。

＋４）　　ＸＩＤ＝ＦＸＩＤ＋ｍＸＦＩＤ　　ｍｏｄ　
　（Ｑ＋１　）第３０図Ｈチップ・フレーム、フレーム
ＩＤ。

Ｆ”ＸＩＤ、Ｆ’ＹＩＤ、ＸＩＤ及びＹＩＤｉ示シテい
る。

上記の除算の商及び剰余は、ｎ、ｍ及び（Ｑ＋１）が２
のべき乗の場合は、牟なるシフトという簡単なツータロ
プロセッサ動作になり得る。

叱標がチップの観点からフレームの４点へいかにして変
換されるか？示したが、以前に開示した種々の工程の実
施例に対する修ｉ′ｌＥを以下説明する。

各ＳＰＥはその局所メモリ（第６図の１９６）紫５　チ
ップの各フレームに等しく分割された領域支び共ｄ領域
に割り振る。前述の迂回限界、ス５ツク・ポイン５．現
在のネソ）ＩＤ等の共通データ及びＳＰＥプログラムは
この共通領域に存在する。セルＩＤ、混雑評価値、ネッ
ト・デー１１ポート・コスト１バイア関連値等のセルに
特有なデータはメモリの対応するフレーム領域に記憶さ
れる。従って機械全体のメモリ要求は、例えプロセッサ
の数が少なくても、チップと同じ大きざのより大きな機
械と殆んど同じである。各５ＰＥｆｉそれが表わす全て
のセルに関するデータ？保持するためにより大きなメモ
リ・スペース？必要とするだけである。

従って制＠装置及び隣接ＳｊＥは、データがフレームに
関して共通の性質を持つ場合以外は、データ転送の時に
どのフレームのデーｌが送信されるのか全特定しなけれ
ばならない。またデータ？受１言する時、ＳＰＥはデー
５と共に受は叡ったフレーム番号に対応するメモリの適
当な区画にそのデータ？記憶する。

実際にセルと通信する之めに、制御装＃は最初にセルＩ
Ｄ（ＸＩＤ、ＹＩＤ）ｋフレーム関連パラメータ（ＦＩ
Ｄ、ＦＸＩＤ、ＦＹＩＤ）に変換し、水平及び垂直の選
択器でＦＸＩＤ、ＦＹＩＤを選択し、その後でデータ及
びフレーム番号ＦＩＤ茫ＳＰＥに伝送する。

セルが隣と通信する場合、隣がそのセルと同じフレーム
内にあればデータに付属するフレーム番号は同一である
。従ってフレームの境界にあってフレームの外側の隣と
通洒するＳＰＥだけが受は敗った隣のフレーム番号を調
整する必要がある。

もしＤ≦に≦Ｓ＆び０２ｔ≦ＱとしてＳＰＥ中のデータ
がフレーム番号Ｆ　Ｉ　Ｄ＝ｋ　（Ｑ＋１　）＋１であ
７ｌ−Ｖｆ、、以下に与えるように隣のフレーム番号が
ＦＩＤ’　として計算される。

西：　ＦＸＩＤ≧１輿ＦＩＤ’＝ＦＩＤＦＸＩＤ−１１
計つ＋２１の時ＦＩＤ’　＝Ｆ　ＩＤ−ＩＦＸＩＤ二〇
且つ１＝０の時ＦＩＤ’は存在しない（即ち西隣が存在
しない９ 東：ＦＸＩＤ＜ｍ−１の時ＦＩＤ’　＝Ｆ’ＩＤＦＸよ
り−ｍ−１且つｔ＜Ｑの時ＦＩＤ’　＝ＦＩＤ　＋ＩＦ
ＸＩＤ−ｍ−１且つｔ＝Ｑの時ＦＩＤ’は存在しない北
：　ＦＹＩＤ＜ｎ−１尖Ｆ　ＩＤ’　＝Ｆ　Ｉ　ＤＦＹ
ＩＤ＝ｎ−ｊ且つｋ＜Ｓの時ＦＩＤ’＝ＦＩＤ＋（Ｑ＋
１　、）ＦＹＩＤ＝ｎ−１且つに＝Ｓの３１ｉＦＩＤ’
は存在しない南：ＦＹＩＤ　　１の時ＦＩＤ’　＝ＦＩ
ＤＦＹＩＤ＝０且つに≧１の時Ｆ’　ＩＤ’−Ｆ　ＩＤ
−（Ｑ＋１　）ＦＹＩＤ＝０且つに二〇の寺Ｆ　Ｉ　Ｄ
’は存在しない隣の存在についての上記の条件は前述の
活動セル領域の状態に付加される。

フレームの概念？用いる時、以前に説明したンステムの
全てはフレーム化構造に適合するように変型される。プ
ログラムにおけるそれらの変換の多りハマイクロプロセ
ッサ・プログラミング技術における通常の知識を有する
者によって実行可能である。フレーム化によるノくフオ
ーマンスへの影響のあるもの及び非常に一般的な・（ラ
ダイムの良好な実施例を以下に開示する。

（・ラダイムＡ）セル遂次動作二大局的経路決定のバッ
クトレースのような一時に１つのセルに付き行なわれる
動作は重大な影響？受けない。そのパフォーマンスハ、
ｕす算のオーバーヘッド及び各データ転送に関するフレ
ームよりの伝送４除けばチップ・すづズの機械と同じで
ある。

（・ラタゴムＢ）水平（又は垂直）掃引動作：多くの場
合１例えば物理的設計工程中の第１０図の１Ｅ罐な埋め
込みのブロック２３６において、ｂ又は列の１１ｊｌＨ
に及びインデツクスの増加又は減少する順に計算？実行
する必要が生じる。第３７図ｔｒｉ　７　／ｌ／・す１
ズの機械に関するパラダイムの流れ図を示す。

ブロック６１６に示すように、左端のセルが計算？セテ
ない、結果２プロツタ６１８に示すように東隣に渡す。

中間のセルはブロック６２０に示すように西から情報を
受は嘔り、ブロック６２２でこの情報に基いて計算が行
なわれる。

計算結果はブロック６１８に示すように東隣に渡される
。

右端のセルは、ブロック６２４に示すように西隣から清
報を受は取り、ブロック６２６に示すようにこの情報に
基いて計算が実行される。

計算が終了すると１ブロツク６２８に示Ｔように制御装
置に通知される。

小さな大きさのフレームｒヒ機械において、第３１図に
示す全ての行の完全な並列処理は不可能である。しかし
ながらＳＰＥは連続しｔフレームの行をパイプライン方
式で処理する事ができる。第３２．１図〜第３２．３図
はその概念？説明するものである。左側において、Ｍ＝
９’、Ｎ＝６のチップに関するフル・サイズの機械の使
用中の５ＰＥｆｌ各時間ステップ毎に影ｒ付けた。

フレ、ムの右側では、ｍ−５列ｎ＝２行の小さ　　　−
な機械がパイプライン比された掃引動作に用いられてい
る。ここでは機械の使用中のＳＰＥ及びチンプ上の対応
するセルに影を付けた。全部の図において、参考のため
フレームは太線で示した。一般にフル・サイズの機械に
関する全掃引時間はＭであり、フレーム化された機械の
全掃引時間は漸近的に（Ｍ　ｘ　Ｎ　）　／　（ｍ　Ｘ
　ｎ　）で表わされる。明らかにこの型の動作に関する
パフォーマンスのペナルティはそう大きくはない。

（・シタ工に〕　完全な並列動作：ポート・コスト計算
、バイア・コスト計算等はこのカテゴリーに属する。こ
の場合フル・す１ズの機械においてケでのセルのＳＰＥ
が完全に並列的に使用状態にある。より小さな機械は一
時に１フレームしか処理できず、処理に要する時間は、
フル・す４ズの機械の所要時間全１牟立とすれば２ＭＮ
　／　ｍ　ｎである。

（バラタ゛１即）　大局的伝搬動作：以前に、フル・す
１ズの機械の活動性がソース・セルかう外向きρてダイ
ヤモンド状の波動の形で伝搬する事を示した。フレーム
に重ね合せると、これらの活動セルはより小さな機械の
ＳＰＥに多重に重なる。従って第２４図のブロック４２
６〜４３８に示すような付加的Ｌ　５Ｔ（ｉ−接続する
各パスにおいて、それらの副工程はフレームに適合しな
ければならない。これは全ての到来する隣の経路コスト
が適当なフレームの部分に記憶される補助的作業スｌツ
タ？用いる事によって行なわれる。一連の受信の後、Ｓ
ＰＥは計算４行ない、全てのフレームの作業が実行され
るまで出力される経路コストをバッファする。その後、
新しいパス會始めるためにフレームＩＤと共に一連湾路
コストを隣に送る。明らかに、’ＳＰＥは作業スｌツタ
中の全てのｌスフ？処哩した後にのみビジー・フラグを
リセツトする。従って当然の事ながら、任意の時間にお
いて各ＳＰＥは異なったフレーム中のセルの伝搬ｆ処Ｆ
ＩＬ、ているかもしれない。機械サイズが小さい（例え
ば８×８以下）時のパフォーマンス・ペナルティはかな
り高い。このペナルティハ機械サイズがチップ・サイズ
に向って増大すると共に次第に減少する。無限大の機械
？用いた無限大のチップに比較して、　３２Ｘ５２のプ
ロセンサ配列から成る機械は平均的に処理時間が２倍に
なる。

コ１７）パフォーマンス・ペナルティの詳細な解析は他
の場所に記す。

本質的な事は、フレームｆヒされた機械のｓＰＥが衣わ
す異なったフレーム中の全てのセル？処理するために用
いられる作業スタックの概念である。

第２８．１図〜第２８８図に示す列に戻り、例えば第３
３図に示すフレーム？仮定する。これらの図かられかる
よりに１ｆｔ５動セルのＳＰＥに対する重なりは欠のよ
うに起きる。

Ｗｌ　　　１　　　　　　　１　　　　　４．５．８Ｗ
２　　１　　　　　　　２　　　　　４．５％７，８Ｗ
３　　１　　　　　　　２　　　　　１．４．５．７．
８Ｗ４　　１　　　　　　　３　　　　　１．６．４．
５．７．８Ｗ５　　１　　　　　　　４　　　　　１〜
８Ｗ６　１　　　　　　４　　　　　ｏ〜８Ｗ７　　１
　　　　　　　６　　　　　０〜３．５〜８．１゜合計
　　７　　　　　　２２ （＊）これは最大の重なり数に対応する。

従って、第２４図のブロック４２６の経路コスト伝搬に
関する第２６．２図のプロッタ５６２及び５３４の論理
機ａ目の実行にＳＰＥの計算時間が殆んど費やされるな
らば、５×５の機械は列の場合を接続するのに３倍以上
のペナルティ？こうむる。

（バラタイムＥ）　中心からの２次元掃引：第１０１図
の配線経路決定の微細トラック埋め込み工程２３６及び
物理設計の過程における他の多くの応用において２次元
掃引モードの計算が用いられる。第３４図はＳＰＥの観
点から見たこのバラタイムを説明している。　　　　　
−。

中心セルＳＰＥはそのタスクを計算し、計算結果？ブロ
ック６３４′＆び６３６に示すように４つの隣接ＳＰＥ
に送る。

チップの中心の行又は列に沿った他のセルを表わすＳ’
　Ｐ　Ｅ　（ブロック６４０のＹＥＳ分岐〕は中心方向
から数値？受は喉る（プロッタ６４２及び６４４）まで
待機し、受は取った数値に対して計算を行ない（ブロッ
ク６４６）、次にその結果をその外側の隣接ＳＰＥの３
３全部に送る。中央の行又は列に属さないセルを表わす
他のＳＰＥに、その内側の隣接ＳＰＥの両者７５＝デー
タを送って来るの全待ち（プロッタ６５２．６５４）、
受は取ったデータに対して計算を行ない（プロッタ６５
６）、その結果を外側の隣１ｉｓＰＥの両者に送る（ブ
ロック６５８）。

フル・サイズの機械では、処理活動（図の「計算する」
のプロッタ）に中心からダイヤモンド状の波動の形で伝
搬し５４つの隅に到達する。

フレーム比哉械では５第６５図及び第３６図に示すよう
に処理は外向きにやや不規則な形で進行する。第６５図
の左側は９×９のフル・サイズの機械を示し、第′５５
図の右側は６×３の機械？用いる時のチップのフレーム
構造を示す。

第５６図は各時間ユニットにおいて動作する５×６の機
械の５ＰＩＩＪ−示す。フル・サイズの機械は９時間ユ
ニットで処理を終え、６×５の機械に１５５時間ユニッ
ト処理全路える。この例から明らかなように、ノぐフオ
ーマンス時間ペナルティは、機械サイズが妥当であると
仮定すれば、チップ対機械のサイズの比よりもはるかに
小さい。

第３５図及び第３６図の例は、ある前もって定められた
規準によって作業ス５ツタの処理の順序がどのよりに影
響され得るか？説明している。この例の各ＳＰＥはチッ
プの中心により近いセルを最初に処理する。

典型的な配線経路決定システムに関して装置は効率的且
つ高速に機能する事？示して来た。速度の利点はより多
くの計算ができる余裕を生み、従って高品質の結果音生
じる。ここで例として示した機械は物理設計工程全体の
主要部についても非常に適している。よシ高度の並列ア
ルゴリズムの設計あるいは変型は、機械購造及び機械を
プログラムする原理が理解されれば、容易に行なう事が
できる。

産業上の利用可能性 本発明の目的は物理設計装置？提供する事であ本発明の
他の目的はＶＬＳＩ回路のための改良された配線経路決
定装置を提供する事である。

本発明の一態様によれば、ＶＬＳＩ回路のための改良さ
れた大局的配線装置が与えられる。

本発明の他の態様によれば、最適の配線経路を決定する
ために混雑評価７行なう改良された大局的配線装置が与
えられる。

本発明の他の態様によれば、能動回路領域の配列及びそ
れらの能動領域の間を直交して走る配線チャネル及び面
間接続のためのバイアより成るマスタ・クラ１ス・チッ
プから構成されたＶＬＳ　Ｉ回路のための改良された大
局的配線装置が与えられる。

本発明の他の態様によれば、チップ上の能動領域間のチ
ャネル配線経路を決定するために多ポート・プロセッサ
の配列と通信する主制御装＃を用いｉ、ＶＬＳＩマスタ
・クラ１ス・チップのための大局的配線装置が与えられ
る。

本発明の他の態様によれば、チップ上の能動領域の数が
配列よりもはるかに大きい場合に、多ポート・プロセッ
サの配列がチップ上の能動領域間の配線経路決定をでき
るような、フレーム・マツピング技術？用いたＶＬＳ　
Ｉマスタ・スライス・チップのための改良された大局的
配線装置が与えられる。

【図面の簡単な説明】

第１＠ばｎＸｎの論理装置の配列を有するマスタ・スラ
イス・チップの図、第２図は本発明による物理設計シス
テムのブロック図、第３１図及び第３２図は第２図の配
列Ｉ１０プロセッサ３４のブロック図、第４図は第６．
２図の駆動回路４４．６６、及び７８のブロック図、第
５図は第２図の特殊処理要素（ＳＰＥ）の図、第６１図
及び第６゜２図は第２図及び第５図に示したＳＰＥのブ
ロック図、第７図は第６．１図のｓＰＥ制両輪理１２４
の選択機構の図、第８図は２つのＳＰＥ間の通信に用い
られるメール・ボックス・フラグ機構のブロック図、第
９図は物理設計工程の流れ図、第１０図は第９図のブロ
ック２３０の詳細な流れ図、第１１図はマスタ・スライ
ス・チップの図、第１２図は第１１図のセル２４２の詳
細？示す図、第１３図は第１０図の大局的配線経路決定
工程の詳細な流れ１図、第１４図は第１６図の混雑評価
工程の詳細な流れ図、第１５図はセルＡ及びＢの２点全
接続する全ての最もらしい配線経路を示す図、第１６図
は混雑評価を行なうためのネット中のノードＸに関する
ルツクアヘソド・コストのテンプレート・パターンの図
、第１７図は５つの論理サービス端子（ＬＳＴ）’ｉ有
するネットに関する混雑評ｆｉｔｌｉｒ説明するテンプ
レート・パターンの図、第１８図は各セル境界における
水平方向の混雑評価の６次元的グラフの図、第１９図は
各セル境界における垂直方向の混雑評価の３次元的グラ
フの図、第２０図は第２０．１図、第２０．２図及び第
２０３図の関係を示す図、第２０，１図、第２ｏ、２図
及び第２０３図は第２図の制御装置２ｏ及び５ＰＥ３２
が特定の配＠経路に関して混雑評ｆｉｎ行な９方式を説
明する詳細な流れ図、第２１図は混雑評価の導出を理解
するのに役立つ図、第２２図は混雑評価におけるポート
・コストの理解に役立つ図、第２３図はボート・コスト
￥説明する３次元的グラフの図、第２４図は第１３図の
ブロック２６８の詳細な流れ図、第２５図は第２４図の
ブロック４２６に関する制御装置の動作を示す流れ図１
第２６図は第２６１図、第２６２図及び第２６５図の関
係を示す図、第２６．１図、第２６２図及び第２６３図
は第２４図のブロック４２６の詳細な流れ図、第２７図
は第２４図のブロック４２６に関する詳細な流れ図、第
２８１図乃至第７８８図は経路コストの伝搬、？説明す
る図、第２９１図及び第２９２図は第２４図のブロック
４５４０機能を実行するためのＳＰＥ動作の流れ図、第
５０図はチップとフレームとの関係を説明するマス！・
クラ１ス・チップの図、第３１図ｉフル・サイズの物理
設計装置における行掃引動作に関するパラダイムに関す
る流れ図、第３２．１図乃至第３２５図は連続したフレ
ームの行をパ１ブラ４ン方式で処理する方法を示す図、
第６６図は第２８１図乃至第２８８図の工程で５ＰＥＫ
対するセルの重なりがフレームｒＩｌ、機械においてど
のよつに生じるかｔ示す図、第３４図はＳＰＥの観点か
らパラダイムＥを説明する詳細な流れ図１第６５図及び
第３６図はフル・サイズの機械及びフレーム化機械に関
して作業スタックの処理？説明する図である。 出ａ　人　インタｉ九ン叶ル・ビジネス・マンーンズ・
コーポレーション代理人　弁理士　　岡　　　１）　　
次　　生（外１名） 左端セ１し　　　　　　　　　　中闇七し待機 右瑞セＪし 持機 ＦＩＧ、３２．１

Claims (1)

1. 【特許請求の範囲】 基板上に複数の装置が杉成烙れ、上記基板上に相互に直
   交する水平及び垂直の複数の配線チャネルが形成きれ、
   各チャネルに複数の配線トラックが形１１ｉ！され、上
   記装置及びチャネルがセルを形成し、上記水平及び垂直
   の配線チャネルの少なくとも１つに配線トラックに旧っ
   て端子が配置された基板上の上記端子間の配線径路を決
   定するための装置でろって、 配列体中の少なくとも４つの隣接する処理要素と通信す
   るための少なくとも４つの入力／出力ポート及び制御人
   力／出力ポート’ｃ有する複数の処理要素の配列体と、 １つのセルのソース端子から他のセルのシンク端子への
   配線径路？決定するために、上記配列体中の各処理要素
   の制御人力／出力ボートに選択的にコマンドを与えるた
   めの制御処理装置と、上記制御処理装置からのコマンド
   に応答して、最初に上記１つのセルのソース端子から上
   記他のセルのシンク端子への最良のチャネル径路を決定
   し、次に上記最良のチャネルにおいて最良の配線トラッ
   ク全決定する、上記処理要素中の手段とから成る 配線径路を決定するための装置。