JPH0540804A

JPH0540804A - 物理的回路の製造方法、論理設計の自動マツピング装置、論理アレイ及び回路のレイアウト方法

Info

Publication number: JPH0540804A
Application number: JP3325142A
Authority: JP
Inventors: Steven J Perry; スチーブン・ジエイ・ペリー
Original assignee: Xilinx Inc
Current assignee: Xilinx Inc
Priority date: 1990-11-13
Filing date: 1991-11-13
Publication date: 1993-02-19
Also published as: EP0486248A3; IT1249833B; ITTO910116A1; CA2054290A1; ITTO910116A0; EP0486248A2

Abstract

(57)【要約】（修正有）【目的】回路支持基板の表面領域に電子回路コンポー
ネント即ち構成要素をレイアウトするための方法に関す
る。【構成】論理設計は、例えば、第１ＡＮＤゲートＥ
１、第１０ＲゲートＥ２、３状態バッファＥ３、第２０
ＲゲートＥ４、第２ＡＮＤゲートＥ５、第３０Ｒゲート
Ｅ６、フリップフロップＥ７の入出力端子を互いに接続
し、他の論理素子、Ｅ１０などに接続するように複数の
配線Ｗ１，Ｗ２…を含む多数の原始機能素子を表す記号
表記からなる。又縦列の領域をＡ，Ｂ等で、横行のを
１，２等で示したマッピング用の座標が設けられてい
る。機能素子Ｅ１〜Ｅ７が、自己区分された領域Ａ１に
はめ込まれてい、他の組織、例えばＥ１００及びＥ１０
１は、Ｃ４の領域に不規則に分散されている。論理設計
は領域Ｃ４に示されるような機能素子を不規則に集める
ことから始まり、例えば領域Ａ１にまとめられたと考え
られるまで、物理的な意味とは逆の論理的な意味で、再
配置される。

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明は、回路支持基板の表面領
域に電子回路コンポーネント即ち構成要素をレイアウト
するための方法に関する。この回路コンポーネントは、
ブール論理関数または他の関数のような既定の即ち画定
された項レベルの関数の組を実行するように接続され
る。基板表面領域の各サブセクションが支持し得る原始
（primitive）関数の数について制限が設けられる。本
発明の方法は、各基板サブセクションに於て使用可能な
リソースを実行する関数をでき得る限り使用することを
目的としている。

【０００２】また、本発明はこのような方法による製品
に関する。

【０００３】本発明は、より詳細に言えば、現場でプロ
グラム可能なコンフィグラブル論理アレイ（ＦＰ−ＣＬ
Ａ）の回路を構成する際に使用されるレイアウト方法及
びそれによって製造される製品に関する。

【０００４】

【従来の技術】集積回路チップの製造は、該集積回路チ
ップに於て実行されるべき動作を定義する最初の機能記
述で始まる。この初期機能記述は、例えば２入力ゲート
レベルのような基礎的コンポーネントレベルで作成され
る回路図の形態をとる。コンピュータ援用設計システム
（ＣＡＤ）を用いる場合、前記機能記述は、原始的関数
及びそれらの配線の組を記述するコンピュータ読取り可
能な「ネットリスト」の形態をとることになる。初期機
能記述は、通常２入力ＡＮＤまたはＯＲ論理ゲート、イ
ンバータ、フリップフロップ、トリステート・ラインド
ライバ等のような多数の、即ち何百もの機能素子（プリ
ミティブ）の長いリストによって定義される。これらの
素子は、「インスタンス」とも称される。これらの素子
の入力及び出力端子は、リンケージ即ち「ネット」によ
って適当に接続されて、所望のより高いレベルの機能の
組を提供する。ここで言う「ネットリスト」は、各イン
スタンスの入力／出力端子（即ち「ピン」）とこれら端
子を接続するネットとの間の関係を定義するデータベー
スの意味で使用されることが多い。

【０００５】説明を簡単にするために、「論理設計」及
び「回路設計」の語は、本明細書に於て「機能記述」と
同じ意味で使用される。回路図は、図面自体または回路
図のコンピュータ表現（コンピュータ読取り可能なネッ
トリスト・ファイル）のいずれかによって定義されるよ
うに論理設計を表すために用いられる。論理設計は、物
理的チップの上に現れる回路コンポーネントの物理的配
置や配線を記述するものではない。それらはレイアウト
の過程に於て画定される。回路設計、回路レイアウト及
び物理的インプリメンテーションの最終製品を本明細書
では「物理的回路」と称する。

【０００６】レイアウト及びインプリメンテーション過
程の第１ステップでは、前記論理設計（ネットリスト）
が、それぞれに予め定義された最大数以下のプリミティ
ブ（例えば、２入力ブールロンリゲート）を有する設計
セクションに細分即ち「区分け」（partition）され
る。この第１ステップは、区分けされた各設計セクショ
ンが後で集積回路チップの対応する機能実行サブセクシ
ョンとの関連を有しかつそれによって実施され得るよう
に実行される。

【０００７】前記集積回路チップの各機能実行サブセク
ションは、それが適合し得る原始関数の数について予め
決められた上限を有する。インプリメンテーションを可
能にするために、各区分け設計セクションに於ける機能
素子（例えば、ブール論理ゲート）の数は、チップ基板
上の対応する機能実行サブセクションの上限値と等しい
かそれ以下にすべきである。

【０００８】区分けの後に、各設計セクションの機能を
実行する回路が直接にまたは等価関係をもって定義され
る。次に各設計セクションの回路（本明細書に於て、
「設計セクション回路」と称する）を形成しかつ前記チ
ップ基板の対応する機能実行サブセクションに固定す
る。最後に、各設計セクション回路の物理的な位置を固
定して、配線用の導体を前記設計セクション回路間に於
てルーティングして集積回路を完成する。上記各ステッ
プは当分野に於て一般に「区分け」、「配置」（placem
ent）、及び「ルーティング」と称されている。

【０００９】従来、前記区分け、配置及びルーティング
の設計ステップはレイアイト専門家と称される熟練した
技術者によって人手により実行されてきた。これらの専
門家は一般に大規模の半導体製造会社で働いており、長
年に亘って一連の露光「マスク」を用いて大量生産され
る集積回路チップのレイアウトを最適に決定する方法を
学んできた。専門家達は長年に亘って経験的に技術を開
発し、それによってチップ上に比較的高密度で回路及び
機能を実装することができ、各チップ上の制限された面
積を効率的に利用している。

【００１０】最近では、様々な種類のいわゆる「フィー
ルドプログラマブル論理デバイス」（ＰＬＤ）や「ユー
ザ・コンフィグラブル・論理アレイ」（ＣＬＡ）が導入
されている。このようなフィールドプログラマブル・デ
バイスによって、現場のユーザは現場で構成可能に回路
を形成するという柔軟性が得られる。しかし、このよう
なＰＬＤは同時に、チップレイアウトの負担を熟練した
企業内のレイアウト専門家から経験のない現場のユーザ
へと移している。現場のユーザは、一般に１個のＰＬＤ
チップの制限された資源を効率的に使用するようにＰＬ
ＤまたはＣＬＡに於てその回路を効率的にレイアウトす
るための方法を学ぶことに消極的であり、またはそのた
めに時間を費やすことができない。

【００１１】現場のユーザの負担を軽くするために、多
くのコンピュータ自動化区分け、配置及びルーティング
・システムが提案されている。大部分の自動化区分けシ
ステムの基礎は、ベル研究所に於て開発されたいわゆる
「ミニ−カット」（min-cut）アルゴリズムに基づいて
いる。これについては、ビー・ダブリュ・カーニガン
（B. W. Kernighan）及びエス・リン（S. Lin）による
「An Efficient Heuristic Procedure for Partitionin
g Graphs」、Bell System Technical Journal、Vol. 4
9、１９７０年２月、第２９１〜３０８頁を参照するこ
とができる。また、カーニガン及びリンの米国特許第
３，６１７，７１３号、「Method of Minimizing the I
nterconnection Cost of Linked Objects」、１９７１
年１１月２日発行を参照することができる。

