(57)【要約】【課題】  ホスト・マルチプロセッシング・システムが緩やかな整合性モデルをサポートし、ターゲット・マルチプロセッシング・システムが強い整合性モデルを指定するときに、あるマルチプロセッシング・システムのメモリ整合性挙動を他のマルチプロセッシング・システム上で効果的にエミュレートするための方法および構造を提供すること。【解決手段】  マルチプロセッサ・システムにおけるエミュレーションの方法（およびシステム）は、マルチプロセッサ・システムのホスト・マルチプロセッシング・システムが弱い整合性モデルをサポートし、マルチプロセッサ・システムのターゲット・マルチプロセッシング・システムが強い整合性モデルをサポートするエミュレーションを実行するステップを含む。【選択図】  図８
2010182331.tif 000002
【特許請求の範囲】
【請求項１】
複数命令のグループ実行の終了時に共用書込みをメモリにコミットする方法において、
変換の終了時に、あるブロックがアクセスした「共用書込み」位置への値をマルチプロセッサ・システムの他のどのプロセッサも変更していないことをチェックして保証するスタブ・コードを追加するステップを具備する方法。 
【請求項２】
他のプロセッサによるアクセスから共用メモリ位置をロックするステップと、
各ロード位置を再ロードし、対応するメモリ・オーダ・バッファ（ＭＯＢ）項目内に記憶された値と比較するステップとをさらに具備し、
すべての再ロードが元のロードと同じであると判明した場合に、前記ＭＯＢからのすべてのストアがメモリ内のそれぞれの実際の位置に対して行われる、請求項１に記載の方法。 
【請求項３】
ロード妥当性検査プロセス中に不一致が発生した場合に、すべてのレジスタをそれぞれの旧状態に復元し、ストア回復テーブル（ＳＲＴ）内の操作をアンドゥすることによって非「共用書込み」位置に対して行った前記ストアを逆転することにより、前記グループの実行全体を取り消すステップをさらに具備する、請求項２に記載の方法。 
【請求項４】
前記システムを前に有効だった状態に戻した後、実行を再試行するステップをさらに具備する、請求項３に記載の方法。 
【請求項５】
共用メモリ位置へのアクセスをロックするステップと、
メモリ・オーダ・バッファ（ＭＯＢ）内の第１の項目にポインタを設定し、前記ＭＯＢの終わりに達したかどうかを判定するステップと、
前記終わりに達していない場合に、前記ＭＯＢ内のその項目が空であるかどうかを判定するステップと、
前記項目がロードではないと判定された場合に、前記ＭＯＢへのポインタを増分するステップとをさらに具備する、請求項１に記載の方法。 
【請求項６】
前記項目がロードであると判定された場合に、前記項目内のアドレスから前記項目を再ロードするステップと、
再ロードした値が前記項目内の値と一致するかどうかを判定するステップと、
前記値が一致した場合に、前記ＭＯＢへのポインタを増分するステップと、
前記値が一致しない場合に、前記ロックを解除し、前記状態を復元し、ストア回復テーブル（ＳＲＴ）を使用して非共用書込みを復元することにより、前記グループの先頭まで回復を実行するステップとをさらに具備する、請求項５に記載の方法。 
【請求項７】
前記ＭＯＢの終わりに達している場合に、前記ＭＯＢ内の前記第１の項目に前記ポインタを設定し、前記ＭＯＢの終わりに達したかどうかを判定するステップと、
前記終わりに達していない場合に、前記ＭＯＢ内の前記項目が空であるかどうかを判定するステップと、
前記ＭＯＢ内の前記項目がストアであるかどうかを判定するステップと、
前記項目がストアである場合に、前記値をメモリに書き込み、前記ＭＯＢ内の前記ポインタを増分するステップとをさらに具備する、請求項６に記載の方法。 
【請求項８】
前記ＭＯＢ内の前記項目がストアではない場合に、前記ＭＯＢ内の前記ポインタが増分される、請求項７に記載の方法。 
【請求項９】
複数の命令を１つずつ処理するステップをさらに具備する、請求項１に記載の方法。 
【請求項１０】
メモリ・オーダ・バッファ（ＭＯＢ）とストア回復テーブル（ＳＲＴ）とを使用することにより、複数命令のグループ内の命令を処理するステップをさらに具備する、請求項１に記載の方法。 
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、一般に、コンピュータ・システムに関し、より具体的には、本質的に異なるメモリ共用挙動を備えた他のマルチプロセッシング・コンピューティング・システム上で、あるマルチプロセッシング・コンピューティング・システムのメモリ共用挙動をエミュレートするための方法に関する。
【背景技術】
【０００２】
エミュレーションの主な動機付けは、特定のアーキテクチャ用に作成されたシステムが最小限のパフォーマンス損失で他のアーキテクチャ上で実行できるようにすることである。その場合、明らかに、エミュレーション・プロセスの効率と、結果として得られる「ホスト」コード・シーケンスの品質は、最も重要なものである。
【０００３】
通常、コンピューティング・システムは、プロセッサと、メモリと、入出力装置とを含む、いくつかの部分を含んでいる。あるコンピューティング・システムの挙動を他のコンピューティング・システム上でエミュレートすることが必要である場合が多い。エミュレーションの主な理由の１つは、あるシステム（たとえば、「ターゲット・コンピューティング・システム」）用に作成されたプログラムが他のシステム（たとえば、「ホスト・コンピューティング・システム」）上で実行して同じ結果が得られるようにすることである。
【０００４】
他のプロセッサの命令セットを使用して、あるプロセッサの命令セットをエミュレートするために、いくつかの従来技法が開発されている（たとえば、１９９８年２月発表のStephen A. Herrodの「Using CompleteMachine Simulation to Understand Computer System Behavior」というスタンフォード大学博士論文により開示されたＳＩＭＯＳ、または１９８７年１０月４〜８日にオーランドで開催されたObject Oriented Programming Systems Languages and ApplicationsConference (OOPSLA)の会議録ならびにSpecialIssue of Sigplan Notices, vol. 22, No. 12, Dec. 1987, vol. 22, No. 7, Jun. 24におけるCathy Mayによる「Mimic: A Fast System/370 Simulator」という論文に開示されているＭＩＭＩＣ）。
【０００５】
エミュレーションを忠実に実行するためには、このようなシステム内のメモリの挙動をエミュレートすることも必要である。通常、この挙動には、プログラム指定アドレスによるメモリ内の位置の読取りおよび書込み以上のものが含まれる。
【０００６】
より具体的には、ある位置の内容がマルチプロセッシング・システム内の１つのプロセッサによって変更された場合、その変更をシステム内のすべてのプロセッサが監視しなければならない時期を左右する規則は、そのアーキテクチャで明確になっている。この点については、現在のほとんどのシステムは、システム内に１つのプロセッサしか存在しない場合にほぼ同様に動作する。すなわち、これらのシステムはプログラム・オーダを執行す
るが、これは単に、ステートメントＳ１がプログラム内に提示された命令シーケンス内の他のステートメントＳ２より先行する場合に、プロセッサはＳ２がその実行を開始する前にＳ１がその実行を完了したかのように動作しなければならないことを意味するだけである。これは、レジスタおよびメモリを含む、いずれかのリソースに対してＳ１が行った変更をＳ２が把握していなければならないことを暗示する。
【０００７】
したがって、前述のＳｉｍＯＳおよびＳｉｍＩＣＳ技法のように、ユニプロセッシング・システム上でマルチプロセッシング・システムをエミュレートする場合であって、ターゲット・システムとホスト・システムの両方がプログラム・オーダに従う場合、エミュレーション中のメモリ・アクセスは一連のエポック１０１と見なすことができ、各エポック１０１は図１に示すようにターゲット・システム内の１つのプロセッサを表す。すなわち、そのエリア内の番号はエミュレートしたプロセッサのＩＤを示し、網掛けエリア１００はそのシステムが他の機能を実行していることを示す。
【０００８】
あるエポック１０１中に２つ以上のプロセッサのエミュレートしたメモリ・アクセス間には同時対話がまったく存在しないので、ホスト・プロセッサ上でターゲット・プロセッサの正確なユニプロセッサ・エミュレーションを実行するだけで、プログラム・オーダを保証することができる。
【０００９】
このため、図１では、単一プロセッサ上で複数プロセッサをエミュレートしようと試みると、それぞれ異なる時期に異なるマルチプロセッサのインタリーブが行われる。したがって、プロセッサ１は所与の時期にエミュレートされ、次にプロセッサ２はしばらくの間エミュレートされ、次にエミュレーションは一時、プロセッサ１のエミュレーションに戻り、次にいかなるエミュレーションも行われないが、単一プロセッサが他の機能を実行している時期（たとえば、網掛けエリア１００）が存在する。したがって、所与の時期の単一プロセッサは、すべてのプロセッサについてではなく、マルチプロセッサのプロセッサのうちの１つのみについてエミュレーションを実行している。
【００１０】
上記のインタリーブ動作はきわめて効率が悪い。しかし、あるプロセッサの「クリティカル・セクション」を他のプロセッサのクリティカル・セクションとインタリーブすることが不可能であるという長所がある。すなわち、「クリティカル・セクション」は、２つのプロセッサが同時に入ることができないセクションである。
【００１１】
ユニプロセッサ上では、エミュレーションを実行しているときに大したことを（たとえば、特殊なことは何も）実行する必要はない。というのは、クリティカル・セクションには２つのプロセッサが同時に入ることがないからである。ある意味で、ユニプロセッサは、クリティカル・セクションには２つのプロセッサが同時に入ることがないという条件を自動的に満足している。同じように、マルチプロセッシング・システム上で全プロセッサをエミュレートしようとする場合、状況は劇的に変化する。すなわち、問題が発生する可能性がある。
【００１２】
たとえば、図２は、プロセッサ２０１と２０２との共用の一例が含まれるデッカー・アルゴリズムのアプリケーションを示している。図２の例では、２つのプロセッサ２０１、２０２がクリティカル・セクションにアクセスしようと試みている。この場合も、ユニプロセッサでは、クリティカル・セクション（たとえば、ある時期に１つのプロセッサのみが入ることができるセクション）のアクセスは問題にならない（たとえば、ユニプロセッサによって自動的に克服される）。というのは、図１に示すエポックの使用により、ユニプロセッサ動作は順次動作になるからである。
【００１３】
このため、デッカー・アルゴリズムを使用するプログラムを実現し、それをマルチプロセッシング・マシン上で実行し、ユニプロセッサ上でエミュレーションを実行している場合、何も問題は発生しないだろう。しかし、デッカー・アルゴリズムを使用する同じプログラムをターゲット・マシン上で実行し、マルチプロセッシング・システムによってそのターゲット・マシンをエミュレートしている場合、問題が発生するだろう。デッカー・ア
ルゴリズムは、ターゲット・プロセッサ２０１、２０２としてのプロセッサ２０１、２０２上で実行しているものと見なさなければならない。
【００１４】
具体的には、第１のプロセッサ２０１は変数ｘを設定し、もう一方のプロセッサ２０２がクリティカル・セクションに入る前にそれ自身の変数ｙを設定していないことを保証する。第２のプロセッサ２０２はｙを設定し、クリティカル・セクションに移る前にｘが設定されないことを保証する。ユニプロセッサ上でエミュレートしているときにアプリケーション全体が完了できるようにする方法がいくつかあるが、そのうちの２つを図３に示す。上記の通り、その時期にＰ２がエミュレートされるエポック変化まで、Ｐ１用のオーダ１が実行される。したがって、図３の２プロセッサ・オーダでは、エポック変化が発生すると、必ずエミュレーションがもう一方のプロセッサにスイッチするので、一方のプロセッサ（たとえば、Ｐ１）がクリティカル・セクション内にあるときに、もう一方のプロセッサ（Ｐ２）がクリティカル・セクションに入れないことは明白である。
【００１５】
しかし、一方のプロセッサのクリティカル・セクションを第２のプロセッサのクリティカル・セクションとインタリーブすることは不可能である。というのは、これは、ホスト・プロセッサがある時期に（ｘ＝１；ｙ＝０）を確認し、他の時期に（ｘ＝０；ｙ＝１）を確認し、その間に書込みが行われていないことを暗示すると思われるからである。
【００１６】
図４は、図２の方法／デッカー・アルゴリズムの間違った挙動に至る可能性のある状況を示している。図４のシステム４００は、共用メモリ４１０と、第１および第２のプロセッサ４３０Ａ、４３０Ｂ用にそれぞれ設けられたキャッシュ４２０Ａ、４２０Ｂとを含む。このため、図４の状況では、両方のプロセッサが同じ時期にクリティカル・セクション内で実行することができ、それにより問題を引き起こす。
【００１７】
すなわち、ターゲット・システムは、（たとえば、メモリへのストア後、他のプロセッサから肯定応答を受け取るまで待つことにより）この状況が決して発生しないことを保証する整合性モデルを有するものと想定する。このようなシステムの例としては、ＩＢＭシステム／３９０（商標）およびインテルｘ８６（商標）を含む。
【００１８】
また、ホスト・システムは、その実現を比較的高速にしようとして、より緩やかな整合性モデルを有し、メモリへの書込みのアトミック記録を保証しないものと想定する。したがって、このようなホスト・システムによって上記の例をエミュレートすると、その結果、間違った挙動になる可能性がある。
【００１９】
ＰｏｗｅｒＰＣ（商標）のように、このように緩やかな整合性モデルを有するシステムは常に、その後の命令の結果を確認する前にその命令より前のメモリ・アクションの結果がすべてのプロセッサによって確認されていることを保証する、特殊な同期化命令またはメモリ・バリア命令を提供する。
【００２０】
したがって、シミュレーションが正しく行われることを保証するための方法の１つは、すべてのメモリ命令の後にメモリ・バリア命令を続けることである。残念ながら、このような命令は完了するのにいくつかのサイクルを要する。しかも、メモリ命令（たとえば、メモリからのロードとメモリへのストア）はきわめて頻発するものである（たとえば、すべての命令の１／３程度の頻度）。
【００２１】
したがって、上記の問題の解決策を見つけることが望ましいことになる。さらに、特にターゲット・マルチプロセッシング・システム（より厳しいかまたは「強い」）に比べ、ホスト・マルチプロセッシング・システムの方が「より弱い」（より緩やかな）整合性モデルをサポートするときに、あるマルチプロセッシング・システムのメモリ整合性挙動を他のマルチプロセッシング・システム上でエミュレートする際のコストを最小限にすることが望ましいことになる。「より弱い」（または「緩やかな」）および「強い」という用語は、当業者には周知のものと思われることに留意されたい（たとえば、１９９６年１２月発行のIEEE Computer, vol. 29, no. 12の６６〜７６ページに掲載されたSarita Adve他の「Shared MemoryConsistency Models: A Tutorial」という論文および１９７９年９月発行のIEEE Transactions on Computers, C-28, 9の６９０〜６９１ページに掲載されたL. Lamportの「How to Make a Multiprocessor Computer ThatCorrectly Executes Multiprocess Programs」という論文を参照されたい）。
【００２２】
したがって、従来のエミュレーション方法および技法では、様々なレベルの変換を使用して、エミュレータが生成するホスト命令のパフォーマンスを強化することができる。しかし、すべての現行技法にもかかわらず、改善の余地はたくさん残っている。
【００２３】
このため、本発明以前の従来の技法では、特にホストが前述の緩やかな整合性モデルをサポートし、ターゲット・システムが強い整合性モデルを使用するときに、あるシステムのメモリ整合性を他のシステム上でエミュレートするための方法および装置はまったく存在していない。
【先行技術文献】
【非特許文献】
【００２４】
【非特許文献１】１９９８年２月発表のStephenA. Herrodの「Using Complete MachineSimulation to Understand Computer System Behavior」というスタンフォード大学博士論文
【非特許文献２】１９８７年１０月４〜８日にオーランドで開催されたObject Oriented Programming Systems Languages and ApplicationsConference (OOPSLA)の会議録ならびにSpecialIssue of Sigplan Notices, vol. 22, No. 12, Dec. 1987, vol.22, No. 7, Jun. 24におけるCathy Mayによる「Mimic: A Fast System/370 Simulator」という論文
【非特許文献３】１９９６年１２月発行のIEEEComputer, vol. 29, no. 12の６６〜７６ページに掲載されたSaritaAdve他の「Shared MemoryConsistency Models: A Tutorial」という論文
【非特許文献４】１９７９年９月発行のIEEETransactions on Computers, C-28, 9の６９０〜６９１ページに掲載されたL. Lamportの「How to Make aMultiprocessor Computer That Correctly Executes Multiprocess Programs」という論文
【特許文献】
【００２５】
【特許文献１】米国特許第６０３１９９２号
【発明の概要】
【発明が解決しようとする課題】
【００２６】
従来の方法および構造の上記その他の問題、欠点、短所を考慮して、本発明の一目的は、ホスト・マルチプロセッシング・システムが緩やかな整合性モデルをサポートし、ターゲット・マルチプロセッシング・システムが強い整合性モデルを指定するときに、あるマルチプロセッシング・システムのメモリ整合性挙動を他のマルチプロセッシング・システム上で効果的にエミュレートするための方法および構造を提供することにある。
【課題を解決するための手段】
【００２７】
本発明の第１の態様では、マルチプロセッサ・システムにおけるエミュレーションの方法（およびシステム）は、マルチプロセッサ・システムのホスト・マルチプロセッシング・システムが弱い整合性モデルをサポートし、マルチプロセッサ・システムのターゲット・マルチプロセッシング・システムが強い整合性モデルをサポートするエミュレーションを実行するステップを含む。
【００２８】
本発明の第２の態様では、ターゲット・マルチプロセッサ・コンピューティング・システムの挙動をエミュレートするためのエミュレータを含むマルチプロセッサ・コンピューティング・システムにおいて、ターゲット・マルチプロセッサ・コンピューティング・システムのメモリ整合性挙動をエミュレートするための方法は、メモリ・アクションの前にメモリ・バリア命令を実行するステップであって、メモリ・バリア命令の実行前に実行されたメモリ・アクションの結果がホスト・コンピューティング・システム内のすべてのプロセッサによって入手されていることをそのメモリ・バリア命令が保証するステップを含み、前記マルチプロセッサ・コンピューティング・システムのホスト・コンピューティング・システムが弱い整合性モデルをサポートし、マルチプロセッサ・システムのターゲット・マルチプロセッシング・システムが強い整合性モデルをサポートする。
【００２９】
本発明の第３の態様では、マルチプロセッサ・メモリ整合性の効率のよいエミュレーションの方法（およびシステム）は、メモリ・バリア命令の実行前に実行されたメモリ・アクションがホスト・コンピューティング・システム内のすべてのプロセッサによって登録されていることを保証するメモリ・バリア命令を形成するステップを含み、ホスト・マルチプロセッシング・システムが緩やかな整合性モデルをサポートし、ターゲット・マルチプロセッシング・システムが強い整合性モデルを指定する。
【００３０】
本発明の第４の態様では、マルチプロセッシング・システムにおけるメモリ整合性を保証する方法（およびシステム）は、命令がロードまたはストアであるかどうかを判定するステップと、その命令がロードまたはストアであると判定された場合に、その命令のアドレスを解明し、そのアドレスがローカル・ルックアサイド・バッファ（ＬＬＢ）に記憶されているかどうかを判定するステップと、そのアドレスがＬＬＢ内にある場合に、その位置が共用読取り状態になっているかどうかを判定するステップと、その位置が共用読取り状態になっていると判定された場合に、現行アドレスが書込みであるかどうかを判定するステップと、現行アドレスが書込みではない場合に、その命令のエミュレーションを実行するステップとを含む。
【００３１】
本発明の第５の態様では、マルチプロセッサ・システムにおいて複数命令のグループ内の整合性を維持するためのコードを挿入する方法（およびシステム）は、命令がロードまたはストアであるかどうかを判定するステップと、その命令がロードまたはストアであると判定された場合に、そのアドレスを解明し、そのアドレスがローカル・ルックアサイド・バッファ（ＬＬＢ）内にあるどうかを判定するステップと、そのアドレスがＬＬＢ内にある場合に、その位置が共用読取り状態になっているかどうかを判定するステップと、その位置が共用読取り状態になっていると判定された場合に、現行アクセスが書込みであるかどうかを判定するステップと、現行アクセスが書込みであると判定された場合に、その位置を共用書込みに設定し、現行アクセスがロード命令であるかどうかを判定するステップと、現行アクセスがロードであると判定された場合に、ロードを実行し、そのロードがメモリ・オーダ・バッファ（ＭＯＢ）テーブルにより満足されたかどうかを判定するステップと、そのロードがＭＯＢテーブルにより満足されていない場合に、メモリ順序番号で索引が付けられたＭＯＢテーブルに対応する項目を挿入するステップとを含む。
【００３２】
本発明の第６の態様では、複数命令のグループ実行の終了時に共用書込みをメモリにコミットする方法（およびシステム）は、変換の終了時に、あるブロックがアクセスした「共用書込み」位置への値を他のどのプロセッサも変更していないことをチェックして保証するスタブ・コードを追加するステップを含む。
【００３３】
本発明の第７の態様では、共用マルチプロセッサ・システム用の記憶域参照テーブル（ＳＲＴ）は、構築され、ストア参照の数と同数の項目を含むテーブルを含み、各項目が、アドレス・フィールドと、回復のために元の値を記憶するための旧値フィールドとを含む複数のフィールドを含み、そのテーブルが全項目の共用書込み状況に関する情報を記憶する。
【００３４】
本発明の第８の態様では、共用マルチプロセッサ・システム用のメモリ・オーダ・バッファ（ＭＯＢ）は、現在参照中の位置に関する情報を共有することにより維持されるテーブルを含み、その情報が、ある項目の特定の状態が共用書込み状態を具備するかどうかを区別する情報を含む。
【００３５】
本発明の第９の態様では、マルチプロセッサ・システムにおけるエミュレーションのためのシステムは、マルチプロセッサ・システムのホスト・マルチプロセッシング・システムが弱い整合性モデルをサポートし、マルチプロセッサ・システムのターゲット・マルチプロセッシング・システムが強い整合性モデルをサポートするエミュレーションを実行するためのエミュレータを含む。
【００３６】
本発明の第１０の態様では、マルチプロセッサ・システムにおけるエミュレーションの方法を実行するためにディジタル処理装置により実行可能な複数の機械可読命令からなるプログラムを具体的に実施する信号運搬媒体が提供され、その方法は、マルチプロセッサ・システムのホスト・マルチプロセッシング・システムが弱い整合性モデルをサポートし、マルチプロセッサ・システムのターゲット・マルチプロセッシング・システムが強い整合性モデルをサポートするエミュレーションを実行するステップを含む。
【００３７】
本発明の固有かつ自明ではない諸態様により、マルチプロセッシング・システム上でエミュレートされる複数のプロセッサによりクリティカル・セクションのエミュレーションを効率よく実行することができる。すなわち、本発明は、種々のプロセッサについて同時にクリティカル・セクションをエミュレートしているときに、このようなクリティカル・セクションに入るプロセッサをエミュレートすることを対象とする。この場合も、これまでは、エミュレーションが伝統的にユニプロセッサ上で実行されていたので、このような問題は検出されていなかった。この点については、本発明者らは、このような問題を認識し、固有かつ自明ではない解決策を考案した最初の者である。
【００３８】
前述のメモリ整合性を保証するために、第１の実施形態では、本発明は、メモリ・バリア命令の実行前に実行されたメモリ・アクションがホスト内のすべてのプロセッサによってアクセス（たとえば、登録）されていることを保証するメモリ・バリア命令を提供する。プロセッサにはこのようなメモリ・アクション／動作を登録する機会があったので、これにより、メモリ整合性の達成が保証される。
【００３９】
本発明は「共用書込み」状態に最も関係するものであることに留意されたい。
【００４０】
上記その他の目的、態様、および長所は、添付図面に関連して以下に示す本発明の好ましい実施形態の詳細な説明からより十分に理解されるだろう。
【図面の簡単な説明】
【００４１】
【図１】マルチプロセッサ・システムのユニプロセッサ・エミュレーションにおけるエポック１０１を示す図である。
【図２】第１および第２のプロセッサ２０１、２０２により実行されるプログラムで実現されたデッカー・アルゴリズムの一例を示す図である。
【図３】図２のプログラムに関しユニプロセッサ上のエミュレーションの２つのサンプル・オーダの一例を示す図である。
【図４】図２のアルゴリズムの間違った挙動に至る可能性がある、システム４００内の状況を示す図である。
【図５】グローバル・ページ・テーブル項目５００内の読取り／書込みマスク・フィールド５７０を示す図である。
【図６】あるページの共用状況を決定するための手順６００を示す図である。
【図７】あるページの共用メモリ状態間の遷移を示す部分状態マシン７００を示す図である。
【図８】メモリ・バリア命令の挿入プロセス８００を示す図である。
【図９】メモリ・オーダ・バッファ（ＭＯＢ）９００を示す図である。
【図１０】図９のメモリ・オーダ・バッファ９００への共用メモリ・アクセスのマッピング１０００を示す図である。
【図１１】回復のために記憶域参照テーブル（ＳＲＴ）１１１０へのストアを保管するプロセス１１００を示す図である。
【図１２】ＭＯＢ９００およびＳＲＴ１１１０を使用して複数命令のグループ内で整合性を維持するためのコードの挿入のプロセス１２００を示す図である。
【図１３】グループ実行の終了時に共用書込みをメモリにコミットするためのプロセス１３００を示す図である。
【図１４】そこに本発明を取り入れるための例示的なハードウェア／情報処理システム１４００を示す図である。
【図１５】本発明による方法のプログラムの諸ステップを記憶するための信号運搬媒体１５００（たとえば、記憶媒体）を示す図である。
【発明を実施するための形態】
【００４２】
次に、添付図面、より具体的には図５〜１５を参照すると、本発明による方法および構造の好ましい実施形態が示されている。
【００４３】
この説明のため、ターゲット・マルチプロセッシング・システムは順次整合性をサポートするものと想定する。これは、ほとんどの既知のシステムがサポートする整合性より強い形式の整合性である。順次整合性はＬａｍｐｏｒｔによって定義され（１９７９年９月発行のIEEE Transactions on Computers, C-28, 9の６９０〜６９１ページに掲載されたL. Lamportの「How to Make a Multiprocessor Computer ThatCorrectly Executes Multiprocess Programs」という論文）、どの実行の結果もすべてのプロセッサの動作が何らかの順番で実行された場合と同じになり、各個別プロセッサの動作がそのプログラムによって指定された順序で現れることを暗示する。
【００４４】
また、ホスト・マルチプロセッシング・システムは弱い整合性（Ａｄｖｅ他による前述の論文に定義されたＲＣｓｃ）をサポートするが、メモリ・コヒーレンス（たとえば、メモリ・コヒーレンスは、単一位置に対して行った変更の順序が、どのプロセッサから見ても同じになることを暗示する）を備えているものと想定する。
【００４５】
そのうえ、バリア後のすべてのメモリ動作が、すべてのプロセッサによって確認（たとえば、登録）されたバリア前のすべてのメモリ動作の後で実行されることを保証する働きをする、メモリ・バリア命令ｍｂａｒの存在が想定されている。
【００４６】
順次整合性は、メモリにアクセスするすべての命令の後にｍｂａｒ命令を続けることにより保証することができる。前述の通り、同期化命令は通常、複数サイクルを要するので、可能であれば、回避しなければならない。
【００４７】
第１の所見は、すべてのメモリ位置がプロセッサ間で共用されているわけではないことである。したがって、所与の位置が共用されているかどうかを確実に判定できる場合、順次整合性を維持するコストは大幅に削減されるだろう。
【００４８】
あるシステムのキャッシュ付きエミュレーションの場合、変換中の共用挙動を学習しても十分ではない。というのは、（ａ）命令が参照するアドレスが変換を実行するたびに変化する可能性があり、（ｂ）実行の進行中にアドレスによってその共用状況が変化する可能性があるからである。その位置の共用性を動的に決定するメカニズムについて、以下に説明する。
【００４９】
好ましくは、現在参照中の位置に関する情報を共有することにより、テーブルが維持される。テーブルのサイズを縮小するため、位置はまとめてグループ化される。おそらくより小さい他の単位を定義することができるが、便利なグループ化の１つはページ単位である。ページ単位が便利である理由は、ＩＢＭの整理番号ＹＯＲ９２００１０５３５ＵＳ１を有し、参照により本明細書に組み込まれる米国特許出願第１０／２４４,５５９号に記載されているようなページ・テーブルおよびローカル・ルックアサイド・バッファ（ＬＬＢ）内の保護およびマッピング情報の単位でもあるからである。各ページは以下にリストした５通りの状態の１つになる。
１．マッピングなし
２．排他読取り
３．排他書込み
４．共用読取り
５．共用書込み
【００５０】
あるページをページ・テーブルに取り込む前またはそれをページ・テーブルから排出した後、そのページは「マッピングなし」状態になる。あるプロセッサが読取りまたは書込みのためにそのページを要求すると、そのページは取り込まれる。したがって、そのページは、「排他読取り」または「排他書込み」のいずれかとしてページ・テーブル内に現れる。
【００５１】
各ページ・テーブル項目には、ＩＢＭの整理番号ＹＯＲ９２００１０５３５ＵＳ１を有し、参照により本明細書に組み込まれる前述の米国特許出願第１０／２４４,５５９号に記載されているようなローカル・ルックアサイド・バッファ（ＬＬＢ）にそのページがリストされているプロセッサのリストが関連付けられている。
【００５２】
この情報はルックアサイド・マスク・フィールド内にあり、たとえば、そのフィールドの５桁目にある１は、第５のプロセッサがそのＬＬＢのこのページを持っていることを示している。この記述は、図５のテーブル５００に示すように、あるプロセッサが読取りモードまたは書込みモードのいずれでそのページにアクセスしているかに関する情報を含むように変更される。
【００５３】
テーブル５００は、妥当性／状況ビット・フィールド５１０と、プロセスＩＤフィールド５２０と、仮想アドレス・フィールド５３０と、実アドレス・フィールド５４０と、保護ビット・フィールド５５０と、ルックアサイド・マスク・フィールド５６０と、読取り／書込みマスク・フィールド５７０と、アクセス・モード・フィールド５８０とを含む。
【００５４】
その後、あるプロセッサが、そのＬＬＢにはないが、ページ・テーブル５００にマッピングされているページへのアクセスを希望する場合、そのプロセッサはこのリスト（たとえば、プロセスＩＤフィールド５２０）に追加され、そのアクセス・モード（たとえば、フィールド５８０）が指定される。
【００５５】
この時点で、そのページの状態は、そのページにアクセスしているすべてのプロセッサが読取りモードのみでそれにアクセスできる場合は「共用読取り」に変更される。１つのプロセッサでもそのページに書込みアクセスできる場合は、そのページは「共用書込み」モードに設定される。この手順については図６の流れ図で説明する。
【００５６】
したがって、前述の通り、「共用書込み」状態を有するページが、本発明が考慮しなければならない主な焦点になる理由が示唆される。
【００５７】
さらに、前述の通り、ターゲット・システムが「順次整合性」（「強い」）をサポートし、ホストが「弱い」整合性をサポートすることなど、本発明によって所与の例示的な想定がなされている。
【００５８】
しかし、これは例示的なものにすぎず、間違いなく本発明はこれに限定されない。実際は、本発明は「強い」整合性と「弱い」整合性の数通りの組合せおよび順列をサポートすることに留意されたい。しかし、本発明者らは「弱」に「強」のシナリオが最も困難なケースであると認識しており、したがって、本明細書では主にこれについて述べる。その他のケース（たとえば、「強」に「強」、「弱」に「弱」、「強」に「弱」など）も同様に機能するが、より容易に機能する。
【００５９】
すなわち、「弱い」整合性をサポートするシステム上で「強い」整合性を有するシステムをエミュレートしようとすることは、最も困難なエミュレーション・ケースである。それが最も困難なケースである理由を示す極度に単純化した例を挙げるため、色々な人が書込みを行う黒板について検討する。「強い」整合性のケースでは、ある人が読取りを行う場合、その人は、他のすべての人がすでに書き込んだものをすべて見ることができなければならない。同様に、他の人が書込みを行う場合、その人は、書込みを始める前に他のすべての人が書込みを終了したことを確認する。これは、黒板への読取りおよび書込みの際に強いオーダが維持される「強い」整合性と呼ばれる。
【００６０】
「弱い」整合性（または「解放」整合性）のケースでは、それぞれの人は自分がそれを行いたいと希望するときに、いつでも書込みおよび読取りを行うことができる。この点については、その人は、自分がそれを変更する前に他の人がすでに読取り（または書込み）を行ったことを確認する必要はない。このようなケースでは、その人がそれを読み取る必要がある場合、他の人がもう一度その書戻し（たとえば、書き込まれたものの変更）を開
始する前にすでにその人がそれを読み取ったことを確認するのは、何らかの「教師」（たとえば、このケースでは何らかのプログラム）の責任である。人々は読取りと書込みを続けるので、これはより混沌とした状況になる。多くの従来のプロセッサは現在、このような「弱い」整合性モデルを使用している。というのは、それによって、プロセッサは共用する場合よりかなり高速になるからである。したがって、パフォーマンスの観点から見ると、「弱い」整合性モデルは、共用があまり行われないときには、より優れたモデルになる。
【００６１】
このため、いくつかの新型マシンでは、このようなモデルと動作モードを実現している。対照的に、より古い従来のマシンでは、動作が順次（ステップバイステップ式）である強い整合性を実現している。
【００６２】
したがって、予想されるように、非常に秩序ある動作モード（「強」）を取って、それを比較的無秩序の動作（たとえば、「弱」）に適用することは非常に困難なことである。対照的に、非常に無秩序の動作モード（「弱」）を取って、それを秩序ある動作（たとえば、「強」）に適用することは、単により多くの秩序をもたらすだけなので、より容易なことである。
【００６３】
したがって、「共用書込み」状態は最も重要なものである。あるページをシステムに取り込むと、システムは、そのページがどの状態を備えているかを決定することを希望する。そのページが「共用書込み」状態を備えている場合、テーブル５００の読取り／書込みマスク・フィールド５７０に決定し示すように、このような状態にフラグを立てる。すなわち、読取り／書込みマスクにより、そのページが「共用書込み」であるかどうかを識別することができる。アクセス・モード・フィールド５８０は、図５のテーブル５００に実際に存在するフィールドではないことに留意されたい。これは、読者が明快に理解できるようにするためにのみ示されており、単にルックアサイド・マスク５６０と読取り／書込みマスク５７０の組合せを調べることにより共用書込み状態を決定できることを記述しているだけである。
【００６４】
このため、図６に戻ると、方法６００は、あるページの共用状況を決定するための手順を対象とする。すなわち、図６は、本質的にルックアサイド・マスクと読取り／書込みマスクを調べ、ビット位置などを決定して状態を入手することにより、テーブル５００内の最後の列（たとえば、フィールド５８０）を決定するための技法を示している。
【００６５】
より具体的には、ステップ６１０で、ルックアサイド・マスクに複数のビットが設定されているかどうかを判定する。
【００６６】
ステップ６１０でルックアサイド・マスクに複数のビットが設定されていると判定された場合（たとえば、「ＹＥＳ」）、ステップ６２０で、読取り／書込みマスクに何らかのビットが設定されているかどうかを判定する。
【００６７】
ステップ６２０で読取り／書込みマスクにビット（複数も可）が設定されていると判定された場合（たとえば、「ＹＥＳ」）、ステップ６３０で、その状況を「共用書込み」に設定する。
【００６８】
ステップ６２０で読取り／書込みマスクにいずれのビット（複数も可）も設定されていないと判定された場合（たとえば、「ＮＯ」）、ステップ６４０で、その状況を「共用読取り」に設定する。
【００６９】
ステップ６１０でルックアサイド・マスクに複数のビットが設定されていないと判定された場合（たとえば、「ＮＯ」）、ステップ６５０で、読取り／書込みマスクに何らかのビットが設定されているかどうかを判定する。
【００７０】
ステップ６５０で読取り／書込みマスクにビット（複数も可）が設定されていると判定された場合（たとえば、「ＹＥＳ」）、ステップ６６０で、その状況を「排他書込み」に設定する。
【００７１】
ステップ６５０で読取り／書込みマスクにいずれのビット（複数も可）も設定されていないと判定された場合（たとえば、「ＮＯ」）、ステップ６７０で、その状況を「排他読取り」に設定する。次に、プロセスが終了する。
【００７２】
あるページの様々な共用メモリ状態間で起こり得る遷移を図７の部分状態マシン７００に示す。様々なメモリ状態としては、「マッピングなし」７１０と、「排他読取り」７２０と、「排他書込み」７３０と、「共用読取り」７４０と、「共用書込み」７５０を含む。図７の「ＬＲ」はローカル読取りであり、「ＬＷ」はローカル書込みであり、「ＲＲ」はリモート読取りであり、「ＲＷ」はリモート書込みであり、「Ｄ」は何らかのＬＬＢから脱落したページを示し、「ＰＯ」はページアウトされたページを示す。ページは、システムからページアウトされると、「マッピングなし」状態に戻ることができることに留意されたい。
【００７３】
「共用書込み」が最も関心のあることであっても、図７は、「共用書込み」状態に至る方法の１つとして、他の状態が必要であること（たとえば、注目すべき重要なこと）を示している。したがって、有限状態マシン７００では、共用書込み状態に至るために、そのページが他の状態の１つになり、共用書込み状態への経路を示す場合もある。このため、このような他の状態についても、部分状態マシン７００で注目する。
【００７４】
複数位置への書込みを行わない限り、記憶域の整合性の問題はまったく発生しない。すなわち、記憶域の整合性の問題は、複数の位置でその内容が変化する場合のみ発生する。所与の時点では、所与のターゲット・プロセッサの実行は正確に１つのホスト・プロセッサで行われるが、エミュレーションを実行するホスト・プロセッサそのものは、それぞれの時期にそれぞれ異なる可能性があるものと想定する。
【００７５】
たとえば、２つの個別プロセッサによって１つのターゲット命令の複数のオペランドを同時にフェッチすることは禁止される。また、一般的なマルチプログラム式システムの場合のように、暗黙的または明示的メモリ・バリアにはコンテキスト・スイッチが関連付けられているものと想定する。これにより、ある位置が共用されない限り、エミュレートされるターゲット・プロセッサのアクションがあるホスト・プロセッサから他のホスト・プロセッサに移行した場合でも、整合性の問題はまったく発生しないことが保証される。
【００７６】
上記の想定では、「共用書込み」状態になっているページに対して行われるアクセスのみに整合性の問題を限定する。したがって、すべてのこのようなアクセスの後にｍｂａｒ命令を続けるだけで十分である。
【００７７】
命令を一度に１つずつエミュレートするときに順次整合性を保証するための手順を図８の流れ図に示す。
【００７８】
すなわち、図８は、メモリ整合性、より具体的には、メモリ・バリア命令（複数も可）の挿入を保証する方法８００を示している。
【００７９】
まず、ステップ８０５では、その命令がロードまたはストアであるかどうかを判定する。メモリに影響する主な命令はロードとストアであるので、本発明は必ずしも他の命令に関連しない。
【００８０】
ステップ８０５でその命令がロードまたはストアではないと判定された場合（たとえば、「ＮＯ」）、プロセスはステップ８４０に移行し、そこで命令のエミュレーションを実行し、ステップ８７０でプロセスが完了する。
【００８１】
同じように、ステップ８０５でその命令がロードまたはストアであると判定された場合（たとえば、「ＹＥＳ」）、プロセスはステップ８１０に移行し、そこでアドレスを解明する。たとえば、ロード／ストア命令は通常、アドレスを作成するために、その命令によって指定された２つの数量を加算する必要がある。これらの数量がいずれも指定のレジスタ内に存在する場合もあれば、その数量の一方がその命令自体の１つのフィールドになっている場合もある。アドレスの解明とは、指定のレジスタがその内容の準備が整い、すでに加算が行われており、結果として得られる合計を実アドレスに変換するためにアドレス変換メカニズムが呼び出されたことを意味する。このため、「アドレスの解明」は、仮想アドレスを実アドレスに変換することになるだろう（たとえば、加算変位、仮想アドレス変換など）。
【００８２】
ステップ８１５では、そのアドレスがローカル・ルックアサイド・バッファ（ＬＬＢ）内にあるかどうかを判定する。そのアドレスがＬＬＢ内にない場合（たとえば、「ＮＯ」）、ステップ８２０でＬＬＢミスに関する手順（たとえば、グローバル・ページ・テーブルに移行することなど）を開始し、プロセスはステップ８１５にループバックする。
【００８３】
そのアドレスがＬＬＢ内にある場合（たとえば、「ＹＥＳ」）、ステップ８２５でその位置（たとえば、アドレス）が共用読取り状態になっているかどうかを判定する。
【００８４】
ステップ８２５でその位置（たとえば、アドレス）が共用読取り状態になっていると判定された場合（たとえば、「ＹＥＳ」）、プロセスはステップ８３０に進み、そこで現行アクセスが書込みであるかどうかを判定する。書込みではない場合（たとえば、「ＮＯ」）、ステップ８４０でその命令のエミュレーションを実行し、プロセスはステップ８７０で終了する。
【００８５】
ステップ８３０で現行アクセスが書込みであると判定された場合（たとえば、「ＹＥＳ」）、ステップ８４５でその位置を共用書込みに設定し、ステップ８５０でその命令のエミュレーションを実行し、ステップ８６０でｍｂａｒ命令をそこに置く。次にプロセスはステップ８７０で終了する。
【００８６】
同じように、ステップ８２５でその位置（たとえば、アドレス）が共用読取り状態になっていないと判定された場合（たとえば、「ＮＯ」）、プロセスはステップ８３５に進み、そこでその位置（たとえば、現行アドレス）が共用書込みであるかどうかを判定する。
【００８７】
ステップ８３５でその位置（アドレス）が共用書込み状態であると判定された場合、プロセスはステップ８５０に進み、そこでその命令のエミュレーションを実行し、ステップ８６０でｍｂａｒ命令をそこに置く。次にプロセスはステップ８７０で終了する。
【００８８】
したがって、ステップ８３０／８３５で、図８は本質的に、そのアドレスが共用書込みである可能性、またはそれがどこから来たかに応じて、その命令が共用書込みになる可能性の２通りを示している。この場合も、図７から明らかなように、共用書込みではない命令が、取られた経路に応じて、共用書込みになりうるケースがいくつかある。たとえば、「排他読取り」状態７２０は、図７に示すように、ローカル書込み（ＬＷ）またはリモート書込み（ＲＷ）を介して「共用書込み」７５０の状態に至る経路を有する。このため、共用書込み命令と、共用書込みになりうる命令（たとえば、書込み（ローカルまたはリモート）になる共用読取り７４０など）のために、ｍｂａｒ命令が必要になる。この場合も、共用読取り状態７４０では、ＬＷ，ＲＷを発行後、ｍｂａｒを挿入することになるだろう。共用書込みになるケースでは、同様にｍｂａｒのその他の挿入が実行されることになるだろう。
【００８９】
ターゲット・システム内の動作間でリオーダが許される（整合性の緩和）程度に応じて、さらにメモリ・バリア命令の数を削減することが可能になるだろう。
【００９０】
たとえば、システム／３９０では、単一命令の複数オペランドの読取り同士の順序付けを維持する必要はない。このため、システム／３９０のエミュレーションでは、このような読取り間に挿入されたｍｂａｒを排除することができ、それにより、第２の読取りの後にそれを保持することができる。
【００９１】
そのうえ、ある命令によって書き込まれる結果はその命令によって読み取られるオペランドに依存しているので、１つの３９０命令において複数オペランドの読取りとメモリへの結果の書込みとの間のｍｂａｒを排除することができ、書込みの後にそれを保持することができる。
【００９２】
上記の説明では、エミュレートしたメモリ参照のプログラム・オーダが、ターゲット・システムによって実行されたと思われるメモリ参照のプログラム・オーダと同一であると想定する。いくつかの既知の例（たとえば、参照により本明細書に組み込まれる米国特許
第６０３１９９２号を参照）に記述されているように、まとめて変換すべき複数命令のグループについて検討し、変換したグループについて最適化を実行することにより、エミュレーション・パフォーマンスを改善することが可能な場合が多い。
【００９３】
しかし、このような最適化では、そのグループについて好都合なスケジュールを見つけようとして、命令を移動し、それらをリオーダする傾向がある。エミュレートした参照のそれぞれの後にｍｂａｒ命令を続ける場合でも、このようなリオーダは、マルチプロセッサ環境で実行したときに整合性の要件に違反する可能性がある。
【００９４】
図９を参照すると、本発明は、このようなリオーダが存在する場合でもエミュレーション中にメモリ動作で必要な整合性を維持するための方式を提供する。すなわち、図９は、複数の命令が１つずつ変換される図８の状況とは異なり、まとめて変換すべき複数命令のグループが存在する状況を対象とする。複数の命令をグループとしてまたは１つずつ変換できるような上記の状況の組合せが発生する可能性があることに留意されたい。このため、グループの状況では、複数参照の組合せが存在する可能性があり、そのうちの一部は共用書込みであり、一部は共用書込みではない。
【００９５】
簡単にするため、元の命令シーケンスは単一の入口と複数の出口を備えた複数命令の順次ストリームであり、各出口が変換済みシーケンスからの条件付き分岐に対応するものと想定する。
【００９６】
また、このシーケンス内の各命令はせいぜい１回実行される（すなわち、その変換内の他の命令にループバックする分岐はまったくない）ものと想定する。最後に、ターゲット命令セット内のメモリ参照はレジスタとメモリとの間のロードとストアのみであるものと想定する。（この最後の想定はいずれにしても限定的なものではない。というのは、より複雑なＣＩＳＣスタイルの命令は、このようなロードおよびストア命令を含む、適切な命令シーケンスに分解できるからである。）
【００９７】
図９では、まず、変換の先頭にスタブ・コードを付加し、潜在的にグループ内の命令によって変更されるターゲット・プロセッサのすべてのレジスタを保管する。そのグループの推測変換を取り消す必要がある場合には、このチェックポイントは有利なものになる。
【００９８】
次に、その命令グループ内の各ロードと各ストアは、（ａ）一連のメモリ参照内のその位置を示すメモリ順序番号と、（ｂ）一連のストア参照サブセット内のその位置を示すストア順序番号を含む、２つの数に関連付けられる。
【００９９】
次に、図９に示すように、メモリ・オーダ・バッファ（ＭＯＢ）と呼ばれるテーブル９００が構築され、その各項目は、それがロードであるかまたはストアであるかの表示９１０と、参照のアドレス９２０と、参照の長さ９３０と、参照に関連する値９４０（ロードの場合はロード値または仮定値、ストアの場合はメモリに記憶すべき値）とを含む、４つのフィールドを有する。したがって、テーブル９００内のロード／ストアの数を調べると、参照のうちの３つは共用書込みであり、２つは共用書込みではない。
【０１００】
テーブル内の項目の数はシーケンス内のメモリ参照の数に等しい。図１０は、ターゲット・コード１０１０と、エミュレーション・コード１０２０と、図９のテーブル９００を示している。すなわち、メモリ参照の順序番号は、図１０の構成１０００に示されるようにテーブル９００への索引である。このため、共用メモリ・アクセスは、図９のＭＯＢにマッピングされる。
【０１０１】
そのうえ、図１１の構成１１００に示すように、ストア参照の数と同数の項目を含むストア回復テーブル（ＳＲＴ）１１１０が構築され、その各項目は、図１１に示すようにアドレス・フィールドと旧値フィールドを含む２つのフィールドを含んでいる。したがって、図１１では、ストアは回復のためにＳＲＴ１１１０に保管される。テーブル１１１０は、たとえば、問題が発生したときに有用である。
【０１０２】
たとえば、他の人がすでに読み取ったものを誰かが書き込んで、すでに書き込まれているべきものが（「古い」ものではなく）「新しい」ものであるときに、問題が発生する可能性がある。その結果、すべての計算が間違ってしまう。このような場合、値を元に戻すことが役に立つだろう。しかも、一部の計算は実際にメモリに記憶されている可能性があり、これらの位置を前の値にリセットする（たとえば、それぞれの元の内容に戻す）ことが望ましい。このため、テーブル１１１０は問題を修正するためのアドレスと値を記憶するので、そのテーブルの使用は役に立つことである。
【０１０３】
より具体的には、システムは問題を感知し、それが正しかった時期まで戻り、その値を復元しなければならない。ループバックし、ストアのそれぞれを一度に１つずつ経て（たとえば、好ましくは、最後のチェックポイントの後に最後のストアを先に実行する）、その位置と、旧値が何であったかを決定することにより、このような動作を実行する。次に、旧値をそこに挿入する。
【０１０４】
それぞれのメモリ参照の変換時には、図１２に示す形式を有するコードが含まれる。
【０１０５】
すなわち、図１２の方法１２００では、ＭＯＢ９００とＳＲＴ１１１０を使用して複数命令のグループ内の整合性を維持するためにコードを挿入する。
【０１０６】
具体的には、まず、ステップ１２０５で、その命令がロードまたはストアであるかどうかを判定する。この場合も、メモリに影響する主な命令はロードとストアであるので、本発明は必ずしも他の命令に関連しない。
【０１０７】
ステップ１２０５でその命令がロードまたはストアではないと判定された場合（たとえば、「ＮＯ」）、プロセスはステップ１２４０に移行し、そこでその命令のエミュレーションを実行し、ステップ１２９０でプロセスが完了する。
【０１０８】
同じように、ステップ１２０５でその命令がロードまたはストアであると判定された場合（たとえば、「ＹＥＳ」）、プロセスはステップ１２１０に移行し、そこでアドレスを解明する。このステップは、図８に関して前述したステップ８１０と同様のものである。
【０１０９】
ステップ１２１５では、そのアドレスがローカル・ルックアサイド・バッファ（ＬＬＢ）内にあるかどうかを判定する。そのアドレスがＬＬＢ内にない場合（たとえば、「ＮＯ」）、ステップ１２２０でＬＬＢミスに関する手順（たとえば、グローバル・ページ・テーブルに移行することなど）を開始し、プロセスはステップ１２１５にループバックする。
【０１１０】
そのアドレスがＬＬＢ内にある場合（たとえば、「ＹＥＳ」）、ステップ１２２５でその位置（たとえば、アドレス）が共用読取り状態になっているかどうかを判定する。
【０１１１】
ステップ１２２５でその位置（たとえば、アドレス）が共用読取り状態になっていると判定された場合（たとえば、「ＹＥＳ」）、プロセスはステップ１２３０に進み、そこで現行アクセスが書込みであるかどうかを判定する。それが書込みではない場合（たとえば、「ＮＯ」）、ステップ１２４０でその命令のエミュレーションを実行し、プロセスはステップ１２９０で終了する。
【０１１２】
ステップ１２３０で現行アクセスが書込みであると判定された場合（たとえば、「ＹＥＳ」）、ステップ１２４５でその位置を共用書込みに設定し、ステップ１２５０で現行アクセスがロード命令であるかどうかを判定する。
【０１１３】
ステップ１２５０で現行アクセスがロードであると判定された場合（たとえば、「ＹＥＳ」）、ステップ１２５５でロードを実行し、そのロードがＭＯＢにより満足されているかどうか（たとえば、そのロード／アドレスがそれ以前にＭＯＢ内に発生したか）を判定する。そのロードが満足されている場合、動作はステップ１２７０で終了する。
【０１１４】
ステップ１２５５でそのロードがＭＯＢにより満足されていない場合（たとえば、「ＮＯ」）、プロセスはステップ１２６０に進む。ステップ１２６０では、メモリ順序番号によって索引が付けられたＭＯＢに項目を挿入し、プロセスはステップ１２９０で終了する。
【０１１５】
ステップ１２５０で現行アクセスがロードではないと判定された場合（たとえば、「ＮＯ」）、ステップ１２６０でメモリ順序番号によって索引が付けられたＭＯＢに項目を挿入し、プロセスはステップ１２９０で終了する。
【０１１６】
同じように、ステップ１２３５に戻ると、その位置（アドレス）が共用書込み状態ではないと判定された場合（たとえば、「ＮＯ」）、プロセスはステップ１２６５に進み、そこでそのアクセスが書込みであるかどうかを判定する。
【０１１７】
ステップ１２６５でそのアクセスが書込みではない場合（たとえば、「ＮＯ」）、プロセスはステップ１２４０に進み、そこでその命令のエミュレーションを実行し、ステップ１２９０でプロセスが終了する。
【０１１８】
同じように、ステップ１２６５でアクセスが書込みであると判定された場合（たとえば、「ＹＥＳ」）、プロセスはステップ１２７０に進み、その時点でその位置の旧値を読み取る。次に、ステップ１２７５でストアを実行し、ステップ１２８０でストア順序番号によって索引が付けられたＳＲＴにその旧値を挿入する。その後、ステップ１２９０でプロセスが終了する。
【０１１９】
したがって、図１２に示すように、このコードは、参照した位置に対応するページが「共用書込み」であるかどうかを判定し、そうである場合にスタブ・コードに分岐する。
【０１２０】
このスタブ・コードは、メモリ参照の順序番号を使用してＭＯＢに索引を付け、（ａ）それがロードまたはストアであるかどうかと、（ｂ）参照のアドレスを記録する。参照がストアである場合、それは記憶すべき値も記録する。参照がロードである場合、それはロードを実行し、ロードした値を記録する。
【０１２１】
特殊なケースとしては、変換時に前のストアのターゲットであった共用書込み位置へのロードがある。この場合、ロードはＭＯＢからその内容を受け取らなければならず、ロード自体はＭＯＢに記録されない。
【０１２２】
参照が「共用書込み」位置に対するものではなく、それがストアである場合、ストアが実行される前に、その位置の旧値が読み取られ、ＳＲＴに記録される。
【０１２３】
このスタブ・コードは最適化にかけられ、変換の残りとともにリオーダ可能であることに留意されたい。変換の終了時に、他のいかなるプロセッサもこのブロックがアクセスした「共用書込み」位置への値を変更していないことをチェックして保証するための他のスタブが追加される。
【０１２４】
これは、まず他のプロセッサによるアクセスから共用メモリ位置をロックすることにより、図１３に示すように行われる。各ロード位置は再ロードされ、対応するＭＯＢ項目内に記憶された値と比較される。すべての再ロードが元のロードと同じであると判明した場合、ＭＯＢからのすべてのストアをメモリ内のそれぞれの実際の位置にコミットしても差し支えない。
【０１２５】
ロード妥当性検査プロセス中に不一致が発生した場合、そのグループの実行全体が取り消される。これは、すべてのレジスタをそれぞれの旧状態に復元し、ＳＲＴ内の操作をアンドゥすることによって非「共用書込み」位置に対して行ったストアを逆転することにより実施される。システムが前に有効だった状態に戻ると、実行が再試行される。１つのグループ内での実行／取消しサイクルの繰返しを回避するため、解釈モードまたは単純変換モードのいずれかを使用して、一度に１つずつ、再実行を行うことができる。
【０１２６】
このため、図１３は計算の終了を示し、したがって、複数命令のグループをまとめて変換した後、すべての命令が実行された後であって、すべてをメモリに保管してしまう前に、計算を実行しながら、何も変化していないことを保証することが望ましい。すなわち、そのグループの実行中に他のプロセッサによって変更が行われた可能性があり、本発明では、このような変更が現在エミュレートしているプロセッサの値／命令に影響しないことを保証する必要がある。
【０１２７】
したがって、グループ実行の終了時に共用書込みをメモリにコミットするための図１３のプロセス１３００をステップごとに調べると、まず、ステップ１３０５では、共用メモリ位置へのアクセスをロックする。
【０１２８】
次にステップ１３１０ではＭＯＢ内の第１の項目にポインタを設定し、ステップ１３１５ではＭＯＢの終わりに達したかどうかを判定する。ステップ１３１５の後のプロセスの左側はロードを対象とし、ステップ１３１５の後のプロセスの右側はストアを対象とすることに留意されたい。
【０１２９】
ステップ１３１５で「ＮＯ」の場合、ステップ１３２０でＭＯＢ内のその項目が空であるかどうかを判定する。（ステップ１３２０で「ＹＥＳ」の場合、プロセスはステップ１３４０に移行する。）
【０１３０】
次にステップ１３２５では、その項目がロードであるかどうかを判定する。ステップ１３２５で「ＮＯ」の場合、ステップ１３４０でＭＯＢへのポインタを増分し、ステップ１３１５にループバックする。
【０１３１】
同じように、ステップ１３２５でその項目がロードであると判定された場合（たとえば、「ＹＥＳ」）、ステップ１３３０でその項目内のアドレスからその項目を再ロードする。ステップ１３３５では、再ロードした値がその項目内の値と一致するかどうかを判定する。
【０１３２】
ステップ１３３５で「ＹＥＳ」の場合、ステップ１３４０でＭＯＢへのポインタを増分し、ステップ１３１５にループバックする。
【０１３３】
ステップ１３３５で「ＮＯ」の場合、ステップ１３４５でロックを解除し、ステップ１３５０では、状態を復元し、ＳＲＴを使用して非共用書込みを復元することにより、そのグループの先頭まで回復を実行する。この時点で、エミュレートしたプログラム・カウンタがそのグループの先頭までリセットされ、実行のプロセスが再試行される。
【０１３４】
同じように、ステップ１３１５で「ＹＥＳ」の場合、プロセスはステップ１３５５に移行し、そこでＭＯＢ内の第１の項目にポインタを設定する。ステップ１３６０では、ＭＯＢの終わりに達したかどうかを判定する。
【０１３５】
「ＮＯ」の場合、ステップ１３６５でＭＯＢ内のその項目が空であるかどうかを判定する。（ステップ１３６５で「ＹＥＳ」の場合、プロセスはステップ１３８０に移行する。）
【０１３６】
次にステップ１３７０では、ＭＯＢ内のその項目がストアであるかどうかを判定する。その項目がストアである場合（たとえば、「ＹＥＳ」）、ステップ１３７５でその値をメモリに書き込み、ステップ１３８０でＭＯＢ内のポインタを増分し、プロセスはステップ１３６０にループバックする。
【０１３７】
ステップ１３７０の結果が「ＮＯ」である場合、プロセスはステップ１３８０に進み、次にステップ１３６０にループバックする。ステップ１３６０で「ＹＥＳ」の場合、ステップ１３８５でロックを解除し、プロセスはステップ１３９０で完了する。
【０１３８】
したがって、前述の通り、本発明は、複数命令を１つずつ通過するか、またはＭＯＢとＳＲＴを使用することによって命令グループを処理することができる。
【０１３９】
図１４は、本発明で使用するためのものであり、好ましくは少なくとも１つのプロセッサまたは中央演算処理装置（ＣＰＵ）１４１１を有する情報処理／コンピュータ・システムの典型的なハードウェア構成を示している。
【０１４０】
ＣＰＵ１４１１は、システム・バス１４１２を介して、ランダム・アクセス・メモリ（ＲＡＭ）１４１４、読取専用メモリ（ＲＯＭ）１４１６、入出力（Ｉ／Ｏ）アダプタ１４１８（ディスク装置１４２１およびテープ・ドライブ１４４０などの周辺装置をバス１４１２に接続するためのもの）、ユーザ・インタフェース・アダプタ１４２２（キーボード１４２４、マウス１４２６、スピーカ１４２８、マイクロホン１４３２、またはその他のユーザ・インタフェース装置、あるいはそれらの組合せをバス１４１２に接続するためのもの）、情報処理システムをデータ処理ネットワーク、インターネット、イントラネット、パーソナル・エリア・ネットワーク（ＰＡＮ）などに接続するための通信アダプタ１４３４、バス１４１２をディスプレイ装置１４３８またはプリンタ１４３９（たとえば、ディジタル・プリンタなど）あるいはその両方に接続するためのディスプレイ・アダプタ１４３６に相互接続されている。
【０１４１】
上記のハードウェア／ソフトウェア環境に加え、本発明の他の態様では、上記の方法を実行するためのコンピュータ実現方法を含む。一例として、この方法は前述の特定の環境で実現することができる。
【０１４２】
このような方法は、たとえば、ディジタル・データ処理装置によって実施されるように、一連の機械可読命令を実行するようにコンピュータを操作することにより実現することができる。このような命令は、様々なタイプの信号運搬媒体に存在することができる。
【０１４３】
したがって、本発明のこの態様は、本発明の方法を実行するために、ＣＰＵ１４１１および上記のハードウェアを取り入れたディジタル・データ・プロセッサにより実行可能な複数の機械可読命令からなるプログラムを具体的に実施する信号運搬媒体を含む、プログラムによる製品を対象とする。
【０１４４】
この信号運搬媒体は、たとえば高速アクセス記憶装置によって代表されるように、たとえばＣＰＵ１４１１内に含まれるＲＡＭを含むことができる。別法として、ＣＰＵ１４１１によって直接または間接的にアクセス可能な磁気データ記憶ディスケット１５００（図１５）などの他の信号運搬媒体に命令を含めることもできる。
【０１４５】
ディスケット１５００に含まれるか、コンピュータ／ＣＰＵ１４１１またはその他の場所に含まれるかにかかわらず、ＤＡＳＤ記憶装置（たとえば、従来の「ハード・ドライブ」またはＲＡＩＤアレイ）、磁気テープ、電子読取専用メモリ（たとえば、ＲＯＭ、ＥＰＲＯＭ、またはＥＥＰＲＯＭ）、光学記憶装置（たとえば、ＣＤ−ＲＯＭ、ＷＯＲＭ、ＤＶＤ、ディジタル光学テープなど）、紙の「パンチ」カードなどの様々な機械可読データ記憶媒体、またはディジタルおよびアナログ通信リンクならびに無線などの伝送媒体を含むその他の適当な信号運搬媒体上に命令を記憶することができる。本発明の例証となる一実施形態では、機械可読命令は、「Ｃ」などの言語からコンパイルされたソフトウェア・オブジェクト・コードを含むことができる。
【０１４６】
本発明の固有かつ自明ではない諸態様により、マルチプロセッシング・システム上でエミュレートされる複数のプロセッサによりクリティカル・セクションのエミュレーションを効率よく実行することができる。すなわち、本発明は、種々のプロセッサについて同時にクリティカル・セクションをエミュレートしているときに、このようなクリティカル・セクションに入るプロセッサをエミュレートすることができる。この場合も、これまでは、エミュレーションが伝統的にユニプロセッサ上で実行されていたので、このような問題は検出されていなかった。この点については、本発明者らは、このような問題を認識し、上記の固有かつ自明ではない解決策を考案した最初の者である。さらに、本発明は前述のメモリ整合性を保証することができる。
【０１４７】
いくつかの好ましい実施形態に関して本発明を説明してきたが、当業者であれば、特許請求の範囲の精神および範囲内で変更を加えて本発明を実施できることが分かるだろう。
【０１４８】
さらに、本出願人の意図は、権利請求中に後日補正された場合でも、すべての特許請求の範囲と同等のものを包含することであることに留意されたい。
【符号の説明】
【０１４９】
２０１、４３０Ａ  プロセッサ１
２０２、４３０Ｂ  プロセッサ２
１４１８  Ｉ／Ｏアダプタ
１４２２  ユーザ・インタフェース・アダプタ
１４３４  通信アダプタ
１４３６  ディスプレイ・アダプタ
１４３９  プリンタ
【図１】
2010182331.tif 000003
【図２】
2010182331.tif 000004
【図３】
2010182331.tif 000005
【図４】
2010182331.tif 000006
【図５】
2010182331.tif 000007
【図６】
2010182331.tif 000008
【図７】
2010182331.tif 000009
【図８】
2010182331.tif 000010
【図９】
2010182331.tif 000011
【図１０】
2010182331.tif 000012
【図１１】
2010182331.tif 000013
【図１２】
2010182331.tif 000014
【図１３】
2010182331.tif 000015
【図１４】
2010182331.tif 000016
【図１５】
2010182331.tif 000017