(57)【要約】アービタ（１００）に対するプログラマブルアーキテクチャが描写される。アービタ（１００）は、回路の中で特にプログラマブルロジックで実現するために、公正、高速、かつ単純になるように設計されている。実施例において、アービタ（１００）は、Ｒｅｑｕｅｓｔｅｒ0，Ｒｅｑｕｅｓｔｅｒ1，．．．，Ｒｅｑｕｅｓｔｅｒn-1とラベル付けされるｎ個のリクエスタの間を調停する。アービタ（１００）は、ｎ個のコネクタを多重化することによって動作し、リクエストの動的な再優先順位付けを可能にする。したがって、Ｃｏｎｎｅｃｔｏｒ0，Ｃｏｎｎｅｃｔｏｒ1，．．．，Ｃｏｎｎｅｃｔｏｒn-1とラベル付けされるｎ個のコネクタは、ｎ個のリクエスタに全単射的に多重化される。コネクタからのリクエストは、その後、コネクタからリクエスタへの全単射割当てを変更することによって最優先順位付けされる。
2005518045.tif 000002
【特許請求の範囲】
【請求項１】
スイッチャーに接続される複数の信号間を調停するのに用いられる、コンピュータリソースと共に用いるスイッチャーであって、
前記コンピュータリソースに対するアクセスを規定する少なくとも１つのリクエストラインと、
前記少なくとも１つのリクエストラインを前記複数の信号のうちの少なくとも１つに接続する多重化装置と、を備え、
前記多重化装置は、前記コンピュータリソースに対するアクセスに関して前記複数の信号のうちの少なくとも１つを前記少なくとも１つのリクエストラインに周期的に再割当てすることを特徴とするスイッチャー。
【請求項２】
スイッチャーに接続される複数の信号間を調停するのに用いられるスイッチャーであって、
前記スイッチャーが前記複数の信号に接続されるように、前記スイッチャーに接続されるコンピュータリソースと、
複数のリクエストラインであって、前記複数のリクエストラインは前記コンピュータリソースに対するアクセスを支配し、前記複数のリクエストラインは優先順位の固定された順番で存在するようになっていることを特徴とする複数のリクエストラインと、
前記複数のリクエストラインを前記複数の信号に接続している多重化装置であって、前記多重化装置は前記複数の信号を前記複数のリクエストラインに周期的に再割当てし、前記コンピュータリソースに対するアクセスに関して前記複数の信号を再優先順位付けするようになっていることを特徴とする多重化装置と、を備えているスイッチャー。
【請求項３】
信号の数はリクエストラインの数に等しいことを特徴とする請求項１に記載のスイッチャー。
【請求項４】
コンピュータリソースはハードウェアリソースであることを特徴とする請求項１に記載のスイッチャー。
【請求項５】
前記ハードウェアリソースはバスであることを特徴とする請求項１に記載のスイッチャー。
【請求項６】
前記ハードウェアリソースはメモリコントローラであることを特徴とする請求項１に記載のスイッチャー。
【請求項７】
前記スイッチャーはプログラマブルハードウェア上に備わっていることを特徴とする請求項１に記載のスイッチャー。
【請求項８】
前記プログラマブルハードウェアは１つ又は複数のＦＰＧＡを備えていることを特徴とする請求項６に記載のスイッチャー。
【請求項９】
前記スイッチャーはＶＨＤＬでＦＰＧＡ上に符号化されていることを特徴とする請求項７に記載のスイッチャー。
【請求項１０】
前記スイッチャーはＶｅｒｉｌｏｇでＦＰＧＡ上に符号化されていることを特徴とする請求項７に記載のスイッチャー。
【請求項１１】
前記スイッチャーは単一のＡＳＩＣ上に備わっていることを特徴とする請求項１に記載のスイッチャー。
【請求項１２】
前記多重化装置は、前記コンピュータリソースに対する前記複数の信号の公正重み付けアクセスを保障するように、前記複数の信号を前記複数のリクエストラインに再割当てすることを特徴とする請求項１に記載のスイッチャー。
【請求項１３】
前記コンピュータリソースは小電圧差動信号伝送方式バスであることを特徴とする請求項１に記載のスイッチャー。
【請求項１４】
前記複数の信号は１つ又は複数のＰＯＳインターフェースを含むことを特徴とする請求項１２に記載のスイッチャー。
【請求項１５】
前記複数の信号はＣＰＵコントローラを含むことを特徴とする請求項１３に記載のスイッチャー。
【請求項１６】
前記複数の信号はフィードバック信号を含むことを特徴とする請求項１４に記載のスイッチャー。
【請求項１７】
コンピュータリソースに対するアクセスのために複数の信号間でリクエストを調停する方法であって、
前記コンピュータリソースは複数のリクエストラインに接続され、前記複数のリクエストラインは優先順位の降順に前記コンピュータリソースにアクセスし得るようになっていることを特徴とする方法であって、
前記複数の信号を前記複数のリクエストラインに割当て、前記複数の信号を割当てることに続いて、前記コンピュータリソースに対するアクセスを前記複数の信号の第１の信号に許可し、前記第１の信号は前記複数のリクエストラインの第１のリクエストラインに接続されており、
アクセスを許可することに応答して、前記複数の信号を前記複数のリクエストラインに再割当てすることにより、前記第１の信号は前記複数のリクエストラインにおける最低優先順位のリクエストラインに割当てられるようになっていることを備えている方法。
【請求項１８】
前記第１のリクエストラインは前記最低優先順位のリクエストラインと異なることを特徴とする請求項１６に記載の方法。
【請求項１９】
前記コンピュータリソースは高速バスであることを特徴とする請求項１６に記載の方法。
【請求項２０】
信号の数はリクエストラインの数に等しいことを特徴とする請求項１６に記載の方法。
【請求項２１】
前記信号の数は４つの信号に等しいことを特徴とする請求項１９に記載の方法。
【請求項２２】
前記４つの信号はＣＰＵアクセスラインを含むことを特徴とする請求項２０に記載の方法。
【請求項２３】
前記４つの信号は２つのＰＯＳラインを含むことを特徴とする請求項２１に記載の方法。
【請求項２４】
前記４つの信号はフィードバックラインを含むことを特徴とする請求項２２に記載の方法。
【請求項２５】
前記コンピュータリソースは小電圧差動信号伝送方式バスであることを特徴とする請求項２３に記載の方法。
【請求項２６】
再度の割当ては多重化装置で行われることを特徴とする請求項２４に記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、コンピューティング及びネットワーキングの分野に関し、より詳細には、多数リクエスト間で選定するのに用いられるアービトレーション方式に関する。
【背景技術】
【０００２】
リクエスト信号間での選定の問題は、電子工学、コンピューティング、及びネットワーキング技術に遍在し、従来技術は、前記信号間で調停するのに用いられる技術を十分に備えている。アービタは、バスリソース、共有メモリへのアクセス、ネットワーキング接続、データベーストランザクションを割り付けるのに用いられ、前記アービタは、ハードウェア回路として、プログラマブルロジックすなわち汎用ＣＰＵで実行するソフトウェアで実現される。
【０００３】
信号又はリソース間で調停するために、多数の方式が配備されている。多くの前記方式において、アービタに接続される様々なリクエスタはランク付けされ、リクエスト間で衝突する場合には、最も高い優先順位を有するリクエスタがアービタからの優先権を得る。方式の中には、リクエスタは静的なランクに固定されているものがある。その他には、順位付けは動的に改められるものがあり、幾つかのそのような方式は、各リクエストの後に順位付けを改める。
【０００４】
動的順位付け方式は、実現するには扱いにくいということがよくある。例えば、一組のリクエスタの優先順位が一組のｉｆ−ｔｈｅｎ−ｅｌｓｅステートメントによって支配されることを特徴とする方式を考える。例えば、アービタが以下の擬似コードで与えられる方式によって定義されていたと想定する。
【０００５】
If Requester0 then grant (Requester0)
Else if Resquester1 then grant (Requester1)
Else if Resquester2 then grant (Requester2)
Else if Resquester3 then grant (Requester3)
【０００６】
ここで、アービタが動的であること、すなわち、リクエスタの優先順位は動的に変更され得ることを想定する。上記コードは、新しい優先順位を適応させるように変更されなければならない。これは、アービタがＦＰＧＡのようなプログラマブルハードウェアで実現される場合には特に問題があり、結果として、アービタの実装が複雑かつ低速になる。
【発明の開示】
【課題を解決するための手段】
【０００７】
アービタのプログラマブル・アーキテクチャがこの中に描写される。アービタは、回路において、特にプログラマブルロジックにおいて実現するために公正かつ高速かつより単純であるように設計される。本発明の幾つかの実施例において、アービタは、多数のバス信号間で調停するのに用いられ、公正な方式を介して優先順位を様々なバス信号に割り付ける。この中に描写されるこれらの少なくとも幾つかの目的及び他の目的は、本発明の実施例によってかなえられる。
【０００８】
本発明に係る幾つかの実施例において、アービタは、例示するために、Ｒｅｑｕｅｓｔｅｒ0，Ｒｅｑｕｅｓｔｅｒ1，．．．，Ｒｅｑｕｅｓｔｅｒn-1とラベル付けされる、多数のリクエスタ間を調停する。幾つかの前記実施例において、アービタは、ｎ個のコネクタを多重化することによって動作し、リクエストの動的な再優先順位付けを可能にする。従って、ｎ個のコネクタは、Ｃｏｎｎｅｃｔｏｒ0からＣｏｎｎｅｃｔｏｒn-1にラベル付けされ、ｎ個のリクエストに全単射で多重化される。コネクタからのリクエストは、その後、コネクタからリクエスタへの全単射割当てを変更することによって再優先順位付けされる。
【０００９】
幾つかの前記実施例において、コネクタからリクエスタへの割当ては、変化し、リクエスタの優先順位は、それがアービタによる制御を認可された後、最低レベルに下げられることになる。認可が終わった後、全単射割当ては改められ、Ｃｏｎｎｅｃｔｏｒ  ｙはＲｅｑｕｅｓｅｔｅｒ  ｎ−２に割当てられ、残存するコネクタは、互いに有する優先順位のそれらの相対的順番を保存するためにＲｅｑｕｅｓｔｅｒ0からＲｅｑｕｅｓｔｅｒn-2に割当てられる。
【００１０】
非限定的な実施例において、アービタは、ネットワーキング装置において高速バスに対するアクセスを支配するのに利用される。例えば、アービタは、ＰＯＳライン及びＤＭＡコントローラによって高速バスに対するアクセスを支配する。幾つかの前記実施例において、高速バスは、小電圧差動信号伝送方式の形態を取り、全二重伝送で約１０Ｇｂｐｓ以上の速度で動作する。これら及び他の実施例は、さらに、この中で詳細に描写される。
【００１１】
この中に描写される本発明の実施例は、もっぱら例示のために与えられ、手段において本発明の範囲を限定するものではない。多くの選択肢及び同等の実施例が当業者にとっては明白である。
【発明を実施するための最良の形態】
【００１２】
アービタの説明
本発明の幾つかの実施例は、図１に例証されるような公正重み付けｉｔｒ  ｔａｔ方式（ａ  ｆａｉｒ  ｗｅｉｇｈｔｅｄ  ｉｔｒ  ｔａｔ  ｓｃｈｅｍｅ）を用いたアービタを含む。幾つかの実施例において、アービタ１００は、スイッチャー１０８内に存在し、多数コネクタ１０６をシステムソースに結合する。例えば、ｎ個のコネクタは、Ｃｏｎｎｅｃｔｏｒ0からＣｏｎｎｅｃｔｏｒn-1にラベル付けされる。非限定例として、スイッチャー１０８は、コネクタ１０６間のシステムバスに対するアクセスを調停するのに用いられる。アクセスがスイッチャー１０８及び／又はアービタ１００によって制御される他のリソースは、当業者にとっては明白である。
【００１３】
図２は、アービタ１００の内部動作を例証する。アービタ１００は、Ｒｅｑｕｅｓｔｅｒ0，Ｒｅｑｕｅｓｔｅｒ1，．．．，Ｒｅｑｕｅｓｔｅｒn-1にラベル付けされたｎ個のリクエスタ２００を処理し、アービタ１００及びスイッチャー１０８の利用により、コネクタ１０６によってアクセスされるリソースに優先順位を割り付ける。幾つかの実施例において、これらのリクエスタ２００は固定された優先順位を有する。非限定例として、固定された優先順位は、優先順位の降順であり、これは、次の擬似コードで表される。
【００１４】
If Requester0 then Grant (Requester0)
Else if Requester1 then Grant (Requester1)
Else if Requestern-1 then Grant (Requestern-1)
表１
【００１５】
幾つかの実施例において、また、アービタは、多重化装置、すなわちｍｕｘ２０２を含み、コネクタ１０６からのリクエストの動的な再優先順位付けを可能にする。動作中、ｍｕｘ２０２は、Ｃｏｎｎｅｃｔｏｒ0からＣｏｎｎｅｃｔｏｒn-1にラベル付けされたｎ個のコネクタ１０６をｎ個のリクエスタ２００に全単射的に割当てる。それによって、コネクタ１０６からのリクエストは、ｍｕｘ２０２の利用によって再優先順位付けされ、コネクタ１０６とリクエスタ２００の間の多重化された接続を再割当てする。
【００１６】
公正重み付けアービタ（Ｆａｉｒ  Ｗｅｉｇｈｔｅｄ  Ａｒｂｉｔｅｒ）の動作
アービタ１００の動作は、例によって示される。リクエスタ２００の相対的な優先順位が動的に改められることになることを考える。非限定例として、各許可の後、優先順位が改められることを想定すると、リクエスタの優先順位は、それがアービタ１００による制御を許可された後、最低レベルに下げられることになる。例えば、Ｒｅｑｕｅｓｔｅｒx｛（ｘ＃ｎ），ａｎｄ，ｗｉｔｈｏｕｔ  ｌｏｓｓ  ｇｅｎｅｒａｌｉｔｙ，ｘ＜＞（ｎ−１）｝が最新のドックサイクルで許可を獲得し、ＲｅｑｕｅｓｔｅｒxがＣｏｎｎｅｃｔｏｒyに接続されたことを想定する。認可が終わった後、ｍｕｘ２０２における全単射の割当ては改められ、ＣｏｎｎｅｃｔｏｒyはＲｅｑｕｅｓｔｅｒn-1に割当てられ、残存するコネクタ１０６は互いに有する優先順位のそれらの相対的順番を保存するためにＲｅｑｕｅｓｔｅｒ0からＲｅｑｕｅｓｔｅｒn-2に割当てられる。この中に描写されるようなアービタを用いると、コネクタ１０６の全ｎ！通りの可能性のある優先順位決定が実現され得る。
【００１７】
【特許文献１】米国出願０９／６７９，３２１
【特許文献２】米国出願０９／９１８，３６３
【００１８】
プログラマブルハードウェアにおける公正重み付けアービタの利用
この中に描写されるアービタ１００の具体例は、図３に例証される。図はスイッチャー３００を含み；非限定例として、スイッチャーは、発明者Ｊｕｎａｉｄ  Ｉｓｌａｍ，Ｈｏｍａｙｏｕｎ  Ｖａｌｉｚａｄｅｈ，及びＪｅｆｆｅｒｙ  Ｓである２０００年１０月３日に出願された特許文献１、及び発明者Ｊｕｎａｉｄ  Ｉｓｌａｍ，Ｈｏｍａｙｏｕｎ  Ｖａｌｉｚａｄｅｈ，及びＪｅｆｆｅｒｙ  Ｓである２００１年７月３０日に出願された特許文献２に描写されるネットワーキング装置の高速バックプレーンに利用されており、その全体を参照によって取り込んでいる。前記幾つかの例において、スイッチャー３００は、フィールドプログラマブルゲートアレー（ＦＰＧＡ）、他のプログラマブルハードウェア、又はＡＳＩＣ上で実現される（ＦＰＧＡの例では、スイッチャーは、非限定例としてＶｅｒｉｌｏｇ又はＶＨＤＬのようなハイレベル設計言語のコードとして実現される）。他の例は、当業者にとっては明白である。
【００１９】
図３に例証される例において、スイッチャー３００は、高速スタックバス３０２に対するアクセスを支配する。本発明に係る実施例において、高速バス３０２は、２つの小電圧差動信号（ＬＶＤＳ）バス３０４  ３０６を含んでいる。説明されている例において、ＬＶＤＳライン３０４  ３０６の各々は、１６ピンを有しており、６２２ＭＨｚの速度で動作し、結果として各ライン３０４  ３０６に対して以下の合計帯域幅を生じる。
【００２０】
６２２ＭＨｚ＊（１ｂｉｔ，ｆｕｌｌ−ｄｕｐｌｅｘ／ｐｉｎ）＊１６ｐｉｎｓ＝９．９５２Ｇｐｓ，ｆｕｌｌ−ｄｕｐｌｅｘ
【００２１】
また、図３は、４つの追加コネクタラインを例証しており、スイッチャー３００をＣＰＵコントローラに接続するＣＰＵライン３０８を含んでいる。非限定例として、コントローラは、ＧａｌｌｉｌｅｏTMＩｎｃ．製のもののような３２ビットＤＭＡコントローラである。前記例において、各ピンは１３３ＭＨｚのドック速度（ｄｏｃｋ  ｒａｔｅｓ）で動作する。従って、ＣＰＵライン３０８は次の帯域幅を有する。
【００２２】
１３３ＭＨｚ＊（１ｂｉｔ，ｆｕｌｌ−ｄｕｐｌｅｘ／ｐｉｎ）＊３２ｐｉｎｓ＝４．２５６Ｇｐｓ，ｆｕｌｌ−ｄｕｐｌｅｘ
【００２３】
アダー３００に接続される追加コネクタは、フィードバックライン３１０及び２つのＰＯＳインターフェース３１２  ３１４である。４つのリクエスタ、すなわちＣＰＵライン３０８、フィードバックライン３１０、及び２つのＰＯＳ接続３１２  ３１４は全て、ＬＶＤＳスタックバス３０２に対するアクセスのためにスイッチャー３００を介して競合する。公正重み付けアービトレーション方式は、スイッチャー３００にアービタ３１６を包含することによって実現される。内部的には、アービタ３１６は、４つのリクエスタ、Ｒｅｑｕｅｓｔｅｒ0，Ｒｅｑｕｅｓｔｅｒ1，Ｒｅｑｕｅｓｔｅｒ2，Ｒｅｑｕｅｓｔｅｒ3を含んでおり、スタックバス３０２に対するアクセスを許可する。リクエスタは優先順位付けされ、非限定例として、それらは擬似コードで表される次のように降順に優先順位付けされる。
【００２４】
If Requester1 then Grant (Requester0)
Else if Requester1 then Grant (Requester1)
Else if Requester2 then Grant (Requester2)
Else if Requester3 then Grant (Requester3)
表２
【００２５】
スイッチャー３００は、内部ｍｕｘを含んでおり、各許可の後に４つのコネクタ、すなわちＣＰＵコントローラ、ＰＯＳインターフェース、及びフィードバックラインをリクエスタに再割当てすることにより、最後のコネクタは、許可を受信するためにＲｅｑｕｅｓｔｅｒ3に割当てられ、残存するコネクタは、優先順位のそれらの相対的順番を保存するようにＲｅｑｕｅｓｔｅｒ0，Ｒｅｑｕｅｓｔｅｒ1，Ｒｅｑｕｅｓｔｅｒ2に再割当てされる。
【００２６】
なお、さらなる随意の特徴が本発明と共に含まれる。結果的に予期される変化又は差異は、本発明に係る対象及び慣例に応じて熟慮される。従って、本発明は請求項の範囲によって定義され、該請求項は合理的であるように広く解釈されることが意図されている。
【図面の簡単な説明】
【００２７】
【図１】本発明の実施例に係るアービタの構造を例証する。
【図２】本発明の実施例に係るアービタの内部動作を例証する。
【図３】本発明の実施例に係る高速バスに対するアクセスを支配するのに用いられるアービタの例を示す。
【図１】
2005518045.tif 000003
【図２】
2005518045.tif 000004
【図３】
2005518045.tif 000005
【国際調査報告】
2005518045.tif 000006