[0001]【発明の属する技術分野】本発明はパラレル(並列)プロセッサによって実行されるタスクをスケジューリングする方法およびその手段に関し、特に、アサインメント(割当て)マネージャの制御下で複数個の機能ユニットにおけるオペレーションのコンカレント(同時)実行に関する。[0002]【従来の技術】従来技術に係るデータ処理システムにおいては、インストラクションシーケンス(命令列)が一度に一つずつ実行されている。コンピュータの実行速度を増大させる目的で、アルゴリズムにおけるプリミティブなオペレーション、あるいはタスク、の並列処理を実行するマルチプルプロセッサが用いられる。この種の並列化には、シーケンシャルオペレーションの場合よりも実質的により多くの(メモリ)空間が必要とされる。[0003]【発明が解決しようとする課題】数多くの並列プログラミング言語により、個別の機能ユニットにおける並列処理が可能になっている。これらの言語の目的は、ユーザに完全な並列処理を提供し、それら言語に並列処理のプロセッサへのインプリメンテーションをさせることである。program,すなわち、“ワーク”と、依存の最長シーケンス長、すなわち“深さ”(デプス)によって測られる。この種の配置における性能異常は非常に一般的である。インプリメンテーションに用いられた論法は、しばしば失敗する。この種のシステムは、時間と空間の双方の観点から、必ずしもよい性能を提供するとは限らない。performance.【0004】本発明の目的は、この種の方法および手段を改良することである。elements,選択されたタスクの利用可能な並列処理エレメントの個数と等しい数よりなるグループへの分割、および並列処理エレメントにおけるタスクの実行、によって達成される。by.【0006】本発明に係るこれらおよびその他の側面は特許請求の範囲において指摘されている。本発明のその他の目的および利点は、添付図とともに本明細書を読み込むことによって明らかとなる。[0007]【発明の実施の形態】図1は、本発明の実施例を示すブロック図である。ここで、プリプロセッサPP1は、入力されたプログラムを翻訳(コンパイル)し、例えば機械語レベルのインストラクション(命令)などの、実行に適した形態にする。本発明の実施例に従って、プリプロセッサPP1はオプションであり、省略されることも可能である。入力プログラムは、タスクが並列処理によって実行されるべきであることを明らかにするが、それらタスクのプロセッサへの割当て(マッピング)を行わないある種のプログラミング言語の形態を有するあらゆるシーケンシャルプログラムである。このプログラムは、タスクの組およびそれらの間の関係が、プログラムの入力データによって決定され(すなわち入力データに依存し)、それがそのプログラムの入力データの並列処理の間にのみ明らかになるようなものである。AM1は、スケジューリングされることが可能なタスクを決定し、これらのタスクのサブセットを、図2に示されている処理エレメントPE1およびルータRT1を有するシステムSY1に対して割り当てる。detail,割当てマネージャAM1は、それぞれの処理エレメントによって実行されるべき可能なタスクの組を供給する。AM11内のタスクバッファ(図示せず)に対してルーティングする。システムSY1内のそれぞれの処理エレメントPE1は、そのタスクバッファ内のタスクのインストラクションを実行し、タスクが完了した際には割当てマネージャAM1に通知する。is,実行されるべきプログラムタスクがさらに存在する限り、かつ、プログラムが完了していない限り、その機能を継続する。function.【0009】処理エレメントPE1は、並列プログラムのタスクがオペレートする入力データを受信する。その後、処理エレメントPE1はプログラム出力データを出力する。data.【0010】図3は、図2に示されたシステムSY1の別な実施例を示している。PE1の機能は、計算エレメントCEとメモリエレメントMEに分割されている。ルータRT1は、割当てマネージャAM1から、計算エレメントCEとメモリエレメントMEの形態を有する処理エレメントPE1宛にタスクをルーティングする。CEは、ルータRT1を介して、メモリエレメントME(あるいはメモリエレメントMEのサブセットのみ)内のロケーションを読み書きする。ME).【0011】図4は、処理エレメントPE1の詳細を示した図である。RI1が、タスクバッファTB1、プロセッサPR1、およびメモリME1をそれぞれ互いに接続している。AM1B1に配置される。プロセッサPR1がアイドリング状態にある場合には、プロセッサPR1はタスクをタスクバッファTB1から読み出して実行することができる。TB1.【0012】タスク実行の完了に関連して、処理エレメントPE1から割当てマネージャAM1へのフィードバックが存在する。本発明の一実施例に従って、この種のフィードバックは、タスクあるいはタスクの組が完了すると発生する。その後、処理エレメントPE1は割当てマネージャAM1宛にルータRT1を介してアクノレッジ信号を送出する。本発明の別の実施例に従うと、処理エレメントPE1は、アクノレッジ信号を、割当てマネージャによって読み出され得る個別のタスクバッファ宛に出力する。PR1が利用可能なメモリを含んでいる。PE1内に存在するメモリエレメントME1のあるロケーションを読み書きすることが可能である。タスクバッファTB1は、メモリエレメントME1内に存在することも可能であり、また、個別のメモリデバイスであることも可能である。device.【0014】図1に示された割当てマネージャAM1の詳細が図5に示されている。TQ1が、スケジューリング可能なタスクの組(それらのすべてである必要はない)を含んでいる。them1に割り当て、それぞれの処理エレメントPE1に係るタスクバッファTB1中にゼロあるいは複数個のタスクよりなる組を供給する。タスクキューおよびステータスバッファマネージャBM1は、スケジューリング可能なタスクを決定するために、タスクキューTQ1およびステータスバッファSB1を利用する。SB1は、タスク間の関係、例えば完了に際して同期が取られなければならないタスク、に関する必要な情報を有している。PE1を含むシステムSY1から得られたプログラムおよびフィードバック情報を利用する。including.【0016】タスクは、そのタスクの実行の前に完了されなければならない先行タスクが存在しない場合に実行可能である。ある種のタスクは、単一あるいは複数個の先行タスクが完了するまでは実行されることが出来ない。この種のタスクは、先行拘束を有していると言われる。この種のタスクは、それに関連する先行拘束タスクのすべてが完了した時点で実行可能になる。ある種のタスクは、始めから、完了を必要とする先行タスクを有さない。この種のタスクは、スタート時から実行可能である。start.【0017】単一のプロセッサとともに用いられることが企図されたシーケンシャルプログラムは、プログラムのそれぞれのタスクに対してインストラクションシーケンス中でのタスクの順序を識別するコードすなわちキャラクタリゼーションを指定する、シーケンシャルスケジューラを通常利用する。tasks,スケジュール中の順序を識別する表示を有することになる。schedule.【0018】本発明に係る方法は、並列処理が可能なタスクのサブセットを選択する目的で、シーケンシャルスケジューリングにおけるタスクの順序を利用する。本発明に係る方法は、シーケンシャルスケジューリングにおいてより早い時点で可能になったタスクに対してより高いプライオリティを割り当てることによって、並列処理が可能なタスクよりなるサブセットを選択する。tasks.【0019】図6は、図1から図4において示されたシステムのオペレーションを示す流れ図である。ステップ504において、プログラムがプリプロセッサPP1にロードされる。ステップ507において、プリプロセッサPP1は、システム内の特定のエレメントに適するような形態にプログラムを翻訳する。ステップ510においては、割当てマネージャAM1がスケジューリング可能なタスクを決定し、ステップ514において、タスクを、図7および図8に示された流れ図に示されているように、処理エレメントに割り当てる。ステップ517においては、処理エレメントPE1がタスクを実行し、ステップ520において、割当てマネージャAM1がプログラムが完了したか否かを調べる。completed,割当てマネージャAM1はオペレーションを停止する。operations.完了していない場合には、割当てマネージャはオペレーションをステップ510へ戻して続行する。510.【0020】ステップ514の詳細が図7に示されている。AM1は、プログラム中のすべてのタスクに係る、本発明に係る方法の開始時点で予め選択された特定のシーケンシャルスケジューラによって決定された順序に従って、スケジューリング可能なタスクにプライオリティを割り当てる。firsttraversal)スケジューラ等の公知のものである。DFTスケジューラは、以下、“理論”の項で議論される。"theory".シーケンシャルスケジューラは、現時点でスケジューリング可能なタスクに関して機能するのみならず、プログラムの並列実行とは独立なシーケンシャル実行によって決定されるすべてのタスクに対しても機能する。program.【0021】本発明の一実施例に従って、割当てマネージャAM1は、並列にオペレート可能な複数個のプロセッサを有している。別の実施例においては、割当てマネージャAM1は、並列処理を実行する複数個の処理エレメントPE1を用いる。processing.【0022】ステップ607においては、割当てマネージャAM1は、割り当てられた最高のプライオリティを有する可能なタスクのうちからN個のタスクを選択する。ここで、Nは、通常、処理エレメントの個数よりも大きく、また可能なタスクの最大数よりも小さいが、必ずしもそうである必要はない。so.【0023】ステップ610においては、割当てマネージャAM1は、N個の選択されたタスクを、それぞれ(N/p)程度の大きさを有するp個のグループに分割する。ここで、pは利用可能な処理エレメントPE1の個数である。ステップ614においては、割当てマネージャAM1は、それぞれのグループをそれぞれ処理エレメントPE1のうちの一つに割り当てる。PE1.【0024】本発明の一実施例に従って、割当てマネージャAM1は複数個のパラレルプロセッサを有している。604,607、610、および614に示されたそれぞれの機能を、一群の並列処理として実行する。割当てマネージャが複数個のパラレルプロセッサを有していない場合には、それぞれの機能を通常のシーケンスで実行する。sequence.【0025】本発明の別の実施例は、選択されたタスクの数Nが、過剰なメモリを占有してしまうことがない程度な大きさであることを保証するように機能する。この目的のために、ステップ607において選択されるタスクの数Nに対して制限Lが置かれる。割当てマネージャAM1は、タスク群に対して常時利用可能なメモリ、およびこのタスク群に対して予約可能なメモリ、に基づいて、選択されるタスクの数Nに制限Lを指定する。Lの値は利用可能なメモリに従って変化する。制限Lは、プログラムの開始時に指定され入力される。Lとセットされ、処理はステップ610へ進む。M<Lである場合には、処理はステップ610へ進む。610.【0026】図8は、本発明の別の実施例の流れ図であり、割当てマネージャAM1のオペレーションの詳細を示した図である。ステップ704において、割当てマネージャAM1内のタスクキューおよびバッファマネージャBM1(図5)が、最初のプログラムインストラクションを読み取り、プログラムの開始時点で準備が整っているタスクの組を決定する。707,タスクキューおよびバッファマネージャBM1は、これらのタスクの適切な記録を保持するためにステータスバッファSB1を初期化する。710,タスクキューおよびバッファマネージャBM1は、バッファ内のタスクにプライオリティを割り当て、記録に基づいてステータスバッファSB1内に存在するものから高いプライオリティを有する準備が整ったN個のタスクをタスクキューTQ1に配置する。本発明の別の実施例に従うと、プライオリティの割当てはステータスバッファSB1によって実行される。TQ1から削除して、それぞれの処理エレメントPE1に係るタスクバッファTB1にN/p個の相異なったタスクを供給する。本発明のさらに別の実施例に従うと、プライオリティの割当てはタスク割当て器TA1において実行される。ステップ715においては、処理エレメントPE1がタスクを実行する。tasks.【0027】次いで、ステップ717において、タスクキューおよびバッファマネージャBM1に対して、処理エレメントPE1よりなるシステムSY1が、割り当てられたタスクを完了したことを通知する。720においては、タスクキューおよびバッファマネージャBM1がプログラムおよびフィードバック情報を用いてステータスバッファSB1を更新し、新たに準備が整ったタスクの記録を含める。724,タスクキューおよびバッファマネージャBM1が、すべてのタスクが完了したか否かを確認する。完了している場合にはオペレーションが終了し、完了していない場合にはオペレーションはステップ710へ戻る。710.【0028】図9は、ステップ714の別の実施例を示す流れ図である。このステップは、ステップ710に引き続くものである。ステップ750においては、タスク割当て器TA1がタスクキューTQ1からタスクを削除する。本発明の一実施例に従って、タスクに対してはステップ710においてバッファマネージャBM1あるいはタスクキューTQ1によって既にプライオリティが割り当てられており、タスクマネージャTA1は高いプライオリティを有するタスクのみを受信する。task.【0029】本発明の別の実施例に従うと、タスク割当て器TA1はプライオリティを割り当てる。754においては、タスク割当て器TA1が、その複雑さに基づいてタスクに重み付けを行う。ステップ757においては、タスク割当て器TA1は、重み付けに基づいて、選択されたタスクを複数個の利用可能な処理エレメントPE1からなるグループに分け、それぞれのグループの総重み付けすなわち複雑さが、その時点で処理を行うことに係る処理エレメントPE1の能力に適合しているようにする。処理エレメントPE1とその能力が同一である場合には、タスク割当て器TA1は、選択されたタスクを、複数個の利用可能な処理エレメントPE1の間で重みがほぼ等しいようなグループに分割する。ステップ760においては、タスク割当て器TA1は、タスク群をそれぞれの処理エレメントPE1のタスクバッファTB1に供給する。to.【0030】図10は、図5に示されたステータスバッファSB1の実施例を示す図である。RS1およびタスクステータスサポートバッファTSSB1を有している。これらは、図11および13に示された割当てマネージャAM1のオペレーションの実施例において用いられる。13.【0031】図11のステップ904においては、割当てマネージャAM1内のタスクキューおよびバッファマネージャBM1(図5)が初期プログラムインストラクションを読み取り、プログラムの開始時点で準備が整っているタスクの組を決定する。RS1に、および、適切な記録をタスクステータスサポートバッファTSSB1にそれぞれ配置する。TSSB1.【0032】ステップ910においては、タスクキューおよびバッファマネージャBM1が、レディタスクマルチウェイスタックRS1内に存在している最初のN個のタスクをタスクキューTQ1に配置する。910のオペレーションの一部として、タスクキューおよびバッファマネージャBM1はバッファ内のタスクにプライオリティを割り当て、タスクキューTQ1内に、記録に基づいて、ステータスバッファSB1のタスクステータスサポートバッファTSSB1内に存在しているタスクの内から準備が整っておりかつ高いプライオリティを有するタスクをN個配置する。placement.【0033】本発明の別の実施例に従うと、プライオリティの割当ては、ステータスバッファSB1のバッファTSSB1によって実行される。ステップ914においては、タスク割当て器914はタスクキューTQ1からタスクを削除し、それぞれの処理エレメントPE1に係るタスクバッファTB1にN/p個の相異なったタスクを供給する。本発明のさらに別の実施例に従うと、プライオリティの割り当ては、タスク割当て器TA1において発生する。ステップ915においては、処理エレメントPE1がタスクを実行する。tasks.【0034】ステップ917においては、タスクキューおよびバッファマネージャBM1に対して、処理エレメントPM1よりなるシステムSY1が、割り当てられたすべてのタスクが完了したことを通知する。920においては、タスクキューおよびバッファマネージャBM1がプログラムおよびフィードバック情報を用いてタスクステータスサポートバッファTSSB1を適切に更新し、新たに生じたタスクの記録を含める。task.【0035】その後、処理は図12のステップ950へ進む。ステップ950においては、タスクキューおよびバッファマネージャBM1がタスクステータスサポートバッファTSSB1情報を利用して、新たに準備が整ったタスクを決定する。ステップ954においては、タスクキューおよびバッファマネージャBM1がレディタスクマルチウェイスタックRS1を更新し、準備が整ったタスクすべてをDFT(デプスファーストトラバーサル、深さ優先走査)順に含ませる。ステップ957においては、すべてのステップが実行されたという観点でプロセスが完了したか否かが調べられる。完了していない場合には、処理はステップ910へ戻る。完了している場合には処理は終了する。ends.【0036】図13は、ステップ914の別の実施例を示す流れ図である。910に引き続くものである。980,タスク割当て器TA1はタスクをタスクキューTQ1から削除する。taskあるいはタスクキューTQ1によってプライオリティが割り当てられており、タスク割当て器TA1は高いプライオリティを有するタスクのみを受け取る。別の実施例に従うと、タスク割当て器TA1はプライオリティを割り当てる。priority.【0037】ステップ984においては、タスク割当て器TA1が、複雑さに基づいて、タスクの重み付けを行う。TA11は、重み付けに基づいて、選択されたタスクを、利用可能な処理エレメントPE1よりなるグループに、それぞれのグループの総重みすなわち複雑さがほぼ等しくなるように分割する。ステップ990においては、タスク割当て器TA1はタスク群をそれぞれの処理エレメントPE1に係るタスクバッファTB1に供給する。その後、処理はステップ915へ戻る。915.【0038】図1から図5に示された本発明の別の実施例に従うと、割当てマネージャAM1は、シーケンシャルな(すなわち集中された)インプリメンテーションかパラレルな(すなわち分散された)インプリメンテーションのいずれかを有することが可能である。パラレルインプリメンテーションは、処理エレメントPE1よりなるシステムSY1上、あるいは個別のシステム上で実行される。TQ1およびタスクステータスバッファSB1はタスクキューおよびステータスバッファマネージャBM1内あるいは個別のメモリメモリデバイス内においてインプリメントされ得る。図1から図5に示されたエレメントは、所定の機能を実行するディスクリート素子の形態を有するか、あるいはプロセッサか、もしくは複数個のプロセッサの一部である。processors.【0039】本発明は、並列処理可能なタスクの組を選択し、シーケンシャルスケジュール中でより早くから利用可能になったタスクに対してより高いプライオリティを割り当てることによって、並列処理に係るメモリ要求を低減している。本発明のプロセスは、それぞれのプライオリティに基づいて、タスク群を並列処理エレメントに供給する。elements.【0040】処理は、新たなタスクを生成すると、そのタスクを生成した親タスクのスケジュール順序に従ってタスクを配置する。本発明の別の実施例に従うと、シーケンシャルスケジュール中での順序が、生成されたタスクに対する位置を予約し、生成されたタスクがその位置に配置される。本発明は、以下に記述される理論的背景に基づいている。ここで、時間と空間(すなわちメモリ)の双方の観点から、性能の限界を保証するための役に立つ汎用のインプリメンテーションを規定する。これらは、実行時間、およびワーク、デプスおよびシーケンシャル空間の関数としてのインプリメンテーションの空間に上限を設定することによって規定される。ここでは、ワーク、デプスおよび空間の表示法を、計算が進むに連れて動的に展開する有向非巡回グラフ(DAG、閉路を含まない有向グラフ)として計算をモデル化することによって定式化する。1994という論文に記載されている。to.【0042】DAGにおけるノード(節点)は単位ワークタスクを表現しており、エッジ(辺)は、タスク間の、インプリメンテーションの際に考慮されなければならない順序の依存関係を表現している。1992に記述されている並列クイックソート等のような)タスクストラクチャあるいはデータ間の依存関係が計算が実行されていくに連れて初めて明らかになるようなプログラムをもモデル化することが可能である。is.計算のワークはDAG内のノードの個数に対応し、デプスはDAG内の最長経路に対応する。メモリ使用法を考慮するために、DAGのそれぞれのノードに対して、そのノードが割り当てたり割り当て解除したりすることが必要なメモリ量を表現する重みが割り当てられる。その後、計算に係るシーケンシャル空間が、入力空間にそのDAGのデプスファーストトラバーサル(DFT)(標準的なシーケンシャルインプリメンテーションによってなされるトラバーサル)によって必要とされる空間を加えたものとして定義される。implementation).【0043】図14は、有向非巡回グラフとして表現された(“n=4”に対応する)行列乗算のタスクストラクチャを示した図である。ノードN01は単位ワークタスクを表現しており、エッジED1(この図においては下向きであると仮定されている)はタスク間の制御および/あるいはデータフローを表現している。)”個の空間を必要とする。)個の空間を必要とする可能性がある。)個の空間しか用いないことに留意されたい。space.【0044】プロセッサを良好に利用するあらゆる並列スケジュール法は、ほとんど常に、シーケンシャルインプリメンテーションにおけるものとは相異なった順序でタスクをスケジューリングする。このことにより、(それぞれの段階において準備が整っているタスクの組の最大のものを追跡するために)タスク予約に関連して必要とされるメモリと(割り当てられてはいるが未だ割当て解除されていない変数の組の最大のものを保持する目的で)プログラム変数を割り当てるために必要となるメモリ量の双方の増大をもたらす。largest.【0045】効率的なスケジューリングを実現するために、動的に展開するあらゆるDAGに関して空間およびステップ数の双方において恐らく効率的である並列スケジューリングのクラスがまず識別される。”シーケンシャル空間を必要とする場合に、このクラスに属する“p”プロセッサスケジューリング法は以下の利点を有している。advantages.【0046】このスケジューリング法においては、最大“W/p+D”ステップが存在する。これは、すべてのスケジューリング法に関して可能な最良のものと比較して常にファクタ2以内に収まっている。充分な並列性(すなわち、“W/p>>D”)を有するプログラムに関しては、最良で“1+o(1)”のファクタ内に収まる。+O(p・D)”の空間を利用するのみである。これには、プログラム変数に係る空間およびタスク予約に係る空間が含まれる。o(1)”のファクタ内に収まる。1994年12月)すなわちシーケンシャル空間のファクタ“p”倍、とは異なっている。that.【0047】これらの制限は、個別のタスクが常に一定量のメモリを割り当てる場合に適用される。)/p+D”ステップを用いて得られ、一般には、空間とステップとの間のトレードオフ関係が存在する。1+o(1)”内に収まっている。上記制限は、スケジューリング法をインプリメントする際のオーバーヘッドを考慮していない。1993,に記載されている)共通のアプローチは、DAGのそれぞれのステップにおいて“p”個の独立のノードを可能な限り貪欲にスケジューリングすることである。ここで、“p”はプロセッサの個数である。processors.【0049】希望される空間制限を求めるために、プログラム変数に対するメモリの増大を制限することに注意が集中している。本発明に係る解は、タスク予約に係るメモリの増大を制限することも可能であるからである。CELeisersonに係る文献に記述されているような、計算における巣レッド全体に関してメモリ要求量を関連付けるこれまでのモデルよりも、より詳細なメモリ割り当てが可能になる。ブロックメモリ割り当て、例えばアレイ、は、その重みが、その割り当てられるべきブロックの大きさであるようなノードによって表現される。block.【0050】基本的な疑問は、すべての計算DAGに関する良好な空間制限を有する(貪欲な)並列スケジューリング法はどれかということである。第一のキーポイントは、与えられたシーケンシャルスケジュールに基づいて並列スケジュールのクラスを規定し、シーケンシャルスケジュールが並列スケジュールに対するスケジューリングプライオリティを命ずるようにすることである。scheduling,それぞれのステップにおいて希望される並列性を実現する目的で、ノードをアウト・オブ・オーダーで(すなわち早期に)スケジューリングする。node,“p”個のプロセッサによるスケジューリング法のあらゆるステップにおいてこれらの早期ノードの数が最大でDAGのデプス、“D”、の“p”倍であることを注意深い議論で示すことである。このことは、すでに示された低い方の制限と一致しており、シーケンシャルスケジューリング法に基づく並列スケジューリング方の利用を正当化するものである。method.【0052】第三のポイントは、空間に対する要求に制限を与える目的で、早期ノードの数に係るこの制限を利用することである。計算のそれぞれの並列ステップにおいて、それぞれの早期ノードは、これらのノードによって実行される付加的な割り当てのためおよびスケジュールされ得る準備が整ったすべてのノードを追跡する目的により、シーケンシャルスケジューリングにおいて必要とされる空間以上の空間を必要とする。早期ノードが必要とする余分の空間がそのノード数と比例関係にあることを保証するアプローチが示されている。·D)”という空間制限が得られる。”はシーケンシャルスケジューリングに必要となる空間である。scheduling.【0053】上記結果は、シーケンシャルスケジューリングに基づくあらゆる並列スケジューリングに適用される。DAGのデプスファーストトラバーサル(DFT)であるため、定義および考察が、“p”−DFTスケジューリングに対して与えられる。これは、シーケンシャルデプスファーストスケジューリングに基づく並列スケジューリングのクラスである。並列DFTを規定するために考慮されるべき方法は数多く存在する。図示されている定義は恐らく良好な性能制限を与えることになる。このスケジューリング法は、“p”−DFTスケジューリング法と呼称されるものであるが、それぞれのステップにおいて最も深いノードに対してプライオリティを与えるようなスケジューリングとは異なっている。step.【0054】効率的なスケジューリングプロセスを実現するために、種々の定義が必要とされる。scheduling−DFTクラスは、標準的なシーケンシャルデプスファーストトラバーサルに対して、時間および空間の双方において効率的である。sizeGに通ずる言語)に関して、“p”−DFTスケジューリングを生成する効率的なランタイム(オンライン)スケジューリングアルゴリズムである。-DFTスケジューリングをインプリメントするために必要とされるプロセッサ割り当ておよびタスク同期が、プロセッサによって最小の時間でかつ最小のオーバーヘッドでどのように実行されるかが記述される。”個のシーケンシャル空間に係る計算に関しては、これらのオーバーヘッドを含むスケジューリング計算の結果、以下の制限が得られる。(i.e.,同時に読み書きがなされないもの)に関して得られる。CRCWスタイルの計算(すなわち同時読み書きがコストレスで許可されている場合)に関しては、より高い確率で“O(W/p+D・logp)”時間が得られる。p)”あるいはそれより少ない空間しか用いない。”)に関してシーケンシャル空間が最悪線型である限りは、同一の制限が得られる。obtained.【0055】これらの結果は、ネストされ得るものとされ得ないものの双方を含むほとんどすべてのデータ並列言語、さらには任意のファンアウトおよび任意のネスティングを許可するものを含む、分岐−結合型並列性を実現する大部分の言語に適用されるものである。realized.【0056】まず第一に、考慮している言語のクラスに関して、計算のタスクストラクチャは、動的に進展する直列−並列DAGであり、ある個数のノードは任意のファンアウトを有し(ソースノードと呼称される)、その他の対応するノードは任意のファンインを有している(シンクノードと呼称される)ことを理解する。-DFTスケジュールおよびプロセッサがどのようにタスクに対して割り当てられるべきかに係る規定が得られることを理解する。よって、シーケンシャルスケジューリングに基づく並列スケジューリングは、シーケンシャルスケジュールを知ることなく高速に構成され得ることになる。schedule.このアルゴリズムは、シーケンシャルデプスファーストスケジューリングをあらわに構成するために必要とされる速度の低下を回避する。scheduling.【0057】単純なスタックに基づくアルゴリズムに加えて、スタック空間に係る制限を得る、レイジースタック割り当てを用いる修正されたアルゴリズムが与えられている。ネスティングされた並列性計算における未知かつ変化する再帰的ネスティングレベルとノードにおいて可能な大きなファンインが与えられると、スケジューリング可能になるノードを効率的に識別することが困難になる。ここでは、この問題が、シンクノードに係るタスク同期問題として指摘される。次のキーポイントは、このタスク同期問題に関する効率的なアルゴリズムである。ここでは、“p”−DFTスケジューリングの直列−並列DAGに係る性質が、本発明に係るアルゴリズムおよびそのデータストラクチャの正確さ、さらにそのリソース制限を議論するために用いられる。PRAMステップを固定回数、それぞれ実行する。DFTを実行することによって、ラウンド毎に各プロセッサに対して複数個のタスクを割り当てる。Thus,時間および空間の複雑が増大するが、並列ワークが最適値から一定ファクタ倍以内に収まっていることが保証される。CRCWPRAMモデルに関して時間の複雑さを改善するために用いられ得ることが示される。model.【0059】本発明が依拠している理論は、動的に展開するDAGとしての計算に基づいており、DAGに係る与えられたスケジュールに従ってプログラムを実行するために必要とされる空間を測定するために用いられる一般的なモデルを含む、計算DAGおよびそのスケジューリングを記述する術語を用いる。1990,).【0060】有向非巡回グラフ“G”を考える。≧1”に対する“G”の“p”個のトラバーサル(すなわち“p”個のスケジュール)は、“τ≧1”ステップよりなるシーケンスである。”(このステップにおいてスケジューリングされたノード)の組を規定しており、以下の3つの性質が成り立つ。(i)それぞれのノードはスケジュール内で正確に一度現れる;(ii)ノードは、その直前のノードがそれ以前のステップにおいてスケジューリングされた後にのみスケジューリングされる;および(iii)それぞれのステップは、最大“p”個のノードから構成される。