(57)【要約】  共有メモリ（１２０）にアクセスする複数台のプロセッサ（１１０−１，１１０−２，１１０−３，・・・）を含む対称型マルチプロセッサシステム（１００）において、インデックス配列（２１０）を介してアクセスされる間接参照配列（２２０）を直接参照配列（２３０）に変換する方法である。本発明の方法は、複数台のプロセッサ(１１０−１，１００−２，１００−３・・・)を用いて、インデックス配列（２１０）中の要素を上位桁の値に従って並べ替え、インデックス配列（２１０）を添字配列（４６０）及び要素配列（４７０）に変換するステップ（３０２）と、複数台のプロセッサ(１１０−１，１１０−２，１１０−３・・・)を用いて、要素配列（４７０）中の要素を添字として使って間接参照配列（２２０）中の要素を読み出し、読み出された要素を、要素配列（４７０）中の要素に対応する添字を使って、中間参照配列（５１０）に格納するステップ（３０４）と、複数台のプロセッサ(１１０−１，１１０−２，１１０−３・・・)を用いて、添字配列（４６０）及び中間参照配列（５１０）から同じ添字を使ってそれぞれの要素を読み出し、添字配列（４６０）から読み出された要素を添字として使って、中間参照配列（５１０）から読み出された要素を直接参照配列（２３０）に格納するステップ（３０６）とを含む。
2008136066.tif 000002
【特許請求の範囲】
【請求項１】
共有メモリにアクセスする複数台のプロセッサを含むシステムにおいて、インデックス配列を介してアクセスされる間接参照配列を直接参照配列に変換する方法であって、
上記インデックス配列中の要素の値を上位桁と下位桁に分ける基数を定めるステップと、
上記複数台のプロセッサを用いて、上記インデックス配列中の上記要素の上位桁の値の累積度数分布を並列的に数え上げるステップと、
上記複数台のプロセッサを用いて、上記インデックス配列の添字及び上記インデックス配列中の要素を上記累積度数分布に基づいて並列的に並べ替えることにより、上記インデックス配列の添字及び上記インデックス配列中の要素をそれぞれ添字配列及び要素配列に並列的に格納するステップと、
上記複数台のプロセッサを用いて、上記要素配列中の要素の値を添字として上記間接参照配列の要素を並列的に読み出し、上記読み出された要素を上記添字配列と同じサイズの中間参照配列に並列的に格納するステップと、
上記複数台のプロセッサを用いて、上記添字配列の要素及び対応する上記中間参照配列の要素を並列的に読み出し、上記添字配列の要素を添字として使用して上記中間参照配列の要素を上記直接参照配列に並列的に格納するステップと、
を含む方法。
【請求項２】
共有メモリにアクセスする複数台のプロセッサを含み、インデックス配列を介してアクセスされる間接参照配列を直接参照配列に変換する装置であって、
上記インデックス配列中の要素の値を上位桁と下位桁に分ける基数を定める手段と、
上記複数台のプロセッサを用いて、上記インデックス配列中の上記要素の上位桁の値の累積度数分布を並列的に数え上げる手段と、
上記複数台のプロセッサを用いて、上記インデックス配列の添字及び上記インデックス配列中の要素を上記累積度数分布に基づいて並列的に並べ替えることにより、上記インデックス配列の添字及び上記インデックス配列中の要素をそれぞれ添字配列及び要素配列に並列的に格納する手段と、
上記複数台のプロセッサを用いて、上記要素配列中の要素の値を添字として上記間接参照配列の要素を並列的に読み出し、上記読み出された要素を上記添字配列と同じサイズの中間参照配列に並列的に格納する手段と、
上記複数台のプロセッサを用いて、上記添字配列の要素及び対応する上記中間参照配列の要素を並列的に読み出し、上記添字配列の要素を添字として使用して上記中間参照配列の要素を上記直接参照配列に並列的に格納する手段と、
を含む装置。
【請求項３】
共有メモリにアクセスする複数台のプロセッサを含むコンピュータにロードされ、インデックス配列を介してアクセスされる間接参照配列を直接参照配列に変換するコードを上記コンピュータに実行させるプログラムであって、
上記インデックス配列中の要素の値を上位桁と下位桁に分ける基数を定めるコードと、
上記複数台のプロセッサを用いて、上記インデックス配列中の上記要素の上位桁の値の累積度数分布を並列的に数え上げるコードと、
上記複数台のプロセッサを用いて、上記インデックス配列の添字及び上記インデックス配列中の要素を上記累積度数分布に基づいて並列的に並べ替えることにより、上記インデックス配列の添字及び上記インデックス配列中の要素をそれぞれ添字配列及び要素配列に並列的に格納するコードと、
上記複数台のプロセッサを用いて、上記要素配列中の要素の値を添字として上記間接参照配列の要素を並列的に読み出し、上記読み出された要素を上記添字配列と同じサイズの中間参照配列に並列的に格納するコードと、
上記複数台のプロセッサを用いて、上記添字配列の要素及び対応する上記中間参照配列の要素を並列的に読み出し、上記添字配列の要素を添字として使用して上記中間参照配列の要素を上記直接参照配列に並列的に格納するコードと、
を含むプログラム。
【請求項４】
共有メモリにアクセスする複数台のプロセッサを含むコンピュータにロードされ、請求の範囲第１項記載のインデックス配列を介してアクセスされる間接参照配列を直接参照配列に変換する方法を上記コンピュータに実行させるためのコンピュータプログラムプロダクト。
【請求項５】
共有メモリにアクセスする複数台のプロセッサを含むコンピュータにロードされ、請求の範囲第１項記載のインデックス配列を介してアクセスされる間接参照配列を直接参照配列に変換する方法を上記コンピュータに実行させるためのコンピュータプログラムが記録された記憶媒体。
【請求項６】
共有メモリにアクセスする複数台のプロセッサを含む対称型マルチプロセッサシステムにおいて、インデックス配列を介してアクセスされる間接参照配列を直接参照配列に変換する方法であって、
上記複数台のプロセッサを用いて、上記インデックス配列中の要素を上位桁の値に従って並べ替え、上記インデックス配列を添字配列及び要素配列に変換するステップと、
上記複数台のプロセッサを用いて、上記要素配列中の要素を添字として使って上記間接参照配列中の要素を読み出し、上記読み出された要素を、上記要素配列中の要素に対応する添字を使って、中間参照配列に格納するステップと、
上記複数台のプロセッサを用いて、上記添字配列及び上記中間参照配列から同じ添字を使ってそれぞれの要素を読み出し、上記添字配列から読み出された要素を添字として使って、上記中間参照配列から読み出された要素を上記直接参照配列に格納するステップと、
を含む方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、メモリ共有型並列処理システム、特に、対称型マルチプロセッサ（Ｓｙｍｍｅｔｒｉｃ  Ｍｕｌｔｉｐｌｅ  Ｐｒｏｃｅｓｓｏｒ）システムにおいて、メモリ間接参照をメモリ直接参照に変換する方法に関係する。【０００２】
本発明は、共有メモリにアクセスする複数台のプロセッサを含み、インデックス配列を介してアクセスされる間接参照配列を直接参照配列に変換する装置にも関係する。
【背景技術】
【０００３】
従来、産業上の様々な分野において、大規模データを高速に処理することが求められている。大規模データの処理は、キャッシュやプリフェッチなどによるメモリアクセスの高速化、メモリ自体の高速化、及び、プロセッサの並列化のような演算処理の高速化、といったハードウェア技術の開発、ならびに、データ処理アルゴリズムの開発によって、高速化され続けている。たとえば、本発明者は、大規模データを高速に処理するため、特許文献１に記載されているような、「オンメモリデータ処理アルゴリズム」を提案している。【０００４】
近年、複数個のプロセッサが並列に動作するマルチプロセッサや、１チップ上に複数個のＣＰＵコアが搭載されたマルチコアプロセッサ、特に、複数個のＣＰＵが同等に処理を分担する対称型マルチプロセッサのようなメモリ共有型並列処理システムが設計されている。大規模データの検索・集計・ソート等の処理は、多くの場合に大規模データに同じ演算を適用するので、特に、対称型マルチプロセッサは大規模データの高速処理に適していると考えられる。【０００５】
このようにＣＰＵの並列化が進み、かつ、ＣＰＵの処理速度（すなわち、クロック）が向上し続けているが、メモリの速度の向上はＣＰＵの処理速度の向上に追いつかないため、メモリの速度とＣＰＵの処理速度との差は増大し続けている。たとえば、３ＧＨｚを超える動作クロックを有するＣＰＵが出現しているが、メモリレイテンシは１００ｎｓ、すなわち、この場合には、３００クロック以上に達することがある。【０００６】
メモリ共有型並列処理システムにおいても、処理の高速化のためにメモリレイテンシを短縮することは不可欠であるため、キャッシュヒット率を高めることが重要である。一般に、キャッシュヒット率を高めるためには、（１）メモリをシーケンシャルにアクセスすること、たとえば、プリフェッチ、及び／又は、（２）アクセス領域を制限することが有効であることが知られているが、このことはメモリ共有型並列処理システムにおいても同様に成り立つ。【０００７】
しかし、メモリ共有型並列処理システムにおいて、キャッシュヒット率を高めることは容易ではない。たとえば、大規模データの検索・集計・ソートなどの処理において使用される、大規模なインデックス配列（Ｉ［ｉ］、ｉはループ変数）によるメモリ間接参照（Ａ［Ｉ［ｉ］］、Ａは参照対象である配列）は、キャッシュミスヒットを頻繁に発生させるが、このようなメモリ共有型並列処理システムにおける大規模なメモリ間接参照時にキャッシュミスヒットを低減できる一般的な方法は知られていない。
【特許文献１】米国特許第６，６４３，６４４号明細書
【発明の開示】
【発明が解決しようとする課題】
【０００８】
本発明は、上記の従来技術の問題点に鑑みて、メモリ共有型並列処理システムにおいて、高いキャッシュヒット率で大規模なメモリ間接参照を行う方法の提供を目的とする。【０００９】
本発明は、さらに、高いキャッシュヒット率で大規模なメモリ間接参照を行うメモリ共有型並列処理装置の提供を目的とする。
【課題を解決するための手段】
【００１０】
本発明者は、上記目的を達成するため、
（１）ＣＰＵのマルチコア化
（２）ＣＰＵのクロックの驚異的な上昇
（３）ＣＰＵのキャッシュアクセスと外部メモリアクセスとの間のパフォーマンスの乖離
という近年のハードウェア技術の傾向と、
（４）ＣＰＵのアクセス範囲を限定するとキャッシュヒット率が高くなる
というキャッシュメモリの特徴と、
を活用できることに着目した。すなわち、本発明者は、メモリ間接参照をそのまま実行するのではなく、ＣＰＵのアクセス範囲を限定するために部分的なソートを用いて配列をチャンクに分割し、分割されたチャンク毎に並列的にメモリ間接参照をメモリ直接参照に変換することによって、キャッシュヒット率を高めることができることに気付いた。【００１１】
したがって、本発明の第１の態様によれば、共有メモリにアクセスする複数台のプロセッサを含むシステムにおいてインデックス配列を介してアクセスされる間接参照配列を直接参照配列に変換する方法であって、
上記インデックス配列中の要素の値を上位桁と下位桁に分ける基数を定めるステップと、
上記複数台のプロセッサを用いて、上記インデックス配列中の上記要素の上位桁の値の累積度数分布を並列的に数え上げるステップと、
上記複数台のプロセッサを用いて、上記インデックス配列の添字及び上記インデックス配列中の要素を上記累積度数分布に基づいて並列的に並べ替えることにより、上記インデックス配列の添字及び上記インデックス配列中の要素をそれぞれ添字配列及び要素配列に並列的に格納するステップと、
上記複数台のプロセッサを用いて、上記要素配列中の要素の値を添字として上記間接参照配列の要素を並列的に読み出し、上記読み出された要素を上記添字配列と同じサイズの中間参照配列に並列的に格納するステップと、
上記複数台のプロセッサを用いて、上記添字配列の要素及び対応する上記中間参照配列の要素を並列的に読み出し、上記添字配列の要素を添字として使用して上記中間参照配列の要素を上記直接参照配列に並列的に格納するステップと、
を含む方法が提供される。【００１２】
さらに、本発明の第２の態様によれば、共有メモリにアクセスする複数台のプロセッサを含み、インデックス配列を介してアクセスされる間接参照配列を直接参照配列に変換する装置であって、
上記インデックス配列中の要素の値を上位桁と下位桁に分ける基数を定める手段と、
上記複数台のプロセッサを用いて、上記インデックス配列中の上記要素の上位桁の値の累積度数分布を並列的に数え上げる手段と、
上記複数台のプロセッサを用いて、上記インデックス配列の添字及び上記インデックス配列中の要素を上記累積度数分布に基づいて並列的に並べ替えることにより、上記インデックス配列の添字及び上記インデックス配列中の要素をそれぞれ添字配列及び要素配列に並列的に格納する手段と、
上記複数台のプロセッサを用いて、上記要素配列中の要素の値を添字として上記間接参照配列の要素を並列的に読み出し、上記読み出された要素を上記添字配列と同じサイズの中間参照配列に並列的に格納する手段と、
上記複数台のプロセッサを用いて、上記添字配列の要素及び対応する上記中間参照配列の要素を並列的に読み出し、上記添字配列の要素を添字として使用して上記中間参照配列の要素を上記直接参照配列に並列的に格納する手段と、
を含む装置が提供される。【００１３】
さらに、本発明の第３の態様によれば、共有メモリにアクセスする複数台のプロセッサを含むコンピュータにロードされ、インデックス配列を介してアクセスされる間接参照配列を直接参照配列に変換するコードを上記コンピュータに実行させるプログラムであって、
上記インデックス配列中の要素の値を上位桁と下位桁に分ける基数を定めるコードと、
上記複数台のプロセッサを用いて、上記インデックス配列中の上記要素の上位桁の値の累積度数分布を並列的に数え上げるコードと、
上記複数台のプロセッサを用いて、上記インデックス配列の添字及び上記インデックス配列中の要素を上記累積度数分布に基づいて並列的に並べ替えることにより、上記インデックス配列の添字及び上記インデックス配列中の要素をそれぞれ添字配列及び要素配列に並列的に格納するコードと、
上記複数台のプロセッサを用いて、上記要素配列中の要素の値を添字として上記間接参照配列の要素を並列的に読み出し、上記読み出された要素を上記添字配列と同じサイズの中間参照配列に並列的に格納するコードと、
上記複数台のプロセッサを用いて、上記添字配列の要素及び対応する上記中間参照配列の要素を並列的に読み出し、上記添字配列の要素を添字として使用して上記中間参照配列の要素を上記直接参照配列に並列的に格納するコードと、
を含むプログラムが提供される。【００１４】
さらに、本発明の第４の態様によれば、共有メモリにアクセスする複数台のプロセッサを含むコンピュータにロードされ、本発明の第１の態様によるインデックス配列を介してアクセスされる間接参照配列を直接参照配列に変換する方法を上記コンピュータに実行させるためのコンピュータプログラムプロダクトが提供される。【００１５】
さらに、本発明の第５の態様によれば、共有メモリにアクセスする複数台のプロセッサを含むコンピュータにロードされ、本発明の第１の態様によるインデックス配列を介してアクセスされる間接参照配列を直接参照配列に変換する方法を上記コンピュータに実行させるためのコンピュータプログラムが記録された記憶媒体が提供される。
【発明の効果】
【００１６】
本発明の少なくとも１つの実施例によれば、間接参照配列から直接参照配列への変換は、最初に、インデックス配列を、部分的な並べ替えによって、添字配列及び要素配列に変換し、次に、間接参照配列を、要素配列を使った読み出しによって、（同様に部分的に並べ替えられた配列である）中間参照配列に変換し、最後に、この中間参照配列を、添字配列を使った書き込みにより、直接参照配列に変換することにより実現される。【００１７】
より詳細には、本発明の少なくとも１つの実施例によれば、インデックス配列中の要素の値を上位桁と下位桁に分離し、上位桁だけに関して、累積度数分布の数え上げと、要素の並べ替えを行っている。これにより、添字配列、要素配列及び中間参照配列は、インデックス配列中の要素の上位桁の値に応じたチャンクに分割され、各プロセッサのアクセス範囲は、１個（又は１個以上）のチャンクに限定される。このように、各プロセッサのアクセス範囲が特定のチャンクに限定されるので、キャッシュヒット率が高くなる。その上、各プロセッサは別々のチャンクを受け持つので、複数台のプロセッサによる並列処理が可能になる。また、累積度数分布の数え上げ、及び、要素の並べ替えは、各プロセッサが、インデックス配列中で当該プロセッサの受け持つ範囲内の要素について数え上げと並べ替えを行うので、全体としては、複数台のプロセッサによる並列処理が可能である。結果的に、インデックス配列を介してアクセスされる間接参照配列が高速に直接参照配列に変換される。【００１８】
共有メモリにアクセスする複数台のプロセッサを含むメモリ共有型並列処理システムには、マルチプロセッサ、マルチコア、メニーコアといった構成が含まれるがこれらに限定されない。本発明の好ましい実施形態においては、対称型マルチプロセッサシステムが利用される。【００１９】
本発明の一実施形態によれば、最初に、各プロセッサが共有メモリ上のインデックス配列中の受け持ち範囲を特定し、次に、各プロセッサが間接参照配列のサイズに応じて、インデックス配列中の要素の値を上位桁と下位桁に分離する基数を決定する。間接参照配列のサイズはインデックス配列中の要素の値の範囲に対応している。付加的に、基数の決定の際に、プロセッサの台数を考慮してもよい。【００２０】
本発明の一実施形態によれば、累積度数分布の数え上げは、各プロセッサがインデックス配列中の受け持ち範囲内の要素の上位桁の値の個数を並列に数え上げ、続いて、各プロセッサがインデックス配列中の受け持ち範囲内の要素の上位桁の値の個数を、同じ上位桁の値について先行するプロセッサによって既に数え上げられた個数を考慮して、累計数化することによって行われる。たとえば、インデックス配列の中で、各プロセッサが受け持つ範囲は、インデックス配列の先頭から順に、各プロセッサの受け持ち範囲がほぼ均等になるように各プロセッサに割り当てられる。このため、同じ上位桁の値が、２台以上のプロセッサの受け持ち範囲内で出現することがある。よって、各プロセッサは、同じ上位桁の値の累計数が連続するように、先行するプロセッサによって既に数え上げられた個数を併合して、当該各プロセッサの受け持ち範囲内の累計数を算出する。【００２１】
本発明の一実施形態によれば、各プロセッサは、インデックス配列中の受け持ち範囲内の要素の添字及び値を、その要素の上位桁の値の累計数をポインタとして利用して、添字配列及び値配列に格納する。【００２２】
本発明の一実施形態によれば、各プロセッサは、共有メモリ上の添字配列及び要素配列中の受け持ち範囲を特定し、要素配列中の受け持ち範囲内の要素をポインタとして利用して、間接参照配列の要素を読み出し、読み出された要素を、要素配列中の要素を指す添字をポインタとして利用して、中間参照配列に格納する。【００２３】
本発明の一実施形態によれば、各プロセッサは、添字配列及び中間参照配列中の受け持ち範囲を特定し、添字配列中の受け持ち範囲内の要素をポインタとして利用して、その要素に対応する中間参照配列中の受け持ち範囲内の要素を、直接参照配列に格納する。
【図面の簡単な説明】
【００２４】
【図１】メモリ共有型並列処理システムの一実施例である対称型マルチプロセッサシステムの概略図である。
【図２】メモリ間接参照のためのインデックス配列及び間接参照配列と直接参照配列とを示す図である。
【図３】本発明の第１の実施形態による間接参照・直接参照変換方法の概略フローチャートである。
【図４】第３図に示された間接参照・直接参照変換方法のステップ３０２の説明図である。
【図５】第３図に示された間接参照・直接参照変換方法のステップ３０４の説明図である。
【図６】第３図に示された間接参照・直接参照変換方法のステップ３０６の説明図である。
【図７】本発明の第２の実施形態による、２段のインデックス配列を介してアクセスされる間接参照配列を直接参照配列に変換する方法で使用される、インデックス配列、間接参照配列及び直接参照配列を示す図である。
【図８】本発明の第２の実施形態による間接参照配列を直接参照配列に変換する方法のフローチャートである。
【図９】本発明の第２の実施形態による方法のステップ８０４の説明図である。
【図１０】本発明の第２の実施形態による方法のステップ８０６の説明図である。
【図１１】本発明の第２の実施形態による方法のステップ８０６の一変形例の説明図である。
【図１２】本発明の第２の実施形態による方法のステップ８０８の説明図である。
【図１３】本発明の第２の実施形態による方法のステップ８１０の説明図である。
【図１４】本発明の第２の実施形態による方法のステップ８１２の説明図である。
【図１５】本発明の第２の実施形態による方法の２段目の変換結果の説明図である。
【図１６】大規模なインデックス配列の一例の説明図である。
【符号の説明】
【００２５】
１００    メモリ共有型並列処理システム
１１０−１，１１０−２，１１０−３    ＣＰＵ
１１１−１，１１１−２，１１１−３    ＣＰＵコア
１１２−１，１１２−２，１１２−３    キャッシュ
１１３−１，１１３−２，１１３−３    Ｌ１キャッシュ
１１４−１，１１４−２，１１４−３    Ｌ２キャッシュ
１２０    共有メモリ
１３０    バス
２１０，７１０，７２０，１６００    インデックス配列
２２０，７３０    間接参照配列
２３０，７４０，１４２０，１４３０，１４４０，１５００    直接参照配列
４１０，４１１，４１２，４１３，９０１，９０２，１１１０，１１１１，１４１０，１４１１    ＣＰＵの受け持ち範囲
４２０    インデックス配列の上位桁の配列
４３０    インデックス配列の下位桁の配列
４４１，４４２，４４３，４４４，９１０，９１１，９２０，９２１    カウント配列
４５１，４５２，４５３，４５４，１０１０，１０１１，１２１０，１２１１    累積度数分布配列
４６０，１２２０，１２２１    インデックス配列の添字配列
４７０，１２３０，１２３１    インデックス配列の要素配列
４８１，４８２，４８３，４８４，１２４０，１２４１，１２４２，１２４３,１３２０，１３２１，１３２２，１３２３    チャンク
５１０，１３１０    中間参照配列
１１２０    作業配列
【発明を実施するための最良の形態】
【００２６】
以下では、添付図面を参照して本発明をより詳細に説明する。すべての図面を通して、同じ参照番号は同一又は類似の要素を示している。【００２７】
図１には、メモリ共有型並列処理システムの一実施例である対称型マルチプロセッサシステム１００の概略図である。システム１００は、ｎ台のＣＰＵ１１０−１、１１０−２、１１０−３、・・・、１１０−ｎと、ｎ台のＣＰＵによってアクセスされる共有メモリ１２０と、バス１３０とを含む。説明を簡単にするため、コンピュータシステムに必要とされる、よく知られている構成要素、たとえば、入力装置、出力装置、プログラム等を記憶するリードオンリーメモリ、ハードディスクのような記憶装置、及び、ＣＤ−ＲＯＭドライバ、ネットワーク等に接続される外部インターフェイス装置は図示されていないが、これらの構成要素もバス１３０に接続される。ＣＰＵ１１０−１は、ＣＰＵコア１１１−１とキャッシュメモリ１１２−１を含み、キャッシュメモリ１１２−１は、一般に、Ｌ１キャッシュ１１３−１とＬ２キャッシュ１１４−１とにより構成される。その他のＣＰＵ１１０−２、１１０−３、・・・、ＣＰＵ１１０−ｎも同様である。【００２８】
対称型マルチプロセッサシステム１００の各ＣＰＵ１１０−１、１１０−２、１１０−３、・・・、１１０−ｎによって実行されるプログラムは、たとえば、ＣＤ−ＲＯＭ（図示せず）に記憶され、ＣＤ−ＲＯＭドライバを介して、共有メモリに読み込まれてもよく、又は、ＣＤ−ＲＯＭから読み出されたプログラムはハードディスクに記憶されてもよい。或いは、プログラムは、インターフェイス装置及びネットワークを介して、外部サーバー等から供給されてもよい。【００２９】
図２は、メモリ間接参照のためのインデックス配列２１０及び間接参照配列２２０と、直接参照配列２３０とを示す図である。同図では、簡単のため、インデックス配列の要素の個数（これは、直接参照配列の要素の個数と一致する）は３２個であり、間接参照配列の要素の個数は１５個であるが、本発明の好ましい実施形態による間接参照配列から直接参照配列への変換が適用される配列は、要素の個数が数百万個以上に達することがある。【００３０】
一般に、配列Ａは、添字をｉとすると、配列の要素がＡ［ｉ］のように表記できるが、図面中では、配列は、配列の要素Ａ［ｉ］は、実線で囲まれた領域内に示され、要素Ａ［ｉ］と要素Ａ［ｉ＋１］の境界は点線で示されている。また、要素Ａ［ｉ］の添字ｉが要素Ａ［ｉ］の左側に示されている。また、配列の添字ｉは０から始まる整数で表されている。なお、インデックス配列２１０の要素の値は、間接参照配列の添字に対応するので、整数であり、すなわち、インデックス配列は整数配列である。一方、間接参照配列及び直接参照配列の要素の値は、どのようなデータ型でもかまわない。【００３１】
なお、図２において、インデックス配列の個数は１個であるため、１段のメモリ間接参照を実現するが、複数個のインデックス配列を重ねることにより、多段のメモリ間接参照を実現することも可能である。【００３２】
たとえば、ｉ，ｊ，ｋを配列の添字として、インデックス配列２１０の要素がＩ［ｉ］、間接参照配列２２０の要素がＡ［ｊ］、直接参照配列２３０の要素がＢ［ｋ］によって表されるならば、間接参照配列から直接参照配列への変換とは、
Ｂ［ｉ］＝Ａ［Ｉ［ｉ］］
を満たす配列Ｂを求めることである。【００３３】
図２の例では、ｉ＝０のとき、
Ａ［Ｉ［ｉ］］＝Ａ［Ｉ［０］］＝Ａ［１２］＝１１２
Ｂ［ｉ］＝Ｂ［０］＝１１２
であり、
Ａ［Ｉ［０］］＝Ｂ［０］
が成り立っていることがわかる。ｉ＝１，...，３１についても同様に、
Ｂ［ｉ］＝Ａ［Ｉ［ｉ］］
であることがわかる。【００３４】
また、インデックス配列がｍ段に多段化された場合、インデックス配列をＩ１、Ｉ２、・・・、Ｉｍのように表すと、間接参照配列から直接参照配列への変換は、
Ｂ［ｉ］＝Ａ［Ｉｍ［Ｉｍ−１［・・・Ｉ２［Ｉ１［ｉ］］・・・］］］
を満たす配列Ｂを求めることである。【００３５】
なお、図２の例では、間接参照行列２２０中の要素は、要素の値が昇順になるように配置されているが、当然ながら、間接参照行列２２０の要素がランダムに配置されていても構わない。【００３６】
以下では、図２に関して使用されたような表記法に従って、本発明の第１の実施形態を詳細に説明する。【００３７】
次に、図１に示されるような共有メモリ１２０にアクセスするｎ台のプロセッサを含む対称型マルチプロセッサシステム１００において、図２に示されたインデックス配列２１０を介してアクセスされる間接参照配列２２０を直接参照配列２３０に変換する、本発明の第１の実施形態による間接参照・直接参照変換方法を説明する。図３は、本発明の好ましい実施形態による間接参照・直接参照変換方法の概略フローチャートである。本実施形態では、対称型マルチプロセッサシステムの特長を十分に発揮させるため、種々の配列に適用される処理は、各配列を複数台のプロセッサにほぼ均等に割り当てることにより、複数台のプロセッサによって並列処理される。以下では、プロセッサの台数ｎが４であるとして説明する。たとえば、インデックス配列２１０は、添字の値が０から７の範囲、８から１５の範囲、１６から２３の範囲、及び、２４から３１の範囲に４分割され、それぞれの範囲がＣＰＵ−０、ＣＰＵ−１、ＣＰＵ−２、ＣＰＵ−３の４台のＣＰＵに割り当てられる。【００３８】
本発明の第１の実施形態による間接参照・直接参照変換方法は、最初に、インデックス配列２１０中の要素を上位桁の値に従って並べ替え、インデックス配列２１０を添字配列及び要素配列に変換する（ステップ３０２）。図４は、本発明の第１の実施形態によるメモリアクセス方式変換方法のステップ３０２の説明図である。【００３９】
本例では、間接参照配列２２０の添字は０から１５までの４ビットの値を取り得るので、インデックス配列２１０の要素は、上位２ビットと下位2ビットに分離され、すなわち、４進数で表現される。よって、本例では、基数４が設定される。これによると、たとえば、インデックス配列２１０の要素は、
Ｉ［０］＝１２（１０）＝３×４＋０＝３０（４）
Ｉ［１］＝０（１０）＝００（４）
・・・
Ｉ［３１］＝１２（１０）＝３０（４）
として表記される。図４には、インデックス配列２１０の上位桁配列（ＩＨ）４２０と下位桁配列（ＩＬ）４３０が示されている。【００４０】
次に、インデックス配列２１０の要素は、４台のプロセッサによって、上位桁の値に関して並列的に数え上げソートされる。すなわち、プロセッサ毎に、受け持ち範囲内のインデックス配列中の要素の上位桁の値の出現個数がカウントされる。よって、出現個数のカウントは並列処理される。プロセッサ毎の上位桁の値の出現個数は図４のカウント配列４４１、４４２、４４３及び４４４に示されている。【００４１】
続いて、このカウント配列４４１、４４２、４４３及び４４４に基づいて、プロセッサ間で、インデックス配列中の要素の上位桁の値のそれぞれの累積度数分布が作成される。累積度数分布は、後の４台のプロセッサによる並列処理で使用されるので、プロセッサ毎に生成される。このようにして生成された累積度数分布配列４５１、４５２、４５３、４５４が図４に示されている。【００４２】
その後、プロセッサ毎に、受け持ち範囲内のインデックス配列Ｉ中の要素が累積度数分布配列４５１、４５２、４５３及び４５４の要素を添字として使って要素配列４７０にコピーされる。このとき、同時に、その要素に対応する添字が添字配列４６０にコピーされる。すなわち、インデックス配列Ｉから添字配列４６０及び要素配列４７０を生成する処理は、複数台のプロセッサによって並列処理される。このようにして生成された要素配列４７０及び添字配列４６０が図４に示されている。要素配列及び添字配列は、それぞれ簡単にＣ及びＤでも表される。【００４３】
図４に示されたチャンク４８１、４８２、４８３及び４８４は、要素配列の要素の上位桁の値がそれぞれ０、１、２及び３に対応する添字の範囲を表している。以降の処理では、１個のチャンクを唯一のプロセッサが受け持つことにより、配列データをアクセスする際のキャッシュヒット率が上昇する。【００４４】
次に、本発明の第１の実施形態による間接参照・直接参照変換方法は、要素配列４７０中の要素を添字として使って間接参照配列２１０中の要素を読み出し、読み出された要素を、要素配列４７０中の当該要素に対応する添字を使って、中間参照配列に格納する（ステップ３０４）。図５には、生成された中間参照配列５１０が添字配列４６０と共に示されている。たとえば、添字配列をＣ、要素配列をＤ、中間参照配列をＥで表わし、ｉをループ変数とすると、ステップ３０４では、
Ｅ［ｉ］＝Ａ［Ｄ［ｉ］］
という処理が行われる。よって、中間参照配列５１０のサイズは、添字配列４６０及び要素配列４７０のサイズと等しい。実際には、本例では、要素配列４７０は4個のチャンク４８１、４８２、４８３及び４８４に分割され、ＣＰＵ−０がチャンク４８１、ＣＰＵ−１がチャンク４８２、ＣＰＵ−２がチャンク４８３、ＣＰＵ−３がチャンク４８４を受け持ち、中間参照配列５１０の要素を並列的に格納するので、キャッシュヒット率が上昇すると共に、処理の高速化も達成される。【００４５】
最後に、本発明の第１の実施形態による間接参照・直接参照変換方法は、添字配列４６０及び中間参照配列５１０から同じ添字を使ってそれぞれの要素を読み出し、添字配列４６０から読み出された要素を添字として使って、中間参照配列５１０から読み出された要素を直接参照配列２２０に格納する（ステップ３４０）。この処理は、
Ｂ［Ｃ［ｉ］］＝Ｅ［ｉ］
と表すことができる。実際には、本例では、添字配列４６０及び中間参照配列５１０は、図６に４１０、４１１、４１２、４１３によって示されるように４分割され、４台のプロセッサＣＰＵ−０、ＣＰＵ−１、ＣＰＵ−２及びＣＰＵ−３に割り当てられる。よって、ＣＰＵのアクセス領域が限定されることによりキャッシュヒット率が高まると共に、４台のＣＰＵがループ変数ｉに関して、並列処理を行うので、処理の高速化も達成される。【００４６】
次に、図７を参照して、本発明の第１の実施形態による、２段のインデックス配列７１０及び７２０を介してアクセスされる間接参照配列７３０を直接参照配列７４０に変換する方法を説明する。【００４７】
インデックス配列７１０及び７２０と間接参照配列７３０は、実際には、大規模配列であるが、本例では、説明を簡単にするためインデックス配列の要素の個数は１６個、間接参照配列の要素の個数は１５個である。このような大規模配列をアクセスするとき、プロセッサのキャッシュミスが頻繁に発生するので、直接参照配列７４０を生成するには非常に長時間を要する。これらのキャッシュミスは、処理の低速化の原因となる。したがって、キャッシュミスを低減する方法が非常に重要である。以下では、インデックス配列の段数が２段である場合について、本発明の第２の実施形態による方法を説明するが、この方法の原理が３段以上のインデックス配列にも適用できることは明白である。【００４８】
既に説明したように、マルチコアシステムやマルチプロセッサシステムは、本発明による方法を効率的に実行することが可能であるので、以下では、複数台のＣＰＵ、特に、ＣＰＵ−０とＣＰＵ−１の２台のプロセッサが共有メモリにアクセスするシステムに関して説明する。なお、インデックス配列Ｉ１及びＩ２の要素は整数型のデータである。間接参照配列Ａの要素は任意のデータ型を取り得る。なお、プロセッサ間（または、コア間）のキャッシュ整合性は、一般に、ハードウェアによってサポートされているので、本明細書では特に言及しない。【００４９】
図８は、本発明の第２の実施形態による方法のフローチャートである。同図に示されるように、本発明の第２の実施形態による方法は、最初に、インデックス配列７２０中の要素の値を上位桁と下位桁に分ける基数を定める（ステップ８０２）。基数については本発明の第１の実施形態に関して既に説明した通りである。【００５０】
次に、本発明の第２の実施形態による方法は、上位桁の値に関して、累積度数分布を取得するため、２台のプロセッサを用いて、インデックス配列７２０中の要素の上位桁の値の個数をカウントし（ステップ８０４）、２台のプロセッサを用いて、インデックス配列７２０中の要素の上位桁の値の個数を累計数化する（ステップ８０６）。【００５１】
本発明の第２の実施形態による方法は、次に、上述の添字配列及び要素配列を生成するため、２台のプロセッサを用いて、インデックス配列７２０の添字及びインデックス配列７２０中の要素をそれぞれ添字配列及び要素配列へ転送する（ステップ８０８）。【００５２】
さらに、本発明の第２の実施形態による方法は、上述の中間参照配列を生成するため、２台のプロセッサを用いて、要素配列中の要素の値を添字として間接参照配列７３０の要素をフェッチする（ステップ８１０）。【００５３】
続いて、本発明の第２の実施形態による方法は、上述の直接参照配列を生成するため、２台のプロセッサを用いて、フェッチされた間接参照配列を添字配列の要素の値の順序に従って再配置する（ステップ８１２）。これにより、１段目のインデックス配列について、間接参照配列から直接参照配列への変換が終了する。【００５４】
次に、すべてのインデックス配列７１０の処理が終了したかどうかを判定する（ステップ８１４）。すべてのインデックス配列の処理が終了しているならば、最後に生成された直接参照配列が最終的に出力される。もし、すべてのインデックス配列の処理が終了していないならば、直前に生成された直接参照配列を新たな間接参照配列とみなして、ステップ８０２へ戻る（ステップ８１６）。【００５５】
以下では、本発明の第２の実施形態をより詳細に説明する。図９は、本発明の第２の実施形態による方法のステップ８０４の説明図である。【００５６】
第１のインデックス配列７２０は、添字０から７までの前半部分９０１と添字８から１５までの後半部分９０２に分割され、ＣＰＵ−０が前半部分を受け持ち、ＣＰＵ−１が後半部分を受け持つ。たとえば、ＣＰＵ−０用のカウント配列９１０をＸ０、ＣＰＵ−１用のカウント配列９１１をＸ１で表すと、Ｘ０、Ｘ１は次のようにカウントアップされる。【００５７】
上述のように基数は４に設定されているので、ＣＰＵ−０は、
Ｉ１［０］＝１２（１０）＝３０（４）
であるので、Ｉ１［０］の上位桁の値３に対応するＸ０［３］をカウントアップする。【００５８】
Ｘ０［３］＋＋
同様に、ＣＰＵ−１は、
Ｉ１［８］＝２（１０）＝０２（４）
であるので、Ｘ１［０］をカウントアップする。【００５９】
ＣＰＵ−０とＣＰＵ−１がインデックス配列Ｉ１に対し、このようなカウントアップ処理を並列に適用することにより、ＣＰＵ−０用のカウント配列９２０とＣＰＵ−１用のカウント配列９２１とが得られる。【００６０】
次に、カウント配列を累積度数分布配列に変換する処理を説明する。図１０は、本発明の第２の実施形態による方法のステップ８０６の説明図である。ＣＰＵ−０用のカウント配列９２０とＣＰＵ−１用のカウント配列９２１を用いて、ＣＰＵ−０用の累積度数分布配列１０１０とＣＰＵ−１用の累積度数分布配列１０１１が生成される。本例では、ＣＰＵ−０用の累積度数分布配列をＹ０、ＣＰＵ−１用の累積度数分布配列をＹ１とし、ｉをループ変数（ｉ＝０，１，２）とすると、カウント配列から累積度数分布配列を生成する処理、すなわち、累計数化処理は、
Ｙ０［０］＝０
Ｙ１［ｉ］＝Ｙ０［ｉ］＋Ｘ０［ｉ］
Ｙ０［ｉ＋１］＝Ｙ１［ｉ］＋Ｘ１［ｉ］
と表すことができる。【００６１】
上述の累計数化処理は、１台のＣＰＵによって実行される形で説明されているが、累計数化処理は複数台のＣＰＵで分担して並列に実行することも可能である。具体的には、累積度数分布配列Ｙ０及びＹ１を先頭から順番に複数台のＣＰＵに割り当てる。本例では、たとえば、ＣＰＵ−０は、Ｙ０［０］、Ｙ１［０］、Ｙ０［１］及びＹ１［１］を計算し、ＣＰＵ−１は、Ｙ０［２］、Ｙ１［２］、Ｙ０［３］、Ｙ１［３］を計算する。図１１は、本発明の第２の実施形態による方法のステップ８０６の一変形例の説明図である。【００６２】
ＣＰＵ−０及びＣＰＵ−１は、カウント配列Ｘ０、Ｘ１の担当範囲１１１０及び１１１１に関して作業配列１１２０を計算する。すなわち、ＣＰＵ−０は添字ｉ＝０、１に関して、ＣＰＵ−１は添字ｉ＝２，３に関して、作業配列：
Ｚ０［ｉ］＝Ｘ０［ｉ］＋Ｘ１［ｉ］
を計算する。【００６３】
累積度数分布配列Ｙ０及びＹ１は、
ＣＰＵ−０が担当する
Ｙ０［０］＝０
Ｙ１［０］＝Ｘ０［０］
Ｙ０［１］＝Ｚ０［０］
Ｙ１［１］＝Ｙ０［１］＋Ｘ０［１］
と、ＣＰＵ−１が担当する
Ｙ０［２］＝Ｚ０［０］＋Ｚ０［１］
Ｙ１［２］＝Ｙ０［２］＋Ｘ０［２］
Ｙ０［３］＝Ｚ０［０］＋Ｚ０［１］＋Ｚ０［２］
Ｙ１［３］＝Ｙ０［３］＋Ｘ０［３］
とにより計算される。【００６４】
次に、インデックス配列７２０の添字と要素を添字配列と要素配列に転送する。転送演算の出力、すなわち、添字配列と要素配列は、本例では、４個のチャンクに分離される。チャンクは、要素配列の上位２ビットによって決まるので、チャンク間では、要素配列の要素の値は、チャンク０、チャンク１、チャンク２、チャンク３の順に大きくなる。しかし、チャンク内では、要素配列の要素の値は一定の順序にならない、すなわち、ランダムである。一方、この転送により、チャンク内では、添字配列の要素の値は昇順になることが重要である。図１２を参照して、本発明の第２の実施形態による方法のステップ８０８を説明する。【００６５】
インデックス配列７２０は、ＣＰＵ−０の受け持ち範囲９０１とＣＰＵ−１の受け持ち範囲９０２に分割される。ＣＰＵ−０は、ＣＰＵ−０用の累積度数分布配列Ｙ０を使用して、インデックス配列７２０の添字及び要素をそれぞれ添字配列Ｃ及び要素配列Ｄに転送する。同様に、ＣＰＵ−１は、ＣＰＵ−１用の累積度数分布配列Ｙ１を使用して、インデックス配列７２０の添字及び要素をそれぞれ添字配列Ｃ及び要素配列Ｄに転送する。【００６６】
より具体的には、ｉをループ変数、ｘ  ｄｉｖ  ｙは、ｘをｙで割った商を求める整数演算とすると、ＣＰＵ−０は、
Ｃ［Ｙ０［Ｉ１［ｉ］  ｄｉｖ  ４］］＝ｉ
Ｄ［Ｙ０［Ｉ１［ｉ］  ｄｉｖ  ４］］＝Ｉ１［ｉ］
Ｙ０［Ｉ１［ｉ］  ｄｉｖ  ４］＋＋
を実行する。同様に、ＣＰＵ−１は、
Ｃ［Ｙ１［Ｉ１［ｉ］  ｄｉｖ  ４］］＝ｉ
Ｄ［Ｙ１［Ｉ１［ｉ］  ｄｉｖ  ４］］＝Ｉ１［ｉ］
Ｙ１［Ｉ１［ｉ］  ｄｉｖ  ４］＋＋
を実行する。【００６７】
図１２の累積度数分布配列１０１０、１０１１と添字配列１２２０と要素配列１２３０は、この転送処理の最初のステップを表し、累積度数分布配列１２１０、１２１１と添字配列１２２１と要素配列１２３１は、この転送処理の最後のステップの終了後の状態を表す。チャンクは、同図には、チャンク１２４０、１２４１、１２４２、１２４３として示されている。チャンク１２４０は、
Ｉ１［ｉ］  ｄｉｖ  ４  ＝０、
すなわち、Ｉ１［ｉ］＝０，１，２，３に対応する。チャンク１２４１は、
Ｉ１［ｉ］  ｄｉｖ  ４  ＝１、
すなわち、Ｉ１［ｉ］＝４，５，６，７に対応する。チャンク１２４２は、
Ｉ１［ｉ］  ｄｉｖ  ４  ＝２、
すなわち、Ｉ１［ｉ］＝８，９，１０，１１に対応する。チャンク１２４３は、
Ｉ１［ｉ］  ｄｉｖ  ４  ＝３、
すなわち、Ｉ１［ｉ］＝１１，１２，１３，１４に対応する。【００６８】
次に、図１３を参照して、間接参照配列７３０の要素を取り出す、本発明の第２の実施形態による方法のステップ８１０を説明する。間接参照配列はＡで表し、間接参照配列の要素を取り出して新たに生成される中間参照配列はＥで表す。この処理は、限定された範囲、すなわち、チャンク１２４０、１２４１、１２４２、１２４３のそれぞれの範囲内で行える。したがって、キャッシュヒット率が高まる。さらに、チャンクをチャンク単位でＣＰＵに割り当てることにより、各ＣＰＵが並列に中間参照配列Ｅに要素を格納できるので、処理が高速化される。【００６９】
この処理は、ループ変数をｉ、添字配列をＣ、要素配列をＤ、間接参照配列をＡ、中間参照配列をＥとすると、
Ｅ［ｉ］＝Ａ［Ｄ［ｉ］］
として記述される。図１３には、最終的な中間参照配列１３１０が示されている。この中間参照配列１３１０は、要素配列１２３１のチャンクに対応するチャンク１３２０、１３２１、１３２２、１３２３に分割されている。よって、中間参照配列の一つのチャンク内の要素の順序は、元の間接参照配列７３０の順序と入れ替わることがあるが、中間参照配列のあるチャンク内の要素が別のチャンク内の要素と入れ替わることはない。【００７０】
次に、図１４を参照して、中間参照配列を直接参照配列に並べ替える、本発明の第２の実施形態による方法のステップ８１２を説明する。添字配列はＣ、中間参照配列はＥ、直接参照配列はＢ１で表されている。この処理は、ループ変数をｉとすると、
Ｂ１［Ｃ［ｉ］］＝Ｅ［ｉ］
として記述される。【００７１】
この処理は、添字配列１２２１及び中間参照配列１３１０をチャンク１３２０、１３２１、１３２２、１３２３に分割し、チャンク単位でＣＰＵに割り当てることにより、並列的に実行される。本例では、ＣＰＵ−０の受け持ち範囲１４１０はチャンク１３２０とチャンク１３２１であり、ＣＰＵ−１の受け持ち範囲１４１１はチャンク１３２２とチャンク１３２３である。【００７２】
図１４に示された直接参照配列１４２０は、
Ｂ１［Ｃ［１２］］＝Ｅ［１２］、すなわち、Ｂ１［０］＝１１２、及び、
Ｂ１［Ｃ［０］］＝Ｅ［０］、すなわち、Ｂ１［１］＝１００
が実行された状態を表している。図１４の直接参照配列１４３０は、さらに、
Ｂ１［Ｃ［１］］＝Ｅ［１］、すなわち、Ｂ１［２］＝１０１、及び、
Ｂ１［Ｃ［１３］］＝Ｅ［１３］、すなわち、Ｂ１［３］＝１１２
が実行された状態を表している。本例では、直接参照配列Ｂ１の先頭から順番に要素の値が格納されているが、その他の格納順序でも構わない。【００７３】
図１４の直接参照配列１４４０は、本発明の第２の実施形態による方法の１段目のインデックス配列Ｉ１を介してアクセスされる間接参照配列Ａを直接参照配列Ｂ１に変換した結果を表している。【００７４】
本発明の第２の実施形態においては、２段目のインデックス配列Ｉ２が存在する。したがって、図１４で得られた直接参照配列Ｂ１を新たな間接参照配列Ｂ１とみなし、図９乃至１４を参照して説明した方法を適用することにより、インデックス配列Ｌ２を介してアクセスされる間接参照配列Ｂ１を直接参照配列Ｂ２に変換することが可能である。図１５は、本発明の第２の実施形態による方法の２段目の変換結果、すなわち、直接参照配列１５００を示す図である。【００７５】
本発明の第２の実施形態による方法は、３段以上のインデックス配列が存在する場合にも拡張され、適用されることは当業者に明らかである。【００７６】
さらに、上記の例では、インデックス配列Ｉ１、Ｉ２を介して参照される間接参照配列Ａを直接参照配列Ｂに変換する際に、
（ステップ１）インデックス配列Ｉ１を介して参照される間接参照配列Ａを直接参照配列Ｂ１に変換し、
（ステップ２）インデックス配列Ｉ２を介して参照される間接参照配列Ｂ１を直接参照配列Ｂに変換する、
という手順で直接参照配列Ｂを得ている。しかし、本発明はこのような手順に現手されることはなく、インデックス配列Ｉ１を間接参照配列とみなして、
（ステップ１）インデックス配列Ｉ２を介して参照される間接参照配列Ｉ１を直接参照配列Ｂ２に変換し、次に、得られた直接参照配列Ｂ２をインデックス配列とみなして、
（ステップ２）インデックス配列Ｂ２を介して参照される間接参照配列Ａを直接参照配列Ｂに変換する、
という手順によっても直接参照配列を得ることができる。なぜならば、インデックス配列Ｉ１は整数配列であるため、インデックス配列Ｉ１を変換して得られる直接参照配列Ｂ２もまた整数配列であり、インデックス配列とみなすことができるからである。【００７７】
このような演算順序の結合則は、一般にｎ段の間接参照においても成立する。【００７８】
最後に本発明の好ましい実施形態による、インデックス配列を介してアクセスされる間接参照配列を直接参照配列に変換する方法をコンピュータに実行させるためのコンピュータプログラムを、Ｄｕａｌ−Ｃｏｒｅ  Ｉｎｔｅｌ（登録商標）  Ｘｅｏｎ（登録商標）  ３．１６ＧＨｚ（１ＭＢ  Ｃａｃｈｅ×２）を２個使用する装置、すなわち、４台のコアと４ＭＢのキャッシュを使用する装置に実行させた実施例を説明する。図１６は、本実施例で使用された５０００万行からなる大規模なインデックス配列１６００を示す図である。同図には、０から４９，９９９，９９９までの添字と、添字に対応する５０，０００，０００種類のアクセス先、すなわち、間接参照配列の添字が示されている。【００７９】
本発明の好ましい実施形態による方法で、チャンクのサイズを２の１６乗（６５，５３６）とし、インデックス配列１６００によって指定されるアクセス先に格納された要素（整数）を取得するための所要時間は１，７３１，４７８μ秒であった。これに対して、インデックス配列１６００を先頭から順番に走査して、インデックス配列１６００によって指定されるアクセス先に格納された要素（整数）を取得するために要した時間は７，７４６，５００μ秒であった。よって、本発明の好ましい実施形態によれば、所要時間が４分の１以下に短縮された。【００８０】
このように、部分的なソートを利用して間接参照を直接参照に変換する本発明のアルゴリズムは、間接参照をそのまま実行するよりも所要時間が大幅に削減されることがわかった。その理由は、部分的なソートを利用する本発明のアルゴリズムが、
（１）ＣＰＵのマルチコア化
（２）ＣＰＵのクロックの驚異的な上昇
（３）ＣＰＵのキャッシュアクセスと外部メモリアクセスとの間のパフォーマンスの乖離
という近年のハードウェア技術の傾向と、
（４）ＣＰＵのアクセス範囲を限定するとキャッシュヒット率が高くなる
というキャッシュメモリの特徴とを考慮して設計されているためである。【００８１】
本発明は、以上の実施の形態に限定されることなく、請求の範囲に記載された発明の範囲内で種々の変更が可能であり、それらもまた本発明の範囲内に包含されるものであることは言うまでもない。
【産業上の利用可能性】
【００８２】
以上のように、本発明にかかるメモリ間接参照をメモリ直接参照に変換する方法及び装置は、メモリ共有型並列処理システムにおける大規模データの処理のための基本的な演算処理として有用であり、特に、大規模データの検索、集計、ソートなどに用いるのに適している。
【図１】
2008136066.tif 000003
【図２】
2008136066.tif 000004
【図３】
2008136066.tif 000005
【図４】
2008136066.tif 000006
【図５】
2008136066.tif 000007
【図６】
2008136066.tif 000008
【図７】
2008136066.tif 000009
【図８】
2008136066.tif 000010
【図９】
2008136066.tif 000011
【図１０】
2008136066.tif 000012
【図１１】
2008136066.tif 000013
【図１２】
2008136066.tif 000014
【図１３】
2008136066.tif 000015
【図１４】
2008136066.tif 000016
【図１５】
2008136066.tif 000017
【図１６】
2008136066.tif 000018
【手続補正書】
【提出日】平成22年3月19日(2010.3.19)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
共有メモリにアクセスする複数台のプロセッサを含むシステムにおいて、インデックス配列を介してアクセスされる間接参照配列を直接参照配列に変換する方法であって、
上記インデックス配列中の要素の値を上位桁と下位桁に分ける基数を定めるステップと、
上記複数台のプロセッサを用いて、上記インデックス配列中の上記要素の上位桁の値の累積度数分布を並列的に数え上げるステップと、
上記複数台のプロセッサを用いて、上記インデックス配列の添字及び上記インデックス配列中の要素を上記累積度数分布に基づいて並列的に並べ替えることにより、上記インデックス配列の添字及び上記インデックス配列中の要素をそれぞれ添字配列及び要素配列に並列的に格納するステップと、
上記複数台のプロセッサを用いて、上記要素配列中の要素の値を添字として上記間接参照配列の要素を並列的に読み出し、上記読み出された要素を上記添字配列と同じサイズの中間参照配列に並列的に格納するステップと、
上記複数台のプロセッサを用いて、上記添字配列の要素及び対応する上記中間参照配列の要素を並列的に読み出し、上記添字配列の要素を添字として使用して上記中間参照配列の要素を上記直接参照配列に並列的に格納するステップと、
を含む方法。
【請求項２】
共有メモリにアクセスする複数台のプロセッサを含み、インデックス配列を介してアクセスされる間接参照配列を直接参照配列に変換する装置であって、
上記インデックス配列中の要素の値を上位桁と下位桁に分ける基数を定める手段と、
上記複数台のプロセッサを用いて、上記インデックス配列中の上記要素の上位桁の値の累積度数分布を並列的に数え上げる手段と、
上記複数台のプロセッサを用いて、上記インデックス配列の添字及び上記インデックス配列中の要素を上記累積度数分布に基づいて並列的に並べ替えることにより、上記インデックス配列の添字及び上記インデックス配列中の要素をそれぞれ添字配列及び要素配列に並列的に格納する手段と、
上記複数台のプロセッサを用いて、上記要素配列中の要素の値を添字として上記間接参照配列の要素を並列的に読み出し、上記読み出された要素を上記添字配列と同じサイズの中間参照配列に並列的に格納する手段と、
上記複数台のプロセッサを用いて、上記添字配列の要素及び対応する上記中間参照配列の要素を並列的に読み出し、上記添字配列の要素を添字として使用して上記中間参照配列の要素を上記直接参照配列に並列的に格納する手段と、
を含む装置。
【請求項３】
共有メモリにアクセスする複数台のプロセッサを含むコンピュータにロードされ、インデックス配列を介してアクセスされる間接参照配列を直接参照配列に変換するコードを上記コンピュータに実行させるプログラムであって、
上記インデックス配列中の要素の値を上位桁と下位桁に分ける基数を定めるコードと、
上記複数台のプロセッサを用いて、上記インデックス配列中の上記要素の上位桁の値の累積度数分布を並列的に数え上げるコードと、
上記複数台のプロセッサを用いて、上記インデックス配列の添字及び上記インデックス配列中の要素を上記累積度数分布に基づいて並列的に並べ替えることにより、上記インデックス配列の添字及び上記インデックス配列中の要素をそれぞれ添字配列及び要素配列に並列的に格納するコードと、
上記複数台のプロセッサを用いて、上記要素配列中の要素の値を添字として上記間接参照配列の要素を並列的に読み出し、上記読み出された要素を上記添字配列と同じサイズの中間参照配列に並列的に格納するコードと、
上記複数台のプロセッサを用いて、上記添字配列の要素及び対応する上記中間参照配列の要素を並列的に読み出し、上記添字配列の要素を添字として使用して上記中間参照配列の要素を上記直接参照配列に並列的に格納するコードと、
を含むプログラム。
【請求項４】
共有メモリにアクセスする複数台のプロセッサを含む対称型マルチプロセッサシステムにおいて、インデックス配列を介してアクセスされる間接参照配列を直接参照配列に変換する方法であって、
上記複数台のプロセッサを用いて、上記インデックス配列中の要素を上位桁の値に従って並べ替え、上記インデックス配列を添字配列及び要素配列に変換するステップと、
上記複数台のプロセッサを用いて、上記要素配列中の要素を添字として使って上記間接参照配列中の要素を読み出し、上記読み出された要素を、上記要素配列中の要素に対応する添字を使って、中間参照配列に格納するステップと、
上記複数台のプロセッサを用いて、上記添字配列及び上記中間参照配列から同じ添字を使ってそれぞれの要素を読み出し、上記添字配列から読み出された要素を添字として使って、上記中間参照配列から読み出された要素を上記直接参照配列に格納するステップと、
を含む方法。
【手続補正２】
【補正対象書類名】明細書
【補正対象項目名】００１４
【補正方法】削除
【補正の内容】
【手続補正３】
【補正対象書類名】明細書
【補正対象項目名】００１５
【補正方法】削除
【補正の内容】
【国際調査報告】
2008136066.tif 000019
2008136066.tif 000020