(57)【特許請求の範囲】
【請求項１】
記憶装置から読み取る記憶領域を指し示すアドレスを記憶するリストベクトルに従い、複数の情報処理装置のうち、自情報処理装置のみがアクセスする記憶領域における値をレジスタに読み取る処理と、前記自情報処理装置と他情報処理装置とがともにアクセスする記憶領域であるか否かを表す参照アクセス情報を作成する処理とを指示する第１ギャザ命令に応じて、前記リストベクトルに従いアクセスする記憶領域を所定の分割方法に従って、論理的に複数の小領域に分割し、分割したそれぞれの前記小領域にアクセスするか否かを表すアクセス情報を作成するとともに、前記自情報処理装置が前記リストベクトルに従いアクセスする複数のアドレスから、前記所定の分割方法に応じた所定の対応情報に基づいて、特定の小領域を算出し、前記アクセス情報において、前記特定の小領域に関連付けされた値を、アクセスすることを表す値に更新するとともに、前記記憶装置において前記リストベクトルが指し示す記憶領域のうち、前記自情報処理装置のみがアクセスする記憶領域における値をレジスタに読み取るギャザ処理部と、
前記自情報処理装置が更新した前記アクセス情報を自アクセス情報として前記他情報処理装置に送信し、前記他情報処理装置が送信した前記アクセス情報を、他アクセス情報として受信する通信部と、
前記自アクセス情報と、前記他アクセス情報とに基づいて、所定の算出方法に従い、前記自情報処理装置と前記他情報処理装置とがともにアクセスする前記小領域を算出するとともに、該算出した小領域を参照小領域とし、前記複数の小領域が前記参照小領域であるか否かを表す前記アクセス情報を算出し、該算出した前記アクセス情報を参照アクセス情報とするアクセス情報演算部と、
レジスタが記憶する値を、前記記憶装置における前記リストベクトルが指し示す記憶領域のうち、前記自情報処理装置のみがアクセスする記憶領域に保存する命令である第１スキャタ命令に応じて、前記レジスタが記憶する値を、前記参照アクセス情報に基づき、前記リストベクトルが指し示す記憶領域のうち、前記参照小領域ではない記憶領域に保存するスキャタ処理部と
を備えるリストベクトル処理装置。
【請求項２】
前記記憶装置において、前記リストベクトルが指し示す記憶領域のうち、前記参照小領域における値を前記レジスタに読み取る第２ギャザ命令に応じて、前記参照アクセス情報に基づき、前記記憶装置において前記リストベクトルが指し示す記憶領域のうち、前記参照小領域における値を、前記レジスタに保存する第２ギャザ処理部と、
前記レジスタが記憶する値を、前記リストベクトルが指し示す記憶領域のうち、前記参照小領域に保存する命令である第２スキャタ命令に応じて、前記参照アクセス情報に基づき、前記レジスタが記憶する値を、前記リストベクトルが指し示す記憶領域のうち前記参照小領域に保存する第２スキャタ処理部と
を更に備える
請求項１に記載のリストベクトル処理装置。
【請求項３】
前記アクセス情報演算部は、
ビットごとに論理和を算出する論理和演算部と、ビットごとに論理積を算出する論理積演算部と、アクセス制御部と
を備え、
スレッドは、該スレッドを起動する順序に関連するスレッド番号に関連付けされており、
前記通信部は、前記自アクセス情報とともに、前記自情報処理装置が処理する前記スレッドの前記スレッド番号を、前記他情報処理装置に送信し、さらに、前記他アクセス情報及び前記スレッド番号を受信し、受信した前記他アクセス情報をアクセス情報キューに保存するとともに、受信した前記スレッド番号をスレッド格納レジスタに保存し、
前記アクセス制御部は、前記スレッド格納レジスタが記憶する前記スレッド番号と、前記自情報処理装置が処理する前記スレッドの前記スレッド番号とを順次比較し、前記自情報処理装置が処理する前記スレッドの前記スレッド番号が、前記スレッド格納レジスタが記憶する前記スレッド番号よりも小さい場合に、前記論理和演算部に有効信号を送信し、
前記論理和演算部は、前記アクセス制御部が送信する前記有効信号に応じて、アクセス情報レジスタが記憶する値、及び、前記アクセス情報キューから前記他アクセス情報を読み出し、読み出した前記値と、読み出した前記他アクセス情報との論理和をビットごとに算出し、該算出した値を前記アクセス情報レジスタに保存し、
前記アクセス制御部は、前記スレッド格納レジスタが記憶する前記スレッド番号に関する処理が終了するに応じて、前記論理積演算部に演算信号を送信し、
前記論理積演算部は、前記アクセス制御部が送信する前記演算信号に応じて、前記アクセス情報レジスタから値を読み出し、読み出した該値と、前記自アクセス情報との論理積をビットごとに算出し、該算出した値に基づいて、前記参照アクセス情報を算出する
請求項１または請求項２に記載のリストベクトル処理装置。
【請求項４】
前記アクセス制御部は、前記論理積演算部が前記参照小領域を算出する処理に応じて、前記参照小領域を算出する処理が完了したことを表す同期信号を送信する
請求項３に記載のリストベクトル処理装置
【請求項５】
前記アクセス情報演算部は、前記参照アクセス情報に基づいて、さらに、前記記憶装置において、前記自情報処理装置のみがアクセスする前記小領域を独立小領域として算出し、前記複数の小領域が前記独立小領域であるか否かを表す独立アクセス情報を生成し、
前記スキャタ処理部は、前記独立アクセス情報に基づいて、前記レジスタが記憶する値を、前記リストベクトルが指し示す記憶領域のうち、前記独立小領域に保存する
請求項２乃至請求項４のいずれかに記載のリストベクトル処理装置。
【請求項６】
前記所定の分割方法は、前記リストベクトルが指し示す記憶領域を、所定の単位にて分割する方法である
請求項１乃至請求項５のいずれかに記載のリストベクトル処理装置。
【請求項７】
前記所定の単位は、前記リストベクトルが指し示す記憶領域の大きさを、前記情報処理装置の数で割った値とする
請求項６に記載のリストベクトル処理装置。
【請求項８】
記憶装置から読み取る記憶領域を指し示すアドレスを記憶するリストベクトルに従い、複数の情報処理装置のうち、自情報処理装置のみがアクセスする記憶領域における値をレジスタに読み取る処理と、前記自情報処理装置と他情報処理装置とがともにアクセスする記憶領域であるか否かを表す参照アクセス情報を作成する処理とを指示する第１ギャザ命令に応じて、前記リストベクトルに従いアクセスする記憶領域を所定の分割方法に従って、論理的に複数の小領域に分割し、分割したそれぞれの前記小領域にアクセスするか否かを表すアクセス情報を作成するとともに、前記自情報処理装置が前記リストベクトルに従いアクセスする複数のアドレスから、前記所定の分割方法に応じた所定の対応情報に基づいて、特定の小領域を算出し、前記アクセス情報において、前記特定の小領域に関連付けされた値を、アクセスすることを表す値に更新するとともに、前記記憶装置において前記リストベクトルが指し示す記憶領域のうち、前記自情報処理装置のみがアクセスする記憶領域における値をレジスタに読み取り、前記自情報処理装置が更新した前記アクセス情報を自アクセス情報として前記他情報処理装置に送信し、前記他情報処理装置が送信した前記アクセス情報を、他アクセス情報として受信し、前記自アクセス情報と、前記他アクセス情報とに基づいて、所定の算出方法に従い、前記自情報処理装置と前記他情報処理装置とがともにアクセスする前記小領域を算出するとともに、該算出した小領域を参照小領域とし、前記複数の小領域が前記参照小領域であるか否かを表す前記アクセス情報を算出し、該算出した前記アクセス情報を参照アクセス情報とし、レジスタが記憶する値を、前記記憶装置における前記リストベクトルが指し示す記憶領域のうち、前記自情報処理装置のみがアクセスする記憶領域に保存する命令である第１スキャタ命令に応じて、前記レジスタが記憶する値を、前記参照アクセス情報に基づき、前記リストベクトルが指し示す記憶領域のうち、前記参照小領域ではない記憶領域に保存する
リストベクトル処理方法。
【請求項９】
記憶装置から読み取る記憶領域を指し示すアドレスを記憶するリストベクトルに従い、複数の情報処理装置のうち、自情報処理装置のみがアクセスする記憶領域における値をレジスタに読み取る処理と、前記自情報処理装置と他情報処理装置とがともにアクセスする記憶領域であるか否かを表す参照アクセス情報を作成する処理とを指示する第１ギャザ命令に応じて、前記リストベクトルに従いアクセスする記憶領域を所定の分割方法に従って、論理的に複数の小領域に分割し、分割したそれぞれの前記小領域にアクセスするか否かを表すアクセス情報を作成するとともに、前記自情報処理装置が前記リストベクトルに従いアクセスする複数のアドレスから、前記所定の分割方法に応じた所定の対応情報に基づいて、特定の小領域を算出し、前記アクセス情報において、前記特定の小領域に関連付けされた値を、アクセスすることを表す値に更新するとともに、前記記憶装置において前記リストベクトルが指し示す記憶領域のうち、前記自情報処理装置のみがアクセスする記憶領域における値をレジスタに読み取るギャザ処理機能と、
前記自情報処理装置が更新した前記アクセス情報を自アクセス情報として前記他情報処理装置に送信し、前記他情報処理装置が送信した前記アクセス情報を、他アクセス情報として受信する通信機能と、
前記自アクセス情報と、前記他アクセス情報とに基づいて、所定の算出方法に従い、前記自情報処理装置と前記他情報処理装置とがともにアクセスする前記小領域を算出するとともに、該算出した小領域を参照小領域とし、前記複数の小領域が前記参照小領域であるか否かを表す前記アクセス情報を算出し、該算出した前記アクセス情報を参照アクセス情報とするアクセス情報演算機能と、
レジスタが記憶する値を、前記記憶装置における前記リストベクトルが指し示す記憶領域のうち、前記自情報処理装置のみがアクセスする記憶領域に保存する命令である第１スキャタ命令に応じて、前記レジスタが記憶する値を、前記参照アクセス情報に基づき、前記リストベクトルが指し示す記憶領域のうち、前記参照小領域ではない記憶領域に保存するスキャタ処理機能と
をコンピュータに実現させるプログラム。
【請求項１０】
請求項１乃至請求項７のいずれかに記載のリストベクトル処理装置を含む情報処理装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、リストベクトルを高速に処理するリストベクトル処理装置等に関する。
【背景技術】
【０００２】
１台のプロセッサ（情報処理装置）あたりの処理性能は、年々向上しているが、その性能向上は鈍化している。マルチコア（メニーコア、ｍｕｌｔｉ−ｃｏｒｅ、ｍａｎｙ−ｃｏｒｅ）技術は、さらに高い性能向上を達成する１つの技術であり、複数のコアが並列に所望の処理を行う技術である。マルチコア技術において、処理性能をより向上させるためには、並列効率を高くすることが重要である。
【０００３】
数値シミュレーションは、ユーザがプロセッサに対して高い処理性能を要求する分野の１つである。例えば、構造解析において、ユーザは、シミュレーションする対象（例えば、建物）を、偏微分方程式を用いて表現することにより、該対象をシミュレーションする。ユーザは、情報処理装置上でシミュレーションするために、該偏微分方程式を離散化する。例えば、有限要素法などを適用することにより、偏微分方程式は、大規模疎行列を係数行列として有する連立一次方程式に変換される。
【０００４】
その場合、該係数行列には、非ゼロ要素がランダムに出現する。ゼロ要素と変数との掛け算は、理論的に無駄な演算である。そのため、非ゼロ要素だけをアクセスすることにより無駄な演算を減らす手法として、リストベクトルを用いて演算する手法が知られている。該リストベクトルは、該係数行列における非ゼロ要素のみを記憶する配列である。
【０００５】
例えば、リストベクトルを処理するプログラムは、プログラム１である。
【０００６】
Ｄｏ  ｉ＝１，Ｋ×Ｎ  Ｓ（Ａ（ｉ））＝Ｓ（Ａ（ｉ））＋Ｘ（ｉ）（ただし、Ｋ、Ｎは、正の整数、Ｓは配列、Ａはリストベクトル、Ｘは変数を表す。）・・・（プログラム１）、
プログラム１において、配列Ｓは、Ｍ個の要素を有するとする。その場合、１≦Ａ（ｊ）≦Ｍ（ただし、１≦ｉ≦Ｋ×Ｎ）である。
【０００７】
プログラム１は、配列Ｓの要素のうち、リストベクトルＡの第１乃至Ｎ要素が指し示す要素の値を更新及び参照する処理である。
【０００８】
情報処理装置は、リストベクトルＡが指し示す値に従い、配列Ｓの値を主記憶装置からレジスタへ読み込むとともに、レジスタが記憶する値を主記憶装置へ書き込む。リストベクトルＡが指し示す値に従い、レジスタが記憶する値を主記憶装置へ書き込む命令は、スキャタ（ｓｃａｔｔｅｒ）命令と呼ばれる。また、リストベクトルＡが指し示す値に従い、配列Ｓの値を主記憶装置からレジスタへ読み込む命令は、ギャザ（ｇａｔｈｅｒ）命令と呼ばれる。
【０００９】
すなわち、ギャザ命令は、主記憶装置が記憶する配列Ｓにおける第Ａ（ｉ）（ただし、１≦ｉ≦Ｋ×Ｎ）要素の値をレジスタに読み取る命令である（プログラム１の右辺におけるＳ（Ａ（ｉ））に関する処理）。一方、スキャタ命令は、レジスタから、主記憶装置上の配列Ｓにおける第Ａ（ｉ）（ただし、１≦ｉ≦Ｋ×Ｎ）要素に値を保存する命令である（プログラム１の左辺におけるＳ（Ａ（ｉ））に関する処理）。
【００１０】
プログラム１が表すプログラムを並列に処理する場合、例えば、第ｋ（ただし、１≦ｋ≦Ｋ）コアは、それぞれ、配列Ａの第Ｎ×（ｋ−１）＋１乃至Ｎ×ｋ要素に関する処理を実施する。各コアは、上記のように、分割されたスキャタ命令、及び、分割されたギャザ命令を処理する。
【００１１】
特許文献１乃至特許文献３は、プログラムを並列に処理する技術を開示する。
【００１２】
特許文献１が開示するコンパイラは、分散メモリプロセッサシステムにおいて、リストベクトルを含むソースプログラムを、並列化されたオブジェクトプログラムに変換する。該コンパイラは、各プロセッサが参照するリストベクトルに関する情報を収集するための前処理命令を、オブジェクトプログラムに挿入する。該コンパイラは、さらに、該前処理命令が収集する情報に基づいて、並列化に必要な通信を実施するオブジェクトプログラムを挿入する。
【００１３】
特許文献２は、ＬＵ分解処理などの反復処理を並列計算機でより短時間に実行可能にする実行方法を開示する。ＬＵ分解処理は、疎行列とは異なる密行列を係数行列として有する連立一次方程式を求解する方法である。
【００１４】
特許文献３が開示するコンパイラは、ユーザが指示する分割方法に応じて、リストベクトルを処理するソースプログラムを、並列化されたオブジェクトプログラムに変換する。
【先行技術文献】
【特許文献】
【００１５】
【特許文献１】特開平１１−２０３２５６号公報
【特許文献２】特開平０８−２２７４０５号公報
【特許文献３】特開平０７−０４４５０８号公報
【発明の概要】
【発明が解決しようとする課題】
【００１６】
例えば、複数の情報処理装置がプログラム１に示すプログラムを並列に処理する場合に、各情報処理装置は、１つの変数を参照及び更新する。１つの変数を参照し合うプログラムを並列化するために、コンパイラは、各情報処理装置における処理をスケジューリングする必要がある。しかしながら、コンパイラは、リストベクトルにおいて参照する要素を解析する機能を有さないため、ユーザを介することなくスケジューリングすることができない。その結果、コンパイラは、該プログラムを逐次的に処理するオブジェクトプログラムに変換する。
【００１７】
特許文献１が開示するコンパイラは、入力されたプログラムを、上述した前処理命令を逐次的に処理するオブジェクトプログラムに変換する。その結果、十分な並列化効率を達成することができない。
【００１８】
特許文献２が開示する方法は、リストベクトルを処理する方式に適用することができない。
【００１９】
特許文献３が開示するコンパイラにおいて、ユーザは、リストベクトルが参照する配列の要素ごとに、所望の処理を割り当てる情報処理装置を決める必要がある。そのため、ユーザが該分割を算出する処理に時間を要する。
【００２０】
そこで、本発明の主たる目的は、例えば、リストベクトル等の間接参照処理を、高速に実施するリストベクトル処理装置等を提供することである。
【課題を解決するための手段】
【００２１】
前述の目的を達成するために、本発明に係るリストベクトル処理装置は、以下の構成を備えることを特徴とする。
【００２２】
即ち、本発明に係るリストベクトル処理装置は、
記憶装置から読み取る記憶領域を指し示すアドレスを記憶するリストベクトルに従い、複数の情報処理装置のうち、自情報処理装置のみがアクセスする記憶領域における値をレジスタに読み取る処理と、前記自情報処理装置と他情報処理装置とがともにアクセスする記憶領域であるか否かを表す参照アクセス情報を作成する処理とを指示する第１ギャザ命令に応じて、前記リストベクトルに従いアクセスする記憶領域を所定の分割方法に従って、論理的に複数の小領域に分割し、分割したそれぞれの前記小領域にアクセスするか否かを表すアクセス情報を作成するとともに、前記自情報処理装置が前記リストベクトルに従いアクセスする複数のアドレスから、前記所定の分割方法に応じた所定の対応情報に基づいて、特定の小領域を算出し、前記アクセス情報において、前記特定の小領域に関連付けされた値を、アクセスすることを表す値に更新するとともに、前記記憶装置において前記リストベクトルが指し示す記憶領域のうち、前記自情報処理装置のみがアクセスする記憶領域における値をレジスタに読み取るギャザ処理部と、
前記自情報処理装置が更新した前記アクセス情報を自アクセス情報として前記他情報処理装置に送信し、前記他情報処理装置が送信した前記アクセス情報を、他アクセス情報として受信する通信部と、
前記自アクセス情報と、前記他アクセス情報とに基づいて、所定の算出方法に従い、前記自情報処理装置と前記他情報処理装置とがともにアクセスする前記小領域を算出するとともに、該算出した小領域を参照小領域とし、前記複数の小領域が前記参照小領域であるか否かを表す前記アクセス情報を算出し、該算出した前記アクセス情報を参照アクセス情報とするアクセス情報演算部と、
レジスタが記憶する値を、前記記憶装置における前記リストベクトルが指し示す記憶領域のうち、前記自情報処理装置のみがアクセスする記憶領域に保存する命令である第１スキャタ命令に応じて、前記レジスタが記憶する値を、前記参照アクセス情報に基づき、前記リストベクトルが指し示す記憶領域のうち、前記参照小領域ではない記憶領域に保存するスキャタ処理部と
を備えることを特徴とする。
【００２３】
また、本発明の他の見地として、本発明に係るリストベクトル処理方法は、
記憶装置から読み取る記憶領域を指し示すアドレスを記憶するリストベクトルに従い、複数の情報処理装置のうち、自情報処理装置のみがアクセスする記憶領域における値をレジスタに読み取る処理と、前記自情報処理装置と他情報処理装置とがともにアクセスする記憶領域であるか否かを表す参照アクセス情報を作成する処理とを指示する第１ギャザ命令に応じて、前記リストベクトルに従いアクセスする記憶領域を所定の分割方法に従って、論理的に複数の小領域に分割し、分割したそれぞれの前記小領域にアクセスするか否かを表すアクセス情報を作成するとともに、前記自情報処理装置が前記リストベクトルに従いアクセスする複数のアドレスから、前記所定の分割方法に応じた所定の対応情報に基づいて、特定の小領域を算出し、前記アクセス情報において、前記特定の小領域に関連付けされた値を、アクセスすることを表す値に更新するとともに、前記記憶装置において前記リストベクトルが指し示す記憶領域のうち、前記自情報処理装置のみがアクセスする記憶領域における値をレジスタに読み取り、前記自情報処理装置が更新した前記アクセス情報を自アクセス情報として前記他情報処理装置に送信し、前記他情報処理装置が送信した前記アクセス情報を、他アクセス情報として受信し、前記自アクセス情報と、前記他アクセス情報とに基づいて、所定の算出方法に従い、前記自情報処理装置と前記他情報処理装置とがともにアクセスする前記小領域を算出するとともに、該算出した小領域を参照小領域とし、前記複数の小領域が前記参照小領域であるか否かを表す前記アクセス情報を算出し、該算出した前記アクセス情報を参照アクセス情報とし、レジスタが記憶する値を、前記記憶装置における前記リストベクトルが指し示す記憶領域のうち、前記自情報処理装置のみがアクセスする記憶領域に保存する命令である第１スキャタ命令に応じて、前記レジスタが記憶する値を、前記参照アクセス情報に基づき、前記リストベクトルが指し示す記憶領域のうち、前記参照小領域ではない記憶領域に保存する
ことを特徴とする。
【発明の効果】
【００２４】
本発明に係るリストベクトル処理装置等によれば、例えば、リストベクトル等の間接参照処理を高速に実施することができる。
【図面の簡単な説明】
【００２５】
【図１】第１の実施形態に係るリストベクトル処理装置が有する構成を示すブロック図である。
【図２】第１の実施形態に係るギャザ処理部における処理の流れを示すフローチャートである。
【図３】第１の実施形態に係る通信部における処理の流れを示すフローチャートである。
【図４】第１の実施形態に係るアクセス情報を概念的に表す図である。
【図５】本発明の第２の実施形態に係るリストベクトル処理装置が有する構成を示すブロック図である。
【図６】本発明の第２の実施形態に係る第２ギャザ処理部における処理の流れを示すフローチャートである。
【図７】本発明の第２の実施形態に係る第２スキャタ処理部における処理の流れを示すフローチャートである。
【図８】本発明の第３の実施形態に係るアクセス情報演算部が有する構成を示すブロック図である。
【図９】本発明の第３の実施形態に係るアクセス制御部における処理の流れを示すフローチャートである。
【図１０】本発明の第３の実施形態に係る論理和演算部における処理の流れを示すフローチャートである。
【図１１】本発明の第３の実施形態に係る論理積演算部における処理の流れを示すフローチャートである。
【図１２】本実施形態に係るリストベクトル処理装置が行う処理のタイミングを表すシーケンス図である。
【図１３】コンパイラがプログラム３に対して出力するオブジェクトプログラムの一例を概念的に表す図である。
【図１４】ＶＲ０が記憶する値の一例を概念的に表す図である。
【図１５】ＶＲ１が記憶するアドレスの一例を概念的に表す図である。
【図１６】アクセス情報を算出する過程を模式的に表す図である。
【発明を実施するための形態】
【００２６】
次に、発明を実施するための最良の形態について図面を参照して詳細に説明する。
【００２７】
＜第１の実施形態＞
本発明の第１の実施形態に係るリストベクトル処理装置１０１が有する構成と、リストベクトル処理装置１０１が行う処理とについて、図１乃至図３を参照しながら、プログラム１を例として説明する。図１は、第１の実施形態に係るリストベクトル処理装置１０１が有する構成を示すブロック図である。図２は、第１の実施形態に係るギャザ処理部１０２における処理の流れを示すフローチャートである。図３は、第１の実施形態に係る通信部１０３における処理の流れを示すフローチャートである。
【００２８】
プロセッサ１０８は、スレッド（ｔｈｒｅａｄ）を実行する複数のコア１０６が通信ネットワーク１０７を介して情報をやり取りする構成を有する。コア１０６は、本実施形態に係るリストベクトル処理装置１０１を有する。リストベクトル処理装置１０１は、ギャザ処理部１０２と、通信部１０３と、アクセス情報演算部１０４と、スキャタ処理部１０５とを有する。
【００２９】
以下の説明においては、プログラム１が並列化されており、第ｋ（ただし、１≦ｋ≦Ｋ）コア１０６は、それぞれ、配列Ａの第Ｎ×（ｋ−１）＋１乃至Ｎ×ｋ要素に関する更新処理を実施するとする。第ｋコアが行う処理を、第ｋリストベクトル処理と表し、第ｋコアが有するリストベクトル処理装置１０１を、第ｋリストベクトル処理装置と表す。
【００３０】
その場合、第ｋリストベクトル処理は、プログラム２のように表すことができる。
【００３１】
Ｄｏ  ｉ＝Ｎ×（ｋ−１）＋１，Ｎ×ｋ  Ｓ（Ａ（ｉ））＝Ｓ（Ａ（ｉ））＋Ｘ（ｉ）・・・（プログラム２）、
プログラム２は、配列Ｓの要素のうち、リストベクトルＡの第（Ｎ×（ｋ−１）＋１）乃至（Ｎ×ｋ）要素が指し示す要素の値を更新及び参照する処理である。
【００３２】
ただし、第ｋ（ただし、１≦ｋ≦Ｋ）コア１０６が処理する範囲は、必ずしも、上述した例のように連続である必要はなく、不連続であっても良い。また、各コア１０６が、必ずしも、均等な要素数を処理する必要はない。並列化する手法は、既に様々な方法が知られている。そのため、本発明の各実施形態においては説明を省略する。
【００３３】
さらに、Ｋの値は、必ずしも、プロセッサ１０８が有するコア１０６の個数と一致していなくとも良い。
【００３４】
すなわち、本実施形態に係るリストベクトル処理装置１０１が行う処理は、上述した例に限定されない。以下の各実施形態においても同様である。
【００３５】
配列Ｓは、所定の分割方法に従って、Ｍ（ただし、Ｍは正の整数）個の小領域に分割されているとする。本実施形態に係るアクセス情報は、配列Ｓにおける各小領域が参照されるか否かを１と０とに関連付けて表す情報である。その場合、アクセス情報の第ｍビットの値が１であることは、配列Ｓにおける第ｍ小領域が参照される状態を表す。また、アクセス情報の第ｍビットの値が０であることは、配列Ｓにおける第ｍ小領域が参照されない状態を表す。
【００３６】
図４を参照しながら、上記のアクセス情報について具体的に説明する。図４は、第１の実施形態に係るアクセス情報を概念的に表す図である。
【００３７】
配列Ｓは、アドレスが０ｘ１００００００００乃至０ｘ１０００ＦＦＦＦＦ（ただし「０ｘ」は１６進数であることを表す）における５１２メガバイト（「ＭＢ」と表す）に記憶されており、相互に等しい大きさを有する５１２個の小領域に分割されているとする。その場合、各小領域の大きさは、１ＭＢである。
【００３８】
上述した例の場合、例えば、リストベクトルが記憶する「０ｘ１０００００００８」は、第１小領域における１つのアドレスである。従って、第１小領域が参照されるため、アクセス情報の第１ビットの値は１である。同様に、「０ｘ１００２００００８」が第３小領域における１つのアドレスであるため、アクセス情報の第３ビットの値は１である。さらに、同様に、「０ｘ１０００００８００」が第１小領域における１つのアドレスであるため、アクセス情報の第１ビットの値は１である。以下、同様である。
【００３９】
上述した例においては、アクセス情報を第ｍビットの値に関連付けしたが、アクセス情報を配列として第ｍ要素に関連付けしても良い。アクセス情報を、配列を用いて表す場合、必ずしも、参照されるか否かに関する情報を０と１とに関連付ける必要はなく、他の値に関連付けてもよい。すなわち、アクセス情報に関する態様は、上述した例に限定されない。以下の各実施形態においても同様である。
【００４０】
所定の分割方法には、例えば、ある大きさで配列Ｓを分割する方法や、配列ＳをＫ等分する方法等がある。所定の分割方法は、上述した方法に限定されない。以下の各実施形態においても同様である。
【００４１】
一方、所定の分割方法に応じて、配列Ｓの第ｊ（ただし、１≦ｊ≦Ｍ）要素から、アクセス情報の第ｐ要素への対応関係が決まる。所定の分割方法に応じて決まる対応関係を表す情報を、所定の対応情報と表す。例えば、所定の対応情報は、配列に保存しても良い。また、所定の分割方法が、配列ＳをＫ等分する方法であれば、所定の対応情報は、（ｉ―１）÷Ｋ＋１（ただし、１≦ｊ≦Ｍ、（ｉ―１）÷Ｋの値は小数以下を切り捨てた値とする）として算出してもよい。
【００４２】
所定の分割方法と同様に、所定の対応情報は、上述した例に限定されない。
【００４３】
次に、第ｋリストベクトル処理装置１０１が行う処理について説明する。
【００４４】
第ｋリストベクトル処理装置１０１は、一般的なギャザ命令とは異なる第１ギャザ命令１０９、及び、一般的なスキャタ命令とは異なる第１スキャタ命令１１０に応じて処理を開始する。第１ギャザ命令１０９は、記憶装置から読み取る記憶領域を指し示すアドレスを記憶するリストベクトルに従い、複数のコアのうち、自コアのみがアクセスする記憶領域における値をレジスタに読み取る処理と、自コアと他コアとがともにアクセスする記憶領域であるか否かを表す参照アクセス情報を作成する処理とを指示する命令である。一方、第１スキャタ命令１１０は、レジスタが記憶する値を、記憶装置におけるリストベクトルが指し示す記憶領域のうち、前記自情報処理装置のみがアクセスする記憶領域に保存する命令である。
【００４５】
まず、第ｋ（ただし、１≦ｋ≦Ｋ）リストベクトル処理装置１０１におけるギャザ処理部１０２は、第１ギャザ命令１０９を受信する処理に応じて、アクセス情報における値を０に初期化する（ステップＳ２０１）。次に、ギャザ処理部１０２は、リストベクトルＡ（ｉ）（ただし、Ｎ×（ｋ−１）＋１≦ｉ≦Ｎ×ｋ）の値を記憶するレジスタから該値を読み取る（ステップＳ２０２）。次に、ギャザ処理部１０２は、所定の対応情報に応じて、Ａ（ｉ）の値に関連付けされた小領域の番号を決める（ステップＳ２０４）。例えば、該小領域の番号が、ｐであるとする。次に、ギャザ処理部１０２は、アクセス情報における第ｐビットの値を１に設定する（ステップＳ２０５）。
【００４６】
ギャザ処理部１０２は、リストベクトルＡの第Ｎ×（ｋ−１）＋１乃至Ｎ×ｋ要素について、ステップＳ２０４及びステップＳ２０５における処理を繰り返す（ステップＳ２０３）。
【００４７】
ギャザ処理部１０２は、上述したステップＳ２０４及びステップＳ２０５における処理とともに、主記憶装置から配列Ｓの第Ａ（ｉ）（ただし、Ｎ×（ｋ−１）＋１≦ｉ≦Ｎ×ｋ）要素を、レジスタに読み取る（ステップＳ２０６）。
【００４８】
次に、第ｋリストベクトル処理装置１０１における通信部１０３は、通信部１０３が処理を行うか否かを表す指示情報１１１を読み取る（ステップＳ３０１）。指示情報１１１が通信部１０３における処理を指示する場合（ステップＳ３０２にてＹＥＳと判定）、第ｋリストベクトル処理装置１０１における通信部１０３は、記憶装置（不図示）にギャザ処理部１０２が作成するアクセス情報を保存する（ステップＳ３０３）とともに、通信ネットワーク１０７を介して第ｑ（ただし、１≦ｑ≦Ｋかつｑ≠ｋ）リストベクトル処理装置１０１に該アクセス情報を送信する（ステップＳ３０４）。
【００４９】
次に、第ｋリストベクトル処理装置１０１における通信部１０３は、第ｑ（ただし、１≦ｑ≦Ｋかつｑ≠ｋ）リストベクトル処理装置１０１が送信するアクセス情報を受信し（ステップＳ３０５）、受信したアクセス情報を記憶装置（不図示）に該アクセス情報を保存する（ステップＳ３０６）。
【００５０】
指示情報１１１が通信部１０３における処理を指示しない場合（ステップＳ３０２にてＮＯと判定）、第ｋリストベクトル処理装置１０１における通信部１０３は、上述した処理を行わない。
【００５１】
以下の説明においては、第ｋリストベクトル処理装置１０１におけるギャザ処理部１０２が作成するアクセス情報を自アクセス情報と表す。さらに、第ｑ（ただし、１≦ｑ≦Ｋかつｑ≠ｋ）リストベクトル処理装置１０１から受信するアクセス情報を他アクセス情報と表す。
【００５２】
次に、本実施形態に係るアクセス情報演算部１０４が行う処理について説明する。
【００５３】
アクセス情報演算部１０４は、自アクセス情報と他アクセス情報とに基づいて、所定のマスク生成方法に従い、自コア１０６及び他コア１０６がアクセスする参照小領域を算出する。スキャタ処理部１０５は、複数の小領域における各小領域が、参照小領域であるか否かを表す参照アクセス情報を作成し、作成した参照アクセス情報を記憶装置（不図示）に記憶させても良い。
【００５４】
また、アクセス情報演算部１０４は、参照小領域に基づいて、自コア１０６のみがアクセスする小領域を算出し、算出した小領域を独立小領域としてもよい。さらに、スキャタ処理部１０５は、複数の小領域における各小領域が、独立小領域であるか否かを表す独立アクセス情報を作成し、作成した独立アクセス情報を記憶装置（不図示）に記憶させても良い。
【００５５】
所定のマスク生成方法としては、例えば、複数の他アクセス情報をビットごとに論理和演算を実施し、算出したアクセス情報と自アクセス情報とをビットごとに論理積演算を実施する方法がある。その場合、複数の他アクセス情報間において論理和演算を適用することにより、他コア１０６がアクセスするアクセス情報を算出することができる。
【００５６】
さらに、算出したアクセス情報と自アクセス情報との間において論理積演算を適用することにより、上述した自コア１０６及び他コア１０６がともにアクセスするアクセス情報を算出することができる。すなわち、算出したアクセス情報は、上述した参照小領域であるか否かを表す。
【００５７】
また、所定のマスク生成方法は、自アクセス情報と他アクセス情報とにおいて、自コア１０６及び他コア１０６が参照するビットを探すプログラムに従って処理しても良い。すなわち、所定のマスク生成方法は、上述した例に限定されない。
【００５８】
また、例えば、独立小領域は、他アクセス情報のビットごとの否定を算出し、算出した値と自アクセス情報との論理和演算を実施することにより算出することができる。
【００５９】
次に、スキャタ処理部１０５は、第１スキャタ命令１１０を受信する処理に応じて、参照アクセス情報に基づき、自コア１０６が処理する配列Ｓのうち、自コア１０６のみがアクセスする要素を、レジスタが記憶する値を主記憶装置に保存する。
【００６０】
特許文献３が開示するコンパイラにおいて、ユーザは、リストベクトルが参照する配列の要素ごとに分割を決定し、該分割をコンパイラに指示する必要がある。該要素ごとに分割を決定する処理が多大な計算時間を必要とするため、該コンパイラは、リストベクトルを効率的に処理することができない。
【００６１】
本実施形態に係るリストベクトル処理装置１０１は、リストベクトルが参照する配列を小領域に分割し、分割した小領域に関する参照関係を調べる構成を有する。小領域の数が上述した要素数に比べ少ないため、分割を算出する時間は、上述したような一般的な並列化方法より短縮される。
【００６２】
一方、コンパイラは、リストベクトルを処理するプログラムに対し、本実施形態に係る第１スキャタ命令１１０及び第１ギャザ命令１０９を含むオブジェクトプログラムを出力する。第１スキャタ命令１１０及び第１ギャザ命令１０９は、算出する自コア１０６のみが参照する小領域を算出する処理をプロセッサ１０８に指示する。自コア１０６のみが参照する小領域におけるデータは、相互に参照関係を有していないため、各コア１０６は、並列に処理することができる。並列に処理することにより、更に、処理時間は短縮する。
【００６３】
すなわち、本実施形態に係るリストベクトル処理装置１０１によれば、リストベクトル等の間接参照処理を高速に実施することができる。
【００６４】
尚、ギャザ処理部１０２、通信部１０３、アクセス情報演算部１０４、及び、スキャタ処理部１０５が、異なる処理部であるとして記載したが、制御部が、ギャザ処理部１０２、通信部１０３、アクセス情報演算部１０４、及び、スキャタ処理部１０５における処理を行っても良い。また、各コア１０６は、同一の構成を有すると仮定したが、必ずしも、同一の構成を有する必要はない。以下の各実施形態についても同様である。
【００６５】
＜第２の実施形態＞
次に、上述した第１の実施形態を基本とする第２の実施形態について説明する。
【００６６】
以下の説明においては、本実施形態に係る特徴的な部分を中心に説明すると共に、上述した第１の実施形態と同様な構成については、同一の参照番号を付すことにより、重複する説明を省略する。
【００６７】
図５乃至図７を参照しながら、本発明の第２の実施形態に係るリストベクトル処理装置５０３が有する構成と、リストベクトル処理装置５０３が行う処理とについて説明する。図５は、本発明の第２の実施形態に係るリストベクトル処理装置５０３が有する構成を示すブロック図である。図６は、本発明の第２の実施形態に係る第２ギャザ処理部５０１における処理の流れを示すフローチャートである。図７は、本発明の第２の実施形態に係る第２スキャタ処理部５０２における処理の流れを示すフローチャートである。
【００６８】
図５を参照すると、プロセッサ５０５における各コア５０４は、リストベクトル処理装置５０３を有する。更に、リストベクトル処理装置５０３は、ギャザ処理部１０２と、通信部１０３と、スキャタ処理部１０５と、第２ギャザ処理部５０１と、第２スキャタ処理部５０２とを有する。
【００６９】
第２ギャザ命令５０６及び第２スキャタ命令５０７は、リストベクトル処理装置５０３が第１スキャタ命令を処理した後に、起動する命令である。
【００７０】
第２ギャザ命令５０６は、リストベクトルが指し示す記憶領域のうち、スキャタ処理部１０５が第１スキャタ命令に応じて参照小領域における値をレジスタに保存する命令である。
【００７１】
第２スキャタ命令５０７は、レジスタが記憶する値を、リストベクトルが指し示す記憶領域のうち、スキャタ処理部１０５が第１スキャタ命令に応じて、参照小領域に保存する命令である。
【００７２】
第２ギャザ処理部５０１は、第２ギャザ命令５０６を受信する処理に応じて処理を開始する。まず、第２ギャザ処理部５０１は、所定の分割方法に基づいて、リストベクトルＡにおけるＡ（ｉ）の値に関連付けされた小領域の番号を決める（ステップＳ６０１）。次に、第２ギャザ処理部５０１は、例えば、記憶装置（不図示）における参照アクセス情報を参照することにより、算出した小領域の番号が、参照小領域であるか否かを判定する（ステップＳ６０２）。スキャタ処理部１０５が独立アクセス情報を作成している場合には、第２ギャザ処理部５０１は、記憶装置（不図示）における独立アクセス情報を参照することにより、該判定を行っても良い。
【００７３】
第２ギャザ処理部５０１は、算出した小領域が参照小領域である場合に（ステップＳ６０２にてＹＥＳと判定）、リストベクトルに基づいて主記憶装置からレジスタに値を読み取る（ステップＳ６０３）。
【００７４】
第２ギャザ処理部５０１は、算出した小領域が独立小領域である場合に（ステップＳ６０２にてＮＯと判定）、上述した処理を行わない。
【００７５】
一方、第２スキャタ処理部５０２は、第２スキャタ命令５０７を受信するのに応じて処理を開始する。
【００７６】
まず、第２スキャタ処理部５０２は、レジスタからリストベクトルの値（すなわち、アドレス）を読み取り、所定の対応情報に基づいて、該アドレスを含む小領域を特定する（ステップＳ７０１）。例えば、図に示す例において、リストベクトルの値が「０ｘ１０００００００８」である場合、第２スキャタ処理部５０２は、第１小領域であることを特定する。
【００７７】
次に、第２スキャタ処理部５０２は、参照アクセス情報を参照することにより、該特定した小領域が参照小領域であるか否かを判定する（ステップＳ７０２）。例えば、上述した例において、第２スキャタ処理部５０２は、参照アクセス情報の第１ビットの値が１である場合に、該特定した小領域が参照小領域であると判定する。
【００７８】
特定した小領域が参照小領域である場合に（ステップＳ７０２にてＹＥＳと判定）、第２スキャタ処理部５０２は、レジスタが記憶する値を、リストベクトルに基づいて記憶装置に保存する（ステップＳ７０３）。特定した小領域が参照小領域である場合に（ステップＳ７０２にてＮＯと判定）、第２スキャタ処理部５０２は、上述した処理を行わない。
【００７９】
本発明の第２の実施形態は、本発明の第１の実施形態と同様の構成を有するため、リストベクトル等の間接参照処理を高速に実施することができる。その理由は、上述した理由と同様である。
【００８０】
さらに、本実施形態は、第２ギャザ命令５０６及び第２スキャタ命令５０７を処理可能である。第２ギャザ命令５０６及び第２スキャタ命令５０７が、参照小領域における処理を可能にする命令であるため、ユーザは、リストベクトル処理装置５０３が有する構成を意識する必要がなくなる。その結果、ユーザは、容易に高速なプログラムを作成することができる。
【００８１】
＜第３の実施形態＞
次に、上述した第１の実施形態を基本とする第３の実施形態について説明する。
【００８２】
以下の説明においては、本実施形態に係る特徴的な部分を中心に説明すると共に、上述した第１の実施形態と同様な構成については、同一の参照番号を付すことにより、重複する説明を省略する。
【００８３】
図８乃至図１１を参照しながら、本発明の第３の実施形態に係るリストベクトル処理装置が有する構成と、リストベクトル処理装置が行う処理とについて説明する。図８は、本発明の第３の実施形態に係るアクセス情報演算部８０１が有する構成を示すブロック図である。図９は、本発明の第３の実施形態に係るアクセス制御部８０４における処理の流れを示すフローチャートである。図１０は、本発明の第３の実施形態に係る論理和演算部８０２における処理の流れを示すフローチャートである。図１１は、本発明の第３の実施形態に係る論理積演算部８０３における処理の流れを示すフローチャートである。
【００８４】
アクセス情報演算部８０１は、ビットごとに論理和演算を実施する論理和演算部８０２と、ビットごとに論理積演算を実施する論理積演算部８０３と、アクセス制御部８０４とを有する。
【００８５】
記憶部（不図示）は、アクセス情報を記憶可能なアクセス情報キューと、アクセス情報を記憶可能なアクセス情報レジスタと、同期情報を記憶可能な同期カウンタと、スレッドのスレッド番号を記憶可能なスレッド格納レジスタとを有する。
【００８６】
図９乃至図１２を参照しながら、通信部（不図示、例えば、図１）及びアクセス情報演算部８０１おける処理について説明する。図１２は、本実施形態に係るリストベクトル処理装置が行う処理のタイミングを表すシーケンス図である。図１２は、左から右に行くに従い、時刻が進むことを表す。
【００８７】
各コアにおける通信部は、それぞれ、第１ギャザ部（不図示、例えば、図１）が作成したアクセス情報と、自コアが処理するスレッドのスレッド番号とを、他コアに送信する（ステップＳ９０１）。第２スレッドを処理するコアにおける通信部が、第０スレッド、第１スレッドの順に、アクセス情報が読み出す（図１２における「スレッド番号」欄）例を用いて説明する。
【００８８】
以下の例において、スレッドは、該スレッドを起動する順序に関連するスレッド番号に関連付けされているとする。また、スレッド番号が小さいスレッドは、より大きいスレッド番号を有するスレッドよりも優先して処理されるものとする。
【００８９】
通信部は、他コアにおける通信部が送信する「スレッドを識別するスレッド番号」と、アクセス情報と、通信ネットワークを経由して受信する（ステップＳ９０２）。次に、通信部は、受信したスレッド番号をスレッド格納レジスタに保存する（ステップＳ９０３）とともに、受信したアクセス情報をアクセス情報キューに保存する（ステップＳ９０４）。本実施形態において、アクセス情報キューは、例えば、アクセス情報を受信可能なエントリを２つ有する。
【００９０】
通信部は、自アクセス情報をアクセス情報レジスタに保存するとともに（図１２における「自コアからｂｉｔｍａｐレジスタ」欄）、自スレッドのスレッド番号（図１２における「自コアからスレッド番号」欄）をスレッド格納レジスタに保存する（図１２における「自スレッド番号格納レジスタ」欄）。さらに、通信部は、自分のスレッド番号を同期カウンタに保存する（図１２における「同期カウンタ１１７」欄）。
【００９１】
その後、アクセス情報演算部８０１は、アクセス情報キューが記憶するスレッド番号を読み出す（ステップＳ９０６）。
【００９２】
アクセス制御部８０４は、スレッド格納レジスタから読み出すスレッド番号と自分のスレッド番号とを比較する（図１２における「比較器１１３」欄、ステップＳ９０７）。次に、アクセス制御部８０４は、読み出したスレッド番号が自スレッド番号よりも小さい場合（自スレッドよりも読み出したスレッド番号に対応するスレッドの方が前に起動されている。ステップＳ９０７にてＹＥＳと判定）に、有効信号を論理和演算部８０２（図１２における「ＯＲ１１４出力」欄）と同期カウンタとに送信する（図１２における「同期カウンタ１１７」欄。ステップＳ９０８）。アクセス制御部８０４は、アクセス情報に関連付けされたスレッド番号が自スレッド番号よりも大きい場合（ステップＳ９０７にてＮＯと判定）に、該有効信号を送信しない。
【００９３】
アクセス制御部８０４は、スレッド格納レジスタが記憶するスレッド番号について上述した処理を完了する（ステップＳ９０５にてＹＥＳと判定）のに応じて、論理積演算部８０３に演算信号を送る（ステップＳ９０９）。
【００９４】
図１６を参照しながら、論理和演算部８０２及び論理積演算部８０３における処理について説明する。図１６は、アクセス情報を算出する過程を模式的に表す図である。
【００９５】
論理和演算部８０２は、アクセス制御部８０４からの有効信号に応じて、アクセス情報レジスタからアクセス情報に関する値（ステップＳ１００１）、及び、アクセス情報キューから他アクセス情報を読み出す（ステップＳ１００２）。例えば、論理和演算部８０２は、ステップＳ１００１において、図１６の第１列に示す情報を読み出し、ステップＳ１００２において、図１６の第２列及び第３列に示す情報を読み出す。
【００９６】
次に、論理和演算部８０２は、アクセス情報レジスタから読み出した値と他アクセス情報との論理和を算出し（図１２における「ＯＲ１１４出力」欄、ステップＳ１００３）、算出した値をアクセス情報レジスタに保存する（図１２における「レジスタ１１５」欄、ステップＳ１００４）。上述した例において、論理和演算部８０２は、図１６の第２列及び第３列に示す情報の論理和を算出し、図１６の第４列に示す情報を算出する。
【００９７】
アクセス制御部８０４は、有効信号を送信する処理に応じて、同期カウンタから値を読み出し１を減算する（図１２における「同期カウンタ１１７」欄）。アクセス制御部８０４は、減算した結果を同期カウンタに保存する。アクセス制御部８０４は、同期カウンタが記憶する値に応じて、演算信号を送信する。
【００９８】
上述した例の場合、同期カウンタが保存する値は、他アクセス情報を参照する回数を表す。該値が１の場合には、論理和演算部８０２が参照する必要がある他アクセス情報を全て参照した状態を表す。
【００９９】
論理積演算部８０３は、アクセス制御部８０４からの演算信号に応じて、アクセス情報レジスタから値を読み出し（ステップＳ１１０１）、読み出した値と自アクセス情報との論理積演算をビットごとに実施する（図１２における「論理積演算部８０３」欄、ステップＳ１１０２）。
【０１００】
例えば、論理積演算部８０３は、図１６の第４列に示す情報と、図１６の第５列に示す情報との論理積演算をビットごとに実施し、該演算した結果（図１６の第６列に示す情報）を算出する。
【０１０１】
その後、論理積演算部８０３は、算出した値をアクセス情報レジスタに送信する。その後、アクセス制御部８０４は、同期終了信号を同期制御部（不図示）に送信する。
【０１０２】
同期制御部（不図示）は、同期制御命令及び同期終了信号を受信する場合に、該同期命令に後続する命令を実行する。同期制御部（不図示）は、同期制御命令または同期終了信号を受信しない場合に、上述した処理を行わない。
【０１０３】
さらに、より具体的に、プログラム３を例として、本実施形態に係るリストベクトル処理装置の処理について説明する。
【０１０４】
Ｄｏ  ｉ＝１，７６８  Ｓ（Ａ（ｉ））＝Ｓ（Ａ（ｉ））＋Ｘ・・・（プログラム３）、
プログラム３は、ループカウンタｉに応じて変化するＡ（ｉ）の値をリストベクトルとして、Ｓ（Ａ（ｉ））の値をメモリから読み出し、Ｓ（Ａ（ｉ））の値に１を加えた後、元のＳ（Ａ（ｉ））のメモリアドレスに書き戻す動作を、７６８回繰り返す処理を指示する。
【０１０５】
配列Ｓにおける１つの要素は、８バイト長の大きさを有するとする。さらに、主記憶装置は、「アドレス０ｘ１００００００００」から５１２ＭＢ分の領域に、配列Ｓ記憶しているとする。また、各コアが処理するスレッドは、該スレッドが起動された順序に関連するスレッド番号に関連付けされているとする。
【０１０６】
３つのスレッドが、プログラム３を並列に実行する一例について説明する。図１３は、コンパイラがプログラム３に対して出力するオブジェクトプログラムの一例を概念的に表す図である。３つのスレッドは、それぞれ、図１３に示すオブジェクトプログラムを実行する。
【０１０７】
まず、該オブジェクトプログラムについて説明する。
【０１０８】
各スレッドは、該オブジェクトプログラムを実行する前に、スカラレジスタ（ｓｃａｌａｒ  ｒｅｇｉｓｔｅｒ、以降「ＳＲ」と表す）１０に、自スレッドが処理する要素番号のうち最小の番号をそれぞれ保存する。
【０１０９】
例えば、第１スレッドは、リストベクトルＡの第１乃至２５６要素に関する処理、第２スレッドは、リストベクトルＡの第２５７乃至５１２要素に関する処理、第３スレッドは、リストベクトルＡの第５１３乃至７６８要素に関する処理を行うとする。
【０１１０】
この場合、第１スレッドは、処理を開始する先頭要素として、ＳＲ１０に１を保存する。同様に、第１スレッドは、先頭要素として、ＳＲ１０に２５７を保存する。さらに、第２スレッドは、ＳＲ１０に５１３を保存する。
【０１１１】
図１３が示すプログラムは、命令１において、スレッドに、リストベクトルＡを主記憶装置からレジスタにベクトルロード（以降、「ＶＬＤ」）させる命令を指示する。各スレッドは、該ベクトルロード命令に応じて、リストベクトルＡの中から、ＳＲ１０が記憶する先頭要素からの２５６個分の要素を主記憶装置から、ベクトルレジスタ（以降、「ＶＲ」と略記する）０へ読み出す。
【０１１２】
この段階において、ＶＲ０は、それぞれ、リストベクトルＡの２５６個の要素を記憶する。すなわち、第１スレッドは、リストベクトルＡの第１乃至２５６要素を、第２スレッドは、リストベクトルＡの第２５７乃至５１２要素を、そして、第３スレッドは、リストベクトルＡの第５１３乃至７６８要素を、それぞれ、ＶＲ０に保存する。
【０１１３】
例えば、第１スレッドは、ＶＲ０に、図１４に示すようなリストベクトルを保存する。図１４は、ＶＲ０が記憶する値の一例を概念的に表す図である。
【０１１４】
次に、図１３における命令２に示すベクトル加算（「ＶＡＤ」）命令は、ＶＲ０が記憶する値をそれぞれ８倍し、その後、配列Ｓを指し示す先頭アドレスである値０ｘ１００００００００をそれぞれ加え、算出した値（例えば、図１５）をＶＲ１に格納させる命令である。各スレッドは、命令２に従い、配列Ｓを指し示すアドレスを生成する。図１５は、ＶＲ１が記憶するアドレスの一例を概念的に表す図である。
【０１１５】
図１３における命令３に示す第１ギャザ（「ＶＧＴ−ＨＢ」）命令は、上述したような処理を指示する命令である。ギャザ処理部は、第１ギャザ命令を受信する処理に応じて、主記憶装置において、ＶＲ１が記憶する値が指し示す記憶領域から値を読み出し、読み出した値をＶＲ２に保存する。それとともに、ギャザ処理部は、オペランドにおける先頭アドレスである０ｘ１００００００００と、配列のサイズを指定する値（すなわち、この例では、２９＝２９桁のビット＝５１２ＭＢ）とを用いて、アクセス情報を更新する。
【０１１６】
通信部は、ギャザ処理部が自アクセス情報を更新する処理に応じて、更新した自アクセス情報を記憶装置に保存する。それとともに、通信部は、該更新した自アクセス情報と、自コアが処理するスレッド番号とを、通信ネットワークを介して、他コアに送信（ブロードキャスト）する。
【０１１７】
通信部（不図示）は、他コア内の通信部が送信したアクセス情報とスレッド番号とを受信し、受信したアクセス情報とスレッド番号とをアクセス情報演算部８０１に送信する。さらに、通信部（不図示）は、受信したアクセス情報とスレッド番号とを、アクセス情報キューに保存する。
【０１１８】
命令４（図１３）におけるベクトル乗算命令（「ＶＦＡＤ」）は、ＶＲ２が記憶する値に、Ｘを加算し、算出した結果をＶＲ３に書き込む命令である。
【０１１９】
命令５（図１３）における同期命令（「ＢＳＡＮＤ」）は、アクセス情報演算部８０１が独立小領域を算出するまで、後続の処理を停止する同期命令である。同期命令を処理する同期制御部（不図示）は、アクセス制御部８０４が送信する同期終了信号に応じて、後続の処理を停止するか否かを判定する。すなわち、同期制御部（不図示）は、アクセス制御部８０４から該同期終了信号を受信した場合には、後続の処理を実施する信号を送信する。同期制御部は、アクセス制御部８０４から該同期終了信号を受信しない場合には、後続の処理を実施しない信号を送信する。
【０１２０】
命令６（図１３）における第１スキャタ（「ＶＳＣ−ＨＭ」）命令は、レジスタが記憶する値を、主記憶装置（不図示）において、リストベクトルが指し示す記憶領域のうち独立小領域に保存する命令である。
【０１２１】
スキャタ処理部（不図示）は、リストベクトルから算出したアドレスの上位ビットを、例えば、比較レジスタに格納する。上述した例の場合、この処理は、アドレスが指し示す小領域を算出する処理である。次に、スキャタ処理部（不図示）は、比較レジスタが記憶する値と、算出したアドレス情報とを比較する。該２つの値が一致する場合、該アドレスは、参照小領域にあるデータを指し示す。スキャタ処理部（不図示）は、該２つの値が一致しない場合、該アドレスが指し示す領域に、レジスタが記憶する値を保存する。一方、スキャタ処理部（不図示）は、該２つの値が一致する場合、レジスタの値を、主記憶装置（不図示）に保存しない。
【０１２２】
例えば、上述した処理は、シフト演算を用いることにより実現することができる。上述した例の場合、「ＶＧＴ−ＨＢ」命令におけるオペランドが２９であるため、配列Ｓのサイズは、５１２ＭＢ（５１２ＭＢ＝２９桁のビット）である。ギャザ処理部（不図示）は、配列Ｓのサイズ２９から９を引くことにより、アクセス情報の大きさを算出する。次に、ギャザ処理部（不図示）は、算出した値２０を、ビットを上位ビット側にシフトするシフタに送ることにより、２進値「１１１１１１１１１ｂ」を２０だけ上位ビット側にシフトする。その後、ギャザ処理部（不図示）は、シフトしたビットに相当する下位ビットに０を書き込む。上述した処理により、ギャザ処理部は、領域を５１２分割した単位において、算出したアドレスが参照小領域を指し示すか否かを判定する。
【０１２３】
本発明の第３の実施形態は、本発明の第１の実施形態と同様の構成を有するため、リストベクトル等の間接参照処理を高速に実施することができる。その理由は、上述した理由と同様である。
【０１２４】
さらに、本実施形態は、論理和演算部８０２及び論理積演算部８０３等を備える。従って、本実施形態によれば、参照アクセス情報を、論理和演算及び論理積演算により少ない演算回数で算出する。その結果、本実施形態によれば、リストベクトル等の間接参照処理をさらに高速に実施することができる。
【０１２５】
尚、プログラム３を例として本実施形態の動作を説明したが、第１配列が第２配列における要素を指し示すリストベクトルに関する処理にも適用できる。本実施形態は、上述した例に限定されない。
【０１２６】
さらに、上述した例においては、全てのコアが上述した処理を実施するとしたが、プロセッサにおける一部のコアのみが上述した処理を実施しても良い。
【０１２７】
なお、本発明は上述した実施形態に限定されるものではなく、その実施に際して様々な変形が可能である。
【０１２８】
例えば、上述した各実施形態の一部又は全部は、以下の付記のようにも記載されうるが、以下の付記に限定されるものではない。
【０１２９】
（付記１）
記憶装置から読み取る記憶領域を指し示すアドレスを記憶するリストベクトルに従い、複数の情報処理装置のうち、自情報処理装置のみがアクセスする記憶領域における値をレジスタに読み取る処理と、前記自情報処理装置と他情報処理装置とがともにアクセスする記憶領域であるか否かを表す参照アクセス情報を作成する処理とを指示する第１ギャザ命令に応じて、前記リストベクトルに従いアクセスする記憶領域を所定の分割方法に従って、論理的に複数の小領域に分割し、分割したそれぞれの前記小領域にアクセスするか否かを表すアクセス情報を作成するとともに、前記自情報処理装置が前記リストベクトルに従いアクセスする複数のアドレスから、前記所定の分割方法に応じた所定の対応情報に基づいて、特定の小領域を算出し、前記アクセス情報において、前記特定の小領域に関連付けされた値を、アクセスすることを表す値に更新するとともに、前記記憶装置において前記リストベクトルが指し示す記憶領域のうち、前記自情報処理装置のみがアクセスする記憶領域における値をレジスタに読み取るギャザ処理部と、
前記自情報処理装置が更新した前記アクセス情報を自アクセス情報として前記他情報処理装置に送信し、前記他情報処理装置が送信した前記アクセス情報を、他アクセス情報として受信する通信部と、
前記自アクセス情報と、前記他アクセス情報とに基づいて、所定の算出方法に従い、前記自情報処理装置と前記他情報処理装置とがともにアクセスする前記小領域を算出するとともに、該算出した小領域を参照小領域とし、前記複数の小領域が前記参照小領域であるか否かを表す前記アクセス情報を算出し、該算出した前記アクセス情報を参照アクセス情報とするアクセス情報演算部と、
レジスタが記憶する値を、前記記憶装置における前記リストベクトルが指し示す記憶領域のうち、前記自情報処理装置のみがアクセスする記憶領域に保存する命令である第１スキャタ命令に応じて、前記レジスタが記憶する値を、前記参照アクセス情報に基づき、前記リストベクトルが指し示す記憶領域のうち、前記参照小領域ではない記憶領域に保存するスキャタ処理部と
を備えるリストベクトル処理装置。
【０１３０】
（付記２）
前記記憶装置において、前記リストベクトルが指し示す記憶領域のうち、前記参照小領域における値を前記レジスタに読み取る第２ギャザ命令に応じて、前記参照アクセス情報に基づき、前記記憶装置において前記リストベクトルが指し示す記憶領域のうち、前記参照小領域における値を、前記レジスタに保存する第２ギャザ処理部と、
前記レジスタが記憶する値を、前記リストベクトルが指し示す記憶領域のうち、前記参照小領域に保存する命令である第２スキャタ命令に応じて、前記参照アクセス情報に基づき、前記レジスタが記憶する値を、前記リストベクトルが指し示す記憶領域のうち前記参照小領域に保存する第２スキャタ処理部と
を更に備える
付記１に記載のリストベクトル処理装置。
【０１３１】
（付記３）
前記アクセス情報演算部は、
ビットごとに論理和を算出する論理和演算部と、ビットごとに論理積を算出する論理積演算部と、アクセス制御部と
を備え、
スレッドは、該スレッドを起動する順序に関連するスレッド番号に関連付けされており、
前記通信部は、前記自アクセス情報とともに、前記自情報処理装置が処理する前記スレッドの前記スレッド番号を、前記他情報処理装置に送信し、さらに、前記他アクセス情報及び前記スレッド番号を受信し、受信した前記他アクセス情報をアクセス情報キューに保存するとともに、受信した前記スレッド番号をスレッド格納レジスタに保存し、
前記アクセス制御部は、前記スレッド格納レジスタが記憶する前記スレッド番号と、前記自情報処理装置が処理する前記スレッドの前記スレッド番号とを順次比較し、前記自情報処理装置が処理する前記スレッドの前記スレッド番号が、前記スレッド格納レジスタが記憶する前記スレッド番号よりも小さい場合に、前記論理和演算部に有効信号を送信し、
前記論理和演算部は、前記アクセス制御部が送信する前記有効信号に応じて、アクセス情報レジスタが記憶する値、及び、前記アクセス情報キューから前記他アクセス情報を読み出し、読み出した前記値と、読み出した前記他アクセス情報との論理和をビットごとに算出し、該算出した値を前記アクセス情報レジスタに保存し、
前記アクセス制御部は、前記スレッド格納レジスタが記憶する前記スレッド番号に関する処理が終了するに応じて、前記論理積演算部に演算信号を送信し、
前記論理積演算部は、前記アクセス制御部が送信する前記演算信号に応じて、前記アクセス情報レジスタから値を読み出し、読み出した該値と、前記自アクセス情報との論理積をビットごとに算出し、該算出した値に基づいて、前記参照アクセス情報を算出する
付記１または付記２に記載のリストベクトル処理装置。
【０１３２】
（付記４）
前記アクセス制御部は、前記論理積演算部が前記参照小領域を算出する処理に応じて、前記参照小領域を算出する処理が完了したことを表す同期信号を送信する
付記３に記載のリストベクトル処理装置
（付記５）
前記アクセス情報演算部は、前記参照アクセス情報に基づいて、さらに、前記記憶装置において、前記自情報処理装置のみがアクセスする前記小領域を独立小領域として算出し、前記複数の小領域が前記独立小領域であるか否かを表す独立アクセス情報を生成し、
前記スキャタ処理部は、前記独立アクセス情報に基づいて、前記レジスタが記憶する値を、前記リストベクトルが指し示す記憶領域のうち、前記独立小領域に保存する
付記２乃至付記４のいずれかに記載のリストベクトル処理装置。
【０１３３】
（付記６）
前記所定の分割方法は、前記リストベクトルが指し示す記憶領域を、所定の単位にて分割する方法である
付記１乃至付記５のいずれかに記載のリストベクトル処理装置。
【０１３４】
（付記７）
前記所定の単位は、前記リストベクトルが指し示す記憶領域の大きさを、前記情報処理装置の数で割った値とする
付記７に記載のリストベクトル処理装置。
【０１３５】
（付記８）
記憶装置から読み取る記憶領域を指し示すアドレスを記憶するリストベクトルに従い、複数の情報処理装置のうち、自情報処理装置のみがアクセスする記憶領域における値をレジスタに読み取る処理と、前記自情報処理装置と他情報処理装置とがともにアクセスする記憶領域であるか否かを表す参照アクセス情報を作成する処理とを指示する第１ギャザ命令に応じて、前記リストベクトルに従いアクセスする記憶領域を所定の分割方法に従って、論理的に複数の小領域に分割し、分割したそれぞれの前記小領域にアクセスするか否かを表すアクセス情報を作成するとともに、前記自情報処理装置が前記リストベクトルに従いアクセスする複数のアドレスから、前記所定の分割方法に応じた所定の対応情報に基づいて、特定の小領域を算出し、前記アクセス情報において、前記特定の小領域に関連付けされた値を、アクセスすることを表す値に更新するとともに、前記記憶装置において前記リストベクトルが指し示す記憶領域のうち、前記自情報処理装置のみがアクセスする記憶領域における値をレジスタに読み取り、前記自情報処理装置が更新した前記アクセス情報を自アクセス情報として前記他情報処理装置に送信し、前記他情報処理装置が送信した前記アクセス情報を、他アクセス情報として受信し、前記自アクセス情報と、前記他アクセス情報とに基づいて、所定の算出方法に従い、前記自情報処理装置と前記他情報処理装置とがともにアクセスする前記小領域を算出するとともに、該算出した小領域を参照小領域とし、前記複数の小領域が前記参照小領域であるか否かを表す前記アクセス情報を算出し、該算出した前記アクセス情報を参照アクセス情報とし、レジスタが記憶する値を、前記記憶装置における前記リストベクトルが指し示す記憶領域のうち、前記自情報処理装置のみがアクセスする記憶領域に保存する命令である第１スキャタ命令に応じて、前記レジスタが記憶する値を、前記参照アクセス情報に基づき、前記リストベクトルが指し示す記憶領域のうち、前記参照小領域ではない記憶領域に保存する
リストベクトル処理方法。
【０１３６】
（付記９）
前記第１スキャタ命令を指示するプログラム。
【０１３７】
（付記１０）
前記第１ギャザ命令を指示するプログラム。
【０１３８】
（付記１１）
前記第２スキャタ命令を指示するプログラム。
【０１３９】
（付記１２）
前記第２ギャザ命令を指示するプログラム。
【０１４０】
（付記１３）
前記第１スキャタ命令を含むオブジェクトプログラムを出力するコンパイラ。
【０１４１】
（付記１４）
前記第１ギャザ命令を含むオブジェクトプログラムを出力するコンパイラ。
【０１４２】
（付記１５）
前記第２スキャタ命令を含むオブジェクトプログラムを出力するコンパイラ。
【０１４３】
（付記１６）
前記第２ギャザ命令を含むオブジェクトプログラムを出力するコンパイラ。
【０１４４】
（付記１７）
前記第１スキャタ命令を含むオブジェクトプログラムを実行する情報処理装置。
【０１４５】
（付記１８）
前記第１ギャザ命令を含むオブジェクトプログラムを実行する情報処理装置。
【０１４６】
（付記１９）
前記第２スキャタ命令を含むオブジェクトプログラムを実行する情報処理装置。
【０１４７】
（付記２０）
前記第２ギャザ命令を含むオブジェクトプログラムを実行する情報処理装置。
【符号の説明】
【０１４８】
１０１    リストベクトル処理装置
１０２    ギャザ処理部
１０３    通信部
１０４    アクセス情報演算部
１０５    スキャタ処理部
１０６    コア
１０７    通信ネットワーク
１０８    プロセッサ
１０９    第１ギャザ命令
１１０    第１スキャタ命令
１１１    指示情報
５０１    第２ギャザ処理部
５０２    第２スキャタ処理部
５０３    リストベクトル処理装置
５０４    コア
５０５    プロセッサ
５０６    第２ギャザ命令
５０７    第２スキャタ命令
８０１    アクセス情報演算部
８０２    論理和演算部
８０３    論理積演算部
８０４    アクセス制御部
【要約】      （修正有）【課題】リストベクトル処理において、間接参照処理を高速に実施する。【解決手段】リストベクトル処理装置１０１は、記憶装置から読み取る記憶領域を指し示すアドレスを記憶するリストベクトルに従い、複数の情報処理装置のうち、自情報処理装置のみがアクセスする記憶領域における値をレジスタに読み取る処理と、前記自情報処理装置と他情報処理装置とがともにアクセスする記憶領域であるか否かを表す参照アクセス情報を作成する処理とを指示する第１ギャザ命令１０９を処理するギャザ処理部１０２と、関連情報を通信する通信部１０３と、情報処理装置がアクセスする領域を算出するアクセス情報演算部１０４と、レジスタが記憶する値を、前記記憶装置における前記リストベクトルが指し示す記憶領域のうち、前記自情報処理装置のみがアクセスする記憶領域に保存する命令である第１スキャタ命令１１０を処理するスキャタ処理部１０５とを備える。【選択図】図１【図１】
0005522283.tif 000002
【図２】
0005522283.tif 000003
【図３】
0005522283.tif 000004
【図４】
0005522283.tif 000005
【図５】
0005522283.tif 000006
【図６】
0005522283.tif 000007
【図７】
0005522283.tif 000008
【図８】
0005522283.tif 000009
【図９】
0005522283.tif 000010
【図１０】
0005522283.tif 000011
【図１１】
0005522283.tif 000012
【図１２】
0005522283.tif 000013
【図１３】
0005522283.tif 000014
【図１４】
0005522283.tif 000015
【図１５】
0005522283.tif 000016
【図１６】
0005522283.tif 000017