(57)【要約】  複数の処理モジュール（M、S、IP）、及びモジュール（M、S、IP）を結合するように構成されたネットワーク（N）を有する集積回路が提供される。当該集積回路はさらに、各々が処理モジュール（M、S、IP）の１つとネットワーク（N）との間に結合された複数のネットワーク・インターフェース（NI）を有する。ネットワーク（N）は、ネットワークリンク（L）を介して隣接するルータ（R）と結合された複数のルータ（R）を有する。処理モジュール（M、S、IP）はネットワーク（N）を通る接続経路（C1乃至C12）を用いた接続上で互いに通信し、接続経路（C1乃至C12）の各々は必要なタイムスロット数の間、少なくとも１つのネットワークリンク（L）を使用する。少なくとも１つのタイムスロット割当てユニット（SA）が、ネットワークリンク（L）にタイムスロットを割当て、不使用タイムスロットを導出し、且つ既に割当てられたタイムスロットに加えて導出された不使用タイムスロットをネットワークリンクを使用する１つ又は複数の接続に割当てるために設けられる。
2008502263.tif 000002
【特許請求の範囲】
【請求項１】
複数の処理モジュール、及び該モジュールを結合するように構成されたネットワーク、
各々が前記処理モジュールの１つと前記ネットワークとの間に結合された複数のネットワーク・インターフェースであり；
前記ネットワークが複数のルータを有し、該複数のルータはネットワークリンクを介して隣接するルータと結合されており；
前記処理モジュールが前記ネットワーク内を通る接続経路を用いた接続上で互いに通信し、その際、該接続経路の各々が必要なタイムスロット数の間、少なくとも１つのネットワークリンクを使用する；ところの複数のネットワーク・インターフェース、及び
少なくとも１つのタイムスロット割当てユニットであり、前記ネットワークリンクにタイムスロットを割当て、不使用タイムスロットを導出し、且つ既に割当てられたタイムスロットに加えて前記導出された不使用タイムスロットを前記ネットワークリンクを使用する１つ又は複数の接続に割当てる、少なくとも１つのタイムスロット割当てユニット、
を有するデータ処理システム。
【請求項２】
請求項１に記載のデータ処理システムを有する集積回路。
【請求項３】
前記少なくとも１つのタイムスロット割当てユニットが前記接続経路内の各ネットワークリンクに関して不使用タイムスロットを導出するように適応されており、連続した不使用タイムスロットが連続したネットワークリンクに割当てられる、ところの請求項２に記載の集積回路。
【請求項４】
前記少なくとも１つのタイムスロット割当てユニットが、該タイムスロット割当てユニットに記憶された優先度リストに従って、不使用タイムスロットを前記接続に割当てるように適応されている、ところの請求項２又は３に記載の集積回路。
【請求項５】
前記少なくとも１つのタイムスロット割当てユニットが、前記接続の１つの待ち時間を短縮するために前記ネットワークリンクのタイムスロットにマーキングするマーカーユニットを有する、ところの請求項２に記載の集積回路。
【請求項６】
前記少なくとも１つのタイムスロット割当てユニットが、前記接続に割当てられた入力項目を有するタイムスロットテーブルをさらに有し、前記タイムスロットテーブルが１つの待ち時間短縮ビットを有する、ところの請求項２又は３に記載の集積回路。
【請求項７】
複数の処理モジュール、及び該モジュールを結合するように構成されたネットワークであり、ネットワークリンクを介して隣接するルータと結合された複数のルータを有するネットワーク、並びに各々が前記処理モジュールの１つと前記ネットワークとの間に結合された複数のネットワーク・インターフェースを有する集積回路におけるタイムスロット割当て方法であって：
前記処理モジュール間で前記ネットワーク内を通る接続経路を用いた接続上で通信するステップであり、該接続経路の各々が必要なタイムスロット数の間、少なくとも１つのネットワークリンクを使用するところの通信するステップ、
前記ネットワークリンクにタイムスロットを割当てるステップ、
不使用タイムスロットを導出するステップ、及び
既に割当てられたタイムスロットに加えて前記導出された不使用タイムスロットを前記ネットワークリンクを使用する１つ又は複数の接続に割当てるステップ、
を有する方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、複数の処理モジュール及び複数の処理モジュールを結合するように構成されたネットワークを有する集積回路、及びそのような集積回路におけるタイムスロット割当て方法、並びにデータ処理システムに関する。
【背景技術】
【０００２】
システム・オン・シリコンは、新機能の追加と既存機能の向上とに対する増し続ける要求を受け、複雑さを増し続けている。このことは、集積回路上に集積される部品密度を一層高めることによって可能にされている。同時に、回路が動作するクロック速度も高速化する傾向にある。より高いクロック速度は、部品の高密度化と相まって、同一クロック範囲内で同期して動作可能な領域を狭めてきた。このため、モジュール手法の必要性が生じている。このような手法に従って、処理システムは複数の比較的独立で複雑なモジュールを有する。伝統的な処理システムでは、通常、システムモジュールはバスを介して互いに通信する。しかしながら、モジュール数が増加するにつれ、この通信手法は以下の理由によりもはや実用的ではなくなっている。すなわち、一方で、多数のモジュールによってバスに過大な負荷が形成され、そして、バスは１つの装置のみがバスにデータを送ることを可能にするだけであるので、バスが通信のボトルネックを構成している。
【０００３】
通信ネットワークはこれらの欠点を解決する有効な手法である。ネットワーク・オン・チップ（ＮｏＣ）は、高度に複雑化したチップにおける相互接続問題の解決策として、最近かなりの注目を集めている。その理由は２つの要素から成る。第１に、ＮｏＣは新しいディープサブミクロン技術における電気的問題を解決する助けとなる。なぜなら、ＮｏＣは全体的な配線を構築かつ管理するからである。同時に、ＮｏＣは配線を共有して配線数を削減し、その利用率を高める。ＮｏＣはまた、エネルギー効率が良く、信頼性が高いものとなり得るとともに、バスに比べて拡張性がある。第２に、ＮｏＣは演算処理を通信から分離するが、このことは莫大な数のトランジスタチップの設計を管理することにおいて不可欠なことである。ＮｏＣがこの分離を実現することができるのは、ＮｏＣは伝統的にプロトコルスタックを用いて設計されるが、プロトコルスタックは通信サービスの使用をサービスの遂行から分離する洗練されたインターフェースを提供するものであるためである。
【０００４】
ネットワークをオンチップ相互接続として導入することは、例えばバス又はスイッチ等の直接相互接続と比較して、通信を根本的に変えるものである。なぜなら、通信モジュールが直接的に接続されずに、１つ以上のネットワークノードによって分離されているという、ネットワークのマルチホップ性のためである。このことは、モジュールが直接接続される一般的な既存の相互接続（例えば、バス）と対照的である。この変化から予期されることは、アービトレーション（これは集中型から分散型に変えられなければならない）及び通信特性（例えば、順序付け又はフロー制御）に属し、それらはインテレクチュアル・プロパティ・ブロック（intellectual  property  block；ＩＰ）又はネットワークの何れかによって処理されなければならない。
【０００５】
これらの問題のほとんどは、ローカル及びワイド・エリア・ネットワーク（コンピュータ・ネットワーク）の分野で、また、並列マシン相互接続ネットワークとして、既に研究主題とされてきた。何れもオンチップ・ネットワークと関連しており、それらの分野での結果の多くがチップにも適用可能である。しかしながら、ＮｏＣの前提はオフチップ・ネットワークとは異なっており、故に、ネットワーク設計の選択肢のほとんどが再評価されなければならない。オンチップ・ネットワークは、設計上の異なる選択につながる異なる特性（例えば、より厳しいリンクの同期化）及び制約（例えば、より高いメモリコスト）を有し、それらは最終的にネットワークサービスに影響を及ぼす。
【０００６】
ＮｏＣはオフチップ・ネットワークとは主にそれらの制約及び同期化の点で異なる。一般に、資源制約はオンチップの方がオフチップよりも厳しい。記憶装置（すなわち、メモリ）及び演算処理資源が比較的高価であるのに対して、ポイントツーポイントリンク数はオンチップの方がオフチップより多い。例えばＲＡＭ等の汎用オンチップ・メモリは大面積を占有するので、記憶装置は高価である。メモリを比較的小型のネットワーク要素に分散させることは、メモリの間接領域が支配的になるので、さらに好ましくない。
【０００７】
オフチップ・ネットワークは、一般に、パケット交換を用いてベストエフォート型サービスを提供する。各ネットワークノードで競合が起こる可能性があり、待ち時間保証を提供することを非常に困難にしている。スループット保証は、例えばレートベース・スイッチング又はデッドラインベース・パケット交換等の手法を用いてなおも提供され得るが、多大なバッファリングのコストを伴う。このような時間関連の保証を提供する代替手法は時分割多重アクセス（ＴＤＭＡ）回路を用いるものであり、そこでは全ての回路がネットワーク接続専用とされる。回路は比較的低コストのメモリ及び計算で保証を提供する。ネットワーク・アーキテクチャが如何なる予備保証された帯域幅もベストエフォート型通信で利用可能にする場合、ネットワーク資源の利用が増大される。
【０００８】
ネットワーク・オン・チップ（ＮｏＣ）は、一般に、複数のルータ及びネットワーク・インターフェースで構成される。ルータはネットワークノードとしての役割を果たし、発信源のネットワーク・インターフェースから宛先のネットワーク・インターフェースまでデータを転送するために使用される。このため、静的な基準（すなわち、経路は事前設定され変更されない）又は動的な基準（すなわち、経路は、例えばホットスポットを避けるためにＮｏＣの負荷に応じて変更され得る）に基づいて、宛先までのデータの経路を的確に選択する。ルータはまた、時間保証を（例えば、レートに基づいて、デッドラインに基づいて、又はＴＤＭＡ流のパイプライン回路を用いて）実行し得る。ルータ・アーキテクチャに関する詳細は非特許文献１に述べられている。
【０００９】
ネットワーク・インターフェースはＩＰブロックに接続される。ＩＰブロックはあらゆる種類のデータ処理ユニットを指し示し、あるいはメモリ、ブリッジ等ともなり得る。具体的には、ネットワーク・インターフェースはＩＰブロックとネットワークとの間の通信インターフェースを構成する。通常、インターフェースは既存のバス・インターフェースと互換性を有する。従って、ネットワーク・インターフェースはデータの順序付け（提示されたコマンド、フラグ及びデータの固定幅（例えば、32ビット）の信号群への適合）及びパケット化（ネットワークにより内部で必要なパケットヘッダ及び後書きの付与）を扱うように設計されている。ネットワーク・インターフェースはまたパケットのスケジューリングを実行してもよく、これはタイミング保証及び許可（admission）制御を含み得る。
【００１０】
オンチップシステムはしばしば、その相互接続通信のタイミング保証を要求する。故に、グローバル時間の概念（すなわち、ネットワーク要素、つまりはルータ及びネットワーク・インターフェースの間での共時性の概念）に基づいてスループット、待ち時間及びジッターが保証された通信体系が提供される。なお、グローバル時間における基本的な時間単位はスロット又はタイムスロットと呼ばれる。全てのネットワーク要素は、通常、ネットワーク要素の各出力ポートに等しい大きさのスロットテーブルを有し、その中で、種々の接続（connection）に対してタイムスロットが予約され、スロットテーブルが同期して（すなわち、全てが同一スロット内で同時に）進む。種々のトラフィックの種類を特定し、特性をそれらに関連付けるために接続が用いられる。
【００１１】
時間関連の保証（すなわち、スループット、待ち時間及びジッター）を提供するコスト効率の良い手法は、ＴＤＭＡ（時分割多重アクセス）流のパイプライン回路を用いることである。この手法は、同期化が密に詰まったシステム・オン・チップ（ＳｏＣ）のレート及びデッドラインに基づく手法と比較して、より小さいバッファ空間を必要とするだけであるので有利である。
【００１２】
各スロットにて、データ項目が１つのネットワーク要素から次の要素へ、すなわち、ルータ間、又はルータとネットワーク・インターフェースとの間で移動される。故に、出力ポートにスロットが予約されるとき、マスターモジュールとスレーブモジュールとの間などの経路に沿った次の出力ポートに次のスロットが確保されなければならない。
【００１３】
タイミング保証を伴う複数の接続が設定されるとき、衝突が生じないように（すなわち、２以上の接続に割当てられるスロットがないように）スロット割当てが実行されなければならない。所定のネットワーク接続形態、すなわち、所定数のルータ及びネットワーク・インターフェース並びにＩＰブロック間の接続の組、に対して最適なスロット割当てを導出する作業は、網羅的な計算時間を要する最適解の導出を含むため、非常に計算が集中する（ＮＰ完全な）問題である。
【非特許文献１】Edwin  Rijpkema、Kees  Goossens、Paul  Wielage、「ネットワーク・オン・シリコン向けルータ・アーキテクチャ（A  Router  Architecture  for  Networks  on  Silicon）」、PROGRESS、2001年10月
【発明の開示】
【発明が解決しようとする課題】
【００１４】
本発明は、ネットワーク・オン・チップ環境において改善されたスロット割当てを提供することを目的とする。
【課題を解決するための手段】
【００１５】
上記課題に鑑み、複数の処理モジュール、及び該モジュールを結合するように構成されたネットワークを有する集積回路が提供される。当該集積回路はさらに、複数のネットワーク・インターフェースであり各々が前記処理モジュールの１つと前記ネットワークとの間に結合された複数のネットワーク・インターフェースを有する。前記ネットワークは複数のルータを有し、該複数のルータはネットワークリンクを介して隣接するルータと結合されている。前記処理モジュールは前記ネットワーク内を通る接続経路を用いた接続上で互いに通信し、その際、該接続経路の各々が必要なタイムスロット数の間、少なくとも１つのネットワークリンクを使用する。少なくとも１つのタイムスロット割当てユニットが、前記ネットワークリンクにタイムスロットを割当て、不使用タイムスロットを導出し、且つ既に割当てられたタイムスロットに加えて前記導出された不使用タイムスロットを前記ネットワークリンクを使用する１つ又は複数の接続に割当てるために設けられる。
【００１６】
従って、タイムスロット割当て後に使用されていないタイムスロットが幾つかの接続に利用され、それらの接続の待ち時間が短縮される。
【００１７】
本発明はまた、複数の処理モジュール、及び該モジュールを結合するように構成されたネットワーク、並びに各々が前記処理モジュールの１つと前記ネットワークとの間に結合された複数のネットワーク・インターフェースを有する集積回路におけるタイムスロット割当て方法に関する。前記ネットワークは複数のルータを有し、該複数のルータはネットワークリンクを介して隣接するルータと結合されている。前記処理モジュール間の通信が前記ネットワーク内を通る接続経路を用いた接続上で実行され、該接続経路の各々が必要なタイムスロット数の間、少なくとも１つのネットワークリンクを使用する。タイムスロットの割当て中に使用されていないタイムスロットが導出され、前記ネットワークリンクを使用する１つ又は複数の接続に、既に割当てられたタイムスロットに加えて割当てられる。
【００１８】
本発明はさらに、複数の処理モジュール、及び該モジュールを結合するように構成されたネットワークを有するデータ処理システムに関する。当該データ処理システムはさらに、複数のネットワーク・インターフェースであり各々が前記処理モジュールの１つと前記ネットワークとの間に結合された複数のネットワーク・インターフェースを有する。前記ネットワークは複数のルータを有し、該複数のルータはネットワークリンクを介して隣接するルータと結合されている。前記処理モジュールは前記ネットワーク内を通る接続経路を用いた接続上で互いに通信し、その際、該接続経路の各々が必要なタイムスロット数の間、少なくとも１つのネットワークリンクを使用する。少なくとも１つのタイムスロット割当てユニットが、前記ネットワークリンクにタイムスロットを割当て、不使用タイムスロットを導出し、且つ既に割当てられたタイムスロットに加えて前記導出された不使用タイムスロットを前記ネットワークリンクを使用する１つ又は複数の接続に割当てるために設けられる。
【００１９】
従って、複数チップネットワーク、又は幾つかの別個の集積回路を備えるシステム若しくはネットワークにおいて、タイムスロット割当てが実行されてもよい。
【００２０】
本発明は、タイムスロット割当て後に不使用のタイムスロットを、既に割り当てられたタイムスロットに加えてネットワーク・オン・チップ環境内の接続に割り当てることによって利用し、その結果として上記接続の待ち時間を短縮するという考えに基づく。
【発明を実施するための最良の形態】
【００２１】
図面を参照して本発明についてより詳細に説明する。
【００２２】
以下の実施形態はシステム・オン・チップ、すなわち、同一チップ上の複数モジュールが或る種の相互接続を介して互いに通信するものに関する。相互接続はネットワーク・オン・チップＮｏＣとして具体化される。ネットワーク・オン・チップはネットワーク内にワイヤー、バス、時分割多重化、スイッチ、及び／又はルータを有し得る。ネットワークの伝送レイヤーにおいて、モジュール間の通信が接続上で実行される。接続は、第１のモジュールと少なくとも１つの第２のモジュールとの間の、各々が１組の接続特性を有する１組のチャネルと見なされる。第１のモジュールと単一の第２のモジュールとの間の接続では、接続は２つのチャネル、すなわち、第１のモジュールから第２のモジュールへのチャネルである要求チャネルと、第２のモジュールから第１のモジュールへの第２のチャネルである応答チャネルとを有し得る。要求チャネルは第１から第２のモジュールへのデータ及びメッセージのために確保され、一方、応答チャネルは第２から第１のモジュールへのデータ及びメッセージのために確保される。応答が不要な場合には、接続は１つのチャネルのみを有してもよい。しかしながら、接続が１つの第１のモジュールとN個の第２のモジュールを含む場合には、2N個のチャネルが設けられる。故に、接続、又はネットワークを介した接続の経路、すなわち接続経路は少なくとも１つのチャネルを有する。換言すれば、唯一のチャネルが用いられる場合、チャネルは接続の接続経路に一致する。上述のように２つのチャネルが用いられる場合には、１つのチャネルが例えばマスターからスレーブへの接続経路を提供する一方で、第２のチャネルはスレーブからマスターへの接続経路を提供する。従って、一般的な接続では、接続経路は２つのチャネルを有することになる。接続特性には、順序付け（順々のデータ伝送）、フロー制御（遠隔バッファが接続のために予約されるとともに、生成されたデータのために空間が利用可能であることが保証されるときに限ってデータ生成器がデータを送ることが可能にされる）、処理能力（処理能力の下限が保証される）、待ち時間（待ち時間の上限が保証される）、損失性（lossiness）（データの劣化）、伝送限界、トランザクションの完全性、データの正確性、優先度、又はデータ配送が含まれ得る。
【００２３】
図１は本発明に従ったネットワーク・オン・チップを示している。このシステムは幾つかの所謂インテレクチュアル・プロパティ・ブロックＩＰ（計算素子、メモリ又は内部に相互接続モジュールを含むサブシステム）を有し、その各々はそれぞれネットワーク・インターフェースNIを介してネットワークNに接続されている。ネットワークNは複数のルータRを有し、ルータRはそれぞれのリンクを介して隣接するルータRに接続されている。
【００２４】
ネットワーク・インターフェースNIは、ＩＰブロックとネットワークNとの間のインターフェースとして用いられる。ネットワーク・インターフェースNIは、ＩＰブロックがネットワークN又は他のＩＰブロックとの通信まで処理する必要なく、専用処理を実行できるように、それぞれのＩＰブロック及びネットワークNの通信を管理するために設けられている。ＩＰブロックはマスターとして機能して要求を発信してもよいし、スレーブとして機能してマスターから要求を受信し、それに応じて要求を処理してもよい。
【００２５】
図２は、図１に従ったネットワーク・オン・チップにおける接続及び基本的なスロット割当てのブロック図を示している。具体的には、マスターMとスレーブSとの間の接続が示されている。この接続はマスターMに結合されたネットワーク・インターフェースNI、２つのルータ、及びスレーブSに結合されたネットワーク・インターフェースNIによって実現されている。マスターMに結合されたネットワーク・インターフェースNIはタイムスロット割当てユニットSAを有する。あるいは、スレーブSに結合されたネットワーク・インターフェースNIもまたタイムスロット割当てユニットSAを有してもよい。マスターMに結合されたネットワーク・インターフェースNIと第１のルータRとの間には第１のリンクL1が存在し、２つのルータR間には第２のリンクL2が存在し、そしてルータとスレーブSに結合されたネットワーク・インターフェースNIとの間には第３のリンクL3が存在している。それぞれのネットワーク要素の出力ポートの３つのスロットテーブルST1乃至ST3も示されている。これらのスロットテーブルは、ネットワーク・インターフェースやルータのようなネットワーク要素の出力側、すなわち、データ作成側に実装されることが好ましい。要求されたスロット毎に、接続経路に沿ったリンクの各スロットテーブル内に１つのスロットが予約される。これら全てのスロットが空いていなければならない。すなわち、他のチャネルによって予約されていてはならない。データはスロットs=1から始まってスロット毎に１つのネットワーク要素から別のネットワーク要素へと進むので、接続に沿って次のスロットがスロットs=2にて、そしてその後スロットs=3にて、確保されなければならない。
【００２６】
タイムスロット割当てユニットSAによって実行されるスロット割当て決定への入力は、ネットワーク要素のような、その相互接続、及びスロットテーブルの大きさを伴うネットワーク接続形態、並びに一揃いの接続である。全ての接続に対し、その経路及びその帯域幅、待ち時間、ジッター、及び／又はスロット要求が与えられる。接続は少なくとも２つのチャネル又は接続経路（マスターからスレーブへの要求チャネル、及びスレーブからマスターへの応答チャネル）で構成される。これらのチャネルの各々は個々の経路上に設定され、異なる帯域幅、待ち時間、ジッター及び／又はスロット要求を有する別のリンクを有してもよい。時間関連の保証を提供するためには、リンクのためにスロットが確保されなければならない。ＴＤＭＡを用いることにより、別々の接続に対して別々のスロットが予約され得る。そして、接続へのデータが連続したスロットで連続したリンク上を接続に沿って転送される。
【００２７】
図３は、図２で実現されるテーブルをより詳細に示している。ここでは、２つのネットワーク・インターフェースNI1、NI2、２つのルータR1、R2、及び３つのリンクL1乃至L3が示されている。リンクL1乃至L3は、それぞれ、ネットワーク・インターフェースNI1とルータR1との間、ルータR1とルータR2との間、ルータR2とネットワーク・インターフェースNI2との間にある。ＩＰブロックは示されていない。標識付きのリンクL1乃至L3の各々にスロットテーブルST1乃至ST3が示されている。これらのリンクは双方向であるため、各リンクには２つの方向の各々に対してスロットテーブルが存在するが、１方向のスロットテーブルST1乃至ST3のみが示されている。さらに、３つの接続c1乃至c3が図示されている。上記の３つのスロットテーブルST1乃至ST3に加えて、さらなるスロットテーブルST4乃至ST6が示されている。これで、３つの接続c1乃至c3に関連する全てのスロットテーブルST1乃至ST6が示されている。第１の接続c1はネットワーク・インターフェースNI1からルータR1及びR2を介してネットワーク・インターフェースNI2へ伸びている。第２の接続c2はネットワーク・インターフェースNI1からルータR1へ、そしてスロットテーブルST4を用いる更なるネットワーク要素（図示せず）へと伸びている。第３の接続c3は、図示されていないネットワーク要素を起源とし、ルータR1からルータR2へ、そしてさらにスロットテーブルST6を用いる別の図示されていないネットワーク要素へと進行している。接続c1は、それが用いる３つのリンクL1乃至L3（NI1からR1、R1からR2、及びR2からNI2）の各々に１つのスロットを予約している。これらのリンクにおけるスロット（それぞれ、スロット２、スロット３及びスロット４）は連続していなければならない。ルータの視点からは、ルータはあるタイムスロットにおいて、接続c1乃至c3のうちのそのためにリンクL1乃至L3が予約された接続上の入力リンクからデータを受け取る。データはルータに保存される。同時に、ルータは先行スロットにおいて受け取ったデータを出力リンクに送る。この規範に従って、データは最大で１スロット間のみルータに保存されるので、接続のスロットは連続的に確保されなければならない。
【００２８】
スロット割当て問題の実行可能な一般化又は代替は、データがルータに１スロット期間より長くバッファされ得るようにすることである。その結果、スロット割当てはより柔軟になり、より多くのバッファリング及び潜在的により長い待ち時間という犠牲の下で、より良くリンクを利用することにつながり得る。
【００２９】
スロットはリンク上の衝突が生じないように予約されなければならない。２つの接続が同一リンクの同一スロットを予約できることはない。故に、c1はNI1とR1との間のリンクのスロット２を予約する。その結果、c2は同一リンクのスロット２を使用することができない。
【００３０】
図４は、実現される直接的なスロットテーブルを示しており、何れのスロットが何れの接続のために予約されているかを特定するテーブルを第１、第２及び第３のリンクL1乃至L3に実装することによるものである。具体的には、３つの接続c1乃至c3によって３つのリンクL1乃至L3に必要とされるスロットテーブルST1乃至ST3のみが示されている。このテーブルを記憶する好適位置は、リンクへのデータを作成するルータ／ネットワーク・インターフェース内、すなわち出力ポート内である。なぜなら、リンクへのデータを作成するために、リンクがいつ予約される、あるいはいつ予約されないかをルータ／ネットワーク・インターフェースは知る必要があるからである。テーブルはタイムスロット割当てユニットSAの部分であってもよい。
【００３１】
図５は、より効率的なスロット割当て符号化を示している。ここでも同様に、３つの接続c1乃至c3によって３つのリンクL1乃至L3に必要とされるスロットテーブルST1乃至ST3のみが示されている。スロットが何れの接続に属するかという情報がネットワーク・インターフェースNI内、特に、タイムスロット割当てユニットSA内に記憶される一方で、ルータのスロットテーブルST1乃至ST3はリンクにスロットが予約されているか否かの印を付けるのみである。ルータは、単に、パケットのヘッダ（宛先アドレス、又は宛先までの経路を含む）に基づいて１つのネットワーク要素から別のネットワーク要素へ、そして最終的には適切な出力へとデータを移動させるだけであるので、スロットに関連する接続が何れであるかを知る必要はない。
【００３２】
図６は、図４及び図５の上記符号化の実行可能な変形例を示している。ここでは、経路選択情報が（パケットヘッダの代わりに）ルータ自体に記憶される。出力ポートのスロットテーブルST1乃至ST3では、スロットは何れの入力からデータが取り込まれたかを指し示す。このようにして、パケットヘッダは省略可能であり、ルータ内のスロットテーブルが大きくなるという犠牲の下でスループットの向上がもたらされる。
【００３３】
図７は、本発明の好適な実施形態に従ったネットワーク・オン・チップを示している。このネットワーク・オン・チップは２つのルータR7、R4を有しており、ルータR7、R4はそれぞれ7×7、4×4のルータである。これら２つのルータは、それぞれ、８個のネットワーク・インターフェースNI1乃至NI8を介してさらなるＩＰブロックに接続されている。ＩＰブロックは、それぞれ、decomp（解凍器）ユニット、L0メモリユニット、ME/MC（動き予測／動き補償）ユニット、comp（圧縮器）ユニット、メモリMEM、さらなるdecompユニット、及びさらなるME/MCユニットである。それぞれのＩＰブロックに固有の機能は本発明の原理を説明するのに重要ではないので、それらの詳細な説明は省略することとする。
【００３４】
さらに、図７は、ネットワーク・インターフェースNIとルータR7、R4との間の各リンクに関する２つのスロットテーブルを示している。具体的には、１つのスロットテーブルは順方向に設けられており、もう１つは逆方向に設けられている。さらに、２つのルータR7、R4間で交信するため、ルータ間のリンクに２つのスロットテーブルが設けられている。すなわち、１つは順方向、もう１つは逆方向に設けられている。故に、このネットワーク・オン・チップの９個のリンクに対して全部で18個のスロットテーブルが示されている。なお、図には18個のスロットテーブルが示されているが、各ネットワーク・インターフェースには１つのスロットテーブルのみが必要であり、ルータはスロットテーブルを全く必要としない場合があるので、物理的には８個のスロットテーブルのみが存在するとしてもよい。
【００３５】
図７には、このネットワーク・オン・チップ内の幾つかの接続に関してタイムスロット割当てが実行された後の状態が示されており、一部のスロットテーブル（例として、第２のネットワーク・インターフェースNI2及び第３のネットワーク・インターフェースNI3に付随する順方向スロットテーブル、並びに第４及び第８のネットワーク・インターフェースNI4、NI8の逆方向スロットテーブル）は完全に予約されていることが見て取れる。その他のスロットテーブルの一部では、例えば、第５のネットワーク・インターフェースNI5に付随する順方向及び逆方向のスロットテーブルでは、20個のタイムスロットの内の１つが予約されているに過ぎない。
【００３６】
18個のスロットテーブル内には、予約済みのスロットが灰色の長方形で示され、空きタイムスロットが白色の長方形で示されている。ここでは、18個全てのスロットテーブルが20個のタイムテーブルを有し、それらを同期化し続けている。例えば、第１のネットワーク・インターフェースNI1との間のリンクの順方向スロットテーブルは、17個の予約済みタイムスロットと３個の空きタイムスロットとを有している。17個の予約済みタイムスロットの内、16個がある１つの接続に関連し、１個がさらなる接続に関連していてもよい。さらに、第８のネットワーク・インターフェースNI8とルータR7との間のリンクの順方向スロットテーブルは４個の予約済みスロットと16個の空きスロットとを有している。
【００３７】
18個のスロットテーブルの多くが空きスロット、すなわち、予約されていないスロットを有している理由は、相異なるＩＰブロックに必要とされるデータ速度は利用可能なデータ速度より小さいからである。スロットテーブルの大きさは、このネットワーク・オン・チップの全ての接続に対する接続要求に応えるために妥協したものである。それぞれのタイムスロットをスロットテーブルに割当てるために用いられるスロットテーブルの割当てアルゴリズムは、全てのスロットテーブルに対してスロットテーブルの断片化（fragmentation）、すなわち、相異なるスロットテーブル内の空きスロットを最小化するように設計されている。従って、このアルゴリズムは、ネットワーク・オン・チップ内の全ての接続を利用可能なスロットテーブルにマッピングし、それにより、完全に使用不能なスロットを最小化するものである。このようなタイムスロット割当ては、スロットテーブル内の最小数のタイムスロットを使用するので、利用上の観点から見れば好ましいものである。しかしながら、このようなタイムスロット割当てによってもたらされる待ち時間は最適からは程遠いものとなる場合がある。例えば、第８のネットワーク・インターフェースNI8に付随する順方向スロットテーブルは20個の利用可能なタイムスロットの内、４個の予約済みタイムスロットを有する。故に、16個のタイムスロットが空いており、最大で16サイクルも待たなければならないという最悪の場合のシナリオにもなり得る。しかしながら、不使用又は空きのタイムスロットは、あるＩＰブロックから他のＩＰブロックへの接続の待ち時間を短縮するために使用される。
【００３８】
図８は、図７に従ったネットワーク・オン・チップから選択された構成要素を示している。従って、図８では不要な構成要素は省略されている。具体的には、２つのルータR7、R4、第２、第６及び第８のネットワーク・インターフェースNI2、NI6、NI8、並びにそれらそれぞれの順方向及び逆方向のスロットテーブルが示されている。加えて、２つのルータR7、R4に付随する順方向及び逆方向のスロットテーブルも図８に示されている。さらに、２つの接続C1、C2もまた図８に示されている。第１の接続C1は、ME/MCからL0メモリに第８のネットワーク・インターフェースNI8、それに付随するスロットテーブルST1-F及びST1-R、第２のネットワーク・インターフェースNI2に付随するスロットテーブルST2-F及びST2-R、並びに第２のネットワーク・インターフェースNI2を介して通信するために、３個のタイムスロットを必要とする。第２の接続C2は、ME/MCからメモリMEMに第８のネットワーク・インターフェースNI8、それに付随する順方向スロットテーブルST1-F、ルータR7、２つのルータR7、R4間に付随するスロットテーブルST3-F、スロットテーブルST4-R、及び第６のネットワーク・インターフェースNI6を介して通信するために、１つのタイムスロットを必要とする。接続C1はルータR7を単に通過するだけであるので、要求される待ち時間とスループットとを保証するためには、順方向の２つのスロットテーブルすなわちST1-F及びST2-F、並びに逆方向の２つのスロットテーブルすなわちST1-R及びST2-Rのみが調整されなければならない。第２の接続C2の場合には、順方向の３つのスロットテーブルすなわちST1-F、ST3-F及びST4-F、並びに逆方向の３つのスロットテーブルすなわちST1-R、ST3-R及びST4-Rが調整されなければならない。
【００３９】
上述のように、接続の待ち時間はスロットテーブル内で割当てられた２つのタイムスロットの間隔に依存する。従って、接続の待ち時間を短縮するため、未だ不使用のタイムスロット群は存在中の接続の幾つかに割り当てられる。待ち時間短縮の手段として接続に割当てられ得る追加タイムスロット、すなわち、不使用又は空きのタイムスロットの数は、ネットワーク・オン・チップの一方から他方へとデータを転送する接続経路に沿った各スロットテーブルにおける利用可能なタイムスロット数の最小値である。上述のように、連続したタイムスロットが接続経路内のスロットテーブルに沿って予約されるべきである。
【００４０】
スロットテーブルST1-Fでは16個のタイムスロットが依然として利用可能である一方で、第２のネットワーク・インターフェースNI2に付随するスロットテーブルST2-Rで依存として利用可能なタイムスロットはただ１つであるので、第１の接続C1における待ち時間短縮のためには１つのスロットのみが使用され得る。第２の接続C2に関しては、３つのスロットテーブルST1-F、ST3-F、ST4-Rにおいては、それぞれ、15、16、16個のスロットが利用可能である。
【００４１】
従って、第１の接続C1には１つの追加スロットが割当て可能であり、第２の接続C2には15個の追加スロットが割当てられ得る。故に、最悪の場合の待ち時間の待機時間、すなわち、スロットテーブルの全スロット数から割当て済みのスロット数を引いたものは、第１の接続C1では17（20タイムスロット−３割当て済みスロット）から16（20スロット−（３割当て済みスロット＋１待ち時間短縮スロット））に短縮される。第２の接続C2についての最悪の場合の待機時間は、19（20スロット−１割当て済みスロット）から４（20スロット−（１割当て済みスロット＋15待ち時間短縮スロット））に短縮される。従って、待ち時間短縮の効果は、スロット割当て実行後の不使用又は空きタイムスロット数に大きく依存する。本発明に従ってこの技術を実行しないときには無駄にされていたスロットが利用されるだけであるので、スロット割当て後の不使用又は空きタイムスロットを利用することは、この技術が何らかのコストや複雑さをもたらさない限り効果的である。
【００４２】
好適な実施形態の原理が１つのスロットテーブルの接続に関して説明されただけであるが、ネットワーク・オン・チップ内のスロットテーブルにおける如何なる接続に関しても同一の技術が適用可能である。待ち時間短縮のために不使用スロットを利用する技術が複数の接続と複数のスロットテーブルとを有するネットワーク・オン・チップで実行される場合、待ち時間短縮に利用可能な不使用の空きスロットは、不使用スロット又は待ち時間が過剰なスロットを有するスロットテーブルを用いる接続群の間で分割又は共有されなければならない。
【００４３】
好ましくは、待ち時間の大きな短縮を必要とする接続が先ず扱われるように、ネットワーク・オン・チップ内の接続群に別々の優先度が結び付けられてもよい。これは優先度リストをタイムスロット割当てユニットに記憶させることによって実現されてもよい。
【００４４】
待ち時間短縮に使用され得る不使用スロットの特定をさらに改善するために、スロット割当てユニットSAはそれぞれのタイムスロットに、使用される、不使用、又は待ち時間短縮に確保済み、としてマーキングすることができる。このようなマーカーユニットMUをスロット割当てユニットSA内に実装するためには、２値ではなく３値を有するマーカーが設けられなければならない。第３の値、すなわち、待ち時間短縮に確保済み、はこれらのスロットを他の如何なる目的にも利用することを可能にし得る。このようなマーカーの実装は接続のスループット保証には影響を及ぼさないものである。
【００４５】
なお、実際に利用可能な待ち時間短縮は、ネットワーク・オン・チップ環境における所与の接続へのスロット割当てや、スロットテーブル内の不使用スロットの位置に依存する。上述の改善されたスロット割当て技術の利点は、データ転送のための接続の待ち時間が短縮されることである。この待ち時間短縮を実装することは如何なる追加コストや複雑さも伴うものではない。唯一の複雑さの増大は待ち時間ビットの削減によってもたらされる。このビットは、ネットワーク・オン・チップ環境内又は接続の特性を記憶する集権的管理（centralized  administration）ユニット内のスロットテーブルに置かれ得る。さらに、マーキングされたスロットがその他の目的にも利用可能であることを表すように追加マーカーが設けられてもよい。すなわち、それぞれの接続のスループット保証に影響を及ぼすことなく、そのスロットが別の接続に利用されるように構成されてもよい。
【００４６】
待ち時間短縮スロットの割当てはスロット割当て後に実行されてもよいし、あるいはスロット割当ての始めから並列で用いられてもよい。この待ち時間短縮スロット割当ては、多重同期化ＴＤＭＡで用いられてもよいが、単一ＴＤＭＡシステム（例えば、ソニック社のバックプレーン）で用いられてもよい。
【００４７】
続いて、上述の不使用スロットの導出前にタイムスロット割当てユニットSAに実装され得る実際のスロット割当て機能について説明する。その結果はスロット要求に一致するスロット割当てをもたらす。接続経路内の各リンク（link）に対し、そのリンクを使用する接続経路の各チャネルchiに要求される帯域幅（bandwidth）、待ち時間（latency）、ジッター（jitter）、優先度（priority）、及び／又はスロット数（slots）の関数として重要性（weight）が計算される：
【００４８】
【数１】
2008502263.tif 000003
あるいは、接続経路（path）内の少なくとも１つのチャネル（channel）の各リンクに対し、そのリンクを使用する各接続経路、すなわち、各チャネルに要求される或いは必要なスロット数の和として重要性が計算される：
【００４９】
【数２】
2008502263.tif 000004
そして、接続経路内の各チャネルに対し、接続経路の部分としてのチャネル経路におけるリンクの重要性、及び場合によりチャネルのその他の特性（例えば、帯域幅、待ち時間、優先度）の関数（例えば、加算）として重要性が計算される：
【００５０】
【数３】
2008502263.tif 000005
あるいは、各チャネル（すなわち、各接続経路）に対し、チャネル経路におけるリンクの重要性の和として重要性が計算される：
【００５１】
【数４】
2008502263.tif 000006
次に、上述の簡易化された関数である数２、数４に関してアルゴリズムを説明する。
【００５２】
このアルゴリズムは以下の擬似コードによって実行され得る：
−リンクの重要性の計算
ＦＯＲ  全チャネルＣ  ＤＯ
ＦＯＲ  全リンクＬ∈経路（Ｃ）  ＤＯ
重要性［Ｌ］＋＝スロット［Ｃ］
ＥＮＤ  ＦＯＲ
ＥＮＤ  ＦＯＲ
−チャネルの重要性の計算
ＦＯＲ  全チャネルＣ  ＤＯ
ＦＯＲ  全リンクＬ∈経路（Ｃ）  ＤＯ
重要性［Ｃ］＋＝重要性［Ｌ］
ＥＮＤ  ＦＯＲ
ＥＮＤ  ＦＯＲ
−スロット割当ての実行
ＢＥＧＩＮ
ＦＯＲ  重要性［Ｃ］によって降順に並べ替えられた全チャネル  ＤＯ
スロット［Ｃ］の空きスロットを見出し、それらをＣに割当て
ＥＮＤ  ＦＯＲ。
【００５３】
スロットは計算された重要性の降順でチャネルに割当てられる。要求されたスロット毎に、チャネル経路に沿ったリンクの各スロットテーブルに１つのスロットが予約される。これら全てのスロットが空いていなければならない。すなわち、その他のチャネルによって先に予約されていてはならない。これらのスロットは試行錯誤的に割当てられてもよく、その場合、ある特定のスロットから始めて、経路に沿ったリンクの全てで空きスロットが発見されるまで多数のスロットが調べられる。
【００５４】
スロット割当ては異なる方策を用いて試みられることも可能である。その例として、連続的なスロット、又は均一に分布されたスロットが挙げられる。複数の方策が必要とされる理由は、種々の方策を用いることにより種々の特性が最適化され得ることである。例えば、連続的なスロットはヘッダのオーバーヘッドを削減し得る一方で、均一に分布されたスロットは待ち時間を短縮し得る。
【００５５】
提案された技法はＯ（Ｃ×Ｌ×Ｓ）という低い複雑性を有する。ここで、Ｃはチャネル数、Ｌはリンク数、そしてＳはスロットテーブルの大きさである。このアルゴリズムを用いて得られるスロット割当ては最適（Ｏ（ＳＣ）という遙かに高い複雑性で得られる）に近く、欲張り（greedy）アルゴリズム（すなわち、ランダムな順番でのチャネル割当て）より２倍優れている。
【００５６】
続いて、これに代わるアルゴリズム例について説明する。この場合も、各リンクに対し、そのリンクを使用する各チャネルに要求されるスロット数の和として重要性が計算される：
【００５７】
【数５】
2008502263.tif 000007
そして、各チャネルに対し、チャネル経路内のリンクの重要性の和として重要性が計算される：
【００５８】
【数６】
2008502263.tif 000008
ここで、a1、a2及びa3は定数である（これは重み付け公式の一例であり、その他も可能である）。また、lengthは長さを表す。
【００５９】
このアルゴリズム例は以下の擬似コードによって実行され得る：
−リンクの重要性の計算
ＦＯＲ  全チャネルＣ  ＤＯ
ＦＯＲ  全リンクＬ∈経路（Ｃ）  ＤＯ
重要性［Ｌ］＋＝スロット［Ｃ］
ＥＮＤ  ＦＯＲ
ＥＮＤ  ＦＯＲ
−チャネルの重要性の計算
ＦＯＲ  全チャネルＣ  ＤＯ
ＦＯＲ  全リンクＬ∈経路（Ｃ）  ＤＯ
重要性［Ｃ］＋＝重要性［Ｌ］
ＥＮＤ  ＦＯＲ
重要性［Ｃ］＝a1×重要性［Ｃ］＋a2×長さ［Ｃ］＋a3×スロット［Ｃ］
ＥＮＤ  ＦＯＲ
−スロット割当ての実行
ＢＥＧＩＮ
ＦＯＲ  重要性［Ｃ］によって降順に並べ替えられた全チャネル  ＤＯ
スロット［Ｃ］の空きスロットを見出し、それらをＣに割当て
ＥＮＤ  ＦＯＲ。
【００６０】
第２実施形態に従ったリンクの重要性計算は第１のコードに記述された通りであるが、チャネルの重要性は異なった計算が為される。このチャネルの重み付け公式に込められた着想は、最初にスケジューリングされるように高い重要性が与えられたことに従って、使用頻度の高いリンクを通るときに、すなわち、ホットスポット（大きい負荷を伴うため、多くのスロットが予約されるべきリンク）を通行するときに、より多くのスロットを必要とするチャネルと、長い経路を有するチャネルとからスケジューリングを始めることである。その理由は、これらの接続はより多くの制約を有するため、最後まで残されると空きスロットを見出す機会が少なくなるからである。それとは対照的に、使用頻度の低いリンクを通行する短めのチャネルはスロットを見出す自由度がより大きいため、スロット割当ての最後の方まで残されてもよい。
【００６１】
スロットは計算された重要性の降順でチャネル（すなわち、各接続経路）に割当てられてもよい。要求されたスロット毎に、図２に示されるようなチャネル経路に沿ったリンクの各スロットテーブルに１つのスロットが予約される。これら全てのスロットが空いていなければならない。すなわち、その他のチャネル（すなわち、各接続経路）によって先に予約されていてはならない。これらのスロットは試行錯誤的に割り当てられてもよく、その場合、ある特定のスロットから始めて、経路に沿った全リンク内に必要数の空きスロットが発見されるまでスロットが調べられる。アルゴリズムのトレース例は以下に記載される。
【００６２】
図９は空きタイムスロットを発見する方法を示している。ここでは、一例として大きさが16のスロットテーブルが図示されている。スロット発見プロセスは様々な手法で実行され得る。一例は欲張り手法でスロットを、すなわち、最初のN個の空きスロットを発見するものである。他の一例はバッファ空間を最小化するために等しく離れたスロットを発見するものである。これは、第１の空きスロットffsを発見した後にスロットテーブル内で等しく離れた位置を計算し、計算位置の周辺で最も近い空き位置を発見するように局所的に探索することによって為され得る。予約済みのスロットは図９では‘×’印を付されている。第１の空きスロットffsはスロット2である。16スロット存在するので、その他の２つのスロットに理想的な位置（第２位置ip2、第３位置ip3）は、それぞれ、スロット7及び13となる（それらの間に等距離を設けるため）。スロット7は予約済みであるので、空きスロットはスロット7の近辺で探索される。発見される最も近い空きスロットはスロット5である。スロット13は空いているので、そのまま予約され得る。従って、予約された３スロットは黒丸印が付された2、5及び13である。
【００６３】
接続のための空きスロットは完全な経路に沿って空いているスロットである。すなわち、経路に沿った連続的なリンクにおいて連続的なタイムスロットが空いているべきである。故に、ある特定の接続のための空きスロットを発見するためには、接続経路に沿った全スロットテーブルが調べられなければならない。接続のための空きスロットを探索する簡易な手法は、その接続の第１のリンクから始め、予約済みのものを飛ばしながら経路に沿って後続の全スロットテーブルを試すことである。探索時間を最小化するため、最も負荷が大きいリンクから始めてもよい。
【００６４】
図１０は、図５で説明されたようにスロットの予約のみが（1ビットで）記憶される場合の、空きスロット探索を高速化する別の技法を示している。これは複数のスロットを並列に調査することに基づく。この技法の実行は、ハードウェア（任意の固定数のビットを調査するユニット、すなわち、タイムスロット割当てユニットSA）、及びソフトウェア（ＣＰＵのデータワードは例えば16又は32個のスロット予約を同時に記憶可能である）の何れでも可能である。図１０の左側にはリンクL1乃至L4用のスロットテーブル1stが一例として示されている。右側には経路に沿った空きスロットを導出するために用いられる空きスロットワードfswが示されている。空きスロットは、スロットテーブルを横断し、予約済みのスロットをフィルタリングし、そして探索済みのスロットをリンク毎に位置を１つ移す（図の>>(1)）ことによって発見される（必要とされるスロット配置に対応する）。最初に、予約済みのスロット0、1、6、9、11、12及び14を有する、経路の第１のリンクL1が選ばれる。これらのスロットは予約済みとして空きスロットワード内に例えば‘×’印を付して示されている。その後、空きスロットワードfswはスロット配置を反映するように右に位置を１つ移され、ＯＲ操作が実行されて第２のリンクの予約済みスロット（スロット3、6、10及び12）に足し合わされる。これらのステップが第３及び第４のリンクL3及びL4でも繰り返され、その結果、経路に沿った全リンクにおける空きスロットのベクトルが得られる。これを第１のリンクL1に揃えるため、これは左に３つ位置を移される。その結果、第１のリンクL1のスロット4、8、10及び13は所定の経路に沿った全リンクL1乃至L4において空いていることが得られる。具体的には、スロット4がリンクL1で空いているとともに、スロット5、6及び7が、それぞれ、リンクL2、L3及びL4で空いている。スロット8がリンクL1で空いているとともに、スロット9、10及び11が、それぞれ、リンクL2、L3及びL4で空いている。さらに、スロット10がリンクL1で空いているとともに、スロット11、12及び13が、それぞれ、リンクL2、L3及びL4で空いている。スロット13がリンクL1で空いているとともに、スロット14、15及び0が、それぞれ、リンクL2、L3及びL4で空いている。
【００６５】
図１１は、４個のルータR1乃至R4及び７個のネットワーク・インターフェースNI（NI1乃至NI7から成るネットワーク・オン・チップの一例を示している。ネットワーク・インターフェースが接続されたＩＰブロックは図示されていない。一例として、12個の接続C1乃至C12が選択される。これらの接続はネットワーク・インターフェースNIに取り付けられた（図示されていない）ＩＰモジュール間でデータを運ぶために用いられ、故に、２つのネットワーク・インターフェースNI間には常に接続が設定されている。実際には双方向接続（２チャンネル）も存在し得るが、単純化のため、全ての接続が単方向性（単チャネルから成る）であると仮定する。例えば、接続C1はNI1から始まり、R1及びR4を通ってNI6に到達する。同様に、接続C2はNI1、R1、R2、R3及びNI4を進行する。接続C3はNI1、R1、R2及びNI2を進行する。接続C4はNI2、R2、R3、R4及びNI7を進行する。接続C5はNI2、R2及びNI3を進行する。接続C6はNI3、R2、R1及びNI1を進行する。接続C7はNI3、R2、R3及びNI5を進行する。接続C8はNI4、R3及びNI5を進行する。接続C9はNI5、R3、R4、R1及びNI1を進行する。接続C10はNI6、R4、R3、R2及びNI2を進行する。接続C11はNI7、R4、R3、R2及びNI3を進行する。接続C12はNI7、R4、R1及びNI1を進行する。各接続に対し、ある数のスロットが確保されなければならない。これらの数は図９の右側にリスト化されている。すなわち、接続C1乃至C12は、それぞれ、1、1、5、2、4、3、2、6、1、2、1及び2個のスロットを必要とする。
【００６６】
図１２は、図１１に従ったネットワーク・オン・チップを示している。アルゴリズムはリンクの重要性を計算することから始まる。これは、各リンクに対し、そのリンクを使用する全ての接続に要求されるスロット数を加算することによって為される。これは各方向に対し別々に行われる。リンクは○印で囲まれ、リンク重要性の結果はその隣に書かれている。例えば、R2からR3へのリンクでは、接続C2、C4及びC7によって要求されるスロットが加算される。これにより、1（C2）＋2（C4）＋2（C7）＝5というリンク重要性が得られる。NI1とR1との間のリンクは７スロットを必要とし、R1とNI1との間のリンクは６スロットを必要とする等々となる。アルゴリズムが接続の重要性を計算する。接続重み付け公式において、a1=1、a2=0、及びa3=0（すなわち、リンク重要性の和）としている。あるいは、異なる値が選択されてもよい。接続重要性の結果は図１１の右側に示されている。例えば、接続C1の重要性は、NI1からR1、R1からR4、及びR4からNI6へのリンクの重要性の和であり、それは7＋1＋1＝9である。そして、接続は計算された重要指数に関して降順に並べ替えられ、その順番にスケジューリングされる。
【００６７】
図１３は、全接続C1乃至C12に対するタイムスロット割当てを示している。必要な空きスロットが最初に割当てられることを前提としている。一例として、スロットテーブルは９スロットの大きさである。スロットテーブル内に表された数は、これらのスロットが割り当てられているそれぞれの接続C1乃至C12に対応している。
【００６８】
５スロットを必要とする接続C3に対しては、全てのスロットが空いているので、NI1からR1へのリンクのスロット1乃至5、R1からR2へのリンクのスロット2乃至6、R2からNI2へのリンクのスロット3乃至7が割当てられる。１スロットを必要とする接続C2に対しては、第１のリンクの最初の５スロットは予約済みであるので、経路に沿ったそれぞれのスロットテーブルにおいてスロット6、7、8及び9を予約する。２スロットを必要とする接続C7は最初の２つのスロットで衝突を起こさないので、そこを割り当てる。２スロットを必要とする接続C4は、最初の２つのスロットは第２のリンク（R2からR3）においてC7に予約済みなので、スロット3及び4を予約できるのみである。接続C11も衝突を起こさずに、ネットワーク・インターフェースNI7とルータR4とのリンクのスロットテーブルにおける最初のスロット、及びその他のリンクのスロットテーブルにおける連続するスロットを予約する。
【００６９】
しかしながら、２スロットを必要とする接続C10の場合には、最初の４つのスロットはR2からNI2へのリンクにおいてC3に予約されたスロットと衝突するため、最初の空きスロットは5及び6である。接続C6は３つのスロット、すなわち、ネットワーク・インターフェースNI3とルータR2とのリンクのスロット3乃至5、ルータR2とルータR1とのリンクのスロットテーブルのスロット4乃至6、及びルータR1とネットワーク・インターフェースNI1とのリンクのスロットテーブルのスロット5乃至7を割当てる。接続C8は６つのスロット、すなわち、ネットワーク・インターフェースNI4とルータR3とのリンクのスロット1及び4乃至8、及びルータR3とネットワーク・インターフェースNI5とのリンクのスロットテーブルのスロット2及び5乃至9を割当てる。なぜなら、ルータR3とネットワーク・インターフェースNI5とのリンクのスロットテーブルのスロット3及び4は接続C7に既に割当てられている、すなわち、予約されているからである。
【００７０】
接続C9は１つのスロット、すなわち、ネットワーク・インターフェースNI5とルータR3とのリンクのスロット1、ルータR3とルータR4とのリンクのスロットテーブルのスロット2、ルータR4とルータR1とのリンクのスロットテーブルのスロット3、及びルータR1とネットワーク・インターフェースNI1とのリンクのスロットテーブルのスロット4を割当てる。接続C12は２つのスロット、すなわち、ネットワーク・インターフェースNI7とルータR4とのリンクのスロット6及び7、ルータR4とルータR1とのリンクのスロット7及び8、及びルータR1とネットワーク・インターフェースNI1とのリンクのスロットテーブルのスロット8及び9を割当てる。なぜなら、ルータR1とネットワーク・インターフェースNI1とのリンクのスロットテーブルのスロット4及び5乃至7は、それぞれ、接続C9及びC6に既に割当てられているからである。
【００７１】
接続C5は４つのスロット、すなわち、ネットワーク・インターフェースNI2とルータR2とのリンクのスロットテーブルのスロット1及び2並びに5及び6、及びルータR2とネットワーク・インターフェースNI3とのリンクのスロットテーブルのスロット2及び3並びに6及び7を割当てる。なぜなら、ネットワーク・インターフェースNI2とルータR2とのリンクのスロットテーブルのスロット3及び4は接続C4に既に割当てられているからである。最後に、接続C1は１つのスロット、すなわち、ネットワーク・インターフェースNI1とルータR1とのリンクのスロットテーブルのスロット7、ルータR1とルータR4とのリンクのスロットテーブルのスロット8、及びルータR4とネットワーク・インターフェースNI6とのリンクのスロットテーブルのスロット9を割当てる。従って、スロット割当ての最終結果は図１３に示されるとおりである。
【００７２】
スロットテーブル割当てが実行された後、依然として不使用のビットの導出が上述と同様の手法で実行可能であり、それにより、少なくとも１つの接続に割り当てられることによって待ち時間短縮に使用され得るタイムスロットが特定される。
【００７３】
タイムスロット割当てユニットは上述ではネットワーク・インターフェースに配置されるように述べられているが、タイムスロット割当てユニットはネットワーク内のルータに配置されてもよい。
【００７４】
上述されたタイムスロット割当ては、単一チップ上のネットワークだけではなく、幾つかの別個の集積回路又は複数チップネットワークを有する如何なるデータ処理装置にも適用可能である。
【００７５】
上述の実施形態は本発明を例示するものであり、本発明を限定するものではない。また、当業者によって、添付の請求項の範囲を逸脱することなく、多数の代替実施形態が設計され得るものである。請求項において、用語“有する”は列挙された要素若しくはステップ以外の要素若しくはステップの存在を排除するものではない。要素の前に置かれた用語“或る”はその要素が複数存在することを排除するものではない。幾つかの手段を列挙するデバイスの請求項において、これらの手段の幾つかは１つ且つ同一のハードウェア品目によって具体化され得るものである。ある特定の手段が相互に異なる従属項に挙げられているという単なる事実は、これらの手段の組み合わせが効果的に用いられ得ないことを指し示すものではない。
【図面の簡単な説明】
【００７６】
【図１】本発明に従ったネットワーク・オン・チップの基本構成を示す図である。
【図２】図１に従ったネットワークにおける接続への基本的なスロット割当てを示す図である。
【図３】図１に従ったネットワークにおけるスロット割当てをより詳細に示す図である。
【図４】本発明に従った、より詳細なスロット割当てを示す図である。
【図５】本発明に従った、より詳細なスロット割当てを示す図である。
【図６】本発明に従った、より詳細なスロット割当てを示す図である。
【図７】第１実施形態に従ったネットワーク・オン・チップ環境を示す図である。
【図８】図７のネットワーク・オン・チップ環境の一部を示す図である。
【図９】空きスロットを発見する方法を例示する図である。
【図１０】幾つかの接続を有するネットワーク・オン・チップを示す図である。
【図１１】計算されたリンク重要性を伴う図９に従ったネットワーク・オン・チップを示す図である。
【図１２】計算された接続重要性を伴う図１０に従ったネットワーク・オン・チップを示す図である。
【図１３】図１０に従った全ての接続に対する詳細なスロット割当てを示す図である。
【図１】
2008502263.tif 000009
【図２】
2008502263.tif 000010
【図３】
2008502263.tif 000011
【図４】
2008502263.tif 000012
【図５】
2008502263.tif 000013
【図６】
2008502263.tif 000014
【図７】
2008502263.tif 000015
【図８】
2008502263.tif 000016
【図９】
2008502263.tif 000017
【図１０】
2008502263.tif 000018
【図１１】
2008502263.tif 000019
【図１２】
2008502263.tif 000020
【図１３】
2008502263.tif 000021
【国際調査報告】
2008502263.tif 000022
2008502263.tif 000023