【手続補正書】
【提出日】平成17年5月13日(2005.5.13)
【手続補正１】
【補正対象書類名】明細書
【補正対象項目名】特許請求の範囲
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
それぞれデータ要素を含むことが可能であり、０からｎ−１まで番号を付けられたｎ個の連続したステージに分配され、ステージｑはノード２qから２q+1−１を有する、１から２n−１まで番号を付けられた２n−１個のノードを有するバイナリツリーにしたがって構成された記憶手段と、１から２nー1−１の間の各整数ｉに対して、ノードｉが分類されるべき要素を含み、ノード２iおよび２i+1のそれぞれは分類されるべき要素を含まないか、あるいは決められた順序関係の向きにソートキーがノードｉに含まれている要素のソートキーよりも大きいかまたはそれに等しい要素を含むように、順序付けの条件を満足するように、ツリーの中でソートされる要素を分散させるためのバイナリツリーの制御手段を有し、
前記制御手段はソートされる新しい要素を挿入するためのコマンドを含むバイナリツリーの内容を修正するコマンドに応答する、それぞれ個々のソートキーを有するデータ要素をソーティングする装置において、
前記制御手段が、それぞれステージ（２０q）あるいはバイナリツリーの複数の連続したステージと組み合わされた、ｍが２からｎの間の整数であるｍ個の連続したコントローラ（２１q）と、連続したステージ間のｎ−１個のインタフェース・レジスタ（２６q）を有し、前記（ｎ−１）個のインタフェース・レジスタの中で異なるコントローラと組み合わされたステージ対の間のｍ−１個のインタフェース・レジスタの各々がパイプラインレジスタを構成し、バイナリツリーの内容を修正するための各コマンドはステージ０からステージｎ−１へ前記インタフェース・レジスタにより伝搬され、前記パイプラインレジスタは前記コントローラの並行動作を許容することを特徴とする、データ要素のソーティング装置。
【請求項２】
１からｎ−１の間の各整数ｑに対して、ステージｑ−１とステージｑの間の前記インタフェース・レジスタ（２６q）が、ステージｑ−１のノードからステージｑのノードへ伝搬されるコマンド（Ａq）を受信するための第１のロケーションと、組合されたコントローラ（２１qー1）が前記コマンドの処理の間にアクセスするステージｑ−１の前記ノードの識別情報（Ｄq）を受信するための第２のロケーションと、ステージｑ−１の前記ノードから送信されたか、あるいはステージｑ−１の前記ノードへ送信されるデータ要素（Ｂq、Ｃq）を受信するための第３のロケーションとを有する請求項１に記載の装置。
【請求項３】
１からｎ−１の間の各整数ｑに対して、ステージｑ−１とステージｑの間の前記インタフェース・レジスタ（２６q）が、第２のロケーションに含まれる識別情報（Ｄｑ）により、もし前記コマンドがツリーの中への新しい要素の挿入に関するものならば、前記コマンドが伝搬され、また対応するコントローラ（２１q）が、第１のロケーションに含まれるコマンド（Ａq）の処理の間にアクセスするステージｑのノードを指定するビット（Ｅq）を受信するための第４のロケーションを有する請求項２に記載の装置。
【請求項４】
１からｎ−１の間の各整数ｑに対して、ステージｑ−１とステージｑの間の前記インタフェース・レジスタ（２６q）の第２および第４のロケーションが、新しい要素を挿入するためのコマンドの伝搬の間に、空きの葉の数のｎ−１個の最下位ビットを含むｎ−１ビットの葉指定フィールド、すなわち、前記コマンドが伝搬される、ステージｎ−１の空きのノードの一部を形成し、前記コマンドが伝搬されるステージｑのノードは葉指定フィールドの内容のｑ個の最高位のビットにより指定される請求項３に記載の装置。
【請求項５】
ツリーのステージｎ−１と組み合わされたコントローラ（２１nー1）が、各葉に向かって新しい要素を挿入するためのコマンドが現在ツリーの中で伝搬されつつある各々の葉を含む、指定された数ｎ'空きの葉を含む、空きの葉の第１のリストと、第１のリストに含まれていない空きの葉を含む空きの葉の第２のリストを管理し、
ステージ０と１の間のインタフェース・レジスタの第１のロケーションにソートされる新しい要素を挿入するためのコマンドを登録する間に、各々の葉と異なりそれに向かってツリーの中で他の挿入コマンドが現在伝搬されつつある、第１のリストの空きの葉の数のｎ−１個の最下位ビットがステージ０と１の間のインタフェース・レジスタの葉指定フィールドの中に登録され、
ツリーの葉からの要素の抽出の間、前記葉は空きの葉の第２のリストに含まれ、
新しい要素を挿入するためのコマンドがステージｎ−２とｎ−１の間のインタフェース・レジスタ（２６nー1）の中のステージｎ−１に到達すると、対応するコントローラ（２１nー1）が空きの葉の第１のリストから前記インタフェース・レジスタの葉指定フィールドのｎ−１個のビットにより指定された葉（Ｇnー1）を除去し、それを第２のリストからの葉（Ｐ）に置換する請求項４に記載の装置。
【請求項６】
ｎ'＜ｎである請求項５に記載の装置。
【請求項７】
空きの葉の第１のリストが、それぞれが葉の数のｎ−１個の最下位ビットを受信するｎ'個のロケーションを有するそれ自身ループバックされるシフト・レジスタ（３０）に記憶される請求項５または６に記載の装置。
【請求項８】
空きの葉の第２のリストが後入れ先出し形式でポインタの連鎖の形で格納され、各ポインタは葉の数を表し、前記連鎖の第１のポインタ（Ｐ）は特定のロケーションに格納され、前記連鎖のｉ番目のポインタ（ｉ≧２）は番号が連鎖のｉ−１番目のポインタで表される葉に格納されている請求項５、６、７のいずれか１項に記載の装置。
【請求項９】
第１および第２のリストは少なくともｎ'個のロケーションを有する先入れ先出し形式の論理待ち行列の形式で格納され、第１のリストは、論理待ち行列の最後のｎ'個のロケーションからなり、第２のリストは論理待ち行列の先行するロケーションから成る請求項５または６に記載の装置。
【請求項１０】
ｐは、ｍ番目のコントローラと組み合わされているバイナリツリーのステージの数であって１以上ｎ−１未満であり、前記記憶手段がｉが１から２nーpー1−１の範囲であるツリーのノード２iと２i+1の対とそれぞれ組み合わされた差分カウンタ（Δ（ｉ））を含むための少なくとも２nーpー1−１個のロケーション（２５）を有し、一対のノードと組み合わされた各差分カウンタが前記対の２つのノードの子孫にそれぞれ含まれる、データ要素の数の間の差を示す値を有し、ステージｑのノードｉの子孫がバイナリツリーの２nーq−１個のノードと規定されており、その数はｉ２j＋ｊ'（ｊおよびｊ'は０≦ｊ＜ｎ−ｑおよび０≦ｊ'＜２jのような整数）の形であって、
ステージｑ−１とステージｑ（１≦ｑ＜ｎ−ｐ）の間のインタフェース・レジスタ（２６q）が、新しい要素をその第１のロケーションに、またステージｑ−１のノードｉの識別情報（Ｄｑ）をその第２のロケーションに挿入するコマンド（Ａｑ）を受信すると、ノード２iと２i+1の対と組み合わされた差分カウンタ（Δ（ｉ））の値に応じて前記挿入コマンドがステージｑのノード２iあるいは２i+1に伝搬される請求項２または３に記載の装置。
【請求項１１】
１つのステージのノードの対と組み合わされた差分カウンタ（Δ（ｉ））を含む記憶手段のロケーション（２５）が、前記ステージのノードと同じコントローラによりアクセス可能である請求項１０に記載の装置。
【請求項１２】
前記記憶手段は、ｉが１から２nー1−１の範囲である、ツリーのノード２iと２i+1の対とそれぞれが組み合わされたステアリングビット（Ｆ（ｉ））を含むための２nー1−１個のロケーション（２３）を有し、前記対のノードの１つを指向する一対のノードと組み合わされた各ステアリングビットが、ソートキーが前記対の他のノードに含まれる要素のソートキー以下である要素を含み、
ステージｑ−１とステージｑ（１≦ｑ≦ｎ−１）の間のインタフェース・レジスタ（２６q）が、その第１のロケーションにおいて要素を抽出あるいは交換するためのコマンド（Ａq）を、またその第２のロケーションにおいてステージｑ−１のノードｉの識別情報（Ｄｑ）を受信すると、前記抽出あるいは交換コマンドが、ノード２iと２i+1の対と組み合わされたステアリングビット（Ｆ（ｉ））の値に応じて、ステージｑのノード２iあるいは２i+1に伝搬される請求項２から１１のいずれか１項に記載の装置。
【請求項１３】
１つのステージのノードの対と組み合わされたステアリングビット（Ｆ（ｉ））を含む記憶手段のロケーション（２３）が、前記ステージのノードと同じコントローラによりアクセス可能である請求項１２に記載の装置。
【請求項１４】
複数の仮想接続にしたがって送信されるＡＴＭセルのスペーサであって、着信セルが書き込まれ、発信セルが読み出されるセルメモリ（４２）と、前記セルメモリに記憶された各セルに理論的送出時間（ＴＥＴ）を割り当てる手段（４０、４１）とを有する、ＡＴＭセルのスペーサにおいて、
仮想接続がセルを収容している各仮想接続に対して、前記セルがリストの始めとリストの終わりの間で先入れ先出しモードで格納されるロケーションのリストをセルメモリが有するように関連するポインタメモリ（４３）の助けにより、前記セルメモリ（４２）を管理するスペーシング制御手段（４１、４６）と、
仮想接続識別情報と、前記仮想接続に関するリストの始めに含まれているセルの理論的送出時間から成るソートキーを各々が有するデータ要素（Ｋ（ｉ）、Ｒ（ｉ））を順序づけ、最小のソートキーを有する少なくとも１つのデータ要素を選択するソーティング手段（４１、４４）をさらに有し、
前記スペーシング制御手段は、前記ソーティング手段により選択されたデータ要素における識別された仮想接続に関するリストの始めに含まれたセルの送出を命令するするように構成され、前記ソーティング手段は、請求項１から１３までのいずれか１項に記載のソーティング装置であって、ステージ０のそのノード１が前記選択された要素を含むソーティング装置を少なくとも１つ有する
ことを特徴とするＡＴＭセルのスペーサ。
【請求項１５】
セルメモリに記憶された各セルに理論的送出時間を割り当てる手段が、前記セルの到着時刻（ｔａ）と前記接続に割り当てられたスペーシング間隔（Ｔ）とを少なくとも含むパラメータに基づいて、仮想接続に関連する各セルに対する理論的送出時間（ＴＥＴ）を回帰的に計算する手段（４０）を有し、
前記ソーティング手段（４１、４４）は、前記セルメモリ（４２）がセルを含んでいない仮想接続に関連するセルが到着すると、前記仮想接続の識別情報を有する新しいデータ要素、およびソートキーとして、前記回帰的計算手段（４０）によって供給された前記セルの理論的送出時間を受け取り、
前記ソーティング手段は、少なくとも１つの第２のセルをさらに含むロケーションのリストを前記セルメモリが有する仮想接続に関連する第１のセルを送出すると、前記仮想接続の識別情報を有する新しいデータ要素、およびソートキーとして、前記第１のセルの理論的送出時間と前記接続に割り当てられたスペーシング間隔との和に等しい前記第２のセルの理論的送出時間を受け取る請求項１４に記載のスペーサ。
【請求項１６】
優先権インデックス（ｕ）が仮想接続に割り当てられ、前記ソーティング手段はそれぞれ同様の優先権インデックスの仮想接続の識別情報を有するデータ要素を処理し、またそれぞれそれが処理するデータ要素の中から最小のソートキー（Ｋ(u)（１））を有する要素を選択するいくつかの、請求項１から１３までのいずれか１項に記載のソーティング装置（４４(u)）を有し、前記スペーシング制御手段は、最小のソートキーを示す選択されたデータ要素の１つに、あるいは、複数のソーティング装置がそれぞれそのソートキーが最小であるデータ要素を選択するならば、前記複数のソーティング装置により選択された優先権インデックスが最高であるデータ要素の１つにおける識別された接続に関連するリスト開始に含まれているセルの送出を命令するように構成されている請求項１４または１５に記載のスペーサ。
【請求項１７】
種々のソーティング装置の各々が、それぞれの記憶手段（２０q(1)、２０q(2)を有し、またその制御手段（２１q、２６q）を共有する請求項１６に記載のスペーサ。
【手続補正２】
【補正対象書類名】明細書
【補正対象項目名】０００１
【補正方法】変更
【補正の内容】
【０００１】
【発明の属する技術分野】
本発明は、それぞれデータ要素を含むことが可能であり、０からｎ−１まで番号を付けられたｎ個の連続したステージに分配され、ステージｑはノード２qから２q+1−１を有する、１から２n−１まで番号を付けられた２n−１個のノードを有するバイナリツリーにしたがって構成された記憶手段と、１から２nー1−１の間の各整数ｉに対して、ノードｉが分類されるべき要素を含み、ノード２iおよび２i+1のそれぞれは分類されるべき要素を含まないか、あるいは決められた順序関係の向きにソートキーがノードｉに含まれている要素のソートキーよりも大きいかまたはそれに等しい要素を含むように、順序付けの条件を満足するように、ツリーの中でソートされる要素を分散させるためのバイナリツリーの制御手段を有する、それぞれソートキーを有しデータ要素をソートする装置に関する。