(57)【要約】セルプロセッサにおけるセルプロセッサタスク管理を述べる。セルプロセッサは、メインメモリ、１以上のパワープロセッサユニット（ＰＰＵ）、１以上のシナジスティックプロセッシングユニット（ＳＰＵ）をもつ。各ＳＰＵはプロセッサとローカルメモリをもつ。１以上のＳＰＵで動作するＳＰＵタスクマネージャ（ＳＴＭ）は、メインメモリに格納された１以上のタスク定義を選択されたＳＰＵのローカルメモリに読み出す。タスク定義に含まれる情報にもとづいて、ＳＰＵはタスク定義に関するコードおよび／またはデータをメインメモリから読み出し、選択されたＳＰＵのローカルメモリにロードする。その後、選択されたＳＰＵはこのコードおよび／またはデータを用いて１以上のタスクを実行する。【選択図】図１
2009510613.tif 000002
【特許請求の範囲】
【請求項１】
メインメモリ、１以上のパワープロセッサユニット（ＰＰＵ）、１以上のシナジスティックプロセッシングユニット（ＳＰＵ）を含み、各ＳＰＵはプロセッサとローカルメモリを含むセルプロセッサにおいて、１以上のＳＰＵによって実行されるタスクを管理する方法であって、当該方法は、
１以上のＳＰＵで動作するＳＰＵタスクマネージャ（ＳＴＭ）の制御下で、前記メインメモリに格納された１以上のタスク定義を選択されたＳＰＵのローカルメモリに読み出すステップと、
前記１以上のタスク定義に含まれる情報にもとづいて、前記タスク定義に関するコードおよび／またはデータをメインメモリから読み出し、前記選択されたＳＰＵのローカルメモリにロードするステップと、
前記選択されたＳＰＵにおいて前記コードおよび／またはデータを用いて１以上のタスクを実行するステップとを含むことを特徴とする方法。
【請求項２】
１以上のタスク定義を読み出すステップは、２以上のタスク定義を読み出すことを含む請求項１の方法。
【請求項３】
１以上のタスク定義は、コード要求と前記コードが入ったメモリアドレスへのポインタを含む請求項１の方法。
【請求項４】
前記コードおよび／またはデータは、前記ローカルストアにメモリスペースを静的に割り当てる位置独立コードによって特徴づけられた１以上のプログラムを含む請求項１の方法。
【請求項５】
前記コードおよび／またはデータは、前記ローカルストアにメモリ空間を動的に割り当てるプログラムを含む請求項１の方法。
【請求項６】
前記プログラムは位置独立コードではない請求項５の方法。
【請求項７】
前記タスク定義は、前記選択されたＳＰＵにロードすべき前記データおよび／またはコードのサイズを含む請求項１の方法。
【請求項８】
前記タスク定義は入出力（Ｉ／Ｏ）ダイレクトメモリアクセス（ＤＭＡ）に対して要求されるローカルストア空間の最大容量を含む請求項１の方法。
【請求項９】
２以上のタスクがタスク定義および入出力（Ｉ／Ｏ）データに対するコンテキストバッファを共有する請求項１の方法。
【請求項１０】
前記１以上のタスクからの出力データを前記メインメモリまたは別のＳＰＵのローカルストアに格納するステップをさらに含む請求項１の方法。
【請求項１１】
前記選択されたＳＰＵで前記１以上のタスクを実行している間、別のタスク定義または他のコードおよび／またはデータをロードし、出力をメインメモリに格納するステップをさらに含む請求項１の方法。
【請求項１２】
前記１以上のタスク定義のそれぞれは優先度を含む請求項１の方法。
【請求項１３】
前記１以上のタスクは、１以上のタスクキューにまとめられる請求項１の方法。
【請求項１４】
高い優先度のタスクキューは低い優先度のタスクキューよりも前に処理される請求項１３の方法。
【請求項１５】
前記１以上のタスクキューは循環式である請求項１３の方法。
【請求項１６】
１以上のタスクを１以上のタスクキューに追加するために１以上のＰＰＵを用いるステップをさらに含む請求項１３の方法。
【請求項１７】
前記タスクキューの一つへのアクセスをアトミックミューテックスで制限するステップをさらに含む請求項１３の方法。
【請求項１８】
前記アトミックミューテックスは１２８バイトのアトミックミューテックスである請求項１７の方法。
【請求項１９】
前記アトミックミューテックスは、ロックする前記メインメモリの領域に関する情報を含む請求項１７の方法。
【請求項２０】
前記アトミックミューテックスは前記タスクキューへのアクセスがロックされているかどうかに関する情報を含む請求項１７の方法。
【請求項２１】
前記アトミックミューテックスは前記タスクキューの他のどのタスクが進行中であるかに関する情報を含む請求項１７の方法。
【請求項２２】
前記アトミックミューテックスは前記タスクキューの進行中の他のタスクの位置に関する情報を含む請求項１７の方法。
【請求項２３】
アクセスを制限するステップは、前記キューのどのタスクが既に取り出されたかを他のＳＰＵおよび／またはＰＰＵに通知するカウンタをデクリメントまたはインクリメントするステップを含む請求項１７の方法。
【請求項２４】
１以上の前記タスクキューは、１以上の以前のタスクが完了するまでは１以上の後続のタスクが始まらないことを保証するバリアコマンドを含む請求項１３の方法。
【請求項２５】
前記メインメモリから前記１以上のタスク定義をロードするステップは、タスクキュー０のタスク定義から前記メインメモリ内の前記タスクのメモリアドレスを読み出すステップを含む請求項１の方法。
【請求項２６】
前記タスクの前記メモリアドレスはコードとデータの両方を含む請求項２５の方法。
【請求項２７】
前記メインメモリから前記１以上のタスクをロードするステップは前記タスクに対する競合度をロードするステップを含む請求項１の方法。
【請求項２８】
前記１以上のタスクの競合を前記１以上のＳＰＵの間でバランスするステップをさらに含む請求項１の方法。
【請求項２９】
前記メインメモリから前記１以上のタスクをロードするステップは、前記タスクに対する最大競合度および／または最小競合度をロードするステップを含む請求項１の方法。
【請求項３０】
前記１以上のタスクは１以上のタスクキューにまとめられ、当該方法は、アトミックな予約消失イベントを待つステップをさらに含む請求項１の方法。
【請求項３１】
１以上のタスクを実行するステップは、前記メインメモリのある位置から前記ローカルストアへデータをコピーし、コピーされたデータを前記ローカルストアから前記メインメモリの別の位置へ転送するステップを含む請求項１の方法。
【請求項３２】
１以上のタスク定義を読み出すステップは、単一のＳＰＵで２以上のタスク定義を互いに並列に読み出すステップを含む請求項１の方法。
【請求項３３】
１以上のタスク定義を読み出すステップは、同一のＳＰＵで別のタスクのためにデータを処理することと並列にタスク定義を読み出すステップを含む請求項１の方法。
【請求項３４】
１以上のタスク定義を読み出すステップは、同一のＳＰＵで別のタスクのためにデータを処理することと並列に、かつ、さらに別のタスクからのデータを出力することと並列に、タスク定義を読み出すステップを含む請求項１の方法。
【請求項３５】
１以上のタスク定義を読み出すステップは、同一のＳＰＵで別のタスクからのデータを出力することと並列にタスク定義を読み出すステップを含む請求項１の方法。
【請求項３６】
１以上のタスクを実行するステップは、あるＳＰＵでタスクからのデータを処理することと並列に同一のＳＰＵで別のタスクからのデータを出力するステップを含む請求項１の方法。
【請求項３７】
１以上のタスクを実行するステップは、第１タスクからのデータを処理することと並列に第２タスクからのデータを入力し、さらに並列に第３タスク用のタスク定義を読み出し、さらに並列に第４タスクのためにデータを出力するステップを含む請求項１の方法。
【請求項３８】
データバスと、
前記データバスに接続され、１以上のタスク定義を含むメインメモリと、
前記データバスに接続された中央プロセッサと、
前記データバスに接続され、それぞれがシナジスティックプロセッサユニット（ＳＰＵ）とローカルストアを有する１以上のシナジスティックプロセッシングエレメント（ＳＰＥ）と、
１以上の前記ＳＰＵ上で実行されるＳＰＵタスクマネージャ（ＳＴＭ）とを含み、
前記ＳＴＭは前記ＳＰＵに、
前記メインメモリに格納された１以上のタスク定義を選択されたＳＰＵのローカルメモリに読み出し、
１以上のタスク定義に含まれる情報にもとづいて、前記タスク定義に関するコードおよび／またはデータをメインメモリから読み出し、前記選択されたＳＰＵのローカルメモリにロードするように命じるように構成されることを特徴とするセルプロセッサ。
【請求項３９】
１以上のタスク定義は、コード要求と前記コードが入ったメモリアドレスへのポインタを含む請求項３８のプロセッサ。
【請求項４０】
各タスク定義は優先度の値を含む請求項３８のプロセッサ。
【請求項４１】
各タスク定義は競合値を含む請求項３８のプロセッサ。
【請求項４２】
各タスク定義は最大許容競合値を含む請求項３８のプロセッサ。
【請求項４３】
各タスク定義は最小競合値を含む請求項３８のプロセッサ。
【請求項４４】
各タスク定義はステートの値を含む請求項３８のプロセッサ。
【請求項４５】
前記ワークキューの前記メモリアドレスはコードとデータの両方を含む請求項３８のプロセッサ。
【請求項４６】
前記１以上のタスクは、１以上のタスクキューにまとめられる請求項３８のプロセッサ。
【請求項４７】
前記ＳＴＭは高い優先度のタスクキューを低い優先度のタスクキューよりも前に処理するために選択するように構成される請求項４６のプロセッサ。
【請求項４８】
前記１以上のタスクキューは循環式である請求項４６のプロセッサ。
【請求項４９】
前記タスクキューの一つへのアクセスはアトミックミューテックスで制限される請求項４６のプロセッサ。
【請求項５０】
前記アトミックミューテックスは１２８バイトのアトミックミューテックスである請求項４９のプロセッサ。
【請求項５１】
前記１２８バイトのアトミックミューテックスは、ロックステート用に４バイト、完了したタスクのカウント用に２バイト、および最大４８８タスクのステート情報が入る１２２バイトを含む請求項５０のプロセッサ。
【請求項５２】
前記アトミックミューテックスは、ロックする前記メインメモリの領域に関する情報を含む請求項４９のプロセッサ。
【請求項５３】
前記アトミックミューテックスは前記タスクキューへのアクセスがロックされているかどうかに関する情報を含む請求項４９のプロセッサ。
【請求項５４】
前記アトミックミューテックスは前記タスクキューの他のどのタスクが進行中であるかに関する情報を含む請求項４９のプロセッサ。
【請求項５５】
前記アトミックミューテックスは前記タスクキューの進行中の他のタスクの位置に関する情報を含む請求項４９のプロセッサ。
【請求項５６】
アクセス制限には、前記キューのどのタスクが既に取り出されたかを他のＳＰＵおよび／またはＰＰＵに通知するカウンタをデクリメントまたはインクリメントすることを含む請求項４９のプロセッサ。
【請求項５７】
１以上の前記タスクキューは、１以上の以前のタスクが完了するまでは１以上の後続のタスクが始まらないことを保証するバリアコマンドを含む請求項４６のプロセッサ。
【請求項５８】
前記コードおよび／またはデータは、前記メインメモリのある位置から前記ローカルストアへデータをコピーし、コピーされたデータを前記ローカルストアから前記メインメモリの別の位置へ転送するように構成されたコードを含む請求項３８のプロセッサ。
【請求項５９】
１以上のパワープロセッサユニット（ＰＰＵ）、１以上のシナジスティックプロセッシングエレメント（ＳＰＥ）を含み、各ＳＰＥはシナジスティックプロセッサユニット（ＳＰＵ）とローカルメモリを含むセルプロセッサにおいて、１以上のＳＰＥ上でコードとデータを管理する方法を実行するためのプロセッサ読み込み可能なインストラクションセットが具体化されたプロセッサ読み込み可能な媒体であって、
当該方法は、
１以上のＳＰＵで動作するＳＰＵタスクマネージャ（ＳＴＭ）の制御下で、前記メインメモリに格納された１以上のタスク定義を選択されたＳＰＵのローカルメモリに読み出すステップと、
前記１以上のタスク定義に含まれる情報にもとづいて、前記タスク定義に関するコードおよび／またはデータをメインメモリから読み出し、前記選択されたＳＰＵのローカルメモリにロードするステップと、
前記選択されたＳＰＵにおいて前記コードおよび／またはデータを用いて１以上のタスクを実行するステップとを含むことを特徴とする媒体。
【請求項６０】
データプロセッシングシステムであって、
一つ以上のセルプロセッサを含み、
各セルプロセッサは、メインメモリと、パワープロセッサユニット（ＰＰＵ）と、１以上のシナジスティックプロセッシングユニット（ＳＰＵ）とを含み、
各ＳＰＵは、プロセッサとローカルメモリを有し、
前記メモリ、前記ＰＰＵ、前記ＳＰＵは互いにデータバスで結合されており、
前記メインメモリおよび／または前記ローカルメモリは、１以上のＳＰＵ上でコードとデータを管理する方法を実行するためのプロセッサで実行可能なインストラクションを含み、
当該方法は、
１以上のＳＰＵで動作するＳＰＵタスクマネージャ（ＳＴＭ）の制御下で、前記メインメモリに格納された１以上のタスク定義を選択されたＳＰＵのローカルメモリに読み出すステップと、
前記１以上のタスク定義に含まれる情報にもとづいて、前記タスク定義に関するコードおよび／またはデータをメインメモリから読み出し、前記選択されたＳＰＵのローカルメモリにロードするステップと、
前記選択されたＳＰＵにおいて前記コードおよび／またはデータを用いて１以上のタスクを実行するステップとを含むことを特徴とするデータプロセッシングシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
［著作権表示］
この特許書類の開示の一部には、著作権のある内容が含まれる。著作権者は、特許商標庁の特許ファイルや記録にある通りに、特許書類または特許開示のいずれかを複写して再生することには異議を唱えないが、それ以外についてはすべての著作権を留保する。
［関連出願との相互参照］
本出願は、２００５年９月２７日に出願された、本出願と譲受人が共通する特許文献１に関連し、その開示内容全体をここに援用する。
本出願はまた、２００５年９月２７日に出願された、本出願と譲受人が共通する特許文献２に関連し、その開示内容全体をここに援用する。
本出願はまた、２００５年９月２７日に出願された、本出願と譲受人が共通する特許文献３に関連し、その開示内容全体をここに援用する。
本出願はまた、２００５年９月２７日に出願された、本出願と譲受人が共通する特許文献４に関連し、その開示内容全体をここに援用する。
【特許文献１】US patent application 11/238,087 entitled "SPU TASK MANAGER FOR CELL PROCESSOR" to John P. Bates, Payton R. White, Richard Stenson, Howard Berkey, Attila Vass and Mark Cerny.
【特許文献２】US patent application 11/238,095 entitled "CELL PROCESSOR TASK AND DATA MANAGEMENT" to Richard B. Stenson and John P. Bates.
【特許文献３】US patent application 11/238,086 entitled "OPERATING CELL PROCESSORS OVER A NETWORK" to Tatsuya Iwamoto.
【特許文献４】US patent application 11/238,085 entitled "METHOD AND SYSTEM FOR PERFORMING MEMORY COPY FUNCTION ON A CELL PROCESSOR" to Antoine Labour John P. Bates and Richard B. Stenson.
【０００２】
［技術分野］
本発明は一般には並列処理に関し、特にセルプロセッサにおけるタスク管理に関する。
【背景技術】
【０００３】
電子計算における主な進歩は、同時に複数の演算を実行することができるシステムが開発されてきたことである。そのようなシステムは、並行処理の実行と称されている。最近では、ハンドヘルド・ゲームデバイスからメインフレームコンピュータに至るまで、電子デバイス上で並列処理を実行するために、セルプロセッサが開発されている。典型的なセルプロセッサはパワープロセッサユニット（ＰＰＵ；Power processor unit）と８個までのシナジスティックプロセッシングユニット（ＳＰＵ；synergistic processing units）と呼ばれる付加的なプロセッサをもつ。各ＳＰＵは典型的には、メインプロセッサとコプロセッサを含むシングルチップまたはシングルチップの一部である。すべてのＳＰＵとＰＰＵは、たとえばメモリフローコントローラ（ＭＦＣ）を通して、メインメモリにアクセスすることができる。ＳＰＵはメインプロセッサ上で走るプログラムと連結して演算を並列処理することができる。ＳＰＵは小さなローカルメモリ（典型的には２５６キロバイト）をもつ。このメモリは、コードとデータがローカルＳＰＵメモリへ／から転送されるようにソフトウェアで管理しなければならない。
【０００４】
ＳＰＵは並列処理アプリケーションにおいてたくさんの利点を有する。たとえば、ＳＰＵは独立したプロセッサであり、ＰＰＵから最低限の関与しか受けずにコードを実行することができる。各ＳＰＵはＲＡＭに対して高いダイレクトメモリアクセス（ＤＭＡ）バンド幅をもつ。ＳＰＵは典型的にはＰＰＵよりも速くメインメモリにアクセスすることができる。それに加えて、各ＳＰＵはそれ自身のローカルストアに比較的速くアクセスする。ＳＰＵはまた限定も有しており、それがＳＰＵ処理を最適化するのを難しくしている。たとえば、ＳＰＵはシンメトリック・マルチプロセッシング（ＳＭＰ）を実行することはできず、共有メモリをもたず、ハードウエアキャッシュもない。さらに、共通したプログラミングモデルはＳＰＵ上でうまく動かない。
【０００５】
典型的なＳＰＵプロセスは、メインメモリからコードおよび／またはデータを取り出し、ＳＰＵ上でデータを操作するためにコードを実行し、データをメインメモリあるいは、ある場合には別のＳＰＵに出力する。高いＳＰＵ性能を達成するには、比較的複雑な処理を行うアプリケーションにおいて上記のＳＰＵプロセスを最適化することが望ましい。たとえば、コンピュータグラフィックス処理のようなアプリケーションでは、ＳＰＵは典型的にはフレーム毎に数千回タスクを実行する。与えられたタスクはいろいろなＳＰＵコードに関係しており、データブロック数やサイズも異なる。高性能のためには、ＰＰＵソフトウエアの関与がほとんどない状態でＳＰＵソフトウエアからＳＰＵコードとデータを転送するように管理することが望ましい。ＳＰＵからコードとデータを管理するための多くの技術がある。しばしば、ＳＰＵからコードとデータを管理するための異なる技術をセルプロセッサ上で同時に実行する必要がある。ＳＰＵ駆動型のタスク管理のためのプログラミングモデルがたくさんある。残念ながら、すべてのアプリケーションにとって正しい一つのタスクシステムというものはない。
【０００６】
セルプロセッサで使用された従来のタスク管理システムはＳＰＵスレッドとして知られている。「スレッド」とは他の部分とは独立して実行できるプログラムの一部のことである。マルチスレッドをサポートするオペレーティングシステムによれば、プログラマはスレッド化された部分が並列に実行されるようにプログラムを設計することができる。ＳＰＵスレッドは、セルにおけるＳＰＵをスレッドのためのプロセッサとみなすことで動作する。コンテクストスイッチにより、ＳＰＵのローカルストレージの内容がメインメモリにスワップされることがある。２５６キロバイトのデータやコードがメインメモリからローカルストレージに差し替えられ、差し替えデータおよびコードはＳＰＵによって処理される。コンテクストスイッチは、複数の処理が単一のリソースを共有できるように、ＳＰＵまたはＰＰＵのステート（コンテクスト）を格納し、復元する計算処理である。コンテクストスイッチは、通常は計算量が多く、オペレーティングシステムの設計の大部分は、コンテクストスイッチの使用を最適化することに割かれる。
【０００７】
残念ながら、ＳＰＵスレッドとインターオペレートすることは、高性能アプリケーションにとっての選択肢ではない。ＳＰＵスレッドにもとづくアプリケーションは、大きなバンド幅要求をもち、ＰＰＵから処理される。したがってＳＰＵスレッドベースのアプリケーションは自律的ではなく、遅くなる傾向がある。ＳＰＵスレッドはＰＰＵから管理されるため、ＳＰＵコンテクストスイッチ（あるＳＰＵ上で現在実行中のプロセスを他のウエイト中のプロセスにスワップする）は時間がかかり過ぎる。ＳＰＵの管理にＰＰＵが関与するのを避けることができれば、あるアプリケーションに対してはもっとよい性能を与えることができる。
【発明の開示】
【発明が解決しようとする課題】
【０００８】
これらの問題を克服するために、ＳＰＵランタイムシステム（ＳＰＵＲＳ）と呼ばれるシステムが開発された。ＳＰＵＲＳでは、各ＳＰＵのメモリには、ＳＰＵによって扱われるタスクのスケジューリングを実行するカーネルがロードされる。残念ながら、ＳＰＵＲＳは、ＳＰＵスレッドと同様、コンテクストスイッチを使ってＳＰＵへ、あるいはＳＰＵから仕事（ワーク）をスワップする。ワークは、ＰＰＵではなくＳＰＵ上で実行されるため、ＳＰＵスレッドとは違って、処理の自律性はある。しかし、ＳＰＵＲＳはＳＰＵスレッドと同じようにコンテクストスイッチのオーバーヘッドを受ける。このように、ＳＰＵＲＳは自律性を提供するが、多くの利用形態に対してはあまり好ましいものではない。
【０００９】
ＳＰＵＲＳはＳＰＵタスクシステムの一例に過ぎない。ミドルウエアおよびアプリケーションには、多様な目的に応じて多様なタスクシステムが求められる。現在、ＳＰＵＲＳはＳＰＵスレッドのグループとして実行され、他のＳＰＵスレッドとインターオペレートすることができる。残念ながら、上述のように、ＳＰＵスレッドには好ましくないオーバーヘッドがあり、ＳＰＵタスクシステムのインターオペレーションのためにＳＰＵスレッドを用いることは、特定の高性能アプリケーションにとっての選択肢ではない。
【００１０】
セルプロセッシングでは、ミドルウエアとアプリケーションが多様なタスクシステムを用いてＳＰＵを共有することが望ましい。多くのタスククラス、たとえば、オーディオ、グラフィックス、人工知能や、布モデリング、流体モデリング、剛体運動のような物理に対して、リソースを提供することが望ましい。これを効率的に実行するために、プログラミングモデルはコードとデータの両方を管理する必要がある。ＳＰＵミドルウエアが共通のタスクシステムとインターオペレートしないようにすることが、一つの努力目標である。残念ながら、ＳＰＵスレッドとＳＰＵＲＳは同じプログラミングモデルに従っており、このモデルもあまり多くの利用ケースにとって十分な性能を提供しない。このように、アプリケーションの開発者は、コードとデータの間でＳＰＵ上の限られたメモリスペースをいかに共有するかについて、依然として答えを見つけなければならない。
【００１１】
そのため、上述の不利な点を克服するセルプロセッサ方法および装置が技術的に求められている。使いやすく、ＳＰＵの利点を強調するようなソフトウエアモデルを用いてＳＰＵタスク管理を実装することが望ましい。また、ＳＰＵ上でキャッシュされるソフトウエアコードおよび／またはデータを用いてＳＭＰを実装することができるのが望ましい。
【課題を解決するための手段】
【００１２】
本発明の実施の形態は、セルプロセッサにおけるセルプロセッサタスク管理に関する。セルプロセッサは、メインメモリ、１以上のパワープロセッサユニット（ＰＰＵ）、１以上のシナジスティックプロセッシングユニット（ＳＰＵ）をもつ。各ＳＰＵはプロセッサとローカルメモリをもつ。タスクを管理する方法は、１以上のＳＰＵによって実行される。１以上のＳＰＵで動作するＳＰＵタスクマネージャ（ＳＴＭ）は、メインメモリに格納された１以上のタスク定義を選択されたＳＰＵのローカルメモリに読み出す。タスク定義に含まれる情報にもとづいて、ＳＰＵはタスク定義に関するコードおよび／またはデータをメインメモリから読み出し、選択されたＳＰＵのローカルメモリにロードする。その後、選択されたＳＰＵはこのコードおよび／またはデータを用いて１以上のタスクを実行する。
【発明を実施するための最良の形態】
【００１３】
これから述べる詳細な説明には、例示のために特定の詳細な内容が多く含まれるが、当業者であれば、これらの詳細な内容にいろいろなバリエーションや変更を加えても、本発明の範囲を超えないことは理解できよう。したがって、以下で説明する本発明の例示的な実施の形態は、権利請求された発明に対して、一般性を失わせることなく、また、何ら限定をすることもなく、述べられたものである。
【００１４】
本発明の実施の形態は、セル・プロセッサを用いて高性能を達成することが望ましい。本発明の実施の形態によれば、ＳＰＵタスク管理が完全である、すなわち、ＳＰＵタスク管理がすべての場合に動作し、スケーラブル、すなわちＳＰＵの数に対して性能がスケールすることが好ましい。加えて、本発明の実施の形態は、ＰＰＵの使用を低く抑え、メモリ使用も少なく、ＤＭＡバンド幅の使用量も低くすることで、ＳＰＵタスク管理を効率良く実装することが望ましい。
【００１５】
図１は、セル・プロセッサ１００の概略図である。本発明の実施の形態によれば、セル・プロセッサ１００は一般にパワープロセッサユニット（ＰＰＵ）１０２といくつかのシナジスティックプロセッシングユニット（ＳＰＵ）１０４を含む。図１では、一つのＰＰＵ１０２と８個のＳＰＵ１０４が例示される。２つ以上のＰＰＵや、８より多いか少ないＳＰＵをもつセルプロセッサが本発明の実施の形態において使われてもよい。
【００１６】
ＰＰＵ１０２は、大部分の計算上の作業負荷を取り扱うＳＰＵ１０４に対してコントローラとして働く。ＰＰＵ１０２が他の６４ビットＰｏｗｅｒＰＣプロセッサと十分に類似しており、ＳＰＵ１０４がベクトル浮動小数点コードを実行するために設計されているならば、ＰＰＵ１０２を、従来のオペレーティングシステムを走らせるために用いてもよい。一例として、ＰＰＵ１０２は、３２ＫｉＢのインストラクション（命令）とＬ１データキャッシュと５１２ＫｉＢのＬ２キャッシュを含んでもよい。
【００１７】
ＰＰＵ１０２とＳＰＵ１０４は、交換インタフェースバス（ＥＩＢ）１０３上で互いにコードとデータを交換し合うことがでる。ＰＰＵ１０２とＳＰＵＳ１０４は、ＥＩＢ１０３およびメモリ・フロー・コントローラ（ＭＦＣ）（たとえば、ダイレクトメモリアクセス（ＤＭＡ）ユニットのようなもの）を介して、メインメモリ１０６に格納されたコードとデータを交換し合うこともできる。ＥＩＢ１０３は、反対方向に２本のチャネルをもつ循環バスであってもよい。ＥＩＢ１０３は、Ｌ２キャッシュ、ＭＦＣ１０８およびシステムインタフェース１０５（例えば外部通信のためのＦｌｅｘＩＯのようなもの）に接続されてもよい。
【００１８】
各ＳＰＵ１０４は、ローカルメモリー１１０をもつ。メインメモリ１０６から取得されたコードとデータはローカルメモリー１１０へロードすることができ、その結果、ＳＰＵ１０４はタスクを処理することができる。図示されているように、ＳＰＵタスクマネージャ（ＳＴＭ）１１２として参照される、小さなソフトウェア・マネージャが、各ＳＰＵ１０４のローカルメモリ１１０に存在する。好ましくは、ＳＴＭ１１２は、各ローカルメモリ１１０の利用可能な総メモリ空間のほんの小さい部分だけを占める。ＳＰＭＭ１１２の中心部分は「ＳＴＭカーネル」と称され、典型的には各ＳＰＵ上のおよそ１６ＫＢを占めている。２５６Ｋのローカルストレージの場合、これはおよそ６％のＳＰＵローカルストアを使用したことを意味する。
【００１９】
たとえば、ポリシーモジュールとワークキューは次のように関連づけられてもよい。図１の下側に示すように、メインメモリ１０６は一組のタスクキュー１１６を持つタスクセット１１４を含んでもよい。各タスクキュー１１６は一つ以上のタスクキューエレメントを含み、タスクキューエレメントはタスク定義へのポインタを含む。ＰＰＵ１０２は新しいタスクキューをタスクセット１１４に追加することができるが、それ以外はタスクセット１１４の管理にはほとんど関与することがない。タスクはＰＰＵ１０２上で動作するアプリケーションからタスクキュー１１６に追加されてもよい。Ｌｖ２ＯＳミューテックスのようなオペレーティングシステムのミューテックスをＰＰＵスレッドの競合のために利用してもよい。それに加えてＳＰＵ１０４は新しいタスクをスケジュールすることもできる。タスクがタスクキューに追加されるたびに、割り込みなしで一度実行される。ＰＰＵ１０２は典型的にはタスクが処理されている間はタスクに割り込むことはない。ＰＰＵアプリケーションは、タスクが完了したかどうかを見るためにタスクキュー１１６をポーリングしてもよい。たとえば、「チェックされた」タスクが完了すると、ＳＴＭカーネル１１２はあるビットをアトミックに設定する。このビットはＰＰＵ１０２からＡＰＩを用いてポーリングすることができる。
【００２０】
タスクキュー１１６が空であるとき、各ＳＰＵ上のＳＰＵカーネルはアトミックな予約消失イベントを待つ。ＳＰＵ１０４はアトミックミューテックス１１７に「チェックされた」タスクの完了を通知する。たとえば、アトミックミューテックスは、ロックステートのために使われるアトミックな４バイト、完了したタスクのカウントに使われる２バイト、および最大４８８タスクのステートが入る１２２バイトを含む。この１２２バイトにはタスク毎の２つのビットを含む。一つは予約のため、もう一つはステート（待ち、処理中、完了など）のためである。通知（ノティフィケーション）は控えめになされるべきである。ＳＴＭタスクは、待っているＰＰＵスレッドにＳＰＵスレッドのイベントキューを用いて随時通知することができる。しかし、この技術のレーテンシー（ＳＰＵがイベントを送ってからＰＰＵスレッドが通知を受けるまでにかかる時間）は、非常に長くなりうる。たとえば、アトミック・ノティフィケーションよりも約１００倍も長くなる。
【００２１】
タスク定義１１８は、タスクパラメータ１２０とＳＰＵタスクコードイメージ１２２があるメモリロケーションへのポインタを含む。コードイメージ１２２は必要なコードの一つ以上の実行可能でリンク可能なフォーマット（ＥＬＦ）イメージの形をとる。タスクパラメータ１２０はタスクに関する情報を含む。これには、入出力（Ｉ／Ｏ）アドレス、Ｉ／Ｏサイズ、入出力タスクデータ１２３のアドレスのようなものが含まれるが、これに限定するものではない。ＳＴＭカーネル１１２は、ＳＰＵ１０４にコンテキストデータ１２６として格納されているコードイメージ１２２とパラメータ１２０を用いて、ＳＰＵ１０４にコード１２４をロードする。その後、ＳＰＵ１０４はコード１２４を走らせて、タスクデータ１２３をロードして処理する。メインメモリ１０６には、いろいろな出力データサイズを有するＳＰＵプログラムを収容するための共有出力バッファ１１５がオプションとして含まれる。そのようなタスクが完了すると、ＰＰＵ１０２は、ＳＴＭ  ＰＰＵアプリケーションプログラミングインターフェース（ＡＰＩ）を通じてそのタスクの出力データを取り出すことができる。
【００２２】
ここで述べられた多くの特徴は、ＳＰＵカーネル１１２の適当なコンフィグレーションを通じて実装することができる。本発明の実施の形態では、ＳＴＭカーネル１１２用のＰＰＵランタイムは存在しない。一般に、ＳＴＭカーネル１１２はメインメモリ１０６の共有タスクキュー１１６からタスク定義１１８を取得する。タスクキュー１１６のサイズは使用の仕方に応じて変わる。タスクがキューに追加されるたびに、割り込みなしで一度実行される。複数のタスクキュー１１６を生成して一つ以上のタスクセット１１４にグループ分けすることができる。各タスクキュー１１６に優先度を割り当てることができる。ＳＴＭカーネルは低い優先度のキューよりも前に高い優先度のキューを処理するために選択することができる。等しい優先度のキューを処理するときは、ＳＰＵは競合を減らすために異なるキューを処理しようとする。高い優先度のキューが準備完了になると、次に利用可能なＳＰＵがそのキューの処理を開始する。
【００２３】
表１は、１つのありうるタスク定義を代表して示す。タスク定義データ構造の特定の内容は、表１の内容とは異なっていてもよい。たとえば、タスクパラメータはオプションである。さらに、タスクが同期を要求しないなら、バリアタググループ情報は必要ではない。
【００２４】
【表１】
2009510613.tif 000003
【００２５】
ＳＰＵカーネル１１６は、もっとタスクを必要とするとき、タスクキューの先頭から多くのタスク定義をＤＭＡ転送する。タスクキュー１１６は循環しており、タスクがＰＰＵ１０２またはＳＰＵ１０４から追加されると、動的に大きくなっていく。循環キューにおいて、タスクはキューの末尾に追加され、先頭から取られる。タスクは利用可能な空間を埋め尽くした後、ラップアラウンド（循環）して、タスクがキューの末尾から取り除かれたときに利用可能となるメモリ空間を占有する。タスクキューは各キューへのアクセスの同期を取るためにアトミック・ミューテックス１１７を用いてもよい。一例として、このアトミック・ミューテックスは１２８バイトのアトミック・ミューテックスであってもよい。タスクキュー１１６に対するポインタとインデックスは、このアトミックの中に格納することができる。アトミック・ミューテックス１１７は一般に、タスクキュー１１６に対するアクセスがロックされているか否かを示す１以上のビットを含む。ミューテックス１１７はまた、タスクキューの他のどのタスクが進行中であるかについての情報、および／またはそれらのタスクの位置についての情報を提供する１以上のバイトのデータを含む。ミューテックス１１７はまた、タスクキュー１１６のどのタスクが取られたかを他のＳＰＵ１０４またはＰＰＵ１０２に通知するためにインクリメントまたはデクリメントすることのできるカウンタ用に１以上のバイトをもつ。
【００２６】
たくさんの独立したタスクのもとでは、プロセッサ１００の性能は、ＳＰＵ１０４の数に対して線形にスケールする傾向がある。割り当てられたＳＰＵ１０４の数が変化しても、アプリケーションデータ管理にはどんな変更も必要ではない。ＳＰＵ１０４は、自分がやり遂げたときはいつでももっと多くのタスクを獲得することにより、自動的に負荷のバランスを取る。複数のタスクキュー１１６があるおかげで、競合によるオーバーヘッドは減らされる。
【００２７】
図２は、図１のセル・プロセッサ１００を用いて処理する方法２００を示すフローチャートである。図３は、セル・プロセッサ１００のある構成要素をブロック図で示した概略図である。セル・プロセッサ１００のオペレーションは図１および図３を参照して理解することができる。ステップ２０２で、一つ以上のＳＰＵ１０４で動作するＳＴＭカーネルはタスクセット１１４からタスクキュー１１６を選択する。タスクキューの選択は優先度にもとづいてなされてもよく、優先度の高いキューは優先度の低いキューよりも前に処理される。
【００２８】
いったんタスクキュー１１６が選択されると、ステップ２０４でＳＴＭカーネル１１２はタスクキューからタスク定義１１８を読み出す。タスク定義はタスクキューで決められた順序で取り出される。ＳＴＭは他のＳＰＵによって既に取られたタスク定義はスキップする。タスク定義１１８の情報によって、ＳＴＭは、ＳＰＵタスクパラメータ１２０に対応するメインメモリアドレスとタスクコードイメージ１２２に導かれる。ステップ２０６でＳＰＵはＳＰＵタスクコード１２４をロードする。ＳＰＵ１０４は、パラメータ１２０とコード１２４を用いてタスクデータ１２３をＳＰＵローカルストア１１０に入力データ１２６としてロードする。ステップ２０８でＳＰＵ１０４はコード１２４を用いて入力データ１２６を処理し出力データ１２８を生成する。ステップ２１０で、出力データ１２８はメインメモリ１０６のあるアドレスに格納されるか、さらなる処理をするために別のＳＰＵ１０４に転送される。
【００２９】
コード１２４は、一つ以上のＳＰＵプログラムを含んでもよい。ここでは、ＳＰＵプログラムとは、ＳＰＵが一つ以上のＳＰＵタスクを実行するために用いることができるコードを指す。本発明のある実施の形態では、ＳＰＵ１０４がデータ１２３を処理するときに使用できるように、複数のＳＰＵプログラムをキャッシュすることができる。そのようなプログラムのキャッシュは、ＤＭＡの使用を最適化するために利用することができ、ＳＰＵ１０４がコードをロードするためにメインメモリ１０６にアクセスする回数を減らすことができる。ＳＰＵプログラムはＰＰＵのＡＰＩを通してメインメモリに動的にロードしてもよい。ＳＰＵプログラムのＥＬＦデータは（ＰＰＵシンボルとしての）メモリ１０６からロードしてもよく、ファイルからロードしてもよい。ＳＰＵタスク定義１１８はメインメモリにロードされたＳＰＵプログラムを参照して生成することができる。ＳＰＵプログラムはアプリケーションの開始時にメインメモリに一度だけロードされる。その後、プログラムはタスクによって必要とされたときに、ＳＰＵローカルストア１１０にＤＭＡ転送することができる。
【００３０】
本発明の実施の形態では、ここではそれぞれタイプ１、タイプ２と称する二つのタイプの一つとしてＳＰＵプログラムを特徴づけることができる。タイプ１のＳＰＵプログラムは位置独立コード（ＰＩＣ）、すなわちメモリ内の異なる位置で実行することができるコードを利用する。ＰＩＣは共有メモリで一般に用いられており、そのため、同じライブラリコードを（たとえば、仮想メモリシステムを用いて）各アプリケーションのある場所にマップすることができ、アプリケーションや他の共有ライブラリと重なることがない。ローカルストアの静的な使用の仕方、すなわちタイプ１コードがランタイムの使用のためにメモリを割り当てることはないことによってプログラムをさらに特徴づけてもよい。図４Ａに示すように、タイプ１のプログラムは、ＳＴＭカーネルによってＳＰＵタイプ１のローカルストア３１０内で管理される。図４Ｂに示すように、複数のタイプ１プログラム３２４を同時にＳＰＵローカルストア３１０にロードすることもできる。タイプ１プログラムを一定のスタックリミットをもつスタック３１１によって特徴づけてもよい。タイプ１プログラムコードとコンテキストデータは、ＳＴＭカーネル３１２またはスタック３１１によって占有されていないＬＳ３１０の残りの空間に存在する。図４Ｃに示すように、プログラム３２４はプログラムとタスク間で共有すべきデータ３２６をキャッシュすることができる。
【００３１】
タイプ１プログラムは高性能のプログラムであるが、多くの制約をもつ傾向がある。キャッシュすることができるタイプ１プログラム３２４の一例は、ＭＥＭ  ＣＯＰＹプログラムである。このプログラムは、メモリ転送はＰＰＵ１０２が行うよりもＳＰＵ１０４を用いてＤＭＡによって行った方が一層速くできるという事実を利用する。ＭＥＭ  ＣＯＰＹは、利用可能なＳＰＵを用いてメインメモリ１０６のある場所から別の場所へデータを転送することにより、この利点を利用する。このようなＳＰＵにもとづくメインメモリ管理は、メインメモリからＳＰＵまたはどこか別の場所にＤＭＡ転送する前にデータのアラインメントをする必要がある場合に特に有利である。ＭＥＭ  ＣＯＰＹの例は、本出願と譲受人が共通する米国特許出願１１／２３８，０８５号、"METHOD AND SYSTEM FOR PERFORMING MEMORY COPY FUNCTION ON A CELL PROCESSOR", Antoine Labour John P. Bates and Richard B. Stensonに詳しく記載されている。この出願は本願と同日に出願されており、その開示全体は参照によりここに取り込まれる。
【００３２】
タイプ２のプログラムは、非位置独立コード（ｎｏｎ−ＰＩＣ）を用い、ローカルストアの空間をＳＰＵラインタイムで動的に割り当ててもよいという事実によって特徴づけられる。典型的には、ただ一つのタイプ２プログラムが一度に一つのＳＰＵにロードされる。もっともこの特徴に対する例外も本発明の実施の形態の範囲内にある。図４Ｄに示すように、タイプ２プログラムに対して、ローカルストア３１０はランタイムで当該プログラムによって動的に割り当てられるメモリ領域を含む。図４Ｅに示すように、この領域にはタイプ２のＳＰＵプログラムコード３２５とコンテキストデータ３２６が含まれる。さらに、図４Ｆに示すようにローカルストア３１０の動的に割り当てられた領域にはｍａｌｌｏｃデータ３２７も含まれることがある。ｍａｌｌｏｃ関数はＣのようなプログラミング言語においてメモリ空間を動的に割り当てるために使われる。ｍａｌｌｏｃ関数はこのメモリブロックにポインタを介してアクセスする。メモリがもはや使われないとき、ポインタは「解放（フリー）」に渡され、メモリはシステムによって再利用できるようになる。タイプ２プログラムは、使い残りのローカルストアの空間がグローバル、スタック、および／またはｍａｌｌｏｃの間でどのように割り当てられるかを決定する。さらに、タイプ１プログラムとは違って、タイプ２プログラムに対するスタック３１１のサイズは可変である。タイプ２プログラムは、ＳＰＵにプログラムコードをロードし、その後そのプログラムコードに合致するタスクを選択することが望ましい状況に特に適している。ＳＴＭカーネル３１２は、タスクキューをずっと先まで見ても合致するものが見つからないなら、別のプログラムをロードすることができる。
【００３３】
図４Ｇは、ＳＰＵのローカルストレージ３２０のメモリーマップを示し、ここでは、ＳＴＭカーネル３１２がＳＰＭＭ３１３のもとでポリシーとして実装される。ＳＴＭカーネル３１２は一つ以上のタスクに対するＳＰＵプログラム３２４とデータ３２６を管理する。ＳＴＭカーネルをＳＰＭＭのもとでポリシーとして走らせることにより、ＳＰＵＲＳ、ＳＰＵスレッド、開発者が設計したカスタムポリシーのような他のポリシーを実装できるという柔軟性をもたせることができる。ＳＰＭＭは、本出願と譲受人が共通する米国特許出願１１／２３８，０７７号、"CELL PROCESSOR METHODS AND APPARATUS", John P. Bates, Payton R. White and Attila Vassに詳しく記載されている。この出願は本願と同日に出願されており、その開示全体は参照によりここに取り込まれる。
【００３４】
タイプ１とタイプ２のＳＰＵプログラムには共通の特徴がある。具体的には、タスク定義１１８のサイズが指定されなければならない。さらに、Ｉ／ＯのＤＭＡデータに対して要求される最大ローカルストア空間を指定しなければならない。これによりカーネル１１２はタスクに対するローカルストアのコンテキストデータを管理することができるようになる。ＳＰＵタスクは典型的にはタスク定義１１８に対するコンテキストバッファとＩ／Ｏデータを共有する。タイプ１とタイプ２のプログラムは、たとえばＣやＣ＋＋のような任意の適切な言語で書いてもよい。プログラムはリンクされてもよく、ＳＰＵカーネルに存在するＳＰＵプログラム内の未定義のシンボルはランタイムでカーネルシンボルにリンクすることができる。
【００３５】
ＳＰＵプログラムはここで、ｐｒｅｆｅｔｃｈ、ｓｔａｒｔ、ｓｐｕｍａｉｎ、ｆｉｎｉｓｈとして参照する４つのカスタマイズ可能なコールバックをもつことができる。ｐｒｅｆｅｔｃｈコールバックはｐｒｅｆｅｔｃｈ（ＳｐｕＴａｓｋＣｏｎｔｅｘｔ＊）というシンタックスをもつ。ここで、括弧内の量はタスクに関する情報へのポインタであり、この情報にはタスク定義のメインメモリアドレスとＩ／Ｏデータ転送に対するＤＭＡタグが含まれる。ＳｐｕＴａｓｋＣｏｎｔｅｘｔは、現在のタスクに関する情報へのローカルポインタである。このデータは、ＳＰＵプログラムがタスクを実行するために必要である。ＳＴＭカーネル１１２はこのデータを準備し、それをＳＰＵプログラムの各コールバックに渡す。ＳｐｕＴａｓｋＣｏｎｔｅｘｔは、このタスク定義のメインメモリ１０６におけるアドレスを含む。タスクはこのアドレスを用いてタスク定義１１８をＤＭＡ転送することができる。ＳｐｕＴａｓｋＣｏｎｔｅｘｔはまた、ＳＰＵプログラムがタスクの４つのステージのそれぞれにおいて用いることができる一時的なローカルストアバッファを含んでもよい。このコールバックはタスクキューからタスク定義１１８のＤＭＡ転送を開始するようにＳＰＵ１０４に命じる。ｓｔａｒｔコールバックは、ｓｔａｒｔ（ＳｐｕＴａｓｋＣｏｎｔｅｘｔ＊）というシンタックスをもつ。このコールバックによって、ＳＰＵ１０４はタスク定義のＤＭＡの完了を待ち、タスク定義１１８によって決められた通りにコードおよび／またはデータの入力ＤＭＡを開始するようになる。ｓｐｕｍａｉｎコールバックはｓｐｕｍａｉｎ（ＳｐｕＴａｓｋＣｏｎｔｅｘｔ＊）というシンタックスをもつ。ここで、括弧内の量は前述のコールバックと同じデータである。このコールバックによって、ＳＰＵ１０４は入力ＤＭＡが完了するのを待ち、入力データを処理し、対応する出力データのＤＭＡを開始するようになる。ｆｉｎｉｓｈコールバックはｆｉｎｉｓｈ（ＳｐｕＴａｓｋＣｏｎｔｅｘｔ＊）というシンタックスをもつ。ここでも括弧内の量は前述のコールバックと同じデータである。
【００３６】
本発明の実施の形態によれば、ここではマルチバッファリングとして参照される処理を通じてコードとデータを効率的に管理することが可能である。マルチバッファリングはＳＰＵのある特徴を利用する。特に、ＳＰＵは一度に複数のＤＭＡオペレーションを実行することができ、ＳＰＵプログラムを実行中もＤＭＡオペレーションを実行可能である。マルチバッファリングでは、ＳＴＭカーネルはタスクコールバックをインターリーブするため、ＤＭＡオペレーションはメイン実行中も進行する。図５はマルチバッファリングの例を示す。この例では、一つのＳＰＵが５つのタスクを実行する。各タスクに対して、ＳＰＵは、タスク定義をプリフェッチし、必要なデータおよび／またはコードのＤＭＡを開始（スタート）し、メインＳＰＵコードを実行して出力を生成し、そして、ＤＭＡによってその出力を転送することで終了（フィニッシュ）しなければならない。図５の上側のチャートは、並列に、すなわち時間的にある程度重複しながら起こるＳＰＵのオペレーションを図示する。中央のチャートはコールバックが開始される順序を示し、下側のチャートはタスク実行によって異なるタスクが時間的に重複することを示している。中央のチャートからわかるように、たとえば最初の二つのタスクに対するプリフェッチコマンド（ｐｒｅｆｅｔｃｈ１，ｐｒｅｆｅｔｃｈ２）が最初に呼び出され、その後、第１タスクに対するスタートコマンド（ｓｔａｒｔ１）が呼び出され、ｐｒｅｆｅｔｃｈ３，ｓｔａｒｔ２，ｍａｉｎ１と続く。上下のチャートを見ればわかるように、キューの中央付近で最大のオーバーラップが生じており、それは、異なるタスクのｐｒｅｆｅｔｃｈ，ｓｔａｒｔ，ｍａｉｎおよびｆｉｎｉｓｈのコールバックの部分が並列に走っているときである。
【００３７】
複数のタスクの異なる部分が同じＳＰＵ上で並列に走ることができる場合、タスクの同期を取れることが多くの場合、重要になる。そのようなタスク同期は、一つのタスクセットを、次のタスクセットが始まる前に完了しなければならない場合に有益である。たとえば、第１のタスクセットからの出力データが次のタスクセットに対する入力データとして用いられる場合などである。そのような同期を容易にするために、バリアコマンドをタスクキューに挿入することで、前者のタスクが完了してはじめて次のタスクが始まることを保証することができる。
【００３８】
図６Ａはバリアコマンドを用いてタスク同期を行った例を図示する。この場合、第１タスクセット６０１は、第２タスクセット６０３に対する入力６０４として用いられるべき出力６０２を生成する。出力６０２はデータ６０６としてたとえばメインメモリに格納される。バリアコマンド６０８が二つのタスクセット６０１、６０３の間に設置される。バリアコマンド６０８は第１タスクセット６０１または第２タスクセット６０３のいずれかにおけるタスクであってもよい。バリアコマンド６０８は、第１タスクセット６０１からのタスクが完了する前に、ＳＰＵＳが第２タスクセット６０３におけるタスクについて作業することを防ぐ。
【００３９】
複数のタスクセットが並列に実行される可能性がある。そのような場合、互いに同期されなけれならないタスクとそうでないタスクをバリアコマンドが区別することが重要である。この区別を容易にするために、同期が必要なタスクセットを特定するタグマスクによってバリアコマンドを特徴づけてもよい。バリアコマンドはタグマスクに含まれるタスクだけを同期させる。たとえば、バリアマスク０ｘＦＦＦＦＦＦＦはすべてのタスクに影響するが、バリアマスク１＜＜２（０ｘ４）はタグの値が２であるタスクだけに影響する。図６Ｂは、複数のタスクセットを選択的に同期づけるためにバリアタグマスクを使用する例を図示する。図６Ａと同様、第１タスクセット６０１は、第２タスクセット６０３に対する入力として用いられるデータ６０６を生成する。しかし、他のタスクセット６１１、６１２は第１タスクセット６０１と並列に処理されている。この例では、第１タスクセット６０１の出力はタスクセット６１２に対する入力と同期する必要はない。そのため、第１および第２タスクセット６０１、６０２間のバリアコマンド６０８は、第１タスクセット６０１に限定して影響するタグマスクをもつ。第１タスクセット６０１が完了するまでは、ＳＰＵは第２タスクセット６０２のタスクについて作業することはできない。しかし、ＳＰＵはバリアコマンド６０８のタグマスクで指定されていない他のタスクセットについては作業することができる。
【００４０】
実施の形態においてコードおよび／またはデータのアフィニティ（親和性）を利用すれば、高性能処理を達成することができる。ここでいう「コードアフィニティ」とは、ＳＰＵが特定のタスクに関するプログラムコードを自分のローカルストアに既にロードした状況のことである。ＳＰＵが特定のタスクとコードアフィニティをもつ場合、ＳＰＵはそのタスクに対して必要なデータをＤＭＡ転送しさえすればよい。同様に、「データアフィニティ」とは、ＳＰＵが特定のタスクに関するデータを自分のローカルストアに既にロードした状況をいう。ＳＰＵが特定のタスクとデータアフィニティをもつ場合、ＳＰＵは必要なコードをＤＭＡ転送しさえすればよい。ＳＰＵカーネルが自分の現在のＳＰＵコードと合致するタスクを選ぶなら、タスクの処理はより効率良くなされる。これはコード切り替えの発生を減らす。ＳＰＵのローカルストアにいくつかのタイプ１のプログラムをキャッシュし、必要に応じてアクセスすることも可能であることに注意されたい。そのような場合は、コードアフィニティはあまり重要ではない。
【００４１】
図７Ａはコードアフィニティの利用を図示する。あるコード７０１があるＳＰＵのローカルストア７０２にロードされる。メインメモリ７０４は複数のタスク定義をもつタスクキュー７０６を含む。ＳＰＵはタスクキュー７０６のある部分７０７をローカルストア７０２にロードする。タスクキュー７０６は、ＳＰＵの現在のコード７０１を要求するタスク７０８に対する定義と、ＳＰＵの現在のコード７０１を要求しない他のタスク７１０に対する定義とを含む（これらは図７で異なる網掛けで示した）。ＳＴＭカーネル（図示しない）は現在のプログラム７０１とコードアフィニティ（親和性）をもつタスク７０８を選択し、そうでないタスク７１０はスキップする。カーネルは、スキップされたタスク７１０をメインメモリ７０６にＤＭＡ転送して戻すようにＳＰＵに命令する。その結果、タスクキュー７０６は連続性を維持する。その後、ＳＰＵはコード７０１を変更することなく、選択されたタスク７０８を処理することができる。この処理の間、タスクキューのアトミックミューテックスはロックされていることに注意する。
【００４２】
どんなタスクも現在のコードに合致しないときもある。そのような場合、ＳＰＵはプログラムコードを切り替えることができる。これは図７Ｂに図示されている。タスクキュー７０６の当該部分７０５は、現在のコード７０１とコードアフィニティ（親和性）を有していないタスク７１０を含む。カーネル７１２は古いコード７０１を解放し、新しいコード７０３用の空間をローカルストア７０２内に割り当てる。カーネル７１２はメインメモリ７０４から新しいコード７０３のＥＬＦイメージをＤＭＡ転送する。
【００４３】
本発明の実施の形態では、あるＳＰＵ１０４がタスクを処理し終えたとき、与えられたタスクが完了したことをＰＰＵ１０２または他のＳＰＵ１０４に通知することがしばしば望ましい。このタスク完了通知を実行するためのいくつかの異なる方法がある。たとえば、任意のタスクまたはバリアにＩＤを割り当て、後からＰＰＵ１０２が完了したかどうかをポーリングすることができるようにする。タスクＩＤをもつバリアが、タスクグループがいつ完了するかを判定する。ＳＰＵタスクが完了時にＰＰＵ割り込みを送るように構成してもよい。
【００４４】
ＳＴＭカーネルに関連するオーバーヘッドはタスク毎に約６５０ＳＰＵサイクルである。これには、共有タスクキュー１１６からタスク定義１１８を取り出すときの平均的なコストが含まれる。いったん定義が取り出されると、オーバーヘッドは典型的には最小化される。もっとも、アプリケーションが多くのバリアを使うならオーバーヘッドは増えることがある。
【００４５】
コード切り替えのコストは、切り替えられるコードのサイズに依存する。たとえば、２００ＫＢコードの切り替えには約４８０００サイクルを要し、１００ＫＢコードの切り替えには約２７０００サイクルを要し、５０ＫＢコードの切り替えには約１７０００サイクルを要し、１ＫＢコードの切り替えには約２４００サイクルを要する。
【００４６】
そのようなコード切り替えによるオーバーヘッドはまた、部分的にはタスクキューの構成とタスクキューに割り当たられたＳＰＵの数に依存する。一般にキューにあるワーストケースのタスクは互い違いのコードを用いる。一般に、ワーストケースのシナリオは、異なるコードを要求するタスクがタスクキューにおいて入れ替わることである。もし一つだけのＳＰＵがタスクキューに割り当てられるなら、オーバーヘッドは、２００ＫＢのコードの場合はタスク毎に約１８４０サイクル、１００ＫＢのコードの場合はタスク毎に約１５２０サイクル、５０ＫＢのコードの場合はタスク毎に約１３６０サイクル、１ＫＢのコードの場合はタスク毎に約１２００サイクルである。もし二つのＳＰＵが同じタスクキューに割り当てられるなら、コード切り替えのオーバーヘッドは、２００ＫＢ、１００ＫＢ、５０ＫＢ、１ＫＢのコードに対してタスク毎に約８２０サイクルである。与えられたタスクキューに割り当てられるＳＰＵの数が、そのタスクキューにおける異なるコードの数に等しい場合に、最適な性能が得られるようである。
【００４７】
図９Ａ〜図９Ｃは、ＳＴＭの使い方の例を示すＣコードのリストである。図９Ａ〜９Ｃに示した例はＣコードで書かれているが、当業者であれば、アセンブリ言語を含め、どんなプログラミング言語でも使用できることが理解されよう。具体的には、図９Ａのコードリストは初期化の例である。このコードにおいて、ＰＰＵはＳＴＭのインスタンスを初期化する。ＳＴＭカーネルが開始され、ＰＰＵプロセスはＳＰＵプログラムイメージを追加する。図９Ｂはランタイムの（フレームベースの）グラフィックス処理の例である。この例では、新しいフレームが開始される。ＰＰＵはＳＰＵタスクをキューおよびＩＤをもつバリアに追加する。ＰＰＵは、以前のフレームを描画するなど他の作業を行い、バリアで保護されたタスクが完了するまで出力データの処理をブロックする。その後、別のフレームに対して処理が繰り返される。
【００４８】
図９ＣはＳＰＵ上のＳＴＭの使い方の例を示す。ＳＰＵプログラムコードは、ｐｒｅｆｅｔｃｈ（…）、ｓｔａｒｔ（…）、ｓｐｕｍａｉｎ（…）およびｆｉｎｉｓｈ（…）といった典型的なシーケンスが続く。上述のように、ｐｒｅｆｅｔｃｈ（…）コマンドはタスク定義のＤＭＡを開始する。ｓｔａｒｔコマンドによって、ＳＰＵはタスク定義のＤＭＡの完了を待ち、タスク定義によって決められたように入力ＤＭＡを開始するようになる。ｓｐｕｍａｉｎ（…）コマンドによって、ＳＰＵは入力ＤＭＡが完了するのを待ち、入力データを処理し、出力のＤＭＡを開始する。ｆｉｎｉｓｈ（…）コマンドはＳＰＵに出力ＤＭＡを待つように命じる。
【００４９】
本発明の実施の形態の利点は、図１０に示すように、比較できるほどのタスクキューをＳＰＵＲＳにもとづいて扱った場合とＳＴＭにもとづいて扱った場合とで、タスク競合のオーバーヘッドの比較をすればわかる。この例では、ＳＰＵＲＳにもとづくシステムは４つのタスクをもつタスクキューを操作した。ＳＰＵＲＳにもとづくシステムはコード１００２を用いてこのタスクキューを操作した。コードからわかるように、タスク切り替えには、イールド（yield）コールすなわち他のタスクが動作するチャンスを与えるオペレーションが必要である。グラフ１００４は、イールドコール毎のＳＰＵＲＳサイクルの平均数という観点でＳＰＵＲＳにもとづくシステムの性能を示す。システムに関与するＳＰＵの数が４から６に増えるにつれて、イールド毎のＳＰＵサイクルの平均数はほぼ４倍になっている。
【００５０】
比較のため、ＳＴＭにもとづくシステムは、ＳＴＭにもとづくコード１００６を用いて４つのＳＴＭ  ＳＰＵプログラムを含むタスクキューを操作した。タスクキューは２つの異なるシナリオにしたがって構成された。ワーストケース（最悪の場合）のキュー１００８では、４つのプログラムが交互に動作し、その結果、どんな二つの連続するタスクも同じコードを用いなかった。ベストケース（最良の場合）のキュー１０１０では、同じプログラムを要求するタスクはいつも一緒にグループ分けされた。グラフ１００４は、ワーストケースのキュー１００８の場合でさえ、ＳＴＭにもとづくシステムは、ＳＰＵＲＳにもとづくシステムが要求するイールドコール毎のサイクル数の１／３以下のサイクル数しか必要としない。ベストケースのキュー１０１０の場合であれば、ＳＴＭにもとづくシステムは、１０分の１以下のイールド毎のサイクル数しか必要としない。さらに、ベストケースとワーストケースのキューの両方について、イールドコール毎のサイクル数は比較的一定である。
【００５１】
上述のように動作する図１に示したタイプの並列処理ユニットは、図１１に示したより大きなプロセッシングシステム１１００の一部として実装されてもよい。システム１１００は、セルプロセッサモジュール１１０１とメモリ１１０２（たとえば、ＲＡＭ、ＤＲＡＭ、ＲＯＭのようなもの）を含む。さらに、プロセッシングシステム１１００は複数のセルプロセッサモジュール１１０１を有してもよい。セルプロセッサモジュール１１０１は一般に一つ以上のプロセッサＰＰＵと一つ以上のＳＰＵ（ＳＰＵ１、ＳＰＵ２、…、ＳＰＵＮ）を有する。ＳＰＵは上述のようにＳＰＭＭの制御下で動作するように構成されてもよい。プロセッサモジュール１１０１はメモリフローコントローラ（ＭＦＣ）を有してもよい。セルプロセッサモジュール１１０１は、たとえば図１で示したタイプのセルプロセッサであってもよい。メモリ１１０２は上述のように構成されたデータとコードを含む。具体的には、メモリには、上述の一つ以上のタスクセット１１０４、タスクキュー１１０６、およびコードとデータ１１０８が含まれる。
【００５２】
システム１１００には、周知の支援機能１１１０として、たとえば、入出力（Ｉ／Ｏ）エレメント１１１１、電源（Ｐ／Ｓ）１１１２、クロック（ＣＬＫ）１１１３およびキャッシュ１１１４が含まれる。システム１１００はオプションとして、プログラムおよび／またはデータを格納するためのディスクドライブ、ＣＤ−ＲＯＭドライブ、テープドライブなどのマスストレージデバイス１１１５が含まれる。コントローラはオプションとして、コントローラ１１００とユーザ間の相互作用を容易にするためのディスプレイユニット１１１６やユーザインタフェースユニット１１１８を含んでもよい。ディスプレイユニット１１１６は、テキスト、数字、グラフィカルシンボルまたはイメージを表示するＣＲＴ（cathode ray tube）やフラットパネルスクリーンの形態を取ってもよい。ユーザインタフェース１１１８はキーボード、マウス、ジョイスティック、ライトペンその他のデバイスを含んでもよい。セルプロセッサモジュール１１０１、メモリ１１０２、およびシステム１１００の他の構成要素は、図１１に示すシステムバス１１２０を介して、信号（たとえばコードインストラクションやデータ）を互いにやりとりしてもよい。
【００５３】
ここでは、Ｉ／Ｏという用語は、システム１１００や周辺デバイスへ／からデータを転送する任意のプログラム、オペレーションあるいはデバイスのことをいう。転送とは、一つのデバイスからの出力や別のデバイスへの入力のことである。周辺デバイスには、キーボードやマウスのような入力のみのデバイス、プリンタのような出力のみのデバイス、書き込み可能ＣＤ−ＲＯＭのような入力デバイスと出力デバイスのどちらにもなるデバイスが含まれる。「周辺デバイス」という用語は、マウス、キーボード、プリンタ、モニタ、外部Ｚｉｐドライブ、スキャナなどの外部デバイスだけでなく、ＣＤ−ＲＯＭドライブ、ＣＤ−Ｒドライブ、内部モデムのような内部デバイスや、フラッシュメモリリーダ／ライタ、ハードドライブのような他の周辺機器を含む。
【００５４】
プロセッサモジュール１１０１は、メモリ１１０２に格納され、読み出され、プロセッサモジュール１１０１によって実行されるメインプログラム１１０３のデータとプログラムコードインストラクションに応じて、タスクキュー１１０６のタスクの性能を管理してもよい。プログラム４０３のコード部分は、アセンブリ、Ｃ＋＋、ＪＡＶＡ（登録商標）あるいはその他の数多くの言語のような、数ある異なるプログラミング言語の任意の一つに適合するものであってもよい。プロセッサモジュール１１０１は汎用コンピュータを形成し、プログラムコード１１０３のようなプログラムを実行するときは、特定用途のコンピュータになる。プログラムコード１１０３はここではソフトウエアで実装され、汎用コンピュータ上で実行されるものとして記述したが、当業者であれば、タスク管理の方法は、特定用途向け集積回路（ＡＳＩＣ）や他のハードウエア回路のようなハードウエアを用いて実装してもよいことは理解されよう。このように、本発明の実施の形態は、全体あるいは一部が、ソフトウエア、ハードウエア、あるいはそれらの組み合わせで実装されてもよいことが理解されよう。ある実施の形態では、プログラムコード１１０３は、図２の方法２００および／または図９Ａ〜９Ｃのコードリストに共通する特徴をもつ方法を実行する、プロセッサ読み込み可能なインストラクションセットを含んでもよい。
【００５５】
本発明の実施の形態は、低いオーバーヘッドのコンテキストスイッチを提供し、並列のＤＭＡとタスク実行を可能にし、コードアフィニティを用いて現在のＳＰＵコードに合った新しいタスクを選択すし、ＤＭＡの使用を減らす。先行技術に対する本発明の実施の形態のこれらの利点は、表２に要約される。
【００５６】
【表２】
2009510613.tif 000004
【００５７】
本発明の実施の形態は開発者に高性能で直観的なＳＰＵプログラミングモデルを提供する。このプログラムモデルのおかげで、たくさんの異なるタスクが、ＳＰＵＲＳやＳＰＵスレッドほどにはコンテキストスイッチによるオーバーヘッドがなく、効率良く実行される。本発明の実施の形態は、アプリケーションコードを変更することなく、可変数のＳＰＵ上で動作可能なＳＰＵタスク管理方法とシステムを提供する。本発明の実施の形態は、多くの短いタスクと多くの小さなＳＰＵプログラムが必要であり、プログラムとタスクの間で共有されるデータが存在する状況において特に有益である。ＳＰＵコードキャッシングは性能を最適化するためにも有益である。本発明の実施の形態によるＳＰＵタスク管理が有益である状況の例として、オーディオの符号化または復号がある。これには多くの異なるフィルタコードが必要であり、フィルタコードはＳＰＵへ／ＳＰＵから動的にスワップされなければならない。各フィルタコードはＲＡＭからの一つ以上のデータブロック上で作業する。これらをオーバーレイを用いて静的に定義することはできない場合がある。そのような場合、タスクのグループはツリーを形成する。ツリーの下の方のタスクからの出力は、ここで述べたように、後続のタスクに対する入力になりうる。
【００５８】
本発明の好ましい実施の形態を完全な形で説明してきたが、いろいろな代替物、変形、等価物を用いることができる。したがって、本発明の範囲は、上記の説明を参照して決められるものではなく、請求項により決められるべきであり、均等物の全範囲も含まれる。ここで述べた特徴はいずれも、好ましいかどうかを問わず、他の特徴と組み合わせてもよい。請求項において、明示的に断らない限り、各項目は１またはそれ以上の数量である。請求項において「〜のための手段」のような語句を用いて明示的に記載する場合を除いて、請求項がミーンズ・プラス・ファンクションの限定を含むものと解してはならない。
【図面の簡単な説明】
【００５９】
【図１】本発明の実施の形態に係るセルプロセッサの概略図である。
【図２】本発明の実施の形態に係るセルプロセッサのオペレーションを例示するフローチャートである。
【図３】本発明の実施の形態に係るセルプロセッサのオペレーションを例示する概略図である。
【図４Ａ】本発明の実施の形態に係るＳＰＵメモリ構成を示すブロック図である。
【図４Ｂ】本発明の実施の形態に係るＳＰＵメモリ構成を示すブロック図である。
【図４Ｃ】本発明の実施の形態に係るＳＰＵメモリ構成を示すブロック図である。
【図４Ｄ】本発明の実施の形態に係るＳＰＵメモリ構成を示すブロック図である。
【図４Ｅ】本発明の実施の形態に係るＳＰＵメモリ構成を示すブロック図である。
【図４Ｆ】本発明の実施の形態に係るＳＰＵメモリ構成を示すブロック図である。
【図４Ｇ】本発明の実施の形態に係るＳＰＵメモリ構成を示すブロック図である。
【図５】本発明の実施の形態に係るセルプロセッサＳＰＵのマルチバッファリングオペレーションを例示するブロック図である。
【図６Ａ】本発明の実施の形態に係るバリアコマンドを用いたタスク同期を例示する概略図である。
【図６Ｂ】本発明の実施の形態に係るタググループバリアの使用を例示する概略図である。
【図７Ａ】本発明の実施の形態に係るコードアフィニティを用いたＳＰＵタスク管理を例示する概略図である。
【図７Ｂ】本発明の実施の形態に係るコード切り替えを例示する概略図である。
【図９Ａ】本発明の実施の形態を実行するセルプロセッサコードのリストである。
【図９Ｂ】本発明の実施の形態を実行するセルプロセッサコードのリストである。
【図９Ｃ】本発明の実施の形態を実行するセルプロセッサコードのリストである。
【図１０】本発明の実施の形態の利点を例示するＳＰＵ性能のグラフである。
【図１１】本発明の実施の形態に係るデータ処理システムのブロック図である。
【図１】
2009510613.tif 000005
【図２】
2009510613.tif 000006
【図３】
2009510613.tif 000007
【図４Ａ】
2009510613.tif 000008
【図４Ｂ】
2009510613.tif 000009
【図４Ｃ】
2009510613.tif 000010
【図４Ｄ】
2009510613.tif 000011
【図４Ｅ】
2009510613.tif 000012
【図４Ｆ】
2009510613.tif 000013
【図４Ｇ】
2009510613.tif 000014
【図５】
2009510613.tif 000015
【図６Ａ】
2009510613.tif 000016
【図６Ｂ】
2009510613.tif 000017
【図７Ａ】
2009510613.tif 000018
【図７Ｂ】
2009510613.tif 000019
【図９Ａ】
2009510613.tif 000020
【図９Ｂ】
2009510613.tif 000021
【図９Ｃ】
2009510613.tif 000022
【図１０】
2009510613.tif 000023
【図１１】
2009510613.tif 000024
【国際調査報告】
2009510613.tif 000025
2009510613.tif 000026
2009510613.tif 000027