JP4183712B2 - マルチプロセッサシステムにおいてプロセッサタスクを移動するデータ処理方法、システムおよび装置 - Google Patents

Description

本発明は、ネットワークを介して分散されたマルチプロセッサシステムにおけるプロセッサタスクの管理方法および装置に関し、より詳細には、実質的に自己管理的に（self-governing）マルチプロセッサシステムのサブ処理ユニット間でネットワークを介してプロセッサタスクをスケジューリングして実行する方法および装置に関する。

本出願は、２００４年２月２０日に出願された米国一部継続特許出願第１０／７８３，２４６号および第１０／７８３，２３８号に関連し、２００５年２月４日に出願された米国仮出願第６０／６５０，１５３号に関連する。

リアルタイムでマルチメディアのアプリケーションは、ますます重要になっている。これらのアプリケーションは、一秒当たり何千メガビットのデータといった極めて速い処理速度を必要とする。単一の処理ユニットでも高速の処理速度を実現できるが、一般にマルチプロセッサアーキテクチャの処理速度と一致することはできない。実際、マルチプロセッサシステムにおいては、複数のサブプロセッサが並行に（または、少なくとも協調して）動作して所望の処理結果を得ることができる。

また、マルチプロセッサアーキテクチャは有用であるが、スケーラビリティは限定的である。より大きな効率は、ネットワークを介して複数のマルチプロセッサシステムをグループ化することによって実現することができ、各マルチプロセッサシステムが単独で動作するときの速度を超える速度で分散処理が実行される。

マルチプロセッサ技術を使用することができるコンピュータおよびコンピューティングデバイスのタイプは、広範囲に及ぶ。コンピューティングデバイスには、パーソナルコンピュータ（ＰＣ）やサーバの他、携帯電話、モバイルコンピュータ、個人携帯情報機器（ＰＤＡ）、セットトップボックス、デジタルテレビのほか多数が含まれる。

リアルタイムでマルチメディアのソフトウェアアプリケーションは、処理命令や処理データなどの処理コードから構成される。処理命令および／または処理データの少なくとも一部の集合を、プロセッサタスクと呼ぶこともできる。あるプロセッサタスク内のプログラム文を順番に実行することもできるし、別のプロセッサタスクをマルチプロセッサシステム内の異なるプロセッサで並列にて実行することもできるし、あるいは、ネットワーク上の異なるマルチプロセッサシステム間に分散させることもできる。このように、ソフトウェアアプリケーションは、マルチプロセッサシステムによって実行されるプロセッサタスクを含むと考えることができる。

マルチプロセッサシステムの設計懸念は、システムのいずれのサブ処理ユニットでいずれのプロセッサタスクを実行させるかを管理する方法であり、また、ネットワーク上のマルチプロセッサシステム間でのプロセッサタスクの分散を管理する方法である。マルチプロセッサシステムのなかには、いずれのサブ処理ユニットのプロセッサタスクが実行されるかを、プロセッサタスクが指定するものがある。この方法の欠点は、サブ処理ユニットの間でのプロセッサタスクの配分をプログラマが最適化することができないという点である。例えば、一つまたは複数のプロセッサタスクが、同時に同一のサブ処理ユニットを指定することがあり得る。これは、指定されたサブ処理ユニットが利用可能になるまで、プロセッサタスクの一部が保留されることを意味し、そのためプロセッサタスクの実行が遅延される。残念なことに、これはプロセッサタスクの実行について予測不可能なレイテンシを引き起こす。

他のシステムでは、管理要素がサブ処理ユニットと通信し、ユニット間のプロセッサタスクをスケジュールすることを検討する。したがって、このような通信を容易にするように通信プロトコルが実施されていなければならない。残念なことに、通信プロトコルは、管理要素とサブ処理ユニットの間のメッセージ遅延を引き起こすことが多い。実際、この種のプロトコルは、メモリマッピングされたレジスタを使用して、メモリマッピングされたＩ／Ｏ空間の使用が必要となり、これは一般的に低速である。さらに、システムのプロセッサ自身であってもよい管理要素が多数の分割領域を使用し、これは変更にかなりの時間（例えば、７００マイクロ秒）を必要としうる。これらの特徴もまた、プロセッサタスクの実行を遅延させて予測不可能なレイテンシを引き起こす。このように、マルチプロセッサシステムのプロセッサ全体のスループットと効率が犠牲になり、システムのユーザのリアルタイムおよび／またはマルチメディア体験に重大な影響を与えうる。

したがって、当技術分野において、ネットワーク上のマルチプロセッサシステム間でプロセッサタスクの効率的な分散処理を実現する新規な方法および装置が必要とされている。

本発明の一態様による、インターネット等のネットワークを介して第１のマルチプロセッサシステムから第２のマルチプロセッサシステムにタスクを移動するための方法およびシステムが提供される。

本方法の一態様によると、様々な理由のうち任意の理由のために、少なくとも一つのマルチプロセッサからタスクを移動すべきか否かをマルチプロセッサが決定する。マルチプロセッサがタスクを別のマルチプロセッサに移動すべきと決定すると、第１のマルチプロセッサシステムからアプリケーションをブロードキャストする。アプリケーションは、複数のタスクと一つの属性とを指定する。属性は、アプリケーションをブロードキャストした前段のマルチプロセッサ、もしくは初めにアプリケーションをブロードキャストしたマルチプロセッサ、のうち少なくとも一つからのアプリケーションの距離と、複数のタスクのそれぞれを終了するためのデッドラインと、を表している。

本発明の別の態様によると、属性は、タスクの実行に必要な処理能力を指定する。さらに、同一の属性または別の属性が、タスクの実行に必要なメモリを指定してもよい。アプリケーションは、自身が複数のタスクを保有することによって、またはタスクの位置する場所を示すポインタ情報を使用して、複数のタスクを指定することができる。

本発明の別の態様によると、第１のマルチプロセッサシステムからブロードキャストされたアプリケーションは、ネットワークに接続された第２のマルチプロセッサで受け取られる。第２のマルチプロセッサは、移動されるべきタスクを含むアプリケーション内のタスクをばらす（unbundle）。第２のマルチプロセッサは、タスクを実行するための要件を指定する属性を調査して、当該タスクを第２のマルチプロセッサで実行すべきか否かを判定する。第２のマルチプロセッサは、必要な処理能力および必要なメモリを検査してもよい。

本発明の別の態様によると、第２のマルチプロセッサもまた、アプリケーションをブロードキャストした前段のマルチプロセッサ、もしくは初めにアプリケーションをブロードキャストしたマルチプロセッサ、のうち少なくとも一つからのアプリケーションの距離を調べて、当該タスクを第２のマルチプロセッサシステムで実行すべきか否かを決定する。第２のマルチプロセッサは、第２のマルチプロセッサがタスクを実行しているか否かを第１のマルチプロセッサに連絡するのが好ましい。なお、ここでいう「距離」には時間的な距離と空間的な距離の両方が含まれ、より具体的にはレイテンシやアプリケーション間の帯域などがある。

本発明の別の態様によると、ブロードキャストされたアプリケーションは複数の他のマルチプロセッサによって受け取られる。複数の他のマルチプロセッサは、それぞれアプリケーションに含まれる移動されるべきタスク（単数または複数）をばらす。複数の他のマルチプロセッサは、それぞれ、タスクを実行するための要件を指定する属性を調査して、当該タスクを実行すべきか否かを決定する。好適には、複数の他のマルチプロセッサのそれぞれは、アプリケーションをブロードキャストした前段のマルチプロセッサ、もしくは初めにアプリケーションをブロードキャストしたマルチプロセッサ、のうち少なくとも一つからのアプリケーションの距離と、複数のタスクのそれぞれを終了するためのデッドラインと、を調査して、当該タスクを実行すべきか否かを決定する。

本発明のさらに別の態様によると、タスクを移動するための装置が提供される。この装置は、ネットワークに接続可能なマルチプロセッサであって、該マルチプロセッサによってタスクを実行すべきか、またはネットワークに接続された少なくとも一つのマルチプロセッサに移動すべきかを決定するようにプログラムされたマルチプロセッサを含む。このマルチプロセッサは、少なくとも一つのマルチプロセッサにタスクを移動すべきと決定されたとき、ネットワークを介して当該マルチプロセッサからアプリケーションをブロードキャストするよう指示する。アプリケーションは複数のタスクと一つの属性とを指定し、この属性は、アプリケーションをブロードキャストした前段のマルチプロセッサ、もしくは初めにアプリケーションをブロードキャストしたマルチプロセッサ、のうち少なくとも一つからのアプリケーションの距離と、複数のタスクのそれぞれを終了するためのデッドラインと、を表示する。

本発明の他の態様、特徴および利点は、添付の図面とともになされる本明細書の説明から当業者にとって明らかとなろう。

説明のために、現時点で好適である形態が図面に示されるが、本発明は図示の正確な構成および手段に限定されないことを理解されよう。

同様の符号が同様の要素を示す図面を参照して、図１は、本発明の一つまたは複数の態様によるマルチプロセッサシステム１００を示す。マルチプロセッサシステム１００は、バス１０８を介して、ＤＲＡＭなどの共有メモリ１０６に連結される複数のプロセッサ１０２（任意の数を使用可能である）を備える。共有メモリ１０６はＤＲＡＭでなくてもよい点に注意する。実際、共有メモリは任意の既知の技術または今後開発される技術を用いて形成することができる。

プロセッサ１０２のうちの一台は、例えば処理ユニット１０２Ａである主処理ユニットであることが好ましい。他の処理ユニット１０２は、サブ処理ユニット（ＳＰＵ）、例えば処理ユニット１０２Ｂ、１０２Ｃ、１０２Ｄなどであることが好ましい。サブ処理ユニット１０２は、既知のまたは今後開発されるコンピュータアーキテクチャのうち任意のものを使用して実現可能なものであってよい。サブ処理ユニット１０２の全てが同一のアーキテクチャを使用して実現される必要はなく、実際、それらは異種または同種の構成のいずれであってもよい。主処理ユニット１０２Ａは、サブ処理ユニット１０２Ｂ〜１０２Ｄに対してローカルに、例えば、同一チップ、同一のパッケージ、同一の回路基盤、同一の製品に位置してもよいことに注意する。代替的に、主処理ユニット１０２Ａは、サブ処理ユニット１０２Ｂ〜１０２Ｄに対してリモートに、例えば、バスやインターネットのような通信ネットワークなどを介して接続可能な異なる製品に位置してもよい。同様に、サブ処理ユニット１０２Ｂ〜１０２Ｄは、互いにローカルにまたはリモートに位置してもよい。

主処理ユニット１０２Ａを使用してサブ処理ユニット１０２Ｂ〜１０２Ｄによるデータおよびアプリケーションの処理をスケジューリングし調整する（orchestrate）ことで、サブ処理ユニット１０２Ｂ〜１０２Ｄは、並列に独立してこれらのデータおよびアプリケーションの処理を実行する。しかしながら、本発明の一部の態様によれば、主処理ユニット１０２Ａは、サブ処理ユニットの間のプロセッサタスクの実行をスケジューリングする中心的な役割を果たさない。むしろ、そのようなスケジューリングは、ＳＰＵ自身に任されることが好ましい。

図１のプロセッサ１０２に対する役割および機能の割り当ては柔軟的である。例えば、プロセッサ１０２のいずれもが主処理ユニットまたはサブ処理ユニットであってよい。

図２を参照して、主処理ユニット１０２Ａは、特にＳＰＵの間でのプロセッサタスクのスケジューリングおよび管理に関して、ＳＰＵ１０２Ｂ〜１０２Ｆに対するサービスプロセッサの役割を担うことが好ましい。本発明のいくつかの態様によれば、主処理ユニット１０２Ａは、ソフトウェアアプリケーションの範囲内に含まれるプロセッサタスクを評価することができ、共有メモリ１０６の割り当て、ＳＰＵの割り当て、および共有メモリ１０６内のプロセッサタスク１１０の最初の記憶に関わることができる。共有メモリ１０６の割り当てに関して、主処理ユニット１０２Ａは、所与の数のプロセッサタスク１１０に割り当てられるべきメモリ空間の量を決定することが好ましい。この点に関して、主処理ユニット１０２Ａは、いくつかのプロセッサタスク１１０の記憶用に共有メモリ１０６の第１の領域１０６Ａを割り当て、他のプロセッサタスク１１０の記憶用に共有メモリ１０６の第２の領域１０６Ｂを割り当ててもよい。主処理ユニット１０２Ａは、共有メモリ１０６内の領域１０６Ａおよび領域１０６Ｂそれぞれにおけるデータ同期に関するルールを設定することもできる。

