JP7273383B2

JP7273383B2 - スケジューリング方法、およびスケジューリング装置

Info

Publication number: JP7273383B2
Application number: JP2020056884A
Authority: JP
Inventors: 圭介黒木; 力佐々木
Original assignee: KDDI Corp
Current assignee: KDDI Corp
Priority date: 2020-03-26
Filing date: 2020-03-26
Publication date: 2023-05-15
Anticipated expiration: 2040-03-26
Also published as: JP2021157482A

Description

本発明は、ＦＰＧＡを時分割で利用するスケジューリング方法、およびスケジューリング装置に関する。

ネットワーク通信機器において、ＮＦＶ（Network Function Virtualization）などに代表されるように仮想化技術を用いて、通信機器を実現する事例が増えてきている。仮想化の技術には、仮想マシンよりも軽量なコンテナ技術を用いて通信機器を実現する事例も増えてきている。

一方で、仮想化技術は専用に作られたハードウェアではなく、汎用のサーバ上などで動作するため、これまでＡＳＩＣ（Application Specific Integrated Circuit）などで処理されてきた通信機器の機能が汎用ＣＰＵ（Central Processing Unit）上で処理されることにより、処理速度の低下などの問題も顕在化し、ＣＰＵの代わりにＧＰＵ（Graphics Processing Unit）やＦＰＧＡ（Field Programmable Gate Array）などに一部の処理をオフロードし、その問題解決の１つとして利用させる事例も増えてきている。

ＦＰＧＡを様々な機能で利用することを考えた場合、単純にはそれぞれの機能で利用するための回路情報を作成し、その回路情報を設定したＦＰＧＡを様々な機能分だけ用意すればよいが、特にコンテナなどで通信機器を構成し、機能（コンテナ）の種類が膨大になった場合に、その手法は費用がかかりすぎる。

一般にはＦＰＧＡを複数のプロセス（コンテナ）で共有する場合には、物理的に領域を分割するか、利用時間を分割（時分割）させるかの手法が考えられるが、前者は１つのプロセスで利用する回路規模が大きくなった場合に、やはりコストがかかるのと、後者は例えばＣＰＵのタスクスケジューリング方式などは単純に利用すると問題がでる。

特許文献１は、サービスとしてのＦＰＧＡへのアクセスを提供するための仕組みが開示されている。共用のＦＰＧＡ使用のためのプロビジョニング管理などが記述されている。ユーザからＦＰＧＡの回路内容である設計パッケージを受け取ると、管理ペイロードを付与し、更に管理ペイロードに適合するユーザキーを付与してコンパイルすることで、ユーザの認証や利用の開始・終了を管理し、サービスとして複数のユーザにＦＰＧＡを共有させることができる。

特表２０１５－５０７２３４号公報

しかし、複数のプロセスによる共有となると、一つ一つの利用時間が短いため、特許文献１記載の方法は、そのような場合の管理手法としては利用できない。また、ＣＰＵのタスクスケジューリングを単純に利用する場合に生じ得る問題とは、例えば、ラウンドロビン方式において論ずることができる。図２（ａ）はある時点で、タスクキューに入っているプロセスを示している。プロセス時間とは、ＦＰＧＡ上で実行される機能の実行開始から終了までの時間である。例えば、これらのプロセスをタイムクォンタム５のラウンドロビン方式で実行した場合、図２（ｂ）のように実行され、「プロセス－い」は実行がいつまでも終わらないことになる。これは、ＦＰＧＡはサーバのホスト上に置かれているコンパイルされた回路情報のバイナリファイルをＦＰＧＡに設定する時間（例えば、OpenCLで言えば、clCreateProgramWithBinary, clCreateKernelの実行時間）を要するため、プロセス時間のみだけでなく、その前処理の時間を測定し、それを考慮に入れる必要があるためである。

本発明は、このような事情に鑑みてなされたものであり、複数のプロセスでＦＰＧＡを時分割で利用する場合において、実行するプロセスの回路情報をＦＰＧＡに設定する時間を考慮してスケジューリングさせるスケジューリング方法、およびスケジューリング装置を提供することを目的とする。

（１）上記の目的を達成するため、本発明は、以下のような手段を講じた。すなわち、本発明の方法は、１または複数の仮想通信機器の複数のプロセスでＦＰＧＡを時分割で利用するスケジューリング方法であって、タスクキューにセットされている前記プロセスを確認するステップと、セットされている前記プロセスのバイナリファイルが前記ＦＰＧＡに設定される前処理時間を取得するステップと、前記タスクキューに複数の前記プロセスがセットされている場合、実行する前記プロセスの順序を決定するステップと、前記決定された順序に従い、実行する順序が到来した前記プロセスのバイナリファイルを前記ＦＰＧＡに設定し実行するステップと、を含み、前記プロセスの順序または前記プロセスを設定し実行する所定の時間は、前記プロセスごとの前処理時間に基づいて決定される。

これにより、複数のプロセスでＦＰＧＡを時分割で利用する場合において、実行するプロセスの回路情報をＦＰＧＡに設定する時間（前処理時間）を考慮してスケジューリングさせることができる。

（２）また、本発明の方法は、前記プロセスの順序または前記所定の時間を決定する方法を示すポリシの設定要求を受け付け、設定するステップを有し、前記プロセスの順序または前記所定の時間は、設定された前記ポリシおよび前記プロセスごとの前処理時間に基づいて決定される。

これにより、設定したポリシごとに異なる観点でプロセスの順序またはプロセスを設定し実行する所定の時間を決定できる。

（３）また、本発明の方法において、前記所定の時間は、前記プロセスごとの前処理時間とすべての前記プロセスに同一のタイムクォンタムとの和として前記プロセスごとに決定される。

このように、前処理時間＋タイムクォンタムを割当時間とすることで、前処理時間が長いプロセスがあっても、タイムクォンタムの分だけ実際の処理時間として与えられるので、終了しない処理が発生することはない。また、全てのプロセスでプロセス時間（実際の処理時間）が等しくなるため、実質的な意味での割当時間は公平になる。

（４）また、本発明の方法は、前記前処理時間を取得するステップにおいて、前記プロセスごとのプロセス時間をさらに取得し、前記プロセスの順序は、前記プロセスごとの前処理時間とプロセス時間との和である初回プロセス時間に基づいて決定される。

