タスクベースの並列プログラミング言語
【課題】タスクの依存性を単純に入力することができるプログラムを提供する。
【解決手段】第１の側面は，メモリを含むプログラムに関する。特に，高級言語に関する。プログラムは，タスク及び依存性を読み込む入力のみを要求する。その時，プログラムは，すべてのタスクをエラーなくスケジュールできるように，すべてのタスクと依存性を決定する。その後，すべてのタスクは，プログラムにより決定された依存性によって，スケジュールされる。各タスクは，他の言語又はハードウェアの手段により実行されてもよい。
【解決手段】第１の側面は，メモリを含むプログラムに関する。特に，高級言語に関する。プログラムは，タスク及び依存性を読み込む入力のみを要求する。その時，プログラムは，すべてのタスクをエラーなくスケジュールできるように，すべてのタスクと依存性を決定する。その後，すべてのタスクは，プログラムにより決定された依存性によって，スケジュールされる。各タスクは，他の言語又はハードウェアの手段により実行されてもよい。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は，タスクベースの並列プログラミング言語に関する。特にゲーム又はグラフィックに関して，様々なタスクの依存性をコンピュータにより考慮することができるシステム又はソフトウェアに関する。
【背景技術】
【０００２】
いくつかのライブラリ及びフレームワークは，依存性や連続性などのスケジューリング機能を多数含むことにより，タスクの並列化を拡張する。タスクの並列化の例として知られているものとして，メニーコアハードウェアをプログラミングするための，効果的で拡張可能な取り組みがあるが，そのようなライブラリやフレームワークなどをＣ＋＋言語及び他の命令型言語で使用する場合に，いくつかの問題点がある。
【０００３】
Ｃｉｌｋは，タスクの生成と同期化のキーワードを加えることにより，Ｃ言語又は，Ｃ＋＋言語を拡張した言語である。Ｃｉｌｋは，高度なタスクスケジューラを含む。タスクは，他のタスクを順に生み出すことができる関数として特定される。Ｃｉｌｋは，タスク並列化プログラムの生成をより単純にするが，プログラマーは，子タスクを同期化する（子タスクが完了するまで待つ）ことにより，手作業で依存性に対処しなければならない。Ｃｉｌｋ＋＋は，Ｃ＋＋言語と非常に深く関係しているため（事実，言語の上位集合である），そのため，依存性情報を自動的に計算するのは難しくなっている。これは，Ｃ＋＋言語のリファレンス及びポインタでは，コンパイラとランタイムシステムが，タスクの入出力と一致するデータについて予測できないことを意味している。
【先行技術文献】
【非特許文献】
【０００４】
【非特許文献１】ＦＲＩＧＯ，Ｍ．，ＬＥＩＳＥＲＳＯＮ，Ｃ．Ｅ．，ＡＮＤ ＲＡＮＤＡＬＬ，Ｋ．Ｈ．１９９８．Ｔｈｅ ｉｍｐｌｅｍｅｎｔａｔｉｏｎ ｏｆ ｔｈｅ ｃｉｌｋ−５ ｍｕｌｔｉｔｈｒｅａｄｅｄ ｌａｎｇｕａｇｅ．Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ ＡＣＭ ＳＩＧＰＬＡＮ ’９８ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｐｒｏｇｒａｍｉｎｇ Ｌａｕｇｕａｇｅ Ｄｅｓｉｇｎ ａｎｄ Ｉｍｐｌｅｍｅｎｔａｔｉｏｎ（Ｊｕｎｅ）．
【発明の概要】
【発明が解決しようとする課題】
【０００５】
本発明の目的の１つは，タスクの依存性を単純に入力できるプログラムを提供することである。プログラムは，タスクの依存性のみを処理する高級言語であってもよく，各タスクは，低級言語によって実行されてもよい。
【０００６】
本発明の目的の１つは，タスクの依存性を自動的に決定することができるプログラムを提供することである。
【０００７】
本発明の他の目的は，タスクの依存性を自動的に決定した後に，並列タスクを実行することができるプログラムを提供することである。
【課題を解決するための手段】
【０００８】
本発明の第１の側面は，プログラムに関する。特に，高級言語に関する。プログラムは，タスクと依存性に関する入力のみを要求する。そのとき，プログラムは，エラーのないタスクのすべてをスケジュールできるように，すべてのタスクと依存性を決定してもよい。その後，すべてのタスクは，本発明のプログラムにより決定された依存性によって，スケジュリングされる。各タスクは，他のプログラム又はハードウェアによって実行されてもよい。
【０００９】
本発明のプログラムは，複数のタスクを入力する手段と，それらのタスクの依存性を入力する手段と，入力されたタスクの依存性により，入力されたすべてのタスクの依存性を自動的に決定する手段とをコンピュータに行わせる。
【００１０】
プログラムに要求される入力は，単純である。しかし，本プログラムは，コンピュータにタスクの依存性を，自動的に，どんなエラーもなく，決定させることができる。繰り返しになるが，本プログラムが，コンピュータにタスクの依存性を決定させた後，他のプログラムが，依存性により決定したスケジュールに基づいて，各タスクを実行してもよい。
【００１１】
下記は，代入文の例である。
ｏｕｔ＿ｂｕｆｆｅｒ：＝ｍｙ＿ｔａｓｋ（ｉｎ＿ｂｕｆｆｅｒ，ｐａｒａｍ１）
この場合，ｍｙ＿ｔａｓｋは，入力として‘ｉｎ＿ｂｕｆｆｅｒ’の出力を要求するとともに，‘ｐａｒａｍ１’も要求する。‘ｐａｒａｍ１’は，タスクに使用されるパラメータ又は数値でもよい。したがって，ｍｙ＿ｔａｓｋは，‘ｉｎ＿ｂｕｆｆｅｒ’に依存するように決定される。その時，タスク，つまりｍｙ＿ｔａｓｋは，‘ｉｎ＿ｂｕｆｆｅｒ’の出力に依存するいずれかのタスクを，非同期的に実行されるようにスケジュールされてもよい。
【００１２】
本プログラムの好ましい態様として，依存性は，所定のタグにより入力される。上記の例として，依存性は，‘ｂｕｆｆｅｒ’のタグが付されており，依存タスクは，かっこ内に記述されている。
【００１３】
本プログラムの好ましい態様として，タスクは，‘ｔａｓｋ ｃｏｄｅ’の入力，‘ｉｎｐｕｔ ｄａｔａ ｂｕｆｆｅｒ’の入力，‘ｏｕｔｐｕｔ ｄａｔａ ｂｕｆｆｅｒ’の入力，及び‘ｉｍｍｅｄｉａｔｅ ｐａｒａｍｅｔｅｒ’の入力に従って実行される。タスクの依存性は，‘ｉｎｐｕｔ ｄａｔａ ｂｕｆｆｅｒ’及び‘ｏｕｔｐｕｔ ｄａｔａ ｂｕｆｆｅｒ’として入力され，‘ｉｎｐｕｔ ｄａｔａ ｂｕｆｆｅｒ’の入力，及び‘ｏｕｔｐｕｔ ｄａｔａ ｂｕｆｆｅｒ’の入力により決定する。
【００１４】
依存性は，‘ｂｕｆｆｅｒ’タグにより入力されるため，コンピュータは，タグの情報を読み込むことにより，入力される依存性を決定することができる。ここでいう‘ｔａｓｋ ｃｏｄｅ’は，他のプログラムにより実行される各タスクを示してもよい。‘ｔａｓｋ ｃｏｄｅ’の例は動画であり，あるオブジェクトの動画を生成することである。‘ｉｍｍｅｄｉａｔｅ ｐａｒａｍｅｔｅｒ’の例は，何かの計算に使用される数字又は数値である。
【００１５】
本プログラムの好ましい態様として，本プログラムは，コンピュータを，すべての入力タスクの決定された依存性を考慮して，タスクを自動的にスケジューリングする手段として，さらに機能させる。
【００１６】
本プログラムの好ましい態様として，自動的に依存性を決定する手段は，親タスク及び親タスクに要求される１つ又は複数の子タスクを決定する手段と，すべての子タスクの情報を格納する手段と，親タスクに必要なすべての子タスクが実行されるか否かを決定する手段とを含む。本発明は，コンピュータの読み取り可能なメディアを含む。このメディアは，上記プログラムを含む。さらに本発明は，上記プログラムを実装するハードウェア，例えばコンピュータを含む。
【発明の効果】
【００１７】
本発明のプログラムは，タスクとそれに伴う依存性の単純な入力に基づき，タスクの依存性を単純に決定することができる。この依存性により，本発明のプログラムを実装するコンピュータは，タスクのスケジュールを決定することができる。プログラムは，依存性の制御装置として使用されてもよい。
【図面の簡単な説明】
【００１８】
【図１】図１は，実施例２の依存性グラフを示す。
【図２】図２は，実施例３の依存性グラフを示す。
【発明を実施するための形態】
【００１９】
タスクベースの並列プログラミング言語
本発明のタスクベースの並列プログラミング言語を説明する。本発明により得られるフレームワークは，２階層システムであってもよい。高階層では，タスクと依存性を特定する簡易なスケジューリング言語を扱い，低階層では，タスクの実装を行う。タスクの実装は，タスク言語又は，例えばＣ＋＋言語のどちらか一方によってなされ得る。
【００２０】
本発明のプログラムは，高階層のプログラムに関する。高階層のプログラミングとして，タスクの指定は，‘ｔａｓｋ ｃｏｄｅ’，‘ｉｎｐｕｔ ｄａｔａ ｂｕｆｆｅｒ’，‘ｏｕｔｐｕｔ ｄａｔａ ｂｕｆｆｅｒ’及び‘ｉｍｍｅｄｉａｔｅ ｐａｒａｍｅｔｅｒ’から成ってもよい。つまり，プログラマーは，‘ｔａｓｋ ｃｏｄｅ’
‘ｉｎｐｕｔ ｄａｔａ ｂｕｆｆｅｒ’，‘ｏｕｔｐｕｔ ｄａｔａ ｂｕｆｆｅｒ’，又は‘ｉｍｍｅｄｉａｔｅ ｐａｒａｍｅｔｅｒ’に関する情報を，キーボード，タッチパネル及びマウスなどのポインティングデバイスによって，入力してもよい。プログラマーは，‘ｉｎｐｕｔ ｄａｔａ ｂｕｆｆｅｒ’及び‘ｏｕｔｐｕｔ ｄａｔａ ｂｕｆｆｅｒ’によりタスクの依存性を入力してもよい。言い換えると，プログラマーは，入出力データの要件に沿って，リスト操作を指示するのみである。
【００２１】
プログラマーは以下のように記述することができる。
Ｔａｓｋ １：ｃａｌｕｃｕｌａｔｅ ｃｈａｒａｃｔｅｒ １ ｐｏｓｉｔｉｏｎ
Ｔａｓｋ ２：ｃａｌｕｃｕｌａｔｅ ｃｈａｒａｃｔｅｒ ２ ｐｏｓｉｔｉｏｎ
Ｔａｓｋ ３：ｄｒａｗ ｃｈａｒａｃｔｅｒ １（ｗｈｅｎ Ｔａｓｋ １ ｉｓ ｃｏｍｐｌｅｔｅ）
Ｔａｓｋ ４：ｄｒａｗ ｃｈａｒａｃｔｅｒ ２（ｗｈｅｎ Ｔａｓｋ ２ ｉｓ ｃｏｍｐｌｅｔｅ）
【００２２】
上記の例において，‘ｃａｌｕｃｕｌａｔｅ’及び‘ｄｒａｗ’は，‘ｔａｓｋ ｃｏｄｅ’であり，‘ｗｈｅｎ Ｔａｓｋ１ ｉｓ ｃｏｍｐｌｅｔｅ’及び‘ｗｈｅｎ Ｔａｓｋ２ ｉｓ ｃｏｍｐｌｅｔｅ’は，‘ｉｎｐｕｔ ｄａｔａ ｂｕｆｆｅｒ’に対応している。入力データは，コンピュータのメモリに格納されている。コンピュータは，依存情報を抽出し，タスクスケジューラに渡す。つまり，本プログラムが実装されるこのシステムは，‘ｉｎｐｕｔ ｄａｔａ ｂｕｆｆｅｒ’を読み込むことにより，Ｔａｓｋ３がＴａｓｋ１に依存すること，及び‘ｉｎｐｕｔ ｄａｔａ ｂｕｆｆｅｒ’を読み込むことにより，Ｔａｓｋ４がＴａｓｋ２に依存することを自動的に決定することができる。また，コンピュータは，メモリから入力データを読み込み，依存性を示すかっこを検索することにより，すべての依存性，つまり，Ｔａｓｋ３がＴａｓｋ１に依存すること，及びＴａｓｋ４がＴａｓｋ２に依存することを決定してもよい。
【００２３】
本プログラムは，プログラマーに，より大きなバッファのサブ領域の指示を入力させてもよい。サブ領域の入力の表記は，[ａｎｄ]である。その指示により，単一のバッファでの作業を分割してもよい。そのようなデータがプログラマーにより入力される時，コンピュータはその入力をメモリに格納する。その際，コンピュータはメモリからその入力を読み込み，分析する。そして，
[ａｎｄ]を含むように入力が決定されると同時に，コンピュータは，サブ領域のタスクが指示されることを決定する。その後，コンピュータは単一のバッファを２つ又は２つ以上に分割する。
【００２４】
本プログラムは，プログラマーに，バッファの使用に関するいくつかの制約をバイパスする指示を入力させてもよい。バイパスの入力表記の例は，＜−である。本プログラムは，コンピュータに，決定された依存性を考慮して，そのようなバイパスを，自動的に決定させてもよい。
【００２５】
本プログラム又は本プログラムを有するコンピュータは，親タスク及び親タスクを要件とする１つ又は複数の子タスクを決定してもよい。上記の例では，Ｔａｓｋ３をＴａｓｋ１の結果として実行することが要求されているので，Ｔａｓｋ３はＴａｓｋ１に依存している。この場合，Ｔａｓｋ３が親タスクで，Ｔａｓｋ１が子タスクとなる。本発明の好ましい態様では，すべての子タスクの情報をメモリに格納する。コンピュータは，すべての子タスクが終了するか否かを，メモリに格納される子タスクの情報により，決定する。コンピュータは，すべての子タスクが終了されると決定すると同時に，親タスクを実行してもよい。プログラムが，コンピュータに親タスクと子タスクを自動的に決定させ，子タスクが終了した後に親タスクを実行させるので，プログラマーは，タスクとランタイムをスケジューリングする必要がない。
【００２６】
コンピュータのスケジューラは，タスクの依存性のすべてを考慮することにより，実行順序を決定する。コンピュータは，ｃｈａｒａｃｔｅｒ１とｃｈａｒａｃｔｅｒ２が独立するように決定する。コンピュータは，Ｔａｓｋ１と３及びＴａｓｋ２と４が並列的に実行されるように決定する。コンピュータは，低階層システムを使用して，各タスクのランタイムを決定する。
【００２７】
このシステムでは，データはバッファのタグが付されてもよい。プログラムは，コンピュータの読み込み可能な媒体に格納されてもよい。そのような媒体の例としては，ＣＤ−ＲＯＭ，ＣＤ，ＤＶＤ，ＦＤ，ＭＯ，ＵＳＢメモリ，ＳＤカード，ＩＰコア及びＩＣチップがある。つまり，本発明は，上記プログラムを格納する，このようなメモリを有する。
【００２８】
本発明の第２の側面は，複数のタスクの入力手段と，タスクの依存性を入力する手段と，入力されたタスクの依存性により，入力されたすべてのタスクの依存性を自動的に決定する手段，とを含むコンピュータに関する。つまり，コンピュータは，例えば上記プログラムをメインメモリに格納し，プログラムにより提供される操作手段によって，依存性を決定する。コンピュータは，入力手段，出力手段，処理ユニット，及び演算ユニットを含んでもよい。各手段及びユニットは，例えば，バスにより接続されている。
【実施例１】
【００２９】
アニメーションシステムの簡単な実施例として，下記のコードは，２つのアニメーションのアンパックとそれらを操作する混合タスクを，正確な依存性でスケジュールする。
【００３０】
ｂｕｆｆｅｒ＜Ａｎｉｍａｔｉｏｎ＞ａｎｉｍ１
ａｎｉｍ１：＝ｕｎｐａｃｋａｎｉｍ＿ｔａｓｋ（ｉｎｐｕｔ１）
ｂｕｆｆｅｒ＜Ａｎｉｍａｔｉｏｎ＞ａｎｉｍ２
ａｎｉｍ２：＝ｕｎｐａｃｋａｎｉｍ＿ｔａｓｋ（ｉｎｐｕｔ２）
ｂｕｆｆｅｒ＜Ａｎｉｍａｔｉｏｎ＞ｆｉｎａｌ
ｆｉｎａｌ：＝ｕｎｐａｃｋａｎｉｍ＿ｔａｓｋ（ａｎｉｍ１，ａｎｉｍ２）
【００３１】
上記では，タスクと依存性が入力されている。つまり，要件となる各タスクの情報は，かっこ内に表示されている。その要件情報は，依存性に関する。従って，コンピュータは，上記入力データを受けとったときに，タスク及び依存性を決定する。コンピュータは，ｂｕｆｆｅｒ＜Ａｎｉｍａｔｉｏｎ＞ｆｉｎａｌから，タスクがａｎｉｍ１及びａｎｉｍ２を要件とすること決定する。すなわち，このタスクは上記２つのタスクに依存している。
【００３２】
適切に定義されている‘Ａｎｉｍａｔｉｏｎ’データオブジェクトと要件となるタスクコードを考えると，プログラマーは，唯一，データがシステムを移動する方法を特定する必要がある。その時，ランタイムフレームワークは，２つの’ｕｎｐａｃｋａｎｉｍ＿ｔａｓｋ’操作を並列に実行できるように決定することができる。アンパックと混合タスクは以下の関数を実装することによりＣ＋＋言語によって記述することできる。
【００３３】
ｖｏｉｄ＿ｔｌ＿ｂｌｅｎｄ＿ｔａｓｋ（ｔｌｃｏｎｔｅｘｔ＿ｔ ｔｌｃｔｘ，
ｂｕｆｆｅｒ＿ｔ ａｎｉｍ１，
ｂｕｆｆｅｒ＿ｔ ａｎｉｍ２，
ｂｕｆｆｅｒ＿ｔ ｏｕｔｐｕｔ１）；
【００３４】
この実装コードは，スケジューリング又はバッファのロッキングの詳細を配慮することなく行われるように，計算のみに焦点を当てることになる。また，実装コードは，コード型とデータ型の最小集合にのみ依存することになるため，すべてのデータは，関数の引数として渡される必要がある。
【００３５】
ここにあるように，このアニメーションのタイプは，Ｃ＋＋言語クラスになるだろうが，意図的にｕｎｐａｃｋ（）メソッドを組み込んでいない。それどころか，これはタスクのあるデータコンテナであって，メソッドは作動しない。このアーキテクチャ（メソッドは，データアクセスを提供するのであって，作動しない）は，演算関数の依存性を軽減するのに役立つ（そのような依存性は，既存コードをタスクにリファクタリングする時よく問題を起こす）。これにより，より多くの並列化が，最小の努力でより少ないエラーにより導入される。
【実施例２】
【００３６】
今後グラフィックアプリケーションとなりえる，ほんの少し高度な実施例を以下に示す。初めに，位置データが復元され，その後，それは，以下の２つの目的に使用される。第１に，位置データは，詳細なバウンディング形状を計算するボクセル構造を満たすように使用される。第２に，位置データは，光のタンジェントデータと標準データを計算するのに使用される。
【００３７】
ｐｏｓＢｕｆ：＝ｄｅｃｏｍｐ＿ｐｏｓ（ｃｏｍｐｂｕｆｆｅｒ，ｎｕｍＶｅｒｔｓ）
ｔａｎＢｕｆ：＝ｃａｌｃ＿ｔａｎｇｅｎｔｓ（ｐｏｓＢｕｆ，ｎｕｍＶｅｒｔｓ）
ｎｏｒＢｕｆ：＝ｃａｌｃ＿ｎｏｒｍａｌｓ（ｐｏｓＢｕｆ，ｔａｎｂｕｆ，ｎｕｍＶｅｒｔｓ）
ｖｏｘｅｌＢｕｆ：＝ｃａｌｃ＿ｖｏｘｅｌ（ｐｏｓＢｕｆ，ｎｕｍＶｅｒｔｓ）
【００３８】
上記では，タスクと依存性が入力されている。つまり，要件となる各タスクの情報が，かっこ内に表示されている。コンピュータは，入力によりすべてのタスクと依存性を決定する。タスクの‘ｔａｎＢｕｆ’は，‘ｐｏｓＢｕｆ’，つまり‘ｄｅｃｏｍｐ＿ｐｏｓ’に依存している。タスクの‘ｖｏｘｅｌＢｕｆ’は，‘ｐｏｓＢｕｆ’，つまり‘ｄｅｃｏｍｐ＿ｐｏｓ’に依存している。タスク‘ｎｏｒＢｕｆ’は，‘ｐｏｓＢｕｆ’，つまり‘ｄｅｃｏｍｐ＿ｐｏｓ’及び‘ｔａｎＢｕｆ’，つまり‘ｃａｌｃ＿ｔａｎｇｅｎｔｓ’に依存している。次に，コンピュータは，すべてのタスク又はタスクのスケジューリングにランタイムを割り当てる。つまり，コンピュータは，初めに‘ｄｅｃｏｍｐ＿ｐｏｓ’タスクを実行するよう手配し，その時，‘ｃａｌｃ＿ｔａｎｇｅｎｔ’タスクと‘ｃａｌｃ＿ｖｏｘｅｌ’タスクを並列に実行し，その後，‘ｃａｌｃ＿ｎｏｒｍａｌｓ’も実行する。
【００３９】
図１の依存性グラフは，設定されたランタイムスケジューラにより，コード実行時に生成された。これは，システムが，タスク間の依存性を正確に抽出していることを示している。
【実施例３】
【００４０】
この実施例では，より高度な検証として，再帰ソーティングアルゴリズムを使用した。ピボット（通常，右端の値）を選択し，バッファのファストパスを行う整数型バッファから始めて，ピボットが正しい位置になるよう配列し直すために，ピボットの左側へのすべてのエントリーは，より少ない値か等しい値とし，ピボットの右側へのすべてのエントリーは，そのピボットよりもすべて大きな値とする。
【００４１】
この段階では，左側と右側はソートされていないが，同じアルゴリズムをこれらのサブバッファに，再帰的に適用することができる。サブバッファは，結局は，完全にソートされた整数リストになる。
【００４２】
この実施において，再帰‘ソート’タスクは，タスク言語により実装され，‘ｄｏＳｏｒｔ（）’関数（Ｃ言語により実装される）の使用により，実際のデータ操作が行われる。‘ｓｏｒｔ’関数のコードは，以下に示される。
【００４３】
ｔａｓｋ ｂｕｆｆｅｒ＜ｕｎｉｔ３２＿ｔ＞ｏｕｔｐｕｔ：：
ｓｏｒｔ（ｓｉｚｅ＿ｔ ｅｎｔｒｉｅｓ，
ｂｕｆｆｅｒ＜ｕｎｉｔ３２＿ｔ＞ｉｎｐｕｔ）
＃Ｄｉｖｉｄｅ ｕｓｉｎｇ ｔｈｅ ｐｉｖｏｔ
ｓｉｚｅ＿ｔ ｐｉｖＩｄｘ
ｐｉｖＩｄｘ
ｐｉｖＩｄｘ＝ｄｏＳｏｒｔ（ｅｎｔｒｉｅｓ，ｏｕｔｐｕｔ）
＃Ｓｏｒｔ ＬＥＦＴ ｂｕｆｆｅｒ
ｉｆ ｐｉｖＩｄｘ＞１ ｔｈｅｎ
ｂｕｆｆｅｒ ＩＢｕｆ＝ｏｕｔｐｕｔ［０，ｐｉｖＩｄｘ］
ＩＢｕｆ＜−ｓｏｒｔ（ｐｉｖＩｄｘ，ＩＢｕｆ）
ｅｎｄ
＃Ｓｏｒｔ ＲＩＧＨＴ ｂｕｆｆｅｒ
ｉｆ ｐｉｖｏｔＩｄｘ＜ｅｎｔｒｉｅｓ−２ ｔｈｅｎ
ｂｕｆｆｅｒ ｒＢｕｆ ＝ｏｕｔｐｕｔ［ｐｉｖＩｄｘ＋１，ｅｎｔｒｉｅｓ］
ｓｉｚｅ＿ｔ ｒＥｎｔｒｉｅｓ ＝ｅｎｔｒｉｅｓ−ｐｉｖＩｄｘ−１
ｒＢｕｆ ＜− ｓｏｒｔ（ｒＥｎｔｒｉｅｓ，ｒＢｕｆ）
ｅｎｄ
ｅｎｄ
【００４４】
このコードは，いくつかの言語機能を示している。‘ｓｕｂ−ｂｕｆｆｅｒ’，つまり，[ａｎｄ]表記は，より大きなバッファのサブ領域を参照する新しいバッファオブジェクトを生成するのに使用される。この機能は，依存性を追跡させたまま，単一のバッファの作業を分割させる。‘ｉｎ−ｐｌａｃｅ ｂｕｆｆｅｒ ａｓｓｉｇｎｍｅｎｔｓ’，つまり，＜−の表記は，バッファ使用時のいくつかの制約を，バイパスするのに使用される。これは，各段階での中間バッファの割り当てを回避するという，実行上の理由で，使用される。
‘ｃｏｎｔｉｎｕａｔｉｏｎｓ’については，左右のサブバッファの子タスクを起動した後，親タスクのソートが終了する。その時，通常ならば，いずれの依存タスクも実行され得るが，子タスクが完了していなかったために，バッファは完全にソートされないかもしれない。これを克服するために，本システムは，子タスクを連続的に起動する。そのため，依存タスクは，子タスクが完了するまで実行されなくてもよい。
【００４５】
図２は，あるテストデータでアルゴリズムを実行することにより生成される依存性グラフを示す。（赤い）ノードはソートプロセスで同時に生成される子タスクを示す。この場合，チェックタスク（Ｃｈｅｃｋ Ｔａｓｋ）は，ソートタスクが完了するまでスケジュールされない。
【産業上の利用可能性】
【００４６】
本発明は，コンピュータ産業，特に，アミューズメント産業において利用可能である。
【符号の説明】
【００４７】
１ タスク
２ バッファ
３ ソート
【技術分野】
【０００１】
本発明は，タスクベースの並列プログラミング言語に関する。特にゲーム又はグラフィックに関して，様々なタスクの依存性をコンピュータにより考慮することができるシステム又はソフトウェアに関する。
【背景技術】
【０００２】
いくつかのライブラリ及びフレームワークは，依存性や連続性などのスケジューリング機能を多数含むことにより，タスクの並列化を拡張する。タスクの並列化の例として知られているものとして，メニーコアハードウェアをプログラミングするための，効果的で拡張可能な取り組みがあるが，そのようなライブラリやフレームワークなどをＣ＋＋言語及び他の命令型言語で使用する場合に，いくつかの問題点がある。
【０００３】
Ｃｉｌｋは，タスクの生成と同期化のキーワードを加えることにより，Ｃ言語又は，Ｃ＋＋言語を拡張した言語である。Ｃｉｌｋは，高度なタスクスケジューラを含む。タスクは，他のタスクを順に生み出すことができる関数として特定される。Ｃｉｌｋは，タスク並列化プログラムの生成をより単純にするが，プログラマーは，子タスクを同期化する（子タスクが完了するまで待つ）ことにより，手作業で依存性に対処しなければならない。Ｃｉｌｋ＋＋は，Ｃ＋＋言語と非常に深く関係しているため（事実，言語の上位集合である），そのため，依存性情報を自動的に計算するのは難しくなっている。これは，Ｃ＋＋言語のリファレンス及びポインタでは，コンパイラとランタイムシステムが，タスクの入出力と一致するデータについて予測できないことを意味している。
【先行技術文献】
【非特許文献】
【０００４】
【非特許文献１】ＦＲＩＧＯ，Ｍ．，ＬＥＩＳＥＲＳＯＮ，Ｃ．Ｅ．，ＡＮＤ ＲＡＮＤＡＬＬ，Ｋ．Ｈ．１９９８．Ｔｈｅ ｉｍｐｌｅｍｅｎｔａｔｉｏｎ ｏｆ ｔｈｅ ｃｉｌｋ−５ ｍｕｌｔｉｔｈｒｅａｄｅｄ ｌａｎｇｕａｇｅ．Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ ＡＣＭ ＳＩＧＰＬＡＮ ’９８ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｐｒｏｇｒａｍｉｎｇ Ｌａｕｇｕａｇｅ Ｄｅｓｉｇｎ ａｎｄ Ｉｍｐｌｅｍｅｎｔａｔｉｏｎ（Ｊｕｎｅ）．
【発明の概要】
【発明が解決しようとする課題】
【０００５】
本発明の目的の１つは，タスクの依存性を単純に入力できるプログラムを提供することである。プログラムは，タスクの依存性のみを処理する高級言語であってもよく，各タスクは，低級言語によって実行されてもよい。
【０００６】
本発明の目的の１つは，タスクの依存性を自動的に決定することができるプログラムを提供することである。
【０００７】
本発明の他の目的は，タスクの依存性を自動的に決定した後に，並列タスクを実行することができるプログラムを提供することである。
【課題を解決するための手段】
【０００８】
本発明の第１の側面は，プログラムに関する。特に，高級言語に関する。プログラムは，タスクと依存性に関する入力のみを要求する。そのとき，プログラムは，エラーのないタスクのすべてをスケジュールできるように，すべてのタスクと依存性を決定してもよい。その後，すべてのタスクは，本発明のプログラムにより決定された依存性によって，スケジュリングされる。各タスクは，他のプログラム又はハードウェアによって実行されてもよい。
【０００９】
本発明のプログラムは，複数のタスクを入力する手段と，それらのタスクの依存性を入力する手段と，入力されたタスクの依存性により，入力されたすべてのタスクの依存性を自動的に決定する手段とをコンピュータに行わせる。
【００１０】
プログラムに要求される入力は，単純である。しかし，本プログラムは，コンピュータにタスクの依存性を，自動的に，どんなエラーもなく，決定させることができる。繰り返しになるが，本プログラムが，コンピュータにタスクの依存性を決定させた後，他のプログラムが，依存性により決定したスケジュールに基づいて，各タスクを実行してもよい。
【００１１】
下記は，代入文の例である。
ｏｕｔ＿ｂｕｆｆｅｒ：＝ｍｙ＿ｔａｓｋ（ｉｎ＿ｂｕｆｆｅｒ，ｐａｒａｍ１）
この場合，ｍｙ＿ｔａｓｋは，入力として‘ｉｎ＿ｂｕｆｆｅｒ’の出力を要求するとともに，‘ｐａｒａｍ１’も要求する。‘ｐａｒａｍ１’は，タスクに使用されるパラメータ又は数値でもよい。したがって，ｍｙ＿ｔａｓｋは，‘ｉｎ＿ｂｕｆｆｅｒ’に依存するように決定される。その時，タスク，つまりｍｙ＿ｔａｓｋは，‘ｉｎ＿ｂｕｆｆｅｒ’の出力に依存するいずれかのタスクを，非同期的に実行されるようにスケジュールされてもよい。
【００１２】
本プログラムの好ましい態様として，依存性は，所定のタグにより入力される。上記の例として，依存性は，‘ｂｕｆｆｅｒ’のタグが付されており，依存タスクは，かっこ内に記述されている。
【００１３】
本プログラムの好ましい態様として，タスクは，‘ｔａｓｋ ｃｏｄｅ’の入力，‘ｉｎｐｕｔ ｄａｔａ ｂｕｆｆｅｒ’の入力，‘ｏｕｔｐｕｔ ｄａｔａ ｂｕｆｆｅｒ’の入力，及び‘ｉｍｍｅｄｉａｔｅ ｐａｒａｍｅｔｅｒ’の入力に従って実行される。タスクの依存性は，‘ｉｎｐｕｔ ｄａｔａ ｂｕｆｆｅｒ’及び‘ｏｕｔｐｕｔ ｄａｔａ ｂｕｆｆｅｒ’として入力され，‘ｉｎｐｕｔ ｄａｔａ ｂｕｆｆｅｒ’の入力，及び‘ｏｕｔｐｕｔ ｄａｔａ ｂｕｆｆｅｒ’の入力により決定する。
【００１４】
依存性は，‘ｂｕｆｆｅｒ’タグにより入力されるため，コンピュータは，タグの情報を読み込むことにより，入力される依存性を決定することができる。ここでいう‘ｔａｓｋ ｃｏｄｅ’は，他のプログラムにより実行される各タスクを示してもよい。‘ｔａｓｋ ｃｏｄｅ’の例は動画であり，あるオブジェクトの動画を生成することである。‘ｉｍｍｅｄｉａｔｅ ｐａｒａｍｅｔｅｒ’の例は，何かの計算に使用される数字又は数値である。
【００１５】
本プログラムの好ましい態様として，本プログラムは，コンピュータを，すべての入力タスクの決定された依存性を考慮して，タスクを自動的にスケジューリングする手段として，さらに機能させる。
【００１６】
本プログラムの好ましい態様として，自動的に依存性を決定する手段は，親タスク及び親タスクに要求される１つ又は複数の子タスクを決定する手段と，すべての子タスクの情報を格納する手段と，親タスクに必要なすべての子タスクが実行されるか否かを決定する手段とを含む。本発明は，コンピュータの読み取り可能なメディアを含む。このメディアは，上記プログラムを含む。さらに本発明は，上記プログラムを実装するハードウェア，例えばコンピュータを含む。
【発明の効果】
【００１７】
本発明のプログラムは，タスクとそれに伴う依存性の単純な入力に基づき，タスクの依存性を単純に決定することができる。この依存性により，本発明のプログラムを実装するコンピュータは，タスクのスケジュールを決定することができる。プログラムは，依存性の制御装置として使用されてもよい。
【図面の簡単な説明】
【００１８】
【図１】図１は，実施例２の依存性グラフを示す。
【図２】図２は，実施例３の依存性グラフを示す。
【発明を実施するための形態】
【００１９】
タスクベースの並列プログラミング言語
本発明のタスクベースの並列プログラミング言語を説明する。本発明により得られるフレームワークは，２階層システムであってもよい。高階層では，タスクと依存性を特定する簡易なスケジューリング言語を扱い，低階層では，タスクの実装を行う。タスクの実装は，タスク言語又は，例えばＣ＋＋言語のどちらか一方によってなされ得る。
【００２０】
本発明のプログラムは，高階層のプログラムに関する。高階層のプログラミングとして，タスクの指定は，‘ｔａｓｋ ｃｏｄｅ’，‘ｉｎｐｕｔ ｄａｔａ ｂｕｆｆｅｒ’，‘ｏｕｔｐｕｔ ｄａｔａ ｂｕｆｆｅｒ’及び‘ｉｍｍｅｄｉａｔｅ ｐａｒａｍｅｔｅｒ’から成ってもよい。つまり，プログラマーは，‘ｔａｓｋ ｃｏｄｅ’
‘ｉｎｐｕｔ ｄａｔａ ｂｕｆｆｅｒ’，‘ｏｕｔｐｕｔ ｄａｔａ ｂｕｆｆｅｒ’，又は‘ｉｍｍｅｄｉａｔｅ ｐａｒａｍｅｔｅｒ’に関する情報を，キーボード，タッチパネル及びマウスなどのポインティングデバイスによって，入力してもよい。プログラマーは，‘ｉｎｐｕｔ ｄａｔａ ｂｕｆｆｅｒ’及び‘ｏｕｔｐｕｔ ｄａｔａ ｂｕｆｆｅｒ’によりタスクの依存性を入力してもよい。言い換えると，プログラマーは，入出力データの要件に沿って，リスト操作を指示するのみである。
【００２１】
プログラマーは以下のように記述することができる。
Ｔａｓｋ １：ｃａｌｕｃｕｌａｔｅ ｃｈａｒａｃｔｅｒ １ ｐｏｓｉｔｉｏｎ
Ｔａｓｋ ２：ｃａｌｕｃｕｌａｔｅ ｃｈａｒａｃｔｅｒ ２ ｐｏｓｉｔｉｏｎ
Ｔａｓｋ ３：ｄｒａｗ ｃｈａｒａｃｔｅｒ １（ｗｈｅｎ Ｔａｓｋ １ ｉｓ ｃｏｍｐｌｅｔｅ）
Ｔａｓｋ ４：ｄｒａｗ ｃｈａｒａｃｔｅｒ ２（ｗｈｅｎ Ｔａｓｋ ２ ｉｓ ｃｏｍｐｌｅｔｅ）
【００２２】
上記の例において，‘ｃａｌｕｃｕｌａｔｅ’及び‘ｄｒａｗ’は，‘ｔａｓｋ ｃｏｄｅ’であり，‘ｗｈｅｎ Ｔａｓｋ１ ｉｓ ｃｏｍｐｌｅｔｅ’及び‘ｗｈｅｎ Ｔａｓｋ２ ｉｓ ｃｏｍｐｌｅｔｅ’は，‘ｉｎｐｕｔ ｄａｔａ ｂｕｆｆｅｒ’に対応している。入力データは，コンピュータのメモリに格納されている。コンピュータは，依存情報を抽出し，タスクスケジューラに渡す。つまり，本プログラムが実装されるこのシステムは，‘ｉｎｐｕｔ ｄａｔａ ｂｕｆｆｅｒ’を読み込むことにより，Ｔａｓｋ３がＴａｓｋ１に依存すること，及び‘ｉｎｐｕｔ ｄａｔａ ｂｕｆｆｅｒ’を読み込むことにより，Ｔａｓｋ４がＴａｓｋ２に依存することを自動的に決定することができる。また，コンピュータは，メモリから入力データを読み込み，依存性を示すかっこを検索することにより，すべての依存性，つまり，Ｔａｓｋ３がＴａｓｋ１に依存すること，及びＴａｓｋ４がＴａｓｋ２に依存することを決定してもよい。
【００２３】
本プログラムは，プログラマーに，より大きなバッファのサブ領域の指示を入力させてもよい。サブ領域の入力の表記は，[ａｎｄ]である。その指示により，単一のバッファでの作業を分割してもよい。そのようなデータがプログラマーにより入力される時，コンピュータはその入力をメモリに格納する。その際，コンピュータはメモリからその入力を読み込み，分析する。そして，
[ａｎｄ]を含むように入力が決定されると同時に，コンピュータは，サブ領域のタスクが指示されることを決定する。その後，コンピュータは単一のバッファを２つ又は２つ以上に分割する。
【００２４】
本プログラムは，プログラマーに，バッファの使用に関するいくつかの制約をバイパスする指示を入力させてもよい。バイパスの入力表記の例は，＜−である。本プログラムは，コンピュータに，決定された依存性を考慮して，そのようなバイパスを，自動的に決定させてもよい。
【００２５】
本プログラム又は本プログラムを有するコンピュータは，親タスク及び親タスクを要件とする１つ又は複数の子タスクを決定してもよい。上記の例では，Ｔａｓｋ３をＴａｓｋ１の結果として実行することが要求されているので，Ｔａｓｋ３はＴａｓｋ１に依存している。この場合，Ｔａｓｋ３が親タスクで，Ｔａｓｋ１が子タスクとなる。本発明の好ましい態様では，すべての子タスクの情報をメモリに格納する。コンピュータは，すべての子タスクが終了するか否かを，メモリに格納される子タスクの情報により，決定する。コンピュータは，すべての子タスクが終了されると決定すると同時に，親タスクを実行してもよい。プログラムが，コンピュータに親タスクと子タスクを自動的に決定させ，子タスクが終了した後に親タスクを実行させるので，プログラマーは，タスクとランタイムをスケジューリングする必要がない。
【００２６】
コンピュータのスケジューラは，タスクの依存性のすべてを考慮することにより，実行順序を決定する。コンピュータは，ｃｈａｒａｃｔｅｒ１とｃｈａｒａｃｔｅｒ２が独立するように決定する。コンピュータは，Ｔａｓｋ１と３及びＴａｓｋ２と４が並列的に実行されるように決定する。コンピュータは，低階層システムを使用して，各タスクのランタイムを決定する。
【００２７】
このシステムでは，データはバッファのタグが付されてもよい。プログラムは，コンピュータの読み込み可能な媒体に格納されてもよい。そのような媒体の例としては，ＣＤ−ＲＯＭ，ＣＤ，ＤＶＤ，ＦＤ，ＭＯ，ＵＳＢメモリ，ＳＤカード，ＩＰコア及びＩＣチップがある。つまり，本発明は，上記プログラムを格納する，このようなメモリを有する。
【００２８】
本発明の第２の側面は，複数のタスクの入力手段と，タスクの依存性を入力する手段と，入力されたタスクの依存性により，入力されたすべてのタスクの依存性を自動的に決定する手段，とを含むコンピュータに関する。つまり，コンピュータは，例えば上記プログラムをメインメモリに格納し，プログラムにより提供される操作手段によって，依存性を決定する。コンピュータは，入力手段，出力手段，処理ユニット，及び演算ユニットを含んでもよい。各手段及びユニットは，例えば，バスにより接続されている。
【実施例１】
【００２９】
アニメーションシステムの簡単な実施例として，下記のコードは，２つのアニメーションのアンパックとそれらを操作する混合タスクを，正確な依存性でスケジュールする。
【００３０】
ｂｕｆｆｅｒ＜Ａｎｉｍａｔｉｏｎ＞ａｎｉｍ１
ａｎｉｍ１：＝ｕｎｐａｃｋａｎｉｍ＿ｔａｓｋ（ｉｎｐｕｔ１）
ｂｕｆｆｅｒ＜Ａｎｉｍａｔｉｏｎ＞ａｎｉｍ２
ａｎｉｍ２：＝ｕｎｐａｃｋａｎｉｍ＿ｔａｓｋ（ｉｎｐｕｔ２）
ｂｕｆｆｅｒ＜Ａｎｉｍａｔｉｏｎ＞ｆｉｎａｌ
ｆｉｎａｌ：＝ｕｎｐａｃｋａｎｉｍ＿ｔａｓｋ（ａｎｉｍ１，ａｎｉｍ２）
【００３１】
上記では，タスクと依存性が入力されている。つまり，要件となる各タスクの情報は，かっこ内に表示されている。その要件情報は，依存性に関する。従って，コンピュータは，上記入力データを受けとったときに，タスク及び依存性を決定する。コンピュータは，ｂｕｆｆｅｒ＜Ａｎｉｍａｔｉｏｎ＞ｆｉｎａｌから，タスクがａｎｉｍ１及びａｎｉｍ２を要件とすること決定する。すなわち，このタスクは上記２つのタスクに依存している。
【００３２】
適切に定義されている‘Ａｎｉｍａｔｉｏｎ’データオブジェクトと要件となるタスクコードを考えると，プログラマーは，唯一，データがシステムを移動する方法を特定する必要がある。その時，ランタイムフレームワークは，２つの’ｕｎｐａｃｋａｎｉｍ＿ｔａｓｋ’操作を並列に実行できるように決定することができる。アンパックと混合タスクは以下の関数を実装することによりＣ＋＋言語によって記述することできる。
【００３３】
ｖｏｉｄ＿ｔｌ＿ｂｌｅｎｄ＿ｔａｓｋ（ｔｌｃｏｎｔｅｘｔ＿ｔ ｔｌｃｔｘ，
ｂｕｆｆｅｒ＿ｔ ａｎｉｍ１，
ｂｕｆｆｅｒ＿ｔ ａｎｉｍ２，
ｂｕｆｆｅｒ＿ｔ ｏｕｔｐｕｔ１）；
【００３４】
この実装コードは，スケジューリング又はバッファのロッキングの詳細を配慮することなく行われるように，計算のみに焦点を当てることになる。また，実装コードは，コード型とデータ型の最小集合にのみ依存することになるため，すべてのデータは，関数の引数として渡される必要がある。
【００３５】
ここにあるように，このアニメーションのタイプは，Ｃ＋＋言語クラスになるだろうが，意図的にｕｎｐａｃｋ（）メソッドを組み込んでいない。それどころか，これはタスクのあるデータコンテナであって，メソッドは作動しない。このアーキテクチャ（メソッドは，データアクセスを提供するのであって，作動しない）は，演算関数の依存性を軽減するのに役立つ（そのような依存性は，既存コードをタスクにリファクタリングする時よく問題を起こす）。これにより，より多くの並列化が，最小の努力でより少ないエラーにより導入される。
【実施例２】
【００３６】
今後グラフィックアプリケーションとなりえる，ほんの少し高度な実施例を以下に示す。初めに，位置データが復元され，その後，それは，以下の２つの目的に使用される。第１に，位置データは，詳細なバウンディング形状を計算するボクセル構造を満たすように使用される。第２に，位置データは，光のタンジェントデータと標準データを計算するのに使用される。
【００３７】
ｐｏｓＢｕｆ：＝ｄｅｃｏｍｐ＿ｐｏｓ（ｃｏｍｐｂｕｆｆｅｒ，ｎｕｍＶｅｒｔｓ）
ｔａｎＢｕｆ：＝ｃａｌｃ＿ｔａｎｇｅｎｔｓ（ｐｏｓＢｕｆ，ｎｕｍＶｅｒｔｓ）
ｎｏｒＢｕｆ：＝ｃａｌｃ＿ｎｏｒｍａｌｓ（ｐｏｓＢｕｆ，ｔａｎｂｕｆ，ｎｕｍＶｅｒｔｓ）
ｖｏｘｅｌＢｕｆ：＝ｃａｌｃ＿ｖｏｘｅｌ（ｐｏｓＢｕｆ，ｎｕｍＶｅｒｔｓ）
【００３８】
上記では，タスクと依存性が入力されている。つまり，要件となる各タスクの情報が，かっこ内に表示されている。コンピュータは，入力によりすべてのタスクと依存性を決定する。タスクの‘ｔａｎＢｕｆ’は，‘ｐｏｓＢｕｆ’，つまり‘ｄｅｃｏｍｐ＿ｐｏｓ’に依存している。タスクの‘ｖｏｘｅｌＢｕｆ’は，‘ｐｏｓＢｕｆ’，つまり‘ｄｅｃｏｍｐ＿ｐｏｓ’に依存している。タスク‘ｎｏｒＢｕｆ’は，‘ｐｏｓＢｕｆ’，つまり‘ｄｅｃｏｍｐ＿ｐｏｓ’及び‘ｔａｎＢｕｆ’，つまり‘ｃａｌｃ＿ｔａｎｇｅｎｔｓ’に依存している。次に，コンピュータは，すべてのタスク又はタスクのスケジューリングにランタイムを割り当てる。つまり，コンピュータは，初めに‘ｄｅｃｏｍｐ＿ｐｏｓ’タスクを実行するよう手配し，その時，‘ｃａｌｃ＿ｔａｎｇｅｎｔ’タスクと‘ｃａｌｃ＿ｖｏｘｅｌ’タスクを並列に実行し，その後，‘ｃａｌｃ＿ｎｏｒｍａｌｓ’も実行する。
【００３９】
図１の依存性グラフは，設定されたランタイムスケジューラにより，コード実行時に生成された。これは，システムが，タスク間の依存性を正確に抽出していることを示している。
【実施例３】
【００４０】
この実施例では，より高度な検証として，再帰ソーティングアルゴリズムを使用した。ピボット（通常，右端の値）を選択し，バッファのファストパスを行う整数型バッファから始めて，ピボットが正しい位置になるよう配列し直すために，ピボットの左側へのすべてのエントリーは，より少ない値か等しい値とし，ピボットの右側へのすべてのエントリーは，そのピボットよりもすべて大きな値とする。
【００４１】
この段階では，左側と右側はソートされていないが，同じアルゴリズムをこれらのサブバッファに，再帰的に適用することができる。サブバッファは，結局は，完全にソートされた整数リストになる。
【００４２】
この実施において，再帰‘ソート’タスクは，タスク言語により実装され，‘ｄｏＳｏｒｔ（）’関数（Ｃ言語により実装される）の使用により，実際のデータ操作が行われる。‘ｓｏｒｔ’関数のコードは，以下に示される。
【００４３】
ｔａｓｋ ｂｕｆｆｅｒ＜ｕｎｉｔ３２＿ｔ＞ｏｕｔｐｕｔ：：
ｓｏｒｔ（ｓｉｚｅ＿ｔ ｅｎｔｒｉｅｓ，
ｂｕｆｆｅｒ＜ｕｎｉｔ３２＿ｔ＞ｉｎｐｕｔ）
＃Ｄｉｖｉｄｅ ｕｓｉｎｇ ｔｈｅ ｐｉｖｏｔ
ｓｉｚｅ＿ｔ ｐｉｖＩｄｘ
ｐｉｖＩｄｘ
ｐｉｖＩｄｘ＝ｄｏＳｏｒｔ（ｅｎｔｒｉｅｓ，ｏｕｔｐｕｔ）
＃Ｓｏｒｔ ＬＥＦＴ ｂｕｆｆｅｒ
ｉｆ ｐｉｖＩｄｘ＞１ ｔｈｅｎ
ｂｕｆｆｅｒ ＩＢｕｆ＝ｏｕｔｐｕｔ［０，ｐｉｖＩｄｘ］
ＩＢｕｆ＜−ｓｏｒｔ（ｐｉｖＩｄｘ，ＩＢｕｆ）
ｅｎｄ
＃Ｓｏｒｔ ＲＩＧＨＴ ｂｕｆｆｅｒ
ｉｆ ｐｉｖｏｔＩｄｘ＜ｅｎｔｒｉｅｓ−２ ｔｈｅｎ
ｂｕｆｆｅｒ ｒＢｕｆ ＝ｏｕｔｐｕｔ［ｐｉｖＩｄｘ＋１，ｅｎｔｒｉｅｓ］
ｓｉｚｅ＿ｔ ｒＥｎｔｒｉｅｓ ＝ｅｎｔｒｉｅｓ−ｐｉｖＩｄｘ−１
ｒＢｕｆ ＜− ｓｏｒｔ（ｒＥｎｔｒｉｅｓ，ｒＢｕｆ）
ｅｎｄ
ｅｎｄ
【００４４】
このコードは，いくつかの言語機能を示している。‘ｓｕｂ−ｂｕｆｆｅｒ’，つまり，[ａｎｄ]表記は，より大きなバッファのサブ領域を参照する新しいバッファオブジェクトを生成するのに使用される。この機能は，依存性を追跡させたまま，単一のバッファの作業を分割させる。‘ｉｎ−ｐｌａｃｅ ｂｕｆｆｅｒ ａｓｓｉｇｎｍｅｎｔｓ’，つまり，＜−の表記は，バッファ使用時のいくつかの制約を，バイパスするのに使用される。これは，各段階での中間バッファの割り当てを回避するという，実行上の理由で，使用される。
‘ｃｏｎｔｉｎｕａｔｉｏｎｓ’については，左右のサブバッファの子タスクを起動した後，親タスクのソートが終了する。その時，通常ならば，いずれの依存タスクも実行され得るが，子タスクが完了していなかったために，バッファは完全にソートされないかもしれない。これを克服するために，本システムは，子タスクを連続的に起動する。そのため，依存タスクは，子タスクが完了するまで実行されなくてもよい。
【００４５】
図２は，あるテストデータでアルゴリズムを実行することにより生成される依存性グラフを示す。（赤い）ノードはソートプロセスで同時に生成される子タスクを示す。この場合，チェックタスク（Ｃｈｅｃｋ Ｔａｓｋ）は，ソートタスクが完了するまでスケジュールされない。
【産業上の利用可能性】
【００４６】
本発明は，コンピュータ産業，特に，アミューズメント産業において利用可能である。
【符号の説明】
【００４７】
１ タスク
２ バッファ
３ ソート
【特許請求の範囲】
【請求項１】
複数のタスクを入力する手段と，
前記タスクの依存性を入力する手段と，
前記タスクの前記入力された依存性を用いることにより，すべての前記入力されたタスクの依存性を，自動的に決定する手段として，コンピュータを機能させる，
プログラム。
【請求項２】
前記依存性は，所定のタグにより入力される，請求項１に記載のプログラム。
【請求項３】
前記タスクは，‘ｔａｓｋ ｃｏｄｅ’の入力，‘ｉｎｐｕｔ ｄａｔａ ｂｕｆｆｅｒ’の入力，‘ｏｕｔｐｕｔ ｄａｔａ ｂｕｆｆｅｒ’の入力，及び‘ｉｍｍｅｄｉａｔｅ ｐａｒａｍｅｔｅｒ’の入力により実行され，
前記タスクの前記依存性は，‘ｉｎｐｕｔ ｄａｔａ ｂｕｆｆｅｒ’及び‘ｏｕｔｐｕｔ ｄａｔａ ｂｕｆｆｅｒ’として入力され，
前記タスクの前記依存性は，‘ｉｎｐｕｔ ｄａｔａ ｂｕｆｆｅｒ’の入力及び‘ｏｕｔｐｕｔ ｄａｔａ ｂｕｆｆｅｒ’の入力により決定される，
請求項１に記載のプログラム。
【請求項４】
前記コンピュータを，さらに，
すべての前記入力されたタスクの前記決定された依存性を考慮して，タスクを自動的にスケジューリングする手段として，機能させる
請求項１に記載のプログラム。
【請求項５】
前記依存性を自動的に決定する手段は，
親タスク，及び前記親タスクに必要な一又は複数の子タスクを決定する手段と，
すべての前記子タスクの情報を格納する手段と，
前記親タスクに必要なすべての前記子タスクが実行されるか否かを決定する手段とを含む，
請求項１に記載のプログラム。
【請求項１】
複数のタスクを入力する手段と，
前記タスクの依存性を入力する手段と，
前記タスクの前記入力された依存性を用いることにより，すべての前記入力されたタスクの依存性を，自動的に決定する手段として，コンピュータを機能させる，
プログラム。
【請求項２】
前記依存性は，所定のタグにより入力される，請求項１に記載のプログラム。
【請求項３】
前記タスクは，‘ｔａｓｋ ｃｏｄｅ’の入力，‘ｉｎｐｕｔ ｄａｔａ ｂｕｆｆｅｒ’の入力，‘ｏｕｔｐｕｔ ｄａｔａ ｂｕｆｆｅｒ’の入力，及び‘ｉｍｍｅｄｉａｔｅ ｐａｒａｍｅｔｅｒ’の入力により実行され，
前記タスクの前記依存性は，‘ｉｎｐｕｔ ｄａｔａ ｂｕｆｆｅｒ’及び‘ｏｕｔｐｕｔ ｄａｔａ ｂｕｆｆｅｒ’として入力され，
前記タスクの前記依存性は，‘ｉｎｐｕｔ ｄａｔａ ｂｕｆｆｅｒ’の入力及び‘ｏｕｔｐｕｔ ｄａｔａ ｂｕｆｆｅｒ’の入力により決定される，
請求項１に記載のプログラム。
【請求項４】
前記コンピュータを，さらに，
すべての前記入力されたタスクの前記決定された依存性を考慮して，タスクを自動的にスケジューリングする手段として，機能させる
請求項１に記載のプログラム。
【請求項５】
前記依存性を自動的に決定する手段は，
親タスク，及び前記親タスクに必要な一又は複数の子タスクを決定する手段と，
すべての前記子タスクの情報を格納する手段と，
前記親タスクに必要なすべての前記子タスクが実行されるか否かを決定する手段とを含む，
請求項１に記載のプログラム。
【図１】
【図２】
【図２】
【公開番号】特開２０１２−１２８５５１（Ｐ２０１２−１２８５５１Ａ）
【公開日】平成２４年７月５日（２０１２．７．５）
【国際特許分類】
【外国語出願】
【出願番号】特願２０１０−２７７８１２（Ｐ２０１０−２７７８１２）
【出願日】平成２２年１２月１４日（２０１０．１２．１４）
【出願人】（３０８０３３２８３）株式会社スクウェア・エニックス (173)
【公開日】平成２４年７月５日（２０１２．７．５）
【国際特許分類】
【出願番号】特願２０１０−２７７８１２（Ｐ２０１０−２７７８１２）
【出願日】平成２２年１２月１４日（２０１０．１２．１４）
【出願人】（３０８０３３２８３）株式会社スクウェア・エニックス (173)
[ Back to top ]