(57)【要約】【課題】同一の命令に従う複数の実行スロットを並列実行可能なプロセッサにおける性能上のボトルネックを解消する手段を提供する。【解決手段】同一の命令を複数のデータに対して同時に適応可能にするため、複数の実行スロットを設けた、並列実行可能なＳＩＭＤ型プロセッサが提供される。同一の命令に含まれるアトミック命令が実行されると、プロセッサは、当該アトミック命令に対応する複数の実行スロットのうち指定されたアドレスが重複している実行スロットを特定し、アドレスが重複している実行スロットのうち１つの実行スロットで命令を実行し、当該実行の結果を返すとともに、残りの実行スロットについては、命令を実行することなく、命令の実行が失敗したことを示す結果を返す。【選択図】図７
2017027432.tif 000002
【特許請求の範囲】
【請求項１】
同一の命令を複数のデータに対して同時に適応可能にするため、複数の実行スロットを設けた、並列実行可能なＳＩＭＤ(Single Instruction Multi Data)型プロセッサであって、
前記同一の命令は、実行スロットごとに指定されたアドレスに格納されているデータを読み込むとともに、当該読み込まれたデータが所定条件を満たした場合に、当該指定されたアドレスへデータを書き込む処理を、アトミック性を維持しつつ実行するためのアトミック命令を含み、
前記アトミック命令が実行されると、前記プロセッサは、
当該アトミック命令に対応する複数の実行スロットのうち指定されたアドレスが重複している実行スロットを特定し、
前記アドレスが重複している実行スロットのうち１つの実行スロットで命令を実行し、当該実行の結果を返すとともに、残りの実行スロットについては、命令を実行することなく、命令の実行が失敗したことを示す結果を返す、プロセッサ。
【請求項２】
前記プロセッサは、前記アドレスが重複している実行スロットのうち１つの実行スロットの命令実行前に、残りの実行スロットについて、命令の実行が失敗したことを示す結果を返す、請求項１に記載のプロセッサ。
【請求項３】
前記プロセッサは、
前記アドレスが重複している実行スロットのうち１つの実行スロットの命令実行後に、指定されたアドレスから読み込んだ値をさらなる結果として返し、
前記残りの実行スロットについて、
前記アドレスが重複している実行スロットのうち１つの実行スロットの命令実行が成功した場合には、当該１つの実行スロットの命令がメモリに書き込んだ値をさらなる結果として返し、
前記アドレスが重複している実行スロットのうち１つの実行スロットの命令実行が失敗した場合には、当該１つの実行スロットが命令実行途中でメモリから読み込んだ値をさらなる結果として返す、請求項１または２に記載のプロセッサ。
【請求項４】
前記プロセッサは、前記アドレスが重複している実行スロットのうち、実行スロットに割り当てられた番号に基づいて、実行する１つの実行スロットを決定する、請求項１〜３のいずれか１項に記載のプロセッサ。
【請求項５】
前記プロセッサは、複数のプロセッサコアおよび前記複数のプロセッサコアの間で共有されるメモリを含む、請求項１〜４のいずれか１項に記載のプロセッサ。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、同一の命令を複数のデータに対して同時に適応可能にするため、複数の実行スロットを設けた、並列実行可能なＳＩＭＤ（Single Instruction Multi Data）型プロセッサに関する。
【背景技術】
【０００２】
近年では、画像処理および音声処理などに適したマルチメディア命令を実装した各種のプロセッサが実用化されている。マルチメディア命令は、主として、同一の演算を多数のデータに対して繰り返さなければならないような用途に向けられる。マルチメディア命令を実現するための実装手法の一つとして、ＳＩＭＤ（Single Instruction Multiple Data）が知られている。
【０００３】
ＳＩＭＤでは、指示された単一の命令に応答して、それぞれに異なるデータが入力される複数の実行スロットが互いに同期して処理を実行する。すなわち、ＳＩＭＤ型プロセッサは、単一の命令ストリームと複数のデータストリームとの組み合わせをサポートする。
【０００４】
ＳＩＭＤ型プロセッサの一例として、ＳＩＭＴ（Single Instruction stream Multiple Thread）型プロセッサが提案されている。ＳＩＭＴ型プロセッサでは、分岐命令に従って実行ユニットの各々が、当該スロット上の命令実行を有効にするか、無効にするかを管理することで、割り当てられたスレッドの実行を完結する。複数のスレッドが並列実行されるので、並列数が増加した場合であっても、その並列数を意識することなく、プログラミングができる。
【０００５】
例えば、米国特許第７６２７７２３号明細書（特許文献１）は、ＳＩＭＴ型プロセッサの一例を示す。特許文献１に記載の並列処理サブシステムでは、複数のＲＯＰ（Raster Operation）ユニットの各々は、メモリの特定アドレス範囲を担当し、当該担当するアドレス範囲にアクセスして割り当てられたスレッドを実行する。
【先行技術文献】
【特許文献】
【０００６】
【特許文献１】米国特許第７６２７７２３号明細書
【発明の概要】
【発明が解決しようとする課題】
【０００７】
ＳＩＭＴ型プロセッサにおいて、実行スロットの各々がスレッドを独立に実行する。各スレッドの処理には、例えば、処理の実行により得られたデータを共通のメモリへ書き戻すような処理が含まれ得る。このような処理では、アトミック性（不可分性）を維持する必要がある。そのため、ＳＩＭＴ型プロセッサでは、アトミック（atomic）命令が用意されており、スレッド間の同期処理に利用される。
【０００８】
アトミック命令は、典型的には、メモリからのデータ読み込み（ｒｅａｄ）、更新後データの計算（ｍｏｄｉｆｙ）、更新後データのメモリへの書き込み（ｗｒｉｔｅ）を含む。あるスレッドの実行を担う実行スロットがアトミック命令に従ってアトミック処理を実行している最中は、他のスレッドの実行を担う実行スロットの同一のメモリに対するアクセスを排除する動作が実行される。このように、ＳＩＭＴ型プロセッサにおいて、複数のスレッドに対してアトミック命令を与えることで、同一のメモリへアクセスする複数のスレッドの処理が直列化されて実行されることになり、この処理の直列化によってアトミック性が維持される。
【０００９】
しかしながら、アトミック性を維持するためにスレッドの処理が直列化されることで、ＳＩＭＴ型プロセッサにおける性能上のボトルネックが生じる場合がある。そこで、本発明は、このような性能上のボトルネックを解消する一つの解決手段を提供することを目的とすることである。
【課題を解決するための手段】
【００１０】
本発明のある局面に従えば、同一の命令を複数のデータに対して同時に適応可能にするため、複数の実行スロットを設けた、並列実行可能なＳＩＭＤ(Single Instruction Multi Data)型プロセッサが提供される。同一の命令は、実行スロットごとに指定されたアドレスに格納されているデータを読み込むとともに、当該読み込まれたデータが所定条件を満たした場合に、当該指定されたアドレスへデータを書き込む処理を、アトミック性を維持しつつ実行するためのアトミック命令を含む。アトミック命令が実行されると、プロセッサは、当該アトミック命令に対応する複数の実行スロットのうち指定されたアドレスが重複している実行スロットを特定し、アドレスが重複している実行スロットのうち１つの実行スロットで命令を実行し、当該実行の結果を返すとともに、残りの実行スロットについては、命令を実行することなく、命令の実行が失敗したことを示す結果を返す。
【００１１】
好ましくは、プロセッサは、アドレスが重複している実行スロットのうち１つの実行スロットの命令実行前に、残りの実行スロットについて、命令の実行が失敗したことを示す結果を返す。
【００１２】
好ましくは、プロセッサは、アドレスが重複している実行スロットのうち１つの実行スロットの命令実行後に、指定されたアドレスから読み込んだ値をさらなる結果として返し、残りの実行スロットについて、アドレスが重複している実行スロットのうち１つの実行スロットの命令実行が成功した場合には、当該１つの実行スロットの命令がメモリに書き込んだ値をさらなる結果として返し、アドレスが重複している実行スロットのうち１つの実行スロットの命令実行が失敗した場合には、当該１つの実行スロットが命令実行途中でメモリから読み込んだ値をさらなる結果として返す。
【００１３】
好ましくは、プロセッサは、アドレスが重複している実行スロットのうち、実行スロットに割り当てられた番号に基づいて、実行する１つの実行スロットを決定する。
【００１４】
好ましくは、プロセッサは、複数のプロセッサコアおよび複数のプロセッサコアの間で共有されるメモリを含む。
【発明の効果】
【００１５】
本発明によれば、同一の命令に従う複数のスレッドを並列実行可能なプロセッサにおける性能上のボトルネックを解消できる。
【図面の簡単な説明】
【００１６】
【図１】実施の形態１に従うコンピュータの装置構成を示す模式図である。
【図２】関連技術に係るアトミック命令の処理手順を説明するための模式図である。
【図３】命令を実行すべき実行スロットを定めるための処理を説明するための図である。
【図４】関連技術に係るＣＡＳ命令１を用いたｌｏｃｋ−ｆｒｅｅアルゴリズムの処理手順を示すフローチャートである。
【図５】図４に示すｌｏｃｋ−ｆｒｅｅアルゴリズムの実行過程におけるメモリに格納されるデータの変化を説明するための図である（実行スロット数が４の場合）。
【図６】図４に示すｌｏｃｋ−ｆｒｅｅアルゴリズムの実行過程におけるメモリに格納されるデータの変化の別の例を説明するための図である（実行スロット数が８の場合）。
【図７】実施の形態１に従うＣＡＳ命令２の処理手順を説明するための模式図である。
【図８】実施の形態１に従うＣＡＳ命令２を用いたｌｏｃｋ−ｆｒｅｅアルゴリズム３００の処理手順を示すフローチャートである。
【図９】図８に示すｌｏｃｋ−ｆｒｅｅアルゴリズムの実行過程におけるメモリに格納されるデータの変化を説明するための図である（実行スロット数が４の場合）。
【図１０】図８に示すｌｏｃｋ−ｆｒｅｅアルゴリズムの実行過程におけるメモリに格納されるデータの変化の別の例を説明するための図である（実行スロット数が８の場合）。
【図１１】実施の形態２に従うアトミック命令の処理手順を説明するための模式図である。
【図１２】実施の形態２に従うＣＳＷ命令を用いたｌｏｃｋ−ｆｒｅｅアルゴリズム３５０の処理手順を示すフローチャートである。
【図１３】実施の形態３に従うコンピュータの装置構成を示す模式図である。
【図１４】実施の形態４に従うコンピュータの装置構成を示す模式図である。
【図１５】図１４に示すローカルストレージの構成例を示す模式図である。
【図１６】図１４に示す実施の形態４に従うコンピュータにおけるメモリアクセスの処理手順を説明するためのフローチャートである。
【図１７】図１６のフローチャートによって定義される処理手順において用いられるアクセスフラグのデータ構造例を示す模式図である。
【図１８】実施の形態５に従うコンピュータに関連したハードウェア構成を示す模式図である。
【図１９】アトミック処理を実現するためのマイクロコードの一例を示す図である。
【発明を実施するための形態】
【００１７】
本発明の実施の形態について、図面を参照しながら詳細に説明する。なお、図中の同一または相当部分については、同一符号を付してその説明は繰り返さない。
【００１８】
＜Ａ．概要＞
本実施の形態に従うプロセッサは、同一の命令を複数のデータに対して同時に適応可能にするため、複数の実行スロットを設けた、並列実行可能なＳＩＭＤ(Single Instruction Multi Data)型プロセッサに向けられる。このような、同一の命令に従う複数のスレッドを並列実行可能なプロセッサにおいて、アクセス先のアドレスが重複するスレッドの並列実行が命令されると、同じアドレスへのアクセスが競合しないように、スレッド間の排他処理が実行される。この結果、アドレスが重複するスレッドの処理については、直列化されて実行される。本願発明者は、ある種のアトミック命令の実行時には、このスレッドの直列化が性能上のボトルネックであるという新たな知見を見出した。
【００１９】
そこで、アクセス先のアドレスが重複する複数のスレッドが存在している場合であっても、スレッドの直列化ではなく、処理性能を向上させる別の解決手段に想到した。以下、本願発明者が想到した新たなアトミック命令について説明する。
【００２０】
本実施の形態に従うアトミック命令のプロセッサへの実装方法は、どのような方法であってもよい。例えば、ｘ８６系と称されるＣＰＵ（Central Processing Unit）といったＣＩＳＣ（Complex Instruction Set Computer）プロセッサでは、単一のプロセッサ命令として実装されてもよい。また、ＰｏｗｅｒＰＣ（登録商標）およびＳＰＡＲＣ（登録商標）といったＲＩＳＣプロセッサでは、複数種類のプロセッサ命令の組み合わせで実現されてもよい。この場合には、Load-LinkおよびStore-Conditionalと称される２種類のプロセッサ命令が用いられてもよい。
【００２１】
また、ＧＰＵ（Graphics Processing Unit）では、ＳＩＭＤ動作する形での、単一のプロセッサ命令として実装してもよい。あるいは、本実施の形態に従う処理手順を複数のプロセッサ命令に分解して実装してもよい。
【００２２】
プロセッサに実装されるプロセッサ命令に応じて、高級言語で作成されたプログラムから、コンパイラまたはアセンブラなどを用いて最適化された命令列が生成されることになる。この場合、プログラムを作成する観点から見れば、プロセッサのアーキテクチャの違いなどを意識する必要はない。
【００２３】
＜Ｂ．実施の形態１＞
（ｂ１：装置構成）
まず、実施の形態１として、本実施の形態に従うアトミック処理をマルチコアのＳＩＭＤ型プロセッサに実装した構成について説明する。典型的には、実施の形態１に従うプロセッサは、同一の命令に従う複数のスレッドを並列実行可能なＳＩＭＴ型を想定している。但し、本発明の技術的範囲は、特許請求の範囲の記載に基づいて定められるべきであり、例えば、将来的に実用化される新たなアーキテクチャを排除するものではない。
【００２４】
図１は、実施の形態１に従うコンピュータ１の装置構成を示す模式図である。図１を参照して、実施の形態１に従うコンピュータ１は、マルチコアプロセッサ１０と、外部メモリ１８０と、外部機器１９０とを含む。
【００２５】
マルチコアプロセッサ１０は、複数のプロセッサコア１００−１，１００−２（以下、「プロセッサコア１００」とも総称する。）と、共有キャッシュ１１０と、メモリコントローラ１２０と、ＩＯコントローラ１３０とを含む。これらの各コンポーネントは、内部バス１４０を介して互いにデータを遣り取り可能に接続されている。共有キャッシュ１１０は、複数のプロセッサコア１００−１，１００−２間で共有される。図１には、説明の便宜上、２つのプロセッサコア１００からなる構成について例示するが、プロセッサコア１００の数については特に制約はない。
【００２６】
マルチコアプロセッサ１０（または、プロセッサコア１００の各々）は、同一の命令に従う複数のスレッドを並列実行可能にするため複数の実行スロットを有したプロセッサである。実施の形態１においては、プロセッサコア１００の各々にＳＩＭＤ命令セットが実装されているものとする。ＳＩＭＤ命令セットは、共有キャッシュ１１０上の複数のデータアドレスについて、リード・モディファイ・ライトを並列実行するためのアトミック命令を含む。このアトミック命令では、並列実行されるリード・モディファイ・ライトの間でのアトミック性が維持されるものとする。本明細書において、「リード・モディファイ・ライト」は、メモリからのデータ読み込み（ｒｅａｄ）、更新後データの計算（ｍｏｄｉｆｙ）、更新後データのメモリへの書き込み（ｗｒｉｔｅ）の処理を総称したものである。但し、「リード・モディファイ・ライト」には、３つの処理のうち一部のみを実行する場合を含み得る。
【００２７】
共有キャッシュ１１０は、プロセッサコア１００の各々がアクセス可能なメモリ領域である。
【００２８】
メモリコントローラ１２０は、外部メモリバス１６０を介して接続された外部メモリ１８０との間で、データを遣り取りする。メモリコントローラ１２０は、内部バス１５０を介して共有キャッシュ１１０に接続されている。メモリコントローラ１２０は、典型的には、外部メモリ１８０から読み込んだデータを共有キャッシュ１１０へ書き込むとともに、共有キャッシュ１１０から読み込んだデータを外部メモリ１８０へ書き込む。
【００２９】
ＩＯコントローラ１３０は、外部機器バス１７０を介して接続された外部機器１９０との間で、データを遣り取りする。ＩＯコントローラ１３０は、典型的には、外部機器１９０から読み込んだデータを共有キャッシュ１１０へ書き込むとともに、共有キャッシュ１１０から読み込んだデータを外部機器１９０へ書き込む。
【００３０】
外部メモリ１８０は、共有キャッシュ１１０に比較してアクセス速度が低速ではあるが、より記憶容量の大きなメモリ領域である。外部機器１９０は、各種の入出力装置および外部記憶装置を含む。
【００３１】
（ｂ２：関連技術に係るアトミック命令の処理手順）
まず、実施の形態１に従うコンピュータ１において、関連技術に係るアトミック命令の処理手順について説明する。図２は、関連技術に係るアトミック命令の処理手順を説明するための模式図である。マルチコアプロセッサ１０に与えられるＳＩＭＤ命令２００＃は、４つの実行スロット２０１〜２０４（ｓｌｏｔ０〜ｓｌｏｔ３）に適用される。実行スロット２０１〜２０４の各々には、並列実行される同一のアトミック命令と、それぞれに独立な入力データとが指定される。
【００３２】
ＳＩＭＤ命令２００＃を含む命令列は、予め定められたロジックに従って、複数のプロセッサコア１００−１，１００−２（図１参照）の一方または両方に与えられる。
【００３３】
実行スロット２０１〜２０４に対応付けられて、フラグ領域２１１〜２１４、および、戻り値領域２２１〜２２４がメモリ領域内にそれぞれ設けられる。フラグ領域２１１〜２１４は、対応する実行スロットに指定されている命令の実行状態を格納するための領域である。戻り値領域２２１〜２２４は、対応する実行スロットに指定されている命令の実行によって得られた戻り値を格納するための領域である。フラグ領域２１１〜２１４および戻り値領域２２１〜２２４は、共有キャッシュ１１０の特定のアドレス範囲を用いて実装してもよいし、特殊レジスタを用いて実装してもよい。
【００３４】
まず、ＳＩＭＤ命令２００＃の実行が開始されると（（１）命令実行開始）、フラグ領域２１１〜２１４に格納されているそれぞれの値が初期化される。図２に示す処理手順においては、フラグ領域２１１〜２１４の各々には、対応する実行スロットに指定されている命令について、「未処理」または「処理済」を意味する値が設定される。
【００３５】
初期化において、命令が有効に指定されている実行スロットに対応するフラグ領域には、「未処理」を意味する値が設定され、命令が無効に指定されている実行スロットに対応するフラグ領域には、「処理済」を意味する値が設定される。
【００３６】
例えば、フラグ領域２１１〜２１４をメモリの特定のアドレス範囲を用いて実装する場合には、状態値に応じた特殊値（例えば、「−１」または「ＦＦＦＦ」など）が指定され、あるいは、フラグ領域２１１〜２１４を特殊レジスタにより実装する場合には、それらの特殊レジスタの値が、状態値に応じてオフまたはオンに設定される。
【００３７】
図２において、ＳＩＭＤ命令２００＃内に記載される「アドレスＡ」、「アドレスＢ」、「アドレスＣ」は、対応する実行スロット２０１〜２０４のアトミック命令が作用する先に指定されている命令がデータを読み込む先のアドレスを意味する。図２に示す例では、実行スロット２０１および２０３には、いずれも「アドレスＡ」に対して処理を行なうことが指定されている。
【００３８】
初期化が終了すると、プロセッサコア１００は、「未処理」に設定されている実行スロットの中で同時処理される実行スロットを特定するとともに、同時処理される実行スロットがアクセスするアドレスに重複があるか否かを判断する（（２）アドレス重複確認）。すなわち、プロセッサコア１００は、実行スロットに対応するアドレスの中で同一のものがあるか否かを判断する。
【００３９】
アトミック命令では同じアドレスへのアクセスが競合しないように、実行スロット間で排他処理が実行される。すなわち、アドレスに重複がある場合には、プロセッサコア１００は、アドレスが重複している実行スロットのうち、ただ１つだけを「未処理」に維持し、その他の実行スロットについては、一時的に無効化する（図２中の符号２４２で示される実行スロット）。
【００４０】
（２）アドレス重複確認の具体的な手順例を考える際は、以下のようなハードウェア的な制約を考慮する必要がある。
【００４１】
図１に示すように、マルチコアプロセッサ１０では、複数のプロセッサコア１００が共有キャッシュ１１０を共有するように接続されている。マルチプロセッサ１０内において、１メモリサイクル内では、共有キャッシュ１１０の予めハードウェアによって定められた限られた数のキャッシュラインにしかアクセスできないという制約が存在する。そのため、プロセッサコア１００は、ＳＩＭＤアトミック命令のような複数のアドレスに対するメモリ操作を行うＳＩＭＤ命令を実行する場合、各メモリサイクルでは限られた数の同じキャッシュラインに対するアクセスを行なう実行スロットのみ並列に実行し、全実行スロットの命令を完了するまでには１以上の複数のメモリサイクルにわたって命令の実行を行なうことになる。以下では１メモリサイクルでアクセス可能なキャッシュライン数が１であるとして説明を行なうが、１メモリサイクルでアクセス可能なキャッシュライン数が２以上の場合でも、アクセスするキャッシュラインの決定部分で複数を選択し、それぞれのキャッシュラインについて、関連する実行スロットのみが有効であると考えることで、同様に処理可能となる。このような制約のもとで、アドレス重複確認の具体的な手順を以下で説明する。
【００４２】
プロセッサコア１００は、「未処理」に設定されている実行スロットの中で、実行スロットの番号が最小となる実行スロットを抽出し、その抽出した実行スロットに対応するアドレスをアドレスＸとして設定する。そして、プロセッサコア１００は、他の「未処理」に設定されている実行スロットに対応するそれぞれのアドレスと、アドレスＸとを比較し、同一のキャッシュライン上のアドレスにない実行スロットを一時的に無効化する。さらに、同一キャッシュライン内の各アドレスについて、命令を実行すべき実行スロットを定めるための処理を行なう。
【００４３】
図３は、命令を実行すべき実行スロットを定めるための処理を説明するための図である。
【００４４】
典型的には、同一のキャッシュライン内にある、同時処理可能なアドレスの数は、キャッシュラインサイズとアトミック命令のデータ幅とによって定まる。図３（Ａ）に示すように、例えば、キャッシュラインサイズが６４ｂｙｔｅ（２６）であり、データ幅が３２ｂｉｔ（＝４ｂｙｔｅ（２２））である場合には、同一キャッシュライン上にある、同時処理可能なアドレスの数は６４／４＝１６（２４）となる。これらのアドレスの順に、０−１５の番号を付け、番号ごとに実行スロット数のｂｉｔ数のフラグを設ける。図３（Ｂ）に示すように、フラグの各ビットは、対応する実行スロットが当該アドレスへのアクセスである場合に「１」となり、異なる場合（すなわち、実行スロットが無効である場合、または、当該アドレスへのアクセスではない場合）に「０」となるようにする。
【００４５】
このように定めたアドレスごとのフラグについて、「１」となる最小のｂｉｔ番号が、当該アドレスへのアクセスを許された実行スロットの番号とする。各実行スロットは、命令の作用アドレスに対応するアドレスのフラグから定められたアクセスを許された実行スロットの番号が自分の実行スロットの番号と異なる場合は、実行スロットを一時的に無効化する。
【００４６】
図３を参照して、以下のような手順で、命令を実行すべき実行スロットが決定される。まず、上位アドレスでキャッシュラインが判定され、同一キャッシュラインアドレスの下位部分で、アドレスを分類して、各アドレスにアクセスする実行スロットが決定される。この場合、（１）実行スロット０のキャッシュラインが選択され、（２）キャッシュラインの異なる実行スロット３を一時無効化され、（３）キャッシュラインの異なるアドレスごとにアクセス要求のある実行スロットが集計される（集計結果は図３（Ｂ）のテーブルに格納される）。（４）各アドレスにアクセスする実行スロットが決定される。この例では、アドレス１にアクセス可能なのは実行スロット１であり、アドレス３にアクセス可能なのは実行スロット０となる。そして、それ以外の実行スロット（スロット２）は無効化される。
【００４７】
なお、並列実行可能な実行スロット数が少ない場合には、キャッシュラインの異なるアドレスごとにフラグを生成するのではなく、各実行スロットに対応するアドレス同士のキャッシュライン内アドレスを示すビット同士を全比較して重複を排除するように実装してもよい。
【００４８】
このように、プロセッサコア１００は、同一アドレスへの複数のアクセスのうち、ただ１つだけを有効化して、その他のアクセスを一時的に無効化する。図２に示す例では、実行スロット２０１および実行スロット２０３のいずれにおいても「アドレスＡ」へのアクセスが指定されているので、実行スロット２０１のみが有効化されて、実行スロット２０３については一時的に無効化される。
【００４９】
続いて、「未処理」に設定されている（すなわち、有効化されている）実行スロットに指定されているアドレスについて、プロセッサコア１００は、アトミック処理（リード・モディファイ・ライト：メモリからのデータ読み込み、更新後データの計算、更新後データのメモリへの書き込み）を実行する（（３）アトミック処理）。プロセッサコア１００は、最初のメモリからのデータ読み込みによって得られた値を、対応する戻り値領域へ書き込む。そして、プロセッサコア１００は、指定されたアトミック処理の実行が完了した実行スロットを「処理済」に設定する。
【００５０】
図２に示す例では、プロセッサコア１００は、命令の実行が成功したことを示す成否結果値２３１，２３２，２３４を戻り値領域２２１，２２２，２２４へ書き込む。また、プロセッサコア１００は、一時的に無効化した実行スロット２０３に対応するフラグ領域２１３を「未処理」に再設定する。
【００５１】
そして、プロセッサコア１００は、「未処理」に設定されている実行スロットが存在しているか否を判断する（（４）未処理の実行スロットの確認）。「未処理」に設定されている実行スロットが存在している場合には、上述の処理（図２中の符号２４０＃で示される３つの処理）が繰り返され、そうでなければ、ＳＩＭＤ命令２００＃の実行が終了する。
【００５２】
図２に示す例では、実行スロット２０３が「未処理」のままであるので、（５）アドレス重複確認、（６）アトミック処理、（７）未処理の実行スロットの確認が実行される。この結果、プロセッサコア１００は、成功フラグ２３３を戻り値領域２２３へ書き込む。符号２４０＃で示される３つの処理が複数回（図２の例では、２回）繰り返して実行されることで、実行スロットのすべてが「処理済」に設定されると、ＳＩＭＤ命令２００＃の実行が完了する。
【００５３】
図２に示すように、関連技術に係るアトミック命令の処理手順においては、ＳＩＭＤ命令２００＃に含まれる実行スロットのうち、有効化された実行スロットの各々について１回だけアトミック処理が実行される。このとき、互いに重複したアドレスが指定された実行スロット同士を並列実行できないので、アドレスが重複している場合には、それらの実行スロットのうち１つだけを有効化するとともに、それ以外の実行スロットについては処理を後回しにするという手順で、すべての実行スロットが処理済になるまで処理が繰り返される。このような処理手順によって、各実行スロットについて指定されているアドレスのデータに対して、リード・モディファイ・ライトがアトミックに処理される。
【００５４】
（ｂ３：ＣＡＳ命令）
以下、アトミックに処理されるＳＩＭＤ命令の一例として、コンペア・アンド・スワップ（Compare-And-Swap）命令（以下、「ＣＡＳ命令」とも総称する。）を、上述の図２に示す処理手順に従って実行する場合について説明する。
【００５５】
ＣＡＳ命令は、指定されたアドレスに格納されているデータ（値）を読み込み、それを命令の結果として返すとともに、その読み込んだ第１のデータと指定された第２のデータとを比較し、両データが等しい場合に、当該指定されたアドレスに第３のデータを書き込むアトミック命令である。
【００５６】
実行スロットにＣＡＳ命令が指定されている場合には、メモリの指定されたアドレスからデータを読み込み、読み込んだデータと旧データとを比較し、両データが一致していた場合にのみ、新データをメモリへ書き込むという処理が実行される。ＣＡＳ命令では、読み込んだデータの比較結果が実行の結果（戻り値）として返される。すなわち、結果（戻り値）は、該当の実行スロットに対応する戻り値領域へ書き込まれる。
【００５７】
（ｂ４：関連技術に係るＣＡＳ命令の実装・動作およびそれを用いたｌｏｃｋ−ｆｒｅｅアルゴリズム）
以下、図２に示す関連技術に係る処理手順に従って実装されるＣＡＳ命令（以下、本実施の形態に実装形態と区別するために、便宜上、「ＣＡＳ命令１」または「atomic-compare-and-swap1」とも記述する。）の処理手順について説明する。併せて、ＣＡＳ命令１を用いた、ｌｏｃｋ−ｆｒｅｅアルゴリズムについて説明する。
【００５８】
ｌｏｃｋ−ｆｒｅｅアルゴリズムとは、複数のスレッド間で共有されるデータ（典型的には、共有キャッシュ１１０に格納されるデータ）に対して、いずれかのスレッドがロックをかけないで処理を実行するアルゴリズムである。すなわち、複数のスレッドが同時並行的に、共有データを毀損することなく、読み込みおよび書き込みを実現する。例えば、あるスレッドの実行に必要なデータが他のスレッドによってロックされており、そのロックが解除されるまで、スレッドの実行が待たされるようなことはない。
【００５９】
このようなｌｏｃｋ−ｆｒｅｅアルゴリズムとは、重み付けヒストグラム計算、複数種別の待ち行列登録といった処理に利用される。
【００６０】
図４は、関連技術に係るＣＡＳ命令１を用いたｌｏｃｋ−ｆｒｅｅアルゴリズム３００＃の処理手順を示すフローチャートである。図４に示すフローチャートは、マルチコアプロセッサ１０で実行されるプログラムの一部の処理を示すものであり、各ステップに対応付けて、プログラムに用いられるコードの一例を示す。
【００６１】
図４を参照して、プロセッサコア１００は、データ更新を準備する（ステップＳ１００）。具体的には、プロセッサコア１００は、指定されたアドレスに格納されている更新前データから更新後データを計算するための変数％ｉｎｐｕｔをセットする（コード３０２）。
【００６２】
続いて、プロセッサコア１００は、更新前データを読み込む（ステップＳ１０２）。具体的には、プロセッサコア１００は、指定されたアドレス（ａｄｄｒｅｓｓＸ）に格納されている更新前データを読み出して、変数％ｏｌｄをセットする（コード３０４）。
【００６３】
続いて、プロセッサコア１００は、更新後データを計算する（ステップＳ１０４）。具体的には、プロセッサコア１００は、指定された演算式に従って、変数％ｏｌｄと変数％ｉｎｐｕｔとをパラメータとして、更新後データ（変数％ｎｅｗ）を計算する（コード３０６）。
【００６４】
続いて、プロセッサコア１００は、更新後データの書き込みを試行する（ステップＳ１０６）。具体的には、プロセッサコア１００は、ＣＡＳ命令１（atomic-compare-and-swap1）を実行して、指定されたアドレス（ａｄｄｒｅｓｓＸ）に格納されているデータと更新後データを計算する際に用いた更新前データ（すなわち、変数％ｏｌｄの値）とを比較し、両データが一致していれば、更新後データ（すなわち、変数％ｎｅｗの値）を指定されたアドレスへ書き込む（コード３０８）。ＣＡＳ命令１（atomic-compare-and-swap1）の戻り値は、指定されたアドレスに格納されていたデータであり、変数％ｒｅｔにセットされる。そこで、現ステップにおける指定されたアドレスに格納されているデータ（すなわち、変数％ｒｅｔの値）と更新後データを計算する際に用いた更新前データ（すなわち、変数％ｏｌｄの値）とを比較し、両データが一致していれば、変数％ｃｏｎｄに「ｔｒｕｅ（真）」がセットされ、そうでなければ、変数％ｃｏｎｄには「ｆａｌｓｅ（偽）」がセットされる（コード３１０）。
【００６５】
更新後データの書き込みが成功した場合（ステップＳ１０６において、変数％ｃｏｎｄ＝＝ｔｒｕｅの場合：コード３１２）、処理は終了する。これに対して、更新後データの書き込みが失敗した場合（ステップＳ１０６において、変数％ｃｏｎｄ＝＝ｆａｌｓｅの場合：コード３１４）、更新後データを再度計算するために、プロセッサコア１００は、更新前データを更新する（ステップＳ１０８）。この場合は、実行中のスレッドによる更新後データの計算中に、別のスレッドが対象のアドレスのデータを変更したことを意味し、更新前データの更新が必要となる。具体的には、プロセッサコア１００は、変数％ｒｅｔの値を変数％ｏｌｄにセットする（コード３１６）。そして、ステップＳ１０４以下の処理が再度実行される。
【００６６】
（ｂ５：関連技術に係るＣＡＳ命令（ＣＡＳ命令１）を用いたｌｏｃｋ−ｆｒｅｅアルゴリズムに適用した場合の同一アドレスに対する複数の実行スロットのアトミック処理回数）
（ｉ）実行スロット数が４の場合
図５は、図４に示すｌｏｃｋ−ｆｒｅｅアルゴリズム３００＃の実行過程におけるメモリに格納されるデータの変化を説明するための図である（実行スロット数が４の場合）。
【００６７】
図５には、ＳＩＭＤ命令の実行スロット数が４である場合を示す。図４に示されるｌｏｃｋ−ｆｒｅｅアルゴリズム３００＃が複数スレッドで実行される場合、コンパイラにより、４つのスレッドに対する処理が単一の命令流としてＳＩＭＤＣＡＳ命令１を含むプロセッサ命令列に変換されマルチコアプロセッサ１０上で実行される（図４のステップＳ１０６）。図５では、マルチコアプロセッサ１０に与えられたｌｏｃｋ−ｆｒｅｅアルゴリズム３００＃中のＳＩＭＤＣＡＳ命令１を実行する際の動作例を示している。
【００６８】
図５に示す例では、実行スロット２０１および２０３のＣＡＳ命令１の操作対象アドレスとして、いずれも「アドレスＡ」が指定されている（図４のコード３０８中のａｄｄｒｅｓｓＸに対応）ものとする。そのため、図５（Ａ）中の符号２４０＃で示される３つの処理（アドレス重複確認、アトミック処理、未処理の実行スロットの確認）が２回繰り返される。
【００６９】
但し、実行スロット２０３に指定されている命令の実行が終了すると、戻り値（図４のコード３０８内の変数％ｒｅｔに対応）は、実行スロット２０１に指定されている命令の実行によりアドレスＡに書き込まれた更新後データとなり、これは通常更新前の値とは異なる。すなわち、図４に示されるｌｏｃｋ−ｆｒｅｅアルゴリズム３００＃のステップＳ１０６において、更新後データの書き込みは失敗したと判断される。そのため、図４に示されるステップＳ１０４およびＳ１０６が再度実行される。すなわち、図５（Ｂ）に示されるように、ＣＡＳ命令１が再度実行される。
【００７０】
図５（Ｂ）に示すように、２回目のＣＡＳ命令１においては、ＳＩＭＤ命令２００＃に指定される複数の命令のうち、実行スロット２０３に指定されている命令のみが実行される。
【００７１】
図５（Ａ）および図５（Ｂ）に示すように、図４に示されるｌｏｃｋ−ｆｒｅｅアルゴリズム３００＃が実行されると、図５中の符号２４０＃で示される３つの処理（アドレス重複確認、アトミック処理、未処理の実行スロットの確認）がトータルで３回繰り返されることになる。
【００７２】
（ｉｉ）実行スロット数が８の場合
図６は、図４に示すｌｏｃｋ−ｆｒｅｅアルゴリズム３００＃の実行過程におけるメモリに格納されるデータの変化の別の例を説明するための図である（実行スロット数が８の場合）。
【００７３】
図６（Ａ）に示すように、１回目のＣＡＳ１命令（ＳＩＭＤ命令２００＃）の実行が開始されると（（１）命令実行開始）、プロセッサコア１００は、初期化などの所定の処理を行った上で、同時処理される実行スロットがアクセスするアドレスに重複があるか否かを判断する（（２）アドレス重複確認）。図６（Ａ）に示す例では、実行スロット２０１，２０３，２０６のいずれにおいても「アドレスＡ」へのアクセスが指定されているので、実行スロット２０１のみが有効化されて、実行スロット２０３，２０６については一時的に無効化される（図６（Ａ）の※１参照）。また、実行スロット２０４および２０８のいずれにおいても「アドレスＣ」へのアクセスが指定されているので、実行スロット２０４のみが有効化されて、実行スロット２０８については一時的に無効化される（図６（Ａ）の※２参照）。この状態で、有効化されている実行スロットに指定されている命令について、プロセッサコア１００は、アトミック処理（ＣＡＳ命令１）を実行する（（３）アトミック処理）。プロセッサコア１００は、ＣＡＳ命令１の実行に伴い各実行スロットの作用アドレス上のメモリを更新するとともに、戻り値領域にメモリから読み込んだ値を書き込む。また、アトミック処理を実行した実行スロット２０１，２０２，２０４，２０５，２０７についてフラグ領域２１３を処理済みに設定する。さらに、プロセッサコア１００は、一時的に無効化した実行スロット２０３，２０６，２０８に対応するフラグ領域２１３を「未処理」に再設定する。
【００７４】
そして、プロセッサコア１００は、「未処理」に設定されている実行スロットが存在しているか否を判断する（（４）未処理の実行スロットの確認）。続いて、（５）アドレス重複確認、（６）アトミック処理、（７）未処理の実行スロットの確認が実行される。このとき、実行スロット２０３および２０６のいずれにおいても「アドレスＡ」へのアクセスが指定されているので、実行スロット２０３のみが有効化されて、実行スロット２０６については再度一時的に無効化される（図６（Ａ）の※３参照）。
【００７５】
符号２４０＃で示される３つの処理が２回繰り返された後であっても、実行スロット２０６が依然として「未処理」であるので、（８）アドレス重複確認、（９）アトミック処理、（１０）未処理の実行スロットの確認が実行される。
【００７６】
図６（Ａ）に示される１回目のＣＡＳ命令１の実行が終了したとしても、実行スロット２０３，２０６，２０８に対応する戻り値（図４のコード３０８内の変数％ｒｅｔに対応）は、他の実行スロットにより変更された更新後データとなる。すなわち、実行スロット２０３，２０６，２０８にそれぞれ対応するｌｏｃｋ−ｆｒｅｅアルゴリズム３００＃（図４参照）では、ステップＳ１０６において、更新後データの書き込みは失敗したと判断される。そのため、図６（Ｂ）に示されるように、ＣＡＳ命令１が再度実行される。
【００７７】
図６（Ｂ）において、実行スロット２０３および２０６のいずれにおいても「アドレスＡ」へのアクセスが指定されているので、図６（Ｂ）中の符号２４０＃で示される３つの処理（アドレス重複確認、アトミック処理、未処理の実行スロットの確認）は２回繰り返される。図６（Ｂ）に示される２回目のＣＡＳ命令１の実行が終了したとしても、実行スロット２０６に対応する戻り値（図４のコード３０８内の変数％ｒｅｔに対応）は、他の実行スロットにより変更された更新後データとなる。そのため、図６（Ｃ）に示されるように、ＣＡＳ命令１がさらに再度実行される。
【００７８】
図６（Ｃ）において、３回目のＣＡＳ命令１では、実行スロット２０６に指定されている命令について、符号２４０で示される３つの処理（アドレス重複確認、アトミック処理、未処理の実行スロットの確認）が１回実行される。
【００７９】
図６（Ａ）〜図６（Ｃ）に示すように、図４に示されるｌｏｃｋ−ｆｒｅｅアルゴリズム３００＃が実行されると、図６中の符号２４０＃で示される３つの処理（アドレス重複確認、アトミック処理、未処理の実行スロットの確認）がトータルで６回繰り返されることになる。
【００８０】
関連技術に係るアトミック命令（ＣＡＳ命令１）でのアトミック処理の実行回数について説明する。以降の説明では説明の都合上、異なるアドレスもすべて同一のキャッシュライン上に載っていて、並列処理が可能なものとして説明する。異なるキャッシュラインのアドレスが含まれる場合は、それぞれのキャッシュラインでアトミック処理の実行回数を計算し、それをすべて足し合わせたものが実際のアトミック処理の回数となる。
【００８１】
図５に示すように、アドレスＡが２つの実行スロットで重複している場合には、１回目のＣＡＳ命令１で最大の重複数Ｎ（＝２）と同じ回数のアトミック処理（符号２４０＃で示される３つの処理）が実行される。複数回実行されるアトミック処理のうち、アドレスが重複している複数の実行スロットのうち、１つの実行スロットについてのみ、更新後データの書き込みが成功する。すなわち、２回目のＣＡＳ命令１は、最大の重複数Ｎから１だけ引いた数のアドレス重複がある状態で実行される。その結果、１回目のＣＡＳ命令１の実行時には、アトミック処理が２回実行され、２回目のＣＡＳ命令１の実行時には、アトミック処理が１回実行され、アトミック処理の総実行数は３回となる。
【００８２】
また、図６に示すように、アドレスＡが３つの実行スロットで重複しており、アドレスＣが２つの実行スロットで重複している場合には、１回目のＣＡＳ命令１で最大の重複数Ｎ（＝３）と同じ回数のアトミック処理（符号２４０＃で示される３つの処理）が実行される。複数回実行されるアトミック処理のうち、アドレスが重複している複数の実行スロットのうち、１つの実行スロットについてのみ、更新後データの書き込みが成功する。すなわち、それ以降のＣＡＳ命令１は、最大の重複数Ｎから１ずつ引いた数のアドレス重複がある状態で実行される。
【００８３】
その結果、１回目のＣＡＳ命令１の実行時には、アトミック処理が３回実行され、２回目のＣＡＳ命令１の実行時には、アトミック処理が２回実行され、３回目のＣＡＳ命令１の実行時には、アトミック処理が１回実行され、アトミック処理の総実行数は６回となる。
【００８４】
以上のように、ｌｏｃｋ−ｆｒｅｅアルゴリズム３００＃が１回実行されると、アトミック処理の総実行数は、最小で、Ｎ×（Ｎ＋１）／２回となる。ここで、Ｎは、同一のＳＩＭＤ命令２００＃に含まれるアドレスの最大の重複数Ｎを示す。
【００８５】
なお、独立にマルチコアプロセッサ１０内に存在する別のプロセッサコア１００で実行される別のスレッドが同一のアドレスに同時アクセスする場合には、処理回数がさらに増加する。
【００８６】
（ｂ６：実施の形態１に従うＣＡＳ類似命令の実装・動作およびそれを用いたｌｏｃｋ−ｆｒｅｅアルゴリズム）
実施の形態１に従うマルチコアプロセッサ１０（または、プロセッサコア１００の各々）で採用する、関連技術に係るＣＡＳ命令に類似した命令の実装・動作について説明する。以下、関連技術に係るＣＡＳ命令に類似した命令を、説明の便宜上、「ＣＡＳ命令２」または「atomic-compare-and-set2」とも記述する。ＳＩＭＤ命令セット上で定義されるＣＡＳ命令２は、各実行スロットで指定されたアドレスに格納されているデータ（値）を読み込み、その読み込んだ第１のデータと指定された第２のデータとを比較し、両データが等しい場合には命令の実行が成功したものとして、当該指定されたアドレスに第３のデータを書き込むという一連の処理をアトミックに行う命令である。さらに比較の際に等しかった場合には成功を表す戻り値（通常１）、等しくなかった場合には、失敗を表す戻り値（通常０）を返す。ただし、同一アドレスにアクセスする実行スロットが複数あった場合にただ一つについてのみ実際のアトミック処理を行い、その他の実行スロットについてはアトミック処理を行わず、常に失敗を表す戻り値を返すものである。
【００８７】
ＣＡＳ命令２が指定されたＳＩＭＤ命令２００が実行されると、以下のように動作する。
【００８８】
実施の形態１に従うコンピュータ１に実装されるＣＡＳ命令２の処理手順について説明する。図７は、実施の形態１に従うＣＡＳ命令２の処理手順を説明するための模式図である。図７を参照して、マルチコアプロセッサ１０に与えられるＳＩＭＤ命令２００は、４つの実行スロット２０１〜２０４（ｓｌｏｔ０〜ｓｌｏｔ３）に適用される。実行スロット２０１〜２０４の各々には、並列実行される同一のアトミック命令（ＣＡＳ命令２）および各実行スロットに異なる入力データが指定される。
【００８９】
実行スロット２０１〜２０４に対応付けられて、フラグ領域２１１〜２１４、および、戻り値領域２２１〜２２４がメモリ領域内にそれぞれ設けられる。フラグ領域２１１〜２１４は、対応する実行スロットに指定されている命令の実行状態を格納するための領域である。戻り値領域２２１〜２２４は、対応する実行スロットに指定されている命令の実行によって得られた戻り値を格納するための領域である。フラグ領域２１１〜２１４および戻り値領域２２１〜２２４は、共有キャッシュ１１０の特定のアドレス範囲を用いて実装してもよいし、特殊レジスタを用いて実装してもよい。
【００９０】
まず、それぞれの実行スロットにＣＡＳ命令２が指定されたＳＩＭＤ命令２００の実行が開始されると（（１）命令実行開始）、フラグ領域２１１〜２１４に格納されているそれぞれの値が初期化される。図７に示す処理手順においては、フラグ領域２１１〜２１４の各々には、対応する実行スロットに指定されているＣＡＳ命令２について、「未処理」または「処理済」を意味する値が設定される。
【００９１】
初期化において、ＣＡＳ命令２が有効に指定されている実行スロットに対応するフラグ領域には、「未処理」を意味する値が設定され、命令が無効に指定されている実行スロットに対応するフラグ領域には、「処理済」を意味する値が設定される。
【００９２】
例えば、フラグ領域２１１〜２１４をメモリの特定のアドレス範囲を用いて実装する場合には、状態値に応じた特殊値（例えば、「−１」または「ＦＦＦＦ」など）が指定され、あるいは、フラグ領域２１１〜２１４を特殊レジスタにより実装する場合には、それらの特殊レジスタの値が、状態値に応じてオフまたはオンに設定される。
【００９３】
図７において、ＳＩＭＤ命令２００内に記載される「アドレスＡ」、「アドレスＢ」、「アドレスＣ」は、対応する実行スロット２０１〜２０４のＣＡＳ命令２が作用する先のアドレスを意味する。図７に示す例では、実行スロット２０１および２０３には、いずれも「アドレスＡ」に対して処理を行なうことが指定されている。
【００９４】
初期化が終了すると、プロセッサコア１００は、「未処理」に設定されている実行スロットの中で同時処理される実行スロットを特定するとともに、同時処理される実行スロットがアクセスするアドレスに重複があるか否かを判断する（（２）アドレス重複確認）。すなわち、プロセッサコア１００は、ＣＡＳ命令２に対応する複数の実行スロットのうち指定されたアドレスが重複している実行スロットを特定する。言い換えれば、プロセッサコア１００は、実行スロットに対応するアドレスの中で同一のものがあるか否かを判断する。
【００９５】
上述したように、マルチプロセッサ１０内において、１メモリサイクル内では、共有キャッシュ１１０の予めハードウェアによって定められた限られた数のキャッシュラインにしかアクセスできないという制約が存在する。そのためプロセッサコア１００はＳＩＭＤアトミック命令のような複数のアドレスに対するメモリ操作を行うＳＩＭＤ命令を実行する場合、各メモリサイクルでは限られた数の同じキャッシュラインに対するアクセスを行う実行スロットのみ並列に実行し、全実行スロットの命令を完了するまでには１以上の複数のメモリサイクルにわたって命令の実行を行うことになる。以下では１メモリサイクルでアクセス可能なキャッシュライン数が１であるとして説明を行うが、１メモリサイクルでアクセス可能なキャッシュライン数が２以上の場合でも、アクセスするキャッシュラインの決定部分で複数を選択し、それぞれのキャッシュラインについて、関連する実行スロットのみが有効であると考えることで、同様に処理可能となる。このような制約のもとで、アドレス重複確認の具体的な手順を以下で説明する。
【００９６】
アドレスに重複がある場合には、プロセッサコア１００は、アドレスが重複している実行スロットのうち、ただ１つだけを「未処理」に維持し、その他の実行スロットについては、「処理済」に設定する。併せて、プロセッサコア１００は、アドレスの重複により「処理済」に設定した実行スロットについて、ＣＡＳ命令２の実行が失敗したことを示す結果（戻り値）を、対応する戻り値領域へ書き込む。
【００９７】
（２）アドレス重複確認の具体的な手順例としては、以下のような処理が実行される。
プロセッサコア１００は、アドレスが重複している実行スロットのうち、実行スロットに割り当てられた番号に基づいて、実行する１つの実行スロットを決定する。より具体的には、プロセッサコア１００は、「未処理」に設定されている実行スロットの中で、実行スロットの番号が最小（または、最大）となる実行スロットを抽出し、その抽出した実行スロットに対応するアドレスをアドレスＸとして設定する。そして、プロセッサコア１００は、他の「未処理」に設定されている実行スロットに対応するそれぞれのアドレスと、アドレスＸとを比較し、アドレスＸと同一のキャッシュライン上にない実行スロットを一時的に無効化する。さらに、同一キャッシュライン内の各アドレスについて、命令を実行すべき実行スロットを定めるための処理を行なう。
【００９８】
典型的には、同一のキャッシュライン内にある、同時処理可能なアドレスの数は、キャッシュラインサイズとアトミック命令のデータ幅とによって定まる。図３（Ａ）に示すように、例えば、キャッシュラインサイズが６４ｂｙｔｅ（２６）であり、データ幅が３２ｂｉｔ（＝４ｂｙｔｅ（２２））である場合には、同一キャッシュライン上にある、同時処理可能なアドレスの数は６４／４＝１６（２４）となる。これらのアドレスの順に、０−１５の番号を付け、番号ごとに実行スロット数のｂｉｔ数のフラグを設ける。図３（Ｂ）に示すように、フラグの各ビットは、対応する実行スロットが当該アドレスへのアクセスである場合に「１」となり、異なる場合（すなわち、実行スロットが無効である場合、または、当該アドレスへのアクセスではない場合）に「０」となるようにする。
【００９９】
このように定めたアドレスごとのフラグについて、「１」となる最小のｂｉｔ番号が、当該アドレスへのアクセスを許された実行スロットの番号とする。
【０１００】
なお、並列実行可能な実行スロット数が少ない場合には、キャッシュラインの異なるアドレスごとにフラグを生成するのではなく、各実行スロットに対応するアドレス同士のキャッシュライン内アドレスを示すビット同士を全比較して重複を排除するように実装してもよい。
【０１０１】
各実行スロットは、命令の作用アドレスに対応するアドレスのフラグから定められたアクセスを許された実行スロットの番号が自分の実行スロットの番号と異なる場合は、「処理済」に設定するとともに、命令の実行が失敗したことを示す結果（戻り値）を対応する戻り値領域へ書き込む。一方、同一のキャッシュライン上のアドレスであって、フラグの状態によりそのアドレスへのアクセスが許された実行スロットについては、そのまま以降の処理に移る。
【０１０２】
このように、プロセッサコア１００は、同一アドレスへの複数のアクセスのうち、ただ１つだけを有効化して、その他のアクセスを「処理済」（但し、ＣＡＳ命令２の実行は失敗）に設定する。図７に示す例では、プロセッサコア１００は、失敗結果値２３３Ｆを戻り値領域２２３へ書き込む。
【０１０３】
続いて、「未処理」に設定されている（すなわち、有効化されている）実行スロットに指定されているＣＡＳ命令２について、プロセッサコア１００は、アトミック処理（リード・モディファイ・ライト：メモリからのデータ読み込み、更新後データの計算、更新後データのメモリへの書き込み）を実行する（（３）アトミック処理）。プロセッサコア１００は、最初のメモリからのデータ読み込みによって得られた、成功したことを示す結果（戻り値）を、対応する戻り値領域へ書き込む。そして、プロセッサコア１００は、各実行スロットについて、ＣＡＳ命令２のアトミック処理の際に行われた比較結果により、成功もしくは失敗を表す成否結果値を、対応する戻り値領域へ書き込む。そして、プロセッサコア１００は、指定されたアトミック処理の実行が完了した実行スロットを「処理済」に設定する。
【０１０４】
図７に示す例では、プロセッサコア１００は、ＣＡＳ命令２のアトミック処理の成否により成否結果値２３１，２３２，２３４を戻り値領域２２１，２２２，２２４へ書き込む。
【０１０５】
以上のように、プロセッサコア１００は、アドレスが重複している実行スロットに指定されたＣＡＳ命令２および入力データのうち１つの実行スロットでのみアトミック処理を実行し、当該実行の結果を返すとともに、残りの実行スロットについては、アトミック処理を実行することなく、ＣＡＳ命令２の実行が失敗したことを示す結果を返す。図７に示すように、実施の形態１においては、プロセッサコア１００は、アドレスが重複している実行スロットのうち１つの実行スロットの命令実行前に、残りの実行スロットについて、ＣＡＳ命令２の実行が失敗したことを示す結果を返すようになっている。先に、ＣＡＳ命令２の実行が失敗したことを示す失敗結果値を書き込むことで、後続の未処理の実行スロットの確認の処理を簡素化できる。
【０１０６】
但し、処理の都合上、成否結果値２３１，２３２，２３４を戻り値領域２２１，２２２，２２４へ書き込むのと同時に、失敗結果値２３３Ｆを戻り値領域２２３へ書き込むようにしてもよい。
【０１０７】
そして、プロセッサコア１００は、一時的に無効化されている実行スロットを「未処理」状態に設定し、「未処理」に設定されている実行スロットが存在しているか否を判断する（（４）未処理の実行スロットの確認）。実施の形態１に従うＳＩＭＤ命令２００においては、互いに重複したアドレスが指定された複数の実行スロットが存在する場合には、１つの実行スロットのみを有効化して、それ以外の実行スロットについては、「処理済」（すなわち、無効）に設定される。
【０１０８】
そのため、単一のＳＩＭＤアトミック命令の実行について、同一のアドレスへの処理が高々１回で済むことになる。
【０１０９】
図７に示すように、実施の形態１に従うＣＡＳ命令２の処理手順においては、ＳＩＭＤ命令２００に含まれる実行スロットのうち、互いに重複したアドレスが指定された実行スロットが存在する場合には、１つの実行スロットについてのみアトミック処理（典型的には、メモリへのアクセスを含む処理）が実行され、それ以外の実行スロットについては、アトミック処理を実行することなく、ＣＡＳ命令２の実行が失敗したことを示す結果（戻り値）を返す。これによって、図２に示すような繰り返しのアトミック処理を実行しない。すなわち、アトミック処理の実行前に、アドレスの重複を比較し、その比較結果に基づいて、ＣＡＳ命令２の実行が成功したこと、または、失敗したことを示す結果を戻すことになる。
【０１１０】
図８は、実施の形態１に従うＣＡＳ命令２を用いたｌｏｃｋ−ｆｒｅｅアルゴリズム３００の処理手順を示すフローチャートである。図８に示すフローチャートは、マルチコアプロセッサ１０で実行されるプログラムの一部の処理を示すものであり、各ステップに対応付けて、プログラムに用いられるコードの一例を示す。
【０１１１】
図８を参照して、プロセッサコア１００は、データ更新を準備する（ステップＳ１００）。具体的には、プロセッサコア１００は、指定されたアドレスに格納されている更新前データから更新後データを計算するための変数％ｉｎｐｕｔをセットする（コード３０２）。
【０１１２】
続いて、プロセッサコア１００は、更新前データを読み込む（ステップＳ１０２）。具体的には、プロセッサコア１００は、指定されたアドレス（ａｄｄｒｅｓｓＸ）に格納されている更新前データを読み出して、変数％ｏｌｄをセットする（コード３０４）。
【０１１３】
続いて、プロセッサコア１００は、更新後データを計算する（ステップＳ１０４）。具体的には、プロセッサコア１００は、指定された演算式に従って、変数％ｏｌｄと変数％ｉｎｐｕｔとをパラメータとして、更新後データ（変数％ｎｅｗ）を計算する（コード３０６）。
【０１１４】
続いて、プロセッサコア１００は、更新後データの書き込みを試行する（ステップＳ１１０）。具体的には、プロセッサコア１００は、ＣＡＳ命令２（atomic-compare-and-set2）を実行して、指定されたアドレス（ａｄｄｒｅｓｓＸ）に格納されているデータと更新後データを計算する際に用いた更新前データ（すなわち、変数％ｏｌｄの値）とを比較し、両データが一致していれば、更新後データ（すなわち、変数％ｎｅｗの値）を指定されたアドレスへ書き込む（コード３１８）。ＣＡＳ命令２（atomic-compare-and-set2）の戻り値は、ブーリアン型をとり、更新後データの書き込みが成功した場合には、「ｔｒｕｅ（真）」を返し、そうでなければ「ｆａｌｓｅ（偽）」を返す。すなわち、現ステップにおける指定されたアドレスに格納されているデータと更新後データを計算する際に用いた更新前データ（すなわち、変数％ｏｌｄの値）とが一致していれば、変数％ｃｏｎｄに「ｔｒｕｅ（真）」がセットされ、そうでなければ、変数％ｃｏｎｄには「ｆａｌｓｅ（偽）」がセットされる。
【０１１５】
更新後データの書き込みが成功した場合（ステップＳ１１０において、変数％ｃｏｎｄ＝＝ｔｒｕｅの場合：コード３２０）、処理は終了する。これに対して、更新後データの書き込みが失敗した場合（ステップＳ１１０において、変数％ｃｏｎｄ＝＝ｆａｌｓｅの場合：コード３２２）、ステップＳ１０２以下の処理が再度実行される。この場合は、実行中のスレッドによる更新後データの計算中に、別のスレッドが対象のアドレスのデータを変更したことを意味し、更新前データの再読み込みが必要となる。
【０１１６】
図４に示すｌｏｃｋ−ｆｒｅｅアルゴリズム３００＃とは異なり、実施の形態１に従うＣＡＳ命令２を用いたｌｏｃｋ−ｆｒｅｅアルゴリズム３００では、アトミック処理ではない、指定されたアドレスに格納されている更新前データの読み出しが、毎回実行される。これは、ＣＡＳ命令２ではＣＡＳ命令１と戻り値に関する仕様が異なり、当該メモリについての最新のデータを戻り値として取得することができないからである。但し、更新前データの読み出し処理は、アトミック処理でないため、キャッシュを利用することによりアトミック処理と比較すると格段に高速アクセスが可能である。また、仮に重複したアドレスを指定する別の実行スロットが存在したとしても、アトミック命令であるＣＡＳ命令２の実行時には、高々１回のアクセスで済むため、メモリアクセスに係る処理負荷が増大することはない。
【０１１７】
（ｂ７：実施の形態１に従うＣＡＳ類似命令（ＣＡＳ命令２）を用いたｌｏｃｋ−ｆｒｅｅアルゴリズムに適用した場合の同一アドレスに対する複数の実行スロットのアトミック処理回数）
以降の説明では説明の都合上、異なるアドレスもすべて同一のキャッシュライン上に載っていて、並列処理が可能なものとして説明する。異なるキャッシュラインのアドレスが含まれる場合は、それぞれのキャッシュラインでアトミック処理の実行回数を計算し、それをすべて足し合わせたものが実際のアトミック処理の回数となる。
【０１１８】
（ｉ）実行スロット数が４の場合
図９は、図８に示すｌｏｃｋ−ｆｒｅｅアルゴリズム３００の実行過程におけるメモリに格納されるデータの変化を説明するための図である（実行スロット数が４の場合）。
【０１１９】
図９には、図５と同様に、４つのアトミック命令を含むＳＩＭＤ命令２００がマルチコアプロセッサ１０へ与えられた場合の動作を示す。
【０１２０】
図９に示す例においても、実行スロット２０１および２０３に指定されている２つの命令では、いずれも「アドレスＡ」が作用アドレスとして指定されている（図８のコード３１８中のａｄｄｒｅｓｓＸに対応）ものとする。この場合、実行スロット２０１，２０２，２０４に指定されている命令は並列実行されるとともに、実行スロット２０３に指定されている命令に対しては、失敗結果値２３３Ｆが付与されて「処理済」に設定される。すなわち、実行スロット２０３については、戻り値（図８のコード３１８内の変数％ｃｏｎｄに対応）として、命令の実行が失敗したことを示す「ｆａｌｓｅ（偽）」が結果として戻される。
【０１２１】
図９（Ａ）中の符号２４０で示される３つの処理（アドレス重複確認、アトミック処理、未処理の実行スロットの確認）が１回実行されると、１回目のＣＡＳ命令２の実行は完了する。しかしながら、実行スロット２０３に設定されている命令については、戻り値として「ｆａｌｓｅ（偽）」が設定された状態であるので、これに対応するスレッドでは、更新前データの読み込み、更新後データの計算、更新後データの書き込み試行（図８のステップＳ１０２，Ｓ１０４，Ｓ１１０）が再度実行される。更新後データの書き込み試行（ステップＳ１１０）が再度実行されることで、図９（Ｂ）に示すように、２回目のＣＡＳ命令２が実行される。２回目のＣＡＳ命令２においても、符号２４０で示される３つの処理（アドレス重複確認、アトミック処理、未処理の実行スロットの確認）が１回実行される。
【０１２２】
（ｉｉ）実行スロット数が８の場合
図１０は、図８に示すｌｏｃｋ−ｆｒｅｅアルゴリズム３００の実行過程におけるメモリに格納されるデータの変化の別の例を説明するための図である（実行スロット数が８の場合）。
【０１２３】
これに対して、実施の形態１に従うＣＡＳ命令２を用いた場合について説明する。図１０には、図６と同様に、ＳＩＭＤ命令２００がマルチコアプロセッサ１０へ与えられた場合の動作を示す。
【０１２４】
図１０に示す例においても、実行スロット２０１，２０３，２０６では、いずれも「アドレスＡ」が作用アドレスとして指定されている（図８のコード３１８中のａｄｄｒｅｓｓＸに対応）ものとする。実行スロット２０４および２０８では、いずれも「アドレスＣ」が作用アドレスとして指定されている。
【０１２５】
図１０（Ａ）中の符号２４０で示される３つの処理（アドレス重複確認、アトミック処理、未処理の実行スロットの確認）が１回実行されると、１回目のＣＡＳ命令２の実行は完了する。実行スロット２０３，２０６，２０８に設定されている命令については、いずれも戻り値として「ｆａｌｓｅ（偽）」が設定された状態であるので、更新前データの読み込み、更新後データの計算、更新後データの書き込み試行（図８のステップＳ１０２，Ｓ１０４，Ｓ１１０）が再度実行される。更新後データの書き込み試行（ステップＳ１１０）が再度実行されることで、図１０（Ｂ）に示すように、２回目のＣＡＳ命令２が実行される。２回目のＣＡＳ命令２においても、符号２４０で示される３つの処理（アドレス重複確認、アトミック処理、未処理の実行スロットの確認）が１回実行される。
【０１２６】
さらに、実行スロット２０６に設定されている命令については、戻り値として「ｆａｌｓｅ（偽）」が設定された状態であるので、更新前データの読み込み、更新後データの計算、更新後データの書き込み試行（図８のステップＳ１０２，Ｓ１０４，Ｓ１１０）が再度実行される。更新後データの書き込み試行（ステップＳ１１０）が再度実行されることで、図１０（Ｃ）に示すように、３回目のＣＡＳ命令２が実行される。３回目のＣＡＳ命令２においても、符号２４０で示される３つの処理（アドレス重複確認、アトミック処理、未処理の実行スロットの確認）が１回実行される。
【０１２７】
図９に示すように、アドレスＡが２つの実行スロットで重複している場合において、１回目のＣＡＳ命令２でアトミック処理（符号２４０で示される３つの処理）が１回実行される。アドレスが重複している複数の実行スロットのうち、１つの実行スロットについてのみ、更新後データの書き込みが成功する。２回目のＣＡＳ命令２は、最大の重複数Ｎから１だけ引いた数のアドレス重複がある状態で実行される。但し、ＣＡＳ命令２の各実行において、アトミック処理（符号２４０で示される３つの処理）は１回だけしか実行されない。その結果、１回目および２回目のＣＡＳ命令２の実行時には、それぞれアトミック処理が１回ずつ実行され、アトミック処理の総実行数は２回となる。
【０１２８】
また、図１０に示すように、アドレスＡが３つの実行スロットで重複しており、アドレスＣが２つの実行スロットで重複している場合において、１回目のＣＡＳ命令２でアトミック処理（符号２４０で示される３つの処理）は１回実行される。アドレスが重複している複数の実行スロットのうち、１つの実行スロットについてのみ、更新後データの書き込みが成功する。すなわち、それ以降のＣＡＳ命令２は、最大の重複数Ｎから１ずつ引いた数のアドレス重複がある状態で実行される。
【０１２９】
その結果、１回目〜３回目のＣＡＳ命令２の実行時には、それぞれ、アトミック処理が１回ずつ実行され、アトミック処理の総実行数は３回となる。
【０１３０】
以上のように、ｌｏｃｋ−ｆｒｅｅアルゴリズム３００が１回実行されると、アトミック処理の総実行数は、最小で、Ｎ回となる。ここで、Ｎは、同一のＳＩＭＤ命令２００に含まれるアドレスの最大の重複数Ｎを示す。
【０１３１】
なお、独立に実行される別のスレッドが同一のアドレスに同時アクセスする場合には、処理回数がさらに増加する。
【０１３２】
以上をまとめると、マルチコアプロセッサ１０で並列実行される複数の実行スロットに指定されているアドレスの最大の重複数をＮとすると、関連技術に係るＣＡＳ命令１を用いたｌｏｃｋ−ｆｒｅｅアルゴリズム３００＃では、外部からのデータの書き込みがないという条件下で、Ｎ×（Ｎ＋１）／２回のアトミック処理が実行される。これに対して、実施の形態１に従うＣＡＳ命令２を用いたｌｏｃｋ−ｆｒｅｅアルゴリズム３００では、Ｎ回のアトミック処理が実行される。
【０１３３】
図４および図８に示すｌｏｃｋ−ｆｒｅｅアルゴリズムの実行に要する時間は、更新前データを読み込む処理（ステップＳ１０２）の実行に要する時間、および、更新後データの書き込みの試行に要する時間（ステップＳ１０６，Ｓ１１０）の和として概算できる。
【０１３４】
ここで、更新前データを読み込む時間（図４および図８のステップＳ１０２の実行に要する時間）をｔ１とする。また、図２，３，６〜９に示される、アドレス重複確認処理、および、未処理の実行スロットの確認処理については、マルチコアプロセッサ１０内でパイプライン処理されるため、処理時間としては実質的に無視できる。そのため、アトミック処理についてのみ考慮すればよい。以下では、アトミック処理に要する時間をｔ２とする。
【０１３５】
したがって、図４に示すｌｏｃｋ−ｆｒｅｅアルゴリズム３００＃の実行に要する時間Ｔ１は、以下の（１）式のように示すことができる。
【０１３６】
Ｔ１＝ｔ１×１＋ｔ２×Ｎ×（Ｎ＋１）／２  …（１）
また、図８に示すｌｏｃｋ−ｆｒｅｅアルゴリズム３００の実行に要する時間Ｔ２は、以下の（２）式のように示すことができる。
【０１３７】
Ｔ２＝（ｔ１＋ｔ２）×Ｎ  …（２）
ここで、アトミック処理の途中では、通常の処理と同様の、メモリからのデータ読み込み処理が発生するので、アトミック処理に要する時間ｔ２≫更新前データの読み込み時間ｔ１が成立する。ここで、アトミック処理は、バスへの負荷などを考慮すると、通常のメモリアクセス（メモリからのデータ読み込み処理）に比較して必要な処理負荷が非常に高い。そのため、アトミック処理に要する時間ｔ２は、更新前データの読み込み時間ｔ１に比較して十分に大きな値となる。
【０１３８】
（１）式および（２）式について検討すると、以下のようになる。
（ｉ）最大の重複数Ｎ＝１の場合
Ｔ１＝ｔ１＋ｔ２×１×２／２＝ｔ１＋ｔ２
Ｔ２＝（ｔ１＋ｔ２）×１＝ｔ１＋ｔ２＝Ｔ１
（ｉｉ）最大の重複数Ｎ＝２の場合
Ｔ１＝ｔ１＋ｔ２×２×３／２＝ｔ１＋３×ｔ２
Ｔ２＝（ｔ１＋ｔ２）×２＝ｔ１×２＋ｔ２×２＝Ｔ１＋（ｔ２−ｔ１）＞Ｔ１
したがって、最大の重複数Ｎ≧２の場合は、常に、Ｔ２＜Ｔ１が成立する。すなわち、マルチコアプロセッサ１０で並列実行される複数の実行スロットに指定されているアドレス間で重複があれば、本実施の形態に従うｌｏｃｋ−ｆｒｅｅアルゴリズム３００の実行時間は、関連技術に係るｌｏｃｋ−ｆｒｅｅアルゴリズム３００＃の実行時間より短縮できることを意味する。
【０１３９】
上述のように、実施の形態１に従うアトミック命令であるＣＡＳ命令２を用いることで、ｌｏｃｋ−ｆｒｅｅアルゴリズムの実装をより最適化することができる。この最適化によって、関連技術に係るアトミック命令であるＣＡＳ命令１を用いた場合に比較して、同様のｌｏｃｋ−ｆｒｅｅアルゴリズムをより少ないアトミック処理の実行回数で実現できる。
【０１４０】
＜Ｃ．実施の形態２＞
上述の実施の形態１に従うＣＡＳ命令２では、戻り値として、成功または失敗したことを示す結果が返されるが、複数の結果を戻すようにしてもよい。以下、実施の形態２においては、Ｃ＋＋（ＩＳＯ／ＩＥＣ１４８８２：２０１１）コア言語にて定義されている、「atomic::compare_exchange_weak」関数の外部動作仕様に準じた複数の結果を返すＣＳＷ命令（以下、命令を「atomic-compare-swap-weak」とも記述する。）の実装例について説明する。
【０１４１】
実施の形態２に従うＣＳＷ命令が実装されるコンピュータ、および、それに含まれるマルチコアプロセッサについては、上述の実施の形態１と同様であるので、詳細な説明は繰り返さない。
【０１４２】
それぞれの実行スロットにアトミック命令であるＣＳＷ命令が複数指定されているＳＩＭＤ命令がマルチコアプロセッサ１０へ与えられると、同時処理される実行スロットがアクセスするアドレスに重複があるか否かが判断される。互いに重複したアドレスが指定された複数の実行スロットが存在する場合には、１つの実行スロットのみが有効化され、それ以外の実行スロットについては無効化される。すなわち、互いに重複したアドレスが指定された実行スロットが存在する場合には、１つの実行スロットルのみアトミック処理（典型的には、メモリへのアクセスを含む処理）が実行され、それ以外の実行スロットについては、アトミック処理を実行することなく、命令の実行が失敗したことを示す結果（戻り値）を返す。
【０１４３】
実際にアトミック処理が実行された実行スロットについては、結果１として、命令の実行が成功したか否かを示す結果（フラグ値）が返され、結果２として、アトミック処理時に読み込んだデータ（値）が返される。このように、マルチコアプロセッサ１０は、アドレスが重複している実行スロットに指定されたアトミック命令のうち１つの実行スロットの命令実行後に、指定されたアドレスから読み込んだ値をさらなる結果（結果２）として返す。
【０１４４】
また、アトミック処理を実行していない実行スロットについては、結果１として、命令の実行が失敗したことを示す結果（フラグ値）が返される。また、アトミック処理を実行していない実行スロットについての結果２として、（１）実際にアトミック処理が実行された実行スロットの結果１が成功を示す場合には、当該実行スロットの命令がメモリに書き込んだデータ（値）が返され、（２）実際にアトミック処理が実行された実行スロットの結果１が失敗を示す場合には、当該１つの実行スロットが命令実行途中でメモリから読み込んだ値（すなわち、実行された実行スロットの結果２と同じ値）が返される。
【０１４５】
このように、マルチコアプロセッサ１０は、アドレスが重複している実行スロットに指定されたアトミック命令のうち実行されない残りのアトミック命令について、当該実行された１の実行が成功した場合には、当該１つのアトミック命令が書き込んだ値をさらなる結果（結果２）として返す。一方、マルチコアプロセッサ１０は、当該実行された１つのアトミック命令の実行が失敗した場合には、当該１つのアトミック命令が読み込んだ値をさらなる結果（結果２）として返す。
【０１４６】
図１１は、実施の形態２に従うアトミック命令の処理手順を説明するための模式図である。図２を参照して、マルチコアプロセッサ１０に与えられるＳＩＭＤ命令２００は、４つの実行スロット２０１〜２０４（ｓｌｏｔ０〜ｓｌｏｔ３）を含む。この例において、実行スロット２０１〜２０４の各々には、実施の形態２に従うＣＳＷ命令が指定されるものとする。
【０１４７】
ＳＩＭＤ命令２００の実行が開始されると（（１）命令実行開始）、各実行スロットについての結果１および結果２を格納するフラグ領域などが初期化される。初期化が終了すると、プロセッサコア１００は、「未処理」に設定されている実行スロットの中で同時処理される実行スロットを特定するとともに、同時処理される実行スロットがアクセスするアドレスに重複があるか否かを判断する（（２）アドレス重複確認）。すなわち、プロセッサコア１００は、実行スロットに対応するアドレスの中で同一のものがあるか否かを判断する。そして、プロセッサコア１００は、同一アドレスへの複数のアクセスのうち、ただ１つだけを有効化して、その他のアクセスを「処理済」に設定する。図７に示す例では、プロセッサコア１００は、実行スロット２０３に対応するフラグ領域に失敗結果値２３３Ｆを書き込む。すなわち、プロセッサコア１００は、実行スロット２０３に指定されているＣＳＷ命令の結果１として、命令の実行が失敗したことを示す結果を返す。
【０１４８】
続いて、「未処理」に設定されている（すなわち、有効化されている）実行スロットに指定されている命令について、プロセッサコア１００は、アトミック処理（ＣＳＷ命令）を実行する（（３）アトミック処理）。このとき、プロセッサコア１００は、実行スロット２０１，２０２，２０４に指定されているＣＳＷ命令のそれぞれの結果２として、アトミック処理時に読み込んだそれぞれのデータ（値）を返す。
【０１４９】
続いて、プロセッサコア１００は、実行スロット２０１，２０２，２０４に指定されているＣＳＷ命令のそれぞれの結果１として、指定されたアドレスに格納されているデータと更新前データとのそれぞれの一致の成否に応じて、命令の実行が成功または失敗したことを示す結果（フラグ値）を返す（（４）結果１の生成）。
【０１５０】
さらに、プロセッサコア１００は、アドレスの重複により実行されていない実行スロット２０３に設定されているＣＳＷ命令の結果２として、アドレスが同一である実行スロット２０１の処理結果に応じて、実行スロット２０１に指定されているＣＳＷ命令が書き込んだデータ（値）（実行スロット２０１の結果１として成功が返された場合）、または、実行スロット２０１に指定されているＣＳＷ命令の結果２と同じデータ（値）（実行スロット２０１の結果１として失敗が返された場合）を返す（（５）結果２の生成）。
【０１５１】
このようにアトミック処理が１回実行されると、ＳＩＭＤ命令２００の実行は終了する。
【０１５２】
図１２は、実施の形態２に従うＣＳＷ命令を用いたｌｏｃｋ−ｆｒｅｅアルゴリズム３５０の処理手順を示すフローチャートである。図１２に示すフローチャートは、マルチコアプロセッサ１０で実行されるプログラムの一部の処理を示すものであり、各ステップに対応付けて、プログラムに用いられるコードの一例を示す。
【０１５３】
図１２を参照して、プロセッサコア１００は、データ更新を準備する（ステップＳ１００）。具体的には、プロセッサコア１００は、指定されたアドレスに格納されている更新前データから更新後データを計算するための変数％ｉｎｐｕｔをセットする（コード３０２）。
【０１５４】
続いて、プロセッサコア１００は、更新前データを読み込む（ステップＳ１０２）。具体的には、プロセッサコア１００は、指定されたアドレス（ａｄｄｒｅｓｓＸ）に格納されている更新前データを読み出して、変数％ｏｌｄをセットする（コード３０４）。
【０１５５】
続いて、プロセッサコア１００は、更新後データを計算する（ステップＳ１０４）。具体的には、プロセッサコア１００は、指定された演算式に従って、変数％ｏｌｄと変数％ｉｎｐｕｔとをパラメータとして、更新後データ（変数％ｎｅｗ）を計算する（コード３０６）。
【０１５６】
続いて、プロセッサコア１００は、更新後データの書き込みを試行する（ステップＳ１２０）。具体的には、プロセッサコア１００は、ＣＳＷ命令（atomic-compare-swap-weak）を実行して、指定されたアドレス（ａｄｄｒｅｓｓＸ）に格納されているデータと更新後データを計算する際に用いた更新前データ（すなわち、変数％ｏｌｄの値）とを比較し、両データが一致していれば、更新後データ（すなわち、変数％ｎｅｗの値）を指定されたアドレスへ書き込む（コード３２８）。ＣＳＷ命令（atomic-compare-swap-weak）の結果１は、変数％ｃｏｎｄにセットされ、結果２は、変数％ｏｌｄにセットされる。
【０１５７】
更新後データの書き込みが成功した場合（ステップＳ１２０において、変数％ｃｏｎｄ＝＝ｔｒｕｅの場合：コード３３０）、処理は終了する。これに対して、更新後データの書き込みが失敗した場合（ステップＳ１２０において、変数％ｃｏｎｄ＝＝ｆａｌｓｅの場合：コード３３２）、ステップＳ１０４以下の処理が再度実行される。更新後データの書き込みが失敗した場合には、結果２として、アトミック処理時に読み込んだそれぞれのデータ（値）が返されるので、更新前データの読み込み（ステップＳ１０２）の再実行は不要となる。ＣＳＷ命令の実行が失敗した場合は、別のスレッドが対象のアドレスのデータを変更したことを意味するが、更新前データの再読み込みは不要であり、メモリアクセスに係る処理負荷の増大を抑制できる。
【０１５８】
実施の形態２に従うＣＳＷ命令は、ハードウェア実装に必要な回路面積が増大するものの、標準のプログラミング言語（例えば、Ｃ＋＋コア言語）に用意されている関数の動作に準拠するものである。そのため、既存のプログラムを修正することなく、実施の形態２に従うＣＳＷ命令を利用することができる。また、図１２に示すようなｌｏｃｋ−ｆｒｅｅアルゴリズムを実装した際に、ループ処理内でのメモリアクセス（更新前データの読み込み処理）の付加を低減できる。
【０１５９】
実施の形態２に従うＣＳＷ命令では、アトミック処理を実行していない実行スロットについての結果２として返されるデータ（値）は、実際にアトミック処理が実行された実行スロットの結果１に応じて変化する。これは、各実行スロットがあたかも直列実行されるようなインターフェイスを実現するためであり、このようなインターフェイスを用意することで、プログラミングを容易化できる。
【０１６０】
＜Ｄ．実施の形態３＞
次に、実施の形態３として、本実施の形態に従うアトミック処理を共有メモリ型（ＮＵＭＡ：Non-Uniform Memory Access）マルチプロセッサコンピュータシステムに実装した構成について説明する。
【０１６１】
図１３は、実施の形態３に従うコンピュータ１Ａの装置構成を示す模式図である。図１３を参照して、実施の形態３に従うコンピュータ１Ａは、２つのマルチコアプロセッサ１０−１，１０−２と、外部メモリ１８０−１，１８０−２と、外部機器１９０−１，１９０−２とを含む。マルチコアプロセッサ１０−１とマルチコアプロセッサ１０−２とは、プロセッサインターコネクトバス１４４を介して、データを遣り取りできるように接続されている。
【０１６２】
マルチコアプロセッサ１０−１，１０−２（すなわち、プロセッサコア１００−１〜１００−４）には、実施の形態１に従うアトミック命令（ＣＡＳ命令２および／またはＣＳＷ命令）が実装されているものとする。
【０１６３】
マルチコアプロセッサ１０−１は、プロセッサコア１００−１，１００−２を有しており、マルチコアプロセッサ１０−２は、プロセッサコア１００−３，１００−４を有している。プロセッサコア１００−１，１００−２は、プロセッサインターコネクトバス１４４を介して、マルチコアプロセッサ１０−２内にある共有キャッシュ１１０−２へアクセス可能である。同様に、プロセッサコア１００−３，１００−４は、プロセッサインターコネクトバス１４４を介して、マルチコアプロセッサ１０−１内にある共有キャッシュ１１０−１へアクセス可能である。
【０１６４】
ある命令を実行しているマルチコアプロセッサ１０とは異なるマルチコアプロセッサ１０に接続されているメモリ領域にアクセスする必要がある場合には、アトミック処理の実行に要する時間はより長くなる。すなわち、あるプロセッサコア１００がアトミック命令を実行中において、指定されたアドレスＸが、そのアトミック命令を実行しているプロセッサコア１００とは別のプロセッサコア１００に接続されている共有メモリ（「リモートメモリ領域）とも称す。）に存在する場合には、プロセッサインターコネクトバス１４４を介したアクセスとなる。
【０１６５】
すなわち、アトミック処理中は、プロセッサインターコネクトバス１４４を介した、リモートメモリ領域からのデータ読み込み（ｒｅａｄ）、および、リモートメモリ領域への書き込み（ｗｒｉｔｅ）が実行される。その結果、ハードウェアリソースの占有時間が増大し、アトミック処理に要する時間自体も増加する。すなわち、アトミック処理の実行回数自体が性能に対してより大きく影響することになる。
【０１６６】
言い換えれば、実施の形態１に従うＣＡＳ命令２、および／または、実施の形態２に従うＣＳＷ命令を実装することによる性能向上の効果は、図１３に示すようなアトミック処理を共有メモリ型マルチプロセッサコンピュータシステムにおいて、より顕著になる。
【０１６７】
その他の構成は、図１に示すコンピュータ１と同様であるので、詳細な説明は繰り返さない。
【０１６８】
＜Ｅ．実施の形態４＞
次に、実施の形態４として、本実施の形態に従うアトミック処理をプロセッサコアごとにローカルストレージが設けられたマルチプロセッサコンピュータシステムに実装した構成について説明する。このようなプロセッサコアごとにローカルストレージが設けられた構成は、典型的には、画像処理エンジン（ＧＰＵ）などに応用される。
【０１６９】
図１４は、実施の形態４に従うコンピュータ１Ｂの装置構成を示す模式図である。図１４を参照して、実施の形態４に従うコンピュータ１Ｂは、マルチコアプロセッサ１０Ｂと、外部メモリ１８０と、外部機器１９０とを含む。
【０１７０】
マルチコアプロセッサ１０Ｂは、複数のプロセッサコア１００−１，１００−２と、共有キャッシュ１１０と、メモリコントローラ１２０と、ＩＯコントローラ１３０とを含む。プロセッサコア１００−１，１００−２には、ストレージバス１０４−１，１０４−２を介して、ローカルストレージ１０２−１，１０２−２（以下、「ローカルストレージ１０２」とも総称する。）にそれぞれ接続される。図１４には、説明の便宜上、２つのプロセッサコア１００からなる構成について例示するが、プロセッサコア１００の数については特に制約はない。
【０１７１】
コンピュータ１Ｂにおいて、プロセッサコア１００ごとに対応したローカルストレージ１０２がハードウェアとして実装されている。ローカルストレージ１０２のメモリ領域は、特定のスレッド間のみで共有することができる。言い換えれば、ローカルストレージ１０２のメモリ領域は、プロセッサコア１００間で共有される必要はない。また、要求されるローカルストレージ１０２のメモリ容量も限られる。そのため、各ローカルストレージ１０２は、各プロセッサコア１００の直近に配置される。
【０１７２】
図１４に示すようなマルチコアプロセッサ１０Ｂは、例えば、ＯｐｅｎＣＬ（Open Computing Language）でのローカルアドレス空間（local address space）に類似したプラットフォームを実現できる。
【０１７３】
図１４に示すようなマルチコアプロセッサ１０Ｂでは、隣り合う所定数単位のデータごと（例えば、３２ｂｉｔごと）に、異なるバンクに格納されるようにマルチバンク構成を採用することが好ましい。このようなマルチバンク構成を採用することで、ランダムアクセス時においても、プロセッサコア１００が扱うデータ並列度と同等の並列メモリアクセス性能を実現できる。
【０１７４】
図１５は、図１４に示すローカルストレージ１０２の構成例を示す模式図である。図１５を参照して、ローカルストレージ１０２の各々は、複数のバンクメモリ１０２１，１０２２，１０２３，１０２４を含む。説明の便宜上、図１５には、４つのバンクメモリからなる構成例を示すが、バンクメモリの数は複数であればいずれであってもよい。
【０１７５】
ストレージバス１０４（図１４参照）は、プロセッサコア１００がバンクメモリ１０２１，１０２２，１０２３，１０２４にそれぞれ並列してアクセスできるように、バンクメモリの数に相当する並列化されている。図１４に示す実施の形態４に従うコンピュータ１Ｂにおいて、実施の形態１に従うアトミック命令（ＣＡＳ命令２）が実行されたときのメモリアクセスの処理手順について説明する。
【０１７６】
図１６は、図１４に示す実施の形態４に従うコンピュータ１Ｂにおけるメモリアクセスの処理手順を説明するためのフローチャートである。図１６に示す処理手順は、バンクメモリごとに並列実行される。図１７は、図１６のフローチャートによって定義される処理手順において用いられるアクセスフラグ１０８のデータ構造例を示す模式図である。
【０１７７】
図１６を参照して、プロセッサコア１００は、それぞれの実行スロットに指定されている命令がいずれのバンクメモリへのアクセスを要求するものであるか否かを示すアクセスフラグ１０８を更新する（ステップＳ２００）。図１７に示すように、アクセスフラグ１０８は、バンクメモリごとに実行スロットの数だけ設けられる。すなわち、アクセスフラグ１０８は、少なくとも、バンクメモリの数と実行スロットの数との積に相当する数のフラグを格納できるようになっている。
【０１７８】
以下、ステップＳ２０２〜Ｓ２１６は、バンクメモリの数だけ並列実行される。
プロセッサコア１００は、ステップＳ２００において更新したアクセスフラグ１０８において、対象のバンクメモリへのアクセスを要求している実行スロットが存在するか否かを判断する（ステップＳ２０２）。すなわち、対象のバンクメモリのいずれかのフラグが「ｔｒｕｅ（真）」または「１」がセットされているか否かを判断する。対象のバンクメモリへのアクセスを要求している実行スロットが存在していなければ（ステップＳ２０２においてＮＯ）、処理はステップＳ２２０へ進む。
【０１７９】
対象のバンクメモリへのアクセスを要求している実行スロットが存在していれば（ステップＳ２０２においてＹＥＳ）、プロセッサコア１００は、対象のバンクメモリへのアクセスを要求している（典型的には、「ｔｒｕｅ（真）」または「１」がセットされている）実行スロットのうち、いずれか１つの実行スロットを選択する（ステップＳ２０４）。この選択された実行スロットのスロット番号をｎとする。
【０１８０】
続いて、プロセッサコア１００は、選択された実行スロットに指定されているアドレスと同一のアドレスを指定する他の実行スロットが存在するか否かを判断する（ステップＳ２０６）。より具体的には、プロセッサコア１００は、選択された実行スロットに指定されているアドレスをアドレスＸとして設定するとともに、同一のバンクメモリへのアクセスが指定されているそれ以外の実行スロットの各々について、その指定されているアドレスとアドレスＸとを比較する。すなわち、アクセスフラグ１０８において対象のバンクメモリについて「ｔｒｕｅ（真）」または「１」がセットされており、かつ、実行スロットのスロット番号がｎではない、実行スロットについて、その指定されているアドレスとアドレスＸとが比較される。
【０１８１】
選択された実行スロットに指定されているアドレスと同一のアドレスを指定する他の実行スロットが存在すれば（ステップＳ２０６においてＹＥＳ）、プロセッサコア１００は、アクセスフラグ１０８において、当該同一のアドレスを指定する他の実行スロットに対応するフラグを「ｆａｌｓｅ（偽）」または「０」に書き換える（ステップＳ２０８）。併せて、プロセッサコア１００は、命令の実行が失敗したことを示す結果（戻り値）を、当該他の実行スロットに対応する戻り値領域へ書き込む（ステップＳ２１０）。
【０１８２】
選択された実行スロットに指定されているアドレスと同一のアドレスを指定する他の実行スロットが存在しなければ（ステップＳ２０６においてＮＯ）、ステップＳ２０８およびＳ２１０の処理はスキップされる。
【０１８３】
続いて、プロセッサコア１００は、対象のバンクメモリにおいて選択されたスロット番号ｎの実行スロットに指定されているアドレスＸに格納されているデータに対して、実施の形態１に従うＣＡＳ命令２を実行する（ステップＳ２１２）。すなわち、プロセッサコア１００は、対象のバンクメモリの指定されたアドレスＸからデータを読み込み、読み込んだデータと旧データとを比較し、両データが一致していた場合にのみ、新データをメモリへ書き込むという処理を実行する。そして、プロセッサコア１００は、読み込んだデータと旧データとの比較結果を実行の結果（戻り値）を対応する戻り値領域に書き込む（ステップＳ２１４）。そして、プロセッサコア１００は、アクセスフラグ１０８において、対象のバンクメモリのスロット番号ｎの実行スロットに対応するフラグを「ｆａｌｓｅ（偽）」または「０」に書き換える（ステップＳ２１６）。そして、ステップＳ２０２以下の処理が繰り返される。
【０１８４】
ステップＳ２２０において、アクセスを要求している実行スロットが存在していないと判断されたバンクメモリの数が管理される。すべてのバンクメモリについて、アクセスを要求している実行スロットが存在していなければ（ステップＳ２２０においてＹＥＳ）、命令の実行は終了する。すなわち、アクセスフラグ１０８において、すべてのバンクメモリについて、「ｔｒｕｅ（真）」または「１」がセットされているフラグが存在しなくなると、命令の実行は終了する。
【０１８５】
以上のような処理によって、マルチバンク構成のローカルストレージを採用した場合であっても、実施の形態１に従うアトミック命令を実現できる。なお、実施の形態２に従うＣＳＷ命令についても、上述と同様に実装できるので、詳細な説明は繰り返さない。
【０１８６】
＜Ｆ．実施の形態５＞
次に、実施の形態５として、本実施の形態に従うアトミック処理をマイクロコード（一種のファームウエア）により実装する構成について説明する。図１８は、実施の形態５に従うコンピュータに関連したハードウェア構成を示す模式図である。
【０１８７】
図１４および図１５に示すようなハードウェア構成においては、複数のメモリバンクのそれぞれについてアトミック処理を並列実行するために、各メモリバンクと対応付けて、メモリバンクと同数のアトミック演算器を設けることが好ましい。より具体的には、図１８（Ａ）に示すように、ローカルストレージ１０２内のバンクメモリ１０２１〜１０２４に対応付けて、同数のアトミック演算器１００１〜１００４がプロセッサコア１００内に設けられている。
【０１８８】
一方で、図８（Ａ）に示すようなハードウェア構成は、実装コストが上がるという欠点もある。この場合には、図８（Ｂ）に示すような、バンクメモリ１０２１〜１０２４に対して単一のアトミック演算器１００６を設けておき、バンクメモリ１０２１〜１０２４のうち、各タイミングでは１つのバンクメモリのみにアクセスするような機構をソフトウエア的に実装する。
【０１８９】
例えば、任意のバンクメモリへのアクセスをロックするためのロック機構を実装してもよい。具体的には、このロック機構によるロックの状態を示す特殊レジスタが設けられるとともに、当該特殊レジスタにアクセスしてその値を読み込む命令と、ロックを解除する特殊なメモリ書き込み命令とをセットにして実装する。この命令のセットを用いて、特定のバンクメモリへのアクセスをロックした上で、通常の演算命令を実行することで、アトミック処理を実現してもよい。
【０１９０】
図１９は、アトミック処理を実現するためのマイクロコードの一例を示す図である。図１９（Ａ）は、関連技術に係るＣＡＳ命令１に対応するマイクロコードの一例を示し、図１９（Ｂ）は、実施の形態１に従うＣＡＳ命令２に対応するマイクロコードの一例を示す。なお、図１９には、ＮＶＩＤＩＡコーポレーション（アメリカ合衆国カリフォルニア州サンタクララ）のＦｅｒｍｉアーキテクチャに沿った疑似命令を用いた場合のコード例を示す。
【０１９１】
図１９（Ａ）に示すマイクロコード４００Ａにおいては、全スレッドについてアトミック処理の実行が完了するまで、図に示すループ処理が実行される。マイクロコード４００Ａにおいて、命令「ＳＥＬ  ％ｏｕｔ，％ｎｅｗ，％ｒｅｔ，Ｐ１」がＣＡＳ命令１の実行を指示するものである。図１９（Ａ）に示すＬＤＳＬＫ命令は、アクセス先として指定されたメモリバンクが互いに重複している複数の実行スロットに対して、高々１つの実行スロットしかロックしかできない。そのため、対象のメモリスロットとは別のメモリスロットに指定された命令については、次のループの処理まで待たされることになる。
【０１９２】
これに対して、図１９（Ｂ）に示すマイクロコード４００Ｂにおいては、実施の形態１に従うＣＡＳ命令２を用いて、ループ処理が実行される。マイクロコード４００Ｂにおいて、命令「ＳＥＬ  ％ｏｕｔ，％ｎｅｗ，％ｒｅｔ，Ｐ１」がＣＡＳ命令２の実行を指示するものである。
【０１９３】
マイクロコード４００Ｂにおいて、命令「ＸＸＸ  ％ａｄｄｒＸ，Ｐ０，％ａｄｄｒ」（図１９（Ｂ）中の符号４０２）は、変数％ａｄｄｒと同じメモリバンクで変数Ｐ０＝＝ｔｒｕｅ（真）である実行スロットのアドレス（変数％ａｄｄｒ）をアドレスＸ（変数％ａｄｄｒＸ）として設定する命令である。すなわち、メモリアドレスが重複しているものが残っているか否かの判断を実行するための処理（図１９（Ｂ）中の符号４０４）の前処理に相当する。
【０１９４】
なお、実施の形態２に従うＣＳＷ命令についても、上述と同様に実装できるので、詳細な説明は繰り返さない。
【０１９５】
＜Ｇ．まとめ＞
一般的なＳＩＭＤ／ＳＩＭＴ型プロセッサにおいて、複雑なアトミック処理を行なう際に用いるＣＡＳ命令を実行する際には、通常のアトミック処理と同様に、アドレスが重複している複数の命令の実行を直列化することで、アクセスの競合を回避する。このような直列化を採用することで、結果的に、むだになるメモリアクセスが増加し、性能上のボトルネックとなっている。
【０１９６】
本願発明者は、このような新たな課題を発見し、その課題を解決するために、以下のような解決手段を採用した。すなわち、ハードウェアにより並列処理される複数のスレッドで、同時にアトミックなＣＡＳ命令を実行する際には、単一のアドレスについては、高々１つのスレッドについてしか処理を行なわない。そして、実行が成功したスレッドについては、成功を示す結果を返し、他のスレッドについては直列化処理せず、即座に失敗を示す結果を返す。
【０１９７】
このように、命令の実行が失敗したことを示す条件について、ＳＩＭＴ型プロセッサに特有の状態を追加することで、アトミックなメモリアクセスの頻度を減らすことが可能となり、ＳＩＭＴ型プロセッサにおける性能上のボトルネックを解消できる。すなわち、このようなアトミック命令を追加することで、プロセッサの性能を向上させることができる。
【０１９８】
今回開示された実施の形態はすべての点で例示であって制限的なものではないと考えられるべきである。本発明の範囲は、上記した説明ではなく、特許請求の範囲によって示され、特許請求の範囲と均等の意味および範囲内でのすべての変更が含まれることが意図される。
【符号の説明】
【０１９９】
１０，１０Ｂ，１０−１，１０−２  マルチコアプロセッサ、１００  プロセッサコア、１０２  ローカルストレージ、１０４  ストレージバス、１０８  アクセスフラグ、１１０  共有キャッシュ、１２０  メモリコントローラ、１３０  コントローラ、１４０，１５０  内部バス、１４４  プロセッサインターコネクトバス、１６０  外部メモリバス、１７０  外部機器バス、１８０  外部メモリ、１９０  外部機器、２００，２００＃  ＳＩＭＤ命令、２０１〜２０８  実行スロット、２１１〜２１４  フラグ領域、２２１〜２２４  戻り値領域、１００１〜１００４，１００６  アトミック演算器、１０２１〜１０２４  バンクメモリ。
【図１】
2017027432.tif 000003
【図３】
2017027432.tif 000004
【図４】
2017027432.tif 000005
【図８】
2017027432.tif 000006
【図１２】
2017027432.tif 000007
【図１３】
2017027432.tif 000008
【図１４】
2017027432.tif 000009
【図１５】
2017027432.tif 000010
【図１６】
2017027432.tif 000011
【図１７】
2017027432.tif 000012
【図１８】
2017027432.tif 000013
【図１９】
2017027432.tif 000014
【図２】
2017027432.tif 000015
【図５】
2017027432.tif 000016
【図６】
2017027432.tif 000017
【図７】
2017027432.tif 000018
【図９】
2017027432.tif 000019
【図１０】
2017027432.tif 000020
【図１１】
2017027432.tif 000021