このように、前処理時間とプロセス時間を足し合わせた初回プロセス時間に基づいてプロセスの順序を決定することで、前処理時間を考慮しない方法よりターンアラウンドタイムを小さくできる。

（５）また、本発明の方法において、前記タスクキューにセットされている複数の前記プロセスに同一のプロセスが含まれる場合、前記同一のプロセスを連続して実行する場合に限定して、それぞれのプロセスの前記初回プロセス時間を算出する。

このように、プロセスの順序をプロセスごとの前処理時間とプロセス時間との和である初回プロセス時間に基づいて決定する方法において、タスクキューに同一のプロセスが複数入っていた場合は、同一のプロセスを連続して実行する場合に限定して前処理時間を算出することで、より適切なプロセスの順序を設定できる。

（６）また、本発明の方法は、複数の前記プロセスの順序の制約を示す順序情報を取得するステップを有し、前記プロセスの順序は、取得した前記ポリシ、前記プロセスごとの前処理時間、および前記順序情報に基づいて決定される。

これにより、プロセスに順序の制約がある場合も、取得したポリシ、プロセスごとの前処理時間、および順序情報に基づいて適切なプロセスの順序を設定できる。

（７）また、本発明の方法は、複数の前記プロセスの優先度の高さを示す優先度情報を取得するステップを有し、前記プロセスの順序は、取得した前記ポリシ、前記プロセスごとの前処理時間、および前記優先度情報に基づいて決定される。

これにより、プロセスに優先度がある場合も、取得したポリシ、プロセスごとの前処理時間、および優先度情報に基づいて適切なプロセスの順序を設定できる。

（８）また、本発明の方法において、前記タスクキューにセットされている複数の前記プロセスに前記優先度情報が同一のプロセスが含まれる場合、前記優先度情報が同一のプロセスごとに前記プロセスの順序が決定される。

これにより、プロセスに優先度があり、さらに同一の優先度を有するプロセスがある場合も、取得したポリシ、プロセスごとの前処理時間、および優先度情報に基づいて適切なプロセスの順序を設定できる。

（９）また、本発明の方法において、前記タスクキューにセットされている前記プロセスの実行中に、実行中の前記プロセスの前記優先度情報よりも優先度の高い前記優先度情報を有する他のプロセスが前記タスクキューにセットされた場合、実行中の前記プロセスの実行を中断し、前記他のプロセスの実行後に、中断した前記プロセスの実行を再開する。

これにより、プロセスの実行中に優先度の高いプロセスを割り込ませることができ、取得したポリシ、プロセスごとの前処理時間、および優先度情報に基づいて適切なプロセスの順序を設定できる。

（１０）また、本発明の方法は、過去の一定の時間内に実行された前記プロセスの現在の実行される可能性の高さを示す待機順位情報を取得するステップを有し、前記ＦＰＧＡを利用する前記プロセスが存在しないときに、前記待機順位情報に基づいて選択された前記プロセスのバイナリファイルを前記ＦＰＧＡにあらかじめ設定する。

これにより、次回設定される可能性の高いプロセスのバイナリファイルをあらかじめＦＰＧＡに設定し待機させることができ、予想が的中した場合に前処理時間を短縮できる。

（１１）また、本発明のスケジューリング装置は、１または複数の仮想通信機器の複数のプロセスでＦＰＧＡを時分割で利用させるスケジューリング装置であって、前記プロセスの実行命令を格納するタスクキューと、前記タスクキューにセットされている前記プロセスを確認し、前記タスクキューに複数の前記プロセスがセットされている場合、実行する前記プロセスの順序を決定し、前記決定された順序に従い、実行する順序が到来した前記プロセスのバイナリファイルの前記ＦＰＧＡへの設定を依頼し、設定されたバイナリファイルを実行するスケジュール部と、前記スケジュール部に依頼された前記プロセスのバイナリファイルを前記ＦＰＧＡに設定するバイナリ設定部と、セットされている前記プロセスのバイナリファイルが前記ＦＰＧＡに設定される前処理時間を取得する前処理測定部と、を備え、前記プロセスの順序または前記プロセスを設定し実行する所定の時間は、前記プロセスごとの前処理時間に基づいて決定される。

本発明によれば、複数のプロセスでＦＰＧＡを時分割で利用する場合において、実行するプロセスの回路情報をＦＰＧＡに設定する時間を考慮してスケジューリングさせることで、通常、時分割の使用に対応していないＦＰＧＡであっても時分割で使用することができ、コストを増加させないでＦＰＧＡのリソースを効率よく使用できる。

本実施形態に係るスケジューリング方法およびスケジューリング装置の基となる、コンテナ技術を用いた通信機器の仮想化およびコンテナ技術とＦＰＧＡとの関係の概念の一例を示す図である。従来方法のプロセスの具体例を示す表、およびそれに対する割当時間を示す概念図である。第１の実施形態に係るスケジューリング装置の概略構成の一例を示すブロック図である。（ａ）、（ｂ）それぞれ、ＤＢに保存される情報の例を示す表である。第２の実施形態に係るスケジューリング装置の概略構成の一例を示すブロック図である。第２の実施形態に係るスケジューリング装置の動作の一例を示すフローチャートである。第２の実施形態に係るスケジューリング装置の動作の一例を示すフローチャートである。（ａ）、（ｂ）それぞれ、実施例１のプロセスの具体例を示す表、およびそれに対する割当時間を示す概念図である。実施例１のプロセスの具体例を示す表である。図９に示されるプロセスの具体例に対する実施例１の割当時間を示す概念図である。（ａ）～（ｃ）それぞれ、第２の実施例のプロセスの具体例を示す表、通常の最短ジョブ優先方式の順序を示す概念図、および本発明の最短ジョブ優先方式の順序を示す概念図である。（ａ）、（ｂ）それぞれ、第３の実施例のプロセスの具体例を示す表、および本発明の最短ジョブ優先方式の順序を示す概念図である。（ａ）、（ｂ）それぞれ、第３の実施例のプロセスの具体例を示す表、および本発明の最短ジョブ優先方式の順序を示す概念図である。実施例３のスケジューリング装置の動作の一例を示すフローチャートである。第４の実施例のプロセスの具体例を示す表である。図１５に示されるプロセスの具体例に対する第４の実施例の順序と割当時間を示す概念図である。図１５に示されるプロセスの具体例に対する第４の実施例の順序と割当時間を示す概念図である。第４の実施例の変形例のプロセスの具体例を示す表である。（ａ）、（ｂ）それぞれ、第５の実施例のプロセスの具体例を示す表、および順序と割当時間を示す概念図である。第６の実施例のプロセスの具体例を示す表である。

