(57)【要約】  本発明の情報処理装置は、マルチスレッドプロセッサと、第１の記憶装置と、第１の記憶装置との間でＤＭＡ転送を行う第２の記憶装置と、第１の記憶装置に物理アドレス空間を割当て、該物理アドレス空間上に仮想アドレス空間を提供するオペレーティングシステムと、を備え、実行予定のスレッドが該物理アドレス空間上でＤＭＡ転送に必要とする容量に応じてメモリ空間を確保し、該スレッドを実行に移し、該スレッドの処理が終了した後に確保したメモリ空間を開放することで、データの転送量にばらつきのある状況であっても効率的なＤＭＡ転送を実現する。
2014016951.tif 000002
【特許請求の範囲】
【請求項１】
マルチスレッドプロセッサと、
第１の記憶装置と、
前記第１の記憶装置との間でＤＭＡ転送を行う第２の記憶装置と、
前記第１の記憶装置に物理アドレス空間を割当て、該物理アドレス空間上に仮想アドレス空間を提供するオペレーティングシステムと、を備え、
実行予定のスレッドが前記物理アドレス空間上で前記ＤＭＡ転送に必要とする容量に応じてメモリ空間を確保し、
該スレッドを実行に移し、
該スレッドの処理が終了した後に確保したメモリ空間を開放することを特徴とする情報処理装置。
【請求項２】
請求項１に記載の情報処理装置において、
前記ＤＭＡ転送に利用される物理アドレス空間の領域が予め設定され、
予め設定された領域の内で実行中のスレッドに確保されている領域を除いた領域で、
前記メモリ空間の確保を行うことを特徴とする情報処理装置。
【請求項３】
請求項１に記載の情報処理装置において、
実行に移されＤＭＡ転送の完了待ちとなったスレッドを一時中断することを特徴とする情報処理装置。
【請求項４】
請求項３に記載の情報処理装置において、
一時中断されたスレッドのコンテキストを前記第１の記憶装置に記憶することを特徴とする情報処理装置。
【請求項５】
請求項３に記載の情報処理装置において、
一時中断されたスレッドのコンテキストを前記第２の記憶装置に記憶することを特徴とする情報処理装置。
【請求項６】
請求項１に記載の情報処理装置において、
前記第１の記憶装置が主記憶装置であることを特徴とする情報処理装置。
【請求項７】
請求項１に記載の情報処理装置において、
前記第１の記憶装置は揮発性メモリを備え、
前記第２の記憶装置は不揮発性メモリを備えることを特徴とする情報処理装置。
【請求項８】
請求項７に記載の情報処理装置において、
ハードディスクドライブを備えることを特徴とする情報処理装置。
【請求項９】
請求項１に記載の情報処理装置において、
前記マルチスレッドプロセッサは複数のコアを有することを特徴とする情報処理装置。
【請求項１０】
請求項１に記載の情報処理装置において、
前記揮発性メモリはＤＲＡＭであり、
前記不揮発性メモリはフラッシュメモリであることを特徴とする情報処理装置。
【請求項１１】
請求項１に記載の情報処理装置において、
前記揮発性メモリはＤＲＡＭであり、
前記不揮発性メモリは相変化メモリであることを特徴とする情報処理装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ＤＭＡ転送によって記憶装置にデータを転送して処理を行う情報処理装置で、特に複数のスレッドを切替えて実行することを特徴とした情報処理装置に関する。
【背景技術】
【０００２】
コンピュータは、データを格納する記憶装置と、記憶装置からデータを読み出して処理を行う中央処理装置（ＣＰＵ）から構成される。一般的に記憶装置は高速なものほど、ビットあたりの価格（単価）が高価である。また、高速なものほど、単位面積ないしは単位体積あたりのビット数（記録密度）が低い。そこで、ＣＰＵの近くに高速だが高価で容量が小さい記憶装置が用意され、直近で必要なデータが配置される。そして、それだけでは収まりきらないデータは低速だが安価で容量が大きい記憶装置に配置され、必要に応じて両記憶装置間でデータが入れ替られて利用される。このように、記憶装置に速度とコスト若しくは速度と容量のトレードオフの関係があることから、性質の異なる複数種の記憶装置を階層的に利用する、いわゆる記憶階層の概念がコンピュータの世界では幅広く用いられてきた。【０００３】
この傾向は今日でも不変であるが、コンピュータベンダーが利用可能な記憶素子の種類から、今日では主にレジスタ、キャッシュメモリ、メインメモリ、およびストレージの４階層から成る記憶階層でコンピュータは構成されている。それぞれの階層で用いられている主な記憶素子は、レジスタはフリップフロップ、キャッシュメモリはＳＲＡＭ、メインメモリはＤＲＡＭ、ストレージはＨＤＤであり、各記憶素子の速度とコスト及び容量によって階層を分ける必然性が生まれている。【０００４】
次に、前述した記憶階層に関して、別の面から説明を行う。ＣＰＵはレジスタに格納されているデータに処理を行う。ＣＰＵは、処理すべきデータがレジスタに無い場合、キャッシュを探して、キャッシュに格納されていればキャッシュからデータをレジスタに読み込んでから処理を行う。ＣＰＵは、キャッシュにも処理すべきデータが無い場合は、メインメモリからキャッシュにデータを読み込む。メインメモリにも処理すべきデータが無い場合には、ストレージからメインメモリにデータが読み込まれる。このように、ＣＰＵから見て手近な階層にデータが無い場合、遠くの階層からデータが読み込まれ、そのペナルティは大きくなる。そして、データを読み込んでいる間、ＣＰＵは行うべき処理が出来ないのでその動作が空いてしまい、ＣＰＵ利用率が低下する。データの読み込みに限らず、データの書き込みでも同様の問題が発生する。【０００５】
ここで、データ転送にＤＭＡ（Ｄｉｒｅｃｔ  Ｍｅｍｏｒｙ  Ａｃｃｅｓｓ）転送を用いるとＣＰＵの介在無しにデータ転送を行うことが出来るため、本来はデータ転送中の空き時間にＣＰＵは他の処理を行うことが出来るはずである。例えば、プログラム上で予めデータが必要になる箇所を特定して、明示的にＤＭＡ転送の指示を埋め込むことで、プログラマーがＤＭＡ転送のタイミングとＣＰＵが行う処理をスケジューリングするような方法も用いられている。しかし、この方法はプログラムのチューニングが煩雑になるという問題を引き起こす。【０００６】
これに対処するための技術として、マルチスレッドが用いられてきた。マルチスレッドでは、同時並行的に行うことが出来る処理の単位がスレッドとして定義され、あるスレッドの実行が止まったら、他の実行可能なスレッドが実行される。なお、スレッドの実行が止まるのは、当該スレッドの処理が完了したときだけでなく、当該スレッドで必要となるデータを読み込んでいる時にもスレッドの実行は止まる。つまり、先のデータ読み込みの動作と合わせて考えれば、あるスレッドを実行していて、必要なデータを読み込み始めると、その間は他のスレッドの実行を行う。このようにして、ＣＰＵ利用率を高めることができる。【０００７】
このようなＤＭＡ転送とマルチスレッドに関する先行技術として、特許文献１に開示の技術と特許文献２に開示の技術がある。いずれも、ＤＭＡ転送がＣＰＵ上のオンチップメモリ（ローカルメモリとも呼ばれる）とメインメモリ（グローバルメモリとも呼ばれる）の間で行われている。
【先行技術文献】
【特許文献】
【０００８】
【特許文献１】特開２００５−１２９００１号公報
【特許文献２】特開２００２−１６３２３９号公報
【発明の概要】
【発明が解決しようとする課題】
【０００９】
ところで、近年、インターネットや各種端末の普及で、大量のデータを容易に取得することが出来るようになってきている。このような大量のデータは、旧来のデータベース管理システムなどで取り扱うことが難しく、ビッグデータという標語の元に種々の技術が開発されている。あらゆるモノがインターネットに接続されるＩｏＴ（Ｉｎｔｅｒｎｅｔ  ｏｆ  Ｔｈｉｎｇｓ）の時代には、モノで発生したあらゆるイベントに関するデータがインターネットに送信される。つまり、大量のＰＯＥ（Ｐｏｉｎｔ  ｏｆ  Ｅｖｅｎｔ）データがインターネット上に送信される。このような世界では、インターネットからＰＯＥデータを収集し、モノとモノ、ヒトとヒト、ないしは、モノとヒトがどのような関係にあるのかを分析し、それに基づいて適切なサービスを提供したり、将来を予測したりするなどの利用がなされていくことが期待される。そのためには、コンピュータが大量のデータを高速に処理することができなければならない。【００１０】
コンピュータが大量のデータを高速に処理するためには、処理すべきデータがメインメモリ上に載ることが望ましい。ストレージ上にデータが置かれていると、その読み出しに時間を要する。特に、様々なモノやヒトの関係性を分析しようとする場合、様々なモノやヒトのデータを読み出さなければならない。その都度ストレージへのアクセスが必要になってしまうと、ストレージの読み出しの遅さがネックとなる。しかし、前述したようなビッグデータに対して、それに見合う容量のメインメモリを実現するために大量のＤＲＡＭを並べると、様々な問題を引き起こす。【００１１】
ＤＲＡＭはストレージに用いるＨＤＤやフラッシュメモリ、相変化メモリなどと比較して単価が高いため、大量のＤＲＡＭでメインメモリを構成するとコスト増を引き起こす。また、ＤＲＡＭは記録密度でも劣ることから、同容量のＨＤＤやフラッシュメモリと比較して装置が巨大になってしまう。そこで、本願発明者らは、メインメモリとメインメモリからデータを退避させておく記憶領域との間でＤＭＡ転送を行うことで、必要な容量を用意しつつ、読み出し速度の問題を解決することを試みた。【００１２】
ここで、スレッドのスケジューリングは、実行可能なスレッドをキューから取りだして行う単純なＦＩＦＯに基づくことが多い。そのため、各スレッドの実行時間は均一なほうが効率的にスケジューリングすることができるので、処理をスレッドに分割するときには負荷が均等になるように分割することが望ましい。【００１３】
しかし、コンピュータが普及し、アプリケーションが多様化する中で、必ずしも均等な分割が出来ないアプリケーションもあり問題となる。たとえば、社会科学系の問題を扱うとき、グラフ処理が行われる。グラフは、頂点の集合と、頂点間を結ぶ辺の集合で構成される。社会科学系の問題では、関係性が扱われることが多い。例えば会社間の関係は会社を表現する頂点と、関係を表現する辺で示される。このようなグラフを複数のスレッドで処理するために分割しようとすると、頂点毎にスレッドを割当てて分割する形態が自然である。ところが、頂点毎に分割したときに、各頂点が繋がっている辺の数はばらつきがある。そして、各頂点の処理に要する時間は、各頂点が関係を持っている頂点の数、すなわち、辺の数に比例する。そのため、頂点毎の分割ではスレッド間に処理量のばらつきが生じてしまい、退避させておいたデータをメインメモリにＤＭＡ転送する際に、ＤＭＡ転送されるデータの大きさがばらついてしまう。【００１４】
中でも、社会科学系の問題で登場するグラフはスケールフリー特性と呼ばれる性質を有しているため、このばらつきがより顕著なものとなる。グラフの各頂点が接続されている辺の数を、その頂点の次数と呼ぶ。スケールフリー特性はこの次数の分布が冪乗分布になっていることが特徴で、ごく少数の頂点は極めて次数が大きいが、大多数の頂点は次数が小さいという特徴を持つ。この特徴を前述した処理量のばらつきにあてはめて考えると、社会学系のグラフを処理する時には、非常に処理量の大きい少数のスレッドと、処理量の小さい多数のスレッドを処理することになる。【００１５】
特許文献１に開示の技術と特許文献２に開示の技術は、ＤＭＡ転送がＣＰＵ上のオンチップメモリとメインメモリの間で行われるものであり、ＤＭＡ転送されるのは直近でＣＰＵが処理するデータに限られるので、上述のデータの大きさのばらつきを解決する技術ではない。【００１６】
本発明は、データの転送量にばらつきのある状況であっても効率的なＤＭＡ転送を実現することを目的とする。
【課題を解決するための手段】
【００１７】
本発明の情報処理装置は、マルチスレッドプロセッサと、第１の記憶装置と、第１の記憶装置との間でＤＭＡ転送を行う第２の記憶装置と、第１の記憶装置に物理アドレス空間を割当て、該物理アドレス空間上に仮想アドレス空間を提供するオペレーティングシステムと、を備え、実行予定のスレッドが該物理アドレス空間上でＤＭＡ転送に必要とする容量に応じてメモリ空間を確保し、該スレッドを実行に移し、該スレッドの処理が終了した後に確保したメモリ空間を開放することで、前述の課題を解決する。
【発明の効果】
【００１８】
本発明により、データの転送量にばらつきのある状況であっても効率的なＤＭＡ転送を実現することができ、ひいては情報処理装置の処理を高速化できる。
【図面の簡単な説明】
【００１９】
【図１】本発明の情報処理システムの構成の例を示す図である。
【図２】本発明の情報処理装置の構成の例を示す図である。
【図３】本発明のＮＶＭサブシステムの構成の例を示す図である。
【図４】スレッドとプロセッサの関係の例を説明するための図である。
【図５】本発明のプロセスの内部構造の例を説明するための図である。
【図６】本発明の情報処理装置の物理アドレス空間と、本発明のプロセスの仮想アドレス空間との対応関係の例を説明するための図である。
【図７】ｓｔａｃｋ領域とＰＩＮ領域プールの例の詳細を説明するための図である。
【図８】マスターコントロールスレッドがスレッド及びＤＭＡ転送の管理に用いるキューを説明するための図である。
【図９】スレッド管理セルの構成の例を説明するための図である。
【図１０】スレッドの状態遷移の例を示す図である。
【図１１】ＮＶＭ転送要求管理セルの構成の例を説明するための図である。
【図１２】ＮＶＭ転送要求の状態遷移の例を示す図である。
【図１３】ユーザレベルマルチスレッディングとＤＭＡ転送の連携を説明するための図である。
【図１４】ユーザレベルマルチスレッディングとＤＭＡ転送の関係を説明するための概念図である。
【図１５】マスターコントロールスレッドのスケジューリング動作の例を説明するためのフローチャートである。
【図１６】ユーザレベルマルチスレッディングとＤＭＡ転送の関係を説明するための概念図である。
【発明を実施するための形態】
【００２０】
以下、本発明の実施の形態を図面を用いて説明する。なお、実施の形態を説明するための全図において、同一の部材には原則として同一の符号を付し、その繰り返しの説明は省略する。
【実施例１】
【００２１】
本実施例では、フラッシュメモリや相変化メモリなどの不揮発メモリを利用して、アプリケーションに対して、ＤＲＡＭで構成されるメモリよりも大きなメモリを提供しつつ、不揮発メモリの欠点である速度の遅さをマルチスレッドで解決する情報処理システム１００を説明する。【００２２】
図１は、本実施例の情報処理システム１００の構成の例を示す図である。情報処理システム１００は、少なくとも１個以上のノード１１０を有する。ノード１１０は、情報処理装置であり、例えばサーバ装置である。図１の例は、ノード０〜３（符号は１１０）の４ノード構成の例を示している。ノード間はノード間ネットワーク１２０で接続される。また、情報処理システム１００は、ノード間ネットワーク１２０に加えて、後述する不揮発メモリ（ＮＶＭ：Ｎｏｎ−ｖｏｌａｔｉｌｅ  ｍｅｍｏｒｙ）サブシステム間を接続するＮＶＭサブシステムインターコネクト１３０をさらに備えていても良い。【００２３】
図２は、情報処理装置であるノード１１０の構成の例を示す図である。ノード１１０は、プロセッサ２１０、２２０、ＤＩＭＭ２３０、２４０、Ｉ／Ｏハブ２５０、ＮＩＣ２６０、ディスクコントローラ２７０、ＨＤＤ２８０、ＳＳＤ２９０、およびＮＶＭサブシステム３００を備える。メインメモリは、記憶装置であるＤＩＭＭ２３０およびＤＩＭＭ２４０で構成される。ＤＩＭＭ２３０、２４０は、揮発性メモリであるＤＲＡＭで構成される。なお、各ノード１１０が有するプロセッサの数は最小で１個あれば良く、図２のノード１１０は、プロセッサ２１０、２２０の２プロセッサ構成の例である。また、プロセッサ２１０、２２０はそれぞれマルチコアプロセッサであっても良い。図２の例では、各プロセッサが２個のコアを有しており、ノード１１０全体では４コアノードとなっている。さらに、各コアは同時マルチスレッディング（ＳＭＴ：Ｓｉｍｕｌｔａｎｅｏｕｓ  Ｍｕｌｔｉｔｈｒｅａｄｉｎｇ）に対応していても良い。図２の例では、各コアが２ＳＭＴ対応であり、よって各プロセッサは４個のスレッドを同時に処理する能力を有する。すなわち、各プロセッサはマルチスレッドプロセッサである。なお、これ以降、ハードウェアとして同時に処理することの出来るスレッドをハードウェアスレッドと称する。【００２４】
Ｉ／Ｏハブ２５０は、ＮＩＣ２６０、ディスクコントローラ２７０、ＮＶＭサブシステム３００などの各種装置を接続するためのインタフェースを提供する。Ｉ／Ｏハブ２５０は、プロセッサ２１０、２２０とは、それぞれのプロセッサが提供するシステムバスで接続される。接続には、例えば、ＨｙｐｅｒＴｒａｎｓｐｏｒｔのようなバスが用いられる。一方、Ｉ／Ｏハブ２５０は、ＮＩＣ２６０、ディスクコントローラ２７０、ＮＶＭサブシステム３００のような各種装置とは、ＰＣＩ  Ｅｘｐｒｅｓｓなどの周辺機器接続用のペリフェラルバスで接続される。本実施例では、Ｉ／Ｏハブ２５０と、ＮＩＣ２６０、ディスクコントローラ２７０、およびＮＶＭサブシステム３００は、ＰＣＩ  Ｅｘｐｒｅｓｓで接続されているものとして説明するが、他のインターコネクト手段でも本発明は実施可能である。【００２５】
従来、コンピュータのメインメモリはＤＩＭＭの容量で決まっていた。そして、メインメモリに入り切らないデータは、ストレージであるＨＤＤやＳＳＤに格納される。ストレージはディスクコントローラを介して接続され、ハードウェア面ではＳＡＳ（Ｓｅｒｉａｌ  Ａｔｔａｃｈｅｄ  ＳＣＳＩ）やＳＡＴＡ（Ｓｅｒｉａｌ  Ａｄｖａｎｃｅｄ  Ｔｅｃｈｎｏｌｏｇｙ  Ａｔｔａｃｈｍｅｎｔ）のようなインタフェースが用いられる。そして、ソフトウェアから見たインタフェースはファイルシステムとなる。アプリケーションはファイルに対して読書きを行うことで、ファイルシステムを経由して、オペレーティングシステムが有するデバイスドライバがディスクコントローラを制御して、ＨＤＤやＳＳＤを読書きする。そのため、複数の階層を経由しないと読書きが出来ず、オーバヘッドが大きい。【００２６】
それに対して、本実施例の情報処理システム１００は、ＤＩＭＭに比べて大容量の不揮発メモリをＨＤＤやＳＳＤのストレージよりも高速に読書きするために、ＮＶＭサブシステム３００を備えている。ストレージを使用するよりも高速に読み書きが必要な場合には、データをストレージからＮＶＭサブシステム３００に予め読み出しておくことで、高速な読み書きを実現する。なお、不揮発メモリ（Ｎｏｎ−ｖｏｌａｔｉｌｅ  Ｍｅｍｏｒｙ）を略記してＮＶＭと記す。【００２７】
図３は、ＮＶＭサブシステム３００の構成の例を示す図である。ＮＶＭサブシステム３００は、ハイブリッドメモリコントローラ３１０と、記憶装置である不揮発性メモリ（ＮＶＭ）３２０と、記憶装置である揮発性メモリ３３０とを備える。ＮＶＭ３２０は、フラッシュメモリや相変化メモリなどの不揮発メモリである。また、揮発性メモリ３３０はＤＲＡＭであり、ＤＩＭＭを流用することができる。ハイブリッドメモリコントローラ３１０は、ＮＶＭ３２０と、揮発性メモリ３３０と、Ｉ／Ｏハブ２５０に接続されている。ハイブリッドメモリコントローラ３１０は、プロセッサ２１０または２２０上で動作するソフトウェアの要求に応じて、ＮＶＭ３２０に格納されているデータをメインメモリであるＤＩＭＭ２３０または２４０にＤＭＡ転送する。また、ハイブリッドメモリコントローラ３１０は、メインメモリであるＤＩＭＭ２３０または２４０に格納されているデータをＮＶＭ３２０にＤＭＡ転送する役割を担う。揮発性メモリ３３０は、ＤＭＡ転送の際に、バッファとして用いられる。また、各ノードが有するハイブリッドメモリコントローラ３１０の間を、前述したようにＮＶＭサブシステムインターコネクト１３０で接続することもできる。この接続により、他のノードのＮＶＭサブシステム３００に格納されているデータにもアクセスが可能になる。【００２８】
ハイブリッドメモリコントローラ３１０は、メモリマップされたレジスタ（ＭＭＲ：Ｍｅｍｏｒｙ  Ｍａｐｐｅｄ  Ｒｅｇｉｓｔｅｒ）３１１を有する。ＭＭＲ３１１は、プロセッサ２１０、２２０上で動作するソフトウェアがハイブリッドメモリコントローラ３１０に対してＤＭＡ転送の指示を行うためのレジスタである。ＰＣＩ  Ｅｘｐｒｅｓｓでは周辺装置が有するレジスタを、メインメモリと同じメモリ空間上にマップすることが可能である。そのため、ＭＭＲ３１１に対して、ソフトウェアは、メインメモリに読書きするのと同様に、プロセッサ２１０、２２０のロード・ストア命令でアクセスすることができる。【００２９】
ノード１１０上では、仮想記憶に対応したオペレーティングシステムが動作する。ノード１１０は、前述のように複数のコアから構成されるが、全てのコアが単一のメインメモリを共有する対称型マルチプロセッシング（ＳＭＰ：Ｓｙｍｍｅｔｒｉｃ  Ｍｕｌｔｉｐｒｏｃｅｓｓｉｎｇ）の構成である。そのため、ノード１１０では単一のオペレーティングシステムが動作することになる。これ以降、ノード１１０でオペレーティングシステムを１個動作させている、シングルシステムイメージを前提として実施例を説明する。各ノード１１０で動作するオペレーティングシステムは、各ノード１１０のＤＩＭＭ２３０、２４０で構成されるメインメモリに物理アドレス空間を割当て、該物理アドレス空間上に仮想アドレス空間を提供する。【００３０】
図４は、ノード１１０が持つ複数のコアと、オペレーティングシステムがユーザに提供する資源との関係を示した説明図である。各ノード１１０は、２プロセッサ／ノード、２コア／プロセッサ、２ＳＭＴ／コアの構成であるため、それぞれのノード全体では２×２×２＝８ハードウェアスレッドの資源がある。【００３１】
仮想記憶に対応したオペレーティングシステムでは、プロセッサのＭＭＵ（Ｍｅｍｏｒｙ  Ｍａｎａｇｅｍｅｎｔ  Ｕｎｉｔ）が有するアドレス変換機構を活用して、アプリケーション用の仮想アドレス空間（ユーザ空間）と、オペレーティングシステムのカーネルが動くための仮想アドレス空間（カーネル空間）を分離して、システムのセキュリティや頑強性を確保している。ユーザ空間では、プロセスという単位毎に独立した仮想アドレス空間を持っている。一般的に、このようなプロセスという概念がある環境下でのスレッドは、プロセスに従属する形態をとる。すなわち、各プロセスが１個以上のスレッドを有し、各スレッドは親となるプロセスの仮想アドレス空間を共有して動作する。【００３２】
また、単一のオペレーティングシステムが複数のコアを管理するような場合、オペレーティングシステムは何らかの形でコアを抽象化し、プロセスに割当てることで、アプリケーションが複数のコアを利用可能な環境を提供しなければならない。そのような目的のためにも、スレッドという概念は用いられている。図４に示すように、オペレーティングシステムはカーネルレベルスレッドを各プロセスに提供している。【００３３】
一般的に、スレッドを実行するときには、実行すべきスレッドの数（Ｎ）に対して、ハードウェアスレッドの数（Ｍ）は限られる。ＮがＭ以下の場合には、両者を一対一対応させることが出来るが、ＮがＭより大きいの場合には切替えが必要となる。この切替えが、コンテキスト切替えである。しかし、カーネルレベルスレッドでコンテキスト切替えを行うためには、仮想アドレス空間をユーザ空間からカーネル空間に切替えて、カーネルの中でコンテキスト切替えの処理を行う必要があるため、コンテキスト切替えのオーバヘッドが大きいことが問題となる。【００３４】
そこで本実施例の情報処理システム１００では、図４に示すようにカーネルレベルスレッドとハードウェアスレッドを一対一に対応させて利用する。すなわち、Ｎ＝Ｍの関係とする。しかし、このままではＮの数がＭの数に制約を受けてしまうため、アプリケーションが必要とするスレッド数を確保できない。スレッド数が小さいと、後述するＤＭＡ転送を隠蔽する余地も少なくなってしまうので、システム全体として効率が低下する。そのため、カーネルでのコンテキスト切替えを避けつつ、大量のスレッドを利用可能にする（Ｎを大きくする）方法が必要となる。【００３５】
これに対処するために、本実施例の情報処理システム１００では、図４のプロセス４１０、４２０の各プロセスに、図５に示すようにマスターコントロールスレッド５５０とユーザレベルスレッドを設けることを特徴としている。【００３６】
図５に示したように、本実施例の情報処理システム１００では、プロセス４１０はスレッド間共有リソース５１０と、カーネルから割当てられた少なくとも２個以上のカーネルレベルスレッドを持つ。そして、複数のカーネルレベルスレッドのうちの１個に、マスターコントロールスレッド５５０が固定的に割当てられる。また、アプリケーションが必要とするユーザレベルスレッドが時分割でカーネルレベルスレッドに割当てられる。【００３７】
マスターコントロールスレッド５５０は、プロセス４１０が存続している期間、常にカーネルレベルスレッドを１個占有して動き続けるスレッドであり、ユーザレベルスレッドのコンテキスト切替えや、スケジューリング、及び、スレッド間共有リソースの管理などを行う。カーネルレベルスレッドとは異なり、マスターコントロールスレッド５５０がこれらの処理をプロセス４１０の中で行うことで、カーネル空間への切替えを発生させることなく、より高速にコンテキスト切替えを実現することができる。すなわち、マスターコントロールスレッド５５０により、大量のスレッドを利用しつつ、コンテキスト切替えの高速化を実現できる。【００３８】
前述したように、スレッドはプロセスの資源を共有して動作する。スレッドでは、各スレッドが固有のスタックを持ち、それ以外の領域は他スレッドと共有するモデルが用いられる。本実施例の情報処理システム１００では、後述のＤＭＡ転送を行うために、さらに、後述するＰＩＮ領域の資源配分をユーザレベルスレッドに対して行う。【００３９】
図６は、ノード１１０が有する物理アドレス空間６１０と、ノード１１０上で動作するプロセス４１０が有する仮想アドレス空間６２０との対応を記した説明図である。物理アドレス空間６１０に配置される領域は、基本的にはノード１１０の物理的な構成部材と一対一に対応している。ＤＲＡＭ領域６１１はＤＩＭＭ２３０、２４０に対応している。また、ＭＭＩＯ（Ｍｅｍｏｒｙ  Ｍａｐｐｅｄ  Ｉｎｐｕｔ／Ｏｕｔｐｕｔ）領域６１２は、前述したＭＭＲ３１１が配置される領域である。これらの領域はいずれもページと呼ばれる単位で管理される。一般的には１ページが４ＫＢの大きさである。【００４０】
プロセス４１０の仮想アドレス空間６２０は、ｔｅｘｔ領域６２１、ｄａｔａ領域６２２、ｍｍｉｏ領域６２３、およびｓｔａｃｋ領域６２４に大別できる。本実施例のプロセス４１０では、それらに加えてさらにＰＩＮ領域プール５１６を有する。【００４１】
仮想アドレス空間６２０内の各領域に関して、図５に示すプロセス４１０の内部構造と、図６に示すプロセス４１０の仮想アドレス空間６２０を対応させながら以下に説明する。【００４２】
プロセス４１０は、ユーザレベルスレッド間で共有する様々なリソースをスレッド間共有リソース５１０として有している。スレッド間共有リソース５１０には、プログラムコード５１１、グローバル変数５１２、ヒープ領域５１３、スレッド管理情報５１４、ＮＶＭ転送要求管理情報５１５、およびＰＩＮ領域プール５１６が含まれる。プログラムコード５１１は、スレッドが実行すべきプログラムの命令列であり、これは仮想アドレス空間６２０上ではｔｅｘｔ領域６２１に配置される。グローバル変数５１２は、プロセス４１０内で動作する任意のサブルーチンやスレッドが共通して利用する変数であり、ｄａｔａ領域６２２に配置される。ヒープ領域５１３は、プログラムが動的にメモリを確保するときのリソースプールであり、ｄａｔａ領域６２２に配置される。スレッド管理情報５１４は、詳細は後述するが、スレッドを管理するためにスレッド毎に必要な情報を記憶するためのものであり、主にマスターコントロールスレッド５５０に利用されるが、ユーザレベルスレッドからアクセス出来る必要があるためグローバル変数５１２と同様の性質を持つことになり、ｄａｔａ領域６２２に配置される。ＮＶＭ転送要求管理情報５１５は、後述するＤＭＡ転送を管理するための情報で、スレッド管理情報５１４と同様の理由により、ｄａｔａ領域６２２に配置される。ｓｔａｃｋ領域は、ローカル変数やサブルーチンのパラメータ渡しのために用いるスタックを用意するための領域であり、後述するように各スレッドに配分される。【００４３】
図６には、物理アドレス空間６１０と仮想アドレス空間６２０との対応関係が破線で示されている。図６に示したように、ページ単位で物理アドレス空間６１０と仮想アドレス空間６２０はマッピングされるが、仮想アドレス空間６２０上は存在するのに、物理アドレス空間６１０に対応するページが存在しないような仮想アドレス空間６２０上のページがあることに留意されたい。これがいわゆる仮想記憶を実現している仕組みであり、仮想アドレス空間６２０にはページが存在していても、それは直接ＤＲＡＭに載っているとは限らず、ＨＤＤやＳＳＤの中にページアウトされている可能性がある。このようなページにアクセスすると、ＭＭＵがページフォルト例外を発生させ、オペレーティングシステムがＨＤＤやＳＳＤから退避されているページを読み出してページインさせる。このように、仮想記憶を採用している情報処理システム１００では、プロセスから見て存在しているメモリ領域（ページ）が、必ずしも物理的なメモリ上に存在している訳ではないという特徴がある。この特徴がＤＭＡ転送に及ぼす影響について、後ほど説明する。【００４４】
図７は、仮想アドレス空間６２０のＰＩＮ領域プール５１６およびｓｔａｃｋ領域６２４のスレッドとの関係を示している。ＰＩＮ領域プール５１６とｓｔａｃｋ領域６２４は、いずれも利用されるスレッド毎に分割される。しかし、ｓｔａｃｋ領域６２４が必ずプロセス４１０が有する全てのスレッド（マスターコントロールスレッド、及び、ユーザレベルスレッド）に対応したｓｔａｃｋ領域を持つのに対して、ＰＩＮ領域プール５１６はその領域の大きさに応じて一部のスレッドに対応する領域しか持たない。これは、ｓｔａｃｋ領域６２４は、仮想記憶の機構を利用して、仮想アドレス空間の許す限り領域を確保することが出来るのに対して、ＰＩＮ領域プール５１６は、後述する理由で、物理アドレス空間６１０のＤＲＡＭ領域６１１と対応しているページを確保できる分しか用意しないためである。【００４５】
以下に、情報処理システム１００のユーザレベルマルチスレッディングとＤＭＡ転送を連携させる機構について説明する。ユーザレベルマルチスレッディングとＤＭＡ転送の連携により、例えば、背景技術で述べたような大規模なグラフ処理を高速化できる。【００４６】
ここで、ユーザレベルマルチスレッディングとは、プロセス４１０の中で複数のスレッド（ユーザレベルスレッド）を切替えながら動作させていくことを言う。スレッド切替えに必要な処理がプロセス４１０の中で完結するので、カーネルレベルスレッドの切替えよりも高速である。一方で、ユーザレベルマルチスレッディングでは、スレッドの管理もプロセス４１０の中で行われる。本実施例の情報処理システム１００では、マスターコントロールスレッド５５０がスレッドの管理の役割を担う。【００４７】
図８は、マスターコントロールスレッド５５０によるユーザレベルスレッド、及び、ＤＭＡ転送を管理するためのキューを示す図である。これらのキューはスレッド管理情報５１４、及び、ＮＶＭ転送要求管理情報５１５としてメモリ上に置かれている。【００４８】
スレッド管理情報５１４は、ＲＥＡＤＹキュー８１０、ＩＯＷＡＩＴキュー８１１、ＮＶＭＷＡＩＴキュー８１２、およびＦＩＮキュー８１３を含む。各キューにエンキューされるエントリは、図９に示すスレッド管理セル９００である。スレッド管理セル９００は、Ｖａｌｉｄフラグ９０１、スレッドＩＤ９０２、スレッド状態９０３、退避コンテキスト９０４、退避スタックポインタ９０５、退避プログラムカウンタ９０６、バッファ要求フラグ９０７、バッファ要求サイズ９０８、バッファ割当てフラグ９０９、およびバッファ領域先頭アドレス９１０から構成される。【００４９】
Ｖａｌｉｄフラグ９０１は、当該スレッド管理セル９００が有効であるかどうかを示すフラグである。スレッドＩＤ９０２は、スレッドを一意に識別するための識別子であり、後述するＤＭＡ転送とスレッドのスケジューリングを連携させるという本発明の特徴となる動作を実現させるために用いられる。スレッド状態９０３は、スレッドが現在どのような状態にあるかを示すための情報である。スレッドの状態に関しては後で詳しく説明する。【００５０】
退避コンテキスト９０４、退避スタックポインタ９０５、および退避プログラムカウンタ９０６は、スレッドの実行に用いられる情報であり、スレッドを停止させるときにプロセッサ２１０、２２０上のレジスタからスレッド管理セル９００に退避させた情報である。バッファ要求フラグ９０７、バッファ要求サイズ９０８、バッファ割当てフラグ９０９、およびバッファ領域先頭アドレス９１０は、後述するＤＭＡ転送のために用いられるものであり、詳細は後述する。【００５１】
ＲＥＡＤＹキュー８１０は、実行可能なユーザレベルスレッドのスレッド管理セル９００がエンキューされている。マスターコントロールスレッド５５０は、プロセス４１０が有するカーネルレベルスレッドに空きがある場合、または、他のユーザレベルスレッドが停止する場合に、ＲＥＡＤＹキュー８１０からスレッド管理セル９００をデキューする。そして、デキューしたスレッド管理セル９００に含まれる退避コンテキスト９０４、退避スタックポインタ９０５、および退避プログラムカウンタ９０６を用いてコンテキスト切替えを行い、スレッドの実行を開始する。【００５２】
実行中（ＲＵＮ）でもなく、実行可能状態（ＲＥＤＡＹ）でも無いスレッドは、何らかの待ち状態にある。マスターコントロールスレッド５５０は、その待ち状態を管理するために、ＩＯＷＡＩＴキュー８１１とＮＶＭＷＡＩＴキュー８１２を用いる。特に、ＮＶＭＷＡＩＴキュー８１２を有することが、本実施例の情報処理システム１００の特徴である。【００５３】
ＩＯＷＡＩＴキュー８１１は、オペレーティングシステムにシステムコールで要求したＩ／Ｏの完了を待っているスレッドが格納されているキューである。ユーザレベルスレッドは、ファイルへのアクセスなどオペレーティングシステムの機能を使ったＩ／Ｏの要求を行う場合に、システムコールを発行してそれをオペレーティングシステムに伝える。その後、システムコールを発行したスレッドが当該システムコールの実行が完了するまで行うべき処理が無い場合、つまり当該システムコールの完了を待って処理を再開する場合には、マスターコントロールスレッド５５０は、このＩＯＷＡＩＴキュー８１１にシステムコールを発行したスレッドを退避させる。システムコールの実行が完了すると、マスターコントロールスレッド５５０は、退避させていたスレッドをＲＥＡＤＹキュー８１０に移行する。【００５４】
ＮＶＭＷＡＩＴキュー８１２は、メインメモリと不揮発メモリ（ＮＶＭ）３２０の間のＤＭＡ転送の完了を待っているスレッドが格納されているキューである。本実施例の情報処理システム１００の想定されるユースケースでは、例えば大規模グラフ処理のために大量の頂点のそれぞれに対応するスレッドが実行される。その際、スレッドの数が膨大となるため、全てのスレッドで処理に必要なデータを一度にメインメモリに載せておくことは難しい。そこで、情報処理システム１００は、データを不揮発メモリ（ＮＶＭ）３２０に格納しておき、スレッドを実行する際にＤＭＡ転送でＮＶＭ３２０からメインメモリに持ってくる。メインメモリがＤＲＡＭで構成されるのに対し、ＮＶＭ３２０はフラッシュメモリや相変化メモリで構成されるため、ＤＲＡＭに比較して安価に大容量が実現される。しかし、このＤＭＡ転送にも時間を要するため、その間、ＤＭＡ転送でデータを要求したスレッドで他に実行可能な処理が無い場合、マスターコントロールスレッド５５０は、当該スレッドをＮＶＭＷＡＩＴ８１２キューに退避する。ＤＭＡ転送が完了すると、マスターコントロールスレッド５５０は、ＮＶＭＷＡＩＴ８１２キューに退避させたスレッドをＲＥＡＤＹキュー８１０に移行する。【００５５】
ＦＩＮキュー８１３は、実行が完了し不要となったスレッド管理セル９００を収集するためのキューである。スレッド管理セル９００はスレッド毎に存在する。そのため、動的な大規模グラフ処理などで、大量のスレッドの生成と破棄を繰り返すような場合、スレッド管理セル９００をその都度、ヒープ領域５１３からメモリの割り当てを受けて生成、ないしは、ヒープ領域５１３に領域を返却していては、そのオーバヘッドが大きい。そのため、マスターコントロールスレッド５５０は、使用済みのスレッド管理セル９００をＦＩＮキュー８１３に収集し、必要に応じてＦＩＮキュー８１３からスレッド管理セル９００を再利用する。【００５６】
図１０は、ここまでに説明したスレッドの各種状態を状態遷移図としてまとめたものである。図１０の（１）で新規にスレッドが生成されると、マスターコントロールスレッド５５０は、新規スレッドのスレッド管理セル９００を、ＲＥＡＤＹキュー８１０にエンキューする。図１０の（２）で、マスターコントロールスレッド５５０は、スレッドを実行する資源に空きが生じた場合、すなわち、既に実行していたユーザレベルスレッドが停止（ＲＥＡＤＹキュー８１０、ＩＯＷＡＩＴキュー８１１、ＮＶＭＷＡＩＴキュー８１２、またはＦＩＮキュー８１３にスレッドが退避される）した場合、または、カーネルレベルスレッドにユーザレベルスレッドが割当てられておらず空いている場合に、ＲＥＤＡＹキュー８１０の先頭にあるスレッド管理セル９００をデキューして実行開始する。当該スレッドは実行中（ＲＵＮ）となる。【００５７】
図１０の（３）では、実行中のスレッドから自発的な資源返上（ｙｉｅｌｄ）があった場合に、マスターコントロールスレッド５５０は、当該スレッドの実行を一時中断し、当該スレッドをＲＥＡＤＹキュー８１０にエンキューする。図１０の（４）では、実行中のスレッドがファイルアクセスなどのためにシステムコールを発行し、システムコールの完了待ちになった場合に、マスターコントロールスレッド５５０は、当該スレッドの実行を一時中断し、当該スレッドをＩＯＷＡＩＴキュー８１１にエンキューする。【００５８】
図１０の（５）では、実行中のスレッドが、ＮＶＭ３２０とメインメモリの間でのＤＭＡ転送の完了待ちになった場合に、マスターコントロールスレッド５５０は、当該スレッドの実行を一時中断し、当該スレッドをＮＶＭＷＡＩＴキュー８１２にエンキューする。【００５９】
図１０の（６）では、マスターコントロールスレッド５５０は、（４）でＩＯＷＡＩＴキュー８１１にエンキューされることにより始まったシステムコール完了待ちで、システムコールの完了を検出した場合に、当該スレッドをＩＯＷＡＩＴキュー８１１からＲＥＡＤＹキュー８１０に移行させる。図１０の（７）に関しても、図１０の（６）と同様に、完了待ちに対して実際に完了した場合の動作であり、マスターコントロールスレッド５５０は、（４）でＮＶＭＷＡＩＴキュー８１２にエンキューされることにより始まったＤＭＡ転送完了待ちで、ＤＭＡ転送の完了を検出した場合に、当該スレッドをＮＶＭＷＡＩＴキュー８１２からＲＥＡＤＹキュー８１０に移行させる。（６）および（７）により、システムコール、ないしは、ＤＭＡ転送の完了待ちをしていて、かつ、システムコール、ないしは、ＤＭＡ転送が完了したスレッドは再度実行可能となり、次にスケジュールされて実行開始されるのを待つこととなる。なお、ＤＭＡ転送の完了を検出する方法は後述する。【００６０】
スレッドの実行が完了した場合、または、スレッドの実行を途中で中断した場合には、マスターコントロールスレッド５５０は、完了または中断したスレッドのスレッド管理セル９００をＦＩＮキュー８１３に移行する（図１０の（８）、（９）に対応する）。なお、スレッドの実行中断は、スレッドがＲＥＡＤＹキュー８１０、ＩＯＷＡＩＴキュー８１１、またはＮＶＭＷＡＩＴキュー８１２に入っている場合にも起こり得るので、これらの場合にも、マスターコントロールスレッド５５０は、中断したスレッドのスレッド管理セル９００をＦＩＮキュー８１３に移行する。また、スレッドの実行が完了した場合、または、スレッドの実行を途中で中断した場合に、マスターコントロールスレッド５５０は、完了または中断して処理が終了したスレッドに後述するＰＩＮ領域を割当てていた場合には、割当てを解除、すなわちＰＩＮ領域として割当てていたメモリ空間を解放する。【００６１】
ＦＩＮキュー８１３に入っているスレッド管理セル９００は、ヒープ領域５１３が不足する場合には、マスターコントロールスレッド５５０により適宜開放される。また、新しいスレッドが生成される（図１０の（１）の動作）際には、ＦＩＮキュー８１３に入っているスレッド管理セル９００から優先的に使われる。それでもスレッド管理セル９００が足りない場合には、マスターコントロールスレッド５５０は、ヒープ領域５１３からスレッド管理セル９００用の領域を割当てる。【００６２】
ＮＶＭ転送要求管理情報５１５は、ＲＥＱキュー８２０、ＷＡＩＴキュー８２１、ＣＯＭＰＬＥＴＥキュー８２２、およびＤＩＳＰＯＳＥキュー８２３から構成される。各キューにエンキューされるエントリは、図１１に示すＮＶＭ転送要求管理セル１１００である。ＮＶＭ転送要求管理セル１１００は、Ｖａｌｉｄフラグ１１０１、要求元スレッドＩＤ１１０２、スレッド管理セルポインタ１１０３、転送方向１１０４、転送状態１１０５、転送元アドレス１１０６、転送データ長１１０７、および転送先アドレス１１０８から構成される。【００６３】
Ｖａｌｉｄフラグ１１０１は、当該ＮＶＭ転送要求管理セル１１００が有効であるかどうかを示すフラグである。要求元スレッドＩＤ１１０２は、当該ＮＶＭ転送要求を発生させたスレッドのスレッドＩＤを格納するものである。スレッド管理セルポインタ１１０３は、当該ＮＶＭ転送要求を発生させたスレッドを管理するスレッド管理セル９００へのポインタである。つまり、このポインタを辿って得られたスレッド管理セル９００に格納されているスレッドＩＤ９０２は、要求元スレッドＩＤ１１０２と同一である。【００６４】
転送方向１１０４は、ＮＶＭ転送の方向を指定するための情報で、ロード、または、ストアを指定する。ロードはＣＰＵに近い側、つまりメインメモリにＮＶＭ３２０からデータを読み出す方向である（もしくは、ＮＶＭ３２０に格納されているデータをメインメモリに書込むとも言える）。ストアは、ＣＰＵに遠い側、つまりＮＶＭ３２０にメインメモリからデータを読み出す方向である（もしくは、メインメモリに格納されているデータをＮＶＭ３２０に書込むとも言える）。転送状態１１０５は、ＮＶＭ転送が現在どのような状態にあるかを示すものである。転送の状態に関しての詳細は後述する。【００６５】
転送元アドレス１１０６は、ＮＶＭ転送で行うＤＭＡ転送の転送元となるアドレスである。転送方向１１０４がロード（ＮＶＭ３２０からメインメモリに転送）である場合、転送元アドレス１１０６はＮＶＭ３２０で用いられる識別子となる。この識別子には、メインメモリのアドレス空間（物理アドレス空間、仮想アドレス空間）と異なる、ＮＶＭ３２０専用のアドレス空間を用いて良い。一般的に、メインメモリのアドレス空間は、その時代でコンピュータに搭載可能と想定されるＤＲＡＭの量で制約を受けており、例えば今日の６４ビットアーキテクチャのプロセッサであっても、コスト面から現実的に利用可能なＤＲＡＭの量を考慮して、４８ビット程度の空間しか実装していないことが多い。そのため、大容量のＮＶＭをメインメモリのアドレス空間にマッピングすることは難しい。転送方向１１０４がストア（メインメモリからＮＶＭ３２０に転送）である場合、転送元アドレス１１０６は、メインメモリのアドレス空間であり、特に後述する理由から物理アドレス空間上のアドレスで指定される。【００６６】
転送データ長１１０７は、ＮＶＭ転送で行うＤＭＡ転送の転送長を指定する。転送先アドレス１１０８は、ＮＶＭ転送で行うＤＭＡ転送の転送先となるアドレスである。転送元アドレス１１０６と同様に、転送方向１１０４に応じて、ＮＶＭ３２０で用いている識別子を指定するか、物理アドレスを指定するかのどちらかで利用される。【００６７】
ＮＶＭ転送要求の状態遷移に関して、図１２の状態遷移図と、図８のキュー構成を対比させながら説明する。【００６８】
まず、図１２の（１）スレッドからのアクセス要求、および（２）ＮＮＭサブシステムへのＤＭＡ転送要求について説明する。スレッドがメインメモリとＮＶＭ３２０との間でのＤＭＡ転送を必要とする場合、マスターコントロールスレッド５５０は、ＮＶＭ転送要求管理セル１１００を生成して、生成したセル１１００をＲＥＱキュー８２０にエンキューする。ＤＭＡ転送を開始するためには、ＭＭＲ３１１にＤＭＡ転送の開始を要求するコマンドを書込まなければならない。ここで、ＮＶＭサブシステム３００にＭＭＲ３１１を複数セット用意して、さらなる処理の高速化のために複数のＤＭＡ転送を同時並行的に進める多重ＤＭＡ転送に対応させることもできる。マスターコントロールスレッド５５０は、ＮＶＭサブシステム３００のＤＭＡ転送に空きがある場合に、ＲＥＱキュー８２０からＮＶＭ転送要求管理セル１１００をデキューして、ＭＭＲ３１１にコマンドを書込むことで、ＤＭＡ転送を開始する。そして、マスターコントロールスレッド５５０は、ＤＭＡ転送中となるＮＶＭ転送要求管理セル１１００をＷＡＩＴキュー８２１にエンキューして、ＤＭＡ転送の完了待ちを行う。【００６９】
次に、図１２の（３）ＮＶＭシステムからのＤＭＡ転送完了通知、（４）スレッドへのアクセス完了通知、および（５）ＮＶＭアクセス管理セルの解放・再利用について説明する。ＤＭＡ転送の完了は、ＮＶＭサブシステム３００からプロセッサ２１０、２２０への割込みで通知される方式を取ることが可能である。また、マスターコントロールスレッド５５０が、ＭＭＲ３１１をポーリングすることでＤＭＡ転送の完了を知ることも出来る。但し、割込みを用いる場合には、割込みを受けるのはオペレーティングシステムが有する割込みハンドラであり、カーネル空間への切替えが必要となり、オーバヘッドが大きい。そこで、本実施例ではＭＭＲ３１１にＤＭＡ転送が完了したことを示すフラグを設けて、このフラグをマスターコントロールスレッド５５０がポーリングする。また、特に複数のＤＭＡ転送を同時並行的に行う場合には、複数のＤＭＡ転送の完了を個別に検出することすら、オーバヘッドの要因となる。そこで、本実施例の情報処理システム１００では、マスターコントロールスレッド５００は、ユーザレベルスレッドやスケジューリングに支障の無い程度の間隔、換言すればマスターコントロールスレッド５００において他に行うべき処理が無い場合にＭＭＲ３１１をポーリングし、複数のＤＭＡ転送の完了を一度のポーリングで検出する。【００７０】
ＤＭＡ転送の完了が検出されたＮＶＭ転送要求管理セル１１００は、マスターコントロールスレッド５５０によって、ＷＡＩＴキュー８２１からデキューされて、ＣＯＭＰＬＥＴＥキュー８２２にエンキューされる。なお、ＤＭＡ転送の完了順序はＷＡＩＴキュー８２１にエンキューされている順序とは限らず、ＷＡＩＴキュー８２１へのアクセスはＦＩＦＯになるとは限らない。【００７１】
ＣＯＭＰＬＥＴＥキュー８２２にエンキューされたＮＶＭ転送要求管理セル１１００は、ＤＭＡ転送を管理するという観点から言えば、ＤＭＡ転送は既に完了しているのでもう不要な情報である。しかし、本実施例の情報処理システム１００では、このＣＯＭＰＬＥＴＥキュー８２２に格納されているＮＶＭ転送要求管理セル１１００を元にして、ＮＶＭＷＡＩＴキュー８１２に格納されているスレッド管理セル９００を、ＮＶＭＷＡＩＴキュー８１２からＲＥＡＤＹキュー８１０に移行させることを特徴としている。つまり、ＤＭＡ転送の完了状況に応じて、当該ＤＭＡ転送要求を発生させる要因となったスレッドを、ＤＭＡ転送完了待ちの状態から実行可能な状態に状態遷移させることが、本実施例におけるＤＭＡ転送とマルチスレッディングの連携という特徴的な動作となる。【００７２】
マスターコントロールスレッド５５０は、定期的にＣＯＭＰＬＥＴＥキュー８２２を監視し、ＣＯＭＰＬＥＴＥキュー８２２にＮＶＭ転送要求管理セル１１００が存在する場合にはそれをデキューして、要求元スレッドＩＤ１１０２をキーとして、ＮＶＭＷＡＩＴキュー８１２の中から対応するスレッド管理セル９００を探す。マスターコントロールスレッド５５０は、対応するスレッド管理セル９００を見つけたら、該スレッド管理セル９００をＲＥＡＤＹキュー８１０にエンキューすると共に、ＮＶＭ転送要求管理セル１１００をＤＩＳＰＯＳＥキュー８２３にエンキューする。なお、ＤＩＳＰＯＳＥキュー８２３は、ＦＩＮキュー８１３と同様に、使用済みのＮＶＭ転送要求管理セル１１００の再利用を行うためのものである。【００７３】
図１３は、これまでに説明してきたユーザレベルマルチスレッディングとＤＭＡ転送の連携で、プロセス４１０内のスレッドがどのように起動・停止するかを示す説明図である。以下に、図１３に沿ってスレッドのライフサイクルと、ＤＭＡ転送との連携を説明する。【００７４】
プロセス４１０は、カーネルレベルスレッド１−１〜１−５をオペレーティングシステムから割当てられている。プロセス４１０は、カーネルレベルスレッド１−１〜１−５に任意のスレッドを割当てて実行することができる。ここで、本実施例の情報処理システム１００では、カーネルレベルスレッド１−１上にマスターコントロールスレッド５５０が固定的に割当てられる。プロセス４１０は、起動すると、マスターコントロールスレッド５５０をカーネルレベルスレッド１−１で実行する。【００７５】
例えば、大規模なグラフ処理を行う場合、マスターコントロールスレッド５５０はグラフの頂点毎に対応するスレッドを立てて処理を行う。図１３の例では、ユーザレベルスレッドＡ、Ｂ、Ｃ、Ｄ、Ｅ、Ｆ、Ｇがそれに対応し、マスターコントロールスレッド５５０は、まずユーザレベルスレッドＡ、Ｄ、Ｆ、Ｇをそれぞれカーネルレベルスレッド１−２〜１−５で起動する。【００７６】
スレッドの実行状況を時系列に見て行くと、（１）においてユーザレベルスレッドＡがマスターコントロールスレッド５５０に対して、ＮＶＭ３２０からのＤＭＡ転送を要求し、また該ＤＭＡ転送が終わらないと他に行える処理が無いことを申告している。マスターコントロールスレッド５５０は、対応するＮＶＭ転送要求管理セル１１００を生成してＲＥＱキュー８２０にエンキューすると共に、ユーザレベルスレッドＡの実行を一時停止し、そのコンテキストをスレッド管理セル９００に退避して、ＮＶＭＷＡＩＴキュー８１２にエンキューする。これにより、カーネルレベルスレッド１−２には実行すべきスレッドが無くなるため、マスターコントロールスレッド５５０は、ＲＥＡＤＹキュー８１０からスレッド管理セル９００を１個デキューして、そのスレッドをカーネルレベルスレッド１−２で実行する（図１３では、マスターコントロールスレッド５５０は、ユーザレベルスレッドＢの実行を開始している）。【００７７】
次に、カーネルレベルスレッド１−３上で実行されているユーザレベルスレッドＤが（２）で、（１）と同様にマスターコントロールスレッド５５０にＤＭＡ転送の要求を出している。しかし、（２）の場合には、ユーザレベルスレッドＤはマスターコントロールスレッド５５０に対してＤＭＡ転送の完了を待たずとも他に行える処理があることを申告しているため、マスターコントロールスレッド５５０は、ユーザレベルスレッドＤを一時停止させることなく、実行を続行させている。例えば、ユーザレベルスレッドで必要となるデータを予めＤＭＡ転送しておき、その後別の処理を行うような場合がこのケースにあたる。つまり、ＤＭＡ転送でＮＶＭ３２０上のデータをプリフェッチしているような動作になる。【００７８】
その後、ユーザレベルスレッドＢ、Ｄはそれぞれ処理が一旦停止され、ＲＥＤＡＹキュー８１０に積まれていた次のスレッドの実行が開始される。図１３の例では、ユーザレベルスレッドＢは、ユーザレベルスレッドＣの実行が完了した後に再度実行予定とされ、ユーザレベルスレッドＤは、先に要求したＤＭＡ転送の完了待ちに入る。続いて図１３の例では、ユーザレベルスレッドＣ、Ｅの実行が開始されている。ユーザレベルスレッドＣの実行中に（３）で（１）で要求したＤＭＡ転送に対する完了が通知されたので、ユーザレベルスレッドＡがＲＥＡＤＹキュー８１０にエンキューされる。このユーザレベルスレッドＡは、ユーザレベルスレッドＣの実行が終了（ないしは一時停止）した後にスケジュールされて、カーネルスレッド１−２で動作を開始している。【００７９】
カーネルレベルスレッド１−４では、（４）でユーザレベルスレッドＦが自主的に資源を返上して停止する。その後、カーネルレベルスレッド１−４では処理すべきスレッドが無い空白の時間がしばらく発生し、その後、ユーザレベルスレッドＢが再びスケジュールされる。前述したように、ユーザレベルスレッドＢはユーザレベルスレッドＣの完了後に再スケジュールされる予定だったが、元々利用していたカーネルスレッド１−１をユーザレベルスレッドＡに取られてしまったので、カーネルスレッド１−４上で動作する。プロセス内は各スレッド間で仮想アドレス空間が共有されるので、コンピュータの構成におけるＳＭＰのように各カーネルスレッド１−１〜１−５は対等なものとして利用可能である。【００８０】
図１４は、本実施例におけるスレッドコンテキスト（スレッド管理情報５１４）と、データのＤＭＡ転送の関係を示した概念図である。スレッドが処理すべきデータはＤＭＡ転送でＮＶＭ３２０からＰＩＮ領域プール５１６を介してメインメモリに転送され、スレッドを実行するために必要なコンテキストは、退避されていたメインメモリから各ハードウェアスレッド（カーネルレベルスレッドはハードウェアスレッドに一対一対応している）にロードされる。【００８１】
図１５は、本実施例におけるマスターコントロールスレッド５５０のスケジューリング動作を示すフローチャートである。ステップＳ１５０１で、マスターコントロールスレッド５５０は、スケジューリングを開始する。スケジューリングを開始する契機はカーネルレベルスレッドに空きが検出された時である。次に、ステップＳ１５０２で、マスターコントロールスレッド５５０は、ＲＥＡＤＹキュー８１０からスレッド管理セル９００をデキュー可能かどうか判定する。デキューできなければその時点でスケジューリングは終了し、マスターコントロールスレッド５５０は、次にスケジューリング可能となる契機を待つ。デキューできる場合には、ステップＳ１５０３で、マスターコントロールスレッド５５０は、スレッド管理セル９００をＲＥＡＤＹキューからデキューする。【００８２】
その後、ステップＳ１５０４で、マスターコントロールスレッド５５０は、ＰＩＮ領域プール５１６にＰＩＮ領域割当てが可能かどうかを判定する。本実施例の情報処理システム１００では、図１５に示すスレッドのスケジューリングにおいて、ＰＩＮ領域の割当ての可否を判定することを特徴としている。【００８３】
本実施例の情報処理システム１００では、スレッド毎にＤＭＡ転送を行う。ＤＭＡ転送はプロセッサやオペレーティングシステムの介在なしに行われるため、基本的には物理アドレス空間内で転送が行われることになる。すなわち、仮想アドレス空間はオペレーティングシステムの管理下であるため、ＤＭＡ転送からは仮想アドレス空間を用いた転送が出来ない。そこで、ＤＭＡ転送を行う場合には、転送対象となるメインメモリ上の領域が物理的なメモリ上にあり、物理アドレス空間上に配置されていることが必須となる。そのため、ＤＭＡ転送を行うプロセスは、プロセスの仮想アドレス空間中の一部の領域を物理アドレス空間のＤＲＡＭ領域に固定的に割当て、仮想記憶によるページアウト・ページインを生じさせないようにする。この物理的な存在があるメモリに固定的に割当てられた領域が、ＰＩＮ領域であり、本実施例ではプロセスに対してＰＩＮ領域プール５１６として用意される。なお、ＰＩＮ領域５１６の大きさは、予めユーザが設定できる。【００８４】
ここで、プロセスに用意したＰＩＮ領域プール５１６をスレッド毎に均等に分割して利用するという方法もあり得るが、これはスレッドの必要とするデータ量が予め分かっていて、かつ、各スレッドの要求するＰＩＮ領域の大きさが均等でないと上手く利用できない。【００８５】
そこで、本実施例の情報処理システム１００では、プロセスにＰＩＮ領域プール５１６を用意し、プロセスが持つＰＩＮ領域をリソースプールとして管理する。その上で、スレッドが起動時に自スレッドで必要とするＰＩＮ領域の大きさをスレッド管理セルのバッファ要求フラグ９０７、及び、バッファ要求サイズ９０８でマスターコントロールスレッド５５０に申告し、マスターコントロールスレッド５５０からＰＩＮ領域の割当てを受けて該スレッドが実行に移る。【００８６】
そのため、ステップＳ１５０４では、現在のＰＩＮ領域プール５１６の残量と、起動しようとしているスレッドが要求している領域の量とを比較して、スレッドの起動可否を判定する。実行中のスレッドがＰＩＮ領域プール５１６の割当てを得ていれば、残量はその分少ない。ＰＩＮ領域プール５１６の残量が不足すると判定された場合には、ステップＳ１５０６で、マスターコントロールスレッド５５０は、当該スレッドをＲＥＡＤＹキュー８１０の末尾に積み、他のスレッドを優先して実行に移す。一方、ＰＩＮ領域プール５１６から必要な領域を確保できる場合には、ステップＳ１５０５で、マスターコントロールスレッド５５０は、申告をしてきたスレッドにＰＩＮ領域を割当てて、スレッドの切替えを行う。マスターコントロールスレッド５５０は、ＰＩＮ領域の割当てについて、スレッド管理セル９００のバッファ割当てフラグ９０９とバッファ領域先頭アドレス９１０に書込むことで、申告をしてきたスレッドに割当てた領域を通知する。【００８７】
このように、実行予定のスレッドがメインメモリの物理アドレス空間上でＤＭＡ転送に必要とする容量に応じてメモリ空間を確保することで、各スレッドの要求するＰＩＮ領域の大きさのばらつきに対して柔軟に対応することが可能となる。ひいては、効率的なＤＭＡ転送を実現でき、情報処理システム１００の処理を高速化できる。
【実施例２】
【００８８】
本実施例では、さらに大規模なグラフ処理を行うなどの状況で、スレッド管理セル９００がメインメモリに収まらないほど大量のスレッドであっても実行することのできる情報処理システムの例を説明する。【００８９】
大規模なグラフ処理などで頂点の数が莫大になると、スレッドの数も莫大になる。その時、全てのスレッドのスレッド管理セル９００をメインメモリ中に保持しておくことすら不可能になる。そこで、本実施例では、図１６に示すようにスレッド管理セル９００の実体をＮＶＭ３２０に配置し、必要に応じてメインメモリにＤＭＡ転送して利用する。さらに、マスターコントロールスレッド５５０がＮＶＭ３２０上のスレッド管理セル９００を、それが必要になる以前に予めＤＭＡ転送しておく。すなわち、スレッド管理セル９００に対するプリフェッチが行われる。図１６に示したように、スレッドコンテキストは、メインメモリとＮＶＭとの間でＤＭＡ転送され、退避または呼び出される。【００９０】
スレッド管理セル９００は基本的にＲＥＡＤＹキュー８１０にエンキューされている順番で必要となるので、ＲＥＤＡＹキュー８１０を監視して、その順序でプリフェッチを行えば良い。また、ＲＥＤＡＹキュー８１０の先頭アドレスを保持し、プロセッサと並行してＲＥＡＤＹキュー８１０を読み出してプリフェッチを行うＤＭＡコントローラを別途用意しても良い。【００９１】
以上、本発明者によってなされた発明を実施の形態に基づき具体的に説明したが、本発明は前記実施の形態に限定されるものではなく、その要旨を逸脱しない範囲で種々変更可能であることはいうまでもない。
【符号の説明】
【００９２】
１００：情報処理システム、１１０：ノード、１２０：ノード間ネットワーク、１３０：ＮＶＭサブシステムインターコネクト、２１０、２２０：プロセッサ、２３０、２４０：ＤＩＭＭ、２５０：Ｉ／Ｏハブ、２６０：ＮＩＣ、２７０：ディスクコントローラ、２８０：ＨＤＤ、２９０：ＳＳＤ、３００：ＮＶＭサブシステム、３１０：ハイブリッドメモリコントローラ、３２０：ＮＶＭ（Ｎｏｎ−ｖｏｌａｔｉｌｅ  Ｍｅｍｏｒｙ、不揮発メモリ）、３３０：揮発性メモリ、３１１：ＭＭＲ（Ｍｅｍｏｒｙ  Ｍａｐｐｅｄ  Ｒｅｇｉｓｔｅｒ）、４１０、４２０：プロセス、５１０：スレッド間共有リソース、５１１：プログラムコード、５１２：グローバル変数、５１３：ヒープ領域、５１４：スレッド管理情報、５１５：ＮＶＭ転送要求管理情報、５１６：ＰＩＮ領域プール。
【図１】
2014016951.tif 000003
【図２】
2014016951.tif 000004
【図３】
2014016951.tif 000005
【図４】
2014016951.tif 000006
【図５】
2014016951.tif 000007
【図６】
2014016951.tif 000008
【図７】
2014016951.tif 000009
【図８】
2014016951.tif 000010
【図９】
2014016951.tif 000011
【図１０】
2014016951.tif 000012
【図１１】
2014016951.tif 000013
【図１２】
2014016951.tif 000014
【図１３】
2014016951.tif 000015
【図１４】
2014016951.tif 000016
【図１５】
2014016951.tif 000017
【図１６】
2014016951.tif 000018
【国際調査報告】
2014016951.tif 000019
2014016951.tif 000020
2014016951.tif 000021
2014016951.tif 000022