(57)【要約】  アクセラレータを用いたタスクの処理を高速化する。アクセラレータ制御装置は、実行可能なタスクを保持するタスク記憶部と、メモリを有するアクセラレータ上で実行するときのメモリへの入出力データ量が相対的に少ないタスクを、実行可能なタスクの中から選択し、選択したタスクに対するメモリにおけるデータ入出力の準備をアクセラレータに指示するデータスケジューラと、選択されたタスクを実行するようにアクセラレータに指示し、選択されたタスクの完了により実行可能となるタスクをタスク記憶部に追加するタスクスケジューラとを備え、データスケジューラは、メモリの使用状況に応じて、タスク記憶部が保持する実行可能なタスクの中から次のタスクの選択と、選択した次のタスクに対するデータ入出力の準備を継続する。
2017131187.tif 000002
【特許請求の範囲】
【請求項１】
実行可能なタスクを保持するタスク記憶部と、
メモリを有するアクセラレータ上で実行するときの前記メモリへの入出力データ量が相対的に少ないタスクを、前記実行可能なタスクの中から選択し、選択したタスクに対する前記メモリにおけるデータ入出力の準備を前記アクセラレータに指示するデータスケジューラと、
前記選択されたタスクを実行するように前記アクセラレータに指示し、前記選択されたタスクの完了により実行可能となるタスクを前記タスク記憶部に追加するタスクスケジューラと、を備え、
前記データスケジューラは、前記メモリの使用状況に応じて、前記タスク記憶部が保持する実行可能なタスクの中から次のタスクの選択と、選択した次のタスクに対するデータ入出力の準備を継続する、
ことを特徴とするアクセラレータ制御装置。
【請求項２】
前記データスケジューラは、前記アクセラレータ上で実行するときに前記メモリへロードすべき入力データ量と、前記メモリから外部のメモリに退避すべき出力データ量の和が相対的に少ないタスクを、前記タスク記憶部が保持するタスクの中から選択する、
請求項１に記載のアクセラレータ制御装置。
【請求項３】
前記データスケジューラは、前記メモリの使用量が所定のしきい値未満の場合、次のタスクの選択と、選択した次のタスクに対するデータ入出力の準備を継続する、
請求項１または２に記載のアクセラレータ制御装置。
【請求項４】
前記タスク記憶部は、
実行可能なタスクであって実行先のアクセラレータが制限されないタスクを保持する第１の記憶部と、
実行先のアクセラレータが制限されたタスクを保持する第２の記憶部と、を有し、
前記データスケジューラは、アクセラレータ上で実行するときのメモリへの入出力データ量が相対的に少ないタスクを、前記第２の記憶部が保持するタスクであって実行先が該アクセラレータに制限されたタスク、および、前記第１の記憶部が保持するタスクの中から選択する、
請求項１ないし３のいずれか１項に記載のアクセラレータ制御装置。
【請求項５】
前記第１の記憶部は、最上流のタスク、または、上流のすべてのタスクの実行が完了したタスクを保持し、
前記第２の記憶部は、実行先のアクセラレータが制限されたタスクとして、上流のタスクの少なくとも１つが該アクセラレータで実行待ちであり、かつ、上流の残りのすべてのタスクの実行が完了したタスクを保持する、
請求項４に記載のアクセラレータ制御装置。
【請求項６】
前記タスクスケジューラは、前記選択されたタスクの実行が完了した場合、前記第１および／または第２の記憶部が保持するタスクを更新する、
請求項５に記載のアクセラレータ制御装置。
【請求項７】
前記データスケジューラまたは前記タスクスケジューラは、前記選択されたタスクに対するデータ入出力の準備が完了した場合、第２の記憶部が保持するタスクを更新する、
請求項５または６に記載のアクセラレータ制御装置。
【請求項８】
実行可能なタスクを記憶部に保持するステップと、
メモリを有するアクセラレータ上で実行するときの前記メモリへの入出力データ量が相対的に少ないタスクを、前記実行可能なタスクの中から選択し、選択したタスクに対する前記メモリにおけるデータ入出力の準備を前記アクセラレータに指示するステップと、
前記選択されたタスクを実行するように前記アクセラレータに指示し、前記選択されたタスクの完了により実行可能となるタスクを前記記憶部に追加するステップと、
前記メモリの使用状況に応じて、前記記憶部が保持する実行可能なタスクの中から次のタスクの選択と、選択した次のタスクに対するデータ入出力の準備を継続するステップと、を含む、
ことを特徴とするアクセラレータ制御方法。
【請求項９】
前記アクセラレータ上で実行するときに前記メモリへロードすべき入力データ量と、前記メモリから外部のメモリに退避すべき出力データ量の和が相対的に少ないタスクを、前記記憶部が保持するタスクの中から選択する、
請求項８に記載のアクセラレータ制御方法。
【請求項１０】
前記メモリの使用量が所定のしきい値未満の場合、次のタスクの選択と、選択した次のタスクに対するデータ入出力の準備を継続する、
請求項８または９に記載のアクセラレータ制御方法。
【請求項１１】
実行可能なタスクであって実行先のアクセラレータが制限されない第１のタスクを前記記憶部に保持するステップと、
実行先のアクセラレータが制限された第２のタスクを前記記憶部に保持するステップと、を含み、
アクセラレータ上で実行するときのメモリへの入出力データ量が相対的に少ないタスクは、前記第２のタスクであって実行先が該アクセラレータに制限されたタスク、および、前記第１のタスクの中から選択される、
請求項８ないし１０のいずれか１項に記載のアクセラレータ制御方法。
【請求項１２】
前記第１のタスクは、最上流のタスク、または、上流のすべてのタスクの実行が完了したタスクであり、
前記第２のタスクは、実行先のアクセラレータが制限されたタスクであって、上流のタスクの少なくとも１つが該アクセラレータで実行待ちであり、かつ、上流の残りのすべてのタスクの実行が完了したタスクである、
請求項１１に記載のアクセラレータ制御方法。
【請求項１３】
前記記憶部が保持する前記第１および／または第２のタスクは、前記選択されたタスクの実行が完了した場合に更新される、
請求項１２に記載のアクセラレータ制御方法。
【請求項１４】
前記記憶部が保持する前記第２のタスクは、前記選択されたタスクに対するデータ入出力の準備が完了した場合に更新される、
請求項１１または１２に記載のアクセラレータ制御方法。
【請求項１５】
実行可能なタスクを記憶部に保持する処理と、
メモリを有するアクセラレータ上で実行するときの前記メモリへの入出力データ量が相対的に少ないタスクを、前記実行可能なタスクの中から選択し、選択したタスクに対する前記メモリにおけるデータ入出力の準備を前記アクセラレータに指示する処理と、
前記選択されたタスクを実行するように前記アクセラレータに指示し、前記選択されたタスクの完了により実行可能となるタスクを前記記憶部に追加する処理と、
前記メモリの使用状況に応じて、前記記憶部が保持する実行可能なタスクの中から次のタスクの選択と、選択した次のタスクに対するデータ入出力の準備を継続する処理と、をコンピュータに実行させる、
ことを特徴とするプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
（関連出願についての記載）
本発明は、日本国特許出願：特願２０１６−０１５３５２号（２０１６年１月２９日出願）の優先権主張に基づくものであり、同出願の全記載内容は引用をもって本書に組み込み記載されているものとする。
本発明はアクセラレータ制御装置、アクセラレータ制御方法およびプログラムに関し、特にアクセラレータを用いた計算を制御するアクセラレータ制御装置、アクセラレータ制御方法およびプログラムに関する。
【背景技術】
【０００２】
近年、衛星画像やセンサデータ等のビックデータをリアルタイムに解析し、未知の現象を発見し、または、将来起こり得る現象を予知ないし予兆することへのニーズが高まっている。ここで、解析対象とされるデータは、センシング精度の向上に伴い大容量化している。しかしながら、個々のオペレータ（ないし事業者）に対して、１００ないし１０００台規模のクラスタ（計算機クラスタ）を占有させることは、コストの観点から困難である。【０００３】
そこで、最近では、上記のリアルタイム解析において、ＧＰＵ（Graphical Processing Unit）等を搭載したアクセラレータが用いられる機会が増えている。特許文献１には、アクセラレータ制御装置の一例が記載されている。図２２に示すように、特許文献１に記載されたアクセラレータ制御装置は、情報処理装置８によって構成される。情報処理装置８は、共有メモリ８１と、共有メモリ８１に接続する複数のアクセラレータ８２１〜８２３とを備えている。【０００４】
共有メモリ８１は、アクセラレータ８２１〜８２３が処理するデータを保持する。アクセラレータ８２１〜８２３は、共有メモリ８１からアクセラレータ８２１〜８２３のメモリ（非図示）に移動されたデータに対して処理を行う。アクセラレータ８２１〜８２３は、処理を完了したデータを再び自身のメモリから共有メモリ８１に移動する。これらのデータの移動と処理は、所望の処理が完了するまで繰り返して行われる。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】特開２０１３−０２５３９２号公報
【発明の概要】
【発明が解決しようとする課題】
【０００６】
上記特許文献の全開示内容は、本書に引用をもって繰り込み記載されているものとする。以下の分析は、本発明者によってなされたものである。【０００７】
特許文献１に記載された技術では、共有メモリからアクセラレータのメモリにデータを移動するのに時間を要するため、アクセラレータを用いた計算が高速に行えないおそれがある。また、同様の理由により、複数のアクセラレータを用いて計算を行う場合、用いるアクセラレータの数に応じて全体の計算時間を短縮できず、スケーラビリティが得られないおそれもある。【０００８】
クラスタ技術を採用する代わりに、ＧＰＵ（Graphical Processing Unit）等を搭載したアクセラレータを用いることにより、例えばノード数を１／１０に削減できる。一方、アクセラレータを用いる場合、クラスタ技術と比較してメモリ容量は１／１０００に減少する。したがって、アクセラレータのメモリ（アクセラレータメモリ）に収まらず、共有メモリ（ないしメインメモリ）とアクセラレータメモリとのデータのやり取りを伴うアウトオブコア（Out-of-Core）処理が増大する。典型的な例では、アクセラレータを用いることにより、処理性能およびメモリ容量は、クラスタ技術の場合におけるこれらの値から以下のように変化する。
処理性能：100ギガフロップ（ＣＰＵ：Central Processing Unit）  ⇒  1テラフロップ（ＧＰＵ）
メモリ容量：1テラバイト（ＣＰＵ）  ⇒ 10ギガバイト（ＧＰＵ）【０００９】
しかながら、アクセラレータにデータを入出力するためのＩ／Ｏ（Input/Output）帯域はＧＰＵの演算性能と比較して極端に狭い。典型的な例では、1テラフロップ（TFlop）の演算性能に対してＩ／Ｏ帯域は32ギガバイト／秒（GB/s）である。したがって、アクセラレータメモリとメインメモリとの間のデータのＩ／Ｏが処理の高速化のボトルネックとなるおそれがある。【００１０】
そこで、メモリを有するアクセラレータを用いたタスクの処理を高速化することが課題となる。本発明の目的は、かかる課題解決に寄与するアクセラレータ制御装置、アクセラレータ制御方法およびプログラムを提供することにある。なお、本発明のその他の課題ないし目的は、後述の発明を実施するための形態の説明において明らかとなる。
【課題を解決するための手段】
【００１１】
本発明の第１の態様に係るアクセラレータ制御装置は、実行可能なタスクを保持するタスク記憶部と、メモリを有するアクセラレータ上で実行するときの前記メモリへの入出力データ量が相対的に少ないタスクを、前記実行可能なタスクの中から選択し、選択したタスクに対する前記メモリにおけるデータ入出力の準備を前記アクセラレータに指示するデータスケジューラと、前記選択されたタスクを実行するように前記アクセラレータに指示し、前記選択されたタスクの完了により実行可能となるタスクを前記タスク記憶部に追加するタスクスケジューラとを備え、前記データスケジューラは、前記メモリの使用状況に応じて、前記タスク記憶部が保持する実行可能なタスクの中から次のタスクの選択と、選択した次のタスクに対するデータ入出力の準備を継続する。【００１２】
本発明の第２の態様に係るアクセラレータ制御方法は、実行可能なタスクを記憶部に保持するステップと、メモリを有するアクセラレータ上で実行するときの前記メモリへの入出力データ量が相対的に少ないタスクを、前記実行可能なタスクの中から選択し、選択したタスクに対する前記メモリにおけるデータ入出力の準備を前記アクセラレータに指示するステップと、前記選択されたタスクを実行するように前記アクセラレータに指示し、前記選択されたタスクの完了により実行可能となるタスクを前記記憶部に追加するステップと、前記メモリの使用状況に応じて、前記記憶部が保持する実行可能なタスクの中から次のタスクの選択と、選択した次のタスクに対するデータ入出力の準備を継続するステップと、を含む。【００１３】
本発明の第３の態様に係るプログラムは、実行可能なタスクを記憶部に保持する処理と、メモリを有するアクセラレータ上で実行するときの前記メモリへの入出力データ量が相対的に少ないタスクを、前記実行可能なタスクの中から選択し、選択したタスクに対する前記メモリにおけるデータ入出力の準備を前記アクセラレータに指示する処理と、前記メモリにおけるデータ入出力の準備が完了すると、前記選択されたタスクを実行するように前記アクセラレータに指示し、前記選択されたタスクの完了により実行可能となるタスクを前記記憶部に追加する処理と、前記メモリの使用状況に応じて、前記記憶部が保持する実行可能なタスクの中から次のタスクの選択と、選択した次のタスクに対するデータ入出力の準備を継続する処理と、をコンピュータに実行させる。なお、プログラムは、非一時的なコンピュータ可読記録媒体（non-transitory computer-readable storage medium）に記録されたプログラム製品として提供することもできる。
【発明の効果】
【００１４】
本発明に係るアクセラレータ制御装置、アクセラレータ制御方法およびプログラムによると、メモリを有するアクセラレータを用いたタスクの処理を高速化することができる。
【図面の簡単な説明】
【００１５】
【図１】一実施形態に係るアクセラレータ制御装置の構成を例示するブロック図である。
【図２】一実施形態に係るアクセラレータ制御装置の動作を例示する図である。
【図３】一実施形態に係るアクセラレータ制御装置の他の構成を例示するブロック図である。
【図４】一実施形態に係るアクセラレータ制御装置の動作を説明するための図である。
【図５】一実施形態に係るアクセラレータ制御装置の動作を例示する図である。
【図６】比較例の動作を説明するための図である。
【図７】一実施形態に係るアクセラレータ制御装置の効果について説明するための図である。
【図８】第１の実施形態に係るアクセラレータ制御装置の構成を例示するブロック図である。
【図９】第１の実施形態に係るアクセラレータ制御装置における予約ＡＰＩ（Application Programming Interface）および実行ＡＰＩを例示する図である。
【図１０】第１の実施形態に係るアクセラレータ制御装置におけるＤＡＧ（Directed Acyclic Graph、有向非巡回グラフ）の構成を例示する図である。
【図１１】第１の実施形態に係るアクセラレータ制御装置におけるデータおよび処理の分割について説明するための図である。
【図１２】第１の実施形態に係るアクセラレータ制御装置におけるデータおよび処理の分割について説明するための図である。
【図１３】第１の実施形態に係るアクセラレータ制御装置のアクセラレータ制御部の構成を例示するブロック図である。
【図１４】第１の実施形態に係るアクセラレータ制御装置におけるメモリ管理テーブルの構成を例示する図である。
【図１５】第１の実施形態に係るアクセラレータ制御装置におけるデータ管理テーブルの構成を例示する図である。
【図１６】第１の実施形態に係るアクセラレータ制御装置の実行不可能サブタスク記憶部が保持するタスクを例示する図である。
【図１７】第１の実施形態に係るアクセラレータ制御装置の動作を例示するフロー図である。
【図１８】第１の実施形態に係るアクセラレータ制御装置の詳細な動作を例示するシーケンス図である。
【図１９】第１の実施形態に係るアクセラレータ制御装置のデータスケジューラの動作を例示するフロー図である。
【図２０】第１の実施形態に係るアクセラレータ制御装置の先読み判定部の動作を例示するフロー図である。
【図２１】第１の実施形態に係るアクセラレータ制御装置の次回サブタスク判定部の動作を例示するフロー図である。
【図２２】特許文献１に記載された関連技術を説明するための図である。
【発明を実施するための形態】
【００１６】
はじめに、一実施形態の概要について説明する。なお、この概要に付記する図面参照符号は、専ら理解を助けるための例示であり、本発明を図示の態様に限定することを意図するものではない。
【００１７】
図１は、一実施形態に係るアクセラレータ制御装置１０の構成を例示するブロック図である。図１を参照すると、アクセラレータ制御装置１０は、タスク記憶部１１、データスケジューラ１２、および、タスクスケジューラ１３を備えている。
【００１８】
タスク記憶部１１は、実行可能なタスク（例えば、図１０のタスク、または、図１１、図１２のサブタスクのうちの実行可能なもの）を保持する。データスケジューラ１２は、メモリを有するアクセラレータ（例えば、図８のアクセラレータメモリを有するアクセラレータ）上で実行するときの当該メモリへの入出力データ量が相対的に少ない（例えば最小の）タスクを、上記実行可能なタスクの中から選択し、選択したタスクに対する当該メモリにおけるデータ入出力の準備をアクセラレータに指示する。タスクスケジューラ１３は、（例えば上記メモリにおけるデータ入出力の準備が完了すると）選択されたタスクを実行するようにアクセラレータに指示するとともに、選択されたタスクの完了により実行可能となるタスク（例えば、図１０のタスク７１の完了により実行可能となるタスク７２）をタスク記憶部１１に追加する。ここで、データスケジューラ１２は、上記メモリの使用状況に応じて、タスク記憶部１１が保持する実行可能なタスクの中から次のタスクの選択と、選択した次のタスクに対するデータ入出力の準備を継続する。
【００１９】
すなわち、アクセラレータ制御装置１０は、アクセラレータのメモリへのデータ入出力量が相対的に少ないタスクを次のタスクとして選択するとともに、当該メモリの使用状況に応じて（例えば余裕がある場合）、選択したタスクに対するデータ入出力の準備を継続する構成を採用する。これにより、アクセラレータメモリと外部メモリとのデータの入出力量を削減すると同時に、アクセラレータメモリと外部メモリとの間のＩ／Ｏ帯域を有効利用することができる。したがって、アクセラレータ制御装置１０によると、メモリを有するアクセラレータを用いたタスクの処理を高速化することが可能となる。
【００２０】
図２は、図１に示すアクセラレータ制御装置１０の動作を例示する図である。図２（ａ）は、ユーザプログラムの処理を示すＤＡＧ（Directed Acyclic Graph、有向非巡回グラフ）を例示する。ここでは、一例として、ＤＡＧの各ノードは、タスクを分割したサブタスク（図１１、図１２参照）を表すものとする。
【００２１】
図２（ｂ）を参照すると、タスクスケジューラ１３とデータスケジューラ１２は並列に動作している。タスクスケジューラ１３は実行可能なサブタスク「１」〜「３」をタスク記憶部１１の実行可能リストに積む。データスケジューラ１２はタスク記憶部１１が保持する実行可能リストの中で最も入力データのアクセラレータ（ないしアクセラレータメモリ）へのＩ／Ｏが小さいサブタスクを選択し、そのサブタスクの実行に必要なデータのＩ／Ｏを行う。例えば、サブタスク「２」の入力データのみがアクセラレータのメモリにキャッシュされている場合、データスケジューラ１２はサブタスク「２」を選択する。また、データスケジューラ１２は、選択したサブタスク「２」のエントリをタスク記憶部１１の実行可能リストから消去する。
【００２２】
図２（ｃ）を参照すると、データスケジューラ１２はサブタスク「２」を実行するための入力データのＩ／Ｏと出力メモリの確保を完了し、それらのメモリ領域をロックし、タスクスケジューラ１３にサブタスク「２」の実行可を通知する。データスケジューラ１２は、タスク記憶部１１の実行可能リストから次にＩ／Ｏを行うべきサブタスクを選択する。ここでは、一例として、データスケジューラ１２はサブタスク「１」を選択したとする。また、タスクスケジューラ１３はサブタスク「２」を実行する。
【００２３】
図２（ｄ）を参照すると、タスクスケジューラ１３はサブタスク「２」の実行を完了し、データスケジューラ１２にサブタスク「２」の実行完了を通知する。データスケジューラ１２は、サブタスク「２」の入出力データのロックを解除する。図２（ａ）のＤＡＧによるとサブタスク「５」が実行可能となるため、タスクスケジューラ１３はサブタスク「５」をタスク記憶部１１の実行可能リストに積む。
【００２４】
以下、同様の処理がタスクスケジューラ１３とデータスケジューラ１２の並列動作によって行われる。なお、複数のアクセラレータが存在する場合、データスケジューラ１２はアクセラレータごとに上記の処理を行う。
【００２５】
このように、タスクスケジューラ１３によるサブタスクの実行が行われる一方で、データスケジューラ１２はアクセラレータのメモリへのデータ入出力量が最小となるサブタスクを次のタスクとして選択し、選択したサブタスクに対するデータ入出力の準備を継続する。これにより、アクセラレータメモリと外部メモリとのデータの入出力を削減し、かつ、アクセラレータメモリと外部メモリとの間のＩ／Ｏ帯域を有効に活用することが可能となる。
【００２６】
図３は、一実施形態に係るアクセラレータ制御装置１０の他の構成を例示するブロック図である。図３を参照すると、タスク記憶部１１は、実行可能なタスク（ないしサブタスク）であって実行先のアクセラレータが制限されないタスクを保持する第１の記憶部１４と、実行先のアクセラレータが制限されたタスクを保持する第２の記憶部１５とを有する。このとき、データスケジューラ１２は、アクセラレータ上で実行するときのメモリへの入出力データ量が相対的に少ない（例えば最小の）タスクを、第１の記憶部１４が保持するタスク、および、第２の記憶部１５が保持するタスクであって実行先が当該アクセラレータに制限されたタスクの中から選択する。
【００２７】
例えば、第１の記憶部１４は、最上流のタスク、または、上流のすべてのタスクの実行が完了したタスクを保持する。一方、第２の記憶部１５は、実行先のアクセラレータが制限されたタスクとして、上流のタスクの少なくとも１つが当該アクセラレータで実行待ち（すなわち、データ入出力の準備が完了し、アクセラレータで実行されるのを待っている状態）であり、かつ、上流の残りのすべてのタスクの実行が完了したタスクを保持する。
【００２８】
図４は、図３に示すアクセラレータ制御装置１０の動作を説明するための図である。ここでは、アクセラレータ５１〜５Ｎ（Ｎは自然数）は、それぞれＧＰＵ１〜Ｎを有するものとする。第１の記憶部１４は、実行先のアクセラレータが制限されないサブタスクを保持している。一方、第２の記憶部１５は、実行先のアクセラレータ（ないしＧＰＵ）が制限されたサブタスクをアクセラレータごとに保持する。第１の記憶部１４および第２の記憶部１５に蓄積されたサブタスクは、「Ｉ／Ｏ待ち」状態である。
【００２９】
データスケジューラ１２は、アクセラレータ（例えばＧＰＵ  １に対応するアクセラレータ）上で実行するときのメモリへの入出力データ量が最小のサブタスクを、第１の記憶部１４が保持するサブタスク（Ready Sub Tasks）、および、第２の記憶部１５が保持するサブタスクであって実行先が当該アクセラレータに制限されたサブタスク（例えばGPU 1 Ready Sub Tasks）の中から選択する。データスケジューラ１２が選択したサブタスクは、当該サブタスクに対するデータ入出力の準備（図４のＩ／Ｏ）が完了すると、対応するＧＰＵに対するキュー（ＦＩＦＯ：First-In First-Out）に格納され、「実行待ち」状態となる。キューに格納されたサブタスクは、対応するアクセラレータのＧＰＵ（例えばGPU 1）で順次実行され（図４のProcessing）、実行が完了すると、「実行完了」状態となる。
【００３０】
図５は、図３に示すアクセラレータ制御装置１０の動作を例示する図である。図５（ａ）は、ユーザプログラムの処理を示すＤＡＧを例示する。ここでは、一例として、ＤＡＧの各ノードは、タスクを分割したサブタスクを表すものとする。図５（ｂ）を参照すると、データスケジューラ１２（またはタスクスケジューラ１３）は、サブタスク「２」をアクセラレータにおいて実行待ちとしたタイミングで、サブタスク「２」が完了したときに実行可能になるサブタスク「５」を第２の記憶部１５が保持する当該アクセラレータ（ないしＧＰＵ）に対応するLocal Queueに追加する。データスケジューラ１２は、サブタスクのスケジュールの際、第１の記憶部１４が保持する実行可能リストと、第２の記憶部１５が保持するスケジュール対象のアクセラレータ（ないしＧＰＵ）に対応するLocal Queueを参照し、これらのリストないしキューが保持するサブタスクの中から、当該アクセラレータ上で実行するときのメモリへの入出力データ量が最小のサブタスクを選択する。ここで、各アクセラレータ内では動作がシリアライズされることになるため、図５に示す状態において、サブタスク「５」を選択しても何ら問題はない。なお、データスケジューラ１２は、サブタスクの選択において他のアクセラレータについては考慮しない。また、データスケジューラ１２（またはタスクスケジューラ１３）は、サブタスク「５」を選択する場合、サブタスク「５」の完了により実行可能になるサブタスクが存在するときには、さらに対応するアクセラレータ（ないしＧＰＵ）に対するLocal Queueに追加する。タスクスケジューラ１３は、サブタスクの完了後、第２の記憶部１５が保持するLocal Queueに該当エントリ（すなわち、実行先のアクセラレータが制限されないサブタスク、例えば上流のすべてのサブタスクの実行が完了したサブタスク）が存在する場合、かかるエントリを第２の記憶部１５から第１の記憶部１４が保持する実行可能リストに移動する。
【００３１】
このように、図３に示すアクセラレータ制御装置１０は、最上流のタスク、または、上流のすべてのタスクの実行が完了したタスクを保持する第１の記憶部１４と、実行先のアクセラレータが制限されたタスクとして、上流のタスクの少なくとも１つが当該アクセラレータで実行待ちであり、かつ、上流の残りのすべてのタスクの実行が完了したタスクを保持する第２の記憶部１５とを有する。また、アクセラレータ制御装置１０はデータスケジューラ１２がアクセラレータ上で実行するときのメモリへの入出力データ量が最小のタスクを、第１の記憶部１４が保持するタスク、および、第２の記憶部１５が保持するタスクであって実行先が当該アクセラレータに制限されたタスクの中から選択する。これにより、メモリを有するアクセラレータを用いたタスクの処理をさらに高速化することが可能となる。なぜなら、データスケジューラ１２は、タスクが実行完了となるよりも前の実行待ちの時点において、当該タスクの完了によって実行が可能となる後段のタスクについても、入出力データの準備を開始するタスクの候補とすることができるからである。
【００３２】
次に、一実施形態に係るアクセラレータ制御装置１０（図１、図３）によってもたらされる効果について、比較例と対比しつつ説明する。
【００３３】
図６は、比較例の動作を説明するための図である。図６を参照すると、比較例においては、上流のサブタスクが完了し、実行可能となったサブタスクに対して、順番に入力データの準備と出力メモリ領域の確保が行われる。
【００３４】
図７は、一実施形態に係るアクセラレータ制御装置１０の効果について説明するための図である。図７を参照すると、ＤＡＧのデータＡ〜Ｃは、それぞれＮ個のデータパーティションに分割されている（Ｎは自然数）。同様に、タスクＡ、Ｂは、それぞれＮ個のサブタスクに分割されている。例えば、サブタスクＳＴａ１〜ＳＴａＮをデータパーティションＤＰａ１〜ＤＰａＮに適用した場合、分割しない場合（すなわち、タスクＡをデータＡに適用した場合）と同一の結果が得られる。ここでは、データＡ、Ｂの双方のすべてのデータパーティションを、同時にアクセラレータメモリに保持することはできないものと仮定する。
【００３５】
図６に示す比較例では、図７のサブタスクを処理する場合、まず、サブタスクＳＴａ１〜ＳＴａＮがＦＩＦＯに積まれる。その後、サブタスクＳＴｂ１〜ＳＴｂＮがＦＩＦＯに積まれる。しかしながら、データＡ、Ｂをアクセラレータのメモリにすべて搭載することは不可能であるため、サブタスクＳＴａ１〜ＳＴａＮの実行において、後に使用されるデータパーティションＤＰｂ１〜ＤＰｂＮの少なくとも一部（例えばデータパーティションＤＰｂｘ）をスワップアウト（Swap Out、すなわちアクセラレータメモリからメインメモリに移動）する必要がある。さらに、サブタスクＳＴｂｘの実行時にスワップアウトされていたデータパーティションＤＰｂｘをスワップイン（Swap In、すなわちメインメモリからアクセラレータメモリに移動）する必要もある。
【００３６】
一方、一実施形態に係るアクセラレータ制御装置１０によると、サブタスクＳＴａ１、ＳＴｂ１を実行した後、サブタスクＳＴａ２、ＳＴｂ２を実行する、というように進めることができ、比較例のようにデータパーティション（例えばデータパーティションＤＰｂｘ）に対するスワップ（Swap、すなわちＩ／Ｏ）が発生しない。したがって、一実施形態によると、アクセラレータとメインメモリとの間のデータのＩ／Ｏを比較例よりも少なくすることができ、処理の高速化を図ることが可能となる。
【００３７】
＜実施形態１＞
次に、第１の実施形態に係るアクセラレータ制御装置について、図面を参照して詳細に説明する。
【００３８】
［構成］
図８は、本実施形態に係るアクセラレータ制御装置１の構成を例示するブロック図である。図８を参照すると、アクセラレータ制御装置１は、アクセラレータ５１〜５３、メインメモリ４、アクセラレータ制御部３、ユーザプログラム２１、および、ＤＡＧ（Directed Acyclic Graph）作成部２２を備えている。アクセラレータ制御装置１は、一例として、ホストコンピュータによって実現される。なお、ユーザプログラム２１は、アクセラレータ制御装置１の外部の構成としてもよい。
【００３９】
アクセラレータ５１〜５３は、計算処理を実行する。
【００４０】
メインメモリ４は、アクセラレータ５１〜５３のメモリリソースの不足により保持できなくなったデータを退避するためのメモリである。
【００４１】
アクセラレータ制御部３は、アクセラレータ５１〜５３を制御する。
【００４２】
ＤＡＧ作成部２２は、ユーザプログラム２１のＡＰＩ（Application Programming Interface）呼び出しにより、ユーザプログラム２１の処理を示すＤＡＧ（Directed Acyclic Graph）を作成してアクセラレータ制御部３に送信する。
【００４３】
図８において、アクセラレータの数は説明の都合上３つとしている。ただし、アクセラレータの数は１つ以上であればよく、図示の態様に限定されない。アクセラレータとは、特に限定されないが、例えばＮＶＩＤＩＡ社のＧＰＵ（Graphical Processing Unit）、Intel社のXeon Phi等である。アクセラレータはコンピュータのＣＰＵ（Central Processing Unit）のコプロセッサであり、例えばコンピュータのＩ／Ｏ（Input/Output）スロットに挿入する形で実装される。
【００４４】
以下では、複数のアクセラレータ５１〜５３についての説明が重複する場合、アクセラレータ５１についてのみ説明する。アクセラレータ５２、５３については、同様の説明があてはまる。
【００４５】
アクセラレータ５１は、データを処理するプロセッサ５１１と、データを格納するアクセラレータメモリ５２１を備えている。ここでは、アクセラレータが有するローカルメモリをアクセラレータメモリという。
【００４６】
ユーザプログラム２１は、アクセラレータ５１〜５３を利用するプログラマ（ユーザ）が作成するアプリケーションプログラム、または、ユーザによって実行されるアプリケーションプログラムである。ユーザプログラム２１は、一例として、ＤＡＧ作成部２２によって提供されるＡＰＩを用いて実装される。ＤＡＧ作成部２２によって提供されるＡＰＩには、例えば、図９に示すように予約ＡＰＩおよび実行ＡＰＩの２種類のＡＰＩが含まれる。
【００４７】
予約ＡＰＩは、図１０に示すＤＡＧのタスク（ないし処理）の１つに対応する。ユーザプログラム２１から予約ＡＰＩが呼び出されると、ＤＡＧ作成部２２は、ＤＡＧに対して１つのタスクと、そのタスクが生成するデータとを追加する。例えば、図１０において、データ６１に対して予約ＡＰＩを用いてタスク７１が呼ばれた場合、ＤＡＧ作成部２２はタスク７１とその出力データであるデータ６２をＤＡＧに付加する。なお、予約ＡＰＩは、タスクを予約するためのＡＰＩである。すなわち、予約ＡＰＩが呼び出された直後には、アクセラレータ５１〜５３でタスクは実行されず、ＤＡＧが生成されるにすぎない。
【００４８】
一方、実行ＡＰＩが呼び出された場合、新たなタスクとそのタスクが生成するデータがＤＡＧに付加される場合とされない場合がある。また、実行ＡＰＩの呼び出しは、それまでに生成されたＤＡＧのタスクの実行をトリガする。実行ＡＰＩに属するタスクは、ユーザプログラム２１内でＤＡＧが処理された後のデータが必要となる場合や、計算結果のデータをアクセラレータメモリにデータオブジェクトとして保持するstoreObjectの場合等である。
【００４９】
予約ＡＰＩや実行ＡＰＩは、図９に示すように１つまたは複数の引数α、β、γ、…を持つ場合がある。これらの引数のうちの１つは、カーネル関数である場合がある。ここで、カーネル関数とは、ユーザプログラム２１がデータに対し実行する処理を示す関数である。ＡＰＩが引数として関数をとるか否かは、予約ＡＰＩや実行ＡＰＩの種類に依存する。予約ＡＰＩや実行ＡＰＩはデータに対し行われる処理のパターンを示し、実際の具体的な処理はユーザプログラム２１内で予約ＡＰＩと実行ＡＰＩの引数として与えられるカーネル関数によって行われる。
【００５０】
カーネル関数を引数とするＡＰＩの一例は、mapである。mapでは、入力データを構成するすべての要素に対してカーネル関数が適用される。ＤＡＧの入力データは、例えば、画像やデータベースのテーブルである。これらのデータにmapが適用された場合、カーネル関数は画像の各画素や、データベースの各エントリに対して個別に適用される。
【００５１】
一方、カーネル関数を必要としないＡＰＩとして、例えば、storeObject，appendObject，readがある。storeObjectは、計算結果をアクセラレータメモリ５２１〜５２３にデータオブジェクトとして保持するＡＰＩである。storeObjectによると、アクセラレータメモリ５２１〜５２３にデータオブジェクトとして保持するデータに名前付けを行うことが可能となる。このとき、storeObjectの引数としてオブジェクトの名前を渡す。また、appendObjectは、すでに存在するオブジェクトの末尾にデータを付加する場合に用いられるＡＰＩである。さらに、readは、アクセラレータ５１〜５３上に存在するデータオブジェクトの内容をユーザ空間に取得するＡＰＩである。
【００５２】
また、ＤＡＧが示すタスクの入力データとして、アクセラレータメモリ５２１〜５２３が保持するデータオブジェクトを指定することが可能である。この場合、予約ＡＰＩや実行ＡＰＩで行う処理の入力データとして、アクセラレータ５１〜５３が保持するオブジェクトの名前を指定する。この名前は、storeObjectを呼び出したプログラムが付けたものである。
【００５３】
ここで、ＤＡＧの各データは、図１１に示すように２つ以上の分割（データパーティション）から構成されてもよい。図１１は、図１０のＤＡＧのデータ６１、タスク７１、データ６２、タスク７２、および、データ６３において、データを２つのデータパーティションで構成した例である。この場合、例えば、タスク７１を、データパーティション６１−１とデータパーティション６１−２の両方に適用すれば、データ６１を分割しない場合の処理と同一の結果が得られる。これは、並列計算ではデータパラレルという処理形態に属し、本発明の属する技術分野の技術者の間では一般的に知られている処理である。図１１では、データパーティション６１−１に対する処理をサブタスク７１−１等と記しているが、サブタスク７１−１の処理内容は図１０におけるタスク７１と同一である。また、複数の分割（データパーティション）に対する処理を、異なるアクセラレータが分散して実行するようにしてもよい。
【００５４】
図１２は、データ６１がデータパーティション６１−１〜６１−４に分割されている場合を示す。ここで、データパーティション６１−１とデータパーティション６１−２は、アクセラレータ５１で処理される。一方、データパーティション６１−３とデータパーティション６１−４は、アクセラレータ５２で処理される。この場合、４つすべてのデータパーティションを１つのアクセラレータで処理する場合と比較して、理想的なケースでは２倍の計算性能が得られる。
【００５５】
なお、以下の説明では、誤解のおそれがない場合、データやタスクを分割する場合について説明し、データやタスクを分割しない場合についての説明を省略する。したがって、データを分割しない場合、以下の説明におけるデータパーティションは分割前の元のデータそのものを意味し、データパーティションに対するサブタスクは元のデータに対するタスクを意味する。
【００５６】
ＤＡＧ作成部２２は、ユーザプログラム２１が予約ＡＰＩと実行ＡＰＩを呼び出す度にＤＡＧを生成する。予約ＡＰＩが呼ばれた場合、ＤＡＧ作成部２２はＤＡＧに対応する処理と出力データを付加する。一方、実行ＡＰＩが呼ばれた場合、ＤＡＧ作成部２２はＤＡＧ処理と出力データの追加が必要であれば追加し、それまで生成したＤＡＧをアクセラレータ制御部３に通知する。
【００５７】
なお、ＤＡＧ作成部２２が作成するＤＡＧは、ユーザプログラム２１が呼び出した予約ＡＰＩや実行ＡＰＩの種類、各ＡＰＩに与えられたカーネル関数を含む。また、ＤＡＧ作成部２２は、ＤＡＧを通知する際、ユーザプログラム２１の識別子を送信する。また、ＤＡＧ作成部２２は、ユーザプログラム２１が終了する場合、アクセラレータ制御部３にユーザプログラム２１の識別子を送信し、ユーザプログラム２１が生成したデータのうちのstoreObjectで保持が指定された以外の中間データを消去するように要求する。
【００５８】
図１３は、図８に示すアクセラレータ制御装置１のアクセラレータ制御部３の構成を例示するブロック図である。図１３を参照すると、アクセラレータ制御部３は、プログラム解析部３１、タスク処理部３２、サブタスク記憶部３６、データ管理部３３、データ管理テーブル３４、および、メモリ管理テーブル３５を備えている。プログラム解析部３１は、ＤＡＧ作成部２２から受信したユーザプログラム２１の処理を示すＤＡＧを解析する。タスク処理部３２は、ＤＡＧの処理を実行する。サブタスク記憶部３６は、ＤＡＧに含まれるサブタスクを実行可能なものと、それ以外のものとに分類して保持する。データ管理部３３は、ＤＡＧの処理に必要なデータの管理や準備を行う。メモリ管理テーブル３５は、アクセラレータのメモリを管理する。データ管理テーブル３４は、アクセラレータのメモリ上のデータを管理する。以下、これらの各構成について詳述する。
【００５９】
メモリ管理テーブル３５は、アクセラレータメモリ５２１〜５２３を管理するテーブルである。アクセラレータメモリ５２１〜５２３は、一定サイズのページに分割して管理される。ページサイズは、例えば、４ＫＢや６４ＫＢである。メモリ管理テーブル３５は、図１４に示すように、各ページに関する情報をエントリとして保持する。各ページの情報は、そのページが属するアクセラレータ番号と、ページ番号と、そのページが使用中であることを示す使用中フラグと、そのページが使用中である場合、ページが保持するデータの識別子を示すデータ番号と、そのページが保持するデータはデータのうちのどのデータパーティションかを示すパーティション番号と、そのページが計算に使用中であり解放することが禁止されていることを示すロックフラグとを保持する。使用中フラグおよびロックフラグは、ブール値である。データの識別子は、ＤＡＧのデータに割り当てられる。
【００６０】
ここでは、一例として、使用中フラグは、ページが使用中である場合には「１」とし、それ以外の場合には「０」とする。また、ロックフラグは、ページの解放が禁止される場合には「１」とし、それ以外の場合には「０」とする。
【００６１】
例えば、図１４に示すメモリ管理テーブル３５の最初のエントリは、アクセラレータ５１が保持するアクセラレータメモリ５２１のページ１は、データパーティション６２−１（すなわち、データ６１の１番目のデータパーティション）によって使用され、このページは現在計算に使用されているためロック中であることを示す。なお、ロック中のページが保持するデータは、メインメモリ４に退避させることができない。
【００６２】
データ管理テーブル３４は、アクセラレータメモリ５２１〜５２３上のデータを管理する。データ管理テーブル３４は、図１５に示すように、ユーザプログラム２１から送信されたＤＡＧ内のデータに関する情報を保持する。各エントリは、データ番号と、各データのパーティション番号と、そのデータが計算済みか否かを示す計算済フラグと、そのデータがメインメモリ４に退避されていることを示すスワップフラグと、そのデータを保持するアクセラレータ番号を示すアクセラレータ番号と、データを保持するアクセラレータのページ番号とを保持する。計算済フラグおよびスワップフラグは、ブール値である。
【００６３】
ここでは、一例として、計算済フラグは計算済である場合には「１」とし、それ以外の場合には「０」とする。また、スワップフラグは、データがメインメモリ４に退避されている場合には「１」とし、それ以外の場合には「０」とする。
【００６４】
例えば、図１５に示すデータ管理テーブル３４の最初のエントリは、データ番号が６２であるデータの１番目のデータパーティション（すなわち、データパーティション６２−１）は既に計算済みであり、アクセラレータ５１のアクセラレータメモリ５２１のページ１に保持されていることを示す。データ管理テーブル３４のエントリが保持するアクセラレータ番号とページ番号より、メモリ管理テーブル３５の該当エントリを参照し、各データが使用するページの情報を検索したり、計算に使用する場合にページをロックしたりすることが可能となる。
【００６５】
プログラム解析部３１は、ＤＡＧ作成部２２から受信したユーザの処理を示すＤＡＧを解析し、データとタスクに分割する。プログラム解析部３１は、ＤＡＧ内のデータについて、データ管理テーブル３４にエントリを作成する。ここで、プログラム解析部３１は、データパーティション数に応じた数のエントリを作成する。なお、データのエントリ作成時点では、まだ各データパーティションの計算が行われていないため、データ管理テーブル３４における計算済フラグは「０」となる。
【００６６】
一方、ＤＡＧの入力データとしてユーザプログラム２１の今回より前のＤＡＧが出力したデータや、ユーザプログラム２１とは別のユーザプログラムが以前に作成し、アクセラレータ上のメモリにストアしたデータオブジェクトのデータについては、エントリがすでに存在している。したがって、プログラム解析部３１は、これらのデータのエントリを新たに作成する必要はない。また、これらのエントリの計算済フラグは、データ管理テーブル３４において「１」にセットされている。
【００６７】
プログラム解析部３１は、ＤＡＧの「タスク」の単位に分割した処理を実行するようにタスク処理部３２に要求する。プログラム解析部３１は、ＤＡＧのタスク１つにつき、データパーティション数に応じてサブタスクの要求を行う。また、プログラム解析部３１は、消去したエントリが使用していたページのメモリ管理テーブル３５の使用中フラグを解除する（例えば、使用中フラグを「１」から「０」に変更する）ことで、アクセラレータメモリ５２１〜５２３を解放する。
【００６８】
データ管理部３３は、データスケジューラ３３１とデータ移動部３３２を備えている。データスケジューラ３３１は、アクセラレータメモリ５２１〜５２３が保持するデータの管理や、メモリの確保を指示する。データ移動部３３２は、アクセラレータ５１〜５３にデータをロードし、アクセラレータメモリ５２１〜５２３の確保を行う。
【００６９】
データスケジューラ３３１は、メモリ管理テーブル３５を参照して、アクセラレータ５１のアクセラレータメモリ５２１を管理する。また、データスケジューラ３３１は、他のアクセラレータ５２、５３についても、同様に管理する。さらに、データスケジューラ３３１は、タスク処理部３２からサブタスクの実行に必要な入力データと出力データの要求を受ける。
【００７０】
実行するサブタスクがＤＡＧの最初のサブタスクである場合、入力データとしてアクセラレータメモリが保持するデータオブジェクトの識別子が指定されている。また、実行するサブタスクが最初のサブタスク以外のサブタスクである場合、ＤＡＧにおける前段のサブタスクが完了していれば、そのサブタスクの出力データがすでに計算されている。いずれの場合も、データ管理テーブル３４の対応するエントリのスワップフラグが「０」であれば、それらのデータパーティションがメインメモリ４に退避されていないため、アクセラレータメモリ上において準備が完了している。
【００７１】
一方、スワップフラグが「１」の場合、データスケジューラ３３１はそのデータパーティションをアクセラレータメモリ上に用意する。データスケジューラ３３１は、メモリ管理テーブル３５を参照し、退避されたデータパーティションをロードするために十分な空きページがいずれかのアクセラレータ５１〜５３に存在するか否かを確認する。十分な空きページが存在する場合、データスケジューラ３３１は退避されたデータをその空きページにロードするようにデータ移動部３３２に要求する。一方、空きページが十分でない場合、データスケジューラ３３１はデータ管理テーブル３４およびメモリ管理テーブル３５を参照し、ロックされていないページが保持するデータパーティションを選択し、そのデータパーティションをメインメモリ４に退避するようにデータ移動部３３２に要求する。ここで、データスケジューラ３３１は、データパーティションを単位として退避の要求を行う。これにより、入力データをロードするためのメモリが確保できるため、データスケジューラ３３１はデータ移動部３３２に入力データのデータパーティションをロードするよう通知する。
【００７２】
データスケジューラ３３１は、サブタスクの出力データに関しては、メモリ管理テーブル３５を参照し、タスク処理部３２が要求するサブタスクの出力データに必要なページ数が空きページから確保可能であれば、メモリを確保するようデータ移動部３３２に要求する。このとき、データスケジューラ３３１はページを確保するアクセラレータも指定する。
【００７３】
一方、空きページから確保可能でない場合、データスケジューラ３３１は、退避された入力データをロードするためにメモリを確保する上述の場合と同様の動作を行う。すなわち、データスケジューラ３３１は、まず、アクセラレータメモリ上でロックされていないページが保持するデータパーティションをメインメモリ４に退避するようにデータ移動部３３２に通知した後、データ移動部３３２に出力データを出力するためのページ数を確保させる。
【００７４】
また、データスケジューラ３３１は、入力データと出力データのメモリ領域をロックするようにデータ移動部３３２に要求する。さらに、データスケジューラ３３１は、タスク処理部３２から処理の完了通知を受信し、データ移動部３３２にロック中のページのロックを解除し、データ管理テーブル３４における出力データの計算済フラグを「１」にセットするように通知する。
【００７５】
なお、タスクスケジューラ３２１が実行を要求するサブタスクの種類によっては、入力データと出力メモリ領域の一方のみを準備すればよい場合がある。例えば、データオブジェクトの内容を取得するreadの実行要求では、出力メモリ領域を用意する必要はない。
【００７６】
データ移動部３３２は、データスケジューラ３３１からの指示を受け、アクセラレータのメモリの確保や、アクセラレータに対するデータの移動を行う。
【００７７】
データ移動部３３２は、データスケジューラ３３１からの指示を受け、アクセラレータのメモリの確保を行い、メモリ管理テーブル３５に確保したメモリのページのエントリを登録する。また、データ移動部３３２は、データ管理テーブル３４のデータパーティションのエントリに、確保したメモリに該当するアクセラレータ番号とページ番号を登録する。
【００７８】
データ移動部３３２は、データスケジューラ３３１からの指示を受け、計算に使用中のページのロックフラグを「１」にセットする。また、データ移動部３３２は、計算が完了したページのロックフラグを「１」から「０」に解除する。さらに、データ移動部３３２は、データ管理テーブル３４において出力データの計算済フラグを「１」にセットする。
【００７９】
データ移動部３３２は、データスケジューラ３３１からの指示を受け、データパーティションをメインメモリ４に退避する。この場合、データ移動部３３２は、退避したデータパーティションのデータ管理テーブル３４のエントリのスワップフラグをセットする。また、データ移動部３３２は、退避したデータパーティションが使用していたページのメモリ管理テーブル３５のエントリの使用中フラグを解除する。
【００８０】
タスク処理部３２は、タスクスケジューラ３２１と、タスク実行部３２２を備えている。タスクスケジューラ３２１は、サブタスクの実行に必要な入力データと出力データのメモリ領域を要求し、また、サブタスクの実行を要求する。また、タスク実行部３２２は、アクセラレータ５１〜５３にサブタスクを実行させる。
【００８１】
タスクスケジューラ３２１は、プログラム解析部３１からＤＡＧに含まれるサブタスクの実行要求を受信する。タスクスケジューラ３２１は、データパーティションに対する処理実行の単位で要求を受信する。タスクスケジューラ３２１は、受信した要求に含まれるサブタスクのうち、ＤＡＧの上流から順番にサブタスクを実行する。図１１で示したＤＡＧでは、サブタスク７１が上流のサブタスクに相当する。ＤＡＧにおいて、上流のサブタスクが完了しなければ、下流の（次段の）サブタスクを実行することができない。タスクスケジューラ３２１は、実行する各サブタスクに必要な入力データと出力データのメモリ領域をデータスケジューラ３３１に要求する。タスクスケジューラ３２１は、データスケジューラ３３１から要求したサブタスクに対するデータとメモリ領域の確保完了を受信後、タスク実行部３２２に該当するサブタスクを実行するために必要なアクセラレータ番号、入力データのアドレス、出力データを書き込むアドレス、または、これらの情報を知るために必要なデータ管理テーブル３４とメモリ管理テーブル３５のエントリ情報を通知し、タスク実行部３２２にサブタスクを実行させる。この処理は、データパーティションの単位で行われる。
【００８２】
要求するサブタスクが、アクセラレータが保持するデータオブジェクトにデータを追記するappendObjectである場合、タスクスケジューラ３２１は追記する情報をタスク実行部３２２に渡す。このデータは、プログラム解析部３１がユーザプログラム２１のＤＡＧを受信する中に含まれている。
【００８３】
タスクスケジューラ３２１は、タスク実行部３２２からサブタスクの完了通知を受信し、サブタスクが完了した際には、入力データと出力データのロックを解除するようにデータスケジューラ３３１に通知する。
【００８４】
さらに、タスクスケジューラ３２１は、タスク実行部３２２に要求したサブタスクがアクセラレータのメモリが保持するデータオブジェクトの内容を取得するreadである場合、readを実行したタスク実行部３２２からデータを取得し、取得したデータを、プログラム解析部３１を介してユーザプログラム２１に伝える。
【００８５】
タスク実行部３２２は、タスクスケジューラ３２１からの指示を受け、タスクスケジューラ３２１から受信したユーザプログラム２１のカーネル関数を用いて指定されたアクセラレータの指定された入力アドレスと出力アドレスに対して処理を行う。また、タスク実行部３２２は、処理完了をタスクスケジューラ３２１に通知する。要求されたサブタスクがappendObjectである場合、タスク実行部３２２は指定されたデータオブジェクトに対してデータを追記する。一方、要求されたサブタスクがデータオブジェクトの内容を取得するreadである場合、タスク実行部３２２は指定されたデータオブジェクトの該当番地から情報を取得してタスクスケジューラ３２１に通知する。
【００８６】
次に、サブタスク記憶部３６が保持する情報と、タスクスケジューラ３２１およびデータスケジューラ３３１の機能のうちの、かかる情報に関連した機能について説明する。
【００８７】
はじめに、サブタスクの分類について説明する。サブタスクには、以下の４つの状態がある。
（１）Ｉ／Ｏ待ち
サブタスクの入力データパーティションの準備および出力データパーティションのメモリ確保を、サブタスクを実行するアクセラレータのメモリに対して行うことを待っている状態（例えば図４のＩ／Ｏ前の状態）
（２）実行待ち
入力データパーティションの準備および出力データパーティションのメモリ確保が完了し、アクセラレータでサブタスクが実行されるのを待っている状態（例えば図４のＩ／Ｏが完了してＦＩＦＯに蓄積された状態）
（３）実行中
サブタスクがアクセラレータ上のプロセッサで実行中の状態（例えば図４のProcessingの状態）
（４）実行完了
サブタスクの実行が完了した状態（例えば図４のProcessingが完了した状態）
【００８８】
以下では、アクセラレータにおけるサブタスクの入力データパーティションの準備および出力データパーティションのメモリ確保を「サブタスクの入出力データの準備」という。
【００８９】
図１３を参照すると、サブタスク記憶部３６は、実行不可能サブタスク記憶部３６１、実行可能サブタスク記憶部３６２、および、アクセラレータ実行可能サブタスク記憶部３６３を有する。
【００９０】
実行不可能サブタスク記憶部３６１が記憶するサブタスクは、ユーザプログラム２１から実行を依頼されたＤＡＧが含むサブタスクの中で、データスケジューラ３３１が入出力データの準備を行う候補とならないサブタスクである。 ここで、入出力データの準備を行う候補とならないサブタスクとは、当該サブタスクより上流のサブタスクにＩ／Ｏ待ちのサブタスクを含むか、２つ以上の実行待ちサブタスクを含み、それらのサブタスクの実行を待っているアクセラレータがすべて同一でない場合である。また、実行待ちのサブタスクとは、データスケジューラ３３１の依頼によるデータ移動部３３２での入出力データの準備が完了し、タスクスケジューラ３２１に実行準備完了の通知が渡ったサブタスクであるが、まだデータスケジューラ３３１の依頼によるサブタスクの実行がタスク実行部３２２で開始されていない（すなわち未実行の）サブタスクである。
【００９１】
図１６は、実行不可能サブタスク記憶部３６１に記憶されるサブタスクの例を示す。例えば、図１６（ａ）においてサブタスク「１」がＩ／Ｏ待ちの場合、サブタスク「２」は実行不可能サブタスク記憶部３６１に記憶される。また、図１６（ｂ）においてサブタスク「ａ」とサブタスク「ｂ」が異なるアクセラレータで実行待ちの場合、サブタスク「ｃ」は実行不可能サブタスク記憶部３６１に記憶される。
【００９２】
実行可能サブタスク記憶部３６２が記憶するサブタスクは、ユーザプログラム２１から実行を依頼されたＤＡＧが含むサブタスクの中で、データスケジューラ３３１が入出力データの準備を行う候補となるサブタスクであり、かつ、入出力データの準備を行うアクセラレータに制限がないサブタスクである。 ここで、入出力データの準備を行うアクセラレータに制限がないサブタスクとは、当該サブタスクがＤＡＧの最も上流のサブタスクであり、それより上流のサブタスクが存在しないか、または、当該サブタスクが依存する当該サブタスクより上流のすべてのサブタスクが実行完了状態であり、当該サブタスクの入力データパーティションがメインメモリ４、または、いずれかのアクセラレータのアクセラレータメモリに保持されているサブタスクである。
【００９３】
アクセラレータ実行可能サブタスク記憶部３６３は、アクセラレータ数分の記憶領域を含む。各アクセラレータに対応する記憶領域に記憶されるサブタスクは、ユーザプログラム２１から実行を依頼されたＤＡＧが含むサブタスクの中で、データスケジューラ３３１が当該アクセラレータでのみ入出力データを準備するサブタスクの候補とすることができるサブタスクである。ここで、ただ１つのアクセラレータでのみ入出力データの準備を行うサブタスクの候補とすることができるサブタスクとは、当該サブタスクが依存するサブタスクがすべて実行待ち、または、実行完了状態であり、それらのサブタスクの少なくとも１つは実行待ちのサブタスクであり、実行待ちのサブタスクはすべて当該サブタスクが記憶される領域に対応するアクセラレータで実行待ちであるサブタスクである。
【００９４】
タスクスケジューラ３２１は、プログラム解析部３１からサブタスクの実行要求を受ける。実行要求を受けたサブタスクはすべてＩ／Ｏ待ち状態である。タスクスケジューラ３２１はサブタスクの中でＤＡＧの一番上流のサブタスクを実行可能サブタスク記憶部３６２に記憶し、それ以外のサブタスクを実行不可能サブタスク記憶部３６１に記憶する。一番上流のサブタスクとは、そのサブタスクが依存するサブタスクが存在しないサブタスクである。タスクスケジューラ３２１はデータスケジューラ３３１に実行可能サブタスク記憶部３６２にサブタスクを記憶したことを通知する。 
【００９５】
また、タスクスケジューラ３２１はデータスケジューラ３３１から入出力データの準備が完了し実行待ちになったサブタスクと、実行を待っているアクセラレータの識別子の通知を受信し、タスク実行部３２２に通知されたサブタスクを通知されたアクセラレータで実行するように要求する。
【００９６】
さらに、タスクスケジューラ３２１は、タスク実行部３２２からサブタスクの実行が完了し実行完了状態になったとの通知を受信し、サブタスクの入力データと出力メモリ領域のロックを解除するようデータスケジューラ３３１に通知する。また、タスクスケジューラ３２１は、実行が完了したサブタスクにより実行不可能サブタスク記憶部３６１からアクセラレータ実行可能サブタスク記憶部３６３、またアクセラレータ実行可能サブタスク記憶部３６３から実行可能サブタスク記憶部３６２に移動すべきサブタスクを探索して移動させる。このとき、タスクスケジューラ３２１はアクセラレータ実行可能サブタスク記憶部３６３と実行可能サブタスク記憶部３６２にサブタスクを移動させたことをデータスケジューラ３３１に通知する。この通知は、サブタスクの移動がアクセラレータ実行可能サブタスク記憶部３６３と実行可能サブタスク記憶部３６２の双方、または、どちらか一方に発生した場合に行う。
【００９７】
データスケジューラ３３１は、タスクスケジューラ３２１からサブタスクの実行完了通知を受信し、サブタスクの入出力データパーティションのロックを解除する。このときロックを解除したアクセラレータに対してデータ移動部３３２にデータの入出力を行わせていない場合、データスケジューラ３３１は後述の「入出力開始処理」を実施する。
【００９８】
また、データスケジューラ３３１はタスクスケジューラ３２１からサブタスクを新たに実行可能サブタスク記憶部３６２またはアクセラレータ実行可能サブタスク記憶部３６３に記憶した通知を受信し、データ移動部３３２にデータの入出力を行わせていないアクセラレータがある場合、それらのすべてのアクセラレータについて後述の「入出力開始処理」を実施する。 
【００９９】
さらに、データスケジューラ３３１は、データ移動部３３２からサブタスクの入出力データの準備完了の通知を受信し、入出力データパーティションを保持するメモリ領域をメモリ管理テーブル３５においてロックし、サブタスクを実行待ち状態とし、タスクスケジューラ３２１にサブタスクが実行待ち状態となったことを通知する。また、データスケジューラ３３１は、サブタスクの入出力データの準備を完了したアクセラレータに対し、次の入出力処理を行わせるための後述の「入出力開始処理」を実施する。
【０１００】
データスケジューラ３３１は、「入出力開始処理」として、データの入出力を行わせていないアクセラレータに対し、次の入出力の要求を行う。データスケジューラ３３１は、先読み判定部３３４を用いてアクセラレータに次に要求する入出力処理を決定する。
【０１０１】
先読み判定部３３４がデータパーティションのスワップアウトを決定した場合、データスケジューラ３３１はアクセラレータが保持するデータパーティションの内、今後のＤＡＧが含むサブタスクの処理で入力データパーティションとして使用しないデータパーティションを選択し、データ移動部３３２に当該データパーティションのメインメモリ４への退避指示を送信する。また、入力データパーティションとして使用しないデータパーティションが存在しない場合、データスケジューラ３３１は入力パーティションとして使用するデータパーティションの内、最近最も参照されなかったデータパーティションを選択し、データ移動部３３２にメインメモリ４への退避指示を送信する。最近最も参照されなかったデータパーティションの選択は、ＬＲＵ（Least Recently Used）の基準に基づく管理方式であり、当該技術分野の技術者にとって一般的な知識である。なお、退避されるデータパーティションを保持するメモリ領域は、メモリ管理テーブル３５によってロックされていないことが必要である。ロックされていないデータパーティションが存在しない場合、データスケジューラ３３１は何も行わない。
【０１０２】
一方、先読み判定部３３４が決定した入出力処理がデータパーティションの準備指示の場合、データスケジューラ３３１は次回サブタスク判定部３３６を用いて当該アクセラレータに対して行わせる入出力データの準備の対象となるサブタスクを決定する。次回サブタスク判定部３３６が決定したサブタスクの入力データパーティションを当該アクセラレータがアクセラレータメモリに保持する場合、データスケジューラ３３１は入力データパーティションをロックする。また、データスケジューラ３３１は、当該アクセラレータが保持しない入力データパーティションの準備と出力データパーティションの確保をデータ移動部３３２に要求する。 
【０１０３】
さらに、データスケジューラ３３１はデータ移動部３３２からデータパーティションのメインメモリ４への退避の完了通知を受信し、退避が完了したアクセラレータに次のデータの入出力を行わせるために入出力開始処理を実行する。
【０１０４】
先読み判定部３３４は、データスケジューラ３３１のために、アクセラレータに要求する入出力処理を決定する。先読み判定部３３４は、メモリ管理テーブル３５を参照し、アクセラレータメモリの使用量がしきい値（例えば、アクセラレータメモリの容量の７０％〜８０％）以上であれば、データスケジューラ３３１にデータパーティションのスワップアウトを行わせる。一方、しきい値未満であれば、先読み判定部３３４は、データスケジューラ３３１にデータパーティションの準備を行わせる。
【０１０５】
次回サブタスク判定部３３６は、データスケジューラ３３１のために、指定されたアクセラレータに対して次に入出力データの準備を行わせるサブタスクを指定する。次回サブタスク判定部３３６は、実行可能サブタスク記憶部３６２と、アクセラレータ実行可能サブタスク記憶部３６３と、データ管理テーブル３４を参照し、入出力データの準備においてアクセラレータへのデータのＩ／Ｏが最小となるサブタスクを、次に入出力データを準備するサブタスクとして指定する。
【０１０６】
具体的には、次回サブタスク判定部３３６は、アクセラレータのデータＩ／Ｏが最小となるサブタスクの選択の際、アクセラレータ実行可能サブタスク記憶部３６３の当該アクセラレータが該当する領域と、実行可能サブタスク記憶部３６２が記憶するサブタスクを全探索することで選択する。次回サブタスク判定部３３６は、探索するサブタスクにおいて、入力データパーティションに関しては指定されたアクセラレータメモリが保持しないデータパーティションをＩ／Ｏが必要なデータパーティションとしてそのデータ容量を総Ｉ／Ｏ容量にカウントする。また、次回サブタスク判定部３３６は、出力データパーティションに関しては、出力データパーティションのデータ容量を確保するとアクセラレータメモリの使用量がしきい値を超える場合、しきい値を超える分の容量を総Ｉ／Ｏ容量にカウントする。これは、サブタスクの入出力データの準備を行う場合、しきい値を超える分のデータ容量に当たるデータパーティションをアクセラレータから退避する必要があるからである。次回サブタスク判定部３３６は、各サブタスクについてカウントした総Ｉ／Ｏ容量が最小となるサブタスクを、アクセラレータのデータＩ／Ｏが最小となるサブタスクとして選択する。
【０１０７】
データ移動部３３２は、データスケジューラ３３１からサブタスクの入出力データの準備と、入出力データの準備を行うアクセラレータの指定を受信し、入出力データの準備を行う。データ移動部３３２は、入力データパーティションに関しては、入力データパーティションを保持するメインメモリ４や他のアクセラレータから入力データパーティションをロードする。一方、データ移動部３３２は、入出力データパーティションに関しては、データパーティションを出力するために必要なメモリ領域を確保する。また、データ移動部３３２は、入出力データパーティションとそれらが使用するメモリ領域に関してメモリ管理テーブル３５とデータ管理テーブル３４が保持する関連情報を更新する。
【０１０８】
さらに、データ移動部３３２はデータスケジューラ３３１からデータパーティションのメインメモリ４への退避の指示を受信し、指定されたデータパーティションをメインメモリ４に退避する。また、データ移動部３３２は、退避したデータパーティションとそれが使用するメモリ領域に関してメモリ管理テーブル３５とデータ管理テーブル３４が保持する関連情報を更新する。
【０１０９】
［動作］
次に、本実施形態の動作について、図８、図１３および図１７を参照して詳細に説明する。図１７は、本実施形態に係るアクセラレータ制御装置１の動作を例示するフロー図である。
【０１１０】
まず、予約ＡＰＩと実行ＡＰＩを用いて作成されたユーザプログラム２１が実行される（ステップＡ１）。
【０１１１】
ユーザプログラム２１が実行ＡＰＩを呼び出すと（ステップＡ２のＹｅｓ）、ＤＡＧ作成部２２は、それまでに生成したＤＡＧを通知する処理に移行する。
【０１１２】
一方、実行ＡＰＩ呼び出しでない場合（ステップＡ２のＮｏ）、ＤＡＧ作成部２２は予約ＡＰＩ呼び出しか否かを確認する（ステップＡ３）。
【０１１３】
予約ＡＰＩ呼び出しである場合（ステップＡ３のＹｅｓ）、ＤＡＧ作成部２２は予約ＡＰＩで指定されたタスクとデータをそれまで生成したＤＡＧに追加する（ステップＡ４）。
【０１１４】
次に、ユーザプログラム２１が終了する場合（ステップＡ５のＹｅｓ）、ユーザプログラム２１の実行は完了する。
【０１１５】
一方、ユーザプログラム２１が終了しない場合（ステップＡ５のＮｏ）、ステップＡ１に戻り、ユーザプログラム２１の実行が継続される。
【０１１６】
実行ＡＰＩが呼び出された場合（ステップＡ２のＹｅｓ）、ＤＡＧ作成部２２は、必要であればＤＡＧに最後のタスクとデータを追加し、ＤＡＧをプログラム解析部３１に通知する（ステップＡ６）。
【０１１７】
プログラム解析部３１は、ＤＡＧを受信し、ＤＡＧを構成するタスクを個別に分解する。次に、プログラム解析部３１は、各サブタスクの実行をタスク処理部３２に要求する（ステップＡ７）。要求されたサブタスクの実行は、データパーティションの単位で行う。例えば、図１１に示すタスク７１では、タスク７１がサブタスク７１−１とサブタスク７１−２の２つから構成されるため、２個の個別のタスクがプログラム解析部３１により生成され、タスク処理部３２に要求される。なお、個別のデータパーティションに対するタスクをサブタスクと呼ぶ代わりに、単にタスクとも呼ぶ。
【０１１８】
タスクスケジューラ３２１は、次のサブタスクの実行に必要な入力データと出力データのメモリ領域をデータ管理部３３に要求する（ステップＡ８）。
【０１１９】
データスケジューラ３３１は、データ管理テーブル３４を参照し、要求されたデータのスワップフラグが「１」にセットされていなければ、データが準備完了であると判断する（ステップＡ９のＹｅｓ）。そして、データスケジューラ３３１は入力データが使用するメモリページのメモリ管理テーブル３５の該当するエントリのロックフラグをセットするようにデータ移動部３３２に要求する。
【０１２０】
一方、要求されたデータのスワップフラグが「１」にセットされている場合（ステップＡ９のＮｏ）、タスクスケジューラ３２１は、メモリ管理テーブル３５を参照し、メインメモリ４に退避されたデータを収容するために十分なメモリ空き領域を保持するアクセラレータが存在するとき、そのアクセラレータに入力データをロードするようにデータ移動部３３２に要求する。データ移動部３３２は、指定されたアクセラレータに入力データをロードし、データ管理テーブル３４の該当するデータのスワップフラグ、アクセラレータ番号、ページ番号を更新する（ステップＡ１０）。また、データスケジューラ３３１は、メモリ管理テーブル３５において、ロードしたデータが使用するページについて、使用中フラグ、データ番号、および、パーティション番号を更新する。また、データスケジューラ３３１は、メモリ管理テーブル３５においてロックフラグを「１」にセットする。
【０１２１】
一方、メインメモリ４に退避されたデータを収容するために十分なメモリ空き領域を保持するアクセラレータが存在しない場合、データスケジューラ３３１はメモリ管理テーブル３５を参照し、ロックフラグがセットされていないページを使用しているデータを選択し、メインメモリ４に退避するようにデータ移動部３３２に要求する。データ移動部３３２は指定されたデータを退避し、データ管理テーブル３４におけるスワップフラグとアクセラレータ番号とページ番号を更新する。データがメインメモリ４に退避されると、そのデータのアクセラレータ番号とページ番号は無効となる。データスケジューラ３３１は、入力データをアクセラレータにロードするために必要なメモリ領域が空くまで、データ退避の要求を継続する。入力データをロードするためのメモリが空きになると、その後のデータをロードする処理は、メインメモリ４に退避されたデータを収容するために十分なメモリ空き領域を保持するアクセラレータが存在する場合のデータのロードの処理と同様である。
【０１２２】
次に、データスケジューラ３３１は、要求されたサブタスクの出力メモリ領域がサブタスクの入力データを保持するアクセラレータに確保可能か否かを確認する（ステップＡ１１）。ここで、空きメモリ領域が十分である場合、確保可能と判断する（ステップＡ１１のＹｅｓ）。
【０１２３】
一方、空きメモリ領域が十分でない場合（ステップＡ１１のＮｏ）、データスケジューラ３３１は、メモリ管理テーブル３５を参照し、ロックフラグがセットされていないページを使用するデータを退避するようデータ移動部３３２に要求する。データ移動部３３２が指定されたデータを退避する動作（ステップＡ１２）は、ステップＡ１０においてデータを退避する場合の動作と同様である。
【０１２４】
アクセラレータに出力データを収容するために十分なメモリ領域が空くと、データスケジューラ３３１は、データ移動部３３２に出力データのメモリを確保するように要求する（ステップＡ１３）。
【０１２５】
データ移動部３３２はメモリを確保し、出力データの該当するデータ管理テーブル３４のエントリにおいてアクセラレータ番号とページ番号を記載する。また、使用しているページのメモリ管理テーブル３５のロックフラグをセットする。データスケジューラ３３１は、入力データと出力データのメモリ領域がアクセラレータ上に用意されると、タスク処理部３２にデータの用意完了を通知する（ステップＡ１４）。
【０１２６】
タスクスケジューラ３２１は、データ用意完了通知を受け、タスク実行部３２２にサブタスクの実行を要求する（ステップＡ１５）。
【０１２７】
実行するサブタスクの要求がユーザプログラム２１により与えられたカーネル関数の実行である場合、タスク実行部３２２はデータを保持するアクセラレータを用いて入力データに対しカーネル関数を実行させ、出力メモリ領域に結果を出力させる。一方、実行するサブタスクの要求がデータのreadである場合、タスク実行部３２２はデータを保持するアクセラレータからデータを読み、タスクスケジューラ３２１に通知する。また、実行するサブタスクの要求がデータを付加するappendである場合、タスク実行部３２２はデータを保持するアクセラレータのメモリ領域に与えられたデータを書き込む。タスクスケジューラ３２１は、タスク実行部３２２によるサブタスクの実行が完了すると、データ管理部３３にサブタスク完了を通知する（ステップＡ１６）。
【０１２８】
タスクスケジューラ３２１は、処理が完了した入力データと出力データについて、メモリ管理テーブル３５におけるロックフラグを解除するとともに、出力データについてデータ管理テーブル３４における該当エントリの計算済フラグをセットするように、データ移動部３３２に要求する（ステップＡ１７）。データ移動部３３２は、要求された処理を行う。
【０１２９】
タスクスケジューラ３２１は、プログラム解析部３１から要求されたＤＡＧのすべてのサブタスクが完了するまで（ステップＡ１８のＮｏ）、サブタスクに関するデータの要求とサブタスクの実行を継続する。
【０１３０】
一方、ＤＡＧの処理が完了すると（ステップＡ１８のＹｅｓ）、ステップＡ１に戻る。
【０１３１】
次に、タスクスケジューラ３２１およびデータスケジューラ３３１の動作のうちの、サブタスク記憶部３６が保持する情報に基づく動作について説明する。
【０１３２】
図１８は、タスクスケジューラ３２１とデータスケジューラ３３１の詳細な動作を例示するシーケンス図である。
【０１３３】
図１８を参照すると、タスクスケジューラ３２１は、プログラム解析部３１からサブタスクの実行要求を受けると、サブタスクの中でＤＡＧの一番上流のサブタスクを実行可能サブタスク記憶部３６２に記憶し、それ以外のサブタスクを実行不可能サブタスク記憶部３６１に記憶する（ステップＢ１）。タスクスケジューラ３２１は、実行可能サブタスク記憶部３６２にサブタスクを記憶したことをデータスケジューラ３３１に通知する（ステップＢ２）。
【０１３４】
データスケジューラ３３１はタスクスケジューラ３２１からサブタスクを新たに実行可能サブタスク記憶部３６２に記憶した通知を受信し、データ移動部３３２にデータの入出力を行わせていないアクセラレータがある場合、それらのすべてのアクセラレータについて「入出力開始処理」を実施する（ステップＢ３）。
【０１３５】
また、データスケジューラ３３１は、データ移動部３３２からサブタスクの入出力データの準備完了の通知を受信し、入出力データパーティションを保持するメモリ領域をメモリ管理テーブル３５においてロックしてサブタスクを実行待ち状態とし（ステップＢ４）、タスクスケジューラ３２１にサブタスクが実行待ち状態となった旨を通知する（ステップＢ５）。さらに、データスケジューラ３３１は、サブタスクの入出力データの準備を完了したアクセラレータに対し、次の入出力処理を行わせるための「入出力開始処理」を実施する（ステップＢ６）。
【０１３６】
タスクスケジューラ３２１は入出力データの準備が完了し実行待ちになったサブタスクと、実行を待っているアクセラレータの識別子の通知をデータスケジューラ３３１から受信し、タスク実行部３２２に通知されたサブタスクを通知されたアクセラレータで実行するように要求する（ステップＢ７）。
【０１３７】
また、タスクスケジューラ３２１は、タスク実行部３２２からサブタスクの実行が完了し実行完了状態になったとの通知を受信し、サブタスクの入力データと出力メモリ領域のロックを解除するようデータスケジューラ３３１に通知する（ステップＢ８）。データスケジューラ３３１は、タスクスケジューラ３２１からサブタスクの実行完了通知を受信し、サブタスクの入出力データパーティションのロックを解除する（ステップＢ９）。
【０１３８】
さらに、タスクスケジューラ３２１は、実行が完了したサブタスクが生じたことにより、実行不可能サブタスク記憶部３６１からアクセラレータ実行可能サブタスク記憶部３６３に移動すべきサブタスクと、アクセラレータ実行可能サブタスク記憶部３６３から実行可能サブタスク記憶部３６２に移動すべきサブタスクを探索して移動させる（ステップＢ１０）。また、タスクスケジューラ３２１はアクセラレータ実行可能サブタスク記憶部３６３と実行可能サブタスク記憶部３６２にサブタスクを移動させたことを、データスケジューラ３３１に通知する（ステップＢ１１）。
【０１３９】
データスケジューラ３３１はタスクスケジューラ３２１からサブタスクを新たに実行可能サブタスク記憶部３６２またはアクセラレータ実行可能サブタスク記憶部３６３に記憶した通知を受信し（ステップＢ１１）、データ移動部３３２にデータの入出力を行わせていないアクセラレータがある場合、それらのすべてのアクセラレータについて「入出力開始処理」を実施する（ステップＢ１２）。
【０１４０】
図１９は、データスケジューラ３３１による上述の「入出力開始処理」（図１８のステップＢ３、Ｂ６、Ｂ１２）を例示するフロー図である。図１９を参照すると、データスケジューラ３３１は、先読み判定部３３４を用いてアクセラレータに次に要求する入出力処理を決定する（ステップＣ１）。
【０１４１】
先読み判定部３３４がデータパーティションのスワップアウトを決定した場合（ステップＣ２のＹｅｓ）、データスケジューラ３３１はアクセラレータが保持するデータパーティションの内、今後のＤＡＧが含むサブタスクの処理で入力データパーティションとして使用しないデータパーティション、または、データスケジューラ３３１は入力データパーティションとして使用するデータパーティションの内、最近最も参照されなかったデータパーティションを選択し、データ移動部３３２にメインメモリ４への退避指示を送信する（ステップＣ３）。
【０１４２】
一方、先読み判定部３３４が決定した入出力処理がデータパーティションの準備指示の場合（ステップＣ２のＮｏ）、データスケジューラ３３１は次回サブタスク判定部３３６を用いて当該アクセラレータに対して行わせる入出力データの準備の対象となるサブタスクを決定する（ステップＣ４）。さらに、データスケジューラ３３１は、次回サブタスク判定部３３６が決定したサブタスクの入力データパーティションを当該アクセラレータがアクセラレータメモリに保持する場合、入力データパーティションをロックする。また、データスケジューラ３３１は、当該アクセラレータが保持しない入力データパーティションの準備と出力データパーティションの確保をデータ移動部３３２に要求する（ステップＣ５）。
【０１４３】
図２０は、先読み判定部３３４の動作（図１９のステップＣ１）を例示するフロー図である。図２０を参照すると、先読み判定部３３４は、メモリ管理テーブル３５を参照する（ステップＤ１）。アクセラレータのメモリの使用量がしきい値以上である場合（ステップＤ２のＹｅｓ）、先読み判定部３３４はデータスケジューラ３３１にデータパーティションのスワップアウトを行わせる（ステップＤ３）。一方、しきい値未満である場合（ステップＤ２のＮｏ）、先読み判定部３３４はデータスケジューラ３３１にデータパーティションの準備を行わせる（ステップＤ４）。
【０１４４】
図２１は、次回サブタスク判定部３３６の動作（図１９のステップＣ４）を例示するフロー図である。図２１を参照すると、次回サブタスク判定部３３６は、アクセラレータ実行可能サブタスク記憶部３６３の当該アクセラレータが該当する領域と、実行可能サブタスク記憶部３６２が記憶するサブタスクを全探索して、１つのサブタスクを選択する（ステップＥ１）。
【０１４５】
次回サブタスク判定部３３６は、選択したサブタスクをアクセラレータ上で実行する際に、アクセラレータメモリに対して必要とされる総Ｉ／Ｏ量を算出する。ここで、次回サブタスク判定部３３６は、総Ｉ／Ｏ量を
「アクセラレータにロードする入力データ量」＋「アクセラレータからスワップアウトされるデータ量」
から算出する。
【０１４６】
次回サブタスク判定部３３６は、入力データパーティションに関しては、指定されたアクセラレータメモリが保持しないデータパーティションをＩ／Ｏが必要なデータパーティションとし、そのデータ量を上式第１項の「アクセラレータにロードする入力データ量」にカウントする（ステップＥ２）。
【０１４７】
また、次回サブタスク判定部３３６は、上式第２項の「アクセラレータからスワップアウトされるデータ量」を
「上式第１項としてロードされる入力データ量」＋「出力領域としてアクセラレータメモリ上に確保すべき領域のサイズ」−「ロード先のアクセラレータメモリのしきい値までの空き容量」
から算出する（ステップＥ３）。一例として、しきい値までの空きメモリ容量を1GBとし、新たにアクセラレータにロードする入力データを500MBとし、確保する出力領域を1GBとした場合、上式第２項の「アクセラレータからスワップアウトされるデータ」量は、
500MB(ロードする入力データ) + 1GB(確保する出力領域) - 1GB(空き領域) = 500MB
となる。
【０１４８】
次回サブタスク判定部３３６は、アクセラレータ実行可能サブタスク記憶部３６３の当該アクセラレータが該当する領域と、実行可能サブタスク記憶部３６２が記憶するすべてのサブタスクについて、上記のステップＥ１〜Ｅ３の処理を完了すると（ステップＥ４のＹｅｓ）、カウントした総Ｉ／Ｏ量が最小となるサブタスクを、アクセラレータのデータＩ／Ｏが最小となるサブタスクとして選択する（ステップＥ５）。
【０１４９】
本実施形態に係るアクセラレータ制御装置１によると、タスクスケジューラ３２１によるサブタスクの実行が行われる一方で、データスケジューラ３３１はアクセラレータメモリへのデータ入出力量が最小となるタスクを次のタスクとして選択し、選択したタスクに対するデータ入出力の準備を継続する。これにより、アクセラレータメモリとメインメモリ４とのデータの入出力を削減しつつ、同時にアクセラレータメモリとメインメモリ４との間のＩ／Ｏ帯域を有効に活用することが可能となる。したがって、本実施形態のアクセラレータ制御装置によるとアクセラレータメモリを有するアクセラレータを用いたタスクの処理において、データＩ／Ｏがボトルネックとなることを回避し、処理を高速化することが可能となる。
【０１５０】
本実施形態では、１つのデータを複数のアクセラレータに分割して保持し、ユーザプログラムの処理を分割し、各データパーティションを保持するアクセラレータに処理を分配して行わせることで、アクセラレータへのデータロードコストを削減し、用いるアクセラレータ数に応じて処理時間を削減することが可能となる。
【０１５１】
＜実施形態２＞
次に、第２の実施形態に係るアクセラレータ制御装置について説明する。本実施形態のアクセラレータ制御装置は、第１の実施形態のアクセラレータ制御装置１（図８〜図２１）と同様の構成を有し、同様の動作を行うことから、差分についてのみ説明する。
【０１５２】
第１の実施形態では、タスクスケジューラ３２１は、タスク実行部３２２からサブタスクの実行（図１８のステップＢ７）が完了した旨の通知を受信したタイミングで、実行が完了したサブタスクが生じたことにより、実行不可能サブタスク記憶部３６１からアクセラレータ実行可能サブタスク記憶部３６３に移動すべきサブタスクと、アクセラレータ実行可能サブタスク記憶部３６３から実行可能サブタスク記憶部３６２に移動すべきサブタスクを探索して、サブタスクを移動させるものとした（図１８のステップＢ１０）。一方、本実施形態では、さらに、タスクスケジューラ３２１がデータスケジューラ３３１からサブタスクを実行待ち状態とした旨の通知を受けたタイミングで（図１８のステップＢ５）、実行待ちのサブタスクが生じたことにより、実行不可能サブタスク記憶部３６１からアクセラレータ実行可能サブタスク記憶部３６３に移動すべきサブタスクを探索して、サブタスクを移動させる。また、タスクスケジューラ３２１はアクセラレータ実行可能サブタスク記憶部３６３にサブタスクを移動させたことをデータスケジューラ３３１に通知する。
【０１５３】
さらに、実行不可能サブタスク記憶部３６１からアクセラレータ実行可能サブタスク記憶部３６３に移動すべきサブタスクの探索と移動を、タスクスケジューラ３２１ではなく、データスケジューラ３３１が行ってもよい。すなわち、データスケジューラ３３１は、入出力データパーティションをロックしたタイミングで（図１８のステップＢ４）、実行待ちのサブタスクが生じたことにより、実行不可能サブタスク記憶部３６１からアクセラレータ実行可能サブタスク記憶部３６３に移動すべきサブタスクを探索して、サブタスクを移動させるようにしてもよい。
【０１５４】
本実施形態によると、タスクスケジューラ３２１は、サブタスクが「実行完了」状態となるよりも前の「実行待ち」状態の時点において（図４参照）、当該サブタスクの完了によって実行が可能となる後段のサブタスクについても、アクセラレータ実行可能サブタスク記憶部３６３に追加する。このとき、データスケジューラ３３１は、タスクが「実行完了」状態となるよりも前の「実行待ち」状態の時点において、当該タスクの完了によって実行が可能となる後段のタスクについても、入出力データの準備を開始するタスクの候補とすることができる。したがって、本実施形態によると、データスケジューラ３３１は、第１の実施形態と比較してさらに早期に後段のサブタスクに対する入出力データの準備に着手することができる。よって、本実施形態によると、第１の実施形態と比較してアクセラレータメモリと外部メモリとの間のＩ／Ｏ（Input/Output）帯域をさらに有効利用することができ、メモリを有するアクセラレータを用いたタスクの処理をさらに高速化することが可能となる。
【０１５５】
＜実施形態３＞
次に、第３の実施形態について説明する。本実施形態では、ＣＰＵ（Central Processing Unit）とメモリを備えたコンピュータに対して、第１、第２の実施形態に係るアクセラレータ制御装置１の動作を行わせる。特に、ＣＰＵに対して、ユーザプログラム２１、ＤＡＧ（Directed Acyclic Graph）作成部２２、プログラム解析部３１、タスクスケジューラ３２１、タスク実行部３２２、データスケジューラ３３１、および、データ移動部３３２の機能を行わせる。一方、コンピュータのメモリを、データ管理テーブル３４、メモリ管理テーブル３５、サブタスク記憶部３６、および、メインメモリ４として使用する。ここで、メモリとは、広義の記憶手段であり、半導体メモリおよび一般に二次記憶と呼ばれるハードディスクやフラッシュディスクを含む。また、アクセラレータはコンピュータのＩ／Ｏ（Input/Output）スロットに挿入する。あるいは、Ｉ／Ｏデバイス用のインターコネクションを用いてアクセラレータとコンピュータを接続することも可能である。
【０１５６】
本発明は、一例として、１つ以上のアクセラレータを含む計算装置の処理高速化といった用途に適用することができる。
【０１５７】
なお、上記特許文献の全開示内容は、本書に引用をもって繰り込み記載されているものとする。本発明の全開示（請求の範囲を含む）の枠内において、さらにその基本的技術思想に基づいて、実施形態の変更・調整が可能である。また、本発明の全開示の枠内において種々の開示要素（各請求項の各要素、各実施形態の各要素、各図面の各要素等を含む）の多様な組み合わせ、ないし、選択が可能である。すなわち、本発明は、請求の範囲を含む全開示、技術的思想にしたがって当業者であればなし得るであろう各種変形、修正を含むことは勿論である。特に、本書に記載した数値範囲については、当該範囲内に含まれる任意の数値ないし小範囲が、別段の記載のない場合でも具体的に記載されているものと解釈されるべきである。
【符号の説明】
【０１５８】
１、１０    アクセラレータ制御装置
３    アクセラレータ制御部
４    メインメモリ
８    情報処理装置
１１    タスク記憶部
１２    データスケジューラ
１３    タスクスケジューラ
１４    第１の記憶部
１５    第２の記憶部
２１    ユーザプログラム
２２    ＤＡＧ作成部
３１    プログラム解析部
３２    タスク処理部
３３    データ管理部
３４    データ管理テーブル
３５    メモリ管理テーブル
３６    サブタスク記憶部
５１〜５３    アクセラレータ
６１〜６６    データ
６１−１〜６１−４、６２−１〜６２−４、６３−１〜６３−４  データパーティション
７１〜７４    タスク
７１−１〜７１−４、７２−１〜７２−４    サブタスク
８１    共有メモリ
３２１    タスクスケジューラ
３２２    タスク実行部
３３１    データスケジューラ
３３２    データ移動部
３３４    先読み判定部
３３６    次回サブタスク判定部
３６１    実行不可能サブタスク記憶部
３６２    実行可能サブタスク記憶部
３６３    アクセラレータ実行可能サブタスク記憶部
５１１〜５１３    プロセッサ
５２１〜５２３    アクセラレータメモリ
８２１〜８２３    アクセラレータ
【図１】
2017131187.tif 000003
【図２】
2017131187.tif 000004
【図３】
2017131187.tif 000005
【図４】
2017131187.tif 000006
【図５】
2017131187.tif 000007
【図６】
2017131187.tif 000008
【図７】
2017131187.tif 000009
【図８】
2017131187.tif 000010
【図９】
2017131187.tif 000011
【図１０】
2017131187.tif 000012
【図１１】
2017131187.tif 000013
【図１２】
2017131187.tif 000014
【図１３】
2017131187.tif 000015
【図１４】
2017131187.tif 000016
【図１５】
2017131187.tif 000017
【図１６】
2017131187.tif 000018
【図１７】
2017131187.tif 000019
【図１８】
2017131187.tif 000020
【図１９】
2017131187.tif 000021
【図２０】
2017131187.tif 000022
【図２１】
2017131187.tif 000023
【図２２】
2017131187.tif 000024
【国際調査報告】
2017131187.tif 000025
2017131187.tif 000026
2017131187.tif 000027