(57)【要約】【課題】システムの現在の性能をダイナミックに評価し、必要な場合個々のプロセッサの構造を更新してシステムの性能を改良することによって、マルチメディアプロセッサシステムの性能を改良するシステム及び方法を提供する。【解決手段】一実施形態はマルチプロセッサシステムで実行される方法を含み、これはプロセッサにインストールされた構成オブジェクトの現在のセットの性能を評価し、構成オブジェクトの好ましいセットを選択し、現在のセットの１以上の構成オブジェクトを置換して現在のセットが好ましいいセットであることを確認することを含んでいる。その方法は、ユーザの選択に応じて構成オブジェクトの性能を評価し、例えば好ましい構成オブジェクトのタイプにおいて単一化又は多様化を好むことができる選択可能な方法に応じて好ましい構成オブジェクトを選択できる。【選択図】図２
2006120160.tif 000002
【特許請求の範囲】
【請求項１】
データエントリを記憶するための複数のバッファロケーションを有するシフトバッファを設け、
前記シフトバッファ中のデータエントリのサブセットに対するイクジット条件を評価し、
前記データエントリのサブセットに対するイクジット条件結果を獲得し、
前記データエントリの前記サブセットに対するシフト数を決定し、前記シフト数は前記イクジット条件の評価中にデータエントリの各前記サブセットが前記シフトバッファ中でシフトされたバッファロケーションの数であり、
対応するイクジット条件結果に基づいて、前記シフトバッファから出力されるデータエントリを選択し、
イクジット条件の前記対応する評価の開始時に前記データエントリが記憶された第１のバッファロケーションと、前記選択されたデータエントリに対応する前記シフト数とに基づいて、前記選択されたデータエントリが記憶されているバッファロケーションを識別するステップを含むことを特徴とする方法。
【請求項２】
前記データエントリを受信し、それを前記シフトバッファへ記憶するステップをさらに含み、前記シフトバッファ中の前記データエントリの前記サブセットに対する前記イクジット条件の評価は、前記データエントリを受信及び記憶するよりも高いクロックサイクル数を取ることを特徴とする請求項１記載の方法。
【請求項３】
データエントリを記憶するための複数のバッファロケーションを有するシフタバッファと、
前記シフトバッファに結合されたイクジット条件論理部と、
前記シフトバッファに結合されたシフト論理部と、
前記イクジット条件論理部と前記シフト論理部に結合されているシフトされたイクジット条件論理部とを具備し、
前記イクジット条件論理部は、前記シフトバッファ中の前記データエントリのサブセットに対するイクジット条件を評価し、前記データエントリの前記サブセットに対するイクジット条件の結果を得るように構成され、
前記シフト論理部は、前記データエントリの前記サブセットのシフト数を決定するように構成され、前記シフト数は前記イクジット条件の評価中にデータエントリの各前記サブセットが前記シフトバッファ中でシフトされたロケーションの数であり、
前記シフトされたイクジット条件論理部は、選択されたデータエントリに対して、イクジット条件の前記対応する評価の開始時に前記データエントリが記憶された第１のバッファロケーションと、前記選択されたデータエントリに対応する前記シフト数とに基づいて、前記選択されたデータエントリが記憶されているバッファロケーションを識別するように構成されていることを特徴とするシステム。
【請求項４】
前記イクジット条件論理部は、前記データエントリに対応するタイプを決定し、前記タイプに対応するトークンが受信されているか否かを決定することにより前記イクジット条件を評価するように構成されることを特徴とする請求項３記載のシステム。
【請求項５】
データエントリを記憶するための複数のバッファロケーションを有するシフトバッファを設け、
１以上のバッファロケーションおよび対応するデータエントリに対するイクジット条件を評価し、
データエントリが前記シフトバッファ中でシフトすることを可能とし、
前記対応するイクジット条件の評価によって対応する第１のデータエントリが前記シフトバッファから除去されるべきことが示されている第１のバッファロケーションを選択し、
前記第１のデータエントリが前記第２のバッファへシフトしているか否かを決定し、
前記第１のデータエントリがシフトされていない場合、前記第１のデータエントリを前記第１のバッファロケーションから出力し、前記第１のデータエントリがシフトされている場合、前記第１のデータエントリを前記第２のバッファロケーションから出力するステップを含むことを特徴とする方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明はシフトタイプバッファシステム及び方法に関する。特に、本発明は高速度のシフトタイプバッファによってデータエントリの処理効率を増加するためのシステム及び方法に関する。
【背景技術】
【０００２】
メモリバッファはしばしばデジタル回路で使用される。メモリバッファは例えば１つの装置から別の装置へ転送されるデータの一時的な保持領域として動作する。通信装置はしばしば非同期に或いは異なる速度でデータを処理する。その結果、１つの装置においてデータ送信の準備ができ、受信装置がデータ受信の準備がまだできていない場合、そのデータは受信装置がデータを受取る準備ができるまでバッファ中に一時的に記憶される。また、これらの装置間の通信が困難であり非効率的であり、中間バッファなしでは不可能なこともある。
【０００３】
最も一般てきなタイプのバッファは、ファーストイン・ファーストアウト（ＦＩＦＯ）である。ＦＩＦＯタイプのバッファにおいて、データエントリはそれがバッファに入った順序でバッファから出力／廃棄される。一般的なＦＩＦＯの構成は、どのデータエントリがバッファに入り、どのデータエントリが最も古く、次にどれがバッファから出力されるかを監視するために読取り及び書込みポインタを使用する。データエントリがバッファに入り、出力されるとき、読取り及び書込みポインタは新しく到来するデータエントリと次に出て行くデータエントリを示すために周期的な方法で動作する。
【０００４】
読取り及び書込みポインタの使用によって、ＦＩＦＯはデータエントリをバッファ中の１つのロケーション（位置）から別のロケーションへ移動する必要なく実行できる。しかし、読取り及び書込みポインタの使用は、バッファに入るデータエントリを全てのバッファロケーションについて利用可能にすることを要求する。書込みポインタはその後、どのロケーションがデータエントリを記憶することが可能かを決定する。従って単一の入力を全てのバッファロケーションに対して利用可能にするため、バッファに入力された単一のデータエントリが分配され、またファンアウトされなければならない。ファンアウト回路は深く、特に多数のロケーションを有するバッファでは入力データを伝播するために多くのクロックサイクルを必要とする。従って、読取り及び書込みポインタＦＩＦＯは高速度プロセッサと共に使用されるバッファの場合のようにタイミングが重要なアプリケーションには適していない。
【０００５】
タイミングが重要な場合、シフトタイプのバッファが使用される。シフトタイプのバッファにおいて、データエントリは最初に第１のバッファロケーションに記憶される。新しいデータエントリがバッファに入る準備ができたとき、既存のデータエントリは新しいデータエントリにスペースを与えるため、連続的なバッファロケーションをシフトされる。シフトタイプのバッファによって新しいエントリは読取り／書込みポインタＦＩＦＯよりも迅速にバッファ中に登録されるが、そのバッファ中のデータエントリは新しいデータエントリがバッファに入るとき、連続して新しいロケーションへシフト／進行する必要がある。
【０００６】
通常、データエントリは、あるイクジット（exit：出力）条件を満足する場合、バッファから出力される。デジタル回路及び装置がさらに複雑になると、データエントリのイクジット条件を評価するために必要な時間が著しく増加する。さらに、イクジット条件を満たすデータエントリを選択し、バッファから適切なエントリを除去するために付加的な時間を必要とする。あるシステムにおいて、データは符号化又は処理を必要とする。この結果、バッファから出力するためにデータエントリが必要とする時間は、データエントリをバッファ中に登録するために必要とする時間よりも非常に長い。例えばデータエントリをバッファに登録するのに１クロックサイクルしか必要ではないが、データエントリをバッファから出力するためのイクジット条件を評価するためには２以上のクロックサイクルがかかる可能性がある。
【０００７】
従来、イクジット条件を評価し、その後バッファからエントリを除去するために多くのサイクルを費やすとき、新しいエントリをバッファに記憶することを遅延させる必要がある。これは新しいエントリのためのスペースを取るために、１つの既存のエントリを出力する必要があるためである。従って、エントリの出力に２サイクルかかる場合、バッファに記憶されるために待機しているエントリは、それがバッファに記憶される前に、さらに２以上のサイクル待機しなければならない。この遅延はバッファの動作効率を低減する。
【０００８】
尚、バスやメモリなどの資源が複数のプロセッサ等のマスタにより共有されるシステムにおいて、複数の保持部を有し、各調停サイクルにおいて、最高位の優先度で調停対象となるマスタを特定する情報をリング状に接続された第１乃至第６優先度状態保持部に記憶し、第１乃至第６優先度状態保持部は、１回調停が行われる度に記憶内容を回転シフトされる技術が開発されている（例えば、特許文献１参照）。
【特許文献１】特開２００１−１８４２９９号公報
【発明の開示】
【発明が解決しようとする課題】
【０００９】
したがって、バッファエントリ処理の遅延を回避し、新しいバッファエントリの記憶を遅延させるイクジット条件の多サイクル評価により生じる遅延を防止するシステム及び方法の提供が望まれている。
【課題を解決するための手段】
【００１０】
上記１以上の課題は本発明の種々の実施形態により解決される。概略的に説明すれば、本発明はシフトバッファ内のデータエントリのシフトを監視するシステム及び方法を含んでおり、バッファからエントリを除去するとき、データエントリは評価され、これらのシフトが考慮に入れられる。バッファ中の各データエントリに対する評価されたイクジット条件は、その後、データエントリのシフトに等しい量だけ有効に“シフト”される。換言すると、特定のデータエントリに対するイクジット条件の評価は、もはやデータエントリを含んでいないバッファロケーションに関連されるより、データエントリに有効に従う。
【００１１】
本発明の一実施形態は、各クロックサイクル期間中にバッファ中の各データエントリのシフトを監視する。イクジット条件の評価及び適用が２クロックサイクルで実行され、データエントリが１サイクル置きにバッファに入力される一実施形態において、データエントリのシフト履歴は、１クロックサイクルの間保持される。最高の優先順位を有するデータエントリに対応するイクジット条件が最初に考慮される。一実施形態において、最も古いデータエントリは最高の優先順位を有している。
【００１２】
イクジット条件が評価された後、イクジット条件はデータエントリのシフト履歴に従って対応するデータエントリと整合される。データエントリが最後のクロックサイクル期間中にバッファ中でロケーションをシフトしなかった場合、特定のバッファロケーションに対するイクジット条件の結果は、バッファロケーションに現在記憶されているデータエントリに対応する。他方、データエントリが最後のクロックサイクル中にロケーションをシフトした場合、そのバッファロケーションに対するイクジット条件の結果は、次のバッファロケーションのデータエントリに対応する。イクジット条件が評価されていた間、データエントリがバッファ中で１ロケーションだけシフトすることは、これによって考慮される。
【００１３】
同様に、イクジット条件の評価及び適用が３クロックサイクルをとる場合、データエントリのシフト履歴は２クロックサイクルの間保持される。特定のデータエントリに対するイクジット条件の結果を得るために、イクジット条件の結果は、最後の２クロックサイクル期間中にデータエントリがデータバッファ中でロケーションをシフトした回数に等しい量だけシフトされる。類似の手順が任意の数のクロックサイクルに対して行われる。
【００１４】
別の実施形態において、バイパス論理部が、バッファイクジット条件が有効かどうかを決定するために使用される。バッファのイクジット条件が有効ではない場合、バッファは完全にバイパスされる。その代りに、バイパス論理部はバッファが空であるかどうか、及び全てのバッファのイクジット条件が真であるか否かを決定することができる。バッファが空であり、全てのバッファイクジット条件が真である場合、バイパス論理部はそのデータエントリを“ロケーション１専用”データエントリとして指定し、そのデータエントリを直接バッファ中の第１のロケーションへ転送する。その後、データエントリは次のクロックサイクル期間中にバッファを直接出る。全てのバッファのイクジット条件が真であるため、イクジット条件をさらに評価する必要はなく、第１のバッファロケーションは符号化又は処理のためのパイプラインステーションとして使用される。
【００１５】
他の実施形態において、データエントリを記憶するための複数のバッファロケーションを有するシフトバッファで方法が実行される。その方法は、１以上のバッファロケーション及び対応するデータエントリに対するイクジット条件を評価し、データエントリがシフトバッファ中でシフトすることを可能とし、対応するイクジット条件の評価によって対応する第１のデータエントリがシフトバッファから除去されることが示されている第１のバッファロケーションを選択し、第１のデータエントリが第２のバッファへシフトしているかどうかを決定し、第１のデータエントリがシフトしていない場合、第１のデータエントリを第１のバッファロケーションから出力し、第１のデータエントリがシフトしている場合、第１のデータエントリを第２のバッファロケーションから出力するステップを含んでいる。
【００１６】
本発明の他の実施形態は、データエントリを記憶するためのバッファロケーションを有するシフトバッファを提供する方法を具備している。さらに、この方法はシフトバッファ中のデータエントリのサブセットに対するイクジット条件を評価し、データエントリのサブセットに対するイクジット条件の結果を得る。バッファ中のデータエントリのロケーションを探知するため、データエントリのサブセットに対するシフト数が決定され、そのシフト数は、イクジット条件の評価期間中にデータエントリの各サブセットがシフトバッファ中でシフトされたロケーションの数である。その後、考慮されたデータエントリに対して、イクジット条件の結果は考慮されたデータエントリに対応するシフト数だけシフトされ、それによって考慮されたデータエントリに対応するイクジット条件結果を識別する。
【００１７】
本発明の更に別の実施形態は、システムに関するものであり、そのシステムはデータエントリを記憶するための複数のバッファロケーションを有するシフタバッファと、そのシフトバッファに結合されたイクジット条件論理部とを有し、イクジット条件論理部はシフトバッファ中のデータエントリのサブセットに対するイクジット条件を評価し、データエントリのサブセットに対するイクジット条件結果を得る。さらにシステムは、シフトバッファに結合されてデータエントリのサブセットのシフト数を決定するように構成されたシフト論理部を有し、そのシフト数はイクジット条件の評価期間中にデータエントリの各サブセットがシフトバッファ中でシフトされたロケーションの数である。最後に、システムはイクジット条件論理部とシフト論理部とに結合されているシフトされたイクジット条件論理部を有し、考慮されたデータエントリに対して、考慮されたデータエントリに対応するシフト数だけイクジット条件の結果をシフトし、それによって考慮されたデータエントリに対応するイクジット条件結果を識別するように構成されている。
【００１８】
多くの付加的な実施形態も可能である。
【００１９】
本発明の種々の実施形態は従来技術にまさる多くの利点を提供することができる。例えば前述の実施形態に関して、システム及び方法はイクジット条件が評価される速度まで速度を低下させる必要なく、高速度でバッファを動作することを可能にする。同様の利点は他のタイプのエージェント及びリソースを含むその他の実施形態でも与えられることができる。
【発明を実施するための最良の形態】
【００２０】
本発明の実施形態について以下に説明する。以下に説明するこれら実施形態は単なる例示であり、本発明を限定するものではなく、本発明を例示することを意図していることに注意すべきである。
【００２１】
概説すると、本発明はデータエントリが評価されている間にシフトバッファ内のデータエントリのシフトをモニタするシステム及び方法を含んでいる。バッファ中の各データエントリの評価されたイクジット条件は、その後、対応するデータエントリのバッファ内のシフトに対応する量（ロケーション数）だけ“シフト”され、それによってデータエントリが評価される間、データエントリのシフトを補償する。
【００２２】
本発明は異なるタイプのシステムに広く適用可能であるため、この開示において本発明の全ての可能な実施形態及び内容を含むことはできない。したがって、本発明の開示はマルチプロセッサ・コンピューティング・システムに実装される幾つかの例示的な実施形態に焦点を絞っている。これらの実施形態は本発明を限定するためのものではなく説明することを意図している。この説明を読むことにより、本発明の多数の別の実施形態は当業者に明白になるであろう。これらの全ての別の実施形態は特許請求の範囲の技術的範囲内に含まれる。
【００２３】
本発明の一実施形態は、各クロックサイクル期間にバッファ中の各データエントリのシフトをモニタすることにより実行される。１サイクル毎にデータエントリがバッファに入る間に、イクジット条件の評価及び適用が２クロックサイクルで実行される実施形態において、データエントリのシフト履歴は１クロックサイクルについて保持される。最高の優先順位を有するデータエントリに対応するイクジット条件は最初に考慮される。一実施形態において、最も古いデータエントリは最高の優先順位を有している。
【００２４】
イクジット条件の評価後、イクジット条件の結果はデータエントリのシフト履歴に従って対応するデータエントリと整合される。データエントリが最後のクロックサイクル期間中にバッファのロケーションをシフトしなかった場合、イクジット条件の結果は、その結果に関連したバッファロケーションに現在記憶されているデータエントリに対応する。他方で、データエントリが最後のクロックサイクル期間中にロケーションをシフトした場合、イクジット条件の結果は次のバッファロケーションに記憶されているデータエントリに対応する。イクジット条件が評価される間にデータエントリがバッファ中で１ロケーションだけシフトすることが考慮される。
【００２５】
同様に、イクジット条件の評価及び適用に３クロックサイクルかかる場合、データエントリのシフト履歴は２クロックサイクルの間保持される。特定のデータエントリのイクジット条件の結果を得るために、イクジット条件の結果は最後の２クロックサイクル期間中にデータエントリがデータバッファ中でロケーションがシフトされた回数に等しい数だけシフトされる。同様の処理が任意の数のクロックサイクルに対して行われる。
【００２６】
別の実施形態において、バイパス論理部は、バッファのイクジット条件が有効であるか否かを決定するために使用される。バッファのイクジット条件が有効でない場合、バッファは完全にバイパスされる。また、バイパス論理部は、バッファが空であるか否か、及び全てのバッファのイクジット条件が真であるか否かを決定する。バッファが空であり、全てのバッファのイクジット条件が真である場合、バイパス論理部は、そのデータエントリを“ロケーション１専用”のデータエントリとして指定し、そのデータエントリを直接バッファ中の第１のロケーションへ転送できる。その後、データエントリは、次のクロックサイクル期間中にバッファを直接出る。全てのバッファのイクジット条件が真であるため、イクジット条件をさらに評価する必要はなく、第１のバッファロケーションはその後、符号化又は処理が必要とする場合、パイプラインステーションとして使用される。
【００２７】
ここで説明する本発明の実施形態は、マルチプロセッサシステムでの構成に焦点を絞っている。前述したように、これらのマルチプロセッサシステムは本発明を限定するものではなく、単に本発明の特別な実施形態の説明を提供している。これらの実施形態が本発明を限定するものではなく説明にあるように、これらの実施形態と共に使用されている特別な専門用語は限定ではなく説明として考慮されるべきである。例えば幾つかの実施形態はバスに対するプロセッサのアクセスの制御を含んでいるが、これらの用語（例えばプロセッサ、コマンド、バス）は明細書及び特許請求の範囲、その他の箇所で使用されているより一般的な用語（例えばエージェント、アクセス、リソース）の例示である。
【００２８】
本発明の種々の実施形態は従来技術にまさる多くの利点を提供できる。例えば前述の実施形態は、データエントリがバッファ中に記憶され、又はバッファから除去される速度まで速度を低下させる必要がなく、高速度でバッファを動作させることができる。同様の利点は、他のタイプのエージェント及びリソースを含む他の実施形態でも提供できる。
【００２９】
図１は、従来技術によるバッファの入力においてファンアウト論理部を有する書込み／読取りポインタバッファを示す機能ブロック図を示している。バッファ125は、データ入力パス110を通してデータエントリを受信し、一時的にそのデータエントリを記憶し、そのデータエントリをデータ出力パス140へ出力するように構成されている。バッファ125は、書込みポインタおよび読取りポインタにより構成されたファーストイン・ファーストアウト（ＦＩＦＯ）待ち行列である。バッファ125は、次に利用可能なバッファロケーションを示すための書込みポインタと、バッファから出力される次に利用可能なバッファロケーションを示すための読取りポインタを使用することにより動作する。この結果、バッファ125中のデータエントリは、データが廃棄又はバッファ125から出力されるまで、同一のバッファロケーションに残っている。
【００３０】
この書込み／読取りポインタバッファ構造において、データ入力パス110を通して受信されたデータは、全てのバッファロケーションに対して利用可能とされる。データエントリが記憶される適切なバッファロケーションは、その後、書込みポインタユニット120を用いて選択される。書込みポインタユニット120は、信号をバッファロケーションの１つへ指定し、それによってデータエントリをそのロケーションに記憶させる。残りのバッファロケーションは、先行してそこに記憶された値を単に保持する。
【００３１】
マルチプレクサ135は、バッファから除去するように選択されたバッファロケーションを選択し、そのロケーションのデータエントリを、データ出力パス140を通して出力するように構成されている。データパスは、バッファ125の各エントリからマルチプレクサ135まで存在する。適切なバッファロケーションは、マルチプレクサ135が読取りポインタユニット130から受信する信号に従って選択される。読取りポインタユニット130は、データの優先順位（例えばファーストイン・ファーストアウト優先順位）及び／又は任意の他の適用可能なイクジット条件に従って選択するバッファロケーションを決定できる。
【００３２】
データを全てのバッファエントリに対して利用可能にするため、ファンアウト論理部115のようなファンアウト論理部が一般に使用される。ファンアウト論理部115は、データ入力パス110に供給されたデータ信号が、一般に全てのバッファロケーションの論理部を駆動するために十分な強さがないため必要とされる。したがって、データ信号は、１以上の演算増幅器（ｏｐ−ａｍｐｓ）又はインバータを通過し、バッファロケーションへ分配（ファンアウト）される前に信号が増幅される。ファンアウト論理部は、分配されたバッファ構造がより高速度であるため、幾つかのバッファにより作られる。
【００３３】
従って、ファンアウト論理部115は、単一のデータエントリを受信し、そのデータエントリをバッファ125の全てのロケーション（図１の例で示されているロケーション１−４）に供給するように構成されている。ファンアウト回路は、特にバッファが多数のエントリを有する場合、処理に対して付加的な時間遅延を導入する。この遅延は、演算増幅器／インバータの信号処理により生じる。実行時間が重要なアプリケーションにおいて、このタイプの読取り／書込みポインタバッファは、容認できない。したがって、バッファの速度が重要である場合、別のバッファ構造を使用することが望ましい。
【００３４】
図２は、本発明の一実施形態に係り、バッファからのデータ出力を制御するためのイクジット条件論理部及びシフト論理部を有するシフトバッファを描いた機能ブロック図を示している。バッファ210は、データ入力パス215を介してデータエントリを受信し、一時的にそのデータエントリを記憶し、そのデータエントリをデータ出力パス240へ出力するように構成されている。バッファ210は、バッファの第１のロケーション（ロケーション１）に全ての受信されたデータエントリを最初に記憶するように構成されている。データエントリは、その後、新しいエントリがバッファに記憶されたとき、バッファを通して“下方に”（例えばロケーション１からロケーション２へ、又はロケーション２からロケーション３へ）シフトされる。バッファ210は、データをバッファへ入力するための１つの主要なデータパスを有するため、１つの入力信号を多数のバッファロケーションへ分配するためのファンアウト論理部は必要としない。これは実行時間を著しく短縮する。
【００３５】
イクジット条件論理部225は、バッファ210中のデータエントリをモニタするよう構成されている。イクジット条件論理部225は、データエントリに対応するイクジット条件をモニタするようにも構成されている。イクジット条件論理部225は、１以上のデータエントリのイクジット条件を評価し、このイクジット条件の評価に基づいて、データエントリが存在する場合、どのデータエントリをバッファ210から除去してマルチプレクサ235を介して出力するかを決定する。
【００３６】
一実施形態において、バッファ210と支援論理は、マイクロプロセッサシステムの一部である。この実施形態において、バッファ210はバスに接続され、このバスはプロセッサに接続されている。バッファ210は、この実施形態において、プロセッサの命令又はデータを一時的に記憶し、それらの有効性を示すプロセッサ信号に応答して、その命令又はデータをプロセッサへ転送するように構成されている。
【００３７】
一実施形態において、バッファ210からエントリを受信するためのスレーブ装置の有効性を示すためにトークンが使用される。この実施形態において、１６個の異なるタイプのトークンが存在し、各スレーブ装置は、特定のタイプのトークンに対応してデータ／命令を処理する。この実施形態のトークンは、１６ビットのセットにより表され、それら全ては１に設定される１ビットを除いて、０に設定される。トークンのタイプはビットが１に設定されているか否かにより決定される。
【００３８】
この実施形態において、１６ビットはバッファ210に関連付けられている。“１”に設定されている各１６ビットは、対応するタイプのトークンの存在を示している。存在する各トークンは、システム中の対応するプロセッサが利用可能である。一実施形態において、イクジット条件論理部225は、バッファ中のデータエントリの優先順位（例えばＦＩＦＯ優先順位）と、目的（destination）プロセッサに対応するトークンが、そのプロセッサが利用可能かどうかを示しているかに従って、出力されるデータエントリを選択するように構成されている。
【００３９】
一実施形態において、バッファはそれぞれのクロックサイクルで新しいデータエントリを記憶し、１つのデータエントリを除去するように設計されている。場合によっては、イクジット条件論理部は、イクジット条件を評価し、バッファから除去される特定のデータエントリを選択するか否かを決定するために２以上のクロックサイクルを取る。イクジット条件が評価される時間中、データエントリはバッファ210の１以上のロケーションだけシフトされる。これはバッファ210がシフトタイプのバッファであり、新しいエントリがバッファに入るときにデータエントリがシフトされるためである。
【００４０】
上記例は、時には、イクジット条件を評価するために１以上のサイクルを必要とする間、それぞれのクロックサイクルでデータエントリを記憶／除去するように設計されているが、別の実施形態は可変の時間条件を有することができる。これら別の実施形態において、記憶／除去する連続的なデータエントリ間の所望の時間はさらに長くてもよく（例えば２以上のサイクル）、イクジット条件評価論理部は、データエントリを出力するためにイクジット条件を評価するため、さらに多くの時間がかかる（例えば２以上のサイクル）。
【００４１】
通常、イクジット条件評価論理部が適切なイクジット条件を評価するために、連続的なデータエントリの記憶／除去間の所望時間よりも長くかかるとき、次のデータエントリの記憶／除去は、イクジット条件が評価されるまで遅延される。これはシフトバッファを使用する通常のシステムで必要であり、その理由はデータエントリが１つのバッファロケーションから別のロケーションへシフトすることが可能な場合、バッファ論理部は、評価されたイクジット条件が示すデータエントリのロケーションが除去されるべきであることを知らないためである。したがって、データエントリのシフトは、バッファ論理部が除去すべきデータエントリを突き止めることができるように遅延されなければならない。このため、本発明の実施形態は、データエントリがシフトすることを許容し、データエントリのシフトを追跡する機構を構成し、それによって適切なエントリがバッファから出力される。
【００４２】
データエントリのバッファへの受信が遅延することを回避し、イクジット条件論理部225がそのタスクを終了することを可能とするため、シフト論理部220が導入されている。シフト論理部220は、バッファ210中の各データエントリのシフトを監視し、この情報をシフトされた条件論理部230へ提供するように構成されている。シフトされた条件論理部230は、イクジット条件論理部225からのイクジット条件の評価結果と、シフト論理部220からのシフト結果とを受信し、それらの結果を組み合わせるように構成され、特定のデータエントリがバッファから出力されるべきか否かを決定する。
【００４３】
一実施形態において、シフト条件論理部230は、以下のように動作する。サイクル０で、バッファロケーションｉにおけるデータエントリのイクジット条件の評価が開始される。イクジット条件の評価は、その後終了される。サイクル１で、データエントリが実際に選択される。データエントリがバッファから除去されるべきであることを評価が示した場合、シフト条件論理部230は、データエントリがバッファ内でシフトしているか否かを知る必要がある。データエントリがシフトしていない場合、バッファロケーションｉにおけるデータエントリは、バッファから除去される。データエントリがシフトしている場合、バッファロケーションｉ＋１のデータエントリがバッファから除去される。これは各クロックサイクルでバッファ中のデータエントリが０又は１バッファロケーションだけシフトすることを仮定する。
【００４４】
上記例は、データがバッファ中へのデータエントリの時間と、イクジット条件の結果の評価時間との時間差（クロックサイクル）が１クロックサイクル以上である場合をカバーするように拡張される。図３と、対応する説明は、シフトデータがイクジット条件データの評価と組み合わされる方法を示すものであり、さらに詳細な例を示している。出力のための特定のデータエントリを選択するとき、シフトされた条件論理部230は、適切な信号をマルチプレクサ235へ送信し、そのマルチプレクサ235は、適切なデータエントリを選択し、データ出力パス240を介してデータエントリを出力する。一実施形態において、シフト論理部220、イクジット条件論理部225、シフトされた条件論理部230は、１つのユニットで構成される。
【００４５】
一実施形態において、この同一のタイプの評価がバッファ中の各エントリに対して実行される。従って、各複数のバッファロケーションに対して、バッファロケーションのデータエントリの評価は１つのサイクルで開始され、次のサイクルで終了される。評価が終了するとき、最高の優先順位のデータエントリがバッファから出力される。最高の優先順位のデータエントリがバッファロケーションｉである場合、データエントリがシフトされているか否かに従って、バッファロケーションｉ又はバッファロケーションｉ＋１が除去される。
【００４６】
図３は、一実施形態によるシフト及びイクジット条件論理部を使用してシフトバッファからのデータ出力を制御する方法を示すフローチャートである。図３の方法は、バッファの各ロケーションのイクジット条件の評価で開始する（ブロック305）。各バッファロケーションの特定のデータエントリに対するイクジット条件の結果が“真”であるか否かが決定される（データエントリがバッファに存在させる準備ができていることを示唆している）。幾つかのエントリが真であると評価し、他は“偽である”と評価する。
【００４７】
ブロック310において、真であると評価されているバッファロケーションの中から、最高の優先順位を有するバッファロケーションが選択され、バッファから除去する準備が行われる。一般に、ＦＩＦＯは、シフトバッファの最も古いデータエントリが最高の優先順位を有し、これは“最下の”バッファロケーションに記憶されるデータエントリである。別の実施形態において、ブロック305と310は逆とされてもよく、このため、最高の優先順位のバッファロケーションが識別され、その後評価されてもよい。バッファロケーションの優先順位の識別と、対応するイクジット条件の評価は並列又は直列で実行してもよい。
【００４８】
その後、最高の優先順位のバッファロケーションにあったデータエントリが最後のクロックサイクル期間中にバッファ中のロケーションをシフトしているか否かについて決定される（ブロック315）。この実施形態において、イクジット条件の結果が評価されるのに２クロックサイクルかかり、新しいデータがバッファに入るのに１クロックサイクルかかると仮定されている。イクジット条件の結果がデータエントリに対して決定されている間に、データエントリはバッファの同一ロケーションに留まるか、（例えば別のデータエントリのための余地を作るため）バッファの次のロケーションにシフトさせることができる。
【００４９】
データエントリがバッファ中のロケーションをシフトしなかった場合、判定315は“ノー”分岐され、ブロック320において、最高の優先順位のバッファロケーションがマルチプレクサにより選択され、データエントリはバッファから出力される。他方、データエントリがバッファ中の次のロケーションにシフトした場合、判定315は“イエス”へ分岐され、ブロック325において、マルチプレクサは最高の優先順位のバッファロケーションの後の次のバッファロケーション（“最高の優先順位のバッファロケーション＋１”）を選択し、このバッファロケーションのデータエントリがバッファから出力される。このようにして、マルチプレクサはイクジット条件の評価が開始されたとき、最高の優先順位のバッファロケーションにあったデータエントリを含んでいるバッファロケーションを選択する。イクジット条件評価プロセス期間中にデータエントリがシフトしてもしなくても、適切なデータエントリがバッファから出力される。
【００５０】
バッファロケーションの１つがマルチプレクサによってバッファから出力されるように選択された後、処理ループはブロック310へ戻る。図面で示されているプロセスはバッファからデータエントリを除去するために連続的に反復され、それによってバッファに新しいエントリの余地を作る。上記例によれば、説明したプロセスはイクジット条件の評価の開始から、バッファからのデータエントリの除去まで２サイクルをカバーする。クロックサイクル毎に１の割合でデータエントリを記憶し、除去することが望ましいため、プロセスはそれが終了する前に再度開始される。あるいは、プロセスは１クロックサイクルだけ位相においてシフトされる２つの同時に実行するスレッドを有すると考えることができる。
【００５１】
図４は、一実施形態に係り、異なるクロックサイクルにおけるシフトバッファ、シフト論理部、及びイクジット条件論理部の状態を示している。各表において、第１の列（Ｄ）は、４つのバッファロケーションのそれぞれに記憶されるデータエントリを含んでおり、第２の列（Ｓ）は、各バッファロケーションに対応するシフト結果を表し、第３の列（Ａ）は、前のサイクルにおける各バッファロケーションに対応するイクジット条件の結果を表している。この例において、バッファは、４つのロケーションを有し、新しいデータエントリはクロックサイクル毎にバッファに入り、イクジット条件の評価は、終了するために２クロックサイクルかかることが仮定されている。
【００５２】
第１のクロックサイクル（Ｃ１）において、最初の２つのバッファロケーションはデータエントリＡとＢを含んでおり、第３のバッファロケーションは空であり、第４のバッファはデータエントリＣを含んでいる。サイクルＣ１において、イクジット条件の評価結果は、列Ａに示されていない。これらの結果が示される場合、イクジット条件の評価は、終了するために２クロックサイクルを必要とするので、これらは前のクロックサイクルにおけるバッファロケーションに記憶されたときのデータエントリに基づいている。同様に、シフト結果は、列Ｓに示されていない、それはこれらが前のクロックサイクルのバッファロケーションに記憶されたときのデータエントリに基づくためである。
【００５３】
第２のクロックサイクル（Ｃ２）において、データエントリＡおよびＢはバッファに入る新しいデータエントリＺの余地を作るためにシフトされる。結果として、バッファはＺ、Ａ、Ｂ、Ｃを含んでいる。シフト列は（先にＡとＢを含んでいた）第１及び第２のバッファロケーションの内容が（１で示されるように）シフトしていることを示している。シフト列はまた（前にＣを含んでいた）第４のバッファロケーションのデータエントリが（０で示されるように）前のクロックサイクルからロケーションをシフトしていないことも示している。
【００５４】
特定のデータエントリが出力するよう選択されるか否かを決定するために、最高の優先順位のバッファロケーションが最初に選択される。この例では下方のバッファロケーションが古いデータエントリと高い優先順位を有すると仮定される。したがって、最高の優先順位のバッファロケーションは、第２のバッファロケーションであり、これはサイクル１の列Ａにおいて１を有する（第３及び第４のバッファロケーションは０のイクジット条件結果を有し、それ故これらはバッファから除去される準備ができている）。列Ｓはその後、イクジット条件の評価が開始されるときに第２のバッファロケーションに記憶されているデータエントリがシフトしているか否かを決定するため検査される。したがって、列Ｓに１が存在し、イクジット条件評価に対応するデータエントリは矢印により示されているように、１バッファロケーションだけ下方にシフトされている。このデータエントリはデータエントリＢである。したがって、データエントリＢは、バッファから出力されるように選択される。
【００５５】
第３のクロックサイクル（Ｃ３）において、データエントリＺとＡはバッファの“下方”ロケーションにシフトされ、データエントリＹがバッファに入ることを可能にする。結果として、バッファはＹ、Ｚ、Ａ、Ｃを含んでいる。このシフト列は（先行してＺとＡを含んだ）第１及び第２のバッファロケーションの内容が（１により示されるように）シフトし、（先にＣを含んだ）第４のバッファロケーションのデータエントリが（０により示されるように）前のクロックサイクルからロケーションをシフトしなかったことを示している。前のサイクルＣ２では、イクジット条件評価の結果は、第２及び第４のバッファロケーションがバッファから除去される準備ができていることを示している。第４のバッファロケーションが選択され、それはこのロケーションが真のイクジット条件結果に対応し、“真”のイクジット条件を有するデータエントリ中で最高の優先順位を有するためである。第４のバッファロケーションに対するシフト条件指示が０であるため、イクジット条件評価結果に対応するデータエントリは、依然として第４のバッファロケーションに含まれている。したがって、このバッファロケーションのデータエントリは、バッファから出力されるように選択される。
【００５６】
第４のクロックサイクル（Ｃ４）において、データエントリＹ、Ｚ、Ａはバッファの“下方”ロケーションにシフトし、データエントリＸがバッファに入ることを可能にする。結果として、バッファはＸ、Ｙ、Ｚ、Ａを含んでいる。シフト列は４つの全バッファロケーションのデータエントリが（１により示される）前のクロックサイクルからシフトされたことを示している。サイクルＣ４において、イクジット条件評価の結果は、第１及び第３のバッファロケーションがバッファから除去される準備ができていることを示している。第３のバッファロケーションが選択され、それはこのロケーションが真のイクジット条件結果に対応し、“真”のイクジット条件を有するデータエントリ中で最高の優先順位を有するためである。列Ｓに示されているシフト条件が１であるため、次に下方のバッファロケーションのデータエントリ（データエントリＡ）がバッファから除去されるように選択される。
【００５７】
図５は、一実施形態による別のデータバイパス路を有するシフトバッファの機能ブロック図を示している。バッファ525は、データエントリが１以上のバッファイクジット条件を満足させることができるまでデータエントリを一時的に保持するように構成されている。データエントリがバッファのイクジット条件を満たすとき、データエントリは、マルチプレクサ530によってバッファを出るように選択される。
【００５８】
一実施形態において、復号論理部520は、バッファイクジット条件の評価を援助するように構成されている。例えばデータエントリがスレーブへのバスコマンドである場合、トークンシステムは、特定のスレーブが新しいバスコマンドを受信するために利用可能であるかどうかを決定できるように設定される。プロセッサは共通のバス上でトークンをバッファに送信することができ、例えば、それによってスレーブが新しいバスコマンドを受信するために利用可能であるかどうかをバッファに通知する。この実施形態において、復号論理部520は、各スレーブの利用可能性を決定するため、各バスコマンドに関連する行先アドレスを対応するトークンに変換するために使用される。同様に、符号論理部535は、バスコマンドがバッファから除去される前に、バスコマンドに関連するトークンをスレーブ行先アドレスに変換するために使用される。
【００５９】
バイパス論理部515は、データ入力パス510を介して新たなデータエントリを受信し、最初に、バッファイクジット条件が有効かどうかを決定するように構成されている。バッファイクジット条件がデータエントリを受信するスレーブの利用可能性に依存している実施形態において、バッファイクジット条件が有効でないインスタンスが存在する。例えば全てのスレーブがバッファからデータエントリを受取るのに利用可能である場合、バッファの単独のデータエントリは、直ちに適切なプロセッサへ送信される。あるいは、バッファイクジット条件を単にディスエーブルすることも可能である。
【００６０】
バッファイクジット条件が効力をもたない場合、バイパス論理部515は、データエントリをバイパス路555へ導き、バッファ525と復号論理部520及び符号化論理部535をバイパスし、不必要な処理を避けるように構成される。
【００６１】
バッファイクジット条件が有効である場合、バイパス路555は使用されない。しかしながら別のバイパス路が存在する。バイパス論理部515は、バッファ525が空であるか否か、及び全てのバッファイクジット条件が真であるか（例えば全てのトークンが真であるか）否かを決定するように構成されている。バッファ525が空であり、全てのバッファイクジット条件が真である場合、バイパス論理部515は、データエントリを“ロケーション１専用”データエントリとして指定し、そのデータエントリを復号論理部520へ送るように構成されている。復号論理部520による復号後、そのデータエントリはバッファの第１のロケーションに進み、その後バイパス路550を通ってマルチプレクサ530へ直接進行する。データエントリは、最終的に符号化論理部535を通過し、データ出力パス540を介して出力される。全てのバッファイクジット条件が真であるため、イクジット条件は評価する必要がなく、第１のバッファロケーションは、パイプラインステーションとして使用される。
【００６２】
最後に、バッファ525が一杯になると、又は全てのバッファイクジット条件が真ではない（例えば幾つかのトークンは真ではない）場合、バイパス論理部515は、データエントリを通常のパス上でバッファ525を介して送信する。即ち、データエントリは、ロケーション１でバッファに入り、上記のように、対応するバッファイクジット条件が満たされるまでそのバッファに留まる。
【００６３】
図６は、一実施形態による方法を示すフローチャートである。この方法において、データエントリがシフトバッファに入るか否かが決定され、それに続いて第１のデータバイバス路と第２のデータバイパス路のいずれをたどるかが決定される。
【００６４】
処理はブロック600で開始し、ブロック610で新しいデータエントリが受信される。その後、バッファをイクジットするためのイクジット条件が有効かどうか決定ブロック615で決定される。イクジット条件が有効でない場合、決定ブロック615は“ノー”へ分岐し、ブロック630において、バッファ及び条件評価がバイパスされる。この後、処理はブロック640へ進み、ここでデータエントリはバッファから出力される。その後、処理はブロック699で終了する。
【００６５】
決定ブロック615に戻り、イクジット条件が効力を有する場合、決定ブロック615は“イエス”へ分岐され、（決定ブロック620において）全てのイクジット条件が真であり、バッファが空であるか否かの別の決定が行われる。全てのイクジット条件が真であり、バッファが空である場合、決定ブロック620は“イエス”へ分岐され、データエントリは、第１のバッファロケーションに記憶され、（ブロック635で）次のクロックサイクルにおいてバッファから出力されるように指定される。データエントリがバッファに入る前に全ての条件が真であるため、イクジット条件を再検査している間、データエントリをバッファ中に留まらせる必要はない。
【００６６】
決定ブロック620に戻り、全てのイクジット条件が真ではないか、或いはバッファが空ではない場合、決定ブロック620は“ノー”へ分岐される。ブロック625において、データエントリは、バッファを通る通常のパスの通過を開始する。即ち、データエントリはそれがイクジット条件を満たすまでバッファ中に保持される。処理はブロック640へ継続し、ここでデータエントリはバッファから出力される。処理は次にブロック699で終了する。
【００６７】
本出願の説明は、マルチプロセッサ・コンピューティング・システムに関連して本発明を説明したが、本発明はさらに広く応用可能であり、種々の他のコンテキストで使用可能である。したがって、この開示は本発明をマルチメディア・ゲーム・システムの分野に限定するものではない。
【００６８】
ここで使用されている“コンピュータ”及び“コンピュータシステム”と言う用語は、ここで説明した機能を実行することができる任意のタイプのデータ処理システムを含むことを意図している。ここで使用される“コンピュータにより読取り可能な媒体”は、コンピュータにより実行することのできるプログラム命令を記憶することができる任意の媒体を指しており、フロッピー（登録商標）ディスク、ハードディスクドライブ、ＣＤ−ＲＯＭ、ＤＶＤ−ＲＯＭ、ＲＡＭ、ＲＯＭ、ＤＡＳＤアレイ、磁気テープ、フロッピーディスケット、光記憶装置等を含むことができる。
【００６９】
当業者であれば、情報及び信号が任意の種々の異なる技術を使用して表されることを理解するであろう。例えば、上記説明を通して参照することのできるデータ、指令、コマンド、情報、信号、ビット、シンボル及びチップは、電圧、電流、電磁波、磁界又は粒子、光フィールド、又は粒子、或いは任意のそれらの組合せによって表される。
【００７０】
当業者は更に、ここで開示した実施形態に関連して説明した種々の例示的な論理ブロック、モジュール、回路、アルゴリズムステップが電子的ハードウェア、コンピュータソフトウェア又はその両者の組合せとして構成できることを認識するであろう。このハードウェアとソフトウェアとの交換可能性を明瞭に示すため、種々の例示的なコンポーネント、ブロック、モジュール、回路、及びステップをそれらの機能に関連して一般的に説明した。このような機能がハードウェア又はソフトウェアのいずれとして構成されるかは、特定のアプリケーションと、システム全体に課された設計条件に依存する。当業者であれば、各特定のアプリケーションに対して、説明した機能を種々の方法で実行できるが、このような実装の決定は、本発明の技術的範囲からの逸脱するものとして解釈すべきではない。
【００７１】
ここで開示した実施形態に関連して説明した種々の例示的な論理ブロック、モジュール及び回路は、汎用目的のプロセッサ、デジタル信号プロセッサ（ＤＳＰＳ）、特定用途用集積回路（ＡＳＩＣ）、フィールドプログラム可能なゲートアレイ（ＦＰＧＡ）、又はその他のプログラム可能な論理デバイス、ディスクリート・ゲート又はトランジスタ・ロジック、ディスクリート・ハードウェア・コンポーネント、或いはここで説明した機能を実行するように設計された任意のその組合せによって構成又は実行される。汎用目的のプロセッサは、任意の通常のプロセッサ、コントローラ、マイクロコントローラ、状態マシン等であってもよい。プロセッサはまた、コンピュータ装置の組合せ、例えばＤＳＰと、マイクロプロセッサ、又は複数のマイクロプロセッサ、ＤＳＰコアと連結した１以上のマイクロプロセッサ、或いは任意の他のこのような構造として構成されることもできる。
【００７２】
ここで開示した実施形態に関連して説明した方法又はアルゴリズムのステップは、直接ハードウェア、プロセッサにより実行されるソフトウェアモジュール、又はその２つの組み合わせにより実施してもよい。ソフトウェアモジュールは、ＲＡＭメモリ、フラッシュメモリ、ＲＯＭメモリ、ＥＰＲＯＭメモリ、ＥＥＰＲＯＭメモリ、レジスタ、ハードディスク、取外し可能なディスク、ＣＤ−ＲＯＭ、又はこの分野の技術で知られているその他の形態の記憶媒体中に存在してもよい。例示的な記憶媒体はプロセッサに結合され、このようなプロセッサは情報を記憶媒体から読み出し、そこに情報を書込むことができる。あるいは、記憶装置はプロセッサに一体化してもよい。プロセッサ及び記憶媒体は、例えばＡＳＩＣ中に配置されていてもよい。ＡＳＩＣはユーザ端末に配置されてもよい。あるいは、プロセッサ及び記憶媒体はユーザ端末中にディスクリートなコンポーネントとして設けられていてもよい。
【００７３】
上記実施形態の説明は、当業者が本発明を製造又は使用することを可能とするために行った。これらの実施形態に対する種々の変形は当業者には容易に明白であり、ここに規定されている一般原理を本発明の技術的範囲を逸脱せずに他の実施形態に応用することができる。従って本発明は、ここで示した実施形態に限定されることを意図するものではなく、ここで開示した原理及び優れた特徴と一貫する最も広い技術的範囲に従う事が意図されている。
【００７４】
本発明により与えられる効果及び利点を特定の実施形態に関して説明した。これらの効果及び利点、ならびに行われ又は更に明白にされるその他のエレメント又は限定は、特許請求の範囲に記載された任意又は全ての臨界的で必要とされる、又は基本的な特徴として解釈されるべきではない。ここで使用されている用語“具備する”、“具備している”又は任意の他のその変形は排他的な意味ではなく、これらの用語に付随するエレメント又は限定を排他的ではなく、含むものとして解釈されることを意図している。従って、システム、方法、又は、１組のエレメントを含むその他の実施形態は、これらのエレメントだけに限定されることを意図するものではなく、記載されていないか、又は請求された実施形態に固有ではないその他のエレメントを含むことができる。
【００７５】
本発明を特定の実施形態を参照して説明したが、それらの実施形態は単なる例示であって、本発明の技術的範囲はそれらの実施形態に限定されないことを理解すべきである。前述の実施形態に対する多くの変形、変更、付加、改良が可能である。これらの変形、変更、付加、改良は特許請求の範囲に詳細にされている本発明の技術的範囲内に含まれると認識すべきである。
【００７６】
尚、本発明の課題は、次の方法、又はシステムによっても達成できる。
【００７７】
すなわち、請求項１について、
（２）前記方法は、マルチプロセッサシステムにおいて、前記データエントリを選択されたプロセッサへ通信するように構成されているバスにおいて行われることを特徴とする（１）記載の方法。
【００７８】
（３）前記イクジット条件の評価は、前記データエントリに対応するタイプを決定し、前記タイプに対応するトークンが受信されているか否かを決定するステップを含んでいることを特徴とする（１）記載の方法。
【００７９】
（４）前記シフトバッファから前記選択されたデータエントリを出力するステップをさらに含むことを特徴とする（１）記載の方法。
【００８０】
（５）前記イクジット条件が有効か否かを決定し、有効でない前記イクジット条件に応答して前記データエントリの前記受信及び前記シフトバッファへの記憶をバイパスするステップを含むことを特徴とする（２）記載の方法。
【００８１】
（６）全ての前記イクジット条件が真であるか否かを決定し、
前記シフトバッファが空であるか否かを決定し、
全ての前記イクジット条件が真であり、前記シフトバッファが空であることに応答して、前記第１のバッファロケーションに前記データエントリを記憶し、
全ての前記イクジット条件が真であり、前記バッファが空であることに応答して、前記第１のバッファロケーションから直接前記データエントリを前記バッファから出力するステップをさらに含むことを特徴とする（５）記載の方法。
【００８２】
（７）前記選択されたデータエントリが記憶されている前記バッファロケーションの識別は、前記第１のバッファロケーションの数と、前記選択されたデータエントリに対応する前記シフト数とを加算するステップを含むことを特徴とする（１）記載の方法。
【００８３】
（８）前記選択されたデータエントリは、前記バッファ中で最高の優先順位を有することを特徴とする（１）記載の方法。
【００８４】
請求項３に関して
（９）前記シフトバッファに結合されたプロセッサバスをさらに具備し、前記プロセッサバスはマルチプロセッサシステムにおいて前記データエントリを選択されたプロセッサへ通信するように構成されていることを特徴とする（３）記載のシステム。
【００８５】
（１０）前記選択されたデータエントリをバッファから出力するように構成されたマルチプレクサをさらに具備することを特徴とする（３）記載のシステム。
【００８６】
（１１）前記シフトバッファは、前記データエントリを受信し、前記シフトバッファ中へ記憶するようにさらに構成され、前記イクジット条件論理部は、イクジット条件を評価するために前記バッファが前記データエントリを受信及び記憶するよりも高いクロックサイクル数を取ることを特徴とする（３）記載のシステム。
【００８７】
（１２）  バイパス論理部をさらに具備し、前記バイパス論理部は、
前記イクジット条件が有効か否かを決定し、
有効でない前記イクジット条件に応答して、データパスで前記データエントリをバイパスして送信し、それによってデータエントリを受信及び記憶するバッファをバイパスするように構成されていることを特徴とする（１１）記載のシステム。
【００８８】
（１３）  バイパス論理部をさらに具備し、前記バイパス論理部は、
全ての前記イクジット条件が真であるか否かを決定し、
前記シフトバッファが空であるか否かを決定し、
全ての前記イクジット条件が真であり、前記シフトバッファが空であることに応答して、前記第１のバッファロケーションに前記データエントリを記憶し、
全ての前記イクジット条件が真であり、前記バッファが空であることに応答して、前記第１のバッファロケーションから直接的に前記データエントリを前記バッファから出力させるように構成されていることを特徴とする（１１）記載のシステム。
【００８９】
（１４）  前記シフトされた出力論理部は、前記データエントリがイクジット条件の前記対応する評価の開始時に記憶された第１のバッファロケーションの数と、前記選択されたデータエントリに対応するシフト数とを加算することによって、前記選択されたデータエントリが記憶された前記バッファロケーションを識別するように構成されていることを特徴とする（３）記載のシステム。
【００９０】
（１５）  前記選択されたデータエントリは、前記バッファで最高の優先順位を有していることを特徴とする（３）記載のシステム。
【００９１】
請求項５に関して
（１６）  前記方法は、マルチプロセッサシステムにおいて前記データエントリを選択されたスレーブへ通信するように構成されているバス中で行われることを特徴とする（５）記載の方法。
【００９２】
（１７）  前記イクジット条件の評価は、前記データエントリに対応するタイプを決定し、前記タイプに対応するトークンが受信されているか否かを決定するステップを含むことを特徴とする（５）記載の方法。
【００９３】
（１８）  前記シフトバッファから前記選択されたデータエントリを出力するステップをさらに含むことを特徴とする（５）記載の方法。
【００９４】
（１９）  前記データエントリを受信し、前記シフトバッファへ記憶するステップをさらに含み、前記シフトバッファ中の前記データエントリの前記サブセットに対する前記イクジット条件の評価は、前記データエントリを受信及び記憶するよりも高いクロックサイクル数を取ることを特徴とする（５）記載の方法。
【００９５】
（２０）  前記イクジット条件が有効か否かを決定し、
有効でない前記イクジット条件に応答して前記シフトバッファへのデータエントリの前記受信及び記憶をバイパスするステップをさらに含むことを特徴とする（１９）記載の方法。
【００９６】
（２２）  全ての前記イクジット条件が真であるか否かを決定し、
前記シフトバッファが空であるか否かを決定し、
全ての前記イクジット条件が真であり、前記シフトバッファが空であることに応答して、前記第１のバッファロケーションに前記データエントリを記憶し、
全ての前記イクジット条件が真であり、前記バッファが空であることに応答して、前記第１のバッファロケーションから直接的に前記データエントリを前記バッファから出力するステップをさらに含むことを特徴とする（１９）記載の方法。
【００９７】
（２３）  前記選択されたデータエントリが記憶されている前記バッファロケーションの識別は、前記第１のバッファロケーションの数と、前記選択されたデータエントリに対応する前記シフト数とを加算するステップを含むことを特徴とする（１０）記載の方法。
【００９８】
（２４）  前記選択されたデータエントリは、前記バッファ中で最高の優先順位を有することを特徴とする（１０）記載の方法。
【図面の簡単な説明】
【００９９】
【図１】従来技術によるバッファの入力においてファンアウト論理部を有する書込み／読取りポインタバッファを示す機能ブロック図。
【図２】一実施形態によるバッファからのデータの出力を制御するためのアービトレーション及びシフト論理部を有するシフトバッファを示す機能ブロック図。
【図３】一実施形態によるシフト及びイクジット条件論理部を使用してシフトバッファからのデータ出力を制御する方法を示すフローチャート。
【図４】一実施形態による異なるクロックサイクルにおけるシフトバッファ、シフト論理部、イクジット条件論理部の状態を示す説明図。
【図５】一実施形態による別のデータバイパス路を有するシフトバッファを示す機能ブロック図。
【図６】一実施形態によるシフトバッファに入るデータエントリがバッファに入るかどうか、第１のデータバイバス路又は第２のデータバイパス路のいずれをたどるかを決定するための方法を示すフローチャート。
【図１】
2006120160.tif 000003
【図２】
2006120160.tif 000004
【図３】
2006120160.tif 000005
【図４】
2006120160.tif 000006
【図５】
2006120160.tif 000007
【図６】
2006120160.tif 000008