(57)【要約】【課題】本発明の課題は、コンピュータの最も基本的な演算手段の一つのデータの整列方法について、最近の高速コンピュータの演算処理時間の一般的な整列時間を１０分の１から数分の位置に短縮する整列演算処理を、安価なハードウェア装置を用いて実現することである。【解決手段】課題を実現するため、安定ソートを多重に繰り返すという方式と、ＦＩＦＯユニットでデータを一時保管し、対象レコードの重複アクセスを避ける方式を用い、複数の論理的に異なるメモリ回路を使用する整列方法を実現し、少なくとも２以上の物理的に分離された、作業用の記憶回路を用い、その複数のメモリ回路へのアクセスを、パイプライン並列処理として実行し、最も時間を要する当該物理メモリ回路の時間内で処理を実行するパイプライン整列装置で、最終的には１ワードの処理時間を、一つのメモリ素子のサイクルタイムまで減少させることのできる高速整列装置を提供した。【選択図】　　図１
2004145620.tif 000002
【特許請求の範囲】
【請求項１】
４以上の数値Ｎを用い、Ｎビットの整数倍であるか、若しくは、複数のＮ以下の値のビット列の値の総和からなるレコードであり、そのＮビットを最大ビット列として、構成される単数、または、複数ビット列を整列のキー・フィールドとする、単数、または、複数フィールドからなるレコードを対象とする整列装置であり、複数の被整列対象レコードからなるレコードを対象とする整列装置であり、複数の被整列対象レコードを格納することのできる記憶回路、２のＮ乗個の、０から２のＮ乗―１の番号により区別がつけることができる記憶回路の集合であって、データのメモリポインタ、データの番号等のレコード認識情報、データ本体、若しくはレコード認識情報とデータの部分をなすビット列を整列途中で格納することができる読み出し用、書き込み用の２組みのＦＩＦＯ記憶回路、または、その他の出し入れ可能な記憶回路で、格納されたデータの順序を保存することができる回路であって、それを擬似的に実現する記憶回路を含む一時格納記憶回路と、必要に応じ、演算の操作の実行のために、補助的に設ける記憶回路で構成される記憶回路であり、それらの記憶回路が単にデータをキャッシングする等という、アクセスの改善のためのものでなく、独立した機能を保有するものであって、その記憶回路が少なくとも２組以上の物理的な記憶回路で構成されるものであって、その物理的な記憶回路へのアクセスが同時並行的に実現可能な記憶回路を保有し、さらに、それらの記憶回路間でデータを移動、変換する演算処理回路を保有することから成り立つデジタル演算装置で、内部演算処理として、２組以上の物理的記憶回路をアクセスする際の演算処理をパイプライン並列処理動作として実現するデジタル演算装置において、第１ステップとして、被整列対象レコード集合から、最も低位のキー・フィールドのデータを読み出し、そのデータの値と同一の番号を保有する書き込み用のＦＩＦＯ記憶回路に、当該レコードのレコード認識情報等を書き込み、それを、すべてのレコードに対し実施し、第２ステップとして、書き込み用のＦＩＦＯ記憶回路を読み出し用に設定し、読み出し用のＦＩＦＯ記憶回路を書き込み用に設定するという交換処理を実施し、昇順整列の場合は最も小さな番号、降順整列の場合は最も大きな番号を保有する一時格納記憶回路先のステップでレコード認識情報を書き込んだ、読み出し用ＦＩＦＯと設定されているＦＩＦＯ記憶回路から、レコード認識情報を読み出し、必要な場合、それを、レコードのメモリ位置情報に変換し、そのレコード中の次に低位のキー・フィールドの値を読み出し、そのデータの値と同一の番号を保有する一時格納記憶回路で、書き込み用のＦＩＦＯ記憶回路と設定されたものに、当該レコードのレコード認識情報を書き込み、それを、読み出し用のＦＩＦＯ記憶回路が空になるまで継続し、空となった場合、昇順の場合はより大きな番号、降順の場合はより小さな番号を保有するＦＩＦＯ記憶回路から読み出されるレコード認識番号に対し、同様な処理を実施し、最終的にすべての一時格納記憶回路で呼び出し用のＦＩＦＯ記憶回路が空になるまで継続し、第３ステップとして、第２ステップの操作を、レコード中の最高位のキー・フィールドの値を処理するまで継続し、第４ステップとして、第２ステップと同様な方法で読み出したレコード認識番号のレコードを、必要な出力装置、または、出力記憶エリアに掃き出すことによって終了するデータの高速整列装置。
【請求項２】
２のＮ乗組の、または２の（Ｎ＋１）乗組の、記憶回路の書き込み用のポインタ、読み出し用のポインタ、またはそれに相当する情報を格納する、記憶回路と、そのデータを処理する演算回路を加えることにより、単一アドレスを保有する通常記憶回路を、請求項１で示す、レコード認識情報等を格納するＦＩＦＯ機能を保有する一時格納記憶回路と擬似的にみなすことができる、請求項１の整列装置で、最終的に必要とする複数の被整列対象レコードを格納することのできる記憶回路、レコード認識情報等を格納するＦＩＦＯ機能を保有する通常記憶回路で実現された一時格納記憶回路およびそれを実現するための一時格納記憶回路への読み出しと書き込みのポインタを保有する記憶回路である３組みの記憶回路が、個々の記憶回路への読み出し、書き込みがパイプライン動作をし、３組みの記憶回路の動作時間の合計ではなく、実質的に一つの記憶回路の動作の処理時間で最大の処理時間を要する、３組みのうちの一つの記憶回路の処理時間で、一つのレコードに対する処理時間を終了させるところのデータの高速整列装置。
【請求項３】
４以上の整数Ｍをワード幅とする記憶回路であって、一組あたり２のＮ乗割るＭワードのワード数を保有する記憶回路２組みを保有し、さらに、その記憶回路に、その記憶回路の１ビットに一時格納記憶回路の番号、即ちキー・フィールドの値を対応させ、レコード認識データを保管する一時格納記憶回路の呼び出し時に、キー・フィールドのビットがセットされていない、即ち、空の一時格納記憶回路をスキップして読み出すことができる制御回路を保有している請求項１、または請求項２のデータの高速整列装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明はデジタルデータを整列するハードウェア演算装置及び方法に関するものである。
【０００２】
【従来の技術】
デジタルデータを整列することはコンピュータを利用するデジタルシステムにおいて、複数のデータから特定のデータを引き出すという極めて一般的なアプリケーションを実行させるための、必須のデータ処理であり、データを整列させることにより、すべてのデータを調べるのことなく、高速に目的のデータを参照することができる。
【０００３】
データを整列させることの基本はデータデータの大小関係を判別して、そのデータを小さい順、または大きい順にならべるものであり、従来の整列方法は個々のデータ列（レコード）を比較することにより、各レコード間の上下関係を判定し、その結果にもとずき、比較したデータを相互に置換することを基本としており、デジタル計算機の標準的なリソースで実施可能な多数の方法が提供されており、「クイックソート」と呼ばれるものが最も一般的である。また、そうしたアルゴリズムは、ハードウェア比較、置換回路を設けることを特徴とする専用整列ハードウェアにおいても実施されている（特許文献１参照）。これらの方法は広くコンピュータアプリケーションにおいて実施されている。
【０００４】
これらの従来技術が、本質的に技術的な欠陥をもっているわけではなく、実用的である。しかしながら、ここ数年のコンピュータアプリケーションの進展はめざましいものがあり、特に、コンピュータの主記憶となるＣＭＯＳ　ＲＡＭ（半導体ランダム・アクセス・メモリー）、主たる外部記憶装置であるハードディスクの価格の低減はいちじるしいものがあり、その結果として、コンピュータが同時に処理しようとするデータ量が飛躍的に増大している。そのために、整列するデータの量も増大し、数千万件規模のレコードを扱うことも希でなくなっている。従って技術的な問題というより、利用者の要求レベルが向上し、技術がその要求に応えられなくなっているのが実状というべきである。従って、革新的で、従来技術を大幅に超える性能を提供する整列技術が要求されるようになっている。しいて、従来の技術を使用した場合の問題点を記述すると、多くの実用的なアルゴリズムは、データの件数が１０倍となると、１０倍を大幅に超える演算時間が必要となり、すなわち、データの数が多くなればなるほど、実行処理速度（データ量／演算処理時間）が低下する傾向にあり、また、初期のデータの並びかたで計算所用時間の予測ができない場合が発生するなどの問題を引き起こす。これらの問題点は近年の、増大したデータの整列処理を実施するときに特に問題である。
【０００５】
【特許文献１】
米国特許第５２６５２６０号明細書
【０００６】
【発明が解決しようとする課題】
整列技術の基本的な評価の仕方は、整列に要する時間と、整列に使用するＲＡＭ（ランダム・アクセス・メモリ）の使用量であり、性能と、ＲＡＭの使用量のトレードオフの関係がアルゴリズムの開発と選択の基本問題であった。従前は、ＲＡＭは高価なものであり、ＲＡＭの使用量を最小とするアルゴリズムの中で高速のものを選択するというアプローチであった。現在の課題としては、相対的にＲＡＭの価格が低下しており、とにかく、整列に要する時間を最小にすることが求められている。また、ハードウェア価格の下落が進行しているおりから専用の演算処理用の回路を用いても、性能の高い整列装置が希求されている。
【０００７】
本発明の課題は、現在使用しうるデバイス（半導体メモリ、演算回路素子）を使用し、最も高速と思われる整列方法及びその演算装置を提供することである。
【０００８】
【課題を解決するための手段】
目的とする課題を解決する第一の課題は、整列のための唯一の情報を保有する非整列情報（通常、ＲＡＭ記憶装置に保管されている。）へのアクセス回数を最小とすることである。そのためには、同時によびだすデータのビット幅（セグメント長Ｎ）が大きければ大きいほどアクセス（この場合、読み出し）の回数は減少させることができる。また、同一レコードの同一データセグメントへのアクセスへの重複をなくすことによりアクセス回数の増大を防ぐことができる。理想的にはレコードのビット幅と同一のセグメント長を保有し、非重複アクセスをすることである。これが実現した場合、同一ＲＡＭ上に展開された、被整列データを整列することにおける理論的な最速値を提供する。当然のことにこれを実現するアルゴリズムは、多くは、実質的に無限のメモリ空間使用し、整列結果の収集に多大の時間を有するので、低ビット数の限定された整列データを扱う方法の他知られていない。本発明では、同一レコードを複数のセグメントに分解し、複数回のレコードアクセスを実行するが、同一レコードの同一データへの重複アクセスのすることのない整列方法を提供する。高速化の方法としては、実現可能で、より大きなセグメントサイズを設定して対応することが選ばれる。
【０００９】
目的とする課題を解決する第二の課題は、データのアクセスに付随して実行される数々の操作のステップ数、とりわけメモリのアクセスに関する操作のステップ数を最小にすることである。「クイックソート」等の一般的アルゴリズムでは、通常比較のため、一つのレコードを数十回アクセスし、また、それに付随する演算処理は単純であるので、単一の演算装置で処理する限りではレコード数×数十回の演算時間は必要であり、また、仮にキャッシュ機能を保有する並列の演算装置を用いたとしても、基本の記憶回路への複数回のアクセスが必要となる。メモリアクセス回数を省略する技術的な方法が存在しないのである。本発明では、演算装置が複数の演算をサポートするということを前提として、レコードを格納しているメモリのアクセス時間とほぼ同等の時間で、他の付随的な操作を実行することを実現している。即ち、本発明では、同一データへの重複アクセスをさけることにより、レコードへアクセス回数を最小とすると同時に、レコードのアクセス時間以外の処理時間をレコードアクセス時間とパイプライン並行処理をすることで、総合的な処理時間から排除することにより高速な整列を実現する装置を提供している。
【００１０】
本発明は上記の２つの課題を実現する方法として、従来の二つのデータの比較、一致をもとの並び替えを実施するという方式を採用せず、理論的には複合安定整列という概念を用いる。安定整列とは、整列のアルゴリズムではなく、整列操作の属性である。レコード集合が、レコード内のデータのサブ集合である、あるキーフィールドのデータですでに整列されていたと仮定する。例えばレコードが年齢と金額の二つのフィールドを保有していたと仮定する。現在の整列データは年齢で整列している。二つのレコードを比較すれば、下位のレコードの年齢フィールドは決して上位のレコードの年齢フィールドの値を超えることはない。しかし、同一の年齢フィールドを保有する二つのレコードの金額フィールドに何ら順序関係は存在していない。このレコード集合を今度は、金額のフィールドをキー・フィールドとして整列の操作を実行する。当然、金額については順序関係が構築され、二つのレコードを比較すれば、下位のレコードの金額フィールドは決して上位のレコードの金額フィールドの値を超えることはない。問題は年齢のフィールドである。同一金額の複数のレコードの集合において、年齢が整列された状態を保存している整列方法を安定整列と呼び、年齢のフィールドの順序関係が保証されない整列を不安定整列と呼ぶ。
【００１１】
「クイックソート」等の現在主流の整列アルゴリズムは不安定整列である。安定整列は、同一レコード集合で複数の集計処理を実施する場合には大変効果がある。一般的にデータ処理における整列とは、任意の長さのビット列を巨大な整数と見立てて、それの集合を、順序集合とすることである。この巨大なビット列を複数に分割する。その下位の分割をキーとして整列操作を実行し、次に、その上位の分割をキーとして、安定整列を実行し、最終的に、最上位の分割まで安定ソートを実行したとき、レコードのビット数が如何に大きくとも、そのレコード集合は最終的に整列する。このように複数の安定整列を実施することにより、どのようなサイズのレコードの整列も可能である。
【００１２】
次に、安定整列を複数実行するとき、必ずしも安定整列の度にレコード集合の整列が必要でないことを示す。下位の集合結果から安定整列を実行するときに必要な操作は下位の整列結果の情報から、安定整列のためのキー・データをアクセスできることが要件であり、その結果として、上位の安定整列情報か構築可能であれば足りる。通常この操作をレコード集合中のレコードの移動操作を実行しないで可能となれば、安定整列操作を複数回継続することによる処理にレコードデータ本体を移動するという負荷を含めることから免れる。
【００１３】
本発明では、「レコード認識データ」という、レコードの記憶回路中のアドレスを計算可能な情報を整列情報として用いることで、これを実現している。通常はレコードの記憶回路中のアドレス、レコードの順序番号、３２ビットのレコードなどはレコードの値自身が「レコード認識データ」となりうる。しかしこれに限定されるものではない。
【００１４】
【発明の実施の形態】
本発明の実動作について説明する。通常、セグメントビット数Ｎとして４以上を用いることが多い。現在のメモリの価格からはＮ＝１６、また、バイト文字を扱う場合はＮ＝８とする。より高速な処理を実現する場合Ｎ＝２８と言う数値が採用される。この値は一連の安定整列操作において同一である必要はない。この演算回路の最大処理が可能なＮの範囲内では、複数のＮ値を設けうることを妨げていない。実際、バイト文字データの場合などに、Ｎ＝８とした安定整列を実行することは優に考慮に値する。最大のＮを決定した場合、本発明による装置は、２のＮ乗個のＦＩＦＯメモリ回路で、その容量が、最大サポートするレコード数分存在し、レコード認識データのビット幅以上のワード幅を保有する、書き込み用と読み出し用の２組みを用意しなければならない。このレコード認識データの一時保管回路であるＦＩＦＯメモリ回路の機能は単純であり、あるレコードのあるセグメントの安定整列を保証することにある。
【００１５】
整列の手順を示す。仮にレコード番号をレコード認識データとする。まず、最下位のセグメントをキーとする整列を実行する。レコード集合は、レコード集合格納用の記憶回路に配列の状態で格納されている。配列の番号、即ち、レコード番号とセグメントの位地を示すと、当該レコードの当該セグメントの値を、一回の記憶回路アクセスで演算回路は入手することができる。この値はＦＩＦＯ記憶回路の番号であるので、演算回路はそのレコード番号を、該当ＦＩＦＯ記憶回路へ記憶する。この操作をレコード番号０（最初の番号）から初めて、最終番号Ｌまで実行する。このＦＩＦＯ回路はそのまま安定整列回路となっており、全てのレコードの、ＦＩＦＯ回路への書き込み操作の終了後、そのＦＩＦＯ回路の０番から順次データを読み出すと、当然、空のＦＩＦＯ回路からはデータを読み出すことができないので、実際には、空でない、即ち、レコード中の対象セグメントの集合の中の最も小さなセグメントの値を持つＦＩＦＯ回路に最初に記録されたレコード番号が最初に呼び出されることとなる。順次そのＦＩＦＯ回路が空になるまで呼び出し、また、空になったら、その上位の番号を持つ空でないＦＩＦＯ回路からレコード認識データを呼び出す。呼び出すＦＩＦＯ番号でレコード番号は整列している。さらに、同一のＦＩＦＯ回路から呼び出されたレコードの集合においては、この回路がＦＩＦＯ回路であるので、先に入れたレコード番号が、先に出てくる。ソート以前のレコードの順番には変化がないことが保証されている。即ち安定ソートが実現していることとなる。
【００１６】
整列に第１のステップは先に述べた、最下位のセグメントをキーとする整列である。通常、０から最大のレコード番号Ｌまで、レコード認識データは順次、該当する書き込み用のＦＩＦＯ回路に記録される。レコードが複数セグメントを保有する場合は、これまでが第１ステップであり、単一のセグメントのみの場合は、以下の、第２、第３のステップは省略される。
【００１７】
第２ステップは、書き込み用のＦＩＦＯ回路を読み出し用に設定する。また、読み出し用のＦＩＦＯ回路を新たに書き込み用に設定する。最初の動作は、読み出し用のＦＩＦＯの最も小さい番号を持つものから調べて、空でないＦＩＦＯ回路からレコード番号を引き出す。次にそのレコード番号と、今回のステップのセグメント位置から、レコード集合を格納した記憶回路をアクセスし、新しいセグメント値、即ち、書き込み用のＦＩＦＯの番号を引き出し、そこへ当該レコード番号を記録する。次に同一の読み出しＦＩＦＯからのレコード番号を読み出し、また、そのＦＩＦＯか空であれば次に空でない大きなメモリ回路からレコード番号を呼び出し、同様にレコード集合の格納記憶回路を呼び出し、かつ、レコード番号をそのセグメント番号の書き込み用のＦＩＦＯ回路へ記録する。このようにして全ての読み出し用のＦＩＦＯを空にするまで実行し、第２ステップを終了する。この時点で、書き込み用のＦＩＦＯ回路に記録されている情報は、このステップまでのセグメントのデータで整列された情報となっている。
【００１８】
第３のステップは第２のステップを最上位のセグメントまで繰り返し継続することである。最上位のセグメントまでの第２ステップ処理をくりかえした場合、最終の書き込み用のＦＩＦＯ回路に記録されている情報は全てのレコードビットで整列された、即ち整列が完了されたところのレコード番号の情報を記録している。
【００１９】
第４ステップは出力操作である。第４ステップは、書き込み用のＦＩＦＯ回路を、読み出し用のＦＩＦＯ回路に設定し、第２ステップと同様にＦＩＦＯ回路からレコード番号を呼び出す。このレコード番号のレコードをレコード集合の格納された記憶回路から読み出し、そのレコードの全体、または、一部を、出力用の一時保管記憶回路に書き出す。このエリアは通常、整列操作を指示したホストコンピュータの記憶回路に存在する。本発明においては、整列結果の出力が可能であるというということが本質的な事項であり、どこへ、どのような方法で出力するかということは本質的な事項ではない。実際には、プログラム転送、ＤＭＡ（ダイレクトメモリアクセス）転送等、多様な形態がとられる。正常に出力された結果は、被整列レコード集合が、昇順に整列された情報となっている。
【００２０】
読み出し用にＦＩＦＯ記憶回路、書き込み用のＦＩＦＯ記憶回路、レコード集合を格納した記憶回路が物理的独立な記憶回路である場合、仮のそのサイクルタイムが１００ｎｓとする。その場合、ｎ番目レコードのＦＩＦＯ回路の読み出し、ｎ−１番めのレコードのレコード集合の格納された記憶回路からの読み出し、ｎ−２番めのレコードの、レコード番号の書き込み用のＦＩＦＯ回路への記録は同一サイクル内で実行できるので、その場合は１レコードの安定整列に要する時間は１サイクル１００ｎｓとなる。このパイプライン並列処理は絶大効果をもたらす。
【００２１】
これまでに説明した方法で、本発明は、極めて高速に整列操作を実行するが、Ｎが極めて大きな場合や、データの数が多くない場合は、空でないＦＩＦＯを調べる操作を実行する時間が比較的大きな無駄時間と評価される場合がある。この場合、以下に示すマーキングビットマップメモリ回路と呼ばれる演算回路によってその時間を実質的に零とすることができる。この記憶回路は、Ｎが１６の場合、２の１６乗ビットの記憶回路２組みであり、これはＦＩＦＯ回路と同様に書き込み用と読み出し用である。この回路は通常メモリ回路のワード数、例えば３２ビットワードで構成される。また、容量も小さいところから、アクセスタイムも３０ｎｓ以下のスタティックメモリ素子で構成されるメモリ回路である。ワード数が３２の場合、この記憶回路は２０４８ワードのメモリ回路２組みとなる。この記憶回路の初期値は全て０である。第１ステップ、第２ステップの書き込み時には、書き込み用のビットメモリ回路のセグメント番号の上位１１ビットをアドレスとするビットメモリ回路の下位５ビット番めのビットを１にするように読み出し、書き込み操作を実行する。第２ステップ、第４ステップのＦＩＦＯの読み出し操作においては、このビットメモリを一回アクセスする度に、３２個のＦＩＦＯか空であるか無いかが判定可能であり、さらに、この動作は、ＦＩＦＯの動作とは独立に実行できるので、実際の現在読み出している空のＦＩＦＯの番号より、ずっと先の空で無い番号を演算回路の内部エリアに記憶させておくことも可能であり、その場合、実質整列操作時間に含める時間としては、空のＦＩＦＯを調べる時間は零となる。
【００２２】
これまでの説明で、複数のＦＩＦＯ記憶回路をもちいることで、整列操作が完了することを示した。Ｎの値が、８以下であれば、用意するＦＩＦＯ記憶回路の数も多くはないので、ＦＩＦＯメモリ素子と、単純な番号のデコード回路を組み合わせることで、工業的に現実的には製品を作成することは可能である。
【００２３】
また本発明が要件とする一時格納記憶回路、即ちＦＩＦＯ回路は、１要素が対象とするレコード数分のレコード認識データの格納の容量をもたなくてはならない。一つの要素記憶回路が固定的に、それだけの格納容量を保有していたとすると、Ｎが８のときは、合計でレコード数の２５６倍の記憶容量を必要とすることになる。Ｎが大きければ、さらに大きな値を必要とする。従ってＦＩＦＯ記憶回路を単純に構成した場合は、その記憶容量は相当大きなものとなる。ＦＩＦＯ記憶回路に、ＦＩＦＯメモリ素子を使用する場合は、現在市販されているＦＩＦＯメモリ素子の仕様を前提とする限りでは、多数レコードの整列の実行を可能とする装置とした場合にかなり高価な演算装置となる。メモリ素子も様々な新仕様の素子が開発されており、将来においてはＦＩＦＯ素子等の専用のメモリ素子を用いて、本発明の定義するＦＩＦＯ記憶回路を構成することは十分可能であるが、現時点では、工業的に現実的であるとはいえない。
【００２４】
また、二組の記憶回路を保有することも、コストアップとなり、工業的には負の要因である。しかし、Ｎを大きくすればするほど、操作のパス数が減少するので、実質的に小さいＮでしか安価な装置とならないということでは、本発明の価値が半減する。従って、Ｎを１６以上とすることができ、ＦＩＦＯメモリ素子を用いず、通常の安価なランダムアクセスメモリ素子（ダイナミックまたはスタティックメモリ素子）を用いて、ＦＩＦＯ記憶素子と同等な機能を持つ、物理的に単一でも、物理的に複数であってもかまわない一時格納記憶回路で、２組の記憶回路の総容量が合理的な容量で収まる記憶回路が存在した場合、上記で説明したすべての負の要因が解決されることは明らかであり、本発明はそれを実現しており、その回路について説明する。この回路を動的擬似ＦＩＦＯ回路と呼ぶ。
【００２５】
動的擬似ＦＩＦＯ回路は全体的に３つの記憶回路から構成されている。そのどれもが、一般的に使用されている、アドレス、データ、読み書きの制御ラインを基本とする、スタティックメモリ、またはダイナミックメモリで構成される。特殊なメモリ素子ではないので大変安価である。構成記憶回路は、データ保管メモリ、ＦＩＦＯ番号管理メモリ、ユニット管理メモリと呼ばれるものである。
【００２６】
データ保管メモリは、単一のメモリ空間であり、データ幅は、通常、レコード認識データのデータ幅以上で３２であることが多い。基本的にはこのメモリがＦＩＦＯ記憶回路の実体であり、レコード番号等のレコード認識データはこのメモリへ記録され、また、このメモリから呼び出される。このシステムではユニットと呼ばれる概念が使用される。ユニットのサイズＬは通常８、または１６である。その他の数値をつかうことは、差し支え無いが、デジタル演算が２進演算であるので、通常より大きなオーバヘッドを伴う。データ保管メモリはユニットに分割されている。ユニットサイズＬを１６として説明を継続する。データ管理メモリのアドレス（ワード単位のアドレス）の下位４ビットをユニット内部アドレスと呼ぶ。また、下位４ビットを除いた上位アドレスで構成される値をユニット番号と呼ぶ。ユニット番号と、ユニット内部アドレスを指定すると、それより構成されるアドレスのワードデータが読み書きできるのは自明である。ユニット内部アドレスは０から１５の値をとることができる。そのアドレスの一つを「リンクアドレス」に指定する。通常アドレス１５が「リンクアドレス」である。
【００２７】
データ保管メモリの機能は動的ＦＩＦＯを構成することである。あるユニット番号のユニットにデータを入れる。通常０のアドレスから順次データを格納する。次に格納すべきアドレスが１５番、即ち、「リンクアドレス」となった場合、ユニット管理メモリとよばれるメモリを制御する、外部のユニット管理機構から、次に接続すべきユニット番号を取得する。そして、「リンクアドレス」へその番号を書き込み、実際に保管すべきデータは新たに得たユニット番号のユニット内部アドレス０に書き込む。さらにデータが存在した場合は、同様に格納していけばよい。最終的には、非常に多くのユニットの中にデータが格納されることがあるし、また、一つのユニットの中でデータが完結する場合もある。データの読み出しは簡単である。最初のデータを保管したユニット番号のユニットからデータを順次、ユニット内部アドレスの低いアドレスからデータを読み出し、リンクアドレスに到達したとき、リンクアドレスに書かれたユニット番号のユニット内部アドレス０のデータを読み出せばよい。以下の操作は同様である。この書き込み、読み出しの操作はＦＩＦＯ回路そのものである。また、この操作において、次のユニットへ読み出しに移行する際、そのユニットは使用済みとなるので、ユニット管理機構へそのユニットの番号が使用済みであることの登録をする。
【００２８】
データ保管メモリ中の一つのＦＩＦＯを管理するための情報は、書き込みポインタと呼ばれるアドレス情報と、読み出しポインタと呼ばれるアドレス情報のみであり、これらは、ユニット番号と、ユニット内部アドレスからなるデータ保管メモリのアドレスを指す。また、データ保管メモリ全体として、どの番号のユニットが空であるかを管理する機構（ユニット管理機構）を必要としている。一つのＦＩＦＯを構成するとき、最初に実行されることは、ユニット管理機構に対し、一つのユニット番号を取得することである。そして、そのユニットの内部アドレス０のメモリアドレスを書き込みポインタ、読み出しポインタへ設定することである。書き込みポインタと読み出しポインタとの値が等しいということは、ＦＩＦＯが空であることと等価である。ＦＩＦＯがデータを取得すると書き込みポインタのアドレスへ当該データを書き込む。その後書き込みポインタをインクリメントする。そのポインタが「リンクアドレス」を示していた場合は、ユニット管理機構から新しいユニット番号を取得し、その番号を自己のポインタの示すアドレスへ書き込み、自己のポインタの値を新しいユニット番号のユニットの内部アドレス０の値に書きかえる。以下はＦＩＦＯへ保管するデータがくる度に同様な操作を行う。ＦＩＦＯからデータを取得する場合は、読み出しポインタのアドレスのデータを読み出すことによって足る。読み出し後に読み出しポインタをインクリメントする。読み出しポインタが「リンクアドレス」を示した場合は、「リンクアドレス」のデータ、即ち、接続するユニット番号を取得し、その内部アドレス０メモリアドレスに自己のポインタの値を書き換え、同様な操作を行う。その場合、必要に応じ、前に使用していたユニットのユニット番号を、使用済みユニットとして、ユニット管理機構に報告する。このことにより、ユニット管理機構はこの使用済みのユニットを新しくユニットを必要とするＦＩＦＯにわりあてることができ、無駄な記憶エリアが生じることを避けることができる。
【００２９】
以上説明したように、データ保管メモリは、書き込みポインタと、読み出しポインタという情報のセットが存在した場合、そのセットに対し、一つのＦＩＦＯを構成できるので、複数のポインタのセットを保有することで単一のメモリでありながら、複数のＦＩＦＯを構成することができる。ＦＩＦＯのメモリが使用効率の最も悪い状態はＦＩＦＯが空のときで、そのときでも、１ＦＩＦＯあたり１６ワードのメモリしか消費していない。また、１６分の１ワードがリンクワードとして使用されるので格納データの１５分の１メモリが管理情報として失われるが、これもコスト的にはまったく問題とならない容量である。
【００３０】
次に番号管理メモリの構造を示す。Ｎを１６とした場合、本発明が必要とするＦＩＦＯの数は２の１６乗の２倍である。ひとつのＦＩＦＯは書き込みと読み出しのポインタを必要とする。このポインタを格納できるワード幅で２の１６乗ワードのメモリユニットが、論理的に４セット、即ち、書き込み用のＦＩＦＯのための、書き込み、読み出しの二つのポインタのセット、および、読み出し用のＦＩＦＯのそれである。従ってこのメモリは２の１８乗ワードの単純なメモリとして構成することができるし、当然、別メモリとすることもできる。これは、単純に、論理的なメモリの構成と、物理的なメモリ構成の設定の問題である。単一メモリとした場合は、０からＮの１６乗―１の値をとるＦＩＦＯの番号を指定する１６ビットの情報、二組のＦＩＦＯセットを指定する１ビットの情報、読み出し、書き込みのポインタを指定する１ビットの情報の合計１８ビットのアドレスを保有するメモリ回路となる。１８ビット構成とする場合は通常高速なスタティックメモリが使用される。通常レコードデータが保管されるダイナミックメモリのサイクルタイムは１００ｎｓ前後であり、スタティックメモリのその２分の１から６分の１のサイクルタイムを容易に実現する。すなわち、並行動作をする演算回路として設計した場合、同一メモリでありながら全体の処理時間を増加させることではなく、複数回のメモリアクセスを可能とすることができる。
【００３１】
ユニット管理メモリはユニット管理機構のなかのメモリである。ユニット管理機構は、様々な実装が可能であるが、その１例を示す。その例は１個のユニット番号カウンターと、約６４ワードのユニット番号を保管できる内部ＦＩＦＯを必要とする。このＦＩＦＯをユニット管理メモリという。このＦＩＦＯはデータ保管メモリ中に構成しても、別個に構成しても問題はない。カウンターの初期値はユニット管理メモリ中のユニット番号の最も小さい値である。データ保管メモリの演算回路から、空のユニットの要求があったとき内部ＦＩＦＯが空のときは、ユニット番号カウンターの値を与え、ＦＩＦＯが空でないときは内部ＦＩＦＯのなかからデータを呼び出して与える。空のユニットの登録があったときは、内部ＦＩＦＯに登録する。
【００３２】
次に、動的擬似ＦＩＦＯ回路全体の動作を説明する。この回路の使命は、ＦＩＦＯの番号を指定されたとき、レコード認識データをそのＦＩＦＯに保管することであり、番号を指定されたときＦＩＦＯに保管されているレコード認識データを出力することである。データを保管するときは、まず、番号管理メモリから、当該する番号の、書き込み用のＦＩＦＯの組みの書き込みポインタを読み出し、そのポインタの値で先に示した保管動作を実施すればよい。データを読み出すときは、書き込みポインタと読み出しポインタの双方を読み出し、ＦＩＦＯが空でないことを確認し、先に示した読み出し動作を実行すればいい。全体として、レコード情報の操作時には、２回のメモリアクセスを必要とするが、これは別の物理メモリとし、メモリを並列にアクセスすることを可能とする演算回路とすれば、実質的な１操作の処理時間は、メモリ１アクセスとすることができ、処理時間の増加につながらない操作とすることができる。
【００３３】
これまでの説明で番号管理ユニットは２組必要であると説明したが、データ管理メモリ中のワードに、現在の読み出しの組、現在の書き込みの組を示す１ビットのマークをつけることにより、一組のポインタセットを保有することで足る。即ち、マークを認識することで、組を混同して、レコード認識データを扱うことを避けることができる。このような構成とした場合、設計されたレコード数分のレコード認識データを保管することができるデータ保管メモリを１組、番号管理メモリは、読み出しポインタ用、書き込みポインタ用の２組の論理メモリ回路で実現できる。勿論、高速化のために、より多くの論理メモリ回路、物理メモリ回路を保有することは一向に差し支えない。
【００３４】
本発明の方式は、重複となるが、セグメントのビットサイズＮを大きくすればするほど、性能は向上する。現在の、デバイス等のコストの趨勢の中では、１６から２８までの値を実用的なＮとして採用することができる。
また、全ての記憶回路に同一のサイクルタイム（この場合、メモリ素子のリードモディファイライトサイクルタイム）の記憶素子を使用し、本発明で必要な多数の論理的な記憶回路を、すべて独立な物理的なメモリ回路とし、必要な場合、書き込み、読み出し用に２セットを保有することにより、当該サイクルタイムで１レコードのセグメント処理を実行することが可能である。現在、ランダムアクセスメモリ回路は１２ｎｓのサイクルタイムで動作させることが可能であり、５０００万件のデータベースの整列を１秒以下で整列させることもできることを意味する。
【００３５】
本発明による整列装置は一般的なコンピュータのソフトウェアとして実現された整列処理に比べ、一連の多くの演算処理が、一つの演算処理の実行時間内の並列的に処理することが可能となっており、多くの場合、被整列対象のデータを、セグメント単位で一回読み出す時間で、整列の操作は完了し、従来方法に比べ飛躍的な、整列時間の短縮を実現する。
【００３６】
（実施例）
図１に実施例の構成を示す。使用するリソースを示す。実施例はＰＣＩローカルバスという、高性能パソコンサーバーが標準的に保有している拡張バスに接続可能な整列演算用アダプタボードの構成をとっている。ＰＣＩバスの先にホストコンピュータが存在し、整列演算が必要な場合、ホストコンピュータより、ＤＭＡにより、整列対象レコード集合を本ボードが受け取り、整列終了後はホストコンピュータの指定メモリアドレスへＤＭＡで整列後のレコード集合を転送する。
【００３７】
ボードの内部構成は、基本的に４つ部分によってなりたっている。その１は記憶回路Ａと呼ばれるもので、２５６ＭＢのサイクルタイム９０ｎｓ、アクセスタイム６０ｎｓ、高速ページモードサイクルタイム３０ｎｓ、ワード幅６４ビットのＤＲＡＭ（高速ページモードダイナミックＲＡＭ）で構成されたメモリ回路であり、レコード集合を格納するためのものである。６４バイトのレコードを４００万件分格納する容量を保有している。勿論１６バイトのレコードであれば１６００万件である。
【００３８】
その２は記憶回路Ｂと呼ばれるものであり、容量は３２ＭＢであることとワープロ幅が３２ビットであることを除き、その他の構成は記憶回路Ａと同じであり、これは、データ管理メモリとして、ＦＩＦＯ回路中核をなすものであり、レコード認識情報の格納用である。１レコードに４バイトの容量を保有するので、この記憶回路へは、８００万件弱の、レコードの記憶回路１の位置情報、即ち、ポインタ値を格納可能である。
【００３９】
その３は記憶回路Ｃと呼ばれる、容量が１ＭＢのサイクルタイム３０ｎｓ、ワード幅３２ビットの高速ＳＰＡＭ（高速ＣＭＯＳスタティックＲＡＭ）で構成されたメモリ回路であり、このメモリは４つの論理メモリ回路を一つの物理メモリ回路へ組み込んだものである。その１は、２５６ＫＢは２の１６乗個の記憶回路Ｂに構成された擬似ＦＩＦＯ回路への書き込みのポインタを格納するもので、その２は、２５６ＫＢは読み出しのポインタの格納用であり、その組みで番号管理ユニットメモリを構成している。その３は、８ＫＢは書き込み用マーキングビットマップメモリ回路として使用するものでの、その４は、同じく８ＫＢの読み出し用のものとして使用する。合計で５１２ＫＢ＋１６ＫＢを使用しており、他のエリアは使用していない。
【００４０】
その４は５万ゲートでシステムクロック３３ＭＨｚで動作する、プログラマブルゲートアレー（ＰＧＡ）であり、次の機能を保有している。機能１は、ホストコンピュータとインターフェースする機能であり、ＰＣＩ仕様のバスの制御機能、ＤＭＡ転送機能等を保有している。当然、本発明に基づく、整列の制御回路で、３つの記憶回路をパイプライン並列動作する制御回路を保有している、また、内部に、少量のメモリ回路を保有しているので、ユニット管理機構、および、そのユニット管理メモリは本フィールドプログラマブルゲートアレーの内部に構成されている。また、レジスタ、カウンタ、アドレス計算ユニット、デコーダ、エンコーダ、整列演算のバッファとして使用される特定用途のＦＩＦＯ等もこのＰＧＡの中に構成される。
【００４１】
本実施例は、プログラマブルゲートアレー（ＰＧＡ）の内部に構成されたものを含み、基本的に４つの独立したアクセスが可能なメモリ回路と、制御回路によってなりたっている。セグメントのビットワード数Ｎは、１６と８をサポートしており、バイト境界の文字列データなどが存在した場合、８のビットワードを使用することがある。通常は１６である。以下は１６として、実施例の説明をする。降順整列の制御も可能であるが、昇順、降順は本質的な問題ではないので、昇順として説明する。
【００４２】
先に説明した、第１ステップの動作は、本実施例では、ホストコンピュータからのＤＭＡによる転送動作中に実行される。即ち、ＤＭＡ動作中はＰＧＡ中を全てのレコードデータが通過するのであり、通過途中で、最も下位のセグメントの値を制御回路が認識することが可能であり、勿論、そのレコードが記憶回路Ａのどのアドレスに格納されるかという情報も既知であるので、本発明の定義する第１ステップの動作が可能であり、実際には、ホストからのＤＭＡの終了時点では、記憶回路Ａにレコードデータが格納されるのはもとより、擬似ＦＩＦＯ回路の本体である記憶回路Ｂ（データ管理メモリ）への、レコード認識情報（今回はレコードのメモリポインタ値）の記録、記憶回路Ｃ中の番号管理ユニットメモリのポインタの更新、マーキングビットマップメモリ回路へのビットセット等が実行される。
【００４３】
第１ステップの動作の説明の前に初期化の動作を説明する。制御回路が必要とする初期化動作は、二組のマーキングビットマップメモリ回路を零クリアすること、ＰＧＡ内部の使用済みユニット保管用のポインタを零とすることである。この初期化に要する時間は２０４８サイクルであり。約６０マイクロ秒である。また、同時に必要な数のＦＩＦＯを構成するために、番号管理ユニットメモリに、初期値を与える必要がある。これは１２８Ｋ回の記憶回路Ｃへの書き込みとなり、１２８Ｋサイクル、即ち、４ミリ秒の時間を要する。この初期化に要する時間は、最初はシステムの起動時に実行されるし、この回路を再度整列に使用する場合は、その前の回の整列結果データをＤＭＡでホストに返送する際に、実行可能であるので、整列開始の要求があってから、この初期化動作が終了するまで、回路を使用できないということではない。この初期化動作に加えて、ホストからのレコードの情報が必要である。レコードのサイズ、下位から上位のセグメントのレコード中の物理的な位置、送られてくるレコードの番号、もし、可変長のレコードであれば、そのフォーマット、レコード終端識別用のコード等をあらかじめ受領していなければならない。本ボード自体は多様なレコードフォーマットに対応可能であるが、実施例の説明用としては、レコードフォーマットはレコードの総ビット数は６４ビット、４個の１６ビットセグメントからなりたち、第１ワードの上位１６ビットが最上位セグメント（第３位セグメント）であり、下位の１６ビットが第２位セグメントであり、第２ワードの上位１６ビットが第１位セグメントであり、下位１６ビットが最下位セグメント（第０位セグメント）であるとする。
【００４４】
ステップの動作の説明にはいる前の、各種の要素動作の説明をする。図２にユニット管理機構の構造を示す。新ユニットカウンタは１９ビットのカウンタであり、初期値は、記憶回路Ｂの先頭メモリアドレス、即ち０である。このカウンタは、アップカウンタである。使用済ユニットポインタは、使用済みのユニットを保管する６４ワードの使用済ユニット保管メモリのアドレスで、使用済みとされた１９ビットのユニット番号を、次に保管するアドレスを指しているアップダウンカウンタである。当然、初期値は０である。他回路より、保管の要求があると、受け取ったユニット番号をこのカウンタの示すアドレスへ書き込み、このカウンタは１インクリメントする。但し、６３をこえるアドレスを指すことはない。使用可能なユニットの要求がある場合は、使用済ユニットポインタの値が０であれば、新ユニットカウンタの値を、要求回路に渡し、その後に新ユニットカウンタをインクリメントする。使用済ユニットポインタの値が０でなければ、使用済ユニットポインタの値を１デクリメントさせ、そのアドレスに格納されているユニット番号を要求回路に渡す。この回路は初期化動作で２の１６乗回のユニットの要求を受領し、その値は番号管理ユニットのそれぞれのアドレスへ記録される。
【００４５】
マーキングビットマップメモリおよびその制御回路の動作について説明する。ビットマップの構造を図３に示す。１６ビットのセグメント番号が与えられたとき、そのデータは上位１１ビットと下位５ビットに分解される。上位１１ビットはマーキングビットマップメモリのアドレスとなる。論理アドレスの物理アドレスへの変換が必要であり、実際の記憶回路Ｃの物理アドレスは、この値に、書き込み用に設定したメモリの記憶回路Ｃ中の先頭アドレスを加えたものである。下位５ビットはデコードされ、３２ビットのデータで１ビットのみセットされている値となる。書き込み動作中は、最初にこのアドレスから読み出したデータとデコードしたデータのビット論理和をとる。この値が０である場合は、初めてこのセグメント番号のＦＩＦＯへのポインタ記録要求があったことを示しており、その場合は読み出した値と、デコードした値の論理積をとりその結果を同一アドレスへ書き込む。論理和の値が正の場合は、すでに登録済みであるので、書き込み動作は実行しない。
【００４６】
マーキングビットマップメモリを読み出し動作で用いる場合は、制御回路中のアドレスカウンタ（１１ビット）を０として、マーキングビットマップメモリのデータを読み出す。その値をエンコード処理をして、最も小さくセットされているビットの番号（５ビット）を演算する。この値と、１１ビットを結合した１６ビットを、次の、空でないＦＩＦＯ番号として、ＰＧＡ内のＦＩＦＯに登録しておく。同時にこのビットをクリアし、次のエンコード操作を実行する。値が０となった場合当該アドレスへ０を書き込み、アドレスカウンタを１インクリメントし次のアドレスのマーキングビットマップメモリのデータを読み込む。すべての処理、即ち、最大アドレスまでマーキングビットマップメモリを調べた時点では、このマーキングビットマップメモリは零クリアされているので、再度の初期化は必要としない。
【００４７】
次に、擬似ＦＩＦＯ回路への書き込み動作を説明する。書き込み動作は、動作するＦＩＦＯを指定するセグメント番号と、ＦＩＦＯに保管するレコードポインタ値の提供を受け、最終的に適切な保管場所に、そのポインタ値を記録することである。番号管理ユニットメモリで、書き込みポインタユニットと設定されたもののセグメント番号アドレスのデータを読み出し、それを内部レジスタＸへ格納する。Ｘの値が、ユニットの最終アドレスであった場合、即ち、下４ビットが１５であった場合、ユニット管理機構より、新しいユニットアドレス（１９ビットのユニット番号と４ビットの値０を結合した２３ビットのアドレス）を取得し、先ず、Ｘの値のアドレスの記憶回路Ｂ（データ管理メモリ）へ書き込み、Ｘ自体を新しいユニットアドレスの値で更新するという動作を実行する。この条件動作は１５回に一回の割りで実行される。この動作が実行されない場合、また、実行されて、内部レジスタＸの値が更新された場合も以下の動作を実行する。即ち、Ｘの値のアドレスの記憶回路Ｂへレコードポインタを記録する。Ｘの値を１インクリメントする。Ｘの値をＸと呼び出したメモリ、即ち、番号管理ユニットメモリで、書き込みポインタユニットと設定されたメモリのセグメント番号アドレスへ書き込む。尚、データ管理メモリへの書き込み動作をする場合、セグメントの位が奇数の場合のみ、最上位ビットを１にセットした値を書き込むものとする。これは、各ステップにおける、読み出し用のレコードポインタと書き込み用のレコードポインタを区別するものである。
【００４８】
次に、擬似ＦＩＦＯ回路への読み出し動作を説明する。読み出し動作の基本は、動作するＦＩＦＯを指定するセグメント番号を与えられた場合、そのＦＩＦＯからレコードのポインタ値を読み出すことである。まず基本となる動作を説明する。番号管理ユニットメモリで、読み出しポインタユニットと設定されたもののセグメント番号アドレスのデータを読み出し、それを内部レジスタＹへ格納する。さらにＹの値のアドレスの記憶回路Ｂ（データ管理メモリ）のデータを読み出し、内部レジスタＺへ保管する。このＺの最上位ビットが、当該処理を実行しているときのセグメントの位が奇数のとき１であれば、また、偶数のとき０であれば、当該ＦＩＦＯへは、読み出すべきポインタ値が存在しないことを意味し、次のＦＩＦＯへ処理をうつるべく終了する。上記条件に該当しない場合は、ＦＩＦＯにデータが存在していることを意味しているので、以下の次に処理へ移行する。そしてＹの値が、ユニットの最終アドレスであった場合、即ち、下４ビットが１５であった場合、ユニット管理機構に対し、Ｙの値の上位１９ビットを使用済みユニットとして登録し、Ｙの値をＺより最上位ビットをマスクした値に書きなおし、再度、Ｙの値のアドレスの記憶回路Ｂ（データ管理メモリ）のデータを読み出し、内部レジスタＺへ保管する。Ｚより最上位ビットをマスクした値が、呼び出された次のレコードのポインタ値である。その後、Ｙをインクリメントし、Ｙの読み出しアドレスへ記録すれば、この処理は終了する。
【００４９】
実施例における、呼び出し操作の実装は、高速化のため、原理的には上に説明したもの同等であるが、若干異なった演算操作となる。その基本は、読み出す時に、ユニットに記録されているレコードのポインタ値を、ユニットの最終アドレス、即ち、１５を超えないアドレスまで、このデータ管理メモリから連続的に読み出すことである。この方式を採用すると、ＤＲＡＭのページモード処理が実現可能であり、一つのアクセスが３０ｎｓで実行可能となる。もうひとつは、ＦＩＦＯに読み出し用のポインタで、記憶回路上にあるものを、一つのレコードのポインタ値の呼び出しの度に更新しないことであり、この値は、当該ＦＩＦＯにおける最初の読み出しを始める時点で、ＰＧＡの内部にコピーレジスタを設け、その値を、当該ＦＩＦＯの読み出し終了、即ち、空になった時点でこのコピーを実際の番号管理ユニットへ書き込む。これらにより、外部のメモリへのアクセスの回数と時間を減少させることができる。
【００５０】
以上で個々の要素動作の説明をしたので、次に全体のステップ動作を示す。第１ステップの動作は、レコードのポインタ値とそのレコードが最も低位のセグメントの数値を得ることから始まる。メモリ中にレコードが展開されている場合は、記憶回路Ａからのアクセスとなるが、通常はホストコンピュータからデータが送られてくるのでＰＧＡで、その情報を抽出し、データの転送過程で第１ステップを終了させることができる。
【００５１】
図４に第１ステップの動作を示す。以下の説明では、新規ユニットの獲得、返却登録等のＦＩＦＯのユニットオペレーションのための特殊操作は、既にそのロジック・操作を説明してあるので、より全体の動きを明確にするために省略してある。ＰＧＡ演算回路はホストから、この場合は６４ビットのデータを受入内部レジスタに保管する。この動作と同時に下位の１６ビット（最下位セグメント）をセグメントレジスタに保管する。次のサイクルでレコードの格納場所を示すアドレスカウンタの値を記憶回路Ａへのアドレスバッファに送出し、同時に、６４ビットのデータは記憶回路Ａのデータバッファへ送出する。この書き込む処理は３サイクル９０ｎｓを要する。記憶回路Ａへの書き込みと同時に記憶回路Ｃの書き込み用の番号管理ユニットのアドレスバッファに、セグメントレジスタの値とユニットのオフセット値の加算データ（実際は加算ではなく、１７ビット、１８ビット目を設定するだけである。）を送る。このサイクルの終了時に番号管理ユニットからのデータが、図中のレジスタカウンタへ読み込まれる。次のサイクルでは、３つの動作が並行的に実施される。レジスタカウンタの値が記憶回路Ｂのアドレスバッファへ送られる。また、同時にアドレスカウンタの値が記憶回路Ｂのデータバッファに送られ、記憶回路Ｂの書き込み動作が開始される。この終了には３サイクルを要する。これが第１の動作である、次の動作はシンプルなものでレジスタカウンタとアドレスカウンタをインクリメントする動作である。アドレスカウンタのインクリメントは、レコードのワード数分だけ増加する。第３の動作は記憶回路Ｃのマーキングビットマップメモリへ、セグメントレジスタの上位１１ビットに対応する記憶回路Ｃのアドレスを送出し、そのサイクルの終了時に、そのデータと下位５ビットのデコード値との論理和演算の結果を得る。次のサイクルは記憶回路Ｃの番号管理ユニットに対し、インクリメントしたレジスタカウンタの値を書き込む動作が実行される。もし、先の論理和の結果が正であれば、受け入れレジスタはホスト（またはホストバッファ）より次のレコードを受け入れる。先の論理和の積が０の場合は第５サイクルとして、デコード結果のビットを読み込んだデータと論理積したデータをマーキングビットマップメモリの同一アドレスへその値を書き込む。
【００５２】
図５に第１ステップの動作のパイプライン並行動作の様子を示す。図より明らかなように、１レコードを処理するためのサイクル数は原則的に３サイクルであり、初めて使用するＦＩＦＯに遭遇したとき、４サイクルとなる。追加サイクルと示されているところがそうである。レコード数が１００万件あるとすると、４サイクル操作の確率は数十分の１であり、ユニット管理操作も、４５サイクルに３サイクルのオーバヘッドを要するものであるから、第１ステップの所要サイクルは約３２０万サイクル程度であり、その時間は約０．１秒である。通常は、ファイルシステムからデータを読み込む時などは、ＰＡＧが全てのデータをホストコンピュータから、受け取る時間の方が大きい。
【００５３】
第２ステップの動作は、記憶回路Ｂのデータ格納ユニットからレコードのポインタを読み出して、そのポインタに該当するレコードの、該当セグメント位置のセグメントの数値を読み出して、同じく、データ格納ユニットへ書き出す一連の操作である。実装としては、１レコードのポインタ値の読み出しから、格納までを一連の動作として実行することも可能であるが、先に示した様に、ＤＲＡＭのページモードオペレーションを有効に利用する意味から、読み出し動作と、書き込み動作は独立した動作として設計されている。即ち、レコードポインタの読み出し動作は、ＰＧＡの内部に１６ワードのＦＩＦＯバッファを保有し、そこに格納する。レコードポインタの書き込み動作は、書き込み用のデータ格納ユニットへ記録される。当初、１６ワードのバッファが満杯となるまで、レコードポインタ値の読み出し操作が実行される。その後に、書き込み動作として、ＦＩＦＯからレコードポインタ値を読み出し、一連の書き込み動作が実行される。ＦＩＦＯの残量が８ワードとなった時点で再び、読み出し動作が行われる。このように、８ワードの処理毎に読み出し動作と書き込み動作が交互に実行される。
【００５４】
第２ステップの読み出しの処理の動作を図６に示す。この制御回路は複雑であるが、順を追って説明する。初期の動作として、１１ビットのセグメントカウンタが０にセットされている。最初のサイクルでこのカウンタの値をアドレスとして、記憶回路Ｃの読み出し用のマーキングビットマップメモリをアクセスし、その内容を取得する。この値は０場合、同一サイクル内でカウンタがインクリメントされる。この操作が０でないマップを読み出すまで継続する。０でないマップが読み出された次のサイクルの終にはエンコードされた数値が生成され、それを下位５ビットとし、セグメントカウンタの１１ビットを上位とする１６ビットの空でない格納ユニットの番号を得る。その値は４ワードのセグメント番号ＦＩＦＯレジスタに格納される。この処理は、読み出し回路が制御を保有している期間で、記憶回路Ｃへのアクセスが無い場合は４ワードのＦＩＦＯが埋まるまで実行される。記憶回路Ｃへのアクセスの優先順位は低く設定してあるが、通常は、あとで述べるポインタ値の操作の方が、サイクル数を多く消費するので、これは常に埋まっていると考えることができる。セグメント番号ＦＩＦＯレジスタのっトップのワードのアドレスが存在した場合、制御回路はその値をアドレスとしてサイクルを起動し、記憶回路Ｃの読み出しの番号管理ユニットの値を読み出し、サイクルの終了時にレジスタカウンタに保管する。レジスタカウンタにデータが読み込まれた場合、内部ＦＩＦＯを充填するために、可能な限りのページモードオペレーションで、レジスタカウンタの値をそのアドレスした、レジスタカウンタをインクリメントしながら、記憶回路Ｂからポインタデータを読み出す。最上位ビットを判定し、読み出し用のポインタであることを確認しながら、その値を内部ＦＩＦＯへ送る。そうでない場合は、最終のレジスタカウンタの値を記憶回路Ｃの番号管理ユニットに書き込み、次のサイクルで新しいセグメント番号をセグメント番号ＦＩＦＯから取得し同様な動作を実行する。このサイクルは内部ＦＩＦＯが充填されるまで継続する。
【００５５】
この回路の実質的な時間は、ページモードでレコード数分のレコードのポインタ値を記憶回路Ｂから読み出す動作の時間である。記憶回路Ｃへの読み出し、書き込み動作の時間がおおむね、記憶回路Ｂのアクセス時間内へ隠れることになる。記憶回路Ｂへの読み出しの多くが８レコード分とすると、それに要する所用時間が１０サイクルとなるので、１００万レコードの場合、その時間は約１２５万サイクル、すなわち、約０，０４秒である。
【００５６】
第２ステップの書き込みの処理の動作を図７に示す。この動作は、アドレスカウンタが、レコードポインタを格納した内部ＦＩＦＯに変更されたこと、記憶回路Ａからの読み出し操作でセグメントレジスタの値を得ることの他、基本的に第１ステップの処理と同じである。したがってその所要時間は約０．１秒である。書き込みと読み出しを切換えるオーバーヘッド等が存在するが、それを含めたとしても、第２ステップ全体の処理時間は０．１４秒とみることができる。
【００５７】
第３ステップの動作は第２ステップの動作の繰り返しであるので今回の場合、さらに２回の第２ステップ動作を行うことである。
第４ステップは出力動作である。第２ステップの呼び出し動作で取得したレコードのポインタ値で記憶回路ＡのレコードデータをＰＧＡに呼び出し、ホストへＤＭＡ転送する操作である。この操作で時間がかかる処理は記憶回路Ａへのアクセス操作であり、１レコードあたり３サイクル要するので３００万サイクル即ち、０．９秒の時間を必要とする。総合の処理時間は合計０．６１秒となる。
【００５８】
【発明の効果】
安定ソートによる多レコード長のレコード集合を、安定ソートを繰り返し実行して整列結果を得ること自体は、一般に行われていることである。本発明の実現するパーフォーマンスは、現在最速と言われているマイクロプロセッサを使用したコンピュータシステムを使用し、十分なメモリを搭載して、実行される整列処理が１００万件を超えるデータ処理である場合、数秒から、十数秒という時間を要することに対し、画期的とも言える優に１０倍を超える整列性能が得られていることである。この性能は２０ＣＰＵを保有する、極めて高価なコンピュータでも、出しうることが難しい実行性能である。その基本は、安定整列にＦＩＦＯメモリを多重構造とし、同じデータを２回読まないようにしたことであり、加えて、メモリを多重構造とし、複数の処理をメモリの多重構造の中で、パイプライン並行処理として、個々の処理時間を加算するのではなく、被整列対象データへのアクセス時間に相当する時間内に処理を完了させるという装置を発明したことである。近年メモリのコストは年々安価となり、そのシステムが工業的なコンピュータ処理をするものとして構築されている場合、１ＧＢ程度の、ＤＲＡＭメモリ、１００ＭＢ程度の高速ＳＰＡＭメモリ使用することへの不合理はなくなりつつある。実施例のボードはパソコンサーバー用に設計してあるので、メモリの物理的多重化レベルも３レベル程度であり安価なボードとなっている。１５ｎｓのサイクルタイムの高速ＳＲＡＭを使用し、多重化のレベルを増やし、また、ＤＲＡＭ中のレコードをＳＲＡＭ中に展開するといった方式を採用すると、１レコードのサイクルタイムを２０ｎｓまで減少させる演算装置を設計できるので、実施例の性能を４倍程度まで、あげることができる。理論的に演算ユニットの多重化をすること無しには、メモリのサイクルタイム以下の整列のサイクルタイムとすることはできないが、現在の市販されているメモリ素子を前提とする限りでは１０ｎｓレベルまでのサイクルタイムでソートを実行させることは、優に可能であり、その場合は、本発明による装置が優に１００ＣＰＵの並列コンピュータ以上のデータ処理の性能を引き出すことを意味している。
【００５９】
近年は、ハードディスクのコストの劇的な低下とインターネットからの情報の収集、マルチメディア的なデータの一般化を背景として、膨大なデータを処理する事に迫られている。ＣＰＵの性能も向上しているが、そのスピードは年率数十パーセントであり、その要求に答えることができない。並列コンピュータがその役割をになっているが、搭載するＣＰＵに比例するパーフォーマンスとは比較にならないレベルの性能しか発揮することができない。そして、その膨大なデータ処理を実行する基本の演算処理は整列をおいてない。実際、データ処理のためのコンピュータのＣＰＵ時間の大半は、実は整列処理によって占められていることは、自明なことであり、整列の処理時間を１０倍速くするということは、１０倍速いコンピュータシステムを導入したことと等価である。従って、本発明の産業上の利用価値ははかりしれないものがある。
【００６０】
現在のコンピュータシステムで主流のアルゴリズムである「クイックソート」、および、他の比較と置換を基本とする整列方法との関連の上で、本発明の位置を明確にする。先ず、整列の性能、整列に要する時間である。取りあえず１００万レコード、レコードの総サイズは６４ビット、総容量８ＭＢのダイナミックメモリにデータが格納されているとする。データはランダム数であり、通常３２ビットを調べることにより、整列が可能である。この場合、「クイックソート」は最も効率の良い性能を発揮し、約２５００万回の比較と５００万回の置換で処理は終了する。比較の処理はランダムアクセスであり、どのような方法を用いても１ワードアクセスに９０ｎｓかかる。従って、比較の操作は、３２ビットを同時にアクセスできるものとして、最低でも１８０ｎｓとなる。置換の操作は二つの６４ビットデータを置換するという操作であるので最低４回のメモリアクセスが発生する。しかし同一レコードの２ワード目のアクセス時間は半分程度と見積もることができるので、合計２７０ｎｓ程度である。その所要時間はプログラム時間を一切無視するとして５．８５秒である。尚、シングルＣＰＵとしては、最も高い整数演算処理性能を保有するＰＥＮＴＩＵＭ（Ｒ）プロセッサ１２０ＭＨｚ、主記憶アクセスタイム６０ｎｓ、キャシュメモリ２５６ＫＢのシステムにおける「クイックソート」の実測値は５．８秒である。この数値はデータのロード時間、セーブ時間を除いたものである。
【００６１】
本発明の実施例で使用した装置では、３２ビットの整列は２セグメントの処理であり、ＤＭＡの転送時間を含めたとしても、０．３３秒で終了する。実測値も同様であり、約０．４秒前後であった。１５倍程度の高速性能を実現している。この相対性能比は、レコード件数がさらに増大することのよりさらに差が開くこととなる。この性能は、ギガバイトを超えているデータベースの索引処理、ネットワークで複数のクライアントからの要求を受けるデータベースサーバなどに画期的な性能を提供する。本発明を搭載した、パソコンサーバは、２０ＣＰＵ程度のデータ処理性能を引き出す。現在のコンピュータの市販価格から想定した場合、そのシステムのコストの比は、２０倍以上になるとも思われる。
【００６２】
現在、数百メガバイトのデータベースレコードを整列させることが日常的に実施されるようになっている。従来の技術のはレコード数Ｎに対し、ＮｌｎＮに比例する実行時間が必要とされている。即ち、Ｎが大きくなればなるほど、１レコードあたりの整列時間が増加することを意味している。これは、メガバイト、ギガバイトのデータの整列には深刻な問題となっている。本発明は、データレコードの大きさに比例する整列処理時間で完了する整列装置であり、このことは、特に大きなデータベースデータの整列に有効である。
【図面の簡単な説明】
【図１】実施例の装置の全体構成図。
【図２】ユニット管理機構の構造。
【図３】マーキングビットマップの構造。
【図４】第１ステップ処理の動作。
【図５】第１ステップの動作のパイプライン並列動作の様子。
【図６】第２ステップの読み出しの処理の動作。
【図７】第２ステップの書き込みの処理の動作。
【図１】
2004145620.tif 000003
【図２】
2004145620.tif 000004
【図３】
2004145620.tif 000005
【図４】
2004145620.tif 000006
【図５】
2004145620.tif 000007
【図６】
2004145620.tif 000008
【図７】
2004145620.tif 000009