(57)【要約】      （修正有）【課題】ハードウェア・トランザクション・メモリにおいて、スレッドレベル投機並列実行を可能とする。【解決手段】トランザクションの状態が投機的から非投機的に変わるとき、順序実行上の次のトランザクションの優先順位を上げるように、先行トランザクションの完了イベントを使用するスレッド優先順位制御機構が提供される。トランザクション衝突を検出するために、トランザクションのフットプリントを記録する連想メモリ３０６と、アドレス・レジスタ３０２とコンパレータ３０４とをもつ。スレッド・レベル投機機構は、メモリ同期命令の属性オペランドを記録するための優先順位上昇ビット３０８と、スレッド起き上がりイベントが発生し且つ、優先順位上昇ビットが1のとき、優先順位上昇イベントを生成する手段３１０と、命令が非トランザクション命令であるときにCAMがアドレスをロードまたはストアするのを禁止する手段３１２を備える。【選択図】図３
2014085839.tif 000002
【特許請求の範囲】
【請求項１】
トランザクション・メモリ・システムにおいて、
連想メモリとアドレス・レジスタとコンパレータとをもち、さらに非トランザクション・メモリアクセス命令をサポートする制御論理回路をもち、スレッド間同期をサポートするスレッド・レベル投機機構であって、
前記非トランザクション・メモリアクセス命令のメモリアドレスおよび属性オペランドを記録するための手段と、 
前記メモリアドレスへのアクセス・イベントを検出する手段と、
前記アクセス・イベントが検出されることに応答して、前記非トランザクション・メモリアクセス命令の属性オペランドがスレッド実行優先順位上昇を示す場合に、順位上昇イベントを生成する手段を有する、
スレッド・レベル投機機構。
【請求項２】
命令が前記非トランザクション・メモリアクセス命令であるときに、前記連想メモリがメモリアドレスを記録することを禁止する手段を有する、請求項１に記載の機構。
【請求項３】
前記非トランザクション・メモリアクセス命令が、スレッド間同期命令及び非トランザクション・ロード命令を含む、請求項１に記載の機構。
【請求項４】
前記スレッド間同期命令がメモリ同期命令である、請求項３に記載の機構。
【請求項５】
前記非トランザクション・ロード命令が、NTLG命令である、請求項３に記載の機構。
【請求項６】
トランザクション・メモリ・システムにおいて、
連想メモリとアドレス・レジスタとコンパレータとをもち、さらに非トランザクション・メモリアクセス命令をサポートする制御論理回路をもち、スレッド間同期をサポートするスレッド・レベル投機方法であって、
前記非トランザクション・メモリアクセス命令のメモリアドレスおよび属性オペランドを記録するステップと、 
前記メモリアドレスへのアクセス・イベントを検出するステップと、
前記アクセス・イベントが検出されることに応答して、前記非トランザクション・メモリアクセス命令の属性オペランドがスレッド実行優先順位上昇を示す場合に、順位上昇イベントを生成するステップを有する、
スレッド・レベル投機動作方法。
【請求項７】
命令が前記非トランザクション・メモリアクセス命令であるときに、前記連想メモリがメモリアドレスを記録することを禁止するステップを有する、請求項６に記載の方法。
【請求項８】
前記非トランザクション・メモリアクセス命令が、スレッド間同期命令及び非トランザクション・ロード命令を含む、請求項６に記載の方法。
【請求項９】
前記スレッド間同期命令がメモリ同期命令である、請求項８に記載の方法。
【請求項１０】
前記非トランザクション・ロード命令が、NTLG命令である、請求項８に記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、スレッドレベル投機並列実行を行うためのハードウェア機構に関する。
【背景技術】
【０００２】
従来より、リアルタイム・トランザクション・アプリケーションにおいて、応答時間は、カスタマにとって、最も重要な指標の1つである。しかし、応答時間は、プロセッサのシングル・スレッド性能に大きく依存する。最近になって、プロセッサのシングル・スレッド性能の伸びは鈍化する傾向にある。
【０００３】
そこで採用される既知の方法の一つとして、スレッドレベル投機並列実行がある。スレッドレベル投機並列実行とは、コンパイラまたはプログラマがシングル・スレッド・プログラムを投機的に並列化することを可能ならしめることによって、シングル・スレッド・プログラムの実行を高速化するものであるが、典型的には、複雑なハードウェア機構を必要とする。
【０００４】
さらに、実行速度高速化の技法として、ハードウェア・トランザクション・メモリが知られている。ハードウェア・トランザクション・メモリにおいては、トランザクション開始とトランザクション終了という特殊命令の間の命令の列をトランザクションとし、並列に実行されている2つのトランザクションがデータ・アクセスの衝突(書き込みの後の読み取り、書き込みの後の書き込み、あるいは読み取りの後の読み取りの衝突)を起こしたとき、ハードウェア機構がトランザクションの実行をキャンセルする。
【０００５】
しかし、ハードウェア・トランザクション・メモリだけではスレッドレベル投機並列実行を可能にすることはできない。なぜなら、スレッドレベル投機並列実行は、トランザクションが順序を保って完了することを要求するが、そのような完了順序をコントロールするためのランタイムが、トランザクションの衝突を引き起こすからである。
【０００６】
これに関連して、次のような従来技術が知られている。
【０００７】
特開２００９−５２１７６７号公報は、ソフトウェアトランザクションメモリ（ＳＴＭ）アクセスに対応する処理は、先行するハードウェアトランザクションメモリ（ＨＴＭ）アクセス処理が失敗する場合に実行することを開示する。
【０００８】
特開２０１０−５３２０５３号公報は、アトミックコミットの機能を利用して、マルチスレッド環境において、ディスパッチテーブルの更新を容易にするためにトランザクションメモリーハードウェアを使用し、ゲストプログラムカウンタをホストプログラムカウンタに変換するために、メインメモリーに保存されているディスパッチテーブルを使用するエミュレータを使用することを開示する。
【０００９】
ＷＯ２０１０／００１７３６号公報は、データを処理するマルチスレッドを実行する複数のプロセッサと、各スレッドが処理するデータ数に基づいて、前記複数のプロセッサがスレッドを実行する順序が満たすべき条件を決定し、当該条件を満たすように各スレッドの実行を開始させるデータ処理制御部とを含むマルチプロセッサシステムを開示する。
【００１０】
米国特許第８１５１２５２号明細書は、コンパイル時にプログラムの変数のスコープを定め、コンパイル時にプログラムにコードを挿入することにより、トランザクショナル・メモリを用いてプログラムを投機的に並列化することを開示する。この技法において、スコープの決定は、スコープされるスカラー変数が、ループ内の非還元データ依存性に関与し、定義されている外のループで使用されているかどうかと、ループ中のどの地点でスカラー変数が定義されているかに基づく。
【００１１】
Jeffrey Thomas Oplinger, "Enhancing Software Reliability with Speculative Threads", Graduate Studies of Stanford University, August 2004は、スレッド・レベル投機に基づくアーキテクチャを提示する。これによればプログラマは、プログラムの実行を検査するための監視コードを追加することができる。このアーキテクチャは、メインの計算と並列に監視コードを投機的に実行する際の速度低下を低減する。エラーから回復するために、プログラマは、細かい粒度のトランザクションを定義できる。そのトランザクションの副作用は、プログラム制御を介して、コミットされるかまたはアボートされる。これらのトランザクションは、スレッド・レベル投機ハードウェア・サポートを通じて、効率的に実装される。
【００１２】
Ruben Titos, Manuel E. Acacio, Jose M. Garcia, "Speculation-Based Conflict Resolution in Hardware Transaction Memory", Parallel & Distributed Processing, 2009. IPDPS 2009. IEEE International Symposium on 23-29 May 2009は、ハードウェア・トランザクション・メモリにおいて、多くの、衝突を起こしやすいトランザクションを共存させるために、熱心なポリシーの機構をベースとしつつも、熱心なポリシーと怠惰なポリシーの両方の利点を組み合わせた、ハイブリッド衝突管理機構を開示する。
【先行技術文献】
【特許文献】
【００１３】
【特許文献１】特開２００９−５２１７６７号公報
【特許文献２】特開２０１０−５３２０５３号公報
【特許文献３】ＷＯ２０１０／００１７３６号公報
【特許文献４】米国特許第８１５１２５２号明細書
【非特許文献】
【００１４】
【非特許文献１】Jeffrey Thomas Oplinger, "Enhancing Software Reliability with Speculative Threads", Graduate Studies of Stanford University, August 2004
【非特許文献２】Ruben Titos, Manuel E. Acacio, Jose M. Garcia, "Speculation-Based Conflict Resolution in Hardware Transaction Memory", Parallel & Distributed Processing, 2009. IPDPS 2009. IEEE International Symposium on 23-29 May 2009
【発明の概要】
【発明が解決しようとする課題】
【００１５】
上記従来技術は、ハードウェア・トランザクション・メモリにおける衝突検出と、それに対応する処理について開示するが、トランザクションが順序を保って完了することを要求する場合に、スレッドレベル投機並列実行を可能ならしめる仕組みについては示唆しない。
【００１６】
従って、この発明の目的は、ハードウェア・トランザクション・メモリにおいて、スレッドレベル投機並列実行を可能ならしめる機構を提供することにある。
【課題を解決するための手段】
【００１７】
本発明において、互いに依存関係を有していてもよい、複数のブロックからなる順次的なプログラムを、ハードウェア・トランザクション・メモリを使用して投機並列実行させて、衝突を検出し、間違えた投機実行から回復するものとする。
【００１８】
その際、従来のハードウェア・トランザクション・メモリに関する問題点として、次のようなことがあった。
-  その際、もとのプログラムのセマンティクスを維持するために、トランザクションの順序どおりの(in-order)完了を実施する必要がある。
-  トランザクションにおけるスレッドは、トランザクションを中止することなく、別のスレッドと交信することはできない。
-  さらに、ある命令のブロックが、全てのブロックのうちで最先になったとき、当該のブロックは、非投機的になる。
-  複数のスレッドがSMT（同時マルチスレッド）プロセッサ上で走行するとき、CPUリソースは、投機的実行ブロックと非投機的実行ブロックで均等に分割され、その間、リソース割り当てが非投機的実行ブロックに有利になるようになされるべきである。
【００１９】
さて、非トランザクション命令は、トランザクションの衝突を引き起こさないようにハードウェア・トランザクション・メモリ上でスレッド・レベル投機実行を可能ならしめるように、ランタイムがトランザクションの順序どおり(in-order)の完了を実施させるものとする。
【００２０】
そしてこの発明によれば、トランザクションの状態が投機的から非投機的に変わるとき、順序実行上の次のトランザクションの優先順位を上げるように、先行トランザクションの完了イベントを使用するスレッド優先順位制御機構が提示される。これにより、投機失敗によるリソースの無駄使いの量が低減される。
【００２１】
この発明の１つの側面によれば、トランザクション衝突を検出するために、トランザクションのフットプリントを記録する連想メモリと、アドレス・レジスタとコンパレータとをもち、CAD(compare and delay)命令をサポートする制御論理回路をもち、ハードウェア・トランザクション・メモリをサポートするスレッド・レベル投機機構が用意され、そのスレッド・レベル投機機構は、CAD命令の属性オペランドを記録するための優先順位上昇ビットと、スレッド起き上がりイベントが発生し且つ、前記優先順位上昇ビットが1のとき、優先順位上昇イベントを生成する手段と、命令が非トランザクション命令であるときにCAMがアドレスをロードまたはストアするのを禁止する手段を備える。
【００２２】
アプリケーション・プログラムのトランザクションは、優先順位上昇イベントに応答して、優先順位を上げる。
【発明の効果】
【００２３】
この発明によれば、トランザクションの状態が投機的から非投機的に変わるとき、順序実行上の次のトランザクションの優先順位を上げるように、先行トランザクションの完了イベントを使用するスレッド優先順位制御機構が設けられ、これにより、投機失敗によるリソースの無駄使いの量が低減される。
【図面の簡単な説明】
【００２４】
【図１】本発明が実施されるコンピュータ・システムのハードウェア構成を示す図である。
【図２】従来技術で、スレッドレベル投機並列実行処理における、トランザクション衝突が起こる例を示す図である。
【図３】本発明を実施するためのハードウェア論理構成の例を示す図である。
【図４】本発明の動作を説明するための図である。
【発明を実施するための形態】
【００２５】
以下、図面に従って、本発明の実施例を説明する。これらの実施例は、本発明の好適な態様を説明するためのものであり、発明の範囲をここで示すものに限定する意図はないことを理解されたい。また、以下の図を通して、特に断わらない限り、同一符号は、同一の対象を指すものとする。
【００２６】
図１を参照すると、本発明の一実施例に係るシステム構成及び処理を実現するためのコンピュータ・ハードウェアのブロック図が示されている。好適には、このコンピュータ・ハードウェアは、ＩＢＭ(登録商標) System z(登録商標)アーキテクチャに従う構成である。
【００２７】
図１において、システム・パス１０２には、ＣＰＵ１０４と、主記憶（ＲＡＭ）１０６と、ハードディスク・ドライブ（ＨＤＤ）１０８と、キーボード１１０と、マウス１１２と、ディスプレイ１１４が接続されている。ＣＰＵ１０４は、好適には、ｚ１０（商標）プロセッサ・チップのアーキテクチャに対して本発明に係る変更を加えたものである。すなわち、ＣＰＵ１０４は、マルチコアで、キャッシュメモリ、フェッチ・ユニット、デコード・ユニット、レジスタ・ファイル、演算ユニット、ロード・ストア・ユニット、トランザクション・メモリ制御回路、その他の論理回路や制御回路からなるが、この実施例では、ｚ１０（商標）の、トランザクション・メモリ制御回路、より詳しくは、CAD(compare and delay)命令の実行ユニットに変更が加えられる。このハードウェア的な変更の内容については、図３を参照して、後で説明する。
【００２８】
主記憶１０６は、好適には、１６ＧＢ以上の容量をもつものである。ハードディスク・ドライブ１０８は、例えば、１ＴＢ以上の容量をもつものである。
【００２９】
ハードディスク・ドライブ１０８には、個々に図示しないが、オペレーティング・システムが、予め格納されている。オペレーティング・システムは、例えば、ｚ／ＯＳであるが、ｚ／ＶＭ、ｚ／ＶＳＥなど、使用するコンピュータ・ハードウェアに適合する、その他のオペレーティング・システムも使用可能である。
【００３０】
キーボード１１０及びマウス１１２は、オペレーティング・システムの機能によって、ハードディスク・ドライブ１０８から主記憶１０６にロードされ、ディスプレイ１１４に表示されたプログラム（図示しない）を操作したり、文字を打ち込んだりするために使用される。
【００３１】
ディスプレイ１１４は、好適には、液晶ディスプレイであり、例えば、ＸＧＡ（１０２４×７６８の解像度）、またはＵＸＧＡ（１６００×１２００の解像度）などの任意の解像度のものを使用することができる。ディスプレイ１１４は、図示しないが、ＣＯＢＯＬのプログラムで計算された会計データなどの数値を表示するために使用される。
【００３２】
さて、本発明に係る具体的な構成を説明する前に、従来技術における、ハードウェア・トランザクション・メモリ(HTM)を使用した、スレッドレベル投機並列実行の完了順序制御の問題点について、図２を参照して説明する。図２は、複数の命令のブロック(t1及びt2)からなり、ポインタ・エイリアシング、すなわち、同一ポインタを複数の箇所からアクセスされることがあり得る、順次的コードを、スレッドレベル投機並列実行させる様子を示す。正しい結果を得るためには、t1の後t2を実行する必要がある。
【００３３】
このとき、図示されているように、次の３つのシナリオがありえる。
(A) ポインタ・エイリアシングが起きていない。すなわち、p ≠ qである。
この場合、t1とt2は、衝突を起こすことなく、トランザクションとして並列に実行することができる。
(B) ポインタ・エイリアシングが起き(p = q)、t1がt2の前に完了する。
この場合、HTMが、書き込みの後の読み取りの衝突を検出し、t2を再実行することが可能である。
(C) ポインタ・エイリアシングが起き(p = q)、t2がt1の前に完了する。
この場合、HTMが、読み取りの後の書き込みの衝突を検出し、t1をアボートさせるが、正しい結果を得るために、t1を再実行することはできない。
【００３４】
次に、メモリ同期（CAD）命令について説明する。本命令は、レジスタR1、ベースアドレスレジスタB2、メモリオディスプレイメント値D２をオペランドとしてとる。D2の値とB2の値の合計値をメモリアドレスとし、そのメモリアドレス上のメモリの値がレジスタR1の値と等しくなるまで、後続の命令の実行を遅延させる。
【００３５】
次に、図３を参照して、本発明の実施例に係る、メモリ同期（CAD）命令の実行ユニットに対するハードウェア的な変更について説明する。
【００３６】
まず、変更を加える元となる構成は、アドレス・レジスタ３０２と、比較器（コンパレータ）３０４と、連想メモリ(CAM: content addressable memory)３０６を有する。連想メモリ３０６は、トランザクション衝突を検出するために、トランザクション・フットプリント(トランザクションにおいてアクセスされるキャッシュ・ライン)を追跡する。
【００３７】
連想メモリ３０６は、他のスレッド及びコアから、外部ストア・アドレスと外部ロード・アドレスを受け取る。そして、トランザクション間のデータ・アクセスの衝突(書き込みの後の読み取り、書き込みの後の書き込み、あるいは読み取りの後の読み取りの衝突)を検出したら、そのイベントを通知する。
【００３８】
アドレス・レジスタ３０２は、CADからのメモリ・アドレスを格納する。比較器３０４は、他のスレッド及びコアからの外部ストア・アドレスと、アドレス・レジスタ３０２の内容を比較して、それが一致するとき、スレッド起き上がり(wake-up)イベントを通知する。
【００３９】
ここまでは従来の構成であるが、本発明のこの実施例によれば、以下の論理回路が追加される。
(1) 本メモリ同期命令の属性を追跡するための、追加のオペランドからの優先順位上昇ビット(pu)３０８。
(2) スレッド起き上がりイベントが発生し、puビットが1であるとき、優先順位上昇イベントを発生するための制御論理回路(and)３１０。
(3) 非トランザクション・フラグが1、すなわち、命令が非トランザクションであるとき、連想メモリ３０６がロード/ストア・アドレスをストアするのを防ぐ制御論理回路(sel)３１２。本メモリ同期命令は非トランザクション命令であり、本フラグが１となる。
これらの追加の構成は、図３では、太線で囲んで示されている。
【００４０】
上記の構成において、同期化のために非トランザクション命令であるCADを使用して、トランザクションの順序どおりの完了を維持するランタイムの、System/zのアセンブラで記述した例を、以下に示す。このコードで、CADは、本発明に従い変更された機能をもつCADであることを理解されたい。
typedef struct _tran_t {
int cont;  int pad1[sizeof(cacheline)/sizeof(int)-1];} tran_t;
tran_t TRAN[NUM_THREADS];   // スレッド毎に1つのキャッシュ
TRAN_N:  TBEGIN             // TBEGINは、当該スレッドの優先順位を下げる
JNZ  TABORT_N 
LA   R2,TRAN[N]    // R2 = &(TRAN[N].cont); 同期化ワードのアドレスをロードする
LHI  R1,1            
CAD  R1,PU,(R2)    // TRAN[N].cont!=1なので、スレッドは停止しない
// TRAN[N].contが0 (N>0)で初期化される.
// このことは、当該キャッシュ・ラインに、PU (優先順位上昇) 属性を追加する
<main body>        // Nth番目の投機スレッドのボディ
LHI  R1,0
CAD  R1,PU,(R2) // if TRAN[N].cont==0なら停止; (非トランザクション・キャップ)
NTLG R4,0(R2)      // R4 = TRAN[N].cont; (非トランザクション・ロード)
LHI  R1,1
CR   R4,R1
JNZ  ABORT_N       // TRAN[N].cont!=1ならば、アボート; (例えば、タイムアウト)
TEND
LHI  R1,1          // TRAN_(N+1) が続くべきと想定する
ST   R1,256+(R2)   // TRAN[N+1].cont=1;  TRAN_(N+1)の優先順位を上昇させる
...
ABORT_N:
TABORT_N:...                // 次の試行を遅延させる、オプションの論理
J   TRAN_N         // 当該トランザクションを再試行
【００４１】
このコードで、最初のCADは、同期化ワードを指し示す、メモリ・オペランド(R2)によって指定されるキャッシュ・ラインに単に、優先順位上昇属性を付加する。
【００４２】
当該スレッドが、このトランザクションのメイン・ボディの実行を終了した後、当該スレッドは再びCAD命令を実行する。当該スレッドは、別のスレッドが先行トランザクションの実行を既に完了しているなら、実行を継続する。そうでないなら、当該スレッドは、別のスレッドが先行トランザクションの実行を完了するまで、実行を停止する。次に、当該スレッドは、先行トランザクションの完了を確認するために、非トランザクション・ロード(NTLG)を使用することによって、同期化ワードの値をロードする。
【００４３】
ここで、非トランザクション命令(CAD及びNTLG)を、一つのトランザクション内で使用することが本質的である。通常の(トランザクション)命令は、書き込みの後の読み取りの衝突を引き起こし、トランザクションのアボートとなる。
【００４４】
図４は、このような処理を図式的に示す図である。すなわち、この図は、順次的コード(a)を、投機的並列実行コード(b)として、実行する図である。
【００４５】
投機的並列実行コード(b)において、「待機」処理は、「通知」処理がトランザクション衝突を起こすのを防ぐために、非トランザクション命令を使用して、先行スレッドから通知を待つ。
【００４６】
「優先順位上昇」は、先行スレッドからの通知によりスレッド優先度を上昇させることを示す。
【００４７】
tbegin命令とtend命令はそれぞれ、トランザクション開始と、トランザクション終了を示す。
【００４８】
以上、本発明を、System/zにおけるCAD命令を用いた特定の例により説明してきたが、この発明は、特定のＣＰＵアーキテクチャに限定されず、スレッド間同期あるいはメモリ同期に使用される任意の命令に適用されることを理解されたい。すなわち、本発明に従い機能を変更するようにハードウェアを変更する対象となる命令はCADに限定されず、BUSYWAITなど、その他のメモリ同期命令も含まれる。
【符号の説明】
【００４９】
１０４  ・・・ＣＰＵ
３０２  ・・・アドレス・レジスタ
３０４  ・・・比較器
３０６  ・・・連想メモリ
３０８  ・・・優先順位上昇ビット
【図１】
2014085839.tif 000003
【図２】
2014085839.tif 000004
【図３】
2014085839.tif 000005
【図４】
2014085839.tif 000006