【００１２】前記ミニカット・アルゴリズムの背後にあ
る考え方は、各設計セクション間を最小数の導線が通る
ように多数の電気素子を個別の設計セクションにまとめ
ることである。このミニカット・アルゴリズムは、それ
ぞれに略同数の原始電気素子を有する２つの部分に回路
設計を分割する第１の区分け線をもって始められる。こ
の第１の区分け線によって切断される接続線の数が数え
られる。次に、前記区分け線の左側にある任意に選択さ
れた素子と前記区分け線の右側にある対応する任意に選
択された素子とが、前記区分け線を挟んでそれらの配線
を維持したまま入れ替えられる。入替え後に前記区分け
線によって切断される線の数が数えられる。この新しい
数が先の数より少ない場合には、この交換した状態が維
持され、そうでない場合には別の入替えが行われる。こ
の入替え及びテスト過程は、ユーザによって定義される
ストップ条件が発生するまで何度も繰り返される。最終
的に、前記ミニカット・アルゴリズムは、最小数の配線
即ち線路を切断する区分け線を画定するためのものであ
る。次に、前記区分け線の両側に画定された２個の設計
セクションを個々に、各前記設計セクションの中に新し
い区分け線を引き、かつ前記各設計セクションに別個に
前記ミニカット・アルゴリズムを再適用することによっ
て配分する。この過程をストップ条件に適合するまで再
帰的に繰り返す。このようなミニカット・アルゴリズム
の再帰的適用によって、レイアウト専門家の人手による
作業と同様に自動的に回路設計を区分けできると考えら
れていた。しかしながら実際には逆の結果が証明され
た。

【００１３】前記ミニカット・アルゴリズムが導入され
てから、多くの改良例が報告されている。例えば、マー
ク・ハートゥーグ（Mark Hartoog）の「Analysis of Pl
acement Procedures for VLSI Standard Cell Layou
t」、23rd Design Automation Conference、IEEE、１９
８６年、第３１４〜３１９頁を参照することができる。
更に、米国南カリフォルニア大学メルビン・ブルーワー
（Melvin Breuer）の「AClass of Min-Cut Placement A
lgorithms」、16th Design Automation Conference、１
９７７年６月、第２８４〜２９０頁、ベル研究所ジリ・
ソーカップ（Jiri Soukup）の「Circuit Layout」、Pro
c. IEEE、 Vol. 69、１９８１年１０月第１２８１〜１
３０４頁、またはＩＢＭ社のエス・カークパトリック
（S. Kirkpatrick）他の「Optimization by Simulated
Annealing」、Science vol. 220、１９８３年５月１３
日、第６７１〜６８０頁を参照することができる。（ま
た参考資料として、トロント大学ロバート・ジェイ・フ
ランシス（Robert J. Francis）他の「Chortle: A Tec
hnology Mapping Program for Lookup Table-Based Fie
ld Programmable Gate Arrays」、27th ACM/IEEE Desig
n Automation Conference、１９９０年６月、第６１３
〜６１９頁がある。）

【００１４】

【発明が解決しようとする課題】従来使用可能な自動区
分けシステムは、レイアウト専門家の人手による作業と
同程度に機能を発揮することができない。配線の切断数
または区分けアルゴリズムによって形成される設計セク
ションは区分け方法の善し悪しを判断する１つの基準に
過ぎす、回路実装密度及び信号遅延特性等を考慮しなけ
ればならない。

【００１５】

【課題を解決するための手段】本発明によれば、或る所
定の回路設計を物理的に実施する際に回路実装密度を自
動的に最大にしかつ／または信号伝搬遅れを最小にする
ことを目的としたコンピュータ自動区分けシステムが提
供される。一般に前記回路設計はコンピュータ読取り可
能ネットリスト・ファイルであり、かつ所望の最終製品
（物理的インプリメンテーション）は集積回路チップ
（ＩＣ）である。本発明は、ユーザ・コンフィグラブル
（構成変更可能な）論理アレイ（ＦＰ−ＣＬＡ）に於て
回路を自動的にかつ効率的に画定するために使用するこ
とができる。

【００１６】本発明による方法は、回路設計を全体に亘
ってサーチし、その後に続く回路素子の組の２個以上の
入力端子を駆動する１個の出力端子をそれぞれに有する
各能動回路素子を「複製候補」としてタグ付けすること
で始まる。このような「マルチプル・ファンアウト」回
路素子に一旦タグが付加されると、各タグ付き回路素子
の複製が形成されて、元の回路設計の元のマルチプル・
ファンアウト素子の位置に挿入される。前記複製の対応
する入力端子が一体に結合される。前記複製の各出力端
子は一体に結合されないが、次に続く回路素子の組の対
応する１個の入力端子にそれぞれ結合される。

【００１７】複製後に、複製の結果として実装密度を増
加させかつ／または信号伝搬時間を短縮することができ
たかどうかを判断するためにテストが行われる。多くの
場合には、当初元のマルチプル・ファンアウト素子を有
することができなかった集積回路チップの機能実行サブ
セクション内に１個または複数の単一ファンアウト複製
論理素子を組み込むことができるので、実装密度が高く
なる。前記単一ファンアウト複製を各機能実行サブセク
ションに組み込むことによって、前記単一ファンアウト
複製とそれらが接続される他の回路素子との間の配線長
さが短くなる傾向がある。これによって信号遅延時間が
短縮される。どのようにして実装密度が増加しかつ／ま
たは信号伝搬時間が短縮されるかについて、以下に詳細
に説明する。

【００１８】

【実施例】第１図に関して説明すると、実施しようとす
る回路の機能技術（「論理設計」または「回路設計」）
と前記回路の実際のインプリメンテーション（物理的回
路、最終的なレイアウトを含む）との間で区別を付ける
べきである。図１は、サンプルの論理設計を描いた１枚
の紙１０を示している。前記論理設計は、例えば第１Ａ
ＮＤゲート（Ｅ1）、第１ＯＲゲート（Ｅ2）、３状態バ
ッファ（Ｅ3）、第２ＯＲゲート（Ｅ4）、第２ＡＮＤゲ
ート（Ｅ5）、第３ＯＲゲート（Ｅ6）、フリップフロッ
プ（Ｅ7）及びこれらの論理素子（Ｅ1〜Ｅ7）の入出力
端子を互いに接続すると共に、同じく図面１０の上に描
かれた他の論理素子、例えばＥ10及びＥ11の端子に接続
するようにあらゆる方向に延長する長いまたは短い複数
の配線（Ｗ1、Ｗ2、Ｗ3、・・・）を含む多数の原始機能素
子を表す記号表記からなる。図示された回路素子（Ｅ1
〜Ｅ7）の大部分は、それぞれが唯１個の信号出力端子
（１ビット出力）と３個または４個以下の信号入力端子
とを有することから、「ブール論理プリミティブ」と定
義することができる。

【００１９】図面１０には、理解を容易にするために、
縦列の領域を欧文字Ａ、Ｂ、Ｃ等によって示しかつ直交
する横行の領域を数字１、２、３等によって示すように
したマッピング用の座標が設けられている。機能素子Ｅ
1〜Ｅ7が、設計図面１０の自己区分けされた左上部の領
域Ａ１の中にはめ込まれていることが分かる。他の組
織、例えばＥ100及びＥ101は、図示されるように設計図
面１０のＣ４のような右下の領域に亘って不規則に分散
されていることが分かる。設計図面１０の自己区分け領
域Ａ１〜Ａ４、Ｂ１、Ｂ２、Ｃ１、Ｃ２が不規則である
ことが理解される。大抵の設計図面は、領域Ｃ４によっ
て明確に表されるような不規則に分散されかつ接続され
るように認められる所謂「ネズミの巣」または「スパゲ
ッティのボール」のように配置された論理記号を有す
る。領域Ａ１〜Ｃ２には、図面１０に描かれた各素子が
どのように再構成され、かつ後述する図２の集積回路チ
ップの機能実行サブセクションと関連させることができ
るかを最初に容易に理解できるようにすることのみを目
的として概念的に理解される程度に図示されている。

【００２０】通例、論理設計は例えば領域Ｃ４に示され
るような機能素子を不規則に集めることから始まる。こ
れらの機能素子は、その機能が物理的な最終製品の機能
実行サブセクションによって実行され得るような合理的
な大きさのグループ、例えば領域Ａ１、Ａ２にまとめら
れたと考えられるまで、レイアウト過程に於て、物理的
な意味とは逆の論理的な意味で全ての配線をそのままに
した状態で、再配置される。

【００２１】前記レイアウト過程では、２つの問題を同
時に考慮する必要がある。第１の問題は、論理設計の条
件に適合する電気回路をどのようにして直接的にまたは
等価関係をもって定義するかということである。第２の
問題は、この回路をどのようにして機能実行最終製品の
物理的制限の範囲内に維持するかということである。特
定種類の機能支持基板が最初に記述され、次にサンプル
区分けの問題が提示される。

【００２２】図２には、その表面に一応に画定されたユ
ーザ・プログラマブル論理実行サブ領域ＬＡ11、ＬＡ1
2、ＬＡ13、・・・ＬＡ1N、ＬＡ21、・・・ＬＡ2N、・・・ＬＡMN
の規則正しいアレイ即ち配列を有するモノリシック半導
体基板（チップ）２０が平面図示されている。このチッ
プ２０をコンフィグラブル論理アレイ（ＣＬＡ）と称す
る。ＣＬＡチップ２０の前記論理実行サブ領域ＬＡ11〜
ＬＡMNは、一般に「論理領域」ＬＡxy（ここで、x及びy
は識別するための整数即ち座標である）で表される。