本発明者らは、複数のプロセスでＦＰＧＡを時分割で利用する場合において、実行するプロセスの回路情報をＦＰＧＡに設定する時間を考慮してスケジューリングさせることで、通常、時分割の使用に対応していないＦＰＧＡであっても時分割で使用することができることを見出し、本発明をするに至った。

すなわち、本発明の方法は、１または複数の仮想通信機器の複数のプロセスでＦＰＧＡを時分割で利用するスケジューリング方法であって、タスクキューにセットされている前記プロセスを確認するステップと、セットされている前記プロセスのバイナリファイルが前記ＦＰＧＡに設定される前処理時間を取得するステップと、前記タスクキューに複数の前記プロセスがセットされている場合、実行する前記プロセスの順序を決定するステップと、前記決定された順序に従い、実行する順序が到来した前記プロセスのバイナリファイルを前記ＦＰＧＡに設定し実行するステップと、を含み、前記プロセスの順序または前記プロセスを設定し実行する所定の時間は、前記プロセスごとの前処理時間に基づいて決定される。

これにより、本発明者らは、通常、時分割の使用に対応していないＦＰＧＡであっても時分割で使用することができ、コストを増加させないでＦＰＧＡのリソースを効率よく使用できることを可能とした。以下、本発明の実施形態について、図面を参照しながら具体的に説明する。説明の理解を容易にするため、各図面において同一の構成要素に対しては同一の参照番号を付し、重複する説明は省略する。

［コンテナ技術とＦＰＧＡとの関係の概念］
図１は、本実施形態に係るスケジューリング方法およびスケジューリング装置の基となる、コンテナ技術を用いた通信機器の仮想化およびコンテナ技術とＦＰＧＡとの関係の概念の一例を示す図である。仮想通信機器は、１つ以上のコンテナで構成されて動作している。それぞれのコンテナは、１つ以上のプロセスの集合として構成されている。仮想通信機器は、例えば、ルータ、ファイアウォール、基地局、モバイルコア等が考えられるが、これに限定されるわけではない。プロセスとは、仮想通信機器の行なう処理を１つまたは複数の機能ごとに分割したものである。例えば、仮想通信機器がルータである場合、パケットをフィルタリングする機能、通信プロトコルを管理する機能等がプロセスとして考えられるが、これに限定されるわけではない。

個々のプロセスは、ハードウェアリソースを消費することで実行されるが、プロセスごとに消費するリソースには違いがある。例えば、図１の「プロセス－え」はＣＰＵを利用して実行されることを表している。一方、図１の「プロセス－あ」、「プロセス－い」、および「プロセス－う」は、ＦＰＧＡに設定されるプロセスごとの回路設定であるバイナリファイルを介して、ＦＰＧＡを利用して実行されることを表している。図１は、「プロセス－あ」、「プロセス－い」、および「プロセス－う」が、それぞれ「バイナリ－Ａ」、「バイナリ－Ｂ」、および「バイナリ－Ｃ」というＦＰＧＡに設定される回路設定と対応していることを表している。

このように、１つのＦＰＧＡは、１つのバイナリファイルが設定された場合、そのバイナリファイルに対応するプロセスの実行に対して使用され、他のバイナリファイルに対応するプロセスの実行に対して同時に使用されることはない。また、そのＦＰＧＡが他のバイナリファイルに対応するプロセスの実行に使用される場合、そのバイナリファイルを新たに設定して、その後使用される。すなわち、本発明において、１つのＦＰＧＡが異なるプロセスに対して使用される場合、時分割で使用される。なお、ＦＰＧＡは、それぞれのＦＰＧＡごとに管理されるため、複数存在していてもよい。

［第１の実施形態］
（スケジューリング装置の構成）
図３は、本実施形態に係るスケジューリング装置の概略構成の一例を示すブロック図である。図３では１つのサーバ１０内での実装を説明しているが、それぞれの要素が別のサーバで実装されていてもよい。「プロセス－あ」は、ある仮想化されたネットワーク機器のプロセスを示している。ＦＰＧＡ２０はサーバ内に実装されたＦＰＧＡであり、サーバ１０内に１つのＦＰＧＡが実装された例で説明を行う。スケジューリング装置１００は、タスクキュー１１０、スケジュール部１２０、バイナリ設定部１３０、および前処理測定部１４０によって構成されている。

タスクキュー１１０は、ＦＰＧＡ２０によって処理を行うプロセスの実行命令を格納する場所であり、タスクキュー１１０に格納された命令をポリシに沿って実行していく。ポリシとは、プロセスの実行順序や実行時間の決め方の基準である。例えば、公平性重視やターンアラウンドタイムの縮小重視などの基準がある。本実施形態では、ポリシはあらかじめ設定されているものとする。

スケジュール部１２０は、タスクキュー１１０にセットされているプロセスを確認する。なお、本実施形態では、スケジュール部１２０が定期的にタスクキュー１１０を確認する例で説明しているが、タスクキュー１１０にプロセスがセットされたタイミングでスケジュールをスタートさせてもよい。

タスクキュー１１０に複数のプロセスがセットされている場合、スケジュール部１２０は、実行するプロセスの順序を決定し、決定された順序に従い、バイナリ設定部１３０に対し、実行する順序が到来したプロセスのバイナリファイルのＦＰＧＡ２０への設定を依頼する。また、タスクキュー１１０に１つのプロセスがセットされている場合、スケジュール部１２０は、バイナリ設定部１３０に対し、そのプロセスのバイナリファイルのＦＰＧＡ２０への設定を依頼する。また、スケジュール部１２０は、ＦＰＧＡ２０に設定されたバイナリファイルを実行する。

プロセスの順序またはプロセスを設定し実行する所定の時間（割当時間）は、後述するプロセスごとの前処理時間に基づいて決定される。これにより、通常、時分割の使用に対応していないＦＰＧＡであっても時分割で使用することができ、コストを増加させないでＦＰＧＡのリソースを効率よく使用できる。

