(57)【要約】【課題】短い処理完了時間で高いスループットを得るワークフロースケジューリングシステム、ワークフロースケジューリング方法及び電子機器を提供する。【解決手段】実施形態によれば、ワークフロースケジューリングシステムは、各々が１以上のタスクを含む複数のワークフローを複数の計算機資源を含む１以上の計算単位によって並列に処理する場合におけるタスクの実行順を計画する。ワークフロースケジューリングシステムは、複数のワークフローのうち１以上のワークフローに含まれる１以上のタスクの集合であるタスクグループごとに、タスクが同時に実行されるワークフローの数が複数の計算単位の数以下の第１個数までに制限されるように制御を行う制御手段を備える。【選択図】  図１
2019121240.tif 000002
【特許請求の範囲】
【請求項１】
各々が１以上のタスクを含む複数のワークフローを複数の計算機資源を含む１以上の計算単位によって並列に処理する場合におけるタスクの実行順を計画するワークフロースケジューリングシステムであって、
前記複数のワークフローのうち１以上のワークフローに含まれる１以上のタスクの集合であるタスクグループごとに、タスクが同時に実行されるワークフローの数が前記計算単位の数以下の第１個数までに制限されるように制御を行う制御手段
を備えるワークフロースケジューリングシステム。
【請求項２】
前記タスクグループは、前記複数のワークフローのうちの異なるワークフローにそれぞれ含まれる１以上のタスクの集合である
請求項１に記載のワークフロースケジューリングシステム。
【請求項３】
前記タスクグループは、同一ワークフロー内の一連のタスクを含む
請求項１又は請求項２に記載のワークフロースケジューリングシステム。
【請求項４】
前記タスクグループは、同一ワークフロー内で並列して処理可能なタスクを含む
請求項１又は請求項２に記載のワークフロースケジューリングシステム。
【請求項５】
前記ワークフローの構成情報に基づいて前記タスクの状態を管理し、前記タスクのうち実行可能な１以上の第１タスクを選択する管理手段を備え、
前記制御手段は、前記第１タスクの中から実行対象とする１以上の第２タスクを選択する第１計画手段を含み、
前記第２タスクに対して所定の前記計算機資源を割り当てる第２計画手段を備える
請求項１乃至請求項４のいずれか一項に記載のワークフロースケジューリングシステム。
【請求項６】
前記制御手段は、前記タスクグループごとにセマフォ又はミューテックスを用いて前記制御を行う
請求項１乃至請求項５のいずれか一項に記載のワークフロースケジューリングシステム。
【請求項７】
前記制御手段は、前記タスクグループごとに、分散ロックマネージャにより構成された分散セマフォ、又は、前記分散ロックマネージャにより構成された分散セマフォを用いて前記制御を行う
請求項１乃至請求項５のいずれか一項に記載のワークフロースケジューリングシステム。
【請求項８】
前記計算機資源は、１以上の主記憶装置と１以上のプロセッサを備える
請求項１乃至請求項５のいずれか一項に記載のワークフロースケジューリングシステム。
【請求項９】
前記タスクの処理前及び前記タスクの処理後に前記制御手段を実行するための制御タスクを前記ワークフローに加えた拡大ワークフローの構成情報に基づいて、前記タスク及び前記制御タスクの状態を管理し、前記タスク及び前記制御タスクのうち実行可能な１以上の第１タスクを選択する管理手段と、
前記第１タスクのうち実行対象とする１以上の第２タスクに対して所定の前記計算機資源を割り当てる計画手段と、
を備える
請求項１乃至請求項４のいずれか一項に記載のワークフロースケジューリングシステム。
【請求項１０】
前記計画手段は、前記第２タスクが前記制御タスクである場合には、前記第２タスクに対して前記計算機資源のうち第１計算機資源を割り当て、前記第２タスクが前記制御タスクでない場合には、前記第２タスクに対して前記計算機資源のうち前記第１計算機資源と重複しない第２計算機資源を割り当てる
請求項９に記載のワークフロースケジューリングシステム。
【請求項１１】
前記制御タスクは、分散ロックマネージャを用いて実装される分散ファイルロックコマンドを用いて分散セマフォ又は分散ミューテックスを操作するスクリプトを、前記計算機資源により構成される所定の計算ノードに実行させる
請求項９又は請求項１０に記載のワークフロースケジューリングシステム。
【請求項１２】
前記分散ロックマネージャは、ＯＣＦＳ２フォーマットのファイルシステムにより提供される
請求項１１に記載のワークフロースケジューリングシステム。
【請求項１３】
前記タスクの処理前及び前記タスクの処理後に前記制御手段を実行するための制御タスクを前記ワークフローに加えた拡大ワークフローの構成情報に基づいて、前記タスク及び前記制御タスクの状態を管理し、実行可能な前記制御タスクを実行し、前記タスクのうち実行対象とする１以上の第１タスクを選択する管理手段と、
前記第１タスクに対して所定の前記計算機資源を割り当てる計画手段と、
を備える
請求項１乃至請求項４のいずれか一項のワークフロースケジューリングシステム。
【請求項１４】
各々が１以上のタスクを含む複数のワークフローを複数の計算機資源を含む１以上の計算単位によって並列に処理する場合におけるタスクの実行順を計画するワークフロースケジューリング方法であって、
ワークフローの構成情報に基づいて前記タスクの状態を管理し、前記タスクのうち実行可能な１以上の第１タスクを選択することと、
前記第１タスクの中から実行対象とする１以上の第２タスクを選択することと、
前記複数のワークフローのうち１以上のワークフローに含まれる１以上の前記タスクの集合であるタスクグループごとに、前記第２タスクが同時に実行されるワークフローの数が前記計算単位の数以下の第１個数までに制限されるように制御を行うことと
前記第２タスクに対して所定の前記計算機資源を割り当てることと、
を備えるワークフロースケジューリング方法。
【請求項１５】
各々が１以上のタスクを含む複数のワークフローを並列に処理可能な計算機資源と、
ワークフローの構成情報に基づいて前記タスクの状態を管理し、前記タスクのうち実行可能な１以上の第１タスクを選択する管理手段と、
前記第１タスクの中から実行対象とする１以上の第２タスクを選択する第１計画手段と、
前記複数のワークフローのうち１以上のワークフローに含まれる１以上の前記タスクの集合であるタスクグループごとに、前記第２タスクが同時に実行されるワークフローの数が複数の前記計算機資源からなる所定の計算単位の数以下の第１個数までに制限されるように制御を行う制御手段と、
前記第２タスクに対して所定の前記計算機資源を割り当てる第２計画手段と、
を備える電子機器。
【発明の詳細な説明】
【技術分野】
【０００１】
本実施形態は、計算機におけるスケジューリング技術に関する。
【背景技術】
【０００２】
計算機においては、複数のジョブを計算機資源（リソース）を用いて効率よく実行するために、例えばどのタイミングで、どのリソースを用いてどのジョブを処理するかを決定するスケジューリング技術が用いられる。
【先行技術文献】
【非特許文献】
【０００３】
【非特許文献１】Zhifeng Yu、“TOWARD PRACTICAL MULTI-WORKFLOW SCHEDULING IN CLUSTER AND GRID ENVIRONMENTS”、[online]、２００９年５月、［平成３０年１月５日検索］、インターネット＜URL:http://www.cs.wayne.edu/~weisong/papers/yu08-dissertation.pdf＞
【発明の概要】
【発明が解決しようとする課題】
【０００４】
スケジューリング技術においては、単位時間ごとに実行完了するジョブの数（以下、スループットと呼ぶ）を最大化し、全てのジョブが実行完了するまでにかかる時間（以下、処理完了時間と呼ぶ）を最小化するように、各ジョブに対してリソースが割り当てられることが好ましい。例えば、複数の処理対象のジョブが存在する場合、１つのジョブにリソースを集中させると、スループットは向上するが、処理完了時間は長くなる場合がある。一方、複数のジョブを全て並列に処理すると、処理完了時間は短くなるが、スループットは低下する場合がある。
【０００５】
本発明が解決しようとする課題は、短い処理完了時間で高いスループットを得るワークフロースケジューリングシステム、ワークフロースケジューリング方法及び電子機器を提供することである。
【課題を解決するための手段】
【０００６】
実施形態によれば、ワークフロースケジューリングシステムは、各々が１以上のタスクを含む複数のワークフローを複数の計算機資源を含む１以上の計算単位によって並列に処理する場合におけるタスクの実行順を計画する。前記ワークフロースケジューリングシステムは、前記複数のワークフローのうち１以上のワークフローに含まれる１以上のタスクの集合であるタスクグループごとに、タスクが同時に実行されるワークフローの数が前記複数の計算単位の数以下の第１個数までに制限されるように制御を行う制御手段を備える。
【図面の簡単な説明】
【０００７】
【図１】第１の実施形態に係る計算機システムの一例を示すブロック図。
【図２】第１の実施形態に係るＷＦＤＡＧの一例を示す図。
【図３】第１の実施形態に係るタスクグループ定義の一例を示す図。
【図４】第１の実施形態に係るマルチワークフロースケジューリングシステムの一例を示す図。
【図５】第１の実施形態に係るリソースプールの一例を示す図。
【図６】第１の実施形態に係るスケジューリング処理の一例を示す図。
【図７】第１の実施形態に係るスケジューリング結果の第１の例を示す図。
【図８】第１の実施形態に係るスケジューリング結果の第２の例を示す図。
【図９】第２の実施形態に係る拡大ＷＦＤＡＧの一例を示す図。
【図１０】第２の実施形態に係るマルチワークフロースケジューリングシステムの一例を示す図。
【図１１】第２の実施形態に係るスケジューリング処理の一例を示す図。
【図１２】第３の実施形態に係るマルチワークフロースケジューリングシステムの一例を示す図。
【図１３】第３の実施形態に係るスケジューリング処理の一例を示す図。
【図１４】第４の実施形態に係る初段ワークフロースケジューリングタスクの処理の第１の例を示すフローチャート。
【図１５】第４の実施形態に係る終段ワークフロースケジューリングタスクの処理の第１の例を示すフローチャート。
【図１６】第４の実施形態に係る中段ワークフロースケジューリングタスクの処理の第１の例を示すフローチャート。
【図１７】第４の実施形態に係る初段ワークフロースケジューリングタスクの処理の第２の例を示すフローチャート。
【図１８】第４の実施形態に係る終段ワークフロースケジューリングタスクの処理の第２の例を示すフローチャート。
【図１９】第４の実施形態に係る中段ワークフロースケジューリングタスクの処理の第２の例を示すフローチャート。
【図２０】第５の実施形態に係る電子機器の一例を示すブロック図。
【図２１】第５の実施形態に係る電子機器に設けられるノードモジュール（ＮＭ）の構成を示すブロック図。
【発明を実施するための形態】
【０００８】
以下、図面を参照しながら各実施形態について説明する。以下の説明において、略又は実質的に同一の機能及び構成要素については、同一符号を付し、必要に応じて説明を行う。
【０００９】
［第１の実施形態］  
本実施形態においては、計算機システムの構成、及び、当該計算機システム上で動作するマルチワークフロースケジューリングシステムが実行するスケジューリング処理について説明する。
【００１０】
本実施形態において、計算機システムが処理するジョブの処理手順は、ワークフロー（ＷＦ：Work Flow）により表されるものとする。ワークフローとは、特定の初期入力ファイル集合を入力とし、特定の最終出力ファイル集合を出力するまでの一連の処理手順である。例えば、計算機システムが処理する１つのジョブは、１つのワークフローにより表される。ワークフローは、例えば、snakemakeプログラムなどを用いて実行される。Snakemakeについては、「Johannes Koester、“Welcome to Snakemake’s documentation!”、［online］、２０１６年、［平成３０年１月５日検索］、インターネット＜https://snakemake.readthedocs.io/en/stable/＞」などに開示されているため、ここではその詳しい説明については省略する。
【００１１】
また、本実施形態において、ワークフローに含まれる処理要素をタスクと呼ぶ。各タスクは、後述する計算ノード上で実行される。タスクは初期入力ファイルもしくは中間ファイルを入力され、又は、最終出力ファイルもしくは中間ファイルを出力する。
【００１２】
図１は、本実施形態に係る計算機システム１の一例を示すブロック図である。  
【００１３】
計算機システム１は、第１ノードＦＮと、共有ファイルシステムＳＦＳと、複数の計算ノードＣＮを含む。第１のノードＦＮ、共有ファイルシステムＳＦＳ及び複数の計算ノードＣＮは、それぞれ通信可能に接続されている。
【００１４】
第１ノードＦＮは、例えば計算機システム１全体の制御を行う電子機器である。また、第１ノードＦＮは、計算機システム１のユーザインタフェースを備える。例えば、ユーザは、第１ノードＦＮに対し計算機システム１に処理させたいワークフローを入力し、第１のノードＦＮを介して当該ワークフローに対する処理結果を得る。
【００１５】
第１ノードＦＮは、記憶装置２、ＣＰＵ（Central Processing Unit）３、主記憶装置としてのＲＡＭ（Random Access Memory）４を含む。記憶装置２、ＣＰＵ３、ＲＡＭ４は、それぞれ内部バスにより通信可能に接続されている。記憶装置２は、例えばハードディスク、ＳＳＤ（Solid State Drive）、フラッシュメモリなどにより記憶領域を構成する。また、記憶装置２は、プログラムＰＧを含む。第１ノードＦＮは、ＣＰＵ３が記憶装置２に格納されたプログラムＰＧを実行することにより、後述するマルチワークフロースケジューリングシステムとして動作する。
【００１６】
なお、本実施形態において、ＣＰＵ３は、ＭＰＵ（Micro Processing Unit）、ＤＳＰ（Digital Signal Processor）などの他のプロセッサでもよい。
【００１７】
共有ファイルシステムＳＦＳは、第１ノード及び複数の計算ノードＣＮが共有する記憶装置である。共有ファイルシステムＳＦＳは、各タスクの処理過程において必要な入力ファイル及び出力ファイルを格納する。
【００１８】
計算ノードＣＮは、例えば、ＣＰＵ５、ＲＡＭ６などのリソースを含む電子機器である。ＣＰＵ５は、例えば少なくとも１つ以上のコア７を含む。計算ノードＣＮは、プログラムＰＧの指示に基づき、計算ノードＣＮに含まれるリソースを用いてワークフローに対する処理を実行する。
【００１９】
１つの計算機システム１は、複数の計算ノードＣＮを含んでいてもよい。この場合、計算機システム１は、例えば計算機クラスターを構成する。
【００２０】
ここで、計算機クラスターとは、複数の計算ノードＣＮを結合し、ひとまとまりとしたシステムである。１つの計算機クラスターは、少なくとも１つ以上の論理ユニット（ＬＵ：Logical Unit）を有する。各論理ユニットＬＵは、少なくとも１つ以上の計算ノードＣＮを含む。
【００２１】
計算ノードＣＮが複数存在する場合、それぞれの計算ノードＣＮのＣＰＵ５に含まれるコア７の数は、計算ノードＣＮごとに異なってもよい。
【００２２】
なお、１つの電子機器は、複数の計算ノードＣＮを含んでいてもよい。１つの論理ユニットＬＵに含まれる計算ノードＣＮは、それぞれ異なる電子機器に含まれていてもよい。例えば、図１に示すように、異なる電子機器である２つの計算ノードＣＮを１つの論理ユニットＬＵとすることができる。また、１つの論理ユニットは、１つの電子機器の中に複数含まれてもよい。すなわち、１つの電子機器に含まれる複数の計算ノードＣＮにより、複数の論理ユニットＬＵが構成されてもよい。
【００２３】
また、上述の各装置は、例えば切替装置ＳＷに接続される。例えば、第１ノードＦＮは、切替装置ＳＷを操作して計算機システム１に含まれる電子機器間の接続を切り替えることで、任意の電子機器間における通信を可能にする。
【００２４】
第１ノードＦＮにワークフローが入力されると、プログラムＰＧは、当該ワークフローに含まれる各タスクを少なくとも１つ以上の計算ノードＣＮのコア７に割り当てる。計算ノードＣＮは、割り当てられたタスクを処理する。当該ワークフローに含まれるタスクが全て処理されると、当該ワークフローの処理結果が得られる。
【００２５】
なお、本実施形態において、あるタスクに対して特定の計算ノード上のリソースを割当てる処理をタスクスケジューリングと呼ぶ。
【００２６】
図２は、本実施形態に係るＷＦＤＡＧ（Work Flow Directed Acyclic Graph）の一例を示す図である。
【００２７】
ＷＦＤＡＧは、ワークフローの処理要素であるタスクを頂点とし、タスク間の入出力ファイルによる依存関係を辺とする有向非巡回グラフである。ＷＦＤＡＧの各頂点（すなわち、各タスク）は、ＷＦＤＡＧ内で固有の識別子を持つ。ＷＦＤＡＧの任意の２つの頂点（頂点ａ及び頂点ｂ）について、頂点ａから頂点ｂへの経路、又は、頂点ｂから頂点ａへの経路が存在しない場合に、頂点ａのタスクと頂点ｂのタスクは並列して（すなわち、同時に）実行可能である。
【００２８】
ＷＦＤＡＧは、部分グラフである部分ＤＡＧ（Sub Directed Acyclic Graph）を含む。部分ＤＡＧが２つ以上の頂点を含む場合、部分ＤＡＧの任意の２つの頂点（頂点ａ及び頂点ｂ）は、部分ＤＡＧ内で頂点ａから頂点ｂもしくは頂点ｂから頂点ａへの経路が存在するか、又は、部分ＤＡＧ及びＷＦＤＡＧ内で頂点ａから頂点ｂもしくは頂点ｂから頂点ａの経路が存在しないかのいずれかとなる。
【００２９】
例えば、図２の例において、ワークフローＷＦ１は、タスク名「Ｔ１」のタスクｔ１１、タスク名「Ｔ２」のタスクｔ２１、タスク名「Ｔ３」のタスクｔ３１、及び、タスク名「Ｔ４」のタスクｔ４１を含む。同様に、ワークフローＷＦ２は、タスク名「Ｔ１」のタスクｔ１２、タスク名「Ｔ２」のタスクｔ２２、タスク名「Ｔ３」のタスクｔ３２、及び、タスク名「Ｔ４」のタスクｔ４２を含む。タスクｔ１１及びタスクｔ１２、タスクｔ２１及びタスクｔ２２、タスクｔ３１及びタスクｔ３２、タスクｔ４１及びタスクｔ４２は同じタスクである。ワークフローＷＦ１において、タスクｔ１１、タスクｔ２１とタスクｔ３１、タスクｔ４１は、それぞれワークフローＷＦ１を示すＷＦＤＡＧの部分ＤＡＧである。同様に、ワークフローＷＦ２において、タスクｔ１２、タスクｔ２２とタスクｔ３２、タスクｔ４２は、それぞれワークフローＷＦ２を示すＷＦＤＡＧの部分ＤＡＧである。
【００３０】
本実施形態において、ワークフローに含まれる各タスクは、例えば以下の４つの状態「実行可能待ち状態」、「実行可能状態」、「実行中状態」及び「実行終了状態」をとる。実行可能待ち状態は、タスクの実行に必要な入力ファイルが揃っていない状態である。実行可能状態は、タスクの実行に必要な入力ファイルが全て揃っており、かつ、タスクが実行中状態及び実行終了状態でない状態である。すなわち、実行可能状態は、実行直前の状態である。実行中状態は、タスクが実行中である状態を示す。実行終了状態は、タスクの実行が終了した状態を示す。
【００３１】
図３は、本実施形態に係るタスクグループ定義表の一例を示す図である。  
【００３２】
本実施形態において、部分ＤＡＧに含まれるタスクの集合をタスクグループ（ＴＧ：Task Group）と呼ぶ。異なるワークフローに属する同じタスクは、同一タスクグループに属することができる。
【００３３】
タスクグループ定義表は、タスクとタスクグループとを関連付けるデータである。図３は、図２のワークフローＷＦ１，ＷＦ２に含まれるタスクグループの例を示している。計算機システム１は、タスクグループ定義表を、例えば共有ファイルシステムＳＦＳ又はＲＡＭ４などに格納する。
【００３４】
図２の例において、ワークフローＷＦ１の部分ＤＡＧに含まれるタスクｔ１１と、ワークフローＷＦ２の部分ＤＡＧに含まれるタスクｔ１２は、タスク名「Ｔ１」の同じタスクであるため、同じタスクグループに含まれることができる。すなわち、タスクグループＴＧ１は、タスク名「Ｔ１」のタスクを含む。同様に、タスクグループＴＧ２は、タスク名「Ｔ２」及び「Ｔ３」のタスクを含む。同様に、タスクグループＴＧ４は、タスク名「Ｔ４」のタスクを含む。
【００３５】
なお、図２に示すワークフローＷＦ１，ＷＦ２において、以下のように別のタスクグループが定義されてもよい。例えば、ワークフローＷＦ１の第１の部分ＤＡＧはタスクｔ１を含むとし、第２の部分ＤＡＧはタスクｔ２１，ｔ３１，ｔ４１を含むとする。同様に、ワークフローＷＦ２の第１の部分ＤＡＧはタスクｔ１２を含むとし、第２の部分ＤＡＧはタスクｔ２２，ｔ３２，ｔ４２を含むとする。この場合、ワークフローＷＦ１及びワークフローＷＦ２双方において、タスク名「Ｔ２」，「Ｔ３」及び「Ｔ４」により構成される部分ＤＡＧが存在するため、当該部分ＤＡＧを同じタスクグループとすることができる。すなわち、この例においては、タスクグループＴＧ１は、タスク名「Ｔ１」のタスクを含み、タスクグループＴＧ２は、タスク名「Ｔ２」，「Ｔ３」及び「Ｔ４」のタスクを含む。
【００３６】
以下では、マルチワークフロータスクスケジューリングについて説明する。マルチワークフロータスクスケジューリングとは、例えばＰ個（Ｐは複数）のワークフローを処理する際、各ワークフローに含まれる各タスクに対し、計算機システム（すなわち、計算機クラスター）内の所定の計算ノードＣＮのリソースを割当て、各タスクを所定の順番で実行すること、又は、当該実行計画を生成することを指す。
【００３７】
ところで、一般的に計算機システムの性能は、上述のようにスループット及び処理完了時間により表される。本実施形態では、計算機システム１において、所定時間あたりに処理完了するワークフローの数（以下、定常処理スループットと呼ぶ）及び全てのワークフローの処理が完了するまでの時間（以下、全処理完了時間と呼ぶ）が、それぞれ以下で説明する所定の条件を満たす。
【００３８】
ここで、１つの論理ユニットＬＵを用いてワークフローの全タスクを処理するのにかかる最大時間をＴ＿ｓｕｍとする。Ｔ＿ｓｕｍは、１つの論理ユニットＬＵを用いてタスクグループｉに属する全タスクを処理するのにかかる時間Ｔ（ｉ）、及び、タスクグループの総数Ｇを用いて、下記の式（１）により表される。なお、式（１）においては、タスクグループごとに割り当てられるリソースは、互いに重複しないものとする。
【００３９】
【数１】
2019121240.tif 000003
【００４０】
計算機システム１に含まれる論理ユニットＬＵの数がＮ＿ｌｕである場合、本実施形態に係る計算機システム１の定常処理スループットは、例えば、下記の式（２）で示される１つのタスクグループの処理時間の最大値Ｔ＿ｍａｘを用いて、Ｔ＿ｍａｘ時間あたりＮ＿ｌｕ個以上となる。
【００４１】
【数２】
2019121240.tif 000004
【００４２】
。
【００４３】
また、ワークフローの数Ｐ、論理ユニットＬＵの数Ｎ＿ｌｕ、１つのタスクグループの処理時間の最大値Ｔ＿ｍａｘ、及び、ワークフローの全タスクを処理するのにかかる最大時間Ｔ＿ｓｕｍを用いて、本実施形態に係る計算機システム１の全処理完了時間は、例えば、下記の式（３）で示される値以下となる。換言すれば、本実施形態における全処理完了時間の目標性能は、式（３）で示される値である。
【００４４】
【数３】
2019121240.tif 000005
【００４５】
式（３）は、ワークフローの処理結果が最初に出力されるまでの時間がＴ＿ｓｕｍであり、その後は、論理ユニットＬＵの数Ｎ＿ｌｕに基づいて算出される所定の時間ごとにワークフローの処理結果が得られることを示している。
【００４６】
以下では、一般的なマルチワークフロータスクスケジューリングの第１乃至第３の例について説明する。
【００４７】
マルチワークフロータスクスケジューリングの第１の例においては、複数のワークフローは、計算機システムにより区別されずに処理される（以下、この方式をフラットスケジューリングと呼ぶ）。フラットスケジューリングにおいては、任意の時点でワークフローの数Ｐ個のワークフローを同時に処理する。この結果、全てのワークフローの処理結果が同時に得られるものの、定常処理スループットを満たさない。
【００４８】
より具体的には、例えば、ワークフローの数Ｐ＝４、論理ユニットＬＵの数Ｎ＿ｌｕ＝１、１つのタスクグループの処理時間の最大値Ｔ＿ｍａｘ＝Ｔ時間、タスクグループの総数Ｇ＝３とする。各ワークフローに含まれるタスクの種類及びタスクグループの定義は、図２及び図３で説明したものと同様である。また、１つの論理ユニットＬＵは、２つの計算ノードを含み、１つの計算ノードは２つのコア７を含むとする。各タスクが１つのコア７を用いて処理時間Ｔで処理されるとすると、フラットスケジューリングにおける全処理完了時間は４Ｔであり、４Ｔ経過時点で全てのワークフローの処理結果をが得られる。
【００４９】
ここで、式（３）を用いて計算される全処理完了時間は６Ｔである。したがって、フラットスケジューリングの全処理完了時間は、式（３）の値以下となり、全処理完了時間の目標性能を満たす。一方、定常処理スループットは１ワークフロー／Ｔ時間となる。上述のフラットスケジューリングでは、４Ｔ経過時点までワークフローの処理結果は出力されないため、定常処理スループットの目標性能を満たさない。
【００５０】
マルチワークフロータスクスケジューリングの第２の例においては、上述のフラットスケジューリングを制御するタスクスケジューラに対し、１つのタスクグループの処理時間の最大値Ｔ＿ｍａｘの間に入力するワークフローの数が論理ユニットＬＵの数Ｎ＿ｌｕ個以下となるように制御する。しかしながら、この第２の例においては、集中制御が必要となるため、例えばネットワークを経由して複数のシステム上に分散したタスクスケジューラ（以下、分散タスクスケジューラと呼ぶ）への適用が難しい。また、種類の異なるワークフローが混在する場合、１つのタスクグループの処理時間の最大値Ｔ＿ｍａｘは、処理量の大きいワークフローに依存するため、処理量の小さいワークフローの割合が高い場合にシステムの利用率が下がってしまう。
【００５１】
マルチワークフロータスクスケジューリングの第３の例においては、タスクスケジューラは、各タスクのワークフロー定義（ＷＦＤＡＧ）を用いて、タスクごとの優先度をリアルタイムに計算し、実行可能なタスクの中からランクの高い順にリソースを割当てる（非特許文献１参照）。しかしながら、この第３の例においては、タスクスケジューラの計算量がワークフロー数及びワークフロー定義に依存してしまう。
【００５２】
そこで、本実施形態においては、以下のようにワークフロースケジューラとタスクスケジューラを用いることにより、２段階のマルチワークフロータスクスケジューリングを行う。
【００５３】
第１の段階において、ワークフロースケジューラは、タスクグループごとに、実行中状態であるタスクを含むワークフローの種類数が論理ユニットＬＵの数Ｎ＿ｌｕ以下となるように制御する。この制御のために、計算機システム１は、タスクグループ毎にセマフォを定義する。
【００５４】
ここで、各セマフォは、例えば、同時に実行可能なワークフローの数を示すセマフォ変数と、処理待ちのワークフローを管理するセマフォキューとを含む。各セマフォカウンタの初期値は、論理ユニットＬＵの数Ｎ＿ｌｕである。
【００５５】
ワークフロースケジューラは、あるワークフローに含まれるタスクグループが実行可能状態になったとき、当該タスクグループのセマフォに対してＰ命令を発行する。当該Ｐ命令を受信したセマフォは、セマフォ変数を１つ減らす。ワークフロースケジューラは、当該タスクグループの実行可能タスクをタスクスケジューラに送信する。
【００５６】
ワークフロースケジューラは、あるワークフローに含まれるタスクグループが実行終了状態になったとき、当該タスクグループのセマフォに対してＶ命令を発行する。当該Ｖ命令を受信したセマフォは、セマフォ変数を１つ増やす。
【００５７】
なお、セマフォ変数が負となる場合、セマフォキューには処理待ちのワークフローが存在することを表す。
【００５８】
本実施形態においては、セマフォキューの代わりに、ワークフローの優先度別にＦＩＦＯ（First In First Out）が設けられてもよい。この場合、計算機システム１は、当該優先度に基づいてデキューするＦＩＦＯを選択してもよい。
【００５９】
第２の段階において、タスクスケジューラは、ワークフロースケジューラより受信した実行可能タスクに対し、所定のリソースを割当てることにより当該タスクを実行する。なお、各タスクグループに対して割り当てられるリソースは、互いに重複しないものとする。
【００６０】
また、論理ユニットの数Ｎ＿ｌｕ＝１の場合は、上述のセマフォに代えてミューテックスを使用可能である。セマフォとミューテックスの使用例の詳細については、第４の実施形態において後述する。
【００６１】
本実施形態において、計算機システム１は、ワークフロースケジューラ及びタスクスケジューラを用いたマルチワークフロータスクスケジューリングにより、Ｔ＿ｍａｘ時間あたりＮ＿ｌｕ個以上の定常スループット、及び、式（３）で示される値以下の全処理完了時間を得る。また、本実施形態に係るマルチワークフロータスクスケジューリングにおいては、計算量がワークフロー数及びワークフロー定義に依存しない。また、種類の異なるワークフローが含まれる場合でもリソース利用率が低下しない。さらに、分散タスクスケジューラにも適用可能である。
【００６２】
図４は、本実施形態に係るマルチワークフロースケジューリングシステムの一例を示す図である。本実施形態において、当該マルチワークフロースケジューリングシステムは、例えばプログラムＰＧにより実現される。
【００６３】
マルチワークフロースケジューリングシステムは、ワークフローマネージャＷＦＭ（Work Flow Manager）、ワークフロースケジューラＷＦＳ（Work Flow Scheduler）、タスクスケジューラＴＳ（Task Scheduler）、リソースマネージャＲＭ（Resource Manager）、計算ノードＣＮを含む。
【００６４】
ワークフローマネージャＷＦＭは、ＷＦＤＡＧ情報に基づき、各ワークフローに含まれるタスクのタスク状態を管理する。ワークフローマネージャＷＦＭは、ワークフロースケジューラＷＦＳに対して各ワークフローの各実行可能タスクに関する情報を含むタスク実行要求Ｒ１を送信する。
【００６５】
タスク実行要求Ｒ１は、例えば、ワークフロースケジューラＷＦＳ内でタスクを一意に識別可能なタスク識別子、ワークフロー内でタスクを一意に識別可能なタスク名、タスク実行時に計算ノードＣＮ上で実行されるスクリプトなどを含む。
【００６６】
なお、タスク実行要求Ｒ１は、リソース要求量を指定可能であってもよい。タスク実行要求Ｒ１の送信先がリソース要求指定表にアクセス可能な場合には、当該リソース要求量の指定は省略可能である。ここで、リソース要求指定表は、タスク名ごとに当該タスクの処理に用いるリソース要求量を指定したデータである。例えば、リソース要求量がＣＰＵコア数で表される場合、リソース要求指定表には、タスク名とＣＰＵコア数とが関連付けられる。リソース要求量は、例えば、最小ＣＰＵコア数、最大ＣＰＵコア数、最小メモリ量（単位：ＭＢ）、最大メモリ量（単位：ＭＢ）、最小Ｉ／Ｏリード速度（単位：ＭＢｐｓ）、最大Ｉ／Ｏリード速度（単位：ＭＢｐｓ）、最小Ｉ／Ｏライト速度（単位：ＭＢｐｓ）、最大Ｉ／Ｏライト速度（単位：ＭＢｐｓ）などのうち少なくとも１つ以上の項目を含む。計算機システム１は、リソース要求指定表を、例えば共有ファイルシステムＳＦＳ又はＲＡＭ４などに格納する。
【００６７】
ワークフローマネージャＷＦＭは、例えば上述のsnakemakeプログラムにより実装される。また、１つのマルチワークフロースケジューリングシステム内には、複数のワークフローマネージャＷＦＭが存在してもよい。
【００６８】
ワークフロースケジューラＷＦＳは、上述のように、例えばタスクグループ毎にセマフォ又はミューテックスを用いたワークフロースケジューリングを実行する。ワークフロースケジューラＷＦＳは、ワークフローマネージャＷＦＭより受信したタスク実行要求Ｒ１で指定されたタスクの中から実行するタスク（以下、実行タスクと呼ぶ）を選択する。ワークフロースケジューラＷＦＳは、タスクスケジューラＴＳに対して実行タスクに対するタスク実行要求Ｒ２を送信する。
【００６９】
ワークフロースケジューラＷＦＳは、例えば上述のsnakemakeプログラムのclusterオプションで指定されるクラスターコマンドである。また、１つのマルチワークフロースケジューリングシステム内には、複数のワークフロースケジューラＷＦＳが存在してもよい。また、例えば、各ワークフロースケジューラＷＦＳは、複数のワークフローマネージャＷＦＭからのタスク実行要求Ｒ１を受信してもよい。
【００７０】
なお、ワークフロースケジューラＷＦＳは、複数のＯＳ（Operating System）上に存在してもよい。換言すれば、ワークフロースケジューラＷＦＳは、分散システム上で動作可能である。この場合、各ワークフロースケジューラＷＦＳは、分散ロックマネージャ（ＤＬＭ：Distributed Lock Manager）の機能をさらに備えてもよい。この分散ロックマネージャは、分散システムにおいて分散セマフォ及び分散ミューテックスとして機能する。すなわち、分散ロックマネージャは、各ワークフロースケジューラＷＦＳが管理する各セマフォ及びミューテックスの代わりとなる。
【００７１】
タスクスケジューラＴＳは、リソースマネージャＲＭから利用可能リソース情報Ｒ５を受信する。利用可能リソース情報Ｒ５は、各計算ノードＣＮで現在利用可能なリソースの総和を示す情報である。
【００７２】
タスクスケジューラＴＳは、ワークフロースケジューラＷＦＳからタスク実行要求Ｒ２を受信すると、タスク実行要求Ｒ２で指定されたタスクに対し、利用可能リソース情報Ｒ５を参照して、当該タスクが所属するタスクグループＴＧのリソースプールＲＰ（Resource Pool）から所定の計算ノードＣＮに所定のリソースを割当てる。また、タスクスケジューラＴＳは、リソースマネージャＲＭに対しタスク実行依頼Ｒ３を送信する。
【００７３】
リソースプールＲＰは、計算ノードＣＮ及びリソースを２項組とする集合である。リソースプールＲＰの詳細については、図５を用いて後述する。
【００７４】
タスク実行依頼Ｒ３は、例えば、タスクスケジューラＴＳ内でタスクを一意に識別可能なタスク識別子、ワークフロー内でタスクを一意に識別可能なタスク名、タスク実行時に計算ノードＣＮ上で実行されるスクリプト、タスクスケジューラＴＳがタスクに割当てたリソースを示す割当リソース情報などを含む。
【００７５】
なお、１つのマルチワークフロースケジューリングシステム内には、複数のタスクスケジューラＴＳが存在してもよい。各タスクスケジューラＴＳは複数のワークフロースケジューラＷＦＳからタスク実行要求Ｒ２を受信してもよい。
【００７６】
タスクスケジューラＴＳは、例えば、Ｍｅｓｏｓ対応スケジューラ（Ｆｅｎｚｏスケジューラ）などである。Ｆｅｎｚｏスケジューラについては、「GitHub,Inc.、“Home Netflix/Fenzo Wiki”、［online］、２０１６年１０月１４日、［平成３０年１月５日検索］、インターネット＜https://github.com/Netflix/Fenzo/wiki＞」などに開示されているため、ここではその詳しい説明については省略する。
【００７７】
リソースマネージャＲＭは、タスクスケジューラＴＳからタスクに対するタスク実行依頼Ｒ３を受信すると、当該タスク実行依頼Ｒ３に含まれる割当リソース情報に基づき、リソース割当て状態を更新する。
【００７８】
リソースマネージャＲＭは、当該タスク実行依頼Ｒ３に含まれる割当リソース情報で指定された計算ノードＣＮに対してタスク実行指示Ｒ４を送信する。
【００７９】
タスク実行指示Ｒ４は、例えば、リソースマネージャＲＭ内でタスクを一意に識別可能なタスク識別子、ワークフロー内でタスクを一意に識別可能なタスク名、タスク実行時に計算ノードＣＮ上で実行されるスクリプト、割当リソース情報などを含む。
【００８０】
リソースマネージャＲＭは、各計算ノードＣＮからリソース総量情報Ｒ６又はタスク実行完了通知Ｒ７を受信すると、リソース割当て状態を更新する。また、リソースマネージャＲＭは、利用可能リソース情報Ｒ５をタスクスケジューラＴＳに送信する。
【００８１】
リソース総量情報Ｒ６は、計算ノードＣＮが持つ最大使用可能リソース量を示す情報である。
【００８２】
タスク実行完了通知Ｒ７は、例えば、リソースマネージャＲＭ内でタスクを一意に識別可能なタスク識別子、タスクの実行結果などを含む。タスクの実行結果は、例えば、「成功」「失敗」「中止」などである。
【００８３】
リソースマネージャＲＭは、例えば、Mesos Masterプログラムなどである。Mesos Masterプログラムについては、「The Apache Software Foundation、“Apache Mesos - Architecture”、［online］、２０１７年、［平成３０年１月５日検索］、インターネット＜http://mesos.apache.org/documentation/latest/architecture/＞」などに開示されているため、ここではその詳しい説明については省略する。
【００８４】
計算ノードＣＮは、図１を用いて上述したように、ＣＰＵモジュール及びメモリモジュールを備える。計算ノードＣＮは、リソース総量情報Ｒ６をリソースマネージャＲＭに送信する。
【００８５】
計算ノードＣＮは、リソースマネージャＲＭからタスク実行指示Ｒ４を受信すると、タスク実行指示Ｒ４で指定されたタスクを、タスク実行指示Ｒ４で指定されたリソースを使用して実行する。なお、当該タスクの実行が行われる計算ノードＣＮは、タスク実行指示Ｒ４で指定される。
【００８６】
計算ノードＣＮは、当該タスクの実行が終了すると、リソースマネージャＲＭに対してタスク実行完了通知Ｒ７を送信する。
【００８７】
なお、計算ノードＣＮは複数あってもよい。複数の計算ノードＣＮは、計算機クラスターを構成する。また、タスク実行はDockerコンテナ上で行ってもよい。Dockerコンテナについては、「Docker Inc.、“Docker - Build, Ship, and Run Any App, Anywhere”、［online］、２０１７年、［平成３０年１月５日検索］、インターネット＜https://www.docker.com/＞」などに開示されているため、ここではその詳しい説明については省略する。
【００８８】
図４の例において、プログラムＰＧは、例えばワークフローマネージャＷＦＭ、ワークフロースケジューラＷＦＳ、タスクスケジューラＴＳ、リソースマネージャＲＭを含む。プログラムＰＧは、計算ノードＣＮ上で動作してもよい。すなわち、計算ノードＣＮのＣＰＵ７は、プログラムＰＧを実行することにより、マルチワークフロースケジューリングシステムとして動作してもよい。
【００８９】
図５は、本実施形態に係るリソースプールの一例を示す図である。より具体的には、図５は、図２及び図３で説明したようにタスクグループが定義される場合における、各タスクグループのリソースプールを示している。
【００９０】
例えば、リソースがＣＰＵコア数である場合、リソースプールは、“｛（論理ユニット番号.計算ノード番号, ＣＰＵコア数）｝”と表される。“論理ユニット番号.計算ノード番号”を計算ノードＩＤと呼ぶ。図５の例では、タスクグループＴＧ１及びＴＧ３のリソースプールは、“{(1.1, 1)}”である。これは、論理ユニット番号「１」の論理ユニットＬＵの計算ノードｃｎ１のコアを１つ使用することを表している。同様に、タスクグループＴＧ２のリソースプールは、“{(1.2, 2)}”である。これは、論理ユニット番号「１」の論理ユニットＬＵの計算ノードｃｎ２のコアを２つ使用することを表している。
【００９１】
本実施形態に係るマルチワークフロースケジューリングシステムにおいては、各タスクグループに対して排他的にリソースプールを割り当てることが好ましい。
【００９２】
図６は、本実施形態に係るスケジューリング処理の一例を示す図である。
【００９３】
計算ノードＣＮは、リソースマネージャＲＭに対してリソース総量情報Ｒ６を送信する（ステップＳ１０１）。リソースマネージャＲＭは、受信したリソース総量情報Ｒ６に基づいてリソース割当て状態を更新し、現在の利用可能リソース情報Ｒ５をタスクスケジューラＴＳへ送信する（ステップＳ１０２）。
【００９４】
ワークフローマネージャＷＦＭは、ワークフロースケジューラＷＦＳに対して実行可能なタスクの情報を含むタスク実行要求Ｒ１を送信する（ステップＳ１０３）。
【００９５】
ワークフロースケジューラＷＦＳは、タスク実行要求Ｒ１に含まれるタスク識別子（又はタスク名）の中から、実行タスクを選択する（ステップＳ１０４）。ワークフロースケジューラＷＦＳは、タスクスケジューラＴＳに対して実行タスクの情報を含むタスク実行要求Ｒ２を送信する（ステップＳ１０５）。
【００９６】
タスクスケジューラＴＳは、タスク実行要求Ｒ２に含まれる実行タスクに対し、利用可能リソース情報Ｒ５に基づいて利用可能リソースを割り当てる（ステップＳ１０６）。タスクスケジューラＴＳは、リソースマネージャＲＭに対して割当リソース情報を含むタスク実行依頼Ｒ３を送信する（ステップＳ１０７）。
【００９７】
リソースマネージャＲＭは、タスク実行依頼Ｒ３に含まれる割当リソース情報に基づき、リソース割り当て状態を更新する（ステップＳ１０８）。リソースマネージャＲＭは、受信した割当リソース情報及び／又は自身が管理するリソース割り当て状態に基づき、タスクスケジューラＴＳに対して利用可能リソース情報Ｒ５を送信する（ステップＳ１０９）。また、リソースマネージャＲＭは、割当リソース情報で指定された計算ノードＣＮに対してタスク実行指示Ｒ４を送信する（ステップＳ１１０）。
【００９８】
計算ノードＣＮは、受信したタスク実行指示Ｒ４に基づき、タスクを実行する（ステップＳ１１１）。計算ノードＣＮは、タスク実行完了後に、リソースマネージャＲＭに対してタスク実行完了通知Ｒ７を送信する（ステップＳ１１２）。
【００９９】
リソースマネージャＲＭは、受信したタスク実行完了通知Ｒ７に基づいて、リソース割り当て状態を更新する（ステップＳ１１３）。リソースマネージャＲＭは、更新したリソース割り当て状態に基づき、タスクスケジューラＴＳに対して利用可能リソース情報Ｒ５を送信する（ステップＳ１１４）。
【０１００】
なお、ステップＳ１０１，Ｓ１０２の処理は、ステップ１０３の前に行われなくてもよいが、ステップＳ１０６の処理の前に行われることが好ましい。ステップＳ１０１，Ｓ１０２の処理は、ステップＳ１０３〜Ｓ１０５の処理と非同期に行われてもよい。
【０１０１】
図７は、本実施形態に係るスケジューリング結果の第１の例を示す図である。より具体的には、図７は、上述の２段階のマルチワークフロースケジューリングシステムを用いてタスクスケジューリングを行った結果を示す。
【０１０２】
ワークフロースケジューリング結果Ｗ１は、タスクグループごと、及び、時間帯ごとに処理対象となったワークフローを示している。タスクスケジューリング結果Ｘ１は、ワークフローごとに各時間帯において処理されたタスクＩＤと、処理に用いた計算ノードＩＤ及びリソース数（ここではＣＰＵのコア数）を示す。ここで、タスク名「Ｔ１」のタスクＩＤはｔ１、タスク名「Ｔ２」のタスクＩＤはｔ２、タスク名「Ｔ３」のタスクＩＤはｔ３、タスク名「Ｔ４」のタスクＩＤはｔ４である。処理完了ワークフローＹ１は、各時間帯終了時に計算完了したワークフローを示す。
【０１０３】
処理結果Ｚ１１〜Ｚ１６は、処理時間帯を０〜６Ｔとしたときの、時間Ｔ経過ごとのワークフロースケジューリング結果Ｗ１、タスクスケジューリング結果Ｘ１及び処理完了ワークフローＹ１を指す。
【０１０４】
図７においては、例えば、ワークフローの数Ｐ＝４、論理ユニットＬＵの数Ｎ＿ｌｕ＝１、１つのタスクグループの処理時間の最大値Ｔ＿ｍａｘ＝Ｔ時間、タスクグループの総数Ｇ＝３とする。各ワークフローに含まれるタスクの種類、タスクグループの定義、リソースプールは、図２、図３及び図５で説明したものと同様である。また、１つの論理ユニットＬＵは、２つの計算ノードを含み、１つの計算ノードは２つのコア７を含むとし、各タスクのリソース要求量は１（すなわち、１つのタスクの処理に１個のＣＰＵコアが必要）であるとする。
【０１０５】
ワークフロースケジューラＷＦＳは、任意の時点で各タスクグループＴＧにおいてＮ＿ｌｕ個（すなわち、１個）のワークフローが処理されるように制御する。各時間帯のワークフロースケジューリング結果Ｗ１によれば、タスクグループＴＧ１〜ＴＧ３で処理されるワークフローの数は１個となっている。
【０１０６】
より具体的には、処理結果Ｚ１１では、まずワークフロー「１」かつタスクグループＴＧ１のタスクＩＤ ｔ１のタスクに対して、計算ノードＩＤ (1.1)のＣＰＵコア７が１つ割り当てられる。すると、他のワークフローにおいては、タスクグループＴＧ１のタスクを処理できないため、他のリソースは未使用状態となる。
【０１０７】
次に、処理結果Ｚ１２では、ワークフロー「１」かつタスクグループＴＧ２のタスクＩＤ ｔ２，ｔ３のタスクに対して、計算ノードＩＤ (1.2)のＣＰＵコア７が１つずつ割り当てられる。他のワークフローのうち１つのワークフローにおいて、タスクグループＴＧ１のタスクを処理可能であるため、例えば、ワークフロー「２」かつタスクグループＴＧ１のタスクＩＤ ｔ１のタスクに対して、計算ノードＩＤ (1.1)のＣＰＵコア７が１つ割り当てられる。
【０１０８】
さらに、処理結果Ｚ１３では、ワークフロー「１」かつタスクグループＴＧ３のタスクＩＤ ｔ４のタスクに対して、計算ノードＩＤ (1.1)のＣＰＵコア７が１つ割り当てられる。他のワークフローのうち１つのワークフローにおいて、タスクグループＴＧ１のタスクを処理可能であるため、例えば、ワークフロー「３」かつタスクグループＴＧ１のタスクＩＤ ｔ１のタスクに対して、計算ノードＩＤ (1.1)のＣＰＵコア７が１つ割り当てられる。また、他のワークフローのうち１つのワークフローにおいて、タスクグループＴＧ２のタスクを処理可能であるため、例えば、ワークフロー「２」かつタスクグループＴＧ２のタスクＩＤ ｔ２，ｔ３のタスクに対して、計算ノードＩＤ (1.2)のＣＰＵコア７が１つずつ割り当てられる。
【０１０９】
処理結果Ｚ１３においては、ワークフロー「１」の処理が完了したため、処理完了ＷＦとして出力されている。同様に、処理結果Ｚ１４〜Ｚ１５において、ワークフロー「１」〜「４」の処理結果が、時間Ｔを経過するごとに１つずつ出力され、処理時間６Ｔで全てのワークフローの処理が完了している。すなわち、定常スループットは「１ワークフロー／Ｔ時間」であり、全処理時間は６Ｔ時間となっている。
【０１１０】
ここで、式（３）を用いて計算される全処理完了時間は６Ｔである。また、式（２）を用いて計算されるＴ＿ｍａｘ時間あたりの定常処理スループットは１ワークフロー／Ｔ時間となる。したがって、当該処理結果は、全処理完了時間及び定常処理スループット両方の目標性能を満たす。
【０１１１】
図８は、本実施形態に係るスケジューリング結果の第２の例を示す図である。より具体的には、図８は、図７の例で論理ユニットＬＵの数Ｎ＿ｌｕ＝２とした場合の、タスクスケジューリング結果を示す。
【０１１２】
図８においては、図７と同様に、時間帯ごとのワークフロースケジューリング結果Ｗ２、タスクスケジューリング結果Ｘ２、処理完了ワークフローＹ２を示す。また、処理結果Ｚ２１〜Ｚ２４は、処理時間帯を０〜４Ｔとしたときの、時間Ｔ経過ごとのワークフロースケジューリング結果Ｗ２、タスクスケジューリング結果Ｘ２及び処理完了ワークフローＹ２を指す。
【０１１３】
図８の例では、各ワークフローに含まれるタスクの種類、タスクグループの定義、ワークフローの数Ｐ、１つのタスクグループの処理時間の最大値Ｔ＿ｍａｘ、タスクグループの総数Ｇ、各タスクのリソース要求量、各論理ユニットＬＵの構成は、図７の例と同様である。また、タスクグループＴＧ１に割り当てられるリソースプールは、“{(1.1, 1), (2.1 ,1)}”であり、タスクグループＴＧ２に割り当てられるリソースプールは、“{(1.2, 2), (2.2 ,2)}”であり、タスクグループＴＧ３に割り当てられるリソースプールは、“{(1.1, 1), (2.1 ,1)}”であるとする。
【０１１４】
ワークフロースケジューラＷＦＳは、任意の時点で各タスクグループＴＧにおいてＮ＿ｌｕ個（すなわち、２個）のワークフローが処理されるように制御する。各時間帯のワークフロースケジューリング結果Ｗ２によれば、タスクグループＴＧ１〜ＴＧ３で処理されるワークフローの数は２個となっている。図８の例では、図７の例に比べて一度に処理できるワークフローの数が増加している。したがって、図７の例に比べて全処理完了時間は減少し、定常処理スループットは増加する。
【０１１５】
処理結果Ｚ２３においては、ワークフロー「１，２」の処理が完了したため、処理完了ＷＦとして出力されている。同様に、処理結果Ｚ２４において、ワークフロー「３，４」の処理結果が出力され、処理時間４Ｔで全てのワークフローの処理が完了している。すなわち、定常スループットは「２ワークフロー／Ｔ時間」であり、全処理時間は４Ｔ時間となっている。
【０１１６】
ここで、式（３）を用いて計算される全処理完了時間は４Ｔである。また、式（２）を用いて計算されるＴ＿ｍａｘ時間あたりの定常処理スループットは２ワークフロー／Ｔ時間となる。したがって、当該処理結果は、全処理完了時間及び定常処理スループット両方の目標性能を満たす。
【０１１７】
［第２の実施形態］
本実施形態においては、上記第１の実施形態の変形例について説明する。本実施形態では、第１の実施形態で定義したＷＦＤＡＧの拡大グラフである拡大ＷＦＤＡＧ（Super WFDAG）について説明する。
【０１１８】
拡大ＷＦＤＡＧにおいては、第１の実施形態で説明した処理要素であるタスク（以下、通常タスクと呼ぶ）に加え、ワークフロースケジューリングを実行するためのタスク（以下、ワークフロースケジューリングタスクと呼ぶ）が用いられる。通常タスクは、ワークフロースケジューリングタスクにより実行タイミングが制御される。
【０１１９】
図９は、図２のワークフローＷＦ１，２それぞれに対しワークフロースケジューリングタスクを加えた拡大ＷＦＤＡＧの例を示す。
【０１２０】
ワークフロースケジューリングタスクは、各タスクグループの入口及び出口に配置される。タスクグループの入口に配置されるワークフロースケジューリングタスクは、当該タスクグループのセマフォに対してＰ命令を実行する。また、タスクグループの出口に配置されるワークフロースケジューリングタスクは、当該タスクグループのセマフォに対してＶ命令を実行する。
【０１２１】
なお、前のタスクグループの出口のワークフロースケジューリングタスクと次のタスクグループの入り口のワークフロースケジューリングタスクは隣接するため、これらは１つのノードに縮約されてもよい（以下、縮約ワークフロースケジューリングタスクと呼ぶ）。縮約ワークフロースケジューリングタスクは、前段タスクグループＴＧのセマフォに対してＶ命令実行し、後段タスクグループＴＧのセマフォに対してＰ命令を実行する。
【０１２２】
図９に示すように、ワークフローごとに、以下の３種類のワークフロースケジューリングタスクが存在する。例えば、ワークフローＷＦ１の入口には初段ワークフロースケジューリングタスクｔｗｆ１０が配置され、ワークフローＷＦ１の出口には終段ワークフロースケジューリングタスクｔｗｆ１３が配置される。また、各タスクグループ間には中段ワークフロースケジューリングタスクｔｗｆ１１，ｔｗｆ１２が配置される。各中段ワークフロースケジューリングタスクは、例えば縮約ワークフロースケジューリングタスクである。
【０１２３】
拡大ＷＦＤＡＧで記述される複数のワークフローが存在する場合、同じタスク名を持つワークフロースケジューリングタスクは、セマフォリソースを共有する。例えば、ワークフローＷＦ１，ＷＦ２に含まれる初段ワークフロースケジューリングタスクｔｗｆ１０，ｔｗｆ２０、中断ワークフロースケジューリングタスクｔｗｆ１１，ｔｗｆ２１、中断ワークフロースケジューリングタスクｔｗｆ１２，ｔｗｆ２２、終段ワークフロースケジューリングタスクｔｗｆ１３，ｔｗｆ２３は、それぞれセマフォリソースを共有する。
【０１２４】
ワークフロースケジューリングタスクは通常タスクと同様に、実行可能状態になるとタスクスケジューラＴＳに入力され、実行される。ただし、ワークフロースケジューリングタスクに対するワークフロースケジューリングは行われない。また、ワークフロースケジューリングタスクはどのタスクグループＴＧにも属さない。
【０１２５】
なお、ワークフロースケジューリングタスクに割り当てられるリソースは、各タスクグループＴＧに割当てられるリソースと区別されてもよい。
【０１２６】
また、論理ユニットＬＵの数Ｎ＿ｌｕ＝１の場合、セマフォに代えてミューテックスを使用可能である。
【０１２７】
図１０は、本実施形態に係るマルチワークフロースケジューリングシステムの一例を示す図である。本実施形態に係るマルチワークフロースケジューリングシステムは、拡大ＷＦＤＡＧで記述されるワークフローを処理する。なお、図４と重複する構成については、説明を省略する。
【０１２８】
マルチワークフロースケジューリングシステムは、ワークフローマネージャＷＦＭ、統合タスクスケジューラＷＦＴＳ、リソースマネージャＲＭ、計算ノードＣＮを含む。
【０１２９】
ワークフローマネージャＷＦＭは、拡大ＷＦＤＡＧ情報に基づき、各ワークフローに含まれるタスクのタスク状態を管理する。ワークフローマネージャＷＦＭは、統合タスクスケジューラＷＦＴＳに対して各ワークフローの実行可能タスクのタスク実行要求Ｒ１を送信する。
【０１３０】
ワークフローマネージャＷＦＭは、図４のワークフローマネージャＷＦＭと同様に、例えばsnakemakeプログラムにより実装される。また、１つのマルチワークフロースケジューリングシステム内には、複数のワークフローマネージャＷＦＭが存在してもよい。
【０１３１】
なお、ワークフローマネージャＷＦＭは、タスクグループ定義表（図３参照）に基づき、ＷＦＤＡＧ情報から拡大ＷＦＤＡＧ情報を自動生成してもよい。
【０１３２】
統合タスクスケジューラＷＦＴＳは、図４におけるワークフロースケジューラＷＦＳ及びタスクスケジューラＴＳを統合したスケジューラである。
【０１３３】
統合タスクスケジューラＷＦＴＳは、リソースマネージャＲＭから利用可能リソース情報Ｒ５を受信する。
【０１３４】
統合タスクスケジューラＷＦＴＳは、ワークフローマネージャＷＦＭからタスク実行要求Ｒ１を受信すると、タスク実行要求Ｒ１で指定されたタスクの中から実行タスクを選択し、利用可能リソース情報Ｒ５を参照して、当該実行タスクに対し所定の計算ノードＣＮの所定のリソースを割当てる。なお、リソースの割り当ての際、統合タスクスケジューラＷＦＴＳは、ワークフロースケジューリングタスクにはワークフロースケジューリングタスクに対応するリソースプールＲＰを、通常タスクにはタスクが所属するタスクグループＴＧに対応するリソースプールＲＰを参照してもよい。
【０１３５】
その後、統合タスクスケジューラＷＦＴＳは、リソースマネージャＲＭに対しタスク実行依頼Ｒ３を送信する。
【０１３６】
なお、１つのマルチワークフロースケジューリングシステム内には、複数の統合タスクスケジューラＷＦＴＳが存在してもよい。各統合タスクスケジューラＷＦＴＳは、複数のワークフローマネージャＷＦＭを扱ってもよい。
【０１３７】
統合タスクスケジューラは、例えば、上述のＦｅｎｚｏスケジューラなどである。
【０１３８】
リソースマネージャＲＭ及び計算ノードＣＮは、図４と同様であるため、説明を省略する。
【０１３９】
なお、統合タスクスケジューラＷＦＴＳが複数のＯＳ上に存在する場合（すなわち、分散システム上で動作する場合）、各計算ノードＣＮは、分散ロックマネージャ（ＤＬＭ）の機能をさらに備えてもよい。分散ロックマネージャは、例えば分散ファイルロックコマンドを提供し、分散セマフォ及び分散ミューテックスは分散ファイルロックコマンドにより実現される。
【０１４０】
図１１は、本実施形態に係るスケジューリング処理の一例を示す図である。
【０１４１】
ステップＳ２０１〜Ｓ２０３の処理は、図６のステップＳ１０１〜Ｓ１０３の処理と同様であるため、説明を省略する。なお、ステップＳ２０１，Ｓ２０２の処理は、ステップ２０３の前に行われなくてもよいが、ステップＳ２０４の処理の前に行われることが好ましい。ステップＳ２０１，Ｓ２０２の処理は、ステップＳ２０３の処理と非同期に行われてもよい。
【０１４２】
統合タスクスケジューラＷＦＴＳは、ワークフローマネージャＷＦＭよりタスク実行要求Ｒ１を受信すると、当該タスク実行要求Ｒ１に含まれるタスク識別子（又はタスク名）により、各タスクがワークフロースケジューリングタスクであるか通常タスクであるかを識別する。統合タスクスケジューラＷＦＴＳは、ワークフロースケジューリングタスクに対してリソースを割り当て（ステップＳ２０４）、さらに、通常タスクに対してリソースを割り当てる（ステップＳ２０５）。なお、ステップＳ２０４及びステップＳ２０５の処理順は逆でもよい。
【０１４３】
統合タスクスケジューラＷＦＴＳは、ワークフロースケジューリングタスク及び通常タスクの中から、実行タスクを選択し、リソースマネージャＲＭに対して当該実行タスクへの割当リソース情報を含むタスク実行依頼Ｒ３を送信する（ステップＳ２０６）。
【０１４４】
ステップＳ２０７〜Ｓ２１３の処理は、図４のステップＳ１０８〜Ｓ１１４の処理と同様であるため、説明を省略する。
【０１４５】
［第３の実施形態］
本実施形態においては、上記第１及び第２の実施形態の変形例について説明する。本実施形態では、図４におけるワークフローマネージャＷＦＭ及びワークフロースケジューラＷＦＳを統合した統合ワークフローマネージャＷＦＭＳ（Work Flow Manager and Scheduler）を用いる。
【０１４６】
図１２は、本実施形態に係るマルチワークフロースケジューリングシステムの一例を示す図である。本実施形態に係るマルチワークフロースケジューリングシステムにおいては、第２の実施形態と同様に、拡大ＷＦＤＡＧで記述されるワークフローを処理する。なお、図４及び図１０と重複する構成については、説明を省略する。
【０１４７】
マルチワークフロースケジューリングシステムは、統合ワークフローマネージャＷＦＭＳ、タスクスケジューラＴＳ、リソースマネージャＲＭ、計算ノードＣＮを含む。
【０１４８】
統合ワークフローマネージャＷＦＭＳは、拡大ＷＦＤＡＧ情報に基づき、各ワークフローに含まれるタスクのタスク状態を管理する。統合ワークフローマネージャＷＦＭＳは、各ワークフローの実行可能タスクが通常タスクである場合に、実行可能タスクの中から実行タスクを選択し、タスク実行要求Ｒ２をタスクスケジューラＴＳに送信する。一方、実行可能タスクがワークフロースケジューリングタスクである場合に、当該ワークフロースケジューリングタスクを実行する。
【０１４９】
統合ワークフローマネージャＷＦＭＳは、図４のワークフローマネージャＷＦＭと同様に、例えばsnakemakeプログラムにより実装される。また、１つのマルチワークフロースケジューリングシステム内には、複数の統合ワークフローマネージャＷＦＭＳが存在してもよい。
【０１５０】
統合ワークフローマネージャＷＦＭＳは、タスクグループ定義表（図３参照）に基づき、ＷＦＤＡＧ情報から拡大ＷＦＤＡＧ情報を自動生成してもよい。
【０１５１】
なお、統合ワークフローマネージャＷＦＭＳが複数のＯＳ上に存在する場合（すなわち、分散システム上で動作する場合）、各統合ワークフローマネージャＷＦＭＳは、分散ロックマネージャ（ＤＬＭ）の機能をさらに備えてもよい。分散ロックマネージャは、例えば分散ファイルロックコマンドを提供し、分散セマフォ及び分散ミューテックスは分散ファイルロックにより実現される。
【０１５２】
タスクスケジューラＴＳ、リソースマネージャＲＭ及び計算ノードＣＮは図４と同様であるため、説明を省略する。
【０１５３】
図１３は、本実施形態に係るスケジューリング処理の一例を示す図である。
【０１５４】
ステップＳ３０１，Ｓ３０２の処理は、図６のステップＳ１０１，Ｓ１０２の処理と同様であるため、説明を省略する。なお、ステップＳ３０１，Ｓ３０２の処理は、ステップ３０５の前に行われなくてもよいが、ステップＳ３０６の処理の前に行われることが好ましい。ステップＳ３０１，Ｓ３０２の処理は、ステップＳ３０３〜Ｓ３０５の処理と非同期に行われてもよい。
【０１５５】
統合ワークフローマネージャＷＦＭＳは、各ワークフローに含まれるタスクのタスク状態を管理し、ワークフロースケジューリングタスクが実行可能である場合に、当該ワークフロースケジューリングタスクを実行する（ステップＳ３０３）。また、統合ワークフローマネージャＷＦＭＳは、通常タスクの中から実行タスクを選択し（ステップＳ３０４）、タスクスケジューラＴＳに対して実行タスクの情報を含むタスク実行要求Ｒ２を送信する（ステップＳ３０５）。
【０１５６】
ステップＳ３０６〜Ｓ３１４の処理は、図４のステップＳ１０６〜Ｓ１１４の処理と同様であるため、説明を省略する。
【０１５７】
［第４の実施形態］
本実施形態においては、第１乃至第３の実施形態で説明したセマフォ及びミューテックスの実現方法について説明する。本実施形態においては、例えば、Ｌｉｎｕｘ（登録商標）のｆｌｏｃｋコマンドを用いたファイルロックにより、セマフォ及びミューテックスを実現する。
【０１５８】
ここで、ｆｌｏｃｋコマンドの書式は、例えば「flock [ファイル名] -c “スクリプト名”」である。各ワークフロースケジューリングタスクは、当該コマンドを実行することにより、[ファイル名]に対するファイルロックを取得する。また、ファイルロックの取得と同時に、“スクリプト名”で指定されるスクリプトが実行される。
【０１５９】
なお、ファイルロックが取得できない場合、ワークフロースケジューリングタスクは、例えばファイルロック取得待ち用のキューに格納される。また、スクリプトの実行が完了すると当該ファイルロックは解除される。
【０１６０】
タスクグループごとに、ｃｔｒファイル、ｑｕｅファイル、ｓｉｇファイル以下のファイルが定義され、例えば共有ファイルシステムＳＦＳに格納される。
【０１６１】
ｃｔｒファイルは、セマフォカウンタの操作に用いられるファイルである。ｃｔｒファイルは、セマフォカウンタ値を格納する。なお、セマフォカウンタ値の初期値は、例えば、論理ユニットＬＵの数Ｎ＿ｌｕである。なお、セマフォに代えてミューテックスが用いられる場合、セマフォカウンタは不要であるため、ｃｔｒファイルは省略可能である。
【０１６２】
ｑｕｅファイルは、ファイルロック取得待ちのためのキューの操作に用いられるファイルである。
【０１６３】
ｓｉｇファイルは、子タスクの処理が全て終了したことを通知する際に用いられるファイルである。
【０１６４】
本実施形態においては、共有ファイルシステムＳＦＳとして、ＯＣＦＳ２（Oracle Cluster File System ver.2）が用いられてもよい。ＯＣＦＳ２においては、例えば複数の計算ノードＣＮより同時に共有ファイルシステムＳＦＳ上のファイルにアクセスされた時などに排他制御を行うために、分散ロックマネージャ（ＤＬＭ）を使用した分散ファイルロック機構が提供される。ＯＣＦＳ２においては、上述のｆｌｏｃｋコマンドを用いることにより、ＯＣＦＳ２上の当該分散ファイルロック機構にアクセス可能である。すなわち、ＯＣＦＳ２上では、ｆｌｏｃｋコマンドにより分散セマフォ及び分散ミューテックスが実現される。
【０１６５】
図１４は、セマフォを用いた場合の初段ワークフロースケジューリングタスクの処理を例示するフローチャートである。以下のステップＳ５０１〜Ｓ５０３の処理は、セマフォに対するＰ命令に相当する。
【０１６６】
ステップＳ５０１において、初段ワークフロースケジューリングタスクは、例えばｆｌｏｃｋコマンド「flock ctr[i] -c “スクリプト１”」を実行する。整数ｉは、拡大ＷＦＤＡＧ内の子タスクのタスクグループ番号を示しており、ctr[i]は、整数ｉに対応するタスクグループのｃｔｒファイルを示す。
【０１６７】
スクリプト１において、初段ワークフロースケジューリングタスクは、ｃｔｒファイルに格納されているセマフォカウンタ値を読み出し、当該セマフォカウンタ値を１だけ減少させる。減少後の当該セマフォカウンタ値は、ファイル「status」にも格納される。初段ワークフロースケジューリングタスクは、当該セマフォカウンタ値をｃｔｒに書き込む。
【０１６８】
ステップＳ５０２において、初段ワークフロースケジューリングタスクは、ｃａｔコマンドを用いて、ステップＳ５０１で生成したファイル「status」の値を確認する。ｃａｔコマンドは、指定されたファイルの内容を読み出すコマンドである。ファイル「status」の値が０以下の場合、処理は終了する。ファイル「status」の値が１以上の場合、処理はステップＳ５０３へ進む。
【０１６９】
なお、ファイル「status」の値が負である場合、論理ユニットＬＵの数Ｎ＿ｌｕ個のワークフローにおいて、当該タスクグループ内のタスクが実行中状態である。したがって、この場合はｑｕｅファイルに対するロックが必要となる。なお、ファイル「status」の値が負の場合は、１以上のワークフローがｑｕｅファイルのロック解除待ち状態となる。
【０１７０】
ステップＳ５０３において、初段ワークフロースケジューリングタスクは、例えばｆｌｏｃｋコマンド「flock que[i] -c “スクリプト２”」を実行する。que[i]は、整数ｉに対応するタスクグループのｑｕｅファイルを示す。
【０１７１】
スクリプト２は、子タスクの処理が全て完了したか否かを検知する。スクリプト２において、初段ワークフロースケジューリングタスクは、定期的に、ｓｉｇファイルが生成されているか否かを確認する。ｓｉｇファイルが生成された場合、初段ワークフロースケジューリングタスクは、当該ｓｉｇファイルを削除して終了する。ｓｉｇファイルが生成さていない場合、初段ワークフロースケジューリングタスクは、当該ｓｉｇファイルが生成されるまで待機する。なお、ｓｉｇファイルの生成については、図１５で説明する。
【０１７２】
図１５は、セマフォを用いた場合の終段ワークフロースケジューリングタスクの処理を例示するフローチャートである。以下のステップＳ６０１の処理は、セマフォに対するＶ命令に相当する。
【０１７３】
ステップＳ６０１において、終段ワークフロースケジューリングタスクは、例えばｆｌｏｃｋコマンド「flock ctr[i] -c “スクリプト３”」を実行する。ctr[i]は、整数ｉに対応するタスクグループのｃｔｒファイルを示す。
【０１７４】
スクリプト３において、終段ワークフロースケジューリングタスクは、ｃｔｒファイルに格納されているセマフォカウンタ値を読み出し、当該セマフォカウンタ値を１だけ増加させる。増加後の当該セマフォカウンタ値が１以下であれば、ｓｉｇファイルを生成し、当該ｓｉｇファイルが削除されるまで待つ。
【０１７５】
なお、増加後のセマフォカウンタ値が１以下である場合、ｑｕｅファイルのロック解除待ち状態のワークフローが存在する。このため、終段ワークフロースケジューリングタスクは、ｓｉｇファイルを生成することにより、上述のスクリプト２を実行中のワークフローに対して処理完了を知らせる。その後、スクリプト２においてｓｉｇファイルが削除され、スクリプト２の終了によりｑｕｅファイルのロック解除後、キューの先頭のワークフローがロック解除を受ける。
【０１７６】
図１６は、セマフォを用いた場合の中段ワークフロースケジューリングタスクの処理を例示するフローチャートである。中断ワークフロースケジューリングタスクは、上述のように、終段ワークフロースケジューリングタスクと初段ワークフロースケジューリングタスクとを組み合わせることにより生成される。
【０１７７】
したがって、中断ワークフロースケジューリングタスクにおいては、まず図１５で示したセマフォに対するＶ命令相当の処理（ステップＳ６０１）が実行され、次に、図１４で示したセマフォに対するＶ命令相当の処理（ステップＳ５０１〜Ｓ５０３）が実行される
。
【０１７８】
図１７は、ミューテックスを用いた場合の初段ワークフロースケジューリングタスクの処理を例示するフローチャートである。
【０１７９】
ステップＳ７０１において、初段ワークフロースケジューリングタスクは、例えばｆｌｏｃｋコマンド「flock que[i] -c “スクリプト４”」を実行する。
【０１８０】
スクリプト４において、初段ワークフロースケジューリングタスクは、定期的に、ｓｉｇファイルが生成されているか否かを確認する。ｓｉｇファイルが生成された場合、初段ワークフロースケジューリングタスクは、当該ｓｉｇファイルを削除して終了する。ｓｉｇファイルが生成さていない場合、初段ワークフロースケジューリングタスクは、当該ｓｉｇファイルが生成されるまで待機する。
【０１８１】
図１８は、ミューテックスを用いた場合の終段ワークフロースケジューリングタスクの処理を例示するフローチャートである。
【０１８２】
ステップＳ８０１において、終段ワークフロースケジューリングタスクは、例えばｓｉｇファイルを削除する旨のコマンド「rm sig[i]」を実行する。sig[i]は、整数ｉに対応するタスクグループのｓｉｇファイルを示す。
【０１８３】
図１９は、ミューテックスを用いた場合の中断ワークフロースケジューリングタスクの処理を例示するフローチャートである。
【０１８４】
図１７と同様、中断ワークフロースケジューリングタスクは、終段ワークフロースケジューリングタスクと中断ワークフロースケジューリングタスクとを組み合わせたタスクである。すなわち、中断ワークフロースケジューリングタスクにおいては、まずステップＳ８０１の処理が実行され、次に、ステップＳ７０１の処理が実行される。
【０１８５】
以上説明した本実施形態においては、所定のファイルシステム及びＯＳのファイルロックコマンドを用いてセマフォ及びミューテックスを実現する。これにより、簡便に排他制御を実装可能となる。
【０１８６】
［第５の実施形態］
本実施形態においては、第１乃至第４の実施形態で説明したマルチワークフロースケジューリングシステムが搭載される電子機器の具体例を例示する。
【０１８７】
図２０は、本実施形態に係る電子機器の一例を示すブロック図である。この電子機器は、例えば、ストレージシステムＳＳとして実現され得る。このストレージシステムＳＳは、例えば、ネットワーク経由で接続されるクライアント装置Ｄからの要求に応じて、データの書き込み、データの読み出し、データの更新、データの削除などを実行するファイルサーバとして機能する。図２０に示すように、ストレージシステムＳＳは、ネットワークスイッチ１０、複数のコネクションユニット（ＣＵ）２０、および複数のノードモジュール（ＮＭ）３０を備えている。
【０１８８】
ＮＭ３０は、ノードコントローラ（ＮＣ）３１と、一つ以上のＮＡＮＤ型フラッシュメモリ３２とを有している。ＮＣ３１は、ＮＡＮＤ型フラッシュメモリ３２に対するアクセス制御と、データの転送制御とを実行する。ＮＣ３１は、例えば４系統の入出力ポートを有しており、ＮＣ３１同士を接続することにより、複数のＮＭ３０を、例えばマトリックス状に相互に接続することができる。複数のＮＭ３０を相互に接続することにより、ストレージシステムＳＳは、大容量のデータ記憶領域４０を論理的に構築する。
【０１８９】
ＣＵ２０は、クライアント装置Ｄからの要求に応じて、前述のように構築されたデータ記憶領域４０に対するデータの入出力処理（データの更新、データの削除を含む）を実行する。より詳細には、クライアント装置Ｄからの要求に対応する、複数のＮＭ３０の中の目的のＮＭ３０に対してデータの入出力命令を発行する。以下、ＣＵ２０からＮＭ３０へ発行されるデータの入出力命令を、コマンドと称することがある。
【０１９０】
ＣＵ２０は、ＣＰＵ２１、ＲＡＭ２２およびＮＭインタフェース２３を有している。ＣＵ２０の各機能は、ＲＡＭ２２に格納され、ＣＰＵ２１によって実行されるプログラムにより実現される。ＮＭインタフェース２３は、ＮＭ３０、より詳細には、ＮＣ３１との間の通信を実行する。ＮＭインタフェース２３は、複数のＮＭ３０の中のいずれか１つのＮ
Ｍ３０のＮＣ３１と接続されている。つまり、ＣＵ２０は、ＮＭインタフェース２３を介して、複数のＮＭ３０の中のいずれか１つのＮＭ３０と直接的に接続され、ＮＭ３０のＮＣ３１を介して、その他のＮＭ３０と間接的に接続される。ＣＵ２０と直接的に接続されるＮＭ３０は、ＣＵ２０毎に異なっている。
【０１９１】
前述したように、ＣＵ２０は、複数のＮＭ３０の中のいずれか一つのＮＭ３０と直接的に接続される。したがって、ＣＵ２０が、直接的に接続されるＮＭ３０以外のＮＭ３０に対してデータの入出力命令を発行する場合においても、その入出力命令は、まず、直接的に接続されるＮＭ３０へ転送される。その後、その入出力命令は、各ＮＭ３０のＮＣ３１を介して目的のＮＭ３０まで転送される。
【０１９２】
例えば、ＮＭ３０がマトリックス状に相互に接続される場合、行番号と列番号との組合せで各ＮＭ３０に識別子（Ｍ，Ｎ）が付されるものと想定すると、ＮＣ３１は、自ＮＭ３０の識別子と、入出力命令の送り先として指定される識別子とを比較することにより、第１に、その入出力命令が自ＮＭ３０宛てか否かを判断できる。自ＮＭ３０宛てでない場合、ＮＣ３１は、自ＮＭ３０の識別子と、入出力命令の送り先として指定される識別子との関係、より詳細には、行番号、列番号それぞれの大小関係から、第２に、隣接するＮＭ３０の中のいずれのＮＭ３０へ転送すべきかを判断できる。入出力命令を目的のＮＭ３０まで転送する手法については、特定の手法に限定されるものではなく、既知のいずれの手法も採用し得る。本来であれば転送先として選ばれることがないＮＭ３０への経路も、予備経路として使用され得る。
【０１９３】
また、ＮＭ３０による、入出力命令に応じた入出力処理の結果、すなわち、ＮＡＮＤ型フラッシュメモリ３２に対するアクセスの結果も、前述した入出力命令の転送と同様、ＮＣ３１の働きにより、他のＮＭ３０をいくつか経由して入出力命令の発行元であるＣＵ２０まで転送される。例えば、入出力命令の発行元の情報として、ＣＵ２０が直接的に接続されるＮＭ３０の識別子を含ませることで、この識別子を処理結果の転送先として指定することができる。
【０１９４】
さらに、ＮＣ３１は、割り込み要求信号を転送するための入出力ポートを別途例えば４系統有しており、前述した入出力命令および処理結果と同様、ＮＭ３０からＣＵ２０までの割り込み要求信号の転送経路が動的に決定される。
【０１９５】
ネットワークスイッチ１０は、クライアント装置Ｄからの要求を受け付け、その要求を複数のＣＵ２０のいずれかに転送する。典型的には、ネットワークスイッチ１０は、複数のＣＵ２０の負荷が均等となるように、クライアント装置Ｄからの要求を複数のＣＵ２０へ振り分ける。なお、ここでは、ネットワークスイッチ１０を設ける例を示しているが、複数のＣＵ２０の中の１つのＣＵ２０がマスタとして動作して、ネットワークスイッチ１０の役割を担ってもよい。ネットワークスイッチ１０は、ＣＵ２０から受領した処理結果をクライアント装置Ｄへ返送する。
【０１９６】
図２１は、ＮＭ３０の構成（ＮＣ３１の詳細な構成）の一例を示す図である。
【０１９７】
前述したように、ＮＭ３０は、ＮＣ３１と、一つ以上のＮＡＮＤ型フラッシュメモリ３２とを有している。ＮＣ３１は、図２１に示されるように、ＣＰＵ３１１、ＲＡＭ３１２、Ｉ／Ｏコントローラ３１３およびＮＡＮＤインタフェース３１４を有している。ＮＣ３１の各機能は、ＲＡＭ３１２に格納され、ＣＰＵ３１１によって実行されるプログラムにより実現される。Ｉ／Ｏコントローラ３１３は、ＣＵ２０（より詳細には、ＮＭインタフェース２３）または他のＮＭ３０（より詳細には、ＮＣ３１）との間の通信を実行する。ＮＡＮＤインタフェース３１４は、ＮＡＮＤ型フラッシュメモリ３２に対するアクセスを実行する。
【０１９８】
ところで、図１に示す計算機システム１は、図２０，２１を用いて説明したストレージシステムＳＳ及びクライアント装置Ｄを用いて柔軟に構成され得る。例えば、第１ノードＦＮはクライアント装置Ｄであり、切替装置ＳＷはネットワークスイッチ１０であり、計算ノードＣＮはＣＵ２０であってもよい。また、複数のＣＵ２０のうちいずれか１つが第１ノードＦＮの役割を担い、他のＣＵ２０が計算ノードＣＮとして動作してもよい。
【０１９９】
また、第１のノードＦＮは省略可能でもよい。この場合、第１ノードＦＮの動作を、複数のＣＵ２０が分担してもよい。すなわち、プログラムＰＧに含まれるワークフローマネージャＷＦＭ、ワークフロースケジューラＷＦＳ、タスクスケジューラＴＳ、リソースマネージャＲＭなどの各機能は、複数のＣＵ２０のＣＰＵ２１で分散して実行されてもよい。
【０２００】
すなわち、ストレージシステムＳＳ及びクライアント装置Ｄが一体となって計算機システム１を構成してもよく、ストレージシステムＳＳのみで計算機システム１を構成してもよい。
【０２０１】
以上説明したように、各実施形態によれば、計算機システム１は、マルチワークフロースケジューリングシステムを実現するためのプログラムＰＧと、少なくとも１つ以上の計算ノードＣＮと、共有ファイルシステムＳＦＳとを含む。論理ユニットＬＵは、少なくとも１つ以上の計算ノードＣＮを含む計算単位である。プログラムＰＧは、ワークフローマネージャＷＦＭと、ワークフロースケジューラＷＦＳと、タスクスケジューラＴＳと、リソースマネージャＲＭとを含む。このような構成において、ワークフロースケジューラＷＦＳは、タスクグループごとに、タスクが同時に実行されるワークフローの数が複数の論理ユニットＬＵの数以下に制限されるように、計算ノードへのタスクの割り当てを行う。これにより、単位時間当たりに論理ユニットＬＵの数の定常処理スループットを確保し、かつ全処理時間を抑えることができる。さらに、処理量がワークフロー数及びワークフローの定義に依存せず、異種ワークフローにも対応可能である。
【０２０２】
また、第２及び第３の実施形態に係るマルチワークフロースケジューリングシステムにおいては、通常タスクに加え、ワークフロースケジューリングタスクが定義される。これにより、統合ワークフローマネージャＷＦＭＳ又は統合タスクスケジューラＷＦＴＳは、セマフォ又はミューテックスによるワークフロー処理の排他制御を、タスクとして実行可能となるため、計算機システム１の処理効率を高めることができる。
【０２０３】
本発明のいくつかの実施形態を説明したが、これらの実施形態は、例として提示したものであり、発明の範囲を限定することは意図していない。これら新規な実施形態は、その他の様々な形態で実施されることが可能であり、発明の要旨を逸脱しない範囲で、種々の省略、置き換え、変更を行うことができる。これら実施形態やその変形は、発明の範囲や要旨に含まれるとともに、特許請求の範囲に記載された発明とその均等の範囲に含まれる。
【符号の説明】
【０２０４】
１…計算機システム、２…記憶装置、３，５…ＣＰＵ、４，６…ＲＡＭ、７…コア、ＣＮ…計算ノード、ＦＳ…共有ファイルシステム、ＬＵ…論理ユニット、ＷＦＭＳ…統合ワークフローマネージャ、ＷＦＭ…ワークフローマネージャ、ＷＦＴＳ…統合タスクスケジューラ、ＷＦＳ…ワークフロースケジューラ、ＴＳ…タスクスケジューラ、ＲＭ…リソースマネージャ、ＣＮ…計算ノード。
【図１】
2019121240.tif 000006
【図２】
2019121240.tif 000007
【図３】
2019121240.tif 000008
【図４】
2019121240.tif 000009
【図５】
2019121240.tif 000010
【図６】
2019121240.tif 000011
【図７】
2019121240.tif 000012
【図８】
2019121240.tif 000013
【図９】
2019121240.tif 000014
【図１０】
2019121240.tif 000015
【図１１】
2019121240.tif 000016
【図１２】
2019121240.tif 000017
【図１３】
2019121240.tif 000018
【図１４】
2019121240.tif 000019
【図１５】
2019121240.tif 000020
【図１６】
2019121240.tif 000021
【図１７】
2019121240.tif 000022
【図１８】
2019121240.tif 000023
【図１９】
2019121240.tif 000024
【図２０】
2019121240.tif 000025
【図２１】
2019121240.tif 000026