【００２３】最初、論理領域ＬＡxyの内部回路は画定さ
れていない（構成されていない）が、レイアウト及びコ
ンフィグレーションが完了した後に、このコンフィグラ
ブル論理アレイ（ＣＬＡ）チップ２０は、図１の設計図
面１０の回路図の記号のようなユーザが提供する機能記
述によって記述される論理機能を実行するようにその上
に画定される物理的回路を有することになる。

【００２４】ＣＬＡチップ２０は、前記論理領域を接続
するためにその表面に配置されたマトリックス状の物理
的に短い水平線２１と物理的に短い垂直線２２とを有す
る。図２には、図面が乱雑になるのを避けるために、こ
れらの線の１部分のみが図示されている。短い垂直線及
び水平線２１、２２の端部（その水平及び垂直端部の関
係がＬＡPNとＬＡMNとの間の領域により詳細に図示され
ている）は、前記論理領域の入力端子及び出力端子を次
から次へと連続的に接続するために、互いに隣接する論
理領域に連結することができる。図示されないプログラ
マブル配線接続点を用いて、形状及び長さが異なるより
長い線を形成するために、水平線及び垂直線２１、２２
の東西南北の各端部を様々に連結する（例えば垂直線の
北側端部を水平線の東側端部に接続する）ことができ
る。

【００２５】大きく離隔された論理領域を次から次へと
より直接的な手法で接続する、例えばＬＡ11をＬＡP2に
接続するために概ねチップ２０全体に亘って延長する物
理的に長い水平線２３及び物理的に長い垂直線２４（グ
ローバル線）が設けられている。チップ２０は更に、該
チップの周辺に設けられた入出力ピン２５に論理実行領
域ＬＡ11〜ＬＡMNの各入力及び出力端子を結合するため
の入出力ブロック（ＩＯＢ、図示せず）を有する。

【００２６】図３には、論理領域ＬＡ11、ＬＡ32を有す
る１個の基板セクション２００が拡大図示されている。
各論理領域ＬＡxyは、唯４個の入力端子Ｉxy.1、Ｉxy.
2、Ｉxy.3、Ｉxy.4と単一の出力端子Ｏxyとを有する関
数発生回路ｆxyを有する。３状態制御端子ＴＸxyを用い
て任意に出力端子Ｏxyを高インピーダンス状態に置くこ
とができる。（ここで、添字ｘｙは関数発生器ｆ11〜ｆ
32を識別する整数即ち座標である）

【００２７】説明を簡単にするために、図３の各論理支
持領域ＬＡxyが、唯１個の出力ビットと４個以下の入力
ビットとを有するあらゆる組合せ論理関数を実行できる
ように構成（プログラム）できるものと考える。このよ
うに能力を制限したコンフィグラブル関数発生器ｆxyの
一例が、唯４個のアドレスの入力端子（Ｉxy.1〜Ｉxy.
4）、１６個のメモリセル（２⁴ビット）及び唯１個のデ
ータ出力線（Ｏxy）を有するルックアップ・テーブル・
メモリユニットである。

【００２８】前記論理領域の外側に延長する領域間接続
線Ｗ11、Ｗ12等を用いて、各関数発生器ｆxyの４個の前
記入力端子、前記３状態制御端子または単一の前記出力
端子のいずれかまたはそれらの幾つかを隣接するスイッ
チマトリックス領域ＳＷＡxyに結合することができる。
各スイッチマトリックス領域ＳＷＡxyは、第１の関数発
生器ｆxyの前記入出力端子と他の前記関数発生器ｆx'y'
の前記信号入力端子または出力端子に向かう他の領域間
接続線との間で信号を伝送するようにプログラムするこ
とができる。

【００２９】前記領域間接続線（Ｗ11、Ｗ12等）と前記
スイッチマトリックス領域ＳＷＡ11、ＳＷＡ21、等）に
ついて信号伝送経路を形成することの問題は、一点を除
いて詳細な説明を省略する。それは、第１の論理支持領
域、例えばＬＡ11から第２の論理支持領域、例えばＬＡ
12及び／または接続された前記スイッチマトリックス
（ＳＷＡ11、ＳＷＡ21等）へと延出する比較的長い前記
領域間接続線（Ｗ11、Ｗ12等）のそれぞれに帰する有限
信号伝搬時間が存在することである。

【００３０】一般に、信号伝搬時間が過度に長くならな
いように、信号を物理的（最終製品の）回路に於て伝送
する場合にこのような領域間（領域外）の線の長さ及び
／または数を最小にすることが望ましい。有限であるが
比較的短い信号伝搬時間は、完全に各論理支持領域（例
えば、ＬＡ12内）に設けられる比較的短い領域内（前記
論理領域内）接続（図３には図示せず）に帰因する。一
般に、できる限り長い領域間接続線（Ｗ11、Ｗ12等）よ
りもむしろ図示されない短い前記領域内ワイヤ接続線を
用いることによって信号を伝送することが望ましい。

【００３１】更に、各論理支持領域ＬＡxyの関数発生器
ｆxyがテーブル・ルックアップ・メモリを有する場合に
は、その関数発生器ｆxy内に個々のメモリセルをアドレ
スするために付加される有限時間遅れが存在する。第２
領域（ＬＡ12）の出力端子（Ｏ12）に応答を発生させる
べく第１論理領域（ＬＡ11）の前記出力端子（例えば、
Ｏ11）から第２論理領域（ＬＡ12）の前記入力端子（Ｉ
12.2）へと該第２論理（ＬＡ12）の関数発生器（ｆ12）
を介して送られる際に信号に付加される遅れを、本明細
書では「領域間」遅れと称する。一連の論理領域（ＬＡ
11、ＬＡ12、ＬＡ13等）についてブール・ツリー論理を
実行する場合には、前記ブール・ツリーを伝搬する論理
信号について領域間遅れの合計が最小になるように論理
領域の数及び／またはそれらの間の距離を最小にするこ
とが一般的に好ましい。

【００３２】物理的なインプリメンテーション（図２及
び図３のチップ２９）に関連する幾つかの制約が理解さ
れた所で、サンプル（第１レベル）の区分に関する問題
を提示する。

【００３３】図４には、論理関数が回路図上でどのよう
に再構成されかつ最終的に区分け及び配置によってユー
ザ・コンフィグラブルチップ（図２）の固定された前記
支持領域内にマッピングされるかと言うことを説明する
ために、回路設計のサンプルセクションミ３００が示さ
れている。

【００３４】図示されるように、設計セクション３００
は、複数の電気素子Ｅ1、Ｅ2、Ｅ3、・・・Ｅ8を有する。
ここで、各素子ＥZは、１個の出力ノードＮz0と１個ま
たは２個以上の入力ノードＮz1、Ｎz2、Ｎz3等（ここで
Ｚは整数１、２、３、・・・を表わす）を有する。個々の
回路素子Ｅzが有する特異な入力ノードＮz1、Ｎz2、Ｎz
3等の数は、前記素子の「ファンイン」として定義され
る。その素子Ｅzの出力ノードＮz0によって駆動される
後の入力ノードの数が、該素子Ｅzの「ファンアウト」
として定義される。即ち、図示されるＡＮＤゲートＥ1
はファンインが２でファンアウトが１であり、ＯＲゲー
トＥ4はファンインが２でファンアウトが２であり、か
つＡＮＤゲートＥ8はファンインが３であるが、その後
に続く論理素子が図示されていないのでファンアウトは
不明である。

【００３５】図４の破線のブロックＰＡ1〜ＰＡ8が各素
子Ｅ1〜Ｅ8について未だ描かれていないと仮定する。こ
こに於ける問題は、各論理支持領域ＬＡxyが４本の入力
線（Ｉxy．１〜Ｉxy．４）または１本以上の３状態制御
線（ＴＸxy）を受け入れることができず、かつそれから
出る出力線（Ｏxy）が１本だけであるという制限下で、
この図２のＣＬＡチップ２０に於ける設計セクション３
００をどのように実行すべきかということである。（図
３参照）論理領域ＬＡxyに入る入力線の数に関する上限
及び同じ論理領域前記ＬＡxyから出る出力線の数を論理
領域ＬＡxyの境界ルールＢＲxyと言う。当面は、各論理
領域に関する境界ルールＢＲxyが同じである、即ち入力
線（３状態制御線を含む）が４本以下で出力線が１本の
みであると仮定する。

【００３６】簡単な方法は、各原始素子Ｅz（即ち、２
入力／１出力ＡＮＤゲートまたはＯＲゲート）を図４に
示されるような対応する区分けブロックＰＡzで囲むこ
とである。これによって自動的に、各ブロックＰＡzを
通る入力線及び出力線の数が境界ルールＢＲxyを満足す
ることが保証される。（ここで、ｘ、ｙ、ｚは整数であ
る。）各区分けブロックＰＡz内に含まれる領域を、本
明細書に於ては区分け領域と称してＰＡzを付すること
にする。

