WO2010013320A1 - 表形式データを操作する方法、分散メモリ型マルチプロセッサ、及び、プログラム - Google Patents

Abstract

　分散メモリ型マルチプロセッサは、専用のローカルメモリ及びプロセッサを含み、相互にデータを送受するため通信接続されている複数台の演算ユニットを備え、一連のデータが複数個のブロックに分割され、複数台の演算ユニットのパイプライン処理によって操作される。演算ユニットは、前のパイプライン段にある１台以上の演算ユニットからそれぞれのローカルデータを受信し、１つのさらなるローカルデータに変換し、後のパイプライン段にある１台の演算ユニットへ送信し、最終的に１つのグローバルデータを生成するようにトーナメント方式で動的に接続可能であり、少なくとも１台のいずれかの演算ユニットがブロックの番号に基づいてグローバルデータを複数台の演算ユニットへ割り当てる。

Description

表形式データを操作する方法、分散メモリ型マルチプロセッサ、及び、プログラム

　本願の開示は、データ項目に対応した項目値を含むレコードの配列として表される表形式データを複数台の演算ユニットによって分担して操作する方法、特に、表形式データを構築し、表形式データをソートし、表形式データから特定のデータを検索し、又は、表形式データを集計する方法に関係する。

　本願の開示は、データ項目に対応した項目値を含むレコードの配列として表される表形式データを複数台の演算ユニットによって分担して操作する分散メモリ型マルチプロセッサ、特に、表形式データを構築し、表形式データをソートし、表形式データから特定のデータを検索し、又は、表形式データを集計する分散メモリ型マルチプロセッサにも関係する。

　さらに、本願の開示は、上記方法を分散メモリ型マルチプロセッサに実行させるためのプログラム、コンピュータプログラムプロダクト、及び、コンピュータプログラムが記録された記録媒体に関係する。

　従来、産業上の様々な分野において、大規模データを高速に処理することが求められている。大規模データの処理は、キャッシュやプリフェッチなどによるメモリアクセスの高速化、メモリ自体の高速化、及び、プロセッサの並列化のような演算処理の高速化、といったハードウェア技術の開発、ならびに、データ処理アルゴリズムの開発によって、高速化され続けている。

　本発明者は、大規模データを高速に処理するための基本的なデータ処理アルゴリズム、たとえば、特許文献１に記載されているような、「オンメモリデータ処理アルゴリズム」を提案している。この技術は、表形式データを、従来のようなレコード（すなわち、行）単位ではなく、項目（すなわち、列）単位に成分分解するという考え方に基づいている。より具体的には、表形式データが、（１）レコード順を表す配列と、（２）項目に属する一意の項目値が所定の順序（たとえば、昇順）に並べられた値テーブルと、（３）各レコードに対応する項目値が値テーブルに格納されている位置情報を表す配列とからなるデータ構造によって表現されている。このようなデータ構造を採用することにより、表形式データの検索、ソート、マージ、ジョイン等の処理が高速に実現されている。

　さらに、本発明者は、分散メモリ型のマルチプロセッサシステム及び共有メモリ型のマルチプロセッサシステムのようなプロセッサの並列化に対応した種々のオンメモリデータ処理アルゴリズムを提案している。たとえば、分散メモリ型のマルチプロセッサシステムに対応した検索・ソートアルゴリズムが特許文献２に記載され、集計アルゴリズムが特許文献３に記載されている。さらに、共有メモリ型のマルチプロセッサシステムに対応した効率的なソートアルゴリズムが特許文献４に記載されている。

　特許文献２及び３に記載されている分散メモリ型のマルチプロセッサシステム向けの検索・ソート及び集計は、特に、超並列プロセッサ（ＭＰＰ）アーキテクチャに適合するように設計されている。特許文献２及び３に記載されている技術では、ある特定のプロセッサモジュールがある処理を行うとき、他のすべてのプロセッサモジュールによって保持されているデータを受信し、受信されたデータとこの特定のプロセッサモジュールに保持されているデータとの間で比較演算を行うことがある。この比較演算のコストは、プロセッサモジュールの台数の２乗のオーダーであるため、並列化の程度が高くなると比較演算のコストも増加するという関係にある。

　一方、特許文献４に記載されている共有メモリ型のマルチプロセッサシステム向きのソートは、特に、対称型マルチプロセッサ（ＳＭＰ）アーキテクチャに適合するように設計されている。共有メモリ型マルチプロセッサシステムでは、多数のプロセッサが同一のメモリ（共有メモリ）に同時にアクセスしようとすることが頻繁に発生し、共有メモリへのメモリアクセス性能がシステム全体の性能を左右することがある。

　ところで、近年、たとえば、非特許文献１に記載されているような、不均一メモリアクセス（ＮＵＭＡ）アーキテクチャを採用するコンピュータシステムが市販されている。ＮＵＭＡタイプのコンピュータシステムは、リモートメモリアクセスが可能ではあるが、共有メモリを具備していないという点で、分散メモリ型のマルチプロセッサシステムである。特許文献２及び３に記載されている技術は、リモートメモリアクセスを利用しなければ、そのままこのＮＵＭＡタイプのコンピュータシステムに適用可能である。勿論、プロセッサ間通信の一部をリモートメモリアクセスによって置き換えるように、特許文献２及び３に記載されている技術を拡張することも可能である。

　このようなＮＵＭＡタイプのプロセッサを含む分散メモリ型マルチプロセッサでは、メモリアクセス性能がシステム全体の性能に与える影響は共有メモリ型コンピュータよりも小さいと考えられる。したがって、プロセッサ自体の演算処理能力の向上がメモリアクセス性能の向上を上回る、という状況においては、大規模なデータ、特に、大規模な表形式データの操作に、分散メモリ型マルチプロセッサを利用する利点がある。
Ｗ．Ｈ．Ｉｎｍｏｎ、Ｋ．Ｒｕｄｉｎ、Ｃ．Ｋ．Ｂｕｓｓ、Ｒ．Ｓｏｕｓａ著、鈴木健司、三船洋一、室住正晴訳、「データウェアハウス・パフォーマンス　－システム構築・管理技法－」、共立出版、２００２年６月１５日、ｐ．１４８－１５１ 国際公開第００／１０１０３号公報 国際公開第２００５／０４１０６６号公報 国際公開第２００５／０４１０６７号公報 国際公開第２００６／１２６４６７号公報

　したがって、分散メモリ型マルチプロセッサを利用して大規模な表形式データを高速に処理するためには、並列化の程度と共にコストが増加するような演算を除去するか、又は、少なくともできる限り削減することが重要である。

　また、分散メモリ型マルチプロセッサを構成する各演算ユニットの専用のローカルメモリの記憶容量は限定されているので、各演算ユニットのローカルメモリにデータが蓄積されることなく、各演算ユニットによって処理されたデータが次の処理のため別の演算ユニットへ受け渡されることが重要である。

　さらに、分散メモリ型マルチプロセッサの演算ユニット間のデータ通信のコストを低下させるためには、各演算ユニットがある処理を実現するとき、他のすべての演算ユニットからのデータを使用することを必要とされず、限定された台数の他の演算ユニット、たとえば、２台の他の演算ユニットからのデータを使用するように構成されていることが好ましい。

　したがって、各演算ユニットの演算量と、各演算ユニットに保持されるデータ量と、演算ユニット間のデータ通信量ができる限り削減されるように大規模データを操作する分散メモリ型マルチプロセッサを提供できることが好ましい。

　また、大規模なデータを操作する分散メモリ型マルチプロセッサにおいて、分散メモリ型マルチプロセッサの性能を十分に活かすため、各演算ユニットの演算量と、各演算ユニットに保持されるデータ量と、演算ユニット間のデータ通信量ができる限り削減されるようにデータを処理する方法を提供できることが好ましい。

　さらに、大規模データを操作する分散メモリ型マルチプロセッサにおいて、分散メモリ型マルチプロセッサの性能を十分に活かすため、各演算ユニットの演算量と、各演算ユニットに保持されるデータ量と、演算ユニット間のデータ通信量ができる限り削減されるようにデータを処理するプログラム、コンピュータプログラムプロダクト、及び、コンピュータプログラムが記録された記録媒体を提供できることが好ましい。

　本発明の一実施形態によれば、専用のローカルメモリ及びプロセッサを含み、相互にデータを送受するため通信接続されている複数台の演算ユニットを備え、一連のデータが上記複数台の演算ユニットに関連付けられた複数個のブロックに分割されて上記複数台の演算ユニットのそれぞれの専用のローカルメモリに保持され、上記一連のデータが上記複数台の演算ユニットのパイプライン処理によって操作される、分散メモリ型マルチプロセッサであって、
　各演算ユニットが、前のパイプライン段にある１台以上の演算ユニットからそれぞれのローカルデータを受信し、受信された少なくとも２つのローカルデータを１つのさらなるローカルデータに変換し、上記さらなるローカルデータを後のパイプライン段にある１台の演算ユニットへ送信するマージ手段を含み、
　前記複数台の演算ユニットのマージ手段が最終的に１つのグローバルデータを生成するようにトーナメント方式で動的に接続可能であり、
　少なくとも１台のいずれかの演算ユニットが、前記複数個のブロックに対応するブロック番号に基づいて、前記グローバルデータを分割し前記複数台の演算ユニットへ割り当てる分配手段を含む、
分散メモリ型マルチプロセッサが提供される。

　分散メモリ型マルチプロセッサは、専用のローカルメモリを含み、相互にデータを送受するため通信接続されている複数台の演算ユニットを備え、複数台の演算ユニットがパイプライン処理を実現するように構成されている装置である。演算ユニットはノードと呼ばれることもある。

　また、演算ユニット内のプロセッサは、シングルコアプロセッサでもよく、又は、２つ以上のプロセッサコアを含むマルチコアプロセッサでもよい。シングルコアプロセッサの場合、一連のデータから得られる各ブロックは演算ユニット毎に、すなわち、演算ユニット内のシングルコアプロセッサに対応付けられる。一方、マルチコアプロセッサの場合、演算ユニット内のローカルメモリは２つ以上のプロセッサコアの間で共有メモリとして用いられる。また、この場合、一連のデータから得られる各ブロックは、好ましくは、演算ユニット内のプロセッサコア毎に対応付けられる。よって、複数のブロックが１台の演算ユニットに関連付けられることになる。しかし、ある特定の１個のブロックには、必ず１台の演算ユニットが対応付けられているので、ブロック番号に基づいて演算ユニットを特定することが可能である。よって、以下の説明中、演算ユニットに含まれているプロセッサは、シングルコアプロセッサ又はマルチコアプロセッサのいずれでも構わない。

　本発明の一実施形態によれば、一連のデータは、複数個のブロックに分割され、ブロックにはブロック番号が割り当てられる。このブロック番号は、あるデータが複数台の演算ユニットのパイプライン処理によってマージされるときに、コピーされ、マージ後のデータに対応付けられる。よって、このデータに対応するブロック番号を参照することにより、マージ後のデータを元のブロックに関連付けられた演算ユニットへ分配することが可能である。このようにデータにブロック番号を対応付けることによって、各演算プロセッサが他のすべての演算プロセッサからのデータを受信する必要性がなくなるので、並列化の程度が増加しても比較演算のような演算のコストの増加が低減され、かつ、演算ユニット間のデータ通信のコストも抑制される。さらに、データはパイプライン処理されるので、いずれかの演算プロセッサの専用のローカルメモリに大量のデータが蓄積することが回避される。

　各演算ユニットのマージ手段は、入力側で１台以上の演算ユニットのマージ手段に接続され、出力側で１台の演算ユニットのマージ手段に接続され、１台以上の演算ユニットから入力された少なくとも２つのローカルデータを１つのローカルデータにマージして、１台の演算ユニットへ出力する。これにより、演算ユニットのマージ手段をトーナメント方式で接続することにより、最終的に１つのローカルデータが生成される。演算ユニットのマージ手段相互の接続は固定ではなく、動的に接続可能であるため、トーナメント表の形や、トーナメント表に配置される演算ユニットを処理対象に応じて変更することが可能である。各演算ユニットのマージ手段は、１台以上の演算ユニットからの３つ以上のローカルデータを１つのローカルデータにマージするように構成されることもある。さらに、演算ユニット間のデータ通信量を削減するため、入力側の２台の演算ユニットのうちの一方と、入力側からのローカルデータをマージするマージ手段を含む演算ユニットとが同一の演算ユニットであっても構わない。

　また、演算ユニットのプロセッサがマルチコアプロセッサであるならば、トーナメント表の第１階層のマージ処理は同一の演算ユニット内のプロセッサコアの間で行われることがある。勿論、この場合でも、第１階層のマージ処理が異なる演算ユニットからのローカルデータを用いて実行されても構わない。

　本発明の一実施形態によれば、上記一連のデータはデータ項目に対応した項目値を含むレコードの配列として表現される表形式データである。上記複数個のブロックに分割された上記表形式データのうち各演算ユニットに割り当てられたレコード、すなわち、担当レコードは、レコードの順序に依存する順序情報と各データ項目に依存する項目情報とに分離されている。表形式データを順序情報と項目情報とに分離すると、表形式データに検索やソートを適用したときに、順序情報だけが影響を受け、項目情報は検索やソートの適用前の状態を維持する。これにより、演算コスト、データ通信コストが大幅に軽減されることになる。

　また、本発明の一実施形態によれば、上記順序情報は、上記表形式データ内で上記担当レコードを識別するレコード番号、すなわち、原始レコード位置番号を上記ブロック内での上記担当レコードのレコード順序番号の順番に格納するレコード順序番号配列、及び、上記担当レコードに含まれる上記項目値にアクセスする項目値アクセス情報を上記レコード順序番号の順番に格納する項目値アクセス情報配列により形成されている。レコード順序番号配列と項目値アクセス情報配列は、整数型配列であり、サイズが等しい。レコード順序番号配列の各要素は、この要素に対応するレコードが表形式データ全体の中での位置、すなわち、原始レコード位置番号を表している。項目値アクセス情報配列の各要素は、順序情報と項目情報を結合するため、項目情報内の特定の配列、すなわち、後述のローカル項目値番号配列を指すインデックスとして用いられる。

　一方、上記項目情報は、上記担当レコードに含まれる一意の項目値が所定の順序で格納されているローカル項目値配列、上記担当レコードに含まれる上記項目値が上記ローカル項目値配列内に格納されている位置を指定するローカル項目値番号が上記担当レコードの上記原始レコード位置番号の順番に格納されているローカル項目値番号配列、及び、上記表形式データの全体で上記所定の順序に基づいて上記ローカル項目値配列中の上記一意の項目値に割り当てられた順序番号が格納されているグローバル項目値順序番号配列により形成されている。ローカル項目値番号配列は、担当レコードのレコード数と同じサイズを有し、ローカル項目値番号配列中の要素は、担当レコード中のあるレコードに含まれる項目値を指定するように、ローカル項目値配列を指すインデックスとして用いられる。ローカル項目値配列は、担当レコードの全レコードに含まれる一意の項目値が所定の順序（たとえば、昇順又は降順）で配置された配列である。ローカル項目値配列は、項目値自体を格納する配列であるため、整数型、浮動小数点型、文字列型など様々なデータ型を取り得る。グローバル項目値順序番号配列は、表形式データの全体に保持されている項目値の中での、ローカル項目値配列に格納されている各項目値の順位を、ローカル項目値配列に格納されている項目値の順番に格納する配列である。各項目値の順位は、たとえば、昇順、又は、降順のような所定の順序に基づいて決定される。

　本発明の一実施形態によれば、上記の成分分解の考え方と、ブロック番号の考え方と、パイプライン処理の考え方とを組み合わせて、表形式データをメモリ上に構築する分散メモリ型マルチプロセッサが提供される。

　表形式データを分散メモリ型マルチプロセッサのメモリ上に構築する処理、すなわち、コンパイル処理は、（ｉ）レコード順序番号配列及び項目値アクセス情報配列を作成する順序集合作成処理と、（ｉｉ）ブロック内でローカル項目値番号配列及びローカル項目値配列を作成するブロック内コンパイル処理と、（ｉｉｉ）ブロック間でグローバル項目値順序番号配列を作成するブロック間コンパイル処理とにより構成される。

　この表形式データのコンパイル処理を実現するために、本発明の一実施形態によれば、表形式データの（複数又は多数の）レコードは、ブロック番号によって識別されるブロックに分割される。本実施形態によれば、このブロックは、初期的には、このブロックに含まれるレコードの処理を担当する演算ユニットに関連付けられている。各演算ユニットが担当するレコードは、本書中で、担当レコードと呼ばれる。各演算ユニットには、このように定義された担当レコードが外部装置から送信される。外部装置は、外部記憶装置でもよく、又は、外部の演算ユニット若しくは外部のコンピュータでもよい。

　各演算ユニットは、担当レコードを認識するために、担当レコードのレコード順序番号（初期的には原始レコード位置番号と一致）がレコード順序番号の順番に格納されているレコード順序番号配列を生成する。原始レコード位置番号とは、元の表形式データの中で各レコードが収容されている位置、たとえば、行番号に対応する。さらに、各演算ユニットは、担当レコードに含まれる項目値にアクセスするため、項目値アクセス情報がレコード順序番号の順番に格納されている項目値アクセス情報配列を生成する。

　各演算ユニットの担当レコードに含まれる項目値は、データ項目毎に各演算ユニットが項目値アクセス情報配列を用いてアクセスすることができるように、各演算ユニットのためのローカル項目値配列に格納される。ローカル項目値配列には、データ項目毎に、一意の項目値が所定の順序（昇順又は降順）に格納されている。また、各演算ユニットが項目値アクセス情報配列を用いて担当レコードに含まれる項目値にアクセスするため、データ項目毎に、担当レコードに含まれる項目値を特定するローカル項目値番号が原始レコード位置番号の順番に格納されているローカル項目値番号配列が生成される。さらに、各演算ユニットによって保持されているローカル項目値を表形式データ全体に含まれているグローバル項目値の中で特定できるようにするため、表形式データの全体に含まれているグローバル項目値が所定の順序に格納される仮想的なグローバル項目値配列中での、ローカル項目値の位置を指定するグローバル項目値順序番号配列が生成される。生成された各種の配列は演算ユニットの専用のローカルメモリに記憶されている。

　以上の考え方に従って、本発明の一実施形態によれば、
　各演算ユニットが、
　上記分散メモリ型マルチプロセッサに接続されている外部装置からこの演算ユニットに割り当てられた上記担当レコードを受信する手段と、
　受信された上記担当レコードから、上記レコード順序番号配列及び上記項目値アクセス情報配列を生成し、この演算ユニットの上記専用のローカルメモリに格納する手段と、
　項目毎に、上記担当レコード中の項目値を上記所定の順序でソートすることにより、上記ローカル項目値配列、及び、上記ローカル項目値番号配列を生成し、この演算ユニットの上記専用のローカルメモリに格納するローカルコンパイル手段と、
　項目毎に、上記ローカル項目値配列、上記担当レコードの範囲内で上記所定の順序に基づいて上記ローカル項目値配列に含まれる上記一意の項目値に割り当てられた順序番号が格納されているローカル項目値順序番号配列、及び、上記ローカル項目値順序番号配列中の上記順序番号に関連した上記担当レコードを示す上記ブロック番号を含むブロック番号配列を、上記ローカルデータとして、この演算ユニットの後のパイプライン段にある演算ユニットへ送信する手段と、
を含み、
　各演算ユニットの上記マージ手段が、前のパイプライン段からの少なくとも２つのローカルデータに含まれている少なくとも２つのローカル項目値配列中の項目値を上記所定の順序でマージすることにより、上記少なくとも２つのローカルデータを、さらなるブロック番号配列、さらなるローカル項目値順序番号配列及びさらなるローカル項目値配列により形成された１つのローカルデータに変換する手段を含み、
　上記分配手段が、最終的に生成されたさらなるローカル項目値順序番号配列に格納されている順序番号を、対応する最終的に生成されたさらなるブロック番号配列に格納されているブロック番号に関連付けられた演算ユニットへ送信する手段を含み、
　各演算ユニットが、上記送信された順序番号を上記グローバル項目値順序番号配列に順次に格納する手段をさらに含む、
分散メモリ型マルチプロセッサが提供される。

　本発明の一実施形態によれば、上記の成分分解の考え方と、ブロック番号の考え方と、パイプライン処理の考え方とを組み合わせて、所定の項目に含まれる項目値をキーとして、表形式データをソートする分散メモリ型マルチプロセッサが提供される。

　表形式データのソート処理は、ソートされたレコード順序番号配列及びソートされた項目値アクセス情報配列を作成する処理である。このソート処理は、（ｉ）ブロック内で、カウンティングソートを実行し、新しい項目値アクセス情報配列を作成し、後の処理で使用されるグローバル項目値順序番号配列及びレコード順序番号配列を作成するブロック内ソート処理と、（ｉｉ）前の処理で作成されたグローバル項目値順序番号配列及びレコード順序番号配列を、ブロック番号配列と共にトーナメント方式でマージするブロック間マージ処理と、（ｉｉｉ）マージされたブロック番号配列から新しいレコード順序番号配列を作成するブロック間分配処理とにより構成される。

　この表形式データのソート処理を実現するために、本発明の一実施形態によれば、
　各演算ユニットが、
　所定の項目に関して、上記担当レコードを含むブロック毎に、上記ローカル項目値番号をキーとして上記レコード順序番号配列、上記項目値アクセス情報配列及び上記グローバル項目値順序番号配列にソートを適用し、これによって、ローカルソートされたレコード順序番号配列、ローカルソートされた項目値アクセス情報配列及びローカルソートされたグローバル項目値順序番号配列を生成するローカルソート手段と、
　上記所定の項目に関して、上記ローカルソートされたグローバル項目値順序番号配列、上記ローカルソートされたレコード順序番号配列、及び、上記ローカルソートされたレコード順序番号配列に関連した上記担当レコードを示す上記ブロック番号を含むブロック番号配列を、上記ローカルデータとして、この演算ユニットの後のパイプライン段にある演算ユニットへ送信する手段と、
を含み、
　各演算ユニットの上記マージ手段が、前のパイプライン段からの少なくとも２つのローカルデータに含まれている上記ローカルソートされたグローバル項目値順序番号配列と上記ローカルソートされたレコード順序番号配列との組を所定の順序でマージすることにより、上記少なくとも２つのローカルデータを、さらなるグローバル項目値順序番号配列、さらなるレコード順序番号配列及びさらなるブロック番号配列により形成された１つのローカルデータに変換する手段を含み、
　上記分配手段が、最終的に生成された上記さらなるブロック番号配列に含まれているブロック番号の上記さらなるブロック番号配列中での順序番号を、上記ブロック番号に関連付けられた演算ユニットへ送信する手段を含み、
　各演算ユニットが、上記送信された順序番号を上記レコード順序番号配列に順次に格納する手段をさらに含む。

　本発明の一実施形態によれば、上記の成分分解の考え方と、ブロック番号の考え方と、パイプライン処理の考え方とを組み合わせて、所定の検索条件を満たすレコードを表形式データから検索する分散メモリ型マルチプロセッサが提供される。

　表形式データの検索処理は、検索前の表形式データから、順序情報、すなわち、新たなレコード順序番号配列及び新たな項目値アクセス情報配列を作成する処理である。この検索処理は、（ｉ）ブロック内でローカル項目値配列に格納されている項目値が検索条件に一致するかどうかを判定し、検索条件に一致する項目値に対応するレコード順序番号及び項目値アクセス情報を抽出するローカル処理と、（ｉｉ）各ブロックで抽出されたレコード順序番号配列をブロック番号配列と共に所定の順序でマージし、マージされたブロック番号配列に従って最終的な新たなレコード順序番号配列を作成するグローバル処理とにより構成される。

　この表形式データの検索処理を実現するために、本発明の一実施形態によれば、
　各演算ユニットが、
　所定の項目に関して、上記担当レコードを含むブロック毎に、検索条件に一致する項目値を含むレコードに対応する新たなレコード順序番号配列及び新たな項目値アクセス情報配列を生成し、上記項目値アクセス情報配列を上記新たな項目値アクセス情報配列で置き換えるローカル検索手段と、
　上記所定の項目に関して、上記新たなレコード順序番号配列、及び、上記新たなレコード順序番号配列に関連した上記担当レコードを示す上記ブロック番号を含むブロック番号配列を、上記ローカルデータとして、この演算ユニットの後のパイプライン段にある演算ユニットへ送信する手段と、
を含み、
　各演算ユニットの上記マージ手段が、前のパイプライン段からの少なくとも２つのローカルデータに含まれている上記新たなレコード順序番号配列と上記ブロック番号配列との組を所定の順序でマージすることにより、上記少なくとも２つのローカルデータを、さらなるレコード順序番号配列及びさらなるブロック番号配列により形成された１つのローカルデータに変換する手段を含み、
　上記分配手段が、最終的に生成された上記さらなるブロック番号配列に含まれているブロック番号の上記さらなるブロック番号配列中での順序番号を、上記ブロック番号に関連付けられた演算ユニットへ送信する手段を含み、
　各演算ユニットが、上記送信された順序番号を上記新たなレコード順序番号配列に順次に格納する手段をさらに含む。

　本発明の一実施形態によれば、上記の成分分解の考え方と、ブロック番号の考え方と、パイプライン処理の考え方とを組み合わせて、表形式データを集計する分散メモリ型マルチプロセッサが提供される。

　表形式データの集計処理では、集計元の表形式データから、集計結果の表形式データが新たに生成される。集計結果の表形式データは、集計の次元に関する項目と、集計対象に関する項目（集計前の項目、集計計算途中の項目、集計結果の項目など）とを含む表形式データである。よって、集計結果の表形式データを新たに生成するためには、集計元の表形式データから、（ｉ）集計結果の表形式データのサイズを計算する処理と、（ｉｉ）集計結果の表形式データをブロックに分割して、複数台の演算ユニットに割り当てる処理と、（ｉｉｉ）（１つ以上の）集計の次元に関する項目の項目値の組を特定し、各演算ユニットに割り当てる処理と、（ｉｖ）集計対象に関する項目の項目値を特定し、複数台の演算ユニットに割り当てる処理とにより構成されている。

　この表形式データの集計処理を実現するために、本発明の一実施形態によれば、
　前記複数台の演算ユニットは、集計元の表形式データとして使用される第１の表形式データに関する第１の担当レコード、及び、上記第１の表形式データの所定の項目の組に関する項目値の組毎に少なくとも１つの別の集計項目に関する項目値を集計することにより得られる集計結果を表現する第２の表形式データに関する第２の担当レコードをそれぞれの専用のローカルメモリに格納するように構成されている。

　各演算ユニットは、
　上記分散メモリ型マルチプロセッサに接続されている外部装置から、上記第２の表形式データのうちこの演算ユニットに分割される上記第２の担当レコードの範囲情報、及び、上記所定の項目の組に属する一意の項目値の個数の組を受信する手段と、
　上記第２の担当レコードの範囲情報に基づいて、この演算ユニットに割り当てられた上記第２の担当レコードのレコード順序番号配列及び項目値アクセス情報配列を生成し、この演算ユニットの上記専用のローカルメモリに格納する手段と、
　上記所定の項目毎に、上記第２の担当レコードの範囲情報と上記所定の項目に属する一意の項目値の個数の組とに基づいて、この演算ユニットに割り当てられた上記第２の担当レコードのグローバル項目値順序番号配列及びローカル項目値番号配列を生成し、この演算ユニットの上記専用のローカルメモリに格納する手段と、
　上記所定の項目毎に、上記第１の担当レコードに関するこの所定の項目のローカル項目値配列と、上記第２の担当レコードに関するこの所定の項目の上記グローバル項目値順序番号配列と、上記グローバル項目値順序番号配列中の順序番号に関連した上記第２の担当レコードを示すブロック番号を含むブロック番号配列とを、上記ローカルデータとして、この演算ユニットの後のパイプライン段にある演算ユニットへ送信する手段と、
を含む。

　各演算ユニットの上記マージ手段は、前のパイプライン段からの少なくとも２つのローカルデータに含まれているローカル項目値配列を所定の順序でマージすることによりさらなるローカル項目値配列を生成し、前のパイプライン段からの少なくとも２つのローカルデータに含まれているブロック番号配列及びグローバル項目値順序番号配列を所定の順序でマージすることによりさらなるブロック番号配列及びさらなるグローバル項目値順序番号配列を生成し、これにより、上記少なくとも２つのローカルデータを、上記さらなるローカル項目値配列、上記さらなるブロック番号配列及び上記さらなるグローバル項目値順序番号配列により形成された１つのローカルデータに変換する手段を含む。

