(57)【要約】  様々なチャネルがビット数において異なる幅を有するシステムインターコネクトの構築に関するシステム及び方法である。このような不均一チャネルＮｏＣインターコネクトを構築する処理が本願において開示されている。チャネル幅は、バンド幅及び当該システムの様々なコンポーネント間の遅延の仕様に基づいて決定され得る。
2016503594.tif 000002
【特許請求の範囲】
【請求項１】
ネットワークオンチップ（ＮｏＣ）内の複数のチャネルの各々の幅を、前記複数のチャネルの各々の少なくとも１つのパフォーマンス目標または前記複数のチャネルの各々の最大データフローに基づいて決定し、前記複数のチャネルのうちの少なくとも１つに前記複数のチャネルのうちの他の少なくとも１つと異なる幅を有せしめるステップを含むことを特徴とする方法。
【請求項２】
請求項１に記載の方法であって、前記複数のチャネルのうちの接続されているものの間においてメッセージ再フォーマッタを形成するステップをさらに含み、前記メッセージ再フォーマッタが前記複数のチャネルのうちの前記接続されているものの間において１または複数のメッセージのフリット（flit）を調整することを特徴とする方法。
【請求項３】
請求項２に記載の方法であって、前記メッセージ再フォーマッタが前記１または複数のメッセージを調整し、前記ＮｏＣの全ての送信元及び送信先端ホストのペアが端末間でのメッセージサイズ及びメッセージフォーマットの一貫性を維持することを特徴とする方法。
【請求項４】
請求項１に記載の方法であって、前記複数のチャネルの各々の前記最大データフローは、最大データフローアルゴリズムを前記複数のチャネルのデータトラフィックのグラフに適用することによって判定されることを特徴とする方法。
【請求項５】
請求項１に記載の方法であって、前記複数のチャネルの各々の前記幅を決定するステップは、線形計画法を適用して、少なくとも１つの特定のコスト関数を最小化しつつ前記少なくとも１つのパフォーマンス目標を満たす前記幅を決定するステップをさらに含むことを特徴とする方法。
【請求項６】
請求項５に記載の方法であって、前記線形計画法を適用するステップは、仮想チャネル及び物理チャネルのパフォーマンス要求に関する制約のリストを構築するステップをさらに含み、少なくとも１つの目的関数は、前記制約のリストに基づいて、前記少なくとも１つのパフォーマンス目標の各々に対して導き出されることを特徴とする方法。
【請求項７】
請求項１に記載の方法であって、前記少なくとも１つのパフォーマンス目標は遅延要求を含み、最短経路ルーティングが前記複数のチャネルに適用されて前記遅延要求が満たされることを特徴とする方法。
【請求項８】
処理を実行するための命令をコンピュータ可読記憶媒体であって、
前記命令は、ネットワークオンチップ（ＮｏＣ）内の複数のチャネルの各々の幅を、前記複数のチャネルの各々の少なくとも１つのパフォーマンス目標または前記複数のチャネルの各々の最大データフローに基づいて決定し、前記複数のチャネルのうちの少なくとも１つに前記複数のチャネルのうちの他の少なくとも１つと異なる幅を有せしめるステップを含むことを特徴とするコンピュータ可読記憶媒体。
【請求項９】
請求項８に記載のコンピュータ可読記憶媒体であって、前記命令が、前記複数のチャネルのうちの接続されているものの間においてメッセージ再フォーマッタを形成するステップをさらに含み、前記メッセージ再フォーマッタが前記複数のチャネルのうちの前記接続されているものの間において１または複数のメッセージのフリットを調整することを特徴とするコンピュータ可読記憶媒体。
【請求項１０】
請求項９に記載のコンピュータ可読記憶媒体であって、前記メッセージ再フォーマッタが前記１または複数のメッセージを調整し、前記ＮｏＣの全ての送信元及び送信先端ホストのペアが端末間でのメッセージサイズ及びメッセージフォーマットの一貫性を維持することを特徴とするコンピュータ可読記憶媒体。
【請求項１１】
請求項８に記載のコンピュータ可読記憶媒体であって、前記複数のチャネルの各々の前記最大データフローは、最大データフローアルゴリズムを前記複数のチャネルのデータトラフィックのグラフに適用することによって判定されることを特徴とするコンピュータ可読記憶媒体。
【請求項１２】
請求項８に記載のコンピュータ可読記憶媒体であって、前記複数のチャネルの各々の前記幅を決定するステップは、線形計画法を適用して、少なくとも１つの特定のコスト関数を最小化しつつ前記少なくとも１つのパフォーマンス目標を満たす前記幅を決定するステップをさらに含むことを特徴とするコンピュータ可読記憶媒体。
【請求項１３】
請求項１２に記載のコンピュータ可読記憶媒体であって、前記線形計画法を適用するステップは、仮想チャネル及び物理チャネルのパフォーマンス要求に関する制約のリストを構築するステップをさらに含み、前記命令は、前記制約のリストに基づいて、前記少なくとも１つのパフォーマンス目標の各々に対して少なくとも１つの目的関数を導き出すステップを含むことを特徴とするコンピュータ可読記憶媒体。
【請求項１４】
請求項８に記載のコンピュータ可読記憶媒体であって、前記少なくとも１つのパフォーマンス目標は遅延要求を含み、前記命令は、最短経路ルーティングを前記複数のチャネルに適用して前記遅延要求をみたすステップをさらに含むことを特徴とするコンピュータ可読記憶媒体。
【請求項１５】
ネットワークオンチップ（ＮｏＣ）内の複数のチャネルの各々の幅を、前記複数のチャネルの各々の少なくとも１つのパフォーマンス目標または前記複数のチャネルの各々の最大データフローに基づいて決定し、前記複数のチャネルのうちの少なくとも１つに前記複数のチャネルのうちの他の少なくとも１つと異なる幅を持たせる幅調整モジュールを含むことを特徴とするシステム。
【請求項１６】
請求項１５に記載のシステムであって、前記複数のチャネルのうちの接続されているものの間においてメッセージ再フォーマッタを形成するメッセージ再フォーマッタモジュールをさらに含み、前記メッセージ再フォーマッタが前記複数のチャネルのうちの前記接続されているものの間において１または複数のメッセージのフリットを調整することを特徴とするシステム。
【請求項１７】
請求項１６に記載のシステムであって、前記メッセージ再フォーマッタが１または複数のメッセージを調整し、前記ＮｏＣの全ての送信元及び送信先端ホストのペアが端末間でのメッセージサイズ及びメッセージフォーマットの一貫性を維持することを特徴とするシステム。
【請求項１８】
請求項１５に記載のシステムであって、前記複数のチャネルの各々の前記最大データフローは、前記幅調整モジュールにより、最大データフローアルゴリズムが前記複数のチャネルのデータトラフィックのグラフに適用されることによって判定されることを特徴とするシステム。
【請求項１９】
請求項１５に記載のシステムであって、前記幅調整モジュールは、線形計画法を適用して、少なくとも１つの特定のコスト関数を最小化しつつ前記少なくとも１つのパフォーマンス目標を満たす前記幅を決定することによって、前記複数のチャネルの各々の前記幅を決定することを特徴とするシステム。
【請求項２０】
請求項１９に記載のシステムであって、前記幅調整モジュールは、仮想チャネル及び物理チャネルパフォーマンス要求を満たす制約のリストを構築することによって線形計画法を適用し、かつ前記制約のリストに基づいて前記少なくとも１つのパフォーマンス目標の各々に対して少なくとも１つの目的関数を導き出すことを特徴とするシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
本明細書に記載の方法及び実施例は、インターコネクト（interconnect）アーキテクチャに関し、特に、ネットワークオンチップシステムのインターコネクトアーキテクチャに関する。
【背景技術】
【０００２】
チップ上のコンポーネントの数は、高集積度化、システムの複雑化及びトランジスタ寸法の小型化の故に急激に増加している。複雑なシステムオンチップ（ＳｏＣｓ：System-on-Chips）は、例えば、プロセッサコア、ＤＳＰ、ハードウェアアクセラレータ、メモリ及びＩ／Ｏのような様々なコンポーネントを含んでいてもよい。その一方で、チップマルチプロセッサ（ＣＭＰｓ：Chip Multi-Processors）は、多数の同種のプロセッサコア、メモリ及びＩ／Ｏサブシステムを有していてもよい。両方のシステムにおいて、チップ上のインターコネクトは、様々なコンポーネント間の高パフォーマンス通信をもたらすことにおいて重要な役割を果たす。従来のバス及びクロスバーベースのインターコネクトの寸法的な制限の故に、チップ上の多数のコンポーネントをインターコネクト（相互接続）する対応策としてネットワークオンチップ（ＮｏＣ）が登場している。
【０００３】
ＮｏＣは、ポイントトゥーポイント物理リンクを用いて互いにインターコネクトされた複数のルーティングノードからなる世界共通の通信インフラストラクチャーである。メッセージは送信元コンポーネント（source component）から入れられて、当該送信元コンポーネントから複数の中間ノード及び物理リンクを通って送信先に送信される。その後、送信先のコンポーネントは、当該メッセージを排出し、当該メッセージを送信先コンポーネントにもたらす。以下、用語「コンポーネント」、「ブロック」、「ホスト」または「コア」は、ＮｏＣを用いてインターコネクトされている様々なシステムコンポーネントに言及する際に、互いに置き換え可能に区別無く用いられる。用語「ルータ」及び「ノード」も、互いに置き換え可能に区別無く用いられる。一般化の喪失なしに、インターコネクトされている複数のコンポーネントを有するシステム自体は、「マルチコアシステム」と称される。
【０００４】
ルータが互いに接続してシステムネットワークを形成することが可能な、複数の実現可能なトポロジーがある。両方向リング（図１（ａ）に示すようなもの）及び２−Ｄメッシュ（図１（ｂ）に示すようなもの）は、関連技術におけるトポロジーの例である。
【０００５】
パケットは、様々なコンポーネント間の相互通信のメッセージ伝送単位である。ルーティングは、パケットが送信元から送信先に送信されるネットワークのルータ及び物理リンクのセットである経路の特定を含む。コンポーネントは、１または複数のルータの１または複数のポートに接続されており、これらのポートの各々は独自のＩＤを有している。パケットは、中間ルータによって用いられる送信先のルータ及びポートＩＤ情報を有しており、それによってパケットが送信先コンポーネントにルーティングされる。
【０００６】
ルーティング技術の例には、全てのパケットに対して同一の経路を選択することを伴う決定論的ルーティングを含む。このルーティング形式は、ネットワークの状態を意識しないものであり、潜在的なネットワークに存在するだろうパスダイバーシティ（pass diversities）に亘る負荷をバランシングしないものである。しかし、このような決定論的ルーティングは、ハードウェアに実装しやすく、パケットの順序が維持され、ネットワークレベルデッドロックを無くすのが簡単である。最短経路ルーティングは、遅延を最小化する。なぜならば、最短経路ルーティングは、送信元から送信先へのホップの数を減少させるからである。このため、最短経路は、２つのコンポーネントの間の通信に関して最も低パワーの経路でもある。次元オーダールーティング（Dimension-order routing）は、２Ｄメッシュネットワーク内の決定論的最短経路ルーティングの１つの形式である。
【０００７】
図２は、２次元メッシュ内のＸＹルーティングの一例を示している。さらに具体的には、図２は、ノード「３４」からノード「００」までのＸＹルーティングを示している。図２の例において、コンポーネントの各々は、１つのルータの１つのポートのみに接続されている。パケットは、最初に、当該パケットが送信先と同一のＸ次元（dimension）にあるノード「０４」に達するまでＸ次元にルーティングされる。次に、当該パケットは、パケットが送信先ノードに達するまでＹ次元にルーティングされる。
【０００８】
ソースルーティング及びテーブルを用いたルーティングは、ＮｏＣにおいて用いられる他のルーティング選択肢である。アダプティブルーティングは、ネットワークの状態に応じてネットワーク上の２つの点の間で取る経路を動的に変更する。このルーティングの形式は、分析及び実装しづらく、現場ではほとんど用いられていない。
【０００９】
ＮｏＣは、複数の物理的ネットワークを含んでいてもよい。物理ネットワークの各々に亘って複数の仮想ネットワークが存在してもよく、様々なタイプのメッセージが様々な仮想ネットワークを通じて伝送される。この場合、物理リンクまたはチャネルの各々において、複数の仮想チャネルが存在する。仮想チャネルの各々は、両終端において専用のバッファを有していてもよい。任意の所定のクロックサイクルにおいて、１つの仮想チャネルのみが物理チャネル上でデータを伝送可能である。
【００１０】
ＮｏＣインターコネクトは、しばしばワームホールルーティングを用いる。その場合、大きなメッセージまたはパケットは、フリット（flit）（フローコントロールディジット（flow control digits）とも称される）として知られる小さな欠片に分解される。最初のフリットはヘッダフリットであり、ペイロードデータと共にそのパケットのルートの情報及びキーメッセージレベルの情報を保持し、当該メッセージに付随している後続の全てのフリットのルーティング態様を定める。０以上のボディフリットは、ヘッドフリットに続いており、データの残りのペイロードを含んでいる。最後のフリットは、最後のペイロードを包含しているのに加えて、ブックキーピング（bookkeeping）の役割を果たし、当該メッセージについての接続を閉じる。ワームホールフローコントロールにおいて、仮想チャネルがしばしば実装されている。
【００１１】
物理チャネルは、仮想チャネル（ＶＣｓ）と称される独立した多数の論理チャネルに時分割化（time slice）される。ＶＣｓは、ルートパケットに複数の独立した経路をもたらすが、これらの経路は、物理チャネルにおいて時間多重化されている。仮想チャネルは、チャネルに亘ってパケットのフリットの取り扱いを調整するために必要な状態を保持する。少なくとも、この状態は、ルートのネクストホップに関する現在ノードの出力チャネル及び仮想チャネルの状態（アイドル、リソース待ち、またはアクティブ）を特定する。当該仮想チャネルは、パケットのうちの現在ノードにおいてバッファリングされているフリット及び次のノードにおいて利用できるフリットバッファの数へのポインターを含んでもよい。
【００１２】
「ワームホール」は、メッセージがチャネルを通って伝送される経路において役割を果たし、次のルータにおける出力ポートが短くてよく、全てのメッセージが到来する前に受信データがヘッドフリットに変換され得る。このことは、ヘッドフリットの到来においてルータが迅速にルートを定め、その後、やりとりからオプトアウト（opt out）することを可能にする。メッセージがフリット毎に伝送されるため、当該メッセージはその経路に沿って異なったルータにおいていくつかのフリットバッファを占有してもよく、これがワームのようなイメージをもたらす。
【００１３】
様々なエンドポイント、並びに様々なメッセージのために用いられる経路及び物理ネットワーク間のトラフィックに基づいて、ＮｏＣインターコネクトの様々な物理チャネルが様々なレベルの負荷状態下及び混雑状態下に置かれ得る。ＮｏＣインターコネクトの様々な物理チャネルの容量は、チャネルの幅（物理的な線の数）及び当該チャネルが動作するクロック周波数によって決定される。ＮｏＣの様々なチャネルは、異なったクロック周波数で動作してもよい。しかし、全てのチャネルは、幅、すなわち物理的線（physical wire）の数が同一である。この幅は、最も負荷がかかるチャネル及び様々なチャネルのクロック周波数に基づいて決定され得る。
【発明の概要】
【課題を解決するための手段】
【００１４】
本発明の実施例の態様は、複数のチャネルの各々の少なくとも１つのパフォーマンス目標または複数のチャネルの各々の最大データフローに基づいてネットワークオンチップ（ＮｏＣ）における複数のチャネルの各々の幅を決定及び／または調整し、複数のチャネルのうちの少なくとも１つに当該複数のチャネルの他の少なくとも１つと異なった幅を持たせることを含む方法を含んでもよい。
【００１５】
本発明の実施例の追加の態様は、複数のチャネルの各々の少なくとも１つのパフォーマンス目標または複数のチャネルの各々の最大データフローに基づいてネットワークオンチップ（ＮｏＣ）における複数のチャネルの各々の幅を決定及び／または調整し、複数のチャネルのうちの少なくとも１つに当該複数のチャネルの他の少なくとも１つと異なった幅を持たせることを含む処理を実行する命令を保存するコンピュータ可読記憶媒体を含んでいてもよい。
【００１６】
本発明の実施例の追加の態様は、システムをさらに含んでもよい。当該システムは、複数のチャネルの各々の少なくとも１つのパフォーマンス目標または複数のチャネルの各々の最大データフローに基づいてネットワークオンチップ（ＮｏＣ）における複数のチャネルの各々の幅を決定及び／または調整し、複数のチャネルのうちの少なくとも１つに当該複数のチャネルの他の少なくとも１つと異なった幅を持たせる幅調整モジュールを含む。
【図面の簡単な説明】
【００１７】
【図１】図１（ａ）及び図１（ｂ）は、双方向リング及び２ＤメッシュＮｏＣトポロジーの例を示す図である。
【図２】図２は、関連技術の双方向メッシュにおけるＸＹルーティングの一例を示す図である。
【図３】図３（ａ）及び図３（ｂ）は、実施例による、リンク幅に依って示されている非対称なチャネル幅／サイズを有するリング及び２ＤメッシュＮｏＣの一例を示す図である。
【図４】図４は、実施例に従った、非対称な入力及び出力チャネル幅を有するルータアーキテクチャの一例を示す図である。
【図５】図５は、実施例に従った、経路に沿ってチャネル幅の様々な組み合わせを有するソースノードから送信先ノードまでの通信シーケンスの一例を示す図である。
【図６】図６は、実施例に従った、チャネルの幅を決定するチャネルを通じた最大トラフィックを判定するように構成されたフローグラフの一例である。
【図７】図７は、実施例に従った、ヘテロジーニアス（heterogeneous）ＮｏＣにおけるチャネル幅を判定するためのフローチャートである。
【図８】図８は、実施例に従った、物理的及び仮想チャネルを有するＮｏＣの実施例を示す図である。
【図９】図９は、実施例に従った、本明細書に記載されている実施例が実装され得るコンピュータ／サーバのブロックダイアグラムである。
【発明を実施するための形態】
【００１８】
ＳｏＣ内の複雑なトラフィックプロファイルは、当該ＳｏＣの様々なコンポーネントを接続するインターコネクトの様々なチャネルにおける不均一な負荷を形成し得る。本明細書に記載されている実施例は、システム内の特定のブロック間通信パターンに対して異なった（不均一な）チャネル容量（線の数）を有する相互通信を構築するコンセプトに基づいている。ＮｏＣ相互通信の自動構築の例示の処理も開示されている。
【００１９】
ＮｏＣ相互通信の様々なチャネルにおける負荷は、様々なコンポーネントがメッセージを送信するレート、ＮｏＣ相互通信のトポロジー、どれだけ多様なコンポーネントがＮｏＣノードに接続されているか、及び様々なメッセージがＮｏＣ内に入ってくる経路に依存している。チャネルは、ＮｏＣ全体に亘って線の数において均一サイズにされ、ＮｏＣノード内のメッセージが様々なチャネルを介して伝送される際の再フォーマットが回避されてもよい。このような場合、輻輳を回避するため、全てのチャネルがＮｏＣ内の最も大きい負荷を受けるチャネルに基づいてサイズ決めされてもよい。チャネルのロードバランシングは、負荷が低い経路を介してメッセージをルーティングすることによって行われ得る。このロードバランシングは、様々なチャネルに不均一な負荷が掛かることを低減し、最大負荷を低減させる。しかし、異なった経路を選択することにおける制限された柔軟性が存在する。ルートパス（route path）は、最短経路の使用、最小ターンの使用、または様々なコンポーネント間の経路多様性の欠如等の様々な制約事項を有し得る。従って、ほとんどのＳｏＣにおいて、チャネルには不均一な負荷が残存し、最大のチャネル負荷を用いて全体のＮｏＣチャネルの幅を決定することが、面積の増大、電力の増大及びインターコネクトコストの増大をもたらす。
【００２０】
線の数において一様なチャネル幅を用いているＮｏＣインターコネクトである関連技術のシステムとは異なり、本明細書に開示されている実施例は、様々なチャネルが異なった数の線を有して、不均一なチャネル幅及び／または帯域幅容量をもたらし得るインターコネクトデザインを対象にしている。要求されるチャネル帯域幅は、トラフィックプロファイルに基づいてチャネルにおいて予想される最大データ帯域幅を計算することによって決定され得る。いくつかのチャネルが、それらの帯域幅要求に基づいて異なった幅を有している場合、ＮｏＣ内の様々なノードは、メッセージが異なった幅の２つのチャネルの間を行き来する際に当該メッセージを再フォーマットしなければならないことがあり得る。単一のメッセージフリットは、複数のさらに小さいフリットに分割される必要があり得、また複数のメッセージフリットが統合されてさらに大きなメッセージフリットが形成される必要があり得る。例えば、１２８ビットの入力チャネルから到来した単一の１２８ビットフリットは、１２８ビットチャネルから６４ビットチャネルに向かう際に６４ビットの２つのフリットに分割される必要があり得る。
【００２１】
このような不均一チャネルのＮｏＣインターコネクトの一例が、図３（ａ）及び図３（ｂ）に示されている。図３（ａ）は、実施例に従った、均一なチャネル幅を有する６ノードリングインターコネクトを示している。４つのプロセッサコンポーネントＰｒｏｃ１、ｐｒｏｃ２、ｐｒｏｃ３及びｐｒｏｃ４は、２つのメモリコンポーネントｍｅｍ１及びｍｅｍ２に接続されている。このインターコネクトにおけるチャネルは、６４ビット（１単位）及び１２８ビット（２単位）の２つの幅を有している。コンポーネントＡ、Ｂ、Ｃ及びＦとＮｏＣを接続しているルータは、図示するように異なった幅の様々な入力及び出力チャネルを有しており、これらのルータは、メッセージが異なった幅のチャネルに亘って伝送される際に当該メッセージを再フォーマットする必要があり得る。図３（ｂ）には、実施例に従った、３×３のトポロジーで構成された９ノードメッシュインターコネクトが示されている。この例において、６つのプロセッサｐｒｏｃ１、・・・、ｐｒｏｃ６は、３つのメモリコンポーネントｍｅｍ１、・・・、ｍｅｍ３に接続されており、コンポーネントＡ、Ｂ、Ｃ、Ｄ、Ｅ及びＦに接続されているルータは、不均一な幅のチャネルを有している。
【００２２】
図４は、本実施例に従って、異なった幅の様々な入力及び出力チャネルを有する５ポートルータのアーキテクチャを示している。図４の例において、チャネル幅及び対応するバッファ幅は６４ビット（１単位）から２５６ビット（４単位）まで変化するリンクの幅によって示されている。フリットの再フォーマットは、入力チャネル幅及び出力チャネル幅に基づいて実行される。例えば、１２８ビット（２単位）フリットが１２８ビットチャネルを通って到達し、１２８ビットバッファに書き込まれる場合、図に示されているように、フリットは６４ビット、１２８ビットまたは２５６ビット出力チャネルに伝送され得る。それに応じて、ルータノードは、入力チャネル及び出力チャネルの幅に基づいて、大きなフリットを複数の小さなフリットに分割することによって、または単一のメッセージの複数のフリットを単一の大きなフリットに結合することによってメッセージを再フォーマットする。図４の例において、再フォーマットは、単一のメッセージ内で行われ、複数のメッセージに亘っては行われていない。しかし、同一の送信元から到来しかつ同一の送信先に送出される複数のメッセージの再フォーマットが行われてもよい。メッセージの到来パターンによって、このような機会は大きなネットワークにおいて希なものとなり得る。
【００２３】
均一なチャネル幅を有するＮｏＣにおいて、ＮｏＣノード内で発生するメッセージの再フォーマットは、終端コンポーネントからするとトランスペアレント（透過的）に維持される。従って、送信先ホストが１２８ビットメッセージを期待している場合、ＮｏＣは、ルートに沿ってなされるいくつかのセグメンテーション（分割）及び再構築操作の後に、メッセージが１２８ビットフリットとして最終の送信先に送達されるように維持される。従って、チャネルは、終端のホストから見た全ての終端間のチャネル幅が元々の均一なインターコネクトと一致するようにサイズ決めされる。例えば、一組の１２８ビットの送信及び受信ホストの間において、当該インターコネクトはルート上においてチャネルを６４ビット以下に減少させ得、最終送信先ホストにおけるルータの出口送信チャネルにおいて１２８ビットに戻し得る。
【００２４】
図５に、実施例に従って、このような一貫したチャネル幅の変換のいくつかの例が示されている。経路５００は、送信元コンポーネントと送信先コンポーネントとの間で均一な１２８ビット（２単位）チャネル幅を有する経路を示している。経路５０１は、ホスト間の経路を示しており、この経路において、チャネル幅は終端ホストにおいて同一に維持されている。しかし、当該経路に沿って、チャネル幅は最初に送信元における２単位から４単位に増大し、次に８単位にされ、その後に４単位に戻されて、さらに送信先において２単位にされる。経路５０２において、当該経路に沿ったチャネル幅は、送信元における２単位から８単位に増大し、次に１単位に減少させられ、その後に４単位に増大させられ、さらに送信先において２単位に戻される。チャネル幅がＮｏＣ内において均一にされ、すべての通信ホストのペアの間の終端間のチャネル幅の一貫性が必要とされてもよい。
【００２５】
終端間チャネル幅の一貫性は、送信元及び送信先ホストが、異なった送信及び受信チャネル幅を有している場合であっても維持される。例えば、６４ビットの送信チャネルを有するホストが１２８ビットの受信チャネルを有するホストにメッセージを送信する場合、当該メッセージは送信において、当該メッセージがルート上でアップコンバート及びダウンコンバートされる場合でも、１２８ビットのフリットとして形成される。
【００２６】
ＮｏＣにおける様々なチャネルの幅は、チャネルを介して行き来する全てのメッセージの帯域幅要求によってのみではなく遅延要求によって決定されてもよい。チャネルをより広くして、より大きなチャネル帯域幅を割り当てることは、チャネルが既に必要とされる平均的データレートよりも広い場合には、必ずしもスループットを増大させない。しかし、チャネルをより広くすることは、不均一なトラフィック分布の下で存在する遅延を減少させ得る。それによって、最小のチャネル幅は、チャネルに亘る全てのフローのデータスループットと少なくとも同一として決定され得る。
【００２７】
チャネルの最小幅を決定するために、全ての送信元及び送信先のペアが列挙され、これらのペアのメッセージはチャネルを介して送信される。ユーザは、これら全てのメッセージのデータレートを提供して、システムが全てのメッセージのデータレートを足し合わせることによってチャネルをサイズ決めすることを可能としてもよい。メッセージのデータレートが提供されない場合でかつ全てのコンポーネントのデータ送信及び受信レートが既知の場合、代替の実施例が用いられて、複雑なトラフィックプロファイルを有する複雑なシステムにおける最小チャネル幅（または最大持続データレート）が決定される。
【００２８】
例えば、４つのプロセッサ及び２つのメモリ、並びに任意のプロセッサが任意のメモリとやりとり可能な共有メモリコンピュータ環境を仮定する。また、プロセッサのピーク送信レートが６４ビット／秒でありメモリのピーク受信レートが６４ビット／秒であると仮定する。このような環境において、プロセッサはデータの一部を一方のメモリに送信して、残りを他方のメモリに送信し得るか、または専ら１つのメモリとのみ通信し得る。通信パターンに依存して、プロセッサは６４ビット／秒で送信を行い得る。
【００２９】
従って、４つのプロセッサを用いた、２５６ビット／秒のピークチャネルスループットを有するＮｏＣがデザインされ得る。しかし、この例において、通信の合計レートは、２つのメモリの合計受信容量である１２８ビット／秒を超えることはない。様々なチャネルにおける負荷は、インターコネクトトポロジー、経路、及び様々なコンポーネントの接続位置にも依存する。
【００３０】
４つのプロセッサ及び２つのメモリが、図３（ａ）に示すように双方向リングを用いて接続されていると仮定する。利用可能な２つの経路の間で、最短経路が毎回選択され、時計回りのルートを選択することによって均衡は破壊されると仮定する。この例において、どのプロセッサがどの部分のどのメモリの組み合わせとやりとりするかに関わらず、コンポーネントＣ及びＤ、Ｄ及びＥ、Ｅ及びＦに接続されているルータ間のチャネルにおけるピーク負荷は、６４ビット／秒（１単位）を超えないだろう。さらに、コンポーネントＦ及びＡ、Ａ及びＢ、Ｂ及びＣが１２８ビット／秒（２単位）の負荷を受けるコミュニケーションパターンが存在するだろう。
【００３１】
さらに複雑なシステム及び通信パターンにおいて、最小の必要チャネル幅が計算され得る故に、様々なチャネルにおけるピークデータレートを決定することは困難になり得る。以下に記載するのは、実施例に従った、ＮｏＣインターコネクトの任意の所定のチャネルにおけるピークデータレートを決定するために使用され得る処理である。
【００３２】
チャネルを介してメッセージを送信するコンポーネントの全てのペアは、左側にある全ての送信元コンポーネント及び右側にある送信先コンポーネントに関する有向フロー（directed flow）または２部グラフ（bipartite graph）を構築するために用いられる。そして、送信元及び送信先コンポーネントは、方向性のある端部（directional edge）に接続されている。端部の容量は最大レートであり、送信元コンポーネントはこのルートに沿って送信先コンポーネントに当該最大レートでデータを送信することが可能である。この容量は、送信元のピーク送信レート及び送信先のピーク受信レートを超え得ない。続いて、２つのさらなるコンポーネントがグラフに追加される。１つはＳとしてグラフの左端に追加され、１つはＤとしてグラフの右端に追加される。そして、左端のコンポーネントは、左側において、方向性のある端部（directed edge）によって、送信元コンポーネント毎に、一連の送信元コンポーネントに接続される。これらの端部の容量は、送信元コンポーネントのピーク送信レートである。右側の一連の送信先コンポーネントは、方向性のある端部によって最右端に、送信先コンポーネント毎に接続される。図６は、いくつかのチャネルに関するグラフを示しており、図示するように、中間端によってチャネルを介して５つの送信元が４つの送信先にメッセージを送信すると仮定している。
【００３３】
このような所定のチャネルに関する有向フロー図が構築されると、図７のフロー図が用いられて、チャネルの各々の幅が決定される。ステップ７００において、ＮｏＣのチャネルがキューとして配される。ステップ７０１において、チェックが行われて、キューが空かが確認される。キューが空の場合には、その後処理が終了する。キューが空でない場合、処理はステップ７０２に進み、キューの先頭のチャネルが取り除かれる。７０３において、当該選択されたチャネルに基づいて、最大フローが、２部グラフのコンポーネントＳからコンポーネントＤまで計算される。関連技術のグラフアルゴリズムは、有向フローグラフ内の最大フローを計算するために用いられてもよい。当該チャネルに掛かる最大データ負荷は、当該最大フローを超えないであろう。当該チャネルは、その後、適切にサイズ決めされて、当該チャネルがトラフィック分布に関わらず十分なバンド幅を有することが保証される。当該チャネル幅は、具体的なパフォーマンス目標に基づいて、遅延を減少させるべくさらに増加させられてもよいし、当該チャネル幅は減少させられて、例えばコストが抑えられてもよい。この処理は、その後、ＮｏＣ内の全てのチャネルに対して繰り返される。
【００３４】
仮想チャネル及び物理チャネルの両方を含むインターコネクトにおいて、様々な仮想チャネルが様々にサイズ決めされる。その一方で、物理チャネル幅は最も広い仮想チャネルの幅と同一であろう。システムの実施例は図８に示されている。図８の例において、入力における複数の仮想チャネルが、ルータ調停論理回路（arbitration logic）を用いて出力物理チャネルを取り合う。最大フローグラフ解析に基づいて、様々な仮想チャネルの最大バンド幅要求が取得され得る。しかし、仮想チャネルの全ての時間が物理チャネルを分け合う場合（例えば、任意の単一の仮想チャネルが一部分の時間のみにおいてデータの送信を行うシステムの場合）、仮想チャネルはこの値でサイズ決めされなくともよい。
【００３５】
例えば、１の物理チャネル上に２つの仮想チャネルがあり、仮想チャネルの各々が最小で６４ビット／サイクルのバンド幅を必要とする場合、仮想チャネルは各々６４ビットにサイズ決めされ得ない。もし仮想チャネルがこのようにサイズ決めされた場合、当該仮想チャネルが物理チャネルを同等に共有すると仮定すると、当該仮想チャネルの各々は、３２ビット／サイクルのバンド幅のみを受けるだろう。仮想チャネルの両方が少なくとも６４ビット／サイクルのデータバンド幅を持つことを保証するために、これらは各々１２８ビットにサイズ決めされることが必要である（仮想チャネルが物理チャネルを同等に共有すると仮定する）。
【００３６】
１の物理チャネルを共有する仮想チャネルが多数存在し、仮想チャネルの各々が異なる最小バンド幅要求を有している場合、仮想チャネルの全てがそれらのバンド幅要求を満たすように仮想チャネルをサイズ決めすることは簡単ではない。実施例において、この問題は、標準形の線形最適化（standard linear optimization）または線形計画問題（linear programming problem）にマッピングされる。そして、我々は、標準形の線形計画解法（standard linear programming solution）を用いて、このような状況における仮想チャネル幅を導き出すことが可能である。
【００３７】
例えば、ｎ個の仮想チャネル（ＶＣ1、ＶＣ2、．．．、ＶＣn）が１の物理チャネルを共有し、当該仮想チャネルの最小バンド幅要求が（Ｂ1、Ｂ2、．．．、Ｂn）であるとする。従って、物理チャネルにおける合計のバンド幅要求はΣＢi（ｉ＝１からｎ）となる。ｓiがＶＣiを示すとする。ｉ＝１からｎである場合にｓｉ＞Ｂiであるのは明確である。物理チャネルの幅は最大である（ｉ＝１からｎ、ｓiの場合）。ＶＣiが調停（arbitration）において時間の一部ｆiを得たと仮定すると、ＶＣiによって受けたバンド幅はｆi×ｓiとなり、これは≧Ｂｉとなるべきであり、必要とされるバンド幅である。全てのＶＣが物理チャネルΣｆi≦１を共有する故に、以下の線形拘束のセットが常に満足されるべきである。
ｓｉ≧Ｂi          ｉ＝１からｎの場合
ｆi×ｓi≧Ｂi      ｉ＝１からｎの場合
０≦ｆi≦１        ｉ＝１からｎの場合
Σｆi≦１          ｉ＝１からｎの場合
仮想チャネル幅ｓiを有するチャネルのバッファコストはΣＳiである。デザインの目標がバッファコストの最小化である場合、目的関数は、Σｓiを最小化するものである。デザインの目標が線数の最小化である場合、目的関数の最大値（ｉ＝１からｎ、ｓiの場合）が最小化され得、これは物理チャネル幅である。目標が様々である場合、代替的な目的関数が構築されてもよい。この場合、標準形の線形計画アルゴリズムが用いられて問題が解決され、ｓiの値、及び制約条件を満たしかつ目的関数を最小化／最大化する様々な仮想チャネルの幅が取得可能である。
【００３８】
従って、実施例は、制約の不均衡を列挙して最適化の目標に応じて目的関数を構築することによって、仮想チャネル及び物理チャネルのサイズ決め問題を、標準形の線形計画最適化法にマッピングすることを含む。
【００３９】
図９は、実施例が実装され得る例示のコンピュータシステム９００を示している。コンピュータシステム９００は、サーバ９０５を含み、サーバ９０５は、Ｉ／Ｏユニット９３５、記憶装置９６０、及び当業者に知られているように１又は複数のユニットを実行するプロセッサ９１０を含んでいてもよい。本明細書で用いられる用語「コンピュータ可読媒体」は、実行のためにプロセッサ９１０に命令を提供することに関与する任意の媒体を言う。当該任意の媒体は、コンピュータ可読記憶媒体の態様で提供されてもよい。コンピュータ可読記憶媒体は、例えば、光ディスク、磁気ディスク、リードオンリーメモリ、ランダムアクセスメモリ、ソリッドステートデバイス及びドライブ、もしくは電子情報を保存するのに適した任意の他のタイプの有形の媒体、または搬送波等の一時的な媒体を含み得るコンピュータ可読信号媒体であるが、これらに限定されるものではない。Ｉ／Ｏユニットは、キーボード、マウス、タッチデバイスまたは口頭命令（verbal command）デバイス等の入力デバイスを使用し得るユーザインタフェース９４０及びオペレータインタフェース９４５からの入力を処理する。
【００４０】
サーバ９０５は、外部記憶装置９５０に接続されていてもよい。外部記憶媒体９５０は、携帯用ハードトライブ、光学媒体（ＣＤまたはＤＶＤ）、ディスク媒体またはコンピュータが実行可能コードを読み出すことが可能な任意の他の媒体を含み得る。サーバは、出力デバイス９５５に接続されていてもよい。出力デバイスは、ユーザにデータ及び他の情報を出力し、ユーザからの追加の情報を要求するディスプレイ等である。サーバ９０５とユーザインタフェース９４０、オペレータインタフェース９４５、外部記憶装置９５０及び出力デバイス９５５との接続は、８０２．１１規格、ブルートゥース（Bluetooth）（登録商標）もしくはセルラープロトコル（cellular protocol）等のワイヤレスプロトコルを介して、またはケーブルもしくは光ファイバー等の物理伝送媒体を介してなされてもよい。出力デバイス９５５は、ユーザと相互に情報をやりとりするために、さらに入力デバイスとしての役割を果たしてもよい。
【００４１】
プロセッサ９１０は、１または複数のモジュールを実行してもよい。幅調整モジュール９１１は、ネットワークオンチップ（ＮｏＣ）内の複数のチャネルの各々の幅を決定及び／または調整する。この決定及び／または調整は、複数のチャネルの各々に関する少なくとも１つのパフォーマンス目標または複数のチャネルの各々の最大フローに基づいて行われ、複数のチャネルのうちの少なくとも１つが当該複数のチャネルのうちの他の少なくとも１つと異なった幅を有するように行われる。幅調整モジュール９１１は、複数のチャネルのデータトラフィックのグラフに最大フローアルゴリズムを適用することによって、当該複数のチャネルの各々の最大フローを判定するように構成されていてもよい。幅調整モジュール９１１は、さらに、線形計画法を適用することによって複数のチャネルの各々の幅を決定し、少なくとも１つの特定のコスト関数を最小化しつつ少なくとも１つのパフォーマンス関数を満たす幅を決定し、かつ仮想チャネル及び物理チャネルパフォーマンス要求に関する制約のリストを構築することによって線形計画法を適用するように構成されていてもよい。幅調整モジュールは、制約のリストに基づいて少なくとも１つのパフォーマンス目標の各々に関する少なくとも１つの目的関数を決定するように構成されていてもよい。
【００４２】
メッセージ再フォーマッタモジュール９１２は、異なった幅を有する複数のチャネルのうちの接続されているものの間においてメッセージ再フォーマッタを形成するように構成されていてもよく、かつ異なった幅を有する複数のチャネルのうちの接続されているものの間においてメッセージのフリットを調整するように構成されていてもよい。メッセージ再フォーマッタモジュール９１２は、ＮｏＣの全ての送信元及び送信先端ホストのペアが端末間でのメッセージサイズ及びメッセージフォーマットの一貫性を維持するようにメッセージ再フォーマッタを形成するように構成されていてもよい。
【００４３】
発明を実施するための形態のいくつかの部分は、コンピュータ内の動作のアルゴリズム及び記号表現に関して説明されている。これらのアルゴリズム的な説明及び記号表現は、データ処理技術の当業者の新しい考えの本質を最も効果的に他の当業者に伝達するために、当業者によって用いられる手段である。アルゴリズムは、所望の最終状態または結果をもたらす一連の定義済みのステップである。実施例において、実行されるステップは、具体的な結果を達成するために具体的な量の物理的操作を要求する。
【００４４】
さらに、実施例の他の実装例は、発明を実施するための形態を考慮することによって、及び本明細書に開示されている実施例を実線することによって、当業者には明らかである。上述の実施例の様々な態様及び／またはコンポーネントは、単一でまたは任意の組み合わせで使用されてもよい。発明を実施するための形態及び実施例は、例示として考慮され、実施例の真の範囲及び趣旨は添付の特許請求の範囲によって示されることが意図されている。
【図１（ａ）】
2016503594.tif 000003
【図１（ｂ）】
2016503594.tif 000004
【図２】
2016503594.tif 000005
【図３（ａ）】
2016503594.tif 000006
【図３（ｂ）】
2016503594.tif 000007
【図４】
2016503594.tif 000008
【図５】
2016503594.tif 000009
【図６】
2016503594.tif 000010
【図７】
2016503594.tif 000011
【図８】
2016503594.tif 000012
【図９】
2016503594.tif 000013
【国際調査報告】
2016503594.tif 000014
2016503594.tif 000015