(57)【要約】      （修正有）【課題】異なるサイズのレジスタ・ラインにおいて動作するＰＰＥとＳＰＥを含む２以上のプロセッサ、および、メインメモリを備えるプロセッサシステムにおいてアトミック処理を実装する。【解決手段】プリミティブのあるメインメモリは、パリティ・バイトと２以上の部分データに分割される。パリティ・バイトは１ビット以上である。パリティ・バイトは、２以上の部分データのうちのどれが有効でどれが無効かを示す。プリミティブのサイズは、ＰＰＥのアトミック処理サイズの最大値よりも大きく、ＳＰＥのアトミック処理サイズの最大値以下である。ＰＰＥとＳＰＥは予約付き読み出しや条件付き書き込みによって、アトミックの値にアクセスする。【選択図】図４Ａ
2007157146.tif 000002
【特許請求の範囲】
【請求項１】
メモリ転送容量の異なるＰＰＥ（Power Processor Element）とＳＰＥ（Synergistic Processing Element）、および、メインメモリを含む２以上のプロセッサを備えるプロセッサ・システムにおいて実行される処理方法であって、
ＰＰＥのメモリ転送処理の最大サイズよりも大きく、ＳＰＥのメモリ転送処理の最大サイズ以下のサイズのプリミティブ（Primitive）について、
ａ）メインメモリにおける前記プリミティブのアドレスを２以上の部分データと前記２以上の部分データのうちのいずれが有効部でいずれが無効部であるかを示す１ビット以上のパリティ・バイトに分割するステップと、
ｂ）ＳＰＥにより、パリティ・バイトと少なくとも有効部についての予約付き読み出しを実行するステップと、
ｃ）ＳＰＥにより、有効部を更新して更新済有効部を生成するステップと、
ｄ）ＳＰＥにより、条件付きにて、パリティ・バイトの値を変更せずに書き戻し、更新済有効部を前記プリミティブのあるアドレスに記録することにより、予約が失効していないことを条件として更新済有効部を前記プリミティブのアドレスに記録するステップと、
ｅ）予約が失効していれば、条件付き書き込みが成功するまでＳＰＥにｂ）、ｃ）、ｄ）のステップを再実行させるステップと、
を備えることを特徴とするアトミック処理方法。
【請求項２】
ＰＰＥにより、パリティ・バイトの予約付き読み出しを実行することにより無効部を更新するステップと、
ＰＰＥが単一のメモリ転送処理にて更新できるサイズの小区分にて、無効部の１以上の小区分に書き込むステップと、
パリティ・バイトに対する更新値の条件付き書き込みを実行するステップと、
条件付き書き込み処理が成功したときに、パリティ・バイトの値を変更するステップと、
を更に備えることを特徴とする請求項１に記載のアトミック処理方法。
【請求項３】
ＰＰＥによる無効部の更新中にパリティ・バイトについての予約が失効したとき、ＰＰＥはパリティ・バイトを再度予約付きで読み出し、ＰＰＥの１以上のレジスタに有効部を読み出すことを特徴とする請求項２に記載のアトミック処理方法。
【請求項４】
ＰＰＥにより、パリティ・バイトの初期値の予約付き読み出しを実行し、ＰＰＥが単一のメモリ転送処理にて更新できるサイズの小区分にて、無効部の１以上の小区分の連続的な読み出しを実行することにより有効部の値を読み出すステップと、
パリティ・バイトへの前記初期値の条件付き書き込みを実行するステップと、
を更に備えることを特徴とする請求項１に記載のアトミック処理方法。
【請求項５】
前記プリミティブのサイズは、ＳＰＥのレジスタのサイズ以下であることを特徴とする請求項１に記載のアトミック処理方法。
【請求項６】
前記プリミティブのサイズは、ＳＰＥのレジスタのサイズ以下であって、
小区分は、ＰＰＥのレジスタのサイズ以下のサイズであることを特徴とする請求項１に記載のアトミック処理方法。
【請求項７】
前記プリミティブのサイズは１２８バイトであることを特徴とする請求項１に記載のアトミック処理方法。
【請求項８】
前記プリミティブのサイズは１２８バイトであって、前記小区分のサイズは８バイトであることを特徴とする請求項１に記載のアトミック処理方法。
【請求項９】
前記プリミティブのサイズは１２８バイトであって、前記２以上の部分データには２つの６３バイト・部分データが含まれることを特徴とする請求項１に記載のアトミック処理方法。
【請求項１０】
ＰＰＥは一回あたり８バイトをアトミックに操作し、
ＳＰＥは一回あたり１２８バイトをアトミックに操作し、
前記プリミティブのサイズは１２８バイトであって、前記２以上の部分データには２つの６３バイト・部分データが含まれることを特徴とする請求項１に記載のアトミック処理方法。
【請求項１１】
前記プリミティブは、更に、ＳＰＥとＰＰＥからアクセスできる追加情報を保持するユーティリティ・バイトを含むことを特徴とする請求項１に記載のアトミック処理方法。
【請求項１２】
前記追加情報は、前記プリミティブの更新に関してＰＰＥと他のＳＰＥのいずれが優先されるかをＳＰＥに通知するための情報であることを特徴とする請求項１１に記載のアトミック処理方法。
【請求項１３】
前記ユーティリティ・バイトは、前記プリミティブをマスクするサイズを示すことを特徴とする請求項１１に記載のアトミック処理方法。
【請求項１４】
前記プリミティブは、第１部分データと第２部分データに分割され、
前記第１部分データは、前記パリティ・バイトを含むことを特徴とする請求項１に記載のアトミック処理方法。
【請求項１５】
前記ｂ）のステップは、
前記第１部分データをＰＰＥのローカルストア・レジスタに読み込むステップと、
前記第１部分データが有効部か否かを前記パリティ・バイトにより判定するステップと、
前記第１部分データが有効部でなければ、前記第２部分データをＰＰＥのローカルストア・レジスタに読み込むステップと、を含み、
有効部である部分データをＰＰＥのローカルストア・レジスタ内に並べることを特徴とする請求項１４に記載のアトミック処理方法。
【請求項１６】
前記ｂ）のステップは、
１回の操作にてＰＰＥのローカルストア・レジスタに前記プリミティブ全体を読み込むステップと、
前記パリティ・バイトにより、どの部分データが有効部であるかを判定するステップと、
を含むことを特徴とする請求項１に記載のアトミック処理方法。
【請求項１７】
データバスと、
前記データバスに接続され、１以上のタスク定義情報を保持するメインメモリと、
前記データバスに接続されるＰＰＥ（Power Processor Element）と、
前記データバスに接続される１以上のＳＰＥ（Synergistic Processing Element）と、を備え、
各ＳＰＥは、ＳＰＵ（Synergistic Processing Unit）とローカルストア（Local Store）を含み、
前記メインメモリは、ＰＰＥのメモリ転送処理の最大サイズよりも大きく、ＳＰＥのメモリ転送処理の最大サイズ以下のサイズであって、パリティ・バイトと２以上の部分データを含むプリミティブ（Primitive）を保持し、
前記パリティ・バイトは、前記２以上の部分データのうちのいずれが有効部でいずれが無効部であるかを示す１ビット以上のデータを含むことを特徴とするＣＥＬＬプロセッサ。
【請求項１８】
ＳＰＥによる前記プリミティブの更新処理方法を示す命令セットとして、１以上のＳＰＥのローカルストアにプロセッサの実行命令セットを保持し、
前記更新処理方法は、
ａ）ＳＰＥにより、パリティ・バイトと少なくとも有効部についての予約付き読み出しを実行するステップと、
ｂ）ＳＰＥにより、有効部を更新して更新済有効部を生成するステップと、
ｃ）条件付きにて、パリティ・バイトの値を書き戻し、更新済有効部を前記プリミティブのあるアドレスに記録することにより、予約が失効していないことを条件としてＳＰＵが更新済有効部を前記プリミティブのアドレスへ記録するステップと、
ｄ）予約が失効していれば、条件付き書き込みが成功するまでＳＰＥにａ）、ｂ）、ｃ）のステップを再実行させるステップと、
を備えることを特徴とする請求項１７に記載のＣＥＬＬプロセッサ。
【請求項１９】
ＰＰＥによる前記プリミティブの更新処理方法を示す命令セットとして、ＰＰＥの１以上のレジスタにプロセッサの実行命令セットを保持し、
前記更新処理方法は、
ＰＰＥにより、パリティ・バイトを予約付きで読み出し、ＰＰＥが単一のメモリ転送処理にて更新できるサイズの小区分により無効部の１以上の小区分に書き込むステップと、
パリティ・バイトに対する更新値の条件付き書き込みを実行するステップと、
条件付き書き込み処理が成功したときに、ＰＰＥによりパリティ・バイトの値を前記更新値に変更するステップと、を含み、
前記更新値は、有効部を無効部に、無効部を有効部に反転させる値であることを特徴とする請求項１７に記載のＣＥＬＬプロセッサ。
【請求項２０】
ＰＰＥによる有効部の読み出し方法を示す命令セットとして、ＰＰＥの１以上のレジスタにプロセッサの実行命令セットを保持し、
前記読み出し方法は、
ＰＰＥにより、パリティ・バイトの初期値の予約付き読み出しを実行するステップと、
無効部の１以上の小区分を連続的に読み出すステップと、
前記初期値のパリティ・バイトへの条件付きで書き込みを実行するステップと、
を含むことを特徴とする請求項１７に記載のＣＥＬＬプロセッサ。
【請求項２１】
前記プリミティブのサイズは、ＳＰＥのレジスタのサイズ以下であることを特徴とする請求項１７に記載のＣＥＬＬプロセッサ。
【請求項２２】
前記プリミティブのサイズは、ＳＰＥのレジスタのサイズ以下であって、
小区分は、ＰＰＥのレジスタのサイズ以下のサイズであることを特徴とする請求項１７に記載のＣＥＬＬプロセッサ。
【請求項２３】
前記プリミティブのサイズは１２８バイトであることを特徴とする請求項１７に記載のＣＥＬＬプロセッサ。
【請求項２４】
前記プリミティブのサイズは１２８バイトであって、前記小区分のサイズは８バイトであることを特徴とする請求項１７に記載のＣＥＬＬプロセッサ。
【請求項２５】
前記プリミティブのサイズは１２８バイトであって、前記２以上の部分データには２つの６３バイト・部分データが含まれることを特徴とする請求項１７に記載のＣＥＬＬプロセッサ。
【請求項２６】
ＰＰＥは一度に８バイトをアトミックに操作し、
ＳＰＥは一度に１２８バイトをアトミックに操作し、
前記プリミティブのサイズは１２８バイトであって、前記２以上の部分データには２つの６３バイト・部分データが含まれることを特徴とする請求項１７に記載のＣＥＬＬプロセッサ。
【請求項２７】
前記プリミティブは、更に、ＳＰＥとＰＰＥからアクセスできる追加情報を保持するユーティリティ・バイトを含むことを特徴とする請求項１７に記載のＣＥＬＬプロセッサ。
【請求項２８】
前記追加情報は、前記プリミティブの更新に関してＰＰＥが優先権を持つことをＳＰＥに通知するための情報であることを特徴とする請求項２７に記載のＣＥＬＬプロセッサ。
【請求項２９】
前記ユーティリティ・バイトは、前記プリミティブをマスクするサイズを示すことを特徴とする請求項２７に記載のＣＥＬＬプロセッサ。
【請求項３０】
前記プリミティブは、第１部分データと第２部分データに分割され、
前記第１部分データは、前記パリティ・バイトを含むことを特徴とする請求項２７に記載のＣＥＬＬプロセッサ。
【請求項３１】
レジスタ・ラインのサイズが異なるＰＰＥ（Power Processor Element）とＳＰＥ（Synergistic Processing Element）、および、メインメモリを含む２以上のプロセッサを備えるプロセッサ・システムにおいて実行され、ＳＰＥによる単一操作にて読み書きが可能なプリミティブ（Primitive）をＰＰＥによりアトミックに更新するための方法であって、
前記プリミティブのサイズは、ＰＰＥのメモリ転送処理の最大サイズよりも大きく、ＳＰＥのメモリ転送処理の最大サイズ以下であって、
メインメモリにおける前記プリミティブのアドレスを２以上の部分データと前記２以上の部分データのうちのいずれが有効部でいずれが無効部であるかを示す１ビット以上のパリティ・バイトに分割するステップと、
ＰＰＥにより、パリティ・バイトの予約付き読み出しを実行するステップと、
ＰＰＥにより、ＰＰＥが単一のメモリ転送処理にて更新できるサイズの小区分にて、無効部の１以上の小区分に書き込むステップと、
ＰＰＥにより、パリティ・バイトに対する更新値の条件付き書き込みを実行するステップと、
条件付き書き込み処理が成功したときに、ＰＰＥによりパリティ・バイトの値を変更するステップと、
を更に備えることを特徴とするアトミック更新方法。
【請求項３２】
メモリ転送容量の異なるＰＰＥ（Power Processor Element）とＳＰＥ（Synergistic Processing Element）、および、メインメモリを含む２以上のプロセッサを備えるプロセッサ・システムにおいて実行され、ＳＰＥによる単一操作にて読み書きが可能なプリミティブ（Primitive）をＰＰＥによりアトミックに読み出すための方法であって、
前記プリミティブのサイズは、ＰＰＥのメモリ転送処理の最大サイズよりも大きく、ＳＰＥのメモリ転送処理の最大サイズ以下であって、
メインメモリにおける前記プリミティブのアドレスを２以上の部分データと前記２以上の部分データのうちのいずれが有効部でいずれが無効部であるかを示す１ビット以上のパリティ・バイトに分割するステップと、
ＰＰＥにより、パリティ・バイトの初期値を予約付きで読み出すステップと、
ＰＰＥが単一のメモリ転送処理にて更新できるサイズの小区分にて、無効部の１以上の小区分を連続的に読み出すステップと、
ＰＰＥにより、パリティ・バイトへの前記初期値の条件付き書き込みを実行するステップと、
を備えることを特徴とするアトミック読出方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本出願は、その優先日と同時に出願され、本出願と譲受人が共通する米国特許出願「発明の名称:特定のＳＰＥを使ったＣＥＬＬプロセッサのアトミックなコンペア・アンド・スワップ処理（CELL PROCESSOR ATOMIC COMPARE AND SWAP USING DEDICATED SPE）、James E.Marr,John P.Bates」に関連し、関連出願の主題は、ここに引用により組み込まれる。
【０００２】
本実施例は、ＣＥＬＬプロセッサに関連し、より詳細には、ＣＥＬＬプロセッサのアトミック処理、に関する。
【背景技術】
【０００３】
ＣＥＬＬプロセッサとは、並行処理可能なマイクロプロセッサの一種である。基本構成のＣＥＬＬプロセッサには、１つのＰＰＥ（Power Processor Element）（「Processing Element」すなわち「PE」ともよばれる）と、複数のＳＰＥ（Synergistic Processing Elements）が含まれる。ＰＰＥとＳＰＥは、ＥＩＢ（Element Interconnect Bus）とよばれる内部高速バスによって接続される。ＣＥＬＬプロセッサは、携帯型デバイスからメインフレームまでのさまざまなアプリケーションについて対応可能に設計されている。
【発明の開示】
【発明が解決しようとする課題】
【０００４】
ＣＥＬＬプロセッサは、通常、１つのＰＰＥと最高８つのＳＰＥを持つ。通常、各ＳＰＥは、単一チップであるか、メインプロセッサ（main processor）や補助プロセッサ（co-processor）を含む単一チップの一部である。各ＳＰＥは、通常、ＳＰＵ（Synergistic Processor Unit）とローカルストア（ＬＳ：Local store）を含む。ＰＰＥは、通常、ＰＰＵ（Power Processor Unit）と１以上のキャッシュを含む。全てのＳＰＥとＰＰＥは、バスなどを介してメインメモリにアクセスできる。ＳＰＥは、ＰＰＥにて実行されるプログラムと連携して複数の処理を並列実行できる。ＳＰＥとＰＰＥにおける並列処理の調整のために、アトミックな命令を実装することが多い。アトミック命令とは、ＳＰＵやＰＰＵが単一操作にて（しばしば「アトミック」として参照されるアドレスである）メモリアドレスへの読み書きを実行し、その間は他のプロセッサの「アトミック」へのアクセスを禁じるような命令である。アトミック命令とは、相互排他的な（ミューテックス（mutex:mutual exclusion））「ロック（locked）」命令か「ロックフリー（lock-free）」命令である。ミューテックス処理では、プロセッサがアトミックをロックすると、ロックが解除されるまで他のプロセッサはアトミックへの書き込みができなくなる。「ロックフリー」処理では、１度に１つのプロセッサだけがアトミックアドレスに書き込み可能であり、他のプロセッサはアトミックに書き込まれたところに上書きできる。ロックフリーのアトミック命令は、「予約（resservation）」命令を使用する。予約命令は、予約を行ったプロセッサに対して、予約後にアトミックが上書きされたかどうかを通知する。
【０００５】
ＣＥＬＬプロセッサでアトミック命令を実行するときに問題となるのは、ＰＰＵとＳＰＵの間でアトミック命令のための予約サイズが違うことである。アトミック命令のサイズの違いは、ＰＰＵとＳＰＵの間におけるメモリアクセス能力のサイズ違いに起因する。ＰＰＵのメモリアクセスは、一般的には、ＰＰＵコアのレジスタサイズにより制約される。ＳＰＵのアトミック処理のサイズは、ＣＥＬＬプロセッサ・アーキテクチャによって定義されるものではない。ＳＰＵはメモリ・フロー・コントローラ（ＭＦＣ：memory flow controller）を介してメインメモリにアクセスできる。ＭＦＣは、ＰＰＵコアのレジスタサイズよりもはるかに大きなサイズにてデータ転送できる。あるＣＥＬＬプロセッサの実装においては、ＳＰＵ用のＭＦＣは１２８バイトの大きさ（chunk）でメインメモリにデータ入出力転送するが、ＰＰＵは８バイトの大きさ（chunk）（あるいはそれ以下）でしかデータ転送できない。単一操作（single operation）あたりのＰＰＵの最大メモリ転送サイズは、ＰＰＵのレジスタ・セットのサイズによって決まる。ＰＰＵのレジスタの長さは８バイトである。１バイトは８ビットなので６４ビットサイズとなる。ＭＦＣはＳＰＵのアトミック・サイズを設定する。ＳＰＵのローカルストアは、１６バイト、すなわち、１２８ビットレジスタのかたちで形成される。ＳＰＵのローカルストアのレジスタは、メインメモリのアドレスとは結びついていない。ＳＰＵは、ＭＦＣを介してメモリとアクセスする。ＭＦＣは１２８バイトの大きさ（chunk）で動作する。ＭＦＣは、ＳＰＵのアトミック操作と非アトミック操作の両方についてのＤＭＡ処理に対応する。あるＣＥＬＬの実装では、ＳＰＵの全てのアトミック命令は１２８バイトとなる。しかし、ＭＦＣが扱う非アトミック命令のサイズは１バイトから１６キロバイトの範囲にわたる。そこで、ＳＰＵは予約付き読み出し（read with reservation）を実行し、１２８バイト分をローカルストアにコピーする。予約単位のサイズは任意である。アトミック・アクセスのサイズよりも大きなサイズであれば、論理的には正しく動作するであろう。
【０００６】
ＳＰＵが大容量のデータをアトミックに扱えることはとても強力であるが、ＰＰＵが１度に８バイトしかアトミックに扱えないことは不自由となりうる。アトミック予約サイズの違いは、ロックフリー・アルゴリズムの特徴を制限してしまう可能性がある。連結リストは、ミューテックスを使わなくても、ロックフリー・アルゴリズムで扱うことができる。しかし、もっと大きなアトミックを扱えれば、整数型よりも大きなサイズの型を一度の操作でアトミックに更新できるので、ロックフリー・アルゴリズムをもっと複雑な操作にも応用できる。
【０００７】
したがって、ＰＰＥとＳＰＥが異なるサイズのレジスタ・ラインを持つＣＥＬＬプロセッサにおいて、アトミックな命令を実行するための技術、が必要である。
【課題を解決するための手段】
【０００８】
上記課題を解決するために、本発明のある態様では、異なるサイズのレジスタ・ラインで動作するＰＰＥ（Power Processor Element）とＳＰＥ（Synergistic Processor Element）を含む２以上のプロセッサおよびメインメモリを備えるプロセッサ・システムにおいて、アトミック処理を実行するための方法を開示する。プリミティブ（Primitive）が保持されているメインメモリのアドレスは、パリティ・バイトと２以上の部分データ（portion）に分割される。「パリティ・バイト」は１ビット以上のサイズとなる。パリティ・バイト値は、２以上の部分データのうちのどれが有効部（valid portion）でどれが無効部（invalid portion）かを示す。プリミティブのメモリ・サイズは、ＰＰＥの最大メモリ転送サイズよりも大きく、ＳＰＥの最大メモリ転送サイズ以下となっている。
【０００９】
ＳＰＥは、パリティ・バイト値と有効部を予約付き読み出ししてプリミティブを更新できる。ＳＰＥは有効部を更新する。条件付きで、ＳＰＥはパリティ・バイト値を変更せずに書き戻し、更新済の有効部をプリミティブのアドレスに記録する。更新済の有効部をプリミティブのアドレスに記録するには、予約が失効していないことが条件となる。予約が失効していたら、条件付き書き込みが成功するまで、ＳＰＥは「予約付き読み出し」、「更新」、「条件付き書き込み」を繰り返してもよい。
【００１０】
ＰＰＥはパリティ・バイトを予約付き読み出しして、無効部の１以上の小区分（subsection）に書き込むことにより、プリミティブを更新してもよい。この小区分のサイズは、ＰＰＥが単一のメモリ転送操作にて更新可能なサイズである。ＰＰＥは、パリティ・バイトに新しい値を条件付き書き込みできる。条件付き書き込みに成功すると、パリティ・バイトの値は新しい値に変更され、無効部は有効部に反転する。
【００１１】
ＰＰＥは、パリティ・バイトの初期値を予約付き読み出しし、無効部の１以上の小区分を連続的に読み出すことにより、プリミティブの値を読み出してもよい。小区分は、ＰＰＥが単一のメモリ転送操作にて更新可能なサイズの区分である。ＰＰＥは、パリティ・バイトにＰＰＥの初期値を条件付き書き込みできる。
【発明を実施するための最良の形態】
【００１２】
本発明の教示するところは、添付図面とあわせて以下の詳細な説明を考慮することにより容易に理解されるでろう。
以下の記述においては、例示のために多くの特定的な詳細を含むけれども、本発明の範囲内において、以下の詳細について多くの変形や変更が可能であることは、当業者には理解されるところである。したがって、下記に示す本発明の実施例は、請求項に記載の発明の一般性を失わせるものでも制約を設けるものでもない。
【００１３】
制約的な意味ではない設例として、図１は、ＣＢＥＡ（ＣＥＬＬブロードバンドエンジン・アーキテクチャ：Cell Broadband engine architecture）として知られるアーキテクチャ準拠のＣＥＬＬプロセッサ１００を示している。同図設例に示すようにＣＥＬＬプロセッサは、ＰＰＥの複数個の集合（ＰＰＥグループ）と、ＳＰＥの複数個の集合（ＳＰＥグループ）を備えることができる。あるいは、ＣＥＬＬプロセッサは、単一のＳＰＥと単一のＰＰＥにより、単一のＳＰＥグループと単一のＰＰＥグループだけを備えてもよい。グループ内の各ユニットは、ハードウェア資源を共有できる。ただし、ソフトウェアからは、ＳＰＥとＰＰＥは独立した要素として見えなければならない。
【００１４】
図１に示す例では、ＣＥＬＬプロセッサ１００は、ＳＧ−０、・・・、ＳＧ−ｎといった多数のＳＰＥグループと、ＰＧ−０、・・・、ＰＧ−ｐといった多数のＰＰＥグループを含む。各ＳＰＥグループは、ＳＰＥ０、・・・、ＳＰＥｇといった多数のＳＰＥを含む。また、ＣＥＬＬプロセッサ１００は、メインメモリ（ＭＥＭ）と入出力機能（Ｉ／Ｏ）も含む。
【００１５】
各ＰＰＥグループは、ＰＰＥ−０、・・・、ＰＰＥ−ｇといった多数のＰＰＥを含む。この例では、ＳＰＥグループは、単一のキャッシュＳＬ１を共有する。キャッシュＳＬ１は、ローカルストレージとメインストレージの間におけるＤＭＡ転送のためのファーストレベルキャッシュである。グループ内の各ＰＰＥは、それぞれ専用のファーストレベル（内部）キャッシュＬ１を持つ。加えて、グループ内のＰＰＥは、単一のセカンドレベル（外部）キャッシュＬ２を共有する。図１では、ＳＰＥとＰＰＥのためのキャッシュが示されているが、一般的なＣＥＬＬプロセッサ、特にＣＢＥＡ準拠プロセッサにとってこれは必須の構成ではない。
【００１６】
要素接続バスＥＩＢは、上記に示したさまざまなコンポーネントを接続する。各ＳＰＥグループにおけるＳＰＥと各ＰＰＥグループにおけるＰＰＥは、バス・インタフェース・ユニットＢＩＵを介して、ＥＩＢにアクセスできる。ＣＥＬＬプロセッサ１００は、通常、プロセッサ内に２つのコントローラを含む。１つは、ＥＩＢとメインメモリＭＥＭの間のデータの流れを制御するメモリ・インタフェース・コントローラＭＩＣである。もう一つは、Ｉ／ＯとＥＩＢの間のデータの流れを制御するバス・インタフェース・コントローラＢＩＣである。ＭＩＣ、ＢＩＣ、ＢＩＵ、ＥＩＢについての実装はさまざまであるが、各実装に応じた機能や回路については当業者にとっては既知のものである。
【００１７】
各ＳＰＥは、ＳＰＵ（ＳＰＵ０、・・・、ＳＰＵｇ）を備える。ＳＰＥグループにおける各ＳＰＵは、専用のローカルストレージ領域ＬＳと専用のメモリ・フロー・コントローラＭＦＣを備える。ＭＦＣは、メモリ管理ユニットＭＭＵと対応づけられる。ＭＭＵは、メモリ保護やアクセス許可に関する情報の保持および処理を行う。
【００１８】
ＰＰＥは、キャッシュ付きの６４ビットのパワーＰＣ・プロセッサ・ユニット（ＰＰＵ）である。ＣＢＥＡ準拠システムでは、ＰＰＥは、ベクトル・マルチメディア・拡張ユニット（vector multimedia extension unit）を内蔵する。ＰＰＥは汎用処理用ユニットであり、（メモリ保護テーブルのような）システム管理資源にアクセスできる。ＣＢＥＡ定義のハードウェア資源は、ＰＰＥから見えるように物理アドレスに明示的にマップされる。それゆえ、いずれのＰＰＥも、適切かつ有効なアドレス値により、どんなリソースでも直接アドレスできる。ＰＰＥの主要機能は、システム内におけるＳＰＥタスクの割り当てと管理である。
【００１９】
ＳＰＥは、ＰＰＥに比べれば計算ユニットとしては複雑ではない。ＳＰＥにはシステム管理機能がないからである。ＳＰＥは、ＳＩＭＤ（single instruction,multiple data）による処理機能を備え、割り当てられたタスクを実行するために必要なデータ転送を（ＰＰＥによってセットアップされたアクセス属性にしたがって）開始する。ＳＰＵの目的は、計算ユニットのいっそうの高密度集積を要求し、所与の命令セットを効果的に実行できるようなアプリケーションを実現とすることである。システムにおいて、ＰＰＥに管理されるべきＳＰＵの数は、さまざまなアプリケーションについてコスト的に効率的な処理を実現できるように決められる。ＳＰＵは、新たな命令セットアーキテクチャを実装する。
【００２０】
ＭＦＣコンポーネントは、本質的にはデータ転送エンジンである。ＭＦＣは、ＣＥＬＬプロセッサのメインストレージとＳＰＥのローカルストレージの間におけるデータの転送、保護、同期に関する主要機能を担う。ＭＦＣコマンドは、転送の実行を示す。アーキテクチャ上におけるＭＦＣの最重要目的は、できるかぎり高速・正確にデータ転送を実行し、ＣＥＬＬプロセッサの全体としてのスループットを最大化することである。データ転送用コマンドは、ＭＦＣ・ＤＭＡコマンドとして参照される。これらのコマンドが変換されて、ローカルストレージ領域とメインストレージ領域の間のＤＭＡ転送となる。
【００２１】
通常、各ＭＦＣは、同時に複数のＤＭＡ転送をサポートし、複数のＭＦＣコマンドを保持・処理できる。このような機能を実現するため、ＭＦＣは、ＭＦＣコマンドキューを保持・処理する。ＭＦＣは、複数個の転送要求とキューに投入したり、それらを同時発行することもできる。各ＭＦＣは、対応するＳＰＵのためのキュー（ＭＦＣ・ＳＰＵ・コマンドキュー）と、他のプロセッサやデバイスのためのキュー（ＭＦＣ・プロキシ・コマンドキュー）を備える。論理的には、ＭＦＣキューの集合は、常に、ＣＥＬＬプロセッサ内の各ＳＰＵに対応づけられている。しかし、アーキテクチャ実装によっては、ＳＰＵグループのように複数のＳＰＵ間で単一の物理的なＭＦＣを共有することもできる。このような場合にも、ソフトウェアからは、すべてのＭＦＣに関連する装置がＳＰＵごとに別々にあるように見えなければならない。各ＭＦＣ・ＤＭＡ・データ転送要求コマンドは、ローカルストレージのアドレス（ＬＳＡ：local strage address）と有効アドレス（ＥＡ：effective address）の両方を含む。ローカルストレージアドレスは、該当ＳＰＵのローカルストレージ領域だけを直接アドレスできる。有効アドレスは、もう少し一般的に応用できる。実アドレス空間にエイリアス（別名：aliase）がなされているときには（すなわち、MFC-SR1[D]に'1'がセットされるとき）、全ＳＰＵのローカルストレージ領域も含めて、メインストレージを参照できるからである。
【００２２】
ＭＦＣは２種類のインタフェースを提供する。１つは、ＳＰＵ用であり、もう１つは、プロセスグループ内における他のプロセッサやデバイス全てのためである。ＳＰＵは、ＭＦＣ制御用にチャネルインタフェース（channel interface）を使う。この場合、ＳＰＵで実行されるコードは、当該ＳＰＵ用のＭＦＣ・ＳＰＵ・コマンドキューにだけアクセスできる。他プロセッサやデバイスは、メモリマップされたレジスタにより、ＭＦＣを制御できる。システム内のプロセッサやデバイスは、ＭＦＣを制御し、ＳＰＵに代わってＭＦＣ・プロキシ・要求コマンドを発行できる。ＭＦＣは、また、帯域予約やデータ同期もサポートする。ＳＰＵ間、および／または、ＳＰＵとＰＰＵ間、ＳＰＥとＰＰＥ間の通信用の装置には、シグナルイベントと対応づけられるシグナル通知レジスタが含まれる。通常、ＰＰＥとＳＰＥは、ＰＰＥがＳＰＥへメッセージを転送するルーターの役割を担うスター型トポロジーにて接続される。このようなトポロジーでは、ＳＰＥ同士はダイレクトに通信しない。代わりに、各ＳＰＥや各ＰＰＥは、一方通行のシグナル通知レジスタを持ち、これは、メールボックスとして参照される。メールボックスは、ＳＰＥとホストＯＳの同期をとるために使うことができる。
【００２３】
ＩＩＣコンポーネントは、ＰＰＥに対する割り込みの優先順位を管理する。ＩＩＣの主目的は、プロセッサ内の他のコンポーネントからの割り込みを、メインシステムの割込コントローラを使わずに扱うことである。ＩＩＣは、実際、セカンドレベルのコントローラである。ＣＢＥＡ準拠プロセッサに対する内部割り込み、あるいは、ＣＢＥＡ準拠プロセッサによるマルチプロセッサシステム内における割り込みの全てを扱うように想定されている。通常、システム割込コントローラは、ＣＥＬＬプロセッサに対する外部割り込みの全てに対応する。
【００２４】
ＣＥＬＬプロセッサシステムにおいては、ソフトウェアは、まず、外部のシステム割込コントローラからの割り込みがあったかを判定するために、しばしば、ＩＩＣをチェックしなければならない。ＩＩＣは、全てのＩ／Ｏデバイスからの割り込みの処理に関し、メインのシステム割込コントローラを代替するものではない。
【００２５】
ＣＥＬＬプロセッサには、２種類のストレージドメイン（storage domain：記憶領域）がある。ローカルストレージドメインとメインストレージドメインである。ＳＰＥのローカルストレージは、ローカルストレージドメイン内にある。他の装置やメモリは、全てメインストレージドメイン内にある。ローカルストレージは、記憶領域を１以上の分離領域から成り、各領域は特定のＳＰＵと関連付けられる。各ＳＰＵは、（データのロードやストアといった操作も含めて）自己に関連するローカルストレージドメイン内の命令のみを実行可能である。ローカルストレージのエイリアスが有効化されていないときには、システム内の他のストレージを対象とするデータ転送要求は、常に、（各ＳＰＵの）ローカルストレージドメインとメインストレージドメインの間でデータを転送するためのＭＦＣ・ＤＭＡコマンドを発行することでしか実行できない。
【００２６】
ＳＰＵプログラムは、ローカルアドレスによりローカルストレージドメインを参照する。ただし、特権ソフトウェアは、MFC-SR1の第Ｄビットを「１」にセットすることによって、ＳＰＵのローカルストレージドメインをメインストレージドメインにエイリアスできる。各ローカルストレージ領域には、メインストレージドメイン内の実アドレスが割り当てられることになる（実アドレスは、システムメモリにおけるバイト単位アドレスかＩ／Ｏデバイスにおけるバイト単位アドレスのいずれかである。）。これにより、特権ソフトウェアは、アプリケーションの有効アドレス空間にローカルストレージ領域を割り当てることが可能となり、あるＳＰＵのローカルストレージと別のＳＰＵのローカルストレージの間のＤＭＡ転送が可能となる。
【００２７】
別プロセッサやデバイスは、メインストレージドメインへのアクセスにより、直接的に、ローカルストレージ領域をアクセス可能となる。このローカルストレージ領域は、メインストレージドメインによって示される実アドレス空間に対して、所定の変換方式にてマップされている有効アドレスやＩ／Ｏバスアドレスによって、メインストレージドメインとエイリアスされている。
【００２８】
メインストレージドメインとエイリアスされているローカルストレージ領域を使ったデータ転送では、キャッシュが禁じられる。このようなアクセスは、ローカルストレージドメインにおいて、ＳＰＵのローカルストレージへのアクセス（たとえば、ＳＰＵのロード、ストア、命令フェッチ）と一貫性を保てないからである。ローカルストレージ領域をメインストレージドメインの実アドレス空間とエイリアスさせることにより、メインストレージ領域へアクセスする他のプロセッサやデバイスは、ローカルストレージに直接アクセスすることができる。しかし、エイリアスされたローカルストレージは、キャッシュ禁止にて処理されなければならないので、ＰＰＥのロード命令やストア命令による大量のデータ転送ではパフォーマンスが悪くなる。ローカルストレージドメインとメインストレージドメインの間におけるデータ転送では、ストール（stall）を避けるためにＭＦＣ・ＤＭＡ・コマンドを使用する。
【００２９】
ＣＢＥＡにおけるメインストレージへのアドレッシングは、パワーＰＣ・アーキテクチャにおいて定義されているアドレッシングと互換性がある。ＣＢＥＡは、パワーＰＣアーキテクチャのコンセプトを基礎としつつも、ＭＦＣによるメインストレージへのアドレッシングにまで拡張されている。
【００３０】
ＳＰＵやその他のプロセッサ、デバイス上において実行されるアプリケーションプログラムは、メインメモリにアクセスするために有効アドレスを使う。有効アドレスは、ＰＰＥがロード、ストア、分岐、キャッシュ命令を実行したり、後続命令をフェッチするときに計算される。ＳＰＵのプログラムは、ＭＦＣコマンドのパラメータとして有効アドレスを示さねばならない。「PowerPC Architecture,Book3」の「overview of address translation」に記載されている処理方法により、有効アドレスから実アドレスへの変換がなされる。実アドレスとは、変換された有効アドレスによって参照されるメインストレージ上における位置である。メインストレージは、システム内の全てのＰＰＥ、ＭＦＣ、Ｉ／Ｏデバイスによって共有される。このレベルのストレージに保持される情報の全ては、システム内の全プロセッサ、全デバイスから見ることができる。このストレージ領域は、構造的にはフラットであってもよいし、階層的なキャッシュ構造を備えてもよい。プログラムは、有効アドレスによってこのレベルのストレージを参照する。
【００３１】
システムのメインメモリは、通常、システムコンフィギュレーション（system configuration）、データ転送同期、メモリマップドＩ／Ｏ、Ｉ／Ｏサブシステムといった処理用の特殊ハードウェアレジスタやアレーと、汎用の不揮発性記憶媒体も含む。メインメモリには、さまざまな設定をすることができる。制約的な意味ではない設例として、表１は、ＣＢＥＡとして知られる実装のＣＥＬＬプロセッサについて、メインメモリにおけるアドレス空間のサイズを示す。
【００３２】
【表１】
2007157146.tif 000003
【００３３】
ＣＥＬＬプロセッサ１００は、プロセッサとシステム内においてクリティカル・リソース（critical resource）の管理機能を持ってもよい。ＣＥＬＬプロセッサの管理対象となるリソースは、ＴＬＢ（translation lookaside buffers）とデータ、命令キャッシュである。これらのリソースは実装依存のテーブルによって制御される。
【００３４】
ＴＬＢやキャッシュを管理するためのテーブルはＲＭＴとして参照され、各ＭＭＵと対応づけられる。このようなテーブルはオプショナルなものであるが、システムのボトルネックとなりうるクリティカル・リソースのためのテーブルは有用であることが多い。ＳＰＥグループは、ＤＭＡ転送のためのファーストレベルキャッシュとなるＳＬ１キャッシュをキャッシュ階層に含んでもよい。ＳＬ１キャッシュも、ＲＭＴを持ってもよい。
【００３５】
本実施例におけるメインメモリＭＥＭには、ＳＰＥやＰＰＥがロックフリー形式にてアトミックにアクセス可能なプリミティブ１０２が保持される。プリミティブ１０２は、２以上の部分データＤ１、Ｄ２、パリティ・バイトＰを含み、更に、ユーティリティ・バイトＵを含んでもよい。プリミティブ１０２は、ＳＰＥにおいて実行されるタスクについての情報（description）を示してもよい。この場合、プリミティブ１０２は、実行対象コードのメモリ位置やそのコードのパラメータを示してもよい。あるいは、プリミティブ１０２はアプリケーションの状態情報を示してもよい。ビデオゲームであれば、ゲームの変数（たとえば、プレーヤーの生命力）、仮想環境の情報（たとえば、ある岩オブジェクトの場所）、あるいは、音声処理情報といった情報などでもよい。プリミティブを操作するコード１０４、１０６は、１以上のＳＰＥのローカルストア、１以上のＰＰＥのＬ１キャッシュ、メインメモリＭＥＭなどに保持される。後述するように、ＳＰＥとＰＰＥでは命令（instruction）が多少違っている。このため、ＳＰＥ用命令セットである第１セット１０４と、ＰＰＥ用命令セットである第２セット１０６という２種類の命令体系が存在する。実装上は、第１セット１０４はＳＰＥが必要とするときにＳＰＥのローカルストアに転送され、第２セット１０６はＰＰＥが必要とするときにＬ１キャッシュに転送されることになる。コード１０４、１０６は、メインメモリＭＥＭにあるもっと大きなプログラム１０８を呼び出すためのサブルーチンコールやファンクションコールであってもよい。
【００３６】
コードセット１０４、１０６を実行することにより、ＳＰＥやＰＰＥはアトミックにプリミティブ１０２にアクセスしてこれを更新する。どちらのコードセットもパリティ・バイトＰに依存する。パリティ・バイトＰは、部分データＤ１、Ｄ２のうちのどちらが有効部でどちらが無効部かを示す。有効部は関連情報を持ち、無効部は非関連情報を持つ。第１コード１０４の実行により、ＳＰＥは部分データとパリティ・バイトを読み出して有効部を更新できるが、パリティ・バイトＰを変更することはできない。第２コード１０６の実行により、ＰＰＥは有効部を読み出したり、プリミティブ１０２の無効部を更新したり、パリティ・バイトＰを変更して無効部を有効部に変更したりできる。
【００３７】
ＳＰＥとＰＰＥのどちらもプリミティブ１０２にアクセスできるので、どちらのコードセット１０４、１０６も、「第１のプロセッサ（ＳＰＥまたはＰＰＥ）がプリミティブを読み出したあと、第１のプロセッサがプリミティブを更新する前に第２のプロセッサがプリミティブを更新した」という状況が発生したときに、ＰＰＥまたはＳＰＥにそれを通知する。このために「予約付き読み出し」や「条件付き書き込み」のような既知の命令を使う。予約付き読み出しコマンドは、アドレスからデータをロードすると同時にそのアドレスに「予約」を設定する。この「予約」とは、予約がなされてからそこに値を書き込もうとするまでの間に、そのアドレスになんらかのデータをロードしようとした別のプロセッサがあることをプロセッサに通知することの予約である。このコマンドは、条件付き書き込みコマンドとの関連で使われることが多い。条件付き書き込みコマンドにおいて、プロセッサは、予約が失効していないことを条件として、そのアドレスへの書き込みを行う。予約失効は、予約されたデータアドレスが更新された可能性を示すが、実際に更新されたかどうかは明確にしていない。更新されたか否かを明確にするためには、（たとえば、予約付きで）そのアドレスを読み出し、現在の値と予約時にそのアドレスにあった値とを比較しなければならない。
【００３８】
条件付き書き込みと予約付き読み出しの処理方法を以下に示す。あるＳＰＵがプリミティブ１０２に条件付き書き込みするとする。別のＳＰＵがプリミティブ１０２に書き込みをしていなければ、この条件付き書き込みは成功する。第１のＳＰＵが条件付き書き込みする前に第２のＳＰＵがプリミティブ１０２を更新したとする。ここで第１のＳＰＵが条件付き書き込みを実行しようとすると、予約が失効しているので条件付き書き込みは失敗し、プリミティブ１０２の値は更新されない。
【００３９】
ＣＥＬＬプロセッサの実装技術について更に詳述する。以下の内容は、本発明の実施例に関連したデータ構造と処理方法について説明するものである。以下の実施例は上記したアーキテクチャを持つＣＥＬＬプロセッサについての実装を制約するものではない。とはいえ、以下の実施例は、多かれ少なかれ、ＳＰＥとＰＰＥの両方についてのアトミック命令が直面し利用されうる環境としてのＣＥＬＬアーキテクチャによる実装を示す。
【００４０】
図２は、本実施例に関して、ＰＰＥやＳＰＥにより取り扱い可能なアトミック命令を実装するＣＥＬＬプロセッサ２００の一例を示す。このＣＥＬＬプロセッサは、メインメモリ２０２と、単一のＰＰＥ２０４、８つのＳＰＥ２０６を備えている。ただし、ＣＥＬＬプロセッサには任意の数のＳＰＥを設置できる。図２において、リング型のエレメント相互接続バス２１０により、メモリ、ＰＰＥ、ＳＰＥは、互いに、また、Ｉ／Ｏデバイス２０８とも通信可能である。メモリ２０２は、上記したプリミティブ１０２と特徴において共通するプリミティブ２０３を保持する。メモリ２０２のプログラム２０９は、上記したプログラム１０８と特徴において共通する。少なくとも１つのＳＰＥ２０６のローカルストアにあるコード２０５は、上記したコード１０４と特徴において共通する。ＰＰＥはＬ１キャッシュに、上記したコード１０６と特徴が共通するコード２０７を含む。コード２０５、２０７は、ＳＰＥやＰＰＥからアクセスするために、必要に応じてメモリ２０２に保持されてもよい。
【００４１】
図３は、本実施例におけるプリミティブ３００の例である。プリミティブ３００は、２つの対等な部分データに分かれる。左部分データ３０２と右部分データ３０４は同じサイズである。プリミティブ全体のサイズは、ＳＰＥが１回のＤＭＡ転送処理で扱えるサイズである。ＰＰＥは、もっと小さな小区分（サブセクション）単位にてプリミティブにアクセスする。制約的な意味ではない例として、プリミティブ３００は、一度に１２８バイトをアトミックに扱うＳＰＥや一度に８バイトをアトミックに扱うＰＰＥが内部的に操作できるように形成されてもよい。実装上においては、プリミティブ３００は、ＰＰＥとＳＰＥの両方とも更新可能な６３バイトのアトミック型に基づいてもよい。ＳＰＥが取り扱える１２８バイトのデータ要素を取り出し、６３バイトの部分データを２つ取り出し、それぞれについて１バイトずつ取り出せばよい。第１残余バイトはパリティ・バイト３０６となる。第２残余バイトはユーティリティ・バイト３０８として使われる。上記したように、２つの部分データ３０２、３０４のうちの一方だけが意味のある値を持つ。他方は未定義となるか、意味のない値を持つ。１ビット程度の小さなパリティ・バイト３０６は、どちらの部分データが有効部であるかを示す。プリミティブ３００の分割やパリティ・バイト３０６の初期値の設定は、プリミティブ３００を取り扱うプログラム１０８の初期化処理において実行してもよい。同図上側では、パリティ・バイト３０６は「０」に設定されているので、左部分データ３０２は有効、右部分データ３０４は無効となる。同図下側では、パリティ・バイト３０６は「１」にセットされているので、左部分データ３０２は無効、右部分データ３０４は有効となる。
【００４２】
ＳＰＵはアトミックにプリミティブの有効部３０２を更新できるが、パリティ・バイト３０６の値は変更しない。最初に読み出したパリティ・バイトの値がなんであれ、ＳＰＵはこれを書き戻す。実装上は、ＳＰＵは部分データ３０２全体を読み出して、有効部だけを変更し、更新値（と更新されないパリティ・バイト値）をメインメモリのプリミティブ３０２のあるところに書き戻す。ＰＰＵは、８バイトずつ無効部を更新し、パリティ・バイトをアトミックに変更する。
【００４３】
図４Ａは、ＳＰＥによるプリミティブ３００のアトミックな更新処理過程を示すフローチャートである。同図左側に示す処理過程４００は、ＳＰＵの実行命令として実装される。処理過程４００の各ステップは、上記した命令コード１０４に対応している。ステップ４０２において、ＳＰＥはプリミティブ３００の全１２８バイトを予約付き読み出しする。同図に示すように、プリミティブ３００全体がＳＰＥのローカルストア４０１にロードされる。ステップ４０４において、ＳＰＥはパリティ・バイトをチェックして、有効部を特定する。同図の場合、パリティ・バイト値が「０」となっているので、左部分データ３０２は有効、右部分データ３０４は無効である。また、左部分データの値は「１０」となっている。ＳＰＵは、ＳＰＥ用実行命令コードにより、ローカルストアの有効部３０２の値を、たとえば、「２０」に変更する。有効部の１バイト以上のカウンタ値をインクリメントするとしてもよい。ただし、パリティ・バイト３０６値は変更しない。ステップ４０６において、ＳＰＥは、メインメモリにおけるプリミティブ３００のアドレスに対する条件付き書き込みの実行により、メインメモリのプリミティブ値を更新しようとする。少なくとも有効部３０２とパリティ・バイト３０６は、条件付き書き込みの対象となる。実装上は、ＳＰＥは、無効な右部分データ３０４も含めて、更新後のプリミティブ３００全体を書き戻す方が簡単である。ステップ４０８において条件付き書き込みが成功すると、アトミック３００は更新完了となる。ＳＰＥは、ステップ４０９の次の処理を実行する。
【００４４】
条件付き書き込みが失敗しない唯一の条件は、ステップ４０２の予約付き読み出しからステップ４０６の条件付き書き込みまでに、プリミティブ３００への書き込みが割り込み発生しないことである。図４Ｂは、条件付き書き込みが成功しない場合のフローチャートである。
【００４５】
図４Ｂの左側に示す処理過程４１０は、ＳＰＵの実行命令として実装される。処理過程４１０の各ステップも、上記した命令コード１０４に対応している。図４Ａと同じく、ステップ４１２において、ＳＰＥ１は、プリミティブ３００の全１２８バイトを予約付き読み出しして、プリミティブ３００の値をＳＰＥのローカルストア４０１にロードする。ステップ４１４において、ＳＰＥはパリティ・バイトをチェックして、有効部を特定する。先の例と同じく、パリティ・バイト値は「０」なので、左部分データ３０２は有効、右部分データ３０４は無効である。先の例と同じく、左部分データ３０２の値は「１０」である。先の例と同じく、ＳＰＥは、ＳＰＥ用実行命令コードにより、ローカルストアの有効部３０２の値を「２０」に変更する。ＳＰＥは、パリティ・バイト３０６の値は変更しない。ステップ４１６において、ＳＰＥ１は、メインメモリにおけるプリミティブ３００のアドレスに対する条件付き書き込みの実行により、メインメモリのプリミティブ値を更新しようとする。
【００４６】
ここでは、ＳＰＥは単一操作（single operation）にてプリミティブ３００の全１２８バイトを読み出しているが、ＳＰＵは、２以上のステージに分けてプリミティブ３００を読み出してもよい。コード１０４をシンプルにするため、ＳＰＥはパリティ・バイト３０６も含めてプリミティブ３００の半分をローカルストアに読み出してもよい。ＳＰＥは、最初に右部分データ３０４とパリティ・バイト３０６を読んでもよい（このとき、ユーティリティ・バイト３０８も読み込んでもよい）。ＳＰＥは、有効部を読み出したか判断するためにパリティ・バイト３０６をチェックする。有効部を読み出していれば、更新可能である。読み出したのが有効部でなければ、ＳＰＵはプリミティブの残り部分をローカルストアの最初に読み出し部分に上書きする。このような処理方法によれば、ローカルストアに並列させるのではなく、ローカルストアの同じ場所に更新したいデータをロードできる。
【００４７】
図４Ｂに示す例では、ステップ４１６にＳＰＥ１が条件付き書き込みを実行する前のステップ４１５において、ＳＰＥ２がプリミティブ３００有効部３０２に「３０」を書き込んでいる。この場合、ＳＰＥ１の予約は失効し、ステップ４１８における条件付き書き込みは失敗する。ステップ４１２の予約付き読み出しからステップ４１６の条件付き書き込みまでの間にＰＰＥが無効な右部分データ３０４を更新したときにも、予約失効となる。プリミティブを更新するためには、ＳＰＥ１の条件付き書き込みが成功しなければならない。しかし、これは、必ずしも、ＳＰＥ２によるプリミティブ３００の更新値に依存しないかもしれない。たとえば、ＳＰＥ２が有効部の１バイトかそれ以上について値を設定しても、それはあるプロセスが完了したことを示すだけであり、プリミティブ３００の値自体は更新されていないかもしれない。もしそうであれば、ＳＰＥ１はプリミティブ３００の値を更新する必要はない。それでも、ＳＰＥ１がプリミティブ３００値を更新する必要があるかもしれない。ステップ４２０において、ＳＰＥ１はアトミックの新しい値を予約付き読み出しし、更新し、必要であれば、再度条件付き書き込みを実行する。このときに割り込みが発生しなければ、書き込みは成功する。
【００４８】
本実施例においては、ＳＰＥはプリミティブ３００の無効部を更新したり、パリティ・バイト３０６を変更することはない。ただし、ＳＰＥによるプリミティブ３００のアドレスへの書き込みでは、通常、全１２８バイトがアトミックに書き込まれる。ＳＰＥが全１２８バイトを書き戻すときには、以前に読み出された元々のパリティ・バイトと、元々の無効部も書き戻す。このため、ＰＰＵが８バイト区分を更新している間に無効部が上書きされることがある。このような事象が発生していることをＰＰＵに通知するために、ＰＰＥはパリティ・バイト３０６の予約付き読み出しと条件付き書き込みを実行する。パリティ・バイトの予約付き読み出しと条件付き書き込みにより、ＰＰＵはパリティ・バイト３０６の条件付き書き込み時において、更新中の部分が予約失効後に上書きされたことがわかる。
【００４９】
図５Ａは、ＰＰＥがどのようにしてプリミティブ３００をアトミックに更新するかを示す。同図左側に示す処理過程５００は、ＰＰＵの実行命令として実装される。処理過程５００の各ステップは、上記した命令コード１０６のサブセットに対応している。この例では、ＰＰＥは、Ｌ１キャッシュ５０１のレジスタを介して、無効部に「３０」という値を書き込むことによってプリミティブを更新しようとしている。ステップ５０２において、ＰＰＥはパリティ・バイト３０６だけを予約付き読み出しする。パリティ・バイトの値はＰＰＥのＬ１キャッシュ５０１にあるレジスタに読み出される。この例では、パリティ・バイト３０６の値は「０」となっているので、左部分データ３０２は有効、右部分データ３０４は無効となる。ステップ５０４において、１回当たり８バイトかそれ以下の小区分単位にて、無効な右部分データ３０４の位置への連続的な書き込みにより、無効部３０４を更新する。ＰＰＥは無効部をアトミックに更新する必要はない。非アトミック処理でも安全に実行できる。パリティ・バイトの書き込みだけはアトミックに実行しなければならない。実装によっては、アトミックな書き込みがＰＰＥの「アーリー・アウト（early out）」を引き起こすことがある。その場合、無効部へのアトミックな書き込みに失敗すると、更新プロセスがリスタートする可能性がある。ＰＰＥがアーリー・アウトを使用しないなら、アトミックにパリティ・バイトを更新しようとする前に全６３バイトを更新しなければならないであろう。ＰＰＥは、プリミティブ３００の情報を更新するために、必要な数だけの小区分５０３を書き込む。書き込みがなされると、ステップ５０６において、ＰＰＥは、条件付き書き込みによって、パリティ・バイトの値を変更しようとする。ステップ５０８において予約が失効していれば、パリティ・バイトの条件付き書き込みをが失敗し、ＳＰＵはアボートし、無効な右部分データ３０４の更新プロセスが再スタートする。ステップ５０８において予約が失効していなければ、条件付き書き込みは成功して、ステップ５０９においてＰＰＵはパリティ・バイト３０６の値を変更する。この例ではパリティ・バイト３０６の値が０から１に変化し、右部分データ３０４が有効になり、左部分データ３０２が無効となっている。
【００５０】
図５Ｂは、ＰＰＥがどのようにしてプリミティブ３００をアトミックに読み出すかを示す。同図左側に示す処理過程５１０は、ＰＰＵの実行命令として実装される。処理過程５１０の各ステップは、上記した命令コード１０６の別のサブセットに対応する。ステップ５１２において、ＰＰＵはパリティ・バイト３０６を予約付き読み出しする。この例では、パリティ・バイトの値は「０」となっているので、左部分データ３０２は有効、右部分データ３０４は無効となる。ステップ５１４において、１回当たり８バイト程度の小区分５０３の単位にて、パリティ・バイト３０６によって指定されている有効な左部分データ３０２をＬ１キャッシュ５０１のレジスタに読み出す。ステップ５１６において、ＰＰＵは、ＰＰＵによる読み出し中にプリミティブ３００の値が更新されたかどうかを判定するために、メインメモリのパリティ・バイト３０６に対して条件付き書き込みを実行する。ＰＰＵは、プリミティブの有効部を読み出しても更新はしないので、予約付き読み出しのステップにおいて読み出したパリティ・バイトの値の再書き込みとなる。ＰＰＥが有効な左部分データ３０２を読み出している間に、別のプロセッサ（たとえば、ＳＰＵ）がプリミティブを更新していれば、ステップ５１８におけるパリティ・バイトへの条件付き書き込みは失敗し、そうでなければ成功する。ＰＰＥは、パリティ・バイトへの条件付き書き込みが成功するまで、シーケンスを繰り返す。ＰＰＥは、アプリケーション（たとえば、プログラム２０９）によるアトミック３００の更新理由によっては他の処理を実行してもよい。たとえば、アプリケーションが左部分データ３０２の値をアトミックにインクリメントしようとしているのなら、インクリメントできるまでループしてもよい。毎回同じ値に更新する必要はない。
【００５１】
ユーティリティ・バイト３０８は、アトミック処理の機能を拡張する。たとえば、ＰＰＵからプリミティブにアクセスしやすいアプリケーションを考える。このようなアプリケーションでは、プリミティブの更新についてはＳＰＵよりもＰＰＵの方が重要である。制約的な意味ではない例として、ユーティリティ・バイト３０８の値は、プリミティブ３００の更新についてＰＰＵを優先すべきか否かをＳＰＥに示す。ユーティリティ・バイトが所定値のときには、プリミティブ３００を読み出そうとするＳＰＥは、プリミティブの読み書きの前の待機サイクル数を設定する。ユーティリティ・バイト３０８には、ＳＰＵの待機サイクルを示すための（数）ビットが含まれてもよい。ユーティリティ・バイト３０８はプリミティブをマスクするサイズを示してもよい。すなわち、プリミティブが何分割され、各部分データの大きさがどのくらいとなるかを示してもよい。ユーティリティ・バイト３０８は、他のユーティリティ機能、たとえば、フラグ、ＳＰＥの優先度、その他アプリケーション特有の機能などのために使用されてもよい。当業者であれば、実装機能に応じてユーティリティ・バイト３０８として２バイト以上を割り当ててもよいことは用意に理解されるであろう。
【００５２】
本実施例によれば、所定のアプリケーションを２以上のＰＰＵやスレッドに対して実装できる。一般的には、ある時点においてプリミティブ３００を更新できるのは１つのＰＰＵスレッドだけである。オペレーティング・システム（ＯＳ：Operating System）のレベルのミューテックスは、別々のＰＰＵスレッドを排他制御するために使用される。これに対して、本実施例に示したプリミティブの処理はロックフリーである。更新中にＰＰＵプロセスがコンテキスト・スイッチ（context switch）しても、ＳＰＵはプリミティブの更新を続けることができる。ＳＰＵとＰＰＵが必要なときに共通のアトミック型を操作できるので、合理的で妥当な処理方法となる。ＣＥＬＬプロセッサにおいて、ロックフリーなプログラミングの実装はとても重要である。（たとえば、ＣＤ−ＲＯＭ・コントローラやネットワーク・カードについての）Ｉ／Ｏ処理は、通常、ＰＰＵプロセスの仕事である。ＳＰＵとＰＰＵの両方がアトミックに操作できるプリミティブにより、ＰＰＵが別のＩ／Ｏ処理に移行してもＳＰＵは処理を継続できる。これは、パフォーマンスの大幅な低下を避ける上で有効である。
【００５３】
上述した内容は、単一のＰＰＥと複数のＳＰＵを備えるＣＥＬＬプロセッサについて言及しているが、本実施例は複数のＰＰＥを備えるＣＢＥＡのようなＣＥＬＬプロセッサ・アーキテクチャにも応用可能であることは当業者には理解されるであろう。複数のＰＰＥを備えるＣＥＬＬプロセッサにおいては、すべてのＰＰＥのために１つのミューテックスを用意して、ある時点においては１つのＰＰＥの１つのプロセスだけがアトミックを更新できる方が望ましい。
【００５４】
本実施例は、メインメモリを共有するアトミックなプロセスがもっと小さくても機能する。本実施例は、別々のプロセッサが同一のメインメモリにアクセスする上で、アトミックなプロセス（すなわち、１２８バイトのデータ構造を６３バイトに分割して、２つの残余バイトを取り出すプロセス以外のプロセス）についてアクセスの「粒度（grain）」の違いにも対応できる。かなり大きなサイズのプリミティブは、適切な数の部分データに分割すればよい。パリティ・バイトが３値以上を示せるように設定してた上で、アトミックのどの部分データが有効かを示してもよい。たとえば、６５バイトのアトミックを、８バイトサイズ×８個の部分データに分割し、パリティ・バイトのために、３ビット以上のエクストラ・バイトを設定してもよい。パリティ・バイトの値は０から７のいずれかとなり、８つの部分データうちどれが有効かを示す。
【００５５】
本実施例によれば、ＳＰＥが取り扱える大きなサイズでアトミック処理を実行できる一方、ＰＰＥが取り扱える小さなサイズでもアトミック処理を実行できる。本実施例は、ＳＰＵタスクの管理において、特に、ＳＰＵとＰＰＵの両方が新たに実行すべきタスクをアトミックに追加する必要があるときに有用である。
【００５６】
以上は、本発明の最適な実施例の完全な記述であるが、さまざまな変更、変形、等価物への置き換えが可能である。それゆえ、本発明の範囲は、上記記述に関してではなく、請求項により定義されるべきであり、完全な等価物の範囲も含まれる。記述された特徴は、それが好ましいものであれ、そうでないものであれ、上記したさまざまな特徴と組み合わされてもよい。請求項においては、通常、特に断らない限りは、各要素は１またはそれ以上の数量を想定している。請求項の記載事項は、「〜手段」のような記載によって、明示される場合のほかは、いわゆるミーンズ・プラス・ファンクション特有の限定的意味で解してはならない。
【図面の簡単な説明】
【００５７】
【図１】本実施例において、ＣＥＬＬのタスクおよびデータの管理を実装するＣＥＬＬブロードバンドエンジンアーキテクチャの模式図である。
【図２】本実施例におけるＣＥＬＬプロセッサの模式図である。
【図３】本実施例におけるデュアル・アクセス・プリミティブのブロック図である。
【図４Ａ】本実施例において、ＳＰＵがデュアル・アクセス・プリミティブを更新するときのフローチャートである。
【図４Ｂ】本実施例において、ＳＰＵによるデュアル・アクセス・プリミティブの更新処理が中断するときのフローチャートである。
【図５Ａ】本実施例において、ＰＰＵがデュアル・アクセス・プリミティブを更新するときのフローチャートである。
【図５Ｂ】本実施例において、ＰＰＵがデュアル・アクセス・プリミティブを読み出すときのフローチャートである。
【図１】
2007157146.tif 000004
【図２】
2007157146.tif 000005
【図３】
2007157146.tif 000006
【図４Ａ】
2007157146.tif 000007
【図４Ｂ】
2007157146.tif 000008
【図５Ａ】
2007157146.tif 000009
【図５Ｂ】
2007157146.tif 000010