(57)【要約】  集積回路は、複数のデータ処理回路（１０）と、データ処理回路（１０）の間に結合された通信ネットワーク（１２）とを含む。通信ネットワーク（１２）は、接続（１２２）と、接続（１２２）の間に結合されたルータ回路（１２０）とを含む。それぞれのデータ・ストリームのためにプログラムされたそれぞれの経路に沿って各それぞれのデータ・ストリームからの各データ・アイテムを伝送するようにルータ回路（１２０）を制御するための、接続（１２２）に沿ったそれぞれの経路の、そのそれぞれのデータ・ストリームのための定義を記憶するためにメモリが提供される。最初に、１組の元のデータ・ストリームのための初期経路が定義され、開始される。その後で、追加的なデータ・ストリームが追加されることができる。データ・ストリームが追加される場合、新たな経路が、元のデータ・ストリームのための将来の経路と組み合わせて選択される。新たな経路と将来の経路との組合せは、その組合せにおいて元のデータ・ストリームのうちの少なくとも１つのための初期経路が当該初期経路に対して再ルーティングされた少なくとも１つの組合せを含む選択可能な組合せから取得される。元のデータ・ストリームのうちの少なくとも１つのための初期経路は、選択された組合せ内でその元のデータ・ストリームのための経路が再ルーティングされる場合、元のデータ・ストリームのうちの当該少なくとも１つ以外のデータ・ストリームのデータ・アイテムの伝送を妨げることなく再プログラムされる。その後で、新たな経路に沿ってデータ・アイテムの伝送が開始される。
2008541677.tif 000002
【特許請求の範囲】
【請求項１】
複数のデータ処理回路と、
前記データ処理回路の間に結合され、接続と、前記接続の間に結合されたルータ回路とを含む通信ネットワークであって、前記通信ネットワークと、前記データ処理回路と、前記通信ネットワークおよび前記データ処理回路の間のさらなる回路との少なくともいずれか１つは、それぞれのデータ・ストリームのためにプログラムされたそれぞれの経路に沿って各それぞれのデータ・ストリームからの各データ・アイテムを伝送するように前記ルータ回路を制御するための、前記接続に沿った前記それぞれの経路の、そのそれぞれのデータ・ストリームのための定義を記憶するようにプログラム可能である、通信ネットワークと、
複数の元のデータ・ストリームのうちの少なくとも１つのための１つの経路または複数の経路を再ルーティングし、前記元のデータ・ストリームのうちの前記少なくとも１つのための前記１つの経路または前記複数の経路の前記再ルーティングによって空けられた接続を占有する新たな経路を新たなデータ・ストリームに対して選択し、前記元のデータ・ストリームのうちの前記少なくとも１つ以外の元のデータ・ストリームに関するデータ・アイテムの伝送を妨げることなく前記元のデータ・ストリームの前記１つの経路または前記複数の経路の定義を再プログラムし、前記新たな経路の定義をプログラムすることによって、前記元のデータ・ストリームの伝送が開始された後で前記元のデータ・ストリームに追加的なデータ・ストリームを追加する要求を満たすように構成された、前記それぞれの経路を選択し、プログラムするための、前記通信ネットワークと前記データ処理回路と前記さらなる回路との少なくともいずれか１つに結合されたスケジューリング回路と
を含む集積回路。
【請求項２】
前記スケジューリング回路は、選択されたタイム・スロットにおいて前記接続を前記それぞれのデータ・ストリームに割り当てるように構成され、前記元のデータ・ストリームはスロットの周期的に繰り返すパターンで前記経路内の前記接続を占有し、前記スケジューリング回路は、前記新たな経路が開始されたときに、前記パターンの前記スロットの使用を前記元のデータ・ストリームの前記少なくとも１つ以外の元のデータ・ストリームに関して途切れないままにするように構成されている請求項１に記載の集積回路。
【請求項３】
前記ルータ回路は、そのタイム・スロットにおいて前記データ・アイテムが前記ネットワークに入る開始タイム・スロットが、そのタイム・スロットにおいてデータ・アイテムがそれぞれの接続を占有するタイム・スロットを決定するように、受信されたデータ・アイテムを受信後に所定の遅延を用いて前記経路に沿って転送するように構成されている請求項２に記載の集積回路。
【請求項４】
それぞれが前記データ処理回路のそれぞれ１つまたはそれぞれの群に結合されたネットワーク・インターフェースを含み、各ネットワーク・インターフェースは、前記定義のうちの少なくとも１つを記憶するためのメモリを含み、前記ネットワーク・インターフェースは、それらのネットワーク・インターフェースのそれぞれのメモリ内の記憶された定義から得られたルーティング情報を前記データ・ストリームからのデータを含むデータ・アイテムに含めるように構成され、前記ルータ回路１２０は、前記ルーティング情報の制御の下で各データ・アイテムをルーティングするように構成され、前記スケジューリング回路は、前記新たな経路の始まりにある前記ネットワーク・インターフェースの前記メモリに新たな定義をプログラムすることによって前記新たな経路を実現し、再ルーティングされた１つの経路または複数の経路の１つの始まりまたは複数の始まりにある前記ネットワーク・インターフェースにおいて前記データ・ストリームのうちの少なくとも１つのための前記再ルーティングされた１つの経路または複数の経路に従って前記記憶された１つまたは複数の定義を置き換えるように構成され、前記ネットワーク・インターフェースは、前記定義のプログラムおよび再プログラムの後で前記新たな経路をアクティブ化する請求項２に記載の集積回路。
【請求項５】
前記スケジューリング回路は、前記スケジューリング回路の構成によって定義される選択可能な組合せから、前記元のデータ・ストリームと前記新たなデータ・ストリームとのための経路の組合せを選択するように構成され、前記選択可能な組合せは、その組合せにおいて前記元のデータ・ストリームのうちの前記少なくとも１つのための再ルーティングされた１つの経路または複数の経路が、前記元のデータ・ストリームのうちの前記少なくとも１つのための初期経路と同じ長さを有する組合せのみを含む請求項２に記載の集積回路。
【請求項６】
前記スケジューリング回路は、前記スケジューリング回路の構成によって定義される選択可能な組合せから、前記元のデータ・ストリームと前記新たなデータ・ストリームとのための経路の組合せを選択するように構成され、前記選択可能な組合せは、その組合せにおいて前記元のデータ・ストリームのうちの前記少なくとも１つのための再ルーティングされた経路が前記元のデータ・ストリームのうちの前記少なくとも１つのための初期経路よりも短い組合せを含まない請求項２に記載の集積回路。
【請求項７】
前記スケジューリング回路は、前記スケジューリング回路の構成によって定義される選択可能な組合せから、前記元のデータ・ストリームと前記新たなデータ・ストリームとのための経路の組合せを選択するように構成され、前記選択可能な組合せは、その組合せにおいて前記元のデータ・ストリームのうちの前記少なくとも１つのための再ルーティングされた経路が初期経路よりも短い組合せを含み、前記スケジューリング回路は、前記通信ネットワークに前記元のデータ・ストリームのうちの前記少なくとも１つに関する前記周期的に繰り返すパターンへ中断を挿入させ、その中断中、前記元のデータ・ストリームのうちの前記少なくとも１つのための前記再ルーティングされた経路を使用する最初の開始スロットが使用される前は、その開始スロットに前記元のデータ・ストリームのうちの前記少なくとも１つのための前記初期経路が関連する最後の開始スロットが占有されないままである請求項２に記載の集積回路。
【請求項８】
前記スケジューリング回路は、前記スケジューリング回路の構成によって定義される選択可能な組合せから、前記元のデータ・ストリームと前記新たなデータ・ストリームとのための経路の組合せを選択するように構成され、前記選択可能な組合せは、その組合せにおいて前記元のデータ・ストリームのうちの前記少なくとも１つのための再ルーティングされた経路が初期経路よりも短い組合せを含み、前記スケジューリング回路は、
新たな開始スロットと初期開始スロットとの間の距離が前記初期経路と前記再ルーティングされた経路との間の差と少なくとも同じである、前記元のデータ・ストリームのうちの少なくとも１つのための前記初期経路に対する前記初期開始スロットのための位置とは異なる、その元のデータ・ストリームのための前記再ルーティングされた経路に対する前記新たな開始スロットのための位置を選択し、
前記通信ネットワークに、前記新たな開始スロットにおける最初のデータ・アイテムを前記再ルーティングされた経路に沿って伝送する前に前記初期スロットの最後のインスタンスを未使用のままにさせる
ように構成されている請求項２に記載の集積回路。
【請求項９】
前記スケジューリング回路は、前記スケジューリング回路の構成によって定義される選択可能な組合せから、前記元のデータ・ストリームと前記新たなデータ・ストリームとのための経路の組合せを選択するように構成され、前記選択可能な組合せは、その組合せにおいて再ルーティングされた経路のうちの多くとも１つが初期経路と異なる組合せのみを含む請求項２に記載の集積回路。
【請求項１０】
前記スケジューリング回路は、前記スケジューリング回路の構成によって定義される選択可能な組合せから、前記元のデータ・ストリームと前記新たなデータ・ストリームとのための経路の組合せを選択するように構成され、前記スケジューリング回路は、その探索において、前記データ・ストリームのための経路のそれぞれの組合せが訪問され、競合する使用を持たない組合せが検出されるまで、前記スケジューリング回路が訪問された組合せが接続の競合する使用を含むかどうかを決定する探索を実行するように構成されている請求項２に記載の集積回路。
【請求項１１】
集積回路を動作させる方法であって、前記集積回路は複数のデータ処理回路と、前記データ処理回路の間に結合された通信ネットワークとを含み、前記通信ネットワークは接続と、前記接続の間に結合されたルータ回路とを含み、前記通信ネットワークと、前記データ処理回路と、前記通信ネットワークおよび前記データ処理回路の間のさらなる回路との少なくともいずれか１つは、それぞれのデータ・ストリームのためにプログラムされたそれぞれの経路に沿って各それぞれのデータ・ストリームからの各データ・アイテムを伝送するように前記ルータ回路を制御するための、前記接続に沿った前記それぞれの経路の、そのそれぞれのデータ・ストリームのための定義を記憶するようにプログラム可能であり、前記方法は、
１組の元のデータ・ストリームのための初期経路を定義することと、
前記元のデータ・ストリームのデータ・アイテムの伝送を開始することと、
その後で、その組合せにおいて前記元のデータ・ストリームの少なくとも１つのための初期経路が前記初期経路に対して再ルーティングされた少なくとも１つの組合せを含む選択可能な組合せから、前記元のデータ・ストリームのための将来の経路と組み合わせて選択される、追加的なデータ・ストリームのための新たな経路を特定することと、
選択された組合せにおいてその元のデータ・ストリームのための経路が再ルーティングされる場合に、前記元のデータ・ストリームのうちの前記少なくとも１つのための前記初期経路を前記元のデータ・ストリームのうちの前記少なくとも１つ以外のデータ・ストリームのデータ・アイテムの伝送を妨げることなく再プログラムすることと、
その後で、前記新たな経路に沿ったデータ・アイテムの伝送を開始することと
を含む、方法。
【請求項１２】
前記データ・ストリームのための前記接続を多重化するタイム・スロットを含み、前記元のデータ・ストリームはスロットの周期的に繰り返すパターンで前記初期経路内の前記接続を占有し、前記パターンは、少なくとも前記選択された組合せの一部でもある前記元のデータ・ストリームのスロットに対して、前記新たな経路の追加中の妨げなしに継続される請求項１に記載の方法。
【請求項１３】
前記元のデータ・ストリームと前記新たなデータ・ストリームとのための経路の組合せは、選択可能な組合せの定義済みの組から選択され、前記定義済みの組は、その組合せにおいて前記元のデータ・ストリームの前記少なくとも１つのための再ルーティングされた１つの経路または複数の経路が前記元のデータ・ストリームのうちの前記少なくとも１つのための前記初期経路と同じ長さを有する組合せのみを含む請求項１２に記載の方法。
【請求項１４】
前記元のデータ・ストリームと前記新たなデータ・ストリームとのための経路の組合せは、選択可能な組合せの定義済みの組から選択され、前記定義済みの組は、その組合せにおいて前記元のデータ・ストリームの前記少なくとも１つのための再ルーティングされた１つの経路または複数の経路が前記元のデータ・ストリームのうちの前記少なくとも１つのための前記１つの初期経路または複数の初期経路と同じか、またはそれよりも短い組合せを含まない請求項１２に記載の方法。
【請求項１５】
前記元のデータ・ストリームと前記新たなデータ・ストリームとのための経路の組合せは、選択可能な組合せの定義済みの組から選択され、前記定義済みの組は、その組合せにおいて、前記元のデータ・ストリームの前記少なくとも１つのための再ルーティングされた経路が前記初期経路よりも短い組合せを含み、前記元のデータ・ストリームのうちの前記少なくとも１つに関する前記周期的に繰り返すパターンへ中断が挿入され、その中断中、前記元のデータ・ストリームのうちの前記少なくとも１つのための前記再ルーティングされた経路を使用する最初の開始スロットが使用される前、その開始スロットに前記元のデータ・ストリームのうちの前記少なくとも１つのための前記初期経路が関連する最後の開始スロットは占有されないままである請求項１２に記載の方法。
【請求項１６】
前記元のデータ・ストリームと前記新たなデータ・ストリームとのための経路の組合せは、選択可能な組合せの定義済みの組から選択され、前記定義済みの組は、その組合せにおいて、前記元のデータ・ストリームの前記少なくとも１つのための再ルーティングされた経路が前記初期経路よりも短い組合せを含み、前記方法は、
新たな開始スロットと初期開始スロットとの間の距離が前記初期経路と前記再ルーティングされた経路との間の差と少なくとも同じである、前記元のデータ・ストリームのための前記初期経路に対する前記初期開始スロットの位置とは異なる、その元のデータ・ストリームのうちの少なくとも１つのための前記再ルーティングされた経路に対する前記新たな開始スロットのための時間的な位置を使用することと、
前記新たな開始スロットにおける最初のデータ・アイテムを前記再ルーティングされた経路に沿って伝送する前に前記初期スロットの最後のインスタンスを未使用のままにすることと
を含む請求項１２に記載の方法。
【請求項１７】
前記元のデータ・ストリームと前記新たなデータ・ストリームとのための経路の組合せは、選択可能な組合せの定義済みの組から選択され、前記定義済みの組は、その組合せにおいて、再ルーティングされた経路のうちの多くとも１つが前記初期経路と異なる組合せのみを含む請求項１２に記載の方法。
【請求項１８】
複数のデータ処理回路と、前記データ処理回路の間に結合された通信ネットワークとを含む集積回路内のプログラム可能なスケジューリング回路のための命令を含み、前記通信ネットワークは接続と、前記接続の間に結合されたルータ回路とを含み、前記通信ネットワークと、前記データ処理回路と、前記通信ネットワークおよび前記データ処理回路の間のさらなる回路との少なくともいずれか１つは、それぞれのデータ・ストリームのためにプログラムされたそれぞれの経路に沿って各それぞれのデータ・ストリームからの各データ・アイテムを伝送するように前記ルータ回路を制御するための、前記接続に沿った前記それぞれの経路の、そのそれぞれのデータ・ストリームのための定義を記憶するようにプログラム可能であり、前記命令は、前記プログラム可能なスケジューリング回路によって実行されるときに前記プログラム可能なスケジューリング回路に、
複数の元のデータ・ストリームを介したデータ・ストリームの伝送が開始された後で、その組合せにおいて前記元のデータ・ストリームの少なくとも１つのための将来の経路が再ルーティングされた経路である少なくとも１つの組合せを含む可能な組合せから、前記元のデータ・ストリームのための前記将来の経路と組み合わせて選択される、追加的なデータ・ストリームのための新たな経路を特定し、
前記通信ネットワークに、少なくとも選択された組合せの一部でもある初期経路の経路に沿ったデータ・アイテムの伝送を妨げることなしに前記元のデータ・ストリームのうちの前記少なくとも１つのための前記初期経路を再ルーティングさせ、その後に前記新たな経路に沿ったデータ・アイテムの伝送を開始させる
ようにさせる、コンピュータ・プログラム製品。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、複数のデータ処理回路と、データ処理回路を相互接続する通信ネットワークとを含む集積回路に関する。
【背景技術】
【０００２】
データ処理回路間でのオンチップの通信ネットワークの使用が、ジャーナル・オブ・システムズ・アーキテクチャ［Journal of Systems Architecture］５０（２００４）の８１〜１０４頁にテリー・タオ・イェ［Terry Tao Ye］、ルカ・ベニニ（Luca Benini）、ギオバニ・デ・ミシェリ［Giovanni de Micheli］により、発表された「オンチップ・マルチプロセッサ・ネットワークスのパケット化およびルーティング解析［Packetization and routing analysis od on-chip multiprocessor networks］」と題された論文に記載されている。
【０００３】
そのような「オンチップのネットワーク」は、処理回路の対の間で情報を受け渡すためのネットワークを介した複数の可能な経路のうちの任意の１つを選択することを可能にする。したがって、処理回路の対は、たとえ１つの可能な通信経路が処理回路の別の対の間の通信のために占有されている場合であっても通信することが可能になる。加えて、ネットワークの同じ部分を介した処理回路の異なる対の間の経路を実現するためにタイム・スロットの多重化が使用されることができる。
【０００４】
ルーティング制御回路は、ネットワークを介して情報を受け渡すために使用されることになる経路を選択するように要求される。さまざまな選択技術が使用されることができる。例えば（上で引用された）テリー・タオ・イェらは、その技術において、非常にビジーな状態のルータ回路を経路が避けるように、ネットワーク内のローカルのルータ回路が周辺のルータからの情報に基づいて、経路についての決定を行なう「先回りコンテンション［contention-look-ahead］」技術を提案している。ルータ回路は、最も短い可能な全体的伝送時間を実現するように試み、非常にビジーなルータにおける長いバッファ遅延を避けることに情報が役立つであろう場合には、この情報を迂回経路に沿って送信する。この技術は、この技術自体をネットワーク負荷に動的に適合させるが、この技術は実時間の要件が満たされることを保証することはできない。さらに、この技術は非常に複雑なローカルのルータ回路を必要とする。
【０００５】
オンチップのネットワークの設計は、ジャーナル・オブ・システムズ・アーキテクチャ［Journal of Systems Architecture］５０（２００４）の１０５〜１２８頁にエヴァゲニ・ボロティン［Evgeny Bolotin］、イズリアル・シドブ［Israel Cidob］、ラン・ギノサ［Ran Ginosar］、アヴィノアム・コロドニ［Avinoam Kolidny］により、発表された、「ＱｎｏＣ：チップ上のネットワークのためのキュー・オー・エスアーキテクチャおよび設計プロセス［QoS architecture and design process for network on a chip］」と題された論文にも記載されている。この論文は、ネットワーク上の実時間の伝送、すなわち所定の量の時間を超える時間を決して要求しないことが保証される伝送を保証することが望ましいことを記載している。実時間の伝送を保証することは、例えば映像および／またはオーディオデータのレンダリングのために必要である。この文書は、その用途のために集積回路が設計される用途のための伝送の要件が満たされることができるように、集積回路の設計段階においてルータ回路の数と、選択されたルータ間に提供される帯域幅とを適応させることを提案している。経路を局所的に決定し、送信元から送信先への最も短い経路をネットワーク内のルータと送信先とのＸ、Ｙ座標の関数として選択する単純なルータが使用される。
【０００６】
この技術は実時間の要件が満たされることを保証するが、この技術は回路のオーバヘッドと柔軟性とを犠牲にして実時間の要件が満たされることを保証する。
【発明の開示】
【発明が解決しようとする課題】
【０００７】
とりわけ、そのネットワークにおいて実時間のパケットのストリームが最小限の回路のオーバヘッドを要求しながら伝送されることができるオンチップのネットワークを備えた集積回路を提供することが本発明の目的である。
【０００８】
とりわけ、そのネットワークにおいて新たな実時間のパケットのストリームが既存のストリームに対する実時間の保証を妨害することなくネットワークを介して開始され、ルーティングされることができるオンチップのネットワークを備えた集積回路を提供することが本発明のもう１つの目的である。
【課題を解決するための手段】
【０００９】
本発明は請求項１に記載の集積回路を提供する。集積回路は、それぞれのデータ・ストリームに対してプログラム可能な経路を提供し、その結果、データ・ストリームのためのオンチップのネットワークを介して伝送される各データ・アイテムは、そのデータ・ストリームのためのプログラムされた経路に沿って伝送される。本発明によれば、複数の元のデータ・ストリームの伝送が始まった後で、元のデータ・ストリームに対して追加的なデータ・ストリームを追加する要求を満たすためにスケジューリング回路が提供される。少なくとも、好適な新しい経路が発見されることができない場合、スケジューリング回路は元のデータ・ストリームのうちの少なくとも１つのための１つの経路または複数の経路を再ルーティングして新しい経路のための接続を空ける。好ましくは、再ルーティングされる経路は、スループットの要件が満たされたままである、すなわち再ルーティングによって引き起こされたあらゆる遅延はスループットの要件によって課された最小値未満であるという制約の下で選択される。スケジューリング回路は、その他のデータ・ストリームに関するデータ・アイテムの伝送を妨げることなく、再ルーティングされる経路を再プログラムし、新たな経路をプログラムする。
【００１０】
概して、元のデータ・ストリームは、スロットの周期的に繰り返されるパターンの形で経路内の接続を占有する。この場合、そのパターンのスロットの使用は、その他のデータ・ストリームに関して途切れないままにされる。この場合にスループットの要件を満たすために、再ルーティングされる経路の経路長と、そのタイム・スロットにおいてデータが再ルーティングされた経路に沿って送信されるタイム・スロットとが、再ルーティングに起因する経路の長さの変化に新しいスロットにおける最初の伝送と元の経路のためのスロットによる最初の非伝送との間の、再スロッティング［reslotting］に起因する全てのスロットのオフセットを加えたものがスループットの要件によって決められた最大切換え遅延の値を上回らないという制約の下で選択されることが好ましい。
【００１１】
好ましくは、スケジューリング回路は、元の経路のうちの多くとも１つを再ルーティングするように構成される。このように構成することは再ルーティングを単純化する。スケジューリング回路が、その探索において、競合する使用を持たない組合せが検出されるまでデータ・ストリームのための経路のそれぞれの組合せが訪問され、訪問された組合せが接続の競合する使用を含むかどうかが決定される探索を実行することがやはり好ましい。この探索を実行することは、可能な経路を特定する効果的な対応である。
【００１２】
種々の実施形態において、再ルーティングがストリームからのデータ・アイテムの順序が狂った送達を引き起こすことを防ぐために、スケジューリング回路が選択することができる再ルーティングされる経路に対して様々な制約が課される。一実施形態において、再ルーティングされた経路は、常に初期経路と同じ長さを有する。別の実施形態において、再ルーティングされた経路は常に同じ長さを有するか、または初期経路よりも長い。再ルーティングされた経路が初期経路よりも短いことがあるその他の実施形態においては、そのスロットにおいてデータ・アイテムが再ルーティングされた経路に沿って伝送されるスロットが順序が狂った送達を防止するために初期経路に対してやはり変更されるか、または選択されたスロットにおける伝送が順序の狂った送達を防止する目的のために拒絶される。
【００１３】
また本発明は、集積回路を動作させる方法にも関し、その上に記憶されたプログラムを有するコンピュータ可読ディスク、そのようなプログラムを含む電子メモリ、または本発明に従って作動するようにスケジューリング回路をプログラムするためのコンピュータ可読ダウンロード信号などのコンピュータ・プログラム製品にも関する。
【００１４】
本発明のこれらのおよびその他の目的と有利な態様とが、添付の図面に示された実施形態の例を使用して説明される。
【発明を実施するための最良の形態】
【００１５】
図１は集積回路上のデータ処理システムを示している。データ処理システムは、データ処理回路１０と、ネットワーク１２と、ネットワーク・インターフェース１４と、スケジューリング回路１６とを含む。ネットワーク１２は、ルータ回路１２０と、ルータ回路１２０の間の接続１２２とを含む。例として、ルータ回路１２０がグリッド構成で相互接続されているところが示され、このグリッド構成において各ルータ回路１２０は、グリッド内の周辺のルータ回路１２０（全ては示されていない）に接続される。本発明は、このグリッド構成に、または示されているルータ回路１２０の数に限定されないことが理解されるべきである。その他の構成が使用されてもよく、および／またはその他のルータ回路１２０へのその他の数の接続を有するルータ回路１２０が使用されてもよい。
【００１６】
ルータ回路１２０の一部は、それぞれのネットワーク・インターフェース１４に接続され、さらにネットワーク・インターフェース１４はデータ処理回路１０に結合される。データ処理回路１０は、ローカル・メモリを有する計算回路（例えば、デジタル信号プロセッサ回路）、またはアドレスとデータとを受け取ってアドレス指定した場所にデータを書き込んだ、もしくは、アドレスを受け取りそれらのアドレスからデータを読み込んで返したメモリ回路、またはシステムのデータ入力回路もしくはデータ出力回路など、任意の種類であってよい。ネットワーク・インターフェース１４はスケジューリング回路１６に結合される。ネットワーク・インターフェース１４とスケジューリング回路１６との間の直接接続が示されているが、任意の接続、例えば通信バス、または、さらにはネットワーク１２を介した接続が使用されてもよいことが理解されるべきである。
【００１７】
動作中、データ処理回路１０はデータ・ストリームを生成し、それらのデータ・ストリームをそれらのデータ処理回路１０の対応するネットワーク・インターフェース１４に供給する。ネットワーク・インターフェース１４は、データ・ストリームを元に一連のネットワーク・データ・アイテムを形成し、それらのデータ・アイテムをルータ回路１２０に与える。ルータ回路１２０は、データ・アイテムがデータ・ストリームの送信先であるデータ処理回路１０のネットワーク・インターフェース１４に達するまで、ネットワーク１２を介した接続１２２の選択された経路に沿ってデータ・アイテムを受け渡す。
【００１８】
ネットワーク・インターフェース１４は、その経路に沿ってルータ回路１２０がデータ・アイテムを受け渡すことになる経路を制御するために、各データ・アイテムにルーティング情報を挿入する。ルーティング情報の内容は、スケジューリング回路１６によって制御される。ネットワーク・インターフェース１４がデータ・ストリームの始まるべきであるという信号をそのネットワーク・インターフェース１４に関連するデータ処理回路１０から受信するとき、ネットワーク・インターフェース１４は、ストリームを伝えるためにネットワーク１２を介してデータ・アイテムを伝送するための経路および／またはタイム・スロットを割り当てるようにスケジューリング回路１６に対して要求を送信する。返報として、スケジューリング回路１６は、ネットワーク・インターフェース１４がデータ・アイテムをルーティングするために使用することになるルーティング情報を返す。
【００１９】
図２は、ルータ回路１２０の実施形態を示している。この実施形態において、ルータ回路１２０は、複数のバッファ・メモリ２０と、多重化回路２２とを含む。ルータ回路は、それぞれのポートがそれぞれのバッファ・メモリ２０に結合された入力と、それぞれの多重化回路２２の出力に結合された出力とを備えるポート２４ａ〜ｄを有する。各バッファ・メモリ２０は、多重化回路２２に結合された出力を有する。
【００２０】
動作中、ルータ回路１２０は連続する伝送サイクル中に動作する。各伝送サイクルにおいて、各バッファ・メモリ２０は、それぞれのポート２４ａ〜ｄから（もしあれば）データ・アイテムを受信し、記憶する。次の伝送サイクルにおいて、各多重化回路２２は、前の伝送サイクルにおいてバッファ・メモリ２０のうちのそれぞれの選択された１つに記憶されたデータ・アイテムをその多重化回路２２に関連する出力に出力する。多重化回路２２によるバッファ・メモリ２０の選択は、バッファ・メモリ２０内のデータ・アイテム中のルーティング情報によって制御される。
【００２１】
概して、各データ・アイテムはそのポートにデータ・アイテムが伝送されるべきであるポート２４ａ〜ｄを指示する所定の場所の所定の数の制御ビットを含み、多重化回路２２はそれらの制御ビットにそれらに応じて対応するように設計される。好ましくは、多重化回路２２は、次のルータ回路１２０によって使用されるデータ・アイテム中の所定の場所に次のルータ回路１２０のための制御ビットが移動されるようにデータ・アイテムを更新するようにさらに構成される。概して、制御ビットはネットワーク・インターフェース１４によってデータ・アイテムに挿入される。
【００２２】
図３は、ネットワーク・インターフェース１４の実施形態を示している。この実施形態において、ネットワーク・インターフェース１４は、複数の入力バッファ・キュー・メモリ３００と、キュー多重化装置３０２と、ルーティング情報多重化装置３０４と、スロット・テーブル・メモリ３０６と、接続テーブル・メモリ３０８とを備える入力部３０を含む。さらに、ネットワーク・インターフェースは、制御ユニット３２と、出力ユニット３４と、スケジューリング回路１６（図示せず）への接続のための接続３６とを含む。
【００２３】
入力バッファ・キュー・メモリ３００は、ネットワーク・インターフェースに関連付けられているデータ処理回路（図示せず）に結合された入力と、キュー多重化装置３０２に結合された出力とを有する。キュー多重化装置３０２はルーティング情報多重化装置３０４の第１の入力に結合された出力を有し、ルーティング情報多重化装置３０４は、オンチップの通信ネットワーク（図示せず）のルータ回路（図示せず）に結合された出力を有する。スロット・テーブル・メモリ３０６は、キュー多重化装置３０２の制御入力と、接続テーブル・メモリ３０８の入力とに結合された出力を有する。接続テーブル・メモリ３０８は、ルーティング情報多重化装置３０４の第２の入力に結合された出力を有する。
【００２４】
動作中、ネットワーク・インターフェースに関連付けられているデータ処理回路（図示せず）は入力バッファ・キュー・メモリ３００にデータを供給し、入力バッファ・キュー・メモリ３００は先入れ先出しバッファを実現する働きをする。ネットワーク・インターフェースによるバッファされたデータの伝送は伝送サイクル中に行われる。ネットワーク・インターフェースは、繰り返しのネットワーク周期［network periods］を定義する。各ネットワーク周期は、複数の連続する伝送サイクルを含む。ネットワーク周期における伝送サイクルの組はそれぞれスロットと呼ばれる。スロット・テーブル・メモリ３０６はそれぞれのスロットに関する記憶場所を含み、各記憶場所は当該スロットに関連する入力バッファ・キュー・メモリ３００を示すキュー選択情報を記憶する。連続する伝送サイクルにおいて、ネットワーク・インターフェースは、スロット・テーブル・メモリ３０６にそのスロットに当該連続する伝送サイクルが属するそれぞれのスロットに応じてキュー選択情報を出力させる。
【００２５】
伝送サイクルにおいて、キュー選択情報は、そのスロットに当該伝送サイクルが属するスロットの選択されたキューのための入力バッファ・キュー・メモリ３００からのデータを受け渡すようにキュー多重化装置３０２を制御する。キュー選択情報は、そのスロットに伝送サイクルが属するスロットのためのルーティング情報を出力するように接続テーブル・メモリ３０８を制御する。このルーティング情報はルーティング情報多重化装置３０４に供給され、ルーティング情報多重化装置３０４は、このルーティング情報を入力バッファ・キュー・メモリ３００からのデータと一緒に出力する。ルーティング情報と入力バッファ・キュー・メモリ３００からのデータとは、ネットワーク内の第１のルータ（図示せず）に供給される。
【００２６】
図３の実施形態は単にネットワーク・インターフェース１４の入力部の組織的な構造を示しているに過ぎないこと、および極めて概略的に示しているに過ぎないことが理解されるべきである。実際には、ネットワーク・インターフェースは、説明された機能のいずれかまたは全てを実行するために、メモリを備えたプロセッサ（図示せず）を含んでもよい。例えば、スロット・テーブル・メモリ３０６と接続テーブル・メモリ３０８とは、同じメモリ内の異なる場所を使用して実装されてもよく、それらの場所は必要とされる情報を取り出すためにアドレス指定される。別の例として、多重化機能は、メモリからの選択的な取り出しによって実現されてもよい。さらに、実装に応じて、入力バッファ・キュー・メモリ３００からのデータは、ルーティング情報と共にシリアル形式で伝送されてもよく（この場合、伝送サイクルは複数のデータ・サイクルを含む）、またはパラレル形式で伝送されてもよい。したがって、ルーティング情報多重化装置３０４は、ルーティング情報を１つのデータ・サイクル中に伝送し、キューに入れられたデータを１つまたは複数のその他のデータ・サイクル中に伝送するか、またはキューに入れられたデータと並列に同じデータ・サイクル中にルーティング情報を伝送するように構成されてもよい。
【００２７】
同時に１つのデータ・ストリームのみが実現される必要がある場合、単一の入力バッファ・キュー・メモリ３００で十分であり、キュー多重化装置３０２は必要とされない。たとえ２つ以上のストリームが使用されてもよいとしても、単一のキュー・メモリが使用されてもよく、多重化装置が、選択されたキューのためのデータを異なるスロットにおいて読み出す。
【００２８】
出力ユニット３４はネットワーク（図示せず）からのデータを受信し、このデータを、バッファリングの後に必要に応じてネットワーク・インターフェース１４の関連するデータ処理回路に受け渡す。
【００２９】
制御ユニット３２は、ネットワーク・インターフェース１４の関連するデータ処理回路からの要求を接続３６を介してスケジューリング回路（図示せず）に受け渡す。要求は、不定の数のネットワーク周期の間、ネットワーク１２を介した選択された送信先への接続を構成する要求、またはそのような接続を破棄する要求を含む。スケジューリング回路は要求が認められたかどうかを示す情報を送り返している。さらに、スケジューリング回路１６は、集積回路の動作のために必要とされるように、スロット・テーブル・メモリ３０６および／または接続テーブル・メモリ３８に情報を書き込む。スケジューリング回路１６は、例えば要求を処理するためのプログラムを用いてプログラムされたプログラムされたデータ処理回路として実装されてもよい。
【００３０】
概して、出力ユニット３４は、受信されたデータをバッファリングするためのＦＩＦＯバッファ（図示せず）を含む。実施形態において、ネットワーク・インターフェースの対の間で双方向のストリームが実現されてもよい。オプションとして、この双方向のストリームを実現することは、その制御において、データを受信するネットワーク・インターフェース１４が、これまでにどれだけの受信されたデータ・アイテムが処理されたか、およびそれらの処理されたデータ・アイテムがもはやネットワーク・インターフェース内のバッファ・スペースを必要としないことをクレジット情報を送り返し、送信されたデータ・アイテムの数と戻って受信されたクレジット情報とが受信側でバッファ・スペースが利用可能であることを保証しない場合、データを送信するインターフェースが伝送を保留するクレジット・ベースのストリーム制御を実現するために使用されてもよい。この場合、概して入力ユニット３０と出力ユニット３４との間の結合（図示せず）が、受信されたクレジット情報をフィードバックするために提供される。
【００３１】
図４は、不定の数のネットワーク周期の間、実時間のストリームのための接続を構成する要求を処理するためのスケジューリング回路１６の動作の流れ図を示す。第１のステップ４１において要求が受信される。概して要求は、ストリームの送信元および送信先（すなわち、そのネットワーク・インターフェースにストリームが送信されるべきネットワーク・インターフェース）、ならびにオプションとして、要求される帯域幅、および最大伝送待ち時間も指定するが、後の２つはデフォルトによって標準的な値であることが示唆されてもよい。
【００３２】
第２のステップ４２において、スケジューリング回路１６は、要求を満足し、前に確立されたデータ・ストリームをサポートすることになる通信ネットワーク１２を介した１組のチャネルの探索を実行する。各チャネルは、ネットワークを介した経路、すなわちルータ回路１２０間の一連の接続１２２と、そのスロットにおいてそれらの接続１２２が使用されることになるスロットとを含む。
【００３３】
図５ａは、チャネルによる接続１２２とスロットとの占有を示す。異なる行（ａ，ｂ，ｃ，…）は異なる接続１２２に対応し、異なる列（０，１，２，…）は時間的に連続する伝送サイクルに対応する。バツ印はそのサイクルにおいて接続１２２がチャネルによって占有される伝送サイクルを示す。この図においては、８つの伝送サイクルからなるネットワーク周期が仮定された。したがって、スロットは、各８伝送サイクルを繰り返す伝送サイクルを含む。したがって、バツ印のパターンは、この図解において８伝送サイクルごとに繰り返し現れる。列を区別する番号はスロットを特定する。
【００３４】
パターンは、連続するスロットにおいて占有される接続１２２が、共有されたルータ回路１２０に接続されることになるようになる。図５ａにおいて、共有されたルータ回路１２０に接続するネットワーク接続１２２は、必ずしも常に連続する行によって表されるわけではなく、したがってパターンにおいて垂直方向の飛びが発生してもよい。図５ｂは、チャネルによって占有された接続１２２を示し、数字はそのスロットにおいて当該接続が占有されるスロットを示す。
【００３５】
図５ｃは、バツ印と、丸印と、四角印とによって示される３つのチャネルの組合せのためのスロットと接続１２２との占有を示す。図５ｄは、それらのチャネルによって占有された接続を示す。
【００３６】
概して、スケジューリング回路１６が新しいチャネルをオープンする要求を受信したとき、スロットと接続１２２とはいくつかの前に要求されたチャネルに対して割り当てられていることになり、それらのスロットと接続とはそれらのチャネルを介してデータ・ストリームを伝送するために使用されることになる。スケジューリング回路１６がチャネルを追加する要求を受信したとき、スケジューリング回路１６はそのチャネルを実現するためのスロットと接続１２２とを探索する。
【００３７】
本発明のスケジューリング回路１６によれば、この探索は、前に存在したチャネルのためのスロットとネットワーク接続１２２との前の割り当てを修正されないままにするスロットとネットワーク接続１２２との割り当てに限定されない。スケジューリング回路１６は、既存のチャネル上のデータ伝送を妨げないような形でそれら既存のチャネルのためのスロットおよび／またはネットワーク接続１２２を修正することも検討する。
【００３８】
第１の実施形態において、スケジューリング回路１６は、そのスロットにおいてネットワーク接続がそれぞれの既存のチャネルのために占有されるスロットを修正することを検討しないが、それぞれの既存のチャネルのための、当該チャネルの同じ送信元と送信先との間のそれぞれの異なる一連の接続を含む全ての同じ長さの経路の組を探索する。
【００３９】
図６ａ〜ｃは、この種の様々な経路を示す。「ｉ」（ｉ＝０，１，…）とラベル付けされた複数のチャネルが既に割り当てられており、Ｎi個の代替的なこの種の経路がチャネルｉに対して存在する場合、それらの既存のチャネルｉに対してＮ＝Ｎ0×Ｎ1×Ｎ2×…個の異なる経路の組合せが存在する。新たなチャネルを構成する要求を処理するときに、スケジューリング回路１６は、要求される待ち時間を満足する（つまり、送信元から送信先へデータを伝送するため所定数の伝送サイクルを超える伝送サイクルを要求しない）、その新しいチャネルのための全ての経路を検討する。Ｍ個のそのような経路が存在する場合、既存のチャネルと新たなチャネルとを合わせたものに対してＮ×Ｍ個の異なる経路の組合せが存在する。
【００４０】
Ｎ×Ｍ個の異なる組合せのそれぞれに対して、スケジューリング回路１６は、要求された新たなチャネルのためのＰ個の異なる開始タイム・スロットを検討する（Ｐはネットワーク周期内の伝送サイクルの数である）。この実施形態において、スケジューリング回路１６は、既存のチャネルのための前の開始タイム・スロットのみを検討する。Ｐ個の異なる開始スロットに対するＮ×Ｍ個の組合せのうち、スケジューリング回路１６は、異なるチャネルが同じスロットにおいて同じネットワーク接続１２２を使用するそれらの組合せを消去することができる。スケジューリング回路１６は、残りの組合せのうちの１つを選択する。
【００４１】
原理上、探索ステップ４２は、その組合せにおいて同じスロットにおいて２回以上使用されるネットワーク接続１２２がない組合せが見つかるまで、スケジューリング回路がタイム・スロットのうちの１つを連続的に用いてＮ×Ｍ×Ｐ個の可能な組合せのそれぞれを訪問するという点において実装されてもよい。
【００４２】
図４ａは、その実施形態において、探索ステップ４２が、例えば既存のチャネルのためのネットワーク接続の組合せから新たな組合せを生成するための第１の探索サブステップ４２１から始まる実施形態を示している。この第１の探索サブステップ４２１において、最初に、スケジューリング回路１６は、要求されたチャネルのための全てのＭ個の可能な経路とＰ個の可能な開始スロットとに対して、既存の経路とのその組合せが同じスロットにおいて同じネットワーク接続１２２を２回以上使用しないような、Ｐ個の開始点のうちの少なくとも１つの開始点に対するＭ個の経路のうちの少なくとも１つの経路が存在するかどうかを検討する。そのような経路と開始スロットとが存在する場合、探索ステップはこの第１の探索サブステップの後で終了する。
【００４３】
そのような経路と開始点とが発見されることができない場合、そのサブステップにおいて、スケジューリング回路が、要求されたチャネルのためのＭ個の可能な経路のうちの少なくとも１つの一部であるネットワーク接続１２２を使用する既存のチャネルを選択する第２のサブステップ４２２が実行される。次に、スケジューリング回路１６は、その組合せにおいて、選択された既存のチャネルが前とは異なる経路に沿って走り、残りのチャネルが前と同じ経路に沿って走る、要求されたチャネルと既存のチャネルとのための経路の組合せを選択する。可能な開始スロットが、要求されたチャネルのために選択される。第３の探索サブステップ４２３において、スケジューリング回路１６は、選択された組合せが同じスロットにおいて同じネットワーク接続１２２を２回以上使用しないかどうかをテストする。使用しないならば探索ステップは終了する。
【００４４】
選択された組合せが接続の競合する使用を行なう場合、スケジューリング回路１６は、その組合せにおいて、選択された既存のチャネルが異なる経路に沿って走り、残りのチャネルが前と同じ経路に沿って走る、要求されたチャネルと既存のチャネルとのための経路の別の可能な組合せを選択するための第４のサブステップ４２４を実行する。必要があれば、要求されたチャネル（Ｍ個）および選択されたチャネル（Ｎi個）のための全てのＭ×Ｎi個の可能な経路の組合せと、要求されたチャネルのためのＰ個の可能な開始スロットとが検討され終わるまで第３の探索サブステップ４２３が繰り返される。そうでなければ、第５のサブステップ４２５が第２のサブステップ４２２の繰り返しを引き起こして、再ルーティングのための別の既存のチャネルを選択する。
【００４５】
経路の好適な組合せと、開始点とが発見されることができない場合、要求を満足することができなかったことが報告される。オプションとして、そのサブステップにおいて、スケジューリング回路１６が、２つの既存のチャネルとより多くの既存のチャネルとのサブセットのそれぞれのための代替経路を同時に検討するさらなる探索サブステップが実行されてもよい。好ましくは、スケジューリング回路は、サブセット内の既存のチャネルのうちの少なくとも１つが、新たに要求された接続のためのＭ個の可能な経路の一部であるネットワーク接続１２２を使用し、サブセット内のそれぞれの次の既存のチャネルが、Ｍ個の可能な経路の一部であるか、またはサブセット内の前の既存のチャネルによって使用されるネットワーク接続１２２を使用するという意味で既存のチャネルのサブセットが関連するように既存のチャネルのそれらのサブセットを選択する。
【００４６】
スケジューリング回路１６の許容可能な複雑性に応じて、探索ステップ４２は、制限された数のそのような探索サブステップに制限されてもよい。
【００４７】
好ましくは、探索は再ルーティングされた経路に制限され、この制限されることはチャネルに対するスループットの保証が満たされたままであることを保証する。一例においては、スループットの保証は、再ルーティングによって追加されることがあるいくつかのタイム・スロットの最大遅延Ｄとして表されることができる（例えば、Ｄ＝０）。再ルーティングされた経路に対する実際の遅延は
ｄＳ＋ｄＬ
である。
【００４８】
ここでｄＳは、元の経路による最初の未使用のタイム・スロットＳ０と、再ルーティングされた経路による最初の使用されるタイム・スロットＳ１との間の距離Ｓ１−Ｓ０である。ｄＬは、元の経路の長さＬ０と、再ルーティングされた経路の長さＬ１との間の長さの差（接続１２２の数）Ｌ１−Ｌ０である。好ましくは、ｄＳ＋ｄＬがＤ以下であるという条件を満たす経路とタイム・スロットとのみが探索中に検討される。典型的な例において、Ｄは０に等しく、ｄＳも０に等しい場合、ｄＬは、したがって０以下であるべきである。ｄＳ＞０ならば、より小さなｄＬが使用されるべきである。
【００４９】
探索ステップ４２の後、スケジューリング回路１６は第３のステップ４３を実行する。第３のステップ４３は、有効な組合せが見つかったかどうかをテストする。見つかっていない場合、第３のサブステップは、新たに要求されたチャネルに対して好適な経路が見つからなかった場合に要求したネットワーク・インターフェースに拒絶を送り返す第４のステップ４４に制御を渡す。
【００５０】
探索ステップ４２において好適な経路が見つかった場合、スケジューリング回路１６はそのステップにおいて、スケジューリング回路１６がそのチャネルに対して探索サブステップにおいて代替経路が選択された既存のチャネルの始めにあるそれらのネットワーク・インターフェース１４に命令を送信する第５のステップ４５に移動する。命令は、関係するネットワーク・インターフェース１４の１つの接続テーブル・メモリ３０８または複数の接続テーブル・メモリ３０８に対する更新を制御する。１つの接続テーブル・メモリ３０８または複数の接続テーブル・メモリにおいて、代替経路を定義する新たなルーティング情報が書き込まれる。例えば、スケジューリング回路１６が上述の第１の探索サブステップにおいて経路の組合せを発見した場合、選択された既存のチャネルに関するルーティング情報を更新するためにその選択された既存のチャネルの始めにあるネットワーク・インターフェースに命令が送信される。
【００５１】
その後で、スケジューリング回路１６は、そのステップにおいてスケジューリング回路１６が、新たに要求されたチャネルの始めにあるネットワーク・インターフェース１４の接続テーブル・メモリ３０８にルーティング情報をプログラムする第６のステップ４６を実行する。さらに、スケジューリング回路１６は、新たに要求されたチャネルの選択されたスロットの識別をネットワーク・インターフェースのスロット・テーブル・メモリ３０６にプログラムする。
【００５２】
第７のステップ４７において、スケジューリング回路１６は、新たに要求されたチャネルの始めにあるネットワーク・インターフェースの制御ユニット３２に肯定応答信号を送信する。肯定応答信号に応答して、制御ユニット３２は、要求が受理されたことと、ストリームが開始できることとをデータ処理回路１０に信号で知らせる。その後で、ネットワーク・インターフェース１４は、スケジューリング回路１６によって指示されたスロットにおいてルーティング情報を伴うデータを送信することになり、ルータ回路１２０は、ルーティング情報に従って通信ネットワーク１２を介してデータをルーティングすることになる。
【００５３】
実施形態において、通信ネットワーク内の既存のチャネルに対する全てのデータが新たなルートに従うか、または少なくとも新たなチャネルと競合する可能性があるまだ古いルートに従うデータがない時点でのみ新たなチャネルが始まるように、既存のチャネルの再ルーティングと、新たなチャネルのアクティブ化との間で遅延が使用される。２つ以上のチャネルが同時に再ルーティングされる場合、再ルーティングを同期化すること、または再ルーティング中の競合を避けるためにそれらの一連のステップにおいてチャネルが１つ１つ再ルーティングされる一連のステップを探索することが必要であることがある。
【００５４】
代替的に、例えば再ルーティング後の最初のデータ・アイテムであるように印が付けられたデータ・アイテムの受信後にスケジューリング回路１６に肯定応答を供給するようにネットワーク・インターフェース１４を構成することによって肯定応答メカニズムが使用されてもよい。この場合、スケジューリング回路１６は、全ての再ルーティングされたチャネルに対して肯定応答が検出された後で新たなチャネルをアクティブ化する。肯定応答は、例えばネットワーク・インターフェース１４内の所定の記憶場所のフラグを設定することによって供給されることができ、スケジューリング回路は再ルーティングされた１つのチャネルまたは複数のチャネルの最後にあるネットワーク・インターフェース内の１つのフラグまたは複数のフラグをポーリングする。代替として、ネットワーク・インターフェースは肯定応答を送信してもよい。スケジューリング回路１６の代わりに、何らかのその他の回路が肯定応答が生成されたかどうかをチェックするために、および新たなチャネルの開始を引き起こすために提供されてもよい。本発明が単純な例に関して示されたが、本発明はこれらの例に限定されないことが理解されるであろう。例えば、本発明は通信ネットワーク１２内の接続１２２の任意のパターンに適用されてもよいことが理解されるべきである。概して、それぞれの可能なネットワークは、ネットワーク・インターフェースの少なくとも一部の間のチャネルのために複数のルータを介した複数の異なる経路を可能にする。さらに本発明は、言うまでもなく４端子のルータ回路１２０に限定されない。より少ない、またはより多い端子を備えたルータ回路１２０が使用されてもよい。さらに受信されたデータをその伝送サイクルにおいてデータが受信された伝送サイクルの直後の伝送サイクルにおいて転送する非常に簡単なルータ回路を使用することが好ましいが、より複雑なルータ回路、例えば選択可能な数の伝送サイクル中にバッファリングを提供するルータ回路が使用されてもよいことが理解されるべきである。この場合、探索はルータ回路１２０に対する様々なバッファリング周期［buffering periods］も含み、ルーティング情報はそれぞれのルータ回路１２０のための要求されるバッファリング周期の指示を含む。
【００５５】
さらに、それぞれの例において、各ネットワーク周期においてチャネルに対して１つの伝送サイクルが使用されることになるように、各チャネルに対して１つのスロットが使用された。しかし、より大きな伝送帯域幅が必要とされる場合、より多くのスロットが使用されてもよい。この場合、探索はより多くのスロット、例えば１つのスロットではなく２つのスロットが使用される場合にはＰ（Ｐ−１）個のスロットの対を含んでもよい。この場合、同じキューの選択がスロット・テーブル・メモリ３０６内の異なるスロットに関するエントリに書き込まれる。両方のスロットにおける伝送のために同じ経路が使用されることがデータの順序正しい送達を保証するので、両方のスロットにおける伝送のために同じ経路が使用されることが好ましい。既存のチャネルと同じ長さを有する、既存のチャネルのための代替経路を探索することの利点は、この場合、結果として得られる代替経路がその順番でデータが送達される順番に影響を与えないことである。
【００５６】
代替として、異なるスロットにおいて同じチャネルに対して異なる経路が使用されてもよい。この場合、異なるスロットのための異なる経路を特定するルーティング情報が接続テーブル・メモリ３０８に書き込まれなければならず、接続テーブル・メモリ３０８はアクティブなスロットに応じて（チャネルに応じてではない）アドレス指定されなければならない。このことは好適な経路を発見する可能性を高める。この場合、等しい長さの経路が使用されることがデータの順序正しい送達を保証するので、等しい長さの経路が使用されることが好ましい。しかし、スロット間の距離が少なくともデータの順序が狂った送達を防止できるだけ十分に大きくされる限り、代替的に異なる長さの経路が使用されてもよい。
【００５７】
さらなる実施形態において、探索ステップ４２における探索は、好ましくはスループットの要件が満たされたままである（例えば、ｄＳ＋ｄＬがＤ以下、Ｄ＝０）という制約の下で、元の経路と異なる長さを有してもよい、すなわち異なる数の接続を含んでもよい、既存のチャネルのための代替経路も含む。経路の長さの変化ｄＬは、データが送信先のネットワーク・インターフェースに順番が狂って到着することになるリスクを伴う。チャネルが１ネットワーク周期につき１スロットのみを使用する場合、新たな経路が、ネットワーク周期Ｐから元の経路よりも１接続短い長さを引いた数以下であればこのリスクが回避されることになる。したがって、好ましくは、スケジューリング回路１６がそれに応じて経路の探索を制限する。チャネルが１ネットワーク周期につき２つ以上のスロットを含む場合、好ましくは、経路の長さの変化は、同じチャネルに対する前のスロットまでのスロットの距離を超える長さだけ短いことはない。
【００５８】
しかし、新たな経路に沿った最初のデータが到着する前に全ての前に送信されたデータが到着したことを確実にするために、新たなチャネルに沿った伝送を開始する前に、変更されたチャネルに対する１つまたは複数のスロットが使用されないままにされる、すなわちチャネルを保留することが可能ならば、ネットワーク・インターフェース１４においてそのような制約が課される必要はない。保留は、例えば、伝送およびその後の再書き込みを防止するために、伝送が行われる前に、好ましくない伝送をもたらすかもしれないネットワーク・インターフェース内の情報を置き換えることによって実現されてもよい。しかし、特定の情報が（まだ）伝送を開始するために使用されるべきでないことを明示的に指示する、ネットワーク・インターフェースにおけるさらなる情報の記憶などのその他のメカニズムが使用されてもよい。さらに、データ処理回路１０への送達の前にネットワークからの受信されたデータをバッファリングするためにネットワーク・インターフェースにおいてバッファ（図示せず）が使用されてもよい。十分なバッファされたデータが利用可能である限り、未使用のスロットは送達に対する影響を持たない。バッファされた受信されたデータが利用できることは、スループットの要件を緩和する（Ｄを大きくする）。
【００５９】
言うまでもなく、この技術は、チャネルに対する最大の許容可能な待ち時間が保留期間の追加によって超えられない場合にのみ可能である。許容可能な待ち時間に関連する問題は、上述のように、順序が狂った送達が起こり得ないように変更された経路の長さを制限することによって避けることができる。この場合、データの伝送は保留なしに継続されることができる。
【００６０】
さらなる実施形態において、探索ステップ４２における探索は、既存の経路よりも長いが、最大の許容可能な待ち時間によって許可される長さ以下である、既存のチャネルのための代替経路も含む。チャネルに対する経路がチャネルの全ての開始スロットに対して同じである実施形態と組み合わせられると、このような代替経路を含むことは、経路の変更中に順序正しい送達が保証されたままであるという利点を有する。
【００６１】
図７ａ〜ｃは、このように検討されてもよい追加的な経路の一部を示している。このさらなる実施形態の効果は、探索中により多くの経路が検討されることになり、その結果、新たに要求されたチャネルのための経路が発見されるより高い見込みがあることである。そのサブステップにおいて、選択された既存の接続に対して代替経路が検討される第１の探索サブステップを有する実施形態との組合せにおいて、Ｍi＞Ｎi個の代替経路が存在することになる。しかし、そうでなければ、探索が同様にして実行されることができる。
【００６２】
代替経路によって実現された短縮が最も近い前のスロットとの距離を超えないと仮定すると、上述のように、より短い経路でさえも保留なしに検討されてもよい。このことは、経路の変更中の順序が狂った送達を防止する。代替実施形態において、既存の経路と比較して異なる長さを有する代替経路の検討は、送達のスロットが、同じままであるか、または少なくともそのスロットが経路の変更前の送達のための最後のスロットに先だって動くほど大きく進まないように、ネットワーク・インターフェースからの伝送の開始スロットの対応する変更に結びつけられてもよい。
【００６３】
より複雑な実施形態において、既存のチャネルに対するより多くの代替経路および／または代替開始タイム・スロットを検討し、その後、経路が変更されたときに順序が狂った送達をもたらすかもしれない経路とスロットとの組合せを消去することによって、探索においてより多くの自由が許容されることがある。
【００６４】
スケジューリング回路１６によって全てのチャネルが選択されることが望ましいが、少なくとも最初に、チャネルの一部が、集積回路の設計中に選択された定義済み経路を使用してもよいことが理解されよう。この場合、スケジューリング回路１６は、ランタイムで追加されなければならない追加的なチャネルを提供することのみを必要とする。実施形態において、新たなチャネルを実現するために全ての最初に定義されたチャネルが再ルーティングされてもよいが、例えばプログラム不可能なネットワーク・インターフェースが一部のチャネルに対して使用されるために、代替的にそれら一部のチャネルが再ルーティングから除外されてもよい。
【００６５】
既に理解されているであろうように、本発明は、集積回路内の通信ネットワークを介したデータの実時間のストリームのためのチャネルのランタイムの追加のための改善されたメカニズムを提供する。ネットワークを介して全てのチャネルを管理するスケジューリング回路１６は、ネットワーク・インターフェースからのチャネルに対するデータの伝送のための利用可能な経路と１つのスロットまたは複数のスロットとを探索する。スケジューリング回路１６は、まだ既存の接続によって使用中でないスロット中の接続を探すだけでなく、代替経路を介して既存の接続を再ルーティングすることによって利用可能にされることができる接続とスロットも探すことによって経路とスロットとを探索する。代替経路は、再ルーティングがチャネルを介したデータの送達の順序を乱すことがないように選択されることが好ましい。好適な経路が発見されると、まず、既存のチャネルが再ルーティングされ、その後、新たなチャネルが生成される。
【図面の簡単な説明】
【００６６】
【図１】集積回路上のデータ処理システムを示す図である。
【図２】ルータ回路を示す図である。
【図３】ネットワーク・インターフェースを示す図である。
【図４】スケジューリング・プロセスの流れ図である。
【図４ａ】スケジューリング・プロセスの流れ図である。
【図５ａ】接続とスロットとの占有を示す図である。
【図５ｂ】接続とスロットとの占有を示す図である。
【図５ｃ】接続とスロットとの占有を示す図である。
【図５ｄ】接続とスロットとの占有を示す図である。
【図６ａ】可能な経路を示す図である。
【図６ｂ】可能な経路を示す図である。
【図６ｃ】可能な経路を示す図である。
【図７ａ】さらなる可能な経路を示す図である。
【図７ｂ】さらなる可能な経路を示す図である。
【図７ｃ】さらなる可能な経路を示す図である。
【図１】
2008541677.tif 000003
【図２】
2008541677.tif 000004
【図３】
2008541677.tif 000005
【図４】
2008541677.tif 000006
【図４ａ】
2008541677.tif 000007
【図５ａ】
2008541677.tif 000008
【図５ｂ】
2008541677.tif 000009
【図５ｃ】
2008541677.tif 000010
【図５ｄ】
2008541677.tif 000011
【図６ａ】
2008541677.tif 000012
【図６ｂ】
2008541677.tif 000013
【図６ｃ】
2008541677.tif 000014
【図７ａ】
2008541677.tif 000015
【図７ｂ】
2008541677.tif 000016
【図７ｃ】
2008541677.tif 000017
【国際調査報告】
2008541677.tif 000018
2008541677.tif 000019
2008541677.tif 000020