(57)【特許請求の範囲】
【請求項１】
それぞれ、メモリおよび制御装置を有する、複数のメモリモジュールと、
前記メモリモジュール間を接続し、あるメモリモジュールが保持するデータを他のメモリモジュールに伝達するデータ伝送路と、を備え、
各メモリモジュールの前記メモリが、それぞれ、昇順または降順に重複なく順序付けられた、値のリストを保持するように構成された情報処理システムであって、
各メモリモジュールの前記制御装置が、
当該メモリモジュールによって保持された前記値のリストに含まれる格納値を他のメモリモジュールに送信するデータ送信手段と、
前記他のメモリモジュールから、前記他のメモリモジュールによって保持された前記値のリストに含まれる前記格納値を受信するデータ受信手段と、
前記データ受信手段によって受信された前記他のメモリモジュールからの前記値のリストと、前記他のメモリモジュールに対し決められた順番及び当該メモリモジュールに対し決められた順番とに基づいて、当該メモリモジュールが当該メモリモジュールによって保持された値のリスト中のある格納値を保持する一つ以上のメモリモジュールを代表する代表モジュールであるか否かを判断し、当該メモリモジュールが前記代表モジュールである場合に、当該メモリモジュールが代表モジュールであることを示す情報を前記ある格納値と関連付けて記憶する代表モジュール判断手段と、を備え、
前記複数のメモリモジュールによって保持された前記値のリスト中のそれぞれの格納値についての前記代表モジュールを決定することを特徴とする情報処理システム。
【請求項２】
当該メモリモジュールの前記代表モジュール判断手段が、当該メモリモジュールに対し決められた前記順番が当該メモリモジュールによって保持される前記値のリスト中の前記ある格納値を保持する前記一つ以上のメモリモジュールに対し決められた前記順番と所定の関係にある場合に、当該メモリモジュールが前記格納値についての前記代表モジュールであると判断することを特徴とする請求項１に記載の情報処理システム。
【請求項３】
前記複数のメモリモジュールの前記順番が前記複数のメモリモジュールの各々に付与されたモジュール番号によって決められ、
当該メモリモジュールの前記代表モジュール判断手段が、
当該メモリモジュールが保持する前記値のリストと同一のサイズの片側カウント配列を生成し、前記片側カウント配列に初期値を格納し、
前記値のリストを送信した前記他のメモリモジュールに付与されたモジュール番号が、当該メモリモジュールに付与されたモジュール番号より下位或いは上位の何れか片側にあり、かつ、当該メモリモジュールが保持する前記値のリスト中の前記ある格納値が、当該他のメモリモジュールからの前記値のリスト中に存在するときに、当該メモリモジュールが保持する前記値のリスト中の前記ある格納値が、当該他のメモリモジュールに存在していることを示すために、前記ある格納値に対応する前記片側カウント配列中の値を増大させ、
前記片側カウント配列中の値が前記初期値のままであるときに、当該メモリモジュールが、前記片側カウント配列中の前記初期値に対応する、前記値のリスト中の前記ある格納値についての前記代表モジュールであると判断することを特徴とする請求項２に記載の情報処理システム。
【請求項４】
前記複数のメモリモジュールの前記順番が前記複数のメモリモジュールの各々に付与されたモジュール番号によって決められ、
当該メモリモジュールの前記代表モジュール判断手段が、
当該メモリモジュールが保持する前記値のリストと同一のサイズの出現カウント配列を生成し、前記出現カウント配列に初期値を格納し、
当該メモリモジュールが保持する前記値のリスト中の前記ある格納値が、前記他のメモリモジュールからの前記値のリスト中に存在するときに、当該メモリモジュールが保持する前記値のリスト中の前記ある格納値が当該他のメモリモジュールに存在していることを示すために、前記ある格納値に対応する前記出現カウント配列の値を増大させ、
当該メモリモジュールが保持する前記値のリストと同一のサイズの片側カウント配列を生成し、当該片側カウント配列に初期値を格納し、
前記値のリストを送信した前記他のメモリモジュールの前記モジュール番号が、当該メモリモジュールの前記モジュール番号より下位或いは上位の何れか片側にあり、かつ、当該メモリモジュールが保持する値のリスト中の前記ある格納値が、当該他のメモリモジュールからの値のリスト中に存在するときに、当該メモリモジュールが保持する値のリスト中の前記ある格納値が、当該他のメモリモジュールに存在していることを示すために、前記ある格納値に対応する前記片側カウント配列中の値を増大させ、
前記値のリスト中の前記格納値に対応する前記片側カウント配列中の値と前記出現カウント配列中の対応する値とを比較して、これらの値が一致するときに、当該メモリモジュールが前記値のリスト中の前記ある格納値についての前記代表モジュールであると判断することを特徴とする請求項２に記載の情報処理システム。
【請求項５】
前記複数のメモリモジュールの前記順番が前記複数のメモリモジュールの各々に付与されたモジュール番号によって決められ、
当該メモリモジュールの前記代表モジュール判断手段が、
当該メモリモジュールが保持する前記値のリストと同一のサイズのフラグ配列を生成し、前記フラグ配列に初期値を格納し、
前記値のリストを送信した前記他のメモリモジュールの前記モジュール番号が、当該メモリモジュールの前記モジュール番号より下位或いは上位の何れか片側にあり、かつ、当該メモリモジュールが保持する前記値のリスト中の前記ある格納値が、当該他のメモリモジュールからの前記値のリスト中に存在するときに、当該メモリモジュールが保持する前記値のリスト中の前記ある格納値が当該他のメモリモジュールに存在していることを示すために、前記ある格納値に対応する前記フラグ配列中の値をセットし、
前記値のリスト中の前記格納値に対応する前記フラグ配列中の値が初期値であるときに、当該メモリモジュールが前記値のリスト中の前記ある格納値についての前記代表モジュールであると判断することを特徴とする請求項２に記載の情報処理システム。
【請求項６】
請求項１ないし５の何れか一項に記載の情報処理システムにおいて、
各メモリモジュールの前記制御装置が、
当該メモリモジュールが保持する前記値のリスト中の前記格納値のうち、前記代表モジュールであることを示す情報が付与されているものを含む送出リスト配列を生成する送出リスト配列生成手段と、
前記他のメモリモジュールのデータ送信手段から送信され、当該メモリモジュールの前記データ受信手段により受信された、前記他のメモリモジュールの前記送出リスト配列中の格納値に基づいて、当該メモリモジュールが保持する前記値のリスト中の前記格納値の順位を算出する順位算出手段と、を備えたことを特徴とする情報処理システム。
【請求項７】
前記順位算出手段が、
当該メモリモジュールが保持する前記値リスト中の隣接する格納値の間に、前記他のメモリモジュールからの前記送出リスト配列中の格納値がいくつ存在するかを判断し、前記判断された存在数に基づいて、前記格納値のそれぞれの順位を算出することを特徴とする請求項６に記載の情報処理システム。
【請求項８】
メモリおよび制御装置を有し、予め順序付けられた複数のメモリモジュールと、
前記メモリモジュール間を接続し、あるメモリモジュールが保持するデータを他のメモリモジュールに伝達するデータ伝送路と、を備え、
各メモリモジュールの前記メモリが、それぞれ、昇順または降順に重複なく順序付けられた、値のリストを保持するように構成された情報処理システムであって、
各メモリモジュールの前記制御装置が、
当該メモリモジュールによって保持された前記値のリストに含まれる格納値を他のメモリモジュールに送信するデータ送信手段と、
前記他のメモリモジュールから、前記他のメモリモジュールによって保持された前記値のリストに含まれる前記格納値を受信するデータ受信手段と、
当該メモリモジュールが保持する値のリストと同一のサイズの出現カウント配列を生成し、前記出現カウント配列に初期値を格納し、当該メモリモジュールが保持する前記値のリスト中のある格納値が、前記他のメモリモジュールからの前記値のリスト中に存在するときに、当該メモリモジュールが保持する前記値のリスト中の前記ある格納値が当該他のメモリモジュールに存在していることを示すために、前記ある格納値に対応する前記出現カウント配列の値を増大させることにより、前記出現カウント配列を完成させる出現カウント配列生成手段と、
当該メモリモジュールが保持する前記値のリストと同一のサイズの片側カウント配列を生成し、前記片側カウント配列に初期値を格納し、前記値のリストを送信した前記他のメモリモジュールのモジュールの順番が、下位或いは上位の何れか片側にあり、かつ、当該メモリモジュールが保持する前記値のリスト中の前記格納値が、当該他のメモリモジュールからの前記値のリスト中に存在するときに、当該メモリモジュールが保持する前記値のリスト中の前記ある格納値が当該他のメモリモジュールに存在していることを示すために、前記ある格納値に対応する前記片側カウント配列の値を増大させることにより、前記片側カウント配列を完成させる片側カウント配列生成手段と、
前記他のメモリモジュールに送出するための、当該メモリモジュールが保持する前記値のリストと同一サイズの送出リスト配列を生成し、前記値リスト中の前記格納値に対応する前記出現カウント配列の値と前記片側カウント配列の対応する値とを比較して、双方の値が一致する場合に、当該メモリモジュールが前記格納値を保持する最上位或いは最下位のメモリモジュールであることを示す第１の値を格納し、前記双方の値が一致しない場合に、それ以外の第２の値を格納して、前記送出リスト配列を完成させる送出リスト配列生成手段と、
前記他のメモリモジュールの前記データ送信手段により送信され、当該メモリモジュールの前記データ受信手段により受信された、前記他のメモリモジュールの前記値のリストおよび前記送出リスト配列に基づいて、当該メモリモジュールが保持する前記値のリスト中の格納値の順位を算出する順位算出手段と、を備えたことを特徴とする情報処理システム。
【請求項９】
前記順位算出手段が、
当該メモリモジュールが保持する前記値リスト中の隣接する格納値の間に存在する、前記他のメモリモジュールの前記値のリスト中の格納値を特定し、前記特定された格納値に対応する、前記送出リスト配列の値の総和に基づいて、前記隣接する格納値の間に、前記他のメモリモジュールの前記値のリスト中の前記特定された格納値がいくつ存在するかを判断し、前記判断された存在数に基づいて、当該メモリモジュールが保持する前記値のリスト中の前記格納値のそれぞれの順位を算出することを特徴とする請求項８に記載の情報処理システム。
【請求項１０】
それぞれ、メモリおよび制御装置を有する、複数のメモリモジュールと、
前記メモリモジュール間を接続し、あるメモリモジュールが保持するデータを他のメモリモジュールに伝達するデータ伝送路と、を備え、
各メモリモジュールの前記メモリが、それぞれ、昇順または降順に重複なく順序付けられた、値のリストを保持するように構成された情報処理システムであって、
各メモリモジュールの前記制御装置が、
当該メモリモジュールによって保持された前記値のリストに含まれる格納値を他のメモリモジュールに送信するデータ送信手段と、
前記他のメモリモジュールから、前記他のメモリモジュールによって保持された前記値のリストに含まれる前記格納値を受信するデータ受信手段と、
当該メモリモジュールが保持する前記値のリストと同一のサイズの出現カウント配列を生成し、前記出現カウント配列に初期値を格納し、当該メモリモジュールが保持する前記値のリスト中のある格納値が、前記他のメモリモジュールからの前記値のリスト中に存在するときに、当該メモリモジュールが保持する前記値のリスト中の前記ある格納値に対応する前記出現カウント配列の値を増大させることにより、前記出現カウント配列を完成させる出現カウント配列生成手段と、
(i)前記他のメモリモジュールの前記データ送信手段により送信され、当該メモリモジュールの前記データ受信手段により受信された、前記他のメモリモジュールの前記値のリストおよび前記出現カウント配列を入力し、(ii)当該メモリモジュールが保持する前記値のリスト中の隣接する格納値の間に存在する、前記他のメモリモジュールの前記値のリスト中の前記格納値に対応する前記他のメモリモジュールの前記出現カウント配列の値の逆数を累算し、(iii)前記累算された逆数を累計数化し、(iv)前記累計数化された逆数に当該メモリモジュールが保持する前記値のリスト中の前記格納値の初期順位を加算することにより、当該メモリモジュールが保持する前記値のリスト中の前記格納値の順位を算出する順位算出手段と、を備えたことを特徴とする情報処理システム。
【請求項１１】
それぞれ、メモリおよび制御装置を有する、複数のメモリモジュールと、
前記メモリモジュール間を接続し、あるメモリモジュールが保持するデータを他のメモリモジュールに伝達するデータ伝送路と、を備え、
各メモリモジュールの前記メモリが、それぞれ、昇順または降順に重複なく順序付けられた、値のリストを保持するよう構成された情報処理システムの、各メモリモジュールの前記制御装置において実行される情報処理方法であって、
当該メモリモジュールの前記制御装置が備えるデータ送信手段が、当該メモリモジュールによって保持された前記値のリストに含まれる格納値を他のメモリモジュールに送信するデータ送信ステップと、
当該メモリモジュールの前記制御装置が備えるデータ受信手段が、前記他のメモリモジュールから、当該他のメモリモジュールによって保持された前記値のリストに含まれる格納値を受信するデータ受信ステップと、
当該メモリモジュールの前記制御装置が備える代表モジュール判断手段が、前記他のメモリモジュールから受信した前記値のリストと、前記他のメモリモジュールに対し決められた順番及び当該メモリモジュールに対し決められた順番とに基づいて、当該メモリモジュールが当該メモリモジュールによって保持された前記値のリスト中のある格納値を保持する一つ以上のメモリモジュールを代表する代表モジュールであるか否かを判断し、当該メモリモジュールが前記代表モジュールである場合に、当該メモリモジュールが前記代表モジュールであることを示す情報を前記ある格納値と関連付けて記憶する代表モジュール判断ステップと、を備え、
前記代表モジュールは、前記複数のメモリモジュールによって保持された前記値のリスト中のそれぞれの格納値について決定されることを特徴とする情報処理方法。
【請求項１２】
前記代表モジュール判断ステップが、
前記順番として前記複数のメモリモジュールの各々に予め付与されたモジュール番号に基づいて、当該メモリモジュールに対し決められた順番が当該メモリモジュールによって保持された前記値のリスト中の前記ある格納値を保持する一つ以上のメモリモジュールに対し決められた順番と所定の関係にある場合に、当該メモリモジュールが前記ある格納値についての前記代表モジュールであると判断するステップを含むことを特徴とする請求項１１に記載の情報処理方法。
【請求項１３】
前記複数のメモリモジュールの前記順番が前記複数のメモリモジュールの各々に付与されたモジュール番号によって決められ、
前記代表モジュール判断ステップが、
当該メモリモジュールが保持する前記値のリストと同一のサイズの片側カウント配列を生成し、前記片側カウント配列に初期値を格納するステップと、
前記値のリストを送信した前記他のメモリモジュールの前記モジュール番号が、当該メモリモジュールの前記モジュール番号より下位或いは上位の何れか片側にあり、かつ、当該メモリモジュールが保持する前記値のリスト中の前記ある格納値が、前記他のメモリモジュールからの前記値のリスト中に存在するときに、当該メモリモジュールが保持する前記値のリスト中の前記ある格納値が前記他のメモリモジュールに存在していることを示すために、前記ある格納値に対応する前記片側カウント配列中の値を増大させるステップと、
前記片側カウント配列中の値が前記初期値のままであるときに、当該メモリモジュールが、前記片側カウント配列中の前記初期値に対応する、前記値のリスト中の前記ある格納値についての前記代表モジュールであると判断するステップと、を含むことを特徴とする請求項１２に記載の情報処理方法。
【請求項１４】
前記複数のメモリモジュールの順番が前記複数のメモリモジュールの各々に付与されたモジュール番号によって決められ、
前記代表モジュール判断ステップが、
当該メモリモジュールが保持する前記値のリストと同一のサイズの出現カウント配列を生成し、前記出現カウント配列に初期値を格納するステップと、
当該メモリモジュールが保持する前記値のリスト中のある格納値が、前記他のメモリモジュールからの前記値のリスト中に存在するときに、当該メモリモジュールが保持する前記値のリスト中の前記ある格納値が当該他のメモリモジュールに存在していることを示すために、前記ある格納値に対応する前記出現カウント配列中の値を増大させるステップと、
当該メモリモジュールが保持する前記値のリストと同一のサイズの片側カウント配列を生成し、前記片側カウント配列に初期値を格納するステップと、
前記値のリストを送信した前記他のメモリモジュールの前記モジュール番号が、当該メモリモジュールの前記モジュール番号より下位或いは上位の何れか片側にあり、かつ、当該メモリモジュールが保持する前記値のリスト中のある格納値が、当該他のメモリモジュールからの前記値のリスト中に存在するときに、当該メモリモジュールが保持する前記値のリスト中の前記ある格納値が当該他のメモリモジュールに存在していることを示すために、前記ある格納値に対応する前記片側カウント配列中の値を増大させるステップと、
前記値のリスト中の前記ある格納値に対応する前記片側カウント配列中の値と前記出現カウント配列中の対応する値とを比較して、これらの値が一致するときに、当該メモリモジュールが前記値のリスト中の前記ある格納値についての前記代表モジュールであると判断するステップと、を含むことを特徴とする請求項１２に記載の情報処理方法。
【請求項１５】
前記複数のメモリモジュールの前記順番が前記複数のメモリモジュールの各々に付与されたモジュール番号によって決められ、
前記代表モジュール判断ステップが、
当該メモリモジュールが保持する前記値のリストと同一のサイズのフラグ配列を生成し、前記フラグ配列に初期値を格納するステップと、
前記値のリストを送信した前記他のメモリモジュールの前記モジュール番号が、当該メモリモジュールの前記モジュール番号より下位或いは上位の何れか片側にあり、かつ、当該メモリモジュールが保持する前記値のリスト中のある格納値が、前記他のメモリモジュールからの前記値のリスト中に存在するときに、当該メモリモジュールが保持する前記値のリスト中の前記ある格納値が前記他のメモリモジュールに存在していることを示すために、前記ある格納値に対応する前記フラグ配列中の値をセットするステップと、
前記値のリスト中の前記格納値に対応する前記フラグ配列中の値が初期値であるときに、当該メモリモジュールが前記値のリスト中の前記ある格納値についての代表モジュールであると判断するステップと、を含むことを特徴とする請求項１２に記載の情報処理方法。
【請求項１６】
請求項１１ないし１５の何れか一項に記載の情報処理方法において、さらに
当該メモリモジュールの前記制御装置が備える送出リスト配列生成手段が、当該メモリモジュールが保持する前記値のリスト中の前記格納値のうち、前記代表モジュールであることを示す情報が付与されているものを含む送出リスト配列を生成する送出リスト配列生成ステップと、
当該メモリモジュールの前記制御装置が備える順位算出手段が、前記他のメモリモジュールのデータ送信ステップにおいて送信され、当該メモリモジュールのデータ受信ステップにおいて受信された、前記他のメモリモジュールの前記送出リスト配列中の格納値に基づいて、当該メモリモジュールが保持する前記値のリスト中の前記格納値の順位を算出する順位算出ステップと、を備えたことを特徴とする情報処理方法。
【請求項１７】
前記順位算出ステップが、
当該メモリモジュールが保持する前記値リスト中の隣接する格納値の間に、前記他のメモリモジュールの前記送出リスト配列中の格納値がいくつ存在するかを判断し、前記判断された存在数に基づいて、前記格納値のそれぞれの順位を算出するステップを含むことを特徴とする請求項１６に記載の情報処理方法。
【請求項１８】
メモリおよび制御装置を有し、予め順序付けられた複数のメモリモジュールと、
前記メモリモジュール間を接続し、あるメモリモジュールが保持するデータを他のメモリモジュールに伝達するデータ伝送路と、を備え、
各メモリモジュールの前記メモリが、それぞれ、昇順または降順に重複なく順序付けられた、値のリストを保持するように構成された情報処理システムの、各メモリモジュールの前記制御装置において実行される情報処理方法であって、
当該メモリモジュールの前記制御装置が備えるデータ送信手段が、当該メモリモジュールによって保持された前記値のリストに含まれる格納値を他のメモリモジュールに送信するデータ送信ステップと、
当該メモリモジュールの前記制御装置が備えるデータ受信手段が、前記他のメモリモジュールから、当該他のメモリモジュールによって保持された前記値のリストに含まれる前記格納値を受信するデータ受信ステップと、
当該メモリモジュールの前記制御装置が備える出現カウント配列生成手段が、当該メモリモジュールが保持する前記値のリストと同一のサイズの出現カウント配列を生成し、前記出現カウント配列に初期値を格納し、当該メモリモジュールが保持する前記値のリスト中のある格納値が、前記他のメモリモジュールからの前記値のリスト中に存在するときに、当該メモリモジュールが保持する前記値のリスト中の前記ある格納値が当該他のメモリモジュールに存在していることを示すために、前記ある格納値に対応する前記出現カウント配列中の値を増大させることにより、前記出現カウント配列を完成させる出現カウント配列生成ステップと、
当該メモリモジュールの前記制御装置が備える前記片側カウント配列生成手段が、当該メモリモジュールが保持する前記値のリストと同一のサイズの片側カウント配列を生成し、前記片側カウント配列に初期値を格納し、前記値のリストを送信した前記他のメモリモジュールのモジュールの順番が、下位或いは上位の何れか片側にあり、かつ、当該メモリモジュールが保持する前記値のリスト中のある格納値が、前記他のメモリモジュールからの前記値のリスト中に存在するときに、当該メモリモジュールが保持する前記値のリスト中の当該前記ある格納値が前記他のメモリモジュールに存在していることを示すために、前記ある格納値に対応する前記片側カウント配列中の値を増大させることにより、前記片側カウント配列を完成させる片側カウント配列生成ステップと、
当該メモリモジュールの前記制御装置が備える送出リスト配列生成手段が、前記他のメモリモジュールに送出するための、当該メモリモジュールが保持する前記値のリストと同一サイズの送出リスト配列を生成し、前記値リスト中の前記格納値に対応する前記出現カウント配列の値と前記片側カウント配列の対応する値とを比較して、双方の値が一致する場合に、当該メモリモジュールが最上位或いは最下位のメモリモジュールであることを示す第１の値を格納し、前記双方の値が一致しない場合に、それ以外の第２の値を格納して、前記送出リスト配列を完成させる送出リスト配列生成ステップと、
当該メモリモジュールの前記制御装置が備える順位算出手段が、前記他のメモリモジュールのデータ送信ステップにおいて送信され、当該メモリモジュールのデータ受信ステップにおいて受信された、前記他のメモリモジュールの前記値のリストおよび前記送出リスト配列に基づいて、当該メモリモジュールが保持する前記値のリスト中の格納値の順位を算出する順位算出ステップと、を備えたことを特徴とする情報処理方法。
【請求項１９】
前記順位算出ステップが、
当該メモリモジュールが保持する前記値リスト中の隣接する格納値の間に存在する、前記他のメモリモジュールの前記値のリスト中の格納値を特定し、前記特定された格納値に対応する、前記送出リスト配列の値の総和に基づいて、前記隣接する格納値の間に、前記他のメモリモジュールの前記値のリスト中の前記特定された格納値がいくつ存在するかを判断し、前記判断された存在数に基づいて、当該メモリモジュールが保持する前記値のリスト中の前記格納値のそれぞれの順位を算出するステップを含むことを特徴とする請求項１８に記載の情報処理方法。
【請求項２０】
それぞれ、メモリおよび制御装置を有する、複数のメモリモジュールと、
前記メモリモジュール間を接続し、あるメモリモジュールが保持するデータを他のメモリモジュールに伝達するデータ伝送路と、を備え、
各メモリモジュールの前記メモリが、それぞれ、昇順または降順に重複なく順序付けられた、値のリストを保持するように構成された情報処理システムの、各メモリモジュールの前記制御装置において実行される情報処理方法であって、
当該メモリモジュールの前記制御装置が備えるデータ送信手段が、当該メモリモジュールによって保持された前記値のリストに含まれる格納値を他のメモリモジュールに送信するデータ送信ステップと、
当該メモリモジュールの前記制御装置が備えるデータ受信手段が、前記他のメモリモジュールから、前記他のメモリモジュールによって保持された前記値のリストに含まれる前記格納値を受信するデータ受信ステップと、
当該メモリモジュールの前記制御装置が備える出現カウント配列生成手段が、当該メモリモジュールが保持する前記値のリストと同一のサイズの出現カウント配列を生成し、前記出現カウント配列に初期値を格納し、当該メモリモジュールが保持する前記値のリスト中のある格納値が、前記他のメモリモジュールからの前記値のリスト中に存在するときに、当該メモリモジュールが保持する前記値のリスト中の前記格納値に対応する前記出現カウント配列の値を増大させることにより、前記出現カウント配列を完成させる出現カウント配列生成ステップと、
当該メモリモジュールの前記制御装置が備える順位算出手段が、(i)前記他のメモリモジュールのデータ送信ステップにおいて送信され、当該メモリモジュールのデータ受信ステップにおいて受信された、前記他のメモリモジュールの前記値のリストおよび前記出現カウント配列を入力し、(ii)当該メモリモジュールが保持する前記値のリスト中の隣接する格納値の間に存在する、前記他のメモリモジュールの前記値のリスト中の前記格納値に対応する前記他のメモリモジュールの前記出現カウント配列の値の逆数を累算し、(iii)前記累算された逆数を累計数化し、(iv)前記累計数化された逆数に当該メモリモジュールが保持する前記値のリスト中の前記格納値の初期順位を加算することにより、当該メモリモジュールが保持する前記値のリスト中の前記格納値の順位を算出する順位算出ステップと、を備えたことを特徴とする情報処理方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ＳＩＭＤ(Single Instruction Stream, Multiple Data Stream)を実現可能な並列コンピュータのアーキテクチャを採用した情報処理システムに関する。
【背景技術】
【０００２】
社会全体のさまざまな場所にコンピュータが導入され、インターネットをはじめとするネットワークが浸透した今日では、そこここで、大規模なデータが蓄積されるようになった。このような大規模データを処理するには、膨大な計算が必要で、そのために並列処理を導入しようと試みるのは自然である。【０００３】
並列処理アーキテクチャは「共有メモリ型」と「分散メモリ型」に大別される。前者（「共有メモリ型」）は、複数のプロセッサが１つの巨大なメモリ空間を共有する方式である。この方式では、プロセッサ群と共有メモリ間のトラフィックがボトルネックとなるので、百を越えるプロセッサを用いて現実的なシステムを構築することは容易ではない。したがって、例えば１０億個の浮動小数点変数の平方根を計算する際、単一ＣＰＵに対する加速比は、せいぜい１００倍ということになる。経験的には、３０倍程度が上限である。【０００４】
後者（「分散メモリ型」）は、各プロセッサがそれぞれローカルなメモリを持ち、これらを結合してシステムを構築する。この方式では、数百〜数万ものプロセッサを組み込んだハードウェアシステムの設計が可能である。したがって、上記１０億個の浮動小数点変数の平方根を計算する際の単一ＣＰＵに対する加速比を、数百〜数万倍とすることが可能である。しかしながら、後者においても、後述するいくつかの課題が存在する。
【特許文献１】国際公開ＷＯ００／１０１０３号公報（第３図および第４図）
【特許文献２】国際公開ＷＯ２００４／０９２９４８号公報
【発明の開示】
【発明が解決しようとする課題】
【０００５】
[第１の課題：巨大配列の分掌管理]
「分散メモリ型」の第１の課題は、データの分掌管理の問題である。【０００６】
巨大なデータ（一般的には配列なので、以降、配列で説明する）は、１つのプロセッサの所有するローカルメモリに収容できるものではなく、必然的に複数のローカルメモリに分掌管理される。効率的かつ柔軟な分掌管理メカニズムを導入しないと、プログラムの開発および実行に際してさまざまな障害を抱え込むことになることは明らかである。
[第２の課題：プロセッサ間通信の効率の低さ]
分散メモリ型システムの各プロセッサが、巨大配列にアクセスしようとすると、自己の所有するローカルメモリ上の配列要素に対しては速やかにアクセスできるものの、他のプロセッサが所有する配列要素へのアクセスはプロセッサ間通信を必須とする。このプロセッサ間通信はローカルメモリとの通信に比べ、極端にパフォーマンスが低く、最低でも１００クロックかかると言われている。このため、ソート実施時には、巨大配列全域にわたる参照が実施され、プロセッサ間通信が多発するため、パフォーマンスが極端に低下する。【０００７】
この問題点につき、より具体的に説明を加える。１９９９年現在、パソコンは、１〜数個のＣＰＵを用いて、「共有メモリ型」として構成されている。このパソコンに使用される標準的なＣＰＵは、メモリバスの５〜６倍程度の内部クロックで動作し、その内部に自動的な並列実行機能やパイプライン処理機能が装備されており、およそ１データを１クロック（メモリバス）で処理できる。【０００８】
このため、「分散メモリ型」のマルチプロセッサシステムでは、プロセッサ数は多いのに、シングルプロセッサ（共有メモリ型）よりも１００倍遅くなることになりかねない。
[第３の課題：プログラムの供給]
「分散メモリ型」の第３の課題は、多数のプロセッサにどうやってプログラムを供給するか、という問題である。【０００９】
非常に多数のプロセッサに、別々のプログラムをロードし、全体を協調動作させる方式（ＭＩＭＤ：Multiple Instruction Stream, Multiple Data Stream）では、プログラムの作成、コンパイル、配信のために多大な負荷を要する。【００１０】
その一方、多数のプロセッサを同一のプログラムで動作させる方式（ＳＩＭＤ：Single Instruction Stream, Multiple Data Stream）では、プログラムの自由度が減少し、所望の結果をもたらすプログラムが開発できない事態も想定される。【００１１】
本発明は、「分散メモリ型」の上記第１ないし３の課題を解決する方法およびコンピュータアーキテクチャを提供する。【００１２】
ところで、本発明者は、表形式データを記憶するために、項目ごとの情報ブロックを形成し、当該情報ブロックに、項目値を記憶した値リスト、および、当該値リストを指定するための値（ポインタ値）を、レコードごとに記憶したポインタ配列を設け、レコード番号から、ポインタ配列および値リストを順次特定していくことにより、表形式のビューを取得できるような構造および処理方法を考案している（特許文献１参照）。この構造において、レコード数が増大するのにしたがって、上記値リストやポインタ配列、特に、ポインタ配列は非常に大きくなるため、これを、複数のメモリで分掌した上で、単一命令により、検索、集計、ソートなどの処理が実行できるのが望ましい。【００１３】
上述した見地から、本発明者は、特許文献２に記載されたように、隣接するＰＭＭ（プロセッサメモリモジュール）の間を、パケット伝送路で接続し、各ＰＭＭが、各々が項目と当該項目に属する項目値とを含むレコードの配列として表わされる表形式データを表現するための、特定の項目に属する項目値に対応した項目値番号の順に、当該項目値が格納されている値リスト、および、一意的な順序集合配列の順に、当該項目値番号を指示するためのポインタ値が格納されたポインタ配列からなる情報ブロックを保持した情報処理システムを提案している。この情報処理システムにおいては、各ＰＭＭにて保持された情報ブロックの集合体により、グローバルな情報ブロックが形成される。また、特許文献２によれば、ＰＭＭを接続するパケット伝送路を利用して、値リスト中の項目値の位置などを交換することにより、検索、集計、ソートなどの種々の処理が実現される。【００１４】
値リストやポインタ配列を、複数のメモリで分掌すると、局所（つまり、各メモリ）にそれぞれ保持される、重複の無い値が昇順に並んだリストを、全体（各ＰＭＭ間）で一意的に順序付けすることが求められる。また、何れかのＰＭＭにおいて、それぞれのＰＭＭが分掌した値リスト中の値に基づき、重複の無い値を含むリストを得られるようにすることも必要である。【００１５】
表形式データに限られず、複数の値を含むリスト（値のリスト）を複数のＰＭＭで分掌する場合にも、同様に、重複の無い値を含む値のリストを取得し、或いは、各ＰＭＭにおいて、自己が把握する値のリスト中の値の順位を把握することが求められる。【００１６】
そこで、本発明は、分散メモリ型において、単一命令により種々のメモリに記憶された配列中の要素を入出力し、処理と通信を統合することで著しく高速な並列処理を実現する情報処理システムおよび情報処理方法において、重複の無い昇順に並んだリストを、高速に、一意的に順序付けする手法を提供することを目的とする。また、本発明は、重複の無い昇順に並んだリストを生成する手法を提供することを目的とする。
【課題を解決するための手段】
【００１７】
本発明の目的は、それぞれ、メモリおよび制御装置を有する、複数のメモリモジュールと、
メモリモジュール間を接続し、あるメモリモジュールが保持するデータを他のメモリモジュールに伝達するデータ伝送路と、を備え、
各メモリモジュールのメモリが、それぞれ、昇順または降順に重複なく順序付けられた、値のリストを保持するように構成された情報処理システムであって、
前記各メモリモジュールの制御装置が、
他のメモリモジュールに、前記値のリストに含まれる格納値を送信するデータ送信手段と、
他のメモリモジュールから、前記値のリストに含まれる格納値を受信するデータ受信手段と、
前記メモリモジュール自身が保持する値のリスト中の格納値について、前記データ受信手段によって受信された他のメモリモジュールからの値のリストと、当該他のメモリモジュールに対し決められた順番及び当該メモリモジュール自身に対し決められた順番とに基づいて、当該メモリモジュール自身が当該格納値を保持する一つ以上のメモリモジュールを代表する代表モジュールであるか否かを判断し、前記代表モジュールである場合に、前記格納値と関連付けて、代表モジュールであることを示す情報を記憶する代表モジュール判断手段と、を備えたことを特徴とする情報処理システムにより達成される。【００１８】
本発明によれば、値のリスト中のそれぞれの値について、その値の代表モジュールとなるＰＭＭが決定され、ＰＭＭ自身がその情報を記憶するため、たとえば、いずれかのメモリモジュールにおいて、重複の無い値のリストを取得することが可能となる。【００１９】
好ましい実施態様においては、前記代表モジュール判断手段が、前記メモリモジュール自身が保持する値のリスト中の格納値について、その格納値を保持する一つ以上のメモリモジュールに対し決められた順番のうち、当該メモリモジュール自身に対し決められた順番が所定の関係にある場合に、当該メモリモジュール自身が当該格納値についての代表モジュールであると判断する。【００２０】
より好ましい実施態様においては、前記複数のメモリモジュールの順番が前記メモリモジュールの各々に付与されたモジュール番号によって決められ、
前記代表モジュール判断手段が、
前記メモリモジュール自身が保持する値のリストと同一のサイズの片側カウント配列を生成し、当該片側カウント配列に初期値を格納し、
前記値のリストを送信した他のメモリモジュールのモジュール番号が、自己のモジュール番号より下位或いは上位の何れか片側にあり、かつ、メモリモジュール自身が保持する値のリスト中の格納値が、当該他のメモリモジュールからの値のリスト中に存在するときに、前記メモリモジュール自身が保持する値のリスト中の当該格納値について、他のメモリモジュールにおける値の存在を示すために、対応する片側カウント配列の値を増大させ、
前記片側カウント配列中のそれぞれの値を参照して、前記片側カウント配列の値が初期値であるときに、当該メモリモジュール自身が、当該片側カウント配列中の値に対応する、値のリスト中の格納値についての代表モジュールであると判断する。【００２１】
別の好ましい実施態様においては、前記複数のメモリモジュールの順番が前記メモリモジュールの各々に付与されたモジュール番号によって決められ、
前記代表モジュール判断手段が、
前記メモリモジュール自身が保持する値のリストと同一のサイズの出現カウント配列を生成し、当該出現カウント配列に初期値を格納し、
前記メモリモジュール自身が保持する値のリスト中の格納値が、他のメモリモジュールからの値のリスト中に存在するときに、前記メモリモジュール自身が保持する値のリスト中の当該格納値について、他のメモリモジュールにおける値の存在を示すために、対応する出現カウント配列の値を増大させ、
前記メモリモジュール自身が保持する値のリストと同一のサイズの片側カウント配列を生成し、当該片側カウント配列に初期値を格納し、
前記値のリストを送信した他のメモリモジュールのモジュール番号が、自己のモジュール番号より下位或いは上位の何れか片側にあり、かつ、前記メモリモジュール自身が保持する値のリスト中の格納値が、当該他のメモリモジュールからの値のリスト中に存在するときに、前記メモリモジュール自身が保持する値のリスト中の当該格納値について、他のメモリモジュールにおける値の存在を示すために、対応する片側カウント配列の値を増大させ、
前記片側カウント配列中の値と、前記出現カウント配列中の対応する値とを比較して、これらの値が一致するときに、当該メモリモジュール自身が、当該片側カウント配列中の値および出現カウント配列中の値に対応する、値のリスト中の格納値についての代表モジュールであると判断する。【００２２】
さらに別の好ましい実施態様においては、前記複数のメモリモジュールの順番が前記メモリモジュールの各々に付与されたモジュール番号によって決められ、
前記代表モジュール判断手段が、
前記メモリモジュール自身が保持する値のリストと同一のサイズのフラグ配列を生成し、当該フラグ配列に初期値を格納し、
前記値のリストを送信した他のメモリモジュールのモジュール番号が、自己のモジュール番号より下位或いは上位の何れか片側にあり、かつ、前記メモリモジュール自身が保持する値のリスト中の格納値が、当該他のメモリモジュールからの値のリスト中に存在するときに、前記メモリモジュール自身が保持する値のリスト中の当該格納値について、他のメモリモジュールにおける値の存在を示すために、対応するフラグ配列をセットし、
前記フラグ配列中のそれぞれの値を参照して、前記フラグ配列の値が初期値であるときに、当該メモリモジュール自身が、当該フラグ配列中の値に対応する、値のリスト中の格納値についての代表モジュールであると判断する。【００２３】
また、本発明の目的は、上述した構成の情報処理システムにおいて、さらに、
前記メモリモジュール自身が保持する値のリスト中の格納値のうち、代表モジュールであることを示す情報が付与されているものを含む送出リスト配列を生成する送出リスト配列生成手段と、
前記他のメモリモジュールのデータ送信手段から送信され、前記自己のデータ受信手段により受信された、当該他のメモリモジュールの送出リスト配列中の格納値に基づいて、前記メモリモジュール自身が保持する値のリスト中の格納値の順位を算出する順位算出手段と、を備えたことを特徴とする情報処理システムによっても達成される。【００２４】
この発明によれば、それぞれのメモリモジュールにおいて、当該メモリモジュール自身が保持する値のリスト中の格納値のそれぞれについて、他のメモリモジュールの値のリストの格納値を考慮した順位を得ることができる。【００２５】
好ましい実施態様においては、前記順位算出手段が、
前記メモリモジュール自身が保持する値リスト中の隣接する格納値の間に、前記他のメモリモジュールの送出リスト中の格納値がいくつ存在するかを判断し、当該判断された存在数に基づいて、前記格納値のそれぞれの順位を算出する。【００２６】
さらに、本発明の目的は、それぞれ、メモリおよび制御装置を有する、複数のメモリモジュールであって、それぞれが予め順序付けられたメモリモジュールと、
メモリモジュール間を接続し、あるメモリモジュールが保持するデータを他のメモリモジュールに伝達するデータ伝送路と、を備え、
各メモリモジュールのメモリが、それぞれ、昇順または降順に重複なく順序付けられた、値のリストを保持するように構成された情報処理システムであって、
前記各メモリモジュールの制御装置が、
他のメモリモジュールに、前記値のリストに含まれる格納値を送信するデータ送信手段と、
他のメモリモジュールから、前記値のリストに含まれる格納値を受信するデータ受信手段と、
前記メモリモジュール自身が保持する値のリストと同一のサイズの出現カウント配列を生成し、当該出現カウント配列に初期値を格納し、前記メモリモジュール自身が保持する値のリスト中の格納値が、他のメモリモジュールからの値のリスト中に存在するときに、前記メモリモジュール自身が保持する値のリスト中の当該格納値について、他のメモリモジュールにおける値の存在を示すために、対応する出現カウント配列の値を増大させることにより、出現カウント配列を完成させる出現カウント配列生成手段と、
前記メモリモジュール自身が保持する値のリストと同一のサイズの片側カウント配列を生成し、当該片側カウント配列に初期値を格納し、前記値のリストを送信した他のメモリモジュールのモジュールの順序が、下位或いは上位の何れか片側にあり、かつ、前記メモリモジュール自身が保持する値のリスト中の格納値が、当該他のメモリモジュールからの値のリスト中に存在するときに、前記メモリモジュール自身が保持する値のリスト中の当該格納値について、他のメモリモジュールにおける値の存在を示すために、対応する片側カウント配列の値を増大させることにより、片側カウント配列を完成させる片側カウント配列生成手段と、
前記他のメモリモジュールに送出するための、前記メモリモジュール自身が保持する値のリストと同一サイズの送出リスト配列を生成し、前記出現カウント配列の値と、前記片側カウント配列の対応する値とを比較して、双方の値が一致する場合に、その値に関する格納値を保持するメモリモジュールとして、当該メモリモジュール自身が最上位或いは最下位であることを示す第１の値を格納するとともに、前記双方の値が一致しない場合に、それ以外の第２の値を格納して、前記送出リスト配列を完成させる送出リスト配列生成手段と、
前記他のメモリモジュールのデータ送信手段により送信され、前記自己のデータ受信手段により受信された、前記他のメモリモジュールの値のリストおよび送出リスト配列に基づいて、前記メモリモジュール自身が保持する値のリスト中の格納値の順位を算出する順位算出手段と、を備えたことを特徴とする情報処理システムによっても達成される。【００２７】
好ましい実施態様においては、前記順位算出手段が、
前記メモリモジュール自身が保持する値リスト中の隣接する格納値の間に存在する、前記他のメモリモジュールの値のリスト中の格納値を特定し、当該格納値に対応する、前記送出リスト配列の値の総和に基づいて、前記隣接する格納値の間に、前記他のメモリモジュールの値のリスト中の格納値がいくつ存在するかを判断し、当該判断された存在数に基づいて、前記格納値のそれぞれの順位を算出する。【００２８】
さらに、本発明の目的は、それぞれ、メモリおよび制御装置を有する、複数のメモリモジュールと、
メモリモジュール間を接続し、あるメモリモジュールが保持するデータを他のメモリモジュールに伝達するデータ伝送路と、を備え、
各メモリモジュールのメモリが、それぞれ、昇順または降順に重複なく順序付けられた、値のリストを保持するように構成された情報処理システムであって、
前記各メモリモジュールの制御装置が、
他のメモリモジュールに、前記値のリストに含まれる格納値を送信するデータ送信手段と、
他のメモリモジュールから、前記値のリストに含まれる格納値を受信するデータ受信手段と、
前記メモリモジュール自身が保持する値のリストと同一のサイズの出現カウント配列を生成し、当該出現カウント配列に初期値を格納し、前記メモリモジュール自身が保持する値のリスト中の格納値が、他のメモリモジュールからの値のリスト中に存在するときに、前記メモリモジュール自身が保持する値のリスト中の当該格納値について、他のメモリモジュールにおける値の存在を示すために、対応する出現カウント配列の値を増大させることにより、出現カウント配列を完成させる出現カウント配列生成手段と、
前記他のメモリモジュールのデータ送信手段により送信され、前記自己のデータ受信手段により受信された、前記他のメモリモジュールの値のリストおよび出現カウント配列に基づいて、前記メモリモジュール自身が保持する値のリスト中の格納値の順位を算出する順位算出手段と、を備えたことを特徴とする情報処理システムによっても達成される。【００２９】
好ましい実施態様においては、前記順位算出手段が、
前記メモリモジュール自身が保持する値リスト中の隣接する格納値の間に存在する、前記他のメモリモジュールの値のリスト中の格納値を特定し、前記存在すると判断された格納値に対応する出現カウント配列の値の逆数を累算することにより、前記他のメモリモジュールの値のリスト中の格納値がいくつ存在するかを判断し、当該判断された存在数に基づいて、前記格納値のそれぞれの順位を算出する。【００３０】
また、本発明の目的は、それぞれ、メモリおよび制御装置を有する、複数のメモリモジュールと、
メモリモジュール間を接続し、あるメモリモジュールが保持するデータを他のメモリモジュールに伝達するデータ伝送路と、を備え、
各メモリモジュールのメモリが、それぞれ、重複なく順序付けられた、値のリストを保持するように構成された情報処理システムであって、
前記各メモリモジュールの制御装置が、
他のメモリモジュールに、前記値のリストに含まれる格納値を送信するデータ送信手段と、
他のメモリモジュールから、前記値のリストに含まれる格納値を受信するデータ受信手段と、
前記他のメモリモジュールのデータ送信手段から送信され、前記自己のデータ受信手段により受信された、当該他のメモリモジュールの値のリスト中の格納値に基づいて、隣接する格納値の間に、前記他のメモリモジュールの値のリスト中の格納値がいくつ存在するかを判断し、当該判断された存在数に基づいて、前記メモリモジュール自身が保持する値のリスト中の格納値の、それぞれについて、他のメモリモジュールの値のリストを考慮した、一定の順序を持ち、必ずしも連続しない整数が割り当てられた配列を生成する整数配列生成手段と、を備えたことを特徴とする情報処理システムにより達成される。【００３１】
この発明によれば、値のリスト中の格納値が、文字列、浮動小数点、あるいは種々の値の組み合わせであった場合にも、それぞれの格納値に、順序付けされた整数を割り当てることが可能となる。【００３２】
また、本発明の目的は、それぞれ、メモリおよび制御装置を有する、複数のメモリモジュールと、
前記メモリモジュール間を接続し、あるメモリモジュールが保持するデータを他のメモリモジュールに伝達するデータ伝送路と、を備え、
各メモリモジュールの前記メモリが、それぞれ、昇順または降順に重複なく順序付けられた、値のリストを保持するよう構成された情報処理システムの、各メモリモジュールの前記制御装置において実行される情報処理方法であって、
当該メモリモジュールの前記制御装置が備えるデータ送信手段が、当該メモリモジュールによって保持された前記値のリストに含まれる格納値を他のメモリモジュールに送信するデータ送信ステップと、
当該メモリモジュールの前記制御装置が備えるデータ受信手段が、前記他のメモリモジュールから、当該他のメモリモジュールによって保持された前記値のリストに含まれる格納値を受信するデータ受信ステップと、
当該メモリモジュールの前記制御装置が備える代表モジュール判断手段が、前記他のメモリモジュールから受信した前記値のリストと、前記他のメモリモジュールに対し決められた順番及び当該メモリモジュールに対し決められた順番とに基づいて、当該メモリモジュールが当該メモリモジュールによって保持された前記値のリスト中のある格納値を保持する一つ以上のメモリモジュールを代表する代表モジュールであるか否かを判断し、当該メモリモジュールが前記代表モジュールである場合に、当該メモリモジュールが前記代表モジュールであることを示す情報を前記ある格納値と関連付けて記憶する代表モジュール判断ステップと、を備え、
前記代表モジュールは、前記複数のメモリモジュールによって保持された前記値のリスト中のそれぞれの格納値について決定されることを特徴とする情報処理方法によっても達成される。
【００３３】
好ましい実施態様においては、前記代表モジュール判断ステップが、
前記順序として前記メモリモジュールの各々に予め付与されたモジュール番号に基づいて、前記メモリモジュール自身が保持する値のリスト中の格納値について、その格納値を保持する一つ以上のメモリモジュールに対し決められた順番のうち、当該メモリモジュール自身に対し決められた順番が所定の関係にある場合に、当該メモリモジュール自身が当該格納値についての代表モジュールであると判断するステップを含む。【００３４】
より好ましい実施態様においては、前記複数のメモリモジュールの順番が前記メモリモジュールの各々に付与されたモジュール番号によって決められ、
前記代表モジュール判断ステップが、
前記メモリモジュール自身が保持する値のリストと同一のサイズの片側カウント配列を生成し、当該片側カウント配列に初期値を格納するステップと、
前記値のリストを送信した他のメモリモジュールのモジュール番号が、自己のモジュール番号より下位或いは上位の何れか片側にあり、かつ、メモリモジュール自身が保持する値のリスト中の格納値が、当該他のメモリモジュールからの値のリスト中に存在するときに、前記メモリモジュール自身が保持する値のリスト中の当該格納値について、他のメモリモジュールにおける値の存在を示すために、対応する片側カウント配列の値を増大させるステップと、
前記片側カウント配列中のそれぞれの値を参照して、前記片側カウント配列の値が初期値であるときに、当該メモリモジュール自身が、当該片側カウント配列中の値に対応する、値のリスト中の格納値についての代表モジュールであると判断するステップと、を含む。【００３５】
別の好ましい実施態様においては、前記複数のメモリモジュールの順番が前記メモリモジュールの各々に付与されたモジュール番号によって決められ、
前記代表モジュール判断ステップが、
前記メモリモジュール自身が保持する値のリストと同一のサイズの出現カウント配列を生成し、当該出現カウント配列に初期値を格納するステップと、
前記メモリモジュール自身が保持する値のリスト中の格納値が、他のメモリモジュールからの値のリスト中に存在するときに、前記メモリモジュール自身が保持する値のリスト中の当該格納値について、他のメモリモジュールにおける値の存在を示すために、対応する出現カウント配列の値を増大させるステップと、
前記メモリモジュール自身が保持する値のリストと同一のサイズの片側カウント配列を生成し、当該片側カウント配列に初期値を格納するステップと、
前記値のリストを送信した他のメモリモジュールのモジュール番号が、自己のモジュール番号より下位或いは上位の何れか片側にあり、かつ、前記メモリモジュール自身が保持する値のリスト中の格納値が、当該他のメモリモジュールからの値のリスト中に存在するときに、前記メモリモジュール自身が保持する値のリスト中の当該格納値について、他のメモリモジュールにおける値の存在を示すために、対応する片側カウント配列の値を増大させるステップと、
前記片側カウント配列中の値と、前記出現カウント配列中の対応する値とを比較して、これらの値が一致するときに、当該メモリモジュール自身が、当該片側カウント配列中の値および出現カウント配列中の値に対応する、値のリスト中の格納値についての代表モジュールであると判断するステップと、を含む。【００３６】
さらに別の好ましい実施態様においては、前記複数のメモリモジュールの順番が前記メモリモジュールの各々に付与されたモジュール番号によって決められ、
前記代表モジュール判断ステップが、
前記メモリモジュール自身が保持する値のリストと同一のサイズのフラグ配列を生成し、当該フラグ配列に初期値を格納するステップと、
前記値のリストを送信した他のメモリモジュールのモジュール番号が、自己のモジュール番号より下位或いは上位の何れか片側にあり、かつ、前記メモリモジュール自身が保持する値のリスト中の格納値が、当該他のメモリモジュールからの値のリスト中に存在するときに、前記メモリモジュール自身が保持する値のリスト中の当該格納値について、他のメモリモジュールにおける値の存在を示すために、対応するフラグ配列をセットするステップと、
前記フラグ配列中のそれぞれの値を参照して、前記フラグ配列の値が初期値であるときに、当該メモリモジュール自身が、当該フラグ配列中の値に対応する、値のリスト中の格納値についての代表モジュールであると判断するステップと、を含む。【００３７】
また、本発明の目的は、上記情報処理方法において、さらに、
当該メモリモジュールの前記制御装置が備える送出リスト配列生成手段が、当該メモリモジュールが保持する前記値のリスト中の前記格納値のうち、前記代表モジュールであることを示す情報が付与されているものを含む送出リスト配列を生成する送出リスト配列生成ステップと、
当該メモリモジュールの前記制御装置が備える順位算出手段が、前記他のメモリモジュールのデータ送信ステップにおいて送信され、当該メモリモジュールのデータ受信ステップにおいて受信された、前記他のメモリモジュールの前記送出リスト配列中の格納値に基づいて、当該メモリモジュールが保持する前記値のリスト中の前記格納値の順位を算出する順位算出ステップと、を備えたことを特徴とする情報処理方法によっても達成される。
【００３８】
好ましい実施態様において、前記順位算出ステップが、
前記メモリモジュール自身が保持する値リスト中の隣接する格納値の間に、前記他のメモリモジュールの送出リスト中の格納値がいくつ存在するかを判断し、当該判断された存在数に基づいて、前記格納値のそれぞれの順位を算出するステップを含む。【００３９】
また、本発明の目的は、メモリおよび制御装置を有し、予め順序付けられた複数のメモリモジュールと、
前記メモリモジュール間を接続し、あるメモリモジュールが保持するデータを他のメモリモジュールに伝達するデータ伝送路と、を備え、
各メモリモジュールの前記メモリが、それぞれ、昇順または降順に重複なく順序付けられた、値のリストを保持するように構成された情報処理システムの、各メモリモジュールの前記制御装置において実行される情報処理方法であって、
当該メモリモジュールの前記制御装置が備えるデータ送信手段が、当該メモリモジュールによって保持された前記値のリストに含まれる格納値を他のメモリモジュールに送信するデータ送信ステップと、
当該メモリモジュールの前記制御装置が備えるデータ受信手段が、前記他のメモリモジュールから、当該他のメモリモジュールによって保持された前記値のリストに含まれる前記格納値を受信するデータ受信ステップと、
当該メモリモジュールの前記制御装置が備える出現カウント配列生成手段が、当該メモリモジュールが保持する前記値のリストと同一のサイズの出現カウント配列を生成し、前記出現カウント配列に初期値を格納し、当該メモリモジュールが保持する前記値のリスト中のある格納値が、前記他のメモリモジュールからの前記値のリスト中に存在するときに、当該メモリモジュールが保持する前記値のリスト中の前記ある格納値が当該他のメモリモジュールに存在していることを示すために、前記ある格納値に対応する前記出現カウント配列中の値を増大させることにより、前記出現カウント配列を完成させる出現カウント配列生成ステップと、
当該メモリモジュールの前記制御装置が備える前記片側カウント配列生成手段が、当該メモリモジュールが保持する前記値のリストと同一のサイズの片側カウント配列を生成し、前記片側カウント配列に初期値を格納し、前記値のリストを送信した前記他のメモリモジュールのモジュールの順番が、下位或いは上位の何れか片側にあり、かつ、当該メモリモジュールが保持する前記値のリスト中のある格納値が、前記他のメモリモジュールからの前記値のリスト中に存在するときに、当該メモリモジュールが保持する前記値のリスト中の当該前記ある格納値が前記他のメモリモジュールに存在していることを示すために、前記ある格納値に対応する前記片側カウント配列中の値を増大させることにより、前記片側カウント配列を完成させる片側カウント配列生成ステップと、
当該メモリモジュールの前記制御装置が備える送出リスト配列生成手段が、前記他のメモリモジュールに送出するための、当該メモリモジュールが保持する前記値のリストと同一サイズの送出リスト配列を生成し、前記値リスト中の前記格納値に対応する前記出現カウント配列の値と前記片側カウント配列の対応する値とを比較して、双方の値が一致する場合に、当該メモリモジュールが最上位或いは最下位のメモリモジュールであることを示す第１の値を格納し、前記双方の値が一致しない場合に、それ以外の第２の値を格納して、前記送出リスト配列を完成させる送出リスト配列生成ステップと、
当該メモリモジュールの前記制御装置が備える順位算出手段が、前記他のメモリモジュールのデータ送信ステップにおいて送信され、当該メモリモジュールのデータ受信ステップにおいて受信された、前記他のメモリモジュールの前記値のリストおよび前記送出リスト配列に基づいて、当該メモリモジュールが保持する前記値のリスト中の格納値の順位を算出する順位算出ステップと、を備えたことを特徴とする情報処理方法によっても達成される。
【００４０】
好ましい実施態様においては、前記順位算出ステップが、
前記メモリモジュール自身が保持する値リスト中の隣接する格納値の間に存在する、前記他のメモリモジュールの値のリスト中の格納値を特定し、当該格納値に対応する、前記送出リスト配列の値の総和に基づいて、前記隣接する格納値の間に、前記他のメモリモジュールの値のリスト中の格納値がいくつ存在するかを判断し、当該判断された存在数に基づいて、前記格納値のそれぞれの順位を算出するステップを含む。【００４１】
また、本発明の目的は、それぞれ、メモリおよび制御装置を有する、複数のメモリモジュールと、
前記メモリモジュール間を接続し、あるメモリモジュールが保持するデータを他のメモリモジュールに伝達するデータ伝送路と、を備え、
各メモリモジュールの前記メモリが、それぞれ、昇順または降順に重複なく順序付けられた、値のリストを保持するように構成された情報処理システムの、各メモリモジュールの前記制御装置において実行される情報処理方法であって、
当該メモリモジュールの前記制御装置が備えるデータ送信手段が、当該メモリモジュールによって保持された前記値のリストに含まれる格納値を他のメモリモジュールに送信するデータ送信ステップと、
当該メモリモジュールの前記制御装置が備えるデータ受信手段が、前記他のメモリモジュールから、前記他のメモリモジュールによって保持された前記値のリストに含まれる前記格納値を受信するデータ受信ステップと、
当該メモリモジュールの前記制御装置が備える出現カウント配列生成手段が、当該メモリモジュールが保持する前記値のリストと同一のサイズの出現カウント配列を生成し、前記出現カウント配列に初期値を格納し、当該メモリモジュールが保持する前記値のリスト中のある格納値が、前記他のメモリモジュールからの前記値のリスト中に存在するときに、当該メモリモジュールが保持する前記値のリスト中の前記格納値に対応する前記出現カウント配列の値を増大させることにより、前記出現カウント配列を完成させる出現カウント配列生成ステップと、
当該メモリモジュールの前記制御装置が備える順位算出手段が、(i)前記他のメモリモジュールのデータ送信ステップにおいて送信され、当該メモリモジュールのデータ受信ステップにおいて受信された、前記他のメモリモジュールの前記値のリストおよび前記出現カウント配列を入力し、(ii)当該メモリモジュールが保持する前記値のリスト中の隣接する格納値の間に存在する、前記他のメモリモジュールの前記値のリスト中の前記格納値に対応する前記他のメモリモジュールの前記出現カウント配列の値の逆数を累算し、(iii)前記累算された逆数を累計数化し、(iv)前記累計数化された逆数に当該メモリモジュールが保持する前記値のリスト中の前記格納値の初期順位を加算することにより、当該メモリモジュールが保持する前記値のリスト中の前記格納値の順位を算出する順位算出ステップと、を備えたことを特徴とする情報処理方法によっても達成される。
【００４３】
また、本発明の目的は、それぞれ、メモリおよび制御装置を有する、複数のメモリモジュールと、
メモリモジュール間を接続し、あるメモリモジュールが保持するデータを他のメモリモジュールに伝達するデータ伝送路と、を備え、
各メモリモジュールのメモリが、それぞれ、重複なく順序付けられた、値のリストを保持するように構成された情報処理システムにおいて、前記各メモリモジュールの制御装置にて実行される情報処理方法であって、
他のメモリモジュールに、前記値のリストに含まれる格納値を送信するデータ送信ステップと、
他のメモリモジュールから、前記値のリストに含まれる格納値を受信するデータ受信ステップと、
前記他のメモリモジュールのデータ送信ステップにおいて送信され、前記自己のデータ受信ステップにおいて受信された、当該他のメモリモジュールの値のリスト中の格納値に基づいて、隣接する格納値の間に、前記他のメモリモジュールの値のリスト中の格納値がいくつ存在するかを判断し、当該判断された存在数に基づいて、前記メモリモジュール自身が保持する値のリスト中の格納値の、それぞれについて、他のメモリモジュールの値のリストを考慮した、一定の順序を持ち、必ずしも連続しない整数が割り当てられた配列を生成する整数配列生成ステップと、を備えたことを特徴とする情報処理方法によっても達成される。
【発明の効果】
【００４４】
本発明によれば、分散メモリ型において、単一命令により種々のメモリに記憶された配列中の要素を入出力し、処理と通信を統合することで著しく高速な並列処理を実現する情報処理システムおよび情報処理方法において、重複の無い昇順に並んだリストを、高速に、一意的に順序付けする手法を提供することが可能となる。また、本発明によれば、重複の無い昇順に並んだリストを生成する手法を提供することが可能となる。
【発明を実施するための最良の形態】
【００４５】
［ハードウェア構成］
以下、添付図面を参照して、本発明の実施の形態につき説明を加える。図１は、本発明の実施の形態にかかる情報処理システムの概略を示すブロックダイヤグラムである。図１に示すように、この実施の形態においては、情報処理システムは、複数のプロセッサ付きメモリモジュール（以下、「ＰＭＭ」と称する）１２−０、１２−１、１２−２、・・・を備え、これらがバスやネットワークなどの伝送路により接続されている。たとえば、図１では、ＰＭＭ１２−０は、少なくとも、他のＰＭＭ１２−１〜３のそれぞれと伝送路で接続されている。他のＰＭＭも同様に、自分以外の３つのＰＭＭのそれぞれと伝送路で接続されている。【００４６】
図２は、ＰＭＭ１２の構造の一例を示す図である。図２に示すように、ＰＭＭ１２は、命令にしたがったメモリのアクセス、演算の実行などを制御する制御回路２０と、バスインタフェース（Ｉ／Ｆ）２２と、メモリ２４とを備えている。【００４７】
メモリ２４は、複数のバンクＢＡＮＫ０、１、・・・、ｎ（符号２６−０、・・・、ｎ）を有し、それぞれに、後述する所定の配列を記憶できるようになっている。【００４８】
また、制御回路２０は、外部の他のコンピュータ等とのデータ授受が可能である。また、他のコンピュータが、バスアービトレーションにより、メモリの所望のバンクにアクセスできるようにしても良い。【００４９】
図１において、ＰＭＭで伝送路からのデータを受信する処理を実行する構成要素（受信処理部）を三角形で示す。この受信処理部は、図２のバスインタフェース２２に相当する。各ＰＭＭにおいて処理の並列性を最も高めるのであれば、受信処理部の数は（ＰＭＭの数―１）であるのが望ましい。また、図１において図示しないが、ＰＭＭは、データを、伝送路を介して他のＰＭＭＮに送信する送信処理部も備える。この送信処理部も、図２のバスインタフェースに相当する。図１に示す例では、４つのＰＭＭが示されているため、ＰＭＭの受信処理部が３つあれば良いが、以下に述べるように、さらに他のＰＭＭからのデータを受信できるように、４つの受信処理部が設けられている。【００５０】
システムが、多数（たとえば、１２８個、２５６個など）のＰＭＭを備える場合に、それぞれのＰＭＭが、（ＰＭＭの数−１）だけの受信処理部を持つことは現実的ではない。そこで、図４７および図４８に示すように、たとえば、４つのＰＭＭを１つのグループと考える（たとえば、符号４７００−１、４７００−２、４７００−ｎ参照）。グループの間にもデータ通信のための伝送路（たとえば符号４７１０参照）が設けられる。【００５１】
同じグループのＰＭＭ間では、ＰＭＭの３つの受信処理部のそれぞれが他のＰＭＭからのデータを受信できることで、完全な並列性を確保し、かつ、ＰＭＭの残りの１つの受信処理部を、他のグループからのデータを受信できるような構成とする。【００５２】
無論、図１、４７、４８に示す接続は一例にすぎず、ＰＭＭ間の接続は他の態様（たとえば、リング状、バス状）を採用しても良い。ただし、同時にデータを受信できる他のＰＭＭの数が大きくなるのに伴って並列性が高まり、より高速な処理が実現できる。
［データの記憶構造］
図３は、表形式データの一例を示す図である。このように、表形式のデータでは、レコードごとに種々の項目（この例では、「性別」、「年齢」、「身長」および「体重」）に値が与えられている。本実施の形態にかかる情報処理装置では、これら表形式データを、原理的には、図４に示すようなデータ形式に基づいて保持する。【００５３】
図４に示すように、順序集合の配列OrdSetには、順序番号ごとにレコード番号が値として配置される。この例では、すべてのレコードが表されるため、順序番号とレコード番号とは一致する。【００５４】
たとえば、性別に関しては、実際の項目値である「男」或いは「女」という値が、所定の順序にてソートされた値リストVLと、順序集合の配列OrdSet中の要素（たとえば、レコード番号）のそれぞれに対応して、当該レコード番号が指し示す値リスト中の番号が格納された、値リストへのポインタ配列VNoとにより、表形式データを表す。この値リストVLおよびポインタ配列VNoの組み合わせを「情報ブロック」とも称する（性別に関する情報ブロックは符号４０１に対応する）。【００５５】
順序集合の配列OrdSet中の要素（レコード番号）が指し示す位置にある、ポインタ配列VNo中の値を特定し、さらに、その値が指し示す位置にある値リストVL中の項目値を取り出すことにより、レコード番号に対応する項目値を取得することができる。他の項目の情報ブロックについても同様の構造である。【００５６】
単一のコンピュータが、単一のメモリ（物理的には複数であっても良いが、単一のアドレス空間に配置されアクセスされるという意味で単一のメモリ）であれば、当該メモリに、順序集合の配列OrdSet、各情報ブロックを構成する値リストVLおよびポインタ配列VNoとを記憶しておけばよい。しかしながら、大量のレコードを保持するためには、その大きさにともなってメモリ容量も大きくなるため、これらを分散配置できるのが望ましい。また、処理の並列化の観点からも、分散配置された情報を分掌把握できるのが望ましい。
［重複の無い値のリストの取得：代表モジュールの選択処理］
複数のＰＭＭにデータを分散配置し、かつ、これらを利用可能にするためには、重複の無い値のリストを取得できること、および、各ＰＭＭにおいて、値のリストに格納されたそれぞれの格納値の、全てのＰＭＭを考慮した順位が把握されていることが必要である。まず、重複の無い値のリストの取得について説明する。なお、「値のリスト」とは、１以上の格納値を含むリストをいう。たとえば、値リストVLも、「値のリスト」になるし、ポインタ配列VNoも、「値のリスト」となることができる。【００５７】
図５の例では、４つのＰＭＭ（ＰＭＭ−０〜ＰＭＭ−３）に、所定のレコード数の表形式データを収容する場合を考えた。この例では、レコード番号０〜２に関する一連のデータ、レコード番号３、４に関する一連のデータ、レコード番号５〜７に関する一連のデータ、および、レコード番号８、９に関する一連のデータを、それぞれ記憶することとした。各ＰＭＭにおいても、上記表形式データの部分は、情報ブロックの形式で記憶される。【００５８】
本実施の形態においては、各ＰＭＭにおいては、それぞれの項目について、値リストへのポインタ配列VNoおよび値リストVLが設けられる。図６および図７は、図５に示す表形式データを、ＰＭＭ−０〜３のそれぞれにおいて分掌するときの配列の例を示す図である。【００５９】
図６、７に示すように、各ＰＭＭには、項目ごとの情報ブロックの部分集合などが収容される。たとえば、図６において、項目「性別」の情報ブロック６０１では、もとのポインタ配列VNo（図４参照）の部分集合VNo（これも「ポインタ配列」と称する。）と、もとの値リストVL（図４参照）の部分集合VL（これも「値リスト」と称する。）と、が含まれる。【００６０】
ポインタ配列VNoの要素の数は、ＰＭＭが分掌するレコードの数に一致する。これに対して、値リストVLは、ポインタ配列VNoが示す値のみが抽出される。項目「性別」については、ポインタ配列VNoの値が、値リストVL全ての要素（項目値）を指し示しているため、値リストVLと、もとの値リストVLとは一致する。その一方、項目「年齢」、「身長」および「体重」については、もとの値リストVLから、ポインタ配列中の要素が指し示す値のみが、もとの値リストVLの部分集合として取り出されることが理解できるであろう。【００６１】
さらに、分掌される情報ブロックにおいては、各ＰＭＭにおいて、ポインタ配列VNoの要素により適切に値リストVLの要素（項目値）が指し示されるように、つまり、ＰＭＭ内のローカルな処理（ポインタ値の指定や項目値の指定）においても整合性が保たれるように、その要素は、対応するもとのポインタ配列VNoの要素から変換されている。【００６２】
図６、７に示す例において、ＰＭＭ−１は、項目「年齢」の値リストVLを参照すると、値「１６」を有し、また、ＰＭＭ−２も、項目「年齢」の値リストVLを参照すると、値「１６」を有する。他の項目についても、同様に、複数のＰＭＭが、同じ値を有することは、当然生じ得る（たとえば、ＰＭＭ−０において、項目「体重」の値リストVL中、値「５５」を有する一方、ＰＭＭ−２においても、項目「体重」の値リストVL中、値「５５」を有している）。【００６３】
それぞれのＰＭＭは、他のＰＭＭが、値のリスト中、どういった値を有しているかを把握していない。また、上述したように、複数のＰＭＭにおいて同じ値を有している場合にも、どのＰＭＭが、自己の値のリストに格納された値と同一の値を有しているかを知ることができない。したがって、図６、７に示すような状態では、何れのＰＭＭにおいても、或いは、伝送路を介して接続された他のＰＭＭにおいても、全体の値リストを取得することが困難であるという問題点があった。そこで、値のリストをそれぞれ分掌したＰＭＭにおいて、より少ないデータ送受信により、重複した値の無い値のリストを得られるような状態にしておくのが望ましい。たとえば、図６、７において、項目「年齢」を考えると、それぞれのＰＭＭにおいて保持されている値リストVLの値に基づいて、重複の無い値リストＶＬ（図４の項目「年齢」に関する値リストVLに相当する）を得られるような状態にすることである。【００６４】
上述したように、重複の無い値のリストを取得するために、値のリスト中のそれぞれの値について、どのＰＭＭが保持するものが、その値を代表するか、つまり、その値を保持する代表モジュールは何であるかを示す情報を生成し、代表する値を保持するＰＭＭ（代表モジュール）が、その情報を保持しておけば良い。図６、７の例において、項目「年齢」の値「１８」については、ＰＭＭ−０が代表値を保持するか、或いは、ＰＭＭ−３が代表値を保持するかを、ＰＭＭ間のデータ交換により決定し、たとえば、ＰＭＭ−０が代表モジュールと決定した場合には、ＰＭＭ−０が、値「１８」については、その代表値を保持していることを示す情報（たとえば、値リストＶＬの値「１８」に関連付けられたフラグ）を保持すれば良い。【００６５】
代表モジュールの選択処理については、以下に述べる値の順位を把握するための処理の処理フローと一部共通する。したがって、値の順位の把握のための処理を含むコンパイル処理の説明の後、再度、代表モジュールの選択処理について説明する。
[コンパイル処理]
以下、複数のＰＭＭにデータを分散配置し、かつ、これらを利用可能にするための処理（コンパイル処理）について考える。【００６６】
図６および図７に示すように、複数のＰＭＭ（たとえば、ＰＭＭ−０〜ＰＭＭ−３）において、値リストVLが分掌された場合を考える。分掌される情報ブロックにおいては、値リストVLにおいて、当該分掌された情報ブロックにおいて必要な要素（項目値）のみを保持している。よって、ポインタ配列VNoおよび値リストVLによって、ローカルな処理の整合性は保たれる。しかしながら、ＰＭＭ間での処理の整合性を保つため、各ＰＭＭにて分掌される値リストVLの要素（項目値）の、値リスト全体における位置づけ、つまり、各項目値が、値リスト全体において、所定の順序のもと何番目であるか、つまり項目値の順位を把握する必要がある。そこで、本実施の形態では、分掌される各情報ブロックにおいて、グローバル値番号配列GVNoを配置し、項目値に対応する値の順位を示す番号を収容できるようにしている。このような項目値の順位を算出するための処理について、以下に説明する。【００６７】
なお、本実施の形態において、各ＰＭＭには、上記情報ブロックの部分集合を分掌するためのオフセット値(OFFSET)が割り当てられる。このオフセット値OFFSETは、ＰＭＭが分掌するレコードに関するもとの順序集合OrdSetにおける先頭の値に対応する。また、各ＰＭＭにおいては、ローカルな処理における整合性をたもつため、新たな順序集合OrdSetが作られる。順序集合OrdSetの要素の数は、ＰＭＭが分掌するレコード数と一致する。その一方、ＰＭＭ間での処理の整合性を保つため、各ＰＭＭが分掌するレコードが、全体の中ではどういった番号（順序集合の要素）を持っているかを把握しておく必要がある。このため、全体における各レコードの番号を収容したグローバル順序集合配列GOrdを設けている。【００６８】
図８は、本実施の形態にかかるコンパイル処理を概略的に示すフローチャートである。図８に示すように、まず、各ＰＭＭに、図６〜図７に示す初期的な情報ブロックが、生成される（ステップ８０１）。これは、たとえば、外部の他のコンピュータから、ＰＭＭに、それぞれが分掌すべき、順序集合OrdSet、各情報ブロックを構成するポインタ配列VNo、値リストVL、および、オフセット値OFFSETが与えられ、これら配列がＰＭＭのメモリなど記憶装置に記憶されることにより実現できる。これら配列は、各ＰＭＭ内のメモリ２４に記憶される。なお、以下の処理において、配列は、メモリ２４などの記憶装置中に生成される。また、処理を高速化する場合には、レジスタに配列を生成しても良い。【００６９】
ステップ８０２以降は、各ＰＭＭにおけるローカルな処理およびＰＭＭ間のパケット通信にかかる処理に移行する。各ＰＭＭの制御回路２０は、オフセット値を参照して、グローバル順序集合配列GOrd中に配置するそれぞれの値を算出し、配列中に値を配置する（ステップ８０２）。図９は、図６〜図７に示す例でのグローバル順序集合配列GOrdへの値の配置を示す図である。ここでは、順序集合の値にオフセット値OFFSETを加えたものを、グローバル順序集合配列GOrdの対応する位置に配置すればよい。ステップ８０２は、各ＰＭＭにおけるローカルな処理で実現できる。【００７０】
次いで、グローバル値番号配列GVNoの値が決定され、その値が、たとえば、メモリ２４上に生成された配列に格納される（ステップ８０３）。このグローバル値番号配列GVNoの値の決定においては、局所（各ＰＭＭ）にそれぞれ保持される、重複の無い値が昇順に並んだリスト（値リストVL）を、全体（各ＰＭＭ間）で一意的に順序付けする必要がある。このグローバル値リストGVNoは、上述した全体で一意的に順序付けした値（順位）が格納されることになる。このような順序付けを高速に実現する方法について、以下により詳細に説明する。
［値のリスト中の値に対する順位付与の第１の手法］
まず、実際に値を、他のＰＭＭとの間で送受信し、受信した他のＰＭＭの値に基づき、自己のＰＭＭが掌握する値の順位を決定する例について説明する。ここでは、説明を容易にするため、各ＰＭＭにおいては、図４９Ｂ〜Ｅに示すような値のリストが分掌されていることを考える。このＰＭＭにおいて分掌される値のリストを、ローカルリスト（ＬＯＣＡＬ  ＬＩＳＴ）とも称する。また、これらローカルリストの値を重複無く、かつ、昇順に並べた配列を図４９Ａに示す。図４９Ａに示すような、全てのＰＭＭ中のローカルリストの値を考慮した、重複の無い値のリストを、トータルリスト（ＴＯＴＡＬ  ＬＩＳＴ）とも称する。つまり、ＰＭＭ−０〜ＰＭＭ−３の４つのＰＭＭのメモリには、それぞれ、以下のような値のリストが記憶されていると考える。たとえば、［ａ，ｂ，ｃ］と表わしている場合には、そのＰＭＭのメモリには、値「ａ」、「ｂ」および「ｃ」が、一定の順序（本例では昇順）で記憶されていることを意味する。【００７１】
ＰＭＭ−０：［１００，３００，５００，６００］
ＰＭＭ−１：［１０，２００，３００，７００］
ＰＭＭ−２：［２００，４００，６００，７００］
ＰＭＭ−３：［１０，１００，３００，５００］
図１０は、各ＰＭＭにおいて、他のＰＭＭにおける値の出現をカウントするために実行される処理の例を示すフローチャートである。図１０に示すように、ＰＭＭは、他のＰＭＭの値の出現をカウントするための、第１のカウント配列群ＣＯＵＮＴ−０〜３をメモリなど記憶装置中に生成して、初期値を格納する（ステップ１００１）。第1のカウント配列のサイズは、自己のＰＭＭが掌握する値の数と同じである。たとえば、ＰＭＭ−０では、４つの格納位置番号（０〜３）を有する配列が生成される。また、配列の格納位置番号は、値のリストの格納位置番号に対応する。たとえば、ＰＭＭ−０に関して、第１のカウント配列の格納位置番号「０」は、値「１００」に関連する。したがって、自己のＰＭＭに関する第１のカウント配列の値として、それぞれ「１」が格納される。また、他のＰＭＭのそれぞれに関する第１のカウント配列の値として、それぞれ「０」が格納される。
ＰＭＭは、自己が掌握する値のリストを、バスを介して他のＰＭＭに送信する（ステップ１００２）。また、ＰＭＭは、他のＰＭＭから送信された値のリストを受信する（ステップ１００３）。たとえば、図１に示すように、システムに４つのＰＭＭが設けられ、それぞれのＰＭＭが、他の３つのＰＭＭからのデータを受信する、３つのデータ受信部を備えていれば、データ受信の処理、および、第１のカウント配列群の生成処理などを、並列的に実現することができる。【００７２】
次いで、ＰＭＭは、他のＰＭＭから受信した値のリストを参照して、自己の値のリストにて保持される値を見出した場合には、当該他のＰＭＭに関する第１のカウント配列中、見出された値に対応する格納位置番号の値をインクリメントする（ステップ１００４）。【００７３】
他のＰＭＭからの値のリストの受信、および、同じ値が存在した場合の、第１のカウント配列のインクリメントは、全てのＰＭＭについて実行される（ステップ１００５参照）。その後、ＰＭＭは、自己のＰＭＭに関する第１のカウント配列、および、他の全てのＰＭＭに関する第１のカウント配列の対応する値を、それぞれ合算して、合算された値を格納した第１のカウント配列を生成する（ステップ１００６）。【００７４】
図１１〜図１４は、それぞれ、ＰＭＭ−０〜ＰＭＭ−３における、第１のカウント配列に関する処理を説明する図である。図１１に示すように、たとえば、ＰＭＭ−０においては、ＰＭＭ−１〜ＰＭＭ−３のそれぞれから値のリスト（図中、「ＲＥＭＯＴＥ
ＬＩＳＴ」と称している）を受信している。また、ＰＭＭ−０（自分自身）に関する第１のカウント配列（図１１において「ＣＯＵＮＴ−０」と称している）の全ての初期値は「１」となっている。その一方、他のＰＭＭに関する第１のカウント配列（図１１において、「ＣＯＵＮＴ−１」〜「ＣＯＵＮＴ−３」と称している）の全ての初期値は「０」となっている。【００７５】
ＰＭＭ−１の値のリストを受信すると、ＰＭＭ−０は、受信した値のリストに含まれる値を参照する。ＰＭＭ−１からの値のリスト中、ＰＭＭ−０の値のリスト（図１１においては、「ＬＯＣＡＬ
ＬＩＳＴ」と称している）にて保持されている値は、「３００」であることがわかる。したがって、ＰＭＭ−１に関する第１のカウント配列（図１１においては、「ＣＯＵＮＴ−１」と称している）中、値のリストにおける値「３００」の格納位置番号（＝１）の値を、インクリメントして「１」とする。【００７６】
ＰＭＭ−２およびＰＭＭ−３についても、同様にして、それぞれに関する第１のカウント配列（図１１において、それぞれ、「ＣＯＵＮＴ−２」および「ＣＯＵＮＴ−３」）中、所定の値がインクリメントされる。その後、図１１における「ＣＯＵＮＴ−０」〜「ＣＯＵＮＴ−３」の対応する値がそれぞれ合算されて、合算された値が格納された第１のカウント配列（図１１においては、単に「ＣＯＵＮＴ」と称している）が得られる。実際には、新たに配列ＣＯＵＮＴのための領域がメモリ中に設けられて、ＣＯＵＮＴ−０〜ＣＯＵＮＴ３の合算値が格納されるようにしても良い。或いは、いずれかの配列（たとえば、ＣＯＮＴ−０）に、他の配列（ＣＯＵＮＴ−１〜３）の値が累算されるように構成しても良い。【００７７】
図１２〜図１４に示すように、ＰＭＭ−１〜ＰＭＭ−３においても、同様に、合算された値が格納された第１のカウント配列（図中、「ＣＯＵＮＴ」と称している）が生成される。【００７８】
図１５Ａは、ＰＭＭ−０〜ＰＭＭ−３のそれぞれが持つ値を、重複なくかつ昇順に並べた仮想的な値のリスト（「ＴＯＴＡＬ＿ＬＩＳＴ」と称する）を示す図である。これらは、ＰＭＭ−０〜ＰＭＭ−３での処理の理解のため図示されており、実際にいずれかのＰＭＭで生成されるものではない。【００７９】
図１５Ｂ〜図１５Ｅは、ＰＭＭ−０〜ＰＭＭ−３のそれぞれにおける図１０に示す処理の実行結果を仮想的に示す配列である。たとえば、図１５Ｂに示すように、ＰＭＭ−０については、仮想的なＬＯＣＡＬ＿ＬＩＳＴの値「１０」、「３００」、「５００」および「６００」に対して、それぞれ、カウント値として「２」、「３」、「３」および「２」が得られていることがわかる。図１５Ａを参照すると、同じ値に対応するカウント値はＰＭＭ間で共通であることがわかる。たとえば、図１５Ｂ、ＣおよびＥの格納位置番号「２」（ローカルリストの値「３００」）をみると、対応するカウント値は全て「３」となる。【００８０】
また、本実施の形態においては、各ＰＭＭにおいて、他のＰＭＭのうち、自己のＰＭＭより下位に位置付けられるものにおける値の出現をカウントするための片側カウント処理が実行される。本実施の形態において、ＰＭＭの上位或いは下位は、ＰＭＭ末尾の番号（たとえば、ＰＭＭ−０における末尾の数字「０」）により表され、当該番号が大きいほうが、ＰＭＭとして上位であると考える。各ＰＭＭにおいては、予め定められた自己のＰＭＭの番号を、メモリなどに記憶して把握しておき、かつ、他のＰＭＭへの値のリストの送信の際に、把握された自己の番号を、値のリストに添付すれば良い。【００８１】
図１６は、各ＰＭＭにおいて実行される片側カウント処理を示すフローチャートである。図１６に示す処理において、他のＰＭＭへの値のリストの送信（ステップ１６０２）および他のＰＭＭからの値のリストの受理（ステップ１６０３）は必須ではなく、図１０のステップ１００３にて受信していた値のリストが利用可能であれば、値のリストの送受信は省略可能である。【００８２】
図１６に示すように、ＰＭＭは、他のＰＭＭに関する値のリスト中の値の出現をカウントするための第２のカウント配列群ＣＯＵＮＴ−０〜３をメモリなど記憶装置中に生成して、初期値を格納する（ステップ１６０１）。図１６に示す処理を、図１０に示す処理と並列的に実行する場合には、図１０にいう第１のカウント配列とは別個に、第２のカウント配列を用意する必要がある。第２のカウント配列のそれぞれに格納すべき初期値は、図１０に関連して説明した第１のカウント配列と同様（自己のＰＭＭについてのカウント配列では、各初期値＝１、他のＰＭＭについてのカウント配列では各初期値＝０）である。【００８３】
次いで、ＰＭＭは、他のＰＭＭからの値のリストについて、それを保有する他のＰＭＭが、自己のＰＭＭより下位に位置づけられているか否かを判断する（ステップ１６０４）。ステップ１６０４でノー(No)と判断された場合には、次のＰＭＭについての処理に移行する（ステップ１６０６参照）。その一方、ステップ１６０４でイエス(Yes)と判断された場合には、図１０のステップ１００４と同様に、ＰＭＭは、他のＰＭＭのリストを参照して、自己の値のリストにて保持される値を見出した場合には、当該他のＰＭＭに関する第２のカウント配列中、見出された値に対応する格納位置番号の値をインクリメントする（ステップ１６０５）。全ての他のＰＭＭについての処理が終了すると（ステップ１６０６でイエス(Yes)）、ＰＭＭは、自己のＰＭＭに関する第２のカウント配列、および、他の全てのＰＭＭに関する第２のカウント配列の対応する値を、それぞれ合算して、合算された値を格納した第２のカウント配列を生成する（ステップ１６０７）。【００８４】
図１７〜図２０は、それぞれ、ＰＭＭ−０〜ＰＭＭ−３における、第２のカウント配列に関する処理を説明する図である。図１７に示すように、ＰＭＭ−０は、ＰＭＭ−１〜ＰＭＭ−３の全てに対して、下位に位置付けられる。したがって、何れのＰＭＭに関しても、ステップ１６０４でノー(No)と判断されるため、第２のカウント配列（図１７では、「ＣＯＵＮＴ−０」〜「ＣＯＵＮＴ−３」）の値は変化せず、したがって、合算後の第２のカウント配列（図１７では「ＣＯＵＮＴ−Ｈ」）は、［１，１，１，１］となる。【００８５】
また、図１８に示すように、ＰＭＭ−１については、ＰＭＭ−０のみが、ＰＭＭ−１よりも下位に位置づけられる。したがって、他のＰＭＭがＰＭＭ−０であるときに、ステップ１６０５の処理が実行され、この処理の結果、ＰＭＭ−０に関する第２のカウント配列（図１８の「ＣＯＵＮＴ−１」）中、値「３００」に対応する（格納位置番号＝２の）カウント値がインクリメントされる。したがって、合算後の第２のカウント配列（図１８のＣＯＵＮＴ−Ｈ）は、［１，１，２，１］となる。【００８６】
図１９に示すように、ＰＭＭ−２については、ＰＭＭ−０およびＰＭＭ−１が、ＰＭＭ−２よりも下位に位置づけられる。したがって、他のＰＭＭが、それぞれ、ＰＭＭ−０、ＰＭＭ−１であるときに、ステップ１６０５の処理が実行される。ＰＭＭ−０に関する第２のカウンタ配列（図１９の「ＣＯＵＮＴ−１」）中、値「６００」に対応する（格納位置番号＝２の）カウント値がインクリメントされる。また、ＰＭＭ−１に関する第２のカウンタ配列（図１９の「ＣＯＵＮＴ−２」）中、値「２００」および「７００」に対応する（格納位置番号＝０，３の）カウント値がインクリメントされる。したがって、合算後の第２のカウント配列（図１９の「ＣＯＵＮＴ−Ｈ」）は、［２，１，２，２］となる。図２０に示すＰＭＭ−３に関する例でも、同様に、それぞれの他のＰＭＭ（ＰＭＭ−０〜ＰＭＭ−２）に関する第２のカウント配列が生成され、最終的な合算後の第２のカウント配列（図２０の「ＣＯＵＮＴ−Ｈ」）は、［２，２，３，２］となる。【００８７】
このようにして、ＰＭＭにおいて、自己の値のリスト中の値の出現数をカウントした第１のカウント配列、および、片側の出現カウントを表す第２のカウント配列が生成されると、ＰＭＭは、それぞれのカウント配列の値を比較する。図２１に示すように、ＰＭＭは、第１のカウント配列の値と、第２のカウント配列の対応する値（つまり同じ格納位置番号の値）とを比較して（ステップ２１０１）、両者が一致するか否かを判断する（ステップ２１０２）。値が一致する場合（ステップ２１０２でイエス(Yes)）には、ＰＭＭは、第１のカウント配列の値を、「Ｎｍ＋１−（第１のカウント配列の対応する値）」として、当該第１のカウンタ配列に、算出された新たな値を格納する（ステップ２１０３）。なお、ここに「Ｎｍ」は、ＰＭＭの数であり、上述した例では「４」となる。【００８８】
その一方、値が一致しない場合（ステップ２１０２でノー(No)）には、当該第１のカウント配列の値を「１」として、第１のカウンタ配列中に「１」を格納する（ステップ２１１０４）。このような処理が、第１のカウント配列の全ての値について実行される（ステップ２１０５、２１０６参照）。【００８９】
図２２Ａは、仮想的な値リストおよび値の順位を格納した仮想的な配列を示す図である。図２２Ｂ〜図２２Ｅは、それぞれ、ＰＭＭ−０〜ＰＭＭ−３における、図２１に示す処理にしたがって、第２のカウント配列の値を考慮した、第１のカウント配列の値の変更を説明する図である。図２２Ｂ〜図２２Ｅでも、仮想的に値の順位が考慮されている。また、図２２Ｆは、カウント値を串刺しで通算した値を示す配列である。【００９０】
ＰＭＭ−０、ＰＭＭ−１については、第１のカウント配列のいずれの値も、第２のカウント配列の対応する値と一致しないため、第１のカウント配列のいずれの値も「１」となる（図２２Ｂ、図２２Ｃ参照）。また、ＰＭＭ−２、ＰＭＭ−３については、第１のカウント配列のいずれの値も、第２のカウント配列の対応する値と一致するため、第１のカウント配列のそれぞれの値は、「４＋１−（第１のカウント配列の対応する値）」となる（図２２Ｄ、図２２Ｅ参照）。【００９１】
ここで、値のリスト中の任意の値について、各ＰＭＭの第１のカウント配列のカウント値を串刺しで通算すると、その総和は「Ｎｍ：ＰＭＭの数」となる。たとえば、仮想的な格納位置番号「０」の値「１０」について、ＰＭＭ−１において、第１のカウント配列の値が「１」であり、ＰＭＭ−３において、第１のカウント配列の値が「３」である。したがって、カウント値を串刺しで通算すると、「１＋３＝４」となり、モジュール数に一致する（図２２Ｆ参照）。他のカウント値についても同様である（図２２Ｆ参照）。【００９２】
その後、各ＰＭＭは、自己が掌握する値のリスト中のそれぞれの値の順位を算出する。図２３に示すように、ＰＭＭは、まず、値のリストと同一サイズの配列Ａｇｇｒ群をメモリなど記憶装置中に生成して、初期値を格納する（ステップ２３０１）。自己のＰＭＭに関する配列Ａｇｇｒ−０については、初期値として、［０，１，２，３］が格納される。その一方、他のＰＭＭに関する配列（上記例では、配列Ａｇｇｒ−１〜Ａｇｇｒ−３）については、初期値として、［０，０，０，０］が格納される。
次いで、ＰＭＭは、自己のＰＭＭの値のリストの値、および、対応する第１のカウント配列の値の組（Ｖａｌｕｅ，Ｃｏｕｎｔ値）を含むリモートリスト（ＲＥＭＯＴＥ  ＬＩＳＴ）を、他のＰＭＭに送信する（ステップ２３０２）。【００９３】
ＰＭＭは、他のＰＭＭからリモートリストを受信すると（ステップ２３０３）、自己のＰＭＭの値のリスト（「ローカルリスト」と称する。）、および、リモートリストのそれぞれのポインタを初期化する（ステップ２３０４）。それぞれのポインタは、初期位置においては、ローカルリスト、および、リモートリストの格納位置番号「０」を指し示す。ＰＭＭは、ローカルリストおよびリモートリストのそれぞれのポインタが示す値（値のリストの値、以下、「カレント値」と称する。）を比較する（ステップ２３０５）。これらカレント値の関係によって、処理が異なる（ステップ２３０６参照）。【００９４】
「ローカルリストのカレント値＜リモートリストのカレント値」である場合には、ＰＭＭは、ローカルリストのポインタを、格納位置番号が「１」だけ大きくなるように移動させる（ステップ２４０１）。「ローカルリストのカレント値＝リモートリストのカレント値」である場合には、ＰＭＭは、ローカルリストのポインタを、格納位置番号が「１」だけ大きくなるように移動させるとともに（ステップ２４０２）、リモートリストのポインタも、格納位置番号が「１」だけ大きくなるように移動させる（ステップ２４０３）。【００９５】
「ローカルリストのカレント値＞リモートリストのカレント値」である場合には、ＰＭＭは、他のＰＭＭについての配列Ａｇｇｒ中、ローカルリストのポインタが示す格納位置の値に、リモートリストのポインタが示す位置のＣｏｕｎｔ値（第１のカウント配列の値）を加算する（ステップ２４０４）。次いで、ＰＭＭは、リモートリストのポインタを、格納位置番号が「１」だけ大きくなるように移動する（ステップ２４０５）。【００９６】
何れかのポインタが、ローカルリストあるいはリモートリストの末尾を越えた位置となった場合には（ステップ２４０６でイエス(Yes)）、ＰＭＭは、全ての他のＰＭＭについて処理が終了したかどうかを判断し（ステップ２４０７）、まだ未処理の他のＰＭＭのリモートリストが存在すれば（ステップ２４０７でノー(No)）、当該他のＰＭＭのリモートリストについて同様に処理を実行する。【００９７】
図２５Ａ〜図２５Ｃおよび図２６Ａ〜図２６Ｃは、ＰＭＭ−０が、他のＰＭＭとしてＰＭＭ−１からのリモートリストを受信した際に実行する処理を詳細に説明する図である。図２５Ａでは、ＰＭＭ−０自身のローカルリスト、および、ＰＭＭ−１からのリモートリストのポインタが初期化され、双方とも格納位置番号が「０」のカレント値が比較されている。図２５Ａに示す状態では、「ローカルリストのカレント値（＝１００）＞リモートリストのカレント値（＝１０）」であるため、当該ＰＭＭ−１に関する配列Ａｇｇｒ−１において、格納位置番号「０」の値として、リモートリストのＣｏｕｎｔ値「１」が格納される（図２４のステップ２４０４）。また、リモートリストのポインタが、格納位置番号が「１」だけ大きくなるように移動される。【００９８】
引き続く図２５Ｂに示す状態では、「ローカルリストのカレント値（＝１００）＜リモートリストのカレント値（＝２００）」であるため、ローカルリストのポインタが、格納位置番号が「１」だけ大きくなるように移動される（図２４のステップ２４０１）。図２５Ｃの状態では、「ローカルリストのカレント値（＝３００）＞リモートリストのカレント値（＝２００）」であるため、当該ＰＭＭ−１に関する配列Ａｇｇｒ−１において、格納位置番号「２」の値として、リモートリストのＣｏｕｎｔ値「１」が格納される（図２４のステップ２４０４）。また、リモートリストのポインタが、格納位置番号が「１」だけ大きくなるように移動される。【００９９】
図２６Ａの状態では、「ローカルリストのカレント値（＝３００）＝リモートリストのカレント値（＝３００）であり、ローカルリストおよびリモートリストのポインタが、格納位置番号が「１」だけ増大するように移動される（図２４のステップ２４０２、２４０３）。図２６Ｂの状態では、「ローカルリストのカレント値（＝５００）＜リモートリストのカレント値（＝７００）」であり、ローカルリストのポインタが、格納位置番号が「１」だけ大きくなるように移動される。さらに、図２６Ｃの例では、「ローカルリストのカレント値（＝６００）＜リモートリストのカレント値（＝７００）」であり、ローカルリストのポインタが、格納位置番号が「１」だけ大きくなるように移動される。これによりローカルリストのポインタが、リストの末尾より後ろを指してしまうため、ＰＭＭ−１からのリモートリストに関する処理が終了する。【０１００】
ＰＭＭ−０においては、ＰＭＭ−１以外の他のＰＭＭ（ＰＭＭ−２、ＰＭＭ−３）からのリモートリストを受信したときにも同様に処理が実行される。【０１０１】
このようにして、図２３および図２４の処理により、自己のＰＭＭに関する配列Ａｇｇｒ（例ではＡｇｇｒ−０）、および、他のＰＭＭに関するそれぞれの配列Ａｇｇｒ（例では、Ａｇｇｒ−１〜Ａｇｇｒ−３）に値が格納された後、これら配列の値に基づいて、値の順位が算出される。図２７に示すように、ＰＭＭは、他のＰＭＭに関する配列Ａｇｇｒ（例では、Ａｇｇｒ−１〜Ａｇｇｒ−３）の値を合算する（ステップ２７０１）。合算された値は、いずれかの配列Ａｇｇｒ中に一時的に格納されても良いし、別途、合算値を格納するための配列を設け、その配列中に合算された値を格納しても良い。次いで、ＰＭＭは、合算された値を、それぞれ、Ｎｍ（つまり、モジュール数）で除する（ステップ２７０２）。その後、ＰＭＭは、除算された値を累計数化する（ステップ２７０３）。累計数化とは、格納位置番号が小さいものから順に、配列中、次の格納位置番号が示す値に、配列の値を加算することを繰り返すことをいう。さらに、ＰＭＭは、累計数化された配列に、自己のＰＭＭに関する配列Ａｇｇｒ（例ではＡｇｇｒ−０）の値を加算する（ステップ２７０４）。自己のＰＭＭに関する配列Ａｇｇｒの値が加算された配列が、自己のＰＭＭの値のリスト中のそれぞれの値の順位を示す配列となる。【０１０２】
図２８Ａ、Ｂ〜図３１Ａ、Ｂは、それぞれ、ＰＭＭ−０〜ＰＭＭ−３において、図２３、２４および図２７の処理が実行されたときの配列等の状態を説明する図である。図２８Ａにおいて、ＰＭＭ−１からのリモートリストの受信結果、当該ＰＭＭ−１に関する配列Ａｇｇｒ（Ａｇｇｒ−１）への値の格納は、図２５Ａ〜図２５Ｃおよび図２６Ａ〜図２６Ｃを参照して詳細に説明したとおりであり、配列Ａｇｇｒ−１の値は［１，１，０，０］となる。同様に、ＰＭＭ−２およびＰＭＭ−３からのそれぞれのリモートリストの受信、および、図２３，２４の処理の結果、ＰＭＭ−２およびＰＭＭ−３に関する配列Ａｇｇｒ（Ａｇｇｒ−２，Ａｇｇｒ−３）も、それぞれ、［０，３，４，０］，［３，０，０，０］となる。Ａｇｇｒ−１〜Ａｇｇｒ−３の値を合算すると、図２８Ｂに示すように、［４，４，４，０］となる。合算値は、Ａｇｇｒ−１〜Ａｇｇｒ−３のいずれかが保持していても良い。次いで、この合算値のそれぞれを、「Ｎｍ＝４」で除すると、除算結果を示す配列は［１，１，１，０］となる。さらに、累計数化することにより、［１，２，３，３］という配列が得られ、さらに、ＰＭＭ−０に関する配列Ａｇｇｒ（Ａｇｇｒ−０）の値を加算することで、最終的な配列［１，３，５，６］を得ることができる。【０１０３】
他のＰＭＭ（ＰＭＭ−１〜ＰＭＭ−３）においても、同様に、図２３、２４および図２７の処理を実行することにより、ぞれぞれ、配列［０，２，３，７］、［２，４，６，７］，［０，１，３，５］が得られる。【０１０４】
図２３および図２４にて実行された処理の意味合いについて説明する。図２３および図２４においては、一定の条件が満たされた場合に、配列Ａｇｇｒ中に、カウント値が格納される（図２４のステップ２４０４参照）。言い換えると、ＰＭＭは、自己の値のリスト（ローカルリスト）中のある値と、その値の一つ前（つまり、格納位置番号が「１」だけ小さい位置）の値との間に、受信した他のＰＭＭからの値のリスト（リモートリスト）の値が、いくつ存在するかをカウントしている。そして、リモートリストのカウント数を、配列Ａｇｇｒ中、自己の値のリスト中のある値に対応する位置に格納している。また、ＰＭＭは、自己の値のリスト（ローカルリスト）中のある値と、他のＰＭＭからの値のリスト（リモートリスト）中の値とが等しい場合には、上記カウントは実行しない。
図３２Ａは、図２２Ａと同様に、仮想的な値リストおよび値の順位を格納した仮想的な配列を示す図である。また、図３２Ｂ〜図３２Ｅは、それぞれ、ＰＭＭ−０〜ＰＭＭ−３において算出された、値のリストのそれぞれの値の順位を示す図である。ＰＭＭ−０〜ＰＭＭ−４の全体で考えると、値のリストは、図３２Ａの「ＴＯＴＡＬ＿ＬＩＳＴ」に示すように、［１０，１００，２００，３００，４００，５００，６００，７００］となり、その順位は、「Ｏｒｄｅｒ
Ｎｏ．」と名付けられた配列に示すようになる。【０１０５】
図３２Ｂは、ＰＭＭ−０が掌握する値のリスト（ＬＯＣＡＬ＿ＬＩＳＴ）［１００，３００，５００，６００］について、それぞれの値の順位が、［１，３，５，６］であることを示している。また、図３２Ｃは、ＰＭＭ−１が掌握する値のリスト（ＬＯＣＡＬ＿ＬＩＳＴ）［１０，２００，３００，７００］について、それぞれの値の順位が［０，２，３，７］であることを示している。図３２Ｄ、図３２Ｅも、それぞれ、ＰＭＭ−２，３が掌握する値およびその順位を示している。図３２Ｂ〜図３２Ｅに示すように、本実施の形態にかかる処理を、それぞれのＰＭＭにおいて実行した結果、適切に、自己の掌握する値の順位が算出されていることが理解できる。【０１０６】
このようにして、それぞれのＰＭＭの値のリスト（ローカルリスト）のそれぞれの値のグローバルな順位を示す配列を得ることができる。すなわち、ＰＭＭ−０において、［１，３，５，６］という配列が、当該ＰＭＭ−０の値リストＶＬ［１００，３００，５００，６００］についてのグローバル値番号配列ＧＶＮｏとなる。同様に、ＰＭＭ−１〜３のそれぞれにおいて、［０，２，３，７］、［２，４，６，７］および［０，１，３，５］という配列が、それぞれの値リストＶＬについてのグローバル値番号配列ＧＶＮｏとなる。【０１０７】
図６および図７に示す例に戻ると、「性別」、「年齢」、「身長」および「体重」の項目のそれぞれについて、上述した処理を実行した結果、図６３および図６４に示すような配列ＧＶＮｏを取得することができる。【０１０８】
以上、詳細に説明したように、値のリスト中の値に対する順位付与の第１の手法を実現するために、情報処理システムの各ＰＭＭは、
他のＰＭＭに、値のリストに含まれる格納値を送信するデータ送信手段と、
他のＰＭＭから、値のリストに含まれる格納値を受信するデータ受信手段と、
ＰＭＭ自身が保持する値のリストと同一のサイズの出現カウント配列を生成し、当該出現カウント配列に初期値を格納し、ＰＭＭ自身が保持する値のリスト中の格納値が、他のＰＭＭからの値のリスト中に存在するときに、ＰＭＭ自身が保持する値のリスト中の当該格納値について、他のＰＭＭにおける値の存在を示すために、対応する出現カウント配列の値を増大させることにより、出現カウント配列を完成させる出現カウント配列生成手段と、
ＰＭＭ自身が保持する値のリストと同一のサイズの片側カウント配列を生成し、当該片側カウント配列に初期値を格納し、値のリストを送信した他のＰＭＭのモジュールの順序が、下位或いは上位の何れか片側にあり、かつ、ＰＭＭ自身が保持する値のリスト中の格納値が、他のＰＭＭからの値のリスト中に存在するときに、ＰＭＭ自身が保持する値のリスト中の当該格納値について、他のＰＭＭにおける値の存在を示すために、対応する片側カウント配列の値を増大させることにより、片側カウント配列を完成させる片側カウント配列生成手段と、
他のＰＭＭに送出するための、ＰＭＭ自身が保持する値のリストと同一サイズの送出リスト配列を生成し、出現カウント配列の値と、片側カウント配列の対応する値とを比較して、双方の値が一致する場合に、その値に関する格納値を保持するＰＭＭとして、当該ＰＭＭ自身が最上位或いは最下位であることを示す第１の値を格納するとともに、双方の値が一致しない場合に、それ以外の第２の値を格納して、送出リスト配列を完成させる送出リスト配列生成手段と、
他のＰＭＭのデータ送信手段により送信され、自己のＰＭＭのデータ受信手段により受信された、他のＰＭＭの値のリストおよび送出リスト配列を含むリモートリストに基づいて、ＰＭＭ自身が保持する値のリスト中の格納値の順位を算出する順位算出手段と、を備える。
［値の整数化］
次に、値のリスト（ローカルリスト）が、整数以外（たとえば、文字列や浮動小数点）である場合の扱いについて説明する。図３３Ａに示すように、順序付けをすべき文字列の値が、ＰＭＭ−０〜ＰＭＭ−３に分散して格納されている場合を考える。ここで、アルファベット順（昇順）で順位を付与すると、図３３Ｂのような結果を得ることができる。【０１０９】
また、図３４Ａに示すように、順序付けをすべき浮動小数点の値が、ＰＭＭ−０〜ＰＭＭ−３に分散して格納さえている場合にも、図３４Ｂのような結果を得ることができる。値は、単一とは限らない。たとえば、図３５Ａに示すように、値が、複数の整数の組（たとえば、（５０，１００））であっても良い。無論、整数の組に限定されず、文字列と整数との組、整数と浮動小数点との組なども考えられる。この場合にも、図３５Ｂに示すように順位を付与することができる。【０１１０】
このように、整数以外の値のそれぞれに、その値の順序を示す値（つまり、順位）を付与するための処理について説明する。順位とは、「０」から開始される連続する整数である。或いは、上記連続する整数に「１」を加えることで、順位を、「１」から開始する整数と考えても良い。【０１１１】
本実施の形態では、上記整数以外の値に、一定の順序をもった、しかしながら、必ずしも連続しない整数を割り当て（第１ステップ）、さらに、一定の順序をもつ、連続しない整数に、図８〜図３２Ｅを参照して説明した処理を施して（第２ステップ）、最終的に、値のリスト（ローカルリスト）の順位を算出している。【０１１２】
図３６は、各ＰＭＭにおいて、上記第１のステップである一定の順序を持つ、連続とは限らない整数を、値に割り当てる際に実行される処理の例を示すフローチャートである。【０１１３】
図３６に示すように、ＰＭＭは、他のＰＭＭの値の出現をカウントするための、第１のカウント配列群ＣＯＵＮＴ−０〜３をメモリなど記憶装置中に生成して、初期値を格納する（ステップ３６０１）。第１のカウント配列のサイズは、自己のＰＭＭが掌握する値の数と同じである。たとえば、ＰＭＭ−０では、４つの格納位置番号（０〜３）を有する配列が生成される。また、配列の格納位置番号は、値のリストの格納位置番号に対応する。たとえば、ＰＭＭ−０に関して、第１のカウント配列の格納位置番号「０」〜「３」の値は、それぞれ、ＰＭＭ−０で保持されている値「ＡＺ」、「ＣＸ」、「ＥＸ」、「ＦＸ」に関連する。自己のＰＭＭ（ＰＭＭ−０）に関する第１のカウント配列の値として、それぞれ「１」が格納される。また、他のＰＭＭのそれぞれに関する第１のカウント配列の値として、それぞれ「０」が格納される。図３７Ａに示すように、ＰＭＭ−０の第１のカウント配列（ＣＯＵＮＴ−０）は［１，１，１，１］、他のＰＭＭに関する第１のカウント配列（ＣＯＵＮＴ−１〜３）は［０，０，０，０］である。【０１１４】
ＰＭＭは、自己が掌握する値のリストを、バスを介して他のＰＭＭに送信する（ステップ３６０２）。また、ＰＭＭは、他のＰＭＭから送信された値のリストを受信する（ステップ３６０３）。【０１１５】
次いで、ＰＭＭは、他のＰＭＭから受信した値のリストを参照して、自己の掌握する値のリストのある値と、その一つ前の（つまり、格納位置番号が１つ小さい）値との間に、他のＰＭＭから受信した値のリストがいくつ存在するかをカウントする（ステップ３６０４）。なお、自己の掌握する値のリスト中のある値と、他のＰＭＭからの値のリスト中の値とが等しい場合には、当該他の値リスト中の等しい値は、上記「間に存在する」値であると考える。【０１１６】
たとえば、図３７Ａの例において、ＰＭＭ−０が、ＰＭＭ−１からの値のリスト（リモートリスト）［ＡＸ，ＢＸ，ＣＸ，ＧＸ］を受信した場合を考える。ここでは、ＰＭＭ−０の値のリスト（ローカルリスト）の格納位置番号「０」の値「ＡＺ」≧「ＡＸ」であるため、「ＡＺ」に関する第１のカウント配列の値（つまり、格納位置番号「０」の値）として「１」が格納される。【０１１７】
次に、ＰＭＭ−０の値のリスト（ローカルリスト）の格納位置番号「１」の値「ＣＸ」について考える。この値「ＣＸ」と、一つ前（つまり格納位置番号「０」）の値「ＡＺ」との間には、ＰＭＭ−１の値のリスト（リモートリスト）中、２つの値「ＢＸ」、「ＣＸ」が存在する。したがって、「ＣＸ」に関する第１のカウント配列の値として、「２」が格納される。【０１１８】
ＰＭＭ−０の値のリスト（ローカルリスト）の格納位置番号「２」の値「ＥＸ」および格納位置番号「３」の値「ＦＸ」については、それぞれ、その値と一つ前の値との間には、ＰＭＭ−１からの値のリスト（リモートリスト）の値が存在しない。したがって、これらの値に関する第１のカウント配列の値は「０」となる。【０１１９】
他のＰＭＭからの値のリストの受信、および、第１のカウント配列への値の格納は、全てのＰＭＭについて実行される（ステップ３６０５参照）。その後、ＰＭＭは、自己のＰＭＭに関する第１のカウント配列、および、他の全てのＰＭＭに関する第１のカウント配列の対応する値を、それぞれ合算して、合算された値を格納した第１のカウント配列を生成する（ステップ３６０６）。【０１２０】
図３７Ａに示す例では、ＰＭＭ−０の自分自身の第１のカウント配列は、［１，１，１，１］、ＰＭＭ−１〜ＰＭＭ−３のそれぞれに関する第１のカウント配列は、［１，２，０，０］、［０，１，１，１］、［２，１，１，０］であり、対応する値を合算すると、合算された第１のカウント配列は、［４，５，３，２］となる。さらに、ＰＭＭは、合算された第１のカウント配列の値を累計して、累計数配列Ａｇｇｒ（ＩＤ）を生成する（ステップ３６０７）。たとえば、図３７Ａに示すように、ＰＭＭ−０は、合算された第１のカウント配列［４，５，３，２］の値を累計する。【０１２１】
ここで、累計することについて、図３７Ａを例として説明する。累計数配列Ａｇｇｒ（ＩＤ）の先頭（格納位置番号「０」）の値は、カウント配列の値「４」と一致する。次いで、Ａｇｇｒ（ＩＤ）の次（格納位置番号「１」）の値として、カウント配列の値「５」と、Ａｇｇｒ（ＩＤ）の一つ前の位置（つまり格納位置番号「０」）の値「４」との加算値「９」を格納する。このように、Ａｇｇｒ（ＩＤ）のある格納位置番号の値として、カウント配列中、同じ格納位置番号の値と、累計数配列Ａｇｇｒ（ＩＤ）中、１つ小さい格納位置番号の値との加算値が格納される。この処理の結果、ＰＭＭ−０における累計数配列Ａｇｇｒ（ＩＤ）は、［４，９，１２，１４］となる。【０１２２】
他のＰＭＭ（ＰＭＭ−１〜ＰＭＭ−３）においても、図３６に示す処理が実行され、それぞれのＰＭＭにおいて、累計数配列Ａｇｇｒ（ＩＤ）が得られる（図３７Ｂ、図３８Ａ、図３８Ｂ参照）。累計数配列Ａｇｇｒ（ＩＤ）は、ＰＭＭのメモリの所定の領域に記憶される。【０１２３】
各ＰＭＭにおいて得られた累計数配列Ａｇｇｒ（ＩＤ）の整数値が、値リスト（ローカルリスト）中、同じ格納位置番号の値に割り当てられた、「一定の順序を持った、しかしながら、必ずしも連続しない整数」となる。したがって、値のリスト（ローカルリスト）中の値が同じであれば、対応する累計数配列Ａｇｇｒ（ＩＤ）の整数値は同一となる。たとえば、図３７Ｂに示すように、ＰＭＭ−１の値のリスト（ローカルリスト）の格納位置番号「０」の値「ＡＸ」に対応する、累計数配列Ａｇｇｒ（ＩＤ）の整数値は「２」である。また、図３８Ｂに示すように、ＰＭＭ−３の値のリスト（ローカルリスト）の格納位置番号「０」の値「ＡＸ」に対応する、累計数配列Ａｇｇｒ（ＩＤ）の整数値は「２」である。【０１２４】
図３９Ａは、仮想的に、ＰＭＭ−０〜ＰＭＭ−３の値を、アルファベット順に並べ、かつ、それぞれの値について、図３６に示す処理で得られた累計数配列の整数値を、仮想的に対応付けて並べた図である。図３９Ａに示すように、累計数配列の整数値は、連続ではないが、値の順にしたがって昇順となっている。つまり、「一定の順序を持った、しかしながら、必ずしも連続しない整数」となっていることが理解できるであろう。また、図３９Ｂ〜図３９Ｅは、それぞれ、各ＰＭＭで図３６の処理の結果得られた、累計数配列Ａｇｇｒ（ＩＤ）の整数値を、値のリスト（ローカルリスト）の値と関連付けて、仮想的に配置した図である。これらから、ＰＭＭが異なっていても、値のリスト（ローカルリスト）の値が同一であれば、対応する累計数配列Ａｇｇｒ（ＩＤ）の整数値が同一であることが理解できるであろう。本実施の形態では、各ＰＭＭが、他のＰＭＭから値のリスト（リモートリスト）を受け取ることのみにより、上述するように、自己の値のリスト（ローカルリスト）の順序を維持した整数値であって、他のＰＭＭと共通化された整数値を得ることができる。累計数配列Ａｇｇｒ（ＩＤ）と値のリスト（ローカルリスト）との間では、値が１対１に対応しているため、累計数配列Ａｇｇｒ（ＩＤ）を変換配列として利用することができる。【０１２５】
このように、本実施の形態においては、整数以外（上記例では、アルファベット）の値を、その順序を維持した、整数と対応付けることができる。さらに、各ＰＭＭにおいて、値のリスト（ローカルリスト）のそれぞれの値と対応付けられた整数値を持つような変換配列を、取得することができる。したがって、この変換配列に対して、先に、［値のリスト中の値に対する順位付与］の項にて説明した手法を適用することで、各ＰＭＭにおいて、自己の値のリストのそれぞれの値の順位を算出することが可能となる。【０１２６】
値のリスト（ローカルリスト）の値が、アルファベット以外、たとえば、浮動小数点や複数の値の組である場合については説明を省略するが、各ＰＭＭにおいて、図３６の処理を実行することで、その順序が維持された整数値を有する変換配列が取得できることが理解できるであろう。【０１２７】
以上、詳細に説明したように、値の整数化を実現するために、情報処理システムの各ＰＭＭは、
他のＰＭＭに、値のリストに含まれる格納値を送信するデータ送信手段と、
他のＰＭＭから、値のリストに含まれる格納値を受信するデータ受信手段と、
他のＰＭＭのデータ送信手段から送信され、自己のデータ受信手段により受信された、他のＰＭＭの値のリスト中の格納値に基づいて、隣接する格納値の間に、他のＰＭＭの値のリスト中の格納値がいくつ存在するかを判断し、判断された存在数に基づいて、ＰＭＭ自身が保持する値のリスト中の格納値の、それぞれについて、他のＰＭＭの値のリストを考慮した、一定の順序を持ち、必ずしも連続しない整数が割り当てられた配列を生成する整数配列生成手段と、を備える。
［値のリスト中の値に対する順位付与の第２の手法］
上述した「順位付与の処理においては、出現カウント配列の生成処理（図１０参照）の後、片側カウント配列の生成処理（図１６参照）を実行し、その後、カウント配列の値の比較により、カウント配列の値に重みを付与している（図２１参照）。【０１２８】
以下、片側カウント処理の代わりに、以下に説明するような、フラグがセットされた配列を利用することで、上述したような出現カウント配列の生成、片側カウント配列の生成、カウント配列の値の比較を省略することが可能となる。【０１２９】
図４０は、検出フラグ配列および論理和配列の生成処理を示すフローチャートである。図４０に示すように、ＰＭＭは、他のＰＭＭに関する値のリスト中の値の出現を検知するための検出フラグ配列群をメモリなど記憶装置中に生成して、初期値を格納する（ステップ４００１）。ステップ４００１では、他のＰＭＭの数だけフラグ配列を生成すれば足りる。検出フラグ配列の初期値は、初期的にはフラグがセットされていない状態を示すため「０」となる。【０１３０】
ＰＭＭは、他のＰＭＭへ値のリストを送信し（ステップ４００２）、また、他のＰＭＭから値のリストを受信する（ステップ４００３）。【０１３１】
次いで、ＰＭＭは、他のＰＭＭからの値のリストについて、それを保有する他のＰＭＭが、自己のＰＭＭより下位に位置づけられているか否かを判断する（ステップ４００４）。ステップ４００４でノー(No)と判断された場合には、次のＰＭＭについての処理に移行する（ステップ４００６参照）。その一方、ステップ４００４でイエス(Yes)と判断された場合に、ＰＭＭは、他のＰＭＭのリストを参照して、自己の値のリストにて保持される値を見出した場合には、当該他のＰＭＭに関する検出フラグ配列中、見出された値に対応する格納位置番号にフラグをセット、つまり、その位置の値に「１」を格納する（ステップ４００５）。全ての他のＰＭＭについての処理が終了すると（ステップ４００６でイエス(Yes)）、ＰＭＭは、他の全てのＰＭＭに関する検出フラグ配列の対応する値の論理和をとる（ステップ４００７）。つまり、検出フラグ配列中、同じ格納位置番号の値の何れかが「１」であれば、演算結果を示す論理和配列中、対応する値を「１」とする。この論理和配列も、メモリなど記憶装置中に生成すれば良い。【０１３２】
図４１Ａ、Ｂおよび図４２Ａ、Ｂは、ＰＭＭ−０〜ＰＭＭ−３における、検出フラグ配列に関する処理を説明する図である。図４１Ａに示すように、ＰＭＭ−０は、ＰＭＭ−１〜ＰＭＭ−３の全てに対して、下位に位置付けられる。したがって、何れのＰＭＭに関しても、ステップ４００４でノー(No)と判断されるため、検出フラグ配列の値は変化せず、したがって、合算後の論理和配列は、［０，０，０，０］となる。【０１３３】
また、図４１Ｂに示すように、ＰＭＭ−１については、ＰＭＭ−０のみが、ＰＭＭ−１よりも下位に位置づけられる。したがって、他のＰＭＭがＰＭＭ−０であるときに、ステップ４００５の処理が実行され、この処理の結果、ＰＭＭ−０に関する検出フラグ配列中、値「３００」に対応する（格納位置番号＝２の）フラグが「１」にセットされる。したがって、論理和が施された論理和配列は、［０，０，１，０］となる。【０１３４】
図４２Ａに示すように、ＰＭＭ−２については、ＰＭＭ−０およびＰＭＭ−１が、ＰＭＭ−２よりも下位に位置づけられる。したがって、他のＰＭＭが、それぞれ、ＰＭＭ−０、ＰＭＭ−１であるときに、ステップ４００５の処理が実行される。ＰＭＭ−０に関する検出フラグ配列中、値「６００」に対応する（格納位置番号＝２の）フラグがセットされる。また、ＰＭＭ−１に関する検出フラグ配列中、値「２００」および「７００」に対応する（格納位置番号＝０，３の）フラグがセットされる。したがって、論理和配列は、［１，０，１，１］となる。さらに、図４２Ｂに示すＰＭＭ−３に関する例でも、同様に、それぞれの他のＰＭＭ（ＰＭＭ−０〜ＰＭＭ−２）に関する検出フラグ配列が生成され、論理和が施された論理和配列は、［１，１，１，１］となる。【０１３５】
以下の処理で、ＰＭＭが送信する値のリスト（リモートリスト）は、ＰＭＭが掌握する値のリスト（ローカルリスト）の値のうち、論理和配列中、対応する位置の値が「０」であるような値から構成される。図４３Ａは、ＰＭＭ−０〜ＰＭＭ−３のそれぞれが持つ値を、重複なくかつ昇順に並べた仮想的な値のリストおよび当該値のリストのそれぞれの値の順序を格納した仮想的な配列を示す図である。図４３Ｂ〜図４３Ｅに示すように、それぞれのＰＭＭについて、値のリスト（ローカルリスト）の値中、論理和配列の値が「０」であるような値のみが、送出する値のリスト（図４３Ｂ〜図４３Ｅでは「送出リスト」と表示される）に格納される。【０１３６】
図４４は、本発明の他の実施の形態にかかるＰＭＭにおいて実行される、値の順位を決定する処理を示すフローチャートである。図４４に示すように、ＰＭＭは、まず、値のリスト（ローカルリスト）中、論理和配列の対応する値が「０」であるような値からなる送出リストを生成する（ステップ４４０１）。この送出リスト（リモートリスト）は、図４３Ｂ〜図４３Ｅに示すものである。【０１３７】
次いで、ＰＭＭは、自己の値のリスト（ローカルリスト）に関する累計数配列Ａｇｇｒ、および、他の送出リストに基づくカウント配列Ｃｏｕｎｔ−１〜３のそれぞれに初期値を格納する（ステップ４４０２）。これら配列は、メモリなど記憶装置に設ければ良い。たとえば、図４５Ａに示すように、ＰＭＭは、自己のＰＭＭに関する累計数配列の値として、［０，１，２，３，・・・］というような「０」から始まる昇順の数字を格納する。これは、自己の値のリスト（ローカルリスト）について、それぞれの格納位置番号より前の格納位置番号に存在する値の数が、１ずつ増えていくことに基づく。また、カウント配列Ｃｏｕｎｔ−１〜３のそれぞれについて、全ての初期値は「０」となる。【０１３８】
ＰＭＭは、他のＰＭＭに送出リスト（リモートリスト）を送信するとともに（ステップ４４０３）、他のＰＭＭからの送出リスト（リモートリスト）を受信する（ステップ４４０４）。【０１３９】
ＰＭＭは、自己の値のリスト（ローカルリスト）のある値と、その一つ前（つまり格納位置番号が１つだけ小さい位置）の値との間に、他のＰＭＭからの送出リスト（リモートリスト）中の値がいくつ存在するかをカウントする（ステップ４４０５）。このカウントされた値を、当該自己の値のリスト（ローカルリスト）のある値についてのカウント値として、カウント配列に格納する。このステップ４４０５の処理は、全ての他のＰＭＭの送出リスト（リモートリスト）について実行される。【０１４０】
図４５Ａに示すように、ＰＭＭ−０は、ＰＭＭ−１から、［１０，２００，７００］という送出リスト（リモートリスト）を受信する。ＰＭＭ−０において、自己の値のリスト（ローカルリスト）中、格納位置番号「０」の値は「１００」である。したがって、それより小さいＰＭＭ−１からの送出リスト（リモートリスト）の値「１０」が存在するため、カウント配列Ｃｏｕｎｔ−１中、格納位置番号「０」の値が「１」となる。また、格納位置番号「１」の値は「３００」である。したがって、値「１００」から「３００」までの間に、ＰＭＭ−１からの送出リスト（リモートリスト）の値「２００」が存在するため、カウント配列Ｃｏｕｎｔ−１中、格納位置番号「１」の値は「１」となる。【０１４１】
なお、ステップ４４０５において、自己の値のリスト（ローカルリスト）中のある値と一致する、他のＰＭＭからの送出リストの値が存在した場合には、ＰＭＭは、この一致する値が反映するような、カウントを行わない。たとえば、図４５Ｂにおいて、ＰＭＭ−１の値のリスト（ローカルリスト）中、格納位置番号「２」の値は「３００」である。ここで、値のリスト中、一つ前の値「２００」から「３００」までの間に、「３００」を除くと、ＰＭＭ−０の送出リスト中の値は存在しない。しかしながら、値が一致する場合には、カウント配列におけるカウントは行われないため、カウント配列Ｃｏｕｎｔ−１中、格納位置番号「２」の値は「０」のままとなる。【０１４２】
次いで、ＰＭＭは、カウント配列の対応する値（つまり格納位置番号が同一の値）を合算して、値が合算されたカウント配列を得る（ステップ４４０７）。これは、いずれかのカウント配列に、他のカウント配列の値を、それぞれ加算することにより実現できる。さらに、ＰＭＭは、値が合算されたカウント配列の値を累計して、累計数配列を得る（ステップ４４０８）。さらに、ＰＭＭは、ステップ４４０８で得られた累計数配列の値と、自分自身の値のリストに関してステップ４４０２において予め用意し、初期値を格納しておいた累計数配列Ａｇｇｒの対応する値とを加算する（ステップ４４０９）。ステップ４４０９で得られた配列の値が、値のリスト（ローカルリスト）の値の順位を示す。【０１４３】
図４５Ａに示すように、ＰＭＭ−０は、他のＰＭＭであるＰＭＭ−１〜ＰＭＭ−３からの送出リスト（リモートリスト）を受信し、ステップ４４０５の処理により、カウント配列Ｃｏｕｎｔ−１〜Ｃｏｕｎｔ３を生成する。これらカウント配列の値を合算すると、合算された配列は［１，１，１，０］となる。さらに、これを累計化することで、累計数配列［１，２，３，３］を得ることができる。この配列のそれぞれの値に、ステップ４４０２で生成した自身の値のリスト（ローカルリスト）に関する累計数配列Ａｇｇｒ［０，１，２，３］の値を加算する。これにより得られた配列［１，３，５，６］が、ＰＭＭ−０の値のリスト（ローカルリスト）のそれぞれの値の、グローバルな順位を示す。【０１４４】
図４５Ｂ、図４６Ａ、Ｂは、それぞれ、ＰＭＭ−１、２、３に関する図４４の処理を説明する図である。これらの図に示すように、ＰＭＭ−１〜３においても、図４４の処理を実行することで、値のリスト（ローカルリスト）のそれぞれの値の、グローバルな順位を示す配列が得られることが理解できるであろう。【０１４５】
以上、詳細に説明したように、値のリスト中の値に対する順位付与の第２の手法を実現するために、情報処理システムの各ＰＭＭは、
ＰＭＭ自身が保持する値のリスト中の格納値のうち、代表モジュールであることを示す情報が付与されているものを含む送出リスト配列を生成する送出リスト配列生成手段と、
他のＰＭＭのデータ送信手段から送信され、自己のデータ受信手段により受信された、当該他のＰＭＭの送出リスト配列中の格納値に基づいて、ＰＭＭ自身が保持する値のリスト中の格納値の順位を算出する順位算出手段と、を備えている。
[値のリスト中の値に対する順位付与の第３の手法]
値のリスト中の値に順位を付与するためには、片側カウント処理（図１６）や検出フラグの生成（図４０）を実行しなくとも実現できる。この場合には、出願カウント処理（図１０）を実行した後に、処理で得られた第１のカウント配列を、対応する値のリストとともに送信する。【０１４６】
図５０は、他の手法を利用した場合の順位付与のためのカウント配列の生成処理を示すフローチャートである。図５０に示すように、ＰＭＭは、他のＰＭＭからの値のリスト中の値の出現をカウントするための第３のカウント配列群ＣＯＵＮＴ−１〜３をメモリなど記憶装置中に生成して、初期値を格納する（ステップ５００１）。カウント配列の初期値として「０」が与えられる。なお、ステップ５００１で、ＰＭＭは、自己のＰＭＭの値のリストのそれぞれの値に対する初期的な順位を格納した配列Ａｇｇｒ−０を生成し、その配列に初期値を生成しても良い。この配列Ａｇｇｒ−０の初期値は、「０」から開始される昇順の値となる。つまり、自己のＰＭＭの値のリストの値が「４」だけ存在すれば、配列Ａｇｇｒ−０の初期値は、［０，１，２，３］となる。無論、配列Ａｇｇｒ−０の生成および初期値の格納は、この段階で行われる必要は無く、使用される際に生成され、初期値が格納されても良い。【０１４７】
次いで、ＰＭＭは、自己のＰＭＭの値のリストの値、および、対応する第１のカウント配列の値の組（Ｖａｌｕｅ，Ｃｏｕｎｔ値）を含むリモートリスト（ＲＥＭＯＴＥ  ＬＩＳＴ）を、他のＰＭＭに送信する（ステップ５００２）。ＰＭＭは、他のＰＭＭからリモートリストを受信すると（ステップ２３０３）、以下に述べる処理を実行して、カウント配列に値を格納する。【０１４８】
ＰＭＭは、自己の値のリスト（ローカルリスト）中のある値と、その値の一つ前（つまり、格納位置番号が「１」だけ小さい位置）の値との間に、受信した他のＰＭＭからの値のリスト（リモートリスト）の値が存在すると、その値に対応するＣｏｕｎｔ値の逆数を、第３のカウント配列中、対応する位置に格納する（ステップ５００４）。上述したローカルリストの隣接する値の間に、リモートリスト中の複数の値が存在する場合には、それぞれのＣｏｕｎｔ値の逆数の和が、第３のカウント配列に格納される。なお、ＰＭＭは、ローカルリスト中の値と、他のＰＭＭからのリモートリスト中の値とが等しい場合には、上記逆数の格納を行わない。【０１４９】
図５１〜図５４は、それぞれ、ＰＭＭ−０〜ＰＭＭ−３における、図５０の処理にしたがった、第３のカウント配列への値の収容、および、その値の合算処理を示す図である。たとえば、ＰＭＭ−０において、ＰＭＭ−１からのリモートリスト中、「１０」、「２００」、「３００」、「７００」という値が含まれる。自己の値のリスト（ローカルリスト）の値と比較すると、「１０＜１００」であるため、カウント配列ＣＯＵＮＴ−１において、ローカルリストの値「１００」に対応する位置（格納位置番号「０」）の値として、Ｃｏｕｎｔ値「２」の逆数「１／２」が格納される。同様に、自己の値のリスト（ローカルリスト）の値「３００」について、「１００」と「３００」との間に、ＰＭＭ−１の値のリスト中の値「２００」が存在するため、カウント配列ＣＯＵＮＴ−１において、ローカルリストの値「３００」に対応する位置（格納位置番号「１」）の値として、Ｃｏｕｎｔ値「２」の逆数「１／２」が格納される。【０１５０】
ＰＭＭは、カウント配列への逆数の格納の処理を、全ての、他のＰＭＭから受信したリモートリストについて実行する（ステップ５００５）。その後、ＰＭＭは、第３のカウント配列の対応する値を合算し（ステップ５００６）、さらに、合算された値を累計化する（ステップ５００７）。図５１の例では、ＰＭＭ−１に関する第３のカウント配列［１／２，１／２，０，０］、ＰＭＭ−２に関する第３のカウント配列［０，１／２，１／２，０］、ＰＭＭ−３に関する第３のカウント配列［１／２，０，０，０］をカウントすると、値が合算されたカウント配列（図中、「ＣＯＵＮＴ」で示す）［１，１，１，０］を取得することができる。ＰＭＭ−１〜３についても同様に、値が合算されたカウント配列を得ることができる（図５２〜図５４参照）。【０１５１】
図５５Ａ、Ｂおよび図５６Ａ、Ｂは、それぞれ、ＰＭＭ−０〜ＰＭＭ−３における、図５０の処理にしたがった、累計数配列の生成、および、最終的な順位を格納した配列の生成を示す図である。たとえば、図５５Ａに示すように、ＰＭＭ−０においては、合算されたカウント配列［１，１，１，０］が累計化されて、累計数配列ＡＧＧＲ［１，２，３，３］が得られている。ＰＭＭ−１〜３においても、同様に、累計数配列ＡＧＧＲが取得される（図５５Ｂ、図５６Ａ、図５６Ｂ参照）。【０１５２】
さらに、ＰＭＭは、得られた累計数配列ＡＧＧＲの値と、自己のＰＭＭの値のリストのそれぞれの値に対する初期的な順位を格納した配列Ａｇｇｒ−０の対応する値とを加算して、最終的な配列を得る（ステップ５００８）。この値の加算により得られた配列が、自己のＰＭＭの値のリスト中のそれぞれの値の順位を示す配列となる。図５５Ａ〜図５６Ｂにおいて、配列ＧＶＮｏが、上記順位を示す配列を示す。【０１５３】
このように、片側カウント処理による第２のカウント配列や、検出フラグ配列を利用しなくとも、値のリスト中の値に対する順位を格納した配列を生成することが可能である。【０１５４】
以上詳細に説明したように、値のリスト中の値に対する順位付与の第３の手法を実現するために、情報処理システムの各ＰＭＭは、
他のＰＭＭに、値のリストに含まれる格納値を送信するデータ送信手段と、
他のＰＭＭから、値のリストに含まれる格納値を受信するデータ受信手段と、
ＰＭＭ自身が保持する値のリストと同一のサイズの出現カウント配列を生成し、当該出現カウント配列に初期値を格納し、ＰＭＭ自身が保持する値のリスト中の格納値が、他のＰＭＭからの値のリスト中に存在するときに、ＰＭＭ自身が保持する値のリスト中の格納値について、他のＰＭＭにおける値の存在を示すために、対応する出現カウント配列の値を増大させることにより、出現カウント配列を完成させる出現カウント配列生成手段と、
他のＰＭＭのデータ送信手段により送信され、自己のデータ受信手段により受信された、他のＰＭＭの値のリストおよび出現カウント配列を含むリモートリストに基づいて、ＰＭＭ自身が保持する値のリスト中の格納値の順位を算出する順位算出手段と、を備える。
［代表モジュールの選択処理］
次に、代表モジュールを選択するための具体的処理について説明する。代表モジュールを選択するためには、上述した、値のリスト中の値に対する順位付与の第１の手法、第２の手法に類似する処理を実行すれば良い。【０１５５】
まず、代表モジュール選択のための第１の手法について説明する。第１の手法においては、片側カウント処理（図１６参照）を実行することで、値のリスト中の値を代表するモジュールを決めることができる。各ＰＭＭが、図１６に示す処理を実行したときに得られた片側カウント配列（ＣＯＵＮＴ−Ｈ）を考える。具体的には、図１７〜図２０に示す片側カウント配列（ＣＯＵＮＴ−Ｈ）が得られたと考える。図５７Ａは、図１７〜図２０に示す値のリスト中の値を、仮想的に重複無く、かつ、昇順で並べた配列を示す図である。代表モジュールの選択処理では、図５７Ａに示す仮想的な配列中の値の各々を代表するようなＰＭＭを決定できれば良い。図５７Ｂ〜図５７Ｅは、それぞれ、ＰＭＭ−０〜ＰＭＭ−３に保持された値のリスト（ＬＯＣＡＬ＿ＬＩＳＴ）および生成された片側カウント配列（ＣＯＵＮＴ−Ｈ）を示す図である。【０１５６】
代表モジュール選択のための第１の手法においては、図５８Ａに示すように、ＰＭＭは、片側カウント処理を実行した後（ステップ５８０１）、当該片側カウント配列（ＣＯＵＮＴ−Ｈ）の値をメモリなど記憶装置から読み出し（ステップ５８０２）、読み出された片側カウント配列（ＣＯＵＮＴ−Ｈ）の値が「１」であるときに、値のリスト（ＬＯＣＡＬ＿ＬＩＳＴ）中の対応する値に関する代表モジュールが自己であると判断する（ステップ５８０３でイエス(Yes)）。したがって、この場合、ＰＭＭは、たとえば、自己の保持する値のリスト（ＬＯＣＡＬ＿ＬＩＳＴ）中の当該値に関連付けて、自己が代表モジュールであることを示す情報（たとえば、フラグなど一定の印）をメモリなど記憶装置に記憶する（ステップ５８０４）。【０１５７】
図５７Ｂ〜図５７Ｅに示す例では、仮想的な値のリスト（ＴＯＴＡＬ＿ＬＩＳＴ）において最初の値である「１０」については、ＰＭＭ−１が代表モジュールとなる（符合ＲＶ−０参照）。仮想的な値のリスト（ＴＯＴＡＬ＿ＬＩＳＴ）において格納位置番号「１」の要素である「１００」については、ＰＭＭ−０が代表モジュールとなる（符合ＲＶ−１参照）。図５７Ｂ〜図５７Ｅにおいて、ＲＶ−０〜ＲＶ−７が、それぞれ、仮想的な値のリスト中の値のそれぞれについて、代表モジュールとなるＰＭＭを示している。【０１５８】
第１の手法は、以下のような論理にしたがっている。図１６に示す処理では、自己より下位のＰＭＭから、自己の値のリスト中の値を受信していれば、片側カウント配列を加算している。したがって、片側カウント配列が「１」であることは、その値を保持しているＰＭＭのうち、自己が最下位のモジュールであることを意味している。つまり、値を保持している最下位のＰＭＭを一意的に決定することができる。したがって、代表モジュールとなったＰＭＭが、その値を伝送路に送出し、上記ＴＯＴＡＬ＿ＬＩＳＴを生成する処理を事項するＰＭＭが、伝送路からの値を受信して、受信された値を含む配列を生成することで、値の重複の無いような配列を得ることができる。さらに、ＰＭＭが、先に説明した「値に対する順位付与」の処理にて得られた、値の順位も伝送路に送出することで、何れかのＰＭＭにおいて、図５７Ａに示すような値の順序も考慮された配列（ＴＯＴＡＬ＿ＬＩＳＴ）を得ることが可能となる。【０１５９】
次に、代表モジュール選択のための第２の手法について説明する。第２の手法では、図５８Ｂに示すように、出現カウント処理（図１０参照）および片側カウント処理（図１６参照）の双方を実行し（ステップ５８１１）、ＰＭＭにおいて、得られた配列（「第１のカウント配列：出現カウント配列」および「第２のカウント配列：片側カウント配列」）の対応する値を読み出して（ステップ５８１２）、これらの値が一致する場合に（ステップ５８１３でイエス(Yes)）、ＰＭＭが，当該一致した値に関連する値のリスト（ＬＯＣＡＬ＿ＬＩＳＴ）の値についての代表モジュールになると決定する（ステップ５８１４）。以下の説明において、具体的に、図１０に示す処理により、図１１〜図１４に示す出現カウント配列（ＣＯＵＮＴ）が得られたと考える。また、図１６に示す処理により、図１７〜図２０に示す片側カウント配列（ＣＯＵＮＴ−Ｈ）が得られたと考える。【０１６０】
図５９Ａは、値のリスト中の値を、仮想的に重複無く、かつ、昇順で並べた配列を示す図である。図５９Ｂ〜図５９Ｅは、それぞれ、ＰＭＭ−０〜ＰＭＭ−３に保持された値のリスト（ＬＯＣＡＬ＿ＬＩＳＴ）、出現カウント配列（ＣＯＵＮＴ）および片側カウント配列（ＣＯＵＮＴ−Ｈ）を示す図である。【０１６１】
代表モジュール選択のための第２の手法においては、ＰＭＭは、出現カウント配列（ＣＯＵＮＴ）の値と、片側カウント配列（ＣＯＵＮＴ−Ｈ）の対応する値とが一致するときに、値のリスト（ＬＯＣＡＬ＿ＬＩＳＴ）中の対応する値に関する代表モジュールが自己であると判断する。したがって、この場合、ＰＭＭは、たとえば、自己の保持する値のリスト（ＬＯＣＡＬ＿ＬＩＳＴ）中の当該値に関連付けて、自己が代表モジュールであることを示す情報（たとえば、フラグなど一定の印）をメモリなど記憶装置に記憶する。【０１６２】
図５９Ｂ〜図５９Ｅに示す例では、仮想的な値のリスト（ＴＯＴＡＬ＿ＬＩＳＴ）において最初の値である「１０」については、ＰＭＭ−１およびＰＭＭ−３において、出現カウント配列（ＣＯＵＮＴ）および片側カウント配列（ＣＯＵＮＴ−Ｈ）が比較される。ＰＭＭ−３において、これらの配列の値が一致するため、ＰＭＭ−３が、値のリスト中の値「１０」の代表モジュールであると判断することができる（符号ＰＶ−０参照）。仮想的な値のリスト（ＴＯＴＡＬ＿ＬＩＳＴ）において格納位置番号「１」の要素である「１００」については、ＰＭＭ−０およびＰＭＭ−３において、出現カウント配列（ＣＯＵＮＴ）および片側カウント配列（ＣＯＵＮＴ−Ｈ）が比較される。ＰＭＭ−３において、これらの配列の値が一致するため、ＰＭＭ−３が、値のリスト中の値「１００」の代表モジュールであると判断することができる（符号ＰＶ−１参照）。図５９Ｂ〜図５９Ｅにおいて、ＲＶ−０〜ＲＶ−７が、それぞれ、仮想的な値のリスト中の値のそれぞれについて、代表モジュールとなるＰＭＭを示している。【０１６３】
第２の手法は、以下のような論理にしたがっている。ＰＭＭにおいて、出現カウント配列の値と、片側カウントの対応する値とが一致することは、その値を保持しているＰＭＭのうち自己が最上位のモジュールであることを意味している。つまり、値を保持している最上位のＰＭＭを一意的に決定することができる。【０１６４】
第１の手法では、値を有する最下位のＰＭＭであることを、該当するＰＭＭ自身が判断することで、それぞれの値の代表モジュールを決定し、また、第２の手法では、値を有する最上位のＰＭＭであることを、該当するＰＭＭ自身が判断することで、それぞれの値の代表モジュールを決定した。このように、最上位或いは最下位に限定されるものではなく、中間の地位のＰＭＭを代表モジュールと決定しても良い。以下、代表モジュール選択のための第３の手法について説明する。第３の手法では、図６０に示すように、ＰＭＭは、出現カウント配列（ＣＯＵＮＴ）の値が偶数であれば（ステップ６００３でイエス(Yes)）、「ＣＯＵＮＴの値／２」と片側カウント配列（ＣＯＵＮＴ−Ｈ）の対応する値とが等しいか否かを判断する（ステップ６００４でイエス(Yes)）。ステップ６００４でイエス(Yes)と判断された場合には、ＰＭＭは、自分自身が、これらの値に関する、値のリスト（ＬＯＣＡＬ＿ＬＩＳＴ）中の値の代表モジュールであると決定する（ステップ６００６）。その一方、出現カウント配列（ＣＯＵＮＴ）の値が奇数であれば（ステップ６００３でノー(No)）、ＰＭＭは、「（ＣＯＵＮＴの値＋１）／２」と片側カウント配列（ＣＯＵＮＴ−Ｈ）の対応する値とが等しいか否かを判断する（ステップ６００５）。ステップ６００５でイエス(Yes)と判断された場合には、ＰＭＭは、自分自身が、これらの値に関する、値のリスト（ＬＯＣＡＬ＿ＬＩＳＴ）中の値の代表モジュールであると決定する（ステップ６００６）。【０１６５】
さらに、出現カウント配列や片側カウント配列を利用せず、検出フラグ配列を利用しても、代表モジュールを選択することができる。代表モジュール選択のための第４の手法においては、ＰＭＭは、図４０に示すような検出フラグ配列の生成およびこれに基づく論理和配列の生成の後（ステップ６２０１）、生成された論理和配列の値をメモリなど記憶装置から読み出し、読み出された論理和配列の値が「０」であるときに、値のリスト（ＬＯＣＡＬ＿ＬＩＳＴ）中の対応する値に関する代表モジュールが自己であると判断する（ステップ６２０３でイエス(Yes)）。したがって、この場合、ＰＭＭは、たとえば、自己の保持する値のリスト（ＬＯＣＡＬ＿ＬＩＳＴ）中の当該値に関連付けて、自己が代表モジュールであることを示す情報（たとえば、フラグなど一定の印）をメモリなど記憶装置に記憶する（ステップ６２０４）。【０１６６】
図６１Ｂ〜図６１Ｅに示す例では、図６１Ａに示す仮想的な値のリスト（ＴＯＴＡＬ＿ＬＩＳＴ）において最初の値である「１０」については、ＰＭＭ−１が代表モジュールとなる（符合ＲＶ−０参照）。仮想的な値のリスト（ＴＯＴＡＬ＿ＬＩＳＴ）において格納位置番号「１」の要素である「１００」については、ＰＭＭ−０が代表モジュールとなる（符合ＲＶ−１参照）。図６１Ｂ〜図６１Ｅにおいて、ＲＶ−０〜ＲＶ−７が、それぞれ、仮想的な値のリスト中の値のそれぞれについて、代表モジュールとなるＰＭＭを示している。この結果は、図５７Ｂ〜図５７Ｅに示す例と同様である。【０１６７】
第４の手法は、以下のような論理にしたがっている。図４０に示す処理において得られた論理和配列の値が「０」であることは、その値を保持しているＰＭＭのうち、自己が最下位のモジュールであることを意味している。つまり、値を保持している最下位のＰＭＭを一意的に決定することができる。したがって、代表モジュールとなったＰＭＭが、その値を伝送路に送出し、上記ＴＯＴＡＬ＿ＬＩＳＴを生成する処理を事項するＰＭＭが、伝送路からの値を受信して、受信された値を含む配列を生成することで、値の重複の無いような配列を得ることができる。さらに、ＰＭＭが、先に説明した「値に対する順位付与」の処理にて得られた、値の順位も伝送路に送出することで、何れかのＰＭＭにおいて、図６１Ａに示すような値の順序も考慮された配列（ＴＯＴＡＬ＿ＬＩＳＴ）を得ることが可能となる。【０１６８】
以上、詳細に説明したように、代表モジュール選択処理を実現するために、情報処理システムの各ＰＭＭは、
他のＰＭＭに、値のリストに含まれる格納値を送信するデータ送信手段と、
他のＰＭＭから、値のリストに含まれる格納値を受信するデータ受信手段と、
データ受信手段により、ＰＭＭの各々に予め付与された順序にしたがって受信された、他のＰＭＭからの値のリストに基づいて、ＰＭＭ自身が保持する値のリスト中の格納値について、当該ＰＭＭ自身が当該格納値を保持する一つ以上のＰＭＭを代表する代表モジュールであるか否かを判断し、代表モジュールである場合に、格納値と関連付けて、代表モジュールであることを示す情報を記憶する代表モジュール判断手段と、を備える。【０１６９】
本発明は、以上の実施の形態に限定されることなく、特許請求の範囲に記載された発明の範囲内で、種々の変更が可能であり、それらも本発明の範囲内に包含されるものであることは言うまでもない。【０１７０】
前記実施の形態においては、メモリ、インタフェースおよび制御回路を有するＰＭＭを利用しているが、これに限定されるものではなく、パーソナルコンピュータ、サーバなどを、ローカルな表形式データを分掌する情報処理ユニットとして、ＰＭＭの代わりに利用しても良い。或いは、単一のパーソナルコンピュータやサーバが、複数の情報処理ユニットを保持するような構成を採用しても良い。これらの場合でも、情報処理ユニットが、レコードの順位を示す値を受理し、グローバル順序集合配列GOrdを参照することにより、レコードを特定することができる。また、グローバル値番号配列GVNoを参照することにより、項目値を特定することも可能である。【０１７１】
さらに、前記実施の形態においては、ＰＭＭがデータをパケット化して伝送路に送信しているがこれに限定されるものではなく、パケット以外の形態でデータを送信しても良いことは言うまでもない。【０１７２】
また、本実施の形態にかかる「重複の無い値のリストの取得（代表モジュールの選択）」、「値のリスト中の値に対する順位付与」、「値の整数化」の処理は、複数のＰＭＭにて分掌された表形式データだけでなく、複数のＰＭＭにて分掌された、複数の値を有するような値のリストに関して実行することが可能である。【０１７３】
また、前記実施の形態中、「値のリスト中の値に対する順位付与の第２の手法」においては（たとえば、図４０〜図４６Ｂ参照）、ＰＭＭが、検出フラグ配列および検出フラグ配列の値の論理和をとった論理和配列を生成し、論理和配列中の値が「０」となるような、値のリスト中の値のみを含む送出リストを生成して、この送出リストを、他のＰＭＭに送信している。上記「値のリスト中の値に対する順位付与の第２の手法」では、代表モジュールの選択処理における第４の手法（検出フラグ配列を利用した手法）を利用し、値のリスト中の値について、ＰＭＭ自身が代表モジュールとなるような値を含む送出リストを生成している。しかしながら、本発明は、上記態様に限定されるものではなく、代表モジュールの選択処理において説明した手法（たとえば、片側カウント配列を利用する第１の手法、出現カウント配列および片側カウント配列を使用する第２の手法或いは第３の手法）を利用して、各ＰＭＭが、当該ＰＭＭ自身が保持する値のリスト中、自分自身が代表モジュールとなるような値のみを含む送出リストを生成し、他のＰＭＭに送信するように構成しても良い。
【図面の簡単な説明】
【０１７４】
【図１】図１は、本発明の実施の形態にかかる情報処理システムの概略を示すブロックダイヤグラムである。
【図２】図２は、本発明の実施の形態にかかるＰＭＭの構造の一例を示す図である。
【図３】図３は、表形式データの一例を示す図である。
【図４】図４は、本実施の形態において、表形式データを保持する構造の原理を説明するための図である。
【図５】図５は、本実施の形態において、各ＰＭＭにて分掌把握される配列およびその値を説明する図である。
【図６】図６は、初期的にＰＭＭ−０〜４の各々にてそれぞれ分掌される表形式データの例を示す図である。
【図７】図７は、初期的にＰＭＭ−０〜４の各々にてそれぞれ分掌される表形式データの例を示す図である。
【図８】図８は、本実施の形態にかかるコンパイル処理を概略的に示すフローチャートである
【図９】図９は、図６〜図７に示す例でのグローバル順序集合配列GOrdへの値の配置を示す図である。
【図１０】図１０は、各ＰＭＭにおいて、他のＰＭＭにおける値の出現をカウントするために実行される処理の例を示すフローチャートである。
【図１１】図１１は、ＰＭＭ−０における、第１のカウント配列に関する処理を説明する図である。
【図１２】図１２は、ＰＭＭ−１における、第１のカウント配列に関する処理を説明する図である。
【図１３】図１３は、ＰＭＭ−２における、第１のカウント配列に関する処理を説明する図である。
【図１４】図１４は、ＰＭＭ−３における、第１のカウント配列に関する処理を説明する図である。
【図１５】図１５Ａは、ＰＭＭ−０〜ＰＭＭ−３のそれぞれが持つ値を、重複なくかつ昇順に並べた仮想的な値のリストを示す図、図１５Ｂ〜図１５Ｅは、それぞれ、ＰＭＭ−０〜ＰＭＭ−３のそれぞれにおける図１０に示す処理の実行結果を仮想的に示す配列である。
【図１６】図１６は、各ＰＭＭにおいて実行される片側カウント処理を示すフローチャートである。
【図１７】図１７は、ＰＭＭ−０における、第２のカウント配列に関する処理を説明する図である。
【図１８】図１８は、ＰＭＭ−１における、第２のカウント配列に関する処理を説明する図である。
【図１９】図１９は、ＰＭＭ−２における、第２のカウント配列に関する処理を説明する図である。
【図２０】図２０は、ＰＭＭ−３における、第２のカウント配列に関する処理を説明する図である。
【図２１】図２１は、各ＰＭＭにおいて実行されるカウント値に重みを与える処理を示すフローチャートである。
【図２２】図２２Ａは、仮想的な値リストおよび値の順位を格納した仮想的な配列を示す図、図２２Ｂ〜図２２Ｅは、それぞれ、ＰＭＭ−０〜ＰＭＭ−３における、図２１に示す処理にしたがって、第２のカウント配列の値を考慮した、第１のカウント配列の値の変更を説明する図、図２２Ｆは、カウント値を串刺しで通算した値を示す配列である。
【図２３】図２３は、各ＰＭＭにおいて実行される、自己が掌握する値のリスト中のそれぞれの値の順位を算出する処理を示すフローチャートである。
【図２４】図２４は、各ＰＭＭにおいて実行される、自己が掌握する値のリスト中のそれぞれの値の順位を算出する処理を示すフローチャートである。
【図２５】図２５Ａ〜図２５Ｃは、ＰＭＭ−０が、他のＰＭＭとしてＰＭＭ−１からのリモートリストを受信した際に実行する処理を詳細に説明する図である。
【図２６】図２６Ａ〜図２６Ｃは、ＰＭＭ−０が、他のＰＭＭとしてＰＭＭ−１からのリモートリストを受信した際に実行する処理を詳細に説明する図である。
【図２７】図２７は、各ＰＭＭにおいて実行される、自己が掌握する値のリスト中のそれぞれの値の順位を算出する処理を示すフローチャートである。
【図２８】図２８Ａ、Ｂは、それぞれ、ＰＭＭ−０〜ＰＭＭ−３において、図２３、２４および図２７の処理が実行されたときの配列等の状態を説明する図である。
【図２９】図２９Ａ、Ｂは、それぞれ、ＰＭＭ−０〜ＰＭＭ−３において、図２３、２４および図２７の処理が実行されたときの配列等の状態を説明する図である。
【図３０】図３０Ａ、Ｂは、それぞれ、ＰＭＭ−０〜ＰＭＭ−３において、図２３、２４および図２７の処理が実行されたときの配列等の状態を説明する図である。
【図３１】図３１Ａ、Ｂは、それぞれ、ＰＭＭ−０〜ＰＭＭ−３において、図２３、２４および図２７の処理が実行されたときの配列等の状態を説明する図である。
【図３２】図３２Ａは、仮想的な値リストおよび値の順位を格納した仮想的な配列を示す図で、図３２Ｂ〜図３２Ｅは、それぞれ、ＰＭＭ−０〜ＰＭＭ−３において算出された、値のリストのそれぞれの値の順位を示す図である。
【図３３】図３３Ａ、Ｂは、それぞれ、値が文字列である場合の値のリストの例、および、それに順位が付けられた例を示す図である。
【図３４】図３４Ａ、Ｂは、それぞれ、値が浮動小数点である場合の値のリストの例、および、それに順位が付けられた例を示す図である。
【図３５】図３５Ａ、Ｂは、それぞれ、値が整数の組である場合の値のリストの例、および、それに順位が付けられた例を示す図である。
【図３６】図３６は、各ＰＭＭにおいて、上記第１のステップである一定の順序を持つ、連続とは限らない整数を、値に割り当てる際に実行される処理の例を示すフローチャートである。
【図３７】図３７Ａ、Ｂは、それぞれ、ＰＭＭ−０、ＰＭＭ−１における累計数配列Ａｇｇｒ（ＩＤ）の生成を説明する図である。
【図３８】図３８Ａ、Ｂは、それぞれ、ＰＭＭ−０、ＰＭＭ−１における累計数配列Ａｇｇｒ（ＩＤ）の生成を説明する図である。
【図３９】図３９Ａは、仮想的な値のリスト、および、それぞれの値に割り当てられた、一定の順序をもち、かつ、必ずしも連続しない整数の配列を示す図、図３９Ｂ〜図３９Ｅは、それぞれ、各ＰＭＭで図３６の処理の結果得られた、累計数配列Ａｇｇｒ（ＩＤ）の整数値を、値のリスト（ローカルリスト）の値と関連付けて、仮想的に配置した図である。
【図４０】図４０は、検出フラグ配列および論理和配列の生成処理を示すフローチャートである。
【図４１】図４１Ａ、Ｂは、ＰＭＭ−０、１における、検出フラグ配列に関する処理を説明する図である。
【図４２】図４２Ａ、Ｂは、ＰＭＭ−２、３における、検出フラグ配列に関する処理を説明する図である。
【図４３】図４３Ａは、ＰＭＭ−０〜ＰＭＭ−３のそれぞれが持つ値を、重複なくかつ昇順に並べた仮想的な値のリストおよび当該値のリストのそれぞれの値の順序を格納した仮想的な配列を示す図、図４３Ｂ〜図４３Ｅは、それぞれのＰＭＭについて、仮想的な値のリスト、論理和配列、および、送出リストを示す図である。
【図４４】図４４は、本発明の他の実施の形態にかかるＰＭＭにおいて実行される、値の順位を決定する処理を示すフローチャートである。
【図４５】図４５Ａ、Ｂは、それぞれ、ＰＭＭ−０、ＰＭＭ−１において、図４４に示す処理が実行されたときの配列の状態を示す図である。
【図４６】図４６Ａ、Ｂは、それぞれ、ＰＭＭ−２、ＰＭＭ−３において、図４４に示す処理が実行されたときの配列の状態を示す図である。
【図４７】図４７は、図１は、本発明の実施の形態にかかる情報処理システムの全体を示すブロックダイヤグラムである。
【図４８】図４８は、図１のブロックダイヤグラムにおいて、他のグループからのデータ通信の伝送路を加えた図である。
【図４９】図４９Ａは、仮想的な値のリストを示す図、図４９Ｂ〜図４９Ｅは、それぞれ、各ＰＭＭにおいて分掌された値のリストの例を示す図である。
【図５０】図５０は、順位付与のためのカウント配列の生成処理の他の例を示すフローチャートである。
【図５１】図５２は、図５０に示す処理を説明するための図である。
【図５２】図５３は、図５０に示す処理を説明するための図である。
【図５３】図５４は、図５０に示す処理を説明するための図である。
【図５４】図５１は、図５０に示す処理を説明するための図である。
【図５５】図５５Ａ、Ｂは、それぞれ、図５０に示す処理を説明するための図である。
【図５６】図５６Ａ、Ｂは、それぞれ、図５０に示す処理を説明するための図である。
【図５７】図５７Ａ〜Ｅは、代表モジュール選択のための第１の手法を説明するための図である。
【図５８】図５８Ａ、Ｂは、それぞれ、代表モジュール選択のためにＰＭＭにて実行される処理の例を示す図ある。
【図５９】図５９Ａ〜図５９Ｅは、代表モジュール選択のための第２の手法を説明するための図である。
【図６０】図６０は、代表モジュール選択のためにＰＭＭにて実行される処理の他の例を示す図ある。
【図６１】図６１Ａ〜図６１Ｅは、代表モジュール選択のための第４の手法を説明するための図である。
【図６２】図６２は、代表モジュール選択のためにＰＭＭにて実行される処理のさらに他の例を示す図ある。
【図６３】図６３は、図６の例について、処理の結果得られた配列ＧＶＮｏなどを示す図である。
【図６４】図６４は、図７の例について、処理の結果得られた配列ＧＶＮｏなどを示す図である。
【符号の説明】
【０１７５】
１２        ＰＭＭ
２０        制御回路
２２        バスＩ／Ｆ
２４        メモリ
２６        バンク
【図１】
0004995724.tif 000002
【図２】
0004995724.tif 000003
【図３】
0004995724.tif 000004
【図４】
0004995724.tif 000005
【図５】
0004995724.tif 000006
【図６】
0004995724.tif 000007
【図７】
0004995724.tif 000008
【図８】
0004995724.tif 000009
【図９】
0004995724.tif 000010
【図１０】
0004995724.tif 000011
【図１１】
0004995724.tif 000012
【図１２】
0004995724.tif 000013
【図１３】
0004995724.tif 000014
【図１４】
0004995724.tif 000015
【図１５】
0004995724.tif 000016
【図１６】
0004995724.tif 000017
【図１７】
0004995724.tif 000018
【図１８】
0004995724.tif 000019
【図１９】
0004995724.tif 000020
【図２０】
0004995724.tif 000021
【図２１】
0004995724.tif 000022
【図２２】
0004995724.tif 000023
【図２３】
0004995724.tif 000024
【図２４】
0004995724.tif 000025
【図２５】
0004995724.tif 000026
【図２６】
0004995724.tif 000027
【図２７】
0004995724.tif 000028
【図２８】
0004995724.tif 000029
【図２９】
0004995724.tif 000030
【図３０】
0004995724.tif 000031
【図３１】
0004995724.tif 000032
【図３２】
0004995724.tif 000033
【図３３】
0004995724.tif 000034
【図３４】
0004995724.tif 000035
【図３５】
0004995724.tif 000036
【図３６】
0004995724.tif 000037
【図３７】
0004995724.tif 000038
【図３８】
0004995724.tif 000039
【図３９】
0004995724.tif 000040
【図４０】
0004995724.tif 000041
【図４１】
0004995724.tif 000042
【図４２】
0004995724.tif 000043
【図４３】
0004995724.tif 000044
【図４４】
0004995724.tif 000045
【図４５】
0004995724.tif 000046
【図４６】
0004995724.tif 000047
【図４７】
0004995724.tif 000048
【図４８】
0004995724.tif 000049
【図４９】
0004995724.tif 000050
【図５０】
0004995724.tif 000051
【図５１】
0004995724.tif 000052
【図５２】
0004995724.tif 000053
【図５３】
0004995724.tif 000054
【図５４】
0004995724.tif 000055
【図５５】
0004995724.tif 000056
【図５６】
0004995724.tif 000057
【図５７】
0004995724.tif 000058
【図５８】
0004995724.tif 000059
【図５９】
0004995724.tif 000060
【図６０】
0004995724.tif 000061
【図６１】
0004995724.tif 000062
【図６２】
0004995724.tif 000063
【図６３】
0004995724.tif 000064
【図６４】
0004995724.tif 000065