(57)【特許請求の範囲】
【請求項１】
集積回路（ＩＣ）のコア領域内におけるＩＣコンポーネントの配置を、前記ＩＣの物理設計の際に決定するための焼きなまし法の方法であって、
コンピュータプロセッサが前記ＩＣのネットリストをだんだんと大きな数のビンに分割することを含み、
ネットリストをだんだんと大きな数のビンに前記分割することが、
前記ＩＣコンポーネントを、前記ＩＣの領域を表すビンに分割し、前記ＩＣコンポーネントの現在の配置構成をもたらすこと、
前記ＩＣコンポーネントの焼きなまし法プロセスのための初期温度値を発生させること、
前記初期温度値に等しい反復限度値を割り当てること、
前記現在の配置構成を摂動させ、新しい配置構成をもたらすこと、
前記新しい配置構成を前記現在の配置構成として受容すべきかどうかを決定すること、および、前記決定に基づいて、前記新しい配置構成を前記現在の配置構成として受容または拒絶すること、
前記反復限度値に達したかどうかを、前記ＩＣに対して配置構成を摂動させることの前の反復に基づいて決定すること、
前記反復限度値に達していない場合、前記反復限度値に達するまで、前記現在の配置構成を前記摂動させることと、前記新しい配置構成を受容すべきかどうかを前記決定することとを繰り返すこと、
前記ＩＣコンポーネントを、前のビン数と比較して、総数が指数関数的により大きな、より小さなビンにさらに分割すること、ならびに、
各ビン内のＩＣコンポーネントの数が指定された数より小さくなるまで、焼きなまし法プロセスのための初期温度値を発生させることから開始して、上記を繰り返すこと
を含む、方法。
【請求項２】
初期温度値を前記発生させることが、初期温度値（Ｔ）を式Ｔ＝α×Ｐ＋βにしたがって発生させることを含み、式中、Ｐ＝Ｋ×ｈであり、ｈは現在の分割階層レベルであり、前記現在の分割階層レベルは、前記ＩＣコンポーネントが前にビンに分割された回数に１を加えたものに等しい値を有し、α、βおよびＫは定数値である、請求項１に記載の方法。
【請求項３】
初期温度値を前記発生させることが、初期温度値（Ｔ）を式Ｔ＝α×ｌｏｇＭＮ＋βにしたがって発生させることを含み、式中、Ｎは現在の分割階層レベルでの分割後のビンの数であり、所与の階層レベルは、前記ＩＣコンポーネントが前にビンに分割された回数に１を加えたものに等しい値を有し、Ｍは分割階層レベル１での分割後のビンの数であり、αおよびβは定数値である、請求項１に記載の方法。
【請求項４】
前記定数値αが約−１２であり、前記定数値βが約６４である、請求項３に記載の方法。
【請求項５】
各ビン内のＩＣコンポーネントの前記指定された数が、５から１４である、請求項１に記載の方法。
【請求項６】
前記新しい配置構成を前記現在の配置構成として受容すべきかどうかを前記決定することが、前記新しい配置構成を、前記新しい配置構成により前記ＩＣの評価された配置コストがより低くなる場合、前記現在の配置構成として受容することを含む、請求項１に記載の方法。
【請求項７】
前記現在の配置構成を前記摂動させることが、新しい位置へビンを変位すること、ビンを交換すること、ビンの方向を変更すること、または、新しい位置へ１つもしくは複数のＩＣコンポーネントを変位することのうちの、１つまたは複数を含む、請求項１に記載の方法。
【請求項８】
集積回路（ＩＣ）のコア領域内におけるＩＣコンポーネントの配置を、前記ＩＣの物理設計の際に決定することに関する焼きなまし法のためのシステムであって、
コンピュータプロセッサと、
前記コンピュータプロセッサに動作可能に結合される少なくとも１つのメモリユニットであって、前記少なくとも１つのメモリユニットは、前記焼きなまし法のための初期温度値を発生させる初期温度値発生器を実装するためのコンピュータ実行可能命令を有する、前記少なくとも１つのメモリユニットと
を備え、
前記少なくとも１つのメモリユニットが、
前記焼きなまし法のための初期温度値を発生させるためのコンピュータ実行可能命令、
前記初期温度値に等しい反復限度値を割り当てるためのコンピュータ実行可能命令、
前記反復限度値にしたがって、ビンへの前記ネットリストの現在の分割に関して前記焼きなまし法を実行するためのコンピュータ実行可能命令、
前記ネットリストを、前のビン数と比較して、総数が指数関数的により大きな、より小さなビンにさらに分割するためのコンピュータ実行可能命令、および、
各ビン内のＩＣコンポーネントの数が指定された数より小さくなるまで、前記焼きなまし法のための初期温度値を発生させることから開始して、上記を繰り返すためのコンピュータ実行可能命令を含む、
前記ＩＣのネットリストをだんだんと大きな数のビンに分割するためのコンピュータ実行可能命令をさらに有する、システム。
【請求項９】
初期温度値を発生させるための前記命令が、初期温度値（Ｔ）を式Ｔ＝α×Ｐ＋βにしたがって発生させるための命令を含み、式中、Ｐ＝Ｋ×ｈであり、ｈは現在の分割階層レベルであり、前記現在の分割階層レベルは、前記ネットリストが前にビンに分割された回数に１を加えたものに等しい値を有し、α、βおよびＫは定数値である、請求項８に記載のシステム。
【請求項１０】
初期温度値を発生させるための前記命令が、初期温度値（Ｔ）を式Ｔ＝α×ｌｏｇＭＮ＋βにしたがって発生させるための命令を含み、式中、Ｎは現在の分割階層レベルでの分割後のビンの数であり、所与の階層レベルは、前記ネットリストが前にビンに分割された回数に１を加えたものに等しい値を有し、Ｍは分割階層レベル１での分割後のビンの数であり、αおよびβは定数値である、請求項８に記載のシステム。
【請求項１１】
前記定数値αが約−１２であり、前記定数値βが約６４である、請求項１０に記載のシステム。
【請求項１２】
各ビン内のＩＣコンポーネントの指定された数が、５から１４である、請求項８に記載のシステム。
【請求項１３】
ビンへの前記ネットリストの現在の分割に関して前記焼きなまし法を前記実行するための前記命令が、前記ネットリストのＩＣコンポーネントの新しい配置構成を、前記新しい配置構成により前記ＩＣの評価された配置コストがより低くなる場合、現在の配置構成として受容することを決定するための命令を含む、請求項８に記載のシステム。
【請求項１４】
集積回路（ＩＣ）のコア領域内におけるＩＣコンポーネントの配置を、前記ＩＣの物理設計の際に決定するための焼きなまし法の方法であって、
焼きなまし法プロセスのための初期温度値を発生させることと、
前記焼きなまし法プロセスにおいて、前記ＩＣコンポーネントを、前のビン数と比較して、総数が指数関数的により大きな、より小さなビンに分割することとを含み、
初期温度値を発生させることが、初期温度値（Ｔ）を式Ｔ＝α×ｌｏｇＭＮ＋βにしたがって発生させることを含み、式中、Ｎは現在の分割階層レベルでの分割後のビンの数であり、所与の階層レベルは、前記ＩＣコンポーネントが前にビンに分割された回数に１を加えたものに等しい値を有し、Ｍは分割階層レベル１での分割後のビンの数であり、αおよびβは定数値である、方法。
【発明の詳細な説明】
【背景技術】
【０００１】
物理設計は、ＩＣ（集積回路）またはＶＬＳＩ（超大規模集積回路）の設計プロセスの工程の１つである。マイクロエレクトロニクスのＩＣチップは、間に電気相互接続を有するセルの集合体である。これらのセルは、半導体基板（たとえば、シリコン）上に形成され得る。（本明細書では、サブ回路、回路コンポーネント、またはモジュールとも互換的に呼ばれる）セルは、機能を実行するためにグループ化される、１つまたは複数の回路素子である。各セルは、さらなるセル、サブ回路、コンポーネント、またはモジュールもまた含み得る。
【０００２】
ＩＣの物理設計は、３つのタスク、すなわち、部分化、配置および配線を含み得る。これらのタスクの中で、配置することは本質的な操作であり、チップのコア領域内で、さまざまなサブ回路、セル、および／または回路コンポーネントに対して的確な位置を割り当てる物理設計フローの一部である。
【０００３】
さまざまなコンピュータ自動化設計（ＣＡＤ）ツールが、最適な配置を決定するために利用可能である。これらは、「プレーサ（ｐｌａｃｅｒ）」と呼ばれることが多い。プレーサの一般的な目的は、チップ設計の「コスト」を最小限に抑えるように配置を決定することである。たとえば、総ワイヤ長（ＷＬ）、すなわち、設計でのすべてのワイヤの長さの合計を最小限に抑えることは、大部分の既存のプレーサの主要な目的である。これは、チップサイズ、ひいてはコストを最小限に抑えるのに役立つだけでなく、ワイヤ長に比例する電力および遅延を最小限に抑える。焼きなまし法（ＳＡ）は、ＶＬＳＩの配置問題を解決するために頻繁に適用されている、広く普及している技法である。
【発明の概要】
【発明が解決しようとする課題】
【０００４】
焼きなまし法は、多くの組み合わせ最適化問題を解決するために使用される、確率的、反復的な改善技法である。その名前は、高品質の金属構造を生成するために、溶融した金属を徐々に冷却する焼きなましプロセスに由来したものである。焼きなまし法の配置を実行する場合、初期配置が、さまざまなサブ回路、回路コンポーネントまたはセルを反復して交換および移動することにより改善される。これらの交換および移動は、それらがコストを改善する場合、受け入れられ得る。しかし、回路のサイズが増大し続けるにつれて、この焼きなまし法プロセスは、より良好な配置結果を実現するために、ますます高価な実行時間コストをもたらしている。
【課題を解決するための手段】
【０００５】
集積回路配置用の最適化ベース焼きなまし法のための技法が提供される。いくつかの実施形態では、集積回路（ＩＣ）コンポーネントの配置を、ＩＣのコア領域内で、ＩＣの物理設計の際に決定するための焼きなまし法の方法が、コンピュータプロセッサがＩＣのネットリストをだんだんと大きな数のビンに分割し、その結果、配置の最適化成果（optimizing effort）が、その分割とともに増大することを含む。
【０００６】
いくつかの実施形態では、集積回路（ＩＣ）コンポーネントの配置を、ＩＣのコア領域内で、ＩＣの物理設計の際に決定することに関する焼きなまし法のためのシステムが、コンピュータプロセッサと、コンピュータプロセッサに動作可能に結合される少なくとも１つのメモリユニットとを含む。その少なくとも１つのメモリユニットは、焼きなまし法のための初期温度値を発生させる初期温度値発生器を実装するためのコンピュータ実行可能命令を有し、該焼きなまし法は、ＩＣのネットリストのコンピュータによる分割が増大するにつれて増大する、焼きなまし法の際の配置の最適化成果をもたらす。
【０００７】
いくつかの実施形態では、コンピュータ可読媒体が、集積回路（ＩＣ）コンポーネントの配置を、ＩＣのコア領域内で、ＩＣの物理設計の際に決定するための焼きなまし法のためのコンピュータ実行可能命令を有する。コンピュータ実行可能命令は、焼きなまし法プロセスのための初期温度値を発生させるための命令、および、焼きなまし法プロセスにおいて、ＩＣコンポーネントを、前のビン数と比較して、総数が指数関数的により大きな、より小さなビンに分割するための命令を含み、初期温度値の発生およびＩＣコンポーネントの分割により、配置の最適化成果が、ＩＣコンポーネントの分割が増大するにつれて線形的に増大する。
【０００８】
いくつかの実施形態では、集積回路（ＩＣ）コンポーネントの配置を、ＩＣのコア領域内で、ＩＣの物理設計の際に決定するための焼きなまし法の方法が、焼きなまし法プロセスのための初期温度値を発生させること、および、焼きなまし法プロセスにおいて、ＩＣコンポーネントを、前のビン数と比較して、総数が指数関数的により大きな、より小さなビンに分割することを含む。初期温度値の発生およびＩＣコンポーネントの分割により、配置の最適化成果が、ＩＣコンポーネントの分割が増大するにつれて線形的に増大する。
【０００９】
前述の概要は、単に例示的なものであり、決して限定的であることは意図されていない。上記に記載された例示的な態様、実施形態、および特徴に加えて、さらなる態様、実施形態、および特徴は、図面および以下の詳細な説明を参照して明らかになる。
【図面の簡単な説明】
【００１０】
【図１】ＩＣ配置用のピラミッド型最適化ベース焼きなまし法（pyramid optimization-based simulated annealing）のためのシステムおよび方法を実装するように構成される、例示的なコンピューティング装置を示すブロック図である。
【図２】ＩＣ配置用のピラミッド型最適化ベース焼きなまし法のための例示的なシステムの枠組みの図である。
【図３】ＩＣ配置用のピラミッド型最適化ベース焼きなまし法の状況において、トップダウン階層的手法を使用する、最適化レベルと最適化成果との間の例示的な相関関係を示す図である。
【図４】ＩＣ配置用のピラミッド型最適化ベース焼きなまし法のための例示的なプロセスを示すフローチャートである。
【図５】ＩＣ配置用のピラミッド型最適化ベース焼きなまし法のための例示的な初期温度値発生器のブロック図である。
【図６】ＩＣ配置用のピラミッド型最適化ベース焼きなまし法を使用する、さまざまなレベルでの、焼きなまし法の終了温度とビンの数との間の関係を示すグラフである。
【図７】テスト回路ＩＢＭ０１に関して、ＩＣ配置用のピラミッド型最適化ベース焼きなまし法を使用する、さまざまな階層レベル（すなわち段階）での、終了温度に対する最終的な配置のワイヤ長のサンプルテスト結果を示すグラフである。
【図８】テスト回路ＩＢＭ０７に関して、ＩＣ配置用のピラミッド型最適化ベース焼きなまし法を使用する、さまざまな階層レベル（すなわち段階）での、終了温度に対する最終的な配置のワイヤ長のサンプルテスト結果を示すグラフである。
【図９】ＩＣ配置用のセルベースピラミッド型最適化ベース焼きなまし法を使用する、終了温度に対する最終的な配置のワイヤ長のサンプルテスト結果を示すグラフである。
【発明を実施するための形態】
【００１１】
以下の詳細な説明では、本明細書の一部を形成する添付図面に対して参照が行われる。図面では、文脈で別段に指示しない限り、同様の記号が、通常は同様のコンポーネントを識別する。詳細な説明、図面、および特許請求の範囲に記載される例示的な実施形態は、限定的であるように定められてはいない。ここで提示される主題の趣旨または範囲から逸脱することなく、他の実施形態が利用され得るとともに、他の変更が行われ得る。本明細書に全体的に記載され、図に例示されるような、本開示の態様は、多種多様の異なる構成に関して構成され、置換され、組み合わされ、かつ設計され得るものであり、それらのすべては、明示的に企図され、本開示に関わるものであるということが容易に理解されるであろう。
【００１２】
本開示は、とりわけ、ＩＣ配置用のピラミッド型最適化ベース焼きなまし法に関する方法、機器、コンピュータプログラムおよびシステムについて描写される。
【００１３】
図１を参照すると、ＩＣ配置用のピラミッド型最適化ベース焼きなまし法を実装するように構成される、例示的なコンピューティング装置を示すブロック図が示されている。きわめて基本的な構成では、コンピューティング装置１００は、通常は、１つまたは複数の、プロセッサ１１０およびシステムメモリ１２０を含む。メモリバス１３０は、プロセッサ１１０とシステムメモリ１２０との間の通信のために使用され得る。
【００１４】
所望の構成に応じて、プロセッサ１１０は、マイクロプロセッサ（μＰ）、マイクロコントローラ（μＣ）、デジタル信号プロセッサ（ＤＳＰ）、またはそれらの任意の組み合わせを含むが、それらには限定されない、任意のタイプのものであってよい。プロセッサ１１０は、レベル１キャッシュ１１１およびレベル２キャッシュ１１２など、もう１つのレベルのキャッシング、プロセッサコア１１３、ならびにレジスタ１１４を含み得る。プロセッサコア１１３は、演算論理装置（ＡＬＵ）、浮動小数点ユニット（ＦＰＵ）、デジタル信号処理コア（ＤＳＰコア）、またはそれらの任意の組み合わせを含み得る。メモリコントローラ１１５がさらに、プロセッサ１１０とともに使用され得る、または、いくつかの実装形態では、メモリコントローラ１１５は、プロセッサ１１０の内部の部分であり得る。
【００１５】
所望の構成に応じて、システムメモリ１２０は、（ＲＡＭなど）揮発性メモリ、（ＲＯＭ、フラッシュメモリなど）不揮発性メモリ、またはそれらの任意の組み合わせを含むが、それらには限定されない、任意のタイプのものであってよい。システムメモリ１２０は、通常は、オペレーティングシステム１２１、１つもしくは複数のアプリケーション１２２、ならびにプログラムデータ１２４を含む。アプリケーション１２２は、ＩＣ配置用のピラミッド型最適化ベース焼きなまし法を実行するように構成される、ピラミッド型最適化ベース焼きなまし法アルゴリズム１２３を含む。プログラムデータ１２４は、以下にさらに記載されるように、ＩＣ配置用のピラミッド型最適化ベース焼きなまし法を実行するために有用である、ピラミッド型最適化ベース焼きなまし法データ１２５を含む。いくつかの実施形態では、アプリケーション１２２は、ＩＣコンポーネントの最適な配置が、ＩＣの物理設計プロセスの際に決定され得るように、オペレーティングシステム１２１上で、プログラムデータ１２４を用いて動作するように構成され得る。この記載された基本構成は、破線１０１内のそれらのコンポーネントにより、図１に例示される。
【００１６】
コンピューティング装置１００は、基本構成１０１と、任意の必要な装置およびインターフェースとの間の通信を容易にするための、さらなる特徴もしくは機能、ならびにさらなるインターフェースを有し得る。たとえば、バス／インターフェースコントローラ１４０は、基本構成１０１と、１つまたは複数のデータ記憶装置１５０との間の、ストレージインターフェースバス１４１を介した通信を容易にするために使用され得る。データ記憶装置１５０は、取外し式記憶装置１５１、非取外し式記憶装置１５２、またはそれらの組み合わせであってよい。取外し式記憶装置および非取外し式記憶装置の例には、いくつか挙げると、フレキシブルディスクドライブおよびハードディスクドライブ（ＨＤＤ）など磁気ディスク装置、コンパクトディスク（ＣＤ）ドライブもしくはデジタルバーサタイルディスク（ＤＶＤ）ドライブなど光ディスクドライブ、ソリッドステートドライブ（ＳＳＤ）、ならびにテープドライブがある。例示的なコンピュータ記憶媒体は、コンピュータ可読命令、データ構造体、プログラムモジュール、または他のデータなど情報の記憶のための、任意の方法または技術で実装される、揮発性および不揮発性の、取外し式および非取外し式の媒体を含み得る。
【００１７】
システムメモリ１２０、取外し式ストレージ１５１および非取外し式ストレージ１５２は、すべて、コンピュータ記憶媒体の例である。本明細書では、コンピュータ可読媒体という用語は、コンピュータ記憶媒体を含む。コンピュータ記憶媒体には、ＲＡＭ、ＲＯＭ、ＥＥＰＲＯＭ、フラッシュメモリまたは他のメモリ技術、ＣＤ−ＲＯＭ、デジタルバーサタイルディスク（ＤＶＤ）または他の光ストレージ、磁気カセット、磁気テープ、磁気ディスクストレージまたは他の磁気記憶装置、または、所望の情報を記憶するために使用され得るとともに、コンピューティング装置１００によりアクセスされ得る他の任意の媒体があるが、それらには限定されない。そのような任意のコンピュータ記憶媒体が、装置１００の一部であり得る。
【００１８】
コンピューティング装置１００は、さまざまなインターフェース装置（たとえば、出力インターフェース、周辺インターフェース、および通信インターフェース）から基本構成１０１への、バス／インターフェースコントローラ１４０を介した通信を容易にするためのインターフェースバス１４２をさらに含み得る。例示的な出力装置１６０は、１つまたは複数のＡ／Ｖポート１６３を介して、ディスプレイまたはスピーカなどさまざまな外部装置と通信するように構成され得る、画像処理ユニット１６１および音声処理ユニット１６２を含む。例示的な周辺インターフェース１７０は、１つまたは複数のＩ／Ｏポート１７３を介して、入力装置（たとえば、キーボード、マウス、ペン、音声入力装置、タッチ入力装置など）または他の周辺装置（たとえば、プリンタ、スキャナなど）など外部装置と通信するように構成され得る、シリアルインターフェースコントローラ１７１またはパラレルインターフェースコントローラ１７２を含む。
【００１９】
例示的な通信インターフェース装置１８０は、１つまたは複数の通信ポート１８２を介したネットワーク通信による、および、任意のさまざまな通信媒体を使用する、１つまたは複数の他のコンピューティング装置１９０との通信を容易にするように構成され得るネットワークコントローラ１８１を含む。通信接続は、通信媒体の一例である。通信媒体は、通常は、搬送波など変調データ信号または他の移送メカニズムを含み得るとともに、任意の情報配信媒体を含む。「変調データ信号」は、その特性の１つまたは複数が、信号内の情報を符号化するような方法で設定または変更される信号であり得る。例として、および限定ではなく、通信媒体は、有線ネットワークもしくは直接有線接続など有線媒体、ならびに、音響、無線周波数（ＲＦ）、赤外（ＩＲ）および他のワイヤレス媒体などワイヤレス媒体を含み得る。
【００２０】
コンピューティング装置１００は、携帯電話、携帯情報端末（ＰＤＡ）、パーソナルメディアプレーヤ装置、ワイヤレスウェブウォッチ装置、パーソナルヘッドセット装置、特定用途向け装置、または上記の機能のいずれかを含むハイブリッド装置など、スモールフォームファクタの携帯型の（すなわちモバイルの）電子装置の一部として実装され得る。コンピューティング装置１００はさらに、ラップトップコンピュータおよび非ラップトップコンピュータの両方の構成を含む、パーソナルコンピュータとして実装され得る。
【００２１】
次に図２を参照すると、ＩＣ配置用のピラミッド型最適化ベース焼きなまし法のための例示的なシステムの枠組みの図が示されている。焼きなまし法の配置を実行する場合、初期配置が、さまざまな回路コンポーネントまたはセルの、反復する交換および移動により改善される。これらの交換および移動は、それらが回路設計のコストを改善する場合受容される。
【００２２】
図２では、例示的な入力回路２００とともに、ピラミッド型最適化システム制御２０５が示される。ピラミッド型最適化システム制御２０５は、トップダウン階層的手法を使用し、回路２００を再帰的に二分すること２２０により配置プロセスを開始する。この操作では、所与の回路２００が、二者択一的な水平方向および垂直方向のカットライン２１０に沿って再帰的に分割され、ＩＣのいくつかの指定された矩形領域（すなわち「ビン」）をもたらす。各ビン内の所与の回路２００の部分は、本明細書ではサブ回路、回路コンポーネント、またはセルと呼ばれ、これらの用語は、互換的に使用され得る。それぞれのサブ回路、回路コンポーネント、またはセルは、さらなるセル、サブ回路、コンポーネント、またはモジュールもまた含み得る。
【００２３】
再帰的プロセスでのそれぞれの分割の後で、サブ回路が、それぞれ、特定のビンに割り当てられる。次いで、以下により詳細に記載される、ビンベース焼きなまし法２３０プロセスが、現在のサブ回路配置２１３を改善するために実行される。ビンベース焼きなまし法２３０プロセスでの移動の対象は、ビン内のサブ回路である。この手順は、所定の停止基準が満たされるときに終了する。所定の停止基準は、たとえば、１つのビンあたりのセルの平均数が、所与の数（たとえば７）未満であるときである場合がある。
【００２４】
次いで、調整操作２２０が、現在のビンベース配置をロウ構造２１５に適合させるために実行される。次の操作は、セルベース焼きなまし法２５０である。セルベース焼きなまし法では、サブ回路内の１つ１つのセルが、配置コスト（たとえばワイヤ長）をさらに低減するために、ビンの至る所に移動される。その後、最終的な操作が、詳細配置２１９を取得するために、重複されたセルを拡散させて局所的改善を行う局所的改善２６０である。
【００２５】
次に図３を参照すると、ＩＣ配置用のピラミッド型最適化ベース焼きなまし法の状況（コンテキスト）において、トップダウン階層的手法を使用する、最適化レベルと最適化成果との間の例示的な相関関係を示す図が示されている。ピラミッド型最適化ベース焼きなまし法が、上記で紹介されたような、配置に関するトップダウン階層的手法の状況において使用され得る。所与の階層レベル（たとえば、第１のレベル３０３）では、レイアウト領域が、いくつかのビンに分割される。回路のセルが、コストを低減するために、決まった配置の目的を最小限に抑えるように、いくつかのビンに分配される。たとえば、配置の目的は、最終的な設計の全体のワイヤ長を最小限に抑えることであり得る。セルが特定のビンに分配される場合、それは、回路の最終的なレイアウトにおいて、このビンの領域内に配置されることになる。より微細なレベル（たとえば、第ｈのレベル３０５）に進むと、ビンの数は、ビンの物理的サイズが減少する一方で増大する。したがって、レイアウト上のセルの物理的位置に関する、ますます詳細になる情報が、それぞれの新しいレベルに達するにつれて取得され得る。トップダウン手法は、各ビン内にわずかな数のセルが存在するときに、最後のレベル３０７で終了する。
【００２６】
例として、ＩＣ配置用のピラミッド型最適化ベース焼きなまし法プロセスは、最初に、入力として、「ネットリスト」と呼ばれるものを利用する場合がある。当業者には理解され、一般的に知られているように、ネットリストは、電子的なＩＣ設計の接続性を説明する。これは、たとえば、相互接続されるサブブロックのリストを含む回路説明であり得る。ネットリストは、さまざまな標準的な、および所有権のあるネットリスト言語（たとえば、Ｖｅｒｉｌｏｇ（商標）、ＶＨＤＬ（商標））で記述され得る。本開示では、例示的なネットリストは、スタンダードセル、マクロブロックまたはＩ／Ｏパッドなど多数の回路コンポーネントで構成され得る。
【００２７】
第１のレベル３０３から開始し、階層を下方に、最後のレベル３０７に移動すると、ネットリストは、増大する数のＰ個のビンに分割される。説明の便宜上、第１のレベル３０３では、Ｐ≧２であり、（２、４など）２の累乗である。次いで、Ｐは、各レベルに達するにつれて、指数関数的に増大する。各レベルでは、各ビンが、ネットリストの決まった数の回路コンポーネントを包含し得る。たとえば、第１のレベル３０３では、ネットリストは、４つのビンに分割される。第２のレベルでは、第１のレベルでの各ビンが、別の４つのビンにさらに分割され、それは、第２のレベルでは、総計で１６個のビンが存在することを意味する。これが、最後のレベル３０７に達するまで続く。したがって、現在の例では、第ｈのレベル３０５では、４ｈ個のビンが存在する。具体的な分割方法は、ここに参照によりその全体が組み込まれている、「Ｍｕｌｔｉｌｅｖｅｌ  ｋ−ｗａｙ  Ｈｙｐｅｒ−ｇｒａｐｈ  Ｐａｒｔｉｔｉｏｎｉｎｇ」Ｇ．ＫａｒｙｐｉｓおよびＶ．Ｋｕｍａｒ、２０００年、Ｏｖｅｒｓｅａｓ  Ｐｕｂｌｉｓｈｅｒｓ  Ａｓｓｏｃｉａｔｉｏｎ（ＯＰＡ）  Ｎ．Ｖ．出版に記載される方法など、当業者には理解される任意のマルチレベル法であってよい。第ｈのレベル３０５での分割の後で、本明細書に記載される焼きなまし法プロセスが、ビン上で実行され得る。
【００２８】
焼きなまし法プロセスでは、プロセスの間に徐々に減少される（温度と呼ばれる）グローバルパラメータＴが、一般に存在する。本明細書に記載される焼きなまし法プロセスは、現在の解（すなわち、ＩＣの現在の配置設計）が、Ｔが大きいときは比較的幅広く変化し得るが、Ｔがゼロに向かうにつれて、より低いコストの配置に向かってだんだんと「下り坂」になるように、Ｔによって変わる。したがって、ピラミッド型最適化ベース焼きなまし法プロセスは、レベルｈでの初期温度Ｔｈ（または反復数限度Ｌ）を割り当て、レベルｈでのそれぞれの配置の反復の後で、温度が、それが０に達するまで、１ずつ減少される（すなわち、冷却される）。その後、このプロセスは、それが最後のレベル３０７に達するまで、レベルｈ＋１に移動し続ける。図３で見ることができるように、第ｈのレベルでの（反復限度数Ｌとして利用される）焼きなまし法プロセスの初期温度Ｔは、レベル番号ｈと線形関係にある。すなわち、最適化成果は、最適化レベルと線形関係にある。最適化レベルの数が大きくなるほど、最適化成果が大きくなり、したがって、配置の最適化成果は、分割とともに線形的に増大する。焼きなまし法プロセスは、上記に記載されるようなマルチレベルのトップダウン配置手法に基づく、ピラミッド型最適化ベース焼きなまし法プロセスにより制御され得る。
【００２９】
次に図４を参照すると、ＩＣ配置用のピラミッド型最適化ベース焼きなまし法のための例示的なプロセスを示すフローチャートが示されている。配置フローは、最初に、上記に記載されたように、原始の入力パラメータとして、ＩＣを説明するネットリストを利用する（４０１）。次いで、ネットリストは、Ｐ個の数のビン（たとえば、Ｐ≧２であり、たとえば、２、４など２の累乗であり得る）に分割され（４０２）、現在の配置構成Ｃが発生される。現在の階層レベルで実行される焼きなまし法プロセスの初期温度が、もしあれば、前の階層レベルでのネットリストの前の分割に基づいて、ピラミッド型最適化アルゴリズムにしたがって計算され（４０３）、次いで、結果が、現在の階層レベルに対する反復限度Ｌとして利用される。これは、最初には、以前に分割が行われてない可能性があるということを意味する。しかし、反復プロセスとして、この分割４０３の操作は、後続の階層レベルで、今後の反復において繰り返され（４１５）、その時点では、ピラミッド型最適化アルゴリズムは、前の階層レベルでの前の分割を考慮する。初期温度を計算するときに前の階層レベルでの前の分割を考慮する例示的な式として、図５の初期温度（Ｔ）値発生器５００により使用される（１つまたは複数の）式を参照されたい。その後、現在の配置構成は、新しい配置構成を発生させるための移動によってランダムに摂動される（４０４）。移動は、当業者には理解されるような、新しい位置へのビンの変位、ビンの交換、ビンの方向の変更などの、いずれか１つまたは組み合わせであり得る。移動は、回路コンポーネントレベルでも行われ得る。たとえば、移動は、当業者には理解されるように、１つまたは複数の回路コンポーネントを、決まった範囲内の新しい位置に変位させる場合がある。
【００３０】
次いで、新しい構成Ｃ’が、現在の配置構成Ｃと比較される（４０５）。次いで、どちらの配置構成が、ＩＣ設計に対してより低いコストをもたらすかが決定される（３０６）。新しい構成Ｃ’は、それが現在の構成Ｃと比較してより低い配置コストを有する場合、現在の配置構成として受容され（４０７）、そうでなければ、新しい配置は放棄され、現在の配置は、同じままであり、次の反復のために維持される（４０８）。コストを評価するための方法は、当業者には理解されるような、面積、ワイヤ長、重複、タイミング、電力消費、および混雑度など配置コストコンポーネントの、いずれか１つまたは組み合わせに基づく場合がある。あるいは、システムは、新しい構成Ｃ’を、それがより高い配置コストを有するとしても、確率的に受容する場合がある。
【００３１】
次いで、配置構成を摂動させる上記のプロセスのＬ回の反復が、現在の階層レベルに関して達せられたかどうかが決定される（４０９）。摂動４０４および評価４０５のプロセスが、第ｈのレベルで、ピラミッド型最適化アルゴリズムにしたがって計算される反復の数に達するまで、Ｌ回反復される。Ｌ回の反復に達していない場合、上記のプロセスは、現在の階層レベルで現在の配置構成を摂動させること（４０４）から開始することを繰り返す。Ｌ回の反復に達した場合、現在のレベルが最終的なレベルであるかどうか（すなわち、プロセスが最終的な階層レベルであるかどうか）が決定される（４１０）。
【００３２】
上記に記載されたように、最終的なレベルは、所定の停止基準に基づいて決定され得る。ビンベース焼きなまし法プロセスに関しては、所定の停止基準は、たとえば、１つのビンあたりのセルの平均数が、所与の数（たとえば５から１４）未満であるときである場合がある。プロセスが最終的な階層レベルでないということが決定される場合、プロセスは、次の下方の階層レベルに進み（４１１）、次の階層レベルでの、指数関数的に増大する数の、より小さなビンへの、ネットリストの分割４０２から開始する上記のプロセスを繰り返す。たとえば、焼きなまし法が第ｈのレベルで完了された後で、配置フローは、第（ｈ＋１）のレベルに進む。各ビンは、４つのビンにさらに分割され、それによって、第ｈ＋１のレベルでは、総計で４ｈ＋１個の数のビンを生成する。したがって、現在の分割階層レベルは、コンポーネントが前にビンに分割された回数に１を加えたものに等しい値を有する。たとえば、現在の階層レベルが３である場合、コンポーネントは、それまでに前に２回分割されたということである。プロセスが最終的な階層レベルであるということが決定される場合、各ビンに包含される回路コンポーネントが、前記回路コンポーネントが重複されないように、最終的なレベルで調整される（４１３）場合があり、それによって、最終的な配置が完了される。次いで、ネットリストの最終的な配置が、評価結果を発生させるために、上記で述べられたような、決まった評価方法により評価され得る。
【００３３】
次に図５を参照すると、図４のピラミッド型最適化ベース焼きなまし法プロセスのための例示的な初期温度値発生器のブロック図が示されている。図４の操作４０３で示されるように、初期温度Ｔが計算される。図５は、ピラミッド型最適化ベース焼きなまし法の１つの例示的な実施形態にしたがって、この初期温度を計算するための例示的な発生器を示す。図５に示されるのは、初期温度値発生器５００に対する入力である。入力は、現在のレベル（ｈ）５０３、第１のレベルでのビンの数（Ｍ）５０５、レベルｈでのビンの数（Ｎ）５０７、ならびに３つの定数：α５０９、β５１１およびＫ５１３を含み得る。これらの定数に対する最適な値は、実験によって取得され得る。しかし、例としては、αは約−１２であってよく、βは約６４であってよい。
【００３４】
たとえば、初期温度値発生器５００は、所与のレベルｈに対する初期温度値Ｔ（Ｔｈ）を、以下の式にしたがってＴｈを計算することにより発生させることができる。
Ｔｈ＝α×Ｐ＋β（ただしＰ＝Ｋ×ｈ）
【００３５】
Ｔｈは、後で第ｈのレベルの反復限度数Ｌとして利用される、第ｈのレベルでの焼きなまし法プロセスの初期温度を示し得るものであり、または、代わりに、Ｔｈは、焼きなまし法終了温度５１５を示し得る。レベルｈ＝２、ならびに、定数の−１２のα値、６４のβ値、および１のＫ値で上記の式を使用すると、Ｔ２は４０に等しい。したがって、数４０は、後で第２のレベルの反復限度数Ｌとして利用される、上記の例での第２のレベルでの焼きなまし法プロセスの初期温度を示し得る。
【００３６】
さらなる例として、初期温度値発生器５００は、所与のレベルｈに対する初期温度値Ｔ（Ｔｈ）を、以下の式にしたがってＴｈを計算することにより発生させることができる。
Ｔｈ＝α×ｌｏｇＭＮ＋β
【００３７】
Ｍは第１のレベルでのビンの数を示し、Ｎは第ｈのレベルでのビンの総数を示すので、ｌｏｇＭＮは、各階層レベルでの配置の密度を表す。たとえば、ネットリストが、第１のレベルで４つのビンに分割され、各ビンが、階層の下方の各レベルで別の４つのビンにさらに分割される場合、ＭとＮの両方は、第１のレベルでは４である。その後、Ｎは、第２のレベルでは１６、第３のレベルでは６４などとなる。したがって、ｌｏｇＭＮは、第１のレベルでは１、第２のレベルでは２、第３のレベルでは３などとなる。レベルｈ＝２、ならびに、定数の−１２のα値および６４のβ値で上記の例を考えると、Ｔ２はやはり４０に等しい。したがって、数４０は、後で第２のレベルの反復限度数Ｌとして利用される、上記の例での第２のレベルでの焼きなまし法プロセスの初期温度を示し得る。
【００３８】
次に図６を参照すると、ＩＣ配置用のピラミッド型最適化ベース焼きなまし法を使用する、さまざまなレベルでの、焼きなまし法の終了温度とビンの数との間の関係を示すグラフ６００が示されている。図６は、初期温度が６３に設定されている（それぞれ１６、６４、２５６および１０２４個のビンを有する）各段階での終了温度を示す。終了温度は、反復が、（たとえば）その段階でテスト回路ｉｂｍ０１  ６０３およびｉｂｍ０７  ６０５に対して、もっとも最適なワイヤ長で停止する点である。
【００３９】
上記に記載されたピラミッド型最適化ベース焼きなまし法の実装形態結果は、さまざまな回路ｉｂｍ０１、ｉｍｂ０７、ｉｂｍ０８、ｉｂｍ０９、ｉｂｍ１０およびｉｂｍ１１に関して、４００ＭＨｚの中央演算装置（ＣＰＵ）を有するＳｕｎ（登録商標）Ｕｌｔｒａ１０ワークステーション上で、この方法を組み込む配置ツール（すなわちプレーサ）を実行させ、ＩＢＭ−ＰＬＡＣＥベンチマークを使用することにより取得された。プレーサは、Ｌｅｎｅｘ  ＸＭＬデータファイル／モジュール定義（ＬＥＦ／ＤＥＦ）ファイルを読み込み、配置結果をＤＥＦフォーマットで出力した。Ｃａｄｅｎｃｅ（商標）Ｗａｒｐ  Ｒｏｕｔｅｒが、配置出力を読み込み、配線を実行するために使用される。ベンチマークの特性は、以下の表Ｉに要約されている。
【００４０】
表Ｉ
以下の表には、さまざまな回路ｉｂｍ０１、ｉｍｂ０７、ｉｂｍ０８、ｉｂｍ０９、ｉｂｍ１０およびｉｂｍ１１に対する、セルの数、ネットの数、ロウの数、ロウ利用率、ホワイトスペース比および配線層の数を含む回路の統計値が示されている。
【００４１】
【表１】
0005433086.tif 000002
【００４２】
プレーサは、関連する焼きなまし法アルゴリズムが、より高い階層レベルで、特別な温度で終了する場合、配置ツールＤｒａｇｏｎと比較して、より高い品質の回路配置を生成することができる。たとえば、焼きなまし法アルゴリズムが、第１の段階で、非常に低い温度の代わりに４８℃で終了する場合（Ｄｒａｇｏｎは、各階層レベルで、温度が１より低いときに、焼きなまし法アルゴリズムを終了する）、プレーサは、最終的な配置のワイヤ長を４％だけ低減することができる。
【００４３】
次に図７および８を参照すると、それぞれテスト回路ｉｂｍ０１およびｉｂｍ０７に対してピラミッド型最適化ベース焼きなまし法を使用するプレーサについて、さまざまな階層レベル（すなわち段階）での、終了温度に対する最終的な配置のワイヤ長のサンプルテスト結果を示す２つのグラフ７００、８００が示されている。
【００４４】
図７および８には、初期温度が６３であるそれぞれの段階での最適な終了温度が示されている。たとえば、図７に示される第１の段階７０１では、最短のワイヤ長を伴う最適な終了温度は４８である。すなわち、反復は、６３−４８＝１５回にわたって実行された。図７に示される第２の段階７０３では、最適な終了温度は３３である。すなわち、反復は、６３−３３＝３０回にわたって実行された、などとなる。図８に示される第１の段階８０１では、最短のワイヤ長を伴う最適な終了温度は３３であり、反復は、６３−３３＝３０回にわたって実行された。図８に示される第２の段階８０３では、最適な終了温度は２２であり、反復は、６３−２２＝４１回にわたって実行された、などとなる。図７および８は、それぞれ、テスト回路ｉｂｍ０１およびｉｂｍ０７に対して異なるテストのネットリストを用いた、上記の実験結果を例示し、プレーサが、各レベルで、非常に低い温度で終了する代わりに、異なる階層レベルに対して異なる特別な温度で焼きなまし法プロセスを終了することにより、より高い品質を取得することができるということを示す。
【００４５】
次に図９を参照すると、ＩＣ配置用のセルベースピラミッド型最適化ベース焼きなまし法を使用する、終了温度に対する最終的な配置のワイヤ長のサンプルテスト結果を示すグラフが示されている。グラフ９００は、セルベースピラミッド型最適化アルゴリズムが、テスト回路ｉｂｍ０７  ９０１に関して実行されたときの、終了温度に対するワイヤ長を示す。セルベース焼きなまし法プロセスは、上記に記載されたビンベース配置がロウ構造に調整された後で実行される。セルベース焼きなまし法プロセスは、巨大な計算量のために非常に時間がかかる。図９のグラフ９００は、ｉｂｍ０７  ９０１に対して、セルベース焼きなまし法プロセスでの最良の終了温度９０３がさらに存在することを明示する。配置の実行時間を低減するために、ピラミッド型最適化ベース焼きなまし法アルゴリズムと、セルの焼きなまし法冷却スケジュールとの間の相関関係が調査された。
【００４６】
プレーサは、他の回路に対して、ＩＢＭ−ＰＬＡＣＥベンチマークを使用して、さらにテストされた。実験結果は、以下の表ＩＩに示される。境界ボックスのワイヤ長および配線用の（ｒｏｕｔｅｄ）ワイヤ長は、メートル単位である。実行時間は、分単位である。Ｄｒａｇｏｎと比較すると、ピラミッド型最適化ベースアルゴリズムに基づくプレーサは、Ｄｒａｇｏｎと比較してほぼ半分の配置の実行時間で、同様の、またはわずかにより高いレイアウト品質を生成することができる。
【００４７】
本明細書に記載されるピラミッド型最適化ベース焼きなまし法プロセスに基づく配置ツール（すなわち、「ピラミッド型最適化ベースプレーサ」または「配置ツール」）は、Ｃプログラミング言語で実装され得る。以下のテスト結果は、４００ＭＨｚのＣＰＵを有するＳＵＮ  Ｕｌｔｒａ１０ワークステーション上で、配置ツールを実行させることにより取得された。Ｃａｄｅｎｃｅ（商標）Ｗａｒｐ  Ｒｏｕｔｅｒが、配置出力を読み込み、グローバルかつ最終的な配線を実行するために使用された。以下の表ＩＩは、配置ツールとＤｒａｇｏｎとの間の比較である。各配置は、１度実行されている。Ｄｒａｇｏｎと比較して、配置ツールは、Ｄｒａｇｏｎのほぼ半分の実行時間で、同様の、またはわずかにより高いレイアウト品質を生成した。
【００４８】
【表２】
0005433086.tif 000003
【００４９】
（Ｕｎｉｖｅｒｓｉｔｙ  ｏｆ  Ｃａｌｉｆｏｒｎｉａ  Ｌｏｓ  Ａｎｇｅｌｅｓにより開発された）ＱＰｌａｃｅ配置ツールおよびＣａｐｏ配置ツールに対する比としての、ピラミッド型最適化ベースプレーサおよびＤｒａｇｏｎの、半周長のワイヤ長および配線用のワイヤ長の改善が、それぞれ、表ＩＩＩおよび表ＩＶに要約されている。
【００５０】
【表３】
0005433086.tif 000004
【００５１】
上記の表ＩＩＩに示されるように、Ｄｒａｇｏｎの総実行時間はＱＰｌａｃｅより長いが、Ｄｒａｇｏｎの結果は、より高い品質に相当する。一方、ピラミッド型最適化ベースプレーサもまた、テストされた回路に対して、より高い品質を伴う配置を生成する。換言すると、ピラミッド型最適化ベースプレーサは、より少量の時間を費やしながら、より高い品質を生成することができる。平均して、ＱＰｌａｃｅと比較して、ピラミッド型最適化ベースプレーサは、わずかにより短い総実行時間で、８％のより高いレイアウト品質を生成し、一方で、Ｄｒａｇｏｎは、６６％のより長い実行時間で、７％のより高いレイアウト品質を生成した。
【００５２】
【表４】
0005433086.tif 000005
【００５３】
表ＩＶでは、ピラミッド型最適化ベースプレーサ、ＤｒａｇｏｎおよびＣａｐｏの実行時間は、７３３ＭＨｚのＣＰＵを有するＩｎｔｅｌ／ＰＣに関するものである。Ｃａｐｏと比較して、Ｄｒａｇｏｎおよびピラミッド型最適化ベースプレーサは、配線可能な配置を生成する著しくより高い能力を示す。表ＩＶでは、ｉｂｍ０１、ｉｂｍ０７およびｉｂｍ０８に対して、Ｃａｐｏは、（配線バイオレーションのない）配線可能な配置を生成することができない。回路の残りに対して、ピラミッド型最適化ベースプレーサは、２５％のより短い総実行時間で、配線用のワイヤ長を１２％だけ低減することができる。
【００５４】
前述の詳細な説明では、ブロック図、フローチャート、および／または例の使用によって、装置および／またはプロセスのさまざまな実施形態を説明してきた。そのようなブロック図、フローチャート、および／または例が１つまたは複数の機能および／または操作を含む限りにおいて、そのようなブロック図、フローチャート、または例の中のそれぞれの機能および／または操作は、広範囲のハードウェア、ソフトウェア、ファームウェア、または実質上それらのすべての組み合わせにより、個別におよび／または集合的に実装可能であることが、当業者には理解されるであろう。ある実施形態では、本明細書に記載された主題のいくつかの部分は、特定用途向け集積回路（ＡＳＩＣ）、フィールドプログラマブルゲートアレイ（ＦＰＧＡ）、デジタル信号プロセッサ（ＤＳＰ）、または他の集積化方式によって実装することができる。しかし、本明細書で開示された実施形態のいくつかの態様が、全体においてまたは一部において、１つまたは複数のコンピュータ上で動作する１つまたは複数のコンピュータプログラムとして（たとえば、１つまたは複数のコンピュータシステム上で動作する１つまたは複数のプログラムとして）、１つまたは複数のプロセッサ上で動作する１つまたは複数のプログラムとして（たとえば、１つまたは複数のマイクロプロセッサ上で動作する１つまたは複数のプログラムとして）、ファームウェアとして、あるいは実質上それらの任意の組み合わせとして、等価に集積回路に実装することができることを、当業者は認識するであろうし、電気回路の設計ならびに／またはソフトウェアおよびもしくはファームウェアに対するコードの記述が、本開示に照らして十分当業者の技能の範囲内であることを、当業者は認識するであろう。さらに、本明細書に記載された主題のメカニズムをさまざまな形式のプログラム製品として配布することができることを、当業者は理解するであろうし、本明細書に記載された主題の例示的な実施形態が、実際に配布を実行するために使用される信号伝達媒体の特定のタイプにかかわらず適用されることを、当業者は理解するであろう。信号伝達媒体の例には、フロッピーディスク、ハードディスクドライブ、コンパクトディスク（ＣＤ）、デジタルビデオディスク（ＤＶＤ）、デジタルテープ、コンピュータメモリ、など記録可能なタイプの媒体、ならびに、デジタル通信媒体および／またはアナログ通信媒体（たとえば、光ファイバケーブル、導波管、有線通信リンク、無線通信リンクなど）など通信タイプの媒体が含まれるが、それらには限定されない。
【００５５】
システムの側面でのハードウェアの実装形態とソフトウェアの実装形態との間には、ほとんど相違が残されていない。ハードウェアまたはソフトウェアの使用は、一般に（いつもそうではないが、ある状況ではハードウェアとソフトウェアの間の選択が重要になり得るという点で）コスト対効果のトレードオフを表す設計上の選択である。本明細書に記載された、プロセスおよび／またはシステムおよび／または他の技術をもたらすことができるさまざまな達成手段があり（たとえば、ハードウェア、ソフトウェア、および／またはファームウェア）、好ましい達成手段は、プロセスおよび／またはシステムおよび／または他の技術が導入される状況によって異なる。たとえば、実装者が速度と正確性が最も重要であると決定すると、実装者は主にハードウェアおよび／またはファームウェアの達成手段を選択することができる。フレキシビリティが最も重要なら、実装者は主にソフトウェアの実装形態を選択することができる。または、さらに別の代替案として、実装者は、ハードウェア、ソフトウェア、および／またはファームウェアのなんらかの組み合わせを選択することができる。
【００５６】
本明細書で説明したやり方で装置および／またはプロセスを記載し、その後そのように記載された装置および／またはプロセスを、データ処理システムに統合するためにエンジニアリング方式を使用することは、当技術分野で一般的であることを当業者は認識するであろう。すなわち、本明細書に記載された装置および／またはプロセスの少なくとも一部を、妥当な数の実験によってデータ処理システムに統合することができる。通常のデータ処理システムは、一般に、システムユニットハウジング、ビデオディスプレイ装置、揮発性メモリおよび不揮発性メモリなどのメモリ、マイクロプロセッサおよびデジタル信号プロセッサなどのプロセッサ、オペレーティングシステムなどの計算実体、ドライバ、グラフィカルユーザインターフェース、およびアプリケーションプログラムのうちの１つもしくは複数、タッチパッドもしくはスクリーンなどの１つもしくは複数の相互作用装置、ならびに／またはフィードバックループおよびコントロールモータを含むコントロールシステム（たとえば、位置検知用および／もしくは速度検知用フィードバック、コンポーネントの移動用および／もしくは数量の調整用コントロールモータ）を含むことを、当業者は理解するであろう。通常のデータ処理システムは、データコンピューティング／通信システムおよび／またはネットワークコンピューティング／通信システムの中に通常見られるコンポーネントなどの、市販の適切なコンポーネントを利用して実装することができる。
【００５７】
本明細書に記載された主題は、さまざまなコンポーネントをしばしば例示しており、これらのコンポーネントは、他のさまざまなコンポーネントに包含されるか、または他のさまざまなコンポーネントに接続される。そのように図示されたアーキテクチャは、単に例示にすぎず、実際には、同じ機能を実現する多くの他のアーキテクチャが実装可能であることが理解されよう。概念的な意味で、同じ機能を実現するコンポーネントの任意の構成は、所望の機能が実現されるように効果的に「関連付け」される。したがって、特定の機能を実現するために組み合わされた、本明細書における任意の２つのコンポーネントは、アーキテクチャまたは中間のコンポーネントにかかわらず、所望の機能が実現されるように、お互いに「関連付け」されていると見ることができる。同様に、そのように関連付けされた任意の２つのコンポーネントは、所望の機能を実現するために、互いに「動作可能に接続」または「動作可能に結合」されていると見なすこともでき、そのように関連付け可能な任意の２つのコンポーネントは、所望の機能を実現するために、互いに「動作可能に結合できる」と見なすこともできる。動作可能に結合できる場合の具体例には、物理的にかみ合わせ可能な、および／もしくは物理的に相互作用するコンポーネント、ならびに／またはワイヤレスに相互作用可能な、および／もしくはワイヤレスに相互作用するコンポーネント、ならびに／または論理的に相互作用する、および／もしくは論理的に相互作用可能なコンポーネントが含まれるが、それらに限定されない。
【００５８】
本明細書における実質的にすべての複数形および／または単数形の用語の使用に対して、当業者は、状況および／または用途に適切なように、複数形から単数形に、および／または単数形から複数形に変換することができる。さまざまな単数形／複数形の置き換えは、理解しやすいように、本明細書で明確に説明することができる。
【００５９】
通常、本明細書において、特に添付の特許請求の範囲（たとえば、添付の特許請求の範囲の本体部）において使用される用語は、全体を通じて「オープンな（ｏｐｅｎ）」用語として意図されていることが、当業者には理解されよう（たとえば、用語「含む（ｉｎｃｌｕｄｉｎｇ）」は、「含むがそれに限定されない（ｉｎｃｌｕｄｉｎｇ  ｂｕｔ  ｎｏｔ  ｌｉｍｉｔｅｄ  ｔｏ）」と解釈されるべきであり、用語「有する（ｈａｖｉｎｇ）」は、「少なくとも有する（ｈａｖｉｎｇ  ａｔ  ｌｅａｓｔ）」と解釈されるべきであり、用語「含む（ｉｎｃｌｕｄｅｓ）」は、「含むがそれに限定されない（ｉｎｃｌｕｄｅｓ  ｂｕｔ  ｉｓ  ｎｏｔ  ｌｉｍｉｔｅｄ  ｔｏ）」と解釈されるべきである、など）。導入される請求項で具体的な数の記載が意図される場合、そのような意図は、当該請求項において明示的に記載されることになり、そのような記載がない場合、そのような意図は存在しないことが、当業者にはさらに理解されよう。たとえば、理解の一助として、添付の特許請求の範囲は、導入句「少なくとも１つの（ａｔ  ｌｅａｓｔ  ｏｎｅ）」および「１つまたは複数の（ｏｎｅ  ｏｒ  ｍｏｒｅ）」を使用して請求項の記載を導くことを含む場合がある。しかし、そのような句の使用は、同一の請求項が、導入句「１つまたは複数の」または「少なくとも１つの」および「ａ」または「ａｎ」などの不定冠詞を含む場合であっても、不定冠詞「ａ」または「ａｎ」による請求項の記載の導入が、そのように導入される請求項の記載を含む任意の特定の請求項を、単に１つのそのような記載を含む開示に限定する、ということを示唆していると解釈されるべきではない（たとえば、「ａ」および／または「ａｎ」は、通常、「少なくとも１つの」または「１つまたは複数の」を意味すると解釈されるべきである）。同じことが、請求項の記載を導入するのに使用される定冠詞の使用にも当てはまる。また、導入される請求項の記載で具体的な数が明示的に記載されている場合でも、そのような記載は、通常、少なくとも記載された数を意味すると解釈されるべきであることが、当業者には理解されよう（たとえば、他の修飾語なしでの「２つの記載（ｔｗｏ  ｒｅｃｉｔａｔｉｏｎｓ）」の単なる記載は、通常、少なくとも２つの記載、または２つ以上の記載を意味する）。「Ａ、ＢまたはＣ、などの少なくとも１つ」に類似の慣例表現が使用されている事例では、通常、そのような構文は、当業者がその慣例表現を理解するであろう意味で意図されている（たとえば、「Ａ、Ｂ、またはＣの少なくとも１つを有するシステム」は、Ａのみ、Ｂのみ、Ｃのみ、ＡおよびＢを共に、ＡおよびＣを共に、ＢおよびＣを共に、ならびに／またはＡ、Ｂ、およびＣを共に、などを有するシステムを含むが、それに限定されない）。２つ以上の代替用語を提示する事実上いかなる離接する語および／または句も、明細書、特許請求の範囲、または図面のどこにあっても、当該用語の一方（ｏｎｅ  ｏｆ  ｔｈｅ  ｔｅｒｍｓ）、当該用語のいずれか（ｅｉｔｈｅｒ  ｏｆ  ｔｈｅ  ｔｅｒｍｓ）、または両方の用語（ｂｏｔｈ  ｔｅｒｍｓ）を含む可能性を企図すると理解されるべきであることが、当業者にはさらに理解されよう。たとえば��句「ＡまたはＢ」は、「Ａ」または「Ｂ」あるいは「ＡおよびＢ」の可能性を含むことが理解されよう。
【００６０】
さまざまな態様および実施形態が、本明細書で開示されたが、他の態様および実施形態が、当業者には明らかであろう。本明細書で開示されたさまざまな態様および実施形態は、例示を目的としたものであり、限定的であることは意図されておらず、真の範囲および趣旨は、以下の特許請求の範囲により指示されている。
【図１】
0005433086.tif 000006
【図２】
0005433086.tif 000007
【図３】
0005433086.tif 000008
【図４】
0005433086.tif 000009
【図５】
0005433086.tif 000010
【図６】
0005433086.tif 000011
【図７】
0005433086.tif 000012
【図８】
0005433086.tif 000013
【図９】
0005433086.tif 000014