(57)【特許請求の範囲】
【請求項１】
複数のノード計算機によって構成され、各ノード計算機が局所的な記憶装置を有し、各ノード計算機が仮想記憶領域の番号を該記憶装置内の記憶領域の番号に変換する仮想記憶操作装置を有し、かつ同一の仮想記憶領域を該ノード計算機の間で共有する並列計算機の更新制御方法において、
各ノード計算機は、同一の仮想記憶領域を共有するノード計算機をトリー状に配列したときの親となるノード計算機の番号と、子となるノード計算機の番号と、各々の子について少なくとも子を含む子孫の数とを各ントリに含むトリードディレクトリを記憶手段上に保持し、
他のノード計算機から追加すべきノード計算機の番号を伴って該エントリの更新要求を受けたノード計算機では、各子の間で最小の子孫数を増加させるよう該エントリを更新し、該エントリのすべての子のノード計算機が存在すれば更新した該子孫数に対応するノード計算機に該エントリの更新要求を発行し、該エントリに空きの子があれば該追加すべきノード計算機の番号を設定し、
他のノード計算機からトリー状に配列したノード計算機のチェーンを張り換える要求を受けたノード計算機では、トリー状チェーンを再構成するために必要なチェーンの張り換えを行い、該他のノード計算機が子のノード計算機であれば対応する該子孫数を１減じるよう該エントリを更新し、該他のノード計算機が子でありかつ親となるノード計算機があればその親に該チェーンを張り換える要求を発行することを特徴とする並列計算機の更新制御方法。
【請求項２】
該仮想記憶領域に対応する該記憶装置内の記憶領域を割り当てるノード計算機では、該トリードディレクトリに新規のエントリを追加し、該トリー状のノード計算機の根となるノード計算機に対してノード計算機追加のための該エントリの更新要求を発行し、
該記憶装置内の記憶領域の割当解除するノード計算機では、該親および子に対して該チェーンを張り換える要求を発行することを特徴とする請求項１記載の並列計算機の更新制御方法。
【請求項３】
該ノード計算機の間で共有される大域記憶装置上に、該根となるノード計算機の番号を登録し、
該大域記憶装置を参照して根となるノード計算機に対してノード計算機追加のための該エントリの更新要求を発行することを特徴とする請求項２記載の並列計算機の更新制御方法。
【請求項４】
複数のノード計算機によって構成され、各ノード計算機が局所的な記憶装置を有し、各ノード計算機が仮想記憶領域の番号を該記憶装置内の記憶領域の番号に変換する仮想記憶操作装置を有し、かつ該ノード計算機の間で共有する同一の仮想記憶領域の更新制御を行う並列計算機において、各ノード計算機は、
同一の仮想記憶領域を共有するノード計算機をトリー状に配列したときの親となるノード計算機の番号と、子となるノード計算機の番号と、各々の子について少なくとも子を含む子孫の数とを各ントリに含むトリードディレクトリを格納する記憶手段と、
他のノード計算機から追加すべきノード計算機の番号を伴って該エントリの更新要求を受けたとき、各子の間で最小の子孫数を増加させるよう該エントリを更新し、該エントリのすべての子のノード計算機が存在すれば更新した該子孫数に対応するノード計算機に該エントリの更新要求を発行し、該エントリに空きの子があれば該追加すべきノード計算機の番号を設定する第１の処理手段と、
他のノード計算機からトリー状に配列したノード計算機のチェーンを張り換える要求を受けたとき、トリー状チェーンを再構成するために必要なチェーンの張り換えを行い、該他のノード計算機が子のノード計算機であれば対応する該子孫数を１減じるよう該エントリを更新し、該他のノード計算機が子でありかつ親となるノード計算機があればその親に該チェーンを張り換える要求を発行する第２の処理手段とを有することを特徴とする並列計算機。
【請求項５】
該第１の処理手段は、該仮想記憶領域に対応する該記憶装置内の記憶領域を割り当てるとき、該トリードディレクトリに新規のエントリを追加し、該トリー状のノード計算機の根となるノード計算機に対してノード計算機追加のための該エントリの更新要求を発行し、
該第２の処理手段は、該記憶装置内の記憶領域の割当解除するとき、該親および子に対して該チェーンを張り換える要求を発行することを特徴とする請求項４記載の並列計算機。
【請求項６】
さらに該ノード計算機の間で共有され、該根となるノード計算機の番号を保持する大域記憶装置を有し、
該第１の処理手段は、該仮想記憶領域に対応する該記憶装置内の記憶領域を割り当てるとき、さらに該大域記憶装置を参照して根となるノード計算機に対してノード計算機追加のための該エントリの更新要求を発行することを特徴とする請求項５記載の並列計算機。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、ネットワークで接続されるノード計算機間で仮想記憶領域を共有する並列計算機に係わり、特に共有する仮想記憶領域の更新制御方法に関する。
【０００２】
【従来の技術】
複数のノード計算機がネットワークを介して相互に接続される並列計算機において、仮想記憶装置を実現する方式の１つとして、並列計算機を構成する複数のノード計算機の間で単一の仮想記憶を共有する方式がある。各ノード計算機は、それぞれ仮想記憶操作装置を有し、読み取り又は書き込みの対象となる仮想記憶領域の番号を局所的な記憶装置内の実記憶領域の番号に変換する。同一の仮想記憶領域に対応する実記憶領域が複数のノード計算機に亘って分散している場合には、これらすべての実記憶領域の内容を同一に保たねばならない。すなわちこの仮想記憶領域に対して更新要求があったとき、対応するすべての実記憶領域の内容が同一になるように更新されねばならない。このように共有する仮想記憶領域に対応する局所記憶領域の内容を同一に保つ制御を一貫性制御という。
【０００３】
構成するノード計算機の数が少ない並列計算機では、一貫性制御の手段として主にブロードキャストが使用されている。すなわち仮想記憶領域の更新要求が発生したノード計算機は、ネットワークを介して他のすべてのノード計算機へ対象となる仮想記憶領域の番号と更新内容を一斉同報通信によって送信する。これを受けたノード計算機は、対応する有効な局所記憶領域があればその内容を更新する。ブロードキャストによる一貫性制御は、ノード計算機が同一の仮想記憶領域を共有しているか否かに関係なく一貫性制御のための処理が発生するため、共有に関係のないノード計算機では無駄な処理が強いられ、処理効率が悪化する。このため特に多くのノード計算機（以下ノードと略称する）を有する並列計算機では、ブロードキャストを使用しない方法が検討されている。
【０００４】
ブロードキャストを使用しない一貫性制御の方法の一つとして、フルマップディレクトリ方式と呼ばれる方式が、特開平６−１８７２３９号公報に開示されている。フルマップディレクトリ方式では、各仮想ページごとにフルマップディレクトリを設ける。フルマップディレクトリは、各ノード対応に当該仮想ページに対応する物理ページを保持するか否かを１ビットの情報で表現するビットマップを有する。仮想記憶領域の更新要求が発生したノードは、ネットワークを介してこのフルマップディレクトリを管理する大域記憶装置に通知し、大域記憶装置は通知された仮想ページに対応するフルマップディレクトリを参照して当該仮想ページに対応する物理ページを保持するノードにのみ更新通知を送信する。ネットワークが複数のノードへの同時通知を行うマルチキャスト機能をサポートしている場合には、大域記憶装置は更新通知を１回行うだけでよい。しかしマルチキャスト機能は、通知メッセージは送信するノード群を宛先として表現する必要があり、通知メッセージの宛先長が送信先のノード数に比例する。このためノード数の多い並列計算機ではマルチキャスト機能を利用することは難しい。マルチキャスト機能を使用しない場合には、大域記憶装置は関連するすべてのノード宛に逐次的に更新通知を行う必要がある。このために仮想ページの更新に必要な時間は関連するノード数に比例して増加する。また更新通知に対する確認応答がフルマップディレクトリを保持する大域記憶装置に集中するため、ネットワークの負荷の集中が発生する。さらにフルマップディレクトリのビットマップのビット数は並列計算機の総ノード数に等しく、ノード数の増加に比例して大きくなるため、台数拡張性が悪いこと、およびノード数の大きい並列計算機ではフルマップディレクトリの記憶容量が大きくなり、その利用効率が悪いという問題がある。
【０００５】
ブロードキャストを使用しない他の一貫性制御方法としてチェーンドディレクトリ方式と呼ばれる方式が特開平３−３１９４７号公報や“ＰＬＵＳ：Ａ  ｄｉｓｔｒｉｂｕｔｅｄ  ｓｈａｒｅｄ−ｍｅｍｏｒｙ  ｓｙｓｔｅｍ”，Ｔｈｅ  １７ｔｈ  Ａｎｎｕａｌ  Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｓｙｍｐｏｓｉｕｍ  ｏｎ  ＣＯＭＰＵＴＥＲ  ＡＲＣＨＩＴＥＣＴＵＲＥ，ｐｐ．１１５−１２４に開示されている。チェーンドディレクトリ方式では、各物理ページごとにチェーンドディレクトリを設ける。チェーンドディレクトリは、同一の仮想ページを共有する当該物理ページとは別の物理ページをもつノードのノード番号をチェーンとして一つ保有する。このようにして同一の仮想ページを共有する物理ページは次々にチェーンし、チェーンの最後の物理ページは先頭の物理ページにチェーンするリンクトリストを構成する。仮想ページの更新通知を受信したノードは、自ノードの対応する物理ページを更新した後、当該物理ページに付随するチェーンドディレクトリのチェーンが指し示すノードに更新通知を送信する。このようにして更新通知がリンクトリストを一巡するまで次々に物理ページの更新と更新通知の送信を繰り返す。更新通知に対する確認応答は、最後に物理ページの更新を行ったノードだけが最初に物理ページの更新を行ったノードに対して行うので、ネットワークの負荷の集中は起こらない。しかし関連する物理ページの更新が逐次的に行われるために、仮想ページの更新に必要な時間は仮想ページを共有するノード数に比例して増加する。なおチェーンドディレクトリのチェーンはノード番号なので、チェーンを格納するために要するビット数は総ノード数の２を底とする対数となり、台数拡張性に優れる。
【０００６】
さらに他の方式として、擬似フルマップ方式の１つである階層化マップ方式が「Ｍｅｍｏｒｙ−Ｂａｓｅｄ  Ｐｒｏｃｅｓｓｏｒによる分散共有メモリ」，情報処理シンポジウムＪＳＰＰ’９３，ｐｐ．２４５−２５２に開示されている。擬似フルマップ方式の階層化マップ方式では、各仮想ページごとに擬似フルマップディレクトリを設けるとともに、仮想ページの管理を各ノードに分散させる。擬似フルマップディレクトリは、ビットマップを有するが、各ビットはノードの集合に対応する。すなわち各ノード集合が当該仮想ページに対応する物理ページを保持するか否かを１ビットの情報で表現する。そしてその仮想ページを管理するノードからの通信距離が近い範囲ではノード集合中のノード数を少なくし、遠くなる程ノード集合中のノード数を多くする。ネットワークは階層構造トポロジ及び階層放送機構を前提とする。階層構造トポロジをもつネットワークにおいて、階層放送機構とは、部分階層構造に対するブロードキャスト機構のことをいい、限定されたマルチキャスト機能を実現する。例えば２進木ネットワークで木の葉にノードが存在する構成では、ノード数が１６ノードの場合、ノード０が管理する仮想ページの擬似フルマップディレクトリのビットマップの各ビットとノードの集合は、ビット０はノード１に、ビット１はノード２〜３に、ビット２はノード４〜７に、ビット３はノード８〜１５にそれぞれ割り当てる。仮想ページの更新に際しては、ビットマップの各ビットに対応するノード集合に対して更新通知を行う。更新通知は仮想ページを管理するノードを起点としてネットワークの階層構造を根に向かって伝搬する。葉と根の中間に位置する節は、階層放送機構を利用して更新通知が伝わって来たのではない方の部分階層構造に対して更新通知を放送する。仮想ページの更新に必要な時間は総ノード数の２を底とする対数に比例する。更新通知に対する確認応答は、更新通知の逆向きに階層構造を伝搬する。このため更新要求ノードに対する確認応答は、仮想ページを管理するノードのみが行うため、ネットワークの負荷の集中は起こらない。しかし更新通知がノードの集合に対して行われるため、共有に無関係のノードが更新通知を受信する場合が多い。すなわち無駄な更新通知がネットワークに伝送される。また階層放送機構を前提とした方式である。なおビットマップのビット数は総ノード数の２を底とする対数となる。
【０００７】
【発明が解決しようとする課題】
以上述べたように、フルマップディレクトリ方式は、ネットワークの効率が良いという利点があるが、ネットワークの負荷が大域記憶装置に集中するとともに、仮想ページの更新に費やす時間が長いと言う欠点がある。またフルマップディレクトリの記憶容量が大きく、利用効率が悪い。チェーンドディレクトリ方式は、ディレクトリの領域が小さく、ネットワークの負荷が集中せず、ネットワークの効率が良いと言う利点があるが、仮想ページの更新に費やす時間が長いと言う欠点がある。擬似フルマップ方式の階層化マップ方式は、ディレクトリの領域が小さく、ネットワークの負荷が集中せず、仮想ページの更新に費やす時間が短いという利点があるが、ネットワークの効率が悪いという欠点と、階層放送機構が必要であるという制約がある。このようにそれぞれの方式とも一長一短がある。
【０００８】
本発明は以上の方式の利点のみを備えるものである。すなわち
本発明の目的は、仮想記憶領域の更新に際して一貫性制御に費やす時間を削減することにある。
【０００９】
また本発明の目的は、一貫性制御のために必要とするディレクトリ領域の大きさを総ノード数の対数に比例する程度のものとすることにある。
【００１０】
また本発明の目的は、ネットワークの負荷の集中を避けることにある。
【００１１】
さらに本発明の目的は、共有に無関係のノードへの更新通知が発生しないようにし、ネットワークの効率を良くすることにある。
【００１２】
【課題を解決するための手段】
本発明は、各ノード計算機にトリードディレクトリを設け、このトリードディレクトリに基づいて一貫性制御を行う更新制御方法を特徴とする。トリードディレクトリは、同一の仮想記憶領域を共有するノード計算機をトリー状に配列したときの少なくとも子となるノード計算機の番号を登録するものである。他のノード計算機から仮想記憶領域の更新要求を受けたノード計算機では、指定された仮想記憶領域に対応する局所記憶装置内の記憶領域を更新し、この仮想記憶領域に対応してトリードディレクトリに登録されているすべての子となるノード計算機に対して更新要求を伝播する。
【００１３】
トリードディレクトリに子となるノードの番号とともに親となるノードの番号を登録すれば、親のノードから仮想記憶領域の更新要求を受けたノードでは、登録されているすべての子となるノードに対して更新要求を伝播する。すべての子となるノードから更新要求に対する確認応答を受けたとき、親となるノードへ確認応答を送信する。
【００１４】
ノード計算機の間で共有される大域記憶装置上に同一の仮想記憶領域を共有するノードをトリー状に配列したときの根となるノードの番号を登録すれば、ノード計算機内部で記憶領域の更新要求が発生したノードでは、大域記憶装置上の根となるノード番号を参照してまず根のノードに対して更新要求を発行する。この更新要求は、根のノードから子のノードへと順次伝播される。更新要求に対する確認応答は末端のノードから順次逆向きに伝播され、確認応答が到達した根のノードでは更新要求を受けたノードに対して確認応答を送信し、仮想記憶領域を共有する実記憶領域の書き込み処理が完了する。
【００１５】
【発明の実施の形態】
（１）第１の実施形態
図１は、本実施形態の並列計算機のシステム構成を示す図である。並列計算機は、複数のノード計算機（以下ノードと略称する）１００、大域記憶装置１０７及びこれらノード１００、大域記憶装置１０７間を接続するクロスバネットワーク１０４から構成される。ノード１００は、処理装置１０１、局所的な記憶装置１０２及び仮想記憶操作装置１０３から構成される。本実施形態の並列計算機は、全体として単一の仮想記憶を有する。仮想記憶は、複数の仮想ページから構成され、各仮想ページは例えば４０９６バイトのように固定長である。記憶装置１０２は、複数の物理ページから構成され、各物理ページのサイズは仮想ページのサイズと同じである。なお処理装置１０１が内蔵のキャッシュメモリを有する場合には、それはライトスルーキャッシュでなければならない。すなわちキャッシュ中のデータと記憶装置１０２中の対応するデータが常に一致していなければならない。仮想記憶操作装置１０３は、記憶装置操作部１３０、通信媒体操作部１４０、トリードディレクトリ１２０、書き込み中テーブル１１０及びこれらを制御する仮想記憶操作装置制御部１７０から構成される。記憶装置操作部１３０は、記憶装置１０２に格納されているデータの読み取り及び記憶装置１０２へのデータの書き込みを制御する。記憶装置操作部１３０は、記憶装置１０２に対して物理ページ番号によってデータの読み取り及び書き込みを行う。各通信媒体操作部１４０は、クロスバネットワーク１０４を介して相互に通信可能であり、各種の要求、確認応答及びデータを相互に交換する。トリードディレクトリ１２０は、仮想ページの番号と対応する記憶装置１０２内の物理ページの番号との変換対を有するとともに、同一の仮想ページを複数のノード１００で共有する場合に対応する物理ページを有する他のノード１００の番号を格納する。書き込み中テーブル１１０は、自身のノード１００又は他のノード１００にデータを書き込む際にデータ書き込み処理が終了するまでデータ書き込み中の仮想ページの番号を格納しておくためのテーブルである。仮想記憶操作装置制御部１７０は、処理装置１０１から仮想ページ内データの読み取り要求を受けたとき、トリードディレクトリ１２０を参照して指定された仮想ページ番号を物理ページ番号に変換して記憶装置操作部１３０を介して記憶装置１０２にアクセスし、得られたデータを処理装置１０１に渡し、処理装置１０１から仮想ページ内データの書き込み要求を受けたとき、書き込み中テーブル１１０に指定された仮想ページ番号を登録し、トリードディレクトリ１２０を参照して指定された仮想ページ番号を物理ページ番号に変換して記憶装置操作部１３０を介して記憶装置１０２にアクセスしデータを書き込む。
【００１６】
大域記憶装置１０７は、大容量記憶装置１０６、大容量記憶装置操作部１６０、大域ページテーブル１０５、大域ページテーブル操作部１５０、通信媒体操作部１４０及びこれらを制御する大域記憶装置制御部１８０から構成される。大容量記憶装置１０６は、複数の物理ページから構成され、すべての仮想ページの内容を保持する。大容量記憶装置操作部１６０は、大容量記憶装置１０６に格納されている物理ページの読み取り及び大容量記憶装置１０６への物理ページの書き込みを制御する。大域ページテーブル１０５は、仮想ページ番号と対応する大容量記憶装置１０６内の物理ページの番号との変換対を有するとともに、格納される仮想ページ番号に対応する記憶装置１０２内の物理ページをもつノード１００の１つの番号を保持する。大域ページテーブル操作部１５０は、大域ページテーブル１０５に格納されている情報の読み取り及び大域ページテーブル１０５への情報の書き込みを制御する。大域記憶装置制御部１８０は、通信媒体操作部１４０を介して受け取ったノード１００からの要求に応答して、大域ページテーブル操作部１５０を介して大域ページテーブル１０５にアクセスし、指定された仮想ページ番号を大容量記憶装置１０６内の物理ページ番号に変換し、大容量記憶装置操作部１６０を介して大容量記憶装置１０６に格納されている物理ページを読み取ってノード１００へ送り、ノード１００から受け取った物理ページを大容量記憶装置１０６へ書き込む。また大域記憶装置制御部１８０は、ノード１００からの要求に従って大域ページテーブル操作部１５０を介して大域ページテーブル１０５にアクセスし、大域ページテーブル１０５上に新しいエントリを作成し、エントリの内容を取得してノード１００へ送り、またエントリを削除する。
【００１７】
仮想記憶操作装置制御部１７０は、通信媒体操作部１４０及びクロスバネットワーク１０４を介して大域記憶装置制御部１８０へ仮想ページの割り当てを要求すると、大域記憶装置制御部１８０は大域ページテーブル操作部１５０を介して大域ページテーブル１０５上に新しいエントリを作成する。また仮想記憶操作装置制御部１７０が仮想ページの割り当て解除を要求すると、大域記憶装置制御部１８０は大域ページテーブル１０５から指定されたエントリを削除する。処理装置１０１から仮想ページ内データの読み取り要求又は書き込み要求を受けたときの仮想記憶操作装置制御部１７０の動作は上記の通りである。特に仮想記憶操作装置制御部１７０が仮想ページの書き込み要求を受けたとき、書き込み中テーブル１１０にその仮想ページの番号を書き込み、トリードディレクトリ１２０と大域ページテーブル１０５とを参照してその仮想ページを共有するトリー状に構成された複数のノードのうち根となるノードに対して物理ページの更新要求を発行する。根となるノードの仮想記憶操作装置制御部１７０は、自ノード内の記憶装置１０２上の物理ページの内容を更新した後、トリーを構成する複数のノードのうち子となるすべてのノードに対して更新要求を発行する。すべての子は当該仮想ページに対応する物理ページの内容を更新した後、孫がいればすべての孫に対して更新要求を発行する。このようにして更新要求はすべての子孫に伝播する。更新要求を受けたすべての子孫は、その親に対して確認応答を送信する。このようにして確認応答はノードのトリーを遡り、根のノードに到達する。根のノードは最初に更新要求を発行したノードの仮想記憶操作装置制御部１７０に書き込み完了通知を行う。この書き込み完了通知を受けた仮想記憶操作装置制御部１７０は、書き込み中テーブル１１０から当該仮想ページ番号を削除する。なお仮想記憶操作装置制御部１７０が仮想ページ読み取り要求を受けたとき自ノード内に対応する物理ページがない場合には、対応する物理ページを保有する他のノードから物理ページの内容のコピーをもらう。対応する物理ページを保有する他のノードがないときには、大域記憶装置制御部１８０に要求し、大容量記憶装置１０６から物理ページの内容のコピーをもらう。
【００１８】
図２は、トリードディレクトリ１２０のデータ構成を示す図である。トリードディレクトリ１２０は、記憶装置１０２がもつ物理ページの数Ｍと同数のエントリ２００をもつ。エントリ２００は、ノード内物理ページ番号２０１、仮想ページ番号２０２、状態２０３、親のエントリが属するノード番号２０４、左の子のエントリが属するノード番号２０５、右の子のエントリが属するノード番号２０６及び更新中カウンタ２０７から構成される。以下親のエントリのことを単に親、左の子のエントリのことを単に左の子及び右の子のエントリのことを単に右の子と呼ぶ。また親が属するノード番号を親のノード番号と呼び、左の子が属するノード番号を左の子のノード番号と呼び、右の子が属するノード番号を右の子のノード番号と呼ぶ。エントリ２００はノード内物理ページ番号２０１でインデックスされる。ノード内物理ページ番号２０１は、当ノードの記憶装置１０２内の物理ページの番号を示す。仮想ページ番号２０２は、物理ページ番号２０１に対応する仮想ページ番号を示す。状態２０３がとりうる値については後述する。親ノード番号２０４、左の子のノード番号２０５、右の子のノード番号２０６については後述する。更新中カウンタ２０７は、初期値が０であり、１以上の場合には当該エントリの仮想ページの内容を更新処理中であることを示し、その場合には子の追加要求及び当該エントリが対応する物理ページの割り当て解除要求を待たせる。これは更新に対する確認応答処理が複雑となるのを避けるためである。
【００１９】
図３は、状態２０３がとり得る状態と状態から状態へ可能な遷移を示す図である。状態２０３は、無効３００、割り当て中３０１、有効３０２、割り当て解除中３０３及びロック３０７をとり得る。無効３００は当該エントリに関して仮想ページが割り当てられていない状態である。有効３０２は当該エントリに関して仮想ページが割り当てられている状態である。割り当て中３０１は無効３００から有効３０２に遷移する途中の状態である。割り当て解除中３０３は有効３０２から無効３００に遷移する途中の状態である。ロック３０７はノード番号２０４、２０５又は２０６を変更する時に当該エントリをロックしている状態である。
【００２０】
図４は、同一の仮想ページを共有する複数の物理ページのトリードディレクトリのエントリ群を示す図である。仮想ページ番号２０２が等しく、状態２０３が無効３００でないエントリ４０１の集合を仮想ページを共有するエントリ群４００と呼ぶ。エントリ群４００を構成するエントリ４０１の物理ページ番号２０１によってアドレス付けされるすべての物理ページは、仮想記憶操作装置１０３によって同一内容に保たれる。親のノード番号２０４は、当該エントリの親となるエントリをもつノード１００の番号を示す。親のノード番号２０４が自ノードのノード番号の場合には親はいないことを示し、その場合はそのエントリを根のエントリ４０２又は単に根と呼ぶ。左の子のノード番号２０５は、当該エントリから分岐して左側の子となるエントリをもつノード１００の番号を示す。左の子のノード番号２０５が自ノードのノード番号の場合には当該エントリの左の子はいないことを示す。左の子のエントリ４１２を単に左の子とも呼ぶ。右の子のノード番号２０６は、当該エントリから分岐して右側の子となるエントリをもつノード１００の番号を示す。右の子のノード番号２０６が自ノードのノード番号の場合には当該エントリの右の子はいないことを示す。右の子のエントリ４１３を単に右の子とも呼ぶ。また左の子と右の子を総称して子と呼ぶ。エントリ群４００には必ず唯一の根のエントリ４０２が含まれる。図４の例は、根のエントリ４０２からその右の子のエントリ４１１が派生し、エントリ４１１からその右の子のエントリ４１０が派生し、エントリ４１０からその左の子のエントリ４１２と右の子のエントリ４１３が派生する４階層の２分木の事例である。
【００２１】
左の子のノード番号２０４、右の子のノード番号２０６のように子のノード番号を複数持つことが本発明の最大の特徴である。本実施例ではあるノードにはある仮想ページ番号に対応するトリードディレクトリエントリは高々１つしか存在しないことが保証されるため、トリードディレクトリエントリが存在するノード番号及び仮想ページ番号によってトリードディレクトリエントリは並列計算機全体において一意に特定される。
【００２２】
図５は、書き込み中テーブル１１０のデータ形式を示す図である。書き込み中テーブル１１０は、一つの書き込み中テーブルのロック５００及び複数のエントリ５０１から構成される。ロック５００が１の場合は書き込み同期中であることを示す。書き込み同期中はロック５００が０になるまでノード１００が行うすべての仮想ページへの書き込み処理が待たされる。各エントリ５０１は、仮想ページ番号５０２と有効ビット５０３とから構成される。有効ビット５０３は無効（０）又は有効（１）の値を取り得る。有効ビット５０３の値が１の場合には、仮想ページ番号５０２の仮想ページ番号が書き込み中テーブル１１０に登録されていることを示す。書き込み中テーブル１１０に仮想ページ番号が登録されている仮想ページは、その書き込み処理が並列計算機全体を通じて完了していないことを示す。書き込み処理が完了したとき、その仮想ページ番号が書き込み中テーブル１１０から削除される。書き込み中テーブル１１０に仮想ページ番号が登録されている仮想ページについての読み取り要求は、その仮想ページの書き込みが完了するまで待たされる。
【００２３】
図６は、大域ページテーブル１０５のデータ形式を示す図である。大域ページテーブル１０５は、複数のエントリ６００から構成される。エントリ６００は、仮想ページ番号６０１、根のトリードディレクトリのエントリを持つノード番号６０２、大容量記憶装置内の物理ページ番号６０３及びロック６０４から構成される。ノード１００から仮想ページの割り当てが要求されたとき、仮想ページ番号６０１にその仮想ページの番号をもつエントリ６００が大域ページテーブル１０５に追加される。ノード１００から仮想ページの割り当て解除が要求されたとき、仮想ページ番号６０１にその仮想ページの番号をもつエントリ６００が大域ページテーブル１０５から削除される。根のトリードディレクトリのエントリをもつノード番号６０２は、根のエントリをもつノード番号を格納する。ノード番号６０２が−１の場合にはどのノード１００も当該仮想ページに関するトリードディレクトリのエントリ及び対応する物理ページをもっていないことを示す。大容量記憶装置内物理ページ番号６０３は、当該仮想ページに対応する大容量記憶装置内の物理ページの番号を示す。ロック６０４が１の場合、当該エントリは書き換え中であることを示す。ロック６０４が１であるエントリ６００へのアクセスは無効である。
【００２４】
仮想記憶操作装置１０３の仮想記憶操作装置制御部１７０は、処理装置１０１からの要求を受けて仮想ページについての操作を行う。仮想ページの操作には、仮想ページの割り当て、仮想ページの割り当て解除、仮想ページの読み取り、仮想ページの書き込み及び書き込みの同期の５つがある。仮想ページの割り当て及び仮想ページの割り当て解除は、通常図示しないオペレーティングシステムが処理装置１０１を介して要求する操作である。これに対して仮想ページの読み取り及び仮想ページの書き込みは、記憶装置１０２に格納され処理装置１０１によって実行される図示しないすべてのプログラムが例えばＬＯＡＤ命令及びＳＴＯＲＥ命令のような機械語の命令によって処理装置１０１を介して要求する操作である。書き込み同期は、その前に要求された仮想ページの書き込み処理が並列計算機全体を通じて完了するまで後続する書き込み処理を待たせるよう要求する操作である。以下各操作について順を追って説明する。
【００２５】
（ａ）仮想ページの割り当て（ｖｐ）
大域ページテーブル１０５に仮想ページ番号ｖｐをもつエントリを追加する操作である。
【００２６】
図７は、仮想ページの割り当てを行う仮想記憶操作装置制御部１７０の処理の流れを示すフローチャートである。処理装置１０１から仮想ページ番号ｖｐの割り当てを要求されたとき、仮想記憶操作装置制御部１７０は、通信媒体操作部１４０及びクロスバネットワーク１０４を介して大域仮想記憶装置１０７に大域ページテーブル１０５のエントリの取得要求（引数はｖｐ，自ノード番号であり、以下同様）を行い（ステップ１０００）、大域ページテーブル１０５上のエントリ（ｖｐ，エントリの内容）もしくは否定応答（ｖｐ）を受け取る。否定応答（ｖｐ）を受け取った場合はステップ１００４へ進む。仮想ページ番号ｖｐのエントリが存在する場合（ステップ１００１ＹＥＳ）、当該エントリのロック６０４が０ならば（ステップ１００２ＮＯ）、すでに同一の仮想ページ番号をもつエントリが存在することを示し、エラーであるのでステップ１００８へ進む。当該エントリのロック６０４が１ならば（ステップ１００２ＹＥＳ）、当該エントリは仮想ページ割り当て解除中でロックが１となっている可能性があるので、一定時間間隔で大域仮想記憶装置１０７に大域ページテーブルのエントリの取得要求（ｖｐ，自ノード番号）を行い、当該エントリのロックが０になるか、否定応答（ｖｐ）を受け取ったとき（ステップ１００３）、ステップ１０００に戻る。仮想ページ番号ｖｐのエントリが存在しない状態（ステップ１００１ＮＯ）で、大域仮想記憶装置１０７に大域ページテーブル１０５のエントリの作成要求（ｖｐ，自ノード番号）を行う（ステップ１００４）。その結果、大域仮想記憶装置１０７から作成肯定応答（ｖｐ）か作成否定応答（ｖｐ）を受け取る。作成否定応答（ｖｐ）を受け取った場合は（ステップ１００５ＮＯ）、ステップ１０００へ戻る。作成肯定応答（ｖｐ）を受け取った場合は（ステップ１００５ＹＥＳ）、大域仮想記憶装置１０７に大域ページテーブル１０５のエントリの根のノード番号６０２の設定要求（ｖｐ，自ノード番号，−１）を行い（ステップ１００６）、大域ページテーブルのエントリの根のノード番号を設定したという確認応答（ｖｐ）を受け取る。この状態では、並列計算機のどのノード１００にも仮想ページ番号ｖｐの仮想ページに対応する物理ページが割り当てられていない。なお大域仮想記憶装置１０７は、エントリ作成の肯定応答を送信するとともに、大容量記憶装置１０６内に物理ページを割り当て、当該エントリのロック６０４を１にセットし、物理ページ番号６０３に割り当てた物理ページ番号を設定する。次に仮想記憶操作装置制御部１７０は、当該エントリのアンロック要求（ｖｐ，自ノード番号）を行い（ステップ１００７）、確認応答（ｖｐ）を受け取ったとき処理装置１０１に仮想ページ割り当て完了を通知して処理を終了する。同一の仮想ページ番号をもつエントリが存在する場合（ステップ１００２ＮＯ）、保護エラーを処理装置１０１に通知して処理を終了する（ステップ１００８）。
【００２７】
（ｂ）仮想ページの割り当て解除（ｖｐ）
大域ページテーブル１０５から仮想ページ番号ｖｐのエントリを削除する操作である。当該仮想ページについて根をもつノードが無い場合には、仮想ページ割り当て解除要求をしたノードが大域ページテーブル１０５から当該仮想ページのエントリを削除する。根をもつノードがある場合には、根をもつノード宛に当該仮想ページを共有するすべての物理ページの割り当てを解除するよう要求し、根をもつノードが大域ページテーブル１０５から当該仮想ページのエントリを削除する。
【００２８】
図８は、仮想ページの割り当て解除を行う仮想記憶操作装置制御部１７０の処理の流れを示すフローチャートである。処理装置１０１から仮想ページｖｐの割り当て解除を要求されたとき、仮想記憶操作装置制御部１７０は、大域仮想記憶装置１０７に大域ページテーブル１０５のエントリの取得要求（ｖｐ，自ノード番号）を行い（ステップ１１００）、エントリ（ｖｐ，エントリの内容）もしくは否定応答（ｖｐ）を受け取る。否定応答（ｖｐ）を受け取った場合（ステップ１１０１ＮＯ）は、ステップ１１０９に進む。エントリの内容を受け取ったとき（ステップ１１０１ＹＥＳ）、当該エントリのロック６０４が０ならば（ステップ１１０２ＹＥＳ）、ステップ１１０４に進む。当該エントリのロック６０４が１ならば（ステップ１１０２ＮＯ）、一定時間間隔で大域仮想記憶装置１０７に大域ページテーブルのエントリの取得要求（ｖｐ，自ノード番号）を行い、当該エントリのロックが０になるか否定応答（ｖｐ）を受け取ったとき（ステップ１１０３）、ステップ１１００に戻る。当該エントリのロックが０の状態で（ステップ１１０２ＹＥＳ）、大域仮想記憶装置１０７に大域ページテーブルのエントリのロック要求（ｖｐ，自ノード番号）をする（ステップ１１０４）。その結果、大域仮想記憶装置１０７から肯定応答（ｖｐ）か否定応答（ｖｐ）を受け取る。否定応答（ｖｐ）を受け取った場合は（ステップ１１０５ＮＯ）、ステップ１１００へ戻る。肯定応答（ｖｐ）を受け取ったとき（ステップ１１０５ＹＥＳ）、すでに受けとっているエントリの内容の中で根をもつノード番号６０２が−１の場合は（ステップ１１０６ＹＥＳ）、ステップ１１１０に進む。根をもつノードがある場合（ステップ１１０６ＮＯ）、そのノード宛に当該仮想ページのエントリ２００のロック要求（ｖｐ，自ノード番号）を行う（ステップ１１０７）。根をもつノードからロック確認応答（ｖｐ，根をもつノード番号）を受け取ったとき、根をもつノード宛に仮想ページに対応する物理ページの割り当てを解除する要求（ｖｐ，自ノード番号）を行い（ステップ１１０８）、処理を終了する。根をもつノードは、この物理ページの割り当て解除の処理を当該仮想ページを共有するすべてのノードに伝播させる。当該仮想ページに対応するすべての物理ページの割り当てが解除されたとき、根をもつノードは大域ページテーブル１０５上の当該仮想ページのエントリを削除する。大域ページテーブル１０５上にエントリが存在しない場合（ステップ１１０１）、処理装置１０１に保護エラー通知を行い（ステップ１１０９）、処理を終了する。根を持つノードが存在しない場合（ステップ１１０６ＹＥＳ）には、大域仮想記憶装置１０７に大域ページテーブルのエントリの削除要求（ｖｐ）を行い、削除確認応答（ｖｐ）を受け取って処理を終了する（ステップ１１１０）。大域仮想記憶装置１０７は大容量記憶装置内物理ページ番号６０３に対応する物理ページを大容量記憶装置１０６から解除する。
【００２９】
（ｃ）仮想ページの読み取り（ｖｐ，読み込み範囲）
仮想ページ内の読み取り範囲の情報を読み取って処理装置１０１に送る操作である。仮想ページに対応する物理ページが自ノード内に存在しない場合は、自ノード内に物理ページを割り当てた後、その内容を読み取る。
【００３０】
図９は、仮想ページの読み取りを行う仮想記憶操作装置制御部１７０の処理の流れを示すフローチャートである。仮想記憶操作装置制御部１７０が処理装置１０１から仮想ページの読み取り要求（ｖｐ，ページ内読み込み範囲）を受けたとき（ステップ１２００）、トリードディレクトリ１２０を仮想ページ番号ｖｐによって検索する。トリードディレクトリにｖｐのエントリが存在する、すなわち仮想ページｖｐに対応する物理ページが自ノードに存在する場合（ステップ１２０１ＹＥＳ）には、ステップ１２０４へ進む。物理ページが存在しない場合（ステップ１２０１ＮＯ）には、大域仮想記憶装置１０７に大域ページテーブルのエントリの取得要求（ｖｐ，自ノード番号）を行い、エントリ（ｖｐ，エントリの内容）もしくは否定応答（ｖｐ）を受け取る。否定応答（ｖｐ）を受け取った場合（ステップ１２０２ＮＯ）は、ステップ１２０７へ進む。大域ページテーブルにエントリが存在する場合（ステップ１２０２ＹＥＳ）には、自ノード内での物理ページの割り当て（ｖｐ）要求を行う（ステップ１２０３）。物理ページ割り当て処理の詳細は「（ｆ）物理ページの割り当て」で説明する。物理ページの割り当てが済んでいる状態で、書き込み中テーブル１１０に仮想ページ番号ｖｐが格納されていれば削除されるまで待つ（ステップ１２０４）。すなわち当該仮想ページの書き込みが完了するまで待つ。当該仮想ページが書き込み中でない状態で、トリードディレクトリ１２０の当該エントリのノード内物理ページ番号２０１に対応する物理ページについて指定された読み取り範囲を記憶装置１０２から読み取る（ステップ１２０５）。最後に仮想記憶操作装置制御部１７０は、読み取った情報を処理装置１０１に渡して（ステップ１２０６）、処理を終了する。大域ページテーブルにエントリが存在しない場合（ステップ１２０２ＮＯ）には、保護エラーを処理装置１０１に通知し（ステップ１２０７）、処理を終了する。
【００３１】
（ｄ）仮想ページの書き込み（ｖｐ，書き込み範囲，書き込み内容）
仮想ページ内の書き込み範囲へ書き込み内容を書き込む操作である。処理装置１０１から仮想ページの書き込み要求を受けたノードは、まず根をもつノードに対して書き込み（あるいは更新）要求を行う。根をもつノードはその物理ページの内容を更新してからその子のノードに対して更新要求を転送する。物理ページの更新が終了したノードは、子からの更新確認応答を受け取ってから親に対して順次更新確認応答を行う。このようにして更新確認応答はノードのトリーを遡り、更新確認応答を受け取った根をもつノードは、処理装置１０１から仮想ページの書き込み要求を受けたノードに対して書き込み完了通知を行う。処理装置１０１から仮想ページの書き込み要求を受けたノードが根をもつノードである場合には、上記の根をもつノードに対する更新要求及び書き込み完了通知の処理をバイパスする。なお処理装置１０１から仮想ページの書き込み要求を受けたノードは、他のノードの記憶装置１０２の物理ページに対してのみ書き込みを行い、自ノードの記憶装置１０２に対して書き込みしないことも可能である。処理装置１０１から仮想ページの書き込み要求を受けたノードでは、書き込み同期中（すなわち書き込み中テーブル１１０のロック５００が１）の場合は、書き込み同期が完了する（すなわち書き込み中テーブル１１０のロック５００が０になる）のを待つ。また当該仮想ページの書き込みが完了しない間は、書き込み中テーブル１１０に当該仮想ページ番号を登録しておき、当該仮想ページの読み取りを待たせる。
【００３２】
図１０は、仮想ページの書き込みを行う仮想記憶操作装置制御部１７０の処理の流れを示すフローチャートである。仮想記憶操作装置制御部１７０が処理装置１０１から仮想ページの書き込み要求（ｖｐ，ページ内書き込み範囲，書き込み内容）を受けたとき（ステップ１３００）、トリードディレクトリ１２０を仮想ページ番号ｖｐで検索し、トリードディレクトリにｖｐのエントリが存在する、すなわち仮想ページｖｐの物理ページが自ノードに存在する場合（ステップ１３０１ＹＥＳ）は、ステップ１３０４へ進む。仮想ページｖｐの物理ページが自ノードにない場合（ステップ１３０１ＮＯ）には、大域仮想記憶装置１０７に大域ページテーブルのエントリの取得要求（ｖｐ，自ノード番号）を行い、エントリ（ｖｐ，エントリの内容）もしくは否定応答（ｖｐ）を受け取る。否定応答（ｖｐ）を受け取った場合（ステップ１３０２ＮＯ）は、ステップ１３０９に進む。エントリを取得した場合（ステップ１３０２ＹＥＳ）には、物理ページ割り当て（ｖｐ）を行う（ステップ１３０３）。次に書き込み中テーブル１１０のロックが０でなければ０になるまで待つ（ステップ１３０４）。すなわち書き込み同期が完了するのを待つ。書き込み中テーブル１１０のロックが０の状態で同テーブルに仮想ページ番号ｖｐを登録する（ステップ１３０５）。ここで登録とは、有効ビット５０２の値が０であるエントリ５０１を一つ選択し、当該エントリの仮想ページ番号５０２の値をｖｐ、当該エントリの有効ビット５０３の値を１と設定することである。すべてのエントリ５０１が有効の場合は、いずれかのエントリ５０１が無効となるまで待ってから登録を行う。次にトリードディレクトリ１２０の当該仮想ページのエントリの親ノード番号２０４を参照して、根のエントリをもつノード宛に更新要求（ｖｐ，自ノード番号，書き込み範囲、書き込み内容）を行う（ステップ１３０６）。自ノードが根のエントリをもつノードである場合又は親がいない場合には自ノード内の更新要求である。親が存在し、かつ根のエントリをもつノードの番号を取得していなければ、大域ページテーブル１０５上のエントリを取得し、根のエントリをもつノードの番号を得てからステップ１３０６の更新要求を行う。書き込み処理が完了したとき、根のエントリをもつノードから書き込み完了通知（ｖｐ）を受け取る（ステップ１３０７）。次に書き込み中テーブル１１０から登録した仮想ページ番号ｖｐを削除して（ステップ１３０８）、処理を終了する。ここで削除とは、有効ビット５０２の値が１でありかつ仮想ページ番号５０２の値がｖｐであるエントリ５０１を選択し、当該エントリの有効ビット５０３の値を０と設定することである。大域ページテーブル１０５にエントリが存在しない場合（ステップ１３０２ＮＯ）には、保護エラーが発生したことを処理装置１０１に通知して（ステップ１３０９）、処理を終了する。
【００３３】
（ｅ）書き込み同期
以前に発行した仮想ページの書き込みがすべて完了するまで後続する仮想ページの書き込みを待たせる操作である。仮想記憶操作装置制御部１７０が処理装置１０１から仮想ページの書き込み要求を受けたとき、この仮想ページを共有するすべてのノードの対応する物理ページを更新するが、並列計算機全体を通じて書き込みが完了しても処理装置１０１に書き込み完了が通知されず、処理装置１０１が書き込み完了を待つ必要はない。従って処理装置１０１から後続の仮想ページ書き込み要求を受けたとき、後続の書き込み要求が先行する書き込み要求よりも先に実行される可能性がある。書き込み同期は、先行する書き込み要求の処理が完了してから後続の書き込み要求の処理を実行することを保証する。なお同一仮想ページを共有する他のノードでも先の仮想ページに対応する物理ページの更新が完了してから後続する仮想ページに対応する物理ページの更新を実行することが保証される。
【００３４】
図１１は、書き込み同期を行う仮想記憶操作装置制御部１７０の処理の流れを示すフローチャートである。仮想記憶操作装置制御部１７０が処理装置１０１から書き込み同期の要求を受けたとき（ステップ１４００）、書き込み中テーブル１１０のロック５００を１にして（ステップ１４０１）、後続する仮想ページの書き込みを待ちとする。ロック５００が１のとき、書き込み中テーブル１１０中に登録された仮想ページ番号を削除することのみ可能であり、新たな仮想ページ番号の登録は許されない。次に書き込み中テーブル１１０から有効なエントリ５０１が存在しなくなるまで待つ（ステップ１４０２）。書き込み中テーブル１１０が空になったとき、書き込み中テーブル１１０のロック５０１を０にする（ステップ１４０３）。最後に書き込み同期の完了を処理装置１０１に通知し（ステップ１４０４）、処理を終了する。
【００３５】
（ｆ）物理ページの割り当て（ｖｐ）
仮想ページｖｐに対応する物理ページの割り当てをする操作である。ノード内に物理ページが存在しない仮想ページに対して読み取り又は書き込みを行う場合、物理ページの割り当てが発生する。仮想記憶操作装置制御部１７０は、トリードディレクトリ１２０から無効のエントリを選択し、物理ページ番号と仮想ページ番号とを対応づけることによって物理ページの割り当てを行う。並列計算機全体を通じて当該仮想ページに対応する物理ページを保有するノードが存在しないときには、大容量記憶装置１０６から当該仮想ページに対応する物理ページの内容を取得し、自ノードの記憶装置１０２上の物理ページにコピーする。他のいずれかのノードが当該仮想ページに対応する物理ページを保有するとき、根のエントリをもつノードを介して自ノードの親となるノードの記憶装置１０２から物理ページの内容を取得し、自ノードの記憶装置１０２上の物理ページにコピーする。
【００３６】
図１２は、物理ページの割り当てを行う仮想記憶操作装置制御部１７０の処理の流れを示すフローチャートである。ステップ１２０３で物理ページ割り当て（ｖｐ）が要求されたとき（ステップ１５００）、トリードディレクトリ１２０にｖｐを仮想ページとするエントリが存在する場合（ステップ１５０１ＹＥＳ）は終了する。エントリが存在しない場合（ステップ１５０１ＮＯ）、大域仮想記憶装置１０７宛に大域ページテーブルのエントリの取得要求（ｖｐ，自ノード番号）を行い、エントリ（ｖｐ，エントリの内容）もしくは否定応答（ｖｐ）を受け取る。否定応答（ｖｐ）を受け取った場合（ステップ１５０２ＮＯ）は、ステップ１５１０に進む。エントリを取得した場合（ステップ１５０２ＹＥＳ）には、トリードディレクトリ１２０中に状態２０３が無効３００のエントリが存在する場合（ステップ１５０３ＹＥＳ）には、ステップ１５０５へ進む。無効のエントリが存在しない場合（ステップ１５０３ＮＯ）には、状態２０３が有効３０２なエントリ（その仮想ページ番号をｖｐ’とする）を１つ選択し、そのエントリに対して物理ページ割り当て解除（ｖｐ’）の処理を行う（ステップ１５０４）。物理ページ割り当て解除の詳細は「（ｇ）物理ページの割り当て解除」で説明する。無効のエントリを１つ選択した状態で、当該エントリの仮想ページ番号２０２にｖｐを書き込み、状態２０３を割り当て中３０１とする（ステップ１５０５）。次に大域仮想記憶装置１０７に大域ページテーブルのエントリの取得要求（ｖｐ，自ノード番号）を行い、ｖｐのエントリを得る。大域ページテーブル１０５のｖｐのエントリの根のノード番号が−１、すなわちどのノード１００も当該仮想ページに関するトリードディレクトリのエントリ及び物理ページを持っていないなら（ステップ１５０６ＹＥＳ）、ステップ１５１１へ進む。根をもつノードが存在するなら（ステップ１５０６ＮＯ）、トリードディレクトリ１２０の当該エントリの親のノード番号２０４、左の子のノード番号２０５及び右の子のノード番号２０６をすべて自ノード番号にし、親子とも存在しないことを示す（ステップ１５０７）。次にトリードディレクトリ１２０の当該エントリの状態２０３をロック３０７にする（ステップ１５０８）。次に根をもつノード宛にエントリ追加要求（ｖｐ，自ノード番号，コピー要）を行い（ステップ１５０９）、処理を終了する。最終的にエントリ追加を行うノードが自ノード宛に親のノード番号及び仮想ページの内容を通知し、自ノードの当該エントリのロックを解除する。大域ページテーブル１０５中にエントリが存在しない場合（ステップ１５０２ＮＯ）には、保護エラーを処理装置１０１に通知し（ステップ１５１０）、処理を終了する。ステップ１２０２でチェック済みであるため、このエラーは発生しないはずである。根をもつノードが存在しないなら（ステップ１５０６ＹＥＳ）、大域仮想記憶装置１０７に大域ページテーブルのエントリのロック要求（ｖｐ，自ノード番号）を行う。否定応答（ｖｐ）が得られたら（ステップ１５１１ＮＯ）、ステップ１５２０に進む。肯定応答が得られたら（ステップ１５１１ＹＥＳ）、当該トリードディレクトリの親のノード番号２０４、左の子のノード番号２０５及び右の子のノード番号２０６を自ノード番号にし、親子とも存在しないことを示す（ステップ１５１２）。次に大容量記憶装置１０６から仮想ページの内容を読み取ってその内容を自ノードの当該仮想ページに対応する物理ページにコピーする（ステップ１５１３）。具体的には大域記憶装置１０７宛に大容量記憶装置の物理ページの読み取り要求（ｖｐ，自ノード番号）を行い、大容量記憶装置の物理ページ読み取り結果（ｖｐ，物理ページの内容）を受け取り、ノード内物理ページ番号２０１に対応する記憶装置１０２の物理ページに受け取った内容を書き込む。次に大域仮想記憶装置１０７に大域ページテーブルのエントリの根のノード番号の設定要求（ｖｐ，自ノード番号，自ノード番号）を行い、大域ページテーブルのエントリの根のノード番号の設定確認応答（ｖｐ）を受け取る（ステップ１５１４）。次にトリードディレクトリ１２０の当該エントリの状態２０３を有効３０２とする（ステップ１５１５）。最後に大域仮想記憶装置１０７に大域ページテーブルのエントリのアンロック要求（ｖｐ，自ノード番号）を行ってそのロックを０にし、アンロック確認応答（ｖｐ）を受け取って（ステップ１５１６）、処理を終了する。大域ページテーブル１０５に対するロック要求が拒否されたとき（ステップ１５１１ＮＯ）、当該エントリの状態２０３を有効３０２にし、一定時間待った後、ステップ１５０２に戻る。
【００３７】
（ｇ）物理ページの割り当て解除（ｖｐ）
仮想ページｖｐに対応する物理ページの割り当て解除をする操作である。物理ページの割り当て時に無効な物理ページが存在しない場合、物理ページの割り当て解除が発生する。物理ページの割り当て解除が要求されたとき、仮想記憶操作装置制御部１７０は、当該ノードのトリードディレクトリ１２０のエントリが根のエントリで子のエントリがなければ、大域ページテーブル１０５のエントリの根のノード番号を−１に更新し、物理ページの内容を大容量記憶装置１０６へ格納してからトリードディレクトリ１２０の当該エントリを無効にする。当該エントリが根のエントリであって子のエントリがあれば、子のエントリのチェーンを更新し、大域ページテーブル１０５のエントリの根のノード番号を子のノード番号に更新してからトリードディレクトリ１２０の当該エントリを無効にする。当該エントリが根のエントリでなければ、親のエントリのチェーンを更新し、子のエントリがあれば子のエントリのチェーンを更新してからトリードディレクトリ１２０の当該エントリを無効にする。
【００３８】
図１３及び図１４は、物理ページの割り当て解除を行う仮想記憶操作装置制御部１７０の処理の流れを示すフローチャートである。ステップ１５０４で物理ページの割り当て解除（ｖｐ）が要求されたとき（ステップ１６００）、トリードディレクトリ１２０にｖｐを仮想ページ番号２０２とするエントリが存在しない場合（ステップ１６０１ＮＯ）は、処理を終了する。エントリが存在する場合（ステップ１６０１ＹＥＳ）、当該エントリの状態２０３が有効３０２かつ更新中カウンタ２０７が０となるまで待つ（ステップ１６０２）。更新中カウンタが０になるまで待つのは、更新中のノードの確認応答処理が複雑となるのを避けるためである。次に当該エントリの状態２０３を割り当て解除中３０３とする（ステップ１６０３）。当該エントリが根のエントリの場合（ステップ１６０４ＹＥＳ）はステップ１６２０へ進む。根のエントリでない場合（ステップ１６０４ＮＯ）は、親宛にロック要求（ｖｐ，自ノード番号）を行った結果としてロック否定応答（ｖｐ，親のノード番号）を受け取る場合（ステップ１６０５ＮＡＫ）はステップ１６１３へ進む。肯定応答を受け取る場合（ステップ１６０５ＡＣＫ）、当該エントリの子が０個なら（ステップ１６０６で０）、ステップ１６１４へ進む。子が０でなければ（ステップ１６０６で≠０）、すべての子からロック確認応答（ｖｐ，子のノード番号）を受け取るまで、すべての子宛にロック要求（ｖｐ，自ノード番号）を行う（ステップ１６０７）。当該エントリの子が１個なら（ステップ１６０８で１）、ステップ１６１５へ進む。子が２個なら（ステップ１６０８で２）、親エントリの子を自エントリの代わりに自エントリの左の子にする。すなわち親宛にチェーン張り換え要求（ｖｐ，自ノード番号，自ノード番号，左の子のノード番号）を行い、チェーン張り換え確認応答（ｖｐ，親のノード番号）を受け取る（ステップ１６０９）。次に左の子の親を自エントリの親にする。すなわち左の子宛にチェーン張り換え要求（ｖｐ，自ノード番号，自ノード番号，親のノード番号）を行い、チェーン張り換え確認応答（ｖｐ，左の子のノード番号）を受け取る（ステップ１６１０）。次に左の子宛にアンロック要求（ｖｐ）を行う（ステップ１６１１）。次に左の子宛にエントリ追加要求（ｖｐ，右の子ノード番号，コピー不要）を行い（ステップ１６１２）、ステップ１６１８へ進む。親宛にロック要求を行って否定応答を受けたとき（ステップ１６０５ＮＡＫ）、当該エントリの状態２０３を有効３０２とし、一定時間待った後に１６０１へ戻る（ステップ１６１３）。自エントリが親宛にロック要求を行っているときに親エントリが自エントリ宛にロック要求を行う場合にも、デッドロックが発生しないようにするためである。当該エントリの子が０のとき（ステップ１６０６で０）、親宛にチェーン張り換え要求（ｖｐ，自ノード番号，自ノード番号，親のノード番号）を行い、親からチェーン張り換え確認応答（ｖｐ，親のノード番号）を受け取る（ステップ１６１４）。当該エントリの子が１のとき（ステップ１６０８で１）、自エントリの代わりに自エントリの子を親の子にする。すなわち親宛にチェーン張り換え要求（ｖｐ，自ノード番号，自ノード番号，子のノード番号）を行い、チェーン張り換え確認応答（ｖｐ，親のノード番号）を受け取る（ステップ１６１５）。次に子宛にチェーン張り換え要求（ｖｐ，自ノード番号，自ノード番号，親のノード番号）を行い、チェーン張り換え確認応答（ｖｐ，子のノード番号）を受け取る（ステップ１６１６）。次に左の子宛にアンロック要求（ｖｐ）を行う（ステップ１６１７）。ステップ１６１８で親宛にアンロック要求（ｖｐ）を行い、トリードディレクトリ１２０の当該エントリの状態２０３を無効３００とし（ステップ１６１９）、処理を終了する。当該エントリが根のエントリの場合（ステップ１６０４ＹＥＳ）、当該エントリの子が０個なら（ステップ１６２０で０）ステップ１６２９へ進む。子が０でなければ（ステップ１６２０で≠０）、当該エントリの子が１個なら（ステップ１６２１で１）ステップ１６２５へ進む。子が２個なら（ステップ１６２１で２）、右の子からロック確認応答（ｖｐ，右の子のノード番号）を受け取るまで右の子宛にロック要求（ｖｐ，自ノード番号）を行う（ステップ１６２２）。次に左の子宛にエントリ追加要求（ｖｐ，右の子のノード番号，コピー不要）を行う（ステップ１６２３）。右の子がエントリ追加要求をするノードとなる。次に自エントリの右の子のノード番号２０５を自ノード番号にする（ステップ１６２４）。次に子からロック確認応答（ｖｐ，子のノード番号）を受け取るまで子宛にロック要求（ｖｐ，自ノード番号）を行う（ステップ１６２５）。次に子宛にチェーン張り換え要求（ｖｐ，自ノード番号，自ノード番号，子のノード番号）を行い、チェーン張り換え確認応答（ｖｐ，子のノード番号）を受け取る（ステップ１６２６）。この処理によって、子のノードが持つエントリが根のエントリとなる。子の数が２個であった場合には、左の子のエントリが根のエントリである。次に子宛にアンロック要求（ｖｐ）を行う（ステップ１６２７）。次に大域仮想記憶装置１０７宛に大域ページテーブルのエントリの根のノード番号設定要求（ｖｐ，自ノード番号，子のノード番号）を行う（ステップ１６２８）。大域ページテーブルのエントリの根のノード番号設定確認応答（ｖｐ）を受け取り、ステップ１６１９へ進む。当該エントリの子が０であれば（ステップ１６２０で０）、大域仮想記憶装置１０７宛に大域ページテーブルのエントリのロック要求（ｖｐ，自ノード番号）を行い、大域ページテーブルエントリロック確認応答（ｖｐ）を受け取る（ステップ１６２９）。次に大域仮想記憶装置１０７宛に大域ページテーブルのエントリの根のノード番号の設定要求（ｖｐ，自ノード番号，−１）を行い、大域ページテーブルのエントリの根のノード番号設定確認応答（ｖｐ）を受け取る（ステップ１６３０）。次にノード内物理ページ番号２０１で指定される記憶装置１０２内の物理ページの内容を読み取り、大容量記憶装置１０６の物理ページ書き込み要求（ｖｐ，物理ページの内容）を行い、大容量記憶装置１０６の物理ページ書き込み確認応答（ｖｐ）を受け取る（ステップ１６３１）。次に大域ページテーブルのエントリのアンロック要求（ｖｐ，自ノード番号）を行い、大域ページテーブルエントリアンロック確認応答（ｖｐ）を受け取り（ステップ１６３２）、ステップ１６１９へ進む。
【００３９】
（ｈ）更新要求（ｖｐ，要求ノード番号，更新範囲、更新内容）
仮想ページの書き込み処理の途中のステップ１３０６で根をもつノードに対して更新要求が発生する。根をもつノードは当該仮想ページに対応する物理ページの内容を更新した後、すべての子に対して更新要求を発行する。すべての子は当該仮想ページに対応する物理ページの内容を更新した後、孫がいればすべての孫に対して更新要求を発行する。このようにして更新要求はすべての子孫に伝播する。更新要求を受けたすべての子孫は、その親に対して確認応答を返すので、確認応答はノードのトリーを遡り、親に到達する。親のノードは最初に更新要求を発行したノード宛に書き込み完了通知を行う。更新要求の伝播が根を起点とする理由は、すべての物理ページにおいて更新の順番を同一に保つためである。
【００４０】
図１５は、更新要求を処理する仮想記憶操作装置制御部１７０の処理の流れを示すフローチャートである。自ノード又は他ノードから仮想ページｖｐの指定された更新範囲に対して更新要求（ｖｐ，要求ノード，ページ内更新範囲、更新内容）があったとき（ステップ１７００）、トリードディレクトリ１２０にｖｐを仮想ページ番号２０２とするエントリが存在しない場合（ステップ１７０１ＮＯ）はエラーである。エントリが存在する場合（ステップ１７０１ＹＥＳ）、当該エントリの状態２０３が有効３０２となるまで待つ（ステップ１７０２）。次に当該エントリのノード内物理ページ番号２０１に対応する記憶装置１０２内の物理ページをその更新範囲と更新内容に従い書き込み又は更新をする（ステップ１７０３）。次に当該エントリの更新中カウンタ２０７に１を加算し、当該エントリ宛のエントリ追加要求及び当該エントリの対応する物理ページの割り当て解除要求を待たせる（ステップ１７０４）。更新確認応答の処理を複雑にしないためである。次に子がいるなら全ての子宛に更新要求（ｖｐ，要求ノード番号，更新範囲，更新内容）を行う（ステップ１７０５）。次に子がいるなら全ての子から更新確認応答（ｖｐ，要求ノード）を受け取る（ステップ１７０６）。次に当該エントリの更新中カウンタ２０７から１を減ずる（ステップ１７０７）。親がいない場合（ステップ１７０８ＮＯ）はステップ１７１０に進む。親がいる場合（ステップ１７０８ＹＥＳ）には、親宛に更新確認応答（ｖｐ，要求ノード番号）を行い（ステップ１７０９）、処理を終了する。親がいない場合（ステップ１７０８ＮＯ）には、要求ノード宛に書き込み完了通知（ｖｐ）を行い（ステップ１７１０）、処理を終了する。要求ノードが自ノードであればこの通知はない。
【００４１】
（ｉ）エントリ追加要求（ｖｐ，要求ノード番号，コピーの要不要）
物理ページの割り当て処理の途中のステップ１５０９で根のエントリをもつノードに対してエントリ追加要求が発生する。根のエントリをもつノードは、子がいないか子が１個なら当該仮想ページのエントリの左の子又は右の子を要求ノードとし、要求ノードに対して対応するエントリの親を自エントリとするよう要求した後に、要求ノードに対して物理ページ初期化要求を発行して自ノードの物理ページの内容を要求ノードの記憶装置１０２にコピーする。子が２個のとき、根のエントリをもつノードは、左の子又は右の子に対してさらにエントリ追加要求をするだけである。要求を受けた子のノードは、根のエントリをもつノードに代わって上記のように要求ノードを子として登録する処理と物理ページ初期化の処理を行う。また物理ページ割り当て解除の処理の途中のステップ１６２３で根のエントリをもつノードの物理ページの割り当て解除をするとき、根のエントリをもつノードから右の子を要求ノードとして左の子に対してエントリ追加要求が発生する。要求を受けた左の子は、子がいないか子が１個なら当該仮想ページのエントリの左の子又は右の子を要求ノードとし、要求ノードに対して対応するエントリの親を自エントリとするよう要求する。子が２個のとき、要求を受けた左の子は、左の子又は右の子に対してさらにエントリ追加要求をするだけである。
【００４２】
図１６は、エントリ追加を行う仮想記憶操作装置制御部１７０の処理の流れを示すフローチャートである。エントリ追加要求（ｖｐ，要求ノード番号，コピーの要不要）を受けたとき（ステップ１８００）、トリードディレクトリ１２０にｖｐを仮想ページ番号２０２とするエントリが存在しない場合（ステップ１８０１ＮＯ）、エラーとして終了する。エントリが存在する場合（ステップ１８０１ＹＥＳ）、当該エントリの状態２０３が有効３０２かつ更新中カウンタ２０７が０となるまで待つ（ステップ１８０２）。更新中カウンタが０となるまで待つ理由は、更新確認応答の処理を複雑にしないためである。次に当該エントリの状態２０３をロック３０７にする（ステップ１８０３）。子が０個なら（ステップ１８０４で０）、ステップ１８０８へ進む。子が１個なら（ステップ１８０５で１）、ステップ１８０９へ進む。子が２個なら（ステップ１８０５で２）、左の子か右の子をランダムに選択し、エントリ追加要求（ｖｐ，要求ノード番号）を行う（ステップ１８０６）。最後に当該エントリの状態２０３を有効３０２にし（ステップ１８０７）、処理を終了する。子が０個の場合（ステップ１８０４で０）、当該エントリの左の子のノード番号２０５を要求ノード番号にし（ステップ１８０８）、ステップ１８１０へ進む。これにより要求ノードのｖｐのエントリは自ノードのｖｐのエントリの子となる。子が１個の場合（ステップ１８０５で１）、当該エントリの左の子のノード番号２０５か右の子のノード番号２０６の内、自ノード番号に等しい方を要求ノード番号とする（ステップ１８０９）。これにより要求ノードのｖｐのエントリは自ノードのｖｐのエントリの子となる。次に要求ノード宛にチェーン張り換え要求（ｖｐ，自ノード番号，要求ノード番号，自ノード番号）を行い、要求ノードからチェーン張り換え確認応答（ｖｐ，要求ノード番号）を受け取る（ステップ１８１０）。これにより要求ノードのｖｐのエントリの親は自エントリとなる。コピーの要不要が不要なら（ステップ１８１１ＮＯ）、ステップ１８１３へ進む。コピーが要なら（ステップ１８１１ＹＥＳ）、要求ノード宛に物理ページ初期化要求（ｖｐ，自ノード番号，物理ページの内容）を行い、物理ページ初期化確認応答（ｖｐ，要求ノード番号）を受け取る（ステップ１８１２）。これにより要求ノード宛に当該仮想ページの内容を転送する。次に要求ノード宛にアンロック要求（ｖｐ）を行う（ステップ１８１３）。最後に当該エントリの状態２０３を有効３０２にし（ステップ１８１４）、処理を終了する。
【００４３】
（ｊ）物理ページ初期化要求（ｖｐ，要求ノード番号，物理ページの内容）
要求を受けたノードは、要求したノードの物理ページの内容を自ノードの記憶装置１０２内の物理ページにコピーする。物理ページ初期化要求は、物理ページの割り当て処理の途中でエントリ追加要求が発行され、そのエントリ追加要求の処理の途中のステップ１８１２で新たに物理ページの割り当てをするノードに対して発行される。
【００４４】
図１７は、物理ページ初期化を行う仮想記憶操作装置制御部１７０の処理の流れを示すフローチャートである。仮想ページｖｐに対応する物理ページの内容の初期化を要求されたとき（ステップ１９００）、トリードディレクトリ１２０にｖｐを仮想ページ番号２０２とするエントリが存在しないと（ステップ１９０１ＮＯ）エラーとして終了する。エントリが存在するとき（ステップ１９０１ＹＥＳ）、当該エントリの状態２０３がロック３０７でないと（ステップ１９０２ＮＯ）エラーとして終了する。状態がロックであるとき（ステップ１９０２ＹＥＳ）、要求したノードの物理ページの内容に従い、記憶装置１０２のノード内物理ページ番号２０１に対応する物理ページを初期化する（ステップ１９０３）。すなわち要求したノードの物理ページの内容を要求されたノードの物理ページにコピーする。最後に要求したノード宛に物理ページ初期化確認応答（ｖｐ，自ノード番号）を行い（ステップ１９０４）、処理を終了する。
【００４５】
（ｋ）チェーン張り換え要求（ｖｐ，要求ノード番号，ｆｒｏｍ，ｔｏ）
仮想ページ番号ｖｐのエントリ内の親のノード番号、左の子のノード番号、右の子のノード番号の順に指定されたｆｒｏｍ（元のノード番号）に等しいものを１つだけ探し、指定されたｔｏ（置き換えるノード番号）に置き換える。
【００４６】
図１８は、チェーン張り換えを行う仮想記憶操作装置制御部１７０の処理の流れを示すフローチャートである。チェーン張り換え要求（ｖｐ，要求ノード番号，元のノード番号，置き換えるノード番号）を受けたとき（ステップ２０００）、トリードディレクトリ１２０に要求仮想ページ番号ｖｐをもつエントリが存在しないと（ステップ２００１ＮＯ）、エラーとして終了する。エントリが存在するとき（ステップ２００１ＹＥＳ）、当該エントリの状態２０３がロック３０７になるまで待つ（ステップ２００２）。通常はすでにロック３０７である。次に当該エントリについて親のノード番号２０４、左の子のノード番号２０５、右の子のノード番号２０６の順にｆｒｏｍ（元のノード番号）に等しいものを１つだけ探し、ｔｏ（置き換えるノード番号）に置き換える（ステップ２００３）。最後に要求ノード宛にチェーン張り換え確認応答（ｖｐ，自ノード番号）を行い（ステップ２００４）、処理を終了する。
【００４７】
（ｌ）ロック要求（ｖｐ，要求ノード番号）
当該エントリの状態が有効なら状態をロックにする。
【００４８】
図１９は、ロック要求を処理する仮想記憶操作装置制御部１７０の処理の流れを示すフローチャートである。仮想ページ番号ｖｐへ要求ノードからロック要求（ｖｐ，要求ノード番号）がされたとき（ステップ２１００）、トリードディレクトリ１２０にｖｐを仮想ページ番号２０２とするエントリが存在しないと（ステップ２１０１ＮＯ）、エラーとして終了する。エントリが存在するとき（ステップ２１０１ＹＥＳ）、当該エントリの状態２０３が有効でないなら（ステップ２１０２ＮＯ）、ステップ２１０５へ進む。状態が有効であるとき（ステップ２１０２ＹＥＳ）、当該エントリの状態２０３をロック３０７にする（ステップ２１０３）。最後に要求ノード宛にロック要求確認応答（ｖｐ，自ノード番号）を行い（ステップ２１０４）、処理を終了する。状態２０３が有効でないとき（ステップ２１０２ＮＯ）、要求ノード宛にロック要求の否定応答（ｖｐ，自ノード番号）を行い（ステップ２１０５）、処理を終了する。
【００４９】
（ｍ）アンロック要求（ｖｐ）
当該エントリの状態をロックから有効に変更する。
【００５０】
図２０は、アンロック要求を処理する仮想記憶操作装置制御部１７０の処理の流れを示すフローチャートである。仮想ページ番号ｖｐへアンロック要求（ｖｐ）がされたとき（ステップ２２００）、トリードディレクトリ１２０にｖｐを仮想ページ番号２０２とするエントリが存在しないと（ステップ２２０１ＮＯ）、エラーとして終了する。エントリが存在するとき（ステップ２２０１ＹＥＳ）、当該エントリの状態２０３がロック３０７でないなら（ステップ２２０２ＮＯ）、エラーとして終了する。状態がロックであれば（ステップ２２０２ＹＥＳ）、当該エントリの状態２０３を有効３０２にし（ステップ２２０３）、処理を終了する。
【００５１】
（ｎ）物理ページ全割り当て解除要求（ｖｐ，要求ノード番号）
仮想ページの割り当て解除の処理の途中のステップ１１０８で根のエントリをもつノードに対して発行される。根をもつノードは、すべての子に対して物理ページ全割り当て解除要求を発行し、すべての子からの確認応答を受けたとき、大域ページテーブル１０５の当該仮想ページのエントリを削除する要求を発行し、トリードディレクトリ１２０の当該エントリを無効にする。物理ページ全割り当て解除要求を受けた子のノードは、親宛に確認応答を行い、トリードディレクトリ１２０の当該エントリを無効にする。
【００５２】
図２１は、物理ページ全割り当て解除を行う仮想記憶操作装置制御部１７０の処理の流れを示すフローチャートである。物理ページ全割り当て解除要求（ｖｐ，要求ノード番号）を受けたとき（ステップ２３００）、チェーンドディレクトリ１２０にｖｐを仮想ページ番号２０２とするエントリが存在しないと（ステップ２３０１ＮＯ）、エラーとして終了する。エントリが存在するとき（ステップ２３０１ＹＥＳ）、当該エントリの状態２０３がロック３０７になるまで待つ（ステップ２３０２）。物理ページ全割り当て解除要求前に親がロック要求を行っているはずである。次に当該エントリの状態２０３を割り当て解除中３０３とする（ステップ２３０３）。次に全ての子をロックする（ステップ２３０４）。すなわち全ての子からロック確認応答（ｖｐ，子のノード番号）を受け取るまで、全ての子宛にロック要求（ｖｐ，自ノード番号）を行う。次に全ての子宛に物理ページ全割り当て解除要求（ｖｐ，自ノード番号）を行う（ステップ２３０５）。次に全ての子から物理ページ全割り当て解除確認応答（ｖｐ，子のノード番号）を受け取る（ステップ２３０６）。当該エントリに親がいない場合（ステップ２３０７ＮＯ）は、ステップ２３１０へ進む。親がいる場合（ステップ２３０７ＹＥＳ）、親宛に物理ページ全割り当て解除確認応答（ｖｐ，自ノード番号）を行う（ステップ２３０８）。最後にトリードディレクトリ１２０の当該エントリの状態２０３を無効３００とし（ステップ２３０９）、処理を終了する。親がいない場合（ステップ２３０７ＮＯ）、根のエントリの処理として、大域仮想記憶装置１０７宛に大域ページテーブルのエントリの削除要求（ｖｐ，自ノード番号）を行う（ステップ２３１０）。大域ページテーブルのエントリの削除確認応答（ｖｐ）を受け取って処理を終了する。ｖｐに対応する大容量記憶装置内の物理ページの解除は大域仮想記憶装置１０７が行う。
【００５３】
（ｏ）大域記憶装置１０７の動作
大域記憶装置１０７の大域記憶装置制御部１８０は、大域ページテーブルのエントリの取得要求、大域ページテーブルのエントリの作成要求、大域ページテーブルのエントリの削除要求、大域ページテーブルのエントリのロック要求、大域ページテーブルのエントリのアンロック要求、大域ページテーブルのエントリの根のノード番号の設定要求、大容量記憶装置の物理ページ書き込み要求及び大容量記憶装置の物理ページの読み取り要求を受け付ける。以下各要求を受けたときの大域記憶装置制御部１８０の処理について説明する。
【００５４】
（ｉ）大域ページテーブルのエントリの取得要求（ｖｐ，要求ノード番号）
仮想ページ番号ｖｐのエントリ６００を大域ページテーブル１０５から読み取る。大域ページテーブル１０５から仮想ページ番号ｖｐのエントリを読み取り、大域ページテーブルエントリ（ｖｐ，エントリの内容）を要求ノード宛に返送する。仮想ページ番号ｖｐのエントリが存在しない場合は大域ページテーブルエントリ否定応答（ｖｐ）を要求ノード宛に返送する。
【００５５】
（ｉｉ）大域ページテーブルのエントリの作成要求（ｖｐ，要求ノード番号）
仮想ページ番号ｖｐのエントリが存在する場合は、大域ページテーブルエントリ作成否定応答（ｖｐ）を要求ノード宛に返送する。仮想ページ番号ｖｐのエントリ６００を大域ページテーブル１０５に作成する。大容量記憶装置１０６内に物理ページを割り付け、当該物理ページ番号を大容量記憶装置内物理ページ番号６０３に登録する。要求ノード宛に大域ページテーブルエントリ作成確認応答（ｖｐ）を返送する。
【００５６】
（ｉｉｉ）大域ページテーブルのエントリの削除要求（ｖｐ，要求ノード番号）仮想ページ番号ｖｐのエントリ６００の大容量記憶装置内物理ページ番号６０３に示される領域を大容量記憶装置１０６から削除する。仮想ページ番号ｖｐのエントリ６００を大域ページテーブル１０５から削除し、要求ノード宛に大域ページテーブルエントリエントリ削除確認応答（ｖｐ）を返送する。
【００５７】
（ｉｖ）大域ページテーブルのエントリのロック要求（ｖｐ，要求ノード番号）
仮想ページ番号ｖｐのエントリ６００のロック６０４が０なら、ロック６０４を１にし、要求ノード宛に大域ページテーブルエントリロック確認応答（ｖｐ）を行う。仮想ページ番号ｖｐのエントリ６００のロック６０４が１なら、要求ノード宛に大域ページテーブルエントリロック否定確認応答（ｖｐ）を行う。
【００５８】
（ｖ）大域ページテーブルのエントリのアンロック要求（ｖｐ，要求ノード番号）
仮想ページ番号ｖｐのエントリ６００のロック６０４を０にし、要求ノード宛に大域ページテーブルエントリアンロック確認応答（ｖｐ）を行う。
【００５９】
（ｖｉ）大域ページテーブルのエントリの根のノード番号の設定要求（ｖｐ，要求ノード番号，根のノード番号）
仮想ページ番号ｖｐのエントリ６００の根のエントリを持つノード番号６０２を根のノード番号とし、要求ノード宛に大域ページテーブルのエントリの根のノード番号設定確認応答（ｖｐ）を行う。
【００６０】
（ｖｉｉ）大容量記憶装置の物理ページ書き込み要求（ｖｐ，要求ノード番号，物理ページの内容）
仮想ページ番号ｖｐのエントリ６００の大容量記憶装置内物理ページ番号６０３に示される大容量記憶装置１０６の領域を、物理ページの内容に書き換え、要求ノード宛に大容量記憶装置の物理ページ書き込み確認応答（ｖｐ）を行う。
【００６１】
（ｖｉｉｉ）大容量記憶装置の物理ページ読み取り要求（ｖｐ，要求ノード番号）
仮想ページ番号ｖｐのエントリ６００の大容量記憶装置内物理ページ番号６０３に示される大容量記憶装置１０６の物理ページの内容を読み取り、要求ノード宛に大容量記憶装置の物理ページ読み取り結果（ｖｐ，物理ページの内容）を返送する。
【００６２】
本実施形態によれば、同一の仮想ページを共有する複数の物理ページが２分木を構成し、２分木の各分枝に沿って更新処理が同時に進行するため、一つの物理ページの更新に伴う物理ページの内容の一貫性制御に費やす時間は、最良時には仮想ページを共有する物理ページ数の２を底とする対数に比例する時間に短縮される。またチェーンとなるノード番号は、総ノード数の２を底とする対数で表現できるので、トリードディレクトリの大きさが総ノード数の対数に比例し、ノードの台数増加による台数拡張性に優れる。また物理ページの更新要求が２分木の各分枝に沿って伝播すること、および更新に対する確認応答が２分木の２つの子からの応答がそろってから親に応答を返すので、ネットワークの負荷の集中が避けられる。また共有に無関係なノードへの更新要求は発生しない。
【００６３】
なお上記実施形態では、トリードディレクトリのエントリが子へのチェーンを２つもつ場合の例を示したが、子へのチェーンを３つ以上もつ場合もエントリが子のノード番号を３つ以上もつことによって同様に実施可能である。また上記実施形態は仮想記憶及び物理記憶の単位をページとしたが、キャッシュライン（例えば３２バイト）としても本発明を適用できる。さらにクロスバネットワーク１０４の代わりにバスやメッシュ等任意のトポロジのネットワークを用いても本発明を適用できるが、送信元及び送信先の独立な通信が相互に影響しないという点からクロスバネットワークが望ましい。
【００６４】
（２）第２の実施形態
図２２は、第２の実施形態の並列計算機のシステム構成を示す図である。大域ページテーブル１０５、大域ページテーブル操作部１５０、大容量記憶装置１０６、大容量記憶装置操作部１６０及び大域記憶装置制御部１８０は、単一のノード１００内に集中して設けても良いし、複数のノード１００内に分散して設けても良い。単一のノード内にある場合、例えばノード０にある場合は、大域ページテーブル１０５又は大容量記憶装置１０６の読み取り及び書き込みの要求は、ノード０の通信媒体操作部１４０宛に行われる。ノード０の通信媒体操作部１４０は、要求が仮想記憶操作装置１０３宛の要求と大域記憶装置１０７宛の要求とを区別可能である。なぜならば仮想記憶操作装置１０３宛に可能な要求と大域記憶装置１０７宛に可能な要求とは異なるからである。大域ページテーブル１０５、大域ページテーブル操作部１５０、大容量記憶装置１０６及び大容量記憶装置操作部１６０を、Ｐ個すべてのノードに分散配置することは、各ノードが担当する仮想ページ番号をあらかじめ固定にすることで可能である。例えばノードＩが割り当てられる仮想ページを、仮想ページ番号をノード数Ｐで割った余りがＩとなるような仮想ページとする方法が考えられる。
【００６５】
（３）仮想記憶操作装置制御部１７０の詳細構成
図２３は、第１及び第２の実施形態の仮想記憶操作装置制御部１７０の内部構成を示す図である。仮想記憶操作装置制御部１７０中、トリードディレクトリ検索部７００及び書き込み中テーブル検索部７０１はハードウェアのみで構成される。その他の制御部７０２は、ハードウェア及びプログラム内蔵の処理装置で構成される。その他の制御部７０２がトリードディレクトリ検索部７００に仮想ページ番号を入力すると、トリードディレクトリ検索部７００からトリードディレクトリ１２０のエントリの内容が得られる。またその他の制御部７０２が書き込み中テーブル検索部７０１に仮想ページ番号を入力すると、その仮想ページ番号が登録されていれば存在を示す信号が得られる。
【００６６】
図２４は、トリードディレクトリ検索部７００のブロック図である。トリードディレクトリ検索部７００は仮想ページ番号を入力とし、当該仮想ページ番号のトリードディレクトリエントリおよび有効情報を出力する。有効情報は１ビットである。有効情報が１の場合には入力された仮想ページ番号のトリードディレクトリエントリが出力されたことを表し、０の場合には入力された仮想ページ番号のトリードディレクトリエントリが存在しないことを表す。トリードディレクトリ検索部分７００は、比較器７１０、有効性判定回路７１１、２入力ＡＮＤ回路７１２及び選択回路７１３から構成される。以上の構成要素はすべてハードウェアのみで構成される。比較器７１０は二つの仮想ページ番号を入力とし、両者の値が一致する場合は１を出力し、一致しない場合は０を出力する。有効性判定回路７１１はトリードディレクトリエントリ２００の状態２０３を入力とし、状態２０３が無効３００の場合には０を出力し、それ以外の場合には１を出力する。
【００６７】
図２５は、有効性判定回路７１１の真理値表を示す図である。２入力ＡＮＤ回路７１２は２ビットを入力とし、２ビットとも１の場合に１を出力し、それ以外の場合は０を出力する。選択回路７１３は、Ｍ個のトリードディレクトリエントリから一つを選択する回路であり、Ｍ個の１ビットとＭ個のトリードディレクトリエントリを入力とする。１ビットがすべて０の場合は有効情報０とダミーのトリードディレクトリエントリを出力し、それ以外の場合は有効情報１と対応するトリードディレクトリエントリを出力する。
【００６８】
図２６は、書き込み中テーブル検索部７０１のブロック図である。書き込み中テーブル検索部７０１は、仮想ページ番号を入力とし、書き込み中テーブルヒット情報を出力する。書き込み中テーブルヒット情報は、０または１の値を取り得る。入力された仮想ページ番号が書き込み中テーブルに登録されている場合には書き込み中テーブルヒット情報は１となり、それ以外の場合には書き込み中テーブルヒット情報は０となる。書き込み中テーブル検索部７０１は、比較器７１０、２入力ＡＮＤ回路７１２及びＫ入力ＯＲ回路７２０から構成される。以上の構成要素はすべてハードウェアのみで構成される。Ｋ入力ＯＲ回路７２０はＫビットを入力とし、入力ビットがすべて０の場合には０を出力し、それ以外の場合には１を出力する。
【００６９】
その他の制御部７０２は、上記の仮想ページの割り当て、仮想ページの割り当て解除、仮想ページの読み取り、仮想ページの書き込み、書き込み同期の処理及びこれらに付随して発生する処理を実現する部分である。計算機の性能上の理由から、少なくとも仮想ページの読み取り及び仮想ページの書き込みの主たる処理はハードウェアによって実現するのが望ましい。これら以外の処理部は、ハードウェアによって実現するか又はプログラム内蔵の処理装置によって実現可能である。仮想記憶操作装置制御部１７０で行う複数の処理は並列処理が可能である。並列処理は、ハードウェアのみで実現する部分は複数の処理資源を設けることによって可能であり、プログラムによって実現する部分はマルチタスクの機能によって可能である。
【００７０】
（４）第３の実施形態
トリードディレクトリ方式における一貫性制御に費やす時間は、木の平衡の度合に依存する。根のエントリから分枝する子孫の数が均等であれば平衡しているのであり、子孫の数の片寄りが大きい程平衡の度合が悪い。木が完全に平衡している場合が最良であり、一貫性制御に費やす時間は、仮想ページを共有する物理ページ数のｒを底とする対数に比例する時間となる。ここでｒは親から分枝する子の数である。これとは逆に木が単なるチェーンとなっている場合が最悪であり、一貫性制御に費やす時間は、仮想ページを共有する物理ページ数に比例する時間となる。このため木の平衡を保つことがトリードディレクトリ方式で高性能を実現するために重要である。
【００７１】
木の平衡を保つ機構の説明をする前にまず言葉の定義をする。あるエントリの子孫とは、当該エントリの子のエントリと当該エントリの子のエントリの子孫との和集合のことをいう。あるエントリの先祖とは、当該エントリの親のエントリおよび当該エントリの親のエントリの先祖の和集合のことをいう。木の平衡を保つため、第１及び第２の実施形態の仮想記憶操作装置１０３を拡張し、トリードディレクトリエントリ１２０のチェーン毎に子孫数を保持するカウンタを付加する。この子孫数とは、チェーン以下の子孫の数を表し、チェーンの指し示すエントリが存在しない場合には０であり、チェーンの指し示すエントリが存在する場合にはチェーンの指し示すエントリの子孫の数（各チェーンに対応する子孫数の和）＋１である。すなわちこの子孫数はチェーンの指し示すエントリ以下の部分木のエントリ数である。あるノード計算機が物理ページ割り当てを行った結果としてエントリ追加要求が発生した時に、このチェーンに対応する子孫数を評価して子孫数の小さい子宛にエントリ割り当て要求を転送することにより、ｒ進木の平衡を保つ。この子孫数を追加したことにより、子孫数が変化した時に子孫数を表すカウンタの値を正しく保つ処理を行う必要がある。以下にこの処理の概要を説明する。
【００７２】
あるノードにおいて物理ページ割り当て解除を行った時に、子孫数を減少させる要求を当該物理ページに対応するトリードディレクトリエントリの親宛に転送する。また子孫数を減少させる要求を受け取ったノードにおいて要求されているエントリの対応する子孫数を減少させた後、当該トリードディレクトリエントリの親宛に子孫数を減少させる要求を行う。以上の処理は、根のエントリまで到達するまで繰り返される。上記処理により子孫数を保持するカウンタの値が正しく保たれる。この子孫数を減少させる要求は、物理ページ割り当て解除の対象となるエントリ及びその先祖すべてを同時にはロックしない。子孫数を減少させる要求により同時にロックされるエントリは高々２エントリだけであり、子孫数を正しく保つ処理が計算機システム全体に与えるオーバヘッドは小さい。
【００７３】
図２７は、第３の実施形態の並列計算機のシステム構成を示す図である。図１の並列計算機の各ノード計算機１００中の仮想記憶操作装置１０３にチェーン張り換え中テーブル１９０を付加し、トリードディレクトリ１２０に子孫数を付加した並列計算機の構成図である。
【００７４】
図２８は、子孫数を付加したトリードディレクトリ１２０の構成を示す図である。図２と比較して左の子孫数２０８と右の子孫数２０９が追加されている。左の子孫数２０８は、左の子の左の子孫数と左の子の右の子孫数との和に１を加えたものに等しい。左の子がいない場合は左の子孫数２０８は０である。同様に右の子孫数２０９は、右の子の左の子孫数と左の子の右の子孫数との和に１を加えたものに等しい。右の子がいない場合は右の子孫数２０９は０である。
【００７５】
図２９は、チェーン張り換え中テーブル１９０の構成を示す図である。チェーン張り換え中テーブル１９０は、複数のエントリ８０１から構成される。各エントリ８０１は、仮想ページ番号８０２と有効ビット８０３とから構成される。有効ビットは無効（０）または有効（１）の値を取り得る。有効ビット８０３の値が１の場合には、仮想ページ番号８０２の仮想ページ番号がチェーン張り換え中テーブル１９０に登録されているとする。チェーン張り換え中テーブル１９０に仮想ページ番号が登録されている仮想ページの物理ページ割り当て解除要求は、チェーン張り替えが完了するまで待たされる。
【００７６】
処理装置１０１が仮想記憶操作装置１０３に要求する仮想ページの割り当て、仮想ページの割り当て解除、仮想ページの読み取り、仮想ページの書き込み及び書き込みの同期のすべての仮想ページアクセスは、物理ページの割り当てがステップ１５００からではなくステップ２４００から開始することと、物理ページの割り当て解除がステップ１６００からではなくステップ２５００から開始すること以外は第１及び第２の実施形態と同じである。仮想記憶操作装置１０３に子孫数を追加しても処理装置１０１からは仮想記憶操作装置１０３は以前と等価に見える。
【００７７】
（ａ）物理ページの割り当て（ｖｐ）
仮想ページｖｐに対応する物理ページを割り当てる操作である。
【００７８】
図３０は、物理ページの割り当てを行う仮想記憶操作装置制御部１７０の処理の流れを示すフローチャートである。ステップ１２０３で物理ページ割り当て（ｖｐ）が要求されたとき（ステップ２４００）、トリードディレクトリ１２０にｖｐを仮想ページとするエントリが存在する場合（ステップ２４０１ＹＥＳ）は終了する。エントリが存在しない場合（ステップ２４０１ＮＯ）、大域仮想記憶装置１０７宛に大域ページテーブルのエントリの取得要求（ｖｐ，自ノード番号）を行い、エントリ（ｖｐ，エントリの内容）もしくは否定応答（ｖｐ）を受け取る。否定応答（ｖｐ）を受け取った場合（ステップ２４０２ＮＯ）は、ステップ２４１０に進む。エントリを取得した場合（ステップ２４０２ＹＥＳ）には、トリードディレクトリ１２０中に状態２０３が無効３００のエントリが存在する場合（ステップ２４０３ＹＥＳ）は、ステップ２４０５へ進む。無効のエントリが存在しない場合（ステップ２４０３ＮＯ）には、状態２０３が有効３０２なエントリ（その仮想ページ番号をｖｐ’とする）を１つ選択し、そのエントリに対して物理ページ割り当て解除（ｖｐ’）の処理を行う（ステップ２４０４）。無効のエントリを１つ選択した状態で、当該エントリの仮想ページ番号２０２にｖｐを書き込み、状態２０３を割り当て中３０１とする（ステップ２４０５）。次に大域仮想記憶装置１０７に大域ページテーブルのエントリの取得要求（ｖｐ，自ノード番号）を行い、ｖｐのエントリを得る。大域ページテーブル１０５のｖｐのエントリの根のノード番号が−１、すなわちどのノード１００も当該仮想ページに関するトリードディレクトリのエントリ及び物理ページを持っていないなら（ステップ２４０６ＹＥＳ）、ステップ２４１１へ進む。根をもつノードが存在するなら（ステップ２４０６ＮＯ）、トリードディレクトリ１２０の当該エントリの親のノード番号２０４、左の子のノード番号２０５及び右の子のノード番号２０６をすべて自ノード番号にし、左の子孫数２０８を０にし、右に子孫数２０９を０にする（ステップ２４０７）。次にトリードディレクトリ１２０の当該エントリの状態２０３をロック３０７にする（ステップ２４０８）。次に根のエントリをもつノード宛にエントリ追加要求（ｖｐ，自ノード番号，コピー要，１）を行い（ステップ２４０９）、処理を終了する。このエントリ追加要求は、自ノード（引数２）が仮想ページｖｐ（引数１）の共有を要求しており、自エントリの左の子孫数と右の子孫数との和に１を加えたものが１（引数４）であり、仮想ページｖｐの内容を物理ページにコピーすることが必要である（引数３）ことを意味する。最終的にエントリ追加を行うノードが自ノード宛に親のノード番号及び仮想ページの内容を通知し、自ノードの当該エントリのロックを解除する。大域ページテーブル１０５中にエントリが存在しない場合（ステップ２４０２ＮＯ）には、保護エラーを処理装置１０１に通知し（ステップ２４１０）、処理を終了する。ステップ１２０２でチェック済みであるため、このエラーは発生しないはずである。根をもつノードが存在しないなら（ステップ２４０６ＹＥＳ）、大域仮想記憶装置１０７に大域ページテーブルのエントリのロック要求（ｖｐ，自ノード番号）を行う。肯定応答（ｖｐ）が得られたら（ステップ２４１１ＹＥＳ）、ステップ２４１２に進む。否定応答（ｖｐ）が得られた場合（ステップ２４１１ＮＯ）には、当該エントリの状態２０３を有効３０２にし、一定時間待った後、ステップ２４０２に戻る。ほぼ同時に複数のノード計算機が同一の仮想ページｖｐの物理ページを割り当てようとしたときなどにこのような状況が起こる。肯定応答が得られたら（ステップ２４１１ＹＥＳ）、当該トリードディレクトリの親のノード番号２０４、左の子のノード番号２０５及び右の子のノード番号２０６を自ノード番号にし、左の子孫数２０８を０にし、右の子孫数２０９を０にする（ステップ２４１２）。次に大容量記憶装置１０６から仮想ページの内容を読み取ってその内容を自ノードの当該仮想ページに対応する物理ページにコピーする（ステップ２４１３）。具体的には大域記憶装置１０７宛に大容量記憶装置の物理ページの読み取り要求（ｖｐ，自ノード番号）を行い、大容量記憶装置の物理ページ読み取り結果（ｖｐ，物理ページの内容）を受け取り、ノード内物理ページ番号２０１に対応する記憶装置１０２の物理ページに受け取った内容を書き込む。次に大域仮想記憶装置１０７に大域ページテーブルのエントリの根のノード番号の設定要求（ｖｐ，自ノード番号，自ノード番号）を行い、大域ページテーブルのエントリの根のノード番号の設定確認応答（ｖｐ）を受け取る（ステップ２４１４）。次にトリードディレクトリ１２０の当該エントリの状態２０３を有効３０２とする（ステップ２４１５）。最後に大域仮想記憶装置１０７に大域ページテーブルのエントリのアンロック要求（ｖｐ，自ノード番号）を行ってそのロックを０にし、アンロック確認応答（ｖｐ）を受け取って（ステップ２４１６）、処理を終了する。
【００７９】
（ｂ）物理ページの割り当て解除（ｖｐ）
仮想ページｖｐに対応する物理ページの割り当て解除要求をする操作である。
【００８０】
図３１及び図３２は、物理ページの割り当て解除を行う仮想記憶操作装置制御部１７０の処理の流れを示すフローチャートである。ステップ１５０４で物理ページの割り当て解除（ｖｐ）が要求されたとき（ステップ２５００）、トリードディレクトリ１２０にｖｐを仮想ページ番号２０２とするエントリが存在しない場合（ステップ２５０１ＮＯ）は終了する。エントリが存在する場合（ステップ２５０１ＹＥＳ）、当該エントリの状態２０３が有効３０２かつ更新中カウンタ２０７が０かつチェーン張り換え中テーブルからｖｐのエントリが無くなるまで待つ（ステップ２５０２）。更新中カウンタが０になるまで待つのは、更新中のノードの確認応答処理が複雑となるのを避けるためである。チェーン張り換え中テーブルからｖｐのエントリが無くなるまで待つのは、子孫数を正しく保つためであり、当該エントリのチェーン張り換え処理が完了するまで当該エントリを除去するのを待つ必要があるためである。次に当該エントリの状態２０３を割り当て解除中３０３とする（ステップ２５０３）。当該エントリが根のエントリの場合（ステップ２５０４ＹＥＳ）は、ステップ２５２０へ進む。根のエントリでない場合（ステップ２５０４ＮＯ）は、親宛にロック要求（ｖｐ，自ノード番号）を行った結果、ロック否定応答（ｖｐ，親のノード番号）を受け取る場合（ステップ２５０５ＮＡＫ）はステップ２５１３へ進む。肯定応答を受け取る場合（ステップ２５０５ＡＣＫ）、当該エントリの子が０個なら（ステップ２５０６で０）、ステップ２５１４へ進む。子が０個でなければ（ステップ２５０６で≠０）、全ての子からロック確認応答（ｖｐ，子のノード番号）を受け取るまですべての子宛にロック要求（ｖｐ，自ノード番号）を行う（ステップ２５０７）。当該エントリの子が１個なら（ステップ２５０８で１）、ステップ２５１５へ進む。子が２個なら（ステップ２５０８で２）、親エントリの子を自エントリの代わりに自エントリの左の子にする。すなわち親宛にチェーン張り換え要求（ｖｐ，自ノード番号，自ノード番号，左の子のノード番号）を行い、チェーン張り換え確認応答（ｖｐ，親のノード番号）を受け取る（ステップ２５０９）。詳しい説明はチェーン張り換え要求処理（ステップ２７００以降）で行うが、親エントリのチェーン張り換え処理において、親エントリの子孫数（自エントリにマッチしていた方）から１が減らされる。このチェーン張り換え要求により、親エントリの親エントリ、そのまた親エントリというように、根のエントリまでチェーン張り換え要求が伝搬し、子孫数は正しく保たれる。次に左の子の親を自エントリの親にする。すなわち左の子宛にチェーン張り換え要求（ｖｐ，自ノード番号，自ノード番号，親のノード番号）を行い、チェーン張り換え確認応答（ｖｐ，左の子のノード番号）を受け取る（ステップ２５１０）。次に左の子宛にアンロック要求（ｖｐ）を行う（ステップ２５１１）。次に左の子宛にエントリ追加要求（ｖｐ，右の子のノード番号，コピー不要，右の子孫数）を行い（ステップ２５１２）、ステップ２５１８へ進む。このエントリ追加要求は、右の子（引数２）が仮想ページｖｐ（引数１）の共有をしており、右の子のエントリの左の子孫数と右の子孫数との和に１を加えたものが右の子孫数（引数４）であり、仮想ページｖｐの内容を物理ページにコピーすることが不要である（引数３）ことを意味する。親宛にロック要求を行って否定応答を受けたとき（ステップ２５０５ＮＡＫ）、当該エントリの状態２０３を有効３０２とし、一定時間待った後にステップ２５０１へ戻る（ステップ２５１３）。自エントリが親宛にロック要求を行っているときに親エントリが自エントリ宛にロック要求を行う場合にも、デッドロックが発生しないようにするためである。当該エントリの子が０のとき（ステップ２５０６で０）、親宛にチェーン張り換え要求（ｖｐ，自ノード番号，自ノード番号，親のノード番号）を行い、親からチェーン張り換え確認応答（ｖｐ，親のノード番号）を受け取る（ステップ２５１４）。詳しい説明はチェーン張り換え要求処理（ステップ２７００以降）で行うが、親エントリのチェーン張り換え処理において、親エントリの子孫数（自エントリにマッチしていた方）から１が減らされる。このチェーン張り換え要求により、親エントリの親エントリ、そのまた親エントリというように根のエントリまでチェーン張り換え要求が伝搬し、子孫数は正しく保たれる。当該エントリの子が１のとき（ステップ２５０８で１）、自エントリのかわりに自エントリの子を親の子にする。すなわち親宛にチェーン張り換え要求（ｖｐ，自ノード番号，自ノード番号，子のノード番号）を行い、チェーン張り換え確認応答（ｖｐ，親のノード番号）を受け取る（ステップ２５１５）。詳しい説明はチェーン張り換え要求処理（ステップ２７００以降）で行うが、親エントリのチェーン張り換え処理において、親エントリの子孫数（自エントリにマッチしていた方）から１が減らされる。このチェーン張り換え要求により、親エントリの親エントリ、そのまた親エントリというように、根のエントリまでチェーン張り換え要求が伝搬し、子孫数は正しく保たれる。次に子がいれば子宛にチェーン張り換え要求（ｖｐ，自ノード番号，自ノード番号，親のノード番号）を行い、チェーン張り換え確認応答（ｖｐ，子のノード番号）を受け取る（ステップ２５１６）。次に左の子宛にアンロック要求（ｖｐ）を行う（ステップ２５１７）。ステップ２５１８で親宛にアンロック要求（ｖｐ）を行い、トリードディレクトリ１２０の当該エントリの状態２０３を無効３００とし（ステップ２５１９）、処理を終了する。当該エントリが根のエントリの場合（ステップ２５０４ＹＥＳ）、当該エントリの子が０個なら（ステップ２５２０で０）、ステップ２５２９へ進む。子が０個でなければ（ステップ２５２０で≠０）、当該エントリの子が１個なら（ステップ２５２１で１）、ステップ２５２５へ進む。子が２個なら（ステップ２５２１で２）、右の子からロック確認応答（ｖｐ，右の子のノード番号）を受け取るまで右の子宛にロック要求（ｖｐ，自ノード番号）を行う（ステップ２５２２）。次に自エントリの右の子を左の子の子孫にする。すなわち左の子宛にエントリ追加要求（ｖｐ，右の子のノード番号，コピー不要，右の子孫数）を行う（ステップ２５２３）。このエントリ追加要求は、右の子（引数２）が仮想ページｖｐ（引数１）の共有をしており、右の子のエントリの左の子孫数と右の子孫数との和に１を加えたものが右の子孫数（引数４）であり、仮想ページｖｐの内容を物理ページにコピーすることが不要である（引数３）ことを意味する。次に自エントリの右の子のノード番号２０５を自ノード番号にする（ステップ２５２４）。次に子からロック確認応答（ｖｐ，子のノード番号）を受け取るまで子宛にロック要求（ｖｐ，自ノード番号）を行う（ステップ２５２５）。次に子宛にチェーン張り換え要求（ｖｐ，自ノード番号，自ノード番号，子のノード番号）を行い、チェーン張り換え確認応答（ｖｐ，子のノード番号）を受け取る（ステップ２５２６）。この処理によって、子のエントリが根のエントリとなる。子の数が２個であった場合には、左の子のエントリが根のエントリである。次に子宛にアンロック要求（ｖｐ）を行う（ステップ２５２７）。次に大域仮想記憶装置１０７宛に大域ページテーブルのエントリの根のノード番号設定要求（ｖｐ，自ノード番号，子のノード番号）を行う（ステップ２５２８）。大域ページテーブルのエントリの根のノード番号設定確認応答（ｖｐ）を受け取り、ステップ２５１９へ進む。当該エントリの子が０であれば（ステップ２５２０で０）、大域仮想記憶装置１０７宛に大域ページテーブルのエントリのロック要求（ｖｐ，自ノード番号）を行い、大域ページテーブルエントリロック確認応答（ｖｐ）を受け取る（ステップ２５２９）。次に大域仮想記憶装置１０７宛に大域ページテーブルのエントリの根のノード番号の設定要求（ｖｐ，自ノード番号，−１）を行い、大域ページテーブルのエントリの根のノード番号設定確認応答（ｖｐ）を受け取る（ステップ２５３０）。次にノード内物理ページ番号２０１で指定される記憶装置１０２内の物理ページの内容を読み取り、大容量記憶装置１０６の物理ページ書き込み要求（ｖｐ，物理ページの内容）を行い、大容量記憶装置１０６の物理ページ書き込み確認応答（ｖｐ）を受け取る（ステップ２５３１）。次に大域ページテーブルのエントリのアンロック要求（ｖｐ，自ノード番号）を行い、大域ページテーブルエントリアンロック確認応答（ｖｐ）を受け取り（ステップ２５３２）、ステップ２５１９へ進む。
【００８１】
（ｃ）エントリ追加要求（ｖｐ，要求ノード番号，コピーの要不要，子孫数）
物理ページの割り当て（ステップ１５０９）により発生する。当該エントリの子が１以下の場合は、要求ノードを子として登録する。子が２の場合は子にエントリ追加要求を行う。引数のｖｐは共有を要求している仮想ページ番号、要求ノード番号は共有を要求しているノード計算機番号である。コピーの要不要は、要求ノードが保持しているｖｐのエントリが対応する物理ページの内容が仮想ページｖｐの内容に等しくない場合には要であり、要求ノードが保持しているｖｐのエントリが対応する物理ページの内容が仮想ページｖｐの内容に等しい場合には不要である。子孫数は要求ノードが保持するｖｐのエントリの左の子孫数と右の子孫数に１を加えた値である。
【００８２】
処理概要は以下の通りである。
（ｉ）左の子がいない場合、要求ノードを左の子とし、左の子孫数を設定する。
（ｉｉ）左の子はいるが右の子がいない場合、要求ノードを右の子とし、右の子孫数を設定する。
（ｉｉｉ）左の子も右の子もいる場合で、左の子孫数≦右の子孫数の場合、同じエントリ追加要求を左の子宛に転送する。
（ｉｖ）左の子も右の子もいる場合で、左の子孫数＞右の子孫数の場合、同じエントリ追加要求を右の子宛に転送する。
【００８３】
第１及び第２の実施形態では、子の数が２の場合には左の子か右の子をランダムに選択し、エントリ追加要求を転送していたが、この実施形態では上記（ｉｉｉ）及び（ｉｖ）の処理によって子孫数の小さい方の子にエントリ追加要求を行うことにより木の平衡を保つ。
【００８４】
図３３は、エントリ追加要求の処理を行う仮想記憶操作装置制御部１７０の処理の流れを示すフローチャートである。エントリ追加要求（ｖｐ，要求ノード番号，コピーの要不要，子孫数）を受けたとき（ステップ２６００）、トリードディレクトリ１２０にｖｐを仮想ページ番号２０２とするエントリが存在しない場合（ステップ２６０１ＮＯ）、エラーとして終了する。エントリが存在する場合（ステップ２６０１ＹＥＳ）、当該エントリの状態２０３が有効３０２かつ更新中カウンタ２０７が０となるまで待つ（ステップ２６０２）。更新中カウンタが０となるまで待つ理由は、更新確認応答の処理を複雑にしないためである。次に当該エントリの状態２０３をロック３０７にする（ステップ２６０３）。子が０個なら（ステップ２６０４で０）、ステップ２６１２へ進む。子が１個なら（ステップ２６０５で１）、ステップ２６１１へ進む。子が２個なら（ステップ２６０５で２）、条件”左の子孫数２０８≦右の子孫数２０９”を判定する（ステップ２６０６）。この条件が偽なら（ステップ２６０６ＮＯ）、ステップ２６０８へ進む。第１及び第２の実施形態では、子の数が２の場合には左の子か右の子をランダムに選択し、エントリ追加要求を行っていたが、本実施形態では子孫数の小さい方の子にエントリ追加要求を行うことにより木の平衡を保つ。”左の子孫数２０８≦右の子孫数２０９”であれば（ステップ２６０６ＹＥＳ）、左の子孫数２０８に引数”子孫数”を加え、ステップ２６０９で行うエントリ追加要求の要求先を左の子とし（ステップ２６０７）、ステップ２６０９へ進む。”左の子孫数２０８＞右の子孫数２０９”であれば（ステップ２６０６ＮＯ）、右の子孫数２０９に引数”子孫数”を加え、ステップ２６０９で行うエントリ追加要求の要求先を右の子とする（ステップ２６０８）。次にステップ２６０７もしくはステップ２６０８で決定した要求先宛にエントリ追加要求（ｖｐ，要求ノード番号，引数で与えられた”コピーの要不要”，引数で与えられた”子孫数”）を行う（ステップ２６０９）。最後に当該エントリの状態２０３を有効３０２に設定し（ステップ２６１０）、処理を終了する。当該エントリの子の数が１の場合（ステップ２６０５で１）、当該エントリの左の子のノード番号２０５が自ノード番号に等しい場合（ステップ２６１１ＹＥＳ）、すなわち左の子は存在しないが右の子は存在する場合には、ステップ２６１２へ進み、左の子を追加する処理をする。当該エントリの左の子のノード番号２０５が自ノード番号に等しくない場合（ステップ２６１１ＮＯ）、すなわち左の子は存在するが、右の子は存在しない場合には、ステップ２６１３へ進み、右の子を追加する処理をする。ステップ２６１２で自エントリの左の子のノード番号２０５を引数”要求ノード番号”に設定する。また自エントリの左の子孫数２０８に引数”子孫数”を加算する。その後ステップ２６１４へ進む。ステップ２６１３で自エントリの右の子のノード番号２０６を引数”要求ノード番号”に設定する。また自エントリの右の子孫数２０９に引数”子孫数”を加算する。その後ステップ２６１４へ進む。次に要求ノードのｖｐエントリの親へのチェーンを自エントリに設定する処理を行う。すなわち引数”要求ノード番号”で指定されるノード宛にチェーン張り換え要求（ｖｐ，自ノード番号，要求ノード番号，自ノード番号）を行い、要求ノードからのチェーン張り換え確認応答（ｖｐ，要求ノード番号）を受け取る（ステップ２６１４）。次に引数”コピーの要不要”が要の場合（ステップ２６１５ＹＥＳ）にはステップ２６１６へ進み、不要の場合（ステップ２６１５ＮＯ）にはステップ２６１７へ進む。コピーの要の場合、要求ノードのｖｐに対応する物理ページの内容を仮想ページｖｐの内容と同じになるように初期化する。具体的には要求ノード宛に物理ページ初期化要求（ｖｐ，自ノード番号，物理ページの内容）を行い、物理ページ初期化確認応答（ｖｐ，要求ノード番号）を受け取る（ステップ２６１６）。次に要求ノード宛にアンロック要求（ｖｐ）を行う（ステップ２６１７）。最後に当該エントリの状態２０３を有効３０２にし（ステップ２６１８）、処理を終了する。
【００８５】
（ｄ）チェーン張り換え要求（ｖｐ，要求ノード番号，ｆｒｏｍ，ｔｏ）
仮想ページ番号ｖｐのエントリの親のノード番号、左の子のノード番号、右の子のノード番号の順にｆｒｏｍ（元のノード番号）に等しいものを１つだけ探し、ｔｏ（置き換えるノード番号）に置き換える。またｆｒｏｍが左の子のノード番号に対応する場合には左の子孫数を１減じ、ｆｒｏｍが右の子のノード番号に対応する場合には右の子孫数を１減じる。この機能により子孫数減少要求を伝搬させる。引数のｖｐはチェーン張り換えを要求している仮想ページ番号、要求ノード番号はチェーン張り換えを要求しているノード計算機番号である。ｆｒｏｍは仮想ページ番号ｖｐのエントリの親のノード番号２０４、左の子のノード番号２０５、右の子のノード番号２０６のうちどれをノード番号ｔｏに変更するかを指定する引数であり、ｔｏはｆｒｏｍで指定されたノード番号が変更された結果として設定されるノード番号である。
【００８６】
処理概要は以下の通りである。
（ｉ）親のノード番号２０４がｆｒｏｍにマッチする状況は、親が物理ページの割り当て解除を行った場合もしくは自ノードが物理ページ割り当てを行った結果として自エントリの親が決定した場合に発生する。当該エントリの親のノード番号２０４をｔｏに設定する。
（ｉｉ）左の子のノード番号２０５がｆｒｏｍにマッチする状況は、左の子孫が物理ページの割り当て解除を行った場合に発生する。当該エントリの左の子のノード番号２０５をｔｏに設定し、左の子孫数２０８から１を減じ、当該エントリの親宛に子孫数減少要求を伝搬させる。
（ｉｉｉ）右の子のノード番号２０６がｆｒｏｍにマッチする状況は、右の子孫が物理ページの割り当て解除を行った場合に発生する。当該エントリの右の子のノード番号２０６をｔｏに設定し、右の子孫数２０９から１を減じ、当該エントリの親宛に子孫数減少要求を伝搬させる。
【００８７】
図３４は、チェーン張り換えを行う仮想記憶操作装置制御部１７０の処理の流れを示すフローチャートである。チェーン張り換え要求を受けたとき（ステップ２７００）、トリードディレクトリ１２０に要求仮想ページ番号ｖｐをもつエントリが存在しないと（ステップ２７０１ＮＯ）、エラーとして終了する。エントリが存在するとき（ステップ２７０１ＹＥＳ）、当該エントリの状態２０３がロック３０７になるまで待つ（ステップ２７０２）。通常はすでにロック３０７である。次にチェーン張り換え中テーブルにｖｐのエントリを追加する（ステップ２７０３）。チェーン張り換え処理中のエントリがチェーン張り換え要求を親宛に転送する前に物理ページ割り当て解除されると、チェーン張り換え要求が根のエントリに到達しなくなる。その場合、子孫数は正しい値を保持しなくなるため、木の平衡が正しく保たれない。チェーン張り換え処理中のエントリをチェーン張り換え中テーブルに登録し、チェーン張り換え中テーブルに登録されている仮想ページの物理ページ割り当て解除を遅延させることにより、チェーン張り換え要求が根のエントリに到達することを保証する。当該エントリの親のノード番号２０３が引数”ｆｒｏｍ”にマッチするかどうか判定する（ステップ２７０４）。マッチする場合（ステップ２７０４ＹＥＳ）には、ステップ２７０５へ進み、マッチしない場合（ステップ２７０４ＮＯ）にはステップ２７０８へ進む。マッチする場合、当該エントリの親のノード番号２０４を引数”ｔｏ”に設定する（ステップ２７０５）。次に要求ノード宛にチェーン張り換え確認応答（ｖｐ，自ノード番号）を行う（ステップ２７０６）。次にチェーン張り換え中テーブルからｖｐのエントリを削除して（ステップ２７０７）、処理を終了する。ステップ２７０８以降では子からのチェーン張り換え要求に対応する処理を行う。当該エントリの左のノード番号２０５が引数”ｆｒｏｍ”にマッチする場合（ステップ２７０８ＹＥＳ）はステップ２７０９へ進む。そうでない場合（ステップ２７０８ＮＯ）はステップ２７１０へ進む。マッチする場合、左の子からチェーン張り換え要求を受けた場合の処理を行う。すなわち左の子孫数２０８から１を減じ、左の子のノード番号２０５を引数”ｔｏ”に設定し（ステップ２７０９）、その後ステップ２７１１へ進む。マッチしない場合、右の子からチェーン張り換え要求を受けた場合の処理を行う。すなわち右の子孫数２０９から１を減じ、左の子のノード番号２０６を引数”ｔｏ”に設定する（ステップ２７１０）。次に要求ノード宛にチェーン張り換え確認応答（ｖｐ，自ノード番号）を行う（ステップ２７１１）。次に自エントリが根のエントリか否かを判定する（ステップ２７１２）。自エントリが根のエントリの場合には、親宛に子孫数の減少を伝搬させる必要は無い。自エントリが根のエントリである場合、すなわち自エントリの親のノード番号２０４が自ノード番号に等しい場合（ステップ２７１２ＹＥＳ）は、ステップ２７０７へ進む。自エントリが根のエントリでなければ（ステップ２７１２ＮＯ）、その場合の処理を行う。すなわち当該エントリの状態２０３が有効３０２となるまで待ち、その後当該エントリの状態２０３をロック３０７にする（ステップ２７１３）。当該エントリの状態をロック３０７から有効３０２に変更するのは、物理ページ割り当て解除においてチェーン張り換え要求を行っていた子である。次に親宛にロック要求（ｖｐ，自ノード番号）を行う（ステップ２７１４）。その後親から肯定応答（ｖｐ，親のノード番号）を受け取った場合（ステップ２７１４ＡＣＫ）は、ステップ２７１７へ進む。否定応答（ｖｐ，親のノード番号）を受け取った場合（ステップ２７１４ＮＡＫ）は、親がロック状態の場合の処理を行う。親がロック状態である場合には、親がエントリ追加を行っているか、親が物理ページ割り当て解除を行っている。自ノードの状態を有効３０２とし、一定時間待つ（ステップ２７１５）。一定時間待つ理由は、一定時間待っている間に親の状態が有効３０２になることを期待するためである。次にトリードディレクトリ１２０に仮想ページ番号ｖｐのエントリが存在するか判定する（ステップ２７１６）。存在しない場合（ステップ２７１６ＮＯ）にはステップ２７０７へ進み、存在する場合（ステップ２７１６ＹＥＳ）にはステップ２７１２へ戻る。存在しない状況は、ステップ２７１５で一定時間待っている間に仮想ページｖｐに対する物理ページ全割り当て解除要求の処理が行われた場合に発生する。親から肯定応答を受けた時（ステップ２７１４ＡＣＫ）、親宛にチェーン張り換え要求（ｖｐ，自ノード番号，自ノード番号，自ノード番号）を行い、チェーン張り換え確認応答（ｖｐ，親のノード番号）を受け取る（ステップ２７１７）。このチェーン張り換え要求により、親の子孫数のカウンタの減少及び先祖への子孫数減少要求の伝搬が実現できる。次に親宛にアンロック要求を行う（ステップ２７１８）。最後に当該エントリの状態２０３を有効にして（ステップ２７１９）、ステップ２７０７へ進む。
【００８８】
【発明の効果】
本発明によれば、トリードディレクトリに基づく仮想記憶の更新制御をするために、一貫性制御に費やす時間が最良時には同一仮想ページを共有する物理ページ数の対数に比例する時間に短縮され、またトリードディレクトリの大きさは総ノード数の対数に比例するので台数拡張性に優れ、さらにネットワーク効率がよく負荷が集中しないという効果がある。
【図面の簡単な説明】
【図１】第１の実施形態の並列計算機の構成図である。
【図２】実施形態のトリードディレクトリのデータ形式を示す図である。
【図３】実施形態のトリードディレクトリの状態遷移図である。
【図４】トリードディレクトリのエントリ群の例を示す図である。
【図５】実施形態の書き込み中テーブルのデータ形式を示す図である。
【図６】実施形態の大域ページテーブルのデータ形式を示す図である。
【図７】実施形態の仮想ページの割り当ての処理の流れを示すフローチャートである。
【図８】実施形態の仮想ページの割り当て解除の処理の流れを示すフローチャートである。
【図９】実施形態の仮想ページの読み取りの処理の流れを示すフローチャートである。
【図１０】実施形態の仮想ページの書き込みの処理の流れを示すフローチャートである。
【図１１】実施形態の書き込み同期の処理の流れを示すフローチャートである。
【図１２】実施形態の物理ページの割り当ての処理の流れを示すフローチャートである。
【図１３】実施形態の物理ページの割り当て解除の処理の流れを示すフローチャートである。
【図１４】実施形態の物理ページの割り当て解除の処理（続き）の流れを示すフローチャートである。
【図１５】実施形態の更新要求の処理の流れを示すフローチャートである。
【図１６】実施形態のエントリ追加要求の処理の流れを示すフローチャートである。
【図１７】実施形態の物理ページ初期化要求の処理の流れを示すフローチャートである。
【図１８】実施形態のチェーン張り換え要求の処理の流れを示すフローチャートである。
【図１９】実施形態のロック要求の処理の流れを示すフローチャートである。
【図２０】実施形態のアンロック要求の処理の流れを示すフローチャートである。
【図２１】実施形態の物理ページ全割り当て解除要求の処理の流れを示すフローチャートである。
【図２２】他の実施形態の並列計算機の構成図である。
【図２３】実施形態の仮想記憶操作装置制御部のブロック図である。
【図２４】実施形態のトリードディレクトリ検索部のブロック図である。
【図２５】実施形態の有効性判定回路の真理値表を示す図である。
【図２６】実施形態の書き込み中テーブル検索部のブロック図である。
【図２７】さらに他の実施形態の並列計算機の構成図である。
【図２８】他の実施形態のトリードディレクトリのデータ形式を示す図である。
【図２９】他の実施形態のチェーン張り換え中テーブルのデータ形式を示す図である。
【図３０】他の実施形態の物理ページの割り当ての処理の流れを示すフローチャートである。
【図３１】他の実施形態の物理ページの割り当て解除の処理の流れを示すフローチャートである。
【図３２】他の実施形態の物理ページの割り当て解除の処理（続き）の流れを示すフローチャートである。
【図３３】他の実施形態のエントリ追加要求の処理の流れを示すフローチャートである。
【図３４】他の実施形態のチェーン張り換えの処理の流れを示すフローチャートである。
【符号の説明】
１００：ノード計算機、１０３：仮想記憶操作装置、１０５：大域ページテーブル、１０７：大域記憶装置、１１０：書き込み中テーブル、１２０：トリードディレクトリ、１７０：仮想記憶操作装置制御部、１８０：大域記憶装置制御部、２０２：仮想ページ番号、２０４：親のノード番号、２０５：左の子のノード番号、２０６：右の子のノード番号、５０２：仮想ページ番号、６０１：仮想ページ番号、６０２：根のエントリをもつノード番号
【図１】
0003566444.tif 000002
【図２】
0003566444.tif 000003
【図３】
0003566444.tif 000004
【図４】
0003566444.tif 000005
【図５】
0003566444.tif 000006
【図６】
0003566444.tif 000007
【図７】
0003566444.tif 000008
【図８】
0003566444.tif 000009
【図９】
0003566444.tif 000010
【図１０】
0003566444.tif 000011
【図１１】
0003566444.tif 000012
【図１２】
0003566444.tif 000013
【図１３】
0003566444.tif 000014
【図１４】
0003566444.tif 000015
【図１５】
0003566444.tif 000016
【図１６】
0003566444.tif 000017
【図１７】
0003566444.tif 000018
【図１８】
0003566444.tif 000019
【図１９】
0003566444.tif 000020
【図２０】
0003566444.tif 000021
【図２１】
0003566444.tif 000022
【図２２】
0003566444.tif 000023
【図２３】
0003566444.tif 000024
【図２４】
0003566444.tif 000025
【図２５】
0003566444.tif 000026
【図２６】
0003566444.tif 000027
【図２７】
0003566444.tif 000028
【図２８】
0003566444.tif 000029
【図２９】
0003566444.tif 000030
【図３０】
0003566444.tif 000031
【図３１】
0003566444.tif 000032
【図３２】
0003566444.tif 000033
【図３３】
0003566444.tif 000034
【図３４】
0003566444.tif 000035