【００３７】この図４の極端に単純化された区分けが一
旦境界ルールＢＲxyを満足するように行なわれると、区
分け領域ＰＡzの個別の等価回路が図２のチップ２０の
単一論理支持領域ＬＡxyの対応する関数発生器ｆxy内に
構成され、領域間接続線が形成されて、前記物理的回路
が実現する。

【００３８】しかし、この図４の単純な方法は非能率的
である。これは、最終製品２０に於て使用される論理支
持領域ＬＡ11、ＬＡ12、ＬＡ13等の数が最大になる。チ
ップの実装密度は最小になる不都合があり、このために
各機能素子Ｅ1、Ｅ2、Ｅ3等間に於て使用される領域間
接続線（Ｗ11、Ｗ12等）の長さ及び／または数が最大に
なり、信号伝搬時間が最大になるという不都合が生じ
る。チップ２０に於て使用可能な領域間接続線の数が少
なくかつそのために非常に制限されている場合には、こ
のような素子Ｅ1〜Ｅ8を互いに接続するための線を多く
用いることによって、接続線のルーティング過程に於て
他の接続を形成することができなくなる場合がある。ま
た、各関数発生器がメモリセル・アドレス手段を有する
ような場合には、信号がこのような一連のメモリアドレ
ス手段を通って伝搬しなければならないので、信号伝搬
遅れが更に大きくなる（領域間遅れの合計が各直列回路
に沿って最大になる）。

【００３９】図５に於て、同じ設計セクショク３００を
区分けするための第２の方法が符号３１５を付して示さ
れている。第１ＯＲゲートＥ2の出力ノードＮ20が区分
け領域ＰＡ12に関連する第１関数発生器ｆ11の単一の出
力端子となり得るのに対して、この関数発生器ｆ11の使
用可能な４個の入力端子Ｉ11.1〜Ｉ11.3の中の３個が入
力ノードＮ11、Ｎ12、Ｎ22によって画定されていること
が分かる。関数発生器ｆ11の４番目の入力端子Ｉ11.4は
接地されており、従って使用されていない。第２のＯＲ
ゲートＥ4は、その出力端子Ｎ40が区分け領域ＰＡ12に
よって既に支持されている出力ノードＮ20と別個である
ことから、区分け領域Ｐ12には関与することができな
い。従って第２ＯＲゲートＥ4の周囲には、別個の区分
けブロックＰＡ4を描かなければならない。

【００４０】第２ＯＲゲートＥ4が区分け領域ＰＡ12内
に含まれていた場合には、その区分け領域ＰＡ12はそれ
から延長する２個の別個の出力端子を有することにな
り、境界ルールＢＲxy＝｛入力≦４、出力＝１｝に違反
することになる。区分けブロックＰＡ56が、３本のブロ
ック入力線と１本のブロック出力線とを画定するように
素子Ｅ5及びＥ6を囲むことによって、前記境界ルールを
満足している。第２ＯＲゲートＥ4のノードＮ40がファ
ンアウトして信号を次に続く複数の入力ノード（次に続
くＯＲゲートＥ2及びＥ6のノードＮ22及びＮ61）に供給
することが注目される。

【００４１】再び図３に関して、図５の区分け領域ＰＡ
12の回路が関数発生器ｆ11によって実行され、区分け領
域ＰＡ4の回路が関数発生器ｆ12によって実行され、か
つ区分け領域ＰＡ56の回路が関数発生器ｆ22によって実
行されると仮定する。ここでは各素子Ｅ3、Ｅ8及びＥ7
の機能を実行するための回路については考慮しない。

【００４２】図５の方法にも依然として或る程度の非能
率性が存在する。４入力関数発生器ｆ12の区分け領域Ｐ
Ａ4に入力ＯＲゲートを実行することによって、該関数
発生器ｆ12の論理実行リソースの半分を無駄にしてい
る。入力ノードＮ41（Ｉ12.1であると仮定）からゲート
Ｅ4（関数発生器ｆ12）を介して領域間接続線Ｗ22を通
って入力ノードＮ22（これを関数発生器ｆ11のＩ11.3と
仮定）へ送られる信号は、関数発生器ｆ12の入力遅れだ
けでなく、出力端子Ｏ12からスイッチマトリックスＳＷ
Ａ11を介して入力端子Ｉ11.3に伝送されることに関連す
る領域間遅れ及び関数発生器ｆ11の入力遅れを被むるこ
とになる。ノードＮ42から領域間接続線Ｗ61を通ってノ
ードＮ60に伝搬する信号は、同様の遅れを受けることに
なる。

【００４３】図６には、本発明による先区分け（pre-pa
rtitioning）ステップが概念的に図示されている。素子
Ｅ4は、そのファンアウト数が１より大きくかつファン
イン数が４より小さいことから、「複製候補」として識
別される。このように識別された素子Ｅ4は、２個の複
製素子Ｅ14及びＥ24によって置き換えられる。前記複製
の対応する入力ノードＮ141及びＮ241が、領域外（領域
間）接続線Ｗ41によって結合され、かつ更に対応するノ
ードＮ142及びＮ242が領域外（領域間）接続線Ｗ42によ
って結合されている。前記複製の対応する出力ノードＮ
140及びＮ240は互いに結合されていないが、各出力ノー
ドは別個に領域内接続線Ｗ140またはＷ240によって、元
のＯＲ素子Ｅ4の出力濃Ｎ40によって先に駆動されてい
た次の入力ノードＮ22及びＮ61の一方に接続されてい
る。このような複製過程の結果、前記境界ルールを違反
することなく素子Ｅ1、Ｅ2及びＥ14を囲む第１の区分け
ブロックＰＡ124を引くことが可能になる。更に、前記
境界ルールを違反することなく素子Ｅ24、Ｅ5及びＥ6を
囲む第２の区分けブロックＰＡ456を引くことが可能に
なる。

【００４４】次に、図６の区分けされた論理設計を図５
の区分けされた論理設計に対して比較して、図６の方法
が有利かどうかを確認する。図５の論理設計は、各素子
Ｅ1、Ｅ2、Ｅ4、Ｅ5及びＥ6の機能を実行するために３
個の論理支持領域ＬＡ11、ＬＡ12、ＬＡ22を必要とした
が、図６の論理設計４００は同じ機能を実行するために
唯２個の論理支持領域しか必要としない。注目すべきこ
とは、各素子Ｅ1、Ｅ2、Ｅ4、Ｅ5及びＥ6の機能を実行
するために必要な論理支持領域ＬＡxyの数が、論理素子
の数を増大させる（素子Ｅ4を複製する）ことによって
３分の１に減ったことである。

【００４５】ここでは、ノードＮ140とＮ22との接続
が、図５の領域外（領域間）接続Ｗ22によってではなく
領域内の導体Ｗ140によって形成される。ノードＮ240と
Ｎ61との接続が同様にして図５の接続線Ｗ61の代わりに
接続線Ｗ240によって行なわれる。図５のように２個ま
たは３個だけでなく、各関数発生器ｆ11及びｆ12の全て
の４入力端子Ｉ11.1〜Ｉ11.4及びＩ12.1〜Ｉ12.4が使用
される。ノードＮ141とＮ20との間またはノードＮ242と
Ｎ60との間には領域間の遅れが存在しない。

【００４６】前記素子複製ステップは、ファンインが２
の素子に限定されるものではない。前記境界ルールのフ
ァンインの限界（本実施例では、Ｉxy．１〜Ｉxy．４に
対応して４に設定されている）と等しいかそれ以下のフ
ァンインの値を有する素子を複製することができ、かつ
テストしてそのような複製によって遅延及び／または区
分けブロックＰＡzの数が減少したかどうか及びそれに
よって最終的に使用される論理支持領域ＬＡxyの数が減
少したかどうかを確認することができる。

【００４７】素子の複製が逆効果になり得る位置が存在
する。複製候補が比較的高いファンイン値（即ち、４入
力端子）または比較的高いファンアウト値（即ち、後に
続く億以上の入力ノードを駆動する）を有する場合に
は、素子の複製によって単に必要な関数発生器の数が多
くなり、または実質的により多くなかつ従って好ましく
ない数の新たな領域間接続線を前記論理設計に導入する
場合がある。即ち、前記素子複製過程は或る制限内で行
なわれるべきである。