　上記分配手段は、最終的に生成されたさらなるグローバル項目値順序番号配列に格納されている順序番号によって指定された最終的に生成されたさらなるローカル項目値配列に格納されている項目値を、対応する最終的に生成されたさらなるブロック番号配列に格納されているブロック番号に関連付けられた演算ユニットへ送信する手段を含む。

　各演算ユニットは、上記送信された項目値をこの演算ユニットの上記第２の担当レコードのローカル項目値配列に順次に格納する手段をさらに含む。

　各演算ユニットは、上記第１の担当レコードに含まれる上記所定の項目の組に関する項目値の組を特定する次元値番号を含む次元値番号配列と、上記次元値番号に対応する上記少なくとも１つの集計項目に関する項目値の集計値を含むローカル集計値配列とを生成し、上記ローカルデータとして、この演算ユニットの後のパイプライン段にある演算ユニットへ送信する手段をさらに含む。

　各演算ユニットの上記マージ手段は、前のパイプライン段からの少なくとも２つのローカルデータに含まれている次元値番号配列及びローカル集計値配列を所定の順序でマージすることにより、上記少なくとも２つのローカルデータをさらなる次元値番号配列及びさらなるローカル集計値配列により形成された１つのローカルデータに変換する手段を含む。

　上記分配手段は、最終的に生成されたさらなるローカル集計値配列に格納されている集計値を上記第２の担当レコードの上記範囲情報に従って演算ユニットへ送信する手段をさらに含む。

　各演算ユニットは、
　上記少なくとも１つの集計項目毎に、上記送信された項目値を所定の順序でソートすることにより、集計項目に関するローカル項目値配列及びローカル項目値番号配列を生成し、この演算ユニットの上記専用のローカルメモリに格納するローカルコンパイル手段と、
　上記少なくとも１つの集計項目毎に、上記ローカル項目値配列、上記第２の担当レコードの範囲内で所定の順序に基づいて上記ローカル項目値配列に含まれる一意の項目値に割り当てられた順序番号が格納されているローカル項目値順序番号配列、及び、上記ローカル項目値順序番号配列中の上記順序番号に関連した上記担当レコードを示す上記ブロック番号を含むブロック番号配列を、上記ローカルデータとして、この演算ユニットの後のパイプライン段にある演算ユニットへ送信する手段と、
をさらに含む。

　各演算ユニットの上記マージ手段は、前のパイプライン段からの少なくとも２つのローカルデータに含まれている少なくとも２つのローカル項目値配列中の項目値を上記所定の順序でマージすることにより、上記少なくとも２つのローカルデータを、さらなるブロック番号配列、さらなるローカル項目値順序番号配列及びさらなるローカル項目値配列により形成された１つのローカルデータに変換する手段をさらに含む。

　上記分配手段は、最終的に生成されたさらなるローカル項目値順序番号配列に格納されている順序番号を、対応する最終的に生成されたさらなるブロック番号配列に格納されているブロック番号に関連付けられた演算ユニットへ送信する手段をさらに含む。

　各演算ユニットは、上記送信された順序番号を、この演算ユニットの上記専用のローカルメモリに設けられた、上記少なくとも１つの集計項目に関するグローバル項目値順序番号配列に順次に格納する手段をさらに含む。

　さらに、本発明の別の実施形態によれば、
　専用のローカルメモリ及びプロセッサを含み、相互にデータを送受するため通信接続されている複数台の演算ユニットを備え、
　一連のデータが上記複数台の演算ユニットに関連付けられた複数個のブロックに分割されて上記複数台の演算ユニットのそれぞれの専用のローカルメモリに保持され、上記一連のデータが上記複数台の演算ユニットのパイプライン処理によって操作される、分散メモリ型マルチプロセッサにおいて、
　各演算ユニットが、前のパイプライン段にある１台以上の演算ユニットからそれぞれのローカルデータを受信し、少なくとも２つの受信されたローカルデータを１つのさらなるローカルデータに変換し、上記さらなるローカルデータを後のパイプライン段にある１台の演算ユニットへ送信し、最終的に１つのグローバルデータを生成するようにトーナメント方式で動的に動作するステップと、
　少なくとも１台のいずれかの演算ユニットが、前記複数個のブロックに対応するブロック番号に基づいて、前記グローバルデータを分割し前記複数台の演算ユニットへ割り当てるステップと、
を備える、表形式データ操作方法が提供される。

　さらに、本発明の別の実施例によれば、
　専用のローカルメモリ及びプロセッサを含み、相互にデータを送受するため通信接続されている複数台の演算ユニットを備えるコンピュータにロードされ、
　一連のデータが上記複数台の演算ユニットに関連付けられた複数個のブロックに分割されて上記複数台の演算ユニットのそれぞれの専用のローカルメモリに保持され、上記一連のデータを上記複数台の演算ユニットのパイプライン処理によって操作するコードを上記コンピュータに実行させるコンピュータ読み取り可能なプログラムであって、
　各演算ユニットが、前のパイプライン段にある１台以上の演算ユニットからそれぞれのローカルデータを受信し、少なくとも２つの受信されたローカルデータを１つのさらなるローカルデータに変換し、上記さらなるローカルデータを後のパイプライン段にある１台の演算ユニットへ送信するコードと、
　前記複数台の演算ユニットのマージ手段が最終的に１つのグローバルデータを生成するようにトーナメント方式で動的に動作するコードと、
　少なくとも１台のいずれかの演算ユニットが、前記複数個のブロックに対応するブロック番号に基づいて、前記グローバルデータを分割し前記複数台の演算ユニットへ割り当てるコードと、
を備えるプログラムが提供される。

　さらに、本発明の別の実施例によれば、
　専用のローカルメモリ及びプロセッサを含み、相互にデータを送受するため通信接続されている複数台の演算ユニットを備えるコンピュータにロードされ、
　一連のデータが上記複数台の演算ユニットに関連付けられた複数個のブロックに分割されて上記複数台の演算ユニットのそれぞれの専用のローカルメモリに保持され、上記一連のデータを上記複数台の演算ユニットのパイプライン処理によって操作する上記表形式データ操作方法を上記コンピュータに実行させるためのコンピュータプログラムプロダクトが提供される。

　さらに、本発明の別の実施例によれば、
　専用のローカルメモリ及びプロセッサを含み、相互にデータを送受するため通信接続されている複数台の演算ユニットを備えるコンピュータにロードされ、
　一連のデータが上記複数台の演算ユニットに関連付けられた複数個のブロックに分割されて上記複数台の演算ユニットのそれぞれの専用のローカルメモリに保持され、上記一連のデータを上記複数台の演算ユニットのパイプライン処理によって操作する上記表形式データ操作方法を上記コンピュータに実行させるためのコンピュータプログラムが記録された記憶媒体が提供される。

　本発明の少なくとも1つの実施例によれば、分散メモリ型マルチプロセッサの各演算ユニットの演算量と、各演算ユニットに保持されるデータ量と、演算ユニット間のデータ通信量ができる限り削減されるので、大規模データを効率的に操作することができる分散メモリ型マルチプロセッサを実現することが可能になる。

本発明の一実施形態による分散メモリ型プロセッサの概略図である。 本発明の一実施形態によるコンピュータシステムの概略図である。 本発明の一実施形態の基礎となるデータ管理機構を説明するための表形式データの一例を表す図である。 本発明の一実施形態の基礎となる基本的なデータ管理機構の説明図である。 本発明の一実施形態による分散メモリ型マルチプロセッサ向けデータ構造の説明図である。 本発明の一実施形態による分散メモリ型マルチプロセッサ向けデータ構造の説明図である。 本発明の一実施形態による分散メモリ型マルチプロセッサ向けデータ構造の説明図である。 本発明の一実施形態による分散メモリ型マルチプロセッサ向けデータ構造の説明図である。 本発明の一実施形態による分散メモリ型マルチプロセッサ向けデータ構造をローカルメモリ上に構築する方法のフローチャートである。 本発明の一実施形態による分散メモリ型マルチプロセッサ向けデータ構造における項目値取得方法のフローチャートである。 本発明の一実施形態によるコンパイル方法の概略的なフローチャートである。 本発明の一実施形態による順序情報作成処理の説明図である。 本発明の一実施形態による順序情報作成処理の説明図である。 本発明の一実施形態によるブロック内コンパイル処理の概要図である。 本発明の一実施形態によるブロック内コンパイル処理の概要図である。 本発明の一実施形態によるブロック内コンパイル処理の概要図である。 本発明の一実施形態によるブロック内コンパイル処理の概要図である。 本発明の一実施形態によるブロック内コンパイル処理の説明図である。 本発明の一実施形態によるブロック内コンパイル処理の説明図である。 本発明の一実施形態によるブロック内コンパイル処理の説明図である。 本発明の一実施形態によるブロック内コンパイル処理の説明図である。 本発明の一実施形態によるブロック内コンパイル処理の説明図である。 本発明の一実施形態によるブロック間コンパイル処理の概要図である。 本発明の一実施形態によるブロック間コンパイル処理の初期化処理の説明図である。 本発明の一実施形態によるブロック間コンパイル処理の初期化処理の説明図である。 本発明の一実施形態によるブロック間コンパイル処理における１段目のマージ処理の説明図である。 本発明の一実施形態によるブロック間コンパイル処理における１段目のマージ処理の説明図である。 本発明の一実施形態によるブロック間コンパイル処理における１段目のマージ処理の説明図である。 本発明の一実施形態によるブロック間コンパイル処理における２段目のマージ処理の説明図である。 本発明の一実施形態によるブロック間コンパイル処理における２段目のマージ処理の説明図である。 本発明の一実施形態によるブロック間コンパイル処理における２段目のマージ処理の説明図である。 本発明の一実施形態によるブロック間コンパイル処理における２段目のマージ処理の説明図である。 本発明の一実施形態によるブロック間コンパイル処理における３段目のマージ処理の結果を説明する図である。 本発明の一実施形態によるブロック間コンパイル処理における分配処理の説明図である。 本発明の一実施形態によるブロック間コンパイル処理における分配処理の説明図である。 本発明の一実施形態によるコンパイル処理の結果を説明する図である。 本発明の一実施形態によるコンパイル処理の結果を説明する図である。 本発明の一実施形態によるコンパイル処理の結果を説明する図である。 本発明の一実施形態によるソート処理を適用する前の表形式データの説明図である。 本発明の一実施形態によるソート処理を適用した後の表形式データの説明図である。 本発明の一実施形態によるソート処理を図５Ａの表形式データに適用することによって得られる表形式データの説明図である。 本発明の一実施形態によるソート処理を図５Ａの表形式データに適用することによって得られる表形式データの説明図である。 本発明の一実施形態によるソート処理を図５Ａの表形式データに適用することによって得られる表形式データの説明図である。 本発明の一実施形態によるソート処理を図５Ａの表形式データに適用することによって得られる表形式データの説明図である。 本発明の一実施形態による表形式データのソート方法の概略的なフローチャートである。 本発明の一実施形態による表形式データのソート処理におけるブロック内ソート処理の説明図である。 本発明の一実施形態による表形式データのソート処理におけるブロック内ソート処理の説明図である。 本発明の一実施形態による表形式データのソート処理におけるブロック内ソート処理の説明図である。 本発明の一実施形態による表形式データのソート処理におけるブロック内ソート処理の結果の説明図である。 本発明の一実施形態による表形式データのソート処理におけるブロック間ソート処理１の階層構造を説明する図である。 本発明の一実施形態による表形式データのソート処理におけるブロック間ソート処理１の階層構造を説明する図である。 本発明の一実施形態による表形式データのソート処理におけるブロック間ソート処理１の階層構造を説明する図である。 本発明の一実施形態による表形式データのソート処理における２段目のマージ処理の説明図である。 本発明の一実施形態による表形式データのソート処理における２段目のマージ処理の説明図である。 本発明の一実施形態による表形式データのソート処理における３段目のマージ処理の説明図である。 本発明の一実施形態による表形式データのソート処理におけるブロック間ソート処理２（分配処理）の説明図である。 本発明の一実施形態による表形式データのソート処理におけるブロック間ソート処理の説明図である。 本発明の一実施形態による表形式データのソート処理におけるブロック間ソート処理の説明図である。 本発明の一実施形態による表形式データのソート処理におけるブロック間ソート処理の説明図である。 本発明の一実施形態による表形式データのソート処理におけるブロック間ソート処理の説明図である。 本発明の一実施形態による表形式データのソート処理におけるブロック間ソート処理の説明図である。 本発明の一実施形態による表形式データのソート処理の結果の説明図である。 本発明の一実施形態による検索処理を適用する前の表形式データの説明図である。 本発明の一実施形態による検索処理を適用した後の表形式データの説明図である。 本発明の一実施形態による検索処理を適用する前の表形式データの順序情報の説明図である。 本発明の一実施形態による検索処理を適用した後の表形式データの順序情報の説明図である。 本発明の一実施形態による検索処理を適用した後の表形式データの項目情報の説明図である。 本発明の一実施形態による検索処理を適用した後の表形式データの項目情報の説明図である。 本発明の一実施形態による表形式データの検索方法の概略的なフローチャートである。 本発明の一実施形態による表形式データの検索処理におけるローカル処理の説明図である。 本発明の一実施形態による表形式データの検索処理におけるローカル処理の説明図である。 本発明の一実施形態による表形式データの検索処理におけるローカル処理の説明図である。 本発明の一実施形態による表形式データの検索処理におけるローカル処理の説明図である。 本発明の一実施形態による表形式データの検索処理におけるグローバル処理の説明図である。 集計元の表形式データの説明図である。 集計結果の表形式データの説明図である。 本発明の一実施形態による表形式データの集計処理の集計元の表形式データの説明図である。 本発明の一実施形態による表形式データの集計処理の集計元の表形式データの説明図である。 本発明の一実施形態による表形式データの集計処理の集計元の表形式データの説明図である。 本発明の一実施形態による表形式データの集計処理の集計元の表形式データの説明図である。 本発明の一実施形態による表形式データの集計処理の集計結果の表形式データの説明図である。 本発明の一実施形態による表形式データの集計処理の集計結果の表形式データの説明図である。 本発明の一実施形態による表形式データの集計処理の集計元表形式データの説明図である。 本発明の一実施形態による表形式データの集計処理の集計結果の表形式データの説明図である。 本発明の一実施形態による表形式データの集計処理の集計結果の表形式データの説明図である。 本発明の一実施形態による表形式データの集計方法のフローチャートである。 本発明の一実施形態による表形式データの集計処理における次元分類結果の説明図である。 本発明の一実施形態による表形式データの集計処理における次元作成処理の説明図である。 本発明の一実施形態による表形式データの集計処理における次元作成処理の説明図である。 本発明の一実施形態による表形式データの集計処理における次元作成処理の説明図である。 本発明の一実施形態による表形式データの集計処理における次元作成処理の説明図である。 本発明の一実施形態による表形式データの集計処理における次元作成処理（マージ処理及び分配処理）の説明図である。 本発明の一実施形態による表形式データの集計処理における測度作成のための次元値の組のソート処理の説明図である。 本発明の一実施形態による表形式データの集計処理における測度作成のための次元値の組のソート処理の説明図である。 本発明の一実施形態による表形式データの集計処理における測度作成のための次元値の組のソート処理の説明図である。 本発明の一実施形態による表形式データの集計処理における測度作成のための次元値の組のソート処理の説明図である。 本発明の一実施形態による表形式データの集計処理における測度作成のための次元値の組のソート処理の説明図である。 本発明の一実施形態による表形式データの集計処理における測度作成のための次元値の組のソート処理の説明図である。 本発明の一実施形態による表形式データの集計処理における測度作成のための次元値の組のソート処理の説明図である。 本発明の一実施形態による表形式データの集計処理における測度作成のための次元値の組のソート処理の説明図である。 本発明の一実施形態による表形式データの集計処理における測度作成のための次元値の組のソート処理の説明図である。 本発明の一実施形態による表形式データの集計処理における測度作成のための次元値の組のソート処理の説明図である。 本発明の一実施形態による表形式データの集計処理における測度作成のための次元空間内順序番号配列及び測度項目値配列の作成処理の説明図である。 本発明の一実施形態による表形式データの集計処理における集計値配列の作成処理の説明図である。 本発明の一実施形態による表形式データの集計処理における測度集計値のマージ処理の説明図である。 本発明の一実施形態による表形式データの集計処理におけるコンパイル処理の説明図である。 本発明の一実施形態による表形式データの集計処理におけるコンパイル処理の説明図である。 本発明の一実施形態による表形式データの集計処理におけるコンパイル処理の説明図である。

符号の説明

　１００　　　分散メモリ型マルチプロセッサ
　１１０，１２０，１３０，１４０　　　演算ユニット
　１１１，１２１，１３１，１４１　　　プロセッサ
　１１２，１２２，１３２，１４２　　　ローカルメモリ
　１５０　　　インターコネクト
　２００　　　コンピュータシステム
　２０２　　　分散メモリ型マルチプロセッサ
　２１０　　　ＣＰＵ
　２１２　　　ＲＡＭ
　２１４　　　ＲＯＭ
　２１６　　　記憶装置
　２１８　　　ＣＤ－ＲＯＭ
　２２０　　　ＣＤ－ＲＯＭドライバ
　２２２　　　Ｉ／Ｆ
　２２４　　　入力装置
　２２６　　　表示装置
　２２８　　　バス
　５００　　　表形式データ
　５０１　　　データ項目「Ｓｃｈｏｏｌ」
　５０２　　　データ項目「Ａｇｅ」
　５１０　　　レコード０
　５１１　　　レコード１４
　５２０，５２１，・・・，５２７　　　ブロック
　５３０　　　順序情報
　５３１　　　項目情報「Ｓｃｈｏｏｌ」
　５３２　　　項目情報「Ａｇｅ」
　５５０－０，５５０－１，・・・，５５０－７　　　ブロック単位順序情報
　５５１－０，５５１－１，・・・，５５１－７　　　レコード順序番号配列
　５５２－０，５５２－１，・・・，５５２－７　　　項目値アクセス情報配列
　５６０－０，５６０－１，・・・，５６０－７　　　ブロック情報「Ｓｃｈｏｏｌ」
　５６１－０，５６１－１，・・・，５６１－７　　　ローカル項目値番号配列「Ｓｃｈｏｏｌ」
　５６２－０，５６２－１，・・・，５６２－７　　　ローカル項目値配列「Ｓｃｈｏｏｌ」
　５８０－０，５８０－１，・・・，５８０－７　　　ブロック情報「Ａｇｅ」
　５８１－０，５８１－１，・・・，５８１－７　　　ローカル項目値番号配列「Ａｇｅ」
　５８２－０，５８２－１，・・・，５８２－７　　　ローカル項目値配列「Ａｇｅ」
　５８３－０，５８３－１，・・・，５８３－７　　　グローバル項目値順序番号配列「Ａｇｅ」

　以下、本発明を実施するための種々の形態を図面と共に詳細に説明する。

　［分散メモリ型マルチプロセッサ］
　最初に、本発明の一実施例によるデータ処理を実現する分散メモリ型マルチプロセッサについて説明する。図１は分散メモリ型マルチプロセッサの一実施形態の概略図である。分散メモリ型マルチプロセッサ１００は、複数台（たとえば、２台、４台、８台等、本例では４台）の演算ユニット１１０、１２０、１３０、１４０を含む。各演算ユニット１１０、１２０、１３０、１４０は、データ処理用のプロセッサ１１１、１２１、１３１、１４１と、プロセッサと直接接続されている専用のローカルメモリ１１２、１２２、１３２、１４２とを含む。各演算ユニット１１０、１２０、１３０、１４０は、演算ユニット間で高速データ通信を可能にするインターコネクト１５０によって接続されている。図示されていないが、演算ユニット１１０、１２０、１３０、１４０は、キャッシュメモリを備えていてもよい。また、演算ユニットは、他の演算ユニットのローカルメモリへのアクセス（リモートアクセス）を可能にする構成でも構わない。その場合、演算ユニットは、リモートアクセスのためのキャッシュメモリをさらに含むことがある。また、ＮＵＭＡ（不均一メモリアクセス）方式のように、各演算ユニットのローカルメモリが全体として論理的に連続した１つのメモリとして見えるように構成されていても構わない。

　また、演算ユニット内のプロセッサは、シングルコアプロセッサでもよく、又は、２つ以上のプロセッサコアを含むマルチコアプロセッサでもよい。その場合、演算ユニット内のローカルメモリは、プロセッサコア間で共有メモリとして使用されることがある。

　［演算ユニットの機能的構成］
　各演算ユニットは、表形式データのような一連のデータが複数台の演算ユニットのパイプライン処理によって操作されるように構成することができる。この場合、各演算ユニットは、前のパイプライン段にある１台以上（たとえば、２台）の演算ユニットからそれぞれのローカルデータを受信し、少なくとも２つ（たとえば、２つ）の受信されたローカルデータを１つのさらなるローカルデータに変換し、さらなるローカルデータを後のパイプライン段にある１台の演算ユニットへ送信するマージ手段を含む。これらの複数台の演算ユニットのマージ手段は最終的に１つのグローバルデータを生成するようにトーナメント方式で動的に接続可能である。ここで、「動的」とは、トーナメント表の段数、トーナメント表内での各演算ユニットの配置などが、マージされるべき対象に応じて可変であることを意味している。さらに、少なくとも１台のいずれかの演算ユニットは、一連のデータを複数個のブロックに分割したときに各ブロックに付与された、すなわち、各ブロックが割り当てられた演算ユニットに付与されたブロック番号に基づいて、マージによって生成されたデータを分割し、複数台の演算ユニットへ割り当てる分配手段を含む。

　より詳細には、演算ユニット内のプロセッサがシングルコアプロセッサの場合、一連のデータから得られる各ブロックは演算ユニット毎に、すなわち、演算ユニット内のシングルコアプロセッサに対応付けられる。一方、マルチコアプロセッサの場合、一連のデータから得られる各ブロックは、演算ユニット内のプロセッサコア毎に対応付けられる。よって、複数のブロックが１台の演算ユニットに関連付けられ、ブロックに関する種々の処理は、演算ユニット内のプロセッサコアの単位で実行されることになる。以下の説明中、演算ユニット内のプロセッサは、シングルコアプロセッサ、又は、マルチコアプロセッサのいずれでも構わない。以下では、説明を簡単化するため、特に断らない限り、発明の実施例は、演算ユニットがシングルコアプロセッサであるかのように、演算ユニットの単位で記載されている。しかし、演算ユニット内のプロセッサがマルチコアプロセッサである場合でも、１台の演算ユニットのプロセッサが１つのコアプロセッサに対応しているとみなすならば、以下の説明がこの場合に同様に適用できることに注意を要する。

　［コンピュータシステム構成］
　図２は、本発明の一実施形態による大規模な一連のデータを操作するコンピュータシステム２００の概略図である。コンピュータシステム２００は、一連のデータを複数台の演算ユニットによって分担して操作する、図１に示されているような、分散メモリ型マルチプロセッサ２０２を備えている。図２に示されているように、コンピュータシステム２００は、さらに、プログラムを実行することによりシステム全体および個々の構成部分を制御するＣＰＵ２１０と、ワークデータ等を記憶する、たとえば、ＲＡＭ(Random Access Memory)のようなメモリ２１２と、プログラム等を記憶するＲＯＭ(Read Only Memory)２１４と、ハードディスク等の記憶装置２１６と、ＣＤ－ＲＯＭ２１８をアクセスするためのＣＤ－ＲＯＭドライバ２２０と、ＣＤ－ＲＯＭドライバ２２０及び外部ネットワーク等（図示せず）へ繋がれた外部端子に接続されているインターフェイス（Ｉ／Ｆ）２２２と、キーボード及びマウス等のような入力装置２２４と、コンピュータモニターのような表示装置２２６とを備えている。プロセッサ２１０、ＲＡＭ２１２、ＲＯＭ２１４、記憶装置２１６、Ｉ／Ｆ２２２、入力装置２２４及び表示装置２２６は、バス２２８を介して相互に接続されている。

　一連のデータの操作をコンピュータシステム２００の分散メモリ型マルチプロセッサ２０２に実行させるプログラムは、ＣＤ－ＲＯＭ２１８に収容され、ＣＤ－ＲＯＭドライバ２２０に読取られても良いし、ＲＯＭ２１４に予め記憶されていても良い。また、いったんＣＤ－ＲＯＭ２１８から読み出したものを、外部記憶媒体２１６の所定の領域に記憶しておいても良い。或いは、上記プログラムは、ネットワーク（図示せず）、外部端子、及び、Ｉ／Ｆ２２２を介して、外部から供給されるものであっても良い。

　また、本発明の一実施形態による分散メモリ型コンピュータは、コンピュータシステム２００に一連のデータを操作するプログラムを実行させることにより実現される。

　図２に示されているコンピュータシステム２００では、分散メモリ型マルチプロセッサ２０２の他にＣＰＵ２１０が設けられ、システム全体及び個々の構成部分を制御している。しかし、本発明は、このような実施形態に限定されることはなく、代替的な実施形態では、分散メモリ型マルチプロセッサ２０２に含まれている演算ユニットがシステム全体及び個々の構成部品を制御する。

　［情報ブロックに基づくデータ管理機構］
　図３は本発明の基礎となるデータ管理機構を説明するための表形式データの一例を表す図である。この表形式データは、上述の国際公開第ＷＯ００／１０１０３号に提案したデータ管理機構を用いることにより、コンピュータ内では図４に示されるようなデータ構造として記憶される。このデータ構造は、市販されているコンピュータ、たとえば、パーソナルコンピュータのハードウェア資源、特に、プロセッサ及びメモリを使用して大規模な表形式データの検索、ソート、集計等を実現するために提案された、コンピュータのメモリ上に置かれる表形式データのデータ構造であることに注意すべきである。

　なお、本書中では、「元の表形式データ中でレコードが収容されている位置を表す情報（すなわち、原始レコード位置番号）」と「レコードの並び順を表す情報（すなわち、レコード順序番号）」とが区別されている。原始レコード位置番号は、データ項目に対応した項目値を含む個々のレコードを特定するために利用される仮想的な情報である。たとえば、通常の表形式データを情報ブロックに基づく表形式データに変換する際に、元々の通常の表形式データ中でレコードが収容されている位置が原始レコード位置番号によって表される。一般に、情報ブロックに基づく表形式データでは、レコードが常に原始レコード位置番号の順番に配列されているとは限らない。たとえば、表形式データをある項目の項目値に関して昇順にソートすると、ソート後の表形式データのレコードの並び順は元の表形式データのレコードの並び順とは異なる。但し、通常の表形式データから変換された直後の情報ブロックに基づく表形式データ中のレコードは、レコードが原始レコード位置番号の順番に並べられていることがあり、この場合には、原始レコード位置番号とレコード順序番号とが初期的に一致している。

　図４に示すように、表形式データの各レコードの並び順の番号（レコード順序番号）と、原始レコード位置番号は、レコード順序指定配列４０１（以下、この配列を「ＯｒｄＳｅｔ」のように略記する。）によって対応付けられる。レコード順序指定配列４０１は、レコード順序番号の順に原始レコード位置番号を格納している。図４の例では、レコードは原始レコード位置番号の順番に並べられている。

　ここで、本明細書中での配列の記法について説明する。一般に、配列Ａは、添字をｉとすると、配列の要素がＡ［ｉ］のように表記できるが、図面中では、配列は実線で囲まれた領域内に示され、要素Ａ［ｉ］と要素Ａ［ｉ＋１］の境界は点線で示されている。また、要素Ａ［ｉ］の添字ｉが要素Ａ［ｉ］の左側に示されている。また、配列の添字ｉは０から始まる整数で表されている。

　もう一度図４に戻ると、性別に関しては、表形式データのレコード順序番号＝０に対応する原始レコード位置番号は、配列ＯｒｄＳｅｔ［０］から「０」であることがわかる。原始レコード位置番号が「０」であるレコードに関する実際の性別の値、即ち、「男」又は「女」は、実際の値が所定の順序（たとえば、昇順又は降順）に従ってソートされた値リストである項目値配列４０３（以下、項目値配列、すなわち、値リストを「ＶＬ」のように略記する。）へのポインタ配列である項目値番号配列４０２（以下、項目値番号配列、すなわち、ポインタ配列を「ＶＮｏ」のように略記する。）を参照することによって取得できる。ポインタ配列４０２は、配列ＯｒｄＳｅｔ４０１に格納されている原始レコード位置番号の順番に従って、実際の値リスト４０３中の要素を指し示すポインタを格納している。これにより、表形式データのレコード「０」に対応する性別の項目値は、（１）配列ＯｒｄＳｅｔ４０１からレコード順序番号＝０に対応する原始レコード位置番号＝０を取り出し、（２）値リストへのポインタ配列４０２から原始レコード位置番号＝０に対応する要素「１」を取り出し、（３）値リスト４０３から、値リストへのポインタ配列３０２から取り出された要素「１」によって指し示される要素「女」を取り出すことにより取得できる。

