(57)【要約】  複数のキーでセルフソートされるテーブル１０であって、インテリジェントな複数のセルフソーティングモジュール１２を含んでいる。各モジュールは、少なくとも１つの値をもつエントリを有し、テーブルに対してエントリの追加又は削除があるとき、４つのアクション(その現在値を保持すること、新たなエントリを格納すること、より大きな値を有する隣接モジュールからエントリを取得すること、又はより小さな値を有する隣接モジュールからエントリを取得すること)の中の１つのアクションを実行するための決定を行ない、その決定が実行される。【選択図】  図１
2004355626.tif 000002
【特許請求の範囲】
【請求項１】
複数のキーでセルフソートされるテーブルであって、
インテリジェントな複数のセルフソーティングモジュールを具え、各モジュールは、少なくとも１つの値をもつエントリを有し、複数のアクションの１つを実行するための決定を行なうことができるテーブル。
【請求項２】
テーブルに対してエントリの追加又は削除があるとき、各モジュールによって実行される複数のアクションは、その現在値を保持すること、新たなエントリを格納すること、より大きな値を有する隣接モジュールからエントリを取得すること、又はより小さな値を有する隣接モジュールからエントリを取得することの４つのアクションを含んでおり、その決定が実行される請求項１に記載のテーブル。
【請求項３】
各モジュールは、コントローラと、該コントローラに接続されてエントリを格納する格納部とを具えている請求項２に記載のテーブル。
【請求項４】
各エントリは、第１キーと、少なくとも第２キーを有し、複数のポインタ(20)を含んでおり、複数のポインタの中の１つのポインタは、第１キーの第１エントリを指す請求項３に記載のテーブル。
【請求項５】
コントローラは、該コントローラに接続された格納部に格納されたエントリの値を、より大きな値を有する隣接モジュール、及び、より小さな値を有する隣接モジュールに通知する請求項４に記載のテーブル。
【請求項６】
各コントローラは、加えられるべきエントリ又は差し引かれるべきエントリが、コントローラに接続された格納部に格納されたエントリよりも大きな値又は小さな値を有するか有しないかのリザルトを演算し、そのリザルトを、大きな値を有する隣接モジュール及び小さな値を有する隣接モジュールに通知する請求項５に記載のテーブル。
【請求項７】
各コントローラは、そのリザルトと、大きな値を有する隣接モジュール及び小さな値を有する隣接モジュールのリザルトに基づいて、複数のモジュールの他の全てのコントローラと並行して、その決定を行なう請求項６に記載のテーブル。
【請求項８】
テーブルをソートする方法であって、
各々が少なくとも１つの値をもつエントリを有する複数のインテリジェントなセルフソーティングモジュールの中の各モジュールにより、複数のアクションの中の１つのアクションを実行するための決定を行なうステップを含んでいる方法。
【請求項９】
テーブルに対してエントリの追加又は削除があるとき、４つのアクションの中の１つを実行するための決定を行なうステップを含んでおり、その現在値を保持するか、新たなエントリを格納するか、より大きな値を有する隣接モジュールからエントリを取得するか、又はより小さな値を有する隣接モジュールからエントリを取得するかが決定される請求項８に記載の方法。
【請求項１０】
各エントリは、第１キーと、少なくとも第２キーを有しており、複数のポインタの中の１つのポインタで、第１キーの第１エントリを指すステップを含んでいる請求項９に記載の方法。
【請求項１１】
各モジュールは、コントローラと、該コントローラに接続されてエントリを格納する格納部とを具えており、各モジュールのコントローラにより、該コントローラに接続された格納部の中のエントリ(14)の値を、より大きな値を有する隣接モジュール及びより小さな値を有する隣接モジュールに通知するステップを含んでいる請求項１０に記載の方法。
【請求項１２】
各コントローラを用いて、加えられるべきエントリ又は差し引かれるべきエントリが、コントローラに接続された格納部に格納されたエントリよりも大きな値又は小さな値を有するか有しないかのリザルトを演算し、そのリザルトを、大きな値を有する隣接モジュール及び小さな値を有する隣接モジュールに通知するステップを有している請求項１１に記載の方法。
【請求項１３】
決定を行なうステップは、そのリザルトと、大きな値を有する隣接モジュール及び小さな値を有する隣接モジュールのリザルトに基づいて、各コントローラが、複数のモジュールのうちの他の全てのコントローラと並行して、その決定を行なうステップを含んでいる請求項１２に記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
＜発明の分野＞
本発明は、複数のキーでセルフソートされるテーブルであって、任意の数のキーに対して一群の番号つきリスト(ordered lists)を提供するテーブルに関する。より具体的には、本発明は、複数のキーでセルフソートされるテーブルであって、インテリジェントな複数のセルフソーティングモジュールを用い、任意の数のキーに対して、一群の番号つきリストを提供するテーブルに関する。
【背景技術】
【０００２】
＜発明の背景＞
ソートされたリストは、データ通信において共通の要件である。このリストは、１又は２又は３以上のキーによってソートされることができ、エントリを自由に追加させる必要があり、所定のキーに対する第１エントリは除去可能(removable)であらねばならない。これまでの構造体では、小さく、固定されたサイズのアレイが用いられていた。少数のエントリが、必要なときにいつでも最小のもがサーチされ、最小のものを見つけるのにコンパレータのツリーを必要とする。この方式では、サーチのレイテンシー(latency)が、アレイのサイズと共に大きくなるので、スケーラブル(scalable)ではなかった。この方式はまた、各キーに対して、別個の固定サイズテーブルを用いているため、全てのキーを使用しないときは、非効率的であった。また、エントリの格納方法も、方式によって相違があった。また、エントリは、メモリアレイに格納されていた。
【発明の開示】
【０００３】
本発明では、全てのエントリがいつでもアクセス可能なように、独立したフロップ(flops)を用いるものである。本発明は、複数のキーでセルフソートされるテーブル(Multiple Key Self-Sorting Table)と称されるもので、任意の数のキーに対して一群の番号つきリストを提供する。これにより、エントリの追加又は除去を、非常に少ないレイテンシーで効率良く行なうことができる。テーブルは、キーとスケールの間でエントリのフレキシブルな割当てを可能ならしめる。この方式は、ハードウエアを並列稼働して効率的に用いており、複数のキーによってソートされたテーブルに対して、高速のスケーラブルソルーション(scalable solution)を作ることができる。
【０００４】
本発明は、複数のキーがセルフソートを行なうテーブルに関する。テーブルは、インテリジェントな複数のセルフソーティングモジュールを含んでいる。複数のモジュールの中の各モジュールは、少なくとも１つの値をもつエントリを有している。テーブルにエントリの追加又は削除があるとき、各モジュールは、複数の動作の１つを実行する決定を行なう。ここで、複数の動作は４つが望ましく、その場合、その現在値を保持するか、新たなエントリを格納するか、直ぐに隣接するモジュールで、より大きな値を有するモジュールからエントリを取得するか、又は直ぐに隣接するモジュールで、より小さな値を有するモジュールからエントリを取得するかが決定され、その決定が実行される。
【０００５】
本発明は、テーブルをソートする方法に関する。本発明の方法は、テーブルに対してエントリの追加又は削除があるとき、各々が少なくとも１つの値をもつエントリを有するインテリジェントな複数のセルフソーティングモジュールの中の各モジュールにより、４つのアクションの中の１つのアクションを実行するための決定を行なうステップを含んでおり、その現在値を保持するか、新たなエントリを格納するか、より大きな値を有する隣接モジュールからエントリを取得するか、又はより小さな値を有する隣接モジュールからエントリを取得するかが決定される。また、決定を実行するステップがある。
【０００６】
＜詳細な説明＞
図面を参照すると、幾つかの図において、同一又は同様な要素については同じ引用符号を付している。例えば、図１は、複数のキーでセルフソートされるテーブル(10)を示している。テーブル(10)は、インテリジェントな複数のセルフソーティングモジュール(12)を含んでいる。複数のモジュール(12)の各モジュールは、少なくとも１つの値をもつエントリ(14)を含んでいる。テーブル(10)にエントリ(14)の追加又は削除があるとき、各モジュールは、複数の動作の１つを実行するための決定を行なう。その動作数が４つのとき、例えば、その現在値を保持するか、新たなエントリ(14)を格納するか、直ぐに隣接するモジュールで、より大きな値を有するモジュールからエントリ(14)を取得するか、又は直ぐに隣接するモジュールで、より小さな値を有するモジュールからエントリ(14)を取得するかの決定を行ない、その決定を実行する。
【０００７】
各モジュールは、コントローラ(16)と、該コントローラに接続されてエントリ(14)を格納する格納部(storage)(18)とを具えている。各エントリ(14)は、第１キーと、少なくとも第２キーを有し、複数のポインタ(20)を含むことが望ましい。複数のポインタ(20)の中の１つのポインタ(20)は、第１キーの第１エントリ(14)を指すようにする。コントローラ(16)は、該コントローラ(16)に接続された格納部(18)の中のエントリ(14)の値を、より大きな値を有する隣接モジュール、及び、より小さな値を有する隣接モジュールに通知することが望ましい。
【０００８】
各コントローラ(16)は、加えられるべきエントリ(14)又は差し引かれるべきエントリ(14)が、コントローラ(16)に接続された格納部(18)に格納されたエントリ(14)よりも大きな値又は小さな値を有するか有しないかのリザルトを演算し、大きな値を有する隣接モジュール及び小さな値を有する隣接モジュールに、前記リザルトを通知することが望ましい。各コントローラ(16)は、そのリザルトと、大きな値を有する隣接モジュール及び小さな値を有する隣接モジュールのリザルトに基づいて、複数のモジュール(12)の他の全てのコントローラ(16)と並行して、その決定を行なうことが望ましい。
【０００９】
本発明は、テーブル(10)をソートする方法に関する。本発明の方法は、テーブル(10)に対してエントリ(14)の追加又は削除があるとき、各々が少なくとも１つの値をもつエントリ(14)を有する複数のインテリジェントなセルフソーティングモジュール(12)の中の各モジュールにより、複数のアクション、望ましくは４つのアクションの中の１つを実行するための決定を行なうステップを含んでおり、その現在値を保持するか、新たなエントリ(14)を格納するか、より大きな値を有する隣接モジュールからエントリ(14)を取得するか、又はより小さな値を有する隣接モジュールからエントリ(14)を取得する。また、決定を実行するステップがある。
【００１０】
各エントリ(14)は、第１キーと、少なくとも第２キーを有しており、複数のポインタ(20)の中のポインタで、第１キーの第１エントリ(14)を指す(pointing)ステップを含むことが望ましい。各モジュールは、コントローラ(16)と、該コントローラに接続されてエントリ(14)を格納する格納部(18)とを具えていることが望ましく、各モジュールのコントローラ(16)が、より大きな値を有する隣接モジュール及びより小さな値を有する隣接モジュールに対して、コントローラ(16)に接続された格納部(18)の中のエントリ(14)の値を通知するステップを含んでいる。
【００１１】
また、各コントローラ(16)にて、加算又は減算されるべきエントリ(14)が、コントローラ(16)に接続された格納部(18)に格納されたエントリ(14)よりも大きな値又は小さな値を有するか有しないかのリザルトを計算し、そのリザルトを、大きな値を有する隣接モジュール及び小さな値を有する隣接モジュールに通知するステップを有することが望ましい。決定を行なうステップは、そのリザルトと、大きな値を有する隣接モジュール及び小さな値を有する隣接モジュールのリザルトに基づいて、各コントローラ(16)が、複数のモジュール(12)のうちの他の全てのコントローラ(16)と並行して、その決定を行なうステップを含むことが望ましい。
【００１２】
複数のキーでセルフソーティングされる本発明に係るテーブル(10)において、全てのエントリ(14)は、インテリジェントなセルフソーティングモジュールである。以下の実施例では、図示のデュアルキーテーブル(10)は、第１キーがポート番号(port number)である。所定のポートに属するエントリは全て、テーブル(10)の中で連続している(consecutive)。ポートのエントリは、第２キーによってさらにソートされる。このキーは、最も小さなキー値を有するポート用として用いるために、次のエントリ(14)を見つける手段を提供する。図面の左側に、３、１３及び３７の値をもつ３つのアクティブエントリを有するポート０を示している。ポート１及びポート２は、エンプティであり、ポート３は、１１及び９２の値をもつ２以上のエントリを有している。図面の右側に示すテーブル(10)は、ポート２がエントリ(14)に加えられ、ポート０のヘッドエントリ(14)が除去された後のものである。ヘッドポインタ(20)は、テーブル(10)のトップにないポートに対して、第１エントリ(14)の読み出しを行なうのに必要である。
【００１３】
各インテリジェントモジュールは、エントリ(14)を追加／削除するとき、４つの事項(things)のうちの１つを行なう。例えば、(i)その現在値(current value)を保持するか、(ii)新たなエントリ(14)を格納するか、(iii)大きな値の隣接モジュールからエントリ(14)を取得するか、(iv)小さな値の隣接モジュールからエントリ(14)を取得することである。各エントリ(14)がどのアクションをとるかを決定するのに必要なのは、その隣接モジュールと、追加又は削除が行われるエントリの情報のみである。各エントリ(14)は、加えられるべきエントリ(14)又は差し引かれるべきエントリ(14)が、それよりも上か下であるかを演算する。各エントリ(14)は、次に、その演算結果を２つの隣接モジュールに通知する。この情報に基づいて、隣接モジュールは、どの動作を並列して実行するかを決定する。これは、構造体が、大きなアレイと同じ速度で稼働できることを意味する。アレイが無限に成長する上でバリアとなるのは、挿入／削除の情報の追加ファンアウト、新エントリに対して追加されるシリコン、個々のエントリを引き出すのに必要なｍｕｘ(マルチプレクサ)ツリーだけである。各エントリ(14)は、その次の値を同時に演算するから、この構造体は、非常に迅速に更新することができるので、これまで用いられていた構造体のように、連続比較(serial comparison)に大きな遅延をもたらすことはない。
【００１４】
図２は、デュアルキーによる稼働中のセルフソーティングテーブル(10)を示している。各モジュール(各ステップの右側に円で囲んで示す)は、並行してその決定を行なうから、図示のトランスフォーメーションの各々は、非常に速やかに実行される。既にソートされたデータは格納されているため、ポートの最小値にアクセスすることは、極く些細なタスクにすぎない。
個々のソーティングモジュールは、図３に示す構造を有している。
【００１５】
各モジュールを同時に稼働させるために、各モジュールは、同じクロックドメイン内にある同じクロック信号のコピーを受信する。このクロックは、イテレーション(繰り返し)を実行することを全てのロジックに告知する周期的パルスである。
【００１６】
当該分野で広く知られているように、回路基板上で、タイミング信号を発生させる。それは、基板のＡＳＩＣｓの全てに分配され、その各々は、これらモジュール(12)を含むＡＳＩＣｓの至るところにある制御及び格納部(18)のロジックの全てに分配する。
【００１７】
本発明の実施例について詳細に説明したが、それらは単なる例示であって、当該分野の専門家であれば、特許請求の範囲に記載された発明の精神及び範囲から逸脱することなく、その詳細について変形を成し得ることは理解されるべきである。
【図面の簡単な説明】
【００１８】
【図１】本発明のセルフソーティングテーブルの概略図である。
【図２】稼働中のセルフソーティングテーブルを示す図である。
【図３】本発明のモジュールの概略図である。
【符号の説明】
【００１９】
(10)  テーブル
(12)  モジュール
(14)  エントリ
(16)  コントローラ
(18)  格納部
(20)  ポインタ
【図１】
2004355626.tif 000003
【図２】
2004355626.tif 000004
【図３】
2004355626.tif 000005