JP2009282976A - 相互接続回路内のデータ経路のルーティングを求める方法、システム、およびコンピュータプログラム製品 - Google Patents

相互接続回路内のデータ経路のルーティングを求める方法、システム、およびコンピュータプログラム製品 Download PDF

Info

Publication number
JP2009282976A
JP2009282976A JP2009120244A JP2009120244A JP2009282976A JP 2009282976 A JP2009282976 A JP 2009282976A JP 2009120244 A JP2009120244 A JP 2009120244A JP 2009120244 A JP2009120244 A JP 2009120244A JP 2009282976 A JP2009282976 A JP 2009282976A
Authority
JP
Japan
Prior art keywords
tiles
tile
tree
interconnect
devices
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Granted
Application number
JP2009120244A
Other languages
English (en)
Other versions
JP5241603B2 (ja
Inventor
Kostadin Gitchev
コスタディン・ジチェフ
Bingda Brandon Wang
ビンダ・ブランドン・ワン
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
ARM Ltd
Original Assignee
ARM Ltd
Advanced Risc Machines Ltd
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by ARM Ltd, Advanced Risc Machines Ltd filed Critical ARM Ltd
Publication of JP2009282976A publication Critical patent/JP2009282976A/ja
Application granted granted Critical
Publication of JP5241603B2 publication Critical patent/JP5241603B2/ja
Expired - Fee Related legal-status Critical Current
Anticipated expiration legal-status Critical

Links

Images

Classifications

    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F30/00—Computer-aided design [CAD]
    • G06F30/30—Circuit design
    • G06F30/39—Circuit design at the physical level
    • G06F30/394—Routing

Landscapes

  • Engineering & Computer Science (AREA)
  • Computer Hardware Design (AREA)
  • Physics & Mathematics (AREA)
  • Theoretical Computer Science (AREA)
  • Computer Networks & Wireless Communication (AREA)
  • Evolutionary Computation (AREA)
  • Geometry (AREA)
  • General Engineering & Computer Science (AREA)
  • General Physics & Mathematics (AREA)
  • Design And Manufacture Of Integrated Circuits (AREA)

Abstract

【課題】様々なデータ経路間の高精度の遅延整合を可能にする、集積回路の相互接続回路内のデータ経路のルーティングを求める改良型の技術を提供する。
【解決手段】集積回路についての相互接続回路内のデータ経路のルーティングを求めるシステム、方法、およびコンピュータプログラム製品が提供される。第1辺上の相互接続回路が、第1デバイスに対する接続のためのナローインターフェースを提供し、第2辺上の相互接続回路が、分散した複数の別のデバイスに対する接続のためのワイドインターフェースを提供する。各データ経路が、別のデバイスのうちの1つに関連付けられ、その関連付けられる別のデバイスと第1デバイスとの間の相互接続回路を通じて接続を実現する。
【選択図】図1

Description

本発明は、集積回路の相互接続回路内のデータ経路のルーティングを求める技術に関する。
ASIC(特定用途向け集積回路)設計フロープロセスで使用されるデジタルレイアウトEDA(electronic design automation)ツールなどの現在の設計ツールは、ディープサブミクロンプロセスで高速ネットおよびバスに対して必要とされることがあるような、相互接続回路のタイミングクリティカルなデータ経路に関する遅延整合で高精度を達成する際の厳しい制限を有する。この制限は主に、EDAツールがどのように問題に取り組むかということによるものである。
現在のデジタルレイアウトEDAツールは、タイミング制約を、設計レイアウトに対する要件として使用する。これはしばしば、「タイミングドリブン位置およびルート(timing driven place and route)」と呼ばれる。これにより、ASICレイアウトツールには、実際には無制限の数のレイアウト実装が提示される。このジレンマに直面して、EDAツールはしばしば、発見的アルゴリズムを使用してASICレイアウトを自動的に生成する。発見的アルゴリズムとは、最適解を求めるように設計されるのではなく、目標関数の点で最適解に近い、実現可能な解を見つけることを目標とするアルゴリズムである。設計の初期の配置およびルートが設計タイミング制約を満たすことはまれである。結果として、レイアウトツールは、設計タイミング制約を満たすことを望みながら、設計のタイミングクリティカルな部分の位置およびルートの反復に頼る。
例えば、高速平衡バス相互接続の場合に通常はそうであるように、設計要件が非常に限定的なものであるとき、レイアウト反復は往々にして収束せず、したがってツールは、使用可能なレイアウトの生成に失敗する。レイアウトツールが設計要件を満たすことに成功しないとき、生成されるレイアウトは、素子配置または信号ルーティングのどちらかで対称性がない。ネットはランダムな長さとなり、層から層へランダムにジャンプする。得られる各ネットのキャパシタンス、抵抗、カップリング、およびインダクタンスを正確に管理することができない。この結果、レイアウトのタイミング不確定性が生じる。
周知のデジタルレイアウトEDAツールは、タイミングを改善するいくつかの技術を使用する。こうした技術は、ある駆動素子を、同じ機能を有するが異なる駆動強度を有する別の駆動素子と置き換えること、クリティカルパス上にバッファを挿入して、遅延を加速または減速すること、および/または長いネットをレピータバッファで分割すること、重要な各セルを物理的に近くに移動することを含む。こうした手法によるタイミング変動が量子化され、タイミング不確定性を導入する。異なるタイミングクリティカルパス間の整合も、プロセスコーナにわたって非常に低減される。こうした経路は、異なる素子数、または異なる駆動特性を有する素子で構築されるからである。異なる素子のタイミング特性は、プロセス-温度-電圧コーナにわたって同一にスケーリングしない。あるコーナを合致させるとしばしば、別のコーナが不整合となる。
デジタルEDAレイアウトアルゴリズムの発見的な性質のために、異なるツールバージョン、または異なるベンダからのバージョンで、同一の設計が劇的に異なるレイアウトを生成する可能性がある。レイアウト手続きが反復されるとき、しばしば同一のツールが、同じ設計で異なるレイアウトを生成する。
現在のデジタルEDAレイアウトフローの別の制限は、ツールが、2つの別々のワイヤ上で送られる2つの補信号によって情報を電気的に送信する方法である差分信号を扱うことが不可能であることである。そのような差分信号技術は、例えばデジタルゲートのスイッチングによって生成されるような雑音のある環境を介する高速信号の正確な伝播を可能にすることができる。
結果として、周知のデジタルレイアウトEDAツールおよびASICフローは、相互接続回路内のクリティカルタイミング経路、ネット、およびバス(本明細書では「データ経路」と呼ぶ)の高度な遅延整合および雑音無影響性を必要とする設計レイアウトを生成することができない。
周知のデジタルレイアウトEDAツールの制限は、バスの異なるビットを物理的に接近していない設計ブロックにルーティングしなければならず、しかもタイミングの整合が必要とされるときに悪化する。DDR(double data rate)メモリインターフェースは、この制限の良い例である。DDRメモリは、ダブルポンピングする(クロック信号の立上りおよび立下り時にデータを転送する)ことにより、クロック周波数を上昇させることなく、非DDR(single data rate)メモリのほぼ2倍の帯域幅を達成する。DDRメモリコントローラは、それが接続しなければならない入出力(I/O)デバイスのスパンに対して比較的小型のレイアウトを有し、これにより、メモリコントローラをこうした分散I/Oデバイスと結合するのに使用される相互接続回路の設計に対して著しいタイミング問題が課される。
一例を挙げると、DDR3は、1600Mbsものデータ転送速度でオフチップSDRAMからのデータを読み書きするのにクロックの両端を使用するパラレルインターフェースである。データ信号DQ、ストローブ信号DQS、およびクロック信号CKの間のタイミング関係をしっかりと制御しなければならず、しかもこの設計に関するI/Oデバイスは、直線的に2mm超に及ぶことがある(すなわち、メモリコントローラブロックのサイズよりも何桁も大きい)。
クロックジッタ、オンチップ変動、プロセス-電圧-温度変動、プリント回路トレース変動、システム雑音、SDRAMセットアップおよび保持タイミングなどの制御不能タイミング不確定性を考慮に入れることにより、相互接続回路内のメモリコントローラとI/Oデバイスの間のデータ経路の伝播遅延を数十ナノ秒以内に整合させることが必要となる。2mm以上のネットについて数百ナノ秒の領域内にある相互接続遅延を仮定すると、そのような相互接続回路の設計は、現在のデジタルレイアウトEDAツールでは達成が困難である。
したがって、様々なデータ経路間の高精度の遅延整合を可能にする、集積回路の相互接続回路内のデータ経路のルーティングを求める改良型の技術を提供することが望ましい。
第1態様から見ると、本発明は、集積回路についての相互接続回路内のデータ経路のルーティングを求める方法において、第1辺上の相互接続回路が、第1デバイスに対する接続のためのナローインターフェースを提供し、第2辺上の相互接続回路が、分散した複数の別のデバイスに対する接続のためのワイドインターフェースを提供し、各データ経路が、前記別のデバイスのうちの1つに関連付けられ、その関連付けられる別のデバイスと第1デバイスとの間の相互接続回路を通じて接続を実現する方法であって、
(i)ワイドインターフェースに沿って設けるべき複数のセルを定義するステップであって、別のデバイスのそれぞれが、前記セルのうちの少なくとも1つに関連付けられるステップと、(ii)行および列として形成されたブロックのアレイとして相互接続回路を定義するステップであって、各セルが前記列のうちの1つに当接するステップと、(iii)所定の1組のタイルを設けるステップであって、各タイルが所定の配線レイアウトを提供するステップと、(iv)各ブロックについて、所定の規則を適用して、そのブロックを実装するのに使用すべき前記タイルのうちの1つを決定するステップであって、所定の規則が、アレイ内のブロックの位置、ならびに複数の別のデバイスと複数のセルの間の関連付けを考慮に入れて、相互接続回路によって設けられる各データ経路が同一の伝播遅延を有することを保証するステップとを含む方法を提供する。
本発明によれば、第1デバイスを分散した複数の別のデバイスと結合するのに使用される相互接続回路内のデータ経路のルーティングを求める方法が提供される。相互接続回路は、第1デバイスと結合するためのナローインターフェースと、分散した複数の別のデバイスと結合するためのワイドインターフェースとを有する。相互接続回路は、行および列として形成されたブロックのアレイとみなされ、所定の1組のタイルが、相互接続回路を構築する際に使用するために提供され、各タイルは所定の配線レイアウトを提供する。各ブロックについて、所定の規則が適用され、そのブロックを実装するのに使用すべきタイルのうちの1つが決定される。アレイ内のブロックの位置、および複数の別のデバイスとワイドインターフェースに沿って設けられる複数のセルとの間の関連付けを考慮に入れるように所定の規則を構成することにより、このタイル割振りプロセスは、相互接続回路によって設けられる各データ経路が同一の伝播遅延を有することを保証する。
したがって、本発明が、所定のタイルを使用する構造化ルーティング方法を提供し、相互接続回路によって設けられる各データ経路が同一の伝播遅延を有することを保証するように、所定の規則が適用されて、相互接続回路を形成するブロックのアレイ内の各ブロックを実装するのにどのタイルが使用されるかが決定されることがわかる。
本発明を使用することにより、周知の従来技術配置ツールと比較して、いくつかの利点を得ることができる。まず、相互接続回路内の各データ経路が同一の伝播遅延を有する効果的な機構を提供することに加えて、プロセスは、カップリング、漏話、ローディング、雑音遮蔽などの他の物理的効果も整合させることができる。さらに、本発明の実施形態では、何ら反復する必要なしに方法を実装することができ、したがって、実行可能なルーティング設計を見つける目的で反復プロセスを実施する必要がある周知のEDAツールと比較したときに、著しい設計時間速度の利点が得られる。さらに、本発明は、所定の配線レイアウトを有するタイルを使用して、同一の伝播遅延を有するデータ経路を生成するものであるので、これにより、タイミングおよび整合を改善するために一定の経路中にバッファおよび/または他の構成要素をしばしば挿入する周知のEDAツールで設計されたものよりも、消費する電力が著しく低い相互接続回路を生み出すことができる。
一実施形態では、各データ経路が、タイルのシーケンスによって形成され、シーケンス中の各タイルは、シーケンスの隣接するタイル内の配線レイアウトと少なくとも部分的に当接する配線レイアウトを有するように選択される。したがって、各データ経路は、そのデータ経路を形成するのに使用されるタイルの関連するシーケンス内の様々な配線レイアウトの組合せによって形成される。各タイル内のワイヤの物理的レイアウトのために、各タイルに関連する伝播遅延が所定のものとなる。所定のタイルの組は、様々な異なる配線レイアウトに異なる伝播遅延を与え、これにより、伝播遅延があらゆるデータ経路について整合されることを保証するために、アレイ内のブロックの位置、および相互接続回路に接続すべき様々な別のデバイスの配置を考慮に入れて、所定の規則が、各ブロックを実装するのに使用すべき適切なタイルを決定することが可能となる。
一実施形態では、所定の規則は、ツリー構造を生成するようにタイルをアレイ内の個々のブロックに割り振り、少なくとも1つの列が、ツリー構造のトランクとして形成されるナローインターフェースに当接し、残りの列内の行が、ツリー構造のブランチを形成する。前記ステップ(iv)で、アレイ内の個々のブロックを実装するのに使用すべきタイルを決定するときに、前記所定の規則は、ブロックがツリー構造のトランク内にあるか、それともツリー構造のブランチ内にあるかを考慮に入れる。そのようなツリー構造の使用により、特に効率的なデータ経路のルーティングを達成することが可能となることが判明した。
一実施形態では、前記所定のタイルの組は、トランクタイルの所定のサブセットと、ブランチタイルの所定のサブセットとを含み、前記ステップ(iv)中に、各ブロックについて、所定の規則が、ブロックがツリー構造のトランク内にある場合にトランクタイルのサブセットからタイルを選択し、またはブロックがツリー構造のブランチ内にある場合にブランチタイルのサブセットからタイルを選択する。
一実施形態では、セルの数が、前記ワイドインターフェースに接続すべき別のデバイスの数を超過し、それによって、前記別のデバイスのうちの1つに関連付けられない少なくとも1つの非接続セルが存在し、ツリー構造のトランクとして形成された各列について、その列に当接するように選ばれたセルが非接続セルである。
したがって、そのような実施形態では、所定の規則が使用されて、ツリー構造のトランクを形成するブロックの列を実装するのに使用されるトランクタイルが選択されるとき、そうしたタイルが別のデバイスのうちの1つとの何らかの直接的接続を実現するための要件はなく、様々な別のデバイスとの接続が、ツリー構造のブランチを実装するのに使用されるブランチタイルを介して行われる。
様々な方式でツリー構造を設計することができる。しかし、一実施形態では、ツリー構造は、1つまたは複数のツリー区間を含み、各ツリー区間は、ナローインターフェースに当接してそのツリー区間に対するトランクを形成する1つの列を有し、ツリー区間の残りの列内の行が、そのツリー区間のブランチを形成する。別々のツリー区間からツリー構造を形成することを可能にすることにより、データ経路ルーティングのレイアウトに関する柔軟性、および相互接続回路のワイドインターフェースに接続すべき別のデバイスの配置に関する柔軟性の改善が実現される。例えば、一実施形態では、少なくとも1つのツリー区間が、少なくとも1つの他のツリー区間とは異なる軸上に設けられ、それによって別のデバイスを複数の軸にわたって分散させることが可能となる。一実施形態では、そのような軸の変化をツリー区間自体の中に吸収することもできる。
様々なタイプのツリー区間を設けることができる。一実施形態では、各ツリー区間は、左ツリー区間または右ツリー区間を含み、前記ステップ(iv)で、適用される所定の規則が、タイルが左ツリー区間のブロックについて決定されるか、それとも右ツリー区間のブロックについて決定されるかに依存すると共に、左ツリー区間内であっても、右ツリー区間内であっても、相互接続回路によって与えられる各データ経路が同一の伝播遅延を有することを依然として保証する。一実施形態では、そのような手法を使用して、相互接続回路のデータ経路レイアウトを、概して中央のトランクを有し、トランクからブランチが対向する方向に形成されるツリー構造として生成することができる。一実施形態では、左ツリー区間と右ツリー区間を共に同じ列数および行数を有するように構成することができ、それによって、ツリー構造のトランクを中心とした対称的設計を生成することが可能となる。
分散した複数の別のデバイスを集積回路上で様々な方式で配置させることができる。しかし、一実施形態では、別のデバイスは、少なくとも1つの軸をたどる分散経路上に分散する。一実施形態では、別のデバイスをすべて線形経路に沿って配置することができ、別の実施形態では、互いに異なる向きでよい複数の線形経路に沿ってデバイスを設けることができる。
一実施形態では、分散経路中の少なくとも1つの地点で、アクセスの変化が生じ、この方法は、前記ステップ(ii)で、軸の変化が生じる分散経路中の各地点に関連して、相互接続回路内にコーナ素子を定義し、それによって各コーナ素子が、アレイ内のブロックの2つの隣接する列間の軸の変化を定義するステップと、前記ステップ(iv)で、所定の規則が、前記所定のタイルの組と共に含まれる所定のコーナタイルを使用して各コーナ素子を実装し、アレイ内の各ブロックについて使用すべきタイルを決定するときに、所定の規則が、相互接続回路によって設けられる各データ経路が同一の伝播遅延を有することを保証するように、相互接続回路内の任意のコーナ素子の位置を考慮に入れるステップとをさらに含む。
所定のコーナタイルを使用することにより、そのようなコーナタイルを使用することに伴う伝播遅延が所定のものとなり、したがって、所定の規則は、相互接続回路内の各データ経路が同一の伝播遅延を有することを保証するように、各ブロックについて相互接続回路内のそのブロックを実装するのに使用すべき適切なタイルを決定するときに、任意のコーナ素子の位置を考慮に入れることができる。
コーナ素子が比較的短い場合、これにより、レイアウトが密集することなく(トランクに関して)コーナ素子の反対側に設けることのできるブランチ数が限定される。一実施形態では、このことを、コーナ素子のどちらかの側にフィラー素子を定義し、次いで所定のタイルの組内に提供される所定のフィラータイルを使用して各フィラー素子を実装することによって軽減することができる。コーナタイルと組み合わせたそのようなフィラータイルは、コーナ素子のサイズを実質上拡張し、コーナ素子の反対側で多数のブランチを必要とするツリー構造を構築することが可能となる。
非接続セルが存在する実施形態では、この方法は、相互接続回路への接続を必要としない集積回路の1つまたは複数の他の構成要素を、1つまたは複数の非接続セルに関連付けるステップをさらに含むことができる。非接続セルに関連付けることのできるそのような構成要素の一例を挙げると、そのような構成要素は、相互接続回路に接続すべき分散した複数の別のデバイスに電力供給するのに使用される電力供給線を備えることができる。
所定の規則を適用して、相互接続回路を定義するブロックのアレイ内の各ブロックにどのタイルを割り振るかを決定するとき、特定のブロックの位置で配線レイアウトが不要であると所定の規則が判定したとき、一実施形態では、そのブロックについてタイルが割り振られない。代替実施形態では、所定のタイルの組は、配線レイアウトを有さない1つまたは複数のフィラータイルを含むことができ、特定のブロックの位置で配線レイアウトが不要であると所定の規則が判定した場合、こうしたフィラータイルのうちの1つが、そのブロックに対して割り振られる。一実施形態では、そのようなフィラータイルは、与えられたプロセスに対する金属密度要件を満たすようにメタルフィルを有することができる。
一実施形態では、すべてのセルは等しい幅を有し、その結果として、ブロックの列のそれぞれは等しい幅となり、したがって所定のタイルの組を等しい幅で作成することができる。しかし、代替実施形態では、定義される複数のセルは、複数の異なる幅であり、所定のタイルの組は、各セルが前記列のうちの1つに当接することが可能となるように、対応する複数の異なる幅を有するタイルを含む。
しかし、代替実施形態では、フィラーセルの使用により、あらゆる可能な幅のセルに対するタイルを設ける必要を回避することができる。より具体的には、前記ステップ(i)で、一定のセルが、初期セルとフィラーセルの組合せによって形成され、それによってアレイ内の列と当接する各セルが、等しい幅となる。そのような手法により、ブロックの各列を同じ幅に構成することができ、したがって、所定のタイルの組が含む必要があるのは、その指定の幅のタイルだけとなり、それによって所定の組の中で提供する必要のあるタイルの数が削減される。
一実施形態では、第1デバイスが、相互接続回路のナローインターフェースに直接的に接続される。しかし、代替実施形態では、この方法は、相互接続回路のナローインターフェースから第1デバイスまで通るルートチャネルを定義し、それによって集積回路内のナローインターフェース以外の位置への第1デバイスの配置を可能にするステップをさらに含む。特定の一実施形態では、前記所定のタイルの組は、ルートタイルのサブセットを含み、この方法は、前記サブセットからの1つまたは複数のルートタイルを使用してルートチャネルを生成するステップをさらに含む。そのような手法により、分散した複数の別のデバイスの配置に対する第1デバイスの配置に関する自由が得られると共に、相互接続回路によって与えられる各データ経路が同一の伝播遅延を有することが依然として保証される。具体的には、一実施形態では、ルートチャネルを通る各データ経路の伝播遅延は同一であり、したがって、ルートチャネルを含めることにより、本発明の実施形態の技術の伝播遅延整合特性が維持される。
第1デバイスおよび別のデバイスは、様々な形態を取ることができる。一実施形態では、分散した複数の別のデバイスは、集積回路の周辺に配置された入力/出力デバイスを含む。そのようなデバイスでは、第1デバイスは、複数の入力/出力デバイスを制御するのに使用されるメモリコントローラデバイスである。SDR、DDRなどのメモリインターフェース、およびPCIなどのパラレルバスアーキテクチャは、本発明の実施形態のルーティング方法から恩恵を受けることのできる技術の主な例である。より一般には、本発明の実施形態の技術は、ワイドインターフェースに沿って物理的に比較的離れた間隔を置いて配置されたデバイスにナローインターフェースを接続するデータ経路に対して高度なタイミング整合が必要となる、すべての相互接続回路に適用可能である。
一実施形態では、様々な別のデバイスが、相互接続回路内の関連する列内の隣接するタイルと直接的に接続される。しかし、代替実施形態では、この方法は、前記別のデバイスのピンと、前記所定のタイルの組の中のタイルの配線レイアウトとの間のピンマッピングを実現する1つまたは複数のブリッジタイルを設けるステップと、特定の別のデバイスについて、そのピンの、当接すべき相互接続回路内のタイルの配線レイアウトに対する直接的マッピングがないとき、前記特定の別のデバイスと相互接続回路内の前記タイルとの間に少なくとも1つのブリッジタイルを導入して、前記特定の別のデバイスのピンをそのタイルの配線レイアウトにマッピングするステップとをさらに含む。したがって、そのようなブリッジタイルを使用して、相互接続回路内の関係するタイルと当接するのに必要なピン位置に適合するように、別のデバイス上のピン位置を変換することができる。そのようなブリッジタイルはまた、相互接続回路内の配線の、相互接続回路を介する接続を必要としない別のデバイス内のピンとの偶発的当接を回避する役割も果たすことができる。
一実施形態では、非接続セルがワイドインターフェースに沿って設けられる場合、そのような非接続セルの追加は、ナローインターフェースに影響を及ぼさない。さらに、そのような実施形態では、ワイドインターフェースに沿ったそのような非接続セルの追加は、データ経路がナローインターフェースに接続される順序に影響を及ぼさない。したがって、セルがワイドインターフェースに沿って設けられる方式、および別のデバイスと個々のセルとの間の関連付けにおいて高度な柔軟性がある。
一実施形態では、所定の組の中のタイルのうちの少なくとも1つの配線レイアウトは、タイルのうちの少なくとも1つが前記アレイ内のブロックを実装するのに使用されるとき、そのタイル内の配線レイアウトのすべてが使用されるのではないようなものとなる。したがって、そのような実施形態では、各タイルの配線レイアウト内の個々のワイヤのすべてが、相互接続回路内のそのタイルのすべての具体化で使用されるわけではない。そのようにタイルを設計することにより、そうしたタイルの使用に関する柔軟性の改善が得られる。
第2態様から見ると、本発明は、コンピュータシステム上で実行されたときに、集積回路についての相互接続回路内のデータ経路のルーティングを求める方法をコンピュータシステムに実行させるコンピュータプログラムを含むコンピュータプログラム製品において、第1辺上の相互接続回路が、第1デバイスに対する接続のためのナローインターフェースを提供し、第2辺上の相互接続回路が、分散した複数の別のデバイスに対する接続のためのワイドインターフェースを提供し、各データ経路が、前記別のデバイスのうちの1つに関連付けられ、その関連付けられる別のデバイスと第1デバイスとの間の相互接続回路を通じて接続を実現するコンピュータプログラム製品であって、方法が、(i)ワイドインターフェースに沿って設けるべき複数のセルを定義するステップであって、別のデバイスのそれぞれが、前記セルのうちの少なくとも1つに関連付けられるステップと、(ii)行および列として形成されたブロックのアレイとして相互接続回路を定義するステップであって、各セルが前記列のうちの1つに当接するステップと、(iii)所定の1組のタイルを設けるステップであって、各タイルが所定の配線レイアウトを提供するステップと、(iv)各ブロックについて、所定の規則を適用して、そのブロックを実装するのに使用すべき前記タイルのうちの1つを決定するステップであって、所定の規則が、アレイ内のブロックの位置、および複数の別のデバイスと複数のセルの間の関連付けを考慮に入れて、相互接続回路によって設けられる各データ経路が同一の伝播遅延を有することを保証するステップとを含むコンピュータプログラム製品を提供する。
第3態様から見ると、本発明は、集積回路についての相互接続回路内のデータ経路のルーティングを求めるシステムにおいて、第1辺上の相互接続回路が、第1デバイスに対する接続のためのナローインターフェースを提供し、第2辺上の相互接続回路が、分散した複数の別のデバイスに対する接続のためのワイドインターフェースを提供し、各データ経路が、前記別のデバイスのうちの1つに関連付けられ、その関連付けられる別のデバイスと第1デバイスとの間の相互接続回路を通じて接続を実現するシステムであって、ワイドインターフェースに沿って設けるべき複数のセルを定義する手段であって、別のデバイスのそれぞれが、前記セルのうちの少なくとも1つに関連付けられる手段と、行および列として形成されたブロックのアレイとして相互接続回路を定義する手段であって、各セルが前記列のうちの1つに当接する手段と、所定の1組のタイルを設ける手段であって、各タイルが所定の配線レイアウトを提供する手段と、各ブロックについて、所定の規則を適用して、そのブロックを実装するのに使用すべき前記タイルのうちの1つを決定するデータ経路決定手段であって、所定の規則が、アレイ内のブロックの位置、および複数の別のデバイスと複数のセルの間の関連付けを考慮に入れて、相互接続回路によって設けられる各データ経路が同一の伝播遅延を有することを保証するデータ経路決定手段とを備えるシステムを提供する。
添付の図面に示される本発明の実施形態を参照しながら、単なる例示として本発明をさらに説明する。
本発明の実施形態の技術を使用して生成される相互接続回路を組み込む集積回路を示す略図である。 相互接続回路内のデータ経路のルーティングを求めるために本発明の一実施形態で使用される方法を示す流れ図である。 本発明の実施形態での相互接続回路に対して使用されるツリー構造を示す略図である。 本発明の一実施形態に従って、相互接続回路内の様々なデータ経路を生成するのに、個々のタイル内の配線レイアウトがどのように使用されるかを示す略図である。 本発明の一実施形態に従って生成される相互接続回路を、左ツリー区間と右ツリー区間を共に含む平衡ツリー構造として示す略図である。 本発明の一実施形態に従って生成される左ツリー区間を示す略図である。 本発明の一実施形態に従って生成される右ツリー区間を示す略図である。 左ツリー区間と右ツリー区間がコーナ素子で分離される、本発明の一実施形態に従って生成される平衡ツリー構造を示す略図である。 右ツリー区間を生成するために本発明の一実施形態に従って使用される方法を概略的に示す流れ図である。 左ツリー区間を生成するために本発明の一実施形態に従って使用される方法を概略的に示す流れ図である。 本発明の一実施形態で使用される所定の1組のタイルを示す図である。 本発明の一実施形態で使用される所定の1組のタイルを示す図である。 本発明の一実施形態で使用される所定の1組のタイルを示す図である。 本発明の一実施形態で使用される所定の1組のタイルを示す図である。 本発明の一実施形態で使用される所定の1組のタイルを示す図である。 本発明の一実施形態で使用される所定の1組のタイルを示す図である。 本発明の一実施形態で使用される所定の1組のタイルを示す図である。 本発明の一実施形態で使用される所定の1組のタイルを示す図である。 本発明の一実施形態で使用される所定の1組のタイルを示す図である。 本発明の一実施形態で使用される所定の1組のタイルを示す図である。 本発明の一実施形態で使用される所定の1組のタイルを示す図である。 本発明の一実施形態で使用される所定の1組のタイルを示す図である。 本発明の一実施形態で使用される所定の1組のタイルを示す図である。 本発明の一実施形態で使用される所定の1組のタイルを示す図である。 本発明の一実施形態で使用される所定の1組のタイルを示す図である。 本発明の一実施形態で使用される所定の1組のタイルを示す図である。 本発明の一実施形態で使用される所定の1組のタイルを示す図である。 本発明の一実施形態で使用される所定の1組のタイルを示す図である。 本発明の一実施形態で使用される所定の1組のタイルを示す図である。 本発明の一実施形態で使用される所定の1組のタイルを示す図である。 本発明の一実施形態で使用される所定の1組のタイルを示す図である。 本発明の一実施形態で使用される所定の1組のタイルを示す図である。 本発明の一実施形態に従って、異なるタイルが当接によってどのように接続されるかを示す図である。 本発明の一実施形態に従って、異なるタイルが当接によってどのように接続されるかを示す図である。 本発明の一実施形態に従って、異なるタイルが当接によってどのように接続されるかを示す図である。 本発明の一実施形態に従って、異なるタイルが当接によってどのように接続されるかを示す図である。 本発明の一実施形態に従って、異なるタイルが当接によってどのように接続されるかを示す図である。 本発明の一実施形態に従って、異なるタイルが当接によってどのように接続されるかを示す図である。 本発明の一実施形態に従って、異なるタイルが当接によってどのように接続されるかを示す図である。 本発明の一実施形態に従って、異なるタイルが当接によってどのように接続されるかを示す図である。 本発明の一実施形態に従って、異なるタイルが当接によってどのように接続されるかを示す図である。 本発明の一実施形態に従って、異なるタイルが当接によってどのように接続されるかを示す図である。 本発明の一実施形態に従って、異なるタイルが当接によってどのように接続されるかを示す図である。 本発明の一実施形態に従って、異なるタイルが当接によってどのように接続されるかを示す図である。 本発明の一実施形態に従って、異なるタイルが当接によってどのように接続されるかを示す図である。 本発明の一実施形態に従って、異なるタイルが当接によってどのように接続されるかを示す図である。 本発明の一実施形態に従って、異なるタイルが当接によってどのように接続されるかを示す図である。 本発明の一実施形態に従って、異なるタイルが当接によってどのように接続されるかを示す図である。 本発明の一実施形態に従って、異なるタイルが当接によってどのように接続されるかを示す図である。 本発明の一実施形態に従って、異なるタイルが当接によってどのように接続されるかを示す図である。 本発明の一実施形態に従って、異なるタイルが当接によってどのように接続されるかを示す図である。 本発明の一実施形態に従って、異なるタイルが当接によってどのように接続されるかを示す図である。 本発明の一実施形態に従って、異なるタイルが当接によってどのように接続されるかを示す図である。 本発明の一実施形態に従って、異なるタイルが当接によってどのように接続されるかを示す図である。 本発明の一実施形態に従って、異なるタイルが当接によってどのように接続されるかを示す図である。 本発明の一実施形態に従って、異なるタイルが当接によってどのように接続されるかを示す図である。 本発明の一実施形態に従って、異なるタイルが当接によってどのように接続されるかを示す図である。 本発明の一実施形態に従って、異なるタイルが当接によってどのように接続されるかを示す図である。 本発明の一実施形態に従って、異なるタイルが当接によってどのように接続されるかを示す図である。 本発明の一実施形態に従って、異なるタイルが当接によってどのように接続されるかを示す図である。 本発明の一実施形態に従って、異なるタイルが当接によってどのように接続されるかを示す図である。 本発明の一実施形態に従って、異なるタイルが当接によってどのように接続されるかを示す図である。 本発明の一実施形態に従って、異なるタイルが当接によってどのように接続されるかを示す図である。 本発明の一実施形態に従って、異なるタイルが当接によってどのように接続されるかを示す図である。 本発明の一実施形態に従って、異なるタイルが当接によってどのように接続されるかを示す図である。 本発明の一実施形態に従って、異なるタイルが当接によってどのように接続されるかを示す図である。 本発明の一実施形態に従って、異なるタイルが当接によってどのように接続されるかを示す図である。 本発明の一実施形態に従って、異なるタイルが当接によってどのように接続されるかを示す図である。 本発明の一実施形態に従って、異なるタイルが当接によってどのように接続されるかを示す図である。 本発明の一実施形態に従って例示的相互接続構造を生成するのに使用されるタイル配置を示す図である。 本発明の一実施形態に従って、相互接続回路に対する様々なデバイスの接続のために様々なタイルがどのように使用されるかを示す図である。 本発明の一実施形態に従って、相互接続回路に対する様々なデバイスの接続のために様々なタイルがどのように使用されるかを示す図である。 本発明の実施形態の技術を実装するコンピュータプログラムを実行することのできる汎用コンピュータのアーキテクチャを示す略図である。
図1は、本発明の実施形態の技術を使用して設計される相互接続回路40を組み込む集積回路60の例示的実施例である。
図1に示されるように、集積回路60の2つの辺に広がる複数のデバイス/構成要素が、相互接続回路40を介して集積回路内のデバイス20に接続される。デバイス30は、相互接続回路40を介してデバイス20に対する接続を必要とするデバイスを含み、図1では、こうしたデバイスが、IO(入力/出力)デバイスと符号が付けられており、さらにデバイス30は、デバイス20に対する接続を必要としない1つまたは複数のデバイスをも含む。図1では、電源構成要素「VDD」34、「VDDA」35、「VSS」36、および「VSSA」37が、デバイス20に対する接続を必要としないそのような構成要素の例である。デバイスの2つの線形分散経路間の接合に、コーナ素子38も設けることができる。
相互接続回路40は、分散したデバイス30に対してワイドインターフェースを提供するが、デバイス20に対してナローインターフェースを提示する。図1に示されるように、デバイス20が集積回路60内に配置された場合に関する柔軟性を向上させるように、相互接続回路40のナローインターフェースからデバイス20に信号をルーティングするルートチャネル50を設けることができる。あるいは、そのようなルートチャネルを必要とすることなく、相互接続回路のナローインターフェースにデバイス20を直接的に接続することもできる。
後でより詳細に説明するように、相互接続回路を設計するとき、いくつかのセル(図1ではパッドとも呼ばれる)が、相互接続回路のワイドインターフェースに沿って設けられ、次いで様々なデバイス/構成要素30のそれぞれが、そうしたセルのうちの少なくとも1つに関連付けられる。一実施形態では、各デバイス30がセルのうちの1つに関連付けられるが、例えばデバイスが単一のセルに関連付けるには大き過ぎる場合、代替実施形態では、デバイスのうちのいくつかを複数のセルに関連付けることができる。
本発明の一実施形態では、相互接続回路内のデータ経路が、トランク部分およびいくつかのブランチ部分を含むツリー構造を採用するように設計される。ツリー構造は、1つまたは複数のツリー区間を含むことができ、例えば左ツリー区間および/または右ツリー区間を含むことができる。図1の実施例では、ツリー構造は、左ツリー区間と右ツリー区間を共に含み、左ツリー区間は、図1に示される点線の左側であり、右ツリー区間は、点線の右側である。各ツリー区間のトランクが、点線の一方の側のセルと位置合せされ、したがって、左ツリー区間のトランクがVDDセル42と位置合せされ、右ツリー区間のトランクがVSSセル44と位置合せされる。
図1に示される実施形態では、左ツリー区間内と右ツリー区間内に等しい数のセル/パッドがある。残りの図を参照しながらより詳細に論じるように、そのような制約を設計に課すことにより、様々なデータ経路が同一の伝播遅延を有する相互接続回路を生成することが容易となる。しかし、代替実施形態では、左ツリー区間と右ツリー区間に対してそれぞれ異なるタイプのタイルが設計される場合、相互接続回路内のすべてのデータ経路が同一の伝播遅延を有することを保証するように、この制約を取り除くことが可能となる。
図1では、デバイス20がメモリコントローラデバイスであり、かつ相互接続回路のワイドインターフェースに沿って設けられた分散した複数のデバイスが、メモリコントローラデバイスによって制御されるIOデバイス32であると仮定する。しかし、伝播遅延が相互接続を介するデータ経路のすべてについて整合される方式で、相互接続を介してデバイスを分散した複数の他のデバイスに結合する必要のある他の任意の相互接続構造に、本発明の実施形態の技術を適用することもできる。
図2は、相互接続回路40内のデータ経路のルーティングを求めるために本発明の一実施形態で使用される方法の略図である。まず、ステップ100で、相互接続回路のワイドインターフェースに沿って設けるべきセルの数が求められる。セルの数は、相互接続回路を通じてデバイス20に接続しなければならないデバイスの数と、収容する必要のある非接続構成要素の数とを考慮して求められる。本発明の一実施形態では、ツリー構造の任意のトランク部分と位置合せされるセルに関連する非接続構成要素があることが要件である。
ステップ100に続いて、ステップ110で、相互接続を表現するブロックのアレイが形成され、アレイは、ブロックの行および列として形成される。次いで、各セルは、アレイ内の列のうちの1つと当接する。したがって、ステップ100で求めたセルの数が、アレイ内に設ける必要のある列数を決定することがわかる。一実施形態では、行数は、ツリー構造の任意の特定のツリー区間内で、列数よりも1つ少なくなるように選ばれる。したがって、全くの例として、ステップ100で求められた100個のセルがあり、相互接続回路が、左ツリー区間および右ツリー区間を有するツリー構造によって形成されるべき場合、各ツリー区間は、50個の列と49個の行を有することになる。
ステップ120で、アレイ内の各ブロックが考慮され、考慮される各ブロックについて、所定の規則が適用され、そのブロックを表現するのに使用すべき所定の複数のタイルからタイルが決定される。後でより詳細に論じるように、所定の1組のタイルが提供され、各タイルは、その中に所定の配線レイアウトを有する。異なるタイルが、相互接続回路内の異なる幅のセル、したがって異なる幅の列に対して提供される。所定の規則は、アレイ内ブロックの位置、および相互接続回路に接続されている複数のデバイス(例えば、図1のIOセル32)と複数のセルの間の関連付けを考慮に入れる(すなわち、そうした様々なデバイスがどのセルに関連付けられるかを考慮に入れる)。この情報に基づいて、所定の規則は、各ブロック位置について適切なタイルを選ぶことができ、その結果、各ブロックが考慮された後は、デバイス20と、IOデバイス32のそれぞれとの間の必要なデータ経路が、相互接続回路内に設けられ、それによって、そうしたデータ経路のそれぞれは同一の伝播遅延を有する。
したがって、ステップ130で示されるように、ステップ120で各ブロックが考慮された後は、相互接続回路についてのレイアウト設計が出力され、必要な各データ経路が、相互接続されたタイルのシーケンスによって形成され、各データ経路は同一の伝播遅延を有する。
図3は、相互接続回路40に対して使用されるツリー構造をより詳細に示す略図である。図示されるように、任意選択のルートチャネル50を介して相互接続ツリー構造40のナローインターフェース160にデバイス20を結合することができる。この例では、相互接続ツリー構造40が、列165によって形成されるトランクと、トランク165の左側に延びる複数のブランチ170、175、180、185、190とを有する左ツリー区間として形成される。この例では、ブロックのアレイが、5個の行および6個の列として構成され、6個の列は、デバイスを関連付けるべき様々なセルに対するワイドインターフェース150を提供する。したがって、この例では、ワイドインターフェースに沿って6個のセルがあり、相互接続に接続すべきデバイス、または相互接続に接続すべきではないデバイス/構成要素が各セルに関連付けられる。
図4は、相互接続ツリー構造40の同じ編成を示すが、タイルが各ブロックに割り振られた後にツリー構造内に生成することのできるデータ経路の略図を示す。前と同様に、任意選択のルートチャネル50が設けられ、デバイス20が相互接続40のナローインターフェースに接続される。図4から理解するであろうが、デバイス20とセル1から5の間に設けられたデータ経路は、それぞれ同一の長さであり、したがって同一の伝播遅延を有する。先に論じたように、相互接続への接続を必要とする任意のデバイスがツリー構造のトランクに当接する位置に配置されないという前述の制約を仮定すると、セル0 200に関連する任意のデバイスを、相互接続40に対する接続を必要としないデバイスとなるように選ぶ必要がある。他のセル205、210、215、220、225に関して、これらはすべて、これらに関連する接続デバイスを有する可能性があり、またはこれらのうちの1つまたは複数が、これらに関連する非接続デバイスを有する可能性がある。
図5は、本発明の一実施形態を使用して生成される相互接続回路構成の一例である。NC(非接続)と符号が付けられた10個のセル260は、相互接続回路を介するデバイス20への接続を必要としない構成要素/デバイスに関連付けるべきセルである。この例は、この相互接続の主なサブコンポーネントを示す。
・ルート50-これは、デバイス20をツリー構造40に接続する。ルートはタイル10および11を使用して構築される。
・ツリー構造40-これは、ルート50を個々のIOセル260に接続する。ツリー構造40は、タイル0L、0R、1L、1R、2L、2R、3L、3R、4L、4R、5L、5R、6L、6R、7L、7R、8L、および8Rを使用して構築される。これが相互接続回路の本体を構成する。
ツリー自体は、2つの区間に分割される。左ツリー区間が、0L、0R、1L、2L、3L、4L、5L、6L、7L、および8Lタイルを使用して構築される。図5では、左ツリー区間は、図の中央の列C=0から、左末端の列C=12までに及ぶ。この区間は、列番号が与えられないコーナ素子250を含む。コーナ素子は、0Lおよび0Rタイルと共に構築される。それぞれの0Lおよび0Rタイルは、その行番号で索引付けされる。図5では、索引が角括弧内に0L[R]および0R[R]として示されており、角括弧内のRは、タイルに関連する行である。
右ツリー区間が、0L、0R、1R、2R、3R、4R、5R、6R、7R、および8Rタイルを使用して構築される。図5では、右ツリー区間は、図の中央の列C=0から、右末端の列C=12にまで及ぶ。図5のこの区間はコーナを含まないが、望むなら、コーナを右ツリー区間のレイアウトに組み込むことができる。
左ツリー区間および右ツリー区間はさらに、2つの部分、すなわちトランクとブランチに分割される。左ツリーブランチおよび右ツリーブランチは、0L、0R、1L、1R、2L、2R、3L、3R、4L、4R、5L、および5Rタイルを使用して構築される。これらは、値C>0を有する列内に含まれる。ツリーブランチは、ツリーの行Rと同じ番号を有する。行が、左ツリー区間と右ツリー区間についてそれぞれ、図の左側下部と右側に示されている。
ツリートランクは、6L、6R、7L、7R、8L、および8Rタイルを使用して構築される。図5では、ツリートランクは、列C=0内のタイルで作成される。
Xと符号が付けられたタイルは「don't care」タイルであり、相互接続回路を生成するときに「don't care」タイルを省略することができ、またはその代わりに、技術によるメタルフィル密度要件を満たすようにメタルフィルセルを含むタイルを使用することができる。
主要なタイプのツリー構成が3つある。左分岐ツリーは左ツリー区間のみを含み、右ツリー区間が省略される。左分岐ツリーはコーナ素子を含む。図6は、そのトランクのナローインターフェースでデバイス20に直接的に接続される左分岐ツリー270の一例を示す。この場合も、IOセル260が各列に関連付けられるように示されており、セルの一部が、相互接続回路のデータ経路に接続すべきデバイスに関連付けられており(IOLセル)、他のセルが、非接続デバイスに関連付けられている(NC IOLセル)。図6の例のこの左分岐ツリーは、コーナ素子またはルートを有さない。
右分岐ツリーは右ツリー区間を含み、左ツリー区間が省略される。左分岐ツリーの場合と同じく、右分岐ツリーはコーナ素子を含むことができる。図7は、コーナ素子またはルートを有さない右分岐ツリー290の一例を示す。やはり、この例では、右分岐ツリー290が、そのトランクのナローインターフェースでデバイス20に直接的に接続され、セル260が各列に関連付けられるように示されている。
平衡ツリーは、例えば図5を参照しながら先に示したように、左ツリー区間と右ツリー区間のどちらも含む。平衡ツリーは、1つが左ツリー区間上、1つが右ツリー区間上の2つのコーナ素子を有することができる。
アングルド平衡ツリーは、左ツリー区間と右ツリー区間の間にコーナ素子を有する、平衡ツリーの特殊なケースである。図8は、アングルド平衡ツリーの一例を示す。アングルド平衡ツリーは、3つのコーナ素子、すなわち左ツリー区間上のコーナ素子、右ツリー区間上のコーナ素子、ならびに左ツリー区間と右ツリー区間の間のコーナ素子を有することができる。図8の例では、アングルド平衡ツリーは、コーナ280によって右ツリー区間290から分離される左ツリー区間270を有する。デバイス20は、タイル9、10、および11で形成されるルート50によってツリーから分離される。先の図5から7の場合と同じく、セル260は、接続されるデバイスまたは非接続デバイスとの関連付けのために、ツリーの各列に関連付けられるように示されている。
上記の例では、任意のツリー区間は、その中に多くとも1つのコーナ素子を有することができることが示されているが、代替実施形態では、各ツリー区間内に複数のコーナ素子を設けることができることを理解されよう。
図9は、右分岐ツリーを構築する一実施形態で使用されるアルゴリズムの流れ図を示す。このアルゴリズムは、平衡ツリーの右ツリー区間を構築するのにも使用される。図10は、左分岐ツリーを構築する一実施形態で使用されるアルゴリズムの流れ図を示す。このアルゴリズムは、平衡ツリーの左ツリー区間を構築するのにも使用される。どちらのアルゴリズムも、以下のパラメータおよび変数を使用する。
N-その値が相互接続回路を介して部分接続されるIOセルの数を表す、所与の構成に対する定数。
CCL-コーナセルがその後ろで具体化されるIOセル列の位置をその値が表す、所与の構成に対する定数。
c-タイルを具体化するために選択された列位置を含む変数。
r-タイルを具体化するために選択された行位置を含む変数。
図9および10では、タイルはGDSタイルと呼ばれる。アルゴリズムは、行rおよび列cの座標を使用することによってタイルのタイプおよびツリー内のタイルの位置を指定することにより、ツリーを構築する。図9および10に示されるアルゴリズムは、「don't care」タイルが使用される場合、「don't care」タイルを具体化しない。図6に示されるように、左分岐ツリーが右から左に構築される。このことは、列c=0が右端の列であり、列c=N-1が左端の列であることを意味する。図7に示されるように、右分岐ツリーが左から右に構築される。このことは、列c=0が左端の列であり、列c=N-1が右端の列であることを意味する。図5に示されるように左分岐ツリーと右分岐ツリーを列c=0で当接させ、または図8に示されるように90°の角度で当接させて共に配置することによって平衡ツリーが構築される。図9および10に示されるアルゴリズムを使用して相互接続回路用に生成されるツリー構造は、以下の制約を有する。
1.すべてのタイル、IOセル、およびデバイス20が、当接によって互いに接続される。
2.素子を当接するとき、相互接続バス(データ経路)に関するビット位置を維持しなければならない。
3.伝播遅延が整合されることを保証するために、左ツリー区間および右ツリー区間に対する平衡ツリーを構築するときの列数が同一でなければならない。
4.列c=0に関連するIOセルを、相互接続を通じてデバイス20に対する接続を必要とするデバイスに関連付けなければならない。
5.コーナが、列番号が与えられないが、(c,r)グリッド位置を有するタイルの後に配置される0Lおよび0Rタイルと共に構築される。
図9および10で定義されるプロセスに続いて、右ツリー区間および左ツリー区間を、先の図で示されるように形成することができる。例えば、図9のプロセスを適用することにより、図7に示される右ツリー区間を生成することができる。この例では、N=11である。位置r=0、c=0で開始すると、プロセスがステップ300、305、310、320、325、330、405を通じてステップ415に進み、このツリー区間上にコーナがないと判定されることがわかる。したがって、プロセスはステップ420に進み、タイル6Rが行0、列0に挿入され、その後でプロセスはステップ400に進む。ステップ400で、列値cが増分され、その後でプロセスは、ステップ325、330、335、350、360を介してステップ370に進む。この時点で、ステップ370で指定される条件が満たされ、プロセスはステップ375に分岐し、タイル1Rが列1、行0に配置され、その後でプロセスはステップ400に戻る。
ステップ400で、値Nに等しい値まで列値が増分されると、プロセスはステップ450に分岐し、行値が増分され、その後で、ステップ320で列値が0にリセットされ、行1のブロック位置のすべてについてプロセスが反復される。ステップ310で、増分された行値がもはやN-1未満ではないと判定されたとき、プロセスはステップ315で終了する。
図10は、左ツリー区間を生成するのに使用される、対応するプロセスを示す。したがって、例えば、図6の左ツリー区間を考慮すると、図6に示されるこのタイル割振りが、図10のプロセスを実施することによって生成される。全くの例として、ブロック位置r=5、c=5を考慮すると、ステップ525から、プロセスは、地点ポイント560まで経路530、535、550をたどる。この地点で、r=5、c=5、およびN=11であるので、ステップ560で指定された条件が満たされる。したがって、プロセスはステップ565に分岐し、図6に明確に示されているように、タイル2Lがグリッド位置に配置される。
図5から8のいずれかに関連して図9および10を同様に検討にすることにより、こうした図に記載のプロセスが図5から8に示されるタイルレイアウトを生成することがわかる。こうしたタイルのそれぞれで設けられる配線レイアウトのために、図9および10のプロセスは、すべて同一の伝播遅延を有する相互接続構造内のデータ経路を生成する。さらに、図9および10から理解できるであろうが、この設計レイアウトプロセスは、タイミング制約を満たすかどうかを確認するための、生成されたレイアウトの評価を必要とせず、したがって、従来技術のEDAツールで一般に必要な反復のいずれも必要としない。
ルート構造は、あらゆる相互接続タイプに対して不要である。デバイス20は、図6および7に示されるように、ツリートランクに直接的に当接することができる。一般には、ルートは、タイル9、10、および11から構築される。左分岐ツリー、右分岐ツリー、および平衡ツリーは、タイル9、10、および11を使用して、ルートをツリーに接続することができる。アングルド平衡ツリーは、タイル9を使用して、ルートをツリーに接続する。図8に示されるように、デバイス20と当接する場所までルートを拡張するのにタイル10および11が使用される。
相互接続ツリー構造が、一緒に配置されたときに当接を通じて接続される1組のタイルから構築される。こうしたタイルを記述するいくつかの共通パラメータが存在する。
N-IO数。このパラメータは、IOリング260の一部となるIOセルの合計数を列挙する。
I-接続されるIO数。このパラメータは、相互接続を通じてデバイス20への接続を必要とするIOセル数を指定する。
P-ポート幅。このパラメータは、IOセルが相互接続を通じてデバイス20に伝播する必要がある最大接続数または最大ビット数を指定する。
Z-最大必要水平金属長。このパラメータは、以下のうちの最長のものを指定する。
1.任意のタイルのイーストポートをウェストポートに接続するのに必要な最長のワイヤ。
2.任意の0Rまたは0Lタイルのイーストポートをウェストポートに接続するのに必要な最長のワイヤの2倍。
V-最大必要垂直金属長。このパラメータは、任意のタイルのノースポートをサウスポートに接続するための最長のワイヤを指定する。
H-タイル高さ。このパラメータは、任意のタイルのイースト側またはウェスト側の幅Pビットの2つのポートを支持するのに必要な最小の高さを指定する。
図11は、例示のためのタイル「0L」の一例である。大部分の実装は、複数の金属層およびバイアを使用して、ポートおよび相互接続配線を作成する。
・タイルは高さHを有する。
・タイル幅は、その行位置に応じて変動する。
・すべてのポート(2、3、4、および5)は、それぞれP個の接続(ビット)を有する。
・相互接続配線6および7は、長さMを有する。ただし
M=0.5*Z
図12は、例示のためのタイル「0R」の一例である。大部分の実装は、複数の金属層およびバイアを使用して、ポートおよび相互接続配線を作成する。
・タイルは高さHを有する。
・タイル幅は、その行位置およびコーナ素子のサイズに応じて変動する。
・すべてのポート(2、3、4、および5)は、それぞれP個の接続(ビット)を有する。
・相互接続配線6および7は、長さMを有する。ただし
M=0.5*Z
左側と右側のタイルが等しい幅を有する場合、水平フリップを使用することにより、所与の行rについてのタイプ0L[r]および0R[r]に対して同一のタイル配線設計を使用することができる。
図13は、例示のためのタイル「1L」の一例である。大部分の実装は、複数の金属層およびバイアを使用して、ポートおよび相互接続配線を作成する。
・タイルは高さHを有する。
・デバイス20への接続を有さないIOセルを含む相互接続回路内で使用される各IOセル幅について、1つのタイルが構築される。
・すべてのポート(2、3、4、5、6、および7)は、それぞれP個の接続(ビット)を有する。
・相互接続配線8および9は、長さMを有する。ただし
M=Z
・相互接続配線10は長さVを有する。
図14は、例示のためのタイル「1R」の一例である。大部分の実装は、複数の金属層およびバイアを使用して、ポートおよび相互接続配線を作成する。
・タイルは高さHを有する。
・相互接続回路内で使用される各IOセル幅について、1つのタイルが構築される。
・すべてのポート(2、3、4、5、6、および7)は、それぞれP個の接続(ビット)を有する。
・相互接続配線8および9は、長さMを有する。ただし
M=Z
・相互接続配線10は長さVを有する。
ノース側とサウス側のポートが垂直対称性を有する場合、水平フリップを使用することにより、タイプ1Lおよび1Rに対して同一のタイル配線設計を使用することができる。
図15は、例示のためのタイル「2L」の一例である。大部分の実装は、複数の金属層およびバイアを使用して、ポートおよび相互接続配線を作成する。
・タイルは高さHを有する。
・相互接続回路内で使用される各IOセル幅について、1つのタイルが構築される。
・すべてのポート(2、3、4、および5)は、それぞれP個の接続(ビット)を有する。
・相互接続配線6は長さMを有する。ただし
M=0.5*Z+0.5*V
・相互接続配線7は長さMを有する。ただし
M=Z
図16は、例示のためのタイル「2R」の一例である。大部分の実装は、複数の金属層およびバイアを使用して、ポートおよび相互接続配線を作成する。
・タイルは高さHを有する。
・相互接続回路内で使用される各IOセル幅について、1つのタイルが構築される。
・すべてのポート(2、3、4、および5)は、それぞれP個の接続(ビット)を有する。
・相互接続配線6は長さMを有する。ただし
M=0.5*Z+0.5*V
・相互接続配線7は長さMを有する。ただし
M=Z
ノース側のポートが垂直対称性を有する場合、水平フリップを使用することにより、タイプ2Lおよび2Rに対して同一のタイル配線設計を使用することができる。
図17は、例示のためのタイル「3L」の一例である。大部分の実装は、複数の金属層およびバイアを使用して、ポートおよび相互接続配線を作成する。
・タイルは高さHを有する。
・相互接続回路内で使用される各IOセル幅について、1つのタイルが構築される。
・すべてのポート(2および3)は、それぞれP個の接続(ビット)を有する。
・相互接続配線4は長さMを有する。ただし
M=2*Z+0.5*V
図18は、例示のためのタイル「3R」の一例である。大部分の実装は、複数の金属層およびバイアを使用して、ポートおよび相互接続配線を作成する。
・タイルは高さHを有する。
・相互接続回路内で使用される各IOセル幅について、1つのタイルが構築される。
・すべてのポート(2および3)は、それぞれP個の接続(ビット)を有する。
・相互接続配線4は長さMを有する。ただし
M=2*Z+0.5*V
水平フリップを使用することにより、タイプ3Lおよび3Rに対して同一のタイル配線設計を使用することができる。
図19は、例示のためのタイル「4L」の一例である。大部分の実装は、複数の金属層およびバイアを使用して、ポートおよび相互接続配線を作成する。
・タイルは高さHを有する。
・相互接続回路内で使用される各IOセル幅について、1つのタイルが構築される。
・すべてのポート(2および3)は、それぞれP個の接続(ビット)を有する。
・相互接続配線4は長さMを有する。ただし
M=Z+0.5*V
図20は、例示のためのタイル「4R」の一例である。大部分の実装は、複数の金属層およびバイアを使用して、ポートおよび相互接続配線を作成する。
・タイルは高さHを有する
・相互接続回路内で使用される各IOセル幅について、1つのタイルが構築される。
・すべてのポート(2および3)は、それぞれP個の接続(ビット)を有する。
・相互接続配線4は長さMを有する。ただし、
M=Z+0.5*V
水平フリップを使用することにより、タイプ4Lおよび4Rに対して同一のタイル配線設計を使用することができる。
図21は、例示のためのタイル「5L」の一例である。大部分の実装は、複数の金属層およびバイアを使用して、ポートおよび相互接続配線を作成する。
・タイルは高さHを有する。
・相互接続回路内で使用される各IOセル幅について、1つのタイルが構築される。
・すべてのポート(2および3)は、それぞれP個の接続(ビット)を有する。
・相互接続配線4は長さMを有する。ただし
M=1.5Z+0.5*V
図22は、例示のためのタイル「5R」の一例である。大部分の実装は、複数の金属層およびバイアを使用して、ポートおよび相互接続配線を作成する。
・タイルは高さHを有する。
・相互接続回路内で使用される各IOセル幅について、1つのタイルが構築される。
・すべてのポート(2および3)は、それぞれP個の接続(ビット)を有する。
・相互接続配線4は長さMを有する。ただし
M=1.5Z+0.5*V
ノース側のポートが垂直対称性を有する場合、水平フリップを使用することにより、タイプ5Lおよび5Rに対して同一のタイル配線設計を使用することができる。
図23は、例示のためのタイル「6L」の一例である。大部分の実装は、複数の金属層およびバイアを使用して、ポートおよび相互接続配線を作成する。
・タイルは高さHを有する。
・タイル幅は、ツリートランク上のIOセル幅と同一である。
・ポート2および3は、S個の接続を有する。ただし
S≧(I-1)*P
・ポート4および5は、S個の接続を有する。ただし
S=P
・相互接続配線6は長さMを有する。ただし
M=V
・相互接続配線7は長さMを有する。ただし
M=Z+0.5*V
図24は、例示のためのタイル「6R」の一例である。大部分の実装は、複数の金属層およびバイアを使用して、ポートおよび相互接続配線を作成する。
・タイルは高さHを有する。
・タイル幅は、ツリートランク上のIOセル幅と同一である。
・ポート2および3は、S個の接続を有する。ただし
S≧(I-1)*P
・ポート4および5は、S個の接続を有する。ただし
S=P
・相互接続配線6は長さMを有する。ただし
M=V
・相互接続配線7は長さMを有する。ただし
M=Z+0.5*V
水平フリップを使用することにより、タイプ6Lおよび6Rに対して同一のタイル配線設計を使用することができる。
図25は、例示のためのタイル「7L」の一例である。大部分の実装は、複数の金属層およびバイアを使用して、ポートおよび相互接続配線を作成する。
・タイルは高さHを有する。
・タイル幅は、ツリートランク上のIOセル幅と同一である。
・ポート2および3は、S個の接続を有する。ただし
S≧I*P
・相互接続配線4は長さMを有する。ただし
M=V
図26は、例示のためのタイル「7R」の一例である。大部分の実装は、複数の金属層およびバイアを使用して、ポートおよび相互接続配線を作成する。
・タイルは高さHを有する。
・タイル幅は、ツリートランク上のIOセル幅と同一である
・ポート2および3は、S個の接続を有する。ただし
S≧I*P
・相互接続配線4は長さMを有する。ただし
M=V
水平フリップを使用することにより、タイプ7Lおよび7Rに対して同一のタイル配線設計を使用することができる。
図27は、例示のためのタイル「8L」の一例である。大部分の実装は、複数の金属層およびバイアを使用して、ポートおよび相互接続配線を作成する。
・タイルは高さHを有する。
・タイル幅は、ツリートランク上のIOセル幅と同一である。
・ポート2および3は、S個の接続を有する。ただし
S≧(I-1)*P
・ポート4および5は、S個の接続を有する。ただし
S=P
・相互接続配線6は長さMを有する。ただし
M=V
・相互接続配線7は長さMを有する。ただし
M=2*Z+0.5*V
図28は、例示のためのタイル「8R」の一例である。大部分の実装は、複数の金属層およびバイアを使用して、ポートおよび相互接続配線を作成する。
・タイルは高さHを有する。
・タイル幅は、ツリートランク上のIOセル幅と同一である。
・ポート2および3は、S個の接続を有する。ただし
S≧(I-1)*P
・ポート4および5は、S個の接続を有する。ただし
S=P
・相互接続配線6は長さMを有する。ただし
M=V
・相互接続配線7は長さMを有する。ただし
M=2*Z+0.5*V
水平フリップを使用することにより、タイプ8Lおよび8Rに対して同一のタイル配線設計を使用することができる。
図29は、例示のためのタイル「9L」の一例である。大部分の実装は、複数の金属層およびバイアを使用して、ポートおよび相互接続配線を作成する。
・タイルは高さTを有する。ただし
Xがツリートランク上のIOセル幅である場合、
T=2*X
・タイルは幅Uを有する。ただし
Xがツリートランク上のIOセル幅である場合、
U=X
・ポート2、3、4、および5は、S個の接続を有する。ただし
S≧(I-1)*P
・相互接続配線6および7は、長さMを有する。ただしMは任意の値でよく、好ましくはタイルに対して可能な最小の長さである。
図30は、例示のためのタイル「9R」の一例である。大部分の実装は、複数の金属層およびバイアを使用して、ポートおよび相互接続配線を作成する。
・タイルは高さTを有する。ただし
Xがツリートランク上のIOセル幅である場合、
T=2*X
・タイルは幅Uを有する。ただし
Xがツリートランク上のIOセル幅である場合、
U=X
・ポート2、3、4、および5は、S個の接続を有する。ただし
S≧(I-1)*P
・相互接続配線6および7は、長さMを有する。ただしMは任意の値でよく、好ましくはタイルに対して可能な最小の長さである。
水平フリップを使用することにより、タイプ9Lおよび9Rに対して同一のタイル配線設計を使用することができる。
図31は、例示のためのタイル「10」の一例である。大部分の実装は、複数の金属層およびバイアを使用して、ポートおよび相互接続配線を作成する。
・タイルは高さTを有する。ただし
Xがツリートランク上のIOセル幅である場合、
T=2*X
・タイルは幅Uを有する。ただし
Xがツリートランク上のIOセル幅である場合、
U=2*X
・ポート2、3、4、および5は、S個の接続を有する。ただし
S≧(I-1)*P
・相互接続配線6および7は、長さMを有する。ただしMは任意の値でよく、好ましくはタイルに対して可能な最小の長さである。
応用例に適合するようにタイル10を回転し、裏返すことができる。
図32は、例示のためのタイル「11」の一例である。大部分の実装は、複数の金属層およびバイアを使用して、ポートおよび相互接続配線を作成する。
・タイルは高さTを有する。ただし
Xがツリートランク上のIOセル幅である場合、
T=2*X
・タイル幅は任意の長さである。幅が短くなるほど、相互接続ルートは、ASIC内にデバイス20をより正確に配置することができる。タイル10の幅を短くすることには、デバイス20を相互接続ツリーから離して配置しなければならないときに、タイル10の多くを使用しなければならないという犠牲が伴う。配置精度をタイル具体化数の削減と組み合わせるために、複数の幅のタイル10を構築することができる。
・ポート2、3、4、および5は、S個の接続を有する。ただし
S≧(I-1)*P
・相互接続配線6および7は、長さMを有する。ただしMは任意の値でよく、好ましくはタイルに対して可能な最小の長さである。
応用例に適合するようにタイル10を回転し、裏返すことができる。
すべてのタイル、IOセル、およびデバイス20は、当接によって接続される。すべてのバスビット順序は、当接するときに常に維持される。図33から69は、相異なるタイルがどのように当接するかについての様々な例を示す。図のリストは網羅的なものではなく、レイアウト内でタイルがどのように共に配置されるかについての広範な概念的例である。
図70は、左ツリー区間および右ツリー区間を有し、各ツリー区間がそれに関連付けられた5個のセルを有する平衡ツリーの比較的単純な例について生成された配線レイアウトを示す。典型的な実施形態では、ワイドインターフェースに沿ってさらに多くのセルが設けられることになり、図70は、例示のために与えられるものに過ぎない。図70からわかるように、様々なタイル内の個々の配線レイアウトが、相互接続を通るデータ経路を提供し、相互接続に接続すべき各IOデバイス32に接続点を提供する。図70の例に示されるように、左ツリー区間内にそのようなIOデバイス32が3個あり、右ツリー区間内にそのようなIOデバイス32が4個ある。個々のタイル内の配線レイアウトを使用して、接続されたIOデバイス32への接続を実現し、または非IOデバイスへの接続を回避することのできる方式が、図71および72に略図で示されている。図71に示されるように、接続する必要のあるIOデバイス32上のピン位置は、隣接するタイル上の必要な配線レイアウトと接続するようなものとなり、接続を必要としないIOデバイスは、そのピンと隣接するタイルの配線レイアウトとが位置合せされない。
同様に、図72では、6Lタイルと6Rタイルの組合せを使用して、デバイス20に対する必要な接続をどのように提供するかを示す。
図73は、上述の技術を実装するのに使用することのできるタイプの汎用コンピュータ700の略図を示す。汎用コンピュータ700は、中央演算処理装置702、ランダムアクセスメモリ704、読取り専用メモリ706、ネットワークインターフェースカード708、ハードディスクドライブ710、ディスプレイドライバ712およびモニタ714、ならびにすべて共通バス722を介して接続されるキーボード718およびマウス720を伴うユーザ入力/出力回路716を含む。動作の際に、中央演算処理装置702は、ランダムアクセスメモリ704、読取り専用メモリ706、およびハードディスクドライブ710のうちの1つまたは複数に格納することができ、またはネットワークインターフェースカード708を介して動的にダウンロードすることのできるコンピュータプログラム命令を実行する。ディスプレイドライバ712およびモニタ714を介して、実行された処理の結果をユーザに表示することができる。キーボード718またはマウス720からユーザ入力/出力回路716を介して、汎用コンピュータ700の動作を制御するユーザ入力を受け取ることができる。コンピュータプログラムを様々なコンピュータ言語で書くことができることを理解されよう。コンピュータプログラムを記録媒体上に格納および配布することができ、または汎用コンピュータ700に動的にダウンロードすることができる。適切なコンピュータプログラムの制御下で動作するとき、汎用コンピュータ700は、相互接続回路内のデータ経路のルーティングを求める上述の技術を実施することができ、汎用コンピュータ700が上述の技術を実施する装置を形成するとみなすことができる。汎用コンピュータ700のアーキテクチャはかなり変動する可能性があり、図73は一例に過ぎない。
本発明の上述の実施形態では、配線レイアウトが不要である任意のブロック位置について、タイルが具体化されない(例えば、図5から8の「x」とマークされたタイルを参照)。しかし、代替実施形態では、所定のタイルの組は、そうしたブロックについてのタイルを具体化するのに使用されるフィラータイルを含むことができる。一実施形態では、こうしたフィラータイルは、所与の製造工程に対する金属密度要件を満たすようにメタルフィルを有する。
さらに、ある実施形態では、IOセルライブラリが、レイアウトが密集することなく(トランクに関して)コーナセルの反対側に設けることのできるブランチ数を限定するショートコーナIOセルを有することがある。一実施形態では、このことを、コーナ素子のどちらかの側にフィラー素子を定義し、次いで所定のタイルの組内に提供される所定のフィラータイルを使用して各フィラー素子を実装することによって軽減することができる。コーナタイルと組み合わせたそのようなフィラータイルは、コーナ素子のサイズを実質上拡張し、コーナ素子の反対側で多数のブランチを必要とするツリー構造を構築することが可能となる。
前述の実施形態では、様々なタイルが、あらゆる可能なセル幅について別々の具体化を有する。しかし、代替実施形態では、フィラーセルの使用により、あらゆる可能なセル幅についてタイルを設ける必要を回避することができる。より具体的には、各IOセルについて同じ幅を有する組合せIOセルライブラリを作成するために、フィラーセルを既存のIOセルと組み合わせることができる。これにより、相互接続回路を構築するために所定のタイルの組内に提供する必要のあるタイル幅の数が著しく削減される。
前述の実施形態では、相互接続回路のツリー構造に接続すべき様々なデバイスが、相互接続回路の関連する列内の隣接するタイルに直接的に接続されるように構成される。しかし、代替実施形態では、こうしたデバイスのピンと、所定のタイルの組の中のタイルの配線レイアウトとの間のピンマッピングを実現する1つまたは複数のブリッジタイルを設けることができる。したがって、こうしたブリッジタイルは、IOデバイスを相互接続ツリーに当接するのに必要なピン位置に適合するように、IOデバイスのピン位置を変換する。こうしたセルはまた、相互接続回路を介する接続を必要としないIOデバイス/構成要素との偶発的当接を回避するように、相互接続回路をデバイスから分離する役割も果たすことができる。こうしたブリッジタイルを使用して、水平フリップによる左側ツリーと右側ツリーについてのタイル配線設計の再利用を可能にする垂直対称性を有するポートを有するIOデバイスインターフェースを作成することもできる。
本発明の実施形態の上記の説明より、そのような実施形態が以下の利点を有することを理解されよう。
1.本発明の実施形態の技術を使用して設計された相互接続回路は、2つの物理ブロックのインターフェース間のサイズ差が非常に大きい場合にその2つの物理ブロックを接続することを可能にする。
2.本発明の実施形態の技術を使用して設計された相互接続回路は、差分信号を効果的に処理することができ、具体的には、本発明の実施形態の対称的ワイヤ長および非励振整合(物理的効果整合)の特性により、差分信号を処理することに特に適している。
3.この技術は、厳密に整合した伝播遅延を実現し、カップリング、漏話、ローディング、雑音遮蔽などの他の物理的側面も整合させることができる。
4.この技術は、様々な幅を有するIOデバイスの混合を扱うことができる。
5.この技術は、コアインターフェースピンおよび信号位置を修正することなく、相互接続を通じて接続されるIOデバイスと、相互接続を通じて接続されないIOデバイス/構成要素との様々な混合を効果的に扱うことができる。
6.前述のルートチャネルの使用により、IOデバイスの配置に関して、どんな場所にもコアインターフェースを配置することができる。
7.この技術は、左コアインターフェース配置、右コアインターフェース配置、および中心コアインターフェース配置に対して、別々の最適化されたトポロジを提供することができる。
8.この技術は、所定の配線レイアウトを有する所定のタイルを使用する構造化ルーティング方法を提供する。
9.少数の所定のレイアウト素子(タイル)のみを用いて多種多様な相互接続を構築することが可能である。
10.本発明の実施形態の技術を使用して構築された相互接続は、厳密な幾何学情報に基づく、事前に特徴付けられたタイミングを有する。
11.この技術はアルゴリズムベースのものであり、フィードフォワード手法に基づいて、様々なバス幅に対して即座にコンパイルすることができる。大部分の周知のASICツールとは異なり、プロセスの反復は不要である。
12.本発明の実施形態の技術を使用して設計された相互接続は通常、従来技術のツールを使用して設計されたものと比較して電力消費が削減される。本技術は、遅延のタイミングおよび整合を改善するためにバッファおよび他の構成要素を様々な経路中に挿入する必要を回避するからである。
本発明の実施形態の技術を、物理的に離れたブロックにバスを接続するときに高度なタイミング整合を必要とするすべての高速バスに適用することができる。本発明の実施形態の技術は、データ経路の物理的幅のサイズが大きく異なる、局所化設計から集積回路上のIOセルにパラレルバスを接続するのに特に適している。SDR、DDRなどのメモリインターフェース、およびPCIなどのパラレルバスアーキテクチャは、本発明の実施形態の技術を使用することから非常に恩恵を受けることのできる技術の主な例である。こうしたアーキテクチャのデータ転送速度が増加するにつれて、本発明の実施形態の技術は特に有益である。
本明細書では本発明の特定の実施形態を説明したが、本発明はその特定の実施形態に限定されず、本発明の範囲内で多数の修正および追加を行えることは明らかであろう。例えば、本発明の範囲から逸脱することなく、以下の従属請求項の特徴の様々な組合せを、独立請求項の特徴と共に作成することができる。
20 デバイス
30 デバイス
32 IOデバイス
34 電源構成要素「VDD」
35 電源構成要素「VDDA」
36 電源構成要素「VSS」
37 電源構成要素「VSSA」
38 電源構成要素コーナ素子
40 相互接続回路
42 VDDセル
44 VSSセル
50 ルートチャネル
60 集積回路
150 ワイドインターフェース
160 ナローインターフェース
165 トランク
170 ブランチ
175 ブランチ
180 ブランチ
185 ブランチ
190 ブランチ
200 セル
205 セル
210 セル
215 セル
220 セル
225 セル
250 コーナ素子
260 IOセル
270 左分岐ツリー
280 コーナ
290 右ツリー区間
700 汎用コンピュータ
702 中央演算処理装置
704 ランダムアクセスメモリ
706 読取り専用メモリ
708 ネットワークインターフェースカード
710 ハードディスクドライブ
712 ディスプレイドライバ
714 モニタ
716 ユーザ入力/出力回路
718 キーボード
720 マウス
722 共通バス

Claims (27)

  1. 集積回路についての相互接続回路内のデータ経路のルーティングを求める方法において、第1辺上の前記相互接続回路が、第1デバイスに対する接続のためのナローインターフェースを提供し、第2辺上の前記相互接続回路が、分散した複数の別のデバイスに対する接続のためのワイドインターフェースを提供し、各データ経路が、前記別のデバイスのうちの1つに関連付けられ、関連付けられる前記別のデバイスと前記第1デバイスとの間の前記相互接続回路を通じて接続を実現する方法であって、
    (i)前記ワイドインターフェースに沿って設けるべき複数のセルを定義するステップであって、前記別のデバイスのそれぞれが、前記セルのうちの少なくとも1つに関連付けられるステップと、
    (ii)行および列として形成されたブロックのアレイとして前記相互接続回路を定義するステップであって、各セルが前記列のうちの1つに当接するステップと、
    (iii)所定の1組のタイルを設けるステップであって、各タイルが所定の配線レイアウトを提供するステップと、
    (iv)各ブロックについて、所定の規則を適用して、前記ブロックを実装するのに使用すべき前記タイルのうちの1つを決定するステップであって、前記所定の規則が、前記アレイ内の前記ブロックの位置、および前記複数の別のデバイスと前記複数のセルの間の関連付けを考慮に入れて、前記相互接続回路によって設けられる各データ経路が同一の伝播遅延を有することを保証するステップと
    を含む方法。
  2. 各データ経路が、タイルのシーケンスによって形成され、前記シーケンス中の各タイルが、前記シーケンスの隣接するタイル内の前記配線レイアウトと少なくとも部分的に当接する配線レイアウトを有するように選択される請求項1に記載の方法。
  3. 前記所定の規則が、ツリー構造を生成するようにタイルを前記アレイ内の個々のブロックに割り振り、少なくとも1つの列が、ツリー構造のトランクとして形成されるナローインターフェースに当接し、残りの列内の前記行が、前記ツリー構造のブランチを形成し、
    前記ステップ(iv)で、前記アレイ内の個々のブロックを実装するのに使用すべきタイルを決定するときに、前記所定の規則が、ブロックが前記ツリー構造の前記トランク内にあるか、それともツリー構造のブランチ内にあるかを考慮に入れる請求項1に記載の方法。
  4. 前記所定のタイルの組が、トランクタイルの所定のサブセットと、ブランチタイルの所定のサブセットとを含み、前記ステップ(iv)中に、各ブロックについて、前記所定の規則が、前記ブロックが前記ツリー構造の前記トランク内にある場合にトランクタイルの前記サブセットからタイルを選択し、または前記ブロックが前記ツリー構造の前記ブランチ内にある場合にブランチタイルの前記サブセットからタイルを選択する請求項3に記載の方法。
  5. セルの数が、前記ワイドインターフェースに接続すべき別のデバイスの数を超過し、それによって、前記別のデバイスのうちの1つに関連付けられない少なくとも1つの非接続セルが存在し、
    前記ツリー構造の前記トランクとして形成された各列について、前記列に当接するように選ばれた前記セルが非接続セルである請求項3に記載の方法。
  6. 前記ツリー構造が、1つまたは複数のツリー区間を含み、各ツリー区間が、前記ナローインターフェースに当接して前記ツリー区間に対するトランクを形成する1つの列を有し、前記ツリー区間の残りの列内の前記行が、前記ツリー区間のブランチを形成する請求項3に記載の方法。
  7. 少なくとも1つのツリー区間が、少なくとも1つの他のツリー区間とは異なる軸上に設けられる請求項6に記載の方法。
  8. 各ツリー区間が、左ツリー区間または右ツリー区間を含み、前記ステップ(iv)で、適用される所定の規則が、タイルが左ツリー区間のブロックについて決定されるか、それとも右ツリー区間のブロックについて決定されるかに依存すると共に、左ツリー区間内であっても、右ツリー区間内であっても、前記相互接続回路によって与えられる各データ経路が同一の伝播遅延を有することを依然として保証する請求項6に記載の方法。
  9. 前記分散した複数の別のデバイスが、少なくとも1つの軸をたどる分散経路に沿って分散する請求項1に記載の方法。
  10. 分散経路中の少なくとも1つの地点で、軸の変化が生じ、
    前記ステップ(ii)で、軸の変化が生じる前記分散経路中の各地点に関連して、前記相互接続回路内にコーナ素子を定義し、それによって各コーナ素子が、前記アレイ内のブロックの2つの隣接する列間の軸の変化を定義するステップと、
    前記ステップ(iv)で、前記所定の規則が、前記所定のタイルの組と共に含まれる所定のコーナタイルを使用して各コーナ素子を実装し、前記アレイ内の各ブロックについて使用すべきタイルを決定するときに、前記所定の規則が、前記相互接続回路によって設けられる各データ経路が同一の伝播遅延を有することを保証するように、前記相互接続回路内の任意のコーナ素子の位置を考慮に入れるステップと
    をさらに含む請求項9に記載の方法。
  11. 前記ステップ(ii)で、前記コーナ素子のどちらかの側にフィラー素子が定義され、前記ステップ(iv)で、前記所定の規則が、前記所定のタイルの組に含まれる所定のフィラータイルを使用して各フィラー素子を実装する請求項10に記載の方法。
  12. セルの数が、前記ワイドインターフェースに接続すべき別のデバイスの数を超過し、それによって、前記別のデバイスのうちの1つに関連付けられない少なくとも1つの非接続セルが存在し、前記相互接続回路に対する接続を必要としない前記集積回路の1つまたは複数の他の構成要素を、1つまたは複数の非接続セルに関連付けるステップをさらに含む請求項1に記載の方法。
  13. 前記他の構成要素が、前記分散した複数の別のデバイスに電力供給するのに使用される電力供給線を備える請求項12に記載の方法。
  14. 前記ステップ(iv)中に、前記所定の規則が、特定のブロックの位置で配線レイアウトが不要であると前記所定の規則が判定した場合、前記ブロックについてタイルが割り振られない請求項1に記載の方法。
  15. 前記所定のタイルの組が、配線レイアウトを有さない1つまたは複数のフィラータイルを含み、前記ステップ(iv)中に、特定のブロックの位置で配線レイアウトが不要であると前記所定の規則が判定した場合、前記フィラータイルのうちの1つが、前記ブロックに対して割り振られる請求項1に記載の方法。
  16. 前記ステップ(i)で、定義される前記複数のセルが、複数の異なる幅であり、前記所定のタイルの組が、各セルが前記列のうちの1つに当接することが可能となるように、対応する複数の異なる幅を有するタイルを含む請求項1に記載の方法。
  17. 前記ステップ(i)で、一定のセルが、初期セルとフィラーセルの組合せによって形成され、それによって前記アレイ内の列と当接する各セルが、等しい幅となる請求項1に記載の方法。
  18. 前記相互接続回路の前記ナローインターフェースから前記第1デバイスまで通るルートチャネルを定義し、それによって前記集積回路内の前記ナローインターフェース以外の位置への第1デバイスの配置を可能にするステップをさらに含む請求項1に記載の方法。
  19. 前記所定のタイルの組が、ルートタイルのサブセットを含み、前記サブセットからの1つまたは複数のルートタイルを使用して前記ルートチャネルを生成するステップをさらに含む請求項18に記載の方法。
  20. 前記分散した複数の別のデバイスが、前記集積回路の周辺に配置された入力/出力デバイスを含む請求項1に記載の方法。
  21. 前記第1デバイスが、前記複数の入力/出力デバイスを制御するのに使用されるメモリコントローラデバイスである請求項20に記載の方法。
  22. 前記別のデバイスのピンと、前記所定のタイルの組の中のタイルの配線レイアウトとの間のピンマッピングを実現する1つまたは複数のブリッジタイルを設けるステップと、
    特定の別のデバイスについて、前記特定の別のデバイスのピンの、当接すべき前記相互接続回路内の前記タイルの前記配線レイアウトに対する直接的マッピングがないとき、前記特定の別のデバイスと前記相互接続回路内の前記タイルとの間に少なくとも1つのブリッジタイルを導入して、前記特定の別のデバイスのピンを前記タイルの前記配線レイアウトにマッピングするステップと
    をさらに含む請求項1に記載の方法。
  23. セルの数が、前記ワイドインターフェースに接続すべき別のデバイスの数を超過し、それによって、前記別のデバイスのうちの1つに関連付けられない少なくとも1つの非接続セルが存在し、ワイドインターフェースに沿った前記非接続セルの追加が、ナローインターフェースの幅に影響を及ぼさない請求項1に記載の方法。
  24. 前記ワイドインターフェースに沿った前記非接続セルの追加が、前記データ経路が前記ナローインターフェースに接続される順序に影響を及ぼさない請求項23に記載の方法。
  25. 前記所定の組の中の前記タイルのうちの少なくとも1つの配線レイアウトが、前記タイルのうちの少なくとも1つが前記アレイ内のブロックを実装するのに使用されるとき、前記タイル内の前記配線レイアウトのすべてが使用されるのではないようなものとなる請求項1に記載の方法。
  26. コンピュータシステム上で実行されたときに、集積回路についての相互接続回路内のデータ経路のルーティングを求める方法を前記コンピュータシステムに実行させるコンピュータプログラムを含むコンピュータプログラム製品において、第1辺上の前記相互接続回路が、第1デバイスに対する接続のためのナローインターフェースを提供し、第2辺上の前記相互接続回路が、分散した複数の別のデバイスに対する接続のためのワイドインターフェースを提供し、各データ経路が、前記別のデバイスのうちの1つに関連付けられ、関連付けられる前記別のデバイスと前記第1デバイスとの間の前記相互接続回路を通じて接続を実現するコンピュータプログラム製品であって、前記方法が、
    (i)前記ワイドインターフェースに沿って設けるべき複数のセルを定義するステップであって、前記別のデバイスのそれぞれが、前記セルのうちの少なくとも1つに関連付けられるステップと、
    (ii)行および列として形成されたブロックのアレイとして前記相互接続回路を定義するステップであって、各セルが前記列のうちの1つに当接するステップと、
    (iii)所定の1組のタイルを設けるステップであって、各タイルが所定の配線レイアウトを提供するステップと、
    (iv)各ブロックについて、所定の規則を適用して、前記ブロックを実装するのに使用すべき前記タイルのうちの1つを決定するステップであって、前記所定の規則が、前記アレイ内の前記ブロックの位置、および前記複数の別のデバイスと前記複数のセルの間の関連付けを考慮に入れて、前記相互接続回路によって設けられる各データ経路が同一の伝播遅延を有することを保証するステップと
    を含むコンピュータプログラム製品。
  27. 集積回路についての相互接続回路内のデータ経路のルーティングを求めるシステムにおいて、第1辺上の前記相互接続回路が、第1デバイスに対する接続のためのナローインターフェースを提供し、第2辺上の前記相互接続回路が、分散した複数の別のデバイスに対する接続のためのワイドインターフェースを提供し、各データ経路が、前記別のデバイスのうちの1つに関連付けられ、関連付けられる前記別のデバイスと前記第1デバイスとの間の前記相互接続回路を通じて接続を実現するシステムであって、
    前記ワイドインターフェースに沿って設けるべき複数のセルを定義する手段であって、前記別のデバイスのそれぞれが、前記セルのうちの少なくとも1つに関連付けられる手段と、
    行および列として形成されたブロックのアレイとして前記相互接続回路を定義する手段であって、各セルが前記列のうちの1つに当接する手段と、
    所定の1組のタイルを設ける手段であって、各タイルが所定の配線レイアウトを提供する手段と、
    各ブロックについて、所定の規則を適用して、前記ブロックを実装するのに使用すべき前記タイルのうちの1つを決定するデータ経路決定手段であって、前記所定の規則が、前記アレイ内の前記ブロックの位置、および前記複数の別のデバイスと前記複数のセルの間の関連付けを考慮に入れて、前記相互接続回路によって設けられる各データ経路が同一の伝播遅延を有することを保証するデータ経路決定手段と
    を備えるシステム。
JP2009120244A 2008-05-19 2009-05-18 相互接続回路内のデータ経路のルーティングを求める方法、システム、およびコンピュータプログラム製品 Expired - Fee Related JP5241603B2 (ja)

Applications Claiming Priority (2)

Application Number Priority Date Filing Date Title
US12/153,448 2008-05-19
US12/153,448 US8024690B2 (en) 2008-05-19 2008-05-19 Method, system and computer program product for determining routing of data paths in interconnect circuitry providing a narrow interface for connection to a first device and a wide interface for connection to a distributed plurality of further devices

Publications (2)

Publication Number Publication Date
JP2009282976A true JP2009282976A (ja) 2009-12-03
JP5241603B2 JP5241603B2 (ja) 2013-07-17

Family

ID=40671785

Family Applications (1)

Application Number Title Priority Date Filing Date
JP2009120244A Expired - Fee Related JP5241603B2 (ja) 2008-05-19 2009-05-18 相互接続回路内のデータ経路のルーティングを求める方法、システム、およびコンピュータプログラム製品

Country Status (5)

Country Link
US (1) US8024690B2 (ja)
JP (1) JP5241603B2 (ja)
CN (1) CN101587508B (ja)
GB (1) GB2460142B (ja)
TW (1) TWI454950B (ja)

Families Citing this family (22)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US8122419B2 (en) * 2008-11-09 2012-02-21 International Business Machines Corporation System and method for three-dimensional variational capacitance calculation
US8341582B2 (en) * 2009-01-30 2012-12-25 Active-Semi, Inc. Programmable analog tile configuration tool
US8219956B2 (en) * 2009-01-30 2012-07-10 Active-Semi, Inc. Analog tile selection, placement, configuration and programming tool
US8225260B2 (en) 2009-01-30 2012-07-17 Active-Semi, Inc. Programmable analog tile placement tool
US8079007B2 (en) * 2009-01-30 2011-12-13 Active-Semi, Inc. Programmable analog tile programming tool
US9003340B2 (en) * 2009-01-30 2015-04-07 Active-Semi, Inc. Communicating configuration information across a programmable analog tile to another tile
US8527929B2 (en) * 2009-12-23 2013-09-03 Cadence Design Systems, Inc. Method and system for optimally connecting interfaces across multiple fabrics
US8479134B2 (en) * 2009-12-23 2013-07-02 Cadence Design Systems, Inc. Method and system for specifying system level constraints in a cross-fabric design environment
US8386981B1 (en) 2010-04-12 2013-02-26 Cadence Design Systems, Inc. Method and systems for implementing I/O rings and die area estimations
US9135373B1 (en) 2010-04-12 2015-09-15 Cadence Design Systems, Inc. Method and system for implementing an interface for I/O rings
US8832629B2 (en) * 2010-07-23 2014-09-09 Freescale Semiconductor, Inc. Method for optimising cell variant selection within a design process for an integrated circuit device
US8510702B2 (en) * 2011-11-15 2013-08-13 Texas Instruments Incorporated Interactive routing editor with symbolic and geometric views for integrated circuit layout
US11157676B2 (en) * 2016-09-20 2021-10-26 Octavo Systems Llc Method for routing bond wires in system in a package (SiP) devices
US10503859B2 (en) * 2017-08-30 2019-12-10 Arm Limited Integrated circuit design and/or fabrication
US10817641B1 (en) 2017-09-29 2020-10-27 Cadence Design Systems, Inc. Method and system to implement topology integrity throughout routing implementations
US10521097B1 (en) 2017-09-29 2019-12-31 Cadence Design Systems, Inc. User interface to implement topology integrity throughout routing implementations
US10489549B1 (en) * 2017-12-22 2019-11-26 Cadence Design Systems, Inc. Tree-routing for specific areas of an electronic design
US10551431B1 (en) 2017-12-22 2020-02-04 Cadence Design Systems, Inc. EM-compliance topology in a tree router
US11309306B2 (en) 2018-09-28 2022-04-19 Taiwan Semiconductor Manufacturing Company, Ltd. Stack-gate circuit
GB2580165B (en) * 2018-12-21 2021-02-24 Graphcore Ltd Data exchange in a computer with predetermined delay
US11151298B1 (en) * 2019-11-21 2021-10-19 Xilinx, Inc. Metal track routing with buffer bank insertion
US11604751B1 (en) * 2021-05-10 2023-03-14 Xilinx, Inc. Optimizing hardware design throughput by latency aware balancing of re-convergent paths

Citations (6)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JPH05334398A (ja) * 1992-05-29 1993-12-17 Yokogawa Electric Corp プリント基板ｃａｄの自動配線機構
JPH0621223A (ja) * 1992-07-06 1994-01-28 Toshiba Corp 半導体集積回路の自動配線方法
JPH06349947A (ja) * 1993-06-14 1994-12-22 Fujitsu Ltd 半導体集積回路装置のマスクパターン設計方法および設計装置
JP2001085528A (ja) * 1999-09-14 2001-03-30 Toshiba Microelectronics Corp 半導体集積回路の設計方法および半導体集積回路の製造方法
JP2005026537A (ja) * 2003-07-04 2005-01-27 Cadence Design Systems Inc 集積回路及び集積回路のレイアウト方法
WO2007073599A1 (en) * 2005-12-29 2007-07-05 Mosaid Technologies Incorporated Asic design using clock and power grid standard cell

Family Cites Families (17)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US5118300A (en) * 1991-05-23 1992-06-02 Amp Incorporated Active electrical connector
US6279142B1 (en) * 1998-10-02 2001-08-21 International Business Machines Corporation Method of on-chip interconnect design
US6654712B1 (en) * 2000-02-18 2003-11-25 Hewlett-Packard Development Company, L.P. Method to reduce skew in clock signal distribution using balanced wire widths
US6571380B2 (en) * 2001-07-12 2003-05-27 Micron Technology, Inc. Integrated circuit with layout matched high speed lines
US6735754B2 (en) * 2002-06-06 2004-05-11 Sun Microsystems, Inc. Method and apparatus to facilitate global routing for an integrated circuit layout
WO2004004008A1 (en) * 2002-06-28 2004-01-08 Koninklijke Philips Electronics N.V. Integrated circuit having building blocks
US7375553B1 (en) * 2003-05-28 2008-05-20 Actel Corporation Clock tree network in a field programmable gate array
US7132851B2 (en) * 2003-07-11 2006-11-07 Xilinx, Inc. Columnar floorplan
JP4620942B2 (ja) * 2003-08-21 2011-01-26 川崎マイクロエレクトロニクス株式会社 半導体集積回路のレイアウト方法、そのレイアウト構造、およびフォトマスク
US7213221B1 (en) * 2004-04-19 2007-05-01 Magma Design Automation, Inc. Modeling interconnected propagation delay for an integrated circuit design
US7126406B2 (en) * 2004-04-30 2006-10-24 Xilinx, Inc. Programmable logic device having an embedded differential clock tree
US7418689B2 (en) * 2005-04-27 2008-08-26 International Business Machines Corporation Method of generating wiring routes with matching delay in the presence of process variation
US7312631B1 (en) * 2005-11-01 2007-12-25 Xilinx, Inc. Structures and methods for avoiding hold time violations in a programmable logic device
US20080074142A1 (en) * 2006-09-25 2008-03-27 Alex Henderson Routing for Microprocessor Busses
US7739095B2 (en) * 2007-03-13 2010-06-15 Synopsys, Inc. Method for determining best and worst cases for interconnects in timing analysis
US7570079B2 (en) * 2007-04-17 2009-08-04 Mihai Sima Level-restoring buffers for programmable interconnect circuits and method for building the same
US20090217225A1 (en) * 2008-02-22 2009-08-27 Mentor Graphics, Corp. Multi-mode multi-corner clocktree synthesis

Patent Citations (6)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JPH05334398A (ja) * 1992-05-29 1993-12-17 Yokogawa Electric Corp プリント基板ｃａｄの自動配線機構
JPH0621223A (ja) * 1992-07-06 1994-01-28 Toshiba Corp 半導体集積回路の自動配線方法
JPH06349947A (ja) * 1993-06-14 1994-12-22 Fujitsu Ltd 半導体集積回路装置のマスクパターン設計方法および設計装置
JP2001085528A (ja) * 1999-09-14 2001-03-30 Toshiba Microelectronics Corp 半導体集積回路の設計方法および半導体集積回路の製造方法
JP2005026537A (ja) * 2003-07-04 2005-01-27 Cadence Design Systems Inc 集積回路及び集積回路のレイアウト方法
WO2007073599A1 (en) * 2005-12-29 2007-07-05 Mosaid Technologies Incorporated Asic design using clock and power grid standard cell

Also Published As

Publication number Publication date
GB0905240D0 (en) 2009-05-13
CN101587508A (zh) 2009-11-25
TWI454950B (zh) 2014-10-01
CN101587508B (zh) 2013-01-02
TW200949592A (en) 2009-12-01
GB2460142B (en) 2012-05-02
GB2460142A (en) 2009-11-25
US8024690B2 (en) 2011-09-20
US20090288056A1 (en) 2009-11-19
JP5241603B2 (ja) 2013-07-17

Similar Documents

Publication Publication Date Title
JP5241603B2 (ja) 相互接続回路内のデータ経路のルーティングを求める方法、システム、およびコンピュータプログラム製品
CN109426695B (zh) 集成电路设计和/或制造
US11625522B2 (en) Method and apparatus for generating three-dimensional integrated circuit design
US6308309B1 (en) Place-holding library elements for defining routing paths
US5665989A (en) Programmable microsystems in silicon
CN107918694B (zh) 用于减少集成电路上的延迟的方法
EP3040888A2 (en) Integrated circuit layout wiring for multi-core chips
US10068048B1 (en) Generating clock trees for a circuit design
US9026967B1 (en) Method and apparatus for designing a system on multiple field programmable gate array device types
US6434731B1 (en) Automated placement of signal distribution to diminish skew among same capacitance targets in integrated circuits
US9852255B2 (en) Method and apparatus for implementing periphery devices on a programmable circuit using partial reconfiguration
US9740808B2 (en) Method and apparatus for implementing a system-level design tool for design planning and architecture exploration
US8397190B2 (en) Method for manipulating and repartitioning a hierarchical integrated circuit design
US6425115B1 (en) Area efficient delay circuits
CN117764024A (zh) 一种基于h树的时钟树综合优化方法
US6260175B1 (en) Method for designing an integrated circuit using predefined and preverified core modules having prebalanced clock trees
US7873934B1 (en) Method and apparatus for implementing carry chains on field programmable gate array devices
KR102527749B1 (ko) 3d 집적 회로용 폴딩 블록들 및 복제 핀들을 갖는 지적 재산 블록 설계
JPH0677403A (ja) 半導体集積回路装置及びその設計方法
TW201837760A (zh) 用於產生積體電路的電路模塊的佈局的技術
KR20250048107A (ko) 복제된 어레이들에서의 클럭 타이밍
CN1862968B (zh) 集成电路以及设计集成电路的方法
JP2004094402A (ja) 遅延シミュレーション用ネットリスト生成システムおよび遅延シミュレーション用ネットリスト生成方法
US8065648B1 (en) Method and apparatus for modeling an integrated circuit in a computer aided design system
CN117851146A (zh) 针对小芯片的fpga原型验证系统和原型验证方法

Legal Events

Date Code Title Description
A621 Written request for application examination

Free format text: JAPANESE INTERMEDIATE CODE: A621

Effective date: 20111011

A977 Report on retrieval

Free format text: JAPANESE INTERMEDIATE CODE: A971007

Effective date: 20120904

A131 Notification of reasons for refusal

Free format text: JAPANESE INTERMEDIATE CODE: A131

Effective date: 20120925

A521 Request for written amendment filed

Free format text: JAPANESE INTERMEDIATE CODE: A523

Effective date: 20121225

TRDD Decision of grant or rejection written
A01 Written decision to grant a patent or to grant a registration (utility model)

Free format text: JAPANESE INTERMEDIATE CODE: A01

Effective date: 20130305

A61 First payment of annual fees (during grant procedure)

Free format text: JAPANESE INTERMEDIATE CODE: A61

Effective date: 20130402

FPAY Renewal fee payment (event date is renewal date of database)

Free format text: PAYMENT UNTIL: 20160412

Year of fee payment: 3

R150 Certificate of patent or registration of utility model

Free format text: JAPANESE INTERMEDIATE CODE: R150

R250 Receipt of annual fees

Free format text: JAPANESE INTERMEDIATE CODE: R250

LAPS Cancellation because of no payment of annual fees