本発明の一つまたは複数のさらなる態様によれば、共有メモリ１０６の領域１０６Ａおよび領域１０６Ｂには、定められた数のサブ処理ユニット１０２のみアクセスすることができる。例えば、共有メモリ１０６の所与の領域の中に格納される特定のプロセッサタスク１１０を実行するために割り当てられるサブ処理ユニット１０２のみアクセスすることができる。例えば、サブ処理ユニット１０２Ｂ〜１０２Ｄのみが、共有メモリ１０６の第１の領域１０６Ａ内のプロセッサタスク１１０へのアクセスが許可されていることが好ましい。同様に、サブ処理ユニット１０２Ｅ〜１０２Ｆのみが、共有メモリ１０６の第２の領域１０６Ｂ内のプロセッサタスク１１０へのアクセスが許可されていることが好ましい。共有メモリ１０６の各領域１０６Ａおよび１０６Ｂを保護する技術に関するさらなる詳細は、「ブロードバンドネットワーク用のコンピュータアーキテクチャのメモリ保護システムおよび方法」と題する米国特許第６，５２６，４９１号に見いだすことができ、その全ての開示は参照により本明細書に援用される。

本発明の一つまたは複数の態様によると、プロセッサタスク１１０が共有メモリ１０６内に配置され、サブ処理ユニット１０２がタスクの実行を割り当てられた後、主処理ユニット１０２Ａは、プロセッサタスク１１０の実行のスケジューリングおよび管理に参加しないことが好ましい。代わりに、それらの責任は関係する特定のサブ処理ユニット１０２に任される。

本発明の様々な実施形態のプロセッサタスク管理特徴に関してさらに詳細を述べる前に、マルチプロセッサシステムを実装するための好適なコンピュータ・アーキテクチャについて説明する。この点に関して、図３の基本処理モジュールまたはプロセッサ要素（processor element：ＰＥ）２００のブロック図を参照する。このコンピュータアーキテクチャによると、マルチプロセッサシステムの全てのサブプロセッサは、共通のコンピューティングモジュール（またはセル）から構成される。この共通のコンピューティングモジュールは、一貫した構造を有し、好ましくは同一の命令セットアーキテクチャを使用する。本発明の別の実施形態では、サブ処理ユニットは異種の構成であってもよい。マルチプロセッサシステムは、一つまたは複数のクライアント、サーバ、ＰＣ、モバイルコンピュータ、ゲーム機、ＰＤＡ、セットトップボックス、機器、デジタルテレビ、およびコンピュータプロセッサを使用する他の装置から形成することができる。

基本処理モジュールは、プロセッサ要素（ＰＥ）である。図３に示すように、ＰＥ２００は、Ｉ／Ｏインタフェース２０２、処理ユニット（processing unit：ＰＵ）２０４、ダイレクト・メモリ・アクセス・コントローラ（ＤＭＡＣ）２０６、複数のサブ処理ユニット２０８、すなわち、サブ処理ユニット２０８Ａ、サブ処理ユニット２０８Ｂ、サブ処理ユニット２０８Ｃおよびサブ処理ユニット２０８Ｄを含む。ローカル（または内部）ＰＥバス２１２は、ＰＵ２０４、サブ処理ユニット２０８、ＤＭＡＣ２０６およびメモリインタフェース２１０の間でデータおよびアプリケーションを送信する。ローカルＰＥバス２１２は、例えば、従来のアーキテクチャを有することができ、またはパケットスイッチネットワークとして実現することもできる。パケットスイッチネットワークとして実現すると、より多くのハードウェアを必要とするが、利用可能な帯域幅を増加することができる。

ＰＥ２００は、デジタルロジックを実装する様々な方法を使用して構成されることができる。しかしながら、ＰＥ２００は、シリコン基板上の相補型金属酸化膜半導体（ＣＭＯＳ）を使用する単一の集積回路として構成されることが好ましい。基板の代替的材料はガリウム・ヒ素、ガリウム・アルミニウム・ヒ素および多様なドーパントを使用するいわゆるＩＩＩ−Ｂ合成物を含む。ＰＥ２００は、超電導材料、例えば高速単一磁束量子（ＲＳＦＱ）論理回路を使用して実現することもできる。

ＰＥ２００は、高帯域幅のメモリ接続２１６を通して、ダイナミック・ランダム・アクセス・メモリ（ＤＲＡＭ）２１４と密接に関連する。ＤＲＡＭ２１４は、ＰＥ２００用のメインメモリ（または共有メモリ）として機能する。ＤＲＡＭ２１４は好ましくはダイナミック・ランダム・アクセス・メモリであるが、例えば、スタティック・ランダム・アクセス・メモリ（ＳＲＡＭ）、磁気ランダム・アクセス・メモリ（ＭＲＡＭ）、光学メモリ、ホログラフィック・メモリなどの他の手段を使用して実現することもできる。ＤＭＡＣ２０６およびおよびメモリインタフェース２１０は、ＤＲＡＭ２１４と、ＰＥ２００のサブ処理ユニット２０８およびＰＵ２０４との間のデータの転送を容易にする。ＤＭＡＣ２０６および／またはメモリインタフェース２１０は、サブ処理ユニット２０８およびＰＵ２０４に対して一体的にまたは別々に配置されていてもよい点に注意する。実際、図示のように別々の構成とする代わりに、ＤＭＡＣ２０６の機能および／またはメモリインタフェース２１０の機能は、サブ処理ユニット２０８およびＰＵ２０４の一つまたは複数（好ましくは全て）と一体であってもよい。

例えば、ＰＵ２０４は、データおよびアプリケーションを独立して処理することができる標準のプロセッサであってもよい。サブ処理ユニット２０８は、好ましくは単一命令マルチデータ（ＳＩＭＤ）プロセッサである。サブ処理ユニット２０８は、並行にまたは独立して、データおよびアプリケーションの処理を実行することが好ましい。ＤＭＡＣ２０６は、ＰＵ２０４およびサブ処理ユニット２０８による、共有ＤＲＡＭ２４に格納されるデータおよびアプリケーション（例えば、プロセッサタスク１１０）へのアクセスを制御する。ＰＵ２０４は、主処理ユニットの役割を引き受けているサブ処理ユニット２０８のうち一つにより実現されてもよいことに注意する。

このモジュール構造にしたがって、特定のコンピュータシステムによって使用されるＰＥ２００の数は、そのシステムによって必要とされる処理能力に基づいて決まる。例えば、サーバは４つのＰＥ２００を使用することができ、ワークステーションは二つのＰＥ２００を使用することができ、ＰＤＡは一つのＰＥ２００を使用することができる。特定のアプリケーションを処理すべく割り当てられるＰＥ２００のサブ処理ユニットの数は、セル内のプログラムおよびデータの複雑さおよび大きさによって決まる。

図４は、サブ処理ユニット２０８の好適な構造および機能を示す。サブ処理ユニット２０８は、ローカルメモリ２５０、レジスタ２５２、一つまたは複数の浮動小数点ユニット２５４、および一つまたは複数の整数ユニット２５６を備える。しかしながら、必要とされる処理能力によって、より多数のまたはより少数の浮動小数点ユニット２５４および整数ユニット２５６を使用してもよい。浮動小数点ユニット２５４は、好ましくは一秒につき３２０億回の浮動小数点演算（３２ＧＦＬＯＰＳ）をする速度で動作し、整数ユニット２５６は、好ましくは一秒につき３２０億回の演算（３２ＧＯＰＳ）をする速度で動作する。

好ましい実施形態では、ローカルメモリ２５０は２５６キロバイトの記憶装置を含み、レジスタ２５２の容量は１２８×１２８ビットである。プロセッサタスク１１０が共有メモリ２１４を使用して実行されない点に注意する。むしろ、タスク１１０は、所与のサブ処理ユニット２０８のローカルメモリ２５０にコピーされ、ローカルに実行される。

ローカルメモリ２５０は、キャッシュメモリであってもキャッシュメモリでなくてもよい。好ましくは、ローカルメモリ２５０はスタティック・ランダム・アクセス・メモリ（ＳＲＡＭ）として構成される。ＰＵ２０４は、ＰＵ２０４により起動されるダイレクトメモリアクセスのために、キャッシュ整合性サポートを必要としてよい。しかしながら、キャッシュ整合性サポートは、サブ処理ユニット２０８によって起動されるダイレクトメモリアクセス、または、外部装置との間でのアクセスについては、不要である。

サブ処理ユニット２０８は、サブ処理ユニット２０８との間でデータおよびアプリケーションを送受信するためのバスインタフェース（Ｉ／Ｆ）２５８をさらに含む。好ましい実施形態では、バスＩ／Ｆ２５８はＤＭＡＣ２０６に連結される。ＤＭＡＣ２０６は、サブ処理ユニット２０８内に一体的に配置することもでき、あるいは外部に配置することもできることを示すよう、図３では点線で描かれている。一対のバス２６８Ａ、２６８Ｂは、バスＩ／Ｆ２５８とローカルメモリ２５０の間でＤＭＡＣ２０６を相互接続する。バス２６８Ａ、２６８Ｂは、好ましくは２５６ビット長である。

サブ処理ユニット２０８は、内部バス２６０、２６２および２６４をさらに含む。好ましい実施形態では、バス２６０は２５６ビットの幅を有し、ローカルメモリ２５０およびレジスタ２５２の間の通信を提供する。バス２６２および２６４は、それぞれ、レジスタ２５２と浮動小数点ユニット２５４の間、レジスタ２５２と整数ユニット２５６の間の通信を提供する。好ましい実施形態では、レジスタ２５２から浮動小数点ユニットまたは整数ユニットに向かうバス２６４と２６２のバス幅は３８４ビットであり、浮動小数点ユニット２５４または整数ユニット２５６からレジスタ２５２に向かうバス２６４および２６２のバス幅は、１２８ビットである。浮動小数点ユニット２５４または整数ユニット２５６からレジスタ２５２へのバス幅より、レジスタ２５２から両ユニットへのバス幅が大きいため、処理の間、レジスタ２５２からより大きいデータフローを収容する。各計算のために、最大で３ワードが必要である。しかしながら、各計算の結果は、通常１ワードのみである。

本発明の様々なプロセッサタスク管理特徴に戻り、図２を参照して、実行のために共有メモリ１０６からＳＰＵ１０２のローカルメモリの一つにいずれのプロセッサタスク１１０をコピーすべきかを決定するために、サブ処理ユニット１０２はタスクテーブルを利用することが好ましい。この点に関して、図５を参照する。図５は、本発明の様々な態様により利用可能なタスクテーブル２８０の概念的な説明である。タスクテーブル２８０は、好ましくは共有メモリ１０６に格納される。タスクテーブル２８０の初期化方法の詳細は、後述する。タスクテーブル２８０は、複数のタスクテーブルエントリＴ１、Ｔ２、Ｔ３その他を含むことが好ましい。各タスクテーブルエントリは、例えば、タスクテーブルエントリをプロセッサタスク１１０に関係付ける連想アドレス指定または他の手段によって、プロセッサタスク１１０（図２参照）の一つに関連付けられるのが好ましい。

好ましい実施形態では、各タスクテーブルエントリは、ステータス表示（ＳＴＡＴ）、優先度表示（ＰＲＩ）、および一対のポインタ（ＰＲＥＶ、ＮＥＸＴ）のうちの少なくとも一つを含んでもよい。ＳＴＡＴは、所与のタスクテーブルエントリに関連付けられるプロセッサタスクが、一つまたは複数のサブ処理ユニットによって実行される準備ができている（ＲＥＡＤＹ）か、または実行中（ＲＵＮＮＩＮＧ）であるかについての表示を提供することが好ましい。ＰＲＩは、関連するプロセッサタスク１１０の優先度についての表示を提供することが好ましい。プロセッサタスク１１０と関連付けられる優先度は任意の数であってよく、これは、ソフトウェアプログラマが設定してもよいし、または、ソフトウェアアプリケーションの実行によって後で設定することもできる。いずれにしても、プロセッサタスク１１０の優先度は、プロセッサタスクが実行される順序を設定するために利用されることができる。ＰＲＥＶ値は、リンク付けされたタスクテーブルエントリの順序付きリスト（または、プロセッサタスクのリスト）において、前のタスクテーブルエントリ（または、前のプロセッサタスク１１０）へのポインタであることが好ましい。ＮＥＸＴ値は、リンク付けされたタスクテーブルエントリの順序付きリスト（または、プロセッサタスクのリスト）において、次のタスクテーブルエントリ（またはプロセッサタスク）へのポインタであることが好ましい。

本発明の一つまたは複数の態様によると、タスクテーブル２８０は、プロセッサタスク１１０が実行のために共有メモリ１０６からコピーされる順序を決定するために、サブ処理ユニット２０８によって利用されることが好ましい。例えば、マルチプロセッサシステム１００または２００上のソフトウェアアプリケーションを適切に実行するために、特定のプロセッサタスク１１０は、特定の順序、すなわち少なくとも一般的な順序、つまりＴ１、Ｔ８、Ｔ６、Ｔ９の順序で実行される必要があってもよい。プロセッサタスク配列のこの実施例を反映するために、タスクテーブル２８０は、拡張プロセッサタスクによる、タスクテーブルエントリのリンク付きリストを作成するタスクテーブルエントリのＰＲＥＶ部分およびＮＥＸＴ部分におけるポインタを含むことが好ましい。上記例の特殊性によると、タスクテーブルエントリＴ１は、タスクテーブルエントリＴ８をポイントするＮＥＸＴ値を含む。タスクテーブルエントリＴ８は、タスクテーブルエントリＴ１をポイントするＰＲＥＶ値と、タスクテーブルエントリＴ６をポイントするＮＥＸＴ値を含む。タスクテーブルエントリＴ６は、タスクテーブルエントリＴ８をポイントするＰＲＥＶ値と、タスクテーブルエントリＴ９をポイントするＮＥＸＴ値を含む。タスクテーブルエントリＴ９は、タスクテーブルエントリＴ６をポイントするＰＲＥＶ値を含む。