　他のレコードに対しても、また、年齢及び身長に関しても同様に項目値を取得することができる。

　このように表形式データは、値リストＶＬと、値リストへのポインタ配列ＶＮｏの組合せにより表現され、この組合せを、特に、「情報ブロック」と称する。図４には、性別、年齢及び身長に関する情報ブロックがそれぞれ情報ブロック４０８、４０９及び４１０として示されている。

　単一のコンピュータが単一のメモリ（物理的には複数であっても良いが、単一のアドレス空間に配置されアクセスされるという意味で単一のメモリ）を有するならば、単一のコンピュータは、当該メモリに、順序集合の配列ＯｒｄＳｅｔ、各情報ブロックを構成する値リストＶＬおよびポインタ配列ＶＮｏとを記憶しておけばよい。しかしながら、本発明の種々の実施形態では、表形式データの操作は、ローカルメモリを伴う複数台の演算ユニットにより構成された分散メモリ型マルチプロセッサによって行われる。そのため、効率的な並列処理を実現するために、表形式データを保持する新たな仕組みが提案されている。

　［分散メモリ型マルチプロセッサ向けデータ構造］
　次に、本発明の一実施形態による分散メモリ型マルチプロセッサ向けデータ構造について説明する。図５Ａ乃至５Ｄは本発明の一実施形態によるデータ構造の説明図である。図５Ａは表形式データの一例を示している。図５Ａに示された表形式データ５００は、「Ｓｃｈｏｏｌ」というデータ項目５０１に対応した項目値（たとえば、「Ｗｅｓｔ」、「Ｓｏｕｔｈ」、「Ｎｏｒｔｈ」及び「Ｅａｓｔ」と、「Ａｇｅ」というデータ項目５０２に対応した項目値（たとえば、「１２」、「８」、「１１」、「１０」など）とを含むレコードの配列として表される。この表形式データ５００のレコードは、先頭から順番に、レコード順序番号＝０、１、２、・・・、３１の順番に並んでいる。配列の先頭に位置するレコード５１０は、レコード順序番号０が付与されたレコードである。レコード５１０のデータ項目「Ｓｃｈｏｏｌ」の項目値は「Ｗｅｓｔ」であり、データ項目「Ａｇｅ」の項目値は「１２」である。レコード５１１のデータ項目「Ｓｃｈｏｏｌ」の項目値は「Ｎｏｒｔｈ」であり、データ項目「Ａｇｅ」の項目値は「９」である。ここで、この表形式データのレコードがソート処理によって並び替えられると、各レコードに付与されるレコード順序番号は変化することに注意すべきである。

　本発明の一実施形態による分散メモリ型マルチプロセッサ向けデータ構造では、この表形式データのレコードは、ブロック番号（本例では、０から７の８個のブロック番号）によって識別されるブロック５２０、５２１、・・・、５２７に分割される。初期的には、このブロックは、このブロックに含まれるレコードの処理を担当する分散メモリ型マルチプロセッサの演算ユニット、より詳しくは、演算ユニットのプロセッサに関連付けられている。

　分散メモリ型マルチプロセッサ向けデータ構造は、レコードの並び順（すなわち、レコード順序番号）と、データ構造内の項目値の格納場所とを対応付ける順序に関する情報（順序情報）と、データ項目毎の項目値に関する情報（項目情報）とによって構成される。順序情報は、機能的に上記の本発明の基礎となるデータ管理機構におけるレコード順序指定配列ＯｒｄＳｅｔに対応し、項目情報は、同様に情報ブロックに対応している。順序情報と項目情報は、共にグローバルメモリに保持され、必要に応じて、それらの一部が各演算ユニットのローカルメモリへ転送される。図５Ｂは順序情報５３０を示し、図５Ｃ及び５Ｄは、それぞれ、データ項目「Ｓｃｈｏｏｌ」及びデータ項目「Ａｇｅ」の項目情報５３１及び５３２を示している。

　本実施形態のデータ構造では、レコード毎に当該レコードの操作を担当する演算ユニットが定められる。よって、（複数の）レコードは、各演算ユニットが担当するレコード、すなわち、担当レコードに分割され、担当レコード毎にブロック番号が割り当てられる。本実施形態のように、ブロックと演算ユニットが１対１に対応しているならば、各演算ユニットはブロック番号を保存する必要はない。なお、レコード順序番号をｉとすると、後述されるブロック番号配列ＢｌｋＮｏ［ｉ］は、レコード順序番号ｉをもつレコードが属するブロックのブロック番号がＢｌｋＮｏ［ｉ］であることを表している。たとえば、図５Ａの例では、レコード順序番号０から３のレコードはブロック番号０のブロックに含まれ、レコード順序番号４から７のレコードはブロック番号１のブロックに含まれ、以下同様である。

　本実施形態のデータ構造によれば、全レコードはブロックに対応した担当レコードに分割されるので、ブロック毎に、担当レコードのそれぞれを元の表形式データのレコードと対応付ける情報が必要になる。そのため、順序情報５３０は、ブロック毎に、担当レコードのレコード順序番号がレコード順序番号の順番に格納されているレコード順序番号配列５５１－０、５５１－１、５５１－２、・・・、５５１－７を含む。レコード順序番号配列は、以下では、ＧＯｒｄという名前で呼ばれることがある。たとえば、図５Ｂの例では、ブロック番号０というブロックに属する担当レコードのレコード順序番号は、０、１、２、３であり、ブロック番号１というブロックに属する担当レコードのレコード順序番号は、４、５、６、７であり、以下同様である。レコード順序番号配列は、各ブロックに属する担当レコードの数と同じサイズを有し、レコード順序番号が昇順に格納されている整数型の配列である。また、レコード順序番号配列は、各演算ユニットのローカルメモリに収容可能なサイズに分割され、各演算ユニット内のローカルメモリに記憶されている。

　ここで、ブロック番号配列とレコード順序番号配列５５１－０、５５１－１、５５１－２、・・・、５５１－７は、相互に変換可能であることに注意すべきである。たとえば、レコード順序番号ｉをもつレコードが属するブロックのブロック番号がＢｌｋＮｏ［ｉ］で表現され、ブロック番号＝ｊであるブロックに属するレコード順序番号配列の添字ｋに対応する要素がＧＯｒｄ［ｊ］［ｋ］で表現されるとする。このとき、レコードの総数をＲｍａｘとすると、ブロック番号配列からレコード順序番号配列への変換は、
ｆｏｒ　（ｉ＝０；ｉ＜Ｒｍａｘ；ｉ＋＋）　｛
　　　　ＧＯｒｄ［ＢｌｋＮｏ［ｉ］］［J［ＢｌｋＮｏ［ｉ］］］＝ｉ；
　　　　J［ＢｌｋＮｏ［ｉ］］＋＋；
｝
として表現される。ここで、配列Ｊの要素J［ＢｌｋＮｏ［ｉ］］は、ブロック番号がＢｌｋＮｏ［ｉ］であるブロックに属するレコード順序番号配列ＧＯｒｄ［ＢｌｋＮｏ［ｉ］］の要素を指定する添字を表している。なお、配列Jは全要素が０に初期化されている。

　逆に、レコード順序番号配列からブロック番号配列への変換は、ブロック番号をｉ、ブロックの総数をＢｍａｘ、各ブロック内のレコードの総数をＢＲｍａｘ［ｉ］によって表現すると、以下のように記述される。すなわち、
ｆｏｒ　（ｉ＝０；ｉ＜Ｂｍａｘ；ｉ＋＋）｛
　　　　ｆｏｒ　（ｊ＝０；ｊ＜ＢＲｍａｘ［ｉ］；ｊ＋＋）　｛
　　　　　　　　ＢｌｋＮｏ［ＧＯｒｄ［ｉ］］［ｊ］＝ｉ；
　　　　｝
｝
となる。

　このように、ブロック番号配列とレコード順序番号配列は相互変換が可能であるため、何れか一方が準備されているならば十分である。

　さらに、各レコードに含まれる項目値は、後述する項目情報の形で保持されているので、各演算ユニットは、担当レコードに含まれる項目値をアクセスするためのアドレス情報、すなわち、項目値アクセス情報を取得することが必要である。よって、本実施形態のデータ構造によれば、順序情報５３０は、ブロック毎に、担当レコードの項目値アクセス情報がレコード順序番号の順番に格納されている項目値アクセス情報配列５５２－０、５５２－１、５５２－２、・・・、５５２－７をさらに含む。この項目値アクセス情報配列は整数型の配列であり、項目値アクセス情報配列のサイズは担当レコードのレコード数に一致する。項目値アクセス情報配列は、ＬＯｒｄという名前で呼ばれることもある。たとえば、図５Ｂの例では、ブロック番号０というブロックに含まれるレコード順序番号が０というレコードに含まれる項目値は、このブロック番号０に関して、０という項目値アクセス情報によってアクセス可能であり、ブロック番号１というブロックに含まれるレコード順序番号が５というレコードに含まれる項目値は、このブロック番号１に関して、１という項目値アクセス情報によってアクセス可能である。

　次に、本実施形態によれば、項目情報は、データ項目毎の項目情報として保持される。たとえば、図５Ｃ及び５Ｄの例では、データ項目「Ｓｃｈｏｏｌ」に関する項目情報５３１とデータ項目「Ａｇｅ」に関する項目情報５３２とが各演算ユニットのローカルメモリに分割され記憶される。そして、ブロック毎の担当レコードに含まれる項目値は、データ項目毎に各演算ユニットが項目値アクセス情報配列を用いてアクセスすることができるように各演算ユニットのローカルメモリに保持される。項目値そのものは、データ項目毎に、一意の項目値が所定の順序（昇順又は降順）に格納されているローカル項目値配列ＬＶＬとしてローカルメモリ上に構築されている。たとえば、図５Ｃ及び５Ｄの例では、データ項目「Ｓｃｈｏｏｌ」に関する項目値は、ローカル項目値配列５６２－０、５６２－１、・・・、５６２－７として各演算ユニットのローカルメモリに保持され、データ項目「Ａｇｅ」に関する項目値は、ローカル項目値配列５８２－０、５８２－１、・・・、５８２－７として各演算ユニットのローカルメモリに保持されている。ローカル項目値配列は、項目値そのものを格納する配列であるため、整数型、浮動小数点型、文字列型などの様々なデータ型をとる。

　項目情報は、担当レコードに関連した項目値アクセス情報を用いて、グローバル項目値配列に格納されている項目値を特定できるように構成されている。そのため、項目情報は、データ項目毎に、担当レコードに含まれる項目値を特定するローカル項目値番号がレコード順序番号の順番（たとえば、昇順又は降順）に格納されているローカル項目値番号配列と、ローカル項目値番号によって表される項目値が表形式データ全体に保持されている一意の項目値の配列（以下では、グローバル項目値配列と呼ばれることがある）に格納されている位置を指定するグローバル項目値順序番号配列とを含む。なお、グローバル項目値配列は実際にメモリ上に構築される必要はないことに注意を要する。ローカル項目値番号配列及びグローバル項目値順序番号配列はブロック毎に設けられ、各演算ユニットのローカルメモリに記憶される。ローカル項目値番号配列は、担当レコードのレコード数に一致するサイズを有する整数型配列であり、ＶＮｏという名前で呼ばれることもある。グローバル項目値順序番号配列は、担当レコードに含まれる一意の項目値の数と同じサイズを有する整数型配列であり、ＧＶＯｒｄという名前で呼ばれることもある。

　図５Ｃの例では、データ項目「Ｓｃｈｏｏｌ」に関して、項目情報５３１は、ローカル項目値番号配列５６１－０、５６１－１、・・・、５６１－７と、ローカル項目値配列５６２－０、５６２－１、・・・、５６２－７と、グローバル項目値順序番号配列５６３－０、５６３－１、・・・、５６３－７とを含む。ローカル項目値番号配列、ローカル項目値配列、及び、グローバル項目値順序番号配列は、いずれもブロック毎に分割されている。同図において、たとえば、Ｂｌｏｃｋ－０のローカル項目値番号配列ＶＮｏの先頭の要素の値は「１」である。これは、値が「０」である項目値アクセス情報によって指定されたレコードに含まれる項目値の項目値番号が「１」であることを意味する。項目値番号が「１」である項目値は、ローカル項目値配列ＬＶＬの２番目の要素、すなわち、ＬＶＬ［１］を参照することにより、「Ｗｅｓｔ」であることがわかる。さらに、この項目値は、グローバル項目値順序番号配列の２番目の要素、すなわち、ＧＶＯｒｄ［１］を参照することにより、仮想的なグローバル項目値配列の３番目の要素であること、すなわち、表形式データの全体の中でのこの項目値の順序番号は「３」であることがわかる。その他のブロックに関しても、また、その他のデータ項目に関しても、同様である。

　このように、本実施形態のデータ構造によれば、各ブロックに属するレコードに含まれる項目値は、ブロック内で各項目値に付けられたローカル項目値番号と、このローカル項目値番号に対応付けられているローカル項目値配列とによって表現されている。

　［分散メモリ型マルチプロセッサ向けデータ構造の構築］
　図６は、本発明の一実施形態による分散メモリ型マルチプロセッサ向けデータ構造を各演算ユニットのローカルメモリ上に構築する方法のフローチャートである。本方法によれば、分散メモリ型マルチプロセッサ２０２の複数台の演算ユニットが並列的に動作して、分散メモリ型マルチプロセッサ向けの表形式データ構造を演算ユニットのローカルメモリに構築する。演算ユニットの受信部は、並列的に動作して、たとえば、記憶装置２１６、Ｉ／Ｆ２２２を介して接続されているネットワーク上の機器などの外部装置から、表形式データのうちそれぞれの演算ユニットに割り当てられた担当レコードを受信し、専用のローカルメモリに格納する（ステップ６０２）。次に、演算ユニットの順序情報作成部は、並列的に動作して、受信された担当レコードから、レコード順序番号配列及び項目値アクセス情報配列を生成し、専用のローカルメモリに格納する（ステップ６０４）。次に、演算ユニットのローカルコンパイル部は、並列的に動作して、項目毎に、担当レコード中の項目値を所定の順序（たとえば、昇順又は降順）でソートすることにより、ローカル項目値配列、及び、ローカル項目値番号配列を生成し、この演算ユニットの専用のローカルメモリに格納する（ステップ６０６）。続いて、演算ユニットの送信部は、並列的に動作して、項目毎に、ローカル項目値配列、担当レコードの範囲内で所定の順序に基づいてローカル項目値配列に含まれる一意の項目値に割り当てられた順序番号が格納されているローカル項目値順序番号配列、及び、ローカル項目値順序番号配列中の順序番号に関連した担当レコードを示すブロック番号を含むブロック番号配列を、ローカルデータとして、この演算ユニットの後のパイプライン段にある演算ユニットへ送信する（ステップ６０８）。さらに、演算ユニットのマージ部は、並列的に動作して、前のパイプライン段からの２つのローカルデータに含まれている２つのローカル項目値配列中の項目値を所定の順序でマージすることにより、２つのローカルデータを、さらなるブロック番号配列、さらなるローカル項目値順序番号配列及びさらなるローカル項目値配列により形成された１つのローカルデータに変換する（ステップ６１０）。さらに、いずれかの演算ユニットの分配部は、最終的に生成されたさらなるローカル項目値順序番号配列に格納されている順序番号を、対応する最終的に生成されたさらなるブロック番号配列に格納されているブロック番号に関連付けられた演算ユニットへ送信する（ステップ６１２）。最後に、演算ユニットの順序番号格納部は、並列的に動作して、専用のローカルメモリに確保されたグローバル項目値順序番号配列に、送信された順序番号を順次に格納する（ステップ６１４）。

　［項目値の取得処理］
　次に、本発明の一実施形態による分散メモリ型マルチプロセッサ向けデータ構造における表形式データの項目値の取得について説明する。図７は、本発明の一実施形態による項目値取得方法のフローチャートである。項目値は、図５Ａ乃至５Ｄを参照して説明したように、データ項目毎に、項目情報の形で各演算ユニットのローカルメモリ上に保持されている。よって、たとえば、分散メモリ型マルチプロセッサは、指定されたレコードに含まれる項目値を容易に取得することができる。また、表形式データは、演算ユニットの担当レコードに分割され、演算ユニット毎に独立して保持されている。よって、各演算ユニットは、他の演算ユニットとは完全に独立に、この演算ユニットのローカルメモリに保持されている項目値を取得することが可能である。本実施形態では、多数の演算ユニットが同時に動作することにより、多数のレコードに含まれる項目値を同時に取得するような状況も考慮している。このような状況においても、項目値取得の基本動作は、ある特定の演算ユニットが担当レコード中のあるレコードに含まれる項目値を取得する処理であることが理解されるであろう。

　図７に示されているように、各演算ユニットは、レコード順序番号が指定されると、指定されたレコード順序番号がローカルメモリに保持されているレコード順序番号配列に存在するかどうかを判定する（ステップ７０２）。もし、指定されたレコード順序番号が存在しなければ（ステップ７０２でＮｏ）、プロセスは終了する。指定されたレコード順序番号が存在するならば、演算ユニットは、指定されたレコード順序番号がレコード順序番号配列内で格納されている位置を特定し、特定された位置によって指定される項目値アクセス情報配列中の項目値アクセス情報を読み出す（ステップ７０４）。その後、演算ユニットは、項目毎に、読み出された項目値アクセス情報によって指定されるローカル項目値番号配列中のローカル項目値番号を読み出す（ステップ７０６）。続いて、演算ユニットは、項目毎に、読み出されたローカル項目値番号によって指定されるローカル項目値配列中の項目値を特定する（ステップ７０８）。最後に、演算ユニットは、未だ項目値が特定されていない項目が存在するかどうかを判定する（ステップ７１０）。未だ項目値が特定されていない項目が存在するならば（ステップ７１０でＹｅｓ）、プロセスはステップ７０６へ戻り、次の項目に関する処理を継続する。すべての項目値が特定されているならば（ステップ７１０でＮｏ）、プロセスは終了する。

　本実施形態によるデータ取得の一例を、図５Ａ乃至５Ｄに示されたデータ構造を用いて、より詳細に説明する。たとえば、レコード順序番号＝１４であるレコード、図５Ａ乃至５Ｄでは、符号５１１で示されたレコードの項目値を取得することを考える。各演算ユニットがこの演算ユニットのローカルメモリに保持されているレコード順序番号配列を参照すると、ブロック番号＝３に対応するブロックＢｌｏｃｋ－３を担当する演算ユニットだけが、指定されたレコード順序番号＝１４であるレコードを担当していると判定する。この演算ユニットは、レコード順序番号配列ＧＯｒｄ中でレコード順序番号＝１４が格納されている位置が２であること、すなわち、ＧＯｒｄ［２］＝１４であることがわかるので、項目値アクセス情報配列から、レコード順序番号＝１４の項目値アクセス情報、すなわち、ＬＯｒｄ［２］＝２を読み出す。なお、レコード順序番号配列の中で、レコード順序番号＝１４が格納されている位置は、この演算ユニットの担当レコード中での対象レコードの順位（ランク）とも称される。レコード順序番号配列は、昇順の配列であるため、この格納位置は、周知の２分割法などによって効率的に見つけられる。

　次に、この演算ユニットは、項目毎に、ローカル項目値番号配列ＶＮｏから、項目値アクセス情報によって指定されるローカル項目値番号を読み出し、読み出されたローカル項目値番号によって指定される項目値をローカル項目値配列から読み出す。たとえば、項目＝Ｓｃｈｏｏｌの場合、ＬＶＬ［ＶＮｏ［ＬＯｒｄ［２］］］＝ＬＶＬ［ＶＮｏ［２］］＝ＬＶＬ［０］＝Ｎｏｒｔｈであることから、項目＝Ｓｃｈｏｏｌの項目値＝Ｎｏｒｔｈが特定される。同様に、項目＝Ａｇｅに関して、ＬＶＬ［ＶＮｏ［ＬＯｒｄ［２］］］＝ＬＶＬ［ＶＮｏ［２］］＝ＬＶＬ［２］＝９という項目値が特定される。

　［表形式データのコンパイル処理］
　次に、本発明の一実施形態による表形式データから分散メモリ型マルチプロセッサ向けデータを作成するコンパイル処理について説明する。以下では、図５Ａ乃至５Ｄに示されたデータ構造に関連して、本発明の一実施形態によるコンパイル処理が記述される。図８は、本発明の一実施形態によるコンパイル処理の概略的なフローチャートである。

　担当レコード取得：本実施形態によれば、最初に、表形式データのうち、各演算ユニットによって担当される担当レコードが演算ユニットに取り込まれる（ステップ８０２）。当然ながら、１台の演算ユニットに複数のプロセッサが収容されているならば、プロセッサ毎に担当レコードが取り込まれ、ブロック単位の処理はプロセッサ毎に実行される。

　順序情報作成：次に、レコード順序番号配列及び項目値アクセス情報配列からなる順序情報が各演算ユニットのローカルメモリ上に作成される（ステップ８０４）。上述のように、レコード順序番号配列及び項目値アクセス情報配列は、複数台の演算ユニットによって並列的に作成される。

　ブロック内コンパイル：次に、複数台の演算ユニットが並列的に動作して、データ項目毎に、単一のブロックに含まれる担当レコードの原始レコード位置番号の順番に、ローカル項目値番号を格納するローカル項目値番号配列を作成し、同時に、複数台の演算ユニットは、担当レコードに含まれる項目値のうちの一意の値を所定の順序（たとえば、昇順又は降順）に格納するローカル項目値配列も作成する（ステップ８０６）。

　ブロック間コンパイル１（マージ）：次に、複数台の演算ユニットが並列的かつ階層的に動作して、データ項目毎に、少なくとも２個（本実施例では、２個）のブロックに関連した、ブロック番号配列、ローカル項目値配列、及び、ローカル項目値配列に格納されている項目値が表形式データ全体に含まれる一意の項目値を所定の順序で格納する仮想的なグローバル項目値配列中に格納されている位置を指定するポインタがローカル項目値番号の順番に格納されているグローバル項目値順序番号配列からなる１対の組から、２個のブロックをマージしたブロックに関連した、ブロック番号配列、ローカル項目値配列、及び、グローバル項目値順序番号配列からなる組を作成するマージ処理を実行する。演算ユニットは、最終的に１個のブロックにマージされるまでこのマージ処理を繰り返し実行し、最終的なブロック番号配列、最終的なローカル項目値配列、及び、最終的なグローバル項目値順序番号配列を作成する（ステップ８０８）。

　ブロック間コンパイル２（分配）：最後に、少なくとも１台の演算ユニットが、データ項目毎に、最終的なグローバル項目値順序番号配列中の要素を最終的なブロック番号配列中の対応する要素によって指定されたブロック番号毎に、各ブロックを担当する演算ユニットへ順次に分配することにより、各演算ユニットのローカルメモリ上に各演算ユニットの担当レコードに関するグローバル項目値順序番号配列が作成される（ステップ８１０）。

　以上のステップにより、図５Ａに示された表形式データから、図５Ｂに示されたレコード順序番号配列及び項目値アクセス情報配列と、図５Ｃに示された、データ項目＝Ｓｃｈｏｏｌに関するローカル項目値番号配列、ローカル項目値配列及びグローバル項目値順序番号配列と、図５Ｄに示された、データ項目＝Ａｇｅに関するローカル項目値番号配列、ローカル項目値配列及びグローバル項目値順序番号配列とが各演算ユニットのローカルメモリ上に作成される。

　以下、図５Ａ乃至５Ｄに示された表形式データに関連して、本発明の一実施形態によるコンパイル処理をより詳細に説明する。図９Ａ及び９Ｂは本発明の一実施形態による順序情報作成処理の説明図である。図９Ａ及び９Ｂに示されたデータは図５Ａ及び５Ｂに示されたデータと同じデータであり、図９Ａの表形式データ５００から、図９Ｂの順序情報５３０が作成される。順序情報作成処理については上述の通りである。レコード順序番号配列ＧＯｒｄには、元の表形式データの行番号がそのまま設定され、項目値アクセス情報配列ＬＯｒｄには、０から始まる連続番号が設定される。順序情報作成処理は、複数台の演算ユニットによって並列的に実行される。

　図１０Ａ乃至１０Ｃは、本発明の一実施形態によるブロック内コンパイル処理の概要図である。ブロック内コンパイル処理によれば、図１０Ａに示された表形式データから、図１０Ｂ及び図１０Ｃに示されたデータ項目＝“Ｓｃｈｏｏｌ”に関する項目情報及びデータ項目＝“Ａｇｅ”に関する項目情報が作成される。同図に示されているように、項目情報には、ローカル項目値番号配列ＶＮｏとローカル項目値配列ＬＶＬとが含まれている。ブロック内コンパイル処理は、Ｂｌｏｃｋ－０、Ｂｌｏｃｋ－１、・・・、Ｂｌｏｃｋ－７というブロック毎に、各演算ユニットによって並列に実行される。

　ここで、１つのブロックについてのブロック内コンパイル処理の一実施例について説明する。図１１は、本発明の一実施形態によるブロック内コンパイル処理の概要図である。本例では、ブロック番号＝１のデータ項目＝Ｓｃｈｏｏｌに関する４行（レコード数＝４）のＳｃｈｏｏｌ（すなわち、原始レコード位置番号の順序に項目値が格納されている項目値配列Ｓｃｈｏｏｌ）から、ローカル項目値番号配列ＶＮｏとローカル項目値配列ＬＶＬを作成する。ローカル項目値配列ＬＶＬは、項目値配列Ｓｃｈｏｏｌに含まれている項目値から抽出された一意の項目値が所定の順序（本例では、アルファベットの昇順）に格納されている値のリストである。一方、ローカル項目値番号配列ＶＮｏは、ｉが原始レコード位置番号を表すとき、元の項目値配列Ｓｃｈｏｏｌの要素であるＳｃｈｏｏｌ［ｉ］とローカル項目値配列ＬＶＬ［ｊ］との間に、
Ｓｃｈｏｏｌ［ｉ］＝ＬＶＬ［ＶＮｏ［ｉ］］
という関係が成り立つような配列である。なお、以下の処理は、演算ユニットが演算ユニットのローカルメモリを使用して実行する。

　次に、ブロック内コンパイル処理の一実施例をより詳細に説明する。図１２Ａ乃至１２Ｅは、本発明の一実施形態によるブロック内コンパイル処理の説明図である。図１２Ａに示されているような項目値配列が演算ユニットのローカルメモリに作成される。続いて、図１２Ｂに示されるように、項目値配列の各要素の配列内での位置を表す値を格納した配列、すなわち、項目値配列をＡ［ｉ］とするとき、位置配列Ｂ［ｉ］＝ｉとなる配列Ｂをローカルメモリ上に作成する。ここで、項目値配列Ａの要素を、項目値をキーとして、項目値の昇順にソートし、同時に、位置配列Ｂの要素もソートする。これにより、図１２Ｃに示されるような項目値配列Ａ及び位置配列Ｂが得られる。続いて、一意の項目値に０から順番に項目値番号を付与して項目値番号配列Ｃを生成する。これにより、項目値番号を用いて項目値が重複なくアクセスできるようになる。そして、項目値を項目値番号の順に並べ換えると、図１２Ｄに示されるように、ローカル項目値配列ＬＶＬが生成される。最後に、図１２Ｅに示されるように、位置配列Ｂの要素によって指定される位置に、項目値番号を格納すると、ローカル項目値番号配列ＶＮｏが得られる。すなわち、ＶＮｏ［Ｂ［ｉ］］＝Ｃ［ｉ］に従って、ローカル項目値番号配列ＶＮｏが生成される。以上のブロック内コンパイル処理により、演算ユニットのローカルメモリにローカル項目値番号配列ＶＮｏ及びローカル項目値配列ＬＶＬが生成される。

　次に、本発明の一実施形態によるブロック間コンパイル処理について説明する。ブロック間コンパイル処理は、複数台の演算ユニットが並列的かつ階層的に動作して、データ項目毎に、最終的に１個のローカルデータにマージされるまで、１対のローカルデータをマージする処理を繰り返し、最終的なブロック番号配列、最終的なグローバル項目値順序番号配列、及び、最終的なローカル項目値配列を生成するマージ処理と、マージ処理によって生成された最終的なグローバル項目値順序番号配列中のグローバル項目値順序番号を対応するブロック番号配列に格納されているブロック番号に基づいてブロック番号に対応する演算ユニットへ分配する分配処理とを含む。各演算ユニットは、分配されたグローバル項目値順序番号をそれぞれのローカルメモリ上に確保されたグローバル項目値順序番号配列に格納する。

