(57)【要約】  複数のデータ項目の共有リソースへのアクセスを制御する方法とシステムであって、データ項目はそれぞれ、複数の優先順位のうちの１つへ割り当てられており、ある１つの優先順位の所定の数のデータ項目が共有リソースに送信されたとき、その優先順位は、低い非待ち受けの優先順位が全て少なくとも１つのデータ項目を共有リソースに送信されるまで待ち受けになり、即ち、その優先順位ではそれ以上のデータ項目は送信されない。このようにして、保証されるサービスを全ての優先順位に関して得ることができる。
2008532145.tif 000002
【特許請求の範囲】
【請求項１】
共有リソースへのアクセスを制御する方法であって、
−複数の異なる所定の優先順位のうちの１つを既にそれぞれ割り付けられている、送信されるべき少なくとも１つのデータ項目に関係する情報を受信することと、
−複数の項目を上記リソースに、
・最も高い非待ち受けの優先順位を有する１つの送信されるべきデータ項目を上記リソースに送信することと、
・その優先順位が、引き続き、送信されるべきデータ項目に関する情報が既に受信されている非待ち受けの低い各優先順位からの１つのデータ項目の送信を待ち受けることによって、繰り返し送信することを含む共有リソースへのアクセスを制御する方法。
【請求項２】
上記複数の優先順位の１つにそれぞれ関係する複数の待ち行列を提供するステップをさらに含み、
−上記受信するステップは、１つの待ち行列内の各データ項目を受信することを含み、上記待ち行列は上記データ項目に割り当てられた優先順位に関係し、
−上記送信するステップは、上記最も高い優先順位を有する１つの非待ち受けの待ち行列から上記データ項目を送信することを含み、
−上記待ち受けるステップは、その待ち行列が、その後、低い優先順位を有する全ての空でない非待ち受けの待ち行列からの１つのデータ項目の送信を待ち受けることを含む請求項１記載の方法。
【請求項３】
上記待ち受けるステップは、非待ち受けの低い各優先順位からのデータ項目がデータプロバイダから上記共有リソースに送信されたとき、上記待ち行列からの次のデータ項目をメモリへ転送することを含み、
上記送信するステップは、上記メモリ内の最も高い優先順位を有するそのデータ項目を送信することを含む請求項２記載の方法。
【請求項４】
複数のデータプロバイダを提供するステップをさらに含み、
上記複数のデータプロバイダはそれぞれ、
−上記複数の優先順位のうちの１つをすでにそれぞれ割り当てられている複数のデータ項目を提供するように、かつ、
−上記データプロバイダから上記共有リソースへの送信準備が整っている少なくとも１つのデータ項目に関する情報を提供するように適合化されており、
−上記送信するステップは、１つのデータプロバイダが上記データ項目を上記リソースに送信することを含み、
−上記待ち受けるステップは、低い各非待ち受けの優先順位からのデータ項目がデータプロバイダから上記共有リソースに送信されるまで、上記待ち受けの優先順位を有する送信準備の整ったデータ項目の任意のデータプロバイダからの送信を防止することを含む請求項１乃至３のうちのいずれか１つの請求項記載の方法。
【請求項５】
上記複数のデータプロバイダは、指示されるとそれに従って、データ項目を転送するように適合化されており、
−上記送信するステップは、最も高い非待ち受けの優先順位の送信準備の整ったデータ項目を有する１つのデータプロバイダに上記データ項目を上記共有リソースに転送するように指示することを含み、
−上記待ち受けるステップは、待ち受けの優先順位の送信準備の整ったデータ項目を有するデータプロバイダに、上記待ち受けの優先順位の任意のデータ項目を送信するように指示しないことを含む請求項４記載の方法。
【請求項６】
上記受信するステップは、上記複数のデータ項目を受信しかつ上記複数のデータ項目を記憶装置又はメモリに提供することを含み、
上記送信するステップは、上記データ項目を上記記憶装置又はメモリから送信することを含む先行するいずれか１つの請求項記載の方法。
【請求項７】
上記共有リソースは、リンク、メモリ、プロセッサ、集積回路又はクロスバーである先行するいずれか１つの請求項記載の方法。
【請求項８】
１つの所定の優先順位のための上記待ち受けるステップは、上記所定の優先順位が複数のデータ項目を送信したときのみ、上記（少なくとも１つの）データ項目の（少なくとも１回の）送信を待ち受けることを含む先行するいずれか１つの請求項記載の方法。
【請求項９】
共有リソースへのアクセスを制御する方法であって、
−複数の異なる所定の優先順位のうちの１つを既にそれぞれ割り付けられている、送信されるべき少なくとも１つのデータ項目に関係する情報を受信することと、
−データ項目に関する情報の各要素は上記関係する優先順位の１つの送信プロセスを割り当てられており、優先順位毎に少なくとも１つの送信プロセスを定義することと、
−複数の項目を上記リソースへ、
・最も高い優先順位のために定義される非待ち受けの送信プロセスに、その関連情報が既に割り当てられている１つのデータ項目を上記リソースに送信することと、
・引き続き、その送信プロセスが、送信されるべきデータ項目に関する情報を既に割り当てられかつそのうちの少なくとも１つの送信プロセスが非待ち受けである低い各優先順位からのデータ項目の送信を待ち受けることによって繰返し送信することを含む共有リソースへのアクセスを制御する方法。
【請求項１０】
上記優先順位／待ち行列／送信プロセスは、時間に間に合って送信された上記データ項目の送信時にはその情報が既に受信されているデータ項目のみの送信を待ち受ける先行するいずれか１つの請求項記載の方法。
【請求項１１】
共有リソースへのアクセスを制御するためのシステムであって、
−複数の異なる所定の優先順位のうちの１つを既にそれぞれ割り付けられている、送信されるべき少なくとも１つのデータ項目に関係する情報を受信するように適合化された受信手段と、
−複数のデータ項目を上記リソースに、
・１つのデータ項目を送信させ、かつ最も高い非待ち受けの優先順位を上記リソースに送信させることと、
・引き続き、その優先順位からの１つのデータ項目の送信を、送信されるべきデータ項目に関する情報が既に受信されている非待ち受けの低い各優先順位によって１つのデータ項目が送信されるまで待機させることによって、繰返し提供させるように適合化された送信機手段とを備える共有リソースへのアクセスを制御するためのシステム。
【請求項１２】
上記複数の優先順位のうちの１つにそれぞれ関連する複数の待ち行列をさらに備え、
−上記受信手段は、１つの待ち行列内に各データ項目を提供するように適合化されており、上記待ち行列は上記データ項目に割り当てられた優先順位に関係し、
−上記送信機手段は、最も高い非待ち受けの優先順位を有する上記データ項目を上記最も高い優先順位を有する任意の非待ち受けの待ち行列のデータ項目から送信し、かつ、引き続き、その行列に低い優先順位に関連する全ての非待ち受けの待ち行列からのデータ項目の送信を待ち受けさせるように適合化される請求項１１記載のシステム。
【請求項１３】
上記送信機手段は、非待ち受けの低い各優先順位からのデータ項目が１つの待ち行列から上記共有リソースに送信されたとき、次のデータ項目を上記待ち行列からメモリへ転送し、かつメモリ内の上記最も高い優先順位を有するそのデータ項目を上記リソースに送信するように適合化される請求項１２記載のシステム。
【請求項１４】
複数のデータプロバイダをさらに備え、上記複数のデータプロバイダはそれぞれ、
−上記複数の優先順位の１つをそれぞれ割り当てられている複数のデータ項目を提供するように、かつ、
−上記データプロバイダから上記共有リソースへの送信準備が整っている少なくとも１つのデータ項目に関する上記情報を提供するように適合化されており、
上記送信機手段は、１つのデータプロバイダに、上記最も高い非待ち受けの優先順位を有する上記データ項目を上記リソースに送信するように指示しかつ、引き続き、低い各非待ち受けの優先順位からのデータ項目がデータプロバイダから上記共有リソースに送信されるまで、任意のデータプロバイダからの上記待ち受け優先順位を有する送信準備の整っているデータ項目の送信を防止するように指示するように適合化される請求項１１乃至１３のうちのいずれか１つの請求項記載のシステム。
【請求項１５】
上記複数のデータプロバイダは、指示されるとそれに従って、データ項目を転送するように適合化されており、
上記送信機手段は、上記最も高い非待ち受けの優先順位の送信準備の整っているデータ項目を有する１つのデータプロバイダに上記データ項目を上記共有リソースに転送するように指示し、かつ、引き続き、上記待ち受けの優先順位の送信準備の整っているデータ項目を有する複数のデータプロバイダに、上記データプロバイダが低い各非待ち受けの優先順位からのデータ項目を送信するように指示されるまで、上記待ち受けの優先順位の任意のデータ項目を送信するように指示しないように適合化される請求項１４記載のシステム。
【請求項１６】
上記受信手段は、上記複数のデータ項目を受信しかつ上記複数のデータ項目を記憶装置又はメモリに提供するように適合化されており、
上記送信機手段は、上記複数のデータ項目を上記記憶装置又はメモリから送信するように適合化される請求項１１乃至１５のうちのいずれか１つの請求項記載のシステム。
【請求項１７】
上記共有リソースは、リンク、メモリ、プロセッサ、集積回路又はクロスバーである請求項１０乃至１６のうちのいずれか１つの請求項記載のシステム。
【請求項１８】
上記送信機手段は、ある優先順位からの複数のデータ項目が上記リソースに送信された後にのみ、上記優先順位を待ち受けさせるように適合化される請求項１１乃至１７のうちのいずれか１つの請求項記載のシステム。
【請求項１９】
共有リソースへのアクセスを制御するためのシステムであって、上記方法は、
−複数の異なる所定の優先順位のうちの１つを既にそれぞれ割り付けられている、送信されるべき少なくとも１つのデータ項目に関係する情報を受信するように適合化された受信手段と、
−データ項目に関する情報の各要素は上記関係する優先順位の１つの送信プロセスを割り当てられている、優先順位毎の少なくとも１つの送信プロセスと、
−複数のデータ項目を上記リソースへ、
・最も高い優先順位のために定義される非待ち受けの送信プロセスに、その関連情報が既に割り当てられている１つのデータ項目を上記リソースに送信させることと、
・引き続き、その送信プロセスに、送信されるべきデータ項目に関する情報を既に割り当てられかつそのうちの少なくとも１つの送信プロセスが非待ち受けである低い各優先順位からのデータ項目の送信を待ち受けさせることによって繰返し提供させるように適合化された送信機手段とを備える共有リソースへのアクセスを制御するためのシステム。
【請求項２０】
上記送信機手段は、上記優先順位／待ち行列／送信プロセスに、時間に間に合って送信された上記データ項目の送信時にはその情報が既に受信されているデータ項目のみの送信を待ち受けさせるように適合化される請求項１１乃至１９のうちのいずれか１つの請求項記載のシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、共有リソースへのアクセスの制御に関し、特に、共有リソースへのデータ転送に所定の保証を提供するために制御することに関する。
【背景技術】
【０００２】
このタイプの技術は、特許文献１及び非特許文献１乃至４に記述されている。
【０００３】
【特許文献１】米国特許出願公開第２００４／００１５０２号明細書。
【非特許文献１】Felicijan, T. et al., 「An asynchronous on-chip network router with quality-of-service (QoS) support」, SOC conference, 2004, proceedings. IEEE, International Santa Clara, CA, USA, Sept. 12-15, 2004, Piscataway, NJ, USA, IEEE, pp 274-77.
【非特許文献２】Felicijan, T. et al., 「An asynchronous low latency arbiter for quality of service (qos) applications」, microelectronics, 2003, ICM 2003, Proceedings of the 15th international conference on Cairo, Egypt, Dec.9-11, 2003, Piscataway, NJ, USA, IEEE, pp 123-26.
【非特許文献３】Bjerregaard, T. et al., 「Virtual channel designs for guaranteeing bandwidth in asynchronous network-on-chip」, Norchip conference, 2004, proceedings, Oslo, Norway, 8-9 Nov. 2004, Piscataway, NJ, USA, IEEE, pp 269-272.
【非特許文献４】Zhang, H. et al., 「Rate-controlled static-priority queueing」, Networking: foundation for the future, San Francisco, March 28  April 1,1993, Proceedings of the annual joint conference, on the computer and communications societies (INFOCOM), Los Alamitos, IEEE Comp. Soc. Press, US, vol. 2, conf. 12, pp 227-236.
【発明の開示】
【発明が解決しようとする課題】
【０００４】
多くのデータ転送アプリケーションに見受けられる問題は、ある量のデータがリンク又はメモリ等の共有リソースへの転送を予定されていて、しかもこのデータの全てを同時には送信することができないことにある。従って、どのデータを最初に送信し、どのデータが待機しなければならないかについて決定を下さなければならない。当然ながら、この決定は、待ち時間等の共有リソースへ向けたデータの転送に影響を与え、ひいては、リソースが関与しているアプリケーションのパフォーマンスに影響を与える。本発明は、共有リソースに向けられるデータを、待ち時間及び帯域幅に関する保証が得られるようにスケジューリングする新規な方法を提供する。
【課題を解決するための手段】
【０００５】
第１の態様において、本発明は共有リソースへのアクセスを制御する方法に関し、
−複数の異なる所定の優先順位のうちの１つを既にそれぞれ割り付けられている、送信されるべき少なくとも１つのデータ項目に関係する情報を受信することと、
−複数の項目を上記リソースに、
・最も高い非待ち受けの優先順位を有する１つの送信されるべきデータ項目を上記リソースに送信することと、
・その優先順位が、引き続き、送信されるべきデータ項目に関する情報が既に受信されている非待ち受けの低い各優先順位からの１つのデータ項目の送信を待ち受けることによって、繰り返し送信することを含む。
【０００６】
一般に、データ項目は、イーサネットのパケット、フリット（フロー制御ユニット）又はこれらの一部等の任意タイプのデータ項目であってもよい。各データ項目は単独で処理されかつ優先順位を付けられてもよく、又はより多い量のデータが優先順位を付けられ、次に複数のデータ項目に分割されてもよい。
【０００７】
データの優先順位は予め決定されてもよく、そのデータ項目又はそのデータ項目が引き出されたより多い量のデータのコンテンツから決定されてもよい。あるいは、優先順位は、そのソース（発信者）又はその受信者から決定されてもよい。
【０００８】
本コンテキストにおいては、優先順位は任意の望ましい方法で表現されてもよい。本発明は通常、電気回路において実現されているので、通常は、整数等の優先順位を表す数が使用される。しなしながら、電気回路であってもこれは必要条件ではない。
【０００９】
一般に、優先順位の順番は、任意の優先順位ペアからどちらが高く、どちらが低いかを決定できるようにして決定される。これは、優先順位の実際の表現方法とは無関係である。本コンテキストでは、優先順位は任意の方法で表現されてもよく、その順位（どれが他より高いか）は任意の方法で決定されてもよい。
【００１０】
受信ステップは、データだけを受信してもよく（その後、その優先順位を決定する）、優先順位だけ、又はデータ及び割り当てられた優先順位の両方を受信してもよい。以下、これらの情報を受信する方法の異なる態様についてさらに説明する。
【００１１】
現在、共有リソースは、データを受信するように適合化された、メモリ、リンク、プロセッサ及び／又はクロスバー等の任意タイプのリソースであってもよい。
【００１２】
本発明は、データ項目の共有媒体への送信を制御する方法に関し、個々のデータ項目に焦点を合わせるのではなく、優先順位に基づいてデータ項目の流れを制御する。
【００１３】
優先順位は、待ち受けであってもなくてもよい。待ち受けの優先順位とは、その優先順位を有するデータはどれも、今は共有リソースに送信され得ないことを意味する。その優先順位を有するデータ項目に共有リソースへの送信を望むものがないとしても、その優先順位は待ち受けであると言える（即ち、このようなデータ項目の送信準備が整っていることを示す情報が受信されている）。
【００１４】
好ましくは、特定の優先順位だけ待ち受けしなければならない非待ち受けの低い優先順位は、関係する優先順位を有するデータ項目の送信の時点で非待ち受けである優先順位である。
【００１５】
任意の時点で、次にリソースに送信されるべきデータ項目は、下記のようなデータ項目である。
−送信の準備が整っており（即ち、それに関する情報が既に受信されており）、
−待ち受けでない優先順位を有しており、かつ
−データ項目の準備が整っている非待ち受けの優先順位のうちで最も高い優先順位を有するもの。
【００１６】
そのデータ項目が一旦送信されると、その優先順位は、待ち受けでなくかつそのためのデータの送信の準備が整っている低い優先順位が全てデータ項目を共有リソースに送信する機会を得るまで、待ち受けしている。
【００１７】
ある優先順位が待ち受けである間に、この待ち受けの優先順位より低い他の優先順位に関するデータ項目の送信の準備が整うことになる点は注目すべきである。待ち受けの優先順位は、このような優先順位からの送信をも待機する必要はない。
【００１８】
現在の優先順位が再び送信するまでに、どの低い優先順位が送信しなければならないかに関して、優先順位毎に記録をとることが所望されてもよい。
【００１９】
最も高い優先順位は、全ての低い（他の全ての）非待ち受けの優先順位がデータ項目を送信する度に、好ましくは少なくとも一度送信を許可されるだけであるとしても、待ち時間及び取得可能な帯域幅の両方に関して、全ての優先順位に所定の保証が得られる点は注目される。さらに、データ項目の共有リソースへの送信は、実際にどの優先順位がデータ項目を送信するかに関わらず、最適（リンクの全能力等）であり得る点も注目される。これは、ある優先順位が待ち受けであり得るのは、他の優先順位を割り当てられたデータ項目の送信の準備が整っている場合に限られることから分かる。１つの優先順位のみが、送信されるべき複数のデータ項目を有するときは、この優先順位は待ち受けにはならず、そのデータ項目は１つずつ共有リソースに送信されてもよい。
【００２０】
複数のデータ項目を提供する１つの方法は、
上記複数の優先順位の１つにそれぞれ関係する複数の待ち行列を提供するステップをさらに含み、
−上記受信するステップは、１つの待ち行列内の各データ項目を受信することを含み、上記待ち行列は上記データ項目に割り当てられた優先順位に関係し、
−上記送信するステップは、上記最も高い優先順位を有する１つの非待ち受けの待ち行列から上記データ項目を送信することを含み、
−上記待ち受けるステップは、その待ち行列が、その後、低い優先順位を有する全ての空でない非待ち受けの待ち行列からの１つのデータ項目の送信を待ち受けることを含む方法である。
【００２１】
従って、データ項目は受信され、かつ関係する優先順位に関する待ち行列に提供される。
【００２２】
これに関しては、上記待ち受けるステップは、非待ち受けの低い各優先順位からのデータ項目がデータプロバイダから上記共有リソースに送信されたとき、上記待ち行列からの次のデータ項目をメモリへ転送することを含むかもしれず、上記送信するステップは、上記メモリ内の最も高い優先順位を有するそのデータ項目を送信することを含む。
【００２３】
これは、待ち受けの状態と、どのデータ項目を送信するかの決定とがさらに分離される点で、プロセスを単純にする。この実施形態では、メモリは単に非待ち受けである空でない待ち行列毎にデータ項目を保持するだけである。従って、これらのデータ項目のうちのどれが送信されるべきかの決定が簡単である。
【００２４】
実際に、どの優先順位が待ち受けであるかを可視化し、かつ送信するために適合化される次の優先順位の容易な決定を促進するためには、この同じメモリ構造が、実際のデータ項目のためではなく、データ項目に関連する情報のために使用されてもよい。
【００２５】
メモリにデータ項目を持たない空でない待ち行列が待ち受けの待ち行列になるように、待ち受けの待ち行列は、データ項目をメモリに送信することを防止されてもよい。
【００２６】
別の実施形態では、本方法は、複数のデータプロバイダを提供するステップをさらに含み、
上記複数のデータプロバイダはそれぞれ、
−上記複数の優先順位のうちの１つをすでにそれぞれ割り当てられている複数のデータ項目を提供するように、かつ、
−上記データプロバイダから上記共有リソースへの送信準備が整っている少なくとも１つのデータ項目に関する情報を提供するように適合化されており、
−上記送信するステップは、１つのデータプロバイダが上記データ項目を上記リソースに送信することを含み、
−上記待ち受けるステップは、低い各非待ち受けの優先順位からのデータ項目がデータプロバイダから上記共有リソースに送信されるまで、上記待ち受けの優先順位を有する送信準備の整ったデータ項目の任意のデータプロバイダからの送信を防止することを含む。
【００２７】
この状況において、本方法又は本方法を実行するシステムはデータを保有又は受信しなくてもよいが、データ項目をいつ送信するか（及び、好ましくはプロバイダが幾つかのデータ項目のうちのどれを送信するかを決定するためのその優先順位の識別）を（データ項目の送信方法を知らせる）データプロバイダに指示するように適合化される。
【００２８】
１つの方法では、待ち受けるステップは、防止信号を送信する等により、データプロバイダが待ち受けの優先順位を有するデータ項目を送信することを能動的に防止する。あるいは、プロバイダは、送信を指示されるまではデータ項目を送信しないように適合化される。これは、上記複数のデータプロバイダは、指示されるとそれに従って、データ項目を転送するように適合化されているときであってもよく、
−上記送信するステップは、最も高い非待ち受けの優先順位の送信準備の整ったデータ項目を有する１つのデータプロバイダに上記データ項目を上記共有リソースに転送するように指示することを含み、
−上記待ち受けるステップは、待ち受けの優先順位の送信準備の整ったデータ項目を有するデータプロバイダに、上記待ち受けの優先順位の任意のデータ項目を送信するように指示しないことを含む。
【００２９】
一般に、受信するステップは、好ましくは、上記複数のデータ項目を受信しかつ上記複数のデータ項目を記憶装置又はメモリに提供することを含み、上記送信するステップは、上記データ項目を上記記憶装置又はメモリから送信することを含む。
【００３０】
ある実施形態では、１つの所定の優先順位のための上記待ち受けるステップは、上記所定の優先順位が複数のデータ項目を送信したときのみ、上記（少なくとも１つの）データ項目の（少なくとも１回の）送信を待ち受けることを含む。この方法では、この所定の優先順位は、上記優先順位が待ち受けの段階になる前にデータ項目が毎回１つしか送信されない場合よりも、リソースへの大きい帯域幅を与えられる。
【００３１】
この状況においては、非待ち受けの待ち行列に関してリソースに送信されるべきデータ項目を保持するメモリはどれも、所定の優先順位のための複数のデータ項目のためのスペースを有し、他の優先順位のためにはそれより少ないスペースを有してもよい。
【００３２】
他の態様において、本発明は共有リソースへのアクセスを制御する方法に関し、
−複数の異なる所定の優先順位のうちの１つを既にそれぞれ割り付けられている、送信されるべき少なくとも１つのデータ項目に関係する情報を受信することと、
−データ項目に関する情報の各要素は上記関係する優先順位の１つの送信プロセスを割り当てられており、優先順位毎に少なくとも１つの送信プロセスを定義することと、
−複数の項目を上記リソースへ、
・最も高い優先順位のために定義される非待ち受けの送信プロセスに、その関連情報が既に割り当てられている１つのデータ項目を上記リソースに送信することと、
・引き続き、その送信プロセスが、送信されるべきデータ項目に関する情報を既に割り当てられかつそのうちの少なくとも１つの送信プロセスが非待ち受けである低い各優先順位からのデータ項目の送信を待ち受けることによって繰返し送信することを含む。
【００３３】
この態様は、第１の態様に密接に関連するものであるが、この態様においては、少なくとも１つの優先順位に関して、第１の態様の送信の特徴に従う幾つかの送信機手段が定義されてもよい。この方法では、この優先順位は、他の優先順位に対して決定可能かつ現実的なサービス保証を提供しながら、より大きい帯域幅を得ることができる。
【００３４】
この場合もやはり、受信される情報をどの送信プロセスに割り当てるか、及びデータ項目の送信にどの送信プロセスが選択されるかを制御することによって、多種多様な振る舞いを得ることができる。また、受信される情報を送信プロセスに割り当てるタイミングは、システムの振る舞いを決定する。好ましくは、情報は、最も早い時点で送信される関係するデータ項目を有することになる送信プロセスに割り当てられる。
【００３５】
ある実施形態では、この送信プロセスは、引き続き、実際に、送信されるべきデータ項目に関する情報が割り当てられている、低い優先順位の各非待ち受けの送信プロセスからのデータ項目の送信を待ち受ける。
【００３６】
一般に、上記第１及び第２の態様においては、上記優先順位／待ち行列／送信プロセスは、好ましくは、時間に間に合って送信された上記データ項目の送信時にはその情報が既に受信されているデータ項目のみの送信を待ち受ける。従って、これらの態様においては、どの待ち行列、送信プロセス又は優先順位が非待ち受けでありかつ空でないかの決定は、好ましくは、そのデータ項目の送信の時点で実行される。ある方法では、各優先順位にメモリが割り当てられ、このメモリには、この優先順位が再び非待ち受けになる前にデータ項目を送信すべき、空でない待ち受けの低い優先順位の情報が与えられてもよい。次に、このメモリは、データ項目の送信の度に更新されてもよい。
【００３７】
本発明の別の態様は、共有リソースへのアクセスを制御するためのシステムに関し、
−複数の異なる所定の優先順位のうちの１つを既にそれぞれ割り付けられている、送信されるべき少なくとも１つのデータ項目に関係する情報を受信するように適合化された受信手段と、
−複数のデータ項目を上記リソースに、
・１つのデータ項目を送信させ、かつ最も高い非待ち受けの優先順位を上記リソースに送信させることと、
・引き続き、その優先順位からの１つのデータ項目の送信を、送信されるべきデータ項目に関する情報が既に受信されている非待ち受けの低い各優先順位によって１つのデータ項目が送信されるまで待機させることによって、繰返し提供させるように適合化された送信機手段とを備える。
【００３８】
上述したように、上記受信手段は実際のデータ項目を受信しかつ関係する優先順位をそれ自身が決定してもよく、データ項目及び優先順位の両方を受信してもよく、又は優先順位のみを受信してもよい。
【００３９】
ある総合的な実施形態では、上記複数の優先順位のうちの１つにそれぞれ関連する複数の待ち行列をさらに備え、
−上記受信手段は、１つの待ち行列内に各データ項目を提供するように適合化されており、上記待ち行列は上記データ項目に割り当てられた優先順位に関係し、
−上記送信機手段は、最も高い非待ち受けの優先順位を有する上記データ項目を上記最も高い優先順位を有する任意の非待ち受けの待ち行列のデータ項目から送信し、かつ、引き続き、その行列に低い優先順位に関連する全ての非待ち受けの待ち行列からのデータ項目の送信を待ち受けさせるように適合化される。
【００４０】
次に、上記送信機手段は、非待ち受けの低い各優先順位からのデータ項目が１つの待ち行列から上記共有リソースに送信されたとき、次のデータ項目を上記待ち行列からメモリへ転送し、かつメモリ内の上記最も高い優先順位を有するそのデータ項目を上記リソースに送信するように適合化されてもよい。
【００４１】
上述したように、このタイプのメモリは、データ項目を送る次の優先順位の迅速な決定を促進するために、非待ち受けの優先順位のための情報のみがメモリにおいて受信されるような方法で受信されるその情報のために、追加的に又は代わりに使用されてもよい。
【００４２】
この同じ、又は他の実施形態において、  複数のデータプロバイダをさらに備え、上記複数のデータプロバイダはそれぞれ、
−上記複数の優先順位の１つをそれぞれ割り当てられている複数のデータ項目を提供するように、かつ、
−上記データプロバイダから上記共有リソースへの送信準備が整っている少なくとも１つのデータ項目に関する上記情報を提供するように適合化されてもよく、
上記送信機手段は、１つのデータプロバイダに、上記最も高い非待ち受けの優先順位を有する上記データ項目を上記リソースに送信するように指示しかつ、引き続き、低い各非待ち受けの優先順位からのデータ項目がデータプロバイダから上記共有リソースに送信されるまで、任意のデータプロバイダからの上記待ち受け優先順位を有する送信準備の整っているデータ項目の送信を防止するように指示するように適合化される。
【００４３】
この点に関して、上記複数のデータプロバイダは、指示されるとそれに従って、データ項目を転送するように適合化されてもよく、上記送信機手段は、上記最も高い非待ち受けの優先順位の送信準備の整っているデータ項目を有する１つのデータプロバイダに上記データ項目を上記共有リソースに転送するように指示し、かつ、引き続き、上記待ち受けの優先順位の送信準備の整っているデータ項目を有する複数のデータプロバイダに、上記データプロバイダが低い各非待ち受けの優先順位からのデータ項目を送信するように指示されるまで、上記待ち受けの優先順位の任意のデータ項目を送信するように指示しないように適合化される。
【００４４】
一般に、上記受信手段は、好ましくは、上記複数のデータ項目を受信しかつ上記複数のデータ項目を記憶装置又はメモリに提供するように適合化されており、上記送信機手段は、上記複数のデータ項目を上記記憶装置又はメモリから送信するように適合化される。
【００４５】
本コンテキストにおいては、上記共有リソースは、リンク、メモリ、プロセッサ、集積回路又はクロスバーであってもよい。
【００４６】
上述したように、上記送信機手段が、ある優先順位からの複数のデータ項目が上記リソースに送信された後にのみ、上記優先順位を待ち受けさせるように適合化されるときに、より広い帯域が所定の優先順位に提供されてもよい。
【００４７】
第４の態様においては、本発明は、共有リソースへのアクセスを制御するためのシステムであって、上記方法は、
−複数の異なる所定の優先順位のうちの１つを既にそれぞれ割り付けられている、送信されるべき少なくとも１つのデータ項目に関係する情報を受信するように適合化された受信手段と、
−データ項目に関する情報の各要素は上記関係する優先順位の１つの送信プロセスを割り当てられている、優先順位毎の少なくとも１つの送信プロセスと、
−複数のデータ項目を上記リソースへ、
・最も高い優先順位のために定義される非待ち受けの送信プロセスに、その関連情報が既に割り当てられている１つのデータ項目を上記リソースに送信させることと、
・引き続き、その送信プロセスに、送信されるべきデータ項目に関する情報を既に割り当てられかつそのうちの少なくとも１つの送信プロセスが非待ち受けである低い各優先順位からのデータ項目の送信を待ち受けさせることによって繰返し提供させるように適合化された送信機手段とを備える。
【００４８】
上述したように、これは、データ項目のフローを制御しかつ優先順位に決定可能かつ制御可能な送信保証を与える追加的な方法を提供する。
【００４９】
ある実施形態では、上記送信機手段は、引き続き、この送信プロセスに、送信されるべきデータ項目に関する情報を既に割り当てられている、低い優先順位の各非待ち受けの送信プロセスからのデータ項目の送信を待ち受けさせるように適合化される。
【００５０】
また、上記第３及び第４の態様において、上記送信機手段は、好ましくは、上記優先順位／待ち行列／送信プロセスに、時間に間に合って送信された上記データ項目の送信時にはその情報が既に受信されているデータ項目のみの送信を待ち受けさせるように適合化される。その決定の時点が確定されるときは、これにより上記プロセスの制御はより容易になる。
【発明の効果】
【００５１】
本発明は、共有リソースに向けられるデータを、待ち時間及び帯域幅に関する保証が得られるようにスケジューリングする新規な方法を提供する。
【発明を実施するための最良の形態】
【００５２】
以下、図面を参照して、本発明の好適な実施形態について説明する。
【００５３】
本実施形態は、本発明（以下、ＡＬＧ（Ａｓｙｎｃｈｒｏｎｏｕｓ  Ｌａｔｅｎｃｙ  Ｇｕａｒａｎｔｅｅ）−非同期の待ち時間保証と呼ぶ。）を非同期のオンチップネットワーク（ネットワーク・オン・チップ（Ｎｅｔｗｏｒｋ−ｏｎ−Ｃｈｉｐ）、ＮｏＣ）におけるリンクスケジューラとして使用し得る方法を示す。ＡＬＧにより提供される複数の保証されるサービス（ＧＳ（Ｇｕａｒａｎｔｅｅｄ  Ｓｅｒｖｉｃｅ））は互いに逆依存しておらず、従って、ＡＬＧは、時分割多重（ＴＤＭ）に基づく帯域幅（ＢＷ）割当ての方法の限界を克服し、かつ異なる複数のＧＳの必要条件によって特徴づけられる広範なトラフィックタイプをサポートする。ＧＳのスペクトル範囲の反対側の両端において、ＡＬＧは臨界待ち時間及び割込み等の低いＢＷトラフィックの両方をサポートし、また、厳しい待ち時間の要請はないがＢＷに関してＧＳを要求するストリーミングデータもサポートする。さらに、ＡＬＧは、完全な非同期環境において動作する。以下、ローエリア０．１２μｍのＣＭＯＳ規格のセル実装によってこれを実証する。
【００５４】
本明細書の以後の編成は、次の通りである。セクション１では、ＧＳの背景を考察し、現在の解決方法を述べ、ＮｏＣにおける最適な解決方法の必要条件を定義する。セクション２では、ＡＬＧスケジューリングの概念を説明してその機能性の証拠を呈示し、セクション４では、セクション３で述べた証拠を拡大して検討してバッファの限界についても説明する。セクション４は、この方法における帯域幅の割当てに関する。セクション５では、オンチップＡＬＧリンクの実装について述べ、セクション６では、シミュレーションの結果を提供する。
【００５５】
１．保証されるサービス
以下、複数のネットワークパフォーマンスパラメータについて検討し、分類を確立する。次に、接続指向のルーティングの必要性について論じ、現在のＮｏＣ及びマクロネットワークにおいて使用されるＧＳの技術について検討し、最後にＮｏＣにおけるＧＳの一連の必要条件を提案する。
【００５６】
１．１．パフォーマンスパラメータ
サービス保証は、少なくとも１つのパフォーマンスパラメータによって定量化される。サービスの限界を適切に指定するためには、ＢＷ及び待ち時間の両方が示されなければならない。維持され得るスループットが小さすぎれば、待ち時間保証は役に立たず、同様に、負わされる待ち時間に限界がなければＢＷ保証は役に立たない。
【００５７】
複数フリットの１つのストリームのＢＷの限界はそのパスにおけるボトルネックによって決定されるが、ネットワークにおける１つのフリットの合計の待ち時間は、発生する待ち時間の総和によって特徴づけられる。これらは、必要とされるネットワーク接続がその間にアクセスされるネットワークのアドミッション待ち時間ｔａｄｍｉｔ及び多くのホップ待ち時間を含む。ここで、１つのホップは、１つのルーティングノード内のバッファからリンクを通って隣のルーティングノード内のバッファへ至るフリットの移動である。ホップ待ち時間は、フリットが例えばリンクである共有のルーティングリソースへのアクセスが許可されるのに要する時間であるアクセス待ち時間ｔａｃｃｅｓｓと、アクセスが一旦許可されているときに、フリットを次のルーティングノード内のバッファに送信するために要する時間である送信待ち時間ｔｌｉｎｋとから成る。従って、Ｘホップの長さであるパスをトラバースして移動する１つのフリットの合計の待ち時間は、ｔｔｏｔａｌ＝ｔａｄｍｉｔ＋ｔａｃｃｅｓｓ１＋ｔｌｉｎｋ１＋…＋ｔａｃｃｅｓｓＸ＋ｔｌｉｎｋＸになる。
【００５８】
１．２．接続指向のＧＳ
確かなサービス保証を提供するためには、接続指向のルーティングが絶対に不可欠である。接続なしのルーティングでは、全てのデータが同じ論理ネットワーク上を移動し、どの送信も別の送信をストールする可能性を有する。ＧＳトラフィックは、ネットワーク内の他のトラフィックとは論理的に独立していなければならない。サービス保証に関する確かな限界は、モジュールの設計フローを促進することにおいて、システムレベルの視点から有益である。このような保証がなければ、システムの変更は、大規模なトップレベルの再検証を必要とすることがある。従って、ＮｏＣにおけるＧＳは、大規模ＳｏＣ設計のターンアラウンド・タイムを短縮する可能性を含んでいる。また、ＢＥルーティングネットワークのパフォーマンスの形式的な検証は可能でない場合が多いが、臨界的なリアルタイムシステムでは望ましいように、ＧＳはこれを可能にする。
【００５９】
１．３．ＧＳの技術
ＢＷ保証を提供する基本的な解決方法は、フェア・フリュイド・キューイング（ＦＦＱ（ｆａｉｒ  ｆｌｕｉｄ  ｑｕｅｉｎｇ））に基づく。ＦＦＱは、接続毎に別々の複数の待ち行列を実現するヘッド・オブ・ライン・プロセッサ・シェアリング（ＨＯＬ−ＰＳ（ｈｅａｄ−ｏｆ−ｌｉｎｅ  ｐｒｏｃｅｓｓｏｒ  ｓｈａｒｉｎｇ））の一般的な形式である。待ち行列の先頭は、フェアシェアなアクセスを例えばリンクである共有媒体へ提供するような方法でサービス処理がされる。
【００６０】
非同期のＮｏＣにおいては、ＦＦＱ型のアクセス方法には、極めて長い最悪のケースの待ち時間という不快な欠点がある。ツリーアービタ（ツリーの調停装置）は、ＦＦＱを近似することができるが、複数の入力の互いに対するタイミングに関しては何も言えないので、所定のチャンネルに到達するパケットはどれも、サービス処理がされるまでに他の全ての入力を待機せざるを得ないという可能性がある。従って、このリンクアクセス方法を実現する非同期ＮｏＣにおいて、複数のリンクのシーケンスを通じて累積される最悪のケースの待ち時間は極めて長い。また、アクセス時間はＢＷの予約に反比例する。短い待ち時間を達成するためには、ＢＷの大部分が予約されなければならない。全体的に同期のＮｏＣでは、ネットワークを通じた待ち時間は１ホップ当たり１クロックサイクルに保証され得るが、ソースにおける接続へアクセスする待ち時間は依然として、予約されるＢＷに反比例する。また、複数の接続は独立してはバッファされないので、このように短いホップ当たりの待ち時間を実現するためには、明示的なエンド・ツー・エンドのフロー制御が要求される。ＢＷ保証から分離された、待ち時間のよりよい限界を提供するためには、異なる方法が必要である。
【００６１】
広域ネットワークでは、複数のネットワークノード間においてクロックレベルでの同期を実現することは明らかに不可能であるので、マクロネットワークは全体的には非同期の性質を有する。これにより、マクロネットワークは幾分、非同期ＮｏＣに類似する。ＧＳに対するＦＦＱ型の解決方法を実現するに当たっては、非同期ＮｏＣに関して上述したような待ち時間に関する問題点は周知の欠点である。これらの欠点を克服するためには、レートで制御される静的優先順位（ＲＣＳＰ（ｒａｔｅ  ｃｏｎｔｒｏｌｌｅｄ  ｓｔａｔｉｃ  ｐｒｉｏｒｉｔｙ））スケジューリングが使用されることが多い。ＲＣＳＰでは、アドミッションコントローラは、着信する全てのパケットに適格な送信時刻を割り当てる。この時刻になると、パケットは静的優先順位付き待ち行列（ＳＰＱ）に入れられる。この方法は、ＢＷの保証だけでなく、待ち時間の保証も、互いに独立して提供することができる。しかしながら、アドミッション制御は、ノードがローカルな時間の概念を有することを必要とする。よって、アドミッション制御は非同期ＮｏＣにおける実現には不適となる。本方法の別の欠点は、それが仕事量非保存型（ｎｏｎｗｏｒｋ−ｃｏｎｓｅｒｖｉｎｇ）であることにあり、これは、チャンネル待ち行列内にその適格な送信時刻を待っているパケットが存在していても、ルータはアイドル状態であってもよいことを意味する。これは、利用可能なネットワークリソースを使用する効率を低下させ、待ち時間の限界が尊重されるとしても、平均の接続待ち時間及びリンク利用度は低減する。
【００６２】
１．４．ＮｏＣにおけるＧＳのための必要条件
ＮｏＣにおけるＧＳのための解決方法に関する出願人による必要条件の案は、本解決方法が（ｉ）高い動作速度及び低いハードウェアオーバーヘッドを容易にするために単純であり、（ｉｉ）ネットワークリソースを効率的に利用するために仕事量保存型（ｗｏｒｋ  ｃｏｎｓｅｒｖｉｎｇ）であり、（ｉｉｉ）待ち時間及びＢＷに関して分離される、又は少なくとも互いに逆依存しない限界を提供できる、というものである。さらに、非同期ＮｏＣにおけるＧＳのための解決方法に関する必要条件として、（ｉｖ）本解決方法は、ローカルであれグローバルであれ、時間の概念を必要としないということがある。ＡＬＧは、これら全ての必要条件に適合し、よって同期システム及び非同期システムの両方においてＧＳを提供する有効な解決方法である。
【００６３】
セクション３では、ＡＬＧスケジューリングの規律について説明し、共有リンク上の待ち時間及びＢＷ保証を提供する際のその使用を実証する。但し、ＡＬＧベースのアクセスは任意の共有媒体に適用できる点に注意する。また、本明細書における実装は非同期の回路に基づいているが、ＡＬＧはこのようなものに限定されない。しかしながら、ＡＬＧは、時間の概念を必要としないという事実により、特に、非同期システムに適している。
【００６４】
２．基本的なＡＬＧスケジューリング
本セクションでは、基本的なＡＬＧスケジューリングの規律について説明する。まずは、その動作の直観的な理解について述べ、続いて、その動作を正式に証明する。以下の説明における時間表示は全て、時間単位であるフリット時間（ｆｌｉｔ−ｔｉｍｅ）を使用して量子化される。１フリット時間は、物理リンク上で１つのハンドシェークサイクルを完了するのに要する時間として定義される。ＶＣ制御手段は、リンク上でストールするフリットがないことを保証し、よって、このようなハンドシェークの時間は十分に定義される。複数の回路は非同期であるため、当然ながら、フリット時間はネットワーク全体を通じて一定ではない。しかしながら、ここでは、フリット時間はかなり均一であることを仮定している。
【００６５】
図３は、完全なＡＬＧリンクを示す。ＡＬＧアドミッション制御及び静的優先順位付き待ち行列（ＳＰＱ）は、ＡＬＧスケジューラを実現する。ＶＣ制御は、これらを包み込む。これらの３つのサブシステムがどのように同時に動作して、１つの物理リンクを共有する複数のＶＣに渡る待ち時間及びＢＷ保証を提供するかは、以下の説明で明らかとなるであろう。ＡＬＧスケジューリングの原理は、完全に最もよく理解される。ＳＰＱは、複数のＶＣに優先順位を付け、それ相応に待ち時間保証を提供するが、それは所定の複数の条件下に限定される。アドミッション制御は、これらの条件が満たされることを確実にする。ＶＣ制御機構は、受信側に空のバッファスペースが存在する場合にのみフリットが共有リンク上で送信されることを保証し、こうして、フリットがリンク上でストールしかつ待ち時間及びＢＷ保証を無効にすることを防止する。
【００６６】
２．１．優先順位付けされたチャンネル
待ち時間保証を提供するためには、リンクアクセス時間に関する限界を提供する必要がある。図２を見て、フリットがチャンネルＡからＤへ無作為に、但し大きい間隔で到着することを想定されたい。次に、これらのチャンネルは優先順位によってサービス処理されており、Ａが最も高い優先順位を有すると考える。Ａに到着するフリットは常に、ただちにサービス処理がされ、よって、最大のリンクアクセス時間は１フリット時間、即ち、進行中である可能性のある送信を完了するために要すると思われる時間、であることが保証される。この時点では、Ａに到着する複数のフリット間に大きい間隔が存在するという単純な仮定を行っているので、Ｂに到着するフリットは、サービス処理がされるまでにＡを１回だけ待機することになる。従って、Ｂ上のフリットは、最大で、進行中の送信の完了及びＡ上の送信を待つので、最大２フリット時間だけ遅延される。同様に、Ｃは最大で３フリット時間だけ待つ、等々となる。結果的に、最大のリンクアクセス時間はチャンネルの優先順位に比例する。これが、図３においてＳＰＱにより実現されている機能性である。
【００６７】
２．２．アドミッション制御
上述の規律は、大きいフリット間隔を必要とする。これを保証することは、特に分散されたルーティング制御を有する非同期ネットワークにおいては必ずしも可能ではない。仮にソースにおいて特定のフリット間隔が提供されるとしても、ネットワークはデータストリームにジッタをもたらし、その結果、間隔への必要条件がネットワーク内部のどこかで無効にされることがある。これにより、ＳＰＱへのアドミッションを調整するアドミッション制御ステージが必要になる。図３では、ＡＬＧアドミッション制御はＳＰＱの前段の複数のボックスとして示されている。これは、アドミッション制御ステージ及びＳＰＱも実装する点で、マクロネットワークに使用されるＲＣＳＰに幾分、類似している。しかしながら、ＲＣＳＰの場合、アドミッションはチャンネルのローカルタイミングに基づいている（優先順位毎に適格な送信時刻がスケジュールされる）。これは、時間の概念を全く持たない完全な非同期システムでは不可能である。
【００６８】
ＳＰＱの待ち時間の限界が無効にされないようにＡＬＧアドミッション制御により実現されるべき条件は、所定の（高い優先順位の）ＶＣ上のフリットが別の（低い優先順位の）ＶＣにおけるフリットを１回だけストールできるというものである。これは、１つのフリットが所定のＶＣ上へのアクセスを競っているときに、ＳＰＱ内で待機している複数のフリットに注目することによって達成され得る。低い優先順位の複数のＶＣ上にあるフリットの待ち時間保証を無効にしないために、所定のＶＣ上にある先行するフリットがＳＰＱ内で順位を与えられている間に待機し続けている全てのフリットは、新たなフリットがアドミッションを得る前にサービス処理がされなければならない。これは、フリットがリンク上で送信されているときにＳＰＱの占有をサンプリングすることによって保証される。同じＶＣ上の新たなフリットは、その時点でＳＰＱ内で待機している全てのフリットがサービス処理がされると、アドミッションを得ることができる。従って、低い優先順位のＶＣ上にあるフリットは、高い優先順位の各ＶＣ上のフリットにより最大で１フリット時間だけストールされる。所定のフリットがリンクへのアクセスが許可される場合、ＳＰＱ機能の定義により、高い優先順位のＶＣ上にあるフリットは全て既にサービス処理がされていることになり、存在するフリットは低い優先順位のＶＣ上で待機しているものだけになる点に留意されたい。
【００６９】
図４は、ＡＬＧを例示したものであり、Ｂ及びＣの待ち行列の待ち時間保証が如何にして満たされるかが分かる。Ａの待ち行列には、多すぎるフリットが到着し、よって、アドミッション制御により抑制が行われている。Ａのフリットは先行するリンク上へ極めて迅速に（保証されている待ち時間の限界より高速で）送信されているので、Ａにおけるバーストの理由は、ネットワークにおけるより早いポイントにおいて見出すことができるものと思われる。
【００７０】
２．３．ＡＬＧの待ち時間及び帯域幅保証
このセクションでは、基本的なＡＬＧ接続により提供される待ち時間及びＢＷ保証について述べる。結果は、セクション３．４において正式に演繹されるであろう。ＡＬＧのサービス保証は、接続のために予約される各ＶＣの優先順位のレベル及び各リンク上のＶＣの合計数によって特徴づけられる。優先順位のレベルＱ１，Ｑ２，…，ＱＸを有する複数のＶＣがＡＬＧリンク１，２，…，Ｘのシーケンス上に予約されている接続について考察する。各リンクは、複数Ｎ個のＶＣを実装している。これらのリンクは、リンクアクセス時間に関してＱ１，Ｑ２，…，ＱＸフリット時間の限界を提供している。これは、ソースにおいてフリット間隔、即ちｔｉｎｔｅｒｖａｌ≧Ｎ＋Ｑｍａｘ−１フリット時間が尊重されるという条件下でのことである。ここで、ＱｍａｘはＶＣシーケンス上の最大のＱ値である。これは、セクション４．４において導出される、いわゆる間隔条件である。間隔条件は、接続のアクセスレート保証でもあり、よって、接続のＢＷ保証を全リンク容量の一部：ＢＷｍｉｎ＝ＢＷｍｉｎ［Ｑｍａｘ］＝ＢＷｌｉｎｋ／（Ｎ＋Ｑｍａｘ−１）として特徴づける。
【００７１】
重要な点は、ＡＬＧにより提供される待ち時間保証はＢＷ保証から分離されるという事実に注目することである。リンク上のＶＣの数であるＮが増加すると、ＢＷ保証は任意に少なくなる可能性があるが、リンクアクセス時間は依然として１フリット時間への低下に維持される。従って、例えば割込みである低いＢＷニーズを有する待ち時間臨界接続は、ＢＷの過剰割当ての必要なしにサポートされる。
【００７２】
ＴＤＭ型のＢＷ割当てに基づくＮｏＣの既存の（同期）ＧＳ規律は、１ホップ当たり１フリット時間の待ち時間を実現するが、最初の接続アクセス待ち時間は、依然として合計のエンド・ツー・エンドの待ち時間をＢＷ保証に対して反比例させる。ＡＬＧは、間隔条件が満たされる限り、ＧＳ接続への即時のアクセスを提供する。また、非同期ネットワークにおける１ステージ当たりの転送待ち時間はごく短くされてもよく、同様の同期回路のクロックサイクルより遙かに短くされてもよい点に留意することもできる。このように、ＡＬＧは待ち時間に関して限界を保証するが、非同期ＮｏＣも潜在的に遙かに低い最小待ち時間を有する。同期回路ではなく非同期回路を使用するＮｏＣを実装する主たる優位点は、このことにある。
【００７３】
２．４．証明
以下、ソースにおいて間隔条件が尊重されれば、エンド・ツー・エンドの接続待ち時間に関する限界を定め得ることを証明する。アドミッション制御はフリットを保持するかもしれないが、そのフリットがそのグローバルなスケジュールより進んでいる場合に限られ、ローカルに観察されるフリット間隔は短縮されることになる。証明は、２つの部分から成る。第１部では、ＡＬＧ規律が単一のリンクに作用することを証明する。はじめに、接続上に送信される第１のフリットが待ち時間の必要条件に適合する、又はデッドラインに間に合うことを示す。次に、デッドラインに間に合ったフリットに続く、間隔条件を固守する任意のフリットもまたそのデッドラインに間に合うことを示し、これから間隔の値に到達する。間隔条件を固守する全てのフリットは、帰納法によりそのデッドラインに間に合う。証明の第２部では、ＡＬＧリンクに関して、ソースにおいて間隔条件が尊重されていれば、フリットは各リンクでそのデッドラインに間に合うことを示す。従って、接続のエンド・ツー・エンド待ち時間は、ネットワーク内部で間隔条件が無効にされることに関わらず、各リンク上の待ち時間保証の総和によって限界を付けられる。
【００７４】
単一リンクの定理：複数Ｎ個のＶＣを実装するＡＬＧリンク上では、ＶＣ  Ｑ上の全てのフリットは、フリット間隔条件ｔｉｎｔｅｒｖａｌ≧Ｎ＋Ｑ−１フリット時間の下で、最大のリンクアクセス時間であるＱフリット時間を保証される。
【００７５】
証明：それぞれがＳＰＱにおける優先順位のレベル１，２，３，…，Ｎに対応する複数Ｎ個のＶＣを実装する所定の１つのリンクをとり挙げる。所定のＶＣ  Ｑ∈｛１，…，Ｎ｝上に到着する第１のフリットは、ＳＰＱへのアクセスがただちに許可される。ＳＰＱにおいて、これは、リンクへのアクセスが許可されるまでに最大でＱフリット時間だけ待機する。従ってこれは、Ｑフリット時間の最大のリンクアクセス時間により限界を付けられるそのデッドラインに間に合う。
【００７６】
次に、Ｑ上の、ＳＰＱへのアクセスがただちに許可され、よってそのデッドラインに間に合うフリットＡと、フリットＡに続く、同じくＱ上のフリットＢについて考察されたい。フリットＢは、フリットＡからｔｉｎｔｅｒｖａｌフリット時間だけ後に到着する。フリットＡは、ＳＰＱへアクセスするために０フリット時間だけ待機し、かつＳＰＱ内で最大でＱフリット時間だけ待機する。フリットＡがリンクへのアクセスが許可されたとき、ＳＰＱ内では、Ｑより低い優先順位にあるＶＣの数である最大でＮ−Ｑ個のフリットが待機していた。ＡＬＧ規律によれば、これらは全て、Ｑ上の次のフリットがＳＰＱへのアクセスが許可される前に送信されなければならない。最悪の場合のシナリオでは、Ｑより高い優先順位のＶＣの数である最大でＱ−１個のフリットが、Ｑのアドミッション制御がフリットＢによるＳＰＱへのアクセスを許可する前に送信されなければならないＮ−Ｑ個のフリットより高い優先順位をとりうる。これらの部分遅延の合計は、Ｑ上の１つのフリットとＳＰＱへのアドミッションが与えられる次のフリットとの間で経過し得る最大時間を示し、Ｑ＋（Ｎ−Ｑ）＋（Ｑ−１）＝Ｎ＋Ｑ−１になる。これは、ｔｉｎｔｅｒｖａｌ≧Ｎ＋Ｑ−１フリット時間であれば、フリットＢは確実にＳＰＱへのただちにアクセスが許可されてＳＰＱ内において最大でＱフリット時間だけ待機し、これもまたそのデッドラインに間に合うことを意味する。従って、間隔条件下では、そのデッドラインに間に合ったフリットに続く任意のフリットは、それ自体もそのデッドラインに間に合い、かつ第１のフリットはそのデッドラインに間に合うので、帰納法により、全てのフリットはそのデッドラインに間に合う。
【００７７】
次に、ＡＬＧリンクのシーケンスに関して、間隔条件がネットワークに導入されるジッタに起因して局地的に無効にされるとしても、ＡＬＧは、全てのフリットが各リンクでそのデッドラインに間に合うことを保証する点を示す。従って、エンド・ツー・エンド待ち時間限界は、各リンクにおける待ち時間限界の総和である。この時点では、依然として、ノードには常に十分なバッファスペースが存在することを仮定している。セクション５では、バッファの必要条件を計算してこの証明を補強する。
【００７８】
リンクのシーケンスの系（Ｃｏｒｏｌｌａｒｙ）：常に十分なバッファスペースが存在するという仮定の下では、それぞれが複数Ｎ個のＶＣを実装する複数Ｘ個のＡＬＧリンクのシーケンス上に予約されたＶＣであるＱ１，Ｑ２，…，ＱＸを有する所定の接続の場合、待ち時間の限界は、ソースにおいてフリット間隔ｔｉｎｔｅｒｖａｌ≧Ｎ＋Ｑｍａｘ−１フリット時間が尊重されるという条件下で、各リンクにおける待ち時間限界の総和である。ここで、Ｑｍａｘは｛Ｑ１，Ｑ２，…，ＱＸ｝の最大値である。
【００７９】
証明：問題の接続上にあり、ＶＣ  Ｑ∈｛Ｑ１，Ｑ２，…，ＱＸ｝が予約されているリンク、及び上記リンク上でそのデッドラインに間に合った上記接続上のフリットＡについて考察されたい。このフリットはそのデッドラインに間に合ったので、上述の単一リンクの定理の証明に従って、アドミッション制御は、同じＶＣ上で、フリットＡがＳＰＱへのアクセスが許可された後、最大でＮ＋Ｑ−１フリット時間の後、進行中のフリットＢのＳＰＱへのアドミッションのために開く。フリットＡは、そのデッドラインに間に合ったので、スケジュール通りであったか、スケジュールより進んでいた。フリットＢは、スケジュールに関してフリットＡよりさらに先に進んでいれば、フリットＡがＳＰＱへのアクセスが許可された後に、Ｎ＋Ｑ−１フリット時間より少ない間隔で到着し、アドミッション制御は、そのＳＰＱへのアクセスをただちには認めない可能性もある。フリットＡがアクセスを許可された後、最も遅いＮ＋Ｑ−１フリット時間で、フリットＢは確実にアクセスが許可される。ソースにおいて、これらの分離間隔はＮ＋Ｑｍａｘ−１フリット時間であった。この時点では、この分離間隔は同じであるか短くなり、よって、フリットＢのスケジュールは少なくともフリットＡと同程度に先に進むことになる。従って、フリットＢもまたそのデッドラインに間に合う。反対に、ネットワーク内のより早いステージにおける輻輳に起因してフリットＢのスケジュールがフリットＡより遅れていれば、フリットＢは、フリットＡがＳＰＱへのアクセスが許可されて以降、Ｎ＋Ｑｍａｘ−１フリット時間より後に到着する。従って、これはただちにアクセスが許可され、そのデッドラインに間に合う。
【００８０】
接続上に送信される第１のフリットは、どのリンクのアドミッション制御においてもストールされないので、そのデッドラインに間に合う。そのデッドラインに間に合うフリットに続くフリットは何れも、それ自体もそのデッドラインに間に合うので、帰納法により、上記接続上の全てのフリットは全てのリンクにおいてそのデッドラインに間に合う。
【００８１】
維持できる最小のＢＷは、これから生じる：
【００８２】
最小帯域幅の系：それぞれが合計帯域幅ＢＷｌｉｎｋを提供する複数Ｘ個のＡＬＧリンクのシーケンス上に留保された複数個のＶＣであるＱ１，Ｑ２，…，ＱＸを有する所定の接続上では、維持される最小帯域幅は、ＢＷｍｉｎ＝ＢＷｌｉｎｋ／（Ｎ＋Ｑｍａｘ−１）になる。ここで、Ｑｍａｘは｛Ｑ１，Ｑ２，…，ＱＸ｝の最大値である。
【００８３】
証明：上記リンクのシーケンスの系に従って、１つのＡＬＧ接続上にある、間隔条件ｔｉｎｔｅｒｖａｌ≧Ｎ＋Ｑｍａｘ−１フリット時間を固守する全てのフリットは、限界を付けられた待ち時間を有する。従って、複数のフリットのストリームは、リンクによりサポートされる合計フリットレートの少なくとも１／（Ｎ＋Ｑｍａｘ−１）のフリットレートで輻輳の発生なく送信されてもよい。これから直接、維持できる帯域幅は少なくとも、ＢＷｍｉｎ＝ＢＷｌｉｎｋ／（Ｎ＋Ｑｍａｘ−１）であることが得られる。
【００８４】
３．バッファ
前のセクションでは、フリットが、ＡＬＧリンクのアクセススケジューリング規律のみによって制約されてネットワーク内を自由に流れると仮定していた。この作業は、フリットが絶対にドロップされない損失なしのネットワークを目標にしているので、各リンクは、受信側が自由なバッファ空間を有している場合にのみＶＣ上で１つのフリットが送信され得ることを保証するバック・プレッシャ・フロー制御も実装しなければならない。これは、アドミッション制御の余分な層、即ち図３に示すＶＣ制御を導入する。ＶＣ制御はＡＬＧアドミッション制御及びＳＰＱを包み込み、受信側のＶＣバッファが空のスペースを有することを示している場合にのみフリットを通させる。フリットは、リンクの受信側へ自由に移動できる場合にのみ、ＡＬＧアドミッション制御へ呈示されなければならない。そうでなければ、ＡＬＧ規律により提供される待ち時間保証は、リンク上でストールするフリットによって無効にされることがある。逆に、フリットはＶＣ制御により、デッドラインに間に合わず、やはりＡＬＧ待ち時間保証を無効にするほど過分に遅延されてはならない。
【００８５】
この作業では、共有ベースのＶＣ制御を使用する。図６に示す方法は、ＶＣ当たり１本のワイヤを使用して、例えばリンクである共有媒体への非ブロッキングのアクセスを実現している。共有ボックスは、１つのフリットにアドミッションを与えた後にロックし、別のフリットが通ることを許可しない。上記１つのフリットは、向こう側の非共有ボックスへこの媒体を通って進む。非共有ボックスはラッチを実装し、フリットはラッチへと受け入れられる。フリットが非共有ボックスを出るときは、アンロック制御ワイヤがトグルする。これにより共有ボックスはアンロックされ、別のフリットに媒体へのアドミッションが与えられる。媒体がデッドロックしない限り、フリットは媒体内でストールしない。
【００８６】
図５に示すように、接続を複数のＡＬＧリンクのシーケンスとしてモデル化し、入力ポートと上記接続のために予約されたＶＣバッファとの間に直接の回線が存在する。この仮定は、非ブロッキングのスイッチングを実装するルータアーキテクチャに関して有効である。図中のＶＣバッファは、その入力に非共有ボックスを実装しかつ出力に共有ボックスを実装している。関連する待ち時間は、１つのフリットがリンクへのアクセスが許可されるのに要する時間であるリンクアクセス待ち時間ｔａｃｃｅｓｓと、リンクアクセスが許可されるとルータからリンクを介して次のＶＣバッファへ至る１つのフリットの待ち時間であるリンク転送待ち時間ｔｌｉｎｋと、アンロック信号が前のＶＣバッファ内の共有ボックスへ戻るのに要する時間であって、別のフリットへリンクへのアクセスを許可してもよいことを示すアンロック待ち時間ｔｕｎｌｏｃｋとである。輻輳が発生しないので、リンクアクセス待ち時間以外の待ち時間は全て一定である。それぞれが複数Ｎ個のＶＣを実装する複数Ｘ個のＡＬＧリンクのシーケンスより成る接続の、エンド・ツー・エンドの待ち時間限界は、セクション３で述べたｔｔｏｔａｌ、即ち、ｔｅｎｄ２ｅｎｄ＝ｔａｃｃｅｓｓ１＋ｔｌｉｎｋ１＋ｔａｃｃｅｓｓ２＋ｔｌｉｎｋ２＋…＋ｔａｃｃｅｓｓＸ＋ｔｌｉｎｋＸと同様である。単純化のために、本明細書では、全リンク上でＮを同じであるものとしている。リンクアクセス時間は、各リンクにおいて予約されているＶＣの優先順位、Ｑ１，Ｑ２，…，ＱＸにより決定され、ｔａｃｃｅｓｓ１＝Ｑ１フリット時間、ｔａｃｃｅｓｓ２＝Ｑ２フリット時間、等々となる。接続上の最大のＱであるＱｍａｘは、パスのボトルネック、即ちＢＷｍｉｎ＝ＢＷｌｉｎｋ／（Ｎ＋Ｑｍａｘ−１）であるので、セクション４．３に従って接続のＢＷ保証の必要条件である。
【００８７】
ここで、フリットがＳＰＱへアクセスできるほど機が熟したとき、即ち、フリットがそのスケジュールより０時間進んでいるときには、共有ボックスが常にアンロックされるという必要条件を決定する必要がある。そうであれば、フリットはＡＬＧアドミッション制御へ提示され、ＡＬＧ規律に従って、そのデッドラインに間に合う。以下、フリット間隔条件及びｔｌｉｎｋ＋ｔｕｎｌｏｃｋ＜Ｎ−１フリット時間というリンクサイクル条件下でＡＬＧスケジューリング規律を正しく機能させるには、単一エレメントのＶＣバッファで足りることを証明する。
【００８８】
単一バッファの定理：フリット間隔条件ｔｉｎｔｅｒｖａｌ≧Ｎ＋Ｑｍａｘ−１フリット時間及びリンクサイクル条件ｔｌｉｎｋ＋ｔｕｎｌｏｃｋ＜Ｎ−１フリット時間の下では、リンクのシーケンスの系の有効性を保証するためには、各ノードにおける各ＶＣにつき単一エレメントのフリットバッファで足りる。
【００８９】
証明：図５に示すように、それぞれが複数Ｎ個のＶＣを実装する複数のＡＬＧリンクのシーケンス上に予約された複数のＶＣ（…，Ｑｉ，Ｑｊ，…）を有する接続の１つのセクションについて考察されたい。ＶＣバッファであるＶＣｂｕｆｉ及びＶＣｂｕｆｊはそれぞれ、１フリット分のバッファスペースを有する。リセット時は、これらは空であるので、接続上で送信される第１のフリットはＶＣ制御によって制限されず、ＡＬＧ規律に従ってそのデッドラインに間に合う。ここで、そのデッドラインに間に合うように進行中のフリットＡに続く、フリットＢについて考察されたい。フリットＡは、そのデッドラインに間に合いつつあるので、遅くとも、それがそのスケジュールより０時間進んでいることに対応する時間０においてＳＰＱｊへのアクセスを取得する。この時点で、ＶＣｂｕｆｊはＶＣｂｕｆｉに別のフリットを受け入れる準備が整っていることを信号で伝える。従って、ＶＣｂｕｆｉは、時間ｔｕｎｌｏｃｋの後に、次のフリットであるフリットＢのためにその出力を開放する。フリットＡは、遅くとも時間０−ｔｌｉｎｋにはＳＰＱｉを出発しているので、ａｄｍ１は０−ｔｌｉｎｋ＋Ｎ−１＝Ｎ−１−ｔｌｉｎｋフリット時間以内にはフリットＢがＳＰＱｉへ入ることを許可する。この時間が、ＶＣｂｕｆｉがフリットＢを通過させた後であれば、ＶＣｂｕｆｉはそのフローにとっての制限ファクタとならない。従って、ＶＣ制御が制限ファクタにならないための必要条件は、Ｎ−１−ｔｌｉｎｋ＞ｔｕｎｌｏｃｋ＝＞ｔｌｉｎｋ＋ｔｕｎｌｏｃｋ＜Ｎ−１フリット時間となる。これは、リンクサイクル条件を構成する。このリンクサイクル条件が成立すれば、フリットＢは、時間：Ｑ１＋ｔｌｉｎｋ＋Ｎ−１−ｔｌｉｎｋ＝Ｑ１＋Ｎ−１フリット時間にＶＣｂｕｆｊに到着する。これは、必要とされるフリット間隔であるＱｍａｘ＋Ｎ−１フリット時間以下である。よって、フリットＢはそのスケジュールに間に合ってａｄｍｊに到着した。
【００９０】
ソースにおける、最小のフリット間隔がＱｍａｘ＋Ｎ−１フリット時間という間隔条件の下、及びｔｌｉｎｋ＋ｔｕｎｌｏｃｋ＜Ｎ−１フリット時間というリンクサイクル条件の下では、そのデッドラインに間に合ったフリットに続く任意のフリットもまたそのデッドラインに間に合う。第１のフリットがそのデッドラインに間に合うので、帰納法により、その接続上の全てのフリットはそのデッドラインに間に合う。
【００９１】
４．帯域幅の割当て
これまでに述べたように、ＡＬＧリンクは、その基本形式においてフレキシブルな待ち時間保証を提供する。ＶＣは、達成されるべき接続の待ち時間の必要条件にその優先順位が対応するものが選択されてもよい。しかしながら、帯域幅保証は、選択されるＶＣの優先順位に従って確定される。また、異なる優先順位の中でも、ＢＷはさほど異ならず、最も高い優先順位の１／Ｎから、最も低い優先順位の１／（２Ｎ−１）までの範囲である。以下、基本的なＡＬＧ構成のフレキシブルな待ち時間保証をなお享受しつつ接続へのフレキシブルなＢＷ割当てを達成するための３つの方法について説明する。
【００９２】
第１の方法（マルチチャンネル方法）は、単一の接続への各リンクに幾つかのＶＣが割り当てられる自明な方法である。これは事実上、実際には幾つかの「並行する」接続であって増大されたデータ容量を有する接続を生成する。その使用は、各リンクで局所的に扱われてもよく、ネットワークアダプタにおいてエンド・ツー・エンド・ベースで扱われてもよい。ＢＷのこの割当て方法における優位点は、理解及び実装が容易であることにある。また、フリットはバーストで到着する（間隔はほとんどない）。最初のＸ個のフリットは、独立してバッファされる別々のＶＣシーケンス上で送信される。ここで、Ｘは各リンクにおいてその接続のために割り当てられるＶＣの数である。従って、これら全ての待ち時間は、高い優先順位のＶＣを選択することによって極めて短くされてもよい。パケット全体に極めて低い合計待ち時間の保証が与えられるので、これは、小さいパケットの主要な優位点である。ＯＣＰインタフェース等のバスタイプ（メモリがマップされた）のアクセスソケットを有するネットワークでは、単純なＯＣＰコマンドを運ぶ大部分のパケットは、３２ビットのネットワークでは、２つから３つのフリットより成る。このようなパケットにおけるフリットの数に対応する幾つかのＶＣシーケンス又は集合を割り当てることにより、これらのコマンドの転送待ち時間は、割り当てられるＶＣ集合のうちで最も遅いＶＣ集合のＡＬＧ待ち時間にまで短縮される。この方法の欠点は、リンクのエリアの必要条件が多かれ少なかれＢＷの粒度に対して線形に増大し、上記エリアは、主としてフリットバッファによって決定されていて、各ＶＣが１つのフリットバッファを必要とするので、ＢＷの粒度はＶＣの数に対してほぼ非線形である、という事実にある。また、広範なＳＰＱも必要とされる。これは、ＳＰＱのパフォーマンスを低下させ、本実施形態ではＳＰＱはリンクのボトルネックであるので、これによりフリット時間が短縮する。
【００９３】
第２及び第３の方法は、より多くのバッファスペースを実装することなく、基本的なＡＬＧアドミッション制御方法により、１つの優先順位が通常許可されるより多いアクセスを許可するという基本概念を軸に展開する。従って、１つのＶＣはＳＰＱへのアクセスがより頻繁に許可されるので、このＶＣのスループットは増大する。しかしながら、複数のフリットが独立して始動することはできないために、接続上の複数フリットのパケットの合計待ち時間は第１の方法に比較して長い。複数のフリットはネットワークを介して同じバッファシーケンスを使用するので、１つのフリットは直前のフリットが接続の直前のノードにおけるバッファを去るのを待機しなければならないという事実に起因して、複数のフリットは接続上において、無視できない分離を有する。
【００９４】
第２の方法（マルチアドミッション制御方法）によれば、各ＶＣは幾つかのアドミッション制御を有する。これらのうちの任意の１つが非待ち受けであれば、フリットはアドミッションを与えられてもよい。次に、上記フリットにアドミッションを与えたアドミッション制御（より多くが非待ち受けであれば、これらのうちの任意の１つが上記フリットにアドミッションを与えた「その１つ」であるとして選ばれてもよい）は、それがアドミッションを与えたフリットの送信時に、基本的なＡＬＧスケジューリングの方法に関して上述した方法に従って、ＳＰＱの低い優先順位の占有をサンプリングする。各ＶＣは、それが実装する（又はアクティブである）各アドミッション制御ステージにつき一度、低い優先順位のＶＣの送信を潜在的にブロックすることができるので、これらの待ち時間保証が適宜低減されることが分かる。従って、ＶＣの待ち時間保証は、高い優先順位のＶＣの数ではなく、高い優先順位のＶＣのアクティブなアドミッション制御ステージの合計数に関連する。本方法は、基本的なＡＬＧリンクにおける２つ以上の異なる優先順位の使用へのアクセスを有しかつ単にアドミッションに対してオープンであれば何れをも選択するフリットバッファに対応する。しかしながら、複数の優先順位は絶対に同期的には使用されないので（フリットバッファが１つしか存在しないため）、これらは等しい待ち時間保証を経験し、２つの優先順位のうちの高い方に従って、絶対に互いにブロックし合わない。
【００９５】
各リンクでは、フリットは、次のノードにおけるフリットバッファが空である場合にのみ送信されてもよい。即ち、フリットは、先行するフリットが先行するリンク上で送信された後でなければ送信され得ない。これは、分離条件を発生させる。フリットは、次のノードではアドミッション制御によってブロックされない、即ち上記フリットは、そのスケジュールより先に進んでいないこと、即ち、ｔ＿（分離）＝ｔ＿（リンク）＋Ｑ（先行する＿リンク）＋ｔ＿（アンロック）、を仮定する。先に示した間隔条件とは異なり、分離条件はＮとは独立である点に留意されたい。間隔条件は依然として各アドミッション制御ステージを求めるが、接続上のフリットのストリームに適用される分離条件とは独立している。従って、ＶＣが２つのアドミッション制御ステージを実装すれば、即ち、ｔ＿（間隔）≧２×ｔ＿（分離）であれば、所定のＶＣについて２倍のＢＷが得られる。これは、図５のリンクサイクル条件に対応する。ｔ＿（間隔）＜２×ｔ＿（分離）であれば、フリットは、間隔条件よりも分離条件によってより厳しい制限を受けるので、２倍未満のＢＷが保証される。従って、達成可能な最大帯域幅は、リンクサイクル条件及びこの条件の倍数の間隔条件による「バランス」によって決定される。
【００９６】
ここで言うＱは、ＳＰＱの優先順位と同等のものではなく、高い優先順位のＶＣのアクティブなアドミッション制御ステージの合計数に１を加算して計算されたＱであることに留意されたい。
【００９７】
第３の方法（アドミッション制御計数法）によれば、アドミッション制御ステージによる占有（及び、低い優先順位のＶＣで待機中のものが存在すれば、後続の近接アクセスも）のサンプリングは、その優先順位でフリットが送信される毎にではなく、Ｘ回目毎に行われるだけである。実際には、フリットのバーストは、アドミッション制御が開放する（非待ち受けになる）度に送信されてもよい。バーストの最後のフリットの後、アドミッション制御は閉止し、低い優先順位のＶＣの占有をサンプリングし、送信を待機中のフリットにより占有されているものを待機する。従って、低い優先順位ＶＣの各フリットは、潜在的に、この特定の（高い優先順位の）ＶＣをＸ回待機しなければならない。従って、その待ち時間保証は低減される。マルチアドミッション制御方法の場合と同様に、ＶＣが利用可能な帯域幅の増大は、低い優先順位のＶＣの待ち時間を犠牲にして達成される。
【００９８】
５．実装
図３によれば、基本的なＡＬＧリンクは、ＶＣ制御、アドミッション制御及びＳＰＱという３つの基本的なサブシステムから成る。
【００９９】
５．１．ＶＣ制御
採用されているＶＣ制御方法の機能性については、セクション４で説明した。図７は、１つのＶＣの共有ボックス及び非共有ボックスの実装を示す略図である。１本のワイヤのアンロック信号は、２相の肯定応答として機能する。ｐｕｌｓｅ＿ｇｅｎにより発生されるパルスは、Ｃエレメントのｃ＿ｌｏｃｋをリセットするに足る長さでなければならない。共有ボックスの出力におけるｏｕｔｐｕｔ＿ｄｅｃｏｕｐｌｅ回路は、ＶＣから共有媒体を分離する。従って、個々のＶＣが遅いことに関わらず、フリットの自由な流れが保証される。
【０１００】
５．２．アドミッション制御
ＡＬＧスケジューリングの新規性はアドミッション制御ステージに見いだされ、アドミッション制御ステージはＳＰＱが適切な待ち時間限界を規定することを許容しながら、フリットの流れを制御する。
【０１０１】
アドミッション制御の各チャンネルは、低い優先順位のチャンネル毎に１ビットのステータスレジスタを実装する。所定のチャンネルの少なくとも１つのステータスビットが設定されると、アドミッション制御は、そのチャンネル上でのフリットのＳＰＱへのアドミッションを停止する。そのチャンネル上のフリットがリンクへのアクセスが許可されると、ＳＰＱの占有のスナップショットに従ってステータスビットが設定される。占有は、所定のチャンネルが（優先順位を付けられている）リンクへのアクセスが許可される間に、どのチャンネルがＳＰＱ内で待機中のフリットを有するかを指定する。ステータスビットは、これらの待機中のフリットがリンクへのアクセスが許可されるときに、引き続いてリセットされる。全てのフリットが送信されると、ステータスビットは全てクリアになり、アドミッション制御は上記所定のチャンネル上の別のフリットにアドミッションを与える。
【０１０２】
図８は、チャンネルｎのアドミッション制御を示す略図である。低い優先順位のチャンネルのそれぞれには、１つのステータスビットレジスタ［ｎ−１…０］がＲＳラッチとして実装される。チャンネルｎは、所定の時点でリンクへのアクセスを競う最も高い優先順位のチャンネルであると考える。ＳＰＱは占有ベクトルを生成し、ｎの肯定応答がハイである間は、その値は安定している。ステータスビットレジスタのセット入力は、ｎの肯定応答及び占有ベクトルの論理和である。このようにして、適切なステータスビットは、上記チャンネルがリンクへのアクセスが許可される時点（その上昇する肯定応答により示される）のＳＰＱの占有に従って設定される。ステータスビットレジスタのリセット入力は、単に対応するチャンネルの肯定応答信号へ接続される。１つのチャンネルがリンクへのアクセスが許可されると、その肯定応答はハイになり、これにより、このチャンネルに対応するステータスビットは、高い優先順位のチャンネルのそれぞれのアドミッション制御においてリセットされる。全てのステータスビットがローであれば、入力要求は出力へ伝搬することを許容される。ローカルな肯定応答はステータスビットを設定させるので、要求パスにおいては、ＡＮＤゲートではなくＣエレメントが必要とされる。これは、入力要求がローにされるまで出力要求はローにされないことを保証する。
【０１０３】
所定の時間においてリンクへのアクセスを得ることのできるチャンネルは１つのみであるので、ステータスビットレジスタのセット及びリセットは互いに排他的であることに留意されたい。
【０１０４】
５．３．静的優先順位付き待ち行列
図１０は、出願人によるＳＰＱアービタ及び付随するマージデータパスの非同期の実装を示す。主要な制御信号は、「イネーブル」である。リセット時には、「イネーブル」はローである。「イネーブル」はアービタのアクティブフェーズを示すので、「イネーブル」がハイである間は、入力における非対称のＣエレメントは、内部の要求信号がローにされないことを保証する。ミューテックス（ｍｕｔｅｘ）は、いわゆるロックレジスタを実装する。少なくとも１つの入力要求がこれらの出力を介して伝搬すると、これは、「ａｎｙ＿ｒｅｑ」を発生するＯＲゲートによって検出され、イネーブルはハイレベルにされる。次に、これによりロックレジスタがロックされ、「イネーブル」がハイである限り、新たに到着する入力要求はブロックされる。これ以降、出力のＣエレメントのうちの正確に１つがファイアし、適切なチャンネルが肯定応答され、上記特定のチャンネルのデータが出力ラッチにおいて捕捉される。この時点で、「イネーブル」はローにされ、優先順位付けのフェーズの終わりが示される。「イネーブル」がローである限り、出力のＣエレメントの何れもファイアすることができないが、肯定応答されたチャンネルがその要求を取り下げ、かつリンクが出力要求を認識すると、対応するＣエレメントはリセットし、「イネーブル」に別の優先順位付けのフェーズを開始させる。
【０１０５】
ミューテックスの「ｇ１」出力は「ｇ２」出力より甚だしくは遅くないものと仮定すると、高速ＲＴＺ相が実現する。ＲＴＺに要求されることは、優先順位が付けられたチャンネルの「ｒ２」入力が「ｇ２」を介して出力Ｃエレメントへ伝搬することが全てである。ローにされる「ｇ２」が出力のＣエレメントを介して伝搬して入力へ戻り、イネーブルを再度ファイアする前に、「ｇ１」がローにされる限り、この仮定は安全である。「ｇ１」及び「ｇ２」を含む両方のＲＴＺタイミングパスは、「イネーブル」がローになるのに伴って始動する。ＳＰＱのサイクルは、ＶＣの数のあらゆるダブリングにおいて３つの２入力ゲート深さ（０．１２マイクロメートル技術で約３０〜４０ｐｓ）分だけ、即ち非対称のＣエレメントにおける１つと、完了を検出するＯＲゲートにおける２つ分が増大するだけである。
【０１０６】
アドミッション制御によりそのステータスビットの設定に使用される占有ベクトルは、イネーブル及びロックされる入力要求の論理和を構成する。すぐ前のセクションで指摘したように、このベクトルは、肯定応答がハイである間は安定していることが要求される。ロックされる要求ベクトルをイネーブルと論理和演算することにより、占有ベクトルのビットは、肯定応答がハイであるときに安定しているかローであることが保証される。ステータスビットレジスタはハイである占有ビットによって設定されるので、これで十分である。
【０１０７】
６．結果
市販の０．１２μｍのＣＭＯＳ規格セルを使用して、１６ビットの、８個のＶＣのＡＬＧリンクを実装した。典型的なタイミングパラメータを適用し、１．４ナノ秒のフリット時間に対応する７０２ＭＤＩ／秒の測度で設計をシミュレートした。共有の物理リンクは、３段パイプラインを実装している。リンク全体のセル面積、即ちプレレイアウトは０．０１２ｍｍ２であり、ＡＬＧスケジューラのコア（アドミッション制御及びＳＰＱ）は僅か０．００４ｍｍ２にした。これは、ＡＬＧの恩恵が面積に関しては全く高価でないことを示している。
【０１０８】
３つのＡＬＧリンクのシーケンス上の接続をエミュレートする試験セットアップをシミュレートした。接続は、高い優先順位のＶＣを予約する高速の接続及び低い優先順位のＶＣを予約する低速の接続の２つを観察した。他の全てのＶＣ上でランダムなバックグラウンドトラフィックが誘導される間に、フリットの待ち時間を記録した。図９は、１００００個を超えるフリットについて記録された異なるネットワーク負荷に対するフリット待ち時間の分布を示す。ネットワーク負荷が１００％であっても、接続上のフリットがそのデッドラインに間に合っている様子が分かる。ネットワーク負荷の増大に伴って、待ち時間の分布図は待ち時間限界へと押し上がるが、絶対に限界を超えない。転送待ち時間限界は、３．６ナノ秒／ホップから１．４ナノ秒（１フリット時間）の増分で上方へと取得可能である。これは、ＡＬＧアクセス待ち時間と、リンクに渡る一定の転送待ち時間（共有ボックス、マージ、パイプライン、スプリット及び非共有ボックス−約２．２ナノ秒）とを含む。ＢＷ保証は、高速の接続上で１／８×７０２ＭＤＩ／秒＝８８ＭＤＩ／秒であり、低速の接続上で１／１５×７０２ＭＤＩ／秒＝４７ＭＤＩ／秒であった。
【０１０９】
表１は、ＡＬＧの保証を、ＮｏＣに使用される既存のスケジューリング方法のそれと比較したものである。表において、Ｎは、各リンク上のＶＣの数であり、ｈは所定の接続によりスパンされたホップの数である。ＴＤＭは同期ＮｏＣにおいて使用され、ある種のエンド・ツー・エンド・フロー制御が実装されることを考慮すれば、接続待ち時間の限界をＮ＋ｈに規定している。この実装がなされなければ、待ち時間限界は、非同期フェアシェアのレベルまで、即ち（Ｎ＋１）×ｈまで低減される。本表は、ＡＬＧが待ち時間に関してより質の高い限界を規定すること、及びインスタンス化され得る様々なタイプの接続に関してＡＬＧが一般に、よりフレキシブルであることを示している。
【０１１０】
【表１】
2008532145.tif 000003
【図面の簡単な説明】
【０１１１】
【図１】独立してクロック同期された複数のコア同士を接続する非同期ネットワークが大規模ＳｏＣ設計におけるモジュール性を促進することを示す。
【図２】仮想チャンネルＡ乃至Ｄが１つの物理リンクを共用する基本的なリンクを示す。
【図３】静的優先順位付き待ち行列（ＳＰＱ）がリンクへのアクセスに優先順位を付けて待ち時間保証を提供し、アドミッション制御はフリットのフローがＳＰＱにより要求される条件を固守することを確実にし、ＶＣ制御は非ブロッキングの振る舞いを保証する、好適な実施形態に係る完全リンクを示す。
【図４】図３のリンクのオペレーション例を示す。
【図５】接続により予約されるＶＣのシーケンスの１つのセクションのモデルである。
【図６】共有ベースのＶＣ制御を示す。
【図７】共有ボックス及び非共有ボックス概略的に示す。
【図８】アドミッション制御を概略的に示す。
【図９】（ａ）は低速パスのフリット待ち時間の分布とネットワーク負荷との関係を示し、（ｂ）は高速パスのフリット待ち時間の分布とネットワーク負荷との関係を示す。
【図１０】ＳＰＱアービタ及び付随するマージデータパスの好適な非同期実装を示す。
【図１】
2008532145.tif 000004
【図２】
2008532145.tif 000005
【図３】
2008532145.tif 000006
【図４】
2008532145.tif 000007
【図５】
2008532145.tif 000008
【図６】
2008532145.tif 000009
【図７】
2008532145.tif 000010
【図８】
2008532145.tif 000011
【図９】
2008532145.tif 000012
【図１０】
2008532145.tif 000013
【国際調査報告】
2008532145.tif 000014
2008532145.tif 000015
2008532145.tif 000016