【００４８】図７には、最適の複製範囲を識別しかつ該
最適識別範囲に従って区分けされた論理設計を作成する
ために本発明によるコンピュータ自動レイアウトシステ
ム内で使用される自動化プロセス５００のフロー図が示
されている。この自動化プセスは、コンピュータ援用設
計（ＣＡＤ）に使用されるあらゆるコンピュータハード
ウエアを用いて実行することができる。米国カリフォル
ニア州マウンテンビュウに所在するサン・マイクロシス
テムズ（Sun Microsystems）から市販されているSun-4
・ワークステーションがその一例である。

【００４９】自動化プロセス５００はステップ５０１で
始まる。初期化ステップ５１０では、初期複製範囲が、
ｆｏL及びｆｏHをそれぞれファンアウト値の下限値及び
上限値としかつｆｉHをファンイン数の最大値とした場
合に、ｆｏL≦ファンアウト≦ｆｏH及びファンイン≦ｆ
ｉHの制限を有するように設定される。図３の境界ルー
ル（ＢＲxy＝入力４以下／出力１）の場合、初期範囲と
してｆｏL＝２、ｆｏH＝３及びｆｉH＝２として始める
ことができる。

【００５０】初期化ステップ５１０は更に、先の最適選
択カウントを無限（または例えばＦＦＦＦhexのような
等価の大きな数）に設定しかつプロセス５００に既定の
ループ限度を設定するようなハウスキーピング・サブス
テップを含んでいる。

【００５１】次のステップ５１５では、前記論理設計を
サーチして前記複製範囲内にあるファンイン値及びファ
ンアウト値を有する素子を求め、これらの素子に複製候
補のタグを付加する。次にステップ５２０に於て、図６
のプロセスに従って前記複製候補を複製する。ステップ
５２５に於て、複製された前記素子を有する前記論理設
計を予備選択（pre-selected）区分けアルゴリズムを用
いて区分けする。この区分けアルゴリズムは、前記論理
領域のリソースを無駄にしないようにしつつ、各区分け
ブロックＰＡzが既定の境界ルール（即ち、各機能実行
領域ＬＡxyについて入力端子がＪ以下で出力端子がＫ以
下である）を満足するように、１個または複数の素子Ｅ
1、Ｅ2等からなるグループの周囲に区分けブロックＰＡ
zを画定する。

【００５２】ステップ５３０に於て区分けステップ５２
５によって生じた区分けセクションの数を数える（セク
ション・カウント）。或る特定の実施例では、ステップ
５３０のセクション・カウントが、区分けステップ５２
５によって消費されるべき関数発生器ｆxy（図３）の数
を表わす。以下により詳細に説明する本発明の別の実施
例では、ステップ５３０のセクション・カウントが、各
論理領域（例えば、図１１のＣＬＢ６００）が２個以上
の関数発生器（例えば、図１２のｆF、ｆG及びｆH）を
有するような場合にステップ５２５の結果として消費さ
れるべき論理領域ＬＡxyの数の推定値を表わす。後者の
場合には、前記推定値はステップ５２５によって消費さ
れた関数発生器の数から得られる。

【００５３】現在のセクション・カウントが前最適セク
ション・カウントより小さいかどうかを決定するために
比較がなされる。そうである場合には、前記プロセスは
ステップ５５０に進み現在のカウントが新しい前最適セ
クション・カウントとなり、かつ区分けステップ５２５
で最後に作成された区分けに暫定最適区分けが得られた
というタグが付される。

【００５４】次に、プロセス５００はステップ５４０ま
たはステップ５５０のいずれかからステップ５６０に進
み、複製範囲を変更して何か別の複製範囲によって前記
前最適セクション・カウントより良好なカウントが得れ
るかどうかを確認する。例えば、複製範囲の制限ｆｏ
H、ｆｉHの一方または両方をステップ５６０に於て１だ
け大きくすることができる。

【００５５】プロセス５００は、ステップ５６０からル
ープバックして（５７０）ステップ５１５に戻る。ステ
ップ５１５からステップ５６０までの各ステップが複数
回繰り返される。プロセス５００の外側ループ５７０
は、最小数の区分けセクションを発生させる最適複製範
囲、従ってチップのレイアウト・コンフィグレーション
過程の最終段階に於て、最小数の機能実行領域（例え
は、ＬＡ11、ＬＡ12、ＬＡ13等）を用いた前記論理設計
の物理的インプリメンテーションに落ち着くように設計
される。ユーザによって定義されるループ限界がステッ
プ５６０でテストされて、越えている場合にはプロセス
５００を終了する。この暫定最適区分け方法は、チップ
のレイアウト過程に使用される方法である。

【００５６】図８には、信号のクリティカル・パスに於
ける信号伝搬時間を最小にする（またはそのような時間
を許容限度内に維持する）ためのプロセス５８０がフロ
ー図を用いて示されている。前記複製範囲はステップ５
９６に於て調整されて、ユーザが画定するクリティカル
・パスに於ける信号伝搬時間を最小にする、または少な
くともユーザが画定する最大レベル以下に信号伝搬時間
を維持する論理設計区分けを作成する。図８の各ステッ
プ５８１、５８２、５８４、５８６、５８８、５９４、
５９６及び５９８は、図７の同様の位置に配置された各
ステップに対応する。

【００５７】ステップ５９０はステップ５８８によって
マッピングされる関数発生器間に所定の領域間遅れを仮
定し、かつこれらの遅延をピラミッド状回路のユーザが
画定したブランチ即ち分枝に沿って加算していく。その
合計値が、予め決められたタイミングの制限を満足する
区分け方法を見出すために、先の最適合計値の組及び／
またはユーザが決めた最大値と比較される。クリティカ
ル・パスに於ける信号伝搬時間を最小にしまたは予め決
められた最大レベル以下に維持すると言う要求に対して
最小数の区分けセクションに対する要望をバランスさせ
る論理設計区分けを行なうために、プロセス５００とプ
ロセス５８０とを組み合せることが考えられる。

【００５８】図７に示されるプロセスの特定の実施例に
ついて特定の物理的なインプリメンテーション（後述す
る図１１〜図１３のＣＬＡチップ）に適応する場合を詳
細に説明する。

【００５９】幾つかの用語を予め定義することが必要で
ある。図９に関して、「インスタンス」の語は以下に於
てブール論理ツリーに於ける各ブール・プリミティブ
（例えば、ゲートＩ1、Ｉ2、Ｉ3）を表わすために用い
られる。「ピン」の語は、各インスタンスの入力及び出
力端子（例えば、インスタンスＩ1に属するピンＰ10、
Ｐ11、Ｐ12）を表わす。「ネット」の語は、２個または
それ以上のピンを接続する導電リンク（例えば、ピンＰ
10、Ｐ22、Ｐ31を接続するネットＮｔ1）を意味する。

【００６０】図１０のＡ図に関して、「ネット・レコー
ド」は、コンピュータ読取り可能なメモリデバイス（図
示せず）に於て画定されるデジタルデータ構造（Ｎｔ−
Ｒｅｃｏｒｄ）である。前記ネット・レコードは、対応
するネット（例えば、図９のＮｔ1）に属する２個また
はそれ以上のピン（例えば、Ｐ10、Ｐ22、Ｐ31）を識別
する２つまたはそれ以上のピン識別データ部分からな
る。図１０のＡ図に示す前記ネット・レコードは多くの
場合に、１個または２個以上の名前（例えば、「Ｎｔ
1」）によってネットを識別するために使用される１個
または２個以上のネット名データ部分を有する。前記ネ
ット・レコードは、任意により前記ネットが長いまたは
短い金属線によって実行される必要があるかどうか、そ
れが接地線であるかどうか等の前記ネットの特定の「属
性」を画定するデータ部分を更に有する場合がある。こ
のようなネット・レコードの集合を「ネット・テーブ
ル」（図示せず）と定義する。

【００６１】図１０のＢ図に関して、「インスタンス・
レコード」は、対応するインスタンスに属する２個また
はそれ以上のピン（例えば、Ｐ10、Ｐ11、Ｐ12）を識別
する２個またはそれ以上のピン識別データ部分を構成す
るようにコンピュータ読取り可能メモリデバイス内に定
義されるデータ構造（Ｉ−Ｒｅｃｏｒｄ）である。この
インスタンス・レコードは多くの場合に、対応するイン
スタンス（例えば、「Ｉ1または「ＡＮＤ1」）及び別の
属性データを識別するために使用される１つまたは２つ
以上のインスタンス名データ部分を含んでいる。このイ
ンスタンス・レコードの集合が「インスタンス・テーブ
ル」（図示せず）と定義される。

【００６２】図１０のＣ図に関して、「ピン・レコー
ド」は、特異なピン（例えば、Ｐ31）を識別するため
に、及びそのピンを対応するインスタンス（例えば、Ｉ
3）及び対応するネット（例えば、Ｎｔ1）に関連させる
ためにコンピュータ読取り可能なメモリデバイス内に定
義されるデータ構造（Ｐ−Ｒｅｃｏｒｄ）である。通
常、前記ピン・レコードは、例えばピンの機能を入力、
出力、双方向性のいずれでも良いものとして識別する追
加の属性データを含んでいる。ピン・レコードの集合が
「ピン・テーブル」と定義される。

