(57)【要約】【課題】本発明の課題は、コンピュータの最も基本的な演算手段の一つのデータの整列方法について、最近の高速コンピュータの演算処理時間の一般的な整列時間を実用的に零とする高速な整列演算を、必要な場合安価なハードウェア装置を用いて表現することである。【解決手段】課題を実現するため、従来の置換と比較を基本とするアルゴリズムを採用せず、Ｎワードのレコードの先頭ワードから、データを再帰的に分類するアルゴリズムを採用し、複数の記憶回路ブロックと複数の演算ブロックからなる装置において、ワードの呼び出し時間内に他の補助的処理を並列処理し、また、入出力操作との並列処理を行うことにより、実用処理時間を零とする整列装置を提供した。【選択図】　　図１
2004145619.tif 000002
【特許請求の範囲】
【請求項１】
８以上の数値Ｎをワードとし、１以上の数値Ｍワードからなるデータをレコードとし、そのレコードの集合で、記憶回路（記憶回路Ａ）上に展開させられているものから、昇順、または、降順に整列されたレコードの集合を生成する、若しくは、集合を配列と見た場合のインデックス、若しくは、その集合の各レコードの先頭アドレス（ポインタ）、若しくは、その集合の記憶回路中の先頭番地からの相対番地（バイトカウント）等のレコード認識データを、それが指し示すレコードの値で昇順、または、降順に整列しているところの集合を生成するデータの整列装置であって、Ｍレベルの２のＮ乗個の可変数のデータを記憶する記憶ユニットを構成するところの記憶回路（記憶回路Ｂ）と、その制御回路を構成する１またはＭセットの記憶回路（記憶回路Ｃ）と、２のＮ乗個の記憶ユニットに有効データが保管されていることを示すデータを保管するＭレベル記憶回路（記憶回路Ｄ）と、演算装置であって、第１ステップとし、Ｍワードのレコードの最上位のワードの値を記憶回路Ａから順次呼び出し、その値を番号に保有するレベル１の記憶ユニット、即ち、番号として０から２のＮ乗マイナス１の番号を保有することができる記憶ユニットで、記憶回路Ｃのデータで制御されている記憶回路Ｂに、該当するレコードデータ、または、インデックス、または、ポインタ等のレコード認識データを格納し、同時に、使用された記憶ユニットの番号マークをレベル１の記憶回路Ｄに保存し、第２ステップとし、記憶回路Ｄの情報を用いて、前回参照されたレベルの記憶ユニットで最も小さな値（昇順の場合、降順の場合は最も大きな値、以下昇順を基準として記述する。）を保有する記憶ユニットからレコード認識データを読み出し、それ以前にレコードＭワードの全てのデータの参照が完了している場合と、そのレコード認識データが当該番号の記憶ユニットに１個しか保有されてない場合は、そのレコード認識データが示すレコードが最小値であると認識し、当該演算装置からは整列済みとし、出力集合に組み入れ、次に小さな値を持つ処理ユニットの操作として、ステップ２の処理の継続操作を実施し、そうで無い場合、レコード認識データが指すレコードの前回参照したワードより、一つ下位の数値を構成するワードの数値を読み出し、それを前回のレベルより１増加させたレベルの記憶ユニットで、その読み出した数値の番号の記憶ユニットに当該レコード認識データを保管し、また、同時にプラス１のレベルの記憶回路Ｄに当該ユニットにデータが保管されたという情報をセットし、第２ステップの先頭の処理に移行し、先に記述した第２ステップの処理を継続し、当該レベルの第２ステップの処理において、さらに再帰的な処理が必要な場合、さらに高次のレベルへ処理を移行させ、最終的に同一のレベルにおいて最も大きな記憶ユニットの処理が終了した時点で、当該レベルの第２ステップ処理を移行させたレベルの第２ステップの処理において、当該レベルの第２ステップへ処理を移行させた処理の次の処理へ戻り、記憶ユニット等のレベルを１減少させ、処理を実行継続し、最終的の第１ステップで格納された全てのレコード認識データを出力集合に組み入れ、整列された情報を作成する再帰的な演算処理装置からなる高速整列演算装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明はデジタルデータを高速整列する装置に関するものである。とりわけ、データベース検索処理等の索引作成等のデジタルコンピュータの基本処理を支援するものであり、大容量、他ワード長のデータを平易に、かつ、高速に扱うことを特徴としている。
【０００２】
【従来の技術】
デジタルデータを整列することはコンピュータを利用するデジタルシステムにおいて、複数のデータから特定のデータを引き出すという極めて一般的なアプリケーションにおいて、必須かつ極めて重要なデータ処理であり、データを整列させることにより、すべてのデータを調べることなく、高速に目的のデータを参照することかできるをいう効果を生む。近年、データベースが益々巨大化し、コンピュータの性能の向上の割合以上に発展し、時には、ＣＰＵ演算時間の５０％以上を整列演算が占有するというアプリケーションも増加し、整列処理をさらに高速に実行したいという要求が強まり、コンピュータとは別のハードウェア演算回路を保有してでも整列を高速に実行できるシステムが求められている。
【０００３】
本発明は、一般的なコンピュータの構造を意識することなく、必要な場合、当該コンピュータへ必要なハードウェア演算回路を組み込み、従来のハードウェア、ソフトウェア整列演算回路のどれよりも高速な整列演算装置で、合理的な費用で実現できるものを提供することを目的としている。
【０００４】
データを整列させることの基本はデータの大小関係を判別して、そのデータを小さい順、または大きい順にならべるものであり、従来の整列方法は個々のデータ列（レコード）を比較することにより、各レコード間の大小関係を版定し、その結果にもとづき、比較したデータを相互に置換することを基本としており「クイックソート」と呼ばれるものが一般的に使用されている。「クイックソート」は多くのデータ整列に使用されており、他の整列方法に比べ優れた整列方法として認識されている。
【０００５】
「クイックソート」等のレコードの比較と置換をアルゴリズムの基本とするものは、通常のコンピュータと別の演算装置を用意し、高速化しようとしても、高速にならないか、とても大掛かりなハードウェアになり（例えば、特許文献１参照）、実用性にかけることとなる。その理由は「クイックソート」の場合ランダムな１００万レコードのデータを整列する場合約２千５００万回の比較と５００万回の置換が実施され、処理時間の９０％以上はその比較処理と置換処理についやされている。ＣＰＵとは別の付加演算装置において高速化を実施するとしても、同一のアルゴリズムを使用する限りでは、この回数の比較と置換のための記憶装置へのアクセスは必要であり、通常のＣＰＵは、個々の比較、置換処理は効果的に実施されており、高価な高速アクセスのメモリを大量に使用するといった方法でもとらない限り、当該ＣＰＵで機械語でかかれた整列プログラムの実行速度より、大幅に速い性能をだすことは難しい。また、先の例で示した整列方法は、データを並列に比較置換するハードウェアであるが、１００万件１０００万件の整列を合理的な費用で効果的に実施できると考えることはできない。
【０００６】
これらの「クイックソート」等の従来技術が、本質的に技術的な欠陥をもっているわけではなく、実用的である。しかしながら、ここ数年のコンピュータアプリケーションの進展は目覚しいものがあり、特に、コンピュータの主記憶となるＣＭＯＳ　ＲＡＭ（半導体ランダム・アクセス・メモリー）、主たる外部記憶装置であるハードディスクの価格の低減は著しいものがあり、その結果として、コンピュータが同時に処理しようとするデータ量が飛躍的に増大している。そのために、整列するデータの量として、数千万件規模のレコードを扱うこともまれでなくなっている。こうした環境のもとで、指摘される従来技術の問題点は整列対象レコードの数が増加するに従い、整列に要する時間がレコード数の増加に比例する以上に増加することである。整列方法の評価は、２つのレコードの大小を比較する比較操作、そのレコードを入れ替える置換操作の数を評価することで実施される。「クイックソート」の場合、整列対象のレコードがランダムな値を保有している場合で、レコード数が、１０００件の場合、１レコードあたり１１．５回の比較と２．５回の置換が実施されるが、１００万件の場合、それぞれ、２５．４回、４．７回に増加する。「クイックソート」以外のものではこの傾向はさらに顕著である。すなわち、従来の技術を使用した場合の問題点を記述すると、どのアルゴリズムを使用しても、データの件数が１０倍となると、１０倍を大幅に超える演算時間が必要となり、すなわち、データの数が多くなればなるほど、実行処理速度（演算処理時間／データ量）が低下する傾向にあり、また、初期のデータの並びかたで計算所用時間の予測ができない場合が発生するなどの問題を引き起こす。これらの問題点は近年の、増大したデータの整列処理を実施するときに特に問題である。
【０００７】
次に、従来技術のもうひとつの問題を示す。それは整列という処理が完全に完了するまで、整列の結果を他の処理に適用できないことである。一般的に整列処理は、整列終了後、最も小さな値のデータから別の処理を実行したりする。最も多く使用される索引処理がそうである。また、整列結果を磁気ディスク等の外部記憶装置に保存することも、しばしば行われる。整列結果を整列終了後まで使用できないという問題は、単一ＣＰＵのコンピュータで、内部処理のために整列操作を実行する場合は、早く結果を利用するためのリソースが存在しないので顕著な問題とならないが、外部記憶装置に整列結果を出力する場合、２つ以上のＣＰＵを保有する場合、または、外部の付加演算回路で整列を実行した場合などは、ＣＰＵとして、整列結果を使用するリソースを保有しているにも拘わらず、整列処理終了まで次の処理を開始することができない。整列処理が終了する以前の最も小さなレコードまたは大きなレコードとして保証されたデータを、待機中のＣＰＵまたは、外部記憶装置に渡すことができれば、並行的な処理が、実行できるので、実質的な整列時間は最初のレコードを確定する馬での時間となり、通常、数マイクロ秒のオーダで、実質的に０と評価することができる。
【０００８】
【特許文献１】
米国特許第５２６５２６０号明細書
【０００９】
【発明が解決しようとする課題】
本発明の課題は、コンピュータにおいて一般的に使用されている「クイックソート」等の従来技術より高速、具体的には、１０から５０倍程度の画期的な整列性能を実現する。必要な場合ＣＰＵとは別に動作する整列装置を提供し、増大したデータ容量のもとでも、短時間に整列を実現することである。また、その整列の処理時間は、処理量に比例するだけであり、処理量の増大による効率の低下をもたらさない。また、整列の完了以前においても、最少レコード、または最大レコードから順次外部出力することを可能とし、他のコンピュータＣＰＵを含む他の演算処理装置との並列処理を可能とする。
【００１０】
【課題を解決するための手段】
従来技術より数十パーセントの性能を実現することが目標の場合、整列と置換の数を減少させることが基本となる。しかし、１０倍以上の性能を実現するには、全く異なった原理を採用しなくてはならない。その原理選択の基本は、被整列対象レコード集合へのアクセス回数を最小とすることである。クイックソートでは、被整列対象レコード集合へのアクセスは１００万レコードの集合の場合少なくとも５０００万回のアクセスを実行している。
【００１１】
本発明は、基数法と呼ばれる基本アルゴリズムを採用している。このアルゴリズムはデジタルコンピュータ以前の時代に、十進法ともよく適合し、人間の直感とも直接的に適合するため人々が数字を整列する場合、暗黙に使用する方法であり、数千年もの歴史を保有するものであると考えられる。コンピュータが普及する時代となり、この方法を人間の直感を利用しないでコンピュータに実装する場合、プログラムが複雑となり、使用する記憶領域も多く、高速でもないところから当初より、プログラマからは見捨てられた存在となっていた。しかしながら、人間が直感的に使用していたということは、本質的には手順が少ないのであり、それが、上手に実装された場合、画期的な性能を提供する可能性が存在する。
【００１２】
この原理の解説をする。３桁の十進数が書いてあるカードが数十枚存在し、目的はそのカードを小さい順に並べることである。この場合、実行者は、まず、カードの百の位の値（百の位の値が無いカードは０として）だけをみて、同じ値のカード毎に、テーブルの上に置いていく。すると最大で１０個のグループができる。次に実行者は０または、０のグループが存在しない場合は最小の値を持つグループのカードだけ取り出して、同様に１０の位の値をベースにテーブルの別のところにグループをつくる。また、新たに作ったグループの集合のなかの最小の値を持つグループのカードをとりだして、テーブルの別のところに１の位の数値を基本にして新しいグループを作る。ここで、同じグループが複数枚あった場合は、その複数枚のカードの値は同じである。従って最後に作成したグループの集合の最も小さい数値グループのカードから順番に集めていけば、そのカードは小さい順に並んでいることとなる。カードのグループ化はいつも１の位までやるとは限らず、もし、１０の位のグループ化で１枚しかカードが無い場合は、当然、１の位の値を見るまでもなく、そのカードがどこに位置するかが確定している。こうして、１００の位のグループの集合で最大値のグループのカードの処理が完了した時点でカードは全て整列されている。
【００１３】
この方法の驚くべきことは、整列者は、カード上の数値をカードを整列するのに必要な桁以上の数値が、仮にカードに書かれていても、それを読んでいないのである。例えば１００以下のカードが一枚しかなく、その値は３４であった場合、実行者は３４という数字を読むまでもなく、認識する必要がないのである。従って３桁×枚数分の数字の認識さえする必要はないのである。もうひとつの驚くべきことは、カードの数値の桁の同じ場所を複数回読むことは決してないのである。従って最大でも、３桁×枚数分の数字を認識するだけである。
【００１４】
次に数が４桁のカード２０００枚の整列を考えることとする。実行者はさらに能率的に実施することを考えた。テーブルでは手狭になるので、１０行１０列の棚で、そこに０から９９までの番号をふったものを二組用意し、全てのカードについて最初は千の位と百の位の数値を読んで該当する棚にいれる。次は、カードの入っている棚で一番小さい番号のものからカードを引き出し、１０の位と１の位の数値を用いて、もう一つの用意された棚にいれる。前回と同様にこれでカードが整列されることはよくわかる。この場合、４桁の数を２桁ずつまとめて読み、棚に入れるという操作をするので、カード１枚あたりのカードを見る回数は、前回の１桁づつみることに比べ半分になることとなる。即ち、一度に認識する数が多ければ多いほど、カードを見る回数は少なくなる。
【００１５】
人間の場合、常人は精々２０以下、訓練された人で１００位の分解ができるだけであるが、コンピュータや仕分機等の機械となった場合、これを極めて大きな値にとることができる。原理的には無限大（扱う数値の最大を超える値）の分解をサポートした場合は、どんなデータでも一回参照するだけで、整列できることとなる。
【００１６】
人間は、空間的な位置、カードを置く場所、棚にカードがあるか、ないか、ということを、一瞬に判断し、特に判断のための特別な手段を必要としない。一方機械の場合、それらを認識することができないので、光センサで棚にカードがあるかないかを判定し、空でない棚をすぐに見つける機構等が必要となる。
【００１７】
この方式は、とにかく、もとのデータは１回以上参照しない。分類の不必要な情報も参照しないという原理的な特徴を保有している。しかしながら、この原理は実装上の致命的とも言える問題を保有している。それは、データ（たとえばカード）を保管する「棚」が、データのサイズが大きい場合、例えば４０桁もある文字の場合、最大４０個の「棚のセット」を必要とし、さらに、その棚には最悪の場合、すべてのデータ（カード）が入る容量を必要とするので、こうした、実装上の重大欠陥への対処が必要で、また、その「棚のセット」を管理するために多大なリソースの処理と管理のオーバヘッドが存在する。このように、この方式を実装するためには「棚が必要である」、「光センサが必要である」といった、一般的には致命的と思われる付加的な作業が多数存在する。しかし、付加的な作業の存在は、それが、新しい演算装置として設計された場合、データアクセスという基本操作と並列に実行される可能性を保有するもので、もし、最も合理的に処理を組み合わせた場合、データのアクセスの実行時間内に、その付加処理が並列になされることが可能であるならば、原理的にアクセス回数が少ないという方式の利益が最大限提供されることは明らかであり、本発明はそれが可能である事を実証した。即ち、対象とするデータを一回アクセスするだけの時間で、整列操作を完了させることができる方法である。
【００１８】
【発明の実施の形態】
本発明は、基数整列法を原理とする整列方法である。
本発明の定義を示す。ワードは原理的には１以上の数値で、実用的な性能を実現するためには８以上の数値であるＮを用い、Ｎビットで構成されるデータの単位である。レコード数の少ない装置ではＮ＝８が一般的であり、通常の場合はＮ＝１６であり、国や大企業の使用するコンピュータではＮ＝２０、Ｎ＝２４が採用されることがある。この数値は関連して動作するコンピュータのワード長と直接的な関連はないが、３２ビットワードの一般的なコンピュータとはＮ＝１６が相性がよい。Ｎ＝２４の場合は整列対象数値が０以上、２の２４乗マイナス１（１６７７７２１５）以下の場合は、各レコードを一回アクセスするだけで整列を終了させることができる。
【００１９】
本発明ではＮが１意のように記述されているが、必ずしも１つの数値に限定されるわけではない。たとえば、６４ビットコンピュータ用に２０，２０、２４の合計６４ビットとして、レベル毎にことなったＮを採用することも可能である。
レコードはワードの集合であり、被整列データ集合の１要素である。大きなデータベースでは合計で数キロビットのレコード長となる場合もある。処理上はレコードは複数ワードよりなりたつと考える。１レコードを構成するワード数は、整列装置がサポートするレベル数Ｍとなる。ワード数ＭはＭ桁の数値と等価な意味を保有しており、レベルとは、棚に区分けする時に参照するワード（桁）を現している。また、同時に、レベルとは、区分けに使用する棚のセットを指定している。レベルが高いということは、後順位で使用される棚に相当する意味を保有している。原理上、棚のセットは桁数即ちワード数より多くを必要としない。実際のデータベースのレコードでは、レコードサイズが大きくとも、整列に使用するキー・ワードはわずかなことが多く、その場合は整列に使用するキー・ワードの数がＭとなる。
【００２０】
本発明の構成要素を示す。その１は記憶回路Ａと呼ばれるもので、整列の対象のレコードの集合が記憶された回路であり、ＲＡＭ（ランダムアクセスメモリー）である。これは、対応コンピュータの主記憶ＲＡＭであってもよいし、演算回路がアクセスする専用記憶回路であってもよい。この記憶回路の大きさは大きなデータベースシステムの場合、数ギガバイトという容量を保有することもある。
【００２１】
次は、記憶回路Ｂと呼ばれるもので、その実体は、先の原理の説明における棚である。この記憶装置も通常はＲＡＭであるが、先ＦＩＦＯ（先入出）、ＬＩＦＯ（後入先出）メモリ等であっても構わない。棚であるので、記憶されたものが最終的に取り出されることが実現される必要がある。この記憶回路Ｂに記憶されるデータは、多くの場合、レコードの位置を示すアドレス（メモリポインタ）かレコードの番号、レコードの位置のデータベースの先頭からの相対バイトアドレス等のレコード認識データ（レコードを一意に特定する数値であり、その数値から容易にレコードの保管番地を計算し、かつ、レコードが保有するデータを参照可能とする数値）である。レコードの総ビット数がこの記憶回路Ｂのワード長より小さい場合、被整列データそのものをいれることができる。記憶回路Ｂのビットサイズはメモリポインタを入れる十分なサイズであり、通常は３２ビットである。この記憶回路Ｂは２のＮ乗個の棚に相当する記憶ユニット、Ｍ組を構成する。また、一つの記憶ユニットは最大レコードの個数分のレコード認識データを格納できなくてはならない。従って、この回路をＦＩＦＯ等の特殊なメモリで必要な仕様を満たした静的な記憶回路とすることもできるが、大きなコストとなるので、通常、安価なＣＭＯＳ　ＲＡＭを用いて動的な構成として実現する。その場合は動的な構成を管理する記憶回路として、記憶回路Ｃを必要とする。この記憶回路Ｂの大きさは、整列対象集合のレコード数分の大きさが必要であり、仮に１００万件分の整列を実行しようとした場合、４ＭＢ程度の容量を必要とする。
【００２２】
次に記憶回路Ｃと呼ばれるものである。記憶回路Ｂが静的なものであれば、記憶回路Ｃは必要としない。しかし、通常静的記憶回路のコストは莫大なものであり、多くの場合動的に構成されるので、ユニットの番号（棚の番号）、レベル（桁）、次の認識データを保管する記憶回路Ｂのアドレス、次に認識データを取り出す記憶回路Ｂのアドレス等を管理する記憶回路が必要となり、これを記憶回路Ｃと呼び、通常ＲＡＭで構成させる。この記憶回路の容量は２のＮ乗の数倍であり、上手に構成した場合は、３２ビット（４バイト）のポインタを構成するものとして、Ｎ＝１６の場合で２の１６乗×４＝２５６キロバイトで構成することができる。安定整列、即ち、整列の結果、同一の整列キーの値を保有するレコードの相対順位が、整列前と整列後に変化のない整列を実現する場合は、最小値を超えた記憶回路Ｂの容量を必要とする。
【００２３】
次の構成要素は、記憶回路Ｄと呼ばれるものである。この記憶回路は、ひとつのレベルのオペレーションに於いて複数のユニットにデータを格納する過程において、データが保管されたユニットがどれであるか特定するための記憶回路である。即ち、空でないユニットを認識することに関連した回路である。レベルの高いオペレーションでは一つのユニットオペレーション（棚入れ）で扱われる認識データが２または３個ということが続く、その場合数万から数百万あるユニットからデータが保管されているユニットを全部探索すると仮定した場合、それは膨大な処理時間を消費する。従って、記憶回路Ｄと、そのデータを処理する演算回路を必要とする。この記憶回路はＭ組必要であり、各組の容量は２Ｎ乗ビット＋アルファを必要とする。Ｎ＝１６の場合、８キロバイト強の容量を各レベル毎に必要とする。
【００２４】
実用的には全ての記憶回路はＲＡＭで構成される。本発明の根本となることは、全体の処理がＡ、Ｂ、Ｃ、Ｄの複数のＲＡＭの処理に分解され、この記憶回路を操作する演算回路は、同時並列的動作、即ち、処理事体は逐次処理であるが、その処理を１リソースへの内部処理分遅らせた、後続処理（複数）を並行に実行させることにより、１リソースの処理時間内にあたかも、全ての処理が完了させていると同等の処理性能を導出するパイプライン並列処理と呼ばれる動作を実行している。アクセス回数の多い操作は記憶回路ＣとＤに関連した操作である。しかし幸いなことに、その容量は大変小さい。従って、高速アクセスタイムのスタティックメモリを使用しても、コスト面、ハードウェアの実装面においても何ら問題を生じない。勿論、演算装置を構成する高集積半導体の内部に実装することも可能である。記憶回路Ａ、Ｂは通常大容量となるのでダイナミックメモリで構成されることが多い。整列の性能上はこれらの記憶回路は、並列操作（アクセス操作）することが可能な物理的な別のメモリとして構成することが望ましい。しかし、同一の物理メモリ上に構成することを妨げるものではない。これは、すべての記憶回路についていえるもので、物理的に並列であれば、より高速な処理が可能となるのであって、Ａ、Ｂ、Ｃ、Ｄ全ての記憶回路を共同動作するコンピュータのＣＰＵの主記憶回路中に構成することを妨げていない。従って、演算回路が、Ａ、Ｂ、Ｃ、Ｄの記憶回路を物理的に別個の記憶回路として保有し、とくに、Ｃ、Ｄの記憶回路に高速アクセスメモリを採用した場合、最も早い整列処理が可能となる。
【００２５】
次に、演算装置の個々の要素回路を記述する。記憶回路Ｄをコントロールする演算回路Ａを示す。この回路はデータの登録時に、レベル、使用されたユニット番号を与えられると、その内容を記憶回路Ｄに記憶させる。データの呼びだし時には、記憶回路Ｄの情報をもとにして、登録された番号、即ち、認識データを保有する記憶ユニットで最も小さいユニットの番号を準備している。
【００２６】
つぎに記憶回路Ｂを認識データの保管回路として動的に操作する演算回路Ｂを必要とする。この回路はレベル、ユニット番号が与えられた場合、記憶回路Ｃ情報をもとにして、保管すべきまたは引出すべき認識データの記録または読み出しのための記憶回路Ｂのアドレスを生成する。
【００２７】
次に出力回路と呼ばれる演算回路Ｃが存在する。この回路は、整列が確定したレコードの認識データ、または、レコードを当該認識データをもとに、外部の処理回路と共有する記憶回路に掃き出す処理を実施する。
次の演算回路Ｄは主制御回路と呼ばれるもので以下の初期動作、再起動作と呼ばれる演算の制御を実行する。
【００２８】
初期動作は記憶回路Ａのレコードデータを通常先頭から、レコード番号、または、レコードの先頭アドレスをレコード認識データとしながら、レコード中最も上位のワード（桁）順に呼び出し、レベル０のユニットセット（棚）の上位ワードの数値のユニットＩＤの格納ユニットへレコード認識データを保管するように、ユニットＩＤ、レベル、認識データを演算回路Ｂへ渡す。これを全てのレコードについて終了するまで実行する。この初期動作は、外部の装置から、記憶回路Ａへレコードの集合が送られてくる時に、拡張された演算回路Ｄを経由する場合、全てのレコードが記憶装置Ａに保管される前に演算回路Ｂに必要なデータを渡すことができる。その場合、より複雑な演算回路を必要とするが、初期動作とレコードの演算装置Ａへの読み込み動作を並列に実行することができるので、初期動作の時間をデータを読み込む時間の中に隠すことができる。
【００２９】
再帰動作とは、この前に実行された、初期動作または再帰動作のレベルに１を加えたレベルにおいて（次のレベルの棚を使用することと同じ）、演算回路Ａから前回レベルで格納された最も小さい値を引き出し、そのユニット番号の値を使用し、そのユニットＩＤの格納ユニットから保管されている認識データの読み出しを演算回路Ｂに指示し、その認識データを得る。それを、順次実行し、読み出しのデータ数が１の場合、または、最終レベル（これ以上参照するワードが存在しないレベル）の場合その認識データを演算回路Ｃへ送り、次に小さな値を保有するユニットで同様な処理を継続すべく処理を進め、データ数が２以上の場合、その読み出した全ての認識データの指すレコードについて、次のレベルに該当するワードを記憶回路Ａより読みだし、その値を演算回路Ａに与え、また、演算回路Ｂのその値をユニットＩＤとする格納ユニットへ、当該認識データを保管するよう、記憶回路Ｂへ情報を渡す。読み出したすべての認識データの再保管後、再帰動作を起動し、最終的に最も大きなユニット番号まで、同様な動作を実行して終了し、当該再帰動作を呼出した動作が再帰動作であるなら、呼び出し再帰動作の直後の処理へ制御を移し、呼び出し動作が初期動作であれば終了とする動作である。
【００３０】
本発明における整列演算操作は、演算回路Ｄの初期動作、および再帰動作において実行される。
本発明は、本発明における整列演算装置を複数個用意し、その全体を制御する制御回路を加え、全体として並列整列演算装置を構成することを妨げない。
【００３１】
（実施例）
本実施例は記憶回路Ａ、Ｂを別に保有し、記憶回路Ｃ、ＤはＣＤを同一の物理メモリに展開をした。記憶回路Ａは１２８ＭＢ３２ビット幅のダイナミックメモリである。記憶回路Ｂは１６ＭＢ３２ビット幅の同じくダイナミックメモリで、高速ページモードアクセスが可能なものである。このダイナミックメモリはアクセスタイムが６０ｎｓ、サイクルタイムが８０ｎｓである。記憶回路Ｃ、Ｄはアクセスタイム１５ｎｓの高速スタティックメモリで１ＭＢ３２ビット幅である。演算処理回路には約５００００ゲートのＦＰＧＡ（フィールド・プログラマブル・ゲートアレー）をクロック６６Ｍｈｚで動作をさせた。この構成において、総レコード数で約４００万、最大ワード数で３２（６４バイト）のデータの整列が可能である。この整列装置全体はＰＣＩローカルバスボードとして実装されており、ＰＣＩローカルバスを保有するどのようなコンピュータへも実装可能であり、実装することにより、当該コンピュータの整列性能を飛躍的に向上させるものである。この構成はパーソナルコンピュータ用には高価であるが、処理性能を必要とするサーバシステム用には十分安価な構成である。尚この実施例のＮは１６である。
【００３２】
全体の構成図を図１に示す。全体の動作を示す。ホストコンピュータは先ず、当該回路に対し、回路の初期化命令をＦＰＧＡに発行する。次に、ＰＣＩローカルバス経由で直接記憶回路Ａに整列対象レコード集合をロードする。通常このロード時間中に整列回路の初期化は終了しているので、初期化時間は整列の処理時間へは加わらない。
【００３３】
本実施例では、初期動作をロード時間中に重複して、完了させるモードを保有しているが、本実施例の説明としては、本発明の内容を、より明確にするために、記憶回路Ａへのロード後に初期動作を開始するモードについて説明する。当該モードにおいては、ロード操作が完了後、ホストコンピュータはＦＰＧＡに必要なパラメータとともに、整列の実行コマンドを発行する。ＦＰＧＡは整列動作を開始し、通常、初期動作をしている時は外部にいかなる動作も発行しない。この時間は、通常、１００ｎｓにレコード数を掛けた時間である。再帰動作が開始されると、整列結果が順次確定するので、確定し次第、ＦＰＧＡはＤＭＡ（ダイレクトメモリアクセス）転送を使用して、ＰＣＩバス経由でホストコンピュータの記憶回路に整列結果を転送する。最終的に全てのレコードをＤＭＡ転送して、整列処理は終了する。
【００３４】
次に本実施例で実装した構成における演算回路Ａを示す。演算回路Ａのデータ構造は２個の３２ビットメモリ（Ｈマップ）、６４個の３２ビットメモリ（Ｍマップ）、２０４８個の３２ビットメモリ（Ｌマップ）の組、３２組（レベルに対応）を記憶回路Ｄに作成している。通常のオペレーションでは、最大二組しか同時に動作しないので、動作中のＨマップのコピーをＦＰＧＡの６４ビット内部レジスタとして保有している。このメモリは初期化動作で全て０クリアされている。
【００３５】
演算回路Ａの第１の機能は１６ビットのユニットＩＤを与えられた時、それを登録することである。この機能は、初期動作、再帰動作において、記憶回路Ａよりデータを読み出して、そのレコード認識データを記憶回路Ｂへ書き込むときに実施される。演算回路Ａが操作の対象とする記憶回路は記憶回路ＣＤである。登録は対象１につき、３個の記憶回路ブロックを必要とする。それぞれ、Ｈマップ、Ｍマップ、Ｌマップと呼ばれるものである。この記憶回路は対象データのワード数分の組を必要とする。１６ビットの数値ｘが与えられた場合、この値を上位の１１ビット値ｐ、下位５ビットｑに分解する。ｑはデコード演算を実施し３２ビットのデータｒを生成する。Ｌマップメモリのｐ番地の３２ビットデータを呼び出し、ｒと論理和をとり、再度同一番地へ保管する。つぎにｐを上位６ビットｓ下位５ビットｔに分解する。ｔは同様にデコード処理され３２ビット値ｕとなり、Ｍマップのｓ番地のメモリにＬマップと同様な処理をする。次にＳを上位１ビットｖと下位５ビットｗに分解し、ｗをデコードし、同様な処理をＨマップに対して実行する。実際にはＨマップの処理はＦＰＧＡ中のコピーレジスタに対し実行されるので、記憶回路への待避が必要な場合を除いて実際のメモリアクセスは発生しない。従ってこの操作に要する処理時間は、４回のメモリアクセス時間であり、約６０ｎｓである。この処理が繰り返されることにより、Ｈ、Ｍ、Ｌの各マップにどのユニットＩＤが使用されたかという情報が格納される。
【００３６】
演算回路Ａの第２の機能は、保管されている最も小さいユニットＩＤの番号を見つけることである。このロジックの実際の処理は、使用済みビットのクリア処理が入るので多少複雑であるが、原理となるロジックを図２に示す。Ｈマップ、Ｍマップ、Ｌマップのそれぞれの、ｉを数値とするｉ番地の値はｈｍａｐ［ｉ］、ｍｍａｐ［ｉ］、ｌｍａｐ［ｉ］である。またＥＮＣＯＤＥ（ｄａｔａ）はエンコード演算操作で３２ビットデータｄａｔａのビットが１である最下位のビットの位置を示す値を導く関数である。ａ、ｂ、ｃ、ｄは最少ユニットＩＤを構成する１６ビットデータの最上位ビット、１１から１５ビット、６から１０ビット、１から５ビットの値であり、（ａ＋＋ｂ）という表現は加算ではなく、ａのデータビットとｂのデータビットを連結したビットデータである。従って、（ａ＋＋ｂ＋＋ｃ＋＋ｄ）は最小のユニットＩＤのビット列でその値を示している。最小ユニットＩＤの操作後に、該当するＬマップのビットをクリアしておけば、同様な操作で、次に小さいユニットＩＤを計算することができる。Ｈマップのコピーが内部レジスタに存在するとすれば、２回のメモリアクセスで即ち３０ｎｓで最小のユニットＩＤを確認できる。
【００３７】
レコード認識データを格納する記憶ユニットの実装には様々な方式があるが、本実施例では、記憶回路Ｃの使用量が最も小さいＬＩＦＯ（ラストイン、ファーストアウト）方式の記憶回路を採用した。この方式はレベル毎に必要となる記憶回路Ｂのアドレスを管理するユニットを、レベル数分持つのではなく、一つのユニットに代表させて保有する方式であり、レベル数分のユニットを保有する代わりに、記憶回路Ｂへ格納する認識データにレベル認識のマーク（本実施例では５ビットの情報）を付加することにより実現した。動的な管理ユニットを実現するために、記憶回路Ｂは１６ワードを１ブロックとし、ブロック単位に、管理ユニットの個々のユニットＩＤに連結するという方式を用いた。１ブロックは番地１から１５までのデータエリアと番地０の連結情報エリアからなりたっている。連結情報エリアには、当該ブロックの前に連結しているブロックの番号を記録している。データを格納する場合は、データエリアの１番地から１５番地へと順位データを格納し、１５番地を超えるデータエリアが必要な場合、空いているブロックのアドレスを獲得し、その０番地に先のブロックの１５番地の記憶回路Ｂのアドレスを書き込み、その後１番地から同様に書きこむ。このようにして、記憶回路Ｂのすべてのブロックを使いきるまで、データエリアへデータを大きい方から順次小さい方へと呼び出し、ブロックの０番地に到達したら、０番地の値を保有するブロックのアドレスを取得し、その連結するブロック番号の１５番地のデータを読みだせばよいことになる。
【００３８】
記憶回路Ｃの構造を説明する。記憶回路Ｃは３２ビット長のワード６５５３６＋１個によってなりたっている。この６５５３６値は００００００００００００００００から１１１１１１１１１１１１１１１１までの１６ビットの全ての値に対応するものである。従って、２０番地のデータはユニットＩＤ２０のデータに相当する。この記憶回路に記憶されているものは、当該ユニットで次に保管されるべき認識データの記憶回路Ｂ中のアドレスが格納されている。この値はデータがユニットに保管されている場合は、次の呼出される認識データのアドレスに１を加えたアドレスを意味している。記憶回路Ｃの各ワードは初期化動作中、初期値として、アドレスＰには、Ｐ×１６＋１の値が保管される。この値は、各ユニットに当初動的に連結された６５５３６個の記憶回路Ｂのブロックのアドレスであり、各ブロックの最初に認識データを格納すべきブロック内のアドレスが１であるところの、記憶回路Ｂのアドレスを指している。この値はユニットに固有の値であるので、その値とユニットＩＤの比較値を使用することにより、ブロックの次に連結するブロックが存在しないことが認識され、ブロックの認識データがすべて呼出され、空である状態を認識することができる。
【００３９】
６５５３７番目のユニットはＡＵＸユニットと呼ばれる特殊なユニットを構成している。このユニットは、再帰動作中、ユニットＩＤ　Ｘに格納されている認識データを読み出し、次のレベルの様々なユニットＩＤの記憶エリアに認識データを書き出す際、ユニット管理のための、管理アドレスデータの記憶回路（記憶回路Ｃ）を１組しか保有していないため、読み出しユニット番号と保管のユニット番号が同一の値の場合、当該ユニットの記憶回路Ｃの管理アドレスデータが読み出し用のポインタとして占有されているため、当該ユニットへの保管動作が不能となるので、読み出しユニットと同一のユニットＩＤへの保管が発生した場合、その認識データが替わりに保管されるユニットである。ＡＵＸユニットに保管された認識データは、当該ユニットＩＤの読み出しが終了した時に、本来のユニットＩＤの記憶ユニットへ複写される。このための処理時間は全く問題にならない。この複写が発生するのはＮ＝１６の場合で１６ビットの同一のデータが２回連続した場合のみであり、その確率はきわめて小さい。
【００４０】
尚、記憶回路Ｃには、３２ビット×６４のブロック管理用のメモリが存在している。ブロック管理は演算回路Ｂ中の未使用のブロックの番地を指すデータを保有する３２ビットのカウンタ（実際には上位２８ビットがカウンタで、下位４ビットはいつも０である。ニューブロックカウンタ＝ＮＢＣ）、ブロック管理用メモリのポインタ用のレジスタ（ブロック管理レジスタ＝ＢＰＲ）を保有している。ＢＰＲは使用済みとなったブロック番号がブロック管理メモリに登録される際、その最後の登録アドレスを保有している。この回路は次の２つの機能を保有する。その一つは、認識データをユニットに保管する際、当該ユニットに与えられた記憶回路Ｂ中にある動的ブロックにデータが満杯になったとき、即ち、ブロックの１５番地まで、認識データが記録されたとき、呼びだされ、使用済みブロックが無い場合はＮＢＣの値を次のブロックとして渡し、ＮＢＣを１インクリメントする。もう一つの機能は、ユニットから認識データを読み出す際、全てのブロック内のデータを呼出したとき、即ち、ブロックの１番地の認識データを読み出した後で、０番地の連結するブロックのアドレスを取得した時、このブロックは、データの読み出しがすべて完了し、使用済みとなり、ＢＰＲを１インクリメントし、その使用済みブロックのブロック番号を、ＢＰＲの示す、記憶回路Ｃに保管する。但しＢＰＲは６３以上の値とはならない。ＢＰＲが６３の場合、当該ブロックの番号は廃棄される。再帰動作の過程で「使用済みブロック」の登録と、再利用が頻繁に実施される。通常ブロックを最も消費している瞬間は、初期動作の終了後である。その後再帰動作が進展するにつれ、廃棄ブロックが生成される。６４個が再利用可能なブロックを全て使用し、ニューブロックを要求することは、２の１００乗分の１よりも低い確率でしか発生しないし、その場合も１、２のニューブロックが新たに消費されるだけである。
【００４１】
演算回路Ｂの基本的な機能は、演算回路Ｃより要求されて、指定されたレベルの、指定されたユニットＩＤを保有する格納ユニットに認識データを保管することである。また、指定されたレベルの指定されたユニットＩＤを保有する格納ユニットから認識データを呼出すことであり、また、格納ユニットに認識データが無いことを、演算回路Ｃへ返すことである。図３に認識データの保管処理を示す。また、図４に認識データの読み出し処理を示す。図３、図４の処理は基本の処理を示している。図中、それぞれ、ｌｖは当該初期動作、再帰動作時のレベル、ｉｄはユニットＩＤであり、ＡＵＸユニットを含め０から１００００（１６進数）までの値を保有するもの、ｄａｔａはレコード認識データ、Ｂ＿ｌ［ａｄｄｒ］は記憶回路Ｂのａｄｄｒ番地のデータの上位５ビット、Ｂ＿ｄ［ａｄｄｒ］は記憶回路Ｂのａｄｄｒ番地のデータの下位２７ビット、ｂｌｋ、ｂｌｋ＿ｔｍｐはブロックの番号、ｉはブロック内のアドレスで０から１５までの値、Ｃ＿ｉ［ｉｄ］は記憶回路Ｃのｉｄ番地の下位４ビット、Ｃ＿ｂ［ｉ］は記憶回路Ｃのｉｄ番地の上位の２８ビット（上位５ビットは０で有効２３ビット）、ｂｌｋ＿ｉｄはユニット番号固有の先頭ブロックのアドレスで初期化動作で設定されたもの、ＧＥＴＮＥＷＢＬＫ（）は新ブロック番号を取得する演算操作、ＲＴＮＢＬＫ（ｂｌｋ）は使用済みのｂｌｋブロックを返却する演算操作である。実施例では一回の呼出しごとに記憶回路Ｃのポインタを更新しているが、呼出しは同一ユニットＩＤの格納ユニットから呼出すことが保証されているので、高速化のため、実際の処理は呼出しの開始時に記憶回路Ｃから呼出し、当該ユニットＩＤの全ての認識データを読み出した時、記憶回路Ｃの値を更新している。従って保管処理では、通常、記憶回路Ｃへのアクセスが２回、記憶回路Ｂへのアクセスは１回となる。記憶回路Ｂへのアクセスは本実施例では単純なランダムアクセスサイクルとして、９０ｎｓで処理している。この回路にページキャッシュ機構を組み込み、通常２０４８ワードの同一ページ内のデータは８ないし、１６キャッシュされた時点で実際のメモリへの書き込みサイクルを実施すれば、平均して、４０ｎｓ程度の実行時間で、記憶回路Ｂへの書き込みが実行されるが、実際例ではこの機構は組み込まれていない。この機構は、ニューブロックを与える時に、再帰動作中可能な限り新規メモリブロックを与えることにより、容易に、良好なパフォーマンスを獲得することができる。１５回に一回記憶回路Ｂへのアクセスが一回余分に挿入される。読み出しの場合は基本的には、一回の記憶回路Ｂへのアクセスが一回余分に挿入される。読み出しの場合には基本的には、１回の記憶回路Ｂへのアクセスが行われる。同様に、１５回に一回、記憶回路Ｂへのアクセスが追加される。これとは別に同一ユニットＩＤの格納ユニットから読み出し処理をする前後に、各１回、計２回の記憶回路Ｃへのアクセスが実行される。呼出しの場合は連続番地のＲＡＭアクセスなので、通常３０ｎｓで処理が終了する。
【００４２】
演算回路Ｃは初期動作、および再帰動作という基本動作によってなりたっている。初期動作は、与えられたレコードの認識データ（実施例の場合は、レコードの格納される記憶回路Ａのアドレス）を、認識データが対象とするレコードの最上位のワード（１６ビット）のユニットＩＤを保有する格納ユニットに保管することである。再帰動作とは、初期動作で分類した、一つユニットＩＤに保管された、サブセットのレコード集合に対し、最上位ワードより下位のワードに従って、レベルを更新させながら再分類処理を実施する再帰的処理操作である。
【００４３】
初期動作の処理の内容を図５に示す。図中、それぞれ、ｗｌｖは保管用のレベル、ｒｌｖは読み出し用のレベル、ｉｄはユニットＩＤであり、ＡＵＸユニットを含め０から１００００（１６進数）までの値を保有するもの、ｄａｔａはレコード認識データ、ｄａｔａ［ｉ］は記憶回路Ａ中の該当レコードのｉ番目のワードの値、ｄａｔａ＿ｂａｓｅはレコード０、即ち、０番目のレコードの記憶回路Ａのアドレス、ｄａｔａ＿ｌａｓｔは最終レコードの記憶回路Ａのアドレス、ｗｎは１レコードのワード数、ＲＥＧＭＡＰ（ｌｖ、ｉｄ）はレベルｌｖの記憶回路Ｄに構成されたマップにたいしユニットｉｄを「データ在り」に登録する演算回路Ａの操作の呼出し命令、ＳＴＯＲＥ（ｌｖ、ｉｄ、ｄａｔａ）は記憶回路Ｂへの認識データｄａｔａの保管操作の呼出し命令（図３の機能処理）、ＬＯＡＤ（ｌｖ、ｉｄ）は記憶回路Ｂからの認識データｄａｔａの獲得操作の呼出し命令（図４の機能処理）である。初期動作はレコード集合のデータの読み取り、認識データを格納する処理であり、全ての演算回路のオペレーションを含めて、記憶回路Ａへのアクセスが１回（９０ｎｓ）、記憶回路Ｂへのアクセスが１回（９０ｎｓ）、記憶回路Ｃへのアクセスが２回（３０ｎｓ）、記憶回路Ｄへのアクセスが４回（６０ｎｓ）、が基本のループオペレーションであり、その他のオーバヘッドは精々この１０％以下である。記憶回路ＣＤは同一の物理記憶回路なので並列は不可能であるが、他は並列処理が可能であるので、実質的には初期動作の処理時間は９０ｎｓ×レコード数分である。
【００４４】
再帰動作の処理の内容を図６、図７に示す。図５で説明した変数、命令等は同一の意味を保有し、それに無いものは、それぞれ、ｗｌｖ＿ｌａｓｔは最終レベルで、データのワード数と同一の値、ｎｏ＿ｄａｔａは認識データが存在していないことを示すＬＯＡＤ命令からの特殊なでーた、ＯＵＴＰＵＴ（ｄａｔａ）はｄａｔａの示すレコードをＤＭＡ出力回路に送り出す命令、ＧＥＴＩＤ（ｌｖ）はレベルｌｖの最小のものからユニットＩＤ番号を次々取得するための演算回路Ａへの命令である。初期動作に比べると複雑となるが、基本ループは、格納ユニットから認識データを読み出し、そのデータを用いて、記憶回路Ａより該当ワードの値を読み出し、その値のユニットＩＤを保有する格納ユニットへ認識データを再保管することである。これは、初期動作に比べると、格納ユニットから読み出す処理が追加された処理となる。これはページモードオペレーションであり、約４０ｎｓなので、１３０ｎｓがレコード１あたりの処理時間となる。
【００４５】
【発明の効果】
本発明の原理自体は古くから人間が直感的に保有していたものである。コンピュータ・ソフトウェア・アルゴリズム理論としては基数法と呼ばれるものの一種であるが、一般的なソフトウェアの教科書では取り上げられていないか、取り上げられていたとしても、整列処理の現在の中心技術である「クイックソート」等の比較と置換を基本とする整列方法に替わって使われるものではないとされている。その理由は、現在のコンピュータ・アーキテクチャーの基本である、「フォン・ノイマン」アーキテクチャーが演算形式としては、ワード単位に処理し、ワード単位の比較、加算、減算、論理積、論理和などの単純な処理のみを保有し、また、キャッシュメモリのような、高速化のために補助メモリは許されているものの、基本的には主記憶だけを記憶回路として保有していることに起因しており、比較と置換の処理は、「フォン・ノイマン」アーキテクチャーが最も効率的に扱える処理であり、「クイックソート」はその最も洗練されたものとされている。
【００４６】
「クイックソート」、および、比較と置換を基本とする整列方法との関連の上で、本発明の位置を明確にする。先ず、整列の性能、整列に要する時間である。とりあえず１００万レコード、レコードの総サイズは６４ビット、総容量８ＭＢのダイナミックメモリにデータが格納されているとする。データはランダム数であり、通常３２ビットを調べることにより、整列が可能である。この場合、「クイックソート」は最も効率の良い性能を発揮し、約２５００万回の比較と５００万回の置換で処理は終了する。比較の処理はランダムアクセスであり、どのような方法を用いても１ワードアクセスに９０ｎｓかかる。したがって、比較の操作は、３２ビットを同時にアクセスできるものとして、最低でも１８０ｎｓとなる。置換の操作は二つの６４ビットデータを置換するのであるので最低４回のメモリアクセスが発生する。しかし同一レコードの２ワード目のアクセス時間は半分程度と見積もることができるので、合計２７０ｎｓ程度である。その所要時間はプログラム時間を一切無視するとして５．８５秒である。尚、ＰＥＮＴＩＵＭ（Ｒ）プロセッサ１２０ＭＨｚ、主記憶アクセスタイム６０ｎｓ、キャッシュメモリ２５６ＫＢのシステムにおける「クイックソート」の実測値は５．８秒である。最新の高性能コンピュータではキャッシュメモリの効果で、この理論値よりも若干早い数値を出すこともある。
【００４７】
本発明は、コンピュータの世界では一般的でない原理を導入し、整列対象レコードへのアクセスを最小にし、その他の、処理時間を、対象レコードのアクセス時間と並列に実行させ、あたかも、整列に必要なデータを読みこむだけの時間で整列を完了させる方法を提供している。このデータを対象とした場合、整列処理時間に外部からのデータの導入、外部への出力期間を含めないとすると、おおよそ、初期動作で１００万回の基本処理を実施し、上位３２ビットで整列の情報が提供されているとすると、同じく再帰動作１００万回の基本処理が実施され、その計算式は（９０＋１３０）ｘ１００万ｎｓであり、その時間は０．２２秒である。実測結果も同様で０．２５秒となっている。実施例２で実績値は０．５２秒となっている。この性能は、ギガバイトを超えているデータベースの索引処理、ネットワークで複数のクライアントからの要求を受けるデータベースサーバなどに画期的な性能を提供する。
【００４８】
本発明は、入出力動作とも並列性を実現することができる。「クイックソート」では、プロセッサが複数存在しようと、すべてのデータがワークエリアに存在してから開始され、整列が完了するまで、その結果を使用することはできない。本発明は、よく設計された場合、データの入力過程で基本動作を実施し、出力過程で再帰動作を実行することができ、本発明による装置にデータの入力操作の最後のレコードデータを渡して０．０００１秒後には、最も小さな値を次の処理システムに渡すことができる。この性能は、オンライン型のデータベース処理では、従来、最もＣＰＵ演算処理能力を消費していた整列演算の処理時間が実質的に零になる事を意味している。従って、現在事務処理用のコンピュータのＣＰＵ時間の大半が整列に使用されているが、そのための処理時間が単にデータの転送時間となることをいみしており、コンピュータの性能が数十倍向上したと同じ効果を発揮する。
【００４９】
現在、数百メガバイトのデータベースレコードを整列させることが日常的に実施されるようになっている。従来の技術はレコード数Ｎに対し、ＮｌｎＮに比例する実行時間が必要とされている。即ち、Ｎが大きくなればなるほど、１レコードあたりの整列時間が増加することを意味している。これは、メガバイト、ギガバイトのデータの整列には深刻な問題となっている。本発明は、データの分解可能な必要な情報だけへのアクセス時間に比例するものであり、基本的には整列時間に比例する。このことは、特に大きなデータベースデータの整列に有効である。
【００５０】
本発明による装置のコストに付いての評価を行う。本発明を実施する最低のハードウェアは演算処理を実施する半導体集積回路と、５１２ＫＢの高速スタティックメモリである。このコストは４ＭＢのダイナミックメモリのコストより易く、通常のパソコンに設置できる価格である。また、データベースソフトウェア等が、そのソフトウェアの性能を向上させるために、ソフトウェアの付属品として提供できる十分な価格妥当性を保有している。数百万円から数億円するデータベースシステムには、１２８メガバイトから１ギガバイトのメモリを実装した本発明による演算装置も、この性能向上分を他のＣＰＵ処理装置の増設によって賄うコスト、例えば並列演算システムのＣＰＵを複数増設することに比べると、はるかに低コストであり、十分な価格の妥当性を保有する。整列装置のコストの大部分を占めるものが半導体メモリの価格であり、現在では、必ずしも高価なものではない。
【図面の簡単な説明】
【図１】実施例の整列装置の基本構成。
【図２】最小ユニットＩＤを求めるための基本回路ロジック。
【図３】認識データの格納ユニットへのロジック。
【図４】格納ユニットからの認識データの読み出しのロジック。
【図５】初期動作の回路ロジック。
【図６】再帰動作の回路ロジック（その１）。
【図７】再帰動作の回路ロジック　（その２）。
【図１】
2004145619.tif 000003
【図２】
2004145619.tif 000004
【図３】
2004145619.tif 000005
【図４】
2004145619.tif 000006
【図５】
2004145619.tif 000007
【図６】
2004145619.tif 000008
【図７】
2004145619.tif 000009