(57)【要約】【課題】マルチスレッドによる並列処理を、より効率的に行うことが可能な情報処理装置及び情報処理方法を提供する。【解決手段】複数の実行ユニットと、他のモジュールと非同期に実行可能な複数の基本モジュールと、当該基本モジュールの実行規則を定義した並列実行制御記述とを記憶する記憶手段と、前記基本モジュールの実行に係る複数のタスクを表した各ノードを、当該タスクの実行順序に応じてエッジで繋ぐとともに、データ依存関係にある他のモジュールのノードと前記エッジで繋いだタスクグラフを生成する生成手段と、前記実行規則に基づき、前記複数の実行ユニットに対する前記複数の基本モジュールの割り当てを制御する制御手段と、を備え、前記実行ユニットの各々は、前記制御手段による割り当てに応じて、処理の対象となった基本モジュールに対し前記生成手段として機能するとともに、当該基本モジュールを前記タスクグラフに従って実行する。【選択図】図２
2015038646.tif 000002
【特許請求の範囲】
【請求項１】
複数の実行ユニットと、
他のモジュールと非同期に実行可能な複数の基本モジュールと、当該基本モジュールの実行規則を定義した並列実行制御記述とを記憶する記憶手段と、
前記基本モジュールの実行に係る複数のタスクを表した各ノードを、当該タスクの実行順序に応じてエッジで繋ぐとともに、データ依存関係にある他のモジュールのノードと前記エッジで繋いだタスクグラフを生成する生成手段と、
前記実行規則に基づき、前記複数の実行ユニットに対する前記複数の基本モジュールの割り当てを制御する制御手段と、
を備え、
前記実行ユニットの各々は、前記制御手段による割り当てに応じて、処理の対象となった基本モジュールに対し前記生成手段として機能するとともに、当該基本モジュールを前記タスクグラフに従って実行することを特徴とする情報処理装置。
【請求項２】
前記実行ユニットの各々は、専用のローカルメモリを有し、
前記生成手段は、基本モジュールの実行に係る複数のタスクのうち、何れかのタスクの実行に必要なデータが同一のローカルメモリに格納されている場合、このローカルメモリに格納されたデータを参照することを規定したタスクグラフを生成することを特徴とする請求項１に記載の情報処理装置。
【請求項３】
前記生成手段は、前記基本モジュールの実行に係る一連のタスクとして、当該基本モジュールの引数を読み出す引数読出タスクと、前記基本モジュールを前記ローカルメモリ上で実行する実行タスクと、前記実行タスクでの実行結果をメインメモリに書き出す書出タスクと、の各々を表したノードを順次生成することを特徴とする請求項２に記載の情報処理装置。
【請求項４】
前記生成手段は、前記引数読出タスクを表したノードの生成に先がけて、前記基本モジュールの引数及び返り値の格納領域を前記ローカルメモリに確保するメモリ確保タスクを表したノードを生成し、前記書出タスクを表したノードの生成後、前記格納領域を前記ローカルメモリから開放するメモリ開放タスクを表したノードを生成することを特徴とする請求項３に記載の情報処理装置。
【請求項５】
前記生成手段は、処理対象の基本モジュールの引数が、他のモジュールの戻り値となり、さらに前記基本モジュール及び前記他のモジュールを実行する実行ユニットが同一で且つ、当該他のモジュールの前記格納領域が未開放である場合に、当該他のモジュールのメモリ開放タスクのノードに接続されたエッジを、前記処理対象の基本モジュールの引数読出タスクのノードに接続し直すことを特徴とする請求項４に記載の情報処理装置。
【請求項６】
前記並列実行制御記述をバイトコードに変換する変換手段を更に備え、
前記生成手段は、前記バイトコードに含まれた前記基本モジュールの命令部分を解釈し、当該基本モジュールの前記タスクグラフを生成することを特徴とする請求項１〜５の何れか一項に記載の情報処理装置。
【請求項７】
前記複数の実行ユニットは、それぞれが個別に構成された複数のＣＰＵであることを特徴とする請求項１に記載の情報処理装置。
【請求項８】
前記複数の実行ユニットは、１つのＣＰＵに内蔵される複数のＣＰＵコアであることを特徴とする請求項１に記載の情報処理装置。
【請求項９】
複数の実行ユニットを備えた情報処理装置で実行される情報処理方法であって、
他のモジュールと非同期に実行可能な複数の基本モジュール各々の実行に係る複数のタスクを表した各ノードを、当該タスクの実行順序に応じてエッジで繋ぐとともに、データ依存関係にある他のモジュールのノードと前記エッジで繋いだタスクグラフを生成する生成ステップと、
前記複数の基本モジュールの実行規則を定義した並列実行制御記述の実行規則に基づいて、前記複数の実行ユニットに対する前記複数の基本モジュールの割り当てを制御する制御ステップと、
を含み、
前記実行ユニットの各々は、前記制御ステップでの割り当てに応じて、処理の対象となった基本モジュールに対して前記生成ステップを実行するとともに、当該基本モジュールを前記タスクグラフに従って実行することを特徴とする情報処理方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明の実施形態は、情報処理装置及び情報処理方法に関する。
【背景技術】
【０００２】
従来、マルチコア向けのプログラム実行モデルとしてマルチスレッド処理が存在している。係るマルチスレッド処理では、実行単位となる複数のスレッドが並列に動作し、メインメモリ上のデータを遣り取りすることによって並列処理を遂行している。
【０００３】
上記並列処理の実行形態の一例としては、複数の実行単位を各実行ユニット（ＣＰＵコア）に割り当てるスケジューラを含むランタイム処理と、各実行ユニット上で動作するスレッドとの２つの要素で構成される。また、並列処理ではスレッド間の同期が重要であり、同期処理が適切でないとデッドロックやデータの整合性が崩れる等の問題が発生する。そこで、従来、スレッドの実行順序をスケジューリングし、このスケジュールに基づいて並列処理を行うことでスレッド間の同期を保持することが行われている。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】特開平１０−２４０７０３号公報
【特許文献２】特開２００８−１２３３１５号公報
【非特許文献】
【０００５】
【非特許文献１】高山征大、境隆二、加藤宣弘、島田智文、「並列プログラミングモデルＭｏｌａｔｏｍｉｕｍ」、情報処理学会論文誌  プログラミング、Ｍａｒ．２０１０  Ｖｏｌ．３  Ｎｏ．１  ｐ．５４−６２
【発明の概要】
【発明が解決しようとする課題】
【０００６】
しかしながら、従来の技術では、メインメモリへのデータの遣り取り（読み取りと書き出し）を基準に処理を切り分けているため、大まかな処理単位でしかスケジューリングを行うことができない。そのため、より詳細な処理（タスク）の中でデータの依存関係が存在したとしても、この依存関係を考慮したスケジューリングを行うことはできず、並列処理の効率化を図る上で改善の余地があった。
【０００７】
本発明は、上記に鑑みてなされたものであって、マルチスレッドによる並列処理を、より効率的に行うことが可能な情報処理装置及び情報処理方法を提供することを目的とする。
【課題を解決するための手段】
【０００８】
実施の形態の情報処理装置は、複数の実行ユニットと、記憶手段と、生成手段と、制御手段とを備える。記憶手段は、他のモジュールと非同期に実行可能な複数の基本モジュールと、当該基本モジュールの実行規則を定義した並列実行制御記述と記憶する。生成手段は、基本モジュールの実行に係る複数のタスクを表した各ノードを、当該タスクの実行順序に応じてエッジで繋ぐとともに、データ依存関係にある他のモジュールのノードとエッジで繋いだタスクグラフを生成する。制御手段は、実行規則に基づき、複数の実行ユニットに対する複数の基本モジュールの割り当てを制御する。さらに、実行ユニットの各々は、制御手段による割り当てに応じて、処理の対象となった基本モジュールに対し生成手段として機能するとともに、当該基本モジュールをタスクグラフに従って実行する。
【図面の簡単な説明】
【０００９】
【図１】図１は、実施形態の情報処理装置の一例を示す図。
【図２】図２は、実施形態のプログラム実行環境を説明するための図。
【図３】図３は、一般的なマルチスレッド処理を示す図。
【図４】図４は、実施形態の並列実行制御記述の一例を示す図。
【図５】図５は、実施形態の情報処理装置が実行するタスクグラフ生成処理の手順を示すフローチャート。
【図６】図６は、図５のタスクグラフ生成処理により、タスクグラフデータが生成される際の動作の一例を説明するための図。
【図７】図７は、図５のタスクグラフ生成処理により、タスクグラフデータが生成される際の動作の一例を説明するための図。
【図８】図８は、図５のタスクグラフ生成処理により、タスクグラフデータが生成される際の動作の一例を説明するための図。
【図９】図９は、実施形態の情報処理装置が実行するタスクグラフ実行処理の手順を示すフローチャート。
【図１０】図１０は、実施形態の情報処理装置でプリフェッチ機能を用いた場合に生成されるタスクグラフデータの一例を示す図。
【発明を実施するための形態】
【００１０】
図１は、本実施形態に係る情報処理装置の一例を示す図である。情報処理装置１００は、ＰＣ（Personal  Computer）や画像（映像）処理装置等として実現され、図１に示すように複数のプロセッサ１１と、メインメモリ１２と、ＨＤＤ１３とを備えている。これらの各部は、共通バスやインターコネクト等の内部バス１４を介し相互に接続されている。
【００１１】
プロセッサ１１は、メインメモリ１２やＨＤＤ１３等の種々の記憶装置に保持されたプログラムコードを解釈し、プログラムとして予め記述された処理を実行する。なお、プロセッサ１１の個数は複数であれば特に問わないものとする。また、各プロセッサ１１は同等の能力を有する必要はなく、処理能力の異なるプロセッサや、別種のコードを処理するプロセッサが含まれていてもよい。
【００１２】
プロセッサ１１は、ＣＰＵコア１１１と、ローカルメモリ１１２と、ＤＭＡエンジン１１３とを有している。ここで、ＣＰＵコア１１１は、プロセッサ１１の核となる演算ユニットであり、並列処理時の実行主体として機能する。ローカルメモリ１１２は、自己のプロセッサ１１専用のメモリであり、ＣＰＵコア１１１のワークエリアとして用いられる。ＤＭＡエンジン１１３は、ローカルメモリ１１２とメインメモリ１２との間のデータ転送（ＤＭＡ転送）を行うための専用モジュールである。
【００１３】
メインメモリ１２は、例えばＤＲＡＭ等の半導体メモリで構成された記憶装置である。プロセッサ１１が処理するプログラムは、処理前に比較的高速にアクセス可能なメインメモリ１２上に読み込まれ、当該プログラムに記述された処理内容に従ってプロセッサ１１からアクセスされる。
【００１４】
ＨＤＤ１３は、例えば磁気ディスク装置であって、後述する並列処理仕様のプログラムＰＧやオペレーティングシステム２５、ランタイムライブラリ２６等（図２参照）を予め記憶している。ＨＤＤ１３は、メインメモリ１２に比べて大容量のデータを記憶する。プロセッサ１１は、ＨＤＤ１３に記憶されたプログラムコードのうち、処理する部分のみをローカルメモリ１１２上に読み出すように構成されている。
【００１５】
また、図示していないが、プロセッサ１１によるプログラムの処理結果等を表示するためのディスプレイや、処理データ等を入力するためのキーボード等の入出力装置がケーブル等で接続される。
【００１６】
プロセッサ１１（ＣＰＵコア１１１）を複数搭載する情報処理装置１００は、複数のプログラムを並列実行することが可能であり、また、一つのプログラム中の複数の処理を並列実行することも可能である。ここで、図２を参照して、情報処理装置１００によって実行される並列処理仕様のプログラムの概要構成について説明する。
【００１７】
図２に示すように、情報処理装置１００によって実行される並列処理仕様のプログラムＰＧは、複数の基本モジュール２１＿ｉ（ｉ＝１〜ｎ）と、この基本モジュール２１＿ｉをどのような順序で実行すべきかを定義する並列実行制御記述２２とで構成される。ここで、図２は、情報処理装置１００のプログラム実行環境を説明するための図である。
【００１８】
いわゆるマルチスレッド処理では、一般的に、図３に示すように、他のスレッドとの間（通信を含む）同期を取りながら、即ち、プログラム全体の整合性を保ちながら、各スレッドが処理を進行させていく。よって、同期の待ち合わせが多発すると、期待した並列性能が得られないことが考えられる。
【００１９】
そこで、本実施形態では、他のモジュールとの同期を取る必要がない、非同期に実行可能な処理単位にプログラムを分割することで、複数の基本モジュール２１＿ｉを作成するとともに、この複数の基本モジュール２１＿ｉの時系列的な実行規則を定義する並列実行制御記述２２を作成する。このように、基本モジュール２１＿ｉとは、他のモジュールと非同期に実行可能な処理単位のモジュールをいう。ここで、基本モジュール２１＿ｉは、例えば、並列プログラミングモデル“Ｍｏｌａｔｏｍｉｕｍ”における“Ａｔｏｍ”に相当する。また、並列実行制御記述２２は、例えば並列プログラミングモデル“Ｍｏｌａｔｏｍｉｕｍ”における“Ｍｏｌ”に相当する。
【００２０】
図４は、並列実行制御記述２２の一例を示す図である。同図において、リストＬ１１〜Ｌ１４の各関数（ｅ（）、ｆ（）、ｇ（）及びｈ（））が、基本モジュール２１＿ｉ（ｉ＝１〜４）に対応する。ここで、各関数は、データの受け渡しがない限りにおいて、それぞれ並列で動作可能なものである。並列実行制御記述２２では、これら関数間のデータの依存関係を、入出力オペランドの繋がりによって定義している。なお、図３では、並列実行制御記述２２を、Ｃ言語に準じた構文を用いて表したが、これに限らないものとする。また、基本モジュール２１＿ｉを記述する言語は特に限らず、例えばＣやＣ＋＋を用いる形態としてもよい。
【００２１】
図２に戻り、プログラムＰＧの実行時において、基本モジュール２１＿ｉはメインメモリ１２内にそのまま取り込まれる。また、並列実行制御記述２２は、トランスレータ２３によりバイトコード２４に変換（コンパイル）された後、メインメモリ１２上に展開される。なお、トランスレータ２３は、何れかのプロセッサ１１（ＣＰＵコア１１１）と所定のプログラムとに協働により実現されるものである。
【００２２】
その結果、プログラムＰＧの実行時のソフトウェア構成は、図２の実行環境ＥＶに示すように、基本モジュール２１＿ｉと、バイトコード２４とを含むことになる。また、実行環境ＥＶは、オペレーティングシステム２５と、ランタイムライブラリ２６とを含む。さらに、実行環境ＥＶは、ランタイムライブラリ２６によってバイトコード２４から生成されるタスクグラフデータ２７を含む。
【００２３】
ここで、オペレーティングシステム２５は情報処理装置１００のハードウェアやタスク（基本モジュール）のスケジューリング（割り当て）など、システム全体の動作を制御、管理する。このオペレーティングシステム２５を導入することで、基本モジュール２１＿ｉを実行する際、プログラマはシステムの雑多な管理から開放され、プログラミングに専念できるとともに、一般的に機機種でも稼動可能なソフトウェアを開発できるというメリットがある。
【００２４】
ランタイムライブラリ２６は、基本モジュール２１＿ｉを情報処理装置１００上で実行する際のＡＰＩ（Application  Interface）などを含み、基本モジュール２１＿ｉを並列処理する際に必要となる排他制御を実現するための機能を有する。
【００２５】
また、ランタイムライブラリ２６は、メインメモリ１２上に展開されたバイトコード２４から、処理の対象となった基本モジュール２１＿ｉに関連する部分を抽出し、当該基本モジュール２１＿ｉに先行する基本モジュール２１＿ｉ（以下、先行モジュールという）の情報と、後続の基本モジュール２１＿ｉ（以下、後続モジュールという）の情報とを含んだタスクグラフデータ２７を生成する。
【００２６】
具体的に、各プロセッサ１１のＣＰＵコア１１１（以下、プロセッサ１１と表記する）は、上記ランタイムライブラリ２６の機能を用いて、自己のプロセッサ１１が対象とする基本モジュール２１＿ｉの実行に必要な一連の処理を５つのタスクの分別し、各々のタスクを表したタスクノードを生成する。ここで、５つのタスクとは、基本モジュール２１＿ｉの引数及び返り値を格納するメモリ領域を自己のプロセッサ１１のローカルメモリ１１２に確保するためのタスク、基本モジュール２１＿ｉの引数を確保したメモリ領域に読み込むためのタスク、基本モジュール２１＿ｉを実際に実行するためのタスク、基本モジュール２１＿ｉの実行結果（返り値）をメインメモリ１２に書き出すためのタスク、基本モジュール２１＿ｉ用に確保したメモリ領域を開放するためのタスクである。
【００２７】
また、各プロセッサ１１は、生成したタスクノードをタスクグラフデータ２７に登録し、各タスクノードのデータ依存関係（引数、返り値）に応じて、タスクノードの間をエッジで接続することで、各タスクを処理する手順を示したタスクフローを定義する。そして、プロセッサ１１の各々は、タスクグラフデータ２７に定義されたタスクフローに基づき、自己のプロセッサ１１が処理を担当する基本モジュール２１＿ｉを実行することで並列処理を実現する。
【００２８】
このように、本実施形態では、バイトコード２４にコンパイルされた並列実行制御記述２２をタスクグラフデータ２７に変換し、これを解釈実行するプロセッサ１１を並列に実行させることによって並列処理を実現している。なお、タスクフローの定義は、各基本モジュール２１＿ｉを実行する前に行う形態としてもよいし、基本モジュール２１＿ｉの実行中、ランタイムタスク等によって逐次生成する形態としてもよい。
【００２９】
次に、図５〜図８を参照し、上述したタスクグラフデータ２７の生成について説明する。ここで、図５は、プロセッサ１１とランタイムライブラリ２６との協働により実行されるタスクグラフ生成処理の手順を示すフローチャートである。
【００３０】
まず、ランタイムライブラリ２６を実行するプロセッサ１１（以下、単にプロセッサ１１という）は、メインメモリ１２上に展開されたバイトコード２４の中から、自己のプロセッサ１１で処理する基本モジュール２１＿ｉ（関数）の記述（命令部分）を解釈し、当該基本モジュール２１＿ｉの引数と、返り値を格納するための変数（以下、単に返り値という）とを特定する（ステップＳ１１）。
【００３１】
プロセッサ１１は、引数及び返り値用のメモリ領域を確保するためのタスクノード（以下、メモリ確保ノードという）を生成し、タスクグラフデータ２７に登録する（ステップＳ１２）。次いで、プロセッサ１１は、自己のプロセッサ１１のローカルメモリ１１２に確保したメモリ領域に、ステップＳ１１で特定した引数を読む込むためのタスクノード（以下、引数読込ノードという）を生成し、タスクグラフデータ２７に登録する（ステップＳ１３）。続いて、プロセッサ１１は、ステップＳ１２で生成したメモリ確保ノードから、ステップＳ１３で生成した引数読込ノードに向けてエッジを接続する（ステップＳ１４）。
【００３２】
次いで、プロセッサ１１は、ステップＳ１１で特定した引数が、先行する他のモジュール２１＿ｉ（先行モジュール）の返り値となっているか否かを判定する（ステップＳ１５）。ここで、プロセッサ１１は、先行モジュールの返り値でないと判定すると（ステップＳ１５；Ｎｏ）、ステップＳ１９に直ちに移行する。
【００３３】
また、ステップＳ１５において、引数が先行モジュールの返り値と判定した場合（ステップＳ１５；Ｙｅｓ）、プロセッサ１１は、その先行モジュールを処理したプロセッサ１１が自己のプロセッサ１１であり、且つ、その先行モジュールの返り値を格納するメモリ領域が未開放か否かを判定する（ステップＳ１６）。
【００３４】
ここで、プロセッサ１１は、ステップＳ１６の条件に該当すると判定した引数について（ステップＳ１６；Ｙｅｓ）、先行モジュール用のメモリ領域を開放するためのタスクノード（以下、メモリ開放ノードという）に接続されたエッジを、その返り値を引数として読み込むための引数読込ノードに接続し直す（ステップＳ１７）。そして、プロセッサ１１は、引数読込ノードに従前から接続されていたメモリ確保ノードとの間のエッジを削除し（ステップＳ１８）、ステップＳ１９に移行する。
【００３５】
また、ステップＳ１６において、先行モジュールを処理したプロセッサ１１が自己のプロセッサ１１でない場合、又は、自己のプロセッサ１１であってもメモリ領域を既に開放していた場合には（ステップＳ１６；Ｎｏ）、ステップＳ１９に移行する。
【００３６】
ステップＳ１９において、プロセッサ１１は、処理対象の基本モジュール２１＿ｉを実行するためのタスクノード（以下、実行ノードという）を生成し、タスクグラフデータ２７に登録する（ステップＳ１９）。続いて、プロセッサ１１は、ステップＳ１３で生成した引数読込ノードから、ステップＳ１９で生成した実行ノードに向けてエッジを接続する（ステップＳ２０）。
【００３７】
次いで、プロセッサ１１は、実行した基本モジュール２１＿ｉの返り値をメインメモリ１２に書き出すためのタスクノード（以下、書出ノードという）を生成し、タスクグラフデータ２７に登録する（ステップＳ２１）。さらに、プロセッサ１１は、ステップＳ１９で生成した実行ノードから、ステップＳ２１で生成した書出ノードに向けてエッジを接続する（ステップＳ２２）。なお、ステップＳ１７でエッジの張り直しを行っていた場合には、実行ノードからエッジの張り直しを行った先行モジュール用のメモリ開放ノードに向けてエッジを接続するものとする。
【００３８】
続いて、プロセッサ１１は、処理対象の基本モジュール２１＿ｉの実行用に確保したローカルメモリ１１２のメモリ領域を開放するためのメモリ開放ノードを生成し、タスクグラフデータ２７に登録する（ステップＳ２３）。そして、プロセッサ１１は、ステップＳ２１で生成した書出ノードから、ステップＳ２３で生成したメモリ開放ノードに向けてエッジを接続し（ステップＳ２４）、処理を終了する。
【００３９】
以下、図６〜図８を参照して、上述したタスクグラフ生成処理の具体例について説明する。なお、図６〜図８では、一例として、図４に示した並列実行制御記述２２のバイトコードからタスクグラフデータ２７を生成する際の動作について説明する。
【００４０】
まず、関数ｅ（）を実行するプロセッサ１１は、リストＬ１１のバイトコードから関数ｅ（）の実行に必要な５つのタスクノードを含んだタスクフローを生成する。
【００４１】
具体的に、関数ｅ（）を実行するプロセッサ１１は、図６に示すように、関数ｅ（）用のメモリ確保ノードＮ１１と、引数（ｗ０、…）を読み込むための引数読込ノードＮ１２とを生成すると、エッジＥ１１によりメモリ確保ノードＮ１１と引数読込ノードＮ１２とを接続する。
【００４２】
ここで、関数ｅ（）は、先行モジュールの返り値を引数としないため、関数ｅ（）を実行するプロセッサ１１は、関数ｅ（）を実行するための実行ノードＮ１３を生成し、エッジＥ１２により引数読込ノードＮ１２と接続する。続いて、関数ｅ（）を実行するプロセッサ１１は、関数ｅ（）の返り値“ｘ０”をメインメモリ１２に書き出すための書出ノードＮ１４を生成し、エッジＥ１３により実行ノードＮ１３と接続する。そして、関数ｅ（）を実行するプロセッサ１１は、メモリ確保ノードＮ１１で確保したメモリ領域を開放するためのメモリ開放ノードＮ１５を生成し、エッジＥ１４により書出ノードＮ１４と接続する。
【００４３】
また、関数ｆ（）を実行するプロセッサ１１は、リストＬ１２のバイトコードから関数ｆ（）の実行に必要な５つのタスクノードを含んだタスクフローを生成する。
【００４４】
具体的に、関数ｆ（）を実行するプロセッサ１１は、図７に示すように、関数ｆ（）用のメモリ確保ノードＮ２１と、各引数（ｘ０〜ｘｎ）を読み込むための引数読込ノードＮ２２＿ｉ（ｉ＝０〜ｎ）とを生成し、エッジＥ２１＿ｉ（ｉ＝０〜ｎ）により、メモリ確保ノードＮ２１と引数読込ノードＮ２２＿ｉとそれぞれ接続する。
【００４５】
ここで、関数ｆ（）は、先行モジュールである関数ｅ（）の返り値“ｘ０”を引数とするため、上述したステップＳ１６の判定対象となる。関数ｅ（）と関数ｆ（）とが異なるプロセッサ１１で実行される場合、又は、同一のプロセッサ１１であっても返り値“ｘ０”を格納するメモリ領域が既に開放済みの場合には、エッジＥ２１＿０は従前のままとなる。
【００４６】
また、関数ｅ（）と関数ｆ（）とが同一のプロセッサ１１で実行され、且つ、返り値“ｘ０”を格納するメモリ領域が未開放の場合、関数ｆ（）を実行するプロセッサ１１は、メモリ開放ノードＮ１５に接続されていたエッジＥ１４を、引数“ｘ０”を読み込むための引数読込ノードＮ２２＿０に接続し直し（破線Ｅ１４１参照）、エッジＥ２１＿０を削除する。
【００４７】
続いて、関数ｆ（）を実行するプロセッサ１１は、関数ｆ（）を実行するための実行ノードＮ２３を生成し、エッジＥ２２＿ｉ（ｉ＝０〜ｎ）により引数読込ノードＮ２２＿ｉのそれぞれと接続する。なお、引数読込ノードＮ２２＿０にて、エッジの繋ぎ替えを行っていた場合、実行ノードＮ２３からメモリ開放ノードＮ１５に向けてエッジ（破線Ｅ２３１参照）を接続することで、このメモリ領域の開放をスケジューリングする。
【００４８】
次いで、関数ｆ（）を実行するプロセッサ１１は、関数ｆ（）の返り値“ｙ”をメインメモリ１２に書き出すための書出ノードＮ２４を生成すると、エッジＥ２３により実行ノードＮ２３と接続する。そして、関数ｆ（）を実行するプロセッサ１１は、メモリ確保ノードＮ２１で確保したメモリ領域を開放するためのメモリ開放ノードＮ２５を生成し、エッジＥ２４により書出ノードＮ２４と接続する。
【００４９】
また、関数ｇ（）を実行するプロセッサ１１は、関数ｇ（）の実行に必要な５つのタスクノードを含んだタスクフローを生成する。このリストＬ１３のバイトコードについては、関数ｇ（）の引数が、関数ｅ（）及び関数ｆ（）に依存しないため、この関数ｇ（）を実行するプロセッサ１１は、他のプロセッサ１１と並列して処理を進めることになる。
【００５０】
具体的に、関数ｇ（）を実行するプロセッサ１１は、図７に示すように、関数ｇ（）用のメモリ確保ノードＮ３１と、各引数（ｗ０〜ｗｎ）を読み込むための引数読込ノードＮ３２＿ｉ（ｉ＝０〜ｎ）とを生成すると、エッジＥ３１＿ｉ（ｉ＝０〜ｎ）によりメモリ確保ノードＮ３１と引数読込ノードＮ３２＿ｉとをそれぞれ接続する。
【００５１】
ここで、関数ｇ（）は、先行モジュールの返り値を引数としないため、関数ｇ（）を実行するプロセッサ１１は、関数ｇ（）を実行するための実行ノードＮ３３を生成し、エッジＥ３２により引数読込ノードＮ３２＿ｉのそれぞれと接続する。続いて、関数ｇ（）を実行するプロセッサ１１は、関数ｇ（）の返り値“ｚ”をメインメモリ１２に書き出すための書出ノードＮ３４を生成し、エッジＥ３３により実行ノードＮ３３と接続する。そして、関数ｇ（）を実行するプロセッサ１１は、メモリ確保ノードＮ３１で確保したメモリ領域を開放するためのメモリ開放ノードＮ３５を生成し、エッジＥ３４により書出ノードＮ３４と接続する。
【００５２】
また、関数ｈ（）を実行するプロセッサ１１は、リストＬ１４のバイトコードから関数ｈ（）の実行に係る５つのタスクノードを含んだタスクフローを生成する。
【００５３】
具体的に、関数ｈ（）を実行するプロセッサ１１は、図８に示すように、関数ｈ（）用のメモリ確保ノードＮ４１と、各引数（ｙ、ｚ）を読み込むための引数読込ノードＮ４２＿ｉ（ｉ＝０，１）とを生成すると、エッジＥ４１＿ｉ（ｉ＝０，１）によりメモリ確保ノードＮ４１と引数読込ノードＮ４２＿ｉとをそれぞれ接続する。
【００５４】
ここで、関数ｈ（）は、先行モジュールである関数ｆ（）の返り値“ｙ”及び関数ｇ（）の返り値“ｚ”を引数とするため、上述したステップＳ１６の判定対象となる。関数ｆ（）と関数ｈ（）とが異なるプロセッサ１１で実行される場合、又は、同一のプロセッサ１１であっても返り値“ｙ”を格納するメモリ領域が開放済みの場合、エッジＥ４１＿０は従前のままとなる。
【００５５】
また、関数ｆ（）と関数ｈ（）とが同一のプロセッサ１１で実行され、且つ、返り値“ｙ”を格納するメモリ領域が未開放の場合、関数ｈ（）を実行するプロセッサ１１は、メモリ開放ノードＮ２５に接続されていたエッジＥ２４を、返り値“ｙ”を引数とする引数読込ノードＮ４２＿０に接続し直し（破線Ｅ２４１参照）、エッジＥ４１＿０を削除する。
【００５６】
また、関数ｇ（）の返り値“ｚ”についても同様に、上述したステップＳ１６の判定対象となる。関数ｇ（）と関数ｈ（）とが異なるプロセッサ１１で実行される場合、又は、同一のプロセッサ１１であっても返り値“ｚ”を格納するメモリ領域が開放済みの場合には、エッジＥ４１＿１は従前のままとなる。関数ｇ（）と関数ｈ（）とが同一のプロセッサ１１で実行され、且つ、返り値“ｚ”を格納するメモリ領域が未開放の場合には、関数ｈ（）を実行するプロセッサ１１は、メモリ開放ノードＮ３５に接続されていたエッジＥ３４を、返り値“ｚ”を引数とする引数読込ノードＮ４２＿１に接続し直し（破線Ｅ３４１参照）、エッジＥ４１＿１を削除する。
【００５７】
続いて、関数ｈ（）を実行するプロセッサ１１は、関数ｈ（）を実行するための実行ノードＮ４３を生成し、エッジＥ４２＿ｉ（ｉ＝０、１）により引数読込ノードＮ４２＿ｉのそれぞれと接続する。なお、引数読込ノードＮ４２＿０又はＮ４２＿１にて、エッジの繋ぎ替えを行っていた場合、実行ノードＮ４３からメモリ開放ノードＮ２５又はＮ３５に向けてエッジ（破線Ｅ４３１、Ｅ４３２参照）を接続することで、メモリ領域の開放をスケジューリングする。
【００５８】
次いで、関数ｈ（）を実行するプロセッサ１１は、関数ｈ（）の返り値“ｖ”をメインメモリ１２に書き出すための書出ノードＮ４４を生成し、エッジＥ４３により実行ノードＮ４３と接続する。
【００５９】
そして、関数ｈ（）を実行するプロセッサ１１は、メモリ確保ノードＮ４１で確保したメモリ領域を開放するためのメモリ開放ノードＮ４５を生成し、エッジＥ４４により書出ノードＮ４４と接続する。
【００６０】
このように、本実施形態の情報処理装置１００では、基本モジュール２１＿ｉの実行に必要な５つのタスクノードを含んだタスクフローを生成し、プロセッサ１１のローカルメモリ１１２に保持された返り値が、他の処理の引数として参照できるような場合には、この返り値を参照して処理を進めるようスケジューリングする。これにより、メインメモリ１２への不要なアクセスを省くことが省くことができるため、並列処理の効率的を図ることができる。
【００６１】
次に、図９を参照し、タスクグラフの実行について説明する。ここで、図８は、プロセッサ１１とランタイムライブラリ２６との協働により実行されるタスクグラフ実行処理の手順を示すフローチャートである。なお、本処理は、各プロセッサ１１において、上述したタスクグラフ生成処理とともに実行されるものである。
【００６２】
まず、プロセッサ１１は、自己のプロセッサ１１が実行する基本モジュール２１＿ｉに係るタスクフローから、先行するタスクノードがなく且つ未実行のタスクノードを選択する（ステップＳ３１）。なお、タスクグラフに実行可能なタスクノードが存在しない場合には、上述したタスクグラフ生成処理を進めるものとする。
【００６３】
続いて、プロセッサ１１は、ステップＳ３１で選択したタスクノードを実行中とする（ステップＳ３２）、実行中としたタスクノードの種別を判別する（ステップＳ３３〜Ｓ３６）。ここで、タスクノードが“メモリ確保ノード”と判別すると（ステップＳ３３；Ｙｅｓ）、プロセッサ１１は、自己のプロセッサ１１のローカルメモリにメモリ領域を確保することが可能か否かを判定する（ステップＳ３７）。
【００６４】
空き容量の不足等によりメモリ領域を確保することができないと判定した場合（ステップＳ３７；Ｎｏ）、プロセッサ１１は、このタスクノード（メモリ確保ノード）を未実行に戻して実行キューの最後に登録し（ステップＳ３８）、ステップＳ３１に再び戻る。また、ステップＳ３７において、メモリ領域を確保することが可能と判定した場合（ステップＳ３７；Ｙｅｓ）、プロセッサ１１は、メモリ確保ノードのタスクを実行することで、ローカルメモリにメモリ領域を確保し（ステップＳ３９）、ステップＳ４４に移行する。
【００６５】
また、タスクノードが“引数読込ノード”と判別した場合（ステップＳ３３；Ｎｏ→ステップＳ３４；Ｙｅｓ）、プロセッサ１１は、引数読込ノードのタスクを実行することで、実行対象の基本モジュール２１＿ｉの引数を読み込むＤＭＡコマンドを発行し、当該引数をステップＳ３９で確保したメモリ領域に格納すると（ステップＳ４０）、ステップＳ４４に移行する。
【００６６】
また、タスクノードが“実行ノード”と判別した場合（ステップＳ３３；Ｎｏ→ステップＳ３４；Ｎｏ→ステップＳ３５；Ｙｅｓ）、プロセッサ１１は、実行ノードのタスクを実行することで、処理対象の基本モジュール２１＿ｉを実行し（ステップＳ４１）、ステップＳ４４に移行する。
【００６７】
また、タスクノードが“書出ノード”と判別した場合（ステップＳ３３；Ｎｏ→ステップＳ３４；Ｎｏ→ステップＳ３５；Ｎｏ→ステップＳ３６；Ｙｅｓ）、プロセッサ１１は、書出ノードのタスクを実行し、ステップＳ４１の実行結果となる返り値を書き出すＤＭＡコマンドを発行することで、返り値をメインメモリ１２に書き出し（ステップＳ４２）、ステップＳ４４に移行する。
【００６８】
また、タスクノードが“メモリ開放ノード”と判別した場合（ステップＳ３３；Ｎｏ→ステップＳ３４；Ｎｏ→ステップＳ３５；Ｎｏ→ステップＳ３６；Ｎｏ）、プロセッサ１１は、メモリ開放ノードのタスクを実行することで、ローカルメモリ１１２に確保したメモリ領域を開放し（ステップＳ４３）、ステップＳ４４に移行する。
【００６９】
ステップＳ４４において、プロセッサ１１は、実行が完了したタスクノードをタスクグラフデータ２７から削除する（ステップＳ４４）。続いて、プロセッサ１１は、自己のプロセッサ１１が実行する基本モジュール２１＿ｉのタスクフローが空となったか、又は、バイトコード２４（タスクグラフデータ２７）全体の処理が終了したか否かを判定する（ステップＳ４５）。ここで、何れの条件も満たさない場合（ステップＳ４５；Ｎｏ）、プロセッサ１１は、ステップＳ３１に再び戻る。また、ステップＳ４５において、何れかの条件を満たした場合、プロセッサ１１は処理を終了する。
【００７０】
以上のように、本実施形態によれば、プロセッサ１１は、タスクグラフ生成処理で生成されたタスクグラフデータ２７（タスクフロー）に従って処理を進めるため、並列処理を効率的に行うことが可能となる。
【００７１】
なお、本発明の実施形態について説明したが、本発明はこれに限定されるものではなく、本発明の主旨を逸脱しない範囲での種々の変更、置換、追加等が可能である。
【００７２】
例えば、上記実施形態では、基本モジュールの引数及び返り値を格納するメモリ領域の確保／開放をタスクノードで表す形態としたが、例えば、プロセッサ１１がプリフェッチ機能を有する場合には、プリフェッチ機能を用いてメモリ領域の確保／開放を行う形態としてもよい。なお、この形態の場合、上述したタスクグラフ生成処理（図５参照）及びタスクグラフ実行処理（図９参照）において、メモリ領域の確保／開放に係るタスクノードを生成する際の処理が不要となる。そのため、例えば図４に示した並列実行制御記述２２のバイトコードに、プリフェッチ機能を有効としたタスクグラフ生成処理の生成結果は、図１０に示すように、図８のタスクグラフデータ２７からメモリ領域の確保及び開放に係るタスクノード及びエッジを削除したものと同等となる。
【００７３】
また、上記実施形態では、ＣＰＵコア１１１がプロセッサ１１のそれぞれ個別に構成されたマルチプロセッサの構成で説明したが、これに限らず、一のプロセッサ１１に複数のＣＰＵコア１１１が内蔵されたマルチコアの構成に適用する形態としてもよい。
【符号の説明】
【００７４】
１００  情報処理装置
１１  プロセッサ
１２  メインメモリ
１３  ＨＤＤ
１４  内部バス
２１＿ｉ  基本モジュール
２２  並列実行制御記述
２３  トランスレータ
２４  バイトコード
２５  オペレーティングシステム
２６  ランタイムライブラリ
２７  タスクグラフデータ
【図１】
2015038646.tif 000003
【図２】
2015038646.tif 000004
【図３】
2015038646.tif 000005
【図４】
2015038646.tif 000006
【図５】
2015038646.tif 000007
【図６】
2015038646.tif 000008
【図７】
2015038646.tif 000009
【図８】
2015038646.tif 000010
【図９】
2015038646.tif 000011
【図１０】
2015038646.tif 000012
【手続補正書】
【提出日】平成23年12月22日(2011.12.22)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
複数の実行ユニットと、
他のモジュールと非同期に実行可能な複数の基本モジュールと、当該基本モジュールの実行規則を定義した並列実行制御記述とを記憶する記憶手段と、
前記複数の基本モジュールの実行時に、当該基本モジュールの実行に係るタスクとして、引数を読み出す引数読出タスクと返り値を書き出す書出タスクとを少なくとも含む複数のタスクの各々を表した各ノードを、当該タスクの実行順序に応じてエッジで繋ぐとともに、データ依存関係にある他のモジュールのノードと前記エッジで繋いだタスクグラフを生成する生成手段と、
前記実行規則に基づき、前記複数の実行ユニットに対する前記複数の基本モジュールの割り当てを制御する制御手段と、
を備え、
前記実行ユニットの各々は、前記制御手段による割り当てに応じて、処理の対象となった基本モジュールに対し前記生成手段として機能するとともに、当該基本モジュールを前記タスクグラフに従って実行することを特徴とする情報処理装置。
【請求項２】
前記実行ユニットの各々は、専用のローカルメモリを有し、
前記生成手段は、基本モジュールの実行に係る複数のタスクのうち、何れかのタスクの実行に必要なデータが同一のローカルメモリに格納されている場合、このローカルメモリに格納されたデータを参照することを規定したタスクグラフを生成することを特徴とする請求項１に記載の情報処理装置。
【請求項３】
前記生成手段は、前記基本モジュールの実行に係るタスクとして、前記基本モジュールを前記ローカルメモリ上で実行する実行タスクを表したノードを生成することを特徴とする請求項２に記載の情報処理装置。
【請求項４】
前記生成手段は、前記引数読出タスクを表したノードの生成に先がけて、前記基本モジュールの引数及び返り値の格納領域を前記ローカルメモリに確保するメモリ確保タスクを表したノードを生成し、前記書出タスクを表したノードの生成後、前記格納領域を前記ローカルメモリから開放するメモリ開放タスクを表したノードを生成することを特徴とする請求項３に記載の情報処理装置。
【請求項５】
前記生成手段は、処理対象の基本モジュールの引数が、他のモジュールの戻り値となり、さらに前記基本モジュール及び前記他のモジュールを実行する実行ユニットが同一で且つ、当該他のモジュールの前記格納領域が未開放である場合に、当該他のモジュールのメモリ開放タスクのノードに接続されたエッジを、前記処理対象の基本モジュールの引数読出タスクのノードに接続し直すことを特徴とする請求項４に記載の情報処理装置。
【請求項６】
前記並列実行制御記述をバイトコードに変換する変換手段を更に備え、
前記生成手段は、前記バイトコードに含まれた前記基本モジュールの命令部分を解釈し、当該基本モジュールの前記タスクグラフを生成することを特徴とする請求項１〜５の何れか一項に記載の情報処理装置。
【請求項７】
前記複数の実行ユニットは、それぞれが個別に構成された複数のＣＰＵであることを特徴とする請求項１に記載の情報処理装置。
【請求項８】
前記複数の実行ユニットは、１つのＣＰＵに内蔵される複数のＣＰＵコアであることを特徴とする請求項１に記載の情報処理装置。
【請求項９】
複数の実行ユニットを備えた情報処理装置で実行される情報処理方法であって、
他のモジュールと非同期に実行可能な複数の基本モジュールの実行時に、当該基本モジュールの実行に係るタスクとして、引数を読み出す引数読出タスクと返り値を書き出す書出タスクとを少なくとも含む複数のタスクの各々を表した各ノードを、当該タスクの実行順序に応じてエッジで繋ぐとともに、データ依存関係にある他のモジュールのノードと前記エッジで繋いだタスクグラフを生成する生成ステップと、
前記複数の基本モジュールの実行規則を定義した並列実行制御記述の実行規則に基づいて、前記複数の実行ユニットに対する前記複数の基本モジュールの割り当てを制御する制御ステップと、
を含み、
前記実行ユニットの各々は、前記制御ステップでの割り当てに応じて、処理の対象となった基本モジュールに対して前記生成ステップを実行するとともに、当該基本モジュールを前記タスクグラフに従って実行することを特徴とする情報処理方法。
【手続補正２】
【補正対象書類名】明細書
【補正対象項目名】０００８
【補正方法】変更
【補正の内容】
【０００８】
実施の形態の情報処理装置は、複数の実行ユニットと、記憶手段と、生成手段と、制御手段とを備える。記憶手段は、他のモジュールと非同期に実行可能な複数の基本モジュールと、当該基本モジュールの実行規則を定義した並列実行制御記述と記憶する。生成手段は、前記複数の基本モジュールの実行時に、当該基本モジュールの実行に係るタスクとして、引数を読み出す引数読出タスクと返り値を書き出す書出タスクとを少なくとも含む複数のタスクの各々を表した各ノードを、当該タスクの実行順序に応じてエッジで繋ぐとともに、データ依存関係にある他のモジュールのノードと前記エッジで繋いだタスクグラフを生成する。制御手段は、実行規則に基づき、複数の実行ユニットに対する複数の基本モジュールの割り当てを制御する。さらに、実行ユニットの各々は、制御手段による割り当てに応じて、処理の対象となった基本モジュールに対し生成手段として機能するとともに、当該基本モジュールをタスクグラフに従って実行する。