(57)【要約】  あるスレッドのストア処理でキャッシュＲＡＭ２１上のデータが書き換えられると，アドレス一致判定回路２５は，他のスレッドの要求を保持するフェッチポート２２を検索し，処理完了済みであり，ロード系の命令であり，かつその命令の対象アドレスがストア処理の対象アドレスと一致する要求があるかをチェックし，該当する要求が検出されれば，最も古い要求を保持するエントリの次から前記検出された要求を保持するエントリまでのフェッチポート２２のすべてのエントリに，ストアによる命令再実行要求フラグをセットする。命令再実行要求回路２６は，前記最も古い要求の処理が行われると，ストアによる命令再実行要求フラグがセットされているエントリに保持された要求について，命令制御部１０に対して命令の再実行要求を送る。これにより，ＳＭＴのプロセッサにおいてスレッド間のデータ更新の順序性を保証する。
2008155829.tif 000002
【特許請求の範囲】
【請求項１】
一連の命令の実行単位であるスレッドを制御する命令制御部と，キャッシュメモリを有するキャッシュ制御部とを備え，メモリアクセスを行うストア命令とロード命令とをアウトオブオーダーで処理し，前記スレッドを複数同時に実行する機能を持つ情報処理装置において，
前記キャッシュ制御部は，
あるスレッドにより前記キャッシュメモリへのストア命令の処理が実行された場合に，先行するロード命令と後続のロード命令とを有する他のスレッドによって，前記ストア命令の対象アドレスのデータに対する前記後続のロード命令が前記先行するロード命令の処理より先に実行され，その後続のロード命令の対象データが前記ストア命令の処理より先に前記命令制御部に返されたか否かを判定する判定回路と，
前記判定回路により前記対象データが前記ストア命令の処理より先に前記命令制御部に返されたと判定された場合に，前記先行するロード命令を処理するとき，前記先行するロード命令の次の命令から前記後続のロード命令までの命令の再実行を前記命令制御部に要求する命令再実行要求回路とを備える
ことを特徴とする情報処理装置。
【請求項２】
メモリアクセスをアウトオブオーダーで処理し，一連の命令の実行単位であるスレッドを複数同時に実行する機能を持つ情報処理装置において用いられる，キャッシュメモリを有するキャッシュメモリ制御装置において，
あるスレッドにより前記キャッシュメモリへのストア命令の処理が実行された場合に，先行するロード命令と後続のロード命令とを有する他のスレッドによって，前記ストア命令の対象アドレスのデータに対する前記後続のロード命令が先行するロード命令の処理より先に実行され，その後続のロード命令の対象データが前記ストア命令の処理より先に前記命令制御部に返されたか否かを判定する判定回路と，
前記判定回路により前記対象データが前記ストア命令の処理より先に前記命令制御部に返されたと判定された場合に，前記先行するロード命令を処理するとき，前記先行するロード命令の次の命令から前記後続のロード命令までの命令の再実行を前記命令制御部に要求する命令再実行要求回路とを備える
ことを特徴とするキャッシュメモリ制御装置。
【請求項３】
キャッシュメモリと，
一連の命令の実行単位であるスレッドごとに，前記キャッシュメモリに対するアクセス要求を保持する複数のエントリを有し，その各エントリに，保持するアクセス要求の処理が完了しているか否かを示す状態フラグと，命令種別情報と，その命令の対象アドレスと，ストア命令の発行による命令再実行要求フラグとを少なくとも有するフェッチポートと，
前記フェッチポートごとに，前記フェッチポートのエントリのうち最も古いアクセス要求を保持するエントリを示す情報を保持するキューレジスタと，
前記ストア命令によって前記キャッシュメモリ上のデータが書き換えられたときに，前記ストア命令を発行したスレッド以外のスレッドに対応する前記フェッチポートを検索し，命令種別情報がロード系の命令であり，状態フラグが処理完了済みであり，かつ命令の対象アドレスが受け取ったアドレスと一致するアクセス要求が格納されたエントリが検出された場合に，前記キューレジスタが示すエントリまたはその次のエントリから前記検出されたエントリまでの各エントリにおける前記ストア命令による命令再実行要求フラグをセットするアドレス一致判定回路と，
前記キューレジスタで示されているアクセス要求の処理が行われるときに，前記ストア命令による命令再実行要求フラグがセットされているエントリに保持されたアクセス要求について，命令を発行したアクセス要求元へ命令の再実行要求を送る命令再実行要求回路とを備える
ことを特徴とするキャッシュメモリ制御装置。
【請求項４】
一連の命令の実行単位であるスレッドを制御する命令制御部と，キャッシュメモリを有するキャッシュ制御部とを備え，メモリアクセスを行うストア命令とロード命令とをアウトオブオーダーで処理し，前記スレッドを複数同時に実行する機能を持つ情報処理装置における，メモリにアクセスする命令の順序に関する予め定められた制約を保証するスレッド間のメモリアクセス順序保証方法であって，
あるスレッドにより前記キャッシュメモリへのストア命令の処理が実行された場合に，先行するロード命令と後続のロード命令とを有する他のスレッドによって，前記ストア命令の対象アドレスのデータに対する前記後続のロード命令が前記先行するロード命令の処理より先に実行され，その後続のロード命令の対象データが前記ストア命令の処理より先に前記命令制御部に返されたか否かを判定するステップと，
前記対象データが前記ストア命令の処理より先に前記命令制御部に返されたと判定された場合に，前記先行するロード命令を処理するとき，前記先行するロード命令の次の命令から前記後続のロード命令までの命令の再実行を前記命令制御部に要求する命令再実行要求ステップとを有する
ことを特徴とするメモリアクセス順序保証方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は，メモリアクセスをアウトオブオーダーで処理するＳＭＴ（Simultaneous Multi Thread ）のプロセッサに関するものであり，特に，あるスレッドで実行されるストア処理の順序性が，同一プロセッサ内の他スレッドで実行されるロード処理に反映されることを保証するＳＭＴにおけるスレッド間のＴＳＯ保証方式に関するものである。
【背景技術】
【０００２】
ＴＳＯ（Total Store Ordering）とは，メモリにアクセスする命令の順序に対して，実際にメモリに書き込む順序の入れ替えの制約が定められたメモリオーダリング（memory ordering ）の一つである。ＴＳＯのルールは，次の三点である。
１．ロード命令は，先行するロード命令を追い越して処理してはいけない。
２．ストア命令は，先行するロード命令と先行するストア命令を追い越して処理してはいけない。
３．アトミックロードストア命令は，先行するロード命令と先行するストア命令を追い越して処理してはいけない。アトミックロードストア命令は，その命令により対象データがロードされてからストアされるまでの間，その対象データへの他からのアクセスを制限しなければならない命令である。【０００３】
図９は，ＴＳＯによって保証しなければならないロード命令／ストア命令間の追い越し可否パターンを示す図である。＃１に示すように，ロード命令は先行するロード命令を追い越して処理することはできない。＃２に示すように，ストア命令は先行するロード命令を追い越して処理することはできない。＃３に示すように，ロード命令は先行するストア命令を追い越して処理することができる。＃４に示すように，ストア命令は先行するストア命令を追い越して処理することができない。【０００４】
つまり，ロード命令は先行するストア命令を追い越して処理してもよいが，その他のパターンの追い越しは禁止となる。ただし，ロード命令の対象となるデータが先行するストア命令の対象となるデータに含まれている場合には，ロード命令は先行するストア命令のデータをロードしなければならない。【０００５】
ここで，メモリアクセスをアウトオブオーダーで処理するプロセッサでは，後続のロード命令が先行するロード命令を追い越して処理を行い，先にデータを命令制御部に返すことを可能とする。【０００６】
図１０は，アウトオブオーダー処理を行うプロセッサにおけるロード命令同士の追い越しの例を説明する図である。アウトオブオーダー処理を行うプロセッサにおいて，命令制御部１００は，キャッシュ制御部２００にロード命令ｌｏａｄ−Ａを発行する。ｌｏａｄ−Ａの対象となるデータがキャッシュミスすると，キャッシュ制御部２００は，外部の記憶手段に対して該当データを要求する。【０００７】
続けて，命令制御部１００は，キャッシュ制御部２００にロード命令ｌｏａｄ−Ｂを発行する。ロード命令ｌｏａｄ−Ｂの対象となるデータがキャッシュヒットすると，キャッシュ制御部２００は，先行するｌｏａｄ−Ａの処理を追い越して後続のロード命令ｌｏａｄ−Ｂの処理を行い，ロード命令ｌｏａｄ−Ｂの対象となるデータｄａｔａ−Ｂを命令制御部１００に返す。【０００８】
その後，キャッシュ制御部２００は，外部の記憶手段からデータ転送を受けると，ロード命令ｌｏａｄ−Ａの処理を行い，ロード命令ｌｏａｄ−Ａの対象となるデータｄａｔａ−Ａを命令制御部１００に返す。【０００９】
このように，アウトオブオーダー処理では，命令の順序通りにキャッシュからのデータの読み出しが行われるとは限らない。しかし，命令制御部１００では実際には順序通りに命令が実行されるため，データを順不同で読み出したとしても，ロード／ストア間のＴＳＯさえ守っていれば，単一スレッドにのみ対応するプロセッサの場合，ソフトウェアからはＴＳＯが守られているように見える。【００１０】
ところが，ＳＭＴのプロセッサでは，同時に実行される複数のスレッドが一次キャッシュを共有するため，一つのプロセッサ内のスレッド間でのＴＳＯ違反の回避が必要となる。【００１１】
ＳＭＴ（Simultaneous Multi Thread ）とは，単一のＣＰＵで複数のスレッドを同時実行する技術である。すなわち，ＳＭＴのプロセッサは，複数のスレッドを同時実行する機能を備えたプロセッサである。ＳＭＴのプロセッサに関する先行技術が記載された文献として，例えば特許文献１などがある。特許文献１には，スレッド間での共有データの読み出しおよび書き込みの実行順序の一貫性を保証する技術が記載されている。
【特許文献１】ＷＯ２００４／０６８３６１号公報
【発明の開示】
【発明が解決しようとする課題】
【００１２】
図１１〜図１３は，ＳＭＴ構成におけるＴＳＯ違反の例を説明する図である。図１１〜図１３に示す例において，命令制御部１００から一次キャッシュ制御部２００に発行されたロード命令／ストア命令等のメモリアクセス要求は，複数のエントリからなるＦＰ（Fetch Port）２２０に一旦保持される。ここでは，説明の便宜上プロセッサ内のスレッド数を２とし，スレッドごとにそれぞれＦＰ２２０が備えられているものとする。命令制御部１００から発行された命令は，ＦＰ２２０のエントリに命令の実行順序に従って循環して割り当てられる。ＦＰ２２０に保持された要求はアウトオブオーダーで読み出され，処理可能な要求からその対象データを命令制御部１００に返すことが可能である。【００１３】
ここでは，キャッシュＲＡＭ２１０上にデータが存在しない領域Ａ，キャッシュＲＡＭ２１０上にデータが存在する領域Ｂに対して，プロセッサ内のあるスレッド（ｔｈｒｅａｄ−α）では，命令制御部１００からｓｔｏｒｅ−Ａ，ｓｔｏｒｅ−Ｂの順で一次キャッシュ制御部２００に命令が発行され，同一プロセッサ内の別のスレッド（ｔｈｒｅａｄ−β）では，命令制御部１００からｌｏａｄ−Ｂ，ｌｏａｄ−Ａの順で一次キャッシュ制御部２００に命令が発行されるケースについて説明する（図１１参照）。【００１４】
ｔｈｒｅａｄ−αで発行されたｓｔｏｒｅ−Ａ，ｓｔｏｒｅ−Ｂは順にＦＰ２２０αに保持され，ｔｈｒｅａｄ−βで発行されたｌｏａｄ−Ｂ，ｌｏａｄ−Ａは順にＦＰ２２０βに保持される。なお，図において，各ＦＰ２２０に保持された命令の左側に表記された数字は，各エントリを示す番号である。【００１５】
一次キャッシュ制御部２００では，まず，ｔｈｒｅａｄ−βで発行された命令から処理が行われるものとする。ｔｈｒｅａｄ−βにおいて先行するｌｏａｄ−ＢでキャッシュＲＡＭ２１０の領域Ｂにアクセスすると，キャッシュＲＡＭ２１０には領域Ｂのデータが存在しないのでキャッシュミスとなり，二次キャッシュ制御部３００に対して該当データの要求を行う。【００１６】
二次キャッシュ制御部３００に対してｌｏａｄ−Ｂの対象データを要求している間に，後続のｌｏａｄ−ＡでキャッシュＲＡＭ２１０の領域Ａにアクセスすると，キャッシュヒットとなり，得られたｄａｔａ−Ａ（ｏｌｄ）を命令制御部１００に返す。なお，図中，領域Ａのデータがｏｌｄと表記されているのは，後のｓｔｏｒｅ−Ａの処理によって書き換えられたデータと比較して古いデータであることを示している。【００１７】
その後，図１２に示すように，二次キャッシュ制御部３００から転送された領域ＢのデータがキャッシュＲＡＭ２１０に到着する。ここで，一次キャッシュ制御部２００では，ｔｈｒｅａｄ−βのｌｏａｄ−Ｂの再処理を行う前に，ｔｈｒｅａｄ−αで発行された命令から処理が行われるものとする。ｓｔｏｒｅ−Ａ，ｓｔｏｒｅ−ＢでキャッシュＲＡＭ２１０の領域Ａ，領域Ｂにアクセスすると，共にキャッシュヒットとなり，キャッシュＲＡＭ２１０の領域Ａ，領域Ｂのデータが更新される。なお，図中，領域Ａ，領域Ｂのデータがｎｅｗと表記されているのは，ｓｔｏｒｅ−Ａ，ｓｔｏｒｅ−Ｂの処理によって書き換えられる前のデータと比較して新しいデータであることを示している。【００１８】
その後，一次キャッシュ制御部２００では，ｔｈｒｅａｄ−βのｌｏａｄ−Ｂの再処理が行われる。ｌｏａｄ−ＢでキャッシュＲＡＭ２１０の領域Ｂにアクセスすると，キャッシュヒットとなり，得られたｄａｔａ−Ｂ（ｎｅｗ）を命令制御部１００に返す（図１３参照）。【００１９】
この結果，ｔｈｒｅａｄ−αでｓｔｏｒｅ−Ａ，ｓｔｏｒｅ−Ｂの順に命令が発行されたにもかかわらず，ｔｈｒｅａｄ−βでは，ｌｏａｄ−Ｂの処理ではストア済みデータを，ｌｏａｄ−Ａの処理ではストア前データを返したことになり，ＴＳＯにおけるロード命令／ロード命令間の追い越し禁止に違反したことになってしまう。【００２０】
本発明は，上記の問題点の解決を図り，メモリアクセスをアウトオブオーバーで処理するＳＭＴのプロセッサにおいて，あるスレッドで実行されるストア処理の順序性が，同一プロセッサ内の他スレッドで実行されるロード処理に反映されることを保証する技術を提供することを目的とする。
【課題を解決するための手段】
【００２１】
本発明は，上記課題を解決するため，複数のスレッドを同時実行するＳＭＴのプロセッサにおいて，あるスレッドで後続のロード命令の処理が先行するロード命令の処理より先に実行され，後続のロード命令の対象データが先に命令制御部に返された場合に，そのデータに対するストア処理が別のスレッドによって実行されると，ＴＳＯを違反する可能性があるとして，先行するロード命令を処理するときに，その先行するロード命令の次の命令から上記の後続のロード命令までの命令の再実行を命令制御部に要求することで，ＴＳＯ違反を回避することを特徴とする。【００２２】
複数のスレッドを同時に実行するＳＭＴのプロセッサにおいて，キャッシュ制御部には，各スレッドのＦＰのエントリごとに，処理が完了済みであることを示すフラグと，他のスレッドのストア処理により命令の再実行が必要となることを示すフラグとを用意し，また各スレッドのＦＰごとに最も古い要求が保持されたエントリを示す情報を用意する。【００２３】
あるスレッドαでストア処理が実行されたときに，他のスレッドβに，実行されたストア処理の対象アドレスと対象アドレスが一致し，処理が完了済みであるロード系の命令が保持されたエントリがあれば，そのスレッドβのＦＰの最も古い要求が保持されたエントリまたはその次のエントリから，上記のストア処理の対象アドレスと対象アドレスが一致し，処理が完了済みであるロード系の命令が保持されたエントリまでのすべてのエントリについて，他のスレッドのストア処理により命令の再実行が必要となることを示すフラグをセットする。【００２４】
スレッドβのＦＰの最も古い要求が実行されると，他のスレッドのストア処理により命令の再実行が必要となることを示すフラグがセットされているエントリに保持された要求について，命令制御部に対して命令の再実行要求を発行する。【００２５】
具体的には，本発明は，一連の命令の実行単位であるスレッドを制御する命令制御部と，キャッシュメモリを有するキャッシュ制御部とを備え，メモリアクセスを行うストア命令とロード命令とをアウトオブオーダーで処理し，前記スレッドを複数同時に実行する機能を持つ情報処理装置において，前記キャッシュ制御部は，あるスレッドにより前記キャッシュメモリへのストア命令の処理が実行された場合に，先行するロード命令と後続のロード命令とを有する他のスレッドによって，前記ストア命令の対象アドレスのデータに対する前記後続のロード命令が前記先行するロード命令の処理より先に実行され，その後続のロード命令の対象データが前記ストア命令の処理より先に前記命令制御部に返されたか否かを判定する判定回路と，前記判定回路により前記対象データが前記ストア命令の処理より先に前記命令制御部に返されたと判定された場合に，前記先行するロード命令を処理するとき，前記先行するロード命令の次の命令から前記後続のロード命令までの命令の再実行を前記命令制御部に要求する命令再実行要求回路とを備えることを特徴とする。
【発明の効果】
【００２６】
本発明によって，メモリアクセスをアウトオブオーダーで処理するＳＭＴのプロセッサにおいて，スレッド間のデータ更新の順序性が保証される。
【図面の簡単な説明】
【００２７】
【図１】本実施の形態によるプロセッサの構成例を示す図である。
【図２】ＦＰのエントリが保持する情報の構成要素の例を示す図である。
【図３】本実施の形態によるストアによる命令再実行要求フラグのセット処理フローチャートである。
【図４】本実施の形態による命令再実行要求処理フローチャートである。
【図５】ＳＭＴ構成におけるＴＳＯ違反回避の例を説明する図である。
【図６】ＳＭＴ構成におけるＴＳＯ違反回避の例を説明する図である。
【図７】ＳＭＴ構成におけるＴＳＯ違反回避の例を説明する図である。
【図８】ＳＭＴ構成におけるＴＳＯ違反回避の例を説明する図である。
【図９】ＴＳＯによって保証しなければならないロード命令／ストア命令間の追い越し可否パターンを示す図である。
【図１０】アウトオブオーダー処理を行うプロセッサにおけるロード命令同士の追い越しの例を説明する図である。
【図１１】ＳＭＴ構成におけるＴＳＯ違反の例を説明する図である。
【図１２】ＳＭＴ構成におけるＴＳＯ違反の例を説明する図である。
【図１３】ＳＭＴ構成におけるＴＳＯ違反の例を説明する図である。
【符号の説明】
【００２８】
１  ＣＰＵ
１０  命令制御部
２０  一次キャッシュ制御部
２１  キャッシュＲＡＭ
２２  ＦＰ
２３  ＦＰ−ＴＯＱ
２４  ストア制御部
２５  アドレス一致判定回路
２６  命令再実行要求回路
３０  二次キャッシュ制御部
【発明を実施するための最良の形態】
【００２９】
以下，本発明の実施の形態について，図を用いて説明する。【００３０】
図１は，本実施の形態によるプロセッサの構成例を示す図である。ＣＰＵ１は，複数のスレッドを並行に処理することが可能なＳＭＴのプロセッサであり，命令制御部１０，一次キャッシュ制御部２０，二次キャッシュ制御部３０を備える。一次キャッシュ制御部２０は，キャッシュＲＡＭ２１，ＦＰ（Fetch Port）２２，ＦＰ−ＴＯＱ（Fetch Port Top Of Queue ）２３，ストア制御部２４，アドレス一致判定回路２５，命令再実行要求回路２６を備える。なお，図１の一次キャッシュ制御部２０の構成は，特に本実施の形態に関連する部分のみを抜粋して記載している。なお，スレッドは，ＣＰＵ１における一連の命令の実行単位である。【００３１】
命令制御部１０は，ロード命令，ストア命令等の要求を一次キャッシュ制御部２０に発行する。一次キャッシュ制御部２０は，命令制御部１０からの要求に対する処理を行う。このとき，キャッシュＲＡＭ２１に命令制御部１０からの要求の対象となるデータが存在しなければ，二次キャッシュ制御部３０に該当データの転送を要求する。命令制御部１０からの要求がロード命令であれば，データを命令制御部１０に返す。【００３２】
二次キャッシュ制御部３０は，一次キャッシュ制御部２０からデータ転送の要求を受けると，自らが備えるキャッシュＲＡＭに一次キャッシュ制御部２０から要求されたデータが存在するかを確認し，存在すればそのデータを一次キャッシュ制御部２０に返す。一次キャッシュ制御部２０から要求されたデータが存在しなければ，外部の記憶手段に該当データの転送を要求する。【００３３】
一次キャッシュ制御部２０において，キャッシュＲＡＭ２１は，容量は少ないがアクセスが速い記憶手段である。【００３４】
ＦＰ２２は，命令制御部１０から受けた要求を保持する複数のエントリを有する。ＦＰ２２の各エントリには，ストアによる命令再実行要求フラグ（ＲＩＳ：ReIfetch for Store）が設けられている。命令制御部１０から発行された命令は，ＦＰ２２のエントリに命令の実行順序に従って循環して割り当てられる。ＦＰ２２に保持された要求はアウトオブオーダーで読み出され，処理可能な要求からその対象データを命令制御部１０に返すことが可能である。なお，ＦＰ２２は，並行に実行されるスレッドごとに用意される。【００３５】
ＦＰ−ＴＯＱ２３は，ＦＰ２２のエントリのうち，一番古い要求を保持するエントリを示す情報を保持するレジスタである。なお，ＦＰ−ＴＯＱ２３は，ＦＰ２２と同様に，並行に実行されるスレッドごとに用意される。【００３６】
ＦＰ２２に保持された要求の開放タイミングは，ＦＰ−ＴＯＱ２３で示されているエントリに保持された要求の処理完了時点である。ＦＰ−ＴＯＱ２３で示されているエントリに保持された要求の処理を追い越して，ＦＰ−ＴＯＱ２３で示されていないエントリに保持された要求の処理が先に完了した場合には，その先に処理された要求は，完了状態であることが示されたままＦＰ２２に保持され続ける。その後，ＦＰ−ＴＯＱ２３で示されているエントリに保持された要求が完了した時点で，まとめて処理完了済みのエントリが開放される。【００３７】
ストア制御部２４は，ストア命令によってキャッシュＲＡＭ２１上のデータが書き換えられるときに，そのストア命令の対象となるアドレスをアドレス一致判定回路２５に通知する。【００３８】
アドレス一致判定回路２５は，ストア制御部２４からストア命令の対象となるアドレスを受けると，そのストア命令が属するスレッド以外のスレッドのＦＰ２２を検索し，ロード系の命令であり，処理完了済みであり，かつ命令の対象アドレスが受け取ったアドレスと一致する要求が検出されれば，ＦＰ−ＴＯＱ２３が示すエントリまたはその次のエントリから検出された要求が保持されたエントリまでのすべてのエントリに，ストアによる命令再実行要求フラグをセットする。なお，検出された要求が保持されたエントリにのみ，ストアによる命令再実行要求フラグをセットするようにしてもよい。【００３９】
命令再実行要求回路２６は，ＦＰ−ＴＯＱ２３で示されているエントリに保持された要求の処理が行われると，ストアによる命令再実行要求フラグがセットされているエントリに保持された要求について，命令制御部１０に対して命令の再実行要求を送る。【００４０】
図２は，ＦＰのエントリが保持する情報の構成要素の例を示す図である。図２の例は，ＦＰ２２のエントリが保持する情報のうち，特に本実施の形態に関連する部分の構成について抜粋したものである。ＦＰ２２の各エントリは，そのエントリが開放されているか開放されていないか，すなわち保持された要求が無効であるか有効であるかを示すフラグ（ｖａｌｉｄ），保持された要求の処理が完了しているか完了していないかを示すフラグ（ｓｔａｔｕｓ），ロード命令，ストア命令などの命令の種別を示す命令コード（ｏｐｃｏｄｅ），その命令の対象となるアドレス（ａｄｄｒｅｓｓ），上述のストアによる命令再実行要求フラグ（ＲＩＳ）等の情報を有する。【００４１】
本実施の形態において，ｖａｌｉｄは，保持された要求が無効である場合には“０”となり，有効である場合には“１”となるものとする。また，ｓｔａｔｕｓは，保持された要求の処理が完了していない場合には“未完了”となり，完了している場合には“完了”となるものとする。また，ストアによる命令再実行要求フラグは，デフォルトで“０”であり，フラグセットで“１”となるものとする。【００４２】
図３は，本実施の形態によるストアによる命令再実行要求フラグのセット処理フローチャートである。キャッシュＲＡＭ２１へのストア処理が実行されると（ステップＳ１０），ストア処理が実行されたスレッドと異なるスレッドのＦＰ２２を検索する（ステップＳ１１）。【００４３】
検索されたＦＰ２２に，ｖａｌｉｄが１であり，ｓｔａｔｕｓが完了であり，かつｏｐｃｏｄｅがロード系の命令であるエントリが存在しなければ（ステップＳ１２），ストアによる命令再実行要求フラグ（ＲＩＳ）をセットしない。【００４４】
検索されたＦＰ２２に，ｖａｌｉｄが１であり，ｓｔａｔｕｓが完了であり，かつｏｐｃｏｄｅがロード系の命令であるエントリが存在するときに（ステップＳ１２），そのエントリのアドレス（ａｄｄｒｅｓｓ）と実行されたストア処理の対象アドレスとが一致すれば（ステップＳ１３），ＦＰ−ＴＯＱ２３が示すエントリの次から一致したエントリまでのすべてのエントリに，ストアによる命令再実行要求フラグ（ＲＩＳ）をセットする（ステップＳ１４）。【００４５】
検索されたＦＰ２２に，ｖａｌｉｄが１であり，ｓｔａｔｕｓが完了であり，かつｏｐｃｏｄｅがロード系の命令であるエントリが存在しても（ステップＳ１２），そのエントリのアドレス（ａｄｄｒｅｓｓ）と実行されたストア処理の対象アドレスとが一致しなければ（ステップＳ１３），ストアによる命令再実行要求フラグ（ＲＩＳ）をセットしない。【００４６】
図４は，本実施の形態による命令再実行要求処理フローチャートである。図４のフローチャートにおいて，ＦＰ＃ｎ（ｎ＝０，１，２，... ）は，ＦＰ２２の各エントリを示し，ｎ（ｎ＝０，１，２，... ）は，便宜上エントリに割り当てられた番号を示す。【００４７】
エントリＦＰ＃ｎに保持された要求により命令制御部１０にデータが転送されると（ステップＳ２０），そのエントリＦＰ＃ｎがＦＰ−ＴＯＱ２３に示されたエントリであり（ステップＳ２１），また，そのエントリＦＰ＃ｎが属するスレッドのＦＰ２２に，ｖａｌｉｄが１であり，かつ命令再実行要求フラグ（ＲＩＳ）が１であるエントリが存在すれば（ステップＳ２２），すべての該当するエントリに保持された要求について，命令制御部１０に命令再実行を要求する（ステップＳ２３）。【００４８】
図５〜図８は，ＳＭＴ構成におけるＴＳＯ違反回避の例を説明する図である。ここでは，図５〜図８を用いて，本実施の形態の一次キャッシュ制御部２０による処理のより具体的な例を説明する。図５〜図８に示す例において，命令制御部１０から一次キャッシュ制御部２０に発行されたロード命令／ストア命令等のメモリアクセス要求は，一旦ＦＰ２２に保持される。ここでは，説明の便宜上プロセッサ内のスレッド数を２とし，スレッドごとにそれぞれＦＰ２２が備えられているものとする。【００４９】
図５〜図８に示す例では，キャッシュＲＡＭ２１上にデータが存在しない領域Ａ，キャッシュＲＡＭ２１上にデータが存在する領域Ｂに対して，ｔｈｒｅａｄ−αでは，ｓｔｏｒｅ−Ａ，ｓｔｏｒｅ−Ｂの順に要求が行われ，ｔｈｒｅａｄ−βでは，ｌｏａｄ−Ｂ，ｌｏａｄ−Ａの順に要求が行われるケースについて説明する（図５参照）。【００５０】
ｔｈｒｅａｄ−αにおいて命令制御部１０から発行された命令は，ＦＰ２２αの０番のエントリ（以下，ＦＰα＃０と表記）にｓｔｏｒｅ−Ａ，１番のエントリ（以下，ＦＰα＃１と表記）にｓｔｏｒｅ−Ｂが保持され，ＦＰ２２αのＦＰ−ＴＯＱ２３αはエントリＦＰα＃０を示しているものとする。ｔｈｒｅａｄ−βにおいて命令制御部１０から発行された命令は，ＦＰ２２βの０番のエントリ（以下，ＦＰβ＃０と表記）にｌｏａｄ−Ｂ，１番のエントリ（以下，ＦＰβ＃１と表記）にｌｏａｄ−Ａが保持され，ＦＰ２２βのＦＰ−ＴＯＱ２３βはエントリＦＰβ＃０を示しているものとする（図５参照）。なお，図において，各ＦＰ２２に保持された命令の左側に表記された数字は，各エントリを示す番号である。【００５１】
ＦＰ２２α，ＦＰ２２βのどちらから要求をするか，またＦＰ２２α，ＦＰ２２βにおいてどのエントリに保持された要求から処理するかは，基本的に順不同である。ここでは，ＦＰβ＃０，ＦＰβ＃１，ＦＰα＃０，ＦＰα＃１の順に，エントリに保持された要求を処理するものとする。【００５２】
一次キャッシュ制御部２０は，まず，ＦＰβ＃０に保持されたｌｏａｄ−Ｂの処理を行うと，キャッシュＲＡＭ２１の領域Ｂにはデータが存在しないためにキャッシュミスとなるので，データの転送を二次キャッシュ制御部３０またはメインメモリ（図示省略）に要求する（図５参照）。【００５３】
そのデータがキャッシュＲＡＭ２１に到着するまでの間に，ＦＰβ＃１に保持されたｌｏａｄ−Ａの処理を開始し，キャッシュヒットとなるため，キャッシュＲＡＭ２１の領域Ａのデータを読み出し，得られたｄａｔａ−Ａ（ｏｌｄ）を命令制御部１０に返す（図５参照）。この時点で，ｔｈｒｅａｄ−βにおいて，ｌｏａｄ−Ａの処理がｌｏａｄ−Ｂの処理を追い越して，データを命令制御部１０に返すことになる。なお，図中，領域Ａのデータがｏｌｄと表記されているのは，後のｓｔｏｒｅ−Ａの処理によって書き換えられたデータと比較して古いデータであることを示している。【００５４】
ここで，ＦＰβ＃１に保持されたｌｏａｄ−Ａの処理は完了しているが，ＦＰ−ＴＯＱ２３βで示されたＦＰβ＃０に保持されたｌｏａｄ−Ｂの処理はまだ完了していないので，この時点ではＦＰβ＃１に処理完了済みのフラグがセットされるだけで，ＦＰβ＃１は開放されない。【００５５】
その後，ｔｈｒｅａｄ−αのＦＰα＃０に保持されたｓｔｏｒｅ−Ａの処理を行い，キャッシュＲＡＭ２１の領域Ａにデータを書き込む。このｓｔｏｒｅ−Ａのデータ書き込み処理時に，ｔｈｒｅａｄ−α以外のスレッドのＦＰ２２，この場合にはｔｈｒｅａｄ−βのＦＰ２２βに保持されているすべての処理完了済みの要求のアドレスをチェックし，領域Ａと一致するアドレスの要求が保持されたエントリがあれば，ＦＰ２２βのＦＰ−ＴＯＱ２３βで示されたエントリまたはその次からその一致したエントリまでのすべてのエントリに，ストアによる命令再実行要求フラグ（ＲＩＳ）をセットする。ここでは，領域Ａと一致するアドレスの要求が保持されたエントリＦＰβ＃１があるので，ＦＰ２２βのＦＰ−ＴＯＱ２３βで示されたエントリＦＰβ＃０からＦＰβ＃１まで，またはＦＰβ＃１に対してのみ，ストアによる命令再実行要求フラグ（ＲＩＳ）をセットする（図６参照）。図では，ＦＰβ＃１のエントリのＲＩＳに１がセットされている。【００５６】
その後，領域Ｂを含むデータが，二次キャッシュ制御部３０から一次キャッシュ制御部２０に到着し，キャッシュＲＡＭ２１の領域Ｂに書き込まれる。ｔｈｒｅａｄ−αのＦＰα＃１に保持されたｓｔｏｒｅ−Ｂの処理を行い，キャッシュＲＡＭ２１の領域Ｂにデータを書き込む（図６参照）。なお，図中，領域Ａ，領域Ｂのデータがｎｅｗと表記されているのは，ｓｔｏｒｅ−Ａ，ｓｔｏｒｅ−Ｂの処理によって書き換えられる前のデータと比較して新しいデータであることを示している。【００５７】
その後，ｔｈｒｅａｄ−βのＦＰβ＃０に保持されたｌｏａｄ−Ｂの再処理を行い，キャッシュヒットとなるため，キャッシュＲＡＭ２１の領域Ｂのデータを読み出し，得られたｄａｔａ−Ｂ（ｎｅｗ）を命令制御部１０に返す。このとき，ＦＰβ＃０はＦＰ−ＴＯＱ２３βに示されたエントリであるので，ストアによる命令再実行要求フラグ（ＲＩＳ）がセットされているエントリについて，命令制御部１０に対して命令の再実行要求を発行する（図７参照）。ただし，ＦＰ−ＴＯＱ２３βに示されたエントリであるＦＰβ＃０については，命令の再実行要求を発行する必要はない。なお，ＦＰ−ＴＯＱ２３βに示されたエントリであるＦＰβ＃０の処理が完了したので，ＦＰ２２βの処理完了済みの要求が保持されたエントリをすべて開放する。【００５８】
命令制御部１０からはｔｈｒｅａｄ−βとして再度ｌｏａｄ−Ａが要求され，その要求はＦＰ２２βの２番のエントリ（以下，ＦＰβ＃２と表記）に保持される。ＦＰβ＃２に保持されたｌｏａｄ−Ａの処理を行い，キャッシュヒットとなるため，キャッシュＲＡＭ２１の領域Ａのデータを読み出し，得られたｄａｔａ−Ａ（ｎｅｗ）を命令制御部１０に返す（図８参照）。これで，ｔｈｒｅａｄ−αのｓｔｏｒｅ−Ａの処理によるストア済みデータを，命令制御部１０に返すことになる。【００５９】
以上のようなストアによる命令再実行の機構がなければ，ｔｈｒｅａｄ−βのｌｏａｄ−Ｂの処理で命令制御部１０に返すデータがストア済みデータであるのに，ｌｏａｄ−Ａの処理で返すデータがストア前データとなり，ソフトウェアからはｔｈｒｅａｄ−αのｓｔｏｒｅ−Ａ，ｓｔｏｒｅ−Ｂの処理順序が逆転しているように見え，ＴＳＯに違反することになる。ストアによる命令再実行を行うことにより，ｔｈｒｅａｄ−βのｌｏａｄ−Ｂ，ｌｏａｄ−Ａの処理において，共にｔｈｒｅａｄ−αのストア済みデータを返すことになり，ＴＳＯ違反を回避できるようになる。
【産業上の利用可能性】
【００６０】
情報処理装置，キャッシュメモリ制御装置およびメモリアクセス順序保証方法は，情報処理装置に用いられる技術に関するものであり，特にキャッシュを有する電算機において利用される技術である。
【図１】
2008155829.tif 000003
【図２】
2008155829.tif 000004
【図３】
2008155829.tif 000005
【図４】
2008155829.tif 000006
【図５】
2008155829.tif 000007
【図６】
2008155829.tif 000008
【図７】
2008155829.tif 000009
【図８】
2008155829.tif 000010
【図９】
2008155829.tif 000011
【図１０】
2008155829.tif 000012
【図１１】
2008155829.tif 000013
【図１２】
2008155829.tif 000014
【図１３】
2008155829.tif 000015
【手続補正書】
【提出日】平成21年12月15日(2009.12.15)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
一連の命令の実行単位であるスレッドを制御する命令制御部と，キャッシュメモリを有するキャッシュ制御部とを備え，メモリアクセスを行うストア命令とロード命令とをアウトオブオーダーで処理し，前記スレッドを複数同時に実行する機能を持つ情報処理装置において，
前記キャッシュ制御部は，
第１のスレッドにより前記キャッシュメモリへのストア命令の処理が実行された場合に，第１のロード命令と第２のロード命令とを有する第２のスレッドによって，前記第２のロード命令が前記第１のロード命令の処理より先に実行され，前記第２のロード命令の対象データが前記ストア命令の処理より先に前記命令制御部に返されたか否かを判定する判定部と，
前記判定部により前記対象データが前記ストア命令の処理より先に前記命令制御部に返されたと判定された場合に，前記第１のロード命令を処理するとき，前記第１のロード命令の次の命令から前記第２のロード命令までの命令の再実行を前記命令制御部に要求する命令再実行要求部とを備える
ことを特徴とする情報処理装置。
【請求項２】
前記第１のロード命令が，前記第２のロード命令よりも先行する命令である
ことを特徴とする請求項１記載の情報処理装置。
【請求項３】
前記第２のロード命令が，前記ストア命令の対象アドレスのデータをロードする命令である
ことを特徴とする請求項１または請求項２記載の情報処理装置。
【請求項４】
メモリアクセスをアウトオブオーダーで処理し，一連の命令の実行単位であるスレッドを複数同時に実行する機能を持つ情報処理装置において用いられる，キャッシュメモリを有するキャッシュメモリ制御装置において，
第１のスレッドにより前記キャッシュメモリへのストア命令の処理が実行された場合に，第１のロード命令と第２のロード命令とを有する第２のスレッドによって，前記第２のロード命令が前記第１のロード命令の処理より先に実行され，前記第２のロード命令の対象データが前記ストア命令の処理より先に前記命令制御部に返されたか否かを判定する判定部と，
前記判定部により前記対象データが前記ストア命令の処理より先に前記命令制御部に返されたと判定された場合に，前記第１のロード命令を処理するとき，前記第１のロード命令の次の命令から前記第２のロード命令までの命令の再実行を前記命令制御部に要求する命令再実行要求部とを備える
ことを特徴とするキャッシュメモリ制御装置。
【請求項５】
前記第１のロード命令が，前記第２のロード命令よりも先行する命令である
ことを特徴とする請求項４記載のキャッシュメモリ制御装置。
【請求項６】
前記第２のロード命令が，前記ストア命令の対象アドレスのデータをロードする命令である
ことを特徴とする請求項４または請求項５記載のキャッシュメモリ制御装置。
【請求項７】
一連の命令の実行単位であるスレッドを制御する命令制御部と，キャッシュメモリを有するキャッシュ制御部とを備え，メモリアクセスを行うストア命令とロード命令とをアウトオブオーダーで処理し，前記スレッドを複数同時に実行する機能を持つ情報処理装置における，メモリにアクセスする命令の順序に関する予め定められた制約を保証するスレッド間のメモリアクセス順序保証方法であって，
第１のスレッドにより前記キャッシュメモリへのストア命令の処理が実行された場合に，第１のロード命令と第２のロード命令とを有する第２のスレッドによって，前記第２のロード命令が前記第１のロード命令の処理より先に実行され，前記第２のロード命令の対象データが前記ストア命令の処理より先に前記命令制御部に返されたか否かを判定するステップと，
前記対象データが前記ストア命令の処理より先に前記命令制御部に返されたと判定された場合に，前記第１のロード命令を処理するとき，前記第１のロード命令の次の命令から前記第２のロード命令までの命令の再実行を前記命令制御部に要求する命令再実行要求ステップとを有する
ことを特徴とするメモリアクセス順序保証方法。
【請求項８】
前記第１のロード命令が，前記第２のロード命令よりも先行する命令である
ことを特徴とする請求項７記載のメモリアクセス順序保証方法。
【請求項９】
前記第２のロード命令が，前記ストア命令の対象アドレスのデータをロードする命令である
ことを特徴とする請求項７または請求項８記載のメモリアクセス順序保証方法。
【手続補正２】
【補正対象書類名】明細書
【補正対象項目名】００２５
【補正方法】変更
【補正の内容】
【００２５】
具体的には，本発明は，一連の命令の実行単位であるスレッドを制御する命令制御部と，キャッシュメモリを有するキャッシュ制御部とを備え，メモリアクセスを行うストア命令とロード命令とをアウトオブオーダーで処理し，前記スレッドを複数同時に実行する機能を持つ情報処理装置において，前記キャッシュ制御部は，第１のスレッドにより前記キャッシュメモリへのストア命令の処理が実行された場合に，第１のロード命令と第２のロード命令とを有する第２のスレッドによって，前記第２のロード命令が前記第１のロード命令の処理より先に実行され，前記第２のロード命令の対象データが前記ストア命令の処理より先に前記命令制御部に返されたか否かを判定する判定部と，前記判定部により前記対象データが前記ストア命令の処理より先に前記命令制御部に返されたと判定された場合に，前記第１のロード命令を処理するとき，前記第１のロード命令の次の命令から前記第２のロード命令までの命令の再実行を前記命令制御部に要求する命令再実行要求部とを備えることを特徴とする。
【国際調査報告】
2008155829.tif 000016
2008155829.tif 000017