(57)【要約】  マルチコア型処理装置において、表形式データのレコードを所定の項目値に応じて並べ替えるソート方法は、複数台の演算ユニットが並列的に動作して、(i)各演算ユニットが担当するブロック内で、項目値情報をキーとして用いて、項目値アクセス情報にソートを適用し、(ii)ブロック間で、項目値情報とレコード順序番号の組を所定の順序でソートし、(iii)ブロック間のソート(ii)を繰り返すことにより、ソートされたブロック番号配列を作成し、(iv)ブロック番号配列中の要素をブロック毎に分配することにより、ソートされたレコード順序番号配列を作成する。
2009044486.tif 000002
【特許請求の範囲】
【請求項１】
専用のローカルメモリを含む複数台の演算ユニットと、上記複数台の演算ユニットに接続されているグローバルメモリとを備えるマルチコア型処理装置において、１つ以上のデータ項目に対応した項目値を含むレコードの配列を表現し、上記グローバルメモリに構築されている表形式データの上記レコードを所定のデータ項目に関する項目値に応じて並べ替えるソート方法であって、
上記表形式データが、
各演算ユニットの上記ローカルメモリに収容可能なサイズをもつブロックに分割されている上記レコードの配列中の各レコードに対応するブロック番号が上記表形式データ中の上記レコードのレコード順序番号の順番に格納されているブロック番号配列と、
各ブロックに属するレコードである担当レコードの上記レコード順序番号が上記レコード順序番号の順番に格納されているレコード順序番号配列と、
上記担当レコードに含まれる上記項目値にアクセスするための項目値アクセス情報が上記レコード順序番号の順番に格納されている項目値アクセス情報配列と、
データ項目毎に上記項目値アクセス情報を用いてアクセスされる上記項目値を記述する項目値情報と、
によって表現され、
当該ソート方法が、上記所定のデータ項目に関して、
(i)上記複数台の演算ユニットが並列的に動作して、上記担当レコードを含むブロック毎に、上記項目値情報をキーとして用いて上記項目値アクセス情報配列にソートを適用し、これによって、ソートされた項目値アクセス情報配列と、上記ソートされた項目値アクセス情報配列に対応する作業用項目値情報配列及び作業用レコード順序番号配列を上記グローバルメモリに作成するステップと、
(ii)上記複数台の演算ユニットが並列的に動作して、１対のブロックに関する上記作業用項目値情報配列からの第１の要素及び対応する上記作業用レコード順序番号配列からの第２の要素からなる要素の組を、上記第１の要素を上位の桁及び上記第２の要素を下位の桁として用いて、所定の順序にマージし、マージされた要素の組に当該要素の組が含まれる上記ブロック番号を関連付け、これによって、上記１対のブロックに関する新たな作業用項目値情報配列、新たな作業用レコード順序番号配列、及び、新たなブロック番号配列を作成するステップと、
(iii)上記複数台の演算ユニットが並列的かつ階層的に動作して、上記ステップ(ii)を繰り返し実行し、これによって、最終的なブロック番号配列を上記グローバルメモリに作成するステップと、
(iv)上記複数台の演算ユニットが並列的に動作して、上記最終的なブロック番号配列中の要素が格納されているレコード順序番号を当該要素によって指定されたブロック番号毎に分配し所定の順番に並べ、これによって、ソートされたレコード順序番号配列を上記グローバルメモリに作成するステップと、
を備えるソート方法。
【請求項２】
上記ステップ(i)が、
上記複数台の演算ユニットが並列的に動作して、上記担当レコードを含むブロックに対応している、上記レコード順序番号配列及び上記項目値アクセス情報配列と、上記所定の項目に関する上記項目値情報配列とを、上記グローバルメモリから上記ローカルメモリへ転送するステップと、
上記複数台の演算ユニットが並列的に動作して、上記ローカルメモリに作成された上記ソートされた項目値アクセス情報配列と、上記作業用項目値情報配列及び上記作業用レコード順序番号配列とを上記グローバルメモリへ転送するステップと、
をさらに含み、
上記ステップ(ii)が、
上記複数台の演算ユニットが並列的に動作して、１対のブロックに関する上記作業用項目値情報配列及び上記作業用レコード順序番号配列を、上記グローバルメモリから上記ローカルメモリへ転送するステップと、
上記複数台の演算ユニットが並列的に動作して、上記ローカルメモリに作成された上記新たな作業用項目値情報配列、上記新たな作業用レコード順序番号配列、及び、上記新たなブロック番号配列を上記グローバルメモリ又はさらなる処理のための演算ユニットへ転送するステップと、
をさらに含む、
請求項１に記載のソート方法。
【請求項３】
上記項目値情報が、
データ項目毎に、一意の項目値が所定の順序に格納されているグローバル項目値配列と、
データ項目毎に、上記担当レコードに含まれる項目値を特定するローカル項目値番号が上記レコード順序番号の順番に格納されているローカル項目値番号配列と、
データ項目毎に、上記ローカル項目値番号によって表される項目値が上記グローバル項目値配列中に格納されている位置を指定する項目値指定ポインタが所定の順番に格納されている項目値指定ポインタ配列と、
を備え、
上記ステップ(i)において適用されるソートが分布数え上げソートであり、
上記作業用項目値情報配列が作業用項目値指定ポインタ配列である、
請求項１又は２に記載のソート方法。
【請求項４】
上記項目値情報がデータ項目毎に上記担当レコードに含まれる項目値が格納されている項目値配列を備え、
上記ステップ(i)において適用されるソートが安定性のあるソートであり、
上記作業用項目値情報配列が作業用項目値配列である、
請求項１又は２に記載のソート方法。
【請求項５】
(v)上記ソートされたレコード順序番号配列及び上記ソートされた項目値アクセス情報配列をそれぞれ上記レコード順序番号配列及び上記項目値アクセス情報配列として用いて、別のデータ項目に関して、上記ステップ(i)、(ii)、(iii)及び(iv)を実行するステップをさらに備える、請求項１乃至４のうち何れか１項に記載のソート方法。
【請求項６】
専用のローカルメモリを含む複数台の演算ユニットと、上記複数台の演算ユニットに接続されているグローバルメモリとを備え、１つ以上のデータ項目に対応した項目値を含むレコードの配列を表現し、上記グローバルメモリに構築されている表形式データの上記レコードを所定のデータ項目に関する項目値に応じて並べ替える、マルチコア型処理装置であって、
上記表形式データが、
各演算ユニットの上記ローカルメモリに収容可能なサイズをもつブロックに分割されている上記レコードの配列中の各レコードに対応するブロック番号が上記表形式データ中の上記レコードのレコード順序番号の順番に格納されているブロック番号配列と、
各ブロックに属するレコードである担当レコードの上記レコード順序番号が上記レコード順序番号の順番に格納されているレコード順序番号配列と、
上記担当レコードに含まれる上記項目値にアクセスするための項目値アクセス情報が上記レコード順序番号の順番に格納されている項目値アクセス情報配列と、
データ項目毎に上記項目値アクセス情報を用いてアクセスされる上記項目値を記述する項目値情報と、
によって表現され、
マルチコア型処理装置の各演算ユニットが、
(a)他の演算ユニットと並列的に動作して、上記担当レコードを含むブロック毎に、上記所定のデータ項目に関する上記項目値情報をキーとして用いて、上記項目値アクセス情報配列にソートを適用し、これによって、ソートされた項目値アクセス情報配列と、上記ソートされた項目値アクセス情報配列に対応する作業用項目値情報配列及び作業用レコード順序番号配列を上記グローバルメモリに作成する手段と、
(b)他の演算ユニットと並列的に動作して、１対のブロックに関する上記作業用項目値情報配列からの第１の要素及び対応する上記作業用レコード順序番号配列からの第２の要素からなる要素の組を、上記第１の要素を上位の桁及び上記第２の要素を下位の桁として用いて、所定の順序にマージし、マージされた要素の組に当該要素の組が含まれる上記ブロック番号を関連付け、これによって、上記１対のブロックに関する新たな作業用項目値情報配列、新たな作業用レコード順序番号配列、及び、新たなブロック番号配列を作成する手段と、
(c)他の演算ユニットと並列的かつ階層的に動作して、上記手段（ｂ）を繰り返し作動させ、これによって、最終的なブロック番号配列を上記グローバルメモリに作成する手段と、
(d)他の演算ユニットと並列的に動作して、上記最終的なブロック番号配列中の要素が格納されているレコード順序番号を当該要素によって指定されたブロック番号毎に分配し所定の順番に並べ、これによって、ソートされたレコード順序番号配列を上記グローバルメモリに作成する手段と、
を備える、マルチコア型処理装置。
【請求項７】
各演算ユニットが上記専用のローカルメモリと上記グローバルメモリとの間のデータ転送のための専用のメモリインターフェイスをさらに備え、
上記手段(a)が、上記専用のメモリインターフェイスを介して、上記担当レコードを含むブロックに対応している、上記レコード順序番号配列及び上記項目値アクセス情報配列と、上記所定の項目に関する上記項目値情報配列とを、上記グローバルメモリから上記ローカルメモリへ転送し、上記ローカルメモリに作成された上記ソートされた項目値アクセス情報配列と、上記作業用項目値情報配列及び上記作業用レコード順序番号配列とを上記グローバルメモリへ転送し、
上記手段(b)が、上記専用のメモリインターフェイスを介して、１対のブロックに関する上記作業用項目値情報配列及び上記作業用レコード順序番号配列を、上記グローバルメモリから上記ローカルメモリへ転送し、上記ローカルメモリに作成された上記新たな作業用項目値情報配列、上記新たな作業用レコード順序番号配列、及び、上記新たなブロック番号配列を上記グローバルメモリ又はさらなる処理のための演算ユニットへ転送し、
上記手段(c)が、上記専用のメモリインターフェイスを介して、上記ローカルメモリに作成された上記最終的なブロック番号配列を上記グローバルメモリへ転送する、
請求項６に記載のマルチコア型処理装置。
【請求項８】
専用のローカルメモリを含む複数台の演算ユニットと、上記複数台の演算ユニットに接続されているグローバルメモリとを備えるコンピュータにロードされ、１つ以上のデータ項目に対応した項目値を含むレコードの配列を表現し、上記グローバルメモリに構築されている表形式データの上記レコードを所定のデータ項目に関する項目値に応じて並べ替えるコードを上記コンピュータに実行させるコンピュータ読み取り可能なプログラムであって、
上記コンピュータにおいて、上記表形式データが、
各演算ユニットの上記ローカルメモリに収容可能なサイズをもつブロックに分割されている上記レコードの配列中の各レコードに対応するブロック番号が上記表形式データ中の上記レコードのレコード順序番号の順番に格納されているブロック番号配列と、
各ブロックに属するレコードである担当レコードの上記レコード順序番号が上記レコード順序番号の順番に格納されているレコード順序番号配列と、
上記担当レコードに含まれる上記項目値にアクセスするための項目値アクセス情報が上記レコード順序番号の順番に格納されている項目値アクセス情報配列と、
データ項目毎に上記項目値アクセス情報を用いてアクセスされる上記項目値を記述する項目値情報と、
によって表現され、
上記プログラムが、
(a)各演算ユニットが他の演算ユニットと並列的に動作して、上記担当レコードを含むブロック毎に、上記所定のデータ項目に関する上記項目値情報をキーとして用いて、上記項目値アクセス情報配列にソートを適用し、これによって、ソートされた項目値アクセス情報配列と、上記ソートされた項目値アクセス情報配列に対応する作業用項目値情報配列及び作業用レコード順序番号配列を上記グローバルメモリに作成するコードと、
(b)各演算ユニットが他の演算ユニットと並列的に動作して、１対のブロックに関する上記作業用項目値情報配列からの第１の要素及び対応する上記作業用レコード順序番号配列からの第２の要素からなる要素の組を、上記第１の要素を上位の桁及び上記第２の要素を下位の桁として用いて、所定の順序にマージし、マージされた要素の組に当該要素の組が含まれる上記ブロック番号を関連付け、これによって、上記１対のブロックに関する新たな作業用項目値情報配列、新たな作業用レコード順序番号配列、及び、新たなブロック番号配列を作成するコードと、
(c)各演算ユニットが他の演算ユニットと並列的かつ階層的に動作して、上記コード（ｂ）を繰り返し実行し、これによって、最終的なブロック番号配列を上記グローバルメモリに作成するコードと、
(d)各演算ユニットが他の演算ユニットと並列的に動作して、上記最終的なブロック番号配列中の要素が格納されているレコード順序番号を当該要素によって指定されたブロック番号毎に分配し所定の順番に並べ、これによって、ソートされたレコード順序番号配列を上記グローバルメモリに作成するコードと、
を含む、プログラム。
【請求項９】
専用のローカルメモリを含む複数台の演算ユニットと、上記複数台の演算ユニットに接続されているグローバルメモリとを備えるコンピュータにロードされ、１つ以上のデータ項目に対応した項目値を含むレコードの配列を表現し、上記グローバルメモリに構築されている表形式データの上記レコードを所定のデータ項目に関する項目値に応じて並べ替える請求項１乃至６のうち何れか１項に記載のソート方法を上記コンピュータに実行させるためのコンピュータプログラムプロダクト。
【請求項１０】
専用のローカルメモリを含む複数台の演算ユニットと、上記複数台の演算ユニットに接続されているグローバルメモリとを備えるコンピュータにロードされ、１つ以上のデータ項目に対応した項目値を含むレコードの配列を表現し、上記グローバルメモリに構築されている表形式データの上記レコードを所定のデータ項目に関する項目値に応じて並べ替える請求項１乃至６のうち何れか１項に記載のソート方法を上記コンピュータに実行させるためのコンピュータプログラムが記録された記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、マルチコア型処理装置において、データ項目に対応した項目値を含むレコードの配列として表され、グローバルメモリに構築された表形式データのレコードを所定の項目値に応じて並べ替えるソート方法に関係する。【０００２】
本発明は、データ項目に対応した項目値を含むレコードの配列として表され、グローバルメモリに構築された表形式データのレコードを所定の項目値に応じて並べ替えるマルチコア型処理装置にも関係する。【０００３】
さらに、本発明は、上記ソート方法を、マルチコア型プロセッサを備えるコンピュータに実行させるためのプログラム、コンピュータプログラムプロダクト、及び、コンピュータプログラムが記録された記録媒体に関係する。
【背景技術】
【０００４】
従来、産業上の様々な分野において、大規模データを高速に処理することが求められている。大規模データの処理は、キャッシュやプリフェッチなどによるメモリアクセスの高速化、メモリ自体の高速化、及び、プロセッサの並列化のような演算処理の高速化、といったハードウェア技術の開発、ならびに、データ処理アルゴリズムの開発によって、高速化され続けている。【０００５】
本発明者は、大規模データを高速に処理するための基本的なデータ処理アルゴリズム、たとえば、特許文献１に記載されているような、「オンメモリデータ処理アルゴリズム」を提案している。この技術は、表形式データを、従来のようなレコード（すなわち、行）単位ではなく、項目（すなわち、列）単位に成分分解するという考え方に基づいている。より具体的には、表形式データが、（１）レコード順を表す配列と、（２）項目に属する一意の項目値が所定の順序（たとえば、昇順）に並べられた値テーブルと、（３）各レコードに対応する項目値が値テーブルに格納されている位置情報を表す配列とからなるデータ構造によって表現されている。このようなデータ構造を採用することにより、表形式データの検索、ソート、マージ、ジョイン等の処理が高速に実現されている。【０００６】
さらに、本発明者は、メモリ分散型のマルチプロセッサシステム及びメモリ共有型のマルチプロセッサシステムのようなプロセッサの並列化に対応した種々のオンメモリデータ処理アルゴリズムを提案している。たとえば、メモリ分散型のマルチプロセッサシステムに対応した検索・ソートアルゴリズムが特許文献２に記載され、集計アルゴリズムが特許文献３に記載されている。さらに、メモリ共有型のマルチプロセッサシステムに対応した効率的なソートアルゴリズムが特許文献４に記載されている。【０００７】
大規模データ、特に、大規模な表形式データを処理する際に頻出する処理はソートであり、効率的なソートアルゴリズムとして、基数（ＲＡＤＩＸ）ソートとカウンティングソート（計数ソート、分布数え上げソートとも称される）が知られている。基数ソートは、ソートの対象となるデータの各桁をキーとして、桁毎にソートを行う。カウンティングソートは、ソートの対象となるデータの出現回数と累積度数分布とを計算し、累積度数分布に応じてソートの対象となるデータを並べ替える。カウンティングソートは基数ソートの各桁のソートに利用されることもある。特許文献４には、共有メモリ型プロセッサシステムにおいて、共有メモリ上の大規模な表形式データを複数台のプロセッサで並列にソートする方法が提案されている。【０００８】
これに対して、近年、１台のプロセッサの内部に複数（又は多数）のコアを含むプロセッサアーキテクチャが提案されている。マルチコア型プロセッサの一例として、Ｃｅｌｌ  Ｂｒｏａｄｂａｎｄ  ＥｎｇｉｎｅＴＭが知られている（非特許文献１を参照のこと）。このタイプのプロセッサは、たとえば、マルチメディアデータの高速処理や、分散コンピューティングなどに適用することが意図されている。このアーキテクチャでは、各コアは、大容量ではないが、専用のローカルメモリを有し、他のコアとは独立して演算を行うことができる。実際には、ローカルメモリのメモリ容量はマルチメディアデータ等の処理に不足しているので、外付けのグローバルメモリが設けられている。マルチコア型プロセッサアーキテクチャは、クロックの高速化に頼るのではなく、コアの追加によって並列性が高まり、処理能力が上昇するので、拡張性に優れている。【０００９】
よって、このようなマルチコア型プロセッサアーキテクチャは、マルチメディアデータ処理だけでなく、高速性が要求される種々のアプリケーション、特に、大規模な表形式データのソート処理に適用されることが望まれている。
【非特許文献１】"Cell Broadband EngineArchitecture", Version 1.01, October 3, 2006、［平成１９年７月２６日検索］、インターネット(URL:http://cell.scei.co.jp/pdf/CBE_Architecture_v101.pdf)
【特許文献１】国際公開第００／１０１０３号公報
【特許文献２】国際公開第２００５／０４１０６６号公報
【特許文献３】国際公開第２００５／０４１０６７号公報
【特許文献４】国際公開第２００６／１２６４６７号公報
【発明の開示】
【発明が解決しようとする課題】
【００１０】
本発明者は、大規模な表形式データを高速にソート処理するため、上記の拡張性に優れたマルチコア型プロセッサアーキテクチャを利用する技術の重要性を認識した。【００１１】
しかし、データベースのように大規模なメモリを用いるアプリケーションでは、ソート処理されるべきデータの全部はコアに付随するローカルメモリに収容できないので、ソート処理アルゴリズムの複雑性が増す。たとえば、各コアに付随するローカルメモリに収容できない程に大きなデータをランダムアクセスすると、外付けのグローバルメモリへのアクセスが頻発し、処理性能が著しく低下する。よって、このような問題を起こさない新たなソート処理アルゴリズムが必要とされる。【００１２】
したがって、マルチコア型プロセッサを備えるコンピュータにおいて、１つ以上のデータ項目に対応した項目値を含むレコードの配列を表現する表形式データのレコードを、並列処理性能を低下させることなく、容量の小さい作業用メモリを用いて、所定のデータ項目に関する項目値に応じて並べ替えるソート方法を提供できることが好ましい。【００１３】
また、１つ以上のデータ項目に対応した項目値を含むレコードの配列を表現する表形式データのレコードを、並列処理性能を低下させることなく、容量の小さい作業用メモリを用いて、所定のデータ項目に関する項目値に応じて並べ替えるマルチコア型情報処理装置を提供できることが好ましい。【００１４】
さらに、マルチコア型プロセッサを備えるコンピュータにおいて、１つ以上のデータ項目に対応した項目値を含むレコードの配列を表現する表形式データのレコードを、並列処理性能を低下させることなく、容量の小さい作業用メモリを用いて、所定のデータ項目に関する項目値に応じて並べ替えるプログラム、コンピュータプログラムプロダクト、及び、コンピュータプログラムが記録された記録媒体を提供できることが好ましい。
【課題を解決するための手段】
【００１５】
本発明の一実施形態によれば、専用のローカルメモリを含む複数台の演算ユニットと、上記複数台の演算ユニットに接続されているグローバルメモリとを備えるマルチコア型処理装置において、１つ以上のデータ項目に対応した項目値を含むレコードの配列を表現し、上記グローバルメモリに構築されている表形式データの上記レコードを所定のデータ項目に関する項目値に応じて並べ替えるソート方法であって、
上記表形式データが、
各演算ユニットの上記ローカルメモリに収容可能なサイズをもつブロックに分割されている上記レコードの配列中の各レコードに対応するブロック番号が上記表形式データ中の上記レコードのレコード順序番号の順番に格納されているブロック番号配列と、
各ブロックに属するレコードである担当レコードの上記レコード順序番号が上記レコード順序番号の順番に格納されているレコード順序番号配列と、
上記担当レコードに含まれる上記項目値にアクセスするための項目値アクセス情報が上記レコード順序番号の順番に格納されている項目値アクセス情報配列と、
データ項目毎に上記項目値アクセス情報を用いてアクセスされる上記項目値を記述する項目値情報と、
によって表現され、
当該ソート方法が、上記所定のデータ項目に関して、
(i)上記複数台の演算ユニットが並列的に動作して、上記担当レコードを含むブロック毎に、上記項目値情報をキーとして用いて、上記項目値アクセス情報配列にソートを適用し、これによって、ソートされた項目値アクセス情報配列と、上記ソートされた項目値アクセス情報配列に対応する作業用項目値情報配列及び作業用レコード順序番号配列を上記グローバルメモリに作成するステップと、
(ii)上記複数台の演算ユニットが並列的に動作して、１対のブロックに関する上記作業用項目値情報配列からの第１の要素及び対応する上記作業用レコード順序番号配列からの第２の要素からなる要素の組を、上記第１の要素を上位の桁及び上記第２の要素を下位の桁として用いて、所定の順序にマージし、マージされた要素の組に当該要素の組が含まれる上記ブロック番号を関連付け、これによって、上記１対のブロックに関する新たな作業用項目値情報配列、新たな作業用レコード順序番号配列、及び、新たなブロック番号配列を作成するステップと、
(iii)上記複数台の演算ユニットが並列的かつ階層的に動作して、上記ステップ(ii)を繰り返し実行し、これによって、最終的なブロック番号配列を上記グローバルメモリに作成するステップと、
(iv)上記複数台の演算ユニットが並列的に動作して、上記最終的なブロック番号配列中の要素が格納されているレコード順序番号を当該要素によって指定されたブロック番号毎に分配し所定の順番に並べ、これによって、ソートされたレコード順序番号配列を上記グローバルメモリに作成するステップと、
を備えるソート方法が提供される。【００１６】
マルチコア型プロセッサを備えるコンピュータのグローバルメモリ上に構築された表形式データは、並列処理性能を低下させることなく、容量の小さい作業用メモリを用いてレコードの並べ替えが可能であるように、２タイプのデータ形式によって記述されている。第１のタイプのデータは、ローカルメモリに収容できることが保証される程に小さく分割され、グローバルメモリ（又は、ディスク）に保持される配列群である。この第１のタイプのデータは、グローバルメモリからローカルメモリへ一括転送され得るので、ランダムアクセスを行っても遅延を生じない。第２のタイプのデータは、大量のデータをアクセスする際に、必ず所定の順序（たとえば、昇順又は降順）に連続的にアクセスされることが保証され、グローバルメモリ（又は、ディスク）に保持される配列群である。第２のタイプのデータは、そのままではローカルメモリに収容できないので、ローカルメモリに収容可能なサイズの単位で、グローバルメモリからローカルメモリへ順次アクセスによって転送される。もちろん、第１のタイプのデータは、順次アクセスによらずに、部分的にグローバルメモリ上に格納されている要素が直接アクセスされることもある。【００１７】
本文書中で、表形式データとは、データ項目に対応した項目値を含むレコードの配列として表されるデータを意味する。【００１８】
また、本文書中で、マルチコア型処理装置又はプロセッサとは、専用のローカルメモリを含む複数台の演算ユニットと、上記複数台の演算ユニットに接続されているグローバルメモリと、上記複数台の演算ユニットを接続するバスと、上記グローバルメモリ及び上記複数台の演算ユニットに接続されている少なくとも１台の制御ユニットと、を備える装置を意味する。【００１９】
さらに、本文書中、「配列にソート（処理）を適用」するとは、「配列の要素をソート」することを意味している。【００２０】
本実施形態によれば、上記の成分分解の考え方と、上記の２タイプのデータ形式の考え方とを組み合わせて、マルチコア型処理装置のグローバルメモリ上に構築された表形式データの（複数又は多数の）レコードは、ブロック番号によって識別されるブロックに分割されている。このブロックは、このブロックに含まれるレコードの処理を担当する演算ユニットに対応している。各演算ユニットが担当するレコードは、本書中で、担当レコードと呼ばれる。そして、このブロック番号がレコード順序番号の順番に格納されているブロック番号配列がグローバルメモリ上に作成されている。ブロック番号配列は第２のタイプのデータをもつ。レコード順序番号とは、表形式データの中で各レコードが収容されている位置、たとえば、行番号に対応する。本実施形態によるソート処理は、表形式データのレコードを並び替えるので、各レコードに付与されているレコード順序番号は、ソート処理によって変化させられる。【００２１】
各演算ユニットは、担当レコードを認識するために、担当レコードのレコード順序番号がレコード順序番号の順番に格納されているレコード順序番号配列にアクセスすることができる。このレコード順序番号配列は、第１のタイプのデータをもち、必要に応じて、グローバルメモリから各演算ユニット内のローカルメモリへ転送される。【００２２】
さらに、各演算ユニットは、担当レコードに含まれる項目値にアクセスするため、項目値アクセス情報がレコード順序番号の順番に格納されている項目値アクセス情報配列にアクセスすることができる。この項目値アクセス情報配列は、第１のタイプのデータをもち、必要に応じて、グローバルメモリから各演算ユニット内のローカルメモリへ転送される。【００２３】
各演算ユニットの担当レコードに含まれる項目値は、データ項目毎に各演算ユニットが項目値アクセス情報配列を用いてアクセスすることができるように項目値情報としてグローバルメモリに保持され、必要に応じて、グローバルメモリから各演算ユニット内のローカルメモリへ転送される。【００２４】
本発明の一実施形態によれば、
上記ステップ(i)が、
上記複数台の演算ユニットが並列的に動作して、上記担当レコードを含むブロックに対応している、上記レコード順序番号配列及び上記項目値アクセス情報配列と、上記所定の項目に関する上記項目値情報配列とを、上記グローバルメモリから上記ローカルメモリへ転送するステップと、
上記複数台の演算ユニットが並列的に動作して、上記ローカルメモリに作成された上記ソートされた項目値アクセス情報配列と、上記作業用項目値情報配列及び上記作業用レコード順序番号配列とを上記グローバルメモリへ転送するステップと、
をさらに含み、
上記ステップ(ii)が、
上記複数台の演算ユニットが並列的に動作して、１対のブロックに関する上記作業用項目値情報配列及び上記作業用レコード順序番号配列を、上記グローバルメモリから上記ローカルメモリへ転送するステップと、
上記複数台の演算ユニットが並列的に動作して、上記ローカルメモリに作成された上記新たな作業用項目値情報配列、上記新たな作業用レコード順序番号配列、及び、上記新たなブロック番号配列を上記グローバルメモリ又はさらなる処理のための演算ユニットへ転送するステップと、
をさらに含む。【００２５】
本発明の一実施形態によれば、上記項目値情報は、
データ項目毎に、一意の項目値が所定の順序に格納されているグローバル項目値配列と、
データ項目毎に、上記担当レコードに含まれる項目値を特定するローカル項目値番号が上記レコード順序番号の順番に格納されているローカル項目値番号配列と、
データ項目毎に、上記ローカル項目値番号によって表される項目値が上記グローバル項目値配列中に格納されている位置を指定する項目値指定ポインタが所定の順番に格納されている項目値指定ポインタ配列と、
を備え、
上記ステップ(i)において適用されるソートは分布数え上げソートであり、上記作業用項目値情報配列は作業用項目値指定ポインタ配列である。【００２６】
本実施形態によれば、表形式データの項目値情報は、データ項目毎に、一意の項目値が所定の順序（昇順又は降順）に格納されているグローバル項目値配列としてグローバルメモリ上に構築されている。このグローバル項目値配列は第２のタイプのデータをもつ。また、各演算ユニットが項目値アクセス情報配列を用いて担当レコードに含まれる項目値にアクセスするため、データ項目毎に、担当レコードに含まれる項目値を特定するローカル項目値番号が、たとえば、原始レコード位置番号（すなわち、初期的なレコード順序番号）の順番に格納されているローカル項目値番号配列と、ローカル項目値番号によって表される項目値がグローバル項目値配列中に格納されている位置を指定する項目値指定ポインタが所定の順序（昇順又は降順）に格納されている項目値指定ポインタ配列とがグローバルメモリ上に構築され、必要に応じて、グローバルメモリから各演算ユニット内のローカルメモリへ転送される。ローカル項目値番号配列及び項目値指定ポインタ配列は第１のタイプのデータをもつ。このように、表形式データの項目値は、データ項目毎に、グローバル項目値配列、ローカル項目値番号配列、及び、項目値指定ポインタ配列の形に展開されている。【００２７】
上記ステップ(i)は、
上記複数台の演算ユニットが並列的に動作して、上記担当レコードを含むブロックに対応している、上記レコード順序番号配列及び上記項目値アクセス情報配列と、上記所定の項目に関する上記ローカル項目値番号配列及び上記項目値指定ポインタ配列とを、上記グローバルメモリから上記ローカルメモリへ転送するステップと、
上記複数台の演算ユニットが並列的に動作して、上記ローカルメモリに作成された上記ソートされた項目値アクセス情報配列と、上記作業用項目値指定ポインタ配列及び上記作業用レコード順序番号配列とを上記グローバルメモリへ転送するステップと、
をさらに含み、
上記ステップ(ii)は、
上記複数台の演算ユニットが並列的に動作して、１対のブロックに関する上記作業用項目値指定ポインタ配列及び上記作業用レコード順序番号配列を、上記グローバルメモリから上記ローカルメモリへ転送するステップと、
上記複数台の演算ユニットが並列的に動作して、上記ローカルメモリに作成された上記新たな作業用項目値指定ポインタ配列、上記新たな作業用レコード順序番号配列、及び、上記新たなブロック番号配列を上記グローバルメモリ又はさらなる処理のための演算ユニットへ転送するステップと、
をさらに含む。【００２８】
本発明の他の実施形態によれば、上記項目値情報はデータ項目毎に上記担当レコードに含まれる項目値が格納されている項目値配列を備え、
上記ステップ(i)において適用されるソートが安定性のあるソートであり、
上記作業用項目値情報配列が作業用項目値配列である。【００２９】
本実施形態では、表形式データの項目値情報は、データ項目毎に担当レコードに含まれる項目値が、たとえば、原始レコード位置番号（すなわち、初期的なレコード順序番号）の順番に格納されている項目値配列としてグローバルメモリ上に構築されている。ステップ(i)では、項目値をキーとして、項目値指定ポインタ配列に安定性のあるソート、すなわち、キー値が同値である場合に、ソートの前後で並べ替えが起こらないソートを適用する。【００３０】
また、上記ステップ(i)は、
上記複数台の演算ユニットが並列的に動作して、上記担当レコードを含むブロックに対応している、上記レコード順序番号配列及び上記項目値アクセス情報配列と、上記所定の項目に関する上記項目値とを、上記グローバルメモリから上記ローカルメモリへ転送するステップと、
上記複数台の演算ユニットが並列的に動作して、上記ローカルメモリに作成された上記ソートされた項目値アクセス情報配列と、上記作業用項目値配列及び上記作業用レコード順序番号配列を上記グローバルメモリへ転送するステップと、
をさらに含み、
上記ステップ(ii)は、
上記複数台の演算ユニットが並列的に動作して、１対のブロックに関する上記作業用項目値配列及び上記作業用レコード順序番号配列を、上記グローバルメモリから上記ローカルメモリへ転送するステップと、
上記複数台の演算ユニットが並列的に動作して、上記ローカルメモリに作成された上記新たな作業用項目値配列、上記新たな作業用レコード順序番号配列、及び、上記新たなブロック番号配列を上記グローバルメモリ又はさらなる処理のための演算ユニットへ転送するステップと、
をさらに含む。【００３１】
本発明の一実施形態によれば、２つ以上のデータ項目に関してソートを多段階的に実行するため、ソート方法は、
(v)上記ソートされたレコード順序番号配列及び上記ソートされた項目値アクセス情報配列をそれぞれ上記レコード順序番号配列及び上記項目値アクセス情報配列として用いて、別のデータ項目に関して、上記ステップ(i)、(ii)、(iii)及び(iv)を実行するステップをさらに備える。【００３２】
本発明の一実施形態によれば、本発明の方法を実施するマルチコア型処理装置が提供される。本実施形態によるマルチコア型処理装置は、専用のローカルメモリを含む複数台の演算ユニットと、上記複数台の演算ユニットに接続されているグローバルメモリとを備え、１つ以上のデータ項目に対応した項目値を含むレコードの配列を表現し、上記グローバルメモリに構築されている表形式データの上記レコードを所定のデータ項目に関する項目値に応じて並べ替える。このマルチコア型処理装置では、上記表形式データは、
各演算ユニットの上記ローカルメモリに収容可能なサイズをもつブロックに分割されている上記レコードの配列中の各レコードに対応するブロック番号が上記表形式データ中の上記レコードのレコード順序番号の順番に格納されているブロック番号配列と、
各ブロックに属するレコードである担当レコードの上記レコード順序番号が上記レコード順序番号の順番に格納されているレコード順序番号配列と、
上記担当レコードに含まれる上記項目値にアクセスするための項目値アクセス情報が上記レコード順序番号の順番に格納されている項目値アクセス情報配列と、
データ項目毎に上記項目値アクセス情報を用いてアクセスされる上記項目値を記述する項目値情報と、
によって表現されている。【００３３】
マルチコア型処理装置の各演算ユニットは、
(a)他の演算ユニットと並列的に動作して、上記担当レコードを含むブロック毎に、上記所定のデータ項目に関する上記項目値情報をキーとして用いて、上記項目値アクセス情報配列にソートを適用し、これによって、ソートされた項目値アクセス情報配列と、上記ソートされた項目値アクセス情報配列に対応する作業用項目値情報配列及び作業用レコード順序番号配列を上記グローバルメモリに作成する手段と、
(b)他の演算ユニットと並列的に動作して、１対のブロックに関する上記作業用項目値情報配列の第１の要素及び対応する上記作業用レコード順序番号配列の第２の要素からなる要素の組を、上記第１の要素を上位の桁及び上記第２の要素を下位の桁として用いて、所定の順序にマージし、マージされた要素の組に当該要素の組が含まれる上記ブロック番号を関連付け、これによって、上記１対のブロックに関する新たな作業用項目値情報配列、新たな作業用レコード順序番号配列、及び、新たなブロック番号配列を作成する手段と、
(c)他の演算ユニットと並列的かつ階層的に動作して、上記手段（ｂ）を繰り返し作動させ、これによって、最終的なブロック番号配列を上記グローバルメモリに作成する手段と、
(d)他の演算ユニットと並列的に動作して、上記最終的なブロック番号配列中の要素が格納されているレコード順序番号を当該要素によって指定されたブロック番号毎に分配し所定の順番に並べ、これによって、ソートされたレコード順序番号配列を上記グローバルメモリに作成する手段と、
を備える。【００３４】
本発明の好ましい一実施形態によれば、マルチコア型処理装置において各演算ユニットは上記専用のローカルメモリと上記グローバルメモリとの間のデータ転送のための専用のメモリインターフェイスをさらに備える。上記手段(a)は、上記専用のメモリインターフェイスを介して、上記担当レコードを含むブロックに対応している、上記レコード順序番号配列及び上記項目値アクセス情報配列と、上記所定の項目に関する上記項目値情報配列とを、上記グローバルメモリから上記ローカルメモリへ転送し、上記ローカルメモリに作成された上記ソートされた項目値アクセス情報配列と、上記作業用項目値情報配列及び上記作業用レコード順序番号配列とを上記グローバルメモリへ転送する。上記手段(b)は、上記専用のメモリインターフェイスを介して、１対のブロックに関する上記作業用項目値情報配列及び上記作業用レコード順序番号配列を、上記グローバルメモリから上記ローカルメモリへ転送し、上記ローカルメモリに作成された上記新たな作業用項目値情報配列、上記新たな作業用レコード順序番号配列、及び、上記新たなブロック番号配列を上記グローバルメモリ又はさらなる処理のための演算ユニットへ転送する。上記手段(c)は、上記専用のメモリインターフェイスを介して、上記ローカルメモリに作成された上記最終的なブロック番号配列を上記グローバルメモリへ転送する。【００３５】
さらに、本発明の一実施形態によれば、専用のローカルメモリを含む複数台の演算ユニットと、上記複数台の演算ユニットに接続されているグローバルメモリとを備えるコンピュータにロードされ、１つ以上のデータ項目に対応した項目値を含むレコードの配列を表現し、上記グローバルメモリに構築されている表形式データの上記レコードを所定のデータ項目に関する項目値に応じて並べ替えるコードを上記コンピュータに実行させるコンピュータ読み取り可能なプログラムであって、
コンピュータにおいて、上記表形式データは、
各演算ユニットの上記ローカルメモリに収容可能なサイズをもつブロックに分割されている上記レコードの配列中の各レコードに対応するブロック番号が上記表形式データ中の上記レコードのレコード順序番号の順番に格納されているブロック番号配列と、
各ブロックに属するレコードである担当レコードの上記レコード順序番号が上記レコード順序番号の順番に格納されているレコード順序番号配列と、
上記担当レコードに含まれる上記項目値にアクセスするための項目値アクセス情報が上記レコード順序番号の順番に格納されている項目値アクセス情報配列と、
データ項目毎に上記項目値アクセス情報を用いてアクセスされる上記項目値を記述する項目値情報と、
によって表現され、
(a)各演算ユニットが他の演算ユニットと並列的に動作して、上記担当レコードを含むブロック毎に、上記所定のデータ項目に関する上記項目値情報をキーとして用いて、上記項目値アクセス情報配列にソートを適用し、これによって、ソートされた項目値アクセス情報配列と、上記ソートされた項目値アクセス情報配列に対応する作業用項目値情報配列及び作業用レコード順序番号配列を上記グローバルメモリに作成するコードと、
(b)各演算ユニットが他の演算ユニットと並列的に動作して、１対のブロックに関する上記作業用項目値情報配列からの第１の要素及び対応する上記作業用レコード順序番号配列からの第２の要素からなる要素の組を、上記第１の要素を上位の桁及び上記第２の要素を下位の桁として用いて、所定の順序にマージし、マージされた要素の組に当該要素の組が含まれる上記ブロック番号を関連付け、これによって、上記１対のブロックに関する新たな作業用項目値情報配列、新たな作業用レコード順序番号配列、及び、新たなブロック番号配列を作成するコードと、
(c)各演算ユニットが他の演算ユニットと並列的かつ階層的に動作して、上記コード（ｂ）を繰り返し実行し、これによって、最終的なブロック番号配列を上記グローバルメモリに作成するコードと、
(d)各演算ユニットが他の演算ユニットと並列的に動作して、上記最終的なブロック番号配列中の要素が格納されているレコード順序番号を当該要素によって指定されたブロック番号毎に分配し所定の順番に並べ、これによって、ソートされたレコード順序番号配列を上記グローバルメモリに作成するコードと、
を備える。【００３６】
さらに、本発明の一実施形態によれば、専用のローカルメモリを含む複数台の演算ユニットと、上記複数台の演算ユニットに接続されているグローバルメモリとを備えるコンピュータにロードされ、１つ以上のデータ項目に対応した項目値を含むレコードの配列を表現し、上記グローバルメモリに構築されている表形式データの上記レコードを所定のデータ項目に関する項目値に応じて並べ替える本発明の方法を上記コンピュータに実行させるためのコンピュータプログラムプロダクトが提供される。【００３７】
さらに、本発明の一実施形態によれば、専用のローカルメモリを含む複数台の演算ユニットと、上記複数台の演算ユニットに接続されているグローバルメモリとを備えるコンピュータにロードされ、１つ以上のデータ項目に対応した項目値を含むレコードの配列を表現し、上記グローバルメモリに構築されている表形式データの上記レコードを所定のデータ項目に関する項目値に応じて並べ替える本発明の方法を上記コンピュータに実行させるためのコンピュータプログラムが記録された記録媒体が提供される。
【発明の効果】
【００３８】
本発明の少なくとも1つの実施例によれば、表形式データのレコードにマルチコア型処理装置によるソート処理を適用できるので、大規模な表形式データのソート処理及びこのソート処理を含む種々のアプリケーションを高速に実現することが可能になる。
【図面の簡単な説明】
【００３９】
【図１】本発明の一実施形態によるマルチコア型処理装置の概略図である。
【図２】本発明の一実施形態によるコンピュータシステムの概略図である。
【図３】本発明の基礎となるデータ管理機構を説明するための表形式データの一例を表す図である。
【図４】本発明の基礎となる基本的なデータ管理機構の説明図である。
【図５Ａ】本発明の一実施形態によるマルチコア型処理装置向けデータ構造の説明図である。
【図５Ｂ】本発明の一実施形態によるマルチコア型処理装置向けデータ構造の説明図である。
【図５Ｃ】本発明の一実施形態によるマルチコア型処理装置向けデータ構造の説明図である。
【図５Ｄ】本発明の一実施形態によるマルチコア型処理装置向けデータ構造の説明図である。
【図６Ａ】本発明の一実施形態によるソート処理を適用する前の表形式データの説明図である。
【図６Ｂ】本発明の一実施形態によるソート処理を適用した後の表形式データの説明図である。
【図７Ａ】本発明の一実施形態によるソート処理を図５Ａの表形式データに適用することによって得られる表形式データの説明図である。
【図７Ｂ】本発明の一実施形態によるソート処理を図５Ａの表形式データに適用することによって得られる表形式データの説明図である。
【図７Ｃ】本発明の一実施形態によるソート処理を図５Ａの表形式データに適用することによって得られる表形式データの説明図である。
【図７Ｄ】本発明の一実施形態によるソート処理を図５Ａの表形式データに適用することによって得られる表形式データの説明図である。
【図８】本発明の一実施形態による項目値取得処理のフローチャートである。
【図９】本発明の一実施形態による表形式データ（第１のタイプの項目値情報）のソート処理の概略的なフローチャートである。
【図１０Ａ】本発明の一実施形態による表形式データのソート処理におけるブロック内ソート処理の説明図である。
【図１０Ｂ】本発明の一実施形態による表形式データのソート処理におけるブロック内ソート処理の説明図である。
【図１０Ｃ】本発明の一実施形態による表形式データのソート処理におけるブロック内ソート処理の説明図である。
【図１１】本発明の一実施形態による表形式データのソート処理におけるブロック内ソート処理の結果の説明図である。
【図１２Ａ】本発明の一実施形態による表形式データのソート処理におけるブロック間ソート処理１の階層構造を説明する図である。
【図１２Ｂ】本発明の一実施形態による表形式データのソート処理におけるブロック間ソート処理１の階層構造を説明する図である。
【図１２Ｃ】本発明の一実施形態による表形式データのソート処理におけるブロック間ソート処理１の階層構造を説明する図である。
【図１３Ａ】本発明の一実施形態による表形式データのソート処理における１段目のマージ処理の説明図である。
【図１３Ｂ】本発明の一実施形態による表形式データのソート処理における１段目のマージ処理の説明図である。
【図１３Ｃ】本発明の一実施形態による表形式データのソート処理における１段目のマージ処理の説明図である。
【図１４Ａ】本発明の一実施形態による表形式データのソート処理における２段目のマージ処理の説明図である。
【図１４Ｂ】本発明の一実施形態による表形式データのソート処理における２段目のマージ処理の説明図である。
【図１５】本発明の一実施形態による表形式データのソート処理における３段目のマージ処理の説明図である。
【図１６Ａ】本発明の一実施形態による表形式データのソート処理におけるブロック間ソート処理１（マージ処理）の結果を表現する表形式データの説明図である。
【図１６Ｂ】本発明の一実施形態による表形式データのソート処理におけるブロック間ソート処理１（マージ処理）の結果を表現する表形式データの説明図である。
【図１６Ｃ】本発明の一実施形態による表形式データのソート処理におけるブロック間ソート処理１（マージ処理）の結果を表現する表形式データの説明図である。
【図１７Ａ】本発明の一実施形態による表形式データのソート処理におけるブロック間ソート処理２（分配処理）の説明図である。
【図１７Ｂ】本発明の一実施形態による表形式データのソート処理におけるブロック間ソート処理２（分配処理）の説明図である。
【図１７Ｃ】本発明の一実施形態による表形式データのソート処理におけるブロック間ソート処理２（分配処理）の説明図である。
【図１８】本発明の一実施形態による表形式データのソート処理の結果を説明する図である。
【図１９】本発明の一実施形態による表形式データのソート処理のフローチャートである。
【図２０】本発明の代替的な実施形態によるブロック番号配列の分離処理の説明図である。
【図２１Ａ】本発明の一実施形態による多段階ソート処理の適用例の説明図である。
【図２１Ｂ】本発明の一実施形態による多段階ソート処理の適用例の説明図である。
【図２２Ａ】本発明の一実施形態による表形式データのデータ構造の説明図である。
【図２２Ｂ】本発明の一実施形態による表形式データのデータ構造の説明図である。
【図２２Ｃ】本発明の一実施形態による表形式データのデータ構造の説明図である。
【図２２Ｄ】本発明の一実施形態による表形式データのデータ構造の説明図である。
【図２３】本発明の一実施形態による表形式データ（第２のタイプの項目値情報）のソート処理の概略的なフローチャートである。
【図２４Ａ】本発明の一実施形態による表形式データのソート処理におけるブロック内ソート処理の説明図である。
【図２４Ｂ】本発明の一実施形態による表形式データのソート処理におけるブロック内ソート処理の説明図である。
【図２４Ｃ】本発明の一実施形態による表形式データのソート処理におけるブロック内ソート処理の説明図である。
【図２４Ｄ】本発明の一実施形態による表形式データのソート処理におけるブロック内ソート処理の説明図である。
【図２４Ｅ】本発明の一実施形態による表形式データのソート処理におけるブロック内ソート処理の説明図である。
【図２４Ｆ】本発明の一実施形態による表形式データのソート処理におけるブロック内ソート処理の説明図である。
【図２４Ｇ】本発明の一実施形態による表形式データのソート処理におけるブロック内ソート処理の説明図である。
【図２４Ｈ】本発明の一実施形態による表形式データのソート処理におけるブロック内ソート処理の説明図である。
【図２５】本発明の一実施形態による表形式データのソート処理におけるブロック内ソート処理の結果の説明図である。
【図２６Ａ】本発明の一実施形態による表形式データのソート処理における１段目のマージ処理の説明図である。
【図２６Ｂ】本発明の一実施形態による表形式データのソート処理における１段目のマージ処理の説明図である。
【図２６Ｃ】本発明の一実施形態による表形式データのソート処理における１段目のマージ処理の説明図である。
【図２７Ａ】本発明の一実施形態による表形式データのソート処理における２段目のマージ処理の説明図である。
【図２７Ｂ】本発明の一実施形態による表形式データのソート処理における２段目のマージ処理の説明図である。
【図２８】本発明の一実施形態による表形式データのソート処理における３段目のマージ処理の説明図である。
【図２９Ａ】本発明の一実施形態による表形式データのソート処理におけるブロック間ソート処理１（マージ処理）の結果を表現する表形式データの説明図である。
【図２９Ｂ】本発明の一実施形態による表形式データのソート処理におけるブロック間ソート処理１（マージ処理）の結果を表現する表形式データの説明図である。
【図２９Ｃ】本発明の一実施形態による表形式データのソート処理におけるブロック間ソート処理１（マージ処理）の結果を表現する表形式データの説明図である。
【符号の説明】
【００４０】
１００      マルチコア型処理装置
１０１      マルチコア型プロセッサチップ
１１０，１２０，１３０，１４０      演算ユニット
１１１，１２１，１３１，１４１      コア
１１２，１２２，１３２，１４２      ローカルメモリ
１５０      チップ内バス
１６０，１６１，１６２，１６３      バス
１７０，１７１，１７２，１７３      グローバルメモリ
２００      コンピュータシステム
２０２      マルチコア型処理装置
２１０      ＣＰＵ
２１２      ＲＡＭ
２１４      ＲＯＭ
２１６      固定記憶装置
２１８      ＣＤ−ＲＯＭ
２２０      ＣＤ−ＲＯＭドライバ
２２２      Ｉ／Ｆ
２２４      入力装置
２２６      表示装置
２２８      バス
５００      表形式データ
５０１      データ項目「Ｓｃｈｏｏｌ」
５０２      データ項目「Ａｇｅ」
５１０      レコード０
５１１      レコード１４
５２０，５２１，・・・，５２７      ブロック
５３０      順序情報
５３１      項目情報「Ｓｃｈｏｏｌ」
５３２      項目情報「Ａｇｅ」
５４０      ブロック番号配列
５５１−０，５５１−１，・・・，５５１−７      レコード順序番号配列
５５２−０，５５２−１，・・・，５５２−７      項目値アクセス情報配列
５６０−０，５６０−１，・・・，５６０−７      ブロック情報「Ｓｃｈｏｏｌ」
５６１−０，５６１−１，・・・，５６１−７      ローカル項目値番号配列「Ｓｃｈｏｏｌ」
５６２−０，５６２−１，・・・，５６２−７      項目値指定ポインタ配列「Ｓｃｈｏｏｌ」
５７０      グローバル項目値配列「Ｓｃｈｏｏｌ」
５８０−０，５８０−１，・・・，５８０−７      ブロック情報「Ａｇｅ」
５８１−０，５８１−１，・・・，５８１−７      ローカル項目値番号配列「Ａｇｅ」
５８２−０，５８２−１，・・・，５８２−７      項目値指定ポインタ配列「Ａｇｅ」
５９０      グローバル項目値配列「Ａｇｅ」
【発明を実施するための最良の形態】
【００４１】
以下、本発明を実施するための種々の形態を図面と共に詳細に説明する。【００４２】
［マルチコア型処理装置］
最初に、本発明の一実施例によるデータ処理を実現するマルチコア型処理装置について説明する。図１はマルチコア型処理装置の一実施形態の概略図である。マルチコア型処理装置１００は、マルチコア型プロセッサチップ１０１上に複数台（たとえば、２台、４台、８台等、本例では４台）の演算ユニット１１０、１２０、１３０、１４０が設けられている。各演算ユニット１１０、１２０、１３０、１４０は、データ処理用のコア１１１、１２１、１３１、１４１とコア専用のローカルメモリ１１２、１２２、１３２、１４２とを含む。各演算ユニット１１０、１２０、１３０、１４０は、チップ内のバス１５０によって接続されている。このバス１５０は、好ましくは、リング型バスである。演算ユニットは、チップ内のバス１５０によって接続されているので、高速にデータ通信することが可能である。さらに、各演算ユニット１１０、１２０、１３０、１４０は、ＤＭＡ転送をサポートするバス１６０、１６１、１６２、１６３を介して、チップ１０１に外付けされたグローバルメモリ１７０、１７１、１７２、１７３と接続されている。【００４３】
チップ内のローカルメモリ１１２、１２２、１３２、１４２の記憶容量は、たとえば、２５６ＫＢ（キロバイト）程度であり、一方、グローバルメモリ１７０、１７１、１７２、１７３は数十ＧＢ（ギガバイト）の大容量メモリである。同図では、グローバルメモリ１７０、１７１、１７２、１７３が区別して記載されている。これは、各コアからグローバルメモリへ１本のバスでアクセスすると、バスの通信性能がボトルネックとなるので、各コアに専用のメモリインターフェイス（図示せず）を設け、外付けのグローバルメモリへはこのメモリインターフェイスを介してアクセスすることを示している。もちろん、このような構成であっても、ＮＵＭＡ（不均一メモリアクセス）方式のように、グローバルメモリが全体として論理的に連続した１つのメモリとして見えるように管理することは可能である。代替的な実施形態では、各演算ユニットは、１つのバスを介して物理的に一体的な外付けのグローバルメモリに接続される。【００４４】
さらに、上記のＣｅｌｌ  Ｂｒｏａｄｂａｎｄ  ＥｎｇｉｎｅＴＭのようなプロセッサでは、１チップ内には、汎用プロセッサコアと、演算用プロセッサコアとが搭載されている。汎用プロセッサコアは複数台の演算用プロセッサコアの動作を制御することが可能である。したがって、マルチコア型プロセッサは、好ましくは、汎用プロセッサコアのような制御ユニットを備えるが、制御ユニットは、チップ内に搭載する必要はなく、チップの外部に設けられることもある。【００４５】
制御ユニットと演算ユニット、又は、演算ユニット同士は、たとえば、メールボックスやシグナル機構を用いて通信することが可能である。【００４６】
［コンピュータシステム構成］
図２は、本発明の一実施形態による表形式データを操作するコンピュータシステム２００の概略図である。コンピュータシステム２００は、データ項目に対応した項目値を含むレコードの配列として表される表形式データを複数台の演算ユニットによって分担して操作する、図１に示されているような、マルチコア型処理装置２０２を備えている。図２に示されているように、コンピュータシステム２００は、さらに、プログラムを実行することによりシステム全体および個々の構成部分を制御するＣＰＵ２１０と、ワークデータ等を記憶する、たとえば、ＲＡＭ(Random Access Memory)のようなメモリ２１２と、プログラム等を記憶するＲＯＭ(Read Only Memory)２１４と、ハードディスク等の固定記憶媒体２１６と、ＣＤ−ＲＯＭ２１８をアクセスするためのＣＤ−ＲＯＭドライバ２２０と、ＣＤ−ＲＯＭドライバ２２０及び外部ネットワーク等（図示せず）へ繋がれた外部端子に接続されているインタフェース（Ｉ／Ｆ）２２２と、キーボード及びマウス等のような入力装置２２４と、コンピュータモニターのような表示装置２２６とを備えている。マルチコア型処理装置２１０、ＲＡＭ２１２、ＲＯＭ２１４、外部記憶媒体２１６、Ｉ／Ｆ２２２、入力装置２２４及び表示装置２２６は、バス２２８を介して相互に接続されている。【００４７】
表形式データの操作をコンピュータシステム２００のマルチコア型処理装置２０２とＣＰＵ２１０に実行させるプログラムは、ＣＤ−ＲＯＭ２１８に収容され、ＣＤ−ＲＯＭドライバ２２０に読取られても良いし、ＲＯＭ２１４に予め記憶されていても良い。また、いったんＣＤ−ＲＯＭ２１８から読み出したものを、外部記憶媒体２１６の所定の領域に記憶しておいても良い。或いは、上記プログラムは、ネットワーク（図示せず）、外部端子、及び、Ｉ／Ｆ２２０を介して、外部から供給されるものであっても良い。【００４８】
また、本発明の一実施形態によるマルチコア型プロセッサシステムは、コンピュータシステム２００に表形式データを操作するプログラムを実行させることにより実現される。【００４９】
図２に示されているコンピュータシステム２００では、マルチコア型処理装置２０２の他にＣＰＵ２１０が設けられ、システム全体及び個々の構成部分を制御している。しかし、本発明は、このような実施形態に限定されることはなく、代替的な実施形態では、マルチコア型処理装置２０２に含まれている制御ユニットがシステム全体及び個々の構成部品を制御する。【００５０】
［情報ブロックに基づくデータ管理機構］
図３は本発明の基礎となるデータ管理機構を説明するための表形式データの一例を表す図である。この表形式データは、上述の国際公開第ＷＯ００／１０１０３号に提案したデータ管理機構を用いることにより、コンピュータ内では図４に示されるようなデータ構造として記憶される。このデータ構造は、市販されているコンピュータ、たとえば、パーソナルコンピュータのハードウェア資源、特に、プロセッサ及びメモリを使用して大規模な表形式データの検索、ソート、集計等を実現するために提案された、コンピュータのメモリ上に置かれる表形式データのデータ構造であることに注意すべきである。【００５１】
なお、本書中では、「元の表形式データ中でレコードが収容されている位置を表す情報（すなわち、原始レコード位置番号）」と「レコードの並び順を表す情報（すなわち、レコード順序番号）」とが区別されている。原始レコード位置番号は、データ項目に対応した項目値を含む個々のレコードを特定するために利用される仮想的な情報である。たとえば、通常の表形式データを情報ブロックに基づく表形式データに変換する際に、元々の通常の表形式データ中でレコードが収容されている位置が原始レコード位置番号によって表される。一般に、情報ブロックに基づく表形式データでは、レコードが常に原始レコード位置番号の順番に配列されているとは限らない。たとえば、表形式データをある項目の項目値に関して昇順にソートすると、ソート後の表形式データのレコードの並び順は元の表形式データのレコードの並び順とは異なる。但し、通常の表形式データから変換された直後の情報ブロックに基づく表形式データ中のレコードは、レコードが原始レコード位置番号の順番に並べられていることがあり、この場合には、原始レコード位置番号とレコード順序番号とが初期的に一致している。【００５２】
図４に示すように、表形式データの各レコードの並び順の番号（レコード順序番号）と、原始レコード位置番号は、レコード順序指定配列４０１（以下、この配列を「ＯｒｄＳｅｔ」のように略記する。）によって対応付けられる。レコード順序指定配列４０１は、レコード順序番号の順に原始レコード位置番号を格納している。図４の例では、レコードは原始レコード位置番号の順番に並べられている。【００５３】
ここで、本明細書中での配列の記法について説明する。一般に、配列Ａは、添字をｉとすると、配列の要素がＡ［ｉ］のように表記できるが、図面中では、配列は、配列の要素Ａ［ｉ］は、実線で囲まれた領域内に示され、要素Ａ［ｉ］と要素Ａ［ｉ＋１］の境界は点線で示されている。また、要素Ａ［ｉ］の添字ｉが要素Ａ［ｉ］の左側に示されている。また、配列の添字ｉは０から始まる整数で表されている。【００５４】
もう一度図４に戻ると、性別に関しては、表形式データのレコード順序番号＝０に対応する原始レコード位置番号は、配列ＯｒｄＳｅｔ［０］から「０」であることがわかる。原始レコード位置番号が「０」であるレコードに関する実際の性別の値、即ち、「男」又は「女」は、実際の値が所定の順序（たとえば、昇順又は降順）に従ってソートされた値リストである項目値配列４０３（以下、項目値配列、すなわち、値リストを「ＶＬ」のように略記する。）へのポインタ配列である項目値番号配列４０２（以下、項目値番号配列、すなわち、ポインタ配列を「ＶＮｏ」のように略記する。）を参照することによって取得できる。ポインタ配列４０２は、配列ＯｒｄＳｅｔ４０１に格納されている原始レコード位置番号の順番に従って、実際の値リスト４０３中の要素を指し示すポインタを格納している。これにより、表形式データのレコード「０」に対応する性別の項目値は、（１）配列ＯｒｄＳｅｔ４０１からレコード順序番号＝０に対応する原始レコード位置番号＝０を取り出し、（２）値リストへのポインタ配列４０２から原始レコード位置番号＝０に対応する要素「１」を取り出し、（３）値リスト４０３から、値リストへのポインタ配列３０２から取り出された要素「１」によって指し示される要素「女」を取り出すことにより取得できる。【００５５】
他のレコードに対しても、また、年齢及び身長に関しても同様に項目値を取得することができる。【００５６】
このように表形式データは、値リストＶＬと、値リストへのポインタ配列ＶＮｏの組合せにより表現され、この組合せを、特に、「情報ブロック」と称する。図４には、性別、年齢及び身長に関する情報ブロックがそれぞれ情報ブロック４０８、４０９及び４１０として示されている。【００５７】
単一のコンピュータが単一のメモリ（物理的には複数であっても良いが、単一のアドレス空間に配置されアクセスされるという意味で単一のメモリ）を有するならば、単一のコンピュータは、当該メモリに、順序集合の配列ＯｒｄＳｅｔ、各情報ブロックを構成する値リストＶＬおよびポインタ配列ＶＮｏとを記憶しておけばよい。しかしながら、本発明の種々の実施形態では、表形式データの操作は、小容量の専用のローカルメモリを伴う複数台の演算ユニットにより構成されたマルチコア型処理装置によって行われる。そのため、効率的な並列処理を実現するために、表形式データを保持する新たな仕組みが提案されている。【００５８】
［マルチコア型処理装置向けデータ構造］
次に、本発明の一実施形態によるマルチコア型処理装置向けデータ構造について説明する。図５Ａ乃至５Ｂは本発明の一実施形態によるデータ構造の説明図である。図５Ａは、表形式データの一例を示している。図５Ａ５Ａに示された表形式データ５００は、「Ｓｃｈｏｏｌ」というデータ項目５０１に対応した項目値（たとえば、「Ｗｅｓｔ」、「Ｓｏｕｔｈ」、「Ｎｏｒｔｈ」及び「Ｅａｓｔ」と、「Ａｇｅ」というデータ項目５０２に対応した項目値（たとえば、「１２」、「８」、「１１」、「１０」など）とを含むレコードの配列として表される。この表形式データ５００のレコードは、先頭から順番に、レコード順序番号＝０、１、２、・・・、３１の順番に並んでいる。配列の先頭に位置するレコード５１０は、レコード順序番号０が付与されたレコードである。レコード５１０のデータ項目「Ｓｃｈｏｏｌ」の項目値は「Ｗｅｓｔ」であり、データ項目「Ａｇｅ」の項目値は「１２」である。レコード５１１のデータ項目「Ｓｃｈｏｏｌ」の項目値は「Ｎｏｒｔｈ」であり、データ項目「Ａｇｅ」の項目値は「９」である。ここで、この表形式データのレコードがソート処理によって並び替えられると、各レコードに付与されるレコード順序番号は変化することに注意すべきである。【００５９】
本発明の一実施形態によるマルチコア型処理装置向けデータ構造では、この表形式データのレコードは、ブロック番号（本例では、０から７の８個のブロック番号）によって識別されるブロック５２０、５２１、・・・、５２７に分割される。初期的には、このブロックは、このブロックに含まれるレコードの処理を担当するマルチコア型処理装置の演算ユニットに対応している。【００６０】
マルチコア型処理装置向けデータ構造は、レコードの並び順（すなわち、レコード順序番号）と、データ構造内の項目値の格納場所とを対応付ける順序に関する情報（順序情報）と、データ項目毎の項目値に関する情報（項目値情報）とによって構成される。順序情報は、機能的に上記の本発明の基礎となるデータ管理機構におけるレコード順序指定配列ＯｒｄＳｅｔに対応し、項目値情報は、同様に情報ブロックに対応している。順序情報と項目値情報は、共にグローバルメモリに保持され、必要に応じて、それらの一部が各演算ユニットのローカルメモリへ転送される。図５Ｂは順序情報５３０を示し、図５Ｃ及び５Ｂ５Ｃ５Ｄは、それぞれ、データ項目「Ｓｃｈｏｏｌ」及びデータ項目「Ａｇｅ」の項目値情報５３１及び５３２を示している。【００６１】
順序情報５３０は、ブロック番号がレコード順序番号の順番に、格納されているブロック番号配列５４０を含む。本実施形態のデータ構造では、レコード毎に当該レコードの操作を担当する演算ユニットが定められる。よって、（複数の）レコードは、各演算ユニットが担当するレコード、すなわち、担当レコードに分割され、担当レコード毎にブロック番号が割り当てられる。ブロック番号配列をＢｌｋＮｏ、レコード順序番号をｉとすると、ＢｌｋＮｏ［ｉ］は、レコード順序番号ｉをもつレコードが属するブロックのブロック番号がＢｌｋＮｏ［ｉ］であることを表している。ブロック番号配列５４０は、レコードの個数に等しいサイズを有する整数型の配列である。また、ブロック番号配列５４０は第２のタイプのデータである。たとえば、図５の例では、レコード順序番号０から３のレコードはブロック番号０のブロックに含まれ、レコード順序番号４から７のレコードはブロック番号１のブロックに含まれ、以下同様である。【００６２】
本実施形態のデータ構造によれば、全レコードはブロックに対応した担当レコードに分割されるので、ブロック毎に、担当レコードのそれぞれを元の表形式データのレコードと対応付ける情報が必要になる。そのため、順序情報５３０は、ブロック毎に、担当レコードのレコード順序番号がレコード順序番号の順番に格納されているレコード順序番号配列５５１−１、５５１−２、・・・、５５１−７を含む。レコード順序番号配列は、以下では、ＧＯｒｄという名前で呼ばれることがある。たとえば、図５の例では、ブロック番号０というブロックに属する担当レコードのレコード順序番号は、０、１、２、３であり、ブロック番号１というブロックに属する担当レコードのレコード順序番号は、４、５、６、７であり、以下同様である。レコード順序番号配列は、各ブロックに属する担当レコードの数と同じサイズを有し、整数型の配列である。また、レコード順序番号配列は、各演算ユニットのローカルメモリに収容可能なサイズに分割されているので、第１のタイプのデータである。したがって、レコード順序番号配列は、必要に応じて、グローバルメモリから各演算ユニット内のローカルメモリへ転送される。【００６３】
ここで、ブロック番号配列５４０とレコード順序番号配列５５１−１、５５１−２、・・・、５５１−７は、相互に変換可能であることに注意すべきである。たとえば、レコード順序番号ｉをもつレコードが属するブロックのブロック番号がＢｌｋＮｏ［ｉ］で表現され、ブロック番号＝ｊであるブロックに属するレコード順序番号配列の添字ｋに対応する要素がＧＯｒｄ［ｊ］［ｋ］で表現されるとする。このとき、レコードの総数をＲｍａｘとすると、ブロック番号配列からレコード順序番号配列への変換は、
Ｆｏｒ  （ｉ＝０；ｉ＋＋；ｉ＜Ｒｍａｘ）  ｛
ＧＯｒｄ［ＢｌｋＮｏ［ｉ］］［ｊ［ＢｌｋＮｏ［ｉ］］］＝ｉ；
ｊ［ＢｌｋＮｏ［ｉ］］＋＋；
｝
として表現される。ここで、ｊ［ＢｌｋＮｏ［ｉ］］は、ブロック番号がＢｌｋＮｏ［ｉ］であるブロックに属するレコード順序番号配列ＧＯｒｄ［ＢｌｋＮｏ［ｉ］］の要素を指定する添字を表している。なお、変数ｊ［ＢｌｋＮｏ［ｉ］］は全要素が０に初期化されている。【００６４】
逆に、レコード順序番号配列からブロック番号配列への変換は、ブロック番号をｉ、ブロックの総数をＢｍａｘ、各ブロック内のレコードの総数をＢＲｍａｘによって表現すると、以下のように記述される。すなわち、
Ｆｏｒ  （ｉ＝０；ｉ＋＋；ｉ＜Ｂｍａｘ）｛
Ｆｏｒ  （ｊ＝０；ｊ＋＋；ｊ＜ＢＲｍａｘ）  ｛
ＢｌｋＮｏ［ＧＯｒｄ［ｉ］］［ｊ］＝ｉ；
｝
｝
となる。【００６５】
このように、ブロック番号配列とレコード順序番号配列は相互変換が可能であるため、何れか一方が準備されているならば十分である。【００６６】
さらに、各レコードに含まれる項目値は、後述する項目値情報の形で保持されているので、各演算ユニットは、担当レコードに含まれる項目値をアクセスするためのアドレス情報、すなわち、項目値アクセス情報を取得することが必要である。よって、本実施形態のデータ構造によれば、順序情報５３０は、ブロック毎に、担当レコードの項目値アクセス情報がレコード順序番号の順番に格納されている項目値アクセス情報配列５５２−１、５５２−２、・・・、５５２−７をさらに含む。この項目値アクセス情報配列は整数型の配列であり、項目値アクセス情報配列のサイズは担当レコードのレコード数に一致する。項目値アクセス情報配列もまた、第１のタイプのデータであり、必要に応じて、グローバルメモリから各演算ユニット内のローカルメモリへ転送される。項目値アクセス情報配列は、ＬＯｒｄという名前で呼ばれることもある。たとえば、図５の例では、ブロック番号０というブロックに含まれるレコード順序番号が０というレコードに含まれる項目値は、このブロック番号０に関して、０という項目値アクセス情報によってアクセス可能であり、ブロック番号１というブロックに含まれるレコード順序番号が５というレコードに含まれる項目値は、このブロック番号１に関して、１という項目値アクセス情報によってアクセス可能である。【００６７】
次に、本実施形態によれば、項目値情報は、データ項目毎の項目値情報として保持される。たとえば、図５の例では、データ項目「Ｓｃｈｏｏｌ」に関する項目値情報５３１とデータ項目「Ａｇｅ」に関する項目値情報５３２とがグローバルメモリに構築される。そして、ブロック毎の担当レコードに含まれる項目値は、データ項目毎に各演算ユニットが項目値アクセス情報配列を用いてアクセスすることができるようにグローバルメモリに保持され、必要に応じて、グローバルメモリから各演算ユニット内のローカルメモリへ転送される。項目値そのものは、データ項目毎に、一意の項目値が所定の順序（昇順又は降順）に格納されているグローバル項目値配列としてグローバルメモリ上に構築されている。たとえば、図５の例では、データ項目「Ｓｃｈｏｏｌ」に関する項目値は、グローバル項目値配列５７０としてグローバルメモリに保持され、データ項目「Ａｇｅ」に関する項目値は、グローバル項目値配列５９０としてグローバルメモリに保持されている。このグローバル項目値配列は第２のタイプのデータである。なお、グローバル項目値配列は、項目値そのものを格納する配列であるため、整数型、浮動小数点型、文字列型などの様々なデータ型をとる。【００６８】
項目値情報は、担当レコードに関連した項目値アクセス情報を用いて、グローバル項目値配列に格納されている項目値を特定できるように構成されている。そのため、項目値情報は、データ項目毎に、担当レコードに含まれる項目値を特定するローカル項目値番号がレコード順序番号の順番（たとえば、昇順又は降順）に格納されているローカル項目値番号配列と、ローカル項目値番号によって表される項目値がグローバル項目値配列中に格納されている位置を指定する項目値指定ポインタがローカル項目値番号の順番に格納されている項目値指定ポインタ配列とを含む。ローカル項目値番号配列及び項目値指定ポインタ配列はブロック毎に設けられる。ローカル項目値番号配列は、担当レコードのレコード数に一致するサイズを有する整数型配列であり、第１のタイプのデータであり、ＶＮｏという名前で呼ばれることもある。項目値指定ポインタ配列は、担当レコードに含まれる一意の項目値の数と同じサイズを有する整数型配列であり、第１のタイプのデータであり、ＬＶＬという名前で呼ばれることもある。ローカル項目値番号配列及び項目値指定ポインタ配列は、共に第１のタイプのデータであるため、ブロック毎にグローバルメモリ上に構築され、必要に応じて、グローバルメモリから各演算ユニット内のローカルメモリへ転送される。【００６９】
図５の例では、データ項目「Ｓｃｈｏｏｌ」に関して、項目値情報５３１は、ローカル項目値番号配列５６１−０、５６１−１、・・・、５６１−７と、項目値指定ポインタ配列５６２−０、５６２−１、・・・、５６２−７と、グローバル項目値配列５９０とを含む。ローカル項目値番号配列と項目値指定ポインタ配列は、ブロック毎に分割されている。同図において、たとえば、ローカル項目値番号配列ＶＮｏの先頭の要素の値は「１」である。これは、値が「０」である項目値アクセス情報によって指定されたレコードに含まれる項目値の項目値番号が「１」であることを意味する。項目値番号が「１」である項目値は、項目値指定ポインタ配列ＬＶＬの２番目の要素、すなわち、ＬＶＬ［１］を参照することにより、グローバル項目値配列ＧＶＬの３番目の要素、すなわち、ＧＶＬ［２］であることがわかる。その他のブロックに関しても、また、その他のデータ項目に関しても、同様である。【００７０】
このように、本実施形態のデータ構造によれば、各ブロックに属するレコードに含まれる項目値は、ブロック内で各項目値に付けられたローカル項目値番号と、このローカル項目値番号とグローバル項目値配列中の項目値とを対応付ける項目値指定ポインタと、グローバル項目値配列とによって表現されている。【００７１】
［表形式データのソート処理の概要］
次に、本発明の一実施形態によるマルチコア型処理装置による表形式データのソート処理について説明する。図６は本発明の一実施形態による表形式データのソート処理の説明図である。図６Ａにはソート処理前の表形式データが示され、図６Ｂにはソート処理後の表形式データが示され、ソート処理前の表形式データは図５Ａに示された表形式データと同一である。同図の例では、表形式データは、データ項目「Ｓｃｈｏｏｌ」をキーとして、このデータ項目の項目値の昇順（より具体的にはアルファベット順）にレコードが並べ替えられている。ソート前のレコード順序番号＝０に相当するレコード（Ｗｅｓｔ，１２）は、ソート処理によってレコード順序番号が２４に変化している。また、ソート前のレコード順序番号＝２に相当するレコード（Ｗｅｓｔ，１１）は、ソート処理後にレコード順序番号が２５に変化している。このようにキー値が同値（すなわち、Ｗｅｓｔ）である２つのレコードの順序がソート処理の前後で変化しないようなソート処理は「安定性のある」ソート処理と呼ばれる。ここで、レコード（Ａ，Ｂ）という表記は、データ項目「Ｓｃｈｏｏｌ」の項目値がＡであり、データ項目「Ａｇｅ」の項目値がＢであるレコードを表している。【００７２】
図６Ａに示されたソート処理前の表形式データは、マルチコア型処理装置向けデータ構造を用いると図５Ａ乃至５Ｄに示されたデータ構造によって表現される。これに対して、図７Ａ乃至７Ｄは、本発明の一実施形態によるソート処理を、図５Ａ乃至５Ｄに示された表形式データに適用することにより得られる表形式データの説明図である。図７Ａ乃至７Ｄを参照して、ソート処理の結果を説明する。たとえば、図７Ａの表形式データのレコード順序番号＝０に相当するレコード（Ｅａｓｔ，６）は、図７Ｂのブロック番号配列のＢｌｋＮｏ［０］＝２から、ブロック番号＝２のブロックに属していることがわかる。次に、ブロック番号＝２のブロックに含まれるレコード順序番号配列ＧＯｒｄを参照すると、レコード順序番号＝０と一致するレコード順序番号配列ＧＯｒｄの要素は、ＧＯｒｄ［０］であることがわかる。このレコード順序番号＝０が格納されているレコード順序番号配列ＧＯｒｄ中の要素ＧＯｒｄ［０］の格納位置、すなわち、０は、このブロックを受け持つ演算ユニットの担当レコード中での対象レコードの順位（ランク）を表している。レコード順序番号配列は、本実施形態では、昇順の配列であるため、この格納位置は、周知の２分割法などによって効率的に見つけられる。【００７３】
次に、ブロック番号＝２のブロック中でランク＝０が付与されたレコードに含まれる項目値情報を取得するために、項目値アクセス情報配列ＬＯｒｄが参照される。より具体的には、ＬＯｒｄ［０］＝０は、ブロックＮｏ．２のブロック中のランク＝０が付与されたレコードに含まれる項目値情報にアクセスするための項目値指定ポインタを表している。【００７４】
データ項目「Ｓｃｈｏｏｌ」に関する項目値情報は図７Ｃに示されている。ブロックＮｏ．２のブロック中のランク＝０が付与されたレコードに含まれる項目値は、
ＧＶＬ［ＬＶＬ［ＶＮｏ［ＬＯｒｄ［０］］＝“Ｅａｓｔ”
によって得られる。この項目値は次の手順にしたがって取得される。最初に、ブロック２に関するローカル項目値番号配列ＶＮｏ中で、項目値アクセス情報＝ＬＯｒｄ［０］＝０によって指定される要素
ＶＮｏ［ＬＯｒｄ［０］］＝ＶＮｏ［０］＝０
を取得する。次に、項目値指定ポインタ配列ＬＶＬ中で、ＶＮｏ［０］＝０によって指定される要素
ＬＶＬ［ＶＮｏ［０］］＝ＬＶＬ［０］＝０
を取得する。最後に、得られた項目値指定ポインタを用いてグローバル項目値配列ＧＶＬ中から項目値
ＧＶＬ［ＬＶＬ［０］］＝ＧＶＬ［０］＝“Ｅａｓｔ”
を取得する。これにより、図７Ａの表形式データのレコード順序番号＝０に相当するレコードに含まれるデータ項目「Ｓｃｈｏｏｌ」に関する項目値は“Ｅａｓｔ”であることが示された。同様に、データ項目「Ａｇｅ」に関する項目値が“６”であることも明らかである。【００７５】
このように、本発明の一実施形態によるソート処理では、ソート処理の前後で変化するのは順序情報（すなわち、ブロック番号配列、レコード順序番号配列及び項目値アクセス情報配列）だけであり、項目値情報はソート処理の前後で変化しない。【００７６】
本実施形態の説明では、項目値情報は、ローカル項目値番号配列ＶＮｏ、項目値指定ポインタ配列ＬＶＬ、及び、グローバル項目値配列ＧＶＬによって構成されているが、項目値情報は、加工されていない項目値を含む項目値配列によって構成することも可能である。よって、以下の説明では、前者を第１のタイプの項目値情報、後者を第２のタイプの項目値情報と呼ぶことにする。【００７７】
［項目値取得処理の概要］
なお、本発明の一実施形態によるマルチコア型処理装置では、上記の項目値を取得する処理は、制御ユニットと演算ユニットの協働、及び、グローバルメモリとローカルメモリとの間のデータ転送を利用して行われる。図８は、本発明の一実施形態による項目値取得方法のフローチャートである。図８に示されているように、最初に、制御ユニットが、グローバルメモリ上のブロック番号配列を参照して、項目値が取得されるべき所定のレコードが含まれるブロックのブロック番号と、このブロックを担当する演算ユニットとを決定する（ステップ８０２）。次に、制御ユニットは、決定されたブロック番号によって識別される演算ユニットへ所定のレコードのレコード順序番号を通知する（ステップ８０４）。その後、演算ユニットは、この演算ユニットの担当レコードに関するレコード順序番号配列及び項目値アクセス情報配列を、グローバルメモリからこの演算ユニットのローカルメモリへ転送する（ステップ８０６）。続いて、演算ユニットは、通知されたレコード順序番号が格納されている位置をローカルメモリへ転送されたレコード順序番号配列中で特定する（ステップ８０８）。その後、演算ユニットは、特定された位置によって指定される項目値アクセス情報をローカルメモリへ転送された項目値アクセス情報配列中で特定する（ステップ８１０）。最後に、演算ユニットは、データ項目毎に、グローバルメモリに保持されたグローバル項目値配列の中から特定された項目値アクセス情報によって指定される項目値を取得し、取得された項目値をグローバルメモリへ転送する（ステップ８１２）。【００７８】
［表形式データのソート処理（第１のタイプの項目値情報）］
第１のタイプの項目値情報を含む表形式データのソート処理は、以下の３ステップにより構成される。図９は、第１のタイプの項目値情報を含む表形式データのソート処理の概略的なフローチャートである。【００７９】
ステップ９０１：ブロック内ソート
各演算ユニットが並列的に動作して、それぞれのブロック内で、ローカル項目値番号配列ＶＮｏをキーとして、項目値アクセス情報配列ＬＯｒｄに分布数え上げソートを適用し、ソートされた項目値アクセス情報配列ＬＯｒｄに適合するように項目値指定ポインタ配列ＬＶＬ’及びレコード順序番号配列ＧＯｒｄ’を生成する。【００８０】
ステップ９０２：ブロック間ソート１（マージ）
各演算ユニットが並列的かつ階層的に動作して、項目値指定ポインタ配列ＬＶＬ’及びレコード順序番号配列ＧＯｒｄ’からブロック番号配列ＢｌｋＮｏを生成する。ここでは、ブロック間で、それぞれのブロックからの項目値指定ポインタ配列ＬＶＬ’、レコード順序番号配列ＧＯｒｄ’及びブロック番号配列ＢｌｋＮｏ’がトーナメント方式で所定の順序にマージされる。【００８１】
ステップ９０３：ブロック間ソート２（分配）
各演算ユニットが並列的に動作して、ブロック番号配列ＢｌｋＮｏからレコード順序番号配列ＧＯｒｄを生成する。【００８２】
このように、表形式データのソート処理は、ブロック内ソートと、ブロック間ソート１（マージ）と、ブロック間ソート２（分配）の３ステップによって実現される。ここで、ブロック間ソート１（マージ）は、１対のブロックからのデータを所定の順序で並べ替えるという意味でソート処理であり、１対のブロックからのデータを１組のデータに統合するという意味でマージ処理でもある。本文書中において、「所定の順序でマージ」するとは、ブロック間ソート１（マージ）における処理を指している。【００８３】
以下では、図５Ａ乃至５Ｄ、図６Ａ及び６Ｂ、及び図７Ａ乃至７Ｄに示された例を参照して、本発明の一実施形態による表形式データのソート処理（第１のタイプの項目値情報）の各ステップの処理をより詳細に説明する。【００８４】
図１０Ａ乃至１０Ｃは本発明の一実施形態による表形式データのソート処理におけるブロック内ソート処理の説明図である。同図には、一例として、ブロック番号＝１のブロック（すなわち、ブロック１）に関する処理が記載されているが、他のブロックに関する処理も同様に行われることは当業者に明白であろう。各ブロックに関する処理は、そのブロックが割り当てられた各演算ユニットによって実行される。また、以下の説明では、配列の操作は、Ｃ言語に類似した疑似命令によって表現されることがある。【００８５】
図１０Ａは分布数え上げソート処理におけるカウントアップ処理の説明図である。図１０Ａには、ブロック１に関するレコード順序番号配列ＧＯｒｄ、項目値アクセス情報配列ＬＯｒｄ、ローカル項目値番号配列ＶＮｏ、及び、項目値指定ポインタ配列ＬＶＬと、分布数え上げソートのキーとして利用するローカル項目値番号の出現回数をカウントするカウント配列Ｃｏｕｎｔの遷移が示されている。カウントアップ処理は、
ｆｏｒ  （ｉ＝０；ｉ＜ブロック内レコード数；ｉ＋＋）  ｛
Ｃｏｕｎｔ［ＶＮｏ［ＬＯｒｄ［ｉ］］］＋＋；
｝
として記述できる。図１０Ａの例では、１段目がｉ＝０、２段目がｉ＝１、３段目がｉ＝２、４段目がｉ＝３に対応している。【００８６】
図１０Ｂは分布数え上げソート処理における累計数化処理の説明図である。カウントアップ処理の結果として得られたカウント配列Ｃｏｕｎｔは、
Ｃｏｕｎｔ［０］＝１
Ｃｏｕｎｔ［１］＝２
Ｃｏｕｎｔ［２］＝１
である。この出現回数を累積度数分布に変換すると（すなわち、累計数化すると）、累積度数分布配列Ａｇｇｒが得られる。なお、この累計数化処理によって生成される累積度数分布配列Ａｇｇｒの先頭の要素は０であり、実際の累積度数はＡｇｇｒ［１］以降に格納されている。累計数化処理は、たとえば、
Ａｇｇｒ［０］＝０；
ｆｏｒ  （ｉ＝１；ｉ＜キー値の個数；ｉ＋＋）  ｛
Ａｇｇｒ［ｉ］＝Ａｇｇｒ［ｉ−１］＋Ｃｏｕｎｔ［ｉ−１］；
｝
として記述できる。【００８７】
最後に、このようにして生成された累積度数分布配列Ａｇｇｒの要素をポインタとして利用して項目値アクセス情報配列ＬＯｒｄの要素をコピーすることにより、ソートされた項目値アクセス情報配列ＬＯｒｄ’が得られる。図１０Ｃは分布数え上げソート処理における転送処理の説明図である。転送処理では、配列ＬＯｒｄの要素を配列ＬＯｒｄ’へコピーするだけでなく、新たに生成された配列ＬＯｒｄ’に対応する項目値指定ポインタ配列ＬＶＬ’及びレコード順序番号配列ＧＯｒｄ’も生成される。たとえば、図１０Ｃの最上段には、ＬＯｒｄ［０］をコピーする処理が示されている。ＬＯｒｄ［０］＝０は、ＬＯｒｄ’の要素ＬＯｒｄ’［１］へコピーされている。これは、ＬＯｒｄ［０］であるレコードに含まれる項目値のローカル項目値番号ＶＮｏ［０］が１であることから、累積度数分布配列Ａｇｇｒ中の要素Ａｇｇｒ［１］＝１をポインタとして利用して、項目値アクセス情報配列ＬＯｒｄ’の要素ＬＯｒｄ’［１］にＬＯｒｄ［０］＝０をコピーすることによって実現されている。この転送処理は、一般的に、たとえば、
ｆｏｒ  （ｉ＝０；ｉ＜ブロック内のレコード数；ｉ＋＋）  ｛
ＬＯｒｄ’［Ａｇｇｒ［ＶＮｏ［ＬＯｒｄ［ｉ］］］］＝ＬＯｒｄ［ｉ］；
ＬＶＬ’［Ａｇｇｒ［ＶＮｏ［ＬＯｒｄ［ｉ］］］］＝ＬＶＬ［ＶＮｏ［ＬＯｒｄ［ｉ］］］；
ＧＯｒｄ’［Ａｇｇｒ［ＶＮｏ［ＬＯｒｄ［ｉ］］］］＝ＧＯｒｄ［ｉ］；
Ａｇｇｒ［ＶＮｏ［ＬＯｒｄ［ｉ］］］＋＋；
｝
として記述できる。【００８８】
このようにして得られた項目値アクセス情報配列ＬＯｒｄ’は、ソート後のブロック内での最終的な項目値アクセス情報配列ＬＯｒｄと一致する。また、新たに生成された項目値指定ポインタ配列ＬＶＬ’とレコード順序番号配列ＧＯｒｄ’は、ブロック内で項目値をキーとしてソートされたレコードに対応している。【００８９】
本発明の一実施形態によれば、各演算ユニットによってブロック内でソートされた表形式データのレコードは、次に、ブロック間でマージされる。ブロック間のマージでは、それぞれのブロック内でソートされているデータが併合され、全体としてソートされた併合データが生成される。より具体的には、項目値指定ポインタ配列ＬＶＬ’の要素とレコード順序番号配列ＧＯｒｄ’の要素の組がソートされる。レコード順序番号配列ＧＯｒｄ’の要素はレコード毎に一意に決まる値をもつので、項目値指定ポインタ配列ＬＶＬ’の要素とレコード順序番号配列ＧＯｒｄ’の要素の組は一意である。あるデータ項目に関する項目値指定ポインタ配列ＬＶＬ’の要素は、そのデータ項目に関する項目値が所定の順序で整列させられたグローバル項目値配列の要素を指示するので、項目値指定ポインタ配列ＬＶＬ’の要素の値の順番にソートすることは、項目値の順番にソートすることと等価である。なお、ブロック内ソート処理の結果として得られた項目値指定ポインタ配列ＬＶＬ’及びレコード順序番号配列ＧＯｒｄ’には、各ブロック内のレコードが属するブロック番号を表すブロック番号配列ＢｌｋＮｏ’が後の処理のため追加される。【００９０】
図１１は、このようにして得られた、本発明の一実施形態による表形式データのソート処理におけるブロック内ソート処理の結果の説明図である。この時点で、各ブロック内の項目値アクセス情報配列ＬＯｒｄは最終的な結果と一致しているので、ＬＯｒｄのようにプライム記号（’）無しで示されている。一方、項目値指定ポインタ配列ＬＶＬ’及びレコード順序番号配列ＧＯｒｄ’は最終的な結果ではなく、処理途中の作業用配列を表しているので、プライム記号（’）付きで示されている。さらに、最終的な結果であるブロック番号配列ＢｌｋＮｏ及びレコード順序番号配列ＧＯｒｄは、この時点では未だ決定されていないのでブランクのまま残されている。【００９１】
図１２Ａ乃至１２Ｃは本発明の一実施形態による表形式データのソート処理におけるブロック間ソート処理１（マージ処理）の階層構造を説明する図である。同図の例では、たとえば、少なくとも７台の演算ユニットＳＰＵ−０、ＳＰＵ−１、・・・、ＳＰＵ−６が、Ｂｌｏｃｋ０からブロック１２７までの１２８ブロックのソート処理を実行している。【００９２】
図１２Ａの１回目の処理は、ブロックＢｌｏｃｋ−０からブロックＢｌｏｃｋ−７までのソート処理と、ブロックＢｌｏｃｋ−８からブロックＢｌｏｃｋ−１５までのソート処理と、以下同様に、ブロックＢｌｏｃｋ−１２０からブロックＢｌｏｃｋ−１２７までのソート処理の１６回のソート処理、すなわち、８個のブロック間のソート処理を１６回に亘って逐次的に実行する。たとえば、１段目では、ＳＰＵ−０がブロックＢｌｏｃｋ−０とブロックＢｌｏｃｋ−１に所定の順序のマージ処理を適用してブロック０〜１を出力し、ＳＰＵ−１がブロックＢｌｏｃｋ−２とブロックＢｌｏｃｋ−３に所定の順序のマージ処理を適用してブロック２〜３を出力する。ここで、ブロック０〜１のようなブロックＡ〜Ｂという表記は、ブロックＡからブロックＢまでに所定の順序のマージ処理を適用した結果として得られるブロックに関するデータ（より詳細には、作業用の項目値指定ポインタ配列、作業用のレコード順序番号配列、及び、作業用のブロック番号配列）を表している。次に、２段目において、ＳＰＵ−４がＳＰＵ−０によって所定の順序のマージ処理されたブロック０〜１と、ＳＰＵ−１によって所定の順序のマージ処理されたブロック２〜３とに所定の順序のマージ処理を適用して、ブロック０〜３を出力する。同様に、ＳＰＵ−４はブロック４〜７を出力する。３段目のＳＰＵ−６は、ＳＰＵ−４によって出力されたブロック０〜３と、ＳＰＵ−５によって出力されたブロック４〜７とに所定の順序のマージ処理を適用して、ブロック０〜７を出力する。このような３段目のマージ処理が、さらに繰り返し実行されることによって、ブロック０〜７、ブロック８〜１５、・・・、ブロック１２０〜１２７の１６個のブロックが出力される。尚、図中、白抜きの矢印は、グローバルメモリと演算ユニット内のローカルメモリとの間の入出力を表し、黒色の矢印は、チップ内バスを経由する演算ユニット内のローカルメモリ間のデータ転送を表している。【００９３】
図１２Ｂの２回目の処理は、１回目の処理によって出力された１６個のブロックのうち、ブロック０〜７、・・・、ブロック５６〜６３の８個のブロックに所定の順序のマージ処理を適用して、ブロック０〜６３を出力し、ブロック６４〜７１、・・・、ブロック１２０〜１２７の８個のブロックに所定の順序のマージ処理を適用して、ブロック６４〜１２７を出力する。【００９４】
さらに、図１２Ｃの３回目の処理では、ＳＰＵ−０が、ブロック０〜６３とブロック６４〜１２７に所定の順序のマージ処理を適用して、最終的な１個のブロック０〜１２７を出力する。【００９５】
ブロック間ソート処理１（すなわち、マージ処理）では、各演算ユニットが、１対のブロックに関する情報をマージして、マージされたより高い層の１個のブロックに関する情報を生成する。よって、マージ処理は、複数台の演算ユニットの並列動作によって実現される。また、各演算ユニットは、同じ層に属するマージされたよりブロックの対に関する情報をマージし、マージされたさらに高い層の１個のブロックに関する情報を生成する。このようにマージ処理を並列的かつ階層的に繰り返すことにより、最終的に最上層の１個のブロックに関する情報が生成される。最上層の１個のブロックとは、レコード全体を含むブロックである。【００９６】
たとえば、２ｎ−１台の演算ユニットが存在し、各演算ユニットが２個のブロックに関する情報を入力し、それらをマージして、１個のブロックに関する情報を出力すると仮定すると、各演算ユニットが１回ずつマージ処理を実行することによって、ｎ段（層）のマージ処理が実現される。この場合、全演算プロセッサによる全データ通信量のうち、演算プロセッサがグローバルメモリとの間で行う通信が占める割合は、１／ｎである。演算ユニット間の通信量は、全データ通信量の（ｎ−１）／ｎである。【００９７】
続いて、本発明の一実施形態による表形式データのソート処理におけるブロック間ソート処理１（ブロック間マージ処理）をより詳細に説明する。図１３Ａ乃至１３Ｃは、本発明の一実施形態による表形式データのソート処理における１段目のブロック間マージ処理の説明図である。本例では、ＳＰＵ−０がブロックＢｌｏｃｋ−０（以下、ブロック０）とブロックＢｌｏｃｋ−１（ブロック１）との間で所定の順序のマージ処理を実行する。ブロック間マージ処理は、２つの昇順リストから１つの昇順リストを生成するという点で昇順リストのマージ処理である。最初に、ＳＰＵ−０は、ブロック０及びブロック１に関する項目値指定ポインタ配列ＬＶＬ’、レコード順序番号配列ＧＯｒｄ’、及び、ブロック番号配列ＢｌｋＮｏ’をグローバルメモリからローカルメモリへ転送する。但し、全体を一度にグローバルメモリへ転送できないときには、グローバルメモリからローカルメモリへ少しずつ転送される。【００９８】
図１３Ａには、ブロック０内の１番目のレコードに関する情報（Ｂ０（ＬＶＬ’，ＧＯｒｄ’）のように表す）とブロック１内の１番目のレコードに関する情報（Ｂ１（ＬＶＬ’，ＧＯｒｄ’）のように表す）とを比較する処理が示されている。このとき、ブロック０側の読み出しポインタとブロック１側の読み出しポインタは共にデータの先頭に位置している。ＬＶＬ’を上位の桁、ＧＯｒｄ’を下位の桁とみなして、ブロック０側及びブロック１側からの（ＬＶＬ’，ＧＯｒｄ’）を所定の順番（たとえば、昇順）に並べる。本例では、
Ｂ０（ＬＶＬ’，ＧＯｒｄ’）＝（２，１）＞Ｂ１（ＬＶＬ’，ＧＯｒｄ’）＝（１，５）
であるので、Ｂ１（ＬＶＬ’，ＧＯｒｄ’）が先頭（最も小さい）要素であることが判定される。よって、ブロック番号を含めた要素の組Ｂ１（１，５，１）がマージ処理の結果として取り出される。このマージ処理の結果は、
ＬＶＬ’［０］＝１
ＧＯｒｄ’［０］＝５
ＢｌｋＮｏ’［０］＝１
のように記述できる。これにより、ブロック１側のデータが取り出されたので、ブロック１側の読み出しポインタが１つ先へ進められる。【００９９】
図１３Ｂでは、読み出しポインタが先頭に位置しているブロック０内の１番目のレコードと、読み出しポインタが１つ先へ進められたブロック１内の２番目のレコードとを比較する処理が示されている。同様に、Ｂ０（２，１）とＢ１（２，４）とを比較すると、Ｂ０（２，１）の方が小さいと判定されるので、ブロック番号を含めた要素の組Ｂ０（２，１，０）がマージ処理の結果、すなわち、
ＬＶＬ’［１］＝２
ＧＯｒｄ’［１］＝１
ＢｌｋＮｏ’［１］＝０
として取り出される。これにより、ブロック０側のデータが取り出されたので、ブロック０側の読み出しポインタが１つ先へ進められる。【０１００】
このように、ポインタを進めながら、ブロック０側のデータとブロック１側のデータを順次比較することにより、最終的に、ブロック０側のデータとブロック１側のデータがマージされた昇順のリストが得られる。図１３Ｃには、最終的に取り出された項目値指定ポインタ配列ＬＶＬ’とレコード順序番号配列ＧＯｒｄ’とブロック番号配列ＢｌｋＮｏ’とが示されている。【０１０１】
なお、取り出された項目値指定ポインタ配列ＬＶＬ’とレコード順序番号配列ＧＯｒｄ’とブロック番号配列ＢｌｋＮｏ’は、２段目のマージ処理のため、本例では、ＳＰＵ−４へ送出されるが、最終的な結果を一括して送出するのではなく、ブロック０側とブロック１側の比較処理を進めながら、取り出されたデータを必要に応じて、ＳＰＵ−０からＳＰＵ−４へ送出してもよい。【０１０２】
以上の説明からわかるように、本発明の一実施形態によるブロック間ソート処理１（マージ処理）の１段目の処理では、データアクセスがシーケンシャルアクセスだけに限定され、かつ、各ＳＰＵが並列にブロック間ソート処理１を実行可能である。よって、マルチプロセッサ型処理装置の性能が十分に活かされている。【０１０３】
今度は、演算ユニットＳＰＵ−４が、ＳＰＵ−０から出力されたブロック０〜１と、ＳＰＵ−１１から出力されたブロック２〜３に所定の順序のマージ処理を適用し、１つのブロック０〜３を出力する２段目のブロック間ソート処理１について説明する。図１４Ａ及び１４Ｂは、本発明の一実施形態による表形式データのソート処理における２段目のマージ処理の説明図である。２段目のマージ処理は、入力される情報が他の演算ユニットのローカルメモリから転送される点を除いて、１段目のマージ処理と同様である。この処理を簡単に説明すると、図１４Ａに示されているように、最初、２つのブロックからの項目値指定ポインタ配列ＬＶＬ’、レコード順序番号配列ＧＯｒｄ’、及び、ブロック番号配列ＢｌｋＮｏ’の読み出し用ポインタが先頭に設定される。両方の（ＬＶＬ’，ＧＯｒｄ’）の組の値を比較すると、
Ｂ０〜１（ＬＶＬ’，ＧＯｒｄ’）＝（１，５）＞Ｂ２〜３（ＬＶＬ’，ＧＯｒｄ’）＝（０，８）
であることから、Ｂ２〜３側の要素の方が小さいということがわかる。よって、Ｂ２〜３側の先頭の要素の組であるＢ２〜３（０，８，２）を取り出す。そして、要素の組が取り出された方のＢ２〜３側の読み出しポインタを１つ先へ進められる。ここで、Ｂａ〜ｂという表記は、ブロックａからブロックｂまでの間の所定の順序のマージ処理の結果として得られたデータを表している。【０１０４】
このような要素の組の大小比較と、小さい方の要素の組の読み出しを繰り返すことにより、図１４Ｂに示されているように、最後にＢ２〜３側の要素の組であるＢ２〜３（３，１３，３）が取り出され、２段目のマージ処理が終了する。【０１０５】
なお、取り出された項目値指定ポインタ配列ＬＶＬ’とレコード順序番号配列ＧＯｒｄ’とブロック番号配列ＢｌｋＮｏ’は、３段目のマージ処理のため、本例では、ＳＰＵ−６へ送出されるが、最終的な結果を一括して送出するのではなく、ブロック０側とブロック１側の比較処理を進めながら、取り出されたデータを必要に応じて、ＳＰＵ−４からＳＰＵ−６へ送出してもよい。また、以上の説明からわかるように、本発明の一実施形態によるブロック間ソート処理１（マージ処理）の２段目の処理では、データアクセスがシーケンシャルアクセスだけに限定され、かつ、各ＳＰＵが並列にブロック間ソート処理１を実行可能である。よって、マルチプロセッサ型処理装置の性能が十分に活かされている。【０１０６】
２段目のマージ処理は、本例では、ＳＰＵ−４とＳＰＵ−５によって並列に実行されている。ＳＰＵ−４は、ブロック０からブロック３までのブロック間マージ処理の結果をブロック０〜３としてＳＰＵ−６へ出力し、ＳＰＵ−５は、ブロック４からブロック７までのブロック間マージ処理の結果をブロック４〜７としてＳＰＵ−６へ出力する。本例では、ブロックの総数は、ブロック０からブロック７までの８ブロックであるため、ＳＰＵ−６による３段目のマージ処理によって、全てのブロックからのデータのマージが終了し、すなわち、全てのブロックを考慮したソート処理が終了する。当業者によって理解されるように、ブロック数が９個以上ある場合には、たとえば、図１２Ａ乃至１２Ｃに示されるように、マージ処理の段数を増加させることにより、最終的に全てのブロックからのデータがマージされたソート処理結果を得ることが可能である。【０１０７】
図１５は、本発明の一実施形態による表形式データのソート処理における３段目のマージ処理の説明図である。３段目のマージ処理もまた、１段目のマージ処理及び２段目のマージ処理と同様に、Ｂ０〜３側のデータＢ０〜３（ＬＶＬ’，ＧＯｒｄ’）とＢ４〜７側のデータＢ０〜４（ＬＶＬ’，ＧＯｒｄ’）を先頭から順番に比較し、小さい方の要素の組を取り出し、要素が取り出された側のデータの読み出し用ポインタを１つ先へ進める、という操作を繰り返す。これにより、図１５の右側に示されているような配列の組、すなわち、項目値指定ポインタ配列ＬＶＬ’、レコード順序番号配列ＧＯｒｄ’、及び、ブロック番号配列ＢｌｋＮｏ’の組が得られる。この配列の組は、全レコードのソート結果を表現している。たとえば、項目値指定ポインタ配列ＬＶＬ’を参照すると、先頭から、同一値を含めて値が昇順に並べられているので、グローバル項目値配列中の項目値の整列順にレコードがソートされていることがわかる。また、項目値指定ポインタ配列ＬＶＬ’の要素の値が同一であるレコードは、レコード順序番号配列ＧＯｒｄ’を参照することにより、ソート前のレコード順序番号の昇順に整列されていることもわかる。このように、レコード順序番号に関して安定性のあるソート結果が得られた理由は、ブロック間ソートの際に、項目値指定ポインタとレコード順序番号の組に関する大小関係に基づいてレコードの並べ替えが行われたからである。【０１０８】
本発明の一実施形態による表形式データのソート処理におけるブロック間ソート処理１（マージ処理）によって得られた３つの配列から次のことがわかる。たとえば、配列の組の１行目のデータ＝（０，８，２）を参照すると、ソート後にレコード順序番号０が付与されるレコードは、
（１）ソートのキーとなるデータ項目に関する項目値を指定する項目値指定ポインタの値が０であり、
（２）ソート前に付与されていたレコード順序番号が８であり、
（３）ブロック２に属している。【０１０９】
発明の理解を助けるため、このブロック間ソート処理1（マージ処理）の結果がマルチコア型処理装置向けのデータ構造で表現される。図１６Ａ乃至１６Ｃは、本発明の一実施形態による表形式データのソート処理におけるブロック間ソート処理１（マージ処理）の結果の説明図である。図１６Ａ乃至１６Ｃに示された表形式データは図７Ｂ乃至７Ｄに示された表形式データと類似しているが、この時点では、図１６Ａに示されているレコード順序番号配列ＧＯｒｄに格納されるべき値が未定である。一方、図１６Ｂ及び図１６Ｃに示されている項目値情報は、ソート処理による影響を受けないので、当然に同じである。【０１１０】
本発明の一実施形態による表形式データのソート処理では、最後に、各ブロックに属するレコードのレコード順序番号を決定する。このレコード順序番号を決定する処理は、ブロック間ソート処理２（分配処理）と呼ばれる。分配処理では、複数台の演算ユニットが並列的に動作して、ブロック番号配列ＢｌｋＮｏの添字ｉに相当するレコード順序番号をブロック番号ＢｌｋＮｏ［ｉ］で表されるブロック毎に分配し、分配されたレコード順序番号をブロック内で所定の順番（たとえば、昇順）に並べる。この処理は、たとえば、ブロックｊのレコード順序番号配列のｋ番目の要素をＧＯｒｄ［ｊ］［ｋ］とし、レコード順序番号配列ＧＯｒｄ［ｊ］にレコード順序番号を設定するための書き込み用ポインタｋをｉｎｄｅｘ［ｊ］とすると、次のように記述できる。
インデックス配列ｉｎｄｅｘを初期化；
ｆｏｒ  （ｉ＝０；ｉ＜レコード総数；ｉ＋＋）  ｛
ＧＯｒｄ［ＢｌｋＮｏ［ｉ］］［ｉｎｄｅｘ［ＢｌｋＮｏ［ｉ］］＝ｉ；
ｉｎｄｅｘ［ＢｌｋＮｏ［ｉ］］＋＋；
｝
但し、実際には、複数台の演算ユニットがブロック番号配列ＢｌｋＮｏの一部を分担して分配処理を行う。そのため、あるブロックに関するレコード順序番号配列ＧＯｒｄ［ｊ］は複数台の演算ユニットによって分担して処理される。そして、複数の演算ユニットによって分担して作成されたレコード順序番号配列がブロック毎に１つのレコード順序番号配列に統合される。ブロック番号配列ＢｌｋＮｏの複数台の演算ユニットへの割り当てが連続的に行われるならば、すなわち、各演算ユニットが担当するブロック番号配列ＢｌｋＮｏの一部が連続しているならば、この統合処理は非常に簡単化される。なぜならば、同一のブロックに関して、別々の演算ユニットによって作成されたレコード順序番号配列の間で要素の順番を入れ替える必要がないからである。つまり、レコード順序番号配列の統合処理は、別々に作成されたレコード順序番号配列を単に連結することにより達成される。【０１１１】
図１７Ａ乃至１７Ｃは、本発明の一実施形態による表形式データのソート処理におけるブロック間ソート処理２（分配処理）の説明図である。図１７Ａを参照すると、ブロック番号配列ＢｌｋＮｏは、先頭から順番にＳＰＵ−０、ＳＰＵ−１、・・・、ＳＰＵ−７の８台の演算ユニットに４個ずつの要素が割り当てられている。図１７Ａでは、各演算ユニットが、並列的に、自分の担当するブロック番号配列ＢｌｋＮｏの添字ｉ（＝レコード順序番号）と要素ＢｌｋＮｏ［ｉ］（＝ブロック番号）とに応じて、レコード順序番号をブロック番号毎に分配している。たとえば、ＳＰＵ−０は、担当するデータＢｌｋＮｏ［０］＝２に応じて、ブロック番号２のためのレコード順序番号配列ＧＯｒｄ−２の先頭にレコード順序番号＝０を書き込む。すなわち、ＧＯｒｄ−２［０］＝０である。なお、各演算ユニットは、ブロック番号配列中の自分の担当する範囲のデータと、レコード順序番号配列ＧＯｒｄ−０、ＧＯｒｄ−１、・・・、ＧＯｒｄ−７をローカルメモリ上に作成して、分配処理を行う。【０１１２】
各演算ユニットは、自分の担当する範囲内の４個のデータについて順次分配処理を行う。図１７Ｂは、各演算ユニットが自分の担当する範囲内の４個目のデータを分配したときの状態を示している。たとえば、ＳＰＵ−７は、ＢｌｋＮｏ［３１］＝７に応じて、ＧＯｒｄ−７［１］に３１を設定する。【０１１３】
本例では、演算ユニット毎に、ブロック０からブロック７までの配列ＧＯｒｄ−０からＧＯｒｄ−７が使用されている。この場合、演算ユニットの台数（＝８個）倍の作業領域がローカルメモリとグローバルメモリに確保されることになる。この作業領域をコンパクトにするため、リンクリストを使用しても構わない。重要なことは、作業領域がローカルメモリに格納できる間は、その作業領域をローカルメモリに収容し、作業領域がローカルメモリに収容できなくことが分かった時点で、ローカルメモリ中の作業領域の全部又は一部をある程度まとめてグローバルメモリへ転送することによって、グローバルメモリへのメモリアクセスを一括化することが可能である。【０１１４】
最後に、各演算ユニットによって作成されたブロック毎のレコード順序番号配列が統合された最終的なレコード順序番号配列が作成される。具体的には、レコード順序番号の小さい順に、すなわち、ＳＰＵ−０からＳＰＵ−７の順に、ＧＯｒｄ−０、ＧＯｒｄ−１、・・・、ＧＯｒｄ−７のそれぞれに格納されている値を取り出し、その値を最終的なＧＯｒｄ−０、ＧＯｒｄ−１、・・・、ＧＯｒｄ−７の先頭から順に格納すればよい。この操作は、たとえば、いずれか１台の演算ユニット、又は、制御ユニットが実行可能であるが、ブロック番号毎に、複数台の演算ユニットが並列的に、ＧＯｒｄ−０等から値を取り出し、最終的なＧＯｒｄ−０等へ書き込むようにしてもよい。【０１１５】
このようにして得られたＧＯｒｄ−０はブロック０に属するレコードに付与されるレコード順序番号であり、ＧＯｒｄ−１はブロック１に属するレコードに付与されるレコード順序番号であり、以下同様である。図１８は、本発明の一実施形態による表形式データのソート処理の結果の説明図である。図１７Ｃで得られたレコード順序番号配列が各ブロックのレコード順序番号配列と一致していることがわかる。【０１１６】
［表形式データのソート処理のまとめ］
上述の本発明の一実施形態による表形式データのソート方法を、図１９に示されたフローチャートを参照してもう一度全体的に説明する。【０１１７】
表形式データのソート方法は、
上記複数台の演算ユニットが並列的に動作して、上記担当レコードを含むブロック毎に、上記項目値情報をキーとして用いて、上記項目値アクセス情報配列にソートを適用し、これによって、ソートされた項目値アクセス情報配列と、上記ソートされた項目値アクセス情報配列に対応する作業用項目値情報配列及び作業用レコード順序番号配列を上記グローバルメモリに作成するステップ１９０２と、
上記複数台の演算ユニットが並列的に動作して、１対のブロックに関する上記作業用項目値情報配列からの第１の要素及び対応する上記作業用レコード順序番号配列からの第２の要素からなる要素の組を、上記第１の要素を上位の桁及び上記第２の要素を下位の桁として用いて、所定の順序にマージし、マージされた要素の組に当該要素の組が含まれる上記ブロック番号を関連付け、これによって、上記１対のブロックに関する新たな作業用項目値情報配列、新たな作業用レコード順序番号配列、及び、新たなブロック番号配列を作成するステップ１９０４と、
上記複数台の演算ユニットが並列的かつ階層的に動作して、上記ステップ(ii)を繰り返し実行し、これによって、１組の最終的な作業用項目値情報配列、最終的な作業用レコード順序番号配列、及び、最終的なブロック番号配列を上記グローバルメモリに作成するステップ１９０６と、
上記複数台の演算ユニットが並列的に動作して、上記最終的なブロック番号配列中の要素が格納されているレコード順序番号を当該要素によって指定されたブロック番号毎に分配し所定の順番に並べ、これによって、ソートされたレコード順序番号配列を上記グローバルメモリに作成するステップ１９０８と、
を備えている。【０１１８】
そして、上記項目値情報が、データ項目毎に、一意の項目値が所定の順序に格納されているグローバル項目値配列と、データ項目毎に、上記担当レコードに含まれる項目値を特定するローカル項目値番号が上記レコード順序番号の順番に格納されているローカル項目値番号配列と、データ項目毎に、上記ローカル項目値番号によって表される項目値が上記グローバル項目値配列中に格納されている位置を指定する項目値指定ポインタが所定の順番に格納されている項目値指定ポインタ配列とを備えている場合、上記ステップ(i)において適用されるソートが分布数え上げソートであり、上記作業用項目値情報配列が作業用項目値指定ポインタ配列である。【０１１９】
さらに、上記ステップ１９０２は、
上記複数台の演算ユニットが並列的に動作して、上記担当レコードを含むブロックに対応している、上記レコード順序番号配列及び上記項目値アクセス情報配列と、上記所定の項目に関する上記ローカル項目値番号配列及び上記項目値指定ポインタ配列とを、上記グローバルメモリから上記ローカルメモリへ転送するステップと、
上記複数台の演算ユニットが並列的に動作して、上記ローカルメモリに作成された上記ソートされた項目値アクセス情報配列と、上記作業用項目値指定ポインタ配列及び上記作業用レコード順序番号配列とを上記グローバルメモリへ転送するステップと、
をさらに含む。また、上記ステップ１９０４は、
上記複数台の演算ユニットが並列的に動作して、１対のブロックに関する上記作業用項目値指定ポインタ配列及び上記作業用レコード順序番号配列を、上記グローバルメモリから上記ローカルメモリへ転送するステップと、
上記複数台の演算ユニットが並列的に動作して、上記ローカルメモリに作成された上記作業用項目値指定ポインタ配列、上記作業用レコード順序番号配列、及び、上記新たなブロック番号配列を上記グローバルメモリ又はさらなる処理のための演算ユニットへ転送するステップと、
を含む。さらに、上記ステップ１９０６は、上記ローカルメモリに作成された上記最終的なブロック番号配列を上記グローバルメモリへ転送するステップを含む。【０１２０】
［代替的な分配処理］
図１７Ａ乃至１７Ｃに示された分配処理の例では、ブロック数が増加すると、ローカルメモリ上の作業領域も増大する。そのため、本発明の代替的な実施形態では、特に、ブロック数が多い場合に、処理を効率化するために、複数のブロックをグループ化した後に、グループ毎に分配処理を実施する。たとえば、ブロック番号を４で除算することにより、上位ブロック番号と、下位ブロック番号に分離し（グループ化し）、上位ブロック番号と下位ブロック番号に関して別々に分配処理を適用する。具体的には、ブロック間ソート処理２におけるマージ処理によって得られたブロック番号配列ＢｌｋＮｏ’から、下位ブロック番号用のブロック番号配列ＢｌｋＮｏ’と上位ブロック番号用のブロック番号作業配列ＢｌｋＮｏ’とを生成する。この生成処理もまた、複数台の演算ユニットが並列的に動作して、実行可能である。【０１２１】
たとえば、図１６Ａ乃至１６Ｃに示されたブロック番号配列ＢｌｋＮｏを下位のブロック番号（すなわち、０から３）と上位のブロック番号（すなわち、４から７）に分離すると、２つのブロック番号配列が生成される。図２０は、本発明の代替的な実施形態によるブロック番号配列の分離処理の説明図である。このようにして得られた、下位ブロック番号用のＢｌｋＮｏ’及びＬＶＬ’と、上位ブロック番号用のＢｌｋＮｏ’及びＬＶＬ’は、図１７Ａ乃至１７Ｃを参照して説明した、本発明の一実施形態によるブロック間ソート処理における分配処理が適用され、ブロック番号毎にレコード順序番号が得られる。【０１２２】
［表形式データの多項目ソート処理］
本発明の一実施形態による表形式データのソート処理は、所定のデータ項目に関するソート処理である。このソート処理によって変化するのは、ブロック番号配列、レコード順序番号配列及び項目値アクセス情報配列である。一方、各ブロックに属するレコード、及び、項目値情報は変化しない。よって、複数のデータ項目に関するソート処理は、上述の所定のデータ項目に関するソート処理を繰り返すことによって実現される。本発明のマルチコア型処理装置の好ましい一実施形態によれば、多項目ソート処理は、制御ユニットが、複数のデータ項目に関してソート処理を繰り返すように演算ユニットを制御することによって実現される。【０１２３】
よって、たとえば、図５Ａに示された表形式データに対して、最初に、データ項目＝「Ｓｃｈｏｏｌ」に関してソート処理を実行し、次に、データ項目＝「Ａｇｅ」に関してソート処理を実行する場合（多段階ソート処理）、図１０Ａ乃至１０Ｃから図１８を参照して説明したソート処理によってデータ項目＝「Ｓｃｈｏｏｌ」に関するソートを行い、続いて、同様に、図１８に示されたレコード順序番号配列及び項目値アクセス情報配列から始めて、データ項目＝「Ａｇｅ」に関するソート処理を実行すればよい。なお、複数のデータ項目に関してソート処理を順次適用する場合、優先度の高いデータ項目に関するソート処理が後から適用される。【０１２４】
図２１は、図５Ａに示された表形式データに対して本発明の一実施形態による多段階ソート処理を適用した結果を示す図である。図２１Ａでは、最初にデータ項目＝「Ｓｃｈｏｏｌ」に関するソート処理が適用され、その後に、データ項目＝「Ａｇｅ」に関するソート処理が適用されている。一方、図２１Ｂでは、最初にデータ項目＝「Ａｇｅ」に関するソートが適用され、その後に、データ項目＝「Ｓｃｈｏｏｌ」に関するソートが適用されている。このように、ソートが適用されるデータ項目の順序に応じてソート処理の結果が異なる。また、本発明の一実施形態による多段階ソート処理が安定性のあるソートであることもわかる。【０１２５】
或いは、代替的な実施形態では、多項目ソート処理を１段階で実現することも可能である。これば、上記の実施形態におけるブロック内ソート処理で実行される分布数え上げソート処理を複数のデータ項目を併合して実行することにより実現される。たとえば、図５Ａの表形式データの例において、データ項目＝「Ｓｃｈｏｏｌ」を優先度の低いデータ項目とし、データ項目＝「Ａｇｅ」を優先度の高いデータ項目として、多項目ソート処理を実施する場合を考える。データ項目＝「Ｓｃｈｏｏｌ」の項目値指定ポインタの値Ｘとデータ項目＝「Ａｇｅ」の項目値指定ポインタの値Ｙとを組み合わせて生成される値Ｚを新たな項目値とみなしてソート処理を実行すればよい。本例では、Ｘの値の取り得る範囲が０≦Ｘ≦３の４通りであり、かつ、Ｙの値の取り得る範囲が０≦Ｙ≦６の７通りであるので、２つの項目値の組み合わせに対して、４×７＝２８の値、すなわち、０から２７までの値を割り付ける。より具体的には、データ項目＝「Ａｇｅ」が優先度の高いデータ項目であることから、
Ｚ＝４×Ｙ＋Ｘ
という値Ｚを新たな項目値とみなして、ソート処理を実行すればよい。【０１２６】
実際的には、新たな項目値をもつ新たな表形式データを作成する必要はなく、分布数え上げソート処理のキー値Ｚとして、データ項目＝「Ｓｃｈｏｏｌ」の項目値指定ポインタの値Ｘとデータ項目＝「Ａｇｅ」の項目値指定ポインタＹの値を組み合わせた値Ｚ＝４×Ｙ＋Ｘを使用すればよい。そして、この新しい項目値指定ポインタＺを用いて、ブロック内ソート処理、ブロック間ソート処理１（マージ処理）、及び、ブロック間ソート処理２（分配処理）を実行することにより、データ項目毎にソート処理を実行する場合と同じ結果を得ることができる。【０１２７】
［表形式データの別のデータ構造］
ここまでの説明では、第１のタイプの項目値情報を使用する場合について、本発明による表形式データのソート処理を説明しているが、既に説明しているように、本発明による表形式データのソート処理は、表形式データのデータ構造が第２のタイプの項目値情報を保持する場合にも適用可能である。図２２Ａ乃至２２Ｄは、図５Ａの表形式データと同一の表形式データを記述する、本発明の一実施形態による表形式データのデータ構造の説明図である。図２２Ａは表形式データを概念的に説明する図、図２２Ｂは表形式データのデータ構造中の順序情報を示す図である。図２２Ｃには、データ項目＝「Ｓｃｈｏｏｌ」に関する項目値情報が示され、図２２Ｄには、データ項目＝「Ａｇｅ」に関する項目値情報が示されている。本実施形態では、項目値情報は項目値自体である。本実施形態においても、項目値情報は、ソート処理の前後で変化しない。以下では、このような表形式データに対して、データ項目＝「Ｓｃｈｏｏｌ」の項目値をキー値として用いるソート処理を説明する。【０１２８】
［表形式データのソート処理（第２のタイプの項目値情報）］
第１のタイプの項目値情報を用いる表形式データのソート処理と第２のタイプの項目値情報を用いる表形式データのソート処理との相違点は以下の通りである。第１のタイプの項目値情報を用いるソート処理では、ローカル項目値番号をキー値としてブロック内で分布数え上げソート処理を実行して項目値アクセス情報を並べ替え、その後に、項目値指定ポインタの値とレコード順序番号の組をキー値として用いてブロック間ソート処理を行った。これに対して、第２のタイプの項目値情報を用いるソート処理では、項目値をキー値としてブロック内で安定性のあるソート処理を実行して項目値アクセス情報を並べ替え、その後に、項目値とレコード順序番号の組をキー値として用いてブロック間ソートを実行する。【０１２９】
図２３は、第２のタイプの項目値情報を含む表形式データのソート処理の概略的なフローチャートである。【０１３０】
ステップ２３０１：ブロック内ソート
各演算ユニットが並列的に動作して、それぞれのブロック内で、項目値配列ＲＶ中の項目値をキー値として、項目値アクセス情報配列ＬＯｒｄに安定性のあるソート（たとえば、マージソート、バブルソートなど）を適用し、ソートされた項目値アクセス情報配列ＬＯｒｄ’に適合するように項目値配列ＲＶ’及びレコード順序番号配列ＧＯｒｄ’を生成する。【０１３１】
ステップ２３０２：ブロック間ソート１（マージ）
各演算ユニットが並列的かつ階層的に動作して、項目値配列ＲＶ’及びレコード順序番号配列ＧＯｒｄ’からブロック番号配列ＢｌｋＮｏを生成する。ここでは、ブロック間で、それぞれのブロックからの項目値配列ＲＶ’、レコード順序番号配列ＧＯｒｄ’及びブロック番号配列ＢｌｋＮｏ’がトーナメント方式でマージされる。【０１３２】
ステップ２３０３：ブロック間ソート２（分配）
各演算ユニットが並列的に動作して、ブロック番号配列ＢｌｋＮｏからレコード順序番号配列ＧＯｒｄを生成する。【０１３３】
図２４Ａ乃至２４Ｈは、本発明の一実施形態による表形式データのソート処理におけるブロック内ソート処理の説明図である。図２４Ａから図２４Ｈには、それぞれ、ブロック０からブロック７におけるブロック内ソート処理の様子が示されている。本例では、ＳＰＵ−０からＳＰＵ−７までの７台の演算ユニットがそれぞれブロック０からブロック７までの各ブロック内のブロック内ソート処理を担当する。本実施形態においても、各演算ユニットは、処理に必要なデータをグローバルメモリから専用のローカルメモリへ転送し、ローカルメモリ内でデータを操作する。全てのデータを同時にローカルメモリに収容できないときには、ある程度のまとまり毎に、グローバルメモリとローカルメモリとの間でデータ転送を行って処理を行う。【０１３４】
たとえば、図２４Ａを参照すると、本例では、ＲＶの要素の値は文字列であるため、ＬＯｒｄは、ＲＶの値をキー値として、キー値のアルファベット順にソートされる。また、マージソート又はバブルソートのような安定性のあるソートアルゴリズムが使用されるので、配列ＬＯｒｄ＝（０，１，２，３）は、配列ＬＯｒｄ’＝（１，３，０，２）のように並べ替えられる。なお、配列Ａ＝（ａ，ｂ，ｃ，ｄ）は、配列Ａの要素が先頭から順に、ａ，ｂ，ｃ，ｄであることを表している。配列ＬＯｒｄの要素の値０、１、２、３に対して、それぞれ、項目値配列ＲＶの要素“Ｗｅｓｔ”、“Ｓｏｕｔｈ”、“Ｗｅｓｔ”、“Ｓｏｕｔｈ”が対応しているので、項目値をキー値として配列ＬＯｒｄの要素を並べ替えると、配列ＬＯｒｄ’が得られることは明らかである。ここで、ＬＯｒｄ’の要素の順に、対応する項目値配列ＲＶの要素とレコード順序番号配列ＧＯｒｄの要素を取り出すと、項目値配列ＲＶ’及びレコード順序番号配列ＧＯｒｄ’が得られる。項目値配列ＲＶ’は、当然、項目値が昇順（アルファベット順）にソートされた配列である。また、レコード順序番号配列ＧＯｒｄ’の要素は、項目値が同一値である場合に、先に出現したＬＯｒｄ値が優先されるような順番にソートされている。すなわち、項目値とレコード順序番号の組は、安定したソートによって並び替えられている。その他のブロック１からブロック７に関しても同様の処理が行われる。【０１３５】
図２５は、このようにして得られた、本発明の一実施形態による表形式データのソート処理におけるブロック内ソート処理の結果の説明図である。この時点で、各ブロック内の項目値アクセス情報配列ＬＯｒｄは最終的な結果と一致しているので、ＬＯｒｄのようにプライム記号（’）無しで示されている。一方、項目値配列ＲＶ’及びレコード順序番号配列ＧＯｒｄ’は最終的な結果ではなく、処理途中の作業用配列を表しているので、プライム記号（’）付きで示されている。さらに、最終的な結果であるブロック番号配列ＢｌｋＮｏ及びレコード順序番号配列ＧＯｒｄは、この時点では未だ決定されていないのでブランクのまま残されている。また、ブロック内ソートの結果である配列ＲＶ’及び配列ＧＯｒｄ’に、ブロック番号ＢｌｋＮｏ’が付加されている。【０１３６】
本発明の一実施形態による表形式データのソート処理におけるブロック間ソート処理１（マージ処理）は、図１２Ａ乃至１２Ｃを参照して説明したように、並列的かつ階層的に実行される。【０１３７】
続いて、本発明の一実施形態による表形式データのソート処理におけるブロック間ソート処理１（ブロック間マージ処理）をより詳細に説明する。図２６Ａ乃至２６Ｃは、本発明の一実施形態による表形式データのソート処理における１段目のブロック間マージ処理の説明図である。本例では、ＳＰＵ−０がブロックＢｌｏｃｋ−０（以下、ブロック０）とブロックＢｌｏｃｋ−１（ブロック１）との間で所定の順序のマージ処理を実行する。ブロック間ソート処理は、２つの昇順リストから１つの昇順リストを生成するという点で昇順リストのマージ処理である。最初に、ＳＰＵ−０は、ブロック０及びブロック１に関する項目値配列ＲＶ’、レコード順序番号配列ＧＯｒｄ’、及び、ブロック番号配列ＢｌｋＮｏ’をグローバルメモリからローカルメモリへ転送する。但し、全体を一度にグローバルメモリへ転送できないときには、グローバルメモリからローカルメモリへ少しずつ転送される。【０１３８】
図２６Ａには、ブロック０内の１番目のレコードに関する情報（Ｂ０（ＲＶ’，ＧＯｒｄ’）のように表す）とブロック１内の１番目のレコードに関する情報（Ｂ１（ＲＶ’，ＧＯｒｄ’）のように表す）とを比較する処理が示されている。このとき、ブロック０側の読み出しポインタとブロック１側の読み出しポインタは共にデータの先頭に位置している。ＲＶ’を上位の桁、ＧＯｒｄ’を下位の桁とみなして、ブロック０側及びブロック１側からの（ＲＶ’，ＧＯｒｄ’）を所定の順番（たとえば、昇順）に並べる。本例では、
Ｂ０（ＲＶ’，ＧＯｒｄ’）＝（“Ｓｏｕｔｈ”，１）＞Ｂ１（ＬＶＬ’，ＧＯｒｄ’）＝（“Ｎｏｒｔｈ”，５）
であるので、Ｂ１（ＲＶ’，ＧＯｒｄ’）が先頭（最も小さい）要素であることが判定される。よって、ブロック番号を含めた要素の組Ｂ１（“Ｎｏｒｔｈ”，５，１）がマージ処理の結果として取り出される。このマージ処理の結果は、
ＲＶ’［０］＝“Ｎｏｒｔｈ”
ＧＯｒｄ’［０］＝５
ＢｌｋＮｏ’［０］＝１
のように記述できる。これにより、ブロック１側のデータが取り出されたので、ブロック１側の読み出しポインタが１つ先へ進められる。【０１３９】
図２６Ｂでは、読み出しポインタが先頭に位置しているブロック０内の１番目のレコードと、読み出しポインタが１つ先へ進められたブロック１内の２番目のレコードとを比較する処理が示されている。同様に、Ｂ０（“Ｓｏｕｔｈ”，１）とＢ１（“Ｓｏｕｔｈ”，４）とを比較すると、Ｂ０（“Ｓｏｕｔｈ”，１）の方が小さいと判定されるので、ブロック番号を含めた要素の組Ｂ０（“Ｓｏｕｔｈ”，１，０）がマージ処理の結果、すなわち、
ＲＶ’［１］＝“Ｓｏｕｔｈ”
ＧＯｒｄ’［１］＝１
ＢｌｋＮｏ’［１］＝０
として取り出される。これにより、ブロック０側のデータが取り出されたので、ブロック０側の読み出しポインタが１つ先へ進められる。【０１４０】
このように、ポインタを進めながら、ブロック０側のデータとブロック１側のデータを順次比較することにより、最終的に、ブロック０側のデータとブロック１側のデータがマージされた昇順のリストが得られる。図２６Ｃには、最終的に取り出された項目値配列ＲＶ’とレコード順序番号配列ＧＯｒｄ’とブロック番号配列ＢｌｋＮｏ’とが示されている。【０１４１】
なお、取り出された項目値配列ＲＶ’とレコード順序番号配列ＧＯｒｄ’とブロック番号配列ＢｌｋＮｏ’は、２段目のマージ処理のため、本例では、ＳＰＵ−４へ送出されるが、最終的な結果を一括して送出するのではなく、ブロック０側とブロック１側の比較処理を進めながら、取り出されたデータを必要に応じて、ＳＰＵ−０からＳＰＵ−４へ送出してもよい。【０１４２】
以上の説明からわかるように、本発明の一実施形態によるブロック間ソート処理１（マージ処理）の１段目の処理では、データアクセスがシーケンシャルアクセスだけに限定され、かつ、各ＳＰＵが並列にブロック間ソート処理１を実行可能である。よって、マルチプロセッサ型処理装置の性能が十分に活かされている。【０１４３】
今度は、演算ユニットＳＰＵ−４が、ＳＰＵ−０から出力されたブロック０〜１と、ＳＰＵ−１１から出力されたブロック２〜３に所定の順序のマージ処理を適用し、１つのブロック０〜３を出力する２段目のブロック間ソート処理１について説明する。図２７Ａ及び２７Ｂは、本発明の一実施形態による表形式データのソート処理における２段目のマージ処理の説明図である。２段目のマージ処理は、入力される情報が他の演算ユニットのローカルメモリから転送される点を除いて、１段目のマージ処理と同様である。この処理を簡単に説明すると、図２７Ａに示されているように、最初、２つのブロックからの項目値配列ＲＶ’、レコード順序番号配列ＧＯｒｄ’、及び、ブロック番号配列ＢｌｋＮｏ’の読み出し用ポインタが先頭に設定される。両方の（ＲＶ’，ＧＯｒｄ’）の組の値を比較すると、
Ｂ０〜１（ＲＶ’，ＧＯｒｄ’）＝（“Ｎｏｒｔｈ”，５）＞Ｂ２〜３（ＲＶ’，ＧＯｒｄ’）＝（“Ｅａｓｔ”，８）
であることから、Ｂ２〜３側の要素の方が小さいということがわかる。よって、Ｂ２〜３側の先頭の要素の組であるＢ２〜３（“Ｅａｓｔ”，８，２）を取り出す。そして、要素の組が取り出された方のＢ２〜３側の読み出しポインタを１つ先へ進められる。ここで、Ｂａ〜ｂという表記は、ブロックａからブロックｂまでの間のソート処理の結果として得られたデータを表している。【０１４４】
このような要素の組の大小比較と、小さい方の要素の組の読み出しを繰り返すことにより、図２７Ｂに示されているように、最後にＢ２〜３側の要素の組であるＢ２〜３（“Ｗｅｓｔ”，１３，３）が取り出され、２段目のマージ処理が終了する。【０１４５】
なお、取り出された項目値配列ＲＶ’とレコード順序番号配列ＧＯｒｄ’とブロック番号配列ＢｌｋＮｏ’は、３段目のマージ処理のため、本例では、ＳＰＵ−６へ送出されるが、最終的な結果を一括して送出するのではなく、ブロック０側とブロック１側の比較処理を進めながら、取り出されたデータを必要に応じて、ＳＰＵ−４からＳＰＵ−６へ送出してもよい。また、以上の説明からわかるように、本発明の一実施形態によるブロック間ソート処理１（マージ処理）の２段目の処理では、データアクセスがシーケンシャルアクセスだけに限定され、かつ、各ＳＰＵが並列にブロック間ソート処理１を実行可能である。よって、マルチプロセッサ型処理装置の性能が十分に活かされている。【０１４６】
２段目のマージ処理は、本例では、ＳＰＵ−４とＳＰＵ−５によって並列に実行されている。ＳＰＵ−４は、ブロック０からブロック３までのブロック間マージ処理の結果をブロック０〜３としてＳＰＵ−６へ出力し、ＳＰＵ−５は、ブロック４からブロック７までのブロック間マージ処理の結果をブロック４〜７としてＳＰＵ−６へ出力する。本例では、ブロックの総数は、ブロック０からブロック７までの８ブロックであるため、ＳＰＵ−６による３段目のマージ処理によって、全てのブロックからのデータのマージが終了し、すなわち、全てのブロックを考慮したソート処理が終了する。当業者によって理解されるように、ブロック数が９個以上ある場合には、たとえば、図１２Ａ乃至１２Ｃに示されるように、マージ処理の段数を増加させることにより、最終的に全てのブロックからのデータがマージされたソート処理結果を得ることが可能である。【０１４７】
図２８は、本発明の一実施形態による表形式データのソート処理における３段目のマージ処理の説明図である。３段目のマージ処理もまた、１段目のマージ処理及び２段目のマージ処理と同様に、Ｂ０〜３側のデータＢ０〜３（ＲＶ’，ＧＯｒｄ’）とＢ４〜７側のデータＢ０〜４（ＲＶ’，ＧＯｒｄ’）を先頭から順番に比較し、小さい方の要素の組を取り出し、要素が取り出された側のデータの読み出し用ポインタを１つ先へ進める、という操作を繰り返す。これにより、図２８の右側に示されているような配列の組、すなわち、項目値配列ＲＶ’、レコード順序番号配列ＧＯｒｄ’、及び、ブロック番号配列ＢｌｋＮｏ’の組が得られる。この配列の組は、全レコードのソート結果を表現している。たとえば、項目値配列ＲＶ’を参照すると、先頭から、同一値を含めて値が昇順に並べられているので、グローバル項目値配列中の項目値の整列順にレコードがソートされていることがわかる。また、項目値配列ＲＶ’の要素の値が同一であるレコードは、レコード順序番号配列ＧＯｒｄ’を参照することにより、ソート前のレコード順序番号の昇順に整列されていることもわかる。このように、レコード順序番号に関して安定性のあるソート結果が得られた理由は、ブロック間ソートの際に、項目値指定ポインタとレコード順序番号の組に関する大小関係に基づいてレコードの並べ替えが行われたからである。【０１４８】
本発明の一実施形態による表形式データのソート処理におけるブロック間ソート処理１（マージ処理）によって得られた３つの配列から次のことがわかる。たとえば、配列の組の１行目のデータ＝（“Ｅａｓｔ”，８，２）を参照すると、ソート後にレコード順序番号０が付与されるレコードは、
（１）ソートのキーとなるデータ項目に関する項目値の値が“Ｅａｓｔ”であり、
（２）ソート前に付与されていたレコード順序番号が８であり、
（３）ブロック２に属している。【０１４９】
発明の理解を助けるため、このブロック間ソート処理1（マージ処理）の結果がマルチコア型処理装置向けのデータ構造で表現される。図２９Ａ乃至２９Ｃは、本発明の一実施形態による表形式データのソート処理におけるブロック間ソート処理１（マージ処理）の結果の説明図である。図２９Ａに示された表形式データは図７Ｂに示された表形式データと類似しているが、この時点では、図２９Ａに示されているレコード順序番号配列ＧＯｒｄに格納されるべき値が未定である。一方、図２９Ｂ及び図２９Ｃに示されている項目値情報、すなわち、項目値配列ＲＶは、ソート処理による影響を受けないので、図２２Ａ乃至２２Ｄに示されている項目値情報と当然に同じである。【０１５０】
本発明の一実施形態による表形式データのソート処理では、最後に、各ブロックに属するレコードのレコード順序番号を決定する。このレコード順序番号を決定する処理は、ブロック間ソート処理２（分配処理）と呼ばれる。ブロック間ソート処理２（分配処理）は、図１７Ａ、１７Ｂ、１７Ｃ及び図１８を参照して説明した処理と全く同一であるため、これ以上の説明は加えない。【０１５１】
さらに、第１のタイプの項目値情報を含む表形式データにも多項目ソート処理を適用することが可能である。この場合に用いられる多項目ソート処理は、多段階ソート処理である。すなわち、図２２Ａ乃至２２Ｄから図２９Ａ乃至２９Ｃを参照して説明した所定のデータ項目に関するソート処理を複数のデータ項目に関して繰り返すことによって実現される。【０１５２】
よって、たとえば、図２２Ａに示された表形式データに対して、最初に、データ項目＝「Ｓｃｈｏｏｌ」に関してソート処理を実行し、次に、データ項目＝「Ａｇｅ」に関してソート処理を実行する場合（多段階ソート処理）、上述のソート処理によってデータ項目＝「Ｓｃｈｏｏｌ」に関するソートを行い、続いて、同様に、図１８に示されたブロック番号配列、レコード順序番号配列及び項目値アクセス情報配列から始めて、データ項目＝「Ａｇｅ」に関するソート処理を実行すればよい。なお、複数のデータ項目に関してソート処理を順次適用する場合、優先度の高いデータ項目に関するソート処理が後から適用される。なお、ソートが適用されるデータ項目の順序に応じてソート処理の結果が異なる。【０１５３】
本発明は、以上の実施の形態に限定されることなく、特許請求の範囲に記載された発明の範囲内で、種々の変更が可能であり、それらも本発明の範囲内に包含されるものであることは言うまでもない。
【図１】
2009044486.tif 000003
【図２】
2009044486.tif 000004
【図３】
2009044486.tif 000005
【図４】
2009044486.tif 000006
【図５Ａ】
2009044486.tif 000007
【図５Ｂ】
2009044486.tif 000008
【図５Ｃ】
2009044486.tif 000009
【図５Ｄ】
2009044486.tif 000010
【図６Ａ】
2009044486.tif 000011
【図６Ｂ】
2009044486.tif 000012
【図７Ａ】
2009044486.tif 000013
【図７Ｂ】
2009044486.tif 000014
【図７Ｃ】
2009044486.tif 000015
【図７Ｄ】
2009044486.tif 000016
【図８】
2009044486.tif 000017
【図９】
2009044486.tif 000018
【図１０Ａ】
2009044486.tif 000019
【図１０Ｂ】
2009044486.tif 000020
【図１０Ｃ】
2009044486.tif 000021
【図１１】
2009044486.tif 000022
【図１２Ａ】
2009044486.tif 000023
【図１２Ｂ】
2009044486.tif 000024
【図１２Ｃ】
2009044486.tif 000025
【図１３Ａ】
2009044486.tif 000026
【図１３Ｂ】
2009044486.tif 000027
【図１３Ｃ】
2009044486.tif 000028
【図１４Ａ】
2009044486.tif 000029
【図１４Ｂ】
2009044486.tif 000030
【図１５】
2009044486.tif 000031
【図１６Ａ】
2009044486.tif 000032
【図１６Ｂ】
2009044486.tif 000033
【図１６Ｃ】
2009044486.tif 000034
【図１７Ａ】
2009044486.tif 000035
【図１７Ｂ】
2009044486.tif 000036
【図１７Ｃ】
2009044486.tif 000037
【図１８】
2009044486.tif 000038
【図１９】
2009044486.tif 000039
【図２０】
2009044486.tif 000040
【図２１Ａ】
2009044486.tif 000041
【図２１Ｂ】
2009044486.tif 000042
【図２２Ａ】
2009044486.tif 000043
【図２２Ｂ】
2009044486.tif 000044
【図２２Ｃ】
2009044486.tif 000045
【図２２Ｄ】
2009044486.tif 000046
【図２３】
2009044486.tif 000047
【図２４Ａ】
2009044486.tif 000048
【図２４Ｂ】
2009044486.tif 000049
【図２４Ｃ】
2009044486.tif 000050
【図２４Ｄ】
2009044486.tif 000051
【図２４Ｅ】
2009044486.tif 000052
【図２４Ｆ】
2009044486.tif 000053
【図２４Ｇ】
2009044486.tif 000054
【図２４Ｈ】
2009044486.tif 000055
【図２５】
2009044486.tif 000056
【図２６Ａ】
2009044486.tif 000057
【図２６Ｂ】
2009044486.tif 000058
【図２６Ｃ】
2009044486.tif 000059
【図２７Ａ】
2009044486.tif 000060
【図２７Ｂ】
2009044486.tif 000061
【図２８】
2009044486.tif 000062
【図２９Ａ】
2009044486.tif 000063
【図２９Ｂ】
2009044486.tif 000064
【図２９Ｃ】
2009044486.tif 000065
【国際調査報告】
2009044486.tif 000066
2009044486.tif 000067
2009044486.tif 000068