【００６３】「ネットリスト」は、コンピュータ読取り
可能メモリデバイス（例えば、磁気ディスク、テープ、
ＲＡＭ、ＲＯＭ等）に於て次の情報を含むように定義さ
れるデータベース構造体である。即ち、（Ａ）「ネット
・テーブル」として知られるネット・レコードの表、及
び（Ｂ）「インスタンス・テーブル」として知られるイ
ンスタンス・レコードの表である。

【００６４】ネット・テーブル（Ａ）に於ける各ネット
・レコードは、次のような情報を定義する。即ち、（Ａ．１）前記ネットに割当てられた０個または１個以
上の名前（例えば、Ｎｔ1）、（Ａ．２）前記ネット・
テーブルに於ける前記ネット・レコードの位置を表わす
インデックス番号（例えば、０、１、２、３・・・）、
（Ａ．３）「ネットピン・テーブル」として知られる、
前記ネットに接続されたピンのリスト、及び（Ａ．４）
前記ネットの属性を記述するブール・フラッグの組であ
る。これらに属性には、前記ネットが物理的回路に於て
物理的接続線として明確に表現されなければならない
か、またはそれが駆動するインスタンスが、前記ネット
が明確に表現されないように機能実行等価物（例えば、
関数発生器）内に吸収されるかどうかということ、及び
前記ネットが前記ＧＮＤまたはＶＣＣネットを表わすか
どうか等が含まれる。

【００６５】前記インスタンス・テーブル（Ｂ）に於け
る各インスタンス・レコードによって以下の情報が提示
される。（Ｂ．１）前記ネットリストに於て或るインスタンスを
他の全てのインスタンスから明確に区別する少なくとも
１つの名前、（Ｂ．２）前記インスタンス・テーブルに
於けるインスタンス・レコードの位置を表わす数、
（Ｂ．３）例えばＡＮＤ、ＯＲまたはフリップフロップ
の動作を実行するかどうか等のような前記インスタンス
の機能を記述するインスタンスの種類の番号、（Ｂ．
４）「インスタンス−ピン・テーブル」として知られ
る、前記インスタンスに接続されたピンのリスト、
（Ｂ．５）前記インスタンスの属性を記述するルール・
フラッグの組である。前記属性フラッグ（Ｂ．５）に
は、本発明に従って前記インスタンスが複製可能である
かどうかを決定するために使用される複製候補認定フラ
ッグが含まれる。このフラッグがＴＲＵＥ（ブール１）
に設定された場合には、前記インスタンスを複製するこ
とができる。前記フラッグがＦＡＬＳＥ（ブール０）に
設定される場合には、コンピュータシステムは前記イン
スタンスを複製しないようにされる。

【００６６】前記ネットピン及びインスタンスピン・テ
ーブルによって参照される各ピンは、以下の情報によっ
て表わされ、かつ（Ａ）ネット・テーブル及び（Ｂ）イ
ンスタンス・テーブルを記憶する前記メモリデバイスに
記憶される。（Ｃ．１）前記インスタンスに属する或るピンを他の全
てのピンから明確に区別する少なくとも１つの名前、
（Ｃ．２）ピンがどのインスタンスに属するかを示すイ
ンスタンスの番号、（Ｃ．３）ピンがどのネットに属す
るかを示すネットの番号、（Ｃ．４）ピンが入力ピン、
出力ピン、または双方向ピンであるかどうかを示す方向
値である。

【００６７】「ブール・ゲート・ツリー」は、コンピュ
ータ読取り可能メモリデバイスに於て画定されかつ１個
または２個以上の信号入力端子及び／または１個または
２個以上の接続されたインスタンスによって構成される
デジタル論理構造である。この論理構造の各要素を本明
細書では「ツリー・ノード」と称する。「ファンアウト
−フリー」ブール・ゲート・ツリーは、１個の「根」の
ノードと該根のノードから出ている０個または１個以上
の「子孫」のノードとを有する論理構造として定義され
る。前記ツリーの各ノードは、コンピュータ読取り可能
メモリデバイスに記憶されているデータの次のデータの
集合によって記述される。

【００６８】（Ｄ．１）存在するならば、現在のツリー
・ノードの親のノードを示す識別子。前記ツリーの前記
値のノードは親のノードを持たない。（Ｄ．２）ノードの子として知られる次に続くノードの
表。ツリー・ノードが子を持たない場合には、「リーフ
・ノード」として知られる。（Ｄ．３）現在のノードによって表されるネットリスト
のインスタンスの名前、または前記現在のノードが前記
ツリーに外部入力信号を供給する「実入力」端子を表し
ていることを示す特別な識別子。（Ｄ．４）前記現在のツリー・ノードがインスタンスの
場合には、現在のインスタンスの出力ネット（現在のツ
リー・ノード）に対応するネット・レコードのネットリ
ストのネットの番号。（Ｄ．５）このツリー・ノード及びその子を表すのに必
要な関数発生器の最小数。（Ｄ．６）関数発生器（Ｄ．５）の最小数を用いて前記
ノード及びその子を表わす場合にこのツリー・ノードが
必要とする「実」入力の数。（Ｄ．７）現在のツリー・ノードの属性を記述するブー
ル・フラッグの組。これらの属性には、前記ツリー・ノ
ードが達成された論理ゲートを表しているかどうか、前
記ノードが後述する特別のＨ関数発生器の１部分である
かどうか、前記ノードが親のノードから分岐されたもの
であるかどうか、及び前記ノードが該ノードの親を包含
する（この包含することが「暗示」されている）関数発
生器に於て表されるべきかどうかが含まれる。その包含
することが暗示されるべきインスタンスの一例が図５の
素子Ｅ1である。Ｅ1は、素子Ｅ2の子供である。親の素
子Ｅ２の機能が関数発生器によって実行される場合に
は、子Ｅ1の機能は、区分けブロックＰ12によって暗示
されるようにその関数発生器に含まれるべきである。

【００６９】定義Ｄ．７の特殊な「Ｈ」関数発生器につ
いて以下に詳細に説明する。図３の前記論理アレイは、
各機能実行領域ＬＡxy内に唯１個の関数発生器ｆxyを有
するように描かれている。これは、素子の複製がどのよ
うにして必要な完成発生器を少なくし、かつ従って機能
実行領域（ＬＡ11、ＬＡ12、ＬＡ13等）の数を少なくし
かつ／または信号伝搬時間を小さくし得るかを容易に理
解できるようにするためである。

【００７０】前記論理領域はその境界内に２個以上の関
数発生器を有することができる。図１１の平面図には、
コンフィグラブル論理ブロック（ＣＬＢ）６００、スイ
ッチングマトリックス（ＳＷＭ）６０１、長い線６０
２、短い線６０３及びキャリー伝搬線６０４からなるア
レイを有するより複雑な機能実行ＣＬＡチップ７００の
一般的な構造が示されている。ＣＬＢ６００は、１個ま
たは２個以上の素子６０１〜６０４によって互いに接続
されている。

【００７１】図１２に関して、各コンフィグラブル論理
ブロック（ＣＬＤ）６００は、ｆF、ｆG、ｆHをそれぞ
れ付した第１乃至第３関数発生器を有する。第１関数発
生器ｆFは、それぞれにＣＬＢ６００から延出する４個
の入力端子Ｆ1〜Ｆ4とＣＬＢ６００内に設けられた１個
の出力端子Ｆ0とを有する。関数発生器ｆFが１個乃至４
個の入力項（ビット）と１個の出力項（ビット）とを有
するあらゆるブール論理関数を実行できるように、関数
発生器ｆF内には１６個のユーザコンフィグラブル・メ
モリセルを有するメモリユニットＭ１６を備える。デー
タは、図１１に示される他のコンポーネントの他のユー
ザコンフィグラブル・メモリユニットＭ１６、Ｍ８、Ｍ
２、Ｍを更に有する図示されない直列のチェーン状シフ
トレジスタを介してメモリユニットＭ１６内にロードさ
れる。

【００７２】第２の関数発生器ｆGは同様に、ＣＬＢ６
００から延出する４個の入力端子Ｇ１〜Ｇ４と単一の出
力端子Ｇ０とを有する。また、関数発生器ｆGは、最大
４個の入力信号と１個の出力信号とを有するあらゆるブ
ール関数を実行するための１６ビットユーザ・コンフィ
グラブル・メモリユニットＭ１６を有する。