図６を参照して、上記例のタスクテーブルエントリのリンク付きリストは、状態図として概念的に示すことができる。この状態図において、タスクテーブルエントリＴ１に関連付けられる特定のプロセッサタスクからの遷移が、タスクテーブルエントリＴ８に関連付けられている別のプロセッサタスクの選択および実行を引き起こす。タスクテーブルエントリＴ８に関連付けられるプロセッサタスクからの遷移が、タスクテーブルエントリＴ６に関連付けられるプロセッサタスクの選択および実行を引き起こし、以下同様である。第１の、または先頭のタスクテーブルエントリＴ１が、タスクテーブルエントリＴ９をポイントするＰＲＥＶ値を含むことを保証し、また、タスクテーブルエントリＴ９がタスクテーブルエントリＴ１をポイントするＮＥＸＴ値を含むことを保証することによって、タスクテーブルエントリ（および／またはプロセッサタスク自身）の循環的な関連を達成することができる。

動作中、共有メモリ１０６のプロセッサタスク１１０（好ましくは所与の領域１０６Ａまたは１０６Ｂ内の）のプールを実行するために割り当てられるそれぞれのサブ処理ユニット１０２は、いずれのプロセッサタスク１１０が実行のために次に占有されるかを判定するために、まず、タスクテーブル２８０にアクセスする。リンク付きリストの最初のまたは先頭のエントリの特定に役立てるために、サブ処理ユニット１０２は、図７に概念的に示すタスクキュー２８２へのアクセスを有することが好ましい。タスクキュー２８２は、関連するプロセッサタスク１１０それぞれの優先度のためのエントリを含むことが好ましい。各エントリは、ＨＥＡＤポインタおよびＴＡＩＬポインタのうちの少なくとも一つを含むことが好ましい。

図６をさらに参照して、例示的なリンク付きリストの状態図は、優先度１を有するプロセッサタスク１１０を表している。実際、エントリＴ１、Ｔ８、Ｔ６およびＴ９のタスクテーブルエントリ（図５）は、それぞれ「１」のＰＲＩ値を含む。

優先度１と関連するタスクキューエントリのＨＥＡＤポインタとＴＡＩＬポインタは、それぞれ、タスクテーブルエントリＴ１とタスクテーブルエントリＴ９へのポインタを含む。タスクキュー２８２の他のエントリは、他のリンク付きリスト用の他の優先度のＨＥＡＤポインタおよびＴＡＩＬポインタと関連付けられる。このように、本発明の様々な実施形態は、（拡張プロセッサタスクによって）タスクテーブルエントリの多数のリンク付きリストを含むことができ、各リンク付きリストは同一のまたは少なくとも類似の優先度を含むことを考慮する。それぞれのサブ処理ユニット１０２は、タスクテーブル２８０とタスクキュー２８２を利用して、いずれのプロセッサタスク１１０が、実行のために共有メモリ１０６からコピーされるべきかについて決定することが好ましい。それぞれのリンク付きリストが作成され適切に維持されると仮定すると、ソフトウェア・アプリケーション全体の実行時に所望の結果を達成するために、プロセッサタスク１１０は適切な順序で実行されることができる。

本発明の様々な態様によると、サブ処理ユニット１０２は、ソフトウェアアプリケーションの実行の間、タスクテーブル２８０とタスクキュー２８２を維持し修正する。この点に関して、図８から図１０を参照する。これらは、本発明の一つまたは複数の望ましい特徴を達成するのに適したプロセスフローを表すフロー図である。アクション３００で、特定のサブ処理ユニット１０２が呼び出されて、プロセッサタスク１１０を共有メモリ１０６から自身のローカルメモリにコピーし始める。アクション３０２で、サブ処理ユニット１０２はタスクキュー２８２をロックし、タスクキュー２８２を自身のローカルメモリにコピーする。その後、タスクキュー２８２は、最も高い優先度の準備ができたタスクを求めて検索される（アクション３０４）。図７で示した実施例を使用すれば、タスクキュー２８２は、最高の優先度、例えば優先度１のプロセッサタスクに関連付けられているタスクテーブルエントリＴ１をポイントするＨＥＡＤポインタを含む。タスクテーブルエントリＴ１に関連付けられたプロセッサタスクが実行のために目標とされるので、サブ処理ユニット１０２は、好ましくはタスクキュー２８２を修正して、そのプロセッサタスクへの参照を除去する（アクション３０６）。好ましい実施形態では、これは、タスクテーブルエントリＴ１へのＨＥＡＤポインタを、実行のために占有されるべき次のプロセッサタスクを表示する新規な第１の（または先頭の）タスクテーブルエントリになる別のタスクテーブルエントリへと修正することを伴う。特に、タスクテーブルエントリＴ１のＮＥＸＴポインタが、優先度１の新たなＨＥＡＤポインタとして用いられてもよい。実際、図６に示したように、タスクテーブルエントリＴ１に関連するプロセッサタスクが実行中である（ＲＵＮＮＩＮＧ）と、もはや準備のできた（ＲＥＡＤＹ）状態ではなく、状態図から除去されなければならない。状態図の先頭のエントリとして、タスクテーブルエントリＴ８を残さなければならない。タスクテーブルエントリＴ１がもはやＲＥＡＤＹ状態図の一部でないとき、タスクテーブルエントリＴ８のＰＲＥＶポインタはタスクテーブルエントリＴ９をポイントするように修正されてもよい。このように、アクション３０８において、タスクテーブルが修正可能となるように、タスクテーブルはラベル付けされＳＰＵ１０２のローカルメモリにコピーされる。同様に、タスクテーブルエントリＴ９のＮＥＸＴポインタは、タスクテーブルエントリＴ８をポイントするように修正されてもよい。

本発明の好ましい態様によると、ＳＰＵ１０２は、タスクテーブルエントリＴ１のＳＴＡＴ値をＲＥＡＤＹからＲＵＮＮＩＮＧに修正することが好ましい（図９のアクション３１０）。アクション３１２として、次のタスクを呼び出すためにＳＰＵ１０２がコール（アクション３００）された時点で、ＳＰＵ１０２が前のタスクを実行しているかに関しての判定がなされることが好ましい。ＳＰＵ１０２上で動作中の前のタスクが他のタスクに譲るとき、これが生じてもよい。本実施例のために、前のタスクが次のプロセッサタスク１１０に実行権を譲渡（yield to）せず、さらに、アクション３１２における判定の結果が否定であったと仮定する。したがって、プロセスフローは好ましくはアクション３１８へ進む。ここで、ＳＰＵ１０２は、修正されたタスクキュー２８２と修正されたタスク・テーブル２８０を共有メモリ１０６に書き戻す。この時点で、タスクテーブル２８０とタスクキュー２８２は更新され、他のサブ処理ユニット１０２によってコピーおよび修正されてもよいように、好ましい同期化技術にしたがってロックが解除される。

前のプロセッサタスク１１０が次のプロセッサタスクに実行権を譲渡したときのように、アクション３１２における判定結果が肯定である場合、プロセスフローは好ましくはアクション３１４へ進む。そこで、ＳＰＵは、好ましくは、実行権を譲渡するプロセッサタスクに関連付けられているタスクテーブルエントリのＳＴＡＴ値を、ＲＵＮＮＩＮＧからＲＥＡＤＹに修正する。さらに、ＳＰＵは、実行権を譲渡するプロセッサタスクを適当なリンク付きリストに再導入（reintroduce）するために、実行権を譲渡するプロセッサタスクに関連するタスクテーブルエントリを含む様々なタスクテーブルエントリのＰＲＥＶポインタとＮＥＸＴポインタを修正してもよい。好ましくは、関連するタスクテーブルエントリのＰＲＩ値に反映されるように、実行権を譲渡するプロセッサタスク１１０の優先度を参照することによって、これが達成される。アクション３１６で、プロセッサタスクが後に占有されてもよいように、実行権を譲渡するプロセッサタスクが共有メモリ１０６に書き込まれてもよい。その後、プロセスフローはアクション３１８へ進む。そこで、タスクキュー２８２とタスクテーブル２８０は、共有メモリ１０６に書き戻される。

アクション３２０（図１０）で、次のプロセッサタスク１１０（例えば、タスクテーブルエントリＴ８に関連するプロセッサタスク）は、サブ処理ユニット１０２によって共有メモリ１０６から自身のローカルメモリにコピーされる。アクション３２２で、サブ処理ユニット１０２は、新たなプロセッサタスク１１０の実行に使用するため、（例えば、新たなプロセッサタスクと関連する任意のデータを有する）自身のレジスタを復元および／または更新することが好ましい。最後に、アクション３２４で、新たなプロセッサタスク１１０は、サブ処理ユニット１０２によって実行される。

上記アクションは例示を目的としてのみ示されており、当業者は、本発明の趣旨および範囲から逸脱することなくこれらのアクションの順序を修正可能であることを理解するであろう。例えば、後述するように、プロセッサタスクが共有メモリからコピーされ共有メモリに書き戻される順序、および、タスクテーブルとタスクキュー２８２が利用される順序は、望ましい結果を達成するために修正可能である。

上述のように、主処理ユニット１０２Ａは、プロセッサタスク１１０の実行および管理がサブ処理ユニット１０２によって対処可能となる状態にシステムを準備するために、システムの初期段階の間に利用されることが好ましい。サブ処理ユニット１０２も、第１インスタンスでタスクテーブル２８０とタスクキュー２８２を作成するために、初期化ルーチンを実行することが好ましい。これらの初期化プロセスを、図１１のフロー図に示す。

アクション３５０で、サービスプロセッサ（例えば、主処理ユニット１０２）は、システム上で実行されるソフトウェアアプリケーションを評価して、プロセッサタスク１１０を実行する複数のサブ処理ユニット１０２を割り当てる。プロセスフローは、好ましくはアクション３５２へ進み、そこで、サービスプロセッサがソフトウェアアプリケーションを評価して、プロセッサタスク１１０を受け取るために共有メモリ１０６の一つまたは複数の部分を割り当てる。アクション３５４で、アクション３５２で実行された任意のメモリ・アロケーションにしたがって、プロセッサタスク１１０が共有メモリ１０６にロードされる。初期化プロセスのこの段階においては、サービスプロセッサは、メンテナンスおよび／またはサブ処理ユニット１０２の間でのプロセッサタスクの配分に関与していないことが好ましい。

プロセスフローは、好ましくはアクション３５６へ進む。そこで、サブ処理ユニット１０２は互いを初期化し、いずれのＳＰＵが第１インスタンスにおいてタスクテーブル２８０とタスクキュー２８２を準備するかを決定する。アクション３５８で、タスクテーブル２８０とタスクキュー２８２を作成する責任を有したサブ処理ユニット１０２は、この種の情報を準備して、同じものを共有メモリ１０６に格納する。例えば、タスクテーブル２８０とタスクキュー２８２の初期化は、好ましくは、各ＳＰＵカーネルに最初のタスクを実行させることによって行われることが好ましい。以下に示すプログラム「init.c」は、各ＳＰＵによって実行される最初のタスクの好適な実施例である。

#include <spurs.h>
#include "task_instance.h"

int
main()
{
spurs_beggin_init();
if（spurs_get_spu_id() = = 0）｛
spurs_create_task(melchior);
spurs_create_task(balthasar);
spurs_create_task(caspar);

spurs_start_task(melchior);
spurs_start_task(balthasar);
spurs_start_task(caspar);
}

spurs_end_init();
return 0;
}