　マージ処理では、各演算ユニットが、１対のブロックに関する情報、すなわち、１対のローカルデータをマージして、マージされたより高い層の１個のブロックに関する情報、すなわち、さらなるローカルデータを生成する。よって、マージ処理は、複数台の演算ユニットの並列動作によって実現される。また、各演算ユニットは、同じ層に属するマージされたブロックの対に関する情報をマージし、マージされたさらに高い層の１個のブロックに関する情報を生成する。このようにマージ処理を並列的かつ階層的に繰り返すことにより、最終的に最上層の１個のブロックに関する情報が生成される。最上層の１個のブロックとは、レコード全体を含むブロックである。

　たとえば、２^ｎ－１台の演算ユニットが存在し、各演算ユニットが２個のブロックに関する情報を入力し、それらをマージして、１個のブロックに関する情報を出力すると仮定すると、各演算ユニットが１回ずつマージ処理を実行することによって、ｎ段（層）のマージ処理が実現される。この場合、全演算ユニットによる全データ通信量のうち、演算ユニットがグローバルメモリとの間で行う通信が占める割合は、１／ｎである。演算ユニット間の通信量は、全データ通信量の（ｎ－１）／ｎである。なお、演算ユニット０に関連したブロック０と演算ユニット１に関連したブロック１は、演算ユニット０又は演算ユニット１以外の演算ユニットによってマージされてもよく、或いは、演算ユニット１又は演算ユニット１のいずれかの演算ユニットによってマージされてもよい。このように、元のローカルデータを保持している一方の演算ユニットが次のパイプライン段のマージ処理を担当することにより、演算ユニット間のデータ通信量が削減される。

　図１３はブロック間コンパイル処理のマージ処理の概要図である。ブロック内コンパイルによって、演算ユニットＰＥ－ｉ（ｉ＝０，１，２，・・・，７）は、それぞれに割り当てられたブロックに関する情報Ｂｌｏｃｋ－ｉ（ｉ＝０，１，２，・・・，７）を生成し、パイプライン段の演算ユニットへ送信している。ここで、ＰＥ－ｉは演算ユニットｉを表し、Ｂｌｏｃｋ－ｉはブロックｉを表している。

　最初のパイプライン段では、演算ユニット０が演算ユニット０からのブロック０と演算ユニット１からのブロック１とをマージする。演算ユニット２は演算ユニット２からのブロック２と演算ユニット３からのブロック３とをマージする。演算ユニット４は演算ユニット４からのブロック４と演算ユニット５からのブロック５とをマージする。演算ユニット６は演算ユニット６からのブロック６と演算ユニット７からのブロック７をマージする。

　次のパイプライン段では、演算ユニット１は、演算ユニット０からのブロック０～１と演算ユニット２からのブロック２～３とをマージする。同様に、演算ユニット５は、演算ユニット４からのブロック４～５と演算ユニット６からのブロック６～７とをマージする。ここで、ブロックｉ～ｊという表記は、ブロックｉからブロックｊまでをマージすることにより生成された１つのブロックを意味している。このように、演算ユニットは、トーナメント方式でパイプライン処理を実行する
　最後に、演算ユニット３が演算ユニット１からのブロック０～３と演算ユニット５からのブロック４～７をマージして、１つのブロック０～７を生成する。勿論、トーナメント表内での演算ユニットの配置（すなわち、ブロックと演算ユニットの対応関係）は、図１３に示されている配置に限定されることがない。

　演算ユニット３で生成されるブロック０～７は、値が得られると、順次、演算ユニット７へ送信される。演算ユニット７は、ブロック０～７を元のブロックに対応した演算ユニット０、演算ユニット１、・・・、演算ユニット７へ分配する。

　ブロック間コンパイル（グローバルコンパイルとも称される）では、取り扱われる配列（すなわち、ブロック番号配列、グローバル項目値順序番号配列、及び、ローカル項目値配列）が１台の演算ユニットのローカルメモリに収容できない程度のサイズに達することがある。そのため、パイプライン化された演算ユニットは、前のパイプライン段の演算ユニットからデータを受信すると、受信されたデータを直ちに処理し、処理されたデータを後のパイプライン段の演算ユニットへ送信しようとする。後のパイプライン段の演算ユニットは、この演算ユニットのローカルメモリにデータを格納可能であるならば、前のパイプライン段からのデータを受信し、データを格納可能でないならば、前のパイプライン段からの送信を待たせる。データ送信を完了した演算ユニットは、送信されたデータが格納されていたローカルメモリ内の記憶領域を開放することが可能である。データ送信が完了していない演算ユニットは、この演算ユニットのローカルメモリにデータを格納できる限り、前のパイプライン段からのデータを受信し処理するが、ローカルメモリにそれ以上データを格納できなくなったならば、前のパイプライン段の演算ユニットに対して、データの送信を待たせ、ローカルメモリにデータを格納する領域が再び確保されたならば、前のパイプライン段の演算プロセッサに対してデータの送信を再開させる。このように、本実施形態では、データの受信側がデータの送信元に対してデータ送信停止要求及びデータ送信再開要求を発行することによって演算ユニット間のデータ通信を制御しているが、演算ユニット間のデータ通信は、一般的に知られているどのようなフロー制御によっても実現され得ることに注意を要する。

　今度は、図１４Ａ及び１４Ｂを参照して、本発明の一実施形態によるブロック間コンパイル処理の初期化処理を説明する。図１４Ａは項目＝Ｓｃｈｏｏｌに関する項目情報を示し、図１４Ｂは項目＝Ａｇｅに関する項目情報を示している。最初に、演算ユニットは、この演算ユニットのローカルメモリ上に初期化されたブロック番号配列ＢｌｋＮｏを作成する。ブロック番号配列ＢｌｋＮｏは、既に作成されているローカル項目値配列ＬＶＬと同じサイズであり、初期値として、各演算ユニットに割り当てられた担当レコードを識別するためのブロック番号が設定される。本例では、たとえば、演算ユニット０のブロック番号配列には０が格納され、演算ユニット１のブロック番号配列には１が格納され、以下同様である。

　演算ユニットは、初期化されたグローバル項目値順序番号配列ＧＶＯｒｄをさらにローカルメモリ上に作成する。グローバル項目値順序番号配列ＧＶＯｒｄのサイズはローカル項目値配列ＬＶＬと同じサイズであり、初期値として、先頭から順番に０から始まる連続番号が設定される。

　これらの初期化処理は複数台の演算ユニットによって並列的に実行される。

　今度は、図１５Ａ、１５Ｂ及び１５Ｃを参照して、本発明の一実施形態によるブロック間コンパイル処理の１段目のマージ処理を説明する。一例として、演算ユニット０がブロック０とブロック１をマージする例を説明する。

　最初に、演算ユニット０（ＰＥ－０）は、図１５Ａに示されているように、ＰＥ－０からのローカル項目値配列ＬＶＬの先頭の格納値＝“Ｓｏｕｔｈ”とＰＥ－１からのローカル項目値配列ＬＶＬの先頭の格納値＝“Ｎｏｒｔｈ”とを比較し、ＰＥ－１からの格納値＝“Ｎｏｒｔｈ”がＰＥ－０からの格納値＝“Ｓｏｕｔｈ”より小さいこと、すなわち、所定の順序（たとえば、本例では、アルファベットの昇順）で高順位であることを検出し、小さい方の項目値＝“Ｎｏｒｔｈ”をさらなるローカル項目値配列ＬＶＬ’に格納する。同時に、小さい方の格納値＝“Ｎｏｒｔｈ”に対応するブロック番号＝１をさらなるブロック番号配列ＢｌｋＮｏ’に格納する。もし、ＰＥ－１からのローカルデータに関して、項目値＝“Ｎｏｒｔｈ”に対応するグローバル項目値順序番号配列の要素の値が連続的に存在するならば、連続的に存在する要素の値の個数分だけさらなるブロック番号配列の要素を繰り返し格納する。一方、さらなるグローバル項目値順序番号配列には、さらなるブロック番号配列中に要素が格納されている位置と同じ位置まで現在の順序番号（すなわち、本例では、順序番号＝０）を充填する。その後、小さい方の格納値＝“Ｎｏｒｔｈ”が格納されていた方のローカル項目値配列ＬＶＬへのポインタ（すなわち、比較されるべき要素を指定するポインタ）を進める。

　次に、ＰＥ－０は、図１５Ｂに示されているように、ＰＥ－０からのローカル項目値配列ＬＶＬの先頭の格納値＝“Ｓｏｕｔｈ”とＰＥ－１からのローカル項目値配列ＬＶＬの２番目の格納値＝“Ｓｏｕｔｈ”とを比較する。両方の格納値が同一値であるため、ＰＥ－０は、いずれか一方の項目値＝“Ｓｏｕｔｈ”をさらなるローカル項目値配列ＬＶＬ’に格納する。同時に、ＰＥ－０は、これらの項目値に対応するブロック番号のうち、小さい方のブロック番号（本例では、ＰＥ－０からのブロック番号＝０）をさらなるブロック番号配列ＢｌｋＮｏ’に格納する。もし、ＰＥ－０からのローカルデータに関して、項目値＝“Ｓｏｕｔｈ”に対応するグローバル項目値順序番号配列の要素の値が連続的に存在するならば、連続的に存在する要素の値の個数分だけさらなるブロック番号配列の要素を繰り返し格納する。その後、ＰＥ－０は、大きい方のブロック番号（本例では、ＰＥ－１からのブロック番号＝１）をさらなるブロック番号配列ＢｌｋＮｏ’に格納し、同様に、もし、ＰＥ－１からのローカルデータに関して、項目値＝“Ｓｏｕｔｈ”に対応するグローバル項目値順序番号配列の要素の値が連続的に存在するならば、連続的に存在する要素の値の個数分だけさらなるブロック番号配列の要素を繰り返し格納する。一方、さらなるグローバル項目値順序番号配列には、さらなるブロック番号配列中に要素が格納されている位置と同じ位置まで現在の順序番号（すなわち、本例では、順序番号＝１）を充填する。その後、両方のローカル項目値配列ＬＶＬへのポインタ（すなわち、比較されるべき要素を指定するポインタ）を進める。

　次に、ＰＥ－０は、図１５Ｃに示されているように、ＰＥ－０からのローカル項目値配列ＬＶＬの２番目の格納値＝“Ｗｅｓｔ”とＰＥ－１からのローカル項目値配列ＬＶＬの３番目の格納値＝“Ｗｅｓｔ”とを比較する。両方の格納値が同一値であるため、ＰＥ－０は、いずれか一方の項目値＝“Ｗｅｓｔ”をさらなるローカル項目値配列ＬＶＬ’に格納する。同時に、ＰＥ－０は、これらの項目値に対応するブロック番号のうち、小さい方のブロック番号（本例では、ＰＥ－０からのブロック番号＝０）をさらなるブロック番号配列ＢｌｋＮｏ’に格納する。もし、ＰＥ－０からのローカルデータに関して、項目値＝“Ｗｅｓｔ”に対応するグローバル項目値順序番号配列の要素の値が連続的に存在するならば、連続的に存在する要素の値の個数分だけさらなるブロック番号配列の要素を繰り返し格納する。その後、ＰＥ－０は、大きい方のブロック番号（本例では、ＰＥ－１からのブロック番号＝１）をさらなるブロック番号配列ＢｌｋＮｏ’に格納し、同様に、もし、ＰＥ－１からのローカルデータに関して、項目値＝“Ｗｅｓｔ”に対応するグローバル項目値順序番号配列の要素の値が連続的に存在するならば、連続的に存在する要素の値の個数分だけさらなるブロック番号配列の要素を繰り返し格納する。一方、さらなるグローバル項目値順序番号配列には、さらなるブロック番号配列中に要素が格納されている位置と同じ位置まで現在の順序番号（すなわち、本例では、順序番号＝２）を充填する。その後、両方のローカル項目値配列ＬＶＬへのポインタ（すなわち、比較されるべき要素を指定するポインタ）を進める。本例では、ポインタが両方のローカル項目値配列ＬＶＬの末尾に達しているので、ＰＥ－０によるブロック間コンパイル処理の１段目のマージ処理が終了する。

　このマージ処理の結果として、２組のローカルデータ、すなわち、２組のブロック番号配列、グローバル項目値順序番号配列及びローカル項目値配列が、１組のさらなるローカルデータ、すなわち、１組のさらなるブロック番号配列、さらなるグローバル項目値順序番号配列及びさらなるローカル項目値配列に変換される。

　ブロック間コンパイル処理の１段目のマージ処理は、ローカルメモリへのシーケンシャルアクセスのみによって実行されるので、ブロック番号配列、グローバル項目値順序番号配列及びローカル項目値配列のサイズとは無関係に、小さなサイズの作業メモリだけを使用して実現され得ることに注意を要する。

　また、さらなるブロック番号配列ＢｌｋＮｏ’に格納されるブロック番号は、さらなるグローバル項目値順序番号配列ＧＶＯｒｄ’に格納されている値が同一である限り、必ず所定の順序（本例では、昇順）になることに注意を要する。

　今度は、図１６を参照して、演算ユニットＰＥ－１が、ＰＥ－０から出力されたブロック０～１と、ＰＥ－２から出力されたブロック２～３を１つのブロックにマージする２段目のマージ処理について説明する。図１６Ａ乃至１６Ｄは、本発明の一実施形態によるブロック間コンパイルにおける２段目のマージ処理の説明図である。２段目のマージ処理は、入力される情報が他の演算ユニットによって既にマージされた結果の情報である点を除いて、１段目のマージ処理と同様である。図１６Ａ、１６Ｂ、１６Ｃ及び１６Ｄには、この処理の過程と、得られたさらなるブロック番号配列ＢｌｋＮｏ’、さらなるグローバル項目値順序番号配列ＧＶＯｒｄ’、及び、さらなるローカル項目値配列ＬＶＬ’とが示されている。

　今度は、図１７を参照して、次のパイプライン段のマージ処理を説明する。ブロック間コンパイル処理の１段目のマージ処理と２段目のマージ処理を終えると、ブロック０からブロック３までがマージされたブロック０～３と、ブロック４からブロック７までがマージされたブロック４～７が得られる。演算ユニットＰＥ－３は、ＰＥ－４によって出力されるブロック０～３と、ＰＥ－５によって出力されるブロック４～７とを受信し、２つのブロックのマージ処理を同様に実行する。これにより、最終的な１個のブロックであるＢｌｏｃｋ０～７が得られる。図１７は、本発明の一実施形態によるブロック間コンパイル処理における３段目のマージ処理の結果を説明する図である。図１７には、データ項目「Ｓｃｈｏｏｌ」に関するブロック間コンパイルによるマージ処理の結果が表されている。ここで、最終的なさらなるローカル項目値配列ＬＶＬ’は、仮想的なグローバル項目値配列に一致することに注意すべきである。

　今度は、図１８Ａ及び１８Ｂを参照して、ブロック間コンパイル処理における分配処理を説明する。図１８Ａは、本発明の一実施形態によるブロック間コンパイル処理における分配処理の説明図である。本発明の一実施形態によるブロック間コンパイル処理は、マージ処理の後に、分配処理を実行する。分配処理では、少なくとも１台の演算ユニットが、データ項目毎に、最終的なグローバル項目値順序番号配列ＧＶＯｒｄ’の要素を最終的なブロック番号配列ＢｌｋＮｏ’の対応する要素によって指定されたブロック番号毎に、このブロック番号に対応する演算プロセッサに分配する。そして、それぞれの演算プロセッサが分配されたグローバル項目値順序番号を所定の順番（たとえば、昇順）で先に初期設定されていたグローバル項目値順序番号配列ＧＶＯｒｄに格納する。

　このため、本発明の一実施形態によるブロック間コンパイル処理における分配では、図１８Ｂに示されたデータが取得されているならば、演算ユニットｉのグローバル項目値順序番号配列をＧＶＯｒｄ［ｉ］［ｊ］と表現すると、グローバル項目値順序番号は次の手順に従って各演算ユニットのローカルメモリに確保されたグローバル項目値順序番号配列ＧＶＯｒｄに分配される。
ｆｏｒ　（ｉ＝０；ｉ＜８；ｉ＋＋）　｛
　Ｏｆｆｓｅｔｓ［ｉ］＝０；
｝
ｆｏｒ　（ｉ＝０；ｉ＜１９；ｉ＋＋）　｛
　ＧＶＯｒｄ［ＢｌｋＮｏ’［ｉ］］［Ｏｆｆｓｅｔｓ［ＢｌｋＮｏ’［ｉ］］］＝ＧＶＯｒｄ’［ｉ］；
　Ｏｆｆｓｅｔｓ［ＢｌｋＮｏ’［ｉ］］＋＋；
｝
　上記の分配処理は１台の演算ユニット又はプロセッサコアで操作を実施する場合の操作に対応している。しかし、本発明の一実施形態によれば、好ましくは、複数台の演算ユニット又はプロセッサコアを用いて、グローバル項目値順序番号配列ＧＶＯｒｄ’を分配することも可能である。また、グローバル項目値順序番号配列ＧＶＯｒｄ［ｉ］［ｊ］は、一旦、分配処理を実行している演算ユニットのローカルメモリ上に作成され、このグローバル項目値順序番号配列ＧＶＯｒｄ［ｉ］［ｊ］の要素が少しずつ充填されるのに応じて、少しずつ各演算ユニットへ送信してもよく、或いは、ある程度の量をまとめて一括して各演算ユニットへ送信してもよい。

　図１８Ｂは、本発明の一実施形態によるブロック間コンパイル処理における分配処理の結果を示す図である。たとえば、演算ユニットＰＥ－０のローカルメモリ上のグローバル項目値順序番号配列ＧＶＯｒｄ［０］には、ＧＶＯｒｄ［０］［０］＝２、ＧＶＯｒｄ［０］［１］＝３という順序番号が格納されている。

　図１８Ａ及び１８Ｂの例では、ブロック数が増加すると、ローカルメモリ上の作業領域も増大する。そのため、本発明の代替的な実施形態では、特に、ブロック数が多い場合に、処理を効率化するために、複数のブロックをグループ化した後に、グループ毎に分配処理を実施する。たとえば、ブロック番号を４で除算することにより、上位ブロック番号と、下位ブロック番号に分離し（グループ化し）、上位ブロック番号と下位ブロック番号に関して別々に分配処理を適用する。具体的には、ブロック間コンパイル処理におけるマージ処理によって得られたブロック番号配列ＢｌｋＮｏ’とグローバル項目値順序番号配列ＧＶＯｒｄ’の組から、上位ブロック番号用のブロック番号配列ＢｌｋＮｏ’とグローバル項目値順序番号配列ＧＶＯｒｄ’の組と、下位ブロック番号用のブロック番号配列ＢｌｋＮｏ’とグローバル項目値順序番号配列ＧＶＯｒｄ’の組が生成される。この処理もまた、複数台の演算ユニットが並列的に動作して、実行可能である。

　図１９Ａ乃至１９Ｃは、本発明の一実施形態によるコンパイル処理の結果を説明する図である。図１９Ａ、１９Ｂ及び１９Ｃは、それぞれ、図５Ｂ、５Ｃ及び５Ｄと同一である。

　［表形式データのソート処理の概要］
　次に、本発明の一実施形態による分散メモリ型マルチプロセッサによる表形式データのソート処理について説明する。図２０Ａ及び２０Ｂは本発明の一実施形態による表形式データのソート処理の説明図である。図２０Ａにはソート処理前の表形式データが示され、図２０Ｂにはソート処理後の表形式データが示され、ソート処理前の表形式データは図５Ａに示された表形式データと同一である。同図の例では、表形式データは、データ項目＝“Ｓｃｈｏｏｌ”をキーとして、このデータ項目の項目値の昇順（より具体的にはアルファベット順）にレコードが並べ替えられている。ソート前のレコード順序番号＝０に相当するレコード（Ｗｅｓｔ，１２）は、ソート処理によってレコード順序番号が２４に変化している。また、ソート前のレコード順序番号＝２に相当するレコード（Ｗｅｓｔ，１１）は、ソート処理後にレコード順序番号が２５に変化している。このようにキー値が同値（すなわち、Ｗｅｓｔ）である２つのレコードの順序がソート処理の前後で変化しないようなソート処理は「安定性のある」ソート処理と呼ばれる。ここで、レコード（Ａ，Ｂ）という表記は、データ項目＝“Ｓｃｈｏｏｌ”の項目値がＡであり、データ項目＝“Ａｇｅ”の項目値がＢであるレコードを表している。

　図２０Ａに示されたソート処理前の表形式データは、分散メモリ型マルチプロセッサ向けデータ構造を用いると図５Ｂ乃至５Ｄに示されたデータ構造によって表現される。これに対して、図２１Ａ乃至２１Ｄは、本発明の一実施形態によるソート処理を、図５Ａ乃至５Ｄに示された表形式データに適用することにより得られる表形式データの説明図である。図２１Ａ乃至２１Ｄを参照して、ソート処理の結果を説明する。たとえば、図２１Ａの表形式データのレコード順序番号＝０に相当するレコード（Ｅａｓｔ，６）は、図２１Ｂのレコード順序番号配列ＧＯｒｄを参照すると、ブロック２のＧＯｒｄ［０］＝０であることから、ブロック番号＝２のブロックに属していることがわかる。このレコード順序番号＝０が格納されているレコード順序番号配列ＧＯｒｄ中の要素ＧＯｒｄ［０］の格納位置、すなわち、０は、このブロックを受け持つ演算ユニットの担当レコード中での対象レコードの順位（ランク）を表している。レコード順序番号配列は、本実施形態では、昇順の配列であるため、この格納位置は、周知の２分割法などによって効率的に見つけられる。

　次に、ブロック番号＝２のブロック中でランク＝０が付与されたレコードに含まれる項目情報を取得するために、項目値アクセス情報配列ＬＯｒｄが参照される。より具体的には、ＬＯｒｄ［０］＝０は、ブロック２のブロック中のランク＝０が付与されたレコードに含まれる項目情報にアクセスするための項目値指定ポインタを表している。

　データ項目＝“Ｓｃｈｏｏｌ”に関する項目情報は図２１Ｃに示されている。ブロック２のブロック中のランク＝０が付与されたレコードに含まれる項目値は、
　ＬＶＬ［ＶＮｏ［ＬＯｒｄ［０］］＝“Ｅａｓｔ”
によって得られる。この項目値は次の手順にしたがって取得される。最初に、ブロック２に関するローカル項目値番号配列ＶＮｏ中で、項目値アクセス情報＝ＬＯｒｄ［０］＝０によって指定される要素
　ＶＮｏ［ＬＯｒｄ［０］］＝ＶＮｏ［０］＝０
を取得する。次に、項目値指定ポインタ配列ＬＶＬ中で、ＶＮｏ［０］＝０によって指定される要素
　ＬＶＬ［ＶＮｏ［０］］＝ＬＶＬ［０］＝“Ｅａｓｔ”
を取得する。これにより、図２１Ａの表形式データのレコード順序番号＝０に相当するレコードに含まれるデータ項目＝“Ｓｃｈｏｏｌ”に関する項目値は“Ｅａｓｔ”であることが示された。同様に、データ項目＝“Ａｇｅ”に関する項目値が６であることも明らかである。

　このように、本発明の一実施形態によるソート処理では、ソート処理の前後で変化するのは順序情報（すなわち、レコード順序番号配列及び項目値アクセス情報配列）だけであり、項目情報はソート処理の前後で変化しない。

　本実施形態の説明では、項目情報は、ローカル項目値番号配列ＶＮｏ、ローカル項目値配列ＬＶＬ、及び、グローバル項目値順序番号配列ＧＶＯｒｄによって構成されている。

　［表形式データのソート処理］
　表形式データのソート処理は、以下の３ステップにより構成される。図２２は、本発明の一実施形態による表形式データのソート処理の概略的なフローチャートである。

　ステップ２２０１：ブロック内ソート
　各演算ユニットが並列的に動作して、それぞれのブロック内で、ローカル項目値番号配列ＶＮｏをキーとして、項目値アクセス情報配列ＬＯｒｄに分布数え上げソートを適用し、ソートされた項目値アクセス情報配列ＬＯｒｄに適合するように、次のステップのためのグローバル項目値順序番号配列ＧＶＯｒｄ’及びレコード順序番号配列ＧＯｒｄ’を生成する。当然ながら、１台の演算ユニットに複数のプロセッサが収容されているならば、ブロック単位の処理はプロセッサ毎に実行される。

　ステップ２２０２：ブロック間ソート１（マージ）
　各演算ユニットが並列的かつ階層的に動作して、前のパイプライン段からのグローバル項目値順序番号配列ＧＶＯｒｄ’及びレコード順序番号配列ＧＯｒｄ’にブロック番号配列ＢｌｋＮｏ’を追加し、グローバル項目値順序番号配列ＧＶＯｒｄ’及びレコード順序番号配列ＧＯｒｄ’をキーとして、それぞれのブロックからのグローバル項目値順序番号配列ＧＶＯｒｄ’、レコード順序番号配列ＧＯｒｄ’及びブロック番号配列ＢｌｋＮｏ’をトーナメント方式で所定の順序にマージする。このステップは順次処理である。

　ステップ２２０３：ブロック間ソート２（分配）
　少なくとも１台の演算ユニットがブロック番号配列ＢｌｋＮｏ’の先頭の要素から順に、要素の値によって指定されるブロック、すなわち、このブロックに関連付けられた演算ユニットに、要素が格納されている位置の値を送信し、各演算ユニットのローカルメモリ上にレコード順序番号配列ＧＯｒｄを生成する。

　このように、表形式データのソート処理は、ブロック内ソートと、ブロック間ソート１（マージ）と、ブロック間ソート２（分配）の３ステップによって実現される。ここで、ブロック間ソート１（マージ）は、１対のブロックからのデータを所定の順序で並べ替えるという意味でソート処理であり、１対のブロックからのデータを１組のデータに統合するという意味でマージ処理でもある。本文書中において、「所定の順序でマージ」するとは、ブロック間ソート１（マージ）における処理を指している。

　以下では、図５Ａ乃至５Ｄ、図２０Ａ及び２０Ｂ、及び、図２１Ａ乃至２１Ｄに示された例を参照して、本発明の一実施形態による表形式データのソート処理の各ステップの処理をより詳細に説明する。

　図２３Ａ乃至２３Ｃは本発明の一実施形態による表形式データのソート処理におけるブロック内ソート処理の説明図である。同図には、一例として、ブロック番号＝１のブロック（すなわち、ブロック１）に関する処理が記載されているが、他のブロックに関する処理も同様に行われることは当業者に明白であろう。各ブロックに関する処理は、そのブロックが割り当てられた各演算ユニットによって実行される。また、以下の説明では、配列の操作は、Ｃ言語に類似した疑似命令によって表現されることがある。

　図２３Ａは分布数え上げソート処理におけるカウントアップ処理の説明図である。図２３Ａには、ブロック１に関するレコード順序番号配列ＧＯｒｄ、項目値アクセス情報配列ＬＯｒｄ、ローカル項目値番号配列ＶＮｏ、及び、グローバル項目値順序番号配列ＧＶＯｒｄと、分布数え上げソートのキーとして利用するローカル項目値番号の出現回数をカウントするカウント配列Ｃｏｕｎｔの遷移が示されている。カウントアップ処理は、
ｆｏｒ　（ｉ＝０；ｉ＜ブロック内レコード数；ｉ＋＋）　｛
　　Ｃｏｕｎｔ［ＶＮｏ［ＬＯｒｄ［ｉ］］］＋＋；
｝
として記述できる。図２３Ａの例では、１段目がｉ＝０、２段目がｉ＝１、３段目がｉ＝２、４段目がｉ＝３に対応している。

　図２３Ｂは分布数え上げソート処理における累計数化処理の説明図である。カウントアップ処理の結果として得られたカウント配列Ｃｏｕｎｔは、
Ｃｏｕｎｔ［０］＝１
Ｃｏｕｎｔ［１］＝２
Ｃｏｕｎｔ［２］＝１
である。この出現回数を累積度数分布に変換すると（すなわち、累計数化すると）、累積度数分布配列Ａｇｇｒが得られる。なお、この累計数化処理によって生成される累積度数分布配列Ａｇｇｒの先頭の要素は０であり、実際の累積度数はＡｇｇｒ［１］以降に格納されている。累計数化処理は、たとえば、
Ａｇｇｒ［０］＝０；
ｆｏｒ　（ｉ＝１；ｉ＜キー値の個数；ｉ＋＋）　｛
　　Ａｇｇｒ［ｉ］＝Ａｇｇｒ［ｉ－１］＋Ｃｏｕｎｔ［ｉ－１］；
｝
として記述できる。

