(57)【要約】【課題】  トランザクショナル・メモリに対する最適化されたサポートを有するコンピューティング・システムを提供する。【解決手段】  第１のスレッドのトランザクション・データのための、第１のスレッド及び第２のスレッドによりアクセス可能な共有メモリ位置へのメモリ・アクセスを管理するための、トランザクション・プログラムにより用いられるコンピュータ実施の方法を提供する。第１のスレッドのトランザクションを完了するための一連の命令を、この一連の命令のうちの１つの命令から開始して実行する。この１つの命令が、第１のスレッドのトランザクションと関連したアクティブなアトミック命令グループ（ＡＩＧ）の一部であるかどうかを判断する。１つの命令がアクティブＡＩＧの一部である場合、ＡＩＧのアクティブ・モードにおけるエントリを協働して提供するキャッシュ構造体及びトランザクション・テーブルを見つけ出す。１つの命令がアクティブＡＩＧの一部ではないとの判断に応答して、次の命令が通常の実行モードの下で実行される。【選択図】      図３
2013503379.tif 000002
【特許請求の範囲】
【請求項１】
第１のスレッドのトランザクション・データのための、前記第１のスレッド及び第２のスレッドによりアクセス可能な共有メモリ位置へのメモリ・アクセスを管理するための、トランザクション・プログラムにより用いられる方法であって、前記方法は、
コンピューティング・システムにおいて、前記第１のスレッドのトランザクションを完了するための一連の命令を、前記一連の命令のうちの１つの命令から開始して実行するステップと、
前記コンピューティング・システムにおいて、前記１つの命令が、前記第１のスレッドの前記トランザクションと関連した命令のアクティブ・アトミック命令グループ（ＡＩＧ）の一部であるかどうかを判断するステップと、
前記１つの命令がアクティブＡＩＧの一部であるとの判断に応答して、前記ＡＩＧのアクティブ・モードにおけるエントリを協働して提供するキャッシュ構造体及びトランザクション・テーブルを見つけ出すステップであって、前記エントリは、前記キャッシュ構造体内にストアされた旧データ状態と、前記トランザクション・テーブル内にストアされた制御情報とを含み、前記アクティブＡＩＧの命令によって検査及び修正される全てのストレージ位置は、前記コンピューティング・システムが前記ストレージ位置をコミットすべきであることを示すまで保留のままにされる、前記ステップと、
前記１つの命令がアクティブＡＩＧの一部ではないとの判断に応答して、前記コンピューティング・システムにおいて、次の命令を通常の実行モードの下で実行するステップと、
を含む方法。
【請求項２】
前記旧データ状態をストアする要求を受け取るステップと、
前記旧データ状態を前記キャッシュ構造体内にストアするか又は前記トランザクション・テーブル内にストアするかを判断するステップと、
前記旧データ状態を前記キャッシュ構造体内にストアすべきであるとの判断に応答して、前記旧データ状態を前記キャッシュ構造体内にストアするステップと、
前記旧データ状態を前記トランザクション・テーブル内にストアすべきであるとの判断に応答して、前記旧データ状態を前記トランザクション・テーブル内にストアするステップと、
をさらに含む、請求項１に記載の方法。
【請求項３】
前記制御情報をストアする要求を受け取るステップと、
前記制御情報を前記トランザクション・テーブル内にストアするステップと、
をさらに含む、請求項２に記載の方法。
【請求項４】
前記制御情報は、物理アドレス及びプライベート・ツー・トランザクション（ＰＴＲＡＮ）タグを含む、請求項１に記載の方法。
【請求項５】
前記トランザクション・テーブルは、主ストレージ内に配置される、請求項１に記載の方法。
【請求項６】
前記キャッシュ構造体は、キャッシュ・ストレージ内に配置される、請求項１に記載の方法。
【請求項７】
前記方法の請求項のいずれかに記載の前記方法の全てのステップを実行するように適合された手段を含むシステム。
【請求項８】
コンピュータ・プログラムであって、前記コンピュータ・プログラムがコンピュータ・システム上で実行されるとき、前記方法の請求項のいずれかによる前記方法の全てのステップを実行するための命令を含む、コンピュータ・プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、一般に、コンピューティング環境内での処理に関し、より特定的には、トランザクショナル・メモリ（transactional memory）に対する最適化されたサポートを有するコンピューティング・システムに関する。
【背景技術】
【０００２】
現在のマルチプロセッサ及びマルチスレッド・コンピューティング・システムは、単一ソフトウェア・アプリケーションの性能を、単一スレッド・アプリケーションの可能な性能の何倍にもスケーリングすることを可能にする。現在のソフトウェア及びハードウェア・システムは、複数の実行スレッドの並列処理を提供する。ソフトウェア・アプリケーションは、ＰＯＳＩＸ（登録商標）ｐｔｈｒｅａｄライブラリのような既存のスレッド・ライブラリを用いて、複数の並列実行スレッドの作成を制御することができる。複数スレッドの使用は、容易に分割されるタスク及びデータの処理を行うアプリケーションには良好に機能し、粗粒度ロック（coarse grain lock）を用いて、幾つかの共有データ構造体へのアクセスを制御し、複数スレッドのデータ更新の間にまれに発生する競合を防ぐことができる。
【０００３】
多くのソフトウェア・アプリケーションは、複数スレッド間で共有する必要があるデータ構造体を含み、共有データ構造体の頻繁な同時検査及び更新を行う。多数のスレッドを用いるとき、これらのアプリケーションは、良好なスケーリングを得るために付加的な修正を必要とする。共有データ構造体に同時にアクセスする複数の実行スレッドを用いるアプリケーションは、デッドロック及び破損したデータが存在しない確実な結果をもたらすために、専用データ・ロッキング・ルーチンの使用を必要とする。このカテゴリーに入る既存のマルチスレッド・アプリケーションの大部分は、細粒度（fine-grained）ソフトウェア・ロックを用いて、良好な性能及び正確な動作を達成する。細粒度ソフトウェア・ロックを用いる高性能のマルチスレッド・プログラムを書くことは極めて難しく、熟練したプログラミング技能を必要とする。ソフトウェア産業におけるこれらの技能の不足により、共有データ構造体の使用を必要とするマルチスレッド・アプリケーションの生成、従って、多くの形態のトランザクション処理を含む特定のアプリケーション・クラスのためのマルチスレッド及びマルチプロセッサ・コンピューティング・システムの有用性が制限されることがある。
【０００４】
共有データ構造体へのアクセスを制御する必要があるマルチスレッド・アプリケーションを構成するためのより簡単なプログラミング・モデルを提供するように、種々の「トランザクショナル・メモリ」システムが提案され、構築されている。これらのシステムは、１つの実行スレッド上で実行されているソフトウェアが、他の実行スレッドのアクセス及び更新と競合することなく共有データ構造体を更新することができると楽観的に想定することを可能にする。トランザクショナル・メモリ・システムが、他のスレッドのストレージ・アクセスとの競合が生じなかったことを確認するまで、メモリに対する投機的（speculative）更新が「保留」のままにされる。トランザクショナル・メモリ・システムは、複数スレッドのストアされたアクセス間の競合が検出されたときに、保留中の投機的更新を破棄できなければならない。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】米国特許第７，５３６，５１７号明細書
【特許文献２】米国特許第７，３５０，０３４号明細書
【非特許文献】
【０００６】
【非特許文献１】DavidA. Wood著、「An Overview of Hardware Alternatives」、Transactional Memory Workshop、２００５年４月８日
【非特許文献２】Chang及びMergan著、801 Storage:Architecture andProgramming
【非特許文献３】Ananian他著、「Unbounded Transactional Memory」、ResearchAbstracts ２００６年、CSAIL Publications and Digital Archive
【非特許文献４】Rajwar, Herlihy及びLai著、「Virtualizing Transactional Memory」、２００５年  IEEE
【非特許文献５】McDonald他、「Architectural Semantics for Practical Transactional Memory」、Computer System Laboratory、StanfordUniversity、２００６年
【発明の概要】
【発明が解決しようとする課題】
【０００７】
トランザクショナル・メモリに対する最適化されたサポートを有するコンピューティング・システムを提供する。
【課題を解決するための手段】
【０００８】
例示的な実施形態は、第１のスレッドのトランザクション・データのための、第１のスレッド及び第２のスレッドによりアクセス可能な共有メモリ位置へのメモリ・アクセスを管理するための、トランザクション・プログラムにより用いられるコンピュータ実施の方法である。この方法は、コンピューティング・システムにおいて、第１のスレッドのトランザクションを完了するための一連の命令を、該一連の命令のうちの１つの命令から開始して実行するステップを含む。コンピューティング・システムにおいて、その１つの命令が、第１のスレッドのトランザクションと関連した命令のアクティブ・アトミック命令グループ（ＡＩＧ）の一部であるかどうかを判断する。ＡＩＧのアクティブ・モードにおけるエントリを協働して提供するキャッシュ構造体及びトランザクション・テーブルを見つけ出す。この見つけ出すステップは、１つの命令がアクティブＡＩＧの一部であるとの判断に応答したものである。エントリは、キャッシュ構造体内にストアされた旧データ状態と、トランザクション・テーブル内にストアされた制御情報とを含む。アクティブＡＩＧの命令によって検査又は修正される全てのストレージ位置は、コンピューティング・システムがそのストレージ位置をコミットすべきであることを示すまで保留のままにされる。１つの命令がアクティブＡＩＧの一部ではないとの判断に応答して、コンピューティング・システムにおいて、次の命令を通常の実行モードの下で実行する。
【０００９】
別の例示的な実施形態は、第１のスレッドのトランザクション・データのための、第１のスレッド及び第２のスレッドによりアクセス可能な共有メモリ位置へのメモリ・アクセスを管理するための、トランザクション・プログラムにより用いられるコンピュータ・プログラム製品である。このコンピュータ・プログラム製品は、方法を実行するために、処理回路により可読であり、かつ、処理回路による実行のための命令をストアする、有形ストレージ媒体を含む。この方法は、第１のスレッドのトランザクションを完了するための一連の命令を、該一連の命令のうちの１つの命令から開始して実行するステップを含む。１つの命令が、第１のスレッドのトランザクションと関連した命令のアクティブＡＩＧの一部であるかどうかを判断する。ＡＩＧのアクティブ・モードにおけるエントリを協働して提供するキャッシュ構造体及びトランザクション・テーブルを見つけ出す。この見つけ出すステップは、１つの命令がアクティブＡＩＧの一部であるとの判断に応答したものである。エントリは、キャッシュ構造体内にストアされた旧データ状態と、トランザクション・テーブル内にストアされた制御情報とを含む。アクティブＡＩＧの命令によって検査又は修正される全てのストレージ位置は、コンピューティング・システムがそのストレージ位置をコミットするべきであることを示すまで保留のままにされる。１つの命令がアクティブＡＩＧの一部ではないとの判断に応答して、次の命令を通常の実行モードの下で実行する。
【００１０】
さらに別の例示的な実施形態は、コンピューティング・システム内において、第１のスレッドのトランザクション・データのための、第１のスレッド及び第２のスレッドによりアクセス可能な共有メモリ位置へのメモリ・アクセスを管理するための、トランザクション・プログラムにより用いられるシステムである。このシステムは、コンピュータ・メモリと、コンピュータ・メモリと通信状態にあるプロセッサとを含む。このプロセッサは、メモリから命令をフェッチするための命令フェッチ要素と、フェッチされた命令を実行するための１つ又は複数の実行要素とを含む。このコンピューティング・システムは、方法を実行することができる。この方法は、第１のスレッドのトランザクションを完了するための一連の命令を、該一連の命令のうちの１つの命令から開始して実行するステップを含む。１つの命令が、第１のスレッドのトランザクションと関連した命令のアクティブＡＩＧの一部であるかどうかを判断する。ＡＩＧのアクティブ・モードにおけるエントリを協働して提供するキャッシュ構造体及びトランザクション・テーブルを見つけ出す。この見つけ出すステップは、１つの命令がアクティブＡＩＧの一部であるとの判断に応答したものである。エントリは、キャッシュ構造体内にストアされた旧データ状態と、トランザクション・テーブル内にストアされた制御情報とを含む。アクティブＡＩＧの命令によって検査又は修正される全てのストレージ位置は、コンピューティング・システムがそのストレージ位置をコミットすべきであることを示すまで保留のままにされる。１つの命令がアクティブＡＩＧの一部ではないとの判断に応答して、次の命令を通常の実行モードの下で実行する。
【００１１】
本発明の技術を通して、さらなる特徴及び利点が実現される。本発明の他の実施形態及び態様は、本明細書で詳細に説明され、特許請求の範囲に記載された発明の一部とみなされる。本発明を利点及び特徴と共により良く理解するために、詳細な説明及び図面を参照されたい。
【００１２】
ここで、幾つかの図面において同様の要素に同様の番号が付けられている図面を参照する。
【図面の簡単な説明】
【００１３】
【図１】本発明の例示的な実施形態によって実装することができる、最適化されたトランザクショナル・メモリを有するコンピューティング・システムを示す。
【図２】例示的な実施形態によって実装することができる、実システム・メモリのトランザクション・テーブルを示す。
【図３】例示的な実施形態によって実装することができるロード処理のフローを示す。
【図４】例示的な実施形態によって実装することができるストア処理のフローを示す。
【図５】例示的な実施形態によって実装することができるコミット処理のフローを示す。
【図６】例示的な実施形態によって実装することができるロールバック処理のフローを示す。
【図７】例示的な実施形態によって実装することができる、特別な命令、及びネスト化ＡＩＧ内で用いられる命令のアトミック命令グループ（ＡＩＧ）を示す。
【図８】例示的な実施形態における命令の復号及び実行のフローを示す一般化されたフローチャートを示す。
【図９】例示的な実施形態によって実装することができる、旧データ状態のストア・フローを示す。
【図１０】例示的な実施形態によって実装することができるコンピュータ・プログラム製品を示す。
【発明を実施するための形態】
【００１４】
本発明の１つの例示的な実施形態は、データ・キャッシュ構造体（例えば、ハードウェア・バッファ）をログ・ベースの構造体（例えば、ソフトウェア・テーブル）と組み合せて投機的トランザクション・データを保持する、トランザクショナル・メモリ・システムに向けられる。例示的な実施形態は、「旧データ状態」がキャッシュ内にストアされるようにし、「旧データ状態」をログ・ベースの構造体に移す必要性をなくす。しかしながら、データ・キャッシュ構造体が旧データ状態をストアすることができない（例えば、データ・キャッシュ構造体が一杯になった）場合、例示的な実施形態は、旧データ状態をログ・ベースの構造体内にストアする。
【００１５】
例示的な実施形態は、実システム・メモリの各増分に取り付けられた「プライベート・ツー・トランザクション（private-to-transaction）」（ＰＴＲＡＮ）タグと、投機的ロード及びストアのログと、投機的ロード及びストアと関連した旧データ状態をストアするデータ・キャッシュ構造体との組み合わせを用いて、トランザクショナル・メモリ・システムの改善された実装をもたらすコンピューティング・システムを提供する。例示的な実施形態は、ＰＴＲＡＮタグとして用いられ、実システム・メモリのあらゆる増分と関連付けられる付加的なマークビットを有するログを用いる。複数の実行スレッド上で実行されているトランザクションのストレージ・アクセス間の競合を迅速に検出するために、ハードウェアが提供される。本発明の例示的な実施形態内に含まれる、メモリ内のタグ及び関連した競合検出ハードウェアの使用により、既存のシステムに比べてオーバーヘッドが遥かに小さく、遥かに速いトランザクショナル・メモリ・システムが提供される。例示的な実施形態の複雑さは、特に多数のプロセッサ及び関連した相互接続部を有するシステムについての競合検出のために付加的なキャッシュ・コヒーレンシ状態を用いる従来の試みよりも低減される。
【００１６】
本発明の例示的な実施形態は、コンピューティング・システムのキャッシュと主メモリ・アレイの組み合わせを用いて、投機的データ（旧データ状態及び制御情報の両方を含む）を保持し、非常に長いトランザクションをサポートすることができる。例示的な実施形態は、キャッシュを用いて旧データ状態をストアし、主メモリ・アレイ（本明細書では主ストレージ又は主メモリとも呼ばれる）を用いて、トランザクション、並びに投機的ロード及びストアと関連したアドレス情報（例えば、制御情報）をストアする。さらに、主メモリ・アレイは、旧データ状態のために予約されたキャッシュの部分（例えば、バッファ）に収まらない、あらゆるオーバーフローの旧データ状態をストアするために用いられる。本明細書で用いられる「旧データ状態（old data state）」という用語は、トランザクション内部のストア命令のターゲットである、ストレージ位置にあるオリジナルの非投機的データを指す。例示的な実施形態は、一般的な場合の長い検索プロセスなしに、新しいメモリ・アクセスのアドレスをチェックする能力を提供する。同様に、競合の検出及びメモリ内のタグの使用により、トランザクションの投機的状態の追跡と関連したソフトウェア・オーバーヘッドの一部が排除されるので、これは、ソフトウェアだけのトランザクショナル・メモリ・システムに優る改善である。これはまた、数百又は数千バイトに成り得るソフトウェア・オブジェクト全体に対する更新を追跡する従来技術のソフトウェア・システムとは対照的に、非常に微細なレベル（単一バイトに至る）でストレージの競合を検出する能力も提供する。既存のソフトウェア・システムは、潜在的なデータ競合の頻繁な過度の表示を与えるか、又は、ソフトウェア・オブジェクトの個々のコンポーネントに対する更新を追跡しようとする場合に非常に長いソフトウェア経路長の不利益を被る。主メモリとの間で読み書きを行うために必要な帯域幅をなくすことの更に別の利点は、旧データ状態をストアするためのキャッシュ位置を提供することによって達成される。
【００１７】
トランザクショナル・メモリ・システムが、トランザクションによってアクセスされたメモリ位置と関連したソフトウェア・エンリストメント記録の使用を教示する特許文献１に示されるように提案されている。特許文献１に記載されるシステムはまた、「エンリストメント記録」内の「バージョン値」も使用する。特許文献１の図３は、「メモリ位置の登録（enlistment）記録を見つけ出す」動作を含む。図３を説明する文章は、参照されるメモリ・アドレスにおけるソフトウェア・オブジェクトの一部であり、且つ、「ソフトウェア・トランザクショナル・メモリ・インタフェース」を用いて作成された登録記録の例を与える。特許文献１は、各々の登録記録と関連したバージョン番号を使用し、バージョン番号が、登録記録によってサポートされる最大番号を超えた場合に対処する必要がある。結果論になるが、本発明の例示的な実施形態の詳細を学習した後では、トランザクショナル・メモリ・システムにおけるこれらの最近の発展の特徴は不要であり、改良され得ることが認識されるであろう。
【００１８】
非特許文献１においてＤａｖｉｄ  Ａ．Ｗｏｏｄにより要約された急速なコンピューティング・システムの発展において指摘されるように、以前に、今ではずっと以前に、仮想メモリの各セグメントと関連したロック・ビットの使用を提案したのは、ＩＢＭのＣｈａｎｇ及びＭｅｒｇｅｎであった（非特許文献２に記載されている）。彼らのシステムは、複数スレッドによるメモリ位置の同時アクセスを検出するための能力をもたらすが、トランザクション・ロッキング機構がアクティブになるときに、いずれかの単一の仮想メモリ・セグメント上で動作することができる並行スレッドの総数を制限するものであった。並行スレッドを実行するのにＣｈａｎｇとＭｅｒｇｅｎが必要とした大きな仮想メモリ・ページ・テーブルは、トランザクションを実行するスレッドだけではなく、仮想メモリを使用する全ての実行スレッドに性能上の不利益を負わせるので、ＣｈａｎｇとＭｅｒｇｅｎの提案は、従来技術における逸話となり、Ｗｏｏｄｓが言ったように「彼らが習得したものに誰も注目しないように見える」。本発明の例示的な実施形態では、データ・キャッシュ構造体と組み合わせて、システムの仮想メモリ・ページ・テーブルとは異なる「トランザクション・テーブル」を使用し、投機的ロード及びストアと関連した情報をストアする。
【００１９】
Ｗｏｏｄｓは知らなかったが、Ｃｈａｎｇ及びＭｅｒｇｅｎのＩＢＭのヨークタウンの施設においては、２００５年６月２０日出願の「Architecture Support of Best-Effort Atomic Transactions forMultiprocessor Systems」と題する特許文献２に記載されているメモリ・システムを含む、トランザクショナル・メモリ・システムに関する研究室での開発が進行中であった。
【００２０】
特許文献２は、「キャッシュを、アトミック・トランザクションによってアクセスされるデータのためのバッファとして」用いることに焦点を合わせたトランザクショナル・メモリ・システムについて記載する。特許文献２は、システムが「バッファ・オーバーフロー（cache overflow）」を検出したときに、トランザクションの失敗を強いることを教示し、投機的データがキャッシュから排除された場合の処理を提案していない。バッファ・オーバーフローは、あまりにも多くのトランザクション・ロード又はストアが同じキャッシュ合同クラス（congruence class）をターゲットにする場合に生じる。キャッシュをオーバーフローさせて失敗するトランザクションの割合は、トランザクション内に含まれるロード及びストアの数に比例する。長いトランザクションは、より頻繁に失敗する。
【００２１】
競合検出スキームを実装し、キャッシュをオーバーフローさせる投機的データを捕捉するためにキャッシュを用いる他のシステムが提案されている。本発明の例示的な実施形態は、競合検出のために、主としてデータ・キャッシュ状態には依存しない。必要とされる特化したキャッシュ状態は、複雑さの望ましくない増大をもたらし、必要とされる検出及び分離機構を既存のマルチプロセッサ・キャッシュのコヒーレンス設計に付加することを困難にする。それにも関わらず、特許文献２に記載される手法に加えて、試行された、キャッシュを利用する多くの試みがある。１つの手法は、「ビフォー・イメージ・ログ」及びキャッシュ・コヒーレンス状態を用いて、競合検出スキームを実装することである。別の手法は、単一の「分類されていない線形アレイ・データ構造体」を用いて、データ・キャッシュをオーバーフローさせる投機的データを捕捉する、トランザクショナル・メモリ・システムについて説明する、非特許文献３にＡｎａｎｉａｎ他により記載される。Ａｎａｎｉａｎ他は、キャッシュ・セット毎に余分なビット、すなわち「Ｏ」ビットを用いて、そのセットが「オーバーフローした」かどうかを示し、キャッシュ・エントリ毎に別のビット、すなわち「Ｔ」ビットを用いて、そのエントリが投機的データを保持することを示す。線形アレイ・データ構造体は、より長いトランザクションをサポートするための能力をもたらすが、本発明の例示的な実施形態の高速検出能力はもたらさない。Ａｎａｎｉａｎにおける線形アレイは、「オーバーフローした」セットをターゲットにするあらゆるキャッシュ・アクセスを検索する必要がある。これは、多くのオーバーフローを引き起こすトランザクションとっては長いプロセスになり得る。Ｒａｊｗａｒ、Ｈｅｒｌｉｈｙ及びＬａｉは、非特許文献４において、Ａｎａｎｉａｎと類似した手法をとる。Ｒａｊｗａｒ他はまた、データ・キャッシュを、トランザクションと関連した投機的状態を追跡するための主機構として用いる。キャッシュの外に押し出された投機的データは、仮想メモリ内のトランザクション・アドレス・データ・テーブル（ＸＡＤＴ）のオーバーフロー領域に移される。ＸＡＤＴの一部であるアドレスとの起こり得る競合の検出には、ＸＡＤＴの遅い線形検索が必要とされる。Ｒａｊｗａｒは、これらの検索の一部をなくすためのフィルタの使用を説明するが、依然として検索を行う必要がある場合が少なくない。
【００２２】
当分野における上で要約された発展に加えて、トランザクショナル・メモリをサポートするために、多くのソフトウェア・インタフェース及び命令セットの修正が提案されている。非特許文献５は、提案の幾つかを比較し、多くの他の提案のための参考文献を提供し、その全体が引用により本明細書に組み入れられる。
【００２３】
トランザクショナル・メモリをサポートするために、多くのソフトウェア・インタフェース及び命令セットの修正が提案されている。本発明の例示的な実施形態を、それらのいずれかと組み合わせて使用し、ハードウェア又はソフトウェアの複雑さの大きな増大を招くことなく、高性能のトランザクショナル・メモリ操作をもたらすことができる。例示的な実施形態が、ＩＢＭ  ＰｏｗｅｒＰＣ（登録商標）アーキテクチャに関して説明されるが、当業者であれば、同じ手法を、例えば、ＩＢＭのｚＳｅｒｉｅｓ（登録商標）、Ｐ３、Ｐ４、Ｐ５プロセッサを有するＩＢＭのｐＳｅｒｉｅｓ（登録商標）、及びＩＢＭのＳｙｓｔｅｍ３８のような他のいずれかのアーキテクチャに適用することもでき、そのＡＳ／４００（登録商標）は、本発明の例示的な実施形態のサポートの他に、Ｓｕｎ  Ｍｉｃｒｏｓｙｓｔｅｍｓ社のＳＰＡＲＣ（登録商標）及びＩｎｔｅｌ（登録商標）ＩＡ−３２のような他のコンピューティング・システムも利用することができる。当業者であれば、トランザクショナル・メモリの実装の他の特化したバージョンに対して作成することができる他のアプリケーション・プログラミング・インタフェース（ＡＰＩ）と共に用いるように、例示的な実施形態を拡張することができる。
【００２４】
本発明の例示的な実施形態は、アクティブなトランザクションの現在の部分であるのものだけではなく、全てのメモリ位置と関連したハードウェア・ビットを用いる。例示的な実施形態は、付加的なハードウェア・ビットを用いて、特許文献１に記載されているプロセスを用いて得ることができるものより遥かに速いトランザクションの実行をもたらす。例示的な実施形態は、データ・キャッシュ構造体を使用して、改善されたトランザクション・テーブルと併せて旧データ状態をログとして保持し、メモリ使用量を最適化し、且つ、特許文献１に記載されるような他のシステムが使用するよりも使用するメモリが少ないシステムを提供し、さらに、これらの他のシステムのために開発されたアプリケーションを実行することができる。例示的な実施形態は、ストレージ増分ごとに１つ又は複数のＰＴＲＡＮビットを与える。現在の実施形態においては、ＰＴＲＡＮビットを「見つけ出す」間接的な方法の必要性はない。ＰＴＲＡＮビットは、マーク付けされるメモリ位置の直接アドレス指定可能な部分であるので、例示的な実施形態は、潜在的な競合を遥かに速く示す。例示的な実施形態は、特許文献１に記載されたようなインタフェースを必要とせず、ＰＴＲＡＮビットを更新及びリセットするのにハードウェア及びファームウェアを用いて、その利益を達成する。例示的な実施形態は、アプリケーション・ソフトウェアがＰＴＲＡＮビットの状態を認識することを必要としないが、必要に応じて、直接インタフェースを提供することができる。例示的な実施形態は、短いコミット処理時間のために最適化することもできる。例示的な実施形態は、各ストレージ位置についてのバージョン番号の使用を必要としない。
【００２５】
例示的な実施形態の利点は、システムの仮想メモリ・ページ・テーブルとは異なる「トランザクション・テーブル」を使用することである。これは、非常に大きいトランザクションを処理するのを可能にし、単一バイトに至るまでの競合検出をもたらす。例示的な実施形態では、同じ仮想メモリ部分内のメモリ位置に同時にアクセスできる並行スレッドの数の制限がない。例示的な実施形態は、物理メモリ・アドレス（又は実アドレス）に関する競合検出を行い、この競合検出の粒度での同時アクセスだけを制限する。この粒度は、例示的な実施形態の種々の実装によって変えることができるが、典型的には、バイトのオーダーである。Ｃｈｅｎｇ及びＭｅｒｇｅｎのシステムが多数の並行スレッドを使用しようとする場合、そのシステムは、極めて大きな仮想ページ・テーブル・フォーマットを使用せずに同様の利益をもたらすことができず、従って性能上の不利益を招く。本発明の例示的な実施形態は、この性能上の不利益を課すものではない。例示的な実施形態の別の利点は、投機的ロード及びストアと関連した旧データ状態が、キャッシュ内に位置するデータ・キャッシュ構造体内にストアされ、従って、旧データ状態をトランザクション・テーブルに移すのに必要とされるいずれの帯域幅及びクロック・サイクルも節約されることである。データ・キャッシュ構造体が一杯になった場合、旧データ状態は、データ・キャッシュ構造体に対するバックアップとしてトランザクション・テーブル内にストアされる。
【００２６】
ここで図をより詳細に参照すると、図１には、相互接続要素（１１０）を介して物理メモリ・アレイ（１２０）に結合された１つ又は複数のマイクロプロセッサ（１００、１０１、１０２）を有する、本発明の例示的な実施形態を示すコンピューティング・システムがあることが分かるであろう。マイクロプロセッサ（１００、１０１、１０２）は、キャッシュ１０４（本明細書では「キャッシュ・ストレージ」とも呼ぶ）を含み、キャッシュ１０４は、トランザクションと関連した旧データ状態をストアするためのキャッシュ構造体１０６を含む。例示的な実施形態において、キャッシュ構造体１０６は、３２のキャッシュ・ラインを含むハードウェア・バッファである。他のキャッシュ構造体及びキャッシュ・ラインの数は、例示的な実施形態により実装することができ、アプリケーション及びシステム要件のような基準に基づいて選択することができる。物理メモリ・アレイは、トランザクション・データ（１２１）と、実システム・メモリの全ての増分と関連したＰＴＲＡＮタグ（１２２）とをストアする。相互接続要素（１１０）は、共用バス又はクロスバー・スイッチとして実装することができる。例示的な実施形態は、物理メモリを、１つ又は複数のチップ内に実装することができるマイクロプロセッサ・システムに相互接続する他のいずれかのスキームを用いるシステムにも適用される。ＰＯＷＥＲ４（登録商標）マイクロプロセッサを用いた幾つかのＩＢＭシステム又はＡｍｄａｈｌのＡＭＤ  Ｏｐｔｅｒｏｎ（登録商標）ベースのサーバのために行われているように、メモリは、より小さい部分に分割し、中央処理ユニット（ＣＰＵ）チップの各々へのプライベート接続にわたって分散させることができる。マイクロプロセッサ及びメモリ・コントローラは、単一のシリコン・チップ上に一緒に配置してもよく、又は複数のチップに散在してもよい。
【００２７】
コンピューティング・システムの物理メモリは、ｎ個の増分に分割される。ｎ個の増分の各々について、実システム・メモリの全ての増分と関連した１つ又は複数の（ＰＴＲＡＮ）ビットが与えられる。例示的な実施形態は、任意のメモリ増分サイズの選択を可能にし、最良の選択は、作業負荷特性、ハードウェアのコスト、及びターゲット・システムにおいて用いられるデータ・キャッシング構造体によって決まる。示される実施形態においては、１６バイトの増分が用いられる。ＰＴＲＡＮビットは、メモリ内のデータ・エントリが、システムにおいて現在アクティブであるコミットされていないトランザクションの投機的メモリ状態の一部であるかどうかを示すために用いられる。
【００２８】
図７のネスト化された（nested）ＡＩＧコード・シーケンスによって示されるような特殊な新規命令（ＢＥＧＩＮ＿ＡＩＧ，ＥＮＤ＿ＡＩＧ）が、命令グループの初めと終わりをマーク付けするために用いられる。特殊新規命令の間に実行される命令は、図７に示されるＡＩＧ命令（命令Ａ０、命令Ａ１、命令Ａ２）によって示される「アトミック命令グループ（atomic instruction group）」（ＡＩＧ）と呼ばれる。プロセッサがＡＩＧの一部である命令を実行しているとき、付加的なストレージ・アクセス規則が用いられる。ＡＩＧ命令グループによって修正されるストレージ位置の全ては、メモリ内でアトミックな方法で更新される。ストレージ位置に対する更新は、プロセッサ及び／又はソフトウェア・アプリケーションが、それらを「コミットする」べきであることを示すまで「保留」のままにされる。更新の全ては、「通常の」メモリに即座にコミットされるか、又は廃棄される。ハードウェア及び／又はソフトウェア・アプリケーションが、マルチプロセッサ・システム内で同時に実行されている複数のＡＩＧのストレージ・アクセス間の競合を検出すると、結果が廃棄される。例示的な実施形態は、ハードウェアが、複数のＡＩＧのストレージ・アクセス間の潜在的な競合を迅速に検出する方法を提供する。例示的な実施形態は、特殊新規命令を用いて、トランザクションの境界にマーク付けするが、他のいずれかの方法を用いて、アトミックな方法で更新されるメモリ位置のグループを識別することができる。例示的な実施形態は、トランザクショナル・メモリ・システムを実装するために用いることができる任意の数のソフトウェア・インタフェースと両立し得る。例示的な実施形態は、複数のストレージ位置のアトミック更新をもたらそうと試みているいずれのシステムに対しても、同じ迅速な競合検出を提供することができる。例示的な実施形態はまた、他の命令に付随するコンパイラ生成ヒント、内部マイクロコード又はミリコードによって生成される内部マイクロプロセッサ・コマンドを含む、他のいずれかの方法で命令グループの境界にマーク付けするシステムにも適用される。
【００２９】
ＰＴＲＡＮタグ（１２２）は、ＡＩＧの一部である命令によって生成される全てのメモリ・アクセスについて設定された、メモリ内の増分と関連した１つ又は複数のビットである。プロセッサは、ビットを設定しようと試みる前にビットを検査し、これは、他のスレッド上で同時に実行されている他のＡＩＧとの潜在的な競合を迅速に検出することを可能にする。ビットの設定は、ＩＢＭ  ｚ／アーキテクチャの「テスト・アンド・セット（test and set）」（ＴＳ）操作、又はマルチスレッド若しくはマルチプロセッサ・システムにおけるアトミック更新を可能にする他のいずれかの同等の操作によって達成することができる。
【００３０】
ここで図２を参照すると、トランザクション・テーブル（２３０、２３１）が、ここでは物理メモリ（１２０）として示される実システム・メモリ（２２０）（本明細書では「主ストレージ」とも呼ぶ）の一部分として作成されることが分かるであろう。トランザクション・テーブル（２３０、２３１）はまた、論理メモリ又は仮想メモリ内に作成することもできる。論理システム・メモリを物理システム・メモリにマッピングするためのいずれのシステムを用いることもでき、ＩＢＭ  ｚＳｅｒｉｅｓ、ＩＢＭ  ｐＳｅｒｉｅｓ、Ｓｕｎ  Ｍｉｃｒｏｓｙｓｔｅｍｓ社のＳＰＡＲＣ、Ｉｎｔｅｌ社のＩＡ−３２におけるもののような、使用することができる、当技術分野には周知の多数の例が存在する。トランザクション・テーブル・エントリは、ＡＩＧの一部である命令によりメモリ位置が検査又は更新されるときに作成される。スレッド識別子（２０３、２１３）が、各々のトランザクション・テーブル（２３０、２３１）と関連付けられる。次エントリ・レジスタ（２０２、２１２）が、トランザクション・テーブル（２３０、２３１）へのインデックスとして用いられ、どのエントリが次に書き込まれるべきかを示す。テーブル起点（２０１、２１１）は、そのスレッド（２０３、２１３）についてのトランザクション・テーブル（２３０、２３１）の第１のエントリのアドレスを示す。トランザクション・テーブル（２３０、２３１）は、検査又は更新されるメモリ位置と関連したＰＴＲＡＮタグ・ビットと関連付けられる単純情報を超える付加的な情報を保持するために用いられる。この付加的な情報は、ＡＩＧと関連した投機的状態に関するものである。ここで説明される図示したＩＢＭ  ｚＳｅｒｉｅｓ又はｐＳｅｒｉｅｓ  ＣＰＵ（１００、１０１、１０２）の実施形態においては、単一のＰＴＲＡＮビットが用いられる。この場合、トランザクション・テーブル（２３０、２３１）とキャッシュ構造体（１０６）の組み合わせは、投機的状態に関する全ての付加的な情報を含み（例えば、この組み合わせは、ＡＩＧのアクティブ・モードにおけるエントリを含む）、従って、ＰＴＲＡＮビットは、物理アドレスがＡＩＧ内に含まれることを示すにすぎない。これは、アドレス（２４０）、トランザクション情報識別子（２４１）及び旧データ又は新データ（２４２）として、トランザクション・テーブルＡ（２３０）において示される。ここで説明されるように、トランザクション・テーブルＡ（２３０）は、キャッシュ構造体（１０６）が旧データをストアできない場合に旧データを含むにすぎない。これは、キャッシュ構造体（１０６）が一杯になったときに起こり得る。このように、トランザクション・テーブルＡ（２３０）は、旧データ状態をストアするための、キャッシュ構造体（１０６）に対するバックアップとして用いられる。他の実施形態は、付加的なＰＴＲＡＮビットを用いることができ、この付加的なＰＴＲＡＮビットをハードウェア又はソフトウェアによって用いて、ＡＩＧの処理又は他のいずれかのトランザクショナル・メモリ・システムの投機的状態に関与する特定のイベントの処理を速めることができる。メモリ内の単一ビットのみを用いること、及び、そのビットを、キャッシュ��造体と組み合わせられたトランザクション・テーブル内のトランザクション状態のより完全な記述と関連付けることの組み合わせることにより、従来技術のソフトウェア・トランザクショナル・メモリ・システムに見られる性能上の不利益を負うことなく、オーバーヘッドほとんど必要としないトランザクショナル・メモリ・システムが提供される。
【００３１】
再び図２を参照すると、例えば、トランザクション・テーブルＡ（２３０）内のエントリは、ＡＩＧの内側の検査又は更新されたアドレス（２４０）、トランザクション情報フィールド（２４１）及びデータ・フィールド（２４２）を含むことが分かる。ＡＩＧの一部であるストア命令により、システムが、「旧」データ値、旧データ状態をオリジナルのストレージ位置から、そのアドレスに関するキャッシュ構造体（１０６）にコピーし、新しい投機的データが、主ストレージ位置（例えば、物理メモリ（１２０））内に置かれる。キャッシュ構造体（１０６）が旧データ状態をストアできない場合、旧データ状態は、トランザクション・テーブルのデータ・フィールド（２４２）内にストアされる。
【００３２】
例示的な実施形態は、必要に応じて、キャッシュ構造体（１０６）内に保持された新しい値を処理するようすることができる。キャッシュ構造体（１０６）内に旧データ値を置くことにより、大部分のトランザクションが成功した場合にシステムを最適化することが可能になる。旧データがもはや必要とされなくなったとき、トランザクションが恒久的にメモリにコミットされたとき、キャッシュ構造体（１０６）へのポインタを変えることによって又はキャッシュ構造体（１０６）のコンテンツを消去することによって、旧データを迅速に廃棄することができる。トランザクション・テーブル・エントリのトランザクション情報フィールド（２４１）は、トランザクション失敗をもたらす必要性に関する詳細な判断をなすのに必要とされるあらゆるトランザクション情報を含む。トランザクション情報フィールド（２４１）はまた、ネスト化トランザクション、仮想化トランザクション、又はトランザクショナル・メモリ・アーキテクチャの他の拡張の効率的なサポートを可能にするための付加的な情報を備える。例示的な実施形態において、トランザクション情報フィールド（２４１）は、関連したアドレス（２４０）のストレージ・アクセスが、ロード型アクセスであるか又はストア型アクセスであるかの表示を含む。トランザクション情報フィールド（２４１）はまた、そのアドレスがシステム内の複数のＡＩＧの間で共有されるかどうかを示すこともできる。
【００３３】
図３は、ＰＴＲＡＮビット及びトランザクション・テーブルを用いて、投機的状態を追跡するためのアクションについてのロード処理フローチャートを示す。プロセッサがロード型アクセスを試みるとき、初めに、そのロード・アクセス・アドレスがＡＩＧの一部であるかどうか、及び、ＡＩＧアクセスについての特別なストレージ・アクセス規則が適用されるかどうかを判断するために、決定（３１０）が行われる。ノーの場合には、通常の処理が適用され、続いて通常のロード処理（３２０）操作が行われる。ロード型アクセスがＡＩＧの一部であるかどうかは、決定プロセス・ステップ（３１０）において多くの異なる方法で判断することができる。プロセッサ・パイプライン内又はロード／ストア・ユニット内でモード・ビットを設定し、特殊ＡＩＧ動作モードがアクティブであることを示すことができる。モードは、プロセッサの物理的状態又は仮想プロセッサの論理的状態の一部とすることができる。特殊動作モードがアクティブでない場合、ロードは、通常のロード（３２０）として扱われる。
【００３４】
この「ＡＩＧアクティブ・モード」の「オーバーライド」をもたらすことができる。オーバーライドは、ターゲット・アドレスを含む論理メモリ・セグメント又は論理メモリ・ページと関連付けることができる。オーバーライドは、システムに、要求がＡＩＧの一部であるという事実にもかかわらず、ストレージ要求を通常のものとして処理するように強制する。オーバーライドがアクティブである場合、決定（３１０）の結果により、通常の処理（３２０）が行われる。ＡＩＧがアクティブであり、オーバーライドがアクティブでないと仮定すると、検査ステップ（３３０）において、関連したＰＴＲＡＮビットが検査される。ＡＩＧの内側のロード命令が、検査時にＰＴＲＡＮビットの状態を検出する。ＰＴＲＡＮビットが既に設定されている（３３０）場合、それは、同じプロセッサ又は別のプロセッサ上で実行されている別のスレッドのアクションによるものである可能性がある。検査ステップ（３３０）において、ＰＴＲＡＮビットが設定されていない（３４０）ことが分かった場合、プロセッサはＰＴＲＡＮビットを設定し、ＰＴＲＡＮ設定ブロック（３４０）においてトランザクション・テーブルに付加することによって、アクティブＡＩＧに関するトランザクション・テーブル（２３０）内にアクセスの記録を作製し、次いで、ロードの完了に進むことができる（３６０）。ＰＴＲＡＮビットが既に設定されている場合、この潜在的競合をもたらしたアドレスを、既にプロセッサのトランザクション・テーブルに入れられたアドレスと比較する。ＰＴＲＡＮビットが、同じＡＩＧの早期に別のロードによって、検査ブロック（３３０）においてテストされたときに設定された場合、これは既に、テストされ決定された（３５０）ＡＩＧの一部であり、次に、ロードの完了に進むことができる（３６０）。各々のトランザクション・テーブル（２３０、２３１）は、特定のＡＩＧについてのアドレス含む。同様に、例示的な実施形態において、各々のキャッシュ構造体（１０６）は、特定のＡＩＧについての旧データ状態を含む。例示的な実施形態において、各々のキャッシュ構造体（１０６）は、１つのトランザクション・テーブルに対応し、同じインデックスが、旧データ状態、及びＡＩＧ内の追跡される各命令と関連した制御情報をストアするために用いられる。従って、アドレスがまだ、テストされ決定されたときに（３５０）ＡＩＧの一部ではない場合、ロードに関するアドレスは、プロセッサのトランザクション・テーブル内に見出されず、次に、プロセッサは、ＡＩＧの共有（３７０）についての判断ステップ（３７０）において、そのアドレスがＡＩＧの間で共有可能かどうかをチェックする。そのアドレスが現在、複数のＡＩＧの間で共有できない場合、プロセッサはシステム内の他のプロセッサに信号を送って、共有がＡＩＧの間で可能であるかどうかの判断ステップ（３７０）中、このアドレスに対する「共有ＡＩＧアクセス」を要求することができる。共有アクセスは、システム内の他のＡＩＧがストレージ位置に投機的に書き込まれていない場合に許可され得る。共有アクセスが許可されない場合、ＡＩＧは失敗し（３８０）、他の場合には（３９０）、ロード・アドレスがトランザクション・テーブル（２３０）に付加され、トランザクション情報フィールド（２４１）が更新されて、そのアドレスが、システム内の複数のＡＩＧの間で共有されるロード・アクセスであることを示す。
【００３５】
図４は、ＡＩＧの一部であるストアを処理するためのアクションを示すストア処理のフローチャートである。プロセッサがストア型アクセスを試みるとき、初めに、そのアクセスがＡＩＧの一部であるかどうか、及び、ＡＩＧアクセスについての特別なストレージ・アクセス規則が適用されるかどうかを判断するために、ストア決定（４００）が行われる。プロセッサのモードが、ロード・アクセスに関して前述したのと同様の方法でチェックされる。ＡＩＧアクセスについての特別なアクセス規則が適用される特殊動作モードがアクティブではない場合、そのストアは通常のストアとして処理される（４４０）。ＡＩＧがアクティブであると仮定すると、ストア・プロセス検査ブロックにおいて関連したＰＴＲＡＮビットが検査される（４１０）。ＰＴＲＡＮビットがまだ設定されていない場合、ストア・トランザクション・ステップにおいてＰＴＲＡＮビットが設定され（４５０）、新しいエントリがトランザクション・テーブル（２３０）に付加される。「旧データ」はキャッシュ構造体（１０６）に移され、アドレスは新しいエントリ（２４０）に書き込まれ、トランザクション情報フィールド（２４１）は更新される。図９を参照して以下に説明されるように、キャッシュ構造体（１０６）が旧データ状態をストアすることができない場合、旧データ状態は、トランザクション・テーブルのデータ・フィールド（２４２）内にストアされる。トランザクション情報フィールド（２４１）は、このエントリと関連したアクセスがストア型アクセスであったことを示すようにマーク付けされる。ＰＴＲＡＮビットの設定が完了した後、新しいストア・データがメモリに書き込まれる。ＰＴＲＡＮビットの検査（４１０）が、ビットが既に設定されたことを示す場合、現在のストア・アドレスが、既に、プロセッサ上でアクティブであるＡＩＧの一部であるかどうかに基づいて、決定が行われる（４２０）。プロセッサについてのトランザクション・テーブル（２３０）が調査され、そのアドレスがトランザクション・テーブル内に存在すると判断される場合には、そのエントリのトランザクション情報フィールド（２４１）がチェックされ、共有アクセス・エントリに関する決定が行われる（４６０）。トランザクション情報フィールド（２４１）が、そのエントリが複数のＡＩＧの間で共有されるロード型アクセス・エントリであることを示す場合には、トランザクションは失敗し（４３０）、他の場合には、関連したエントリについてのトランザクション情報フィールド（２４１）はストア型アクセスを示すように更新され、ストアが処理される（４７０）。
【００３６】
ここで図５のコミット処理のフローチャートを参照すると、初めにテスト・ステップ（５００）において判断されるように、例示的な実施形態は、ＡＩＧ内の最後の命令が処理されたときに完了する１組のアクションを含み、グループ全体がメモリに恒久的に「コミットされる「準備が整った」ことが分かるであろう。そうでない場合には、処理はＡＩＧモードで継続する（５５０）。
【００３７】
図３及び図４からのフローチャートによる、ＡＩＧのロード及びストアの処理がトランザクションの失敗をもたらさないとき、ＡＩＧはメモリにコミットされる。ＡＩＧが成功した場合、テスト・ステップ（５００）は、ＡＩＧ内の最後の命令が処理され、グループ全体がメモリに恒久的に「コミットされる」準備が整ったと判断する。次に、トランザクション・テーブルが調査され（５１０、５２０）、コミットされるＡＩＧについての各エントリが読み出され、トランザクション・テーブル・コミット・ステップ（５３０）の判断において、その関連したＰＴＲＡＮビットが、メモリ内でリセットされる。
【００３８】
専用ハードウェア・エンジンを用いて、このコミット動作の遂行を完了することができる。プロセッサ・キャッシュ、マルチプロセッサ・コヒーレンス・アクション及び例示的な実施形態の組み合わせを用い、主メモリ・ストレージ・アレイが同時に更新されなかったとしても、単一のＡＩＧについてのメモリ更新の全てが同時に行われるという錯覚をソフトウェアに与えることができる。コミット処理中、ＰＴＲＡＮビットのリセットは、トランザクション・テーブル内の最後の有効エントリに達したと判断される（５３０）まで継続する。この時点で、ＡＩＧはコミットされると考えられ、従って、エンジンによる遂行が完了する（５４０）。
【００３９】
幾つかの条件により、ＡＩＧの完了を妨げられる。これらの条件を、ＡＩＧの実行中のロード処理の際（３８０）、又はＡＩＧの実行中のストア処理の際（４３０）に検出することができる。ＡＩＧの処理を途中停止する（abort）必要を生じさせ得る多くの他の可能なプロセッサ条件が存在する。これらには、システム内で検出されるエラー条件、並びに、プロセッサがそれらを正しく処理するのを可能にするために相当な付加的ハードウェア・サポートを必要とする他の条件が含まれる。多くの従来技術のトランザクショナル・メモリ・アーキテクチャは、トランザクションの途中停止及び後の再試行のための備えを含む。従来技術のソフトウェア構成を例示的な実施形態と一緒に用いて、全ての起こり得る特殊ケースに対処するためにハードウェアを提供する必要性をなくすことができる。簡単な例は、ＡＩＧ処理の途中のタイマー割り込みの場合である。割り込みにより、プロセッサは、部分的に完了したＡＩＧの部分ではない、実行コードに長時間を費やすことがある。この時間中、プロセッサがＡＩＧをアクティブに保持することが望ましくないことがある。システムは、タイマー割り込みが起ったとき、現在実行中のあらゆるＡＩＧに対してトランザクションの失敗を強いることができる。同様の手法をプロセッサ内で起こる他のあらゆる特殊ケースのイベントに用いることができる。
【００４０】
トランザクションの失敗又は強制された再試行は、図６に示される「ロールバック」処理についてのロールバック処理フローチャートのプロセスによって処理される。ここで図６を参照すると、トランザクション失敗条件（６００）がなければ、プロセッサがＡＩＧアクティブ・モードで継続できる（６５０）ことが分かる。例示的な実施形態は、トランザクション失敗の検出、及びトランザクション・ロールバックの発生に対して「イーガー（eager）」ポリシーを用いる。また、例示的な実施形態は、ロールバックに必要とされるアクションをとるために、トランザクションの終了まで待つシステムにおいて用いることもできる。ＡＩＧの一部として実行されるメモリ更新は、同時に通常の主ストレージにコミットされるか（図５）、又は「ロールバック」動作によって廃棄される（６２０−６４０）。
【００４１】
トランザクション失敗条件の発見に失敗すると（６００）、幾つかの付加的なステップが必要になる（６１０、６２０）。ロールバック・トランザクション・テーブル処理エントリ・ステップは、ＡＩＧについてのトランザクション・テーブル（２３０）及びキャッシュ構造体（１０６）を検査し、いずれかの旧データ（又は旧データ状態）を、エントリ内に示される主メモリ・アドレス（２４０）に書き戻す（ライトバックする）。関連したアドレスについてのＰＴＲＡＮビットがリセットされる。ロールバック処理（６２０）は、テーブル内の最後の有効エントリが処理されるまで継続する（６３０）。最後の有効エントリが処理された後、ロールバックが完了する（６４０）。この時点でプロセッサがとるアクションは、トランザクショナル・メモリのための種々のソフトウェア・アーキテクチャによって異なる。背景技術において説明されたいずれかのトランザクショナル・メモリ・アーキテクチャを用いることもできる。場合によっては、ＡＩＧは、初めから再試行される。他の場合には、トランザクション失敗に対処するために、特別なソフトウェア・ハンドラが呼び出される。例示的な実施形態を、これらの異なるアーキテクチャのいずれかと共に用いることができる。
【００４２】
例示的な実施形態は、「ネスト化」トランザクションの実行をサポートする。図７に示すように、第１のＡＩＧの範囲内に第２のＡＩＧを含ませることができる。各々のＢＥＧＩＮ＿ＡＩＧ特殊命令文（図７）により、システムが、トランザクション・テーブル（２３０）を作成し、テーブルをＡＩＧと関連付ける。ストレージ・アドレスがＡＩＧに属するかどうか（３５０）についての決定は、内側ＡＩＧ（Ａ）、又は内側ＡＩＧと外側ＡＩＧとの組み合わせ（Ａ＆Ｂ）を含むことができる。ＥＮＤ＿ＡＩＧの特殊命令文（図７）は、トランザクション・シーケンスを終了させるが、図示したように、特定のトランザクション（トランザクションＢ）についてのシーケンスを別のシーケンス（トランザクションＡ）内にネスト化することができる。複数のトランザクション・テーブル（２３０）を用いて、トランザクショナル・メモリについての多数のネスト化アーキテクチャをサポートすることができる。「旧データ」又は旧データ状態の複数のバージョンを、任意の数のキャッシュ構造体（１０６）又は任意のネスト化深さにあるトランザクション・テーブル（２３０）内にストアすることができる。投機的状態を保持するのにデータ・キャッシュに依存する従来技術のトランザクショナル・メモリ・システムは、付加的な状態情報をキャッシュ・ディレクトリに付加し、かつ、付加的な複雑さをキャッシュ・コヒーレンス・プロトコルに付加せずに、ネスト化トランザクションに対して同様のサポートを提供することはできない。従来技術のシステムのネスト化サポートは、それらの設計に大きなハードウェア複雑さの不利益を負わせる。例示的な実施形態を、内側ＡＩＧ（命令Ｂ０、命令Ｂ１）及び外側ＡＩＧ（命令Ａ０、命令Ａ１、命令Ａ２）の両方からのエントリを含む組み合わせられたトランザクション・テーブル／キャッシュ構造体を含むように拡張させることもできる。この組み合わせられたトランザクション・テーブル／キャッシュ構造体を、個々のトランザクション・テーブル及びキャッシュ構造体の代わりに、又は個々のトランザクション・テーブル及びキャッシュ構造体に加えて、用いることができる。
【００４３】
例示的な実施形態に付加して、トランザクション・テーブル操作の処理、並びに、ＰＴＲＡＮビットの設定及び再設定を速めることができる多くの付加的なハードウェア・フィーチャ（feature）が存在する。ＰＴＲＡＮビットは主ストレージ・データの一部であるので、これをシステムの通常のデータ・キャッシュ内にキャッシュすることができる。トランザクション・テーブルもまた主ストレージの一部であるので、これもキャッシュすることができる。本明細書で用いられる「主ストレージ（main storage）」という用語は、ＤＲＡＭメモリ・チップのアレイを指す。付加的な制御情報をデータ・キャッシュに付加して、特定のアドレスが「共有ＡＩＧアクセス」に対して許可されるかどうかを示すことができ、従って場合によっては、トランザクション・テーブルを検索する必要性をなくすことができる。
【００４４】
上述したような本発明の例示的な実施形態の能力は、ソフトウェア、ファームウェア、ソフトウェア及びファームウェアの何らかの組み合わせを伴うハードウェアの形で実装することができる。
【００４５】
図８は、例示的な実施形態を用いたコンピューティング・システムにおける命令の復号及び実行のフローを示す。例示的な実施形態は、ＢＥＧＩＮ＿ＡＩＧ命令を用いて、ＡＩＧの初めを示し、ＥＮＤ＿ＡＩＧ命令を用いてＡＩＧの最後を示す。命令グループの初め及び最後にマーク付けする他のいずれかの適切な方法を用いることもできる。命令又はマークは、プログラマーにより、高水準言語でコード内に明示的に挿入することができ、或いは、コンパイラ若しくはトランスレータにより、高レベルのロッキング関数の実装として付加することができる。命令又はマークは、ライブラリ関数呼び出しによって付加することができ、又はランタイム環境における特別イベントにより含ませることができる。命令又はマークは、特定の命令シーケンスの復号又は新しい実行モードに入る特別コマンドの受信への応答として、ファームウェア、ハードウェア、又はこれらの両方の組み合わせによって生成することができる。
【００４６】
例示的な実施形態は、命令を復号した（８００）後、ＡＩＧの初めを識別する。ＢＥＧＩＮ＿ＡＩＧ命令が復号されたと判断した（８０５）場合、プロセッサは新しい実行モード、すなわちＡＩＧモード（８１５）に入り、他の場合には、命令は、通常通りに実行され（８１０）、処理は次の命令に進む（８００）。
【００４７】
ＡＩＧモードに入る前に、伝統的なプログラム呼び出しがＩＢＭ  Ｚ−Ｓｅｒｉｅｓアーキテクチャ内で処理されるのと同じ方法で、プロセッサのアーキテクト（architected）状態が保存される。他のいずれかのプロセッサ・アーキテキチャ上で、任意の同様の状態保存機構を用いることができる。プロセッサは、ＡＩＧが失敗した場合にこの保存された状態に直接戻ることができ、又は、一連の他のエラー処理ルーチンを呼び出した後にこの状態に戻ることができる。ＡＩＧモードにある間、命令の復号が継続する（８２０）。ロード又はストアが復号される（８２５）場合、これらのロード及びストアの特別な処理が必要になる（８４０）。ＡＩＧの内側のロードの処理のために必要なステップが図３に記載され、ＡＩＧの内側のストアに関しては図４に記載される。ＡＩＧ内のロード及びストアが処理された後、図３及び図４の説明に記載されたようなＡＩＧ失敗があったかどうかが判断される（８５０）。失敗があった場合には、特殊ハンドラが呼び出される（８６０）。トランザクション失敗についての特殊ハンドラの動作は、例示的な実施形態を用いるシステムのアーキテクチャによって変化し得る。従来技術においてトランザクション失敗を処理する多くの方法が説明されており、そのいずれかをこの目的のために用いることができる。可能な方法は、トランザクションを初めから設定された試行回数だけ再試行すること、失敗を引き起こした条件が変わるのを待つこと、スレッド間の競合を解決するための特殊ソフトウェア・ルーチンを呼び出すこと等を含む。これらの可能な失敗ハンドラは、失敗を引き起こしたＡＩＧのロールバックを要求することができる（８６０）。失敗が検出されなかった場合には、そのロード又はストアがＡＩＧの最後の命令であったかどうかが判断される（８５５）。その命令がＡＩＧ内の最後の命令である場合には、図５に記載されたプロセスを用いてＡＩＧがコミットされる（８６５）。次に、プロセッサはＡＩＧモードを終了し、ＡＩＧの後の次の順次命令を続ける。
【００４８】
ＡＩＧの内側のロード及びストア以外の命令の復号は、必ずしも特別な処理を必要としない（８３０）。命令がロード又はストア型命令でない場合には、その命令が別のＢＥＧＩＮ＿ＡＩＧであるかどうかが判断される（８３０）。ネスト化ＡＩＧ命令は、特別な処理を必要とする（８３５）。従来技術は、ネスト化トランザクションを処理する多くの異なる方法を含む。例示的な実施形態を用いて、それらのいずれかをサポートすることができる。例示的な実施形態に関するネスト化ＡＩＧハンドラは、「内側」のＡＩＧの命令を「外側」のＡＩＧに付加して、単一の大きなＡＩＧを作成する。本発明の他の実施形態は、内側のネスト化トランザクションの一部であるロード及びストアのための異なる処理規則、並びに、内側のネスト化トランザクションのコミットメント及び失敗処理のための特別な規則を提供することができる。命令がＢＥＧＩＮ＿ＡＩＧではないと判断された場合、その命令は実行され（８４５）、次に、その命令がＡＩＧの最後の命令であるかどうかが判断される（８５５）。好ましい実施形態は、ＥＮＤ＿ＡＩＧ命令の復号を用いて、ＡＩＧの最後の命令に達したことを示す。ＡＩＧの最後の命令に達した場合、ＡＩＧはメモリにコミットされ、プロセッサはＡＩＧ動作モードを終了する（８６５）。
【００４９】
図９は、例示的な実施形態によって実装することができる旧データ状態のストア・フローを示す。ブロック９０２において、ＡＩＧと関連した旧データ状態をキャッシュ構造体（１０６）に書き込む要求を受け取る（例えば、図４のブロック４５０から）
【００５０】
前述のように、キャッシュ構造体（１０６）は、キャッシュ・ストレージ（１０４）内に配置され、旧データ状態を読み書きするときに迅速なデータ・アクセスをもたらす。例示的な実施形態において、キャッシュ構造体（１０６）はハードウェア・バッファとなるが、例示的な実施形態によって、他のソフトウェア及び／又はハードウェアの実装を実現することができる。例示的な実施形態において、ハードウェア・バッファは、トランザクション・テーブル（２３０、２３１）に対応し、各々のトランザクション・テーブル（２３０、２３１）について実装された１つのバッファ（論理的又は物理的）が存在する。この実施形態において、トランザクション・テーブル（２３０、２３１）についての次エントリ・レジスタ（２０２、２１２）は、旧データ状態をストアする（又は取り出す）ための対応するバッファによって利用することができる。他の例示的な実施形態においては、複数のトランザクション・テーブル（２３０、２３１）によって１つのバッファを利用して、旧データ状態をストアする。この実施形態においては、バッファに対して別個のインデックスが保持され、トランザクション・テーブル（２３０、２３１）内の旧データ状態とアドレスとの間の相関関係が保持される。
【００５１】
ブロック９０４において、旧データ状態をバッファ内にストアできるかどうかが判断される。図９に示される実施形態において、バッファが一杯である場合には、旧データ状態をバッファ内にストアすることができない。例示的な実施形態において、キャッシュの制御構造体内の１ビットが、バッファが一杯であることを示すために用いられる。バッファが一杯である場合には、ブロック９０８が実行され、旧データ状態は、次エントリ・レジスタ（２０２、２１２）により示される位置（即ち、対応するアドレスのような、トランザクション・テーブル内の同じ行）においてトランザクション・テーブルに書き込まれる。旧データ状態がそのトランザクション・テーブル内に配置されていることを示すように、トランザクション・テーブルのヘッダ内の１ビットが設定される。
【００５２】
ブロック９０４において、バッファが一杯ではないと判断された場合、処理はブロック９０６に進む。ブロック９０６において、旧データ状態がバッファに書き込まれる。
【００５３】
図９に示される実施形態において、各々のトランザクション・テーブルは、対応するバッファを有し、旧データ状態は、次エントリ・レジスタ（２０２、２１２）により示される位置においてバッファに書き込まれる。旧データ状態がそのバッファ内に配置されているか又はトランザクション・テーブルのデータ・フィールド（２４２）内に配置されているかを示すように、トランザクション・テーブル内の１ビットが設定される。
【００５４】
技術的効果及び利点として、既存システムと比べてオーバーヘッドが遥かに少ない高速トランザクショナル・メモリ・システムであることが挙げられる。さらに、投機的ロード及びストア命令と関連した旧データ状態をストアするためのキャッシュ位置を設けることによって、帯域幅要件及び処理時間が減少される。さらに、キャッシュ構造体が一杯になったときにキャッシュに対するバックアップとして主ストレージ内のトランザクション・テーブルを用いることにより、システムの信頼性及び可用性が改善される。
【００５５】
本明細書で用いられる用語は、特定の実施形態を説明する目的のためのものにすぎず、本発明を限定することを意図するものではない。本明細書で用いられる場合、文脈から明らかにそうでないことが示されていない限り、「ａ」、「ａｎ」及び「ｔｈｅ」の単数形は、複数形も同様に含むことが意図される。「含む（ｃｏｍｐｒｉｓｅｓ）」及び／又は「含んでいる（ｃｏｍｐｒｉｓｉｎｇ）」という用語は、本明細書で用いられる場合、言明された特徴、整数、ステップ、動作、要素及び／又はコンポーネントの存在を特定するものではあるが、１つ又は複数の他の特徴、整数、ステップ、動作、要素、コンポーネント及び／又はそれらのグループの存在又は追加を排除するものではないこともさらに理解される。
【００５６】
以下の特許請求の範囲における全ての「手段又はステップと機能との組み合わせ（ミーンズ又はステップ・プラス・ファンクション）」要素の対応する構造、材料、行為及び均等物は、その機能を、明確に特許請求されているように他の特許請求された要素と組み合わせて実行するための、いかなる構造、材料又は行為をも含むことが意図される。本発明の説明は、例示及び説明の目的で提示されたものであるが、網羅的であることを意図するものではなく、本発明を開示された形態に限定することを意図するものでもない。本発明の範囲及び精神から逸脱することのない多くの変更及び変形が、当業者には明らかである。実施形態は、本発明の原理及び実際の用途を最も良く説明するため、及び、当業者が本発明を種々の変更を有する種々の実施形態について企図される特定の使用に好適なものとして理解することを可能にするために、選択及び記載された。
【００５７】
当業者であれば認識するように、本発明の態様は、システム、方法、又はコンピュータ・プログラム製品として具体化することができる。従って、本発明の態様は、全体がハードウェアの実施形態、全体がソフトウェアの実施形態（ファームウェア、常駐ソフトウェア、マイクロコード等を含む）、又は、ソフトウェアの態様とハードウェアの態様とを組み合わせた実施形態の形を取ることができ、本明細書においてはこれらの全てを一般に、「回路」、「モジュール」又は「システム」と呼ぶことができる。さらに、本発明の態様は、媒体内に具体化されたコンピュータ使用可能プログラム・コードを有する、いずれかの有形の表現媒体内に具体化されたコンピュータ・プログラム製品の形態をとることができる。
【００５８】
１つ又は複数のコンピュータ可読媒体の任意の組み合わせを利用することができる。コンピュータ可読媒体は、コンピュータ可読信号媒体又はコンピュータ可読ストレージ媒体とすることができる。コンピュータ可読ストレージ媒体は、例えば、電子、磁気、光学、電磁気、赤外線若しくは半導体のシステム、装置若しくはデバイス、又は上記の任意の適切な組み合わせとすることができるが、これらに限定されるものではない。コンピュータ可読ストレージ媒体のより具体的な例（非網羅的なリスト）として、１つ又は複数の配線を有する電気的接続、ポータブル・コンピュータ・ディスケット、ハード・ディスク、ランダム・アクセス・メモリ（ＲＡＭ）、読み出し専用メモリ（ＲＯＭ）、消去可能プログラマブル読み出し専用メモリ（ＥＰＲＯＭ又はフラッシュメモリ）、光ファイバ、ポータブル・コンパクト・ディスク読み出し専用メモリ（ＣＤ−ＲＯＭ）、光記憶装置、磁気記憶装置、又は上記のいずれかの適切な組み合わせが挙げられる。本明細書の文脈では、コンピュータ可読ストレージ媒体とは、命令実行システム、装置又はデバイスによって又はこれらと関連して用いるためのプログラムを収容又はストアすることができるいずれかの有形媒体とすることができる。
【００５９】
コンピュータ可読信号媒体は、例えばベースバンド内又は搬送波の一部にコンピュータ可読プログラム・コードを組み入れた搬送データ信号を含むことができる。こうした搬送データ信号は、電磁気、光、又はこれらのいずれかの適切な組み合わせを含むがこれらに限定されない、種々の形態のいずれかを取ることができる。コンピュータ可読信号媒体は、コンピュータ可読ストレージ媒体ではなく、命令実行システム、装置又はデバイスによって又はこれらと関連して用いるためのプログラムを通信し、伝搬し、又は転送することができる、いずれかのコンピュータ可読媒体とすることができる。
【００６０】
コンピュータ可読媒体に組み入れられたプログラム・コードは、無線、有線、光ファイバ・ケーブル、ＲＦなど、又はこれらのいずれかの適切な組み合わせを含むがこれらに限定されない、いずれかの適切な媒体を用いて伝送することができる。
【００６１】
本発明の態様についての動作を実行するためのコンピュータ・プログラム・コードは、Ｊａｖａ、Ｓｍａｌｌｔａｌｋ、Ｃ＋＋等のようなオブジェクト指向型プログラミング言語、及び、「Ｃ」プログラミング言語又は同様のプログラミング言語のような従来の手続き型プログラミング言語を含む、１つ又は複数のプログラミング言語のいずれかの組み合わせで記述することができる。プログラム・コードは、全体がユーザのコンピュータ上で実行される場合もあり、独立したソフトウェア・パッケージとして、一部がユーザのコンピュータ上で実行される場合もあり、一部がユーザのコンピュータ上で実行され、一部が遠隔コンピュータ上で実行される場合もあり、又は全体が遠隔コンピュータ若しくはサーバ上で実行される場合もある。後者のシナリオにおいては、遠隔コンピュータは、ローカル・エリア・ネットワーク（ＬＡＮ）若しくは広域ネットワーク（ＷＡＮ）を含むいずれかのタイプのネットワークを通じてユーザのコンピュータに接続することができ、又は（例えば、インターネット・サービス・プロバイダを用いたインターネットを通じて）外部コンピュータに接続することもできる。
【００６２】
本発明の態様を、本発明の実施形態による方法、装置（システム）及びコンピュータ・プログラム製品のフローチャート図及び／又はブロック図を参照して以下で説明する。フローチャート図及び／又はブロック図の各ブロック、並びにフローチャート図及び／又はブロック図内のブロックの組み合わせは、コンピュータ・プログラム命令によって実装することができることが理解されるであろう。これらのコンピュータ・プログラム命令を、汎用コンピュータ、専用コンピュータ又は他のプログラム可能データ処理装置のプロセッサに与えて機械を製造し、それにより、コンピュータ又は他のプログラム可能データ処理装置のプロセッサを介して実行される命令が、フローチャート及び／又はブロック図の１つ又は複数のブロックにおいて指定された機能／動作を実装するための手段を作り出すようにすることができる。
【００６３】
これらのコンピュータ・プログラム命令を、コンピュータ、他のプログラム可能データ処理装置、又は他のデバイスを特定の方式で機能させるように指示することができるコンピュータ可読媒体内にストアして、それにより、そのコンピュータ可読媒体内にストアされた命令が、フローチャート及び／又はブロック図の１つ又は複数のブロック内で指定された機能／動作を実装する命令を含む製品を製造するようにすることもできる。
【００６４】
コンピュータ・プログラム命令を、コンピュータ、他のプログラム可能データ処理装置、又は他のデバイスにロードし、コンピュータ、他のプログラム可能データ処理装置、又は他のデバイス上で一連の動作ステップを行わせてコンピュータ実装処理を生成し、それにより、コンピュータ又は他のプログラム可能装置上で実行される命令が、フローチャート及び／又はブロック図の１つ又は複数のブロック内で指定された機能／動作を実装するためのプロセスを提供するようすることもできる。
【００６５】
前述のように、実施形態は、コンピュータ実施のプロセス及びそれらのプロセスを実行するための装置の形態で具体化することができる。例示的な実施形態において、本発明は１つ又は複数のネットワーク要素によって実行されるコンピュータ・プログラム・コードの形で具体化することができる。実施形態は、製品として有形媒体内に具体化された命令を含むコンピュータ・プログラム・コード論理１００４を有するコンピュータ使用可能媒体１００２上の、図１０に示されるようなコンピュータ・プログラム製品１０００を含む。コンピュータ使用可能媒体１００２の例示的な製品として、フロッピー・ディスケット、ＣＤ−ＲＯＭ、ハード・ドライブ、ユニバーサル・シリアル・バス（ＵＳＢ）フラッシュ・ドライブ、又は任意の他のコンピュータ可読ストレージ媒体を挙げることができ、コンピュータ・プログラム・コード論理１００４がコンピュータにロードされ、コンピュータによって実行されるとき、コンピュータは本発明を実施するための装置となる。実施形態は、例えば、ストレージ媒体内にストアされ、コンピュータにロードされ及び／又はコンピュータによって実行されるか、或いは、例えば、電気配線若しくはケーブルにより、光ファイバを通して、又は電磁放射線を介して何らかの伝送媒体上で伝送される、コンピュータ・プログラム・コード論理１００４を含み、コンピュータ・プログラム・コード論理１００４がコンピュータにロードされ、コンピュータによって実行されるとき、コンピュータは本発明を実施するための装置となる。汎用マイクロプロセッサ上に実装されるとき、コンピュータ・プログラム・コード論理１００４のセグメントは、マイクロプロセッサを構成して、特定の論理回路を作成する。
【００６６】
図面におけるフローチャート及びブロック図は、本発明の様々な実施形態による、システム、方法及びコンピュータ・プログラム製品の可能な実装のアーキテクチャ、機能及び動作を示すものである。この点で、フローチャート又はブロック図における各ブロックは、モジュール、セグメント又はコードの一部を表すことができ、これらは、指定された論理機能を実装するための１つ又は複数の実行可能命令を含む。幾つかの代替的な実装においては、ブロックに記された機能が図面に記された順序通りに行われない場合があることにも留意すべきである。例えば、連続して示された２つのブロックが、実際には実質的に同時に実行されることがあり、又は、これらのブロックが、関与する機能に応じて、ときとして逆順で実行されることもある。ブロック図及び／又はフローチャート図における各ブロック、並びにブロック図及び／又はフローチャート図におけるブロックの組み合わせは、指定された機能若しくは動作を行う専用ハードウェア・ベースのシステム又は専用のハードウェアとコンピュータ命令との組み合わせによって実装できることにも留意される。
【符号の説明】
【００６７】
１００、１０１、１０２：マイクロプロセッサ
１０４：キャッシュ
１０６：キャッシュ構造体
１１０：相互接続要素
１２０：物理メモリ・アレイ
１２１：トランザクション・データ
１２２：ＰＴＲＡＮタグ
２０１、２１１：テーブル起点
２０２、２１２：次エントリ・レジスタ
２０３、２１３：スレッド識別子
２２０：実システム・メモリ
２３０、２３１：トランザクション・テーブル
２４０：アドレス
２４１：トランザクション情報識別子（トランザクション情報フィールド）
２４２：旧又は新データ（データ・フィールド）
１０００：コンピュータ・プログラム製品
１００２：コンピュータ使用可能媒体
１００４：コンピュータ・プログラム・コード論理
【図１】
2013503379.tif 000003
【図２】
2013503379.tif 000004
【図３】
2013503379.tif 000005
【図４】
2013503379.tif 000006
【図５】
2013503379.tif 000007
【図６】
2013503379.tif 000008
【図７】
2013503379.tif 000009
【図８】
2013503379.tif 000010
【図９】
2013503379.tif 000011
【図１０】
2013503379.tif 000012
【国際調査報告】
2013503379.tif 000013
2013503379.tif 000014