(57)【要約】      （修正有）【課題】開発後期ステージのタイミング再調整は、レジスタ再配置に関連する困難性のゆえ、柔軟性が制限される。そこで、高レベルの正確さおよび配置段階後にルーティング経路を変更する柔軟性を与える、タイミング再調整の新方法を提供する。【解決手段】再構成可能な回路における２つの論理要素間の最長遅延経路を最小化し、各論理要素は１つのレジスタに関連付けられ、このレジスタはトランスペアレントであるようにプログラミングされる方法であって、関連付けられた特定のレジスタを介して、２つの論理要素を接続することが可能なルーティング経路であり、トランスペアレントであるようにプログラミングされたレジスタを通過する経路を含むルーティング経路の数を決定し、トランスペアレントであるようにプログラミングされたレジスタを、各ルーティング経路が通過するかどうかを含むルーティング経路判断基準に基づいて、ルーティング経路を選択する方法。【選択図】図６
2009238221.tif 000002
【特許請求の範囲】
【請求項１】
再構成可能な装置において配置された回路における２つの論理要素間の最長遅延経路を最小化し、各論理要素は１つのレジスタに関連付けられ、前記再構成可能な装置は論理要素および関連付けられたレジスタを含み、前記関連付けられたレジスタはトランスペアレントであるようにプログラミングされる、方法であって、
前記２つの論理要素のうちの１つに関連付けられた特定のレジスタを介して、前記回路における前記２つの論理要素を接続することが可能なルーティング経路であって、トランスペアレントであるようにプログラミングされた少なくとも１つのレジスタを通過する少なくとも１つの経路を含むルーティング経路の数を決定するステップと、
トランスペアレントであるようにプログラミングされたレジスタを、各ルーティング経路が通過するかどうかを含む少なくとも１つのルーティング経路判断基準に基づいて、ルーティング経路を選択するステップと、
前記各トランスペアレントレジスタを起動し前記特定のレジスタをトランスペアレントにするようにプログラミングすることにより、前記２つの論理要素間の前記最長遅延が低減される程度によって、前記選択された経路がルーティングされる前記各トランスペアレントレジスタに対して、計算するステップと、
前記最長遅延における前記低減量を、もしあれば、どのトランスペアレントレジスタが最大化するのかを、前記計算するステップの前記結果に基づいて決定するステップと、
前記決定するステップにおいて１つのトランスペアレントレジスタが決定される場合、前記決定されたトランスペアレントレジスタを有効にするようにプログラミングし、前記特定のレジスタをトランスペアレントにするようにプログラミングするステップと、を有する方法。
【請求項２】
前記少なくとも１つのルーティング経路判断基準は、各経路における前記全遅延を含む、請求項１に記載の方法。
【請求項３】
前記少なくとも１つのルーティング経路判断基準は、各ルーティング経路の混雑状態を含む、請求項１または２のいずれか１つに記載の方法。
【請求項４】
さらに、前記最大遅延経路に基づいて前記回路の最高周波数を設定するステップを有する、請求項１から３のいずれか１つに記載の方法。
【請求項５】
前記決定されたトランスペアレントレジスタを有効にするようにプログラミングし、特定のレジスタをトランスペアレントにするようにプログラミングするステップは、
前記特定のトランスペアレントレジスタをルート貫通レジスタとして構成するステップと、
前記決定されたトランスペアレントレジスタをクロック制御レジスタとして構成するステップと、を含む、請求項１から４のいずれか１つに記載の方法。
【請求項６】
前記再構成可能な装置は、フィールドプログラム可能ゲートアレイ（ＦＰＧＡ）回路である、請求項１から５のいずれか１つに記載の方法。
【請求項７】
再構成可能な装置において配置された回路における２つの論理要素間の最長遅延経路を最小化し、各論理要素は１つのレジスタに関連付けられ、前記再構成可能な装置は論理要素および関連付けられたレジスタを含み、前記関連付けられたレジスタはトランスペアレントであるようにプログラミングされる、装置であって、
前記２つの論理要素のうちの１つに関連付けられた特定のレジスタを介して、前記回路における前記２つの論理要素を接続することが可能なルーティング経路であって、トランスペアレントであるようにプログラミングされた少なくとも１つのレジスタを通過する少なくとも１つの経路を含むルーティング経路の数を決定する経路決定手段と、
トランスペアレントであるようにプログラミングされたレジスタを、各ルーティング経路が通過するかどうかを含む少なくとも１つのルーティング経路判断基準に基づいて、ルーティング経路を選択する選択手段と、
前記各トランスペアレントレジスタを起動し前記特定のレジスタをトランスペアレントにするようにプログラミングすることにより、前記２つの論理要素間の前記最長遅延が低減される程度によって、前記選択された経路がルーティングされる前記各トランスペアレントレジスタに対して、計算する計算手段と、
前記最長遅延における前記低減量を、もしあれば、どのトランスペアレントレジスタが最大化するのかを、前記計算手段によりなされる計算、決定するトランスペアレントレジスタ決定手段と、
前記トランスペアレントレジスタ決定手段により１つのトランスペアレントレジスタが決定される場合、前記決定されたトランスペアレントレジスタを有効にするようにプログラミングし、前記特定のレジスタをトランスペアレントにするようにプログラミングするプログラミング手段と、を有する装置。
【請求項８】
前記少なくとも１つのルーティング経路判断基準は、各経路における全遅延を含む、請求項７に記載の装置。
【請求項９】
前記少なくとも１つのルーティング経路判断基準は、各ルーティング経路における混雑状態を含む、請求項７または８のいずれか１つに記載の装置。
【請求項１０】
さらに、前記最大遅延経路に基づいて前記回路の最高周波数を設定する設定手段を有する、請求項７から９のいずれか１つに記載の装置。
【請求項１１】
前記プログラミング手段は、
前記特定のトランスペアレントレジスタをルート貫通レジスタとして構成する構成手段と、
前記決定されたトランスペアレントレジスタをクロック制御レジスタとして構成する構成手段と、を含む、請求項７から１０のいずれか１つに記載の装置。
【請求項１２】
前記再構成可能な装置は、フィールドプログラム可能ゲートアレイ（ＦＰＧＡ）回路である、請求項７から１１のいずれか１つに記載の装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、プログラム可能アーキテクチャ上に実装されたハードウェア構成を最適化する装置および方法を与えることにより、再構成可能な論理装置の構成を最適化することに関する。
【０００２】
ある種の再構成可能な装置／構造は、一般に、単一のユーザプログラム可能論理タイルからなる多数の実体から構成される。これらのタイルは、特定の再構成可能な装置／構造を用いて設計される、あらゆる論理回路の基本となるビルディングブロックを表す。
【０００３】
これらのタイルの１つは、典型的には算術論理ユニット（ＡＬＵ）またはマルチプレクサなどの論理要素と関連付けられたレジスタを有する。特定の機能を実行するために、これらのタイルは、特定の仕方で相互接続される必要がある。これらのタイルが相互接続される方法に関する情報は、ネットリストとして知られているものに含まれている。
【０００４】
再構成可能な装置／構造上へマッピングされる構成の性能を最大化するために、いずれか２つのレジスタ間の最長経路が最小化されるように、各レジスタセルの最適な配置を見つけることが重要である。性能、面積、および／または電力特性を改善するために、デジタル回路におけるラッチまたはレジスタの構造的配置を移動するこの技術は、「タイミング再調整」として知られている。タイミング再調整のアプローチはいくつか知られており、そのほとんどは、タイミング再調整アルゴリズムまたは加重タイミング再調整機能の使用に基づいている。
【０００５】
タイミング再調整の最初のアプローチは、開発における合成ステージの間に、タイミング再調整アルゴリズムを用いることから成る。この時点で、ネットリストはまだ装置／構造上に配置されていないので、相互接続遅延は、最初に数学的モデルを用いて見積もられる必要がある。次に、レジスタ間の経路の長さが、各論理セルの測定遅延および見積もられた相互接続遅延を用いて計算される。最後に、これらの長さがタイミング再調整アルゴリズムにより使用され、構造上へ要素が配置される。この技術は、全体として、相互接続遅延を見積もるのに使用されるモデルの正確さに依存するという不利を招く。非効率的なまたは不正確なモデルは、非効率的な構成を選択するアルゴリズムの原因になる可能性がある。
【発明の概要】
【発明が解決しようとする課題】
【０００６】
この課題に対する解決法を与えるために、回路設計の配置ステージの間にタイミング再調整を実行することを含む技術が開発された。このアプローチでは、タイミング再調整アルゴリズムは、各配置の繰り返し後に実行され、その時点でレジスタは、レジスタ間の経路を最適化するように再構成可能となる。この技術の１つの意味深い有利な点は、相互接続遅延を決定するのに使用されるモデルが、所定量の配置情報を計算に組み込んでもよいことである。この配置情報は、合成ステージにおいて入手可能ではなかったデータである。それゆえに、このモデルは、依然としてルーティング遅延の見積もりに部分的に頼っているにもかかわらず、開発における合成ステージで使用されるモデルよりも正確である。しかしながら、この新モデルを使用するタイミング再調整アルゴリズムは、レジスタの新配列が容易に配置可能でなくてもよく、それによって、いずれか１つの繰り返しの間に見つけられる最適な配置解を無効にする可能性を増加させるという事実によって制約される。
【０００７】
さらに、タイミング再調整過程の正確さを増大させるために、ルーティングステージにおいてレジスタタイミング再調整が実行されるような技術が開発されてきた。このシナリオにおいて、実際のすべてのルーティング情報は、レジスタ間の経路が固定されている点で知られている。したがって、この技術は、相互接続遅延を決定するために、モデルの使用必要としていない。しかしながら、このステージにおいて、レジスタ配置が修正可能ではないので、タイミング再調整は回路の性能上に、ほとんどまたはまったく影響しない。
【０００８】
それゆえに、上述した技術のそれぞれは、特定の不利な点を招く。タイミング再調整技術は、開発における早期のステージにおいてレジスタ位置の点ではより大きい柔軟性を与えるにもかかわらず、近似のタイミング調整モデルを使用しなければならないという不利な点を招く。反対に、後のステージにおけるタイミング再調整は、さらに正確なタイミング調整データを与えるが、しかしレジスタを再配置することに関連する困難性のゆえに、柔軟性が制限される。
【０００９】
したがって、タイミング調整における高レベルの正確さおよび配置段階後にルーティング経路を変更する柔軟性を与える、タイミング再調整の新方法が、明らかに必要となっている。
【課題を解決するための手段】
【００１０】
上述した課題を解決するために、本発明は、再構成可能な装置において配置された回路における２つの論理要素間の最長遅延経路を最小化し、各論理要素は１つのレジスタに関連付けられ、前記再構成可能な装置は論理要素および関連付けられたレジスタを含み、前記関連付けられたレジスタはトランスペアレントであるようにプログラミングされる、方法であって、前記２つの論理要素のうちの１つに関連付けられた特定のレジスタを介して、前記回路における前記２つの論理要素を接続することが可能なルーティング経路であって、トランスペアレントであるようにプログラミングされた少なくとも１つのレジスタを通過する少なくとも１つの経路を含むルーティング経路の数を決定するステップと、トランスペアレントであるようにプログラミングされたレジスタを、各ルーティング経路が通過するかどうかを含む少なくとも１つのルーティング経路判断基準に基づいて、ルーティング経路を選択するステップと、前記各トランスペアレントレジスタを起動し前記特定のレジスタをトランスペアレントにするようにプログラミングすることにより、前記２つの論理要素間の前記最長遅延が低減される程度によって、前記選択された経路がルーティングされる前記各トランスペアレントレジスタに対して、計算するステップと、前記最長遅延における前記低減量を、もしあれば、どのトランスペアレントレジスタが最大化するのかを、前記計算するステップの前記結果に基づいて決定するステップと、前記決定するステップにおいて１つのトランスペアレントレジスタが決定される場合、前記決定されたトランスペアレントレジスタを有効にするようにプログラミングし、前記特定のレジスタをトランスペアレントにするようにプログラミングするステップと、を有する方法を与える。
【００１１】
好ましくは、前記少なくとも１つのルーティング経路判断基準は、各経路における前記全遅延を含む。
【００１２】
好ましくは、前記少なくとも１つのルーティング経路判断基準は、各ルーティング経路の混雑状態を含む。
【００１３】
好ましくは、さらに、前記最大遅延経路に基づいて前記回路の最高周波数を設定するステップを有する。
【００１４】
好ましくは、前記決定されたトランスペアレントレジスタを有効にするようにプログラミングし、特定のレジスタをトランスペアレントにするようにプログラミングするステップは、前記特定のトランスペアレントレジスタをルート貫通レジスタとして構成するステップと、前記決定されたトランスペアレントレジスタをクロック制御レジスタとして構成するステップと、を含む。
【００１５】
さらに、本発明は、再構成可能な装置において配置された回路における２つの論理要素間の最長遅延経路を最小化し、各論理要素は１つのレジスタに関連付けられ、前記再構成可能な装置は論理要素および関連付けられたレジスタを含み、前記関連付けられたレジスタはトランスペアレントであるようにプログラミングされる、装置であって、前記２つの論理要素のうちの１つに関連付けられた特定のレジスタを介して、前記回路における前記２つの論理要素を接続することが可能なルーティング経路であって、トランスペアレントであるようにプログラミングされた少なくとも１つのレジスタを通過する少なくとも１つの経路を含むルーティング経路の数を決定する経路決定手段と、トランスペアレントであるようにプログラミングされたレジスタを、各ルーティング経路が通過するかどうかを含む少なくとも１つのルーティング経路判断基準に基づいて、ルーティング経路を選択する選択手段と、前記各トランスペアレントレジスタを起動し前記特定のレジスタをトランスペアレントにするようにプログラミングすることにより、前記２つの論理要素間の前記最長遅延が低減される程度によって、前記選択された経路がルーティングされる前記各トランスペアレントレジスタに対して、計算する計算手段と、前記最長遅延における前記低減量を、もしあれば、どのトランスペアレントレジスタが最大化するのかを、前記計算手段によりなされる計算、決定するトランスペアレントレジスタ決定手段と、前記トランスペアレントレジスタ決定手段により１つのトランスペアレントレジスタが決定される場合、前記決定されたトランスペアレントレジスタを有効にするようにプログラミングし、前記特定のレジスタをトランスペアレントにするようにプログラミングするプログラミング手段と、を有する装置を与える。
【００１６】
好ましくは、前記少なくとも１つのルーティング経路判断基準は、各経路における全遅延を含む。
【００１７】
好ましくは、前記少なくとも１つのルーティング経路判断基準は、各ルーティング経路における混雑状態を含む。
【００１８】
好ましくは、さらに、前記最大遅延経路に基づいて前記回路の最高周波数を設定する設定手段を有する。
【００１９】
好ましくは、前記プログラミング手段は、前記特定のトランスペアレントレジスタをルート貫通レジスタとして構成する構成手段と、前記決定されたトランスペアレントレジスタをクロック制御レジスタとして構成する構成手段と、を含む。
【００２０】
前記再構成可能な装置は、フィールドプログラム可能ゲートアレイ（ＦＰＧＡ）回路であってもよい。
【発明の効果】
【００２１】
好ましいことに、本発明はいくつかの有利な点を与える。たとえば、本発明が配置およびルーティング段階の後で実装することが可能な解を与えるので、正確なタイミング調整情報および遅延情報が入手可能となる。本発明は、レジスタを物理的に移動することを含まない。代わりに、本発明の方法は、トランスペアレントフラグを用いてレジスタの起動状態を効果的に交換する。それゆえに、本発明が未使用のレジスタを使用するので、回路のタイミング再調整が従来のレジスタに対して最小限の混乱で成し遂げられ、回路における最長遅延経路は最小化される。したがって、本発明は、柔軟性および有効性を増大させるタイミング再調整方法およびシステムを与え、論理回路はさらに効果的に最適化される。これらの有利な点は、本発明の方法に従って設計された回路を、増加した最高周波数で動作可能にすることである。
【図面の簡単な説明】
【００２２】
【図１】ネットリストの一例を表す回路図である。
【図２】算術論理ユニットおよびマルチプレクサ、レジスタ、ならびにこれら要素を接続するルーティングネットワークを有する単純な再構成可能な装置の一例である。
【図３】図２の再構成可能な装置上への図１のネットリストの可能な配置を表す回路図である。
【図４】構成におけるほとんどの経路に対する最終のルーティング解、および図２の配置されたネットリストにおけるレジスタＲＸからマルチプレクサＭＹへのネットに対するかなり可能性があるルーティング解の回路図である。
【図５】本発明において与えられるルーティングアルゴリズムにより選択されたルーティング解の回路図である。
【図６】図５のルーティングされたネットリストにおいて本発明の配置後ルーティングによるタイミング再調整の効果の回路図である。
【発明を実施するための形態】
【００２３】
ここで、本発明の一例が添付の図面を参照して説明される。
【００２４】
ここで、図１から６を参照して、本発明の方法が説明される。図１は、一適用例の合成ステージ後のネットリストを示す。このネットリストは、４つの２入力／１出力算術論理ユニット（ＡＡ、ＡＢ、ＡＣ、およびＡＤ）、２つのマルチプレクサ（ＭＸおよびＭＹ）、ならびに５つのレジスタ（ＲＡ、ＲＢ、ＲＣ、ＲＤ、およびＲＸ）を有する。これらの要素は、互いに接続され、かつ示されるような入力／出力（Ｉ／Ｏ）ポートに接続される。
【００２５】
図１における経路構成は、最適である。図１における論理的タイミング調整経路は、１つの論理要素だけを介してルーティングされ、それゆえに理想的である。しかしながら、これが、再構成可能な装置／構造においてまだ配置されていない、およびルーティングされていないネットリストであるので、このルーティングの仕組みは、理想的であるように見えるにすぎない。したがって、図１のネットリストは、ただ単に、再構成可能な構造において構成されることが必要な接続を表し、再構成可能な構造において構成される実際の物理的接続を表さない。それゆえに、ネットリストは、接続の長さ、または各接続に関連付けられる時間遅延に関する情報をまったく与えない。この観点において、図１は、回路のハイレベルな図面を表す。物理的に実現するためには、図１のネットリストが、物理的装置／構造上へ配置され、ルーティングされる必要がある。
【００２６】
図２は、論理ブロックおよび相互接続するルーティングネットワークを有する、単純で再構成可能なアーキテクチャを示す。この例において、論理ブロック自身は、プログラム可能ＡＬＵおよびマルチプレクサを有することが可能である。しかしながら、実際のアーキテクチャにおいて、論理ブロックは、さらにビットセレクタ、ブール論理要素、およびその他の一般的にさらに複雑なブロックを有することが可能である。ルーティングネットワークは、その交点に位置したプログラム可能スイッチ（図示されない）により接続されるいくつかの配線を有する。知られている再構成可能なアーキテクチャにおいて、これらのスイッチは、能動的なまたは受動的なスイッチであることが可能である。この例において、および本発明を説明するために、各交点は、いずれか２つの垂直の配線を接続するか、または代わりの構成としては、直線上のあらゆる配線対を接続することが可能なスイッチ（図示されない）を有する。しかしながら、注目すべきは、異なるアーキテクチャが配線を接続する異なる方法を実装してもよいことである。Ｉ／Ｏ接続は、配列の周囲に位置している。
【００２７】
さらに、この例における論理要素は、ルート貫通リソースとして使用することが可能である。ＡＬＵに対しては、これは、「入力伝搬」機能を用いてプログラミングすることにより達成される。マルチプレクサに対しては、これは、ルーティングネットワークからの入力を用いるよりもむしろ選択入力へ、一定の信号をルーティングすることによりなされる。レジスタは、上述した要素の出力バスのいくつかに位置している。図２から理解されるように、ルーティングネットワークに対して独立しているレジスタは１つも無い。むしろ、レジスタの各１個と、このレジスタを駆動する論理要素との間の短い接続が常に存在する。
【００２８】
各レジスタは、クロックで制御されるか、またはトランスペアレントであることが可能である。この状態は、「トランスペアレントフラグ」として知られている構成可能状態ホルダーにより特定される。レジスタがクロックで制御される場合、レジスタは通常通りに動作する（すなわち、レジスタはあらゆるクロック周期において入力値を出力値へ伝搬する）。それとは異なって、レジスタがトランスペアレントモードにある場合、レジスタはクロックの待ち時間無しに（すなわち、小さい伝搬遅延だけで）入力値を伝搬する。これは、レジスタがルート貫通リソースとして使用されることが可能であることを意味する。
【００２９】
配置ステージにおける起こり得る結果が図３に示される。図３では、図１のネットリストにおける要素が、図２の物理的配列上に配置されている。図３に示される配置は、いくつかの可能性がある配置解の１つである。この配置解のいくつかの態様は有益である。たとえば、マルチプレクサは選択入力を制御するＡＬＵに相対的に近接して配置され、その結果、ルーティングネットワークが与える高速接続を利用することになる。さらに、ネットリスト内で一連のＡＬＵ（ＡＢ、ＡＣ、およびＡＤ）が接続される斜めの軸は、配置内で維持される。さらにその上、あらゆるレジスタが、レジスタを駆動する要素に非常に近接して配置される。しかしながら、好ましいことに、これらの有益な特徴を与えるために、この配置解は、特に、マルチプレクサＭＸおよびＭＹを遠ざけるなどの、いくらかの不利益を被る。
【００３０】
開発過程における次のステージ、および本発明の方法における最初のステップは、配置されたネットリストをルーティングすることを有する。ネットリストにおけるネットのほとんどにとっては、ルーティング問題への解はささいなことである。したがって、混雑状態はまったく見つけられない。図４は、レジスタＲＸからマルチプレクサＭＹへの経路に対して、３つの代替的な経路を有する、起こり得る不完全なルーティングシナリオを示す。
【００３１】
ＲＸからＭＹへの経路は、マルチプレクサＭ１３の一方の入力を通過する（および次に、トランスペアレントとして設定可能なレジスタＲＧ１３を通過する）かまたはマルチプレクサブロック全体の周囲にルーティングされることが可能である。これが可能になるのは、上述したように、論理要素およびレジスタがルート貫通リソースとして使用可能であるからである。図４は、配線のあらゆる線分およびこの例におけるあらゆる論理要素に対する遅延量を示す。
【００３２】
ルーティングアルゴリズムには、１つの経路を選択するためのいくつかの判断基準がある。典型的には、選択は、経路全体の遅延に依存し（すなわち、性能を最大化するために最低遅延経路が選択される）、混雑した配線の数に依存する（すなわち、混雑状態は回避されることになる）。本発明の方法は、最適な経路を選択する、追加された新しい判断基準を使用する修正されたルーティングアルゴリズムを与える。さらに、本発明は、より長い遅延を有し、配線混雑状態に対してこれ以上利益を与えないにもかかわらず、タイミング再調整段階において利用可能な少なくとも１つのトランスペアレントレジスタを通過する１つの経路を選択するという、修正されたルーティングアルゴリズムを実装するルータを与える。
【００３３】
図４の例において、提案された経路に伴う不利な点は、示された起こり得る解のすべてが、レジスタＲＸから出力ポートへの相対的に長いタイミング調整経路に結果することである。これは、要素を接続するのに使用される配線のあらゆる線分が、信号伝搬遅延の原因となる抵抗および静電容量を有し、あらゆる有効な通過する論理要素が自身の伝搬遅延を有するからである。図４に示される遅延は、時間について非特定の単位で記載されている。好ましいことに当業者によっては、再構成可能な装置のハードウェア実装に依存して、この非特定の単位における実際の長さは変えてもよい。
【００３４】
標準のタイミング調整に基づくルータは、遅延の最小量を作り出す解を選択する。それは、マルチプレクサブロックの周囲を回る経路である。図４に示されるように、この経路は、ＲＸから出力ポートへ、０．８４単位（すなわち、０．０３＋０．０９＋０．０１＋０．０１＋０．０４＋０．１２＋０．０６＋０．０９＋０．０１＋０．２＋０．１＋０．０３＋０．０５）の全遅延を有する。したがって、回路の性能は、この相対的に長い接続により影響される。
【００３５】
この問題を解決するために、本発明の方法は、修正されたルーティングアルゴリズムと、ルーティングステージ後に与えられるタイミング再調整アルゴリズムとの間の相乗効果を使用する。
【００３６】
本発明に従うルータは、最初に、ＲＸからＭＹまでの間の種々の経路を分析する。その際、ルータは、これらの経路間の差が、スイッチαからスイッチβまで伸びるルートに限定されることを決定する。上述したように、図４の例は、３つのルーティングの可能性を示す。ネットは、マルチプレクサブロックの周囲に、マルチプレクサ入力の一方を介して、またはマルチプレクサ入力の他方を介して、ルーティングされることが可能である。マルチプレクサの周囲にネットをルーティングすることにより、スイッチαからスイッチβまでは、０．２４単位の遅延となる一方、可能性があるマルチプレクサを介してネットをルーティングすると、選択された入力に依存して、０．３４単位または０．３６単位の遅延となる。
【００３７】
次に、本発明のルータは、マルチプレクサブロックを経由する経路が貫通レジスタ（すなわちレジスタＲＧ１３）を含むことを検出する。この検出ステップは、貫通レジスタを通過する経路がタイミング調整の点では最適ではないかも知れないにもかかわらず、これらの経路内におけるトランスペアレントレジスタＲＧ１３が、タイミング再調整段階でさらに有利な点を与えるかも知れないという点において、意味深い有利な点を与える。
【００３８】
次のステップは、可能性がある経路を解析し、信号をルーティングするためにもっとも便利な経路を決定することである。１つの経路に位置した貫通レジスタが、ルーティング過程の間にさらにいくつかの点で有用であるにもかかわらず、ある場合には、レジスタに達するために必要となる追加された遅延はあまりにも大きくなる。それゆえに、本発明に従うルータは、１つ以上の貫通レジスタを有する相対的に長い経路を受け入れるかどうかを決定する判断基準を使用する。この判断基準は、いずれかの数学的または論理的判断基準、たとえば、単純な費用関数であり得る（すなわち、最短経路と、少なくとも貫通レジスタ上に有する経路の最短との間の遅延差が所定のしきい値以下の場合、その経路は受け入れられる）。しきい値は、ユーザにより固定可能な、固定した数または「許容範囲」（たとえば、特定の遅延のパーセンテージ）であることが可能である。それゆえに、ユーザは、貫通レジスタの使用から利益を得る可能性に対して、進んでリスクを取る遅延の量を決定することが可能である。同様に、経路が有してもよい貫通レジスタの数などの、他の因数が、解析ステップに織り込まれてもよい。
【００３９】
ここで、図４の例を参照して、上述した一例が説明される。ここでは、０．１５時間単位の遅延しきい値が、ユーザにより選択されている。レジスタＲＧ１３を通過するルーティング経路が代わりの選択肢よりもわずかに長いだけなので（すなわち、それぞれ０．１０または０．１２時間単位）、これらのルーティング経路は、本発明のルータにより受け入れられる。レジスタを通過する２つの経路のうち、０．３４単位の遅延を作り出す一方が最短となる。したがって、本発明の方法は、最終的に０．３４単位の遅延を有する経路を選択する。
【００４０】
図５は、本発明のルータにより選択された最終のルーティングを示す。レジスタＲＸから出力ポートへの全遅延は、０．９４単位である。このステージにおいて、知られているタイミング再調整アルゴリズムは、有効な配置の制限された一組に対して、挿入または移動することだけが可能であるという点において、重大な制約を被る。
【００４１】
それとは異なって、本発明の方法においては、レジスタの「移動」を実行することは、レジスタ対の「トランスペアレント」状態ホルダーを交換し、レジスタ対の一方がトランスペアレントなルート貫通レジスタとなるように「降格」させ、他方がクロック制御レジスタとなるように「昇進」させることを意味する。同様に、レジスタを「挿入する」ことは、その「トランスペアレント」フラグをスイッチングし、クロック制御レジスタとなるように昇進させることを意味する。
【００４２】
それゆえに、選択された経路上のすべてのトランスペアレントレジスタは、タイミング再調整アルゴリズムに用いるのに有効な追加された配置となる。本発明の方法が、ルーティング経路に含むことが可能なトランスペアレントレジスタを具体的に探し出すステップを有するので、本発明の方法は、引き続くタイミング再調整ステップにおいて使用可能なトランスペアレントレジスタに関して、平均して、広い範囲の選択肢を入手できる。
【００４３】
本方法の次のステップは、ネットリストの機能性を維持し、ネットリストにおける最長遅延経路を最小化するレジスタ配置の最適な構成を計算するステップである。好ましいことに、アルゴリズムがこのステップにおいて値を計算するのに使用する情報は、配置およびルーティング段階の後で抽出されるので、正確である。さらにその上、論理要素を接続する配線の抵抗および静電容量が知られている。最後に、セルを介する伝搬遅延は、たとえば、ハードウェア特性データベースで調べることが可能であるので、知られている。したがって、各経路全体の遅延は、見積もられるというよりもむしろ正確に決定される。
【００４４】
図５の例において、１つの「移動」だけが、レジスタの最適な構成に達するのに必要である。図５から理解可能なように、理想的な「移動」は、ＲＧ１３をＲＸであるように起動することである。図５から明らかに理解可能なように、この構成は、システムにおいて最長遅延経路を最小化する。したがって、本発明の方法は、ＲＧ０２のトランスペアレント状態ホルダーを起動し、それによってトランスペアレントレジスタへ「降格」させ、ＲＧ１３のトランスペアレント状態ホルダーを停止し、それによってクロック制御レジスタへ「昇進」させる。レジスタＲＧ２２の状態は、変化しないままである。
【００４５】
図６は、本発明の方法により作り出される最終の結果を図示する。理解可能なように、タイミング再調整段階が与えられる前には、最長タイミング調整経路は、ＲＸからＭＹを介して出力ポートへの経路であった。本発明の方法を用いて選択されるルートは、０．９４時間単位の長さであったが、一方、標準ルーティングアルゴリズムは、０．８４時間単位の最長遅延経路を有する経路を選択していた。しかしながら、標準ルータにより回路に与えられる、知られているタイミング再調整アルゴリズムは、十分に有効で入手可能な配置が無かったので、いずれの未使用のレジスタも使用することができなかったが、一方、本発明に従って実行されるタイミング再調整段階は、最終のルーティング経路において有益に使用される追加のレジスタ配置を入手することができた。
【００４６】
本発明の方法の実行結果として、最長経路がＲＡからＭＸを介してＲＸへの経路となる。このルートは、０．７４単位の長さである。この低減された遅延により、設計の最高クロック周波数を増加することが可能になる。これは、基本的なルーティングステップにおける結果に対して、性能で２７％の改善、標準ルーティングアルゴリズムにより達成される結果に対して、性能で１３．５％の改善を表す。
【産業上の利用可能性】
【００４７】
本発明は、ルータを利用した配置後ルーティングによるタイミング再調整に利用できる。
【図１】
2009238221.tif 000003
【図２】
2009238221.tif 000004
【図３】
2009238221.tif 000005
【図４】
2009238221.tif 000006
【図５】
2009238221.tif 000007
【図６】
2009238221.tif 000008
【外国語明細書】
2009238221.tif 000009
2009238221.tif 000010
2009238221.tif 000011
2009238221.tif 000012
2009238221.tif 000013
2009238221.tif 000014
2009238221.tif 000015
2009238221.tif 000016
2009238221.tif 000017
2009238221.tif 000018
2009238221.tif 000019
2009238221.tif 000020
2009238221.tif 000021
2009238221.tif 000022
2009238221.tif 000023
2009238221.tif 000024
2009238221.tif 000025
2009238221.tif 000026
2009238221.tif 000027
2009238221.tif 000028
2009238221.tif 000029