　最後に、このようにして生成された累積度数分布配列Ａｇｇｒの要素をポインタとして利用して項目値アクセス情報配列ＬＯｒｄの要素をコピーすることにより、ソートされた項目値アクセス情報配列ＬＯｒｄ’が得られる。図２３Ｃは分布数え上げソート処理における転送処理の説明図である。転送処理では、配列ＬＯｒｄの要素を配列ＬＯｒｄ’へコピーするだけでなく、新たに生成された配列ＬＯｒｄ’に対応するグローバル項目値順序番号配列ＧＶＯｒｄ’及びレコード順序番号配列ＧＯｒｄ’も生成される。たとえば、図２３Ｃの最上段には、ＬＯｒｄ［０］をコピーする処理が示されている。ＬＯｒｄ［０］＝０は、ＬＯｒｄ’の要素ＬＯｒｄ’［１］へコピーされている。これは、ＬＯｒｄ［０］であるレコードに含まれる項目値のローカル項目値番号ＶＮｏ［０］が１であることから、累積度数分布配列Ａｇｇｒ中の要素Ａｇｇｒ［１］＝１をポインタとして利用して、項目値アクセス情報配列ＬＯｒｄ’の要素ＬＯｒｄ’［１］にＬＯｒｄ［０］＝０をコピーすることによって実現されている。この転送処理は、一般的に、たとえば、
ｆｏｒ　（ｉ＝０；ｉ＜ブロック内のレコード数；ｉ＋＋）　｛
　　ＬＯｒｄ’［Ａｇｇｒ［ＶＮｏ［ＬＯｒｄ［ｉ］］］］＝ＬＯｒｄ［ｉ］；
　　ＧＶＯｒｄ’［Ａｇｇｒ［ＶＮｏ［ＬＯｒｄ［ｉ］］］］＝ＧＶＯｒｄ［ＶＮｏ［ＬＯｒｄ［ｉ］］］；
　　ＧＯｒｄ’［Ａｇｇｒ［ＶＮｏ［ＬＯｒｄ［ｉ］］］］＝ＧＯｒｄ［ｉ］；
　　Ａｇｇｒ［ＶＮｏ［ＬＯｒｄ［ｉ］］］＋＋；
｝
として記述できる。

　このようにして得られた項目値アクセス情報配列ＬＯｒｄ’は、ソート後のブロック内での最終的な項目値アクセス情報配列ＬＯｒｄと一致する。また、新たに生成されたグローバル項目値順序番号配列ＧＶＯｒｄ’とレコード順序番号配列ＧＯｒｄ’は、ブロック内で項目値をキーとしてソートされたレコードに対応している。

　本発明の一実施形態によれば、各演算ユニットによってブロック内でソートされた表形式データのレコードは、次に、ブロック間でマージされる。ブロック間のマージでは、それぞれのブロック内でソートされているデータが併合され、全体としてソートされた併合データが生成される。より具体的には、グローバル項目値順序番号配列ＧＶＯｒｄ’の要素とレコード順序番号配列ＧＯｒｄ’の要素の組がソートされる。レコード順序番号配列ＧＯｒｄ’の要素はレコード毎に一意に決まる値をもつので、グローバル項目値順序番号配列ＧＶＯｒｄ’の要素とレコード順序番号配列ＧＯｒｄ’の要素の組は一意である。あるデータ項目に関するグローバル項目値順序番号配列ＧＶＯｒｄ’の要素は、そのデータ項目に関する項目値が所定の順序で整列させられた仮想的なグローバル項目値配列の要素の位置を指示するので、グローバル項目値順序番号配列ＧＶＯｒｄ’の要素の値の順番にソートすることは、項目値の順番にソートすることと等価である。なお、ブロック内ソート処理の結果として得られたグローバル項目値順序番号配列ＧＶＯｒｄ’及びレコード順序番号配列ＧＯｒｄ’には、各ブロック内のレコードが属するブロック番号を表すブロック番号配列ＢｌｋＮｏ’が後の処理のため追加される。

　図２４は、このようにして得られた、本発明の一実施形態による表形式データのソート処理におけるブロック内ソート処理の結果の説明図である。この時点で、各ブロック内の項目値アクセス情報配列ＬＯｒｄは最終的な結果と一致しているので、ＬＯｒｄのようにプライム記号（’）無しで示されている。一方、グローバル項目値順序番号配列ＧＶＯｒｄ’及びレコード順序番号配列ＧＯｒｄ’は最終的な結果ではなく、処理途中の作業用配列を表しているので、プライム記号（’）付きで示されている。さらに、追加的に生成されたブロック番号配列ＢｌｋＮｏ’も示されている。

　本発明の一実施形態による表形式データのソート処理におけるブロック間ソート処理１（マージ処理）は、図１３に示された階層構造と同じ階層構造によって実現することが可能である。ブロック０から７に関連付けられた演算ユニット０から演算ユニット７によって並列的にローカルソート処理が実行されると、１段目のマージ処理として、演算ユニット０によるブロック０とブロック１のマージ処理、演算ユニット２によるブロック２とブロック３のマージ処理、演算ユニット４によるブロック４とブロック５のマージ処理、及び、演算ユニット６によるブロック６とブロック７のマージ処理が実行される。２段目のマージ処理は、演算ユニット１によるブロック０－１とブロック２－３のマージ処理、及び、演算ユニット５によるブロック４－５とブロック６－７のマージ処理により実現される。最後に、３段目のマージ処理として、演算ブロック３が、ブロック０－３とブロック４－７のマージ処理を実行する。各パイプライン段でマージ処理を担当する演算ユニットは上記の組み合わせに限定されないことに注意を要する。なお、分配処理は、たとえば、演算ユニット７によって実行される。

　ブロック間ソート処理１（すなわち、マージ処理）では、各演算ユニットが、１対のブロックに関する情報をマージして、マージされたより高い層の１個のブロックに関する情報を生成する。よって、マージ処理は、複数台の演算ユニットの並列動作によって実現される。また、各演算ユニットは、同じ層に属するマージされたブロックの対に関する情報をマージし、マージされたさらに高い層の１個のブロックに関する情報を生成する。このようにマージ処理を並列的かつ階層的に繰り返すことにより、最終的に最上層の１個のブロックに関する情報が生成される。最上層の１個のブロックとは、レコード全体を含むブロックである。

　続いて、本発明の一実施形態による表形式データのソート処理におけるブロック間ソート処理１（ブロック間マージ処理）をより詳細に説明する。図２５Ａ乃至２５Ｃは、本発明の一実施形態による表形式データのソート処理における１段目のブロック間マージ処理の説明図である。本例では、ＰＥ－０がブロックＢｌｏｃｋ－０（以下、ブロック０）とブロックＢｌｏｃｋ－１（ブロック１）との間で所定の順序のマージ処理を実行する。ブロック間マージ処理は、２つの昇順リストから１つの昇順リストを生成するという点で昇順リストのマージ処理である。

　図２５Ａには、ブロック０内の１番目のレコードに関する情報（Ｂ０（ＧＶＯｒｄ’，ＧＯｒｄ’）のように表す）とブロック１内の１番目のレコードに関する情報（Ｂ１（ＧＶＯｒｄ’，ＧＯｒｄ’）のように表す）とを比較する処理が示されている。このとき、ブロック０側の読み出しポインタとブロック１側の読み出しポインタは共にデータの先頭に位置している。ＧＶＯｒｄ’を上位の桁、ＧＯｒｄ’を下位の桁とみなして、ブロック０側及びブロック１側からの（ＧＶＯｒｄ’，ＧＯｒｄ’）を所定の順番（たとえば、昇順）に並べる。本例では、
Ｂ０（ＧＶＯｒｄ’，ＧＯｒｄ’）＝（２，１）＞Ｂ１（ＧＶＯｒｄ’，ＧＯｒｄ’）＝（１，５）
であるので、Ｂ１（ＧＶＯｒｄ’，ＧＯｒｄ’）が先頭（最も小さい）要素であることが判定される。よって、ブロック番号を含めた要素の組Ｂ１（１，５，１）がマージ処理の結果として取り出される。このマージ処理の結果は、
ＧＶＯｒｄ’［０］＝１
ＧＯｒｄ’［０］＝５
ＢｌｋＮｏ’［０］＝１
のように記述できる。これにより、ブロック１側のデータが取り出されたので、ブロック１側の読み出しポインタが１つ先へ進められる。

　図２５Ｂでは、読み出しポインタが先頭に位置しているブロック０内の１番目のレコードと、読み出しポインタが１つ先へ進められたブロック１内の２番目のレコードとを比較する処理が示されている。同様に、Ｂ０（２，１）とＢ１（２，４）とを比較すると、Ｂ０（２，１）の方が小さいと判定されるので、ブロック番号を含めた要素の組Ｂ０（２，１，０）がマージ処理の結果、すなわち、
ＧＶＯｒｄ’［１］＝２
ＧＯｒｄ’［１］＝１
ＢｌｋＮｏ’［１］＝０
として取り出される。これにより、ブロック０側のデータが取り出されたので、ブロック０側の読み出しポインタが１つ先へ進められる。

　このように、ポインタを進めながら、ブロック０側のデータとブロック１側のデータを順次比較することにより、最終的に、ブロック０側のデータとブロック１側のデータがマージされた昇順のリストが得られる。図２５Ｃには、最終的に取り出されたグローバル項目値順序番号配列ＧＶＯｒｄ’とレコード順序番号配列ＧＯｒｄ’とブロック番号配列ＢｌｋＮｏ’とが示されている。

　なお、取り出されたグローバル項目値順序番号配列ＧＶＯｒｄ’とレコード順序番号配列ＧＯｒｄ’とブロック番号配列ＢｌｋＮｏ’は、２段目のマージ処理のため、本例では、たとえば、ＰＥ－１へ送出されるが、最終的な結果を一括して送出するのではなく、ブロック０側とブロック１側の比較処理を進めながら、取り出されたデータを必要に応じて、ＰＥ－０からＰＥ－１へ送出してもよい。

　以上の説明からわかるように、本発明の一実施形態によるブロック間ソート処理１（マージ処理）の１段目の処理では、データアクセスがシーケンシャルアクセスだけに限定され、かつ、各演算ユニットが並列にブロック間ソート処理１を実行可能である。よって、マルチプロセッサ型処理装置の性能が十分に活かされている。

　今度は、演算ユニットＰＥ－１が、ＰＥ－０から出力されたブロック０～１と、ＰＥ－２から出力されたブロック２～３に所定の順序のマージ処理を適用し、１つのブロック０～３を出力する２段目のブロック間ソート処理１について説明する。図２６Ａ及び２６Ｂは、本発明の一実施形態による表形式データのソート処理における２段目のマージ処理の説明図である。２段目のマージ処理は、入力される情報が他の演算ユニットのローカルメモリから転送される点を除いて、１段目のマージ処理と同様である。この処理を簡単に説明すると、図２６Ａに示されているように、最初、２つのブロックからのグローバル項目値順序番号配列ＧＶＯｒｄ’、レコード順序番号配列ＧＯｒｄ’、及び、ブロック番号配列ＢｌｋＮｏ’の読み出し用ポインタが先頭に設定される。両方の（ＧＶＯｒｄ’，ＧＯｒｄ’）の組の値を比較すると、
Ｂ０～１（ＧＶＯｒｄ’，ＧＯｒｄ’）＝（１，５）＞Ｂ２～３（ＧＶＯｒｄ’，ＧＯｒｄ’）＝（０，８）
であることから、Ｂ２～３側の要素の方が小さいということがわかる。よって、Ｂ２～３側の先頭の要素の組であるＢ２～３（０，８，２）を取り出す。そして、要素の組が取り出された方のＢ２～３側の読み出しポインタが１つ先へ進められる。ここで、Ｂａ～ｂという表記は、ブロックａからブロックｂまでの間の所定の順序のマージ処理の結果として得られたデータを表している。

　このような要素の組の大小比較と、小さい方の要素の組の読み出しを繰り返すことにより、図２６Ｂに示されているように、最後にＢ２～３側の要素の組であるＢ２～３（３，１３，３）が取り出され、２段目のマージ処理が終了する。

　なお、取り出されたグローバル項目値順序番号配列ＧＶＯｒｄ’とレコード順序番号配列ＧＯｒｄ’とブロック番号配列ＢｌｋＮｏ’は、３段目のマージ処理のため、本例では、ＰＥ－３へ送出されるが、最終的な結果を一括して送出するのではなく、ブロック０側とブロック１側の比較処理を進めながら、取り出されたデータを必要に応じて、ＰＥ－１からＰＥ－３へ送出してもよい。また、以上の説明からわかるように、本発明の一実施形態によるブロック間ソート処理１（マージ処理）の２段目の処理では、データアクセスがシーケンシャルアクセスだけに限定され、かつ、各演算ユニットが並列にブロック間ソート処理１を実行可能である。よって、マルチプロセッサ型処理装置の性能が十分に活かされている。

　２段目のマージ処理は、本例では、ＰＥ－１とＰＥ－５によって並列に実行されている。ＰＥ－１は、ブロック０からブロック３までのブロック間マージ処理の結果をブロック０～３としてＰＥ－３へ出力し、ＰＥ－５は、ブロック４からブロック７までのブロック間マージ処理の結果をブロック４～７としてＰＥ－３へ出力する。本例では、ブロックの総数は、ブロック０からブロック７までの８ブロックであるため、ＰＥ－３による３段目のマージ処理によって、全てのブロックからのデータのマージが終了し、すなわち、全てのブロックを考慮したソート処理が終了する。当業者によって理解されるように、ブロック数が９個以上ある場合には、たとえば、マージ処理の段数を増加させることにより、最終的に全てのブロックからのデータがマージされたソート処理結果を得ることが可能である。

　図２７は、本発明の一実施形態による表形式データのソート処理における３段目のマージ処理の説明図である。３段目のマージ処理もまた、１段目のマージ処理及び２段目のマージ処理と同様に、Ｂ０～３側のデータＢ０～３（ＧＶＯｒｄ’，ＧＯｒｄ’）とＢ４～７側のデータＢ０～４（ＧＶＯｒｄ’，ＧＯｒｄ’）を先頭から順番に比較し、小さい方の要素の組を取り出し、要素が取り出された側のデータの読み出し用ポインタを１つ先へ進める、という操作を繰り返す。これにより、図２７の右側に示されているような配列の組、すなわち、グローバル項目値順序番号配列ＧＶＯｒｄ’、レコード順序番号配列ＧＯｒｄ’、及び、ブロック番号配列ＢｌｋＮｏ’の組が得られる。この配列の組は、全レコードのソート結果を表現している。たとえば、グローバル項目値順序番号配列ＧＶＯｒｄ’を参照すると、先頭から、同一値を含めて値が昇順に並べられているので、仮想的なグローバル項目値配列中の項目値の整列順にレコードがソートされていることがわかる。また、グローバル項目値順序番号配列ＧＶＯｒｄ’の要素の値が同一であるレコードは、レコード順序番号配列ＧＯｒｄ’を参照することにより、ソート前のレコード順序番号の昇順に整列されていることもわかる。このように、レコード順序番号に関して安定性のあるソート結果が得られた理由は、ブロック間ソートの際に、項目値指定ポインタとレコード順序番号の組に関する大小関係に基づいてレコードの並べ替えが行われたからである。

　本発明の一実施形態による表形式データのソート処理におけるブロック間ソート処理１（マージ処理）によって得られた３つの配列から次のことがわかる。たとえば、配列の組の１行目のデータ＝（０，８，２）を参照すると、ソート後にレコード順序番号０が付与されるレコードは、
（ｉ）ソートのキーとなるデータ項目に関する項目値のグローバル項目値順序番号の値が０であり、
（ｉｉ）ソート前に付与されていたレコード順序番号が８であり、
（ｉｉｉ）ブロック２に属している。

　発明の理解を助けるため、このブロック間ソート処理1（マージ処理）の結果が分散メモリ型マルチプロセッサ向けのデータ構造で表現される。

　本発明の一実施形態による表形式データのソート処理では、最後に、各ブロックに属するレコードのレコード順序番号を決定する。このレコード順序番号を決定する処理は、ブロック間ソート処理２（分配処理）と呼ばれる。図２８に示す分配処理では、少なくとも１台の演算ユニット又はプロセッサコア（たとえば、本例では、演算ユニットＰＥ－７）が、ブロック番号配列ＢｌｋＮｏ’の添字ｉに相当するレコード順序番号をブロック番号ＢｌｋＮｏ［ｉ］で表されるブロック毎に分配し、分配されたレコード順序番号をブロック内で所定の順番（たとえば、昇順）に並べる。この処理は、たとえば、ブロックｊのレコード順序番号配列のｋ番目の要素をＧＯｒｄ［ｊ］［ｋ］とし、レコード順序番号配列ＧＯｒｄ［ｊ］にレコード順序番号を設定するための書き込み用ポインタｋをＯｆｆｓｅｔｓ［ｊ］とすると、次のように記述できる。
オフセット配列Ｏｆｆｓｅｔｓを初期化；
ｆｏｒ　（ｉ＝０；ｉ＜レコード総数；ｉ＋＋）　｛
　　ＧＯｒｄ［ＢｌｋＮｏ［ｉ］］［Ｏｆｆｓｅｔｓ［ＢｌｋＮｏ［ｉ］］＝ｉ；
　　Ｏｆｆｓｅｔｓ［ＢｌｋＮｏ［ｉ］］＋＋；
｝
　或いは、複数台の演算ユニット又はプロセッサコアがブロック番号配列ＢｌｋＮｏの一部を分担して分配処理を行ってもよい。そのため、あるブロックに関するレコード順序番号配列ＧＯｒｄ［ｊ］は複数台の演算ユニットによって分担して処理される。そして、複数の演算ユニットによって分担して作成されたレコード順序番号配列がブロック毎に１つのレコード順序番号配列に統合される。ブロック番号配列ＢｌｋＮｏ’の複数台の演算ユニットへの割り当てが連続的に行われるならば、すなわち、各演算ユニットが担当するブロック番号配列ＢｌｋＮｏ’の一部が連続しているならば、この統合処理は非常に簡単化される。なぜならば、同一のブロックに関して、別々の演算ユニットによって作成されたレコード順序番号配列の間で要素の順番を入れ替える必要がないからである。つまり、レコード順序番号配列の統合処理は、別々に作成されたレコード順序番号配列を単に連結することにより達成される。

　今度は、図２９Ａ乃至２９Ｅを参照して、本発明の一実施形態による表形式データのソート処理の流れ、特に、ブロック間ソート処理の流れをもう一度説明する。図２９Ａは、本発明の一実施形態によるブロック間ソート処理の説明図である。図２９Ａに示されているように、ブロック内ソート処理によって、各演算ユニットのローカルメモリには、担当レコード（すなわち、それぞれのブロック）に関する項目値アクセス情報配列ＬＯｒｄ、グローバル項目値順序番号配列ＧＶＯｒｄ’、レコード順序番号配列ＧＯｒｄ’、及び、ブロック番号配列ＢｌｋＮｏ’が作成されている。図２９Ｂに示されているように、パイプライン処理の１段目では、演算ユニット０が演算ユニット０及び演算ユニット１からのローカルデータをマージし、演算ユニット２が演算ユニット２及び演算ユニット３からのローカルデータをマージし、演算ユニット４が演算ユニット４及び演算ユニット５からのローカルデータをマージし、演算ユニット６が演算ユニット６及び演算ユニット７からのローカルデータをマージする。次に、図２９Ｃに示されているように、パイプライン処理の２段目では、演算ユニット１が演算ユニット０及び演算ユニット２からのローカルデータをマージし、演算ユニット５が演算ユニット４及び演算ユニット６からのローカルデータをマージする。次に、図２９Ｄに示されているように、パイプライン処理の３段目では、演算ユニット３が演算ユニット１及び演算ユニット５からのローカルデータをマージする。このように、ブロック間処理におけるマージ処理はトーナメント方式で階層的に行われる。最後に、図２９Ｅに示されているように、演算ユニット７は、演算ユニット３によって生成された最終的なローカルデータのうち、ブロック番号配列ＢｌｋＮｏ’を先頭から受信し、ブロック番号がブロック番号配列中で格納されている位置、すなわち、レコード順序番号を、ブロック番号に関連付けられた演算ユニットへ分配する。レコード順序番号が分配された演算ユニットは、分配されたレコード順序番号をそれぞれのローカルメモリ上のレコード順序番号配列ＧＯｒｄに順次に格納する。なお、図２９Ｄには、説明の便宜上、ブロック番号配列ＢｌｋＮｏ’の他に、グローバル項目値順序番号配列ＧＶＯｒｄ’及びレコード順序番号配列ＧＯｒｄ’が示されているが、必要とされる最終的なマージ結果は、ブロック番号配列ＢｌｋＮｏ’であることに注意を要する。したがって、マージ処理の最終段では、ブロック番号配列ＢｌｋＮｏ’だけを生成すればよい。なお、パイプライン処理の３段目に位置している演算プロセッサ３が分配処理をさらに行っても構わない。

　図３０は、以上の本発明の一実施形態による表形式データのソート処理によって生成された順序情報の説明図である。これは、図２１Ｂに示されたソート後の順序集合と一致している。ソート処理によって、項目情報は変化しないことに注意を要する。

　［表形式データの多項目ソート処理］
　本発明の一実施形態による表形式データのソート処理は、所定のデータ項目に関するソート処理である。このソート処理によって変化するのは、レコード順序番号配列及び項目値アクセス情報配列である。一方、各ブロックに属するレコード、及び、項目情報は変化しない。よって、複数のデータ項目に関するソート処理は、上述の所定のデータ項目に関するソート処理を繰り返すことによって実現される。本発明の分散メモリ型マルチプロセッサの好ましい一実施形態によれば、多項目ソート処理は、制御ユニットが、複数のデータ項目に関してソート処理を繰り返すように演算ユニットを制御することによって実現される。

　よって、たとえば、図５Ａに示された表形式データに対して、最初に、項目＝“Ｓｃｈｏｏｌ”に関してソート処理を実行し、次に、項目＝”Ａｇｅ”に関してソート処理を実行する場合（多段階ソート処理）、上述のソート処理によって項目＝“
Ｓｃｈｏｏｌ”に関するソートを行い、続いて、同様に、項目＝“Ａｇｅ”に関するソート処理を実行すればよい。なお、複数のデータ項目に関してソート処理を順次適用する場合、優先度の高いデータ項目に関するソート処理が後から適用される。

　或いは、代替的な実施形態では、多項目ソート処理を１段階で実現することも可能である。これば、上記の実施形態におけるブロック内ソート処理で実行される分布数え上げソート処理を複数の項目を併合して実行することにより実現される。たとえば、図５Ａの表形式データの例において、項目＝“Ｓｃｈｏｏｌ”を優先度の低い項目とし、項目＝“Ａｇｅ”を優先度の高い項目として、多項目ソート処理を実施する場合を考える。項目＝“Ｓｃｈｏｏｌ”のグローバル項目値順序番号の値Ｘと項目＝“Ａｇｅ”のグローバル項目値順序番号の値Ｙとを組み合わせて生成される値Ｚを新たなグローバル項目値順序番号とみなしてソート処理を実行すればよい。本例では、Ｘの値の取り得る範囲が０≦Ｘ≦３の４通りであり、かつ、Ｙの値の取り得る範囲が０≦Ｙ≦６の７通りであるので、２つの項目値の組み合わせに対して、４×７＝２８の値、すなわち、０から２７までの値を割り付ける。より具体的には、項目＝“Ａｇｅ”が優先度の高い項目であることから、
Ｚ＝４×Ｙ＋Ｘ
という値Ｚを新たなグローバル項目値順序番号とみなして、ソート処理を実行すればよい。

　実際的には、新たな項目値をもつ新たな表形式データを作成する必要はなく、分布数え上げソート処理のキー値Ｚとして、値Ｚ＝４×Ｙ＋Ｘを使用すればよい。そして、この新しい項目値指定ポインタＺを用いて、ブロック内ソート処理、ブロック間ソート処理１（マージ処理）、及び、ブロック間ソート処理２（分配処理）を実行することにより、データ項目毎にソート処理を実行する場合と同じ結果を得ることができる。なお、ソートが適用される項目の優先順に応じてソート処理の結果が異なることは当然である。

　［表形式データの検索処理の概要］
　次に、本発明の一実施形態による分散メモリ型マルチプロセッサによる表形式データの検索処理について説明する。図３１Ａ及び３１Ｂは本発明の一実施形態による表形式データの検索処理の説明図である。図３１Ａには検索処理前の表形式データが示され、図３１Ｂには検索処理後の表形式データが示され、検索処理前の表形式データは図５Ａに示された表形式データと同一である。同図の例では、表形式データにおいて、項目＝“Ｓｃｈｏｏｌ”に関して、項目値＝“Ｎｏｒｔｈ”という検索条件に一致するレコードが検索されている。検索前のレコード順序番号＝５に相当するレコード（Ｎｏｒｔｈ，６）は、検索処理によってレコード順序番号＝０のレコードとして取り出されている。また、検索前のレコード順序番号＝２に相当するレコード（Ｗｅｓｔ，１１）は、検索条件に一致していないので、検索後の表形式データ中に現れない。ここで、レコード（Ａ，Ｂ）という表記は、データ項目＝“Ｓｃｈｏｏｌ”の項目値がＡであり、データ項目＝“Ａｇｅ”の項目値がＢであるレコードを表している。

　図３１Ａに示された検索処理前の表形式データは、分散メモリ型マルチプロセッサ向けデータ構造を用いると図５Ｂ乃至５Ｄに示されたデータ構造によって表現される。これに対して、図３２Ａ乃至３２Ｄは、本発明の一実施形態による検索処理を、図５Ａ乃至５Ｄに示された表形式データに適用することにより得られる表形式データの説明図である。図３２Ａ乃至３２Ｄを参照して、検索処理の結果を説明する。図３２Ａには、図３１Ａに対応する検索前の（すなわち、検索元の）表形式データの順序情報が示されている。図３２Ｂには、図３１Ｂに対応する検索後の表形式データの順序情報が示され、図３２Ｃ及び図３２Ｄには、図３２Ｂに対応する検索後の表形式データの項目情報が示されている。

　たとえば、図３１Ａの表形式データのブロック０には、検索条件に一致するレコードが存在しないので、図３２Ｂの表形式データのブロック０に関する順序情報には、検索結果となるデータが存在しない。一方、図３１Ａの表形式データのブロック１には、検索条件に一致するレコード（Ｎｏｒｔｈ，６）が存在するので、図３２Ｂの表形式データのブロック１に関する順序情報には、検索結果として、レコード順序番号配列ＧＯｒｄ［０］＝０と、項目値アクセス情報配列［０］＝１が格納されている。この検索結果は、レコード（Ｎｏｒｔｈ，６）が検索結果の中でレコード順序番号＝０のレコードであり、かつ、このレコードに属する項目値が、ブロック１の項目情報の中でランク＝１に対応する領域に格納されていることを意味している。

　このように、本発明の一実施形態による検索処理では、検索処理の前後で変化するのは順序情報（すなわち、レコード順序番号配列及び項目値アクセス情報配列）だけであり、項目情報はソート処理の前後で変化しない。本実施形態の説明では、項目情報は、ローカル項目値番号配列ＶＮｏ、ローカル項目値配列ＬＶＬ、及び、グローバル項目値順序番号配列ＧＶＯｒｄによって構成されている。

　［表形式データの検索処理］
　表形式データの検索処理は、以下の５ステップにより構成される。図３３は、本発明の一実施形態による表形式データの検索処理の概略的なフローチャートである。上述の通り、検索では、順序情報だけが変化する。したがって、検索処理によって作成されるのは、レコード順序番号配列ＧＯｒｄ及び項目値アクセス情報配列ＬＯｒｄである。

　ステップ３３０１：ローカル処理（ヒットフラグ配列設定）
　各演算ユニットが並列的に動作して、それぞれのブロック内で、検索対象となる項目に関して、ローカル項目値配列ＬＶＬ内の各項目値が検索条件に一致するかどうかを判定し、検索条件に一致する項目値に対応するヒットフラグ配列の要素をセットする。当然ながら、１台の演算ユニットに複数のプロセッサが収容されているならば、ブロック単位の処理はプロセッサ毎に実行される。

　ステップ３３０２：ローカル処理（レコード抽出）
　各演算ユニットが並列的に動作して、ヒットフラグがセットされている項目値に対応するレコード順序番号及び項目値アクセス情報を抽出し、レコード順序番号配列ＧＯｒｄ及び項目値アクセス情報配列ＬＯｒｄを作成する。