バイナリ設定部１３０は、スケジュール部１２０に依頼されたプロセスのバイナリファイルをＦＰＧＡ２０に設定する。本発明では、１つのプロセスに対応するＦＰＧＡの回路情報は事前にコンパイルされ、バイナリファイルとして管理される。各プロセスに対応するバイナリファイルは、ＤＢ５０に保存される。バイナリ設定部１３０は、ＤＢ５０から必要な情報を取得する。

前処理測定部１４０は、タスクキュー１１０にセットされているプロセスのバイナリファイルがＦＰＧＡ２０に設定される前処理時間を取得する。前処理時間は、あらかじめプロセスごとまたはバイナリファイルごとに設定されている値を取得してもよいが、バイナリファイルがＦＰＧＡ２０に設定されるごとに前処理測定部１４０が設定時間を測定して、測定した複数の値の平均値を前処理時間とすることが好ましい。これは、ＦＰＧＡに対するバイナリファイルの設定は、その回路規模によって設定時間が異なるため、実際に設定する度に、どの程度の時間がかかるかを測定した方が、より現実的な前処理時間に基づいてプロセスの順序またはプロセスを設定し実行する所定の時間を決定することができるからである。

測定された設定時間はＤＢ（データベース）５０に送信され、ＤＢ５０にはこれまでの測定値、それらの平均値、所定の測定回数分の平均値などのうち少なくとも１つが保持される。測定方法は限定されないが、例えば、スケジューリング装置１００が、ＯｐｅｎＣＬに基づいて構成される場合、バイナリ設定時のｃｌＣｒｅａｔｅＰｒｏｇｒａｍＷｉｔｈＢｉｎａｒｙ，ｃｌＣｒｅａｔｅＫｅｒｎｅｌの実行時間を前処理時間として測定することができる。

図４（ａ）、（ｂ）は、それぞれＤＢ５０に保存される情報の例を示す表である。ＤＢ５０は、プロセスごとのバイナリファイル、前処理測定部１４０で測定したプロセスごとの前処理時間、プロセスごとのプロセス時間、プロセスごとの前処理時間とプロセス時間を合計した初回処理時間（初回プロセス時間）などの情報が格納されている。また、後述する実施例で使用される複数のプロセスの順序の制約を示す順序情報、複数のプロセスの優先度の高さを示す優先度情報、過去の一定の時間内に実行されたプロセスの現在の実行される可能性の高さを示す待機順位情報などの様々なポリシに対応するために必要な情報が格納されていてもよい。また、ＤＢに保存される情報は、必要に応じて更新される。

［第２の実施形態］
（スケジューリング装置の構成）
図５は、本実施形態に係るスケジューリング装置の概略構成の一例を示すブロック図である。スケジューリング装置２００は、タスクキュー１１０、スケジュール部１２０、バイナリ設定部１３０、前処理測定部１４０、およびポリシ設計部２１０によって構成されている。タスクキュー１１０、スケジュール部１２０、バイナリ設定部１３０、および前処理測定部１４０の機能は、第１の実施形態と同様であるため、説明は省略する。

ポリシ設計部２１０は、プロセスの順序またはプロセスのバイナリファイルをＦＰＧＡ２０に設定し実行する所定の時間を決定する方法を示すポリシを設定する。ポリシ設計部２１０は、プロセススケジューリングの際に何を重視するかを、ユーザが設定要求する機能部であり、例えば、公平性重視やターンアラウンドタイムの縮小重視などが設定される。

スケジューリング装置２００は、ポリシ設計部２１０を備えることで、ユーザが重視するポリシを設定することができ、ＦＰＧＡ２０に処理させるプロセスや処理量に応じたポリシをユーザが選択することができる。

（動作の一例の説明）
次に、本実施形態に係るスケジューリング装置の動作の一例を、図６および図７のフローチャートを用いて説明する。図６および図７は、本実施形態に係るスケジューリング装置の動作の一例を示すフローチャートである。

図６および図７は、スケジューリング装置を構成する各機能部、ＤＢ、およびユーザの設定要求を含む。ＤＢからの情報の取得は、各機能部がそれぞれ受け持つ。まず、ユーザがスケジューリング装置にポリシの設定を要求する（ステップＳ１）。次に、ポリシ設計部は、設定するポリシに応じて考慮する時間を決定する（ステップＳ２）。考慮する時間（考慮時間）は、少なくとも前処理時間を含む。例えば、設定するポリシに応じて前処理時間、または前処理時間とプロセス時間を合わせた初回プロセス時間のいずれを考慮するかを決定することができる。考慮時間は、前処理時間に基づいて算出されていれば、ポリシごとにどのような時間を考慮時間としてもよい。次にポリシ設計部は、スケジュール部にポリシの設定（セット）を通知する（ステップＳ３）。

次に、スケジュール部はポリシの設定（セット）を受領し（ステップＳ４）、考慮時間を決定する（ステップＳ５）。その間、タスクキューにはプロセスがセットされる（ステップＳ６）。そして、タスクキューを確認し（ステップＳ７）、プロセスがセットされている場合（ステップＳ８－ＹＥＳ）、ＤＢに考慮時間の値の確認をする（ステップＳ９）。ＤＢは、考慮時間の値の確認メッセージを受領し（ステップＳ１０）、値を返信する（ステップＳ１１）。そして、スケジュール部は、考慮時間の値に基づいて、スケジュールの決定をする（ステップＳ１２）。なお、考慮時間の値とは、少なくともセットされたプロセスに対応するバイナリファイルの前処理時間を含む。また、スケジュールの決定は、少なくともプロセスの実行する順序またはプロセスを設定し実行する所定の時間を決定することを含む。

また、タスクキューを確認し（ステップＳ７）、プロセスがセットされていない場合（ステップＳ８－ＮＯ）、ステップＳ７に戻り、再度タスクキューの確認をする。

スケジュールの決定の後、スケジュール部は、回路情報を変更するかどうかを判断し、変更する場合（ステップＳ１３－ＹＥＳ）、バイナリ設定部に該当プロセスの回路の設定を指示する（ステップＳ１４）。回路情報を変更するかどうかの判断は、実行しようとしているプロセスのバイナリファイルがＦＰＧＡに設定されているかどうかを確認し判断することであり、直接ＦＰＧＡを確認してもよいが、前回の処理を確認するか、バイナリ設定部に問い合わせることが好ましい。また、該当プロセスの回路の設定とは、該当プロセスに対応するバイナリファイルの設定である。

