(57)【特許請求の範囲】
【請求項１】
並列的に動作する複数のプロセッサをそなえ、該複数のプロセッサが一つの業務に参加し全体として該業務を実行するとともに、
前記の各プロセッサにおいて、該業務における処理対象のデータを、個々に独立して処理を受けることが可能なデータ単位（以下、タプルという）として取り扱う並列プロセッサ装置であって、
前記処理対象のデータを分散して予め格納するための第１プロセッサ群と、
該第１プロセッサ群から送信されてくる前記処理対象のデータを、同一種別のタプルのみの集合体であるバケットに分割した状態で格納するための第２プロセッサ群と、
前記処理対象のデータを、該第１プロセッサ群から受信して一時的に格納した後に、該第２プロセッサ群へ送信するための中間プロセッサ群とが該複数のプロセッサに包含されており、
該第１プロセッサ群から該中間プロセッサ群へのデータ送信時に、前記処理対象のデータを、それぞれ複数種別のタプルの集合体である複数組のバケットグループに分割して該中間プロセッサ群に一時的に格納する第１分割処理を行なってから、
該中間プロセッサ群から該第２プロセッサ群へのデータ送信時に、該第１分割手段により分割されて該中間プロセッサ群に一時的に格納される該複数組のバケットグループを、各バケットグループ毎に読み出して同一種別のタプルのみの集合体であるバケットに分割して該第２プロセッサ群に格納する第２分割処理を行なうことを特徴とする、並列プロセッサ装置。
【請求項２】
該第１分割処理を行なうべく、前記処理対象のデータをなす各タプルを分類するためのグループ化関数が予め設定されており、
該第１分割処理として、各タプルに対して該グループ化関数を適用して得られた、該グループ化関数の出力値としてのバケット識別子に基づいて、バケットグループ分割処理を行なうことを特徴とする、請求項１記載の並列プロセッサ装置。
【請求項３】
該第２分割処理を行なうべく、前記処理対象のデータをなす各タプルを分類するためのグループ化関数が予め設定されており、
該第２分割処理として、各タプルに対して該グループ化関数を適用して得られた、該グループ化関数の出力値としてのバケット識別子に基づいて、バケット分割処理を行なうことを特徴とする、請求項１または請求項２に記載の並列プロセッサ装置。
【請求項４】
該第１プロセッサ群，該第２プロセッサ群および該中間プロセッサ群の動作状態を管理して該第１プロセッサ群，該第２プロセッサ群および該中間プロセッサ群の動作を同期させながら該第１分割処理および該第２分割処理を実行させるための制御用プロセッサが、該複数のプロセッサに包含されていることを特徴とする、請求項１〜請求項３のいずれか１項に記載の並列プロセッサ装置。
【請求項５】
同一バケットグループに属するタプルを、該中間プロセッサ群に属する各プロセッサに対して均一またはほぼ均一に送付して、該中間プロセッサ群に属する各プロセッサにおける負荷を平坦化するための第１負荷平坦化手段がそなえられ、該第１分割処理に際して該第１負荷平坦化手段により該中間プロセッサ群に属する各プロセッサにおける負荷を平坦化することを特徴とする、請求項１〜請求項４のいずれか１項に記載の並列プロセッサ装置。
【請求項６】
同一バケットグループに属するタプルを、該第２プロセッサ群に属する各プロセッサに対して均一またはほぼ均一に送付して、該第２プロセッサ群に属する各プロセッサにおける負荷を平坦化するための第２負荷平坦化手段がそなえられ、該第２分割処理に際して該第２負荷平坦化手段により該第２プロセッサ群に属する各プロセッサにおける負荷を平坦化することを特徴とする、請求項１〜請求項５のいずれか１項に記載の並列プロセッサ装置。
【発明の詳細な説明】
【０００１】
（目次）
産業上の利用分野
従来の技術（図９〜図１５）
発明が解決しようとする課題
課題を解決するための手段（図１）
作用（図１）
実施例（図２〜図８）
発明の効果
【０００２】
【産業上の利用分野】
本発明は、複数のプロセッサが同時並列的に動作して所定の業務を実行する並列計算機システム等の並列プロセッサ装置に関する。
【０００３】
【従来の技術】
まず、一般的な並列計算機システム（並列プロセッサ装置）の概要について説明する。なお、この概要は、後述する本発明にも共通している。
この一般的な並列計算機システム（本発明が適用されるシステム）は、次の条件を満たすものである。
【０００４】
システムを構成する複数のプロセッサは、メモリおよび二次記憶装置を共用しない。つまり、あるメモリやある二次記憶装置は、システムの動作中、ある１プロセッサによってのみアクセスされる。
また、複数のプロセッサ間は、任意のプロセッサから任意のプロセッサへのデータ転送が可能なネットワーク機構により相互接続されている。
【０００５】
ここで、図９により一般的な並列計算機システムの構成例について説明すると、図９において、１０−１〜１０−Ｎはそれぞれ並列計算機システムを構成するプロセッサモジュール（以下、ＰＭと略記する場合がある）で、これらのＰＭ１０−１〜１０−Ｎは、並列的に動作するもので、その相互間は、ネットワーク機構１１により通信可能に接続されている。
【０００６】
ネットワーク機構１１は、ＰＭ１０−１〜１０−Ｎ間の任意長データの全点対全点通信を論理的に可能とするものである。このネットワーク機構１１は、実際には、固定長バケットをＰＭ相互間で複数回数交換することにより前記通信を行なうものであってもよいし、ミクロな時間幅ではＰＭ相互間のある結合関係が輻輳現象などにより不可能（輻輳を起こした一方の通信が待たされ遅延する）であってもよいが、マクロな視点で任意のプロセッサ相互間の任意長のデータ転送が可能なものとする。
【０００７】
そして、ＰＭ１０−１〜１０−Ｎは、それぞれ、ＣＰＵ２０，メモリ２１，アクセス機構２２およびＩ／Ｏ機構２３を含んで構成されている。
ここで、ＣＰＵ２０は、各ＰＭ１０−１〜１０−Ｎに内蔵され、アクセス機構２２やＩ／Ｏ機構２３の動作を制御するほか、メモリ２１上に存在するデータの読出やメモリ２１上へのデータの書込を行なう機能を有している。
【０００８】
メモリ２１は、各ＰＭ１０−１〜１０−Ｎに内蔵されており、このメモリ２１上の任意の位置にある任意長のデータブロックに対して、ＣＰＵ２０，アクセス機構２２およびＩ／Ｏ機構２３からアクセスすることができるようになっている。
アクセス機構２２は、各ＰＭ１０−１〜１０−Ｎに内蔵され、ＰＭ１０−１〜１０−Ｎの相互間を接続するネットワーク機構１１へのアクセスを行なうためのものである。このアクセス機構２２は、ＣＰＵ２０から指定された自メモリ上位置（メモリ２１のアドレス）に存在する任意長のデータブロックをＣＰＵ２０から指定された他プロセッサに対して転送する機能と、ネットワーク機構１１から与えられたデータブロックを自ＣＰＵ２０から指定された自メモリ上位置に格納する機能とを（少なくとも論理的に）有している。
【０００９】
Ｉ／Ｏ機構２３は、各ＰＭ１０−１〜１０−Ｎに内蔵され、各ＰＭ１０−１〜１０−Ｎに接続された二次記憶装置２４へのアクセスを行なうためのものである。このＩ／Ｏ機構２３は、ＣＰＵ２０から指定された自メモリ上位置に存在する任意長のデータブロックをＣＰＵ２０から指定された二次記憶装置２４の指定領域に書き込む機能と、ＣＰＵ２０から指定された二次記憶装置２４の指定領域におけるデータブロックをＣＰＵ２０から指定された自メモリ上位置に書き込む機能とを（少なくとも論理的に）有している。
【００１０】
なお、各ＰＭ１０−１〜１０−Ｎに接続された二次記憶装置２４は、例えば図１２を参照しながら後述するような磁気ディスク装置で、各ＰＭ１０−１〜１０−Ｎに複数台接続されていてもよい。また、静的な意味では１台の二次記憶装置２４が複数のＰＭに対してアクセスバスをもっていてもよい。しかし、ここで、述べる範囲の処理に関しては、１台の二次記憶装置２４にアクセスするＰＭ台数は１であるとする。
【００１１】
次に、上述した一般的な並列計算機システムが行なう処理の概要（当該処理が満たす条件）について、図１０および図１１により説明する。なお、この処理の概要は、後述する本発明にも共通している。
上述した一般的な並列計算機システムにおける論理的な処理を、図１０により説明する。
【００１２】
ある１ファイル、あるいは、ＲＤＢ（Ｒｅｌａｔｉｏｎａｌ  ＤａｔａＢａｓｅ）で定義される所の１テーブルがあるものとする。以下、ＲＤＢ処理を例として説明する。これが図１０に示すソーステーブル（Ｓｏｕｒｃｅ  Ｔａｂｌｅ）４００である。
ソーステーブル４００から１つのタプル（個々に独立して処理を受けることが可能なデータ単位）５００が抽出され、このタプル５００に対して分類関数ｆ〔グループ化関数（Ｇｒｏｕｐｉｎｇ  Ｆｕｎｃｔｉｏｎ）４０１〕が適用される。
【００１３】
その結果（分類関数ｆの出力値）により、このタプル５００がいずれのタプルグループ〔バケット（Ｂｕｃｋｅｔ）４０２〜４０４〕に属するかが決定される。タプル５００は、決定されたバケット４０２〜４０４に付加される。
このようにして生成されたバケット群は、二次記憶装置（図９の符号２４参照）に格納され、各バケット４０２〜４０４毎に独立に適用される次段処理（Ｎｅｘｔ  Ｐｒｏｃｅｓｓ）４０５〜４０７の入力情報となる。
【００１４】
図１０にて説明した処理は、前述した一般的な並列計算機システムの上では図１１に示すように実装されているものとする。
即ち、入力テーブル（図１０のソーステーブル４００）８００は、第１プロセッサ群６０に属する各ＰＭ６００〜６０２に接続された二次記憶装置群に分割格納されている。各ＰＭ６００〜６０２の配下にある、入力テーブル８００の部分集合９００〜９０２をサブテーブルと呼ぶ。
【００１５】
図１０にて前述したタプルの抽出および分類関数の適用は、第１のプロセッサグループ６０に属する個々のＰＭ６００〜６０２により、並列的に実行される。タプル抽出の対象は、各サブテーブル９００〜９０２である。
分類関数の適用によって分類されたタプル群（同一種別のタプルの集合体）は、最終的に第２プロセッサ群７０に格納されなければならない。ここで、第１プロセッサ群６０と第２プロセッサ群７０とが排他的関係にあることは要求されない。つまり、第１プロセッサ群６０と第２プロセッサ群７０とは、全く同じプロセッサ群であってもよいし、一部のプロセッサが重複する関係であってもよいし、全く異なるものであってもよい。
【００１６】
同一種別のタプルからなる１つのバケットは、第２プロセッサ群７０に属する１つのプロセッサに集中して格納されてもよいし、第２プロセッサ群７０に属するある台数のプロセッサに分割して格納されてもよい。ここでの要求は、「次段処理の実行時に、特定のバケットのデータのみを第２プロセッサ群７０から選択して読み出すことができること」である。これを実現するデータ構造により、データ（第１プロセッサ群６０に格納されていた入力テーブル８００）は、図１１に示すように、第２プロセッサ群７０に属する各ＰＭ７００〜７０２（各二次記憶装置２４）に、複数の部分１０００〜１２９９に分割されて格納される。
【００１７】
ここで注意すべき点は、第１プロセッサ群６０と第２プロセッサ群７０との間の矢印は必ずしもネットワーク上の直接交信を意味していないことである。図１１は、入力情報の格納形態と出力（結果）情報の格納形態とを示そうとするものであって、その間の転送処理に対して要求がないことに着目するためのものである。以降に説明する本発明は、この図１１に示される第１プロセッサ群６０から第２プロセッサ群７０への矢印を如何に実現するかに関する技術である。
【００１８】
ところで、ＲＤＢ処理において、分類関数（例えばハッシングや特定カラムの値による分類）によりタプル群を複数のグループ（バケット）に分割する作業は極めて一般的である。例えば、ＳＱＬ文の“Ｇｒｏｕｐ  Ｂｙ”句は、このグループ分割処理を明らかに要求するものであるし、上述のような構成でジョイン（ｊｏｉｎ）演算の代表的方式であるハッシュジョインは、ハッシュ関数によるタプルのグループ分割を特徴としている。
【００１９】
並列データベースマシンや分散データベースシステムと呼ばれるシステムでは、末端ユーザから見て論理的に１つのテーブルであるべきタプル群が、メモリや二次記憶装置を直接共用しない複数のプロセッサに分割される場合が多い。これは、例えば同じテーブルへの条件検索処理が、テーブルの部分集合に対して同一の検索処理を行なうプロセッサ群による実行により大幅に性能改善されるなどの効果を狙ったものである。
【００２０】
このような環境で、上記グループ分割処理は、これもまた各プロセッサが自身配下のテーブルの部分集合（以下、サブテーブルという）に含まれる全タプルに対して指定された分類関数を適用し、その適用結果を論理的に和すること、つまり「結果を格納すべきプロセッサ群に、それぞれが生成したサブテーブルのグループ分割された結果（サブバケット）を送付し、その結果を受信したプロセッサ側で同一バケットに属するサブバケットどうしを連結して最終的にバケットを作成し、これを自身の二次記憶装置に格納すること」により実現される。
【００２１】
このとき、以下に記述する二次記憶装置２４の特性▲１▼〜▲３▼から、このグループ分割処理によって生成された各バケットの二次記憶装置への格納方式によって、大きな処理性能差が、該グループ分割処理にも次段処理（つまり生成されたバケット個々を読み出すことにより行なわれる次の処理）にも発生する。
なお、図１２は、代表的な二次記憶装置２４としての磁気ディスク装置を模式的に示すもので、図１２において、３００〜３０３はそれぞれ高速回転する磁気媒体、３０４は磁気媒体３００〜３０３の回転軸で、この回転軸３０４は、図示しないモータに結合されている。また、３０５〜３１２は磁気ヘッドおよびヘッドアームからなるヘッド部で、これらのヘッド部３０５〜３１２は、各磁気媒体３００〜３０３を両面から挟むように配置されており、外部から与えられたアドレスの一部により選択されたヘッド部３０５〜３１２のみが磁気媒体３００〜３０３のいずれかに対するデータ授受を行なうことができるようになっている。さらに、３１３は各ヘッド部３０５〜３１２のヘッドアームを支持するための支持部材であり、この支持部材３１３が、外部から与えられたアドレスのデータを読み取ることのできる位置まで、ヘッド部３０５〜３１２を移動させるようになっている。
【００２２】
▲１▼図１２にその概要が示される通り、代表的な二次記憶装置２４としての磁気ディスク装置は、高速に回転する磁気媒体３００〜３０３のうち、外部から与えられたアドレスの上位で指定されるものが選択された上、その中心からの距離が外部から与えられたアドレスの中位で指定される部分にヘッド部（磁気ヘッド）３０５〜３１２が物理的に移動し、その磁気ヘッドがアクセスする１円周上の、外部から与えられたアドレスの下位で指定される領域に対してデータの書込／読出が行なわれる。
【００２３】
▲２▼上述した現状の磁気ディスク装置では、磁気媒体３００〜３０３の回転速度に比較して、上記ヘッド部３０５〜３１２の位置変更（回転媒体の選択切替も、厳密にはヘッド位置の微調整を必要とするため、これに含まれる）に要する時間が相対的に長い。このため、磁気ディスク装置に対する入出力処理の性能を向上させるためには、ある特定量のデータの入出力に必要なヘッド部３０５〜３１２の移動回数および移動距離を小さくすればする程、効果が大きい。ある容量のデータを格納する時に、このようなヘッドの移動回数および移動距離を最小とする二次記憶装置上の領域を以下では仮に「物理連続な領域」と呼称する。以下の説明では、二次記憶磁気媒体上の特定面積内に固まっていることが「物理連続な領域」の定義ではない。
【００２４】
▲３▼あるＩ／Ｏアクセスがこのような物理連続な領域に対するアクセスであり、そのデータ転送量がある値以上に大きいならば、Ｉ／Ｏ処理の性能はこの二次記憶装置の性能を充分に活用しているということができる。このＩ／Ｏアクセスに関する物理連続な領域に期待される容量は、現状の磁気ディスク装置の場合、数百ＫＢ程度であり、これを下回るとＩ／Ｏ性能は急速に低下する一方、これ以上大きくしても性能の改善効果は小さい。
【００２５】
一般に、データベース（ＤＢ）処理では、扱うデータ量が膨大であるためにＩ／Ｏ性能がその処理性能のほとんどを決定する場合が多い。このため、上述したＩ／Ｏアクセスに関する物理連続な領域の容量の保証が可能であることの効果は大きい。その簡単な例を図１３および図１４に示す。
図１３はアクセス効率の悪いＤＢ処理例を示すもので、図１３の左側には、二次記憶装置２４に記入されるべきタプル群が、Ｉ／Ｏ要求に投入される順序に並んで示されている。今、ここでは、２つの「物理連続な領域」１２００と１２０１とが存在するものとする。図１３に示す例では、物理連続な領域１２００と１２０１とに記入されるべきタプルが交互に投入されるため、この２領域間をヘッドが往復することになり、Ｉ／Ｏ性能は極めて低下してしまう。
【００２６】
一方、図１４は相対的にアクセス効率の良いＤＢ処理例を示すもので、この図１３に示す例では、同一領域に記入されるべきタプルが連続して投入されるため、いわゆる「まとめ書き」が可能であって、領域間のヘッド移動は１回で済むことになる。
従って、少なくとも次段処理実行時の読出性能を保証しようとするならば、１バケットが可能な限り少ない個数の「物理連続な領域」に分割されて格納されているべきである。一方、一般にＤＢ処理では１バケットの容量は数メガバイト程度にはなるので、これら全部を１つの「物理連続な領域」に収めても上記議論から二次記憶装置の性能への寄与は少ない。従って、具体的な要求は次のような２点（Ａ），（Ｂ）となる。
【００２７】
（Ａ）上記Ｉ／Ｏアクセス性能保証のための「物理連続な領域」の容量に関する要求を満足する大きさ（数百ＫＢ程度）を、１Ｉ／Ｏアクセス単位とする。この１Ｉ／Ｏアクセス単位中の全データは、二次記憶装置中の１つの「物理連続な領域」に対して記入されるとともに、該１つの「物理連続な領域」から読み出されることになる。
【００２８】
（Ｂ）バケットデータの書込時、１Ｉ／Ｏアクセス単位中に混在するバケット種別数を可能な限り小さくする。可能ならば、全てのＩ／Ｏアクセス単位中に混在するバケット種別数を１とする。
しかし、上述のような要求▲１▼，▲２▼を満足することは現在まで困難であった。次に説明するように、既存技術では、１つのＰＭに到来する可能性のあるバケット種別が極めて多いため、バケット種別毎に上記Ｉ／Ｏアクセス単位の整数倍の容量のブロッキングバッファを準備することは、現実的でない程巨大なメモリ容量を格納側（受信側である第２プロセッサ群７０）の各ＰＭ７００〜７０２にそなえることを要求することになる。
【００２９】
次に、図１５により既存技術について説明する。
図１５は、図１１に示した第２プロセッサ群７０に属するＰＭ７００〜７０２のうちの一つ（ここではＰＭ７０２）の内部構造を示すものである。
既存技術の特徴は、少なくとも、論理的に図１１における送信側のＰＭ６００〜６０２と受信側（格納側）のＰＭ７００〜７０２との間がネットワークにより直結されている点にある。つまり、タプルやバケットに関して、ＰＭ６００〜６０２の出力ストリームは、特に加工されることなく最終的な格納先であるＰＭ７００〜７０２に送付される。
【００３０】
また、既存技術では、送信側のＰＭ６００〜６０２は、バケットと受信側の各ＰＭ７００〜７０２との対応関係を与えられており、あるバケットに属するタプルを送出する際、その対応関係を満足するＰＭを宛先として陽に指定して送出することになる。
一方、受信側の各ＰＭ７００〜７０２では、図１５に示すように、これら複数の送信側の各ＰＭ６００〜６０２からタプルのストリーム（図１５中の“Ｉｎｐｕｔ  Ｔｕｐｌｅ  Ｓｔｒｅａｍ”参照）としてデータを受理し、そのデータを、各ＰＭ７００〜７０２（図１５中ではＰＭ７０２）が担当すべき各バケットに対して準備されたブロッキングバッファ（Ｂｌｏｃｋｉｎｇ  Ｂｕｆｆｅｒｓ）２１Ａにバケット種別毎に分類して蓄積する。ブロッキングバッファ２１Ａの容量は、少なくとも、上述したＩ／Ｏアクセス単位に、各ＰＭ７００〜７０２が格納すべきバケット種別数を乗算した値となる。なお、ブロッキングバッファ２１Ａの領域は、例えば図９に示したメモリ（主記憶）２１内に設定される。
【００３１】
そして、各ＰＭ７００〜７０２は、Ｉ／Ｏアクセス単位にその蓄積量が達したバケットについてブロッキングバッファ２１Ａの内容（該バケットに対応する部分）を二次記憶装置２４に書き込む。
【００３２】
【発明が解決しようとする課題】
ところが、上述のような方式の場合、格納側のＰＭ７００〜７０２が担当しなければならないバケット数は、一般に極めて多い。ハッシュジョインの場合を例にとると、各ＰＭ７００〜７０２のメモリ容量でデータベース容量を除算した値程度のバケット数が必要になる。例えば１００ＧＢ程度のデータベース容量を６４ＭＢ程度の主記憶（メモリ２１）をもつＰＭで処理しようとする場合には、１６００個程度のバケットが全体として必要になる。
【００３３】
また、受信側のＰＭ７００〜７０２でのバケットとＰＭとの対応関係を制限する、つまりあるバケットは特定の受信側のＰＭのみが処理することになると、予め各バケットの容量を予測することは通常不可能であるために、ＰＭ間で扱うデータ量に著しい不均等が発生する可能性があり、可能ならば１バケットはどのＰＭにも均等に配布することが望ましい。このことは、１つのＰＭが扱うバケット種別の低減が通常困難であることを意味する。
【００３４】
例えば、主記憶容量６４ＭＢのＰＭが格納側のＰＭとして３２台配置された場合、容量１００ＧＢのデータベースを１．６Ｋ個のバケットに分割して格納しなければならないとするならば、同一バケットに属するデータ量が格納側のＰＭ間でほぼ同容量になるように制御すると、１ＰＭ当たり平均バケット数はやはり１．６Ｋ個程度になる。この平均バケット数に、処理に参加するＰＭの台数は関係しない。
【００３５】
上述のような要求を満足するＩ／Ｏアクセス単位がこの場合２５６ＫＢであるとすると、１．６Ｋ個のバケットに対してこれだけの容量を準備することが上記ブロッキングバッファ２１Ａに対して要求されることになるため、４００ＭＢ程度の主記憶（メモリ２１）が必要ということになる。
上述した通り、準備可能な主記憶はこの場合６４ＭＢが上限である。従って、ここで記述した処理を行なうことは実際には不可能であり、Ｉ／Ｏアクセス単位に関する容量を保証することができず、つまり、書込性能や読出性能が悪化する事態を招くことになる。この場合、Ｉ／Ｏアクセス時の平均ブロック長はせいぜい４１ＫＢになってしまうから、通常のＤＥ（Ｄｉｓｋ  Ｅｎｃｌｏｓｕｒｅ）では５１２ＫＢ単位の上記要求が満足された場合の１／５以下の性能しか提供できない。
【００３６】
一方、１タプルの最大長をこのブロック長が下回ることは当然許されない。現状のＲＤＢシステムでは３２〜６４ＫＢ程度のタプルは普通に許されるから、上記ケース（バッファ長４１ＫＢ）の場合、既存技術ではこの要求すら満たせなくなる可能性がある。
そこで、商用データベースの多くは、上記ブロッキングバッファ２１Ａを公知の仮想記憶空間に配置することにより、問題を回避しようとしている。しかし、これでは、ほぼ確実に１タプル毎に１回の二次記憶装置２４への読出／書込が発生することになり、ブロッキングが可能になり次段処理の性能が保証されるが、バケット分割処理の性能は著しく低下する。
【００３７】
そこで、本発明は、現実的なメモリ容量のみ消費しながら、しかも全体処理性能をほとんど低下させることなく、前述した要求（Ａ），（Ｂ）を満足する手法を提供することを可能にしている。
しかも、本発明は、１ＰＭ当たりの担当バケット数を低減するために、あるバケットを担当するＰＭを１台に制限することを要求しない。これにより、通常発生するバケット間の容量の差によるＰＭ間の負荷の偏りの発生が防止されることになる。
【００３８】
以上説明した通り、本発明は、バケット分割処理の性能の低下を招くことなく、通常範囲のメモリ量でのバケット書込／読出性能の保証のためのブロッキング作業を可能にし、バケット書込／読出性能を大幅に改善できるようにした、並列プロセッサ装置を提供することを目的とする。
【００３９】
【課題を解決するための手段】
図１は本発明の原理ブロック図で、この図１において、１は並列的に動作する複数のプロセッサで、これらの複数のプロセッサ１が一つの業務に参加し全体として該業務を実行するとともに、各プロセッサ１において、業務における処理対象のデータを、個々に独立して処理を受けることが可能なデータ単位（以下、タプルという）として取り扱うようになっている。
【００４０】
そして、本発明の並列プロセッサ装置を構成する複数のプロセッサ１には、第１プロセッサ群２，第２プロセッサ群３および中間プロセッサ群４が包含されている。
ここで、第１プロセッサ群２は、処理対象のデータを分散して予め格納するプロセッサ１のグループであり、第２プロセッサ群３は、第１プロセッサ群２から送信されてくる処理対象のデータを、同一種別のタプルのみの集合体であるバケットに分割した状態で格納するプロセッサ１のグループであり、中間プロセッサ群４は、処理対象のデータを、第１プロセッサ群２から受信して一時的に格納した後に、第２プロセッサ群３へ送信するプロセッサ１のグループである。
【００４１】
また、本発明の並列プロセッサ装置には、第１分割手段５および第２分割手段６がそなえられている。
第１分割手段５は、第１プロセッサ群２から中間プロセッサ群４へのデータ送信時に、処理対象のデータを、それぞれ複数種別のタプルの集合体である複数組のバケットグループに分割して中間プロセッサ群４に一時的に格納する第１分割処理を行なうものであり、第２分割手段６は、該第１分割手段５による前記第１分割処理後、中間プロセッサ群４から第２プロセッサ群３へのデータ送信時に、第１分割手段５により分割されて中間プロセッサ群４に一時的に格納される複数組のバケットグループを、各バケットグループ毎に読み出して同一種別のタプルのみの集合体であるバケットに分割して第２プロセッサ群３に格納する第２分割処理を行なうものである（請求項１）。
【００４２】
なお、第１分割手段５によって第１分割処理を行なうべく、処理対象のデータをなす各タプルを分類するためのグループ化関数を予め設定しておき、第１分割手段５による第１分割処理として、各タプルに対してグループ化関数を適用して得られた、グループ化関数の出力値としてのバケット識別子に基づいて、バケットグループ分割処理を行なうように構成してもよい（請求項２）。同様に、第２分割手段６によって第２分割処理を行なうべく、処理対象のデータをなす各タプルを分類するためのグループ化関数を予め設定しておき、第２分割手段６による第２分割処理として、各タプルに対してグループ化関数を適用して得られた、グループ化関数の出力値としてのバケット識別子に基づいて、バケット分割処理を行なうように構成してもよい（請求項３）。
【００４３】
また、第１プロセッサ群２，第２プロセッサ群３および中間プロセッサ群４の動作状態を管理しこれらの第１プロセッサ群２，第２プロセッサ群３および中間プロセッサ群４の動作を同期させながら第１分割手段５による第１分割処理および第２分割手段６による第２分割処理を実行させるための制御用プロセッサを、複数のプロセッサ１に包含させておいてもよい（請求項４）。
【００４４】
さらに、同一バケットグループに属するタプルを、中間プロセッサ群４に属する各プロセッサ１に対して均一またはほぼ均一に送付して、中間プロセッサ群４に属する各プロセッサ１における負荷を平坦化するための第１負荷平坦化手段をそなえ、第１分割処理に際して第１負荷平坦化手段により中間プロセッサ群４に属する各プロセッサ１における負荷を平坦化してもよい（請求項５）。同様に、同一バケットグループに属するタプルを、第２プロセッサ群３に属する各プロセッサ１に対して均一またはほぼ均一に送付して、第２プロセッサ群３に属する各プロセッサ１における負荷を平坦化するための第２負荷平坦化手段をそなえ、第２分割処理に際して第２負荷平坦化手段により第２プロセッサ群３に属する各プロセッサ１における負荷を平坦化してもよい（請求項６）。
【００４５】
【作用】
図１により上述した本発明の並列プロセッサ装置では、第１プロセッサ群２から第２プロセッサ群３へのタプルデータの転送に際して、これらの第１プロセッサ群２と第２プロセッサ群３との間に中間プロセッサ群４が介在されている。
そして、第１プロセッサ群２から中間プロセッサ群４へのデータ送信時には、第１分割手段５の第１分割処理により、処理対象のデータが、それぞれ複数種別のタプルの集合体である複数組のバケットグループに分割されてから、中間プロセッサ群４に一時的に格納される。
【００４６】
この後、中間プロセッサ群４から第２プロセッサ群３へのデータ送信時には、第２分割手段６の第２分割処理により、中間プロセッサ群４に一時的に格納されている複数組のバケットグループが、各バケットグループ毎に読み出され、同一種別のタプルのみの集合体であるバケットに分割されてから、最終的に第２プロセッサ群３に格納される。
【００４７】
このように中間プロセッサ群４を介在させて、少なくとも２段階のデータ分割処理を行なうことにより、各プロセッサ１に、タプルの総種別数分（バケット総種別数分）のバッファをそなえることなく、第２プロセッサ群３に属する各プロセッサ１に、データをバケットに分割した状態で格納させることができる。
従って、バケット分割処理の性能の低下を招くことなく、通常範囲のメモリ量でのバケット書込／読出性能の保証のためのブロッキング作業を行なうことが可能になる（請求項１）。
【００４８】
なお、第１分割手段５によるバケットグループ分割処理（第１分割処理）は、各タプルに対してグループ化関数を適用して得られたバケット識別子に基づいて行なうことができるとともに（請求項２）、第２分割手段６によるバケット分割処理（第２分割処理）も、各タプルに対してグループ化関数を適用して得られたバケット識別子に基づいて行なうことができる（請求項３）。
【００４９】
また、制御用プロセッサを用いて、第１プロセッサ群２，第２プロセッサ群３および中間プロセッサ群４の動作を同期させながら第１分割手段５による第１分割処理および第２分割手段６による第２分割処理を実行させることにより、タプル種別を意識しながら各プロセッサ１に分散配置されたデータを分割することができる（請求項４）。
さらに、第１負荷平坦化手段により、中間プロセッサ群４に属する各プロセッサ１における負荷が平坦化されるとともに（請求項５）。第２負荷平坦化手段により、第２プロセッサ群３に属する各プロセッサ１における負荷も平坦化される（請求項６）。つまり、本発明の並列プロセッサ装置では、ある種別のバケットを担当するプロセッサを１台に制限せず、各プロセッサ１における負荷の平坦化を行なうことにより、通常発生するバケット間の容量の差によるプロセッサ間の負荷の偏りの発生が防止される。
【００５０】
【実施例】
以下、図面を参照して本発明の実施例を説明する。
まず、図２を参照しながら、本発明の一実施例としての並列プロセッサ装置の原理的な構成および動作について説明する。
図２に示す通り、本実施例の並列プロセッサ装置には、送信側のＰＭ群（第１プロセッサ群）６０と受信側のＰＭ群（第２プロセッサ群）７０との間に、中間プロセッサ群としての中間ブロッキングＰＭ群１５０が介在している。
【００５１】
そして、第１ステップ（図１にて前述した第１分割手段５としての機能による処理動作；第１分割処理，バケットグループ分割処理）として、送信側のＰＭ群６０と中間ブロッキングＰＭ群１５０との間で全点対全点通信を行ない、ここでバケット群を大きくｍ種類のバケットグループ９２０−１〜９２０−ｍに分割し、各バケットグループを、中間ブロッキングＰＭ群１５０に属する各ＰＭ１５００〜１５０２に接続された二次記憶装置２４に格納する。ここで、ｍ種類のバケットグループ９２０−１〜９２０−ｍには、それぞれｎ種類のタプル（ｎ種類のバケット）が含まれている。
【００５２】
このような第１ステップに際しての送信側ＰＭ群６０の処理について説明すると、まず、このＰＭ群６０に属する各ＰＭ６００〜６０２は、自身配下の処理対象テーブルのサブテーブル（二次記憶装置２４内に格納）９００〜９０２からタプルを読み出し、そのタプルを、任意の配分論理により中間ブロッキングＰＭ群１５０に送付する。ここでは、ＰＭ間の負荷平坦化を陽に実現しないものとして説明を進めるので、ハッシュ関数等のグループ化関数の適用を、送信側ＰＭ群６０と中間ブロッキングＰＭ群１５０とのいずれで行なうかについては特に指定しない。
【００５３】
また、第１ステップに際しての中間ブロッキングＰＭ群１５０の処理について説明すると、中間ブロッキングＰＭ群１５０に属する各ＰＭ１５００〜１５０２は、バケット識別子とｍ種類のバケットグループとの対応関係を把握しておく。バケット識別子は、予め外部から指定されるか、あるいは、ルールとしてバケット総種別数から予め与えられた計算方式により求められるものである。あるバケットは必ずたかだか一つのバケットグループに属する。
【００５４】
各ＰＭ１５００〜１５０２は、送信側の各ＰＭ６００〜６０２からタプルを受理し、もし、送信側の各ＰＭ６００〜６０２でタプルに対するグループ化関数の適用が行なわれていないか、あるいは、送付されたタプルにグループ化関数の適用結果（出力値）によるバケット識別子が添付されていなければ、そのタプルに対してグループ化関数を適用して、そのタプルが属するバケットのバケット識別子を求める。
【００５５】
そして、各ＰＭ１５００〜１５０２は、そのタプルのバケット識別子に上記対応関係を適用し、そのタプルが属するべきバケットグループを把握する。
このとき、本実施例の各ＰＭ１５００〜１５０２では、バケットグループの各種類に対応して、Ｉ／Ｏブロッキングバッファ１５１がメモリ（主記憶；図９の符号２１参照）上に準備されている。これらのＩ／Ｏブロッキングバッファ１５１は、送信側ＰＭ群６０からのタプル受理と自身の二次記憶装置２４への書込とが同時並列的に実行可能な個数だけ準備され、その個々の大きさは、上記Ｉ／Ｏアクセス単位の容量保証に関する要求を満足するように設定されている。
【００５６】
各ＰＭ１５００〜１５０２に入力されたタプルが属するバケットグループがいずれであるかの上記認識に基づいて、そのタプルを、認識されたバケットグループに対応したＩ／Ｏブロッキングバッファ１５１に蓄積する。
このようなタプルの蓄積作業により、あるＩ／Ｏブロッキングバッファ１５１に蓄積されたタプル量が上記Ｉ／Ｏアクセス単位に関する容量保証の要求を満足するようになった場合、そのＩ／Ｏブロッキングバッファ１５１に蓄積されたタプルを、まとめて自身の二次記憶装置２４内に格納する。これにより、処理対象データが、ｍ種類のバケットグループ９１０−１〜９１０−ｍに分割された状態で、中間ブロッキングＰＭ群１５０の各二次記憶装置２４内に格納されることになる。
【００５７】
ついで、第２ステップ（図１にて前述した第２分割手段６としての機能による処理動作；第２分割処理，バケット分割処理）として、中間ブロッキングＰＭ群１５０から各バケットグループが読み出され、各バケットグループが、受信側ＰＭ群７０に送付され、受信側ＰＭ群７０において個別のバケット（総数ｍ・ｎ個）９２０−１〜９２０−ｍ・ｎに再分割された状態で二次記憶装置２４に格納される。
【００５８】
このような第２ステップに際しての中間ブロッキングＰＭ群１５０の処理について説明すると、まず、このＰＭ群１５０および受信側ＰＭ群７０は、任意のマクロな同期機構（図２には図示せず）により第２ステップの開始を一斉に認識する。ここで、マクロという意味は、クロックレベルの詳細な同期は必要なく、メッセージパッシング程度の実現手段で構わない、つまり時間の微小なずれは許容されるということである。また、前記同期機構は、中間ブロッキングＰＭ群１５０と受信側ＰＭ群７０との全てが相互に通信して同期を実現するものであってもよいし、全ＰＭのマクロな制御を行なう存在として別個にそなえてもよい。
【００５９】
受信側ＰＭ群７０および中間ブロッキングＰＭ群１５０は、上記同期機構あるいはこれとは別に設けられた同様の機構により指示されるか、あるいは、ルールとして予め与えられた法則により、いずれのバケットグループが処理の対象となるべきかを認識する。この認識は、受信側ＰＭ群７０および中間ブロッキングＰＭ群１５０に属する全ＰＭで、同様にマクロ的な意味でほぼ同時に（実際のデータ転送に先立って）持たなければならない。
【００６０】
中間ブロッキングＰＭ群１５０に属する各ＰＭ１５００〜１５０２は、処理対象となったバケットグループからタプル群を、自身の二次記憶装置２４から読み出し、そのタプルを、任意の配分論理により受信側ＰＭ群７０に送付する。ここでも、ＰＭ間の負荷平坦化を陽に実現しないものとして説明を進めるので、バケット識別子に依存した制御を、中間ブロッキングＰＭ群１５０と受信側ＰＭ群７０とのいずれで行なうかについては特に指定しない。
【００６１】
あるバケットグループの送付を完了した場合、中間ブロッキングＰＭ群１５０および受信側ＰＭ群７０に属する全ＰＭがそのバケットグループの送受信を終了したことが、上記同期機構のいずれか、あるいは別に設けられた同様の機構により認識された時点で、中間ブロッキングＰＭ群１５０および受信側ＰＭ群７０は次のバケットグループの処理を開始する。
【００６２】
また、第２ステップに際しての受信側ＰＭ群７０の処理について説明すると、受信側ＰＭ群７０に属する各ＰＭ７００〜７０２は、中間ブロッキングＰＭ群１５０とともに、第２ステップの処理全体および各バケットグループの処理の開始／終了をマクロ的な意味でほぼ同時に認識する。
バケットグループの受理開始に先立ち、本実施例の受信側ＰＭ群７０に属する各ＰＭ７００〜７０２では、各バケットグループに含まれるバケットの種類に対応して、Ｉ／Ｏブロッキングバッファ７１がメモリ（主記憶；図９の符号２１参照）上に準備されている。これらのＩ／Ｏブロッキングバッファ７１は、次に処理されるバケットグループに含まれるバケット数に対応した「中間ブロッキングＰＭ群１５０からのタプル受理と二次記憶装置２４への書込との同時並列実行」が可能な個数だけ準備され、その個々の大きさは上記Ｉ／Ｏアクセス単位に関する容量の保証に関する要求を満たすように設定されている。
【００６３】
各ＰＭ７００〜７０２は、処理対象であるバケットグループに含まれるタプルを中間ブロッキングＰＭ群１５０から受理すると、もし送付されたタプルにバケット識別子が添付されていないならば、そのタプルに対してグループ化関数を適用して、そのタプルが属するバケットのバケット識別子を求める。
そして、各ＰＭ７００〜７０２は、そのタプルを、求められたバケット識別子に基づいて、そのタプルが属するバケットに対応したＩ／Ｏブロッキングバッファ７１に蓄積する。
【００６４】
このようなタプルの蓄積作業により、あるＩ／Ｏブロッキングバッファ７１に蓄積されたタプル量が上記Ｉ／Ｏアクセス単位に関する容量保証の要求を満足するようになった場合、そのＩ／Ｏブロッキングバッファ７１に蓄積されたタプルを、まとめて自身の二次記憶装置２４内に格納する。これにより、各バケットグループ９１０−１〜９１０−ｍに含まれるｎ種類のタプル（ｎ種類のバケット）が、それぞれ、その種類毎に分割された状態で、受信側ＰＭ群７０の各二次記憶装置２４内に格納されることになる。
【００６５】
ところで、本実施例では、図２により上述したシステムにおいて、さらにＰＭ間の負荷平坦化（前述した第１負荷平坦化手段および第２負荷平坦化手段による機能）を行なうことにより、特定ＰＭへの負荷集中による全体のスループットの低下を防止している。
即ち、前述した第１ステップにおいて、送信側ＰＭ群６０に属する各ＰＭ６００〜６０２は、自身の二次記憶装置２４から読み出したタプルにグループ化関数を適用し、ｍ種類のバケットグループのいずれにそのタプルが属するかを認識する。
【００６６】
また、送信側ＰＭ群６０に属する各ＰＭ６００〜６０２は、前述した第１ステップにおいて、ｍ種類のバケットグループのそれぞれについて、そこに属するタプルが、中間ブロッキングＰＭ群１５０に属するＰＭ１５００〜１５０２のいずれにもほぼ同量だけ（均一もしくは略均一に）転送されるように制御する機構（第１負荷平坦化手段；図２には図示せず）をそなえる。この機構は、例えば、ラウンドロビンポインタや、各バケットおよび中間ブロッキングＰＭ識別子によるアドレスが可能で各中間ブロッキングＰＭ１５００〜１５０２へのデータ送付量を積算するテーブルなどにより実現することができる。このような機構を使用して、どの中間ブロッキングＰＭ１５００〜１５０２にも、送信側ＰＭ６００〜６０２から、同一バケットグループに属するタプルデータがほぼ同量送付されることになる。
【００６７】
さらに、中間ブロッキングＰＭ群１５０に属する各ＰＭ１５００〜１５０２は、前述した第２ステップにおいて、自身の二次記憶装置２４から読み出したタプルのバケット識別子を使用して、各バケットグループに含まれるｎ種類のバケットのそれぞれについて、そこに属するタプルが、受信側ＰＭ群７０に属するＰＭ７００〜７０２のいずれにもほぼ同量だけ（均一もしくは略均一に）転送されるように制御する機構（第２負荷平坦化手段；図２には図示せず）をそなえる。この機構は、例えば、ラウンドロビンポインタや、各バケットおよび受信側ＰＭ識別子によるアドレスが可能で各受信側ＰＭ７００〜７０２へのデータ送付量を積算するテーブルなどにより実現することができる。このような機構を使用して、どの受信側ＰＭ７００〜７０２にも、中間ブロッキングＰＭ１５００〜１５０２から、同一バケットに属するタプルデータがほぼ同量送付されることになる。なお、各ＰＭ１５００〜１５０２において、自身の二次記憶装置２４から読み出したタプルにバケット識別子が添付されていない場合には、改めてグループ化関数を適用してバケット識別子を得る。
【００６８】
次に、図２を参照しながら、本発明の並列プロセッサ装置の概要について説明する。
前述の通り、通常の場合、あるデータベーステーブルにグループ化関数を適用して得られるバケット個数は、個々のバケットが主記憶に乗り切る程度の大きさであることが期待される場合などでは極めて大きくなり、Ｉ／Ｏアクセス単位に関する容量の保証の要件を全てのバケット種別に対して同時に満足することが極めて難しい状況となる。
【００６９】
本発明は、バケット種別数だけのＩ／Ｏブロッキングバッファを準備することは難しくても、これらバケット種別数の例えば平方根の数だけのＩ／Ｏブロッキングバッファを準備することはそれ程困難ではないことに着目し、スループットこそ理想的速度の１／２ではあるが、上記Ｉ／Ｏアクセス単位に関する容量の保証の要件が満足されない場合（読出／書込がそれぞれ１／５以下に低下するため全体としての性能低下は極めて大きい）に比較すれば充分高速であることから、少なくとも２回に分けてグルーピング（分割処理）を行なうことをその骨子としている。
【００７０】
まず、前述した第１ステップでは、バケット識別子の値域をｍ個に排他的に分割し、タプルをバケット識別子によりｍ種類に分割する。この分割により作成されたｍ個のタプル集合体を、それぞれバケットグループと呼ぶ。各バケットグループの内部では、複数（ここではｎ種類）のバケットが、タプルレベルでの発生順序は全くランダムに、格納されている。
【００７１】
そして、前述した第２ステップでは、各バケットグループを格納している全てのＰＭ１５００〜１５０２でマクロ的な同期をとりながら、同じバケットグループ、つまり元々のテーブルの平均１／ｍ個分のバケットしか含まない領域に対して読出を行ない、同様にバケット分割を行なう。
もし元々のテーブルがｎ・ｍ個のバケットを含んでいたならば、この第２ステップでは平均ｎ個のバケットのみ現れることになる。このｎなるバケット数を完全に分割可能なだけのＩ／Ｏブロッキングバッファ７１が第２ステップで取得可能ならば、完全なバケット分割が可能になる。
【００７２】
一般に、データベース容量と主記憶容量との比１０３  〜１０４  程度で収まるので、ｍ≒ｎを仮定すると、ｍ≒ｎ≦１０２  ということになり、数百ＫＢがＩ／Ｏアクセス単位についての容量保証の具体的な要求値であったとしても数ＭＢ〜数十ＭＢ程度、つまり主記憶容量の範囲で、充分、Ｉ／Ｏブロッキングバッファ７１，１５１を準備することができる。
【００７３】
さらに、本発明の発展形として、中間ブロッキングＰＭ群１５０を複数段に構成し、バケット数を複数乗根し、極めて大きなバケット数にも対応することができるようにすることも可能である。ただし、１段増す度にそれだけ性能低下が発生するので、構成段数は、次段処理を含めた性能利得を評価した上で判断されるべきである。
【００７４】
なお、ここでは、中間ブロッキングＰＭ群１５０が送信側ＰＭ群６０や受信側ＰＭ群７０とは別に存在するかのうように記述しているが、物理的に中間ブロッキングＰＭ群１５０が送信側ＰＭ群６０や受信側ＰＭ群７０と一致していたり、重なっていたり、包含関係にあったり、あるいは全てのＰＭ群６０，７０，１５０が物理的に同じ集合であったとしても全く構わない。
【００７５】
また、前述した負荷平坦化処理を行なわないと、受信側ＰＭ群７０や中間ブロッキングＰＭ群１５０に属する各ＰＭの二次記憶書込処理性能を含めて特定のＰＭにデータを送付しようとする速度がそのＰＭの処理性能を上回り、システムの演算性能を低下させてしまう可能性がある。従って、負荷平坦化処理は、これを防ぐために各段でのＰＭ間負荷アンバランスが発生するのを防止している。
【００７６】
以下に、図３〜図８を参照しながら、本発明の一実施例としての並列プロセッサ装置（並列計算機システム）について、より詳細に説明する。
図３は本発明の一実施例としての並列プロセッサ装置の全体構成を概略的に示すブロック図で、この図３に示すように、制御用ＰＭ１６００が新たに追加されている以外は、図２に示したものとほぼ同様の構成になっている。
【００７７】
図３に示すシステムに新たに追加されている制御用ＰＭ１６００は、前述したマクロなＰＭ間同期，および各ＰＭで行なわれる処理の大筋の制御を行なうものとして別個に存在している。この制御用ＰＭ１６００は、通信線１６０１および１６０２を介して各ＰＭ６００〜６０２，７００〜７０２，１５００〜１５０２との間でコマンド送付／状況報告等のデータを授受することにより、システムの全体を管理し全体処理を制御するものである。
【００７８】
本実施例では、中間ブロッキングＰＭ群１５０に属する各ＰＭ１５００〜１５０２には、それぞれ、ｍ＋１個のＩ／Ｏブロッキングバッファ１５１が準備されている。これらのｍ＋１個のバッファ１５１のうちｍ個は、前段つまり送信側ＰＭ６００〜６０２から送付されるタプルデータをバケットグループ毎に蓄積するためのものであり、残りの１個は、二次記憶装置２４との間でデータ授受を行なうためのものである。
【００７９】
また、同様に、受信側ＰＭ群７０に属する各ＰＭ７００〜７０２には、それぞれ、ｎ＋１個のＩ／Ｏブロッキングバッファ７１が準備されている。これらのｍ＋１個のバッファ７１のうちｍ個は、前段つまり中間ブロッキングＰＭ１５００〜１５０２から送付されるタプルデータをバケット毎に蓄積するためのものであり、残りの１個は、二次記憶装置２４との間でデータ授受を行なうためのものである。
【００８０】
なお、上述したＩ／Ｏブロッキングバッファ１５１および７１は、いずれも、Ｉ／Ｏアクセス単位に関する容量保証の要求を満たすだけの大きさのものである。
上述の構成により、この図３に示すシステムは、制御用ＰＭ１６００により管理・制御されながら、図２に示したシステムと全く同様の動作を行なうようになっている。
【００８１】
ここで、図４により、本実施例におけるＰＭ間ネットワークを流れるパケットの概略構成を説明する。ＰＭ間ネットワークを介して１タプル毎の送信を行なう場合、図４に示すように、パケットのデータ部にタプルデータ（Ｔｕｐｌｅ  Ｄａｔａ）が格納されるとともに、パケットのヘッダ部には、宛先ＰＭのネットワーク内の識別子（Ｔａｒｇｅｔ  ＰＭ  ＩＤ）と、このタプルが属するバケット識別子（Ｂｕｃｋｅｔ  ＩＤ；グループ化関数の出力値）と、タプル長（Ｔｕｐｌｅ  Ｌｅｎｇｔｈ）とが添付・格納されている。
【００８２】
さて、図５は、前述した第１ステップにおける送信側ＰＭ６００の内部構造および動作を説明するためのブロック図であり、この図５において、１７００はＰＭ６００に接続された二次記憶装置（前述した二次記憶装置２４に対応）で、この二次記憶装置１７００は、処理対象のテーブルの部分集合（サブテーブル）９００を格納している。
【００８３】
また、送信側ＰＭ６００には、Ｉ／Ｏ回路１７０１，ＣＰＵ回路１７０２，主記憶１７０３および対ＰＭ間ネットワークインタフェース回路１７０４が内蔵されている。ここで、Ｉ／Ｏ回路１７０１は図９にて前述したＩ／Ｏ機構２３に対応し、ＣＰＵ回路１７０２は図９にて前述したＣＰＵ２０に対応し、主記憶１７０３は図９にて前述したメモリ２１に対応し、インタフェース回路１７０４は図９にて前述したアクセス機構２２に対応している。
【００８４】
さらに、１７１０〜１７１３および１７１５〜１７１７は主記憶１７０３上の領域であり、１７１０はサブテーブル９００の内部の読出位置を示す読出ポインタで、この読出ポインタ１７１０は、主記憶１７０３上の変数として実現されている。読出ポインタ１７１０は、初期化直後にはサブテーブル９００の先頭位置を示し、サブテーブル９００から１回の入力処理を行なう度に、後述のバッファ１７１１の容量だけインクリメントされる。
【００８５】
１７１１は１回のＩ／Ｏ処理で読み出されるデータを格納する入力バッファであり、その大きさ（容量）は、Ｉ／Ｏアクセス単位に関する容量保証の要求を満足するように設定されている。
１７１２は各バケットグループに対応して設けられた中間ブロッキングＰＭ１５００〜１５０２のいずれにデータを転送すべきかを示すラウンドロビンポインタ（第１負荷平坦化手段）である。今、中間ブロッキングＰＭ１５００〜１５０２の個数をＡ個とするならば、このラウンドロビンポインタ１７１２の値は０からＡ−１の間をラップする。
【００８６】
１７１３はラウンドロビンポインタ１７１２の値から具体的な中間ブロッキングＰＭ１５００〜１５０２のネットワーク上の識別子を求めるための変換表である。この変換表１７１３のエントリ数は、中間ブロッキングＰＭ１５００〜１５０２の個数に等しく、その内部には個々の中間ブロッキングＰＭ１５００〜１５０２のネットワーク上の識別子が格納されている。
【００８７】
１７１５は入力バッファ１７１１内のデータから抽出された１タプル分のデータ、１７１６は１タプル分のデータ１７１５にグループ化関数を適用した結果として得られるバケット識別子を当該１タプル分のデータ１７１５に接合したデータ、１７１７はデータ１７１６にさらに宛先ＰＭのネットワーク上の識別子を接合したデータ（転送パケット）で、このデータ１７１７は、図４に示すバケットフォーマットを満足するものとなっている。
【００８８】
また、１７１８は二次記憶装置１７００から今まさに送信側ＰＭ６００に読み込まれているデータ部を示している。
なお、図５中の括弧付数字（０）〜（１２）は、送信側ＰＭ６００における処理に対応して付されたもので、送信側ＰＭ６００の動作を後述する際に用いられるものである。また、図５には、送信側ＰＭ６００の構成のみ示しているが、他の送信側ＰＭ６０１，６０２も同様に構成されていることはいうまでもない。
【００８９】
上述のごとく構成された送信側ＰＭ６００の、前記第１ステップに際しての動作概要を以下に説明する。この説明に際して、図５中の括弧付数字（０）〜（１２）と以下の項目の括弧付数字（０）〜（１２）とは対応している。
（０）図５には図示しない制御用ＰＭ１６００（図３参照）から、行なうべき処理の記述、例えば対象テーブルの識別子，適用されるべきグループ化関数の識別子，ｍおよびＡの値，中間ブロッキングＰＭ群１５０の識別子リストなどがＣＰＵ１７０２に送付され、これらのデータにより主記憶１７０３の内部制御テーブル群が初期化される。初期化を終了すると、ＣＰＵ１７０２は、その旨を応答として制御用ＰＭ１６００に返し、次に制御用ＰＭ１６００から処理開始の指示が来ると処理を開始する。
【００９０】
（１）ＣＰＵ１７０２は、ポインタ１７１０の内容を読み出して、バッファ１７１１の大きさに等しいデータブロックを、該ポインタ１７１０が示す領域から読み出す入力コマンドを生成し、そのコマンドをＩ／Ｏ回路１７０１に与える。この後、ポインタ１７１０の値をバッファ１７１１の大きさだけインクリメントしておく。
【００９１】
（２）Ｉ／Ｏ回路１７０１は、ＣＰＵ１７０２から指定されたデータ１７１８を、二次記憶装置１７００からバッファ１７１１内部に読み出す。
（３）Ｉ／Ｏ回路１７０１は、要求された入力処理を終了したことを、割込みによりＣＰＵ１７０２に通知する。
（４）ＣＰＵ１７０２は、バッファ１７１１内部から１タプル分のデータ１７１５を抽出し、このデータ１７１５に対して以下の処理（５）〜（１１）を施す。
【００９２】
（５）タプルデータ１７１５が、ＣＰＵ１７０２に取り込まれ、指定されたグループ化関数の適用を受ける。
（６）その適用結果であるバケット識別子がタプルデータ１７１５（図５中の左側）に接合される。
（７）そのバケット識別子は、整数ｍ（バケットグループの種類数）で割った余りによって同時にバケットグループの識別子ともなる。ＣＰＵ１７０２は、このタプルデータ１７１５が属するバケットグループの識別子を得て、その識別子により、送信宛先を決定するためのラウンドロビンポインタ１７１２（このバケットグループに対応する値）を特定する。
【００９３】
（８）ラウンドロビンポインタ１７１２により指定されるポインタ値により、そのポインタ値をＰＭ識別子に変換する変換表１７１３が索引され、宛先情報、つまりこのタプルデータ１７１５を受信すべき中間ブロッキングＰＭの識別子が得られる。また、この時、ポインタ（１７１２中の１エントリ）の内容は１だけインクリメントされた後、中間ブロッキングＰＭ数による整数剰余の値が代入され直す。
【００９４】
（９）得られた宛先情報が、〔タプルデータ＋バケット識別子〕のデータ１７１６（図５中の左側）に接続され、転送パケット１７１７が主記憶１７０３上に生成される。
（１０）ＣＰＵ１７０２は、インタフェース回路１７０４に対し、転送パケット１７１７の格納領域の主記憶内先頭アドレスを示して送出を指示する。
【００９５】
（１１）転送パケット（タプルデータ）１７１７は、インタフェース回路１７０４により、即時に（ＣＰＵ１７０２に同期して）ネットワークに送出される。本実施例では、ネットワーク上のプロトコルは簡単化され、ＣＰＵ１７０２から可視のＡＣＫ（Ａｃｋｎｏｗｌｅｄｇｅ）信号などの応答はないものとする。
（１２）以上のような処理が二次記憶装置１７００内のサブテーブル９００中の全てのデータに対して行なわれるまで、上記項目（１）の処理に戻る。もし、ＣＰＵ１７０２が、全てのデータの処理を終了したと判断した場合には、内部資源を解放した上、処理の終了を制御用ＰＭ１６００に報告する。
【００９６】
図６は、前述した第１ステップにおける中間ブロッキングＰＭ１５００の内部構造および動作を説明するためのブロック図であり、この図６において、１７５０はＰＭ１５００に接続された二次記憶装置（前述した二次記憶装置２４に対応）で、この二次記憶装置１７５０は、後述するごとく、その内部に、送信側ＰＭ６００（〜６０２）から受理したｍ種類のバケットグループ９１０−１〜９１０−ｍ（図３参照）の部分集合１７５５を格納する領域を有している。
【００９７】
また、中間ブロッキングＰＭ１５００には、対ＰＭ間ネットワークインタフェース回路１７５１，ＣＰＵ回路１７５２，主記憶１７５３およびＩ／Ｏ回路１７５４が内蔵されている。ここで、インタフェース回路１７５１は図９にて前述したアクセス機構２２に対応し、ＣＰＵ回路１７５２は図９にて前述したＣＰＵ２０に対応し、主記憶１７５３は図９にて前述したメモリ２１に対応し、Ｉ／Ｏ回路１７５４は図９にて前述したＩ／Ｏ機構２３に対応している。
【００９８】
さらに、１７６０〜１７６５は主記憶１７５３上の領域であり、１７６０はＰＭ間データ転送により送信側ＰＭ６００〜６０２のいずれかから送付されたタプルデータを一時的に格納する領域、１７６１はｍ種類のＩ／Ｏブロッキングバッファ（０〜ｍ−１；図２，図３に示すＩ／Ｏブロッキングバッファ１５１に対応）で、各Ｉ／Ｏブロッキングバッファ１７６１は、前述したように、二次記憶装置１７５０が要求するＩ／Ｏアクセス単位の容量の保証の要求を満足する大きさを有し、バケットグループ種別と１対１に対応している。
【００９９】
１７６２はＩ／Ｏ回路１７５４へ出力すべきデータもしくはＩ／Ｏ回路１７５４から入力されたデータを一時的に格納する入出力バッファ（Ｉ／Ｏバッファ）、１７６３は領域１７６５内への書込ポインタで、この書込ポインタ１７６３は、領域１７６５に対する入出力処理を１回終了する度にバッファ１７６２の大きさだけインクリメントされるようになっている。
【０１００】
１７６４は各バケットグループが書き込まれたファイル内位置（アドレス）を記憶する領域１７６５への書込ポインタで、書込ポインタ１７６４と領域１７６５とは、１対１の対になって、それぞれのバケットグループ種別に対応して設けられている。
なお、図６中の括弧付数字（０）〜（１０）は、中間ブロッキングＰＭ１５００における処理に対応して付されたもので、中間ブロッキングＰＭ１５００の動作を後述する際に用いられるものである。また、図６には、中間ブロッキングＰＭ１５００の構成のみ示しているが、他の中間ブロッキングＰＭ１５０１，１５０２も同様に構成されていることはいうまでもない。
【０１０１】
上述のごとく構成された中間ブロッキングＰＭ１５００の、前記第１ステップに際しての動作概要を以下に説明する。この説明に際して、図６中の括弧付数字（０）〜（１０）と以下の項目の括弧付数字（０）〜（１０）とは対応している。
（０）図６には図示しない制御用ＰＭ１６００（図３参照）から、行なうべき処理の記述、例えば対象テーブルの識別子，バケット識別子の値域幅，ｍの値，転送されるデータ量の予想値，交信しなければならない送信側ＰＭ群７０の一覧などが送付される。これにより、ＣＰＵ１７５２は、主記憶１７５３内の制御表を初期化し、初期化を終了すると、その旨を制御用ＰＭ１６００に対して応答し、その後、制御用ＰＭ１６００から処理開始の指示が来ると処理を開始する。なお、初期化の例としては、領域１７６５の全エントリを無効な値（例えば負の値）に設定するとともに、書込ポインタ１７６４の全ての値を０に設定する。
【０１０２】
（１）ネットワークインタフェース回路１７５１は、タプルを受信すると、これを割込みによりＣＰＵ１７５２に伝達する。ＣＰＵ１７５２は、領域１７６０の先頭アドレスを通知することにより、タプルを領域１７６０に取り込むことを指示する。
（２）タプル内のバケット識別子フィールドがＣＰＵ１７５２により参照され、整数ｍによる整数剰余演算の結果（余り値）がこのタプルのバケットグループ識別子として認識される。
【０１０３】
（３）このバケットグループ識別子により、当該タプル（正確にはバケット識別子＋タプル長＋タプルデータ部分）が、バケットグループ種別に対応するＩ／Ｏブロッキングバッファ１７６１に蓄積される。もし、この蓄積処理により、Ｉ／Ｏブロッキングバッファ１７６１内に蓄積されたデータ量が二次記憶装置１７５０の要求するＩ／Ｏアクセス単位の容量の保証に関する要求を満たさないならば、後述する項目（１０）の処理へジャンプする。
【０１０４】
（４）Ｉ／Ｏブロッキングバッファ１７６１へのデータ蓄積量が、二次記憶装置１７５０の要求するＩ／Ｏアクセス単位の容量の保証に関する要求を満たすようになったならば、このバッファ１７６１の内容は、Ｉ／Ｏバッファ１７６２に転送された後、クリアされる。
（５）ＣＰＵ１７５２は、書込ポインタ１７６３の値の内容を取り込み、書込位置を得る。また、その後、ポインタ１７６３の内容は、Ｉ／Ｏバッファ１７６２の大きさけインクリメントされる。
【０１０５】
（６）ＣＰＵ１７５２により、吐き出しが行なわれる対象であるバケットグループに対応した、書込ポインタ１７６４と領域１７６５との対が選択される。
（７）上記項目（６）の処理で選択された書込ポインタ１７６４と領域１７６５との対において、書込ポインタ１７６４で示される領域１７６５のエントリが選択される。この後、その書込ポインタ１７６４の内容は１エントリ分だけインクリメントされる。
【０１０６】
（８）上記項目（７）の処理で選択された領域１７６５のエントリに上記項目（５）で得られた書込位置が記入される。
（９）ＣＰＵ１７５２は、Ｉ／Ｏバッファ１７６２の内容を上記項目（５）の処理で得られた書込位置（二次記憶装置１７５０上の位置）へ格納するための入出力コマンドを生成し、そのコマンドをＩ／Ｏ回路１７５４に送付する。
【０１０７】
（１０）そして、ＣＰＵ１７５２は、制御用ＰＭ１６００からの終了信号、あるいは新たなタプルの到着を示すネットワークインタフェース回路１７５１からの割込み信号が到着するまで待機する。もし、制御用ＰＭ１６００からの終了信号が到来した場合には、バッファ１７６１のうち空きでない全てのものについて、上記項目（４）以降の処理を行ない、その上で内部制御情報を書込ポインタ１７６４および領域１７６５を除いて解放し、処理終了報告を制御用ＰＭ１６００に返す。
【０１０８】
図７は、前述した第２ステップにおける中間ブロッキングＰＭ１５００の内部構造および動作を説明するためのブロック図であり、この図７において、図６で既述の符号と同一の符号は、基本的には同一部分を示しているので、その詳細な説明は省略する。
なお、図７に示す状態では、ＰＭ１５００に接続された二次記憶装置１７５０の内部には、後述するごとく、前述した第１ステップにより受理されたデータ〔ｍ種類のバケットグループ９１０−１〜９１０−ｍ（図３参照）の和集合〕１７５５を格納する領域がそなえられている。
【０１０９】
また、主記憶１７５３上の領域１７６５には、前述した第１ステップで生成された、各バケットグループの二次記憶装置１７５０内における格納アドレス（書込位置）を記述する情報が格納されている。さらに、第２ステップの処理を行なうに際して、各書込ポインタ１７６４は、各領域１７６５の情報内の、各Ｉ／Ｏアクセス単位に関する記述を逐次的にアクセスするためのカウンタとして機能し、各ポインタ１７６４の内容から、対応する領域１７６５内の各エントリのアドレスを容易に生成できるようになっている。
【０１１０】
そして、１７７０は二次記憶装置１７５０内のデータ１７５５のデータブロックで、このデータブロック１７７０は、あるバケットグループに属するデータのみが格納されているものであり、図７に示す状態で現在まさに処理対象となっているものである。
１７７１〜１７７５は主記憶１７５３上の領域であり、１７７１は二次記憶装置１７５０から読み出されたデータを一時的に格納するＩ／Ｏバッファ（入出力バッファ）、１７７２はＩ／Ｏバッファ１７７１から抽出されたタプルデータ（厳密にはタプルデータに当該タプルが属するバケットのバケット識別子を接合されたデータ）を一時的に格納する領域である。
【０１１１】
１７７３は各バケットグループに対応して設けられた受信側ＰＭ７００〜７０２のいずれに転送すべきかを示すラウンドロビンポインタ（第２負荷平坦化手段）である。今、受信側ＰＭ７００〜７０２の個数をＢ個とするならば、このラウンドロビンポインタ１７７３の値０からＢ−１の間をラップする。
１７７４はラウンドロビンポインタ１７７３の値から具体的な受信側ＰＭ７００〜７０２のネットワーク上の識別子を求めるための変換表である。この変換表のエントリ数は、受信側ＰＭ７００〜７０２の個数に等しく、その内部には個々の受信側ＰＭ７００〜７０２のネットワーク上の識別子が格納されている。
【０１１２】
１７７５はネットワークに送出されるべきパケットデータを一時的に格納する領域である。この領域１７７５から、インタフェース回路１７５１は、ＣＰＵ１７５２からの指示に従って、領域１７７２に格納されたデータに、宛先たる受信側ＰＭのネットワーク上の識別子を接合したデータ（つまり図４に示したパケットフォーマットを満足するデータ）を読み出し、そのデータをネットワーク上に送出するようになっている。
【０１１３】
なお、図７中の括弧付数字（０）〜（１２）は、中間ブロッキングＰＭ１５００における処理に対応して付されたもので、中間ブロッキングＰＭ１５００の動作を後述する際に用いられるものである。また、図７には、中間ブロッキングＰＭ１５００の構成のみ示しているが、他の中間ブロッキングＰＭ１５０１，１５０２も同様に構成されていることはいうまでもない。
【０１１４】
上述のごとく構成された中間ブロッキングＰＭ１５００の、前記第２ステップに際しての動作概要を以下に説明する。この説明に際して、図７中の括弧付数字（０）〜（１２）と以下の項目の括弧付数字（０）〜（１２）とは対応している。
（０）図７には図示しない制御用ＰＭ１６００（図３参照）から、行なうべき処理の記述、例えば処理対象の領域１７５５の識別子，ｎおよびＢの値，受信側ＰＭ群７０の識別子リストなどがＣＰＵ１７５２に送付され、これらのデータにより主記憶１７５３の内部制御テーブル群が初期化される。初期化を終了すると、ＣＰＵ１７５２は、その旨を応答として制御用ＰＭ１６００に返し、次に制御用ＰＭ１６００から処理開始の指示が来ると処理を開始する。具体的な処理は、各バケットグループ毎に完結する。即ち、制御用ＰＭ１６００は、処理開始の指示に伴い、いずれのバケットグループを処理対象とするかを、０〜ｍ−１の番号をこの指示内に含ませることにより指定する。
【０１１５】
（１）ＣＰＵ１７５２は、制御用ＰＭ１６００からの指示内に含まれる番号（０〜ｍ−１）に応じたバケットグループの格納領域を記述するカウンタ１７６４と領域１７６５との対を選択する。ここでは、バケットグループの読出終了は、領域１７６５の無効なエントリを読み出すことにより判定可能であるものとする。ＣＰＵ１７５２は、選択したカウンタ１７６４の値を０に初期化する。
【０１１６】
（２）ＣＰＵ１７５２は、現在処理対象になっているバケットグループに対応したカウンタ１７６４の値から、二次記憶装置１７５０の領域１７５５内の、当該バケットグループのデータの次の格納領域の値を格納している領域１７６５内のエントリのアドレスを得て、このエントリにアクセスし、その内容たる格納領域アドレスを得る。この後、カウンタ１７６４の値は１エントリ分だけインクリメントされる。なお、このとき読み出された領域１７６５内のエントリの値が無効である時（例えば負の値である時）には、このバケットグループに対する処理は終了したと見做され、下記項目（１２）の処理にジャンプする。ＣＰＵ１７５２は、選択された領域１７６５のエントリから読み出された二次記憶装置１７５０内部の格納アドレスを使用して、二次記憶装置１７５０の領域から１ブロック分のデータを入力バッファ１７７１に読み出すための入出力コマンドを生成し、そのコマンドをＩ／Ｏ回路１７５４に通知してＩ／Ｏ処理を開始させる。なお、上述した１ブロックの大きさは、第１ステップのデータ格納に使用された大きさと同じで、この大きさは、二次記憶装置１７５０が要求するＩ／Ｏアクセス単位の容量の保証要求を満足するものである。
【０１１７】
（３）Ｉ／Ｏ回路１７５４は、ＣＰＵ１７０２から指定されたデータブロック１７７０を、二次記憶装置１７５０からバッファ１７７１内部に読み出す。
（４）Ｉ／Ｏ回路１７５４は、要求された入力処理を終了したことを、割込みによりＣＰＵ１７５２に通知する。
（５）ＣＰＵ１７５２は、バッファ１７７１内部から１タプル分のデータ（タプルデータにバケット識別子を接合されたデータ）１７７２を抽出し、このデータ１７７２に対して以下の処理（６）〜（１０）を施す。この処理は、バッファ１７７１内部にある全てのタプルに対して行なわれる。
【０１１８】
（６）タプルデータ１７７２に接合されたバケット識別子がＣＰＵ１７５２に取り込まれる。ＣＰＵ１７５２は、そのバケット識別子に対応する、ラウンドロビンポインタ１７７３の１エントリを特定する。
（７）ラウンドロビンポインタ１７７３により指定されるポインタ値により、そのポインタ値をＰＭ識別子に変換する変換表１７１３が索引され、宛先情報、つまりこのタプルデータ１７７２を受信すべき受信側ＰＭの識別子が得られる。また、この時、ポインタ（１７７３中の１エントリ）の内容は１だけインクリメントされた後、受信側ＰＭ数による整数剰余演算の結果が代入され直す。
【０１１９】
（８）得られた宛先情報が、〔タプルデータ＋バケット識別子〕のデータ１７７２（図７中の左側）に接続され、転送パケット１７７５が主記憶１７０３上に生成される。
（９）ＣＰＵ１７５２は、インタフェース回路１７５１に対し、転送パケット１７７５の格納領域の主記憶内先頭アドレスを示して送出を指示する。
【０１２０】
（１０）転送パケット（タプルデータ）１７７５は、インタフェース回路１７５１により、即時に（ＣＰＵ１７５２に同期して）ネットワークに送出される。本実施例では、第１ステップにおける送信側ＰＭ６００の動作においても前述した通り、ネットワーク上のプロトコルは簡単化され、ＣＰＵ１７５２から可視のＡＣＫ（Ａｃｋｎｏｗｌｅｄｇｅ）信号などの応答はないものとする。
【０１２１】
（１１）上記項目（２）の処理に戻る。
（１２）あるバケットグループの全データに対して処理が終了したことが検出されると、ＣＰＵ１７５２は、制御用ＰＭ１６００に対してその旨を報告し、制御用ＰＭ１６００からの指示を待つ。制御用ＰＭ１６００からの指示が処理終了指示であった場合には、ＣＰＵ１７５２は、全ての作業領域を解放し、処理を終了する。一方、制御用ＰＭ１６００からの指示が次のバケットグループに関する処理の開始指示（その指示の内部にバケットグループの識別子を含む）であった場合〔上記項目（０）の処理の後半部と同じ〕には、上記項目（１）以降の処理を再開する。
【０１２２】
図８は、前述した第２ステップにおける受信側ＰＭ７００の内部構造および動作を説明するためのブロック図であり、この図８において、１７８０はＰＭ７００に接続された二次記憶装置（前述した二次記憶装置２４に対応）で、この二次記憶装置１７８０は、後述するごとく、その内部に、第２ステップで受理されたデータ〔バケット９２０−１〜９２０−ｍ・ｎ（図３参照）の和集合の部分集合〕１７８５を格納する領域を有している。
【０１２３】
また、受信側ＰＭ７００には、対ＰＭ間ネットワークインタフェース回路１７８１，ＣＰＵ回路１７８２，主記憶１７８３およびＩ／Ｏ回路１７８４が内蔵されている。ここで、インタフェース回路１７８１は図９にて前述したアクセス機構２２に対応し、ＣＰＵ回路１７８２は図９にて前述したＣＰＵ２０に対応し、主記憶１７８３は図９にて前述したメモリ２１に対応し、Ｉ／Ｏ回路１７８４は図９にて前述したＩ／Ｏ機構２３に対応している。
【０１２４】
さらに、１７９０〜１７９５は主記憶１７８３上の領域であり、１７９５は、第２ステップの処理で生成される、各バケットの二次記憶装置１７８０内における格納アドレスを記述する情報を格納する領域である。また、１７９４は、各領域１７９５の情報内の、各Ｉ／Ｏアクセス単位に関する記述を逐次的にアクセスするためのカウンタであり、各ポインタ１７９４の内容から、対応する領域１７９５内の各エントリのアドレスを容易に生成できるようになっている。
【０１２５】
１７９０はインタフェース回路１７８１が中間ブロッキングＰＭ群１５０から受理したデータを一時的に格納する受信バッファ、１７９１はｎ種類のＩ／Ｏブロッキングバッファ（０〜ｎ−１；図２，図３に示すＩ／Ｏブロッキングバッファ７１に対応）で、各Ｉ／Ｏブロッキングバッファ１７９１は、前述したように、二次記憶装置１７８０が要求するＩ／Ｏアクセス単位の容量の保証の要求を満足する大きさを有し、バケット種別と１対１に対応している。
【０１２６】
１７９２はＩ／Ｏ回路１７８４へ出力すべきデータもしくはＩ／Ｏ回路１７８４から入力されたデータを一時的に格納する入出力バッファ（Ｉ／Ｏバッファ）、１７９３は領域１７９５内への書込ポインタで、この書込ポインタ１７９３は、領域１７９５に対する入出力処理を１回終了する度にバッファ１７９２の大きさだけインクリメントされるようになっている。
【０１２７】
なお、前述したカウンタ１７９４は、各バケットグループが書き込まれたファイル内位置（アドレス）を記憶する領域１７９５への書込ポインタとしても機能するもので、書込ポインタ（カウンタ）１７９４と領域１７９５とは、１対１の対になって、それぞれのバケット種別に対応して設けられている。
なお、図８中の括弧付数字（０）〜（９）は、受信側ＰＭ７００における処理に対応して付されたもので、受信側ＰＭ７００の動作を後述する際に用いられるものである。また、図８には、受信側ＰＭ７００の構成のみ示しているが、他の受信側ＰＭ７０１，７０２も同様に構成されていることはいうまでもない。
【０１２８】
上述のごとく構成された受信側ＰＭ７００の、前記第２ステップに際しての動作概要を以下に説明する。この説明に際して、図８中の括弧付数字（０）〜（９）と以下の項目の括弧付数字（０）〜（９）とは対応している。
（０）図８には図示しない制御用ＰＭ１６００（図３参照）から、行なうべき処理の記述、例えば対象テーブルの識別子，バケット識別子の値域幅，ｎの値，転送されるデータ量の予想値，交信しなければならない中間ブロッキングＰＭ群１５０の一覧などが送付される。これにより、ＣＰＵ１７８２は、主記憶１７８３内の制御表を初期化し、初期化を終了すると、その旨を制御用ＰＭ１６００に対して応答し、その後、制御用ＰＭ１６００から処理開始の指示が来ると処理を開始する。なお、初期化の例としては、領域１７９５の全エントリを無効な値（例えば負の値）に設定するとともに、書込ポインタ（カウンタ）１７９４の全ての値を０に設定する。
【０１２９】
（１）ネットワークインタフェース回路１７８１は、タプルを受信すると、これを割込みによりＣＰＵ１７８２に伝達する。ＣＰＵ１７８２は、領域１７９０の先頭アドレスを通知することにより、タプルを領域１７９０に取り込むことを指示する。
（２）タプル内のバケット識別子フィールドがＣＰＵ１７８２により参照され、このタプルが属するべきバケットがいずれであるかが認識される。
【０１３０】
（３）このバケット識別子により、領域１７９０に格納されたデータからタプルデータ部分のみが抽出され、そのタプルデータ部分が、そのバケット種別に対応するＩ／Ｏブロッキングバッファ１７９１に蓄積される。もし、この蓄積処理により、Ｉ／Ｏブロッキングバッファ１７９１内に蓄積されたデータ量が、二次記憶装置１７８０の要求するＩ／Ｏアクセス単位の容量の保証に関する要求を満たさないならば、後述する項目（９）の処理へジャンプする。
【０１３１】
（４）Ｉ／Ｏブロッキングバッファ１７９１へのデータ蓄積量が、二次記憶装置１７８０の要求するＩ／Ｏアクセス単位の容量の保証に関する要求を満たすようになったならば、このバッファ１７９１の内容は、Ｉ／Ｏバッファ１７９２に転送された後、クリアされる。
（５）ＣＰＵ１７８２は、書込ポインタ１７９３の値の内容を取り込み、書込位置を得る。また、その後、ポインタ１７９３の内容は、Ｉ／Ｏバッファ１７９２の大きさけインクリメントされる。
【０１３２】
（６）ＣＰＵ１７８２により、吐き出しが行なわれる対象であるバケットに対応した、書込ポインタ（カウンタ）１７９４と領域１７９５との対が選択される。
（７）上記項目（６）の処理で選択された書込ポインタ１７９４と領域１７９５との対において、書込ポインタ１７９４で示される領域１７９５のエントリが選択され、そのエントリに上記項目（５）の処理で得られた書込位置が記入される。この後、その書込ポインタ１７９４の内容は１エントリ分だけインクリメントされる。
【０１３３】
（８）ＣＰＵ１７８２は、Ｉ／Ｏバッファ１７９２の内容を上記項目（５）の処理で得られた書込位置（二次記憶装置１７８０上の位置）へ格納するための入出力コマンドを生成し、そのコマンドをＩ／Ｏ回路１７８４に送付する。
（９）そして、ＣＰＵ１７５２は、制御用ＰＭ１６００からの終了信号、あるいは新たなタプルの到着を示すネットワークインタフェース回路１７８１からの割込み信号が到着するまで待機する。もし、制御用ＰＭ１６００からの終了信号が到来した場合には、バッファ１７９１のうち空きでない全てのものについて、上記項目（４）以降の処理を行ない、その上で内部制御情報を書込ポインタ（カウンタ）１７９４および領域１７９５を除いて解放し、処理終了報告を制御用ＰＭ１６００に返す。これらの書込ポインタ１７９４および領域１７９５に格納されている情報は、二次記憶装置１７８０の領域１７８５内に格納されたデータとともに本処理（第２ステップ）の出力であって、これらの出力を用いることにより、次の処理において各バケット毎にデータを高速に読み出すことを可能としている。
【０１３４】
このようにして、本実施例は、並列プロセッサ装置を構成する各ＰＭにおいて必要とされる主記憶容量の大幅な低減に寄与することになる。
即ち、本実施例において、バケット分割に必要なブロッキングバッファ容量の和は、高々、（ｍ＋ｎ＋２）×〔Ｉ／Ｏアクセス単位〕で済む。ここで、ｍ＝ｎと仮定すれば、その値は、ほぼ、２・〔バケット総数〕１／２  ・〔Ｉ／Ｏアクセス単位〕である。従来、この値は、〔バケット総数〕・〔Ｉ／Ｏアクセス単位〕であった。通常、バケット数は数百のオーダであるから、本発明の主記憶容量の低減の効果によれば、上記必要なブロッキングバッファ容量を十数分の１にできることになる。
【０１３５】
具体的には、容量１００ＧＢのデータベースを、容量６４ＧＢの主記憶をもつＰＭで取り扱う場合、通常、バケット数は両者の比である１６００個程度となり、且つ、通常のＩ／Ｏ装置では、２５６ＫＢ程度が、所謂、「性能保証のために必要とされるＩ／Ｏアクセス単位最低容量」であるから、既存技術では容量４００ＭＢのバッファが個々のＰＭに必要である。このようなバッファは、勿論矛盾を発生しており、仮想記憶機構を使用しなければ実現不可能ということになる。これに対して、本発明によれば、中間ブロッキングＰＭ群１５０および受信側ＰＭ群７０を同一のＰＭで実現したとしても、１つのＰＭ当たり容量２０ＭＢのバッファがあれば良く、主記憶ベースで実現することができる。
【０１３６】
また、このことにより、本発明の技術を、例えば仮想記憶記憶にブロッキングバッファを配置した既存技術と比較すると、その性能改善効果は、およそ次の式で示されるオーダとなる。
〔改善効果〕＝ＲＳ  ／（２・Ｒｒ  ）
ここで、ＲＳ  はＩ／Ｏアクセス単位に関する性能保証のための要求が満足された場合の二次記憶性能であり、Ｒｒ  はタプル単位のランダムアクセス処理を行なった場合の二次記憶性能である。ただし、Ｒｒ  の実効性能とは、仮想記憶機構は一度要求された主記憶ページを二次記憶から読み込み、上位アプリケーション（この場合、データベース・マネージメント・システム）の処理が終了した後にそのページを二次記憶機構に書き戻すため、この処理に要する時間で、タプル長を割った値である。アクセスが本当にランダムで、ブロッキングバッファの必要容量が主記憶容量に比較して余りに巨大な場合（このような場合をＶＲ比が悪いという）、性能改善効果は上式のようになる。
【０１３７】
上式の値は、２００Ｂ程度のタプル平均長を例にとると、４５０程度になる。つまり、本発明により、並列プロセッサ装置の性能は４５０倍程度改善されたことになる。
このように、本実施例では、充分なバケット書込／読出性能を保証するために、あるバケットに属するタプル群（レコード群）を、ある程度まとまった量となるまで、メモリ（主記憶のＩ／Ｏブロッキングバッファ）上で蓄積してから二次記憶装置に書き込む際に、この作業のために必要とされるメモリ容量を抑制している。
【０１３８】
従って、既存技術では、上記バケット書込／読出性能の保証のためのメモリ（主記憶）上のブロッキング作業は、莫大なメモリ量を要請し、結果として不可能であったが、本発明によれば、通常範囲のメモリ量（主記憶容量）でのバケット書込／読出性能の保証のためのブロッキング作業が初めて可能となり、結果としてバケット書込／読出性能が大幅に改善される。
【０１３９】
また、本実施例では、ある種別のバケットを担当するＰＭを１台に制限せず、各ＰＭにおける負荷の平坦化を行なうことにより、１つのＰＭ当たりの担当バケット数が低減されるとともに、通常発生するバケット間の容量の差によるＰＭ間の負荷の偏りの発生が確実に防止され、特定のＰＭへの負荷集中による全体のスループットの低下が防止されるので、処理性能のさらなる向上に寄与することができる。
【０１４０】
なお、上述した実施例では、送信側ＰＭ群６０と受信側ＰＭ群７０との間に、中間ブロッキングＰＭ群１５０を１段のみ介在させた構成の並列プロセッサ装置について説明したが、本発明は、これに限定されるものではなく、前述した通り、中間ブロッキングＰＭ群１５０を複数段に構成してバケット数を複数乗根することによってし、極めて大きなバケット数にも対応することができるようにすることも可能である。
【０１４１】
また、上述した実施例では、第１負荷平坦化手段および第２負荷平坦化手段をラウンドロビンポインタ１７１２，１７７３にて構成した場合について説明したが、本発明は、これに限定されるものではなく、前述したように、第１負荷平坦化手段として、各バケットおよび中間ブロッキングＰＭ識別子によるアドレスが可能で各中間ブロッキングＰＭ１５００〜１５０２へのデータ送付量を積算するテーブルを用い、第２負荷平坦化手段として、各バケットおよび受信側ＰＭ識別子によるアドレスが可能で各受信側ＰＭ７００〜７０２へのデータ送付量を積算するテーブルを用いてもよい。
【０１４２】
この場合、各テーブルのデータ送付量を参照し、そのデータ送付量の最も少ないＰＭに対してタプルデータを送信するように構成することで、タプルデータを各ＰＭに対して均一またはほぼ均一に送付して、各ＰＭにおける負荷を平坦化することができ、上記実施例と同様の作用効果が得られる。
【０１４３】
【発明の効果】
以上詳述したように、本発明の並列プロセッサ装置によれば、中間プロセッサ群を介在させて、少なくとも２段階のデータ分割処理を行なうことにより、各プロセッサに、タプルの総種別数分のバッファをそなえることなく、データをバケットに分割して第２プロセッサ群に属する各プロセッサに格納させることができるので、バケット分割処理の性能の低下を招くことなく、通常範囲のメモリ量でのバケット書込／読出性能の保証のためのブロッキング作業を行なうことが可能になり、結果としてバケット書込／読出性能が大幅に改善される効果がある（請求項１〜４）。
【０１４４】
また、ある種別のバケットを担当するプロセッサを１台に制限せず、各プロセッサにおける負荷の平坦化を行なうことにより、１つのプロセッサ当たりの担当バケット数が低減されるとともに、通常発生するバケット間の容量の差によるプロセッサ間の負荷の偏りの発生が確実に防止され、特定プロセッサへの負荷集中による全体のスループットの低下が防止されるので、処理性能のさらなる向上に寄与できるという効果もある（請求項５，６）。
【図面の簡単な説明】
【図１】本発明の原理ブロック図である。
【図２】本発明の一実施例としての並列プロセッサ装置の原理的な構成および動作を説明するためのブロック図である。
【図３】本発明の一実施例としての並列プロセッサ装置の全体構成を概略的に示すブロック図である。
【図４】本実施例におけるＰＭ間ネットワークを流れるパケットの概略構成を説明するための図である。
【図５】本実施例の第１ステップにおける送信側ＰＭの内部構造および動作を説明するためのブロック図である。
【図６】本実施例の第１ステップにおける中間ブロッキングＰＭの内部構造および動作を説明するためのブロック図である。
【図７】本実施例の第２ステップにおける中間ブロッキングＰＭの内部構造および動作を説明するためのブロック図である。
【図８】本実施例の第２ステップにおける受信側ＰＭの内部構造および動作を説明するためのブロック図である。
【図９】一般的な並列計算機システムの構成例を示すブロック図である。
【図１０】一般的な並列計算機システムにおける論理的な処理を説明するためのブロック図である。
【図１１】一般的な並列計算機システムが行なう処理の概要を説明するためのブロック図である。
【図１２】代表的な二次記憶装置としての磁気ディスク装置を示す模式図である。
【図１３】アクセス効率の悪いデータベース処理例を説明するための図である。
【図１４】アクセス効率の良いデータベース処理例を説明するための図である。
【図１５】一般的な並列計算機システムにおける第２プロセッサ群に属するプロセッサモジュールの内部構造を説明するための図である。
【符号の説明】
１  プロセッサモジュール（ＰＭ）
２  第１プロセッサ群
３  第２プロセッサ群
４  中間プロセッサ群
５  第１分割手段
６  第２分割手段
６０  送信側ＰＭ群（第１プロセッサ群）
６００〜６０２  プロセッサモジュール（ＰＭ）
７０  受信側ＰＭ群（第２プロセッサ群）
７１  Ｉ／Ｏブロッキングバッファ
７００〜７０２  プロセッサモジュール（ＰＭ）
１５０  中間ブロッキングＰＭ群（中間プロセッサ群）
１５１  Ｉ／Ｏブロッキングバッファ
１５００〜１５０２  プロセッサモジュール（ＰＭ）
１６００  制御用ＰＭ（制御用プロセッサ）
１７００  二次記憶装置
１７０１  Ｉ／Ｏ回路
１７０２  ＣＰＵ回路
１７０３  主記憶
１７０４  対ＰＭ間ネットワークインタフェース回路
１７１２  ラウンドロビンポインタ（第１負荷平坦化手段）
１７５０  二次記憶装置
１７５１  対ＰＭ間ネットワークインタフェース回路
１７５２  ＣＰＵ回路
１７５３  主記憶
１７５４  Ｉ／Ｏ回路
１７６１  Ｉ／Ｏブロッキングバッファ
１７７３  ラウンドロビンポインタ（第２負荷平坦化手段）
１７８０  二次記憶装置
１７８１  対ＰＭ間ネットワークインタフェース回路
１７８２  ＣＰＵ回路
１７８３  主記憶
１７８４  Ｉ／Ｏ回路
１７９１  Ｉ／Ｏブロッキングバッファ
【図１】
0003560690.tif 000002
【図２】
0003560690.tif 000003
【図３】
0003560690.tif 000004
【図４】
0003560690.tif 000005
【図５】
0003560690.tif 000006
【図６】
0003560690.tif 000007
【図７】
0003560690.tif 000008
【図８】
0003560690.tif 000009
【図９】
0003560690.tif 000010
【図１０】
0003560690.tif 000011
【図１１】
0003560690.tif 000012
【図１２】
0003560690.tif 000013
【図１３】
0003560690.tif 000014
【図１４】
0003560690.tif 000015
【図１５】
0003560690.tif 000016