【００７３】第３の関数発生器ｆHは唯３個の入力端子
Ｈ１〜Ｈ３を有し、それらの中の１個Ｈ１のみがＣＬＢ
６００から延出している。他の２個の入力端子Ｈ３、Ｈ
２は、それぞれ第１及び第２関数発生器ｆF及びｆGの出
力端子Ｆ０及びＧ０に接続している。第３の関数発生器
ｆHのユーザ・コンフィグラブル・メモリユニットＭ８
には８個のメモリセルのみが設けれている。

【００７４】第３関数発生器ｆHの出力端子Ｈ０は、ユ
ーザ・プログラマブル・マルチプレクサ６１０の第１入
力端子に接続している。マルチプレクサ６１０の第２入
力端子は、第２関数発生器ｆGの出力端子Ｇ０に接続し
ている。マルチプレクサ６１０に属する１ビット・メモ
リセルＭを適当に設定することによって、ユーザはいず
れかの端子Ｇ０またはＨ０の信号を緩衝ＣＬＢ出力信号
Ｇのソースとして選択することができる。バッファリン
グ増幅器６１５がマルチプレクサ６１０の出力端子とＣ
ＬＢ出力ノードとの間に介装されている。

【００７５】また、Ｈ０出力端子が、その他の入力端子
を関数発生器の出力端子Ｆ０に接続した同様にユーザ・
コンフィグラブルな第２マルチプレクサ６２０の一方の
入力端子に接続している。この第２のマルチプレクサ６
２０は、増幅器６１７を通過する第２緩衝ＣＬＢ出力信
号Ｆを供給する。

【００７６】ＣＬＢ６００は、更に一対のフリップフロ
ップＦＦ1及びＦＦ2を有する。これらの各フリップフロ
ップＦＦ1、ＦＦ2は、データ入力端子Ｑ、クロック入力
端子＞、クロックイネーブル端子ＥＣ、データプリセッ
ト端子ＳＤ及びデータリセット端子ＲＤを有する。フリ
ップフロップＦＦ1、ＦＦ2のＱ出力信号は、それぞれ増
幅器６１６、６１４によって一時的に記憶されてＣＬＢ
レジスタ出力信号Ｑ１及びＱ２を生成する。

【００７７】フリップフロップＦＦ1及びＦＦ2のクロッ
ク入力端子＞にそれぞれ外部クロック信号Ｋの反転信号
Ｋ＊または非反転信号Ｋのいずれかを供給するために、
ユーザ・プログラマブル・マルチプレクサ６３１、６３
２がＣＬＢ６００内に設けられている。更にＣＬＢ６０
０内には、各フリップフロップＦＦ1及びＦＦ2のクロッ
クイネーブル端子ＥＣに外部ブロックイネーブル信号Ｃ
４または一定の論理１信号を供給するためにユーザ・コ
ンフィグラブルマルチプレクサ６４１、６４２が設けら
れている。セット／リセット制御ユニット６５１、６５
２は、外部Ｓ／Ｒ信号を（制御信号Ｃ３を付して表示）
に応答して各フリップフロップＦＦ1及びＦＦ2にセット
コマンドまたはリセットコマンドの一方を印加しまたは
双方共印加しないようにユーザが構成可能になってい
る。ユーザ・コンフィグラブル・マルチプレクサ６６
１、６６２はフリップフロップＦＦ1及びＦＦ2の各デー
タ入力端子Ｄに関数Ｆ０、Ｇ０及びＨ０上の関数出力信
号のユーザが選択したいずれかの信号、または外部から
供給された入力信号ＤＩＮ（制御信号Ｃとして表示）を
供給するために４個の入力端子を有する。

【００７８】更に、ＣＬＢ６００内には、図１１に示さ
れるように水平に延長するキャリー伝搬線６０４に沿っ
てＣＬＢ６００のすぐ上方及び下方に配置された他の同
様のＣＬＢ図１２）に向けてまたはそれらからすばやく
キャリー信号を伝搬するためにキャリー伝搬回路６７０
が設けられている。

【００７９】図１３に関して、各ＣＬＢはその関数入力
端子Ｆ１〜Ｆ４、Ｇ１〜Ｇ４及びＨ１が、レジスタ出力
Ｑ１及びＱ２と同様に図示されるように関数出力端子Ｆ
及びＧと共に配設されている。（入力端子Ｃ１は、入力
端子Ｃ２、Ｃ３、Ｃ４をそれぞれ図１１のＤＩＮ、Ｓ／
Ｒ、及びＥＣ信号に対応させているが、関数発生器入力
端子Ｈ１と同じ意味である。）

【００８０】ＣＬＢ６００が上述したような構造を有す
ることから、関数発生器ｆHのＨ０出力端子をＣＬＢ出
力端子（Ｆ、Ｇ、Ｑ１またはＱ２）のいずれかに接続
し、かつそのＨ２入力端子またはＨ３入力端子の一方ま
たは双方に存在する信号に応答してＨ０出力信号を生成
するように関数発生器ｆHを構成する（プログラムす
る）ことによって、各ＣＬＢ６００内でピラミッド状の
ネットワークを実行できることが分かる。

【００８１】図１４に関して、多くの場合に当然ながら
ツリー状ネットワークが論理設計に表れることが分か
る。例えば、第１及び第２の機能素子ｆ71及びｆ72の出
力信号が第３機能素子ｆ73の入力になる。第３機能素子
ｆ73は、図示されるように機能素子ｆ71及びｆ72の唯一
の子供である。機能設計素子ｆ73が３個の入力端子を有
するのに対して、機能設計素子ｆ71及び72はそれぞれ４
個の入力端子を有する。このような場合には、前記ＣＬ
Ｂのリソースが完全に利用されかつＣＬＢ間（ＣＬＢ
外）ルーティング線が無駄とならないように、単一のＣ
ＬＢ６００内に素子ｆ71、ｆ72及びｆ73によって形成さ
れる複合ツリー構造を実行することが好ましい。

【００８２】再び図１２に関して説明すると、関数発生
器ｆFが第１の設計素子ｆ71の機能を実行し、関数発生
器ｆGが第２の設計素子ｆ72の機能を実行し、かつ関数
発生器ｆHが第３の設計素子ｆ73の機能を実行すること
になる。このｆ71〜ｆ73からなるツリー構造は完全に前
記ＣＬＢ内のＦＧＨツリーパターンにマッピング即ち写
像されている。

【００８３】図１５では、ｆ71〜ｆ73からなるツリーの
機能を吸収したブロックがＣＬＢ123として図示されて
いる。同様に、機能素子ｆ74〜ｆ76を第２ブロックＣＬ
Ｂ456に写像し、かつ機能素子ｆ81〜ｆ83を第３ブロッ
クＣＬＢ321に写像することが好ましい。更に、機能素
子ｆ85及びｆ86を第４ブロックＣＬＢ654の各関数発生
器Ｆ、Ｈに写像すると好都合である。（これによって、
ＦＧＨツリーパターンではなくＦＨツリーパターンが定
義される。）第４ブロックＣＬＢ654の関数発生器Ｇは
設計素子ｆ84の機能を吸収することができる。そして、
図１４を完成させるためには、機能ｆ77、ｆ87及びｆ88
を第５ブロックＣＬＢ778に写像することが好ましい。

【００８４】このような観点から、本発明の１つの特徴
は、このように設計素子を論理領域内に最適にマッピン
グ即ち写像する可能性が最大となるようにパーティショ
ニング即ち区分け過程を調整することである。これは、
ＣＬＡチップの機能実行領域がそれぞれ図３の単一の関
数発生器を有する論理領域ＬＡxyではなく図１２の多数
の関数発生器を有するＣＬＢとして画定されるような場
合に適用される。例えば図７及び／または図８の区分け
調整方法は、結果的に得られる関数発生器の数及び／ま
たは関数発生器間伝搬遅れについてだけではなく結果と
して得られるＣＬＢの数及びＣＬＢ間信号伝搬遅れにつ
いても注目するように構成されている。

【００８５】最小数のＣＬＢを実現するためのステップ
が、以下の表に示す擬似コードリストのように設定され
る。

【００８６】

【表１】

【００８７】

【表２】

【００８８】

【表３】

【００８９】

【表４】

【００９０】

【表５】

【００９１】

【表６】

【００９２】

【表７】

【００９３】

【表８】

【００９４】

【表９】

【００９５】

【表１０】

【００９６】

【表１１】

【００９７】

【表１２】

【００９８】上述の方法は、米国カリフォルニア州サン
ノゼに所在するザイリンクス・インコーポレイテッド
（Xilinx Inc.）のＣＬＡチップのＸＣ４０００（登録
商標）ファミリーを構成（configure）するために同社
から販売されているＸＡＣＴ（登録商標）レイアウト・
ツールキットに適合するように構成されている。上述し
た方法で作成される区分けネットリスト・ファイルは、
コンピュータ読取り可能媒体に固定され、ユーザが定義
する機能技術を満足する物理的な回路を製造するべくレ
イアウト及びインプリメンテーションプロセスに於て使
用される製品である。

