(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）が、接続経路（C1乃至C12）の少なくとも１つのネットワークリンク（L）に対し、少なくとも１つのネットワークリンク（L）への少なくとも１つの接続要求の関数としてリンク重要指数を計算し、少なくとも１つの接続経路（C1乃至C12）に対し、接続経路（C1乃至C12）の少なくとも１つのネットワークリンク（L）に対して計算されたリンク重要指数の関数として接続経路重要指数を計算し、且つ計算された接続経路重要指数に従ってネットワークリンク（L）にタイムスロットを割当てるために設けられる。
2007532075.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では、スロットは何れの入力からデータが取り込まれたかを指し示す。このようにして、パケットヘッダは省略可能であり、ルータ内のスロットテーブルが大きくなるという犠牲の下でスループットの向上がもたらされる。
【００４０】
続いて、タイムスロット割当てユニットSAにて実施され得る実際のスロット割当て関数について説明する。その結果はスロット要求に一致するスロット割当てをもたらす。接続経路内の各リンク（link）に対し、そのリンクを使用する接続経路の各チャネルchiに要求される帯域幅（bandwidth）、待ち時間（latency）、ジッター（jitter）、優先度（priority）、及び／又はスロット数（slots）の関数として重要性（weight）が計算される：
【００４１】
【数１】
2007532075.tif 000003
あるいは、接続経路（path）内の少なくとも１つのチャネル（channel）の各リンクに対し、そのリンクを使用する各接続経路、すなわち、各チャネルに要求される或いは必要なスロット数の和として重要性が計算される：
【００４２】
【数２】
2007532075.tif 000004
そして、接続経路内の各チャネルに対し、接続経路の部分としてのチャネル経路におけるリンクの重要性、及び場合によりチャネルのその他の特性（例えば、帯域幅、待ち時間、優先度）の関数（例えば、加算）として重要性が計算される：
【００４３】
【数３】
2007532075.tif 000005
あるいは、各チャネル（すなわち、各接続経路）に対し、チャネル経路におけるリンクの重要性の和として重要性が計算される：
【００４４】
【数４】
2007532075.tif 000006
次に、上述の簡易化された関数である数２、数４に関してアルゴリズムを説明する。
【００４５】
このアルゴリズムは以下の擬似コードによって実行され得る：
−リンクの重要性の計算
ＦＯＲ  全チャネルＣ  ＤＯ
ＦＯＲ  全リンクＬ∈経路（Ｃ）  ＤＯ
重要性［Ｌ］＋＝スロット［Ｃ］
ＥＮＤ  ＦＯＲ
ＥＮＤ  ＦＯＲ
−チャネルの重要性の計算
ＦＯＲ  全チャネルＣ  ＤＯ
ＦＯＲ  全リンクＬ∈経路（Ｃ）  ＤＯ
重要性［Ｃ］＋＝重要性［Ｌ］
ＥＮＤ  ＦＯＲ
ＥＮＤ  ＦＯＲ
−スロット割当ての実行
ＢＥＧＩＮ
ＦＯＲ  重要性［Ｃ］によって降順に並べ替えられた全チャネル  ＤＯ
スロット［Ｃ］の空きスロットを見出し、それらをＣに割当て
ＥＮＤ  ＦＯＲ。
【００４６】
スロットは計算された重要性の降順でチャネルに割当てられる。要求されたスロット毎に、チャネル経路に沿ったリンクの各スロットテーブルに１つのスロットが予約される。これら全てのスロットが空いていなければならない。すなわち、その他のチャネルによって先に予約されていてはならない。これらのスロットは試行錯誤風に割り当てられてもよく、その場合、ある特定のスロットから始めて、経路に沿ったリンクの全てで空きスロットが発見されるまで多数のスロットが調べられる。
【００４７】
スロットの割当ては異なる方策を用いて試みられることも可能である。その例として、連続的なスロット、又は均一に分布されたスロットが挙げられる。複数の方策が必要とされる理由は、種々の方策を用いることにより種々の特性が最適化され得ることである。例えば、連続的なスロットはヘッダのオーバーヘッドを低減し得る一方で、均一に分布されたスロットは待ち時間を低減し得る。
【００４８】
提案された技法はＯ（Ｃ×Ｌ×Ｓ）という低い複雑性を有する。ここで、Ｃはチャネル数、Ｌはリンク数、そしてＳはスロットテーブルの大きさである。このアルゴリズムを用いて得られるスロット割当ては最適（Ｏ（ＳＣ）という遙かに高い複雑性で得られる）に近く、欲張り（greedy）アルゴリズム（すなわち、ランダムな順番でのチャネル割当て）より２倍優れている。
【００４９】
続いて、これに代わるアルゴリズム例について説明する。この場合も、各リンクに対し、そのリンクを使用する各チャネルに要求されるスロット数の和として重要性が計算される：
【００５０】
【数５】
2007532075.tif 000007
そして、各チャネルに対し、チャネル経路内のリンクの重要性の和として重要性が計算される：
【００５１】
【数６】
2007532075.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、C2、C7、C4、C11、C10、C6、C8、C9、C12、C5及びC1の割当てを示している。
【００６３】
図１２に従って、５スロットを必要とする接続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を割当てる。従って、スロット割当ての最終結果は図２３に示されるとおりである。
【００６８】
タイムスロット割当てユニットは上述ではネットワーク・インターフェースに配置されるように述べられているが、タイムスロット割当てユニットはネットワーク内のルータに配置されてもよい。
【００６９】
上述されたタイムスロット割当ては、単一チップ上のネットワークだけではなく、幾つかの別個の集積回路又は複数チップネットワークを有する如何なるデータ処理装置にも適用可能である。
【００７０】
上述の実施形態は本発明を例示するものであり、本発明を限定するものではない。また、当業者によって、添付の請求項の範囲を逸脱することなく、多数の代替実施形態が設計され得るものである。請求項において、用語“有する”は列挙された要素若しくはステップ以外の要素若しくはステップの存在を排除するものではない。要素の前に置かれた用語“或る”はその要素が複数存在することを排除するものではない。幾つかの手段を列挙するデバイスの請求項において、これらの手段の幾つかは１つ且つ同一のハードウェア品目によって具体化され得るものである。ある特定の手段が相互に異なる従属項に挙げられているという単なる事実は、これらの手段の組み合わせが効果的に用いられ得ないことを指し示すものではない。
【図面の簡単な説明】
【００７１】
【図１】本発明に従ったネットワーク・オン・チップの基本構成を示す図である。
【図２】図１に従ったネットワークにおける接続への基本的なスロット割当てを示す図である。
【図３】図１に従ったネットワークにおけるスロット割当てをより詳細に示す図である。
【図４】第１実施形態に従った、より詳細なスロット割当てを示す図である。
【図５】第２実施形態に従った、より詳細なスロット割当てを示す図である。
【図６】第３実施形態に従った、より詳細なスロット割当てを示す図である。
【図７】空きスロットを発見する方法を例示する図である。
【図８】空きスロットを発見する他の方法を示す図である。
【図９】幾つかの接続を有するネットワーク・オン・チップを示す図である。
【図１０】計算されたリンク重要性を伴う図９に従ったネットワーク・オン・チップを示す図である。
【図１１】計算された接続重要性を伴う図１０に従ったネットワーク・オン・チップを示す図である。
【図１２】図９乃至１１に従った、それぞれの接続に対する詳細なスロット割当てを示す図である。
【図１３】図９乃至１１に従った、それぞれの接続に対する詳細なスロット割当てを示す図である。
【図１４】図９乃至１１に従った、それぞれの接続に対する詳細なスロット割当てを示す図である。
【図１５】図９乃至１１に従った、それぞれの接続に対する詳細なスロット割当てを示す図である。
【図１６】図９乃至１１に従った、それぞれの接続に対する詳細なスロット割当てを示す図である。
【図１７】図９乃至１１に従った、それぞれの接続に対する詳細なスロット割当てを示す図である。
【図１８】図９乃至１１に従った、それぞれの接続に対する詳細なスロット割当てを示す図である。
【図１９】図９乃至１１に従った、それぞれの接続に対する詳細なスロット割当てを示す図である。
【図２０】図９乃至１１に従った、それぞれの接続に対する詳細なスロット割当てを示す図である。
【図２１】図９乃至１１に従った、それぞれの接続に対する詳細なスロット割当てを示す図である。
【図２２】図９乃至１１に従った、それぞれの接続に対する詳細なスロット割当てを示す図である。
【図２３】図９乃至１１に従った、それぞれの接続に対する詳細なスロット割当てを示す図である。
【図１】
2007532075.tif 000009
【図２】
2007532075.tif 000010
【図３】
2007532075.tif 000011
【図４】
2007532075.tif 000012
【図５】
2007532075.tif 000013
【図６】
2007532075.tif 000014
【図７】
2007532075.tif 000015
【図８】
2007532075.tif 000016
【図９】
2007532075.tif 000017
【図１０】
2007532075.tif 000018
【図１１】
2007532075.tif 000019
【図１２】
2007532075.tif 000020
【図１３】
2007532075.tif 000021
【図１４】
2007532075.tif 000022
【図１５】
2007532075.tif 000023
【図１６】
2007532075.tif 000024
【図１７】
2007532075.tif 000025
【図１８】
2007532075.tif 000026
【図１９】
2007532075.tif 000027
【図２０】
2007532075.tif 000028
【図２１】
2007532075.tif 000029
【図２２】
2007532075.tif 000030
【図２３】
2007532075.tif 000031
【国際調査報告】
2007532075.tif 000032
2007532075.tif 000033