(57)【要約】【課題】分岐命令、ループ命令を含む各種計算処理の性能向上を図る。【解決手段】本発明の例に係る計算機システムは、他と共有しないローカルメモリ１１０，２１０，３１０を有する複数の計算主体１００，２００，３００と、複数の計算主体１００，２００，３００により共有される共有メモリ３０とを備える。複数の計算主体１００，２００，３００の各々は、ローカルメモリ１１０，２１０，３１０から共有メモリ３０へのデータ更新を一時的に禁止する機能を持つストア制御機構１２０，２２０，３２０を備える。【選択図】      図１
2008210027.tif 000002
【特許請求の範囲】
【請求項１】
他と共有しないローカルメモリを有する複数の計算主体と、前記複数の計算主体により共有される共有メモリとを具備し、前記複数の計算主体の各々は、前記ローカルメモリから前記共有メモリへのデータ更新を一時的に禁止する機能を持つストア制御機構を備えることを特徴とする計算機システム。
【請求項２】
前記複数の計算主体は、マルチコアプロセッサを構成し、前記複数の計算主体の各々は、ＣＰＵコアであることを特徴とする請求項１に記載の計算機システム。
【請求項３】
前記ストア制御機構は、アーキテクチャ命令によって有効／無効が制御されるフラグに基づいて、前記データ更新を一時的に禁止するか否かを決定することを特徴とする請求項１又は２に記載の計算機システム。
【請求項４】
他と共有しないローカルメモリを有する複数の計算主体をスレッドとする実行コードを持つコンパイラにおいて、前記ローカルメモリから前記複数の計算主体により共有される共有メモリへのデータ更新を一時的に禁止するＣＰＵ命令又はシステムコールを具備することを特徴とする並列化コンパイラ。
【請求項５】
請求項４に記載の並列化コンパイラにおいて、
条件の確定のための計算に一定以上の時間がかかる場合に、前記条件の確定後の命令列の全て又は一部を、前記条件の確定のための計算を実行している計算主体とは異なる他の計算主体を用いて投機的に実行し、
少なくとも前記計算が終了するまでは、前記他の計算主体では前記共有メモリへのデータ更新を禁止するオブジェクトコードを生成可能な
ことを特徴とする並列化コンパイラ。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、計算機システム及び並列化コンパイラに関する。
【背景技術】
【０００２】
従来の分岐命令の性能向上に対しての施策は、分岐履歴などを用いた予測による投機実行がほとんどである。このような方式の場合、結局、分岐先として１つのみ選んで実行するため、分岐先の数が多くなればなるほど予測精度が低下する。
【０００３】
例えば、特許文献１に開示される発明では、分岐予測方式により、選択される分岐先の予測精度を向上させる。しかし、予測に履歴を用いるため、ランダムに分岐条件が変わる場合には、分岐先の数の増加に応じて予測精度が低下する。
【特許文献１】特開平１０−１３３８７３号公報
【発明の開示】
【発明が解決しようとする課題】
【０００４】
本発明では、分岐命令、ループ命令を含む各種計算処理の性能向上を図る技術について提案する。
【課題を解決するための手段】
【０００５】
本発明の例に係る計算機システムは、他と共有しないローカルメモリを有する複数の計算主体と、複数の計算主体により共有される共有メモリとを備え、複数の計算主体の各々は、ローカルメモリから共有メモリへのデータ更新を一時的に禁止する機能を持つストア制御機構を備える。
【０００６】
本発明の例に係る並列化コンパイラは、他と共有しないローカルメモリを有する複数の計算主体をスレッドとする実行コードを持ち、ローカルメモリから複数の計算主体により共有される共有メモリへのデータ更新を一時的に禁止するＣＰＵ命令又はシステムコールを備える。
【発明の効果】
【０００７】
本発明によれば、分岐命令、ループ命令を含む各種計算処理の性能向上を図ることができる。
【発明を実施するための最良の形態】
【０００８】
以下、図面を参照しながら、本発明の例を実施するための最良の形態について詳細に説明する。
【０００９】
１．  概要  
本発明では、第一に、分岐命令において予測という手段を採らず、複数のプロセッサに複数の分岐先の処理を投機的に実行させることで、分岐命令の性能向上を図る。第二に、ループ命令におけるループ制御変数の値域の算出前にループを投機的に実行させ、ループ命令の性能向上を図る。
【００１０】
具体的には、他と共有しないローカルメモリを有する複数のＣＰＵコア（計算主体）と、これら複数のＣＰＵコアにより共有される共有メモリとを備えるマルチコアプロセッサシステムにおいて、各々のＣＰＵコア内に、ローカルメモリから共有メモリへのデータ更新を一時的に禁止する機能を持つストア制御機構を設けることで、分岐先の処理又はループの投機的な実行を可能にする。
【００１１】
また、並列化コンパイラに関しては、複数のＣＰＵコアをスレッドとする実行コードを持つと共に、ローカルメモリから共有メモリへのデータ更新を一時的に禁止するＣＰＵ命令又はシステムコールを備える。
【００１２】
これにより、マルチコアプロセッサシステムにおける分岐条件、ループ条件などの各種条件の判定からその後の処理までを効率的に行い、性能向上を図る。
【００１３】
２．  実施の形態  
次に、最良と思われるいくつかの実施の形態について説明する。
【００１４】
(1)   計算機システム  
図１は、本発明の例に係る計算機システムを示している。  
この計算機システム１０は、複数のＣＰＵコア１００，２００，３００を有するマルチコアプロセッサ２０を有する。
【００１５】
マルチコアプロセッサ２０は、複数のＣＰＵコア１００，２００，３００と、これらに共有される１つの共有メモリ３０とを有する１つのチップである。
【００１６】
但し、本例においては、複数のＣＰＵコア１００，２００，３００及び共有メモリ２０の各々が１つのチップから構成されていてもよい。また、本例では、ＣＰＵコア１００，２００，３００の数を３つとしているが、これに限られることはない。
【００１７】
複数のＣＰＵコア１００，２００，３００は、それぞれ、ローカルメモリ１１０，２１０，３１０と、共有メモリ３０に対するデータ更新を一時的に禁止する機能を持つストア制御機構１２０，２２０，３２０と、共有メモリ更新禁止フラグ１３０，２３０，３３０とを有する。
【００１８】
共有メモリ更新禁止フラグ１３０，２３０，３３０の値が“１”の場合には、ストア制御機構１２０，２２０，３２０は、ローカルメモリ１１０，２１０，３１０から共有メモリ３０へのデータ更新を禁止する。
【００１９】
また、共有メモリ更新禁止フラグ１３０，２３０，３３０の値が“０”の場合には、ストア制御機構１２０，２２０，３２０は、ローカルメモリ１１０，２１０，３１０から共有メモリ３０へのデータ更新を許可する。即ち、ローカルメモリ１１，２１０，３１０をキャッシュメモリとする一般的な動作が実行される。
【００２０】
(2)   動作例  
図１の計算機システムの動作例について説明する。
【００２１】
A.  第１例  
図２は、分岐命令を投機的に処理するプログラムソースの例を示している。
【００２２】
ＩＦ分岐命令の条件判定には変数Ｘの値が確定していることが必要であるが、変数Ｘの決定には関数ｆ(a,b,c,d)の計算が必要である。
【００２３】
コンパイラは、関数ｆの計算に特定のステップ数以上を要すると判断すると、変数Ｘの確定に先立って、複数のスレッドの全て又は一部を投機的に実行するオブジェクトコードを出力する。
【００２４】
ここで、関数ｆの計算に要するステップ数は、システムのデフォルト値、コンパイラ引数、システム環境変数、又は、プログラム中のユーザによるディレクティブなどに基づいて判断される。
【００２５】
また、本例では、複数のスレッドは、関数ｆの命令列より構成されるスレッドと、ＩＦ分岐命令の分岐先の関数g0(x0)の命令列により構成されるスレッドと、分岐先の関数g1(x1)の命令列により構成されるスレッドと、分岐先の関数g2(x2) の命令列により構成されるスレッドから構成される。
【００２６】
図３及び図４は、オブジェクトコードによる動作例を示している。
【００２７】
オペレーティングシステムプロセスは、ＣＰＵコア０（図１のＣＰＵコア１００に相当）で実行される。
【００２８】
ユーザプログラムプロセス（オブジェクトコードのプロセス）は、当初、ＣＰＵコア０で実行されるスレッドＡからなる。図２の条件分岐の処理に進むと（Ｓ１００）、スレッドＡは、共有メモリ更新禁止フラグを有効にするシステムコール（有効化命令実行宣言）を発行する（Ｓ１１０）。
【００２９】
オペレーティングシステムプロセスは、このシステムコールを受けると、ＣＰＵコア１，２（図１のＣＰＵコア２００，３００に相当）で動作中の全てのスレッドを、停止、又は、ＣＰＵコア０に移動させる。また、ＣＰＵコア１，２内のローカルメモリの全てのデータを共有メモリに更新する。
【００３０】
この後、スレッドＡを続行する（Ｓ１２０〜Ｓ１３０）。
【００３１】
以後、オペレーティングシステムは、ＣＰＵコア１，２に対して、共有メモリ更新禁止フラグを無効にするシステムコール（無効化命令実行宣言）が発行されるまで、ユーザプログラムプロセス内のスレッド以外を割り当てることはない。
【００３２】
スレッドＡは、ユーザプログラムプロセスで実行を許可されたＣＰＵ数（本例では、２つ）に応じて、新規スレッドＢ，Ｃを生成する（Ｓ１４０）。
【００３３】
スレッドＢ，Ｃは、当初、共有メモリ更新禁止フラグの有効化命令を実行する。この後、スレッドＢは、分岐条件X=x0の場合の処理g0(x0)を実行し、スレッドＣは、分岐条件X=x1の場合の処理g1(x1)を実行する。実行が完了したら待機状態WAITにする。
【００３４】
また、ＣＰＵコア１，２のローカルメモリの容量やWAY数などにより、それ以上ストアを続けられないところまで処理が進んだ場合にも、その時点で待機状態WAITにする。
【００３５】
これらスレッドＢ，Ｃの処理に並行して、スレッドＡは、ＩＦ分岐命令の条件Ｘを計算する処理を実行する（Ｓ１７０）。計算の完了によりＸが確定すると（Ｓ１８０）、スレッドＡは、スレッドＢ，Ｃの状態を確認する。
【００３６】
スレッドＢ，Ｃが待機状態WAITである場合には、共有メモリ更新禁止フラグを無効にするシステムコール（無効化命令実行宣言）を発行する（Ｓ１９０）。
【００３７】
オペレーティングシステムは、X=x0の場合には、ＣＰＵコア２内のローカルメモリを無効化し、X=x1の場合には、ＣＰＵコア１内のローカルメモリを無効化する。また、オペレーティングシステムは、X≠(x0 or x1)の場合には、ＣＰＵコア１，２内のローカルメモリを共に無効化する。
【００３８】
この後、スレッドＢ，Ｃを続行する（Ｓ２００〜Ｓ２１０）。  
スレッドＢ，Ｃは、共有メモリ更新禁止フラグの無効化命令を実行する。
【００３９】
この後、条件Xに適合した分岐先の処理は、それ以上ストアを続けられないところまで処理が進んで待機状態WAITになっている場合には、処理を続行し、条件Xに適合しない分岐先の処理は行わずに、スレッドＢ，Ｃを終了する（Ｓ２２０，Ｓ２３０）。
【００４０】
また、スレッドＡは、X≠(x0 or x1)であった場合には、新たにg2(x2)を実行し（Ｓ２４０）、以後、ユーザプログラムプログラムを続行する（Ｓ２５０）。
【００４１】
このように、第１例では、ローカルメモリから共有メモリへの書き込みが一時的に禁止されたＣＰＵコア（スレッド）では、分岐先の処理を投機的に実行可能である。また、変数Ｘの確定後、変数Ｘにより選択された分岐先の処理を行ったＣＰＵコアのローカルメモリのデータのみを有効にし、他を無効にすれば、分岐条件の判定からその後の処理までを効率的に行うことができる。
【００４２】
B.  第２例  
図５は、ループ命令を投機的に処理するプログラムソースの例を示している。
【００４３】
ループ命令を実行するためには、ループ制御変数iの値域 0 < i < N が確定していることが必要であるが、Nの決定には関数h (e,f,g,h)の計算が必要である。
【００４４】
コンパイラは、関数hの計算に特定のステップ数以上を要すると判断すると、ループ制御変数iの値域を 0 < i < M と仮定し、実行時に使用できるＣＰＵコアの数に応じて、要素並列化された複数のスレッドを生成し、これらを並列して実行するオブジェクトコードを出力する。
【００４５】
Mの値は、例えば、使用可能なＣＰＵコア数が２つで、配列Bのために使用可能なローカルメモリの大きさが 128 KB/1CPUコアで、配列Bが64 bit浮動小数点数を要素として持つ場合には、128 KB / (64/8) x 2 の計算式により、M = 32 x 1024と仮定される。
【００４６】
尚、関数hの計算に要するステップ数は、システムのデフォルト値、コンパイラ引数、システム環境変数、又は、プログラム中のユーザによるディレクティブなどに基づいて判断される。
【００４７】
図６及び図７は、オブジェクトコードによる動作例を示している。
【００４８】
オペレーティングシステムプロセスは、ＣＰＵコア０（図１のＣＰＵコア１００に相当）で実行される。
【００４９】
ユーザプログラムプロセス（オブジェクトコードのプロセス）は、当初、ＣＰＵコア０で実行されるスレッドＡからなる。図５のループ命令の処理に進むと（Ｓ１００）、スレッドＡは、共有メモリ更新禁止フラグを有効にするシステムコール（有効化命令実行宣言）を発行する（Ｓ１１０）。
【００５０】
オペレーティングシステムプロセスは、このシステムコールを受けると、ＣＰＵコア１，２（図１のＣＰＵコア２００，３００に相当）で動作中の全てのスレッドを、停止、又は、ＣＰＵコア０に移動させる。また、ＣＰＵコア１，２内のローカルメモリの全てのデータを共有メモリに更新する。
【００５１】
この後、スレッドＡを続行する（Ｓ１２０〜Ｓ１３０）。
【００５２】
以後、オペレーティングシステムは、ＣＰＵコア１，２に対して、共有メモリ更新禁止フラグを無効にするシステムコール（無効化命令実行宣言）が発行されるまで、ユーザプログラムプロセス内のスレッド以外を割り当てることはない。
【００５３】
スレッドＡは、ユーザプログラムプロセスで実行を許可されたＣＰＵ数（本例では、２つ）に応じて、ループ制御変数の値域を 0 < i < M と仮定し、新規スレッドＢ，Ｃを生成する（Ｓ１４０）。
【００５４】
スレッドＢ，Ｃは、当初、共有メモリ更新禁止フラグの有効化命令を実行する。この後、スレッドＢは、 i = 0 〜 M/2 のイタレーションを実行し、スレッドＣは、i = M/2 + 1〜M のイタレーションを実行する。実行が完了したら待機状態WAITにする。
【００５５】
これらスレッドＢ，Ｃの処理に並行して、スレッドＡは、ループ制御変数iの値域を計算する処理を実行する（Ｓ１７０）。計算の完了によりNが確定すると（Ｓ１８０）、スレッドＡは、スレッドＢ，Ｃの状態を確認する。
【００５６】
スレッドＢ，Ｃが待機状態WAITである場合には、共有メモリ更新禁止フラグを無効にするシステムコール（無効化命令実行宣言）を発行する（Ｓ１９０）。
【００５７】
オペレーティングシステムは、N ≧ Mの場合には、何もせず、N < M/2の場合には、ＣＰＵコア１，２内の全ローカルメモリを無効化する。また、オペレーティングシステムは、M/2 < N < Mの場合には、ＣＰＵコア２内の全ローカルメモリを無効化する。
【００５８】
この後、ユーザプログラムプロセスでは、スレッドＢ，Ｃを続行する（Ｓ２００〜Ｓ２１０）。
【００５９】
スレッドＢ，Ｃは、共有メモリ更新禁止フラグの無効化命令を実行した後に終了する（Ｓ２２０，Ｓ２３０）。
【００６０】
この後、スレッドＡは、N > Mの場合には、M + 1〜Nについて通常の要素並列実行を新たに行い、N = Mの場合には、何もしない。また、スレッドＡは、N < M/2の場合には、0〜Nについて通常の要素並列実行を新たに行い、M/2 < N < Mの場合には、M/2 + 1〜Nについて通常の要並列実行を新たに行い、以後、ユーザプログラムプロセスを続行する（Ｓ２５０）。
【００６１】
このように、第２例では、ローカルメモリから共有メモリへの書き込みが一時的に禁止されたＣＰＵコア（スレッド）では、ループ制御変数の閾値を仮定し、ループ処理を投機的に要素並列実行可能である。また、閾値Nの確定後、ＣＰＵコアで投機実行された結果を使用すれば、ループ条件の判定からその後の処理までを効率的に行うことができる。
【００６２】
３．  まとめ  
本発明によれば、分岐命令、ループ命令を含む各種計算処理の性能向上を図ることができる。
【００６３】
即ち、本発明の例に係る計算機システムは、他と共有しないローカルメモリを有する複数の計算主体と、複数の計算主体により共有される共有メモリとを備え、複数の計算主体の各々は、ローカルメモリから共有メモリへのデータ更新を一時的に禁止する機能を持つストア制御機構を備える。
【００６４】
これにより、ローカルメモリから共有メモリへの書き込みを一時的に禁止し、分岐条件の処理と並行して分岐先の処理を実行し、閾値を確定する処理に並行してループ処理を実行することができる。
【００６５】
尚、複数の計算主体は、マルチコアプロセッサを構成し、複数の計算主体の各々は、ＣＰＵコアである。この場合、複数の計算主体は、１チップ化されていてもよいし、それぞれ別のチップに形成されていてもよい。
【００６６】
また、ストア制御機構は、アーキテクチャ命令によって有効／無効が制御されるフラグに基づいて、データ更新を一時的に禁止するか否かを決定する。
【００６７】
本発明の例に係る並列化コンパイラは、他と共有しないローカルメモリを有する複数の計算主体をスレッドとする実行コードを持ち、ローカルメモリから複数の計算主体により共有される共有メモリへのデータ更新を一時的に禁止するＣＰＵ命令又はシステムコールを備える。
【００６８】
条件の確定のための計算に一定以上の時間がかかる場合には、条件の確定後の命令列の全て又は一部を、条件の確定のための計算を実行している計算主体とは異なる他の計算主体を用いて投機的に実行し、少なくとも条件の確定のための計算が終了するまでは、他の計算主体では共有メモリへのデータ更新を禁止する。
【００６９】
これにより、例えば、複数の分岐先の処理を投機的に実行する複数のスレッドを生成する実行コードを出力可能なコンパイラと、そのスレッド生成前に、ローカルメモリから共有メモリへの書き込みを禁止にする命令若しくはシステムコールを発行する実行コードを出力可能なコンパイラを提供できる。
【００７０】
また、ループ命令においても同様であり、ループ制御変数の値域の確定に一定以上の時間がかかる場合に、その確定に先立って値域を仮定し、ループ処理を投機的に要素並列実行することを可能にする。
【００７１】
このような投機実行の際、実際には実行されないイタレーションの処理が共有メモリを更新してしまうことを防ぐため、各ＣＰＵコア内のローカルメモリのみを用いてプログラムを実行できる環境を実現できる。
【００７２】
本発明は、コンピュータシステムにおけるプロセッサアーキテクチャ、オペレーティングシステム及びコンパイラに使用される。
【００７３】
本発明の例は、上述の実施の形態に限定されるものではなく、その要旨を逸脱しない範囲で、各構成要素を変形して具体化できる。また、上述の実施の形態に開示されている複数の構成要素の適宜な組み合せにより種々の発明を構成できる。例えば、上述の実施の形態に開示される全構成要素から幾つかの構成要素を削除してもよいし、異なる実施の形態の構成要素を適宜組み合わせてもよい。
【図面の簡単な説明】
【００７４】
【図１】本発明の例に係わる計算機システムを示す図。
【図２】分岐命令を含んだプログラムソースを示す図。
【図３】オブジェクトコードによる分岐命令の動作例を示す図。
【図４】オブジェクトコードによる分岐命令の動作例を示す図。
【図５】ループ命令を含んだプログラムソースを示す図。
【図６】オブジェクトコードによるループ命令の動作例を示す図。
【図７】オブジェクトコードによるループ命令の動作例を示す図。
【符号の説明】
【００７５】
１０：  計算機システム、  ２０：  マルチコアプロセッサ、  ３０：  共有メモリ、  １００，２００，３００：  ＣＰＵコア、  １１０，２１０，３１０：  ローカルメモリ、  １２０，２２０，３２０：  ストア制御機構、  １３０，２３０，３３０：  共有メモリ更新禁止フラグ。
【図１】
2008210027.tif 000003
【図２】
2008210027.tif 000004
【図３】
2008210027.tif 000005
【図４】
2008210027.tif 000006
【図５】
2008210027.tif 000007
【図６】
2008210027.tif 000008
【図７】
2008210027.tif 000009