【００９９】本発明の変形・変更については、当業者で
あれば上述の説明から容易に理解することができる。例
えば、異なる数またはパターンの関数発生器を有するＣ
ＬＢを用いることができる。前記境界ルールは、１個の
チップに異なるＣＬＢを混在させ使用しているような場
合には或るＣＬＢから別のＣＬＢに変更することができ
る。また、上述した実施例は単なる例示であって、本発
明はその技術的範囲内に於て様々な変形・変更を加えて
実施することができる。

【０１００】

【図面の簡単な説明】

【図１】コンフィグラブル・論理アレイ（ＣＬＡ）デバ
イスに於て実行されるべきサンプル・デジタル論理デバ
イスを示す回路図である。

【図２】図１に示される論理機能を実行するように構成
されるべきＣＬＡデバイスを示す平面図である。

【図３】図２のＣＬＡチップの１部分に存在する機能実
行サブセクションを詳細に示す拡大平面図である。

【図４】図３の各機能実行サブセクションの制限された
能力に対応する境界ルールを満足するように区分けを行
なう場合に或る設計部分の第１の区分けを示す回路図で
ある。

【図５】前記回路設計の第２の区分けを示す回路図であ
る。

【図６】素子複製過程及びそれによって可能となる区分
けを示す回路図である。

【図７】本発明による区分け最適化プロセスを示すフロ
ー図である。

【図８】本発明による伝搬遅れ最小化プロセスを示すフ
ロー図である。

【図９】本発明のネット、ピン及びインスタンスの概念
を示す回路図である。

【図１０】Ａ〜Ｃ図からなり、それぞれにネット・テー
ブル、インスタンス・テーブル及びピン・テーブルから
なるネットリスト・データベースを画定するコンピュー
タ読取り可能メモリデバイスの部分を示す図である。

【図１１】その基板上に画定されるコンフィグラブル論
理ブロック（ＣＬＢ）、スイッチングマトリックス（Ｓ
ＷＭ）及び接続バスのアレイを有するＣＬＡチップの平
面図である。

【図１２】コンフィグラブル論理ブロックＣＬＢのブロ
ック図である。

【図１３】外部接続線との関連に於て図１１のＣＬＢ上
の入力端子及び出力端子の物理的な方向を示す平面図で
ある。

【図１４】ブール・ツリー構造を示す図である。

【図１５】図１４のツリー構造のＣＬＢの組への最適な
写像を示す図である。

【符号の説明】

１０設計図２０チップ２１水平線２２垂直線２３水平線２４垂直線２５入出力ピン２００基板セクション３００、６１０設計セクション４００論理設計５００自動化システム５０１開始ステップ５１０初期化ステップ５１５サーチステップ５２０複製ステップ５２５区分けステップ５３０カウントステップ５４０比較ステップ５５０設定ステップ５６０最終ステップ５７０ループバック５８０信号伝搬時間最小化プロセス５８１開始ステップ５８２複製範囲設定ステップ５８４サーチステップ５８６複製ステップ５８８区分けステップ５９０計算ステップ５９２比較ステップ５９４設定ステップ５９６最終ステップ５９８ループバック６００ＣＬＢ６０１ＳＷＭ６０２、６０３接続線６０４キャリー伝搬線６１０ユーザ・プログラマブル・マルチプレクサ６１４増幅器６１５バッファリング増幅器６１６増幅器６１７増幅器６２０第２マルチプレクサ６３１、６３２ユーザ・コンフィグラブル・マルチプ
レクサ６４１、６４２ユーザ・コンフィグラブル・マルチプ
レクサ６５１、６５２セット／リセット制御ユニット６６１、６６２ユーザ・コンフィグラブル・マルチプ
レクサ６７０キャリー伝搬回路７００ＣＬＡチップ

Claims

【特許請求の範囲】

【請求項１】相互に接続された多数の回路コンポー
ネントを有する回路設計から物理的な回路を製造する方
法に於て、前記各回路コンポーネントが少なくとも１個
の信号出力端子と１個または２個以上の信号入力端子と
を有し、少なくとも１個の前記回路コンポーネントの前
記出力端子が、ピラミッド状回路を画定するように１個
または２個以上の他の前記回路コンポーネントの各１個
または２個以上の前記入力端子を駆動するように結合さ
れ、前記物理的回路が複数の機能実行領域を有し、かつ
第１の数Ｊ以下の数の独立した入力信号線と第２の数Ｋ
以下の数の独立した出力信号線とが前記機能実行領域の
境界を横切ることができるような所定の境界ルールによ
って前記各機能実行領域が制限されており、その前記信号出力端子が前記ピラミッド状回路の２個以
上の他の前記回路コンポーネントの前記信号入力端子を
駆動する或る前記回路コンポーネントを複製候補として
識別する過程と、その対応する信号入力端子が互いに接続されかつ対応す
る信号出力端子が互いに独立しているような複数の複製
コンポーネントで前記複製候補を置き換える過程とから
なることを特徴とする物理的回路の製造方法。
【請求項２】前記置換え過程の後に、それぞれに前
記境界ルールを満足する設計部分に前記回路設計を区分
けする過程を更に有することを特徴とする請求項１に記
載の方法。
【請求項３】前記区分け過程の後に、前記物理的回
路の対応する前記機能実行領域にある各前記設計部分を
実行する過程を更に有することを特徴とする請求項２に
記載の方法。
【請求項４】結果物である前記物理的回路が、その
表面に前記機能実行領域を均一に配置したモノリシック
基板を有することを特徴とする請求項１に記載の方法。
【請求項５】前記各機能実行領域が、第１の数ＩF
の入力項と第２の数ＯFの出力項とを有するブール論理
関数を実行するための第１ルックアップ・テーブル手段
Ｆを有することを特徴とする請求項１に記載の方法。
【請求項６】前記各機能実行領域が第３の数ＩHの
入力項と第４の数ＯHの出力項とを有するブール論理関
数を実行するための第２のルックアップ・テーブル手段
Ｈを有することを特徴とする請求項５に記載の方法。
【請求項７】前記第１ルックアップ・テーブル手段
Ｆの少なくとも１個の前記出力項が、前記第２ルックア
ップ・テーブル手段Ｈの入力項としての機能を有するこ
とを特徴とする請求項６に記載の方法。
【請求項８】既定の論理設計の各部分を構成変更可
能な論理アレイの機能実行領域に自動的に複写すること
によって前記論理設計を実行するための装置であって、
前記論理設計が順次結合された入力及び出力ノードを有
する複数の回路要素を備え、かつ前記論理設計が機械読
取り可能なメモリデバイスに含まれるネットリストデー
タによって記述されており、ファンアウト数を特徴付けされた或る前記回路要素の出
力ノードによって駆動される次の前記入力ノードの特性
数とした場合に、ｆｏL≦ファンアウト数≦ｆｏHとして
複製範囲を画定する複製範囲画定手段と、前記メモリデバイスの前記ネットリストデータをサーチ
しかつ前記複製範囲を満足する回路要素を識別するため
のサーチ手段と、前記ネットリストの識別された前記各回路要素を複数の
複製要素に置き換えるための回路要素複製手段とを備え
ることを特徴とする論理設計の自動マッピング装置。
【請求項９】前記複製範囲画定手段を変更して新し
い複製範囲を画定するための調整手段と、新しい前記複製範囲に従って構成される論理アレイの特
性を先の複製範囲に従って構成される論理アレイの同様
の特性と比較するための比較手段とを更に備えることを
特徴とする請求項８に記載の装置。
【請求項１０】前記特性に、前記論理設計を実行す
るために前記論理アレイに於て消費される関数発生器の
総数が含まれることを特徴とする請求項９に記載の装
置。
【請求項１１】前記特性に、前記論理設計を実行す
るための前記論理アレイに於て消費される前記機能実行
領域の総数が含まれることを特徴とする請求項９に記載
の装置。
【請求項１２】前記特性に、前記論理設計の第１設
計要素から第２設計要素への信号伝搬時間が含まれるこ
とを特徴とする請求項９に記載の装置。
【請求項１３】第１の数の機能素子と前記機能素子
を連結する第２の数のネットとを含む最初の機能定義か
ら導出される回路を有する構成変更可能な論理アレイで
あって、前記回路が、前記第１の数より大きな第３の数
の機能素子を有し、かつ前記最初の機能定義に於て画定
される機能素子の複製を有する複製包含機能定義から導
出されることを特徴とする論理アレイ。
【請求項１４】既定の論理設計をサーチする過程
と、既定のファンアウト範囲を満足する前記論理設計内の或
る一定の前記論理要素に複製候補としてタグ付けする過
程と、前記論理設計内の前記複製候補を複製する過程とからな
ることを特徴とする回路のレイアウト方法。