このプログラムにおいて、「melchior」、「balthasar」および「caspar」は非常に初期のタスクの名称であり、これらは典型的なスタートアップタスクである。ＳＰＵカーネルの全てがこの初期タスクinit.cを実行する。しかし、一つのＳＰＵ（ＩＤ０を持つＳＰＵ）だけは、if(spurs_get_spu_id () = = 0）のコードラインで指定されるこれらのタスクを実行する。他のＳＰＵの全て、例えば異なるＩＤを持つＳＰＵの全ては、spurs_end_init()で待機する。このように、各ＳＰＵカーネルは最初のタスクを実行し、この最初のタスクが終了した後、本明細書で述べるように、ＳＰＵカーネルは次のタスクの検索を開始する。

上述のように、サービス・プロセッサとして動作する主処理ユニット１０２は、一つまたは複数のプロセッサタスク１１０をグループとして指定してもよいことに注意する。これは、初期化段階の間に実行されることが好ましい。例えば、二つ以上のプロセッサタスク１１０が互いに緊密に通信する必要があってもよく、したがって、それらがタスクグループ内でグループ化されている場合、プロセッサタスクをより効率的に実行することができる。暗号化プログラムは、プロセッサタスクが一つ以上のタスクグループに形成されている場合、緊密に通信しより効率的に実行されるプロセッサタスクを含むことができるアプリケーションの一例である。

本発明のプロセッサタスク管理の特徴を利用して、主処理ユニット１０２Ａが、特定のサブ処理ユニット１０２またはサブ処理ユニット１０２のグループのデバイスドライバをオフロード（off-load）するのを助けることができる。例えば、ギガビットイーサネットハンドラ（イーサネットは登録商標）のようなネットワークインタフェースは、ＣＰＵパワーの８０％まで利用することができる。ネットワークインタフェースが主処理ユニット１０２Ａによってのみ実行される場合、主処理ユニットは１０２Ａは、他のサービス指向の処理タスクをするために利用することができない。したがって、主処理ユニットが１０２Ａが、一つまたは複数のサブ処理ユニット１０２にネットワークインタフェースプログラムをオフロードすることは、有益でありえる。主処理ユニット１０２Ａは、ネットワークインタフェースの処理タスクを共有メモリ１０６に配置し、これを実行する一つまたは複数のサブ処理ユニット１０２を割り当てることによって、この結果を達成してもよい。それに応じて、ＳＰＵは、そのようなプロセッサタスクの実行を管理しスケジューリングするのに適したタスクテーブル２８０とタスクキュー２８２を形成してもよい。したがって、有利なことには、主処理ユニット１０２Ａは、より多くのＣＰＵパワーを他のタスクの実行に充てることができる。主処理ユニット１０２Ａは、また、例えばデジタルテレビデバイスドライバなどの他のデバイスドライバをオフロードしてもよい。ＳＰＵにオフロードさせるための好ましい候補である他のデバイスドライバは、重いプロトコルスタックを有するものである。例えば、ＨＤＤレコーダなどのリアルタイム高速アクセスデバイス用のドライバは、オフロードされると有利である。オフロードされてもよいタスクの他の実施例には、仮想プライベートネットワークおよびＩＰ（例えばＶｏＩＰ）アプリケーションを介したマルチメディアに使用されるネットワークパケット暗号化／解読タスクが含まれる。

図１２を参照して、プロセッサタスクのステータスの状態図の一例を示す。タスク状態は、実行（ＲＵＮＮＩＮＧ）状態、準備（ＲＥＡＤＹ）状態、ブロック（ＢＬＯＣＫＥＤ）状態、休止（ＤＯＲＭＡＮＴ）状態、および不在（ＮＯＮ−ＥＸＩＳＴＥＮＴ）状態の５つのカテゴリに分類することができる。プロセッサタスクは、現在実行中であるときは、実行（ＲＵＮＮＩＮＧ）状態にある。ある条件下では、プロセッサタスクは、例えば割り込みの間、タスクコンテクストがなくても、実行状態を維持することができる。プロセッサタスクは、タスクの実行の準備ができているが、より高い優先順位を有する一つまたは複数のプロセッサタスクが既に実行されており、またサブ処理ユニットがタスクの占有のために利用できないため、実行することができないときに、準備（ＲＥＡＤＹ）状態にある。準備状態のプロセッサタスクの優先度が共有メモリ１０６の準備状態タスクのプールの中で十分に高い場合、サブ処理ユニットはそのプロセッサタスクを占有しそれを実行してもよい。このように、タスクがディスパッチされる（dispatch）とき、プロセッサタスクの状態は準備状態から実行状態に変化してもよい。反対に、この種のタスクがプリエンプティブ実行（先取り）されるかまたはその実行の間に侵害される場合、実行状態のタスクは準備状態に変化してもよい。プロセッサタスクのプリエンプティブ実行の実施例は、一つのプロセッサタスクが別のタスクに実行権を譲渡することに関連して、既に述べた。

ブロック状態カテゴリは、待機（ＷＡＩＴＩＮＧ）状態、中断（ＳＵＳＰＥＮＤＥＤ）状態、および待機中断（ＷＡＩＴＩＮＧ−ＳＵＳＰＥＮＤＥＤ）状態を含んでもよい。タスクの実行を継続する前に特定の条件が満足されなければならないことを規定するサービスコールの呼び出しのために、タスクがブロックされるとき、プロセッサタスクは待機（ＷＡＩＴＩＮＧ）状態にある。このように、タスクの実行状態は、サービスコールの呼び出し時に待機状態に変化してもよい。待機状態のプロセッサタスクは、規定された条件が満足するとき準備状態に解放されてもよく、これによって、その後に、処理中のタスクがサブ処理ユニット１０２に占有されることが可能になる。タスクが強制的に停止される（タスクそれ自身が呼び出してもよい）とき、プロセッサタスクは実行状態から中断（ＳＵＳＰＥＮＤＥＤ）状態に入ってもよい。同様に、準備状態のプロセッサタスクは、強制されたアクションによって中断状態に入ってもよい。このようなプロセッサタスクの強制的な停止が開放されるとき、中断状態のプロセッサタスクが再開され準備状態に入ってもよい。プロセッサタスクは、タスクが満足するべき条件を待機しておりまた強制的に中断させられているとき、待機中断（ＷＡＩＴＩＮＧ−ＳＵＳＰＥＮＤＥＤ）状態にある。したがって、待機中断状態のプロセッサタスクは、プロセッサタスクの強制的中断時に待機状態に入ってもよく、ここでプロセッサタスクは満足すべき条件を待機する。

タスクが実行されていないかまたは既にその実行を終了したとき、プロセッサタスクは休止（ＤＯＲＭＡＮＴ）状態にある。休止状態のプロセッサタスクは、適当な状況の下で準備状態に入ってもよい。不在（ＮＯＮ−ＥＸＩＳＴＥＮＴ）状態は、例えば、タスクがまだ作成されていなかったりまたは既に削除されているなどによって、タスクがシステム内に存在しないいわゆる仮想状態を指す。

準備状態へ移動したタスクが実行状態のタスクより高い優先順位（または、優先度）を有する場合、より低い優先順位のタスクが準備状態へ移動し、より高い優先度のタスクがディスパッチされて実行状態へ移動することが好ましい。この状況において、より低い優先度のタスクは、より高い優先度のタスクによってプリエンプティブ実行されている。

ノン・プリエンプティブな（non-preemptive）、優先度に基づくタスクスケジューリングは、プロセッサタスクに割り当てられた優先度に基づいてなされる。同じ優先度を有する多くのプロセッサタスクがある場合、スケジューリングは、最初に来て最初に役立つ（first-come, first-served：ＦＣＦＳ）ことを基準に実行される。このタスクスケジューリングの規則は、タスク優先度に基づいたタスク間の優先順位を使用して定められてもよい。実行可能なタスクが存在する場合、せいぜい、高い優先順位のタスクと同数の割り当てられたサブ処理ユニット１０２が実行状態にある。実行可能なタスクの残りは、準備状態にある。異なる優先度を有するタスクの中で、最も高い優先度を有するタスクは、より高い優先順位を有する。同じ優先度のタスクの中で、最も早く実行可能な（実行中または準備ができている）状態に入ったプロセッサタスクは、より高い優先順位を有する。しかしながら、同じ優先度のタスク間の優先順位は、いくつかのサービスコールの呼び出しのせいで変化してもよい。プロセッサタスクが他のプロセッサタスクに対して優先順位を与えられると、ディスパッチが直ちに発生し、タスクが実行状態に移動することが好ましい。

図１３と図１４を参照して、本発明の特定の態様にしたがった特定のプリエンプション（preemption）特徴を示す。上述のように、実行状態にあるプロセッサタスク（例えばタスクＡ）はプリエンプティブ実行されるか、または準備状態にある別のプロセッサタスク（例えばタスクＢ）に実行権を譲渡してもよい。図１３と図１４に示すように、タスクＡは、実行権の譲渡の時点まで、サブ処理ユニット１０２で実行されている。この時点で、ＳＰＵのカーネルは、共有メモリ１０６にタスクＡをコピーする（タスクＡを保存する）よう動作する。その後、タスクＢは、共有メモリ１０６からＳＰＵのローカルメモリにコピーされる（タスクＢを復元する）。そして、ＳＰＵはタスクＢを実行する。この技術は、ローカルメモリの使用量および高い帯域幅については比較的高い性能を享受する一方、実行権を譲渡した時点から最適化されないタスクＢの実行の時点までのタスク実行レイテンシが存在する。

図１５と図１６を参照して、本発明のさらなる態様による代替的方法を示す。このシナリオにおいて、タスクＡをローカルメモリから共有メモリ１０６にコピーする前に、タスクＢを共有メモリ１０６からサブ処理ユニット１０２のローカルメモリにコピーしてもよい。この点に関して、サブ処理ユニット１０２は、共有メモリ１０６からタスクＢを特定して読み出すための処置を同時にとりながら、タスクＡを実行してもよい。これは、タスクテーブル２８０とタスクキュー２８２を共有メモリ１０６からサブ処理ユニット１０２Ａのローカルメモリにコピーし、それらを用いて次の準備状態のタスク、すなわちタスクＢを特定することを伴う。実行権の譲渡の時点で、サブ処理ユニット１０２Ａのカーネルは、ローカルメモリから共有メモリ１０６にタスクＡをコピーするが、これは、上述のようにタスクテーブル２８０とタスクキュー２８２を修正することを伴ってもよい。その後、サブ処理ユニット１０２はタスクＢの実行を占有してもよい。この技術は、図１３と図１４に示した技術と比較して、実行権の譲渡とタスクＢの実行との間のレイテンシを大きく削減する。

図１７と図１８を参照して、本発明の一つまたは複数のさらなる態様にしたがって、実行権の譲渡とタスクＢの実行との間のレイテンシをさらに削減することもできる。より詳細には、実行権の譲渡の時点までは、図１５と図１６に関して先に述べたのと実質的に同様な方法でサブ処理ユニット１０２が動作してよい。しかしながら、実行権の譲渡の後、サブ処理ユニット１０２はタスクＢの実行を開始するのが好ましい。実質的に同時に、サブ処理ユニット１０２のカーネルは、タスクＡをサブ処理ユニット１０２のローカルメモリから共有メモリ１０６にコピーするように動作することが好ましい。タスクＢが実行件の譲渡後すぐに実行されるので、図１４から図１６に示した方法と比較してレイテンシが大きく削減される。

本発明の一つまたは複数の態様によると、サブ処理ユニット１０２は、実行のためにローカルメモリ内の多数のプロセッサタスクを維持してもよい。これは、図１９で示される。多数のプロセッサタスクの実行を管理するために、ローカルメモリは、複数のページとページテーブルを含んでもよい。この方法の利点は、レイテンシがさらに削減できるという点である。但し、その欠点の一つとして、ローカルメモリ内の相当多くの空間がプロセスタスクの実行によって独占される。

図２０から図２２を参照して、本発明の一つまたは複数の態様によるプロセッサタスクの移動（マイグレーション）を示す。これらの図は、プロセッサタスク、例えばタスクＢが、サブ処理ユニットＳＰＵ１から別のサブ処理ユニットＳＰＵ２に移動される方法を示している。移動は、何らかの条件、例えばそれぞれのプロセッサタスクと関連付けられるそれぞれの優先度に基づいてもよい。本発明のいくつかの態様によれば、一つのサブ処理ユニットから別のサブ処理ユニットへのプロセッサタスクの移動は、プリエンプティブでなくてもよい。言い換えると、プロセッサタスクの移動は、優先度条件とタイミングの結果として自然に起こり、移動を引き起こす何らかの決定に基づくのではない。

このノン・プリエンプティブな移動は、以下の実施例で示すことができる。タスクテーブルを利用している共有メモリ１０６からプロセッサタスクＢが選択され、このタスクテーブルが、実行の準備ができているプロセッサタスクの優先度順序を表す、と仮定する。タスクＢは、サブ処理ユニットＳＰＵ１上で動作している。同様に、タスクテーブルにしたがって共有メモリ１０６からプロセッサタスクＣが選択され、サブ処理ユニットＳＰＵ２上で動作していると仮定する。プロセッサタスクＢとプロセッサタスクＣが選択された時点で、より高い優先度のプロセッサタスクＡは実行の準備ができておらず、したがって実行のために選択されたなかったと仮定する。しかしながら、プロセッサタスクＢとプロセッサタスクＣが動作している間に、プロセッサタスクＡの実行の準備ができると仮定する。

図２１を参照して、プロセッサタスクＢは、サブ処理ユニットＳＰＵ１の実行権を譲渡（yield）してもよい。プロセッサタスクＢによるこの譲渡アクションは、実行権の譲渡がソフトウェアアプリケーションの全体的な実行に有益であると判断したプログラマにより発生してもよい。いずれの場合も、サブ処理ユニットＳＰＵ１は、共有メモリ１０６にプロセッサタスクＢを書き込み、タスクテーブルを更新することによって、この実行権の譲渡に応答する。サブ処理ユニットＳＰＵ１はまた、タスクテーブルにアクセスし、共有メモリ１０６内の複数のプロセッサタスクのうちいずれをコピーし実行するべきかを判定する。この例では、タスクテーブルによるとプロセッサタスクＡが最も高い優先度を持ち、したがって、サブ処理ユニットＳＰ１は、プロセッサタスクＡを実行のために共有メモリ１０６から自身のローカルメモリにコピーする。この時点で、サブ処理ユニットＳＰ１はプロセッサタスクＡを実行し、サブ処理ユニットＳＰ２はプロセッサタスクＣの実行を継続する。

図２２をさらに参照して、プロセッサタスクＣは、他のプロセッサタスクにサブ処理ユニットＳＰＵ２の実行権を譲渡してもよい。また、この実行権の譲渡は、プログラム命令および／またはプロセッサタスクＣの条件によって呼び出されてもよい。いずれの場合も、サブ処理ユニットＳＰ２はプロセッサタスクＣを共有メモリ１０６に書き戻し、タスクテーブルを更新する。サブ処理ユニットＳＰ２はまた、タスクテーブルにアクセスし、実行の準備ができているプロセッサタスクのうちいずれをコピーするかを決定する。この実施例では、プロセッサタスクＢが実行の準備ができており、また実行の準備ができている複数のプロセッサタスクの中で最も高い優先度を持つ。したがって、サブ処理ユニットＳＰＵ２は、実行のためにプロセッサタスクＢを共有メモリ１０６から自身のローカルメモリにコピーする。

図２０に示した処理状況と図２２に示した処理状況を比較すると、プロセッサタスクＢがサブ処理ユニットＳＰＵ１からサブ処理ユニットＳＰＵ２に移動したことが分かる。

図２３および図２４を参照して、本発明のプリエンプティブなマルチタスク態様を示す。本発明のこれらの態様は、例えばサブ処理ユニットＳＰＵ２であるサブ処理ユニット上で実行中の低い優先度のプロセッサタスクが、より高い優先度のプロセッサタスク、例えばプロセッサタスクＡでプリエンプティブに置換されてもよいことを述べる。より詳細には、プロセッサタスクＢはサブ処理ユニットＳＰＵ１上で動作していてもよいし、プロセッサタスクＣはサブ処理ユニットＳＰＵ２（図２３）上で動作していてもよい。その後、より高い優先度タスク、つまりタスクＡの実行の準備ができるようになってもよい。これは、システムの他のサブ処理ユニットによる何らかのアクションを原因として発生してもよい。

説明のため、例えばプロセッサタスクＢの実行の結果として、サブ処理ユニットＳＰＵ１がタスクＡのステータスを実行状態に変更したと仮定する。その結果、サブ処理ユニットＳＰＵ１は、プロセッサタスクＡの優先度が、他のサブ処理ユニット上で動作中のプロセッサタスクのあらゆる優先度より高いか否かについての判定をすることが好ましい。この単純化されたケースにおいて、サブ処理ユニットＳＰＵ１は、プロセッサタスクＡがプロセッサタスクＣより高い優先度を持つか否かについて判定を行う。優先度が高い場合、サブ処理ユニットＳＰＵ１は、少なくともプロセッサタスクＣをプロセッサタスクＡで置換することを開始する。言い換えると、 サブ処理ユニットＳＰＵ１は、プロセッサタスクＣにサブ処理ユニット１０２を明け渡してプロセッサタスクＡに与えさせる。この点に関して、サブ処理ユニットＳＰＵ１のカーネルは、サブ処理ユニットＳＰＵ２のカーネルに割り込みを発行してもよい。割り込みに応答して、サブ処理ユニットＳＰＵ２は、共有メモリ１０６にプロセッサタスクＣを書き戻して、タスクテーブル（図２４）を更新してもよい。サブ処理ユニットＳＰＵ２はまた、実行のためにプロセッサタスクＡを共有メモリから自身のローカルメモリにコピーしてもよい。

図２５と図２６を参照して、本発明の特定の直接移動態様を示す。これらの態様は、サブ処理ユニットの一つで実行中のより高い優先度のプロセッサタスクが、より低い優先度のプロセッサタスクを実行している別のサブ処理ユニットに移動されてもよいことを述べる。この移動は、より高い優先度のプロセッサタスクを実行しているサブ処理ユニットによって受け取られる直接の割り込みに応答してなされてもよい。図２５を参照して、サブ処理ユニットＳＰＵ１は、他のいくつかのタスクを実行しなければならないことを示す割り込みを受け取ってもよい。この割り込みは、サブ処理ユニットＳＰＵ１に、システムの他のサブ処理ユニットのいずれがより低い優先度のプロセッサタスクを実行しているかについての判定をさせるようにしてもよい。その場合、このようなサブ処理ユニットは、より高い優先度の処理タスクを支持して、プロセッサタスクの実行権を譲渡してもよい。より詳細には、サブ処理ユニットＳＰＵ１は、サブ処理ユニットＳＰＵ２がプロセッサタスクＡより低い優先度のプロセッサタスク（例えばプロセッサタスクＢ）を実行していると判定する場合、サブ処理ユニットＳＰＵ１のカーネルは、サブ処理ユニットＳＰＵ２のカーネルに割り込みを発行することが好ましい。割り込みに応答して、サブ処理ユニットＳＰＵ２は、プロセッサタスクＢを自身のローカルメモリから共有メモリ１０６に書き戻して、タスクテーブルを更新する。サブ処理ユニットＳＰＵ２はまた、実行のためにプロセッサタスクＡをサブ処理ユニットＳＰＵ１のローカルメモリから自身のローカルメモリにコピーする（または、移動する）ことが好ましい。

図２７は、処理ユニット（ＰＵ）が本発明の一態様にしたがって割り込みを処理する方法について示す。第１のステップにおいて、ＰＵは割り込みを受け取る。ＰＵは、いずれのサブ処理ユニット（この場合、ＳＰＵ０、ＳＰＵ１、ＳＰＵ２のグループ）が最も低い優先度を有しているかを判定する。そして、ＰＵは最も低い優先度を有するＳＰＵに割り込みを送信する。図２７の場合、ＳＰＵ２が最も低い優先度を持つので、ＰＵはＳＰＵ２に割り込みを送信する。

本発明の一つまたは複数のさらなる態様によると、サブ処理ユニットの一つから別のサブ処理ユニットへの割り込みは、多数の方法で処理することができる。図２８を参照して、本発明の一実施形態において、一つのサブ処理ユニットが、システム内の他のサブ処理ユニットのいずれかに対する割り込みを管理するよう指定されていてもよい。指定されたサブ処理ユニットは、このようなタスク移動割り込みの全てを受け取り、それらを自ら処理するか、または他のサブ処理ユニットにその割り込みを渡すかについて判定をする。例えば、割り込みが指定されたサブ処理ユニットに向けられたものであった場合、指定されたサブ処理ユニット自身でその割り込みを処理してもよい。代替的に、割り込みが指定されたサブ処理ユニットに向けられたものでなかった場合、指定されたサブ処理ユニットは、その割り込みを、最も低い優先度のプロセッサタスクを実行しているサブ処理ユニットに送信してもよい。

図２９は、分散割り込み処理スキームが使用される別の方法を示す。この技術によると、それぞれの割り込みは各サブ処理ユニットに割り当てられる。例えば、割り込みＡがサブ処理ユニットＳＰＵ０に割り当てられてもよい。割り込みＢ、Ｃがサブ処理ユニットＳＰＵ１に割り当てられ、割り込みＤ、Ｅ、Ｆがサブ処理ユニットＳＰＵ２に割り当てられてもよい。

図２３から図２６を参照して述べた説明では、システムの他のサブ処理ユニット上で動作中のるプロセッサタスクの優先度を、サブ処理ユニットが判定可能である必要があった。本発明の一実施形態によれば、サブ処理ユニットは、実行中のプロセッサタスクの優先度を判定する際に、共有のタスク優先度テーブルを利用してもよい。共有タスク優先度テーブルは共有メモリに置かれていてもよく、サブ処理ユニット識別子およびプロセッサタスク優先度識別子のための複数のエントリを含んでいてもよい。例えば、サブ処理ユニット識別子は、サブ処理ユニットに固有の数字および／または英数字のコードであってもよい。プロセッサタスク優先度識別子は、好ましくは、実行中の特定のプロセッサタスクの優先度を示す。共有タスク優先度テーブルの各エントリは、サブ処理ユニット識別子と優先度識別子のペアを含むことが好ましく、これらは、関連付けられたサブ処理ユニット上で実行中の所与のプロセッサタスクの優先度を示す。このように、実行中のプロセッサタスクの優先度を判定しようとしているサブ処理ユニットは、共有タスク優先度テーブルにアクセスして、より低い優先度のプロセッサタスクを実行しているサブ処理ユニットを発見してもよい。最も低い優先度のプロセッサタスクを実行中のサブ処理ユニットが特定されて、より高い優先度のプロセッサタスクに実行権を譲渡することが好ましい。

本発明の他の実施形態は、サブ処理ユニットが、いずれのサブ処理ユニットが最も低い優先度のプロセッサタスクを実行中かを表す共有変数を利用することを提供する。優先度の正確な表示が保証されるように、共有変数の使用は微少更新プロセス（atomic update process）を通して達成されることが好ましい。代替的な方法は、一つのサブ処理ユニットから別のサブ処理ユニットに順次送信される、連続したメッセージを利用してもよい。メッセージは、より低い優先度のプロセッサタスクの優先度識別子とサブ処理ユニット識別子によって更新されてもよい。

図３０を参照して、本発明の別の実施形態は、処理能力を強化するために、多数のＰＥ２００を結合することによって、プロセッサタスク１１０を実行するために割り当てられるサブ処理ユニット２０８の数を増加してもよいことを考察する。例えば、二つ以上のＰＥ２００Ａ、２００Ｂは、一つまたは複数のチップパッケージ内などにパッケージングされるか結合されて、一組のマルチプロセッサ装置を形成してもよい。この構成を広帯域エンジン（ＢＥ）と称してもよい。ＢＥ２９０は、二つのＰＥ２００Ａ、２００Ｂを含み、これらはバス２１２を介してデータ通信のために相互接続される。ＰＥ２００Ａ、２００Ｂおよび共有ＤＲＡＭ２１４の間で通信を可能にするように、追加的なデータバス２１６が提供されることが好ましい。一つまたは複数の入出力（Ｉ／Ｏ）インタフェース２０２Ａ、２０２Ｂおよび外部バス（図示せず）は、ＢＥ２９０と任意の外部要素の間の通信を提供する。ＢＥ２９０中のＰＥ２００Ａ、２００Ｂは、それぞれ、図３に関して上述したサブ処理ユニット２０８によって実行される並列で独立したアプリケーションおよびデータの処理に類似の並列で独立の態様で、データおよびアプリケーションの処理を実行する。本発明の様々な態様によれば、ＢＥは単一のＰＥを備えていても多数のＰＥを備えていてもよい。さらに、ＢＥ自体が複数のＢＥを含むことで構成されてもよい。

図３１を参照する。ここで、基本構成単位としてスタンドアロン型のＳＰＵ２０８、ＰＥ２００、または複数のＰＥのセットであるＢＥ２９０が複数の製品に分散されて、マルチプロセッサシステム５００を形成してもよい。コンピュータおよび／またはコンピューティングデバイスとして実装された、システム５００の要素またはメンバは、ネットワーク５０４を介して通信することが好ましい。ネットワーク５０４は、ローカルエリアネットワーク（ＬＡＮ）であっても、インターネットや他の任意のコンピュータネットワークのような大域的ネットワークであってもよい。

例えば、ネットワーク５０４に接続されたメンバは、例えば、クライアントコンピュータ５０６、サーバコンピュータ５０８、個人携帯情報機器（ＰＤＡ）５１０、デジタルテレビ（ＤＴＶ）５１２、または、そのほかの有線または無線ワイヤレスコンピュータおよびコンピューティングデバイスを含む。例えば、クライアント５０６Ａは、一つまたは複数のＰＥ２００、または他の適切なマルチプロセッサシステムから構成されるラップトップコンピュータであってもよい。クライアント５０６Ｂは、一つまたは複数のＰＥ２００、または他の適切なマルチプロセッサシステムから構成されるデスクトップコンピュータ（またはセットトップボックス）であってもよい。さらに、サーバ５０８Ａはデータベース機能を使用した管理要素（administrative entity）であってもよく、これは一つまたは複数のＰＥ２００から好ましくは構成される。

したがって、マルチプロセッサシステム５００の処理能力は、ローカルに（例えば、一つの製品に）またはリモートに（例えば複数の製品に）配置された複数のＰＥ２００に依存してもよい。この点に関して、図３０は、本発明の一つまたは複数の態様による全体的なコンピュータネットワークのブロック図である。ＰＥ２００および／または多数のＰＥからなるＢＥ２９０は、コンピュータシステム５００の全体的な分散アーキテクチャを実装するために利用することができる。

システム５００のサーバ５０８がクライアント５０６より多くのデータおよびアプリケーションの処理を実行するので、サーバ５０８は、クライアント５０６より多くのコンピュータモジュール（例えばＰＥ２００）を含む。他方、ＰＤＡ５１０は、この実施例において最小の処理量を実行する。したがって、ＰＤＡ５１０は、単一のＰＥ２００のように最小数のＰＥ２００を含む。ＤＴＶ５１２は、実質的にクライアント５０６とサーバ５０８の間の処理レベルを実行する。したがって、ＤＴＶ５１２は、クライアント５０６のＰＥとサーバ５０８のＰＥの間の数のＰＥを含む。

分散マルチプロセッサシステム５００に関して、さらに詳細に述べる。システム５００の均質的な構成は、適応性、処理速度、処理効率を促進する。システム５００の各メンバが同一のコンピューティングモジュール、例えばＰＥ２００の一つまたは複数（またはその一部）を使用して処理を実行するので、データおよびアプリケーションの処理がネットワークメンバで共有されてもよいため、データおよび／またはアプリケーションの処理を実行するコンピュータおよびコンピューティングデバイスの特定は、重要でない。システム５００により処理されるデータおよびアプリケーションを含むセルアプリケーションを固有に識別することによって、処理が発生した場所にかかわらず、その処理を要求するコンピュータまたはコンピューティングデバイスに処理結果を送信することができる。処理を実行するモジュールが共通の構造を有し、共通の命令セットアーキテクチャを使用するので、プロセッサ間の互換性を得るための追加ソフトウェアレイヤによる計算負荷が省かれる。このアーキテクチャおよびプログラミングモデルは、例えば、リアルタイムでマルチメディアのアプリケーションを実行するのに必要な処理速度を促進する。

システム５００により促進される処理速度および処理効率のさらなる利点を得るために、このシステムにより処理されるデータおよびアプリケーションは、固有に識別され一様にフォーマット化されたセルアプリケーション５０２にパッケージングされてもよい。各セルアプリケーション５０２は、アプリケーションおよびデータの両方を含み、または含んでもよい。後述するように、各セルアプリケーションはまた、ネットワーク５０４およびシステム５００の全体にわたってセルを識別するためのＩＤを含む。

セルアプリケーションの構造の均質性、およびネットワーク全体にわたるセルアプリケーションの一様な識別により、ネットワーク５０４の任意のコンピュータまたはコンピューティングデバイス上でのアプリケーションおよびデータの処理が容易になる。例えば、クライアント５０６がセルアプリケーション５０２を実行してもよいが、クライアント５０６の処理能力が限られているため、セルアプリケーション５０２を処理のためにサーバ５０８に送信してもよい。したがって、セルアプリケーション５０２は、ネットワーク５０４上の処理リソースの利用可能性に基づいて、ネットワーク５０４の全体にわたって移動することができる。

システム５００のプロセッサおよびセルアプリケーション５０２の均質的な構造により、今日の異機種間ネットワークの課題の多くが回避される。任意の命令セット、例えばＪａｖａ仮想マシン（Ｊａｖａは登録商標）のような仮想マシンを使用して、任意のＩＳＡでのアプリケーションの処理を可能にしようとする非効率的なプログラムモジュールが回避される。したがって、システム５００は、従来のネットワークより効果的にまた効率的に、ブロードバンド処理を実行することができる。

本発明の方法の一態様によると、第１のマルチプロセッサ（便宜上、例えば第１のＢＥとする）は、様々な理由のうち任意のもののために、第１のＢＥからタスクを移動するべきか否かを決定する。例えば、第１のＢＥは、指定されたデッドラインまたは合理的な期間内にタスクを終了するにはビジーであるという判定をしてもよい。第１のＢＥが、別の処理システムにタスクを移動すべきであると判定すると、第１のＢＥからネットワークを介してアプリケーションをブロードキャストする。アプリケーションは、複数のタスクと一つの属性とを指定するかまたは含む。移動されることになるタスクは、指定されたタスクまたは含まれているタスクのうちの一つである。属性は、アプリケーションをブロードキャストした前段のＢＥ、もしくは初めにアプリケーションをブロードキャストしたＢＥ、のうち少なくとも一つからのアプリケーションの距離と、複数のタスクのそれぞれを終了するためのデッドラインと、を表示することが好ましい。タスクキューを指定することもできる。アプリケーションは、アプリケーション自身がタスクを保有することによって複数のタスクを直接指定してもよいし、または、アプリケーションがポインタ情報を使用して間接的にタスクを指定してもよい。ポインタ情報は、例えばポインタ、インデックスまたは他の同等手法であり、タスクの位置する場所を表すか指し示すものである。あるいは、タスクキュー、各タスク、およびアプリケーション内の属性と組み合わされたタスクのブロックのうちのいずれか一つと、属性とがリンク付けされていてもよい。さらに、本発明の態様によると、タスクは、タスクを実行するための要件を指定する属性を有している。属性は、二つ以上のタスクで共通であるか、または全てのタスクで共通であってもよい。または、タスクのそれぞれが固有の独立した属性を有していてもよい。

アプリケーションの「距離」とは、転送レイテンシの尺度となりうる物理的距離のことをいう場合もあるが、好適には、ネットワークを越えて別の位置またはプロセッサにアプリケーションを移動する際の、ネットワークレイテンシのことを指す。

例えば、送信元すなわち「オーナーＢＥ」は、アプリケーションＡの移動を決定し、ネットワークにアプリケーションＡをブロードキャストする。アプリケーションＡは、デッドラインと、必要となる計算リソース（例えば、ＳＰＵの数または複数のタスク）と、他のパラメータとを有している。別のセルである第１のＢＥは、アプリケーションＡを受け取り、パラメータとオーナーＢＥへの「距離」とをチェックする。いくつかの理由により、第１のＢＥがアプリケーションＡを処理しないと決定し、アプリケーションＡをネットワークに戻してブロードキャストする。この場合、アプリケーションＡの距離は、依然として、潜在的な新たなＢＥからオーナーＢＥへのネットワークレイテンシである。今度は、第２のＢＥがアプリケーションＡを受け取り、パラメータとオーナーＢＥへの距離とをチェックする。この情報に基づいて、第２のＢＥはアプリケーションＡの結果をオーナーＢＥへと戻してもよい。

あるいは、「距離」は、送信元すなわちオーナーＢＥでなく、直前のＢＥからの距離であってもよい。例えば、オーナーＢＥが、アプリケーションＡをネットワーク上に移動させると決定したとする。アプリケーションＡは、デッドラインと、必要となる計算リソース（例えば、ＳＰＵの数または複数のタスク）と、他のパラメータとを有している。第１のＢＥは、アプリケーションＡを受け取り、パラメータとオーナーＢＥへの距離とをチェックする。いくつかの理由により、第１のＢＥがアプリケーションＡの一部を「Ａ’」として移動させると決定し、Ａ’をネットワークにブロードキャストする。この場合、Ａ’の距離は、潜在的な新たなＢＥから第１のＢＥへのネットワークレイテンシである。Ａ’のデッドラインは、アプリケーションＡよりも早い。第２のＢＥがＡ’を受け取り、パラメータと第１のＢＥへの距離とをチェックする。第２のＢＥは、Ａ’の結果を第１のＢＥへと戻してもよい。第１のＢＥは、Ａ’を有するアプリケーションＡの結果を生成し、その結果をオーナーＢＥへと戻してもよい。

属性は、タスクの実行に要求される処理能力を指定することが好ましい。したがって、上述のプロセッサアーキテクチャが使用される場合、この属性は、タスクの実行に必要なＳＰＵの数を指定してもよい。さらに、同じ属性または異なる属性が、タスクの実行に必要とされるメモリの量を指定してもよい。

第１のＢＥによってブロードキャストされたアプリケーションは、ネットワークにより第１のＢＥに接続される第２のＢＥで受け取られる。第２のＢＥは、アプリケーション内のタスクを分解し（unbundle）、いずれのタスクを第１のＢＥから移動させるべきかについて決定する。タスクをばらし移動させるべきタスクを決定した後、第２のＢＥは、好適には、ソフトウェアコマンドにより、タスクを実行するための要件を指定する属性を調べ、第２のＢＥによって実行されなければならないタスクを決定する。上述したように、属性（または、複数の属性）が必要な処理能力および必要なメモリを記述する場合、好適には第２のＢＥは、移動されるタスクに関連付けられている必要な処理能力および必要なメモリを検査する。

本発明の別の態様によると、第２のＢＥもまた、アプリケーションをブロードキャストした前段のＢＥ、または、初めにアプリケーションをブロードキャストしたＢＥ、のうちの少なくとも一つからのアプリケーションの距離と、複数のタスクのそれぞれを終了するためのデッドラインと、複数のタスクのそれぞれを終了するためのデッドラインとを調べる。そして、その複数のタスクを第２のＢＥで実行すべきか否かを決定する。第２のＢＥは、第１のＢＥに対して、第２のＢＥがタスク（単数または複数）を実行しているか否かを連絡することが好ましい。

本発明の別の態様によると、ブロードキャストされたアプリケーションは、複数の他のＢＥによって受け取られる。複数の他のＢＥはそれぞれ、第２のＢＥに関して先に述べたステップを実行する。したがって、他のＢＥはそれぞれ、アプリケーション内のタスク（単数または複数）を分解する。移動されるべきタスク（単数または複数）は、アプリケーション内に含まれる。複数の他のＢＥはそれぞれ、複数のタスクを実行するための要件を指定する属性を調べて、タスクが実行されるべきか否かを決定する。さらに、複数の他のＢＥはそれぞれ、アプリケーションをブロードキャストした前段のＢＥ、もしくは初めにアプリケーションをブロードキャストしたＢＥ、のうち少なくとも一つからのアプリケーションの距離と、複数のタスクのそれぞれを終了するためのデッドラインと、を調べて、タスクが実行されるべきか否かを決定する。

上記説明においては、第１のマルチプロセッサとして第１のＢＥ、第２のマルチプロセッサとして第２のＢＥを便宜上定めた。しかし、当然であるが、第１のマルチプロセッサおよび第２のマルチプロセッサはそれぞれ、図３２に示した要素のいずれであってもよい。したがって、一例として、第１のマルチプロセッサはクライアント５０６のうちの一つであってもよいし、第２のマルチプロセッサはクライアント５０６のうちの別の一つまたはＰＤＡ５１０であってもよい。図３２中では、ネットワーク５０４上を複数のセル５０２が移動している状態が示されているが、このセル５０２がこれまでの説明でＢＥ間で転送またはブロードキャストされるとしたアプリケーションである。例えば、クライアント５０６内には複数の「セル」が描かれているが、これはクライアント５０６内の複数のＢＥまたはＰＥにおいて、セルアプリケーションが実行されているイメージを表したものである。クライアント５０６の他に、サーバ５０８内にも「セル」が描かれているが、これは必ずしもサーバやクライアント内のＢＥまたはＰＥが「セル」を実行中であるイメージを表しているわけではなく、「セル」を実行可能であることを示しているに過ぎない。各ＰＥは、複数のＳＰＵを持つ図３に示したようなアーキテクチャを有してもよい。しかしながら、本発明は、プロセッサのタイプまたはアーキテクチャにかかわらず、複数のネットワーク化されたプロセッサを有する任意のシステムに適用可能であることが理解される。

この点に関して、図３３は本発明のセルサーバ６００の一実施形態を示す。一つまたは複数の広帯域エンジン（ＢＥ）６１０は、セルサーバによって管理される。各ＢＥは、上述の環境と同じく、処理ユニット（ＰＵ）６３０、複数の相乗的（synergistic）処理ユニット（ＳＰＵ）６４０、有利には（図４に示す）複数のＳＰＵのそれぞれに関連するローカルメモリ用の論理記憶装置（ＬＳ）（ＤＭＡＣ６５０を介してアクセスされる）を備える基本プロセッサ要素（ＰＥ）６２０と、共有メモリ６６０とを備える。ＢＥは、ＢＥバス６７０およびＢＥ入出力チャネル６７５を介して内部通信する。加えて、セルサーバは、一つまたは複数のネットワークインタフェース６８０を有する。ネットワークインタフェースは、有利には、各ＰＵまたはＳＰＵに関連付けられているが、セルサーバに直接関連付けられていてもよい。有利には、セルサーバ６００は、内部通信用のセルバス６９０とローカルセル入出力チャネル６９５とを備える。

ＢＥの一実施形態の汎用メモリハンドリング特性の詳細は、２００１年３月２２日に出願された「SYSTEM AND METHOD FOR DATA SYNCHRONIZATION FOR A COMPUTER ARCHITECTURE FOR BROADBAND NETWORKS」と題する米国特許出願第０９／８１５，５５４号に説明されており、これは本出願の譲受人に譲渡されている。ネットワーク化されたマルチプロセッサ環境におけるＢＥの基本的な相互接続の一実施形態の説明は、２００４年４月２２日に出願された「METHOD AND APPARATUS FOR PROVIDING AN INTERCONNECTION NETWORK FUNCTION」と題する米国仮特許出願第６０／５６４，６４７号に説明されており、これは本出願の譲受人に譲渡されている。

各ＢＥは、図３４の一実施形態に模式的に示すように、一つまたは複数のＢＥタスク７００を含む。ＢＥタスク７００は、タスクキュー７１０および関連するタスクテーブル７２０ａ〜７２０ｄを利用して、セルサーバの共有メモリ内に編成されることが好ましい。タスクテーブル７２０ａ〜７２０ｄは、それぞれタスクテーブルエントリのセットを備え（図３５を参照）、タスクテーブルは、一つまたは複数のＳＰＵによって実行されるべき一つまたは複数のＳＰＵタスクを有する（図３５を参照）。ＢＥタスクは、固有のＢＥタスク識別子７３０を有することが好ましい。

加えて、各ＢＥタスクは、少なくとも以下の４つのパラメータを有することが好ましい。すなわち、ＢＥタスクまたはタスクグループを実行するために必要となる最小のＳＰＵ数（最小必要ＳＰＵ７３０ａ）、ＢＥタスクまたはタスクグループによって要求されるメモリサイズ（メモリ割り当て７３０ｂ）、セルレイテンシすなわちこのＢＥを所有するセルサーバと受取り側ＢＥとの間の距離（セルレイテンシ７３０ｃ）、およびＢＥタスクに含まれるＳＰＵタスクのタスクデッドライン（タスクデッドライン７３０ｄ）である。ＢＥタスクは、セルサーバネットワークによって要求される他の値（７３０ｅ）も含むことが好ましい。ＢＥタスクの一例を表１に示す。

図３５は、本発明のタスクテーブルの一実施形態を示す。上述したように、各タスクテーブル７４０は、以下のパラメータのうち一つまたは複数を保持するテーブルエントリ７５０のセットを含む。すなわち、タスクステータス７６０ａ、タスク優先度７６０ｂ、他のタスクテーブル値７６０ｃ、前のタスクへのポインタ７８０、および次のタスクへのポインタ７９０である。各タスクテーブル７４０は、実行されるべき実際の命令に対する命令ポインタ７７０を有してもよい。

タスクステータス７６０ａは、タスクの状態、例えば、タスクが実行中、準備、待機、待機中断、中断、休止、不在のいずれかを表す。タスク優先度７６０ｂは、タスクのレベルまたは重要度を表し、スケジューリング中にタスクの実行順序を決定するために使用される。前のタスクポインタ７８０および次のタスクポインタ７９０は、他のテーブルエントリ７５０に関連して使用され、タスクテーブル７４０内のリンク付きリストを形成する。前のタスクポインタ７８０および次のタスクポインタ７９０もまた、ＰＵおよびＳＰＵへのタスクテーブルの処理タスクの順序づけされたアクセスを提供する。

図３６は、本発明のＢＥタスクキューの一実施形態を示す。各タスクキュー７１０は、複数のタスク優先度レベル８２０のそれぞれについての、ヘッドエントリポインタ８００とテイルエントリポインタ８１０のセットを含む。具体的には、タスクキュー７１０は、セルサーバ上でＢＥでのタスク命令の実行を優先順位付けするために提供される、ｎ優先度レベル（０からｎ−１）のそれぞれについて別個にヘッドエントリとテイルエントリの対を有する。一般に、優先度レベルと同じ数のリンク付きリストが存在する。したがって、各優先度レベルについて、その優先度レベルでのタスクのリンク付きリスト８３０は、その優先度のタスクテーブル７４０内の第１のタスクエントリ８４５をポイントするヘッドポインタ８４０と、その優先度のタスクテーブル内の最後のタスクエントリ８５５をポイントするテイルポインタ８５０とに関連付けられている。タスクキュー７１０の一実施例を表２に示す。

ＰＵおよび／またはＳＰＵは、ＢＥタスクキューおよび関連するＢＥタスクテーブルを使用して、タスク処理のスケジューリングを実行する。具体的には、共有メモリから引き抜かれたプロセスタスクを実行のためにＳＰＵの一つに入れる順序を決定する。セルサーバ内の各ＢＥは、少なくとも一つのタスクキューと、関連するタスクテーブルとを維持することが好ましい。

各ＢＥについてのタスクキューおよびタスクテーブルは、同一セルサーバ内での一つのＢＥから別のＢＥへのプロセッサタスクの移動、または、ネットワークを介して接続された別個のセルサーバでの一つのＢＥから別のＢＥへのプロセッサタスクの移動を容易にする。別のＢＥに実行のために渡されるべきプロセッサタスクは、移動のためにアプリケーション内にバンドルされる（bundle）。一般に、アプリケーションは、以下に詳細に述べるように、他の情報でラップされた一つまたは複数のＢＥタスクを含む。特定のＢＥを管理するセルサーバは、一般に、そのＢＥのアプリケーションオーナーとみなされる。

図３７は、移動のためにアプリケーションをバンドルする方法の一実施形態を示す。一般に、例えば、他の状況と同じく、ＢＥ内（または、セルサーバの特定のＳＰＵ内）のプロセッサロードが高いとき、または、特定のＳＰＵ内で優先度の衝突が発生したとき、特定のセルサーバ内のＢＥが、一つまたは複数のＢＥタスクのセットを含むアプリケーションを別のＢＥへ移動する。特に、移動のためのアプリケーションのバンドリングは、送出し側ＢＥによって処理されるステッププロセスを伴う。

通常のタスク処理状態９００の間、移動判定ステップ９１０において、例えば高いプロセッサロード、低いメモリ利用可能性などのために、ＢＥは、タスクの移動が必要であるか否かを判定する。移動が必要な場合、停止タスクステップ９２０において、現在実行中のタスク７００が停止される。タスク更新ステップ９３０において、バンドリングの準備のために、送出し側ＢＥの現在のタスクキュー７１０およびタスクテーブル７２０が更新される。バンドルステップ９５０において、移動されるべきＢＥタスクが移動のためにアプリケーション９４０にバンドルされる。好適には、セル９４０は、（タスクキュー７１０とタスクテーブル７２０の情報を含む）移動されるべきＢＥタスク７００のみならず、ＢＥタスクに関連するタスクデータ９５２も含む。有利には、アプリケーションは、必要に応じて、アプリケーションセキュリティを保証し、アプリケーション整合性を確認するために、圧縮されるか最小アプリケーションサイズに暗号化されてもよい。続いて、図３８に詳細を示すポーリング−応答−移動−復帰プロセスを介する移動ステップ９６０によって、タスクが別のＢＥに移動される。移動プロセス（および、移動されたプロセスの復帰）が完了すると、ＢＥは、通常のタスク処理状態９００を介してタスクの処理の継続に復帰する。

図３８は、送出し側ＢＥから、既知のセルサーバネットワーク上のいずれかにある受取り側ＢＥへのＢＥタスクの移動プロセスの一実施形態を示す。図３７のバンドルステップ９５０において述べたように、移動されるべきＢＥタスクがバンドルされた後、ＢＥは、ポーリングステップ９７０において他のＢＥをポーリングする。好適には、ＢＥは、一つまたは複数のセルサーバネットワーク９７４上で、同一のセルサーバ６００および他の既知のセルサーバ９７２の双方にある、他のＢＥ６１０をポーリングする。

好適には、ポーリングステップ９７０は、図３９に示す既知のセルサーバネットワーク上の既知のＢＥに対して、ブロードキャストクエリを介して実行される。一実施形態では、ブロードキャストクエリメッセージ９８０は、複数の値を含むネットワークメッセージの形態をとる。値には、送信元セルサーバおよびＢＥの表示９８５ａ、移動されるべきタスクのタスク優先度の表示９８５ｂ、必要なＳＰＵおよび／またはメモリリソースの表示９８５ｃ、移動中のタスクのタスクデッドラインの表示９８５ｄ、および、ブロードキャストクエリによって送信されることが有利な他の任意の値９８５ｅが含まれるが、これらに限定されない。これらの値は、バンドルされたアプリケーションの一部であるタスクテーブル内に格納される。これらの値は、必要に応じて、他のデータ構造で記載されてもよい。

図３８に戻り、クエリ応答受信ステップ９９０において、送出しセルサーバ内の送出し側ＢＥは、セルサーバネットワーク内の既知のＢＥから一つまたは複数の応答を受け取る。図４０に示すように、好適には、クエリ応答は、特定の値を含むネットワークメッセージの形態をとる。特定の値には、応答ＢＥおよびセルサーバロケーションの表示１００５ａ、応答ＢＥの現在のタスクデッドラインの表示１００５ｂ、現在のＢＥの空きＳＰＵ、プロセッサロード、および／またはメモリ負荷の表示１００５ｃ、クエリ応答１０００内で必要とされるか要求されるかまたは含まれる任意の他のブロードキャスト応答メッセージ値１００５ｄが含まれるが、これらに限定されない。

再び図３８に戻り、受取り側ＢＥ選択ステップ１０１０において、送出し側ＢＥは、受け取ったクエリ応答１０００から、応答ＢＥの移動タスクのうちいずれのセットを送信すべきかを決定する。この選択は、セルレイテンシの短さもしくは受取り側ＢＥと送出し側ＢＥ間のネットワークトポロジ構造上の短さ、受取り側ＢＥにおいて現在実行しているタスクのデッドラインまでの時間の短さ、受取り側ＢＥにおけるＳＰＵおよびメモリの利用可能性が十分かどうか、の一部または全てを考慮に入れた決定に基づくことが好ましい。移動ステップ１０２０において、アプリケーション９４０内のバンドルされたタスクは、選択された受取り側ＢＥ１０３０に移動される。

アプリケーション９４０が受取り側ＢＥに送信されると、受取り側ＢＥタスクアンバンドルステップ１０４０において、有利には、受取り側ＢＥ１０３０は、共有メモリ内のアプリケーションをばらして処理する。受取り側ＢＥタスク処理ステップ１０５０において、受取り側ＢＥ１０３０は、バンドルされたタスク、データ、タスクキュー、およびタスクテーブルにアクセスして、移動された処理タスクを実行する。

ステップ１０５０において、移動されたタスクの処理が受取り側ＢＥによって完了すると、受取り側ＢＥ再バンドルステップ１０６０において、完了したタスク、データ、タスクキュー、およびタスクテーブルがアプリケーションに再バンドルされ、送信元の送出し側ＢＥ、典型的には始めに移動されたＢＥタスクを所有するセルサーバに戻される。送出し側ＢＥ終了タスク受信ステップ１０７０において、終了したタスクが元の送出し側ＢＥによって受け取られると、タスクアンバンドルステップ１０８０において、送出し側ＢＥは終了ＢＥタスクをばらす。続いて、終了タスク更新ステップ１０９０において、終了したＢＥタスクが関連するプロセスを更新し、一般のタスク処理状態９００を再開する。有利には、メッセージ９８０、１０００、アプリケーション６００、およびタスクデータ９５２等の他の重要なデータは、例えばＡＥＳ標準、Ｂｌｏｗｆｉｓｈ、または、ＲＳＡベースの公開鍵暗号化アルゴリズム等の既知のアルゴリズムによって暗号化されてもよい。同様に、本発明のメッセージ、データ構造および他の特徴は、例えばＭＤ５等のダイジェストアルゴリズムによって情報を採取され（fingerprint）、タスク、タスクデータ、およびメッセージが信頼性のないネットワークおよびネットワークプロトコルによって送信されるときに、重要なデータ整合性を保証するようにしてもよい。

図４１は、本発明の安全なサーバランチ（ranch）の一実施形態を示す。このネットワークで相互接続されたセルサーバ１１００は、有利には、サーバランチ１１１０と呼ばれるセルサーバのコミュニティを形成する。好適には、このサーバランチは、例えばインターネットまたはイントラネット等のＩＰ（インターネットプロトコル）ベースのネットワーク等の、トポロジーフリーなネットワーク上で形成される。しかしながら、十分な効率性および信頼性のあるネットワークプロトコルを使用可能である。

無線ネットワーク、安全でないローカルエリアネットワーク、広域エリアネットワーク、組織されたまたはトポロジカルなイントラネットまたはより一般的なインターネット等の他のオープンネットワーク上にサーバランチが存在する場合にセキュリティが重要であるように、有利にはサーバランチは、それが存在する上でのネットワークに関して安全でであってもよい。一実施形態では、安全なサーバランチ内の各セルサーバは公開鍵および個人鍵を使用し、ネットワークを介して分散されるセルサーバは、暗号化モジュール１１２０（一実施形態では、公開鍵暗号化（ＰＫＩ）モジュール）を介してアプリケーションおよび他のメッセージを送信し、受信し、および認証することができる。しかしながら、ＡＥＳベースのハンドシェークまたは圧縮−暗号化技術等の任意のタイプの暗号化アルゴリズムを使用してもよい。既知のネットワーク１１３０の外部のセルサーバは、一般にセルランチに参加可能であるが、適当なタイプの暗号化モジュールおよび適当な認証（すなわち、キーおよび／または署名）を持たない場合は、安全なサーバランチへの参加を控えることが好ましい。

本明細書において特定の実施形態を参照して本発明を記載したが、これらの実施形態が単に本発明の原理および応用を例示するものにすぎないことは理解されよう。したがって、例示した実施形態には多数の変形が可能であり、添付の特許請求の範囲で規定される本発明の精神および範囲から逸脱することなく他の構成を考案することができることが理解されよう。

本発明の一つまたは複数の態様によるマルチプロセッサシステムの構造を示す図である。 共有メモリ内のプロセッサタスクの格納を示すブロック図である。 本発明のプロセッサ要素（ＰＥ）の好適な構造を示す図である。 本発明による例示的なサブ処理ユニット（ＳＰＵ）の構造を示す図である。 本発明の一つまたは複数の態様により使用可能なプロセッサタスクテーブルの一例を示す図である。 図５のタスクテーブルによって設定されるプロセッサタスクのリンク付きリストの状態図である。 図５のタスクテーブルとともに使用してプロセッサタスクの実行を管理することができるタスクキューの一例を示す図である。 本発明の一つまたは複数の態様によるマルチプロセッサシステムによって実行可能なプロセスステップを示すフロー図である。 本発明のマルチプロセッサシステムによって実行可能なプロセスステップを示すフロー図である。 本発明のマルチプロセッサシステムによって実行可能なプロセスステップを示すフロー図である。 共有メモリ内のプロセッサタスクを初期化し、本発明の様々な態様によるマルチプロセッサシステムにより実行可能なプロセスステップを示すフロー図である。 本発明の一つまたは複数の態様による、プロセッサタスクの異なるステータス状態を示す状態図である。 本発明の一つまたは複数の態様による、プロセッサタスクが共有メモリからコピーされ共有メモリに書き戻される方法を示すブロック図である。 図１３のコピーおよび書き戻し技術に関連するレイテンシの処理を示すタイミング図である。 本発明の一つまたは複数の態様による、プロセッサタスクが共有メモリからコピーされ共有メモリに書き戻される方法を示すブロック図である。 図１５のコピーおよび書き戻し技術に関連するレイテンシの処理を示すタイミング図である。 本発明の一つまたは複数の態様による、プロセッサタスクが共有メモリからコピーされ共有メモリに書き戻される方法を示すブロック図である。 図１７のコピーおよび書き戻し技術に関連するレイテンシの処理を示すタイミング図である。 本発明の一つまたは複数の態様による、プロセッサタスクが共有メモリからコピーされ共有メモリに書き戻される方法を示すブロック図である。 本発明の特定の態様のノン・プリエンプティブなプロセッサタスク移動を示すブロック図である。 本発明の特定の態様のノン・プリエンプティブなプロセッサタスク移動を示すブロック図である。 本発明の特定の態様のノン・プリエンプティブなプロセッサタスク移動を示すブロック図である。 本発明の特定の態様のプリエンプティブなマルチタスクを示すブロック図である。 本発明の特定の態様のプリエンプティブなマルチタスクを示すブロック図である。 本発明の特定の態様のプリエンプティブなプロセッサタスク移動を示すブロック図である。 本発明の特定の態様のプリエンプティブなプロセッサタスク移動を示すブロック図である。 本発明の一つまたは複数の態様による特定プロセッサ割り込み技術を示す部分的なブロック図と部分的なフロー図である。 本発明の一つまたは複数の態様によるプロセッサ割り込み技術を示す部分的なブロック図と部分的なフロー図である。 本発明の一つまたは複数の態様によるプロセッサ割り込み技術を示す部分的なブロック図と部分的なフロー図である。 本発明の一つまたは複数の態様による二つ以上のサブ処理ユニットを含む処理システムの構造を示す図である。 本発明の一つまたは複数の態様による分散マルチプロセッサシステムのシステム図である。 本発明のマルチプロセッサユニットと共に使用可能なセルアプリケーションのブロック図である。 本発明の一実施形態を示すシステム図である。 本発明の広帯域エンジンタスクの一実施形態を示すブロック図である。 本発明のタスクテーブルおよびタスクエントリの一実施形態を示すブロック図である。 本発明のタスクキューの一実施形態を示すブロック図である。 本発明のアプリケーションのバンドリングの一実施形態を示す部分的なフロー図である。 本発明のタスク移動の一実施形態を示す部分的なフロー図である。 本発明のブロードキャストクエリメッセージの一実施形態を示すブロック図である。 本発明のクエリ応答メッセージの一実施形態を示すブロック図である。 本発明の安全なセルランチの一実施形態を示すシステム図である。

符号の説明

６００ セルサーバ、 ６１０ ＢＥ、 ６５０ ＤＭＡＣ、 ６６０ 共有メモリ、 ６７０ ＢＥバス、 ６７５ ＢＥ入出力チャネル、 ６８０ ネットワークインタフェース、 ６９０ セルバス、 ６９５ ローカルセル入出力チャネル。

Claims (19)

1. 一つのマルチプロセッサから少なくとも一つのマルチプロセッサに対してネットワークを介してタスクを移動するデータ処理方法であって、
   一つのマルチプロセッサから少なくとも一つのマルチプロセッサにタスクを移動すべきか否かを決定し、
   少なくとも一つのマルチプロセッサにタスクを移動すべきと決定されたとき、マルチプロセッサのうちの一つからアプリケーションをブロードキャストすることを含み、
   前記アプリケーションは複数のタスクと一つの属性とを指定し、前記属性は、アプリケーションをブロードキャストした前段のマルチプロセッサからのアプリケーションの距離と、複数のタスクのそれぞれを終了するためのデッドラインと、を表しており、
   ブロードキャストされたアプリケーションを第２のマルチプロセッサで受け取り、
   第２のマルチプロセッサが前記アプリケーションで指定された複数のタスクをばらし、前記アプリケーションの距離および前記デッドラインを調査し、前記アプリケーションのうち一部のタスクを別のマルチプロセッサへと移動させるか否かを決定し、該アプリケーションの一部のタスクをネットワークにブロードキャストすることをさらに含むことを特徴とするデータ処理方法。
2. 前記属性は、タスクの実行に必要な処理能力をさらに指定し、
   前記第２のマルチプロセッサは、前記処理能力を調査して前記アプリケーションのうち一部のタスクを別のマルチプロセッサへと移動させるか否かを決定することを特徴とする請求項１に記載のデータ処理方法。
3. 前記属性は、タスクのを実行に必要なメモリサイズをさらに指定し、
   前記第２のマルチプロセッサは、前記必要なメモリをさらに調査して前記アプリケーションのうち一部のタスクを別のマルチプロセッサへと移動させるか否かを決定することを特徴とする請求項１に記載のデータ処理方法。
4. 前記アプリケーションは、タスクの位置する場所を示すポインタ情報によって前記複数のタスクを指定することを特徴とする請求項１ないし３のいずれかに記載のデータ処理方法。
5. 前記属性は、前記タスクを実行するための要件を指定し、
   前記第２のマルチプロセッサは、前記タスクを実行するための要件を調査して前記アプリケーションのうち一部のタスクを別のマルチプロセッサへと移動させるか否かを決定することを特徴とする請求項１に記載のデータ処理方法。
6. 第２のマルチプロセッサがタスクを実行しているか否かを、該第２のマルチプロセッサが第１のマルチプロセッサに連絡することをさらに含むことを特徴とする請求項１、２、３または５のいずれかに記載のデータ処理方法。
7. 前記第２のマルチプロセッサからブロードキャストされたアプリケーションを複数の他のマルチプロセッサで受け取り、
   前記アプリケーションで指定されたタスクを複数の他のマルチプロセッサのそれぞれでばらし、
   複数の他のマルチプロセッサのそれぞれにおいて、タスクを実行するための要件を指定する属性を調査して、当該タスクを実行すべきか否かを決定することをさらに含むことを特徴とする請求項５に記載のデータ処理方法。
8. 複数の他のマルチプロセッサがそれぞれ、アプリケーションをブロードキャストした前段のマルチプロセッサからのアプリケーションの距離と、複数のタスクを終了するためのデッドラインと、を調べて、当該タスクを複数の他のマルチプロセッサのそれぞれが実行すべきか否かを決定することを特徴とする請求項７に記載のデータ処理方法。
9. タスクが実行されているか否かを、複数の他のマルチプロセッサが第１のマルチプロセッサに連絡することを特徴とする請求項７に記載のデータ処理方法。
10. タスクを移動させるデータ処理システムであって、
    ネットワークと、
    前記ネットワークに接続された複数のマルチプロセッサと、
    一つのマルチプロセッサから少なくとも一つのマルチプロセッサにタスクを移動すべきか否かを決定する手段と、
    少なくとも一つのマルチプロセッサにタスクを移動すべきと決定されたとき、マルチプロセッサの一つからネットワークを介してアプリケーションをブロードキャストする手段と、を備え、
    前記アプリケーションは複数のタスクと一つの属性とを指定し、前記属性は、アプリケーションをブロードキャストした前段のマルチプロセッサからのアプリケーションの距離と、複数のタスクのそれぞれを終了するためのデッドラインと、を表し、
    ブロードキャストされたアプリケーションを第２のマルチプロセッサで受け取る手段と、
    第２のマルチプロセッサにおいて前記アプリケーションで指定された複数のタスクをばらす手段と、
    第２のマルチプロセッサにおいて、前記アプリケーションの距離および前記デッドラインを調査し、前記アプリケーションのうち一部のタスクをさらに別のマルチプロセッサへと移動させるか否かを決定する手段と、
    前記アプリケーションの一部のタスクをネットワークにブロードキャストする手段と、
    をさらに備えることを特徴とするデータ処理システム。
11. 前記属性は、タスクの実行に必要な処理能力をさらに指定し、
    前記第２のマルチプロセッサは、前記処理能力を調査して前記アプリケーションのうち一部のタスクをさらに別のマルチプロセッサへと移動させるか否かを決定することを特徴とする請求項１０に記載のデータ処理システム。
12. 前記属性は、タスクの実行に必要なメモリサイズを指定し、
    前記第２のマルチプロセッサは、前記必要なメモリサイズを調査して前記アプリケーションのうち一部のタスクをさらに別のマルチプロセッサへと移動させるか否かを決定することを特徴とする請求項１１に記載のデータ処理システム。
13. 前記アプリケーションは、タスクの位置する場所を示すポインタ情報によって前記複数のタスクを指定することを特徴とする請求項１０ないし１２のいずれかに記載のデータ処理システム。
14. 前記属性は、前記タスクを実行するための要件を指定し、
    前記第２のマルチプロセッサは、前記タスクを実行するための要件を調査して前記アプリケーションのうち一部のタスクをさらに別のマルチプロセッサへと移動させるか否かを決定することを特徴とする請求項１０に記載のデータ処理システム。
15. 前記第２のマルチプロセッサからブロードキャストされたアプリケーションを複数の他のマルチプロセッサで受け取る手段と、
    前記アプリケーション内のタスクを複数の他のマルチプロセッサのそれぞれでばらす手段と、
    複数の他のマルチプロセッサのそれぞれにおいて、タスクを実行するための要件を指定する属性を調査して、当該タスクを実行すべきか否かを決定する手段と、
    をさらに備えることを特徴とする請求項１４に記載のデータ処理システム。
16. 複数の他のマルチプロセッサのそれぞれは、アプリケーションをブロードキャストした前段のマルチプロセッサ、もしくは初めにアプリケーションをブロードキャストしたマルチプロセッサ、のうち少なくとも一つからのアプリケーションの距離と、複数のタスクのそれぞれを終了するためのデッドラインと、を調べて、当該タスクを実行すべきか否かを決定する手段を備えることを特徴とする請求項１５に記載のデータ処理システム。
17. 複数の他のマルチプロセッサは、タスクが実行されているか否かを第１のマルチプロセッサに連絡する手段を備えることを特徴とする請求項１５に記載のデータ処理システム。
18. 前記第２のマルチプロセッサは、第２のマルチプロセッサがタスクを実行しているか否かを第１のマルチプロセッサに連絡する手段をさらに備えることを特徴とする請求項１０、１１、１２または１４のいずれかに記載のデータ処理システム。
19. タスクを移動するためのデータ処理装置であって、
    ネットワークに接続可能なマルチプロセッサであって、該マルチプロセッサによってタスクを実行すべきか、またはネットワークに接続された少なくとも一つのマルチプロセッサに移動すべきかを決定するようにプログラムされたマルチプロセッサを備え、
    前記マルチプロセッサは、少なくとも一つのマルチプロセッサにタスクを移動すべきと決定されたとき、ネットワークを介して当該マルチプロセッサからアプリケーションをブロードキャストするよう指示し、
    前記アプリケーションは複数のタスクと一つの属性とを指定し、前記属性は、アプリケーションをブロードキャストした前段のマルチプロセッサからのアプリケーションの距離と、複数のタスクのそれぞれを終了するためのデッドラインと、を表し、
    ブロードキャストされたアプリケーションを第２のマルチプロセッサで受け取り、
    第２のマルチプロセッサが前記アプリケーションで指定された複数のタスクをばらし、前記アプリケーションの距離および前記デッドラインを調査し、前記アプリケーションのうち一部のタスクを別のマルチプロセッサへと移動させるか否かを決定し、該アプリケーションの一部のタスクをネットワークにブロードキャストすることを特徴とするデータ処理装置。

Images