バイナリ設定部は、該当プロセスの回路の設定の指示を受領（ステップＳ１５）し、ＤＢにプロセスの該当バイナリ（バイナリファイル）の確認をする（ステップＳ１６）。ＤＢは、バイナリ確認メッセージを受領（ステップＳ１７）し、バイナリ設定部にバイナリ情報（バイナリファイル）の返信をする（ステップＳ１８）。バイナリ設定部は、ＦＰＧＡにバイナリを設定し（ステップＳ１９）、前処理測定部にバイナリ設定時間の測定を依頼する（ステップＳ２０）。

前処理測定部は、バイナリ設定時間の測定依頼メッセージを受領し（ステップＳ２１）、測定を開始する。そして、測定が完了（ステップＳ２２）したら、ＤＢに測定値を通知する（ステップＳ２３）。ＤＢは、測定値を受領し（ステップＳ２４）、前処理時間の平均値の算出と格納をする（ステップＳ２５）。

一方、バイナリ設定部は、バイナリ設定完了（ステップＳ２６）後、スケジュール部に該当プロセスの回路設定完了を通知する（ステップＳ２７）。スケジュール部は、該当プロセスの回路設定完了通知を受領し（ステップＳ２８）、該当プロセスの実行をする（ステップＳ２９）。実行後、全てのプロセスが完了したかを判断し、完了した場合（ステップＳ３０－ＹＥＳ）、終了する。終了後、ポリシの変更をしない場合、ステップＳ７に戻ってタスクキューの確認をするように動作してもよい。

また、スケジュール部は、全てのプロセスが完了したかを判断し、完了していない場合（ステップＳ３０－ＮＯ）、ステップＳ１３に戻り、回路情報を変更するかを判断する。

また、スケジュール部は、ステップＳ１３で回路情報を変更するかどうかを判断し、変更しない場合（ステップＳ１３－ＮＯ）、該当プロセスの実行をする（ステップＳ２９）。

本実施形態に係るスケジューリング装置は、このようにして、動作することができる。なお、第１の実施形態に係るスケジューリング装置も、ポリシ設計部がないだけで、それ以外は同様の動作をすることができる。なお、上記の動作説明は、動作の一例を説明したものであり、本発明は、これに限定されるわけではない。

第１の実施形態および第２の実施形態の上記の説明では、説明が理解されやすいように、スケジューリング装置がハードウェアで実装されている例で説明したが、上記のフローチャートの説明で理解されるように、本発明は、スケジューリング装置の一部または全部がソフトウェアで実装されることが可能である。また、本発明は、１のソフトウェアとしてだけではなく、１または複数のサーバ上に実装された複数の機能の要素間で実行される処理方法として実装されることが可能である。以下の実施例も同様である。

［実施例］
次に実施例を説明する。以下の実施例では、プロセス間の公平性を重視して各プロセスにＦＰＧＡを割り当てる時間を決定する、いわゆるラウンドロビン方式と、ターンアラウンドタイムを小さくする、いわゆる最短ジョブ優先方式に基づいた方法を採用した場合の実施例を説明するが、本発明は、これに限定されるわけではない。各プロセスで利用する回路データのバイナリファイルを、時分割でＦＰＧＡに設定する際に、ＦＰＧＡへの設定時間（前処理時間）を考慮したスケジューリングをする方法は、本発明に含まれる。

（実施例１）
まず、公平性を重視する方法について説明する。ポリシ設計部に公平性重視が設定された場合は、スケジューリング装置は、プロセス間の割当時間を実質的に公平に割り当てることを重視することとする。この場合、スケジュール部は全プロセスに共通のタイムクウォンタムにプロセスごとの前処理時間を足したものを各プロセスに割り当てる時間とする。具体的な例として、図８（ａ）のプロセスをスケジュールする場合、および図９のプロセスをスケジュールする場合で説明する。図８（ａ）、（ｂ）は、それぞれ、本実施例のプロセスの具体例を示す表および割当時間を示す概念図である。図９は、本実施例のプロセスの具体例を示す表である。図１０は、図９に示されるプロセスの具体例に対する割当時間を示す概念図である。

例えば、タイムクウォンタムを５として図８（ａ）のプロセスをスケジュールする場合、「プロセス－あ」には前処理時間２＋タイムクォンタム５で割当時間７、「プロセス－い」には前処理時間５＋タイムクォンタム５で割当時間１０、「プロセス－う」には前処理時間４＋タイムクォンタム５で割当時間９を割り当てることをスケジュールし、図８（ｂ）のように実行する。

また、プロセス時間が上記より長い例として、図９のプロセスをスケジュールする場合で説明する。例えば、タイムクウォンタムを上記と同様に５として、図９のプロセスをスケジュールする場合、「プロセス－あ」には前処理時間２＋タイムクォンタム５で割当時間７、「プロセス－い」には前処理時間５＋タイムクォンタム５で割当時間１０、「プロセス－う」には前処理時間４＋タイムクォンタム５で割当時間９を割り当てることをスケジュールし、図１０のように実行する。

このように、前処理時間＋タイムクォンタムを割当時間とすることで、前処理時間が長いプロセスがあっても、タイムクォンタムの分だけ実際の処理時間として与えられるので、図２（ａ）、（ｂ）に示される例のように、終了しない処理が発生することはない。また、全てのプロセスでタイムクォンタム（実際の処理時間）が等しくなるため、実質的な意味での割当時間は公平になる。

（実施例２）
次に、ターンアラウンドタイムを小さくする方法を説明する。ターンアラウンドタイムを小さくする代表的なスケジューリング方式として最短ジョブ優先方式がある。通常、最短ジョブ優先方式ではプロセス時間が最短であるものが優先して実行されるが、本発明では前処理時間とプロセス時間を足し合わせた初回プロセス時間が最短であるものが優先して実行される。

具体的な例として、図１１（ａ）のプロセスをスケジュールする場合で説明する。図１１（ａ）～（ｃ）は、それぞれ、本実施例のプロセスの具体例を示す表、通常の最短ジョブ優先方式の順序を示す概念図、および本発明の最短ジョブ優先方式の順序を示す概念図である。通常の最短ジョブ優先方式は、プロセス時間が最短であるものが優先して実行されるため、図１１（ａ）のプロセスでは、図１１（ｂ）に示されるように、「プロセス－い」、「プロセス－う」、「プロセス－あ」の順序で実行される。この場合のターンアラウンドタイムは、（７＋１３＋１８）／３≒１２．６７となる。これに対し、本発明の最短ジョブ優先方式は、前処理時間とプロセス時間を足し合わせた初回プロセス時間が最短であるものが優先して実行される。そのため、図１１（ａ）のプロセスでは、「プロセス－あ」、「プロセス－う」、「プロセス－い」の順序で実行される。この場合のターンアラウンドタイムは、（５＋１１＋１８）／３≒１１．３３となる。

