(57)【特許請求の範囲】
【請求項１】
システムを設計するための方法であって、該システムは、標的デバイス上に実装されるものであり、該方法は、
基準に基づいてコンピュータ支援設計（ＣＡＤ）ツールによって配置されるように、該システム内の第１の複数の構成要素を割り当てることと、
該基準に基づいて、ハードウェア内に実装されたハードウェア配置ユニットによって配置されるように、該システム内の第２の複数の構成要素を割り当てることと、
該標的デバイス上の該システムに対する配置の解を生成するために、該ＣＡＤツールおよび該ハードウェア配置ユニットからの配置結果を利用することと
を含む、方法。
【請求項２】
前記システムを合成することと、
該システムを経路指定することと、
該システムを前記標的デバイスにプログラムするためのデータファイルを作成することと、
該標的デバイス上のリソースを物理的に変換して該システムを実装するように、該標的デバイスをプログラムすることと
をさらに含む、請求項１に記載の方法。
【請求項３】
前記基準は、構成要素が閾値を超えるタイミング必要条件を有するときに、ＣＡＤツールを用いて該構成要素を配置することを含む、請求項１に記載の方法。
【請求項４】
前記基準は、構成要素がクリティカルパスに連結されるときに、ＣＡＤツールを用いて該構成要素を配置することを含む、請求項１に記載の方法。
【請求項５】
前記基準は、構成要素が入力／出力（Ｉ／Ｏ）であるときに、ＣＡＤツールを用いて該構成要素を配置することを含む、請求項１に記載の方法。
【請求項６】
前記基準は、構成要素がメモリであるときに、ＣＡＤツールを用いて該構成要素を配置することを含む、請求項１に記載の方法。
【請求項７】
前記基準は、構成要素がデジタル信号プロセッサ（ＤＳＰ）であるときに、ＣＡＤツールを用いて該構成要素を配置することを含む、請求項１に記載の方法。
【請求項８】
前記基準に基づいてハードウェア配置ユニットによって配置されるように、前記システム内の第２の複数の構成要素を割り当てることは、
該ハードウェア配置ユニット上で行および列に配列された仮想論理要素（ＶＬＥ）に、前記標的デバイス上のリソースをマップすることと、
該ＶＬＥをセクションに区切ることと、
移動処理ユニット（ＭＰＵ）を（ＶＬＥ）の該セクションのそれぞれに割り当てることと、
ＶＬＥ間で構成要素を移動させるコストを計算するようにＭＰＵに指示することと
を含む、請求項１に記載の方法。
【請求項９】
前記指示することは、１組のＶＬＥ間の移動が第２組のＶＬＥの行および列に交差しない場合に行われる、請求項８に記載の方法。
【請求項１０】
前記ＭＰＵは、並行してＶＬＥ間で構成要素を移動させるコストを計算する、請求項８に記載の方法。
【請求項１１】
フィールドプログラマブルゲートアレイ（ＦＰＧＡ）を使用するコストを計算するための方法であって、該方法は、
行および列に配列された仮想論理要素（ＶＬＥ）に、標的デバイス上のリソースをマップすることと、
ＶＬＥのグループを複数のセクションに区切ることと、
該ＦＰＧＡ上の一意的な移動処理ユニット（ＭＰＵ）を該複数のセクションの各セクションに割り当てることと、
各一意的なＭＰＵが、その関連付けられるセクション内のＶＬＥ間で構成要素を移動させるコストを計算することと
を含み、
該マップすること、該区切りすること、該割り当てること、および有することのうちの少なくとも１つは、ＦＰＧＡを用いて行われる、方法。
【請求項１２】
前記一意的なＭＰＵのそれぞれは、
第１のＶＬＥおよび第２のＶＬＥにおける前記構成要素と関連付けられるネットのネット境界縁を識別することと、
該ネット境界縁において該ネットに連結される構成要素を実装するために使用される、ＶＬＥの数を識別することと、
該ネット境界縁が増加するか減少するかに基づいて、および移動したネット境界縁において該ネットに連結される構成要素を実装するために使用されるＶＬＥの数にさらに基づいて、該第１および第２のＶＬＥの間で構成要素を移動させることにコストを割り当てることと
によって該一意的なＭＰＵのそれぞれの関連付けられるセクション内のＶＬＥ間で構成要素を移動させる前記コストを計算する、請求項１１に記載の方法。
【請求項１３】
構成要素を移動させることに前記コストを割り当てることは、前記第１のＶＬＥから前記第２のＶＬＥへ前記構成要素を移動させるとともに前記ネット境界が増加する場合に、１というコストを割り当てることを含む、請求項１２に記載の方法。
【請求項１４】
構成要素を移動させることに前記コストを割り当てることは、前記構成要素を移動させるとともに前記ネット境界が減少する場合に、および移動させられる前記ネット境界縁に１つのＶＬＥがある場合に、−１というコストを割り当てることを含む、請求項１２に記載の方法。
【請求項１５】
移動させることに前記コストを割り当てることは、前記構成要素を移動させるとともにネット境界が減少する場合に、および移動させられる前記ネット境界縁に１つよりも多くのＶＬＥがある場合に、０というコストを割り当てることを含む、請求項１２に記載の方法。
【請求項１６】
前記ネット境界縁を識別することは、前記ＦＰＧＡのメモリに記憶されたネット境界縁情報を取り出すことを含む、請求項１２に記載の方法。
【請求項１７】
前記ネット境界縁におけるＶＬＥの数を識別することは、前記ＦＰＧＡのメモリに記憶されたネット識別子情報を取り出すことを含む、請求項１２に記載の方法。
【請求項１８】
計算された前記コストに応じて、前記第１および第２のＶＬＥの間で前記構成要素を移動させることと、
前記構成要素を移動させるときに、ネットと関連付けられるネット境界縁情報およびネット識別子情報を更新することと
をさらに含む、請求項１２に記載の方法。
【請求項１９】
別のＭＰＵが、前記ＭＰＵと並行して別のグループ内のＶＬＥ間で他の構成要素を移動させるコストを計算することをさらに含む、請求項１１に記載の方法。
【請求項２０】
標的デバイス上のリソースを表す仮想論理要素（ＶＬＥ）、該ＶＬＥによって表される該リソースによって実装されるシステム設計における構成要素、および該構成要素と関連付けられるネットを記憶するように動作可能な第１の複数のメモリブロックと、
該構成要素と関連付けられるネットのネット境界縁を識別するネット境界要素（ＮＢＥ）を記憶するように動作可能な第２の複数のメモリブロックと、
該ネット境界が増加するか減少するか、および移動したネット境界縁において該ネットに連結される該構成要素を実装するために使用されるＶＬＥの数に基づいて、第１および第２のＶＬＥの間で該構成要素を移動させるコストを計算するように動作可能な移動処理ユニット（ＭＰＵ）と
を備える、ハードウェア配置ユニット。
【請求項２１】
前記第１および第２のＶＬＥの間で構成要素を移動させる前記コストを計算する前記ＭＰＵと並行して、第３および第４のＶＬＥの間で構成要素を移動させるコストを計算するように動作可能な別のＭＰＵをさらに備える、請求項２０に記載のハードウェア配置ユニット。
【請求項２２】
前記ＭＰＵは、前記コストが容認可能であるという決定に応じて、前記第１および第２のＶＬＥの間で前記構成要素を移動させ、前記移動を反映するように前記ＶＬＥおよび前記ＮＢＥを更新する、請求項２０に記載のハードウェア配置ユニット。
【請求項２３】
前記ハードウェア配置ユニットは、フィールドプログラマブルゲートアレイ（ＦＰＧＡ）上で実装される、請求項２０に記載のハードウェア配置ユニット。
【請求項２４】
コンピュータを、
システムを合成するように動作可能な合成ユニットと、
基準に基づいて、コンピュータ支援設計（ＣＡＤ）ツールによって配置されるように、該システム内の第１の複数の構成要素を割り当て、ハードウェア内に実装されたハードウェア配置ユニットによって配置されるように、該システム内の第２の複数の構成要素を割り当てるように動作可能であり、標的デバイス上の該システムに対する配置解決法を生成するために、該ＣＡＤツールおよび該ハードウェア配置ユニットからの配置結果を利用する、配置準備ユニットと
として機能させる、システムデザイナプログラム。
【請求項２５】
前記配置準備ユニットは、配置される構成要素が閾値以上または以下であるタイミング必要条件を有するかどうかを決定するように動作可能なタイミングユニットを備える、請求項２４に記載のシステムデザイナプログラム。
【請求項２６】
前記配置準備ユニットは、配置される構成要素が、１）入力／出力、２）メモリ、および３）デジタル信号プロセッサのうちの１つであるかどうかを決定するように動作可能な構成要素種類識別子ユニットを備える、請求項２４に記載のシステムデザイナプログラム。
【請求項２７】
システムを合成するように動作可能な合成ユニットと、
基準に基づいて、コンピュータ支援設計（ＣＡＤ）ツールによって配置されるように、該システム内の第１の複数の構成要素を割り当て、ハードウェア内に実装されたハードウェア配置ユニットによって配置されるように、該システム内の第２の複数の構成要素を割り当てるように動作可能であり、標的デバイス上の該システムに対する配置解決法を生成するために、該ＣＡＤツールおよび該ハードウェア配置ユニットからの配置結果を利用する、配置準備ユニットと
を備える、システムデザイナ装置。
【請求項２８】
前記配置準備ユニットは、配置される構成要素が閾値以上または以下であるタイミング必要条件を有するかどうかを決定するように動作可能なタイミングユニットを備える、請求項２７に記載のシステムデザイナ装置。
【請求項２９】
前記配置準備ユニットは、配置される構成要素が、１）入力／出力、２）メモリ、および３）デジタル信号プロセッサのうちの１つであるかどうかを決定するように動作可能な構成要素種類識別子ユニットを備える、請求項２７に記載のシステムデザイナ装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本願は、２００９年１１月１２日に出願された先願である米国特許出願第１２／５９０，６４３号の優先権を主張し、上記米国特許出願は、本明細書において参照により援用される。
【０００２】
本発明の実施形態は、標的デバイス上でシステムを設計するためのツールに関する。より具体的には、本発明の実施形態は、ハードウェア支援配置を行うための方法および装置に関する。
【背景技術】
【０００３】
大型システム用の電子設計は、何百万ものゲートおよびメガビットの組み込みメモリを含んでもよい。標的デバイス上の電子設計を管理および最適化する際に必要とされるタスクのうち、利用可能なリソースを利用した、合成、配置、および経路指定が、最も困難で時間がかかるものとなり得る。大型システムの複雑性はしばしば、設計を管理および最適化するために、コンピュータ支援設計（ＣＡＤ）または電子設計自動化（ＥＤＡ）ツールの使用を必要とする。ＣＡＤツールは、標的デバイス上の合成、配置、および経路指定という時間のかかるタスクを行う。
【０００４】
配置は現在、大型システムにおける設計時間の約５０％を占めている。フィールドプログラマブルゲートアレイ（ＦＰＧＡ）等の現在の標的デバイスの密度は、プロセッサ速度およびＣＡＤ手順が動作する速度の増加をしのぎ、配置コンパイル時間の増加につながっている。この問題に対処するために使用される１つのアプローチは、ＣＡＤツールによって提供される配置アルゴリズムの代わりにハードウェア支援配置を使用することである。
【０００５】
過去のハードウェア支援配置技術は、配置に使用されるコスト指標を導出することと関連付けられる、いくつかの制限を受けた。例えば、過去のハードウェア支援配置技術には、ネットの末端の境界を示すために使用されるネットの境界ボックスコストを計算するときに古くなった情報を使用するという問題があった。過去のハードウェア支援配置技術はまた、タイミングクリティカルパスへの配慮を提供できず、設計を実行することができる最大頻度に悪影響を及ぼした。
【発明の概要】
【発明が解決しようとする課題】
【０００６】
したがって、必要とされるものは、配置で使用されるコスト指標を効率的かつ正確に導出する、ハードウェア支援配置を行うための方法および装置である。
【課題を解決するための手段】
【０００７】
本発明の例示的実施形態によれば、標的デバイス上でシステムを設計するための方法および装置が開示される。システム内の第１の複数の構成要素は、基準に基づいてコンピュータ支援設計（ＣＡＤ）ツールによって配置されるように割り当てられる。システム内の第２の複数の構成要素は、基準に基づいてハードウェア配置ユニットによって配置されるように割り当てられる。ＣＡＤツールおよびハードウェア配置ユニットからの配置結果は、標的デバイス上のシステムに対する配置解決法を生成するために利用される。開示されるハイブリッドハードウェアソフトウェア配置技術は、タイミングクリティカルパスに対処しながら並列性を増加させ、結果として生じるシステム設計が最大許容頻度で動作することを可能にする。
【０００８】
本発明の実施形態の特徴および利点は、一例として図示され、本発明の実施形態の範囲を示された特定の実施形態に限定することを目的としていない。
本願明細書は、例えば、以下の項目も提供する。
（項目１）
標的デバイス上でシステムを設計するための方法であって、
基準に基づいてコンピュータ支援設計（ＣＡＤ）ツールによって配置されるように、該システム内の第１の複数の構成要素を割り当てることと、
該基準に基づいてハードウェア配置ユニットによって配置されるように、該システム内の第２の複数の構成要素を割り当てることと、
該標的デバイス上の該システムに対する配置解決法を生成するために、該ＣＡＤツールおよび該ハードウェア配置ユニットからの配置結果を利用することと
を含む、方法。
（項目２）
前記システムを合成することと、
該システムを経路指定することと、
該システムを組み立てることと、
前記標的デバイス上のリソースを物理的に変換して該システムを実装するように、該標的デバイスをプログラムすることと
をさらに含む、項目１に記載の方法。
（項目３）
前記基準は、構成要素が閾値を超えるタイミング必要条件を有するときに、ＣＡＤツールを用いて該構成要素を配置することを含む、項目１に記載の方法。
（項目４）
前記基準は、構成要素がクリティカルパスに連結されるときに、ＣＡＤツールを用いて該構成要素を配置することを含む、項目１に記載の方法。
（項目５）
前記基準は、構成要素が入出力（ＩＯ）であるときに、ＣＡＤツールを用いて該構成要素を配置することを含む、項目１に記載の方法。
（項目６）
前記基準は、構成要素がメモリであるときに、ＣＡＤツールを用いて該構成要素を配置することを含む、項目１に記載の方法。
（項目７）
前記基準は、構成要素がデジタル信号プロセッサ（ＤＳＰ）であるときに、ＣＡＤツールを用いて該構成要素を配置することを含む、項目１に記載の方法。
（項目８）
前記基準に基づいてハードウェア配置ユニットによって配置されるように、前記システム内の第２の複数の構成要素を割り当てることは、
該ハードウェア配置ユニット上で行および列に配列された仮想論理要素（ＶＬＥ）に、前記標的デバイス上のリソースをマップすることと、
該ＶＬＥをセクションに区切ることと、
移動処理ユニット（ＭＰＵ）を（ＶＬＥ）の該セクションのそれぞれに割り当てることと、
ＶＬＥ間で構成要素を移動させるコストを計算するようにＭＰＵに指示することと
を含む、項目１に記載の方法。
（項目９）
前記指示することは、１組のＶＬＥ間の移動が第２組のＶＬＥの行および列に交差しない場合に行われる、項目８に記載の方法。
（項目１０）
前記ＭＰＵは、並行してＶＬＥ間で構成要素を移動させるコストを計算する、項目８に記載の方法。
（項目１１）
フィールドプログラマブルゲートアレイ（ＦＰＧＡ）を使用するコストを計算するための方法であって、
行および列に配列された仮想論理要素（ＶＬＥ）に、標的デバイス上のリソースをマップすることと、
ＶＬＥのグループをセクションに区切ることと、
該ＦＰＧＡ上の一意的な移動処理ユニット（ＭＰＵ）をＶＬＥの該セクションのそれぞれに割り当てることと、
該グループ内のＶＬＥ間で構成要素を移動させるコストをＭＰＵに計算させることと
を含む、方法。
（項目１２）
前記ＭＰＵは、各グループ内のＶＬＥ間で構成要素を移動させる前記コストを計算し、
第１のＶＬＥおよび第２のＶＬＥにおける前記構成要素と関連付けられるネットのネット境界縁を識別することと、
該境界縁においてネットに連結される構成要素を実装するために使用される、ＶＬＥの数を識別することと、
該ネット境界縁が増加するか減少するか、および移動したネット境界縁においてネットに連結される構成要素を実装するために使用されるＶＬＥの数に基づいて、該第１および第２のＶＬＥの間で構成要素を移動させることにコストを割り当てることと
を含む、項目１１に記載の方法。
（項目１３）
構成要素を移動させることに前記コストを割り当てることは、前記第１のＶＬＥから前記第２のＶＬＥへ前記構成要素を移動させるとともにネット境界が増加する場合に、１というコストを割り当てることを含む、項目１１に記載の方法。
（項目１４）
構成要素を移動させることに前記コストを割り当てることは、前記構成要素を移動させるとともにネット境界が減少する場合に、−１というコストを割り当てることを含み、１つのＶＬＥは、移動させられたネット境界縁にある、項目１１に記載の方法。
（項目１５）
移動させることに前記コストを割り当てることは、前記構成要素を移動させるとともにネット境界が減少する場合に、０というコストを割り当てることを含み、１つよりも多くのＶＬＥは、移動させられたネット境界縁にある、項目１１に記載の方法。
（項目１６）
前記ネット境界縁を識別することは、前記ＦＰＧＡのメモリに記憶されたネット境界縁情報を取り出すことを含む、項目１２に記載の方法。
（項目１７）
前記ネット境界縁におけるＶＬＥの数を識別することは、前記ＦＰＧＡのメモリに記憶されたネット識別子情報を取り出すことを含む、項目１２に記載の方法。
（項目１８）
計算された前記コストに応じて、前記第１および第２のＶＬＥの間で前記構成要素を移動させることと、
前記構成要素を移動させるときに、ネットと関連付けられるネット境界縁情報およびネット識別子情報を更新することと
をさらに含む、項目１２に記載の方法。
（項目１９）
前記ＭＰＵと並行して別のグループ内のＶＬＥ間で他の構成要素を移動させるコストを別のＭＰＵに計算させることをさらに含む、項目１１に記載の方法。
（項目２０）
標的デバイス上のリソースを表す仮想論理要素（ＶＬＥ）、該ＶＬＥによって表される該リソースによって実装されるシステム設計における構成要素、および該構成要素と関連付けられるネットを記憶する、第１の複数のメモリブロックと、
構成要素と関連付けられるネットのネット境界縁を識別するネット境界要素（ＮＢＥ）を記憶する、第２の複数のメモリブロックと、
該ネット境界が増加するか減少するか、および移動したネット境界縁においてネットに連結される構成要素を実装するために使用されるＶＬＥの数に基づいて、第１および第２のＶＬＥの間で構成要素を移動させるコストを計算する、移動処理ユニット（ＭＰＵ）と
を備える、ハードウェア配置ユニット。
（項目２１）
前記第１および第２のＶＬＥの間で構成要素を移動させる前記コストを計算する前記ＭＰＵと並行して、第３および第４のＶＬＥの間で構成要素を移動させるコストを計算する別のＭＰＵをさらに備える、項目２０に記載のハードウェア配置ユニット。
（項目２２）
前記ＭＰＵは、前記コストが容認可能であるという決定に応じて、前記第１および第２のＶＬＥの間で構成要素を移動させ、前記移動を反映するように前記ＶＬＥおよびＮＢＥを更新する、項目２０に記載のハードウェア配置ユニット。
（項目２３）
前記ハードウェア配置ユニットは、フィールドプログラマブルゲートアレイ（ＦＰＧＡ）上で実装される、項目２０に記載のハードウェア配置ユニット。
（項目２４）
システムを合成する合成ユニットと、
基準に基づいて、コンピュータ支援設計（ＣＡＤ）ツールによって配置されるように、該システム内の第１の複数の構成要素を割り当て、ハードウェア配置ユニットによって配置されるように、該システム内の第２の複数の構成要素を割り当て、標的デバイス上の該システムに対する配置解決法を生成するために、該ＣＡＤツールおよび該ハードウェア配置ユニットからの配置結果を利用する、配置準備ユニットと
を備える、システムデザイナ。
（項目２５）
前記配置準備ユニットは、配置される構成要素が閾値以上または以下であるタイミング必要条件を有するかどうかを決定する、タイミングユニットを備える、項目２４に記載のシステムデザイナ。
（項目２６）
前記配置準備ユニットは、配置される構成要素が、１）入出力、２）メモリ、および３）デジタル信号プロセッサのうちの１つであるかどうかを決定する、構成要素種類識別子ユニットを備える、項目２４に記載のシステムデザイナ。
【図面の簡単な説明】
【０００９】
【図１】図１は、本発明の例示的実施形態による、システムを設計するための方法を図示するフローチャートである。
【図２】図２は、本発明の例示的実施形態による、配置準備を行うための方法を図示するフローチャートである。
【図３】図３は、仮想論理要素のグループをセクションに区切ることの実施例を図示する。
【図４】図４は、相互排他的な移動の実施例を図示する。
【図５】図５ａ−ｄは、ブロックが異なるＶＬＥへと移動させられることを可能にするように、仮想論理要素のグループをセクションに区切ることの実施例を図示する。
【図６】図６は、本発明の実施形態による、ハードウェア支援配置を行うための方法を図示するフローチャートである。
【図７ａ】図７ａ−ｃは、本発明の実施形態による、境界ボックスコストを計算することの実施例を図示する。
【図７ｂ】図７ａ−ｃは、本発明の実施形態による、境界ボックスコストを計算することの実施例を図示する。
【図７ｃ】図７ａ−ｃは、本発明の実施形態による、境界ボックスコストを計算することの実施例を図示する。
【図８】図８は、本発明の実施形態による、ハードウェア配置ユニットを実装するために使用されるデバイスを図示する。
【図９】図９は、本発明の例示的実施形態による、ハードウェア配置ユニットの構成要素間の相互作用を図示する。
【図１０】図１０は、本発明の例示的実施形態による、システム設計を拡大縮小するための処理ウィンドウを図示する。
【図１１】図１１は、本発明の例示的実施形態が存在するコンピュータシステムを図示する、ブロック図である。
【図１２】図１２は、本発明の例示的実施形態による、システムデザイナのブロック図である。
【図１３】図１３は、本発明の例示的実施形態による、配置準備ユニットのブロック図である。
【発明を実施するための形態】
【００１０】
以下の説明では、説明の目的で、本発明の実施形態の徹底的な理解を提供するように、具体的な用語が記載される。本発明の実施形態を実践するために、説明における具体的詳細が必要とされなくてもよいことが、当業者に明白となるであろう。他の場合において、本発明の実施形態を不必要に曖昧にすることを回避するように、周知の回路、デバイス、およびブロックがブロック図形態で示されている。
【００１１】
図１は、本発明の例示的実施形態による、標的デバイス上でシステムを設計するための方法を図示するフローチャートである。標的デバイスは、ＦＰＧＡ、ＡＳＩＣ、構造化ＡＳＩＣ、または他のデバイスであってもよい。一実施形態によれば、図１に図示された手順は、コンピュータシステム上で実装されるコンピュータ支援設計（ＣＡＤ）／電子設計自動化（ＥＤＡ）ツールによって行われてもよい。１０１では、システムが合成される。合成は、実装されるシステムの論理設計を生成することを含む。本発明の実施形態によれば、合成は、ＨＤＬ設計定義からシステムの最適化論理表現を生成する。システムの最適化論理表現は、システムに必要とされる、論理ゲートおよび論理要素等の最小化した数の機能ブロックおよびレジスタ（「構成要素」）を有する、表現を含んでもよい。合成はまた、最適化論理設計をマップすることも含む（技術マッピング）。マッピングは、標的デバイス上で利用可能なリソースを用いて、最適化論理表現において論理ゲートおよび論理要素をどのように実装するかを決定することを含む。本発明の実施形態によれば、ネットリストがマッピングから生成される。このネットリストは、ＨＤＬから生成される最適化技術マッピングネットリストであってもよい。
【００１２】
１０２では、配置準備が行われる。本発明の実施形態によれば、配置準備は、配置する最適化技術マッピングネットリスト内の構成要素を識別することと、どの構成要素を配置のためにＣＡＤ配置手順に割り当てるか、およびどの構成要素を配置のためにハードウェア配置ユニットに割り当てるかを決定することと伴う。ハードウェア配置ユニットに割り当てる構成要素の間で、構成要素が配置される順序および構成要素が並行して配置されるかどうかを決定するように、スケジュールが維持されてもよい。
【００１３】
１０３では、特定の構成要素で行われる配置が、ハードウェア配置ユニットによって行われるか、ＣＡＤツールによって実装される配置手順によって行われるかが決定される。配置がハードウェア配置ユニットによって行われるものである場合、制御は１０４へと進む。配置がＣＡＤツールによって実装される配置手順によって行われるものである場合、制御は１０５へと進む。
【００１４】
１０４では、マップされた論理システム設計における構成要素が、ハードウェア配置ユニットによって配置される。配置は、最適化技術マッピングネットリストに作用して、機能ブロックのそれぞれに対する配置を生成する。本発明の実施形態によれば、配置は、論理設計上のどのリソースが特定の論理要素に使用されるか、および合成中に決定されるようなシステムを実装すると決定される他の機能ブロックを決定することによって、標的デバイス上でシステムを嵌合することを含む。本発明の実施形態によれば、配置は、構成要素の初期配置から開始することと、構成要素の場所を標的デバイス上の他の構成要素と交換することとを伴ってもよい。コストが交換について計算されてもよい。交換が望ましいかどうかは、計算されるコストから決定されてもよい。制御は１０６へと進む。
【００１５】
１０５では、マップされた論理システム設計における構成要素が、ＣＡＤツールによって配置される。ＣＡＤツールは、ソフトウェアで実装され、コンピュータシステム内のプロセッサによって実行される１つ以上の配置手順を利用してもよい。配置は、最適化技術マッピングネットリストに作用して、機能ブロックのそれぞれに対する配置を生成する。本発明の実施形態によれば、配置は、論理設計上のどのリソースが特定の論理要素に使用されるか、および合成中に決定されるようなシステムを実装すると決定される他の機能ブロックを決定することによって、標的デバイス上でシステムを嵌合することを含む。配置は、標的デバイス上に存在する論理クラスタを形成するように論理要素をグループ化することを伴う、クラスタリングを含んでもよい。本発明の実施形態によれば、クラスタリングは、配置の初期段階で行われ、配置準備段階中の合成直後に発生する。
【００１６】
１０６では、配置解決法が、手順１０４によるハードウェア配置ユニットから生成される配置解決法から、および手順１０５によるＣＡＤツールから実装される配置手順から生成される配置解決法から生成される。
【００１７】
１０７では、配置が容認可能であるかどうかが決定される。本発明の実施形態によれば、配置は、タイミング、距離、および／または他の基準を含む、いくつかのパラメータを使用して評価されてもよい。タイミングが容認可能である場合、制御は１０８へと進む。タイミングが容認可能ではない場合、制御は１０３に戻る。１０３では、異なる配置解決法を生成するように、ＣＡＤツールを使用したハードウェア支援配置および／またはソフトウェア配置の別の反復が行われてもよい。
【００１８】
１０８では、配置された設計が経路指定される。経路指定中、標的デバイス上の経路指定リソースが、標的デバイス上の論理ゲート、論理要素、および他の構成要素間の相互接続を提供するように割り振られる。経路指定可能性の最適化も、配置された論理設計に行われてもよい。本発明の実施形態によれば、経路指定可能性の最適化の目標は、配置された論理設計における構成要素を接続するために使用される配線の量を削減することである。経路指定可能性の最適化は、論理出力数分割、論理重複、論理再配線、または他の手順を行うことを含んでもよい。手順のうちの１つ以上が、配置された論理設計に行われてもよいことを理解されたい。
【００１９】
１０９では、組み立て手順が行われる。組み立て手順は、１０１−１０８によって説明される編集手順によって決定される情報を含む、データファイルを作成することを伴う。データファイルは、標的デバイスをプログラムするために使用されてもよい、ビットストリームであってもよい。本発明の実施形態によれば、図１に図示される手順は、第１のコンピュータシステム上で実行されるＥＤＡツールによって行われてもよい。生成されるデータファイルは、システムの設計がさらに処理されることを可能にするように、第２のコンピュータシステムに伝送されてもよい。代替として、データファイルは、システム設計に従って標的デバイスをプログラムするために使用されてもよい、第２のコンピュータシステムに伝送されてもよい。システムの設計はまた、表示デバイスまたは他の媒体上等で他の形態で出力されてもよいことを理解されたい。
【００２０】
１０９では、標的デバイスは、データファイルでプログラムされる。データファイルで標的をプログラムすることによって、標的デバイス上の構成要素は、システムを実装するように物理的に変換される。標的デバイスが、ＡＳＩＣまたはＦＰＧＡ以外の他の標的デバイスである、本発明の実施形態によれば、手順１０８および１０９が行われなくてもよい。
【００２１】
図２は、本発明の例示的実施形態による、配置準備を行うための方法を図示するフローチャートである。図２に図示される手順は、図１の１０２−１０６で図示される手順を実装するために１０２で使用されてもよい。２０１では、構成要素が閾値以上または以下であるタイミング必要条件を有するかどうかが決定される。この基準は、構成要素がタイミングに関する重要構成要素であるか、重要信号と関連付けられるか、またはクリティカルパス上にあるかどうかを決定するために使用されてもよい。構成要素が閾値以上または以下であるタイミング必要条件を有すると決定された場合、制御は２０２へと進む。構成要素が閾値以上または以下であるタイミング必要条件を持たないと決定された場合、制御は２０３へと進む。
【００２２】
２０２では、構成要素は、コンピュータシステムによってソフトウェアで実装されるＣＡＤツールを使用して配置される構成要素として識別される。
【００２３】
２０３では、構成要素が１組の構成要素に属する種類であるかどうかが決定される。本発明の実施形態によれば、１組の構成要素は、入出力（ＩＯ）、メモリ、およびデジタル信号プロセッサ（ＤＳＰ）のうちの１つ以上、または他の種類の構成要素を含んでもよい。構成要素がこの基準を見たし、１組の構成要素に属する場合、制御は２０２へと進む。構成要素が１組の構成要素に属しない種類ではない場合、制御は２０４へと進む。
【００２４】
２０４では、構成要素は、物理的配置ユニットを使用して配置される構成要素として識別される。
【００２５】
２０５では、構成要素に割り当てられるために利用可能である標的デバイス上のリソースが、ハードウェア配置ユニット上の仮想論理要素（ＶＬＥ）にマップされる。２０２で識別される構成要素の配置を支持するために使用されるリソースは、利用不可能なリソースであると決定されてもよいことを理解されたい。各ＶＬＥは、標的デバイス上の複数のリソースを表してもよい。各ＶＬＥは、標的デバイス上の位置座標、ならびにリソースを使用する複数の構成要素と関連付けられる全てのネットについての情報を含んでもよい。
【００２６】
図３は、ＶＬＥがハードウェア配置ユニット上の行および列で配列される、本発明の実施形態を図示する。ＶＬＥは、移動処理ユニット（ＭＰＵ）（図示せず）がセクションのそれぞれに割り当てられる、セクション３０１−３０２に区切られてもよい。配置の反復中に、ＭＰＵは、各セクション内のＶＬＥ間で構成要素を移動させるコストを計算する。
【００２７】
図２を再び参照すると、２０６では、相互排他的な複数組の移動が識別される。移動によって覆われる行／列が交差しない場合、２つの個別移動は相互排他的である。本発明の実施形態によれば、ＭＰＵが並行してＶＬＥ間で構成要素を移動させるコストを計算することを可能にするために、相互排他的な複数組の移動が識別される。最大数の相互排他的な移動は、隣接する水平または垂直移動を考慮することによって達成される。ＶＬＥのｎ×ｎ行列を考慮すると、同時に交換することができる、最大ｎ／２対の既知のブロックがある。
【００２８】
図４は、相互排他的な移動の実施例を図示する。この実施例では、複数のブロックＢ１−Ｂ４は、配置されるシステム設計における構成要素を含む。ブロックＢ１は、最初に、第３列および第３行上のＶＬＥに存在する。ブロックＢ２は、最初に、第１行および第４列上のＶＬＥに存在する。ブロック３は、最初に、第４行および第１列上のＶＬＥに存在する。ブロックＢ４は、最初に、第４行および第２列上のＶＬＥに存在する。Ｂ２の位置へのブロックＢ１の移動は、Ｂ４への位置へのブロックＢ３の移動に関して相互排他的である。Ｂ２へのＢ１の移動は、行１−３および列３−４を覆う。Ｂ４へのＢ３の移動は、行１および列１−２を覆う。
【００２９】
図２を再び参照すると、２０７では、物理的配置ユニットによって配置されるように割り当てられる構成要素は、物理的配置ユニットにオフロードされる。本発明の実施形態によれば、物理的配置ユニットは、移動のコストを計算し、コストが所定の範囲内であれば移動を容認する。
【００３０】
２０８では、付加的な移動が考慮されるかどうかが決定される。本発明の実施形態によれば、反復の数が閾値数を越えていない場合、構成要素の配置と関連付けられるコストが閾値コスト値を超えない場合、または他の基準で、付加的な移動が考慮されてもよい。付加的な移動が考慮されない場合、制御は、配置結果が返信される２０９へと進む。付加的な移動が考慮される場合、制御は２０５に戻る。２０５に戻ると、ハードウェア配置ユニット上のＶＬＥは、ＭＰＵが付加的な配置オプションのために異なるＶＬＥ間で構成要素を移動させるコストを計算してもよい、異なる構成で区切られてもよい。本発明の実施形態によれば、配置スケジュール進行構成要素が、ハードウェア配置とソフトウェア配置との間で推移する。例えば、配置アニールの初めに、ブロックはタイミングに重要でなくてもよく、したがって、ハードウェア配置エンジンによって配置されてもよい。多数の配置反復後、この構成要素が最終的にタイミングに重要となることが可能である。この場合、ブロックは、タイミングに関して最適な配置を得るために、ソフトウェアプレーサに再び割り当てられる。ハードウェア配置ユニットおよびソフトウェア配置手順は、並行してＣＡＤツール作業を用いて実装される。ソフトウェア配置手順は、ハードウェア配置ユニットから返信される結果を取り込み、それらをその現在の配置の図と統合する。
【００３１】
図５ａ−ｄは、ブロックＡが異なるＶＬＥへと移動させられ、標的デバイス上のリソースによって実装されることを可能にするように、ＶＬＥのグループを異なる構成に区切ることの実施例を図示する。図５Ａは、ＶＬＥにおけるブロックが、それに水平に隣接して位置付けられた別のＶＬＥへと移動させられることを許可される、３つのセクションにＶＬＥが区切られることが示される、第１の水平区分構成を図示する。示されるように、最初に第２行および第２列上のＶＬＥに存在するブロックＡが、第２行および第１列上のＶＬＥへと移動させられてもよい。ブロック交換反復中に、全ブロックが場所をその近隣と交換する。例えば、図５Ａでは、列１内の全てのブロックが、列２内の近隣との交換を試行する。ｎが行または列内のＶＬＥの数である、一実施形態によれば、各ＭＰＵが相互とは無関係に動作する、並行して移動を計算するｎ／２ＭＰＵが存在する。
【００３２】
図５Ｂは、ＶＬＥにおけるブロックが、それに水平に隣接して位置付けられた別のＶＬＥへと移動させられることも許可される、２つのセクションにＶＬＥが区切られることが示される、第２の水平区分構成を図示する。示されるように、最初に第２行および第２列上のＶＬＥに存在するブロックＡが、第２行および第３列上のＶＬＥへと移動させられてもよい。
【００３３】
図５Ｃは、ＶＬＥにおけるブロックが、それに垂直に隣接して位置付けられた別のＶＬＥへと移動させられることも許可される、第１および第２行を含むセクションにＶＬＥが区切られることが示される、第１の垂直区分構成を図示する。示されるように、最初に第２行および第２列上のＶＬＥに存在するブロックＡが、第１行および第２列上のＶＬＥへと移動させられてもよい。
【００３４】
図５Ｄは、ＶＬＥにおけるブロックが、それに垂直に隣接して位置付けられた別のＶＬＥへと移動させられることも許可される、第２および第３行を含むセクションにＶＬＥが区切られることが示される、第２の垂直区分構成を図示する。示されるように、最初に第２行および第２列上のＶＬＥに存在するブロックＡが、第３行および第２列上のＶＬＥへと移動させられてもよい。交換距離を１に限定することによって、多大な程度の並列性が達成されてもよい。この実施例では、各ブロックに対する４つの移動方向に及ぶために、４回の反復が使用される。
【００３５】
図６は、本発明の実施形態による、ハードウェア支援配置を行うための方法を図示するフローチャートである。図６に図示される手順は、図１の１０４で使用されてもよい。６０１では、ネット境界が、移動させられるブロックと関連付けられるネットについて識別される。ネット境界は、標的デバイス上のネットを取り囲む境界ボックスを画定する。本発明の実施形態によれば、ネット境界は、ネットに対するネット境界要素（ＮＢＥ）から識別されてもよい。ネット境界要素は、標的設計上のネットの縁を表す。ＮＢＥは、チップがｘおよびｙ座標を伴う２次元面として見なされる、標的デバイスの左、右、上、および下を追跡するものとして見なすことができる。本発明の実施形態によれば、各ＮＢＥは、ネット境界のｘおよびｙ位置、ならびにネット境界上に存在するネットと関連付けられるＶＬＥの数のカウントを追跡する。６０１では、ＮＢＥは、その最初の場所で、およびその移動場所で、ブロックと関連付けられるネットについて識別される。
【００３６】
６０２では、ブロックの移動に応じて変更される、ネット境界上に存在するネットと関連付けられるＶＬＥの数を識別するカウントが決定される。ＶＬＥは、ネットに連結される構成要素を実装するために使用される場合に、ネットと関連付けられてもよい。本発明の実施形態によれば、カウントは、ネットについてＮＢＥから決定されてよい。
【００３７】
６０３では、ネット境界が移動とともに増加するかどうかが決定される。ネット境界は、ネットの境界ボックスの面積が増加する場合に増加する。ネット境界が増加する場合、制御は６０４へと進む。ネット境界が増加しない場合、制御は６０５へと進む。
【００３８】
６０４では、ネットに対するコストが１に設定される。
【００３９】
６０５では、ネット境界が移動とともに減少するかどうかが決定される。ネット境界は、ネットの境界ボックスの面積が減少する場合に減少する。ネット境界が減少する場合、制御は６０６へと進む。ネット境界が減少しない場合、制御は６０８へと進む。
【００４０】
６０６では、移動に応じて変更されるネット境界上に沿って存在する、ネットに連結される構成要素を実装するために使用される、ＶＢＥの数を識別するカウントが、１であるかどうかが決定される。ネットに対するカウントが１である場合、制御は６０７へと進む。ネットに対するカウントが１ではない場合、制御は６０８へと進む。
【００４１】
６０７では、ネットに対するコストが−１に設定される。
【００４２】
６０８では、ネットに対するコストが０に設定される。
【００４３】
６０９では、移動に対するコストが決定される。本発明の実施形態によれば、移動に対するコストは、ブロックを移動させることと関連付けられる全てのネットのコストの線形和を求めることによって生成されてもよい。本発明の代替実施形態によれば、ブロックを移動させるためのコストは、非線形方程式を使用して決定される。非線形方程式は、例えば、ワイヤ長さを予測するように、決定されたネットのコストに適用されてもよい。
【００４４】
６１０では、付加的なネットがブロックと関連付けられるかどうかが決定される。付加的なネットがブロックと関連付けられる場合、制御は６０１へと進み、評価されていないネットに関してブロックを移動させることと関連付けられるコストを評価する。付加的なネットがブロックと関連付けられない場合、制御は６１１へと進む。
【００４５】
６１１では、移動と関連付けられるコストが容認可能であるかどうかが決定される。移動のコストが容認可能ではない場合、制御は６１２へと進む。移動のコストが容認可能である場合、制御は６１３へと進む。
【００４６】
６１２では、移動が拒絶され、他の移動がブロックについて考慮されてもよい。
【００４７】
６１３では、ブロックが標的デバイス上の新しい場所へと移動させられる。古い場所および新しい場所でブロックを実装した標的デバイス上のリソースを表すＶＬＥ、およびブロックと関連付けられるネットに対するＮＢＥが更新される。
【００４８】
本発明の実施形態によれば、ブロックを移動させるためのコストが容認可能であるかどうかを決定するときに、第１のＶＬＥによって表される標的デバイス上の第１の場所から第２のＶＬＥによって表される第２の場所へとブロックを移動させることと関連付けられるコストが、第２のＶＬＥによって表される第２の場所から第１のＶＬＥによって表される第１の場所へと別のブロックを移動させることと関連付けられる任意のコストとともに考慮されてもよい。
【００４９】
図１、２、および６は、本発明の実施形態を図示するフローチャートである。図示される技術のうちのいくつかは、連続的に、並行して、または説明される順序および説明される手順が繰り返されてもよい順序以外の順序で行われてもよい。説明される技術の全てが行われることが要求されるわけではないこと、付加的な技術が追加されてもよいこと、および図示した技術のうちのいくつかが他の技術と置換されてもよいことを理解されたい。
【００５０】
図７ａ−ｃは、本発明の実施形態による、境界ボックスコストを計算することの実施例を図示する。図７ａ−７ｃは、標的デバイス上のリソースのマッピングを含む。リソースは、行および列に配列された複数のＶＬＥ７０１−７０５、７１１−７１５、７２１−７２５、および７３１−７３５を含む。図７ａは、システム設計における複数の構成要素を表す、ブロックＢ１を図示する。Ｂ１は、最初にＶＬＥ７２３によって表されるリソースによって実装される。Ｂ１は、ＶＬＥ７３３、７０３、および７１５によって表されるリソースに連結される、第１のネットを含む。第１のネットのネット境界は、境界ボックス７４１によって表される。ブロックＢ１が、ＶＬＥ７２４によって表されるリソースによって実装されるように移動するものである場合、第１のネットのネット境界は同じとなる。したがって、ＶＬＥ７２３からＶＬＥ７２４へＢ１を移動させるためのコストは、０となる。
【００５１】
図７ｂは、ブロックＢ１と関連付けられる第２のネットを図示する。第２のネットは、ＶＬＥ７３１および７３２によって表されるリソースに連結される。第２のネットのネット境界は、境界ボックス７５１によって表される。ブロックＢ１が、ＶＬＥ７２４によって表されるリソースによって実装されるように移動するものである場合、第２のネットのネット境界は、境界ボックス７５２によって表される。第２のネットの境界ボックスは増加する。したがって、ＶＬＥ７２３からＶＬＥ７２４へＢ１を移動させるためのコストは、１となる。
【００５２】
図７ｃは、ブロックＢ１と関連付けられる第３のネットを図示する。第３のネットは、ＶＬＥ７０４によって表されるリソースに連結される。第３のネットのネット境界は、境界ボックス７６１によって表される。ブロックＢ１が、ＶＬＥ７２４によって表されるリソースによって実装されるように移動するものである場合、第３のネットのネット境界は、境界ボックス７６２によって表される。第３のネットの境界ボックスは減少する。移動する境界上のネットと関連付けられるＶＬＥの数を識別するカウントは、１である。したがって、ＶＬＥ７２３からＶＬＥ７２４へＢ１を移動させるためのコストは、−１となる。
【００５３】
この実施例では、Ｂ１を移動させるための正味コストの合計は、０となる。Ｂ２によって表される構成要素をＶＬＥ７２３によって表される場所へと移動させることと関連付けられるコストは、Ｂ１が移動されるべきかどうかを決定するときに計上されてもよいことを理解されたい。
【００５４】
図８は、本発明の実施形態による、ハードウェア配置ユニットを実装するために使用されてもよい、デバイス８００を図示する。デバイス８００は、複数の論理アレイブロック（ＬＡＢ）を含む、フィールドプログラマブルゲートアレイ（ＦＰＧＡ）である。各ＬＡＢは、複数の論理ブロック、キャリーチェーン、ＬＡＢ制御信号（参照テーブル）ＬＵＴチェーン、およびレジスタチェーン接続ラインから形成されてもよい。論理ブロックは、ユーザ論理関数の効率的な実装を提供する、論理の小単位である。論理ブロックは、１つ以上の組み合わせセルを含み、各組み合わせセルは、単一の出力およびレジスタを有する。本発明の一実施形態によれば、論理ブロックは、Ａｌｔｅｒａ（登録商標）  Ｃｏｒｐｏｒａｔｉｏｎによって製造されているＳｔｒａｔｉｘまたはＣｙｃｌｏｎｅデバイスで見られるもの等の論理要素（ＬＥ）、またはＸｉｌｉｎｘ  Ｉｎｃ．によって製造されているＶｉｒｔｅｘデバイスで見られるもの等の組み合わせ論理ブロック（ＣＬＢ）と同様に動作してもよい。この実施形態では、論理ブロックは、構成可能なレジスタを伴う４入力参照テーブル（ＬＵＴ）を含んでもよい。本発明の代替実施形態によれば、論理ブロックは、Ａｌｔｅｒａ  Ｃｏｒｐｏｒａｔｉｏｎによって製造されているＳｔｒａｔｉｘデバイスで見られるもの等の適応論理モジュール（ＡＬＭ）と同様に動作してもよい。ＬＡＢは、デバイス８００を横断する行および列にグループ化される。ＬＡＢの列は、８１１−８１６として示される。論理ブロックは、付加的または代替的な構成要素を含んでもよいことを理解されたい。
【００５５】
デバイス８００は、メモリブロックを含む。メモリブロックは、例えば、最大で種々の周波数で最大で種々のビット幅の専用の真のデュアルポート、単純デュアルポート、または単一ポートメモリを提供する、二重ポートランダムアクセスメモリ（ＲＡＭ）ブロックであってもよい。メモリブロックは、選択されたＬＡＢの間でデバイスを横断する列にグループ化されるか、またはデバイス８００内で個別に、あるいは対になって位置してもよい。メモリブロックの列は、８２１−８２４として示される。
【００５６】
デバイス８００は、デジタル信号処理（ＤＳＰ）ブロックを含む。ＤＳＰブロックは、加算または減算特徴を伴う種々の構成の乗算器を実装するために使用されてもよい。ＤＳＰブロックは、シフトレジスタ、乗算器、加算器、および累算器を含む。ＤＳＰブロックは、デバイス８００を横断する列にグループ化されてもよく、８３１として示される。
【００５７】
デバイス８００は、複数の入出力要素（ＩＯＥ）８４０を含む。各ＩＯＥは、デバイス８００上のＩＯピン（図示せず）にデータ入力する。ＩＯＥ８４０は、デバイス８００の周囲のＬＡＢ行および列の末端に位置する。各ＩＯＥは、双方向ＩＯバッファと、入力、出力、および出力使用可能信号を登録するための複数のレジスタとを含んでもよい。
【００５８】
デバイス８００は、標的デバイス上の構成要素間で信号を経路指定するように、ＬＡＢローカル相互接続ライン、行相互接続ライン（「Ｈ型ワイヤ」）、および列相互接続ライン（「Ｖ型ワイヤ」）（図示せず）等の経路指定リソースを含んでもよい。
【００５９】
図８は、ハードウェア配置ユニットを実装するために使用されるデバイスの例示的実施形態を図示する。また、上記で示されるように、デバイスは、異なる方式で配列される同じまたは異なる半導体デバイスを含んでもよいことも理解されたい。デバイス８００はまた、図８に図示されるデバイスを参照して説明および図示されるもの以外のＦＰＧＡリソースを含んでもよい。したがって、本明細書で説明される発明の実施形態は、図８で説明されるアーキテクチャ上で利用されてもよいが、また、異なるアーキテクチャ上で利用されてもよいことを理解されたい。
【００６０】
図９は、本発明の例示的実施形態による、ハードウェア配置ユニットの構成要素間の相互作用を図示する。ハードウェア配置ユニットは、複数のＭＰＵを含み、そのうちの１つがＭＰＵ９１０として図９で示される。ＭＰＵ９１０は、ブロックを移動させることと関連付けられるコストを計算するように、１つ以上のＬＡＢまたはＦＰＧＡ上の他のリソースによって実装されてもよい。
【００６１】
ハードウェア配置ユニットは、ＶＬＥの行または列を記憶する、第１の複数のメモリ９２１−９２２を含む。ハードウェア配置ユニットはまた、ＮＢＥの行または列を記憶する、第２の複数のメモリ９３１−９３２も含む。メモリ９２１−９２２および９３１−９３２は、１つ以上のＭ４Ｋ、Ｍ５１２、またはＦＰＧＡ上の他のメモリブロックによって実装されてもよい。
【００６２】
ＭＰＵ９１０は、メモリ９２１−９２２に記憶されたＶＬＥからのブロックに関する情報、およびメモリ９３１−９３２に記憶されたＮＢＥからのネット境界に関する情報にアクセスすることによって、ＶＬＥ間でブロックを移動させることと関連付けられるコストを計算する。メモリ９２１−９２２からアクセスされる情報は、ＶＬＥによって表されるブロックと関連付けられるネットの識別を含んでもよい。メモリ９３１−９３２からアクセスされる情報は、ブロックと関連付けられるネットのネット境界と、ネットの境界に沿って存在するＶＬＥのカウントとを含んでもよい。
【００６３】
本発明の実施形態は、配置時間を削減するように、ＦＰＧＡの並列計算能力を利用するための方法を提供する。ソフトウェア配置手順の融通性を維持し、また、ＦＰＧＡの並列処理能力も利用する、ハイブリッドソフトウェア・ハードウェアプレーサが開示される。ブロックを移動させるためのコストを計算することは、有意量の時間を必要とする。境界ボックスコストおよびタイミング計算といった２つの主要コスト指標が、コスト計算で使用される。
【００６４】
過去に、境界ボックスコストは、ブロックの各ネットを通して反復することによって計算された。これらの計算は、ネットの高い相互接続性により複雑であった。加えて、典型的な移動で使用されたアクセスパターンは、設計における任意のブロックに影響を及ぼす可能性があった。これは、移動を別個の独立した実行単位に分離することを困難にした。依存性が２つの移動の間に存在したとき、移動の並列実行が不正確なコスト計算をもたらし得た。さらに、タイミング計算は、デバイス特有の遅延計算に大きく依存する。これは、キャッシュに格納した遅延への高速メモリアクセスを必要とする。
【００６５】
本発明の実施形態は、データアクセスを局限することによって、境界ボックスコストを実施するための改良型技術を提供する。各ネットの高度に分散した論理出力数を横断するよりもむしろ、ネット縁（境界）が横断される。境界ボックスが増加するか減少するかは、ネット縁に沿って存在するブロックの数を決定することによって推定されてもよい。所与の縁に沿ったＶＬＥへのデータアクセスを要求することによって、データアクセスは、ＶＬＥの特定の行または列に局限される。本発明の実施形態によれば、ＶＬＥの行または列内のｎ個のブロック全てに対するデータが、キャッシュに格納されてもよい。キャッシュに格納したデータは、ｎ個のブロックの移動に使用されてもよい。ブロックが移動させられた場合、キャッシュに格納したデータが古くなることを回避するように、増分更新がキャッシュに格納したデータに行われてもよい。境界ボックス縁が反復間で変化すると、キャッシュに格納したデータは、最初から再計算されてもよい。ブロックネットデータがハードウェアを通してパイプラインで運ばれてもよく、行または列内の各ネットにインデックスを付けるメモリ参照テーブルが使用されてもよく、またはバイナリソートしたアプローチに基づく並列ハッシュを使用することができる。
【００６６】
本発明の実施形態は、また、相互排他的な移動を画定することによって、境界ボックスコストを実施するための改良型技術を提供する。ＭＰＵによって並行して行われる移動は、コスト計算に使用される古くなったデータを排除するように、相互排他的な移動に限定される。本発明の実施形態によれば、２つの個別移動は、移動によって覆われる行および列が交差しない場合に相互排他的である。ＶＬＥ間の交換距離を限定することによって、並行して発生することができる潜在的な移動候補の数が増加させられる。本発明の実施形態によれば、最大数の相互排他的な移動を考慮するために、隣接する水平および垂直移動のみが考慮される。ブロックのｎ×ｎ行列を考慮すると、同時に交換することができる、最大ｎ／２対の既知のブロックがある。
【００６７】
本発明の実施形態によれば、ハードウェア配置ユニットは、非タイミング重要ブロックで配置を行う。ＣＡＤツールにおけるソフトウェア配置手順は、タイミング重要ブロックを処理する。ハードウェア配置ユニットおよびソフトウェア配置手順は、一緒に稼働して、最適である、システムが動作することができる最大頻度を含む、配置解決法を生成してもよい。
【００６８】
図１０は、本発明の例示的実施形態による、システム設計を拡大縮小するための処理ウィンドウ１０１０を図示する。大型システム設計を計算するとき、ハードウェア配置ユニットのメモリおよび領域制限が効率的に動作することを可能にするために、システム設計を細分する必要があってもよい。処理ウィンドウ１０１０は、システム設計におけるブロックの一部で移動を行うように導入される。各ネット縁は、関連固定境界ボックス値を有する。値は、処理ウィンドウ１０１０の外側のネットに属するブロックによって決定されてもよい。帯域幅要件を低減するために、処理ウィンドウ１０１０は、実際のシステム設計にわたって増分的にスキャンする。
【００６９】
図１１は、本発明の実施形態例が存在する、例示的なコンピュータシステム１１００のブロック図である。示されるように、コンピュータシステム１１００は、プロセッサ１１０１を含む。プロセッサ１１０１は、プロセッサ１１０１とコンピュータシステム１１００内の他の構成要素との間でデータ信号を伝送する、ＣＰＵバス１１１０に連結される。
【００７０】
コンピュータシステム１１００は、メモリ１１１３を含む。メモリ１１１３は、動的ランダムアクセスメモリデバイス、静的ランダムアクセスメモリデバイス、および／または他のメモリデバイスであってもよい。メモリ１１１３は、プロセッサ１１０１によって実行されてもよい、データ信号によって表される命令およびコードを記憶してもよい。ブリッジメモリコントローラ１１１１が、ＣＰＵバス１１１０およびメモリ１１１３に連結される。ブリッジメモリコントローラ１１１１は、プロセッサ１１０１、メモリ１１１３、およびコンピュータシステム１１００内の他の構成要素の間でデータ信号を方向付け、ＣＰＵバス１１１０、メモリ１１１３、および第１のＩＯバス１１２０の間でデータ信号を橋渡しする。
【００７１】
第１のＩＯバス１１２０は、単一のバスまたは複数のバスの組み合わせであってもよい。第１のＩＯバス１１２０は、コンピュータシステム１１００内の構成要素間に通信リンクを提供する。ネットワークコントローラ１１２１は、第１のＩＯバス１１２０に連結される。ネットワークコントローラ１１２１は、コンピュータシステム１１００をコンピュータのネットワーク（図示せず）に結び付け、機械間の通信をサポートする。表示デバイスコントローラ１１２２が、第１のＩＯバス１１２０に連結される。表示デバイスコントローラ１１２２は、コンピュータシステム１１００への表示デバイス（図示せず）の連結を可能にし、表示デバイスとコンピュータシステム１１００との間のインターフェースの役割を果たす。
【００７２】
第２のＩＯバス１１３０は、単一のバスまたは複数のバスの組み合わせであってもよい。第２のＩＯバス１１３０は、コンピュータシステム１１００内の構成要素間に通信リンクを提供する。データ記憶デバイス１１３１が、第２のＩＯバス１１３０に連結される。データ記憶デバイス１１３１は、ハードディスクドライブ、フロッピー（登録商標）ディスクドライブ、ＣＤ−ＲＯＭデバイス、フラッシュメモリデバイス、または他の大容量記憶デバイスであってもよい。入力インターフェース１１３２が、第２のＩＯバス１１３０に連結される。入力インターフェース１１３２は、コンピュータシステム１１００への入力デバイスの連結を可能にし、入力デバイスからコンピュータシステム１００へデータ信号を伝送する。バスブリッジ１１２３が、第１のＩＯバス１１２０を第２のＩＯバス１１３０に連結する。バスブリッジ１１２３は、データ信号をバッファに格納し、第１のＩＯバス１１２０と第２のＩＯバス１１３０との間でデータ信号を橋渡しするように動作する。異なるアーキテクチャを有するコンピュータシステムもまた、コンピュータシステム１１００を実装するために使用されてもよいことを理解されたい。
【００７３】
システムデザイナ１１４０が、メモリ１１１３の中に存在し、プロセッサ１１０１によって実行されてもよい。システムデザイナ１１４０は、システムを合成する、標的デバイス上にシステムを配置する、システムを経路指定する、システムを組み立てる、およびシステムを実装するよう標的デバイスをプログラムするように、動作してもよい。
【００７４】
図１２は、本発明の例示的実施形態による、システムデザイナ１２００を図示する。システムデザイナ１２００は、図１１に示されるシステムデザイナ１１４０を実装するために使用されてもよく、図１および２で説明される手順の一部を行ってもよい。システムデザイナ１２００は、標的デバイス上でシステムを設計するためのＣＡＤツールであってもよい。標的デバイスは、例えば、ＡＳＩＣ、構造化ＡＳＩＣ、ＦＰＧＡ、プログラマブル論理デバイス（ＰＬＤ）、プリント回路基板（ＰＣＢ）、または他の回路であってもよい。図１２は、システムデザイナ１２００の実施形態を実装するモジュールを図示する。一実施形態によれば、システム設計は、図１２に示されるモジュールによって表される命令のシーケンスを実行するコンピュータシステム（図示せず）によって行われてもよい。命令のシーケンスの実行は、以降で説明されるように、コンピュータシステムにシステム設計をサポートさせる。代替実施形態では、本発明を実装するために、ソフトウェア命令の代わりに、またはソフトウェア命令と組み合わせて、ハードワイヤ回路が使用されてもよい。したがって、本発明は、ハードウェア回路およびソフトウェアの任意の特定の組み合わせに限定されない。システムデザイナ１２００は、システムデザイナマネージャ１２１０を含む。システムデザイナマネージャ１２１０は、システムデザイナ１２００の構成要素に接続され、それらの間でデータを伝送する。システム設計マネージャ１２１０はまた、システムデザイナ１２００に入力される設計情報に精緻化を行ってもよい。精緻化は、情報の構文が正しいことを確実にするように、設計情報を再検討することを含んでもよい。
【００７５】
ブロック１２２０は、合成ユニットを表す。合成ユニット１２２０は、標的デバイスで実装されるシステムの論理設計を生成する。システムデザイナ１２００の実施形態によれば、合成ユニット１２２０は、概念的ハードウェア記述言語（ＨＤＬ）設計定義を取り込み、システムの最適化論理表現を生成する。合成ユニット１２２０によって生成されるシステムの最適化論理表現は、システムに必要とされる、論理ゲートおよび論理要素等の最小化した数の機能ブロックおよびレジスタを有する表現を含んでもよい。代替として、合成ユニット１２２０によって生成されるシステムの最適化論理表現は、論理の低減した深さを有し、より低い信号伝搬遅延を生成する表現を含んでもよい。合成ユニット１２２０はまた、標的デバイス上の特定のリソースを利用して、最適化論理表現において機能ブロックおよびレジスタをどのように実装するかも決定し、したがって、最適化「技術マッピング」ネットリストを作成する。技術マッピングネットリストは、システムを実装するために、標的デバイス上のリソース（構成要素）がどのように利用されるかを図示する。標的デバイスがＦＰＧＡである実施形態では、構成要素は、論理要素または適応論理モジュールとなり得る。標的デバイスがＡＳＩＣである実施形態では、構成要素は、ゲートまたは標準セルとなり得る。標的デバイスが構造化ＡＳＩＣである実施形態では、技術マッピングネットリストは、ＲＡＭブロック、乗算器ブロック、およびゲートのライブラリからのゲート等の構造化ＡＳＩＣファブリックで実装することができる、構成要素を含有してもよい。
【００７６】
ブロック１２３０は、配置準備ユニットを表す。配置準備ユニット１２３０は、最適化技術マッピングネットリスト内の構成要素を識別し、どの構成要素を配置のためにＣＡＤ配置手順に割り当てるか、およびどの構成要素を配置のためにハードウェア配置ユニットに割り当てるかを決定する。本発明の実施形態によれば、配置準備ユニット１２３０は、標的デバイス上のリソースをハードウェア配置ユニット上のＶＬＥにマップし、ＶＬＥを区分に区切り、ＭＰＵをＶＬＥ区分のそれぞれに割り当て、ＭＰＵがＶＬＥのブロック（システム設計における構成要素）を配置する反復を設定する。配置準備ユニット１２３０はまた、ＭＰＵが並行して行ってもよい相互排他的な移動を識別してもよい。
【００７７】
ブロック１２４０は、ＣＡＤ配置手順によって実装される配置ユニットを表す。配置ユニット１２４０は、標的デバイス上のどの構成要素または領域が、特定の機能ブロックおよびレジスタに使用されるかを決定することによって、標的デバイス上にシステムを配置する。システムデザイナ１２００の実施形態によれば、配置ユニット１２４０は、最初に、クラスタで最適化論理設計の複数部分をどのように実装するかを決定する。クラスタは、論理設計上の構成要素の一部を表してもよい。クラスタは、例えば、一緒にグループ化されたいくつかの標準セルによって表されてもよい。この実施形態では、最適化論理設計の複数部分がクラスタで実装された後、クラスタは、標的デバイス上の特定の部分にクラスタを割り当てることによって配置されてもよい。配置ユニット１２４０は、標的デバイス上のリソースの良好な割当を決定するために、コスト関数を利用してもよい。
【００７８】
ブロック１２５０は、経路指定ユニットを表す。経路指定ユニット１２５０は、論理設計の機能ブロックおよびレジスタを実装する構成要素間の相互接続を提供するために使用する、標的デバイス上の経路指定リソースを決定する。
【００７９】
ブロック１２６０は、組み立てユニットを表す。組み立てユニット１２６０は、システムデザイナ８００によって行われる編集手順によって決定される情報を含む、データファイルを作成する。データファイルは、標的デバイスをプログラムするために使用されてもよい、ビットストリームであってもよい。本発明の実施形態によれば、生成されるデータファイルは、システムの設計がさらに処理されることを可能にするように、別のコンピュータシステムに伝送されてもよい。代替として、データファイルは、システム設計に従って標的デバイスをプログラムするために使用されてもよい、別のコンピュータシステムに伝送されてもよい。データファイルで標的デバイスをプログラムすることによって、標的デバイス上の構成要素は、システムを実装するように物理的に変換される。システムの設計は、表示デバイスまたは他の媒体上等で、他の形態で出力されてもよいことを理解されたい。
【００８０】
図１３は、本発明の例示的実施形態による、配置準備ユニット１３００を図示する。配置準備ユニット１３００は、図１２に図示される配置準備ユニット１２３０を実装し、図２に図示される手順を行うために使用されてもよい。代替として、配置準備ユニット１３００の複数部分は、ハードウェア配置ユニットによって実装されてもよい。配置準備ユニット１３００は、配置準備マネージャユニット（ＰＰＭＵ）１３１０を含む。配置準備マネージャユニット１３１０は、配置準備マネージャユニット１３１０内の構成要素に接続され、それらの間で情報を伝送する。
【００８１】
ブロック１３２０は、タイミングユニットを表す。タイミングユニット１３２０は、配置される構成要素が、閾値以上または以下であるタイミング必要条件を有するかどうかを決定する。これは、構成要素がタイミングに関する重要構成要素であるか、重要信号と関連付けられるか、またはクリティカルパス上にあるかどうかを決定してもよい。構成要素が閾値以上または以下であるタイミング必要条件を有すると決定された場合、構成要素は、コンピュータシステムによってソフトウェアで実装されるＣＡＤツールを使用して配置される構成要素として識別される。
【００８２】
ブロック１３３０は、構成要素種類識別子ユニットを表す。構成要素種類識別子ユニット１３３０は、構成要素が１組の構成要素に属する種類であるかどうかを決定する。本発明の実施形態によれば、１組の構成要素は、入出力（ＩＯ）、メモリ、およびデジタル信号プロセッサ（ＤＳＰ）のうちの１つ以上、または他の種類の構成要素を含んでもよい。構成要素が１組の構成要素に属する種類である場合、構成要素は、物理的配置ユニットを使用して配置される構成要素として識別される。
【００８３】
ブロック１３４０は、区分ユニットを表す。区分ユニット１３４０は、構成要素に割り当てられるために利用可能なリソースを、ハードウェア配置ユニット上のＶＬＥにマップする。区分ユニット１３４０は、ＶＬＥをセクションに区切り、ＭＰＵをセクションのそれぞれに割り当てる。配置の反復中に、ＭＰＵは、各セクション内のＶＬＥ間で構成要素を移動するコストを計算する。
【００８４】
ブロック１３５０は、相互排他的移動識別子（ＭＥＭＩ）ユニットを表す。ＭＥＭＩユニット１３５０は、配置のために考慮される相互排他的な移動を識別する。本発明の実施形態によれば、移動によって覆われる行／列が交差しない場合、２つの個別移動は相互排他的である。
【００８５】
配置準備マネージャユニット１３１０は、物理的配置ユニットによって配置されるように割り当てられる構成要素の配置を、物理的ユニットにオフロードする。構成要素の配置をオフロードすることは、１つのＶＬＥ場所から第２のＶＬＥ場所へと、ブロックを形成する構成要素または構成要素群を移動させることと関連付けられるコストを、物理的配置ユニットに計算させることを伴ってもよい。配置準備ユニット１３００は、移動の数回の反復、コストの合計、およびコストが容認可能であるかどうかという評価をサポートしてもよいことを理解されたい。代替として、物理的配置ユニットは、チップ上のこれらの機能性のうちのいくつかを果たすように構成されてもよい。配置結果が物理的配置ユニットによって生成された場合、配置準備マネージャユニット１３１０は、システム設計に対する配置解決法を生成するために、物理的配置ユニットおよびＣＡＤツールからの配置結果を利用する。
【００８６】
本発明の実施形態は、命令を有するコンピュータ読み取り可能または機械読み取り可能媒体を含んでもよい、コンピュータプログラム製品、またはソフトウェアとして提供されてもよい。コンピュータ読み取り可能または機械読み取り可能媒体上の命令は、コンピュータシステムまたは他の電子デバイスをプログラムするために使用されてもよい。機械読み取り可能媒体は、フロッピー（登録商標）ディスク、光ディスク、ＣＤ−ＲＯＭ、光磁気ディスク、または電子命令を記憶するために好適な他の種類の媒体／機械読み取り可能媒体を含んでもよいが、それらに限定されない。本明細書で説明される技術は、いずれの特定のソフトウェア構成にも限定されない。それらは、任意の計算または処理環境で適用性を見出してもよい。本明細書で使用される「コンピュータ読み取り可能媒体」または「機械読み取り可能媒体」という用語は、コンピュータによって実行するための命令のシーケンスを記憶または符号化することが可能であり、本明細書で説明される方法のうちのいずれか１つをコンピュータに行わせる、任意の媒体を含むものとする。さらに、当技術分野では、１つの形態または別の形態（例えば、プログラム、手順、プロセス、アプリケーション、モジュール、ユニット、論理等）のソフトウェアを、措置を講じる、または結果を引き起こすものであると言うことが一般的である。そのような表現は、処理システムによるソフトウェアの実行が、結果を生じる動作をプロセッサに行わせることを述べる簡便な方法にすぎない。
【００８７】
先述の明細書では、本発明の実施形態は、その具体的な例示的実施形態を参照して説明されている。しかしながら、本発明の実施形態のより広い精神および範囲から逸脱することなく、種々の修正および変更が行われてもよいことが明白となるであろう。したがって、本明細書および図面は、制限的な意味よりもむしろ例証的な意味で見なされるものである。
【図３】
0005544427.tif 000002
【図７Ａ】
0005544427.tif 000003
【図７Ｂ】
0005544427.tif 000004
【図７Ｃ】
0005544427.tif 000005
【図８】
0005544427.tif 000006
【図１】
0005544427.tif 000007
【図２】
0005544427.tif 000008
【図４】
0005544427.tif 000009
【図５】
0005544427.tif 000010
【図６】
0005544427.tif 000011
【図９】
0005544427.tif 000012
【図１０】
0005544427.tif 000013
【図１１】
0005544427.tif 000014
【図１２】
0005544427.tif 000015
【図１３】
0005544427.tif 000016