(57)【要約】【課題】  ルーティング制御情報にしたがって、データを第１数の入力チャネルの任意のものから、第２数の出力チャネルの任意のものへルーティングするよう動作可能なクロスバーに関する方法および装置を提供する。【解決手段】  ルーティング制御情報にしたがって、データを第１数の入力チャネルの任意のものから、第２数の出力チャネルの任意のものへルーティングするよう動作可能なクロスバーに関する方法および装置を提供する。入力チャネルおよび出力チャネルのそれぞれの組み合わせは、複数のリンクのうちの１つに対応する。このクロスバー回路は、データを決定的な方法でルーティングするよう動作可能であり、それによりルーティング制御情報によって表された部分的順序付けを維持できる。異なるリンク上のイベントは非相関である。
2005516508.tif 000002
【特許請求の範囲】
【請求項１】
ルーティング制御情報に基づいて第１数の入力チャネルのうちの任意のものから、第２数の出力チャネルのうちの任意のものへデータをルーティングするよう動作可能なクロスバーであって、入力チャネルおよび出力チャネルのそれぞれの組み合わせは、複数のリンクのうちの１つを含み、前記クロスバーは、前記リンクのうちのそれぞれ上で前記データを決定的にルーティングし、それにより前記ルーティング制御情報によって表現された部分的順序付けを維持するよう動作可能なクロスバー回路を含み、異なるリンク上のイベントは非相関であるクロスバー。
【請求項２】
請求項１に記載のクロスバーであって、前記ルーティング制御情報は、独立したスプリット制御およびマージ制御チャネル上で前記クロスバーに送られるスプリット制御情報およびマージ制御情報を含み、前記クロスバー回路は、前記出力アドレスを前記入力アドレスに対応する前記スプリット制御チャネル上で、前記入力アドレスを前記出力アドレスに対応する前記マージ制御チャネル上で送ることによって前記部分的順序付けを維持するよう動作可能であるクロスバー。
【請求項３】
請求項１に記載のクロスバーであって、前記クロスバー回路は、
それぞれ前記入力チャネルのうちの１つに対応する前記第１数のスプリットバス、
それぞれ前記出力チャネルのうちの１つに対応する前記第２数のマージバス、および
前記スプリットバスのそれぞれを前記マージバスのそれぞれに接続する複数の中間チャネル
を含むクロスバー。
【請求項４】
請求項３に記載のクロスバーであって、それぞれのスプリットバスは、前記データを前記対応する入力チャネルから受け取る第１スプリット回路、およびそれぞれのスプリットセルが前記マージバスのうちの１つに対応する複数のスプリットセルを含むクロスバー。
【請求項５】
請求項３に記載のクロスバーであって、それぞれのマージバスは、前記データを前記対応する出力チャネルに送る第１マージ回路、およびそれぞれのマージセルが前記スプリットバスのうちの１つに対応する複数のマージセルを含むクロスバー。
【請求項６】
請求項３に記載のクロスバーであって、前記クロスバー回路は、前記データについてＭ個の1ofNエンコーディングを用い、ここでＭは１以上の整数であり、Ｎは２以上の整数であるクロスバー。
【請求項７】
請求項３に記載のクロスバーであって、前記クロスバー回路は、前記ルーティング制御情報について1ofNエンコーディングを用い、ここでＮは２以上の整数であるクロスバー。
【請求項８】
請求項３に記載のクロスバーであって、前記ルーティング制御情報は、スプリット制御情報およびマージ制御情報を含み、前記スプリット制御情報は、1ofAおよび1ofBエンコーディングを用いてエンコーディングされ、ここでＡ＊Ｂは前記第２数であり、前記マージ制御情報は、1ofCおよび1ofDエンコーディングを用いてエンコーディングされ、ここでＣ＊Ｄは前記第１数であるクロスバー。
【請求項９】
請求項３に記載のクロスバーであって、前記クロスバー回路は、前記データを少なくとも１つの前記リンク上で非同期で転送するよう動作可能であるクロスバー。
【請求項１０】
請求項９に記載のクロスバーであって、前記クロスバー回路は、前記データを少なくとも１つの前記リンク上でハンドシェークプロトコルを用いて転送するよう動作可能であるクロスバー。
【請求項１１】
請求項１０に記載のクロスバーであって、前記リンクのうちの前記少なくとも１つの上での第１センダーおよび第１レシーバ間の前記ハンドシェークプロトコルは、
前記第１レシーバからのイネーブル信号がハイになるとき、前記第１センダーがデータ信号を有効にセットし、
前記第１レシーバは、前記有効なデータ信号を受け取ると前記イネーブル信号を下げ、
前記第１センダーは、前記低イネーブル信号を受け取ると前記データ信号をニュートラルにセットし、
前記第１レシーバは、前記ニュートラルデータ信号を受け取ると前記イネーブル信号を上げる
クロスバー。
【請求項１２】
請求項１０に記載のクロスバーであって、前記ハンドシェークプロトコルは、遅延非敏感であるクロスバー。
【請求項１３】
請求項３に記載のクロスバーであって、前記クロスバー回路は、少なくとも１つのタイミング推定に基づいて、前記リンクのうちの少なくとも１つの上で前記データを転送するよう動作可能であるクロスバー。
【請求項１４】
請求項１３に記載のクロスバーであって、前記少なくとも１つのタイミング推定は、パルスタイミング推定、干渉タイミング推定、および黙示のデータニュートラル性タイミング推定のうちの任意のものを含むクロスバー。
【請求項１５】
請求項１４に記載のクロスバーであって、前記パルスタイミング推定は、そうでなければ遅延非敏感な４フェーズハンドシェークに適用されるクロスバー。
【請求項１６】
請求項１４に記載のクロスバーであって、前記黙示のデータニュートラル性タイミング推定は、そうでなければ遅延非敏感な４フェーズハンドシェークに適用されるクロスバー。
【請求項１７】
請求項１４に記載のクロスバーであって、前記干渉タイミング推定は、干渉するオペレータ間の適切なタイミングマージンを推定するクロスバー。
【請求項１８】
請求項３に記載のクロスバーであって、前記クロスバー回路は、クロック信号の遷移を参照して前記リンクのうちの少なくとも１つの上で前記データを転送するよう動作可能なクロスバー。
【請求項１９】
請求項１８に記載のクロスバーであって、そうでなければ非同期ハンドシェークプロトコルに関連付けられたイベントは、前記クロック信号の前記遷移にアラインされるクロスバー。
【請求項２０】
請求項３に記載のクロスバーであって、前記ルーティング制御情報が前記リンクのうちの特定のものに対応するときを示すよう動作可能なヒット回路をさらに備えるクロスバー。
【請求項２１】
請求項２０に記載のクロスバーであって、前記ヒット回路は、前記特定のリンクに対応する前記ルーティング制御情報の前記ニュートラル性をチェックするよう動作可能な対称ヒット回路を備えるクロスバー。
【請求項２２】
請求項２１に記載のクロスバーであって、前記対称ヒット回路は、４入力コンセンサス要素を含むクロスバー。
【請求項２３】
請求項２０に記載のクロスバーであって、前記ヒット回路は、前記特定のリンクに対応する前記ルーティング制御情報の前記ニュートラル性をチェックするよう動作可能ではない対称ヒット回路を備えるクロスバー。
【請求項２４】
請求項３に記載のクロスバーであって、前記クロスバー回路は、前記複数のリンクのうちの第１リンクの上で前記データの複数のユニットを連続的にルーティングするよう動作可能であるクロスバー。
【請求項２５】
請求項２４に記載のクロスバーであって、前記データの前記複数のユニットは、最終的なデータユニットを含み、前記クロスバー回路は、前記最終データユニットが特定されるまで前記複数のデータユニットをルーティングするよう動作可能であるクロスバー。
【請求項２６】
請求項２５に記載のクロスバーであって、前記最終データユニットは、前記複数のデータユニットに関連付けられたカウントを参照して特定されるクロスバー。
【請求項２７】
請求項２６に記載のクロスバーであって、前記カウントは、全てのデータ転送について固定されるクロスバー。
【請求項２８】
請求項２６に記載のクロスバーであって、前記カウントは、前記複数のデータユニットを参照して可変であるクロスバー。
【請求項２９】
請求項２５に記載のクロスバーであって、前記最終データユニットは、前記複数のデータユニットに関連付けられたデータフィールドを用いて特定されるクロスバー。
【請求項３０】
請求項２９に記載のクロスバーであって、前記データフィールドは、テールビットおよび終端キャラクタのうちの１つを備えるクロスバー。
【請求項３１】
請求項２５に記載のクロスバーであって、前記最終データユニットは、前記ルーティング制御情報に関連付けられたデータフィールドを用いて特定されるクロスバー。
【請求項３２】
請求項３に記載のクロスバーであって、前記クロスバー回路は、前記データを前記入力チャネルから前記出力チャネルへ前記決定的な方法で転送するよう全体として動作可能な複数の個別クロスバー回路を備えるクロスバー。
【請求項３３】
請求項１に記載のクロスバーであって、前記クロスバー回路は、前記データを対応する入力チャネルから受け取るようそれぞれ動作可能な前記第１数のスプリット回路、前記データを対応する出力チャネルへ送るようそれぞれ動作可能な前記第２数のマージ回路、および前記データを前記スプリット回路のうちの対応する１つから前記マージ回路のうちの対応する１つへ中間チャネルなしで直接に転送するようそれぞれ動作可能な複数のルータセルを備えるクロスバー。
【請求項３４】
請求項３３に記載のクロスバーであって、スプリットおよびマージ回路の少なくとも１つのペアは、それらの間に中間チャネルを有するクロスバー。
【請求項３５】
請求項３４に記載のクロスバーであって、前記中間チャネルは、バッファリングを含むクロスバー。
【請求項３６】
請求項３３に記載のクロスバーであって、前記クロスバー回路は、前記データについてＭ個の1ofNエンコーディングを用い、ここでＭは１以上の整数であり、Ｎは２以上の整数であるクロスバー。
【請求項３７】
請求項３３に記載のクロスバーであって、前記クロスバー回路は、前記ルーティング制御情報について1ofNエンコーディングを用い、ここでＮは２以上の整数であるクロスバー。
【請求項３８】
請求項３３に記載のクロスバーであって、前記ルーティング制御情報は、スプリット制御情報およびマージ制御情報を含み、前記スプリット制御情報は、1ofAおよび1ofBエンコーディングを用いてエンコーディングされ、ここでＡ＊Ｂは前記第２数であり、前記マージ制御情報は、1ofCおよび1ofDエンコーディングを用いてエンコーディングされ、ここでＣ＊Ｄは前記第１数であるクロスバー。
【請求項３９】
請求項３３に記載のクロスバーであって、前記クロスバー回路は、前記データを少なくとも１つの前記リンク上で非同期で転送するよう動作可能であるクロスバー。
【請求項４０】
請求項３９に記載のクロスバーであって、前記クロスバー回路は、前記データを少なくとも１つの前記リンク上でハンドシェークプロトコルを用いて転送するよう動作可能であるクロスバー。
【請求項４１】
請求項４０に記載のクロスバーであって、前記リンクのうちの前記少なくとも１つの上での第１センダーおよび第１レシーバ間の前記ハンドシェークプロトコルは、
前記第１レシーバからのイネーブル信号がハイになるとき、前記第１センダーがデータ信号を有効にセットし、
前記第１レシーバは、前記有効なデータ信号を受け取ると前記イネーブル信号を下げ、
前記第１センダーは、前記低イネーブル信号を受け取ると前記データ信号をニュートラルにセットし、
前記第１レシーバは、前記ニュートラルデータ信号を受け取ると前記イネーブル信号を上げる
クロスバー。
【請求項４２】
請求項４０に記載のクロスバーであって、前記ハンドシェークプロトコルは、遅延非敏感であるクロスバー。
【請求項４３】
請求項３３に記載のクロスバーであって、前記クロスバー回路は、少なくとも１つのタイミング推定に基づいて、前記リンクのうちの少なくとも１つの上で前記データを転送するよう動作可能であるクロスバー。
【請求項４４】
請求項４３に記載のクロスバーであって、前記少なくとも１つのタイミング推定は、パルスタイミング推定、干渉タイミング推定、および黙示のデータニュートラル性タイミング推定のうちの任意のものを含むクロスバー。
【請求項４５】
請求項４４に記載のクロスバーであって、前記パルスタイミング推定は、そうでなければ遅延非敏感な４フェーズハンドシェークに適用されるクロスバー。
【請求項４６】
請求項４４に記載のクロスバーであって、前記黙示のデータニュートラル性タイミング推定は、そうでなければ遅延非敏感な４フェーズハンドシェークに適用されるクロスバー。
【請求項４７】
請求項４４に記載のクロスバーであって、前記干渉タイミング推定は、干渉するオペレータ間の適切なタイミングマージンを推定するクロスバー。
【請求項４８】
請求項３３に記載のクロスバーであって、前記クロスバー回路は、クロック信号の遷移を参照して前記リンクのうちの少なくとも１つの上で前記データを転送するよう動作可能なクロスバー。
【請求項４９】
請求項４８に記載のクロスバーであって、そうでなければ非同期ハンドシェークプロトコルに関連付けられたイベントは、前記クロック信号の前記遷移にアラインされるクロスバー。
【請求項５０】
請求項３３に記載のクロスバーであって、前記ルーティング制御情報が前記リンクのうちの特定のものに対応するときを示すよう動作可能なヒット回路をさらに備えるクロスバー。
【請求項５１】
請求項５０に記載のクロスバーであって、前記ヒット回路は、前記特定のリンクに対応する前記ルーティング制御情報の前記ニュートラル性をチェックするよう動作可能な対称ヒット回路を備えるクロスバー。
【請求項５２】
請求項５１に記載のクロスバーであって、前記対称ヒット回路は、４入力コンセンサス要素を含むクロスバー。
【請求項５３】
請求項５０に記載のクロスバーであって、前記ヒット回路は、前記特定のリンクに対応する前記ルーティング制御情報の前記ニュートラル性をチェックするよう動作可能ではない対称ヒット回路を備えるクロスバー。
【請求項５４】
請求項３３に記載のクロスバーであって、前記クロスバー回路は、前記複数のリンクのうちの第１リンクの上で前記データの複数のユニットを連続的にルーティングするよう動作可能であるクロスバー。
【請求項５５】
請求項５４に記載のクロスバーであって、前記データの前記複数のユニットは、最終的なデータユニットを含み、前記クロスバー回路は、前記最終データユニットが特定されるまで前記複数のデータユニットをルーティングするよう動作可能であるクロスバー。
【請求項５６】
請求項５５に記載のクロスバーであって、前記最終データユニットは、前記複数のデータユニットに関連付けられたカウントを参照して特定されるクロスバー。
【請求項５７】
請求項５６に記載のクロスバーであって、前記カウントは、全てのデータ転送について固定されるクロスバー。
【請求項５８】
請求項５６に記載のクロスバーであって、前記カウントは、前記複数のデータユニットを参照して可変であるクロスバー。
【請求項５９】
請求項５５に記載のクロスバーであって、前記最終データユニットは、前記複数のデータユニットに関連付けられたデータフィールドを用いて特定されるクロスバー。
【請求項６０】
請求項５９に記載のクロスバーであって、前記データフィールドは、テールビットおよび終端キャラクタのうちの１つを備えるクロスバー。
【請求項６１】
請求項５５に記載のクロスバーであって、前記最終データユニットは、前記ルーティング制御情報に関連付けられたデータフィールドを用いて特定されるクロスバー。
【請求項６２】
請求項３３に記載のクロスバーであって、前記クロスバー回路は、前記データを前記入力チャネルから前記出力チャネルへ前記決定的な方法で転送するよう全体として動作可能な複数の個別クロスバー回路を備えるクロスバー。
【請求項６３】
請求項１に記載のクロスバーであって、前記第１数はＰを含み、ここでＰは１以上の第１整数であり、前記第２数はＱを含み、ここでＱは１以上の第２整数であり、ＰおよびＱの両方が１に等しいのではないクロスバー。
【請求項６４】
請求項１に記載の前記クロスバーを備える集積回路。
【請求項６５】
請求項６４に記載の集積回路であって、前記集積回路は、ＣＭＯＳ集積回路、ＧａＡｓ集積回路、およびＳｉＧｅ集積回路のうちのいずれかを備える集積回路。
【請求項６６】
請求項６４に記載の集積回路であって、前記集積回路は、少なくとも１つのプログラマブルロジックデバイス、フィールドプログラマブルゲートアレイ、特定用途向け集積回路、マイクロプロセッサ、システムオンチップ、パケットスイッチングデバイス、およびシェアドメモリブリッジのうちのいずれかを備える集積回路。
【請求項６７】
請求項１に記載のクロスバーを表すデータ構造をその上に記憶する少なくとも１つのコンピュータで読み取り可能な媒体。
【請求項６８】
請求項６７に記載の少なくとも１つのコンピュータで読み取り可能な媒体であって、前記データ構造は、前記クロスバーのシミュレーション可能な表現を備える少なくとも１つのコンピュータで読み取り可能な媒体。
【請求項６９】
請求項６８に記載の少なくとも１つのコンピュータで読み取り可能な媒体であって、前記シミュレーション可能な表現はネットリストを備える少なくとも１つのコンピュータで読み取り可能な媒体。
【請求項７０】
請求項６７に記載の少なくとも１つのコンピュータで読み取り可能な媒体であって、前記データ構造は、前記クロスバーのコード記述を備える少なくとも１つのコンピュータで読み取り可能な媒体。
【請求項７１】
請求項７０に記載の少なくとも１つのコンピュータで読み取り可能な媒体であって、前記コード記述はハードウェア記述言語に対応する少なくとも１つのコンピュータで読み取り可能な媒体。
【請求項７２】
請求項１に記載のクロスバーの少なくとも一部を表す半導体処理マスクのセット。
【請求項７３】
請求項１に記載のクロスバーであって、前記クロスバー回路は、イベントドリブンプロトコルにしたがって前記リンク上で前記データをルーティングするよう動作可能であるクロスバー。
【請求項７４】
請求項７３に記載のクロスバーであって、前記イベントドリブンプロトコルは非同期であるクロスバー。
【請求項７５】
請求項７３に記載のクロスバーであって、前記イベントドリブンプロトコルに関連付けられたイベントは、グローバルタイミングレファレンスの遷移にアラインされるクロスバー。
【請求項７６】
命令ルーティング情報に基づいて第１数の入力チャネル上で受け取られた順序付けられた命令のストリームを、第２数の出力チャネルのうちの指定されたものへルーティングするよう動作可能なディスパッチャであって、前記ディスパッチャは、前記命令をそれぞれの出力チャネルへ決定的にルーティングし、それにより前記順序付けられたストリーム内で規定されたそれぞれの出力チャネルについての部分的順序付けを維持するよう動作可能であるディスパッチ回路を備え、異なる出力チャネル上の命令は非相関であるディスパッチャ。
【請求項７７】
請求項７６に記載のディスパッチャであって、前記クロスバー回路は、前記データについてＭ個の1ofNエンコーディングを用い、ここでＭは１以上の整数であり、Ｎは２以上の整数であるディスパッチャ。
【請求項７８】
請求項７６に記載のディスパッチャであって、前記クロスバー回路は、前記ルーティング制御情報について1ofNエンコーディングを用い、ここでＮは２以上の整数であるディスパッチャ。
【請求項７９】
請求項７６に記載のディスパッチャであって、前記ルーティング制御情報は、スプリット制御情報およびマージ制御情報を含み、前記スプリット制御情報は、1ofAおよび1ofBエンコーディングを用いてエンコーディングされ、ここでＡ＊Ｂは前記第２数であり、前記マージ制御情報は、1ofCおよび1ofDエンコーディングを用いてエンコーディングされ、ここでＣ＊Ｄは前記第１数であるディスパッチャ。
【請求項８０】
請求項７６に記載のディスパッチャであって、前記クロスバー回路は、前記データを少なくとも１つの前記リンク上で非同期で転送するよう動作可能であるディスパッチャ。
【請求項８１】
請求項８０に記載のディスパッチャであって、前記クロスバー回路は、前記データを少なくとも１つの前記リンク上でハンドシェークプロトコルを用いて転送するよう動作可能であるディスパッチャ。
【請求項８２】
請求項８１に記載のディスパッチャであって、前記リンクのうちの前記少なくとも１つの上での第１センダーおよび第１レシーバ間の前記ハンドシェークプロトコルは、
前記第１レシーバからのイネーブル信号がハイになるとき、前記第１センダーがデータ信号を有効にセットし、
前記第１レシーバは、前記有効なデータ信号を受け取ると前記イネーブル信号を下げ、
前記第１センダーは、前記低イネーブル信号を受け取ると前記データ信号をニュートラルにセットし、
前記第１レシーバは、前記ニュートラルデータ信号を受け取ると前記イネーブル信号を上げる
ディスパッチャ。
【請求項８３】
請求項８１に記載のディスパッチャであって、前記ハンドシェークプロトコルは遅延非敏感であるディスパッチャ。
【請求項８４】
請求項７６に記載のディスパッチャであって、前記ディスパッチ回路は、前記命令を前記入力チャネルから受け取り、前記命令を前記出力チャネルへ送るよう動作可能なクロスバーを備え、前記ディスパッチ回路は、前記クロスバーを制御するよう動作可能な入力制御回路および出力制御回路をさらに備えるディスパッチャ。
【請求項８５】
請求項８４に記載のディスパッチャであって、前記入力制御回路は、前記命令ルーティング情報を参照して前記クロスバーについてのスプリット制御情報を生成するよう動作可能であり、前記入力制御回路は、前記入力および出力チャネルのそれぞれのペアに対応するリクエストビットを生成するようさらに動作可能であり、それぞれのリクエストビットは、前記対応する入力チャネルが前記対応する出力チャネルとリンクを形成すべきかどうかを示し、前記リクエストビットはまた前記命令ルーティング情報を参照して生成されるディスパッチャ。
【請求項８６】
請求項８５に記載のディスパッチャであって、前記出力制御回路は、前記リクエストビットを参照して前記クロスバーについてのマージ制御情報を生成するよう動作可能であるディスパッチャ。
【請求項８７】
請求項８６に記載のディスパッチャであって、前記出力制御回路はバイナリツリー構造を備えるディスパッチャ。
【請求項８８】
請求項８６に記載のディスパッチャであって、前記出力制御回路はリップリングリング回路を備えるディスパッチャ。
【請求項８９】
請求項８４に記載のディスパッチャであって、前記クロスバーは、前記命令をそれぞれの出力チャネルへ決定的な方法でルーティングするよう動作可能であるディスパッチャ。
【請求項９０】
請求項７６に記載のディスパッチャを備える集積回路。
【請求項９１】
請求項９０に記載の集積回路であって、前記集積回路は、ＣＭＯＳ集積回路、ＧａＡｓ集積回路、およびＳｉＧｅ集積回路のうちのいずれかを備える集積回路。
【請求項９２】
請求項７６に記載のディスパッチャを表すデータ構造をその上に記憶する少なくとも１つのコンピュータで読み取り可能な媒体。
【請求項９３】
請求項９２に記載の少なくとも１つのコンピュータで読み取り可能な媒体であって、前記データ構造は、前記ディスパッチャのシミュレーション可能な表現を備える少なくとも１つのコンピュータで読み取り可能な媒体。
【請求項９４】
請求項９３に記載の少なくとも１つのコンピュータで読み取り可能な媒体であって、前記シミュレーション可能な表現はネットリストを備える少なくとも１つのコンピュータで読み取り可能な媒体。
【請求項９５】
請求項９２に記載の少なくとも１つのコンピュータで読み取り可能な媒体であって、前記データ構造は、前記ディスパッチャのコード記述を備える少なくとも１つのコンピュータで読み取り可能な媒体。
【請求項９６】
請求項９５に記載の少なくとも１つのコンピュータで読み取り可能な媒体であって、前記コード記述はハードウェア記述言語に対応する少なくとも１つのコンピュータで読み取り可能な媒体。
【請求項９７】
請求項７６に記載のディスパッチャの少なくとも一部を表す半導体処理マスクのセット。
【請求項９８】
請求項７６に記載のディスパッチャであって、前記ディスパッチ回路は、少なくとも１つのタイミング推定に基づいて、少なくとも１つの出力チャネルへ前記命令をルーティングするよう動作可能であるディスパッチャ。
【請求項９９】
請求項９８に記載のディスパッチャであって、前記少なくとも１つのタイミング推定は、パルスタイミング推定、干渉タイミング推定、および黙示のデータニュートラル性タイミング推定のうちの任意のものを含むディスパッチャ。
【請求項１００】
請求項９９に記載のディスパッチャであって、前記パルスタイミング推定は、そうでなければ遅延非敏感な４フェーズハンドシェークに適用されるディスパッチャ。
【請求項１０１】
請求項９９に記載のディスパッチャであって、前記黙示のデータニュートラル性タイミング推定は、そうでなければ遅延非敏感な４フェーズハンドシェークに適用されるディスパッチャ。
【請求項１０２】
請求項９９に記載のディスパッチャであって、前記干渉タイミング推定は、干渉するオペレータ間の適切なタイミングマージンを推定するディスパッチャ。
【請求項１０３】
命令ルーティング情報に基づいて第１数の入力チャネル上で受け取られた複数の命令を、第２数の出力チャネルのうちの指定されたものへルーティングするよう動作可能なアービタであって、前記アービタは、異なる入力チャネルで受け取られ同じ出力チャネルを特定する命令の間で調停し、前記異なる入力チャネルの任意のものが後続の命令を、前記異なる入力チャネル間での調停が完了するまで転送しないよう動作可能であるアービタ回路を備えるアービタ。
【請求項１０４】
請求項１０３に記載のアービタであって、前記クロスバー回路は、前記データについてＭ個の1ofNエンコーディングを用い、ここでＭは１以上の整数であり、Ｎは２以上の整数であるアービタ。
【請求項１０５】
請求項１０３に記載のアービタであって、前記クロスバー回路は、前記ルーティング制御情報について1ofNエンコーディングを用い、ここでＮは２以上の整数であるアービタ。
【請求項１０６】
請求項１０３に記載のアービタであって、前記ルーティング制御情報は、スプリット制御情報およびマージ制御情報を含み、前記スプリット制御情報は、1ofAおよび1ofBエンコーディングを用いてエンコーディングされ、ここでＡ＊Ｂは前記第２数であり、前記マージ制御情報は、1ofCおよび1ofDエンコーディングを用いてエンコーディングされ、ここでＣ＊Ｄは前記第１数であるアービタ。
【請求項１０７】
請求項１０３に記載のアービタであって、前記クロスバー回路は、前記データを少なくとも１つの前記リンク上で非同期で転送するよう動作可能であるアービタ。
【請求項１０８】
請求項１０７に記載のアービタであって、前記クロスバー回路は、前記データを少なくとも１つの前記リンク上でハンドシェークプロトコルを用いて転送するよう動作可能であるアービタ。
【請求項１０９】
請求項１０８に記載のアービタであって、前記リンクのうちの前記少なくとも１つの上での第１センダーおよび第１レシーバ間の前記ハンドシェークプロトコルは、
前記第１レシーバからのイネーブル信号がハイになるとき、前記第１センダーがデータ信号を有効にセットし、
前記第１レシーバは、前記有効なデータ信号を受け取ると前記イネーブル信号を下げ、
前記第１センダーは、前記低イネーブル信号を受け取ると前記データ信号をニュートラルにセットし、
前記第１レシーバは、前記ニュートラルデータ信号を受け取ると前記イネーブル信号を上げる
アービタ。
【請求項１１０】
請求項１０８に記載のアービタであって、前記ハンドシェークプロトコルは遅延非敏感であるアービタ。
【請求項１１１】
請求項１０３に記載のアービタであって、前記ディスパッチ回路は、前記命令を前記入力チャネルから受け取り、前記命令を前記出力チャネルへ送るよう動作可能なクロスバーを備え、前記ディスパッチ回路は、前記クロスバーを制御するよう動作可能な入力制御回路および出力制御回路をさらに備えるアービタ。
【請求項１１２】
請求項１１１に記載のアービタであって、前記入力制御回路は、前記命令ルーティング情報を参照して前記クロスバーについてのスプリット制御情報を生成するよう動作可能であり、前記入力制御回路は、前記入力および出力チャネルのそれぞれのペアに対応するリクエストビットを生成するようさらに動作可能であり、それぞれのリクエストビットは、前記対応する入力チャネルが前記対応する出力チャネルとリンクを形成すべきかどうかを示し、前記リクエストビットはまた前記命令ルーティング情報を参照して生成されるアービタ。
【請求項１１３】
請求項１１２に記載のアービタであって、前記出力制御回路は、前記リクエストビット間で調停することによって前記クロスバーについてのマージ制御情報を生成するよう動作可能であるアービタ。
【請求項１１４】
請求項１１２に記載のアービタであって、前記出力制御回路はバイナリツリー構造を備えるアービタ。
【請求項１１５】
請求項１１４に記載のアービタであって、前記バイナリツリー構造は、複数のステージで構成され、ウィニング入力チャネルのインデックスを累積することによって前記リクエストビットの間で調停するよう動作可能な複数の調停回路およびマージ回路を備えるアービタ。
【請求項１１６】
請求項１１５に記載のアービタであって、前記ツリー構造のステージの振る舞いは、同時シーケンシャルプロセス（ＣＳＰ）記法を用いて
【数３】
2005516508.tif 000005
のように記述され、ここでL[0] およびL[1]はトリガ入力、Ｔはトリガ出力、Ａは調停結果であるアービタ。
【請求項１１７】
請求項１０３に記載のアービタであって、前記調停回路は、前記同じ出力チャネルに対応するグラントトークンを調停ウィニング入力チャネルに送ることによって、前記アービタのデッドロックを防止するよう動作可能なグラント回路を備えるアービタ。
【請求項１１８】
請求項１１７に記載のアービタであって、前記調停回路はまた、前記入力チャネルから前記命令を受け取り、前記命令を前記出力チャネルへ送るよう動作可能なメインクロスバーを備え、前記調停回路は、前記命令ルーティング情報から第１スプリット制御情報および第１マージ制御情報を生成することによって前記メインクロスバーを制御するよう動作可能な入力制御回路および出力制御回路をさらに備え、前記グラント回路は、前記グラントトークンを第２スプリット制御情報および第２マージ制御情報に応答して送るよう動作可能なグラントクロスバーを備え、前記第２スプリット制御情報は、前記第１マージ制御情報から導出され、前記第２マージ制御情報は、前記第１スプリット制御情報から導出されるアービタ。
【請求項１１９】
請求項１１７に記載のアービタであって、前記グラント回路は、１つまたはそれより小さいスラックで実現され、それにより特定のチャネルからの第２リクエストが、第１リクエストがグラントされるまでブロックされるアービタ。
【請求項１２０】
請求項１０３に記載のアービタであって、前記調停回路はまた、前記入力チャネルから前記命令を受け取り、前記命令を前記出力チャネルへ送るよう動作可能な第１クロスバーを備え、前記調停回路は、前記命令ルーティング情報から第１スプリット制御情報および第１マージ制御情報を生成することによって前記第１クロスバーを制御するよう動作可能な入力制御回路および出力制御回路をさらに備え、前記調停回路はまた、第２スプリット制御情報および第２マージ制御情報に応答して前記出力チャネルの任意のものから前記入力チャネルの任意のものへデータを転送するよう動作可能な第２クロスバーを備え、前記第２スプリット制御情報は、前記第１マージ制御情報から導出され、前記第２マージ制御情報は、前記第１スプリット制御情報から導出されるアービタ。
【請求項１２１】
請求項１２０に記載のアービタであって、前記調停回路は、２ウェイトランザクションがリクエストされたことの指示に応答してのみ、前記第２スプリット制御情報および第２マージ制御情報を生成するよう動作可能であるアービタ。
【請求項１２２】
請求項１１１に記載のアービタであって、前記クロスバーは、前記命令を出力チャネルに決定的な方法でルーティングするよう動作可能なアービタ。
【請求項１２３】
請求項１０３に記載のアービタを備える集積回路。
【請求項１２４】
請求項１２３に記載の集積回路であって、前記集積回路は、ＣＭＯＳ集積回路、ＧａＡｓ集積回路、およびＳｉＧｅ集積回路のうちのいずれかを備える集積回路。
【請求項１２５】
請求項１０３に記載のアービタを表すデータ構造をその上に記憶する少なくとも１つのコンピュータで読み取り可能な媒体。
【請求項１２６】
請求項１２５に記載の少なくとも１つのコンピュータで読み取り可能な媒体であって、前記データ構造は、前記アービタのシミュレーション可能な表現を備える少なくとも１つのコンピュータで読み取り可能な媒体。
【請求項１２７】
請求項１２６に記載の少なくとも１つのコンピュータで読み取り可能な媒体であって、前記シミュレーション可能な表現はネットリストを備える少なくとも１つのコンピュータで読み取り可能な媒体。
【請求項１２８】
請求項１２５に記載の少なくとも１つのコンピュータで読み取り可能な媒体であって、前記データ構造は、前記アービタのコード記述を備える少なくとも１つのコンピュータで読み取り可能な媒体。
【請求項１２９】
請求項１２８に記載の少なくとも１つのコンピュータで読み取り可能な媒体であって、前記コード記述はハードウェア記述言語に対応する少なくとも１つのコンピュータで読み取り可能な媒体。
【請求項１３０】
請求項１０３に記載のアービタの少なくとも一部を表す半導体処理マスクのセット。
【請求項１３１】
請求項１に記載のクロスバーを介して相互接続された複数のシステム要素を備えるシステムオンチップ。
【請求項１３２】
リクエストクロスバーとしての請求項１に記載のクロスバーの第１部分およびレスポンスクロスバーとしての請求項１に記載のクロスバーの第２部分を備えるシェアドメモリブリッジ。
【請求項１３３】
請求項７６に記載のディスパッチャを命令ディスパッチャとして備えるスーパスカラ中央処理ユニット。
【請求項１３４】
請求項１に記載のクロスバーをレジスタバイパスとして備えるスーパスカラ中央処理ユニット。
【請求項１３５】
請求項１に記載のクロスバーをスイッチファブリックとして備えるパケットスイッチングデバイス。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、２００２年１月２５日出願、米国特許仮出願第６０／３５２，１３１号、「ASYNCHRONOUS CROSSBAR CIRCUIT WITH DETERMINISTIC OR ARBITRATED CONTROL」（弁護士整理番号FULCP001P）の優先権を主張し、その全体が全ての目的のためにここで参照によって援用される。
【０００２】
本発明は、非同期ディジタル回路設計に関し、より具体的には非同期クロスバーおよび関連する制御回路に関する。
【背景技術】
【０００３】
同時に高速に、かつより複雑なディジタル回路、例えばマイクロプロセッサへのますます増加する要求は、従来のディジタル回路設計手法をその限界まで押しやっている。高クロックレート（すなわち１００ＭＨｚより高い）および設計の複雑さ（例えば１０００万以上のトランジスタを持つ超大規模集積（ＶＬＳＩ）デバイス）の組み合わせのために、信号伝搬遅延は、設計を考慮するときに支配的になった。もしディジタル回路設計が今までのようにムーアの法則に従い続けようとするなら、設計パラダイムの大転換が必要であることはまちがいない。
【０００４】
非同期ＶＬＳＩは、ディジタル回路設計において研究および開発が盛んなエリアである。これは、グローバルクロック同期信号が存在しないディジタル回路設計の全ての形態をいう。遅延非敏感な非同期設計は、そのもともとの性質から、従来の設計パラダイムの発展の唯一最大の障害となってきた信号伝搬遅延に鈍感である。すなわち、遅延非敏感回路設計は、ディジタル回路の任意の遷移が無限の遅延を持った場合の特性を維持し、その回路はそれでも正確に振る舞う。回路は、シーケンスを守るが、絶対的なタイミングは必要ではない。この設計スタイルは、タイミング推定、グリッチ、または競合条件から生じる設計および検証の困難さを回避する。
【０００５】
一般に言って、同期設計スタイルは、深刻なパフォーマンス限界に直面している。ある非同期設計手法はまた、同様の限界、例えば競合条件で困難にぶつかっている。対照的に、非同期ディジタル設計の遅延非敏感な分野は、これら限界に対するその相対的な耐性のために、ディジタル回路のパフォーマンスにおける将来の発展を支持する大きな約束をされているようである。
【０００６】
遅延非敏感非同期ディジタル設計に関する背景情報については、以下の論文を参照されたい。A.J. Martin, "Compiling Communicating Processes into Delay-Insensitive Circuits," Distributed Computing, Vol.1, No.  4, pp.  226-234, 1986; U.V. Cummings, A.M. Lines, A.J. Martin, "An Asynchronous Pipelined Lattice Structure Filter." Advanced Research in Asynchronous Circuits and Systems, IEEE Computer Society Press, 1994; A.J. Martin, A.M. Lines, et al, "The Design of an Asynchronous MIPS R3000 Microprocessor." Proceedings of the 17th Conference on Advanced Research in VLSI, IEEE Computer Society Press, 1997;およびA.M. Lines, "Pipelined Asynchronous Circuits." Caltech Computer Science Technical Report CS-TR-95-21, Caltech, 1995、これらそれぞれは、その全体が全ての目的のためにここで参照によって援用される。
【０００７】
また１９９８年５月１２日発行の米国特許第５，７５２，０７０号「Asynchronous Processsors」、および２０００年３月１４日発行の米国特許第６，０３８，６５６号、「Pipelined Completion for Asynchronous Communication」を参照されたい。これらのそれぞれはその全体が全ての目的のためにここで参照によって援用される。
【発明の開示】
【発明が解決しようとする課題】
【０００８】
もし非同期ディジタル設計手法が、ディジタル回路およびシステムのパフォーマンスが歴史的な法則に則って改善され続けていくことを可能にするディジタル設計手法になるのであれば、対応する同期型回路やシステムのパフォーマンスに匹敵し凌駕するような回路およびシステムの基本構成単位が提供されなければならない。
【課題を解決するための手段】
【０００９】
本発明によれば、非同期ＶＬＳＩ設計のクリチカルな問題を解決する回路が提供される。ある実施形態によれば、ＰからＱへのクロスバーが提供され、これは全ての考えられる組み合わせにおいてＰ入力チャネルをＱ出力チャネルにルーティングできる。他の実施形態によれば、ディスパッチャが提供され、これは入力を特定された出力にルーティングすることによって、それぞれのチャネル上の与えられた部分的順序を維持するようにクロスバー回路を決定的な方法で制御するよう動作可能である。さらに他の実施形態によれば、調停メカニズムが提供され、これはクロスバー回路の入力をその出力に非決定的な方法で制御するよう動作可能である。
【００１０】
よってさまざまな実施形態によれば、本発明は、ルーティング制御情報にしたがって、データを第１数の入力チャネルの任意のものから、第２数の出力チャネルの任意のものへルーティングするよう動作可能なクロスバーに関する方法および装置を提供する。入力チャネルおよび出力チャネルのそれぞれの組み合わせは、複数のリンクのうちの１つに対応する。このクロスバー回路は、データを決定的な方法でルーティングするよう動作可能であり、それによりルーティング制御情報によって表された部分的順序付けを維持できる。異なるリンク上のイベントは非相関である。
【００１１】
実施形態の他のセットによれば、ディスパッチャが提供され、これは命令ルーティング情報に基づいて第１数の入力チャネル上で受け取られた順序付けられた命令のストリームを、第２数の出力チャネルのうちの指定されたものへルーティングするよう動作可能である。前記ディスパッチャは、前記命令をそれぞれの出力チャネルへ決定的にルーティングし、それにより前記順序付けられたストリーム内で規定されたそれぞれの出力チャネルについての部分的順序付けを維持するよう動作可能であるディスパッチ回路を含む。異なる出力チャネル上の命令は非相関である。
【００１２】
さらに他の実施形態のセットによれば、アービタが提供され、これは命令ルーティング情報に基づいて第１数の入力チャネル上で受け取られた複数の命令を、第２数の出力チャネルのうちの指定されたものへルーティングするよう動作可能である。前記アービタは、異なる入力チャネルで受け取られ同じ出力チャネルを特定する命令の間で調停し、前記異なる入力チャネルの任意のものが後続の命令を、前記異なる入力チャネル間での調停が完了するまで転送しないよう動作可能であるアービタ回路を備える。
本発明の性質および利点をさらに理解することは、明細書の残りの部分および図面を参照することによって達成されよう。
【発明を実施するための最良の形態】
【００１３】
発明者によって考えられる本発明を実施するためのベストモードを含む本発明の具体的な実施形態を詳細に参照する。これら実施形態の例は、添付図面に示される。本発明は、これら具体的な実施形態について記載されるが、記載された実施形態に本発明を限定するよう意図はされない。むしろ添付の特許請求の範囲に規定される本発明の精神および範囲内に含まれるように、代替物、改変物、および等価物をカバーするよう意図される。以下の記載において、多くの具体的な詳細が述べられるが、これは本発明の完全な理解を促すためである。本発明は、これら具体的な詳細の一部または全部なしでも実施されえる。さらによく知られたプロセス操作は、本発明の趣旨を不必要にぼかさないために記載されていない。
【００１４】
始めに、本願に記載された手法および回路の多くは、遅延非敏感非同期ＶＬＳＩとして記載され実現されることに注意されたい。しかし本発明の原理および手法は、例えば遅延に鈍感ではない非同期ＶＬＳＩおよび同期ＶＬＳＩのような他のコンテキストにおいても用いられえることが理解されよう。
【００１５】
本発明のさまざまな実施形態は、さまざまな方法で本発明の範囲から逸脱することなく実現されえることが理解されよう。すなわち、ここで記載された非同期プロセスおよび回路は、コンパイルのさまざまな段階におけるソフトウェア（オブジェクトコードまたは機械語）において、１つ以上のネットリストとして、シミュレーション言語において、ハードウェア記述言語において、半導体処理マスクのセットによって、または部分的に、または完全に実現された半導体デバイスとして表現されえる（限定なく）。当業者に理解される前述のそれぞれについてのさまざまな代替物も本発明の範囲に入る。例えば、ここで記載されたプロセスおよび回路を設計および製造するのに適するコンピュータで読み取り可能な媒体、ソフトウェア言語（例えばVerilog、ＶＨＤＬ）、シミュレーション可能な表現（例えばＳＰＩＣＥネットリスト）、半導体プロセス（例えばＣＭＯＳ、ＧａＡｓ、ＳｉＧｅなど）、およびデバイスタイプ（例えばＦＰＧＡ）は、本発明の範囲に入る。
【００１６】
本発明はまた、疑似コード言語ＣＳＰ（同時シーケンシャルプロセス）を利用して高級アルゴリズムを記述する。ＣＳＰは、典型的にはパラレルプログラミングソフトウェアプロジェクトにおいて、および遅延非敏感ＶＬＳＩにおいて用いられる。この特定の言語および記述法の使用は単に例示的であり、本発明の基本的局面は本発明の範囲から逸脱することなく、さまざまな方法で表現され実現されえることが理解されよう。
【００１７】
さらに、ここで記載された回路のさまざまな態様のためのＣＳＰ仕様のトランジスタレベルの実現への変換は、A. Linesによる「Pipelined Asynchronous Circuits」（ここで参照によって援用される）において記載される手法によって達成されえる。しかし非同期設計手法のさまざまな種類の任意のものがこの目的で用いられえることが理解されよう。
【００１８】
ここで用いられるＣＳＰは、以下の構造および文法を有する。プロセスは静的かつシーケンシャルであり、他のプロセスとチャネルを通して通信する。複数のプロセス群が合わさってパラレルプログラムを構成する。［および］は、ｉｆ文を表し、＊［および］はループを表す。
【００１９】
多肢選択は、Ｂ→Ｓのペアをｉｆ文またはループの中に追加することによってなされ、□（決定的選択）または｜（非決定的選択）によって分離され、ここでＢはブール式であり、Ｓはステートメントである。よって［Ｂ１→Ｓ１□Ｂ２→Ｓ２］は、もし式Ｂ１が真ならＳ１を実行し、またはもし式Ｂ２が真ならＳ２を実行することを意味する。もしＢ１もＢ２も真でないなら、このステートメントはいずれかがそうなるまで待つ（ｉｆ−ｅｌｓｅ構文とは異なり）。略記法＊［ｓ］は、ステートメントＳを無限に繰り返すことを意味する。略記法［Ｂ］は、ブール式Ｂが真になるのを待つことを意味する。ローカル変数は、整数であるとみなされ、ｘ：＝ｙ＋１のような整数式に代入されえる。セミコロンは、ステートメントを厳密な順序付けで分離する。コンマは、ステートメントを順序付けなしで分離する。疑問符および感嘆符は、それぞれチャネルから受け取り、チャネルに送ることを表すのに用いられる。よって＊［Ａ？；ｙ：＝ｘ＋１；Ｂ！ｙ］は、整数ｘをチャネルＡから受け取り、それから整数ｙに式ｘ＋１を代入し、それからｙをチャネルＢに送り、それから永久に繰り返すことを意味する。
【００２０】
本発明のさまざまな具体的な実施形態によれば、データのラッチングはレジスタの代わりにチャネル内で起こる。このようなチャネルは、送信回路から受信回路へのデータのＦＩＦＯ（ファーストインファーストアウト）転送を実現する。データワイヤは、センダからレシーバへ走り、イネーブル（すなわちアクノリッジの反対の意味）ワイヤは、フロー制御のために逆方向に走る。これら実施形態の具体的なものによれば、近接回路（プロセス）間の４フェーズのハンドシェークがチャネルを実現する。４フェーズは、以下の順序である。１）センダは、高イネーブルを待ち、それからデータを有効にセットする。２）レシーバは、有効なデータを待ち、それからイネーブルを低にする。３）センダは低イネーブルを待ち、それからデータをニュートラルにセットする。そして４）レシーバはニュートラルデータを待ち、それからイネーブルを高にする。このハンドシェークプロトコルの使用は例示目的であって、したがって本発明の範囲はこれに限定されるべきではないことに注意されたい。
【００２１】
具体的な実施形態によれば、データの遅延非敏感エンコーディング（delay-insensitive encoding）は、デュアルレール（dual rail）であり、1of2とも呼ばれる。このエンコーディングにおいて、２本のワイヤ（レール）が用いられて２つの有効な状態およびニュートラルな状態を示す。両方のワイヤがローのとき、データはニュートラルである。第１ワイヤがハイのとき、データは有効な０である。第２ワイヤがハイのとき、データは有効な１である。両方のワイヤが一度にハイになることは許されない。チャネルＸに関連付けられたワイヤは、データについてはX0、 X1 と、イネーブルについてはXeと書かれる。
【００２２】
他の実施形態によれば、大きな整数は、1of3または1of4コードのようなより多くのワイヤによってエンコードされる。ずっと大きな数については、異なる数値的大きさの複数の1ofNが併せて用いられる。例えば３２ビットは、３２個の1of2コードまたは１６個の1of4コードによって表現されえる。この場合、下付き添え字は、それぞれの1ofNコードの重みを示し、すなわち、Lrgはｇ番目のビット（またはグループ）のｒ番目のワイヤであり、Legは関連付けられたイネーブルである。
【００２３】
さらに他の実施形態によれば、いくつかの関連するチャネルは、L[i]またはV [i, j ]のような１−Ｄまたは２−Ｄアレイにまとめられえる。このような実施形態における個々のワイヤを特定するために、記法L[i]rまたはL[i]rgが用いられる。
【００２４】
具体的な実施形態によれば、本発明によるクロスバーの設計は、米国特許第６，０３８，６５６号（ここで参照によって援用される）に記載された方法を利用して大きなデータパスの速度を改善する。この方法は、例えば、遅延に対する非敏感性を維持しつつ、１つの３２ビットデータパスを４つの８ビットデータパスに減らすような、データパスをより小さいビットサイズ複数のデータパスに分割する方法を記載する。
【００２５】
この開示における図は、ボックスおよび矢印の図およびトランジスタの図を含む。ボックスの図において、ボックスは、回路またはプロセスを表現し、矢印はボックス間のＦＩＦＯチャネルを表現する。ＦＩＦＯチャネルはまた、ボックス内で外に出されえる。同じ名前の任意のチャネルまたはワイヤは、接続が描かれていないときでも接続されるよう意図される。場合によっては回路の「内部」ポート名が入力チャネルまたは出力チャネルの隣にボックス内で書かれる。
【００２６】
トランジスタの図において、矢印（またはライン）は個々のワイヤを表現する。標準的なゲートシンボルが可能な限り用いられ、「Ｃ」がその上に書かれたＮＡＮＤゲートのようにＣ要素も追加されている。このゲートは、標準の非同期ゲートであり、ミュラーＣ要素（Mueller C-element）またはコンセンサス要素（consensus element）とも呼ばれる。ゲート表現およびＣ要素１００のトランジスタレベルの実現例が図１に示される。
【００２７】
簡潔さのために回路図からある種の機能は省略されていることに注意されたい。例えばいくつかの回路ノードは「動的」であり、これはそれらがいつもハイまたはローに駆動されるわけではなく、その状態を不定に保持すると期待される。これは、「スタティサイザ」、すなわちノードに接続された小さなクロス結合されたインバータのペアを必要とする。スタティサイザは省略されるが、プルアップおよびプルダウンネットワークが論理的な補足物（logical complements）（実質的に全ての非標準ゲートおよびＣ要素）ではない任意のノードに存在すると推定されえる。さらに、これらパイプラインされた回路は、チップがブートするときに初期状態にリセットされなければならず、このためResetおよびReset＼（Resetのバー、否定）信号を用いるいくつかの追加のトランジスタが必要となる。ふつうリセット状態は、Resetがアサートされたまま左のイネーブルをローにすることによって達成される。
【００２８】
ここで記載されるように、スプリット（Split）は、１からＱのバスで、制御チャネルＳを読み、単一のＬチャネルから入力データの１つのトークンを読み、それからデータをＳから読まれた値によって選択されるＱ個の出力チャネルのうちの１つに送る。マージ（Merge）は、Ｐから１のバスで、制御チャネルＭを読み、それからＭから読まれた値によって選択されたＰ入力チャネルのうちの１つからのデータのトークンを読み、それからそのデータを単一の出力チャネルＲに送る。図２は、スプリット２００の基本ブロック図である。図３は、マージ３００の基本ブロック図を示す。上述の参照によって援用されるA.Linesによる「Pipelined Asynchronous Circuits」も参照されたい。
【００２９】
本発明のさまざまな実施形態によれば、ＰからＱのクロスバー４００は、図４に示されるようにＰ  ＱウェイのスプリットおよびＱ  Ｐウェイのマージから構築されえる。Ｐスプリットバスのｉ番目、すなわちsplit[i]は、プログラム＊[S[i]?j , L[i]?x; V [i, j]!x]を走らせる。Ｑマージバスのｊ番目、すなわちmerge[j]は、プログラム＊[M[j]?i; V [i, j]?x; R[j ]!x]を走らせる。本発明のさまざまな実施形態と共に利用されえる第１非同期クロスバー設計によれば、は、スプリットデータ出力およびマージデータ入力の間の中間データチャネルを表現する。後述の本発明の具体的な実施形態によれば、これらチャネルは、除去されている。
【００３０】
クロスバー４００は、入力および出力側の両方からS[i]およびM[j]制御チャネルを介して制御される。これら制御チャネルの情報に基づいて、それぞれのチャネルを通して送られたトークンのシーケンスは、入力および出力チャネルについて完全に決定的であるが、より大きいグループのチャネルについてはそうではない。すなわち、関係のないチャネルの通信のタイミングは制約がない。入力／出力ポートの任意の２つの無関係のペアは、競合なくパラレルに通信できる。もし２つの入力／出力転送が同じ入力または出力ポートを参照するなら、そのポートと関連付けられた制御ストリームは、曖昧さなしに順序を決定するだろう。これら制御チャネルの情報を生成するさまざまな手法が以下に記載される。
【００３１】
この明細書の前で述べたように、本発明によって設計された非同期クロスバーのあるタイプは、情報をスプリットバスから指定されたマージバスへ渡す実際のチャネルV [i, j]を含む。これらチャネルは、さまざまな点で有利に用いられえる。例えば、バッファリングの量を変えることが、それぞれのリンクに関連付けられた中間チャネルに付加されえ、それによってさまざまなパフォーマンスの目的を達成する。しかしこれらチャネルおよび関連付けられたハンドシェーキングオーバヘッドのために、そのように設計された非同期クロスバーのサイズおよび／または電力消費は、ＰまたはＱのいずれかの大きさに依存して実現不可能になりえる。
【００３２】
よって、本発明の具体的な実施形態は、少なくともスプリットおよびマージ機能性の一部を単一のルータセル（記法router_cellもまたここでは用いられる）に結合することによって、これらチャネルのうちの少なくともいくつかをなくすクロスバー設計を提供する。この実施形態によって設計された非同期クロスバーの外部に見える振る舞いは、この改良されたクロスバー設計は１ステージの遊び（パイプライン深さ）がなくなったことを除いて、V [i, j]チャネルを含む同じサイズ（すなわちＰからＱ）のクロスバーのそれと事実上、同一である。
【００３３】
本発明によって設計されたクロスバーの具体的な実施形態が図５〜８を参照してこれから説明される。この実現例によれば、それぞれのスプリットバスは、１つのsplit_env部分およびQ split_cell部分を含み、それぞれのマージバスは、１つのmerge_env部分およびP merge_cell部分を含む。split_cellは、それぞれの出力チャネルのために反復されたスプリットバスの一部を含み、split_envは回路の残りを含む。同様に、merge_cellは、それぞれの出力チャネルのために反復されたマージバスの一部を含む。図９を参照して説明されるように、具体的な実施形態によれば、特定の入力／出力の組み合わせに対応するsplit_cellおよびmerge_cellのそれぞれのペアの機能性は、単一のrouter_cellに組み合わされ、よってスプリットおよびマージバス間の中間チャネルをなくしている。
【００３４】
機能的には、それぞれのsplit_cell[i, j]は、S[i]が有効になるのを待ち、S[i]の値がjに等しい（すなわちS[i]jが真である）ことをチェックする。もしそうであるなら、それは、その出力V[i, j]eからのイネーブルをチェックし、ハイであるときには、それは有効なデータをL[i]からV[i, j]へコピーする。いったんデータがV[i, j]へコピーされると、split_cell[i, j]は、そのイネーブルをsplit_env, se[i, j]へ下げる。最終的に、S[i]、L[i]、およびV [i, j ]eがニュートラルに戻り、split_cell[i, j]はデータをリセットしse[i, j]を再び上げることができる。１ビットデータおよび１ビット制御（共に1of2コードとしてエンコードされる）を持つsplit_cell５００の概略図は、図５に示される。
【００３５】
split_env[i]は、L[i]チャネルの有効性およびニュートラル性を試験し、split_cellからのse[i, 0..Q - 1]のAND論理を計算し、S[i]およびL[i]入力チャネルについてのアクノリッジを作る。S[i]の有効性およびニュートラル性は、split_cellからのアクノリッジによって推定される。１ビットデータおよび２つのsplit_cellについてのsplit_env６００の概略図は図６に示される。
【００３６】
それぞれのmerge_cell[i, j]は、M[j]が有効になるのを待ち、M[j]の値がiに等しい（すなわちM[j ]iが真である）ことをチェックする。もしそうであるなら、それはmerge_envからのgo[j]信号（出力イネーブルの準備ができていることを含む）を待ち、入力データV[i, j]が有効になるのを待つ。これが起こるとき、それはV [i, j]の値をR[j]にコピーする。merge_envは、R[j]の有効性をチェックし、rv[j]をハイにセットすることによってこの状態を全てのmerge_cellにブロードキャストする。次にmerge_cellは、そのイネーブルme[i, j]およびV [i, j]eを下げる。いったんM[j]およびV[i, j]データがニュートラルに戻ると、go[j]が下げられ、R[j]がニュートラルに戻され、rv[j]が下げられ、merge_cellはイネーブルme[i, j]およびV[i, j]eを上げる。１ビットデータおよび１ビット制御（1of2コードとしてエンコードされる）を持つmerge_cell７００についての概略図は図７に示される。
【００３７】
merge_envは、R[j]アクノリッジの準備ができていることをチェックし、go[j]を上げる。M[j]は直接にmerge_cellへ行き、そのうちの１つは、R[j]を新しい有効な値にセットすることによって応答する。merge_envは、それからrv[j]を上げ、その後、merge_cellはme[i, j]で応答する。merge_env[j]はこれらアクションの完了をチェックし、それからM[j]をアクノリッジする。いったんM[j ]が再びニュートラルになり、R[j]がアクノリッジすると、merge_env[j]はgo[j]を下げ、これはmerge_cellがme[i, j]をリセットさせるようにする。merge_env[j]はまたR[j]をニュートラル値にリセットする。いったんこれらのアクションが完了すると、merge_env[j]はM[j ]のアクノリッジを下げる。１ビットデータおよび２つのマージセルについてのmerge_env８００の概略図は図８に示される。
【００３８】
本発明の他の具体的な実施形態によれば、クロスバー内のそれぞれのグリッドにおいて（すなわちiおよびjのそれぞれの組み合わせについて）、router_cell[i, j]が存在し、これは１つのsplit_cell[i, j]および１つのmerge_cell[i, j]の機能性を上述のように組み合わせる。split_env[i]およびmerge_env[j]は、それらのrouter_cellと上述のハンドシェークプロトコルを用いて通信する。router_cellは、別々のsplit_cellおよびmerge_cellの全ての条件のスーパーセットを待ち、それらのenvについて両方のアクションを行う。
【００３９】
本発明の実施形態は、選択されたリンクだけが本発明のrouter_cellで実現されると想定されることに注意されたい。そのような実施形態によれば、他のリンクは、図５および７のsplit_cellおよびmerge_cellおよびそれらの関連する中間チャネルV [i, j]を用いて実現される。そのような実施形態は、例えば追加のバッファリングが１つ以上の特定のリンクに望まれるが、それぞれのリンクについて中間チャネルを持たせることに伴うエリアペナルティを払うのは望ましくない場合には有用かもしれない。
【００４０】
さらにより具体的な実施形態によれば、router_cellは以下を行う。それはそのS[i]入力が有効でjに等しくなるのを待ち、そのM[j]入力が有効でiに等しくなるのを待ち、L[i]が有効になるのを待ち、merge_envからのgo[j]がハイになるのを待つ。いったんこれが起これば、router_cell[i, j]は、中間V[i, j]チャネルなしでL[i]を直接にR[j]にコピーする。merge_env[j]はR[j]がセットされたことを検出し、rv[j]を上げることによってそれを信号で表す。それからrouter_cell[i, j]は、そのイネーブルをenvのse[i, j]およびme[i, j]に下げることができ、これは同じ信号でありえる。
【００４１】
リセットフェーズは対称的に進められる。router_cellは、S[i]およびM[j]がニュートラルになり、go[j]が下がるのを待つ。merge_env[j]はR[j]をニュートラルにリセットし、それからrv[j]を下げることによって完了を信号で表す。最後に、router_cell[i, j]はそのイネーブルを共にenvに上げる。１ビットデータおよび１ビットS[i]およびM[j]を持つrouter_cell９００についての概略図は図９に示される。具体的な実施形態によれば、router_cell９００と用いられるsplit_envおよびmerge_envは、別々のsplit_cellおよびmerge_cellと用いられるそれらと同じである（上の図６および８を参照）。
【００４２】
理解されるようにさまざまな実施形態によれば、基本クロスバー実現例のいずれも異なるデータサイズおよびＰおよびＱ値に拡張されえる。また後述のエリアまたは速度を改善しえるいくつかの回路変更が存在する。すなわち、後述のさまざまな異なるデータエンコーディング、ルータセル回路実現例、および他の回路実現例の変更事例は、エリアおよび速度間のさまざまなトレードオフを表す。
【００４３】
さまざまな実施形態によれば、S[i]は、Ｑ個の可能なsplit_cellのうちから選択するために1ofQチャネルでエンコードされえる。これはＳ本のワイヤ上のファンアウトを増やし、se[i, j]をsplit_env中に組み合わせるためにより大きいANDツリーを必要とする。同様にM[j]は、Ｐ個の可能なmerge_cellのうちから選択するために1ofPチャネルでエンコードされえる。制御ワイヤの数は、ＰおよびＱと直線的に比例し、これはより小さいクロスバー、例えば８×８以下のものについては適する。さらにより具体的な実施形態によれば、seおよびmeについてのANDツリーは、ワイヤリングを減らすためにデータパスにわたって物理的に分散される。
【００４４】
例えば１６×１６以上の、より大きいクロスバーについて、S[i]およびM[j]は、それぞれ1ofAと1ofBとの1ofNコードのペアでエンコードされえ、これはA * Bの可能性を生む。Ｓ制御の最下位および最上位の半分は、S[i]0およびS[i]1と呼ばれる。M[j]0およびM[j]1についても同様である。このエンコーディングのワイヤリングコストは、√Ｐまたは√Ｑに従って増え、６４×６４のクロスバーまでうまく動作する。遅延非敏感設計においては、split_envがもう一方をチェックする場合は、router_cell中のニュートラル性についてS[i]0/S[i]1のペアのうちの１つだけをチェックすることが可能である。M[j]0/M[j]1のペアについても同様である。
【００４５】
大きなＰまたはＱについては、あるrouter_cellが選択されたか（「ヒット」とも呼ばれる）を検出するのに用いられるトランジスタの個数がますます複雑化し、このコストは全てのデータワイヤについて重複する。したがって、大きなＰ、Ｑ、またはデータサイズを有するクロスバーについてのある実施形態によれば、hit[i, j]信号は、ＳおよびＭワイヤを直接用いる代わりに単一のヒット回路において計算される。対称hit回路を用いる１ビットデータおよび２個の1of4制御を持つrouter_cell１０００の例が図１０に示される。S[i]1またはM[j]1のニュートラル性をチェックしない非対称hit回路を用いる代替のrouter_cell１１００は図１１に示される。非対称hit回路は、split_envおよびmerge_envがそれぞれS[i]1およびM[j]1のニュートラル性をチェックするように変更される。
【００４６】
さまざまな実施形態によれば、データエンコーディングを他の1ofNコード、例えばイベントを信号で表すために1of1から1of4へと２ビットの良好な低電力エンコーディングなどのために変更するのは簡単である。より大きなデータサイズを持つ実施形態によれば、複数の1ofNコードが採用されえる。図１２は、図１１の非対称hit回路を用いる２つの1of4チャネルを持つ４ビットデータおよび制御を持つrouter_cell１２００を示す。それぞれ1of4に対応する異なるrv[j]0/rv[j]1およびgo[j]0/go[j]1ワイヤを用いること、またはそれらをmerge_envから単一のrv[j]およびgo[j]に組み合わせることが可能である。
【００４７】
さまざまな実施形態によれば、マルチキャストが本発明によるクロスバーにおいてサポートされえる。あるそのような実施形態によれば、S[0..P - 1]制御は、1ofQコードから1of2コードのビットベクタS[0..P - 1, 0..Q - 1]へ変換される。それぞれのS[i, j]ビットは、直接にrouter_cell[i, j]へ行き、ここでS[i, j]1ワイヤがS[i]jの代わりにhit回路において用いられる。split_envにおいて、se[i, j]信号は、最初、S[i, j]0の逆数（inverse）とANDが取られ、それからANDツリーの代わりにＣ要素ツリーと組み合わせられる。本質的に、複数の同時のhitは、１つの入力について起こりえ、split_ envはそれらが全て完了したことをチェックしなければならない。マージ側は以前のように制御される。ここで後述のディスパッチおよびアービタ回路の実現例は、このようなマルチキャストクロスバーを制御するように構成されえることに注意されたい。
【００４８】
本発明によって設計された非対称クロスバーのさまざまな実施形態は、データパスサイズより小さいいくつかの並列のチャンクにまとめられる。データパスサイズがＢビット（これはこの実施形態における遅延非敏感コードについての２＊Ｂ本のワイヤを必要とする）であり、splitで用いられる追加の制御ワイヤの本数はｓであり、mergeの追加の制御ワイヤの本数はｍ（１つのホット制御エンコーディングを用いられる実施形態について）であると仮定すると、もしデータパスがＣビットのチャンクに分けられるなら、クロスバーのワイヤリング制限エリアは、(B/C)＊ P＊Q＊(2＊ C+s)＊(2＊C + m)になる。よって最適なＣは、（√（ｓ＊ｍ））／２である。
【００４９】
この式を用いて、スプリット制御オーバヘッドの１２本のワイヤおよびマージ制御オーバヘッドの１４本のワイヤを持つ３２ビットデータパスは、約６から７ビットのチャンクのサイズに分けられる。実際には、回路の所望の速度（小さいチャンクが望ましい）およびさまざまなチャンクのサイズの便宜性のような他のファクタが考慮される。例えばこのような考慮に依存して、３２ビットクロスバーは、４ビットの８チャンク（より速い）または８ビットの４チャンク（より小さい）として実現されえる。他のチャンクサイズは許容できないエリア、または不便なペナルティを持ちえるが、それでも本発明の範囲に入る。
【００５０】
非同期クロスバーのためのS[i]およびM[j]制御チャネルを生成するさまざまな手法がこれから説明される。このような手法は、例えば上述の異なるクロスバーを含むさまざまな非同期クロスバーアーキテクチャの任意のものに適用されえることが理解されよう。すなわち、ここで記載されるディスパッチおよびアービタ回路は、本発明によって設計された任意のクロスバー回路だけでなく、Ｐ入力チャネルをＱ出力チャネルに相互接続する基本機能性を有する任意のタイプのクロスバー回路を制御するために採用されえる。さまざまな実施形態によれば、マルチキャストクロスバーの制御および２ウェイトランザクションはこれら回路の特定の実現例によって提供されえる。
【００５１】
本発明のさまざまな実施形態によれば、ＰからＱクロスバーにおけるデータ転送の部分的（または予測された）順序、すなわち与えられたチャネル上で予測されたときの動作の順序は決定的でなければならない。すなわち、あるチャネルを伴う動作の順序は、決定的順序で起こり、しかし異なるチャネル上の動作は、互いに任意の順序関係で起こりえる。よってこのような実施形態によれば、次の問題を解決するディスパッチャが提供される。L[0..P -1]チャネル上の入力命令の順序付けられたシーケンスが与えられるとき、その命令についてそれぞれの命令をTO[0..P - 1]チャネルによって特定されたR[0..Q - 1]出力チャネルのうちの１つにルーティングする。
【００５２】
ディスパッチャは、それぞれの出力チャネルへの命令の順序を維持しなければならない。しかし、異なる出力チャネルへの命令が順序通りに渡されることは要求されない。これにより、インプリメントにおける内部パイプライン、全てのチャネル上での恣意的バッファリング、および複数の同時転送が可能になる。
【００５３】
Ｐが１の場合、ディスパッチャの簡単な実現例は、ＳとしてのLおよびTO、およびR[0..Q - 1]を用いる単にＱウェイのスプリットバスである。さらにより具体的な実施形態によれば、異なるＲへの遅れた命令にもかかわらず、後で命令が発行されることを可能にするために、追加のバッファリングが出力チャネル上に提供されえる。
【００５４】
他の実施形態によれば、複数の命令がクロスバーを用いて適切な順序でパラレルに発行される。ディスパッチャのL[i]およびR[j]データチャネルは、直接にそのクロスバーに接続する。ディスパッチャのTO[i]は、クロスバーのS[i]にコピーされる。M[j]クロスバー制御チャネルは、TO[i] から導かれ、それによりそれらがそれぞれの出力チャネル上で予測されたプログラム順序を維持できる。ある実施形態によれば、これは次のようにして達成される。
【００５５】
図１３のディスパッチャ１３００を参照し、それぞれのinput_ctrl[i]は、この入力がその出力に行きたいかどうかをTO[i]に基づいて示すリクエストビットreq[i, j]（例えば1of2コード）をそれぞれのoutput_ctrl[j]に送る。それからそれぞれのは、これらのビットを全てのから集め、巡回順序でそれぞれの１のインデックス（indices）を決定する。これらインデックスは、クロスバーのM[j]チャネルを制御する。クロスバーはそれからペイロードを転送する。
【００５６】
入力コントローラ、例えばinput_ctrl[i]回路は、req[i, j]ビットを作り、TO[i]をS[i]にコピーするために、上に参照によって援用されたA. Linesによる「Pipelined Asynchronous Circuits」において記載されるアプローチを用いて導き出せる。
【００５７】
それぞれの出力コントローラ（combineともここでは呼ばれる）は、ビットベクタを受け入れ、入力０からＰ−１への巡回順序で全ての１の位置を読み出す。ある実施形態によれば、これはバイナリツリー構造を用いて達成される。ツリーのそれぞれのステージは、その下位Ｌ入力上の１の数を受け取り、それからその上位Ｈ入力から受け取り、ツリーの次のステージへ和を出力する。これらの数は、状態付きで1of3コードによってシリアルにエンコーディングされる。すなわち、ゼロ、ラスト、および非ラストである。例えば３は、シーケンスによって表現され、すなわち非ラスト、非ラスト、ラストである。
【００５８】
それぞれのツリーステージはまた、1of2チャネルを出力し、１がロー（０）またはハイ（１）側から来たかを示す。これの追加チャネルは、それまでのインデックス（index）のＭＳＢビットになる。それまでのＬＳＢビットは、現在のＭＳＢビットによって制御され、ローまたはハイの前のステージのいずれかからのインデックスの２ウェイmergeによって得られる。ツリーの最終の1of3のビット和は廃棄され、累積されたインデックスビットはクロスバーについてのＭ制御になる。
【００５９】
本発明のさまざまな具体的な実施形態によれば、コンバインは、上に参照によって援用されたA. Linesによる「Pipelined Asynchronous Circuits」において記載されるアプローチを用いて実現されえる。このような実施形態において、１つの内部状態ビットは、左または右の側から来るシーケンスを区別するために提供される。図１４は、４ウェイツリーコンバイン１４００を示す。このようなコンバイン回路の具体的な実施形態についてのＣＳＰは以下の通りである。
【００６０】
【数１】
2005516508.tif 000003
【００６１】
ＬおよびＨは、1of3コードでシリアルにエンコーディングされた入力リクエストカウントである。Ｒはシリアルにエンコーディングされた出力リクエストカウントである。Ｍは、それまでの次のインデックスの最上位ビットであり、前のステージからの累積した最下位ビットのマージを制御する。
【００６２】
コンバインは、既存の手法を用いたツリーとして実現されえるが、大きなファンインのために有利でありえるより小さい実現例も、それぞれの入力リクエストを巡回順序で検査し、もし入力が１なら対応する1ofNデータレールを駆動し、もし入力が０なら先に飛ばすリップリングリング回路を用いて提供される。この1ofNコードは排他的に保たれなければならない。コンバインのこのバージョンは、不規則なスループットおよびレイテンシ特性を有し、大きなファンインについてそのエリア節約のためだけに価値があるかもしれない。
【００６３】
さまざまな実施形態によれば、クロスバーは、一連の「move」命令を実行するために用いられ、これらのそれぞれはクロスバーの入力ポートおよび出力ポートを特定し、いくつかのトークンをそのリンクにわたって転送する。一つのそのような実施形態において、move命令は、入力ポート、出力ポート、およびリピートカウントを特定する。より具体的な実施形態によれば、これらmove命令の順序付けられたシーケンスは、２つのディスパッチ回路を介してパラレルに発行される。リピートカウントは、この実施形態が使用しえる単に一つのメカニズムである。
【００６４】
この実施形態によれば、第１ディスパッチ回路は、出力ポートおよびリピートカウントを特定された入力ポートに発信する。第２のものは、入力ポートおよびリピートカウントを出力ポートに発信する。すなわちmove命令は、対応するディスパッチについてのＳ制御として働く入力または出力ポートのいずれかで２つの方法でコピーされる。リピートカウントは、入力および出力ポートにローカルにアンロールされる（unrolled）。すなわち同じクロスバー制御は、カウントが使い尽くされるまで再発行される。２つのそのようなディスパッチ回路を有するディスパッチャ１５００の具体的な実施形態は、図１５に示される。
【００６５】
ディスパッチャの使用は、もしそれらがいずれかのポートを共通に持つならmoveがオリジナルのプログラムの順序で実行されることを確実にするが、もしそれらが異なるポートを参照するならそれらを順序からはずれて、またはパラレルに実行しえる。ディスパッチャはまた、一度に非常に大きな数のmove命令までスケールアップすることができる。これは、ディスパッチャにおける電力または帯域幅の浪費を防ぐための最適化として用いられえ、またオリジナルの命令ストリームを大きく圧縮できる。
【００６６】
本発明の他の実施形態は、メッセージを渡す通信相互接続としてのクロスバーの使用を促進する。この実施形態によれば、それぞれの入力ポートは、所望の宛先ポートナンバをTOチャネル上で提供し、これはクロスバーのＳ制御になる。それぞれの入力ポートは、所望の出力ポートを用いる許可をリクエストする。それぞれの出力ポートは、同じ出力へのアクセスについて競合する全ての入力からのリクエストの間で調停することによってＭ制御を生成する。オプションのFROMチャネルは、例えばクロスバーのＭ制御のコピーを含みえる出力と共に送られえる。このようなオプションは、例えば、センダーのアイデンティティを知ることが望ましいある種の通信プロトコルでは便利である。
【００６７】
入力毎の制御は、TOをＳにコピーし、それを1of1のリクエストチャネルreq[i, j]を意図された出力制御に送るスプリットバスのための制御として用いる。出力毎の制御は、リクエストを入力制御から集め、それらの間で調停する。調停の結果は、クロスバーのＭとして用いられ、またもし所望であるならFROMチャネルへコピーされえる。
【００６８】
ある実施形態によれば、リクエスト間で調停するＰウェイアービタは、先のセクションのcombineのようにバイナリツリーとして構築される。バイナリツリーのそれぞれのステージは、前のステージの左（例えば低いインデックス（lower indices））または右（例えば高いインデックス（higher indices））のいずれかの側からリクエストを受け取る。それは、勝者のＭＳＢについてチャネルをmergeのサイドツリーへ出力し、これはcombineのように勝者のインデックスを累積する。それはツリーの次のステージをリクエストするために1of1を送る。図１６は８ウェイアービタのためのツリー構造１６００を示す。
【００６９】
アービタの具体的な実施形態によれば、アービタのそれぞれのステージについての回路は、準安定性を含む。ＣＳＰは以下の通りである。
【００７０】
【数２】
2005516508.tif 000004
【００７１】
ここでL[0..1]はトリガ入力、Ｔはトリガ出力、Ａは調停結果である。図１７は、この振る舞いをする回路１７００のある実現例を示す。この実施形態によれば、出力リクエストは、入力リクエストのＯＲを取ることによってなされ、準安定ではない。1of2 の側のＡ出力だけが、実際の調停および準安定フィルタを用いる。このアービタツリーは、わずかに公平であり、もし競合するリクエストが時間的に充分間隔が空くならファーストカムファーストサーブとして働く。もし競合するリクエストがもっと速く来るなら、全てのリクエストがサービスされるが、必ずしも厳密に公平なレートではない。
【００７２】
さらなる実施形態によれば、クロスバーの調停された制御は、デッドロック状態を避けるアービタによって促進される。上述のようにそのようなアービタによって制御されるクロスバーは、これに限定されないがここで説明されたようなものを含む任意のタイプのクロスバーでありえる。
【００７３】
入力ポートＡが出力ＣそれからＤに行こうとし、他の入力ポートＢが出力ＤそれからＣに行こうとしていると仮定する。リクエストおよび調停チャネルのスラック（slack）のために、遅延非敏感タイミングモデルにおいてはＡがＤを獲得し、ＢがＣを獲得する。しかしＡがＣに先に送ろうとし、ＢはＤに先に送ろうとする。よってシステムはデッドロックに陥る。
【００７４】
よって具体的な実施形態によれば、「スラック」が取り除かれることによって、入力は、以前の者がその調停を獲得するまで、他のリクエストを作らない。これは、入力が調停に勝つとき、出力ポートによって入力ポートに返される「グラント」トークン（例えば1of1チャネル）を導入することによってなされる。このメカニズムは、入力が１つ以上の未決定のリクエストを作ることを防ぐ。
【００７５】
ある実現例によれば、グラントは、出力のＭからコピーされたそのＳ制御および入力のＳからコピーされたそのＭ制御を持つ小さいクロスバーを介して返される。出力Ｒの1of1データチャネルは、入力のスプリットバスに与えられる。入力側は、単一のグラントトークンで始まる。図１８は、このグラントスキームを用いるクロスバーのための調停された制御を実現するアービタ１８００を示す。
【００７６】
本発明のグラントクロスバーはまた、有用な順序付け関係を確立するように動作可能である。入力があるデータを出力Ｂに送り、それからデータが準備できているという通知を出力Ｃに送ると仮定する。もしＣがそれからそれをＢから読むなら、それはＡが書いた値を得るだろうが、それはＡのＢへの通信が調停に最初に勝ったからである。これは多くのバスプロトコルによって要求される生産者−消費者順序付けモデルを満足する。
【００７７】
本発明の他の実施形態によれば、このようなグラントクロスバーを用いることの代替物が提供される。一般に、デッドロックを避けるためには、リクエストされたのと異なる順序で調停が獲得されることを避ける必要がある。これを行う一つの方法は、１またはそれより少ない合計スラックを持つリクエスト／アービタ回路を実現することによって、第１のものがグラントされるまで第２のリクエストがいつもブロックされるようにすることである。これはグラントクロスバーの必要をなくし、より小さくなりえる。しかしこのゼロスラック設計は、スループットを減らし（なぜなら回路は、他の始まっているリクエストとパラレルにプリチャージできないからである）、ふつうのパイプライン化された構成単位の代わりに、要素の異なるゼロスラック実現例を要求する。グラントクロスバーは、より多くのパイプライン要素で構築されていても、実効的にはパイプラインが１スラックを持つようにする一つの方法である。
【００７８】
典型的なシステムにおけるトランザクションは、しばしば１語より大きい原子サイズ（atomic sizes）を有する。すなわちあるリクエストおよび調停について、多くのサイクルのデータが転送される必要がありえる。これは、本発明のある実施形態によって、「テール」ビットをメインクロスバーを通してデータと関連付けることによって達成されえる。この実施形態によれば、テールビットは、入力および出力ポートの両方によってサンプリングされ、単純な制御ユニットに与えられ、これは同じ制御値をテールビットが１になるまで繰り返す。他の実施形態によれば、データそのもの（例えばパケットにおいて）と関連付けられた、またはクロスバーを制御する制御データと共に来る情報を用いて単純なカウンタが採用されえる。理解されるように、これらは、恣意的なサイズのデータの転送を実現するために本発明の実施形態が利用しえるメカニズムの例に過ぎない。本発明の範囲はそのようには限定されるべきではない。
【００７９】
本発明の具体的な実施形態によって設計されたリクエスト／調停回路は、「パケット」だけに関心があり、受け取られた制御値にしたがってデータパスリンクをセットアップする。データパスクロスバーは、データの大きなブロックを転送し、それからテールビットを１にセットすることによって最後のサイクルの後にリンクを解放できる。図１９は、追加のリピータを制御入力上に持つデータパスクロスバー１９００を示す。代替の実施形態によれば、リピートカウントは、テールビットの代わりに用いられえる。しかしテールビットは、ハードウェアで実現するのがより簡単で、データパケット中で長さを特定することを禁止しない。
【００８０】
本発明のさらなる実施形態によれば、２ウェイトランザクションを実現するために２つの異なるクロスバーデータパスが、単一の調停制御回路を用いて制御される。そのような実施形態によれば、入力および出力の1of2チャネルLTYPEおよびRTYPEがそれぞれのポートについて本発明によって設計されたアービタ回路に追加される。もしLTYPEチャネルが１であるなら、通常のＳ／Ｍ制御がコピーされ、戻るトランザクションについての第２クロスバーのＭ／Ｓ制御になる。もしLTYPEチャネル０であるなら、第２クロスバーは用いられない。LTYPEチャネルの情報は、出力のRTYPEチャネルにコピーされ、それによりターゲットユニットは応答すべきかどうかを知る。この実現例は、１ウェイトランザクション（例えばストア）および２ウェイトランザクション（例えばロード、スワップ、リード−モディファイ−ライト）の混合をサポートする。より具体的な実施形態によれば、もし２つのクロスバーによって接続されるモジュールが排他的にマスタ（イニシエータ）またはターゲット（レスポンダ）であるなら、２つのクロスバーは非対称にサイズが決められ（例えば８×４リクエストクロスバーおよび４×８レスポンスクロスバー）える。そのような実施形態によれば、このスキームは、シェアドメモリブリッジを効率的に実現するのに用いられる。
【００８１】
上述の非対称回路の３つのタイプのいくつかの追加の例示的応用例がここで説明される。しかし本発明のクロスバー、ディスパッチャ、およびアービタは、さまざまな種類の応用例で用いられえ、したがって本発明の範囲は記載された応用例に限定されない。
【００８２】
このような例示的応用例において、Ｐウェイ命令発行およびＱパイプラインを持つスーパースカラＣＰＵは、ＰｘＱディスパッチャを用いて命令を正しいパイプラインに送り、一方でそれぞれのパイプラインへの順序付けを保持する。TO制御は命令からデコードされえる。
【００８３】
RISCスタイルのスーパースカラ非同期ＣＰＵに関する他の例示的実施形態において、クロスバーは、任意の実行パイプラインのＺリザルトを任意のレジスタにルーティングするために、または任意のレジスタからの読み出しを任意のパイプラインのＸおよびＹオペランドにルーティングするために用いられえる。それぞれのレジスタは、そのレジスタへの次のアクセスまでライトを遅延させることによって、任意のデータ依存リードが素速くバイパスされえるようにする。Ｚリザルトから従属ＸまたはＹオペランドへのレイテンシは、６トランジションまで小さくなりえ、リザルトクロスバー、レジスタそのもの、およびオペランドクロスバーについてそれぞれ２である。この低レイテンシバイパスの特徴は、追加のバイパス回路の必要をなくす。これらクロスバーの制御は、「move」制御スキーム上の変形を用いてパラレルRISC命令から生成されえる。この実現例は大きいが、大きな再順序付けを可能にし（すなわちそれはリザルト、オペランド、およびレジスタ上で予測された部分的順序付けを保持するだけである）、非常に広い発行設計（issue designs）に応じて拡張しえる。デュアルイシューＣＰＵでも、このレジスタファイルは、一度に短いバーストでしばしば２命令より多いものを行いえ、これはストールの後に追いつく助けになる。
【００８４】
それぞれの実施形態によれば、本発明によって設計された調停されたクロスバーは、チップ上でいくつかのモジュールを接続するのに用いられえる。いくつかの実施形態において、それぞれのモジュールは、１ウェイテール終端パケットを他のモジュールのそれぞれへ送りえる。いくつかのモジュールは、ストアを受け取り、ロード完了パケットを持つロードリクエストに応答しえるメモリでありえる。他のものは、Ｉ／Ｏインタフェースでありえ、特にフロー制御された双方向ＦＩＦＯでありえる。他のものは、Ｉ／Ｏ、メモリにアクセスし、または互いにパケットを送りえるＣＰＵまたはＤＳＰまたはＡＳＩＣでありえる。これらパケットは、キャッシュコヒーレンスプロトコルまたはハードウェアにサポートされたメッセージ転送を実現するために用いられえる。さらにＰＣＩのようなレガシーバスプロトコルもこのようなクロスバーを跨ぐことができ、これはそれが必要とされた順序付けの関係をサポートするからである。
【００８５】
さらなる実施形態によれば、本発明によって設計された調停されたクロスバーは、パケットスイッチングのためのスイッチファブリックとして働きえる。それぞれの入力パケットは、TO制御として用いるために抽出されえるインバンド宛フィールドを有する。パケットの長さは、テールビットシーケンスに変換されえる。FROM出力は、もし所望であるならパケット内に挿入し直しえる。さらに具体的な実施形態によれば、競合が存在するなら、ＦＩＦＯを全ての入力および出力に追加し、全てのシステムが過渡輻輳から回復するための大きなオーバースピードを有することが望ましい。
【００８６】
本発明は、その具体的な実施形態を参照して、特に示され記載されてきたが、開示された実施形態の形態および詳細の変更は、本発明の精神または範囲から逸脱することなくなされえることが当業者には理解されよう。例えば、上述のように、具体的な実施形態はここでは遅延非敏感ハンドシェークプロトコルを参照して記載されてきたが、本発明のさまざまな実施形態は、異なるタイプのタイミングが推定とされる遅延非敏感回路で提供される。
【００８７】
例えば、タイミング推定（timing-assumptions）は、追加の回路検証エンジニアリングの代償を払って、そうでなければ遅延非敏感回路をより速くかつ低電力にするために用いられえる。特定の回路のための最も良いタイミング推定は、回路のクリチカルパスおよび設計者が引き受けようとする追加の検証作業の量に依存する。特に興味があるのは、１つの４フェーズハンドシェーク（後述）、または外部ハンドシェーク間の１つのセル内の１つの内部パスに対してローカルなタイミング推定である。このクラスのタイミング推定が残りの遅延非敏感回路より長いクリチカルパスを持つ複雑なセルに適用されるとき、特に望ましい。これらタイミング推定は、４フェーズリターンをニュートラルハンドシェークに用い、一般に１ホットデータエンコーディングを用いる非同期回路に当てはまる。
【００８８】
一般に、本発明のさまざまな実施形態に適用される３つのタイプのタイミング推定が存在する。パルスタイミング推定がそうでなければ遅延非敏感な４フェーズハンドシェークに適用されるとき、データ有効性、制御有効性、アクノリッジ有効性のようなセットされた条件の全てが完了する。しかしハンドシェークのリセットフェーズは、完了されず、適切なタイミングマージンで起こると推定される。このスキームでは全ての信号、データ、制御、および出力チャネルからの全てのアクノリッジ信号は、ハンドシェークのリセットフェーズではチェックされず、例外的にたまにアクノリッジ信号が日和見主義的にデータのための良いプリチャージ信号として用いられる。場合によっては、出力データの完了のチェックを行ってもよい。このスキームは、いったんリンクがセットアップされると、データが計算されることから防ぐものは何もなく、チャネルがリセットフェーズを経ることから防ぐものは何もない。
【００８９】
黙示のデータニュートラル性タイミング推定が、そうでなければ遅延非敏感４フェーズハンドシェークに適用されるとき、出力チャネル上の計算されたデータは、セットされた指示で完了されるがリセットフェーズではない。全てのアクノリッジは全ての指示においてやはりチェックされる。このスキームは、いったん出力チャネルのアクノリッジがセットされると、いかなるイベントもデータチャネルのリセットフェーズを阻止しない。
【００９０】
一般に回路設計において干渉するオペレータはふつうであるが、遅延非敏感タイミングモデルによって禁止されている。干渉はグリッチを起こす。遅延非敏感回路設計においては、カットオフトランジスタが干渉を防ぐ。しかし適切なタイミングマージンで、回路設計者は、そうでなければ遅延非敏感回路においてグリッチのない動作を保証できる。
【００９１】
本発明によって設計された回路におけるこのようなタイミング推定の使用の具体的な例は、例示的である。本発明の具体的な遅延非敏感アプローチによって効率的に実現された１６から１６のポートの４ビットクロスバーは、サイクル当たり２０遷移を必要とする。しかし同様の機能性を持つクロスバー設計は、サイクル当たり１２遷移しか必要としない上述のタイミング推定で実現されえる。これは理論的には回路を６７％速くする。
【００９２】
図２０ａ〜２０ｃは、このようなサイクル当たり１２遷移のクロスバーを作るために、どのようにrouter_cell２０００、split_env２０２０、およびmerge_env２０４０の回路図がこれらタイミング推定で（上述の対応するものに比較して）変更されえるかを示す。svおよびlv信号は、ｌおよびｓチャネルの入力完了を表現する。rvおよびmv信号は、チャネルｒ上の出力データおよびチャネルｍ上の入力制御データの完了を示す。
【００９３】
パルスタイミング推定は、split_env ≡> router cell ≡> merge_envを通してのメインデータ転送において用いられる。これは、２つのNANDゲート完了、およびrvバス信号の除去を可能にする。それはまた、ＬおよびＳの到着からＳＥ（ＬおよびＳのアクノリッジ）への応答時間を９遷移から５に短縮する。干渉タイミング推定は、図中、veバス上で使用されるが、少し追加のコストを費やせば、split_envから制御を作ることもでき、これをveバスに渡し、干渉タイミング推定を除去できる。split_envおよびmerge_envを巡るバッファにおいては、黙示のデータニュートラル性タイミング推定（implied-data-neutrality timing assumption）は、パルスタイミング推定のブロックしないニュートラルに戻るという要求（non-blocking return-to-neutral requirement）を満足するために、かつ２つの1of4コードをサイクル当たり１２遷移にデータ完了するクリチカルパスを維持するために用いられる。このような回路になされえるタイミング推定の多くの小さいトレードオフが存在することが理解されよう。またこれら全ては本発明の範囲内である。
【００９４】
さらに、本発明のいくつかの具体的な実施形態が非同期回路設計のコンテキストで記載されてきたが、ここで記載されたクロスバーのイベントドリブンのアーキテクチャを、クロック信号の導入で同期環境に応用することも可能であり、本発明の範囲内である。そのような実施形態によれば、上述のものと同様のクロスバー回路アーキテクチャは、非同期４フェーズチャネルではなく、同期リクエストグラントＦＩＦＯの基本となるチャネルモデルと共に実現される。クロスバーは、やはり４つの独立したＦＩＦＯであるＬ、Ｓ、Ｍ、およびＲに基づくので、独立したフロー制御されたＦＩＦＯチャネルを持つクロスバーを実現することから来る全ての特性は、やはり当てはまる。差異は、データトランザクションがクロックエッジ境界にアラインされて始まることである。例えばこのようなアプローチは、単一のクロックドメイン同期システムにおいて望ましいが、これは同期から非同期へ、また逆に戻すことの要求から解かれるからである。
【００９５】
最後に、本発明のさまざまな利点、局面、および目的がさまざまな実施形態を参照して説明されてきたが、本発明の範囲はこのような効果、局面、および目的を参照して限定されるべきではないことが理解されよう。むしろ、本発明の範囲は、添付の特許請求の範囲を参酌して決定されるべきである。
【図面の簡単な説明】
【００９６】
【図１】ミューラーコンセンサス要素を示す図である。
【図２】Ｑウェイスプリットの図である。
【図３】Ｐウェイスマージの図である。
【図４】非同期クロスバーの簡略図である。
【図５】スプリットバスの第１部分の簡略図である。
【図６】スプリットバスの第２部分の簡略図である。
【図７】マージバスの第１部分の簡略図である。
【図８】マージバスの第２部分の簡略図である。
【図９】ルータセルの第１実現例の簡略図である。
【図１０】ルータセルの第２実現例の簡略図である。
【図１１】ルータセルの第３実現例の簡略図である。
【図１２】ルータセルの第４実現例の簡略図である。
【図１３】さまざまなクロスバー回路の任意のものと共に使用するためのディスパッチャの図である。
【図１４】ディスパッチャの出力コントローラ部分の図である。
【図１５】さまざまなクロスバー回路の任意のものと共に使用するためのディスパッチャの他の例の図である。
【図１６】さまざまなクロスバー回路の任意のものと共に使用するためのアービタの図である。
【図１７】アービタの出力コントローラ部分の概略図である。
【図１８】さまざまなクロスバー回路の任意のものと共に使用するためのアービタの他の例の図である。
【図１９】データパスクロスバーの図である。
【図２０ａ】本発明の具体的な実施形態によるさまざまなタイミング推定を用いたクロスバーを実現するのに用いられるクロスバー回路の図である。
【図２０ｂ】本発明の具体的な実施形態によるさまざまなタイミング推定を用いたクロスバーを実現するのに用いられるクロスバー回路の図である。
【図２０ｃ】本発明の具体的な実施形態によるさまざまなタイミング推定を用いたクロスバーを実現するのに用いられるクロスバー回路の図である。
【図１】
2005516508.tif 000006
【図２】
2005516508.tif 000007
【図３】
2005516508.tif 000008
【図４】
2005516508.tif 000009
【図５】
2005516508.tif 000010
【図６】
2005516508.tif 000011
【図７】
2005516508.tif 000012
【図８】
2005516508.tif 000013
【図９】
2005516508.tif 000014
【図１０】
2005516508.tif 000015
【図１１】
2005516508.tif 000016
【図１２】
2005516508.tif 000017
【図１３】
2005516508.tif 000018
【図１４】
2005516508.tif 000019
【図１５】
2005516508.tif 000020
【図１６】
2005516508.tif 000021
【図１７】
2005516508.tif 000022
【図１８】
2005516508.tif 000023
【図１９】
2005516508.tif 000024
【図２０ａ】
2005516508.tif 000025
【図２０ｂ】
2005516508.tif 000026
【図２０ｃ】
2005516508.tif 000027
【手続補正書】
【提出日】平成16年9月27日(2004.9.27)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
ルーティング制御情報に基づいて第１数の入力チャネルのうちの任意のものから、第２数の出力チャネルのうちの任意のものへデータをルーティングするよう動作可能なクロスバーであって、入力チャネルおよび出力チャネルのそれぞれの組み合わせは、複数のリンクのうちの１つを含み、前記クロスバーは、前記リンクのうちのそれぞれ上で前記データを決定的にルーティングし、それにより前記ルーティング制御情報によって表現された部分的順序付けを維持するよう動作可能なクロスバー回路を含み、異なるリンク上のイベントは非相関であるクロスバー。
【請求項２】
請求項１に記載のクロスバーであって、前記ルーティング制御情報は、独立したスプリット制御およびマージ制御チャネル上で前記クロスバーに送られるスプリット制御情報およびマージ制御情報を含み、前記クロスバー回路は、前記出力アドレスを前記入力アドレスに対応する前記スプリット制御チャネル上で、前記入力アドレスを前記出力アドレスに対応する前記マージ制御チャネル上で送ることによって前記部分的順序付けを維持するよう動作可能であるクロスバー。
【請求項３】
請求項１に記載のクロスバーであって、前記クロスバー回路は、
それぞれ前記入力チャネルのうちの１つに対応する前記第１数のスプリットバス、
それぞれ前記出力チャネルのうちの１つに対応する前記第２数のマージバス、および
前記スプリットバスのそれぞれを前記マージバスのそれぞれに接続する複数の中間チャネル
を含むクロスバー。
【請求項４】
請求項３に記載のクロスバーであって、それぞれのスプリットバスは、前記データを前記対応する入力チャネルから受け取る第１スプリット回路、およびそれぞれのスプリットセルが前記マージバスのうちの１つに対応する複数のスプリットセルを含むクロスバー。
【請求項５】
請求項３に記載のクロスバーであって、それぞれのマージバスは、前記データを前記対応する出力チャネルに送る第１マージ回路、およびそれぞれのマージセルが前記スプリットバスのうちの１つに対応する複数のマージセルを含むクロスバー。
【請求項６】
請求項３に記載のクロスバーであって、前記クロスバー回路は、前記データを少なくとも１つの前記リンク上で非同期で転送するよう動作可能であるクロスバー。
【請求項７】
請求項３に記載のクロスバーであって、前記少なくとも１つのタイミング推定は、パルスタイミング推定、干渉タイミング推定、および黙示のデータニュートラル性タイミング推定のうちの任意のものを含むクロスバー。
【請求項８】
請求項３に記載のクロスバーであって、前記クロスバー回路は、クロック信号の遷移を参照して前記リンクのうちの少なくとも１つの上で前記データを転送するよう動作可能なクロスバー。
【請求項９】
請求項３に記載のクロスバーであって、前記ルーティング制御情報が前記リンクのうちの特定のものに対応するときを示すよう動作可能なヒット回路をさらに備えるクロスバー。
【請求項１０】
請求項３に記載のクロスバーであって、前記クロスバー回路は、前記複数のリンクのうちの第１リンクの上で前記データの複数のユニットを連続的にルーティングするよう動作可能であるクロスバー。
【請求項１１】
請求項３に記載のクロスバーであって、前記クロスバー回路は、前記データを前記入力チャネルから前記出力チャネルへ前記決定的な方法で転送するよう全体として動作可能な複数の個別クロスバー回路を備えるクロスバー。
【請求項１２】
請求項１に記載のクロスバーであって、前記クロスバー回路は、前記データを対応する入力チャネルから受け取るようそれぞれ動作可能な前記第１数のスプリット回路、前記データを対応する出力チャネルへ送るようそれぞれ動作可能な前記第２数のマージ回路、および前記データを前記スプリット回路のうちの対応する１つから前記マージ回路のうちの対応する１つへ中間チャネルなしで直接に転送するようそれぞれ動作可能な複数のルータセルを備えるクロスバー。
【請求項１３】
請求項１２に記載のクロスバーであって、前記クロスバー回路は、前記データを少なくとも１つの前記リンク上で非同期で転送するよう動作可能であるクロスバー。
【請求項１４】
請求項１２に記載のクロスバーであって、前記クロスバー回路は、少なくとも１つのタイミング推定に基づいて、前記リンクのうちの少なくとも１つの上で前記データを転送するよう動作可能であり、前記少なくとも１つのタイミング推定は、パルスタイミング推定、干渉タイミング推定、および黙示のデータニュートラル性タイミング推定のうちの任意のものを含むクロスバー。
【請求項１５】
請求項１２に記載のクロスバーであって、前記クロスバー回路は、クロック信号の遷移を参照して前記リンクのうちの少なくとも１つの上で前記データを転送するよう動作可能なクロスバー。
【請求項１６】
請求項１２に記載のクロスバーであって、前記ルーティング制御情報が前記リンクのうちの特定のものに対応するときを示すよう動作可能なヒット回路をさらに備えるクロスバー。
【請求項１７】
請求項１２に記載のクロスバーであって、前記クロスバー回路は、前記複数のリンクのうちの第１リンクの上で前記データの複数のユニットを連続的にルーティングするよう動作可能であるクロスバー。
【請求項１８】
請求項１２に記載のクロスバーであって、前記クロスバー回路は、前記データを前記入力チャネルから前記出力チャネルへ前記決定的な方法で転送するよう全体として動作可能な複数の個別クロスバー回路を備えるクロスバー。
【請求項１９】
請求項１に記載のクロスバーであって、前記第１数はＰを含み、ここでＰは１以上の第１整数であり、前記第２数はＱを含み、ここでＱは１以上の第２整数であり、ＰおよびＱの両方が１に等しいのではないクロスバー。
【請求項２０】
命令ルーティング情報に基づいて第１数の入力チャネル上で受け取られた順序付けられた命令のストリームを、第２数の出力チャネルのうちの指定されたものへルーティングするよう動作可能なディスパッチャであって、前記ディスパッチャは、前記命令をそれぞれの出力チャネルへ決定的にルーティングし、それにより前記順序付けられたストリーム内で規定されたそれぞれの出力チャネルについての部分的順序付けを維持するよう動作可能であるディスパッチ回路を備え、異なる出力チャネル上の命令は非相関であるディスパッチャ。
【請求項２１】
請求項２０に記載のディスパッチャであって、前記クロスバー回路は、前記データを少なくとも１つの前記リンク上で非同期で転送するよう動作可能であるディスパッチャ。
【請求項２２】
請求項２０に記載のディスパッチャであって、前記ディスパッチ回路は、前記命令を前記入力チャネルから受け取り、前記命令を前記出力チャネルへ送るよう動作可能なクロスバーを備え、前記ディスパッチ回路は、前記クロスバーを制御するよう動作可能な入力制御回路および出力制御回路をさらに備えるディスパッチャ。
【請求項２３】
請求項２０に記載のディスパッチャであって、前記ディスパッチ回路は、少なくとも１つのタイミング推定に基づいて、少なくとも１つの出力チャネルへ前記命令をルーティングするよう動作可能であり、前記少なくとも１つのタイミング推定は、パルスタイミング推定、干渉タイミング推定、および黙示のデータニュートラル性タイミング推定のうちの任意のものを含むディスパッチャ。
【請求項２４】
命令ルーティング情報に基づいて第１数の入力チャネル上で受け取られた複数の命令を、第２数の出力チャネルのうちの指定されたものへルーティングするよう動作可能なアービタであって、前記アービタは、異なる入力チャネルで受け取られ同じ出力チャネルを特定する命令の間で調停し、前記異なる入力チャネルの任意のものが後続の命令を、前記異なる入力チャネル間での調停が完了するまで転送しないよう動作可能であるアービタ回路を備えるアービタ。
【請求項２５】
請求項２４に記載のアービタであって、前記クロスバー回路は、前記データを少なくとも１つの前記リンク上で非同期で転送するよう動作可能であるアービタ。
【請求項２６】
請求項２４に記載のアービタであって、前記ディスパッチ回路は、前記命令を前記入力チャネルから受け取り、前記命令を前記出力チャネルへ送るよう動作可能なクロスバーを備え、前記ディスパッチ回路は、前記クロスバーを制御するよう動作可能な入力制御回路および出力制御回路をさらに備えるアービタ。
【請求項２７】
請求項２６に記載のアービタであって、前記クロスバーは、前記命令を出力チャネルに決定的な方法でルーティングするよう動作可能なアービタ。
【請求項２８】
請求項２４に記載のアービタであって、前記調停回路は、前記同じ出力チャネルに対応するグラントトークンを調停ウィニング入力チャネルに送ることによって、前記アービタのデッドロックを防止するよう動作可能なグラント回路を備えるアービタ。
【請求項２９】
請求項２４に記載のアービタであって、前記調停回路はまた、前記入力チャネルから前記命令を受け取り、前記命令を前記出力チャネルへ送るよう動作可能な第１クロスバーを備え、前記調停回路は、前記命令ルーティング情報から第１スプリット制御情報および第１マージ制御情報を生成することによって前記第１クロスバーを制御するよう動作可能な入力制御回路および出力制御回路をさらに備え、前記調停回路はまた、第２スプリット制御情報および第２マージ制御情報に応答して前記出力チャネルの任意のものから前記入力チャネルの任意のものへデータを転送するよう動作可能な第２クロスバーを備え、前記第２スプリット制御情報は、前記第１マージ制御情報から導出され、前記第２マージ制御情報は、前記第１スプリット制御情報から導出されるアービタ。
【国際調査報告】
2005516508.tif 000028
2005516508.tif 000029
2005516508.tif 000030