このように、前処理時間とプロセス時間を足し合わせた初回プロセス時間が最短であるものを優先して実行することで、前処理時間を考慮しない方法よりターンアラウンドタイムを小さくできる。

（実施例３）
次に、ターンアラウンドタイムを小さくする方法において、タスクキューに同一のプロセスが複数入っていた場合の方法を説明する。タスクキューにセットされている複数の前記プロセスに同一のプロセスが含まれる場合、同一のプロセスを連続して実行する場合に限定して、それぞれのプロセスの初回プロセス時間を算出することが好ましい。言い換えると、タスクキューに同一のプロセスが複数入っていた場合には、各プロセスの順番の組み合わせから、同一プロセスが連続しないものを除き、その他の組み合わせの、各プロセスが終了する時間をそれぞれ足し合わせ、その合計値が一番小さいパターンでスケジュールする。

具体的な例として、図１２（ａ）のプロセスをスケジュールする場合、および図１３（ａ）のプロセスをスケジュールする場合で説明する。図１２（ａ）、（ｂ）は、それぞれ、本実施例のプロセスの具体例を示す表、および本発明の最短ジョブ優先方式の順序を示す概念図である。タスクキューに「プロセス－あ、い、い、う」がセットされているとする。このとき、２つの「プロセス－い」を連続して実行した場合のそれぞれのプロセスの初回プロセス時間を算出する。そうすると、「プロセス－あ」の初回プロセス時間は５、１つ目の「プロセス－い」の初回プロセス時間は７、２つ目の「プロセス－い」の初回プロセス時間は９、「プロセス－う」の初回プロセス時間は６となる。ただし、２つの「プロセス－い」は連続して実行される。このときの考えられる順番は、「いいあう」、「いいうあ」、「あいいう」、「ういいあ」、「うあいい」、「あういい」の６通りであるが、このうちターンアラウンドタイムが最小となる順番は、図１１に示した「いいあう」であり、その値は１２．５である。

一方、連続するプロセスは、最初に実行されるほうがターンアラウンドタイムが小さくなるとは限らない。図１３（ａ）に示されるプロセスは、図１２（ａ）の「プロセス－い」の前処理時間を１０に変更したプロセスである。図１３（ａ）に示されるプロセスをスケジュールする場合、考えられる順番は上記と同様に、「いいあう」、「いいうあ」、「あいいう」、「ういいあ」、「うあいい」、「あういい」の６通りであるが、このうちターンアラウンドタイムが最小となる順番は、図１３（ｂ）に示した「あういい」である。

（実施例３の動作の一例）
実施例３の動作の一例を図１４のフローチャートを用いて説明する。図１４は、実施例３のスケジューリング装置の動作の一例を示すフローチャートである。まず、タスクキューを確認する（ステップＴ１）。次に、タスクキューに同一プロセスが存在するかどうか確認し、同一プロセスが存在しない場合（ステップＴ２－ＮＯ）、初回プロセス時間が短い順に並び替え（ステップＴ３）、その順番でプロセスを実行し（ステップＴ８）、全てのプロセスが実行されたら終了する。

一方、タスクキューに同一プロセスが存在するかどうか確認し、同一プロセスが存在する場合（ステップＴ２－ＹＥＳ）、プロセスの順番のパターンを算出する（ステップＴ４）。次に、算出した順番のパターンから同一プロセスが連続しないものを除き（ステップＴ５）、算出された順番のパターンにおいて、それぞれのプロセス終了時間の合計値を算出する（ステップＴ６）。そして、算出した合計値の小さい順に並び替え（ステップＴ７）、その順番でプロセスを実行し（ステップＴ８）、全てのプロセスが実行されたら終了する。

このように、ターンアラウンドタイムを小さくする方法において、タスクキューに同一のプロセスが複数入っていた場合も、前処理時間を考慮することで、ターンアラウンドタイムを小さくすることができる。

（実施例４）
ＦＰＧＡの時分割を適用する際、プロセス間に順序の制約や優先度を考慮する場合においても、前処理時間などの考慮が活用できる。例えば、図１５のように優先値（優先度情報）を設けることで、プロセス間の順序制約や優先度などを表現することができる。図１５の例では、優先値が大きいほど優先することを示し、「プロセス－あ」および「プロセス－う」は、「プロセス－い」の後に実行することを示している。例えば、これをラウンドロビン、タイムクォンタム５で実行した場合、図１６のように、タイムクォンタムに前処理時間を加算したものがそれぞれに割り当てられつつ、「プロセス－い」を先に実行することになる。

また、タスクキュー内のプロセスが図１５の場合で、且つ最短ジョブ優先を行う場合は図１７のように実行される。

このように、プロセスに優先度がある場合のプロセスの順序は、設定されたポリシ、プロセスごとの前処理時間、および優先度情報に基づいて決定される。これにより、プロセスに優先度がある場合も、取得したポリシ、プロセスごとの前処理時間、および優先度情報に基づいて適切なプロセスの順序を設定できる。

また、タスクキューにセットされている複数のプロセスに優先度情報が同一のプロセスが含まれる場合、優先度情報が同一のプロセスごとにプロセスの順序が決定されることが好ましい。これにより、プロセスに優先度があり、さらに同一の優先度を有するプロセスがある場合も、取得したポリシ、プロセスごとの前処理時間、および優先度情報に基づいて適切なプロセスの順序を設定できる。

（実施例４変形例）
なお、図１５に示される優先値の場合、全てのプロセス間で同一の値を含め優先度の差異があり、これを用いて順序の制約を表すこともできるが、一部のプロセス間にのみ順序の制約を示す順序情報を設けてもよい。例えば、図１８に示されるプロセスは、順序情報の数字の順序でプロセスが実行される必要があることを表し、「プロセス－あ」は「プロセス－い」の後に実行することを示し、「プロセス－う」は「プロセス－い」の前、「プロセス－い」と「プロセス－あ」の間、「プロセス－あ」の後の、どの段階で実行してもよいことを示している。

