(57)【特許請求の範囲】
【請求項１】
設定変更可能なネットワークオンチップ（ＮｏＣ）であって、
仕様に基づいて前記ネットワークオンチップのハードウェア要素群から構成された、前記仕様に基づく数の１つ又は複数のシステムエージェントインタフェースと、
システムエージェント群の前記仕様に基づいて前記ネットワークオンチップの前記ハードウェア要素群から構成された、前記仕様に基づく他の数の１つ又は複数のキャッシュコヒーレンシーコントローラと、
を具備する、ネットワークオンチップ。
【請求項２】
請求項１記載のネットワークオンチップにおいて、
前記システムエージェント群のキャッシュコヒーレンスを管理するように構成されたディレクトリをさらに具備し、
前記１つ又は複数のキャッシュコヒーレンシーコントローラは、それぞれ、前記ディレクトリの一部分と関連付けられている、
ネットワークオンチップ。
【請求項３】
請求項２記載のネットワークオンチップにおいて、
前記ディレクトリは、複数のアドレスを具備し、
各アドレスは、各システムエージェントがプライベートキャッシュを有している前記システムエージェント群の１つ又は複数のキャッシュにおけるアドレスと関連付けられており、
前記ディレクトリは、前記システムエージェントの各プライベートキャッシュにおける前記アドレスの有効性を示す、複数のビットベクトルをさらに具備する、
ネットワークオンチップ。
【請求項４】
請求項３記載のネットワークオンチップにおいて、
カッコウハッシュによって前記ディレクトリを管理するように構成された、ハッシュテーブルをさらに具備する、
ネットワークオンチップ。
【請求項５】
請求項１記載のネットワークオンチップにおいて、
前記１つ又は複数のシステムエージェントインタフェースは、複数のプロトコルをサポートするように構成されており、
各システムエージェントインタフェースは、前記仕様に基づいて、前記複数のプロトコルのうちの少なくとも１つをサポートするように構成されている、
ネットワークオンチップ。
【請求項６】
請求項１記載のネットワークオンチップにおいて、
前記１つ又は複数のキャッシュコヒーレンシーコントローラは、フレキシブルプロトコルを利用するように構成されており、
各キャッシュコヒーレンシーコントローラは、前記フレキシブルプロトコルのサブセット群を利用するように構成され、各システムエージェントインタフェースと関連付けられた少なくとも１つのプロトコルに対する伝達を容易にする、
ネットワークオンチップ。
【請求項７】
請求項１記載のネットワークオンチップにおいて、
前記１つ又は複数のシステムエージェントインタフェースは、異なる複数のバス幅をサポートするように構成されており、
前記１つ又は複数のシステムエージェントインタフェースの各バスのバス幅は、前記仕様に基づいて設定されている、
ネットワークオンチップ。
【請求項８】
設定変更可能なネットワークオンチップ（ＮｏＣ）のための方法において、
仕様に基づいて、１つ又は複数のＮｏＣエージェントインタフェースを構成し、
ＮｏＣエージェント群の前記仕様に基づいて、１つ又は複数のキャッシュコヒーレンシーコントローラを構成し、
前記１つ又は複数のＮｏＣエージェントインタフェースを構成することは、前記仕様に基づく数の、前記ネットワークオンチップのハードウェア要素群を、前記１つ又は複数のＮｏＣエージェントインタフェースに構成することを含み、
前記１つ又は複数のキャッシュコヒーレンシーコントローラを構成することは、前記仕様に基づく他の数の、前記ネットワークオンチップのハードウェア要素群を、前記１つ又は複数のキャッシュコヒーレンシーコントローラに構成することを含む、
方法。
【請求項９】
請求項８記載の方法において、
ディレクトリを用いて、前記ＮｏＣエージェント群のキャッシュコヒーレンスを管理し、
前記１つ又は複数のキャッシュコヒーレンシーコントローラは、それぞれ、前記ディレクトリの一部分と関連付けられている、
方法。
【請求項１０】
請求項９記載の方法において、
前記ディレクトリは、複数のアドレスを具備し、
各アドレスは、各ＮｏＣエージェントがキャッシュを有している前記ＮｏＣエージェント群の１つ又は複数のキャッシュにおけるエントリに対応しており、
前記ディレクトリは、前記１つ又は複数のキャッシュのそれぞれにおけるキャッシュの有効性を示す、複数のビットベクトルをさらに具備する、
方法。
【請求項１１】
請求項１０記載の方法において、
ハッシュテーブルを用いたカッコウハッシュによって前記ディレクトリを管理する、
方法。
【請求項１２】
請求項８記載の方法において、
前記１つ又は複数のＮｏＣエージェントインタフェースを、複数のプロトコルをサポートするように構成し、
各ＮｏＣエージェントインタフェースを、前記仕様に基づいて、前記複数のプロトコルのうちの少なくとも１つをサポートするように構成する、
方法。
【請求項１３】
請求項８記載の方法において、
前記１つ又は複数のキャッシュコヒーレンシーコントローラを、フレキシブルプロトコルを利用するように構成し、
各キャッシュコヒーレンシーコントローラを、前記フレキシブルプロトコルのサブセット群を利用するように構成して、各ＮｏＣエージェントインタフェースと関連付けられた少なくとも１つのプロトコルに対する伝達を容易にする、
方法。
【請求項１４】
請求項８記載の方法において、
前記１つ又は複数のＮｏＣエージェントインタフェースを、異なる複数のバス幅をサポートするように構成し、
前記１つ又は複数のＮｏＣエージェントインタフェースの各バスのバス幅は、前記仕様に基づいて設定されている、
方法。
【発明の詳細な説明】
【技術分野】
【０００１】
概してキャッシュコヒーレント相互接続を対象とした、より具体的には、キャッシュコヒーレントネットワークオンチップ（NoC）の生成を対象とした、方法及び実施例に関する。
【背景技術】
【０００２】
統合のレベル、システムの複雑化のレベル、及びトランジスタ配置の縮小化のレベルが増しているため、チップ上の構成要素の数が急速に増大している。複雑なシステムオンチップ（SoCs ：System-on-Chips）は、種々の構成要素（例えば、プロセッサコア群、ＤＳＰ群、ハードウェアアクセレータ群、メモリ、入出力（I/O））を含んでいる可能性がある。また、チップマルチプルプロセッサ（CMPs ：Chip Multi-Processors）は、多数の同質なプロセッサコア群、メモリ、及び入出力サブシステム（I/O subsystems）を含んでいる可能性がある。ＳｏＣシステム及びCMPシステムの双方において、オンチップ相互接続は、種々の構成要素間におけるハイパフォーマンスなコミュニケーションを提供する役割を担っている。従来のバスの拡張性制限及びクロスバーに基づく相互接続の拡張性制限のため、ネットワークオンチップ（NoC：Network-on-Chip）が、チップ上の多数の構成要素を相互接続するためのパラダイム（枠組み）として浮かび上がっている。ネットワークオンチップは、ポイント間の（ポイントツーポイントの）物理リンク群を用いて互いに相互接続された複数のルーティングノードによって作られた、グローバルにシェアされた通信インフラである。
【０００３】
メッセージは送信元によって投入され、中間ノード群及び物理リンク群を亘って、その送信元ノードから送信先（目的地）に向けて転送される。そして、その送信先ノードは、そのメッセージを取り出して目的地へ提供する。以下では、「構成要素（components）」、「ブロック（blocks）」、「ホスト（hosts）」、又は「コア（cores）」は、ＮｏＣを用いて相互接続された種々のシステム構成要素に言及するために、ほとんど同じ意味で用いられる。また、「ルータ（routers）」及び「ノード（nodes）」もほとんど同じ意味で用いられる。マルチプルに相互接続された構成要素を持ったそのシステムは、それ自体、「マルチプルコアシステム」として言及されるが、これに限定されるものではなく一般性を失うものではない。
【０００４】
複数のルータがシステムネットワークを作るために互いに接続可能なトポロジがいくつかある。関連技術におけるトポロジの例としては、図１Ａに示されるような双方向リング（Bi-directional rings）、図１Ｂに示されるような2-D（２次元）メッシュ、及び、図１Ｃに示されるようなトーラス（Torus）である。メッシュ及びトーラスは、2.5-D（２．５次元）組織又は3-D（３．５次元）組織にも拡張することができる。図１Ｄは、3DメッシュＮｏＣを示しており、ここでは、３×３の2-Dメッシュが３層互いに重なっている。そのＮｏＣのルータは、２つまで追加的なポートを有しており、そのうちの１つは上側のレイヤのルータと繋がっており、もう１つは下側のレイヤのルータと繋がっている。その例において真ん中のレイヤのルータ１１１では両ポートが用いられており、１つがそのトップレイヤのルータと繋がっており、もう１つがそのボトムレイヤのルータと繋がっている。ルータ１１０及びルータ１１２は、それぞれ、そのボトムメッシュレイヤ及びトップメッシュレイヤに在るので、上側に向いたポート１１３及び下側に向いたポート１１４がそれぞれ繋がった状態になっている。
【０００５】
パケットは、メッセージを搬送する単位であり、種々の構成要素間における相互通信に用いられる。ルーティングは、経路（path）を特定することを含む。この経路（path）は、パケットが送信元から送信先へ送信される、ネットワークのルータ群及び物理リンク群のセットから構成される。構成要素は、１つ又は複数のルータの１つ又は複数のポートと繋がっており、各ポートはユニークな識別子（ID）を有している。パケットは、中間のルータがそのパケットを送信先構成要素まで転送するために用いられる、送信先ルータのＩＤ及びポートのＩＤを含んでいる。
【０００６】
例えば、ルーティング技術には、確定的ルーティング（deterministic routing）が含まれ、この確定的ルーティングは、すべてのパケットに対して、ＡからＢまでの同じ経路を選択する。このルーティングの形態は、ネットワークの状態とは関係なく、下層のネットワークに存在する可能性のあるパスダイバーシティによる、負荷均衡を図らない。しかしながら、そのような確定的ルーティングは、ハードウェアで実行されてもよく、パケットの順序を維持して、ネットワークレベルのデッドロックを回避してもよい。最短パスのルーティングは、送信元から送信先までのホップ数を低減できるので、待ち時間（latency：レイテンシ）を最小化することができる。このため、その最短パスは、また、２つの構成要素間における通信のための、最も電力のかからない経路である可能性がある。次元順ルーティング（Dimension-order routing）は、2-Dメッシュネットワーク、2.5-Dメッシュネットワーク、及び3-Dメッシュネットワークにおける確定的最短パスルーティングの一形態である。このルーティングスキームにおいては、メッセージが最終目的地に届くまで特定の手順によって各座標に沿ってルーティングされる。例えば、3-Dメッシュネットワークでは、最初に、メッセージは、送信先ルータのＸ座標と同じＸ座標を持つルータに到達するまで、Ｘ座標に沿って転送される。次に、メッセージは、向きを変えてＹ座標にそって転送され、最後に、向きを変えて、Ｚ座標に沿って最終的な送信先ルータに到達するまで移動する。次元順ルーティングは、方向転換を最小とし且つ経路を最短とするルーティングである可能性がある。
【０００７】
図２Ａは、２次元メッシュにおけるＸＹルーティングの一例を図示している。より具体的には、図２Ａは、ノード３４からノード００までのＸＹルーティングを図示している。図２Ａに示した例では、各構成要素は、１つのルータの１つのポートにだけ繋がっている。パケットは、まず、ノード０４に到達するまでｘ軸に沿って転送される。ここで、ノード０４のｘ座標は、送信先ノードであるノード００のｘ座標と同じである。次に、そのパケットは、送信先ノードであるノード００に到達するまで、ｙ軸に沿って転送される。
【０００８】
１つ又は複数のルータ又は１つ又は複数のリンクが欠落している、他のメッシュトポロジでは、特定の送信元ノードと送信先ノードとの間では次元順ルーティングを実行できない可能性があり、代わりの経路を選択する必要がある可能性がある。その代替パスは、最短ではないもしれないし、又は、方向転換を最小にしないかもしれない。
【０００９】
ソースルーティング（Source routing）及びテーブルを用いたルーティングは、ＮｏＣにおける、ルーティングに関する他のオプションである。適応的ルーティング（Adaptive routing）は、ネットワークの状態に基づいて、ネットワーク上の２点間の経路をダイナミックに変更することができる。ルーティングのこの形態は、分析や実装が複雑である。
【００１０】
ＮｏＣ相互接続は、複数の物理的なネットワークを含んでいてもよい。各物理的ネットワークの全体に亘って、複数の仮想的ネットワークが存在していてもよい。ここで、異なるメッセージ種別は、異なる仮想的ネットワークを介して送信される。この場合、各物理リンク又は物理的チャネルには、複数の仮想的チャネルが存在する。各仮想的チャネルは、両終点においてバッファを有していてもよい。任意のクロックサイクルにおいて、１つの仮想的チャネルだけがその物理的チャネルにおいてデータを送信することができる。
【００１１】
ＮｏＣ相互接続は、ワームホールルーティング（wormhole routing）を採用することができる。ここで、大きなメッセージ又はパケットは、フリット（フロー制御単位（flow control digits）とも呼ばれる）として知られる小さなピースに分割される。１番目のフリットは、ヘッダフリットである。このヘッダフリットは、このパケットのルートについての情報及びキーメッセージレベルの情報を保持しており、ペイロードデータが付加されている。また、このヘッダフリットは、このメッセージに関連付けられ且つ後に続くすべてのフリットのルーティング挙動をセットアップする。任意に、１つ又は複数のボディフリットがヘッダフリットに続いてもよく、この１つ又は複数のフリットは残りのデータペイロードを含んでいる。最後のフリットは、テールフリットであり、このテールフリットは、最後のペイロードを含むと共に、ブックキーピングとして機能してそのメッセージのためのコネクションを閉じる。ワームホールフロー制御では、仮想的チャネルがしばしば実装される。
【００１２】
物理的チャネル群は、仮想的チャネル群（VCs：virtual channels）と呼ばれる独立した論理的チャネル群にスライスされた、時間である。仮想的チャネル群は、複数の独立パスを提供してパケットを搬送する。仮想的チャネル群は、物理的チャネル上で時間分割多重されている。仮想的チャネルは、ステート（state）を保持している。このステートは、１つのチャネルにおいて１つのパケットのフリット群をハンドリングするために必要とされる。少なくとも、このステートは、ルート上の次のホップに向けた、現在のノードの出力チャネル、及び、その仮想的チャネルの状態（例えば、アイドル状態、リソースの待ち状態、又はアクティブ状態）を特定する。また、その仮想的チャネルは、現在のノードにおいてバッファされているフリット群に対するポインタ群、及び、次のノードにおいて利用可能なフリットバッファの数を含んでいてもよい。
【００１３】
「ワームホール」という表現は、複数のチャネルに亘る複数のメッセージが送信される、道を意味する。次のルータの出力ポートが短くて、ヘッダフリットにおける受信データが、メッセージ全体の到着前に、翻訳され得る。これにより、ルータは、ヘッダフリットが到着すると即座にルートをセットアップすることができ、残りの会話を回避することができる。メッセージはフリット毎に送信されるので、メッセージは異なる複数のルータにおいて経路に沿ったフリットバッファ群を占有する可能性があり、これが蠕虫のようなイメージを作っている。
【００１４】
種々の終点間のトラヒック、並びに、種々のメッセージのために用いられる、ルータ及び物理的ネットワークに基づいて、ＮｏＣ相互接続の異なる物理的チャネル群は、異なるレベルの負荷及び輻輳を経験する可能性がある。ＮｏＣ相互接続における種々の物理的チャネル群の容量は、チャネル幅（物理的なワイヤの数）、及び、動作に用いられるクロック周波数によって、決定される。ＮｏＣにおける種々のチャネル群は、異なるクロック周波数で動作してもよく、また、チャネルにおけるバンド幅（帯域幅）に関する要求に基づいて、異なる幅であってもよい。チャネルにおけるバンド幅に関する要求は、そのチャネルを横断するフロー群及びそれらのバンド幅値によって決まる。種々のＮｏＣチャネルを横断するフロー群は、そのフロー群によって取られるルート群によって影響を受ける。メッシュＮｏＣ又はトーラスＮｏＣでは、送信元ノードと送信先ノードとの任意のペア間の長さが等しいか又はホップ数が等しいルートパスが複数存在する可能性がある。例えば、図２Ｂでは、ノード３４とノード００との間の標準ＸＹルートの他に、ＹＸルート２０３又は送信元から送信先までに１回よりも多い方向転換が為されるマルチターンルート２０２のような、利用可能な追加のルートが存在する。
【００１５】
種々のトラヒック渋滞について静的に割り当てられた複数のルートを持ったＮｏＣにおいて、種々のフロー群についてルートを知的に選択することによって、種々のチャネル群の負荷をコントロールすることができる。多数のトラヒックフロー及び十分なパスダイバーシティが存在する場合、すべてのＮｏＣチャネル群における負荷が略均一に釣り合うようにルートを選択することができ、これにより、ボトルネックの１つのポイントを回避することができる。ルートが決まると、複数のＮｏＣチャネル幅を、そのチャネル群におけるフロー群のバンド幅に関する要求に基づいて決めることができる。あいにく、時間的な輻輳又は配線の輻輳のような物理的なハードウェアデザインの制限のため、複数のチャネル幅は任意の大きさとすることはできない。最大チャネル幅についての制限があってもよく、これにより、いかなる１つのＮｏＣチャネルの最大バンド幅に対しても制限がかかる。
【００１６】
さらに、メッセージが短い場合、より広い物理的チャネル群がより速いバンド幅を実現するのに役立たない可能性がある。例えば、パケットが６４ビット幅を持つ１フリットから成るパケットである場合、チャネルをどんなに広くしたところで、そのチャネルを通るすべてのパケットが同様ならば、そのチャネルは、データサイクル毎に６４ビットしか運ぶことができない。このように、チャネル幅は、ＮｏＣにおけるメッセージサイズによっても制限される。最大ＮｏＣチャネル幅に対するこれらの制限のため、ルート群の均衡を保っていても、バンド幅が十分でない可能性がある。
【００１７】
上記のバンド幅に関する懸案に対処するために、複数の並列な物理的ＮｏＣが用いられてもよい。各ＮｏＣは、レイヤと呼んでもよく、これにより、マルチレイヤのＮｏＣ構造が作られる。ホストは、ＮｏＣレイヤにメッセージを投入し、このメッセージは、そのＮｏＣレイヤ上で目的地に向けて送られる。ここで、そのメッセージは、ＮｏＣレイヤから目的地であるホストへ届けられる。このように、各レイヤは、互いにほとんど独立して動作し、レイヤ間の相互接続は、ホストからＮｏＣレイヤへの投入時間及びＮｏＣレイヤからホストへの放出時間の間だけ生じてもよい。図３Ａは、２つのレイヤのＮｏＣを図示している。ここで、２つのＮｏＣレイヤは、互いに左右に隣り合わせで示されており、そのホスト群は、左右に複製されたＮｏＣに接続されている。１つのホストは、この例では、２つのルータと繋がっている。第１のレイヤのルータはＲ１として示されており、第２レイヤのルータはＲ２として示されている。この例では、マルチレイヤＮｏＣは、３ＤのＮｏＣと異なっている。例えば、マルチプルレイヤは、単一のシリコンダイ上に存在し、同じシリコンダイ上のホスト間の通信に対する高いバンド幅要求に合うようになっている。メッセージは、１つのレイヤからもう１つのレイヤへは行かない。明確化のために、この出願では、垂直方向に互いに重なるように図示する３ＤのＮｏＣと区別するために、マルチレイヤＮｏＣを左右に横並びで図示する。
【００１８】
図３Ｂでは、各レイヤのルータＲ１及びルータＲ２にそれぞれ接続された、ホストが図示されている。各ルータは、そのレイヤ内で方向性のあるポート３０１を用いて他のルータと接続されると共に、投入及び放出ポート３０２を用いてホストと接続されている。ブリッジロジック３０３は、ホストと２つのＮｏＣレイヤとの間に存在していてもよい。ここで、ブリッジロジック３０３は、メッセージが出て行くＮｏＣレイヤを決定し、また、ホストからそのＮｏＣレイヤへメッセージを送る。また、ブリッジロジック３０３は、２つのＮｏＣレイヤから入力される複数のメッセージを仲裁して多重し、その複数のメッセージをホストへ届ける。
【００１９】
マルチレイヤＮｏＣにおいて、必要なレイヤの数は、多くの因子（factors）に基づいてもよい。その多くの因子（factors）は、例えば、システムにおけるすべてのトラヒックフロー群の統合バンド幅に関する要求、種々のフロー群によって用いられるルータ群、メッセージサイズ分配、最大チャネル幅等である。ＮｏＣ相互接続におけるＮｏＣレイヤの数がデザインで決まると、異なるメッセージ群及びトラヒックフロー群は、異なるＮｏＣレイヤ群を介して転送されてもよい。さらに、異なるレイヤがルータ、チャネル、及び接続の数について異なるトポロジを有するように、ＮｏＣ相互接続をデザインしてもよい。レイヤが異なる複数のチャネルは、そのチャネルを通るフロー及びバンド幅要求に基づいて、異なるバンド幅を有していてもよい。
【００２０】
ＮｏＣ相互接続において、トラヒックプロファイルが統一されておらず且つある程度の不均一が存在している場合（例えば、或るホスト群は、他のホスト群よりもより頻繁に互いに遣り取りする場合）、その相互接続のパフォーマンスは、主に、ＮｏＣトポロジと、種々のホストが互いにそのトポロジ上でどこに配置されており且つその種々のホストにどのルータが接続されているかと、に基づいている可能性がある。例えば、２つのホストが互いに頻繁に遣り取りしより速いバンド幅を必要とする場合、その１つのホストは、互いに隣接して配設されるべきである。このようにすることで、この通信のレイテンシは低減し、これにより、この通信の速いバンド幅が設定される、ルータノード及びリンクの数が減るだけでなく、全平均レイテンシが減る。すべてのホスト群は２次元平面ＮｏＣトポロジ内に互いにオーバーラップすることなく配置されているので、２つのホストを近づけると、或る他の２つのホストは遠ざかることになる。このように、適切なトレードオフが為される必要があり、また、ホスト群は、すべてのホスト同士のペア毎のバンド幅及びレイテンシについての要求を、全体のコスト及びパフォーマンスのメトリクス（指標）が最適化されるように、分析した後に、配設される必要がある。そのコスト及びパフォーマンスメトリクスは、ルータポップの数における、通信しているすべてのホスト間の平均的な構造上レイテンシ、又は、ホストの全ペアのバンド幅及び各ペアのホップ数における距離の総和、又は、それらの組み合わせを含んでいてもよい。この最適化の問題は、非決定性多項式時間困難（NP-hard：non-deterministic polynomial-time hard）として知られており、発見的アプローチ（heuristic based approaches）がしばしば用いられる。システムにおける複数のホストは、互いに種々の形及びサイズを取り得る。そのシステムは、２次元平面ＮｏＣトポロジに複数のホストを配置すること、複数のホストをスペースをほとんど空けずに詰め込むこと、複数のホストがオーバーラップすることを回避することに、付加的な複雑さがある。
【００２１】
ＮｏＣを作る際に、例えば、米国特許出願13/965,668（Attorney Docket: 120126-NET021）で説明されているように、ＮｏＣにおけるエージェント間のキャッシュコヒーレンシーを維持する必要がある。ここで、米国特許出願13/965,668の全体が本明細書に参考として組み込まれる。キャッシュコヒーレンシーを維持するための関連技術の方法は、キャッシュコヒーレントデータを維持するためのいくつかの方法を含んでいる。関連技術の方法の一例では、データの１つのユニバーサルコピーが維持され、エージェント群は、そのユニバーサルコピーのみを参照する。関連技術の他の一例では、エージェント群は、自身のキャッシュを含んでいてもよく、これにより、自身のデータコピーを維持することができる。エージェントが自身のキャッシュを有していても有していなくてもよい他の異種システムでは、上記の関連技術の方法の両方が、採用され、且つ、MESI（Modified Exclusive Shared Invalid）、MSI、MOESI（Modified Owned Exclusive Shared Invalid）等の種々のキャッシュコヒーレンシープロトコルを用いることによって管理されてもよい。
【００２２】
キャッシュコヒーレンシープロトコルについてのステート（状態）遷移を管理するために、関連技術の方法は、キャッシュリクエストのコヒーレントステートを参照する。コヒーレントステートの参照に基づいて、存在するキャッシュ群に対して、それらのステートを変化させるために遷移コマンドが発行されてもよい。コヒーレントステートの参照は、ＮｏＣに関連するすべてのエージェントに対するブロードキャスト、又は、現在のステートを追跡してキャッシュ群のステートを管理するために用いることができるディレクトリ構造を必要とする。
【００２３】
関連技術のシステムにおいて、キャッシュコヒーレンシーを維持するためのハードウェアベースの解決策が用いられている。しかしながら、そのようなハードウェアベースの解決策によれば、典型的には、構造の固定化を余儀なくされ、固定化されたシステムとしてデザインされる。例えば、知られた数及び種類のエージェント及び知られた入出力コントローラ（input/output (I/O) controllers）を有する固定化されたシステムでは、そのシステムを管理するための、特別にデザインされた、キャッシュコヒーレンシーインタフェースＮｏＣが設けられてもよい。しかしながら、異なる複数のエージェントを必要とする場合（例えば、より多い又はより少ないエージェントを必要とする場合、内部キャッシュを用いることができるか又は用いることができない、異なる複数のエージェントを採用する場合等）、特別にデザインされた、キャッシュコヒーレンシーインタフェースＮｏＣは、その異なる複数のエージェントに十分に対処できない可能性がある。それゆえ、新しいシステムのユーザは、他のハードウェアによる解決策（例えば、次世代のキャッシュコヒーレンシーインタフェースＮｏＣ）が提供されるまで、待たなければならない。このため、任意のハードウェアシステム内のキャッシュコヒーレンシーを管理するための、一般的なハードウェアによる解決策が求められている。
【発明の概要】
【課題を解決するための手段】
【００２４】
本出願は、仕様によるＮｏＣ相互接続構造をデザインすることを対象としている。このＮｏＣ相互接続構造は、これに限定されるものではないが、ＮｏＣエージェントインタフェースの数及びキャッシュコヒーレンシーコントローラの数を含む、実装パラメータを示すことができる。ＮｏＣエージェントインタフェース及びキャッシュコヒーレンシーコントローラの柔軟性のある識別子によって、仕様からＮｏＣを構成する際に、任意の数のエージェントがＮｏＣと関連付けられることが可能となる。
【００２５】
本出願の態様は、方法を含んでいてもよい。この方法は、ＮｏＣ仕様に基づいて、１つ又は複数のＮｏＣエージェントインタフェースを構成し、さらに、ＮｏＣエージェント群の前記仕様に基づいて、１つ又は複数のキャッシュコヒーレンシーコントローラを構成することを含む。追加的な態様では、キャッシュコヒーレンスは、ディレクトリによって管理されてもよく、ここで、１つ又は複数のキャッシュコヒーレンシーコントローラは、前記ディレクトリの一部分と関連付けられていてもよい。
【００２６】
本出願の態様は、コンピュータで読み取り可能な記録媒体を含んでいてもよい。この記録媒体は、プロセスを実行するための指示群を保持している。この指示群は、他のパラメータの中でとりわけ、１つ又は複数のエージェント、ハードウェア要素群、バンド幅要求群、レイテンシ要求群に関連する情報についての、ＮｏＣ仕様を処理すること、及び、ＮｏＣの１つ又は複数のハードウェア要素をキャッシュコヒーレンシーコントローラ群又はＮｏＣエージェントインタフェース群として決定するために、そのような処理された情報を用いること、を含んでいてもよい。その指示群は、プロトコル群、バス幅、及び仕様に基づき必要とされる他のパラメータ群を用いた、ＮｏＣエージェントインタフェース群及び／又はキャッシュコヒーレンシーコントローラ群の設定をさらに含んでいてもよい。
【００２７】
本出願の態様は、方法を含んでいてもよい。この方法は、異種の複数のルータ又は異種のメッシュ配置、リング配置、若しくはトーラス配置によって相互接続された、複数のコアを含む、ネットワークオンチップ（ＮｏＣ）設定に関し、他のパラメータの中で、１つ又は複数のエージェント、ハードウェア要素群、バンド幅要求群、レイテンシ要求群に関連する情報についての、ＮｏＣ仕様を処理すること、及び、ＮｏＣの１つ又は複数のハードウェア要素をキャッシュコヒーレンシーコントローラ群又はＮｏＣエージェントインタフェース群として決定するために、そのような処理された情報を用いること、を含んでいてもよい。この方法は、さらに、仕様に基づいて必要とされる、プロトコル群、バス幅、及び他のパラメータを用いた、ＮｏＣエージェントインタフェース群及び／又はキャッシュコヒーレンシーコントローラ群の設定を含んでいてもよい。
【００２８】
本出願の態様は、システムを含んでいてもよい。このシステムは、ＮｏＣ仕様処理モジュール、ＮｏＣエージェントインタフェース設定モジュール、及び、キャッシュコヒーレンシーコントローラ設定モジュールを含んでいる。ＮｏＣ仕様処理モジュールは、他の属性の中でとりわけ、ＮｏＣエージェント群、ハードウェア要素群、バンド幅要求群、レイテンシ要求群のうちの１つ又は組み合わせに関連する情報を回収するため又は処理するための、ＮｏＣ仕様を処理するように構成されていてもよい。ＮｏＣエージェントインタフェース設定モジュールは、ＮｏＣエージェント群に基づいてハードウェア要素群のリストから１つ又は複数のＮｏＣエージェントインタフェースを決定するように、且つ、他のパラメータ群の中でとりわけ、プロトコル群、バス幅のような１つのパラメータ又は組み合わせパラメータに基づいて、ＮｏＣエージェントインタフェース群を設定するように、構成されていてもよい。これに対して、キャッシュコヒーレンシーコントローラ設定モジュールは、ハードウェア要素群のリストから、キャッシュコヒーレンシーコントローラ群を決定するように、且つ、これに限定されるものではないが、仕様に基づいて必要とされる、プロトコル群、バス幅、及び他のパラメータを含む、１つ又は複数のパラメータに基づいて、決定されたキャッシュコヒーレンシーコントローラ群を設定するように、構成されてもよい。
【図面の簡単な説明】
【００２９】
【図１Ａ】双方向リング型のＮｏＣトポロジの一例を示す図である。
【図１Ｂ】２次元メッシュ型のＮｏＣトポロジの一例を示す図である。
【図１Ｃ】２次元トーラス型のＮｏＣトポロジの一例を示す図である。
【図１Ｄ】３次元メッシュ型のＮｏＣトポロジの一例を示す図である。
【図２Ａ】関連技術の二次元メッシュにおけるＸＹルーティングの一例を示す図である。
【図２Ｂ】送信元ノードと送信先ノードとの間の３つの異なる経路を示す図である。
【図３Ａ】関連技術の２層ＮｏＣ相互接続の一例を示す図である。
【図３Ｂ】関連技術の、ホストと複数のＮｏＣレイヤとの間のブリッジロジックを示す図である。
【図４】実施例の設定変更可能なＮｏＣを示す図である。
【図５】実施例の、対応キャッシュコヒーレンシーコントローラに基づいて複数の部分に分割されたディレクトリの一例を示す図である。
【図６Ａ】マルチ符号化を含むディレクトリの一例を示す図である。
【図６Ｂ】実施例の、ディレクトリ内のセット・アソシエイティブのエントリの一例を示す図である。
【図７】実施例の、ＮｏＣの構築及び設定についてのフロー図である。
【図８】実施例を実装可能な、コンピュータ／サーバのブロック図である。
【発明を実施するための形態】
【００３０】
以下の詳細な説明において、本出願の図面及び実施例について詳しく説明する。図面間で重複する要素の参照番号及び記載は明確化のために省略する。詳細な説明を通して用いられる表現は例示であり、これに限定されるものではない。例えば、「自動（automatic）」という表現は、本出願の実装を実施する技術における通常スキルの予期される履行に基づいて、全自動実装、又は、実装の特定態様に対するユーザ又は管理者のコントロールを含む半自動実装を含んでいてもよい。
【００３１】
ここで説明される例示の実装は、設定変更可能なネットワークオンチップ（configurable NoC）である。この設定変更可能なネットワークオンチップは、例えば、図１−３のトポロジに図示されるように、設定変更可能なハードウェア要素（例えば、ホスト）の配列を含んでいる。提案するＮｏＣ相互接続構造は、仕様によって構成することができる。このＮｏＣ相互接続構造は、これに限定されるものではないが、ＮｏＣエージェントインタフェースの数及びキャッシュコヒーレンシーコントローラの数を含む、ＮｏＣの実装パラメータを示すことができる。これにより、仕様からＮｏＣを構成する際に、柔軟な数又は任意の数のエージェントがＮｏＣと関連付けられることが可能となる。１つの態様において、ここで開示するＮｏＣは、統合プロセッサ（IP：integrated processor）ブロック群、ルータ群、メモリ通信コントローラ群、及び、ネットワークインタフェースコントローラを含むことができる。このＮｏＣでは、各ＩＰブロックは、メモリ通信コントローラ及びネットワークインタフェースコントローラを介してルータに適応されている。他の態様では、メモリ通信コントローラは、さらに、１つ又は複数のキャッシュコヒーレンシーコントローラを含んでいてもよい。各キャッシュコヒーレンシーコントローラは、ＩＰブロックとメモリとの間の通信を制御するように構成されてもよい。また、各ネットワークインタフェースコントローラは、ルータ群を介した、中間ＩＰブロック通信を制御してもよい。ここで、メモリ通信コントローラは、メモリアクセス指示を実行するように、且つ、メモリアクセス指示によってアドレス指定されたキャッシュラインのステートを決定するように構成されてもよい。さらに、キャッシュラインのステートは、共有状態（shared）、独占状態（exclusive）、又は無効状態（invalid）のうちの１つとすることができる。
【００３２】
バンド幅要求及びレイテンシ要求を満たすために、ハードウェア要素群は、拡張性を提供できるように、或る配列で並べられてもよい。１つ又は複数のハードウェア要素は、仕様におけるエージェントの数及びバンド幅要求群に基づいて、キャッシュコヒーレンシーコントローラ群として構成されてもよい。ＮｏＣによって用いられるキャッシュコヒーレンシーコントローラ群の数は、仕様に基づいて柔軟性をもって決定されてもよい。
【００３３】
図４は、実施例の設定変更可能なＮｏＣ４００を図示している。この実施例では、ハードウェア要素群は、仕様に基づいて、ＮｏＣエージェントインタフェース４０２−１，４０２−２，４０２−３，・・・，４０２−ｎ、及び、キャッシュコヒーレンシーコントローラ４０４−１，４０４−２，４０４−３，・・・，４０４−ｎとして構成されてもよい。以下では、ＮｏＣエージェントインタフェース４０２−１，４０２−２，４０２−３，・・・，４０２−ｎを、纏めて、ＮｏＣエージェントインタフェース群４０２と呼び、キャッシュコヒーレンシーコントローラ４０４−１，４０４−２，４０４−３，・・・，４０４−ｎを、纏めて、キャッシュコヒーレンシーコントローラ群４０４と呼ぶ。また、この実施例では、ＮｏＣの入力／出力チャネル群は、対応するハードウェア要素と関連付けられていてもよい。ＮｏＣエージェントインタフェース群４０２及び／又はキャッシュコヒーレンシーコントローラ群４０４としてのハードウェア要素群の構成は、ＮｏＣを作るために用いられる仕様に基づいていてもよい。ハードウェア要素群は、ＮｏＣエージェントインタフェース群４０２及びキャッシュコヒーレンシーコントローラ群４０４のいずれか一方として構成され得るので、これにより、ＮｏＣは、そのハードウェアシステムにおいて用いられる、任意の数及び任意のタイプのエージェント群と関連付けられていてもよい。ＮｏＣエージェントインタフェース群４０２は、１つ又は複数のハードウェアエージェントと関連付けられていてもよく、また、そのハードウェアエージェントとの通信を促進するように柔軟性をもって構成されてもよい。これに対して、キャッシュコヒーレンシーコントローラ群４０４は、ハードウェアエージェント間のキャッシュコヒーレンシーを維持するように構成されてもよく、また、各ＮｏＣエージェントインタフェースと関連付けられた、任意の数及び任意のタイプのエージェント群に対するキャッシュコヒーレンシーを維持するように柔軟性をもって構成されてもよい。
【００３４】
ＮｏＣエージェントインタフェース群４０２として構成されたハードウェア要素群に関して、ＮｏＣエージェントインタフェース群４０２は、任意のエージェントとの通信を促進することができる必要がある。実施例では、１つ又は複数のＮｏＣエージェントインタフェースは、MESI、MSI、及びMOESI等の複数のプロトコルをサポートするように構成されてもよい。このようなサポートは、当該技術におけるスキルとして知られているプロトコル群のすべての機能を組み入れたユニバーサルプロトコルに基づいていてもよい。ユニバーサルプロトコルの機能群に対する複数の改良のサブセットは、仕様において特定された各エージェントに対して用いられてもよい。例えば、MOESIをベースとするユニバーサルプロトコルを用いて構成されたＮｏＣエージェントインタフェース４０２は、MESI及びMSIの機能を扱うように構成されてもよい。また、そのＮｏＣエージェントインタフェース４０２は、MESI及びMSIの機能を扱うために、MOESIプロトコルのサブセットを活用できるように構成されてもよい。ＮｏＣエージェントインタフェース群４０２は、異なるバス幅群をサポートして、仕様からの対応するエージェント群の要求群（バンド幅、レイテンシ等）を満たすようにするために、実装されてもよい。
【００３５】
１つの態様では、ＮｏＣのハードウェア要素群は、活用されるエージェントの数及びタイプに基づいて、もし必要ならば、さらに所望の実装に基づいて、キャッシュコヒーレンシーコントローラ群４０４としてさらに構成されてもよい。このため、ＮｏＣは、ディレクトリを管理すると共に関連付けられたエージェント群に対するロジックを制御するために、１つ又は複数のキャッシュコヒーレンシーコントローラ４０４を含んでいてもよい。キャッシュコヒーレンシーコントローラ群４０４の数及びこれらの構成は、仕様におけるエージェント群の数に基づいてもよく、また、コヒーレントバンド幅要求、レイテンシ要求、及びスループット要求に基づいてもよい。
【００３６】
共通ディレクトリがキャッシュの管理に用いられると、共通ディレクトリの参照回数が増えるにつれて、レイテンシの問題が起こる可能性がある。このため、本出願の実施例では、キャッシュコヒーレンシーコントローラ４０４として用いられる各ハードウェア要素は、さらに、アドレスについて分割した、ディレクトリの一部を管理するように、構成されてもよい。ディレクトリは、ＮｏＣエージェント群のキャッシュコヒーレンスを管理するように構成されてもよく、ここで、各キャッシュコヒーレンシーコントローラは、ディレクトリの一部と関連付けられてもよい。そのようなディレクトリ群は、ブロードキャストベースのディレクトリ群であってもよく、一態様では、ハマープロトコル（Hammer protocol）のようなプロトコルに従ってもよい。図５は、例示のディレクトリ５００を図示しており、ディレクトリ５００は、実施例に従って、対応するキャッシュコヒーレンシーコントローラに基づいて、複数の部分に分割されている。ディレクトリ５００は、ステート（例えば、読み出しのみ（read only）、読み出し／書き込み可能（read/write）等）、アドレスタグ、及び、ビットベクトルについてのエントリ群を含んでいてもよい。ここで、アドレスタグは、データを保持しているキャッシュ内のアドレスを示し、ビットベクトルは、データを保持するキャッシュを有するエージェントを示す。一態様では、ビットベクトルは、仕様に基づいて柔軟性をもって構成されてもよい。例えば、ＮｏＣが６４個のエージェントと関連付けられている場合、ビットベクトルは、６４ビット長のベクトルを有していてもよく、各ビットは、対応するエージェントにデータが保持されているか否かを示す。アドレスに基づく分割（Address slicing）を含む例では、ＮｏＣの１つのキャッシュコヒーレンシーコントローラは、アドレスブロック「０００」を管理するように構成されてもよく、他のキャッシュコヒーレンシーコントローラは、アドレスブロック「００１」，「０１０」，「０１１」を管理するように構成されてもよく、さらに他のキャッシュコヒーレンシーコントローラは、アドレスブロック「１００」，「１０１」等を管理するように構成されてもよい。このため、キャッシュコヒーレンシーコントローラ群に対する、ディレクトリのアドレスに基づく分割は、柔軟なＮｏＣの見積りを可能とし、エージェントの任意の数に合わせることができる。一態様では、キャッシュコヒーレンシーコントローラは、ディレクトリから、キャッシュラインのステートを取り出して、要求しているメモリ通信コントローラに対して、そのキャッシュラインのステートを返してもよい。他の態様では、ディレクトリ５００は、各キャッシュラインについて、キャッシュラインインデックス、及びキャッシュラインを識別するキャッシュラインタグを含んでいてもよい。
【００３７】
他の実施例では、ディレクトリ５００は、２次元以上で見積もられてもよい。そして、マルチ符号化（multiple encodings）を、実装の際にディレクトリにおいて用いることができる。例えば、ディレクトリ５００は、ビットベクトルを含む第１フォーマット又は対応するエントリを示すポインタを含む第２フォーマットについての、エントリ群を含んでいてもよい。図６Ａは、マルチ符号化を含んでいるディレクトリの一例を図示している。ビットベクトルを集約できるケースでは、例えばビットベクトルが重複している場合に、ビットベクトルの代わりに、ポインタを用いることができる。マルチ符号化をディレクトリに実装することにより、ディレクトリの領域（area）を減らすことができる。これにより、ＮｏＣに関連するエージェントの数が増えたときに拡張性をより良好にすることができる。図６Ｂのテーブル６５０に図示されるように、ポインタは、重複するビットベクトルのエントリを指すことができ、これにより、アドレスとビットベクトルとがセット・アソシエイティブ方式で関連付けられている。これにより、ポインタによって参照されるインデックスは、関連付けられたアドレスを見つけ出すために、ディレクトリ内の対応アドレスを参照することができる。アドレスが見つけられると、そのビットベクトルに到達するまで、ディレクトリは、隣接したエントリ群を調べられてもよい。これにより、この実装は、符号化及び次元をミックスした、任意の二次元ディレクトリを可能とする。このため、ディレクトリのサイズ及び形態は、セット・アソシエイティブに適応するために、任意に調整されてもよい。
【００３８】
ディレクトリのセット・アソシエイティブを含む実施例では、さらに、カッコウハッシュ（cuckoo hash）による組織化が為されてもよい。例えば、図６Ｂに図示されたようなエントリ群は、異なるインデックスメカニズムを用いて、別のハッシュテーブルに分離されてもよく、この場合、図６Ａのポインタは、そのハッシュインデックスを参照することができる。エントリをポップしハッシュテーブルに再キューイングすることによって衝突を解決するために、カッコウハッシュを採用することができる。
【００３９】
図７は、実施例に従ったＮｏＣの構築及び設定についてのフロー図７００を図示している。そのフローは、エージェント群、バンド幅要求群、及びレイテンシ要求群等に関する情報についての、仕様が処理されるときに、ステップ７０１で始まる。ステップ７０２で、ＮｏＣトポロジが決定され、ＮｏＣの１つ又は複数のハードウェア要素が、キャッシュコヒーレンシーコントローラ群又はＮｏＣエージェントインタフェース群として構成されてもよい。ステップ７０３で、ＮｏＣエージェントインタフェース群及び／又はキャッシュコヒーレンシーコントローラ群は、プロトコル群、バス幅、及び、仕様に基づき必要となる他のパラメータを用いて、設定される。また、ステップ７０３は、さらに、ＮｏＣエージェント群の仕様に基づく、キャッシュコヒーレンシーコントローラ群の設定を含んでいてもよい。
【００４０】
図８は、実施例が実装され得る、例示のコンピュータシステム８００を図示している。コンピュータシステム８００は、サーバ８０５と、入力／出力（I/O）ユニット８３５と、記憶装置（ストレージ）８６０と、この技術のスキルの１つとして知られている１つ又は複数のユニットを実行することができるプロセッサ８１０とを含んでいる。ここで用いられる「コンピュータ読み取り可能媒体（computer-readable medium）」という表現は、プロセッサ８１０が実行する指示をプロセッサ８１０へ与えることができる如何なる媒体を意味していてもよい。例えば、「コンピュータ読み取り可能媒体」は、コンピュータ読み取り可能記録媒体（computer readable storage mediums）の形態又はコンピュータ読み取り可能信号媒体（computer readable signal mediums）の形態であってもよい。コンピュータ読み取り可能記録媒体は、これに限定されるものではないが、光学ディスク、磁気ディスク、読み取り専用メモリ（read-only memories）、ランダムアクセスメモリ、ソリッドステートデバイス及びドライブ、又は、電子情報の記録に適した有形媒体の他の形態である。コンピュータ読み取り可能信号媒体は、キャリア波のような媒体を含んでいてもよい。入力／出力（I/O）ユニットは、ユーザインタフェース８４０及びオペレータインタフェース８４５からの入力を処理する。ユーザインタフェース８４０及びオペレータインタフェース８４５は、キーボード、マウス、タッチデバイス、又は音声入力装置（verbal command）のような入力装置であってもよい。
【００４１】
また、サーバ８０５は、外部記憶装置（外部ストレージ）８５０に接続されていてもよい。外部記憶装置８５０は、ポータブルハードドライブ、光学媒体（ＣＤ又はＤＶＤ）、ディスク媒体、又は、コンピュータが実行コードを読み取ることができる他の媒体のような、リムーバブル記憶媒体（removable storage）を含んでいてもよい。また、サーバ８０５は、ユーザからの要求追加情報（request additional information）だけでなく、ユーザに対して出力データ及び他の情報を出力するディスプレイのような、出力デバイス８５５と接続されていてもよい。サーバ８０５から、ユーザインタフェース８４０、オペレータインタフェース８４５、外部記憶装置８５０、及び出力デバイス８５５への接続は、無線プロトコル（wireless protocols）を介した接続、又は、物理的な通信媒体（physical transmission media）を介した接続であってもよい。無線プロトコルは、例えば、８０２．１１標準規格（802.11 standards）、Bluetooth（登録商標）、又は、セルラープロトコル（cellular protocols）である。物理的な通信媒体は、例えば、ケーブル又は繊維光学（fiber optics）である。このため、出力デバイス８５５は、ユーザと関わるための入力デバイスとして動作してもよい。
【００４２】
プロセッサ８１０は、１つ又は複数のモジュールを実行してもよい。システム８００は、ＮｏＣ仕様処理モジュール８１１、ＮｏＣエージェントインタフェース設定モジュール８１２、及び、キャッシュコヒーレンシーコントローラ設定モジュール８１３を含んでいてもよい。ＮｏＣ仕様処理モジュール８１１は、他の属性の中でとりわけ、ＮｏＣエージェント群、ハードウェア要素群、バンド幅要求群、レイテンシ要求群のうちの１つ又は組み合わせに関連する情報を回収するため又は処理するための、ＮｏＣ仕様を処理するように構成されていてもよい。ＮｏＣエージェントインタフェース設定モジュール８１２は、ＮｏＣエージェント群に基づいてハードウェア要素群のリストから１つ又は複数のＮｏＣエージェントインタフェースを決定するように、且つ、他のパラメータ群の中でとりわけ、プロトコル群、バス幅のような１つのパラメータ又は組み合わせパラメータに基づいて、ＮｏＣエージェントインタフェース群を設定するように、構成されていてもよい。
【００４３】
キャッシュコヒーレンシーコントローラ設定モジュール８１３は、ハードウェア要素群のリストから、キャッシュコヒーレンシーコントローラ群を決定するように、且つ、これに限定されるものではないが、仕様に基づいて必要とされる、プロトコル群、バス幅、及び他のパラメータを含む、１つ又は複数のパラメータに基づいて、決定されたキャッシュコヒーレンシーコントローラ群を設定するように、構成されてもよい。一態様では、キャッシュコヒーレンシーコントローラ群及びＮｏＣエージェントインタフェース群が準拠したプロトコル群は、他の類似のプロトコルの中でとりわけ、MESI(Modified Exclusive Shared Invalid)、MSI、MOESI(Modified Owned Exclusive Shared Invalid)を含んでいる。モジュール８１３は、さらに、キャッシュコヒーレンシーコントローラ群を管理するディレクトリを含み且つ処理するように構成されてもよい。ここで、各キャッシュコヒーレンシーコントローラは、ディレクトリの一部と関連付けられている。
【００４４】
実施例では、コンピュータシステム８００は、クラウドのようなコンピュータ環境において実装されてもよい。そのようなコンピュータ環境は、コンピュータシステム８００をそのまま含んでいてもよいし、コンピュータシステム８００が１つ又は複数の他のデバイスにネットワークによって繋がれており且つ１つ又は複数のストレージデバイス群と繋がれている状態でコンピュータシステム８００を含んでいてもよい。そのようなデバイス群は、移動可能なユーザイクイプメント（UE）（例えば、スマートフォン、車又は他の機械に搭載された装置、人間や動物によって持ち運ばれる装置等）、携帯装置（例えば、タブレット、ノートパソコン、ラップトップコンピュータ、パーソナルコンピュータ、ポータブルテレビ、ラジオ等）、及び、固定状態で使用される装置（例えば、デスクトップコンピュータ、他のコンピュータ、インフォメーションセンター、１つ又は複数のプロセッサが搭載され及び／又は繋がれたテレビ、ラジオ等）を含んでいてもよい。
【００４５】
これらのアルゴリズム的な記述及び象徴は、データ処理技術における当業者が他の当業者にイノベーションの本質を伝えるために用いる手段である。アルゴリズムは、所望の最終ステート又は最終結果へ導く工程群のシリーズである。その実施例では、実行される工程群は、具体的な結果を得るために、具体的な数の物理的な操作群を必要とする。
【００４６】
さらに、本出願の他の実施は、その仕様の考慮及びここに記述した実施例の実施から、当該技術の当業者にとって明らかであろう。記述してきた実施例の種々の態様及び／又は構成要素は、単独で又は任意の組み合わせで用いることができる。以上の仕様及び実施例は例示であり、本出願の真の範囲及び思想は以下の請求の範囲によって示されている。
【図１Ａ】
0006383793.tif 000002
【図１Ｂ】
0006383793.tif 000003
【図１Ｃ】
0006383793.tif 000004
【図１Ｄ】
0006383793.tif 000005
【図２Ａ】
0006383793.tif 000006
【図２Ｂ】
0006383793.tif 000007
【図３Ａ】
0006383793.tif 000008
【図３Ｂ】
0006383793.tif 000009
【図４】
0006383793.tif 000010
【図５】
0006383793.tif 000011
【図６Ａ】
0006383793.tif 000012
【図６Ｂ】
0006383793.tif 000013
【図７】
0006383793.tif 000014
【図８】
0006383793.tif 000015