　ステップ３３０３：グローバル処理（ブロック番号設定）
　各演算ユニットが並列的に動作して、作成されたレコード順序番号配列ＧＯｒｄと同じサイズのブロック番号配列ＢｌｋＮｏを作成し、ブロック番号を設定する。

　ステップ３３０４：グローバル処理（マージ処理）
　各演算ユニットのマージ手段が、レコード順序番号配列ＧＯｒｄ及びブロック番号配列ＢｌｋＮｏをトーナメント方式でマージする。

　ステップ３３０５：グローバル処理（分配処理）
　少なくとも１台の演算ユニットの分配手段が、最終的なブロック番号配列ＢｌｋＮｏの先頭の要素から順に、この要素が格納されている位置の値、すなわち、順序番号を、この要素の値によって指定されるブロック、すなわち、このブロックに関連付けられた演算ユニットへ送信し、各演算ユニットが送信された順序番号をそれぞれのレコード順序番号配列ＧＯｒｄに順次に格納する。

　このように、表形式データの検索処理は、ブロック内での検索処理に相当するローカル処理と、ブロック間でのマージ処理と、ブロック間での分配処理とを含む。

　以下では、図３４乃至３６に示された例を参照して、本発明の一実施形態による表形式データの検索処理の各ステップの処理をより詳細に説明する。

　図３４は本発明の一実施形態による表形式データの検索処理におけるヒットフラグ配列設定処理の説明図である。同図に示されているように、各演算ユニットは、検索対象となる項目＝“Ｓｃｈｏｏｌ”に関して、ローカル項目値配列ＬＶＬの中で検索条件＝“Ｎｏｒｔｈ”に一致する項目値を検索し、ローカルヒットフラグＬｏｃａｌ＿Ｈｉｔ＿Ｆｌａｇの要素のうち、検索条件に一致する項目値に対応する要素をマーキングする（すなわち、フラグを立てる）。たとえば、図３４に示された例では、ブロック０には、検索条件に一致する項目値は存在しないが、ブロック１には、検索条件に一致する項目値＝“Ｎｏｒｔｈ”が存在するので、ローカルヒットフラグ配列中の“Ｎｏｒｔｈ”のランク＝０によって示される位置にフラグが立てられる。

　今度は、図３５Ａ乃至３５Ｃを参照して、検索条件に一致するレコードを抽出する処理を説明する。図３５Ａ乃至３５Ｃは、本発明の一実施形態による表形式データの検索処理におけるローカル処理の説明図である。ここでは、ヒットフラグ配列中のフラグがセットされているレコードが抽出される。具体的には、演算ユニットは、ヒットフラグ配列中のフラグがセットされているレコードの項目値アクセス情報配列ＬＯｒｄ’及びレコード順序番号配列ＧＯｒｄ’をローカルメモリ上に作成する。たとえば、ブロック１に関する演算ユニット１の動作について説明すると、演算ユニット１は、担当レコードのローカル項目値番号配列の要素、すなわち、ローカル項目値番号を配列の先頭から順番に取り出し、このローカル項目値番号によって指定されるヒットフラグ配列の要素がセットされているかどうかを判定する。ヒットフラグがセットされているならば、このローカル項目値番号に対応するレコードは、検索条件に一致しているので、このレコードの項目値アクセス情報及びレコード順序番号がそれぞれ項目値アクセス情報配列ＬＯｒｄ’及びレコード順序番号配列ＧＯｒｄ’に格納される。図３５Ｂに示されているように、このレコード抽出処理は、複数台の演算ユニットによって並列的に実行される。最終的に、図３５Ｃに示されているように、検索条件に一致するレコードに関する項目値アクセス情報配列ＬＯｒｄ’及びレコード順序番号配列ＧＯｒｄ’が演算ユニットのローカルメモリ上に構築される。このとき構築された項目値アクセス情報配列ＬＯｒｄ’は検索結果として生成される順序情報に含まれる項目値アクセス情報ＬＯｒｄと一致する。

　今度は、本発明の一実施形態による表形式データの検索処理のグローバル処理を示す図３６を参照して、検索処理のグローバル処理をより詳細に説明する。最初に、各演算ユニットは、レコード抽出処理によって作成されたレコード順序番号配列ＧＯｒｄ’と同じサイズのブロック番号配列ＢｌｋＮｏ’をローカルメモリ上に作成し、各演算ユニットの担当レコードを示すブロック番号でこのブロック番号配列を充填する。本例では、演算ユニット０が担当するブロック０には、検索条件に一致するレコードが存在しないので、レコード順序番号配列ＧＯｒｄ’及びブロック番号配列ＢｌｋＮｏ’は空である。一方、演算ユニット３が担当するブロック３には、検索条件＝“Ｎｏｒｔｈ”に一致するレコードが２つ存在するので、ＧＯｒｄ［０］＝１４、ＢｌｋＮｏ’［０］＝３、及び、ＧＯｒｄ［１］＝１５、ＢｌｋＮｏ’［１］＝３というローカルデータが作成され、１段目のマージ処理を実行する演算ユニットへ送信される。

　本発明の一実施形態によれば、各演算ユニットによってブロック内で検索された表形式データのレコードは、次に、ブロック間でマージされる。ブロック間のマージでは、それぞれのブロック内で検索されたデータが併合され、全体として検索された併合データが生成される。より具体的には、レコード順序番号配列ＧＯｒｄ’の要素とブロック番号配列ＢｌｋＮｏ’の要素の組が、レコード順序番号の昇順にマージされる。レコード順序番号配列ＧＯｒｄ’の要素はレコード毎に一意に決まる値をもつので、要素の組は一意である。

　本発明の一実施形態による表形式データの検索処理におけるマージ処理は、図１３に示された階層構造と同じ階層構造によって実現することが可能である。ブロック０から７に関連付けられた演算ユニット０から演算ユニット７によって並列的にローカル処理が実行されると、１段目のマージ処理として、演算ユニット０によるブロック０とブロック１のマージ処理、演算ユニット２によるブロック２とブロック３のマージ処理、演算ユニット４によるブロック４とブロック５のマージ処理、及び、演算ユニット６によるブロック６とブロック７のマージ処理が実行される。２段目のマージ処理は、演算ユニット１によるブロック０－１とブロック２－３のマージ処理、及び、演算ユニット５によるブロック４－５とブロック６－７のマージ処理により実現される。最後に、３段目のマージ処理として、演算ブロック３が、ブロック０－３とブロック４－７のマージ処理を実行する。各パイプライン段でマージ処理を担当する演算ユニットは上記の組み合わせに限定されないことに注意を要する。なお、分配処理は、たとえば、演算ユニット３とは別の演算ユニット７によって実行されてもよい。

　マージ処理では、ソートの場合と同様に、各演算ユニットが、１対のブロックに関する情報をマージして、マージされたより高い層の１個のブロックに関する情報を生成する。よって、マージ処理は、複数台の演算ユニットの並列動作によって実現される。また、各演算ユニットは、同じ層に属するマージされたよりブロックの対に関する情報をマージし、マージされたさらに高い層の１個のブロックに関する情報を生成する。このようにマージ処理を並列的かつ階層的に繰り返すことにより、最終的に最上層の１個のブロックに関する情報が生成される。最上層の１個のブロックとは、レコード全体を含むブロックである。演算ユニット３は、最終的に１つのレコード順序番号配列ＧＯｒｄ’及びブロック番号配列ＢｌｋＮｏ’を生成する。レコード順序番号配列ＧＯｒｄ’の要素は、所定の順序（本例では、昇順）に整列させられている。一方、ブロック番号配列ＢｌｋＮｏ’の要素は、本例では、偶然に、昇順に並べられているが、一般には、所定の順序に並べられることはない。

　本発明の一実施形態による表形式データの検索処理におけるマージ処理は、表形式データのソート処理におけるブロック間ソート処理１（ブロック間マージ処理）と全く同様に実現され得るので、これ以上詳細には説明されない。

　以上の説明からわかるように、本発明の一実施形態による検索処理におけるマージ処理では、データアクセスがシーケンシャルアクセスだけに限定され、かつ、各演算ユニットが並列にマージ処理を実行可能である。よって、マルチプロセッサ型処理装置の性能が十分に活かされている。

　本発明の一実施形態による表形式データの検索処理におけるマージ処理によって得られた２つの配列から次のことがわかる。たとえば、配列の組の１行目のデータ＝（５，１）を参照すると、検索後にレコード順序番号０が付与されるレコードは、
（ｉ）検索前に付与されていたレコード順序番号が５であり、
（ｉｉ）ブロック１に属している。

　本発明の一実施形態による表形式データの検索処理では、最後に、各ブロックに属するレコードのレコード順序番号を決定する。このレコード順序番号を決定する処理は分配処理と呼ばれる。分配処理では、少なくとも１台の演算ユニット又はプロセッサコア（たとえば、本例では、演算ユニットＰＥ－７）が、ブロック番号配列ＢｌｋＮｏ’の添字ｉに相当するレコード順序番号をブロック番号ＢｌｋＮｏ［ｉ］で表されるブロック毎に分配し、分配されたレコード順序番号をブロック内で所定の順番（たとえば、昇順）に並べる。この処理は、たとえば、ブロックｊのレコード順序番号配列のｋ番目の要素をＧＯｒｄ［ｊ］［ｋ］とし、レコード順序番号配列ＧＯｒｄ［ｊ］にレコード順序番号を設定するための書き込み用ポインタｋをＯｆｆｓｅｔｓ［ｊ］とすると、次のように記述できる。
オフセット配列ｉｎｄｅｘを初期化；
ｆｏｒ　（ｉ＝０；ｉ＜レコード総数；ｉ＋＋）　｛
　　ＧＯｒｄ［ＢｌｋＮｏ［ｉ］］［Ｏｆｆｓｅｔｓ［ＢｌｋＮｏ［ｉ］］＝ｉ；
　　Ｏｆｆｓｅｔｓ［ＢｌｋＮｏ［ｉ］］＋＋；
｝
　以上の処理によって、各演算ユニットのローカルメモリには、検索条件に一致するレコードのレコード順序番号配列ＧＯｒｄが作成される。上述されているように、ローカル処理において、項目値アクセス情報ＬＯｒｄが既に作成されているので、レコード順序番号配列ＧＯｒｄの作成によって順序情報が完成し、検索処理が終了する。

　或いは、複数台の演算ユニット又はプロセッサコアがブロック番号配列ＢｌｋＮｏの一部を分担して分配処理を行ってもよい。そのため、あるブロックに関するレコード順序番号配列ＧＯｒｄ［ｊ］は複数台の演算ユニットによって分担して処理される。そして、複数の演算ユニットによって分担して作成されたレコード順序番号配列がブロック毎に１つのレコード順序番号配列に統合される。ブロック番号配列ＢｌｋＮｏ’の複数台の演算ユニットへの割り当てが連続的に行われるならば、すなわち、各演算ユニットが担当するブロック番号配列ＢｌｋＮｏ’の一部が連続しているならば、この統合処理は非常に簡単化される。なぜならば、同一のブロックに関して、別々の演算ユニットによって作成されたレコード順序番号配列の間で要素の順番を入れ替える必要がないからである。つまり、レコード順序番号配列の統合処理は、別々に作成されたレコード順序番号配列を単に連結することにより達成される。

　［表形式データの集計処理の概要］
　今度は、本発明の一実施形態による表形式データの集計処理について説明する。図３７Ａ及び３７Ｂは表形式データの集計処理の説明図であり、図３７Ａには、集計元の表形式データが示され、図３７Ｂには、集計結果の表形式データが示されている。集計元の表形式データは、Ｓｃｈｏｏｌ、Ｃｌａｓｓ、Ａｇｅという３つの項目により形成され、たとえば、レコード順序番号＝０のレコードは、
項目＝“Ｓｃｈｏｏｌ”：項目値＝“Ｗｅｓｔ”
項目＝“Ｃｌａｓｓ”：項目値＝“Ａ”
項目＝“Ａｇｅ”：項目値＝１２
であることがわかる。以下では、Ｒｅｃ［０］＝（Ｗｅｓｔ，Ａ，１２）と表記されることがある。一方、集計結果の表形式データは、Ｓｃｈｏｏｌ、Ｃｌａｓｓ、Ａｇｅの個数、Ａｇｅの和という４つの項目により形成されている。すなわち、本例では、項目＝“Ａｇｅ”に関して、項目値の出現回数と、項目値の和とが集計されている。たとえば、集計結果の表形式データのレコードＲｅｃ「０」＝（Ｅａｓｔ，Ａ，３，２０）は、項目＝“Ｓｃｈｏｏｌ”の項目値が“Ｅａｓｔ”であり、項目＝“Ｃｌａｓｓ”の項目値が“Ａ”であるレコードに関して、項目＝“Ａｇｅ”の項目値の出現回数が３回であり（本例では、項目＝“Ａｇｅ”の項目値を含まないレコードは存在しないので、項目値の出現回数はレコードの個数と一致している）、項目＝“Ａｇｅ”の項目値の和が２０であることを意味している。なお、本例における項目＝“Ｓｃｈｏｏｌ”及び項目＝“Ｃｌａｓｓ”のように、集計とは、表形式データのある項目（次元）のある項目値（次元値）毎に、この項目、又は、別の項目の項目値に基づく数量（測度）を算出することである。測度の算出とは、測度の個数をカウントしたり、測度の総和を算出したり、測度の平均値を算出したりすることである。また、次元数は、本例のように、２次元以上でも構わない。例えば、Ｓｃｈｏｏｌという項目と、Ｃａｓｓという項目と、Ａｇｅという項目を含む表形式データである場合に、Ｓｃｈｏｏｌ・Ｃｌａｓｓ別にＡｇｅの平均値を求める処理は、ＳｃｈｏｏｌとＣｌａｓｓを次元とし、Ａｇｅの平均値を測度とする集計処理である。

　このような集計処理では、最初に、次元を設定し、次元値毎にレコードを分類することが必要である。次元値毎にレコードを分類するために、次元値に関してレコードをソートする処理を利用することが可能である。特に、多次元集計においては、レコードを次元値の組毎にグループ化し、同一のグループに属するレコードに含まれる項目値に基づく測度を算出することによって、表形式データ全体の集計が達成される。よって、大規模な表形式データを高速集計するためには、集計のための、特に、多次元集計のための次元を高速に作成する技術が必要である。

　図３８Ａ乃至３８Ｄは、図３７Ａと等価である、本発明の一実施形態によるデータ構造で表現された集計元の表形式データの説明図である。図３８Ａは順序情報を表し、図３８Ｂは項目＝“Ｓｃｈｏｏｌ”に関する項目情報を表し、図３８Ｃは項目＝”Ｃｌａｓｓ”に関する項目情報を表し、図３８Ｄは項目＝“Ａｇｅ”に関する項目情報を表している。レコード順序番号０から３がブロック０に含まれ、レコード順序番号４から７がブロック１に含まれ、レコード順序番号８から１１がブロック２に含まれ、レコード順序番号１２から１５がブロック３に含まれ、レコード順序番号１６から１９がブロック４に含まれ、レコード順序番号２０から２３がブロック５に含まれ、レコード順序番号２４から２７がブロック６に含まれ、レコード順序番号２８から３１がブロック７に含まれている。この表形式データが上述の本発明のコンパイル処理を用いて演算ユニットのローカルメモリ上に構築できることは明白である。

　同様に、図３９Ａ乃至３９Ｅは、図３７Ｂと等価である、本発明の一実施形態によるデータ構造で表現された集計結果の表形式データの説明図である。本例では、図３７Ｂに示された集計結果の表形式データは、図３７Ａに示された集計元の表形式データとはことなるブロックに分割されている。一般に、集計元の表形式データと集計結果の表形式データは、ブロック分割の仕方が異なっている。図３９Ａは順序情報を表し、図３９Ｂは次元１＝“Ｓｃｈｏｏｌ”の項目情報を表し、図３９Ｃは次元２＝“Ｃｌａｓｓ”の項目情報を表し、図３９Ｄは測度１＝“Ｃｏｕｎｔ（Ａｇｅ）”の項目情報を表し、図３９Ｅは測度２＝“Ｓｕｍ（Ａｇｅ）”の項目情報を表している。本例では、レコード順序番号０から４がブロック０に含まれ、レコード順序番号５と６がブロック１に含まれ、レコード順序番号７と８がブロック２に含まれ、レコード順序番号９から１１がブロック３に含まれている。このように表形式データのブロックへの分割法が規定されるならば、この表形式データが上述の本発明のコンパイル処理を用いて演算ユニットのローカルメモリ上に構築できることは明白である。

　表形式データの集計処理では、上述されているように、集計元の表形式データに基づいて、別個の集計結果の表形式データが作成される。このとき、集計結果の表形式データのサイズは、各次元の一意の項目値の個数から推定可能である。具体的には、たとえば、（各次元の一意の項目値の個数）の積によって、集計結果の表形式データのレコード数が決定される。なお、各次元の一意の項目値の個数は、集計元の表形式テーブルにおいて、次元に対応する項目に関するグローバル項目値順序番号の最大値に１を加えた値であるので、実際に集計することなく、集計結果の表形式データのサイズが決定され得る。さらに、集計結果の表形式データのブロックへの分割もまた、集計結果の表形式データのサイズに基づいて、事前に決定され得ることに注意を要する。これらの事前知識を利用することにより、表形式データの集計がより効率的に行われる。

　今度は、図４０を参照して、本発明の一実施形態による表形式データの集計処理の概要を説明する。図４０には、本発明の一実施形態による表形式データの集計方法のフローチャートが示されている。集計方法は、
　集計元の表形式テーブルを各演算ユニットのローカルメモリ上に展開するステップ４００２と、
　集計結果の表形式テーブルのサイズ及びブロック分割定義を決定するステップ４００４と、
　集計結果の表形式テーブルの順序情報を作成するステップ４００６と、
　次元の分割を決定し、次元の項目情報を作成するステップ４００８と、
　次元空間に測度の項目値を割り当てるステップ４０１０と、
　測度の項目値を集計するステップ４０１２と、
　測度の項目情報を作成するステップ４０１４と、
を備える。当然ながら、１台の演算ユニットに複数のプロセッサが収容されているならば、ブロック単位の処理はプロセッサ毎に実行される。

　［集計処理における次元の定義］
　今度は、集計処理における次元の定義について詳述する。集計の次元となる項目（以下、次元項目とも称される）に関して、仮想的なグローバル項目値配列ＧＶＬのサイズ、すなわち、一意の項目値の個数を考える。仮想的なグローバル項目値配列ＧＶＬは、ローカル項目値配列ＬＶＬの要素の値を重複なくマージすることにより生成される配列である。このＧＶＬのサイズは、集計元の表形式テーブルの次元項目に関するグローバル項目値順序番号の最大値＋１である。ここで、グローバル項目値順序番号の最大値は集計元の表形式データから容易に決定される。よって、次元空間のサイズ（すなわち、次元項目の一意の項目値の組の個数）は、ＧＶＬのサイズの積である。図３８Ａ乃至３８Ｄの例では、次元１（Ｓｃｈｏｏｌ）のＧＶＬのサイズ＝４と次元２（Ｃｌａｓｓ）のＧＶＬのサイズ＝３とから、次元空間のサイズは４＊３＝１２である。これにより、次元１の項目値番号と次元２の項目値番号の組（次元１の項目値番号，次元２の項目値番号）は、（０，０）、（０，１）、（０，２）、（１，０）、（１，１）、（１，２）、（２，０）、（２，１）、（２，２）、（３，０）、（３，１）、（３，２）の１２通りであることがわかる。

　以下では、次元が１からＮまでのＮ次元であり、第ｉ次元（１≦ｉ≦Ｎ）のＧＶＬのサイズをＣ_ｉとして、一般的な例について説明する。

　このとき、次元空間のサイズＣＳｉｚｅ＿ａｌｌは、ΠＣ_ｉ，ｉ＝１．．Ｎによって与えられる。但し、Πφ＝１とする。集計結果の表形式データは、次元空間のサイズを参照して、０番目から（Ｍ－１）番目までのＭ個のブロックに分割される。各ブロックのサイズはブロックに収容可能なレコード数を考慮して決定される。ここで、ブロックｋが集計結果の表形式データのＲ_ｋ行からＲ_ｋ＋１－１行までを担当する場合を考える。図３９Ａ乃至３９Ｅの例では、
ブロック０の担当範囲：０行から４行
ブロック１の担当範囲：５行から６行
ブロック２の担当範囲：７行から８行
ブロック３の担当範囲：９行から１１行
と定義されているので、Ｒ_０＝０、Ｒ_１＝５、Ｒ_２＝７、Ｒ_３＝９、Ｒ_４＝１２である。勿論、ブロックの分割定義はこの例に限定されない。

　集計結果の表形式データを作成するためには、ブロックｋに含まれる次元値を特定することが必要である。ブロックｋの第ｐ次元に属する次元値は次のように特定され得る。ここで、次元値、すなわち、項目値は、次元値自体を取り扱う必要はなく、各項目値に付与されているグローバル項目値順序番号によって、個々の項目値を特定することが可能である。グローバル項目値順序番号を用いて記述することにより、項目値のデータ型とは無関係に、整数型を用いて次元値を取り扱うことが可能である。また、次元値を特定するとは、具体的には、ローカル項目値番号配列ＶＮｏ及びローカル項目値配列ＬＶＬを特定することに相当する。

　ＣＳｉｚｅ＿ｈｉｇｈ＝ΠＣ_ｉ，ｉ＝ｐ．．Ｎ
　ＣＳｉｚｅ＿ｌｏｗ＝ΠＣ_ｉ，ｉ＝ｐ＋１．．Ｎ
　但し、Πφ＝１
と表すと、ＣＳｉｚｅ＿ａｌｌ＝４＊３＝１２であり、
第１次元（Ｓｃｈｏｏｌ）に関して、
ＣＳｉｚｅ＿ｈｉｇｈ＝４＊３＝１２
ＣＳｉｚｅ＿ｌｏｗ＝３
であり、第２次元（Ｃｌａｓｓ）に関して、
ＣＳｉｚｅ＿ｈｉｇｈ＝３
ＣＳｉｚｅ＿ｌｏｗ＝１
である。

　一般的に、第ｐ次元のブロックｋのローカル項目値番号配列ＶＮｏ及びローカル項目値配列ＬＶＬの算出は、次の３つのケースに分類して考えることができる。

　ケースＡ：このケースでは、次の関係式、
（Ｒ_ｋ＋１－Ｒ_ｋ）≧ＣＳｉｚｅ＿ｈｉｇｈ
が成り立ち、第ｐ次元のすべての項目値がブロックｋに含まれている。

　ケースＢ：このケースでは、次の関係式、
（Ｒ_ｋ＋１－Ｒ_ｋ）＜ＣＳｉｚｅ＿ｈｉｇｈ
かつ
（（Ｒ_ｋ　ｍｏｄ　ＣＳｉｚｅ＿ｈｉｇｈ）　ｄｉｖ　ＣＳｉｚｅ＿ｌｏｗ）≦（（Ｒ_ｋ＋１－１）　ｍｏｄ　ＣＳｉｚｅ＿ｈｉｇｈ）　ｄｉｖ　ＣＳｉｚｅ＿ｌｏｗ）
が成り立ち、第ｐ次元の項目値が小さい方から順に部分的にブロックｋに含まれている。

　ケースＣ：このケースでは、次の関係式、
（Ｒ_ｋ＋１－Ｒ_ｋ）＜ＣＳｉｚｅ＿ｈｉｇｈ
かつ
（（Ｒ_ｋ　ｍｏｄ　ＣＳｉｚｅ＿ｈｉｇｈ）　ｄｉｖ　ＣＳｉｚｅ＿ｌｏｗ）＞（（Ｒ_ｋ＋１－１）　ｍｏｄ　ＣＳｉｚｅ＿ｈｉｇｈ）　ｄｉｖ　ＣＳｉｚｅ＿ｌｏｗ）
が成り立ち、第ｐ次元の項目値の一部がブロックｋに含まれ、しかも、昇順又は降順のような一定の順序ではなく（単調に変化するのではなく）、小さい値から大きい値へ変化している項目値が、ブロックｋの途中で、大きい値から小さい値へ変化し、再び小さい値から大きい値へ変化する。

　なお、上記関係式中、ｄｉｖは整数の除算を表し、商の小数点以下は切り捨てられる。また、ｍｏｄは整数の剰余を表している。

　この場合分けを上述の本例のブロック分割定義、すなわち、
ブロック０の担当範囲：０行から４行
ブロック１の担当範囲：５行から６行
ブロック２の担当範囲：７行から８行
ブロック３の担当範囲：９行から１１行
に適用すると、上述のように、第１次元（Ｓｃｈｏｏｌ）に関して、
ＣＳｉｚｅ＿ｈｉｇｈ＝４＊３＝１２
ＣＳｉｚｅ＿ｌｏｗ＝３
であるため、すべてのブロック分割がケースＢに分類されることがわかる。たとえば、ブロック０に関して、実際に計算すると、
（Ｒ_ｋ＋１－Ｒ_ｋ）＝（５－０）＝５
ＣＳｉｚｅ＿ｈｉｇｈ＝１２
より、
（Ｒ_ｋ＋１－Ｒ_ｋ）＜ＣＳｉｚｅ＿ｈｉｇｈ
が成立し、
（（Ｒ_ｋ　ｍｏｄ　ＣＳｉｚｅ＿ｈｉｇｈ）　ｄｉｖ　ＣＳｉｚｅ＿ｌｏｗ）
＝（（０　ｍｏｄ　１２）　ｄｉｖ　３）＝０
（（Ｒ_ｋ＋１－１）　ｍｏｄ　ＣＳｉｚｅ＿ｈｉｇｈ）　ｄｉｖ　ＣＳｉｚｅ＿ｌｏｗ）
＝（（５－１）　ｍｏｄ　１２）　ｄｉｖ　３
＝（４　ｍｏｄ　１２）　ｄｉｖ　３＝１
より、
（（Ｒ_ｋ　ｍｏｄ　ＣＳｉｚｅ＿ｈｉｇｈ）　ｄｉｖ　ＣＳｉｚｅ＿ｌｏｗ）≦（（Ｒ_ｋ＋１－１）　ｍｏｄ　ＣＳｉｚｅ＿ｈｉｇｈ）　ｄｉｖ　ＣＳｉｚｅ＿ｌｏｗ）
が成立する。他のブロックについても同様に計算することにより、ケースＢに分類されることがわかる。

　次に、この場合分けを第２次元（Ｃｌａｓｓ）に関して適用すると、上述のように、第２次元（Ｓｃｈｏｏｌ）に関して、
ＣＳｉｚｅ＿ｈｉｇｈ＝３
ＣＳｉｚｅ＿ｌｏｗ＝１
であるため、ブロック毎にケースＡ、ケースＢ、ケースＣに分類されることがわかる。たとえば、ブロック０に関して、実際に計算すると、
（Ｒ_ｋ＋１－Ｒ_ｋ）＝（５－０）＝５
ＣＳｉｚｅ＿ｈｉｇｈ＝３
より、
（Ｒ_ｋ＋１－Ｒ_ｋ）≧ＣＳｉｚｅ＿ｈｉｇｈ
が成立するので、ブロック０はケースＡに分類される。ブロック１に関して、実際に計算すると、
（Ｒ_ｋ＋１－Ｒ_ｋ）＝７－５＝２
ＣＳｉｚｅ＿ｈｉｇｈ＝３
より、
（Ｒ_ｋ＋１－Ｒ_ｋ）＜ＣＳｉｚｅ＿ｈｉｇｈ
であり、さらに、
（（Ｒ_ｋ　ｍｏｄ　ＣＳｉｚｅ＿ｈｉｇｈ）　ｄｉｖ　ＣＳｉｚｅ＿ｌｏｗ）
＝（（５　ｍｏｄ　３）　ｄｉｖ　１）＝２
（（Ｒ_ｋ＋１－１）　ｍｏｄ　ＣＳｉｚｅ＿ｈｉｇｈ）　ｄｉｖ　ＣＳｉｚｅ＿ｌｏｗ）
＝（（７－１）　ｍｏｄ　３）　ｄｉｖ　１
＝（６　ｍｏｄ　３）　ｄｉｖ　１＝０
より、
（（Ｒ_ｋ　ｍｏｄ　ＣＳｉｚｅ＿ｈｉｇｈ）　ｄｉｖ　ＣＳｉｚｅ＿ｌｏｗ）＞（（Ｒ_ｋ＋１－１）　ｍｏｄ　ＣＳｉｚｅ＿ｈｉｇｈ）　ｄｉｖ　ＣＳｉｚｅ＿ｌｏｗ）
が成立するので、ブロック１はケースＣに分類される。さらに、ブロック２に関して、実際に計算すると、
（Ｒ_ｋ＋１－Ｒ_ｋ）＝９－７＝２
ＣＳｉｚｅ＿ｈｉｇｈ＝３
より、
（Ｒ_ｋ＋１－Ｒ_ｋ）＜ＣＳｉｚｅ＿ｈｉｇｈ
であり、さらに、
（（Ｒ_ｋ　ｍｏｄ　ＣＳｉｚｅ＿ｈｉｇｈ）　ｄｉｖ　ＣＳｉｚｅ＿ｌｏｗ）
＝（（７　ｍｏｄ　３）　ｄｉｖ　１）＝０
（（Ｒ_ｋ＋１－１）　ｍｏｄ　ＣＳｉｚｅ＿ｈｉｇｈ）　ｄｉｖ　ＣＳｉｚｅ＿ｌｏｗ）
＝（（９－１）　ｍｏｄ　３）　ｄｉｖ　１
＝（８　ｍｏｄ　３）　ｄｉｖ　１＝２
より、
（（Ｒ_ｋ　ｍｏｄ　ＣＳｉｚｅ＿ｈｉｇｈ）　ｄｉｖ　ＣＳｉｚｅ＿ｌｏｗ）≦（（Ｒ_ｋ＋１－１）　ｍｏｄ　ＣＳｉｚｅ＿ｈｉｇｈ）　ｄｉｖ　ＣＳｉｚｅ＿ｌｏｗ）
が成立するので、ブロック２はケースＢに分類される。さらに、ブロック３に関して、実際に計算すると、
（Ｒ_ｋ＋１－Ｒ_ｋ）＝１２－９＝３
ＣＳｉｚｅ＿ｈｉｇｈ＝３
より、
（Ｒ_ｋ＋１－Ｒ_ｋ）≧ＣＳｉｚｅ＿ｈｉｇｈ
が成立するので、ブロック３はケースＡに分類される。