このように、順序情報がある場合のプロセスの順序は、設定されたポリシ、プロセスごとの前処理時間、および順序情報に基づいて決定される。これにより、プロセスに順序の制約がある場合も、取得したポリシ、プロセスごとの前処理時間、および順序情報に基づいて適切なプロセスの順序を設定できる。

（実施例５）
プリエンプション（優先度の高いものがタスクキューに新たに到着した際に、実行中のプロセスを停止して、優先度の高いプロセスを実行すること）方式が選択される場合においても、ＦＰＧＡの時分割適用には、前処理時間等の考慮が必要になる。例えば、最短ジョブ優先方式が選択され、さらに図１９（ａ）のように「プロセス－い」が遅れて到着し、プリエンプションが行われる場合は図１９（ｂ）のように実行される。但し、本実施例は図６、７のフローチャートとは少し異なることに注意が必要である。図６、７のフローチャートに従うと、到着時間０の「プロセス－あ、う」を実行した後で、タスクキューの確認に行くので、「プロセス－い」の到着に気が付けない。

よって、図１９（ｂ）のように実行するには、タスクキューの定期確認を、プロセス実行とは独立して、実施するか、優先度の高いプロセスがタスクキューに入ったことを（タスクキューなど）別の機構がスケジュール部に知らせる必要がある。

（実施例６）
次に、ＦＰＧＡを利用するプロセスが存在しない時間に、ＦＰＧＡにいずれかの回路情報（バイナリファイル）を設定して待機しておくことで、プロセスの処理時間を短縮する方法を説明する。次に実行される、ＦＰＧＡを利用するプロセスの回路情報をＦＰＧＡに設定し待機しておけば、前処理時間を削減することができる。

そこで新たに、ＤＢに図２０のような待機順位情報を設ける。これは、過去の一定の時間当たりでどのプロセスが何回呼ばれたかという情報を保持し、更にそれに前処理時間を乗じた値を重みとして保持している。この重みが大きいということは頻繁に利用される、またはボトルネックとなる前処理時間が大きいことを意味し、この順位が１位のものをＦＰＧＡの待機時間に設定する。また、この方式はＦＰＧＡが複数ある場合にも有用であり、例えば、ＦＰＧＡが２枚ある場合には、１枚目に１位のバイナリを設定し、２枚目に２位のバイナリを設定して待機することで、より効率的にターンアラウンドタイムを小さくすることができる。なお、この方法は、ターンアラウンドタイムを小さくする方法において効果的に使用されるが、ラウンドロビンで実行される場合も、少なくとも初回の前処理時間が短縮される意味において効果を有する。

以上説明したように、本発明のスケジューリング方法、およびスケジューリング装置は、複数のプロセスでＦＰＧＡを時分割で利用する場合において、実行するプロセスの回路情報をＦＰＧＡに設定する時間を考慮してスケジューリングさせることで、通常、時分割の使用に対応していないＦＰＧＡであっても時分割で使用することができ、コストを増加させないでＦＰＧＡのリソースを効率よく使用できる。

１０サーバ
２０ＦＰＧＡ
５０ＤＢ
１００、２００スケジューリング装置
１１０タスクキュー
１２０スケジュール部
１３０バイナリ設定部
１４０前処理測定部
２１０ポリシ設計部

Claims

