データ処理スケジューリング装置、方法及びプログラム
【課題】コ・プロセッサにデータを転送して処理させるシステムにおいて、データ転送やデータ処理の待ち時間を短縮し、処理効率を向上させる。
【解決手段】ホストは、処理対象のデータを複数のチャンクに分割し、各チャンクのデータ転送時間とデータ処理時間を取得し、各チャンクのデータ転送時間とデータ処理時間の大小関係に基づいて、各チャンクをコ・プロセッサに処理させる順番を決定し、決定した順番に従って、各チャンクをコ・プロセッサに転送して処理させる。
【解決手段】ホストは、処理対象のデータを複数のチャンクに分割し、各チャンクのデータ転送時間とデータ処理時間を取得し、各チャンクのデータ転送時間とデータ処理時間の大小関係に基づいて、各チャンクをコ・プロセッサに処理させる順番を決定し、決定した順番に従って、各チャンクをコ・プロセッサに転送して処理させる。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、コ・プロセッサにデータを転送して処理させるシステムにおけるデータ処理スケジュールリング装置に関する。
【背景技術】
【０００２】
近年の計算機において、ＧＰＵ（Graphics Processing Unit）はコモディティ化しており、広く利用可能となっている。ＧＰＵは、主にグラフィックス用の処理を行うものであったが、ＣＰＵ（Central Processing Unit）のコ・プロセッサとして一般的な計算用途に使うＧＰＧＰＵ（General Purpose computing on Graphics Processing Units）と呼ばれる利用形態が注目されている。また、同じくコ・プロセッサとして利用可能なＦＰＧＡ（Field Programmable Gate Array）などのプログラマブルなデバイスの低廉化も進んできている。これらのデバイスは、ホストの計算機とデータバスを介してデータをやり取りするが、その帯域は限られるため、データの転送時間が処理全体の時間に影響を及ぼす。
【０００３】
一般に、大量のデータをコ・プロセッサを用いて処理するシステムにおけるデータ処理の手順は、１）ホストコンピュータからコ・プロセッサへのデータの転送、２）コ・プロセッサでのデータ処理、３）コ・プロセッサからホストコンピュータへの結果データの転送、となる。一般にデータ転送時間は、データ量に対して単調増加である。ホスト―コ・プロセッサ間はPCIExpressX16などのバスで結ばれるため、データ転送時間がボトルネックになりやすい。
【０００４】
データ転送時間を小さくし、全体の処理を高速化するためには、一般に次の二つの方法がある。一つ目は、データ列を複数に分割し、転送と処理を多重化（パイプライン処理）して、データ転送時間を隠ぺいする方法である。二つ目は、転送データを圧縮する方法である。
【０００５】
例えば、特許文献１には、転送される各圧縮データのデータサイズと送信順序を受信側Ｗの機器に送信し、受信側の機器では、これらの情報に基づいて、転送される各圧縮データの解凍処理のスケジューリングを行う技術が開示されている。
【先行技術文献】
【特許文献】
【０００６】
【特許文献１】特開２００６−３３８４０９号公報
【発明の概要】
【発明が解決しようとする課題】
【０００７】
コ・プロセッサを用いてデータを処理するシステムで上述の二つの方法を用いて、処理対象のデータを分割し、分割したデータ（チャンク）を圧縮してコ・プロセッサに転送して処理させる場合を考える。この場合、圧縮後のチャンクのサイズが異なることでチャンク毎にデータ転送時間とデータ処理時間が異なる状況が発生する場合がある。例えば、不均一なサイズでチャンクを作成した場合や、固定長サイズでチャンクを作成したがチャンク毎に圧縮率が異なる場合等である。このような状況で、ホストコンピュータとコ・プロセッサの間でパイプライン処理を行う場合、元のままのデータの順番（インオーダー）で各チャンクを転送・処理していくと、データ転送待ちやデータ処理待ちが発生し、処理効率が低下するという問題があった。
【０００８】
特許文献１の転送方式においても、データ列を元のままの順番で転送しているため、受信側でデータ転送待ちが発生し、効率が低下するという問題がある。
【０００９】
本発明は、上記問題点に鑑みてなされたもので、コ・プロセッサにデータを転送して処理させるシステムにおいて、データ転送やデータ処理の待ち時間を短縮し、処理効率を向上させることができるデータ処理スケジューリング装置、方法及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【００１０】
本発明は、コ・プロセッサにデータを転送して処理させるデータ処理スケジュールリング装置であって、処理対象のデータを複数のチャンクに分割する分割手段と、各チャンクのデータ転送時間とデータ処理時間を取得する時間取得手段と、各チャンクのデータ転送時間とデータ処理時間の大小関係に基づいて、前記各チャンクを前記コ・プロセッサに処理させる順番を決定する順番決定手段と、を備えることを特徴とするデータ処理スケジュールリング装置である。
【００１１】
本発明は、ホストからコ・プロセッサにデータを転送して処理させるデータ処理スケジュールリング方法あって、処理対象のデータを複数のチャンクに分割し、各チャンクのデータ転送時間とデータ処理時間を取得し、各チャンクのデータ転送時間とデータ処理時間の大小関係に基づいて、前記各チャンクを前記コ・プロセッサに処理させる順番を決定することを特徴とするデータ処理スケジュールリング方法である。
【００１２】
本発明は、コンピュータに、処理対象のデータを複数のチャンクに分割する分割処理、各チャンクのデータ転送時間とデータ処理時間を取得する時間取得処理、各チャンクのデータ転送時間とデータ処理時間の大小関係に基づいて、前記各チャンクを前記コ・プロセッサに処理させる順番を決定する順番決定処理、を実行させるためのプログラムである。
【発明の効果】
【００１３】
本発明によれば、コ・プロセッサにデータを転送して処理させるシステムにおいて、データ転送やデータ処理の待ち時間を短縮し、処理効率を向上させることができる。
【図面の簡単な説明】
【００１４】
【図１】図１は本発明の実施形態に係るデータ処理スケジューリング装置を概略的に示すブロック図である。
【図２】図２は本実施形態に係るデータ処理スケジュール装置の動作を説明するための図である。
【図３】図３はデータの登録処理を説明するためのフローチャートである。
【図４】図４は処理の順番の決定処理を説明するためのフローチャートである。
【図５】図５は順番が決定された処理の実行を説明するためのフローチャートである。
【図６】図６は各チャンクのデータ転送処理とデータ処理の実行時間の具体例を示す図である。
【図７】図７はチャンク毎に処理結果をホスト側に渡す場合の処理を説明するためのフローチャートである。
【図８】図８はデータ転送時間とデータ処理時間を計測して取得する場合のデータ登録処理を説明するためのフローチャートである。
【発明を実施するための形態】
【００１５】
以下、本発明の実施形態について図面を参照して説明する。本発明は、ホストコンピュータからコ・プロセッサにデータを転送して処理させるデータ処理スケジュール装置に関する。本発明の装置が処理対象とするデータ処理は、処理対象のデータ列が複数個に分割されたデータ列（以下、チャンク）について、その処理順番に影響を受けない処理を含む。例えば、数値配列の総和計算や平均値計算などの集約処理、数値配列から特定の数値だけビットの立ったフラグ配列を作り出すbitmapインデックスの作成処理、数百万から数億件の巨大なデータを扱うＤＷＨ（Data
Ware House）内部で行われる処理等を含む。
【００１６】
図１は、本発明の実施形態に係るデータ処理スケジューリング装置を概略的に示すブロック図である。このデータ処理スケジューリング装置は、ホストコンピュータ１０と、コ・プロセッサ２０と、ホストコンピュータ１０とコ・プロセッサ２０を接続するデータバス７を備える。
【００１７】
ホストコンピュータ１０は、データ登録部１とデータ蓄積部２と順番決定部３と処理指示部４を備える。
【００１８】
データ登録部１は、入力された処理対象のデータに所定の処理を施してデータ蓄積部２に登録する。データ登録部１は、データ分割部１１とデータ圧縮部１２と時間取得部１３を備える。
【００１９】
データ分割部１１は、入力された処理対象データを複数のチャンクに分割する。
【００２０】
データ圧縮部１２は、分割されたチャンクを、所定の圧縮アルゴリズムにより圧縮する。
【００２１】
時間取得部１３は、入力されたデータと入力された処理内容に基づいて、データ転送時間とデータ処理時間を取得する。データ転送時間とデータ処理時間の取得方法は任意であり、例えば、データサイズ等に基づく実測値のデータを予め記憶しておき、その実測値を取得してもよく、また、データサイズ等を引数とする予め設定された関数を用いて取得してもよい。
【００２２】
データ登録部１は、データ分割部１１とデータ圧縮部１２により分割・圧縮されたチャンクと、時間取得部１３により取得されたデータ転送時間とデータ処理時間と、入力された処理内容と、を対応付けてデータ蓄積部２に登録する。
【００２３】
データ蓄積部２は、圧縮されたチャンクと、チャンクに対する処理内容と、チャックについて取得されたデータ転送時間とデータ処理時間と、チャンクに対する処理結果と、を蓄積して記憶する。データ蓄積部２は、ＤＲＡＭ（Dynamic Random Access Memory）、ＳＳＤ（Solid
State Drive）等を含む。
【００２４】
順番決定部３は、データ蓄積部２の蓄積された情報に基づいて、各チャンクを処理する順番を決定する。この処理の順番を決定する処理の詳細については後述する。
【００２５】
処理指示部４は、順番決定部３により決定された順番に従って、各チャンクのデータ転送とデータ処理の実行を指示する。
【００２６】
コ・プロセッサ２０は、データ蓄積部５と演算実行部６を備える。コ・プロセッサ２０は、例えば、ＧＰＵ、ＦＰＧＡ等を含む。
【００２７】
データ蓄積部５は、ホスト側から転送されたチャンクと、チャンクに対する処理と、チャンクに対する処理結果を蓄積記憶する。データ蓄積部５は、ＤＲＡＭ、ＳＳＤ等を含む。
【００２８】
演算実行部６は、転送が終わったチャンクについてデータ処理を行い、処理結果をデータ蓄積部５に格納する。
【００２９】
データバス７はホストコンピュータ１０とコ・プロセッサ２０を接続し、データ蓄積部２からデータ蓄積部５へデータを転送する。データバス７は、例えば、PCI Expressやイーサネット（登録商標）を含む。
【００３０】
次に本実施形態に係るデータ処理スケジューリング装置の動作について説明する。本実施形態に係るデータ処理スケジュール装置は、図２に示すように、各種データの登録（ステップＡ２１）、処理の順番の決定（ステップＡ２２）、処理の実行（ステップＡ２３）という処理の流れに従って動作する。以下、これらの各ステップについて説明する。
【００３１】
まず、ステップＡ２１のデータの登録処理について図３を参照して説明する。データ登録部１は、処理対象データ、処理内容、転送時間を求めるための関数、処理時間を求めるための関数の入力を受ける（ステップＡ３１）。データ分割部１１は、入力された処理対象データを複数のチャンクに分割する（ステップＡ３２）。データ圧縮部１２は、各チャンクを圧縮する（ステップＡ３３）。データ登録部１は、圧縮された各チャンクと、入力された処理内容をデータ蓄積部２に記憶する（ステップＡ３４）。
【００３２】
次に、ステップＡ２２の処理の順番の決定処理について図４を参照して説明する。順番決定部２は、データ蓄積部２に保存された全チャックについて以下の処理を行う（ステップＡ４１）。順番決定部２は、データ蓄積部２に保存されている一つのチャンクについて、転送時間と処理時間を取得する（ステップＡ４２）。順番決定部２は、転送時間と処理時間を比較し、処理時間が転送時間以上かどうか、それらの大小関係を判定する。転送時間が処理時間よりも大きい場合（ステップＡ４３：ＮＯ）、そのチャンクをリストＡに追加する（ステップＡ４４）。また、処理時間が転送時間以上の場合（ステップＡ４３：ＹＥＳ）、そのチャンクをリストＢに追加する（ステップＡ４５）。
【００３３】
全チャンクについて、ステップＡ４２〜Ａ４５の処理が終了すると（ステップＡ４１：ＹＥＳ）、順番決定部２は、リストＡに登録したチャンクを転送時間の短い順にソートし（ステップＡ４６）、リストＢに登録したチャンクを処理時間の長い順にソートする（ステップＡ４７）。順番決定部２は、リストＡの後ろにリストＢを連結して、全体の実行スケジュールとして、データ蓄積部２に保存する（ステップＡ４８）。
【００３４】
これにより、各チャンクの処理の順番が決定される。先に実行される、転送時間が処理時間よりも小さいチャンクのグループ（リストＡ）について転送時間の短い順にソートしたのは、初めの処理開始待ち時間を短縮するためである。また、続いて実行される、処理時間が転送時間以上のチャンクのグループ（リストＢ）について処理時間の長い順にソートしたのは、終わりの処理時間を短縮するためである。
【００３５】
次に、ステップＡ２３の処理の実行について図５を参照して説明する。
【００３６】
処理指示部４は、まず、チャンクの転送をコ・プロセッサ２０に指示し、順番決定部３により決定された順番に従って、チャンクをデータ蓄積部２から読み出し、データバス７を介してコ・プロセッサ２０に転送する（ステップＡ５１）。コ・プロセッサ２０は、転送されたチャンクをデータ蓄積部５に記憶する。
【００３７】
処理指示部４は、データ蓄積部２に保存された処理内容を読み出し、コ・プロセッサ２０にチャンクの処理を指示する（ステップＡ５２）。コ・プロセッサ２０の演算実行部６は、転送が終わったチャンクについて、ホストから指示されたデータ処理を行う。
【００３８】
処理指示部４は、全チャンクについて処理の指示が終わったかを判定し（ステップＡ５３）、終わっていない場合には（ステップＡ５３：ＮＯ）、ステップＡ５１に戻って次のチャンクについての処理を行う。また、全チャンクについて処理の指示が終わった場合には（ステップＡ５３：ＹＥＳ）、コ・プロセッサ２０演算実行部６による最後のチャンクの処理の終了を待つ（ステップＡ５４）。
【００３９】
処理指示部４は、コ・プロセッサ２０において最後のチャンクの処理が終了すると、処理結果の転送をコ・プロセッサ２０に指示する（ステップＡ５５）。コ・プロセッサ２０は、データ蓄積部５に保存された処理結果をホストコンピュータ１０に転送する。
【００４０】
次に本データ処理スケジューリング装置の動作を具体的に説明する。例えば、ＤＷＨ等の分野では、データの傾向や関連性を分析するために、数百万〜数億件の大量のデータに対する処理を何度も行うことがある。ここでは、１億件の要素を持つ数値データ配列の総和計算を行う場合を例に説明する。
【００４１】
まず、データ登録処理が実行される（ステップＡ２１）。具体的には、データ登録部１に、１億件の数値データ配列と、処理内容（圧縮された数値列の総和を計算する）と、変数ｙを引数とし、データ転送時間を返す関数Ｔ（ｙ）と、変数ｙを引数とし、データ処理時間を返す関数Ｘ（ｙ）と、が入力される（ステップＡ３１）。本実施形態では、関数Ｔと関数Ｘにおける引数は、圧縮後のチャンクのデータサイズとし、例えば、Ｔ（ｓｉｚｅ）＝２α＊ｓｉｚｅ、Ｘ（ｓｉｚｅ）＝α＊ｓｉｚｅとする。
【００４２】
データ分割部１１は、入力された１億件の数値データ配列を、２５００万件ずつの４個のチャンク（チャンクＣ０〜Ｃ３）に分割する（ステップＡ３２）。チャンクの数は４なので、コ・プロセッサ２０は、チャンク内のデータの和を計算し、その値をデータ蓄積部５に記憶されている結果値に加算する処理を４回繰り返すこととなる。
【００４３】
データ圧縮部１２は、各チャンクを圧縮する（ステップＡ３３）。この例において、圧縮後の各チャンクのサイズは、ｃｈｕｎｋ[０]．ｓｉｚｅ＝１、ｃｈｕｎｋ[１]．ｓｉｚｅ＝２、ｃｈｕｎｋ[２]．ｓｉｚｅ＝２、ｃｈｕｎｋ[３]．ｓｉｚｅ＝３であったとする。
【００４４】
データ登録部１は、圧縮された各チャンクと、圧縮されたチャンクに対する処理内容と、関数Ｔと、関数Ｘをデータ蓄積部２に保存する（ステップＡ３４）。
【００４５】
次に、処理の順番の決定処理が実行される（ステップＡ２２）。具体的には、順番決定部２は、図４に示すアルゴリズムに従って、データ蓄積部２に保存されたデータから、各チャンクの処理順番を決定する。各チャンクについて転送時間と処理時間を取得し（ステップＡ４２）、これらの大小関係を判定する（ステップＡ４３）。この例では、全てのチャンクにおいて、Ｔ（ｓｉｚｅ）＞Ｘ（ｓｉｚｅ）が成り立つ。このため、各チャンクはリストＢに登録されることとなる（ステップＡ４５）。全チャンクについて転送時間と処理時間の大小関係の判定が終了すると（ステップＡ４１：ＹＥＳ）、順番決定部２は、データ処理時間Ｘ（ｓｉｚｅ）の大きい順にソートし、ソート結果に基づいてスケジュールのリストを作成する。この例では、チャンク処理順は、Ｃ３，Ｃ２，Ｃ１，Ｃ０となる。
【００４６】
次に、処理の実行が行われる（ステップＡ２３）。具体的には、処理指示部４は、図５に示すアルゴリズムに従って、チャンクＣ３，Ｃ２，Ｃ１，Ｃ０の順で処理の実行を指示する。
【００４７】
処理指示部４は、コ・プロセッサ２０にデータ転送を指示し、データ蓄積部２からコ・プロセッサ側のデータ蓄積部５へのデータを転送する（ステップＡ５１）。
【００４８】
処理指示部４は、コ・プロセッサ２０にデータ処理を指示する。コ・プロセッサ２０の演算実行部６は、転送が終わったチャンクに対して、演算実行部６が総和の計算を行う（ステップＡ５２）。
【００４９】
処理指示部４は、全チャンクについて処理の指示が終わるまで（ステップＡ５３：ＮＯ）、ステップＡ５１、Ａ５２を繰り返す。そして、全チャンクの処理の指示が終わると（ステップＡ５３：ＹＥＳ）、コ・プロセッサ２０において最後のチャンクの処理が終了するのを待つ（ステップＡ５４）。最後のチャンクの計算が終わったことを検知すると、処理指示部４は、処理結果の転送をコ・プロセッサ２０に指示する。コ・プロセッサ２０は、データ蓄積部５から最終結果のデータを読み出し、ホストコンピュータ１０に転送する（ステップＡ５５）。
【００５０】
上述した例における各チャンクのデータ転送処理とデータ処理の実行時間を図６に示す（optimized）。ここでは、最終結果の転送時間がαであったとする。また、図６では、比較のため、チャンクＣ０，Ｃ１，Ｃ２，Ｃ３という元の順番のままで処理した場合のデータ転送処理とデータ処理の実行時間も示している（in-order）。図６に示すように、順番決定部３で決定した順番で処理を行うことによって、インオーダーで処理を行うよりも、転送待ち、処理待ち時間を短くすることができ、全体の処理を高速化できる。
【００５１】
以上のように、本実施の形態によれば、処理データをコ・プロセッサに転送して処理させる場合に、処理データを複数に分割し、分割した各チャンクについて、その転送時間と処理時間に基づいて処理の順番を決定することにより、データ転送の効率とコ・プロセッサの利用率を向上させることができ、全体の処理時間を短縮させることができる。
【００５２】
なお、上述した処理では、コ・プロセッサ２０において全てのチャンクの処理が終わってからホスト側に結果を渡しているが、これに限定されず、チャンク毎に処理結果をホスト側に渡すようにしてもよい。この場合の処理について図７を参照して説明する。
【００５３】
処理指示部４は、チャンクの転送をコ・プロセッサ２０に指示し、順番決定部３により決定された順番に従って、チャンクをデータ蓄積部２から読み出してコ・プロセッサ２０に転送する（ステップＡ７１）。コ・プロセッサ２０は、転送されたチャンクをデータ蓄積部５に記憶する。
【００５４】
処理指示部４は、データ蓄積部２に保存された処理内容を読み出し、コ・プロセッサ２０にチャンクの処理を指示する（ステップＡ７２）。コ・プロセッサ２０の演算実行部６は、転送が終わったチャンクについて、ホストから指示されたデータ処理を行う。
【００５５】
処理指示部４は、コ・プロセッサ２０にチャンクの処理結果の転送を指示する（ステップＡ７３）。コ・プロセッサ２０は、チャンクの処理結果をホストに転送し、処理指示部４は、転送されてきた処理結果をデータ蓄積部２に蓄積する。
【００５６】
処理指示部４は、全チャンクについて処理の指示が終わったかを判定し（ステップＡ７４）、終わっていない場合には（ステップＡ７４：ＮＯ）、ステップＡ７１に戻って次のチャンクについての処理を行う。また、全チャンクについて処理の指示が終わった場合には（ステップＡ７３：ＹＥＳ）、コ・プロセッサ２０演算実行部６による最後のチャンクの転送処理の終了を待つ（ステップＡ７５４）。
【００５７】
処理指示部４は、コ・プロセッサ２０において最後のチャンクの転送処理が終了すると、データ蓄積部２に保存していたチャンク毎の結果処理をまとめる処理を行う（ステップＡ７６）。
【００５８】
なお、図７に示すような処理を行う場合、チャンクの処理の順番の決定は、チャンクの転送時間、チャンクの処理時間に加えて、コ・プロセッサ側に保持可能な結果のサイズ、結果の転送時間等をパラメータとする最適化問題となる。この場合、順番決定部３は、例えば、総当たりによって最適なスケジュールを得る、ヒューリスティックな解法により、近似最適なスケジュールを作成する。
【００５９】
上記実施形態では、ホストコンピュータ１０のデータ登録部１によるデータ登録処理（図３）では、各チャンクのデータ転送時間とデータ処理時間を求めるための各関数が入力されていた。上記実施形態の変形例として、のデータ登録部１の時間取得部１３が、各チャンクのデータ転送時間とデータ処理時間の少なくとも一方を実測して取得し、この実測値に基づいて順番決定部３が各チャンクの処理の順番を決定してもよい。この場合のデータ登録部１によるデータ登録処理について図８を参照して説明する。
【００６０】
データ登録部１は、処理対象データ、処理内容の入力を受ける（ステップＡ８１）。データ分割部１１は、入力された処理対象データを複数のチャンクに分割する（ステップＡ８２）。データ圧縮部１２は、各チャンクを圧縮する（ステップＡ８３）。時間取得部１３は、圧縮された各チャンクについてデータ転送時間とデータ処理時間を測定する（ステップＡ８４）。具体的には、各チャンクについて、データ転送をコ・プロセッサ２０に指示した時点から、その転送が完了するまでの時間を計測する。また、各チャンクについて、処理を指示した時点から、その処理が完了するまでの時間を計測する。データ登録部１は、圧縮された各チャンクと、入力された処理内容と、測定された各チャンクの転送時間と処理時間をデータ蓄積部２に記憶する（ステップＡ８５）。
【００６１】
なお、ここでは、データ転送時間とデータ処理時間の双方を測定しているが、どちらか一方だけ測定し、他方は関数等で求めてもよい。
【００６２】
上述した本発明の実施形態に係るデータ登録部１、順番決定部３、処理指示部４、演算実行部６は、ＣＰＵ等の処理装置が記憶部に格納された動作プログラム等を読み出して実行することにより実現されてもよく、また、ハードウェアで構成されてもよい。上述した実施の形態の一部の機能のみをコンピュータプログラムにより実現することもできる。
【００６３】
以上、好ましい実施の形態をあげて本発明を説明したが、本発明は必ずしも上記実施の形態に限定されるものではなく、その技術的思想の範囲内において様々に変形し実施することが出来る。
【００６４】
上記の実施形態の一部又は全部は、以下の付記のようにも記載されうるが、以下には限られない。
【００６５】
(付記１）
コ・プロセッサにデータを転送して処理させるデータ処理スケジュールリング装置であって、
処理対象のデータを複数のチャンクに分割する分割手段と、
各チャンクのデータ転送時間とデータ処理時間を取得する時間取得手段と、
各チャンクのデータ転送時間とデータ処理時間の大小関係に基づいて、前記各チャンクを前記コ・プロセッサに処理させる順番を決定する順番決定手段と、
を備えることを特徴とするデータ処理スケジュールリング装置。
【００６６】
(付記２）
前記順番決定手段は、前記各チャンクを、データ転送時間とデータ処理時間の大小関係に基づいて分別し、データ転送時間の方が小さいチャンクのグループをデータ転送時間の小さい順に処理した後にデータ転送時間の方が大きいチャンクのグループをデータ処理時間の大きい順に処理するように、各チャンクの順番を決定する、
ことを特徴とする付記１に記載のデータ処理スケジュールリング装置。
【００６７】
(付記３）
前記順番決定手段は、データ転送時間の方が小さいチャンクのグループをデータ転送時間の小さい順にソートし、データ転送時間の方が大きいチャンクのグループをデータ処理時間の大きい順にソートし、データ転送時間の方が小さいチャンクのグループが先になるように前記２つのグループのソート結果を結合して、チャンクの処理の順番のスケジュールリストを生成する、
ことを特徴とする請求項２に記載のデータ処理スケジュールリング装置。
【００６８】
(付記４）
前記時間取得手段は、各チャンクのデータ転送時間とデータ処理時間を計測して取得し、
前記順番決定手段は、前記計測された各チャンクのデータ転送時間とデータ処理時間に基づいて、各チャンクを前記コ・プロセッサに処理させる順番を決定する
ことを特徴とする請求項１から３のいずれか１項に記載のデータ処理スケジュールリング装置。
【００６９】
(付記５）
ホストからコ・プロセッサにデータを転送して処理させるデータ処理スケジュールリング方法あって、
処理対象のデータを複数のチャンクに分割し、
各チャンクのデータ転送時間とデータ処理時間を取得し、
各チャンクのデータ転送時間とデータ処理時間の大小関係に基づいて、前記各チャンクを前記コ・プロセッサに処理させる順番を決定する、
ことを特徴とするデータ処理スケジュールリング方法。
【００７０】
(付記６）
各チャンクを前記コ・プロセッサに処理させる順番を決定するときに、前記各チャンクを、データ転送時間とデータ処理時間の大小関係に基づいて分別し、データ転送時間の方が小さいチャンクのグループをデータ転送時間の小さい順に処理した後にデータ転送時間の方が大きいチャンクのグループをデータ処理時間の大きい順に処理するように、各チャンクの順番を決定する、
ことを特徴とする請求項５に記載のデータ処理スケジュールリング方法。
【００７１】
(付記７）
各チャンクを前記コ・プロセッサに処理させる順番を決定するときに、データ転送時間の方が小さいチャンクのグループをデータ転送時間の小さい順にソートし、データ転送時間の方が大きいチャンクのグループをデータ処理時間の大きい順にソートし、データ転送時間の方が小さいチャンクのグループが先になるように前記２つのグループのソート結果を結合して、チャンクの処理の順番のスケジュールリストを生成する、
ことを特徴とする請求項６に記載のデータ処理スケジュールリング方法。
【００７２】
(付記８）
各チャンクのデータ転送時間とデータ処理時間を計測して取得し、
各チャンクを前記コ・プロセッサに処理させる順番を決定するときに、前記計測された各チャンクのデータ転送時間とデータ処理時間に基づいて、各チャンクを前記コ・プロセッサに処理させる順番を決定する
ことを特徴とする請求項５から７のいずれか１項に記載のデータ処理スケジュールリング方法。
【００７３】
(付記９）
コンピュータに、
処理対象のデータを複数のチャンクに分割する分割処理、
各チャンクのデータ転送時間とデータ処理時間を取得する時間取得処理、
各チャンクのデータ転送時間とデータ処理時間の大小関係に基づいて、前記各チャンクを前記コ・プロセッサに処理させる順番を決定する順番決定処理、
を実行させることを特徴とするプログラム。
【００７４】
(付記１０）
前記順番決定処理は、前記各チャンクを、データ転送時間とデータ処理時間の大小関係に基づいて分別し、データ転送時間の方が小さいチャンクのグループをデータ転送時間の小さい順に処理した後にデータ転送時間の方が大きいチャンクのグループをデータ処理時間の大きい順に処理するように、各チャンクの順番を決定する、
ことを特徴とする請求項９に記載のプログラム。
【００７５】
(付記１１）
前記順番決定処理は、データ転送時間の方が小さいチャンクのグループをデータ転送時間の小さい順にソートし、データ転送時間の方が大きいチャンクのグループをデータ処理時間の大きい順にソートし、データ転送時間の方が小さいチャンクのグループが先になるように前記２つのグループのソート結果を結合して、チャンクの処理の順番のスケジュールリストを生成する、
ことを特徴とする請求項１０に記載のプログラム。
【００７６】
(付記１２）
前記時間取得処理は、各チャンクのデータ転送時間とデータ処理時間を計測して取得し、
前記順番決定処理は、前記計測された各チャンクのデータ転送時間とデータ処理時間に基づいて、各チャンクを前記コ・プロセッサに処理させる順番を決定する
ことを特徴とする請求項９から１１のいずれか１項に記載のプログラム。
【符号の説明】
【００７７】
１ データ登録部
２ データ蓄積部
３ 順番決定部
４ 処理指示部
５ データ蓄積部
６ 演算実行部
７ データバス
１０ ホストコンピュータ
１１ データ分割部
１２ データ圧縮部
１３ 時間取得部
２０ コ・プロセッサ
【技術分野】
【０００１】
本発明は、コ・プロセッサにデータを転送して処理させるシステムにおけるデータ処理スケジュールリング装置に関する。
【背景技術】
【０００２】
近年の計算機において、ＧＰＵ（Graphics Processing Unit）はコモディティ化しており、広く利用可能となっている。ＧＰＵは、主にグラフィックス用の処理を行うものであったが、ＣＰＵ（Central Processing Unit）のコ・プロセッサとして一般的な計算用途に使うＧＰＧＰＵ（General Purpose computing on Graphics Processing Units）と呼ばれる利用形態が注目されている。また、同じくコ・プロセッサとして利用可能なＦＰＧＡ（Field Programmable Gate Array）などのプログラマブルなデバイスの低廉化も進んできている。これらのデバイスは、ホストの計算機とデータバスを介してデータをやり取りするが、その帯域は限られるため、データの転送時間が処理全体の時間に影響を及ぼす。
【０００３】
一般に、大量のデータをコ・プロセッサを用いて処理するシステムにおけるデータ処理の手順は、１）ホストコンピュータからコ・プロセッサへのデータの転送、２）コ・プロセッサでのデータ処理、３）コ・プロセッサからホストコンピュータへの結果データの転送、となる。一般にデータ転送時間は、データ量に対して単調増加である。ホスト―コ・プロセッサ間はPCIExpressX16などのバスで結ばれるため、データ転送時間がボトルネックになりやすい。
【０００４】
データ転送時間を小さくし、全体の処理を高速化するためには、一般に次の二つの方法がある。一つ目は、データ列を複数に分割し、転送と処理を多重化（パイプライン処理）して、データ転送時間を隠ぺいする方法である。二つ目は、転送データを圧縮する方法である。
【０００５】
例えば、特許文献１には、転送される各圧縮データのデータサイズと送信順序を受信側Ｗの機器に送信し、受信側の機器では、これらの情報に基づいて、転送される各圧縮データの解凍処理のスケジューリングを行う技術が開示されている。
【先行技術文献】
【特許文献】
【０００６】
【特許文献１】特開２００６−３３８４０９号公報
【発明の概要】
【発明が解決しようとする課題】
【０００７】
コ・プロセッサを用いてデータを処理するシステムで上述の二つの方法を用いて、処理対象のデータを分割し、分割したデータ（チャンク）を圧縮してコ・プロセッサに転送して処理させる場合を考える。この場合、圧縮後のチャンクのサイズが異なることでチャンク毎にデータ転送時間とデータ処理時間が異なる状況が発生する場合がある。例えば、不均一なサイズでチャンクを作成した場合や、固定長サイズでチャンクを作成したがチャンク毎に圧縮率が異なる場合等である。このような状況で、ホストコンピュータとコ・プロセッサの間でパイプライン処理を行う場合、元のままのデータの順番（インオーダー）で各チャンクを転送・処理していくと、データ転送待ちやデータ処理待ちが発生し、処理効率が低下するという問題があった。
【０００８】
特許文献１の転送方式においても、データ列を元のままの順番で転送しているため、受信側でデータ転送待ちが発生し、効率が低下するという問題がある。
【０００９】
本発明は、上記問題点に鑑みてなされたもので、コ・プロセッサにデータを転送して処理させるシステムにおいて、データ転送やデータ処理の待ち時間を短縮し、処理効率を向上させることができるデータ処理スケジューリング装置、方法及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【００１０】
本発明は、コ・プロセッサにデータを転送して処理させるデータ処理スケジュールリング装置であって、処理対象のデータを複数のチャンクに分割する分割手段と、各チャンクのデータ転送時間とデータ処理時間を取得する時間取得手段と、各チャンクのデータ転送時間とデータ処理時間の大小関係に基づいて、前記各チャンクを前記コ・プロセッサに処理させる順番を決定する順番決定手段と、を備えることを特徴とするデータ処理スケジュールリング装置である。
【００１１】
本発明は、ホストからコ・プロセッサにデータを転送して処理させるデータ処理スケジュールリング方法あって、処理対象のデータを複数のチャンクに分割し、各チャンクのデータ転送時間とデータ処理時間を取得し、各チャンクのデータ転送時間とデータ処理時間の大小関係に基づいて、前記各チャンクを前記コ・プロセッサに処理させる順番を決定することを特徴とするデータ処理スケジュールリング方法である。
【００１２】
本発明は、コンピュータに、処理対象のデータを複数のチャンクに分割する分割処理、各チャンクのデータ転送時間とデータ処理時間を取得する時間取得処理、各チャンクのデータ転送時間とデータ処理時間の大小関係に基づいて、前記各チャンクを前記コ・プロセッサに処理させる順番を決定する順番決定処理、を実行させるためのプログラムである。
【発明の効果】
【００１３】
本発明によれば、コ・プロセッサにデータを転送して処理させるシステムにおいて、データ転送やデータ処理の待ち時間を短縮し、処理効率を向上させることができる。
【図面の簡単な説明】
【００１４】
【図１】図１は本発明の実施形態に係るデータ処理スケジューリング装置を概略的に示すブロック図である。
【図２】図２は本実施形態に係るデータ処理スケジュール装置の動作を説明するための図である。
【図３】図３はデータの登録処理を説明するためのフローチャートである。
【図４】図４は処理の順番の決定処理を説明するためのフローチャートである。
【図５】図５は順番が決定された処理の実行を説明するためのフローチャートである。
【図６】図６は各チャンクのデータ転送処理とデータ処理の実行時間の具体例を示す図である。
【図７】図７はチャンク毎に処理結果をホスト側に渡す場合の処理を説明するためのフローチャートである。
【図８】図８はデータ転送時間とデータ処理時間を計測して取得する場合のデータ登録処理を説明するためのフローチャートである。
【発明を実施するための形態】
【００１５】
以下、本発明の実施形態について図面を参照して説明する。本発明は、ホストコンピュータからコ・プロセッサにデータを転送して処理させるデータ処理スケジュール装置に関する。本発明の装置が処理対象とするデータ処理は、処理対象のデータ列が複数個に分割されたデータ列（以下、チャンク）について、その処理順番に影響を受けない処理を含む。例えば、数値配列の総和計算や平均値計算などの集約処理、数値配列から特定の数値だけビットの立ったフラグ配列を作り出すbitmapインデックスの作成処理、数百万から数億件の巨大なデータを扱うＤＷＨ（Data
Ware House）内部で行われる処理等を含む。
【００１６】
図１は、本発明の実施形態に係るデータ処理スケジューリング装置を概略的に示すブロック図である。このデータ処理スケジューリング装置は、ホストコンピュータ１０と、コ・プロセッサ２０と、ホストコンピュータ１０とコ・プロセッサ２０を接続するデータバス７を備える。
【００１７】
ホストコンピュータ１０は、データ登録部１とデータ蓄積部２と順番決定部３と処理指示部４を備える。
【００１８】
データ登録部１は、入力された処理対象のデータに所定の処理を施してデータ蓄積部２に登録する。データ登録部１は、データ分割部１１とデータ圧縮部１２と時間取得部１３を備える。
【００１９】
データ分割部１１は、入力された処理対象データを複数のチャンクに分割する。
【００２０】
データ圧縮部１２は、分割されたチャンクを、所定の圧縮アルゴリズムにより圧縮する。
【００２１】
時間取得部１３は、入力されたデータと入力された処理内容に基づいて、データ転送時間とデータ処理時間を取得する。データ転送時間とデータ処理時間の取得方法は任意であり、例えば、データサイズ等に基づく実測値のデータを予め記憶しておき、その実測値を取得してもよく、また、データサイズ等を引数とする予め設定された関数を用いて取得してもよい。
【００２２】
データ登録部１は、データ分割部１１とデータ圧縮部１２により分割・圧縮されたチャンクと、時間取得部１３により取得されたデータ転送時間とデータ処理時間と、入力された処理内容と、を対応付けてデータ蓄積部２に登録する。
【００２３】
データ蓄積部２は、圧縮されたチャンクと、チャンクに対する処理内容と、チャックについて取得されたデータ転送時間とデータ処理時間と、チャンクに対する処理結果と、を蓄積して記憶する。データ蓄積部２は、ＤＲＡＭ（Dynamic Random Access Memory）、ＳＳＤ（Solid
State Drive）等を含む。
【００２４】
順番決定部３は、データ蓄積部２の蓄積された情報に基づいて、各チャンクを処理する順番を決定する。この処理の順番を決定する処理の詳細については後述する。
【００２５】
処理指示部４は、順番決定部３により決定された順番に従って、各チャンクのデータ転送とデータ処理の実行を指示する。
【００２６】
コ・プロセッサ２０は、データ蓄積部５と演算実行部６を備える。コ・プロセッサ２０は、例えば、ＧＰＵ、ＦＰＧＡ等を含む。
【００２７】
データ蓄積部５は、ホスト側から転送されたチャンクと、チャンクに対する処理と、チャンクに対する処理結果を蓄積記憶する。データ蓄積部５は、ＤＲＡＭ、ＳＳＤ等を含む。
【００２８】
演算実行部６は、転送が終わったチャンクについてデータ処理を行い、処理結果をデータ蓄積部５に格納する。
【００２９】
データバス７はホストコンピュータ１０とコ・プロセッサ２０を接続し、データ蓄積部２からデータ蓄積部５へデータを転送する。データバス７は、例えば、PCI Expressやイーサネット（登録商標）を含む。
【００３０】
次に本実施形態に係るデータ処理スケジューリング装置の動作について説明する。本実施形態に係るデータ処理スケジュール装置は、図２に示すように、各種データの登録（ステップＡ２１）、処理の順番の決定（ステップＡ２２）、処理の実行（ステップＡ２３）という処理の流れに従って動作する。以下、これらの各ステップについて説明する。
【００３１】
まず、ステップＡ２１のデータの登録処理について図３を参照して説明する。データ登録部１は、処理対象データ、処理内容、転送時間を求めるための関数、処理時間を求めるための関数の入力を受ける（ステップＡ３１）。データ分割部１１は、入力された処理対象データを複数のチャンクに分割する（ステップＡ３２）。データ圧縮部１２は、各チャンクを圧縮する（ステップＡ３３）。データ登録部１は、圧縮された各チャンクと、入力された処理内容をデータ蓄積部２に記憶する（ステップＡ３４）。
【００３２】
次に、ステップＡ２２の処理の順番の決定処理について図４を参照して説明する。順番決定部２は、データ蓄積部２に保存された全チャックについて以下の処理を行う（ステップＡ４１）。順番決定部２は、データ蓄積部２に保存されている一つのチャンクについて、転送時間と処理時間を取得する（ステップＡ４２）。順番決定部２は、転送時間と処理時間を比較し、処理時間が転送時間以上かどうか、それらの大小関係を判定する。転送時間が処理時間よりも大きい場合（ステップＡ４３：ＮＯ）、そのチャンクをリストＡに追加する（ステップＡ４４）。また、処理時間が転送時間以上の場合（ステップＡ４３：ＹＥＳ）、そのチャンクをリストＢに追加する（ステップＡ４５）。
【００３３】
全チャンクについて、ステップＡ４２〜Ａ４５の処理が終了すると（ステップＡ４１：ＹＥＳ）、順番決定部２は、リストＡに登録したチャンクを転送時間の短い順にソートし（ステップＡ４６）、リストＢに登録したチャンクを処理時間の長い順にソートする（ステップＡ４７）。順番決定部２は、リストＡの後ろにリストＢを連結して、全体の実行スケジュールとして、データ蓄積部２に保存する（ステップＡ４８）。
【００３４】
これにより、各チャンクの処理の順番が決定される。先に実行される、転送時間が処理時間よりも小さいチャンクのグループ（リストＡ）について転送時間の短い順にソートしたのは、初めの処理開始待ち時間を短縮するためである。また、続いて実行される、処理時間が転送時間以上のチャンクのグループ（リストＢ）について処理時間の長い順にソートしたのは、終わりの処理時間を短縮するためである。
【００３５】
次に、ステップＡ２３の処理の実行について図５を参照して説明する。
【００３６】
処理指示部４は、まず、チャンクの転送をコ・プロセッサ２０に指示し、順番決定部３により決定された順番に従って、チャンクをデータ蓄積部２から読み出し、データバス７を介してコ・プロセッサ２０に転送する（ステップＡ５１）。コ・プロセッサ２０は、転送されたチャンクをデータ蓄積部５に記憶する。
【００３７】
処理指示部４は、データ蓄積部２に保存された処理内容を読み出し、コ・プロセッサ２０にチャンクの処理を指示する（ステップＡ５２）。コ・プロセッサ２０の演算実行部６は、転送が終わったチャンクについて、ホストから指示されたデータ処理を行う。
【００３８】
処理指示部４は、全チャンクについて処理の指示が終わったかを判定し（ステップＡ５３）、終わっていない場合には（ステップＡ５３：ＮＯ）、ステップＡ５１に戻って次のチャンクについての処理を行う。また、全チャンクについて処理の指示が終わった場合には（ステップＡ５３：ＹＥＳ）、コ・プロセッサ２０演算実行部６による最後のチャンクの処理の終了を待つ（ステップＡ５４）。
【００３９】
処理指示部４は、コ・プロセッサ２０において最後のチャンクの処理が終了すると、処理結果の転送をコ・プロセッサ２０に指示する（ステップＡ５５）。コ・プロセッサ２０は、データ蓄積部５に保存された処理結果をホストコンピュータ１０に転送する。
【００４０】
次に本データ処理スケジューリング装置の動作を具体的に説明する。例えば、ＤＷＨ等の分野では、データの傾向や関連性を分析するために、数百万〜数億件の大量のデータに対する処理を何度も行うことがある。ここでは、１億件の要素を持つ数値データ配列の総和計算を行う場合を例に説明する。
【００４１】
まず、データ登録処理が実行される（ステップＡ２１）。具体的には、データ登録部１に、１億件の数値データ配列と、処理内容（圧縮された数値列の総和を計算する）と、変数ｙを引数とし、データ転送時間を返す関数Ｔ（ｙ）と、変数ｙを引数とし、データ処理時間を返す関数Ｘ（ｙ）と、が入力される（ステップＡ３１）。本実施形態では、関数Ｔと関数Ｘにおける引数は、圧縮後のチャンクのデータサイズとし、例えば、Ｔ（ｓｉｚｅ）＝２α＊ｓｉｚｅ、Ｘ（ｓｉｚｅ）＝α＊ｓｉｚｅとする。
【００４２】
データ分割部１１は、入力された１億件の数値データ配列を、２５００万件ずつの４個のチャンク（チャンクＣ０〜Ｃ３）に分割する（ステップＡ３２）。チャンクの数は４なので、コ・プロセッサ２０は、チャンク内のデータの和を計算し、その値をデータ蓄積部５に記憶されている結果値に加算する処理を４回繰り返すこととなる。
【００４３】
データ圧縮部１２は、各チャンクを圧縮する（ステップＡ３３）。この例において、圧縮後の各チャンクのサイズは、ｃｈｕｎｋ[０]．ｓｉｚｅ＝１、ｃｈｕｎｋ[１]．ｓｉｚｅ＝２、ｃｈｕｎｋ[２]．ｓｉｚｅ＝２、ｃｈｕｎｋ[３]．ｓｉｚｅ＝３であったとする。
【００４４】
データ登録部１は、圧縮された各チャンクと、圧縮されたチャンクに対する処理内容と、関数Ｔと、関数Ｘをデータ蓄積部２に保存する（ステップＡ３４）。
【００４５】
次に、処理の順番の決定処理が実行される（ステップＡ２２）。具体的には、順番決定部２は、図４に示すアルゴリズムに従って、データ蓄積部２に保存されたデータから、各チャンクの処理順番を決定する。各チャンクについて転送時間と処理時間を取得し（ステップＡ４２）、これらの大小関係を判定する（ステップＡ４３）。この例では、全てのチャンクにおいて、Ｔ（ｓｉｚｅ）＞Ｘ（ｓｉｚｅ）が成り立つ。このため、各チャンクはリストＢに登録されることとなる（ステップＡ４５）。全チャンクについて転送時間と処理時間の大小関係の判定が終了すると（ステップＡ４１：ＹＥＳ）、順番決定部２は、データ処理時間Ｘ（ｓｉｚｅ）の大きい順にソートし、ソート結果に基づいてスケジュールのリストを作成する。この例では、チャンク処理順は、Ｃ３，Ｃ２，Ｃ１，Ｃ０となる。
【００４６】
次に、処理の実行が行われる（ステップＡ２３）。具体的には、処理指示部４は、図５に示すアルゴリズムに従って、チャンクＣ３，Ｃ２，Ｃ１，Ｃ０の順で処理の実行を指示する。
【００４７】
処理指示部４は、コ・プロセッサ２０にデータ転送を指示し、データ蓄積部２からコ・プロセッサ側のデータ蓄積部５へのデータを転送する（ステップＡ５１）。
【００４８】
処理指示部４は、コ・プロセッサ２０にデータ処理を指示する。コ・プロセッサ２０の演算実行部６は、転送が終わったチャンクに対して、演算実行部６が総和の計算を行う（ステップＡ５２）。
【００４９】
処理指示部４は、全チャンクについて処理の指示が終わるまで（ステップＡ５３：ＮＯ）、ステップＡ５１、Ａ５２を繰り返す。そして、全チャンクの処理の指示が終わると（ステップＡ５３：ＹＥＳ）、コ・プロセッサ２０において最後のチャンクの処理が終了するのを待つ（ステップＡ５４）。最後のチャンクの計算が終わったことを検知すると、処理指示部４は、処理結果の転送をコ・プロセッサ２０に指示する。コ・プロセッサ２０は、データ蓄積部５から最終結果のデータを読み出し、ホストコンピュータ１０に転送する（ステップＡ５５）。
【００５０】
上述した例における各チャンクのデータ転送処理とデータ処理の実行時間を図６に示す（optimized）。ここでは、最終結果の転送時間がαであったとする。また、図６では、比較のため、チャンクＣ０，Ｃ１，Ｃ２，Ｃ３という元の順番のままで処理した場合のデータ転送処理とデータ処理の実行時間も示している（in-order）。図６に示すように、順番決定部３で決定した順番で処理を行うことによって、インオーダーで処理を行うよりも、転送待ち、処理待ち時間を短くすることができ、全体の処理を高速化できる。
【００５１】
以上のように、本実施の形態によれば、処理データをコ・プロセッサに転送して処理させる場合に、処理データを複数に分割し、分割した各チャンクについて、その転送時間と処理時間に基づいて処理の順番を決定することにより、データ転送の効率とコ・プロセッサの利用率を向上させることができ、全体の処理時間を短縮させることができる。
【００５２】
なお、上述した処理では、コ・プロセッサ２０において全てのチャンクの処理が終わってからホスト側に結果を渡しているが、これに限定されず、チャンク毎に処理結果をホスト側に渡すようにしてもよい。この場合の処理について図７を参照して説明する。
【００５３】
処理指示部４は、チャンクの転送をコ・プロセッサ２０に指示し、順番決定部３により決定された順番に従って、チャンクをデータ蓄積部２から読み出してコ・プロセッサ２０に転送する（ステップＡ７１）。コ・プロセッサ２０は、転送されたチャンクをデータ蓄積部５に記憶する。
【００５４】
処理指示部４は、データ蓄積部２に保存された処理内容を読み出し、コ・プロセッサ２０にチャンクの処理を指示する（ステップＡ７２）。コ・プロセッサ２０の演算実行部６は、転送が終わったチャンクについて、ホストから指示されたデータ処理を行う。
【００５５】
処理指示部４は、コ・プロセッサ２０にチャンクの処理結果の転送を指示する（ステップＡ７３）。コ・プロセッサ２０は、チャンクの処理結果をホストに転送し、処理指示部４は、転送されてきた処理結果をデータ蓄積部２に蓄積する。
【００５６】
処理指示部４は、全チャンクについて処理の指示が終わったかを判定し（ステップＡ７４）、終わっていない場合には（ステップＡ７４：ＮＯ）、ステップＡ７１に戻って次のチャンクについての処理を行う。また、全チャンクについて処理の指示が終わった場合には（ステップＡ７３：ＹＥＳ）、コ・プロセッサ２０演算実行部６による最後のチャンクの転送処理の終了を待つ（ステップＡ７５４）。
【００５７】
処理指示部４は、コ・プロセッサ２０において最後のチャンクの転送処理が終了すると、データ蓄積部２に保存していたチャンク毎の結果処理をまとめる処理を行う（ステップＡ７６）。
【００５８】
なお、図７に示すような処理を行う場合、チャンクの処理の順番の決定は、チャンクの転送時間、チャンクの処理時間に加えて、コ・プロセッサ側に保持可能な結果のサイズ、結果の転送時間等をパラメータとする最適化問題となる。この場合、順番決定部３は、例えば、総当たりによって最適なスケジュールを得る、ヒューリスティックな解法により、近似最適なスケジュールを作成する。
【００５９】
上記実施形態では、ホストコンピュータ１０のデータ登録部１によるデータ登録処理（図３）では、各チャンクのデータ転送時間とデータ処理時間を求めるための各関数が入力されていた。上記実施形態の変形例として、のデータ登録部１の時間取得部１３が、各チャンクのデータ転送時間とデータ処理時間の少なくとも一方を実測して取得し、この実測値に基づいて順番決定部３が各チャンクの処理の順番を決定してもよい。この場合のデータ登録部１によるデータ登録処理について図８を参照して説明する。
【００６０】
データ登録部１は、処理対象データ、処理内容の入力を受ける（ステップＡ８１）。データ分割部１１は、入力された処理対象データを複数のチャンクに分割する（ステップＡ８２）。データ圧縮部１２は、各チャンクを圧縮する（ステップＡ８３）。時間取得部１３は、圧縮された各チャンクについてデータ転送時間とデータ処理時間を測定する（ステップＡ８４）。具体的には、各チャンクについて、データ転送をコ・プロセッサ２０に指示した時点から、その転送が完了するまでの時間を計測する。また、各チャンクについて、処理を指示した時点から、その処理が完了するまでの時間を計測する。データ登録部１は、圧縮された各チャンクと、入力された処理内容と、測定された各チャンクの転送時間と処理時間をデータ蓄積部２に記憶する（ステップＡ８５）。
【００６１】
なお、ここでは、データ転送時間とデータ処理時間の双方を測定しているが、どちらか一方だけ測定し、他方は関数等で求めてもよい。
【００６２】
上述した本発明の実施形態に係るデータ登録部１、順番決定部３、処理指示部４、演算実行部６は、ＣＰＵ等の処理装置が記憶部に格納された動作プログラム等を読み出して実行することにより実現されてもよく、また、ハードウェアで構成されてもよい。上述した実施の形態の一部の機能のみをコンピュータプログラムにより実現することもできる。
【００６３】
以上、好ましい実施の形態をあげて本発明を説明したが、本発明は必ずしも上記実施の形態に限定されるものではなく、その技術的思想の範囲内において様々に変形し実施することが出来る。
【００６４】
上記の実施形態の一部又は全部は、以下の付記のようにも記載されうるが、以下には限られない。
【００６５】
(付記１）
コ・プロセッサにデータを転送して処理させるデータ処理スケジュールリング装置であって、
処理対象のデータを複数のチャンクに分割する分割手段と、
各チャンクのデータ転送時間とデータ処理時間を取得する時間取得手段と、
各チャンクのデータ転送時間とデータ処理時間の大小関係に基づいて、前記各チャンクを前記コ・プロセッサに処理させる順番を決定する順番決定手段と、
を備えることを特徴とするデータ処理スケジュールリング装置。
【００６６】
(付記２）
前記順番決定手段は、前記各チャンクを、データ転送時間とデータ処理時間の大小関係に基づいて分別し、データ転送時間の方が小さいチャンクのグループをデータ転送時間の小さい順に処理した後にデータ転送時間の方が大きいチャンクのグループをデータ処理時間の大きい順に処理するように、各チャンクの順番を決定する、
ことを特徴とする付記１に記載のデータ処理スケジュールリング装置。
【００６７】
(付記３）
前記順番決定手段は、データ転送時間の方が小さいチャンクのグループをデータ転送時間の小さい順にソートし、データ転送時間の方が大きいチャンクのグループをデータ処理時間の大きい順にソートし、データ転送時間の方が小さいチャンクのグループが先になるように前記２つのグループのソート結果を結合して、チャンクの処理の順番のスケジュールリストを生成する、
ことを特徴とする請求項２に記載のデータ処理スケジュールリング装置。
【００６８】
(付記４）
前記時間取得手段は、各チャンクのデータ転送時間とデータ処理時間を計測して取得し、
前記順番決定手段は、前記計測された各チャンクのデータ転送時間とデータ処理時間に基づいて、各チャンクを前記コ・プロセッサに処理させる順番を決定する
ことを特徴とする請求項１から３のいずれか１項に記載のデータ処理スケジュールリング装置。
【００６９】
(付記５）
ホストからコ・プロセッサにデータを転送して処理させるデータ処理スケジュールリング方法あって、
処理対象のデータを複数のチャンクに分割し、
各チャンクのデータ転送時間とデータ処理時間を取得し、
各チャンクのデータ転送時間とデータ処理時間の大小関係に基づいて、前記各チャンクを前記コ・プロセッサに処理させる順番を決定する、
ことを特徴とするデータ処理スケジュールリング方法。
【００７０】
(付記６）
各チャンクを前記コ・プロセッサに処理させる順番を決定するときに、前記各チャンクを、データ転送時間とデータ処理時間の大小関係に基づいて分別し、データ転送時間の方が小さいチャンクのグループをデータ転送時間の小さい順に処理した後にデータ転送時間の方が大きいチャンクのグループをデータ処理時間の大きい順に処理するように、各チャンクの順番を決定する、
ことを特徴とする請求項５に記載のデータ処理スケジュールリング方法。
【００７１】
(付記７）
各チャンクを前記コ・プロセッサに処理させる順番を決定するときに、データ転送時間の方が小さいチャンクのグループをデータ転送時間の小さい順にソートし、データ転送時間の方が大きいチャンクのグループをデータ処理時間の大きい順にソートし、データ転送時間の方が小さいチャンクのグループが先になるように前記２つのグループのソート結果を結合して、チャンクの処理の順番のスケジュールリストを生成する、
ことを特徴とする請求項６に記載のデータ処理スケジュールリング方法。
【００７２】
(付記８）
各チャンクのデータ転送時間とデータ処理時間を計測して取得し、
各チャンクを前記コ・プロセッサに処理させる順番を決定するときに、前記計測された各チャンクのデータ転送時間とデータ処理時間に基づいて、各チャンクを前記コ・プロセッサに処理させる順番を決定する
ことを特徴とする請求項５から７のいずれか１項に記載のデータ処理スケジュールリング方法。
【００７３】
(付記９）
コンピュータに、
処理対象のデータを複数のチャンクに分割する分割処理、
各チャンクのデータ転送時間とデータ処理時間を取得する時間取得処理、
各チャンクのデータ転送時間とデータ処理時間の大小関係に基づいて、前記各チャンクを前記コ・プロセッサに処理させる順番を決定する順番決定処理、
を実行させることを特徴とするプログラム。
【００７４】
(付記１０）
前記順番決定処理は、前記各チャンクを、データ転送時間とデータ処理時間の大小関係に基づいて分別し、データ転送時間の方が小さいチャンクのグループをデータ転送時間の小さい順に処理した後にデータ転送時間の方が大きいチャンクのグループをデータ処理時間の大きい順に処理するように、各チャンクの順番を決定する、
ことを特徴とする請求項９に記載のプログラム。
【００７５】
(付記１１）
前記順番決定処理は、データ転送時間の方が小さいチャンクのグループをデータ転送時間の小さい順にソートし、データ転送時間の方が大きいチャンクのグループをデータ処理時間の大きい順にソートし、データ転送時間の方が小さいチャンクのグループが先になるように前記２つのグループのソート結果を結合して、チャンクの処理の順番のスケジュールリストを生成する、
ことを特徴とする請求項１０に記載のプログラム。
【００７６】
(付記１２）
前記時間取得処理は、各チャンクのデータ転送時間とデータ処理時間を計測して取得し、
前記順番決定処理は、前記計測された各チャンクのデータ転送時間とデータ処理時間に基づいて、各チャンクを前記コ・プロセッサに処理させる順番を決定する
ことを特徴とする請求項９から１１のいずれか１項に記載のプログラム。
【符号の説明】
【００７７】
１ データ登録部
２ データ蓄積部
３ 順番決定部
４ 処理指示部
５ データ蓄積部
６ 演算実行部
７ データバス
１０ ホストコンピュータ
１１ データ分割部
１２ データ圧縮部
１３ 時間取得部
２０ コ・プロセッサ
【特許請求の範囲】
【請求項１】
コ・プロセッサにデータを転送して処理させるデータ処理スケジュールリング装置であって、
処理対象のデータを複数のチャンクに分割する分割手段と、
各チャンクのデータ転送時間とデータ処理時間を取得する時間取得手段と、
各チャンクのデータ転送時間とデータ処理時間の大小関係に基づいて、前記各チャンクを前記コ・プロセッサに処理させる順番を決定する順番決定手段と、
を備えることを特徴とするデータ処理スケジュールリング装置。
【請求項２】
前記順番決定手段は、前記各チャンクを、データ転送時間とデータ処理時間の大小関係に基づいて分別し、データ転送時間の方が小さいチャンクのグループをデータ転送時間の小さい順に処理した後にデータ転送時間の方が大きいチャンクのグループをデータ処理時間の大きい順に処理するように、各チャンクの順番を決定する、
ことを特徴とする請求項１に記載のデータ処理スケジュールリング装置。
【請求項３】
前記順番決定手段は、データ転送時間の方が小さいチャンクのグループをデータ転送時間の小さい順にソートし、データ転送時間の方が大きいチャンクのグループをデータ処理時間の大きい順にソートし、データ転送時間の方が小さいチャンクのグループが先になるように前記２つのグループのソート結果を結合して、チャンクの処理の順番のスケジュールリストを生成する、
ことを特徴とする請求項２に記載のデータ処理スケジュールリング装置。
【請求項４】
前記時間取得手段は、各チャンクのデータ転送時間とデータ処理時間を計測して取得し、
前記順番決定手段は、前記計測された各チャンクのデータ転送時間とデータ処理時間に基づいて、各チャンクを前記コ・プロセッサに処理させる順番を決定する
ことを特徴とする請求項１から３のいずれか１項に記載のデータ処理スケジュールリング装置。
【請求項５】
ホストからコ・プロセッサにデータを転送して処理させるデータ処理スケジュールリング方法あって、
処理対象のデータを複数のチャンクに分割し、
各チャンクのデータ転送時間とデータ処理時間を取得し、
各チャンクのデータ転送時間とデータ処理時間の大小関係に基づいて、前記各チャンクを前記コ・プロセッサに処理させる順番を決定する、
ことを特徴とするデータ処理スケジュールリング方法。
【請求項６】
コンピュータに、
処理対象のデータを複数のチャンクに分割する分割処理、
各チャンクのデータ転送時間とデータ処理時間を取得する時間取得処理、
各チャンクのデータ転送時間とデータ処理時間の大小関係に基づいて、前記各チャンクを前記コ・プロセッサに処理させる順番を決定する順番決定処理、
を実行させることを特徴とするプログラム。
【請求項１】
コ・プロセッサにデータを転送して処理させるデータ処理スケジュールリング装置であって、
処理対象のデータを複数のチャンクに分割する分割手段と、
各チャンクのデータ転送時間とデータ処理時間を取得する時間取得手段と、
各チャンクのデータ転送時間とデータ処理時間の大小関係に基づいて、前記各チャンクを前記コ・プロセッサに処理させる順番を決定する順番決定手段と、
を備えることを特徴とするデータ処理スケジュールリング装置。
【請求項２】
前記順番決定手段は、前記各チャンクを、データ転送時間とデータ処理時間の大小関係に基づいて分別し、データ転送時間の方が小さいチャンクのグループをデータ転送時間の小さい順に処理した後にデータ転送時間の方が大きいチャンクのグループをデータ処理時間の大きい順に処理するように、各チャンクの順番を決定する、
ことを特徴とする請求項１に記載のデータ処理スケジュールリング装置。
【請求項３】
前記順番決定手段は、データ転送時間の方が小さいチャンクのグループをデータ転送時間の小さい順にソートし、データ転送時間の方が大きいチャンクのグループをデータ処理時間の大きい順にソートし、データ転送時間の方が小さいチャンクのグループが先になるように前記２つのグループのソート結果を結合して、チャンクの処理の順番のスケジュールリストを生成する、
ことを特徴とする請求項２に記載のデータ処理スケジュールリング装置。
【請求項４】
前記時間取得手段は、各チャンクのデータ転送時間とデータ処理時間を計測して取得し、
前記順番決定手段は、前記計測された各チャンクのデータ転送時間とデータ処理時間に基づいて、各チャンクを前記コ・プロセッサに処理させる順番を決定する
ことを特徴とする請求項１から３のいずれか１項に記載のデータ処理スケジュールリング装置。
【請求項５】
ホストからコ・プロセッサにデータを転送して処理させるデータ処理スケジュールリング方法あって、
処理対象のデータを複数のチャンクに分割し、
各チャンクのデータ転送時間とデータ処理時間を取得し、
各チャンクのデータ転送時間とデータ処理時間の大小関係に基づいて、前記各チャンクを前記コ・プロセッサに処理させる順番を決定する、
ことを特徴とするデータ処理スケジュールリング方法。
【請求項６】
コンピュータに、
処理対象のデータを複数のチャンクに分割する分割処理、
各チャンクのデータ転送時間とデータ処理時間を取得する時間取得処理、
各チャンクのデータ転送時間とデータ処理時間の大小関係に基づいて、前記各チャンクを前記コ・プロセッサに処理させる順番を決定する順番決定処理、
を実行させることを特徴とするプログラム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【公開番号】特開２０１２−１９０２０６（Ｐ２０１２−１９０２０６Ａ）
【公開日】平成２４年１０月４日（２０１２．１０．４）
【国際特許分類】
【出願番号】特願２０１１−５２３６０（Ｐ２０１１−５２３６０）
【出願日】平成２３年３月１０日（２０１１．３．１０）
【国等の委託研究の成果に係る記載事項】（出願人による申告）平成２１年度 独立行政法人新エネルギー・産業技術総合開発機構 「グリーンネットワーク・システム技術研究開発プロジェクト（グリーンＩＴプロジェクト）」委託研究、産業技術力強化法第１９条の適用を受ける特許出願
【出願人】（０００００４２３７）日本電気株式会社 (19,353)
【公開日】平成２４年１０月４日（２０１２．１０．４）
【国際特許分類】
【出願日】平成２３年３月１０日（２０１１．３．１０）
【国等の委託研究の成果に係る記載事項】（出願人による申告）平成２１年度 独立行政法人新エネルギー・産業技術総合開発機構 「グリーンネットワーク・システム技術研究開発プロジェクト（グリーンＩＴプロジェクト）」委託研究、産業技術力強化法第１９条の適用を受ける特許出願
【出願人】（０００００４２３７）日本電気株式会社 (19,353)
[ Back to top ]