　図４１には、ブロック０からブロック３のすべてのブロックの第１次元及び第２次元の分類結果が示されている。

　［集計処理における次元の項目情報の作成（ローカル処理）］
　今度は、図４１に示されるような分類結果に基づいて、実際に次元を作成する処理を説明する。第１次元は、すべてのブロックがケースＡに分類されているので、以下の例では、第２次元＝Ｃｌａｓｓに関して、次元作成処理を説明する。

　最初に、ブロック０の第２次元を参照すると、このブロックはケースＡに分類されている。ケースＡでは、一般的に説明すると、第ｐ次元のすべての値がブロックｋに存在する。ブロックｋを担当している演算プロセッサは、第ｐ次元の値のすべてがこの演算プロセッサに割り当てられているので、割り当てられた値を参照することにより、第ｐ次元の一意の値の個数（ＧＶＬのサイズ）がわかる。よって、グローバル項目値順序番号配列ＧＶＯｒｄを作成することができる。本例では、第２次元＝ＣｌａｓｓのＧＶＬのサイズは３である。よって、演算プロセッサは、ブロック０のグローバル項目値順序番号配列ＧＶＯｒｄとして、
ＧＶＯｒｄ［０］＝０
ＧＶＯｒｄ［１］＝１
ＧＶＯｒｄ［２］＝２
を作成する。

　第２次元に関して、ブロック３もまたケースＡに分類されているので、ブロック３のグローバル項目値順序番号配列ＧＶＯｒｄもまた、
ＧＶＯｒｄ［０］＝０
ＧＶＯｒｄ［１］＝１
ＧＶＯｒｄ［２］＝２
である。

　次に、ブロックｋを担当している演算プロセッサは、第ｐ次元に関して、ローカル項目値番号配列ＶＮｏを作成する。ケースＡのブロックｋに含まれているレコードのレコード順序番号、すなわち、行番号をＬとすると、ローカル項目値番号ＶＮｏは、
ＶＮｏ＝（Ｌ　ｍｏｄ　ＣＳｉｚｅ＿ｈｉｇｈ）　ｄｉｖ　ＣＳｉｚｅ＿ｌｏｗ
によって計算することができる。また、ブロックｋに含まれているレコードの行番号Ｌは、上述のように、Ｒ_ｋからＲ_ｋ＋１－１の範囲に入る。よって、ローカル項目値番号配列ＶＮｏは、次の通り決定される。
ｆｏｒ　（ｉ＝０；ｉ＜Ｒ_ｋ＋１－Ｒ_ｋ；ｉ＋＋）　｛
　　ＶＮｏ［ｉ］＝（（ｉ＋Ｒ_ｋ）　ｍｏｄ　ＣＳｉｚｅ＿ｈｉｇｈ）　ｄｉｖ　ＣＳｉｚｅ＿ｌｏｗ；
｝
　第２次元のブロック０の例では、
ＶＮｏ［０］＝（０　ｍｏｄ　３）　ｄｉｖ　１＝０
ＶＮｏ［１］＝（１　ｍｏｄ　３）　ｄｉｖ　１＝１
ＶＮｏ［２］＝（２　ｍｏｄ　３）　ｄｉｖ　１＝２
ＶＮｏ［３］＝（３　ｍｏｄ　３）　ｄｉｖ　１＝０
ＶＮｏ［４］＝（４　ｍｏｄ　３）　ｄｉｖ　１＝１
が得られる。

　同様に、第２次元のブロック３の例では、
ＶＮｏ［０］＝（９　ｍｏｄ　３）　ｄｉｖ　１＝０
ＶＮｏ［１］＝（１０　ｍｏｄ　３）　ｄｉｖ　１＝１
ＶＮｏ［２］＝（１１　ｍｏｄ　３）　ｄｉｖ　１＝２
が得られる。

　次に、ブロック１の第２次元を参照すると、ブロック１はケースＣに分類されている。ケースＣでは、一般に、ブロックｋの第ｐ次元の値は、ブロックｋ内では、前半の昇順部分１と後半の昇順部分２とに分離され、前半の昇順部分１の最後で最大値に達し、後半の昇順部分２の先頭で最小値に戻る。このとき、グローバル項目値順序番号配列ＧＶＯｒｄを決定するために、最初に、次の変数Ｇａｐを計算する。
Ｇａｐ＝（（Ｒ_ｋ　ｍｏｄ　ＣＳｉｚｅ＿ｈｉｇｈ）　ｄｉｖ　ＣＳｉｚｅ＿ｌｏｗ）－（（（Ｒ_ｋ＋１－１）　ｍｏｄ　ＣＳｉｚｅ＿ｈｉｇｈ）　ｄｉｖ　ＣＳｉｚｅ＿ｌｏｗ）－１
　ブロック１の第２次元の場合には、
Ｇａｐ＝（（５　ｍｏｄ　３）　ｄｉｖ　１）－（（（７－１）　ｍｏｄ　３）　ｄｉｖ　１）－１＝２－０－１＝１
となる。グローバル項目値順序番号配列ＧＶＯｒｄのサイズは、第２次元のＧＶＬのサイズからＧａｐを減算した値、すなわち、
３－Ｇａｐ＝３－１＝２
である。

　ケースＣでは、グローバル項目値順序番号の最小値と最大値は必ずグローバル項目値順序番号配列ＧＶＯｒｄに格納され、最小値と最大値の間の区間は、区間の先頭の格納位置及び格納値が、
（（Ｒ_ｋ＋１－１）　ｍｏｄ　ＣＳｉｚｅ＿ｈｉｇｈ）　ｄｉｖ　ＣＳｉｚｅ＿ｌｏｗ
によって表され、区間の末尾の格納位置及び格納値が、それぞれ、
（Ｒ_ｋ　ｍｏｄ　ＣＳｉｚｅ＿ｈｉｇｈ）　ｄｉｖ　ＣＳｉｚｅ＿ｌｏｗ
（（Ｒ_ｋ　ｍｏｄ　ＣＳｉｚｅ＿ｈｉｇｈ）　ｄｉｖ　ＣＳｉｚｅ＿ｌｏｗ）－Ｇａｐ　
によって表される。

　ブロック１の第２次元の例では、グローバル項目値順序番号配列ＧＶＯｒｄのサイズは２であり、グローバル項目値順序番号の最小値＝０と最大値＝２が必ずグローバル項目値順序番号配列ＧＶＯｒｄに格納されているので、
ＧＶＯｒｄ［０］＝０
ＧＶＯｒｄ［１］＝２
が得られる。なお、中間の区間の先頭の位置及び値は、
（（Ｒ_ｋ＋１－１）　ｍｏｄ　ＣＳｉｚｅ＿ｈｉｇｈ）　ｄｉｖ　ＣＳｉｚｅ＿ｌｏｗ＝（（７－１）　ｍｏｄ　３）　ｄｉｖ　１＝０　ｄｉｖ　１＝０
である。本例では、実際には中間の区間が存在しないので、中間の区間の先頭は、グローバル項目値順序番号配列ＧＶＯｒｄの先頭と一致している。また、中間の区間の末尾の位置は、
（（Ｒ_ｋ　ｍｏｄ　ＣＳｉｚｅ＿ｈｉｇｈ）　ｄｉｖ　ＣＳｉｚｅ＿ｌｏｗ）－Ｇａｐ＝（（５　ｍｏｄ　３）　ｄｉｖ　１）－１＝（２　ｄｉｖ　１）－１＝１
であり、中間の区間の末尾の値は、
（Ｒ_ｋ　ｍｏｄ　ＣＳｉｚｅ＿ｈｉｇｈ）　ｄｉｖ　ＣＳｉｚｅ＿ｌｏｗ＝（（５　ｍｏｄ　３）　ｄｉｖ　１）＝２　ｄｉｖ　１＝２
である。本例では、実際には中間の区間が存在しないので、中間の区間の末尾は、グローバル項目値順序番号配列ＧＶＯｒｄの末尾と一致している。

　さらに、ブロックｋを担当している演算プロセッサは、第ｐ次元に関して、ローカル項目値番号配列ＶＮｏを作成する。ケースＣの場合、ブロックｋに含まれている項目値は、項目値全体のうち、最小値と第１の中間値との間のすべての値と、第２の中間値と最大値との間のすべての値である。換言すると、ブロックｋには、項目値全体のうち、第１の中間値と第２の中間値との間の項目値が含まれていない。これをローカル項目値番号の観点からみると、ローカル項目値番号配列ＶＮｏには、先頭から順に、第２の中間値に対応する項目値番号から連続的に最大値に対応する項目値番号までが格納され、次に、最小値に対応する項目値番号から連続的に第１の中間値に対応する項目値番号までが格納されている。ブロック１の第２次元に関しては、簡単に、
ＶＮｏ［０］＝１
ＶＮｏ［１］＝０
となる。ローカル項目値番号配列ＶＮｏの一般的な計算法は次の通りである。

　変数ＨｉｇｈＰａｒｔＳｔａｒｔを、
ＨｉｇｈＰａｒｔＳｔａｒｔ＝（Ｒ_ｋ　ｍｏｄ　ＣＳｉｚｅ＿ｈｉｇｈ）　ｄｉｖ　ＣＳｉｚｅ＿ｌｏｗ
と定義すると、上記のＧａｐを用いて、ローカル項目値番号配列ＶＮｏは、
ｆｏｒ　（ｉ＝Ｒ_ｋ；ｉ＜Ｒ_ｋ＋１；ｉ＋＋）　｛
　　ｏｆｆｓｅｔ　＝　（ｉ　ｍｏｄ　ＣＳｉｚｅ＿ｈｉｇｈ）　ｄｉｖ　ＣＳｉｚｅ＿ｌｏｗ；
　　ｉｆ　（ｏｆｆｓｅｔ　＞＝　ＨｉｇｈＰａｒｔＳｔａｒｔ）　｛
　　　　ＶＮｏ［ｉ－Ｒ_ｋ］＝ｏｆｆｓｅｔ　－　Ｇａｐ；
　　｝　ｅｌｓｅ　｛
　　　　ＶＮｏ［ｉ－Ｒ_ｋ］＝ｏｆｆｓｅｔ；
　　｝
｝
として取得される。

　最後に、ブロック２の第２次元を参照すると、ブロック２はケースＢに分類されている。ケースＢでは、一般に、ブロックｋの第ｐ次元の値は、昇順に出現する。このとき、グローバル項目値順序番号配列ＧＶＯｒｄを決定するためには、グローバル項目値順序番号の最小値及び最大値を決定すればよい。グローバル項目値順序番号の最小値Ｍｉｎ（ＧＶＯｒｄ）及び最大値Ｍａｘ（ＧＶＯｒｄ）は、それぞれ、
Ｍｉｎ（ＧＶＯｒｄ）＝（Ｒ_ｋ　ｍｏｄ　ＣＳｉｚｅ＿ｈｉｇｈ）　ｄｉｖ　ＣＳｉｚｅ＿ｌｏｗ
及び
Ｍａｘ（ＧＶＯｒｄ）＝（（Ｒ_ｋ＋１－１）　ｍｏｄ　ＣＳｉｚｅ＿ｈｉｇｈ）　ｄｉｖ　ＣＳｉｚｅ＿ｌｏｗ
によって決定される。よって、本例において、ブロック１の第２次元に関して、
Ｍｉｎ（ＧＶＯｒｄ）＝（７　ｍｏｄ　３）　ｄｉｖ　１＝１
Ｍａｘ（ＧＶＯｒｄ）＝（（９－１）　ｍｏｄ　３）　ｄｉｖ　１＝２
が得られる。したがって、ブロック２の第２次元のグローバル項目値順序番号配列ＧＶＯｒｄは、
ＧＶＯｒｄ［０］＝１
ＧＶＯｒｄ［１］＝２
である。

　さらに、ブロックｋを担当している演算プロセッサは、第ｐ次元に関して、ローカル項目値番号配列ＶＮｏを作成する。ケースＢのブロックｋに含まれているレコードのレコード順序番号、すなわち、行番号をＬとすると、ローカル項目値番号ＶＮｏは、
ＶＮｏ＝（Ｌ　ｍｏｄ　ＣＳｉｚｅ＿ｈｉｇｈ）　ｄｉｖ　ＣＳｉｚｅ＿ｌｏｗ　－　Ｍｉｎ（ＧＶＯｒｄ）
によって計算することができる。また、ブロックｋに含まれているレコードの行番号Ｌは、上述のように、Ｒ_ｋからＲ_ｋ＋１－１の範囲に入る。よって、ローカル項目値番号配列ＶＮｏは、次の通り決定される。
ｆｏｒ　（ｉ＝０；ｉ＜Ｒ_ｋ＋１－Ｒ_ｋ；ｉ＋＋）　｛
　　ＶＮｏ［ｉ］＝（（（ｉ＋Ｒ_ｋ）　ｍｏｄ　ＣＳｉｚｅ＿ｈｉｇｈ）　ｄｉｖ　ＣＳｉｚｅ＿ｌｏｗ）－　Ｍｉｎ（ＧＶＯｒｄ）
｝
　ブロック２の第２次元の例では、
ＶＮｏ［０］＝（（７　ｍｏｄ　３）　ｄｉｖ　１）－１＝０
ＶＮｏ［１］＝（（８　ｍｏｄ　３）　ｄｉｖ　１）－１＝１
が得られる。

　以上の処理により、第２次元に関して、図４２Ａ乃至４２Ｄに示されているように、ブロック毎にローカル項目値番号配列ＶＮｏ及びグローバル項目値順序番号配列ＧＶＯｒｄが得られる。

　［集計処理における次元の項目情報の作成（グローバル処理）］
　今度は、本発明の一実施形態による表形式データの集計処理における項目情報作成処理を示す図４３を参照して、項目情報作成処理のグローバル処理をより詳細に説明する。最初に、各演算ユニットは、集計結果の表形式データのローカルな項目情報作成処理によって作成されたグローバル項目値順序番号配列ＧＶＯｒｄと同じサイズのブロック番号配列ＢｌｋＮｏをローカルメモリ上に作成し、各演算ユニットの担当レコードを示すブロック番号でこのブロック番号配列を充填する。さらに、各演算ユニットは、集計元の表形式データのローカル項目値配列ＬＶＬを準備する。各演算処理ユニットは、集計元の表形式データのローカル項目値配列ＬＶＬと、集計結果の表形式データのブロック番号配列ＢｌｋＮｏ及びグローバル項目値順序番号配列ＧＶＯｒｄとをローカルデータとして、１段目のマージ処理を実行する演算ユニットへ送信する。

　本発明の一実施形態によれば、各演算ユニットによってブロック内で準備されたローカルデータは、次に、ブロック間でマージされる。ブロック間のマージでは、それぞれのブロック内で準備されたデータが併合され、全体として新たな併合データが生成される。より具体的には、集計元の表形式データのローカル項目値配列ＬＶＬがローカル項目値の昇順にマージされると共に、集計結果の表形式データのグローバル項目値順序番号配列ＧＶＯｒｄの要素とブロック番号配列ＢｌｋＮｏの要素の組がグローバル項目値順序番号をキーとしてマージされる。ここでは、集計元の表形式データに関連する項目情報と、集計結果の表形式データに関連する項目値情報とがそれぞれ独立にマージされていることに注意を要する。

　本発明の一実施形態による表形式データの検索処理におけるマージ処理は、図１３に示された階層構造と同じ階層構造によって実現することが可能である。ブロック０から７に関連付けられた演算ユニット０から演算ユニット７によって並列的にローカル処理が実行されると、１段目のマージ処理として、演算ユニット０によるブロック０とブロック１のマージ処理、演算ユニット２によるブロック２とブロック３のマージ処理、演算ユニット４によるブロック４とブロック５のマージ処理、及び、演算ユニット６によるブロック６とブロック７のマージ処理が実行される。２段目のマージ処理は、演算ユニット１によるブロック０－１とブロック２－３のマージ処理、及び、演算ユニット５によるブロック４－５とブロック６－７のマージ処理により実現される。最後に、３段目のマージ処理として、演算ブロック３が、ブロック０－３とブロック４－７のマージ処理を実行する。各パイプライン段でマージ処理を担当する演算ユニットは上記の組み合わせに限定されないことに注意を要する。なお、分配処理は、たとえば、演算ユニット３とは別の演算ユニット７によって実行されてもよい。

　マージ処理では、ソートの場合と同様に、各演算ユニットが、１対のブロックに関する情報をマージして、マージされたより高い層の１個のブロックに関する情報を生成する。よって、マージ処理は、複数台の演算ユニットの並列動作によって実現される。また、各演算ユニットは、同じ層に属するマージされたよりブロックの対に関する情報をマージし、マージされたさらに高い層の１個のブロックに関する情報を生成する。このようにマージ処理を並列的かつ階層的に繰り返すことにより、最終的に最上層の１個のブロックに関する情報が生成される。最上層の１個のブロックとは、レコード全体を含むブロックである。演算ユニット３は、最終的に、集計元の表形式データに関するローカル項目値番号配列（すなわち、仮想的なグローバル項目値番号配列）と、集計結果の表形式データに関連する１つのグローバル項目値順序番号配列ＧＶＯｒｄ及びブロック番号配列ＢｌｋＮｏを生成する。集計結果の表形式データに関連する項目情報は、グローバル項目値順序番号の順序（本例では、昇順）に整列させられている。

　本発明の一実施形態による表形式データの集計処理におけるマージ処理は、表形式データのソート処理におけるブロック間ソート処理１（ブロック間マージ処理）と全く同様に実現され得るので、これ以上詳細には説明されない。

　以上の説明からわかるように、本発明の一実施形態による集計処理におけるマージ処理では、データアクセスがシーケンシャルアクセスだけに限定され、かつ、各演算ユニットが並列にマージ処理を実行可能である。よって、マルチプロセッサ型処理装置の性能が十分に活かされている。

　本発明の一実施形態による表形式データの集計処理における次元作成処理では、最後に、各ブロックに含まれるローカル項目値配列ＬＶＬを作成する。このローカル項目値配列を生成する処理は分配処理とも呼ばれる。分配処理では、少なくとも１台の演算ユニット（たとえば、本例では、演算ユニットＰＥ－７）が、ブロック番号配列ＢｌｋＮｏの添字ｉに相当するグローバル項目値順序番号によって指定される項目値を仮想的なグローバル項目値配列ＬＶＬから取り出し、この項目値をブロック番号によって指定されたブロック毎に分配する。分配された項目値を受信した演算ユニットは、受信した項目値をこの演算ユニットのローカルメモリ上のローカル項目値配列ＬＶＬに順次に格納する。

　この処理は、たとえば、ブロックｊのローカル項目値配列のｋ番目の要素をＬＶＬ［ｊ］［ｋ］とし、ローカル項目値配列ＬＶＬ［ｊ］［ｋ］に項目値を設定するための書き込み用ポインタｋをＯｆｆｓｅｔｓ［ｊ］とし、仮想的なグローバル項目値配列を（ブロック毎のローカル項目値配列と区別するために）ＧＶＬとすると、次のように記述できる。
オフセット配列Ｏｆｆｓｅｔｓを初期化；
ｆｏｒ　（ｉ＝０；ｉ＜一意のグローバル項目値の個数；ｉ＋＋）　｛
　　ＬＶＬ［ＢｌｋＮｏ［ｉ］］［Ｏｆｆｓｅｔｓ［ＢｌｋＮｏ［ｉ］］＝ＧＶＬ［ＧＶＯｒｄ［ｉ］］；
　　Ｏｆｆｓｅｔｓ［ＢｌｋＮｏ［ｉ］］＋＋；
｝
　以上の処理によって、各演算ユニットのローカルメモリには、集計処理の次元に関する項目情報に含まれるローカル項目値配列ＬＶＬが作成される。上述されているように、ローカル処理において、ローカル項目値番号配列ＶＮｏ及びグローバル項目値順序番号配列ＧＶＯｒｄが既に作成されているので、ローカル項目値配列ＬＶＬの作成によって集計の次元に関する項目情報が完成する。

　本例の場合も、複数台の演算ユニットが分配処理を担当してもよい。

　なお、集計の次元に関する項目情報、すなわち、ローカル項目値番号配列ＶＮｏ、グローバル項目値順序番号配列ＧＯｒｄ、及び、ローカル項目値配列ＬＶＬは、たとえば、集計結果の表形式データを分担して保持する演算ユニットが、他の演算ユニットから、他の演算ユニットが保持している集計元の表形式データのグローバル項目値順序番号配列ＧＶＯｒｄ及びローカル項目値配列ＶＬを取得することにより、各演算ユニットが独立に取得してもよい。

　［集計処理における測度の作成］
　最初に、測度の項目に関して、グローバル項目値配列ＧＶＬを定義する。グローバル項目値配列ＧＶＬは、各ブロックに存在する項目値を重複無しにマージすることによって得られる仮想的な項目値配列である。ここで、仮想的とは、実際に作成する必要がないということを意味している。この仮想的なグローバル項目値配列ＧＶＬのデータ型は、ローカル項目値配列ＬＶＬのデータ型と同じであり、文字列型、整数型、浮動小数点型などの種々のデータ型をとる。グローバル項目値配列ＧＶＬに格納されている項目値は所定の順序（たとえば、昇順）に並べられている。上述の通り、格納されている項目値に重複がない。さらに、グローバル項目値配列ＧＶＬのサイズは、各ブロックに存在するグローバル項目値順序番号配列ＧＶＯｒｄの格納値の最大値＋１である。

　測度は次元値の組毎に値を集計することにより作成される。よって、測度作成処理は、集計元の表形式データに関して、次元値の組、すなわち、次元値に対応する項目値番号の組を項目値の昇順にソートし、ソートされた項目値番号の組毎に測度の値を計算し、計算された測度の値から項目毎に項目情報を作成する。

　図４４Ａ乃至４４Ｊは、測度作成のための次元値の組のソート処理の説明図である。このソート処理では、最初に、優先度の低い第２次元に関して、項目値アクセス情報配列ＬＯｒｄをソートし、次に、優先度の高い第１次元に関して、項目値アクセス情報配列ＬＯｒｄを再度ソートする。以下では、集計元の表形式データのブロック０の例について説明する。ソート処理は、よく知られているカウンティングソートを使用する。

　図４４Ａ乃至図４４Ｄは、ローカル項目値番号をカウントアップする処理の説明図である。次に、図４４Ｅに示されているように、カウントアップによって生成されたカウント配列Ｃｏｕｎｔを累計数化し、累計数配列Ａｇｇｒを作成する。配列Ａｇｇｒは、Ｃｏｕｎｔ配列の要素を１個後へずらして累計数化することにより作成される。

　次に、図４４Ｆ乃至図４４Ｇに示されているように、項目値アクセス情報配列ＬＯｒｄの要素を累計数配列Ａｇｇｒの要素をポインタとして用いて転送することにより、ソートされた項目値アクセス情報配列ＬＯｒｄ’が作成される。図４４Ｈには、第２次元に関するソート処理によって生成された項目値アクセス情報配列ＬＯｒｄ’が示されている。

　続いて、図４４Ｉに示されているように、項目値アクセス情報配列ＬＯｒｄ’を優先度の高い第１次元に関してソートすると、項目値アクセス情報配列ＬＯｒｄ’’が得られる。

　以上のソート処理は、複数台の演算ユニットによって並列的に実行され、図４４Ｊに示されるように、ブロック０からブロック７までのすべてのブロックについて、項目値アクセス情報配列ＬＯｒｄ’’が生成される。

　次に、次元に関してソートされた項目値アクセス情報配列ＬＯｒｄ’’を用いて、測度に関して、次元空間内順序番号配列ＣｕｂｅＡｄｒと、この次元空間内順序番号に対応する測度値を格納した測度項目値配列ｗＶＬを作成する。次元空間内順序番号とは、次元値の項目値番号の組に対して、次元値のソート順に付与された順序番号である。次元空間順序番号は、本例では、（第１次元のＧＶＯｒｄの値）×（次元２の仮想的なグローバル項目値配列のサイズの積）＋（第２次元のＧＶＯｒｄの値）によって計算される。図４５には、次元空間内順序番号配列及び測度項目値配列の作成処理が示されている。

　すべてのブロックに関して、演算ユニットによって次元空間内順序番号配列ＣｕｂｅＡｄｒ及び測度項目値配列ｗＶＬが作成されると、演算ユニットは、次元空間内順序番号毎に集計値を計算する。本例では、測度の値の出現回数Ｃｏｕｎｔと、測度の値の和Ｓｕｍとが計算される。図４６には、次元空間内順序番号配列ＣｕｂＡｄｒと測度項目値配列ｗＶＬとから、測度出現回数配列Ｃｏｕｎｔと測度和配列Ｓｕｍを作成する処理が示されている。本例では、ＣｕｂｅＡｄｒの値が重複していなければ、Ｃｏｕｎｔ配列に１が格納され、ＳｕｍにｗＶＬの値が格納される。一方、ブロック０のＣｕｂｅＡｄｒ＝７のように、ＣｕｂｅＡｄｒに重複値が存在するならば、Ｃｏｕｎｔ配列及びＳｕｍ配列を作成する際に、次元空間内順序番号を１つにまとめ、ＣｕｂｅＡｄｒの重複回数が配列Ｃｏｕｎｔに格納され、同一のＣｕｂｅＡｄｒに対するｗＶＬの値の和が配列Ｓｕｍに格納される。同時に重複値を含まない次元空間内順序番号配列ＣｕｂｅＡｄｒ’も作成される。

　次に、図４７に示されているように、ＣｕｂｅＡｄｒ’の値をキーとして、配列Ｃｏｕｎｔと配列Ｓｕｍが複数のブロック間でマージされる。マージ処理は、本明細書中で既に説明されているように、複数台の演算ユニットのマージ手段がトーナメント方式でパイプライン処理を実行することによって実現される。本例では、ローカルデータとして、次元空間内順序番号配列ＣｕｂｅＡｄｒ’、出現回数配列Ｃｏｕｎｔ、及び、和配列Ｓｕｍが利用され、同じ次元空間内順序番号に関連付けられた出現回数及び和が併合されると共に、ローカルデータの各要素は次元空間内順序番号の昇順に並べられる。

　最後に、トーナメント方式でマージされた出現回数配列Ｃｏｕｎｔ及び和配列Ｓｕｍを、既に作成されている集計結果の表形式データの順序情報を用いて、集計結果の表形式データの項目情報に変換する。図４８Ａは集計結果の表形式データの順序情報を示し、図４８Ｂは出現回数配列Ｃｏｕｎｔに関するコンパイル処理の説明図であり、図４８Ｃは和配列Ｓｕｍに関するコンパイル処理の説明図である。コンパイル処理については、本明細書中で既に説明されているので、これ以上詳細には説明しない。

　以上の集計処理により、図３９Ｄ及び３９Ｅに示された集計結果の表形式データが作成される。

　本発明は、以上の実施の形態に限定されることなく、特許請求の範囲に記載された発明の範囲内で、種々の変更が可能であり、それらも本発明の範囲内に包含されるものであることは言うまでもない。

