集積回路のコンピュータ支援設計ソフトウェアをパラレル化する装置および方法
【課題】コンピュータ支援設計（ＣＡＤ）ソフトウェアのパラレル化を提供する。
【解決手段】コンピュータを備えるコンピュータ支援設計（ＣＡＤ）ソフトウェアのパラレル化を提供するシステムであって、該コンピュータは、該タスクのセットの各タスクをパラレルに実行されるように割り当てることと、該タスクのセットの各タスクを実行することとを行うように構成される、システム。本発明のコンセプトの一局面は、ＰＬＤ ＣＡＤソフトウェアのようなＣＡＤソフトウェアをパラレル化する方法に関する。一実施形態において、本発明に従う方法は、独立性を有するタスクのセットを同定することと、このタスクのセットの各タスクをパラレルに実行されるように割り当てることとを含む。この方法は、このタスクのセットの各タスクを実行することをさらに含む。
【解決手段】コンピュータを備えるコンピュータ支援設計（ＣＡＤ）ソフトウェアのパラレル化を提供するシステムであって、該コンピュータは、該タスクのセットの各タスクをパラレルに実行されるように割り当てることと、該タスクのセットの各タスクを実行することとを行うように構成される、システム。本発明のコンセプトの一局面は、ＰＬＤ ＣＡＤソフトウェアのようなＣＡＤソフトウェアをパラレル化する方法に関する。一実施形態において、本発明に従う方法は、独立性を有するタスクのセットを同定することと、このタスクのセットの各タスクをパラレルに実行されるように割り当てることとを含む。この方法は、このタスクのセットの各タスクを実行することをさらに含む。
【発明の詳細な説明】
【技術分野】
【０００１】
（関連出願の相互参照）
本出願は、米国仮特許出願第６０／７７２，７４７号（２００６年２月１３日出願、発明の名称「Ａｐｐａｒａｔｕｓ ａｎｄ Ｍｅｔｈｏｄｓ ｆｏｒ Ｐａｒａｌｌｅｌｉｚｉｎｇ Ｓｏｆｔｗａｒｅ」、代理人整理番号第ＡＬＴＲ：０５５ＰＺ１号）の利益を主張し、該仮特許出願を本明細書にて参照することによって援用する。
【０００２】
（技術分野）
一般的に、開示されるコンセプトは、ソフトウェアおよびアルゴリズムをパラレル化する装置および方法に関する。より特定的には、プログラマブルロジックデバイス（ＰＬＤ）のような集積回路（ＩＣ）用のコンピュータ支援設計（ＣＡＤ）ソフトウェアをパラレル化する装置および方法に関する。
【背景技術】
【０００３】
(背景）
伝統的に、プロセッサ（例えば、Ｉｎｔｅｌ製のＰｅｎｔｉｕｍ（登録商標）シリーズ、ＡＭＤ製のＡｔｈｌｏｎシリーズなど）は、ますます速くなるクロック速度をサポートすることによって、ますます高速化してきた。プロセッサが、このようにますます高速になるにつれ、これらプロセッサ上でソフトウェアの特定のピースを稼動させるのに要する時間は、それに比例するように自動的に高速化される（なぜなら、単一のコード命令を実行する時間は、プロセッサクロックの速度に概ね比例するからである）。
【０００４】
しかしながら、今日市販されている新世代のプロセッサは、２年前のもの（約３ＧＨｚ）よりも、顕著に速いクロックを使用していない。その代わりに、今日では、これらのプロセッサチップは、そのチップの中に２つ以上のプロセッサを含んでいる（例えば、Ｐｅｎｔｉｕｍ（登録商標） Ｄは、「デュアルコア」であり、１つのチップに２つのミニプロセッサを有することを意味する）。この特性は、コンピュータが同時に、幾つかの実行する「スレッド」を同時に稼動することを可能にする。
【発明の開示】
【発明が解決しようとする課題】
【０００５】
任意のシリアルなソフトウェア（ソフトウェアが、一度に実行する１つのタスクを有することを意味する）は、これらチップ内の追加的なプロセッサを利用可能にしても、高速化しない。追加の処理能力を引き上げるには、シリアルソフトウェアは、パラレル化される必要がある。つまり、シリアルソフトウェアは、全てのプロセッサをビジーに保つためにすぐに実行されるべき複数のタスクを有さなければならない。残念なことに、このパラレル化は、必ずと言ってもよいほど、自動的に行われない。それは、ソフトウェアコードの変更を必然的にともなうからである。また、変更自体も、かなり巧妙である。それは、シリアルソフトウェアの根底にある仮定の多くは、パラレルソフトウェアでは通用しないからである。それゆえ、ＣＡＤソフトウェアのようなソフトウェアをパラレル化するニーズが存在する。
【課題を解決するための手段】
【０００６】
（概要）
開示される新たなコンセプトは、ＣＡＤソフトウェアおよびアルゴリズムのようなソフトウェアをパラレル化する装置および方法に関する。本発明のコンセプトの一局面は、ＰＬＤ ＣＡＤソフトウェアのようなＣＡＤソフトウェアをパラレル化する方法に関する。一実施形態において、本発明に従う方法は、独立性を有するタスクのセットを同定することと、このタスクのセットの各タスクをパラレルに実行されるように割り当てることとを含む。この方法は、このタスクのセットの各タスクを実行することをさらに含む。
【０００７】
本発明の別の局面は、ソフトウェアをパラレル化するシステムに関する。このシステムは、上述したパラレル化方法を実行するように構成されたコンピュータを含む。本発明のコンセプトのさらなる別の局面は、コンピュータプログラム製品に関する。この製品は、ソフトウェアをパラレル化するコンピュータによる処理をするように適合されたコンピュータアプリケーションを含む。コンピュータアプリケーションは、上述したソフトウェアパラレル化方法をコンピュータに実行させる。
【０００８】
上記課題を解決するために、本発明は、以下を提供する：
（項目１）
コンピュータを備えるコンピュータ支援設計（ＣＡＤ）ソフトウェアのパラレル化を提供するシステムであって、該コンピュータは、
独立性を有するタスクのセットを同定することと、
該タスクのセットの各タスクをパラレルに実行されるように割り当てることと、
該タスクのセットの各タスクを実行することと
を行うように構成される、システム。
【０００９】
（項目２）
上記コンピュータは、上記タスクのセットを用いて待ち行列をロードするように構成される、項目１に記載のシステム。
【００１０】
（項目３）
上記待ち行列は、上記パラレル化されたＣＡＤソフトウェアがシリアルアルゴリズムと同様の結果を生成するように、シリアルＣＡＤアルゴリズムと同様な順番でロードされる、項目２に記載のシステム。
【００１１】
（項目４）
上記タスクのセットは、上記待ち行列内に保持される独立なアクションの数を最大化するように選択される、項目２に記載のシステム。
【００１２】
（項目５）
上記タスクは、任意の順番で実行される、項目４に記載のシステム。
【００１３】
（項目６）
上記待ち行列は、上記タスクのセットが実行される前に、該タスクのセットの全てのタスクを用いてロードされる、項目２に記載のシステム。
【００１４】
（項目７）
上記待ち行列は、上記タスクのセットが実行されている間に、追加のタスクが提案されることを可能にする強化待ち行列を備える、項目２に記載のシステム。
【００１５】
（項目８）
複数のスレッドが、実行されるべきそれぞれのタスクを決定し、該タスクを待ち行列に追加する、項目２に記載のシステム。
【００１６】
（項目９）
スレッドが、他のタスクに依存する場合に、タスクを再生する、項目８に記載のシステム。
【００１７】
（項目１０）
上記ＣＡＤソフトウェアは、プログラマブルロジックデバイス（ＰＬＤ）内のリソースを配置するための配置アルゴリズムを備える、項目１に記載のシステム。
【００１８】
（項目１１）
上記ＣＡＤソフトウェアは、パラレル解析アルゴリズムを備える、項目１に記載のシステム。
【００１９】
（項目１２）
コンピュータ支援設計（ＣＡＤ）ソフトウェアをパラレル化するようにコンピュータによって処理するために適合したコンピュータアプリケーションを備える、コンピュータプログラム製品であって、
該コンピュータアプリケーションは、該コンピュータに
独立性を有するタスクのセットを同定することと、
該タスクのセットの各タスクをパラレルに実行されるように割り当てることと、
該タスクのセットの各タスクを実行することと
を行わせるように構成される、コンピュータプログラム製品。
【００２０】
（項目１３）
上記タスクのセットを用いて上記コンピュータに待ち行列をロードさせる、項目１２に記載のコンピュータプログラム製品。
【００２１】
（項目１４）
上記パラレル化されたＣＡＤソフトウェアがシリアルアルゴリズムと同様の結果を生成するように、シリアルＣＡＤアルゴリズムと同様な順番で上記コンピュータに上記待ち行列をロードさせる、項目１３に記載のコンピュータプログラム製品。
【００２２】
（項目１５）
上記待ち行列内に保持される独立なアクションの数を最大化するように、上記コンピュータに上記タスクのセットを選択させる、項目１３に記載のコンピュータプログラム製品。
【００２３】
（項目１６）
上記コンピュータに、上記タスクを任意の順番で実行させる、項目１５に記載のコンピュータプログラム製品。
【００２４】
（項目１７）
上記タスクのセットが実行される前に、該タスクのセットの全てのタスクを用いて上記待ち行列を上記コンピュータにロードさせる、項目１３に記載のコンピュータプログラム製品。
【００２５】
（項目１８）
上記タスクのセットが実行されている間に、追加のタスクが提案されることを可能にする強化待ち行列を、上記コンピュータに使用させる、項目１３に記載のコンピュータプログラム製品。
【００２６】
（項目１９）
実行されるべきそれぞれのタスクを決定し、該タスクを待ち行列に追加する複数のスレッドを、上記コンピュータに使用させる、項目１３に記載のコンピュータプログラム製品。
【００２７】
（項目２０）
他のタスクに依存する場合に、タスクを再生するスレッドを、上記コンピュータに使用させる、項目１９に記載のコンピュータプログラム製品。
【００２８】
（項目２１）
プログラマブルロジックデバイス（ＰＬＤ）内のリソースの配置を、上記コンピュータに実行させる、項目１２に記載のコンピュータプログラム製品。
【００２９】
（項目２２）
パラレル解析アルゴリズムを、上記コンピュータに実行させる、項目１２に記載のコンピュータプログラム製品。
【００３０】
（項目２３）
コンピュータ支援設計（ＣＡＤ）ソフトウェアをパラレル化する方法であって、該方法は、
独立性を有するタスクのセットを同定することと、
該タスクのセットの各タスクをパラレルに実行されるように割り当てることと、
該タスクのセットの各タスクを実行することと
を包含する、方法。
【００３１】
（項目２４）
上記タスクのセットを用いて待ち行列をロードすることをさらに包含する、項目２３に記載の方法。
【００３２】
（項目２５）
上記パラレル化されたＣＡＤソフトウェアがシリアルアルゴリズムと同様な結果を生成するように、シリアルＣＡＤアルゴリズムと同様な順番で待ち行列をロードすることをさらに包含する、項目２４に記載の方法。
【００３３】
（項目２６）
上記タスクのセットを、上記待ち行列内に保持される独立なアクションの数を最大化するように選択することをさらに包含する、項目２４に記載の方法。
【００３４】
（項目２７）
上記タスクを任意の順番で実行することをさらに包含する、項目２６に記載の方法。
【００３５】
（項目２８）
上記タスクのセットが実行される前に、該タスクのセットの全てのタスクを用いて上記待ち行列をロードすることをさらに包含する、項目２４に記載の方法。
【００３６】
（項目２９）
上記待ち行列は、上記タスクのセットが実行されている間に、追加のタスクが提案されることを可能にする強化待ち行列を備える、項目２４に記載の方法。
【００３７】
（項目３０）
実行されるべきそれぞれのタスクを決定し、上記待ち行列に該タスクを追加する複数のスレッドを使用することをさらに包含する、項目２４に記載の方法。
【００３８】
（項目３１）
スレッドが、他のタスクに依存する場合に、タスクを再生する、項目３０に記載の方法。
【００３９】
（項目３２）
上記ＣＡＤソフトウェアは、プログラマブルロジックデバイス（ＰＬＤ）内のリソースを配置するための配置アルゴリズムを備える、項目２３に記載の方法。
【００４０】
（項目３３）
上記ＣＡＤソフトウェアは、パラレル解析アルゴリズムを備える、項目２３に記載の方法。
【００４１】
コンピュータ支援設計（ＣＡＤ）ソフトウェアにおけるパラレル化を提供するシステムは、コンピュータを含む。このコンピュータは、局所独立性を有するタスクのセットを同定することと、このタスクのセットの各タスクがパラレルに実行されるように、割り当てることとを行うように構成される。また、このコンピュータは、このタスクのセットの各タスクを実行するように構成される。
【発明を実施するための最良の形態】
【００４２】
（詳細な説明）
本発明のコンセプトは、ソフトウェア（例えば、ＣＡＤアルゴリズムまたはソフトウェア、あるいは、ＦＰＧＡ用ＣＡＤソフトウェア）をパラレル化する装置および関連方法に関する。開示されたコンセプトは、実行速度を改善するために、例えば、プロセッサをスレッド化して使用すること、あるいは、プロセッサを複数使用することによって、パラレルにソフトウェアまたはアルゴリズムを稼動（ｒｕｎ）させることを探求する。
【００４３】
一般的に言って、本発明のコンセプトは、様々な方法で、ソフトウェアをパラレルに稼動させること、あるいは、アルゴリズムをパラレルに実行することを検討する。図１および図２は、使用され得る技術の２つの例である。本発明の記載の利益を有する当業者には、必要に応じて、他の技術および例も使用され得ることは理解される。
【００４４】
図１は、複数のスレッドを用いて、例示的な実施形態に使用されるパラレル化技術を示す。図１に示されるアレンジメントは、タスクのセット１３、スケジューラ１０、および、スレッドのセット１６を含む。タスクのセット１３は、ＣＡＤソフトウェアまたはアルゴリズムが実行または稼動しようとする様々なタスクを構成する。一般的に、セット１３は、任意の所望の数のタスク、例えば、Ｎ個のタスクを含み得る。一方、スレッドのセット１６は、任意の所望または適切な数のスレッド、例えば、Ｋ個のスレッドを含み得る（ＮとＫとは、等しいことも等しくないこともある点に留意されたい）。
【００４５】
スケジューラ１０は、セット１３からタスクを受け入れ、１つ以上のコンピュータで実行するために、タスクをスケジュールする。より具体的には、スケジューラ１０は、セット１３内のタスクをセット１６内のスレッドに割り当てる。例えば、スケジューラ１０は、タスク１をスレッド１に、タスク２をスレッド２に、などと割り当て得る。スレッドに割り当てると、次いで、その結果、割り当てられた対応するタスクが実行される。
【００４６】
図２は、複数のプロセッサを用いる例示的な実施形態を使用されるパラレル化技術を示す。図２のアレンジメントは、タスクのセット１３、スケジューラ１０、１９とラベル付けされたプロセッサのセットまたはコンピュータ、あるいは、同様の適切な装置を含む。例えば、プロセッサのセット１９は、パラレルコンピュータ、大規模パラレルコンピュータなどで構成され得る。これは、本発明の記載の利益を有する当業者には、理解される。
【００４７】
タスクのセット１３は、ＣＡＤソフトウェアまたはアルゴリズムが実行または稼動しようとする様々なタスクを表わす。一般的に、セット１３は、任意の所望の数のタスク、例えば、Ｎ個のタスクを含み得る。一方、プロセッサのセット１９は、任意の所望または適切な数のプロセッサ、例えば、Ｍ個のプロセッサを含み得る（ＫとＭとは、等しいことも等しくないこともある点に留意されたい）。
【００４８】
スケジューラ１０は、セット１３からタスクを受け入れ、１つ以上のコンピュータで実行するために、タスクをスケジュールする。より具体的には、スケジューラ１０は、セット１３内のタスクをセット１９内のプロセッサに割り当てる。例えば、スケジューラ１０は、タスク１をプロセッサ１に、タスク２をプロセッサ２に、などと割り当て得る。タスクをプロセッサに割り当てると、次いで、その結果、割り当てられた対応するタスクが実行される。
【００４９】
この発明のコンセプトは、必要に応じて、様々なＣＡＤのソフトウェア、アルゴリズムおよびアプリケーションに適用され得る。適用される特定のエリアの一つは、ＰＬＤの設計および使用のためのＣＡＤソフトウェアを構成する（例えば、ＰＬＤリソースを使用して、ユーザの設計をインプリメントする）。以下の記述は、このようなＰＬＤおよびソフトウェアパラレル化技術の詳細を提供する。
【００５０】
図３は、本発明の例示的な実施形態によって設計または使用され得るＰＬＤの一般的なブロック図である。ＣＡＤソフトウェア内のソフトウェアをパラレル化する本開示のコンセプトは、所望の回路またはシステムをインプリメントするために、ＰＬＤ１０３の設計あるいはそのリソースの使用で、用いられ得る。
【００５１】
ＰＬＤ１０３は、構成回路網１３０、構成メモリ（ＣＲＡＭ）１３３、制御回路網１３６、プログラマブルロジック１０６、プログラマブル相互接続１０９、および、入出力回路網１１２を含む。さらに、ＰＬＤ１０３は、必要に応じて、テスト／デバッグ回路網１１５、１つ以上のプロセッサ１１８、１つ以上の通信回路網１２１、１つ以上のメモリ１２４、１つ以上の制御装置１２７、および、初期化回路１３９を含み得る。
【００５２】
本図が示すのは、ＰＬＤ１０３の簡略化されたブロック図であることに留意されたい。したがって、ＰＬＤ１０３は、他のブロックや回路網も含み得る。このことは、当業者には理解される。このような回路網の例は、クロック発生および分配回路、冗長回路などを含む。さらに、ＰＬＤ１０３は、必要に応じて、アナログ回路網、他のデジタル回路網、および／または、混成モード回路網を含み得る。
【００５３】
プログラマブルロジック１０６は、構成可能ロジック回路網あるいはプログラマブルロジック回路網（例えば、ルックアップテーブル（ＬＵＴ）、プロダクトタームロジック、マルチプレクサ（ＭＵＸ）、ロジックゲート、レジスタ、メモリなど）を含む。プログラマブル相互接続１０９は、プログラマブルロジック１０６に結合し、プログラマブルロジック１０６内の様々なブロックやＰＬＤ１０３内外の他の回路網との間で構成可能な相互接続（結合機構）を提供する。
【００５４】
制御回路網１３６は、ＰＬＤ１０３内の様々な動作を制御する。制御回路網１３６の監視下で、ＰＬＤ構成回路網１３０は、ＰＬＤ１０３の機能性をプログラムあるいは構成するために、構成データ（ストレージデバイス、ホストなどの外部ソースから取得する）を使用する。構成データは、典型的には、ＣＲＡＭ１３３に情報を格納するために使われる。ＣＲＡＭ１３３のコンテンツは、ＰＬＤ１０３の様々なブロック（例えば、プログラマブルロジック１０６およびプログラマブル相互接続１０９）の機能性を決定する。初期化回路１３９は、ＰＬＤ１０３のリセット時またはパワーアップ時に、様々な機能をもたらし得る。
【００５５】
入出力回路網１１２は、幅広い様々な入出力デバイスまたは回路から形成され得る。このことは、本発明の記載の利益を有する当業者なら理解される。入出力回路網１１２は、ＰＬＤ１０３の様々なパーツ（例えば、プログラマブルロジック１０６、および、プログラマブル相互接続１０９）に結合し得る。入出力回路網１１２は、外部回路網または外部デバイスと通信するために、ＰＬＤ１０３内の様々なブロックに対し、メカニズムおよび回路網を提供する。
【００５６】
テスト／デバッグ回路網１１５は、ＰＬＤ１０３内の様々なブロックおよび回路のテストおよびトラブルシューティングを容易にする。テスト／デバッグ回路網１１５は、本発明の記載の利益を有する当業者に周知の様々なブロックまたは回路を含み得る。例えば、テスト／デバッグ回路網１１５は、必要に応じて、ＰＬＤ１０３のパワーアップまたはリセット後に、テストを実行する回路を含み得る。また、テスト／デバッグ回路網１１５は、必要に応じて、コード化回路およびパリティ回路も含み得る。
【００５７】
ＰＬＤ１０３は、１つ以上のプロセッサ１１８を含み得る。プロセッサ１１８は、ＰＬＤ１０３内の他のブロックおよび回路に結合し得る。プロセッサ１１８は、ＰＬＤ１０３内外の回路からのデータおよび情報を受け取り、幅広い様々な方法で、情報を処理する。これは、本発明の記載の利益を有する当業者には、理解される。１つ以上のプロセッサ１１８は、デジタル信号プロセッサ（ＤＳＰ）を構成し得る。ＤＳＰは、必要に応じて、幅広い様々な信号処理タスク（例えば、圧縮、復元、音声処理、映像処理、フィルタ処理など）を実行できる。
【００５８】
ＰＬＤ１０３は、また、１つ以上の通信回路１２１も含み得る。本発明の記載の利益を有する当業者には、理解されるように、通信回路１２１は、ＰＬＤ１０３内の様々な回路とＰＬＤ１０３外の様々な回路との間でのデータおよび情報の交換を促進し得る。
【００５９】
ＰＬＤ１０３は、１つ以上のメモリ１２４、および、１つ以上の制御装置１２７をさらに含み得る。メモリ１２４は、ＰＬＤ１０３内の様々なデータおよび情報（例えば、ユーザデータ、中間結果、計算結果など）の格納が可能である。メモリ１２４は、必要に応じて、細かな形式（ｇｒａｎｕｌａｒ ｆｏｒｍ）またはブロック形式を有し得る。制御装置１２７は、ＰＬＤ外の回路網とインターフェースし、これらＰＬＤ外の回路網の動作および様々な機能を制御できる。例えば、制御装置１２７は、必要に応じて、外部のシンクロナスダイナミックランダムアクセスメモリ（ＳＤＲＡＭ）とインターフェースし、制御するメモリ制御装置１２７を構成し得る。
【００６０】
上述のように、ＰＬＤ１０３は、プログラマブルリソースの多数のブロックを含む。これらのリソースを使用して設計をインプリメントすることは、ＰＬＤ１０３の平面図内にこれらのブロックを配置すること（後述）を必然的に伴う。図４は、本発明のコンセプトを用いて、設計またはインプリメントされ得るＰＬＤの平面図を示す。
【００６１】
ＰＬＤ１０３は、二次元アレイとしてアレンジされたプログラマブルロジック１０６を含む。プログラマブル相互接続１０９は、水平な相互接続と垂直な相互接続としてアレンジされ、プログラマブルロジック１０６のブロックを互いに結合する。ユーザ設計をインプリメントするために、特定の様式で、これらブロックが配置され得ることは、本発明の記載の利益を有する当業者には、理解される。
【００６２】
例示的な実施形態において、ＰＬＤ１０３は、階層的構造を有する。換言すれば、プログラマブルロジック１０６の各ブロックは、順に、より小さな、あるいは、より細かなプログラマブルロジックブロックまたは回路を含み得る。例えば、一実施形態において、プログラマブルロジック１０６は、ロジックアレイブロック（ＬＡＢ）と命名された構成可能ロジックのブロックを形成し得、必要に応じて、各ＬＡＢは、ロジックエレメント（ＬＥ）または他の回路網を含み得る。
【００６３】
しかしながら、本発明の記載の利益を有する当業者には、術語および形態を変更して、幅広い様々な他のアレンジメントも可能であり、それらが本発明のコンセプトの範囲内に収まることは、理解される。さらに、図４は、プログラマブルロジック１０６のブロックを示すが、その平面図において、他あるいは追加のブロック（例えば、メモリ、プロセッサ、図３の他のブロックなど）とともにＰＬＤを使用し得、本発明のコンセプトから利点を活かし得る。これは、本発明の記載の利益を有する当業者には、理解される。
【００６４】
しかしながら、特定のアレンジメントまたは設計に関わらず、ＰＬＤのリソースを利用するＣＡＤソフトウェアまたはプログラムにおける発明のコンセプトを用いて、所望の回路またはシステムをインプリメントし得る。ＰＬＤ１０３のようなＰＬＤにおけるユーザ設計をインプリメントすると、以下に詳述されるように、必然的に、幾つかのステップまたはプロセスを伴う。
【００６５】
図５は、本発明の例示的な実施形態に従うＰＬＤ ＣＡＤソフトウェアを使用する様々なソフトウェアモジュールを示す。このモジュールは、設計エントリモジュール２０３、合成モジュール２０６、配置・ルートモジュール２０９、および、検証モジュール２１２を含む。以下の記述は、各モジュールの動作の簡単な説明を提供する。
【００６６】
本発明の記載の利益を有する当業者に理解されるように、ＣＡＤ技術は、様々なアプリケーションを有し得る。例は、設計領域、タイミング性能、パワー要求、および、ルーティング可能性を必要に応じて含む。
【００６７】
設計エントリモジュール２０３は、回路およびその挙動のグラフィックまたはテキスト記述（例えば、必要に応じて、図表、ハードウェア記述言語（ＨＤＬ）または波形など）を用いて、様々な設計記述ファイルの編集が可能である。ユーザは、設計エントリモジュール２０３を用いて、あるいは、必要に応じて、様々な電子設計自動化（ＥＤＡ）またはＣＡＤツール（例えば、業界標準ＥＤＡツール）を用いて、設計ファイルを生成し得る。ユーザは、必要に応じて、グラフィック形式、波形ベースの形式、図表形式、テキストまたはバイナリ形式、あるいは、これら形式の組み合わせで、設計を入力し得る。
【００６８】
合成モジュール２０６は、設計エントリモジュール２０３の出力を受ける。ユーザ提供の設計に基づき、合成モジュール２０６は、ユーザ提供の設計を実現する適切なロジック回路を生成する。１つ以上のＰＬＤ（明確に図示せず）は、合成された設計全体またはシステム全体をインプリメントする。また、合成モジュール２０６は、ユーザ設計の中の様々なモジュールの統合および適切な動作ならびにインターフェースを可能にする任意のグルーロジック（ｇｌｕｅ ｌｏｇｉｃ）を生成する。例えば、合成モジュール２０６は、１つのブロックの出力がもう１つのブロックの入力と適切にインターフェースするように適切なハードウェアを提供する。合成モジュール２０６は、設計全体またはシステム全体内で、モジュールそれぞれの仕様を満たすように適切なハードウェアを提供する。
【００６９】
さらに、合成モジュール２０６は、合成設計を最適化するためのアルゴリズムおよびルーチンを含み得る。最適化によって、合成モジュール２０６は、設計全体またはシステム全体をインプリメントする１つ以上のＰＬＤのリソースをより効率的に使用しようとする。合成モジュール２０６は、その出力を配置・ルートモジュール２０９に提供する。
【００７０】
配置・ルートモジュール２０９は、最適なロジックのマッピングおよび配置を実行するために、設計のタイミング仕様を使用する。このロジックのマッピングおよび配置は、ＰＬＤ内のルーティングリソースの使用を決定する。換言すれば、設計の一部のパーツに対して、ＰＬＤとの特定のプログラマブル相互接続を使用することによって、配置・ルートモジュール２０９は、設計全体またはシステム全体の性能を最適化するのに役立つ。ＰＬＤのルーティングリソースを適切に使用することによって、配置・ルートモジュール２０９は、設計全体またはシステム全体のクリティカルタイミングパス（ｃｒｉｔｉｃａｌ ｔｉｍｉｎｇ ｐａｔｈ）を満足するために役立つ。
【００７１】
配置・ルートモジュール２０９は、クリティカルタイミングパスを最適化し、本発明の記載の利益を有する当業者に周知の方法よりも速くタイミングクロージャ（ｔｉｍｉｎｇ ｃｌｏｓｕｒｅ）を提供することに役立つ。その結果、設計全体またはシステム全体は、より高速な性能（すなわち、より高速なクロックレートで動作すること、または、より高いスループットを有すること）を達成し得る。
【００７２】
検証モジュール２１２は、設計のシミュレーションおよび検証を実行する。このシミュレーションおよび検証は、設計がユーザの所定の仕様に適合することを検証しようとする。また、シミュレーションおよび検証は、設計のプロトタイプを作る前に何らかの設計問題を検出し、修正することを狙いとする。こうして、検証モジュール２１２は、ユーザが、設計全体またはシステム全体の全体的なコストを削減し、市場に出すまでの時間を短縮するのに役立つ。
【００７３】
検証モジュール２１２は、必要に応じ、様々な検証およびシミュレーションのオプションをサポートし、実行し得る。このオプションは、必要に応じ、機能検証、テストベンチ生成、静的タイミング解析、タイミングシミュレーション、ハードウェア／ソフトウェアシミュレーション、システム内検証、ボードレベルタイミング解析、信号品位解析と電磁環境両立性（ＥＭＣ）、フォーマルネットリスト（ｆｏｒｍａｌ ｎｅｔｌｉｓｔ）検証などを含み得る。このことは、本発明の記載の利益を有する当業者には、理解される。
【００７４】
必要に応じて、また、本発明の記載の利益を有する当業者には理解されるように、その他または追加の検証技術も実行され得ることに留意されたい。また、設計の検証は、適宜、必要に応じ、このフローの他の段階でも実行され得る。
【００７５】
多数（おそらく大部分）の従来の市販ＣＡＤアルゴリズムは、事実上、シリアルである。換言すれば、これらのアルゴリズムは、様々なタスクをパラレルではなく、むしろ、シリアルに実行する。これは驚くべきことではない。なぜなら、第一に、プロセッサクロック速度は、今日まで定期的に高速化されてきたし、第二に、頑強な（ｒｏｂｕｓｔ）パラレルソフトウェアを開発するのは、ずっと困難だからである。
【００７６】
上述のような傾向があるので、今日では、既存のアルゴリズムを、新たなパラレル処理能力に引き上げ、ユーザに利用可能なものに改変することは、ずっと重要である。ＣＡＤアルゴリズムは、一般的に実用ソフトウェアで最も遅いタイプであるから、このことは、特に正しい。典型的な稼働時間が、週末をフルに費やすことも非常に一般的である。パラレル化技術が使用されなければ、シリアルアルゴリズムは、将来これらのアルゴリズムを用いて解かれ得る更に複雑な問題に見合うように十分に高速化され得ない。
【００７７】
一般に、シリアルＣＡＤアルゴリズムをパラレル化するときに、２つのアプローチが使用される。第一のアプローチは、シリアルアルゴリズムを処分して、その代わりに、より内在的な並列処理を有するアルゴリズムを使用する。このオプションは、幾つかの不利な点を有する。
【００７８】
第一に、このアプローチは、設計者に対し、最初から、既存のコードを処分して、新たなパラレルコードを開発するということを要求する。多くの人々の長年にわたる努力は、現存するアルゴリズムを最適化することに注ぎ込まれてきた。この努力を放棄すると、新しいアルゴリズムの品質が同じレベルに達するまでには、その後何年もかからなければならなくなる。また、このアプローチは、設計者に利用可能なアルゴリズムの選択を制限する。一部のシリアルアルゴリズムは特定の問題に対し、より適しており、パラレルアルゴリズムを無理に使用すると、ソフトウェアツールの品質を損ね得る。
【００７９】
さらに、パラレルアルゴリズムが、決定を行うことは、比較的困難である。決定性アルゴリズムは、同じ入力で、複数回稼動させたとき、同じ結果を与える。しかしながら、パラレルプログラムまたはアルゴリズムは、同時に複数のセットの命令を実行し、各プロセッサによりこれらのセットに与えられるアクセスに依存し、結果は、アルゴリズムが稼動するたびに異なり得る。この性質のために、ユーザがアルゴリズムで得た結果を再現することは難しいし、また、ベンダにとっては、ユーザが遭遇するあらゆる問題からバグを取り除くことは難しい。
【００８０】
最後に、アルゴリズムを稼動させるために依然として単一のプロセッサを使用しているユーザに対し、上述の潜在的な品質のロスと上述のその他の欠点とを伴うパラレルアルゴリズムへの変更を強いることは、ユーザを不満にさせる。さらに、パラレルアルゴリズムは、一般的に、これらユーザに対して顕著な遅さを強いるオーバーヘッドを招く結果となる。ソフトウェアツールのベンダは、それゆえ、少なくとも短期間の間、双方のアルゴリズムのセットを維持する必要があり、それに伴い、維持コストが高くなる。
【００８１】
第二のオプションとして、異なる設定を有する利用可能な各プロセッサ上において、シリアルアルゴリズムを稼動させ得、最後に、最適な結果を採択する。この従来のアプローチは、第一のアプローチに比べ、インプリメントが容易であるが、同様に幾つかの制約を有する。
【００８２】
第一に、これは、高速化には寄与しない。これは、単に、結果を改善するために、アルゴリズムのコピーをより多く稼動させるに過ぎない。アルゴリズムに対して考えられる最速の稼働時間を欲するユーザは、このアプローチからは、ユーザの欲するものを得ることはできない。第二に、このアプローチは、拡張性がない。なぜなら、同じアルゴリズムを多数稼動させてより良好な結果を得るために、より多くのプロセッサを利用可能にするので、稼動するコピーの数が増えれば増えるほど、減速する結果となるからである。明らかに、両アプローチは、重大な制約を有する。しかしながら、本発明のコンセプトは、これらの制約を克服する技術を提供する。
【００８３】
より具体的には、本発明の方法は、多数のシリアルＣＡＤアルゴリズムが、その実行時間のほとんどを入力問題の異なる部分で特定のアクションまたはアクションのセットを実行するのに費やすという事実を活用する。このアクションは、多数回（しばしば、数万回）繰り返され、その結果、これらのアルゴリズムに対する稼働時間が比較的長くなる。これらアルゴリズムをシリアルにする特性は、各アクションが、自身の以前の各アクションの結果の知見を用いて（すなわち、以前のアクションに依存して）実行される。この特性は、つまり、１つのアクションが任意の時間に行われ得ること、あるいは、行われることを意味し、これが、アルゴリズムをシリアルに実行するときの制限になる。
【００８４】
しかしながら、連続的なアクションの所定のセットは、入力問題の独立部分に影響を与えることが多い。それゆえ、これらのアクションを全てシリアルに実行する必要はない。この特性は、特に、入力問題が比較的大きいときに維持される。例えば、数多くのアクション（＃１０〜＃２０を含み、＃１０〜＃２０のアクションは互いに独立）を含む問題においてである。換言すれば、アクションの実行は、他のアクションの実行とは無関係である。
【００８５】
このような状況において、アルゴリズムは、これら１１個のアクションをパラレルに実行し得る。例示的な実施形態において、本発明の技術は、パラレルな実行の結果を形成するために、局所独立性を使用する。例えば、アクション＃２１が、以前のアクションの２つ（例えば、＃１３および＃１７）に依存する場合、アルゴリズムは、＃２１に進むまでに、＃１３および＃１７を終了しなくてはならない（そうでなければ、結果は決定論的なものではない）。そうでない場合、アルゴリズムは、アクションをパラレルに実行し得る。局所独立性は、この方法が使用するものであり、並列性を形成する。それゆえ、性能が改善される。
【００８６】
発明の技術は、アクションの待ち行列を使用する。ここで、待ち行列は、互いに独立なアクションでロードされる。この待ち行列は、シリアルにロードされ、全てのアクションが独立であることを確実にする。本発明の１つの変種として、待ち行列は、シリアルアルゴリズムがアクションを実行するのと同じ順序でロードされる。このアクションは、アルゴリズムのパラレル版の結果が、シリアル版の結果と、同様または同一になることを確実にする。
【００８７】
図６は、この技術を簡略化したブロック図である。タスク１３のセットは、スケジューラ１０に入力される。スケジューラ１０は、タスクを待ち行列２５０に提供し、上述のように、局所独立性を提供する。タスクは、待ち行列２５０から出力され、パラレルに実行される（局所独立性が存続する限り）。
【００８８】
本発明の別の変種として、アクションは、待ち行列で保持される独立アクションの数が最大となるような方法で選択され得る。一度、この待ち行列がロードされたら、全ての利用可能なプロセッサは、あらゆる任意または所望の順番で処理され得る。なぜなら、アクションの独立性が、保証されるからである。一度、待ち行列の全てのアクションが終了したら、待ち行列は、再びロードされ、この処理が繰り返される。
【００８９】
この技術をより詳細に示すと、配置の例が、配置アルゴリズムをパラレル化するために使用され得る方法を示すために提供される。配置アルゴリズムが、入力として、回路のネットリスト表現およびデバイスの平面図表現を取り込む。Ｑｕａｒｔｕｓ ＩＩソフトウェア（本出願の譲受人であるＡｌｔｅｒａ Ｃｏｒｐｏｒａｔｉｏｎから市販）において、例えば、ネットリストは、ユーザのロジック回路におけるブロック（例えば、ロジックアレイブロックすなわちＬＡＢ、ＲＡＭブロック、乗算器ブロックなど）を表す。平面図は、ＰＬＤまたは同様のデバイスで利用可能なブロックを表す。
【００９０】
シリアル配置アルゴリズムは、以下のように動作し得る。品質とはほとんどまたは全く無関係に、初期の適法な配置をできるだけ迅速または比較的迅速に生成する。その結果、ネットリスト内の各ブロックは、平面図内の位置に割り当てられる。第二に、ネットリストからランダムに１つのブロックをつまみ出し、ランダムな位置に移動させようとする。ソースブロックと既に存在する任意のブロックとを交換する。第三に、この配置への変更が良好であるか、あるいは、望ましいものであるかを評価する。良好または望ましい場合は、その変更を実施する。そうでない場合、変更を処分する。この評価は、幾つかの測定法で行われることが多いが、一般的には、この測定法は、互いに近くに配置されて、接続または結合されるブロックを保つように試みる。最終的に、第二のステップに戻り、所定の回数の移動が行われるまで繰り返される（例えば、この回数は、ネットリストのブロック数の１０００倍であり得る）。
【００９１】
上述の配置アルゴリズムは、本質的にシリアルである。なぜなら、第三のステップでの変更をコミットする決定は、アルゴリズムの全ての将来の繰り返し（すなわち、移動）に影響を与えるからである。例えば、図７の例を仮定する。ブロック＃６は、平面図のＸ＝３およびＹ＝４にあり、アルゴリズムの第一の移動は、Ｘ＝３０およびＹ＝４０にあるブロック＃２０と交換することを試みると仮定する。
【００９２】
さらに、アルゴリズムの第二の移動が、ブロック＃２１（たまたま、ブロック＃２０に接続または結合されている）を、Ｘ＝３０，Ｙ＝４からＸ＝１，Ｙ＝１に移動させるものと仮定する。図８は、第一の移動が受け入れられた場合の位置と接続性がどうなるかを示す。
【００９３】
アルゴリズムの第一の移動が、その移動を受け入れたとき、第二の移動（ブロック＃２１を（１，１）に移動させようと試みる）は、より受け入れられやすい。なぜなら、ブロック＃２１の新たな位置（１，１）は、それが接続または結合されているブロック（すなわち、現在の位置（３，４）を有するブロック＃２０）に、より近いからである。しかしながら、第一の移動が受け入れられなかった場合（図７のままの状況）、ブロック＃２１を（１，１）に移動することは、良い移動であるとは思われない。なぜなら、その接続または結合されたブロック（すなわち、ブロック＃２０）は、（３０，４０）にあるからであり、また、現在のブロック＃２１の位置（すなわち、３０，４）が、位置（１，１）よりも近いからである。
【００９４】
この例は、上記のシリアルアルゴリズムのようなアルゴリズムがパラレルに稼動する場合に直面し得る問題を示す。例えば、移動＃１および＃２が同時に稼動する場合、＃２が受け入れられるかどうかは、移動＃２が評価される前に、移動＃１が終了したかどうかに依存する。
【００９５】
アルゴリズムが変更されなければ、アルゴリズムをパラレルに稼動させることは、結果として、その接続または結合されたブロックが存在する最終位置を追うブロック追跡になる。また、これは、結果を非決定論的なものとする。なぜなら、たとえ同じ回路での異なる稼動に対してであっても、所定の移動がどのくらいの時間で完了するのかを予見することは一般に不可能だからである。
【００９６】
これらの問題を解決するための本発明の技術を適用すると、上述のように、独立した移動の待ち行列を形成し得る。上記の例から第一の移動は、待ち行列の中に配置され、第二の移動は、もはや待ち行列の中に入ることは許可されない（なぜなら、第二の移動は、ブロック＃２１とブロック＃２０との間の接続または結合を介して、第一の移動に依存するからである）。この待ち行列のロードは、停止され、移動が処理されるか、または、上述のように、移動が処理される前に、待ち行列がその他の独立な移動を用いてロードされ得る。いずれの場合も、待ち行列が大きければ大きいほど、高速化は、複数のプロセッサを有することから、その速度アップは大きくなる。例えば、常に２つ以下の移動を有する待ち行列は、２つのプロセッサ（しかし、４つ以上ではない）を使用することからメリットを得る。
【００９７】
上記の技術は、待ち行列のシリアルなロードを用いることに留意されたい。移動を提案する時間が比較的短い場合、シリアルにロードしても問題は生じない。例えば、ロードに、シリアル稼働時間の５％を要し、評価に９５％を要するアルゴリズムの場合、稼働時間は、２つのプロセッサを有するマシンでは、理論的には１．９倍の係数で速度アップし得る。しかしながら、シリアル部分の比率が高い場合、このメリットは、劇的に低下し得る。例えば、このアルゴリズムの半分がパラレル化されたに過ぎない場合、２つのプロセッサからなるシステムの速度アップは、１．３３の係数に制限される。
【００９８】
比較的より高度な待ち行列を使用すると、この問題を緩和することができる。配置問題に戻ると、移動同士での依存性には、２つのソースがあることが分かる。（１）独立した移動の提案が不可能であり得ること、および（２）移動の独立した評価が不可能であり得ることである。
【００９９】
これらの２つの場合は、同様または同一に扱われるが、両者は非常に異なる。例えば、単一のブロックに対して２つの移動が提案された場合を考える。第一の移動が終わるか、拒絶されるかまで、第二の移動を提案すらできないことは明らかである。なぜなら、第一の移動の後、ブロックがどこにあるかが分からないからである。
【０１００】
一方、２つのブロックの場合で、互いに近くに移動させたいという場合を考える。双方のブロックで、同時に移動を提案することは容易である。その双方を独立して評価はできない（なぜなら、どちらのブロックを最初に移動させるかによって、第二の移動が、良好ないこと、望ましくないこと、あるいは、有利でないこともあり得るからである）。しかしながら、ブロックに対する移動が、その双方で評価される前であっても、他の移動に進むことも、提案することも可能である。パラレルな観点から、そのようにすることは有利である。なぜなら、任意の移動が行き詰まり（ｓｔａｌｌ）の原因となるときのような多くの環境下よりも、すべてのプロセッサに対して、仕事を生成し続けるようにできるからである。
【０１０１】
以下は、この改善の例を記載する。図９の配置を考える。ブロック３０３〜３１５に関して、幾つかの移動が提案されている。上述した元々の本発明のアルゴリズムは、第一の移動、次いで、第二の移動を提案すると、ストップする。なぜなら、２つの移動は、接続または結合されたブロックに関連しているからである。それゆえ、移動＃２を受け入れるか、拒絶するかの決定は、＃１の移動に依存する（換言すれば、移動＃１は、ブロック３０３を移動させ、移動＃２は、ブロック３０３に結合されたブロック３０６を移動させる）。
【０１０２】
しかしながら、次いで、移動＃２および＃３（ブロック３０９の移動）をパラレルに評価し、次いで、＃４（ブロック３１２の移動）、＃５（ブロック３１５の移動）および＃６（ブロック３０３の移動）、そして、最終的に、＃７（ブロック３１８の移動）を評価し得る。配置が、３回ストップしたこと、そして、４つの「セット」の移動において、そのセットの半分は、単一のブロックの移動であったことに留意されたい。こうして、半分の時間で、（一例として）デュアルコアのマシン上の１つのプロセッサは、遊んでいる。
【０１０３】
しかしながら、この代わりに、もはや移動が提案されなくなったときに、ストップする場合、状況は改善する。例えば、移動＃１〜＃５までをストップすることなく、提案し得る。移動＃６でストップすることに留意されたい。なぜなら、移動＃６は、ブロック（すなわち、ブロック３０３）をターゲットにし、上記ブロックは、他の移動の結果、既に移動している可能性があるからである。移動＃１が受け入れられるか、拒絶されると、すぐに再開して、移動＃７の提案に進む。換言すれば、１つ以上の移動に１つ以上の依存が、解決されたときに、再開し得る。
【０１０４】
ここで、任意の与えられた時間に、パラレルに評価され得る少なくとも２つの移動（移動＃１とパラレルな移動＃３、移動＃３とパラレルな移動＃４、移動＃４および移動＃２とパラレルな＃５、移動＃３とパラレルな移動＃６、ならびに、移動＃３、＃５および＃６とパラレルな移動＃４、＃５および＃７）があるとする。本発明の記載の利益を有する当業者は、この技術を用いると、一度に４つまたは８つあるいはそれ以上の移動でさえも確実に生成し得る更に大きな機会を有し得る。こうして、必要に応じて、３つ以上のプロセッサを有するマシンからそのメリットを得ることができる。
【０１０５】
このアルゴリズムをインプリメントするために、本発明のコンセプトは、より高度または「スマート」な、あるいは、改善または強化された待ち行列を使用する。より具体的には、その移動の順番を保ち、利用可能な次の移動においてプロセッサが機能できるようにする代わりに、そのような待ち行列は、各移動が評価される前に、受け入れられるか拒絶され得る最後の移動を追跡する。例えば、移動＃２は、移動＃１をリストに載せ、移動＃６は、移動＃２（しかし、移動＃３、＃４および＃５ではない）をリストに載せる。例えば、移動＃２の評価し終わったプロセッサは、たとえ移動＃３、＃４および＃５が完了していなくても、移動＃６で機能を開始する。
【０１０６】
この技術は、様々な状況で使用され得る。例えば、必要に応じて、このような待ち行列は、図６の待ち行列２５０と置換され得る。代替として、必要に応じて、本発明の記載の利益を有する当業者には理解されるように、他のアレンジメントも使用され得る。
【０１０７】
強化または改善された待ち行列によって可能になった速度アップが十分でない場合でもまた、パラレルに機能させたいと望む入力問題の一部分が選択された異なるスレッドを有することが可能である。こうした場合であっても、依然、決定論的な結果を維持していることに留意されたい。上記の配置の例を用いると、このアプローチは、移動をパラレルに評価するだけでなく、移動をパラレルに生成することを意味する。この技術は、以下に記載され、図１０に図示されるように、動作する。
【０１０８】
上述のように、３５０で、全てのアクションに数字のＩＤが与えられる。しかしながら、３５５で、複数のスレッドは、入力問題のどの部分（例えば、各スレッドが移動することを提案するブロック）を選択して調査するかを決定し得る。しかしながら、それぞれのスレッドは、実際には、アクションを実行しない。
【０１０９】
次いで、３６０で、スレッドは、アクションをサブミッション待ち行列に追加する。この待ち行列は、アクションを任意の順番で受け入れるが、アクションをＩＤ番号の順に発信する。例えば、アクション＃１および＃３が追加された場合、待ち行列は、アクション＃２が追加されるまで、その待ち行列は、その中に１つのアクション（＃１）を有するよう見える。
【０１１０】
アクションが待ち行列から除去されたら、３６５で、上述したような依存関係解析を実行する。あるアクションが、以前のアクションに依存することが分かった場合、上述のように、そのアクションを処理する。しかしながら、アクション自身が、無効なこともあり得る。例えば、期待された場所に今や存在し得ないブロックに対して、移動を提案し得る。この状況が本明細書で記述されたバージョンの技術を用いて生じた場合、新たなアクションの生成が、単純にストップされ得る。改善技術を用いると、アクションをパラレルに生成する複数のスレッドを有し得る。このことは、比較的より深刻な制約であり得る。
【０１１１】
一度、この比較的より深刻な種類の依存性が見出されると、３７０で、スレッドは、アクションを（好ましくはできるだけ迅速に）再生成するように、単に求められる。例えば、「できるだけ迅速に」とは、標的ブロックが実際に移動したかどうかが判断されるときであり得る。移動していなかった場合、その移動を単に評価し、移動していた場合、新たな移動を最初から提案または検討し、代わりに、その移動を評価する。
【０１１２】
この技術の利点は、アルゴリズムのどの部分もシリアルでない（チェッカの依存性を除く。これは、比較的高速であると仮定する）ことなので、与えられた固有の依存性の中で、理論的に可能な限り、プログラム全体を加速できることが期待される。このアルゴリズムは、それ自身の新たな依存性をほとんど全く導入しないことに留意されたい。
【０１１３】
特定のアルゴリズムに特有なＰＬＤ ＣＡＤのアプリケーション以外の他のアプローチもある。この特定のアルゴリズムは、アルゴリズム設計の柔軟性に著しい影響を与えることなく、パラレル処理能力のメリットを享受して使用され得る。一例は、パラレル解析である。
【０１１４】
より具体的には、最適化アルゴリズムは、様々な設計目標を達成するのに、どのくらいの努力が付与されるべきか（そして、その努力をどこに付与すべきか）を決定するために、解析エンジンに頼ることが多い。これらの解析エンジンは、現在の状態のスナップショットを取り、その状態に対する解析の結果を返す。図１１に示されるシリアルアルゴリズムは、解析を待ち、その解析が行われたら進む（例えば、最適化フェーズ４０３Ｂは、解析フェーズ４０６の結果を待ち、次いで、その入力を最適化フェーズ４０３Ａから受信する）。その結果、上述の不利な点を有する。
【０１１５】
このアルゴリズムをパラレルにするため、絶えず状態のスナップショットを取り、その解析を実行する追加のプロセッサを有し得る。この解析結果は、解析結果が利用可能であるときに解析に用いられる状態が現在の状態でないために、１つの不都合を有する。しかしながら、一方で、並列化は、効率を向上し、リソースの需要を削減する。図１２は、この処理がどのように機能するかを示す。
【０１１６】
図１２に示される技術において、解析および最適化がパラレルに実行され得る。例えば、最適化フェーズまたはエンジン４０３Ａは、解析フェーズまたはエンジン４０６Ａとともに、パラレルに、あるいは、同時に、動作し得る。同様に、最適化フェーズまたはエンジン４０３Ｂは、解析フェーズまたはエンジン４０６Ｂとともに、パラレルにあるいは、同時に、動作し得る。このシナリオにおいて、解析フェーズは、以前の最適化状態で実行される。解析フェーズの結果は、最適化の状態が潜在的に変化した後に、最適化フェーズにフィードバックされる。
【０１１７】
各解析ステップへの入力は、その出力を使用する状態とは異なる最適化状態からであることに留意されたい。例えば、最適化ステップが、配置（例えば、数千の移動がブロックに行われる）であり、解析ステップが、タイミング解析であると仮定する。この技術は、解析および最適化が同時またはパラレルに実行されるというメリットを提供する。それでも、潜在的に（しかし、必然的にではない）、より少ない最適化ソリューションを代償にする。
【０１１８】
この技術が適用され得る解析の例は、タイミング解析（回路における各経路のタイミング性能の決定）、混雑解析（設計の配置に基づいて、ルーティング混雑に直面しそうなチップのエリアの決定）、および設計解析（最適化に焦点をより良く合わせるのに、望ましい、または有利である（あるいは要求される）設計の部分の決定）を含む。列挙した例は、単に例示的なものであり、この技術は、他のアプリケーションまたは状況においても使用され得ることには留意されたい。このことは、本発明の記載の利益を有する当業者には、理解される。
【０１１９】
上述のように、コンピュータシステムまたはプロセッサ上で、本発明に従うアルゴリズムまたはソフトウェアを稼動または実行し得る。図１３は、本発明に従う情報を処理する例示的なシステムのブロック図を示す。
【０１２０】
システム１０００は、コンピュータデバイス１００５、入力デバイス１０１０、ビデオ／ディスプレイデバイス１０１５、および、ストレージ／出力デバイス１０２０を示す。しかしながら、必要に応じて、これらデバイスのそれぞれを２つ以上含み得る。
【０１２１】
コンピュータデバイス１００５は、入力デバイス１０１０、ビデオ／ディスプレイデバイス１０１５、および、ストレージ／出力デバイス１０２０に結合される。システム１０００は、必要に応じて、例えば、関連コンピュータデバイスまたはシステムのセットのように、２つ以上のコンピュータデバイス１００５を含み得る。
【０１２２】
システム１０００は、ユーザからの入力と関連し得る。ユーザは、典型的には、システム１０００に、特定の所望の情報処理タスク（回路シミュレーションを含む）を実行させる。システム１０００は、部分的に、コンピュータデバイス１００５を用いて、これらのタスクを実行する。コンピュータデバイス１００５は、中央演算処理装置（ＣＰＵ）のような情報処理回路網を含む。しかしながら、当業者には理解されるように、２つ以上のＣＰＵまたは情報処理回路網を含み得る。
【０１２３】
入力デバイス１０１０は、ユーザからの入力を受け入れ、その入力をコンピュータデバイス１００５で処理するために、利用可能にする。ユーザ入力は、必要に応じて、データ、命令、または、その双方を含み得る。入力デバイス１０１０は、英数字入力デバイス（例えば、キーボード）、ポインティングデバイス（例えば、マウス、ローラボール、ライトペン、タッチセンサ式ディスプレイ、またはタブレット）、あるいは、その双方から構成され得る。ユーザは、英数字キーボードを動作し、ＡＳＣＩＩ文字のようなテキストをコンピュータデバイス１００５に提供する。同様に、ユーザは、ポインティングデバイスを動作し、カーソル位置または制御情報をコンピュータデバイス１００５に提供する。
【０１２４】
ビデオ／ディスプレイデバイス１０１５は、ユーザに画像を提供する。視覚画像には、コンピュータデバイス１００５の動作に関する情報（例えば、グラフ、ピクチャ、画像、および、テキスト）も含み得る。ビデオ／ディスプレイデバイスは、当業者なら理解されるように、コンピュータモニタまたはディスプレイ、投影デバイスなどを構成し得る。システムが、タッチセンサ式ディスプレイの場合、また、ディスプレイが動作して、ユーザ入力をコンピュータデバイス１００５に提供し得る。
【０１２５】
ストレージ／出力デバイス１０２０は、コンピュータデバイス１００５が追加の処理または後の引き出し（例えば、ソフトコピー）を行うための情報を格納し、様々な形式（ハードコピー）で情報を表示する。一例として、ストレージ／出力デバイス１０２０は、所望の媒体上に、所望の形式で情報を格納できる磁気ドライブ、光学ドライブ、または磁気光学ドライブから構成され得る。別の例として、ストレージ／出力デバイス１０２０は、コンピュータデバイス１００５からの情報を印刷表示またはプロット表示を生成するプリンタ、プロッタ、または、他の出力デバイスであり得る。
【０１２６】
コンピュータ可読媒体１０２５は、コンピュータデバイス１００５と構造的および機能的に相互関連する。コンピュータ可読媒体１０２５は、機能記述マテリアルを格納、コード化、記録、および／または、具現化する。例としては、機能記述マテリアルには、コンピュータプログラム、コンピュータコード、コンピュータアプリケーション、および／または、情報構造（例えば、データ構造またはファイルシステム）が含まれ得る。コンピュータ可読媒体１０２５によって、格納、コード化、記録、および／または、具現化されると、機能記述マテリアルは、機能性を伝える。機能記述マテリアルは、コンピュータ可読媒体１０２５と相互に関係付ける。
【０１２７】
機能記述マテリアルの中の情報構造は、情報構造と、コンピュータ可読媒体１０２５および／またはシステム１０００の他の局面との間の構造的および機能的相互関係を規定する。これらの相互関係は、情報構造の機能性の実現化を可能にする。さらに、コンピュータプログラムは、このような機能記述マテリアル内で、コンピュータプログラムと、コンピュータ可読媒体１０２５および／またはシステム１０００の他の局面との間の構造的および機能的相互関係を規定する。これらの相互関係は、コンピュータプログラムの機能性の実現化を可能にする。
【０１２８】
例として、コンピュータデバイス１００５は、コンピュータデバイス１００５のコンピュータメモリ（図には明示せず）の中で、機能記述マテリアルを読み取り、アクセスし、コピーする。コンピュータデバイス１００５は、コンピュータメモリ内に存在するマテリアルに応答して動作する。コンピュータデバイス１００５は、コンピュータデバイス１００５に追加の動作を実行させるコンピュータアプリケーションを処理する動作を実行し得る。従って、機能記述マテリアルは、コンピュータデバイス１００５が処理を実行し、動作を実行する方法と機能的相互関連を示す。
【０１２９】
さらに、コンピュータ可読媒体１０２５は、コンピュータデバイス１００５がコンピュータ情報、プログラム、コードおよび／またはアプリケーションにアクセスし得る装置を構成する。コンピュータデバイス１００５は、コンピュータデバイス１００５に追加の動作を実行させるコンピュータ情報、プログラム、コードおよび／またはアプリケーションを処理し得る。
【０１３０】
当業者には理解されるように、コンピュータ可読媒体１０２５は、様々な方法でインプリメントされ得ることに留意されたい。例えば、コンピュータデバイス１００５内のメモリは、必要に応じて、コンピュータ可読媒体を構成し得る。代替として、コンピュータ可読媒体１０２５は、関連、相互関係付け、結合（例えば、導体、ファイバなど）、または、ネットワーク化されたコンピュータ可読媒体のセットを含み得る。例えば、コンピュータデバイス１００５は、必要に応じて、機能記述マテリアルをコンピュータ可読媒体１０２５、ネットワーク、あるいは、その双方から受信し得る。
【０１３１】
必要に応じて、また、本発明の記載の利益を有する当業者なら分かるように、本発明のコンセプトは、プログラマブルまたは構成可能ロジック回路網（業界で他の名称でも周知）を有するＩＣを含む様々なＩＣに有効に適用され得ることに留意されたい。このような回路網には、例えば、複合プログラマブルロジックデバイス（ＣＰＬＤ）、プログラマブルゲートアレイ（ＰＧＡ）、フィールドププログラマブルゲートアレイ（ＦＰＧＡ）、および、構造化特定用途向けＩＣ（すなわち、構造化ＡＳＩＣ）を含む。
【０１３２】
図面に関して言うと、図示された様々なブロックは、概念的機能および信号の流れを主として表し得ることを、当業者は気付き得る。実際の回路インプリメンテーションは、様々な機能ブロック用に、個別の同一のハードウェアを含むことも含まないこともあり得、図示された特定の回路網を用いることも用いないこともあり得る。例えば、必要に応じて、１つの回路ブロックに様々なブロックの機能が組み合わされ得る。さらに、必要に応じて、単一のブロックの機能を幾つかの回路ブロックで実行し得る。本発明の記載の利益を有する当業者なら理解されるように、回路インプリメンテーションの選択は、所定のインプリメンテーションに対する特定の設計および性能仕様などの様々な因子に依存する。また、本発明の記載の利益を有する当業者には、上述した事項に加え、本発明の他の改変や代替的な実施形態は明白である。したがって、本記述は、当業者に、本発明の実行を教示するものであり、単に例示的なものに過ぎないと解釈されるべきである。
【０１３３】
図示され、記載された発明の形式は、現在のところ、好ましい実施形態あるいは例示的な実施形態として考えられるべきである。当業者なら、本明細書に記載した発明の範囲から逸脱することなく、パーツの形状、サイズおよびアレンジメントを様々に変更し得る。例えば、当業者は、本明細書に図示され記載されたエレメントを同等のエレメントで代替し得る。さらに、本発明の記載の利益を有する当業者は、本発明の範囲から逸脱することなく、本発明のある特徴を他の特徴とは、独立して使用し得る。
【図面の簡単な説明】
【０１３４】
添付図面は、本発明の例示的な実施形態を示すだけであって、本発明の範囲を限定するものと考慮または解釈されるべきではない。本発明の記載の利益を有する当業者は、開示された発明のコンセプトが他の同じように有効な実施形態にも役立つことを理解し得る。図面において、２つ以上の図面で使用される同じ数字符号は、同等、類似または等価の機能性、コンポーネントまたはブロックを示す。
【図１】図１は、複数のスレッドを用いて、例示的な実施形態で使用されるパラレル化技術を示す。
【図２】図２は、複数のプロセッサを用いて、例示的な実施形態で使用される別のパラレル化技術を示す。
【図３】図３は、本発明の例示的な実施形態を用いて、指定または使用され得るＰＬＤの一般的なブロック図を示す。
【図４】図４は、本発明のコンセプトを用いて、設計またはインプリメントされ得るＰＬＤの平面図を示す。
【図５】図５は、本発明の例示的な実施形態に従うＰＬＤ ＣＡＤソフトウェアを使用する様々なソフトウェアモジュールを示す。
【図６】図６は、パラレル化技術の簡略化したブロック図を示す。
【図７】図７は、デバイス平面図の初期構成の例を示す。
【図８】図８は、リソースの移動を受け入れた後の図７のデバイス平面図を示す。
【図９】図９は、デバイス平面図におけるリソースの移動の提案を示す。
【図１０】図１０は、例示的な実施形態に従うパラレル化技術を示す。
【図１１】図１１は、シリアル解析アルゴリズムの例を示す。
【図１２】図１２は、解析アルゴリズムのパラレル化の例を示す。
【図１３】図１３は、開示されたコンセプトを用いて情報を処理するシステムのブロック図を示す。
【技術分野】
【０００１】
（関連出願の相互参照）
本出願は、米国仮特許出願第６０／７７２，７４７号（２００６年２月１３日出願、発明の名称「Ａｐｐａｒａｔｕｓ ａｎｄ Ｍｅｔｈｏｄｓ ｆｏｒ Ｐａｒａｌｌｅｌｉｚｉｎｇ Ｓｏｆｔｗａｒｅ」、代理人整理番号第ＡＬＴＲ：０５５ＰＺ１号）の利益を主張し、該仮特許出願を本明細書にて参照することによって援用する。
【０００２】
（技術分野）
一般的に、開示されるコンセプトは、ソフトウェアおよびアルゴリズムをパラレル化する装置および方法に関する。より特定的には、プログラマブルロジックデバイス（ＰＬＤ）のような集積回路（ＩＣ）用のコンピュータ支援設計（ＣＡＤ）ソフトウェアをパラレル化する装置および方法に関する。
【背景技術】
【０００３】
(背景）
伝統的に、プロセッサ（例えば、Ｉｎｔｅｌ製のＰｅｎｔｉｕｍ（登録商標）シリーズ、ＡＭＤ製のＡｔｈｌｏｎシリーズなど）は、ますます速くなるクロック速度をサポートすることによって、ますます高速化してきた。プロセッサが、このようにますます高速になるにつれ、これらプロセッサ上でソフトウェアの特定のピースを稼動させるのに要する時間は、それに比例するように自動的に高速化される（なぜなら、単一のコード命令を実行する時間は、プロセッサクロックの速度に概ね比例するからである）。
【０００４】
しかしながら、今日市販されている新世代のプロセッサは、２年前のもの（約３ＧＨｚ）よりも、顕著に速いクロックを使用していない。その代わりに、今日では、これらのプロセッサチップは、そのチップの中に２つ以上のプロセッサを含んでいる（例えば、Ｐｅｎｔｉｕｍ（登録商標） Ｄは、「デュアルコア」であり、１つのチップに２つのミニプロセッサを有することを意味する）。この特性は、コンピュータが同時に、幾つかの実行する「スレッド」を同時に稼動することを可能にする。
【発明の開示】
【発明が解決しようとする課題】
【０００５】
任意のシリアルなソフトウェア（ソフトウェアが、一度に実行する１つのタスクを有することを意味する）は、これらチップ内の追加的なプロセッサを利用可能にしても、高速化しない。追加の処理能力を引き上げるには、シリアルソフトウェアは、パラレル化される必要がある。つまり、シリアルソフトウェアは、全てのプロセッサをビジーに保つためにすぐに実行されるべき複数のタスクを有さなければならない。残念なことに、このパラレル化は、必ずと言ってもよいほど、自動的に行われない。それは、ソフトウェアコードの変更を必然的にともなうからである。また、変更自体も、かなり巧妙である。それは、シリアルソフトウェアの根底にある仮定の多くは、パラレルソフトウェアでは通用しないからである。それゆえ、ＣＡＤソフトウェアのようなソフトウェアをパラレル化するニーズが存在する。
【課題を解決するための手段】
【０００６】
（概要）
開示される新たなコンセプトは、ＣＡＤソフトウェアおよびアルゴリズムのようなソフトウェアをパラレル化する装置および方法に関する。本発明のコンセプトの一局面は、ＰＬＤ ＣＡＤソフトウェアのようなＣＡＤソフトウェアをパラレル化する方法に関する。一実施形態において、本発明に従う方法は、独立性を有するタスクのセットを同定することと、このタスクのセットの各タスクをパラレルに実行されるように割り当てることとを含む。この方法は、このタスクのセットの各タスクを実行することをさらに含む。
【０００７】
本発明の別の局面は、ソフトウェアをパラレル化するシステムに関する。このシステムは、上述したパラレル化方法を実行するように構成されたコンピュータを含む。本発明のコンセプトのさらなる別の局面は、コンピュータプログラム製品に関する。この製品は、ソフトウェアをパラレル化するコンピュータによる処理をするように適合されたコンピュータアプリケーションを含む。コンピュータアプリケーションは、上述したソフトウェアパラレル化方法をコンピュータに実行させる。
【０００８】
上記課題を解決するために、本発明は、以下を提供する：
（項目１）
コンピュータを備えるコンピュータ支援設計（ＣＡＤ）ソフトウェアのパラレル化を提供するシステムであって、該コンピュータは、
独立性を有するタスクのセットを同定することと、
該タスクのセットの各タスクをパラレルに実行されるように割り当てることと、
該タスクのセットの各タスクを実行することと
を行うように構成される、システム。
【０００９】
（項目２）
上記コンピュータは、上記タスクのセットを用いて待ち行列をロードするように構成される、項目１に記載のシステム。
【００１０】
（項目３）
上記待ち行列は、上記パラレル化されたＣＡＤソフトウェアがシリアルアルゴリズムと同様の結果を生成するように、シリアルＣＡＤアルゴリズムと同様な順番でロードされる、項目２に記載のシステム。
【００１１】
（項目４）
上記タスクのセットは、上記待ち行列内に保持される独立なアクションの数を最大化するように選択される、項目２に記載のシステム。
【００１２】
（項目５）
上記タスクは、任意の順番で実行される、項目４に記載のシステム。
【００１３】
（項目６）
上記待ち行列は、上記タスクのセットが実行される前に、該タスクのセットの全てのタスクを用いてロードされる、項目２に記載のシステム。
【００１４】
（項目７）
上記待ち行列は、上記タスクのセットが実行されている間に、追加のタスクが提案されることを可能にする強化待ち行列を備える、項目２に記載のシステム。
【００１５】
（項目８）
複数のスレッドが、実行されるべきそれぞれのタスクを決定し、該タスクを待ち行列に追加する、項目２に記載のシステム。
【００１６】
（項目９）
スレッドが、他のタスクに依存する場合に、タスクを再生する、項目８に記載のシステム。
【００１７】
（項目１０）
上記ＣＡＤソフトウェアは、プログラマブルロジックデバイス（ＰＬＤ）内のリソースを配置するための配置アルゴリズムを備える、項目１に記載のシステム。
【００１８】
（項目１１）
上記ＣＡＤソフトウェアは、パラレル解析アルゴリズムを備える、項目１に記載のシステム。
【００１９】
（項目１２）
コンピュータ支援設計（ＣＡＤ）ソフトウェアをパラレル化するようにコンピュータによって処理するために適合したコンピュータアプリケーションを備える、コンピュータプログラム製品であって、
該コンピュータアプリケーションは、該コンピュータに
独立性を有するタスクのセットを同定することと、
該タスクのセットの各タスクをパラレルに実行されるように割り当てることと、
該タスクのセットの各タスクを実行することと
を行わせるように構成される、コンピュータプログラム製品。
【００２０】
（項目１３）
上記タスクのセットを用いて上記コンピュータに待ち行列をロードさせる、項目１２に記載のコンピュータプログラム製品。
【００２１】
（項目１４）
上記パラレル化されたＣＡＤソフトウェアがシリアルアルゴリズムと同様の結果を生成するように、シリアルＣＡＤアルゴリズムと同様な順番で上記コンピュータに上記待ち行列をロードさせる、項目１３に記載のコンピュータプログラム製品。
【００２２】
（項目１５）
上記待ち行列内に保持される独立なアクションの数を最大化するように、上記コンピュータに上記タスクのセットを選択させる、項目１３に記載のコンピュータプログラム製品。
【００２３】
（項目１６）
上記コンピュータに、上記タスクを任意の順番で実行させる、項目１５に記載のコンピュータプログラム製品。
【００２４】
（項目１７）
上記タスクのセットが実行される前に、該タスクのセットの全てのタスクを用いて上記待ち行列を上記コンピュータにロードさせる、項目１３に記載のコンピュータプログラム製品。
【００２５】
（項目１８）
上記タスクのセットが実行されている間に、追加のタスクが提案されることを可能にする強化待ち行列を、上記コンピュータに使用させる、項目１３に記載のコンピュータプログラム製品。
【００２６】
（項目１９）
実行されるべきそれぞれのタスクを決定し、該タスクを待ち行列に追加する複数のスレッドを、上記コンピュータに使用させる、項目１３に記載のコンピュータプログラム製品。
【００２７】
（項目２０）
他のタスクに依存する場合に、タスクを再生するスレッドを、上記コンピュータに使用させる、項目１９に記載のコンピュータプログラム製品。
【００２８】
（項目２１）
プログラマブルロジックデバイス（ＰＬＤ）内のリソースの配置を、上記コンピュータに実行させる、項目１２に記載のコンピュータプログラム製品。
【００２９】
（項目２２）
パラレル解析アルゴリズムを、上記コンピュータに実行させる、項目１２に記載のコンピュータプログラム製品。
【００３０】
（項目２３）
コンピュータ支援設計（ＣＡＤ）ソフトウェアをパラレル化する方法であって、該方法は、
独立性を有するタスクのセットを同定することと、
該タスクのセットの各タスクをパラレルに実行されるように割り当てることと、
該タスクのセットの各タスクを実行することと
を包含する、方法。
【００３１】
（項目２４）
上記タスクのセットを用いて待ち行列をロードすることをさらに包含する、項目２３に記載の方法。
【００３２】
（項目２５）
上記パラレル化されたＣＡＤソフトウェアがシリアルアルゴリズムと同様な結果を生成するように、シリアルＣＡＤアルゴリズムと同様な順番で待ち行列をロードすることをさらに包含する、項目２４に記載の方法。
【００３３】
（項目２６）
上記タスクのセットを、上記待ち行列内に保持される独立なアクションの数を最大化するように選択することをさらに包含する、項目２４に記載の方法。
【００３４】
（項目２７）
上記タスクを任意の順番で実行することをさらに包含する、項目２６に記載の方法。
【００３５】
（項目２８）
上記タスクのセットが実行される前に、該タスクのセットの全てのタスクを用いて上記待ち行列をロードすることをさらに包含する、項目２４に記載の方法。
【００３６】
（項目２９）
上記待ち行列は、上記タスクのセットが実行されている間に、追加のタスクが提案されることを可能にする強化待ち行列を備える、項目２４に記載の方法。
【００３７】
（項目３０）
実行されるべきそれぞれのタスクを決定し、上記待ち行列に該タスクを追加する複数のスレッドを使用することをさらに包含する、項目２４に記載の方法。
【００３８】
（項目３１）
スレッドが、他のタスクに依存する場合に、タスクを再生する、項目３０に記載の方法。
【００３９】
（項目３２）
上記ＣＡＤソフトウェアは、プログラマブルロジックデバイス（ＰＬＤ）内のリソースを配置するための配置アルゴリズムを備える、項目２３に記載の方法。
【００４０】
（項目３３）
上記ＣＡＤソフトウェアは、パラレル解析アルゴリズムを備える、項目２３に記載の方法。
【００４１】
コンピュータ支援設計（ＣＡＤ）ソフトウェアにおけるパラレル化を提供するシステムは、コンピュータを含む。このコンピュータは、局所独立性を有するタスクのセットを同定することと、このタスクのセットの各タスクがパラレルに実行されるように、割り当てることとを行うように構成される。また、このコンピュータは、このタスクのセットの各タスクを実行するように構成される。
【発明を実施するための最良の形態】
【００４２】
（詳細な説明）
本発明のコンセプトは、ソフトウェア（例えば、ＣＡＤアルゴリズムまたはソフトウェア、あるいは、ＦＰＧＡ用ＣＡＤソフトウェア）をパラレル化する装置および関連方法に関する。開示されたコンセプトは、実行速度を改善するために、例えば、プロセッサをスレッド化して使用すること、あるいは、プロセッサを複数使用することによって、パラレルにソフトウェアまたはアルゴリズムを稼動（ｒｕｎ）させることを探求する。
【００４３】
一般的に言って、本発明のコンセプトは、様々な方法で、ソフトウェアをパラレルに稼動させること、あるいは、アルゴリズムをパラレルに実行することを検討する。図１および図２は、使用され得る技術の２つの例である。本発明の記載の利益を有する当業者には、必要に応じて、他の技術および例も使用され得ることは理解される。
【００４４】
図１は、複数のスレッドを用いて、例示的な実施形態に使用されるパラレル化技術を示す。図１に示されるアレンジメントは、タスクのセット１３、スケジューラ１０、および、スレッドのセット１６を含む。タスクのセット１３は、ＣＡＤソフトウェアまたはアルゴリズムが実行または稼動しようとする様々なタスクを構成する。一般的に、セット１３は、任意の所望の数のタスク、例えば、Ｎ個のタスクを含み得る。一方、スレッドのセット１６は、任意の所望または適切な数のスレッド、例えば、Ｋ個のスレッドを含み得る（ＮとＫとは、等しいことも等しくないこともある点に留意されたい）。
【００４５】
スケジューラ１０は、セット１３からタスクを受け入れ、１つ以上のコンピュータで実行するために、タスクをスケジュールする。より具体的には、スケジューラ１０は、セット１３内のタスクをセット１６内のスレッドに割り当てる。例えば、スケジューラ１０は、タスク１をスレッド１に、タスク２をスレッド２に、などと割り当て得る。スレッドに割り当てると、次いで、その結果、割り当てられた対応するタスクが実行される。
【００４６】
図２は、複数のプロセッサを用いる例示的な実施形態を使用されるパラレル化技術を示す。図２のアレンジメントは、タスクのセット１３、スケジューラ１０、１９とラベル付けされたプロセッサのセットまたはコンピュータ、あるいは、同様の適切な装置を含む。例えば、プロセッサのセット１９は、パラレルコンピュータ、大規模パラレルコンピュータなどで構成され得る。これは、本発明の記載の利益を有する当業者には、理解される。
【００４７】
タスクのセット１３は、ＣＡＤソフトウェアまたはアルゴリズムが実行または稼動しようとする様々なタスクを表わす。一般的に、セット１３は、任意の所望の数のタスク、例えば、Ｎ個のタスクを含み得る。一方、プロセッサのセット１９は、任意の所望または適切な数のプロセッサ、例えば、Ｍ個のプロセッサを含み得る（ＫとＭとは、等しいことも等しくないこともある点に留意されたい）。
【００４８】
スケジューラ１０は、セット１３からタスクを受け入れ、１つ以上のコンピュータで実行するために、タスクをスケジュールする。より具体的には、スケジューラ１０は、セット１３内のタスクをセット１９内のプロセッサに割り当てる。例えば、スケジューラ１０は、タスク１をプロセッサ１に、タスク２をプロセッサ２に、などと割り当て得る。タスクをプロセッサに割り当てると、次いで、その結果、割り当てられた対応するタスクが実行される。
【００４９】
この発明のコンセプトは、必要に応じて、様々なＣＡＤのソフトウェア、アルゴリズムおよびアプリケーションに適用され得る。適用される特定のエリアの一つは、ＰＬＤの設計および使用のためのＣＡＤソフトウェアを構成する（例えば、ＰＬＤリソースを使用して、ユーザの設計をインプリメントする）。以下の記述は、このようなＰＬＤおよびソフトウェアパラレル化技術の詳細を提供する。
【００５０】
図３は、本発明の例示的な実施形態によって設計または使用され得るＰＬＤの一般的なブロック図である。ＣＡＤソフトウェア内のソフトウェアをパラレル化する本開示のコンセプトは、所望の回路またはシステムをインプリメントするために、ＰＬＤ１０３の設計あるいはそのリソースの使用で、用いられ得る。
【００５１】
ＰＬＤ１０３は、構成回路網１３０、構成メモリ（ＣＲＡＭ）１３３、制御回路網１３６、プログラマブルロジック１０６、プログラマブル相互接続１０９、および、入出力回路網１１２を含む。さらに、ＰＬＤ１０３は、必要に応じて、テスト／デバッグ回路網１１５、１つ以上のプロセッサ１１８、１つ以上の通信回路網１２１、１つ以上のメモリ１２４、１つ以上の制御装置１２７、および、初期化回路１３９を含み得る。
【００５２】
本図が示すのは、ＰＬＤ１０３の簡略化されたブロック図であることに留意されたい。したがって、ＰＬＤ１０３は、他のブロックや回路網も含み得る。このことは、当業者には理解される。このような回路網の例は、クロック発生および分配回路、冗長回路などを含む。さらに、ＰＬＤ１０３は、必要に応じて、アナログ回路網、他のデジタル回路網、および／または、混成モード回路網を含み得る。
【００５３】
プログラマブルロジック１０６は、構成可能ロジック回路網あるいはプログラマブルロジック回路網（例えば、ルックアップテーブル（ＬＵＴ）、プロダクトタームロジック、マルチプレクサ（ＭＵＸ）、ロジックゲート、レジスタ、メモリなど）を含む。プログラマブル相互接続１０９は、プログラマブルロジック１０６に結合し、プログラマブルロジック１０６内の様々なブロックやＰＬＤ１０３内外の他の回路網との間で構成可能な相互接続（結合機構）を提供する。
【００５４】
制御回路網１３６は、ＰＬＤ１０３内の様々な動作を制御する。制御回路網１３６の監視下で、ＰＬＤ構成回路網１３０は、ＰＬＤ１０３の機能性をプログラムあるいは構成するために、構成データ（ストレージデバイス、ホストなどの外部ソースから取得する）を使用する。構成データは、典型的には、ＣＲＡＭ１３３に情報を格納するために使われる。ＣＲＡＭ１３３のコンテンツは、ＰＬＤ１０３の様々なブロック（例えば、プログラマブルロジック１０６およびプログラマブル相互接続１０９）の機能性を決定する。初期化回路１３９は、ＰＬＤ１０３のリセット時またはパワーアップ時に、様々な機能をもたらし得る。
【００５５】
入出力回路網１１２は、幅広い様々な入出力デバイスまたは回路から形成され得る。このことは、本発明の記載の利益を有する当業者なら理解される。入出力回路網１１２は、ＰＬＤ１０３の様々なパーツ（例えば、プログラマブルロジック１０６、および、プログラマブル相互接続１０９）に結合し得る。入出力回路網１１２は、外部回路網または外部デバイスと通信するために、ＰＬＤ１０３内の様々なブロックに対し、メカニズムおよび回路網を提供する。
【００５６】
テスト／デバッグ回路網１１５は、ＰＬＤ１０３内の様々なブロックおよび回路のテストおよびトラブルシューティングを容易にする。テスト／デバッグ回路網１１５は、本発明の記載の利益を有する当業者に周知の様々なブロックまたは回路を含み得る。例えば、テスト／デバッグ回路網１１５は、必要に応じて、ＰＬＤ１０３のパワーアップまたはリセット後に、テストを実行する回路を含み得る。また、テスト／デバッグ回路網１１５は、必要に応じて、コード化回路およびパリティ回路も含み得る。
【００５７】
ＰＬＤ１０３は、１つ以上のプロセッサ１１８を含み得る。プロセッサ１１８は、ＰＬＤ１０３内の他のブロックおよび回路に結合し得る。プロセッサ１１８は、ＰＬＤ１０３内外の回路からのデータおよび情報を受け取り、幅広い様々な方法で、情報を処理する。これは、本発明の記載の利益を有する当業者には、理解される。１つ以上のプロセッサ１１８は、デジタル信号プロセッサ（ＤＳＰ）を構成し得る。ＤＳＰは、必要に応じて、幅広い様々な信号処理タスク（例えば、圧縮、復元、音声処理、映像処理、フィルタ処理など）を実行できる。
【００５８】
ＰＬＤ１０３は、また、１つ以上の通信回路１２１も含み得る。本発明の記載の利益を有する当業者には、理解されるように、通信回路１２１は、ＰＬＤ１０３内の様々な回路とＰＬＤ１０３外の様々な回路との間でのデータおよび情報の交換を促進し得る。
【００５９】
ＰＬＤ１０３は、１つ以上のメモリ１２４、および、１つ以上の制御装置１２７をさらに含み得る。メモリ１２４は、ＰＬＤ１０３内の様々なデータおよび情報（例えば、ユーザデータ、中間結果、計算結果など）の格納が可能である。メモリ１２４は、必要に応じて、細かな形式（ｇｒａｎｕｌａｒ ｆｏｒｍ）またはブロック形式を有し得る。制御装置１２７は、ＰＬＤ外の回路網とインターフェースし、これらＰＬＤ外の回路網の動作および様々な機能を制御できる。例えば、制御装置１２７は、必要に応じて、外部のシンクロナスダイナミックランダムアクセスメモリ（ＳＤＲＡＭ）とインターフェースし、制御するメモリ制御装置１２７を構成し得る。
【００６０】
上述のように、ＰＬＤ１０３は、プログラマブルリソースの多数のブロックを含む。これらのリソースを使用して設計をインプリメントすることは、ＰＬＤ１０３の平面図内にこれらのブロックを配置すること（後述）を必然的に伴う。図４は、本発明のコンセプトを用いて、設計またはインプリメントされ得るＰＬＤの平面図を示す。
【００６１】
ＰＬＤ１０３は、二次元アレイとしてアレンジされたプログラマブルロジック１０６を含む。プログラマブル相互接続１０９は、水平な相互接続と垂直な相互接続としてアレンジされ、プログラマブルロジック１０６のブロックを互いに結合する。ユーザ設計をインプリメントするために、特定の様式で、これらブロックが配置され得ることは、本発明の記載の利益を有する当業者には、理解される。
【００６２】
例示的な実施形態において、ＰＬＤ１０３は、階層的構造を有する。換言すれば、プログラマブルロジック１０６の各ブロックは、順に、より小さな、あるいは、より細かなプログラマブルロジックブロックまたは回路を含み得る。例えば、一実施形態において、プログラマブルロジック１０６は、ロジックアレイブロック（ＬＡＢ）と命名された構成可能ロジックのブロックを形成し得、必要に応じて、各ＬＡＢは、ロジックエレメント（ＬＥ）または他の回路網を含み得る。
【００６３】
しかしながら、本発明の記載の利益を有する当業者には、術語および形態を変更して、幅広い様々な他のアレンジメントも可能であり、それらが本発明のコンセプトの範囲内に収まることは、理解される。さらに、図４は、プログラマブルロジック１０６のブロックを示すが、その平面図において、他あるいは追加のブロック（例えば、メモリ、プロセッサ、図３の他のブロックなど）とともにＰＬＤを使用し得、本発明のコンセプトから利点を活かし得る。これは、本発明の記載の利益を有する当業者には、理解される。
【００６４】
しかしながら、特定のアレンジメントまたは設計に関わらず、ＰＬＤのリソースを利用するＣＡＤソフトウェアまたはプログラムにおける発明のコンセプトを用いて、所望の回路またはシステムをインプリメントし得る。ＰＬＤ１０３のようなＰＬＤにおけるユーザ設計をインプリメントすると、以下に詳述されるように、必然的に、幾つかのステップまたはプロセスを伴う。
【００６５】
図５は、本発明の例示的な実施形態に従うＰＬＤ ＣＡＤソフトウェアを使用する様々なソフトウェアモジュールを示す。このモジュールは、設計エントリモジュール２０３、合成モジュール２０６、配置・ルートモジュール２０９、および、検証モジュール２１２を含む。以下の記述は、各モジュールの動作の簡単な説明を提供する。
【００６６】
本発明の記載の利益を有する当業者に理解されるように、ＣＡＤ技術は、様々なアプリケーションを有し得る。例は、設計領域、タイミング性能、パワー要求、および、ルーティング可能性を必要に応じて含む。
【００６７】
設計エントリモジュール２０３は、回路およびその挙動のグラフィックまたはテキスト記述（例えば、必要に応じて、図表、ハードウェア記述言語（ＨＤＬ）または波形など）を用いて、様々な設計記述ファイルの編集が可能である。ユーザは、設計エントリモジュール２０３を用いて、あるいは、必要に応じて、様々な電子設計自動化（ＥＤＡ）またはＣＡＤツール（例えば、業界標準ＥＤＡツール）を用いて、設計ファイルを生成し得る。ユーザは、必要に応じて、グラフィック形式、波形ベースの形式、図表形式、テキストまたはバイナリ形式、あるいは、これら形式の組み合わせで、設計を入力し得る。
【００６８】
合成モジュール２０６は、設計エントリモジュール２０３の出力を受ける。ユーザ提供の設計に基づき、合成モジュール２０６は、ユーザ提供の設計を実現する適切なロジック回路を生成する。１つ以上のＰＬＤ（明確に図示せず）は、合成された設計全体またはシステム全体をインプリメントする。また、合成モジュール２０６は、ユーザ設計の中の様々なモジュールの統合および適切な動作ならびにインターフェースを可能にする任意のグルーロジック（ｇｌｕｅ ｌｏｇｉｃ）を生成する。例えば、合成モジュール２０６は、１つのブロックの出力がもう１つのブロックの入力と適切にインターフェースするように適切なハードウェアを提供する。合成モジュール２０６は、設計全体またはシステム全体内で、モジュールそれぞれの仕様を満たすように適切なハードウェアを提供する。
【００６９】
さらに、合成モジュール２０６は、合成設計を最適化するためのアルゴリズムおよびルーチンを含み得る。最適化によって、合成モジュール２０６は、設計全体またはシステム全体をインプリメントする１つ以上のＰＬＤのリソースをより効率的に使用しようとする。合成モジュール２０６は、その出力を配置・ルートモジュール２０９に提供する。
【００７０】
配置・ルートモジュール２０９は、最適なロジックのマッピングおよび配置を実行するために、設計のタイミング仕様を使用する。このロジックのマッピングおよび配置は、ＰＬＤ内のルーティングリソースの使用を決定する。換言すれば、設計の一部のパーツに対して、ＰＬＤとの特定のプログラマブル相互接続を使用することによって、配置・ルートモジュール２０９は、設計全体またはシステム全体の性能を最適化するのに役立つ。ＰＬＤのルーティングリソースを適切に使用することによって、配置・ルートモジュール２０９は、設計全体またはシステム全体のクリティカルタイミングパス（ｃｒｉｔｉｃａｌ ｔｉｍｉｎｇ ｐａｔｈ）を満足するために役立つ。
【００７１】
配置・ルートモジュール２０９は、クリティカルタイミングパスを最適化し、本発明の記載の利益を有する当業者に周知の方法よりも速くタイミングクロージャ（ｔｉｍｉｎｇ ｃｌｏｓｕｒｅ）を提供することに役立つ。その結果、設計全体またはシステム全体は、より高速な性能（すなわち、より高速なクロックレートで動作すること、または、より高いスループットを有すること）を達成し得る。
【００７２】
検証モジュール２１２は、設計のシミュレーションおよび検証を実行する。このシミュレーションおよび検証は、設計がユーザの所定の仕様に適合することを検証しようとする。また、シミュレーションおよび検証は、設計のプロトタイプを作る前に何らかの設計問題を検出し、修正することを狙いとする。こうして、検証モジュール２１２は、ユーザが、設計全体またはシステム全体の全体的なコストを削減し、市場に出すまでの時間を短縮するのに役立つ。
【００７３】
検証モジュール２１２は、必要に応じ、様々な検証およびシミュレーションのオプションをサポートし、実行し得る。このオプションは、必要に応じ、機能検証、テストベンチ生成、静的タイミング解析、タイミングシミュレーション、ハードウェア／ソフトウェアシミュレーション、システム内検証、ボードレベルタイミング解析、信号品位解析と電磁環境両立性（ＥＭＣ）、フォーマルネットリスト（ｆｏｒｍａｌ ｎｅｔｌｉｓｔ）検証などを含み得る。このことは、本発明の記載の利益を有する当業者には、理解される。
【００７４】
必要に応じて、また、本発明の記載の利益を有する当業者には理解されるように、その他または追加の検証技術も実行され得ることに留意されたい。また、設計の検証は、適宜、必要に応じ、このフローの他の段階でも実行され得る。
【００７５】
多数（おそらく大部分）の従来の市販ＣＡＤアルゴリズムは、事実上、シリアルである。換言すれば、これらのアルゴリズムは、様々なタスクをパラレルではなく、むしろ、シリアルに実行する。これは驚くべきことではない。なぜなら、第一に、プロセッサクロック速度は、今日まで定期的に高速化されてきたし、第二に、頑強な（ｒｏｂｕｓｔ）パラレルソフトウェアを開発するのは、ずっと困難だからである。
【００７６】
上述のような傾向があるので、今日では、既存のアルゴリズムを、新たなパラレル処理能力に引き上げ、ユーザに利用可能なものに改変することは、ずっと重要である。ＣＡＤアルゴリズムは、一般的に実用ソフトウェアで最も遅いタイプであるから、このことは、特に正しい。典型的な稼働時間が、週末をフルに費やすことも非常に一般的である。パラレル化技術が使用されなければ、シリアルアルゴリズムは、将来これらのアルゴリズムを用いて解かれ得る更に複雑な問題に見合うように十分に高速化され得ない。
【００７７】
一般に、シリアルＣＡＤアルゴリズムをパラレル化するときに、２つのアプローチが使用される。第一のアプローチは、シリアルアルゴリズムを処分して、その代わりに、より内在的な並列処理を有するアルゴリズムを使用する。このオプションは、幾つかの不利な点を有する。
【００７８】
第一に、このアプローチは、設計者に対し、最初から、既存のコードを処分して、新たなパラレルコードを開発するということを要求する。多くの人々の長年にわたる努力は、現存するアルゴリズムを最適化することに注ぎ込まれてきた。この努力を放棄すると、新しいアルゴリズムの品質が同じレベルに達するまでには、その後何年もかからなければならなくなる。また、このアプローチは、設計者に利用可能なアルゴリズムの選択を制限する。一部のシリアルアルゴリズムは特定の問題に対し、より適しており、パラレルアルゴリズムを無理に使用すると、ソフトウェアツールの品質を損ね得る。
【００７９】
さらに、パラレルアルゴリズムが、決定を行うことは、比較的困難である。決定性アルゴリズムは、同じ入力で、複数回稼動させたとき、同じ結果を与える。しかしながら、パラレルプログラムまたはアルゴリズムは、同時に複数のセットの命令を実行し、各プロセッサによりこれらのセットに与えられるアクセスに依存し、結果は、アルゴリズムが稼動するたびに異なり得る。この性質のために、ユーザがアルゴリズムで得た結果を再現することは難しいし、また、ベンダにとっては、ユーザが遭遇するあらゆる問題からバグを取り除くことは難しい。
【００８０】
最後に、アルゴリズムを稼動させるために依然として単一のプロセッサを使用しているユーザに対し、上述の潜在的な品質のロスと上述のその他の欠点とを伴うパラレルアルゴリズムへの変更を強いることは、ユーザを不満にさせる。さらに、パラレルアルゴリズムは、一般的に、これらユーザに対して顕著な遅さを強いるオーバーヘッドを招く結果となる。ソフトウェアツールのベンダは、それゆえ、少なくとも短期間の間、双方のアルゴリズムのセットを維持する必要があり、それに伴い、維持コストが高くなる。
【００８１】
第二のオプションとして、異なる設定を有する利用可能な各プロセッサ上において、シリアルアルゴリズムを稼動させ得、最後に、最適な結果を採択する。この従来のアプローチは、第一のアプローチに比べ、インプリメントが容易であるが、同様に幾つかの制約を有する。
【００８２】
第一に、これは、高速化には寄与しない。これは、単に、結果を改善するために、アルゴリズムのコピーをより多く稼動させるに過ぎない。アルゴリズムに対して考えられる最速の稼働時間を欲するユーザは、このアプローチからは、ユーザの欲するものを得ることはできない。第二に、このアプローチは、拡張性がない。なぜなら、同じアルゴリズムを多数稼動させてより良好な結果を得るために、より多くのプロセッサを利用可能にするので、稼動するコピーの数が増えれば増えるほど、減速する結果となるからである。明らかに、両アプローチは、重大な制約を有する。しかしながら、本発明のコンセプトは、これらの制約を克服する技術を提供する。
【００８３】
より具体的には、本発明の方法は、多数のシリアルＣＡＤアルゴリズムが、その実行時間のほとんどを入力問題の異なる部分で特定のアクションまたはアクションのセットを実行するのに費やすという事実を活用する。このアクションは、多数回（しばしば、数万回）繰り返され、その結果、これらのアルゴリズムに対する稼働時間が比較的長くなる。これらアルゴリズムをシリアルにする特性は、各アクションが、自身の以前の各アクションの結果の知見を用いて（すなわち、以前のアクションに依存して）実行される。この特性は、つまり、１つのアクションが任意の時間に行われ得ること、あるいは、行われることを意味し、これが、アルゴリズムをシリアルに実行するときの制限になる。
【００８４】
しかしながら、連続的なアクションの所定のセットは、入力問題の独立部分に影響を与えることが多い。それゆえ、これらのアクションを全てシリアルに実行する必要はない。この特性は、特に、入力問題が比較的大きいときに維持される。例えば、数多くのアクション（＃１０〜＃２０を含み、＃１０〜＃２０のアクションは互いに独立）を含む問題においてである。換言すれば、アクションの実行は、他のアクションの実行とは無関係である。
【００８５】
このような状況において、アルゴリズムは、これら１１個のアクションをパラレルに実行し得る。例示的な実施形態において、本発明の技術は、パラレルな実行の結果を形成するために、局所独立性を使用する。例えば、アクション＃２１が、以前のアクションの２つ（例えば、＃１３および＃１７）に依存する場合、アルゴリズムは、＃２１に進むまでに、＃１３および＃１７を終了しなくてはならない（そうでなければ、結果は決定論的なものではない）。そうでない場合、アルゴリズムは、アクションをパラレルに実行し得る。局所独立性は、この方法が使用するものであり、並列性を形成する。それゆえ、性能が改善される。
【００８６】
発明の技術は、アクションの待ち行列を使用する。ここで、待ち行列は、互いに独立なアクションでロードされる。この待ち行列は、シリアルにロードされ、全てのアクションが独立であることを確実にする。本発明の１つの変種として、待ち行列は、シリアルアルゴリズムがアクションを実行するのと同じ順序でロードされる。このアクションは、アルゴリズムのパラレル版の結果が、シリアル版の結果と、同様または同一になることを確実にする。
【００８７】
図６は、この技術を簡略化したブロック図である。タスク１３のセットは、スケジューラ１０に入力される。スケジューラ１０は、タスクを待ち行列２５０に提供し、上述のように、局所独立性を提供する。タスクは、待ち行列２５０から出力され、パラレルに実行される（局所独立性が存続する限り）。
【００８８】
本発明の別の変種として、アクションは、待ち行列で保持される独立アクションの数が最大となるような方法で選択され得る。一度、この待ち行列がロードされたら、全ての利用可能なプロセッサは、あらゆる任意または所望の順番で処理され得る。なぜなら、アクションの独立性が、保証されるからである。一度、待ち行列の全てのアクションが終了したら、待ち行列は、再びロードされ、この処理が繰り返される。
【００８９】
この技術をより詳細に示すと、配置の例が、配置アルゴリズムをパラレル化するために使用され得る方法を示すために提供される。配置アルゴリズムが、入力として、回路のネットリスト表現およびデバイスの平面図表現を取り込む。Ｑｕａｒｔｕｓ ＩＩソフトウェア（本出願の譲受人であるＡｌｔｅｒａ Ｃｏｒｐｏｒａｔｉｏｎから市販）において、例えば、ネットリストは、ユーザのロジック回路におけるブロック（例えば、ロジックアレイブロックすなわちＬＡＢ、ＲＡＭブロック、乗算器ブロックなど）を表す。平面図は、ＰＬＤまたは同様のデバイスで利用可能なブロックを表す。
【００９０】
シリアル配置アルゴリズムは、以下のように動作し得る。品質とはほとんどまたは全く無関係に、初期の適法な配置をできるだけ迅速または比較的迅速に生成する。その結果、ネットリスト内の各ブロックは、平面図内の位置に割り当てられる。第二に、ネットリストからランダムに１つのブロックをつまみ出し、ランダムな位置に移動させようとする。ソースブロックと既に存在する任意のブロックとを交換する。第三に、この配置への変更が良好であるか、あるいは、望ましいものであるかを評価する。良好または望ましい場合は、その変更を実施する。そうでない場合、変更を処分する。この評価は、幾つかの測定法で行われることが多いが、一般的には、この測定法は、互いに近くに配置されて、接続または結合されるブロックを保つように試みる。最終的に、第二のステップに戻り、所定の回数の移動が行われるまで繰り返される（例えば、この回数は、ネットリストのブロック数の１０００倍であり得る）。
【００９１】
上述の配置アルゴリズムは、本質的にシリアルである。なぜなら、第三のステップでの変更をコミットする決定は、アルゴリズムの全ての将来の繰り返し（すなわち、移動）に影響を与えるからである。例えば、図７の例を仮定する。ブロック＃６は、平面図のＸ＝３およびＹ＝４にあり、アルゴリズムの第一の移動は、Ｘ＝３０およびＹ＝４０にあるブロック＃２０と交換することを試みると仮定する。
【００９２】
さらに、アルゴリズムの第二の移動が、ブロック＃２１（たまたま、ブロック＃２０に接続または結合されている）を、Ｘ＝３０，Ｙ＝４からＸ＝１，Ｙ＝１に移動させるものと仮定する。図８は、第一の移動が受け入れられた場合の位置と接続性がどうなるかを示す。
【００９３】
アルゴリズムの第一の移動が、その移動を受け入れたとき、第二の移動（ブロック＃２１を（１，１）に移動させようと試みる）は、より受け入れられやすい。なぜなら、ブロック＃２１の新たな位置（１，１）は、それが接続または結合されているブロック（すなわち、現在の位置（３，４）を有するブロック＃２０）に、より近いからである。しかしながら、第一の移動が受け入れられなかった場合（図７のままの状況）、ブロック＃２１を（１，１）に移動することは、良い移動であるとは思われない。なぜなら、その接続または結合されたブロック（すなわち、ブロック＃２０）は、（３０，４０）にあるからであり、また、現在のブロック＃２１の位置（すなわち、３０，４）が、位置（１，１）よりも近いからである。
【００９４】
この例は、上記のシリアルアルゴリズムのようなアルゴリズムがパラレルに稼動する場合に直面し得る問題を示す。例えば、移動＃１および＃２が同時に稼動する場合、＃２が受け入れられるかどうかは、移動＃２が評価される前に、移動＃１が終了したかどうかに依存する。
【００９５】
アルゴリズムが変更されなければ、アルゴリズムをパラレルに稼動させることは、結果として、その接続または結合されたブロックが存在する最終位置を追うブロック追跡になる。また、これは、結果を非決定論的なものとする。なぜなら、たとえ同じ回路での異なる稼動に対してであっても、所定の移動がどのくらいの時間で完了するのかを予見することは一般に不可能だからである。
【００９６】
これらの問題を解決するための本発明の技術を適用すると、上述のように、独立した移動の待ち行列を形成し得る。上記の例から第一の移動は、待ち行列の中に配置され、第二の移動は、もはや待ち行列の中に入ることは許可されない（なぜなら、第二の移動は、ブロック＃２１とブロック＃２０との間の接続または結合を介して、第一の移動に依存するからである）。この待ち行列のロードは、停止され、移動が処理されるか、または、上述のように、移動が処理される前に、待ち行列がその他の独立な移動を用いてロードされ得る。いずれの場合も、待ち行列が大きければ大きいほど、高速化は、複数のプロセッサを有することから、その速度アップは大きくなる。例えば、常に２つ以下の移動を有する待ち行列は、２つのプロセッサ（しかし、４つ以上ではない）を使用することからメリットを得る。
【００９７】
上記の技術は、待ち行列のシリアルなロードを用いることに留意されたい。移動を提案する時間が比較的短い場合、シリアルにロードしても問題は生じない。例えば、ロードに、シリアル稼働時間の５％を要し、評価に９５％を要するアルゴリズムの場合、稼働時間は、２つのプロセッサを有するマシンでは、理論的には１．９倍の係数で速度アップし得る。しかしながら、シリアル部分の比率が高い場合、このメリットは、劇的に低下し得る。例えば、このアルゴリズムの半分がパラレル化されたに過ぎない場合、２つのプロセッサからなるシステムの速度アップは、１．３３の係数に制限される。
【００９８】
比較的より高度な待ち行列を使用すると、この問題を緩和することができる。配置問題に戻ると、移動同士での依存性には、２つのソースがあることが分かる。（１）独立した移動の提案が不可能であり得ること、および（２）移動の独立した評価が不可能であり得ることである。
【００９９】
これらの２つの場合は、同様または同一に扱われるが、両者は非常に異なる。例えば、単一のブロックに対して２つの移動が提案された場合を考える。第一の移動が終わるか、拒絶されるかまで、第二の移動を提案すらできないことは明らかである。なぜなら、第一の移動の後、ブロックがどこにあるかが分からないからである。
【０１００】
一方、２つのブロックの場合で、互いに近くに移動させたいという場合を考える。双方のブロックで、同時に移動を提案することは容易である。その双方を独立して評価はできない（なぜなら、どちらのブロックを最初に移動させるかによって、第二の移動が、良好ないこと、望ましくないこと、あるいは、有利でないこともあり得るからである）。しかしながら、ブロックに対する移動が、その双方で評価される前であっても、他の移動に進むことも、提案することも可能である。パラレルな観点から、そのようにすることは有利である。なぜなら、任意の移動が行き詰まり（ｓｔａｌｌ）の原因となるときのような多くの環境下よりも、すべてのプロセッサに対して、仕事を生成し続けるようにできるからである。
【０１０１】
以下は、この改善の例を記載する。図９の配置を考える。ブロック３０３〜３１５に関して、幾つかの移動が提案されている。上述した元々の本発明のアルゴリズムは、第一の移動、次いで、第二の移動を提案すると、ストップする。なぜなら、２つの移動は、接続または結合されたブロックに関連しているからである。それゆえ、移動＃２を受け入れるか、拒絶するかの決定は、＃１の移動に依存する（換言すれば、移動＃１は、ブロック３０３を移動させ、移動＃２は、ブロック３０３に結合されたブロック３０６を移動させる）。
【０１０２】
しかしながら、次いで、移動＃２および＃３（ブロック３０９の移動）をパラレルに評価し、次いで、＃４（ブロック３１２の移動）、＃５（ブロック３１５の移動）および＃６（ブロック３０３の移動）、そして、最終的に、＃７（ブロック３１８の移動）を評価し得る。配置が、３回ストップしたこと、そして、４つの「セット」の移動において、そのセットの半分は、単一のブロックの移動であったことに留意されたい。こうして、半分の時間で、（一例として）デュアルコアのマシン上の１つのプロセッサは、遊んでいる。
【０１０３】
しかしながら、この代わりに、もはや移動が提案されなくなったときに、ストップする場合、状況は改善する。例えば、移動＃１〜＃５までをストップすることなく、提案し得る。移動＃６でストップすることに留意されたい。なぜなら、移動＃６は、ブロック（すなわち、ブロック３０３）をターゲットにし、上記ブロックは、他の移動の結果、既に移動している可能性があるからである。移動＃１が受け入れられるか、拒絶されると、すぐに再開して、移動＃７の提案に進む。換言すれば、１つ以上の移動に１つ以上の依存が、解決されたときに、再開し得る。
【０１０４】
ここで、任意の与えられた時間に、パラレルに評価され得る少なくとも２つの移動（移動＃１とパラレルな移動＃３、移動＃３とパラレルな移動＃４、移動＃４および移動＃２とパラレルな＃５、移動＃３とパラレルな移動＃６、ならびに、移動＃３、＃５および＃６とパラレルな移動＃４、＃５および＃７）があるとする。本発明の記載の利益を有する当業者は、この技術を用いると、一度に４つまたは８つあるいはそれ以上の移動でさえも確実に生成し得る更に大きな機会を有し得る。こうして、必要に応じて、３つ以上のプロセッサを有するマシンからそのメリットを得ることができる。
【０１０５】
このアルゴリズムをインプリメントするために、本発明のコンセプトは、より高度または「スマート」な、あるいは、改善または強化された待ち行列を使用する。より具体的には、その移動の順番を保ち、利用可能な次の移動においてプロセッサが機能できるようにする代わりに、そのような待ち行列は、各移動が評価される前に、受け入れられるか拒絶され得る最後の移動を追跡する。例えば、移動＃２は、移動＃１をリストに載せ、移動＃６は、移動＃２（しかし、移動＃３、＃４および＃５ではない）をリストに載せる。例えば、移動＃２の評価し終わったプロセッサは、たとえ移動＃３、＃４および＃５が完了していなくても、移動＃６で機能を開始する。
【０１０６】
この技術は、様々な状況で使用され得る。例えば、必要に応じて、このような待ち行列は、図６の待ち行列２５０と置換され得る。代替として、必要に応じて、本発明の記載の利益を有する当業者には理解されるように、他のアレンジメントも使用され得る。
【０１０７】
強化または改善された待ち行列によって可能になった速度アップが十分でない場合でもまた、パラレルに機能させたいと望む入力問題の一部分が選択された異なるスレッドを有することが可能である。こうした場合であっても、依然、決定論的な結果を維持していることに留意されたい。上記の配置の例を用いると、このアプローチは、移動をパラレルに評価するだけでなく、移動をパラレルに生成することを意味する。この技術は、以下に記載され、図１０に図示されるように、動作する。
【０１０８】
上述のように、３５０で、全てのアクションに数字のＩＤが与えられる。しかしながら、３５５で、複数のスレッドは、入力問題のどの部分（例えば、各スレッドが移動することを提案するブロック）を選択して調査するかを決定し得る。しかしながら、それぞれのスレッドは、実際には、アクションを実行しない。
【０１０９】
次いで、３６０で、スレッドは、アクションをサブミッション待ち行列に追加する。この待ち行列は、アクションを任意の順番で受け入れるが、アクションをＩＤ番号の順に発信する。例えば、アクション＃１および＃３が追加された場合、待ち行列は、アクション＃２が追加されるまで、その待ち行列は、その中に１つのアクション（＃１）を有するよう見える。
【０１１０】
アクションが待ち行列から除去されたら、３６５で、上述したような依存関係解析を実行する。あるアクションが、以前のアクションに依存することが分かった場合、上述のように、そのアクションを処理する。しかしながら、アクション自身が、無効なこともあり得る。例えば、期待された場所に今や存在し得ないブロックに対して、移動を提案し得る。この状況が本明細書で記述されたバージョンの技術を用いて生じた場合、新たなアクションの生成が、単純にストップされ得る。改善技術を用いると、アクションをパラレルに生成する複数のスレッドを有し得る。このことは、比較的より深刻な制約であり得る。
【０１１１】
一度、この比較的より深刻な種類の依存性が見出されると、３７０で、スレッドは、アクションを（好ましくはできるだけ迅速に）再生成するように、単に求められる。例えば、「できるだけ迅速に」とは、標的ブロックが実際に移動したかどうかが判断されるときであり得る。移動していなかった場合、その移動を単に評価し、移動していた場合、新たな移動を最初から提案または検討し、代わりに、その移動を評価する。
【０１１２】
この技術の利点は、アルゴリズムのどの部分もシリアルでない（チェッカの依存性を除く。これは、比較的高速であると仮定する）ことなので、与えられた固有の依存性の中で、理論的に可能な限り、プログラム全体を加速できることが期待される。このアルゴリズムは、それ自身の新たな依存性をほとんど全く導入しないことに留意されたい。
【０１１３】
特定のアルゴリズムに特有なＰＬＤ ＣＡＤのアプリケーション以外の他のアプローチもある。この特定のアルゴリズムは、アルゴリズム設計の柔軟性に著しい影響を与えることなく、パラレル処理能力のメリットを享受して使用され得る。一例は、パラレル解析である。
【０１１４】
より具体的には、最適化アルゴリズムは、様々な設計目標を達成するのに、どのくらいの努力が付与されるべきか（そして、その努力をどこに付与すべきか）を決定するために、解析エンジンに頼ることが多い。これらの解析エンジンは、現在の状態のスナップショットを取り、その状態に対する解析の結果を返す。図１１に示されるシリアルアルゴリズムは、解析を待ち、その解析が行われたら進む（例えば、最適化フェーズ４０３Ｂは、解析フェーズ４０６の結果を待ち、次いで、その入力を最適化フェーズ４０３Ａから受信する）。その結果、上述の不利な点を有する。
【０１１５】
このアルゴリズムをパラレルにするため、絶えず状態のスナップショットを取り、その解析を実行する追加のプロセッサを有し得る。この解析結果は、解析結果が利用可能であるときに解析に用いられる状態が現在の状態でないために、１つの不都合を有する。しかしながら、一方で、並列化は、効率を向上し、リソースの需要を削減する。図１２は、この処理がどのように機能するかを示す。
【０１１６】
図１２に示される技術において、解析および最適化がパラレルに実行され得る。例えば、最適化フェーズまたはエンジン４０３Ａは、解析フェーズまたはエンジン４０６Ａとともに、パラレルに、あるいは、同時に、動作し得る。同様に、最適化フェーズまたはエンジン４０３Ｂは、解析フェーズまたはエンジン４０６Ｂとともに、パラレルにあるいは、同時に、動作し得る。このシナリオにおいて、解析フェーズは、以前の最適化状態で実行される。解析フェーズの結果は、最適化の状態が潜在的に変化した後に、最適化フェーズにフィードバックされる。
【０１１７】
各解析ステップへの入力は、その出力を使用する状態とは異なる最適化状態からであることに留意されたい。例えば、最適化ステップが、配置（例えば、数千の移動がブロックに行われる）であり、解析ステップが、タイミング解析であると仮定する。この技術は、解析および最適化が同時またはパラレルに実行されるというメリットを提供する。それでも、潜在的に（しかし、必然的にではない）、より少ない最適化ソリューションを代償にする。
【０１１８】
この技術が適用され得る解析の例は、タイミング解析（回路における各経路のタイミング性能の決定）、混雑解析（設計の配置に基づいて、ルーティング混雑に直面しそうなチップのエリアの決定）、および設計解析（最適化に焦点をより良く合わせるのに、望ましい、または有利である（あるいは要求される）設計の部分の決定）を含む。列挙した例は、単に例示的なものであり、この技術は、他のアプリケーションまたは状況においても使用され得ることには留意されたい。このことは、本発明の記載の利益を有する当業者には、理解される。
【０１１９】
上述のように、コンピュータシステムまたはプロセッサ上で、本発明に従うアルゴリズムまたはソフトウェアを稼動または実行し得る。図１３は、本発明に従う情報を処理する例示的なシステムのブロック図を示す。
【０１２０】
システム１０００は、コンピュータデバイス１００５、入力デバイス１０１０、ビデオ／ディスプレイデバイス１０１５、および、ストレージ／出力デバイス１０２０を示す。しかしながら、必要に応じて、これらデバイスのそれぞれを２つ以上含み得る。
【０１２１】
コンピュータデバイス１００５は、入力デバイス１０１０、ビデオ／ディスプレイデバイス１０１５、および、ストレージ／出力デバイス１０２０に結合される。システム１０００は、必要に応じて、例えば、関連コンピュータデバイスまたはシステムのセットのように、２つ以上のコンピュータデバイス１００５を含み得る。
【０１２２】
システム１０００は、ユーザからの入力と関連し得る。ユーザは、典型的には、システム１０００に、特定の所望の情報処理タスク（回路シミュレーションを含む）を実行させる。システム１０００は、部分的に、コンピュータデバイス１００５を用いて、これらのタスクを実行する。コンピュータデバイス１００５は、中央演算処理装置（ＣＰＵ）のような情報処理回路網を含む。しかしながら、当業者には理解されるように、２つ以上のＣＰＵまたは情報処理回路網を含み得る。
【０１２３】
入力デバイス１０１０は、ユーザからの入力を受け入れ、その入力をコンピュータデバイス１００５で処理するために、利用可能にする。ユーザ入力は、必要に応じて、データ、命令、または、その双方を含み得る。入力デバイス１０１０は、英数字入力デバイス（例えば、キーボード）、ポインティングデバイス（例えば、マウス、ローラボール、ライトペン、タッチセンサ式ディスプレイ、またはタブレット）、あるいは、その双方から構成され得る。ユーザは、英数字キーボードを動作し、ＡＳＣＩＩ文字のようなテキストをコンピュータデバイス１００５に提供する。同様に、ユーザは、ポインティングデバイスを動作し、カーソル位置または制御情報をコンピュータデバイス１００５に提供する。
【０１２４】
ビデオ／ディスプレイデバイス１０１５は、ユーザに画像を提供する。視覚画像には、コンピュータデバイス１００５の動作に関する情報（例えば、グラフ、ピクチャ、画像、および、テキスト）も含み得る。ビデオ／ディスプレイデバイスは、当業者なら理解されるように、コンピュータモニタまたはディスプレイ、投影デバイスなどを構成し得る。システムが、タッチセンサ式ディスプレイの場合、また、ディスプレイが動作して、ユーザ入力をコンピュータデバイス１００５に提供し得る。
【０１２５】
ストレージ／出力デバイス１０２０は、コンピュータデバイス１００５が追加の処理または後の引き出し（例えば、ソフトコピー）を行うための情報を格納し、様々な形式（ハードコピー）で情報を表示する。一例として、ストレージ／出力デバイス１０２０は、所望の媒体上に、所望の形式で情報を格納できる磁気ドライブ、光学ドライブ、または磁気光学ドライブから構成され得る。別の例として、ストレージ／出力デバイス１０２０は、コンピュータデバイス１００５からの情報を印刷表示またはプロット表示を生成するプリンタ、プロッタ、または、他の出力デバイスであり得る。
【０１２６】
コンピュータ可読媒体１０２５は、コンピュータデバイス１００５と構造的および機能的に相互関連する。コンピュータ可読媒体１０２５は、機能記述マテリアルを格納、コード化、記録、および／または、具現化する。例としては、機能記述マテリアルには、コンピュータプログラム、コンピュータコード、コンピュータアプリケーション、および／または、情報構造（例えば、データ構造またはファイルシステム）が含まれ得る。コンピュータ可読媒体１０２５によって、格納、コード化、記録、および／または、具現化されると、機能記述マテリアルは、機能性を伝える。機能記述マテリアルは、コンピュータ可読媒体１０２５と相互に関係付ける。
【０１２７】
機能記述マテリアルの中の情報構造は、情報構造と、コンピュータ可読媒体１０２５および／またはシステム１０００の他の局面との間の構造的および機能的相互関係を規定する。これらの相互関係は、情報構造の機能性の実現化を可能にする。さらに、コンピュータプログラムは、このような機能記述マテリアル内で、コンピュータプログラムと、コンピュータ可読媒体１０２５および／またはシステム１０００の他の局面との間の構造的および機能的相互関係を規定する。これらの相互関係は、コンピュータプログラムの機能性の実現化を可能にする。
【０１２８】
例として、コンピュータデバイス１００５は、コンピュータデバイス１００５のコンピュータメモリ（図には明示せず）の中で、機能記述マテリアルを読み取り、アクセスし、コピーする。コンピュータデバイス１００５は、コンピュータメモリ内に存在するマテリアルに応答して動作する。コンピュータデバイス１００５は、コンピュータデバイス１００５に追加の動作を実行させるコンピュータアプリケーションを処理する動作を実行し得る。従って、機能記述マテリアルは、コンピュータデバイス１００５が処理を実行し、動作を実行する方法と機能的相互関連を示す。
【０１２９】
さらに、コンピュータ可読媒体１０２５は、コンピュータデバイス１００５がコンピュータ情報、プログラム、コードおよび／またはアプリケーションにアクセスし得る装置を構成する。コンピュータデバイス１００５は、コンピュータデバイス１００５に追加の動作を実行させるコンピュータ情報、プログラム、コードおよび／またはアプリケーションを処理し得る。
【０１３０】
当業者には理解されるように、コンピュータ可読媒体１０２５は、様々な方法でインプリメントされ得ることに留意されたい。例えば、コンピュータデバイス１００５内のメモリは、必要に応じて、コンピュータ可読媒体を構成し得る。代替として、コンピュータ可読媒体１０２５は、関連、相互関係付け、結合（例えば、導体、ファイバなど）、または、ネットワーク化されたコンピュータ可読媒体のセットを含み得る。例えば、コンピュータデバイス１００５は、必要に応じて、機能記述マテリアルをコンピュータ可読媒体１０２５、ネットワーク、あるいは、その双方から受信し得る。
【０１３１】
必要に応じて、また、本発明の記載の利益を有する当業者なら分かるように、本発明のコンセプトは、プログラマブルまたは構成可能ロジック回路網（業界で他の名称でも周知）を有するＩＣを含む様々なＩＣに有効に適用され得ることに留意されたい。このような回路網には、例えば、複合プログラマブルロジックデバイス（ＣＰＬＤ）、プログラマブルゲートアレイ（ＰＧＡ）、フィールドププログラマブルゲートアレイ（ＦＰＧＡ）、および、構造化特定用途向けＩＣ（すなわち、構造化ＡＳＩＣ）を含む。
【０１３２】
図面に関して言うと、図示された様々なブロックは、概念的機能および信号の流れを主として表し得ることを、当業者は気付き得る。実際の回路インプリメンテーションは、様々な機能ブロック用に、個別の同一のハードウェアを含むことも含まないこともあり得、図示された特定の回路網を用いることも用いないこともあり得る。例えば、必要に応じて、１つの回路ブロックに様々なブロックの機能が組み合わされ得る。さらに、必要に応じて、単一のブロックの機能を幾つかの回路ブロックで実行し得る。本発明の記載の利益を有する当業者なら理解されるように、回路インプリメンテーションの選択は、所定のインプリメンテーションに対する特定の設計および性能仕様などの様々な因子に依存する。また、本発明の記載の利益を有する当業者には、上述した事項に加え、本発明の他の改変や代替的な実施形態は明白である。したがって、本記述は、当業者に、本発明の実行を教示するものであり、単に例示的なものに過ぎないと解釈されるべきである。
【０１３３】
図示され、記載された発明の形式は、現在のところ、好ましい実施形態あるいは例示的な実施形態として考えられるべきである。当業者なら、本明細書に記載した発明の範囲から逸脱することなく、パーツの形状、サイズおよびアレンジメントを様々に変更し得る。例えば、当業者は、本明細書に図示され記載されたエレメントを同等のエレメントで代替し得る。さらに、本発明の記載の利益を有する当業者は、本発明の範囲から逸脱することなく、本発明のある特徴を他の特徴とは、独立して使用し得る。
【図面の簡単な説明】
【０１３４】
添付図面は、本発明の例示的な実施形態を示すだけであって、本発明の範囲を限定するものと考慮または解釈されるべきではない。本発明の記載の利益を有する当業者は、開示された発明のコンセプトが他の同じように有効な実施形態にも役立つことを理解し得る。図面において、２つ以上の図面で使用される同じ数字符号は、同等、類似または等価の機能性、コンポーネントまたはブロックを示す。
【図１】図１は、複数のスレッドを用いて、例示的な実施形態で使用されるパラレル化技術を示す。
【図２】図２は、複数のプロセッサを用いて、例示的な実施形態で使用される別のパラレル化技術を示す。
【図３】図３は、本発明の例示的な実施形態を用いて、指定または使用され得るＰＬＤの一般的なブロック図を示す。
【図４】図４は、本発明のコンセプトを用いて、設計またはインプリメントされ得るＰＬＤの平面図を示す。
【図５】図５は、本発明の例示的な実施形態に従うＰＬＤ ＣＡＤソフトウェアを使用する様々なソフトウェアモジュールを示す。
【図６】図６は、パラレル化技術の簡略化したブロック図を示す。
【図７】図７は、デバイス平面図の初期構成の例を示す。
【図８】図８は、リソースの移動を受け入れた後の図７のデバイス平面図を示す。
【図９】図９は、デバイス平面図におけるリソースの移動の提案を示す。
【図１０】図１０は、例示的な実施形態に従うパラレル化技術を示す。
【図１１】図１１は、シリアル解析アルゴリズムの例を示す。
【図１２】図１２は、解析アルゴリズムのパラレル化の例を示す。
【図１３】図１３は、開示されたコンセプトを用いて情報を処理するシステムのブロック図を示す。
【特許請求の範囲】
【請求項１】
コンピュータを備えるコンピュータ支援設計（ＣＡＤ）ソフトウェアのパラレル化を提供するシステムであって、該コンピュータは、
独立性を有するタスクのセットを同定することと、
該タスクのセットの各タスクをパラレルに実行されるように割り当てることと、
該タスクのセットの各タスクを実行することと
を行うように構成される、システム。
【請求項２】
前記コンピュータは、前記タスクのセットを用いて待ち行列をロードするように構成される、請求項１に記載のシステム。
【請求項３】
前記待ち行列は、前記パラレル化されたＣＡＤソフトウェアがシリアルアルゴリズムと同様の結果を生成するように、シリアルＣＡＤアルゴリズムと同様な順番でロードされる、請求項２に記載のシステム。
【請求項４】
前記タスクのセットは、前記待ち行列内に保持される独立なアクションの数を最大化するように選択される、請求項２に記載のシステム。
【請求項５】
前記タスクは、任意の順番で実行される、請求項４に記載のシステム。
【請求項６】
前記待ち行列は、前記タスクのセットが実行される前に、該タスクのセットの全てのタスクを用いてロードされる、請求項２に記載のシステム。
【請求項７】
前記待ち行列は、前記タスクのセットが実行されている間に、追加のタスクが提案されることを可能にする強化待ち行列を備える、請求項２に記載のシステム。
【請求項８】
複数のスレッドが、実行されるべきそれぞれのタスクを決定し、該タスクを待ち行列に追加する、請求項２に記載のシステム。
【請求項９】
スレッドが、他のタスクに依存する場合に、タスクを再生する、請求項８に記載のシステム。
【請求項１０】
前記ＣＡＤソフトウェアは、プログラマブルロジックデバイス（ＰＬＤ）内のリソースを配置するための配置アルゴリズムを備える、請求項１に記載のシステム。
【請求項１１】
前記ＣＡＤソフトウェアは、パラレル解析アルゴリズムを備える、請求項１に記載のシステム。
【請求項１２】
コンピュータ支援設計（ＣＡＤ）ソフトウェアをパラレル化するようにコンピュータによって処理するために適合したコンピュータアプリケーションを備える、コンピュータプログラム製品であって、
該コンピュータアプリケーションは、該コンピュータに
独立性を有するタスクのセットを同定することと、
該タスクのセットの各タスクをパラレルに実行されるように割り当てることと、
該タスクのセットの各タスクを実行することと
を行わせるように構成される、コンピュータプログラム製品。
【請求項１３】
前記タスクのセットを用いて前記コンピュータに待ち行列をロードさせる、請求項１２に記載のコンピュータプログラム製品。
【請求項１４】
前記パラレル化されたＣＡＤソフトウェアがシリアルアルゴリズムと同様の結果を生成するように、シリアルＣＡＤアルゴリズムと同様な順番で前記コンピュータに前記待ち行列をロードさせる、請求項１３に記載のコンピュータプログラム製品。
【請求項１５】
前記待ち行列内に保持される独立なアクションの数を最大化するように、前記コンピュータに前記タスクのセットを選択させる、請求項１３に記載のコンピュータプログラム製品。
【請求項１６】
前記コンピュータに、前記タスクを任意の順番で実行させる、請求項１５に記載のコンピュータプログラム製品。
【請求項１７】
前記タスクのセットが実行される前に、該タスクのセットの全てのタスクを用いて前記待ち行列を前記コンピュータにロードさせる、請求項１３に記載のコンピュータプログラム製品。
【請求項１８】
前記タスクのセットが実行されている間に、追加のタスクが提案されることを可能にする強化待ち行列を、前記コンピュータに使用させる、請求項１３に記載のコンピュータプログラム製品。
【請求項１９】
実行されるべきそれぞれのタスクを決定し、該タスクを待ち行列に追加する複数のスレッドを、前記コンピュータに使用させる、請求項１３に記載のコンピュータプログラム製品。
【請求項２０】
他のタスクに依存する場合に、タスクを再生するスレッドを、前記コンピュータに使用させる、請求項１９に記載のコンピュータプログラム製品。
【請求項２１】
プログラマブルロジックデバイス（ＰＬＤ）内のリソースの配置を、前記コンピュータに実行させる、請求項１２に記載のコンピュータプログラム製品。
【請求項２２】
パラレル解析アルゴリズムを、前記コンピュータに実行させる、請求項１２に記載のコンピュータプログラム製品。
【請求項２３】
コンピュータ支援設計（ＣＡＤ）ソフトウェアをパラレル化する方法であって、該方法は、
独立性を有するタスクのセットを同定することと、
該タスクのセットの各タスクをパラレルに実行されるように割り当てることと、
該タスクのセットの各タスクを実行することと
を包含する、方法。
【請求項２４】
前記タスクのセットを用いて待ち行列をロードすることをさらに包含する、請求項２３に記載の方法。
【請求項２５】
前記パラレル化されたＣＡＤソフトウェアがシリアルアルゴリズムと同様な結果を生成するように、シリアルＣＡＤアルゴリズムと同様な順番で待ち行列をロードすることをさらに包含する、請求項２４に記載の方法。
【請求項２６】
前記タスクのセットを、前記待ち行列内に保持される独立なアクションの数を最大化するように選択することをさらに包含する、請求項２４に記載の方法。
【請求項２７】
前記タスクを任意の順番で実行することをさらに包含する、請求項２６に記載の方法。
【請求項２８】
前記タスクのセットが実行される前に、該タスクのセットの全てのタスクを用いて前記待ち行列をロードすることをさらに包含する、請求項２４に記載の方法。
【請求項２９】
前記待ち行列は、前記タスクのセットが実行されている間に、追加のタスクが提案されることを可能にする強化待ち行列を備える、請求項２４に記載の方法。
【請求項３０】
実行されるべきそれぞれのタスクを決定し、前記待ち行列に該タスクを追加する複数のスレッドを使用することをさらに包含する、請求項２４に記載の方法。
【請求項３１】
スレッドが、他のタスクに依存する場合に、タスクを再生する、請求項３０に記載の方法。
【請求項３２】
前記ＣＡＤソフトウェアは、プログラマブルロジックデバイス（ＰＬＤ）内のリソースを配置するための配置アルゴリズムを備える、請求項２３に記載の方法。
【請求項３３】
前記ＣＡＤソフトウェアは、パラレル解析アルゴリズムを備える、請求項２３に記載の方法。
【請求項１】
コンピュータを備えるコンピュータ支援設計（ＣＡＤ）ソフトウェアのパラレル化を提供するシステムであって、該コンピュータは、
独立性を有するタスクのセットを同定することと、
該タスクのセットの各タスクをパラレルに実行されるように割り当てることと、
該タスクのセットの各タスクを実行することと
を行うように構成される、システム。
【請求項２】
前記コンピュータは、前記タスクのセットを用いて待ち行列をロードするように構成される、請求項１に記載のシステム。
【請求項３】
前記待ち行列は、前記パラレル化されたＣＡＤソフトウェアがシリアルアルゴリズムと同様の結果を生成するように、シリアルＣＡＤアルゴリズムと同様な順番でロードされる、請求項２に記載のシステム。
【請求項４】
前記タスクのセットは、前記待ち行列内に保持される独立なアクションの数を最大化するように選択される、請求項２に記載のシステム。
【請求項５】
前記タスクは、任意の順番で実行される、請求項４に記載のシステム。
【請求項６】
前記待ち行列は、前記タスクのセットが実行される前に、該タスクのセットの全てのタスクを用いてロードされる、請求項２に記載のシステム。
【請求項７】
前記待ち行列は、前記タスクのセットが実行されている間に、追加のタスクが提案されることを可能にする強化待ち行列を備える、請求項２に記載のシステム。
【請求項８】
複数のスレッドが、実行されるべきそれぞれのタスクを決定し、該タスクを待ち行列に追加する、請求項２に記載のシステム。
【請求項９】
スレッドが、他のタスクに依存する場合に、タスクを再生する、請求項８に記載のシステム。
【請求項１０】
前記ＣＡＤソフトウェアは、プログラマブルロジックデバイス（ＰＬＤ）内のリソースを配置するための配置アルゴリズムを備える、請求項１に記載のシステム。
【請求項１１】
前記ＣＡＤソフトウェアは、パラレル解析アルゴリズムを備える、請求項１に記載のシステム。
【請求項１２】
コンピュータ支援設計（ＣＡＤ）ソフトウェアをパラレル化するようにコンピュータによって処理するために適合したコンピュータアプリケーションを備える、コンピュータプログラム製品であって、
該コンピュータアプリケーションは、該コンピュータに
独立性を有するタスクのセットを同定することと、
該タスクのセットの各タスクをパラレルに実行されるように割り当てることと、
該タスクのセットの各タスクを実行することと
を行わせるように構成される、コンピュータプログラム製品。
【請求項１３】
前記タスクのセットを用いて前記コンピュータに待ち行列をロードさせる、請求項１２に記載のコンピュータプログラム製品。
【請求項１４】
前記パラレル化されたＣＡＤソフトウェアがシリアルアルゴリズムと同様の結果を生成するように、シリアルＣＡＤアルゴリズムと同様な順番で前記コンピュータに前記待ち行列をロードさせる、請求項１３に記載のコンピュータプログラム製品。
【請求項１５】
前記待ち行列内に保持される独立なアクションの数を最大化するように、前記コンピュータに前記タスクのセットを選択させる、請求項１３に記載のコンピュータプログラム製品。
【請求項１６】
前記コンピュータに、前記タスクを任意の順番で実行させる、請求項１５に記載のコンピュータプログラム製品。
【請求項１７】
前記タスクのセットが実行される前に、該タスクのセットの全てのタスクを用いて前記待ち行列を前記コンピュータにロードさせる、請求項１３に記載のコンピュータプログラム製品。
【請求項１８】
前記タスクのセットが実行されている間に、追加のタスクが提案されることを可能にする強化待ち行列を、前記コンピュータに使用させる、請求項１３に記載のコンピュータプログラム製品。
【請求項１９】
実行されるべきそれぞれのタスクを決定し、該タスクを待ち行列に追加する複数のスレッドを、前記コンピュータに使用させる、請求項１３に記載のコンピュータプログラム製品。
【請求項２０】
他のタスクに依存する場合に、タスクを再生するスレッドを、前記コンピュータに使用させる、請求項１９に記載のコンピュータプログラム製品。
【請求項２１】
プログラマブルロジックデバイス（ＰＬＤ）内のリソースの配置を、前記コンピュータに実行させる、請求項１２に記載のコンピュータプログラム製品。
【請求項２２】
パラレル解析アルゴリズムを、前記コンピュータに実行させる、請求項１２に記載のコンピュータプログラム製品。
【請求項２３】
コンピュータ支援設計（ＣＡＤ）ソフトウェアをパラレル化する方法であって、該方法は、
独立性を有するタスクのセットを同定することと、
該タスクのセットの各タスクをパラレルに実行されるように割り当てることと、
該タスクのセットの各タスクを実行することと
を包含する、方法。
【請求項２４】
前記タスクのセットを用いて待ち行列をロードすることをさらに包含する、請求項２３に記載の方法。
【請求項２５】
前記パラレル化されたＣＡＤソフトウェアがシリアルアルゴリズムと同様な結果を生成するように、シリアルＣＡＤアルゴリズムと同様な順番で待ち行列をロードすることをさらに包含する、請求項２４に記載の方法。
【請求項２６】
前記タスクのセットを、前記待ち行列内に保持される独立なアクションの数を最大化するように選択することをさらに包含する、請求項２４に記載の方法。
【請求項２７】
前記タスクを任意の順番で実行することをさらに包含する、請求項２６に記載の方法。
【請求項２８】
前記タスクのセットが実行される前に、該タスクのセットの全てのタスクを用いて前記待ち行列をロードすることをさらに包含する、請求項２４に記載の方法。
【請求項２９】
前記待ち行列は、前記タスクのセットが実行されている間に、追加のタスクが提案されることを可能にする強化待ち行列を備える、請求項２４に記載の方法。
【請求項３０】
実行されるべきそれぞれのタスクを決定し、前記待ち行列に該タスクを追加する複数のスレッドを使用することをさらに包含する、請求項２４に記載の方法。
【請求項３１】
スレッドが、他のタスクに依存する場合に、タスクを再生する、請求項３０に記載の方法。
【請求項３２】
前記ＣＡＤソフトウェアは、プログラマブルロジックデバイス（ＰＬＤ）内のリソースを配置するための配置アルゴリズムを備える、請求項２３に記載の方法。
【請求項３３】
前記ＣＡＤソフトウェアは、パラレル解析アルゴリズムを備える、請求項２３に記載の方法。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【公開番号】特開２００７−２２０１１４（Ｐ２００７−２２０１１４Ａ）
【公開日】平成１９年８月３０日（２００７．８．３０）
【国際特許分類】
【外国語出願】
【出願番号】特願２００７−３１３７４（Ｐ２００７−３１３７４）
【出願日】平成１９年２月９日（２００７．２．９）
【出願人】（５９７１５４９２２）アルテラ コーポレイション (163)
【氏名又は名称原語表記】Ａｌｔｅｒａ Ｃｏｒｐｏｒａｔｉｏｎ
【Ｆターム（参考）】
【公開日】平成１９年８月３０日（２００７．８．３０）
【国際特許分類】
【出願番号】特願２００７−３１３７４（Ｐ２００７−３１３７４）
【出願日】平成１９年２月９日（２００７．２．９）
【出願人】（５９７１５４９２２）アルテラ コーポレイション (163)
【氏名又は名称原語表記】Ａｌｔｅｒａ Ｃｏｒｐｏｒａｔｉｏｎ
【Ｆターム（参考）】
[ Back to top ]