１または複数の仮想通信機器の複数のプロセスでＦＰＧＡを時分割で利用するスケジューリング方法であって、
タスクキューにセットされている前記プロセスを確認するステップと、
セットされている前記プロセスのバイナリファイルが前記ＦＰＧＡに設定される前処理時間を取得するステップと、
前記タスクキューに複数の前記プロセスがセットされている場合、実行する前記プロセスの順序を決定するステップと、
前記決定された順序に従い、実行する順序が到来した前記プロセスのバイナリファイルを前記ＦＰＧＡに設定し実行するステップと、を含み、
前記プロセスのバイナリファイルを前記ＦＰＧＡに設定し実行する割当時間は、前記プロセスごとの前処理時間とすべての前記プロセスに同一のタイムクォンタムとの和として前記プロセスごとに決定されることを特徴とする方法。
１または複数の仮想通信機器の複数のプロセスでＦＰＧＡを時分割で利用するスケジューリング方法であって、
タスクキューにセットされている前記プロセスを確認するステップと、
セットされている前記プロセスのバイナリファイルが前記ＦＰＧＡに設定される前処理時間を取得するステップと、
前記タスクキューに複数の前記プロセスがセットされている場合、実行する前記プロセスの順序を決定するステップと、
前記決定された順序に従い、実行する順序が到来した前記プロセスのバイナリファイルを前記ＦＰＧＡに設定し実行するステップと、を含み、
前記前処理時間を取得するステップにおいて、前記プロセスごとのプロセス時間をさらに取得し、
前記プロセスの順序は、前記プロセスごとの前処理時間と前記プロセス時間との和である初回プロセス時間に基づいて決定されることを特徴とする方法。
１または複数の仮想通信機器の複数のプロセスでＦＰＧＡを時分割で利用するスケジューリング方法であって、
前記プロセスの順序または前記プロセスのバイナリファイルを前記ＦＰＧＡに設定し実行する割当時間を決定する方法を示すポリシの設定要求を受け付け、設定するステップと、
タスクキューにセットされている前記プロセスを確認するステップと、
セットされている前記プロセスのバイナリファイルが前記ＦＰＧＡに設定される前処理時間を取得するステップと、
複数の前記プロセスのうち一部の前記プロセスの順序の制約を示す順序情報を取得するステップと、
前記タスクキューに複数の前記プロセスがセットされている場合、実行する前記プロセスの順序を決定するステップと、
前記決定された順序に従い、実行する順序が到来した前記プロセスのバイナリファイルを前記ＦＰＧＡに設定し実行するステップと、を含み、
前記プロセスの順序は、設定された前記ポリシ、前記プロセスごとの前処理時間を含む考慮時間、および前記順序情報に基づいて決定されることを特徴とする方法。
１または複数の仮想通信機器の複数のプロセスでＦＰＧＡを時分割で利用するスケジューリング方法であって、
タスクキューにセットされている前記プロセスを確認するステップと、
セットされている前記プロセスのバイナリファイルが前記ＦＰＧＡに設定される前処理時間を取得するステップと、
前記タスクキューに複数の前記プロセスがセットされている場合、実行する前記プロセスの順序を決定するステップと、
前記決定された順序に従い、実行する順序が到来した前記プロセスのバイナリファイルを前記ＦＰＧＡに設定し実行するステップと、
過去の一定の時間内に実行された前記プロセスの現在の実行される可能性の高さを示す待機順位情報を取得するステップと、を含み、
前記プロセスの順序または前記プロセスのバイナリファイルを前記ＦＰＧＡに設定し実行する割当時間は、前記プロセスごとの前処理時間を含む考慮時間に基づいて決定され、
前記ＦＰＧＡを利用する前記プロセスが存在しないときに、前記待機順位情報に基づいて選択された前記プロセスのバイナリファイルを前記ＦＰＧＡにあらかじめ設定することを特徴とする方法。
前記タスクキューにセットされている複数の前記プロセスに同一のプロセスが含まれる場合、前記同一のプロセスを連続して実行する場合に限定して、それぞれのプロセスの前記初回プロセス時間を算出することを特徴とする請求項２記載の方法。
過去の一定の時間内に実行された前記プロセスの現在の実行される可能性の高さを示す待機順位情報を取得するステップを有し、
前記ＦＰＧＡを利用する前記プロセスが存在しないときに、前記待機順位情報に基づいて選択された前記プロセスのバイナリファイルを前記ＦＰＧＡにあらかじめ設定することを特徴とする請求項１から請求項３のいずれかに記載の方法。
１または複数の仮想通信機器の複数のプロセスでＦＰＧＡを時分割で利用させるスケジューリング装置であって、
前記プロセスの実行命令を格納するタスクキューと、
前記タスクキューにセットされている前記プロセスを確認し、前記タスクキューに複数の前記プロセスがセットされている場合、実行する前記プロセスの順序を決定し、前記決定された順序に従い、実行する順序が到来した前記プロセスのバイナリファイルの前記ＦＰＧＡへの設定を依頼し、設定されたバイナリファイルを実行するスケジュール部と、
前記スケジュール部に依頼された前記プロセスのバイナリファイルを前記ＦＰＧＡに設定するバイナリ設定部と、
セットされている前記プロセスのバイナリファイルが前記ＦＰＧＡに設定される前処理時間を取得する前処理測定部と、を備え、
前記プロセスのバイナリファイルを前記ＦＰＧＡに設定し実行する割当時間は、前記プロセスごとの前処理時間とすべての前記プロセスに同一のタイムクォンタムとの和として前記プロセスごとに決定されることを特徴とするスケジューリング装置。
１または複数の仮想通信機器の複数のプロセスでＦＰＧＡを時分割で利用させるスケジューリング装置であって、
前記プロセスの実行命令を格納するタスクキューと、
前記タスクキューにセットされている前記プロセスを確認し、前記タスクキューに複数の前記プロセスがセットされている場合、実行する前記プロセスの順序を決定し、前記決定された順序に従い、実行する順序が到来した前記プロセスのバイナリファイルの前記ＦＰＧＡへの設定を依頼し、設定されたバイナリファイルを実行するスケジュール部と、
前記スケジュール部に依頼された前記プロセスのバイナリファイルを前記ＦＰＧＡに設定するバイナリ設定部と、
セットされている前記プロセスのバイナリファイルが前記ＦＰＧＡに設定される前処理時間を取得する前処理測定部と、を備え、
前記スケジュール部は、前記プロセスごとのプロセス時間を取得し、
前記プロセスの順序は、前記プロセスごとの前処理時間とプロセス時間との和である初回プロセス時間に基づいて決定されることを特徴とするスケジューリング装置。
１または複数の仮想通信機器の複数のプロセスでＦＰＧＡを時分割で利用させるスケジューリング装置であって、
前記プロセスの順序または前記プロセスのバイナリファイルを前記ＦＰＧＡに設定し実行する割当時間を決定する方法を示すポリシを設定するポリシ設計部と、
前記プロセスの実行命令を格納するタスクキューと、
前記タスクキューにセットされている前記プロセスを確認し、前記タスクキューに複数の前記プロセスがセットされている場合、実行する前記プロセスの順序を決定し、前記決定された順序に従い、実行する順序が到来した前記プロセスのバイナリファイルの前記ＦＰＧＡへの設定を依頼し、設定されたバイナリファイルを実行するスケジュール部と、
前記スケジュール部に依頼された前記プロセスのバイナリファイルを前記ＦＰＧＡに設定するバイナリ設定部と、
セットされている前記プロセスのバイナリファイルが前記ＦＰＧＡに設定される前処理時間を取得する前処理測定部と、を備え、
前記スケジュール部は、複数の前記プロセスのうち一部の前記プロセスの順序の制約を示す順序情報を取得し、
前記プロセスの順序は、設定された前記ポリシ、前記プロセスごとの前処理時間を含む考慮時間、および前記順序情報に基づいて決定されることを特徴とするスケジューリング装置。
１または複数の仮想通信機器の複数のプロセスでＦＰＧＡを時分割で利用させるスケジューリング装置であって、
前記プロセスの実行命令を格納するタスクキューと、
前記タスクキューにセットされている前記プロセスを確認し、前記タスクキューに複数の前記プロセスがセットされている場合、実行する前記プロセスの順序を決定し、前記決定された順序に従い、実行する順序が到来した前記プロセスのバイナリファイルの前記ＦＰＧＡへの設定を依頼し、設定されたバイナリファイルを実行するスケジュール部と、
前記スケジュール部に依頼された前記プロセスのバイナリファイルを前記ＦＰＧＡに設定するバイナリ設定部と、
セットされている前記プロセスのバイナリファイルが前記ＦＰＧＡに設定される前処理時間を取得する前処理測定部と、を備え、
前記スケジュール部は、過去の一定の時間内に実行された前記プロセスの現在の実行される可能性の高さを示す待機順位情報を取得し、
前記プロセスの順序または前記プロセスのバイナリファイルを前記ＦＰＧＡに設定し実行する割当時間は、前記プロセスごとの前処理時間を含む考慮時間に基づいて決定され、
前記バイナリ設定部は、前記ＦＰＧＡを利用する前記プロセスが存在しないときに、前記待機順位情報に基づいて選択された前記プロセスのバイナリファイルを前記ＦＰＧＡにあらかじめ設定することを特徴とするスケジューリング装置。