Claims (17)

1. 　専用のローカルメモリ及びプロセッサを含み、相互にデータを送受するため通信接続されている複数台の演算ユニットを備え、
   　一連のデータが上記複数台の演算ユニットに関連付けられた複数個のブロックに分割されて上記複数台の演算ユニットのそれぞれの専用のローカルメモリに保持され、上記一連のデータが上記複数台の演算ユニットのパイプライン処理によって操作される、分散メモリ型マルチプロセッサであって、
   　各演算ユニットが、前のパイプライン段にある１台以上の演算ユニットからそれぞれのローカルデータを受信し、少なくとも２つの受信されたローカルデータを１つのさらなるローカルデータに変換し、上記さらなるローカルデータを後のパイプライン段にある１台の演算ユニットへ送信するマージ手段を含み、
   　前記複数台の演算ユニットのマージ手段が最終的に１つのグローバルデータを生成するようにトーナメント方式で動的に接続可能であり、
   　少なくとも１台のいずれかの演算ユニットが、前記複数個のブロックに対応するブロック番号に基づいて、前記グローバルデータを分割し前記複数台の演算ユニットへ割り当てる分配手段を含む、
   分散メモリ型マルチプロセッサ。
2. 　上記一連のデータがデータ項目に対応した項目値を含むレコードの配列として表現される表形式データであり、
   　上記複数個のブロックに分割された上記表形式データのうち各演算ユニットに割り当てられた担当レコードが、レコードの順序に依存する順序情報と各データ項目に依存する項目情報とに分離されている、
   請求項１記載の分散メモリ型マルチプロセッサ。
3. 　上記順序情報が、上記表形式データ内での上記担当レコードの原始レコード位置番号を上記ブロック内での上記担当レコードのレコード順序番号の順番に格納するレコード順序番号配列、及び、上記担当レコードに含まれる上記項目値にアクセスする項目値アクセス情報を上記レコード順序番号の順番に格納する項目値アクセス情報配列により形成され、
   　上記項目情報が、上記担当レコードに含まれる一意の項目値が所定の順序で格納されているローカル項目値配列、上記担当レコードに含まれる上記項目値が上記ローカル項目値配列内に格納されている位置を指定するローカル項目値番号が上記担当レコードの上記原始レコード位置番号の順番に格納されているローカル項目値番号配列、及び、上記表形式データの全体で上記所定の順序に基づいて上記ローカル項目値配列中の上記一意の項目値に割り当てられた順序番号が格納されているグローバル項目値順序番号配列により形成されている、
   請求項２記載の分散メモリ型マルチプロセッサ。
4. 　各演算ユニットが、
   　上記分散メモリ型マルチプロセッサに接続されている外部装置からこの演算ユニットに割り当てられた上記担当レコードを受信する手段と、
   　受信された上記担当レコードから、上記レコード順序番号配列及び上記項目値アクセス情報配列を生成し、この演算ユニットの上記専用のローカルメモリに格納する手段と、
   　項目毎に、上記担当レコード中の項目値を上記所定の順序でソートすることにより、上記ローカル項目値配列、及び、上記ローカル項目値番号配列を生成し、この演算ユニットの上記専用のローカルメモリに格納するローカルコンパイル手段と、
   　項目毎に、上記ローカル項目値配列、上記担当レコードの範囲内で上記所定の順序に基づいて上記ローカル項目値配列に含まれる上記一意の項目値に割り当てられた順序番号が格納されているローカル項目値順序番号配列、及び、上記ローカル項目値順序番号配列中の上記順序番号に関連した上記担当レコードを示す上記ブロック番号を含むブロック番号配列を、上記ローカルデータとして、この演算ユニットの後のパイプライン段にある演算ユニットへ送信する手段と、
   を含み、
   　各演算ユニットの上記マージ手段が、前のパイプライン段からの少なくとも２つのローカルデータに含まれている少なくとも２つのローカル項目値配列中の項目値を上記所定の順序でマージすることにより、上記少なくとも２つのローカルデータを、さらなるブロック番号配列、さらなるローカル項目値順序番号配列及びさらなるローカル項目値配列により形成された１つのローカルデータに変換する手段を含み、
   　上記分配手段が、最終的に生成されたさらなるローカル項目値順序番号配列に格納されている順序番号を、対応する最終的に生成されたさらなるブロック番号配列に格納されているブロック番号に関連付けられた演算ユニットへ送信する手段を含み、
   　各演算ユニットが、上記送信された順序番号を上記グローバル項目値順序番号配列に順次に格納する手段をさらに含む、
   請求項３記載の分散メモリ型マルチプロセッサ。
5. 　各演算ユニットが、
   　所定の項目に関して、上記担当レコードを含むブロック毎に、上記ローカル項目値番号をキーとして上記レコード順序番号配列、上記項目値アクセス情報配列及び上記グローバル項目値順序番号配列にソートを適用し、これによって、ローカルソートされたレコード順序番号配列、ローカルソートされた項目値アクセス情報配列及びローカルソートされたグローバル項目値順序番号配列を生成するローカルソート手段と、
   　上記所定の項目に関して、上記ローカルソートされたグローバル項目値順序番号配列、上記ローカルソートされたレコード順序番号配列、及び、上記ローカルソートされたレコード順序番号配列に関連した上記担当レコードを示す上記ブロック番号を含むブロック番号配列を、上記ローカルデータとして、この演算ユニットの後のパイプライン段にある演算ユニットへ送信する手段と、
   を含み、
   　各演算ユニットの上記マージ手段が、前のパイプライン段からの少なくとも２つのローカルデータに含まれている上記ローカルソートされたグローバル項目値順序番号配列と上記ローカルソートされたレコード順序番号配列との組を所定の順序でマージすることにより、上記少なくとも２つのローカルデータを、さらなるグローバル項目値順序番号配列、さらなるレコード順序番号配列及びさらなるブロック番号配列により形成された１つのローカルデータに変換する手段を含み、
   　上記分配手段が、最終的に生成されたさらなるブロック番号配列に含まれているブロック番号の上記さらなるブロック番号配列中での順序番号を、上記ブロック番号に関連付けられた演算ユニットへ送信する手段を含み、
   　各演算ユニットが、上記送信された順序番号を上記レコード順序番号配列に順次に格納する手段をさらに含む、
   請求項３記載の分散メモリ型マルチプロセッサ。
6. 　各演算ユニットが、
   　所定の項目に関して、上記担当レコードを含むブロック毎に、検索条件に一致する項目値を含むレコードに対応する新たなレコード順序番号配列及び新たな項目値アクセス情報配列を生成し、上記項目値アクセス情報配列を上記新たな項目値アクセス情報配列で置き換えるローカル検索手段と、
   　上記所定の項目に関して、上記新たなレコード順序番号配列、及び、上記新たなレコード順序番号配列に関連した上記担当レコードを示す上記ブロック番号を含むブロック番号配列を、上記ローカルデータとして、この演算ユニットの後のパイプライン段にある演算ユニットへ送信する手段と、
   を含み、
   　各演算ユニットの上記マージ手段が、前のパイプライン段からの少なくとも２つのローカルデータに含まれている上記新たなレコード順序番号配列と上記ブロック番号配列との組を所定の順序でマージすることにより、上記少なくとも２つのローカルデータを、さらなるレコード順序番号配列及びさらなるブロック番号配列により形成された１つのローカルデータに変換する手段を含み、
   　上記分配手段が、最終的に生成されたさらなるブロック番号配列に含まれているブロック番号の上記さらなるブロック番号配列中での順序番号を、上記ブロック番号に関連付けられた演算ユニットへ送信する手段を含み、
   　各演算ユニットが、上記送信された順序番号を上記新たなレコード順序番号配列に順次に格納する手段をさらに含む、
   請求項３記載の分散メモリ型マルチプロセッサ。
7. 　前記複数台の演算ユニットが、集計元の表形式データとして使用される第１の表形式データに関する第１の担当レコード、及び、上記第１の表形式データの所定の項目の組に関する項目値の組毎に少なくとも１つの別の集計項目に関する項目値を集計することにより得られる集計結果を表現する第２の表形式データに関する第２の担当レコードをそれぞれの専用のローカルメモリに格納するように構成され、
   　各演算ユニットが、
   　上記分散メモリ型マルチプロセッサに接続されている外部装置から、上記第２の表形式データのうちこの演算ユニットに分割される上記第２の担当レコードの範囲情報、及び、上記所定の項目の組に属する一意の項目値の個数の組を受信する手段と、
   　上記第２の担当レコードの範囲情報に基づいて、この演算ユニットに割り当てられた上記第２の担当レコードのレコード順序番号配列及び項目値アクセス情報配列を生成し、この演算ユニットの上記専用のローカルメモリに格納する手段と、
   　上記所定の項目毎に、上記第２の担当レコードの範囲情報と上記所定の項目に属する一意の項目値の個数の組とに基づいて、この演算ユニットに割り当てられた上記第２の担当レコードのグローバル項目値順序番号配列及びローカル項目値番号配列を生成し、この演算ユニットの上記専用のローカルメモリに格納する手段と、
   　上記所定の項目毎に、上記第１の担当レコードに関するこの所定の項目のローカル項目値配列と、上記第２の担当レコードに関するこの所定の項目の上記グローバル項目値順序番号配列と、上記グローバル項目値順序番号配列中の順序番号に関連した上記第２の担当レコードを示すブロック番号を含むブロック番号配列とを、上記ローカルデータとして、この演算ユニットの後のパイプライン段にある演算ユニットへ送信する手段と、
   を含み、
   　各演算ユニットの上記マージ手段が、前のパイプライン段からの少なくとも２つのローカルデータに含まれているローカル項目値配列を所定の順序でマージすることによりさらなるローカル項目値配列を生成し、前のパイプライン段からの少なくとも２つのローカルデータに含まれているブロック番号配列及びグローバル項目値順序番号配列を所定の順序でマージすることによりさらなるブロック番号配列及びさらなるグローバル項目値順序番号配列を生成し、これにより、上記少なくとも２つのローカルデータを、上記さらなるローカル項目値配列、上記さらなるブロック番号配列及び上記さらなるグローバル項目値順序番号配列により形成された１つのローカルデータに変換する手段を含み、
   　上記分配手段が、最終的に生成されたさらなるグローバル項目値順序番号配列に格納されている順序番号によって指定された最終的に生成されたさらなるローカル項目値配列に格納されている項目値を、対応する最終的に生成されたさらなるブロック番号配列に格納されているブロック番号に関連付けられた演算ユニットへ送信する手段を含み、
   　各演算ユニットが、上記送信された項目値をこの演算ユニットの上記第２の担当レコードのローカル項目値配列に順次に格納する手段をさらに含み、
   　各演算ユニットが、上記第１の担当レコードに含まれる上記所定の項目の組に関する項目値の組を特定する次元値番号を含む次元値番号配列と、上記次元値番号に対応する上記少なくとも１つの集計項目に関する項目値の集計値を含むローカル集計値配列とを生成し、上記ローカルデータとして、この演算ユニットの後のパイプライン段にある演算ユニットへ送信する手段をさらに含み、
   　各演算ユニットの上記マージ手段が、前のパイプライン段からの少なくとも２つのローカルデータに含まれている次元値番号配列及びローカル集計値配列を所定の順序でマージすることにより、上記少なくとも２つのローカルデータをさらなる次元値番号配列及びさらなるローカル集計値配列により形成された１つのローカルデータに変換する手段を含み、
   　上記分配手段が、最終的に生成されたさらなるローカル集計値配列に格納されている集計値を上記第２の担当レコードの上記範囲情報に従って演算ユニットへ送信する手段を含み、
   　各演算ユニットが
   　上記少なくとも１つの集計項目毎に、上記送信された項目値を所定の順序でソートすることにより、集計項目に関するローカル項目値配列及びローカル項目値番号配列を生成し、この演算ユニットの上記専用のローカルメモリに格納するローカルコンパイル手段と、
   　上記少なくとも１つの集計項目毎に、上記ローカル項目値配列、上記第２の担当レコードの範囲内で所定の順序に基づいて上記ローカル項目値配列に含まれる一意の項目値に割り当てられた順序番号が格納されているローカル項目値順序番号配列、及び、上記ローカル項目値順序番号配列中の上記順序番号に関連した上記担当レコードを示す上記ブロック番号を含むブロック番号配列を、上記ローカルデータとして、この演算ユニットの後のパイプライン段にある演算ユニットへ送信する手段と、
   をさらに含み、
   　各演算ユニットの上記マージ手段が、前のパイプライン段からの少なくとも２つのローカルデータに含まれている少なくとも２つのローカル項目値配列中の項目値を上記所定の順序でマージすることにより、上記少なくとも２つのローカルデータを、さらなるブロック番号配列、さらなるローカル項目値順序番号配列及びさらなるローカル項目値配列により形成された１つのローカルデータに変換する手段をさらに含み、
   　上記分配手段が、最終的に生成されたさらなるローカル項目値順序番号配列に格納されている順序番号を、対応する最終的に生成されたさらなるブロック番号配列に格納されているブロック番号に関連付けられた演算ユニットへ送信する手段を含み、
   　各演算ユニットが、上記送信された順序番号を、この演算ユニットの上記専用のローカルメモリに設けられた、上記少なくとも１つの集計項目に関するグローバル項目値順序番号配列に順次に格納する手段をさらに含む、
   請求項３記載の分散メモリ型マルチプロセッサ。
8. 　専用のローカルメモリ及びプロセッサを含み、相互にデータを送受するため通信接続されている複数台の演算ユニットを備え、
   　一連のデータが上記複数台の演算ユニットに関連付けられた複数個のブロックに分割されて上記複数台の演算ユニットのそれぞれの専用のローカルメモリに保持され、上記一連のデータが上記複数台の演算ユニットのパイプライン処理によって操作される、分散メモリ型マルチプロセッサにおいて、
   　各演算ユニットが、前のパイプライン段にある１台以上の演算ユニットからそれぞれのローカルデータを受信し、少なくとも２つの受信されたローカルデータを１つのさらなるローカルデータに変換し、上記さらなるローカルデータを後のパイプライン段にある１台の演算ユニットへ送信し、最終的に１つのグローバルデータを生成するようにトーナメント方式で動的に動作するステップと、
   　少なくとも１台のいずれかの演算ユニットが、前記複数個のブロックに対応するブロック番号に基づいて、前記グローバルデータを分割し前記複数台の演算ユニットへ割り当てるステップと、
   を備える、表形式データ操作方法。
9. 　上記一連のデータがデータ項目に対応した項目値を含むレコードの配列として表現される表形式データであり、
   　上記複数個のブロックに分割された上記表形式データのうち各演算ユニットに割り当てられた担当レコードが、レコードの順序に依存する順序情報と各データ項目に依存する項目情報とに分離されている、
   請求項８記載の表形式データ操作方法。
10. 　上記順序情報が、上記表形式データ内での上記担当レコードの原始レコード位置番号を上記ブロック内での上記担当レコードのレコード順序番号の順番に格納するレコード順序番号配列、及び、上記担当レコードに含まれる上記項目値にアクセスする項目値アクセス情報を上記レコード順序番号の順番に格納する項目値アクセス情報配列により形成され、
    　上記項目情報が、上記担当レコードに含まれる一意の項目値が所定の順序で格納されているローカル項目値配列、上記担当レコードに含まれる上記項目値が上記ローカル項目値配列内に格納されている位置を指定するローカル項目値番号が上記担当レコードの上記原始レコード位置番号の順番に格納されているローカル項目値番号配列、及び、上記表形式データの全体で上記所定の順序に基づいて上記ローカル項目値配列中の上記一意の項目値に割り当てられた順序番号が格納されているグローバル項目値順序番号配列により形成されている、
    請求項８記載の表形式データ操作方法。
11. 　各演算ユニットが、上記分散メモリ型マルチプロセッサに接続されている外部装置からこの演算ユニットに割り当てられた上記担当レコードを受信するステップと、
    　各演算ユニットが、受信された上記担当レコードから、上記レコード順序番号配列及び上記項目値アクセス情報配列を生成し、この演算ユニットの上記専用のローカルメモリに格納するステップと、
    　各演算ユニットが、項目毎に、上記担当レコード中の項目値を上記所定の順序でソートすることにより、上記ローカル項目値配列、及び、上記ローカル項目値番号配列を生成し、この演算ユニットの上記専用のローカルメモリに格納するステップと、
    　各演算ユニットが、項目毎に、上記ローカル項目値配列、上記担当レコードの範囲内で上記所定の順序に基づいて上記ローカル項目値配列に含まれる上記一意の項目値に割り当てられた順序番号が格納されているローカル項目値順序番号配列、及び、上記ローカル項目値順序番号配列中の上記順序番号に関連した上記担当レコードを示す上記ブロック番号を含むブロック番号配列を、上記ローカルデータとして、この演算ユニットの後のパイプライン段にある演算ユニットへ送信するステップと、
    を備え、
    　上記マージするステップが、前のパイプライン段からの少なくとも２つのローカルデータに含まれている少なくとも２つのローカル項目値配列中の項目値を上記所定の順序でマージすることにより、上記少なくとも２つのローカルデータを、さらなるブロック番号配列、さらなるローカル項目値順序番号配列及びさらなるローカル項目値配列により形成された１つのローカルデータに変換するステップを含み、
    　上記分配するステップが、最終的に生成されたさらなるローカル項目値順序番号配列に格納されている順序番号を、対応する最終的に生成されたさらなるブロック番号配列に格納されているブロック番号に関連付けられた演算ユニットへ送信するステップを含み、
    　各演算ユニットが、上記送信された順序番号を上記グローバル項目値順序番号配列に順次に格納するステップをさらに備える、
    請求項１０記載の表形式データ操作方法。
12. 　各演算ユニットが、所定の項目に関して、上記担当レコードを含むブロック毎に、上記ローカル項目値番号をキーとして上記レコード順序番号配列、上記項目値アクセス情報配列及び上記グローバル項目値順序番号配列にソートを適用し、これによって、ローカルソートされたレコード順序番号配列、ローカルソートされた項目値アクセス情報配列及びローカルソートされたグローバル項目値順序番号配列を生成するステップと、
    　各演算ユニットが、上記所定の項目に関して、上記ローカルソートされたグローバル項目値順序番号配列、上記ローカルソートされたレコード順序番号配列、及び、上記ローカルソートされたレコード順序番号配列に関連した上記担当レコードを示す上記ブロック番号を含むブロック番号配列を、上記ローカルデータとして、この演算ユニットの後のパイプライン段にある演算ユニットへ送信するステップと、
    を備え
    　上記マージするステップが、前のパイプライン段からの少なくとも２つのローカルデータに含まれている上記ローカルソートされたグローバル項目値順序番号配列と上記ローカルソートされたレコード順序番号配列との組を所定の順序でマージすることにより、上記少なくとも２つのローカルデータを、さらなるグローバル項目値順序番号配列、さらなるレコード順序番号配列及びさらなるブロック番号配列により形成された１つのローカルデータに変換するステップを含み、
    　上記分配するステップが、最終的に生成されたさらなるブロック番号配列に含まれているブロック番号の上記さらなるブロック番号配列中での順序番号を、上記ブロック番号に関連付けられた演算ユニットへ送信するステップを含み、
    　各演算ユニットが、上記送信された順序番号を上記レコード順序番号配列に順次に格納するステップをさらに備える、
    請求項１０記載の表形式データ操作方法。
13. 　各演算ユニットが、所定の項目に関して、上記担当レコードを含むブロック毎に、検索条件に一致する項目値を含むレコードに対応する新たなレコード順序番号配列及び新たな項目値アクセス情報配列を生成し、上記項目値アクセス情報配列を上記新たな項目値アクセス情報配列で置き換えるステップと、
    　各演算ユニットが、上記所定の項目に関して、上記新たなレコード順序番号配列、及び、上記新たなレコード順序番号配列に関連した上記担当レコードを示す上記ブロック番号を含むブロック番号配列を、上記ローカルデータとして、この演算ユニットの後のパイプライン段にある演算ユニットへ送信するステップと、
    を備え、
    　上記マージするステップが、前のパイプライン段からの少なくとも２つのローカルデータに含まれている上記新たなレコード順序番号配列と上記ブロック番号配列との組を所定の順序でマージすることにより、上記少なくとも２つのローカルデータを、さらなるレコード順序番号配列及びさらなるブロック番号配列により形成された１つのローカルデータに変換するステップを含み、
    　上記分配するステップが、最終的に生成された上記さらなるブロック番号配列に含まれているブロック番号の上記さらなるブロック番号配列中での順序番号を、上記ブロック番号に関連付けられた演算ユニットへ送信するステップを含み、
    　各演算ユニットが、上記送信された順序番号を上記新たなレコード順序番号配列に順次に格納するステップをさらに備える、
    請求項１０記載の表形式データ操作方法。
14. 　前記複数台の演算ユニットが、集計元の表形式データとして使用される第１の表形式データに関する第１の担当レコード、及び、上記第１の表形式データの所定の項目の組に関する項目値の組毎に少なくとも１つの別の集計項目に関する項目値を集計することにより得られる集計結果を表現する第２の表形式データに関する第２の担当レコードをそれぞれの専用のローカルメモリに格納するように構成され、
    　各演算ユニットが、上記分散メモリ型マルチプロセッサに接続されている外部装置から、上記第２の表形式データのうちこの演算ユニットに分割される上記第２の担当レコードの範囲情報、及び、上記所定の項目の組に属する一意の項目値の個数の組を受信するステップと、
    　各演算ユニットが、上記第２の担当レコードの範囲情報に基づいて、この演算ユニットに割り当てられた上記第２の担当レコードのレコード順序番号配列及び項目値アクセス情報配列を生成し、この演算ユニットの上記専用のローカルメモリに格納するステップと、
    　各演算ユニットが、上記所定の項目毎に、上記第２の担当レコードの範囲情報と上記所定の項目に属する一意の項目値の個数の組とに基づいて、この演算ユニットに割り当てられた上記第２の担当レコードのグローバル項目値順序番号配列及びローカル項目値番号配列を生成し、この演算ユニットの上記専用のローカルメモリに格納するステップと、
    　各演算ユニットが、上記所定の項目毎に、上記第１の担当レコードに関するこの所定の項目のローカル項目値配列と、上記第２の担当レコードに関するこの所定の項目の上記グローバル項目値順序番号配列と、上記グローバル項目値順序番号配列中の順序番号に関連した上記第２の担当レコードを示すブロック番号を含むブロック番号配列とを、上記ローカルデータとして、この演算ユニットの後のパイプライン段にある演算ユニットへ送信するステップと、
    を備え、
    　上記マージするステップが、前のパイプライン段からの少なくとも２つのローカルデータに含まれているローカル項目値配列を所定の順序でマージすることによりさらなるローカル項目値配列を生成し、前のパイプライン段からの上記少なくとも２つのローカルデータに含まれているブロック番号配列及びグローバル項目値順序番号配列を所定の順序でマージすることによりさらなるブロック番号配列及びさらなるグローバル項目値順序番号配列を生成し、これにより、上記２つのローカルデータを、上記さらなるローカル項目値配列、上記さらなるブロック番号配列及び上記さらなるグローバル項目値順序番号配列により形成された１つのローカルデータに変換する手段を含み、
    　上記分配手段が、最終的に生成されたさらなるグローバル項目値順序番号配列に格納されている順序番号によって指定された最終的に生成されたさらなるローカル項目値配列に格納されている項目値を、対応する最終的に生成されたさらなるブロック番号配列に格納されているブロック番号に関連付けられた演算ユニットへ送信するステップを含み、
    　各演算ユニットが、上記送信された項目値をこの演算ユニットの上記第２の担当レコードのローカル項目値配列に順次に格納するステップと、
    　各演算ユニットが、上記第１の担当レコードに含まれる上記所定の項目の組に関する項目値の組を特定する次元値番号を含む次元値番号配列と、上記次元値番号に対応する上記少なくとも１つの集計項目に関する項目値の集計値を含むローカル集計値配列とを生成し、上記ローカルデータとして、この演算ユニットの後のパイプライン段にある演算ユニットへ送信するステップと、
    をさらに備え、
    　上記マージするステップが、前のパイプライン段からの少なくとも２つのローカルデータに含まれている次元値番号配列及びローカル集計値配列を所定の順序でマージすることにより、上記少なくとも２つのローカルデータをさらなる次元値番号配列及びさらなるローカル集計値配列により形成された１つのローカルデータに変換する手段を含み、
    　上記分配手段が、最終的に生成されたさらなるローカル集計値配列に格納されている集計値を上記第２の担当レコードの上記範囲情報に従って演算ユニットへ送信するステップを含み、
    　各演算ユニットが、上記少なくとも１つの集計項目毎に、上記送信された項目値を所定の順序でソートすることにより、集計項目に関するローカル項目値配列及びローカル項目値番号配列を生成し、この演算ユニットの上記専用のローカルメモリに格納するステップと、
    　各演算ユニットが、上記少なくとも１つの集計項目毎に、上記ローカル項目値配列、上記第２の担当レコードの範囲内で所定の順序に基づいて上記ローカル項目値配列に含まれる一意の項目値に割り当てられた順序番号が格納されているローカル項目値順序番号配列、及び、上記ローカル項目値順序番号配列中の上記順序番号に関連した上記担当レコードを示す上記ブロック番号を含むブロック番号配列を、上記ローカルデータとして、この演算ユニットの後のパイプライン段にある演算ユニットへ送信するステップと、
    をさらに備え、
    　上記マージするステップが、前のパイプライン段からの少なくとも２つのローカルデータに含まれている少なくとも２つのローカル項目値配列中の項目値を上記所定の順序でマージすることにより、上記２つのローカルデータを、さらなるブロック番号配列、さらなるローカル項目値順序番号配列及びさらなるローカル項目値配列により形成された１つのローカルデータに変換するステップをさらに含み、
    　上記分配するステップが、最終的に生成されたさらなるローカル項目値順序番号配列に格納されている順序番号を、対応する最終的に生成されたさらなるブロック番号配列に格納されているブロック番号に関連付けられた演算ユニットへ送信するステップを含み、
    　各演算ユニットが、上記送信された順序番号を、この演算ユニットの上記専用のローカルメモリに設けられた、上記少なくとも１つの集計項目に関するグローバル項目値順序番号配列に順次に格納するステップをさらに備える、
    請求項１０記載の表形式データ操作方法。
15. 　専用のローカルメモリ及びプロセッサを含み、相互にデータを送受するため通信接続されている複数台の演算ユニットを備えるコンピュータにロードされ、
    　一連のデータが上記複数台の演算ユニットに関連付けられた複数個のブロックに分割されて上記複数台の演算ユニットのそれぞれの専用のローカルメモリに保持され、上記一連のデータを上記複数台の演算ユニットのパイプライン処理によって操作するコードを上記コンピュータに実行させるコンピュータ読み取り可能なプログラムであって、
    　各演算ユニットが、前のパイプライン段にある１台以上の演算ユニットからそれぞれのローカルデータを受信し、少なくとも２つの受信されたローカルデータを１つのさらなるローカルデータに変換し、上記さらなるローカルデータを後のパイプライン段にある１台の演算ユニットへ送信するコードと、
    　前記複数台の演算ユニットのマージ手段が最終的に１つのグローバルデータを生成するようにトーナメント方式で動的に動作するコードと、
    　少なくとも１台のいずれかの演算ユニットが、前記複数個のブロックに対応するブロック番号に基づいて、前記グローバルデータを分割し前記複数台の演算ユニットへ割り当てるコードと、
    を備えるプログラム。
16. 　専用のローカルメモリ及びプロセッサを含み、相互にデータを送受するため通信接続されている複数台の演算ユニットを備えるコンピュータにロードされ、
    　一連のデータが上記複数台の演算ユニットに関連付けられた複数個のブロックに分割されて上記複数台の演算ユニットのそれぞれの専用のローカルメモリに保持され、上記一連のデータを上記複数台の演算ユニットのパイプライン処理によって操作する請求項８乃至１４のうちいずれか１項記載の表形式データ操作方法を上記コンピュータに実行させるためのコンピュータプログラムプロダクト。
17. 　専用のローカルメモリ及びプロセッサを含み、相互にデータを送受するため通信接続されている複数台の演算ユニットを備えるコンピュータにロードされ、
    　一連のデータが上記複数台の演算ユニットに関連付けられた複数個のブロックに分割されて上記複数台の演算ユニットのそれぞれの専用のローカルメモリに保持され、上記一連のデータを上記複数台の演算ユニットのパイプライン処理によって操作する請求項８乃至１４のうちいずれか１項記載の表形式データ操作方法を上記コンピュータに実行させるためのコンピュータプログラムが記録された記憶媒体。

Images